Linux 核心專題: 紅黑樹實作

執行人: marsh-fish
專題解說錄影

任務簡介

延伸 2023 年專題，探究 Linux 核心的紅黑樹設計和實作。可重用原本的素材，但要重現所有實驗並改進程式碼。

Reviewed by ChenFuhuangKye

commit 3498397 增進英文表達，程式原本的出錯問題是?

這個 commit 是我拿來測試用的，請無視 commit 內容

介紹紅黑樹

簡述紅黑樹

紅黑樹是 2-3-4 樹的變形，1978 年 Leonidas J. Guibas 和 Robert Sedgewick 發明最初的紅黑樹。2008 年 Sedgewick 做了改進，並將此命名為 LLRBT (Left-leaning red–black tree，即 左傾紅黑樹)，後者相比 1978 年的紅黑樹要簡單，程式碼量更精簡，可參見 Left-leaning Red-Black Trees。

底下為一個符合規則的紅黑樹

在研究 rbtree.c 的程式碼時，發現了例子錯誤，下圖中的 Sr 應為小寫 S 加上小寫 r，組成 sr，但如果 N 節點與 sl 節點都有子節點的話，此紅黑樹也會成立，所以也可能是作者省略，不過我認為例子應該保持其簡單易懂，更改成 sr 會好一點。
Fix the example typo patch

/*
 * Case 3 - right rotate at sibling
 * (p could be either color here)
 *
 *   (p)           (p)
 *   / \           / \
 *  N   S    -->  N   sl
 *     / \             \
 *    sl  Sr            S
 *                       \
 *                        Sr
 ...

文字訊息「不要」用圖片展現！

TODO: 重做紅黑樹相關測驗題

均有設計和實作考量、完整的效能分析

TODO: 對第 3 週測驗 treesort.c 程式碼的理解

將 treesort.c 整合到 lab0-c ，探討 tree sort 的效率

commit 8fccccf

header

參考 LiChiiiii 的定義及程式
將list_head套用至 treesort.c 的結構裡並將 long 改成 char*

struct rb_node {
    uintptr_t color;
    struct rb_node *left, *right;
    char *value;
}__attribute__((aligned(sizeof(long))));

typedef struct __node {
    struct rb_node RBnode;
    struct list_head *list;
} node_t ;

同時 cmap_cmp_int 也要改寫成 cmap_cmp_str 使其能夠比較字串大小

static inline int cmap_cmp_str(void *arg0, void *arg1)
{
    char *a = (char *) arg0, *b = (char *) arg1;
    int result = strcmp(a, b);
    return result < 0 ? _CMP_LESS : result > 0 ? _CMP_GREATER : _CMP_EQUAL;
}

cmap_internal 改成與結構相符

struct cmap_internal {
    struct rb_node *head;

    /* Properties */
    size_t key_size, element_size, size;
    struct rb_node *it_end, *it_most, *it_least;
    int (*comparator)(void *, void *);
};

將上述定義結構與宣告函式之程式寫入 treesort.h

treesort.c

建立 treesort.c 以使用 treesort.h 定義的函式，這部份的僅列出想探討的部份

list_make_node

為了符合定義的結構將 list_make_node 的參數改寫成使用 list_head 類別，並用 cmap_create_node 來初始化 rb_node

node_t *list_make_node(struct list_head *list)
{
    node_t *node = malloc(sizeof(node_t));
    node->list = list;
    node->RBnode.value =
        ((element_t *) list_entry(list, element_t, list))->value;
    cmap_create_node(node);
    return node;
}

node_t *cmap_create_node(node_t *node)
{
    /* Setup the pointers */
    node->RBnode.left = node->RBnode.right = NULL;
    rb_set_parent(&(node->RBnode), NULL);

    /* Set the color to black by default */
    rb_set_red(&(node->RBnode));

    return node;
}

tree_free

功能相當於原本的 list_free 目的為釋放使用到的空間，以 DFS (Depth-First-Search) 的方式走訪每個節點

