---
# System prepended metadata

title: linux2024-homework2
tags: [Linux Kernel]

---

# 2024q1 Homework2 (quiz1+2)
contributed by < [`SuNsHiNe-75`](https://github.com/SuNsHiNe-75) >

## 第一週測驗題

### 測驗`1`
本測驗是在鏈結串列上實作 quick sort，且是非遞迴版本的，使用==堆疊==來模擬原本的遞迴呼叫。

#### 程式碼解讀

```c 
// variables
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
```
- `begin` 與 `end` 是用來記錄 `pivot` 未完成排序的節點。
- `max_level` 是串列長度的 2 倍。
- `left` 與 `right` 分別存放比 `pivot` 大/小 的節點。
```c
begin[0] = *list;
end[0] = list_tail(list);
```
`begin` 紀錄頭端，而 `end` 紀錄尾端，所以一開始把整個串列視為未完成排序。

```c 
node_t *L = begin[i], *R = end[i];
```
每一輪使用 `L` 和 `R` 此輪要排序的串列的頭和尾端。`i` 是用來告知程式碼目前要處理的未完成排序的串列的所在位置。
##### 此輪有不只一個節點時

```c 
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
如果兩個節點的值不一樣，則代表長度 > 1，即可把第一個節點當作 pivot，也就是 `L` 節點。
接著用 `p` 來走訪整個串列。

```c 
while (p) {
    node_t *n = p;
    p = p->next;    //CCCC
    list_add(n->value > value ? &right : &left, n);
}
```
`p` 會提前跑到下一個節點的位置，有點像 `list_for_each_safe` 的概念。並把目前節點與 `pivot` 比較，大的就加進 `right`；小於等於的加進 `left`。

```c
begin[i] = left;
end[i] = list_tail(&left);         //DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);    //EEEE

left = right = NULL;
i += 2;
```
分好大小邊後，把 `left` 裡面的節點設置為「第 ==i== 個」未處理的串列，把 `right` 裡面的節點設置為「第 ==i+2== 個」未處理的串列。而 `pivot` 設置為「第 ==i+1== 個」未處理的串列。
最後把兩邊清空，調整 `i`，準備下一輪。

##### 此輪 只有一個節點/沒有節點 時
```c
if (L)
    list_add(&result, L);
i--;
```
若此輪只有一個節點，此時它會是所有未完成排序的節點中值最大的，直接將其加到最終串列中。這蠻好理解的，因為每輪結束的時候，`i` 會加 2，代表程式選取 `right` 串列作為下一輪的輸入。

要注意，如果上一輪中，沒有存在比 `pivot` 大的值，那這邊有可能會是空的。

#### 圖解
- 設 `list` 如下：

```graphviz
digraph structs {
    node[shape=plaintext];
    begin_0 [fontcolor="red"];
    end_0 [fontcolor="red"];
    pivot [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "3"];
    struct1 [label= "4"];
    struct2 [label= "5"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }
    begin_0 -> struct0
    end_0 -> struct4
    pivot -> struct0
}
```

- 把 `pivot` 以外的所有節點逐一跟 `pivot` 比較，並分到 `right` / `left` 中。
```graphviz
digraph structs {
    node[shape=plaintext];
    pivot [fontcolor="black"]
    right [fontcolor="blue"]
    left [fontcolor="blue"]
    
    node[shape=box];
    struct0 [label= "3"];
    struct1 [label= "4"];
    struct2 [label= "5"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct2 -> struct1
        struct4 -> struct3
    }
    left -> struct4
    pivot -> struct0
    right -> struct2
}
```

- 把這 3 個串列分別放入 `begin` 與 `end` 正確的位置。下一輪則用 `i == 2` 的位置進行排序。
```graphviz
digraph structs {
    node[shape=plaintext];
    begin_0 [fontcolor="red"]
    begin_1 [fontcolor="orange"]
    begin_2 [fontcolor="purple"]
    end_0 [fontcolor="red"]
    end_1 [fontcolor="orange"]
    end_2 [fontcolor="purple"]
    
    node[shape=box];
    struct0 [label= "3"];
    struct1 [label= "4"];
    struct2 [label= "5"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct2 -> struct1
        struct4 -> struct3
    }
    begin_0 -> struct4
    end_0 ->  struct3
    begin_1 -> struct0
    end_1 ->  struct0
    begin_2 -> struct2
    end_2 ->  struct1
   
}
```
#### 優化方案
- 或許 `begin` 與 `end` 也可以用鏈結串列來儲存?
    - 動機：程式利用 `i` 來存取這兩個陣列，但 `i` 在執行程式的過程中並不會大範圍跳躍，最多連續加 2 而已，可以避免宣告不必要的記憶體空間。

- 使用雙向鏈結串列。

#### 使用 Linux 核心風格的 List API 改寫
:::info
[程式碼](https://github.com/SuNsHiNe-75/LinuxLab_quiz1-2/tree/main/QuickSortImproving)
:::

首先把 `quick_sort.h` 裡面宣告的結構改成用 `list_head`，以及把上個作業的 `list.h` 拿過來使用，有些重複的函式就統一使用內建的 API。
```diff 
  typedef struct __node {
-     struct __node *left, *right;
-     struct __node *next;
+     struct list_head list;
      long value;
  } node_t;
```

:::info
接著是最麻煩的地方，雖然想法很簡單，但是我卻在這邊花了將近半天的時間，期間一直發生 Segmentation fault，非常的折磨人。但沒辦法，菜就多練...
:::


我建立了另一個結構 `begin_t`，它的作用是儲存那些尚未完成排序的串列的 「`head`」，然後再將此節點存入另一個鏈結串列中，==並不像原本的程式碼是用陣列來模擬堆疊==。原諒我不會取名。
```c 
typedef struct begins {
    struct list_head list;
    struct list_head *head;
} begin_t;
```

現在要使用 Linux 的 API，所以變數形態要更換，且因為使用雙向鏈結串列，所以不須留下 `end`。
```diff 
- node_t *begin[max_level], *end[max_level];
- node_t *result = NULL, *left = NULL, *right = NULL;

+ struct list_head *begins = malloc(sizeof(struct list_head));
+ struct list_head *result = malloc(sizeof(struct list_head));
+ struct list_head *left = malloc(sizeof(struct list_head));
+ struct list_head *right = malloc(sizeof(struct list_head));
+ struct list_head *mid = malloc(sizeof(struct list_head));
```
一開始把整個串列的 `head` 放進 `begins` 中。
`now` 是用來模擬堆疊的 `top` 的位置。
`begins` 則是目前==所有==未完成排序的串列所在的堆疊。
```c
begin_t *all = new_begin(*head);
list_add_tail(&all->list, begins);
    
struct list_head *now = begins->next;
```

`now_entry_head` 是這輪要處理的未完成排序的串列的 `head`。
```c
struct list_head *now_entry_head = list_entry(now, begin_t, list)->head;
```
`pivot` 放入中間的串列。
```c 
node_t *pivot = list_first_entry(now_entry_head, node_t, list);
list_del(&pivot->list);
list_add(&pivot->list, mid);
```
中間將資料依照大小區分為 `left` 與 `right` 的過程因為與之前無異，所以省略不提。

因為要依序將 `left`、`pivot`、`right` 放入 `begins` 中，所以會需要額外在堆疊中增加 2 個節點，而 `left` 就會直接將目前正在處理排序的鏈結串列取代，分別 push `pivot` 和 `right`。
注意如果 `left` 或 `right` 裡沒有東西，也會需要 push 空串列的 `head` 進去。
```c 
// 1
list_splice_tail_init(left, now_entry_head);
INIT_LIST_HEAD(left);

// 2            
begin_t *mid_begin = new_begin(mid);
list_add_tail(&mid_begin->list, begins);
INIT_LIST_HEAD(mid);

// 3
begin_t *right_begin = new_begin(right);
list_add_tail(&right_begin->list, begins);
INIT_LIST_HEAD(right);
```

`top` 的指標往上 2 格。`pop` 時則是往下一格。
```c 
// push 2 elements into stack
now = now->next->next;
// pop 1 element out of stack
now = now->prev;
```

操作大致上是這樣，注意當要 pop `begins` 的節點時，由於內部是儲存鏈結串列的頭，所以要記得呼叫 `list_free` 來釋放記憶體空間。

#### 實驗結果
- 原本的程式的記憶體用量

![image](https://hackmd.io/_uploads/HkEBSiFap.png)

- 使用鏈結串列實作堆疊的記憶體使用量

![image](https://hackmd.io/_uploads/SyTzPsFaT.png)

在 100000 筆資料的情況下，用鏈結串列去實作堆疊可以節省約 0.8 MB 的記憶體。

### 測驗`2`
合併串列時，若 run 的數量等於或略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就特別低。
所以要定義 minrun 來控制每個 run 的長度。

而為了避免一開始就掃描整個資料來產生 run， timsort 會用堆疊來暫存 run，運用 `merge_collapse` 函式來達成，該函式的功能如下：
- 檢查 A 的長度要大於 B 和 C 的長度總和
- 檢查 B 的長度要大於 C 的長度

注意合併只能在相鄰的 2 個 run 進行，以確保穩定性。

##### Galloping mode
在合併兩個序列 (A & B) 時，考慮到它們都是已經排序好的數列，因此可以加快比較的過程。

首先尋找 B 的首個元素 ( $B_0$ ) 在 A 中的排序位置，即可確定 A 中有一小段是小於 $B_0$，就不需處理這段，接著再尋找 A 的首個元素在 B 中的排序位置，如此反覆進行。

#### 程式碼解讀

##### `find_run`
如果目前節點比下一個節點大，則代表是降冪排列，需要將序列倒轉。`do while` 迴圈中間在將 `list` 所在節點與 `next` 交換，直到下一個元素大於等於目前元素，或沒有下一元素就停止。
```c 
if (cmp(priv, list, next) > 0) {
    /* decending run, also reverse the list */
    struct list_head *prev = NULL;
    do {
        len++;
        list->next = prev;
        prev = list;
        list = next;
        next = list->next;
        head = list;
    } while (next && cmp(priv, list, next) > 0);
    list->next = prev;
}
```
如果目前是升冪排列，則找到此升冪排列的最後一個元素
```c 
else {
    do {
        len++;
        list = next;
        next = list->next;
    } while (next && cmp(priv, list, next) <= 0);
    list->next = NULL;
}
```
假設有 1 序列如下：
```graphviz
digraph structs {
    node[shape=plaintext];
    prev [fontcolor="black"]
    list [fontcolor="black"]
    next [fontcolor="black"]
    head [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "3"]
    struct1 [label= "2"]
    struct2 [label= "1"]
    struct3 [label= "3"]
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
    }
    {
        list -> struct0
        head -> struct0
        next -> struct1
    }

}
```
做完一次迴圈會變成這樣：
```graphviz
digraph structs {
    node[shape=plaintext];
    prev [fontcolor="black"]
    list [fontcolor="black"]
    next [fontcolor="black"]
    head [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "3"]
    struct1 [label= "2"]
    struct2 [label= "1"]
    struct3 [label= "3"]
    {
        rank="same";
        
        struct1 -> struct2
        struct2 -> struct3
    }
    {
        list -> struct1
        prev -> struct0
        head -> struct1
        next -> struct2
    }

}
```
第二次：
```graphviz
digraph structs {
    node[shape=plaintext];
    prev [fontcolor="black"]
    list [fontcolor="black"]
    next [fontcolor="black"]
    head [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "3"]
    struct1 [label= "2"]
    struct2 [label= "1"]
    struct3 [label= "3"]
    {
        rank="same";
        
        struct1 -> struct0
        struct2 -> struct3
    }
    {
        list -> struct2
        prev -> struct1
        head -> struct2
        next -> struct3
    }

}
```
結束後就會跳出 `while` 迴圈了，最後再設定 `list->next = prev`，與後續操作。
```c 
head->prev = NULL;
head->next->prev = (struct list_head *) len;
result.head = head, result.next = next;
return result;
```
```graphviz
digraph structs {
    node[shape=plaintext];
    prev [fontcolor="black"]
    list [fontcolor="black"]
    next [fontcolor="black"]
    head [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "3"]
    struct1 [label= "2"]
    struct2 [label= "1"]
    struct3 [label= "3"]
    {
        rank="same";
        
        struct1 -> struct0
        struct2 -> struct1
    }
    {
        list -> struct2
        prev -> struct1
        head -> struct2
        next -> struct3
    }

}
```
##### `*merge_collapse`
只要目前有超過 2 個 run，就會持續進行合併操作。
```c 
while ((n = stk_size) >= 2)
```

如果前 4 個 run 中，
- run B 的長度小於等於 run C + run D
- run A 的長度小於等於 run B + run C

就會啟動合併。

```c 
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)))
```
```graphviz
digraph structs {
    node[shape=plaintext];
    A [fontcolor="black"]
    B [fontcolor="black"]
    C [fontcolor="black"]
    D [fontcolor="black"]
    
    node[shape=box];
    struct0 [label= "tp"]
    struct1 [label= "tp->prev"]
    struct2 [label= "tp->prev->prev"]
    struct3 [label= "tp->prev->prev->prev"]
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
    }
    {
        A -> struct3
        B -> struct2
        C -> struct1
        D -> struct0
    }

}
```
怎麼決定要合併哪個 run：
- run B 小於 run D：合併 run B 與 run C
- 否則合併 run C 與 run D
```c 
    if (run_size(tp->prev->prev) < run_size(tp)) {
        tp->prev = merge_at(priv, cmp, tp->prev);
    } else {
        tp = merge_at(priv, cmp, tp);
    }
