[PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search)

[PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search)

[Alan Jenkins]

As requested by Mike Frysinger, this version of the series

1) generalizes the use of CONFIG_SYMBOL_PREFIX so that arbitrary symbol 
prefixes remain possible
2) uses CONFIG_SYMBOL_PREFIX to implement VMLINUX_SYMBOL() in the 
generic linker script, instead of relying on arch linker scripts to 
define it if needed.


I also changed the position of the patch which implements the above 
changes.  So it is possible to revert or drop the actual optimizations, 
without removing the cleanups and annoying Mike (or Rusty, or Tejun Heo, 
or miscellaneous fans of lib/bsearch.c :).

A clean revert may be useful if hash tables are added in future, to 
avoid the complexity of keeping hash tables + sorted tables + unsorted 
tables.  (This current series leaves module symbol tables unsorted).

[PATCH 01/10] ARM: use unified discard definition in linker script

[Alan Jenkins]

Commit 023bf6f "linker script: unify usage of discard definition"
changed the linker scripts for all architectures except for ARM.
I can find no discussion about this ommision, so here are the changes
for ARM.

These changes are exactly parallel to the ia64 case.

"ia64 is notable because it first throws away some ia64 specific
 subsections and then include the rest of the sections into the final
 image, so those sections must be discarded before the inclusion."

Not boot-tested.  In build testing, the modified linker script generated
an identical vmlinux file.

[I would like to be able to rely on this unified discard definition.
 I want to sort the kernel symbol tables to allow faster symbol
 resolution during module loading. The simplest way appears to be
 to generate sorted versions from vmlinux.o, link them in to vmlinux,
 _and discard the original unsorted tables_.

 This work is driven by my x86 netbook, but it is implemented at a
 generic level. It is possible it will benefit some ARM systems also.]

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Acked-by: Russell King <rmk+kernel@arm.linux.org.uk>
Acked-by-without-testing: Tejun Heo <tj@kernel.org>
---
 arch/arm/kernel/vmlinux.lds.S |   13 ++++++++-----
 1 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
index aecf87d..ec511d4 100644
--- a/arch/arm/kernel/vmlinux.lds.S
+++ b/arch/arm/kernel/vmlinux.lds.S
@@ -79,11 +79,11 @@ SECTIONS
 #endif
 	}
 
