# 2024q1 Homework2 (quiz1+2)
contributed by < `BooleanII` >

## Graphviz
佇列與串列的操作，單透過文字時常難以清楚描述，需要輔以圖示說明讓整個流程更加易懂，作業要求中提到使用 `Graphviz` 進行圖片繪製，以下為使用 Graphviz 的筆記。

Grpahviz 安裝 (under Ubuntu)

$ sudo apt install graphviz

Graphviz 提供多種 layout engine 繪製不同類型的圖片，甚至可以自行建立客製化的 layout engine 畫出自己想要的圖片風格，下列皆為同一組描述文字檔使用不同 layout engine 繪製的圖片。

graph G {
    a -- {b,c};
    b -- d;
    d -- {e,f};
}

| Layout Engine | 範例圖片 |
|:-------------:|:------------------------------------------------------:|
| dot |  |
| neato |  |
| fdp |  |
| sfdp |  |
| circo | |
| twopi |  |
| osag | |
| patchwork |  |

圖片內容以 .dot 檔進行描述，描述順序不影響繪圖結果，註解的語法除了 C 語言中的 `//` 和 `/**/` 外，還多了 `#` 可以使用，其常用語法範例如下所示：

digraph abc {
    size ="4,4";
    main [shape=box]; /* this is a comment */
    main -- parse [weight=8];
    parse -- execute;
    main -- init [style=dotted];
    main -- cleanup;
    execute -- { make_string; printf}
    init -- make_string;
    edge [color=red]; // so is this
    main -- printf [style=bold,label="100 times"];
    make_string [label="make a\nstring"];
    node [shape=box,style=filled,color=".7 .3 1.0"];
    execute -- compare;
}


需注意使用 `digraph` 或 `graph` 進行描述的差異，一開始測試因為這個問題花了不少時間。前者的連線帶有箭頭，且連線的描述文字為 `->` ，而後者的連線描述文字為 `--` ，如混用則該文字檔進行編譯時系統會顯示 syntax error。

Error: test.dot: syntax error in line 14 near '->'

撰寫好描述文字檔後，需使用命令進行編譯產生圖片，命令格式如下：

cmd [ flags ] [ input files ]

透過 cmd 選擇要使用上面提到的那一個 layout engine 進行繪圖，並以 `-Tpng` 選擇輸出圖片格式為 png 檔、 `-o filename` 指定輸出圖檔名稱，範例如下：

dot test.dot -Tpng -o abc.png

