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

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

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

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.

Thanks to Ian Lance Taylor for help about how the linker works.


Changes since V3:
*) Please ignore this version completely

Changes since V2:
*) Fix a bug in each_symbol() semantics by Anders Kaseorg
*) Split the work in three patches as requested by Rusty Russell
*) Add a generic binary search implementation made by Tim Abbott
*) Remove CONFIG_SYMBOLS_BSEARCH kernel option

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


Alessio Igor Bogani (3):
  module: Restructure each_symbol() code
  module: Sort exported symbols
  module: Use the binary search for symbols resolution

Tim Abbott (1):
  lib: Add generic binary search function to the kernel.

 include/asm-generic/vmlinux.lds.h |   20 ++++----
 include/linux/bsearch.h           |    9 ++++
 include/linux/module.h            |    4 +-
 kernel/module.c                   |   84 ++++++++++++++++++++++++++++---------
 lib/Makefile                      |    3 +-
 lib/bsearch.c                     |   53 +++++++++++++++++++++++
 scripts/module-common.lds         |   11 +++++
 7 files changed, 151 insertions(+), 33 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

-- 
1.7.4.1

[PATCH 1/4] module: Restructure each_symbol() code

[Alessio Igor Bogani]

Restructure code to better integrate future improvements.

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

Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
Signed-off-by: Anders Kaseorg <andersk@ksplice.com>
---
 kernel/module.c |   75 ++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 55 insertions(+), 20 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index d5938a5..b438b25 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,13 +351,20 @@ 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)
+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;
 
-	if (strcmp(syms->start[symnum].name, fsa->name) != 0)
+	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;
 
 	if (!fsa->gplok) {
@@ -379,7 +414,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.4.1

[PATCH 2/4] module: Sort exported symbols

[Alessio Igor Bogani]

This patch places every exported symbol in its own section
(i.e. "___ksymtab__printk").  Thus the linker will use its SORT() directive
to sort and finally merge all symbol in the right and final section
(i.e. "__ksymtab").

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         |   11 +++++++++++
 3 files changed, 23 insertions(+), 12 deletions(-)

diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index bd297a2..349e356 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..cfb9563 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..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

[PATCH 3/4] lib: Add generic binary search function to the kernel.

[Alessio Igor Bogani]

From: Tim Abbott <tabbott@ksplice.com>

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them).  Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.

This generic binary search implementation comes from Ksplice.  It has
the same basic API as the C library bsearch() function.  Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    3 +-
 lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 64 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index ef0f285..4b49a24 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,8 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
+	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
+	 bsearch.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
 
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..5b54758
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt))
+{
+	size_t start = 0, end = num;
+	int result;
+
+	while (start < end) {
+		size_t mid = start + (end - start) / 2;
+
+		result = cmp(key, base + mid * size);
+		if (result < 0)
+			end = mid;
+		else if (result > 0)
+			start = mid + 1;
+		else
+			return (void *)base + mid * size;
+	}
+
+	return NULL;
+}
+EXPORT_SYMBOL(bsearch);
-- 
1.7.4.1

[PATCH 3/4] lib: Add generic binary search function to the kernel.

[Alessio Igor Bogani]

From: Tim Abbott <tabbott@ksplice.com>

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them).  Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.

This generic binary search implementation comes from Ksplice.  It has
the same basic API as the C library bsearch() function.  Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    3 +-
 lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 64 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index ef0f285..4b49a24 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,8 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
+	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
+	 bsearch.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
 
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..5b54758
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt))
+{
+	size_t start = 0, end = num;
+	int result;
+
+	while (start < end) {
+		size_t mid = start + (end - start) / 2;
+
+		result = cmp(key, base + mid * size);
+		if (result < 0)
+			end = mid;
+		else if (result > 0)
+			start = mid + 1;
+		else
+			return (void *)base + mid * size;
+	}
+
+	return NULL;
+}
+EXPORT_SYMBOL(bsearch);
-- 
1.7.4.1

[PATCH 4/4] module: Use the binary search for symbols resolution

[Alessio Igor Bogani]

