---
tags: linux2025
---
# [2025q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 2 週測驗題
:::info
目的: 檢驗學員對[鏈結串列](https://hackmd.io/@sysprog/c-linked-list)、[雜湊表](https://hackmd.io/@sysprog/linux-hashtable)，及位元操作的認知
:::
==[作答表單: 測驗 `1` 和測驗 `2`](https://docs.google.com/forms/d/e/1FAIpQLSd9JhDDF42hntIRS9Zk0YFrcvrj9S3tzIZBm1UBsoRrQc9gLQ/viewform?usp=dialog)==
==[作答表單: 測驗 `3`](https://docs.google.com/forms/d/e/1FAIpQLSd9PfCvslu58tV9dS6OEZfteVP3ouwcqGeMxv8cVngZC4kyqQ/viewform?usp=dialog)==
### 測驗 `1`
我們使用 Linux 核心風格 List API 的簡化標頭檔 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 來開發快速排序程式碼。
首先定義結構體和比較用的函式：
```c
#include <stdint.h>
struct listitem {
uint16_t i;
struct list_head list;
};
static inline int cmpint(const void *p1, const void *p2)
{
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
```
預期開發的快速排序函式的原型宣告如下：
```c
static void list_quicksort(struct list_head *head);
```
接著準備測試用的輔助函式：
```c
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
static uint16_t values[256];
static inline uint8_t getnum(void)
{
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
s1 *= UINT16_C(171);
s1 %= UINT16_C(30269);
s2 *= UINT16_C(172);
s2 %= UINT16_C(30307);
s3 *= UINT16_C(170);
s3 %= UINT16_C(30323);
return s1 ^ s2 ^ s3;
}
static uint16_t get_unsigned16(void)
{
uint16_t x = 0;
size_t i;
for (i = 0; i < sizeof(x); i++) {
x <<= 8;
x |= getnum();
}
return x;
}
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;
}
}
```
以下是測試程式：
```c
int main(void)
{
struct list_head testlist;
struct listitem *item, *is = NULL;
size_t i;
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
INIT_LIST_HEAD(&testlist);
assert(list_empty(&testlist));
for (i = 0; i < ARRAY_SIZE(values); i++) {
item = (struct listitem *) malloc(sizeof(*item));
assert(item);
item->i = values[i];
list_add_tail(&item->list, &testlist);
}
assert(!list_empty(&testlist));
qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
list_quicksort(&testlist);
i = 0;
list_for_each_entry_safe (item, is, &testlist, list) {
assert(item->i == values[i]);
list_del(&item->list);
free(item);
i++;
}
assert(i == ARRAY_SIZE(values));
assert(list_empty(&testlist));
return 0;
}
```
預期執行時期不會遇到 [assert](https://man7.org/linux/man-pages/man3/assert.3.html) 錯誤。
相較於尋常的快速排序程式碼，我們希望排序結果是符合 stable sorting，以下是 `list_quicksort` 的程式碼 (部分遮蔽)：
```c
{
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);
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);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
DDDD(&pivot->list, head);
EEEE(&list_less, head);
FFFF(&list_greater, head);
}
```
補完程式碼，使其符合預期。
作答規範:
* AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF` 均為 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 定義的巨集或行內展開函式 (inline function) 名稱，可能的選項：
* `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`
* 以最精簡的方式撰寫，不包含空白
:::success
延伸問題：
* 解釋上方程式碼運作原理，改進 `random_shuffle_array` 也探討 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting
* 將程式碼整合進 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 提及的 `qtest`，並探討環狀雙向鏈結串列的排序效能，並善用 [perf](https://hackmd.io/@sysprog/linux-perf) 一類的效能分析工具，探討包含 Linux 核心 [list_sort](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 在內排序實作的效能表現並充分解釋
:::
---
### 測驗 `2`
以下針對 [從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)，嘗試開發整數的開平方根運算。
首先是 `clz2` 函式，其作用是藉由遞迴呼叫以計算 [count leading zero](https://en.wikipedia.org/wiki/Find_first_set) (clz)。每次呼叫 `clz2()` 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量。以下藉由一個數值（`0x0001F000`）來說明其步驟：
```plaintext
0x0001F000 = 0000 0000 0000 0001 1111 0000 0000 0000 ~2~
```
- [ ] Step 1
將此數值等分為兩部分：較高位（upper）與較低位（lower）。
| Upper | Lower |
|:--:|:--:|
| 0000 0000 0000 0001 | 1111 0000 0000 0000 |
- [ ] Step 2
此時，依據 `upper` 的數值判斷下一次遞迴呼叫應該處理哪一部分，以累計 leading zero 的數量。
- **若 `upper` 等於 `0`**，則下一次遞迴呼叫應檢查 `lower` 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 `upper` 位元數）。
- **若 `upper` 不等於 `0`**，則下一次遞迴呼叫應繼續檢查 `upper` 部分。
```plaintext
upper = 0000 0000 0000 0001
```
由於 `upper` 不為 `0`，下一次遞迴呼叫將繼續檢查 `upper` 部分的 leading zero。
- [ ] Step 3
遞迴呼叫 `clz2()` 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。
`clz2` 函式的實作如下： (部分遮蔽)
```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
#define clz32(x) clz2(x, 0)
```
參考執行輸出:
* 輸入: 0x00000F00，其 clz32 為 20
* 輸入: 0x00000001，其 clz32 為 31
我們可運用 `clz32` 建構 `clz64`:
```c
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;
}
```
最後實作整數開平方根： (部分遮蔽)
```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;
}
```
參考執行結果：
* 輸入: 63，得到 7
* 輸入: $2^{20}$，得到 1024
補完程式碼，使其符合預期。
作答規範:
* `GGGG`, `HHHH`, ..., `LLLL` 均為整數
* `MMMM`, `NNNN` 和 `PPPP` 為有效的 C 語言表示式，以最精簡的形式書寫
:::success
延伸問題：
1. 解釋上述程式碼，並探討擴充為 $\lceil \sqrt{x}) \rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
2. 參照[計算機結構測驗題 C](https://hackmd.io/@sysprog/arch2024-quiz3-sol#Problem-C) 及其[注釋](https://hackmd.io/@sysprog/HJKRbSAVJl#Problem-C30)，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 `sqrtf`，確保符合 IEEE 754 規格。對照 [sqrtf, rsqrt, reciprocal implementations in Arm assembly](https://github.com/picolibc/picolibc/issues/956)
3. 參照[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能
* 一旦發現效能改進的機會，可準備提交改進 `int_sqrt` 程式碼到 Linux 核心
:::
---
### 測驗 `3`
檢測學員對於 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)的認知。
[LeetCode](https://leetcode.com/) 編號 1 的題目 [Two Sum](https://leetcode.com/problems/two-sum/)，貌似簡單，作為 LeetCode 的開篇之題，乃是經典中的經典，正所謂「平生不識 [Two Sum](https://leetcode.com/problems/two-sum/)，刷盡 [LeetCode](https://leetcode.com/) 也枉然」，就像英語單詞書的第一個單詞總是 [Abandon](https://www.dictionary.com/browse/abandon) 一樣，很多沒有毅力堅持的人就只能記住這一個單詞，所以通常情況下單詞書就前幾頁有翻動的痕跡，後面都是[嶄新如初](https://en.wikipedia.org/wiki/Mint_condition)，道理不需多講，雞湯不必多灌，明白的人自然明白。
> 以上說法取自 [Two Sum 兩數之和](https://www.cnblogs.com/grandyang/p/4130379.html)
> [mint condition](https://en.wikipedia.org/wiki/Mint_condition): "mint" 除了薄荷的意思，還可指鑄幣廠，"mint condition" 裡的 “mint” 就與鑄幣廠有關。有些人收集錢幣會在錢幣剛開始發行時收集，因爲這樣的錢幣看起來很新，他們會用 "mint condition" 來形容這種錢幣的狀況，強調「像剛從鑄幣廠出來」，後來衍伸出「有如新一樣的二手商品」的意涵。
題意是給定一個陣列 `nums` 和一個目標值 `target`，求找到 `nums` 的 2 個元素相加會等於 target 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 `nums = [2, 7, 11, 15]`, `target = 9`，相加變成 `9` 的元素僅有 `2` 及 `7`，因此回傳這二個元素的索引值 `[0, 1]`
考慮以下 C 語言實作:
```cpp
#include <stdlib.h>
static int cmp(const void *lhs, const void *rhs) {
if (*(int *) lhs == *(int *) rhs)
return 0;
return *(int *) lhs < *(int *) rhs ? -1 : 1;
}
static int *alloc_wrapper(int a, int b, int *returnSize) {
*returnSize = 2;
int *res = (int *) malloc(sizeof(int) * 2);
res[0] = a, res[1] = b;
return res;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
*returnSize = 2;
int arr[numsSize][2]; /* {value, index} pair */
for (int i = 0; i < numsSize; ++i) {
arr[i][0] = nums[i];
arr[i][1] = i;
}
qsort(arr, numsSize, sizeof(arr[0]), cmp);
for (int i = 0, j = numsSize - 1; i < j; ) {
if (arr[i][0] + arr[j][0] == target)
return alloc_wrapper(arr[i][1], arr[j][1], returnSize);
if (arr[i][0] + arr[j][0] < target)
++i;
else
--j;
}
*returnSize = 0;
return NULL;
}
```
若用暴力法，時間複雜度為 $O(n^2)$，顯然不符合期待。我們可改用 [hash table](https://en.wikipedia.org/wiki/Hash_table) (以下簡稱 `HT`) 記錄缺少的那一個值 (即 `target - nums[i]`) 和對應的索引。考慮以下案例:
> nums = `[2, 11, 7, 15]`：
對應的步驟:
1. `nums[0]` 是 `2`，`HT[2]` 不存在，於是建立 `HT[9 - 2] = 0`
2. `nums[1]`是 `11`， `HT[11]` 不存在，於是建立 `HT[9 - 11] = 1`
3. `nums[2]` 是 `7`，`HT[7]` 存在 (設定於步驟 `1`)，於是回傳 `[2, HT[7]] = [2, 0]`
`hlist` 用於 hash table 的實作，它的資料結構定義在 [include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 中:
```cpp
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
示意如下:
`hlist` 的操作與 `list` 一樣定義於 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)，以 `hlist_` 開頭。`hlist_head` 和 `hlist_node` 用於 hash table 中 bucket 的實作，具有相同 hash value 的節點會放在同一條 `hlist` 中。 為了節省空間，`hlist_head` 只使用一個 `first` 指標指向 `hlist_node`，沒有指向串列尾節點的指標。
`hash table` 主要是由一個 `hlist_head` 的動態陣列所構成，每個 entry 指向一個由 `struct hlist_node` 構成的非環狀 doubly linked list ，hash table 長度依照 `bits` 給定，可知大小為 2 的冪。
而可以發現 `struct hlist_head` 只有一個 `struct hlist_node *` 的成員; 而 `struct hlist_node` 型態卻包含一個 `struct hlist_node *` 及 `struct hlist_node **` ，其中一個原因為 hash table 指向的為非環狀的 linked list ，因此只需指向 list 的一端點，若單純使用 `struct hlist_node` 當作 head ，無用的 "pprev" 會造成大量的記憶體空間浪費，因此將 head 與 node 分開來實作。
而 `struct hlist_node` 中的 pprev 為何使用「指標的指標」而非「指標」？ 回答這個問題前可以先參考 Linux 原始碼中 [type.h](https://elixir.bootlin.com/linux/v6.13.4/source/include/linux/types.h#L194-L204) ：
```c
struct list_head {
struct list_head *next, *prev;
};
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
可知在 type.h 中有兩種 list 的結構：
`struct list_head` 在 Linux 中實作為環狀 doubly-linked list，且可以在行程管理 (process scheduling) 的相關實作上看到，如 [sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h) 中有約 20 處使用到此結構，因可快速存取到頭以及尾的節點（時間複雜度 $O(1)$） 故有較好的效能，適用於行程管理這種對時間要求嚴謹的部分做使用。
引用自 linux [sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h)
```c=547
struct sched_entity {
/* For load-balancing: */
struct load_weight load;
struct rb_node run_node;
struct list_head group_node;
unsigned int on_rq;
...
}
```
struct `hlist_head` 搭配 `hlist_node`。在 Linux 核心中專門為了 hash table 而使用，`hlist_head` 的設計也省去了 list 起始端 `pprev` 的存放空間、在初始狀態就省去了一半的記憶體容量。而且同時 hash table 不會特別需要存取到 list 的尾端，並且走訪 list 相對沒那麼講求效率（因為 hash 的設計理念就是講求 hash collision rate 要低、因此一個 list 若太長比較需要改進的為 hash function 的設計而非改進整個資料結構）。綜合上述所說單向 list 已滿足 hash table 的需求。
**`pprev` 為何是「指標的指標」**？若和 `list_head` 一樣使用單純的指標( `hlist_node *`)，則考慮到 list 有方向性，delete node 時需要額外檢查其是否為 list 的 head 或是 NULL 等等，有較冗餘的程式碼必須實作，因此使用 `hlist_node **pprev` 直接存取上一個 node 所在的位址。Linux 為求程式碼簡潔故以 pointer to pointer 的方式用 `pprev` 直接指向前一個元素的記憶體位址本身。
以下是引入 [hash table](https://en.wikipedia.org/wiki/Hash_table) 的實作，學習 Linux 核心程式碼風格: (省略 hlist_{node,head} 及 `container_of` 的定義)
首先是結構體:
```c
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
初始化操作:
```c
map_t *map_init(int bits)
{
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
雜湊函數:
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
對應的檢索程式碼: (部分遮蔽)
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
新增操作： (部分遮蔽)
```c
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, BBBB)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
CCCC = &n->next;
h->first = n;
DDDD = &h->first;
}
```
釋放記憶體的操作:
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = EEEE;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
主體程式碼:
```c
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
goto bail;
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
補完程式碼，使其運作符合預期。作答規範：
* `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE` 皆為有效的 C 語言表示式
* 以最精簡的形式書寫，不包含空白
:::success
延伸問題：
* 解釋上述程式碼運作原理，應提供測試程式碼
> 針對 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)，提供更多圖例並揣摩 Linux 核心開發者
* 進行《[The Art of Computer Programming](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S
> 注意: Linux 核心內部大量使用 hash table，但並非每處的雜湊函數都滿足減少碰撞及避免 clustering 現象的原則，也就是存在若干改進空間
* 探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素
:::
Sign in with Wallet
Connect another wallet