【原】打破常规，Linux内核新的数据结构上场maple tree

深度Linux 2023-07-10 发布于湖南

展开全文

Linux kernal鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。

在外界看来，Linux内核的内部似乎变化很少，尤其是像内存管理子系统（memory-management subsystem）这样的子系统。然而，开发人员时常需要更换内部接口来解决某些长期存在的问题。比如，其中一个问题就是用来保护内存管理里的重要结构的锁的竞争问题，这些重要结构是指页表（page table）和虚拟内存区域（VMA, virtual memory area）等。Liam Howlett 和Matthew Wilcox 一直在开发一种新的数据结构，称为 "maple tree"，希望能取代目前用于 VMA 管理的数据结构。这个改动可能对内核内部结构造成巨大变化，作者已经公布了一个改动很大的 patch set 来召唤 review。

Linux 是一个虚拟内存(virtual-memory)系统。每个进程的地址空间中包含多个虚拟内存区域（VMA），都是由 vm_area_struct 结构表示。每个 vma 都代表一块连续的地址空间，并且这部分区域都是属于相同的内存类型，也就是可以是 anonymous memory（匿名内存，内容并不与某个文件对应）、memory-mapped file（内存映射文件），甚至是 device memory（设备内存）。从进程的角度来看，一个 VMA 区域都是连续的，而实际上底层的物理内存区域可能并不连续。此外，整个地址空间在各个 VMA 之间是有空洞的，当内核需要映射产生一个新的区域时（例如在加载一个库文件或者响应 mmap()调用时），内核就会从这些空洞分配出虚拟空间从而利用起来（当然还是会预留一些未映射的 "guard" page，有利于减少缓冲区溢出的危害）。

我们的系统中几乎所有工作都涉及到内存，所以对这些表示 VMA 的结构的操作必须要快。这些操作包括 lookup（查找，也就是找出哪个 VMA 是对应某个虚拟地址的、确认内存是否被 map 过，或者寻找一个空闲区域用于分配新的 VMA），以及修改（例如，增大堆栈空间）。

VMA 目前是通过一个红黑树（rbtree，red-black tree）的变种来管理的，针对红黑树来说增加了一个额外的双向链表，用来让内核遍历某个进程地址空间中的所有 VMA。内核开发者对这种数据结构的不满已经有一段时间了，原因有很多：rbtree 不能很好地支持范围（ranges），难以用 lockless（不需要获取锁）的方式来进行操作（rbtree 需要进行 balance 操作，这会同时影响多个 item），而且 rbtree 遍历的效率很低，这也是为什么需要一个额外的双向链表。

对 VMA 的操作会使用一个 lock 来保护（具体来说是一个 reader/writer semaphore），这个 lock 位于 struct mm_struct 中，此前名为 mmap_sem，2020 年 6 月的 5.8 版本将其改名为 mmap_lock。改名是为了能将对这个 lock 的操作都用 API 包装起来，希望将来替换的时候方便。

用户经常会碰到争抢这个 lock 的情况，尤其是那些在大型系统中使用多线程应用的用户。内核开发者已经多次讨论过这个问题，在 2019 年的 Linux Storage, Filesystem, and Memory-Management Summit (LFSMM) 峰会上至少有三次讨论过这个问题。问题的核心是，许多操作都需要获取 lock，这包括几乎全部的涉及 page table 和 VMA 的操作。还有其他一些相关的结构事实上也被 mmap_lock 地保护起来（麻烦的是相关文档也是缺失的）。开发者们在做的事情除了将不相关的结构从 mmap_lock 保护下拆分出来之外，还在考虑使用一个结构能允许 VMA 的访问变成 lockless 模式，或者使用某种类型的 range lock。当时有人提出了 maple tree 结构作为解决方案之一，但当时 maple tree 还处于早期开发状态，代码还没有完成。

Linux内核实现了常用的通用数据结构：

链表
队列
映射
二叉树

内核开发者应尽可能使用这些数据结构，不要造轮子重复开发。

一、链表

Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。

（1）单向链表

单向链表的指针区只包含一个指向下一个节点的指针，因此会形成一个单一方向的链表，如下代码所示。

