2024q1 Homework2(quiz1+quiz2)

contributed by < kkkkk1109 >

2024q1 第一周測驗題

測驗 `1`

此題主要為參考Optimized QuickSort — C Implementation (Non-Recursive)的方式，來實作非遞迴的快速排序法。

傳統的快速排序法:

void sort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

將所需要排序的陣列輸入，並選擇 beg 和 end 當作陣列中需要排序的開頭和結尾。主要由以下步驟組成

將 piv 值設為 arr[beg]，也就是第一個元素， l 為第二個元素， r 為最後一個元素。
當 l < r 時，查看 arr[l] <= piv 是否成立，成立的話，則 l++ ，查看下個元素；若不成立的話，則將 arr[l] 的值和 arr[r-1] 的值互換。
當 l == r 時，則代表目前 l 左方所有元素均<= piv ，而右方所有元素均> piv。將 arr[beg] 和 arr[l-1] 的值交換，將 piv 放到中間。
將 piv 左，右方的值當成全新陣列，呼叫 sort 進行遞迴排序。

而此題則是將第四步的遞迴方式，改成使用兩個 stack 來儲存要進行排序的 beg 和 end ，分別記錄到堆疊 begin 和 end。

將 pivot 設為第一位，並將 L 從左到右計算有幾個小於 pivot 的數， R 則是從右往左掃。

找到之後，將 R 放到 head ，L 放到 R ， pivot 放到 L 。

現在，又可以在對左方紅色和右方藍色的序列進行排序

而 begin_L 、end_L、begin_R、end_R 則是以 stack 的方式儲存

下次會取 begin[i] 和 end[i] 之間的序列來進行排序，做完再 pop 取下一序列排序。

AAAA 於 list_tail 當中，可知是要找尋序列的尾巴，在 while 迴圈中前往下個節點，因此為 (*left)->next 。

此舉是否會影響所輸入的指標的指標?

使用測驗一的範例產生 list 且不使用 shuffle，並顯示出 list 和 tail 的值。

list value is: 0 ,tail value is: 4

可知不會影響輸入的指標的指標，除非去影響了 *left 的值，也就是儲存 left 的地址。

將 list_tail 改成以節點為輸入

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

並在呼叫時以節點為輸入，結果仍相同。

list value is: 0 ,tail value is: 4

因此得出，兩中寫法均可以達成找到 tail 的目的，且不改變 left 的值。

BBBB 也為 (*left)->next，因為要去尋找序列的長度，因此也是在 while 迴圈當中找到最後一個節點。
CCCC 、 DDDD、 EEEE

在 quick_sort 中，以下部分為初始宣告，可以看到 begin[0] 和 end[0] 位於 list 的開頭和尾巴。

    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);

在 while (p) 中，動作為逐一比較串列中的節點和 pivot 的值，並加入 left 序列和 right 序列中，因此可以得知 CCCC 應為前往下個節點，也就是 p->next。

而在 while(i >= 0) 的迴圈當中，L 和 R 分別為 begin[i] 和 end[i] 因此可以判定 begin[i] 和 end[i] 為輸入序列的頭尾， CCCC 為 list_tail(&left) ， DDDD = list_tail(&right)。

延伸問題

改進 quicksort

max_level 是否需要達到 2n ?
由於 quick_sort 會不斷的分割成更小的序列，因此 max_level 不可能大於 n ，將其設為 n 即可。
是否需要 end 來存取序列尾巴?
實際看程式碼可發現，end[i] 是在此次排序結束時，透過 list_tail 來賦值的，可改成於排序開始時，利用 list_tail(&L) 來獲得 R。

void quick_sort(node_t **list)
{

-    int max_level = 2 * n;
+    int max_level = n;
-    node_t *begin[max_level], *end[max_level];
+    node_t *begin[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
-    end[0] = list_tail(list);
            
    while (i >= 0) {
-        node_t *L = begin[i], *R = end[i];
+        node_t *L = begin[i], *R = list_tail(&L);
        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--;
        }
    }
    *list = result;
}

使用 clock 查看運行時間，發現幾乎沒什麼變

測驗 `2`

Timsort 致力於從以下三個方面，改進合併排序演算法：

加快合併（merge）過程
減少進行合併的次數。
在某些特定情況下，尋找比合併排序更有效的排序方法

