kallsyms

[TOC]

linux-gnu/bits/getopt_ext.h getopt_long: GNU 命令行长选项解析接口

本代码片段是一个 C 语言头文件（getopt_ext.h，通常被 getopt.h 包含），它定义了 GNU C 库中用于解析命令行参数的 getopt_long 函数及其核心数据结构 struct option。其主要功能是为命令行程序提供一个强大且灵活的机制，使其能够支持并解析长格式的选项（例如，--all-symbols），而不仅仅是传统的单字母短格式选项（如 -a）。

实现原理分析

此机制的核心是通过一个描述符结构体数组，将命令行中的字符串与程序内部的变量和行为进行声明式映射。

1. 选项描述符 (struct option): 这是整个机制的核心数据结构。开发者需要创建一个 struct option 类型的数组，数组中的每一个元素都完整地描述了一个长选项：

   • const char *name: 定义了长选项的名称，即 -- 后面的字符串，例如 "all-symbols"。
   • int has_arg: 指定该选项是否需要参数。它有三个可能的值：
     • no_argument (0): 选项后面不跟任何参数 (例如, --verbose)。
     • required_argument (1): 选项后面必须跟一个参数 (例如, --output file.txt)。
     • optional_argument (2): 选项后面可以跟一个可选的参数。
   • int *flag 和 int val: 这两个字段共同决定了当 getopt_long 匹配到这个选项时所执行的动作，有两种主要模式：
     • 标志模式 (flag 非 NULL): 如果 flag 指向一个 int 变量，那么当该选项出现时，getopt_long 会自动将 val 字段的值赋给 *flag 指向的变量。这是一种“自动”模式，getopt_long 本身返回 0。kallsyms.c 中的 {"all-symbols", no_argument, &all_symbols, 1} 就是这种用法，它会在匹配到 --all-symbols 时，将全局变量 all_symbols 的值设置为 1。
     • 返回值模式 (flag 为 NULL): 如果 flag 为 NULL，那么当该选项出现时，getopt_long 会直接返回 val 字段的值。这允许程序在 switch 语句中根据返回值来执行更复杂的逻辑。

2. 解析循环 (getopt_long): 应用程序通常在一个 while 循环中反复调用 getopt_long 函数。getopt_long 会在每次调用时，解析命令行参数数组（argv）中的下一个选项。它会自动处理选项与参数的关联（例如 --output file.txt 中的 file.txt 会被存入全局变量 optarg），并更新一个内部索引来跟踪解析进度。当所有选项都解析完毕后，getopt_long 会返回 -1，循环随之结束。

代码分析

/* getopt_ext.h */

// SPDX-License-Identifier: LGPL-2.1-or-later
// ... (版权和许可证信息)

#ifndef _GETOPT_EXT_H
#define _GETOPT_EXT_H 1

// ...

__BEGIN_DECLS

/**
 * @struct option
 * @brief 用于描述一个长选项的结构体。
 *
 * getopt_long 或 getopt_long_only 的 LONG_OPTIONS 参数是一个
 * 由 'struct option' 组成的数组，以一个 name 字段为零的元素作为结尾。
 */
struct option
{
  /** @brief 长选项的名称 (不含 '--')。 */
  const char *name;
  
  /** 
   * @brief 指示选项是否需要参数。
   * @details
   * - no_argument (0): 选项不带参数。
   * - required_argument (1): 选项必须带一个参数。
   * - optional_argument (2): 选项可以带一个可选的参数。
   */
  int has_arg;
  
  /** 
   * @brief 行为模式选择标志。
   * @details
   * - 如果非 NULL, 它指向一个 int 变量。当找到该选项时，这个变量会被设置为 'val' 字段的值。
   * - 如果为 NULL, getopt_long 会返回 'val' 字段的值。
   */
  int *flag;
  
  /** 
   * @brief 选项的值。
   * @details
   * - 如果 'flag' 非 NULL，这是要赋给 *flag 的值。
   * - 如果 'flag' 为 NULL，这是 getopt_long 找到该选项时的返回值。
   */
  int val;
};

/* 'has_arg' 字段的推荐值名称。 */

/** @def no_argument
 *  @brief 'has_arg' 的值，表示选项不带参数。
 */
#define no_argument		0
/** @def required_argument
 *  @brief 'has_arg' 的值，表示选项必须带一个参数。
 */
#define required_argument	1
/** @def optional_argument
 *  @brief 'has_arg' 的值，表示选项可以带一个可选参数。
 */
#define optional_argument	2

/**
 * @brief 解析命令行参数，支持长选项。
 * @param ___argc 参数计数 (来自 main)。
 * @param ___argv 参数数组 (来自 main)。
 * @param __shortopts 短选项字符串 (例如 "ab:c:")。
 * @param __longopts 指向 'struct option' 数组的指针。
 * @param __longind 如果非 NULL，它指向一个变量，用于存储找到的长选项在 __longopts 数组中的索引。
 * @return 找到选项时，返回选项字符或 'val'；解析完毕返回 -1；出错返回 '?'。
 */
extern int getopt_long (int ___argc, char *__getopt_argv_const *___argv,
			const char *__shortopts,
		        const struct option *__longopts, int *__longind)
       __THROW __nonnull ((2, 3));

/**
 * @brief 与 getopt_long 类似，但即使是非选项的参数（不以'-'开头）
 *        如果与某个长选项匹配，也会被当作该长选项处理。
 */
extern int getopt_long_only (int ___argc, char *__getopt_argv_const *___argv,
			     const char *__shortopts,
		             const struct option *__longopts, int *__longind)
       __THROW __nonnull ((2, 3));

__END_DECLS

#endif /* getopt_ext.h */

scripts/kallsyms.c

kallsyms.c: 内核符号表的压缩与汇编代码生成

本代码是一个在主机（Host）编译环境上运行的 C 语言程序，它是 Linux 内核构建过程中的一个关键工具。它的核心功能是读取由 nm 工具生成的文本格式的内核符号列表（System.map 格式），然后执行一套复杂的字典压缩算法来减小符号名称数据所占用的空间，最后将这些压缩好的二进制数据以及符号地址（以相对偏移量存储）转换成一个汇编语言源文件（.S 文件）。这个最终生成的汇编文件随后会被编译并链接回内核，从而在内核映像中嵌入一个完整的、紧凑的、可在运行时查询的符号表。

实现原理分析

此程序是结合了高级数据压缩技术和底层二进制格式生成的典范。其实现原理可分为四个主要阶段：数据读取与过滤、地址相对化、字典压缩，以及最终的汇编代码生成。

1. 数据读取与过滤 (read_map, shrink_table):

   • 程序首先逐行读取 nm 工具生成的 地址 类型 符号名 格式的文本文件。
   • 对于每一行，read_symbol 函数会将其解析并存储到一个 sym_entry 结构体中。
   • 关键的过滤步骤在 shrink_table 函数中完成。它调用 symbol_valid 来决定每个符号是否应该被保留。默认情况下（没有 --all-symbols 选项），只有位于代码段 (_stext 到 _etext) 和初始化代码段 (_sinittext 到 _einittext) 内的符号，以及一些特殊的边界符号（如 __start_...）才会被保留。这极大地减小了最终符号表的规模，排除了数据段中的变量等。

2. 地址相对化 (sort_symbols, record_relative_base):

   • 这是一个重要的空间优化技术。在过滤后，sort_symbols 首先按地址对所有符号进行排序。
   • record_relative_base 函数随后记录下排序后第一个符号的地址作为全局的 relative_base。
   • 在最终生成代码时（write_src），每个符号的地址将不再存储为绝对值，而是存储为 table[i]->addr - relative_base 的 32 位偏移量。这在 64 位系统上可以为每个符号节省 4 个字节的存储空间。内核在运行时，只需将这个相对基地址加上符号的偏移量即可还原出其绝对地址。

3. 字典-令牌压缩算法 (optimize_token_table):

   • 这是整个程序中最核心、最精妙的部分，旨在将符号名称字符串的体积压缩约 50%。
   • 学习阶段: build_initial_token_table 函数会遍历所有符号名称，并统计所有连续两个字节（2-byte token）出现的频率，存入 token_profit 数组。
   • 初始化字典: insert_real_symbols_in_table 函数初始化一个 256 项的“最佳令牌表”（best_table）。最初，表中的每一项 i 都只代表它自己（即单个字节 i）。
   • 贪心迭代压缩: optimize_result 函数在一个循环中执行贪心算法。在每一步：
     a. find_best_token 都会从 token_profit 中找出当前频率最高（“利润”最大）的 2 字节令牌。
     b. 它会从 best_table 中找到一个尚未被用过的索引 i（从 255 向下查找）。
     c. 它将这个利润最高的令牌（例如 “st”）存入 best_table[i]。现在，字节 i 就代表了字符串 “st”。
     d. compress_symbols 函数会被调用，它会遍历所有符号，将其中所有的 “st” 字符串替换为单个字节 i。
     e. 在替换后，compress_symbols 内部会调用 forget_symbol 和 learn_symbol 来动态更新所有受影响符号的令牌频率计数。
   • 这个过程会不断重复，直到没有更多可用的索引或没有更多有利润的令牌为止。最终，best_table 就成了一个完整的“字典”，而 table 中存储的符号名称则被替换成了一系列代表原始字符或字典条目的“令牌”。