Takes advantage of the order and locates symbols using binary search.

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 |   23 ++++++++++++++++-------
 1 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index b438b25..74a57c1 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -57,6 +57,7 @@
 #include <linux/kmemleak.h>
 #include <linux/jump_label.h>
 #include <linux/pfn.h>
+#include <linux/bsearch.h>
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/module.h>
@@ -351,22 +352,30 @@ struct find_symbol_arg {
 	const struct kernel_symbol *sym;
 };
 
+static int cmp_name(const void *va, const void *vb)
+{
+	const char *a;
+	const struct kernel_symbol *b;
+	a = va; b = vb;
+	return strcmp(a, b->name);
+}
+
 static bool find_symbol_in_symsearch(const struct symsearch *syms,
 				     struct module *owner,
 				     void *data)
 {
 	struct find_symbol_arg *fsa = data;
+	struct kernel_symbol *sym;
 	unsigned int symnum;
-	int result;
 
-	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)
+	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
+		sizeof(struct kernel_symbol), cmp_name);
+
+	if (sym == NULL)
 		return false;
 
+	symnum = sym - syms->start;
+
 	if (!fsa->gplok) {
 		if (syms->licence == GPL_ONLY)
 			return false;
-- 
1.7.4.1

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Wanlong Gao]

On 4/16/11, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Takes advantage of the order and locates symbols using binary search.
>
> 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 |   23 ++++++++++++++++-------
>  1 files changed, 16 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index b438b25..74a57c1 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -57,6 +57,7 @@
>  #include <linux/kmemleak.h>
>  #include <linux/jump_label.h>
>  #include <linux/pfn.h>
> +#include <linux/bsearch.h>
>
>  #define CREATE_TRACE_POINTS
>  #include <trace/events/module.h>
> @@ -351,22 +352,30 @@ struct find_symbol_arg {
>  	const struct kernel_symbol *sym;
>  };
>
> +static int cmp_name(const void *va, const void *vb)
> +{
> +	const char *a;
> +	const struct kernel_symbol *b;
> +	a = va; b = vb;
> +	return strcmp(a, b->name);
> +}
> +
>  static bool find_symbol_in_symsearch(const struct symsearch *syms,
>  				     struct module *owner,
>  				     void *data)
>  {
>  	struct find_symbol_arg *fsa = data;
> +	struct kernel_symbol *sym;
>  	unsigned int symnum;
> -	int result;
>
> -	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)
> +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> +		sizeof(struct kernel_symbol), cmp_name);
> +
> +	if (sym == NULL)
>  		return false;
>
> +	symnum = sym - syms->start;
> +
>  	if (!fsa->gplok) {
>  		if (syms->licence == GPL_ONLY)
>  			return false;
> --
> 1.7.4.1
>
> --
It seems like a great work .
Thanks
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Wanlong Gao]

