2024q1 Homework2 (quiz1+2)

contributed by <marvin0102>

第一周測驗

測驗 1:

結構體 node_t:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

此結構體作為陣列的單一節點 :
*left 、 *right的作用是當作為 pivot 時，分別記錄與比較比 pivot 大或小的節點。
*next 則是作為 linked list 的指標，指向下一個元素。
value 為該節點的值。

操作函式:

我們可以只用以下這些 API 來操作與建構陣列。

• void list_add(node_t **list, node_t *node_t)
• node_t *list_tail(node_t **left)
• int list_length(node_t **left)
• node_t *list_construct(node_t *list, int n)
• void list_free(node_t **list)

解題思路:

以知原始程式為非遞迴快速排序( quick sort )的實作。

    while (count--)
        list = list_construct(list, test_arr[count]);

從函式list_construct()以及 main function 建構初始陣列的程式碼可知，此陣列為單向鏈接串列(linked list)。

---

函式quick_sort() 中的參數list為指標的指標，其指向的位置為指向串列第一個節點的指標 head 之地址。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

函式list_length()回傳的是一串列的長度，因此需要逐一走訪整個串列聘記錄其節點的個數，而node_t **left為指標的指標，因此，每一次迴圈，需要將left的值更新為指向下一個節點的指標之地址，也就是指標next的地址。

-       left = &(BBBB);
+       left = &((*left)->next);

loop 0

loop 1

loop 2

---

快速排序法在排序過程中，會將尚未排序好的子序列做排序，以子序列的第一個節點作為 pivot 、 L 會從左邊開始掃，紀錄有多少值小於 pivot，R 從右邊開始，紀錄有多少值大於 pivot。
而第一次排序，L 必為串列的第一個節點，R 為串列的最後一個節點。

    begin[0] = *list;
    end[0] = list_tail(list);

因此，end[0]為串列的最後一個節點，而函式list_tail()的作用即為回傳一串列最後一個節點的指標。

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

與函式list_length()相同，函式list_tail()需要逐一走訪串列中的所有節點才能夠得到最後一個節點的地址。

-left = &(AAAA);
+left = &((*left)->next);

---

快速排序法在完成一次排序後，會形成三個子串列，分別為，比 pivot 小的序列、 pivot 、比 pivot 大的序列，下一次排序則會對比 pivot 小的序列與比 pivot 大的序列做排序。

排序前

排序後

從結果可以看到，排序後 L 與 R 會指向子序列的第一個節點，即成為子序列的起始指標。

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

而實作程式碼則運用這個結果，先建立兩個空字串left、right，並且將比 pivot 小的節點加至left，比 pivot 大的節點加入right中，最後的結果會與快速排序法一致。

由此可以知道，此迴圈須逐一走訪串列並且與 pivot 比大小。

-p = CCCC;
+p = p->next;

• void list_add(node_t **list, node_t *node_t):
  list_add 的功能是將額外的節點插置陣列的開頭。
  其運作的方式為，將新節點指向陣列的第一個節點，並且將指向陣列頭部指標的 list 更新為指向新節點。

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

---

由於使用非遞迴的方式做快速排序，因此需要紀錄每個子序列的起始節點與結束節點，並用迴圈代替遞迴。

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

此段程式碼即為紀錄每個子序列的起始與結束節點，因此

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

改進方案

以遞迴實作中，遞迴的最底層，即每個以序列只用一個元素，因此begin[]與end[]的記憶體分配至多只需要 n個空間。
此外，每個子序列的end[i]可由list_tail(begin[i])取得，因此不需要使用額外的儲存空間。

-   int max_level = 2 * n;
+   int max_level = n;
-   node_t *begin[max_level], *end[max_level];
+   node_t *begin[max_level];