void tree_free(struct rb_node *node)
{
    if (!node)
        return;

    tree_free(node->left);
    tree_free(node->right);
    free(container_of(node, node_t, RBnode));
}

其餘的修改主要是將 node_t 的結構體改成 treesort.h 定義的 rb_node 結構體

qtest.c

新增 treesort 命令以方便使用 treesot, do_treesort 程式碼取至 do_sort 但不使用 set_noallocate_mode 因為在建立紅黑樹的時候會使用到 malloc

bool do_treesort(int argc, char *argv[])
{
    ...
    if (current && exception_setup(true))
        tree_sort(current->q);
    exception_cancel();
    ...
}

ADD_COMMAND(treesort,
                "Sort queue in ascending/descening order with tree sort", "");

執行看看

數字排序

cmd> show
Current queue ID: 0
l = [9 8 2 6 5 1]
cmd> treesort
l = [1 2 5 6 8 9]

字母排序

cmd> it RAND 5
l = [bkyeaezwp bcfykyts bgtjza juxuhi yiqyjg]
cmd> treesort
l = [bcfykyts bgtjza bkyeaezwp juxuhi yiqyjg]

可以成功進行排序，但在釋放記憶體的時候會出現錯誤訊息

cmd> free
l = NULL
ERROR: There is no queue, but 3 blocks are still allocated

注意用語：

• allocate 是「配置」，而非「分配」，避免無法與 dispatch 區隔

這是因為 it_end, it_most, it_least 有配置記憶體給他們，但配置給他們的空間並沒有被釋放，檢查程式碼發現，這三個變數並沒有被使用到，因此將 cmap_calibrate 註解，在 cmap_new 的宣告刪除

commit 5eef13f

改進你的漢語表達。

能夠成功釋放記憶體且不會有錯誤訊息

cmd> free
l = NULL
cmd> 
Freeing queue

cmd> it RAND 10000
l = [kjtpn jqlxp bcncdx ynssgd uyrsotju sshlouzmp dcuvaz galom srixx hpcahtfx hyforrqm lyzljfqfr qvjqoywf yldjn zxulxcuq wvfjxc ehbqhuij nahsaohsu pwvfnejob nggduem edylzuv ronfoidm lwugslt ombuq rrhunjmpf geclgcyu froeu yelpid kbiqqow onuhluaec ... ]
cmd> time treesort
l = [aabvut aacfzseue aacoyzxgd aadvsk aafwpycv aahhvdk aapnvp aarlnjcrp aawfoah aaxarpvjq aaxpitqo aazernv aazqzm abarifdmu abbdkfow abcvxl abeit abgvyo abjcb abjwafsad abroltd abveev abvhbfybp abvkcwnrh abvqrovzg abyhpgj acbhxmk acbxd accjnadap acdpvqe ... ]
Delta time = 0.125

treesort 平均五次下來為 0.126.2 s

參考 LiChiiiii 的作法

TODO: 對第 4 週測驗 LLRBT 程式碼的理解

在 2023 年第 4 週測驗一提供的程式碼中定義

#define rb_node(x_type)
    struct{
        x_type *left, *right_red;
    }

使用精準的描述。

可以看出與紅黑樹不同，不需要 parent 的指標，因此在程式碼的實作上也會有許多不同之處，下面是 LLRBT 中的旋轉和顏色翻轉，可以看出即使沒有親代節點的指標也能夠達成，不過需要提前知道下一步動作，因此在實作上才會透過 search path 來紀錄路線

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致

Node rotateLeft(Node h)
{
    x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x;
}
Node rotateRight(Node h)
{
    x = h.left;
    h.left= x.right;
    x.right= h;
    x.color = h.color;
    h.color = RED;
    return x;
}
void flipColors(Node h)
{
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
}

而與一般紅黑樹的操作中，最大的差異是若出現下圖左邊的情況，需執行左旋以符合左傾條件

兩種紅黑樹實作方式比較

