Re: [PATCH 3/3] kallsyms: delta-compress lineinfo tables for ~2.7x size reduction

[Sasha Levin <sashal@kernel.org>]

On Thu, Mar 12, 2026 at 10:03:55AM +0800, Vivian Wang wrote:
>Hi Sasha,
>
>On 3/11/26 22:49, Sasha Levin wrote:
>> Thanks for the review!
>>
>> On Wed, Mar 11, 2026 at 11:34:24AM +0800, Vivian Wang wrote:
>>> Hi Sasha,
>>>
>>> I've been trying this out and AFAICT this does work perfectly. Thank you
>>> for this.
>>>
>>> There are a few oddities I found:
>>>
>>> Firstly I've been building with something like O=_riscv out of
>>> convenience, and the file names have an extra ../ in the front. (This is
>>> just me exiting out of init=/bin/sh.) 
>>> [    2.317268] Kernel panic - not syncing: Attempted to kill init! exitcode=0x00000000
>>> [    2.320283] CPU: 0 UID: 0 PID: 1 Comm: sh Not tainted 7.0.0-rc3-00004-g8ad18f1a1a2f #31 PREEMPTLAZY
>>> [    2.322048] Hardware name: riscv-virtio,qemu (DT)
>>> [    2.323220] Call Trace:
>>> [    2.324465] [<ffffffff800172a8>] dump_backtrace+0x1c/0x24 (../arch/riscv/kernel/stacktrace.c:150)
>>> [    2.329061] [<ffffffff8000241e>] show_stack+0x2a/0x34 (../arch/riscv/kernel/stacktrace.c:156)
>>> [    2.330334] [<ffffffff8000fe32>] dump_stack_lvl+0x4a/0x68 (../lib/dump_stack.c:122)
>>> [    2.331462] [<ffffffff8000fe64>] dump_stack+0x14/0x1c (../lib/dump_stack.c:130)
>>> [    2.332571] [<ffffffff80002a88>] vpanic+0x108/0x2bc (../kernel/panic.c:651)
>>> [    2.333674] [<ffffffff80002c6e>] panic+0x32/0x34 (../kernel/panic.c:787)
>>> [    2.334427] [<ffffffff8002e97a>] do_exit+0x7ee/0x7f4 (../kernel/exit.c:930)
>>> [    2.335194] [<ffffffff8002eade>] do_group_exit+0x1a/0x88 (../kernel/exit.c:1099)
>>> [    2.335945] [<ffffffff8002eb62>] __riscv_sys_exit_group+0x16/0x18 (../kernel/exit.c:1129)
>>> [    2.336763] [<ffffffff80b3e868>] do_trap_ecall_u+0x260/0x45c (../arch/riscv/include/asm/syscall.h:112)
>>> [    2.337765] [<ffffffff80b4c034>] handle_exception+0x168/0x174 (../arch/riscv/kernel/entry.S:233)
>>> This is fine by me, but I've seen mentions of O= builds but I'm not sure
>>> if it's expected.
>>
>> Could you try v2 and see if it makes it prettier? I tried to tackle
>> this :)
>
>Thanks, I'll try it out and see.
>
>>
>>> Also, toggling CONFIG_KALLSYMS_LINEINFO seems to rebuild every single
>>> file. I haven't debugged why, but is this expected?
>>
>> I think that this is because we increase KSYM_SYMBOL_LEN when lineinfo is
>> enabled. I suppose we can just increase the size irregardless of whether
>> lineinfo is enabled and ignore the waste?
>>
>> Or, folks really won't be toggling this option too often for the
>> rebuilds to
>> matter too much, so we can just enjoy the savings? 
>
>Yeah I understand now. The size affects some fundamental headers.
>
>I just thought it was odd. The current situation is fine by me - if I'm
>building a kernel and toggling configs, it means I have the vmlinux file
>and can use scripts/decode_stacktrace.sh :)
>
>>> I have a few ideas about the code as well. Since this patch 3 touches
>>> most of the files involved, I'll just dump my thoughts on the whole
>>> series here. I want to note that I haven't read the RFC thread too
>>> carefully, but I don't think there were many comments on the
>>> implementation.
>>>
>>> On 3/4/26 02:21, Sasha Levin wrote:
>>>> Replace the flat uncompressed parallel arrays (lineinfo_addrs[],
>>>> lineinfo_file_ids[], lineinfo_lines[]) with a block-indexed,
>>>> delta-encoded, ULEB128 varint compressed format.
>>>>
>>>> The sorted address array has small deltas between consecutive entries
>>>> (typically 1-50 bytes), file IDs have high locality (delta often 0,
>>>> same file), and line numbers change slowly.  Delta-encoding followed
>>>> by ULEB128 varint compression shrinks most values from 4 bytes to 1.
>>>>
>>>> Entries are grouped into blocks of 64.  A small uncompressed block
>>>> index (first addr + byte offset per block) enables O(log(N/64)) binary
>>>> search, followed by sequential decode of at most 64 varints within the
>>>> matching block.  All decode state lives on the stack -- zero
>>>> allocations, still safe for NMI/panic context.
>>>>
>>>> Measured on a defconfig+debug x86_64 build (3,017,154 entries, 4,822
>>>> source files, 47,144 blocks):
>>>>
>>>>   Before (flat arrays):
>>>>     lineinfo_addrs[]    12,068,616 bytes (u32 x 3.0M)
>>>>     lineinfo_file_ids[]  6,034,308 bytes (u16 x 3.0M)
>>>>     lineinfo_lines[]    12,068,616 bytes (u32 x 3.0M)
>>>>     Total:              30,171,540 bytes (28.8 MiB, 10.0 bytes/entry)
>>>>
>>>>   After (block-indexed delta + ULEB128):
>>>>     lineinfo_block_addrs[]    188,576 bytes (184 KiB)
>>>>     lineinfo_block_offsets[]  188,576 bytes (184 KiB)
>>>>     lineinfo_data[]        10,926,128 bytes (10.4 MiB)
>>>>     Total:                 11,303,280 bytes (10.8 MiB, 3.7 bytes/entry)
>>>>
>>>>   Savings: 18.0 MiB (2.7x reduction)
>>>>
>>>> Booted in QEMU and verified with SysRq-l that annotations still work:
>>>>
>>>>   default_idle+0x9/0x10 (arch/x86/kernel/process.c:767)
>>>>   default_idle_call+0x6c/0xb0 (kernel/sched/idle.c:122)
>>>>   do_idle+0x335/0x490 (kernel/sched/idle.c:191)
>>>>   cpu_startup_entry+0x4e/0x60 (kernel/sched/idle.c:429)
>>>>   rest_init+0x1aa/0x1b0 (init/main.c:760)
>>>>
>>>> Suggested-by: Juergen Gross <jgross@suse.com>
>>>> Assisted-by: Claude:claude-opus-4-6
>>>> Signed-off-by: Sasha Levin <sashal@kernel.org>
>>>> ---
>>>>  .../admin-guide/kallsyms-lineinfo.rst         |   7 +-
>>>>  include/linux/mod_lineinfo.h                  | 103 ++++++++--
>>>>  init/Kconfig                                  |   8 +-
>>>>  kernel/kallsyms.c                             |  91 +++++++--
>>>>  kernel/kallsyms_internal.h                    |   7 +-
>>>>  kernel/module/kallsyms.c                      | 107 +++++++---
>>>>  scripts/gen_lineinfo.c                        | 192 ++++++++++++++----
>>>>  scripts/kallsyms.c                            |   7 +-
>>>>  scripts/link-vmlinux.sh                       |  16 +-
>>>>  9 files changed, 423 insertions(+), 115 deletions(-)
>>>>
>>>> diff --git a/Documentation/admin-guide/kallsyms-lineinfo.rst b/Documentation/admin-guide/kallsyms-lineinfo.rst
>>>> index 21450569d5324..fe92c5dde16b3 100644
>>>> --- a/Documentation/admin-guide/kallsyms-lineinfo.rst
>>>> +++ b/Documentation/admin-guide/kallsyms-lineinfo.rst
>>>> @@ -76,10 +76,11 @@ Memory Overhead
>>>>  ===============
>>>>
>>>>  The vmlinux lineinfo tables are stored in ``.rodata`` and typically add
>>>> -approximately 44 MiB to the kernel image for a standard configuration
>>>> -(~4.6 million DWARF line entries, ~10 bytes per entry after deduplication).
>>>> +approximately 10-15 MiB to the kernel image for a standard configuration
>>>> +(~4.6 million DWARF line entries, ~2-3 bytes per entry after delta
>>>> +compression).
>>>>
>>>> -Per-module lineinfo adds approximately 10 bytes per DWARF line entry to each
>>>> +Per-module lineinfo adds approximately 2-3 bytes per DWARF line entry to each
>>>>  ``.ko`` file.
>>>
>>> Maybe this could be given in terms of percentages? It wasn't obvious to
>>> me what 10-15 MiB amounts to.
>>>
>>> On riscv64, I'm seeing a 24.2 MiB to 30.2 MiB increase in
>>> arch/riscv/boot/Image size on an approximately defconfig+mod2noconfig
>>> build, which is about a 25% increase. I haven't checked yet, but if 25%
>>> is similar to what other archs get, that's a more useful figure than
>>> 10-15 MiB, given that the size increase is correlated to the total
>>> amount of code linked into the kernel/module.
>>
>> I ended up giving an example instead of percentages because it seemed
>> to vary
>> wildly between configs and archs. For example, defconfig on x86 yields
>> a 15%
>> increase compared to the 25% you see with your config on riscv,
>> compared to a
>> 39% increase with defconfig on riscv. 
>
>That's fair. I guess it also depends on arch code density and compiler
>codegen.
>
>[...]
>
>>>> +/*
>>>> + * Read a ULEB128 varint from a byte stream.
>>>> + * Returns the decoded value and advances *pos past the encoded bytes.
>>>> + * If *pos would exceed 'end', returns 0 and sets *pos = end (safe for
>>>> + * NMI/panic context -- no crash, just a missed annotation).
>>>
>>> What does that last bit mean...?
>>
>> This goes back to your previous point about correctness and checks in the
>> lineinfo code :)
>>
>> It just means that this function never faults or allocates. On bad
>> input it
>> returns 0, so the worst case is a missing annotation, not a crash. 
>
>Ah, right, it didn't occur to me it was "annotation" as in the lineinfo
>annotation in the stack trace. I thought it was something like noinstr
>or lockdep stuff at first. This checks out.

Thanks again for the review! I'll send a v3 :)

-- 
Thanks,
Sasha