2025q1 Homework2 (quiz1+2)

contributed by <Andrushika>

Week 1 Q1

本題要實作 list_insert_before 這個函式：

如果只看函式說明，參數的用法還是有些難懂。所以往前找到了 list_t 和 list_item_t 的定義：

typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

由此可知，list_t 代表著整個鏈結串列，其中每個節點的結構為 list_item。

接下來，在不看題目給定的程式碼的狀況下，思考應該如何實作；可以歸納為以下步驟：

1. 用迴圈迭代，維護兩個 list_item* (*prev, *curr)，代表著目前和上一個節點
2. 持續迭代更新兩個 pointer，直到 curr == before
3. 插入 *item 到 *prev 和 *curr 之間

void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
    if (!l || !item) return;

    // 如果要插入的位置就是 head (或原本就是 empty)
    // 那 item 會變成新的 head
    if (before == l->head) {
        item->next = l->head;
        l->head = item;
        return;
    }

    list_item_t *prev = NULL;
    list_item_t *curr = l->head;

    // 迭代直到找到 curr == before 或走到串列末端
    while (curr && curr != before) {
        prev = curr;
        curr = curr->next;
    }

    // 連結新節點
    if (curr == before) {
        item->next = curr;
        if (prev) {
            prev->next = item;
        }
    }
}

但這樣的實作方式不太優雅，需要考慮太多 edge cases（要從 head 插入等等）

改用 pointer of pointer 來簡化過程，用一個比較生動的描述幫助理解：

1. 找到指向 *before 的指標 （找到 *before 他家，即 **before）
2. 把 *before 從他家趕出來，讓新節點 *item 住進去
   （如此一來，原本指向 *before 的，會變成指向 *item）
3. *item 的下一位指向 *before

依題意可實作成下方程式碼：

void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

將步驟視覺化：
（假設 before->value = 4, item->value = 3）

先移動到 pointer of pointer，找到 *before 的家

把 *before 從他家趕出來，讓新節點 *item 住進去

將*item 的下一位指向 *before

Week 1 Q2

先看節點的結構：

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

可以觀察到 *l, *r 這樣指向下一個節點的指標，可以合理推測是使用 Binary tree 進行 free block 的管理。
本題要完成的是 remove_free_tree 這個函式，看起來和 Binary Search Tree 的 remove 操作相同，該函式的流程如下：

1. 先用 find_free_tree(root, target) 找到欲刪除節點的位置
2. 根據 target 擁有不同數量的 child，有不同的策略
   • target 同時有 l, r child
     • 找到 target 的 pred，稍等要用它來取代 target 本身
     • 如果 pred 是 target 的 l child，可以直接用 pred 替換 target
     • 如果不是，代表要先從其他 subtree 中移除 pred；先遞迴呼叫 remove 後，才把它用來替換 target
   • target 只有一個子節點，直接用子節點替換 target
   • target 是 leaf node，直接刪除 target
3. 清理 target 節點，防止 dangling pointer

在做題目的時候，一直卡在 predecessor node 這個名詞；原來他指的是 left subtree 中最大的節點。

了解名詞後，要填出空缺處的 code 就很簡單了：

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred)->r)
    pred_ptr = &(*pred)->r;

Week 1 Q3

本題目標為實作 quick sort，不使用傳統遞迴的方式，而是改用兩個 linked list pointer left, right 來儲存陣列中元素和 pivot 比較大小後的結果；比較小的會被儲存在 left，比較大的儲存在 right。

針對程式碼中空缺的地方進行填補：

rebuild_list_link

下方的程式在進行 circular doubly linked list 的重建，可以看出迴圈的最後是在連接 linked list 的 head 和 tail；因要進行雙向的連結，故補上該程式碼。

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev; // GGGG
}

quick_sort

參照題意，每次會從 begin[] 選定 pivot（每個 begin[i] 都是一個 linked list 的 head）
讓所有元素和 pivot 比大小，並依結果放進 left or right；分組完畢後再將 left 和 right 放進 begin[] 中。

原先的實作方式中還會使用 end 去紀錄子陣列結束點；但在 linux kernel list API 中，可以直接呼叫 list_end()，就無需再用額外的記憶體空間紀錄 end。
分組完畢的結果可以參考以下：