參考文件
>[Graphviz 中文筆記](https://hackmd.io/@PeterHsi/Graphviz)
>[Drawing graph with dot](https://graphviz.org/pdf/dotguide.pdf)

## [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
題目提到是使用 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 的 Quick Sort 演算法進行修改，故先閱讀該網頁中的介紹，該演算法提出使用 `L` 與 `R` 紀錄需交換資料的指標，每次的 pivot run 排序流程如下：
1. 取串列的 head 作為 pivot
2. `R` 自串列末端節點開始，往串列的前一個節點移動，直到該節點的數值小於 pivot 時停止，將該節點的資料複製到 `L`
3. `L` 自串列起始節點開始，往串列的下一個節點移動，直到該節點的數值大於 pivot 時停止，將該節點的資料複製到 `R`
4. 重複步驟 2 到 3 直到 `R` 的位置比 `L` 更接近串列起始點
5. 將 `L` 的節點寫入 pivot 數值
6. 完成這一輪的排序

該作者表示其演算法的具備下列優缺點：
- [優] 使用 begin 與 end 儲存串列以取代遞迴呼叫，降低遞迴衍生的 function call 與 stack 成本
- [優] 減少排序過程中資料節點的移動次數
- [缺] 排序過程中需要較多次數比較

在測驗 1 題目描述中，說明作法是將 'L' 與 'R' 找出需要交換的數量，以範例的串列為例，取串列的 head 為 pivot ， L 應會紀錄到3筆小於 pivot 的節點，而 R 則紀錄到有2筆大於 pivot 的節點（題目解說需要修改）。

然而一開始無法將測驗的題目描述與提供的程式碼內容對應起來，以為 `L` 與 `R` 直接用於儲存需要交換的序列長度，但程式碼中將兩者宣告為 `node_t` 結構體，明顯並非單純紀錄數量。閱讀整份程式碼並對照 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 後才慢慢想通。

題目的快速排序同樣使用第一筆資料做為 pivot ，但 `L` 與 `R` 的用途為標示待排序序列的起始點與末端點，而 `begin` 與 `end` 用於儲存尚未排列好的序列起始點與末端點，存入 stack 的順序如下：
1. 小於 pivot 的序列
2. pivot
3. 大於 pivot 的序列

每一輪的排序使用 begin 陣列中的最後一筆序列，在第一輪排序中，我們將 list 的開頭與末端分別放入 begin 和 end 中， list_tail 函式功能為走訪序列上的每一個節點，回傳 list 末端的 node 的指標。而在 quick_sort 函式中被呼叫的 list_length 函式與 list_tail 大同小異，同樣是以走訪每一個節點的方式計算序列的長度，故兩者皆透過下列程式碼將 left 指向序列中的下一個節點：

left = &((*left)->next)

`p` 節點指標用於走訪整個序列，將每個節點的值與 pivot 進行比較。因此，在 while 迴圈中， `p` 需要指向下一個節點，並執行 quick_sort 函式中最關鍵的部分：將小於等於 pivot 的節點存入 `left` 序列，大於 pivot 的節點存入 `right` 序列中。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

根據前述描述，將比較後的 left 與 right 序列分別存入 `begin` 和 `end` stack 中，由於 `end` 代表的是序列的末端點，可以透過呼叫 list_tail 函式取得，以下是存入 stack 的完整程式碼如下：

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

當 stack 中的最後一筆序列的起始點與末端點為同一個節點時，表示該序列只包含一個已完成排序的節點。在這種情況下，我們可以將 stack 中的資料 pop 出來，並用 list_add 將它們加入 result 序列中。然後對 stack 中剩下的序列重複執行上述流程，以獲得排序完成的序列。

總結測驗 1 的答案如下：
1. AAAA = (*left)->next
2. BBBB = (*left)->next
3. CCCC = p->next
4. DDDD = list_tail(&left)
5. EEEE = list_tail(&right)

#### 使用 Linux 核心風格的 List API 改寫上述程式碼
這邊以 lab0-c 作業中的結構體來進行實現。 `node_t` 可使用變形後的 `element_t` 結構體取代，將 `value` 成員的型態由 `char *` 改為 `int` ，沿用 list_head 結構體來達成 Linux 核心風格的佇列結構，並搭配 list.h 提供的佇列操作函式進行相關實作。

typedef struct {
    int value;
    struct list_head list;
} element_t;

儲存未排序佇列的 begin 與 end 兩個 stack ，因可利用 list_head 結構體中的 `prev` 指標，避免使用 list_tail 走訪整個佇列，以獲得佇列中的最後一個節點，並省去使用 end 儲存未排序的末端點。
因佇列的 `head` 並未儲存資料，故進行排序時將 `head` 移除，保留第一個資料節點的 `prev` 指向佇列中的末端點，佇列末端點的 `next` 指向 NULL ，使佇列變形為串列。修改後的 quick sort 程式碼如下：

while (i >= 0) {
    struct list_head *L = begin[i], *R;
    if (begin[i]) {
        R = begin[i]->prev;
    } else {
        R = NULL;
    }
    if (L != R) {
        struct list_head *pivot = L;
        pivot_value = list_entry(pivot, element_t, list)->value;
        struct list_head *p = pivot->next;
        pivot->prev = pivot;
        pivot->next = NULL;

        while (p) {
            struct list_head *n = p;
            p = p->next;
        // insert element into right value if element is larger than pivot
            list_add(list_entry(n, element_t, list)->value > pivot_value 
                      ? &right : &left, n);
        }

        begin[i] = left;
        begin[i + 1] = pivot;
        begin[i + 2] = right;

        left = right = NULL;
        i += 2;
    } else {
        if (L)
            q_list_add(&result, L);
      // pop stack
      i--;
    }
}

實作後發現為了使用 list_head 結構體中的 prev 成員儲存串列的末端點，程式碼較原本的版本多了好幾處的細節處理，如 R 需判斷當前的 stack 內容是否為 NULL ， list_add 函式也需針對輸入的串列指標是否指向 NULL 來決定 prev assign 的內容。

void list_add(struct list_head **list, struct list_head *node) {
    node->next = *list;
    if (*list) {
        node->prev = (*list)->prev;
    } else {
        node->prev = node;
    }
    *list = node;
}

#### 對程式碼做些改進
在實際進行改進之前，我們先比較原始的程式碼和使用 List API 改寫後的版本。這兩個版本在不同資料量下使用 stack 的深度是相同的，因為它們僅僅是對資料結構的不同實作方式。此外，我們也需要留意到，對於相同資料量，shuffle 函式會產生相同的洗牌結果。因此，對於相同長度的資料，使用 shuffle 函式處理後進行測試，stack 的使用深度也將保持一致。
- 原始程式碼

$ ./opt_quicksort 
data size: 10, deepest level: 4
data size: 100, deepest level: 14
data size: 1000, deepest level: 26
data size: 10000, deepest level: 38
data size: 100000, deepest level: 48

- 使用 List API

$ ./quicksort_linklist 
data size: 10, deepest level: 4
data size: 100, deepest level: 16
data size: 1000, deepest level: 26
data size: 10000, deepest level: 40
data size: 100000, deepest level: 48

在 Linux 系統中，可以使用 [clock 函式](https://man7.org/linux/man-pages/man3/clock.3.html)來獲取程式碼的執行時間，以檢測程式碼在不同的資料長度下的執行時間。請注意，這僅測量快速排序的執行時間，不包含 shuffle 的執行時間。以下是執行 100,000 次的平均結果，顯示使用 list API 實作的版本速度比原始程式碼更快。
- 原始程式碼

$ ./opt_quicksort 
Data size: 10, execution time: 0.000618 ms 
Data size: 100, execution time: 0.006516 ms 
Data size: 1000, execution time: 0.090552 ms 
Data size: 10000, execution time: 1.364948 ms 
Data size: 100000, execution time: 23.467461 ms

- 使用 List API

$ ./quicksort_linklist 
Data size: 10, execution time: 0.000518 ms
Data size: 100, execution time: 0.005165 ms
Data size: 1000, execution time: 0.069995 ms
Data size: 10000, execution time: 0.979346 ms
Data size: 100000, execution time: 14.678142 ms

以 1000 筆資料的排序條件下進行比較，使用 perf record 紀錄兩者執行 100000 次，所獲得的性能指標。從結果可發現原始程式碼雖然有較高的 IPC ，但實際執行時間卻比 List API 版本來的久。

| Event | 原始程式碼 | 使用 List API | Better |
| ---------------- | ---------------- | --------------- | ---------- |
| Cache misses | 171757.2383 | 66258.646 | List API |
| Cache references | 401250.1308 | 64210.7886 | 原始程式碼 |
| Branch misses | 454205710.1405 | 42053879.6032 | List API |
| Branches | 8143817422.8188 | 8007732828.4409 | List API |
| Instructions | 95711793.1548 | 58791077.9339 | 原始程式碼 |
| Cycles | 36256592463.9717 | 27774658834.164 | 原始程式碼 |
| Page faults | 0 | 0 | Same |
| CPU migration | 3.9996 | 4 | |
| Context Switch | 60.0038 | 26.9982 | List API |
| Task clock | 8815.5827 | 6417.4784 | List API |

當使用第一筆資料作為 pivot ，且資料是最已排序的或者是逆序排列時，就會導致最壞情況發生。這種情況下，快速排序的效率會降到最低，時間複雜度將達到 $O(n^2)$ 。這是因為在這種情況下，每次切割都只會將一個元素移到正確的位置上，而不是將資料均勻地分割為兩部分，造成每筆資料都會單獨存入 stack 中，使 stack 使用的深度將與資料長度相同。
- 對已排序資料進行排序

$ ./quicksort_linklist 
data size: 10, deepest level: 10
data size: 100, deepest level: 100
data size: 1000, deepest level: 1000
data size: 10000, deepest level: 10000
data size: 100000, deepest level: 100000

由上述的比較可看出待改進的點有二：
1. stakc 大小在 worst case 下，只需要 data size 的深度，此項改進可降低排序過程中的記憶體需求。
2. 透過 pivot 的選擇必免 worst case 。常見的作法為從序列中隨機選擇 pivot 。

### 測驗 `2`

Timsort演算法主要行為是將序列中已完成排序的部份切割為子序列（ run ），當 run 的滿足特定條件時，使用合併排序（ merge sort ）將兩個 run 進行合併。
在題目解說中，有提到『合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。』。乍看之下不是很懂哪個要略小於 2 的冪才能獲得較高效率，是指 minrun 的長度還是切割後 run 的數量？

參考維基百科的介紹進行整理：
Timsort 運作時會定義最一開始切割的每個 run 最小長度為 minrun ，切割時當已排序的 run 長度不足 minrun 時，會將方的資料節點以 insertion sort 方式插入，使該 run 長度滿足 minrun 。

切割完 run 後， Timsort 會使用合併排序將兩個 run 合併為一個 run ，而要將哪兩個 run 進行合併則依據 run 的長度，以下列關係式進行決定。當 XYZ 三個 run 之間無法滿足關係式時， X 與 Y run 會進行合併。
- $Z > Y + X$
- $Y > X
(e.g. Z 的長度小於 Y+X ，則 X 與 Y 會進行合併)

因 Timesort 為 stable sorting 演算法（同樣大小的節點的順序在排序後不變），為了在時間與空間成本上達到平衡，在合併 run 時只變更兩個 run 間需要合併的範圍。

首先， Timsort 會搜尋 Y run 中的第一個節點在 X run 中合併時要插入的位置，接著搜尋 X run 中末端節點合併入 Y run時要插入的位置。合併時僅對這兩個插入點之間的節點進行操作，節省 merge 時所需使用的暫存記憶體空間。

維基百科引述下列連結文章，指出當 run 的數量小於或等於 2 的冪時，在合併階段可以得到較好的效率，降低 run 在合併時因長度落差過大造成的效率降低問題。
>https://hg.python.org/cpython/file/tip/Objects/listsort.txt

名詞定義
minrun ：run的最小分割長度
N ：序列資料總數
n ：切割後的 run 長度

測驗題目的 timsort 在合併時不需 malloc 暫存記憶體空間 (in-place algorithm) ，共分為六個函式進行實作，為了統計排序過程中比較次數，在每個函式輸入 priv 的 void 指標，用來傳遞並累加比較次數的參數 count 。
- find_run
- merge_collapse
- merge_force_collapse
- build_prev_link
- merge_final

需注意題目的比較節點資料大小的方式，有別於直接使用 if 判斷式，而是透過呼叫 輸入參數的 `cmp` 的函式指標，以函式 `compare` 進行比較，增加整體程式碼的靈活度(如透過呼叫不同的 compare 函式決定排序的方向為 descend 或 ascend ）。

int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
    if (a == b)
        return 0;

    int res = list_entry(a, element_t, list)->val -
              list_entry(b, element_t, list)->val;

    if (priv)
        *((int *) priv) += 1;

    return res;
}

首先使用 find_run 函式進行串列的 run 切割，當發現到資料串列中存在降序排列時，會將該節點切割放入 prev 串列中，放入的過程中會進行反轉使其成為升序排列；如資料為升序排列時，則會繼續走訪下一個節點，直到出現降序排列時停止。這個切割方法未如同傳統 timsort 演算法介紹中提到的使用特定 minrun 大小進行切割，是後續可以進行改進的地方。

切割好的 run 串列透過 pair 結構體的 head 成員進行儲存，並回傳至作為 stack 使用的 tp 串列，而剩餘尚未切割的串列則儲存於 next 成員中。需注意 find_run 切割時未處理節點的 prev 指標內容，僅將 run 長度儲存於該 run 串列中第二個資料節點的 prev 進行儲存 （ head->next->prev )。

struct pair {
    struct list_head *head, *next;
};

以下圖串列 [8,11,9,7,5] 為例

共可被切割為兩個 run ：

並依序存入 tp stack 中：

在此測驗的程式碼中區分了好幾種合併的函式，當每完成一個 run 切割，皆會呼叫一次 merge_collapse 函式，如 stack 中的 run 長度滿下列條件就進行合併。
- tp stack 中有三個以上的 run ， tp->prev->prev 的長度小於等於 tp->prev 與 tp 的總和
- tp stack 中有四個以上的 run ， tp->prev->prev->prev 的長度小於等於 tp->prev->prev 與 tp->prev 的總和
- tp stack 中有兩個 run ，且 tp->prev 中的長度小於等於 tp

merge_collapse 函式的合併是使用 merge 函式進行，為實現 in-place algorithm ， merge 函式未 malloc 暫存的記憶體空間，而使用間接指標 **tail 來達成資料合併。該操作手法可以參照 [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D) ，以間接指標 tail 指向當前完成合併的串列末端點，故在最一開始的時候應指向回傳合併串列的 head ，將 tail assign 為 ＆head 儲存 head 的位址。

struct list_head *head;
struct list_head **tail = &head;

完成比較後，將 *tail assign 為較小的資料節點指標，使 head 指向 a 或 b 串列中最小的節點，並將 tail assign 為該資料節點結構體中的 next 成員，讓 *tail 在下一次比較中可指向次小的節點，不斷執行到其中一方的串列走訪完畢時，將 *tail assgin 剩餘的串列。

for (;;) {
    /* if equal, take 'a' -- important for sort stability */
    if (cmp(priv, a, b) <= 0) {
        *tail = a;
        tail = &(a->next);
        a = a->next;
        if (!a) {
            *tail = b;
            break;
        }
    } else {
        *tail = b;
        tail = &(b->next);
        b = b->next;
        if (!b) {
            *tail = a;
            break;
        }
    }
}

當輸入串列完成所有的 run 切割後，呼叫 merge_force_collapse 函式將 stack 中所有的 run 兩兩進行合併，直到 stack 中的 run 數量小於三個才停止，此處看起來是個可以改進的地方，如果能夠將所有 run 在此函式中完成合併，若 stack 中只剩兩個 run 時，後續就不用額外使用 merge_final 函式進行合併。

最後，要注意因先前的串列操作皆未對 list_head 結構體中的 prev 指標進行處理，故完成排序後透過 build_prev_link 函式，將 prev 重新寫入正確的指向節點，並在最後將 tail->next 需指向 head ，而 head->prev 需指向 tail讓整個排序好的串列可回到 Linux 風格的環狀佇列架構。

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 */
    tail->next = head;
    head->prev = tail;
}

因為 build_prev_link 函式是在完成所有 run 的合併後才能執行，故 timsort 函式最後的 if 判斷式數值應為 1 。

if (stk_size <= 1) {
    build_prev_link(head, head, stk0);
    return;
}

總結測驗 2 的答案如下：
1. AAAA = &head
2. BBBB = &(a->next)
3. CCCC = &(b->next)
4. DDDD = tail->next
5. EEEE = head->prev
6. FFFF = 1

## [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)

### 測驗 `1`

### 測驗 `2`

### 測驗 `3`
題目為實作 `find_nth_bit` 函式，讓其可在**連續**的記憶體空間找出第 N 個設定的位元。由於直接從 find_nth_bit 開始看程式碼看不太懂運作原理，故先從此函式的的程式碼最終會使用到 `__ffs` 開始說明。

__ffs 用於找出輸入的 word 中哪個位元是第一個為 1 的位元（由最低有效位元 Least Significant Bit 開始找）。 `__ffs` 函式使用 binary search 方式進行實作，透過 bit mask 確認右半邊的位元是否皆為零，若皆為零則將輸入的數值向右位移，搜尋剩下的另外一半位元。以 64 bit 長度的 word 為例，使用 '0xffffffff' 的 bit mask 確認右半邊的 32 bit 資料是否皆為0，若成立則將位置變數 num 累加 32 ，並將 word 向右位移 32 bit ，接續確認剩餘的 32 bit 資料。需注意此函式如果輸入的 word 內容為 `0` 時，輸出結果會是錯誤的 63 。

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

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 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;
}

