2023q1 Homework4 (quiz4)

contributed by < chiangkd >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85

測驗 `1`

延伸問題:

摘錄上述紅黑樹新增和刪除節點操作的程式碼，解釋其原理。不用列出完整程式碼，但要推敲其設計思維

提示: 善用 TreeComparison 製圖

運用你在第 3 週測驗題提及的延伸問題所開發出的效能評比程式，分析不同 rbtree 實作的效能落差
jemalloc 專案的 test/unit/rb.c 對 rbtree API 有更完整的涵蓋，其中 summarize/filter 能夠特化查詢範圍，請自 jemalloc 移植更豐富的 rbtree API 及其實作，並撰寫相關的測試程式 (含效能評比)
解讀 Linux 核心的 include/linux/rbtree.h, include/linux/rbtree_types, lib/rbtree.c 運作原理，並探討能否運用上述手法，以縮減 rbtree 節點的佔用空間

在原本的實作的結構體中，包含親代節點、左子、右子節點，且使用 __attribute__((aligned(sizeof(long)))) 使此結構體對齊 sizeof(long) 也就是讓最後兩個 bit 維持為 0，在日後便可利用這兩個 bit 中其一用以標示顏色

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

而改寫後的結構體如下，此時親代節點已經不保存於 rb_node 中

/* Node structure */
#define rb_node(x_type)           \
    struct {                      \
        x_type *left, *right_red; \
    }

rb_gen

#define rb_gen(x_attr, x_prefix, x_rbt_type, x_type, x_field, x_cmp)

在測試程式中， xprefix 為 tree_，在經歷一連串的展開、串接後就會拿到具有 tree_ 系列 prefix 的函式定義，例如測試程式中使用的 tree_new、tree_insert、tree_search 等等

新增以及刪除節點操作

老師貼文以及 wanghanchi 同學筆記

王漢祺同學研究給定的紅黑樹實作，他著手理解為何描述節點的結構體只包含指向左側和右側的指標，卻沒有親代節點的指標，這是因為既然紅黑樹的樹高增長較慢，與其在描述節點的結構體中多佔用一個指標的空間 (與 WORD_SIZE 等寬，亦即 64 位元或 32 位元，取決於微處理器架構)，不如挪動節點的走訪成為路徑。
以下圖為例，即將要插入的節點 key 為 90，於是節點走訪的過程可表示為:

先對 50 比較，得到 cmp = 1 後，就會往右側進行下一層的尋找，並紀錄 cmp

對 70 比較，一樣得到了 cmp = 1 後，就會往右邊進行下一層的尋找，並紀錄 cmp

再對 80 比較，得到 cmp = 1 後，就會往右邊進行下一層的尋找，這時會得到 NULL，並紀錄 cmp

跳出 for 迴圈，將 pathp 指向節點，亦即指向即將插入的節點

如此一來，即使描述節點的結構體不存在親代節點的指標，但運用上述路徑走訪，依然可完成插入的操作，也因此程式碼將這個特別的陣列命名成 path。

新增節點
在測試程式中 tree_insert 會透過建立好的隨機 nodes 陣列將其中的元素插入 tree 中。

for (int i = 0; i < NNODES; ++i)
    tree_insert(&tree, nodes + i);

查看其對應註解

 *   static void
 *   ex_insert(ex_t *tree, ex_node_t *node);
 *       Description: Insert node into tree.
 *       Args:
 *         tree: Pointer to an initialized red-black tree object.
 *         node: Node to be inserted into tree.

以測試程式為例

x_attr
$\to$ static
x_prefix
$\to$ tree_
x_rbt_type
$\to$ tree_t
x_type
$\to$ node_t
x_field
$\to$ link (name of rb tree node linkage)
x_cmp
$\to$ node_cmp

其中 node_cmp

static int node_cmp(const node_t *a, const node_t *b)
{
    int ret = (a->key > b->key) - (a->key < b->key);
    if (ret == 0 && a != b)
        assert(0 && "Duplicates are not allowed in the tree");
    return (ret);
}

key is search key，如果 a > b 則回傳 1 ， a < b 則回傳 -1，duplicate ，相等則回傳 0

在 tree_insert 中會先根據名稱定義的 tree_path_entry_t 型別的 path，其最大長度為 RB_MAX_DEPTH

#define RB_MAX_DEPTH (sizeof(void *) << 4)

在一般 64 位元的系統上， void * 為 8 bytes ，故 RB_MAX_DEPTH 將樹的最大深度限制在
$8 * 16 = 128$ bytes

Wind

在 tree_insert 中的 node 為要插入的節點，在第一個 for loop 中 (for (pathp = path; pathp->node; pathp++)) 會去比較 node 和當前 tree 中的節點 pathp->node ，如果有相同的 key 則觸發 assert。接著

