From c89d219884e3b5d9faa7052175964cc4a6a59dfa Mon Sep 17 00:00:00 2001
From: Lucas De Marchi <lucas.demarchi@intel.com>
Date: Fri, 30 May 2014 09:38:26 -0300
Subject: [PATCH] depmod: Add better error messages when facing loops

Since now depmod fails when there are module loops, let's at least give
better error messages, printing the loops we found. Since we may have
more than 1 loop, just printing the modules that are in loop is not
very clear.

Assuming as an example 2 independent loops, this is how the new messages
compare to the old ones:

Before:
	depmod: ERROR: Found 5 modules in dependency cycles!
	depmod: ERROR: /tmp/test-kmod//lib/modules/3.14.4-1-ARCH/kernel/moduleE.ko in dependency cycle!
	depmod: ERROR: /tmp/test-kmod//lib/modules/3.14.4-1-ARCH/kernel/moduleB.ko in dependency cycle!
	depmod: ERROR: /tmp/test-kmod//lib/modules/3.14.4-1-ARCH/kernel/moduleC.ko in dependency cycle!
	depmod: ERROR: /tmp/test-kmod//lib/modules/3.14.4-1-ARCH/kernel/moduleD.ko in dependency cycle!
	depmod: ERROR: /tmp/test-kmod//lib/modules/3.14.4-1-ARCH/kernel/moduleA.ko in dependency cycle!

After:
	depmod: ERROR: Found 5 modules in dependency cycles!
	depmod: ERROR: Cycle detected: moduleE -> moduleD -> moduleE
	depmod: ERROR: Cycle detected: moduleB -> moduleC -> moduleA -> moduleB
---
 tools/depmod.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 93 insertions(+), 9 deletions(-)

diff --git a/tools/depmod.c b/tools/depmod.c
index b8516c9..e90ff83 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -927,6 +927,7 @@ struct mod {
 	int dep_sort_idx; /* topological sort index */
 	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 */
 	char modname[];
 };
 
@@ -1577,6 +1578,96 @@ static void depmod_sort_dependencies(struct depmod *depmod)
 	}
 }
 
+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)
+{
+	const char sep[] = " -> ";
+	int ir = 0;
+	ERR("Found %u modules in dependency cycles!\n", n_roots);
+
+	while (n_roots > 0) {
+		int is, ie;
+
+		for (; ir < n_mods; ir++) {
+			if (users[ir] > 0) {
+				break;
+			}
+		}
+
+		if (ir >= n_mods)
+			break;
+
+		/* New DFS with ir as root, no edges */
+		stack[0] = ir;
+		ie = 0;
+
+		/* at least one root less */
+		n_roots--;
+
+		/* skip this root on next iteration */
+		ir++;
+
+		for (is = 1; is > 0;) {
+			uint16_t idx = stack[--is];
+			struct mod *m = depmod->modules.array[idx];
+			const struct mod **itr, **itr_end;
+
+			DBG("Cycle report: Trying %s visited=%d users=%d\n",
+			    m->modname, m->visited, users[idx]);
+
+			if (m->visited) {
+				int i, n = 0, sz = 0;
+				char *buf;
+
+				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;
+						break;
+					}
+				}
+
+				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]--;
+			}
+		}
+	}
+}
+
 static int depmod_calculate_dependencies(struct depmod *depmod)
 {
 	const struct mod **itrm;
@@ -1631,16 +1722,9 @@ static int depmod_calculate_dependencies(struct depmod *depmod)
 	}
 
 	if (n_sorted < n_mods) {
-		ERR("Found %u modules in dependency cycles!\n",
-		    n_mods - n_sorted);
+		depmod_report_cycles(depmod, n_mods, n_mods - n_sorted,
+				     users, roots, sorted);
 		ret = -EINVAL;
-		for (i = 0; i < n_mods; i++) {
-			struct mod *m;
-			if (users[i] == 0)
-				continue;
-			m = depmod->modules.array[i];
-			ERR("%s in dependency cycle!\n", m->path);
-		}
 		goto exit;
 	}
 
-- 
2.7.4