闡述Linux內(nèi)存管理：紅黑樹
很多的人都開始學(xué)習(xí)Linux操作系統(tǒng)。當(dāng)我們學(xué)習(xí)Linux時(shí)，會(huì)遇到很多的問題。最近看Linux內(nèi)存管理，看到紅黑樹這一部分甚為頭大，于是了解了一下紅黑數(shù)的基本知識(shí)。詳細(xì)講解一下Linux內(nèi)存管理。
紅黑樹是平衡二叉樹的一種，它有很好的性質(zhì)，樹中的結(jié)點(diǎn)都是有序的，而且因?yàn)樗旧砭褪瞧胶獾?，所以查找也不?huì)出現(xiàn)非常惡劣的情況，基于二叉樹的操作的時(shí)間復(fù)雜度是O(log(N))。Linux內(nèi)核在管理vm_area_struct時(shí)就是采用了紅黑樹來維護(hù)內(nèi)存塊的。
先到include/Linux/rbtree.h中看一下紅黑樹的一些定義，如下：
- struct rb_node
- {
- struct rb_node* rb_parent; 該節(jié)點(diǎn)的父節(jié)點(diǎn)
- int rb_color; 該節(jié)點(diǎn)的顏色
- #define RB_RED 0
- #define RB_BLACK 1
- struct rb_node *rb_right; 該節(jié)點(diǎn)的右子節(jié)點(diǎn)
- struct rb_node *rb_left; 該節(jié)點(diǎn)的左子節(jié)點(diǎn)
- } __attribute__((aligned(sizeof(long))));
struct rb_root只是struct rb_node*的一個(gè)包裝，這樣做的好處是看起來不用傳遞二級(jí)指針了。不錯(cuò)，很簡(jiǎn)單。
測(cè)試顏色和設(shè)置顏色也是水到渠成的事了。需要特別指出的是下面的一個(gè)內(nèi)聯(lián)函數(shù)：
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);
它把parent設(shè)為node的父結(jié)點(diǎn)，并且讓rb_link指向node。
我們把重點(diǎn)集中在lib/rbtree.c上，看看一些和紅黑樹相關(guān)的重要算法。開始之前我們一起回憶一下紅黑樹的規(guī)則：
1. 每個(gè)結(jié)點(diǎn)要么是紅色要么是黑色；
2. 根結(jié)點(diǎn)必須是黑色；
3. 紅結(jié)點(diǎn)如果有孩子，其孩子必須都是黑色；
4. 從根結(jié)點(diǎn)到葉子的每條路徑必須包含相同數(shù)目的黑結(jié)點(diǎn)。
5、每個(gè)樹節(jié)點(diǎn)N的左孩子樹上的所有元素都是排在N之前，右孩子樹子上的所有元素都是排在N之后
這四條規(guī)則可以限制一棵排序樹是平衡的。
__rb_rotate_left是把以root為根的樹中的node結(jié)點(diǎn)進(jìn)行左旋，__rb_rotate_right是進(jìn)行右旋。這兩個(gè)函數(shù)是為后面的插入和刪除服務(wù)，而不是為外部提供接口。
新插入的結(jié)點(diǎn)都設(shè)為葉子，染成紅色，插入后如果破壞了上述規(guī)則，通過調(diào)整顏色和旋轉(zhuǎn)可以恢復(fù)，二叉樹又重新平衡。插入操作的接口函數(shù)是
void rb_insert_color(struct rb_node *node, struct rb_root *root);
它把已確定父結(jié)點(diǎn)的node結(jié)點(diǎn)融入到以root為根的紅黑樹中，具體算法的分析可以參考[1]中第14.3節(jié)，這里的實(shí)現(xiàn)和書中的講解幾乎完全一樣。怎么確定node的父結(jié)點(diǎn)應(yīng)該在調(diào)用rb_insert_color之前通過手工迭帶完成。值得指出的一點(diǎn)是，雖然插入操作需要一個(gè)循環(huán)迭代，但是總的旋轉(zhuǎn)次數(shù)不會(huì)超過兩次！所以效率還是很樂觀的。
刪除操作多多少少都有點(diǎn)麻煩，它要先執(zhí)行像普通二叉查找樹的“刪除”，然后根據(jù)刪除結(jié)點(diǎn)的顏色來判斷是否執(zhí)行進(jìn)一步的操作。刪除的接口是：
void rb_erase(struct rb_node *node, struct rb_root *root);
其實(shí)它并沒有真正刪除node，而只是讓它和以root為根的樹脫離關(guān)系，最后它還要判斷是否調(diào)用__rb_erase_color來調(diào)整。具體算法的講解看參考[1]中第13.3和14.4節(jié)，__rb_erase_color對(duì)應(yīng)書中的RB-DELETE-FIXUP，此處的實(shí)現(xiàn)和書上也基本上一致。
其余的幾個(gè)接口就比較簡(jiǎn)單了。
struct rb_node *rb_first(struct rb_root *root);
在以root為根的樹中找出并返回最小的那個(gè)結(jié)點(diǎn)，只要從根結(jié)點(diǎn)一直向左走就是了。
struct rb_node *rb_last(struct rb_root *root);
是找出并返回最大的那個(gè)，一直向右走。
struct rb_node *rb_next(struct rb_node *node);
返回node在樹中的后繼，這個(gè)稍微復(fù)雜一點(diǎn)。如果node的右孩子不為空，它只要返回node的右子樹中最小的結(jié)點(diǎn)即可；如果為空，它要向上查找，找到迭帶結(jié)點(diǎn)是其父親的左孩子的結(jié)點(diǎn)，返回父結(jié)點(diǎn)。如果一直上述到了根結(jié)點(diǎn)，返回NULL。
struct rb_node *rb_prev(struct rb_node *node);
返回node的前驅(qū)，和rb_next中的操作對(duì)稱。
void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);
用new替換以root為根的樹中的victim結(jié)點(diǎn)。
因?yàn)榧t黑樹的這些良好性質(zhì)和實(shí)現(xiàn)中接口的簡(jiǎn)易性，它被廣泛應(yīng)用到內(nèi)核編程中，大大提高了內(nèi)核的效率。
通過本文的介紹你就能熟練掌握Linux內(nèi)存管理。
【編輯推薦】
