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

From: Anders Kaseorg
Date: Tue Apr 12 2011 - 18:36:58 EST


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

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

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

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

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

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

diff --git a/kernel/module.c b/kernel/module.c
index efa290e..a67a1c9 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -235,28 +235,28 @@ extern const unsigned long __start___kcrctab_unused_gpl[];
#define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL)
#endif

-static bool each_symbol_in_section(const struct symsearch *arr,
- unsigned int arrsize,
- struct module *owner,
- bool (*fn)(const struct symsearch *syms,
- struct module *owner,
- unsigned int symnum, void *data),
- void *data)
+static bool each_symsearch_in_section(const struct symsearch *arr,
+ unsigned int arrsize,
+ struct module *owner,
+ bool (*fn)(const struct symsearch *syms,
+ struct module *owner,
+ void *data),
+ void *data)
{
- unsigned int i, j;
+ unsigned int j;

for (j = 0; j < arrsize; j++) {
- for (i = 0; i < arr[j].stop - arr[j].start; i++)
- if (fn(&arr[j], owner, i, data))
- return true;
+ if (fn(&arr[j], owner, data))
+ return true;
}

return false;
}

/* Returns true as soon as fn returns true, otherwise false. */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
- unsigned int symnum, void *data), void *data)
+static bool each_symsearch(bool (*fn)(const struct symsearch *syms,
+ struct module *owner, void *data),
+ void *data)
{
struct module *mod;
static const struct symsearch arr[] = {
@@ -278,7 +278,7 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};

- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
+ if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
return true;

list_for_each_entry_rcu(mod, &modules, list) {
@@ -304,11 +304,39 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};

- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, fn, data))
+ if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), mod, fn,
+ data))
+ return true;
+ }
+ return false;
+}
+
+struct each_symbol_arg {
+ bool (*fn)(const struct symsearch *arr, struct module *owner,
+ unsigned int symnum, void *data);
+ void *data;
+};
+
+static bool each_symbol_in_symsearch(const struct symsearch *syms,
+ struct module *owner, void *data)
+{
+ struct each_symbol_arg *esa = data;
+ unsigned int i;
+
+ for (i = 0; i < syms->stop - syms->start; i++) {
+ if (esa->fn(syms, owner, i, esa->data))
return true;
}
return false;
}
+
+/* Returns true as soon as fn returns true, otherwise false. */
+bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
+ unsigned int symnum, void *data), void *data)
+{
+ struct each_symbol_arg esa = {fn, data};
+ return each_symsearch(each_symbol_in_symsearch, &esa);
+}
EXPORT_SYMBOL_GPL(each_symbol);

struct find_symbol_arg {
@@ -323,14 +351,42 @@ struct find_symbol_arg {
const struct kernel_symbol *sym;
};

-static bool find_symbol_in_section(const struct symsearch *syms,
- struct module *owner,
- unsigned int symnum, void *data)
+#define CONFIG_SYMBOLS_BSEARCH
+static bool find_symbol_in_symsearch(const struct symsearch *syms,
+ struct module *owner,
+ void *data)
{
struct find_symbol_arg *fsa = data;
+ unsigned int symnum;
+ int result;
+#ifdef CONFIG_SYMBOLS_BSEARCH
+ int start, end;
+#endif

- if (strcmp(syms->start[symnum].name, fsa->name) != 0)
+#ifdef CONFIG_SYMBOLS_BSEARCH
+ start = 0;
+ end = syms->stop - syms->start - 1;
+ while (true) {
+ if (start > end)
+ return false;
+ symnum = (start + end) / 2;
+ result = strcmp(fsa->name, syms->start[symnum].name);
+ if (result < 0)
+ end = symnum - 1;
+ else if (result > 0)
+ start = symnum + 1;
+ else
+ break;
+ }
+#else
+ for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
+ result = strcmp(fsa->name, syms->start[symnum].name);
+ if (result == 0)
+ break;
+ }
+ if (symnum >= syms->stop - syms->start)
return false;
+#endif

if (!fsa->gplok) {
if (syms->licence == GPL_ONLY)
@@ -379,7 +435,7 @@ const struct kernel_symbol *find_symbol(const char *name,
fsa.gplok = gplok;
fsa.warn = warn;

- if (each_symbol(find_symbol_in_section, &fsa)) {
+ if (each_symsearch(find_symbol_in_symsearch, &fsa)) {
if (owner)
*owner = fsa.owner;
if (crc)
--
1.7.5.rc0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/