研讀 box64 的紅黑樹實作

研讀 box64 的紅黑樹實作問題： 1. 紅黑樹在 box64 專案中的作用為何？ 2. 為何一定要使用紅黑樹？ 3. 我能如何改進呢？ ## 基本紅黑樹的特性 1. 所有節點非黑即紅 2. 根節點為黑 3. 葉子節點為黑 4. 紅色節點的子節點必為黑色節點 5. 對於每一個節點，所有通往其後代葉子節點的路徑上必含一樣數量的黑色節點 ## box64 中的紅黑樹 >The main functionality of the red-black trees is to provide a fast, cheap way to map ranges of addresses to a number and acccessing by providing an address in this range. [#2039](https://github.com/ptitSeb/box64/issues/2039#issuecomment-2485419771) 紅黑樹實作來自 2023 年 12 月 31 日合併的 [#1180](https://github.com/ptitSeb/box64/pull/1180) (即 commit [5e9e1faedc97194e46f3fb4b3665ec416ce7efbf](https://github.com/ptitSeb/box64/commit/5e9e1faedc97194e46f3fb4b3665ec416ce7efbf)) > This PR switches the way memory permission is tracked, from a sparse array to a red-black tree (self-balancing binary search tree). The notion of hot pages has also been removed. > > Performance does not seem to be very impacted, and memory usage has decreased a bit for processes which used a lot of RAM (for example, Steam uses ~100M less memory and every process of wine uses ~15M less memory). 藉由 `git checkout 5e9e1faedc97194e46f3fb4b3665ec416ce7efbf^` 可以切換到引入紅黑樹之前的版本，可以注意到在早期的版本所有記憶體有關的操作都在 `custommem.c` 之中，閱讀早期的 `custommem.c` 對理解 box64 的記憶體管理有巨大的幫助。而改用紅黑樹後，節省大量的記憶體，且效能衝擊不明顯（嗎？）。因此，倘若我們可提出效能略好但更省記憶體的方案 (如 jemalloc 的 rb，及後續 rv32emu 的 map)，應可讓 box64 受益。 ##### 節點的結構： ```c typedef struct rbnode { struct rbnode *left, *right, *parent; uintptr_t start, end; uint32_t data; uint8_t meta; } rbnode; ``` 可以注意到在 box64 的紅黑樹節點紀錄了兩個資訊 : 整數 `data` 與記憶體區段 ( `start` ~ `end`)。如此一來便可以用較小的記憶體（48）來管理一大段記憶體（e.g allocsize = 2097168） `meta` 代表 `IS_LEFT` (0x1), `IS_BLACK` 或 `0` 利用 `sizeof` 可以觀察到節點的大小為 48 bytes 。在標頭檔 [rbtree.h](https://github.com/ptitSeb/box64/blob/main/src/include/rbtree.h) 中發現在 box64 專案中定義了以下有關紅黑樹的操作： ```c rbtree_t* rbtree_init(const char* name); void rbtree_delete(rbtree_t* tree); uint32_t rb_get(rbtree_t* tree, uintptr_t addr); int rb_get_end(rbtree_t* tree, uintptr_t addr, uint32_t* val, uintptr_t* end); int rb_set(rbtree_t* tree, uintptr_t start, uintptr_t end, uint32_t data); int rb_unset(rbtree_t* tree, uintptr_t start, uintptr_t end); uintptr_t rb_get_righter(rbtree_t* tree); ``` 1. `rb_get` : 藉由 `addr` 找到其所屬的紅黑樹節點並回傳節點的 `data` 。例如 `getProtection`, `getProtection_fast` 和 `getMmapped` 都是藉由 `rb_get` 的回傳值來判斷 1. `rb_get_end` :藉由 `addr` 找到其所屬的紅黑樹節點並利用指標寫入的方式獲取該節點的 `data` 以及記憶體區段的結尾 `end` 。由於可以獲得某一記憶體區段的結尾 `end` ， `rb_get_end` 可以用來走訪一大段連續的記憶體。 2. `rb_set` : 將記憶體區段 ( `start` ~ `end`) 與 `data` 加入紅黑樹，若新加入的記憶體片段與原有的儲存的記憶體片段有重疊，則重疊部分的 `data` 會被覆蓋成新的 `data`，如此一來便不會有重疊的記憶體片段。 3. `rb_unset` : 刪除記憶體區段 ( `start` ~ `end`) 4. `rb_get_righter` : 回傳指向紅黑樹 `tree` 的最右節點的指標，該節點代表的是整顆紅黑樹所涵蓋的記憶體範圍中地址最大的區段。我們來看看 box64 紅黑樹的細節： ([rbtree.c](https://github.com/ptitSeb/box64/blob/main/src/tools/rbtree.c)) ```c int add_range(rbtree *tree, uintptr_t start, uintptr_t end, uint32_t data) { rbnode *cur = tree->root, *prev = NULL; while (cur) { prev = cur; if (cur->start < start) cur = cur->right; else cur = cur->left; } return add_range_next_to(tree, prev, start, end, data); } ``` 這個函式的目標是藉由指標 `start` 找到節點 `prev` 並呼叫函式 `add_range_next_to` 而這個 `prev` 是什麼呢？可以從註解 `// Make sure prev is either the rightmost node before start or the leftmost range after start` 得到提示：`prev` 是離 `start` 所指向的地址最近的節點 (結尾節點) 換句話說，box64 的紅黑樹與傳統二元搜尋樹不一樣，是以指定的地址而非 `data` 的數值作為插入的依據。 ### 紅黑樹與記憶體管理在 box64 中使用了四顆紅黑樹來做記憶體管理與追蹤，分別是: - `memprot` : 紀錄一段記憶體的存取權限 - `mapallmem`：紀錄所有 memory mapping - `mmapmem` ：紀錄由 mmap 所 map 出來的記憶體 - `blockstree`：紀錄一段 block 的記憶體，其 `data` 為該 block 在陣列 p_block 中的索引值 `mapallmem` 跟 `mmapmem` 的 `data` 有三種數值，分別為： - `0` : 該段記憶體沒有被 mapped - `1` : 該段記憶體被被 mapped 並紀錄在 `mapallmem` - `2` : 該段記憶體被被 mmap mapped 並同時紀錄在 `mapallmem` 與 `mmapmem` 問題 1.由 map 所配置的記憶體為何要被特別紀錄？ 2. 為何不統一紀錄在 `mapallmem` ，並用 `data` 來紀錄是否為 mmap 所配置的記憶體，畢竟使用 `rb_get` 就能檢查某段記憶體是否被紀錄在紅黑樹中會用到 `mmapmem` 的函式只有這時我們要分析 `setProtection` 與 `setProtection_mmap` 的差異，因為這是唯一一個 `mmapmem` 被建立的場景。後者被使用的場景有 `src/tools/wine_tools.c` 和 `src/wrapped/wrappedlibc.c` 務必要釐清 `mmapmem` 與 `mapallmem` 的核心差異，方能合併兩者 ```c setProtection_mmap((uintptr_t)my_wine_reserve[idx].addr, my_wine_reserve[idx].size, 0); ``` ## 追蹤紅黑樹操作 #### 1. 修改程式碼，加入 printf 追蹤以下動作： - rb_set - rb_unset - rb_get - rb_get_end #### 2. [重新編譯 box64](https://hackmd.io/@lambert-wu/HJ6royNKR#:~:text=linux%2Dgnu%2Dgcc-,%E7%B7%A8%E8%AD%AF%20box64,-%E7%95%99%E8%A8%80) 但編譯時會遇到小問題: ```shell /home/chiu/box64/src/tools/rbtree.c:728:93: note: 'stdout' is defined in header '<stdio.h>'; did you forget to '#include <stdio.h>'? ``` 問題不大，加上`include <stdio.h>`即可 #### 3. 在 pc 端上用 qemu [測試](https://hackmd.io/Uqi1DK8VToup_UGi73r-Mw?both#:~:text=sysroot/lib/custom-,%E6%8E%A5%E8%91%97%E5%88%A9%E7%94%A8%20QEMU%20%E6%B8%AC%E8%A9%A6%3A,-%E7%95%99%E8%A8%80): 1. 將可執行檔 box64 改為 box64_mark 避免混淆，接著記得將其位置加入環境變數 PATH 中 2. 執行 `qemu-riscv64 -L sysroot box64_mark --help` 來檢查是否可以成功模擬 box64_mark 但此時會遇到錯誤： ```shell qemu-riscv64: Could not open '/lib/ld-linux-riscv64-lp64d.so.1': No such file or directory ``` 原來是之前使用 sysroot 時誤刪了重要的檔案 '/lib/ld-linux-riscv64-lp64d.so.1' ，重新下載之後執行: ```shell qemu-riscv64 -L Documents/riscv/sysroot box64/build_mark/box64_mark --help ``` 就可以看到相關資訊 4. 執行 `box64_mark` 並統計輸出結果，以 `qsort_x86` 為例： - rb_set: 223 - add_range: 35 - Adding: 73 - Removing: 20 - rb_unset: 21 - rb_get: 196 - rb_get_end: 220 - rb_get_righter 0 #### 4. 在 Tinker V 上測試： >box64 的測試不能全在 QEMU 上進行，因為後者採用動態編譯，行為會不一致，因此需要在 Tinker V 實驗問題：動態編譯為何會導致紅黑樹的行為不一致呢？ 1. 在 pc 端編譯用於統計命令的 `count.c` 並將其傳輸至 `tk2` 1. 利用命令 `scp -O box64_mark tk2:/debian/usr/bin/` 將編譯好的 `box64_mark` 放入 `tk2` 上的`/debian/usr/bin` 2. 執行 `box64_mark [file name] | ./count` 並觀察輸出，以 qsort 為例： | Operation | Count | |-----------------|-------| | rb_set | 192 | | add_range | 4 | | Adding | 74 | | Removing | 4 | | rb_unset | 1 | | rb_get | 683 | | rb_get_end | 499 | | rb_get_righter | 0 | 可以發現有些程式在執行第二次後其命令數目便會固定，但有些程式的命令數目則始終保持恆定 4. 以下是各 bench 在執行第三次後的命令數量統計： | bench | rb_set | Adding | Removing | rb_unset | rb_get | rb_get_end | rb_get_righter | |----------------|--------|--------|----------|----------|--------|------------|----------------| | qsort | 241 | 87 | 51 | 63 | 1090 | 753 | 3 | | primes | 165 | 56 | 20 | 33 | 613 | 507 | 3 | | dhrystone | 187 | 64 | 28 | 42 | 801 | 586 | 5 | | aes | 208 | 72 | 36 | 47 | 978 | 648 | 5 | | norx | 215 | 74 | 38 | 51 | 1042 | 678 | 3 | | miniz | 486 | 196 | 152 | 147 | 2818 | 1535 | 11 | | sha512 | 176 | 64 | 28 | 44 | 771 | 566 | 3 | 問題： 1. 是否有像是「清理快取」的功能以便觀察建立快取的情形？ 2. 是否有必要觀察「建立快取」的過程？ #### 5. 對照 box64 的紅黑樹操作與 Mado 視窗操作為了避免細微的動作對結果的影響，有關預測量之視窗事件的動作皆會重複多次： | 視窗事件 | rb_set | rb_unset | rb_get | rb_get_end | rb_get_righter | |------------|--------|----------|--------|------------|----------------| | 未動作（僅關閉視窗） | 6261 | 332 | 37695 | 14404 | 6 | | 拖曳視窗（沿著邊匡繞三圈）| 6568 | 342 | 45753 | 15068 | 6 | | 滑鼠點擊（十次）| 6569 | 342 | 40242 | 15067 | 6 | | 滑鼠移動（沿著邊匡繞三圈）| 6420 | 338 | 42496 | 14735 | 6 | | 操作計算器（三次）| 6627 | 343 | 43870 | 15185 | 6 | 可以注意到 `rb_get` 與 `rb_get_end` 的數量皆是「萬」級，若能精簡紅黑樹節點佔用的空間，使一條 cacheline 中能塞入更多節點，將對效能產生巨大的影響 ### 將 box64 的紅黑樹程式碼抽出並獨立運作目標：熟悉 box64 紅黑樹在 box64 記憶體操作流程中所扮演的角色，即以下三個函式中: - `box64context.c` : rbtree_init, rbtree_delete - `custommem.c` : findBlock, internal_customMalloc, internal_customMemAligned, FindDynablockFromNativeAddress, box32_dynarec_mmap, AllocDynarecMa, FreeDynarecMap, protectDBJumpTable, protectDB, unprotectDB, isprotectedDB, updateProtection, setProtection, setProtection_mmap, setProtection_elf, refreshProtection, allocProtection, freeProtection, getProtection, getProtection_fast, getMmapped, memExist, find31bitBlockNearHint, find47bitBlockNearHint, isBlockFree, reverveHigMem32, my_reserveHighMem, init_custommem_helper - `dynablock.c` : InvalidDynablock, InvalidDynablock, internalDBGetBlock 為了方便測試，可將 `dynablock.c` 和 `box64context.c` 內用到的紅黑樹操作合併到 `custommem.c` 。 TODO:說明結構 `context` 的用途 TODO:box64 +wine 會用到 8200 個節點，深度為 14，遠遠於最大深度限制，但為何會造成錯誤執行以下命令: ```shell $ mkdir -p rbtree-test $ cd rbtree-test $ wget https://raw.githubusercontent.com/ptitSeb/box64/refs/heads/main/src/include/rbtree.h $ wget https://raw.githubusercontent.com/ptitSeb/box64/refs/heads/main/src/tools/rbtree.c ``` 修改 `rbtree.c` 的開頭數行: ```c #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdlib.h> #include "rbtree.h" #ifdef RBTREE_TEST #define printf_log(...) #define dynarec_log(...) #define rbtreeMalloc malloc #define rbtreeFree free #else #include "custommem.h" #include "debug.h" #define rbtreeMalloc customMalloc #define rbtreeFree customFree #endif ``` 編譯和測試: ```shell $ gcc -O2 -o rbtree -I. -D RBTREE_TEST rbtree.c $ ./rbtree ``` 參考執行輸出: ``` [0] ([1], (B/0x600000a042a0) 130000-140000: 7, [1]) ([1], (B/0x600000a042a0) 130000-140000: 7, ([1], (R/0x600000a042d0) 141000-142000: 135, [1])) ([1], (B/0x600000a042a0) 130000-140000: 7, ([1], (R/0x600000a042d0) 140000-142000: 135, [1])) ([1], (B/0x600000a042a0) 130000-141000: 7, ([1], (R/0x600000a042d0) 141000-142000: 135, [1])) ([1], (B/0x600000a042a0) 130000-140000: 7, ([1], (R/0x600000a042d0) 140000-142000: 135, [1])) 0x141994 has attribute 135 ``` 可在此目錄執行 `git init ; git add *.[ch] ; git commit -a` 以將紅黑樹程式碼納入版本控制，便於後續實驗。 #### 使用 GDB 分析 box64 記憶體管理流程以 `qsort_x86` 為例，分析紅黑樹相關操作的啟動流程 ```shell gdb --args box64 qsort_x86 ``` ### Hook Function 程式配置記憶體的頻繁程度和區域巔峰量吞吐量的定義為單位時間所操作的記憶體大小由於節點大小是固定的，所以計算方式就是（節點數量＊節點大小）/ 時間建立紀錄資訊用的結構： ```c typedef struct record_item{ const char* tree_name; const char* op_name; long tree_number; long node_number; struct tm *op_time; }record_item; ``` TODO：建立共享記憶體空間後在程式執行的過程中將資訊紀錄在 `record_item` 陣列中 #### 搭配 custommem.c 並設計測試情境在開始測試前需要將 custommem.c 所需的檔案一併獨立出來 1. 配置 block 2. 刪除 block 3. 查看 block 4. 走訪 block ### 研讀紅黑樹實作改進和紅黑樹實作 #### 2-3-4 樹、紅黑樹與左傾紅黑樹紅黑樹是實踐 2-3-4 樹的一種方式，紅黑樹的「紅色節點」代表該節點與其親代節點在對應的 2-3-4 樹中屬於同一節點。這也是紅黑樹能要保證「任一根到葉子路線上的黑節點數量一致」的原因，因為 2-3-4 樹中任一根到葉子路線長度都是一樣的。然而給定 2-3-4 樹可以對應到多個紅黑樹（但我不知道為什麼這是個問題），因為 3 node 可以對照到兩種紅黑樹： ```graphviz digraph { node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]; values [label="<f0> 33 | <f1> 48 | <f2> 80 ", color=blue, fillcolor=lightblue, style=filled]; "35/50" [label="35/50", style=filled]; edge [color=blue]; "35/50":f0 -> values:f0 ; "35/50":f1 -> values:f1 ; "35/50":f2 -> values:f2 ; "35/50":f5 -> values:f5 ; } ``` 該 3 node 可以對應成以下兩種紅黑樹（`35` 為紅色子節點，代表 `35` 與其親代節點 `50` 在對應的 2-3-4 樹中屬於同一節點） ```graphviz digraph RBT { graph[ordering="out"] node [shape=circle, fixedsize=true, style=filled,width=.5] 35 [fillcolor=red] 50 -> {35 80} 35 -> {33 48} } ``` 或是 ```graphviz digraph RBT { graph[ordering="out"] node [shape=circle, fixedsize=true, style=filled,width=.5] 35 -> {33 50} 50 -> {48 80} 50 [fillcolor=red] } ``` 為此，左傾紅黑樹（[Left-leaning Red-Black Trees](https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf)）規範了 3 node 必須要 "left-leaning" ![Screenshot 2024-11-11 at 3.14.36 PM](https://hackmd.io/_uploads/HJsJJNkG1x.png) 「左傾紅黑樹」與「紅黑樹」的差異在於前者增加了「若一節點只有一個紅色子節點，則該子節點必在左側」的特性，其餘五個特性相同。只要掌握「左傾紅黑樹」能對應到唯一的「 2-3-4 樹」的特性，便可將紅黑樹操作對照到「 2-3-4 樹」操作，如此一來在進行紅黑樹操作時只會遇到以下三種可類型（如下圖 A, B and C），複雜的操作就可以變的很直觀(相較於一般紅黑樹會有2+5種)： ```graphviz digraph RBT { graph[ordering="out"] node [shape=circle, fixedsize=true, style=filled,width=.5] A -> {nil_ _nil_} B -> {x nil} x [fillcolor=red] C -> {y z} y [fillcolor=red] z [fillcolor=red] } ``` ##### 插入：原先的紅黑樹插入要判斷八種情況（兩組四種），若使用左傾紅黑樹則可以簡化成三種情況： 1. 欲插入的親代節點沒有其他子節點(`A`): 此舉相當於對 2 node 加入一個節點使其變成 3 node (`B`) ，不需額外調整 2. 欲插入的親代節點有一個子節點(`B`): 此舉相當於對 3 node 加入一個節點使其變成 4 node (`C`) ，這時要考慮以下兩種情形： - 加入的節點為三者最大，則該節點為右子節點，不需額外調整 - 加入的節點為三者最小，相當於連續兩個紅節點，需作旋轉 4. 欲插入的親代節點有兩個子節點(`C`)：此舉相當於對 4 node 加入一個節點，此時會節點兩端會變成兩個 2 node (`B`)，而中間的節點會變成兩個 2 node 的根節點，接著再將節點加入匹配的 2 node 中使其成為 3 node ，方法跟情況 1 一樣。此步驟看似複雜，但若切換到紅黑樹的視角儘僅是將顏色交換後再插入節點(如下圖所示，欲加入節點 F ) ```graphviz digraph RBT { graph[ordering="out"] node [shape=circle, fixedsize=true, style=filled,width=.5] C -> {y z} y [fillcolor=red] z [fillcolor=red] F y -> {nil nil_} z -> {_nil _nil_} } ``` ```graphviz digraph RBT { graph[ordering="out"] node [shape=circle, fixedsize=true, style=filled,width=.5] C -> {y z} C [fillcolor=red] z -> {F nil} F [fillcolor=red] y -> {_xnil nil_} } ``` 當然，以上 1, 2, 3 都是遞迴操作，確保整棵樹都能維持紅黑樹的特性 ##### 刪除： #### jemalloc >在 jemalloc 中，不使用 parent pointers，而是在進行插入或刪除時才會用 path 陣列去記錄走過的路徑，直接減少了每個節點結構體的大小，在 cacheline 固定為 64 bytes 的情況下，可以使一次能放入 cache 的節點數量增加，提升整體系統的使用效率。 path 的機制？ #### 研讀〈[Left-Leaning Red-Black Trees Considered Harmful](https://read.seas.harvard.edu/~kohler/notes/llrb.html)〉 Sedgewick’s left-leaning red-black ### jserv/rbtree TODO: 加上摘要並說明 malloc vs. alloca #### `rb_t` ： ```c typedef struct { rb_node_t *root; /**< Root node of the tree */ rb_cmp_t cmp_func; /**< Comparison function for nodes */ int max_depth; #if _RB_DISABLE_ALLOCA != 0 rb_node_t *iter_stack[_RB_MAX_TREE_DEPTH]; bool iter_left[_RB_MAX_TREE_DEPTH]; #endif } rb_t; ``` - `root` ：指向根節點的指標 - `cmp_func` ： - 堆疊：用於紀錄紅黑樹上某一段路徑上的所有節點，由兩種配置方式 - 靜態配置： ```c rb_node_t *iter_stack[_RB_MAX_TREE_DEPTH]; bool iter_left[_RB_MAX_TREE_DEPTH]; ``` 其中 `_RB_MAX_TREE_DEPTH` 會根據執行環境的架構有所差異（TODO:補算式） - 動態配置（問題：這樣算動態嗎？）：利用整數 `max_depth` 紀錄目前紅黑樹最深的路徑長，再根據此長度配置堆疊。 #### `rb_node_t` ： ```c typedef struct __rb_node { struct __rb_node *children[2]; } rb_node_t; ``` 可以注意到節點只包含了兩個指向子結點的指標，並不包含指向親代節點的指標與顏色，其大小（64位元系統）為 16 byte。 ##### color bit 節點的顏色紀錄在指向左節點的指標的 LSB 利用 `& ~1UL` 對指向左子節點的指標進行 masking (消掉 LSB) ，就可以得到真正的指標。這樣的結構可以方便嵌入使用者自訂的結構，以 box64 為例，紅黑樹節點 node 就可以定義為： ```c typedef struct rbnode { rb_node_t node; uintptr_t start, end; uint32_t data; } rbnode; ``` #### `rb_foreach_t` ```c typedef struct { rb_node_t **stack; /**< Hold the nodes encountered during traversal */ bool *is_left; /**< Track the relationship of each node to its parent */ int32_t top; /**< Keeps track of the current position in the stack */ } rb_foreach_t; ``` - `stack` 紀錄了某一段路徑上的所有節點 - `is_left` 紀錄了某一路徑上所有節點是否為其親代節點的左子節點 - `top` 紀錄當前節點 `node` 的索引值，同理 `stack[top-1]` 則為 `node` 的親代節點。注意 `top` 為 $-1$ 時代表堆疊尚未建立或初始化（記載之前的資料尚未清洗）。 TODO：說明如何找到同輩節點？配置 `rb_foreach_t` 有兩種方式： 1. 靜態配置：直接使用結構體 `rb_t` 中的兩個陣列作為紀錄路徑的堆疊 ```c stack = &(tree)->iter_stack[0]; is_left = &(tree)->iter_left[0]; ``` 2. 動態配置：利用 `alloca` 配置記憶體 ```c stack = alloca((tree)->max_depth * sizeof(rb_node_t *)); is_left = alloca((tree)->max_depth * sizeof(bool)); ``` #### rb_insert 此函式的功能是將節點 `node` 加入紅黑樹 `tree` 之中，過程包含尋找`node` 欲加入的位置和調整紅黑樹結構。在走訪紅黑樹 `tree` 之前要先建立堆疊 `stack` 來紀錄從根節點到 `node` 的路徑。建立堆疊有兩種模式： 1. fixed stack，使用 `rb_t` 結構中的堆疊（TODO:說明重複利用的情況） ```c rb_node_t **stack = &tree->iter_stack[0]; ``` 2. (問題：這不也叫 fixed stack 嗎？)，使用 `rb_t` 中的 `max_depth` ，設定成 `max_depth + 1` 是因為一次 `rb_insert` 最多加入一個節點，最大深度只能可是過去的最大深度 `max_depth` 再多一層。 ```c rb_node_t *stack = stack[tree->max_depth+1]; ``` ##### find_and_stack 此函數會利用二元搜尋樹的特性找到 `node` 或是 `node` 適合的位置（即符合二元搜尋樹的定義的位置），在尋找的過程中，走訪過的節點皆會被紀錄在堆疊 `stack` 中並記錄數量，最後回傳 `sz` 即為堆疊的深度。 ```c static int find_and_stack(rb_t *tree, rb_node_t *node, rb_node_t **stack) { int sz = 0; stack[sz++] = tree->root; while (stack[sz - 1] != node) { rb_side_t side = tree->cmp_func(node, stack[sz - 1]) ? RB_LEFT : RB_RIGHT; rb_node_t *ch = get_child(stack[sz - 1], side); if (!ch) break; stack[sz++] = ch; } return sz; } ``` 此時 `node` 還未被加入紅黑樹 `tree` 中，但透過剛才的走訪我們可以得到 `node` 未來的親代節點 `parent` （即 `stack[sz-1]`），注意 `stack[sz]` 此時還未建立，因為此時 `node` 還未加入 `tree` 中，無法透過 `get_child` 獲得。找到 insertion point 後...(補細節)便可以把 `node` 加入 `stack` 中，此時的 `stack` 就是完整的路徑，有了此路徑便可以開始調整 `tree` 的結構以符合紅黑樹的定義。 ##### fix_extra_red ```c static void fix_extra_red(rb_node_t **stack, int stacksz) { while (stacksz > 1) { const rb_node_t *node = stack[stacksz - 1]; rb_node_t *parent = stack[stacksz - 2]; /* If the parent is black, the tree is already balanced. */ if (is_black(parent)) return; rb_node_t *grandparent = stack[stacksz - 3]; rb_side_t side = get_side(grandparent, parent); rb_node_t *aunt = get_child(grandparent, (side == RB_LEFT) ? RB_RIGHT : RB_LEFT); /* Case 1: The aunt is red. Recolor and move up the tree. */ if (aunt && is_red(aunt)) { set_red(grandparent); set_black(parent); set_black(aunt); /* The grandparent node was colored red, may having a red parent. * Continue iterating to fix the tree from this point. */ stacksz -= 2; continue; } /* Case 2: The aunt is black. Perform rotations to restore balance. */ rb_side_t parent_side = get_side(parent, node); /* If the node is on the opposite side of the parent, perform a rotation * to align it with the grandparent's side. */ if (parent_side != side) rotate(stack, stacksz); /* Rotate the grandparent with the parent and swap their colors. */ rotate(stack, stacksz - 1); set_black(stack[stacksz - 3]); set_red(stack[stacksz - 2]); return; } /* If the loop exits, the node has become the root, which must be black. */ set_black(stack[0]); } ``` 接著要更新 `rb_t` 結構中的 `max_depth` ，使 `max_depth` 能記載目前最長的路徑。 ##### rotate ### rb_remove 首先我們要回顧中序走訪的定義：中序走訪（In-Order Traversal）是依序以左節點、根節點、右節點為順序走訪的方式。因此找到「相對於某一節點的最左節點」變得至關重要，因為該節點即為某一抽象單元的走訪起點（TODO:換個更好的方式表達） ![image](https://hackmd.io/_uploads/HJguKbwUkg.png) 以上圖的例子來說....(待續) ### stack_left_limb ```c static rb_node_t *stack_left_limb(rb_node_t *n, rb_foreach_t *f) { f->top++; f->stack[f->top] = n; f->is_left[f->top] = false; for (n = get_child(n, RB_LEFT); n; n = get_child(n, RB_LEFT)) { f->top++; f->stack[f->top] = n; f->is_left[f->top] = true; } return f->stack[f->top]; } ``` 此函式的功能是將節點 `n` 以及其所有左子孫加入結構 `rb_foreach_t` 之中，函式預設 `n` 是根節點或是右子節點，這個預設在（？）得到保證。當 `n` 被放入節點並記錄 `n` 與其親代的關係後，函式隨即將其左子孫們（如果存在的話）加入堆疊並回傳 `n` 的最左子孫(TODO:確認是否有其他更精確的名詞)或是 `n` 。 TODO:示意圖 #### `__rb_foreach_next` 首先先將根節點到最左節點的路徑紀錄在堆疊中，做為之後操作的主要路徑 ```c if (!tree->root) return NULL; if (f->top == -1) return stack_left_limb(tree->root, f); ``` 為了實踐紅黑樹的中序走訪，必須依據當前節點 `f->stack[f->top]` 的情況分成以下幾種處理方式： 1. 當前節點擁有右子節點 `n` : 利用 `stack_left_limb` 找出 `n` 的最右子節點並回傳 ```c rb_node_t *n = get_child(f->stack[f->top], RB_RIGHT); if (n) return stack_left_limb(n, f); ``` 2. 當前節點為左子節點且沒有右子節點（子樹的極值？）此時代表該節點已經被回傳過了（即該節點為某一路徑的終點，已被回傳過了），因此需要 pop `stack` 並回傳該節點的親代節點 `f->stack[--f->top]`。 (此處) ```c if (f->is_left[f->top]) return f->stack[--f->top]; ``` ```c while ((f->top > 0) && (f->is_left[f->top] == false)) f->top--; f->top--; return (f->top >= 0) ? f->stack[f->top] : NULL; ``` ### 研讀〈Rank-Balanced Trees〉論文該論文第一部分先介紹了三種自平衡的搜尋樹 (Red black trees、AVL tree and B-tree) 接著介紹一種抽象化的方式 Ranks: 此方式將節點中用來維持平衡的資訊皆抽象化為 `rank` ，而不同都自平衡樹會利用不同的 rank rule 來維持樹的平衡。以下是幾個跟 `rank` 有關的操作： - r(x) : Returns rank of a node - parent(x) : Returns parent of a node - rank difference of x : r(parent(x)) - r(x) - x is an i-child : its rank difference is i - x is an (i, j)-node : its left and right children have i and j rank differences respectively 接著示範在利用 rank 將不同自平衡樹抽象化後的結果： 1. AVL tree : Every node is (1, 1) or (1, 2). In the case of the AVL tree, rank represents height. (1, 2)-node represents a tree where one of its subtrees has a bigger height. In this case, we are talking about the nodes with balance factor −1 or 1 (respectively being signed with a − or a +). >問題：此處我看不懂，如果説 rank 是指節點高度的話那親代節點與子代節點的 rank difference 必為 1 ，換句話說，所以有的節點都會是 (1,1) ，如果無法搞清楚該論文的抽象化方法 rank 將無法看懂後面的分析 2. Red-Black Rule: All rank differences are 0 or 1, and no parent of a 0-child is a 0-child. #### Week AVL tree #### 評比程式 ### 修改 box64 的紅黑樹實作 >參考 [Improve red-black tree implementation in map](https://github.com/sysprog21/rv32emu/issues/29) 整合現有實作 [jserv/rbtree](https://github.com/jserv/rbtree) ，該實作有以下特性： - 使用「侵入」技法 (intrusive `rb_node_t` structure) -> 少了一層的間接操作，並有更好的 cache locality - 移除親代指標，只有在「加入」及「刪除」時會紀錄在紅黑樹結構的 stack 中 -> 減少節點大小 - 使用 Indirect pointers -> 減少分支數量 - 使用指向右子節點的指標的 LSB 來紀錄節點顏色 -> 減少 node 大小 TODO:畫出 box64 的紅黑樹函式架構圖，並對對映到 jserv/rbtree 的函式，避免瞎忙 TODO :實作細節 > 必須善用「侵入式」的特性，無腦瞎改就無法獲得本應獲得的效能 1. 比較函式: ```c bool compare(const rb_node_t *a, const rb_node_t *b){ rbnode* A = container_of(a, rbnode, node); rbnode* B = container_of(b, rbnode, node); if(A->start < B->start) return true; return false; } ``` 2. 紅黑樹節點外的 container 結構: ```c typedef struct rbnode { rb_node_t node; uintptr_t start, end; uint32_t data; } rbnode; ``` 3. Search 4. Insert 5. Delete TODO: `add_range_next_to` 的功能是將代表一個記憶體區段的 `node` 加入紅黑樹成為 `prev` 的子節點。而`add_range` 的功能是找到與欲加入之記憶體區段(`node`)最接近的節點 `prev` 之後呼叫 `add_range_next_to` ，因此上述功能可以完全由 `rb_insert` 來代替（`add_range` 前半段對應到 `find_and_stack` ）但 `add_range_next_to` 可以由 `rb_insert` 來替代嗎？要釐清 `find_and_stack` 找到的 parent 是否用相等於 `add_range_next_to` 的參數 `prev` TODO: 務必從 rb_set 開始改，先改枝微末節的小程式會陷入死胡同 TODO: 尋找前驅和後繼節點的時候需要用到親代節點的指標，要想辦法搞定 --- ### TODO 設定改進紅黑樹實作的目標： 1. 加速插入/刪除/查詢 (符合 box64 使用情境) 2. 更低的記憶體開銷 - [x] TODO: 在 box64 程式碼增加紅黑樹新增/刪除/查詢的動作追蹤 (用 printf 或 [log.c](https://github.com/rxi/log.c))，以利後續效能評估。應建立圖表，使用固定的 x86-64 效能評比程式。注意：選定的[效能評比程式](https://hackmd.io/@devaraja/box64-bench)規模過小，不足以反映 box64 實際的應用場景，待程式碼充分改進後，可參照上述 git log， - [ ] 利用 [box64 + Win64](https://github.com/ptitSeb/box64/blob/main/docs/X64WINE.md) 來執行經典 Windows 內建程式，以彰顯記憶體管理的開銷。 - [ ] TODO: 現行 [rbtree.c](https://github.com/ptitSeb/box64/blob/main/src/tools/rbtree.c) 的測試情境過於單純，不足以反映紅黑樹特性和 box64 使用案例，可整理之前的動作追蹤，將紅黑樹相關函式呼叫時的參數予以重現，作為測試案例的改進。如此一來，後續的程式碼改進就有一致的測試基準。 - [ ] TODO: `rb_get_end` 是 box64 特有的實作，且用於 `custommem.c` 作為記憶體管理機制，其實作為: ```c int rb_get_end(rbtree_t* tree, uintptr_t addr, uint32_t* val, uintptr_t* end) { rbnode *node = tree->root, *next = NULL; while (node) { if ((node->start <= addr) && (node->end > addr)) { *val = node->data; *end = node->end; return 1; } if (node->end <= addr) { node = node->right; } else { next = node; node = node->left; } } *val = 0; if (next) { *end = next->start; } else { *end = (uintptr_t)-1; } return 0; } ``` 倘若最後的節點不常更動，可比照 Linux 核心的 rbtree，快取最左邊的節點的作法 (參見 Linux CPU scheduler 書籍第三章)，讓原本 $O(\log{n})$ 的時間複雜度降到 $O(1)$ - [ ] TODO: 研讀[紅黑樹實作改進](https://hackmd.io/@sysprog/ryDD1HgS3)和[紅黑樹實作](https://hackmd.io/@sysprog/HkZcqus8R)並留意 jemalloc (rv32emu 的紅黑樹改寫自 jemalloc 的 rb) vs. Linux 的實作。注意：jemalloc 的 rb 可能具備較低的記憶體開銷。 - [ ] TODO: 學習 [Improve red-black tree implementation in map](https://github.com/sysprog21/rv32emu/issues/29) 和 [rbtree_bench](https://github.com/EagleTw/rbtree_bench) 的手法，對 box64 的紅黑樹實作予以分析，可將後者獨立出來並包裝為一致的介面 - [ ] TODO: 查看 [alloca](https://man7.org/linux/man-pages/man3/alloca.3.html) - [ ] TODO: 釐清 box64 中 `rb_` 系列函式的應用場景，整理並修改程式碼來觀察，倘若有疑慮，建立對應的 GitHub issue，請開發者澄清，務必先列出你的認知和推論，接著才提問 - [ ] TODO: 研讀〈[Rank-Balanced Trees](https://is.muni.cz/th/elt9h/thesis.pdf)〉論文 (2022 年) - [ ] TODO: 針對 [jserv/rbtree](https://github.com/jserv/rbtree) 程式碼，提出改進現有效能評比程式的規劃，附上你預計利用 Python 的 Matplotlib 如何製作對應紅黑樹操作的視覺化 --- ## 參考文獻 * [Faster, Simpler Red-Black Trees](https://www.khoury.northeastern.edu/~camoy/pub/red-black-tree.pdf) * [A STL compliant map and set that uses a red-black tree under the hood](https://github.com/drogalis/Flat-Map-RB-Tree)