Re: [PATCH v5 1/3] kallsyms: Match compressed tokens on the fly during binary search

[bot+bpf-ci@kernel.org]

[-- Attachment #1: Type: text/plain, Size: 2163 bytes --]

> kallsyms: Match compressed tokens on the fly during binary search
>
> kallsyms_lookup_names() runs a binary search across kallsyms_names[],
> a packed array of ~130k encoded kernel symbols.  For each of the ~17
> comparisons in the search, it currently decompresses the candidate
> symbol into a temporary buffer on the stack before calling strcmp().
>
> Comparing raw tokens directly in compressed space is impossible.  The
> BPE token table assigns values by frequency, not alphabetical order
> (e.g. token 0x05 might expand to "zebra" while 0x42 expands to "apple"),
> so comparing raw token values scrambles lexicographical order.
>
> However, full string expansion is equally wasteful: roughly 16 of the
> 17 binary search steps fail within the first two characters.
>
> Introduce kallsyms_strcmp_symbol() to compare ASCII queries against
> compressed tokens on the fly.  It walks kallsyms_token_index and
> kallsyms_token_table incrementally, matching characters directly and
> bailing out on the first character mismatch without expanding subsequent
> tokens.
>
> This optimization:
>
> 0. Avoids decompressing non-matching tokens, short-circuiting ~94% of
>    binary search character expansions without adding any tables in
>    .rodata.
>
> 1. Drops the 512-byte namebuf buffer from the kernel stack in
>    kallsyms_lookup_names().
>
> 2. Cuts unindexed lookup latency by ~530 ns (~14% faster) while leaving
>    sequential address ordering and kallsyms_expand_symbol() streaming
>    invariants intact for /proc/kallsyms and table walks.

This isn't a bug, but could the changelog say how the ~530 ns and ~14%
numbers were measured, such as which selftest and roughly how many
symbols? The ~94% figure seems to come from the 16-of-17 binary search
steps estimate mentioned earlier, which is a share of comparisons rather
than character expansions. Could that be reworded to match what it seems
to come from?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/36204745600