[PATCH 2/2] Replace the linear search with a binary search for locate the symbols

[Alessio Igor Bogani <abogani@kernel.org>]

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 |   49 ++++++++++++++++++++++++++++++-------------------
 1 files changed, 30 insertions(+), 19 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index 1f9f7bc..932726d 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,26 @@ static bool each_symbol_in_section(const struct symsearch *arr,
 					      unsigned int symnum, void *data),
 				   void *data)
 {
-	unsigned int i, j;
+	unsigned int j, i;
+	struct find_symbol_arg *fsa = data;
+	size_t num;
+	int start, end, mid, result;
 
 	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;
+		num = arr[j].stop - arr[j].start;
+		start = 0, end = num - 1, mid, result, i = 0;
+		while (start <= end) {
+			i++;
+			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;
+		}
 	}
 
 	return false;
@@ -311,27 +337,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;
-- 
1.7.4.1