2023q1 Homework3 (quiz3)

contributed by < hankTaro >

測驗一

延伸問題:

指出 treesort.c 程式碼的缺失並改進
利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率
研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作

此紅黑樹節點架構將顏色與親代節點的資料存在同個空間，藉由透過 __attribute__((aligned(sizeof(long)))) 對齊到 sizeof(long)，這樣指標最低 3 個位元是沒有使用到的，便可將此位置用於儲存顏色(但是儲存顏色只需要用到 1 bit)

long 所需的位元數為 4，所以對齊後最小的三位元會固定不動
e.g. 00001000 -> 00010000 -> 00011000 -> 00100000 -> 00101000
你所不知道的 C 語言：記憶體管理、對齊及硬體特性

這裡對將變數名取為 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);
}

測驗二

答案

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 只會有 -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 進行左旋

要注意插入新節點還沒平衡前，新節點的 parent 的 balance 尚未更新，並且新節點必定平衡，所以第一次平衡不可能會進行旋轉

新節點的 parent 只受新節點在其左還右，以改變其平衡狀態

node 為平衡或左傾時，都算做 L

LL 型:

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

故 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，以及 linux 的鎖定機制 seqlock(short for sequence lock)，因為要將 AVL tree 用 RBT 取待，需要確保 RBT 支援 RCU ，否則在多執行上效率不彰

在使用 RCU 的狀況下，RBT 可使用較少的函式達成，同時使用較少的變數

(TODO)利用 rb_tree 替代 AVL_tree 之實作

延伸問題:

解釋上述程式碼運作原理，並比較用紅黑樹實作的 priority queue，應提供完整的測試程式和效能分析
Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀

見 commit b145425
研讀 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 = l o g_{2} x

最大位元 - 左側0數量 - 1 = 右側到最大 1 之間的 0 數量 = n

延伸問題:

解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例
解釋上述程式碼運作的原理
在 Linux 核心原始程式碼中找到
$\log_{2} (x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數
$\log_{2} (x)$ 的應用案例並解說。
lab0-c 提供類似的實作 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 的組合案例

TODO:

解釋上述程式碼運作原理
改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

2023q1 Homework3 (quiz3)

測驗一

引入 list.h

測驗二

程式碼講解

Linux 核心 rb_tree 替代 AVL_tree 之因素

(TODO)利用 rb_tree 替代 AVL_tree 之實作

測驗三

測驗四

運作原理

改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless

(TODO)Linux 核心中 ceil 和 log2 的組合案例

Read more

2023 年「資訊科技產業專案設計」作業 1

vcam

2023q1 Homework2 (quiz2)

2023q1 Homework5 (assessment)