- optional fancy pruning-mode for depmod

2 files changed, 121 insertions, 21 deletions

diff --git a/modutils/Config.in b/modutils/Config.in
index c69e1b376..fb7fb2266 100644
--- a/modutils/Config.in
+++ b/modutils/Config.in
@@ -11,6 +11,20 @@ config DEPMOD
 	help
 	  depmod generates modules.dep (FIXME: elaborate)
 
+config FEATURE_DEPMOD_PRUNE_FANCY
+	bool "fancy dependency pruning"
+	default n
+	depends on DEPMOD
+	help
+	  By default modules.dep contains all dependencies as listed by
+	  the modules.
+	  If you enable this option then we remove implied modules from
+	  the dependencies.
+	  This makes depmod somewhat bigger but generates a smaller
+	  modules.dep file.
+
+	  If unsure, say N.
+
 config INSMOD
 	bool "insmod"
 	default n
diff --git a/modutils/depmod.c b/modutils/depmod.c
index e061501f6..b0b09c235 100644
--- a/modutils/depmod.c
+++ b/modutils/depmod.c
@@ -10,15 +10,27 @@
 #define _GNU_SOURCE
 #include <libbb.h>
 #include <sys/utsname.h> /* uname() */
-
+#if ENABLE_DEBUG
+#include <assert.h>
+#define dbg_assert assert
+#else
+#define dbg_assert(stuff) do {} while (0)
+#endif
 /*
  * Theory of operation:
  * - iterate over all modules and record their full path
  * - iterate over all modules looking for "depends=" entries
  *   for each depends, look through our list of full paths and emit if found
  */
+
+typedef struct dep_lst_t {
+	char *name;
+	llist_t *dependencies;
+	struct dep_lst_t *next;
+} dep_lst_t;
+
 struct globals {
-	llist_t *lst; /* modules without their corresponding extension */
+	dep_lst_t *lst; /* modules without their corresponding extension */
 	size_t moddir_base_len; /* length of the "-b basedir" */
 };
 #define G (*(struct globals*)&bb_common_bufsiz1)