struct list {
    int data;   /*有效数据*/
    struct list *next; /*指向下一个元素的指针*/
    struct list *prev; /*指向上一个元素的指针*/
};

（2）双向链表

如图所示，双向链表和单向链表的区别是指针区包含了两个指针，一个指向前继节点，另一个指向后继节点，如下代码所示。

struct list {
    int data;   /*有效数据*/
    struct list *next; /*指向下一个元素的指针*/
    struct list *prev; /*指向上一个元素的指针*/
};

（3）Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性，如数据区必须是固定数据，而实际需求是多种多样的。这种方法无法构建一套通用的链表，因为每个不同的数据区需要一套链表。为此，Linux内核把所有链表操作方法的共同部分提取出来，把不同的部分留给代码编程者自己去处理。Linux内核实现了一套纯链表的封装，链表节点数据结构只有指针区而没有数据区，另外还封装了各种操作函数，如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

Linux内核链表使用struct list_head数据结构来描述：

<include/linux/types.h>
 
struct list_head {
    struct list_head *next, *prev;
};

struct list_head数据结构不包含链表节点的数据区，通常是嵌入其他数据结构，如struct page数据结构中嵌入了一个lru链表节点，通常是把page数据结构挂入LRU链表。

<include/linux/mm_types.h>
 
struct page {
    ...
    struct list_head lru;
    ...
}

链表头的初始化有两种方法，一种是静态初始化，另一种动态初始化。把next和prev指针都初始化并指向自己，这样便初始化了一个带头节点的空链表。

<include/linux/list.h>
 
/*静态初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
#define LIST_HEAD(name) 
    struct list_head name = LIST_HEAD_INIT(name)
 
/*动态初始化*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

添加节点到一个链表中，内核提供了几个接口函数，如list_add()是把一个节点添加到表头，list_add_tail()是插入表尾。

<include/linux/list.h>
 
void list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

遍历节点的接口函数。

#define list_for_each(pos, head) 
for (pos = (head)->next; pos != (head); pos = pos->next)

这个宏只是遍历一个一个节点的当前位置，那么如何获取节点本身的数据结构呢？这里还需要使用list_entry()宏。

#define list_entry(ptr, type, member) 
    container_of(ptr, type, member)
container_of()宏的定义在kernel.h头文件中。
#define container_of(ptr, type, member) ({            
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    
    (type *)( (char *)__mptr - offsetof(type,member) );})
 
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其中offsetof()宏是通过把0地址转换为type类型的指针，然后去获取该结构体中member成员的指针，也就是获取了member在type结构体中的偏移量。最后用指针ptr减去offset，就得到type结构体的真实地址了。

下面是遍历链表的一个例子：

<drivers/block/osdblk.c>
 
static ssize_t class_osdblk_list(struct class *c,
                struct class_attribute *attr,
                char *data)
{
    int n = 0;
    struct list_head *tmp;
 
    list_for_each(tmp, &osdblkdev_list) {
        struct osdblk_device *osdev;
 
        osdev = list_entry(tmp, struct osdblk_device, node);
 
        n += sprintf(data+n, "%d %d %llu %llu %sn",
            osdev->id,
            osdev->major,
            osdev->obj.partition,
            osdev->obj.id,
            osdev->osd_path);
    }
    return n;
}

【文章福利】小编推荐自己的Linux内核技术交流群:【865977150】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100名进群领取，额外赠送一份价值699的内核资料包（含视频教程、电子书、实战项目及代码)

二、队列

Linux内核通用队列实现称为kfifo。

kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。

struct kfifo {
     unsigned char *buffer;    /* the buffer holding the data */
     unsigned int size;    /* the size of the allocated buffer */
     unsigned int in;    /* data is added at offset (in % size) */
     unsigned int out;    /* data is extracted from off. (out % size) */
     spinlock_t *lock;    /* protects concurrent modifications */
 };

它的结构如图：

这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。

2.1kfifo内存分配和初始化

首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0，我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？

 bool is_power_of_2(unsigned long n)
 {
     return (n != 0 && ((n & (n - 1)) == 0));
 }

