# 2024q1 Homework2 (quiz1+2)
contributed by < `yinghuaxia` >
## 第一週測驗
[題目](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
這個題目想透過非遞迴的方式實作 [quick sort](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwiYrtXkyt6EAxUeoK8BHaJWCK4QFnoECBQQAQ&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FQuicksort&usg=AOvVaw3DF_aFhNjU5vDr6xBl6cSy&opi=89978449)。根據 [Optimized QuickSort -- C Implementation (Non Recursive)](https://alienryderflex.com/quicksort/) ，陣列版本的 quick sort 的流程如下圖所示：
決定 pivot 之後，分別用 L、R 兩個指標從左右兩邊遍歷陣列。如果 L 指到的元素數值比 pivot 的數值大，則將其數值複製到當前 R 指向的位置；如果 R 指到的元素數值比 pivot 的數值小，則將其數值複製到當前 L 指向的位置，在 L、R 指向同一個位置時，就將 pivot 置於該位置，完成第一次位置的更新，再繼續下一輪的位置替換動作。然而在我們的例子中，L 和 R 會是兩個串列，將 L、R 遍歷到的節點存入串列中，搭配 `begin[]` 和 `end[]` 指向 L、R 串列的頭和尾，定義下一次排序的起始與終止節點。
* 選擇最左邊的節點作為 pivot
```graphviz
digraph name{
node[shape=box]
rankdir = LR
n1[label=4]
n2[label=1]
n3[label=3]
n4[label=5]
n5[label=2]
n6[label=7]
NULL[label=NULL,shape=plaintext]
n1 -> n2 -> n3 -> n4 -> n5 -> n6 ->NULL
{
rank="same";
L[label="L", shape=plaintext, fontcolor=red]
pivot[label="pivot", shape=plaintext, fontcolor=blue]
pivot -> n1[color=blue]
L -> n1[color=red];
}
{
rank="same";
R[label="R",shape=plaintext,fontcolor=red]
R->n6[color=red];
}
}
```
* 將 L 指標向右遍歷串列，如果值比 pivot 小，則將其加到 L 串列底下；將 R 指標向左遍歷串列，如果值比 pivot 大，則將其加到 R 串列底下。L 和 R 指到同一個位置時停止。
```graphviz
digraph name{
node[shape=plaintext];
left [fontcolor="red"];
pivot [fontcolor="blue"];
right [fontcolor="red"];
node[shape=box]
n1 [label= "4"];
n2 [label= "7"];
n3 [label= "2"];
n4 [label= "3"];
n5 [label= "1"];
n6 [label= "5"];
pivot -> n1;
left -> n3;
n3 -> n4;
n4 -> n5;
right -> n2;
n2 -> n6
}
```
* 更新 begin 和 end 串列
```graphviz
digraph name{
rankdir = LR;
node[shape=box]
n1 [label= "4"];
n2 [label= "7", color = "red"];
n3 [label= "2", color = "red"];
n4 [label= "3"];
n5 [label= "1", color = "blue"];
n6 [label= "5", color = "blue"];
n3 -> n4 -> n5;
n2 -> n6;
{
rank = "same";
node[shape=plaintext];
begin_0 [label = "begin[0]", fontcolor="red"];
begin_0 -> n3;
}
{
rank = "same";
node[shape = plaintext];
end_0 [label = "end[0]", fontcolor = "blue"]
end_0 -> n5
}
{
node[shape = plaintext];
begin_1 [label = "begin[1]", fontcolor = "red"]
end_1 [label = "end[1]", fontcolor = "blue"]
begin_1 -> n1
end_1 -> n1
}
{
rank = "same";
node[shape=plaintext];
begin_2 [label = "begin[2]", fontcolor="red"];
begin_2 -> n2;
}
{
rank = "same";
node[shape = plaintext];
end_2 [label = "end[2]", fontcolor = "blue"]
end_2 -> n6
}
}
```
* 重複排序的動作直到所有節點被排序好
1.
```graphviz
digraph name{
rankdir = LR;
node[shape=box]
n6 [label= "5", color = "red"];
node[shape=plaintext];
begin_2 [label = "begin[2]", fontcolor="red"];
begin_2 -> n6;
}
```
2.
```graphviz
digraph name{
rankdir = LR;
node[shape=box]
n6 [label= "7"];
node[shape=plaintext];
ans [label = "answer"];
null [label = "null"];
ans -> n6 -> null;
}
```
3.
```graphviz
digraph name{
rankdir = LR;
node[shape=box]
n6 [label= "7"];
n5 [label= "5"];
node[shape=plaintext];
ans [label = "answer"];
null [label = "null"];
ans -> n6 -> n5 -> null;
}
```
對於上面給出的 quick sort 方法，最直觀的想法在於 pivot 的選擇或是否會影響到整體程式排序的速度？如果串列本身是以降序排列，而我們又選擇做左邊的節點作為 pivot，worst case 就會發生，如果此時 pivot 並不是最左邊的節點，可以讓這個排序的演算法把時間複雜度降到多少？
:::info
Todo: implement middle pivot, random pivot
:::
### 測驗二
這個題目想實現 Timsort，其概念為一個序列中常常會有已經按順序排的子序列(稱之為 run)，此排序法希望先找到這些 run 之後再不斷進行合併。因此對於隨機的資料，Timsort的表現較差，針對部分排序的資料則可以有較好的表現。
## 第二週測驗
[題目](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
此題想要藉由給定的 preoder 和 inorder traversal 序列，進行二元樹的重建。
從程式碼中，我們可以分別去畫出 `hlist_node`、`hlist_head`、`TreeNode`、`order_node` 的圖形結構，以利理解。
`hlist_head` 與 `hlist_node` 連接：
```graphviz
digraph {
node [shape=record];
rankdir=LR;
list_head [label = "<n> hlist_head|<first> first"];
list_head1 [label = "<n> hlist_node_1|{<pprev> pprev|<next> next}"];
list_head2 [label = "<n> hlist_node_2|{<pprev> pprev|<next> next}"];
list_head:first -> list_head1:n;
list_head1:pprev -> list_head:first;
list_head1:next -> list_head2:n;
list_head2:pprev -> list_head1:next;
}
```
在 `hlist_node` 中的 `pprev` 是個指向指標的指標 (pointer to pointer)，而他指向的就是前一個
指向他的指標，在上圖中的例子，`hlist_node_1` 的 `pprev` 就是指向 `hlist_head` 的 `first` 指標；而`hlist_node_2` 的 `pprev` 則是指向 `hlist_node_1` 的 `next` 指標。
`TreeNode` 架構：
```graphviz
digraph {
node [shape=record];
rankdir = LR;
subgraph cluster {
label = "TreeNode"
list_head [label = "<val> val|{<left> left|<right> right}"];
}
}
```
`other_node` 架構：
```graphviz
digraph {
node [shape=record];
rankdir = LR;
subgraph cluster_element {
label = "other_node"
list_head2 [label = "idx|val"];
list_head1 [label = "<n> hlist_node_1|{<pprev> pprev|<next> next}"];
}
}
```
接著我們就可以開始針對程式碼進行解析。在 `hlist_add_head` 中，我們想要將傳入的 `hlist_node *n` 接在 `hlist_head *h` 所指向的串列中的第一個節點，因此程式所做的操作如下：
```c
// 如果 h 有指向一個節點，則將該節點的 pprev 指向新的節點的 next 指標
if (h->first)
h->first->pprev = &n->next;
```
```graphviz
digraph {
node [shape=record];
rankdir=LR;
list_head [label = "<n> h|<first> first"];
list_head1 [label = "<n> hlist_node_1|{<pprev> pprev|<next> next}"];
list_head2 [label = "<n> hlist_node_2|{<pprev> pprev|<next> next}"];
list_head3 [label = "<n> n|{<pprev> pprev|<next> next}"];
list_head:first -> list_head1:n;
list_head1:pprev -> list_head3:next[color = red];
list_head1:next -> list_head2:n;
list_head2:pprev -> list_head1:next;
}
```
從上面的圖示中，我們可以觀察到：如果 `n` 要成為串列的第一個節點，其 `next` 指標應該要指向原本串列中的第一個節點，也就是圖中的 `hlist_node_1`。而要找到該節點，我們可以透過 `h->first` ，因此在下面程式中，我們應該要將 `AAAA` 填入 `h->first`。
```c
n->next = AAAA; //AAAA = h->first
```
```graphviz
digraph {
node [shape=record];
rankdir=LR;
head [label = "<n> h|<first> first", group = list];
node1 [label = "<n> hlist_node_1|{<pprev> pprev|<next> next}", group = list];
node2 [label = "<n> hlist_node_2|{<pprev> pprev|<next> next}", group = list];
add_node [label = "<n> n|{<pprev> pprev|<next> next}"];
head:first -> node1:n
node1:next -> node2:n
node2:pprev -> node1:next
node1:pprev -> add_node:next
add_node:next -> node1:n[color = red]
}
```
:::info
Todo: 整理 node 的位置
:::
最後的步驟是把 `n` 的 `pprev` 指向 `h` 的 `first` 以及把 `h` 的 `first` 指向 `n` 即可完成 `hlist_add_head` 這個函式的操作。
```C
n->pprev = &h->first;
h->first = n;
```
```graphviz
digraph {
node [shape=record];
rankdir=LR;
head [label = "<n> h|<first> first", group = list];
add_node [label = "<n> n|{<pprev> pprev|<next> next}"];
node1 [label = "<n> hlist_node_1|{<pprev> pprev|<next> next}", group = list];
node2 [label = "<n> hlist_node_2|{<pprev> pprev|<next> next}", group = list];
head:first -> add_node:n[color = red]
add_node:pprev -> head:first[color = red]
node1:next -> node2:n
node2:pprev -> node1:next
node1:pprev -> add_node:next
add_node:next -> node1:n
}
```
接著我們觀察第二個函式 `find`，其目的是想要找到 `val` 與 `num` 相等的 `other_node`，而程式裡面的 `hash` 則是代表在 hash table 儲存的位置。`hlist_for_each(pos, head)` 的用途是遍歷 `head` 指向的串列，因此我們在 `BBBB` 的位置中填入 `hash` 的數值來查找 hash table 中指向的串列。因為我們在遍歷節點時需要知道串列的位址以得到 `val` 的數值資訊，因此我們使用 `container_of` 來做此操作，最後判斷如果該節點的 `val` 值與 `num` 相同時，則回傳該節點的 `idx`。
```C
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) { //BBBB = &heads[hash]
struct order_node *on = CCCC(p, struct order_node, node); //CCCC = container_of
if (num == on->val)
return on->idx;
}
return -1;
}
```
下面 `TreeNode` 就是使用遞迴的方式，進行題目所要求的二元樹重建，傳入的參數包含：preorder 的序列與 inorder 的序列、指向 preorder、inorder 序列當前節點範圍的 `pre_low`、`pre_high` 與 `in_low`、`in_high`，`in_head` 是串列的 `head`，`size` 是此串列的大小。
```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` 判斷式中寫的情形發生：
```C
if (in_low > in_high || pre_low > pre_high)
return NULL;
```
下面的的函式最後會以二元樹的順序(從上而下、從左而右)遍歷節點。從 [測驗題](https://hackmd.io/@sysprog/linux2024-quiz2#2024q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C) 上面對於二元樹 preorder 和 inorder 的描述有提及，preorder 的開頭為 root value，對應到 inorder 中的位置，以左的數值都會是 left node 底下的節點；以右的數值都會是 right node 底下的節點。因此我們從 `preorder[prelow]` 的值開始，找到在二元樹中對應的節點作為 root node，對應 inorder 序列得到左樹與右樹，再呼叫 `dfs` 繼續進行遍歷的動作。
```C=
struct TreeNode *tn = malloc(sizeof(*tn));
// 找到root node 的 value
tn->val = preorder[pre_low];
// 找到 root node 對應的位置
int idx = find(preorder[pre_low], size, in_heads);
// 定義 root node 的左樹
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
// 定義 root node 的右樹
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
```
如果我們就程式中第七與第十行進行更仔細的討論，我們可以知道它其實是先把判斷為左樹的所有節點先掛在 `root node -> left`，而後進行遞迴時才又將其繼續整理。其中 `pre_low` 和 `in_low` 定義了 inorder 序列中，左樹節點樹值範圍；而 `pre_high` 和 `in_high` 定義了 inorder 序列中，左樹節點樹值範圍。
```graphviz
digraph {
rankdir = LR;
subgraph cluster {
node [shape=record];
label = "TreeNode"
list_head [label = "<val> 3|{<left> left|<right> right}"];
}
right [label = "15 20 7"]
left [label = "9"]
list_head:left -> left
list_head:right -> right
}
```
下面 `node_add` 的函式，並不單指把一個節點加到串列中，而是把節點加到 hash table 對應位置所指向串列的第一個位置。Hash table 的位址可由 `*head` 得知。
```C
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;
// 根據 val 的數值，找到這個節點應該要置於 hash table 的哪個位置
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, DDDD); //DDDD = &heads[hash]
}
```
```graphviz
digraph G {
rankdir=LR;
subgraph cluster_table{
node[shape=record];
label = "hash table"
table [label="<0> |<1> |<2> |<3> |<4> |<5> |<6> |<7> "];
}
subgraph cluster {
node [shape=record];
style = filled;
color = lightblue
added_node [label="<label> hlist_node | {<pprev>pprev | <next>next}"];
label="added_node"
}
subgraph cluster_1 {
node [shape=record];
other_node1 [label="<label> hlist_node | {<pprev>pprev | <next>next}"];
label="order_node 1"
}
subgraph cluster_2 {
node [shape=record];
other_node2 [label="<label> hlist_node | {<pprev>pprev | <next>next}"];
label="order_node 2"
}
node[shape = none]
NULL [label = "NULL"]
NULL2 [label = "NULL"]
hlist_head [label = "hlist_head *heads"]
hlist_head:s -> table:0
table:3 -> added_node:label [color=blue]
added_node:pprev -> table:3 [color = blue]
added_node:next -> other_node1:label
other_node1:pprev -> added_node:next
table:6 -> other_node2:label
other_node2:pprev -> table:6
other_node1:next -> NULL
other_node2:next -> NULL2
}
```
下面的程式碼目的是要建構一棵二元樹：
```C
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
// 指派一個空間存放二元樹的節點，總數量是 inorderSize 個
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
// 初始化每個節點的位址
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
// 依序把節點串接到串列上
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
// 使用上面的 dfs 將串列以二元樹順序排列
return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
in_heads, inorderSize);
}
```
### Linux 核心 cgroups
[linux/cgroups.h](https://elixir.bootlin.com/linux/v3.10/source/include/linux/cgroup.h) 中的程式碼是來自於 Linux 核心的 cgroup（Control groups）子系統，主要應用於資源管理、隔離和任務監控。 Cgroup 的核心概念包含以下四個：
* Task：運行在 cgroup 中，以進程 (process) 最小單位。
* Subsystem：cgroup 的架構中，我們可以對不同的資源進行各自的管理 (e.g. CPU, memory, I/O 等)，一個 subsystem 會負責管理一種資源。
* cgroup：cgroup 中控制資源的機制，可以控制一個或多個 subsystem 來對 task 進行管理。
* hierarchy：在 cgroup 中使用的是樹狀的結構來管理其資源，每個節點都是一個 cgroup，子節點會繼承父節點的特性。
cgroup 主要目的在於實現資源的分配和控制，在程式中有定義這樣的一個巨集：
```C
#define cgroup_for_each_descendant_pre(pos, cgroup) \
for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \
pos = cgroup_next_descendant_pre((pos), (cgroup)))
```
其註解的說明如下所示：
```C
/*
* cgroup_for_each_descendant_pre - pre-order walk of a cgroup's descendants
* @pos: the cgroup * to use as the loop cursor
* @cgroup: cgroup whose descendants to walk
*/
```
此巨集的功能在於使用 preorder 的方式遍歷 cgroup 中的元素。可以在 [/kernel/cgroup_freezer.c](https://elixir.bootlin.com/linux/v3.10/source/kernel/cgroup_freezer.c#L411) 檔案(用於暫停跟恢復位於 cgroup 內的 task)中的 [freezer_change_state](https://elixir.bootlin.com/linux/v3.10/C/ident/freezer_change_state) 函式中，看到該巨集被應用於更新樹狀結構的節點。在其他檔案中也可以看到用 preorder 遍歷元素的函式，例如 [block/blk-cgroup.c](https://elixir.bootlin.com/linux/v3.10/source/block/blk-cgroup.c#L51) 檔案(用於限制 task 對於儲存裝置的讀取)中的 `blkg_for_each_descendant_pre`：
```C
#define blkg_for_each_descendant_pre(d_blkg, pos_cgrp, p_blkg) \
cgroup_for_each_descendant_pre((pos_cgrp), (p_blkg)->blkcg->css.cgroup) \
if (((d_blkg) = __blkg_lookup(cgroup_to_blkcg(pos_cgrp), \
(p_blkg)->q, false)))
```
或是 [/kernel/cpuset.c](https://elixir.bootlin.com/linux/v3.10/source/kernel/cpuset.c#L225) 中的 `cpuset_for_each_descendant_pre`：
```C
#define cpuset_for_each_descendant_pre(des_cs, pos_cgrp, root_cs) \
cgroup_for_each_descendant_pre((pos_cgrp), (root_cs)->css.cgroup) \
if (is_cpuset_online(((des_cs) = cgroup_cs((pos_cgrp)))))
```
針對在 Linux kernel 中使用 preorder 這種遍歷方式的原因，我做出兩點推測：
* 使用 preorder 的遍歷順序可以在拜訪到子節點之前就拜訪到父節點，而因為一個 cgroup 可以有多個子節點，子節點也會繼承父節點的特性，因此 preorder 可以在更深入知悉子節點特性之前先透過父節點對其有個大概的了解，進而更有效率。
* 在 freezer 中，對一個 cgroup 進行凍結會對節底下的所有 task，因此此時如果使用 preorder 進行遍歷，可以確保在父節點之下的每一個子節點都遵循命令。
可能的因素可能遠不止於效率、同步等層面，linux/cgroups.h 中也有針對 [post-order traverse](https://elixir.bootlin.com/linux/v3.10/C/ident/cgroup_for_each_descendant_post) 的巨集，因此需要更多相關資料的閱讀才能針對 Linux kernel 中不同遍歷的方式給出更深入的解釋。
### 測驗二
Least Recently Used (LRU) 的核心觀念就是將比較常用到的資料放置在記憶體空間的前面，減少對磁盤的存取，讓讀取的速度可以更快。
```C
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev; //EEEE = next->pprev
}
```
上面的函式 `hlist_del` 主要目的是要從串列中刪除一個節點 `n`，其步驟如下：
1. `struct hlist_node *next = n->next, **pprev = n->pprev`: 宣告一個指標 `*next` 指向 `n` 的下一個節點；宣告另一個指標的指標 `**pprev` 指向 `n` 的前一個節點的 `next` 指標。
2. `*pprev = next`: 將 `n` 的前一個節點的 `next` 指標指向 `n` 的下一個節點，也就是在做 `n` 的移除。
3. 如果 `next` 存在，就更新該節點的 `pprev` 指標，使其指向原本 `n` 節點的 `pprev` 指向的指標。
在進行 cache 的相關操作之前，程式中有先對 `LRUCache` 和 `LRUNode` 進行定義：
LRUCache:
```graphviz
digraph {
rankdir=LR;
subgraph cluster_1{
node [shape=record];
label = "LRUCache"
other[label = "<cap> capacity|<count> count"]
list_head [label = "<h> dhead|{<next> next|<prev> prev}", group = list];
hlist_head [label = "<h> hhead[]|<first> first"];
}
}
```
當中的 capacity 代表的是這個 cache 的頁面數 (page)，count 代表的是當前使用的頁面數，`dhead` 指向紀錄 LRU 的 node，用來儲存最近使用的頁面，當一個頁面愈常被使用，他就會排在較前面的位置，`hhead` 指向 hash table，對應 node 的儲存位置。
LRUNode:
```graphviz
digraph{
rankdir = LR
subgraph cluster_2{
node [shape=record];
label = "LRUNode"
other1[label = "<key> key|<val> value"]
hlist_node [label = "<h> node", group = list];
list_head2 [label = "<h> link|{<next> next|<prev> prev}", group = list];
}
}
```
`key` 指的是索引值，`value` 則是該節點儲存的內容。`node` 會被 hash 並被插入到串列中，`link` 則是會隨資料的使用而被改變。在 [HenryChaing](https://hackmd.io/O_Me7VZOSX2N_yne2I05lQ?both) 的報告中有清楚的圖來指明 `LRUCache` 和 `LRUNode` 的互動關係，如下圖所示。
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
subgraph cluster_4 {
style=filled;
color=lightgrey;
dhlist_head [label="dhead | {<prev>prev | <next>next}"];
map [label=" hhead[] |<ht0>|<ht1>|<ht2>|<ht3>|<ht4>|<ht5>|<ht7>|<ht8>|<ht9>|<ht10>|<ht11>|<ht12>"];
label="LRUCache"
}
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn5 [label="link | {<prev>prev | <next>next} "];
hn1 [label="node | {<prev>pprev | <next>next} "];
label="LRUNode 1"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn6 [label="link | {<prev>prev | <next>next} "];
hn3 [label="node | {<prev>pprev | <next>next}"];
label="LRUNode 2"
}
null1 [label=NULL,shape="plaintext"]
null2 [label=NULL,shape="plaintext"]
map:ht1 -> hn1
hn1:next -> null1
map:ht10 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht10
dhlist_head:next -> hn5:prev [color = red]
hn5:next-> hn6 [color = red]
hn6:next ->dhlist_head:e [color = red]
}
```
函式 `lRUCacheCreate` 的目的是要創造一個動態存取的空間給 `LRUCache` 並初始化其 `capacity` 和 `count`，設置一個 doubly-linked list head，就可以有一個初始化完成的 LRUCache 可以被使用。首先，我們要先指派位置給我們的 `LRUCache`，大小為兩個 `int` (capacity, count)、一個 `list_head` 和 capacity 乘上 `list_head`。
```C
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct list_head));
```
接著設置 cache 的 capacity 和 count 後，用 `INIT_LIST_HEAD` 對串列 `dhead` 串列做初始化，接著再依序對有對應到 hash table 的串列 `hhead` 做初始化，最後回傳 cache 即可完成。
```C
cache->capacity = capacity;
cache->count = 0;
INIT_LIST_HEAD(&cache->dhead);
for (int i = 0; i < capacity; i++)
INIT_HLIST_HEAD(&cache->hhead[i]);
return cache;
```
`lRUCacheFree` 函式則是將 cache 的位置釋出，其流程如下：
```C
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF); // FFFF = link
list_del(GGGG); // &cache->link
free(cache);
}
free(obj);
}
```
透過 `list_for_each_safe` 遍歷節點，由 `list_entry` 找到對應的位址後，使用
`list_del` 將該節點從串列中移除，並使用 `free` 釋出記憶體。
`lRUCacheGet` 的目標在於根據 `key` ，從串列中得到對應節點的 `value`。
```C
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); //HHHH = node
if (cache->key == key) {
list_move(IIII, &obj->dhead); //IIII = &cache->link
return cache->value;
}
}
return -1;
}
```
先根據 `key` 和 cache 的 `capacity` 數值找到該節點在 hash table 中的對應位置，再透過 `hlist_for_each` 函式遍歷儲存於 hash table 該位置的串列。如果找到相同 `key` 的目標節點，則將其移動到 `dhead` 的最前面。
`lRUCachePut` 函式的目的在於插入新的 `key` 和 `value` 值，也可以對 LRUCache 根據給定的 `key`，幫對應到的節點 `value` 值做更新。此函式會檢查`key` 是否已存在於 cache 中並且做處理，並更新hhead 和 dhead。
```C
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); //JJJJ = node
if (c->key == key) {
list_move(KKKK, &obj->dhead); //KKKK = &c->link
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;
}
```
從程式中我們可以看到有三種情況可能會發生，分別是：
1. 資料已經在 cache 中被儲存
2. `if (obj->count == obj->capacity)`: cache 的空間已滿且在 cache 中找不到對應的 `key` (`if (!cache)`)
3. `else`: cache 的空間未滿且在 cache 中找不到對應的 `key`
針對第一種情況，我們會在遍歷串列，找到對應的節點之後，將其移動到串列的第一個位置；第二種情況則是會將 hash table 中最後一筆資料做移除，意即將最久沒被使用的資料移除，再將新的資料放到串列中的第一個位置；對於第三種情況，函式會新指派一個空間，並將其加入到串列的第一個位置，同時更新 hash table。
### Linux 核心 LRU
LRU 的概念在 Linux 核心中主要涉及到頁面置換 (page replacement) 與頁面回收 (page reclaim) 的概念，在 [fs/proc/meminfo.c](https://android.googlesource.com/kernel/msm/+/refs/heads/android-msm-crosshatch-4.9-android10/fs/proc/meminfo.c) 中有幾種不同類型的串列如下所示，原理就是將較不常用的頁面放置到 inactive 串列，將較常用的頁面放置到 active 串列：
1. LRU_INACTIVE_ANON：swap 中非活動頁面的 LRU 串列。
2. LRU_ACTIVE_ANON：swap 中活動頁面的 LRU 串列。
3. LRU_INACTIVE_FILE：磁碟中非活動頁面的 LRU 串列。
4. LRU_ACTIVE_FILE：磁碟中活動頁面的 LRU 串列。
5. LRU_UNEVICTABLE：保存禁止被換出的頁面的描述符。
### 測驗三
下面的程式目的在於在指定的記憶體空間找出第 N 個設定的位元，先針對內部的巨集進行分析：
#### BITS_PER_LONG
此巨集根據給定的位元數 `nr` ，計算出編譯此程式碼的 `long` 所需的位元數。
```C
#define DIV_ROUND_UP(n, d) (((n) + (d) -1) / (d))
#define BITS_PER_BYTE 8
#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
```
#### small_const_nbits
使用 `__builtin_constant_p` 檢查 `nbits` 是否為常數，以及 `nbits` 是否藉於 0 和 `BITS_PER_LONG` 之間。
```C
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
#### GENMASK
設定在範圍 1 到 h 內的連續位元為1。
```C
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
#### __ffs
目的是找到 word 的第一個 bit 的位置，一開始先求出 word & AAAA(0xffffffff)，如果其值為 0，就代表此 word 第 32 位的 bit 沒有為 1 的數值。後面再依序對 0xffff、0xff、0xf、0x3 和 0x1 做 `and` 來觀察 1 在 word 中的出現情形。需注意的是 #if BITS_PER_LONG == 64 這個假設，在 word 是 64 位元架構的情況下才可以做 `if((word & 0xffffffff) == 0)` 的這個比較，避免出錯。
#### __clear_bit
先用 BIT_MASK 設定只有第 nr 個 bit 為 1 的 mask，接著使用 BIT_WORD 去計算 nr 是屬於第幾個 word ，並將定義為 `unsigned long` 的指標 p 指向 addr 中 nr 所屬的 word，將 BBBB 填為 ~mask 就是要得到只有第 nr 個 bit 為 0 的遮罩，最後執行 `&` 就能將 addr 中第 nr 個 bit 清除成 0。
```C
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; //BBBB = ~mask
}
```
#### FIND_NTH_BIT
```C
#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) //CCCC = < \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
* sz: 剩餘 bit array 的大小
* nr: 剩餘要找的 bit 數
* idx: 遍歷 bit array 的指標
* w: 指向現在這個 word 的 set bit
* tmp: 用來暫存 fetched word of bits
Sign in with Wallet
Connect another wallet