```
如果只有 2 個 run，且 run C 小於等於 run D，則合併兩者。
```c
} else if (run_size(tp->prev) <= run_size(tp)) {
    tp = merge_at(priv, cmp, tp);
} else {
    break;
}
```

##### `*merge_force_collapse`
這個步驟會強制合併所有的 run，不須檢查要合併的 run 的長度和是否已經大於另一個 run。
注意，這個步驟會讓堆疊中剩下 2 個 run。

##### `timsort`
每次先找到一個 run，將這個 run 放入堆疊中，並將 `list` 指標移到剛剛找到的 run 的後面一個節點，然後觀察堆疊中最上面的 4 個 run，看需不需要合併，走訪完串列後，再將剩下的 run 合併。
```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);
```

#### 優化方案
:::info
[程式碼](https://github.com/SuNsHiNe-75/LinuxLab_quiz1-2/tree/main/TimSortImproving)
:::
我發現在[測驗題目](<https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2>)中的 Galloping mode 方法並沒有實現在原本 timsort 的程式中，因此我選擇改優化這部分。但還沒開始實作就想到一個問題，程式是怎麼不用比較就找到要插入的位置的，所以這個想法先被擱置。

再來程式也沒有考慮到 minrun 的長度來調整每次找到的 run，目前想要改進這方面，但實作上遇到疫點問題，正在調整中。


## 第二週測驗題

### 測驗 `1`

#### 解釋程式碼之運行，並重新填空
:::info
先針對每個函式作簡短說明、填空，大部分的程式碼運作原理寫在「`dfs()` 函式說明處」，最後用==測試程式==來驗證程式碼的正確性。
:::
```c
struct hlist_node {
    struct hlist_node *next, **pprev;
}; // 此段即 Linux 核心之 Hash table 實作中，用以處理 hash 數值碰撞的 hlist_node

