Skip to contentSkip to conversation

Fast LKM symbol resolution with SysV ELH hash table

DISCUSSION Carmelo Amoroso 5 participants 13 messages Oct 18, 2009 – Oct 21, 2009 Kbuild

lore
Share & tools
lore
#0 lore raw

Hi,
I'm just sending this message to report about a work I've recently done to speed-up symbol resolution for modules by using a SysV ELF hash table (without relying upon binutils support).
This work has been presented few days ago at the Embedded Linux Conference Europe.

Patches are already publicly available for 2.6.23 kernel @STLinux git
(http://git.stlinux.com/?p=stm/linux-sh4-2.6.23.y.git;a=summary)

For 2.6.30 already ported but not yet available.

Benchmarks have shown an average reduction of 96% in time spent for symbol resolution (that is 25x faster).

All details can be found at
http://tree.celinuxforum.org/CelfPubWiki/ELCEurope2009Presentations?action=AttachFile&do=view&target=C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf

I'm working to update them to mainline and post for review and discussion.
We are also working right now to update this work too to use GNU hash instead of SysV ELF hash

Carmelo

#1 lore raw
Quoted 16 lines · Carmelo Amoroso

Hi,
I'm just sending this message to report about a work I've recently done to speed-up symbol resolution for modules by using a SysV ELF hash table (without relying upon binutils support).
This work has been presented few days ago at the Embedded Linux Conference Europe.

Patches are already publicly available for 2.6.23 kernel @STLinux git
(http://git.stlinux.com/?p=stm/linux-sh4-2.6.23.y.git;a=summary)

For 2.6.30 already ported but not yet available.

Benchmarks have shown an average reduction of 96% in time spent for symbol resolution
(that is 25x faster).

Quoted 6 lines

All details can be found at
http://tree.celinuxforum.org/CelfPubWiki/ELCEurope2009Presentations?action=AttachFile&do=view&target=C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf

I'm working to update them to mainline and post for review and discussion. We are also working right now to update this work too to use GNU hash instead of SysV ELF hash

Hi!

I found this very interesting. I recently posted a prototype to use binary search to optimize symbol lookup[1]. I guess it's unlikely for more than one such optimization to be merged into mainline :).

The nice thing about binary search is that it doesn't require increased memory structures. You just have to sort the existing tables (although it's easier said than done). Anyway, this means I didn't have to worry about making it optional, or being accused of bloat. I also managed to patch into the existing modpost run, instead of adding another intermediate build step.

---
We should certainly expect hash tables to be faster. Strictly speaking our numbers are incomparable, because your test machine is a bit different to my x86 netbook :). I didn't even report the same numbers. That said, I have some saved "perf report" output, and it _looks_ like using bsearch cut down find_symbol()+strcmp() by 96% <grin>.

If look at the total savings hash tables made in your slides, I actually get 98%. I guess either the analysis was conservative or there were more modules which were omitted for brevity.
---

Hypothetically: imagine we both finish our work and testing on the same machine shows hash tables saving 100% and bsearch saving 90%. In absolute terms, hash tables might have an advantage of 0.03s on my system (where bsearch saved 0.3s), and a total advantage of 0.015s for the modules you tested (where hash tables saved ~0.15s).

Would you accept bsearch in this case? Or would you feel that the performance of hash tables outweighed the extra memory requirements?

(This leaves the question of why you need to load 0.015s worth of always-needed in-tree kernel code as modules. For those who haven't read the slides, the reasoning is that built-in code would take _longer_ to load. The boot-loader is often slower at IO, and it doesn't allow other initialization to occur in parallel).

Warm regards
Alan

---
[1] My bsearch prototype has several undisclosed problems which I'm
working on. If you're curious you can find the patches by searching
"from:[email protected] to:Rusty". At the moment the series is blocked on ARM. I want to kill EXPORT_SYMBOL_ALIAS in armksyms.c, because it breaks some simplifying assumptions I was relying on.

The protoype also limits the optimization to built-in symbols to avoid extra modpost overhead. However, this is an orthogonal decision - it should not be hard to change if desired.

#2 lore raw
Quoted 68 lines · Alan Jenkins
Quoted 18 lines · Carmelo Amoroso

Hi,
I'm just sending this message to report about a work I've recently done to speed-up symbol resolution for modules by using a SysV ELF hash table (without relying upon binutils support).
This work has been presented few days ago at the Embedded Linux Conference
Europe.