4. 汇编代码生成 (write_src):

   • 此函数负责将内存中处理好的所有数据结构，以汇编指令的形式输出。
   • 它会依次生成多个数据段，包括：
     • kallsyms_num_syms: 符号总数。
     • kallsyms_names: 所有符号名称的压缩后令牌序列，每个名称前都有一个变长的长度前缀。
     • kallsyms_markers: 一个稀疏索引表，用于在运行时快速定位到 kallsyms_names 中的某个符号。
     • kallsyms_token_table 和 kallsyms_token_index: 最终生成的“字典”本身，内核需要它来进行运行时的解压。
     • kallsyms_offsets: 所有符号的 32 位相对地址偏移量。
     • kallsyms_relative_base: 相对地址的基准值。

kallsyms.c main: 内核符号表处理流水线

本代码片段是 kallsyms.c 这个主机端构建工具的 main 函数，即整个程序的入口点。其核心功能是作为一个总指挥（orchestrator），按照一个严格确定的顺序，调用一系列处理函数，形成一个完整的数据处理流水线。这个流水线将一个纯文本格式的内核符号列表作为输入，经过读取、过滤、排序、压缩和格式化等一系列步骤，最终生成一个包含高度压缩的二进制符号表的汇编语言源文件作为输出。

实现原理分析

main 函数的实现原理是一个经典的确定性处理流水线（Deterministic Processing Pipeline）。流水线中的每一步都以上一步的输出作为输入，并为其后的一步准备好数据。这个顺序是经过精心设计的，至关重要，任何一步的顺序颠倒都将导致错误的结果。

1. 参数解析 (getopt_long): 程序首先处理命令行参数。它支持一个关键选项 --all-symbols，该选项通过设置一个全局标志 all_symbols 来改变后续过滤步骤的行为。

2. 处理流水线（The Pipeline）:

   • read_map(argv[optind]) (数据加载): 这是流水线的第一步。它负责读取输入文件（in.map），将每一行文本解析成一个结构化的 sym_entry，并将它们加载到内存中的一个动态数组 table 中。
   • shrink_table() (数据过滤): 第二步。它遍历内存中的 table，根据 symbol_valid 函数的规则（主要看符号是否在代码段内，除非 --all-symbols 被指定）移除不需要的符号。这一步必须在排序和压缩之前完成，以减少后续高开销操作需要处理的数据量。
   • sort_symbols() (数据排序): 第三步。它使用 qsort 按符号的地址对 table 进行排序。排序是 record_relative_base 的绝对前提，因为下一步需要找到地址最低的符号。
   • record_relative_base() (基准化): 第四步。在排序后的 table 中，它简单地取出第一个符号的地址，并将其记录为 relative_base。所有符号的地址稍后都将表示为相对于这个基地址的偏移量，这是一种关键的空间优化。
   • optimize_token_table() (核心处理/压缩): 第五步。这是整个流水线中最复杂和计算密集的一步。它对过滤和排序后的符号名称执行复杂的字典-令牌压缩算法，将字符串压缩为令牌序列，并构建用于解压的字典。
   • write_src() (数据生成/输出): 流水线的最后一步。它将内存中所有经过处理的数据结构——符号总数、压缩后的名称、用于快速查找的标记点、解压字典以及相对地址偏移量——格式化为汇编语言指令，并打印到标准输出。

这个严格的顺序确保了每一步操作都在其所需的数据已经准备好的前提下进行，最终高效、正确地完成了从文本到压缩二进制汇编的转换。

代码分析

/**
 * @brief kallsyms 工具的主函数入口。
 * @param argc 命令行参数数量。
 * @param argv 命令行参数数组。
 * @return 成功返回0，失败则通过 exit() 退出。
 */
int main(int argc, char **argv)
{
	// 循环解析命令行长选项。
	while (1) {
		// 定义长选项结构体。
		static const struct option long_options[] = {
			// "--all-symbols" 选项，不带参数，如果出现，则将全局变量 all_symbols 的地址设为1。
			{"all-symbols",     no_argument, &all_symbols,     1},
			{}, // 数组结束标记。
		};

		int c = getopt_long(argc, argv, "", long_options, NULL);

		if (c == -1) // 如果 getopt_long 返回-1，表示所有选项已解析完毕。
			break;
		if (c != 0) // 如果 getopt_long 设置了标志，它返回0；否则对于长选项返回非零值表示错误。
			usage(); // 如果选项无效，打印用法并退出。
	}

	// optind 是 getopt 处理后，第一个非选项参数的索引。
	// 检查是否提供了输入文件名。
	if (optind >= argc)
		usage(); // 如果没有提供输入文件名，打印用法并退出。

	// === 执行核心处理流水线 ===

	// 1. 读取并解析 in.map 文件，将符号加载到内存。
	read_map(argv[optind]);
	
	// 2. 根据规则过滤符号表，移除不需要的符号。
	shrink_table();
	
	// 3. 按地址对符号表进行排序。
	sort_symbols();
	
	// 4. 记录排序后第一个符号的地址，作为计算相对偏移的基准。
	record_relative_base();
	
	// 5. 执行字典压缩算法，压缩符号名称并构建解压所需的令牌表。
	optimize_token_table();
	
	// 6. 将处理好的所有数据结构（符号数、压缩名、地址偏移、令牌表等）生成为汇编代码，并输出到 stdout。
	write_src();

	return 0; // 成功退出。
}

read_map & read_symbol: 内核符号表的解析与内存加载

本代码片段是 kallsyms.c 这个主机端构建工具的核心输入和解析部分。其主要功能是读取由 nm 和 sed 预处理过的、格式为 地址 类型 符号名 的文本文件（System.map 格式），然后将每一行解析并转换成一个结构化的、便于后续处理的内存表示（struct sym_entry）。read_map 负责驱动整个文件读取过程并管理动态内存，而 read_symbol 则负责单行文本的精细解析和数据结构填充。

实现原理分析

此实现的核心是一种高效的行式文本流解析与内存数据结构化的流水线。它结合了标准的 C 库 I/O 函数和手动的指针操作，以实现快速和精确的解析。

1. 动态数组管理 (read_map): read_map 函数负责打开文件并循环读取。由于符号的总数事先未知，它采用了一种经典的动态数组增长策略。全局指针数组 table 在需要时会通过 xrealloc 进行扩容（每次增加 10000 个条目），这避免了预先分配一个可能过大或过小的静态数组，实现了对内存的有效利用。

2. 高效行读取 (getline): read_symbol 函数内部使用了 POSIX 的 getline 函数。相比于 fgets，getline 能够自动处理任意长度的行，并负责缓冲区的分配和再分配。这使得代码更加健壮，能够正确处理异常长的符号名，而无需编写复杂的缓冲区管理逻辑。

3. 精确的格式解析 (read_symbol):

   • 地址解析: 使用 strtoull 函数，以 16 为基数，将行首的十六进制字符串直接转换为 unsigned long long 类型的地址。
   • 格式验证: 通过 *p++ != ' ' 等一系列指针操作和检查，代码严格验证了输入行是否遵循 地址<空格>类型<空格>名称 的格式。这是一个简单但高效的手动状态机解析，任何格式错误都会导致程序中止。

4. 关键的优化：类型与名称的融合 (read_symbol):

   • 这是一个非常精妙的优化，旨在为后续的压缩阶段做准备。在分配 sym_entry 结构体时，它额外多分配了一个字节（len++）。
   • 然后，它将符号的类型字符（如 ‘T’, ‘d’）存储在 sym->sym[0]，而将符号的名称字符串本身存储在从 sym->sym[1] 开始的位置（通过 strcpy(sym_name(sym), name) 实现，其中 sym_name 宏返回 &sym->sym[1]）。
   • 通过这种方式，类型信息被无缝地“嵌入”到了符号名称数据的前面。这使得后续的字典压缩算法可以将类型字符与名称的第一个字符组成的二元组，也视为一个潜在的、可以被压缩的“令牌”，从而可能获得更好的整体压缩率。

代码分析

/**
 * @brief 从指定的 map 文件中读取所有符号，并将其加载到全局的符号表中。
 * @param in 输入文件的路径字符串。
 */
