--- tags: Linux Kernel --- # Linux 紅黑樹探討 contributed by < [steven1lung](https://github.com/steven1lung) > [Documentation](https://www.kernel.org/doc/Documentation/rbtree.txt) 在 Linux 核心中，有許多地方都有使用到紅黑樹。但是我們可能會想說為什麼要使用紅黑樹，而不是其他的二元樹像是：AVL Tree 之類。雖然二者平均時間複雜度都是 $O(\log n)$，但因行為和特性的落差，有不同的應用場景。 以下簡述 AVL Tree 和紅黑樹的差異: * 平衡 - AVL Tree 比紅黑樹還要平衡（左右子樹的高度不能差超過 2），但是會在平衡自己的時候花費比紅黑樹多的時間。 - 如果考慮到要更快速地去 search 一個節點，那 AVL tree 會比較適合。 - 紅黑樹的優點在於雖然沒有到完全平衡（最長路徑 $\le$ 2 倍最短路徑），但是紅黑樹會在平衡自己時達到 $O(1)$ （最多 3 個 rotation）的複雜度。 * 空間 - AVL 的節點會需要宣告 factor (height) 的變數給每個節點來作為平衡的參考，而紅黑樹只需要 1 位元的變數來區分顏色（紅、黑）。 > 下方介紹 Linux 如何運用 alignment 將這個額外的 1 位元也省略 總而言之我們可以分兩種場景來選擇要使用的樹： 1. 插入跟刪除較多：紅黑樹 2. 查詢節點較多：AVL Tree 在 Linux Kernel 中有許多地方都有使用到紅黑樹，例如：`hr_timer` 使用紅黑樹來記錄 timer requests、`ext3` 檔案系統使用紅黑樹來追蹤目錄、VMA（Virtual Memory Area）也是用紅黑樹來紀錄。 而在 CFS 中，需要頻繁地插入跟刪除節點（任務），所以我覺得這是當初開發者會選擇使用紅黑樹的考量。 ## Linux 紅黑樹介紹 Linux 紅黑數跟一般紅黑樹不一樣得地方在有對速度進行優化，少了一層的 indirection 並且有更好的 cache locality。並且使用的方法是將 `rb_node` 嵌入要使用的結構中，透過 `container_of` 存取 data，而不是在 `rb_node` 裡宣告 data 指標。 **Linux 紅黑樹需要使用者去定義 tree search 跟 insert 函式。** ### 紅黑樹節點 ```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` 跟 `list_head` 之後，發現 Linux 風格的資料結構都不會包含 data，而是會將 `rb_node` 或是 `list_head` 這些資料結構包在一個更大的結構體裡面。 一個紅黑樹節點包含：親代節點、左子節點、右子節點、顏色。而在 Linux 宣告的程式碼中，很巧妙地將親代節點跟顏色一起宣告，使用 `unsigned long __rb_parent_color` 將指向親代節點的指標跟自身的顏色合併。 透過 `__attribute__((aligned(sizeof(long))))` 讓編譯器知道 `struct rb_node` 會對齊 `sizeof(long)`，這樣就會讓指標最低 2 個位元是沒有使用到的，就可以把顏色的資料放進去其中一個位元中。 舉例來說，一個節點指標如果指向 `0xF724315C` ，這個位址轉成二進制會變成 `...1100`，最低 2 個位元會是 `0`，Linux 核心開發者利用這特性，將其中一個沒用到的位元拿來標注紅和黑這二種顏色。 ### container_of Linux Kernel 風格資料結構都會用一個大的 `struct` 包住我們使用的資料結構（`list_head`、`rb_node`），再透過巨集 `container_of` 從節點去存取外面的 container（也就是包住節點的結構體）。 ```c /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); }) ``` ```c #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) ``` `container_of` 的實作就是先將位址 `0` 轉成結構體指標，再取得 member（節點）的位址。因為是從 `0` 開始，所以就會得出這個 member 在結構體裡的偏移量。最後再將原本 member 記憶體位址扣掉這個偏移量，就可以得到 container struct 的位址了！ #### `container_of` or `rb_entry` 關於什麼時候要使用 `container_of` 還是 `rb_entry`（或是其他的 `XXXX_entry`，依照你正在使用的資料結構），作者的說法是當你是要存取節點的 container structure 時，會使用 `container_of`。如果要存取節點 container structure 裡的 member，就會使用 `XXXX_entry`。雖然 `XXXX_entry` 是一個巨集，且定義跟 `container_of` 一樣，透過這樣來區分是要存取大的 container 還是裡頭的 member 我覺得對其他人閱讀你的程式碼時會更好被理解、或是自己在看時更容易懂當初的寫法，是一個小但是有幫助的技巧。 ### rb_link_node 我們先看一個最常被使用到的函式： ```c static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; *rb_link = node; } ``` 這個函式就是把 `node` 的親代節點設為 `parent`，並且將 `rb_link` 指向 `node`。放入 `parent` 的左或是右子樹則是依照 `rb_link`。 ### rb_insert_color ```c void rb_insert_color(struct rb_node *node, struct rb_root *root) { __rb_insert(node, root, dummy_rotate); } ``` `__rb_insert` 可以到 [lib/rbtree.c](https://elixir.bootlin.com/linux/v5.10/source/lib/rbtree.c#L85) 看，程式碼太長就不放上來了。`__rb_insert` 做的事情就是插入節點並且進行平衡（rotate）。 ### 親代節點 當要存取親代節點時，可以透過巨集來存取： ```c #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) ``` 這個巨集會捨棄最右邊的兩個位元，並且將結果轉成節點指標，就可以得到親代節點的位址了。 ### 顏色 ```c= #define RB_RED 0 #define RB_BLACK 1 #define __rb_color(pc) ((pc) & 1) #define __rb_is_black(pc) __rb_color(pc) #define __rb_is_red(pc) (!__rb_color(pc)) #define rb_color(rb) __rb_color((rb)->__rb_parent_color) #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) ``` 在 `rbtree_augmented` 中定義了紅色為 0，黑色為 1。由此可知，如果一個節點是紅色的，那就可以直接存取 `__rb_parent_color`，但還是透過巨集方式統一比較好。 第七行的 `rb_color(rb)` 會存取這個節點的親代節點 `__rb_parent_color` 的顏色，因為知道黑色是 1，所以透過 `(pc) & 1` 就可以知道顏色了。 我們先看設定親代節點所使用的函式： ```c static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; } ``` 這個函式所做的事情就是將 `p` 設定為 `rb` 的親代節點，`rb_color(rb)` 是 `p` 的顏色跟 `p` 的位址去做 `|` 就一起設定好親代節點的位址跟顏色了。 也有可以針對親代節點去設定顏色的函式： ```c static inline void rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color) { rb->__rb_parent_color = (unsigned long)p | color; } ``` ## 簡單的紅黑樹例子 ### 決定架構 首先要定義好紅黑樹節點外的 container 結構： ```c struct mytype { struct rb_node node; char *keystring; }; ``` 我們就可以透過 `container_of(ptr, type, member)` 從 `rb_node` 存取 `struct mytype`。 ### Search 實作 接著就需要定義 search 的函式，想法也很直覺：比對現在節點的 `keystring` 如果小於就往左子節點找，大於就往右子節點找。範例如下： ```c struct mytype *my_search(struct rb_root *root, char *string) { struct rb_node *node = root->rb_node; while (node) { struct mytype *data = container_of(node, struct mytype, node); int result; result = strcmp(string, data->keystring); if (result < 0) node = node->rb_left; else if (result > 0) node = node->rb_right; else return data; } return NULL; } ``` ### Insert 實作 插入的做法就需要先使用 `search` 找到要插入的位置，新增節點，再進行平衡跟重新著色。 ```c= int my_insert(struct rb_root *root, struct mytype *data) { struct rb_node **new = &(root->rb_node), *parent = NULL; /* Figure out where to put new node */ while (*new) { struct mytype *this = container_of(*new, struct mytype, node); int result = strcmp(data->keystring, this->keystring); parent = *new; if (result < 0) new = &((*new)->rb_left); else if (result > 0) new = &((*new)->rb_right); else return FALSE; } /* Add new node and rebalance tree. */ rb_link_node(&data->node, parent, new); rb_insert_color(&data->node, root); return TRUE; } ``` 第 6 到 17 行是找出要插入的位置，作法是用一個指向**節點位址**的指標（指標的指標）來儲存新增的節點要在的位址。 第 20 行就是將找到的 `*new` 位址插入一個新的節點，將 `*new` 位址放入節點並連接 `parent`。 > 從 11 或是 14 可以知道 `new` 是左、右子節點指標的指標，可以透過 `*new` 存取左、右子節點 ### 迭代紅黑樹里的節點 ```c struct rb_node *rb_first(struct rb_root *tree); struct rb_node *rb_last(struct rb_root *tree); struct rb_node *rb_next(struct rb_node *node); struct rb_node *rb_prev(struct rb_node *node); ``` 要迭代過每個節點的方式是透過先呼叫 `rb_first` 或是 `rb_last`，就會回傳一個紅黑樹節點的指標。之後再用這個指標去呼叫 `rb_next` 或是 `rb_prev` 就可以存取下一個或是上一個節點了。 > 回傳 NULL 就代表沒有下一個了 將所有節點的 `keystring` 輸出的範例（由小到大）： ```c struct rb_node *node; for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); ``` ## Source code [linux/rbtree.h](https://elixir.bootlin.com/linux/v5.10/source/include/linux/rbtree.h) [linux/rbtree_augmented.h](https://elixir.bootlin.com/linux/v5.10/source/include/linux/rbtree_augmented.h#L146) [lib/rbtree.c](https://elixir.bootlin.com/linux/v5.10/source/lib/rbtree.c)
Last changed by  
 