@@ -28,22 +40,28 @@ struct globals {
 static int fill_lst(const char *modulename, struct stat ATTRIBUTE_UNUSED *sb,
 					void ATTRIBUTE_UNUSED *data, int ATTRIBUTE_UNUSED depth)
 {
+
 	/* We get a file here. If the file does not have ".ko" but an
 	 * intermittent dentry has, it's just their fault.
 	 */
-	if (strrstr(modulename, ".ko") != NULL)
-		llist_add_to(&G.lst, xstrdup(modulename + G.moddir_base_len));
+	if (strrstr(modulename, ".ko") != NULL) {
+		dep_lst_t *new = xzalloc(sizeof(dep_lst_t));
+		new->name = xstrdup(modulename + G.moddir_base_len);
+		new->next = G.lst;
+		G.lst = new;
+	}
 	return TRUE;
 }
 
 static int fileAction(const char *fname, struct stat *sb,
-					void *data, int ATTRIBUTE_UNUSED depth)
+					void ATTRIBUTE_UNUSED *data, int ATTRIBUTE_UNUSED depth)
 {
 	size_t len = sb->st_size;
 	void *the_module;
 	char *ptr;
 	int fd;
 	char *depends, *deps;
+	dep_lst_t *this;
 
 	if (strrstr(fname, ".ko") == NULL) /* not a module */
 		goto skip;
@@ -61,40 +79,44 @@ static int fileAction(const char *fname, struct stat *sb,
 	close(fd);
 	if (the_module == MAP_FAILED)
 		bb_perror_msg_and_die("mmap");
-
 	ptr = the_module;
-
-	fprintf((FILE*)data, "%s:", fname + G.moddir_base_len);
+	this = G.lst;
+	do {
+		if (!strcmp(fname + G.moddir_base_len, this->name))
+			break;
+		this = this->next;
+	} while (this);
+	dbg_assert (this);
 //bb_info_msg("fname='%s'", fname + G.moddir_base_len);
 	do {
 		/* search for a 'd' */
 		ptr = memchr(ptr, 'd', len - (ptr - (char*)the_module));
 		if (ptr == NULL) /* no d left, done */
 			goto none;
-		if (strncmp(ptr, "depends=", sizeof("depends=")-1) == 0)
+		if (!strncmp(ptr, "depends=", sizeof("depends=")-1))
 			break;
 		++ptr;
 	} while (1);
 	deps = depends = xstrdup (ptr + sizeof("depends=")-1);
 //bb_info_msg(" depends='%s'", depends);
 	while (deps) {
-		llist_t * _lst = G.lst;
+		dep_lst_t *all = G.lst;
 
 		ptr = strsep(&deps, ",");
-		while (_lst) {
+		while (all) {
 			/* Compare the recorded filenames ignoring ".ko*" at the end.  */
-			char *tmp = bb_get_last_path_component_nostrip(_lst->data);
-			if (strncmp(ptr, tmp, strrstr(tmp, ".ko") - tmp) == 0)
+			char *tmp = bb_get_last_path_component_nostrip(all->name);
+			if (!strncmp(ptr, tmp, MAX(strlen(ptr),strrstr(tmp, ".ko") - tmp)))
 				break; /* found it */
-			_lst = _lst->link;
+			all = all->next;
 		}
-		if (_lst) {
-//bb_info_msg("[%s] -> '%s'", (char*)ptr, _lst->data);
-			fprintf((FILE*)data, " %s", _lst->data);
+		if (all) {
+			dbg_assert(all->name); /* this cannot be empty */
+//bb_info_msg("[%s] -> '%s'", (char*)ptr, all->name);
+			llist_add_to_end(&this->dependencies, all->name);
 		}
 	}
 	free(depends);
-	fprintf((FILE*)data, "\n");
  none:
 	munmap(the_module, sb->st_size);
  skip:
@@ -115,11 +137,14 @@ int depmod_main(int ATTRIBUTE_UNUSED argc, char **argv)
 		ARG_F = (1<<4), /* System.map that contains the symbols */
 		ARG_n = (1<<5)  /* dry-run, print to stdout only */
 	};
+	INIT_G();
 
 	getopt32(argv, "aAb:eF:n", &moddir_base, &system_map);
 	argv += optind;
 
-	/* got a version to use? */
+	/* If a version is provided, then that kernel version’s module directory
+	 * is used, rather than the current kernel version (as returned by
+	 * "uname -r").  */
 	if (*argv && (sscanf(*argv, "%d.%d.%d", &ret, &ret, &ret) == 3)) {
 		moddir = concat_path_file(CONFIG_DEFAULT_MODULES_DIR, *argv++);
 	} else {
@@ -160,6 +185,9 @@ int depmod_main(int ATTRIBUTE_UNUSED argc, char **argv)
 		else
 			return EXIT_FAILURE;
 	}
+#if ENABLE_FEATURE_CLEAN_UP
+	else
+#endif
 	do {
 		chp = option_mask32 & ARG_a ? moddir : *argv++;
 
@@ -167,16 +195,74 @@ int depmod_main(int ATTRIBUTE_UNUSED argc, char **argv)
 				ACTION_RECURSE, /* flags */
 				fileAction, /* file action */
 				NULL, /* dir action */
-				(void*)filedes, /* user data */
+				NULL, /* user data */
 				0)) { /* depth */
 			ret = EXIT_FAILURE;
 		}
 	} while (!(option_mask32 & ARG_a) && *argv);
 
+	/* modprobe allegedly wants dependencies without duplicates, i.e.
+	 * mod1: mod2 mod3
+	 * mod2: mod3
+	 * mod3:
+	 * implies that mod1 directly depends on mod2 and _not_ mod3 as mod3 is
+	 * already implicitely pulled in via mod2. This leaves us with:
+	 * mod1: mod2
+	 * mod2: mod3
+	 * mod3:
+	 */
+	{
+	dep_lst_t *mods = G.lst;
+#if ENABLE_FEATURE_DEPMOD_PRUNE_FANCY
+	while (mods) {
+		llist_t *deps = mods->dependencies;
+		while (deps) {
+			dep_lst_t *all = G.lst;
+			while (all) {
+				if (!strcmp(all->name, deps->data)) {
+					llist_t *implied = all->dependencies;
+					while (implied) {
+						/* erm, nicer would be to just
+						 * llist_unlink(&mods->dependencies, implied)  */
+						llist_t *prune = mods->dependencies;
+						while (prune) {
+							if (!strcmp(implied->data, prune->data))
+								break;
+							prune = prune->link;
+						}
+//if (prune) bb_info_msg("[%s] '%s' implies '%s', removing", mods->name, all->name, implied->data);
+						llist_unlink(&mods->dependencies, prune);
+						implied = implied->link;
+					}
+				}
+				all = all->next;
+			}
+			deps = deps->link;
+		}
+		mods = mods->next;
+	}
+
+	mods = G.lst;
+#endif
+	/* Finally print them.  */
+	while (mods) {
+		fprintf(filedes, "%s:", mods->name);
+		while (mods->dependencies)
+			fprintf(filedes, " %s", (char*)llist_pop(&mods->dependencies));
+		fprintf(filedes, "\n");
+		mods = mods->next;
+	}
+	}
+
 	if (ENABLE_FEATURE_CLEAN_UP) {
 		fclose_if_not_stdin(filedes);
-		llist_free(G.lst, free);
 		free(moddir);
+		while (G.lst) {
+			dep_lst_t *old = G.lst;
+			G.lst = G.lst->next;
+			free(old->name);
+			free(old);
+		}
 	}
 	return ret;
 }