特徵	Tree Sort	LLRBT
節點結構	包含左子節點、右子節點和親代節點的指標	包含左子節點和右子節點的指標，無親代節點直接紀錄
節點操作方式	通過節點的親代指標直接獲取和操作親代節點	使用額外的路徑陣列追蹤操作路徑並對紅黑樹進行平衡
空間佔用	需要額外的指標記錄親代節點，佔用更多的內存空間	不需要額外的指標記錄親代節點，節省內存空間
平衡操作複雜度	平衡操作相對較簡單，直接通過指標修改節點的親代關係	平衡操作較複雜，需要使用陣列記錄路徑並進行調整
適用場景	操作和追蹤節點的親代關係較為頻繁的場景	節點操作和平衡操作頻率較低的場景

TODO: 紅黑樹實作的效能評比

利用 rb-bench，分析不同紅黑樹實作手法的差異，應當考慮更大的資料範圍

對照 rbtree_bench

執行 rb-bench

fork rb-bench 並執行以下命令

make all
./rb-bench > reports/test-linux-emag.xml
make images

注意用語：

• command 是「命令」，而非「指令」(instruction)

我有修改原本的 make images 命令使其相當於執行 ./plot.py reports/test-linux-emag.xml reports/test-linux-emag.png 才能夠成功執行 python 並將圖片生成於 reports 目錄下，便可得到以下這張圖，其中

Linear: 插入的節點為遞增的數值。
RandomOps: 若要插入的隨機數已在樹中就將其移除，反之進行插入。

下圖為small_set_size = 128時的結果

會發現再左側的 X 軸和底部的 Y 軸以及上方的標題都出現了重疊的數值，猜測是 python 語法因為版本不同而產生的錯誤顯示，仔細看可以看出上方重疊一個 X ，對照 python 檔便可得知 plt.title('x') 是產生此重疊的原因將該行刪除，再輸出一次

commit 8fb9889

Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap

下圖為small_set_size = 256時的結果

Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap

下圖為small_set_size = 512時的結果

Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap

下圖為small_set_size = 1024時的結果

Linear: LLRB > Eternally Confuzzled > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap

當 small_set_size 大於 512 的時候，在 Linear 的部份 LLRB 的時間已經大於 Eternally Confuzzled 所需要的時間，猜測在 small_set_size = 2048 時其差距會更大

下圖為small_set_size = 2048時的結果

Linear: LLRB > Eternally Confuzzled > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap

根據 small_set_size = 2048 的結果得知先前 LLRB > Eternally Confuzzled 的假設是正確的，其他線圖的斜率也沒發生重大的變化，若所有方法都是線性增長的，可以推知資料再增大也不會有變化

思考現有的 rb-bench 是否足以代表真實世界的場景？

TODO: 分析不同紅黑樹實作手法的差異

應予以解讀並說明應用場景。

Linear 相當於僅有插入節點沒有刪除節點操作，而 RandomOps 若遇到以出現過的節點的情況會將已存在的節點刪除，所以 Linear 和 RandomOps 的差異可以想成是有刪除操作與否。所以在應用場景上，例如前面做的 treesort.c ，在 treesort.c 中，紅黑樹的操作只有使用到插入節點的功能，所以使用 FreeBSD 便會達到最好的效果，在會使用到刪除的場景上，如 timer ，則使用 bheap 會達到最好的效果。

用 Linux 核心在內的開放原始碼專案，探討其紅黑樹設計的考量和效能表現。

jemalloc 使用特化的 LLRBT

TODO: 探討 Linux 核心 augmented rbtree 實作手法

Linux 核心的 augmented rbtree 在設計上與經典的紅黑樹不同，探究其 rbtree_augmented.h 的設計。

以下規則參照 rbtree.c 的程式碼

插入節點

當插入的節點之親代節點為紅色時會有三個不同的情況會需要判斷，以下是三種不同的操作

Case 1 - 親代的平輩節點為紅色 (祖代節點 (grandparent) 與其子節點顏色翻轉)：

例子

插入 40，遇到 Case 1

65 節點與其子節點顏色翻轉並移到65

27 節點與其子節點顏色翻轉並移到27

27 顏色翻轉結束迴圈操作