On 4/16/11, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Takes advantage of the order and locates symbols using binary search.
>
> 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 |   23 ++++++++++++++++-------
>  1 files changed, 16 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index b438b25..74a57c1 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -57,6 +57,7 @@
>  #include <linux/kmemleak.h>
>  #include <linux/jump_label.h>
>  #include <linux/pfn.h>
> +#include <linux/bsearch.h>
>
>  #define CREATE_TRACE_POINTS
>  #include <trace/events/module.h>
> @@ -351,22 +352,30 @@ struct find_symbol_arg {
>  	const struct kernel_symbol *sym;
>  };
>
> +static int cmp_name(const void *va, const void *vb)
> +{
> +	const char *a;
> +	const struct kernel_symbol *b;
> +	a = va; b = vb;
> +	return strcmp(a, b->name);
> +}
> +
>  static bool find_symbol_in_symsearch(const struct symsearch *syms,
>  				     struct module *owner,
>  				     void *data)
>  {
>  	struct find_symbol_arg *fsa = data;
> +	struct kernel_symbol *sym;
>  	unsigned int symnum;
> -	int result;
>
> -	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)
> +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
As the bsearch func, why not change the syms->stop to syms->end ?
Hmm..Just a stupid suggestion.
Thanks
> +		sizeof(struct kernel_symbol), cmp_name);
> +
> +	if (sym == NULL)
>  		return false;
>
> +	symnum = sym - syms->start;
> +
>  	if (!fsa->gplok) {
>  		if (syms->licence == GPL_ONLY)
>  			return false;
> --
> 1.7.4.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [PATCH 1/4] module: Restructure each_symbol() code

[Rusty Russell]

On Sat, 16 Apr 2011 15:26:10 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Restructure code to better integrate future improvements.

I like all the rest, but I find the function names here a bit confusing.

How about using this (untested!) patch instead?

Thanks!
Rusty.
---
Subject: module: each_symbol_section instead of each_symbol

Instead of having a callback function for each symbol in the kernel,
have a callback for each array of symbols.

This eases the logic when we move to sorted symbols and binary search.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/include/linux/module.h b/include/linux/module.h
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -477,8 +477,9 @@ const struct kernel_symbol *find_symbol(
 					bool warn);
 
 /* Walk the exported symbol table */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
-			    unsigned int symnum, void *data), void *data);
+bool each_symbol_section(bool (*fn)(const struct symsearch *arr,
+				    struct module *owner,
+				    void *data), void *data);
 
 /* Returns 0 and fills in value, defined and namebuf, or -ERANGE if
    symnum out of range. */
