[PATCH 3/4] lib: Add generic binary search function to the kernel.
From: Tim Abbott tabb...@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 tabb...@ksplice.com
Extra-bikeshedding-by: Alan Jenkins alan-jenk...@tuffmail.co.uk
Extra-bikeshedding-by: André Goddard Rosa andre.godd...@gmail.com
Extra-bikeshedding-by: Rusty Russell ru...@rustcorp.com.au
Signed-off-by: Rusty Russell ru...@rustcorp.com.au
Signed-off-by: Alessio Igor Bogani abog...@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 000..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 000..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 tabb...@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.0.4
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 4/4] module: Use the binary search for symbols resolution
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 abog...@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
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 0/4] Speed up the symbols' resolution process V4
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 -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 1/4] module: Restructure each_symbol() code
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 abog...@kernel.org
Signed-off-by: Anders Kaseorg ande...@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
[PATCH 2/4] module: Sort exported symbols
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 abog...@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
[PATCH 3/4] lib: Add generic binary search function to the kernel.
From: Tim Abbott tabb...@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 tabb...@ksplice.com
Extra-bikeshedding-by: Alan Jenkins alan-jenk...@tuffmail.co.uk
Extra-bikeshedding-by: André Goddard Rosa andre.godd...@gmail.com
Extra-bikeshedding-by: Rusty Russell ru...@rustcorp.com.au
Signed-off-by: Rusty Russell ru...@rustcorp.com.au
Signed-off-by: Alessio Igor Bogani abog...@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 000..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 000..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 tabb...@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
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 4/4] module: Use the binary search for symbols resolution
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 abog...@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
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 0/4] Speed up the symbols' resolution process V4
Dear Mr. Frysinger, 2011/5/11 Mike Frysinger vapier@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 CALLscripts/checksyscalls.sh [...] OBJCOPY arch/blackfin/boot/vmlinux.bin GZIParch/blackfin/boot/vmlinux.bin.gz UIMAGE arch/blackfin/boot/vmImage.gz Image Name: bf537-0.2-2.6.39-rc3-4-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: 1000 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 -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 0/4] Speed up the symbols' resolution process V4
Dear Mr. Frysinger,
2011/5/11 Alessio Igor Bogani abog...@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
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 0/4] Speed up the symbols' resolution process V4
Dear Mr. Frysinger, 2011/5/11 Mike Frysinger vapier@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 -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 0/4] Speed up the symbols' resolution process V4
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 -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] module: Use binary search in lookup_symbol()
Dear Mr. Behme, 2011/5/17 Dirk Behme dirk.be...@googlemail.com: [...] With the version above we should get a warning kernel/module.c: In function 'lookup_symbol': kernel/module.c:1809: warning: unused variable 'ks' Sorry It's my fault. I'll provide a right version in few hours. Ciao, Alessio -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH] module: Use binary search in lookup_symbol()
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani abog...@kernel.org
---
kernel/module.c |7 ++-
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const
char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks stop; ks++)
- if (strcmp(ks-name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[no subject]
Dear Mr. Bird, Dear Mr. Kroah-Hartman,
Sorry for my very bad English.
2011/5/18 Tim Bird tim.b...@am.sony.com:
[...]
Alessio - do you have any timings you can share for the speedup?
You can find a little benchmark using ftrace at end of this email:
https://lkml.org/lkml/2011/4/5/341
On 05/17/2011 04:22 PM, Greg KH wrote:
On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
This work was supported by a hardware donation from the CE Linux Forum.
[...]
Please explain why you make a change, not just who sponsored the change,
that's not very interesting to developers.
You are right. I apologize.
This patch is a missing piece (not essential it is only a further little
optimization) of this little patchset:
https://lkml.org/lkml/2011/4/16/48
Unfortunately I forgot to include this patch in the series (my first error)
then I avoided explaining the changes because I had thought that those were
already enough explained in the cover-letter of the patchset (my second error).
Sorry for my mistakes.
Is this better?
Subject: [PATCH] module: Use binary search in lookup_symbol()
The function is_exported() with its helper function lookup_symbol() are used to
verify if a provided symbol is effectively exported by the kernel or by the
modules. Now that both have their symbols sorted we can replace a linear search
with a binary search which provide a considerably speed-up.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani abog...@kernel.org
---
kernel/module.c |7 ++-
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const
char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks stop; ks++)
- if (strcmp(ks-name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
Thank you very much!
Ciao,
Alessio
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: your mail
Dear Mr. Kroah-Hartman, 2011/5/18 Greg KH g...@kroah.com: [...] Care to resend it without all the stuff above so someone (Rusty I guess) can apply it? Sure! It'll follow in few minutes. Thank you very much! Ciao, Alessio -- To unsubscribe from this list: send the line unsubscribe linux-embedded in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH] module: Use binary search in lookup_symbol()
The function is_exported() with its helper function lookup_symbol() are used to
verify if a provided symbol is effectively exported by the kernel or by the
modules. Now that both have their symbols sorted we can replace a linear search
with a binary search which provide a considerably speed-up.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani abog...@kernel.org
Acked-by: Greg Kroah-Hartman gre...@suse.de
---
kernel/module.c |7 ++-
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const
char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks stop; ks++)
- if (strcmp(ks-name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
--
To unsubscribe from this list: send the line unsubscribe linux-embedded in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