static void read_map(const char *in)
{
	FILE *fp;
	struct sym_entry *sym;
	char *buf = NULL; // 指向 getline 使用的行缓冲区的指针。
	size_t buflen = 0; // 行缓冲区的大小。

	// 以只读模式打开输入文件。
	fp = fopen(in, "r");
	if (!fp) {
		perror(in); // 如果打开失败，打印错误信息并退出。
		exit(1);
	}

	// 循环读取文件，直到文件末尾。
	// 注意：使用 feof() 作为循环条件是不完美的，但在这里与 getline 的行为结合是可行的。
	while (!feof(fp)) {
		// 调用 read_symbol 来解析文件中的下一行。
		sym = read_symbol(fp, &buf, &buflen);
		// 如果 read_symbol 返回 NULL (例如，空行、格式错误或被忽略的符号)，则继续下一轮循环。
		if (!sym)
			continue;

		// 记录该符号的原始顺序，这对于后续需要稳定排序的场景很重要。
		sym->seq = table_cnt;

		// 检查全局符号表数组是否已满。
		if (table_cnt >= table_size) {
			// 如果已满，则将容量增加 10000。
			table_size += 10000;
			// 重新分配内存，扩大数组。xrealloc 是一个带错误检查的 realloc 包装。
			table = xrealloc(table, sizeof(*table) * table_size);
		}

		// 将新解析出的符号条目指针存入数组，并增加计数器。
		table[table_cnt++] = sym;
	}

	free(buf); // 释放 getline 自动分配的行缓冲区。
	fclose(fp); // 关闭文件。
}

/**
 * @brief 从文件流中读取并解析单行符号信息。
 * @param in 输入文件流指针。
 * @param buf 指向行缓冲指针的指针 (供 getline 使用)。
 * @param buf_len 指向行缓冲大小的指针 (供 getline 使用)。
 * @return 成功解析则返回一个新分配的 sym_entry 结构体指针，否则返回 NULL。
 */
static struct sym_entry *read_symbol(FILE *in, char **buf, size_t *buf_len)
{
	char *name, type, *p;
	unsigned long long addr;
	size_t len;
	ssize_t readlen;
	struct sym_entry *sym;

	errno = 0; // 清除旧的错误码。
	// 从 'in' 读取一整行到 *buf，自动处理内存分配。
	readlen = getline(buf, buf_len, in);
	// 如果 getline 返回负值，表示已到文件末尾或发生错误。
	if (readlen < 0) {
		if (errno) { // 如果是 I/O 错误。
			perror("read_symbol");
			exit(EXIT_FAILURE);
		}
		return NULL; // 如果是文件末尾，正常返回 NULL。
	}

	// 移除行尾的换行符。
	if ((*buf)[readlen - 1] == '\n')
		(*buf)[readlen - 1] = 0;

	// 解析行首的十六进制地址。
	addr = strtoull(*buf, &p, 16);

	// 验证行格式是否为 "地址<空格>类型<空格>名称"。
	if (*buf == p || *p++ != ' ' || !isascii((type = *p++)) || *p++ != ' ') {
		fprintf(stderr, "line format error\n");
		exit(EXIT_FAILURE);
	}

	// 剩余部分为符号名称。
	name = p;
	len = strlen(name);

	// 检查符号名是否过长。
	if (len >= KSYM_NAME_LEN) {
		fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
				"Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
			name, len, KSYM_NAME_LEN);
		return NULL;
	}

	// 特殊处理：记录 _text 符号的地址。
	if (strcmp(name, "_text") == 0)
		_text = addr;

	// 根据类型和名称进行初步过滤，忽略某些符号。
	if (is_ignored_symbol(name, type))
		return NULL;

	// 检查并记录特殊的文本段边界符号的地址。
	check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));

	// [关键优化] 增加长度以包含类型字符，以便一起进行压缩。
	len++;

	// 分配内存：结构体大小 + 名称长度 + 类型字符(已计入len) + 字符串结束符。
	sym = xmalloc(sizeof(*sym) + len + 1);
	sym->addr = addr;
	sym->len = len; // 存储的是包含类型字符的长度。
	sym->sym[0] = type; // 将类型字符存为数据的第一个字节。
	// 将名称字符串复制到类型字符之后的位置。
	strcpy(sym_name(sym), name);

	return sym;
}

符号预过滤与边界检测 (is_ignored_symbol, check_symbol_range)

本代码片段是 kallsyms.c 主机端构建工具在解析符号表过程中的两个关键辅助函数。它们在 read_symbol 函数内部被调用，协同完成两个核心任务：is_ignored_symbol 扮演一个初步过滤器的角色，根据符号的类型和一小部分特例名称，快速剔除掉明显无用的符号；而 check_symbol_range 则扮演一个边界哨兵的角色，它在符号流中专门寻找并捕获标记内核关键内存区域（如代码段）起始和结束的特殊符号地址。

实现原理分析

这两个函数共同构成了解析阶段的“预处理”步骤，为后续更复杂的过滤和压缩算法准备好干净、有用的数据。

1. 基于“黑名单”的快速过滤 (is_ignored_symbol):

   • 该函数的逻辑是一个简单的“黑名单”机制，其目的是尽早地丢弃那些对最终 kallsyms 表毫无意义的符号，以减少内存占用和后续处理的开销。
   • 规则 1 (类型过滤): if (type == 'u' || type == 'n')。它直接丢弃两种类型的符号：
     • 'u' (对应 nm 输出中的 U): 代表未定义 (Undefined) 的符号。这些是内核代码引用了但并未在内核主镜像中定义的符号（可能在模块中，或链接错误），它们没有地址，因此无用。
     • 'n': 代表来自调试段（如 .stab）的调试符号，这些不属于运行时符号表。
   • 规则 2 (特例处理): if (toupper(type) == 'A')。'A' (或 'a') 代表绝对地址 (Absolute) 符号，它们通常是常量或特殊地址，大部分对运行时地址解析无用。因此，该函数的默认行为是丢弃它们。
   • 白名单中的特例: 在丢弃绝对地址符号的规则内部，有一个 if (strcmp(...) && ...) 的反向逻辑判断。这实际上构成了一个白名单，用于“拯救”几个虽然是绝对地址但对系统运行至关重要的符号，例如 __kernel_syscall_via_* (系统调用入口点)、__kernel_sigtramp (信号处理trampoline代码) 以及 __gp (某些架构上的全局指针)。

2. 基于“标记”的范围捕获 (check_symbol_range):

   • 该函数不进行任何过滤。它的唯一任务是在流经的符号中识别并记录特定的“边界标记”符号的地址。
   • 它会遍历一个预定义的 addr_range 结构体数组（text_ranges），这个数组中包含了它所关心的边界符号对的名称，例如 {"_stext", "_etext"}。
   • 当它遇到一个符号，其名称与数组中某个 start_sym 或 end_sym 匹配时，它就会将该符号的地址 addr 捕获并存入 addr_range 结构体对应的 start 或 end 字段中。
   • 目的: 这一步至关重要，因为它动态地确定了内核代码段 .text 和初始化代码段 .init.text 在内存中的确切范围。这个范围信息将在后续的 symbol_valid 函数中被用作主要的过滤依据，以确保（在默认模式下）只有位于这些代码区域内的函数符号才会被最终保留下来。

代码分析

/**
 * @brief 判断一个符号是否应该被初步忽略。
 * @param name 符号的名称字符串。
 * @param type 符号的类型字符 (来自 nm 的输出)。
 * @return 如果符号应该被忽略则返回 true，否则返回 false。
 */
static bool is_ignored_symbol(const char *name, char type)
{
	// 规则1：忽略未定义符号 ('u') 和调试符号 ('n')。
	if (type == 'u' || type == 'n')
		return true;

	// 规则2：处理绝对地址符号 ('A' 或 'a')。
	if (toupper(type) == 'A') {
		/* 保留这些有用的绝对地址符号 (白名单)。*/
		// 如果符号名不是以下任何一个，则它是一个应该被忽略的绝对地址符号。
		if (strcmp(name, "__kernel_syscall_via_break") &&
		    strcmp(name, "__kernel_syscall_via_epc") &&
		    strcmp(name, "__kernel_sigtramp") &&
		    strcmp(name, "__gp"))
			return true;
	}

	// 对于所有其他情况，暂时不忽略该符号。
	return false;
}

/**
 * @brief 在符号流中检查是否存在预定义的边界符号，并记录它们的地址。
 * @param sym 待检查的符号的名称。
 * @param addr 待检查的符号的地址。
 * @param ranges 指向一个 addr_range 结构体数组，其中包含了要寻找的边界符号名称。
 * @param entries ranges 数组中的条目数。
 */