diff --git a/kernel/module.c b/kernel/module.c
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -240,23 +240,24 @@ static bool each_symbol_in_section(const
 				   struct module *owner,
 				   bool (*fn)(const struct symsearch *syms,
 					      struct module *owner,
-					      unsigned int symnum, void *data),
+					      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)
+bool each_symbol_section(bool (*fn)(const struct symsearch *arr,
+				    struct module *owner,
+				    void *data),
+			 void *data)
 {
 	struct module *mod;
 	static const struct symsearch arr[] = {
@@ -309,7 +310,7 @@ bool each_symbol(bool (*fn)(const struct
 	}
 	return false;
 }
-EXPORT_SYMBOL_GPL(each_symbol);
+EXPORT_SYMBOL_GPL(each_symbol_section);
 
 struct find_symbol_arg {
 	/* Input */
@@ -323,9 +324,9 @@ 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)
+static bool test_symbol_for_find(const struct symsearch *syms,
+				 struct module *owner,
+				 unsigned int symnum, void *data)
 {
 	struct find_symbol_arg *fsa = data;
 
@@ -365,6 +366,19 @@ static bool find_symbol_in_section(const
 	return true;
 }
 
+static bool find_symbol_in_section(const struct symsearch *syms,
+				   struct module *owner,
+				   void *data)
+{
+	unsigned int i;
+
+	for (i = 0; i < syms->stop - syms->start; i++) {
+		if (test_symbol_for_find(syms, owner, i, data))
+			return true;
+	}
+	return false;
+}
+
 /* Find a symbol and return it, along with, (optional) crc and
  * (optional) module which owns it.  Needs preempt disabled or module_mutex. */
 const struct kernel_symbol *find_symbol(const char *name,
@@ -379,7 +393,7 @@ const struct kernel_symbol *find_symbol(
 	fsa.gplok = gplok;
 	fsa.warn = warn;
 
-	if (each_symbol(find_symbol_in_section, &fsa)) {
+	if (each_symbol_section(find_symbol_in_section, &fsa)) {
 		if (owner)
 			*owner = fsa.owner;
 		if (crc)

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Rusty Russell]

On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao <wanlong.gao@gmail.com> wrote:
> > +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> As the bsearch func, why not change the syms->stop to syms->end ?
> Hmm..Just a stupid suggestion.


The names are derived from the linker symbols for end of sections, which
is __stop_<sectionname>.

Cheers,
Rusty.

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Wanlong Gao]

  2011-4-19 9:37, Rusty Russell wroted:
> On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com>  wrote:
>>> +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
>> As the bsearch func, why not change the syms->stop to syms->end ?
>> Hmm..Just a stupid suggestion.
>
>
> The names are derived from the linker symbols for end of sections, which
> is __stop_<sectionname>.
>
> Cheers,
> Rusty.
As this , why not change the bsearch's "end" to "stop", too ? It will be 
more readable.

Thanks
Wanlong

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Rusty Russell]

On Tue, 19 Apr 2011 09:44:20 +0800, Wanlong Gao <wanlong.gao@gmail.com> wrote:
>   2011-4-19 9:37, Rusty Russell wroted:
> > On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com>  wrote:
> >>> +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> >> As the bsearch func, why not change the syms->stop to syms->end ?
> >> Hmm..Just a stupid suggestion.
> >
> >
> > The names are derived from the linker symbols for end of sections, which
> > is __stop_<sectionname>.
> >
> > Cheers,
> > Rusty.
> As this , why not change the bsearch's "end" to "stop", too ? It will be 
> more readable.

I'm confused.  bsearch uses a count, not an end pointer...

Rusty.

Re: [PATCH 4/4] module: Use the binary search for symbols resolution

[Wanlong Gao]

  2011-4-19 19:35, Rusty Russell wroted:
> On Tue, 19 Apr 2011 09:44:20 +0800, Wanlong Gao<wanlong.gao@gmail.com>  wrote:
>>    2011-4-19 9:37, Rusty Russell wroted:
>>> On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com>   wrote:
>>>>> +	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
>>>> As the bsearch func, why not change the syms->stop to syms->end ?
>>>> Hmm..Just a stupid suggestion.
>>>
>>>
>>> The names are derived from the linker symbols for end of sections, which
>>> is __stop_<sectionname>.
>>>
>>> Cheers,
>>> Rusty.
>> As this , why not change the bsearch's "end" to "stop", too ? It will be
>> more readable.
>
> I'm confused.  bsearch uses a count, not an end pointer...
>
> Rusty.

Hmm...I see, I see . I made a mistake on this func .
Thanks for your explanation.

Best regards

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Dirk Behme]

On 16.04.2011 15:26, Alessio Igor Bogani wrote:
> 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 use 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 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.
>
> 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.
>
> Thanks to Ian Lance Taylor for help about how the linker works.
>
>
> Changes since V3:
> *) Please ignore this version completely
>
> Changes since V2:
> *) Fix a bug in each_symbol() semantics by Anders Kaseorg
> *) Split the work in three patches as requested by Rusty Russell
> *) Add a generic binary search implementation made by Tim Abbott
> *) Remove CONFIG_SYMBOLS_BSEARCH kernel option
>
> Changes since V1:
> *) Merge all patches into only one
> *) Remove few useless things
> *) Introduce CONFIG_SYMBOLS_BSEARCH kernel option
>
>
> Alessio Igor Bogani (3):
>    module: Restructure each_symbol() code
>    module: Sort exported symbols
>    module: Use the binary search for symbols resolution
>
> Tim Abbott (1):
>    lib: Add generic binary search function to the kernel.
>
>   include/asm-generic/vmlinux.lds.h |   20 ++++----
>   include/linux/bsearch.h           |    9 ++++
>   include/linux/module.h            |    4 +-
>   kernel/module.c                   |   84 ++++++++++++++++++++++++++++---------
>   lib/Makefile                      |    3 +-
>   lib/bsearch.c                     |   53 +++++++++++++++++++++++
>   scripts/module-common.lds         |   11 +++++
>   7 files changed, 151 insertions(+), 33 deletions(-)
>   create mode 100644 include/linux/bsearch.h
>   create mode 100644 lib/bsearch.c

Tested-by: Dirk Behme <dirk.behme@googlemail.com>

On an embedded ARM system insmoding a large number of modules the 
overall module load time is improved up to ~1s. Great! :)

It would be nice to get these patches into mainline asap.

Many thanks

Dirk

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Sat, Apr 16, 2011 at 09:26, Alessio Igor Bogani wrote:
> 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.

this breaks symbol prefixed arches (like Blackfin):
  CC      kernel/softirq.o