minrun : 在合併過程中，run至少要有的長度，而決定方式為讓 run 的個數為 2的冪，以達到合併時兩個run的數量不會相差太大

merge_collapse : 以確認堆疊上的 run 長度保持平衡，也保持排序的穩定性
Galloping mode : 以 temp 為暫存記憶區，將較短的數列放入，並比較另一數列的首個元素，小於首個元素的可以搬離temp，將剩餘的數列進行比較。

傳統合併排序的問題:

每層合併需要掃過整個序列，對cache不友善
雖然已遞迴的方式，在於連續記憶體中較友善，但於非連續記憶體則較有可能造成cache miss

Timsort改進:

非遞迴版本合併排序的改進，邊走訪編合併，而非走訪完再合併。
對兩個 runs 中重疊部分合併即可，減少必較的次數。

list_cmp_func_t : 藉由回傳值，決定決定兩元素的排序。

The comparison function cmp must return > 0 if a should sort after b ("a > b" if you want an ascending sort), and <= 0 if a should sort before b or their original order should be preserved. It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.

code

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H

#include <linux/types.h>

struct list_head;

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif

AAAA 、 BBBB 、 CCCC

於 merge 中，宣告了指標 head 和指標的指標 tail，可猜測 head 為合併後要回傳的 list_head，並藉由 tail 來連接後續節點，因此 AAAA 應為 &head 。而迴圈中，以 cmp 來決定 a 和 b 的排序

cmp <= 0 : a 排序於 b 的前方
cmp > 0 : a 排序於 b 的後方

因此可以得知， *tail 會指向要放入的節點， tail = BBBB 和 CCCC，為前往下個地址的指標的指標，所以為 &(a->next) 和 &(b ->next)。

struct list_head *head;
struct list_head **tail = AAAA;

DDDD 、 EEEE

build_prev_link 用來建立串列的 prev 指標，而最後兩行為建立雙向環狀鏈結，因此 DDDD 要指向 head 的話，應為 tail->next ，而 EEEE 即為 head -> prev。

FFFF

由於做完 merge_force_collapse 後，會只剩兩個 run 尚未合併，因此 FFFF 應為 2 。

延伸問題

timsort 的程式碼解釋

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;

timsort 引入了 priv?? 、 head 、 cmp，使用 stk_size 來追蹤目前 run　的個數，並檢查輸入的序列是否只有一個元素，接下來將環狀鏈結斷開。

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

接著開始找 run ，定義一個 result 為找到的 run ，接著來看 find_run 的內容。

find_run:

目的為在給定的串列中選出適合的 run ，將以 ascend 排序好的元素結合成一個 run 。

若有個串列 [1、3、8、5、2]，比較 list = [1] 和 next = [3]，此時 cmp <= 0 ，代表為 ascend 排序， run = [1、3]，
再看下個元素是否也構成 ascend ，直到不成立。此時所選出的 run 為 [1、3、8]，而 result 中的　head　會存取　[1] 的指標， next 則指向 [5] ，代表此 run 的下一點。
下一次再呼叫 find_run　的話，　則會從 [5] 開始找，而下一個 [5、2] 構成 descend ，會將此串列反轉成 [2、5]，而原先 head 指向 [5] ，則會改成指向 [2]。而此輪的 run 為[2、5]。

回到 timsort 的程式碼中，以result 來指向此 run，並令 tp 為上個run，且此 result 的 head->prev 為 tp。下面為多個 run 的示意圖

接下來會呼叫 merge_collapse，來進行 run 的合併