接續來看有呼叫 __ffs 的 `fns` 函式，其功能為找出輸入的 word 中，第 'n' 個為 1 的位元位置，注意這裡的 n 是由 0 開始數，當 n 的數值非零時，代表 __ffs 找到的位元位置被非所要的位置，要將該位元設為 0 ，重新執行 __ffs 找到下一個為 1 的位置。以函式輸入 word 為 5 、 n 為 1 ，其輸出結果應為 2 。

fns 中使用 __clear_bit 函式進行上述將 word 特定位元設為 0 的實做，由於 `find_nth_bit` 函式的功能需能用在連續記憶體空間中，故這邊使用指標處理當指定的位元位置超出一個 long 的長度時的狀況，並在最後以BIT_MASK 函式獲得的 bit mask 將目標的位元設為 `0` 。需注意由於是將目標位元設為 0 ，故在與 *p 做 ＆ 處理前需將 bit mask 取 not 運算。

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 &= ~mask;
}

接續看到 small_const_nbits 巨集( macro )，當中用到 gcc 提供的 [built-in function `__builtin_constant_p`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) ，該函式的功能是讓 gcc 在編譯時檢查輸入的參數（ argument ）是否為常數，若 gcc 無法在優化選項的條件下判斷其為常數則回傳為 0 ，反之則回傳 1 代表確定是常數。故該函式僅有在 nbits 同時滿足大於零、小於等於 long 長度且 gcc 判斷為常數時回傳為 1 。故當 find_nth_bit 要找尋的資料範圍大於一個 long 長度時，將使用 FIND_NTH_BIT 找處第 N 個為 1 的位元位置。

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