Patches are already publicly available for 2.6.23 kernel @STLinux git
(http://git.stlinux.com/?p=stm/linux-sh4-2.6.23.y.git;a=summary)

For 2.6.30 already ported but not yet available.

Benchmarks have shown an average reduction of 96% in time spent for symbol
resolution
(that is 25x faster).

Quoted 7 lines

All details can be found at
http://tree.celinuxforum.org/CelfPubWiki/ELCEurope2009Presentations?action=AttachFile&do=view&target=C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf

I'm working to update them to mainline and post for review and discussion.
We are also working right now to update this work too to use GNU hash instead of SysV ELF hash

Hi!

I found this very interesting. I recently posted a prototype to use binary search to optimize symbol lookup[1]. I guess it's unlikely for more than one such optimization to be merged into mainline :).

The nice thing about binary search is that it doesn't require increased memory structures. You just have to sort the existing tables (although it's easier said than done). Anyway, this means I didn't have to worry about making it optional, or being accused of bloat. I also managed to patch into the existing modpost run, instead of adding another intermediate build step.

---
We should certainly expect hash tables to be faster. Strictly speaking our numbers are incomparable, because your test machine is a bit different to my x86 netbook :). I didn't even report the same numbers. That said, I have some saved "perf report" output, and it _looks_ like using bsearch cut down find_symbol()+strcmp() by 96% <grin>.

If look at the total savings hash tables made in your slides, I actually get 98%. I guess either the analysis was conservative or there were more modules which were omitted for brevity.
---

Hypothetically: imagine we both finish our work and testing on the same machine shows hash tables saving 100% and bsearch saving 90%. In absolute terms, hash tables might have an advantage of 0.03s on my system (where bsearch saved 0.3s), and a total advantage of 0.015s for the modules you tested (where hash tables saved ~0.15s).

Would you accept bsearch in this case? Or would you feel that the performance of hash tables outweighed the extra memory requirements?

(This leaves the question of why you need to load 0.015s worth of always-needed in-tree kernel code as modules. For those who haven't read the slides, the reasoning is that built-in code would take _longer_ to load. The boot-loader is often slower at IO, and it doesn't allow other initialization to occur in parallel).

Quoted 6 lines

Warm regards
Alan

---
[1] My bsearch prototype has several undisclosed problems which I'm working on.

So here's a dump of my current state. It fixes the known issues (some ugliness is still marked as TODO). Boot-tested for i386 only; it should also build for ARM.

<http://github.com/sourcejedi/linux-2.6/commits/module-V2-alpha1>

It's definitely supposed to be cross-platform, so if you do try it and fail then I'd be very interested to hear that. Even if all you say is "idiot, it doesn't work, why haven't you tested it in qemu yet" :-).

Quoted 7 lines

At the moment the series
is blocked on ARM. I want to kill EXPORT_SYMBOL_ALIAS in armksyms.c, because it breaks some simplifying assumptions I was relying on.

The protoype also limits the optimization to built-in symbols to avoid extra modpost overhead. However, this is an orthogonal decision - it should not be hard to change if desired.

#3 lore raw
In reply to Alan Jenkins
Quoted 8 lines · Alan Jenkins

Hypothetically: imagine we both finish our work and testing on the same machine shows hash tables saving 100% and bsearch saving 90%. In absolute terms, hash tables might have an advantage of 0.03s on my system (where bsearch saved 0.3s), and a total advantage of 0.015s for the modules you tested (where hash tables saved ~0.15s).

Would you accept bsearch in this case? Or would you feel that the performance of hash tables outweighed the extra memory requirements?

The performance difference in "raw" time speed might be much different on embedded platforms with slower processors, so it might be worth the tiny complexity to get that much noticed speed.

Quoted 5 lines

(This leaves the question of why you need to load 0.015s worth of always-needed in-tree kernel code as modules. For those who haven't read the slides, the reasoning is that built-in code would take _longer_ to load. The boot-loader is often slower at IO, and it doesn't allow other initialization to occur in parallel).

Distros are forced to build almost everything as modules. I've played with building some modules into the kernel directly (see the openSUSE moblin kernels for examples of that), but when you have to suport a much larger range of hardware types and features that some users use and others don't, and the ability to override specific drivers by others due to manufacturer requests for specific updates, the need to keep things as modules is the only way to solve the problem.

So I'm glad to see this speedup happen, very nice work everyone.

thanks,

greg k-h

#4 lore raw
Quoted 20 lines · Greg KH
Quoted 8 lines · Alan Jenkins

Hypothetically: imagine we both finish our work and testing on the same machine shows hash tables saving 100% and bsearch saving 90%. In absolute terms, hash tables might have an advantage of 0.03s on my system (where bsearch saved 0.3s), and a total advantage of 0.015s for the modules you tested (where hash tables saved ~0.15s).