如果 cmp < 0，即代表要放在左側作為左子節點，藉由 rbtn_left_get 獲取 pathp->node->link->left
- 這邊的 link 由 rb_node(node_t) 產生，其結構體包含 node_t * 型別的 left 以及 right_red
如果 cmp > 0，即代表要放在右側作為右子節點，藉由 rbtn_right_get 獲取該節點指標，但是因其後兩位 bit 作為顏色標示為 1 (紅色)，故額外使用 $ ~3 將其清除。

將走訪過的節點 accessor 紀錄於 pathp[1] 中，且 cmp 的結果紀錄於 path->cmp 中，最後走訪完成後將待插入的節點 node 置於 pathp->node。

利用兩個 assert 確認該 node 左右皆為 NULL

assert(!rbtn_left_get(x_type, x_field, node));
assert(!rbtn_right_get(x_type, x_field, node));

Unwind

接著在第二個 for loop 中倒著走訪回來 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--)

在迴圈中 cnode 為走訪中的 node，接著照順序查找剛剛紀錄下來的 cmp，如果 cmp < 0

  if (pathp->cmp < 0) {                                                    \
    x_type *left = pathp[1].node;                                          \
    rbtn_left_set(x_type, x_field, cnode, left);                           \
    if (!rbtn_red_get(x_type, x_field, left))                              \
      return;                                                              \
    x_type *leftleft = rbtn_left_get(x_type, x_field, left);               \
    if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {             \
      /* Fix up 4-node. */                                                 \
      x_type *tnode;                                                       \
      rbtn_black_set(x_type, x_field, leftleft);                           \
      rbtn_rotate_right(x_type, x_field, cnode, tnode);                    \
      cnode = tnode;                                                       \
    }                                                                      \
  }

透過 rbtn_left_set 將 cnode 的左子節點設定為 left ，若其 rbtn_red_get(x_type, x_field, left) 不存在，也就是其右節點是黑色的則直接 return，代表結束
如果沒有結束，則代表其右節點是紅色的，接著判斷該節點的左節點 (leftleft) 是否存在且右節點是否為紅色的，若真，則將 leftleft 塗黑並對著　cnode 進行右旋，在將 cnode 設定為 tnode ，也就是原來的親代節點的左子節點，作為新的親代節點 (迭代中的位置)。

刪除節點
同樣地在測試程式中根據 NNODES 數量進行刪除

for (int i = 0; i < NNODES; ++i) {
    tree_remove(&tree, nodes + i);
}

查看其對應註解

 *   static void
 *   ex_remove(ex_t *tree, ex_node_t *node);
 *       Description: Remove node from tree.
 *       Args:
 *         tree: Pointer to an initialized red-black tree object.
 *         node: Node in tree to be removed.

Wind

以下圖為例，刪除 49 節點

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

同樣的先走訪 tree，紀錄其 cmp 值，在 else 區塊有判斷 cmp 是否為 0，也就是找到要刪除的節點。