之後會繼續對左、右子鏈結串列持續 quick sort。當 L == R，也就是 list 中只剩下一個節點時，會直接將其將到 result 中。

這樣的實作方式，需要確保 left, right 在分割完畢後，放進 begin[] 時的順序需為 inorder。根據這個線索，可以完成程式碼空缺部分：

{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = pivot->value; // HHHH
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = n->value; // IIII
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            // 此處須以 inorder 插入
            begin[i] = left;
            begin[i + 1] = pivot; // JJJJ
            begin[i + 2] = right; // KKKK
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

Week 2 Q1

本題和 Week 1 Q3 相似，都和 quick sort 高度相關；但實作手法不同，本題更全面使用 linux kernel list API。

在開始完成題目需求前，先探討一下前面的亂數生成、洗牌函式。

get_num

一開始看不太懂，為何一個沒有傳入參數的函式，可以用來產生每次都不相同的隨機數？
原來是這三行的定義發揮了作用：

static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);

此處使用 static，讓 s1, s2, s3 即使在函式結束後，占用的記憶體不會被釋放掉；進而導致每次呼叫 get_num() 會有不一樣的結果。

static 的特性可以參考 C99 規格書：

An object whose identifier is declared with external or internal linkage, or with the storage-class specifier static has static storage duration. Its lifetime is the entire execution of the program and its stored value is initialized only once, prior to program startup. (C99 6.2.4.3)

隨機數產生的小細節？

get_num() 實際上是使用了 Linear congruential generator (LCG) 來產生隨機亂數：

$$X_{n+1}=(a{X}_n+c)modm$$
但是單個變數所產生的亂數，在經過

$m$ 週期後就會重複。
題目的設計使用了三個變數計算 LCG 後 XOR，使重複的週期延長，為三個

$m$ 的最小公倍數。當三個

$m$ 互質時，可以達到最長的周期。
舉例來說，題目裡設計的三個

$m$ 分別為 30269, 30307, 30323，其週期為：

$$30269\times 30307\times 30323=2.8\times {10}^{13}$$

random_shuffle_array

先看程式碼：

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}

這個算法存在兩個問題：

1. 在選擇隨機數時，每次隨機數出現的機率不同。由於每次都是對 i+1 mod，那麼對於其他 n (i+1 <= n < len) 就沒有被選到的機會。
   這樣會造成某些排列組合出現的機率比較高，亂度不足。
2. 在完成隨機 index 選擇後，swap 的操作有些奇怪。除非能保證輸入的陣列滿足 operations[i] == i 的條件，否則 shuffle 函式的結果會有錯誤。這不只是亂度不足的問題，可能會意外改變了陣列內的元素。若不能保證 input，使用 swap 才正確。

list_quicksort

此處為本題填空主要作答的地方，考驗點應該是 linux kernel list API 的熟悉程度，且前面已經解釋過 quick sort 的思路，故不再詳細解釋。
附上程式碼：

{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    // AAAA
    pivot = list_first_entry(head, struct listitem, list);
    // BBBB
    list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            // CCCC
            list_move_tail(&item->list, &list_greater); 
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);
    
    //DDDD 加入單顆節點到 linked list 中
    list_add(&pivot->list, head); 
    
    //EEEE 加入整串 left 到 head
    list_splice(&list_less, head);
    
    //FFFF 加入整串 right 到 tail
    list_splice_tail(&list_greater, head);
}

為何使用 list_move 取代 list_move_tail 時無法滿足 stable sort？

根據 kernel.org 於 Linux Kernel API List Management Functions 的說明，list_move 的作用如下：

void list_move(struct list_head * list, struct list_head * head)

delete from one list and add as another’s head

因為 list_for_each_entry_safe 是逐一走訪，比較後方的節點也會比較晚走訪到。如果使用 list_move，當兩個節點值相同時，會將後方節點插入在前方節點之前，也就破壞了 stable sort 的規則。

Week 2 Q2

clz2() 包含了兩個參數，其定義如下：

unsigned clz2(uint32_t x, int c)