merge_collapse:

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        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))) {
            if (run_size(tp->prev->prev) < run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (run_size(tp->prev) <= run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

若目前只有 2 個 run ，則合併
若大於 2 個，則以以下判斷來讓 run 的長度平衡
以 A、B、C為堆疊頂端的 3 個 run 須保持以下原則來合併
A > B + C
A > C
run_size(tp->prev->prev) 、run_size(tp->prev)、run_size(tp) 即為 A、B、C 三個 run ，並依照上述情況進行判斷並合併。

而呼叫的 merge_at 會將所引入的 tp 和上個 run 進行合併。

，依照上述的合併方式，最後會剩餘 3 個 run ，以 merge_forece_collapse 來將剩餘的 run 合併，直到剩餘 2 個 run，將兩個 run 以 build_prev_link 來連成環狀序列，再呼叫merge_final 來將兩序列合併。

或許可改進的點: 為何要先接成環狀序列再合併呢? 若先合併會發生什麼事

2024q1 第二周測驗題

測驗 `1`

此題為LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal，得到對同一二元樹的前序(preorder) 和中序(inorder) 的形式，來建構二元樹。

AAAA

於 hlist_add_head 中，可知是將節點 n 加入 h　後面，另ｎ 為此串列的第一個節點。參考Linux 核心的 hash table 實作可知，next 指向下個節點的地址，而 pprev 則指向前個節點指向自身地址的指標。因此 AAAA 應為 h->first。

BBBB 、 CCCC

find 為找尋雜湊表中的對應的值，使用 h_list_for_each 來逐一走訪串列，因此 BBBB 應為 heads[hash] 。而 CCCC 應為 list_entry，用以找尋 struct order_node 的 val。

DDDD

於 node_add 中，可以看出是要增加一個節點，引用到了 hlist_add_head ，代表此節點是要加在 head 後方，因此 DDDD 即為 heads[hash]。

延伸問題

參考 Linux 核心的 hash table 實作
首先，hlist_node 為 Linux 核心中，處理 hash 數值的結構

struct hlist_node {
    struct hlist_node *next, **pprev;
};

以 next 來指向下個節點， pprev 來指向上個節點的next 的指標，以此方式來避免移除節點需要考量多個情境。

此題使用了 hash table 結構來完成 order_node 的設計，如下圖

接下來介紹各個操作

hlist_add_heads : 將新節點加入至雜湊的 hlist_head 的第一位。
node_add : 創建一個新的 order_node ，賦值後，找到其對應的 hlist_head 加入。
TreeNode *buildTree :

首先，創立一個雜湊表，大小以 inorderSize 定義，並且於 node_add 將 inorder 中的順序和數值填入，並利用 hash 來找到對應的 hlist_head 加入。


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

接下來呼叫 dfs 進行深度優先搜索

dfs:

首先，先查看 pre_low、 pre_high 、 pre_low 和 pre_high 來判斷範圍是否合理

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

利用 find 找尋此數於 inorder 中的 inx ，原因如下

preorder = [3 9 20 15 7];
inorder = [9 3 15 20 7];

由於 preorder 中，第一個數字會是 root， inorder 中 root 的左、右方分別代表左、右子樹，在此情境可以知道 [9] 為左子樹，[15 20 7] 為右子樹，且左子樹的 root 為 [9]，右子樹的 root 為 [20]。

    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;

得到左右子樹的 root 和範圍後，即可透過遞迴的方式進行 dfs ，最後建立二元樹。

Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

什麼是 cpgroups?

cgroups (control groups)是Linux kernel內建的一個機制，可以以進程為最小單位，對可使用的CPU、memory、裝置I/O等資源進行限制、分割。

在bpf: rstat: cgroup hierarchical stats，可以看到對於 cgroup walk 的相關敘述

This patch series allows for using bpf to collect hierarchical cgroup
stats efficiently by integrating with the rstat framework. The rstat
framework provides an efficient way to collect cgroup stats percpu and
propagate them through the cgroup hierarchy.

The stats are exposed to userspace in textual form by reading files in
bpffs, similar to cgroupfs stats by using a cgroup_iter program.
cgroup_iter is a type of bpf_iter. It walks over cgroups in four modes:

walking a cgroup's descendants in pre-order.

walking a cgroup's descendants in post-order.

walking a cgroup's ancestors.

process only a single object.

If no order is specified, the default order is pre-order.

說明可使用 bps 的方式來蒐集不同階層的 cgroup ，並以四種方式來禁行走訪，若未特殊設定的話，會以 pre-order 的方式走訪。

kernel/cgroup/cgroup.c 中，巨集 cgroup_for_each_live_descendant_pre 以 pre-order 的方式進行走訪

#define cgroup_for_each_live_descendant_pre(dsct, d_css, cgrp)		\
	css_for_each_descendant_pre((d_css), cgroup_css((cgrp), NULL))	\
		if (({ lockdep_assert_held(&cgroup_mutex);		\
		       (dsct) = (d_css)->cgroup;			\
		       cgroup_is_dead(dsct); }))			\
			;						\
		else

又引用了另一個在include/linux/cgroup.h 中的巨集 css_for_each_descendant_pre(pos, css)，並且有以下說明

css_for_each_descendant_pre - pre-order walk of a css's descendants
@pos: the css * to use as the loop cursor
@root: css whose descendants to walk
Walk @root's descendants. @root is included in the iteration and the
first node to be visited. Must be called under rcu_read_lock().

If a subsystem synchronizes ->css_online() and the start of iteration, a
css which finished ->css_online() is guaranteed to be visible in the
future iterations and will stay visible until the last reference is put.
A css which hasn't finished ->css_online() or already finished
->css_offline() may show up during traversal. It's each subsystem's
responsibility to synchronize against on/offlining.
For example, the following guarantees that a descendant can't escape
state updates of its ancestors.

my_online(@css)
{
    Lock @css's parent and @css;
    Inherit state from the parent;
    Unlock both.
}

my_update_state(@css)
{
    css_for_each_descendant_pre(@pos, @css) {
    Lock @pos;
    if (@pos == @css)
        Update @css's state;
    else
        Verify @pos is alive and inherit state from its parent;
    Unlock @pos;
}
}

說明可以利用 pre-order 的方式來保證子節點可以在父節點更新後再進行狀態繼承。

測驗 `2`

此題為針對 LeetCode 146. LRU Cache，提出 LRU 的 C 實作

EEEE

hlist_del 為刪除節點 n，而 next 為 n 的下一節點，由於 pprev 為指向前一節點指向自身的指標，因此 EEEE 應為 next-> pprev

FFFF 、 GGGG

lRUCacheFrere 用以釋放快取記憶體，使用list_entry 來找到 struct LRUNode ，FFFF 應為 link ，為 LRUNode 中定義的 list_head， GGGG 為 pos ，及刪除目前的 list_head 。

HHHH 、 IIII

lRUCacheGet 用以獲得快取中的值，HHHH 應為 node 。若 key 符合，則呼叫 list_move ，將節點移出並放入串列中， IIII 為 pos ，及此節點的 list_head。

JJJJ 、 KKKK

lRUCachePut 將資料放入快取，JJJJ 應為 node 。若 key 符合，則呼叫 list_move ，將節點移出並放入串列中， KKKK 為 pos ，及此節點的 list_head。

延伸問題

解釋 LRU Cache 的實作

lRUCacheCreate: 用以創造快取空間。
lRUCachePut: 將資料放入快取。
以 key 來取得 hash_index ，並查看 hash 所對應到的 hlist_node 中有無此key

有對應到，將值 value 存入
無對應到，且記憶體已滿。以 list_last_entry 查看 dhead 所存取的最後一個快取，使用list_move 插入到 dhead 的第一位，並將此 node 和原始的 hhead[hash] 斷開，再接入新的 hhead[hash]。
無對應到，且記憶體未滿，代表還可以再開新的快取空間，則開新快取空間，並連結其雜湊表。

lRUCacheGet: 將資料放入快取。
以 key 來取得 hash_index ，並找此 hash是否有key的值，並將其放置於 dhead 的第一位。

可以發現在無論在 lRUCacheGet 或 lRUCachePUT 中，都會進行 list_move，將節點連接至 dhead 的頭，可知最少用到的，即為 dhead 的 tail，可以 LRU 的原則，將最少次使用到的快取給替換掉，也可以在 lRUCachePUT 的第二個情況看見，將 list_last_entry 的快取節點給替換掉。

測驗 `3`

使用 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)，完成程式碼實作。

BITMAP_LAST_WORD_MASK :

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

~0UL 為產生一個全為1的遮罩，(BITS_PER_LONG - 1) 為確保 right shift 最多就是 63，和 -nbit 做 & 運算則可以計算要 right shift 多少位元。

BITMAP_LAST_WORD_MASK(5) = 0x1f = 0b11111

BITMASK :

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))