/tmp/ccp3A6LU.s: Assembler messages:
/tmp/ccp3A6LU.s:3734: Error: symbol `___ksymtab__local_bh_enable' is
already defined
make[1]: *** [kernel/softirq.o] Error 1

this is because your new system of section naming happens to overlap
actual symbol names and the gnu assembler does not allow you to
declare a section and a symbol with the same name.

might be better to pick a separator that cannot appear in a symbol
name.  so rather than "__", use "+".  or some other funky char.
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/11 Mike Frysinger <vapier.adi@gmail.com>:
> this breaks symbol prefixed arches (like Blackfin):
>  CC      kernel/softirq.o
> /tmp/ccp3A6LU.s: Assembler messages:
> /tmp/ccp3A6LU.s:3734: Error: symbol `___ksymtab__local_bh_enable' is
> already defined
> make[1]: *** [kernel/softirq.o] Error 1

Could you provide the preprocessed file and details about the toolchain used?

Thanks!

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/11 Alessio Igor Bogani <abogani@kernel.org>:
> 2011/5/11 Mike Frysinger <vapier.adi@gmail.com>:
>> this breaks symbol prefixed arches (like Blackfin):
>>  CC      kernel/softirq.o
>> /tmp/ccp3A6LU.s: Assembler messages:
>> /tmp/ccp3A6LU.s:3734: Error: symbol `___ksymtab__local_bh_enable' is
>> already defined
>> make[1]: *** [kernel/softirq.o] Error 1
>
> Could you provide the preprocessed file and details about the toolchain used?

Please ignore this now I can reproduce the problem on my machine.

>> name.  so rather than "__", use "+".

Sorry I don't think that is a good choice from a long term point of
view. What do you think to add MODULE_SYMBOL_PREFIX to section names
instead? In this way symbol and section names should always be
different also on symbol prefixed archs (which are blackfin and
h8300).

Thank you very much!

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/11 Alessio Igor Bogani <abogani@kernel.org>:
[...]
>>> this breaks symbol prefixed arches (like Blackfin):
>>>  CC      kernel/softirq.o
>>> /tmp/ccp3A6LU.s: Assembler messages:
>>> /tmp/ccp3A6LU.s:3734: Error: symbol `___ksymtab__local_bh_enable' is
>>> already defined
[...]
>>> name.  so rather than "__", use "+".
>
> Sorry I don't think that is a good choice from a long term point of
> view. What do you think to add MODULE_SYMBOL_PREFIX to section names
> instead? In this way symbol and section names should always be
> different also on symbol prefixed archs (which are blackfin and
> h8300).

I'm thinking to something like this:

