Linux Kernel

Linux 用 Maple Tree 管理进程的 VMA，将虚拟地址区间关联到映射对象。

页缓存用 XArray 把文件页索引映射到 folio，支持稀疏条目和多页 folio。

Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合，用增强红黑树搜索候选任务。

伙伴分配器把空闲物理页组织为不同 order 的连续块，并用空闲链表管理同阶块。

hrtimer 通过 timerqueue 的红黑树维护到期顺序，并缓存最早到期节点。

Linux IIO 的 kfifo 缓冲在采样进入内核与用户态读取之间暂存数据，按先进先出顺序交付采样记录。

Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。

Linux SLUB 将同类对象组织在 slab 中，并用 per-CPU freelist 满足常见分配，避免每次都访问集中管理的部分空闲 slab 列表。

Linux DRM 使用通用 list_sort 对显示模式链表排序；底层归并通过相等时优先取较早元素来保持稳定性。

Linux v6.5 的 CFS 将可运行实体按 vruntime 放入红黑树，用加权运行时间作为公平性的基准。

Linux 把 list_head 嵌入业务对象，通过成员偏移找回宿主，并在编译期检查指针类型。

Linux 通过 RCU 保护 PID 查找期间的对象存活，再用引用计数延长返回对象的生命；移除 PID 后先等待 RCU 宽限期，再释放索引持有的引用。

Linux 读取系统实时时钟时用序列计数校验多个字段，若期间发生写入就重读，避免把旧的秒值与新的时钟换算状态拼在一起。

KVM 预先匹配设备通知地址，命中后 signal eventfd，使通知无需让 vCPU 逐次退回 QEMU 分派。

Linux 普通定时器把较近超时放进细粒度槽，远期超时放进粗粒度槽，使用位图寻找待处理槽。v6.12 的这套时间轮不再逐层级联迁移。