All of lore.kernel.org
 help / color / mirror / Atom feed
From: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
To: rusty@rustcorp.com.au
Cc: linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org,
	Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Subject: [PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables
Date: Sat,  7 Nov 2009 21:04:00 +0000	[thread overview]
Message-ID: <1257627841-15817-9-git-send-email-alan-jenkins@tuffmail.co.uk> (raw)
In-Reply-To: <4AF5DF9F.5020208@tuffmail.co.uk>

The builtin symbol tables are now sorted, so we can use a binary
search.

The symbol tables in modules are still unsorted and require linear
searching as before. But since the generic each_symbol() is removed,
the code size only goes up 8 bytes overall on i386.

On my EeePC 701, coldplug is mainly cpu bound and takes 1.5 seconds
during boot. perf showed this change eliminated 20% of cpu cycles during
coldplug, saving 0.3 seconds of real time.

These savings may not be representative since my config is not very well
tuned.  The numbers above represent the loading of 35 modules,
referencing a total of 441 symbols.  Nevertheless, it shows why I think
this is worth doing.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 kernel/module.c |  144 ++++++++++++++++++++++++++++++++++--------------------
 1 files changed, 91 insertions(+), 53 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index ca4f2ba..56a7e65 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -55,6 +55,7 @@
 #include <linux/async.h>
 #include <linux/percpu.h>
 #include <linux/kmemleak.h>
+#include <linux/bsearch.h>
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/module.h>
@@ -264,36 +265,98 @@ bool each_symbol(each_symbol_fn_t *fn, void *data)
 }
 EXPORT_SYMBOL_GPL(each_symbol);
 
