# 2024q1 Homework2 (quiz1+2)
contributed by < [`jimmylu890303`](https://github.com/jimmylu890303)>
## 第一周測驗題
- [題目](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
#### 程式運作原理
測驗是參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) ，實作非遞迴 (non-recursive; iterative) 的快速排序法。 再使用
- `list_add`
在這個函式中，它會插入一顆新的節點到原本串列的前方，他傳入一個 `node_t ** list` 的參數為 `pointer to pointer` ， 因為 C 語言的在函數中傳入的參數為一個`副本`，所以要將原本 `head` 指標改指向到新的節點上，就需要使用 pointer to pointer 的方式去更改原本的 head 指標。
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;
*list = node_t;
}
```
圖片取自於[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)，在函數傳入參數時，會複製一份副本 `p` ，這個指標會指向原本的 head 指標。
透過更改 `head` 指標所指向的位置可以將 ptrA 的指標更改成下個位置。
- `list_tail`
在這個函式中會去尋找著串列中的最後一個節點位置並回傳該位置，它傳入一個 `node_t ** left` 的參數，但是這邊使用方式為 `indirect pointer` ，為了可以能夠更精簡程式碼，可以省略一些條件判斷的行數。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(*left)->next;
return *left;
}
```
但是在這個函式中，使用 `node_t *left`中也是可以的，並不會增加程式碼的行數。
```c
node_t *list_tail(node_t *left)
{
while (left && left->next)
left = left->next;
return left;
}
```
- `list_length`
在這個函式中會計算串列中的長度，但是傳入的參數為 `node_t **left` ， 使用方式為 `indirect pointer`，所以在迴圈內 left 要指向的位置必須為 `node_t *` 的指標，所以 left 在迴圈內操作會指向 `(*left)->next` 。
- `quick_sort`
在 `quick_sort` 中一開始宣告 `max_level = 2 * n` 為堆疊深度，為了模仿遞迴中堆疊的行為。 begin 負責儲存串列的頭元素位置， end 負責儲存串列的尾元素位置， i 負責模擬堆疊中 pop 操作。
```c
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
// 初始串列為原始串列
begin[0] = *list;
end[0] = list_tail(list);
```
在 while 迴圈負責控制 stack 的行為，每次迴圈內，從 bgein 和 end 取出串列的頭部及尾部節點位置。如果 L != R 則代表該串列元素大於一個，反之串列元素剩下一個，在將該元素加入到 result 的結果串列中。
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
//
} else {
if (L)
list_add(&result, L);
i--;
}
}
```
p 指標一開始會為 pivot 的下個元素， 在 while (p) 迴圈內會將此串列分割成 left 和 right 兩個串列。 left 串列為元素值小於 pivot， right 串列為元素值大於 pivot。
```c
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
將串列分成 left 和 right 串列後，就需要將他們存入到 begin 和 end 中，在這個部分因為 `list_add` 是將新的元素插入到串列的第一個，所以堆疊的順序是高位為 right 。
```c
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
```
#### 提出改進方案並予以實作
以上程式碼在事先宣告兩個大小為 max_level 的 begin 和 end 陣列太耗費記憶體空間了，假設在 n = $10^6$ 且處理器架構為32位元的情況，一個 begin 陣列就需要高達 $4 \times 2 \times 10^6$ Bytes， 所以這個部分我覺得可以使用 `dynamic array` 的方式去實作這個陣列。
我將原先的 begin 和 end 兩個陣列作更改成動態陣列的方式，先只事先宣告成長度為 n 的陣列。
```diff
+ int stack_size = n;
- int max_level = 2 * n;
+ node_t **begin =(node_t **) malloc(sizeof(node_t *)*stack_size);
+ node_t **end =(node_t **) malloc(sizeof(node_t *)*stack_size);
- node_t *begin[max_level], *end[max_level];
```
若stack空間不足，在 realloc 堆疊空間。
```diff
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
+ if(i>=stack_size-3){
+ stack_size+=3;
+ begin = realloc(begin,sizeof(node_t*)*stack_size);
+ end = realloc(end,sizeof(node_t*)*stack_size);
+}
```
改成使用動態陣列的方式，這些資料會存放在 heap 的區塊，而原先的陣列方式為區域變數，所以會存放在堆疊的區塊。
使用 valgrind 的 massif 來追蹤使用動態陣列的程式碼堆積的使用狀況。
```
$ valgrind --tool=massif --stacks=yes ./main.elf
==6045== Massif, a heap profiler
==6045== Copyright (C) 2003-2017, and GNU GPL'd, by Nicholas Nethercote
==6045== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==6045== Command: ./main.elf
==6045==
==6056==
$ massif-visualizer massif.out.6056
QCommandLineParser: already having an option named "h"
QCommandLineParser: already having an option named "help-all"
QCommandLineParser: already having an option named "v"
loaded massif file: QUrl("file:///home/jimmylu/linux2024/hw2/quick_sort/massif.out.6056")
description: "--stacks=yes"
command: "./main.elf"
time unit: "i"
snapshots: 55
peak: snapshot # 10 after 2.09999e+06 "i"
peak cost: "507.8 KiB" heap "78.1 KiB" heap extra "592 B" stacks
```
而原先的程式碼
```
$ valgrind --tool=massif --stacks=yes ./origin.elf
==6165== Massif, a heap profiler
==6165== Copyright (C) 2003-2017, and GNU GPL'd, by Nicholas Nethercote
==6165== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==6165== Command: ./origin.elf
==6165==
==6165==
$ massif-visualizer massif.out.6165
QCommandLineParser: already having an option named "h"
QCommandLineParser: already having an option named "help-all"
QCommandLineParser: already having an option named "v"
loaded massif file: QUrl("file:///home/jimmylu/linux2024/hw2/quick_sort/massif.out.6165")
description: "--stacks=yes"
command: "./origin.elf"
time unit: "i"
snapshots: 56
peak: snapshot # 11 after 2.23016e+06 "i"
peak cost: "351.6 KiB" heap "78.1 KiB" heap extra "313.1 KiB" stacks
```
從上面兩圖可以發現若使用動態陣列，會使得 heap 的使用區塊增加。
從 [stackoverflow](https://stackoverflow.com/questions/48910614/measure-static-heap-and-stack-memory-c-linux-centos-7) 節錄以下對話。
```
To measure the heap memory use valgrind -> massif
To measure the static memory use the bash function size on the binary
To measure the stack it is possible to use stackusage
```
所以我使用 [stackusage](https://github.com/d99kris/stackusage) 這個工具來觀察堆疊的區塊使用率。
觀察改善後面的程式
```
$ stackusage ./main.elf
stackusage log at 2024-03-07 23:57:24 ----------------------------------------
pid id tid requested actual maxuse max% dur funcP name
6269 0 6269 8388608 8384512 5160 0 0 (nil) main.elf
```
觀察原本的程式
```
$ stackusage ./origin.elf
stackusage log at 2024-03-07 23:57:59 ----------------------------------------
pid id tid requested actual maxuse max% dur funcP name
6297 0 6297 8388608 8376320 321344 3 0 (nil) origin.elf
```
可以發現若使用動態陣列的方式可以有效去改善佔用太多堆疊區塊空間的問題。
### 測驗二
[Tim Sort](https://en.wikipedia.org/wiki/Timsort) 結合合併排序和插入排序的特點，如今已廣泛用於生活的各個地方，而 TimSort 主要的想法是在現實世界中，許多資料往往是由一些已經部分排序的序列組合而成，所以首先的策略是識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序。
首先在使用 Time Sort 時會先將原本的串列的最後一個節點解除環狀佇列，並將它指向 `NULL`
```graphviz
digraph{
## rankdir=TD
rankdir=LR
node [shape=box,color=black]
null [shape=none,label=NULL]
list [shape=none,label=list,fontcolor=red]
head [shape=box,color=red]
list->node1
head->node1->node2->node3->node4->null[arrowhead=vee]
{rank=same; list;node1}
}
```
而以下程式碼操作的流程為每次呼叫 `find_run` 後會找到一個 `un , 接下來使用 result.head 和 result.next 記錄整個 run 的頭尾，並且會記錄該 run 的長度在 head->next->prev 當中。
```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` 所回傳的 `struct pair` 的 result ， result.head 為此回合找到的 run 。
```graphviz
digraph{
## rankdir=TD
rankdir=LR
node [shape=box,color=black]
null [shape=none,label=NULL]
Result_head [shape=none,label=result_head,fontcolor=red]
Result_next [shape=none,label=result_next,fontcolor=red]
len [shape=none,label=len,fontcolor=red]
Result_head->node1
Result_next->node3
node2->len
node1->node2
node3->node4->null
node2->node3 [style=invis]
{rank=same; Result_head;node1}
{rank=same; len;node2}
{rank=same; Result_next;node3}
}
```
而在 `find_run` 中以下程式碼將 size_t 型態的變數強制轉型成 struct list_head * 型態，並且讓 `head->next->prev` 指標存放這個值，這個寫法個人覺得非常的有趣，因為指標裡頭的內容是存放目標位置，該目標位址的型態為指標的型態，但這邊作法是指標存放 len 裡頭存放的值，透過這指標可能會存取到非法區塊，並且這區塊的型態不是指標所指向的型態。
```c
static struct pair find_run(void *priv,
struct list_head *list,
list_cmp_func_t cmp)
{
size_t len = 1;
// 中間省略
head->next->prev = (struct list_head *) len;
}
```
所以因為以上緣故，才可以透過 `run_size` 來存取此 run 的長度。
```c
static inline size_t run_size(struct list_head *head)
{
if (!head)
return 0;
if (!head->next)
return 1;
return (size_t) (head->next->prev);
}
```
經過幾次的 `find_run` ，串列會被分成若干個 run ，而 tp 會指向堆疊中最上面的 run ，也就是最新的 run 。
```graphviz
digraph{
## rankdir=TD
rankdir=LR
node [shape=box,color=black]
tp [shape=none,label=tp,fontcolor=red]
A [shape=none,label=A,fontcolor=blue]
B [shape=none,label=B,fontcolor=blue]
C [shape=none,label=C,fontcolor=blue]
C->8-> 9
B->5->6->7
A->1->2->3->4
8->5 [xlabel= " tp->prev",fontcolor=red]
{rank=same; 5;8}
tp->8
{rank=same; tp;8}
5->1[xlabel= " tp->prev->prev",fontcolor=red]
{rank=same; 5;1}
}
```
之後使用 `merge_collapse` 檢查堆疊中上面 3 段的 run 的長度是否滿足以下原則：
- A 的長度要大於 B 和 C 的長度總和。
- B 的長度要大於 C 的長度。
在以下情況進行合併
1. A <= B+C && A < C : AB 合併
2. A <= B+C && A >= C : BC 合併
3. B <= C : BC合併
```c
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev)))
{
// A <= B+C and A < C => AB 合併
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
}
// A <= B+C and A>=C => BC 合併
else {
tp = merge_at(priv, cmp, tp);
}
}
// B<=C => BC合併
else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
```
之後會透過 `merge_force_collapse` 將多個 run 進行合併，直到 run 總數 < 3 為止。
最後因為經過 `merge_force_collapse` 合併後，run 總數 < 3 ，所以可能的總數為 1 或 2 ，若為 1 則直接呼叫 `build_prev_link` ， 若為 2 則呼叫 `merge_final` 合併最後的 run ，如以下程式碼所示。
```c
if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
## 第二周測驗題
[題目](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹，但是是運用 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) 來完成實作。
而在 linux 核心中 hash table 視覺圖如下
Hash table 中的元素為 `hlist_head` ，而 Hash table 中各個 bucket 的節點為 `hlist_node`
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
```
使用前序和中序來完成 `buildTree` ，首先會透過中序建立 hash table ，而雜湊函數的作法是使用 `Division method` 的方式
```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;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, DDDD);
}
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
}
```
之後使用遞迴的方式呼叫 `dfs` 來完成建樹的工作
```c
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
in_heads, inorderSize);
}
```
而在 dfs 中 TreeNode tn 的值為前序 index 最低的點(即 pre_low) ，在藉由透過 `find` 去尋找此點在中序的 index ，再依序 dfs 遞迴左子樹及右子樹完成建樹，而在左子樹和右子樹的前序和中序的 low , high index 的設定如下
- 左子樹
- pre_low : 為原本的 pre_low + 1
- pre_high : 為原本的 pre_low + 1 再加上 (idx - in_low) ， (idx - in_low) 表示為中序當前點左子樹的節點個數
- in_low : 原本的最低索引 in_low
- in_high : 根節點的左邊
```graphviz
digraph{
## rankdir=TD
rankdir=LR
node [shape=circle,color=black]
idx[shape=plaintext,fontcolor=red,label="idx=2"]
in_order [shape=none,fontcolor=red]
i1 [color=red,label=1]
i2 [label=2]
i3 [label=3]
i4 [label=4]
i5 [label=5]
i6 [label=6]
in_order->i4->i2->i1->i5->i3->i6
pre_order [shape=none,fontcolor=red]
p1 [color=red,label=1]
p2 [label=2]
p3 [label=3]
p4 [label=4]
p5 [label=5]
p6 [label=6]
pre_order->p1->p2->p4->p3->p5->p6
tn[shape=plaintext,fontcolor=blue,label="tn, old_pre_low"]
tn->p1
{rank=same;tn;p1}
new_pre_low[shape=plaintext,fontcolor=blue]
new_pre_low->p2
{rank=same;new_pre_low;p2}
new_pre_high[shape=plaintext,fontcolor=blue,label="new_pre_high, old_pre_high"]
new_pre_high->p6
{rank=same;new_pre_high;p6}
in_low [shape=plaintext,fontcolor=blue,label="new_in_low, old_in_low"]
in_low->i4
{rank=same;in_low;i4}
new_in_high[shape=plaintext,fontcolor=blue]
new_in_high->i2
{rank=same;new_in_high;i2}
old_in_high[shape=plaintext,fontcolor=blue]
old_in_high->i6
{rank=same;old_in_high;i6}
}
```
- 右子樹
- pre_low : 為原本的 pre_high 再減 (in_high - idx - 1) ，(in_high - idx - 1) 為中序根節點右子樹的數量
- pre_high : 為原本的 pre_high
- in_low : 根節點的右邊
- in_high : 原本的最高索引 in_high
```graphviz
digraph{
## rankdir=TD
rankdir=LR
node [shape=circle,color=black]
idx[shape=plaintext,fontcolor=red,label="idx=2"]
in_order [shape=none,fontcolor=red]
i1 [color=red,label=1]
i2 [label=2]
i3 [label=3]
i4 [label=4]
i5 [label=5]
i6 [label=6]
in_order->i4->i2->i1->i5->i3->i6
pre_order [shape=none,fontcolor=red]
p1 [color=red,label=1]
p2 [label=2]
p3 [label=3]
p4 [label=4]
p5 [label=5]
p6 [label=6]
pre_order->p1->p2->p4->p3->p5->p6
tn[shape=plaintext,fontcolor=blue,label="tn, old_pre_low"]
tn->p1
{rank=same;tn;p1}
new_pre_low[shape=plaintext,fontcolor=blue]
new_pre_low->p3
{rank=same;new_pre_low;p3}
new_pre_high[shape=plaintext,fontcolor=blue,label="new_pre_high, old_pre_high"]
new_pre_high->p6
{rank=same;new_pre_high;p6}
new_in_low[shape=plaintext,fontcolor=blue]
new_in_low->i5
{rank=same;new_in_low;i5}
in_high[shape=plaintext,fontcolor=blue]
in_high->i6
{rank=same;in_high;i6}
}
```
```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;
}
```
### 測驗二
此題是使用雜湊表來模仿 cache 的實作，考慮以下結構
```c
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
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;
```
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
LRUCache[label="<m>LRUCache | <n>capacity | <o>count | <p>dhead | <q>hhead[]"]
LRUNode[label="<m>LRUNode | <n>key | <o>value | <p>node | <q>link"]
hlist_head[label = "<m>hlist_head | first", group = list];
hlist_node[label = "<m>hlist_node | {<p>pprev | <n>next}", group = list];
hlist_head-> hlist_node [style=invis]
LRUCache->LRUNode [style=invis]
}
```
使用 `lRUCacheCreate` 創建 cache ，透過 hhead[ ] ，可將要存放的資料存入 cache
```diff
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
- capacity * sizeof(struct list_head));
+ capacity * sizeof(struct hlist_head));
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;
}
```
使用 `lRUCachePut` 來存放資料
首先會去對應的雜湊表檢查要新增的值是否存在，若存在此 key 則忽略存入此值，並去在 dhead 中更新 LRU 的順序。
```c
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
list_move(&c->link, &obj->dhead);
cache = c;
}
}
```
若沒在 hash table 中沒找到對應的 key ，則需存入該值，則會有以下狀況 :
1. cache 容量已滿 : 需要使用 list_last_entry 尋找 dhead 中最後面的節點 (代表最不常被使用到)，並將它從 dhead 中移動到第一個位置且從原本的雜湊表中移除，這裡值得注意是它並無重新 malloc 一個新的空間給新的值，而是重複使用的舊空間，所以最後才會呼叫 `hlist_add_head` 將此節點新增到對應的雜湊表。
2. cache 容量未滿 : malloc 一個新的空間給新的值作存放。
```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;
}
```
使用 `lRUCacheGet` 可以去尋找 cache 中是否有對應的值並取出，若無該 key 則回傳 -1 。
```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);
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
#### 實作程式
> [commit - 6040fbf](https://github.com/jimmylu890303/linux2024_lab/commit/6040fbf4df44d4f261ef6f50b551dd72eab7b5c0)
新增 multiplication hash function 並將原先的 hash function 額外包裝使程式碼更易維護
```diff
+int division_hash(LRUCache *obj,int key){
+ return key % obj->capacity;
+}
+int multiplication_hash(LRUCache *obj,int key){
+ double A = (sqrt(5) - 1) / 2;
+ double s = key * A;
+ double x = s - floor(s);
+ return floor(obj->capacity * x);
+}
+int hash_function(LRUCache *obj,int key){
+ if(obj->hash_type==0)
+ return division_hash(obj,key);
+ return multiplication_hash(obj,key);
+}
```
實作 [test.py](https://github.com/jimmylu890303/linux2024_lab/blob/main/LRU/test.py) 比較原先測驗題目中的 division hash function 與我新實作的 multiplication hash function 兩者間的 Hash Collision 次數
從上圖中可以發現 multiplication 的方法碰撞次數相較 division 較為平均
```
$ python3 test.py
Total count of division : 315699
mean : 154.14990234375,variance : 276.66877380579814
Total count of multiplication : 315439
mean : 154.02294921875,variance : 268.4845732226276
```
並且計算兩者的平均和變異數，multiplication 的方法皆比較低
#### LRU in Linux
> [linux/include/linux/lru_cache.h](https://github.com/torvalds/linux/blob/586b5dfb51b962c1b6c06495715e4c4f76a7fc5a/include/linux/lru_cache.h#L167)
> [linux/lib/lru_cache.c](https://github.com/torvalds/linux/blob/586b5dfb51b962c1b6c06495715e4c4f76a7fc5a/lib/lru_cache.c#L4)
`lru_cache` 是一個輔助的框架，它可以用於追蹤 index 和 label 間的關聯，並更改 `Activate Set` 中的 Objects 。
> This header file (and its .c file; kernel-doc of functions see there)
define a helper framework to easily keep track of index:label associations,
and changes to an "active set" of objects, as well as pending transactions,
to persistently record those changes.
而它主要目的是使用於本地和遠端磁碟複製的 IO 操作， 若在複製節點時發生崩潰，需要`重新同步`所有曾經被寫入的IO操作的目標區域（使用中或熱區域），因為無法確定這些寫入是否已經存到遠端磁碟中。為了避免完全重新同步，需要持續追蹤這些區域，稱為 `write intent log`
在 `lru_cache.h` 中定義了兩個結構
```C
struct lc_element {
struct hlist_node colision;
struct list_head list; /* LRU list or free list */
unsigned refcnt;
/* back "pointer" into lc_cache->element[index],
* for paranoia, and for "lc_element_to_index" */
unsigned lc_index;
/* if we want to track a larger set of objects,
* it needs to become an architecture independent u64 */
unsigned lc_number;
/* special label when on free list */
#define LC_FREE (~0U)
/* for pending changes */
unsigned lc_new_number;
};
```
`refcnt` : 紀錄目前被使用的次數，若為 0 可能會被 `lru_cache` 移動到 `lru` 或 `free` 的串列
```C
struct lru_cache {
/* the least recently used item is kept at lru->prev */
struct list_head lru;
struct list_head free;
struct list_head in_use;
struct list_head to_be_changed;
/* the pre-created kmem cache to allocate the objects from */
struct kmem_cache *lc_cache;
/* size of tracked objects, used to memset(,0,) them in lc_reset */
size_t element_size;
/* offset of struct lc_element member in the tracked object */
size_t element_off;
/* number of elements (indices) */
unsigned int nr_elements;
/* Arbitrary limit on maximum tracked objects. Practical limit is much
* lower due to allocation failures, probably. For typical use cases,
* nr_elements should be a few thousand at most.
* This also limits the maximum value of lc_element.lc_index, allowing the
* 8 high bits of .lc_index to be overloaded with flags in the future. */
#define LC_MAX_ACTIVE (1<<24)
/* allow to accumulate a few (index:label) changes,
* but no more than max_pending_changes */
unsigned int max_pending_changes;
/* number of elements currently on to_be_changed list */
unsigned int pending_changes;
/* statistics */
unsigned used; /* number of elements currently on in_use list */
unsigned long hits, misses, starving, locked, changed;
/* see below: flag-bits for lru_cache */
unsigned long flags;
const char *name;
/* nr_elements there */
struct hlist_head *lc_slot;
struct lc_element **lc_element;
};
```
在 `lru_cache.c` 中
```c
/**
* lc_put - give up refcnt of @e
* @lc: the lru cache to operate on
* @e: the element to put
*
* If refcnt reaches zero, the element is moved to the lru list,
* and a %LC_STARVING (if set) is cleared.
* Returns the new (post-decrement) refcnt.
*/
unsigned int lc_put(struct lru_cache *lc, struct lc_element *e)
{
PARANOIA_ENTRY();
PARANOIA_LC_ELEMENT(lc, e);
BUG_ON(e->refcnt == 0);
BUG_ON(e->lc_number != e->lc_new_number);
if (--e->refcnt == 0) {
/* move it to the front of LRU. */
list_move(&e->list, &lc->lru);
lc->used--;
clear_bit_unlock(__LC_STARVING, &lc->flags);
}
RETURN(e->refcnt);
}
```
`lc_put` 實作中可以看到若 refcnt 為 0 ，會把此 lc_element 移動到 lc_cache->lru 中
```c
/**
* lc_del - removes an element from the cache
* @lc: The lru_cache object
* @e: The element to remove
*
* @e must be unused (refcnt == 0). Moves @e from "lru" to "free" list,
* sets @e->enr to %LC_FREE.
*/
void lc_del(struct lru_cache *lc, struct lc_element *e)
{
PARANOIA_ENTRY();
PARANOIA_LC_ELEMENT(lc, e);
BUG_ON(e->refcnt);
e->lc_number = e->lc_new_number = LC_FREE;
hlist_del_init(&e->colision);
list_move(&e->list, &lc->free);
RETURN();
}
```
`lc_del` 則會將 lru 的 object 移動到 free 的串列
```c
static int lc_unused_element_available(struct lru_cache *lc)
{
if (!list_empty(&lc->free))
return 1; /* something on the free list */
if (!list_empty(&lc->lru))
return 1; /* something to evict */
return 0;
}
```
再透過 `lc_unused_element_available` 檢查 lc_cache 中是否可用的區塊
Sign in with Wallet
Connect another wallet