2023q1 Homework4 (quiz4)

--- tags: linux2023 --- # 2023q1 Homework4 (quiz4) contributed by < [chiangkd](https://github.com/chiangkd) > ## 開發環境 ```shell $ 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` **延伸問題**: 1. 摘錄上述紅黑樹新增和刪除節點操作的程式碼，解釋其原理。不用列出完整程式碼，但要推敲其設計思維 >提示: 善用 [TreeComparison](https://github.com/tinfoilhater/TreeComparison) 製圖 2. 運用你在[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)提及的延伸問題所開發出的效能評比程式，分析不同 rbtree 實作的效能落差 3. [jemalloc](https://github.com/jemalloc/jemalloc) 專案的 [test/unit/rb.c](https://github.com/jemalloc/jemalloc/blob/dev/test/unit/rb.c) 對 rbtree API 有更完整的涵蓋，其中 summarize/filter 能夠特化查詢範圍，請自 jemalloc 移植更豐富的 rbtree API 及其實作，並撰寫相關的測試程式 (含效能評比) 4. 解讀 Linux 核心的 [include/linux/rbtree.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h), [include/linux/rbtree_types](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_types.h), [lib/rbtree.c](https://github.com/torvalds/linux/blob/master/lib/rbtree.c) 運作原理，並探討能否運用上述手法，以縮減 rbtree 節點的佔用空間在原本的實作的結構體中，包含親代節點、左子、右子節點，且使用 `__attribute__((aligned(sizeof(long))))` 使此結構體對齊 `sizeof(long)` 也就是讓最後兩個 bit 維持為 `0`，在日後便可利用這兩個 bit 中其一用以標示顏色 ```c struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); ``` 而改寫後的結構體如下，此時親代節點已經不保存於 `rb_node` 中 ```c /* Node structure */ #define rb_node(x_type) \ struct { \ x_type *left, *right_red; \ } ``` ### rb_gen ```c #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 同學筆記](https://hackmd.io/@wanghanchi/linux2023-quiz4)** >王漢祺同學研究給定的紅黑樹實作，他著手理解為何描述節點的結構體只包含指向左側和右側的指標，卻沒有親代節點的指標，這是因為既然紅黑樹的樹高增長較慢，與其在描述節點的結構體中多佔用一個指標的空間 (與 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` 中。 ```c for (int i = 0; i < NNODES; ++i) tree_insert(&tree, nodes + i); ``` 查看其對應註解 ```shell * 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` $\rightarrow$ `static` - `x_prefix` $\rightarrow$ `tree_` - `x_rbt_type` $\rightarrow$ `tree_t` - `x_type` $\rightarrow$ `node_t` - `x_field` $\rightarrow$ `link` (name of rb tree node linkage) - `x_cmp` $\rightarrow$ `node_cmp` 其中 `node_cmp` ```c 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` ```c #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`。接著 1. 如果 `cmp < 0`，即代表要放在左側作為左子節點，藉由 `rbtn_left_get` 獲取 `pathp->node->link->left` - 這邊的 `link` 由 `rb_node(node_t)` 產生，其結構體包含 `node_t *` 型別的 `left` 以及 `right_red` 2. 如果 `cmp > 0`，即代表要放在右側作為右子節點，藉由 `rbtn_right_get` 獲取該節點指標，但是因其後兩位 bit 作為顏色標示為 `1` (紅色)，故額外使用 `$ ~3` 將其清除。將走訪過的節點 accessor 紀錄於 `pathp[1]` 中，且 cmp 的結果紀錄於 `path->cmp` 中，最後走訪完成後將待插入的節點 `node` 置於 `pathp->node`。利用兩個 assert 確認該 `node` 左右皆為 `NULL` ```c 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` ```c 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` 數量進行刪除 ```cpp for (int i = 0; i < NNODES; ++i) { tree_remove(&tree, nodes + i); } ``` 查看其對應註解 ```shell * 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 節點 ![](https://i.imgur.com/9woVD3L.png) 同樣的先走訪 `tree`，紀錄其 `cmp` 值，在 `else` 區塊有判斷 `cmp` 是否為 `0`，也就是找到要刪除的節點。 | node | `48` | `60` | `50` | `49` | | ---- | ---- | ---- | ---- | ------------------------------ | | cmp | 1 | -1 | -1 | 0 => 1 (Find node's successor) | 在這邊也用了一個 `assert` 來檢查 `nodep->node` 是否指向要刪除的節點 `node` ```c assert(nodep->node == node); ``` `pathp--` 後 `pathp` 指向 `49` 因其只有一個節點且沒有子節點，會進到條件中 ```c 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` 為紅色節點，直接遺除掉就結束了刪除完成 ![](https://i.imgur.com/7TtJS4B.png) 繼續下去此時若刪除節點 `50`，一樣從 root 開始逐個進行 `cmp`，建立表如下， | node | `48` | `60` | `50` | `51` | NULL | | ---- | ---- | ---- | ----------------------------- | ---- | ---- | | cmp | 1 | -1 | 0 => 1(Find node's successor) | -1 | | 在比對到 `cmp == 0` 時 (`50`) ```c 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` 設定成**紅色** 此處有註解 ```c /* 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 ```c 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; \ } ``` 刪除完成 ![](https://i.imgur.com/zhKKGG3.png) 此時在接著刪除 `51` 節點 **Wind** 部份與前述相似 | node | `48` | `60` | `51` | NULL | | ---- | ---- | ---- | ----------------------------- | ---- | | cmp | 1 | -1 | 0 => 1(Find node's successor) | | 迭代完後來到刪除黑色節點，所以需要 **Unwind** 直到恢復平衡狀態，首先因刪除節點 (`51`) 的前一個為 `60`，其紀錄的 `cmp` 為 `-1`，且在本例中最後會進到這個 case (和註解長的不太一樣?) ```c 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) 做完這一步後會長這樣 ![](https://i.imgur.com/SXHkisV.png) 但從上方這張圖片到下方刪除完成後的結果似乎沒有實作? **刪除完成結果應長的如下** ![](https://i.imgur.com/OwXPmQN.png) 突然注意到在註解中有提到標頭檔中的巨集實作為 **left-leaning 2-3 red-black tree** ```c /* 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. */ ``` 如此一來舉上面這個例子就不太正確了，在[簡報](https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf)中有提到左傾紅黑樹，3-nodes 的轉換必須是左傾的，而因為是 2-3 tree，所以暫不考慮 4-node 的情況 ![](https://i.imgur.com/qoo3MlE.png) 在傳統的紅黑樹下這樣的樹的樣子是可以接受的，但在左傾的情況下不行 ![](https://i.imgur.com/GZZ2jMW.png) 左傾紅黑樹必須確保左節點是紅色的，也就是左子樹要比右子樹還要高或相等，在[簡報](https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf)中也有提到一個 **"surprise"**，也就是根據顏色交換 (color flip) 的位置不同可以將實作從 2-3-4 trees 變為 2-3 trees ![](https://i.imgur.com/qQH1WeA.png) 這段也可以對應到在 `insert` 函式中的 ```c 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); } ``` 在[論文](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf)中也有相對應的敘述 >**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` **延伸問題**: 1. 解釋上述程式碼運作原理，不用列出完整程式碼，但要推敲其設計思維，應參照論文〈[On the Worst-Case Complexity of TimSort](https://arxiv.org/abs/1805.08612)〉和〈[Merge Strategies: from Merge Sort to TimSort](http://nicolas.louvet.pages.univ-lyon1.fr/meef-nsi/m1-algoprog/TD7-tris/merge_strategies.pdf)〉 2. BONUS: 針對 Linux 核心原始程式碼的 lib/list_sort.c 和 lib/sort.c，提出 hybrid sorting 的引入和改進方案，並予以實作 → 之後可提交成果到 LKML 3. F9 microkernel 的 [kernel/lib/sort.c](https://github.com/f9micro/f9-kernel/blob/master/kernel/lib/sort.c) 用非遞迴的方式實作快速排序，請評估導入 [introsort](https://en.wikipedia.org/wiki/Introsort) 或更新的 hybrid sort 的效益 ## 測驗 `3` **延伸問題** 1. 解釋上述程式碼運作原理，不用列出完整程式碼，但要推敲其設計思維 2. 將測驗 `1` 對節點的紅色和黑色標注的技巧嵌入到指標變數中 3. Linux 核心的 rbtree 具備 cache 機制 (參見 [Red-black Trees (rbtree) in Linux](https://www.kernel.org/doc/Documentation/rbtree.txt))，探討其原理，並嘗試在測驗 1 或測驗 3 的基礎之上實作 ## Reference - [Wanhanchi](https://hackmd.io/@wanghanchi/linux2023-quiz4) - [Red/Black Tree](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)