# 2023q1 Homework3 (quiz3)
contributed by < [cin-cout](https://github.com/cin-cout) >
[題目](https://hackmd.io/@sysprog/linux2023-quiz3)

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

### Question
考慮一個 Tree sort 的實作，搭配 Red–black tree 作為排序所需的自我平衡樹，原始程式碼可見 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。

先簡單介紹一下 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 的內容，主要是利用紅黑樹去實作map。

資料結構如下：
tree node 的方面， `color` 紀錄其顏色、`left` `right` 則記錄其左右子節點 `next` 是用來記錄在原本 array 中其下一個位置在 RB tree 中 node 的位置、`value` 則是記錄其值。

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

map 的資料結構則會記錄 RB tree 的 root，以及其他 map 之中的一些特質(ex size)。

struct cmap_internal {
    node_t *head;

    /* Properties */
    size_t key_size, element_size, size;

    cmap_iter_t it_end, it_most, it_least;

    int (*comparator)(void *, void *);
};

#### AAAA
這邊用了一個特殊的方法來儲存顏色。因為現在電腦多數都是 64 bits (8 bytes)，所以其位置二進位最後三位必為 0。所以這邊就用了 node 的 parent 的位址的第一個 bit 來儲存 node 之顏色，如此一來找 parent 只需要對其顏色做 bit wise 的處理，不須額外花費記憶體空間，紅色為 0 黑色為 1。

由上述邏輯可知要找 node 的 parent 只需把 node 的 color 前三個(或第一個) bits 設為 0 ，故 AAAA = `((r)->color & ~7)`。

typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;

#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)

#### BBBB CCCC
同 AAAA 提到的原理，透過更改其 parent 的 last bit 來記錄顏色，在 set color 時，紅色為 0 ，黑色為 1。
故 BBBB 為 `(r)->color &= ~1`。
故 CCCC 為 `(r)->color |= 1`。

#define rb_set_red(r) \
    do {              \
        BBBB;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        CCCC;           \
    } while (0)

#### DDDD EEEE
rb tree insert node 的程式碼如下，DDDD、EEEE 前的部分是在處理 create root 的狀況，為解答出 DDDD、EEEE，我們著重於 for 迴圈的部分。

for 迴圈處的邏輯跟 binary tree insert 的方式類似，即若小於此處的 node 則往左走，反之大於則往右走，直到走到 null 的位置即為要插入的位置。

故 DDDD 為 cur = cur->left。
故 EEEE 為 cur = cur->right。

另外，插入時會需要先 set parent，而 `cmap_fix_colors` 則會對於 ll lr rl rr 的情況去平衡紅黑數。

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) {
            if (!cur->left) {
                cur->left = node;
                rb_set_parent(node, cur);
                cmap_fix_colors(obj, node);
                break;
            }
            DDDD;
        } else {
            if (!cur->right) {
                cur->right = node;
                rb_set_parent(node, cur);
                cmap_fix_colors(obj, node);
                break;
            }
            EEEE;
        }
    }

    cmap_calibrate(obj);
    return true;
}

#### FFFF GGGG HHHH
最後則是實際使用 map 的情況，輸入會是一個 list 而 map 則會使用紅黑樹將其排序。

FFFF 是為將 list 內的值一一傳入 map 做 insert，故在每次 while　時都必須將 *list 改下一個值的位置。

故 FFFF = &(*list)->next

for 迴圈的部分是將排序完成後的結果放回 list。每次迴圈都會更新到下一個 node ，GGGG 則是在耕莘 list 的位置。

故 GGGG 同為 &(*list)->next。

將 list 更新完畢以後，必須確保最後一個值的 next 為 null， list 在 for 結束後會落在，tail->next 的位置。

故 HHHH 為 *list = NULL。

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 = FFFF;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = GGGG;
    }
    HHHH;
    *record = first;
    free(map);
}

### Answer
:::success
AAAA = `((r)->color & ~7)`
BBBB = `(r)->color &= ~1`
CCCC = `(r)->color |= 1`
DDDD = `cur = cur->left`
EEEE = `cur = cur->right`
FFFF = `&(*list)->next`
GGGG = `&(*list)->next`
HHHH = `*list = NULL`
:::

## 測驗二
### 延伸問題:
1. 解釋上述程式碼運作原理，並比較用紅黑樹實作的 priority queue，應提供完整的測試程式和效能分析
2. Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀
見 commit b145425
3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會
### Question
考慮一個使用 AVL tree 實作的 priority queue。
其中 `avltree.h` 的程式碼可見 [avltree.h](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。

AVL tree 是嚴格的平衡樹，每一個節點的左子樹高度跟右子樹的高度不差超過 1 。

先講解 AVL tree node 的資料結構：
`left` `right` 是紀錄其左右子節點的位址，`parent_balance` 跟上一題 rb tree node 用了類似的手法，原因以及好處可見上題。後三位 bits 用來儲存此節點 balance 的狀況，高位元用來儲存父節點的位址。

struct avl_node {
    unsigned long parent_balance;
    struct avl_node *left, *right;
} AVL_NODE_ALIGNED;

balance 的狀況有三種，分別為：
`AVL_NEUTRAL (0)` 左右子樹高度相等。
`AVL_LEFT (1)` 左子樹高 1 。
`AVL_RIGHT (2)` 右子樹高 1 。

enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };

