---
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` 會更容易閱讀理解，並避免混淆
:::

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

並且定義巨集以便取出親代節點的位置與節點顏色

#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)

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)，

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;` 替換

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`

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;
}

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` 資料回傳型態

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 的狀況

// 用於對應是平衡、左傾還是右傾(Balance Factor 為 0, -1, 1)
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };

#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 的位置存入

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 型:

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 型: 先右旋再左旋

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 為紅色節點

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"] ;
   
}

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 核心的機會
:::

---

## 測驗三

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;
}

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)$ 並向上取整

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

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 核心排程器就有)
:::