struct hlist_head {
    struct hlist_node *first;
}; // Hash table 中的頭節點，唯一代表一 hash 值

static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
} // 初始化 hlist_head 的 *first 指標為 NULL
```
參照 [`hlist_head`/`hlist_node` 結構解析](http://linux.laoqinren.net/kernel/hlist/)。

```graphviz
digraph G {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn1 [label="hlist_node1 | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn1;
    
    hn1:next -> hn2;
    hn1:prev -> map:ht2;
    
    hn2:next -> null;
    hn2:prev:s -> hn1:next:s;
}
```
> 注意：`*pprev` 指向**指著自身節點的指標**；`hlist_head` 中的 `*first` 會指向**鏈表頭之節點**。

```c
#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos; pos = pos->next)
// 走訪該鏈表的所有節點
```
```graphviz
digraph structs {
    rankdir=LR;

    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head |<ht3> |<ht4>..."];
        
    node[shape=box];
    struct0 [label= "pos"];
    struct2 [label= "hlist_node1"];
    struct3 [label= "hlist_node2"];   
    struct4 [label= "hlist_node3"];
    
    node[shape=none]
    null [label=NULL]
    
    {
        rank="same";
        struct0 -> struct2
    }
    map:ht2 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct4 -> null[arrowhead=vee, dir=forward, tailclip=true, arrowsize=1];
}
```
```graphviz
digraph structs {
    rankdir=LR;

    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head |<ht3> |<ht4>..."];
        
    node[shape=box];
    struct0 [label= "pos"];
    struct2 [label= "hlist_node1"];
    struct3 [label= "hlist_node2"];   
    struct4 [label= "hlist_node3"];
    
    node[shape=none]
    null [label=NULL]
    
    {
        rank="same";
        struct0 -> null
    }
    map:ht2 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1];
    struct4 -> null[arrowhead=vee, dir=forward, tailclip=true, arrowsize=1];
}
```
> 第一張圖為迴圈剛開始的狀態；到第二張圖時，走訪終止。

```c
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;
    n->pprev = &h->first;
    h->first = n;
} // 將一新的 hlist_node 插入到一 hlist_head 及「原 *first 指向的節點」中間
```
AAAA 為 **`h->first`**。
運作流程如下一系列圖：設有一 `hlist_node_new` 節點要執行此函式。首先，若該列表是有節點而非 NULL 的，則調整 `h->first->pprev` 指標（如圖二）；接著調整新節點之 `*next` 及 `*pprev` 指標（如圖三）；最後將頭節點之 `*first `指向新節點（如圖四）即可。

```graphviz
digraph add_head {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn1 [label="hlist_node1 | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    hn3 [label="hlist_node_new | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn1;
    
    hn1:next -> hn2;
    hn1:prev -> map:ht2;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
}
```
```graphviz
digraph add_head {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn1 [label="hlist_node1 | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    hn3 [label="hlist_node_new | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn1;
    
    hn1:next -> hn2;
    hn1:prev -> hn3:next;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
}
```
```graphviz
digraph add_head {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn1 [label="hlist_node1 | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    hn3 [label="hlist_node_new | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn1;
    
    hn1:next -> hn2;
    hn1:prev -> hn3:next;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
    
    hn3:next -> hn1;
    hn3:prev -> map:ht2;
}
```
```graphviz
digraph add_head {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn1 [label="hlist_node1 | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    hn3 [label="hlist_node_new | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn3;
    
    hn1:next -> hn2;
    hn1:prev -> hn3:next;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
    
    hn3:next -> hn1;
    hn3:prev -> map:ht2;
}
```

```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) {
        struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
} // 找傳入的 num 值在該鏈表的「位置索引」；若無，則回傳 -1。
```
BBBB 為 **`&heads[hash]`**。
CCCC 為 **`list_entry`**。

```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;
}
```
首先，`pre_low/high` 即該 `*preorder` 之左右範圍；`in_low/high` 同理，為 `*inorder` 之左右範圍。
要知道的是，此測驗一之程式碼即是要重建二元樹，且 dfs 存取順序實際上就是 preorder，所以會傳 `preorder[pre_low]`（表中間節點） 進 `find()`，以尋找該節點在 inorder 中的位置索引 `idx`，找到後「切分左右子樹（`tn->left` 及 `tn->right`）」，分別再對 inorder 的 `in_low ~ (idx-1)` 與 `(idx+1) ~ in_high` 作 dfs。
> 由 preorder 可知哪個節點在上面（越靠前的越上面）、而由 inorder 可知哪個節點靠左（越靠前的越左邊），於是可得知 preorder 的第一個元素一定是 root 的值，且該元素對應到 inorder 後，左邊的值就在左邊，右邊的值就在右邊。
> 接著就將 left 和 right 分別當作新的 root node 下去做即可。
> 遞迴的中止條件是在 inorder 中找不到對應元素。

```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);
}
```
DDDD 為 **`&heads[hash]`**。

```c
static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int 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);

    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}
