lkml.org 
[lkml]   [2011]   [Apr]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH] module: Use the binary search for symbols resolution
Date
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


\
 
 \ /
  Last update: 2011-04-05 19:25    [W:0.070 / U:0.680 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site