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] [day] [month] [year] [list]
Message-ID: <alpine.DEB.2.02.1104121809030.2997@dr-wily.mit.edu>
Date:	Tue, 12 Apr 2011 18:36:47 -0400 (EDT)
From:	Anders Kaseorg <andersk@...lice.com>
To:	Rusty Russell <rusty@...tcorp.com.au>
cc:	Alessio Igor Bogani <abogani@...nel.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Tim Bird <tim.bird@...sony.com>,
	Tim Abbott <tabbott@...lice.com>
Subject: Re: [PATCH] module: Use the binary search for symbols resolution

On Tue,  5 Apr 2011 19:22:26 +0200, Alessio Igor Bogani <abogani@...nel.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@...lice.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

--
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/

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