再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下： kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。

 struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
 {
     unsigned char *buffer;
     struct kfifo *ret;
  
     /*
      * round up to the next power of 2, since our 'let the indices
      * wrap' technique works only in this case.
      */
     if (!is_power_of_2(size)) {
         BUG_ON(size > 0x80000000);         
`        size = roundup_pow_of_two(size);
     }
  
     buffer = kmalloc(size, gfp_mask);
     if (!buffer)
         return ERR_PTR(-ENOMEM);
  
     ret = kfifo_init(buffer, size, gfp_mask, lock);
       if (IS_ERR(ret))
         kfree(buffer);
  
     return ret;
 }

2.2kfifo并发无锁奥秘---内存屏障

为什么kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的呢？天底下没有免费的午餐的道理人人都懂，下面我们就来看看kfifo实现并发无锁的奥秘。

我们知道编译器编译源代码时，会将源代码进行优化，将源代码的指令进行重排序，以适合于CPU的并行执行。然而，内核同步必须避免指令重新排序，优化屏障（Optimization barrier）避免编译器的重排序优化操作，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。

举个例子，如果多核CPU执行以下程序：

a = 1;
 b = a + 1;
 assert(b == 2);

假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：

1 CPU0执行a=1;
2 因为a在CPU1-cache中，所以CPU0发送一个read invalidate消息来占有数据
3 CPU0将a存入store buffer
4 CPU1接收到read invalidate消息，于是它传递cache-line，并从自己的cache中移出该cache-line
5 CPU0开始执行b=a+1;
6 CPU0接收到了CPU1传递来的cache-line，即“a=0”
7 CPU0从cache中读取a的值，即“0”
8 CPU0更新cache-line，将store buffer中的数据写入，即“a=1”
9 CPU0使用读取到的a的值“0”，执行加1操作，并将结果“1”写入b（b在CPU0-cache中，所以直接进行）
10 CPU0执行assert(b == 2); 失败

软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙，所有在设置读写屏障之前发起的内存访问，必须先于在设置屏障之后发起的内存访问之前完成，确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。

如果对上述代码加上内存屏障,就能保证在CPU0取a时，一定已经设置好了a = 1:

void foo(void)
 {
 a = 1;
  smp_wmb();
 b = a + 1;
 }

这里只是简单介绍了内存屏障的概念，如果想对内存屏障有进一步理解,请参考我的译文《为什么需要内存屏障》。

2.3kfifo的入队__kfifo_put和出队__kfifo_get操作

__kfifo_put是入队操作，它先将数据放入buffer中，然后移动in的位置，其源代码如下：

unsigned int __kfifo_put(struct kfifo *fifo,
             const unsigned char *buffer, unsigned int len)
 {
     unsigned int l;
  
     len = min(len, fifo->size - fifo->in + fifo->out);
 
    /*
      * Ensure that we sample the fifo->out index -before- we
     * start putting bytes into the kfifo.
      */
  
     smp_mb();
  
     /* first put the data starting from fifo->in to buffer end */
     l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
     memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
 
     /* then put the rest (if any) at the beginning of the buffer */
     memcpy(fifo->buffer, buffer + l, len - l);
  
     /*
      * Ensure that we add the bytes to the kfifo -before-
      * we update the fifo->in index.
      */
  
     smp_wmb();
  
    fifo->in += len;
  
     return len;
 }

6行，环形缓冲区的剩余容量为fifo->size - fifo->in + fifo->out，让写入的长度取len和剩余容量中较小的，避免写越界；

13行，加内存屏障，保证在开始放入数据之前，fifo->out取到正确的值（另一个CPU可能正在改写out值）

16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)，所以fifo->size - (fifo->in & (fifo->size - 1)) 即位 fifo->in 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为需要拷贝l 字节到fifo->buffer + fifo->in的位置上。

17行，拷贝l 字节到fifo->buffer + fifo->in的位置上，如果l = len，则已拷贝完成，第20行len – l 为0，将不执行，如果l = fifo->size - (fifo->in & (fifo->size - 1)) ，则第20行还需要把剩下的 len – l 长度拷贝到buffer的头部。

27行，加写内存屏障，保证in 加之前，memcpy的字节已经全部写入buffer，如果不加内存屏障，可能数据还没写完，另一个CPU就来读数据，读到的缓冲区内的数据不完全，因为读数据是通过 in – out 来判断的。

29行，注意这里只是用了 fifo->in += len而未取模，这就是kfifo的设计精妙之处，这里用到了unsigned int的溢出性质，当in 持续增加到溢出时又会被置为0，这样就节省了每次in向前增加都要取模的性能，锱铢必较，精益求精，让人不得不佩服。

__kfifo_get是出队操作，它从buffer中取出数据，然后移动out的位置，其源代码如下：

 unsigned int __kfifo_get(struct kfifo *fifo,
              unsigned char *buffer, unsigned int len)
 {
     unsigned int l;
  
     len = min(len, fifo->in - fifo->out);
 
     /*
      * Ensure that we sample the fifo->in index -before- we
      * start removing bytes from the kfifo.
      */
  
     smp_rmb();
  
     /* first get the data from fifo->out until the end of the buffer */
     l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
    memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
  
     /* then get the rest (if any) from the beginning of the buffer */
     memcpy(buffer + l, fifo->buffer, len - l);
  
     /*
      * Ensure that we remove the bytes from the kfifo -before-
      * we update the fifo->out index.
      */
  
     smp_mb();
  
     fifo->out += len;
 
     return len;
 }

6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；

13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个CPU可能正在改写in值）

16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。

17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。

27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的操作，数据还没取完，令一个CPU可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的。

29行，注意这里只是用了 fifo->out += len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。

这里图解一下 in 先溢出的情况，size = 64，写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;

写入数据16个字节，则 in + 16 = 4294967307，溢出为 11，此时 in – out = –4294967268，溢出为28，数据长度仍然正确，由此可见，在这种特殊情况下，这种计算仍然正确，是不是让人叹为观止，妙不可言？

三、映射

Linux内核提供了简单、有效的映射数据结构，目标是：映射一个唯一的标识数（UID）到一个指针。idr数据结构用于映射用户空间的UID。

初始化idr：

void  idr_init(struct idr *idp);

分配新的UID，分为两步：

1、告诉idr需要分配新的UID，允许其在必要时调整后备树的大小

int idr_pre_get(struct idr *idp, gfp_t gfp_mask);

2、获取新的UID，并且将其加到idr:

int idr_get_new(struct idr *idp, void *ptr, int *id);
int idr_get_new_above(struct idr *idp, void *ptr, int startint_id, int *id); //分配的UID必须大于或等于startint_id

查找UID:

void *idr_find(strcut idr *idp, int, id);

删除UID：

void idr_remove(struct idr *idp, int id);

撤销idr：

void idr_destroy(struct idr *idp); //只释放idr中未使用的内存，不释放当前分配给UID使用的任何内存
void idr_remove_all(struct idr *idp); //删除所有UID

四、hlist

hlist_head 和 hlist_node 是位于linux内核中的数据结构，其设计初衷主要是为了减少Hash表的内存消耗。

struct hlist_head {
  struct hlist_node *first;
};

struct hlist_node {
  struct hlist_node *next, **pprev;
};

其内存结构如下：

hlist_head 结构体仅仅有一个first指针，hlist_node 结构体有两个指针，next 和 ppre。其中next指针指向下一个hlist_node,如果该节点为最后一个一个节点，那么next指向NULL。

这样设计的原因在于：通常我们在使用Hash表是为实现快速查找，那么Hash表通常会维护一张相对较大的数组，否则的会带来较大的冲突，而一张较大的数组必然会带来较大的内存消耗。我们知道通常一个Hash表中每一个dentry(每一个具体数元素)会使用两个指针，有其中一个指向尾节点，而我们知道在Hash表中的list通常是非常短（如果过长，说明冲突过多），那么显然这个指向尾节点的指向我们就不那么的必要，Hash表中的每一个denry只用保存一个指针。这样的设计显然会造成链表中节点数据结构不一致，如果hlist_node采用的next和pre指针，那么对于第一个节点和其他节点操作必然会使不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址，由于hlist_head和hlist_node指向的下一个节点的指针类型相同，这样就解决了通用性。

常用接口

（1）hlist_head 和 hlist_node初始化

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h) 
{
  h->next = NULL;
  h->pprev = NULL;
}

（2）添加节点

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 
{
  struct hlist_node *first = h->first;
  n->next = first;
  if (first)
    first->pprev = &n->next;
  h->first = n;
  n->pprev = &h->first;
}

（3）删除节点

static inline void __hlist_del(struct hlist_node *n)
{
  struct hlist_node *next = n->next;
  struct hlist_node **pprev = n->pprev;
  *pprev = next;
  if (next)
    next->pprev = pprev;
}

static inline void hlist_del(struct hlist_node *n)
{
  __hlist_del(n);
  n->next = LIST_POISON1;
  n->pprev = LIST_POISON2;
}

（4）遍历节点

#define hlist_for_each_entry(pos, head, member)       \
  for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
       pos;             \
       pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

五、二叉树

叉树是一种重要的数据结构，与数组、向量、链表都是一种顺序容器，它们提供了按位置访问数据的手段。但是有一个缺点，它们都是按照位置来确定数据，想要通过值来获取数据，只能通过遍历的方式。而二叉树在很大程度上解决了这个缺点，二叉树是按值来保存元素，也按值来访问元素。

二叉树由一个个节点组成，一个节点最多只能有两个子节点，从根节点开始左右扩散，分左子节点和右子节点，向下一直分支。

许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树是递归定义的。

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

5.1二叉树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

访问结点本身(N)，
遍历该结点的左子树(L)，
遍历该结点的右子树(R)。

遍历方法普遍有以下几种：

先序遍历（NLR）、中序遍历（LNR），后序遍历（LRN）和层次遍历。

遍历节点顺序：

先序遍历（NLR）：根、左子树、右子树
中序遍历（LNR）：左子树、根、右子树
后序遍历（LRN）：左子树、右子树、根
层次遍历：按照从上到下、从左到右的次序进行遍历

5.2二叉树的代码的实现

<?php
class Node{
    public $value;
    public $left;
    public $right;
}
//先序遍历 根节点 ---> 左子树 ---> 右子树
function preorder($root){
    $stack=array();
    array_push($stack,$root);
    while(!empty($stack)){
        $center_node=array_pop($stack);
        echo $center_node->value.' ';//先输出根节点
        if($center_node->right!=null){
            array_push($stack,$center_node->right);//压入左子树
        }
        if($center_node->left!=null){
            array_push($stack,$center_node->left);
        }
    }
}
//中序遍历，左子树---> 根节点 ---> 右子树
function inorder($root){
    $stack = array();
    $center_node = $root;
    while (!empty($stack) || $center_node != null) {
             while ($center_node != null) {
                 array_push($stack, $center_node);
                 $center_node = $center_node->left;
             }

             $center_node = array_pop($stack);
             echo $center_node->value . " ";

             $center_node = $center_node->right;
         }
}
//后序遍历，左子树 ---> 右子树 ---> 根节点
function tailorder($root){
    $stack=array();
    $outstack=array();
    array_push($stack,$root);
    while(!empty($stack)){
        $center_node=array_pop($stack);
        array_push($outstack,$center_node);//最先压入根节点，最后输出
        if($center_node->left!=null){
            array_push($stack,$center_node->left);
        }
        if($center_node->right!=null){
            array_push($stack,$center_node->right);
        }
    }

    while(!empty($outstack)){
        $center_node=array_pop($outstack);
        echo $center_node->value.' ';
    }

}
$a=new Node();
$b=new Node();
$c=new Node();
$d=new Node();
$e=new Node();
$f=new Node();
$a->value='A';
$b->value='B';
$c->value='C';
$d->value='D';
$e->value='E';
$f->value='F';
$a->left=$b;
$a->right=$c;
$b->left=$d;
$c->left=$e;
$c->right=$f;
preorder($a);//A B D C E F
echo '<hr/>';
inorder($a);//D B A E C F
echo '<hr/>';
tailorder($a);//D B E F C A

5.3二叉树的作用

二叉树常被用于实现二叉查找树和二叉堆。在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

根据不同的用途可分为：

1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

六、Introducing maple trees

maple tree（取这个名字可能是借用了枫叶的形状，意指能走向多个方向）与 rbtrees 有根本性的差异。它们属于 B-tree 类型(https://en.wikipedia.org/wiki/B-tree)，也就是说它们的每个节点可以包含两个以上的元素，leaf node（叶子节点）中最多包含 16 个元素，而 internal node（内部节点）中最多包含 10 个元素。使用 B-trees 也会导致很少需要创建新的 node，因为 node 可能包含一些空余空间，可以随着时间的推移而填充利用起来，这就不需要额外进行分配了。每个 node 最多需要 256 字节，这是常用的 cache line size 的整数倍。node 中增加的元素数量以及 cache-aligned size 就意味着在遍历树时会减少 cache-miss。

maple tree 对搜索过程也有改进，同样是来自于 B-tree 结构特点。在 B-tree 中，每个 node 都有一些 key 键值，名为 "pivot"，它会将 node 分隔成 subtree（子树）。在某个 key 之前的 subtree 只会包含小于等于 key 的数据，而这个 key 之后的子树只包含大于 key 的值（并且小于下一个 key 值）。

当然，maple tree 的设计中也是按照 lockless 方式的要求来的，使用 read-copy-update (RCU) 方式。maple tree 是一个通用结构，可以用在内核的不同子系统中。第一个用到 maple tree 的地方就是用来替换 VMA 管理中用到的 rbtree 和双向链表。作者之一 Liam Howlett 在一篇博客中解释了设计由来(https://blogs.oracle.com/linux/the-maple-tree)。

Maple tree 提供了两组 API：一个是简单 API ，一个是高级 API。简单 API 使用 mtree_前缀来标记相关功能，主结构 struct maple_tree 定义如下：

struct maple_tree {
  spinlock_t    ma_lock;
  unsigned int  ma_flags;
  void __rcu    *ma_root;
};

需要静态初始化（static initialize）的话，可以使用 DEFINE_MTREE(name) 和 MTREE_INIT(name，flags)，后者会的 flags 目前只定义了两个 bit 选项，其中 MAPLE_ALLOC_RANGE 表示该树将被用于分配 range，并且需要把多个分配区域之间的空间（gap）管理起来；MAPLE_USE_RCU 会激活 RCU mode，用在多个 reader 的场景下。mtree_init() API 也使用相同的 flags，不过是用在动态初始化（dynamic initialization）场景：

void mtree_init(struct maple_tree *mt, unsigned int ma_flags);

开发者可以用这个函数来 free 整个 tree：

void mtree_destroy(struct maple_tree *mt);

可以用三个函数来给树增加条目：mtree_insert()、mtree_insert_range()和 mtree_store_range()。前两个函数只有在条目不存在的情况下才会添加，而第三个函数可以对现有的条目进行覆盖。它们的定义如下：

int mtree_insert(struct maple_tree *mt, unsigned long index,
                 void *entry, gfp_t gfp);
int mtree_insert_range(struct maple_tree *mt, unsigned long first,
                       unsigned long last, void *entry, gfp_t gfp);
int mtree_store_range(struct maple_tree *mt, unsigned long first,
                      unsigned long last, void *entry, gfp_t gfp);

mtree_insert()的参数 mt 是指向 tree 的指针，index 就是 entry index，entry 是指向一个条目的的指针，有必要的话可以利用 gfp 来指定新增 tree node 的内存分配参数（memory allocation flag）。mtree_insert_range() 会利用给出的 entry 数据来插入从 first 到 last 的一个 range 范围。这些函数成功时返回 0，否则返回负值，如果返回-EEXIST 就表示 key 已经存在。mtree_store_range()与 mtree_insert_range()接受的参数相同，不同的是，它会替换相应 key 的任何现有条目。

有两个函数可以用来从 tree 中获取一个条目或删除一个条目：

void *mtree_load(struct maple_tree *mt, unsigned long index);
void *mtree_erase(struct maple_tree *mt, unsigned long index);

要读取一个条目的话，可以使用 mtree_load()，它的参数是一个指向 tree 的指针 mt ，以及所要读取的数据的键值 index。该函数会返回一个指向该条目的指针，如果在 tree 中没有找到键值，则返回 NULL。mtree_erase() 也是同样的语法，用于从 tree 中删除一个 entry。它会从 tree 中删除给定的 key，并返回相关的 entry，如果没有找到，则返回 NULL。

简单的 API 不止上面这些，还有比如 mtree_alloc_range() 可以用来从 key space 中分配一个 range。而高级 API (用 mas_ 前缀标记出来了) 则额外增加了遍历整个 tree 的迭代函数，以及使用 state variable 来访问后一个或者前一个元素。通过这种细粒度的操作，开发者就可以根据需要来恢复中断了的搜索。还有供开发人员找到空闲区域或者对 tree 进行复制操作的 API。

6.1Replacing the VMA rbtree (and more)

patch set 中不仅仅是引入了 maple tree。着重需要指出的是，这组 patch set 中有很大一部分是增加修改测试代码，考虑到这个改动会带来的巨大影响，以及新的数据结构在未来的重要性，这些测试代码是非常值得鼓励的。

这组 patch set 中有 70 个 patch 将 VMA 的所有操作中的 rbtree 操作换成了 maple tree，其中一个 patch 彻底在 VMA 中禁用了 rbtree。patch set 中另一部分代码移除了 VMA 里的双向链表。这个改动需要修改内核中所有直接地使用了 VMA 链表的代码：体系架构相关代码，core dump 代码，program 加载代码，一些设备驱动程序等，当然还有 memory-management 代码。patch set 里还删除了 VMA cache（用来跟踪每个进程最近访问过的 VMA，从而加快 lookup 速度），这是因为使用 maple tree 实现后速度更快，不再需要 VMA cache 了。

Patch set 的第一封邮件中还包括了一些性能数据，不过结果有些难以理解。一些 microbenchmark 的结果说明性能提升了，而其他一些（数量较少）则说明性能下降了。编译内核的时间与 5.10 内核本身相类似，只是多执行了几条指令（可能与添加的代码有关）。Howlett 希望大家给些建议如何对这些结果进行更深入的分析。

6.2Current status and next steps

目前 Maple tree 还处于 RFC 阶段，有一些缺点。比如说，目前的实现不支持 32 位系统或 non-MMU 的平台。不过，这些代码已经可以实际用起来了，内核开发者们可以研究一下，从而决定是否符合他们期望的方向（因为这组 patch set 并没有去掉 mmap_lock ）。这个 patch set 太大了，可能需要不少时间才能完成 review。

6.3Splay Tree

Splay Tree(伸展树)是Binary Search Tree(二叉搜索树)， Daniel Sleator和Robert E.Tarjan发明。但此操作可能会花费O(n)时间，但m次操作的最坏情况为O(m*log2(n))。

Splay Tree是在节点访问后，此节点将成为该树的根。如此节点位置深，则根到该节点路径上会有很多较深节点。旋转后，这些节点的深度会减少。

查找频率高的item经常在靠近树根的位置。每次查找后，对树进行重构，把item挪倒离树根近地方。Splay tree是自调整形式的二叉查找树，会沿着某个节点到树根间的路径，通过一系列旋转把此节点搬移到树根。

RtlSplay 主要例程，完成节点到Splay树根的操作。

RtlDelete 删除节点，重新平衡。

RtlIsRoot 节点是否是Splay树根。

RtlRealPredecessor 返回节点的pre节点。

RtlInsertAsLeftChild

下面贴以下Win2k源码中的RtlSplay代码：

PRTL_SPLAY_LINKS
RtlSplay( IN PRTL_SPLAY_LINKS Links )
{
    PRTL_SPLAY_LINKS L;
    PRTL_SPLAY_LINKS P;
    PRTL_SPLAY_LINKS G;
    //  while links is not the root we need to keep rotating it toward
    //  the root
    L = Links;
 
    while (!RtlIsRoot(L)) {

        P = RtlParent(L);
        G = RtlParent(P);
        if (RtlIsLeftChild(L)) {
            if (RtlIsRoot(P)) {
                /*
                  we have the following case

                          P           L
                         / \         / \
                        L   c  ==>  a   P
                       / \             / \
                      a   b           b   c
                */

                //  Connect P & b
                //

                P->LeftChild = L->RightChild;
                if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
                //  Connect L & P

                L->RightChild = P;
                P->Parent = L;

                //  Make L the root

                L->Parent = L;

            } else if (RtlIsLeftChild(P)) {

                /* we have the following case

                          |           |
                          G           L
                         / \         / \
                        P   d  ==>  a   P
                       / \             / \
                      L   c           b   G
                     / \                 / \
                    a   b               c   d
                */

                //  Connect P & b

                P->LeftChild = L->RightChild;
                if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
                //  Connect G & c

                G->LeftChild = P->RightChild;
                if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}

               //  Connect L & Great GrandParent

                if (RtlIsRoot(G)) {
                    L->Parent = L;
                } else {
                    L->Parent = G->Parent;
                    *(ParentsChildPointerAddress(G)) = L;
                }

                //  Connect L & P

                L->RightChild = P;
                P->Parent = L;

                //
                //  Connect P & G
                //

                P->RightChild = G;
                G->Parent = P;

            } else { // RtlIsRightChild(Parent)

                /*
                  we have the following case

                        |                |
                        G                L
                       / \             /   \
                      a   P           G     P
                         / \         / \   / \
                        L   d  ==>  a   b c   d
                       / \
                      b   c
                */

                //
                //  Connect G & b
                //

                G->RightChild = L->LeftChild;
                if (G->RightChild != NULL) {G->RightChild->Parent = G;}

                //
                //  Connect P & c
                //

                P->LeftChild = L->RightChild;
                if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}

                //
                //  Connect L & Great GrandParent
                //

                if (RtlIsRoot(G)) {
                    L->Parent = L;
                } else {
                    L->Parent = G->Parent;
                    *(ParentsChildPointerAddress(G)) = L;
                }

                //
                //  Connect L & G
                //

                L->LeftChild = G;
                G->Parent = L;

                //
                //  Connect L & P
                //

                L->RightChild = P;
                P->Parent = L;

            }

        } else { // RtlIsRightChild(L)

            if (RtlIsRoot(P)) {

                /*
                  we have the following case

                        P               L
                       / \             / \
                      a   L           P   c
                         / \         / \
                        b   c  ==>  a   b
                */

                //
                //  Connect P & b
                //

                P->RightChild = L->LeftChild;
                if (P->RightChild != NULL) {P->RightChild->Parent = P;}

                //
                //  Connect P & L
                //

                L->LeftChild = P;
                P->Parent = L;

                //
                //  Make L the root
                //

                L->Parent = L;

            } else if (RtlIsRightChild(P)) {

                /*
                  we have the following case

                      |                   |
                      G                   L
                     / \                 / \
                    a   P               P   d
                       / \             / \
                      b   L           G   c
                         / \         / \
                        c   d  ==>  a   b
                */

                //
                //  Connect G & b
                //

                G->RightChild = P->LeftChild;
                if (G->RightChild != NULL) {G->RightChild->Parent = G;}

                //
                //  Connect P & c
                //

                P->RightChild = L->LeftChild;
                if (P->RightChild != NULL) {P->RightChild->Parent = P;}

                //
                //  Connect L & Great GrandParent
                //

                if (RtlIsRoot(G)) {
                    L->Parent = L;
                } else {
                    L->Parent = G->Parent;
                    *(ParentsChildPointerAddress(G)) = L;
                }

                //
                //  Connect L & P
                //

                L->LeftChild = P;
                P->Parent = L;

                //
                //  Connect P & G
                //

                P->LeftChild = G;
                G->Parent = P;

            } else { // RtlIsLeftChild(P)

                /*
                  we have the following case

                          |              |
                          G              L
                         / \           /   \
                        P   d         P     G
                       / \           / \   / \
                      a   L    ==>  a   b c   d
                         / \
                        b   c
                */

                //
                //  Connect P & b
                //

                P->RightChild = L->LeftChild;
                if (P->RightChild != NULL) {P->RightChild->Parent = P;}

                //
                //  Connect G & c
                //

                G->LeftChild = L->RightChild;
                if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}

                //
                //  Connect L & Great GrandParent
                //

                if (RtlIsRoot(G)) {
                    L->Parent = L;
                } else {
                    L->Parent = G->Parent;
                    *(ParentsChildPointerAddress(G)) = L;
                }

                //
                //  Connect L & P
                //

                L->LeftChild = P;
                P->Parent = L;

                //
                //  Connect L & G
                //

                L->RightChild = G;
                G->Parent = L;

            }
        }
    }

    return L;
}