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

[bot+bpf-ci@kernel.org]

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

> kallsyms: Match compressed tokens on the fly during binary search
>
> kallsyms_lookup_names() runs a binary search across ~184k tokenized
> (compressed) 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 tokenized symbols 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.  Even sorting the token table alphabetically
> wouldn't help; "bpf_" and "bpf_foo_" do not *have* a determinative
> sorting order, because the suffixes following those tokens would
> matter.
>
> However, full string expansion at every step is equally wasteful: of
> the ~17 strcmps in the binary search, only the last needs to check
> all N chars in both strings, earlier steps will know +/- outcome at
> char 0,1,2..N-1.
>
> However, full string expansion at every step is equally wasteful: of
> the ~17 strcmp()s in the binary search, only the final matching step
> needs to test all characters.  Earlier non-matching steps diverge at
> the first differing character (0..N-1), but the baseline expands every
> candidate symbol to the stack unconditionally, before comparing.

Does the commit message have the same paragraph twice?  Both start with
"However, full string expansion at every step is equally wasteful" and
make the same point about wasteful expansion. The first version uses
rough phrasing ("strcmps", "+/- outcome at char 0,1,2..N-1"), while the
second version is more polished ("strcmp()s", "diverge at the first
differing character"). Having two paragraphs in a row starting with
"However," also makes the rationale harder to follow.

Should one of the paragraphs be removed, probably the first one since the
second is clearer?


---
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/36651779347