GENMASK 巨集因涉及到了 bitwise 操作，透過直接帶入數字實驗很快就能抓到邏輯，該巨集的作用為建立指定區間為 1(set) 的 bit mask ， h 作為 head 決定最後一個為 set 的位元， l 作為 last 決定第一個為 set 的位元。其運作的原理首先透過 ~0UL 獲得 0xFFFF FFFF FFFF FFFF ，將 ~0UL 減去 1ul向左位移 l 後的數值，使 l 位元設定為 0 ，在透過加 1 讓較 l 低的位元設定為 0 ；而透過向右位移 ~0UL 可讓較 h 高的位元設為 0 ，使用 h 與 l 分別產生的兩個 bit mask 取 ＆ 獲得兩者皆為 1 的位元 bit mask。

以 long 為 64 bits 的電腦為例，當 h 為 15 、 l 為 4 時， GENMASK 的輸出為 0x0000 0000 0000 FFF0 。此巨集在 find_nth_bit 函式中，用於限制 fns 搜尋的範圍，避免 find_nth_bit 回傳超出 size 參數範圍的結果。

再來看到 FIND_NTH_BIT 巨集實作所使用的 hweight_long 巨集，接連使用 __const_hweight64 、 __const_hweight32 、 __const_hweight16 和 __const_hweight8 組成，由呼叫的方式可推測以 byte 為單位，逐步擴展到 64 bits 的運算。

