All of lore.kernel.org
 help / color / mirror / Atom feed
* Re: Fast LKM symbol resolution
@ 2009-11-02 16:52 Alan Jenkins
  2009-11-03  3:55 ` Greg KH
                   ` (12 more replies)
  0 siblings, 13 replies; 57+ messages in thread
From: Alan Jenkins @ 2009-11-02 16:52 UTC (permalink / raw)
  To: linux-kbuild; +Cc: Carmelo Amoroso, Linux Kernel Mailing List, Rusty Russell

Here's my latest code using binary search for symbol resolution.  This
version has benefited from a little more testing (heh), in particular
running on a simulated ARM system.

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

    git clone git://github.com/sourcejedi/linux-2.6.git module-V2-beta1

As before, it saves 0.3s boot time for a modular kernel on my netbook
(630 Mhz Celeron M).  On that system it represents something like 90%
of the maximum possible speedup.  It is claimed that slower systems
would benefit from a further speedup (e.g. using hash tables instead),
but we don't have any numbers to illustrate this yet.


Changes since the original patches were posted:

1) The sorted version of the exports is now generated in
arch-independent assembly language, as .tmp-exports-asm.S.  It uses
similar pseudo-instructions to those in the current .tmp-kallsyms.S.

Previously the sorted exports were generated in C, but the compiler
outputted them in reverse order.  This was made to work by reversing
the comparison used in binary search, but it was a brittle hack.

This means mod_export.h now includes two implementations of
EXPORT_SYMBOL; one for general use in C code, and one for use in
.tmp-exports-asm.S.

2) In vmlinux.lds.h, the unsorted exports are now discarded in the
DISCARDS macro.

Previouslly they were discarded before including the sections of
sorted exports.  This broke the ARM build by discarding some unrelated
symbols too early.  It appears that a) the position of /DISCARD/
directives is signficant; b) all /DISCARD/ directives are merged
together and applied at the point of the first /DISCARD/ directive.

3) Now lightly tested on ARM (using qemu)

To build on ARM it was necessary to remove EXPORT_ALIAS, used in
armksyms.c for the sole purpose of allowing out of tree floating point
emulation code to be loaded as a module.  I have posted this change on
the ARM list and received no comments either way.

4) Build-tested on blackfin (a MODULE_SYMBOL_PREFIX arch)

This required that MODULE_SYMBOL_PREFIX be defined via a Kconfig
option, CONFIG_HAVE_SYMBOL_PREFIX.  Up until now it has been defined
in <asm/module.h> - but this also includes C declarations, which made
it impossible to use in .tmp-exports-asm.S.

Alan

^ permalink raw reply	[flat|nested] 57+ messages in thread
* [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search)
@ 2009-11-07 20:59 Alan Jenkins
  0 siblings, 0 replies; 57+ messages in thread
From: Alan Jenkins @ 2009-11-07 20:59 UTC (permalink / raw)
  To: Rusty Russell; +Cc: linux-kernel, carmelo73, linux-kbuild

As requested by Mike Frysinger, this version of the series

1) generalizes the use of CONFIG_SYMBOL_PREFIX so that arbitrary symbol 
prefixes remain possible
2) uses CONFIG_SYMBOL_PREFIX to implement VMLINUX_SYMBOL() in the 
generic linker script, instead of relying on arch linker scripts to 
define it if needed.


I also changed the position of the patch which implements the above 
changes.  So it is possible to revert or drop the actual optimizations, 
without removing the cleanups and annoying Mike (or Rusty, or Tejun Heo, 
or miscellaneous fans of lib/bsearch.c :).

A clean revert may be useful if hash tables are added in future, to 
avoid the complexity of keeping hash tables + sorted tables + unsorted 
tables.  (This current series leaves module symbol tables unsorted).

^ permalink raw reply	[flat|nested] 57+ messages in thread

end of thread, other threads:[~2009-11-27 11:03 UTC | newest]