(nr) % BITS_PER_LONG) 取得要left shift 幾個位元，確保不會超出最長位元。

BIT_MASK(5) = 0x20 = 0b10 0000

BIT_WORD :

#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

計算 nr / 64 的商，可能用來計算 offset ?

__const_hweight8 :

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

用來計算此數二進位由幾個 1 所組成，即為 hamming weight

__const_hweight8(63) = 6 = 0b10 0000
63 = 0b111111

可用在 __const_hweight16 、 __const_hweight32 、 __const_hweight64，計算不同長度的 hamming weight。

AAAA :

位於 static inline unsigned long __ffs(unsigned long word) 中，用以找尋 first bit。透過不同的 bitmask 來計算0的個數，而 AAAA 應為找尋較低 32 位元是否為 0 ，若為 0，則可以直接將計算數 num 加 32 ，接下來是尋找較高位元。因此， AAAA 為 0xffffffff。

__ffs(0x2000) = 13

__clear_bit :

由名稱可知，其目的為刪除特定的bit，但是不確定是一個還是多個，因此，查看此巨集使用的時機。

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

在 fns 中，可以看到對於輸入的 word ，會先進行 ffs ，找到第一個set，並查看 n-1 是否為零，成立即代表這個 bit 是想要找到的第n 個 bit 。不成立則呼叫 clear_bit 再重新進入迴圈。因此 clear_bit 應該是要刪除目前的 first set bit ，再重新做 ffs 找下一個 set bit。

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

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

