FreeBSD虚存系统splay树的代码分析

雨丝风片

已完成的内容

1、vm_map_entry结构体中的adj_free和max_free
2、vm_map_entry_splay()函数
3、vm_map_findspace()函数
......

1、vm_map_entry结构体中的adj_free和max_free

vm_map_entry结构体同时按两种数据结构进行组织，一种是双向链表（通过prev和next指针），一种是二叉查找树（通过left和right指针）。其中的二叉查找树就是由Daniel Dominic Sleator和Robert Endre Tarjan提出的splay树，他们的论文题目把这种树叫做自调整二叉查找树。

splay树的基本原理请参见原始论文【Self-Adjusting Binary Search Trees】和我写的一些笔记【FreeBSD虚存系统splay树的基本原理】

FreeBSD是从5.0开始将splay树引入VM系统的，在5.3的时候又加入了基于树状结构的空闲空间算法。本文就从这个空闲空间算法讲起。

vm_map_entry结构体的主要内容如下：

_____________________________________________________________________FreeBSD6.0
093 /*
094 * Address map entries consist of start and end addresses,
095 * a VM object (or sharing map) and offset into that object,
096 * and user-exported inheritance and protection information.
097 * Also included is control information for virtual copy operations.
098 */
099 struct vm_map_entry {
100 struct vm_map_entry *prev; /* previous entry */
101 struct vm_map_entry *next; /* next entry */
102 struct vm_map_entry *left; /* left child in binary search tree */
103 struct vm_map_entry *right; /* right child in binary search tree */
104 vm_offset_t start; /* start address */
105 vm_offset_t end; /* end address */
106 vm_offset_t avail_ssize; /* amt can grow if this is a stack */
107 vm_size_t adj_free; /* amount of adjacent free space */
108 vm_size_t max_free; /* max free space in subtree */
_______________________________________________________/usr/src/sys/vm/vm_map.h

空闲空间算法向vm_map_entry结构体中添加了两个字段，adj_free和max_free。adj_free是和这个map entry相邻且紧跟其后（位于较高地址）的空闲空间的大小。注意，adj_free字段取决于链表结构，而不是splay树。这个链表是按照地址的升序来排列的，因此adj_free可以通过下述方式来计算：

_____________________________________________________________________FreeBSD6.0
789 entry->adj_free = (entry->next == &map->header ? map->max_offset :
790 entry->next->start) - entry->end;
_______________________________________________________/usr/src/sys/vm/vm_map.c

也就是说，一个map entry的adj_free字段的值等于它在链表中的下一个map entry的起始地址减去它自己的终止地址。

下图画出了一个FreeBSD VM系统splay树的局部示意图，图中虚拟地址空间中的地址数值仅做算法示例用，不具备任何真实地址的属性。

图中给出了三个map entry，分别表示了虚拟地址空间中三个区间。entry和对应地址空间使用相同颜色标注，分别为蓝色、绿色和粉色。绿色entry和粉色entry分别作为蓝色entry在splay树中的左孩子和右孩子，它们自己则无后继，左右孩子指针皆为空，图中用红色箭头标出了splay树的链接关系。对于链表结构而言，排在最前面的是绿色entry，其后继为蓝色entry，绿色entry则作为蓝色节点的后继，图中用蓝色箭头标出了链表结构的链接关系。

我们可以看到，绿色entry所表示的虚拟地址空间的起始地址为100，终止地址为300。蓝色entry的起始地址为500，终止地址为600。粉色entry的起始地址为850，终止地址为1050。根据上面给出的计算方法，绿色entry的adj_free字段的值就应该是200，蓝色entry的adj_free就是250，粉色entry的adj_free就是300。

max_free字段则是基于splay树的，表示这个map entry的子树中的相邻空闲空间的最大值。其计算方法是取这个entry自己的adj_free和其左、右子树的max_free三者之中的最大值。这也就是vm_map_entry_set_max_free()函数做的事情：

_____________________________________________________________________FreeBSD6.0
574 /*
575 * vm_map_entry_set_max_free:
576 *
577 * Set the max_free field in a vm_map_entry.
578 */
579 static __inline void
580 vm_map_entry_set_max_free(vm_map_entry_t entry)
581 {
582
583 entry->max_free = entry->adj_free;
584 if (entry->left != NULL && entry->left->max_free > entry->max_free)
585 entry->max_free = entry->left->max_free;
586 if (entry->right != NULL && entry->right->max_free > entry->max_free)
587 entry->max_free = entry->right->max_free;
588 }
_______________________________________________________/usr/src/sys/vm/vm_map.c

根据上述算法，我们就可以分别计算出上图中三个map entry的max_free字段的值：绿色entry为200，粉色entry为300，而蓝色entry则为200、300、250三者之最大值，即300。

引入了这两个字段之后，我们就可以很方便地判断出一个子树中是否存在足够大的空闲空间。这使得我们只需在树中从上至下走一次即可找到满足first-fit原则的空闲区域。这个算法的具体实现在vm_map_findspace()函数中。但我们先来看看vm_map_entry_splay()函数。

vm_map_entry_splay()函数

vm_map_entry_splay()是splay树算法的核心所在。给定一个地址addr和splay树的根节点root，这个函数能够把包含或者是与这个地址相邻的map entry搬移成树根。

_____________________________________________________________________FreeBSD6.0
607 static vm_map_entry_t
608 vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
609 {
610 vm_map_entry_t llist, rlist;
611 vm_map_entry_t ltree, rtree;
612 vm_map_entry_t y;
613
614 /* Special case of empty tree. */
615 if (root == NULL)
616 return (root);
_______________________________________________________/usr/src/sys/vm/vm_map.c

这个函数的算法需要在树中从上到下和从下到上走两遍。下面是第一遍的代码段：

_____________________________________________________________________FreeBSD6.0
618 /*
619 * Pass One: Splay down the tree until we find addr or a NULL
620 * pointer where addr would go. llist and rlist are the two
621 * sides in reverse order (bottom-up), with llist linked by
622 * the right pointer and rlist linked by the left pointer in
623 * the vm_map_entry. Wait until Pass Two to set max_free on
624 * the two spines.
625 */
626 llist = NULL;
627 rlist = NULL;
628 for (;;) {
629 /* root is never NULL in here. */
630 if (addr < root->start) {
631 y = root->left;
632 if (y == NULL)
633 break;

634 if (addr < y->start && y->left != NULL) {
635 /* Rotate right and put y on rlist. */
636 root->left = y->right;
637 y->right = root;
638 vm_map_entry_set_max_free(root);
639 root = y->left;
640 y->left = rlist;
641 rlist = y;
642 } else {
643 /* Put root on rlist. */
644 root->left = rlist;
645 rlist = root;
646 root = y;
647 }
648 } else {
649 y = root->right;
650 if (addr < root->end || y == NULL)
651 break;
652 if (addr >= y->end && y->right != NULL) {
653 /* Rotate left and put y on llist. */
654 root->right = y->left;
655 y->left = root;
656 vm_map_entry_set_max_free(root);
657 root = y->right;
658 y->right = llist;
659 llist = y;
660 } else {
661 /* Put root on llist. */
662 root->right = llist;
663 llist = root;
664 root = y;
665 }
666 }
667 }
_______________________________________________________/usr/src/sys/vm/vm_map.c

我们还是以一种形象化的方法来描述这个“splay”过程。假设我们现在有一棵splay树，它的局部如图vm_map_entry_splay_001所示。同样，图中的所有数字都仅仅用于算法示例，不具有任何实际地址的属性。每个map entry的起始地址和终止地址用“100-200”的格式标注，其adj_free和max_free字段的值也都根据前面讲到的规则进行了计算和标注。

假设vm_map_entry_splay函数的入参addr为1000，也就是说，我们要拿1000这个值来对这颗树执行splay操作，当前的树根是A entry。我将用以下这种格式来描述整个过程，首先给出一些关键变量的当前值，然后按代码执行顺序描述相关流程，左边的数字是代码所在行数，右边是对应的实际操作。一个阶段的操作完成之后我将给出当前的树的形态图示。

第一次执行for循环体：

_______________________________________________________________________________
预置条件：llist = rlist = NULL; root = A;
-------------------------------------------------------------------------------
630 1000 < 2400
631 y = B
632 y != NULL
634 1000 < 1700 且 C != NULL
636 A->left = E
637 B->right = A
638 重新计算A entry的max_free字段的值
_______________________________________________________________________________

经过上述操作之后的树的形态如图vm_map_entry_splay_002所示。我们可以看到，A的子树已经发生了变化，而且我们已经在第634行确定了在B之后仍将继续向左走，因此余下的操作不会再对A的子树造成影响，于是就在这里对A的max_free字段进行重新计算。计算是通过调用vm_map_entry_set_max_free()函数来进行的，这个函数的算法我们已经在前面讲过了，就是取E和C的max_free以及A的adj_free三者之最大值。此处就是把A的max_free从原来的300更新成了200，表示在A的新子树中的最大相邻空闲空间为200，在图中用红色标出。除此之外，节点B的子树也发生了变化，但由于后面的操作还有可能会影响到B的子树结构，所以此处并不急于更新B的max_free字段。

继续：

_______________________________________________________________________________
预置条件：llist = rlist = NULL; y = B; root = A;
-------------------------------------------------------------------------------
639 root = D
640 B->left = NULL
641 rlist = B
_______________________________________________________________________________

经过上述操作之后的树的形态如图vm_map_entry_splay_003所示。我们可以看到，此时的splay树已被一分为二：一边是已经遍历过的以B为顶点的子树，这个子树以rlist指针指向；一边是尚未遍历过的以D为顶点的子树，这个子树以root指针指向。

for循环的第一次执行到次就结束了。下面是第二次：

_______________________________________________________________________________
预置条件：llist = NULL; rlist = B; root = D;
-------------------------------------------------------------------------------
630 1000 > 300
649 y = G
650 1000 > 400 且 G != NULL
652 1000 > 800 且 I != NULL
654 D->right = NULL
655 G->left = D
656 重新计算D的max_free字段的值
_______________________________________________________________________________

经过上述操作之后的树的形态如图vm_map_entry_splay_004所示。此时D的子树也发生了变化，且我们已经在第652行确定在G处将继续向右走，因此D的子树不会再有变化，于是就在这里对D的max_free进行更新，只不过更新前后的值都是300，在图中用红色标出。

继续：

_______________________________________________________________________________
预置条件：llist = NULL; rlist = B; root = D; y = G;
-------------------------------------------------------------------------------
657 root = I
658 G->right = NULL
659 llist = G
_______________________________________________________________________________

经过上述操作之后的树的形态如图vm_map_entry_splay_005所示。我们可以看到，新的root已经指向了I，而已经遍历过的部分则被分成了两个子树，分别由rlist和llist指针指向。我们还可以初步看出这两个子树的性质，rlist指向的子树中的地址都是大于我们的入参地址100的，而llist指向的子树中的地址都是小于1000的。

下面是for循环的第三次执行：

_______________________________________________________________________________
预置条件：llist = G; rlist = B; root = I;
-------------------------------------------------------------------------------
630 1000 < 1050
631 y = J
632 J != NULL
634 1000 > 900
635 I->left = B
636 rlist = I
637 root = J
_______________________________________________________________________________

经过上述操作之后的树的形态如图vm_map_entry_splay_006所示。我们可以看到，新的root已经指向了J节点，当然，对于我们的例子而言，这也是最后一个节点。遍历过的部分仍然被分成了由rlist和llist两个指针指向的子树。刚才遍历过的I及其右子树被“倒置”在了B及其子树的上面。连接I和B的指针被标成了红色，因为这条边等会还有用，别忘了，用这条边串起来的节点的max_free字段的值还都没有确定呢，等会就要通过这条边来更新这些节点的max_free字段。同样，在llist指向的子树中也会有这么一条边，只是对于我们的例子而言就无法画出来了。另外还有一点需要明确，rlist的子树中的“这条边”是由一系列的left指针连成的，而llist的子树中的“那条边”则是由一系列的right指针连成的。

下面是for循环的第四次执行：

_______________________________________________________________________________
预置条件：llist = G; rlist = I; root = J;
-------------------------------------------------------------------------------
630 1000 > 900
649 y = NULL
650 Y = NULL
651 终止for循环
_______________________________________________________________________________

由于我们只剩最后一个J entry了，于是for循环到此结束。实际上也就完成了对splay树的“第一遍”处理。

下面是“第二遍”的代码：

_____________________________________________________________________FreeBSD6.0
669 /*
670 * Pass Two: Walk back up the two spines, flip the pointers
671 * and set max_free. The subtrees of the root go at the
672 * bottom of llist and rlist.
673 */
674 ltree = root->left;
675 while (llist != NULL) {
676 y = llist->right;
677 llist->right = ltree;
678 vm_map_entry_set_max_free(llist);
679 ltree = llist;
680 llist = y;
681 }
682 rtree = root->right;
683 while (rlist != NULL) {
684 y = rlist->left;
685 rlist->left = rtree;
686 vm_map_entry_set_max_free(rlist);
687 rtree = rlist;
688 rlist = y;
689 }
_______________________________________________________/usr/src/sys/vm/vm_map.c

这部分代码比较简单，而且一些基本思想我们已经在前面介绍过了，所以这里就不再做详细的逐步分析，仅从大的概念上来谈谈。

splay树的基本思想是什么？就是假设我这次访问的节点在将来被继续访问的可能性极高，因此需要把这个节点移往树根，虽然这次的移动要花点时间，但如果前面的假设成立，这种算法就能获得极好的“摊平效率”，也就是说，从一段长时间的连续操作来看，它的平均操作时间是相当低的。此处，我们的splay操作到J entry那儿就结束了，这个entry要么就包含我们的入参地址，要么就是和我们的入参地址相邻，也就是说，按照splay树的算法，它即将成为新的树根。但一人得道，鸡犬不能升天，J entry可以成为树根，但它的子树却没有沾光的权利，它们仍将留在树中相对较低的位置。

我们前面已经提到过，llist指向的子树中用right指针串起来的那些entry和rlist指向的子树中用left指针串起来的那些entry的max_free字段都还没定呢，现在就要分别确定它们。这两个子树是互不相干的，因为一边是小于入参地址的，一边是大于入参地址的。但是有个问题，别忘了当前root也即J的子树。虽然在我们的例子里J是没有子树的，但在实际当中是完全可能有的。因此这次的计算也得把它们捎上。这两个子树显然也是一边小于入参地址，一边大于入参地址，所以它们将分别加入llist和rlist指向的子树。在两个while循环开始之前的ltree = root->left;和rtree = root->right;这两条语句就是为了让llist和rlist分别接管当前root的这两个子树。

另外还要注意的就是，llist和rlist指向的子树都是”倒置的“。比如在我们的例子中，I的子树放在了B的子树的上面，这种倒置的设计就是为了这第二遍的计算。因为第一遍的splay操作是从上到下，而第二遍对max_free的更新必须从下到上更新才行。要达到这个目的，我们就得知道来时的路径。这里的设计和“栈”很像，先入后出，既保存了路径，又省掉了一个父指针。

所以，在上面的两个while循环里，就沿着right指针遍历llist链表，沿着left指针遍历rlist链表，在对所经过的entry的max_free进行更新之后，就把顺序纠正过来，该在上面的还在上面，该在下面的还在下面。完成之后的树的形态如图vm_map_entry_splay_007所示。

llist和rlist指针被用来遍历链表了，最后肯定要变成空指针，所以拨乱反正之后的两个子树就分别用ltree和rtree指针来指向。我们可以看到，通过这次更新计算，G entry的max_free从200变成了300，而B entry的max_free则从300变成了200，在图中用红色标出。

现在两边躯体都已经弄好了，就差把“头”装上去了：

_____________________________________________________________________FreeBSD6.0
691 /*
692 * Final assembly: add ltree and rtree as subtrees of root.
693 */
694 root->left = ltree;
695 root->right = rtree;
696 vm_map_entry_set_max_free(root);
697
698 return (root);
_______________________________________________________/usr/src/sys/vm/vm_map.c

对于我们的例子来说，就是把ltree指向的子树作为J的左子树，把rtree指向的子树作为J的右子树。最后还别忘了更新J的max_free，从50改成300。最终的树的形态如图vm_map_entry_splay_008所示。

vm_map_entry_splay()函数到此结束。

vm_map_findspace()函数

vm_map_findspace()函数的功能就是对于给定的map映射，找到其虚拟地址空间中位于start地址之后的第一个满足length长度要求的空闲空间。

_____________________________________________________________________FreeBSD6.0
1005 int
1006 vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
1007 vm_offset_t *addr) /* OUT */
1008 {
1009 vm_map_entry_t entry;
1010 vm_offset_t end, st;
_______________________________________________________/usr/src/sys/vm/vm_map.c

首先是对所请求的数据进行判断。即所请求的起始地址必须大于该map的最低地址，而所请求的地址范围必须落在该map的最高地址之内，且所请求的地址范围不会跨越vm_size_t类型的表达极限。若树为空，则表示该map的地址空间尚是一块完整的没有开垦过的土地，因此返回其最低地址，查找成功结束。

_____________________________________________________________________FreeBSD6.0
1012 /*
1013 * Request must fit within min/max VM address and must avoid
1014 * address wrap.
1015 */
1016 if (start < map->min_offset)
1017 start = map->min_offset;
1018 if (start + length > map->max_offset || start + length < start)
1019 return (1);
1020
1021 /* Empty tree means wide open address space. */
1022 if (map->root == NULL) {
1023 *addr = start;
1024 goto found;
1025 }
_______________________________________________________/usr/src/sys/vm/vm_map.c

接下来是用入参地址start去对树进行splay操作，参见前面对vm_map_entry_splay()函数的分析，这个操作之后，新的树根所表示的地址区间要么就包含start，要么就紧接在start所属的空闲区域之前或者之后。首先假设新的树根位于start之后，如果start之后的空闲空间满足我们的需求，查找操作成功结束。如果start属于新树根的地址区间，我们就以新树根的终止地址作为请求的起始地址，否则仍然以start作为起始地址。map->root->end + map->root->adj_free实际上就找到了新树根在链表中的下一个entry的起始地址，也就是虚拟地址空间中位于新树根的地址区间之后的下一个非空闲区域的起始地址，用这个地址减去我们前面算出的请求起始地址，就能判断出这个空闲区间内是否有足够的空间满足我们的请求。如果满足，则查找成功结束。

_____________________________________________________________________FreeBSD6.0
1027 /*
1028 * After splay, if start comes before root node, then there
1029 * must be a gap from start to the root.
1030 */
1031 map->root = vm_map_entry_splay(start, map->root);
1032 if (start + length <= map->root->start) {
1033 *addr = start;
1034 goto found;
1035 }
1036
1037 /*
1038 * Root is the last node that might begin its gap before
1039 * start, and this is the last comparison where address
1040 * wrap might be a problem.
1041 */
1042 st = (start > map->root->end) ? start : map->root->end;
1043 if (length <= map->root->end + map->root->adj_free - st) {
1044 *addr = st;
1045 goto found;
1046 }
_______________________________________________________/usr/src/sys/vm/vm_map.c

流程走到这里，说明在和新root相邻的空闲空间中没有找到满足要求的空闲区域，需要我们继续往树中查找。注意，vm_map_findspace()函数只在入参start之后的地址空间中查找空闲区域，经过前面用start对整个树的splay处理，我们现在就可以确定，这样的空间如果存在，那它只能出现在当前树根的右子树中，因为这半个子树表示的才是地址空间中大于start的部分。如果右子树为空，那么我们就可以直接断定查找失败。如果右子树非空，但它的子树中没有超过我们所请求的length的空闲空间，那么我们也可以直接断定查找失败。此处的判断也正是前面所讲的vm_map_entry_splay()函数中计算max_free字段的意义所在。

_____________________________________________________________________FreeBSD6.0
1048 /* With max_free, can immediately tell if no solution. */
1049 entry = map->root->right;
1050 if (entry == NULL || length > entry->max_free)
1051 return (1);
_______________________________________________________/usr/src/sys/vm/vm_map.c

下面就是遍历右子树的代码，清晰明了。注意，FreeBSD查找可用空闲空间时使用的是first fit原则，即从低地址开始，返回满足条件的第一个空闲空间。由于splay树本质上就是一个二叉查找树，左小右大，所以遍历操作也按左、中、右的顺序来安排。其中的注释也提到了我们之前的分析，即右子树中的所有区域的地址都是大于start的。显然，之所以能进入这个遍历循环，是因为我们在第1050行判断过这个右子树中一定存在大于length的空闲空间，因此，遍历操作不可能以失败结束。所以在while循环之后会有一个panic，如果执行到了那条语句，那就说明max_free出问题了。注意，我们遍历每一级的时候都是用max_free字段来判断子树中是否有满足条件的空闲空间的。

_____________________________________________________________________FreeBSD6.0
1053 /*
1054 * Search the right subtree in the order: left subtree, root,
1055 * right subtree (first fit). The previous splay implies that
1056 * all regions in the right subtree have addresses > start.
1057 */
1058 while (entry != NULL) {
1059 if (entry->left != NULL && entry->left->max_free >= length)
1060 entry = entry->left;
1061 else if (entry->adj_free >= length) {
1062 *addr = entry->end;
1063 goto found;
1064 } else
1065 entry = entry->right;
1066 }
1067
1068 /* Can't get here, so panic if we do. */
1069 panic("vm_map_findspace: max_free corrupt");
_______________________________________________________/usr/src/sys/vm/vm_map.c

如果vm_map_findspace()函数的查找操作是针对内核映射而言，则需要将所请求的空间向上调整为页尺寸的整数倍，并根据实际情况决定是否增加内核的地址空间。

_____________________________________________________________________FreeBSD6.0
1071 found:
1072 /* Expand the kernel pmap, if necessary. */
1073 if (map == kernel_map) {
1074 end = round_page(*addr + length);
1075 if (end > kernel_vm_end)
1076 pmap_growkernel(end);
1077 }
1078 return (0);
_______________________________________________________/usr/src/sys/vm/vm_map.c