linux xarray 原理

LinuxXArrayeXtensible Array是内核 4.20 引入的可扩展稀疏数组对外像 “巨大指针数组”内部是优化的多级 Radix 树主打高效稀疏索引、无锁读、自动缩扩、缓存友好;XArray 诞生背景替代 Radix-TreeLinux 早期使用基数树 radix_tree做稀疏索引映射PID、页缓存、fd但 radix-tree 存在明显缺陷API 复杂区分 slot、tag、遍历接口不支持区间映射连续 index 绑定同一个对象锁设计笨重RCU 使用门槛高内存开销大叶子节点冗余。XArray 从 Linux 4.20 正式引入是新一代内核稀疏动态数组目标兼容 radix-tree 全部场景API 极简统一原生支持区间存储、批量操作轻量化 RCU 无锁读更低内存占用、更好缓存局部性统一一套接口管理指针、整数、位标签。XArray 由 Matthew Wilcox 重写完全兼容 Radix Tree 场景并提供仿数组的极简 APIxa_store/xa_loadRCU 读 自旋锁写的高并发模型节点动态合并 / 拆分内存更省内置mark 标记支持快速筛选遍历核心原理XArray 多层分级稀疏哈希数组功能将非负整数 index0 ~ ULONG_MAX映射到一个指针void *entry。典型使用PID、page cache、文件描述符、块设备扇区映射、io_uring 缓冲区管理。层级拆分规则4 层每层 6bit索引 index 被拆分为 4 段 6bit最多覆盖0 ~ 2^(4*6)-1 0~16777215 超过该范围会启用超大索引扩展XA_ZERO_ENTRY 占位。层级计算逻辑Level 3根节点shift18取 index 第 18~23 位 → 根 slotLevel 2shift12取 index 第 12~17 位 → 二级 slotLevel 1shift6取 index 第 6~11 位 → 三级 slotLevel 0叶子shift0取 index 第 0~5 位 → 叶子 slot示例index 0xABCDEF根slot (index 18) 0x3F 二级slot (index 12) 0x3F 三级slot (index 6) 0x3F 叶子slot index 0x3F每层节点仅分配有数据的分支天然稀疏不存在连续空白数组占用内存。Slot 内 Entry 编码规则关键slots[]存储的不是单纯指针通过低 2 位区分 entry 类型entry 最低2bit掩码 XA_FLAGS_MASK 0x3 1. XA_ZERO_ENTRY (0b00)空槽无数据 2. XA_NODE_ENTRY (0b01)指向子 xa_node中间节点 3. XA_RETRY_ENTRY (0b10)RCU 并发修改时读重试标记 4. XA_VALUE_ENTRY (0b11)存储有效用户指针对象用户传入的有效指针必须2 字节对齐内核分配内存天然满足最低 2 位 0存入时自动或运算XA_VALUE_ENTRY读取时剥离标记还原原始指针。额外特殊 entry区间映射XA_RANGE_ENTRY用于xa_store_range。核心数据结构1. 顶层结构struct xarraystruct xarray { spinlock_t xa_lock; // 写操作自旋锁 gfp_t xa_flags; // 内存分配掩码 void __rcu *xa_head; // 树根指针或直接存值 };2. 树节点struct xa_node#define XA_CHUNK_SHIFT 6 // 每级6位 → 64槽 #define XA_CHUNK_SIZE (1 XA_CHUNK_SHIFT) // 64 struct xa_node { unsigned char shift; // 当前层级高位→低位 unsigned char offset; // 在父节点的槽位 unsigned char count; // 有效条目数 struct xa_node __rcu *parent; // 父节点 void __rcu *slots[XA_CHUNK_SIZE]; // 64个指针槽 };每个节点固定64 槽6 位索引64 位系统最多11 级6×1166覆盖 64 位索引索引高位在顶层低位在叶子逐级拆分基础 API静态定义DEFINE_XARRAY(my_xa);动态初始化struct xarray xa; xa_init(xa); // 带GFP标记 xa_init_flags(xa, GFP_KERNEL);存 / 取 / 删除// 存储index指针返回旧值 void *old xa_store(xa, index, ptr, GFP_KERNEL); // 读取 void *val xa_load(xa, index); // 删除置NULL void *del xa_erase(xa, index);范围条目一个索引区间映射同一个对象xa_store_range(xa, start, end, obj, GFP_KERNEL);读写核心流程原理读流程xa_load无锁 RCU读全程不加 xa_lock依靠 RCU 保证节点不会中途释放rcu_read_lock () 进入读临界区从xa_head根节点开始按 index 逐层拆分 6bit取对应 slot若 slot 是 XA_NODE_ENTRY向下递归子节点若中途遇到 XA_RETRY_ENTRY重启整个查询叶子节点 slot 为 XA_VALUE_ENTRY剥离标记返回对象指针遇到 XA_ZERO_ENTRY返回 NULLrcu_read_unlock()。优势大量并发读无锁性能远优于带锁 radix-tree。写流程xa_store /xa_erase加锁修改写操作必须持有xa_lock自旋锁保证独占修改spin_lock(xa-xa_lock);逐层遍历 index 路径路径不存在中间节点 NULL动态分配 xa_node插入树路径存在直达叶子 slot保存 slot 旧 entry写入新 entry用户对象 / XA_ZERO向上回溯父节点更新count有效槽计数若节点 count0无有效 slot回收节点RCU 延迟释放spin_unlock(xa-xa_lock);返回旧指针给调用者。节点释放规则不会立即 free通过 RCU 回调等待所有读临界区退出后回收避免读方野指针。区间映射 Range 核心创新radix-tree 不具备传统 radix-tree 只能单个 index 映射XArray 原生支持连续一段 index [start, end] 绑定同一个对象APIint xa_store_range(struct xarray *xa, unsigned long start, unsigned long end, void *entry, gfp_t gfp);实现原理当连续区间长度超过单个节点覆盖范围时节点不再存储普通 VALUE_ENTRY将节点标记为 RANGE 模式node-range指向struct xarray_rangerange 结构记录起始、终止 index、绑定对象查询落在区间内时直接返回绑定对象无需逐层遍历叶子大幅减少大量连续 index如大块内存、连续扇区场景的节点数量节省内存。Tag 标签机制兼容 radix-tree 页面标记内核页面缓存需要标记页面状态脏页、写回、锁定XArray 保留 tag 位图每个 xa_node 有tags[]位图数组每 bit 对应一个 slot 是否带该标记APIxa_set_mark / xa_clear_mark / xa_find_mark用途快速遍历所有 “脏页”无需遍历全部 index 底层用位运算批量扫描效率极高。RCU 并发安全模型XArray 是典型 RCU 数据结构分离读写路径读侧rcu_read_lock无锁遍历遇到修改中节点RETRY重试写侧xa_lock 串行所有修改修改旧节点指针时使用 rcu_assign_pointer回收删除空节点不立即释放调用 call_rcu等待所有正在读该节点的 RCU 临界区结束后再释放内存。无 ABA 问题保障RETRY_ENTRY 标记拦截并发更新时的脏读。与 Radix-Tree 关键对比特性Radix-TreeXArray层级动态可变固定 4 层每层 64 槽区间映射不支持原生 xa_store_rangeAPI多套接口radix_tree_insert/set_tag统一 store/load/eraseRCU 使用复杂手动处理重试内置 RETRY 自动重试读内存开销节点冗余高节点更少缓存友好锁粒度读写均易加锁读完全无锁仅写自旋锁超大索引扩展性差支持 ULONG_MAX 全范围时间复杂度单次 load/storeO (4)固定 4 层遍历与数据量无关稀疏存储仅分配使用到的分支空白 index 不占内存区间批量操作O (1) 标记整个范围远快于循环单 index 插入。典型内核应用场景PID 管理PID 是连续稀疏整数XArray 快速映射 pid → task_struct分配 / 回收 O (log₆₄N) 复杂度。Page Cache以文件偏移 index 映射 struct pagetag 标记脏页区间映射处理连续大文件块。文件描述符 fdtablefd 号作为 index映射 file*大量空闲 fd 不会占用节点内存。块设备扇区映射连续扇区使用 range 映射同一缓存页面大幅减少节点分配。io_uringsqe/cqe 索引、缓冲区 ID 映射高并发无锁读提升 IO 性能。