Skip to contentSkip to conversation

Speed up the symbols' resolution process

PATCH In review Alessio Igor Bogani 3 participants 12 messages Mar 23, 2011 – Mar 28, 2011

Subsystems (2)
Generic include/asm header files Module support
lore
Share & tools
lore

Alessio Igor Bogani

author
#0 lore raw

cover Speed up the symbols' resolution process

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(-)
Signature · 1 line
1.7.4.1
author
#1 lore raw

PATCH 1/2 Let Linker sort the symbols

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(-)
include/asm-generic/vmlinux.lds.h +10 -10
index 32c45e5..83f6bc1 100644
@@ -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) = .;	\
 	}								\
 									\
include/linux/module.h +2 -2
index 5de4204..a8116e1 100644
@@ -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)					\
scripts/module-common.lds +19 -0
index 47a1f9a..0057a21 100644
@@ -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) }
 }
Signature · 1 line
1.7.4.1
author
#2 lore raw

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

In reply to Alessio Igor Bogani

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(-)
kernel/module.c +30 -19
index 1f9f7bc..932726d 100644
@@ -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;
Signature · 1 line
1.7.4.1
#3 lore raw

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

Quoted 1 line · Alessio Igor Bogani

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

Signature · 1 line
[email protected] -- Speaking for myself only
#4 lore raw

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

Quoted 6 lines · Andi Kleen
Quoted 1 line · Alessio Igor Bogani

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.

#5 lore raw

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

Quoted 9 lines · Rusty Russell
Quoted 6 lines · Andi Kleen
Quoted 1 line · Alessio Igor Bogani

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

Signature · 1 line
[email protected] -- Speaking for myself only.
author
#6 lore raw

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

Dear Mr. Kleen,

2011/3/25 Andi Kleen <[email protected]>:
[...]

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

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

#7 lore raw

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

Quoted 7 lines · Alessio Igor Bogani

Dear Mr. Kleen,

2011/3/25 Andi Kleen <[email protected]>:
[...]

Quoted 3 lines
Quoted 3 lines
Quoted 2 lines

Patch looks good to me. SORT is a nice trick, too bad it won't work for the main kernel.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

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

Signature · 1 line
[email protected] -- Speaking for myself only.
author
#8 lore raw

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

Dear Mr. Kleen,

2011/3/25 Andi Kleen <[email protected]>:

Quoted 1 line

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:

Quoted 1 line

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

#9 lore raw

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

Quoted 3 lines

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

Signature · 1 line
[email protected] -- Speaking for myself only.
author
#10 lore raw

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

Dear Mr. Kleen,

2011/3/26 Andi Kleen <[email protected]>:

Quoted 6 lines
Quoted 3 lines

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

#11 lore raw

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

Quoted 3 lines

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

Signature · 1 line
[email protected] -- Speaking for myself only.