中崎pst700,关于内核中PST的实现

很久没有写东西了，这几天看了下以前看过的东西，然后下午看了下内核中PST的实现。因为在网上很少，也找不到什么权威的分析，所以这里的分析也不能保证是完全正确的。先看相关的结构体：
下面是PST的根：
struct prio_tree_root { struct prio_tree_node *prio_tree_node; unsigned short index_bits; unsigned short raw; };
嵌入到vm_area_struct中的结构：
struct raw_prio_tree_node { struct prio_tree_node *left; struct prio_tree_node *right; struct prio_tree_node *parent; };
而其中的prio_tree_node:
struct prio_tree_node { struct prio_tree_node *left; struct prio_tree_node *right; struct prio_tree_node *parent; unsigned long start; unsigned long last; };
整个过程中比较麻烦的是插入的操作。下面就开始分析这个函数：
struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,struct prio_tree_node *node)
把node按照一定的规则插入到root中，然后再把node的指针返回。按道理来说插入是不应该失败的，所以如果是返回NULL的话就说明出现了BUG（）。具体什么规则就看函数的具体实现：
unsigned long radix_index, heap_index; unsigned long r_index, h_index, index, mask; int size_flag = 0;
如果把每个节点看做是一个区间的话，child节点的区间是[randix_index，heap_index]，parent对应的区间是[r_index，h_index]。根据node取得区间的过程是调用get_index函数：
static void get_index(const struct prio_tree_root *root,const struct prio_tree_node *node,unsigned long *radix, unsigned long *heap) { if (root->raw) { struct vm_area_struct *vma = prio_tree_entry( node, struct vm_area_struct, shared.prio_tree_node); *radix = RADIX_INDEX(vma); *heap = HEAP_INDEX(vma); } else { *radix = node->start; *heap = node->last; } }
初始化curr，mask后就要开始真正的插入过程了：
cur = root->prio_tree_node; mask = 1UL << (root->index_bits - 1);
如果现在的区间已经在PST中有保存就直接返回该节点，否则下面就遇到child，parent的比较：
if (h_index < heap_index || (h_index == heap_index && r_index > radix_index)) { struct prio_tree_node *tmp = node; node = prio_tree_replace(root, cur, node); cur = tmp; index = r_index; r_index = radix_index; radix_index = index; index = h_index; h_index = heap_index; heap_index = index; }
这个比较就体现了一个规则：parent的右边界永远大于child的右边界（如果parent也child的右边界相同，那么parent的左边界一定小于child的左边界）。其实更简单的说明就是，如果从根节点到叶子的一个路径上面区间是先按照heap_index从大到小排序，对于heap_index相同的几个区间按照radix从小到大排序。这里还没有涉及到平衡的问题，下面看如何选择左右子树：
if (index & mask) { if (prio_tree_right_empty(cur)) { INIT_PRIO_TREE_NODE(node); cur->right = node; node->parent = cur; return res; } else cur = cur->right; } else { if (prio_tree_left_empty(cur)) { INIT_PRIO_TREE_NODE(node); cur->left = node; node->parent = cur; return res; } else cur = cur->left; } mask >>= 1;
index&mask的作用是检查index的各个比特位是不是1，如果是1的话就到cur->right，否则就到cur->left。mask>>=1可知是从高位到低位依次检查的（这里的实现是不是和基数树很像？），这样的话小的都在左边，大的都在右边了。下面看index是从哪里来的：
if (size_flag) index = heap_index - radix_index; else index = radix_index;
在层数小于root->index_bits的时候可以保证left_child中的左边界总是小于right_child中的左边界。PST中因为有左边界相同的情况，所以然层数超过index_bits是有可能的。这时候是根据区间长度值中的比特位来决定向哪个方向走：
if (!mask) { mask = 1UL << (BITS_PER_LONG - 1); size_flag = 1; }
在层数超过的时候就初始化为Long能表示的最高位。这样的话，超过层数的时候首先是向左走的（这种情况出现的概率应该不是特别大）。到此为止，我们知道了PST中数据的组织方式。
------------------------------
欢迎拍砖。

延伸阅读