[Linux2025q1: Quiz 2](https://hackmd.io/@sysprog/linux2025-quiz2) ## 測驗 1 測驗 1 的重點在快速排序，故先回顧何為快速排序。 :::success 快速排序基於分治 (Divide and Conquer)，係透過選定一個基準值 (pivot)，將資料分成左右兩部分(陣列、鏈結串列...)，再以遞迴呼叫 (recursive calls) 或[迭代 (iterate)](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3) 形式依序對子部分進行相同操作。直至最後子部分的長度為 0 或 1。 接著進行合併操作，根據區分資料的方式 (位置交換或是移動到新開記憶體)會有不同方式，前者是就地 (in-place) 操作，因此不需要再進行合併，後者則需依照 註: 有關迭代式鏈結串列的快排實作，可以參見 [Linux2025q1: Quiz1 Write-Up](https://hackmd.io/@dennis40816/linux2025q1-quiz1-writeup)。 ::: 現在我們來看關鍵程式: ```c static void list_quicksort(struct list_head *head); { 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); /* Section A */ pivot = AAAA(head, struct listitem, list); BBBB(&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(&item->list, &list_greater); } /* Section B */ list_quicksort(&list_less); list_quicksort(&list_greater); /* Section C */ DDDD(&pivot->list, head); EEEE(&list_less, head); FFFF(&list_greater, head); } ``` :::spoiler 可能選項 - `list_add` - `list_add_tail` - `list_del` - `list_for_each_entry_reverse` - `list_for_each_entry` - `list_first_entry` - `list_move` - `list_move_tail` - `list_splice` - `list_splice_tail` - `list_cut_position` ::: 整段程式採遞迴呼叫，大致可分為 A、B、C 三個部分，其中 B 是遞迴呼叫部分，後面不贅述。 :::info Section A ::: **AAAA** 參考值通常由頭、尾、中間或隨機選擇，而根據 `pivot` 型別，可以判斷 ++AAAA++ 要返回的是元素的指針，選項中只有 `list_first_entry` 有關。故選 `list_first_entry`。 **BBBB** 在鏈結串列中選完 `pivot` 後通常會將其移除鏈結串列中。因此推斷 ++BBBB++ 應該是移出或移動操作，因為參數只有一個，故選 `list_del`。 **CCCC** 位於 `list_for_each_entry_safe` 中，++CCCC++ 對應將鏈結串列中的一個元素 ++移動到++ `list_greater` 這個鏈結串列的頭或尾的操作。且移動操作應該使元素保持原本的順序，故選 `list_move_tail`。 :::info Section B ::: **DDDD - FFFF** ++DDDD++ - ++FFFF++ 可以一起觀察，首先當做完上述的操作，head 應該是一個指向自己的 `list_head`，我們現在要將結果添加回去。針對單個元素有以下選擇: - `list_add` - `list_add_tail` - `list_move` - `list_move_tail` 由於 `pivot` 現在是獨立的元素(沒有 `head`)，所以應該使用 `list_add` 或 `list_add_tail`，雖然意思沒有差，但前者短，故 ++DDDD++ 選 `list_add`。 ++EEEE++ 和 ++FFFF++ 是將排序好的兩個鏈結串列串接到 `head` 上，由於是按順序，所以 `list_less` 接到 `head` 的頭部(在 `pivot` 前)，而 `list_greater` 應該接到 `pivot` 的後面，所以要連到 `head` 尾部。移動整個 `list` 是 `list_splice` 相關的函式。故: - ++EEEE++: `list_splice` - ++FFFF++: `list_splice_tail` ::::info :::spoiler 延伸閱讀 🧐 看完主要程式，我們來看看輔助程式。 `getnum` 作為獲得隨機數的函式，使用了三個線性[同餘產生器 (Linear Congruential Generators, LCG)](https://link.springer.com/chapter/10.1007/978-1-4615-2317-8_3)。 LCG 的公式如下: $$ N_{j+1} \equiv (A \cdot N_j + B) \mod{M} $$ 此處的 $A$ 、 $B$ 選擇了特殊的數字，這些數值在 [Wichmann–Hill](https://en.wikipedia.org/wiki/Wichmann%E2%80%93Hill)，由 Brian Wichmann 和 David Hill 於 1982 年所提出的。將這三個 LCG 的結果進行 ++相加++ 後作為隨機數，該數列的週期為 $6.95 \times 10^{12}$。 :question: 考題中則對三個 LCG 進行異或操作得到隨機數，這個的週期又是多少呢？ ::: :::: ## 測驗 2 [平方根](https://hackmd.io/@sysprog/sqrt)是日常運算重要的一環，以下測驗為對其的探討: 首先討論計算前導零 (leading zero) 的實作 `cl2`，其使用遞迴手法呼叫。 ### clz2 `clz2` 的處理邏輯如下: 1. 將當前的數字以位元為單位，切成一半。 2. 若 upper 是 0，下一次檢查 lower 部分，且紀錄 ==upper 位元數 (16 >> c)== ^[1]^。 3. 直到剩下 ==2 個== 位元，回傳結果，結束遞迴呼叫。 以下程式實現以上邏輯: ```c static const int mask[] = {0, 8, 12, GGGG}; static const int magic[] = {HHHH, 1, 0, IIII}; 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 == JJJJ) return upper ? magic[upper] : KKKK + magic[lower]; return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL); } ``` 讓我們一行行解析: ```c if (!x && !c) return 32; ``` 若程式剛開始 ( `c` 是 `0` ) ，且 `x` 也是 `0`，直接返回全部都是 0 的前導零個數。 ```c uint32_t upper = (x >> (16 >> c)); uint32_t lower = (x & (0xFFFF >> mask[c])); ``` 創立兩個變數 `upper` 和 `lower`，`upper` 是將 `x` 右移 `(16 >> c)`，對於第一輪來說: ```c= uint32_t upper = (x >> (16 >> 0)) uint32_t lower = (x & (0xFFFF >> 0)); ``` 第 1 行將目前的數字左半部分右移，完全覆蓋掉右部分，以此得到 `upper`。 第 2 行就是僅保留下半部分。 若進一步思考在下一步，可以發現 `mask[c]` 在下一步 ( `c=1` )變成 `8`，再下一步會變成 `12`，這個規律是甚麼呢? 是**上次的位移量加上 `(16 >> c)`** ^[2]^ 。 因此我們可以推斷出 `mask[3]` 應該為 12 + 2 = 14。 ```c if (c == JJJJ) return upper ? magic[upper] : KKKK + magic[lower]; return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL); ``` 接下來最為精華的部分，首先是看到 `if` 分支，進入後回傳一個 ==固定的值== ( `magic` 必定是數值，沒有函式再被呼叫)，這也代表進入 `if` 後，流程就剩下一系列的返回階段了。而題目說明了結束條件: >遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。 說明當 `c` 與 `JJJJ` 相等剛好剩下 2 bits，結合上述提到: >若 upper 是 0，下一次檢查 lower 部分，且紀錄 ==upper 位元數 (16 >> c)== ^[1]^。 得知所求即 `(16 >> c) == 3`。故得知 `JJJJ`^[1]^。 **magic** 接著，我們先看 `if` 分支內，此時要返回 `upper`、`lower` ++各剩下兩個 bits 時的前導零數量++。 如果 `upper` 非 `0`，直接返回 `magic[upper]`，此時 `upper` 只可能有三種可能 ^[3]^ : - `0b01`: 有一個前導 `0`，對應到 `magic[1]` ➝ `1` - `0b10`: 沒有前導 `0`，對應到 `magic[2]` ➝ `0` - `0b11`: 沒有前導 `0`，對應到 `magic[3]` ➝ `0` ➝ `IIII` 那 `magic[0]` 呢? 我們知道該項只跟==三元運算符後半有關==，讓我們來思考甚麼時候會用 `magic[0]`。 只有一種，就是 `upper` 是 `0` (才會進入三元運算符的後半)，而 `lower` 也是 `0` (`magic` 的 index)，此時前導零數量為 `4` (剩下各兩 bits，都是 `0`) ^[4]^。 但應該要注意 `magic[0]` 不直接填 4 喔!!! 因為還有一項 `KKKK`，這項是常數代表的是 `upper` ==固定貢獻== 的前導零數量，也就是 `2` (才會進入後半部嘛!)。因此也能知道 `magic[0]` 也是 `2`。 :::warning :warning: `KKKK` 也可以做為常數加入 `magic` 陣列嗎? 不行! 因為 `upper` 非零時也會用到。 ::: **recursive function calls** 最後一部分，是遞迴呼叫 `clz2` 的過程: ```c return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL); ``` 當 `upper` 非零，計算 `upper` 的 `clz2` 並返回 ( `c + 1` 是要再把 `upper` 切一半)，若 `upper` 是零，則計算 `lower` 的 `clz2` 並加上 `upper` 全零的領導零數量( `16 >> c` )並返回。 由於 `lower` 也要切一半，所以 `LLLL` 同樣也是 `1` ^[5]^。 **Summary of clz2** 從上述可統整出以下資訊，++數字對應上方中的 ^[x]^++ : 1. `(16 >> c)` 是本輪切割完後的 bit 有多長。例如 `c` 是 `0` 時，則當輪分割完剩 16 bits。題目中提到==若位元剩兩位時==，結束繼續呼叫，對應到的是 `if (c == JJJJ)` 的判斷。 至此可以推斷 `JJJJ` 是當位元只剩下兩位時， `c` 的數值。僅 `c` 是 `3`，`(16 >> c)` 是 `2`，代表分割完就剩下兩位。故 `JJJJ` 是 `3`。 1. `mask` 陣列裡面放的數字，是 $mask[i] = mask[i-1] + (16 \gg c)$，其中 `mask[0]` 是 0。故 `GGGG` (`mask[3]`) 為 `14`。 1. 在進入 `if` 分支，若 `upper` 非 `0`，則只會有三種可能: `1`、`2`、`3`，對應的前導零數量為 `1`、`0`、`0`，其中最後一種可能對應到 `IIII`，故 `IIII` 為 `0`。 1. 只有當 `upper` 是 `0`，才可能會用到 `magic[0]`，且此時 `lower` 也是 `0`，所有 bits 都是 `0`，故知 `KKKK` 加上 `HHHH` 是 `4`。此處，`KKKK` 代表由全零的 `upper` 貢獻的前導 `0`，故 `KKKK` 是 `2`，因此 `HHHH` 也是 `2`。 1. 由於 `lower` 在遞迴中也要切一半，故 `LLLL` 是 `1`。 結束了嗎? 當然沒有，繼續看下去。 ### sqrti 可參考[〈2024-02-25 問答簡記〉](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg#%E6%AA%A2%E8%A8%8E%E7%AC%AC%E4%BA%8C%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C) 的第二週測驗題。 在一開始，利用剛剛實作的 `clz2` 實作 `clz64`: ```c #define clz32(x) clz2(x, 0) static inline int clz64(uint64_t x) { /* If the high 32 bits are nonzero, count within them. * Otherwise, count in the low 32 bits and add 32. */ return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32; } ``` `sqrti` 實作如下: ```c uint64_t sqrti(uint64_t x) { 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)) & MMMM; m = 1ULL << shift; while (m) { uint64_t b = y + m; y >>= NNNN; if (x >= b) { x -= b; y += m; } m >>= PPPP; } return y; } ``` 說明指出: >(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. 該要求表明 `PPPP` 要是偶數 (0, 2, 4, 6)，如何用 `&` 強制一個數字變成偶數呢?就是確保最低位是 `0`，因此 `PPPP` 的最簡表示為 `~1`。 剩下的 `NNNN` 和 `MMMM` 竟然要求是負數，暫時看不懂? :question: **Answers** - **GGGG**: 14 - **HHHH**: 2 - **IIII**: 0 - **JJJJ**: 3 - **KKKK**: 2 - **LLLL**: 1 - **MMMM**: - **NNNN**: - **PPPP**: ~1 ## 測驗 3 參考 [〈Linux 核心的 hash table 實作〉](https://hackmd.io/@sysprog/linux-hashtable) 了解完 Linux 中雙向鏈結串列的原理，沒想到在雜湊表的 Linux 實作上，也有它的身影!