while (i >= 0) {
-       node_t *L = begin[i], *R = end[i];
+       node_t *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
        ...

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

以 linux List API 改寫

void quick_sort(struct list_head **list)
{
    struct list_head *head = (*list);
    int n = list_length(head);
    int value;
    int i = 0;
    int max_level = 2*n;
    struct list_head *begin[max_level];
    struct list_head *result = new_head(), *left = new_head(), *right = new_head();
    
    begin[0] = head;
    for(int j=1 ; j<max_level ; j++){
        begin[j] = new_head();
    }       
    while (i >= 0) {
        struct list_head *L = begin[i]->next, *R = begin[i]->prev;
        if (L != R) {
            struct list_head *pivot = begin[i]->next;
            value = list_entry(pivot, node_t, list)->value;
            list_del(pivot);
            node_t *entry, *safe;
            list_for_each_entry_safe (entry, safe, begin[i],list) {
                list_move(&(entry->list),entry->value > value ? right : left);
            }
            list_splice_init(left, begin[i]);
            list_add(pivot,begin[i + 1]);
            list_splice_init(right, begin[i+2]);

            i += 2;
        } else {
            if (list_is_singular(begin[i]))
                list_splice_init(begin[i],result);
            i--;
        }
    }
    *list = result;
    for(int j=1 ; j<max_level ; j++){
        free(begin[j]);
    }
    free(right);
    free(left);
    
}

程式細節見commit

測驗 2:

Timsort 程式運作原理：

Timsort 透過只合併 2 runs 中大小關係重疊的區域、將以序列中已排序的元素分在同一 run ，降低了傳統合併排序法（merge sort）的記憶體開銷與比較次數。

考慮以下序列

find_run 作用為找出序列中的下一個 run ，也就是需要合併的子序列。

執行完第一次 find_run 後， result.head 會紀錄此 run ，並且將其餘的序列紀錄在 result.next。

指標 tp 負責紀錄所有待合併的 runs，作法是使用 linked list 串連所有 runs 的 head 指標。
merge_collapse 在接收 runs 的鍊接串列後，負責判斷需要合併哪些 runs ，合併串列須達成兩個條件：

• 當欲合併的 runs 超過三個時，須判斷 tp->prev->prev 的長度是否小於等於 tp->prev 、 tp長度之合
• tp->prev 的長度是否小於等於 tp

merge_at 則負責將 tp 、 tp->prev 合併，其中 merge 使用指標的指標將兩序列合併，好處是不需要額外的記憶體。

上圖為合併前 tp所紀錄的 runs

因為 tp->prev->prev<=tp->prev+tp，且tp->prev<tp，因此將tp、tp->prev 合併。

又，因為tp->prev<tp ，因此做合併

最後merge_force_collapse將剩餘的 runs 做合併。

改進實做：

此實作程式中的 merge 並不符合 Galloping mode 的方法敘述，而是依照linux merge的方法進行。
可以將 Galloping mode 進行實做，並比較其效率。

實驗結果：
在亂數測資的情況下，原始 merge 的比較次數為：

==== Testing timesort ====
  Comparisons:    9356
  List is sorted

Galloping mode 的比較次數為：

==== Testing timesort ====
  Comparisons:    16855
  List is sorted

在一般亂數的情況下， Galloping mode 的比較次數有明顯提昇。

---

第二周測驗

測驗 1

透過前序與中序建構樹程式運作原理

實作程式碼會使用到 hash table
Linux 核心的 hash table 實作

在 linux 核心的 hash table 實作中，節點的資料結構被定義為：

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

而 table 是由資料結構 hlist_head 型別的陣列所構成：

struct hlist_head {
    struct hlist_node *first;
};

其連接示意圖如下：

---

在建構樹的時候，需要取得前序、中序、後序中的其中兩個，否則無法確定父節點與子節點的關係。

程式一開始需要建立一個空的 hash table ，並且使用INIT_HLIST_HEAD() 將 table 初始化。
node_add() 負責把樹的節點依照 inorder 順序插至 hash table 中

以 preorder: [3,9,20,15,7] ,inorder: [9,3,15,20,7] 為例：

dfs() 使用遞迴重新建構樹，方法為：

將當前 preorder 的第一個數值作為 root ，並使用 find() 函式在 hash table 中找到此數值在 inorder 中的位置idx。
使用 idx 分割原前序、中序為左子樹與右子樹之前、中序，並呼叫 dfs()分別建構其左、右子樹。

改進想法：

在建構樹的過程中，hash table 中的每個節點只會只用一次，因此在節點被加數樹時，將節點從 hash table 中刪除可以有效降低每次的尋時間。

在原本的實作程式中，hash table 單純被用來查找 node index，在建構樹時仍須配置額外的記憶體，此過程明顯存在記憶體浪費，如果能將 hash table 的記憶體加以利用，移可增加記憶體的利用率。

    struct order_node {
-       struct hlist_node node;
-       int val;
+       struct TreeNode node;
        int idx;
    };

基於這個想法，我將改變了原本 hash table 的資料結構，捨棄 hlist_head 、 hlist_node 改為使用建構樹時的資料結構 TreeNode 作為代替。

hash table 的建構改為與 linux linked list 相似的雙向鍊接串列進行實作。

-static int find(int num, int size, const struct hlist_head *heads)
+static struct TreeNode* find(int num, int size, const struct TreeNode *heads)
 {
-    struct hlist_node *p;
+    struct TreeNode *p;
     int hash = (num < 0 ? -num : num) % size;
-    hlist_for_each (p, &heads[hash]) {
+    list_for_each (p, &heads[hash]) {
         struct order_node *on = list_entry(p, struct order_node, node);
-        if (num == on->val)
-            return on->idx;
+        if (num == on->node.val){
+            list_del(p);
+            return p;
+        }    
     }
-    return -1;
+    return NULL;
 }

    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);
+   struct TreeNode *tn = find(preorder[pre_low], size, in_heads);
+   int idx = list_entry(tn, struct order_node, node)->idx;
    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);