diff --git a/include/linux/module.h b/include/linux/module.h
index 98ddaf0..c4aa266 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 "__"#sym), unused))	\
+	__attribute__((section("___kcrctab" sec "___" MODULE_SYMBOL_PREFIX
#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 "__"#sym), unused))	\

+	__attribute__((section("___ksymtab" sec "___" MODULE_SYMBOL_PREFIX
#sym), unused))	\
 	= { (unsigned long)&sym, __kstrtab_##sym }

 #define EXPORT_SYMBOL(sym)					\

Could you try this, please?

Thank you very much!

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Wed, May 11, 2011 at 05:19, Alessio Igor Bogani wrote:
>> name.  so rather than "__", use "+".
>
> Sorry I don't think that is a good choice from a long term point of
> view. What do you think to add MODULE_SYMBOL_PREFIX to section names
> instead? In this way symbol and section names should always be
> different also on symbol prefixed archs (which are blackfin and
> h8300).

that doesnt work.  it simply delays the problem to another set of
underscores.  so with that change, local_bh_enable/_local_bh_enable
work, but now send_remote_softirq/__send_remote_softirq fail:
  CC      kernel/softirq.o
nano /tmp/cconhYy1.s: Assembler messages:
/tmp/cconhYy1.s:3664: Error: symbol `___ksymtab___send_remote_softirq'
is already defined
make[1]: *** [kernel/softirq.o] Error 1

so any option that involves using underscores as the separator will
not work.  pick something else, like "+" or "." or ...  i dont see a
problem with using these.
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Wed, May 11, 2011 at 05:19, Alessio Igor Bogani wrote:
>> name.  so rather than "__", use "+".
>
> Sorry I don't think that is a good choice from a long term point of
> view. What do you think to add MODULE_SYMBOL_PREFIX to section names
> instead? In this way symbol and section names should always be
> different also on symbol prefixed archs (which are blackfin and
> h8300).

that doesnt work.  it simply delays the problem to another set of
underscores.  so with that change, local_bh_enable/_local_bh_enable
work, but now send_remote_softirq/__send_remote_softirq fail:
  CC      kernel/softirq.o
nano /tmp/cconhYy1.s: Assembler messages:
/tmp/cconhYy1.s:3664: Error: symbol `___ksymtab___send_remote_softirq'
is already defined
make[1]: *** [kernel/softirq.o] Error 1

so any option that involves using underscores as the separator will
not work.  pick something else, like "+" or "." or ...  i dont see a
problem with using these.
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/11 Mike Frysinger <vapier.adi@gmail.com>:
[...]
>> Sorry I don't think that is a good choice from a long term point of
>> view. What do you think to add MODULE_SYMBOL_PREFIX to section names
>> instead? In this way symbol and section names should always be
>> different also on symbol prefixed archs (which are blackfin and
>> h8300).
>
> that doesnt work.  it simply delays the problem to another set of
> underscores.  so with that change, local_bh_enable/_local_bh_enable
> work, but now send_remote_softirq/__send_remote_softirq fail:

In my opinion it should work. if I use SYMBOL_PREFIX + two underscore
for section name I should always obtain different names.
So if SYMBOL_PREFIX is "_" section name will be "___", if
SYMBOL_PREFIX is "__" section name will be "____" and so on.

>  CC      kernel/softirq.o
> nano /tmp/cconhYy1.s: Assembler messages:
> /tmp/cconhYy1.s:3664: Error: symbol `___ksymtab___send_remote_softirq'
> is already defined
> make[1]: *** [kernel/softirq.o] Error 1

I'm a bit confused. I can build a kernel here:
$ make ARCH=blackfin CROSS_COMPILE="bfin-uclinux-" defconfig
*** Default configuration is based on 'BF537-STAMP_defconfig'
[...]
$ make ARCH=blackfin CROSS_COMPILE="bfin-uclinux-"
  CHK     include/linux/version.h
  CHK     include/generated/utsrelease.h
  CALL    scripts/checksyscalls.sh
[...]
  OBJCOPY arch/blackfin/boot/vmlinux.bin
  GZIP    arch/blackfin/boot/vmlinux.bin.gz
  UIMAGE  arch/blackfin/boot/vmImage.gz
Image Name:   bf537-0.2-2.6.39-rc3-00004-gf26a
Created:      Wed May 11 17:06:45 2011
Image Type:   Blackfin Linux Kernel Image (gzip compressed)
Data Size:    986471 Bytes = 963.35 kB = 0.94 MB
Load Address: 00001000
Entry Point:  001a8518
  Building modules, stage 2.
  MODPOST 69 modules

Unfortunately I can't make skyeye emulator works to test the obtained
kernel image.

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Wed, May 11, 2011 at 11:25, Alessio Igor Bogani wrote:
> 2011/5/11 Mike Frysinger:
>>> Sorry I don't think that is a good choice from a long term point of
>>> view. What do you think to add MODULE_SYMBOL_PREFIX to section names
>>> instead? In this way symbol and section names should always be
>>> different also on symbol prefixed archs (which are blackfin and
>>> h8300).
>>
>> that doesnt work.  it simply delays the problem to another set of
>> underscores.  so with that change, local_bh_enable/_local_bh_enable
>> work, but now send_remote_softirq/__send_remote_softirq fail:
>
> In my opinion it should work. if I use SYMBOL_PREFIX + two underscore
> for section name I should always obtain different names.
> So if SYMBOL_PREFIX is "_" section name will be "___", if
> SYMBOL_PREFIX is "__" section name will be "____" and so on.

i dont follow your logic.  SYMBOL_PREFIX is simply an underscore for
Blackfin, so you are not guaranteed unique names when you're only
prefixing more underscores.  the issue isnt with a symbol colliding
with itself, the issue is with a symbol colliding with another symbol
that has underscores added to its name.

if you export _foo/foo, you'll get an error with the current code:
/* EXPORT_SYMBOL(foo); */
        .section        ___ksymtab__foo,"a",@progbits
___ksymtab_foo:
/* EXPORT_SYMBOL(_foo); */
        .section        ___ksymtab___foo,"a",@progbits
___ksymtab__foo:

you can see how the first section and the last symbol collide

by putting the symbol prefix along the lines of the separator, you
delay it to __foo/foo:
/* EXPORT_SYMBOL(foo); */
        .section        ___ksymtab___foo,"a",@progbits
___ksymtab_foo:
/* EXPORT_SYMBOL(__foo); */
        .section        ___ksymtab_____foo,"a",@progbits
___ksymtab___foo:

the Blackfin toolchain puts the prefix before the ksymtab part while
you're putting it after, so there is always a possibility of collision
unless you pick a split char that doesnt include an underscore.

>>  CC      kernel/softirq.o
>> nano /tmp/cconhYy1.s: Assembler messages:
>> /tmp/cconhYy1.s:3664: Error: symbol `___ksymtab___send_remote_softirq'
>> is already defined
>> make[1]: *** [kernel/softirq.o] Error 1
>
> I'm a bit confused. I can build a kernel here:
> $ make ARCH=blackfin CROSS_COMPILE="bfin-uclinux-" defconfig

it's failing for me with current linux-next and the patch you posted
previously.  also, you dont need to set CROSS_COMPILE as that is the
default value for ARCH=blackfin ...

> Unfortunately I can't make skyeye emulator works to test the obtained
> kernel image.

skyeye is crap.  the latest upstream gdb/sim code can boot a kernel,
but if you aren't up-to-date with that, this binary i've been using
locally should work too:
http://blackfin.uclinux.org/uimages/bfin-elf-run

$ bfin-elf-run --env operating --model bf537 --sirev 2 ./vmlinux
earlyprintk=serial,uart0 console=ttyBF0
Linux version 2.6.39-rc7-ADI-2011R1-pre-00132-g9d91c9a
(vapier@vapier-m) (gcc version 4.3.5 (ADI-trunk/git-ce854ee) ) #16 Wed
May 11 11:55:28 EDT 2011
register early platform devices
bootconsole [early_shadow0] enabled
bootconsole [early_BFuart0] enabled
early printk enabled on early_BFuart0
Limiting kernel memory to 56MB due to anomaly 05000263
Board Memory: 64MB
Kernel Managed Memory: 64MB
Memory map:
  fixedcode = 0x00000400-0x00000490
  text      = 0x00001000-0x000f7f30
  rodata    = 0x000f7f30-0x001456ac
.............
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

Thank you for excellent explanation!

2011/5/11 Mike Frysinger <vapier.adi@gmail.com>:
[...]
> if you export _foo/foo, you'll get an error with the current code:
> /* EXPORT_SYMBOL(foo); */
>        .section        ___ksymtab__foo,"a",@progbits
> ___ksymtab_foo:
> /* EXPORT_SYMBOL(_foo); */
>        .section        ___ksymtab___foo,"a",@progbits
> ___ksymtab__foo:
[...]

So I can suggest two possible solutions for section names:

1) As you suggested change "__" to "+" so
i.e. ___ksymtab+foo

2) Pick a more appropriate name:
i.e. ___ksym__foo
or
i.e. ___ksymsec__foo

In fact these section names aren't a table of symbols (in ksymtab the
"tab" part stand for table, I suppose) so I think that name should be
changed accordingly (my patchset create a temporary section for every
symbol).

Which do you prefer?

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Thu, May 12, 2011 at 05:10, Alessio Igor Bogani wrote:
> 2011/5/11 Mike Frysinger:
> [...]
>> if you export _foo/foo, you'll get an error with the current code:
>> /* EXPORT_SYMBOL(foo); */
>>        .section        ___ksymtab__foo,"a",@progbits
>> ___ksymtab_foo:
>> /* EXPORT_SYMBOL(_foo); */
>>        .section        ___ksymtab___foo,"a",@progbits
>> ___ksymtab__foo:
> [...]
>
> So I can suggest two possible solutions for section names:
>
> 1) As you suggested change "__" to "+" so
> i.e. ___ksymtab+foo
>
> 2) Pick a more appropriate name:
> i.e. ___ksym__foo
> or
> i.e. ___ksymsec__foo
>
> In fact these section names aren't a table of symbols (in ksymtab the
> "tab" part stand for table, I suppose) so I think that name should be
> changed accordingly (my patchset create a temporary section for every
> symbol).
>
> Which do you prefer?

i suggested the diff split char as i dont know how embedded the
"ksymtab" section name is in the rest of the tree.  but if changing
that is an option, that'd work too.  either works for me, so whichever
is less effort for you.
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

I changed the "__" in "+". Could you test this, please?
http://git.kernel.org/?p=linux/kernel/git/abogani/linux-2.6.git;a=shortlog;h=refs/heads/ksym-sorted-v6
Thanks a lot!

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Mike Frysinger]

