# 2024q1 Homework2 (quiz1+2)
## quiz1 測驗一
:::success
1. 解釋程式碼的運作原理，提出改進方案並予以實作。
1. 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
### 運作原理
#### quick_sort
鏈結串列結構:
```clike
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph "struct __node"
{
node[shape=plaintext];
NULL[fontcolor="black"];
rankdir = "LR"
subgraph "cluster __node"
{
next [shape = box];
value[shape = box];
left_right [shape = record, label = "{<left> left |<right> right}"];
}
next -> NULL;
}
```
`L`:指向被排序的鍵結串列第一個節點
`R`:指向被排序的鍵結串列最後一個節點
`pivot` :指向被排序的鍵結串列第一個節點
用 `begin[]` 與 `end[]` 作為堆疊，用來紀錄比較的範圍
`begin[i]`:left 串列的第一個節點
`end[i]`:left 串列的最後一個節點
`begin[i+1]`: pivot 節點
`end[i+1]`: pivot 節點
`begin[i+2]`:right 串列的第一個節點
`end[i+2]`:right 串列的最後一個節點
**1. 選擇 `pivot`**
每次都選擇鏈結串列第一個節點作為 `pivot`
**2. 分割鏈結串列**
所有比 `pivot` 小的元素放在 L 串列，比`pivot`大的元素放在 R 串列
**3. 由 `begin[]` 與 `end[]` 的範圍進行排序**
每次都優先處理 R 串列去進行排序
直到 `beg[i] == end[i]` ，表示此串列中只有一個節點，就將該節點加入到 `result` 串列中。
以下方的鏈結串列為例:
```graphviz
digraph quick_sort_example{
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
NULL[fontcolor="black"];
p[fontcolor="black"];
node[shape=box];
{
rank="same";
rankdir=LR;
4->1->3->2->5->NULL;
}
pivot->4;
L->4;
p->1;
R->5;
}
```
`p` 依序走完鏈結串列，並分割鏈結串列，將所有比 `pivot` 小的元素放在 L 串列，比`pivot`大的元素放在 R 串列，如下圖:
```graphviz
digraph quick_sort_divide{
node[shape=plaintext];
R [fontcolor="blue"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
node[shape=box];
rankdir=LR;
L->1->3->2
pivot->4;
R->5;
}
```
更新 `begin[]` 與 `end[]` 的值，接著每次都優先處理 R 串列去進行排序，此時 `beg[i] == end[i]` ，表示 R 串列中只有一個節點，加入到 `result` 串列中第一個節點的位置
```graphviz
digraph result{
node[shape=plaintext];
result_head [fontcolor="red"];
node[shape=box];
result_head->5
}
```
接著 `i--`，此時`beg[i] == end[i]` ，`begin[i]` 與 `end[i]` 的值放的是 `pivot`，將 `pivot` 節點加入到 `result` 串列中第一個節點的位置
```graphviz
digraph result{
node[shape=plaintext];
result_head [fontcolor="red"];
node[shape=box];
{
rank="same";
rankdir=LR;
4->5;
}
result_head->4
}
```
接著 `i--`，開始處理 L 串列，進行排序直到整個串列排序完成。
### 改進方法
#### 縮減 begin[]的大小
#### 避免最差狀況的快速排序實作
**平均情況:**
快速排序的時間複雜度為 $O(nlogn)$
**最差情況:**
快速排序的時間複雜度為 $O(n^2)$，當排列的元素已經按照升序或降序排列，導致每次分割都只能減少一個元素。
所以選擇 `pivot` 很重要，希望每次都能將串列平均分割，避免最差情況的發生，我的作法是隨機選擇 `pivot`。
#### Linux 核心風格的 List API
在 `node_t` 結構中新增 `struct list_head list`，因 Linux List API 中 list_head 的結構中已經有 `prev` 和 `next` ，因此可以把 `node_t` 結構中的 `left`、`right`、 `next` 指標移除，另外因避免快速排序最差情況的發生，需再新增一個隨機選取 `pivot` 的函式 `rand_pivot()`。
```clike
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
在 `quick_sort()`中不需要 `end[]`，因 linux list 是雙向鏈結串列，查找最後一個只需要使用 `head->prev` 即可找到串列最後一個節點。
在 改寫 Linux 核心風格的 List API 時，發現在 `list_add` 時會發生 segamentation fault，進一步去檢查，發現在 `quick_sort` 中把 `pivot` 加入到 `begin[i+1]` 時發生錯誤，再重新審查一遍後發現是 `begin[]` 沒有去做 `list_new()`。
#### Linux 效能分析工具: Perf
效能測試上使用 `perf` 來分析選取 `pivot` 策略的差異，`perf` 是一個在 Linux 系统上用於性能分析的工具。`perf stat` 是一個用於監控和分析系統性能的命令。它的主要目的是執行指定的命令，並在命令執行期間保持對硬體和軟體事件發生的運行計數，並生成這些計數的統計信息。
硬體事件統計：CPU 迴圈數、快取命中率、指令執行次數等。
軟體事件統計：上下文切換次數、記憶體存取、I/O 處理時間等。
實驗分成最差情況和一般情況下隨機選取 `pivot` 和 直接選取鏈結串列的第一個節點作為 `pivot` 的差異，因一般情況下指令數以及耗費時間預計會高於最差情況下，因在排序前會先打亂陣列資料，主要比較隨機 `pivot` 和直接選取第一個節點的平均執行時間，和觀察兩者之間的差異，特別是在不同大小的輸入資料上。
每次執行效能測試前須清除快取
```shell
$ echo 3 | sudo tee /proc/sys/vm/drop_caches
```
執行效能測試
```shell
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./linux_qsort_no_rand_pivot
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./linux_qsort
```
重複執行 5 次該程序，並顯示每個 event 的變化區間。
觀察的 event 分別為 快取的命中率、快取的存取、指令數和執行的 cycle 數。
**worst case 的情況下(排序的順序為升序或降序)：**
:::spoiler **測試 100000 筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
17,1340 cache-misses # 7.08% of all cache refs ( +- 19.31% )
241,9193 cache-references ( +- 4.59% )
3,2687,3138 instructions # 2.56 insn per cycle ( +- 0.02% )
1,2752,6925 cycles ( +- 0.53% )
0.03275 +- 0.00447 seconds time elapsed ( +- 13.64% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
17,5439 cache-misses # 15.18% of all cache refs ( +- 19.82% )
115,5482 cache-references ( +- 0.18% )
3,6791,2078 instructions # 3.19 insn per cycle ( +- 0.02% )
1,1530,0504 cycles ( +- 1.76% )
0.02647 +- 0.00122 seconds time elapsed ( +- 4.59% )
```
:::
:::spoiler **測試 1000 筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
5820 cache-misses # 22.02% of all cache refs ( +- 28.89% )
2,6429 cache-references ( +- 4.96% )
3900,0168 instructions # 4.22 insn per cycle ( +- 0.02% )
924,3143 cycles ( +- 3.14% )
0.00822 +- 0.00137 seconds time elapsed ( +- 16.72% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
4940 cache-misses # 23.56% of all cache refs ( +- 40.92% )
2,0971 cache-references ( +- 7.79% )
380,2888 instructions # 2.31 insn per cycle ( +- 0.09% )
164,9545 cycles ( +- 2.61% )
0.00603 +- 0.00311 seconds time elapsed ( +- 51.58% )
```
:::
:::spoiler **測試 10筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
3549 cache-misses # 17.13% of all cache refs ( +- 41.67% )
2,0712 cache-references ( +- 2.02% )
103,6432 instructions # 1.23 insn per cycle ( +- 0.37% )
84,3458 cycles ( +- 0.97% )
0.0015844 +- 0.0000369 seconds time elapsed ( +- 2.33% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
4262 cache-misses # 19.76% of all cache refs ( +- 40.00% )
2,1571 cache-references ( +- 7.35% )
104,3593 instructions # 1.25 insn per cycle ( +- 0.41% )
83,4795 cycles ( +- 3.44% )
0.00492 +- 0.00288 seconds time elapsed ( +- 58.52% )
```
:::
---
**一般情況：**
:::spoiler **測試 100000 筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
18,6967 cache-misses # 7.09% of all cache refs ( +- 14.72% )
263,6204 cache-references ( +- 1.68% )
3,2716,9090 instructions # 2.56 insn per cycle ( +- 0.04% )
1,2779,8557 cycles ( +- 0.37% )
0.03144 +- 0.00288 seconds time elapsed ( +- 9.16% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
13,1878 cache-misses # 2.92% of all cache refs ( +- 31.84% )
452,2847 cache-references ( +- 2.92% )
3,7541,7692 instructions # 2.07 insn per cycle ( +- 0.01% )
1,8132,7720 cycles ( +- 0.65% )
0.04373 +- 0.00391 seconds time elapsed ( +- 8.93% )
```
:::
:::spoiler **測試 1000 筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
5773 cache-misses # 26.58% of all cache refs ( +- 30.05% )
2,1721 cache-references ( +- 4.27% )
360,6218 instructions # 2.15 insn per cycle ( +- 0.06% )
167,3905 cycles ( +- 1.24% )
0.0027962 +- 0.0000931 seconds time elapsed ( +- 3.33% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
4256 cache-misses # 18.23% of all cache refs ( +- 42.39% )
2,3345 cache-references ( +- 3.09% )
392,6116 instructions # 2.10 insn per cycle ( +- 0.04% )
187,4003 cycles ( +- 0.80% )
0.003057 +- 0.000155 seconds time elapsed ( +- 5.06% )
```
:::
:::spoiler **測試 10 筆資料**
```perf
Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):
4312 cache-misses # 23.12% of all cache refs ( +- 40.36% )
1,8653 cache-references ( +- 5.29% )
103,6244 instructions # 1.23 insn per cycle ( +- 0.16% )
84,0002 cycles ( +- 3.29% )
0.0012722 +- 0.0000279 seconds time elapsed ( +- 2.19% )
```
```perf
Performance counter stats for './linux_qsort' (5 runs):
4039 cache-misses # 19.44% of all cache refs ( +- 36.90% )
2,0777 cache-references ( +- 2.39% )
103,2732 instructions # 1.16 insn per cycle ( +- 0.17% )
88,8412 cycles ( +- 3.26% )
0.001064 +- 0.000126 seconds time elapsed ( +- 11.84% )
```
:::
---
**最差情況**
| 輸入資料大小 | 100000 | 1000 | 10 |
| --------------------------- | --------- | ---- | --- |
| **選取第一個節點作`pivot`** | 0.03275 s | 0.00822 s |0.0015844 s |
| **隨機選取節點作`pivot`** | 0.02647 s | 0.00603 s| 0.00492 s|
**一般情況**
| 輸入資料大小 | 100000 | 1000 | 10 |
| --------------------------- | --------- | ---- | --- |
| **選取第一個節點作`pivot`** | 0.03144 s | 0.0027962 s | 0.0012722 s |
| **隨機選取節點作`pivot`** | 0.04373 s | 0.003057 s| 0.001064 s|
**總結：**
* 隨機 `pivot` 可以減少最壞情況下的執行時間，因為它避免了選擇最差的 `pivot`。
* 直接選取第一個節點的方法簡單，但在已排序情況下導致效能下降。
* 選擇 `pivot` 的方法和數據的特性（例如數據是否已經部分排序）可能會影響 `quick_sort` 的效率。因此，在使用 `quick_sort` 時，選擇合適的 `pivot` 選擇策略是很重要的。
## quiz1 測驗二
:::success
1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
2. 將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
### 運作原理
**主要想法:**
想要利用資料中已存在排序好的子序列來最小化比較和交換的次數。
Tim Peter發現在現實世界中，許多資料都是由部分排序好的序列組合而成。他提出的策略是先找出這些已排序的子序列（也就是所謂的`run`），然後透過不斷合併這些子序列來完成整個資料範圍的排序。儘管在處理隨機資料時，Timsort的效能稍遜於理論上的極限值$O(nlogn)$，但對於部分已排序的資料，其表現卻相當出色。
Timsort的改進主要集中在三個方面：
1. 加快合併過程。
2. 減少合併的次數。
3. 在某些情況下尋找比合併排序更有效的排序方法。
Timsort 使用一組堆疊 (stack) 來存儲run，這樣做是為了減少掃描整個資料範圍以產生run所需的記憶體開銷。在這個過程中，Timsort使用`merge_collapse`函式來確保堆疊上的run長度保持平衡。該函式主要檢查堆疊頂端的3個run是否滿足以下原則：
* A的長度要大於B和C的長度總和。
* B的長度要大於C的長度。
如果不符合這些條件，函式將決定是否進行合併。這樣做確保了堆疊中run的長度平衡，並且由於合併只能在相鄰的兩個run之間進行，以確保排序的穩定性，因此合併操作僅可能採取A和BC 以及 AB和C 兩種形式。這使得Timsort在執行時能夠兼顧高效和穩定性。
例如，考慮 3 段 run: A 的長度為 30，B 的長度為 20，C 的長度為 10，由於 A 的長度不大於 B 加 C 的總和（亦即 $A<=B+C$），且 C 的長度小於 A，因此會選擇將 C 與 B 進行合併，形成兩個新的 run
* A: 30
* BC: 30
藉此，不僅確保堆疊中 run 的長度平衡，且因合併只能在相鄰的兩個 run 間進行，以確保排序的穩定性，因此合併操作僅可能採取 $A+(B+C)$ 或 $(A+B)+C$ 的形式進行。此舉讓 Timsort 在執行時兼顧高效又穩定。
處理相鄰子序列的合併過程中，直接在記憶體中進行操作會面臨挑戰，因為大量的記憶體操作不僅難以實作，效率也未必理想。因此，Timsort採用了使用臨時記憶區的策略，其大小設定為兩個子序列（A、B）中較短者的長度。
當A的長度小於B時，會先將A序列暫存。一種直觀的合併方法是從A和B的開頭開始進行逐對比較，將較小的元素放置於A的原位置，這一過程持續進行直到A和B完全排序，類似於經典的合併排序，也稱為逐對合併（one-pair-at-a-time）。
然而，考慮到A和B都是已排序的序列，可以進一步改進：首先尋找B的首個元素（即B[0]）在A中的排序位置，這樣就能確定A中有一段是小於B[0]的，可以將這部分元素放回A。接著，尋找剩餘A的首個元素在B中的位置，如此反覆進行，直到完成排序。這種方法被稱為Galloping mode。
例如，考慮以下情況：
A: [3, 5, 7, 9, 11]
B: [6, 8, 10, 12, 13, 17]
顯然A較短，因此先將A放入暫存記憶區`temp`。然後找到B[0]在A中的位置，即A[1]和A[2]之間，因為B[0]=6，所以A[0] 到 A[1] 都可以直接放回A序列。然後，將`temp`的首個元素放到B中適當的位置，如此反覆進行。
這種改進方案在大多數情況下效果顯著，但對於隨機資料序列而言，可能比逐對合併更慢。因此，在Timsort中有一個機制決定是否要啟動Galloping mode。
相對於合併排序，Timsort的改進包括：
* 降低快取失效（cache miss）
* 減少記憶體開銷
* 降低比較次數
傳統的合併排序會從合併樹的最底層開始合併，這導致每進行一層的合併就要掃過整個序列，這對快取不友好。Timsort優化了這一點，利用Galloping mode和臨時記憶區的策略，在適當時機進行合併，從而降低快取失效和記憶體開銷，同時減少比較次數，提高了效率。
#### **Galloping mode**
在Timsort中，當資料呈現非均勻分布且存在叢集(Clusters)特性時，會啟用Galloping演算法。初始時無法得知資料分布情況，但在使用傳統的「逐對比較」方式時，若連續進行多次比較都來自同一個Run，就會推測資料可能具有叢集特性，進而切換至Galloping模式。判斷是否切換的條件是有一個名為`MIN_GALLOP`的常數，默认值為7，即當進行了7次連續比較，且來自同一個Run時，就會啟動Galloping模式。一旦進入Galloping模式，如果從同一個Run找到的連續資料次數小於`MIN_GALLOP`，則會回到傳統的「逐對比較」模式。
Galloping Mode：
* 進入 Galloping 模式時，Timsort 需要不斷尋找某個數字在已排序陣列中的位置。
* 假設 A 是較短的序列，我們要找 A[0] 在 B 序列中應排序的位置。
* 傳統的二分查找是一種選擇，但 Timsort 使用了另一種演算法，稱為 Galloping Search（也稱為指數搜尋）。
* Galloping Search 透過跳躍式地尋找，更快地確定 B[0] 在 A[0] 中的位置，從而將整個 A 的一部分移動到正確的位置。
**1. 初始化堆疊大小**
`stk_size` 被設置為 0，用來紀錄堆疊中的 `run` 數量
**2. 建單向鏈表**
如果 `head == head->prev`，那麼函數將返回。
否則，它將把雙向鏈表轉換為單向鏈表。
**3.找到下一個 `run` 並合併**
在一個循環中尋找下一個 `run` (`find_run` 函數來完成)，並在每次找到一個 `run` 時合併它 (`merge_collaps` 來合併)。
**4. 強制合併所有 `run`**
當所有的輸入都被處理後，將強制合併所有剩餘的 `run` (`merge_force_collapse` 來強制合併)。
**5. 最終合併並重建鏈接**
最終的合併(merge_final )，並重建雙向鏈表的鏈接(build_prev_link)。
## quiz2 測驗一
:::success
1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
:::
### 運作原理
* 建立一棵二元樹的，使用了前序(preorder)和中序(inorder)來建立這棵樹。
* 透過前序遍歷可以確定節點的上下關係（越前面的越在上面），而中序遍歷可以確定節點的左右關係（越前面的越在左邊）
* 利用前序遍歷的第一個元素來確定根節點的值，並在中序遍歷中找到該元素，將其左邊的元素視為左子樹，右邊的元素視為右子樹。
結構:
```clike
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
```
這邊的 `pprev` 宣告為指標的指標
可以發現:
* 只有鏈結串列的尾端指標內容是 NULL。
* next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標。
這樣設計的好處是，當需要刪除的節點是第一個節點時，可以直接透過 `*pprev = next` 來修改指標的指向。
另外，hlist 是一種特別針對雜湊表設計的鏈結串列。雖然雙向鏈結串列也可以用來實作雜湊表，但因為需要在開頭和結尾各使用 2 個指標，所以在 bucket 很大的情況下，會增加記憶體的使用量。
```graphviz
digraph "struct hlist_node"
{
rankdir = "LR"
node[shape = record];
hlist_head[label = "<m>hlist_head | <n>first", group = list]
hlist_node1[label = "<m>hlist_node1| {<p> pprev |<n> next}", group = list];
hlist_node2[label = "<m>hlist_node2| {<p> pprev |<n> next}", group = list];
NULL[label = "NULL", shape = plaintext ,fontcolor = "black", group = list];
{rank = "min" hlist_head}
hlist_head -> hlist_node1 -> hlist_node2[
weight = 10, style = invis
]
hlist_node1 : p -> hlist_head : n
hlist_head : n -> hlist_node1 : m
hlist_node1 : n -> hlist_node2 : m
hlist_node2 : p -> hlist_node1 : n
hlist_node2 : n -> NULL
}
```
**`struct TreeNode`**:
二元樹節點的結構，包含一個整數值和兩個指向左右子節點的指標。
**`struct order_node`**：
用於存儲數字和其在陣列中的索引。它還包含一個 `hlist_node` 結構，用於將 `hlist_node` 添加到雜湊表中。
**`hlist_add_head`**：
將一個節點添加到雜湊表的頭部。
**`find`**：
在雜湊表中查找一個數字並返回其在中序的索引。如果找不到該數字，則返回-1。
**`dfs`**：
一個遞迴函數，用於建立二元樹。它先建立一個新的節點，然後在中序遍歷的結果中找到該節點的值，利用前序遍歷的第一個元素來確定根節點的值，並在中序遍歷中找到該元素，將其左邊的元素視為左子樹，右邊的元素視為右子樹，並以此劃分左右子樹。然後對左右子樹進行遞迴調用。
```clike
//左子樹
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);
```
以下方 preorder[], inorder[] 為例:
| preorder[0] | preorder[1] | preorder[2] | preorder[3] | preorder[4] | preorder[5] |
|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|
| 3 | 9 | 12 | 20 | 15 | 7 |
| inorder[0] | inorder[1] | inorder[2] | inorder[3] | inorder[4] | inorder[5] |
|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|
| 12 | 9 | 3 | 15 | 20 | 7 |
root = 3，其對應中序的索引為 2，
其左右子樹的範圍便是
| 左子樹 | 右子樹 |
| ------------------------------ | ------------------------------- |
| inorder[in_low]~inorder[idx-1] | inorder[idx+1]~inorder[in_high] |
| inorder[0] ~inorder[1] | inorder[3]~inorder[5] |
對應回前序，其左右子樹的範圍便是
| 左子樹 | 右子樹 |
| ------------------------------ | ------------------------------- |
| preorder[pre_low+1]~preorder[pre_high- (idx-in_low)] | preorder[pre_high -(idx-in_low)+1]~preorder[pre_high] |
| preorder[1]~preorder[2] | preorder[3]~preorder[5] |
```clike
//左子樹
tn->left = dfs(preorder, 1, 2, inorder, 0, 1, in_heads, size);
//右子樹
tn->right = dfs(preorder,3 , 5, inorder,3, 5, in_heads, size);
```
**`buildTree`**：
用於建立二元樹。藉由呼叫 `node_add` 函式將 `inorder` 的節點建立一個雜湊表(雜湊函式為 :` |val| % inorderSize`。最後，它調用 `dfs` 函數來建立二元樹。
為了能快速找到值所對應中序的索引，我們建立一個雜湊表加快查詢，以值為3為例，當我們要找值為3其在中序的索引，我們會遍歷 `hash = 3 % 5` ->heads[3]，第一個便是我們所要找的節點。
```graphviz
digraph hash {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.8,height=.1];
hash [label = "<th>heads[hash] | <f0>heads[0] |<f1>heads[1] |<f2>heads[2] |<f3>heads[3] |<f4>heads[4] ",height=2.5];
node [width=0.8];
node0 [label = "{<n> 20 }"];
node1 [label = "{<n> 15 }"];
node2 [label = "{<n> 7 }"];
node3 [label = "{<n> 12 }"];
node4 [label = "{<n> 3}"];
node5 [label = "{<n> 9}"];
NULL1, NULL2, NULL3 ,NULL4[shape=plaintext,label="NULL"];
hash:f0 -> node0:n -> node1:n -> NULL1;
node1:n -> node0:n -> hash:f0;
hash:f2 -> node2:n -> node3:n -> NULL2;
node3:n -> node2:n -> hash:f2;
hash:f3 -> node4:n -> NULL3;
node4:n -> hash:f3;
hash:f4 -> node5:n -> NULL4;
node5:n -> hash:f4;
}
```
### Linux 核心的 cgroups 相關原始程式碼
在 [linux/kernel/cgroup/cgroup.c](https://github.com/torvalds/linux/blob/master/kernel/cgroup/cgroup.c) 中 `css_next_descendant_pre` 利用 pre-order walk 來尋找下一個後代。 `css_for_each_descendant_pre` 會使用 `css_next_descendant_pre` 尋找下一個後代，來進行 pre-order traversal 。
**`css_next_descendant_pre`**:
```clike
struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
struct cgroup_subsys_state *root)
{
struct cgroup_subsys_state *next;
cgroup_assert_mutex_or_rcu_locked();
/* if first iteration, visit @root */
if (!pos)
return root;
/* visit the first child if exists */
next = css_next_child(NULL, pos);
if (next)
return next;
/* no child, visit my or the closest ancestor's next sibling */
while (pos != root) {
next = css_next_child(pos, pos->parent);
if (next)
return next;
pos = pos->parent;
}
return NULL;
}
```
這個函式主要用於在樹中進行深度優先搜索，直到遍歷完整棵樹為止。
## quiz2 測驗二
:::success
1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心找出 LRU 相關程式碼並探討
:::
### 運作原理
* LRU 緩存（Least Recently Used）是一種常見的緩存演算法，當緩存達到其容量時，會先淘汰最長時間未被訪問的數據。
**結構:**
**`list_head`**:
雙向鏈表用於實現 LRU 策略
**`hlist_head`,`hlist_node`**:
用於雜湊表，雜湊表則用於快速查找鍵值。
**`LRUNode`**：
每個節點包含一個鍵（key）、一個值（value）、一個雜湊表節點（hlist_node）和一個雙向鏈表節點（list_head）。
**`LRUCache`**：
主要的緩存結構，包含緩存的容量（capacity）、當前的數量（count）、一個雙向鏈表頭（dhead）和一個雜湊表頭陣列（hhead）。
```clike
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct list_head {
struct list_head *next, *prev;
};
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
**hlist_head 和 hlist_node 結構:**
```graphviz
digraph "struct hlist"
{
rankdir = "LR"
node[shape = record];
hlist_head[label = "<m>hlist_head | <n>first", group = list]
hlist_node1[label = "<m>hlist_node1| {<p> pprev |<n> next}", group = list];
hlist_node2[label = "<m>hlist_node2| {<p> pprev |<n> next}", group = list];
NULL[label = "NULL", shape = plaintext ,fontcolor = "black", group = list];
{rank = "min" hlist_head}
hlist_head -> hlist_node1 -> hlist_node2[
weight = 10, style = invis
]
hlist_node1 : p -> hlist_head : n
hlist_head : n -> hlist_node1 : m
hlist_node1 : n -> hlist_node2 : m
hlist_node2 : p -> hlist_node1 : n
hlist_node2 : n -> NULL
}
```
**list_head 結構:**
```graphviz
digraph "struct list_head"
{
rankdir = "LR"
node[shape = record];
list_head[label = "<m>list_head | {<p> prev |<n> next}", group = list];
rank="same"
list_head : n :e-> list_head:e ;
list_head : p :w-> list_head:w;
}
```
**LRUCache 結構:**
```graphviz
digraph "struct LRUCache"
{
node[shape=plaintext];
rankdir = "LR"
subgraph "cluster __node"
{
capacity [shape = box];
count[shape = box];
node[shape = record];
list_head[label = "<m>dhead | {<p> prev |<n> next}", group = list];
hlist_head[label = "<m>hhead[] |first ", group = list]
}
}
```
**LRUNode 結構:**
```graphviz
digraph "struct LRUNode"
{
node[shape=plaintext];
rankdir = "LR"
subgraph "cluster __node"
{
key [shape = box];
value [shape = box];
node[shape = record];
hlist_head[label = "<m>link |first ", group = list]
list_head[label = "<m>node | {<p> prev |<n> next}", group = list];
}
}
```
**`lRUCacheCreate`**：
用於創建一個新的 LRU 緩存，並初始化其容量和數量。
**`lRUCacheFree`**：
用於釋放 LRU 緩存的所有節點和緩存本身。
**`lRUCacheGet`**：
用於獲取指定 key 的 value。如果找到 指定 key，則將其對應的節點移到雙向鏈表的頭部，並返回其值。
**`lRUCachePut`**：
用於增加或更新一個鍵值對。如果鍵已經存在，則更新其值並將其節點移到雙向鏈表的頭部。如果鍵不存在，則建立一個新的節點，並將其添加到雙向鏈表的頭部和雜湊表中。如果此時緩存已滿，則還需要從雙向鏈表的尾部淘汰一個最近最少使用的節點。
`lRUCacheGet` 和 `lRUCachePut` 的時間複雜度都是 O(1)。這是因為雜湊表可以在常數時間內完成查找操作，而雙向鏈表可以在常數時間內加入、刪除和移動節點的操作。這對於需要快速響應的緩存系統來說非常重要。
## quiz2 測驗三
:::success
1. 解釋上述程式碼的運作原理
2. 在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。
:::
### 運作原理
* 用來操作位元組（bit）
**`BITMAP_LAST_WORD_MASK(nbits)`**:
產生一個遮罩，該遮罩的最後 nbits 位元為 0，其餘位元為 1。
**`BIT_MASK(nr)`**:
產生一個遮罩，該遮罩的第 nr 位元為 1，其餘位元為 0。
**`BIT_WORD(nr)`**:
計算第 nr 位元所在的 word 的索引。
**`__const_hweight8(w), __const_hweight16(w), __const_hweight32(w), __const_hweight64(w)`**:
計算一個 8 位元、16 位元、32 位元或 64 位元的數字中，有多少位元為 1。
**`hweight_long(w)`**:
計算一個長整數中，有多少位元為 1。
**`__ffs(word)`**:
找出一個字中，最低位的 1 在哪一位。
**`__clear_bit(nr, addr)`**:
清除位址 addr 中的第 nr 位元。
**`fns(word, n)`**:
找出一個字中，第 n 個 1 在哪一位。
**`find_nth_bit(addr, size, n)`**:
在一個記憶體區域中，找出第 n 個 1 的位元位置
## Reference
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
[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)
[Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
Sign in with Wallet
Connect another wallet