2024q1 Homework2 (quiz1+2)

contributed by < rain20010126 >

課程理解與疑問

Linux 核心原始程式碼巨集: container_of

1對於一個結構體，裡面的元素因為編譯器 alignment 的需求，裡面的元素不一定會按照記憶體的順序進行排列，實際跑過以下程式碼，可以發現輸出的 c= 並不符合預期，接著程式碼第 15 行的輸出可以看到 p 和 x.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 的位置，也就是兩者之間的距離

#define offsetof(TYPE, MEMBER)	__builtin_offsetof(TYPE, MEMBER)

接著巨集 container_of 根據 offsetof 的基礎上擴充為輸入給定 struct 成員的位址 ptr 、 struct 的型態 type ，以及該成員的名稱 member ，最後回傳此 struct 的位址

#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

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

以下函數為算出鏈結串列的長度， BBBB 部分需要不斷更新至下一個節點，並在更新的同時將計算節點數量的 n 的數值+1，因此 BBBB 和 AAAA 的結果相同，皆為 (*left)->next

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 串列中

接著由下方函數可知，當檢查到的元素 p 若是大於 pivot，則會將結點加入到 right 串列，若是小於則加入到 left 串列內，另外 begin[i] 為 left 頭部位置，而 end[i] 為其尾部位置， begin[i + 1] 以及 end[i + 1] 為 pivot 元素，最後 begin[i + 2] 為 right 串列的頭部位置， end[i + 2] 則為其尾部位置。

經過第一次 iteration 後的結果如以下

 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 元素一樣是串列的開頭位置，結果如以下

再次對節點 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

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 同樣會將鏈接修改成雙向的

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 對於 此題leetcode 的說明，來幫助我理解程式碼，以下是我在觀看完後對於此問題的理解

1. preorder 的第一個元素為 root ，也就是 3

2. 再來可以看到 inorder 序列， root 元素以前的(也就是 9) ，即為 2 的左子樹， root 元素以後(也就是 15、20、7)的即為 2 的右子樹，並分別取得子樹的長度

3. 接下來分別對 2 的左右子樹做以上操作
4. 先對左子樹，可以得知子樹的長度為 1 ，因此 9 即為左子樹；右子樹則長度為 3
5. 再回到先前的 preorder ，左子樹後的第一個元素 20 即為右子樹的起點，接續的操作依此類推

有了以上理解，再來看到測驗題程式碼的部分
hlist_add_head 函式的目標為在一個 struct hlist_head *h 後插入一個新的 first ，由此可知遮蔽處 AAAA 為 h->first ，也就是原先的 first

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]

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

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 的所在位置，接著該位置以前的為左子樹，以後的為右子樹，接著左子樹和右子樹分別再進行同樣操作

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 重建二元樹

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 的說明

• LRUCache(int capacity)：將 cache 的大小設定為 capacity
• 透過 int get(int key) 獲取該 key 所存放的值
• 透過 void put(int key, int value) 進行新增，如果該 key 存在則更新該 key 的值，不存在的話則新增。如果 cache 的容量不夠時，則刪除最少使用的 key

在閱讀完 leetcode 要求並對 LRU cache 有基本的理解後，看到 題目

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 中，若還有位置，則就配置一個新的記憶體空間並將相關資訊存入相對位置

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

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

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 的位元

#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

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 的用法和用意

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 應該填上 %