* [PATCH 0/2] Speed up the symbols' resolution process @ 2011-03-23 21:00 Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 1/2] Let Linker sort the symbols Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 2/2] Replace the linear search with a binary search for locate " Alessio Igor Bogani 0 siblings, 2 replies; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-23 21:00 UTC (permalink / raw) To: Rusty Russell; +Cc: LKML, Ian Lance Taylor, Tim Bird, Alessio Igor Bogani The intent of this patchset is to speed up the symbols' resolution process. This objective is achieved by sorting all symbols (those which reside both in the kernel and in the modules) and thus convert the slow linear search to the fast binary search. To avoid adding lots of code for symbols sorting I rely on the linker which can easily do the job thanks to a little trick. The trick isn't really beautiful to see but permits minimal changes to the code and build process. Indeed, the patchset is constituted by only two very short patches. In the first patch I changed the code for place every symbol in a different section (for example: "___ksymtab" sec "__" #sym) at compile time (this the above mentioned trick!). In the same patch I also request to the linker to sort and merge all these sections into the appropriate ones (for example: "__ksymtab") at link time using the linker scripts. Once all symbols are sorted we can use binary search instead of the linear one (this is done in the second patch). I'm fairly sure that this is a good speed improvement even though I haven't made any benchmarking (I would be very happy to receive suggestions about how made it). Collaterally, the boot time should be reduced also (proportionally to the number of modules involved at boot stage). I hope that you find that interesting! This work was supported by a hardware donation from the CE Linux Forum. Alessio Igor Bogani (2): Let Linker sort the symbols Replace the linear search with a binary search for locate the symbols include/asm-generic/vmlinux.lds.h | 20 +++++++------- include/linux/module.h | 4 +- kernel/module.c | 49 ++++++++++++++++++++++-------------- scripts/module-common.lds | 19 ++++++++++++++ 4 files changed, 61 insertions(+), 31 deletions(-) -- 1.7.4.1 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 1/2] Let Linker sort the symbols 2011-03-23 21:00 [PATCH 0/2] Speed up the symbols' resolution process Alessio Igor Bogani @ 2011-03-23 21:00 ` Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 2/2] Replace the linear search with a binary search for locate " Alessio Igor Bogani 1 sibling, 0 replies; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-23 21:00 UTC (permalink / raw) To: Rusty Russell; +Cc: LKML, Ian Lance Taylor, Tim Bird, Alessio Igor Bogani This work was supported by a hardware donation from the CE Linux Forum. Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> --- include/asm-generic/vmlinux.lds.h | 20 ++++++++++---------- include/linux/module.h | 4 ++-- scripts/module-common.lds | 19 +++++++++++++++++++ 3 files changed, 31 insertions(+), 12 deletions(-) diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h index 32c45e5..83f6bc1 100644 --- a/include/asm-generic/vmlinux.lds.h +++ b/include/asm-generic/vmlinux.lds.h @@ -274,70 +274,70 @@ /* Kernel symbol table: Normal symbols */ \ __ksymtab : AT(ADDR(__ksymtab) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___ksymtab) = .; \ - *(__ksymtab) \ + *(SORT(___ksymtab__*)) \ VMLINUX_SYMBOL(__stop___ksymtab) = .; \ } \ \ /* Kernel symbol table: GPL-only symbols */ \ __ksymtab_gpl : AT(ADDR(__ksymtab_gpl) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___ksymtab_gpl) = .; \ - *(__ksymtab_gpl) \ + *(SORT(___ksymtab_gpl__*)) \ VMLINUX_SYMBOL(__stop___ksymtab_gpl) = .; \ } \ \ /* Kernel symbol table: Normal unused symbols */ \ __ksymtab_unused : AT(ADDR(__ksymtab_unused) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___ksymtab_unused) = .; \ - *(__ksymtab_unused) \ + *(SORT(___ksymtab_unused__*)) \ VMLINUX_SYMBOL(__stop___ksymtab_unused) = .; \ } \ \ /* Kernel symbol table: GPL-only unused symbols */ \ __ksymtab_unused_gpl : AT(ADDR(__ksymtab_unused_gpl) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___ksymtab_unused_gpl) = .; \ - *(__ksymtab_unused_gpl) \ + *(SORT(___ksymtab_unused_gpl__*)) \ VMLINUX_SYMBOL(__stop___ksymtab_unused_gpl) = .; \ } \ \ /* Kernel symbol table: GPL-future-only symbols */ \ __ksymtab_gpl_future : AT(ADDR(__ksymtab_gpl_future) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___ksymtab_gpl_future) = .; \ - *(__ksymtab_gpl_future) \ + *(SORT(___ksymtab_gpl_future__*)) \ VMLINUX_SYMBOL(__stop___ksymtab_gpl_future) = .; \ } \ \ /* Kernel symbol table: Normal symbols */ \ __kcrctab : AT(ADDR(__kcrctab) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___kcrctab) = .; \ - *(__kcrctab) \ + *(SORT(___kcrctab__*)) \ VMLINUX_SYMBOL(__stop___kcrctab) = .; \ } \ \ /* Kernel symbol table: GPL-only symbols */ \ __kcrctab_gpl : AT(ADDR(__kcrctab_gpl) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___kcrctab_gpl) = .; \ - *(__kcrctab_gpl) \ + *(SORT(___kcrctab_gpl__*)) \ VMLINUX_SYMBOL(__stop___kcrctab_gpl) = .; \ } \ \ /* Kernel symbol table: Normal unused symbols */ \ __kcrctab_unused : AT(ADDR(__kcrctab_unused) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___kcrctab_unused) = .; \ - *(__kcrctab_unused) \ + *(SORT(___kcrctab_unused__*)) \ VMLINUX_SYMBOL(__stop___kcrctab_unused) = .; \ } \ \ /* Kernel symbol table: GPL-only unused symbols */ \ __kcrctab_unused_gpl : AT(ADDR(__kcrctab_unused_gpl) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___kcrctab_unused_gpl) = .; \ - *(__kcrctab_unused_gpl) \ + *(SORT(___kcrctab_unused_gpl__*)) \ VMLINUX_SYMBOL(__stop___kcrctab_unused_gpl) = .; \ } \ \ /* Kernel symbol table: GPL-future-only symbols */ \ __kcrctab_gpl_future : AT(ADDR(__kcrctab_gpl_future) - LOAD_OFFSET) { \ VMLINUX_SYMBOL(__start___kcrctab_gpl_future) = .; \ - *(__kcrctab_gpl_future) \ + *(SORT(___kcrctab_gpl_future__*)) \ VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .; \ } \ \ diff --git a/include/linux/module.h b/include/linux/module.h index 5de4204..a8116e1 100644 --- a/include/linux/module.h +++ b/include/linux/module.h @@ -223,7 +223,7 @@ struct module_use { extern void *__crc_##sym __attribute__((weak)); \ static const unsigned long __kcrctab_##sym \ __used \ - __attribute__((section("__kcrctab" sec), unused)) \ + __attribute__((section("___kcrctab" sec "__" #sym), unused)) \ = (unsigned long) &__crc_##sym; #else #define __CRC_SYMBOL(sym, sec) @@ -238,7 +238,7 @@ struct module_use { = MODULE_SYMBOL_PREFIX #sym; \ static const struct kernel_symbol __ksymtab_##sym \ __used \ - __attribute__((section("__ksymtab" sec), unused)) \ + __attribute__((section("___ksymtab" sec "__" #sym), unused)) \ = { (unsigned long)&sym, __kstrtab_##sym } #define EXPORT_SYMBOL(sym) \ diff --git a/scripts/module-common.lds b/scripts/module-common.lds index 47a1f9a..0057a21 100644 --- a/scripts/module-common.lds +++ b/scripts/module-common.lds @@ -5,4 +5,23 @@ */ SECTIONS { /DISCARD/ : { *(.discard) } + + .rodata : { *(.rodata) } + .rodata.str1.1 : { *(.rodata.str1.1) } + .parainstructions : { *(.parainstructions) } + .modinfo : { *(.modinfo) } + + __ksymtab : { *(SORT(___ksymtab__*)) } + __ksymtab_gpl : { *(SORT(___ksymtab_gpl__*)) } + __ksymtab_unused : { *(SORT(___ksymtab_unused__*)) } + __ksymtab_unused_gpl : { *(SORT(___ksymtab_unused_gpl__*)) } + __ksymtab_gpl_future : { *(SORT(___ksymtab_gpl_future__*)) } + __kcrctab : { *(SORT(___kcrctab__*)) } + __kcrctab_gpl : { *(SORT(___kcrctab_gpl__*)) } + __kcrctab_unused : { *(SORT(___kcrctab_unused__*)) } + __kcrctab_unused_gpl : { *(SORT(___kcrctab_unused_gpl__*)) } + __kcrctab_gpl_future : { *(SORT(___kcrctab_gpl_future__*)) } + + __ksymtab_strings : { *(__ksymtab_strings) } + __versions : { *(__versions) } } -- 1.7.4.1 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-23 21:00 [PATCH 0/2] Speed up the symbols' resolution process Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 1/2] Let Linker sort the symbols Alessio Igor Bogani @ 2011-03-23 21:00 ` Alessio Igor Bogani 2011-03-24 15:54 ` Andi Kleen 1 sibling, 1 reply; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-23 21:00 UTC (permalink / raw) To: Rusty Russell; +Cc: LKML, Ian Lance Taylor, Tim Bird, Alessio Igor Bogani This work was supported by a hardware donation from the CE Linux Forum. Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> --- kernel/module.c | 49 ++++++++++++++++++++++++++++++------------------- 1 files changed, 30 insertions(+), 19 deletions(-) diff --git a/kernel/module.c b/kernel/module.c index 1f9f7bc..932726d 100644 --- a/kernel/module.c +++ b/kernel/module.c @@ -235,6 +235,18 @@ extern const unsigned long __start___kcrctab_unused_gpl[]; #define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL) #endif +struct find_symbol_arg { + /* Input */ + const char *name; + bool gplok; + bool warn; + + /* Output */ + struct module *owner; + const unsigned long *crc; + const struct kernel_symbol *sym; +}; + static bool each_symbol_in_section(const struct symsearch *arr, unsigned int arrsize, struct module *owner, @@ -243,12 +255,26 @@ static bool each_symbol_in_section(const struct symsearch *arr, unsigned int symnum, void *data), void *data) { - unsigned int i, j; + unsigned int j, i; + struct find_symbol_arg *fsa = data; + size_t num; + int start, end, mid, result; for (j = 0; j < arrsize; j++) { - for (i = 0; i < arr[j].stop - arr[j].start; i++) - if (fn(&arr[j], owner, i, data)) - return true; + num = arr[j].stop - arr[j].start; + start = 0, end = num - 1, mid, result, i = 0; + while (start <= end) { + i++; + mid = (start + end) / 2; + result = strcmp(fsa->name, arr[j].start[mid].name); + if (result < 0) + end = mid - 1; + else if (result > 0) + start = mid + 1; + else + if (fn(&arr[j], owner, mid, data)) + return true; + } } return false; @@ -311,27 +337,12 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner, } EXPORT_SYMBOL_GPL(each_symbol); -struct find_symbol_arg { - /* Input */ - const char *name; - bool gplok; - bool warn; - - /* Output */ - struct module *owner; - const unsigned long *crc; - const struct kernel_symbol *sym; -}; - static bool find_symbol_in_section(const struct symsearch *syms, struct module *owner, unsigned int symnum, void *data) { struct find_symbol_arg *fsa = data; - if (strcmp(syms->start[symnum].name, fsa->name) != 0) - return false; - if (!fsa->gplok) { if (syms->licence == GPL_ONLY) return false; -- 1.7.4.1 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-23 21:00 ` [PATCH 2/2] Replace the linear search with a binary search for locate " Alessio Igor Bogani @ 2011-03-24 15:54 ` Andi Kleen 2011-03-25 5:14 ` Rusty Russell 0 siblings, 1 reply; 12+ messages in thread From: Andi Kleen @ 2011-03-24 15:54 UTC (permalink / raw) To: Alessio Igor Bogani; +Cc: Rusty Russell, LKML, Ian Lance Taylor, Tim Bird Alessio Igor Bogani <abogani@kernel.org> writes: > This work was supported by a hardware donation from the CE Linux Forum. Patch looks good to me. SORT is a nice trick, too bad it won't work for the main kernel. -Andi -- ak@linux.intel.com -- Speaking for myself only ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-24 15:54 ` Andi Kleen @ 2011-03-25 5:14 ` Rusty Russell 2011-03-25 15:41 ` Andi Kleen 0 siblings, 1 reply; 12+ messages in thread From: Rusty Russell @ 2011-03-25 5:14 UTC (permalink / raw) To: Andi Kleen, Alessio Igor Bogani; +Cc: LKML, Ian Lance Taylor, Tim Bird On Thu, 24 Mar 2011 08:54:57 -0700, Andi Kleen <andi@firstfloor.org> wrote: > Alessio Igor Bogani <abogani@kernel.org> writes: > > > This work was supported by a hardware donation from the CE Linux Forum. > > Patch looks good to me. SORT is a nice trick, too bad it won't > work for the main kernel. Why not? If it's just that some linkers don't support SORT, can we work around it and call sort() of the symbols in our kernel init? Thanks, Rusty. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-25 5:14 ` Rusty Russell @ 2011-03-25 15:41 ` Andi Kleen 2011-03-25 16:30 ` Alessio Igor Bogani 0 siblings, 1 reply; 12+ messages in thread From: Andi Kleen @ 2011-03-25 15:41 UTC (permalink / raw) To: Rusty Russell Cc: Andi Kleen, Alessio Igor Bogani, LKML, Ian Lance Taylor, Tim Bird On Fri, Mar 25, 2011 at 03:44:24PM +1030, Rusty Russell wrote: > On Thu, 24 Mar 2011 08:54:57 -0700, Andi Kleen <andi@firstfloor.org> wrote: > > Alessio Igor Bogani <abogani@kernel.org> writes: > > > > > This work was supported by a hardware donation from the CE Linux Forum. > > > > Patch looks good to me. SORT is a nice trick, too bad it won't > > work for the main kernel. > > Why not? Because kallsyms is supposed to be in address order, not name order. -Andi -- ak@linux.intel.com -- Speaking for myself only. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-25 15:41 ` Andi Kleen @ 2011-03-25 16:30 ` Alessio Igor Bogani 2011-03-25 19:49 ` Andi Kleen 0 siblings, 1 reply; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-25 16:30 UTC (permalink / raw) To: Andi Kleen; +Cc: Rusty Russell, LKML, Ian Lance Taylor, Tim Bird Dear Mr. Kleen, 2011/3/25 Andi Kleen <andi@firstfloor.org>: [...] >> > Patch looks good to me. SORT is a nice trick, too bad it won't >> > work for the main kernel. >> >> Why not? > > Because kallsyms is supposed to be in address order, not name order. What should that break exactly? Thanks you very much! Ciao, Alessio ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-25 16:30 ` Alessio Igor Bogani @ 2011-03-25 19:49 ` Andi Kleen 2011-03-25 21:31 ` Alessio Igor Bogani 0 siblings, 1 reply; 12+ messages in thread From: Andi Kleen @ 2011-03-25 19:49 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Andi Kleen, Rusty Russell, LKML, Ian Lance Taylor, Tim Bird On Fri, Mar 25, 2011 at 05:30:11PM +0100, Alessio Igor Bogani wrote: > Dear Mr. Kleen, > > 2011/3/25 Andi Kleen <andi@firstfloor.org>: > [...] > >> > Patch looks good to me. SORT is a nice trick, too bad it won't > >> > work for the main kernel. > >> > >> Why not? > > > > Because kallsyms is supposed to be in address order, not name order. > > What should that break exactly? > Thanks you very much! For kallsyms you either look it up by address or by name. You can only sort for one of those. Most likely address lookup is more important. If you sorted by name you would make the address case slower. Then the order is also exposed in /proc/kallsyms. If people use this like System.map they likely expect numeric order. -Andi -- ak@linux.intel.com -- Speaking for myself only. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-25 19:49 ` Andi Kleen @ 2011-03-25 21:31 ` Alessio Igor Bogani 2011-03-26 20:04 ` Andi Kleen 0 siblings, 1 reply; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-25 21:31 UTC (permalink / raw) To: Andi Kleen; +Cc: Rusty Russell, LKML, Ian Lance Taylor, Tim Bird Dear Mr. Kleen, 2011/3/25 Andi Kleen <andi@firstfloor.org>: > For kallsyms you either look it up by address or by name. Sorry but I still don't understand the problem in particularly this your sentence: > You can only sort for one of those. I have felt sure to have sorted both: indeed the linker sorts symbols *before* it writes down their addresses (and not after). But I could have made a mistake, obviously. Could you pinpoint me to an sure method for clarify this point, please? Thank you very much and sorry for my stupidity. Ciao, Alessio ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-25 21:31 ` Alessio Igor Bogani @ 2011-03-26 20:04 ` Andi Kleen 2011-03-28 8:22 ` Alessio Igor Bogani 0 siblings, 1 reply; 12+ messages in thread From: Andi Kleen @ 2011-03-26 20:04 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Andi Kleen, Rusty Russell, LKML, Ian Lance Taylor, Tim Bird > I have felt sure to have sorted both: indeed the linker sorts symbols > *before* it writes down their addresses (and not after). But I could > have made a mistake, obviously. I was refering to the address the symbol points to, not the address of the ksymtab entry. -Andi -- ak@linux.intel.com -- Speaking for myself only. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-26 20:04 ` Andi Kleen @ 2011-03-28 8:22 ` Alessio Igor Bogani 2011-03-28 15:59 ` Andi Kleen 0 siblings, 1 reply; 12+ messages in thread From: Alessio Igor Bogani @ 2011-03-28 8:22 UTC (permalink / raw) To: Andi Kleen; +Cc: Rusty Russell, LKML, Tim Bird Dear Mr. Kleen, 2011/3/26 Andi Kleen <andi@firstfloor.org>: >> I have felt sure to have sorted both: indeed the linker sorts symbols >> *before* it writes down their addresses (and not after). But I could >> have made a mistake, obviously. > > I was refering to the address the symbol points to, not the address of > the ksymtab entry. I'm very confused. My patches don't change nothing else but ksymtab* and kcrctab* entries. My intentions were to leave actual symbols completely unchanged. Ciao, Alessio ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols 2011-03-28 8:22 ` Alessio Igor Bogani @ 2011-03-28 15:59 ` Andi Kleen 0 siblings, 0 replies; 12+ messages in thread From: Andi Kleen @ 2011-03-28 15:59 UTC (permalink / raw) To: Alessio Igor Bogani; +Cc: Andi Kleen, Rusty Russell, LKML, Tim Bird > My patches don't change nothing else but ksymtab* and kcrctab* > entries. My intentions were to leave actual symbols completely > unchanged. Your patches are fine because they're for modules. I just said the same trick would not work for the main kernel ksymtab. Sorry for the confusion. -Andi -- ak@linux.intel.com -- Speaking for myself only. ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2011-03-28 16:00 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-03-23 21:00 [PATCH 0/2] Speed up the symbols' resolution process Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 1/2] Let Linker sort the symbols Alessio Igor Bogani 2011-03-23 21:00 ` [PATCH 2/2] Replace the linear search with a binary search for locate " Alessio Igor Bogani 2011-03-24 15:54 ` Andi Kleen 2011-03-25 5:14 ` Rusty Russell 2011-03-25 15:41 ` Andi Kleen 2011-03-25 16:30 ` Alessio Igor Bogani 2011-03-25 19:49 ` Andi Kleen 2011-03-25 21:31 ` Alessio Igor Bogani 2011-03-26 20:04 ` Andi Kleen 2011-03-28 8:22 ` Alessio Igor Bogani 2011-03-28 15:59 ` Andi Kleen
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).