# 2024q1 Homework2 (quiz1+2)
contributed by < `max890808` >
## [第一周測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 實作非遞迴 (non-recursive; iterative) 的快速排序法
#### 解釋程式碼運作原理
```c
node_t *begin[max_level], *end[max_level];
node_t *left = NULL, *right = NULL;
```
`begin` 和 `end` 用來紀錄比較的範圍
`left` 存放比 `pivot` 的 value 小的 node_t
`right` 存放比 `pivot` 的 value 大的 node_t
**圖解**
假設有一串列 [2, 0, 4, 1, 3] ，此時 i 為0 ，`left` 和 `right` 皆為NULL
```graphviz
digraph struct1 {
rankdir=TD;
pivot [fontcolor="red", shape=plaintext];
L [fontcolor="blue", shape=plaintext];
R [fontcolor="blue", shape=plaintext];
A[label = "2", shape=box];
B[label = "0", shape=box];
C[label = "4", shape=box];
D[label = "1", shape=box];
F[label = "3", shape=box];
G[label = "NULL", shape=plaintext];
{rank=same A B C D F G}
{rank=same pivot L R }
A->B->C->D->F->G;
pivot->A
L->A
R->F
}
```
遍歷整個串列，比 `pivot` 的 value 小的會被放入 `left` 串列，反之放入 `right` 串列
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph struct1 {
rankdir=TD;
left [fontcolor="blue", shape=plaintext];
pivot [fontcolor="red", shape=plaintext];
right [fontcolor="blue", shape=plaintext];
A[label = "2", shape=box];
B[label = "0", shape=box];
C[label = "4", shape=box];
D[label = "1", shape=box];
F[label = "3", shape=box];
{rank=same left pivot right}
{rank=same D A F}
{rank=same B C}
left->D->B;
pivot->A;
right->F->C;
}
```
更新 `begin` 和 `end`
```diff
begin[i] = left;
- end[i] = DDDD;
+ end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
- end[i + 2] = EEEE;
+ end[i + 2] = list_tail(&right);
```
```graphviz
digraph struct2 {
rankdir=TD;
begin [fontcolor="blue", shape=plaintext];
end [fontcolor="blue", shape=plaintext];
A[label = "2", shape=box];
B[label = "0", shape=box];
C[label = "4", shape=box];
D[label = "1", shape=box];
F[label = "3", shape=box];
E[label = "2", shape=box];
{rank=same begin end}
{rank=same A E}
{rank=same F C}
begin->D->A->F
end->B->E->C
}
```
進入下一次迭代，此時 i = 2
```graphviz
digraph struct3 {
rankdir=TD;
pivot [fontcolor="red", shape=plaintext];
L [fontcolor="blue", shape=plaintext];
R [fontcolor="blue", shape=plaintext];
NULL [shape=plaintext];
C[label = "4", shape=box];
F[label = "3", shape=box];
{rank=same pivot L R}
{rank=same C F NULL}
F->C->NULL
pivot->F
L->F
R->C
}
```
```graphviz
digraph struct4 {
rankdir=TD;
begin [fontcolor="blue", shape=plaintext];
end [fontcolor="blue", shape=plaintext];
A[label = "2", shape=box];
B[label = "0", shape=box];
C[label = "NULL", shape=box];
D[label = "1", shape=box];
F[label = "NULL", shape=box];
E[label = "2", shape=box];
G[label = "3", shape=box];
H[label = "3", shape=box];
I[label = "4", shape=box];
J[label = "4", shape=box];
{rank=same begin end}
{rank=same A E}
{rank=same F C}
{rank=same G H}
{rank=same I J}
begin->D->A->F->G->I
end->B->E->C->H->J
}
```
此時 `begin[4]` = 4 和 `end[4]` = 4, 不滿足 if 的條件，因此進行 else 的動作,透過 `list_add` 將 `begin[4]` 放入 `result` ，並將 `i` 減一
```c
if (L)
list_add(&result, L);
i--;
```
當索引 i 扣到小於 0 時，while 條件不成立跳出迴圈，完成排序，將 result 指派給 list
```graphviz
digraph struct1 {
rankdir=TD;
label="list";
A[label = "0", shape=box];
B[label = "1", shape=box];
C[label = "2", shape=box];
D[label = "3", shape=box];
F[label = "4", shape=box];
G[label = "NULL", shape=plaintext];
{rank=same A B C D F G}
A->B->C->D->F->G;
}
```
#### 使用Linux 核心風格的 List API 改寫上述程式碼
> commit [7ff3f48](https://github.com/max890808/Linux-homework/commit/7ff3f488bc2052605ed9ac7fa611a458335a1e9d)
將原本的結構體改為使用 `list_head`，詳細修改可以看 commit 紀錄
```diff!
typedef struct __node {
- struct __node *left, *right;
- struct __node *next;
+ struct list_head list;
long value;
} node_t;
```
#### 改進方案
* **max_level 大小**
原本的 `max_level` 為 `2 * list_legnth(list)` ，但最差的情況下只需要 `list_legnth(list) + 1` ，因此作以下修正：
```diff
- int max_level = 2 * n;
+ int max_level = n + 1;
```
* **移除 end[]**
`end[i]` 可由 `begin[i]->prev` 取得，因此不需要使用額外的儲存空間
```diff
- node_t *L = begin[i], *R = end[i];
+ struct list_head *L = begin[i]->next, *R = begin[i]->prev;
```
#### 避免最差狀況的快速排序
> commit [4644839](https://github.com/max890808/Linux-homework/commit/464483992175f2dd934526ea805f8a68b806ab8f)
最差的狀況會發生在 `Pivot` 恰好是該資料陣列的最小值或最大值，這裡的解決方式為 `Randomized Quick Sort` ，用亂數選取的方式，隨機挑一個值作為 `Pivot` ，並使用 `<time.h>` 比較最差狀況的結果
| 資料總數 | `quick_sort` 第一次 (s) | `quick_sort` 第二次 (s) | `quick_sort` 第三次 (s) | `quick_sort` 平均 (s) |`random_quick_sort` 第一次 (s) | `random_quick_sort` 第二次 (s) | `random_quick_sort` 第三次 (s) | `random_quick_sort` 平均 (s) |
| ------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| 1000 | 0.009 | 0.008 | 0.009 | 0.009 | 0.001 | 0.001 | 0.001 | 0.001 |
| 10000 | 0.600 | 0.621 | 0.578 | 0.600 | 0.005 | 0.006 | 0.006 | 0.006 |
| 100000 | 55.475 | 55.576 | 57.474 | 56.175 | 0.057 | 0.057 | 0.070 | 0.061 |
### 測驗二
Timsort 定義一個 `minrun` 控制每個 run 的長度，使 run 的數量等於或者略小於 2 的冪，這樣可以提高合併的效率。並且採用一組堆疊 (stack) 來暫存 run，避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。此外，透過 `merge_collapse` 函式確保 run 的長度，函式策略如下：
* A > B + C
* B > C
當不符合上述條件時，則會判斷 A 、C 大小，小的跟 B 合併。在合併兩個 run 時，Timsort 會有一個機制決定是否要啟動 `Galloping mode` 。
#### 解釋程式碼運作原理
```c
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
```
不斷呼叫 `find_run` 函式找出下一個 run，並根據 run 的長度和目前的堆疊狀態，呼叫 `merge_collapse()` 合併不滿足條件的 run。
```c
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= FFFF) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
使用 `build_prev_link()` 使原本單向串列成為環狀雙向鏈結串列，並透過 `marge_final()` 將最後兩段 run 進行合併。
#### 改進方案
* 實作 galloping mode 並加入 `MIN_GALLOP` 判斷 `galloping mode` 和 `one-pair-at-a-time mode`的使用時機
**TODO :**
* 實作改進方案
* 將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
## [第二周測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
Linux 核心的 hash table 與典型的雙向環狀鏈結串列不同，hash table 所使用的 pprev 宣告為指標的指標，這樣的好處為 `hlist_head` 僅需要保存一個指標，當 bucket 很大時，就能減少記憶體開銷。示意圖如下：
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
#### 解釋程式碼的運作
**`find`**
```diff
static int find(int num, int size, const struct hlist_head *heads)
{
struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
- hlist_for_each (p, BBBB) {
+ hlist_for_each (p, &heads[hash]) {
- struct order_node *on = CCCC(p, struct order_node, node);
+ struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
透過雜湊值和 `list_entry` 找出目標結構體的位置，回傳相對應 `idx` 值
**`node_add`**
```diff
static inline void node_add(int val,
int idx,
int size,
struct hlist_head *heads)
{
struct order_node *on = malloc(sizeof(*on));
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
- hlist_add_head(&on->node, DDDD);
+ hlist_add_head(&on->node, &heads[hash]);
}
```
計算雜湊值判斷要將節點加入到雜湊表的哪一位置
**`dfs`**
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
if (in_low > in_high || pre_low > pre_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
}
```
透過 `find` 函式找到目前 root 的 `idx` 值，分別將 preorder 和 inorder 切成 left, root 和 right 三部分，不斷的遞迴重複上述步驟直到 preorder 或 inorder 陣列長度為一
#### 測試程式
> commit [781cdee](https://github.com/max890808/Linux-homework/commit/781cdeec50a5173c5dd55f56d65186a1e93d7599)
修正版
> commit [30b0614](https://github.com/max890808/Linux-homework/commit/30b0614a2ecec78a043f1b732e18c38b768cc0db)
```diff
- preOrderTraversal(tree, check_pre);
+ preOrderTraversal(check_tree, check_pre);
- inOrderTraversal(tree, check_in);
+ inOrderTraversal(check_tree, check_in);
```
透過 `generateRandomTree()` 隨機生成一顆樹
```c
struct TreeNode* generateRandomTree(int height, int *number) {
if (height <= 0) {
return NULL;
}
struct TreeNode* root = createNode(rand() % 100);
number += 1;
root->left = generateRandomTree(height - 1, number);
root->right = generateRandomTree(height - 1, number);
return root;
}
```
`preOrderTraversal()` 和 `inOrderTraversal()` 負責找出前序和中序的陣列
```c
void preOrderTraversal(struct TreeNode* root, int* pre) {
if (root != NULL) {
*pre = root->val;
preOrderTraversal(root->left, pre+1);
preOrderTraversal(root->right, pre+1);
}
}
void inOrderTraversal(struct TreeNode* root, int* in) {
if (root != NULL) {
inOrderTraversal(root->left, in+1);
*in = root->val;
inOrderTraversal(root->right, in+1);
}
}
```
之後將前序和中序傳入 `buildTree()` 得到所要測試的樹，再透過 `preOrderTraversal()` 和 `inOrderTraversal()` 得到所要測試的樹的前序和中序陣列，最後比較一開始的前序和中序陣列是否相等就能完成測試
**TODO:**
1. 指出其中可改進之處並實作
2. 在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
### 測驗二
LRU(Least Recently Used Cache) 是一種快取的實做方式，概念是會儲存最近用過的內容，會透過 Hash Map 與 Double Linked List 來搭配實做，如果資料愈常被使用，資料會被擺在 List愈前方的位置，如果快取滿了，則會從 List 最末端元素開始移除。
因為 List 會從第一筆逐一查詢，所以查詢的時間複雜度為 O(N)，為了降低查詢時間，所以才搭配HashMap，在 HashMap中設置 key，讓 key 的內容對應到 List 中的元素，就可以讓查詢時間降低到 O(1)
#### 解釋程式碼的運作
**`LRUCache`**
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
`capacity:` 紀錄 cache 能存放的最大資料數
`count:` cache 當前的資料數
`dhead:` 資料的頭節點
`hhead[]:` 雜湊表
**`lRUCacheGet`**
```diff
int lRUCacheGet(LRUCache *obj, int key)
{
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *cache = list_entry(pos, LRUNode, HHHH);
+ LRUNode *cache = list_entry(pos, LRUNode, node);
if (cache->key == key) {
- list_move(IIII, &obj->dhead);
+ list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
計算 hash 值後，在對應的 `hhead[hash]` 所指向的鍵結串列進行搜索，若找到該節點回傳對應的值，並且透過 `list_move` 更新 `dhead`
**`lRUCachePut`**
```diff
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *cache = NULL;
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *c = list_entry(pos, LRUNode, JJJJ);
+ LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
- list_move(KKKK, &obj->dhead);
+ list_move(&c->link, &obj->dhead);
cache = c;
}
}
if (!cache) {
if (obj->count == obj->capacity) {
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
} else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
cache->key = key;
}
cache->value = value;
}
```
將新的資料放入快取當中，若資料已經在快取中，則使用 `list_move` 更新 `dhead`。若資料不在快取中且快取空間已滿，則會刪除最久沒被使用的資料，加入新的節點。若資料不在快取中且快取空間還沒滿，則配置新的記憶體空間並加入新節點。
**TODO:**
* 撰寫完整的測試程式，指出其中可改進之處並實作
* 在 Linux 核心找出 LRU 相關程式碼並探討
### 測驗三
#### 解釋程式碼的運作
**`hweight_long`**
```c
#define __const_hweight8(w) \
((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
(!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
(!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
(!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
#define __const_hweight16(w) (__const_hweight8(w) + __const_hweight8((w) >> 8))
#define __const_hweight32(w) \
(__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) \
(__const_hweight32(w) + __const_hweight32((w) >> 32))
static inline unsigned long hweight_long(unsigned long w)
{
return __const_hweight64(w);
}
```
計算 `w` 當中有幾個位元被設定
**`__ffs`**
```diff
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
- if ((word & AAAA) == 0) {
+ if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
#endif
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
找 `word` 第一個被設定的 bit 的位置
**`fns`**
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
透過 `__ffs` 函式得到第 N 個被設定的 bit 的位置
**`find_nth_bit`**
```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
{
if (n >= size)
return size;
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
return FIND_NTH_BIT(addr[idx], size, n);
}
```
透過 `small_const_nbits` 巨集判斷 `size` 的大小，若 `size` 小於 `BITS_PER_LONG` ，則運用 `fns` 函式找出第 N 個被設定的 bit 的位置，反之則會進入到 `FIND_NTH_BIT` 巨集
**`FIND_NTH_BIT`**
```diff
#define FIND_NTH_BIT(FETCH, size, num) \
({ \
unsigned long sz = (size), nr = (num), idx, w, tmp; \
\
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
\
- if (sz CCCC BITS_PER_LONG) \
+ if (sz % BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
每次迭代都計算 `FETCH` 的 `BITS_PER_LONG` 長度有幾個位元被設定，透過 `found` 找出目標答案
**TODO:**
* 在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。
Sign in with Wallet
Connect another wallet