linux-kernel - Re: [PATCH 0/4] Speed up the symbols' resolution process V4

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

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

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

Date:	Wed, 27 Apr 2011 17:31:14 +0200
From:	Dirk Behme <dirk.behme@...glemail.com>
To:	Alessio Igor Bogani <abogani@...nel.org>
CC:	Rusty Russell <rusty@...tcorp.com.au>,
	Tim Abbott <tabbott@...lice.com>,
	Anders Kaseorg <andersk@...lice.com>,
	Jason Wessel <jason.wessel@...driver.com>,
	Tim Bird <tim.bird@...sony.com>,
	LKML <linux-kernel@...r.kernel.org>,
	Linux Embedded <linux-embedded@...r.kernel.org>
Subject: Re: [PATCH 0/4] Speed up the symbols' resolution process V4

On 16.04.2011 15:26, Alessio Igor Bogani wrote:
> The intent of this patch is to speed up the symbols resolution process.
>
> This objective is achieved by sorting all ksymtab* and kcrctab* symbols
> (those which reside both in the kernel and in the modules) and thus use the
> fast binary search.
>
> To avoid adding lots of code for symbols sorting I rely on the linker which can
> easily do the job thanks to a little trick. The trick isn't really beautiful to
> see but permits minimal changes to the code and build process. Indeed the patch
> is very simple and short.
>
> In the first place I changed the code for place every symbol in a different
> section (for example: "___ksymtab" sec "__" #sym) at compile time (this the
> above mentioned trick!). Thus I request to the linker to sort and merge all
> these sections into the appropriate ones (for example: "__ksymtab") at link
> time using the linker scripts. Once all symbols are sorted we can use binary
> search instead of the linear one.
>
> I'm fairly sure that this is a good speed improvement even though I haven't
> made any comprehensive benchmarking (but follow a simple one). In any case
> I would be very happy to receive suggestions about how made it. Collaterally,
> the boot time should be reduced also (proportionally to the number of modules
> and symbols nvolved at boot stage).
>
> I hope that you find that interesting!
>
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Thanks to Ian Lance Taylor for help about how the linker works.
>
>
> Changes since V3:
> *) Please ignore this version completely
>
> Changes since V2:
> *) Fix a bug in each_symbol() semantics by Anders Kaseorg
> *) Split the work in three patches as requested by Rusty Russell
> *) Add a generic binary search implementation made by Tim Abbott
> *) Remove CONFIG_SYMBOLS_BSEARCH kernel option
>
> Changes since V1:
> *) Merge all patches into only one
> *) Remove few useless things
> *) Introduce CONFIG_SYMBOLS_BSEARCH kernel option
>
>
> Alessio Igor Bogani (3):
>    module: Restructure each_symbol() code
>    module: Sort exported symbols
>    module: Use the binary search for symbols resolution
>
> Tim Abbott (1):
>    lib: Add generic binary search function to the kernel.
>
>   include/asm-generic/vmlinux.lds.h |   20 ++++----
>   include/linux/bsearch.h           |    9 ++++
>   include/linux/module.h            |    4 +-
>   kernel/module.c                   |   84 ++++++++++++++++++++++++++++---------
>   lib/Makefile                      |    3 +-
>   lib/bsearch.c                     |   53 +++++++++++++++++++++++
>   scripts/module-common.lds         |   11 +++++
>   7 files changed, 151 insertions(+), 33 deletions(-)
>   create mode 100644 include/linux/bsearch.h
>   create mode 100644 lib/bsearch.c

Tested-by: Dirk Behme <dirk.behme@...glemail.com>

On an embedded ARM system insmoding a large number of modules the 
overall module load time is improved up to ~1s. Great! :)

It would be nice to get these patches into mainline asap.

Many thanks

Dirk



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