[PATCH] kbuild: implement modules.order

[PATCH] kbuild: implement modules.order

[Tejun Heo]

When multiple built-in modules (especially drivers) provide the same
capability, they're prioritized by link order specified by the order
listed in Makefile.  This implicit ordering is lost for loadable
modules.

When driver modules are loaded by udev, what comes first in
modules.alias file is selected.  However, the order in this file is
indeterministic (depends on filesystem listing order of installed
modules).  This causes confusion.

The solution is two-parted.  This patch updates kbuild such that it
generates and installs modules.order which contains the name of
modules ordered according to Makefile.  The second part is update to
depmod such that it generates output files according to this file.

Note that both obj-y and obj-m subdirs can contain modules and
ordering information between those two are lost from beginning.
Currently obj-y subdirs are put before obj-m subdirs.

Signed-off-by: Tejun Heo <htejun@gmail.com>
Cc: Bill Nottingham <notting@redhat.com>
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Greg Kroah-Hartman <gregkh@suse.de>
Cc: Kay Sievers <kay.sievers@vrfy.org>
---
 Makefile               |    5 ++
 scripts/Makefile       |    1 
 scripts/Makefile.build |   16 +++++++-
 scripts/Makefile.lib   |   10 +++++
 scripts/remove-dup.c   |   98 +++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 128 insertions(+), 2 deletions(-)

diff --git a/Makefile b/Makefile
index a65ffd2..1c020c7 100644
--- a/Makefile
+++ b/Makefile
@@ -311,6 +311,7 @@ DEPMOD		= /sbin/depmod
 KALLSYMS	= scripts/kallsyms
 PERL		= perl
 CHECK		= sparse
+REMOVE_DUP	= scripts/remove-dup
 
 CHECKFLAGS     := -D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise $(CF)
 MODFLAGS	= -DMODULE
@@ -1023,6 +1024,7 @@ all: modules
 
 PHONY += modules
 modules: $(vmlinux-dirs) $(if $(KBUILD_BUILTIN),vmlinux)
+	@$(REMOVE_DUP) $(vmlinux-dirs:%=$(objtree)/%/modules.order) > $(objtree)/modules.order
 	@echo '  Building modules, stage 2.';
 	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.modpost
 
@@ -1050,6 +1052,7 @@ _modinst_:
 		rm -f $(MODLIB)/build ; \
 		ln -s $(objtree) $(MODLIB)/build ; \
 	fi
+	@cp -f $(objtree)/modules.order $(MODLIB)/
 	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.modinst
 
 # This depmod is only for convenience to give the initial
@@ -1109,7 +1112,7 @@ clean: archclean $(clean-dirs)
 	@find . $(RCS_FIND_IGNORE) \
 		\( -name '*.[oas]' -o -name '*.ko' -o -name '.*.cmd' \
 		-o -name '.*.d' -o -name '.*.tmp' -o -name '*.mod.c' \
-		-o -name '*.symtypes' \) \
+		-o -name '*.symtypes' -o -name 'modules.order' \) \
 		-type f -print | xargs rm -f
 
 # mrproper - Delete all generated files, including .config
diff --git a/scripts/Makefile b/scripts/Makefile
index 1c73c5a..1c82547 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -12,6 +12,7 @@ hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_PROM_CONSOLE) += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
+hostprogs-$(CONFIG_MODULES)	 += remove-dup
 
 always		:= $(hostprogs-y) $(hostprogs-m)
 
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index de9836e..816a955 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -83,10 +83,12 @@ ifneq ($(strip $(obj-y) $(obj-m) $(obj-n) $(obj-) $(lib-target)),)
 builtin-target := $(obj)/built-in.o
 endif
 
+modorder-target := $(obj)/modules.order
+
 # We keep a list of all modules in $(MODVERDIR)
 
 __build: $(if $(KBUILD_BUILTIN),$(builtin-target) $(lib-target) $(extra-y)) \
-	 $(if $(KBUILD_MODULES),$(obj-m)) \
+	 $(if $(KBUILD_MODULES),$(obj-m) $(modorder-target)) \
 	 $(subdir-ym) $(always)
 	@:
 
@@ -276,6 +278,18 @@ targets += $(builtin-target)
 endif # builtin-target
 
 #
+# Rule to create modules.order file
+#
+$(modorder-target): $(subdir-ym) FORCE
+	@{ for m in $(modorder); do				\
+		if echo $$m | grep -q '.*/modules.order'; then	\
+			cat $$m;				\
+		else						\
+			echo kernel/$$m;			\
+		fi;						\
+	done } > $@
+
+#
 # Rule to compile a set of .o files into one .a file
 #
 ifdef lib-target
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 3c5e88b..4563c96 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -25,6 +25,15 @@ lib-y := $(filter-out $(obj-y), $(sort $(lib-y) $(lib-m)))
 # o if we encounter foo/ in $(obj-m), remove it from $(obj-m) 
 #   and add the directory to the list of dirs to descend into: $(subdir-m)
 