#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))

從最底層的 __const_hweight8 原理開始解說，此巨集最巧妙的地方在於連續使用兩次 not 的邏輯運算，非零的數值經過兩次 not 邏輯運算後結果皆為 true ( 1 )，再透過搭配 bit mask 可以計算該 byte 中為 1 的位元數量，並以此為基礎擴充到可計算 64 bits 長度資料中為 1 的位元數量。

接續解說 BITMAP_LAST_WORD_MASK ，其功能為列出最低位元 nbits 皆為 1 的 bit mask。以byte 長度的 bit mask 為例， nbits 為 1 時結果為 0x01 ； nbits 為 3 時結果為 0x07 。

回到 FIND_NTH_BIT 巨集，其輸入共有 FETCH 、 size 、 num 三個參數，傳入的資訊如下：
- FETCH ：搜尋記憶體空間的起點位址
- size ：搜尋的記憶體空間範圍，單位為 bit
- num ：第 num 個為 1 的位元

FIND_NTH_BIT 巨集的關鍵為下列 for 迴圈， idx 用於決定搜尋的記憶體 index 位置，當 idx 為 0 ，搜尋的記憶體位址為 FETCH ；當 idx 為 1 時，搜尋的記憶體位址為 FETCH+1 。故在 for 迴圈中的結束判斷條件中，使用當 idx 指到的記憶體位置超出搜尋範圍 size 大小時，則終止 for 迴圈的執行。

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;
}