static void check_symbol_range(const char *sym, unsigned long long addr,
			       struct addr_range *ranges, int entries)
{
	size_t i;
	struct addr_range *ar;

	// 遍历所有需要寻找的边界范围。
	for (i = 0; i < entries; ++i) {
		ar = &ranges[i];

		// 检查当前符号是否是某个范围的起始符号。
		if (strcmp(sym, ar->start_sym) == 0) {
			// 如果是，则记录其地址并返回。
			ar->start = addr;
			return;
		// 检查当前符号是否是某个范围的结束符号。
		} else if (strcmp(sym, ar->end_sym) == 0) {
			// 如果是，则记录其地址并返回。
			ar->end = addr;
			return;
		}
	}
}

shrink_table 内核符号表的精炼：基于地址范围的核心符号过滤

本代码片段是 kallsyms.c 主机端构建工具中的核心过滤模块。其主要功能是通过 shrink_table 函数，对从内核 ELF 文件中读取的原始符号列表进行一次决定性的“精炼”或“提纯”。它利用 symbol_valid 函数中定义的一套复杂的规则，主要依据符号的地址是否落在内核代码段（.text 和 .init.text）内，来精确地筛选出对运行时符号查找有用的核心符号（主要是函数），并丢弃所有其他无关的符号。

实现原理分析

此机制的核心是一种高效的基于规则的在位过滤（In-Place Filtering）算法，结合了一套精心设计的符号有效性判断策略。

1. 在位过滤算法 (shrink_table):

   • shrink_table 函数实现了一个经典的、高效的在位数组过滤算法。它使用两个索引（或称为“指针”）：i 作为“读取头”，它总是从头到尾遍历整个原始符号表；pos 作为“写入头”，它只在遇到一个有效的符号时才向前移动。
   • 工作流程:
     a. 循环遍历 table[i]。
     b. 对每个 table[i]，调用 symbol_valid 进行判断。
     c. 如果 symbol_valid 返回 true，则将 table[i] 的指针复制到 table[pos] 的位置（if (pos != i) 是一个避免不必要自我复制的微优化），然后 pos 自增。
     d. 如果 symbol_valid 返回 false，则 free(table[i]) 释放该无效符号条目所占用的内存，但 pos 指针不移动。
   • 循环结束后，pos 的值就是有效符号的总数。通过 table_cnt = pos;，数组的逻辑大小被“收缩”了，所有无效的条目都被有效地丢弃了。这种 O(n) 复杂度的算法避免了创建新数组的开销，非常高效。

2. 符号有效性判断策略 (symbol_valid):

   • 这是过滤的“策略引擎”，它定义了什么是一个“好”的符号。在默认模式下（即没有指定 --all-symbols 命令行选项），它遵循一个三层逻辑：
   • 规则 1 (白名单): if (string_starts_with(name, "__start_") || ...)。它无条件地保留所有以 __start_ 或 __stop_ 开头的符号。这些是链接器脚本定义的、用于标记内存区段边界的特殊符号，它们是后续地址范围判断的元数据，必须保留。
   • 规则 2 (核心地址范围过滤): if (symbol_in_range(...) == 0)。这是最主要的过滤器。它要求一个符号的地址必须严格落在 text_ranges 数组所定义的范围之内（即 .text 或 .init.text 段）。text_ranges 的边界是在之前的 check_symbol_range 函数中动态捕获的。这个规则有效地将符号集限制为代码和初始化代码。
   • 规则 3 (边界稳定性特例): if ((s->addr == text_range_text->end && ...))。这是一个处理迭代链接过程中地址稳定性的关键特例。它会丢弃那些地址与 _etext 或 _einittext 完全相同，但名称却不是它们的符号。原因在于：在 kallsyms 的多遍链接过程中，添加 kallsyms 数据段本身可能会使其他符号的地址向后移动。一个在第一遍链接时恰好位于 _etext 地址的符号，在第二遍链接时可能会被挤到 _etext 之后，从而在第二遍的 symbol_valid 检查中被意外丢弃。这会破坏“符号集在迭代中只增不减”的规则。因此，此规则通过提前丢弃这些“不稳定的”边界符号来保证迭代过程的正确性。

代码分析

/**
 * @brief 获取符号条目中的名称字符串。
 * @param s 指向符号条目结构体的常量指针。
 * @return 指向符号名称字符串的指针。
 * @note 符号类型存储在 s->sym[0]，名称从 s->sym[1] 开始。
 */
static char *sym_name(const struct sym_entry *s)
{
	return (char *)s->sym + 1;
}

/**
 * @brief 检查一个符号的地址是否落在给定的地址范围数组中的任何一个范围内。
 * @param s 指向待检查的符号条目结构体的常量指针。
 * @param ranges 指向地址范围结构体数组的常量指针。
 * @param entries ranges 数组中的条目数。
 * @return 如果地址在任何一个范围内则返回1，否则返回0。
 */
static int symbol_in_range(const struct sym_entry *s,
			   const struct addr_range *ranges, int entries)
{
	size_t i;
	const struct addr_range *ar;

	// 遍历所有给定的地址范围。
	for (i = 0; i < entries; ++i) {
		ar = &ranges[i];

		// 检查符号地址是否在当前范围的起始和结束地址之间（包含边界）。
		if (s->addr >= ar->start && s->addr <= ar->end)
			return 1;
	}

	return 0;
}

/**
 * @brief 检查一个字符串 's' 是否以 'prefix' 开头。
 * @param s 待检查的字符串。
 * @param prefix 前缀字符串。
 * @return 如果 s 以 prefix 开头则返回 true，否则返回 false。
 */
static bool string_starts_with(const char *s, const char *prefix)
{
	return strncmp(s, prefix, strlen(prefix)) == 0;
}

static struct addr_range text_ranges[] = {
	{ "_stext",     "_etext"     },
	{ "_sinittext", "_einittext" },
};
#define text_range_text     (&text_ranges[0])
#define text_range_inittext (&text_ranges[1])
/**
 * @brief 判断一个符号是否应该被保留在最终的 kallsyms 表中。
 * @param s 指向待检查的符号条目结构体的常量指针。
 * @return 如果符号有效则返回1，否则返回0。
 */
static int symbol_valid(const struct sym_entry *s)
{
	const char *name = sym_name(s);

	// 默认情况下（没有 --all-symbols 选项），只保留代码段和特定边界符号。
	if (!all_symbols) {
		/*
		 * 规则1 (白名单): 始终保留用于表示区段边界的 __start 和 __stop 符号。
		 */
		if (string_starts_with(name, "__start_") ||
		    string_starts_with(name, "__stop_"))
			return 1;

		/*
		 * 规则2 (核心过滤): 符号必须位于 .text 或 .init.text 代码段内。
		 */
		if (symbol_in_range(s, text_ranges,
				    ARRAY_SIZE(text_ranges)) == 0)
			return 0; // 如果不在任何一个代码段范围内，则丢弃。
		
		/*
		 * 规则3 (边界稳定性特例): 丢弃与 _etext 或 _einittext 地址相同但名称不同的符号。
		 * 这是为了防止在多遍链接过程中，由于 kallsyms 数据段的加入导致地址偏移，
		 * 从而使这些符号在后续遍中被错误地丢弃。
		 */
		if ((s->addr == text_range_text->end &&
		     strcmp(name, text_range_text->end_sym)) ||
		    (s->addr == text_range_inittext->end &&
		     strcmp(name, text_range_inittext->end_sym)))
			return 0;
	}

	// 如果指定了 --all-symbols，或者符号通过了以上所有检查，则保留该符号。
	return 1;
}

/**
 * @brief 遍历全局符号表，移除所有无效的符号，实现表的“收缩”。
 */
static void shrink_table(void)
{
	unsigned int i, pos;

	// pos 是“写入”指针，i 是“读取”指针。
	pos = 0;
	for (i = 0; i < table_cnt; i++) {
		// 使用 symbol_valid() 作为判断条件。
		if (symbol_valid(table[i])) {
			// 如果符号有效，则将其移动到“写入”指针的位置。
			if (pos != i) // 避免不必要的自我复制。
				table[pos] = table[i];
			pos++; // “写入”指针前进。
		} else {
			// 如果符号无效，则释放其内存。
			free(table[i]);
			// “写入”指针不前进，该位置将被下一个有效符号覆盖。
		}
	}
	// 更新符号表的逻辑大小为有效符号的数量。
	table_cnt = pos;
}

sort_symbols 内核符号表的稳定排序与歧义消解