Thread overview: 57+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-11-02 16:52 Fast LKM symbol resolution Alan Jenkins
2009-11-03  3:55 ` Greg KH
2009-11-03 10:06 ` [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search) Alan Jenkins
2009-11-03 15:58   ` Greg KH
2009-11-05 12:17     ` Rusty Russell
2009-11-03 10:06 ` [PATCH 01/10] ARM: use unified discard definition in linker script Alan Jenkins
2009-11-03 10:06 ` [PATCH 02/10] ARM: unexport symbols used to implement floating point emulation Alan Jenkins
2009-11-03 10:06 ` [PATCH 03/10] module: extract __EXPORT_SYMBOL from module.h into mod_export.h Alan Jenkins
2009-11-03 10:06 ` [PATCH 04/10] module: make MODULE_SYMBOL_PREFIX into a CONFIG option Alan Jenkins
2009-11-03 10:19   ` Mike Frysinger
2009-11-03 10:19     ` Mike Frysinger
2009-11-03 12:16     ` Alan Jenkins
2009-11-03 12:30       ` Mike Frysinger
2009-11-03 12:30         ` Mike Frysinger
2009-11-03 13:29         ` Paul Mundt
2009-11-03 13:39           ` Mike Frysinger
2009-11-03 13:39             ` Mike Frysinger
2009-11-03 13:46             ` Paul Mundt
2009-11-03 13:58               ` Mike Frysinger
2009-11-03 13:58                 ` Mike Frysinger
2009-11-03 14:07                 ` Paul Mundt
2009-11-03 10:06 ` [PATCH 05/10] kbuild: sort the list of symbols exported by the kernel (__ksymtab) Alan Jenkins
2009-11-04  8:19   ` Rusty Russell
2009-11-04 10:00     ` Alan Jenkins
2009-11-04 11:12       ` Mike Frysinger
2009-11-04 11:12         ` Mike Frysinger
2009-11-04 17:19       ` Sam Ravnborg
2009-11-05 14:24         ` Alan Jenkins
2009-11-05 16:17           ` Mike Frysinger
2009-11-05 16:17             ` Mike Frysinger
2009-11-09  3:17           ` Rusty Russell
2009-11-20 22:20             ` Tony Luck
2009-11-20 22:20               ` Tony Luck
2009-11-21  0:02               ` Alan Jenkins
2009-11-23 19:53                 ` Alex Chiang
2009-11-23 22:44                   ` Alan Jenkins
2009-11-24  0:57                   ` Rusty Russell
2009-11-24  5:39                     ` James Bottomley
2009-11-24  9:28                       ` Alan Jenkins
2009-11-24 22:43                         ` James Bottomley
2009-11-25  9:15                           ` Alan Jenkins
2009-11-25 15:08                             ` James Bottomley
2009-11-25 17:01                               ` Alan Jenkins
2009-11-27 11:03                               ` Rusty Russell
2009-11-26  0:40   ` Andrew Morton
2009-11-26 17:14     ` Alan Jenkins
2009-11-03 10:06 ` [PATCH 06/10] module: refactor symbol tables and try to reduce code size of each_symbol() Alan Jenkins
2009-11-04  8:28   ` Rusty Russell
2009-11-04  9:45     ` Alan Jenkins
2009-11-03 10:06 ` [PATCH 07/10] lib: Add generic binary search function to the kernel Alan Jenkins
2009-11-03 10:06 ` [PATCH 08/10] lib: bsearch - remove redundant special case for arrays of size 0 Alan Jenkins
2009-11-03 10:06 ` [PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables Alan Jenkins
2009-11-04  8:31   ` Rusty Russell
2009-11-03 10:06 ` [PATCH 10/10] module: fix is_exported() to return true for all types of exports Alan Jenkins
2009-11-04  8:32   ` Rusty Russell
2009-11-06  5:37 ` Fast LKM symbol resolution Carmelo Amoroso
2009-11-07 20:59 [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search) Alan Jenkins

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.