另外，若考量到所要刪除的 bit 大於 BITS_PER_LONG 的話，則會使用巨集 BIT_WORD 來對 address　進行偏移，可以看到使用了 p 存取需要偏移的地址，再取值進行 ~ 操作，來去除特定的 bit。

BBBB :
由以上可知 BBBB 應為 ~mask ，也就是除了這個 bit 以外的位數均為 1 ，來將 first set bit 給去除。

接下來開始進行於記憶體空間中找尋第 N 個bit。

find_nth_bit :

addr : 開始找尋的地址

size : 選擇要從幾位中尋找

n : 要找尋第幾個 bit

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

1. 若 n >= size ，則 return size，因為找尋的 bit 已超過範圍。
2. 查看 small_const_nbits(size) 是否成立

small_const_nbits :

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

於 include/linux/bitmap.h 中，可看到此巨集廣泛出現，並可以在 include/asm-generic/bitsperlong.h 中找到定義

small_const_nbits(n) is true precisely when it is known at compile-time
that BITMAP_SIZE(n) is 1, i.e. 1 <= n <= BITS_PER_LONG. This allows
various bit/bitmap APIs to provide a fast inline implementation. Bitmaps
of size 0 are very rare, and a compile-time-known-size 0 is most likely
a sign of error. They will be handled correctly by the bit/bitmap APIs,
but using the out-of-line functions, so that the inline implementations
can unconditionally dereference the pointer(s).

可知此操作在編譯時期時，是否已得到此數，並檢查是否在 BITS_PER_LONG 和 1 之間；而 0 的話就代表可能是錯誤，畢竟不會有人要找第 0 個 bit，最後再交由外部的操作來進行 bit 運算，避免 inline 操作出現錯誤。

因為目前確定 size 介於 1 ~ 64 之間，僅看 size 大小即可，使用巨集 GENMASK 來產生 size 大小的 bitmask。再呼叫 fns 計算。

3. size 大於 BIT_PER_LONG 的情況 :

引用巨集 FIND_NTH_BIT 來進行超出記憶體範圍的找尋。

首先，先判斷
idx * BITS_PER_LONG + nr >= sz : 檢查目標是否在範圍內，若超過則返回 size。

接著，查看目前的 tmp 的 hamming_weight ，若大於 nr 的話，則代表可以在此範圍內找出解答，

若找不到的話，則進行 nr-=w ，來前往下個

最後，當迴圈結束後，檢查 sz 是否能夠被 BITS_PER_LONG 整除，利用巨集 BITMAP_LAST_WORD_MASK 保留 size 位的 bit ，同時 size 外的 bit 為零。因此 CCCC 為 % 。

最後返回 sz 為輸出。

2024q1 Homework2(quiz1+quiz2)

2024q1 第一周測驗題

測驗 1

延伸問題

測驗 2

延伸問題

2024q1 第二周測驗題

測驗 1

延伸問題

Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

測驗 2

延伸問題

測驗 3

Read more

linux2024-homework6

期末專題

2024q1 Homework1 (lab0)

linux2024-homework5

測驗 `1`

測驗 `2`

測驗 `1`

測驗 `2`

測驗 `3`