這樣更改的優點為：

1. 將 hash table 作為 TreeNode 的存放陣列，當特定節點需要被用於建構樹時，可以直接從 hash table 中提取而不需要額外配置記憶體。
2. 由於樹的節點會從 hash table 中移出，可以有效提昇 hash table 的搜索效率

詳細的更改內容見commit

Linux 核心的 cgroups 相關原始程式碼

include/linux/cgroup.h
在 Linux 核心中定義了巨集 css_for_each_descendant_pre 以 pre-order 順序走訪 *css，其中 root 會是第一個走訪的節點。

#define css_for_each_descendant_pre(pos, css)				\
	for ((pos) = css_next_descendant_pre(NULL, (css)); (pos);	\
	     (pos) = css_next_descendant_pre((pos), (css)))

在此巨集中，會利用函式 css_next_descendant_pre 找尋 pos 節點的下一個 pre-order 節點。

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 找尋下一個節點的方法為：

• 若現在尚未走訪任何節點，則以 root 為第一個走訪的節點
• 若 pos 節點存在子節點，則利用 css_next_child 走訪第一個子節點
• 若 pos 節點不存在子節點，則找尋自己或是祖先的兄弟節點走訪

---

測驗 2

LRU 資料結構:

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

LRUCache 資料結構可以當作 Cashe 本身，其中：

• capacity: Cache 的容量
• count: 目前在 Cache 內的資料個數
• dhead: 為 linux linked list ， 目的是紀錄 Cache 內各LRUnode的使用頻率
• hhead: 為 hash table，可以使用key來找尋欲寫入或讀取的LRUnode

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

LRUNode作為資料的存取單元，用於儲存放入 Cache 內的資料：

• key: hash table 的建值，用於在 hash table 中搜尋LRUNode
• value: 儲存於 Cache 內的數值
• node：連接於 hash table 中，用於在 hash table 中搜尋LRUNode
• link: 連接於 linked list 中，在寫入或讀取時，可以即時更新LRUNode的取用頻率

LRU 程式運作原理:

lRUCacheCreate()函式的作用是創建一個容量為capacity的 LRUCache 並且初始化。

lRUCacheFree()則是負責釋放LRUCache裡所註冊的所有記憶體。

lRUCacheGet()取用目前已經在 cache 內的 LRUnode。

假設目前 cache 內已有三個 LRUNode 如下:

則當我們想要存取LRUNode_key 2的 value 時，呼叫lRUCacheGet()， LRUCache內的 linked list會被更新。

LRUNode_key 2被移到了 list 的最前面，這表示LRUNode_key 2為我們最近一次使用的LRUNode

lRUCachePut()更新 LRUNode->value的值，若 LRUNode 不存在且 Cache 未滿，則新增LRUNode ，但若 Cache 已滿，則須將被閒置最久的LRUNode從hash table 中移除，並且將LRUNode->key、LRUNod->value更新後再重新插入 hash table。

加入LRUNode_key 4

改進方法:

將最後一次存取的 cache 在 hash table 中的位置一致最前面，這樣做的好處是可以提昇搜索 cache 時的效率。
但是，在 hash table size 為最佳時，搜尋的時間趨近於常數，此種改進方法並沒有辦法提昇搜尋效率。
程式請見commit

Linux 核心 lru 相關程式：

include/linux/lru_cache.h 中定義了 LRU cache 的資料型別，其中包含 lc_element、lc_cache。
其中會使用到 kmem_cache ，kmem_cache 主要的作用是管理 slub 等對象。（slub)

而在 lib/lru_cache.c 中，定義了 lc_create() 、 lc_find() 等新增及操作 lru cache 的函式。

---

測驗 3

考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)
以下為程式的實作原理：

程式實作原理：

巨集small_const_nbits(nbits) 的作用是判斷欲查詢的記憶體是否為陣列，其中：

• __builtin_constant_p(exp):
  判斷 exp 在編譯時是否為常量。

The use of the GNU compilers. 6.61

Built-in Function: int __builtin_constant_p (exp):

• You can use the built-in function __builtin_constant_p to determine if the expression exp is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value.
• The argument of the function is the expression to test. The expression is not evaluated, side-effects are discarded.
• The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant.
• Any expression that has side-effects makes the function return 0. A return of 0 does not indicate that the expression is not a constant, but merely that GCC cannot prove it is a constant within the constraints of the active set of optimization options.

---

