# 2024q1 Homework2 (quiz1+2)
contributed by < [`56han`](https://github.com/56han/lab0-c) >
## 第 1 週測驗題
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
#### 1. 補完程式碼，使其得以符合預期運作
取得 `list` 尾端的 `node_t`，先確認是否 `left` 且 `left->next` 不為 `NULL`，若不為 `NULL` 則指標往下一個 `node_t` 指，即 `left->next`，最後跳出 while 迴圈時剛好會指到 tail。
```diff
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
- left = &(AAAA);
+ left = &((*left)->next);
return *left;
}
```
當 `left` 不為 `NULL` 時，持續往下一個 `node_t` 指，走完整個鏈結串列時，剛好可得鏈結串列長度。
```diff
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
- left = &(BBBB);
+ left = &((*left)->next);
}
return n;
}
```
`while` 迴圈持續往下一個指，將原本的鏈結串列分成 `> pivot` 和 `< pivot`，因此 `CCCC` 可填入 `n->next` 或 `p->next`。
接著判斷是否比 `pivot` 值還大，若有加入 `right` 鏈結串列，反之加入 `left` 鏈結串列。
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
使用 `begin[i]` 和 `end[i]` 紀錄 `left` 串列的頭、尾；
`begin[i+1]` 和 `end[i+1]` 紀錄 `pivot`；
`begin[i+2]` 和 `end[i+2]` 紀錄 `right` 串列的頭、尾。
這裡可以使用 `list_tail` 子函式，取得**尾端的節點**。
```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);
```
#### 2. 運作原理
使用鏈結串列實作 `quick sort`，實際上的鏈結串列如下，引用 [YangYeh-PD](https://hackmd.io/-iW9qu9MQYuaky39rwBi3A?view) 的畫法。
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph "queue"
{
rankdir = "LR"
subgraph "cluster node1"
{
node1_1[shape = record, label = "next"];
node1_2[shape = record, label = "value"];
node1_3[shape = record, label = "{<left> left |<right> right}"];
}
subgraph "cluster node2"
{
node2_1[shape = record, label = "next"];
node2_2[shape = record, label = "value"];
node2_3[shape = record, label = "{<left> left |<right> right}"];
}
subgraph "cluster node3"
{
node3_1[shape = record, label = "next"];
node3_2[shape = record, label = "value"];
node3_3[shape = record, label = "{<left> left |<right> right}"];
}
node1_1 -> node2_1;
node2_1 -> node3_1;
}
```
觀察程式碼可知，並沒有使用到 `left` 和 `right` ，因此可設計鍵結串列如下。
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "1"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
pivot -> struct0;
L -> struct0;
R -> struct4;
p -> struct1;
}
```
在上面的例子可以發現，當 4 是 pivot 時，
大於 pivot : 5
小於 pivot : 3， 2， 1
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left， n);
}
```
經過以上程式碼後，就會變成下圖。
```graphviz
digraph structs{
node[shape=plaintext];
left [fontcolor="blue"];
pivot [fontcolor="red"];
right [fontcolor="blue"];
node[shape=box]
struct0 [label= "4"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "1"];
pivot -> struct0;
left -> struct2;
struct2 -> struct3;
struct3 -> struct4;
right -> struct1;
}
```
觀察整個 `quick_sort()` 函式，發現：
1. 都是先檢查 `right` 串列是否還有需要排序(因為`i += 2;`)，再去檢查 `left` 。
>以上面例子來說， `right` 串列只有一個節點。因此將結果放入 `result` 串列中， `i--` 再去檢查 `pivot` 和 `left` 串列。
2. `begin` 和 `end` 使用了 2 倍的 `list_length` 空間，去記錄 `left` 和 `right` 串列中的頭尾。
3. `pivot` 都是取鏈結串列的第一個節點。
#### 3. 改進方案
* `begin` 和 `end` 是否真的需要 2 倍的 `list_length` 空間？
實際執行 `count` = `10` ~ `100000` ，觀察 `begin` 和 `end` 需要使用多大的空間。
```c
int main(int argc, char **argv)
{
node_t *list = NULL;
for (int i = 10; i < 1000000; i *= 10) {
printf("size : %d", i);
size_t count = i;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; i++)
test_arr[i] = i;
shuffle(test_arr, count);
while (count--)
list = list_construct(list, test_arr[count]);
quick_sort(&list);
assert(list_is_ordered(list));
list_free(&list);
free(test_arr);
}
return 0;
}
```
在 `begin[i+2]` 和 `end[i+2]` 後面加入
```c
if(i+2 > max_deep){
max_deep = i+2;
}
```
最後發現 `begin` 和 `end` 只需要 10x( 計算 size 是10的幾次方 ) 的空間，就足夠了。
```
size : 10, deepest level : 4
size : 100, deepest level : 14
size : 1000, deepest level : 26
size : 10000, deepest level : 38
size : 100000, deepest level : 48
```
* 每次都取第一個節點為 `pivot` ，當遇到已排序成 ascending /descending order 的鏈結串列時，就會成為 worst case，如何以別的方式挑選 `pivot` 以避免 worst case 的發生？
1. `rand()` 取一數，並和 `head` 做交換，取新的 `head` 當作 `pivot`
2. Median-of-three
#### 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列
>commit [9fdec7b](https://github.com/56han/Optimized_QuickSort/commit/9fdec7b8c333957883e06861eab276593f371d9b)
:::warning
TODO：提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
### 測驗 `2`
#### 1. 補完程式碼，使其得以符合預期運作
```diff
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
{
struct list_head *head;
- struct list_head **tail = AAAA;
+ struct list_head **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
- tail = BBBB;
+ tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
- tail = CCCC;
+ tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
```diff
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
- DDDD = head;
+ tail->next = head;
- EEEE = tail;
+ head->prev = tail;
}
```
```diff
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
stk_size = 0;
struct list_head *list = head->next, *tp = NULL;
if (head == head->prev)
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
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);
/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
- if (stk_size <= FFFF) {
+ if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
#### 2. 運作原理
`timsort` 函式：
* 一開始會先將雙向鏈結串列轉為**單向串列**。接著進入主要的迴圈，不斷呼叫 `find_run()` 找出下一個 run，並根據 run 的長度和目前的堆疊狀態，呼叫 `merge_collapse()` 觸發必要的合併。
* 當輸入串列掃描完畢後，函式會呼叫 `merge_force_collapse()` 強制合併所有剩餘的 run。
* 最後，根據堆疊的大小決定要呼叫 `build_prev_link()` 還是 `merge_final()` 來建立最終排序完成的雙向鏈結串列。
`merge` 函式：**合併兩個已經排序好的鏈結串列 `a` 和 `b`。**
>它會比較兩個串列的元素，較小的元素會被放在合併後的串列前面。如果兩個元素相等，為了保持穩定性(stability)，會優先選擇串列 `a` 的元素。
`build_prev_link` 函式：**重建雙向鏈結串列的 `prev` 指標。**
>從 `tail` 開始，調整每個節點的 `prev`，讓它指向前一個節點。最後再將頭尾兩端的 `prev` 和 `next` 指標連接起來，構成一個環狀的雙向鏈結串列。
`merge_final` 函式：**執行最後一次的合併，並建立完整的雙向鏈結串列。**
>函式會不斷比較 `a` 和 `b` 的元素，較小的會被連接到 `tail` 之後，調整對應的 `prev` 和 `next` 指標。一旦 `a` 或 `b` 的元素取完， 迴圈就會結束。最後，函式會呼叫 `build_prev_link()`，將 `b` 剩餘的元素全部接到 `tail` 之後，完成雙向鏈結串列的建立。
`find_run` 函式：**在未排序的鏈結串列中找出一段遞增或遞減的子串列(run)。**
>它會從 `list` 開始，比較相鄰元素的大小，決定目前的 run 是遞增還是遞減。對於遞減的 run， 函式會同時進行反轉，讓 run 變成遞增。函式會持續比較元素，直到不再滿足遞增/遞減的條件為止。
>最後回傳一個 `pair`，其中 `head` 指向 run 的起點， `next` 指向 run 結束後的下一個節點。函式還會在 run 的第二個節點的 `prev` 欄位中暫存 run 的長度。
`merge_at` 函式：**合併指定位置 at 後面的兩個鏈結串列。**
>首先計算要合併的兩個段的長度總和，然後呼叫 `merge()` 將它們合併。最後，它更新合併後的鏈結串列的長度訊息，將前一個節點的 next 指針指向合併後的鏈結串列，並減少堆疊的大小。
`merge_force_collapse` 函式：**在堆疊的 size >= 3 時，持續合併鏈結串列。**
>它比較 tp 前面兩個鏈結串列的長度，合併較小的那一個。這個過程會一直持續，直到堆疊的 size < 3。
`merge_collapse` 函式：**盡可能地將相鄰的較短鏈結串列合併，從而減少鏈結串列中節點的數量，提高逐一走訪的效率。**
確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
1. A 的長度 > B 的長度 + C 的長度。
2. B 的長度 > C 的長度。
>主要是根據堆疊中當前的鏈結串列的長度情況，來決定如何進行合併操作。它會根據以下條件來判斷：
>**條件一：**
>stack 的 size >= 3
>且 `tp->prev->prev` 的長度 <= `tp->prev` 的長度 + `tp` 的長度。
>**條件二：**
>stack 的 size >= 4
>且 `tp->prev->prev->prev` 的長度 <= `tp->prev->prev` 的長度 + `tp->prev` 的長度。
>**如果滿足條件一或條件二：**
如果 `tp->prev->prev` 較短，則呼叫 `merge_at(priv, cmp, tp->prev)` 合併 `tp->prev` 和 `tp->prev->prev`。
如果 `tp` 較短，則呼叫 `merge_at(priv, cmp, tp)` 合併 `tp` 和 `tp->prev`。
**如果上述兩個條件都不滿足：**
如果 `tp->prev` 較短，則呼叫 `merge_at(priv, cmp, tp)` 合併 `tp` 和 `tp->prev`。
如果 `tp` 較短，終止合併過程，返回 `tp`。
#### 3. 改進方法
* 原程式碼並無實作 Galloping mode
:::warning
TODO：實作 Galloping mode
:::
:::warning
TODO：將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
## 第 2 週測驗題
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
#### 1. 補完程式碼，使其得以符合預期運作
將新節點插入到雙向鏈結串列的 head 時，新節點的 next 指針應該指向的位置。因為我們是將新節點插入到 head，所以它的 next 應該指向原來的 head 節點。
```diff
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
- n->next = AAAA;
+ n->next = h->first;
n->pprev = &h->first;
h->first = n;
}
```
`hlist_for_each` 用於逐一走訪 hash table 中特定鏈結串列的 head 指標。`heads` 是一個 hash table 的 heads array，每個元素對應一個鏈結串列，而 `hash` 是根據給定值計算出的 hash values，用於確定逐一走訪哪個鏈結串列。
```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) {
- struct order_node *on = CCCC(p, struct order_node, node);
+ hlist_for_each (p, &heads[hash]) {
+ struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
獲取 hash table 中特定鏈結串列的 head 指標，用於將新節點插入到對應鏈結串列的 head。
```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]);
}
```
#### 2. 運作原理
此程式碼的用意是透過構建一個 hash table，有效地儲存和查詢 **inorder** 序列中的節點，從而加速以 preorder 和 inorder 序列重建二元樹的過程。
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
`hlist_node` 以圖像表示。
```graphviz
digraph G{
rankdir = LR;
splines = false;
node[shape = "record"]
node_1[label = "<m>hlist_node | {<p>pprev | <n>next}", group = list];
}
```
很多個 `hlist_node` 連接，則會形成下圖。
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
```c
struct hlist_head {
struct hlist_node *first;
};
```
`hlist_head` 以圖像表示。
```graphviz
digraph G{
rankdir = LR;
splines = false;
node[shape = "record"]
node_1[label = "<m>hlist_head | <f>first", group = list];
}
```
透過 `node_add` 函式：將 node 一個一個加入 hash table 中。
示意圖如下：引用 [ShchangAnderson](https://hackmd.io/OkL9VMRxS5-1dRUgiwiGgQ?view) 同學的圖。
```graphviz
digraph so
{
rankdir=TB
;
Array [ shape = record, label = "{ 0 | 1 | 2 | 3 |4 }"] ;
in_heads [shape= "none"]
in_heads -> Array [style=invis]
shape = "none"
inorder [label="Inorder:";shape="none"]
{rank=same inorder 9 3 15 20 7}
9 [shape = "none"]
3 [shape = "none"]
15 [shape = "none"]
20 [shape = "none"]
7 [shape = "none"]
inorder -> 9 -> 3 -> 15 -> 20 -> 7 [style=invis]
color = white;
}
```
-----------------
```graphviz
digraph so
{
rankdir=LR
;
{rank=same inh4 inh3 inh2 inh1 inh }
inh [label="in_heads[0]"; shape="none"]
inh1 [label="in_heads[1]"; shape="none"]
inh2 [label="in_heads[2]"; shape="none"]
inh3 [label="in_heads[3]"; shape="none"]
inh4 [label="in_heads[4]"; shape="none"]
15 [label="{val : 15 | Idx : 2}", shape="record"];
20 [label="{val : 20 | Idx : 3}", shape="record"];
7 [label="{val : 7 | Idx : 4}", shape="record"];
9 [label="{val : 9 | Idx : 0}", shape="record"];
3 [label="{val : 3 | Idx : 1}", shape="record"];
inh -> 20 -> 15
inh2 -> 7
inh3 -> 3
inh4 -> 9
}
```
建立完成 hash table 之後，呼叫 `dfs` 函式以深度優先搜尋往下尋找 root ，利用 `find` 函式找到 root 並且回傳 `idx` 值，即為 root 的位置。以 root 又可以切成左、右子樹，遞迴呼叫 `dfs` 函式。
引用 [ShchangAnderson](https://hackmd.io/OkL9VMRxS5-1dRUgiwiGgQ?view) 同學的圖。
```graphviz
digraph so
{
rankdir=TB
;
shape = "none"
inorder [label="Inorder:";shape="none"]
{rank=same inorder 9 3 15 20 7}
9 [shape = "none"]
3 [color=blue;shape = ""]
15 [shape = "none"]
20 [shape = "none"]
7 [shape = "none"]
inorder -> 9 -> 3 -> 15 -> 20 -> 7 [style=invis]
91 [label="9";shape = "none"]
31 [color=red;label="3";shape = "";]
151 [label="15";shape = "none"]
201 [label="20";shape = "none"]
71 [label="7";shape = "none"]
preorder [label="Preorder:";shape="none"]
{rank=same preorder 31 91 201 151 71}
preorder -> 31 -> 91 -> 201 -> 151 -> 71[style=invis]
31 -> 9 [style=invis]
}
```
-----------------
```graphviz
digraph so
{
rankdir=TB
;
shape = "none"
inorder [label="Inorder:";shape="none"]
{rank=same inorder 9 3 }
9 [color=red;shape = ""]
3 [color=red;label="15 20 7"shape = ""]
inorder
31 [color=blue;label="3";shape = "";]
31 -> 9
31 -> 3
}
```
------
:::warning
TODO：
1. 指出其中可改進之處並實作
2. 在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
:::
### 測驗 `2`
#### 1. 補完程式碼，使其得以符合預期運作
目的是在從 hash table 中刪除一個節點時，更新下一個節點的 pprev 指標，使其指向上一個節點的地址。
閱讀 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-hash-table-%E5%AF%A6%E4%BD%9C) 學到為何是 `*next` 和 `**pprev`。
```diff
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
- EEEE = pprev;
+ next->pprev = pprev;
}
```
釋放 LRU 快取實例所占用的記憶體。
```diff
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
- LRUNode *cache = list_entry(pos, LRUNode, FFFF);
- list_del(GGGG);
+ LRUNode *cache = list_entry(pos, LRUNode, link);
+ list_del(&cache->link);
free(cache);
}
free(obj);
}
```
從快取中獲取給定 key 對應的值，如果存在則返回該值，並將該節點移動到鏈結串列的頭部 (表示最近使用)；如果不存在則返回 -1。
```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;
}
```
將給定的 **鍵-值對** (key–value pair) 插入快取中。
Case 1：如果 **key 已存在**，則更新對應的值
Case 2：如果 key 不存在且**容量已滿**，則刪除鏈結串列尾部的節點(最久未使用)，然後插入新的鍵-值對。
Case 3：如果 key 不存在且**容量未滿**，則直接插入新的鍵-值對在鏈結串列的頭部。
**不管 key 是新的還是已存在，對應的節點都會被移動到鏈結串列的頭部。**
```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;
}
```
:::info
不理解第 20、21 行，實際上的意思是刪除第一個節點和加入新節點，但為甚麼 `hlist_del` 和 `hlist_add_head` 輸入參數都是 `&cache->node` ？
:::
#### 2. 運作原理
利用 `lRUCachePut` 及 `lRUCacheGet` 等函式實作 LRU (Least Recently Used) 快取的資料結構。LRU 快取是一種常用的快取演算法，它會根據資料的最近使用情況，自動釋放最久未使用的資料，以確保快取空間的有效利用。
**LRUCache 結構體**
引用 [vax-r](https://hackmd.io/VNAV9GIkRx6uFQVulRVe_w?view) 同學的圖
* `capacity` ：紀錄此 cache 最多能記錄幾筆資料
* `count` ：cache 當前紀錄的資料筆數
* `dhead` ：用來串接所有資料的雙向鍵結串列
* `hhead` ：處理碰撞使用的 `hlist` 結構體陣列
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
```graphviz
digraph structs{
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "LRUCache";
struct1 [label="capacity"];
struct2 [label="count"];
struct3 [label="dhead"];
struct4 [label="<head>hhead[0]|hhead[1]|...|hhead[capacity - 1]"];
struct3 -> struct3 [label="next"];
struct3 -> struct3 [label="prev"];
}
}
```
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
`hlist_node` 以圖像表示。
```graphviz
digraph G{
rankdir = LR;
splines = false;
node[shape = "record"]
node_1[label = "<m>hlist_node | {<p>prev | <n>next}", group = list];
}
```
很多個 `hlist_node` 連接，則會形成下圖。
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
#### 3.在 Linux 核心找出 LRU 相關程式碼
在 [Linus Torvalds 的 GitHub](https://github.com/torvalds/linux) 中可見，例如：`linux/mm/list_lru.c`。
以下程式碼主要是在處理 LRU list 時，將一個項目添加到特定節點的 LRU list中。
```c
bool list_lru_add(struct list_lru *lru, struct list_head *item, int nid,
struct mem_cgroup *memcg)
{
struct list_lru_node *nlru = &lru->node[nid];
struct list_lru_one *l;
spin_lock(&nlru->lock);
if (list_empty(item)) {
l = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(memcg));
list_add_tail(item, &l->list);
/* Set shrinker bit if the first element was added */
if (!l->nr_items++)
set_shrinker_bit(memcg, nid, lru_shrinker_id(lru));
nlru->nr_items++;
spin_unlock(&nlru->lock);
return true;
}
spin_unlock(&nlru->lock);
return false;
}
EXPORT_SYMBOL_GPL(list_lru_add);
```
:::warning
TODO：指出其中可改進之處並實作
:::
### 測驗 `3`
#### 1. 補完程式碼，使其得以符合預期運作
目的是找出 `word` 參數中最低位的1所在的位置（從0開始計算）。
```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;
}
```
計算出 bitmask，然後找到該位所在的字，最後使用 `*p &= ~mask;` 來清除該位。
```diff
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
- *p &= BBBB;
+ *p &= ~mask;
}
```
用於尋找第 `n` 個 bit 為1的索引。
```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; \
})
```
#### 2. 運作原理
此篇程式碼目的是在指定的記憶體空間找出第 N 個設定的位元。
```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);
}
```
:::info
不理解執行 find_nth_bit() 時，甚麼時候會需要 `return FIND_NTH_BIT(addr[idx], size, n);`
:::
用來檢查一個數字 `nbits` 是否 <= `BITS_PER_LONG` ，並且> 0 的常數。
>`__builtin_constant_p(nbits)` 是 GCC 提供的一個內建函數，用於在編譯時檢查 nbits 是否是一個已知的常數。
```c
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
用於生成一個 bitmask ，其中從第 `l` 位到第 `h` 位(含)的所有位都是1，其餘的位都是0。
>`(~0UL)`： 這表示一個 unsigned long 的值，其中所有位都是1。`~` 是反運算符，所以取反就是全部 bit 都為1。
>`(1UL << (l))`： 這將數值1(也是一個 unsigned long) 左移 `l` 位。左移操作會在右側補0，因此這個表達式生成了一個數，其中只有第 `l` 位是1，其餘位都是0。
```c
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
`fns` 函數的目的是找出 `word` 中第 `n` 個設定的位元。
>不斷呼叫 `__ffs` 來找到最低位元的1，如果那不是我們要找的位元，它就使用 `__clear_bit` 來清除這個位，然後繼續搜索下一個設置位。如果 `n` 等於0，意思是我們找到了想要的位元，所以它返回當前的 `bit`。
>如果 `word` 為0（即沒有更多設置位），則返回 `BITS_PER_LONG`，表示沒有找到。
```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;
}
```
計算出 bitmask，然後找到該位所在的字，最後使用 `*p &= ~mask;` 來清除該位。
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr); //只有第 nr 位是1，其他位都是0
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr); //計算某個位 nr 在一個 unsigned long 陣列中的哪個字
*p &= ~mask;
}
```
#### 3. 在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例
位於 `include/linux/cpumask.h` 的 [`cpumask_nth`](https://elixir.bootlin.com/linux/latest/source/include/linux/cpumask.h) 可以用來取得 cpumask 當中第 n 個 CPU。
>使用 `cpumask_bits(srcp)` 獲取 cpumask 以 bit 表示，然後使用 `small_cpumask_bits` 作為搜尋範圍的大小，最後通過 `cpumask_check(cpu)` 確保傳入的 CPU 編號是有效的。
```c
/**
* cpumask_nth - get the Nth cpu in a cpumask
* @srcp: the cpumask pointer
* @cpu: the Nth cpu to find, starting from 0
*
* Return: >= nr_cpu_ids if such cpu doesn't exist.
*/
static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
{
return find_nth_bit(cpumask_bits(srcp), small_cpumask_bits, cpumask_check(cpu));
}
```
Sign in with Wallet
Connect another wallet