```
建樹的主要程式碼。其起初會先將 inorder 節點建立一 hash table 以方便 `dfs()` 函式的內部實作，之後再呼叫 `dfs()` 函式，遞迴求出該二元樹並回傳結果。

#### 測試程式及可改進之處
- **測試程式**：[BinaryTreeTesting](https://github.com/SuNsHiNe-75/LinuxLab_quiz1-2/tree/main/BinaryTreeTesting)。
    > 設定一 preorder 及 inorder 的序列，其會有一對應的樹，也會有對應的 postorder 序列。本測試程式即比較 buildTree 後的 postorder，與期望的 postorder 有無差別，若無，表示程式運作無誤。
- **可改進之處**：
    - 用紅黑樹代替鏈表之儲存資料方式：我們都知道，用 Hash table 的話，找特定資料的時間複雜度通常是 $O(1)$，但在最差情況下（目標資料在鏈表尾端），就可能會達到 $O(n)$－因為碰撞發生的時候，要線性查找鏈表以找到目標資料。若用紅黑樹儲存的話，其可以保持樹的高度平衡，來保證在最壞情況下的查找時間複雜度降為 $O(log n)$。
        > 比起 Hash table，紅黑樹在處理碰撞時不用線性查找鏈表，而是透過比較節點值來定位目標資料，所以其在查找上的性能更為穩定，特別是在「處理大量資料」或「碰撞發生頻繁」的情況下，紅黑樹的優勢會更明顯。

#### 探討 Pre-order Walk 
參照 [linux/kernel/cgroup/cgroup.c](https://github.com/torvalds/linux/blob/master/kernel/cgroup/cgroup.c) ，透過 Ctrl-F 搜尋可發現 `css_next_descendant_pre()` 函式實作了 Pre-order Walk。以下即針對該函式進行探討。
> **cgroup** 為何：一種 Linux 核心功能，用於限制、監視和分離一組 process 的資源（如 CPU、記憶體或磁碟 I/O 等）。其允許系統管理員根據需求分配資源，來改善系統的性能和穩定性。

```c
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;
}
```
> `css_next_descendant_pre()`－找到下一個要進行 Preorder Traversal 的後代節點
`@pos`: 當前位置
`@root`: 要走訪其後代節點的 CSS

其用於 `css_for_each_descendant_pre()` 函式－找要訪問的下一個後代節點，以進行 `@root` （(含)第一個要訪問的節點）的後代節點的 Preorder Traversal。

雖然此函式需要 cgroup_mutex 或 RCU read locking，但不需要整個走訪過程都跑在 critical section 裡。 只要 `@pos` 和 `@root` 可訪問，且 `@pos` 是 `@root` 的後代節點，其就會回傳下一個後代節點。

因此，其用於實現對 cgroup 子系統狀態的一種很有效率的 Pre-access traversal。
且在「遞迴訪問 cgroup 的後代來走訪整個 cgroup 樹」的過程中，還保持對 cgroup_mutex 或 RCU read locking 的佔用，確保不會有多餘一個 process 跑進 critical section。

### 測驗 `2`

#### 解釋程式碼之運行，並重新填空
:::info
理解 LRU 後，先針對幾個函式作簡短說明、填空，大部分的程式碼運作原理寫在「`Get()`」及「`Put()`」內，最後用==測試程式==來驗證程式碼的正確性。
:::
首先理解一下此作業之 LRU 定義，參照自 [Least recently used (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU))。
> 每個 items 會有一個 "Age bit" 紀錄其被寫入 Cache line 的時間，當要存取某 item 時發生 Cache miss，會先「取代 Cache line 中擁有最小 Age bit」的 item－白話來說就是其「近期最少用到」。

```c
#define hlist_for_each_safe(pos, n, head)        \
    for (pos = (head)->first; pos && ({          \
                                  n = pos->next; \
                                  true           \
                              });                \
         pos = n)


