From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 21F44382F02; Thu, 12 Mar 2026 03:07:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773284827; cv=none; b=UIrwU4Rsblj/NnzQ2W1YQZuTOCcvECwE3abbivgwPBVFKXXd73BTQkw0Pk/yBgwz9rVPQOPPX5sUPf+uM7x6gR9/LsgXKTT4/mf4Kd8p7zFJGqEsZ5AHoPq4zpznkp0TWN+HqEexSZnF4cmSH1avaZIvAkgXQiAYvdYR74FKxEE= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773284827; c=relaxed/simple; bh=vVHMMNgZWZWlOVIKgdTPTTdGZCuONoISAYzGWqHCfEc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=h4Jnum4H77pGuwH71GA37zOkZOR0NalDeInhMq7s3RH1CofX8eYHdan2TjNGUxQtBufIdvSLbVuaWFY6nkyMaiGq9Z6LtpbzaP/XRZMFVwCOzrEQb0AC5VF1APe2/SGpsY+6bZQwcXPJOCRDv7gbYa4fRQ4gYodlvYRHlVvDLes= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=PT78vk7j; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="PT78vk7j" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 04FD9C19421; Thu, 12 Mar 2026 03:07:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1773284826; bh=vVHMMNgZWZWlOVIKgdTPTTdGZCuONoISAYzGWqHCfEc=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=PT78vk7jR+CFNnlYMiZUsEcbZcgHiJ+FLbAqwkrUE0GXDOrapy0RVF60gCzsCa+De VRhhThJP38Pm0WEkNXYrx5tajWTo/n6R5uQ+WS2KKp+KaPglQQfBeM7OiPpUpI9RU1 K2PO9izqhScAEynKjJ4U/hWDCoeokCNDC/G3Ql9AFHqdEXttP46wWME/AYsswfPeed bTcI2016Rj8QIKpCCccQuI++x1vKO/likOuhHnwulpOVUcQfA5vXS5QBo3IkF2hkKU TLdxOHVBHYUKsrkwuMesUCZJPXt32HF/+zPrSU6MgGH8gRMg8fZmEk0GEiScolI30l 7nzwFsK5iAMSA== From: Sasha Levin To: Andrew Morton , Masahiro Yamada , Luis Chamberlain , Linus Torvalds , Richard Weinberger , Juergen Gross , Geert Uytterhoeven , James Bottomley Cc: Jonathan Corbet , Nathan Chancellor , Nicolas Schier , Petr Pavlu , Daniel Gomez , Greg KH , Petr Mladek , Steven Rostedt , Kees Cook , Peter Zijlstra , Thorsten Leemhuis , Vlastimil Babka , Helge Deller , Randy Dunlap , Laurent Pinchart , Vivian Wang , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, linux-modules@vger.kernel.org, linux-doc@vger.kernel.org, Sasha Levin Subject: [PATCH v3 3/4] kallsyms: delta-compress lineinfo tables for ~2.7x size reduction Date: Wed, 11 Mar 2026 23:06:47 -0400 Message-ID: <20260312030649.674699-4-sashal@kernel.org> X-Mailer: git-send-email 2.51.0 In-Reply-To: <20260312030649.674699-1-sashal@kernel.org> References: <20260312030649.674699-1-sashal@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 Assisted-by: Claude:claude-opus-4-6 Signed-off-by: Sasha Levin --- .../admin-guide/kallsyms-lineinfo.rst | 7 +- include/linux/mod_lineinfo.h | 227 ++++++++++++++++-- init/Kconfig | 8 +- kernel/kallsyms.c | 46 ++-- kernel/kallsyms_internal.h | 8 +- kernel/module/kallsyms.c | 77 +++--- scripts/empty_lineinfo.S | 20 +- scripts/gen_lineinfo.c | 189 +++++++++------ scripts/kallsyms.c | 7 +- 9 files changed, 400 insertions(+), 189 deletions(-) diff --git a/Documentation/admin-guide/kallsyms-lineinfo.rst b/Documentation/admin-guide/kallsyms-lineinfo.rst index 5cae995eb118e..dd264830c8d5b 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. Known Limitations diff --git a/include/linux/mod_lineinfo.h b/include/linux/mod_lineinfo.h index d62e9608f0f82..364e5d81fe5bb 100644 --- a/include/linux/mod_lineinfo.h +++ b/include/linux/mod_lineinfo.h @@ -8,13 +8,23 @@ * * Section layout (all values in target-native endianness): * - * struct mod_lineinfo_header (16 bytes) - * u32 addrs[num_entries] -- offsets from .text base, sorted - * u16 file_ids[num_entries] -- parallel to addrs - * <2-byte pad if num_entries is odd> - * u32 lines[num_entries] -- parallel to addrs + * struct mod_lineinfo_header + * u32 block_addrs[num_blocks] -- first addr per block, for binary search + * u32 block_offsets[num_blocks] -- byte offset into compressed data stream + * u8 data[data_size] -- LEB128 delta-compressed entries * u32 file_offsets[num_files] -- byte offset into filenames[] * char filenames[filenames_size] -- concatenated NUL-terminated strings + * + * Each sub-array is located by an explicit (offset, size) pair in the + * header, similar to a flattened devicetree. This makes bounds checking + * straightforward: validate offset + size <= section_size for each array. + * + * Compressed stream format (per block of LINEINFO_BLOCK_ENTRIES entries): + * Entry 0: file_id (ULEB128), line (ULEB128) + * addr is in block_addrs[] + * Entry 1..N: addr_delta (ULEB128), + * file_id_delta (SLEB128), + * line_delta (SLEB128) */ #ifndef _LINUX_MOD_LINEINFO_H #define _LINUX_MOD_LINEINFO_H @@ -25,44 +35,209 @@ #include typedef uint32_t u32; typedef uint16_t u16; +typedef uint8_t u8; #endif +#define LINEINFO_BLOCK_ENTRIES 64 + struct mod_lineinfo_header { u32 num_entries; + u32 num_blocks; u32 num_files; - u32 filenames_size; /* total bytes of concatenated filenames */ - u32 reserved; /* padding, must be 0 */ + u32 blocks_offset; /* offset to block_addrs[] from section start */ + u32 blocks_size; /* bytes: num_blocks * 2 * sizeof(u32) */ + u32 data_offset; /* offset to compressed stream */ + u32 data_size; /* bytes of compressed data */ + u32 files_offset; /* offset to file_offsets[] */ + u32 files_size; /* bytes: num_files * sizeof(u32) */ + u32 filenames_offset; + u32 filenames_size; + u32 reserved; /* must be 0 */ }; -/* Offset helpers: compute byte offset from start of section to each array */ +/* + * Descriptor for a lineinfo table, used by the shared lookup function. + * Callers populate this from either linker globals (vmlinux) or a + * validated mod_lineinfo_header (modules). + */ +struct lineinfo_table { + const u32 *blk_addrs; + const u32 *blk_offsets; + const u8 *data; + u32 data_size; + const u32 *file_offsets; + const char *filenames; + u32 num_entries; + u32 num_blocks; + u32 num_files; + u32 filenames_size; +}; -static inline u32 mod_lineinfo_addrs_off(void) +/* + * 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). + */ +static inline u32 lineinfo_read_uleb128(const u8 *data, u32 *pos, u32 end) { - return sizeof(struct mod_lineinfo_header); -} + u32 result = 0; + unsigned int shift = 0; -static inline u32 mod_lineinfo_file_ids_off(u32 num_entries) -{ - return mod_lineinfo_addrs_off() + num_entries * sizeof(u32); + while (*pos < end) { + u8 byte = data[*pos]; + (*pos)++; + result |= (u32)(byte & 0x7f) << shift; + if (!(byte & 0x80)) + return result; + shift += 7; + if (shift >= 32) { + /* Malformed: skip remaining continuation bytes */ + while (*pos < end && (data[*pos] & 0x80)) + (*pos)++; + if (*pos < end) + (*pos)++; + return result; + } + } + return result; } -static inline u32 mod_lineinfo_lines_off(u32 num_entries) +/* Read an SLEB128 varint. Same safety guarantees as above. */ +static inline int32_t lineinfo_read_sleb128(const u8 *data, u32 *pos, u32 end) { - /* u16 file_ids[] may need 2-byte padding to align lines[] to 4 bytes */ - u32 off = mod_lineinfo_file_ids_off(num_entries) + - num_entries * sizeof(u16); - return (off + 3) & ~3u; -} + int32_t result = 0; + unsigned int shift = 0; + u8 byte = 0; -static inline u32 mod_lineinfo_file_offsets_off(u32 num_entries) -{ - return mod_lineinfo_lines_off(num_entries) + num_entries * sizeof(u32); + while (*pos < end) { + byte = data[*pos]; + (*pos)++; + result |= (int32_t)(byte & 0x7f) << shift; + shift += 7; + if (!(byte & 0x80)) + break; + if (shift >= 32) { + while (*pos < end && (data[*pos] & 0x80)) + (*pos)++; + if (*pos < end) + (*pos)++; + return result; + } + } + + /* Sign-extend if the high bit of the last byte was set */ + if (shift < 32 && (byte & 0x40)) + result |= -(1 << shift); + + return result; } -static inline u32 mod_lineinfo_filenames_off(u32 num_entries, u32 num_files) +/* + * Search a lineinfo table for the source file and line corresponding to a + * given offset (from _text for vmlinux, from .text base for modules). + * + * Safe for NMI and panic context: no locks, no allocations, all state on stack. + * Returns true and sets @file and @line on success; false on any failure. + */ +static inline bool lineinfo_search(const struct lineinfo_table *tbl, + unsigned int offset, + const char **file, unsigned int *line) { - return mod_lineinfo_file_offsets_off(num_entries) + - num_files * sizeof(u32); + unsigned int low, high, mid, block; + unsigned int cur_addr, cur_file_id, cur_line; + unsigned int best_file_id = 0, best_line = 0; + unsigned int block_entries, data_end; + bool found = false; + u32 pos; + + if (!tbl->num_entries || !tbl->num_blocks) + return false; + + /* Binary search on blk_addrs[] to find the right block */ + low = 0; + high = tbl->num_blocks; + while (low < high) { + mid = low + (high - low) / 2; + if (tbl->blk_addrs[mid] <= offset) + low = mid + 1; + else + high = mid; + } + + if (low == 0) + return false; + block = low - 1; + + /* How many entries in this block? */ + block_entries = LINEINFO_BLOCK_ENTRIES; + if (block == tbl->num_blocks - 1) { + unsigned int remaining = tbl->num_entries - + block * LINEINFO_BLOCK_ENTRIES; + + if (remaining < block_entries) + block_entries = remaining; + } + + /* Determine end of this block's data in the compressed stream */ + if (block + 1 < tbl->num_blocks) + data_end = tbl->blk_offsets[block + 1]; + else + data_end = tbl->data_size; + + /* Clamp data_end to actual data size */ + if (data_end > tbl->data_size) + data_end = tbl->data_size; + + /* Decode entry 0: addr from blk_addrs, file_id and line from stream */ + pos = tbl->blk_offsets[block]; + if (pos >= data_end) + return false; + + cur_addr = tbl->blk_addrs[block]; + cur_file_id = lineinfo_read_uleb128(tbl->data, &pos, data_end); + cur_line = lineinfo_read_uleb128(tbl->data, &pos, data_end); + + /* Check entry 0 */ + if (cur_addr <= offset) { + best_file_id = cur_file_id; + best_line = cur_line; + found = true; + } + + /* Decode entries 1..N */ + for (unsigned int i = 1; i < block_entries; i++) { + unsigned int addr_delta; + int32_t file_delta, line_delta; + + addr_delta = lineinfo_read_uleb128(tbl->data, &pos, data_end); + file_delta = lineinfo_read_sleb128(tbl->data, &pos, data_end); + line_delta = lineinfo_read_sleb128(tbl->data, &pos, data_end); + + cur_addr += addr_delta; + cur_file_id = (unsigned int)((int32_t)cur_file_id + file_delta); + cur_line = (unsigned int)((int32_t)cur_line + line_delta); + + if (cur_addr > offset) + break; + + best_file_id = cur_file_id; + best_line = cur_line; + found = true; + } + + if (!found) + return false; + + if (best_file_id >= tbl->num_files) + return false; + + if (tbl->file_offsets[best_file_id] >= tbl->filenames_size) + return false; + + *file = &tbl->filenames[tbl->file_offsets[best_file_id]]; + *line = best_line; + return true; } #endif /* _LINUX_MOD_LINEINFO_H */ diff --git a/init/Kconfig b/init/Kconfig index bf53275bc405a..6e3795b3dbd62 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -2065,8 +2065,9 @@ config KALLSYMS_LINEINFO anon_vma_clone+0x2ed/0xcf0 (mm/rmap.c:412) This requires elfutils (libdw-dev/elfutils-devel) on the build host. - Adds approximately 44MB to a typical kernel image (10 bytes per - DWARF line-table entry, ~4.6M entries for a typical config). + Adds approximately 10-15MB to a typical kernel image (~2-3 bytes + per entry after delta compression, ~4.6M entries for a typical + config). If unsure, say N. @@ -2079,7 +2080,8 @@ config KALLSYMS_LINEINFO_MODULES so stack traces from module code include (file.c:123) annotations. Requires elfutils (libdw-dev/elfutils-devel) on the build host. - Increases .ko sizes by approximately 10 bytes per DWARF line entry. + Increases .ko sizes by approximately 2-3 bytes per DWARF line + entry after delta compression. If unsure, say N. diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 9df92b0fd9041..76e30cac3a277 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -467,13 +467,16 @@ static int append_buildid(char *buffer, const char *modname, #endif /* CONFIG_STACKTRACE_BUILD_ID */ +#include + bool kallsyms_lookup_lineinfo(unsigned long addr, const char **file, unsigned int *line) { + struct lineinfo_table tbl; unsigned long long raw_offset; - unsigned int offset, low, high, mid, file_id; - if (!IS_ENABLED(CONFIG_KALLSYMS_LINEINFO) || !lineinfo_num_entries) + if (!IS_ENABLED(CONFIG_KALLSYMS_LINEINFO) || + !lineinfo_num_entries || !lineinfo_num_blocks) return false; /* Compute offset from _text */ @@ -483,34 +486,19 @@ bool kallsyms_lookup_lineinfo(unsigned long addr, raw_offset = addr - (unsigned long)_text; if (raw_offset > UINT_MAX) return false; - offset = (unsigned int)raw_offset; - - /* Binary search for largest entry <= offset */ - low = 0; - high = lineinfo_num_entries; - while (low < high) { - mid = low + (high - low) / 2; - if (lineinfo_addrs[mid] <= offset) - low = mid + 1; - else - high = mid; - } - - if (low == 0) - return false; - low--; - - file_id = lineinfo_file_ids[low]; - *line = lineinfo_lines[low]; - - if (file_id >= lineinfo_num_files) - return false; - - if (lineinfo_file_offsets[file_id] >= lineinfo_filenames_size) - return false; - *file = &lineinfo_filenames[lineinfo_file_offsets[file_id]]; - return true; + tbl.blk_addrs = lineinfo_block_addrs; + tbl.blk_offsets = lineinfo_block_offsets; + tbl.data = lineinfo_data; + tbl.data_size = lineinfo_data_size; + tbl.file_offsets = lineinfo_file_offsets; + tbl.filenames = lineinfo_filenames; + tbl.num_entries = lineinfo_num_entries; + tbl.num_blocks = lineinfo_num_blocks; + tbl.num_files = lineinfo_num_files; + tbl.filenames_size = lineinfo_filenames_size; + + return lineinfo_search(&tbl, (unsigned int)raw_offset, file, line); } /* Look up a kernel symbol and return it in a text buffer. */ diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index d7374ce444d81..ffe4c658067ec 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -16,10 +16,12 @@ extern const unsigned int kallsyms_markers[]; extern const u8 kallsyms_seqs_of_names[]; extern const u32 lineinfo_num_entries; -extern const u32 lineinfo_addrs[]; -extern const u16 lineinfo_file_ids[]; -extern const u32 lineinfo_lines[]; extern const u32 lineinfo_num_files; +extern const u32 lineinfo_num_blocks; +extern const u32 lineinfo_block_addrs[]; +extern const u32 lineinfo_block_offsets[]; +extern const u32 lineinfo_data_size; +extern const u8 lineinfo_data[]; extern const u32 lineinfo_file_offsets[]; extern const u32 lineinfo_filenames_size; extern const char lineinfo_filenames[]; diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c index 5b46293e957ab..743cf7033c37f 100644 --- a/kernel/module/kallsyms.c +++ b/kernel/module/kallsyms.c @@ -509,16 +509,11 @@ bool module_lookup_lineinfo(struct module *mod, unsigned long addr, const char **file, unsigned int *line) { const struct mod_lineinfo_header *hdr; + struct lineinfo_table tbl; const void *base; - const u32 *addrs, *lines, *file_offsets; - const u16 *file_ids; - const char *filenames; - u32 num_entries, num_files, filenames_size; + u32 section_size; unsigned long text_base; - unsigned int offset; unsigned long long raw_offset; - unsigned int low, high, mid; - u16 file_id; if (!IS_ENABLED(CONFIG_KALLSYMS_LINEINFO_MODULES)) return false; @@ -527,27 +522,30 @@ bool module_lookup_lineinfo(struct module *mod, unsigned long addr, if (!base) return false; - if (mod->lineinfo_data_size < sizeof(*hdr)) + section_size = mod->lineinfo_data_size; + if (section_size < sizeof(*hdr)) return false; hdr = base; - num_entries = hdr->num_entries; - num_files = hdr->num_files; - filenames_size = hdr->filenames_size; - if (num_entries == 0) + if (hdr->num_entries == 0 || hdr->num_blocks == 0) return false; - /* Validate section is large enough for all arrays */ - if (mod->lineinfo_data_size < - mod_lineinfo_filenames_off(num_entries, num_files) + filenames_size) + /* Validate each sub-array fits within the section */ + if (hdr->blocks_offset + hdr->blocks_size > section_size) + return false; + if (hdr->data_offset + hdr->data_size > section_size) + return false; + if (hdr->files_offset + hdr->files_size > section_size) + return false; + if (hdr->filenames_offset + hdr->filenames_size > section_size) return false; - addrs = base + mod_lineinfo_addrs_off(); - file_ids = base + mod_lineinfo_file_ids_off(num_entries); - lines = base + mod_lineinfo_lines_off(num_entries); - file_offsets = base + mod_lineinfo_file_offsets_off(num_entries); - filenames = base + mod_lineinfo_filenames_off(num_entries, num_files); + /* Validate array sizes match declared counts */ + if (hdr->blocks_size < hdr->num_blocks * 2 * sizeof(u32)) + return false; + if (hdr->files_size < hdr->num_files * sizeof(u32)) + return false; /* Compute offset from module .text base */ text_base = (unsigned long)mod->mem[MOD_TEXT].base; @@ -557,31 +555,18 @@ bool module_lookup_lineinfo(struct module *mod, unsigned long addr, raw_offset = addr - text_base; if (raw_offset > UINT_MAX) return false; - offset = (unsigned int)raw_offset; - - /* Binary search for largest entry <= offset */ - low = 0; - high = num_entries; - while (low < high) { - mid = low + (high - low) / 2; - if (addrs[mid] <= offset) - low = mid + 1; - else - high = mid; - } - - if (low == 0) - return false; - low--; - - file_id = file_ids[low]; - if (file_id >= num_files) - return false; - if (file_offsets[file_id] >= filenames_size) - return false; - - *file = &filenames[file_offsets[file_id]]; - *line = lines[low]; - return true; + tbl.blk_addrs = base + hdr->blocks_offset; + tbl.blk_offsets = base + hdr->blocks_offset + + hdr->num_blocks * sizeof(u32); + tbl.data = base + hdr->data_offset; + tbl.data_size = hdr->data_size; + tbl.file_offsets = base + hdr->files_offset; + tbl.filenames = base + hdr->filenames_offset; + tbl.num_entries = hdr->num_entries; + tbl.num_blocks = hdr->num_blocks; + tbl.num_files = hdr->num_files; + tbl.filenames_size = hdr->filenames_size; + + return lineinfo_search(&tbl, (unsigned int)raw_offset, file, line); } diff --git a/scripts/empty_lineinfo.S b/scripts/empty_lineinfo.S index e058c41137123..edd5b1092f050 100644 --- a/scripts/empty_lineinfo.S +++ b/scripts/empty_lineinfo.S @@ -14,12 +14,20 @@ lineinfo_num_entries: .balign 4 lineinfo_num_files: .long 0 - .globl lineinfo_addrs -lineinfo_addrs: - .globl lineinfo_file_ids -lineinfo_file_ids: - .globl lineinfo_lines -lineinfo_lines: + .globl lineinfo_num_blocks + .balign 4 +lineinfo_num_blocks: + .long 0 + .globl lineinfo_block_addrs +lineinfo_block_addrs: + .globl lineinfo_block_offsets +lineinfo_block_offsets: + .globl lineinfo_data_size + .balign 4 +lineinfo_data_size: + .long 0 + .globl lineinfo_data +lineinfo_data: .globl lineinfo_file_offsets lineinfo_file_offsets: .globl lineinfo_filenames_size diff --git a/scripts/gen_lineinfo.c b/scripts/gen_lineinfo.c index 5ced6897cbbee..fe46e2fa45d8a 100644 --- a/scripts/gen_lineinfo.c +++ b/scripts/gen_lineinfo.c @@ -550,6 +550,35 @@ static void deduplicate(void) num_entries = j + 1; } +/* + * Emit the LEB128 delta-compressed data stream for one block. + * Uses .uleb128/.sleb128 assembler directives for encoding. + */ +static void emit_block_data(unsigned int block) +{ + unsigned int base = block * LINEINFO_BLOCK_ENTRIES; + unsigned int count = num_entries - base; + + if (count > LINEINFO_BLOCK_ENTRIES) + count = LINEINFO_BLOCK_ENTRIES; + + /* Entry 0: file_id, line (both unsigned) */ + printf("\t.uleb128 %u\n", entries[base].file_id); + printf("\t.uleb128 %u\n", entries[base].line); + + /* Entries 1..N: addr_delta (unsigned), file/line deltas (signed) */ + for (unsigned int i = 1; i < count; i++) { + unsigned int idx = base + i; + + printf("\t.uleb128 %u\n", + entries[idx].offset - entries[idx - 1].offset); + printf("\t.sleb128 %d\n", + (int)entries[idx].file_id - (int)entries[idx - 1].file_id); + printf("\t.sleb128 %d\n", + (int)entries[idx].line - (int)entries[idx - 1].line); + } +} + static void compute_file_offsets(void) { unsigned int offset = 0; @@ -573,6 +602,11 @@ static void print_escaped_asciz(const char *s) static void output_assembly(void) { + unsigned int num_blocks; + + num_blocks = num_entries ? + (num_entries + LINEINFO_BLOCK_ENTRIES - 1) / LINEINFO_BLOCK_ENTRIES : 0; + printf("/* SPDX-License-Identifier: GPL-2.0 */\n"); printf("/*\n"); printf(" * Automatically generated by scripts/gen_lineinfo\n"); @@ -593,29 +627,40 @@ static void output_assembly(void) printf("lineinfo_num_files:\n"); printf("\t.long %u\n\n", num_files); - /* Sorted address offsets from _text */ - printf("\t.globl lineinfo_addrs\n"); + /* Number of blocks */ + printf("\t.globl lineinfo_num_blocks\n"); + printf("\t.balign 4\n"); + printf("lineinfo_num_blocks:\n"); + printf("\t.long %u\n\n", num_blocks); + + /* Block first-addresses for binary search */ + printf("\t.globl lineinfo_block_addrs\n"); printf("\t.balign 4\n"); - printf("lineinfo_addrs:\n"); - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.long 0x%x\n", entries[i].offset); - printf("\n"); - - /* File IDs, parallel to addrs (u16 -- supports up to 65535 files) */ - printf("\t.globl lineinfo_file_ids\n"); - printf("\t.balign 2\n"); - printf("lineinfo_file_ids:\n"); - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.short %u\n", entries[i].file_id); - printf("\n"); - - /* Line numbers, parallel to addrs */ - printf("\t.globl lineinfo_lines\n"); + printf("lineinfo_block_addrs:\n"); + for (unsigned int i = 0; i < num_blocks; i++) + printf("\t.long 0x%x\n", entries[i * LINEINFO_BLOCK_ENTRIES].offset); + + /* Block byte offsets into compressed stream */ + printf("\t.globl lineinfo_block_offsets\n"); printf("\t.balign 4\n"); - printf("lineinfo_lines:\n"); - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.long %u\n", entries[i].line); - printf("\n"); + printf("lineinfo_block_offsets:\n"); + for (unsigned int i = 0; i < num_blocks; i++) + printf("\t.long .Lblock_%u - lineinfo_data\n", i); + + /* Compressed data size */ + printf("\t.globl lineinfo_data_size\n"); + printf("\t.balign 4\n"); + printf("lineinfo_data_size:\n"); + printf("\t.long .Ldata_end - lineinfo_data\n\n"); + + /* Compressed data stream */ + printf("\t.globl lineinfo_data\n"); + printf("lineinfo_data:\n"); + for (unsigned int i = 0; i < num_blocks; i++) { + printf(".Lblock_%u:\n", i); + emit_block_data(i); + } + printf(".Ldata_end:\n\n"); /* File string offset table */ printf("\t.globl lineinfo_file_offsets\n"); @@ -623,34 +668,27 @@ static void output_assembly(void) printf("lineinfo_file_offsets:\n"); for (unsigned int i = 0; i < num_files; i++) printf("\t.long %u\n", files[i].str_offset); - printf("\n"); /* Filenames size */ - { - unsigned int fsize = 0; - - for (unsigned int i = 0; i < num_files; i++) - fsize += strlen(files[i].name) + 1; - printf("\t.globl lineinfo_filenames_size\n"); - printf("\t.balign 4\n"); - printf("lineinfo_filenames_size:\n"); - printf("\t.long %u\n\n", fsize); - } + printf("\t.globl lineinfo_filenames_size\n"); + printf("\t.balign 4\n"); + printf("lineinfo_filenames_size:\n"); + printf("\t.long .Lfilenames_end - lineinfo_filenames\n\n"); /* Concatenated NUL-terminated filenames */ printf("\t.globl lineinfo_filenames\n"); printf("lineinfo_filenames:\n"); for (unsigned int i = 0; i < num_files; i++) print_escaped_asciz(files[i].name); - printf("\n"); + printf(".Lfilenames_end:\n"); } static void output_module_assembly(void) { - unsigned int filenames_size = 0; + unsigned int num_blocks; - for (unsigned int i = 0; i < num_files; i++) - filenames_size += strlen(files[i].name) + 1; + num_blocks = num_entries ? + (num_entries + LINEINFO_BLOCK_ENTRIES - 1) / LINEINFO_BLOCK_ENTRIES : 0; printf("/* SPDX-License-Identifier: GPL-2.0 */\n"); printf("/*\n"); @@ -660,46 +698,56 @@ static void output_module_assembly(void) printf("\t.section .mod_lineinfo, \"a\"\n\n"); - /* Header: num_entries, num_files, filenames_size, reserved */ + /* + * Header -- offsets and sizes are assembler expressions so the + * layout is self-describing without manual C arithmetic. + */ + printf(".Lhdr:\n"); printf("\t.balign 4\n"); - printf("\t.long %u\n", num_entries); - printf("\t.long %u\n", num_files); - printf("\t.long %u\n", filenames_size); - printf("\t.long 0\n\n"); - - /* addrs[] */ - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.long 0x%x\n", entries[i].offset); - if (num_entries) - printf("\n"); - - /* file_ids[] */ - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.short %u\n", entries[i].file_id); - - /* Padding to align lines[] to 4 bytes */ - if (num_entries & 1) - printf("\t.short 0\n"); - if (num_entries) - printf("\n"); - - /* lines[] */ - for (unsigned int i = 0; i < num_entries; i++) - printf("\t.long %u\n", entries[i].line); - if (num_entries) - printf("\n"); + printf("\t.long %u\t\t\t\t/* num_entries */\n", num_entries); + printf("\t.long %u\t\t\t\t/* num_blocks */\n", num_blocks); + printf("\t.long %u\t\t\t\t/* num_files */\n", num_files); + printf("\t.long .Lblk_addrs - .Lhdr\t\t/* blocks_offset */\n"); + printf("\t.long .Lblk_offsets_end - .Lblk_addrs\t/* blocks_size */\n"); + printf("\t.long .Ldata - .Lhdr\t\t\t/* data_offset */\n"); + printf("\t.long .Ldata_end - .Ldata\t\t/* data_size */\n"); + printf("\t.long .Lfile_offsets - .Lhdr\t\t/* files_offset */\n"); + printf("\t.long .Lfile_offsets_end - .Lfile_offsets /* files_size */\n"); + printf("\t.long .Lfilenames - .Lhdr\t\t/* filenames_offset */\n"); + printf("\t.long .Lfilenames_end - .Lfilenames\t/* filenames_size */\n"); + printf("\t.long 0\t\t\t\t\t/* reserved */\n\n"); + + /* block_addrs[] */ + printf(".Lblk_addrs:\n"); + for (unsigned int i = 0; i < num_blocks; i++) + printf("\t.long 0x%x\n", entries[i * LINEINFO_BLOCK_ENTRIES].offset); + + /* block_offsets[] */ + printf(".Lblk_offsets:\n"); + for (unsigned int i = 0; i < num_blocks; i++) + printf("\t.long .Lblock_%u - .Ldata\n", i); + printf(".Lblk_offsets_end:\n\n"); + + /* compressed data stream */ + printf(".Ldata:\n"); + for (unsigned int i = 0; i < num_blocks; i++) { + printf(".Lblock_%u:\n", i); + emit_block_data(i); + } + printf(".Ldata_end:\n"); /* file_offsets[] */ + printf("\t.balign 4\n"); + printf(".Lfile_offsets:\n"); for (unsigned int i = 0; i < num_files; i++) printf("\t.long %u\n", files[i].str_offset); - if (num_files) - printf("\n"); + printf(".Lfile_offsets_end:\n\n"); /* filenames[] */ + printf(".Lfilenames:\n"); for (unsigned int i = 0; i < num_files; i++) print_escaped_asciz(files[i].name); - if (num_files) - printf("\n"); + printf(".Lfilenames_end:\n"); } int main(int argc, char *argv[]) @@ -779,8 +827,10 @@ int main(int argc, char *argv[]) deduplicate(); compute_file_offsets(); - fprintf(stderr, "lineinfo: %u entries, %u files\n", - num_entries, num_files); + fprintf(stderr, "lineinfo: %u entries, %u files, %u blocks\n", + num_entries, num_files, + num_entries ? + (num_entries + LINEINFO_BLOCK_ENTRIES - 1) / LINEINFO_BLOCK_ENTRIES : 0); if (module_mode) output_module_assembly(); @@ -796,6 +846,5 @@ int main(int argc, char *argv[]) for (unsigned int i = 0; i < num_files; i++) free(files[i].name); free(files); - return 0; } diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 42662c4fbc6c9..94fbdad3df7c6 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -80,11 +80,12 @@ static bool is_ignored_symbol(const char *name, char type) { /* Ignore lineinfo symbols for kallsyms pass stability */ static const char * const lineinfo_syms[] = { - "lineinfo_addrs", - "lineinfo_file_ids", + "lineinfo_block_addrs", + "lineinfo_block_offsets", + "lineinfo_data", "lineinfo_file_offsets", "lineinfo_filenames", - "lineinfo_lines", + "lineinfo_num_blocks", "lineinfo_num_entries", "lineinfo_num_files", }; -- 2.51.0