On Fri, May 13, 2011 at 03:01, Alessio Igor Bogani wrote:
> I changed the "__" in "+". Could you test this, please?
> http://git.kernel.org/?p=linux/kernel/git/abogani/linux-2.6.git;a=shortlog;h=refs/heads/ksym-sorted-v6
> Thanks a lot!

seems to build & boot ok for me.  cheers.
-mike

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/14 Mike Frysinger <vapier.adi@gmail.com>:
> On Fri, May 13, 2011 at 03:01, Alessio Igor Bogani wrote:
>> I changed the "__" in "+". Could you test this, please?
>> http://git.kernel.org/?p=linux/kernel/git/abogani/linux-2.6.git;a=shortlog;h=refs/heads/ksym-sorted-v6
>> Thanks a lot!
>
> seems to build & boot ok for me.  cheers.
> -mike

Thank you very much!

Ciao,
Alessio

Re: [PATCH 0/4] Speed up the symbols' resolution process V4

[Alessio Igor Bogani]

Dear Mr. Frysinger,

2011/5/14 Mike Frysinger <vapier.adi@gmail.com>:
> On Fri, May 13, 2011 at 03:01, Alessio Igor Bogani wrote:
>> I changed the "__" in "+". Could you test this, please?
>> http://git.kernel.org/?p=linux/kernel/git/abogani/linux-2.6.git;a=shortlog;h=refs/heads/ksym-sorted-v6
>> Thanks a lot!
>
> seems to build & boot ok for me.  cheers.
> -mike