本代码片段是 kallsyms.c 主机端构建工具中负责对内核符号表进行最终排序的核心模块。其主要功能是通过 sort_symbols 函数调用 C 标准库的 qsort，并提供一个高度定制化的比较函数 compare_symbols。这个比较函数实现了一个复杂的多级排序策略，其首要目标是按地址对所有符号进行排序，但更重要的是，它定义了一套精确的规则，用于处理多个不同符号恰好位于同一内存地址时的歧义问题，确保最终的符号表在逻辑上是正确和可预测的。

实现原理分析

此机制的核心是一种带歧义消解的多级稳定排序（Multi-level Stable Sort with Ambiguity Resolution）。compare_symbols 函数是这一原理的精髓，它建立了一个清晰的优先级层次结构来处理地址冲突的符号。

1. 主排序键：地址 (sa->addr vs sb->addr): 这是最优先的排序规则。所有符号都必须首先按照它们的内存地址从小到大进行排列。这是生成 System.map 和后续 kallsyms 数据结构的基础要求，也是 record_relative_base 函数能正确找到最低地址符号的前提。

2. 次级排序键（Tie-breakers for Address Collisions）: 当两个或多个符号地址相同时 (sa->addr == sb->addr)，比较函数会依次应用以下规则来决定它们的相对顺序：

   • a. 强弱符号 (Weakness): wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');。它会优先排列强符号（类型不是 ‘w’ 或 ‘W’）在弱符号之前。这是因为在链接时，如果一个强符号和一个弱符号同名，强符号会覆盖弱符号。在符号表中也反映这一优先级是符合逻辑的。
   • b. 符号类型（代码 vs. 边界）: wa = may_be_linker_script_provide_symbol(sa);。may_be_linker_script_provide_symbol 函数通过启发式规则（检查 __start_, __stop_ 等模式）来识别那些由链接器脚本生成的、用于标记内存区段边界的符号。此排序规则会优先排列“真正的”代码/数据符号，而将这些边界标记符号排在后面。这确保了当一个函数的地址与一个区段的起始地址完全相同时，地址查找会优先返回函数名，而不是边界名。
   • c. 命名约定（公共 vs. 内部）: wa = strspn(sym_name(sa), "_");。此规则计算符号名前导下划线的数量。它会优先排列前导下划线较少的符号。这是基于一个普遍的编码约定，即前导下划线越多的符号，其内部性越强。这有助于将更“公开”的符号名排在前面。
   • d. 稳定性（原始顺序）: return sa->seq - sb->seq;。这是最后的杀手锏。如果经过以上所有规则比较后，两个符号仍然无法区分，此规则将依据它们在输入文件中出现的原始顺序（seq）进行排序。这保证了整个排序过程是稳定的，即对于等价的元素，它们的相对顺序在排序后保持不变。这对于构建过程的可复现性至关重要。

代码分析

/**
 * @brief 通过启发式规则猜测一个符号是否是由链接器脚本提供的边界符号。
 * @param se 指向待检查的符号条目结构体的指针。
 * @return 如果猜测是边界符号则返回1，否则返回0。
 */
static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
{
	const char *symbol = sym_name(se);
	int len = se->len - 1; // 获取真实的符号名长度

	if (len < 8) // 边界符号通常较长
		return 0;

	if (symbol[0] != '_' || symbol[1] != '_') // 通常以 "__" 开头
		return 0;

	// 检查是否匹配 "__start_XXXXX" 模式
	if (!memcmp(symbol + 2, "start_", 6))
		return 1;

	// 检查是否匹配 "__stop_XXXXX" 模式
	if (!memcmp(symbol + 2, "stop_", 5))
		return 1;

	// 检查是否匹配 "__end_XXXXX" 模式
	if (!memcmp(symbol + 2, "end_", 4))
		return 1;

	// 检查是否匹配 "__XXXXX_start" 模式
	if (!memcmp(symbol + len - 6, "_start", 6))
		return 1;

	// 检查是否匹配 "__XXXXX_end" 模式
	if (!memcmp(symbol + len - 4, "_end", 4))
		return 1;

	return 0;
}

/**
 * @brief qsort 的比较函数，用于对符号表进行多级稳定排序。
 * @param a 指向第一个待比较元素的指针 (实际是 struct sym_entry**)。
 * @param b 指向第二个待比较元素的指针 (实际是 struct sym_entry**)。
 * @return -1 (a < b), 0 (a == b), 1 (a > b)。
 */
static int compare_symbols(const void *a, const void *b)
{
	const struct sym_entry *sa = *(const struct sym_entry **)a;
	const struct sym_entry *sb = *(const struct sym_entry **)b;
	int wa, wb;

	/* 规则1: 首先按地址排序 */
	if (sa->addr > sb->addr)
		return 1;
	if (sa->addr < sb->addr)
		return -1;

	/* --- 地址相同，进入歧义消解流程 --- */

	/* 规则2: 按“弱符号”类型排序 (强符号优先) */
	wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W'); // wa=1 if weak
	wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W'); // wb=1 if weak
	if (wa != wb)
		return wa - wb; // 强符号(0)会排在弱符号(1)之前

	/* 规则3: 按“链接器脚本提供”的符号类型排序 (真实符号优先) */
	wa = may_be_linker_script_provide_symbol(sa); // wa=1 if linker symbol
	wb = may_be_linker_script_provide_symbol(sb); // wb=1 if linker symbol
	if (wa != wb)
		return wa - wb; // 真实符号(0)会排在边界符号(1)之前

	/* 规则4: 按前导下划线的数量排序 (下划线少的优先) */
	wa = strspn(sym_name(sa), "_"); // 计算前导 '_' 数量
	wb = strspn(sym_name(sb), "_");
	if (wa != wb)
		return wa - wb; // 下划线少的排在前面

	/* 规则5: 按原始顺序排序 (保证稳定性) */
	// 如果以上所有规则都相同，则保持它们在输入文件中的原始相对顺序。
	return sa->seq - sb->seq;
}

/**
 * @brief 调用 qsort 对全局符号表进行排序。
 */
static void sort_symbols(void)
{
	qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
}

optimize_token_table 与内核符号表压缩算法

本代码片段是Linux内核构建过程中的主机端工具代码（通常位于 scripts/kallsyms.c），其核心功能是对内核符号表（kallsyms）中的符号名称进行压缩。它采用了一种基于统计的贪婪算法，类似于字节对编码（Byte Pair Encoding, BPE）。其目的是通过将频繁出现的字符对（tokens）替换为未在原始符号中使用的单字节索引，从而减小最终内核镜像的大小。

实现原理分析

该算法属于基于字典的压缩算法。它通过多次迭代，构建一个将单字节索引映射到一至两个字节字符序列的“最佳表”（best_table）。

1. 相对基地址记录 (record_relative_base):
   为了进一步压缩符号地址，内核通常存储相对于某个基地址的偏移量而非绝对地址。此函数假定符号表已按地址排序，并记录第一个符号的地址作为基准。这是一种差分编码（Delta Encoding）的预处理步骤。

2. 频率统计与动态更新 (learn_symbol, forget_symbol, build_initial_token_table):
   算法的核心依赖于对所有符号名中相邻字符对（bigrams）出现频率的精确统计。

   • 统计空间被映射为一个大小为 $256 \times 256 = 65536$ (0x10000) 的数组 token_profit。字符对 $(c_1, c_2)$ 的索引计算为 $c_1 + (c_2 \times 256)$。
   • build_initial_token_table 初始化全局频率直方图。
   • 关键在于动态性：当执行压缩替换时，原有的字符对消失，新的字符对（包含压缩索引）产生。forget_symbol 和 learn_symbol 分别用于在替换前后减少旧对和增加新对的计数，维持统计的实时准确性。

3. 贪婪选择与全局替换 (find_best_token, compress_symbols):

   • 贪婪策略: find_best_token 遍历整个 token_profit 数组，找到当前出现频率最高（”收益”最大）的字符对。
   • 全局替换: compress_symbols 负责执行实际的压缩动作。它遍历所有符号，找到目标字符对，将其替换为指定的单字节索引，并利用 memmove 处理字符串缩短后的内存移动。最重要的是，它在替换前后调用 forget/learn 来更新全局频率表，确保后续迭代基于最新的数据。

4. 优化驱动流程 (optimize_result, insert_real_symbols_in_table):
   这是算法的主循环。

   • 首先，insert_real_symbols_in_table 标记出所有在原始符号名中实际存在的单字节字符。这些字符对应的索引不能被用作压缩代号。
   • optimize_result 从 255 到 0 逆向遍历所有可能的单字节槽位。如果某个槽位未被原始字符占用，则它是一个可用的“压缩槽”。
   • 对于每个可用槽，算法找到当前最佳的字符对，将其存入解压字典 (best_table)，并在所有符号中用该槽位的索引替换该字符对。
   • 该过程持续进行，直到没有可用槽位或没有值得压缩的字符对（收益为0）。

