kallsyms: optimise symbol search by name
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v4 Latest13 patches 2 repliesIn review
- v313 patches 10 repliesSuperseded
- v215 patches 7 repliesSuperseded
Earlier versions · 1
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v1 | 2 patches | 2 replies | Superseded |
Patches in v4 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/13 | scripts/kallsyms: Avoid overrunning on-stack bufferscripts/ | +1 | 0 replies | |
| 2/13 | scripts/kallsyms: Improve error reportingscripts/ | +91 | 0 replies | |
| 3/13 | scripts/elf-parse: add elf_map_big_endian() helperscripts/ scripts/ | +10 | 0 replies | |
| 4/13 | scripts/kallsyms: make use of binary data output optionalscripts/ scripts/ scripts/ +1 more | +197 | 0 replies | |
| 5/13 | kallsyms: Fix selftest startup delaykernel/ | +3 | 1 reply | |
| 6/13 | kallsyms: Improve selftest test_perf_kallsyms_lookup_name() outputkernel/ | +127 | 0 replies | |
| 7/13 | kallsyms: Match compressed tokens on the fly during binary searchkernel/ | +59 | 0 replies | |
| 8/13 | kallsyms: Optimise symbol name searchkernel/ kernel/ scripts/ | +148 | 0 replies | |
| 9/13 | kallsyms: Add a kernel parameter to change the kallsyms_markers[] densityinit/ kernel/ kernel/ +2 more | +70 | 0 replies | |
| 10/13 | scripts/kallsyms: Keep full expansion of tokensscripts/ | +88 | 0 replies | |
| 11/13 | scripts/kallsyms: Optimise compress_symbols()scripts/ | +105 | 0 replies | |
| 12/13 | scripts/kallsyms: Reuse tokens that have no referencesscripts/ | +57 | 0 replies | |
| 13/13 | scripts/kallsyms: Reuse little-used compression tokensscripts/ | +272 | 1 reply |
Reviews trailers per patch
1 of 13 patches has a Reviewed-by or Acked-by.
| Patch | Samuel Wu |
|---|---|
| 1/13 | |
| 2/13 | |
| 3/13 | |
| 4/13 | |
| 5/13 | |
| 6/13 | |
| 7/13 | R-b |
| 8/13 | |
| 9/13 | |
| 10/13 | |
| 11/13 | |
| 12/13 | |
| 13/13 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v4 next 00/13] kallsyms: optimise symbol search by name
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.
v4 is pretty much the same as v3. It contains a couple of fixes from sashiko and bot+bpf+ci that fix the compression output for BE on BE and for kernels over 1GB and a few less important minor changes.
The biggest change is the addition of some extra consistency tests at the end of the compression code.
The kernel code is really unchanged since v2.
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. I've deleted a duplicate paragraph from the commit message. 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 | 1035 ++++++++++++++++++++++++++---------- scripts/kallsyms.h | 1 + scripts/link-vmlinux.sh | 13 +- 10 files changed, 1104 insertions(+), 426 deletions(-)
Signature · 1 line
2.39.5