Would you accept bsearch in this case? Or would you feel that the performance of hash tables outweighed the extra memory requirements?

The performance difference in "raw" time speed might be much different on embedded platforms with slower processors, so it might be worth the tiny complexity to get that much noticed speed.

Quoted 5 lines

(This leaves the question of why you need to load 0.015s worth of always-needed in-tree kernel code as modules. For those who haven't read the slides, the reasoning is that built-in code would take _longer_ to load. The boot-loader is often slower at IO, and it doesn't allow other initialization to occur in parallel).

Quoted 7 lines

Distros are forced to build almost everything as modules. I've played with building some modules into the kernel directly (see the openSUSE moblin kernels for examples of that), but when you have to suport a much larger range of hardware types and features that some users use and others don't, and the ability to override specific drivers by others due to manufacturer requests for specific updates, the need to keep things as modules is the only way to solve the problem.

Those are all good reasons. They're just not the reasons for loading usbcore as a module on a 266Mhz processor as shown in the slides. That module accounted for 84ms out of the 145ms total (without the optimisation). So I feel obliged to stipulate this specific reasoning before quoting the numbers on the slide.

Quoted 6 lines

So I'm glad to see this speedup happen, very nice work everyone.

thanks,

greg k-h

I neglected to say that in the first place, but let me second it. It's great to see this work from STLinux being proposed for inclusion in mainline. If all my work does is serve as a baseline for some even better numbers - I can survive that :). My netbook will still boot 0.3s faster :).

Alan

#5 lore raw
In reply to Greg KH

2009/10/18 Greg KH <[email protected]>:

Quoted 7 lines · Alan Jenkins
Quoted 6 lines

Hypothetically: imagine we both finish our work and testing on the same machine shows hash tables saving 100% and bsearch saving 90%.  In absolute terms, hash tables might have an advantage of 0.03s on my system (where bsearch saved 0.3s), and a total advantage of 0.015s for the modules you tested (where hash tables saved ~0.15s).

Quoted 7 lines
Quoted 2 lines

Would you accept bsearch in this case?  Or would you feel that the performance of hash tables outweighed the extra memory requirements?

The performance difference in "raw" time speed might be much different on embedded platforms with slower processors, so it might be worth the tiny complexity to get that much noticed speed.

yes, right. Further the figures I reported on the slides were taken from a development
system with the rootfs mounted via NFS (no HDD or flash), with a debug kernel and so on.

Quoted 14 lines
Quoted 5 lines

(This leaves the question of why you need to load 0.015s worth of always-needed in-tree kernel code as modules.  For those who haven't read the slides, the  reasoning is that built-in code would take _longer_ to load.  The boot-loader is often slower at IO, and it doesn't allow other initialization to occur in parallel).

Distros are forced to build almost everything as modules.  I've played with building some modules into the kernel directly (see the openSUSE moblin kernels for examples of that), but when you have to suport a much larger range of hardware types and features that some users use and others don't, and the ability to override specific drivers by others due to manufacturer requests for specific updates, the need to keep things as modules is the only way to solve the problem.

Quoted 2 lines

So I'm glad to see this speedup happen, very nice work everyone.

Just a few other notes. The current implementation I did based on SysV has a drawback
that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol. Anyway I've just figured out how to change it to remove this limitation. I need some time to review these patches.
Further, the newer implementation based on GNU hash which we are working on right now,
will not require the extra .undef.hash ELF sections because hash values are already embedded
into the GNU hash table, with a reduction in terms of footprint.

Quoted 4 lines

thanks,

greg k-h

Thanks to you too,
Carmelo

#6 lore raw
Quoted 4 lines · Carmelo Amoroso

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Why would this be a problem? Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

Quoted 6 lines

Anyway I've just figured out how to change it to remove this limitation. I need some time to review these patches. Further, the newer implementation based on GNU hash which we are working on right now, will not require the extra .undef.hash ELF sections because hash values are already embedded into the GNU hash table, with a reduction in terms of footprint.

Footprint in the memory for the loaded module, or just in the footprint for the module on the disk?

I'd be interested in seeing your patches when you have something that works for the current Linus kernel tree.

thanks,

greg k-h

#7 lore raw

2009/10/19 Greg KH <[email protected]>:

Quoted 10 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Why would this be a problem?  Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules
(e.g vendors that provide non GPL modules)

Quoted 10 lines
Quoted 6 lines

Anyway I've just figured out how to change it to remove this limitation. I need some time to review these patches.  Further, the newer implementation based on GNU hash which we are working on right now, will not require the extra .undef.hash ELF sections because hash values are already embedded into the GNU hash table, with a reduction in terms of footprint.

