--- 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)
Last changed by  
 
坤諦江
451

Read more

2023q1 Homework1 (lab0)

contributed by < chiangkd > :::warning :warning: 留意細節！唯有重視小處並步步為營，方可挑戰原始程式碼達到三千萬行的 Linux 核心 :notes: jserv Got it! 謝謝老師 ::: 作業要求

3/24/2024
將現有的 Raspberry PI 系統備份

踩了不少雷，紀錄一下

12/6/2023
Run FreeRTOS on VexRiscv and Measure/Tweak context switch overhead

Github : FreeRTOS-on-VexRiscv Requirement and Expectation :::warning Reproduce Run FreeRTOS and multitasking on VexRiscv with FreeRTOS 202212.00 released or latest Study Reference Link to understand how to measure FreeRTOS context switch Understand how to accurately measure cycle count and related latencyInclude timer interrupt. Run above at simulator and quantify the performence about context switch

5/29/2023
2023q1 Homework7 (ktcp)

作業說明 開發環境 $ 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

5/11/2023
Read more from 坤諦江
Published on HackMD