其中 x 代表目前要計算 count leading zero 的目標數，c 代表目前已經累積計算第幾輪。因為每次會把 x 拆成一半 （upper 和 lower） 以進行後續運算，每次遞迴呼叫時，x 的 bits 長度減半 （

${\log }_{2}x\to \frac{{\log }_{2}x}{2}$），所以這個函式可以在

$O(\log ({\log }_{2}x))$ 的時間複雜度下完成計算。

註：對於任意 x，其在二進位制下的 bits 數可表示為

${\log }_{2}x$

模擬運算過程

假設要對 0x00000001 count leading zero，運行的過程應該長怎樣呢？

第一輪

x = 0x00000001, c = 0

Upper	Lower
0000 0000 0000 0000	0000 0000 0000 0001

此時 upper 為 0，確定至少有 16 個 leading zero。
因此呼叫 return 16 + clz2(lower, c+1)，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 16 個 0）

第二輪

x = 0x0001, c = 1

Upper	Lower
0000 0000	0000 0001

此時 upper 為 0，確定至少有 8 個 leading zero。
因此呼叫 return 8 + clz2(lower, c+1)，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 24 個 0）

第三輪

x = 0x01, c = 2

Upper	Lower
0000	0001

此時 upper 為 0，確定至少有 4 個 leading zero。
因此呼叫 return 4 + clz2(lower, c+1)，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 28 個 0）

第四輪

x = 0x1, c = 3

Upper	Lower
00	01

做到這邊時，已經不用繼續遞迴呼叫，可以直接從 magic[] 來獲取結果。
判斷依據是 magic[] 的 size 為 4，且程式中只有一行會用到 magic[]：

return upper ? magic[upper] : KKKK + magic[lower];

由此可知，當 upper 和 lower 小於 4 時，可以直接進行查表；且此時 c = 3，因此可以借助這些線索，還原 clz2() 程式碼如下：

static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

整數開根號實作

參閱老師撰寫的 從 √2 的存在談開平方根的快速運算 Digit-by-digit Method 部分，但該章節最後好像沒有寫完整，因此我參照 維基百科 將剩餘證明過程補齊。

對於二進位制，可以先假設我們要計算平方根的數如下：

$$N^2=(a_n+a_{n-1}+\cdots +a_1+a_0{)}^2$$

注意！此處的

$a_n$ 為最高位係數！所以從最高位到最低位，

$n$ 是倒序的

以上假設數的二進位表示法共有

$n$ 位，其中每一個

$a_m$ 皆為

$2^m$ 或

$0$。
透過 digit-by-digit 的方法，由高位開始找到低位，依序判斷「放不放得下」。為了計算方便，定義一個符號：

$$P_m=a_n+a_{n-1}+\cdots +a_{m+1}+a_m$$

由於會逐位進行測試「是否塞得下」，

$P_m$ 將代表著「目前確定的部份和」。隨著每次測試，

$P_m$ 都會更新一次，直到

$P_0=N$。

逐位檢查的過程，事實上就是在檢查以下條件是否成立：

$$\begin{array}{rl}& P_m^2\le N^2\\ \Rightarrow & (P_{m+1}+2^m{)}^2\le N^2\end{array}$$

但因為每次檢查條件都要計算平方的話，成本很高；可以再額外定義兩個符號，幫助後續的加速與簡化。

$$X_m=N^2-P_m^2$$ 主要的想法是，每次計算完「是否塞得下某數」之後，就把該數從總數中減去。這裡的

$X_m$ 代表餘數，亦會隨著逐位更新而變動：當第

$m$ 位決定後，距離最終目標還剩多少？當

$P_m^2$ 足夠逼近

$N^2$ 時，

$X_m$ 就會很小。這樣一來，就不用每次都計算

$N^2-P_m^2$，只需要每一位

$a_m$ 決定完，更新

$X_m$ 即可。

再定義

$X_m$ 的更新方式：

$$X_m=X_{m+1}-Y_m$$

$$\begin{array}{rl}{Y}_m& =P_m^2-P_{m+1}^2\\ & =(P_{m+1}+a_m{)}^2-P_{m+1}^2\\ & =P_{m+1}^2+2\cdot P_{m+1}\cdot a_m+a_m^2-P_{m+1}^2\\ & =2P_{m+1}{a}_m+a_m^2\end{array}$$

