[PATCH] Speed up modprobe and MAKEDEV

[Kyle McMartin]

On Wed, Oct 01, 2008 at 06:52:15PM +0200, Jakub Jelinek wrote:
> Given the recent 5sec boot efforts http://lwn.net/Articles/299483/
> and Mandriva follow-ups on that http://lwn.net/Articles/300873/,
> I thought I'd share my modprobe and MAKEDEV speedup patches with
> a wider community so folks can experiment with them, especially seeing
> Mandriva folks playing with turning modprobe into a daemon because of its
> slowness.
> 

Ah, I'm glad to see others working on this! I'd not seen the Mandriva
efforts, but I should really poke at them as I'd turned modprobe into
a library and started integrating it into udev.

> MAKEDEV sources almost 500KB of config files on every invocation, and the
> inner loop is terribly inefficient.  The second patch allows it to shrink
> the files to 55KB while expressing the same info and makes the inner loop
> more efficient.  Depending on how many modprobe and MAKEDEV invocations
> are done on your box during bootup, this can or might not make meassurable
> difference.
> 

Definitely. The biggest win by far for MAKEDEV is profiling the often
hit devices, and prioritizing things. Dave Airlie moved a bunch of the
cciss and other almost never-seen devices to be sourced last and ended
up with a huge win.

> IMHO the binary caches for modprobe are better than
> having thousands of symlinks around (given 7500 wildcards where for many of
> them a few dozens of symlinks would be needed), especially if the symlinks
> would be included in rpm package, but I can be of course convinced
> otherwise.  In any case, the module-init-tools contains a bunch of speedups
> that are IMHO desirable anyway, even without the modules.{dep,alias}cache
> files.
> 

This sounds like a better idea than what I was working on, especially
since I hadn't tackled speeding up the alias issue yet. Big +1 from me
on integrating this. (It also solves a few other issues, like making
things work properly in the cpio initrd...)

Have you tested things on a big endian machine? In any case, this looks
really good. Hopefully Jon will apply this upstream soon so we can get
it in F10.

regards, Kyle

> 	Jakub

> For modules.dep depmod -a also creates modules.depcache which is just  
> a simple hash table with chains and a dumb fast compression of strings,
> so that modules.depcache is roughly 3 times smaller than modules.dep.
> The hash function already makes no difference between _ and -, so for dep
> lookups all it needs is compute the hash, walk the chain, comparing full
> 32-bit hash value and if that hits, compare also modname string, on success
> just return that and its dependencies.
> 
> For modules.alias it creates modules.aliascache, which contains a tree.
> Each tree node has 0 or more associated fnmatch wildcards that need to be
> fnmatched at that level unconditionally, then some fixed number of
> characters and prefixes of up to that length can be binary searched to
> find further node.  The further node can be of 3 types - either again
> a normal range node, or just a pointer to a result (if all chars have been
> already compared), or an entry containing remaining chars to strncmp and
> pointer to result.  Guess better is just to read the algorithm in modprobe.c
> for details.  When reading modules.alias, modprobe always calls fnmatch
> on all patterns in there and fnmatch is quite expensive.  With
> modules.aliascache, for some strings which don't have any wildcards in it,
> fnmatch isn't called at all, otherwise it is called only on wildcards where
> its prefix consisting of non-wildcard chars matches the input.
> 
> Both modules.depcache and modules.aliascache contain a file header, which
> embeds a version number, endianity and mtime/ino/size of the corresponding
> modules.{dep,alias} file - in case it is hand edited later, modprobe won't
> use the cache which will be stale in that case, until regenerated.
> 
> In addition to these changes there are some small cleanups here and there,
> e.g. as modprobe and depmod aren't threaded we can speed things up quite a
> lot by using _unlocked functions, or there is no point for every
> getline_wrapped to malloc new chunk of memory and let the caller free it
> (almost) immediately again.
> 
> vanilla, modules.dep (time to handle ~ 1600 dep searches):
> real    0m6.554s
> user    0m6.424s
> sys     0m0.128s
> 
> patched + modules.depcache
> real    0m0.042s
> user    0m0.008s
> sys     0m0.034s
> 
> vanilla, modules.alias (time to handle ~ 6400 alias searches):
> real    1m22.548s
> user    1m21.554s
> sys     0m0.965s
> 
> patched + modules.aliascache
> real    0m0.552s
> user    0m0.438s
> sys     0m0.114s
> 
> time of modprobe pci:v0000EA60d00009897svAsdBbcCscDiE
> real    0m0.034s
> user    0m0.028s
> sys     0m0.006s
> vs.
> real    0m0.007s
> user    0m0.004s
> sys     0m0.003s
>