---
tags: linux kernel
---
# 2023q1 Homework3 (quiz3)
contributed by < `hankTaro` >
## 測驗一
:::success
延伸問題:
1. 指出 `treesort.c` 程式碼的缺失並改進
2. 利用 Linux 核心的 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) 的效率
3. 研讀 Linux 核心的 [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 程式碼，比較給定的 `treesort.c` 實作手法，指出後者的改進空間並予以實作
:::
<!-- :::warning
文字訊息不要用圖片展現，尊重視覺障礙者閱讀的權益。
:notes: jserv
::: -->
此紅黑樹節點架構將顏色與親代節點的資料存在同個空間，藉由透過 `__attribute__((aligned(sizeof(long))))` 對齊到 `sizeof(long)`，這樣指標最低 3 個位元是沒有使用到的，便可將此位置用於儲存顏色(但是儲存顏色只需要用到 1 bit)
> long 所需的位元數為 4，所以對齊後最小的三位元會固定不動
> e.g. `00001000` -> `00010000` -> `00011000` -> `00100000` -> `00101000`
> [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
:::info
這裡對將變數名取為 `color` 頗為不滿，若將其命名為 `parent_color` 會更容易閱讀理解，並避免混淆
:::
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
並且定義巨集以便取出親代節點的位置與節點顏色
```c
#define rb_parent(r) ((node_t *) (r)->color & ~7)
#define rb_color(r) ((color_t) (r)->color & 1)
#define rb_set_parent(r, p) \
do { \
(r)->color = rb_color(r) | (uintptr_t) (p); \
} while (0)
#define rb_set_red(r) \
do { \
(r)->color & ~7; \
} while (0)
#define rb_set_black(r) \
do { \
(r)->color | 1; \
} while (0)
```
```c
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = &(*list)->next;
}
// 找出 tree 中最小的值(也就是不停的往左側尋訪)
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = &(*list)->next;
}
*list = NULL;
*record = first;
free(map);
}
```
`int res = obj->comparator(&node->value, &cur->value);` 中的 res ，是 `obj->comparator` (一個比較函數，由 `cmap_new`， assign 進去的)，當 `&node->value` 大於 `&cur->value` 時回傳 1，反之回傳 -1 ，相等回傳 0 ，隨後便利用 res 辨別相對大小，將此 node 放在 NIL 的位置(leaf)，
```c
static bool cmap_insert(cmap_t obj, node_t *node, void *value)
{
cmap_create_node(node);
obj->size++;
if (!obj->head) {
/* Just insert the node in as the new head. */
obj->head = node;
rb_set_black(obj->head);
/* Calibrate the tree to properly assign pointers. */
cmap_calibrate(obj);
return true;
}
/* Traverse the tree until we hit the end or find a side that is NULL */
for (node_t *cur = obj->head;;) {
int res = obj->comparator(&node->value, &cur->value);
if (!res) /* If the key matches something else, don't insert */
assert(0 && "not support repetitive value");
if (res < 0) { //若 node 比現在這個點小，則檢查 cur 左側有沒有節點，若沒有就將 node 放入 cur 的左側，反之則將 cur 變為其左側節點重複判斷
if (!cur->left) {
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur->cur->left;
} else {
if (!cur->right) {
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur->cur->right;
}
}
cmap_calibrate(obj);
return true;
}
```
cmap_new 的必要性，因為只有在 tree_sort 中呼叫過一次，內容也只是將固定傳入數值 assign 進結構中
### 引入 list.h
將 `struct __node` 中的 `struct __node *next;` 用 `struct list_head list;` 替換
```c
typedef struct __node {
uintptr_t color;
struct __node* left, * right;
struct list_head list;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
將 `main` 中的 `list_make_node` 改為使用 `list_add`
```c
int main(int argc, char** argv)
{
size_t count = 100;
int* test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
/*node_t* list = NULL;*/
LIST_HEAD(list);
while (count--) {
list_make_node(list, test_arr[count]);
}
tree_sort(&list);
assert(list_is_ordered(list));
list_free(&list);
free(test_arr);
return 0;
}
```
```c
static inline void list_make_node(struct list_head* head, int n)
{
node_t* node = malloc(sizeof(node_t));
node->value = n;
list_add(node->list, head);
}
```
使用 `list_for_each_entry` 與 `list_move_tail` 省去使用 `list = &(*list)->next;`，並且更改 `cmap_next` 與 `cmap_first` 資料回傳型態
```c
void tree_sort(struct list_head **list)
{
struct list_head **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
node_t *it;
list_for_each_entry(it, *list, list) {
cmap_insert(map, it, NULL);
}
struct list_head* node = cmap_first(map);
for (; node; node = cmap_next(node)) {
list_move_tail(node, *list);
}
free(map);
}
```
---
## 測驗二
:::spoiler 答案
`IIII = node->parent_balance & ~7`
`JJJJ = node->parent_balance & 3`
`KKKK = node->parent_balance & 3`
`LLLL = node->parent_balance & ~7`
`MMMM = avl_rotate_right`
`NNNN = avl_rotate_leftright`
:::
### 程式碼講解
AVL tree 這裡也利用 `AVL_NODE_ALIGNED` 做 data alignment ，將 balance 值存於 adress 的末兩位中，剛好 balance 只有三種可能，平衡、左傾或右傾，故可以使用 2 bits 空間進行保存
> 要注意的是，這裡左傾與右傾是指，兩邊最大高度差為 1，因為當兩邊高度差為 2 時，就會進行平衡，並且求出新的 balance ，所以這邊 [Balance Factor](https://josephjsf2.github.io/data/structure/and/algorithm/2019/06/22/avl-tree.html) 只會有 -1, 0, 1 的狀況
```c
// 用於對應是平衡、左傾還是右傾(Balance Factor 為 0, -1, 1)
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
```
```c
#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))
...
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
```
呼叫 `avl_insert` 的情況下，是已經找到此 node 在樹中的位置，並且 parent 已將此節點設為他的 child，故呼叫 `avl_link_node` 建立出一個 `left` `right` 都是 NULL 的新節點，並且是平衡的，再將 parent 的位置存入
```c
static inline void avl_link_node(struct avl_node *node,
struct avl_node *parent,
struct avl_node **avl_link)
{
avl_set_parent_balance(node, parent, AVL_NEUTRAL);
node->left = NULL;
node->right = NULL;
*avl_link = node;
}
static inline void avl_insert(struct avl_node *node,
struct avl_node *parent,
struct avl_node **avl_link,
struct avl_root *root)
{
avl_link_node(node, parent, avl_link);
avl_insert_balance(node, root);
}
```
當 node 插入後，便開始沿著 parent 的路徑依序平衡，可以將情況分為一下幾種:
* case 1:
* node 平衡，在 parent 的左側，parent 右傾
* node 平衡，在 parent 的右側，parent 左傾
* case 2:
* node 平衡，parent 平衡
* case 3:
* node 不平衡
在 case 1 中只需要將 parent 設為平衡
在 case 2 中只需要依據 node 是插入在左側還是右側，將 parent 設為右傾或左傾
case 3 需要進行旋轉以平衡兩側高度，並且要同時對 node 與 parent 做判斷，可以分為 4 種類型
* LL 型:
* 狀況: parent 與 node 均為左傾
* 處理方法: 對 parent 進行右旋
* LR 型:
* 狀況: parent 左傾，node 右傾
* 處理方法: node 進行左旋後，對 parent 進行右旋
* RR 型:
* 狀況: parent 與 node 均為右傾
* 處理方法: parent 進行左旋
* RL 型:
* 狀況: parent 右傾，node 左傾
* 處理方法: node 進行右旋後，對 parent 進行左旋
:::warning
要注意插入新節點還沒平衡前，新節點的 parent 的 balance 尚未更新，並且新節點必定平衡，所以第一次平衡不可能會進行旋轉
新節點的 parent 只受新節點在其左還右，以改變其平衡狀態
node 為平衡或左傾時，都算做 L
:::
LL 型:
<!-- 上圖中 B 點是左傾，故右旋後會平衡
 -->
LR 型:
RR 型:
RL 型:
```c
void avl_insert_balance(struct avl_node *node, struct avl_root *root)
{
struct avl_node *parent;
/* go tree upwards and fix the nodes on the way */
while ((parent = avl_parent(node))) {
if (avl_is_right_child(node)) {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* compensate double right balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_RIGHT:
case AVL_NEUTRAL:
avl_rotate_left(node, parent, root);
break;
case AVL_LEFT:
avl_rotate_rightleft(node, parent, root);
break;
}
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as right and continue upwards */
avl_set_balance(parent, AVL_RIGHT);
break;
case AVL_LEFT:
/* new right child + left leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
}
} else {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* new left child + right leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as left and continue upwards */
avl_set_balance(parent, AVL_LEFT);
break;
case AVL_LEFT:
/* compensate double left balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_LEFT:
case AVL_NEUTRAL:
avl_rotate_right(node, parent, root);
break;
case AVL_RIGHT:
avl_rotate_leftright(node, parent, root);
break;
}
parent = NULL;
break;
}
}
if (!parent)
break;
node = parent;
}
}
```
而進入旋轉後，需要根據親代節點的平衡狀況去設置調整後的平衡狀況
依序分別為:
* LL 型: 右旋
* LR 型: 先左旋再右旋
* RR 型: 左旋
* RL 型: 先右旋再左旋
```c
static struct avl_node *avl_rotate_right(struct avl_node *node,
struct avl_node *parent,
struct avl_root *root)
{
enum avl_node_balance balance_parent, balance_node;
struct avl_node *tmp;
switch (avl_balance(node)) {
case AVL_NEUTRAL:
balance_parent = AVL_LEFT;
balance_node = AVL_RIGHT;
break;
default:
/* AVL_RIGHT is not allowed */
case AVL_LEFT:
balance_parent = AVL_NEUTRAL;
balance_node = AVL_NEUTRAL;
break;
}
/* rotate right */
tmp = parent->left;
parent->left = tmp->right;
tmp->right = parent;
avl_rotate_switch_parents(tmp, parent, parent->left, root, balance_node,
balance_parent);
return tmp;
}
```
此方法對應的是 LL 型，由於此情況 node 不可能右傾，因為右傾則會成為 LR 型， 故只需要考慮 node 為平衡以及左旋的狀況，當 node 為平衡時，代表其左右側都不為 NIL(因為第一次平衡不可能會進行旋轉，故發生選轉的節點必定有子節點)，所以其右側節點會成為其親節點的左側節點
node 為紅色節點
```graphviz
graph graphname {
label="NODE 為平衡時"
n01 [label="A"] ;
n01 -- n02 ;
n01 -- n03 ;
n02 [label="B",color="red"] ;
n02 -- n04 ;
n02 -- n05 ;
n03 [label="C"] ;
n04 [label="D"] ;
n05 [label="E"] ;
}
```
```graphviz
graph graphname {
label="旋轉後"
n01 [label="B",color="red"] ;
n01 -- n02 ;
n01 -- n03 ;
n02 [label="D"] ;
n03 -- n05 ;
n03 -- n04 ;
n03 [label="A"] ;
n04 [label="C"] ;
n05 [label="E"] ;
}
```
故 node 在旋轉後會右傾，而 parent 會左傾，故更新平衡狀態，隨後進行節點的移動與連結
而 RL/LR 型則是先對 node 做相對應的旋轉，使其變為 RR 或 LL 型，再用同樣的方式對 parent 旋轉，並更新平衡狀態，概念相同這裡就不多做贅述
### Linux 核心 rb_tree 替代 AVL_tree 之因素
目前Linux 核心中的 AVL tree ，逐漸被紅黑樹替代，AVL tree 相較於 RBT 的劣勢在於，當節點數量較大時，可能需要一直旋轉直到 root ，在大多數情況下，RBT 的效率會比 AVL tree 好
在考慮是否要用 RBT 取代 AVL tree 以前，必須先行了解 linux 核心的同步機制之一 [RCU](https://hackmd.io/@sysprog/linux-rcu)，以及 linux 的鎖定機制 [seqlock(short for sequence lock)](https://en.wikipedia.org/wiki/Seqlock)，因為要將 AVL tree 用 RBT 取待，需要確保 RBT 支援 RCU ，否則在多執行上效率不彰
在使用 RCU 的狀況下，RBT 可使用較少的函式達成，同時使用較少的變數
### (TODO)利用 rb_tree 替代 AVL_tree 之實作
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並比較用紅黑樹實作的 [priority queue](https://en.wikipedia.org/wiki/Priority_queue)，應提供完整的測試程式和效能分析
2. Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀
> 見 commit [b145425](https://github.com/torvalds/linux/commit/b145425f269a17ed344d737f746b844dfac60c82)
3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 `rbtree.h`，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會
:::
---
## 測驗三
```c
uint64_t log2_64(uint64_t v)
{
unsigned r;
uint64_t t, tt, ttt;
ttt = v >> 32;
if (ttt) {
tt = ttt >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 56 + log_table_256[t];
} else {
r = 48 + log_table_256[tt];
}
} else {
t = ttt >> 8;
if (t) {
r = 40 + log_table_256[t];
} else {
r = 32 + log_table_256[ttt];
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 24 + log_table_256[t];
} else {
r = 16 + log_table_256[tt];
}
} else {
t = v >> 8;
if (t) {
r = 8 + log_table_256[t];
} else {
r = 0 + log_table_256[v];
}
}
}
return r;
}
```
```c
unsigned int bucket_number(uint64_t x)
{
uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */
unsigned char leq = ((x & mask111) < N_BUCKETS);
/* leq (less or equal) is 0 or 1. */
return (leq * (x & mask111)) +
((1 - leq) * ((x >> (N_BITS + 1)) & mask011));
/* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
* '... & mask011' guarantees that the result is less or equal N_BUCKETS.
*/
}
```
用 `__builtin_clzl` 求出左側0數量就可以求出小於 x 的 $n=log_2x$
最大位元 - 左側0數量 - 1 = 右側到最大 1 之間的 0 數量 = n
:::success
延伸問題:
1. 解釋 [Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的運作原理，搭配在 [Linux 核心原始程式碼](https://github.com/torvalds/linux)中，用 `git log` 和 `grep` 找出 LFSR 的應用案例
2. 解釋上述程式碼運作的原理
3. 在 Linux 核心原始程式碼中找到 $\log_2(x)$的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $\log_2(x)$ 的應用案例並解說。
4. `lab0-c` 提供類似的實作 [log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)，解釋其原理並嘗試改進其效能
:::
---
## 測驗四
### 運作原理
此程式欲求出 $\log_2(x)$ 並向上取整
```c=1
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x >> 1) + 1;
}
```
取 $\log_2(x)$ 的改念就是看最高有效位元的位置，因為在二進位中，位元的位置為冪運算的上標，所以只要知道 x 最左側的 1 後有幾個位元，就可以求出$\log_2(x)$
在第 5 行中，將 `x--` 是為了將 $2^n$ 型態的數值最大值降低一位元，確保無條件進位時的答案正確
6~15 行都是在求最高有效位的位置，最後在 `return (r | shift | x >> 1) + 1;` 無條件向上取整
### 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
由於 $\log_2(x)$ 需要求出最高有效位元右側有幾個位元，便可使用 `__builtin_clz` 函式，求出最高有效位元左側有幾個 `0` ，在用最大位元數減去，便可得到其值共佔多少位元，由於要向上取整，故在運算前 `x - 1`，這樣 $2_n$ 型態算出的值會剛好是其減 1 前右側位元數，而不是$2_n$ 型態算出的值會是無條件進位後的位元數
另外輸入有機會為 0，故使用 `assert` 檢查，並達成 branchless
```c
int ceil_log2(uint32_t x)
{
assert(x != 0 && "log2(0) is undefined !\n");
return 32 - __builtin_clz(x - 1);
}
```
### (TODO)Linux 核心中 ceil 和 log2 的組合案例
:::success
TODO:
1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)
:::
Sign in with Wallet
Connect another wallet