在該 for 迴圈中，每當呼叫 hweight_long 獲得當前記憶體位置的資料中為 1 的位元數量後，會將 num 數值減去該結果，代表還剩下多少個為 1 的位元尚未找尋到。

使用 goto 決定該巨集輸出的結果，第一個 if 判斷式將搜尋為 1 的位元數量納入是否要離開 for 迴圈的判斷依據。以 idx 為 0 時來看，當搜尋為 1 的位元數量大於等於搜尋的記憶體位元長度時， 代表需要搜尋為 1 的位元數量已超出所設定的搜尋範圍，故使用 goto 跳躍到 out 程式位置直接回傳 size 數值。反之，則使用 hweight_long 獲得當下記憶體內容中為 1 的位元數量，如大於目標搜尋數量，則代表該位址中存在搜尋的目標位元，使用 goto 跳躍到 found 程式位置，以 fns 找出並回傳位元的位置。需注意此處使用 min 比較 fns 計算結果與 size 哪個比較小後決定實際的輸出結果，主要是當 fns 未找到目標位元時，會回傳 BITS_PER_LONG ，透過 min 可限制 FIND_NTH_BIT 回傳的數值最大為 size 。

sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);

需注意當 size 非 64 bits 的倍數時，需要額外透過下列程式碼進行處理，透過 BITMAP_LAST_WORD_MASK 將超出 size 範圍的位元設為 0 ，避免後續的 fns 將其算入，故 CCCC 的答案為 < 。

if (sz < BITS_PER_LONG)
    tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);

最後提出我對這段程式碼感到疑惑且驚訝的地方，FIND_NTH_BIT 在 find_nth_bit 函式中以 addr[idx] 作為第一個輸入參數，使 FIND_NTH_BIT 在 idx 大於 0 時，可以透過 addr[idx] 讓 tmp assign 超出 64 bits 範圍的資料，這是我第一次看到的操作方式，這部份應該是 [preprocessor](https://hackmd.io/@sysprog/c-preprocessor) 方面的語法應用，後續會花時間進行研究。

總結測驗 3 的答案如下：
1. AAAA = 0xffffffff
2. BBBB = ~mask
3. CCCC = <