#### IIII
如同上述的解釋，在找 parent 時，即抓取 parent_balance 的高位元。

故 IIII 為 (node)->parent_balance & ~7。

static inline struct avl_node *avl_parent(struct avl_node *node)
{
    return (struct avl_node *) (IIII);
}****

#### JJJJ
找 balance 也一樣，即抓取 parent_balance 的最低三位元，因為 balance 只有 0 1 2，所以只會用到最低二位，可以只取最低兩位，放 & 7 也可以。

故 JJJJ 為 (node)->parent_balance & 3。

static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
    return (enum avl_node_balance)(JJJJ);
}

#### KKKK
更新 parent 必須要考慮到 parent 跟 balance ， set parent 只要更新父節點的位置，balance 保持一樣。函式中已經有更新 parent 的實作，缺少保留 balance 的實作部分。

故 KKKK 為 (node)->parent_balance & 3。

static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
    node->parent_balance =
        (unsigned long) parent | (KKKK);
}

#### LLLL
反之，在更新 balance 時，也必須保持原 parent 的狀況。

故 LLLL 為 (node)->parent_balance & ~7。

static void avl_set_balance(struct avl_node *node,
                            enum avl_node_balance balance)
{
    node->parent_balance = (LLLL) | balance;
}

#### MMMM NNNN
最後則是在插入新的節點後平衡的處理。
簡單講解 AVL 樹的平衡方式，首先檢查它是其父節點的左子節點還是右子節點。對於右子節點，它根據父節點的 balance 做出不同的處理。
如果父節點的 balance 是 AVL_LEFT，意味著它的左子樹比右子樹高，這樣 node 插入右側就沒什麼問題。
若是 AVL_RIGHT，意味著它的右子樹比左子樹高，這樣 node 插入右側就則需要做旋轉的處理，處理方式則是依照 node 本身的 balance來決定，來保持 AVL 樹的平衡性。
若是 AVL_NEUTRAL，則需要繼續往上檢查到上面的節點需不需要旋轉。
對於左子節點，它的處理方式類似，只是 balance 的方向相反。

故 MMMM 為 avl_rotate_right。
故 NNNN 為 avl_rotate_leftright。

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:
                    MMMM(node, parent, root);
                    break;
                case AVL_RIGHT:
                    NNNN(node, parent, root);
                    break;
                }

                parent = NULL;
                break;
            }
        }

        if (!parent)
            break;

        node = parent;
    }
}

