2023q1 第 3 週測驗題

目的: 檢驗學員對 bitwise, alignment, C 語言程式設計的認知

作答表單: 測驗 1-2 (針對 Linux 核心「設計」課程)
作答表單: 測驗 3-4 (針對 Linux 核心「實作」課程)

測驗 1

考慮一個 Tree sort 的實作，搭配 Red–black tree 作為排序所需的自我平衡樹，原始程式碼可見 treesort.c。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。

作答規範:

• AAAA : 利用〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，對給定的引數 (r) 計算合法的記憶體地址 (記得要考慮 alignment)。
• BBBB 和 CCCC : 運用〈你所不知道的 C 語言：數值系統篇〉和〈你所不知道的 C 語言: bitwise 操作〉，以 bitwise 操作分別設定紅黑數節點的顏色。
• DDDD, EEEE, HHHH 是 C 語言敘述
• FFFF 和 GGGG 則運用〈你所不知道的 C 語言: linked list 和非連續記憶體〉，是合法的 C 語言敘述
• 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 r | 1
• 上述皆不包含 ;，並該依循 CONTRIBUTING.md 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫

延伸問題:

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

---

測驗 2

考慮一個使用 AVL tree 實作的 priority queue，部分程式碼如下:

#include "avltree.h"

struct avl_prio_queue {
    struct avl_root root;
    struct avl_node *min_node;
};

static inline void avl_prio_queue_init(struct avl_prio_queue *queue)
{
    INIT_AVL_ROOT(&queue->root);
    queue->min_node = NULL;
}

static inline void avl_prio_queue_insert_unbalanced(
    struct avl_prio_queue *queue,
    struct avlitem *new_entry)
{
    struct avl_node *parent = NULL;
    struct avl_node **cur_nodep = &queue->root.node;
    struct avlitem *cur_entry;
    int isminimal = 1;

    while (*cur_nodep) {
        cur_entry = avl_entry(*cur_nodep, struct avlitem, avl);

        parent = *cur_nodep;
        if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
            cur_nodep = &((*cur_nodep)->left);
        } else {
            cur_nodep = &((*cur_nodep)->right);
            isminimal = 0;
        }
    }

    if (isminimal)
        queue->min_node = &new_entry->avl;

    avl_link_node(&new_entry->avl, parent, cur_nodep);
}

static inline struct avlitem *avl_prio_queue_pop_unbalanced(
    struct avl_prio_queue *queue)
{
    struct avlitem *item;
    bool removed_right;

    if (!queue->min_node)
        return NULL;

    item = avl_entry(queue->min_node, struct avlitem, avl);
    queue->min_node = avl_next(queue->min_node);

    avl_erase_node(&item->avl, &queue->root, &removed_right);

    return item;
}

tatic inline void avl_prio_queue_insert_balanced(
    struct avl_prio_queue *queue,
    struct avlitem *new_entry)
{
    struct avl_node *parent = NULL;
    struct avl_node **cur_nodep = &queue->root.node;
    struct avlitem *cur_entry;
    int isminimal = 1;

    while (*cur_nodep) {
        cur_entry = avl_entry(*cur_nodep, struct avlitem, avl);

        parent = *cur_nodep;
        if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
            cur_nodep = &((*cur_nodep)->left);
        } else {
            cur_nodep = &((*cur_nodep)->right);
            isminimal = 0;
        }
    }

    if (isminimal)
        queue->min_node = &new_entry->avl;

    avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root);
}

static inline struct avlitem *avl_prio_queue_pop_balanced(
    struct avl_prio_queue *queue)
{
    struct avlitem *item;

    if (!queue->min_node)
        return NULL;

    item = avl_entry(queue->min_node, struct avlitem, avl);
    queue->min_node = avl_next(queue->min_node);

    avl_erase(&item->avl, &queue->root);

    return item;
}

其中 avltree.h 的程式碼可見 avltree.h。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。

作答規範:

• IIII, JJJJ, KKKK, LLLL 利用〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，計算合法的記憶體地址 (記得要考慮 alignment)。
• MMMM 和 NNNN 為函式名稱
• 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 r | 1
• 上述皆不包含 ;，並該依循 CONTRIBUTING.md 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫

延伸問題

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

   見 commit b145425

3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會

---

測驗 3

Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，其應用包括 PRNG 場景。

LFSR 範例:

1. 初始狀態
   $s=[s_2,s_1,s_0]=[1,0,0]$
2. 反饋
   $p=[p_2,p_1,p_0]=[0,1,1]$
3. 線性運算 s[n+1] = s[n]*p[2] ^ s[n-1]*p[1] ^ s[n-2]*p[0]

考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large uint64_t)。參考執行輸出如下:

  0:91263 |   1:93093 |   2:92113 |   3:92503 |   4:92253 | 
  5:91833 |   6:93023 |   7:92283 |   8:93473 |   9:92983 | 
 10:90433 |  11:92373 |  12:91733 |  13:93733 |  14:92193 | 
...
105:81623 | 106:82253 | 107:82573 | 108:82393 | 109:82483 | 
110:82643 | 111:81483 | 112:82473 | 113:80623 | 114:82833 | 
115:81703 | 116:82213 | 117:80603 | 118:81143 | 119:81253 | 

程式碼可參見 bucket_uniform.c (部分程式碼遮蔽):

• log2_64 : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)
• bucket_number : 在指定區間內，使產生的 LFSR 數值得以均勻分佈

請補上程式碼，使程式碼的執行結果符合參考輸出。作答規範:

• AAAA, BBBB, CCCC, DDDD, EEEE, FFFF, GGGG, HHHH 皆為大於或等於 0 的整數
• IIII 和 JJJJ 是 mask111 或 mask011

延伸問題:

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

---

測驗 4

已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算

$\lceil lo{g}_2(x)\rceil$ ，也就是 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 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
• KKKK 為表示式，限制使用 ^, &, |, <<, >> 這幾個運算子，可能會出現常數
• KKKK 不該包含小括號 (即 ( 和 ))
• 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 r, shift, x
• KKKK 不可包含 , 和 ; 這樣的分隔符號 (separator)

延伸問題:

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

   善用 lxr 和 git log

---