LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] Speed up the symbols' resolution process V2
@ 2011-04-05 17:22 Alessio Igor Bogani
  2011-04-05 17:22 ` [PATCH] module: Use the binary search for symbols resolution Alessio Igor Bogani
  0 siblings, 1 reply; 5+ messages in thread
From: Alessio Igor Bogani @ 2011-04-05 17:22 UTC (permalink / raw)
  To: Rusty Russell; +Cc: LKML, Tim Bird, Alessio Igor Bogani

The intent of this patch is to speed up the symbols' resolution process.

This objective is achieved by sorting all ksymtab* and kcrctab* symbols
(those which reside both in the kernel and in the modules) and thus add the fast
binary search side by side to the usual slow linear 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 patch
is very simple and short.

In the first place 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!). Thus I 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 (enabling CONFIG_SYMBOLS_BSEARCH).

I'm fairly sure that this is a good speed improvement even though I haven't
made any comprehensive benchmarking (but follow a simple one). In any case
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
and symbols nvolved at boot stage).

I hope that you find that interesting!

This work was supported by a hardware donation from the CE Linux Forum.

Changes since V1:
*) Merge all patches into only one
*) Remove few useless things
*) Introduce CONFIG_SYMBOLS_BSEARCH kernel option 

Using ftrace on each_symbol() function I obtained these values:

Ubuntu       	Vanilla   	 Patched
 34.792 us 	 19.928 us 	9.561 us
104.418 us 	 43.831 us 	4.018 us
 23.075 us 	  9.700 us	2.667 us
 40.798 us 	 15.495 us 	2.534 us
 48.106 us 	  7.658 us	3.219 us
 10.162 us 	  4.144 us	2.895 us
 27.939 us 	 12.624 us 	2.024 us
 39.885 us 	 16.618 us 	1.952 us
 28.419 us 	 12.751 us 	1.760 us
  9.561 us	  4.108 us	1.394 us
 12.744 us 	  4.907 us	1.243 us
 10.342 us 	  4.504 us	2.408 us
 15.435 us 	  6.036 us	2.210 us
  6.456 us	 10.414 us 	1.556 us
 25.807 us 	  5.994 us	2.798 us
 14.654 us 	  6.408 us	2.438 us
 16.150 us 	  1.165 us	2.114 us
  2.534 us	  8.979 us	1.561 us
 22.017 us 	  1.322 us	1.820 us
  2.894 us	 36.035 us 	2.583 us
 95.607 us 	 13.260 us 	1.735 us
 29.657 us 	  4.571 us	1.652 us
 11.778 us 	  1.994 us	2.247 us
  4.498 us	 34.606 us 	1.400 us
 92.022 us 	 36.834 us 	1.664 us
 97.145 us 	  6.696 us	2.840 us
 16.847 us 	  9.417 us	2.486 us
 23.105 us 	 11.099 us 	1.682 us
 27.969 us 	 38.576 us 	1.375 us
100.581 us    	  4.991 us	2.594 us
 12.756 us 	 14.348 us 	1.585 us
 37.309 us 	 37.350 us 	1.717 us
 97.776 us 	  9.657 us	1.297 us
 23.634 us 	  6.612 us	2.072 us
 17.387 us 	 38.791 us 	1.892 us
100.028 us 	 10.300 us 	1.898 us
 25.098 us 	  3.994 us	2.252 us
  9.934 us	 12.048 us 	1.640 us
 28.816 us 	 11.417 us 	1.237 us
 28.407 us 	 38.395 us 	1.459 us
100.057 us 	  7.057 us	2.066 us
 16.396 us 	 38.822 us 	1.183 us
 99.787 us 	 19.153 us 	1.850 us
  7.033 us	 15.862 us 	1.484 us
 44.341 us 	  7.976 us	1.711 us
 41.495 us 	  6.480 us	1.897 us
 19.129 us 	160.435 us 	1.542 us 
 16.498 us 	141.246 us 	0.426 us 
418.032 us 	193.275 us 	10.000 us
402.255 us 	141.780 us 	10.042 us 
408.038 us 	142.243 us 	9.796 us
404.957 us 	142.278 us 	9.759 us
438.656 us 	142.261 us 	9.729 us
399.666 us 	141.978 us 	9.693 us
403.588 us 	142.255 us 	9.694 us
394.987 us 	142.255 us 	9.700 us
404.386 us 	142.242 us 	9.718 us
398.861 us 	142.237 us 	9.735 us
389.197 us 	142.237 us 	9.729 us
401.053 us 	142.273 us 	9.772 us
393.696 us 	142.267 us 	9.730 us
442.008 us 	142.255 us 	9.801 us
398.495 us 	142.254 us 	9.699 us
396.645 us 	142.249 us 	9.711 us
399.474 us 	142.243 us 	9.688 us
400.327 us 	142.399 us 	9.694 us
399.023 us 	142.267 us 	9.718 us
397.588 us 	142.249 us 	9.687 us
397.960 us 	142.254 us 	9.699 us
398.147 us 	142.237 us 	9.724 us
397.065 us 	142.297 us 	9.718 us
442.193 us 	142.248 us 	9.700 us
396.555 us 	142.249 us 	9.747 us
402.158 us 	142.261 us 	9.705 us
399.072 us 	142.254 us 	9.724 us
400.074 us 	158.050 us 	9.730 us
396.928 us 	142.567 us 	9.723 us
395.666 us 	142.260 us 	9.837 us

Ubuntu  kernel 2.6.38-7-generic 3306 modules
Vanilla kernel 2.6.38 42 modules
Patched kernel 2.6.38 42 modules

Alessio Igor Bogani (1):
  module: Use the binary search for symbols resolution

 include/asm-generic/vmlinux.lds.h |   43 +++++++++++++++++++++------
 include/linux/module.h            |   12 ++++++-
 init/Kconfig                      |    7 ++++
 kernel/module.c                   |   57 +++++++++++++++++++++++++-----------
 scripts/module-common.lds         |   11 +++++++
 5 files changed, 100 insertions(+), 30 deletions(-)

-- 
1.7.4.1


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

* [PATCH] module: Use the binary search for symbols resolution
  2011-04-05 17:22 [PATCH] Speed up the symbols' resolution process V2 Alessio Igor Bogani
@ 2011-04-05 17:22 ` Alessio Igor Bogani
  2011-04-07 13:49   ` Jason Wessel
  2011-04-12  3:48   ` Rusty Russell
  0 siblings, 2 replies; 5+ messages in thread
