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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 23 Mar 2011 22:00:43 +0100
From:	Alessio Igor Bogani <abogani@...nel.org>
To:	Rusty Russell <rusty@...tcorp.com.au>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Ian Lance Taylor <ian@...s.com>,
	Tim Bird <tim.bird@...sony.com>,
	Alessio Igor Bogani <abogani@...nel.org>
Subject: [PATCH 2/2] Replace the linear search with a binary search for locate the symbols

This work was supported by a hardware donation from the CE Linux Forum.

Signed-off-by: Alessio Igor Bogani <abogani@...nel.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

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