Footprint in the memory for the loaded module, or just in the footprint for the module on the disk?

both

Quoted 3 lines

I'd be interested in seeing your patches when you have something that works for the current Linus kernel tree.

sure. I tested weeks ago it on a 2.6.30 tree on x86 at it worked without problems.
I had to hack the x86 linker scripts to remove a check on file size that sounded strange
to me.

carmelo

Quoted 4 lines

thanks,

greg k-h

#8 lore raw
Quoted 7 lines · Carmelo Amoroso

2009/10/19 Greg KH <[email protected]>:

Quoted 6 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Quoted 7 lines
Quoted 4 lines

Why would this be a problem? ?Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules (e.g vendors that provide non GPL modules)

But we do not care at all about that kind of thing, sorry.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Anyway I've just figured out how to change it to remove this limitation. I need some time to review these patches. ?Further, the newer implementation based on GNU hash which we are working on right now, will not require the extra .undef.hash ELF sections because hash values are already embedded into the GNU hash table, with a reduction in terms of footprint.

Quoted 5 lines
Quoted 3 lines

Footprint in the memory for the loaded module, or just in the footprint for the module on the disk?

both

Why would the already-loaded module size increase?

I guess I'll just wait to see the code before worrying about this :)

thanks,

greg k-h

#9 lore raw
Quoted 30 lines · Greg KH
Quoted 7 lines · Carmelo Amoroso

2009/10/19 Greg KH <[email protected]>:

Quoted 6 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Quoted 7 lines
Quoted 4 lines

Why would this be a problem? ?Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules (e.g vendors that provide non GPL modules)

But we do not care at all about that kind of thing, sorry.

Quoted 12 lines
Quoted 11 lines
Quoted 7 lines

Anyway I've just figured out how to change it to remove this limitation.
I need some time to review these patches. ?Further, the newer implementation based on GNU hash which we are working on right now, will not require the extra .undef.hash ELF sections because hash values are already embedded into the GNU hash table, with a reduction in terms of footprint.

Footprint in the memory for the loaded module, or just in the footprint for the module on the disk?

Quoted 5 lines
Quoted 1 line

both

Why would the already-loaded module size increase?

I guess I'll just wait to see the code before worrying about this :)

Modules export symbols, as well as importing them :).

#10 lore raw
In reply to Carmelo Amoroso
Quoted 7 lines · Carmelo Amoroso

2009/10/19 Greg KH <[email protected]>:

Quoted 6 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Quoted 7 lines
Quoted 3 lines

Why would this be a problem? Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules
(e.g vendors that provide non GPL modules)

And breaking them is a feature. I do not go out of my way to avoid breaking out-of-tree modules; it's certainly more important to have simple maintainable code.

You guys figure out what the best speed/size tradeoff is, and send me the patch for review.

Thanks!
Rusty.

#11 lore raw
In reply to Carmelo Amoroso
Quoted 7 lines · Carmelo Amoroso

2009/10/19 Greg KH<[email protected]>:

Quoted 6 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Quoted 8 lines
Quoted 4 lines

Why would this be a problem? Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules
(e.g vendors that provide non GPL modules)

Even non-GPL modules can normally be rebuilt as far as the module format is concerned, there's usually an object file blob that gets compiled into a module on install or something, like the Nvidia graphics driver. If anyone's providing binary-only fully built modules (which would be inherently tied to one exact kernel version and one configuration) they really need to have their head examined..

#12 lore raw
Quoted 17 lines · Robert Hancock
Quoted 7 lines · Carmelo Amoroso

2009/10/19 Greg KH<[email protected]>:

Quoted 6 lines · Carmelo Amoroso
Quoted 4 lines

Just a few other notes. The current implementation I did based on SysV has a drawback that is not backward compatible, so you cannot use old modules with a kernel with the option enabled due to changes on struct kernel_symbol.

Quoted 8 lines
Quoted 4 lines

Why would this be a problem? Whenever making a kernel config change, you should be able to rebuild everything, as lots of other configuration options are that way.

This is not always true... there could be cases in which you cannot recompile old modules
(e.g vendors that provide non GPL modules)

Quoted 6 lines

Even non-GPL modules can normally be rebuilt as far as the module format is concerned, there's usually an object file blob that gets compiled into a module on install or something, like the Nvidia graphics driver. If anyone's providing binary-only fully built modules (which would be inherently tied to one exact kernel version and one configuration) they really need to have their head examined..

Welcome to embedded Linux :)