### Answer
:::success
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`
:::

## 測驗三
### 延伸問題:
1. 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例
2. 解釋上述程式碼運作的原理
3. 在 Linux 核心原始程式碼中找到 log2(x) 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 log2(x) 的應用案例並解說。
4. lab0-c 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能

### Question

考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large uint64_t)。完成 [bucket_uniform.c](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d) (部分程式碼遮蔽)。

#### AAAA ~ HHHH
先看 log2_64 這個函式，此函式的目的是找到 64 bits 數的 log2 floor int。在測驗中，這個函式的目的是找到一個 64 bits 的 FSB (第一個 1 的) 位置。

使用的方法為，使用不斷的 shift 的方式，找到 64 bits FSB 在哪一個 bytes，使用這個 bytes 去查表找到其 log2 值，最後要加上前面 shift 的數量。

舉例：
0x0100000000000000
在例子中 shift 了 48 次。
使用 1 這個 bytes 去查表時，得到的結果為 1 。
所以最後 r 為 49。

其意義為，因為找 log2 floor 意及找 FSB 的位置，在這個例子中，我們用查表得到了 1 的 log2 (意及其在這 8 bytes 中 FSB 的位置)，但前面 shift 掉了 1 後面的 48 個 bits，所以最終 FSB 的位置必須加上 48。

故 AAAA 為 56 。
故 BBBB 為 48 。
故 CCCC 為 40 。
故 DDDD 為 32 。
故 EEEE 為 24 。
故 FFFF 為 16 。
故 GGGG 為 8 。
故 HHHH 為 0 。

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 = AAAA + log_table_256[t];
            } else {
                r = BBBB + log_table_256[tt];
            }
        } else {
            t = ttt >> 8;
            if (t) {
                r = CCCC + log_table_256[t];
            } else {
                r = DDDD + log_table_256[ttt];
            }
        }
    } else {
        tt = v >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = EEEE + log_table_256[t];
            } else {
                r = FFFF + log_table_256[tt];
            }
        } else {
            t = v >> 8;
            if (t) {
                r = GGGG + log_table_256[t];
            } else {
                r = HHHH + log_table_256[v];
            }
        }
    }
    return r;
}

#### IIII JJJJ
IIII JJJJ 在 `bucket_number` 這個函式中，但是在理解怎麼做此函式前，必須知道其用處。

所以我們先解釋，`fill_buckets` 這個函式：
步驟為：

1. while 迴圈會利用多次的 lfsr 找到一個 64 bits 的隨機數 x。
2. 利用這個隨機數，放入 `bucket_number` 得到一個小於設定的 N_BUCKETS 的數，所以得出來的 tmp_bucket 也可以視為 1 隨機數。

以一套這樣的方法，就可以產生固定範圍的隨機數了！
而 for 迴圈只是重複做多次上數的步驟，用來統計產生出來的隨機數。

(lfsr 原理請見題目)

void fill_buckets(unsigned int *buckets, unsigned int iterations)
{
    uint64_t x = 0x98765421b16b00b5;
    unsigned char lfsr_iter = (N_BITS << 1);

    for (uint64_t i = 0; i < iterations; i++) {
        unsigned int tmp_bucket = bucket_number(x);
        *(buckets + tmp_bucket) = *(buckets + tmp_bucket) + 1;

        // 'turn handle' on LFSR lfsr_iteration-times!
        unsigned char ell = 0;
        while (ell < lfsr_iter) {
            lfsr(&x);
            ell++;
        }
    }
}

如此一來就可以來探討 `bucket_number` 這個函式了，這個函式的目的即為將傳入的 64 bits 整數轉換為一規定範圍內的數字。

首先，有兩種 mask，配合上面 log2_64 的意義，找到一個 64 bits 的 FSB (第一個 1 的) 位置，不難理解其意義：
mask111：包含 FSB 之下的 bits 全為 1。
mask011：不包含 FSB 之下的 bits 全為 1。

之後 leq 的意義為判斷 64 bits 的 x 是否有大於我們設定的 N_BUCKET。

最後的 return 則分為兩種狀況：
1. 若傳入的 x 就已經比 N_BUCKET 小了，直接回傳 x。
2. 若傳入的 x 大於等於 N_BUCKET ，取 x 的高位元段回傳。

第一個很好理解是直接對 mask111 做 and，而第二個因為確保高位元段的值一定比 N_BUCKET 小，所以是跟 mask011 做 and 。

故 IIII 為 mask111。
故 JJJJ 為 mask011。

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 & IIII)) +
           ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ));
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

### Answer
:::success
AAAA = `56`
BBBB = `48`
CCCC = `40`
DDDD = `32`
EEEE = `24`
FFFF = `16`
GGGG = `8`
HHHH = `0`
IIII = `mask111`
JJJJ = `mask011`
:::

## 測驗四
### 延伸問題:
1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有。善用 lxr 和 git log

### Question
已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算
⌈log2(x)⌉，也就是 ceil 和 log2 的組合並轉型為整數:

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 (KKKK) + 1;       
}

#### KKKK
邏輯跟上一題的 log2 floor 類似，只是不是用 control flow 的方式找到 FSB 所在的位置，而是無論是哪一種情況都能成功計算 FSB 的位置。

接著解釋程式碼：

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    /*
    因為是求 ceil ，最後結果都會加 1 ，
    但是對於本來就是 2 冪次的數反而會多加 1 ，
    所以一開始先減掉 1 避免此問題。
    */
    x--;
    /*
    如果 x 前 16 bits 有值，r = 16 反之 r = 0
    r 的意義跟上題類似是用來記錄目前統計到 FSB 後的值。
    */
    r = (x > 0xFFFF) << 4;                 
    /*
    x shift r 次，即後面 16 位已討論完，繼續討論前 16 位。
    若 shift 0 次，即前 16 位沒值，直接討論後 16 位。
    */
    x >>= r;
    /*
    同理，只是改為處理 x 前 16 bits 或後 16 bits，而非 32 bits。
    */
    shift = (x > 0xFF) << 3;
    /*
    因為 r 是代表累計的 shift 數量所以，改為用 shift 紀錄。
    */
    x >>= shift;
    /*
    因為 shift 是從 16 -> 8 -> 4 -> 2 討論。
    所以可以利用 r |= shift 代替 r += shift。
    */
    r |= shift;
    /*
    同理。 
    */
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    /*
    最後因為要直接 return 了，所以將 r |= shift ，
    直接留在 KKKK 做，而此時 x 還剩下 2 位，所以最後
    累計的 shift 還要在 + x>>1 (例如 x = 0b10)。
    
    故 KKKK 為 r | shift | x >> 1。
    最後的 + 1 是因為是求 ceil。
    */
    return (KKKK) + 1;       
}

### Answer
:::success
KKKK = `r | shift | x >> 1`
:::