void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        EEEE = pprev;
}
```
> list 相關的函式與資料結構，運作邏輯大致與 [lab0-c 的 list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 相同，這裡不多加贅述。
> 另外，測驗 `1` 也以理解過 hlist 的一些基本函式，故這裡只看新增的部分。

EEEE 為 **`next->pprev`**。
`hlist_for_each_safe()` 似 list 的 `list_for_each_safe()`。走訪鏈表時，會有一 `n` 來紀錄當前的節點；一 `pos` 來記錄「當前節點的下一個節點（可稱之 safe）」，這樣若當前節點被刪除，走訪仍能繼續執行。
`hlist_del()` 的操作邏輯如下系列圖（假設要刪除 node1），簡單來說就是刪除一個鏈表節點。
```graphviz
digraph hlist_del {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn0 [label="hlist_node0 | {<prev>pprev | <next>next}"];
    
    hn1 [label="hlist_node1(n) | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    node [shape=none]
    null [label=NULL]
    
    map:ht2 -> hn0;
    
    hn0:next -> hn1;
    hn0:prev -> map:ht2;
    
    hn1:next -> hn2;
    hn1:prev -> hn0:next;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
}
```
```graphviz
digraph hlist_del {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn0 [label="hlist_node0 | {<prev>pprev | <next>next}"];
    
    hn1 [label="hlist_node1(n) | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    node [shape=none];
    null [label=NULL];
    
    node [shape=none];
    next [label=next];
    next -> hn2;
    
    pprev [label=pprev];
    pprev -> hn0:next;
    
    map:ht2 -> hn0;
    
    hn0:next -> hn1;
    hn0:prev -> map:ht2;
    
    hn1:next -> hn2;
    hn1:prev -> hn0:next;
    
    hn2:next -> null;
    hn2:prev -> hn1:next;
}
```
```graphviz
digraph hlist_del {
    rankdir=LR;
    
    node[shape=record];
    map [label="hash_table |<ht0> |<ht1> |<ht2>hlist_head2.first |<ht3> |<ht4>..."];
    
    hn0 [label="hlist_node0 | {<prev>pprev | <next>next}"];
    
    hn1 [label="hlist_node1(n) | {<prev>pprev | <next>next}"];
    
    hn2 [label="hlist_node2 | {<prev>pprev | <next>next}"];
    
    node [shape=none];
    null [label=NULL];
    
    node [shape=none];
    next [label=next];
    next -> hn2;

    pprev [label=pprev];
    pprev -> hn0:next;
    
    map:ht2 -> hn0;
    
    hn0:next -> hn2;
    hn0:prev -> map:ht2;
    
    hn1:next -> hn2;
    hn1:prev -> hn0:next;
    
    hn2:next -> null;
    hn2:prev -> hn0:next;
}
```

```c
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;
```

LRU Cache 及 LRU Node 的結構演示如下圖：
> 不太確定能不能這樣畫。

:::info
我繪製的 LRU Cache 及 LRU Node 之結構演示圖是否有問題？
:::

```graphviz
digraph LRUcache {
    node [shape=record];
    rankdir = LR;
    subgraph cluster_a {
        label = LRUCache;
        struct0 [label="capacity"];
        struct1 [label="count"];
        struct2 [label="dhead | {<prev>prev | <next>next}"];
        struct3 [label="<head>hhead[0] | hhead[1] | ..."];
    }
    subgraph cluster_b {
        label = LRUNode1;
        struct4 [label="key1"];
        struct5 [label="value1"];
        struct6 [label="link | {<prev>prev | <next>next}"];
        struct7 [label="node | {<prev>pprev | <next>next}"];
    }
    subgraph cluster_c {
        label = LRUNode2;
        struct8 [label="key2"];
        struct9 [label="value2"];
        struct10 [label="link | {<prev>prev | <next>next}"];
        struct11 [label="node | {<prev>pprev | <next>next}"];
    }
    node [shape=none];
    null1 [label="NULL"];
    null2 [label="NULL"];
    
    struct2:next -> struct6;
    struct6:prev -> struct2;
    
    struct6:next -> struct10;
    struct10:prev -> struct6;
    
    struct10:next -> null1;
    
    struct3:head -> struct7;
    struct7:prev -> struct3:head;
    struct7:next -> struct11;
    
    struct11:prev -> struct7;
    struct11:next -> null2;
}
```
> `capacity`：該 LRU cache 「能紀錄的資料量」
`count`：當前該 LRU cache 紀錄的「資料筆數」
`dhead`：一 Doubly Linked List，將所有資料串接起來
`hhead`：處理碰撞使用的 hlist 結構體陣列

```c
LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct list_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;
}
```
建立一 LRU 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);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}
```
FFFF 為 `link`；GGGG 為 `&cache->link`。
釋放該 Cache 的 dhead 串內，指定 LRU 節點的記憶體空間（`list_head link`）。


```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(IIII, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}
```
HHHH 為 `node`；IIII 為 `&cache->link`。
由此函式可知，其 hash 值是透過「key % 該 cache 之可記錄資料量」計算的。
取得 hash 值後，到該 hash 值對應的 `hhead[hash]` 走訪該鏈表，若有找到對應 key 值，則回傳該節點之 `value`；否則回傳 `-1`，表未有此 key 值。
> 從這裡可揣摩出使用 LRU Cache 的好處及意義－若 hash function 設計得當，找到對應資料需要的時間複雜度會很小；倘若只使用 dhead 雙向鏈結串列，走訪整條串列來找資料會花很久的時間，最差能到 $O(n)$。

```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);
        if (c->key == key) {
            list_move(KKKK, &obj->dhead);
            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;
}
```
JJJJ 為 `node`；KKKK 為 `&c->link`。
先找看看對應 hash 值的 `hhead[hash]` 鏈表內有無對應 key 值之節點，若有找到，將該節點「移到雙向鏈結串列的最前端」，表「**最近使用過**」，並指定該 cache 之 value 為此節點之值（更新其值）；若無對應 key 值之節點，表「**Cache Miss**」，有兩種運作情況：
- 若**快取已滿**，須將「雙向鏈結串列 dhead 最尾端的節點（表 Least Recently Used 節點！）」刪除，並將新節點插入到 hhead 的頭部，同時添加到 dhead 的前面。
- 若**快取未滿**，則創建一個新的節點，並將其添加到 hhead 的頭部，同時添加到 dhead 的最前端，更新快取的 key 值。
    > 故 dhead 中的節點，越尾端表「最近越少用過」。

#### 測試程式及可改進之處
- **測試程式**：[LRUCacheTesting](https://github.com/SuNsHiNe-75/LinuxLab_quiz1-2/tree/main/LRUCacheTesting)。
    > 撰寫一 `checkLRU()` 函式回傳 bool，搭配 `assert()` 以測試 dhead 中的首個元素，是否為最近互動過的 key 值節點。
- **可改進之處**：
    - `lRUCachePut()`：Cache Hit 時，除了將節點移動 dhead 最前端，對應 hash 值的哈希鏈表（`hhead[hash]`）內的對應節點，也應該要移到最前端。
```diff
    if (c->key == key) {
        list_move(KKKK, &obj->dhead);
        cache = c;
+       hlist_del(&c->node);
+       hlist_add_head(&c->node, &obj->hhead[hash]);
    }
```

#### 探討 Linux 的 LRU 相關機制
參照 [Linux Kernel 內存回收機制](http://www.wowotech.net/memory_management/233.html/comment-page-2)。
首先談及 Linux 對 LRU 的實現機制－一對雙向鏈表，`active` 及 `inactive`。顧名思義，比較常用到的 page 會被放到 `active` 鏈表；不常用的 page 則放到 `inactive` 鏈表中。兩列表的 page 可相互轉移，若 `active` 的 page 越來越不常使用，其可能被轉放到 `inactive` 鏈表。
> Linux 在作 Page 回收時，會先從 **`inactive` 鏈表的尾部**開始回收。

每個 zone 有 5 個 LRU 鏈表，用來放不同「最近使用狀態」的 pages：
```c
enum lru_list {
    LRU_INACTIVE_ANON = LRU_BASE,
    LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    LRU_UNEVICTABLE,
    
    NR_LRU_LISTS
};
```
> 其中 INACTIVE_ANON、ACTIVE_ANON、INACTIVE_FILE 及 ACTIVE_FILE 中的 pages 是可以回收的。

另外，為了評估 page 的常用程度，Kernel 引入了 `PG_referenced` 及 `PG_active` 兩個 bits。其核心想法是－其一表示「當前活躍程度」，其一表示「最近是否被引用過」。

![圖片](https://hackmd.io/_uploads/BJq-4Udpa.png)
> Refer from [Linux Kernel 內存回收機制](http://www.wowotech.net/memory_management/233.html/comment-page-2)。

基本上有以下步驟：
1. 如果 page 很常用，設定 PG_active bit，並將其放在 ACTIVE LRU 鏈表；反之在 INACTIVE。
2. 每次存取 page 時，透過 `mark_page_accessed()` 來設定 PG_referenced bit。
3. 使用 `page_referenced()` 函式，透過 PG_referenced bit 以及「由逆向映射提供的信息」來確定 page 常用程度（每次清除該 bit 時都會檢測）。
4. 再次呼叫 `mark_page_accessed()`。此時，如果發現 PG_referenced bit 已被設定，表 `page_referenced()` 沒有作檢查，因此對於 `mark_page_accessed()` 的呼叫比 `page_referenced()` 更頻繁－表該 page 經常被存取。
    > 如果該 page 位於 INACTIVE 鏈表，將其移動到 ACTIVE，此外還會設定 PG_active bit，並清除 PG_referenced bit；
5. 也有可能從 ACTIVE 移到 INACTIVE－在 page 比較不常用時，可能連續呼叫兩次 `page_referenced()` 而途中沒有 `mark_page_accessed()`。

如果存取內存 page 的頻率穩定，表對 `page_referenced()` 和 `mark_page_accessed()` 的呼叫大致上平衡，此時會把 page 放在「當前 LRU 鏈表」。
> 確保了 page 不會在 ACTIVE 與 INACTIVE 鏈表間跳來跳去。

#### Page 回收的實現
Linux 的 page 回收主要有兩種觸發方式：
- 內存嚴重不足。透過 `try_to_free_pages()` 函式來檢查內存區域的 pages。
- 透過後台程序 `kswapd` 來觸發，其會週期性檢查內存夠不夠，若不足，則會觸發 page 回收機制。使用 `balance_pgdat()` 作為媒介。

參照 [linux/mm/vmscan.c](https://github.com/torvalds/linux/blob/master/mm/vmscan.c)。
當呼叫 try_to_free_pages() 時，其會重複呼叫 `shrink_zones()` 和 `shrink_slab()` 來釋放一定數量的 pages（預設為 32 個）。而 `shrink_zones()` 會分別對內存區域列表中的所有區域呼叫 `shrink_node()` 函式－其即是「從內存中**回收較少使用的 pages**」的核心函式。
```c=
static void shrink_node(pg_data_t *pgdat, struct scan_control *sc)
{
	unsigned long nr_reclaimed, nr_scanned, nr_node_reclaimed;
	struct lruvec *target_lruvec;
	bool reclaimable = false;

	if (lru_gen_enabled() && root_reclaim(sc)) {
		lru_gen_shrink_node(pgdat, sc);
		return;
	}

	target_lruvec = mem_cgroup_lruvec(sc->target_mem_cgroup, pgdat);

again:
	memset(&sc->nr, 0, sizeof(sc->nr));

	nr_reclaimed = sc->nr_reclaimed;
	nr_scanned = sc->nr_scanned;

	prepare_scan_control(pgdat, sc);

	shrink_node_memcgs(pgdat, sc);

	flush_reclaim_state(sc);

	nr_node_reclaimed = sc->nr_reclaimed - nr_reclaimed;

	if (!sc->proactive)
		vmpressure(sc->gfp_mask, sc->target_mem_cgroup, true,
			   sc->nr_scanned - nr_scanned, nr_node_reclaimed);

	if (nr_node_reclaimed)
		reclaimable = true;

	if (current_is_kswapd()) {

		if (sc->nr.writeback && sc->nr.writeback == sc->nr.taken)
			set_bit(PGDAT_WRITEBACK, &pgdat->flags);

		if (sc->nr.unqueued_dirty == sc->nr.file_taken)
			set_bit(PGDAT_DIRTY, &pgdat->flags);

		if (sc->nr.immediate)
			reclaim_throttle(pgdat, VMSCAN_THROTTLE_WRITEBACK);
	}

	if (sc->nr.dirty && sc->nr.dirty == sc->nr.congested) {
		if (cgroup_reclaim(sc) && writeback_throttling_sane(sc))
			set_bit(LRUVEC_CGROUP_CONGESTED, &target_lruvec->flags);

		if (current_is_kswapd())
			set_bit(LRUVEC_NODE_CONGESTED, &target_lruvec->flags);
	}

	if (!current_is_kswapd() && current_may_throttle() &&
	    !sc->hibernation_mode &&
	    (test_bit(LRUVEC_CGROUP_CONGESTED, &target_lruvec->flags) ||
	     test_bit(LRUVEC_NODE_CONGESTED, &target_lruvec->flags)))
		reclaim_throttle(pgdat, VMSCAN_THROTTLE_CONGESTED);

	if (should_continue_reclaim(pgdat, nr_node_reclaimed, sc))
		goto again;

	if (reclaimable)
		pgdat->kswapd_failures = 0;
}
```
其第 22 行的 `shrink_node_memcgs()` 會呼叫 `shrink_lruvec()` 及 `shrink_slab()` 等與 page 回收相關的函式，並會直/間接呼叫下列兩函式：
- `shrink_active_list()`： 將某些 pages 移到 active 鏈表。
- `shrink_inactive_list()`：inactive 鏈表中選擇一定數量的 pages 放到一臨時鏈表中，最終呼叫 [page_alloc.c](https://github.com/torvalds/linux/blob/master/mm/page_alloc.c#L2520) 中定義的`free_unref_page_list()` 函式將其回收。
:::info
其中 `shrink_slab()` 為「背景機制為 LRU」的快取回收操作，有興趣的可以再去嗑原始程式碼。
:::

### 測驗 `3`

#### 解釋程式碼之運行，並重新填空
```c
#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

#define __const_hweight16(w) (__const_hweight8(w) + __const_hweight8((w) >> 8))
#define __const_hweight32(w) \
    (__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) \
    (__const_hweight32(w) + __const_hweight32((w) >> 32))
```
這些巨集定義了一些用來計算**對應數字的二進制表示**中「包含多少個位元值為 1」的函式，其可以針對 8-bit、16-bit、32-bit、64-bit 等數字去執行。
> 「有幾個 bit 1」的概念類似權重。

```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)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })
```
CCCC 為 `%`。
此巨集定義，用來「在指定的位圖中，由左至右，查找第 n 個 **set bit**（即位元值為 1 的位元）所對應的索引」。

首先計算字中被設置的位元數目，然後比較以找到第 `num` 個被設置的位元。如果找到了，回傳該位元的索引值；否則，繼續往下個位元找。
> 此函式可處理「跨字節邊界」的情況。

```c
static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & AAAA) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}
```
AAAA 為 `0xffffffff`。
**Find First Set Bit**：傳入一 `word`，經過此巨集，即可找到其「由右至左的第一個（Least Significant）位元為 1 之索引值」。
> 參照 [ffs(3)](https://man7.org/linux/man-pages/man3/ffs.3.html)。

```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`。
傳入一 `addr`，設定其「特定的位元」為 0。

```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}
```
**Find n'th Set Bit**：與 `ffs()` 不同的是，此函式目的是在 `word` 中尋找並回傳「第 n 個被設置過的位元（即位元 1）之索引值」。如果 `word` 中沒有位元被設置過，則回傳 `BITS_PER_LONG`。

其用到 `__ffs()` 來找每次循環中「第一個被設置的位元」，然後將其索引位置存進 `bit` 變數中。一旦 n 的值為 0，則立即回傳當前的 bit 值。否則，用 `__clear_bit()` 清除該位元（成 0），然後 n 減少 1。反覆執行，直到找到第 n 個被設置的位元，最後回傳其索引位置。

> 舉個例子：假設 `word` 的二進位表示為 `11001001`，而我們想要找到第 2 個被設置的位元（即由右至左，找到第 2 個位元 1 的位置）。首先，`__ffs()` 先回傳 0，因為第一個被設置的位元在索引 0 上，然後清除此位元，繼續尋找下一個被設置的位元。照此邏輯，最後會回傳索引值 **3**。

```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}
```
此函式用來「在一個記憶體區域中找到第 n 個被設置的位元的索引位置」。

其會先檢查傳入的 `size` 是否 $\leq$ 機器字長（`BITS_PER_LONG`，透過 `small_const_nbits(size)` 檢查），並且大於 0。
- 如果是，表示位元索引在 `size` 內，這時**可以直接對記憶體中的位元進行處理，而不用跨字節**－先用 `GENMASK()` 設定一個遮罩，把要處理的範圍遮出來；然後，將遮罩後的值傳進 `fns()` 來找第 n 個被設置的位元的索引位置。
- 否則，需要**在處理位元時跨越字節邊界**。需呼叫 `FIND_NTH_BIT()`，來處理跨字節邊界的情況。
> `addr`: The address to start the search at.
`size`: The maximum number of bits to search.
`n`: The number of set bit, which position is needed, counting from 0.

#### Linux 的 `find_nth_bit()` 應用案例之解說與分析
參照 [linux/include/linux/find.h](https://github.com/torvalds/linux/blob/master/include/linux/find.h)，其有該函式之原始碼定義。
嗑了一下程式碼及線上資源，可以大略理解到 `find_nth_bit()` 通常用在處理器排程相關的操作中－透過 CPU mask 等技術實作相關位元操作，來表示程序的 CPU 指定（下面的 *CPU Affinity* 中有更詳細的說明），而要得知某程序中的 CPU 指定狀況，就有可能會需要用到 `find_nth_bit()` 的函式邏輯。
> 而其又牽扯到 **Bitmap** 的使用，詳細可參考如下資料：
    - https://zhuanlan.zhihu.com/p/668567051
    - [linux/lib/bitmap.c](https://github.com/torvalds/linux/blob/master/lib/bitmap.c)

透過對該函式的延伸搜尋，可知其在 Linux 原始程式碼中使用在 [linux/kernel/trace/trace_events_filter.c](https://github.com/torvalds/linux/blob/master/kernel/trace/trace_events_filter.c#L688) 中的 `do_filter_cpumask_scalar()` 函式，而其又是以 `cpumask_nth()` 函式（參照 [linux/include/linux/cpumask.h](https://github.com/torvalds/linux/blob/master/include/linux/cpumask.h#L397)）來呼叫 `find_nth_bit()`－其主要目的就是透過 `find_nth_bit()` 函式，來找尋 cpu mask 中的第 n 個 CPU 之位置。
```c
static inline int do_filter_cpumask_scalar(int op, const struct cpumask *mask,
                                           unsigned int cpu)
{
	switch (op) {
	case OP_EQ:
		return cpumask_test_cpu(cpu, mask) &&
			cpumask_nth(1, mask) >= nr_cpu_ids;
	case OP_NE:
		return !cpumask_test_cpu(cpu, mask) ||
			cpumask_nth(1, mask) < nr_cpu_ids;
	case OP_BAND:
		return cpumask_test_cpu(cpu, mask);
	default:
		return 0;
	}
}
```
```c
static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
{
	return find_nth_bit(cpumask_bits(srcp), small_cpumask_bits, cpumask_check(cpu));
}
```
> 對於 CPU mask 的概念與詳細理解，可參閱 [Linux Kernel：CPU 狀態管理之 cpumask](https://zhuanlan.zhihu.com/p/670194359)。
> 利用 struct cpumask 這個 bitmap 來代表系統當中 CPU 的集合，每個 bit 代表一個 CPU，其中只有 `nr_cpu_ids` 個位元是有效的。

#### CPU Affinity
其又稱 Processor Affinity。
指在 Linux 中，process 想儘量長時間運行在某個指定的 CPU 上 ，且不被轉移至其他 CPU 的傾向性。

在 Symmetric Multi-Processing 的架構下，Linux 排程器會根據 CPU Affinity 的設置，讓指定的程序運行在「指定」的 CPU 上，而不會在別的 CPU 上運行。
> 如此，表程序不會在處理器之間頻繁移動，其產生的負載較小。

CPU Affinity 會用 bitmask 表示，每個位元表一個 CPU，若為 1，則表示「已指定」。
最低位元表第一個 CPU；最高位元則表最後一個 CPU。
> 舉個例子（用十六進制表示）：
`0x00000001` 表指定*處理器 1*；
`0xFFFFFFFF` 表指定*所有處理器（0~31）*。

參照 [linux/kernel/sched/core.c](https://github.com/torvalds/linux/blob/master/kernel/sched/core.c#L8396)，其檔案內容與處理排程非常相關，其中有 `sched_setaffinity()` 函式也用到了 CPU mask 的概念，而這也是使用到 `find_nth_bit()` 的前置步驟－沒有處理器遮罩，就不會有相關位元操作來找 CPU 了。

又一函式（系統呼叫，參照 [`SYSCALL_DEFINE3()`](https://github.com/torvalds/linux/blob/master/kernel/sched/core.c#L8461)）使用到 `sched_setaffinity()` 函式。根據其原文註解（`set the CPU affinity of a process`），這裡就是前面提到可指定 CPU Affinity 的地方了。

```c
long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
{
	struct affinity_context ac;
	struct cpumask *user_mask;
	int retval;

	CLASS(find_get_task, p)(pid);
	if (!p)
		return -ESRCH;

	if (p->flags & PF_NO_SETAFFINITY)
		return -EINVAL;

	if (!check_same_owner(p)) {
		guard(rcu)();
		if (!ns_capable(__task_cred(p)->user_ns, CAP_SYS_NICE))
			return -EPERM;
	}

	retval = security_task_setscheduler(p);
	if (retval)
		return retval;

	/*
	 * With non-SMP configs, user_cpus_ptr/user_mask isn't used and
	 * alloc_user_cpus_ptr() returns NULL.
	 */
	user_mask = alloc_user_cpus_ptr(NUMA_NO_NODE);
	if (user_mask) {
		cpumask_copy(user_mask, in_mask);
	} else if (IS_ENABLED(CONFIG_SMP)) {
		return -ENOMEM;
	}

	ac = (struct affinity_context){
		.new_mask  = in_mask,
		.user_mask = user_mask,
		.flags     = SCA_USER,
	};

	retval = __sched_setaffinity(p, &ac);
	kfree(ac.user_mask);

	return retval;
}
```