module: Speed up symbol resolution during module loading (using binary search)
Subsystems (5)
cover module: Speed up symbol resolution during module loading (using binary search)
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 1/10 ARM: use unified discard definition in linker script
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.]
Acked-by-without-testing: Tejun Heo <[email protected]>
--- arch/arm/kernel/vmlinux.lds.S | 13 ++++++++----- 1 files changed, 8 insertions(+), 5 deletions(-)
arch/arm/kernel/vmlinux.lds.S +8 -5
@@ -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 } /*
Signature · 1 line
1.6.3.3
PATCH 2/10 ARM: unexport symbols used to implement floating point emulation
In reply to Alan JenkinsThe 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/
--- arch/arm/kernel/armksyms.c | 20 -------------------- 1 files changed, 0 insertions(+), 20 deletions(-)
arch/arm/kernel/armksyms.c +0 -20
@@ -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);
Signature · 1 line
1.6.3.3
PATCH 3/10 module: make MODULE_SYMBOL_PREFIX into a CONFIG option
In reply to Alan JenkinsThe 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).
--- 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(-)
arch/blackfin/Kconfig +4 -0
@@ -5,6 +5,10 @@ mainmenu "Blackfin Kernel Configuration" +config SYMBOL_PREFIX + string + default "_" + config MMU def_bool n
arch/blackfin/include/asm/module.h +0 -2
@@ -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
arch/blackfin/kernel/vmlinux.lds.S +0 -2
@@ -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>
arch/h8300/Kconfig +4 -0
@@ -10,6 +10,10 @@ config H8300 default y select HAVE_IDE +config SYMBOL_PREFIX + string + default "_" + config MMU bool default n
arch/h8300/include/asm/module.h +0 -2
@@ -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 */
arch/h8300/kernel/vmlinux.lds.S +0 -1
@@ -1,4 +1,3 @@ -#define VMLINUX_SYMBOL(_sym_) _##_sym_ #include <asm-generic/vmlinux.lds.h> #include <asm/page.h>
include/asm-generic/vmlinux.lds.h +6 -2
@@ -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. */
include/linux/module.h +4 -2
@@ -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
scripts/Makefile.lib +5 -0
@@ -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 '/').
scripts/mod/Makefile +1 -1
@@ -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)
scripts/mod/mk_elfconfig.c +0 -9
@@ -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 ; }
scripts/mod/modpost.c +9 -0
@@ -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) */
Signature · 1 line
1.6.3.3
PATCH 4/10 module: extract EXPORT_SYMBOL() from module.h into mod_export.h
In reply to Alan JenkinsThe 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__".
--- 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
include/linux/mod_export.h new file +75 -0
@@ -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 */
include/linux/module.h +1 -64
91 lines not on this page · raw message
Signature · 1 line
1.6.3.3
PATCH 5/10 kbuild: sort the list of symbols exported by the kernel (__ksymtab)
In reply to Alan Jenkinsmodpost 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.
--- 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(-)
Makefile +18 -6
@@ -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
include/asm-generic/vmlinux.lds.h +28 -11
@@ -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) \ }/**
include/linux/mod_export.h +79 -5
112 lines not on this page · raw message
init/Kconfig +5 -0
@@ -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
scripts/Makefile.modpost +1 -1
@@ -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)
scripts/mod/modpost.c +62 -1
105 lines not on this page · raw message
Signature · 1 line
1.6.3.3
PATCH 6/10 module: refactor symbol tables and try to reduce code size of each_symbol()
In reply to Alan Jenkinsfind_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.
--- include/linux/module.h | 102 +++++++++++++-------- kernel/module.c | 241 ++++++++++++++++++++++++------------------------ 2 files changed, 183 insertions(+), 160 deletions(-)
include/linux/module.h +64 -38
@@ -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 modulestruct 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. */
kernel/module.c +119 -122
346 lines not on this page · raw message
Signature · 1 line
1.6.3.3
PATCH 7/10 lib: Add generic binary search function to the kernel.
In reply to Alan JenkinsFrom: Tim Abbott <[email protected]>
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.
--- 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
include/linux/bsearch.h new file +9 -0
@@ -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 */
lib/Makefile +1 -1
@@ -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
lib/bsearch.c new file +53 -0
53 lines not on this page · raw message
Signature · 1 line
1.6.3.3
PATCH 8/10 lib: bsearch - remove redundant special case for arrays of size 0
In reply to Alan JenkinsQuoted 3 lines · Rusty Russell
Quoted 2 lines
The if (num == 0) line is superfluous.
Quoted 2 lines · Tim Abbott
You are quite right.
--- lib/bsearch.c | 2 -- 1 files changed, 0 insertions(+), 2 deletions(-)
lib/bsearch.c +0 -2
@@ -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 ;
Signature · 1 line
1.6.3.3
PATCH 9/10 module: speed up find_symbol() using binary search on the builtin symbol tables
In reply to Alan JenkinsThe 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.
--- kernel/module.c | 144 ++++++++++++++++++++++++++++++++++-------------------- 1 files changed, 91 insertions(+), 53 deletions(-)
kernel/module.c +91 -53
@@ -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);
Signature · 1 line
1.6.3.3
PATCH 10/10 module: fix is_exported() to return true for all types of exports
In reply to 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.
--- kernel/module.c | 30 ++++++++---------------------- 1 files changed, 8 insertions(+), 22 deletions(-)
kernel/module.c +8 -22
@@ -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 */
Signature · 1 line
1.6.3.3
Re: [PATCH 10/10] module: fix is_exported() to return true for all types of exports
Quoted 3 lines · Alan Jenkins
/proc/kallsymsannotates module symbols as global (e.g. 'D' for a data symbol) or local (e.g. 'd'), depending on whetheris_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)’)
kernel/module.c +35 -20
@@ -194,30 +194,45 @@ extern const unsigned long __start___kcrstatic 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 ; }