此處所定義的

$Y_m$ 代表

$X_m$ 所需更新的幅度。所有

$Y_i$ 的和正好會等於最終部分解

$P^2$。
這樣還不夠，為了完全免去在程式實作中的乘法操作，還需要定義兩個符號來巧妙的避開他們。

$$c_m=P_{m+1}{2}^{m+1}$$

$$d_m=2^{2m}$$

這樣一來，若

$Y_m$ 中的

$a_m$ 為

$2^m$ （該位「放得下」），則定義為

$$Y_m=c_m+d_m$$ 否則為

$0$。

經過這番巧妙的定義，

$c_m$ 和

$d_m$ 的更新方式，變成了可以透過位移和加法操作完成的形式：

$$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=\{\begin{array}{ll}{\displaystyle c_m/2+d_m}& \text{if }{a}_m=2^m\\ {\displaystyle c_m/2}& \text{if }{a}_m=0\end{array}$$

$$d_{m-1}=\frac{d_m}{4}$$

其中

$c_{-1}=P_0{2}^0=P_0=N$，即為所求之開根號計算結果。

最後來看程式碼：

uint64_t sqrti(uint64_t x)
{
    // m is d_n in the proof above
    // y is c_n
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;

    /* clz64(x) returns the count of leading zeros in x.
     * (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
     * Rounding that index down to an even number ensures our starting m is a
     * power of 4.
     */
    int shift = (total_bits - 1 - clz64(x)) & ~1;
    m = 1ULL << shift;

    while (m) {
        // b is Y_m = c_m + d_m
        uint64_t b = y + m;
        y >>= 1;       // c_m = c_m/2 (do it early, use later)
        if (x >= b) {  // if X_(m+1) ≥ Y_m then a_m = 2^m
            x -= b;    // X_m = X_(m+1) - Y_m
            y += m;    // c_(m-1) = c_m/2 + d_m (for the case a_m = 2^m)
        }
        m >>= 2;
    }
    return y; // c_(-1) = sqrt(x)
}

擴充為

$\lceil \sqrt{x})\rceil$ 函式

事實上，向上取整可以視作下方兩個條件：

• x 有小數部分，答案為整數部分 +1
• x 沒有小數部分，答案維持不變

在上方小節的證明中，提及了

$X_m$ 為餘數。若

$X$ 在做完開根號後為 0（整除），則代表傳入函式的數值是完全平方數，不需要做額外操作；反之，對

$c_{-1}$ +1（在先前程式中為變數 y）即為所求。

在先前的程式碼中加上兩行即可：

uint64_t sqrti(uint64_t x)
{
    //... ignore()
    
    if(x > 0)
        y++;
        
    return y; // c_(-1) = ceil(sqrt(x))
}

Week 2 Q3

Hash Table 的結構

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

其中 hlist_node 為何需要將 pprev 定義為 pointer of pointer 呢？他代表的又是什麼？
先觀察 map_add() （已經還原程式空缺處）：

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key;
    kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)]; 
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        first->pprev = &n->next;  /* CCCC: 把原先第一個節點的 pprev 指向 n->next */
    h->first = n;
    n->pprev = &h->first;         /* DDDD: 新節點 n 的 pprev 指向鏈表頭 */
}

這個 add 操作，會把新的 node 插入到該 hash bucket 的第一個位置。
其中 first->pprev = &n->next;，會將後方節點的 pprev 指向「上個節點指向自己的指標」（換句話說，他其實在指著自己的家？）
若當前節點是 hash bucket 中的第一個節點，指向自己的會是 hlist_head*；而若不是第一個節點，指向自己的則會是 hlist_node*。選擇不和普通的 doubly linked list 一樣維護一個 *prev，而是改用 **pprev 的話，就不需要創建一個「用不到、但和 hlist_node 一樣肥的 dummy head」，可以節省更多空間。

這樣做的好處是，當想要對特定節點進行刪除時，就不需要對當前節點的狀態進行額外判斷（是否是第一個節點等等），如果想要刪除，可以簡化成以下（假設要刪除的節點為 curr）：

if (n->pprev) {
    *n->pprev = n->next;
}
if (n->next) {
    n->next->pprev = n->pprev;
}