+# make sure '/' follows subdirs
+subdir-y	:= $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
+subdir-m	:= $(patsubst %//,%/, $(addsuffix, /,$subdir-m))
+
+# Determine modorder.  Both -y and -m subdirs can contain modules and
+# unfortunately we don't have information about ordering between -y
+# and -m subdirs.  Just put -y's first.
+modorder	:= $(patsubst %/,%/modules.order, $(subdir-y) $(subdir-m) $(filter %/, $(obj-y)) $(obj-m:.o=.ko))
+
 __subdir-y	:= $(patsubst %/,%,$(filter %/, $(obj-y)))
 subdir-y	+= $(__subdir-y)
 __subdir-m	:= $(patsubst %/,%,$(filter %/, $(obj-m)))
@@ -64,6 +73,7 @@ real-objs-m := $(foreach m, $(obj-m), $(if $(strip $($(m:.o=-objs)) $($(m:.o=-y)
 extra-y		:= $(addprefix $(obj)/,$(extra-y))
 always		:= $(addprefix $(obj)/,$(always))
 targets		:= $(addprefix $(obj)/,$(targets))
+modorder	:= $(addprefix $(obj)/,$(modorder))
 obj-y		:= $(addprefix $(obj)/,$(obj-y))
 obj-m		:= $(addprefix $(obj)/,$(obj-m))
 lib-y		:= $(addprefix $(obj)/,$(lib-y))
diff --git a/scripts/remove-dup.c b/scripts/remove-dup.c
new file mode 100644
index 0000000..3a7a402
--- /dev/null
+++ b/scripts/remove-dup.c
@@ -0,0 +1,98 @@
+/*
+ * remove-dup - Drop duplicate lines from unsorted input files
+ *
+ * Dec 2007 Tejun Heo <teheo@suse.de>
+ *
+ * This software is released under GPLv2.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+struct hash_ent {
+	struct hash_ent *next;
+	char str[];
+};
+
+#define fatal(fmt, args...)	do {		\
+		fprintf(stderr, fmt , ##args);	\
+		exit(1);			\
+	} while (0)
+
+static inline unsigned int sdb_hash(const char *str)
+{
+        unsigned int hash = 0;
+        int c;
+
+        while ((c = *str++))
+		hash = c + (hash << 6) + (hash << 16) - hash;
+
+        return hash;
+}
+
+int main(int argc, char **argv)
+{
+	unsigned int nr_entries = 0;
+	struct hash_ent **hash_tbl;
+	char line[10240];
+	int i;
+
+	/* first pass, count lines */
+	for (i = 1; i < argc; i++) {
+		FILE *fp = fopen(argv[i], "r");
+
+		if (!fp)
+			fatal("failed to open %s for reading\n", argv[i]);
+
+		while (fgets(line, sizeof(line), fp))
+			nr_entries++;
+
+		fclose(fp);
+	}
+
+	nr_entries = nr_entries * 10 / 8;
+	hash_tbl = calloc(nr_entries, sizeof(struct hash_ent *));
+	if (!hash_tbl)
+		fatal("failed to allocate hash table for %u entries\n",
+		      nr_entries);
+
+	/* second pass, hash and print unique lines */
+	for (i = 1; i < argc; i++) {
+		FILE *fp = fopen(argv[i], "r");
+
+		if (!fp)
+			fatal("failed to open %s for reading\n", argv[i]);
+
+		while (fgets(line, sizeof(line), fp)) {
+			int len = strlen(line);
+			struct hash_ent **ppos, *new_ent;
+
+			if (line[len - 1] == '\n')
+				line[--len] = '\0';
+
+			ppos = hash_tbl + (sdb_hash(line) % nr_entries);
+			while (*ppos) {
+				if (strcmp((*ppos)->str, line) == 0)
+					break;
+				ppos = &(*ppos)->next;
+			}
+			if (*ppos)
+				continue;
+
+			new_ent = malloc(sizeof(struct hash_ent) + len + 1);
+			if (!new_ent)
+				fatal("failed to allocate hash entry\n");
+			new_ent->next = NULL;
+			memcpy(new_ent->str, line, len + 1);
+
+			*ppos = new_ent;
+
+			printf("%s\n", line);
+		}
+
+		fclose(fp);
+	}
+
+	return 0;
+}

[PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Kbuild now generates and installs modules.order along with modules.
This patch updates depmod such that it sorts module list according to
the file before generating output files.  Modules which aren't on
modules.order are put after modules which are ordered by
modules.order.

This makes modprobe to prioritize modules according to kernel
Makefile's just as built-in modules are link-ordered by them.

This patch is against module-init-tools 3.3-pre1.

Signed-off-by: Tejun Heo <htejun@gmail.com>
Cc: Bill Nottingham <notting@redhat.com>
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Greg Kroah-Hartman <gregkh@suse.de>
Cc: Kay Sievers <kay.sievers@vrfy.org>
---
 depmod.c |   47 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 47 insertions(+)

diff --git a/depmod.c b/depmod.c
index ea7ad05..e5b9bc3 100644
--- a/depmod.c
+++ b/depmod.c
@@ -585,6 +585,52 @@ static struct module *grab_basedir(const char *dirname)
 	return list;
 }
 
+static void sort_modules(const char *dirname, struct module **listp)
+{
+	struct module *list = *listp, *tlist = NULL, **tpos = &tlist;
+	FILE *modorder;
+	int dir_len = strlen(dirname) + 1;
+	char file_name[dir_len + strlen("modules.order") + 1];
+	char line[dir_len + 10240];
+
+	sprintf(file_name, "%s/%s", dirname, "modules.order");
+
+	modorder = fopen(file_name, "r");
+	if (!modorder) {
+		if (errno == ENOENT)
+			return;
+		fatal("Could not open '%s': %s\n", file_name, strerror(errno));
+	}
+
+	sprintf(line, "%s/", dirname);
+
+	/* move modules listed in modorder file to tlist in order */
+	while (fgets(line + dir_len, sizeof(line) - dir_len, modorder)) {
+		struct module **pos, *mod;
+		int len = strlen(line);
+
+		if (line[len - 1] == '\n')
+			line[len - 1] = '\0';
+
+		for (pos = &list; (mod = *pos); pos = &(*pos)->next) {
+			if (strcmp(line, mod->pathname) == 0) {
+				*pos = mod->next;
+				mod->next = NULL;
+				*tpos = mod;
+				tpos = &mod->next;
+				break;
+			}
+		}
+	}
+
+	/* append the rest */
+	*tpos = list;
+
+	fclose(modorder);
+
+	*listp = tlist;
+}
+
 static void parse_modules(struct module *list)
 {
 	struct module *i;
@@ -857,6 +903,7 @@ int main(int argc, char *argv[])
 	} else {
 		list = grab_basedir(dirname);
 	}
+	sort_modules(dirname, &list);
 	parse_modules(list);
 
 	for (i = 0; i < sizeof(depfiles)/sizeof(depfiles[0]); i++) {

Re: [PATCH] kbuild: implement modules.order

[WANG Cong]

{snip}

Comments on your C code below.

>--- /dev/null
>+++ b/scripts/remove-dup.c
>@@ -0,0 +1,98 @@
>+/*
>+ * remove-dup - Drop duplicate lines from unsorted input files
>+ *
>+ * Dec 2007 Tejun Heo <teheo@suse.de>
>+ *
>+ * This software is released under GPLv2.
>+ */
>+
>+#include <stdio.h>
>+#include <string.h>
>+#include <stdlib.h>
>+
>+struct hash_ent {
>+	struct hash_ent *next;
>+	char str[];
>+};
>+
>+#define fatal(fmt, args...)	do {		\
>+		fprintf(stderr, fmt , ##args);	\
>+		exit(1);			\
>+	} while (0)
>+
>+static inline unsigned int sdb_hash(const char *str)
>+{
>+        unsigned int hash = 0;
>+        int c;
>+
>+        while ((c = *str++))

Maybe ` while ((c = *str++) != '\0') ` is better. ;)


>+		hash = c + (hash << 6) + (hash << 16) - hash;
>+
>+        return hash;
>+}
>+
>+int main(int argc, char **argv)
>+{
>+	unsigned int nr_entries = 0;
>+	struct hash_ent **hash_tbl;
>+	char line[10240];

Needs to #define the magic number?


>+	int i;
>+
>+	/* first pass, count lines */
>+	for (i = 1; i < argc; i++) {
>+		FILE *fp = fopen(argv[i], "r");
>+
>+		if (!fp)
>+			fatal("failed to open %s for reading\n", argv[i]);
>+
>+		while (fgets(line, sizeof(line), fp))
>+			nr_entries++;
>+
>+		fclose(fp);
>+	}
>+
>+	nr_entries = nr_entries * 10 / 8;
>+	hash_tbl = calloc(nr_entries, sizeof(struct hash_ent *));
>+	if (!hash_tbl)
>+		fatal("failed to allocate hash table for %u entries\n",
>+		      nr_entries);
>+
>+	/* second pass, hash and print unique lines */
>+	for (i = 1; i < argc; i++) {
>+		FILE *fp = fopen(argv[i], "r");
>+
>+		if (!fp)
>+			fatal("failed to open %s for reading\n", argv[i]);
>+
>+		while (fgets(line, sizeof(line), fp)) {
>+			int len = strlen(line);

strlen returns 'size_t', which is unsigned.


>+			struct hash_ent **ppos, *new_ent;
>+
>+			if (line[len - 1] == '\n')
>+				line[--len] = '\0';
>+
>+			ppos = hash_tbl + (sdb_hash(line) % nr_entries);
>+			while (*ppos) {
>+				if (strcmp((*ppos)->str, line) == 0)
>+					break;
>+				ppos = &(*ppos)->next;
>+			}
>+			if (*ppos)
>+				continue;
>+
>+			new_ent = malloc(sizeof(struct hash_ent) + len + 1);
>+			if (!new_ent)
>+				fatal("failed to allocate hash entry\n");
>+			new_ent->next = NULL;
>+			memcpy(new_ent->str, line, len + 1);
>+
>+			*ppos = new_ent;
>+
>+			printf("%s\n", line);
>+		}
>+
>+		fclose(fp);
>+	}
>+

I think, you forgot to free(3) the memory you calloc(3)'ed and
malloc(3)'ed above.

>+	return 0;
>+}


Thanks!


 Cong

Re: [PATCH] kbuild: implement modules.order

[Tejun Heo]

WANG Cong wrote:
>> +static inline unsigned int sdb_hash(const char *str)
>> +{
>> +        unsigned int hash = 0;
>> +        int c;
>> +
>> +        while ((c = *str++))
> 
> Maybe ` while ((c = *str++) != '\0') ` is better. ;)

Yeah, probably.  That hash function is copied & pasted mindlessly from web.

>> +		hash = c + (hash << 6) + (hash << 16) - hash;
>> +
>> +        return hash;
>> +}
>> +
>> +int main(int argc, char **argv)
>> +{
>> +	unsigned int nr_entries = 0;
>> +	struct hash_ent **hash_tbl;
>> +	char line[10240];
> 
> Needs to #define the magic number?

Or maybe write a wrapper function around fgets() to detect long lines
reliably.

>> +		while (fgets(line, sizeof(line), fp)) {
>> +			int len = strlen(line);
> 
> strlen returns 'size_t', which is unsigned.

It's capped by the magic number above but yeah size_t would be better.

> I think, you forgot to free(3) the memory you calloc(3)'ed and
> malloc(3)'ed above.

It's a simple program where whole body is in main().  Why bother?
What's the benefit of adding hash-table iterating free logic?

-- 
tejun

Re: [PATCH] kbuild: implement modules.order

[WANG Cong]

>> I think, you forgot to free(3) the memory you calloc(3)'ed and
>> malloc(3)'ed above.
>
>It's a simple program where whole body is in main().  Why bother?
>What's the benefit of adding hash-table iterating free logic?
>

Personally, I think memory leaks are bugs. And we hate bugs. ;)

Regards.

Re: [PATCH] kbuild: implement modules.order

[Tejun Heo]

WANG Cong wrote:
>>> I think, you forgot to free(3) the memory you calloc(3)'ed and
>>> malloc(3)'ed above.
>> It's a simple program where whole body is in main().  Why bother?
>> What's the benefit of adding hash-table iterating free logic?
>>
> 
> Personally, I think memory leaks are bugs. And we hate bugs. ;)

Trust me.  As a person buried alive in bug reports, I hate bugs too.  I
just don't agree that this type of programs should free all its
resources before exiting.  How about adding a comment saying /* we're
going out anyway, don't bother freeing hashtable */?

-- 
tejun

Re: [PATCH] kbuild: implement modules.order

[Li Zefan]

Tejun Heo wrote:
> WANG Cong wrote:
>>>> I think, you forgot to free(3) the memory you calloc(3)'ed and
>>>> malloc(3)'ed above.
>>> It's a simple program where whole body is in main().  Why bother?
>>> What's the benefit of adding hash-table iterating free logic?
>>>
>> Personally, I think memory leaks are bugs. And we hate bugs. ;)
> 
> Trust me.  As a person buried alive in bug reports, I hate bugs too.  I
> just don't agree that this type of programs should free all its
> resources before exiting.  How about adding a comment saying /* we're
> going out anyway, don't bother freeing hashtable */?
> 

I don't consider this as memory leak. I agree that a comment should be
enough. :)

	Li Zefam

Re: [PATCH] depmod: sort output according to modules.order

[Sam Ravnborg]

Hi Tejun.
On Tue, Dec 04, 2007 at 10:55:48PM +0900, Tejun Heo wrote:
> Kbuild now generates and installs modules.order along with modules.
> This patch updates depmod such that it sorts module list according to
> the file before generating output files.  Modules which aren't on
> modules.order are put after modules which are ordered by
> modules.order.
> 
> This makes modprobe to prioritize modules according to kernel
> Makefile's just as built-in modules are link-ordered by them.

With this change depmod require the precense of modules.order.
Could we make it optional so depmod are backward compatible?

It would also simplify the kbuild integration if depmod
could read the modules as a space separated list where
duplicates are allowed.
If we do so then the is no reason to escape to the shell
in Makeilfe.build and we do not have to remove duplicates either.

	Sam

Re: [PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Sam Ravnborg wrote:
> Hi Tejun.
> On Tue, Dec 04, 2007 at 10:55:48PM +0900, Tejun Heo wrote:
>> Kbuild now generates and installs modules.order along with modules.
>> This patch updates depmod such that it sorts module list according to
>> the file before generating output files.  Modules which aren't on
>> modules.order are put after modules which are ordered by
>> modules.order.
>>
>> This makes modprobe to prioritize modules according to kernel
>> Makefile's just as built-in modules are link-ordered by them.
> 
> With this change depmod require the precense of modules.order.
> Could we make it optional so depmod are backward compatible?

It is backward compatible by virtue of

+		if (errno == ENOENT)
+			return;

in sort_modules().  If the file isn't there, the list isn't sorted.

> It would also simplify the kbuild integration if depmod
> could read the modules as a space separated list where
> duplicates are allowed.
> If we do so then the is no reason to escape to the shell
> in Makeilfe.build and we do not have to remove duplicates either.

I'm no Makefile expert so no doubt my modifications are ugly.  But I
think producing a file w/ duplicates in it is just ugly.

-- 
tejun

Re: [PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Tejun Heo wrote:
>> It would also simplify the kbuild integration if depmod
>> could read the modules as a space separated list where
>> duplicates are allowed.
>> If we do so then the is no reason to escape to the shell
>> in Makeilfe.build and we do not have to remove duplicates either.
> 
> I'm no Makefile expert so no doubt my modifications are ugly.  But I
> think producing a file w/ duplicates in it is just ugly.

Oh, and, depmod should do just fine with duplicate entries as it is.

-- 
tejun

Re: [PATCH] depmod: sort output according to modules.order

[Sam Ravnborg]

On Wed, Dec 05, 2007 at 04:34:30PM +0900, Tejun Heo wrote:
> Tejun Heo wrote:
> >> It would also simplify the kbuild integration if depmod
> >> could read the modules as a space separated list where
> >> duplicates are allowed.
> >> If we do so then the is no reason to escape to the shell
> >> in Makeilfe.build and we do not have to remove duplicates either.
> > 
> > I'm no Makefile expert so no doubt my modifications are ugly.  But I
> > think producing a file w/ duplicates in it is just ugly.
> 
> Oh, and, depmod should do just fine with duplicate entries as it is.
What is the purpose of REMOVE-DUP then?
If depmod handle duplicate entries there is no need to remove them.

And this change in Makefile.lib seems bogus:
+# make sure '/' follows subdirs
+subdir-y       := $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
+subdir-m       := $(patsubst %//,%/, $(addsuffix, /,$subdir-m))

I commented it out and with my config everything seems to still
work as expected.
And I get scripts/mod/modpost built in a mrproper tree again (bug!).

subdir-y and subdir-m does not point to directories that
contains modules (built-in or not) so they can be ignored for modorder.


I did a quick hack up top of your patch and came up with the following.
I just checked that if I manually ran remove-dup then the resulting
module.order files were identical with a simple configuration (50 modules).

And I did not try out depmod at all.
Feel free to use this as an updated patch.

	Sam

diff --git a/Makefile b/Makefile
index 92dc3cb..9309e89 100644
--- a/Makefile
+++ b/Makefile
@@ -1023,6 +1023,7 @@ all: modules
 
 PHONY += modules
 modules: $(vmlinux-dirs) $(if $(KBUILD_BUILTIN),vmlinux)
+	$(Q)cat $(vmlinux-dirs:%=$(objtree)/%/modules.order) > $(objtree)/modules.order
 	@echo '  Building modules, stage 2.';
 	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.modpost
 
@@ -1050,6 +1051,7 @@ _modinst_:
 		rm -f $(MODLIB)/build ; \
 		ln -s $(objtree) $(MODLIB)/build ; \
 	fi
+	@cp -f $(objtree)/modules.order $(MODLIB)/
 	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.modinst
 
 # This depmod is only for convenience to give the initial
@@ -1109,7 +1111,7 @@ clean: archclean $(clean-dirs)
 	@find . $(RCS_FIND_IGNORE) \
 		\( -name '*.[oas]' -o -name '*.ko' -o -name '.*.cmd' \
 		-o -name '.*.d' -o -name '.*.tmp' -o -name '*.mod.c' \
-		-o -name '*.symtypes' \) \
+		-o -name '*.symtypes' -o -name 'modules.order' \) \
 		-type f -print | xargs rm -f
 
 # mrproper - Delete all generated files, including .config
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index de9836e..ac68c70 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -83,10 +83,12 @@ ifneq ($(strip $(obj-y) $(obj-m) $(obj-n) $(obj-) $(lib-target)),)
 builtin-target := $(obj)/built-in.o
 endif
 
+modorder-target := $(obj)/modules.order
+
 # We keep a list of all modules in $(MODVERDIR)
 
 __build: $(if $(KBUILD_BUILTIN),$(builtin-target) $(lib-target) $(extra-y)) \
-	 $(if $(KBUILD_MODULES),$(obj-m)) \
+	 $(if $(KBUILD_MODULES),$(obj-m) $(modorder-target)) \
 	 $(subdir-ym) $(always)
 	@:
 
@@ -276,6 +278,18 @@ targets += $(builtin-target)
 endif # builtin-target
 
 #
+# Rule to create modules.order file
+#
+# Create commands to etiher record .ko file
+# or cat modules.order from a subdirectory
+modorder-cmds =                                        \
+	$(foreach m, $(modorder),                      \
+		$(if $(filter %/modules.order, $m),    \
+	 		cat $m;, echo kernel/$m;)) 
+
+$(modorder-target): $(subdir-ym) FORCE
+	$(Q)(cat /dev/null; $(modorder-cmds)) > $@
+#
 # Rule to compile a set of .o files into one .a file
 #
 ifdef lib-target
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 3c5e88b..4dedea1 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -25,6 +25,11 @@ lib-y := $(filter-out $(obj-y), $(sort $(lib-y) $(lib-m)))
 # o if we encounter foo/ in $(obj-m), remove it from $(obj-m) 
 #   and add the directory to the list of dirs to descend into: $(subdir-m)
 
+# Determine modorder. 
+# Unfortunately we don't have information about ordering between -y
+# and -m subdirs.  Just put -y's first.
+modorder	:= $(patsubst %/,%/modules.order, $(filter %/, $(obj-y)) $(obj-m:.o=.ko))
+
 __subdir-y	:= $(patsubst %/,%,$(filter %/, $(obj-y)))
 subdir-y	+= $(__subdir-y)
 __subdir-m	:= $(patsubst %/,%,$(filter %/, $(obj-m)))
@@ -64,6 +69,7 @@ real-objs-m := $(foreach m, $(obj-m), $(if $(strip $($(m:.o=-objs)) $($(m:.o=-y)
 extra-y		:= $(addprefix $(obj)/,$(extra-y))
 always		:= $(addprefix $(obj)/,$(always))
 targets		:= $(addprefix $(obj)/,$(targets))
+modorder	:= $(addprefix $(obj)/,$(modorder))
 obj-y		:= $(addprefix $(obj)/,$(obj-y))
 obj-m		:= $(addprefix $(obj)/,$(obj-m))
 lib-y		:= $(addprefix $(obj)/,$(lib-y))

Re: [PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Sam Ravnborg wrote:
> On Wed, Dec 05, 2007 at 04:34:30PM +0900, Tejun Heo wrote:
>> Tejun Heo wrote:
>>>> It would also simplify the kbuild integration if depmod
>>>> could read the modules as a space separated list where
>>>> duplicates are allowed.
>>>> If we do so then the is no reason to escape to the shell
>>>> in Makeilfe.build and we do not have to remove duplicates either.
>>> I'm no Makefile expert so no doubt my modifications are ugly.  But I
>>> think producing a file w/ duplicates in it is just ugly.
>> Oh, and, depmod should do just fine with duplicate entries as it is.
> What is the purpose of REMOVE-DUP then?
> If depmod handle duplicate entries there is no need to remove them.

As I said, I don't think leaving duplicate lines in a file which will be
installed, distributed and used widely is the RTTD.  There can be other
uses of the file.  For example, the file can be parsed and modified by
distro specific module selector.  Sure, all of them can be made to deal
with dup entries but that's just not the right place to solve the problem.

> And this change in Makefile.lib seems bogus:
> +# make sure '/' follows subdirs
> +subdir-y       := $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
> +subdir-m       := $(patsubst %//,%/, $(addsuffix, /,$subdir-m))

Some subdir-y|m entries have following / while others don't.  subdir-y|m
are lax about because either way it points to subdirectory.  The above
two lines are to normalize them so that there's no surprises when
concatenating file name to it.  I think it's a good idea to have the
above with or without other changes.

> I commented it out and with my config everything seems to still
> work as expected.

Yeah, it depends on config.  If you don't have subdir-y|m entries which
don't have following '/', it will work just fine.  If you do, it will break.

> And I get scripts/mod/modpost built in a mrproper tree again (bug!).

This I dunno much about.

> subdir-y and subdir-m does not point to directories that
> contains modules (built-in or not) so they can be ignored for modorder.

I didn't know that.  Is it forced that modules can't be put in
subdir-y|m directories?  What happens if I do that?

> I did a quick hack up top of your patch and came up with the following.
> I just checked that if I manually ran remove-dup then the resulting
> module.order files were identical with a simple configuration (50 modules).

e.g. Some of USB modules are listed twice in config.  They'll appear twice.

> And I did not try out depmod at all.
> Feel free to use this as an updated patch.

Ah.. that looks much less hacky.  Thanks.  I'll submit an updated
version as soon as above issues are settled.

Thanks.

-- 
tejun

Re: [PATCH] kbuild: implement modules.order

[Rusty Russell]

On Wednesday 05 December 2007 18:11:49 Tejun Heo wrote:
> WANG Cong wrote:
> >>> I think, you forgot to free(3) the memory you calloc(3)'ed and
> >>> malloc(3)'ed above.
> >>
> >> It's a simple program where whole body is in main().  Why bother?
> >> What's the benefit of adding hash-table iterating free logic?
> >
> > Personally, I think memory leaks are bugs. And we hate bugs. ;)
>
> Trust me.  As a person buried alive in bug reports, I hate bugs too.  I
> just don't agree that this type of programs should free all its
> resources before exiting.  How about adding a comment saying /* we're
> going out anyway, don't bother freeing hashtable */?

I too once battled with the moral dilemma of freeing in programs that exit.

Then in 2001, I was moving out of a house which was to be demolished.  The 
landlord insisted that we pay for the carpets to be cleaned.  My wife still 
uses it as a canonical example of wasteful idiocy.

So I hope this has contributed to your enlightenment, as it did to mine.
Rusty.

Re: [PATCH] depmod: sort output according to modules.order

[Sam Ravnborg]

On Thu, Dec 06, 2007 at 08:28:03AM +0900, Tejun Heo wrote:
> Sam Ravnborg wrote:
> > On Wed, Dec 05, 2007 at 04:34:30PM +0900, Tejun Heo wrote:
> >> Tejun Heo wrote:
> >>>> It would also simplify the kbuild integration if depmod
> >>>> could read the modules as a space separated list where
> >>>> duplicates are allowed.
> >>>> If we do so then the is no reason to escape to the shell
> >>>> in Makeilfe.build and we do not have to remove duplicates either.
> >>> I'm no Makefile expert so no doubt my modifications are ugly.  But I
> >>> think producing a file w/ duplicates in it is just ugly.
> >> Oh, and, depmod should do just fine with duplicate entries as it is.
> > What is the purpose of REMOVE-DUP then?
> > If depmod handle duplicate entries there is no need to remove them.
> 
> As I said, I don't think leaving duplicate lines in a file which will be
> installed, distributed and used widely is the RTTD.  There can be other
> uses of the file.  For example, the file can be parsed and modified by
> distro specific module selector.  Sure, all of them can be made to deal
> with dup entries but that's just not the right place to solve the problem.

googled a bit.
It looks like:
awk '!x[$0]++'
does the trick.

So we can skip the C file (good thing).
> 
> > And this change in Makefile.lib seems bogus:
> > +# make sure '/' follows subdirs
> > +subdir-y       := $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
> > +subdir-m       := $(patsubst %//,%/, $(addsuffix, /,$subdir-m))
> 
> Some subdir-y|m entries have following / while others don't.  subdir-y|m
> are lax about because either way it points to subdirectory.  The above
> two lines are to normalize them so that there's no surprises when
> concatenating file name to it.  I think it's a good idea to have the
> above with or without other changes.
With this change building modpost no longer worked so kbuild
does not like the preceeding slashes. It could be fixed but thats
another patch.
> 
> > I commented it out and with my config everything seems to still
> > work as expected.
> 
> Yeah, it depends on config.  If you don't have subdir-y|m entries which
> don't have following '/', it will work just fine.  If you do, it will break.
> 
> > And I get scripts/mod/modpost built in a mrproper tree again (bug!).
> 
> This I dunno much about.
> 
> > subdir-y and subdir-m does not point to directories that
> > contains modules (built-in or not) so they can be ignored for modorder.
> 
> I didn't know that.  Is it forced that modules can't be put in
> subdir-y|m directories?  What happens if I do that?

I guess modules can be built as modules - but they can never be built-in.
And if someone uses subdir-y to point to a dir with modules
I would anyway cosider that a bug.

	Sam

Re: [PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Sam Ravnborg wrote:
>> As I said, I don't think leaving duplicate lines in a file which will be
>> installed, distributed and used widely is the RTTD.  There can be other
>> uses of the file.  For example, the file can be parsed and modified by
>> distro specific module selector.  Sure, all of them can be made to deal
>> with dup entries but that's just not the right place to solve the problem.
> 
> googled a bit.
> It looks like:
> awk '!x[$0]++'
> does the trick.

Great, that's much better.  I'll give it a try.

> So we can skip the C file (good thing).

Fully agreed.

>>> And this change in Makefile.lib seems bogus:
>>> +# make sure '/' follows subdirs
>>> +subdir-y       := $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
>>> +subdir-m       := $(patsubst %//,%/, $(addsuffix, /,$subdir-m))
>> Some subdir-y|m entries have following / while others don't.  subdir-y|m
>> are lax about because either way it points to subdirectory.  The above
>> two lines are to normalize them so that there's no surprises when
>> concatenating file name to it.  I think it's a good idea to have the
>> above with or without other changes.
> With this change building modpost no longer worked so kbuild
> does not like the preceeding slashes. It could be fixed but thats
> another patch.

I don't really follow what you mean here.  Do you mean with the tailing
slash normalized, modpost doesn't work anymore?  Or with the
normalization removed?

>>> subdir-y and subdir-m does not point to directories that
>>> contains modules (built-in or not) so they can be ignored for modorder.
>> I didn't know that.  Is it forced that modules can't be put in
>> subdir-y|m directories?  What happens if I do that?
> 
> I guess modules can be built as modules - but they can never be built-in.
> And if someone uses subdir-y to point to a dir with modules
> I would anyway cosider that a bug.

s/module/component which can be a dynamically loadable module or
built-in to the kernel/ in my original sentence.  I just couldn't find a
good word to use.  So, you're saying subdir-ym's can be dropped from
modorder, right?  It would be great if we can implement a safeguard to
check that subdif-ym's don't actually contain modules.

Thanks.

-- 
tejun

Re: [PATCH] depmod: sort output according to modules.order

[Sam Ravnborg]

> 
> >>> And this change in Makefile.lib seems bogus:
> >>> +# make sure '/' follows subdirs
> >>> +subdir-y       := $(patsubst %//,%/, $(addsuffix, /,$subdir-y))
> >>> +subdir-m       := $(patsubst %//,%/, $(addsuffix, /,$subdir-m))
> >> Some subdir-y|m entries have following / while others don't.  subdir-y|m
> >> are lax about because either way it points to subdirectory.  The above
> >> two lines are to normalize them so that there's no surprises when
> >> concatenating file name to it.  I think it's a good idea to have the
> >> above with or without other changes.
> > With this change building modpost no longer worked so kbuild
> > does not like the preceeding slashes. It could be fixed but thats
> > another patch.
> 
> I don't really follow what you mean here.  Do you mean with the tailing
> slash normalized, modpost doesn't work anymore?  Or with the
> normalization removed?
I a mrproper tree I did:
make defconfig
make

And it failed because modpost were never built - because the directory
scripts/mod/ was never visited.

> 
> >>> subdir-y and subdir-m does not point to directories that
> >>> contains modules (built-in or not) so they can be ignored for modorder.
> >> I didn't know that.  Is it forced that modules can't be put in
> >> subdir-y|m directories?  What happens if I do that?
> > 
> > I guess modules can be built as modules - but they can never be built-in.
> > And if someone uses subdir-y to point to a dir with modules
> > I would anyway cosider that a bug.
> 
> s/module/component which can be a dynamically loadable module or
> built-in to the kernel/ in my original sentence.  I just couldn't find a
> good word to use.  So, you're saying subdir-ym's can be dropped from
> modorder, right?
Correct - my patch did so.

> It would be great if we can implement a safeguard to
> check that subdif-ym's don't actually contain modules.
Could be a good idea - will think about it.

	Sam

Re: [PATCH] kbuild: implement modules.order

[Adrian Bunk]

On Tue, Dec 04, 2007 at 10:49:37PM +0900, Tejun Heo wrote:
> When multiple built-in modules (especially drivers) provide the same
> capability, they're prioritized by link order specified by the order
> listed in Makefile.  This implicit ordering is lost for loadable
> modules.
>...

What exactly are the drivers you are thinking of?

I would rather see us getting away from any link order dependencies.

E.g. we might one day want to compile the whole kernel with one gcc call 
(using "--combine -fwhole-program").

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] kbuild: implement modules.order

[Tejun Heo]

Adrian Bunk wrote:
> On Tue, Dec 04, 2007 at 10:49:37PM +0900, Tejun Heo wrote:
>> When multiple built-in modules (especially drivers) provide the same
>> capability, they're prioritized by link order specified by the order
>> listed in Makefile.  This implicit ordering is lost for loadable
>> modules.
>> ...
> 
> What exactly are the drivers you are thinking of?
> 
> I would rather see us getting away from any link order dependencies.
> 
> E.g. we might one day want to compile the whole kernel with one gcc call 
> (using "--combine -fwhole-program").

The following bugzilla triggered this change and I think contains enough
discussion on the subject.

  http://bugzilla.kernel.org/show_bug.cgi?id=8933

Thanks.

-- 
tejun

Re: [PATCH] depmod: sort output according to modules.order

[Jon Masters]

On Tue, 2007-12-04 at 22:55 +0900, Tejun Heo wrote:

> Kbuild now generates and installs modules.order along with modules.
> This patch updates depmod such that it sorts module list according to
> the file before generating output files.  Modules which aren't on
> modules.order are put after modules which are ordered by
> modules.order.

Thanks. Please CC me in general on these patches :-)

I was planning to also discuss ordering of module aliases entries, since
we can have several modules providing the same modalias (this gets even
worse on "Enterprise Linux" distributions, where we might have third
party modules providing additional aliases). I guess this ordering is
probably better than just a numeric sort, which was the original idea.

Jon.

Re: [PATCH] depmod: sort output according to modules.order

[Jon Masters]

On Thu, 2007-12-06 at 08:28 +0900, Tejun Heo wrote:

> As I said, I don't think leaving duplicate lines in a file which will be
> installed, distributed and used widely is the RTTD.

For what it's worth, I changed the module processing in depmod so that
it doesn't output duplicate entries. Having duplicates is not the right
solution - especially modalias entries that depend entirely upon the
file layout on disk when you run depmod against a kernel.

Thanks for the ordering patches folks - a good idea!

Jon.

Re: [PATCH] depmod: sort output according to modules.order

[Jon Masters]

On Sat, 2007-12-08 at 03:03 -0500, Jon Masters wrote:
> On Tue, 2007-12-04 at 22:55 +0900, Tejun Heo wrote:
> 
> > Kbuild now generates and installs modules.order along with modules.
> > This patch updates depmod such that it sorts module list according to
> > the file before generating output files.  Modules which aren't on
> > modules.order are put after modules which are ordered by
> > modules.order.
> 
> Thanks. Please CC me in general on these patches :-)
> 
> I was planning to also discuss ordering of module aliases entries, since
> we can have several modules providing the same modalias (this gets even
> worse on "Enterprise Linux" distributions, where we might have third
> party modules providing additional aliases). I guess this ordering is
> probably better than just a numeric sort, which was the original idea.

Actually, this still won't quite solve that problem, because modules not
installed in the kernel itself won't have ordering data supplied. Maybe
I need to do this, *and* then sort modaliases numerically aswell.

Jon.

Re: [PATCH] depmod: sort output according to modules.order

[Alan Cox]

> it doesn't output duplicate entries. Having duplicates is not the right
> solution - especially modalias entries that depend entirely upon the
> file layout on disk when you run depmod against a kernel.
> 
> Thanks for the ordering patches folks - a good idea!

And as it happens just what I need for the upcoming pata_legacy module
changes

Re: [PATCH] kbuild: implement modules.order

[Adrian Bunk]

On Sat, Dec 08, 2007 at 08:59:31AM +0900, Tejun Heo wrote:
> Adrian Bunk wrote:
> > On Tue, Dec 04, 2007 at 10:49:37PM +0900, Tejun Heo wrote:
> >> When multiple built-in modules (especially drivers) provide the same
> >> capability, they're prioritized by link order specified by the order
> >> listed in Makefile.  This implicit ordering is lost for loadable
> >> modules.
> >> ...
> > 
> > What exactly are the drivers you are thinking of?
> > 
> > I would rather see us getting away from any link order dependencies.
> > 
> > E.g. we might one day want to compile the whole kernel with one gcc call 
> > (using "--combine -fwhole-program").
> 
> The following bugzilla triggered this change and I think contains enough
> discussion on the subject.
> 
>   http://bugzilla.kernel.org/show_bug.cgi?id=8933
> 
> Thanks.

Thanks, that explains much.

And thinking about it, it doesn't seem to add any problems regarding 
what I have in mind:

If we would ever stop having any well-defined link-order for in-kernel 
code and express everything through initcall levels, we simply must 
additionally update the modules.order file.

> tejun

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] kbuild: implement modules.order

[Tejun Heo]

Adrian Bunk wrote:
> And thinking about it, it doesn't seem to add any problems regarding 
> what I have in mind:
> 
> If we would ever stop having any well-defined link-order for in-kernel 
> code and express everything through initcall levels, we simply must 
> additionally update the modules.order file.

Expressing order in Makefile is a convenient way to express simple
ordering.  I think it's nice to keep it that way even if it doesn't
necessarily mean link order.  So, maybe we can do the reverse and make
built in modules follow module order regardless of actual link order
(say sort init table according to module order before final link).

Thanks.

-- 
tejun

Re: [PATCH] depmod: sort output according to modules.order

[Tejun Heo]

Jon Masters wrote:
> On Tue, 2007-12-04 at 22:55 +0900, Tejun Heo wrote:
> 
>> Kbuild now generates and installs modules.order along with modules.
>> This patch updates depmod such that it sorts module list according to
>> the file before generating output files.  Modules which aren't on
>> modules.order are put after modules which are ordered by
>> modules.order.
> 
> Thanks. Please CC me in general on these patches :-)

Sure.  FYI, updated patchset is posted.

  http://thread.gmane.org/gmane.linux.kernel/611212

-- 
tejun