# 2022q1 Homework1 (quiz1)
contributed by < [`tinyynoob`](https://github.com/tinyynoob) >
> [作業要求](https://hackmd.io/@sysprog/B166rc3Jq)
## 測驗 1
本題主要是在闡述 Linux kernel 當中 hash table 的實作，觀察
```c
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
可知 table 結構大致如下
```graphviz
digraph {
rankdir = LR;
node [shape=record];
heads [label="heads[0]|heads[1]|heads[2]|heads[3]"];
label = "struct hlist_head heads[4]";
}
```
每格都連接著一條 linked list (或 NULL )，以 `heads[2]` 為例
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[2]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none1 [label=""];
edge [weight=3 style="invis"];
first -> a -> b -> c;
edge [weight=2 style=""];
first -> a:body;
a:n -> b:body;
b:n -> c:body;
c:n -> none1 [arrowhead=dot];
edge [color="blue"];
a:p -> first;
b:p -> a:n;
c:p -> b:n;
}
```
每個 hlist_node 上的 entry 結構定義為：
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
其中不同節點的 key 應不同，即 key 的唯一性需要被保證，否則後續在 **find_key()** 可能會出問題。
```c
typedef struct { int bits; struct hlist_head *ht; } map_t;
#define MAP_HASH_SIZE(bits) (1 << bits)
```
table size (圖中的數字 4 ) 是由 `MAP_HASH_SIZE()` macro 來取得，其值為輸入乘以 2 ，並會紀錄於 `map_t` 的 `bits` 成員。
:::warning
為何 `bits` 不使用 `size_t` 型別？
此外，為何會選用 `bits` 做為變數名稱？是否有什麼特殊意涵？
> 取名 `bits` 主要是搭配 capacity 的計算，無論是 `size_t` 或 `ssize_t` 都不影響理解。
> :notes: jserv
:::
### map_init()
```c
map_t *map_init(int bits) {
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
該函式的功能為動態配置出 table 結構，並依序將每個 hlist_head 的 `first` 成員都初始化為 NULL 。
### find_key()
```c=
static struct hash_key *find_key(map_t *map, int key) {
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
```
函式的第 2 行使用 hash function 快速前往資料所在的 hlist ，接著 3 到 7 行走訪該 hlist ，一個一個比對是否為我們要尋找的節點，若找不到則回傳 NULL 。
以上功能正確運作的一個必要條件是 key 的唯一性，否則可能會找到 key 值相同的另一個節點，使得後續取出的 data 不如預期。
這裡頭所使用的 hash function 定義為
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
目前不太清楚為何選用 golden ratio 為乘數。
---
這裡使用了 [Fibonacci hashing](https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing) ，根據 wikipedia ，這樣的 hash 方法可以使結果均勻分配在 table space 中。
:::warning
或許可以用程式測看看它的分佈
:::
至於前面的 macro define 怎麼來呢？首先， ==golden ratio== 在數學上為 $\varphi=(\sqrt{5}+1)/2\approx 1.618033989$ ，我們可以計算出其倒數 $\varphi^{-1}= (\sqrt{5}-1)/2\approx 0.618033989$ 恰好是原本的小數部份。
[**linux/hash.h**](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的註解中引註了一篇文章 [Linux Kernel Hash Table Behavior: Analysis and Improvements](http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf) ，在其 5.1 節給出
> $(\sqrt{5} - 1 ) / 2 = 0.618033989$
$2654435761 / 4294967296 = 0.618033987$
這個 4294967296 顯然是 32 位無號數的最大值加 1 ，也就是 $2^{32}$ 。
這代表我們將輸入的 `val` 乘上 $\varphi^{-1}$ 幾乎等同於乘上 2654435761 並右移 32 ，然後我們需要左移 `bits` 位以充分利用 hashtable 的 size 。
然而 **hash.h** 裡定義的 golden_ratio_32 是 0x61C88647 也就是 1640531527 ，並不是文章中的 2654435761 ，由於 0x61C88647 的二進制最高位是 0 ，所以我以為這個差異不是來自有無號轉換。
查詢了[網路上的討論](https://stackoverflow.com/questions/38994306/what-is-the-meaning-of-0x61c88647-constant-in-threadlocal-java)，得到答案說這其實還是跟有號數、無號數有關，我整理如下
|signed|unsigned|binary|hex|
|:-:|:-:|:-:|:-:|
|1640531527|1640531527|01100001110010001000011001000111|0x61C88647|
|-1640531527|2654435769|10011110001101110111100110111001|0x9E3779B9|
所以兩種相乘的答案雖然會以截然不同的面貌存在記憶體中，但就二補數的電腦數值系統而言，它們所表達的數「值」是相同，只差了 sign ，也因此並不影響 hash 的 distribution 。
另外雖然 2654435769 並不是文章中給出的 2654435761 ，但是它更接近於我們期望的 0.618033989 ：
```shell
(gdb) p (double)2654435769/4294967296
$2 = 0.6180339886341244
(gdb) p (double)2654435761/4294967296
$3 = 0.61803398677147925
```
### map_get()
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
該函式去 `map` 中尋找是否有符合 `key` 值的 entry ，若有便將該 entry 的 `data` 讀出來。
### map_add()
```c=
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
}
```
首先 3 至 7 行直接到 `map` 當中查找，若已存在該 key 則不增添新節點，反之進入新增節點的程序。
```graphviz
digraph {
check [label="於 map 中尋找 key"];
add [label="新增節點"];
node [shape=none];
return;
check -> add [dir=forward, xlabel="not found"];
check -> return [label="已經有了"];
}
```
以下舉例說明新增節點的過程：
Suppose $\mathrm{hash}(\mathrm{key}) = 1$
```graphviz
digraph {
rankdir = LR;
node [shape=record];
heads [label="<first>[0]|<second>[1]|[2]|[3]"];
node [color=red];
kn [label="<body>|{<p>pprev|<n>next}"];
node [shape=none];
ht; h;
knptr [label="kn"];
ht -> heads:first;
h -> heads:second;
knptr -> kn;
}
```
假設 `[1]` 原為
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "[1]";
}
a [label="<body>a|{<p>pprev|<n>next}"];
node [shape=none];
none1 [label=""];
edge [weight=3 style="invis"];
first -> a;
edge [weight=2 style=""];
first -> a:body;
a:p -> first;
a:n -> none1 [arrowhead=dot];
}
```
現在我們希望將 `kn` 所指到的節點放進這條 list ，最便利的方法是直接塞在最前方
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "[1]";
}
a [label="<body>a|{<p>pprev|<n>next}"];
node [color=red];
kn [label="<body>|{<p>pprev|<n>next}"];
node [shape=none];
none1 [label=""];
edge [weight=3 style="invis"];
first -> kn -> a
edge [weight=2 style=""];
first -> kn:body;
a:p -> kn:n;
a:n -> none1 [arrowhead=dot];
edge [color="blue"];
kn:p -> first;
kn:n -> a:body
}
```
圖中黑色的連線已由程式碼第 14 及 15 行完成，因此另外兩條藍色的連線即為我們在 `AAA` 和 `BBB` 需要達成的功能。
### map_deinit()
```c=
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
`map_deinit()` 的功能為刪除掉整個 hash table ，其運作流程大致如下圖
```flow
st=>start: 進入 map->ht 陣列
op1=>operation: 前往陣列的下一項
op2=>operation: 刪除首節點
cond1=>condition: list 裡有無內容
cond2=>condition: 已走訪完陣列
e=>end: free(map)
st->op1->cond1->op2->cond1->cond2
cond1(yes)->op2
cond1(no)->cond2
cond2(yes)->e
cond2(no)->op1
```
接著圖解內層迴圈的行為，假設程式在某個時候執行到第 8 行
```graphviz
digraph {
rankdir = LR;
node [shape=record];
heads [label="<first>[0]|[1]|<now>[2]|[3]"];
a [label="<body>a|{<p>pprev|<n>next}"];
b [label="<body>b|{<p>pprev|<n>next}"];
c [label="<body>c|{<p>pprev|<n>next}"];
node [shape=none];
ht;
none1 [label=""];
node [fontcolor=red];
p;
h [label="head"];
edge [weight=3 style="invis"];
heads:now -> a -> b ->c;
edge [weight=2 style=""];
ht -> heads:first;
h -> heads:now;
p -> a;
heads:now -> a:body;
a:n -> b:body;
b:n -> c:body;
c:n -> none1 [arrowhead=dot];
edge [color=blue];
a:p -> heads:now;
b:p -> a:n;
c:p -> b:n;
}
```
在程式執行到第 21 行時會變成
```graphviz
digraph {
compound = true;
subgraph cluster {
rankdir = LR;
node [shape=record];
a [label="<body>a|{<p>pprev|<n>next}"];
node [shape=none label="" width=.1];
none2; none3;
edge [weight=1 arrowhead=dot style=""];
a:p -> none2;
a:n -> none3;
}
rankdir = LR;
node [shape=record];
heads [label="<first>[0]|[1]|<now>[2]|[3]"];
b [label="<body>b|{<p>pprev|<n>next}"];
c [label="<body>c|{<p>pprev|<n>next}"];
node [shape=none];
ht;
none1 [label=""];
node [fontcolor=red];
p; kn;
h [label="head"];
edge [weight=3 style="invis"];
heads:now -> b ->c;
edge [weight=2 style=""];
ht -> heads:first;
h -> heads:now;
p -> b;
heads:now -> b:body;
b:n -> c:body;
c:n -> none1 [arrowhead=dot];
kn -> a [lhead=cluster];
edge [color=blue];
b:p -> heads:now;
c:p -> b:n;
}
```
:::warning
百思不解什麼情況下會出現第 13 行的 condition ，或許與多執行緒有關？
> 看 Linux 核心原始程式碼 `list.h` 對於 `hlist_unhashed` 的註解:
> ```cpp
> /**
> * hlist_unhashed - Has node been removed from list and reinitialized?
> * @h: Node to be checked
> *
> * Not that not all removal functions will leave a node in unhashed
> * state. For example, hlist_nulls_del_init_rcu() does leave the
> * node in unhashed state, but hlist_nulls_del() does not.
> */
> ```
> 然後再翻閱核心文件關於 RCU 對於 reader 的行為
> :notes: jserv
:::
### twoSum()
```c=
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
goto bail;
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
程式運作邏輯可大致理解如下：
```flow
st=>start: 建立 hash table
op1=>operation: 前往陣列的下一項 nums[i]
cond=>condition: 檢查 hash table 中是否
存在 target-nums[i]
op2=>operation: 將 nums[i] 加入 hash table
e=>end: 回傳 index
st->op1->cond->op2->op1
cond(yes)->e
cond(no)->op2
```
成功配對出 `target` 值則達成目標，否則將現值加入 hash table 再繼續往下尋找。
此處使用 hashtable 帶來的主要好處是加快搜尋舊資料的速度，避免一一確認帶來的 $O(n)$ 低效。
### 探討 kernel 中的 hashtable 實作
本題範例與 Linux kernel 中所使用的 hash 結構相同，最大的區別在於 kernel 中有為了++多使用者並行讀寫++的情境設計了另一組 API ，同時在此種情境下的 hashtable 被稱為 *rcu enabled hashtable* 。
==RCU== 的主要概念是將 **更新** 動作拆分成 **移除** 與 **再生** ，原因在於在並行的情境下，若更新在 reader 使用資料時發生，則可能會導致 reader 讀到更新一半的資料，發生非預期的後果； RCU 機制使用 read-side critical section ， reader 只可能讀到完全舊的資料抑或是完全新的資料，如此便不致發生讀取錯誤。
> [What is RCU? – “Read, Copy, Update”](https://www.kernel.org/doc/html/latest/RCU/whatisRCU.html#whatisrcu)
## 測驗 2
```c=
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (COND1) {
/* Remove all duplicate numbers */
while (COND2)
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
```
在遞迴的實作中，程式先確認 `head` 與 `head->next` 是否 duplicate ，若有則進入 while 迴圈刪除這組 duplicate ，此外就繼續遞迴下去。
例如：
```graphviz
digraph{
rankdir = LR;
node [shape=record];
a1,a2,a3 [label="a"];
b;
node [shape=none];
h [label="head"];
h -> a1 -> a2 -> a3 -> b;
}
```
經過 while 後會變成
```graphviz
digraph{
rankdir = LR;
node [shape=record];
a; b;
node [shape=none];
h [label="head"];
h -> a -> b;
}
```
由於第 10 行的遞迴參數是 `head->next` ，因此它會對 b 呼叫遞迴，如此一來便移除了所有重複的 a 。
COND1 及 COND2 都是 duplicate 的判斷式
```c
head->next && head->val == head->next->val
```
### 撰寫非遞迴版本
```c
struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head)
return NULL;
for (struct ListNode **it = &head; *it;) {
if((*it)->next && (*it)->val == (*it)->next->val) {
while((*it)->next && (*it)->val == (*it)->next->val)
*it = (*it)->next;
*it = (*it)->next;
} else {
it = &(*it)->next;
}
}
return head;
}
```
## 測驗 3
### LRUCache
這支程式主要是用 linked list 來實現 cache 的運作，並使用 mod 運算來映射對應的 cache 位置。
cache 的本體結構宣告為
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
```
cache 的 creation 如下
```c=
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
obj->count = 0;
obj->capacity = capacity;
INIT_LIST_HEAD(&obj->dhead);
for (int i = 0; i < capacity; i++)
INIT_LIST_HEAD(&obj->hheads[i]);
return obj;
}
```
大致上就是配置空間和初始化，唯一需要留意的是第 3 行的語法可以依據 `capacity` 的值動態配置 `hheads[]` 的大小。
每個載有資料的節點有結構：
```c
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
比較特別的是節點有 `hlink` 與 `dlink` 兩個用於 linked list 的成員，稍後會解釋為何如此。
### CacheGet()
```c=
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
MMM2 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
第 4 行由輸入 `key` 值對應 cache 的位置。
第 5 行開始明顯是個用來尋找 node 的迴圈，觀察參數的數量與型別，可以推測 `MM2` 應為 `list_for_each_entry()` 。
程式在 `obj->hheads[hash]` list 中尋找，找到之後的行為是回傳 `value` 並將 `dlink` 移到 `obj->dhead` 前方，如果找不到則回傳 -1 。我們可以發現 `obj->hheads[hash]` 這條 list 都沒有被改變。
得知 `obj->hheads[]` 結構是 array of struct list_head ，每一個 element 拖著一條 list ，其中的 node 藉由 `hlink` 成員與對應的 list 互動。所有被放到 cache 的資料都會以節點形式存在 `obj->hheads[]` 的某處，且可以用近乎 $O(1)$ 的速度快速被找到。
```graphviz
digraph {
rankdir = LR;
node [shape=record];
hheads [label="hheads[0]|hheads[1]|hheads[2]|hheads[3]"];
label = "obj->hheads[]";
}
```
For some variable $\text{hash}$,
```graphviz
digraph {
rankdir = LR;
node [shape=record];
h [label="<body>hhead[hash]|{<p>prev|<n>next}"];
a [label="<body>node|{<p>prev|<n>next}"];
node [shape=none];
edge [weight=3 style="invis"];
h -> a;
edge [weight=2 style=""];
h:n -> a:body;
a:n -> h:body;
edge [color=blue];
a:p -> h:body;
h:p -> a:body;
}
```
這裡用的都是 **list.h** 裡一般的 `list` ，所以 `prev` 全部是 direct pointer 。
除了 `hheads[]` 以外，我們的 cache 額外 maintain 了一條 list `dhead` 。由於 `obj->dhead` 這條 list 在每次節點被 access 時都會更動，我們可以猜想它就是用來指示 recently used 的標的。因為資料每次被 access 就會被移到最前方，所以節點位置越靠後表示越久沒被 access 。而每個節點是用 `dlink` 來與 `obj->dhead` 串列互動， ++`hlink` 與 `dlink` 各自獨立、互不干擾++。這就像是一筆資料有兩個分身，一個在 `hheads[]` 中，另一個在 `dhead` 中。
Example for obj->capacity=3 :
```graphviz
graph {
rankdir = LR;
node [shape=record];
h [label="<0>hheads[0]|<1>hheads[1]|<2>hheads[2]"];
edge [weight=3 label="hlink"];
h:0 -- a -- c;
h:2 -- b;
edge [weight=1];
c -- h:0;
b -- h:2;
}
```
```graphviz
graph {
rankdir = LR;
node [shape=record];
edge [weight=3 label="dlink"];
dhead -- c -- b -- a;
edge [weight=1];
a -- dhead;
}
```
此外值得注意的是第 7 行，藉由 `lru->dlink` 的方式快速找到目標節點在 `dhead` 中的分身，我們就不必再於 `dhead` 走訪一次。
### CachePut()
以上圖為例，當又有一筆資料要放進 cache 的時候，節點 `a` 的兩個分身都會被踢出，因為它在 `dhead` 這條串列的尾巴，如此功能便是在 `CachePut()` 實現。
```c=
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
if (obj->count == obj->capacity) {
lru = MMM4(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
lru = malloc(sizeof(LRUNode));
obj->count++;
}
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
```
此函式概略運作邏輯如圖：
```graphviz
digraph{
st [label="CachePut"];
search [label="查詢是否已在 cache 中"];
st -> search;
exist [label="修改 lru->value"];
capcheck [label="cache 是否已滿"];
search -> exist [label="yes"];
search -> capcheck [label="no"];
full [label="踢掉最舊的節點
並換成新的"];
not [label="為 lru 配置空間
並新增到 cache 中"];
capcheck -> full [label="yes"];
capcheck -> not [label="no"];
}
```
第 5 行依據 `key` 尋找節點是否已存在，因此 `MM3` 顯然也是 `list_for_each_entry()` 。
根據流程圖可以分成 3 個分支討論
- (yes)
- (no, yes)
- (no, no)
#### (yes)
如果有找到的話就更新 `dlink` (recently used) ，並修改節點的 `value` 值。
#### (no, yes)
使用 `obj->count` 來計數是否已達 cache 容量上限 。
在空間已滿的情況下，我們的 policy 是移除 least recently used 的節點，也就是 `dhead` 的尾節點。
為了避免 `free()` 之後又馬上 `malloc()` ，我們可以回收利用舊節點空間。首先我們得要找到舊節點，取得尾節點可以使用 API `list_last_entry()` ，於是我們解出了 `MM4` 。
接著得將節點從對應的 `hhead[]` 和 `dhead` 中移出，填入新資料之後依據新的 `key` 重新串入 `hheads[hash]` 並移到 `dhead` 最前方。
#### (no, no)
這個分支也相對簡單，就是為資料建構新節點，並更新 `hheads[hash]`, `dhead` 及 `count` 。
### CacheFree()
```c
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
將 `obj` 清空的函式， `MM1` 為 `list_for_each_entry_safe()` ，此 API 有註解
```c
iterate over list entries and allow deletes
```
注意到因為所有進到 cache 節點必定有在 `dhead` 的分身，所以我們不需要去走訪 `hheads[]` 陣列，只要清空 `dhead` 串列就可以釋放完所有的 `LRUNode` 。
且因 `hheads[]` 是隨著 `obj` 動態配置而來，所以我們不應該執行
```c
free(hheads);
```
只要呼叫
```c
free(obj);
```
便能一勞永逸。
### 缺點探討
在 `hlink` 所屬的串列上，我們會進行的操作就是
- 走訪
- 新增
- 走訪後移除
並沒有特別需要 access 尾節點的需求，所以我認為我們沒有必要使用環狀串列，取而代之可以使用 kernel 中 `hlist` 風格 (如測驗 1 ) 的串列，它更便利於從 list 中移除節點。
而 `dlink` 所屬的串列則因頭尾操作的需要，維持 kernel `list` 風格。
### LRU in Linux kernel
對應本題，我找到了 [**linux/lru_cache.h**](https://github.com/torvalds/linux/blob/master/include/linux/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;
};
```
這裡的 `colision` 成員相當於我們的 `hlink` ，使用了 `hlist` 的結構，與我的想法相符； `list` 成員相當於 `dlink` 。
`lc` 應是 `lru_cache` 的縮寫。
:::warning
不確定 element 是怎麼存放資料的，是用內嵌結構或是用 unsigned 儲存指標訊息
:::
```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;
void *lc_private;
const char *name;
/* nr_elements there */
struct hlist_head *lc_slot;
struct lc_element **lc_element;
};
```
在 **lru_cache.h** 中，節點通常不會真的被刪除，而是不斷被移到 `lru_cache` 裡的各個不同串列，見這段註解
```
* .list is on one of three lists:
* in_use: currently in use (refcnt > 0, lc_number != LC_FREE)
* lru: unused but ready to be reused or recycled
* (lc_refcnt == 0, lc_number != LC_FREE),
* free: unused but ready to be recycled
* (lc_refcnt == 0, lc_number == LC_FREE),
*
* an element is said to be "in the active set",
* if either on "in_use" or "lru", i.e. lc_number != LC_FREE.
```
藉此可以推測 `refcnt` 的功能是紀錄該 element 的 user 數量，原意可能是 reference counter 。若沒有 user 使用則會被移到 `lru` 或 `free` 。
為了了解這些函式，得再前往 [**lru_cache.c**](https://github.com/torvalds/linux/blob/master/lib/lru_cache.c)
:::spoiler `lc_get` 的實作函式
```c
static struct lc_element *__lc_get(struct lru_cache *lc, unsigned int enr, unsigned int flags)
{
struct lc_element *e;
PARANOIA_ENTRY();
if (lc->flags & LC_STARVING) {
++lc->starving;
RETURN(NULL);
}
e = __lc_find(lc, enr, 1);
/* if lc_new_number != lc_number,
* this enr is currently being pulled in already,
* and will be available once the pending transaction
* has been committed. */
if (e) {
if (e->lc_new_number != e->lc_number) {
/* It has been found above, but on the "to_be_changed"
* list, not yet committed. Don't pull it in twice,
* wait for the transaction, then try again...
*/
if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
RETURN(NULL);
/* ... unless the caller is aware of the implications,
* probably preparing a cumulative transaction. */
++e->refcnt;
++lc->hits;
RETURN(e);
}
/* else: lc_new_number == lc_number; a real hit. */
++lc->hits;
if (e->refcnt++ == 0)
lc->used++;
list_move(&e->list, &lc->in_use); /* Not evictable... */
RETURN(e);
}
/* e == NULL */
++lc->misses;
if (!(flags & LC_GET_MAY_CHANGE))
RETURN(NULL);
/* To avoid races with lc_try_lock(), first, mark us dirty
* (using test_and_set_bit, as it implies memory barriers), ... */
test_and_set_bit(__LC_DIRTY, &lc->flags);
/* ... only then check if it is locked anyways. If lc_unlock clears
* the dirty bit again, that's not a problem, we will come here again.
*/
if (test_bit(__LC_LOCKED, &lc->flags)) {
++lc->locked;
RETURN(NULL);
}
/* In case there is nothing available and we can not kick out
* the LRU element, we have to wait ...
*/
if (!lc_unused_element_available(lc)) {
__set_bit(__LC_STARVING, &lc->flags);
RETURN(NULL);
}
/* It was not present in the active set. We are going to recycle an
* unused (or even "free") element, but we won't accumulate more than
* max_pending_changes changes. */
if (lc->pending_changes >= lc->max_pending_changes)
RETURN(NULL);
e = lc_prepare_for_change(lc, enr);
BUG_ON(!e);
clear_bit(__LC_STARVING, &lc->flags);
BUG_ON(++e->refcnt != 1);
lc->used++;
lc->pending_changes++;
RETURN(e);
}
```
:::
## 測驗 4
Sign in with Wallet
Connect another wallet