各位好，欢迎来到今天的内核极客大会。我是你们的领路人。
今天我们不谈虚的，咱们来聊聊那个让无数内核开发者头秃的东西——全局符号表。具体点说，是针对那些像喷泉一样喷涌而出的海量常量定义的查找优化。
大家想象一下，现在的Linux内核，代码量早已突破千万行。每次编译、每次加载模块，背后都有成千上万个 #define 在飞。这些常量，有的用来做错误码，有的用来做版本号，有的干脆就是某种魔数。在旧版本的内核里，查找这些常量就像是在一个没装灯泡的杂乱仓库里找一颗螺丝钉。
这不仅仅是慢，这是在浪费CPU的时间。CPU是宇宙中最昂贵的资源，如果它在那儿把内存翻得哗哗响，却只为了找一个 CONFIG_MUTEX 的定义，那简直是对能源的亵渎。
那么，我们怎么解决呢？是不是直接换一个更大的哈希表？哦不，那太天真了。哈希表有冲突，需要扩容，而且内存开销大，缓存命中率低。是不是用红黑树？太重了，维护一棵完美的平衡树，每次插入都要旋转，对于这种“海量常量”来说，太累赘了。
今天，我要给你们展示的，是新版内核里那些隐秘角落里的“黑科技”。我们不谈花哨的算法，我们谈的是空间换时间，谈的是对CPU缓存行的极致压榨。
我们要讲的主角有两个，一位是基数树（Radix Tree），另一位是跳表（Skip List）。别被这些名字吓到了，它们听起来很学术，但原理其实非常接地气。
第一幕：杂乱仓库的“天花板”设计——基数树
首先，我们来看看基数树。为什么叫基数树？因为它用的是“基数”作为索引，也就是二进制。它是树吗？在某种意义上，它更像是树，但又不像树。它是一种稀疏多维数组。
在内核中，传统的哈希表就像是一个个杂乱的抽屉，每个抽屉里塞着很多东西，而且抽屉的大小还不固定，这就导致了严重的内存碎片。而基数树，它是零空闲开销的。
什么是零空闲开销？就是说，如果你有一个从 0x00000000 到 0x0000FFFF 的范围，哈希表里哪怕你只用了其中两个数，为了存这两个数，哈希表也要预留一大堆空间。但在基数树里，我只用多少，就占多少空间。如果中间空缺了，我就不占，直接跳过。
想象一下，你在一个电话本里找人。你不会一页一页翻，你直接看名字的第一个字。基数树就是这个逻辑的极致版。它把地址的每一位都拆开，作为树的一个层级。
比如你要找地址 0xA1B2C3D4。
在第一层，我们看最高位 A。
在第二层，看接下来的位 1。
…
直到最后一层。
如果这一层没有，那就意味着这个地址不存在。这有什么好处？
巨大的缓存亲和性。
在传统的树结构里，一个节点的指针可能会散落在内存的各个角落，导致CPU在遍历树的时候，不断地去取指令、取数据，缓存行（Cache Line）疯狂失效。而在基数树里，数据的存储是连续的（尽管是稀疏的连续），CPU预取机制可以大显身手，像流水线一样把数据拉进缓存。
深入代码：基数树的极简实现
为了证明基数树的威力，我们不看那个几千行的Linux源码，我们自己手搓一个简化版的，看看它是如何处理海量常量的。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// 为了演示，我们假设常量就是简单的整数ID
typedef struct {
uint32_t key;
void *value;
} constant_entry;
// 基数树的节点结构
// 注意这里没有左指针、右指针、甚至没有子节点指针数组！
// 它只有一个连续的指针数组
typedef struct radix_node {
struct radix_node **children; // 这就是它的“孩子”
constant_entry *entry; // 只有叶子节点才存数据
} radix_node;
// 初始化一棵空树
radix_node *radix_tree_create() {
// 顶层节点总是存在的
radix_node *root = (radix_node *)malloc(sizeof(radix_node));
// 起始时只有根节点，children数组可以是空的，或者可以初始化为0
root->children = NULL;
root->entry = NULL;
return root;
}
// 插入常量
// key是32位整数，我们将它看作32层“台阶”
void radix_tree_insert(radix_node *root, uint32_t key, void *value) {
radix_node *current = root;
uint32_t shift = 31; // 从最高位开始遍历
while (shift >= 0) {
uint32_t bit = (key >> shift) & 1; // 取出当前这一位的 0 或 1
// 如果当前层没有对应的分支（bit是0，但children[0]是NULL）
if (current->children == NULL || current->children[bit] == NULL) {
// 动态分配这一层的新节点，不需要预先分配整个树的大小！
// 这就是零开销的精髓
radix_node *new_node = (radix_node *)malloc(sizeof(radix_node));
new_node->children = NULL;
new_node->entry = NULL;
// 挂载新节点
if (current->children == NULL) {
current->children = (radix_node **)calloc(2, sizeof(radix_node*));
}
current->children[bit] = new_node;
current = new_node;
} else {
// 如果已经有这个分支，顺着路走
current = current->children[bit];
}
shift--;
}
// 到达叶子节点，挂载数据
// 注意：在真实内核中，这里会有复杂的竞争处理（RCU等）
if (current->entry != NULL) {
// 简单的覆盖逻辑，实际中可能需要合并或报错
printf("Warning: Overwriting key %un", key);
} else {
current->entry = (constant_entry *)malloc(sizeof(constant_entry));
current->entry->key = key;
current->entry->value = value;
}
}
// 查找常量
void *radix_tree_lookup(radix_node *root, uint32_t key) {
radix_node *current = root;
uint32_t shift = 31;
while (shift >= 0) {
uint32_t bit = (key >> shift) & 1;
// 如果这一层不存在，或者这一层的bit指向NULL，那完了，找不到
if (current->children == NULL || current->children[bit] == NULL) {
return NULL;
}
current = current->children[bit];
shift--;
}
// 到了底，直接取数据
return current ? current->entry->value : NULL;
}
// 清理内存（仅供演示）
void radix_tree_destroy(radix_node *root) {
if (!root) return;
if (root->children) {
for (int i = 0; i < 2; i++) {
radix_tree_destroy(root->children[i]);
}
free(root->children);
}
if (root->entry) {
free(root->entry);
}
free(root);
}
int main() {
radix_node *tree = radix_tree_create();
// 插入一堆随机常量
for (int i = 0; i < 100000; i++) {
radix_tree_insert(tree, i, (void *)(long)i * 100);
}
// 查找
int key_to_find = 99999;
void *res = radix_tree_lookup(tree, key_to_find);
if (res) {
printf("Found key %d, value %ldn", key_to_find, (long)res);
} else {
printf("Not found!n");
}
radix_tree_destroy(tree);
return 0;
}看，这就是基数树的魔力。上面这段代码，没有任何指针的“浪费”。如果你想找 0x80000000，它只需要创建根节点下的一个子节点，根本不需要去管那些奇数地址怎么存。对于常量这种稀疏分布的数据，基数树简直是量身定做的。
在Linux内核的 mm 子系统里，基数树被用来将物理页面帧号映射到虚拟地址。那是真正的海量常量（物理地址）查找场景。如果没有基数树，内核早就内存溢出或者缓存爆炸了。
第二幕：那个“作弊”的随机分布者——跳表
好了，基数树很强，但它要求键是连续的或者有序的。如果你有一堆乱七八糟的常量（比如模块ID、随机种子、非连续的错误码），基数树虽然也能用，但树的高度可能会因为乱序而变得很高，导致查找路径变长。
这时候，跳表（Skip List） 就登场了。
跳表是数学家们在1990年发明的，它是为了解决平衡二叉搜索树（BST）的并发问题而生的。它的核心思想非常简单粗暴：在有序链表的基础上，加一层一层的“高速公路”。
想象一下，你在一个只有一排台阶的楼梯上找楼顶（有序查找）。你需要一级一级地往上爬，效率低。现在，你在每10级台阶的顶部加一根横梁，让你能直接跨过去。这就是跳表。
跳表是一个概率性数据结构。它不是像红黑树那样严格平衡的，而是通过随机概率来决定某个节点是不是有一条“横梁”。这个概率通常是50%。也就是说，每层有50%的节点有上一层指针，有25%的节点有两层指针，以此类推。
为什么它快？
- 平均复杂度 O(log n)：和红黑树一样，但是没有复杂的旋转操作！插入和删除只需要修改指针，不用调整树结构。
- 缓存友好：相比于红黑树那种散乱在内存各个角落的节点，跳表的层级是顺序排列的，CPU的缓存命中率极高。
- 并行友好：因为不需要加锁去旋转树，修改操作非常容易实现。
对于内核里的“海量常量”，尤其是那些在运行时动态注册、动态销毁的常量（比如Netfilter的规则表），跳表是完美的选择。它允许内核在不牺牲太多性能的前提下，极大地提高并发插入和删除的吞吐量。
深入代码：跳表的极简实现
下面是一个处理海量常量（Key-Value对）的跳表实现。注意看它的层级结构。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
typedef struct skip_list_node {
int key;
int value;
// 指向所有层级的下一跳
struct skip_list_node **forward;
} skip_list_node;
typedef struct {
int level;
skip_list_node *header;
} skip_list;
// 随机层生成器
// 概率是50%，所以random() % 2 是最简单的模拟
int random_level(int max_level) {
int level = 1;
while ((rand() % 2) && (level < max_level)) {
level++;
}
return level;
}
skip_list* skiplist_create(int max_level) {
skip_list *sl = (skip_list*)malloc(sizeof(skip_list));
sl->level = 1;
// 头节点不需要存储数据，所有层级的next都指向它
sl->header = (skip_list_node*)malloc(sizeof(skip_list_node));
sl->header->key = -1;
sl->header->value = -1;
sl->header->forward = (skip_list_node**)malloc(sizeof(skip_list_node*) * max_level);
for (int i = 0; i < max_level; i++) {
sl->header->forward[i] = NULL;
}
return sl;
}
void sl_insert(skip_list *sl, int key, int value) {
skip_list_node *update[32]; // 假设最大层级不超过32（足够存4G的key了）
skip_list_node *current = sl->header;
// 从最顶层开始找
for (int i = sl->level - 1; i >= 0; i--) {
// 往后跳，直到找到一个比key大的节点，或者到了链表尾
while (current->forward[i] != NULL && current->forward[i]->key < key) {
current = current->forward[i];
}
// 记录这一层需要更新的节点
update[i] = current;
}
current = current->forward[0];
// 如果key已存在，更新值（如果是常量查找，通常不允许覆盖，或者视为修改）
if (current != NULL && current->key == key) {
printf("Key %d already exists, updating value.n", key);
current->value = value;
return;
}
// 决定新节点的层数
int rlevel = random_level(6); // 假设最大6层
if (rlevel > sl->level) {
for (int i = sl->level; i < rlevel; i++) {
update[i] = sl->header;
}
sl->level = rlevel;
}
// 创建新节点
skip_list_node *new_node = (skip_list_node*)malloc(sizeof(skip_list_node));
new_node->key = key;
new_node->value = value;
new_node->forward = (skip_list_node**)malloc(sizeof(skip_list_node*) * rlevel);
// 链接节点
for (int i = 0; i < rlevel; i++) {
new_node->forward[i] = update[i]->forward[i];
update[i]->forward[i] = new_node;
}
printf("Inserted key %d at level %dn", key, rlevel);
}
int sl_search(skip_list *sl, int key) {
skip_list_node *current = sl->header;
// 同样从顶层开始，快速定位
for (int i = sl->level - 1; i >= 0; i--) {
while (current->forward[i] != NULL && current->forward[i]->key < key) {
current = current->forward[i];
}
}
// 检查下一级是否匹配
current = current->forward[0];
if (current != NULL && current->key == key) {
printf("Found key %d, value: %dn", key, current->value);
return current->value;
} else {
printf("Key %d not found.n", key);
return -1;
}
}
int main() {
srand(time(NULL));
skip_list *sl = skiplist_create(6);
// 模拟插入海量常量
// 假设这些是内核里的各种错误码或配置常量
for (int i = 0; i < 100; i++) {
int key = rand() % 200;
sl_insert(sl, key, i * 10);
}
// 查找
sl_search(sl, 50);
sl_search(sl, 999);
return 0;
}看这段代码，sl_insert 函数里没有递归，没有复杂的树平衡逻辑。它就是顺着指针往下插。对于常量表来说，这种“写时复制”式的修改非常友好，不容易出现锁竞争导致的死锁或者性能抖动。
第三幕：如何将它们塞进你的内核？
光懂原理不行，关键是怎么用在工程里。在内核中，我们很少直接写 struct 然后手动管理指针。我们需要考虑内存分配器（Slab/Slub）和并发控制（RCU）。
对于海量常量，我们通常会有一个 global_constant_table 结构体。
// 伪代码：内核风格的常量表结构
struct global_constants {
// 使用基数树还是跳表？看你的场景。
// 如果是内存映射，用 radix_tree。
// 如果是模块注册，用 skip_list。
struct radix_tree_root root;
struct rw_semaphore lock; // 保护并发修改
};
// 初始化
void constants_init(void) {
radix_tree_init(&global_constants.root);
init_rwsem(&global_constants.lock);
}
// 注册一个常量
void register_constant(uint64_t key, const void *value) {
down_write(&global_constants.lock);
// 这里使用 RCU 或者 atomic_t 来保护插入
radix_tree_insert(&global_constants.root, key, (void*)value);
up_write(&global_constants.lock);
}
// 查找一个常量（读操作，必须极快！）
const void *find_constant(uint64_t key) {
// 读锁，允许并发读，但禁止写
down_read(&global_constants.lock);
void *value = radix_tree_lookup(&global_constants.root, key);
up_read(&global_constants.lock);
return value;
}这里有个关键点：读操作的性能。在我们的场景下，常量表通常是在内核启动时初始化一次，之后主要是查找。查找频率远高于插入频率。
所以，对于查找函数，我们可以用 RCU（Read-Copy-Update）。
RCU 是什么？它是一种“延迟释放”技术。当你读取一个指针时，你不加锁，直接拿走。如果这时候有人修改了这个指针，CPU 会悄悄地把旧数据复制一份，修改新的数据，然后在旧数据彻底没人用的时候（比如所有中断处理都退出了），再把它回收。
这极大地消除了读锁的开销。
// RCU 优化的查找
const void *find_constant_rcu(uint64_t key) {
// 获取 RCU 读取端的临界区
rcu_read_lock();
// 查找
// 在 Linux 内核中，radix_tree_lookup 通常配合 rcu_dereference 使用
// 这里简化展示
const void *val = radix_tree_lookup(&global_constants.root, key);
rcu_read_unlock();
return val;
}第四幕：性能分析——到底快了多少？
我们来做个思想实验。假设我们有 100 万个常量。
场景 A：传统哈希表
- 内存占用：假设哈希表是固定的（比如2M条目），那么即使只用了1M条，也有1M条是浪费的。内存占用大。
- 查找速度：平均两次比较。但是，如果哈希冲突多了，链表就变长，查找就变成了 O(n)。而且，因为内存碎片化严重，CPU 缓存经常失效。
场景 B：红黑树
- 内存占用：每个节点都有额外的颜色位、父指针、子指针。内存占用是哈希表的 3-4 倍。
- 查找速度：O(log n)。大概是 20 次比较。
- 问题：每次插入/删除后的平衡调整（旋转），是昂贵的原子操作，会阻塞 CPU。
场景 C：基数树（我们的主角）
- 内存占用：极低。100万个稀疏常量可能只需要几兆内存。
- 查找速度：平均 30-40 次位操作（比比较整数快）。因为内存局部性好，缓存命中率接近 100%。
- 适合场景：常量空间是稀疏的（比如错综复杂的虚拟地址范围）。
场景 D：跳表（我们的助手）
- 内存占用：比红黑树稍高，因为有额外的层指针，但比哈希表紧凑。
- 查找速度：平均 20 次比较。
- 适合场景：动态增删频繁，且对并发要求高。
第五幕：实战中的“坑”与“特技”
在实际的内核开发中，优化符号表不仅仅是换数据结构。还有几个细节是大家容易忽略的：
-
对齐（Alignment）：
千万不要忘了__attribute__((aligned(64)))。如果你定义了一个结构体数组，没有对齐，CPU 可能需要读两次缓存行才能拿到一个完整的数据。在处理海量常量时，这点微小的延迟会被放大 100 倍。保证内存布局对 CPU 友好，比算法本身更重要。 -
位压缩：
看看你的常量。如果 key 是uint32_t，但只有低 16 位在用，别浪费内存！把 key 压缩一下，或者直接把常量存在 key 的低半部分。这会让基数树的层级更深一点（从32层变16层），但极大地节省了内存。 -
预取：
在遍历查找前，手动插入prefetch(&node->forward[1])。告诉 CPU：“嘿，别闲着，先把下一层的数据拿进来。” 在跳表中，这招非常有效，因为你总是先走高层，再走底层，预取器非常容易猜中你的意图。
结语
好了，今天的讲座就到这里。
我们回顾一下。面对海量常量的查找，传统的哈希表太占地方，红黑树太重且慢。新版内核选择了 基数树 和 跳表 作为主力军。基数树凭借零空闲开销和极致的内存局部性，成为了内存映射类常量的首选；而跳表则凭借概率性的平衡和简单的并发控制，统治了动态注册表。
记住，好的代码不是写得最聪明的代码，而是让硬件（CPU/内存）跑得最舒服的代码。
当你下次在内核里看到那些几千行的宏定义，或者在内核日志里看到 radix_tree 相关的打印时，希望你能会心一笑——你懂得了它们背后的故事。
现在，去优化你的符号表吧，别让那些常量在缓存里流浪了。