這裡先示範插入節點的親代節點為黑色時會如何
插入 100，由於 100 的親代節點為黑色因此可以直接插入

Case 3 - 親代的平輩節點為黑色且為其親代節點的左(右)子點 (對其祖代節點做右(左)旋)：

例子

插入 105，遇到 Case 3

對 98 做左旋

98 100 顏色對調

Case 2 - 親代的平輩節點為黑色且插入的節點為親代節點的右(左)子點 (對插入的節點之親代節點做左(右)旋)：

例子

插入 46，遇到 Case 2

對 40 做左旋

在linux版本的紅黑數中，做完 Case 2 後會直接執行 Case 3 的操作，因此對 49 做右旋

46 49 顏色對調

刪除節點

當我們刪除節點的時候會先判斷是否需要執行再平衡(rebalance)，因為當我們刪除節點後可能不會影響到樹的平衡，此時便無需再平衡。

根據以下幾種情況判斷是否需要執行再平衡

Case 1 - 當刪除的節點沒有超過 1 個子節點：

若刪除的節點沒有子節點且該節點為紅色，可以直接刪除不會影響平衡，例如底下圖式的 2, 40, 49, 98, 105；若刪除的節點只有一個子節點，根據紅黑樹的規則只會有一種情況，該節點為黑色，其子節點為紅色，如 7, 2 ，此時也可以直接刪除並將子節點補上並變色

例子

刪除 7

也就是說若刪除的節點沒有子節點且該節點為黑色，就需要執行再平衡
例如現在這個圖的 2, 25, 31

Case 2 - 當刪除的節點的後繼節點(successor)是該節點右子節點：

刪除後變成

以我們的例子來說的話， 19, 46, 100 節點便是 Case 2

其中，後繼節點的子節點不一定存在，若後繼節點的子節點存在則無須再平衡；若後繼節點的子節點不存在，根據後繼節點的顏色來決定是否再平衡。

Case 3 - 當刪除的節點的後繼節點 (successor) 是該節點右子節點的最左子節點：

刪除後變成

以我們的例子來說的話， 27, 34, 65 節點便是 Case 3

Case 2, Case 3 是否需要再平衡的判斷是一樣的，主要的差異為程式的實作。

再平衡

接著再做再平衡的時候也會有四種情況需要考慮，但此時四種情況是會依序判斷並執行

Case 1 - 刪除節點為親代節點的左(右)子節點，平輩節點為紅色，對親代節點左(右)旋，並保持與旋轉前相當的顏色
Case 2 - 刪除節點為親代節點的左(右)子節點，平輩節點的左(右)子節點為黑色，平輩節點顏色翻轉，若不是從 Case 1 進入到 Case 2 則遞迴向上
Case 3 - 刪除節點為親代節點的左(右)子節點，平輩節點的右(左)子節點為黑色，對平輩節點右(左)旋
Case 4 - 刪除節點為親代節點的左(右)子節點，對親代節點左(右)旋 + 顏色翻轉

其中 Case 4 的旋轉會依照以下規則進行：

左旋後

s 節點的顏色會等同旋轉前 p 節點的顏色
sl 節點的顏色則會保持不便
旋轉後的 p, sr 節點顏色會是黑色

例子

刪除 31

遇到 Case 1，對 34 左旋

34 65 顏色對調

遇到 Case 4，對 34 左旋

顏色翻轉

刪除 49

34 左子節點為黑色，Case 3，對 34 左旋

接續執行 Case 4，右旋

顏色翻轉

刪除 2

遇到 Case 2，將 25 顏色翻轉，並遞迴至 19 節點

遇到 Case 3，對 65 右旋

接續執行 Case 4，對 27 左旋

顏色翻轉

針對其他學員 (含授課教師和社會人士) 在開發紀錄頁面提出的問題或建議

Linux 核心專題: 重作第 3, 4, 7 週測驗題
Linux 核心專題: 紅黑樹實作改進
Linux 核心專題: 浮點數運算案例探討
Linux 核心專題: 高性能網頁伺服器
Linux 核心專題: 虛擬無線網路裝置驅動程式