# 2024q1 Homework2 (quiz1+2)
contributed by < `rain20010126` >
## 課程理解與疑問
### Linux 核心原始程式碼巨集: container_of
1對於一個結構體，裡面的元素因為編譯器 `alignment` 的需求，裡面的元素不一定會按照記憶體的順序進行排列，實際跑過以下程式碼，可以發現輸出的 `c=` 並不符合預期，接著程式碼第 15 行的輸出可以看到 `p` 和 `x.c` 的輸出並不相同
```c=
#include <stdio.h>
struct data {
short a;
char b;
double c;
};
int main() {
struct data x = {.a = 25, .b = 'A', .c = 12.45};
char *p = (char *) &x;
printf("a=%d\n", *((short *) p));
p += sizeof(short);
printf("b=%c\n", *((char *) p));
p += sizeof(char);
printf("c=%lf\n", *((double *) p));
printf("p=%p, &x.c=%p\n", p, &(x.c));
}
```
為了提升程式碼的可攜性， `ofsetof` 可以接受給定成員的型態 `TYPE` 以及成員的名稱 `MEMBER` ，傳回**成員的位置減去 struct 的位置**，也就是兩者之間的距離
```c
#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)
```
接著巨集 **`container_of`** 根據 `offsetof` 的基礎上擴充為輸入給定 struct 成員的位址 `ptr` 、 struct 的型態 `type` ，以及該成員的名稱 `member` ，最後回傳此 struct 的位址
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *(__pmember) = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
### 你所不知道的 C 語言: bitwise 操作
### 你所不知道的 C 語言：記憶體管理、對齊及硬體特性
#### Cache 理解
`cache` 為一個速度較快但容量較小的儲存空間，他的成本比較低，能減少資料存取時的延遲時間，而 `cache` 中還有在做不同層級的分類( L1 cache 、 L2 cache 等等)
#### aligment
因為 CPU 在擷取資料時不黑只擷取 1 byte 的資料，常常會多個 byte 進行擷取，假設一次擷取 4 byte ， `int` 得大小假設也是 4 byte， 這時如果有使用 `4 byte aligment` ，也就是將整數對其在記憶體中 4 的倍數上，就可以進行一次擷取獲得完整的 `int`，若沒有做，就有可能在擷取的 4 byte 中沒有包含一個完整的 `int` 資料，就會需要多進行一次的擷取，降低電腦的效能
#### 其他
`overcommit` : 過度承諾配置記憶體
## 第一週測驗題
### 測驗一
#### **程式運作原理**
首先是程式碼對應的操作函式
以下函數為找出單向鏈結串列的尾部節點，由次可知 `AAAA` 部分需要將 `left` 更新為下一個節點，因此 `AAAA` 為 `(*left)->next`
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
以下函數為算出鏈結串列的長度， `BBBB` 部分需要不斷更新至下一個節點，並在更新的同時將計算節點數量的 `n` 的數值+1，因此 `BBBB` 和 `AAAA` 的結果相同，皆為 `(*left)->next`
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
接著為作者實作排序的過程，由作者的說明和圖例，可以得知此段程式碼在執行的是實作非遞迴 (non-recursive; iterative) 的快速排序法 ，以下為其原理
`quick_sort` 函數的實作過程如下，假設以下為需要進行排序的陣列，首先以第一個元素 `4` 作為 pivot ，另外會由最左側 L (也就是數字1處)向右檢查比 pivot 小的節點，若是小於則加入到 `left` 串列中，若是比 pivot 大的節點，則加入到 `right ` 串列中
```graphviz
digraph {
node [shape=box];
rankdir = LR;
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=15];
7 -> NULL;
node [fontcolor=red];
pivot -> 4;
rank=same {pivot 4 };
node [fontcolor=green];
L ->1;
rank=same {L 1};
R ->7;
rank=same {R 7};
}
```
接著由下方函數可知，當檢查到的元素 p 若是大於 pivot，則會將結點加入到 `right` 串列，若是小於則加入到 `left` 串列內，另外 `begin[i]` 為 `left` 頭部位置，而 `end[i]` 為其尾部位置， `begin[i + 1]` 以及 `end[i + 1]` 為 pivot 元素，最後 ` begin[i + 2]` 為 `right` 串列的頭部位置， `end[i + 2]` 則為其尾部位置。
經過第一次 iteration 後的結果如以下
```graphviz
digraph {
node [shape=box];
rankdir = LR;
7->5;
4;
2 -> 3 -> 1;
node [fontcolor=black];
node [shape=plaintext, fontsize=15];
left ->2;
pivot->4;
right->7;
}
```
```c
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;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
```
首先由程式邏輯可知， `CCCC` 處需指向下一個節點，也就是 `p->next` ， `DDDD` 處與 `EEEE` 處分別為 `left` 和 `right` 串列的尾部位置， 由此可知遮蔽部分分別為 `list_tail(&left)` 和 `list_tail(&right)`
接著可以看到迴圈的部分中 `i+=2` 的部分，表示會將繼續對 `right` (`node_t *L = begin[i], *R = end[i];`, i=2 代入) 串列進行分類， pivot 元素一樣是串列的開頭位置，結果如以下
```graphviz
digraph {
node [fontcolor=black];
node [shape=plaintext, fontsize=15];
right->Null;
node [shape=box];
rankdir = LR;
7;
5;
node [fontcolor=black];
node [shape=plaintext, fontsize=15];
left ->5;
pivot->7;
}
```
再次對節點 NULL 進行分割會出現不滿足 `L != R` 的條件，因此會進入 `else` 內，接著同樣不滿足 `if(L)` 的條件，執行 `i--` ，也就是回到先前的 pivot 元素7，對其進行分割，同樣不滿足 `L != R` 的條件因此進入到 `else` 部分，將最大的元素7加入到 `result` 中，並執行 `i--` ...
#### 使用 Linux 核心風格的 List API 改寫上述程式碼
- quicksort 中 pivot 的選擇十分重要，在以上程式碼可看出， pivot 皆是挑選串列中最左側的元素，有無更好的選擇方式？
- 在配置 begin 和 end 的陣列的空間時是考慮最差的情況進行配置的，有無其他更好的方法？
以下是進行十次運算後取平均的比較結果
時間單位：sec
| 資料長度 | 10 | 100 | 1000 | 10000 | 100000 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| pivot 固定 | 0.0000003 | 0.0000293 | 0.0053396 | 0.2443159 | 22.7133486 |
### 測驗二
**程式運作原理**
由題目說明可知程式碼在實作 Tim Peter 所提出的 `Timsort` 排序法，首先需要了解的是此排序方法是應對現實世界中的序列大多都是已經部分排序的情況
**`merge`** ：本函式的作用是將兩串列進行 merge ， `AAAA` 處是對 tail 進行初始，所以其為 `&head` ，接著會不斷更新 `tail` 的位置，將兩個串列中較小的元素加入到回傳的串列中， `BBBB` 和 `CCCC` 處則會對 tail 進行更新， 分別為 `&a->next` 和 `&b->next`
```c
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;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = CCCC;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
**`build_prev_link`** ：此函式則是將原本串列修改成雙向循環的串列，同時在其尾端加入剩下的 `list` 和新增 `prev` ，`DDDD` 和 `EEEE` 是確保將最後一個元素的 next 指向第一個元素，第一個元素的 prev 指向最後一個元素，因此其分別為 `tail->next` 和 `head->prev`
**`merge_final`** ：將兩個串列合併成一個，並修改每個節點的 `prev` ;
**`find_run`** ：此函式的目標是在雙向鏈表中尋找一個遞增或遞減的 `run` ， 首先 if 中的 do while 迴圈的目標是找出遞減的 run ，同時使用 `list->next = prev` 不斷將新的節點的 next 指向前一個較大的節點，也就是 prev，達成反轉順序的效果，將其修改成小到大的排列方式， else 中的 do while 迴圈則是找出遞增的 run ，並維持小到大的排列方式，當完成該次的 run 後，會做特別的操作 `head->next->prev = (struct list_head *) len;` 將長度訊息儲存在第二個節點的 `prev` 中，回傳的 `result.head` 為串列的頭部位置， `result.next` 則為其尾部位置
**`merge_at`** ：將 `at` 與 `at->prev` 做 merge ，最後將堆疊的數量減一
**`merge_force_collapse`**：在最後合併時所用，讓堆疊的數量 (run) 變成 2
**`merge_collapse`** : 本函式目標是合併，while 中的合併的條件由題目可知如以下：
1. A (tp->prev->prev) 的長度要大於 B (tp->prev) 和 C (tp) 的長度總和。
2. B 的長度要大於 C 的長度。
當不滿足以上條件時，會再比較 A 和 C 的大小，將較小的與 B 做合併
**其中我疑惑的部分**是以下條件，**不了解**需要以下兩個條件的原因(會再嘗試理解)
```
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)))
```
**`timsort`** ： 最後本次實作 Timsort 的邏輯如下
1. 將原雙向鏈接修改成單向鏈接
2. 在 do while 迴圈內，不斷使用 `find run` 找出新的 run ，並使用 `merge_collapse` 將 run 合併直到 list 至尾端，同時如果不滿足堆疊頂端的 3 個 run 的原則時，即呼叫 `merge_at` 函式進行合併，合併的過程中會使用 `merge` 函式進行排序，合併出的 run 為排序好的，重複執行迴圈直到鏈接尾端
3. 將原先的鏈接區分完所有的 run 後，使用 `merge_force_collapse` 進行最後的合併，將堆疊的數量 (run) 控制在2，合併的過程同樣呼叫 `merge_at` 函式並使用 `merge` 函式進行排序
4. 此時如果堆疊的數量 (run) 只剩下一個的話，也就是 `FFFF` 為 1，則透過 `build_prev_link` 將鏈接修改成雙向的，若是剩下 stk1 和 stk0 則使用 `merge_final` 進行最後的合併，此函式中包含 `build_prev_link` 同樣會將鏈接修改成雙向的
```c=
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) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
**以上程式碼我有疑惑的點是程式碼第 26~28 行的作用為何**（會再嘗試理解），當程式碼執行到第 23 行時 `merge_force_collapse` 會使 stk_size<3 ，也就是 1 或 2 ， 我目前的理解是最多只會有兩個鏈接，因此第27行的條件不會成立
## 第二週測驗題
### 測驗一
題目程式碼是將所提供的 preorder 序列與 inorder 序列重構二元樹
因為不理解程式碼的邏輯，我決定先查看 [youtube](https://www.youtube.com/watch?v=ihj4IQGZ2zc) 對於 [此題leetcode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/) 的說明，來幫助我理解程式碼，以下是我在觀看完後對於此問題的理解
1. `preorder` 的第一個元素為 `root` ，也就是 `3`
```graphviz
digraph BinaryTree {
3;
node [shape=plaintext, fontsize=15];
root -> 3;
}
```
2. 再來可以看到 `inorder` 序列， `root` 元素以前的(也就是 `9`) ，即為 `2` 的左子樹， `root` 元素以後(也就是 `15`、`20`、`7`)的即為 `2` 的右子樹，並分別取得子樹的長度
```graphviz
digraph structs{
node[shape=record];
lpre[label=<9>];
lin[label=<15|20|7>];
node [fontcolor=black];
node [shape=plaintext, fontsize=15];
left_subtree->lpre;
right_subtree->lin;
}
```
3. 接下來分別對 `2` 的左右子樹做以上操作
4. 先對左子樹，可以得知子樹的長度為 1 ，因此 `9` 即為左子樹；右子樹則長度為 3
5. 再回到先前的 `preorder` ，左子樹後的第一個元素 `20` 即為右子樹的起點，接續的操作依此類推
有了以上理解，再來看到測驗題程式碼的部分
**`hlist_add_head`** 函式的目標為在一個 `struct hlist_head *h` 後插入一個新的 `first` ，由此可知遮蔽處 `AAAA` 為 `h->first` ，也就是原先的 `first`
```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;
}
```
**`node_add`** 將節點放入 hash table 的操作，首先新增一塊記憶體空間，接著將要賦予的 val 透過簡單的 hash function 得到 index 後，使用得到的 index 指定 hash table 的位置，最後將整個節點加入該位置，因此遮蔽處 `DDDD` 為 `&heads[hash]`
```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);
}
```
**`find`** 函式是要利用 `hash table` 找到 `preorder` 的特定元素對應到 `inorder` 的所在位置， `hlist_for_each` 會搜尋對應的 `hash` 下有無相同的元素 ，因此遮蔽處 `BBBB` 為 `&heads[hash]` ， 遮蔽處 `CCCC` 則為 `list_entry`
```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;
}
```
**`dfs`** 負責重建二元樹，`preorder[pre_low]` (`preorder` 的第一個元素)為新的起始點，接著利用 `find` 函式來找到該起始點在 `hash table ` 所對應到的 `idx` ，也就是其對應到 `inorder` 的所在位置，接著該位置以前的為左子樹，以後的為右子樹，接著左子樹和右子樹分別再進行同樣操作
```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;
}
```
**`buildTree`** 函式首先利用 `node_add` 將 `inorder` 的每個元素插入到對應的 `hash table` 中， 接著再利用 `dfs` 重建二元樹
```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);
}
```
### 測驗二
以下為 [leetcode](https://leetcode.com/problems/lru-cache/description/) 的說明
- `LRUCache(int capacity)`：將 `cache` 的大小設定為 `capacity`
- 透過 `int get(int key)` 獲取該 `key` 所存放的值
- 透過 `void put(int key, int value)` 進行新增，如果該 `key` 存在則更新該 `key` 的值，不存在的話則新增。如果 `cache` 的容量不夠時，則刪除最少使用的 `key`
在閱讀完 `leetcode` 要求並對 `LRU cache` 有基本的理解後，看到 [題目](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-2)
**`lRUCacheCreate`** :
此函式主要為初始化 `LRUCache` ，詳細定義如以下
**`LRUCache`**：
此結構體包含了 `capacity` 紀錄 `cache` 的容量， `hlist_head hhead[]` 是雜湊表， `list_head dhead` 用來記錄存放節點的順序，當一個新的節點進行新增時，會將其放在 `dhead` 的開頭
**`LRUNode`**：
此結構體包含了 `key` 、 `value` ， `hlist_node node` 為雜湊表的其中一個節點， `list_head link` 為一個雙向鏈表，用來紀錄存放節點的順序
**`lRUCachePut`** :
此函式根據輸入的 `key` 和 `value` 存放於 `cache` 中， 首先 `hash` 由 `key` 除以容量 `capacity` 取得，接著透過 `hlist_for_each` 找尋該 `hash` 下有無相同的 `key` ，若有的話則先更新 `link` 至 `dhead` 開頭位置，由此可知遮蔽處 `KKKK` 為 `&c->link`，接著由開頭所提到的 `container_of` 的說明，可以得知 `pos` 指向的位置為結構體 `LRUNode` 中的 `node` ，由此可知遮蔽處 `JJJJ` 需要填上的是 `node` ，如果沒有相同的 `key` 則透過 `capacity` 判斷 `cache` 中還有無位置可以新增 `LRUNode` ，若空間已滿則將 `dhead` 最尾端所記錄的 `LRUNode->node` 在 `hhead` 刪除並將要新增的節點新增至 `hhead` 對應的 `hash` 中，若還有位置，則就配置一個新的記憶體空間並將相關資訊存入相對位置
```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;
}
```
**`lRUCacheGet`** :
由以下程式碼可知， `hash` 是透過 `key` 除以容量 `capacity` 取得，接著透過 `hlist_for_each` 找尋 `hhead` 當中有無該 `key` ，若有則透過 `list_move` 重新將該 `key` 在紀錄存取順序的表中更新至開頭的位置，並回傳對應的 `value`，由此可知遮蔽處 `IIII` 為 `&cache->link` 。若沒有對應到的 `key` ，則回傳 `-1`
由前面 `container_of` 的說明，可以得知 pos 指向的位置為結構體 LRUNode 中的 node ，可以得知遮蔽處 `HHHH` 為 `node`
```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;
}
```
**`lRUCacheFree`** :
此函式透過 `list_for_each_safe` 遍歷每個 `LRUNode` 並且釋放該節點對應於 `dhead` 所在的位置，由此可知遮蔽處 `FFFF` 為 `link` ; `GGGG` 為 `&cache->link` ，後釋放掉整個 `LRUCache`，由此可知遮蔽處 `GGGG` 為 `&cache->link`
```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);
}
```
### 測驗三
首先了解以下各個巨集
**`BITMAP_LAST_WORD_MASK(nbits)`**:
此巨集為保存 `nbits` 以內的元素
`~0UL` : 0UL 是一個表示零的數值，其中 UL 表示 unsigned long，`~` 表則讓他們的位元取反， 0 變為 1，也就是所有位元都設置為 1，得到 0xFFFFFFFFFFFFFFFF（64位元）
接著 `(-(nbits) & (BITS_PER_LONG - 1)))`， `BITS_PER_LONG` 在先前有定義為 64
以下為範例: BITMAP_LAST_WORD_MASK(4)
- `(-(nbits) & (BITS_PER_LONG - 1)))` 為 -4 & 63，運算結果為 60
- 將 ~0UL 向右移動 60 位，得到遮罩 0x4（60個位元為 1，其餘為 0）
- 最後得到的位遮罩為 0x4，它將只保留原始數字中的最後 4 個位元。
**`BIT_MASK`:**
此巨集將第 nr 位置的位元設定為 1，其餘為 0
以下以例子說明: BIT_MASK(3)
- 1UL 的十六進位表示是 0x1
- 將 1 向左移動 ((nr) % BITS_PER_LONG) 位，也就是 0x8
**`__const_hweight8`:**
此巨集用來計算計一個8位元空間中位元被設定為1的個數， 拿 `(!!((w) & (1ULL << 5)))` 進行說明，若是 w 的第 5 個位元為 1 ，則 `((w) & (1ULL << 5))` 出來的結果為 `00100000` 經過 !! 會將數值轉換為 1 ，並對每個位元進行相同處理，以此來計算8位元空間中位元為 1 的數量， `__const_hweight16(w)`, `__const_hweight32(w)`, `__const_hweight64(w)` 皆是基於此結構所做的延伸
**`small_const_nbits`:**
此巨集用來檢查一個數字 `nbits` 是否滿足三個條件
其中`__builtin_constant_p` 是 GCC 提供的一個內建函式，用來判斷 `nbits` 是否是一個常數，如果是常數會回傳 1，不是的話則回傳 0
**`GENMASK`:**
此函式的作用為生成一個位元遮罩，將第 `1` 位元到第 `h` 位元設定成 1，其餘位元設定為 0
**`FIND_NTH_BIT`:**
此函式的作用為尋找第 n 個 bit 為 1 的位元
首先輸入變數 `FETCH` 為 ，`size` 為記憶體區間有幾個位元， `num` 為要找的第幾個設置為 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; \
})
```
---
再來了解各個函式
**`__ffs`**:
此函式用來尋找 `1` 所在的最低位元，程式碼主要在分段進行討論，首先 `if ((word & AAAA) == 0)` 的部分，先把 64 位元的區間切成兩段，也就是各 32 位元，如果靠後的 32 個位元中都沒有 `set bit` 的話則將 `word` 向右移 32 位元，以對靠前的 32 位元做檢查，並將 `num` 加上 `32`。若是後面 32 個位元中有 `set bit` ，則 `if` 條件見不成立，接著再將這 32 位元再切成兩段，接著再度分成兩段進行檢查，以此類推
由以上說明可以得知遮蔽處 `AAAA` 要填上 `0xffffffff`
```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;
}
```
**`__clear_bit`**:
此函式的作用為清除特定位置的位元
首先透過 `BIT_MASK` 生成只有指定位元 `nr` 為 1 的 mask，最後透過 `*p &= BBBB` 將特定位元清除，為了達到消除特定位元的效果，我們能將 mask 取反(也就是只有特定位元為 0，其餘為 1)，並與指向 `unsigned long ` 的 `p` 取 `&` ，即可消除特定位元，由此可知 `BBBB` 為 `~mask`
比較特別的是 `volatile` ，被 volatile 宣告的變數 將不會使用最佳化編譯，詳細可參考 [volatile 的用法和用意](https://anal02.pixnet.net/blog/post/117485340-%5Bc%5D-volatile-%E7%9A%84%E7%94%A8%E6%B3%95%E5%92%8C%E7%94%A8%E6%84%8F)
```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;
}
```
**`fns`:**
此函式用於找出輸入變數 `word` 中第 `n` 個為 1 的位元，過程中透過 `__ffs` 不斷尋找直到 `n = 0` ，若找不到則回傳 `BITS_PER_LONG`
**`find_nth_bit`:**
首先輸入變數 `addr` 是指向位元位址空間的指標，`size` 是位元位址空間的大小，`n` 是要尋找的第 n 個 `set bit`
如果此 if 判斷式成立 `if (small_const_nbits(size))` ，利用 `GENMASK` 將需要判斷的 unsigned long (利用 size) 賦值給 `val` ，如果 `val` 有值，則利用 `fns(val, n)` 尋找 `val` 中的第 `n` 個 set bit
==不確定呼叫 FIND_NTH_BIT 巨集時的情況是不是當 size 不等於 1 個 BITS_PER_LONG 時，也就是只有一個 unsign long 的情況以外==
呼叫`FIND_NTH_BIT` 時， for 迴圈部分能檢查 `addr` 的每個 64 位元有幾個 set bit ，檢查時透過 `hweight_long` 來取得找到的數量， 當查找的範圍超過 `size` 卻依然沒找到時則 `goto out` (回傳 size) ，如果找到則 `goto found`
`found` 內是透過 `fns` 算出我們要的目標是在 `addr[idx]` 中的位置，並加上 `idx * BITS_PER_LONG` (先前的位元)來得到最後的位置，但若是求得的值大於 `sz` ，則代表超出範圍了，回傳 `sz`
最後 if 判斷式內是為了避免超出找尋範圍，因為 for 回圈內依次是找尋 `BITS_PER_LONG` (64) 個位元，這時 `size` 若不是 `BITS_PER_LONG` 的倍數，則可能找尋到的值會超出 `size` 的限制，因此當此情況發生時，進入到此判斷式，藉由 `BITMAP_LAST_WORD_MASK` 將不滿足一個 unsigned long 範圍的位元賦值給 `temp`
由上述可知，巨集 `FIND_NTH_BIT` 內的 `CCCC` 應該填上 `%`
Sign in with Wallet
Connect another wallet