linux-kernel - RE: [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup symbols

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:   Sat, 29 Oct 2022 12:49:17 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     "'Leizhen (ThunderTown)'" <thunder.leizhen@...wei.com>,
        Luis Chamberlain <mcgrof@...nel.org>
CC:     Josh Poimboeuf <jpoimboe@...nel.org>,
        Jiri Kosina <jikos@...nel.org>,
        Miroslav Benes <mbenes@...e.cz>,
        Petr Mladek <pmladek@...e.com>,
        Joe Lawrence <joe.lawrence@...hat.com>,
        "live-patching@...r.kernel.org" <live-patching@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Masahiro Yamada <masahiroy@...nel.org>,
        Alexei Starovoitov <ast@...nel.org>,
        Jiri Olsa <jolsa@...nel.org>,
        Kees Cook <keescook@...omium.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        "linux-modules@...r.kernel.org" <linux-modules@...r.kernel.org>,
        "Steven Rostedt" <rostedt@...dmis.org>,
        Ingo Molnar <mingo@...hat.com>
Subject: RE: [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup
 symbols

> >> On 2022/10/27 3:03, Luis Chamberlain wrote:
> >>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
> >>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
> >>>>> This answers how we don't use a hash table, the question was *should* we
> >>>>> use one?

(Probably brainfart) thought...

Is the current table (effectively) a sorted list of strings?
So the lookup is a binary chop - so O(log(n)).

But your hashes are having 'trouble' stopping one chain
being very long?
So a linear search of that hash chain is slow.
In fact that sort of hashed lookup in O(n).

What if the symbols were sorted by hash then name?
(Without putting the hash into each entry.)
Then the code could do a binary chop search over
the symbols with the same hash value.
The additional data is then an array of symbol numbers
indexed by the hash - 32 bits for each bucket.

If the hash table has 0x1000 entries it saves 12 compares.
(All of which are likely to be data cache misses.)

If you add the hash to each table entry then you can do
a binary chop search for the hash itself.
While this is the same search as is done for the strings
the comparison (just a number) will be faster than a
string compare.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)