Steven Lung
1751

Read more

Git 基礎教學

contributed by <steven1lung> and <Niomoo> Git 是所有開發者、工程師必定要學會如何使用的工具，今天就打算講解一下我們為什麼會需要版本控制工具，以及要如何去初步使用它。 ![](https://i.imgur.com/PGzKhpN.jpg =500x) 課程投影片請點我。 介紹 Git 是由 Linux Kernel 的開發者 Linus Torvalds 在開發 kernel 時，因為需要一個版本控制工具而發明的。

11/18/2022
提交第一份 Patch 到 Linux Kernel

contributed by < steven1lung > 我自己的心得 在看老師的書 Demystifying the Linux CPU Scheduler 的時候，突然好奇說每一個任務的 loading 是如何運算的，畢竟排程器上的任務如此多，計算出 load 然後依據每個 CPU 的狀態去做 task migration 應該是很重要的課題。所以我就跑去 pelt.c 看了一下實際的運算是如何做到的。 pelt 全名是 Per Entity Load Tracking 在看程式碼的時候，發現有個地方的中括號打反了變成 [1002..1024[，我就想說試試看發人生第一個 patch。 結果自己在摸索如何發 patch 花了好多時間...，轉眼間就早上了。所以就記錄了一下自己發 patch 的過程來紀念逝去的時間。雖然這個 patch 最後是我誤會中括號的用法，所以並沒有被採納，但跟這些厲害的人交流讓人有點興奮><

9/29/2022
2022q1 Homework6 (ktcp)

contributed by < steven1lung > :checkered_flag: 自我檢查清單 [x] 參照 Linux 核心模組掛載機制，解釋 $ sudo insmod khttpd.ko port=1999 這命令是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？ [ ] 參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？ [ ] htstress.c 用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？ [x] 給定的 kecho 已使用 CMWQ，請陳述其優勢和用法 [x] 核心文件 Concurrency Managed Workqueue (cmwq) 提到 "The original create_*workqueue() functions are deprecated and scheduled for removal"，請參閱 Linux 核心的 git log (不要用 Google 搜尋!)，揣摩 Linux 核心開發者的考量 [ ] 解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用

6/17/2022
在乙太鍊上實作 NFT 鑄造網站

contributed by < steven1lung > 會使用到的技術 Polygon Next.js Tailwind ( CSS 的套件 ) Solidity Hardhat Ether.js

5/12/2022
Read more from Steven Lung
Published on HackMD