[PATCH v3 next 00/13] kallsyms: optimise symbol search by name

[David Laight <david.laight.linux@gmail.com>]

These patches speed up the lookup of symbol names by a factor of about 18
while both reducing the size of the compressed data by 9.5% (for my kernel)
and speeding up the compression code itself.
As well as improving the normal symbol lookup, looking up symbols that occur
a lot of times is also massively improved.

The technical content of these patches is the same as v2 except for an
additional compression optimisation in the final patch.
However rebasing onto 7.4-rc1 took some effort due to changes to
sripts/kallsyms.c.

Patch 1 is a stack buffer overrun - but in a program run during the build
    so is isn't that improtant.
Patch 2 improves the error reporting added for 7.4-rc1 and adds some timestamp
    output to time the different parts of the code.
Patch 3 obtains the target endianness from the elf file.
    Being run-time doesn't make any significant difference.
    (v2 extracted it from the kernel makefile.)
Patch 4 is, in some sense, a conditional revert of 83da9f3197e5 (output binary
    data speed output and kallsyms assembly).
    While the binary output does speed things up it makes debugging impossible.
    Change it to be a command line option.
    - Output the token table first and always in text - it is small.
    - Use a fixed format and fwrite() for the symbol values avoid printf.
      Reduces the time to output the symbol table from 5.8ms to 2.1ms
      (on my system, with my kernel, today).
    - The marker array is now written to bin.out in host order.
    Contains some of the changes from patch 14, but the size of the out.S
    file matters less.