node	`48`	`60`	`50`	`49`
cmp	1	-1	-1	0 => 1 (Find node's successor)

在這邊也用了一個 assert 來檢查 nodep->node 是否指向要刪除的節點 node

assert(nodep->node == node);

pathp-- 後 pathp 指向 49

因其只有一個節點且沒有子節點，會進到條件中

if (rbtn_red_get(x_type, x_field, pathp->node)) {                          \
  /* Prune red node, which requires no fixup. */                           \
  assert(pathp[-1].cmp < 0);                                               \
  rbtn_left_set(x_type, x_field, pathp[-1].node, NULL);                    \
  return;                                                                  \
}

判斷到刪除的節點 49 為紅色節點，直接遺除掉就結束了

刪除完成

繼續下去此時若刪除節點 50，一樣從 root 開始逐個進行 cmp，建立表如下，

node	`48`	`60`	`50`	`51`	NULL
cmp	1	-1	0 => 1(Find node's successor)	-1

在比對到 cmp == 0 時 (50)

if (cmp == 0) {                                                        \
  /* Find node's successor, in preparation for swap. */                \
  pathp->cmp = 1;                                                      \
  nodep = pathp;                                                       \
  for (pathp++; pathp->node; pathp++) {                                \
    pathp->cmp = -1;                                                   \
    pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);       \
  }                                                                    \
  break;                                                               \
}

一進入時的 pathp 指向 50，並將其 cmp 設定為 1，path++ 後會指向 51，並將其 cmp 設定為 -1，接著透過 rbtn_left_get() 將 path 最後一個填入 NULL

此時 pathp 指向 NULL， nodep 指向 node 也就是 50

透過 pathp-- 此時 pathp 指向 51，進入條件 if (pathp->node != node) { 中，將 tred 為 1

rbtn_color_set 將 51 設定為黑色
rbtn_left_set 將 51 的左子節點設定為 50 的左子節點，也就是 NULL

接下來

rbtn_right_set 會將 51 的右子節點設定為 50 的右子節點，也就是 51 自己
rbtn_color_set 會將 50 設定成紅色

此處有註解

/* If node's successor is its right child, the following code */         \
/* will do the wrong thing for the right child pointer.       */         \
/* However, it doesn't matter, because the pointer will be    */         \
/* properly set when the successor is pruned.                 */

正好符合現在的情況，他的 successor 就是他的右子節點 (51)

接著把 nodep 和 pathp 指向的 node 交換，故此時 nodep->node 指向 51， pathp->node 指向 50，此時因 nodep[-1].cmp 為 -1 故將其左子節點設定為 nodep->node，也就是將 60 的左子節點設定成 51

在此處把 out-of-date 的 pathp[-1] (50) 的左子節點設定為 NULL

if (rbtn_red_get(x_type, x_field, pathp->node)) {                          \
  /* Prune red node, which requires no fixup. */                           \
  assert(pathp[-1].cmp < 0);                                               \
  rbtn_left_set(x_type, x_field, pathp[-1].node, NULL);                    \
  return;                                                                  \
}

刪除完成

此時在接著刪除 51 節點

Wind 部份與前述相似

node	`48`	`60`	`51`	NULL
cmp	1	-1	0 => 1(Find node's successor)

迭代完後來到刪除黑色節點，所以需要 Unwind 直到恢復平衡狀態，首先因刪除節點 (51) 的前一個為 60，其紀錄的 cmp 為 -1，且在本例中最後會進到這個 case (和註解長的不太一樣?)

else {                                                             \
/*      ||                                        */               \
/*    pathp(b)                                    */               \
/*  //        \                                   */               \
/* (b)        (b)                                 */               \
/*           /                                    */               \
/*          (b)                                   */               \
x_type *tnode;                                                     \
rbtn_red_set(x_type, x_field, pathp->node);                        \
rbtn_rotate_left(x_type, x_field, pathp->node, tnode);             \
pathp->node = tnode;                                               \
}

在 rbtn_rotate_left 中，會將 pathp->node (60) 的右子節點設定為 80 的左子節點，並將 r_node (80) 的左子節點設定為 pathp_node (60)

做完這一步後會長這樣

但從上方這張圖片到下方刪除完成後的結果似乎沒有實作?

刪除完成結果應長的如下

突然注意到在註解中有提到標頭檔中的巨集實作為 left-leaning 2-3 red-black tree

/* C macro implementation of left-leaning 2-3 red-black trees.  Parent
 * pointers are not used, and color bits are stored in the least significant
 * bit of right-child pointers, thus making node linkage as compact as is
 * possible for red-black trees.
 */

如此一來舉上面這個例子就不太正確了，在簡報中有提到左傾紅黑樹，3-nodes 的轉換必須是左傾的，而因為是 2-3 tree，所以暫不考慮 4-node 的情況

在傳統的紅黑樹下這樣的樹的樣子是可以接受的，但在左傾的情況下不行

左傾紅黑樹必須確保左節點是紅色的，也就是左子樹要比右子樹還要高或相等，在簡報中也有提到一個 "surprise"，也就是根據顏色交換 (color flip) 的位置不同可以將實作從 2-3-4 trees 變為 2-3 trees

這段也可以對應到在 insert 函式中的

if (left && rbtn_red_get(x_type, x_field, left)) {             \
    /* Split 4-node. */                                        \
    rbtn_black_set(x_type, x_field, left);                     \
    rbtn_black_set(x_type, x_field, right);                    \
    rbtn_red_set(x_type, x_field, cnode);
}

在論文中也有相對應的敘述

2-3 trees Remarkably, moving the color flip to the end in the top-down 2-3-4 tree implementation just described yields an implementation for 2-3 trees. We split any 4-node that is created by doing a color flip, passing a red link up the tree, and dealing with the effects of doing so in precisely the same way as we move up the tree.

測驗 `2`

延伸問題:

解釋上述程式碼運作原理，不用列出完整程式碼，但要推敲其設計思維，應參照論文〈On the Worst-Case Complexity of TimSort〉和〈Merge Strategies: from Merge Sort to TimSort〉
BONUS: 針對 Linux 核心原始程式碼的 lib/list_sort.c 和 lib/sort.c，提出 hybrid sorting 的引入和改進方案，並予以實作 → 之後可提交成果到 LKML
F9 microkernel 的 kernel/lib/sort.c 用非遞迴的方式實作快速排序，請評估導入 introsort 或更新的 hybrid sort 的效益

測驗 `3`

延伸問題

解釋上述程式碼運作原理，不用列出完整程式碼，但要推敲其設計思維
將測驗 1 對節點的紅色和黑色標注的技巧嵌入到指標變數中
Linux 核心的 rbtree 具備 cache 機制 (參見 Red-black Trees (rbtree) in Linux)，探討其原理，並嘗試在測驗 1 或測驗 3 的基礎之上實作

2023q1 Homework4 (quiz4)

開發環境

測驗 1

rb_gen

新增以及刪除節點操作

測驗 2

測驗 3

Reference

Read more

面試紀錄 & 練習 (聯發科)

2023q1 Homework1 (lab0)

將現有的 Raspberry PI 系統備份

Run FreeRTOS on VexRiscv and Measure/Tweak context switch overhead

測驗 `1`

測驗 `2`

測驗 `3`