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

[Anders Kaseorg <andersk@ksplice.com>]

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

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

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

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

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

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

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