From: Alessio Igor Bogani @ 2011-04-05 17:22 UTC (permalink / raw)
  To: Rusty Russell; +Cc: LKML, Tim Bird, Alessio Igor Bogani

Let the linker sort the exported symbols and use the binary search for locate them.

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 |   43 +++++++++++++++++++++------
 include/linux/module.h            |   12 ++++++-
 init/Kconfig                      |    7 ++++
 kernel/module.c                   |   57 +++++++++++++++++++++++++-----------
 scripts/module-common.lds         |   11 +++++++
 5 files changed, 100 insertions(+), 30 deletions(-)

diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index fe77e33..b438dd9 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -149,6 +149,29 @@
 #define TRACE_SYSCALLS()
 #endif
 
+#ifdef CONFIG_SYMBOLS_BSEARCH
+#define KSYMTAB_SYMBOLS SORT(___ksymtab__*)
+#define KSYMTAB_GPL_SYMBOLS SORT(___ksymtab_gpl__*)
+#define KSYMTAB_UNUSED_SYMBOLS SORT(___ksymtab_unused__*)
+#define KSYMTAB_UNUSED_GPL_SYMBOLS SORT(___ksymtab_unused_gpl__*)
+#define KSYMTAB_GPL_FUTURE_SYMBOLS SORT(___ksymtab_gpl_future__*)
+#define KCRCTAB_SYMBOLS SORT(___kcrctab__*)
+#define KCRCTAB_GPL_SYMBOLS SORT(___kcrctab_gpl__*)
+#define KCRCTAB_UNUSED_SYMBOLS SORT(___kcrctab_unused__*)
+#define KCRCTAB_UNUSED_GPL_SYMBOLS SORT(___kcrctab_unused_gpl__*)
+#define KCRCTAB_GPL_FUTURE_SYMBOLS SORT(___kcrctab_gpl_future__*)
+#else
+#define KSYMTAB_SYMBOLS __ksymtab
+#define KSYMTAB_GPL_SYMBOLS __ksymtab_gpl
+#define KSYMTAB_UNUSED_SYMBOLS __ksymtab_unused
+#define KSYMTAB_UNUSED_GPL_SYMBOLS __ksymtab_unused_gpl
+#define KSYMTAB_GPL_FUTURE_SYMBOLS __ksymtab_gpl_future
+#define KCRCTAB_SYMBOLS __kcrctab
+#define KCRCTAB_GPL_SYMBOLS __kcrctab_gpl
+#define KCRCTAB_UNUSED_SYMBOLS __kcrctab_unused
+#define KCRCTAB_UNUSED_GPL_SYMBOLS __kcrctab_unused_gpl
+#define KCRCTAB_GPL_FUTURE_SYMBOLS __kcrctab_gpl_future
+#endif
 
 #define KERNEL_DTB()							\
 	STRUCT_ALIGN();							\