如果small_const_nbits(nbits) 通過即表示欲檢查的記憶體小於等於一個 unsigned long 大小，這時就可以在設定的範圍內尋找 Nth set bit。

巨集GENMASK(h, l)為限制函式的找尋範圍為從 l th 到 h th 個 bit ，低於或超出這個範圍的 bit 都會因被 mask 遮擋而設為 0。

n = 0xAAAA /*0b1010 1010 1010 1010*/
val = GENMASK(15, 4) /*val = 0x0AA0 = 0b0000 1010 1010 0000*/

---

如果small_const_nbits(nbits) 未通過即表示欲檢查的記憶體大於一個 unsigned long 大小。

此時需要透過巨集 FIND_NTH_BIT() 先鎖定 Nth set bit 位於陣列中的第幾個元素中，再藉由 fns() 找出其位置。

作法是，逐一走訪陣列中的每個 unsigned long ，透過hweight_long()計算其中的 set bits 個數，當累積的 set bits 個數超過 N 時，即代表 Nth set bit 位於目前的 undigned long 中。

---

函式fns(word, n)的作用為，在unsigned long word中，找出 nth set bit 的位置。
方法為透過__ffs(word)找出目前word中，第一個 set bit 的位置，如果此 set bit 並非我們所需的 nth set bit ，則使用函式__clear_bit()設為0，並且做n--，當n--==0成立時，此時的 set bit 即為 nth set bit 。

• __ffs():透過分區檢查的方式，找出 unsigned long 中的第一個 set bit 位置

/* 假設 word 值  */
word = 0xABCDEF00
/*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/

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

#if BITS_PER_LONG == 64
    /* 檢查 first set bit  是否出現在前半*/
    /*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
    /*                      &                         */
    /*       0b1111 1111 1111 1111 1111 1111 1111 1111*/
    if ((word & AAAA) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    /*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
    /*                      &                         */
    /*       0b0000 0000 0000 0000 1111 1111 1111 1111*/
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    /*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
    /*                      &                         */
    /*       0b0000 0000 0000 0000 0000 0000 1111 1111*/
    /*如果 ＆ 結果為 0 ，代表檢查區域無 set bit 因此將 word 
     * 向右移清除此區域，並且 num 加上此區長度*/
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    /*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
    /*                      &                         */
    /*       0b0000 0000 0000 0000 0000 0000 0000 1111*/
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    /*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
    /*                      &                         */
    /*       0b0000 0000 0000 0000 0000 0000 0000 0011*/
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    /*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
    /*                      &                         */
    /*       0b0000 0000 0000 0000 0000 0000 0000 0001*/
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

• __clear_bit(nr, addr):將 addr 中，第 nr 個 bit 設為 0
  • BIT_MASK(nr):回傳一段 bit mask ，只有第 nr 個 bit 為 1 ，用於改變第 nr 個 bit
  • BIT_WORD(nr):因為 addr 可能為陣列，因此需要計算 nr 位於陣列中的第幾個元素中。

最後只需要將 p & ~mask，就可以清除第 nr 個 bit。

Linux 核心中 find_nth_bit的應用

在 kernel/sched/core.c 中分別定義了取得與設定 affinity 的函式，sched_getaffinity 、 sched_setaffinity 。

extern long sched_setaffinity(pid_t pid, const struct cpumask *new_mask);
extern long sched_getaffinity(pid_t pid, struct cpumask *mask);

函式引數中的 cpumask 的每一個 bit 代表一個處理器，當第 n 個 bit 被設為 1 時，即代表此程式可以在第 n 個上運行，透過設定 cpumask 上的 bit 即可以指定程式可以在哪些固定的處理器上執行。(CPU Affinity)

位於 /include/linux/cpumask.h 的函式 cpumask_nth() 作用為取得 cpumask 當中第 n 個處理器

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

其實作的原理即為，使用 find_nth_bit 找出 cpu_mask 中的第 n 個 bit。

提問

使用巨集（macro)定義寒是的好處是什麼？

因為巨集是由前製處理器（preprocessor)預處理的，本質上算是字串代換，因此使用巨集定義函式時，不需考慮傳入參數的資料型別。

但如果此函式的傳入參數型別是固定的，以 find_nth_bit 實作程式為例，FIND_NTH_BIT(addr[idx], size, n)中，addr、size、n的資料型別必定為unsigned long *、unsigned long、unsigned long，此時使用巨集定義函式就沒有了上述的優勢。且FIND_NTH_BIT中定義了新的變數，如果重複使用FIND_NTH_BIT，會造成變數重複定義的問題，引發編譯時的錯誤。

因此，在find_nth_bit 實作程式中，將FIND_NTH_BIT定義為一般函式應該會比較安全，也方便出現錯誤時追蹤程式，那麼使用巨集定義函式的優勢為何？