-struct find_symbol_arg {
-	/* Input */
-	const char *name;
-	bool gplok;
-	bool warn;
+static int symbol_compare(const void *key, const void *elt)
+{
+	const char *str = key;
+	const struct kernel_symbol *sym = elt;
+	return strcmp(str, sym->name);
+}
 
-	/* Output */
-	struct module *owner;
-	const unsigned long *crc;
+/* binary search on sorted symbols */
+static const struct kernel_symbol *find_symbol_in_kernel(
+	const char *name,
+	enum export_type *t,
+	const unsigned long **crc)
+{
+	struct kernel_symbol *sym;
+	enum export_type type;
+	unsigned int i;
+
+	for (type = 0; type < ARRAY_SIZE(ksymtab); type++) {
+		sym = bsearch(name, ksymtab[type].syms, ksymtab[type].num_syms,
+			      sizeof(struct kernel_symbol), symbol_compare);
+		if (sym) {
+			i = sym - ksymtab[type].syms;
+			*crc = symversion(ksymtab[type].crcs, i);
+			*t = type;
+			return sym;
+		}
+	}
+
+	return NULL;
+}
+
+/* linear search on unsorted symbols */
+static const struct kernel_symbol *find_symbol_in_module(
+	struct module *mod,
+	const char *name,
+	enum export_type *t,
+	const unsigned long **crc)
+{
+	struct ksymtab *symtab = mod->syms;
 	const struct kernel_symbol *sym;
-};
+	enum export_type type;
+	unsigned int i;
 
-static bool find_symbol_in_section(enum export_type type,
-				   const struct kernel_symbol *sym,
-				   const unsigned long *crc,
-				   struct module *owner,
-				   void *data)
+	for (type = 0; type < EXPORT_TYPE_MAX; type++) {
+		for (i = 0; i < symtab[type].num_syms; i++) {
+			sym = &symtab[type].syms[i];
+
+			if (strcmp(sym->name, name) == 0) {
+				*crc = symversion(symtab[type].crcs, i);
+				*t = type;
+				return sym;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/* Find a symbol and return it, along with, (optional) crc and
+ * (optional) module which owns it */
+const struct kernel_symbol *find_symbol(const char *name,
+					struct module **owner,
+					const unsigned long **crc,
+					bool gplok,
+					bool warn)
 {
-	struct find_symbol_arg *fsa = data;
+	struct module *mod = NULL;
+	const struct kernel_symbol *sym;
+	enum export_type type;
+	const unsigned long *crc_value;
 
-	if (strcmp(sym->name, fsa->name) != 0)
-		return false;
+	sym = find_symbol_in_kernel(name, &type, &crc_value);
+	if (sym)
+		goto found;
+
+	list_for_each_entry_rcu(mod, &modules, list) {
+		sym = find_symbol_in_module(mod, name, &type, &crc_value);
+		if (sym)
+			goto found;
+	}
+
+	DEBUGP("Failed to find symbol %s\n", name);
+	return NULL;
 
-	if (!fsa->gplok) {
+found:
+	if (!gplok) {
 		if (export_is_gpl_only(type))
-			return false;
-		if (export_is_gpl_future(type) && fsa->warn) {
+			return NULL;
+		if (export_is_gpl_future(type) && warn) {
 			printk(KERN_WARNING "Symbol %s is being used "
 			       "by a non-GPL module, which will not "
-			       "be allowed in the future\n", fsa->name);
+			       "be allowed in the future\n", name);
 			printk(KERN_WARNING "Please see the file "
 			       "Documentation/feature-removal-schedule.txt "
 			       "in the kernel source tree for more details.\n");
@@ -301,9 +364,9 @@ static bool find_symbol_in_section(enum export_type type,
 	}
 
 #ifdef CONFIG_UNUSED_SYMBOLS
-	if (export_is_unused(type) && fsa->warn) {
+	if (export_is_unused(type) && warn) {
 		printk(KERN_WARNING "Symbol %s is marked as UNUSED, "
-		       "however this module is using it.\n", fsa->name);
+		       "however this module is using it.\n", name);
 		printk(KERN_WARNING
 		       "This symbol will go away in the future.\n");
 		printk(KERN_WARNING
@@ -314,36 +377,11 @@ static bool find_symbol_in_section(enum export_type type,
 	}
 #endif
 
-	fsa->owner = owner;
-	fsa->crc = crc;
-	fsa->sym = sym;
-	return true;
-}
-
-/* Find a symbol and return it, along with, (optional) crc and
- * (optional) module which owns it */
-const struct kernel_symbol *find_symbol(const char *name,
-					struct module **owner,
-					const unsigned long **crc,
-					bool gplok,
-					bool warn)
-{
-	struct find_symbol_arg fsa;
-
-	fsa.name = name;
-	fsa.gplok = gplok;
-	fsa.warn = warn;
-
-	if (each_symbol(find_symbol_in_section, &fsa)) {
-		if (owner)
-			*owner = fsa.owner;
-		if (crc)
-			*crc = fsa.crc;
-		return fsa.sym;
-	}
-
-	DEBUGP("Failed to find symbol %s\n", name);
-	return NULL;
+	if (owner)
+		*owner = mod;
+	if (crc)
+		*crc = crc_value;
+	return sym;
 }
 EXPORT_SYMBOL_GPL(find_symbol);
 
-- 
1.6.3.3


  parent reply	other threads:[~2009-11-07 21:04 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2009-11-07 20:59 [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search) Alan Jenkins
2009-11-07 21:03 ` [PATCH 01/10] ARM: use unified discard definition in linker script Alan Jenkins
2009-11-07 21:03 ` [PATCH 02/10] ARM: unexport symbols used to implement floating point emulation Alan Jenkins
2009-11-07 21:03 ` [PATCH 03/10] module: make MODULE_SYMBOL_PREFIX into a CONFIG option Alan Jenkins
2009-11-07 21:03 ` [PATCH 04/10] module: extract EXPORT_SYMBOL() from module.h into mod_export.h Alan Jenkins
2009-11-07 21:03 ` [PATCH 05/10] kbuild: sort the list of symbols exported by the kernel (__ksymtab) Alan Jenkins
2009-11-07 21:03 ` [PATCH 06/10] module: refactor symbol tables and try to reduce code size of each_symbol() Alan Jenkins
2009-11-07 21:03 ` [PATCH 07/10] lib: Add generic binary search function to the kernel Alan Jenkins
2009-11-07 21:03 ` [PATCH 08/10] lib: bsearch - remove redundant special case for arrays of size 0 Alan Jenkins
2009-11-07 21:04 ` Alan Jenkins [this message]
2009-11-07 21:04 ` [PATCH 10/10] module: fix is_exported() to return true for all types of exports Alan Jenkins
2009-11-09  2:49   ` Rusty Russell
  -- strict thread matches above, loose matches on Subject: below --
2009-11-02 16:52 Fast LKM symbol resolution Alan Jenkins
2009-11-03 10:06 ` [PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables Alan Jenkins
2009-11-04  8:31   ` Rusty Russell

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1257627841-15817-9-git-send-email-alan-jenkins@tuffmail.co.uk \
    --to=alan-jenkins@tuffmail.co.uk \
    --cc=linux-kbuild@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=rusty@rustcorp.com.au \
    --subject='Re: [PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.