@@ -274,70 +297,70 @@
 	/* Kernel symbol table: Normal symbols */			\
 	__ksymtab         : AT(ADDR(__ksymtab) - LOAD_OFFSET) {		\
 		VMLINUX_SYMBOL(__start___ksymtab) = .;			\
-		*(__ksymtab)						\
+		*(KSYMTAB_SYMBOLS)					\
 		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)					\
+		*(KSYMTAB_GPL_SYMBOLS)					\
 		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)					\
+		*(KSYMTAB_UNUSED_SYMBOLS)				\
 		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)					\
+		*(KSYMTAB_UNUSED_GPL_SYMBOLS)				\
 		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)					\
+		*(KSYMTAB_GPL_FUTURE_SYMBOLS)				\
 		VMLINUX_SYMBOL(__stop___ksymtab_gpl_future) = .;	\
 	}								\
 									\
 	/* Kernel symbol table: Normal symbols */			\
 	__kcrctab         : AT(ADDR(__kcrctab) - LOAD_OFFSET) {		\
 		VMLINUX_SYMBOL(__start___kcrctab) = .;			\
-		*(__kcrctab)						\
+		*(KCRCTAB_SYMBOLS)					\
 		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)					\
+		*(KCRCTAB_GPL_SYMBOLS)					\
 		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)					\
+		*(KCRCTAB_UNUSED_SYMBOLS)				\
 		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)					\
+		*(KCRCTAB_UNUSED_GPL_SYMBOLS)				\
 		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)					\
+		*(KCRCTAB_GPL_FUTURE_SYMBOLS)				\
 		VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .;	\
 	}								\
 									\
diff --git a/include/linux/module.h b/include/linux/module.h
index 5de4204..7ffdb0d 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -215,6 +215,14 @@ struct module_use {
 	struct module *source, *target;
 };
 
