# 2024q1 Homework2 (quiz1+2)
contributed by < nelson0720j >
## 第 1 周測驗題
### 測驗一
#### 解析
node_t 結構
```clike
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph node_t {
node [shape = record]
struct1 [label = "left|value|right|<next>next"];
struct2 [label = "left|value|right|<next>next"];
struct1:next -> struct2
}
```
#### 解題
1. list_tail
```clike
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA); // *left->next
return *left;
}
```
目標: 找出鏈結串列的最後一個節點，並輸出指向他的指標
`*left` 不斷指向他的 `next` 所指向的節點，直到這個節點不存在為止。
2. list_length
```clike
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB); // (*left)->next
}
return n;
}
```
同上述，不斷更新 `*left` 所指向的節點，每往下移長度就加一。
3. iterative Quicksort
```clike
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
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 (i >= 0) {
node_t *L = begin[i], *R = end[i];
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 = CCCC; // p->next
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = DDDD; // list_tail(&left)
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE; // list_tail(&right)
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
首先， `pivot` 設為最左邊的點， `p` 為 `pivot` 的下一個節點。依序看 `p` 的 `vlaue` 是否比 `pivot` 的 `value` 還大， 若大於則加到 `right` 的鏈結串列中，反之，則加到 `left` 的鏈結串列中。
接下來，會分成三個鏈結串列。begin[0] 及 end[0] 紀錄 left 頭及尾端節點， begin[1] 及 end[1] 紀錄當前 pivot 節點，begin[2] 及 end[2] 紀錄 right 頭及尾端節點。
最後，迭代操作，直到分開的三個鏈結串列都只有一個節點，依序將節點加入到 `result` 。
### 測驗二
Timsort
#### 解析
#### 解題
1. merge
merge之實作
```clike
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; // &head
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB; // &a->next
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = CCCC; // &b->next
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
將 `tail` 指向 `head` 來達成首尾相接
```graphviz
digraph G {
node [shape=box];
rankdir = LR
head [label="struct list_head *head"];
tail [label="struct list_head **tail"];
tail->head;
head->"";
}
```
接著，比較 a 和 b 所指向節點的值，若 a 小於或等於 b ，則將 a 加入 `head` 所指向的新佇列，反之，則將 b 加入。
2. build_prev_link
建立雙向循環鏈表的前向和後向鏈接。
```clike
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
EEEE = tail; // head->prev
}
```
```graphviz
digraph G {
node [shape=box];
rankdir = LR
head [label="struct list_head *head"];
tail [label="struct list_head *tail"];
list [label="struct list_head *list"];
tail -> list; // tail->next = list
list -> tail; // list->prev = tail
list:se -> head:sw;
head:nw -> list:e;
tail -> head; // Final circular links
head -> tail;
}
```
3. timsort
```clike
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) { // 1
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
`find_run` 找出適合的遞增 run ，再將 `tp` 指向當前 run 的頭節點。
`merge_collapse` 執行合併操作，合併最小的兩個 run 。
`merge_force_collapse` 會持續合併，直到 stk_size < 3 (也就是小於 3 個 run )，如果有 1 個 run ，則 `build_prev_link` ， 2 個則 `merge_final`。
## 第 2 周測驗題
### 測驗一
#### 結構
```clke
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
[Linux 核心的 hash table 實作](/rpIi8FeqQ9eBJ-UTFgb--A)
`hlist_node` 結構為一個雙向鏈結串列， `next` 指標指向下一個節點本身， `pprev` 為指向指標的指標，存 `&next` 指向前一個節點的 `next` 指標
```graphviz
digraph node_t {
node[shape="record"];
rankdir=LR;
splines=false;
list_head[label="<h>list_head|<f>first"];
hlist_node1[label="<n1>node1|{<p>pprev|<n>next}"]
hlist_node2[label="<n2>node2|{<p>pprev|<n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> hlist_node1-> hlist_node2[
weight = 10, style=invis
]
list_head:f->hlist_node1:n1;
hlist_node1:p->list_head:f;
hlist_node1:n->hlist_node2:n2;
hlist_node2:f->hlist_node1:n;
hlist_node2:n->NULL;
}
```
#### 測驗
1.
```clike
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; //h->first
n->pprev = &h->first;
h->first = n;
}
```
目標為: 將新節點 `n` 加到串列前面。
先檢查 `h` 的成員 `first` 是否非空，若為空，將原先 `h` 的 `pprev` 所指向的節點( `node2` )的 `pprev` 指向要加入的 `n` 的 `next` 。
```graphviz
digraph node_t {
node[shape="record"];
rankdir=LR;
splines=false;
list_head[label="<h>h|<f>first"];
hlist_node1[label="<n1>n|{<p>prv|<n>next}"]
hlist_node2[label="<n2>node2|{<p>prv|<n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> hlist_node1-> hlist_node2[
weight = 10, style=invis
]
hlist_node2:p->hlist_node1:n[color="red"];
hlist_node2:n->NULL;
}
```
再將 `n` 的 `next` 指向 `h` 的 `first` 原先指向的節點，即可完成 `n` 和原先第一個節點 `h->first` 的雙向鏈結。
```graphviz
digraph node_t {
node[shape="record"];
rankdir=LR;
splines=false;
list_head[label="<h>h|<f>first"];
hlist_node1[label="<n1>n|{<p>pprev|<n>next}"]
hlist_node2[label="<n2>node2|{<p>pprev|<n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> hlist_node1-> hlist_node2[
weight = 10, style=invis
]
hlist_node2:p->hlist_node1:n;
hlist_node1:n->hlist_node2:n2[color="red"];
hlist_node2:n->NULL;
}
```
因此 `AAAA` 為 `h->first` 。
2.
```clile
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);
if (num == on->val)
return on->idx;
}
return -1;
}
```
此函式功用為找尋串列中是否有結構的值和參數 `num` 一樣，若有則回傳此節點的 `index` 。
`hlist_for_each` 傳入根據 mod 後的結構位址，因此 `BBBB` 為 `&head[hash]`。
接著要取得這個結構的值來比對，這裡用一個結構 `order_node` 來取得值和索引，透過傳入結構，指標和成員來取得這個結構 `order_node` 的位址。
因此 `CCCC` 是 `list_entry` 。
3.
```clike
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` 他需要的參數為 `hlist_head *` ，因此根據 `hash` ，傳入目標位址。
`DDDD` 為 `&heads[hash]` 。
#### 延伸問題
* Linux 核心的 cgroups 相關原始程式碼
根據 [kernel.docs](https://docs.kernel.org/admin-guide/cgroup-v1/cgroups.html)
>Control Groups provide a mechanism for aggregating/partitioning sets of tasks, and all their future children, into hierarchical groups with specialized behaviour.
[cgroups](https://github.com/torvalds/linux/blob/005f6f34bd47eaa61d939a2727fc648e687b84c1/include/linux/cgroup.h#L240) 作用為限制，控制與隔離 Process 所使用到的系統資源。
cgroup 內可以有多個 subsystems ，各個 subsystem 分別對 cpu, memory, network 等去進行控制。</br>
cgroup 可以以階層結構 ( Hierarchical Organization ) 的方式組織和管理，其子節點預設繼承父節點的屬性，形成一個 forest 的結構。
更多請見 [cgroup v1 和 v2 介紹](https://medium.com/starbugs/%E7%AC%AC%E4%B8%80%E5%8D%83%E9%9B%B6%E4%B8%80%E7%AF%87%E7%9A%84-cgroups-%E4%BB%8B%E7%B4%B9-a1c5005be88c) ， [v2 kernel.docs](https://docs.kernel.org/admin-guide/cgroup-v2.html) 。
在此先觀察 cgroup v1 的 pre-order walk 程式碼，
```clike
#define css_for_each_descendant_pre(pos, css) \
for ((pos) = css_next_descendant_pre(NULL, (css)); (pos); \
(pos) = css_next_descendant_pre((pos), (css)))
```
上述程式碼會用 pre-order 的方式走過 css ( cgroup subsystem ) 的後代，並且提到會在依序走過樹的時候使用 `cu_read_lock()` 的函式作同步控制，確保狀態更新的一致。
另外，在 [`cgroup-defs.h`](https://github.com/torvalds/linux/blob/005f6f34bd47eaa61d939a2727fc648e687b84c1/include/linux/cgroup-defs.h) 中的 `struct cgroup_subsys_state` 有提到保存 css 狀態的結構，方便管理整個樹狀的結構。
### 測驗二
LRU可能的合法 C 程式實作
1.
```clike
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
解釋:
`**pprev = n->pprev` 為將 `pprev` 指標指向 `n` 的 `pprev` 指標所指向的 `next` 指標，即 `pprev` 存 `&(n->pprev)` 。
解題:
先將 `n` 節點的前一個節點的 `next` 指向 `n` 的下一個節點(即 `n->next` ) 。
接著將 `n` 的下一個節點的 `pprev` 指向 `n` 的前一個節點的 `next` ，即可跳過節點 `n` ，達成類似刪除節點 `n` 的效果(實際上 `n` 節點仍存在)。
`EEEE` 為 `next->pprev` 。
2.
```clike
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);
free(cache);
}
free(obj);
}
```
`list_entry` 的第三個參數是第二個參數型態的成員，因此根據以下 `LRUNode` 結構，可能成員為 `node` 或 `link`
```clike
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
且根據 `struct list_head *pos` pos指標需要存一個 `list_head` 型別，
因此 `FFFF` 為 `link`。
找到結構位址後，用 `list_del()` 刪除結構，參數為 `struct list_head *entry` ，因此 `GGGG` 為 `&cache->link` 。
最後再釋放 `cache` 所指向的整個結構。
3.
```clike
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(IIII, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
解釋:
函式功能為獲取指定 key 的 value，並將最近使用過的節點，也就是符合 `key` 值的點，透過 `list_move` 移動到串列頭，以此代表最近使用過，來實現 LRU 。
解題:
`pos` 為 `hlist_node *` 型別，因此 `HHHH` 為 `node` 。
`void list_move(struct list_head *entry, struct list_head *head)` 需傳入 `list_head` 型別，因此 `IIII` 為 `&cache->link`。
4.
```clike
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);
if (c->key == key) {
list_move(KKKK, &obj->dhead);
cache = c;
}
}
#以下省略
}
```
這個函式用於將一個鍵值對放入LRU快取中。根據LRU快取的特性，如果快取已滿且新的鍵值對要放入，則應該淘汰最近最少使用的鍵值對。
`JJJJ` 為 `node` ，`KKKK` 為 `&c->link` 。
#### 延伸問題
1. 解釋程式碼
結構:
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
subgraph cluster_0 {
node1 [label="capacity|count|{dhead|<h>hhead[]}"];
label = "LRUCache";
}
map [label="<f>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
node1:h->map:f
}
```
2. 在 Linux 核心找出 LRU 相關程式碼並探討
[lru_cache](https://github.com/torvalds/linux/blob/master/lib/lru_cache.c)
`struct lc_element`: 代表快取中的一個元素。
`struct lru_cache`: 代表整個 LRU 快取。
`lc_create`: 用於初始化 LRU 快取。
`lc_get`: 通過標籤獲取元素，並可能改變活動集。
`lc_put`: 減少元素的引用計數，並在引用計數為零時將其移到 LRU 列表中。
### 測驗三
## 參考資料
[作業要求](https://hackmd.io/@sysprog/BkmmEQCn6)
Sign in with Wallet
Connect another wallet