-	/DISCARD/ : {			/* Exit code and data		*/
-		EXIT_TEXT
-		EXIT_DATA
-		*(.exitcall.exit)
-		*(.discard)
+	/*
+	 * unwind exit sections must be discarded before the rest of the
+	 * unwind sections get included.
+	 */
+	/DISCARD/ : {
 		*(.ARM.exidx.exit.text)
 		*(.ARM.extab.exit.text)
 #ifndef CONFIG_HOTPLUG_CPU
@@ -271,6 +271,9 @@ SECTIONS
 	.stab.index 0 : { *(.stab.index) }
 	.stab.indexstr 0 : { *(.stab.indexstr) }
 	.comment 0 : { *(.comment) }
+
+	/* Default discards */
+	DISCARDS
 }
 
 /*
-- 
1.6.3.3

[PATCH 02/10] ARM: unexport symbols used to implement floating point emulation

[Alan Jenkins]

The Kconfigs for in-tree floating point emulation do not allow building
as modules. That leaves the Acorn FPEmulator module. I found two public
releases of this as a binary module for 2.1 and 2.2 kernels, optimized
for ARMV4.[1] If there is a resurgence of interest in this, the symbols
can always be re-exported.

This allows the EXPORT_SYMBOL_ALIAS() hack to be removed. The ulterior
motive here is that EXPORT_SYMBOL_ALIAS() makes it harder to sort the
resulting kernel symbol tables.  Sorted symbol tables will allow faster
symbol resolution during module loading.

Note that fp_send_sigs() and fp_printk() are simply aliases for existing
exports and add no obvious value.  Similarly fp_enter could easily be
renamed to kern_fp_enter at the point of definition. Therefore removing
EXPORT_SYMBOL_ALIAS will not serve as a material obstacle to re-adding
the exports should they be desired in future.

Build tested only.

[1] http://ftp.arm.linux.org.uk/pub/linux/arm/fpemulator/

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
CC: Russell King <linux@arm.linux.org.uk>
---
 arch/arm/kernel/armksyms.c |   20 --------------------
 1 files changed, 0 insertions(+), 20 deletions(-)

diff --git a/arch/arm/kernel/armksyms.c b/arch/arm/kernel/armksyms.c
index 0e62770..8214bfe 100644
--- a/arch/arm/kernel/armksyms.c
+++ b/arch/arm/kernel/armksyms.c
@@ -48,27 +48,7 @@ extern void __aeabi_uidivmod(void);
 extern void __aeabi_ulcmp(void);
 
 extern void fpundefinstr(void);
-extern void fp_enter(void);
 
-/*
- * This has a special calling convention; it doesn't
- * modify any of the usual registers, except for LR.
- */
-#define EXPORT_CRC_ALIAS(sym) __CRC_SYMBOL(sym, "")
-
-#define EXPORT_SYMBOL_ALIAS(sym,orig)		\
- EXPORT_CRC_ALIAS(sym)				\
- static const struct kernel_symbol __ksymtab_##sym	\
-  __used __attribute__((section("__ksymtab"))) =	\
-    { (unsigned long)&orig, #sym };
-
-/*
- * floating point math emulator support.
- * These symbols will never change their calling convention...
- */
-EXPORT_SYMBOL_ALIAS(kern_fp_enter,fp_enter);
-EXPORT_SYMBOL_ALIAS(fp_printk,printk);
-EXPORT_SYMBOL_ALIAS(fp_send_sig,send_sig);
 
 EXPORT_SYMBOL(__backtrace);
 
-- 
1.6.3.3

[PATCH 03/10] module: make MODULE_SYMBOL_PREFIX into a CONFIG option

[Alan Jenkins]

The next commit will require the use of MODULE_SYMBOL_PREFIX in
.tmp_exports-asm.S.  Currently it is mixed in with C structure
definitions in "asm/module.h".  Move the definition of this arch option
into Kconfig, so it can be easily accessed by any code.

This also lets modpost.c use the same definition.  Previously modpost
relied on a hardcoded list of architectures in mk_elfconfig.c.

A build test for blackfin, one of the two MODULE_SYMBOL_PREFIX archs,
showed the generated code was unchanged.  vmlinux was identical save
for build ids, and an apparently randomized suffix on a single "__key"
symbol in the kallsyms data).

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Acked-by: Mike Frysinger <vapier@gentoo.org> (blackfin)
CC: Sam Ravnborg <sam@ravnborg.org>
---
 arch/blackfin/Kconfig              |    4 ++++
 arch/blackfin/include/asm/module.h |    2 --
 arch/blackfin/kernel/vmlinux.lds.S |    2 --
 arch/h8300/Kconfig                 |    4 ++++
 arch/h8300/include/asm/module.h    |    2 --
 arch/h8300/kernel/vmlinux.lds.S    |    1 -
 include/asm-generic/vmlinux.lds.h  |    8 ++++++--
 include/linux/module.h             |    6 ++++--
 scripts/Makefile.lib               |    5 +++++
 scripts/mod/Makefile               |    2 +-
 scripts/mod/mk_elfconfig.c         |    9 ---------
 scripts/mod/modpost.c              |    9 +++++++++
 12 files changed, 33 insertions(+), 21 deletions(-)

diff --git a/arch/blackfin/Kconfig b/arch/blackfin/Kconfig
index 9a01d44..1983662 100644
--- a/arch/blackfin/Kconfig
+++ b/arch/blackfin/Kconfig
@@ -5,6 +5,10 @@
 
 mainmenu "Blackfin Kernel Configuration"
 
+config SYMBOL_PREFIX
+	string
+	default "_"
+
 config MMU
 	def_bool n
 
diff --git a/arch/blackfin/include/asm/module.h b/arch/blackfin/include/asm/module.h
index e3128df..81d8b90 100644
--- a/arch/blackfin/include/asm/module.h
+++ b/arch/blackfin/include/asm/module.h
@@ -1,8 +1,6 @@
 #ifndef _ASM_BFIN_MODULE_H
 #define _ASM_BFIN_MODULE_H
 
-#define MODULE_SYMBOL_PREFIX "_"
-
 #define Elf_Shdr        Elf32_Shdr
 #define Elf_Sym         Elf32_Sym
 #define Elf_Ehdr        Elf32_Ehdr
diff --git a/arch/blackfin/kernel/vmlinux.lds.S b/arch/blackfin/kernel/vmlinux.lds.S
index ffd90fb..1f585e8 100644
--- a/arch/blackfin/kernel/vmlinux.lds.S
+++ b/arch/blackfin/kernel/vmlinux.lds.S
@@ -27,8 +27,6 @@
  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  */
 
-#define VMLINUX_SYMBOL(_sym_) _##_sym_
-
 #include <asm-generic/vmlinux.lds.h>
 #include <asm/mem_map.h>
 #include <asm/page.h>
diff --git a/arch/h8300/Kconfig b/arch/h8300/Kconfig
index 9420648..53cc669 100644
--- a/arch/h8300/Kconfig
+++ b/arch/h8300/Kconfig
@@ -10,6 +10,10 @@ config H8300
 	default y
 	select HAVE_IDE
 
+config SYMBOL_PREFIX
+	string
+	default "_"
+
 config MMU
 	bool
 	default n
diff --git a/arch/h8300/include/asm/module.h b/arch/h8300/include/asm/module.h
index de23231..8e46724 100644
--- a/arch/h8300/include/asm/module.h
+++ b/arch/h8300/include/asm/module.h
@@ -8,6 +8,4 @@ struct mod_arch_specific { };
 #define Elf_Sym Elf32_Sym
 #define Elf_Ehdr Elf32_Ehdr
 
-#define MODULE_SYMBOL_PREFIX "_"
-
 #endif /* _ASM_H8/300_MODULE_H */
diff --git a/arch/h8300/kernel/vmlinux.lds.S b/arch/h8300/kernel/vmlinux.lds.S
index b9e2490..03d356d 100644
--- a/arch/h8300/kernel/vmlinux.lds.S
+++ b/arch/h8300/kernel/vmlinux.lds.S
@@ -1,4 +1,3 @@
-#define VMLINUX_SYMBOL(_sym_) _##_sym_
 #include <asm-generic/vmlinux.lds.h>
 #include <asm/page.h>
 
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index b6e818f..67e6520 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -52,8 +52,12 @@
 #define LOAD_OFFSET 0
 #endif
 
-#ifndef VMLINUX_SYMBOL
-#define VMLINUX_SYMBOL(_sym_) _sym_
+#ifndef SYMBOL_PREFIX
+#define VMLINUX_SYMBOL(sym) sym
+#else
+#define PASTE2(x,y) x##y
+#define PASTE(x,y) PASTE2(x,y)
+#define VMLINUX_SYMBOL(sym) PASTE(SYMBOL_PREFIX, sym)
 #endif
 
 /* Align . to a 8 byte boundary equals to maximum function alignment. */
diff --git a/include/linux/module.h b/include/linux/module.h
index 482efc8..6cb1a3c 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -25,8 +25,10 @@
 /* Not Yet Implemented */
 #define MODULE_SUPPORTED_DEVICE(name)
 
-/* some toolchains uses a `_' prefix for all user symbols */
-#ifndef MODULE_SYMBOL_PREFIX
+/* Some toolchains use a `_' prefix for all user symbols. */
+#ifdef CONFIG_SYMBOL_PREFIX
+#define MODULE_SYMBOL_PREFIX CONFIG_SYMBOL_PREFIX
+#else
 #define MODULE_SYMBOL_PREFIX ""
 #endif
 
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 7a77787..f9f1f6c 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -127,6 +127,11 @@ _c_flags += $(if $(patsubst n%,, \
 		$(CFLAGS_GCOV))
 endif
 
+ifdef CONFIG_SYMBOL_PREFIX
+_cpp_flags += -DSYMBOL_PREFIX=$(patsubst "%",%,$(CONFIG_SYMBOL_PREFIX))
+endif
+
+
 # If building the kernel in a separate objtree expand all occurrences
 # of -Idir to -I$(srctree)/dir except for absolute paths (starting with '/').
 
diff --git a/scripts/mod/Makefile b/scripts/mod/Makefile
index 11d69c3..ff954f8 100644
--- a/scripts/mod/Makefile
+++ b/scripts/mod/Makefile
@@ -8,7 +8,7 @@ modpost-objs	:= modpost.o file2alias.o sumversion.o
 $(obj)/modpost.o $(obj)/file2alias.o $(obj)/sumversion.o: $(obj)/elfconfig.h
 
 quiet_cmd_elfconfig = MKELF   $@
-      cmd_elfconfig = $(obj)/mk_elfconfig $(ARCH) < $< > $@
+      cmd_elfconfig = $(obj)/mk_elfconfig < $< > $@
 
 $(obj)/elfconfig.h: $(obj)/empty.o $(obj)/mk_elfconfig FORCE
 	$(call if_changed,elfconfig)
diff --git a/scripts/mod/mk_elfconfig.c b/scripts/mod/mk_elfconfig.c
index 6a96d47..639bca7 100644
--- a/scripts/mod/mk_elfconfig.c
+++ b/scripts/mod/mk_elfconfig.c
@@ -9,9 +9,6 @@ main(int argc, char **argv)
 	unsigned char ei[EI_NIDENT];
 	union { short s; char c[2]; } endian_test;
 
-	if (argc != 2) {
-		fprintf(stderr, "Error: no arch\n");
-	}
 	if (fread(ei, 1, EI_NIDENT, stdin) != EI_NIDENT) {
 		fprintf(stderr, "Error: input truncated\n");
 		return 1;
@@ -55,12 +52,6 @@ main(int argc, char **argv)
 	else
 		exit(1);
 
-	if ((strcmp(argv[1], "h8300") == 0)
-	    || (strcmp(argv[1], "blackfin") == 0))
-		printf("#define MODULE_SYMBOL_PREFIX \"_\"\n");
-	else
-		printf("#define MODULE_SYMBOL_PREFIX \"\"\n");
-
 	return 0;
 }
 
diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index 801a16a..fb0f9b7 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -15,8 +15,17 @@
 #include <stdio.h>
 #include <ctype.h>
 #include "modpost.h"
+#include "../../include/linux/autoconf.h"
 #include "../../include/linux/license.h"
 
+/* Some toolchains use a `_' prefix for all user symbols. */
+#ifdef CONFIG_SYMBOL_PREFIX
+#define MODULE_SYMBOL_PREFIX CONFIG_SYMBOL_PREFIX
+#else
+#define MODULE_SYMBOL_PREFIX ""
+#endif
+
+
 /* Are we using CONFIG_MODVERSIONS? */
 int modversions = 0;
 /* Warn about undefined symbols? (do so if we have vmlinux) */
-- 
1.6.3.3

[PATCH 04/10] module: extract EXPORT_SYMBOL() from module.h into mod_export.h

[Alan Jenkins]

The next commit will add a new implementation of EXPORT_SYMBOL() in
arch-independent assembly language.  It will be used by the build system
to help sort the list of symbols exported by the kernel.

Both implementations will live in the same file, to make it clear that
they should be kept in sync.  Moving them to mod_export.h will avoid
cluttering module.h with "ifndef __ASSEMBLY__".

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 include/linux/mod_export.h |   75 ++++++++++++++++++++++++++++++++++++++++++++
 include/linux/module.h     |   65 +-------------------------------------
 2 files changed, 76 insertions(+), 64 deletions(-)
 create mode 100644 include/linux/mod_export.h

diff --git a/include/linux/mod_export.h b/include/linux/mod_export.h
new file mode 100644
index 0000000..9f38816
--- /dev/null
+++ b/include/linux/mod_export.h
@@ -0,0 +1,75 @@
+#ifndef LINUX_MOD_EXPORT_H
+#define LINUX_MOD_EXPORT_H
+
+#include <linux/compiler.h>
+#include <asm/module.h>
+
+/* Some toolchains use a `_' prefix for all user symbols. */
+#ifdef CONFIG_SYMBOL_PREFIX
+#define MODULE_SYMBOL_PREFIX CONFIG_SYMBOL_PREFIX
+#else
+#define MODULE_SYMBOL_PREFIX ""
+#endif
+
+struct kernel_symbol {
+	unsigned long value;
+	const char *name;
+};
+
+#ifdef CONFIG_MODULES
+#ifndef __GENKSYMS__
+#ifdef CONFIG_MODVERSIONS
+/* Mark the CRC weak since genksyms apparently decides not to
+ * generate a checksums for some symbols */
+#define __CRC_SYMBOL(sym, sec)					\
+	extern void *__crc_##sym __attribute__((weak));		\
+	static const unsigned long __kcrctab_##sym		\
+	__used							\
+	__attribute__((section("__kcrctab" sec), unused))	\
+	= (unsigned long) &__crc_##sym;
+#else
+#define __CRC_SYMBOL(sym, sec)
+#endif
+
+/* For every exported symbol, place a struct in the __ksymtab section */
+#define __EXPORT_SYMBOL(sym, sec)				\
+	extern typeof(sym) sym;					\
+	__CRC_SYMBOL(sym, sec)					\
+	static const char __kstrtab_##sym[]			\
+	__attribute__((section("__ksymtab_strings"), aligned(1))) \
+	= MODULE_SYMBOL_PREFIX #sym;                    	\
+	static const struct kernel_symbol __ksymtab_##sym	\
+	__used							\
+	__attribute__((section("__ksymtab" sec), unused))	\
+	= { (unsigned long)&sym, __kstrtab_##sym }
+
+#define EXPORT_SYMBOL(sym)					\
+	__EXPORT_SYMBOL(sym, "")
+
+#define EXPORT_SYMBOL_GPL(sym)					\
+	__EXPORT_SYMBOL(sym, "_gpl")
+
+#define EXPORT_SYMBOL_GPL_FUTURE(sym)				\
+	__EXPORT_SYMBOL(sym, "_gpl_future")
+
+#ifdef CONFIG_UNUSED_SYMBOLS
+#define EXPORT_UNUSED_SYMBOL(sym) __EXPORT_SYMBOL(sym, "_unused")
+#define EXPORT_UNUSED_SYMBOL_GPL(sym) __EXPORT_SYMBOL(sym, "_unused_gpl")
+#else
+#define EXPORT_UNUSED_SYMBOL(sym)
+#define EXPORT_UNUSED_SYMBOL_GPL(sym)
+#endif
+
+#endif /* __GENKSYMS__ */
+
+#else /* !CONFIG_MODULES */
+
+#define EXPORT_SYMBOL(sym)
+#define EXPORT_SYMBOL_GPL(sym)
+#define EXPORT_SYMBOL_GPL_FUTURE(sym)
+#define EXPORT_UNUSED_SYMBOL(sym)
+#define EXPORT_UNUSED_SYMBOL_GPL(sym)
+
+#endif /* CONFIG_MODULES */
+
+#endif /* LINUX_MOD_EXPORT_H */
diff --git a/include/linux/module.h b/include/linux/module.h
index 6cb1a3c..b9e860a 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -15,6 +15,7 @@
 #include <linux/stringify.h>
 #include <linux/kobject.h>
 #include <linux/moduleparam.h>
+#include <linux/mod_export.h>
 #include <linux/tracepoint.h>
 
 #include <asm/local.h>
@@ -25,21 +26,8 @@
 /* Not Yet Implemented */
 #define MODULE_SUPPORTED_DEVICE(name)
 
-/* Some toolchains use a `_' prefix for all user symbols. */
-#ifdef CONFIG_SYMBOL_PREFIX
-#define MODULE_SYMBOL_PREFIX CONFIG_SYMBOL_PREFIX
-#else
-#define MODULE_SYMBOL_PREFIX ""
-#endif
-
 #define MODULE_NAME_LEN MAX_PARAM_PREFIX_LEN
 
-struct kernel_symbol
-{
-	unsigned long value;
-	const char *name;
-};
-
 struct modversion_info
 {
 	unsigned long crc;
@@ -180,52 +168,6 @@ void *__symbol_get(const char *symbol);
 void *__symbol_get_gpl(const char *symbol);
 #define symbol_get(x) ((typeof(&x))(__symbol_get(MODULE_SYMBOL_PREFIX #x)))
 
-#ifndef __GENKSYMS__
-#ifdef CONFIG_MODVERSIONS
-/* Mark the CRC weak since genksyms apparently decides not to
- * generate a checksums for some symbols */
-#define __CRC_SYMBOL(sym, sec)					\
-	extern void *__crc_##sym __attribute__((weak));		\
-	static const unsigned long __kcrctab_##sym		\
-	__used							\
-	__attribute__((section("__kcrctab" sec), unused))	\
-	= (unsigned long) &__crc_##sym;
-#else
-#define __CRC_SYMBOL(sym, sec)
-#endif
-
-/* For every exported symbol, place a struct in the __ksymtab section */
-#define __EXPORT_SYMBOL(sym, sec)				\
-	extern typeof(sym) sym;					\
-	__CRC_SYMBOL(sym, sec)					\
-	static const char __kstrtab_##sym[]			\
-	__attribute__((section("__ksymtab_strings"), aligned(1))) \
-	= MODULE_SYMBOL_PREFIX #sym;                    	\
-	static const struct kernel_symbol __ksymtab_##sym	\
-	__used							\
-	__attribute__((section("__ksymtab" sec), unused))	\
-	= { (unsigned long)&sym, __kstrtab_##sym }
-
-#define EXPORT_SYMBOL(sym)					\
-	__EXPORT_SYMBOL(sym, "")
-
-#define EXPORT_SYMBOL_GPL(sym)					\
-	__EXPORT_SYMBOL(sym, "_gpl")
-
-#define EXPORT_SYMBOL_GPL_FUTURE(sym)				\
-	__EXPORT_SYMBOL(sym, "_gpl_future")
-
-
-#ifdef CONFIG_UNUSED_SYMBOLS
-#define EXPORT_UNUSED_SYMBOL(sym) __EXPORT_SYMBOL(sym, "_unused")
-#define EXPORT_UNUSED_SYMBOL_GPL(sym) __EXPORT_SYMBOL(sym, "_unused_gpl")
-#else
-#define EXPORT_UNUSED_SYMBOL(sym)
-#define EXPORT_UNUSED_SYMBOL_GPL(sym)
-#endif
-
-#endif
-
 enum module_state
 {
 	MODULE_STATE_LIVE,
@@ -543,11 +485,6 @@ extern void module_update_tracepoints(void);
 extern int module_get_iter_tracepoints(struct tracepoint_iter *iter);
 
 #else /* !CONFIG_MODULES... */
-#define EXPORT_SYMBOL(sym)
-#define EXPORT_SYMBOL_GPL(sym)
-#define EXPORT_SYMBOL_GPL_FUTURE(sym)
-#define EXPORT_UNUSED_SYMBOL(sym)
-#define EXPORT_UNUSED_SYMBOL_GPL(sym)
 
 /* Given an address, look for it in the exception tables. */
 static inline const struct exception_table_entry *
-- 
1.6.3.3

[PATCH 05/10] kbuild: sort the list of symbols exported by the kernel (__ksymtab)

[Alan Jenkins]

modpost of vmlinux.o now extracts the ksymtab sections and outputs
sorted versions of them as .tmp_exports-asm.S.  These sorted sections
are linked into vmlinux and the original unsorted sections are
discarded.

This will allow modules to be loaded faster, resolving symbols using
binary search, without any increase in the memory needed for the
symbol tables.

This does not affect the building of modules, so hopefully it won't
affect compile times too much.

Minimally tested on ARM under QEMU emulator.
Build tested on blackfin; output of "size -A" unchanged.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
CC: Sam Ravnborg <sam@ravnborg.org>
---
 Makefile                          |   24 ++++++++---
 include/asm-generic/vmlinux.lds.h |   39 ++++++++++++-----
 include/linux/mod_export.h        |   84 ++++++++++++++++++++++++++++++++++--
 init/Kconfig                      |    5 ++
 scripts/Makefile.modpost          |    2 +-
 scripts/mod/modpost.c             |   63 +++++++++++++++++++++++++++-
 6 files changed, 193 insertions(+), 24 deletions(-)

diff --git a/Makefile b/Makefile
index 00444a8..a2deddf 100644
--- a/Makefile
+++ b/Makefile
@@ -721,6 +721,8 @@ libs-y		:= $(libs-y1) $(libs-y2)
 #   +--< $(vmlinux-main)
 #   |    +--< driver/built-in.o mm/built-in.o + more
 #   |
+#   +-< .tmp_exports-asm.o (see comments regarding modpost of vmlinux.o)
+#   |
 #   +-< kallsyms.o (see description in CONFIG_KALLSYMS section)
 #
 # vmlinux version (uname -v) cannot be updated during normal
@@ -784,7 +786,6 @@ define rule_vmlinux__
 	$(verify_kallsyms)
 endef
 
-
 ifdef CONFIG_KALLSYMS
 # Generate section listing all symbols and add it into vmlinux $(kallsyms.o)
 # It's a three stage process:
@@ -844,13 +845,13 @@ quiet_cmd_kallsyms = KSYM    $@
 	$(call cmd,kallsyms)
 
 # .tmp_vmlinux1 must be complete except kallsyms, so update vmlinux version
-.tmp_vmlinux1: $(vmlinux-lds) $(vmlinux-all) FORCE
+.tmp_vmlinux1: $(vmlinux-lds) $(vmlinux-all) .tmp_exports-asm.o FORCE
 	$(call if_changed_rule,ksym_ld)
 
-.tmp_vmlinux2: $(vmlinux-lds) $(vmlinux-all) .tmp_kallsyms1.o FORCE
+.tmp_vmlinux2: $(vmlinux-lds) $(vmlinux-all) .tmp_exports-asm.o .tmp_kallsyms1.o FORCE
 	$(call if_changed,vmlinux__)
 
-.tmp_vmlinux3: $(vmlinux-lds) $(vmlinux-all) .tmp_kallsyms2.o FORCE
+.tmp_vmlinux3: $(vmlinux-lds) $(vmlinux-all) .tmp_exports-asm.o .tmp_kallsyms2.o FORCE
 	$(call if_changed,vmlinux__)
 
 # Needs to visit scripts/ before $(KALLSYMS) can be used.
@@ -881,8 +882,18 @@ define rule_vmlinux-modpost
 	$(Q)echo 'cmd_$@ := $(cmd_vmlinux-modpost)' > $(dot-target).cmd
 endef
 
+# The modpost of vmlinux.o above creates .tmp_exports-asm.S, a list of exported
+# symbols sorted by name.  This list is linked into vmlinux to replace the
+# original unsorted exports.  It allows symbols to be resolved efficiently
+# when loading modules.
+.tmp_exports-asm.S: vmlinux.o
+
+ifneq ($(CONFIG_SYMBOL_PREFIX),)
+export AFLAGS_.tmp_exports-asm.o += -DSYMBOL_PREFIX=$(patsubst "%",%,$(CONFIG_SYMBOL_PREFIX))
+endif
+
 # vmlinux image - including updated kernel symbols
-vmlinux: $(vmlinux-lds) $(vmlinux-init) $(vmlinux-main) vmlinux.o $(kallsyms.o) FORCE
+vmlinux: $(vmlinux-lds) $(vmlinux-init) $(vmlinux-main) vmlinux.o .tmp_exports-asm.o $(kallsyms.o) FORCE
 ifdef CONFIG_HEADERS_CHECK
 	$(Q)$(MAKE) -f $(srctree)/Makefile headers_check
 endif
@@ -1232,7 +1243,8 @@ endif # CONFIG_MODULES
 # Directories & files removed with 'make clean'
 CLEAN_DIRS  += $(MODVERDIR)
 CLEAN_FILES +=	vmlinux System.map \
-                .tmp_kallsyms* .tmp_version .tmp_vmlinux* .tmp_System.map
+                .tmp_kallsyms* .tmp_version .tmp_vmlinux* .tmp_System.map \
+                .tmp_exports-asm*
 
 # Directories & files removed with 'make mrproper'
 MRPROPER_DIRS  += include/config include2 usr/include include/generated
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index 67e6520..ea14ede 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -258,76 +258,76 @@
 	/* Kernel symbol table: Normal symbols */			\
 	__ksymtab         : AT(ADDR(__ksymtab) - LOAD_OFFSET) {		\
 		VMLINUX_SYMBOL(__start___ksymtab) = .;			\
-		*(__ksymtab)						\
+		*(__ksymtab_sorted)					\
 		VMLINUX_SYMBOL(__stop___ksymtab) = .;			\
 	}								\
 									\
 	/* Kernel symbol table: GPL-only symbols */			\
 	__ksymtab_gpl     : AT(ADDR(__ksymtab_gpl) - LOAD_OFFSET) {	\
 		VMLINUX_SYMBOL(__start___ksymtab_gpl) = .;		\
-		*(__ksymtab_gpl)					\
+		*(__ksymtab_gpl_sorted)					\
 		VMLINUX_SYMBOL(__stop___ksymtab_gpl) = .;		\
 	}								\
 									\
 	/* Kernel symbol table: Normal unused symbols */		\
 	__ksymtab_unused  : AT(ADDR(__ksymtab_unused) - LOAD_OFFSET) {	\
 		VMLINUX_SYMBOL(__start___ksymtab_unused) = .;		\
-		*(__ksymtab_unused)					\
+		*(__ksymtab_unused_sorted)				\
 		VMLINUX_SYMBOL(__stop___ksymtab_unused) = .;		\
 	}								\
 									\
 	/* Kernel symbol table: GPL-only unused symbols */		\
 	__ksymtab_unused_gpl : AT(ADDR(__ksymtab_unused_gpl) - LOAD_OFFSET) { \
 		VMLINUX_SYMBOL(__start___ksymtab_unused_gpl) = .;	\
-		*(__ksymtab_unused_gpl)					\
+		*(__ksymtab_unused_gpl_sorted)				\
 		VMLINUX_SYMBOL(__stop___ksymtab_unused_gpl) = .;	\
 	}								\
 									\
 	/* Kernel symbol table: GPL-future-only symbols */		\
 	__ksymtab_gpl_future : AT(ADDR(__ksymtab_gpl_future) - LOAD_OFFSET) { \
 		VMLINUX_SYMBOL(__start___ksymtab_gpl_future) = .;	\
-		*(__ksymtab_gpl_future)					\
+		*(__ksymtab_gpl_future_sorted)				\
 		VMLINUX_SYMBOL(__stop___ksymtab_gpl_future) = .;	\
 	}								\
 									\
 	/* Kernel symbol table: Normal symbols */			\
 	__kcrctab         : AT(ADDR(__kcrctab) - LOAD_OFFSET) {		\
 		VMLINUX_SYMBOL(__start___kcrctab) = .;			\
-		*(__kcrctab)						\
+		*(__kcrctab_sorted)					\
 		VMLINUX_SYMBOL(__stop___kcrctab) = .;			\
 	}								\
 									\
 	/* Kernel symbol table: GPL-only symbols */			\
 	__kcrctab_gpl     : AT(ADDR(__kcrctab_gpl) - LOAD_OFFSET) {	\
 		VMLINUX_SYMBOL(__start___kcrctab_gpl) = .;		\
-		*(__kcrctab_gpl)					\
+		*(__kcrctab_gpl_sorted)					\
 		VMLINUX_SYMBOL(__stop___kcrctab_gpl) = .;		\
 	}								\
 									\
 	/* Kernel symbol table: Normal unused symbols */		\
 	__kcrctab_unused  : AT(ADDR(__kcrctab_unused) - LOAD_OFFSET) {	\
 		VMLINUX_SYMBOL(__start___kcrctab_unused) = .;		\
-		*(__kcrctab_unused)					\
+		*(__kcrctab_unused_sorted)				\
 		VMLINUX_SYMBOL(__stop___kcrctab_unused) = .;		\
 	}								\
 									\
 	/* Kernel symbol table: GPL-only unused symbols */		\
 	__kcrctab_unused_gpl : AT(ADDR(__kcrctab_unused_gpl) - LOAD_OFFSET) { \
 		VMLINUX_SYMBOL(__start___kcrctab_unused_gpl) = .;	\
-		*(__kcrctab_unused_gpl)					\
+		*(__kcrctab_unused_gpl_sorted)				\
 		VMLINUX_SYMBOL(__stop___kcrctab_unused_gpl) = .;	\
 	}								\
 									\
 	/* Kernel symbol table: GPL-future-only symbols */		\
 	__kcrctab_gpl_future : AT(ADDR(__kcrctab_gpl_future) - LOAD_OFFSET) { \
 		VMLINUX_SYMBOL(__start___kcrctab_gpl_future) = .;	\
-		*(__kcrctab_gpl_future)					\
+		*(__kcrctab_gpl_future_sorted)				\
 		VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .;	\
 	}								\
 									\
 	/* Kernel symbol table: strings */				\
         __ksymtab_strings : AT(ADDR(__ksymtab_strings) - LOAD_OFFSET) {	\
-		*(__ksymtab_strings)					\
+		*(__ksymtab_strings_sorted)				\
 	}								\
 									\
 	/* __*init sections */						\
@@ -643,6 +643,23 @@
 	EXIT_DATA							\
 	EXIT_CALL							\
 	*(.discard)							\
+									\
+	/* 								\
+	 * Discard the original unsorted symbol tables.			\
+	 * In vmlinux they are replaced by sorted versions		\
+	 * generated by modpost -x.					\
+	 */								\
+	*(__ksymtab)							\
+	*(__ksymtab_gpl)						\
+	*(__ksymtab_unused)						\
+	*(__ksymtab_unused_gpl)						\
+	*(__ksymtab_gpl_future)						\
+	*(__kcrctab)							\
+	*(__kcrctab_gpl)						\
+	*(__kcrctab_unused)						\
+	*(__kcrctab_unused_gpl)						\
+	*(__kcrctab_gpl_future)						\
+	*(__ksymtab_strings)						\
 	}
 
 /**
diff --git a/include/linux/mod_export.h b/include/linux/mod_export.h
index 9f38816..394795e 100644
--- a/include/linux/mod_export.h
+++ b/include/linux/mod_export.h
@@ -1,8 +1,20 @@
 #ifndef LINUX_MOD_EXPORT_H
 #define LINUX_MOD_EXPORT_H
+/*
+ * Define EXPORT_SYMBOL() and friends for kernel modules.
+ *
+ * Under __GENKSYMS__ these definitions are skipped, making it possible to
+ * scan for EXPORT_SYMBOL() in preprocessed C files.
+ *
+ * Under __MODPOST_EXPORTS__ we skip C definitions and define __EXPORT_SYMBOL()
+ * in arch-independent assembly code.  This makes it possible to construct
+ * sorted symbol tables.
+ */
+
+#ifndef __GENKSYMS__
+#ifndef __MODPOST_EXPORTS__
 
 #include <linux/compiler.h>
-#include <asm/module.h>
 
 /* Some toolchains use a `_' prefix for all user symbols. */
 #ifdef CONFIG_SYMBOL_PREFIX
@@ -11,13 +23,13 @@
 #define MODULE_SYMBOL_PREFIX ""
 #endif
 
+#ifdef CONFIG_MODULES
+
 struct kernel_symbol {
 	unsigned long value;
 	const char *name;
 };
 
-#ifdef CONFIG_MODULES
-#ifndef __GENKSYMS__
 #ifdef CONFIG_MODVERSIONS
 /* Mark the CRC weak since genksyms apparently decides not to
  * generate a checksums for some symbols */
@@ -60,8 +72,6 @@ struct kernel_symbol {
 #define EXPORT_UNUSED_SYMBOL_GPL(sym)
 #endif
 
-#endif /* __GENKSYMS__ */
-
 #else /* !CONFIG_MODULES */
 
 #define EXPORT_SYMBOL(sym)
@@ -72,4 +82,68 @@ struct kernel_symbol {
 
 #endif /* CONFIG_MODULES */
 
+#else /* __MODPOST_EXPORTS__ */
+/*
+ * Here is the arch-independent assembly version, used in .tmp_exports-asm.S.
+ *
+ * We use CPP macros since they are more familiar than assembly macros.
+ * Note that CPP macros eat newlines, so each pseudo-instruction must be
+ * terminated by a semicolon.
+ */
+
+#include <asm/bitsperlong.h>
+#include <linux/stringify.h>
+
+#if BITS_PER_LONG == 64
+#define PTR .quad
+#define ALGN .balign 8
+#else
+#define PTR .long
+#define ALGN .balign 4
+#endif
+
+/* build system gives us an unstringified version of CONFIG_SYMBOL_PREFIX */
+#ifndef SYMBOL_PREFIX
+#define SYM(sym) sym
+#else
+#define PASTE2(x,y) x##y
+#define PASTE(x,y) PASTE2(x,y)
+#define SYM(sym) PASTE(SYMBOL_PREFIX, sym)
+#endif
+
+
+#ifdef CONFIG_MODVERSIONS
+#define __CRC_SYMBOL(sym, crcsec)				\
+	.globl SYM(__crc_##sym);				\
+	.weak SYM(__crc_##sym);					\
+	.pushsection crcsec, "a";				\
+	ALGN;							\
+	SYM(__kcrctab_##sym):					\
+	PTR SYM(__crc_##sym);					\
+	.popsection;
+#else
+#define __CRC_SYMBOL(sym, section)
+#endif
+
+#define __EXPORT_SYMBOL(sym, sec, strsec, crcsec)		\
+	.globl SYM(sym);					\
+								\
+	__CRC_SYMBOL(sym, crcsec)				\
+								\
+	.pushsection strsec, "a";				\
+	SYM(__kstrtab_##sym):					\
+	.asciz __stringify(SYM(sym));				\
+	.popsection;						\
+								\
+	.pushsection sec, "a";					\
+	ALGN;							\
+	SYM(__ksymtab_##sym):					\
+	PTR SYM(sym);						\
+	PTR SYM(__kstrtab_##sym);				\
+	.popsection;
+
+#endif /* __MODPOST_EXPORTS__ */
+
+#endif /* __GENKSYMS__ */
+
 #endif /* LINUX_MOD_EXPORT_H */
diff --git a/init/Kconfig b/init/Kconfig
index c7bac39..bb4051c 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1100,6 +1100,11 @@ config BASE_SMALL
 	default 0 if BASE_FULL
 	default 1 if !BASE_FULL
 
+config HAVE_SYMBOL_PREFIX
+	bool
+	help
+	  Some arch toolchains use a `_' prefix for all user symbols.
+
 menuconfig MODULES
 	bool "Enable loadable module support"
 	help
diff --git a/scripts/Makefile.modpost b/scripts/Makefile.modpost
index 8f14c81..876a3c7 100644
--- a/scripts/Makefile.modpost
+++ b/scripts/Makefile.modpost
@@ -91,7 +91,7 @@ __modpost: $(modules:.ko=.o) FORCE
 	$(call cmd,modpost) $(wildcard vmlinux) $(filter-out FORCE,$^)
 
 quiet_cmd_kernel-mod = MODPOST $@
-      cmd_kernel-mod = $(modpost) $@
+      cmd_kernel-mod = $(modpost) -x .tmp_exports-asm.S $@
 
 vmlinux.o: FORCE
 	$(call cmd,kernel-mod)
diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index fb0f9b7..b5a801d 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -163,6 +163,7 @@ struct symbol {
 };
 
 static struct symbol *symbolhash[SYMBOL_HASH_SIZE];
+unsigned int symbolcount;
 
 /* This is based on the hash agorithm from gdbm, via tdb */
 static inline unsigned int tdb_hash(const char *name)
@@ -200,6 +201,7 @@ static struct symbol *new_symbol(const char *name, struct module *module,
 	unsigned int hash;
 	struct symbol *new;
 
+	symbolcount++;
 	hash = tdb_hash(name) % SYMBOL_HASH_SIZE;
 	new = symbolhash[hash] = alloc_symbol(name, 0, symbolhash[hash]);
 	new->module = module;
@@ -1985,6 +1987,58 @@ static void write_dump(const char *fname)
 	write_if_changed(&buf, fname);
 }
 
+static const char *section_names[] = {
+	[export_plain] 		= "",
+	[export_unused]		= "_unused",
+	[export_gpl]		= "_gpl",
+	[export_unused_gpl]	= "_unused_gpl",
+	[export_gpl_future]	= "_gpl_future",
+};
+
+static int compare_symbol_names(const void *a, const void *b)
+{
+	struct symbol *const *syma = a;
+	struct symbol *const *symb = b;
+
+	return strcmp((*syma)->name, (*symb)->name);
+}
+
+/* sort exported symbols and output using arch-independent assembly macros */
+static void write_exports(const char *fname)
+{
+	struct buffer buf = { };
+	struct symbol *sym, **symbols;
+	int i, n;
+
+	symbols = NOFAIL(malloc(sizeof(struct symbol *) * symbolcount));
+	n = 0;
+
+	for (i = 0; i < SYMBOL_HASH_SIZE; i++) {
+		for (sym = symbolhash[i]; sym; sym = sym->next)
+			symbols[n++] = sym;
+	}
+
+	qsort(symbols, n, sizeof(struct symbol *), compare_symbol_names);
+
+	buf_printf(&buf, "#define __MODPOST_EXPORTS__\n");
+	buf_printf(&buf, "#include <linux/mod_export.h>\n");
+	buf_printf(&buf, "\n");
+
+	for (i = 0; i < n; i++) {
+		sym = symbols[i];
+
+		buf_printf(&buf, "__EXPORT_SYMBOL(%s,"
+					" __ksymtab%s_sorted,"
+					" __ksymtab_strings_sorted,"
+					" __kcrctab%s_sorted)\n",
+					sym->name,
+					section_names[sym->export],
+					section_names[sym->export]);
+	}
+
+	write_if_changed(&buf, fname);
+}
+
 static void add_marker(struct module *mod, const char *name, const char *fmt)
 {
 	char *line = NULL;
@@ -2086,6 +2140,7 @@ int main(int argc, char **argv)
 	struct buffer buf = { };
 	char *kernel_read = NULL, *module_read = NULL;
 	char *dump_write = NULL;
+	char *exports_write = NULL;
 	char *markers_read = NULL;
 	char *markers_write = NULL;
 	int opt;
@@ -2093,7 +2148,7 @@ int main(int argc, char **argv)
 	struct ext_sym_list *extsym_iter;
 	struct ext_sym_list *extsym_start = NULL;
 
-	while ((opt = getopt(argc, argv, "i:I:e:cmsSo:awM:K:")) != -1) {
+	while ((opt = getopt(argc, argv, "i:I:e:cmsSo:awM:K:x:")) != -1) {
 		switch (opt) {
 		case 'i':
 			kernel_read = optarg;
@@ -2131,6 +2186,9 @@ int main(int argc, char **argv)
 		case 'w':
 			warn_unresolved = 1;
 			break;
+		case 'x':
+			exports_write = optarg;
+			break;
 			case 'M':
 				markers_write = optarg;
 				break;
@@ -2191,6 +2249,9 @@ int main(int argc, char **argv)
 		     "'make CONFIG_DEBUG_SECTION_MISMATCH=y'\n",
 		     sec_mismatch_count);
 
+	if (exports_write)
+		write_exports(exports_write);
+
 	if (markers_read)
 		read_markers(markers_read);
 
-- 
1.6.3.3

[PATCH 06/10] module: refactor symbol tables and try to reduce code size of each_symbol()

[Alan Jenkins]

find_symbol() will use bsearch() instead of each_symbol(). each_symbol()
is still desired by Ksplice (although it is not in-tree yet).  Let's try
to minimize the code which will be duplicated between these two
functions, by changing how the symbol tables are declared.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 include/linux/module.h |  102 +++++++++++++--------
 kernel/module.c        |  241 ++++++++++++++++++++++++------------------------
 2 files changed, 183 insertions(+), 160 deletions(-)

diff --git a/include/linux/module.h b/include/linux/module.h
index b9e860a..0bb0f74 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -168,6 +168,62 @@ void *__symbol_get(const char *symbol);
 void *__symbol_get_gpl(const char *symbol);
 #define symbol_get(x) ((typeof(&x))(__symbol_get(MODULE_SYMBOL_PREFIX #x)))
 
+#ifdef CONFIG_UNUSED_SYMBOLS
+enum export_type {
+	/* GPL-only exported symbols. */
+	__EXPORT_FLAG_GPL_ONLY =	0x1,
+
+	/* unused exported symbols. */
+	__EXPORT_FLAG_UNUSED =		0x2,
+
+	/* exports that will be GPL-only in the near future. */
+	__EXPORT_FLAG_GPL_FUTURE =	0x4,
+
+	EXPORT_TYPE_PLAIN =		0x0,
+	EXPORT_TYPE_GPL =		0x1,
+	EXPORT_TYPE_UNUSED =		0x2,
+	EXPORT_TYPE_UNUSED_GPL =	0x3,
+	EXPORT_TYPE_GPL_FUTURE = 	0x4,
+
+	EXPORT_TYPE_MAX
+};
+
+#else /* !CONFIG_UNUSED_EXPORTS */
+enum export_type {
+	__EXPORT_FLAG_UNUSED =		0x0,
+	__EXPORT_FLAG_GPL_ONLY =	0x1,
+	__EXPORT_FLAG_GPL_FUTURE =	0x2,
+
+	EXPORT_TYPE_PLAIN =		0x0,
+	EXPORT_TYPE_GPL =		0x1,
+	EXPORT_TYPE_GPL_FUTURE = 	0x2,
+	EXPORT_TYPE_MAX
+};
+#endif
+
+static inline bool export_is_gpl_only(enum export_type type)
+{
+	return (type & __EXPORT_FLAG_GPL_ONLY);
+}
+
+static inline bool export_is_unused(enum export_type type)
+{
+	return (type & __EXPORT_FLAG_UNUSED);
+}
+
+static inline bool export_is_gpl_future(enum export_type type)
+{
+	return (type & __EXPORT_FLAG_GPL_FUTURE);
+}
+
+struct ksymtab {
+	const struct kernel_symbol *syms;
+#ifdef CONFIG_MODVERSIONS
+	const unsigned long *crcs;
+#endif
+	unsigned int num_syms;
+};
+
 enum module_state
 {
 	MODULE_STATE_LIVE,
@@ -193,36 +249,12 @@ struct module
 	struct kobject *holders_dir;
 
 	/* Exported symbols */
-	const struct kernel_symbol *syms;
-	const unsigned long *crcs;
-	unsigned int num_syms;
+	struct ksymtab syms[EXPORT_TYPE_MAX];
 
 	/* Kernel parameters. */
 	struct kernel_param *kp;
 	unsigned int num_kp;
 
-	/* GPL-only exported symbols. */
-	unsigned int num_gpl_syms;
-	const struct kernel_symbol *gpl_syms;
-	const unsigned long *gpl_crcs;
-
-#ifdef CONFIG_UNUSED_SYMBOLS
-	/* unused exported symbols. */
-	const struct kernel_symbol *unused_syms;
-	const unsigned long *unused_crcs;
-	unsigned int num_unused_syms;
-
-	/* GPL-only, unused exported symbols. */
-	unsigned int num_unused_gpl_syms;
-	const struct kernel_symbol *unused_gpl_syms;
-	const unsigned long *unused_gpl_crcs;
-#endif
-
-	/* symbols that will be GPL-only in the near future. */
-	const struct kernel_symbol *gpl_future_syms;
-	const unsigned long *gpl_future_crcs;
-	unsigned int num_gpl_future_syms;
-
 	/* Exception table */
 	unsigned int num_exentries;
 	struct exception_table_entry *extable;
@@ -352,17 +384,6 @@ static inline int within_module_init(unsigned long addr, struct module *mod)
 /* Search for module by name: must hold module_mutex. */
 struct module *find_module(const char *name);
 
-struct symsearch {
-	const struct kernel_symbol *start, *stop;
-	const unsigned long *crcs;
-	enum {
-		NOT_GPL_ONLY,
-		GPL_ONLY,
-		WILL_BE_GPL_ONLY,
-	} licence;
-	bool unused;
-};
-
 /* Search for an exported symbol by name. */
 const struct kernel_symbol *find_symbol(const char *name,
 					struct module **owner,
@@ -370,9 +391,14 @@ const struct kernel_symbol *find_symbol(const char *name,
 					bool gplok,
 					bool warn);
 
+typedef bool each_symbol_fn_t (enum export_type type,
+			       const struct kernel_symbol *sym,
+			       const unsigned long *crc,
+			       struct module *owner,
+			       void *data);
+
 /* Walk the exported symbol table */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
-			    unsigned int symnum, void *data), void *data);
+bool each_symbol(each_symbol_fn_t *fn, void *data);
 
 /* Returns 0 and fills in value, defined and namebuf, or -ERANGE if
    symnum out of range. */
diff --git a/kernel/module.c b/kernel/module.c
index fe748a8..ca4f2ba 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -192,25 +192,56 @@ extern const unsigned long __start___kcrctab_unused[];
 extern const unsigned long __start___kcrctab_unused_gpl[];
 #endif
 
+static struct ksymtab ksymtab[EXPORT_TYPE_MAX];
+
+static int __init init_ksymtab(void)
+{
+	ksymtab[EXPORT_TYPE_PLAIN] = (struct ksymtab) {
+		__start___ksymtab, __start___kcrctab,
+		__stop___ksymtab - __start___ksymtab,
+	};
+	ksymtab[EXPORT_TYPE_GPL] = (struct ksymtab) {
+		__start___ksymtab_gpl, __start___kcrctab_gpl,
+		__stop___ksymtab_gpl - __start___ksymtab_gpl,
+	};
+#ifdef CONFIG_UNUSED_EXPORTS
+	ksymtab[EXPORT_TYPE_UNUSED] = (struct ksymtab) {
+		__start___ksymtab_unused, __start___kcrctab_unused,
+		__stop___ksymtab_unused - __start___ksymtab_unused,
+	};
+	ksymtab[EXPORT_TYPE_UNUSED_GPL] = (struct ksymtab) {
+		__start___ksymtab_unused_gpl, __start___kcrctab_unused_gpl,
+		__stop___ksymtab_unused_gpl - __start___ksymtab_unused_gpl,
+	};
+#endif
+	ksymtab[EXPORT_TYPE_GPL_FUTURE] = (struct ksymtab) {
+		__start___ksymtab_gpl_future, __start___kcrctab_gpl_future,
+		__stop___ksymtab_gpl_future - __start___ksymtab_gpl_future,
+	};
+
+	return 0;
+}
+pure_initcall(init_ksymtab);
+
 #ifndef CONFIG_MODVERSIONS
 #define symversion(base, idx) NULL
 #else
 #define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL)
 #endif
 
-static bool each_symbol_in_section(const struct symsearch *arr,
-				   unsigned int arrsize,
+static bool each_symbol_in_section(const struct ksymtab syms[EXPORT_TYPE_MAX],
 				   struct module *owner,
-				   bool (*fn)(const struct symsearch *syms,
-					      struct module *owner,
-					      unsigned int symnum, void *data),
+				   each_symbol_fn_t *fn,
 				   void *data)
 {
-	unsigned int i, j;
+	enum export_type type;
+	unsigned int i;
 
-	for (j = 0; j < arrsize; j++) {
-		for (i = 0; i < arr[j].stop - arr[j].start; i++)
-			if (fn(&arr[j], owner, i, data))
+	for (type = 0; type < EXPORT_TYPE_MAX; type++) {
+		for (i = 0; i < syms[type].num_syms; i++)
+			if (fn(type, &syms[type].syms[i],
+			       symversion(syms[type].crcs, i),
+			       owner, data))
 				return true;
 	}
 
@@ -218,56 +249,15 @@ static bool each_symbol_in_section(const struct symsearch *arr,
 }
 
 /* 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)
+bool each_symbol(each_symbol_fn_t *fn, void *data)
 {
 	struct module *mod;
-	const struct symsearch arr[] = {
-		{ __start___ksymtab, __stop___ksymtab, __start___kcrctab,
-		  NOT_GPL_ONLY, false },
-		{ __start___ksymtab_gpl, __stop___ksymtab_gpl,
-		  __start___kcrctab_gpl,
-		  GPL_ONLY, false },
-		{ __start___ksymtab_gpl_future, __stop___ksymtab_gpl_future,
-		  __start___kcrctab_gpl_future,
-		  WILL_BE_GPL_ONLY, false },
-#ifdef CONFIG_UNUSED_SYMBOLS
-		{ __start___ksymtab_unused, __stop___ksymtab_unused,
-		  __start___kcrctab_unused,
-		  NOT_GPL_ONLY, true },
-		{ __start___ksymtab_unused_gpl, __stop___ksymtab_unused_gpl,
-		  __start___kcrctab_unused_gpl,
-		  GPL_ONLY, true },
-#endif
-	};
 
-	if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
+	if (each_symbol_in_section(ksymtab, NULL, fn, data))
 		return true;
 
 	list_for_each_entry_rcu(mod, &modules, list) {
-		struct symsearch arr[] = {
-			{ mod->syms, mod->syms + mod->num_syms, mod->crcs,
-			  NOT_GPL_ONLY, false },
-			{ mod->gpl_syms, mod->gpl_syms + mod->num_gpl_syms,
-			  mod->gpl_crcs,
-			  GPL_ONLY, false },
-			{ mod->gpl_future_syms,
-			  mod->gpl_future_syms + mod->num_gpl_future_syms,
-			  mod->gpl_future_crcs,
-			  WILL_BE_GPL_ONLY, false },
-#ifdef CONFIG_UNUSED_SYMBOLS
-			{ mod->unused_syms,
-			  mod->unused_syms + mod->num_unused_syms,
-			  mod->unused_crcs,
-			  NOT_GPL_ONLY, true },
-			{ mod->unused_gpl_syms,
-			  mod->unused_gpl_syms + mod->num_unused_gpl_syms,
-			  mod->unused_gpl_crcs,
-			  GPL_ONLY, true },
-#endif
-		};
-
-		if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, fn, data))
+		if (each_symbol_in_section(mod->syms, mod, fn, data))
 			return true;
 	}
 	return false;
@@ -286,19 +276,21 @@ struct find_symbol_arg {
 	const struct kernel_symbol *sym;
 };
 
-static bool find_symbol_in_section(const struct symsearch *syms,
+static bool find_symbol_in_section(enum export_type type,
+				   const struct kernel_symbol *sym,
+				   const unsigned long *crc,
 				   struct module *owner,
-				   unsigned int symnum, void *data)
+				   void *data)
 {
 	struct find_symbol_arg *fsa = data;
 
-	if (strcmp(syms->start[symnum].name, fsa->name) != 0)
+	if (strcmp(sym->name, fsa->name) != 0)
 		return false;
 
 	if (!fsa->gplok) {
-		if (syms->licence == GPL_ONLY)
+		if (export_is_gpl_only(type))
 			return false;
-		if (syms->licence == WILL_BE_GPL_ONLY && fsa->warn) {
+		if (export_is_gpl_future(type) && fsa->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);
@@ -309,7 +301,7 @@ static bool find_symbol_in_section(const struct symsearch *syms,
 	}
 
 #ifdef CONFIG_UNUSED_SYMBOLS
-	if (syms->unused && fsa->warn) {
+	if (export_is_unused(type) && fsa->warn) {
 		printk(KERN_WARNING "Symbol %s is marked as UNUSED, "
 		       "however this module is using it.\n", fsa->name);
 		printk(KERN_WARNING
@@ -323,8 +315,8 @@ static bool find_symbol_in_section(const struct symsearch *syms,
 #endif
 
 	fsa->owner = owner;
-	fsa->crc = symversion(syms->crcs, symnum);
-	fsa->sym = &syms->start[symnum];
+	fsa->crc = crc;
+	fsa->sym = sym;
 	return true;
 }
 
@@ -1564,23 +1556,13 @@ EXPORT_SYMBOL_GPL(__symbol_get);
 static int verify_export_symbols(struct module *mod)
 {
 	unsigned int i;
-	struct module *owner;
+	enum export_type type;
 	const struct kernel_symbol *s;
-	struct {
-		const struct kernel_symbol *sym;
-		unsigned int num;
-	} arr[] = {
-		{ mod->syms, mod->num_syms },
-		{ mod->gpl_syms, mod->num_gpl_syms },
-		{ mod->gpl_future_syms, mod->num_gpl_future_syms },
-#ifdef CONFIG_UNUSED_SYMBOLS
-		{ mod->unused_syms, mod->num_unused_syms },
-		{ mod->unused_gpl_syms, mod->num_unused_gpl_syms },
-#endif
-	};
+	struct module *owner;
 
-	for (i = 0; i < ARRAY_SIZE(arr); i++) {
-		for (s = arr[i].sym; s < arr[i].sym + arr[i].num; s++) {
+	for (type = 0; type < EXPORT_TYPE_MAX; type++) {
+		for (i = 0; i < mod->syms[type].num_syms; i++) {
+			s = &mod->syms[type].syms[i];
 			if (find_symbol(s->name, &owner, NULL, true, false)) {
 				printk(KERN_ERR
 				       "%s: exports duplicate symbol %s"
@@ -1812,24 +1794,30 @@ static void free_modinfo(struct module *mod)
 
 /* lookup symbol in given range of kernel_symbols */
 static const struct kernel_symbol *lookup_symbol(const char *name,
-	const struct kernel_symbol *start,
-	const struct kernel_symbol *stop)
+	const struct kernel_symbol *syms,
+	unsigned int count)
 {
-	const struct kernel_symbol *ks = start;
-	for (; ks < stop; ks++)
-		if (strcmp(ks->name, name) == 0)
-			return ks;
+	unsigned int i;
+
+	for (i = 0; i < count; i++)
+		if (strcmp(syms[i].name, name) == 0)
+			return &syms[i];
 	return NULL;
 }
 
 static int is_exported(const char *name, unsigned long value,
 		       const struct module *mod)
 {
+	const struct ksymtab *symtab;
 	const struct kernel_symbol *ks;
+
 	if (!mod)
-		ks = lookup_symbol(name, __start___ksymtab, __stop___ksymtab);
+		symtab = &ksymtab[EXPORT_TYPE_PLAIN];
 	else
-		ks = lookup_symbol(name, mod->syms, mod->syms + mod->num_syms);
+		symtab = &mod->syms[EXPORT_TYPE_PLAIN];
+
+	ks = lookup_symbol(name, symtab->syms, symtab->num_syms);
+
 	return ks != NULL && ks->value == value;
 }
 
@@ -2064,6 +2052,26 @@ static inline void kmemleak_load_module(struct module *mod, Elf_Ehdr *hdr,
 }
 #endif
 
+static const char *export_section_names[] = {
+	[EXPORT_TYPE_PLAIN] = "__ksymtab",
+	[EXPORT_TYPE_GPL] = "__ksymtab_gpl",
+#ifdef CONFIG_UNUSED_SYMBOLS
+	[EXPORT_TYPE_UNUSED] = "__ksymtab_unused",
+	[EXPORT_TYPE_UNUSED_GPL] = "__ksymtab_unused_gpl",
+#endif
+	[EXPORT_TYPE_GPL_FUTURE] = "__ksymtab_gpl_future",
+};
+
+static const char *crc_section_names[] = {
+	[EXPORT_TYPE_PLAIN] = "__kcrctab",
+	[EXPORT_TYPE_GPL] = "__kcrctab_gpl",
+#ifdef CONFIG_UNUSED_SYMBOLS
+	[EXPORT_TYPE_UNUSED] = "__kcrctab_unused",
+	[EXPORT_TYPE_UNUSED_GPL] = "__kcrctab_unused_gpl",
+#endif
+	[EXPORT_TYPE_GPL_FUTURE] = "__kcrctab_gpl_future",
+};
+
 /* Allocate and load the module: note that size of section 0 is always
    zero, and we rely on this for optional sections. */
 static noinline struct module *load_module(void __user *umod,
@@ -2078,6 +2086,7 @@ static noinline struct module *load_module(void __user *umod,
 	unsigned int symindex = 0;
 	unsigned int strindex = 0;
 	unsigned int modindex, versindex, infoindex, pcpuindex;
+	enum export_type export_type;
 	struct module *mod;
 	long err = 0;
 	void *percpu = NULL, *ptr = NULL; /* Stops spurious gcc warning */
@@ -2338,34 +2347,21 @@ static noinline struct module *load_module(void __user *umod,
 	 * find optional sections. */
 	mod->kp = section_objs(hdr, sechdrs, secstrings, "__param",
 			       sizeof(*mod->kp), &mod->num_kp);
-	mod->syms = section_objs(hdr, sechdrs, secstrings, "__ksymtab",
-				 sizeof(*mod->syms), &mod->num_syms);
-	mod->crcs = section_addr(hdr, sechdrs, secstrings, "__kcrctab");
-	mod->gpl_syms = section_objs(hdr, sechdrs, secstrings, "__ksymtab_gpl",
-				     sizeof(*mod->gpl_syms),
-				     &mod->num_gpl_syms);
-	mod->gpl_crcs = section_addr(hdr, sechdrs, secstrings, "__kcrctab_gpl");
-	mod->gpl_future_syms = section_objs(hdr, sechdrs, secstrings,
-					    "__ksymtab_gpl_future",
-					    sizeof(*mod->gpl_future_syms),
-					    &mod->num_gpl_future_syms);
-	mod->gpl_future_crcs = section_addr(hdr, sechdrs, secstrings,
-					    "__kcrctab_gpl_future");
 
-#ifdef CONFIG_UNUSED_SYMBOLS
-	mod->unused_syms = section_objs(hdr, sechdrs, secstrings,
-					"__ksymtab_unused",
-					sizeof(*mod->unused_syms),
-					&mod->num_unused_syms);
-	mod->unused_crcs = section_addr(hdr, sechdrs, secstrings,
-					"__kcrctab_unused");
-	mod->unused_gpl_syms = section_objs(hdr, sechdrs, secstrings,
-					    "__ksymtab_unused_gpl",
-					    sizeof(*mod->unused_gpl_syms),
-					    &mod->num_unused_gpl_syms);
-	mod->unused_gpl_crcs = section_addr(hdr, sechdrs, secstrings,
-					    "__kcrctab_unused_gpl");
+	export_type = 0;
+	for (; export_type < ARRAY_SIZE(export_section_names); export_type++) {
+		mod->syms[export_type].syms =
+				section_objs(hdr, sechdrs, secstrings,
+					     export_section_names[export_type],
+					     sizeof(struct kernel_symbol),
+					     &mod->syms[export_type].num_syms);
+#ifdef CONFIG_MODVERSIONS
+		mod->syms[export_type].crcs =
+				section_addr(hdr, sechdrs, secstrings,
+					     crc_section_names[export_type]);
 #endif
+	}
+
 #ifdef CONFIG_CONSTRUCTORS
 	mod->ctors = section_objs(hdr, sechdrs, secstrings, ".ctors",
 				  sizeof(*mod->ctors), &mod->num_ctors);
@@ -2390,19 +2386,20 @@ static noinline struct module *load_module(void __user *umod,
 					     sizeof(*mod->ftrace_callsites),
 					     &mod->num_ftrace_callsites);
 #endif
+
 #ifdef CONFIG_MODVERSIONS
-	if ((mod->num_syms && !mod->crcs)
-	    || (mod->num_gpl_syms && !mod->gpl_crcs)
-	    || (mod->num_gpl_future_syms && !mod->gpl_future_crcs)
-#ifdef CONFIG_UNUSED_SYMBOLS
-	    || (mod->num_unused_syms && !mod->unused_crcs)
-	    || (mod->num_unused_gpl_syms && !mod->unused_gpl_crcs)
-#endif
-		) {
-		err = try_to_force_load(mod,
-					"no versions for exported symbols");
-		if (err)
-			goto cleanup;
+	export_type = 0;
+	for (; export_type < ARRAY_SIZE(mod->syms); export_type++) {
+		if (mod->syms[export_type].syms &&
+		    !mod->syms[export_type].crcs) {
+			err = try_to_force_load(mod,
+				"no versions for exported symbols");
+			if (err)
+				goto cleanup;
+
+			/* force load approved, don't check other sections */
+			break;
+		}
 	}
 #endif
 
-- 
1.6.3.3

[PATCH 07/10] lib: Add generic binary search function to the kernel.

[Alan Jenkins]

From: Tim Abbott <tabbott@ksplice.com>

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them).  Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.

This generic binary search implementation comes from Ksplice.  It has
the same basic API as the C library bsearch() function.  Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    2 +-
 lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index 2e78277..fb60af1 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o
+	 string_helpers.o gcd.o bsearch.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..4297c98
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt))
+{
+	int start = 0, end = num - 1, mid, result;
+	if (num == 0)
+		return NULL;
+
+	while (start <= end) {
+		mid = (start + end) / 2;
+		result = cmp(key, base + mid * size);
+		if (result < 0)
+			end = mid - 1;
+		else if (result > 0)
+			start = mid + 1;
+		else
+			return (void *)base + mid * size;
+	}
+
+	return NULL;
+}
+EXPORT_SYMBOL(bsearch);
-- 
1.6.3.3

[PATCH 08/10] lib: bsearch - remove redundant special case for arrays of size 0

[Alan Jenkins]

> On Thu, 24 Sep 2009, Rusty Russell wrote:
>
>> The if (num == 0) line is superfluous.

On 9/27/09, Tim Abbott <tabbott@ksplice.com> wrote:
>
> You are quite right.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 lib/bsearch.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index 4297c98..2e70664 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -34,8 +34,6 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt))
 {
 	int start = 0, end = num - 1, mid, result;
-	if (num == 0)
-		return NULL;
 
 	while (start <= end) {
 		mid = (start + end) / 2;
-- 
1.6.3.3

[PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables

[Alan Jenkins]

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

[PATCH 10/10] module: fix is_exported() to return true for all types of exports

[Alan Jenkins]

/proc/kallsyms annotates module symbols as global (e.g. 'D' for a data
symbol) or local (e.g. 'd'), depending on whether is_exported() returns
true or false.

Historically, is_exported() only returns true if the symbol was exported
using EXPORT_SYMBOL(). EXPORT_SYMBOL_UNUSED(), for example, is not taken
into account. This looks like an oversight, so let's fix it.

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

diff --git a/kernel/module.c b/kernel/module.c
index 56a7e65..021b9cc 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -1830,33 +1830,19 @@ static void free_modinfo(struct module *mod)
 
 #ifdef CONFIG_KALLSYMS
 
-/* lookup symbol in given range of kernel_symbols */
-static const struct kernel_symbol *lookup_symbol(const char *name,
-	const struct kernel_symbol *syms,
-	unsigned int count)
-{
-	unsigned int i;
-
-	for (i = 0; i < count; i++)
-		if (strcmp(syms[i].name, name) == 0)
-			return &syms[i];
-	return NULL;
-}
-
 static int is_exported(const char *name, unsigned long value,
-		       const struct module *mod)
+		       struct module *mod)
 {
-	const struct ksymtab *symtab;
-	const struct kernel_symbol *ks;
+	const struct kernel_symbol *sym;
+	enum export_type type;
+	const unsigned long *crc;
 
-	if (!mod)
-		symtab = &ksymtab[EXPORT_TYPE_PLAIN];
+	if (mod)
+		sym = find_symbol_in_module(mod, name, &type, &crc);
 	else
-		symtab = &mod->syms[EXPORT_TYPE_PLAIN];
-
-	ks = lookup_symbol(name, symtab->syms, symtab->num_syms);
+		sym = find_symbol_in_kernel(name, &type, &crc);
 
-	return ks != NULL && ks->value == value;
+	return (sym && sym->value == value);
 }
 
 /* As per nm */
-- 
1.6.3.3

Re: [PATCH 10/10] module: fix is_exported() to return true for all types of exports

[Rusty Russell]

On Sun, 8 Nov 2009 07:34:01 am Alan Jenkins wrote:
> /proc/kallsyms annotates module symbols as global (e.g. 'D' for a data
> symbol) or local (e.g. 'd'), depending on whether is_exported() returns
> true or false.

Thanks, I've applied the whole series.

Cheers,
Rusty.
PS.  One fix so far:

Fix for CONFIG_MODVERSIONS=n:

kernel/module.c: In function ‘init_ksymtab’:
kernel/module.c:200: warning: initialization makes integer from pointer without a cast
kernel/module.c:201: warning: excess elements in struct initializer
kernel/module.c:201: warning: (near initialization for ‘(anonymous)’)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/kernel/module.c b/kernel/module.c
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -194,30 +194,45 @@ extern const unsigned long __start___kcr
 
 static struct ksymtab ksymtab[EXPORT_TYPE_MAX];
 
+#ifdef CONFIG_MODVERSIONS
+#define init_one_ksymtab(ksymt, start, stop, crc_start)	\
+	do {						\
+		struct ksymtab *ks = (ksymt);		\
+		ks->syms = (start);			\
+		ks->num_syms = (stop) - ks->syms;	\
+		ks->crcs = (crc_start);			\
+	} while (0)
+#else
+#define init_one_ksymtab(ksymt, start, stop, crc_start)	\
+	do {						\
+		struct ksymtab *ks = (ksymt);		\
+		ks->syms = (start);			\
+		ks->num_syms = (stop) - ks->syms;	\
+	} while (0)
+#endif
+
 static int __init init_ksymtab(void)
 {
-	ksymtab[EXPORT_TYPE_PLAIN] = (struct ksymtab) {
-		__start___ksymtab, __start___kcrctab,
-		__stop___ksymtab - __start___ksymtab,
-	};
-	ksymtab[EXPORT_TYPE_GPL] = (struct ksymtab) {
-		__start___ksymtab_gpl, __start___kcrctab_gpl,
-		__stop___ksymtab_gpl - __start___ksymtab_gpl,
-	};
+	init_one_ksymtab(&ksymtab[EXPORT_TYPE_PLAIN],
+			 __start___ksymtab, __stop___ksymtab,
+			 __start___kcrctab);
+	init_one_ksymtab(&ksymtab[EXPORT_TYPE_GPL],
+			 __start___ksymtab_gpl, __stop___ksymtab_gpl,
+			 __start___kcrctab_gpl);
 #ifdef CONFIG_UNUSED_EXPORTS
-	ksymtab[EXPORT_TYPE_UNUSED] = (struct ksymtab) {
-		__start___ksymtab_unused, __start___kcrctab_unused,
-		__stop___ksymtab_unused - __start___ksymtab_unused,
-	};
-	ksymtab[EXPORT_TYPE_UNUSED_GPL] = (struct ksymtab) {
-		__start___ksymtab_unused_gpl, __start___kcrctab_unused_gpl,
-		__stop___ksymtab_unused_gpl - __start___ksymtab_unused_gpl,
-	};
+	init_one_ksymtab(&ksymtab[EXPORT_TYPE_UNUSED],
+			 __start___ksymtab_unused,
+			 __stop___ksymtab_unused,
+			 __start___kcrctab_unused);
+	init_one_ksymtab(&ksymtab[EXPORT_TYPE_UNUSED_GPL],
+			 __start___ksymtab_unused_gpl,
+			 __stop___ksymtab_unused_gpl,
+			 __start___kcrctab_unused_gpl);
 #endif
-	ksymtab[EXPORT_TYPE_GPL_FUTURE] = (struct ksymtab) {
-		__start___ksymtab_gpl_future, __start___kcrctab_gpl_future,
-		__stop___ksymtab_gpl_future - __start___ksymtab_gpl_future,
-	};
+	init_one_ksymtab(&ksymtab[EXPORT_TYPE_GPL_FUTURE],
+			 __start___ksymtab_gpl_future,
+			 __stop___ksymtab_gpl_future,
+			 __start___kcrctab_gpl_future);
 
 	return 0;
 }

[PATCH 08/10] lib: bsearch - remove redundant special case for arrays of size 0

[Alan Jenkins]

> On Thu, 24 Sep 2009, Rusty Russell wrote:
>
>> The if (num == 0) line is superfluous.

On 9/27/09, Tim Abbott <tabbott@ksplice.com> wrote:
>
> You are quite right.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 lib/bsearch.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index 4297c98..2e70664 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -34,8 +34,6 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt))
 {
 	int start = 0, end = num - 1, mid, result;
-	if (num == 0)
-		return NULL;
 
 	while (start <= end) {
 		mid = (start + end) / 2;
-- 
1.6.3.2