+#ifdef CONFIG_SYMBOLS_BSEARCH
+#define __KCRCTAB_SECTION(sym, sec) "___kcrctab" sec "__"#sym
+#define __KSYMTAB_SECTION(sym, sec) "___ksymtab" sec "__"#sym
+#else
+#define __KCRCTAB_SECTION(sym, sec) "__kcrctab" sec
+#define __KSYMTAB_SECTION(sym, sec) "__ksymtab" sec
+#endif
+
 #ifndef __GENKSYMS__
 #ifdef CONFIG_MODVERSIONS
 /* Mark the CRC weak since genksyms apparently decides not to
@@ -223,7 +231,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_SECTION(sym, sec)), unused)) \
 	= (unsigned long) &__crc_##sym;
 #else
 #define __CRC_SYMBOL(sym, sec)
@@ -238,7 +246,7 @@ struct module_use {
 	= MODULE_SYMBOL_PREFIX #sym;                    	\
 	static const struct kernel_symbol __ksymtab_##sym	\
 	__used							\
-	__attribute__((section("__ksymtab" sec), unused))	\
+	__attribute__((section(__KSYMTAB_SECTION(sym, sec)), unused)) \
 	= { (unsigned long)&sym, __kstrtab_##sym }
 
 #define EXPORT_SYMBOL(sym)					\
diff --git a/init/Kconfig b/init/Kconfig
index be788c0..4809c3e 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1354,6 +1354,13 @@ config MODULE_SRCVERSION_ALL
 	  the version).  With this option, such a "srcversion" field
 	  will be created for all modules.  If unsure, say N.
 
+config SYMBOLS_BSEARCH
+	bool "Use the binary search for symbols resolution" if EXPERT
+	default n
+	help
+	  Use binary search for symbols resolution during the kernel
+	  modules loading.  If unsure, say N.
+
 endif # MODULES
 
 config INIT_ALL_POSSIBLE
diff --git a/kernel/module.c b/kernel/module.c
index efa290e..cb3c1f7 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,36 @@ static bool each_symbol_in_section(const struct symsearch *arr,
 					      unsigned int symnum, void *data),
 				   void *data)
 {
-	unsigned int i, j;
+	unsigned int j;
+	struct find_symbol_arg *fsa = data;
+	int result;
+#ifdef CONFIG_SYMBOLS_BSEARCH
+	size_t num;
+	int start, end, mid;
+#endif
 
 	for (j = 0; j < arrsize; j++) {
-		for (i = 0; i < arr[j].stop - arr[j].start; i++)
-			if (fn(&arr[j], owner, i, data))
+#ifdef CONFIG_SYMBOLS_BSEARCH
+		num = arr[j].stop - arr[j].start;
+		start = 0, end = num - 1, mid, result;
+		while (start <= end) {
+			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;
+		}
+#else
+		for (unsigned int i = 0; i < arr[j].stop - arr[j].start; i++) {
+			result = strcmp(fsa->name, arr[j].start[i].name);
+			if (result == 0 && fn(&arr[j], owner, i, data))
 				return true;
+		}
+#endif
 	}
 
 	return false;
@@ -311,27 +347,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;
diff --git a/scripts/module-common.lds b/scripts/module-common.lds
index 47a1f9a..055a8d5 100644
--- a/scripts/module-common.lds
+++ b/scripts/module-common.lds
@@ -5,4 +5,15 @@
  */
 SECTIONS {
 	/DISCARD/ : { *(.discard) }
+
+	__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__*)) }
 }
-- 
1.7.4.1


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

