kbuild: implement modules.order

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.

Hi Tejun.

Quoted 6 lines · 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.

Quoted 2 lines

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.

Quoted 5 lines

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.

Quoted 8 lines · Tejun Heo

Quoted 5 lines

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.

Quoted 6 lines · Tejun Heo

Quoted 5 lines · Tejun Heo

Quoted 5 lines

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.

Quoted 3 lines

Quoted 2 lines

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.

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.

Quoted 10 lines · Sam Ravnborg

Quoted 9 lines · Tejun Heo

Quoted 7 lines · Tejun Heo

Quoted 5 lines

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.

Quoted 2 lines

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.

Review

Quoted 5 lines

And this change in Makefile.lib seems bogus:

(quoted diff) +3 -0

+# 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.

Quoted 3 lines

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.

Quoted 1 line

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

This I dunno much about.

Quoted 2 lines

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?

Quoted 5 lines

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).

Quoted 9 lines

Review

Quoted 4 lines

And this change in Makefile.lib seems bogus:

(quoted diff) +3 -0

+# 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.

Quoted 4 lines

Quoted 2 lines

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.

Quoted 10 lines

Quoted 10 lines

Review

Quoted 5 lines

And this change in Makefile.lib seems bogus:

(quoted diff) +3 -0

+# 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.

Quoted 3 lines

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?

Quoted 6 lines

Quoted 5 lines

Quoted 3 lines

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?

Quoted 3 lines

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.

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

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!

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.

Quoted 5 lines · 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.

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.

Quoted 5 lines · 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.

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

scripts/remove-dup.c new file +18 -0

@@ -0,0 +1,98 @@
+/*
+ * remove-dup - Drop duplicate lines from unsorted input files
+ *
+ * Dec 2007 Tejun Heo <[email protected]>
+ *
+ * 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 {		\

scripts/remove-dup.c new file +20 -0

+	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);

scripts/remove-dup.c new file +18 -0

+			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;

scripts/remove-dup.c line 28

Quoted 6 lines

scripts/remove-dup.c new file +6 -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. ;)

Quoted 4 lines

scripts/remove-dup.c new file +4 -0

+		hash = c + (hash << 6) + (hash << 16) - hash;
+
+        return hash;
+}

scripts/remove-dup.c line 38

Quoted 6 lines

scripts/remove-dup.c new file +6 -0

+
+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?

scripts/remove-dup.c line 68

Quoted 2 lines

scripts/remove-dup.c new file +2 -0

+		while (fgets(line, sizeof(line), fp)) {
+			int len = strlen(line);

strlen returns 'size_t', which is unsigned.

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

Quoted 3 lines

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?

Quoted 5 lines

Quoted 2 lines

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. ;)

Quoted 5 lines · WANG Cong

Quoted 5 lines

Quoted 2 lines

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?

Quoted 1 line

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 */?

Quoted 6 lines · WANG Cong

Quoted 5 lines

Quoted 2 lines

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?

Quoted 1 line

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 */?

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.
...

Quoted 5 lines · 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.
...

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").

Quoted 7 lines · Adrian Bunk

Quoted 5 lines · 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.
...

Quoted 6 lines

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

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.