Linux 内核基数树深度解析：原理、实现与两大核心应用场景

Linux 内核基数树深度解析

基数树是 Linux 内核中高频使用的数据结构，兼具多叉树与多级索引特性，实现「时间换空间」的动态 ID→指针映射。本文从数据结构定义、核心操作源码、文件页缓存与 IPC 对象管理两大应用场景、同步机制五个维度展开。

数据结构定义

// 树根
struct radix_tree_root {
    unsigned int height;      // 树高
    gfp_t gfp_mask;           // 内存分配标志
    struct radix_tree_node *rnode; // 根节点指针
};

// 树节点
struct radix_tree_node {
    unsigned int height;      // 距叶子高度
    unsigned int count;       // 非空子节点数
    void *slots[RADIX_TREE_MAP_SIZE]; // 子节点指针数组
    unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; // 标签位图
};

关键常量：RADIX_TREE_MAP_SHIFT = 6（每层 6 bit，64 叉），RADIX_TREE_MAP_SIZE = 64，RADIX_TREE_MAX_TAGS = 2（DIRTY/WRITEBACK）。

核心操作源码走读

1. 插入 radix_tree_insert()

• 索引超限 → radix_tree_extend() 增高树高（在根上方添加单支路径）
• 自顶向下按 shift = (height-1)*MAP_SHIFT 分段取槽位
• 槽位为空 → radix_tree_node_alloc() 分配中间节点
• 到达第 0 层 → 槽位存入 item 指针，更新 count 与标签

2. 删除 radix_tree_delete()

• 记录搜索路径 path[]（含哨兵）
• 自底向上清空槽位、递减 count
• 遇到 count > 0 节点停止回溯；若为根节点 → radix_tree_shrink() 尝试降高
• 全空 → 释放根节点，树高置 0

3. 查找 radix_tree_lookup()

• 自顶向下按位分段索引 slots[(index>>shift)&MASK]
• 中途遇 NULL 返回 NULL；到达高度 0 返回目标指针
• 时间复杂度 O(log₆₄N) ≈ O(log₂N / 6)

4. 扩容/收缩策略

• 扩容：在根上方堆叠单支节点（高位补 0），保持原有索引映射不变
• 收缩：根节点仅第 0 槽非空时，剥离单支层，释放节点

应用场景一：文件页缓存管理

演进：2.4 版本全局哈希表 + 单自旋锁 → 2.6 版本每个 address_space 独立基数树，提升并发。

struct address_space {
    struct inode *host;
    struct radix_tree_root page_tree; // 页缓存树根
};

外围函数 add_to_page_cache() / find_get_page() 分别持有 tree_lock 写/读锁，保证并发安全。

应用场景二：IPC 对象管理

演进：固定数组 grow_ary() 扩容拷贝 → 基于基数树的 idr 机制，动态分配 ID，避免大块内存拷贝。

struct idr {
    struct idr_layer *top;      // 根层
    struct idr_layer *id_free;  // 空闲节点链表
    int layers;                 // 树高
    spinlock_t lock;
};

外围函数 ipc_addid() / ipc_rmid() / ipc_findkey() 由 rw_mutex 保护（粗粒度锁，后续版本优化为 RCU/细粒度锁）。

三种结构对比总结

结论

基数树以「位分段索引 + 动态节点分配」实现 ID→指针映射，完美平衡查找性能、内存占用、动态伸缩与 ID 自动分配能力，是内核管理海量动态对象的首选结构。