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
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
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
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
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
Alessio Igor Bogani <[email protected]> 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
--
[email protected] -- Speaking for myself only
On Thu, 24 Mar 2011 08:54:57 -0700, Andi Kleen <[email protected]> wrote:
> Alessio Igor Bogani <[email protected]> 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.
On Fri, Mar 25, 2011 at 03:44:24PM +1030, Rusty Russell wrote:
> On Thu, 24 Mar 2011 08:54:57 -0700, Andi Kleen <[email protected]> wrote:
> > Alessio Igor Bogani <[email protected]> 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
--
[email protected] -- Speaking for myself only.
Dear Mr. Kleen,
2011/3/25 Andi Kleen <[email protected]>:
[...]
>> > 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
On Fri, Mar 25, 2011 at 05:30:11PM +0100, Alessio Igor Bogani wrote:
> Dear Mr. Kleen,
>
> 2011/3/25 Andi Kleen <[email protected]>:
> [...]
> >> > 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
--
[email protected] -- Speaking for myself only.
Dear Mr. Kleen,
2011/3/25 Andi Kleen <[email protected]>:
> 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
> 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
--
[email protected] -- Speaking for myself only.
Dear Mr. Kleen,
2011/3/26 Andi Kleen <[email protected]>:
>> 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
> 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
--
[email protected] -- Speaking for myself only.