Thank you very much!

Ciao,
Alessio

[PATCH 4/4] module: Use the binary search for symbols resolution

[Alessio Igor Bogani]

Takes advantage of the order and locates symbols using binary search.

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 |   12 ++++++++----
 1 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index 8845a0b..731173c 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -57,6 +57,7 @@
 #include <linux/kmemleak.h>
 #include <linux/jump_label.h>
 #include <linux/pfn.h>
+#include <linux/bsearch.h>
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/module.h>
@@ -244,12 +245,15 @@ static bool each_symbol_in_section(const struct symsearch *arr,
 					      unsigned int symnum, void *data),
 				   void *data)
 {
-	unsigned int i, j;
+	unsigned int j;
+	const struct kernel_symbol *sym, *start;
+	size_t size = sizeof(struct kernel_symbol);
 
 	for (j = 0; j < arrsize; j++) {
-		for (i = 0; i < arr[j].stop - arr[j].start; i++)
-			if (cmp(data, &arr[j].start[i]) == 0)
-				return fn(&arr[j], owner, i, data);
+		start = arr[j].start;
+		sym = bsearch(data, start, arr[j].stop - arr[j].start, size, cmp);
+		if (sym != NULL)
+			return fn(&arr[j], owner, sym - start, data);
 	}
 
 	return false;
-- 
1.7.0.4