代码分析

/* 寻找最小的非绝对符号地址，用作相对寻址的基地址 */
static void record_relative_base(void)
{
	/*
	 * 符号表已经按地址进行了排序。
	 * 取第一个符号的地址作为基地址。
	 */
	if (table_cnt)
		relative_base = table[0]->addr;
}


/* 表查找压缩函数集 */
static int token_profit[0x10000];
/**
 * @brief learn_symbol - 统计一个符号中所有可能的字符对（token）的出现次数
 * @param symbol: 指向符号名字符串的指针
 * @param len: 符号名的长度
 */
static void learn_symbol(const unsigned char *symbol, int len)
{
	int i;

	// 遍历字符串，处理每一对相邻的字符
	for (i = 0; i < len - 1; i++)
		// 计算字符对的索引：symbol[i] 为低字节，symbol[i+1] 为高字节。
		// 增加该字符对在全局收益表中的计数值。
		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
}

/**
 * @brief forget_symbol - 减少一个符号中所有字符对的出现次数
 * @param symbol: 指向符号名字符串的指针
 * @param len: 符号名的长度
 *
 * 此函数用于在符号被压缩（修改）之前，从全局统计中移除其旧的贡献。
 */
static void forget_symbol(const unsigned char *symbol, int len)
{
	int i;

	// 遍历字符串，处理每一对相邻的字符
	for (i = 0; i < len - 1; i++)
		// 减少该字符对在全局收益表中的计数值。
		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
}

/**
 * @brief build_initial_token_table - 执行初始的字符对统计
 *
 * 遍历整个当前的符号表，建立初始的频率直方图。
 */
static void build_initial_token_table(void)
{
	unsigned int i;

	// 遍历所有符号
	for (i = 0; i < table_cnt; i++)
		// 对每个符号调用 learn_symbol 进行统计
		learn_symbol(table[i]->sym, table[i]->len);
}

/**
 * @brief find_token - 在字符串中查找指定的二字节 token
 * @param str: 要搜索的字符串
 * @param len: 字符串长度
 * @param token: 要查找的二字节序列
 * @return 指向找到的 token 在 str 中首次出现位置的指针，未找到则返回 NULL。
 */
static unsigned char *find_token(unsigned char *str, int len,
				 const unsigned char *token)
{
	int i;

	// 线性搜索匹配的字符对
	for (i = 0; i < len - 1; i++) {
		if (str[i] == token[0] && str[i+1] == token[1])
			return &str[i];
	}
	return NULL;
}

/**
 * @brief compress_symbols - 在所有有效符号中替换给定的 token
 * @param str: 要被替换掉的二字节 token
 * @param idx: 用于替换的新单字节索引值
 *
 * 此函数使用采样的符号来动态更新计数。它执行贪婪替换并维护统计一致性。
 */
static void compress_symbols(const unsigned char *str, int idx)
{
	unsigned int i, len, size;
	unsigned char *p1, *p2;

	// 遍历整个符号表
	for (i = 0; i < table_cnt; i++) {

		len = table[i]->len;
		p1 = table[i]->sym;

		/* 在当前符号中查找该 token */
		p2 = find_token(p1, len, str);
		if (!p2) continue; // 如果没有找到，处理下一个符号

		/* 在修改前，减少此符号中当前所有 token 的计数 */
		forget_symbol(table[i]->sym, len);

		size = len;

		// 循环替换符号中出现的所有目标 token
		do {
			// 将 token 的第一个字节替换为压缩索引
			*p2 = idx;
			p2++;
			// 计算剩余部分的长度（减去 token 的第二个字节）
			size -= (p2 - p1);
			// 使用 memmove 将剩余字符串前移一个字节，覆盖 token 的第二个字节
			memmove(p2, p2 + 1, size);
			// 更新当前处理位置指针
			p1 = p2;
			// 符号总长度减 1
			len--;

			// 如果剩余长度小于2，无法再包含 token，退出内循环
			if (size < 2) break;

			/* 在剩余部分继续查找 token */
			p2 = find_token(p1, size, str);

		} while (p2);

		// 更新符号结构体中的长度
		table[i]->len = len;

		/* 增加此符号被压缩后产生的新 token 的计数 */
		learn_symbol(table[i]->sym, len);
	}
}

/**
 * @brief find_best_token - 搜索具有最大收益（出现频率最高）的 token
 * @return 最佳 token 的 16 位组合值（byte1 + (byte2 << 8)）。
 */
static int find_best_token(void)
{
	int i, best, bestprofit;

	// 初始化最佳收益为一个负值
	bestprofit = -10000;
	best = 0;

	// 遍历所有可能的 65536 种字符对组合
	for (i = 0; i < 0x10000; i++) {
		// 如果当前 token 的收益高于已知最佳收益
		if (token_profit[i] > bestprofit) {
			best = i;
			bestprofit = token_profit[i];
		}
	}
	return best;
}

/* the table that holds the result of the compression */
static unsigned char best_table[256][2];
static unsigned char best_table_len[256];
/**
 * @brief optimize_result - 算法核心：计算“最佳”压缩表
 *
 * 驱动整个压缩过程，填充 best_table 并执行替换。
 */
static void optimize_result(void)
{
	int i, best;

	/* 从 255 倒序遍历到 0。
	 * 这种顺序不是绝对必要的，但可能将较低的索引留给原始 ASCII 字符。
	 * 重要的是填满所有未使用的槽位。
	 */
	for (i = 255; i >= 0; i--) {

		/* 如果这个表项槽位是空的（它没有被原始符号中的实际字符使用） */
		if (!best_table_len[i]) {

			/* 找到当前具有最佳收益值的 token */
			best = find_best_token();
			// 如果最佳收益为 0，说明没有更多重复的二字节组可压缩，退出。
			if (token_profit[best] == 0)
				break;

			/* 将该 token 放入“最佳”表中对应的槽位 i */
			best_table_len[i] = 2; // 标记该槽位扩展为 2 个字节
			best_table[i][0] = best & 0xFF; // 低字节
			best_table[i][1] = (best >> 8) & 0xFF; // 高字节

			/* 在所有有效符号中用索引 i 替换此 token */
			compress_symbols(best_table[i], i);
		}
	}
}

/**
 * @brief insert_real_symbols_in_table - 标记原始符号中实际使用的字符
 *
 * 防止压缩算法使用这些字符作为压缩索引，造成冲突。
 */
static void insert_real_symbols_in_table(void)
{
	unsigned int i, j, c;

	// 遍历所有符号
	for (i = 0; i < table_cnt; i++) {
		// 遍历符号中的每个字符
		for (j = 0; j < table[i]->len; j++) {
			c = table[i]->sym[j];
			// 在 best_table 中将该字符映射为自身
			best_table[c][0] = c;
			// 标记该槽位已被占用，长度为 1
			best_table_len[c] = 1;
		}
	}
}

/**
 * @brief optimize_token_table - 优化符号表的顶层函数
 *
 * 协调整个压缩流程。
 */
static void optimize_token_table(void)
{
	// 步骤 1: 建立初始的 token 频率表
	build_initial_token_table();

	// 步骤 2: 识别并锁定原始符号中存在的单字节字符
	insert_real_symbols_in_table();

	// 步骤 3: 执行贪婪压缩循环
	optimize_result();
}

output_label 与 expand_symbol 汇编生成与符号解压

本代码片段包含两个独立的函数。第一个是 output_label，一个用于在 kallsyms 生成的汇编文件中输出标准、对齐的全局符号标签的辅助工具。第二个是 expand_symbol，它是 kallsyms 压缩算法的核心解压引擎，负责在编译时将一个压缩后的符号名递归地展开为其原始的、人类可读的字符串形式。

实现原理分析

1. 汇编标签生成 (output_label):

   • 此函数是一个简单的代码生成器，它将一个常见的汇编模式封装成一个函数调用。
   • globl: 这是一个汇编器伪指令，用于将一个符号的可见性声明为“全局”。这意味着该符号在链接阶段可以被其他目标文件引用。在这里，它使得 C 代码可以引用 kallsyms_names、kallsyms_offsets 等在汇编中定义的数据表。
   • ALGN: 这是一个宏，根据目标平台的指针大小，被定义为相应的对齐伪指令（例如，对于32位平台是 .balign 4）。它的作用是确保紧随其后的标签地址是特定字节数的倍数。这对于性能至关重要，因为许多CPU架构（包括ARMv7-M）在访问自然对齐的数据时效率最高。
   • label:: 这是标准的汇编语法，用于定义一个标签，即把当前地址与一个符号名称关联起来。