* Re: [PATCH] module: Use the binary search for symbols resolution
  2011-04-05 17:22 ` [PATCH] module: Use the binary search for symbols resolution Alessio Igor Bogani
@ 2011-04-07 13:49   ` Jason Wessel
  2011-04-12  3:48   ` Rusty Russell
  1 sibling, 0 replies; 5+ messages in thread
From: Jason Wessel @ 2011-04-07 13:49 UTC (permalink / raw)
  To: Alessio Igor Bogani; +Cc: Rusty Russell, LKML, Tim Bird

On 04/05/2011 12:22 PM, Alessio Igor Bogani wrote:
> Let the linker sort the exported symbols and use the binary search for locate them.
>

It would be nice if this patch header included some of the information from introduction message, that asside the technical content looks good.

> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>

Reviewed-by: Jason Wessel <jason.wessel@windriver.com>


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


This was the only part I had a hard time following, but after having looked at the original source to kernel/module.c, I see how this was optimized and agree.

This looks like a very nice speed up for large interdependent kernel modules.

Cheers,
Jason.

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

* Re: [PATCH] module: Use the binary search for symbols resolution
  2011-04-05 17:22 ` [PATCH] module: Use the binary search for symbols resolution Alessio Igor Bogani
  2011-04-07 13:49   ` Jason Wessel
@ 2011-04-12  3:48   ` Rusty Russell
  2011-04-12 22:36     ` Anders Kaseorg
  1 sibling, 1 reply; 5+ messages in thread
From: Rusty Russell @ 2011-04-12  3:48 UTC (permalink / raw)
  To: Alessio Igor Bogani; +Cc: LKML, Tim Bird, Alessio Igor Bogani, Tim Abbott

On Tue,  5 Apr 2011 19:22:26 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Let the linker sort the exported symbols and use the binary search for
> locate them.

OK, but why is this optional?

Also note that each_symbol() has an out-of-tree user in ksplice, so
changing the semantics to always search for a particular name might
break them.

Assuming they need it, we could rename it (so they can easily detect the
change) to search_symbol() and make it take a comparitor fn and a
"found" function.

So we want this as three patches, I think:
1) Change each_symbol() to search_symbol() as detailed above.
2) Change symbol tables to be sorted.
3) Change module code to do binary search.

That means we can tell exactly *what* breaks things in linux-next :)

Also:
>  	for (j = 0; j < arrsize; j++) {
> -		for (i = 0; i < arr[j].stop - arr[j].start; i++)
> -			if (fn(&arr[j], owner, i, data))
> +#ifdef CONFIG_SYMBOLS_BSEARCH
> +		num = arr[j].stop - arr[j].start;
> +		start = 0, end = num - 1, mid, result;
> +		while (start <= end) {
> +			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;
> +		}
> +#else

This will loop forever if rn() returns false!  You want

     return fn(&arr[j], owner, mid, data)

I think.

But very neat work!
Rusty.

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

* Re: [PATCH] module: Use the binary search for symbols resolution
  2011-04-12  3:48   ` Rusty Russell
