内核数据结构(1) Maple Tree

Intro

从外部来看，Linux 内核的内部结构似乎比较稳定，尤其是在内存管理子系统等子系统中。然而，开发人员有时需要替换内部接口来解决一些长期存在的问题。其中一个问题就是用于保护关键内存管理结构（包括页表和虚拟内存区域 (VMA)）的锁的争用。Liam Howlett 和 Matthew Wilcox 一直在开发一种名为“枫树”的新数据结构，以取代目前用于 VMA 的数据结构。 —-LWN

虽然Maple Tree脱胎于B树，但是细节上还是有很大的差异的。

引入新的数据结构总是有目的的，在这个commit中，Liam叙述了这个目标：

It is significantly short than the rbtree so it has fewer cache misses.

The long term goal of the maple tree is to reduce mmap_sem contention by
removing users that cause contention one by one.  This may lead to the lock
being completely removed at some point.

• 减少访问时的cache miss

• 降低mmap_lock的竞争

Impl

To be Continued