2. 递归符号解压 (expand_symbol):

   • 该函数的核心原理是递归查表。kallsyms 的压缩算法可能产生嵌套的压缩。例如，一个高频出现的字符对 “ab” 可能首先被替换为索引 255；随后，”255c” 这个序列本身也可能因为高频出现而被替换为索引 254。因此，best_table[254] 中存储的不是 “abc”，而是压缩后的序列 {255, 'c'}。
   • 递归终止条件（Base Case）: 当函数遇到的一个字节 c 在解压表 best_table 中对应的条目是一个单字节且映射到其自身的字符时（best_table[c][0]==c && best_table_len[c]==1），这个字符就是原始的、未被压缩的“原子”字符。这是递归的最底层，直接将该字符输出。
   • 递归步骤（Recursive Step）: 如果遇到的字节 c 对应的条目不是原子字符，说明 c 是一个压缩标记。函数必须对 best_table[c] 中存储的序列进行解压，这是通过调用自身来完成的。函数将 best_table[c] 的内容作为新的输入，进行递归展开，直到所有遇到的字节都最终分解为原子字符。
   • 由于压缩过程保证了不会出现循环定义（例如 A->B, B->A），这个递归过程保证是有限的，最终会终止。

代码分析

/**
 * @brief output_label - 在汇编文件中输出一个全局的、对齐的标签。
 * @param label: 要输出的标签字符串。
 *
 * 这是一个辅助函数，用于生成标准的汇编标签定义。
 */
static void output_label(const char *label)
{
	// .globl 伪指令使标签对于链接器是全局可见的，允许其他文件引用它。
	printf(".globl %s\n", label);
	// ALGN 是一个宏，会展开为 .balign 4 (对于32位系统)，确保标签地址4字节对齐。
	printf("\tALGN\n");
	// 定义标签本身。
	printf("%s:\n", label);
}


/**
 * @brief expand_symbol - 递归地解压一个压缩的符号。
 * @param data: 指向压缩符号名数据的指针。
 * @param len: 压缩数据的长度。
 * @param result: 用于存放解压后结果字符串的缓冲区。
 * @return 解压后字符串的实际长度。
 *
 * 当此函数被调用时，解压字典（best_table）本身可能也包含压缩的条目，
 * 因此函数必须是递归的才能完全展开符号。
 */
static int expand_symbol(const unsigned char *data, int len, char *result)
{
	int c, rlen, total=0;

	// 循环处理压缩数据中的每一个字节
	while (len) {
		c = *data; // 获取当前字节作为索引
		/*
		 * 如果解压表中该索引对应的条目是一个单字节，且就是其自身，
		 * 这说明它是一个“原子”字符，不是一个压缩标记。
		 */
		if (best_table[c][0]==c && best_table_len[c]==1) {
			// 将原子字符直接写入结果缓冲区
			*result++ = c;
			total++;
		} else {
			/*
			 * 否则，该索引是一个压缩标记，需要递归地展开其所代表的序列。
			 */
			rlen = expand_symbol(best_table[c], best_table_len[c], result);
			// 累加递归解压出的字符串长度
			total += rlen;
			// 将结果缓冲区的指针向后移动相应的长度
			result += rlen;
		}
		// 处理下一个压缩数据字节
		data++;
		len--;
	}
	// 在解压后的字符串末尾添加空终止符
	*result=0;

	return total;
}

稀疏索引加速 (kallsyms_markers) 机制的原理

这是一种典型的二级索引（Two-Level Indexing）策略，旨在解决在大型、连续但非定长的数据流中进行高效查找的问题。

1. 问题陈述：没有 kallsyms_markers 的世界

首先，我们必须理解它要解决的根本问题。内核符号数据在 kallsyms_names 中是这样存储的：

[len1][name1][len2][name2][len3][name3] ... [len_N][name_N]

其中：

• [lenX] 是符号 nameX 的长度，采用 1 或 2 字节的 ULEB128 编码。
• [nameX] 是压缩后的符号名称字节序列。

假设内核需要查找第 i 个符号的名称（例如，在打印堆栈回溯时，通过地址找到了第 i 个符号的偏移，现在需要它的名字）。如果没有 kallsyms_markers，查找过程将是这样的：

1. 从头开始：将指针指向 kallsyms_names 的起始位置。
2. 顺序解码和跳过：
   • 读取第一个符号的长度 len1（需要解码 ULEB128，可能是1或2字节）。
   • 将指针向后移动 len1 个字节，跳过第一个符号的名称。
   • 现在指针位于第二个符号的长度 len2 处。
3. 重复：重复第 2 步 i-1 次。每次都要解码一个长度，然后根据该长度进行一次指针移动。
4. 找到目标：在重复 i-1 次后，指针最终会停在第 i 个符号的长度 len_i 处。此时，内核才能读取并解压第 i 个符号的名称。

这个过程的时间复杂度是 O(i)，即与要查找的符号序号成正比。如果要查找的符号在列表的末尾（例如，第 60000 个符号），内核就必须对前面的 59999 个符号逐一进行“解码长度-跳过名称”的操作。这在运行时，尤其是在需要快速响应的内核 panic 期间，是无法接受的低效。

2. 解决方案：kallsyms_markers 的二级索引机制

kallsyms_markers 表就像一本书的“章节起始页码表”。它并不记录每一页的页码，而只记录每章第一页的页码，从而允许你快速翻到任何一章。

构建过程（在编译时）

如代码所示，在生成 kallsyms_names 流的同时，会创建一个 markers 数组。

• 一个计数器 off 持续追踪当前在 kallsyms_names 流中的字节偏移量。
• for (i = 0; i < table_cnt; i++) 循环每处理一个符号，off 就会增加。
• if ((i & 0xFF) == 0) 这个条件判断 i 是否是 256 的整数倍（i % 256 == 0）。
• 当条件成立时（即处理第 0、256、512 … 个符号时），就执行 markers[i >> 8] = off;，将当前的偏移量 off 存入 markers 数组的相应位置。i >> 8 等价于 i / 256。

最终，markers 数组看起来像这样：

• markers[0] = 第 0 个符号在 kallsyms_names 中的起始偏移。
• markers[1] = 第 256 个符号在 kallsyms_names 中的起始偏移。
• markers[2] = 第 512 个符号在 kallsyms_names 中的起始偏移。
• …

查找过程（在运行时）

现在，当内核需要查找第 i 个符号的名称时，过程被优化为：

1. 计算标记点索引：计算 marker_idx = i >> 8 (即 i / 256)。这能立刻告诉内核应该使用哪个标记点。
2. 快速跳转（粗定位）：直接从 kallsyms_markers 表中读取 start_offset = markers[marker_idx]。然后将文件流指针直接设置为 kallsyms_names + start_offset。这一步是 O(1) 的，它代替了之前可能需要成千上万次的解码-跳过操作。
3. 计算块内起始符号：计算出这个标记点对应的符号序号 start_symbol_idx = marker_idx << 8 (即 (i / 256) * 256)。
4. 小范围线性扫描（精定位）：从 start_symbol_idx 开始，执行前述的“解码长度-跳过名称”操作，总共执行 i - start_symbol_idx 次。由于 0 <= (i - start_symbol_idx) < 256，这个线性扫描的次数最多不超过 255 次。

这个新过程的时间复杂度变成了 O(1) + O(k)，其中 O(1) 是查表跳转的开销，k 是一个固定的小常数（最大为255）。因此，无论要查找的符号在列表中的位置有多靠后，查找时间都基本是恒定的，效率得到了极大的提升。

3. “空间换时间”的权衡分析

这是一种经典的工程权衡。

• 付出的空间 (Space)：我们需要额外存储 kallsyms_markers 这个数组。其大小为 (符号总数 / 256) * 4 字节（在32位系统上）。假设内核有 60,000 个符号，那么这个表的大小约为 (60000 / 256) * 4 ≈ 235 * 4 = 940 字节。对于一个数MB大小的内核镜像来说，增加不足 1KB 的只读数据来换取性能的巨大提升，是非常划算的。

• 赢得的时间 (Time)：将一个 O(N) 的查找操作，优化为了一个近似 O(1) 的操作。这对于系统的实时响应性，尤其是在进行调试和故障诊断时，是至关重要的。

write_src: 序列化压缩后的内核符号表

本代码片段是 Linux 内核构建工具链的一部分，其核心功能是将经过压缩算法处理后的内核符号表（kallsyms）数据，序列化为汇编语言源文件。它负责生成一系列定义好的数据表，包括压缩后的符号名称流、用于快速查找的标记、解压字典、以及相对编码的符号地址。这些数据表最终会被汇编器和链接器处理，成为内核镜像中 .rodata 只读数据段的一部分。

实现原理分析

