[PATCH 0/2] Speed up the symbols' resolution process

[PATCH 0/2] Speed up the symbols' resolution process

[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

[PATCH 1/2] Let Linker sort the symbols

[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

[PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[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

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Andi Kleen]

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

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Rusty Russell]

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.

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Andi Kleen]

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.

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Alessio Igor Bogani]

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

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Andi Kleen]

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.

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Alessio Igor Bogani]

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

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Andi Kleen]

> 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.

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Alessio Igor Bogani]

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

Re: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Andi Kleen]

> 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.