diff --git a/tools/depmod.c b/tools/depmod.c
index f2b370f..dea60ea 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -37,7 +37,10 @@
 #include <shared/util.h>
 #include <shared/scratchbuf.h>
 
-#include <libkmod/libkmod.h>
+#include <libkmod/libkmod-internal.h>
+
+#undef ERR
+#undef DBG
 
 #include "kmod.h"
 
@@ -785,6 +788,7 @@
 
 
 /* depmod calculations ***********************************************/
+struct vertex;
 struct mod {
 	struct kmod_module *kmod;
 	char *path;
@@ -800,6 +804,7 @@
 	uint16_t idx; /* index in depmod->modules.array */
 	uint16_t users; /* how many modules depend on this one */
 	bool visited; /* helper field to report cycles */
+	struct vertex *vertex; /* helper field to report cycles */
 	char modname[];
 };
 
@@ -1450,105 +1455,228 @@
 	}
 }
 
-static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
-				 uint16_t n_roots, uint16_t *users,
-				 uint16_t *stack, uint16_t *edges)
+struct vertex {
+	struct vertex *parent;
+	struct mod *mod;
+};
+
+static struct vertex *vertex_new(struct mod *mod, struct vertex *parent)
+{
+	struct vertex *v;
+
+	v = malloc(sizeof(*v));
+	if (v == NULL)
+		return NULL;
+
+	v->parent = parent;
+	v->mod = mod;
+	return v;
+}
+
+static void depmod_list_remove_data(struct kmod_list **list, void *data)
+{
+	struct kmod_list *l;
+
+	l = kmod_list_remove_data(*list, data);
+	*list = l;
+}
+
+static void depmod_report_one_cycle(struct depmod *depmod,
+				    struct vertex *vertex,
+				    struct kmod_list **roots,
+				    struct hash *loop_set)
 {
 	const char sep[] = " -> ";
-	int ir = 0;
-	int num_cyclic = 0;
+	size_t sz;
+	char *buf;
+	struct array reverse;
+	int i;
+	int n;
+	struct vertex *v;
 
-	while (n_roots > 0) {
-		int is, ie;
+	array_init(&reverse, 3);
 
-		for (; ir < n_mods; ir++) {
-			if (users[ir] > 0) {
-				break;
-			}
-		}
+	sz = 0;
+	for (v = vertex->parent, n = 0;
+	     v != NULL;
+	     v = v->parent, n++) {
 
-		if (ir >= n_mods)
-			break;
+		sz += v->mod->modnamesz - 1;
+		array_append(&reverse, v);
+		hash_add(loop_set, v->mod->modname, NULL);
+	}
+	sz += vertex->mod->modnamesz - 1;
 
-		/* New DFS with ir as root, no edges */
-		stack[0] = ir;
-		ie = 0;
+	buf = malloc(sz + n * strlen(sep) + 1);
 
-		/* at least one root less */
-		n_roots--;
+	sz = 0;
+	for (i = reverse.count - 1; i >= 0; i--) {
+		size_t len;
 
-		/* skip this root on next iteration */
-		ir++;
+		v = reverse.array[i];
 
-		for (is = 1; is > 0;) {
-			uint16_t idx = stack[--is];
-			struct mod *m = depmod->modules.array[idx];
-			const struct mod **itr, **itr_end;
+		len = v->mod->modnamesz - 1;
+		memcpy(buf + sz, v->mod->modname, len);
+		sz += len;
+		strcpy(buf + sz, sep);
+		sz += strlen(sep);
 
-			DBG("Cycle report: Trying %s visited=%d users=%d\n",
-			    m->modname, m->visited, users[idx]);
+		depmod_list_remove_data(roots, v->mod);
+	}
+	strcpy(buf + sz, vertex->mod->modname);
+	ERR("Cycle detected: %s\n", buf);
 
-			if (m->visited) {
-				int i, n = 0, sz = 0;
-				char *buf;
-				bool is_cyclic = false;
+	free(buf);
+	array_free_array(&reverse);
+}
 
-				for (i = ie - 1; i >= 0; i--) {
-					struct mod *loop = depmod->modules.array[edges[i]];
-					sz += loop->modnamesz - 1;
-					n++;
-					if (loop == m) {
-						sz += loop->modnamesz - 1;
-						is_cyclic = true;
-						break;
-					}
-				}
-				/* Current module not found in dependency list.
-				 * Must be a related module. Ignore it.
-				 */
-				if (!is_cyclic)
-					continue;
+static int depmod_report_cycles_from_root(struct depmod *depmod,
+					  struct mod *root_mod,
+					  struct kmod_list **roots,
+					  void **stack,
+					  size_t stack_size,
+					  struct hash *loop_set)
+{
+	struct kmod_list *free_list = NULL; /* struct vertex */
+	struct kmod_list *l;
+	struct vertex *root;
+	struct vertex *vertex;
+	struct vertex *v;
+	struct mod *m;
+	struct mod **itr, **itr_end;
+	size_t is;
 
-				num_cyclic += n;
-
-				buf = malloc(sz + n * strlen(sep) + 1);
-				sz = 0;
-				for (i = ie - n; i < ie; i++) {
-					struct mod *loop =
-						depmod->modules.array[edges[i]];
-					memcpy(buf + sz, loop->modname,
-					       loop->modnamesz - 1);
-					sz += loop->modnamesz - 1;
-					memcpy(buf + sz, sep, strlen(sep));
-					sz += strlen(sep);
-				}
-				memcpy(buf + sz, m->modname, m->modnamesz);
-
-				ERR("Cycle detected: %s\n", buf);
-
-				free(buf);
-				continue;
-			}
-
-			m->visited = true;
-
-			if (m->deps.count == 0) {
-				continue;
-			}
-
-			edges[ie++] = idx;
-
-			itr = (const struct mod **) m->deps.array;
-			itr_end = itr + m->deps.count;
-			for (; itr < itr_end; itr++) {
-				const struct mod *dep = *itr;
-				stack[is++] = dep->idx;
-				users[dep->idx]--;
-			}
-		}
+	root = vertex_new(root_mod, NULL);
+	if (root == NULL) {
+		ERR("No memory to report cycles\n");
+		return -ENOMEM;
 	}
 
+	l = kmod_list_append(free_list, root);
+	if (l == NULL) {
+		ERR("No memory to report cycles\n");
+		return -ENOMEM;
+	}
+	free_list = l;
+
+	is = 0;
+	stack[is++] = (void *)root;
+
+	while (is > 0) {
+		vertex = stack[--is];
+		m = vertex->mod;
+		/*
+		 * because of the topological sort we can start only
+		 * from part of a loop or from a branch after a loop
+		 */
+		if (m->visited && m == root->mod) {
+			depmod_report_one_cycle(depmod, vertex,
+						roots, loop_set);
+			continue;
+		}
+
+		m->visited = true;
+		if (m->deps.count == 0) {
+			/*
+			 * boundary condition: if there is more than one
+			 * single node branch (not a loop), it is
+			 * recognized as a loop by the code above:
+			 * m->visited because more then one,
+			 * m == root->mod since it is a single node.
+			 * So, prevent deeping into the branch second
+			 * time.
+			 */
+			depmod_list_remove_data(roots, m);
+
+			continue;
+		}
+
+		itr = (struct mod **) m->deps.array;
+		itr_end = itr + m->deps.count;
+		for (; itr < itr_end; itr++) {
+			struct mod *dep = *itr;
+			v = vertex_new(dep, vertex);
+			if (v == NULL) {
+				ERR("No memory to report cycles\n");
+				return -ENOMEM;
+			}
+			assert(is < stack_size);
+			stack[is++] = v;
+
+			l = kmod_list_append(free_list, v);
+			if (l == NULL) {
+				ERR("No memory to report cycles\n");
+				return -ENOMEM;
+			}
+			free_list = l;
+
+		}
+	}
+	while (free_list) {
+		v = free_list->data;
+		l = kmod_list_remove(free_list);
+		free_list = l;
+		free(v);
+	}
+
+	return 0;
+}
+
+static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
+				 uint16_t *users)
+{
+	int num_cyclic = 0;
+	struct kmod_list *roots = NULL; /* struct mod */
+	struct kmod_list *l;
+	size_t n_r; /* local n_roots */
+	int i;
+	int err;
+	void **stack;
+	struct mod *m;
+	struct mod *root;
+	struct hash *loop_set;
+
+	for (i = 0, n_r = 0; i < n_mods; i++) {
+		if (users[i] <= 0)
+			continue;
+		m = depmod->modules.array[i];
+		l = kmod_list_append(roots, m);
+		if (l == NULL) {
+			ERR("No memory to report cycles\n");
+			return;
+		}
+		roots = l;
+		n_r++;
+	}
+
+	stack = malloc(n_r * sizeof(void *));
+	if (stack == NULL) {
+		ERR("No memory to report cycles\n");
+		return;
+	}
+
+	loop_set = hash_new(16, NULL);
+	if (loop_set == NULL) {
+		ERR("No memory to report cycles\n");
+		return;
+	}
+
+	while (roots != NULL) {
+		root = roots->data;
+		l = kmod_list_remove(roots);
+		roots = l;
+		err = depmod_report_cycles_from_root(depmod,
+						     root,
+						     &roots,
+						     stack, n_r, loop_set);
+		if (err < 0)
+			goto err;
+	}
+
+	num_cyclic = hash_get_count(loop_set);
 	ERR("Found %d modules in dependency cycles!\n", num_cyclic);
+err:
+	hash_free(loop_set);
 }
 
 static int depmod_calculate_dependencies(struct depmod *depmod)
@@ -1605,8 +1733,7 @@
 	}
 
 	if (n_sorted < n_mods) {
-		depmod_report_cycles(depmod, n_mods, n_mods - n_sorted,
-				     users, roots, sorted);
+		depmod_report_cycles(depmod, n_mods, users);
 		ret = -EINVAL;
 		goto exit;
 	}