该函数将内存中的压缩数据结构，通过一系列精心设计的格式，转换为静态的、可链接的汇编数据。其设计目标是在保证运行时查找效率的同时，最大限度地减小存储占用。

1. 可变长数据编码 (ULEB128):

   • 在输出压缩的符号名称 (kallsyms_names) 时，每个名称的长度不是用固定的4字节整数存储，而是采用了 ULEB128 (Unsigned Little Endian Base 128) 编码。
   • 对于长度小于等于127 (0x7F) 的符号，长度只用1个字节表示。
   • 对于更长的符号，第一个字节的最高位被置1，用于表示后续还有字节，而低7位存储长度的低7位。第二个字节存储长度的高位。这种编码方式使得绝大多数短符号名能节省3个字节的长度存储开销。

2. 稀疏索引加速 (kallsyms_markers):

   • 线性扫描整个压缩的符号名称流 (kallsyms_names) 来查找第 N 个符号会非常慢。为了加速这个过程，代码每隔256个符号，就记录下当前在名称流中的偏移量，并存入 kallsyms_markers 表。
   • 在运行时，要查找第 i 个符号的名称，内核可以先通过 markers[i >> 8] (即 markers[i / 256]) 快速跳转到附近的位置，然后再从此位置开始线性扫描最多255个符号，极大地提高了查找效率。这是一种典型的空间换时间优化。

3. 解压字典的序列化 (kallsyms_token_table, kallsyms_token_index):

   • kallsyms_token_table 存储了从压缩索引（0-255）到原始字符串（1或2字节）的映射。它被输出为一个由多个 \0 结尾的字符串拼接而成的大字符串。
   • kallsyms_token_index 是一个辅助表，存储了 kallsyms_token_table 中每个字符串的起始偏移量。运行时，当解压器遇到一个压缩索引 c 时，可以直接通过 kallsyms_token_index[c] 获得对应字符串的地址，实现了 O(1) 复杂度的字典查询。

4. 地址的相对编码 (kallsyms_offsets, kallsyms_relative_base):

   • 为了使符号表与内核代码的位置无关（position-independent），所有符号的地址不存储绝对值，而是存储相对于一个基准地址 (relative_base) 的32位偏移量。
   • 这个基准地址本身，又被存储为相对于内核代码段起始符号 _text 的偏移。运行时，内核的符号查找代码首先获取 _text 的绝对地址，然后加上 kallsyms_relative_base 的值，计算出符号表的绝对基地址，最后才能通过 kallsyms_offsets 中的偏移量解析出任意符号的绝对地址。

代码分析

/**
 * @brief write_src - 将所有处理过的符号表数据写入到标准输出，格式为汇编源文件。
 */
static void write_src(void)
{
	unsigned int i, k, off;
	// 用于存储解压字典中每个字符串的偏移量
	unsigned int best_idx[256];
	// 指向标记表的指针，该表用于加速符号名称的查找
	unsigned int *markers;
	unsigned int markers_cnt;
	// 临时缓冲区，用于存储解压后的符号名
	char buf[KSYM_NAME_LEN];

	// --- 汇编文件头 ---
	// 打印预处理指令，根据目标平台的字长（32位或64位）定义指针和对齐伪指令。
	// 对于STM32H750 (ARMv7-M)，BITS_PER_LONG 为 32。
	printf("#include <asm/bitsperlong.h>\n");
	printf("#if BITS_PER_LONG == 64\n");
	printf("#define PTR .quad\n");
	printf("#define ALGN .balign 8\n");
	printf("#else\n");
	printf("#define PTR .long\n");
	printf("#define ALGN .balign 4\n");
	printf("#endif\n");

	// 将数据放入 .rodata (只读数据) 段
	printf("\t.section .rodata, \"a\"\n");

	// --- 符号总数 ---
	output_label("kallsyms_num_syms");
	printf("\t.long\t%u\n", table_cnt);
	printf("\n");

	// --- 压缩的符号名称流 (kallsyms_names) ---
	// 计算标记点的数量，每256个符号一个标记点
	markers_cnt = (table_cnt + 255) / 256;
	markers = xmalloc(sizeof(*markers) * markers_cnt);

	output_label("kallsyms_names");
	off = 0; // 当前在名称流中的偏移量
	for (i = 0; i < table_cnt; i++) {
		// 每256个符号，记录一次当前偏移量到 markers 数组
		if ((i & 0xFF) == 0)
			markers[i >> 8] = off;
		// 记录符号在地址排序表中的原始序号
		table[i]->seq = i;

		// 检查并确保符号长度不为零
		if (table[i]->len == 0) {
			fprintf(stderr, "kallsyms failure: "
				"unexpected zero symbol length\n");
			exit(EXIT_FAILURE);
		}
		// 检查符号长度是否超出 ULEB128 两字节编码的最大范围 (16383)
		if (table[i]->len > 0x3FFF) {
			fprintf(stderr, "kallsyms failure: "
				"unexpected huge symbol length\n");
			exit(EXIT_FAILURE);
		}

		// 使用 ULEB128 编码符号长度
		if (table[i]->len <= 0x7F) {
			// 长度小于等于127，用单字节编码
			printf("\t.byte 0x%02x", table[i]->len);
			off += table[i]->len + 1; // 偏移增加：长度(1) + 符号本身
		} else {
			// 长度大于127，用双字节编码
			printf("\t.byte 0x%02x, 0x%02x",
				(table[i]->len & 0x7F) | 0x80, // 低7位，最高位置1
				(table[i]->len >> 7) & 0x7F);  // 高7位
			off += table[i]->len + 2; // 偏移增加：长度(2) + 符号本身
		}
		// 逐字节输出压缩后的符号名
		for (k = 0; k < table[i]->len; k++)
			printf(", 0x%02x", table[i]->sym[k]);

		// 为了汇编文件的可读性，将符号解压回原名并作为注释打印
		expand_symbol(table[i]->sym, table[i]->len, buf);
		strcpy((char *)table[i]->sym, buf);
		printf("\t/* %s */\n", table[i]->sym);
	}
	printf("\n");

	// --- 名称流标记表 (kallsyms_markers) ---
	output_label("kallsyms_markers");
	for (i = 0; i < markers_cnt; i++)
		printf("\t.long\t%u\n", markers[i]);
	printf("\n");
	free(markers);

	// --- 解压字典字符串表 (kallsyms_token_table) ---
	output_label("kallsyms_token_table");
	off = 0; // 当前在 token_table 中的偏移量
	for (i = 0; i < 256; i++) {
		best_idx[i] = off; // 记录第i个 token 字符串的起始偏移
		// 将 token (可能为1或2字节) 解压为原始字符串
		expand_symbol(best_table[i], best_table_len[i], buf);
		// 以.asciz伪指令输出，自动添加'\0'结尾
		printf("\t.asciz\t\"%s\"\n", buf);
		off += strlen(buf) + 1;
	}
	printf("\n");

	// --- 解压字典索引表 (kallsyms_token_index) ---
	output_label("kallsyms_token_index");
	for (i = 0; i < 256; i++)
		printf("\t.short\t%d\n", best_idx[i]); // 输出每个 token 字符串的偏移
	printf("\n");

	// --- 符号地址偏移量表 (kallsyms_offsets) ---
	output_label("kallsyms_offsets");
	for (i = 0; i < table_cnt; i++) {
		// 计算符号地址相对于基地址的偏移
		long long offset = table[i]->addr - relative_base;
		// 检查偏移量是否在无符号32位整数范围内
		if (offset < 0 || offset > UINT_MAX) {
			fprintf(stderr, "kallsyms failure: "
				"relative symbol value %#llx out of range\n",
				table[i]->addr);
			exit(EXIT_FAILURE);
		}
		printf("\t.long\t%#x\t/* %s */\n", (int)offset, table[i]->sym);
	}
	printf("\n");

	// --- 相对基地址本身 (kallsyms_relative_base) ---
	output_label("kallsyms_relative_base");
	// 将基地址表示为相对于内核代码段起始 (_text) 的偏移，以实现位置无关
	if (_text <= relative_base)
		printf("\tPTR\t_text + %#llx\n", relative_base - _text);
	else
		printf("\tPTR\t_text - %#llx\n", _text - relative_base);
	printf("\n");

	// --- 按名称排序的序号表 (kallsyms_seqs_of_names) ---
	// 此表用于按名称查找符号
	sort_symbols_by_name();
	output_label("kallsyms_seqs_of_names");
	for (i = 0; i < table_cnt; i++)
		// 输出该符号在地址排序表中的原始序号（seq），使用3个字节存储
		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
			(unsigned char)(table[i]->seq >> 16),
			(unsigned char)(table[i]->seq >> 8),
			(unsigned char)(table[i]->seq >> 0),
		       table[i]->sym);
	printf("\n");
}