3. 页缓存数据结构：address_space 结构体、基数树（Radix Tree）与 XArray 的演进
页缓存（Page Cache）是 Linux 内核文件 I/O 性能的核心。为了高效管理大量物理页面与文件偏移量之间的映射关系，内核维护了一套精妙的数据结构。本章将深入剖析 address_space 结构体、经典的基数树（Radix Tree）以及其现代替代者 XArray，揭示页缓存索引机制的演进历程。
3.1 address_space 结构体：页缓存的“中枢神经”
每个文件对象（inode）都关联一个 address_space 结构体，它是连接文件逻辑空间与物理页面的桥梁。该结构体不仅管理页缓存，还负责存储预读状态、回写控制以及内存回收的辅助信息。
核心角色：
address_space 是文件页缓存的管理器，它通过 i_pages 字段（XArray）来索引所有缓存的页面，并通过 a_ops 操作集定义页面读写、回写和释放的具体行为。
| 字段 | 类型 | 功能描述 |
|---|---|---|
i_pages |
struct xarray |
核心索引结构（原为基数树），存储文件偏移量到 struct page * 的映射 |
nrpages |
pgoff_t |
当前缓存的页面总数，用于内存回收的快速判断 |
a_ops |
const struct address_space_operations * |
操作函数指针集，包括 readpage、writepage、releasepage 等 |
host |
struct inode * |
指向所属的 inode 对象，用于文件系统上下文关联 |
i_mmap |
struct rb_root_cached |
红黑树，管理所有映射到该地址空间的 VMA（虚拟内存区域） |
private_list |
struct list_head |
用于文件系统私有数据的链表，如日志或元数据缓冲区 |
关键洞察： 当内核需要回收某个文件的页缓存时，它会遍历
i_pages 中的页面，检查每个页面的引用计数和脏状态。回收算法（如页面回收算法）会优先回收干净且未被锁定的页面。
3.2 基数树（Radix Tree）：经典的多路索引结构
在 Linux 内核 4.20 版本之前，address_space 使用基数树（Radix Tree）来管理页缓存。基数树是一种基于键值（文件偏移量）的多路搜索树，其高度固定，查找效率为 O(log64N)，非常适合管理稀疏的页面索引。
3.2.1 基数树的结构与查找原理
- 多路分支： 每个内部节点包含 64 个槽位（slot），对应 6 位索引（2^6 = 64）。
- 层级计算： 对于 64 位系统，文件偏移量被分割成多个 6 位组，树的深度取决于最大索引值。
- 标记系统： 每个节点维护两个标记位（PG_dirty 和 PG_writeback），用于快速查找脏页或回写中的页面，避免遍历所有叶子节点。
性能优势： 基数树的标记传播机制使得内核可以快速定位“所有脏页”或“所有正在回写的页”，这对于周期性回写（如
pdflush 或 writeback 线程）至关重要。
3.3 XArray：现代内核的索引革命
Linux 内核 4.20 版本引入了 XArray，作为基数树的直接替代品。XArray 由 Matthew Wilcox 设计，旨在解决基数树在并发、内存占用和 API 易用性方面的痛点。
3.3.1 为什么需要 XArray？
| 对比维度 | 基数树（Radix Tree） | XArray |
|---|---|---|
| 锁粒度 | 需要外部自旋锁保护整棵树 | 内置 RCU 和自旋锁，支持细粒度并发 |
| 内存开销 | 每个内部节点固定 64 个指针槽位，稀疏时浪费严重 | 支持压缩节点（Sibling Entry），节省内存 |
| API 复杂度 | 大量宏和内联函数，接口混乱 | 统一、简洁的 API，类似标准库容器 |
| 多条目操作 | 不支持原子地插入/删除多个条目 | 支持批量操作和范围查询 |
| 调试友好性 | 难以跟踪和调试 | 内置跟踪点和自检功能 |
3.3.2 XArray 的核心设计
- 节点压缩： 当某个内部节点只有一个有效条目时，XArray 会将其压缩为“兄弟条目”（Sibling Entry），直接存储在父节点中，减少树的高度。
- 内置 RCU： 读操作可以无锁进行，写操作通过 RCU 机制安全更新，极大提升了多核场景下的性能。
- 统一迭代器： 提供
xa_for_each、xa_for_each_range等宏，简化了页面遍历逻辑。
迁移影响： 从基数树到 XArray 的迁移对文件系统开发者几乎是透明的。内核提供了兼容层，旧的
radix_tree_* API 被映射到新的 xa_* 函数，但新代码应直接使用 XArray 接口。
3.4 从 Radix Tree 到 XArray 的演进总结
页缓存索引结构的演进反映了 Linux 内核在应对大规模内存和并发访问时的持续优化。基数树奠定了多路索引的基础，而 XArray 则在内存效率、并发安全和 API 易用性上实现了质的飞跃。
调优提示： 在分析内存压力时，可以通过
/proc/slabinfo 观察 radix_tree_node 或 xarray_node 的缓存占用。如果发现大量节点缓存，说明页缓存索引结构本身可能成为内存开销的来源，尤其是在文件数量巨大但每个文件页面稀疏的场景下。
| 演进阶段 | 内核版本 | 核心改进 | 对页缓存回收的影响 |
|---|---|---|---|
| 基数树（Radix Tree） | 2.6.x ~ 4.19 | 多路搜索、标记传播 | 标记系统加速脏页查找，但锁竞争严重 |
| XArray | 4.20+ | 节点压缩、RCU 并发、统一 API | 减少内存占用，提升多核回收效率 |
理解这些数据结构的演进，有助于我们在进行内存压力调优时，准确判断页缓存索引层是否成为瓶颈，并采取相应的优化策略（如调整文件系统布局、控制并发访问模式等）。