（參考 Linux 核心的 hash table 實作）

two sum 使用 hash table 的實作

由於 hash table 在沒有 collision 的狀況下，可以達到 query 和 insert 操作時間複雜度 O(1) 的優異表現；可以利用其特性來完成 two sum 函式。

步驟 - 走訪所有陣列中數值

• 若該數的 key 不存在於 hash table，代表尚未出現匹配的數字
  • 將 target - num 加入 hash table 中，供後續數值匹配
• 若該數 key 存在於 hash table，則 return table[num]

Linux 核心中使用 hash table 的應用

fs/inode.c

在檔案系統中的 inode，是協助在 data block 檢索資料時使用的索引節點。
可以看到在 inode.c 中定義了這個：

static struct hlist_head *inode_hashtable __ro_after_init;

其中 __ro_after_init 為 初始化後改為 read-only 之意。
可以看到，在 ilookup 中，該 hash table 被用來快速尋找 inode 位置：

struct inode *ilookup(struct super_block *sb, unsigned long ino)
{
        //此行可以快速得到對應的 hash bucket
	struct hlist_head *head = inode_hashtable + hash(sb, ino);
	struct inode *inode;
again:
	inode = find_inode_fast(sb, head, ino, false);

	if (inode) {
		if (IS_ERR(inode))
			return NULL;
		wait_on_inode(inode);
		if (unlikely(inode_unhashed(inode))) {
			iput(inode);
			goto again;
		}
	}
	return inode;
}

可以看到是以 ino (inode number) 進行 hash 計算，其中 head 為 inode 所在的 bucket，因為可能存在多個 inode 在 bucket 中，所以還需要呼叫 find_inode_fast() 尋找正確的對應 inode。
程式碼的下半部則是針對修改檔案系統時的 lock 處理；一次只能有一個 writer，必須等待該 inode idle 的時候才可以對其進行修改。

net/phonet/socket.c

在 socket 套件中也能看見 hash table 的身影。不過本套件似乎有些冷門，根據 The Linux Kernel 官網描述，Phonet 這個封包協議是由 Nokia 的手機及相關設備在使用：

Phonet is a packet protocol used by Nokia cellular modems for both IPC and RPC. With the Linux Phonet socket family, Linux host processes can receive and send messages from/to the modem, or any other external device attached to the modem.

在 socket.c 中，裡面定義了一個包含 hash table 的結構：

static struct  {
	struct hlist_head hlist[PN_HASHSIZE]; //hash table
	struct mutex lock;
} pnsocks;

還有使用到 hash table 的函式：

static struct hlist_head *pn_hash_list(u16 obj)
{
	return pnsocks.hlist + (obj & PN_HASHMASK);
}

struct sock *pn_find_sock_by_sa(struct net *net, const struct sockaddr_pn *spn)
{
	struct sock *sknode;
	struct sock *rval = NULL;
	u16 obj = pn_sockaddr_get_object(spn);
	u8 res = spn->spn_resource;
	struct hlist_head *hlist = pn_hash_list(obj);

	rcu_read_lock();
	sk_for_each_rcu(sknode, hlist) {
		struct pn_sock *pn = pn_sk(sknode);
		BUG_ON(!pn->sobject); /* unbound socket */

		if (!net_eq(sock_net(sknode), net))
			continue;
		if (pn_port(obj)) {
			/* Look up socket by port */
			if (pn_port(pn->sobject) != pn_port(obj))
				continue;
		} else {
			/* If port is zero, look up by resource */
			if (pn->resource != res)
				continue;
		}
		if (pn_addr(pn->sobject) &&
		    pn_addr(pn->sobject) != pn_addr(obj))
			continue;

		rval = sknode;
		sock_hold(sknode);
		break;
	}
	rcu_read_unlock();

	return rval;
}

本函式將用來尋找特定的 socket，會傳入一個 obj 來計算 hash。同樣的，因 hash table 存在 collision 問題，需要在找到 bucket 後逐一走訪，確認該節點是 target 時才回傳。

走訪時使用到了 RCU 機制，簡單來說是同時允許一個 writer、多個 reader 存取檔案的機制，需要再深入學習 Linux 核心設計: RCU 同步機制