@ 2011-04-12 22:36     ` Anders Kaseorg
  0 siblings, 0 replies; 5+ messages in thread
From: Anders Kaseorg @ 2011-04-12 22:36 UTC (permalink / raw)
  To: Rusty Russell; +Cc: Alessio Igor Bogani, LKML, Tim Bird, Tim Abbott

On Tue,  5 Apr 2011 19:22:26 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Let the linker sort the exported symbols and use the binary search for
> locate them.

Previously, the each_symbol API allowed you to iterate through every 
exported symbol in the kernel.  With your modification it can no longer be 
used for that purpose.  Now, in fact, it’s impossible to use each_symbol 
for _any_ purpose outside module.c:

bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
			    unsigned int symnum, void *data), void *data)

‘void *data’ was intended as an argument of arbitrary type to be passed to 
‘fn’.  But your patched each_symbol_in_section uses it as a ‘struct 
find_symbol_arg *’, and that struct only exists inside module.c.

I’ve refactored your module.c change below to avoid breaking the 
each_symbol API, by introducing an intermediate each_symsearch API that 
can be used for both purposes.

Signed-off-by: Anders Kaseorg <andersk@ksplice.com>
---
 kernel/module.c |   96 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 76 insertions(+), 20 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index efa290e..a67a1c9 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -235,28 +235,28 @@ extern const unsigned long __start___kcrctab_unused_gpl[];
 #define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL)
 #endif
 
-static bool each_symbol_in_section(const struct symsearch *arr,
-				   unsigned int arrsize,
-				   struct module *owner,
-				   bool (*fn)(const struct symsearch *syms,
-					      struct module *owner,
-					      unsigned int symnum, void *data),
-				   void *data)
+static bool each_symsearch_in_section(const struct symsearch *arr,
+				      unsigned int arrsize,
+				      struct module *owner,
+				      bool (*fn)(const struct symsearch *syms,
+						 struct module *owner,
+						 void *data),
+				      void *data)
 {
-	unsigned int i, j;
+	unsigned int j;
 
 	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;
+		if (fn(&arr[j], owner, data))
+			return true;
 	}
 
 	return false;
 }
 
 /* Returns true as soon as fn returns true, otherwise false. */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
-			    unsigned int symnum, void *data), void *data)
+static bool each_symsearch(bool (*fn)(const struct symsearch *syms,
+				      struct module *owner, void *data),
+			   void *data)
 {
 	struct module *mod;
 	static const struct symsearch arr[] = {
@@ -278,7 +278,7 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
 #endif
 	};
 
-	if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
+	if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
 		return true;
 
 	list_for_each_entry_rcu(mod, &modules, list) {
@@ -304,11 +304,39 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
 #endif
 		};
 
-		if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, fn, data))
+		if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), mod, fn,
+					      data))
+			return true;
+	}
+	return false;
+}
+
+struct each_symbol_arg {
+	bool (*fn)(const struct symsearch *arr, struct module *owner,
+		   unsigned int symnum, void *data);
+	void *data;
+};
+
+static bool each_symbol_in_symsearch(const struct symsearch *syms,
+				     struct module *owner, void *data)
+{
+	struct each_symbol_arg *esa = data;
+	unsigned int i;
+
+	for (i = 0; i < syms->stop - syms->start; i++) {
+		if (esa->fn(syms, owner, i, esa->data))
 			return true;
 	}
 	return false;
 }
+
+/* Returns true as soon as fn returns true, otherwise false. */
+bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
+			    unsigned int symnum, void *data), void *data)
+{
+	struct each_symbol_arg esa = {fn, data};
+	return each_symsearch(each_symbol_in_symsearch, &esa);
+}
 EXPORT_SYMBOL_GPL(each_symbol);
 
 struct find_symbol_arg {
@@ -323,14 +351,42 @@ struct find_symbol_arg {
 	const struct kernel_symbol *sym;
 };
 
-static bool find_symbol_in_section(const struct symsearch *syms,
-				   struct module *owner,
-				   unsigned int symnum, void *data)
+#define CONFIG_SYMBOLS_BSEARCH
+static bool find_symbol_in_symsearch(const struct symsearch *syms,
+				     struct module *owner,
+				     void *data)
 {
 	struct find_symbol_arg *fsa = data;
+	unsigned int symnum;
+	int result;
+#ifdef CONFIG_SYMBOLS_BSEARCH
+	int start, end;
+#endif
 
-	if (strcmp(syms->start[symnum].name, fsa->name) != 0)
+#ifdef CONFIG_SYMBOLS_BSEARCH
+	start = 0;
+	end = syms->stop - syms->start - 1;
+	while (true) {
+		if (start > end)
+			return false;
+		symnum = (start + end) / 2;
+		result = strcmp(fsa->name, syms->start[symnum].name);
+		if (result < 0)
+			end = symnum - 1;
+		else if (result > 0)
+			start = symnum + 1;
+		else
+			break;
+	}
+#else
+	for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
+		result = strcmp(fsa->name, syms->start[symnum].name);
+		if (result == 0)
+			break;
+	}
+	if (symnum >= syms->stop - syms->start)
 		return false;
+#endif
 
 	if (!fsa->gplok) {
 		if (syms->licence == GPL_ONLY)
@@ -379,7 +435,7 @@ const struct kernel_symbol *find_symbol(const char *name,
 	fsa.gplok = gplok;
 	fsa.warn = warn;
 
-	if (each_symbol(find_symbol_in_section, &fsa)) {
+	if (each_symsearch(find_symbol_in_symsearch, &fsa)) {
 		if (owner)
 			*owner = fsa.owner;
 		if (crc)
-- 
1.7.5.rc0


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

end of thread, other threads:[~2011-04-12 22:36 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-04-05 17:22 [PATCH] Speed up the symbols' resolution process V2 Alessio Igor Bogani
2011-04-05 17:22 ` [PATCH] module: Use the binary search for symbols resolution Alessio Igor Bogani
2011-04-07 13:49   ` Jason Wessel
2011-04-12  3:48   ` Rusty Russell
2011-04-12 22:36     ` Anders Kaseorg

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