Patch 5 (formally #2) is a fix to the selftest.
Patch 6 (formally #3) is a big update to the selftest output to make
    it less affected by interrupts (etc) and visually more obvious.
    Includes a very long symbol to check their handling.
The old patch 4 (error reporting) is merged elsewhere.
Patch 7 (formally #5) is from Jim Cromie and optimises the name compare.
    I think this is the final version of his patch, but any one will do.
    The following patches are built on top of it.
Patches 8 (merged #6 and #7) improve the search by name code.
    Indexing the list of names (not the values) speeds it up ~12 times.
    Marking duplicate symbols improves things as well, especially for
    symbols that appear 1000s of times.
Patches 9 (merged #8 and #9) make the 'marker density' a kernel build option
    and changes the default from 1:256 to 1:64 (one bit for two symbols).
    This change gives a 33% improvement on top of that from patch 8.
The old patch 10 is dropped.
Patch 10 (technically the same as 11, but rewritten) avoids the recursive
    expansion of compressed data. It speeds up the compression phase
    by about 17ms in 100ms.
Patch 11 (formally #12) speeds up the compression code by about 35ms
    in 100ms, it will be more for kernels with a lot of long symbol names.
Patch 12 (formally #13) reuses unused compression tokens to improve
    the compression ratio.
    (Patch 11 means they don't have to be kept to expand tokens.)
The old patch 14 is dropped, some parts went into patch 3.
Patch 13 (formally #15) improves the compression ratio by splitting little
    used tokens so that they can be used for more common token pairs.
    For v3 this includes tokens for three single characters as well
    as those where both the original tokens are still valid.
    This improves the compression ratio (for the test kernel) from 53.35%
    to 50.05%, so a 6% reduction in the datasize.

Some test output (TL;DR):

Timestamps from scrpts/kallsyms (typical values - they vary between runs):
Initial (7.4-rc1 with part of patch 4 applied):
kallsyms: stamp read elf 29.6 ms
kallsyms: stamp shrink table 0.1 ms
kallsyms: stamp sort symbols 2.2 ms
kallsyms: stamp build initial token table 10.9 ms
kallsyms: stamp insert real symbols in table 1.9 ms
kallsyms: stamp optimize result 109.5 ms
kallsyms: stamp write compressed names 11.3 ms
kallsyms: stamp write token table 0.0 ms
kallsyms: stamp write symbol values 5.8 ms
kallsyms: stamp sort by name 18.8 ms
kallsyms: stamp write name index 1.7 ms

Patch 4 (make binary data optional) changes:
kallsyms: stamp write compressed names 12.6 ms   +1.5ms
kallsyms: stamp write symbol values 2.1 ms       -3.8ms
The +1.5 comes from logic changes, the -3.8 by using fwrite() not printf().
(The all-text output is 50+ms slower overall.)

Patch 10 (fully expand tokens) changes:
kallsyms: stamp optimize result 98.2 ms           -15ms
kallsyms: stamp write compressed names 10.1 ms     -2ms 
The changes from removing the number of short memcpy() and (probably)
changing the argument to compress_symbols() from 'char *' to int.
(In fact replacing memcpy() by a byte copy loop saves ~1ms.)

Patch 11 (Optimise compress symbols) is the big one:
kallsyms: stamp optimize result 64.5 ms           -34ms
In effect that reduces the compression from O(n^2) to O(n) in the
length of the symbol.

Patches 12 and 13 find more things to compress and make
it ~13ms slower.

One obvious change that would improve things would be to throw some
(more) extra memory at the symbol table and keep the original symbol
name. That would remove all the calls to expand_symbol() and make
the loop that outputs the compressed symbols trivial.
Potentially it would let the 'sort by name' be done be a separate thread.
I didn't look at why 'read elf' takes ~30ms, nor have I timed the
old code from 7.3.

kallsyms_selftest output (run in a userspace wrapper).
(Unchanged from v2, but the kernel code changes are minimal.)
The results are comparable to each other, but the in-kernel results
seem to be faster (possibly due to optimisation choices for functions
like memcpy().

Performance changes
The average value is a much better indication of speed than the
fastest (usually the middle of the table).
The slow times are likely to be worse than the figures imply, the tests
take long enough that the cpu clock frequency is likely to increase.

The times go down from:
kallsyms_lookup_name() looked up 123312 symbols, average 3753 ns
	fastest 341 ns (bpf_get_netns_cookie_sock_ops_proto)
	slowest 78069 ns (__func__.0)

to:
kallsyms_lookup_name() looked up 123312 symbols, average 204 ns
	fastest 60 ns (_rs.0)
	slowest 802 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)

Baseline (based  on 7.3.0-rc4):
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7507638 ns
kallsyms_on_each_match_symbol() traverse all: 9418 ns
kallsyms_lookup_name() looked up 123312 symbols, average 3753 ns
	fastest 341 ns (bpf_get_netns_cookie_sock_ops_proto)
	slowest 78069 ns (__func__.0)
	Distribution, 1280ns per column, 8714 counts per *:
	|  *
	|  *
	|  *
	|  *
	|  **
	| ***
	| ***
	|************ ****************                 ***************

After 'Match compressed tokens on the fly during binary search'.
This doesn't make much difference (yet) because the linear scan dominates.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7521035 ns
kallsyms_on_each_match_symbol() traverse all: 7986 ns
kallsyms_lookup_name() looked up 123312 symbols, average 3661 ns
	fastest 411 ns (pciehp_poll_mode)
	slowest 76677 ns (__func__.0)
	Distribution, 1280ns per column, 8759 counts per *:
	|  *
	|  *
	|  *
	|  *
	|  *
	| ***
	| ***
	|******** *  *   **    **   **                            ***

After 'Optimise symbol name search'.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7547445 ns
kallsyms_on_each_match_symbol() traverse all: 1733 ns
kallsyms_lookup_name() looked up 123312 symbols, average 377 ns
	fastest 90 ns (pkcs1pad_create)
	slowest 4578 ns (io_register_clone_buffers)
	Distribution, 80ns per column, 3494 counts per *:
	|   ***
	|   ***
	|   ***
	|  *****
	|  *****
	|  *****
	|  ******
	| *******************           ***        *              *

After 'Optimise detection of duplicate symbol names'
marker density 256:
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7620445 ns
kallsyms_on_each_match_symbol() traverse all: 2976 ns
kallsyms_lookup_name() looked up 123312 symbols, average 336 ns
	fastest 90 ns (shmem_unuse)
	slowest 2044 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 40ns per column, 1912 counts per *:
	|      *****
	|     *******
	|    ********
	|    *********
	|    *********
	|    *********
	|   ***********
	|  ******************                               *
(That 'slowest' time looks like a lie.)

With the marker denstity reduced to 64
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7654179 ns
kallsyms_on_each_match_symbol() traverse all: 2405 ns
kallsyms_lookup_name() looked up 123312 symbols, average 204 ns
	fastest 60 ns (_rs.0)
	slowest 802 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 20ns per column, 2783 counts per *:
	|         **
	|        ****
	|        ****
	|        *****
	|       ******
	|       *******
	|      *********
	|   **********************               *

After 'Reuse tokens that have no references'.
Improves the compressions ratio slightly.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1575323   |      2969490  |  53.05   |
 ---------------------------------------------------------
kernel code unchanged.

Final version.
Improves the compression ratio again.
(the v3 version is slightly better - 50.05%)
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1505184   |      2969490  |  50.68   |
 ---------------------------------------------------------
kernel code unchanged again.


David Laight (12):
  scripts/kallsyms: Avoid overrunning on-stack buffer
  scripts/kallsyms: Improve error reporting
  scripts/elf-parse: add elf_map_big_endian() helper
  scripts/kallsyms: make use of binary data output optional
  kallsyms: Fix selftest startup delay
  kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output
  kallsyms: Optimise symbol name search
  kallsyms: Add a kernel parameter to change the kallsyms_markers[]
    density
  scripts/kallsyms: Keep full expansion of tokens
  scripts/kallsyms: Optimise compress_symbols()
  scripts/kallsyms: Reuse tokens that have no references
  scripts/kallsyms: Reuse little-used compression tokens

Jim Cromie (1):
  kallsyms: Match compressed tokens on the fly during binary search

 init/Kconfig               |  19 +
 kernel/kallsyms.c          | 262 ++++++----
 kernel/kallsyms_internal.h |   8 +-
 kernel/kallsyms_selftest.c | 173 +++++--
 scripts/elf-parse.c        |  13 +-
 scripts/elf-parse.h        |   5 +-
 scripts/kallsyms-sysmap.c  |   1 +
 scripts/kallsyms.c         | 957 ++++++++++++++++++++++++++-----------
 scripts/kallsyms.h         |   1 +
 scripts/link-vmlinux.sh    |  13 +-
 10 files changed, 1034 insertions(+), 418 deletions(-)

-- 
2.39.5