Linux 如何用一棵树管住百万页缓存：内核的 Page Cache 面纱

1. 从一个数字说起

一台 8GB 内存的 Linux 机器，通常有 3~5GB 被 Page Cache 占据——换算成 4KB 页面就是 75万~130万页。内核必须随时回答一个问题：“文件 X 的第 N 页在不在内存里？” 回答这个问题的速度直接决定了一次 read() 是 100 纳秒还是 100 微秒——差 1000 倍。

答案藏在一棵树里。

2. 全局视角：三个核心数据结构

先看从文件到缓存页的完整链路：

  
    
    
    
  
  c
struct inode {                    // 代表磁盘上的一个文件
    struct address_space *i_mapping;  // 指向该文件的缓存管理器
    ...
};
struct address_space {            // 文件的"缓存管家"
    struct inode    *host;            // 反指所属文件
    struct xarray   i_pages;          // 核心！页面索引树
    unsigned long   nrpages;          // 当前缓存页总数
    const struct address_space_operations *a_ops; // 文件系统回调
};
struct folio {                    // 一个物理 4KB 页的描述符
    struct address_space *mapping;    // 我属于哪个文件
    pgoff_t              index;       // 我是文件的第几页
    unsigned long        flags;       // 状态标志 (dirty/uptodate等)
};

关系一句话概括：inode → address_space → XArray（树）→ folio。多个进程打开同一文件，共享同一个 address_space 和同一份缓存——这就是"第二次打开秒开"的原因。

3. XArray 基数树：一棵什么样的树

address_space.i_pages 是一个 XArray——一棵分层的基数树。每个内部节点（xa_node）有 64 个 slot（由 XA_CHUNK_SHIFT=6 决定），每层消耗 key 的 6 个 bit。

图示说明：查找 index=131 时，将 131 拆为 64 进制 [0][2][3]，逐层走 slots[0] → slots[2] → slots[3]，直达 folio。3 次数组取值，零比较零遍历。

3.1 为什么可以分层查找？

核心就一行代码（lib/xarray.c）：

  
    
    
    
  
  c
offset = (index >> node->shift) & 63;   // 取 index 某 6 bit 作为数组下标
entry  = node->slots[offset];           // 直接跳到子节点

原理：每个节点 64 = 2^6 个 slot，每层恰好"消耗" index 的 6 个 bit。等价于把 index 看作 64 进制数，每一位就是一层的 slot 下标：

  
    
    
    
  
  bash
131 (十进制) = 0×64² + 2×64¹ + 3×64⁰

64 进制: [0] [2] [3]
        ↓   ↓   ↓
        层1  层2  层3 的 slot 下标

和十进制查表完全类似——如果你有一个 1000 格的柜子，找第 457 格，你可以拆成"第 4 排、第 5 列、第 7 格"逐层定位，而不需要从第 1 格数到第 457 格。XArray 就是把这个思路换成了 64 进制。

对比红黑树/哈希表：红黑树每层要比大小决定走左/走右；哈希表要处理冲突链。XArray 用位运算直接算出路径——3 次右移 + 3 次取数组元素，CPU 几乎不用"思考"。

3.2 树的容量

key（pgoff_t）是 unsigned long，64-bit 系统为 64 位。每层消耗 6 bit，最大深度 = ⌈64 / 6⌉ = 11 层。

树按需生长——空 slot 不分配 xa_node，稀疏文件几乎零开销。

4. 如何判断一个页是否已缓存

就看 xas_load() 的返回值：非 NULL = 已缓存，NULL = 未缓存。

  
    
    
    
  
  c
// mm/filemap.c
void *filemap_get_entry(struct address_space *mapping, pgoff_t index)
{
    XA_STATE(xas, &mapping->i_pages, index);
    struct folio *folio;

    rcu_read_lock();              // RCU 读锁：零竞争
    folio = xas_load(&xas);      // 沿树逐层走到叶子
    if (folio && !xa_is_value(folio))
        folio_try_get(folio);    // 防止并发回收
    rcu_read_unlock();
    return folio;                // NULL = 未缓存，非 NULL = 已缓存
}

没有标志位、没有布尔变量——树的 slot 里有 folio 指针就是缓存了，是 NULL 就是没缓存。整个判断只需沿树走 2~3 层，不遍历任何链表，不比较任何 key。

性能数字：Page Cache 命中约 100 纳秒，SSD 随机读需 50,000~100,000 纳秒——命中与未命中差 500~1000 倍。

5. 插入：缓存一个新页

当 read() 未命中时，内核从磁盘读取数据后把新 folio 挂进树里：

  
    
    
    
  
  c
// mm/filemap.c
int __filemap_add_folio(struct address_space *mapping,
                        struct folio *folio, pgoff_t index, ...)
{
    XA_STATE(xas, &mapping->i_pages, index);

    folio->mapping = mapping;    // 反向指针：folio 属于哪个文件
    folio->index = index;        // 反向记录：folio 是第几页

    xas_lock_irq(&xas);         // 写操作需要加锁
    xas_store(&xas, folio);     // 沿路径插入（必要时分配新 xa_node）
    mapping->nrpages++;
    xas_unlock_irq(&xas);
}

如果路径上缺少中间 xa_node，xas_store 会自动分配——树的"按需生长"就发生在这里。

6. 双向映射：正查 + 反查

  
    
    
    
  
  c
struct folio {
    struct address_space *mapping;    // → 所属文件的 address_space
    pgoff_t              index;       // → 文件中第几页
};

• 正向：read() 时用——mapping->i_pages[index] → folio*
• 反向：回收时用——folio->mapping → 哪个文件；folio->index → 哪个位置

每个缓存页只多花 16 字节（一个指针 + 一个 ulong）就实现了双向寻址。

7. 标记系统：一棵树如何追踪脏页

xa_node 内置 tag 位图：

  
    
    
    
  
  c
struct xa_node {
    void __rcu *slots[64];           // 64 个子指针
    unsigned long tags[3][1];        // 3 组 tag，每组 64 bit 位图
};

标记为 DIRTY 时，从叶子到根的每一层都设置对应 bit——遍历脏页时可以跳过所有没有脏子节点的子树。百万页中找 100 个脏页不需要遍历百万次。

8. 实战：一次 read() 的完整路径

  
    
    
    
  
  bash
read(fd, buf, 4096)   // 读文件偏移 8192 处的 4KB
│
├─ index = 8192 / 4096 = 2
│
├─ filemap_get_read_batch(mapping, index=2)
│   └─ xas_load() 在 XArray 中查 slot → folio*
│
├─ 命中 (folio != NULL && uptodate)
│   └─ copy_to_user(buf, page_address(folio), 4096)
│   └─ return 4096                     ← ~100ns 完成
│
└─ 未命中 (folio == NULL)
    ├─ page_cache_sync_ra()            ← 触发预读（多读几十页）
    │   ├─ alloc_pages()               ← 分配物理页
    │   ├─ __filemap_add_folio()       ← 插入 XArray
    │   └─ a_ops->readahead()          ← 文件系统从磁盘读取
    ├─ 等待 IO 完成 → set_folio_uptodate()
    └─ copy_to_user() → return 4096   ← ~50-100μs（含磁盘）

9. 内存回收：树不会无限膨胀

  
    
    
    
  
  bash
首次访问 folio
    → 放入 inactive list（观察区）
        → 再次被访问 → 晋升 active list（保护区）
        → 长期不访问 → 留在 inactive 尾部
            → 内存紧张时从尾部开始回收：
                clean page → 直接丢弃（磁盘有原始数据）
                dirty page → 先 writeback，再丢弃

回收 folio 时，xas_store(&xas, NULL) 把树的对应 slot 置空——之后查找该 index 就回到"未命中"路径。

10. 指针低位复用

folio 的 mapping 字段除了指向 address_space，还要标记页面类型。利用地址对齐：

  
    
    
    
  
  c
struct address_space { ... } __attribute__((aligned(8)));
// 8 字节对齐 → 地址低 3 bit 永远是 000

#define PAGE_MAPPING_ANON  0x1   // bit0=1 → 匿名页(堆/栈)

if (folio->mapping & 0x1)  → 匿名页
else                       → 文件页（Page Cache）

address_space *as = (void *)(folio->mapping & ~0x3);  // 还原指针

百万个 folio，每个省 8 字节 = 省 8MB 内存。

11. 文件系统在哪里？

整棵 XArray 树、LRU 回收、脏页追踪——全部是通用层（mm/filemap.c）做的。文件系统只需实现一组回调：

  
    
    
    
  
  c
struct address_space_operations {
    int  (*read_folio)(struct file *, struct folio *);
    void (*readahead)(struct readahead_control *);
    int  (*writepages)(struct address_space *, ...);
    int  (*write_begin)(struct file *, ...);
    int  (*write_end)(struct file *, ...);
};

换文件系统不影响缓存性能——无论 ext4 还是 f2fs，Page Cache 的树查找速度完全一致。

12. 一图总结

图示说明：一个 1GB 文件的完整缓存架构。struct inode → address_space → XArray（3层，~4000个xa_node）。四大能力：正向查找（100ns，RCU无锁）、Tag位图标记脏页（跳过无脏子树）、反向查找（folio→mapping+index，16B/page）、LRU回收（slot=NULL，按需释放）。

Linux 用一棵按需生长、逐层 64 分叉的基数树，在百万页面中实现了纳秒级定位、零遍历的脏页追踪、以及优雅的按需回收。这就是文件第二次读取比第一次快 1000 倍的根本原因——数据已经在树里了，不再需要访问磁盘。