2024q1 Homework2 (quiz1+2)

contributed by < jimmylu890303>

第一周測驗題

• 題目

測驗一

程式運作原理

測驗是參考 Optimized QuickSort — C Implementation (Non-Recursive) ，實作非遞迴 (non-recursive; iterative) 的快速排序法。 再使用

• list_add
  在這個函式中，它會插入一顆新的節點到原本串列的前方，他傳入一個 node_t ** list 的參數為 pointer to pointer ， 因為 C 語言的在函數中傳入的參數為一個副本，所以要將原本 head 指標改指向到新的節點上，就需要使用 pointer to pointer 的方式去更改原本的 head 指標。

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

  圖片取自於你所不知道的 C 語言：指標篇，在函數傳入參數時，會複製一份副本 p ，這個指標會指向原本的 head 指標。
  

  
  透過更改 head 指標所指向的位置可以將 ptrA 的指標更改成下個位置。
  
  

• list_tail
  在這個函式中會去尋找著串列中的最後一個節點位置並回傳該位置，它傳入一個 node_t ** left 的參數，但是這邊使用方式為 indirect pointer ，為了可以能夠更精簡程式碼，可以省略一些條件判斷的行數。

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

  但是在這個函式中，使用 node_t *left中也是可以的，並不會增加程式碼的行數。

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

• list_length
  在這個函式中會計算串列中的長度，但是傳入的參數為 node_t **left ， 使用方式為 indirect pointer，所以在迴圈內 left 要指向的位置必須為 node_t * 的指標，所以 left 在迴圈內操作會指向 (*left)->next 。

• quick_sort
  在 quick_sort 中一開始宣告 max_level = 2 * n 為堆疊深度，為了模仿遞迴中堆疊的行為。 begin 負責儲存串列的頭元素位置， end 負責儲存串列的尾元素位置， i 負責模擬堆疊中 pop 操作。

  ​​​​    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 迴圈負責控制 stack 的行為，每次迴圈內，從 bgein 和 end 取出串列的頭部及尾部節點位置。如果 L != R 則代表該串列元素大於一個，反之串列元素剩下一個，在將該元素加入到 result 的結果串列中。

  ​​​​while (i >= 0) {
  ​​​​    node_t *L = begin[i], *R = end[i];
  ​​​​    if (L != R) {
  ​​​​        //
  ​​​​    } else {
  ​​​​        if (L)
  ​​​​            list_add(&result, L);
  ​​​​        i--;    
  ​​​​    }
  ​​​​}
  

  p 指標一開始會為 pivot 的下個元素， 在 while § 迴圈內會將此串列分割成 left 和 right 兩個串列。 left 串列為元素值小於 pivot， right 串列為元素值大於 pivot。

  ​​​​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 = p->next;
  ​​​​​       list_add(n->value > value ? &right : &left, n);
  ​​​​​   }
  
  

  將串列分成 left 和 right 串列後，就需要將他們存入到 begin 和 end 中，在這個部分因為 list_add 是將新的元素插入到串列的第一個，所以堆疊的順序是高位為 right 。

  ​​​​    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);
  
  ​​​​    left = right = NULL;
  ​​​​    i += 2;
  

提出改進方案並予以實作

以上程式碼在事先宣告兩個大小為 max_level 的 begin 和 end 陣列太耗費記憶體空間了，假設在 n =

${10}^6$ 且處理器架構為32位元的情況，一個 begin 陣列就需要高達

$4\times 2\times {10}^6$ Bytes， 所以這個部分我覺得可以使用 dynamic array 的方式去實作這個陣列。

我將原先的 begin 和 end 兩個陣列作更改成動態陣列的方式，先只事先宣告成長度為 n 的陣列。

+ int stack_size = n;
- int max_level = 2 * n;
+ node_t **begin =(node_t **) malloc(sizeof(node_t *)*stack_size);
+ node_t **end =(node_t **) malloc(sizeof(node_t *)*stack_size);
- node_t *begin[max_level], *end[max_level];

若stack空間不足，在 realloc 堆疊空間。

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

left = right = NULL;
i += 2;
+ if(i>=stack_size-3){
+    stack_size+=3;
+    begin = realloc(begin,sizeof(node_t*)*stack_size);
+    end = realloc(end,sizeof(node_t*)*stack_size);
+}

改成使用動態陣列的方式，這些資料會存放在 heap 的區塊，而原先的陣列方式為區域變數，所以會存放在堆疊的區塊。

使用 valgrind 的 massif 來追蹤使用動態陣列的程式碼堆積的使用狀況。

$ valgrind --tool=massif --stacks=yes ./main.elf 
==6045== Massif, a heap profiler
==6045== Copyright (C) 2003-2017, and GNU GPL'd, by Nicholas Nethercote
==6045== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==6045== Command: ./main.elf
==6045== 
==6056==

$ massif-visualizer massif.out.6056 
QCommandLineParser: already having an option named "h"
QCommandLineParser: already having an option named "help-all"
QCommandLineParser: already having an option named "v"
loaded massif file: QUrl("file:///home/jimmylu/linux2024/hw2/quick_sort/massif.out.6056")
description: "--stacks=yes"
command: "./main.elf"
time unit: "i"
snapshots: 55
peak: snapshot # 10 after 2.09999e+06 "i"
peak cost: "507.8 KiB" heap "78.1 KiB" heap extra "592 B" stacks

而原先的程式碼

$ valgrind --tool=massif --stacks=yes ./origin.elf 
==6165== Massif, a heap profiler
==6165== Copyright (C) 2003-2017, and GNU GPL'd, by Nicholas Nethercote
==6165== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==6165== Command: ./origin.elf
==6165== 
==6165== 

$ massif-visualizer massif.out.6165 
QCommandLineParser: already having an option named "h"
QCommandLineParser: already having an option named "help-all"
QCommandLineParser: already having an option named "v"
loaded massif file: QUrl("file:///home/jimmylu/linux2024/hw2/quick_sort/massif.out.6165")
description: "--stacks=yes"
command: "./origin.elf"
time unit: "i"
snapshots: 56
peak: snapshot # 11 after 2.23016e+06 "i"
peak cost: "351.6 KiB" heap "78.1 KiB" heap extra "313.1 KiB" stacks

從上面兩圖可以發現若使用動態陣列，會使得 heap 的使用區塊增加。

從 stackoverflow 節錄以下對話。

To measure the heap memory use valgrind -> massif
To measure the static memory use the bash function size on the binary
To measure the stack it is possible to use stackusage

所以我使用 stackusage 這個工具來觀察堆疊的區塊使用率。

觀察改善後面的程式

$ stackusage ./main.elf 
stackusage log at 2024-03-07 23:57:24 ----------------------------------------
  pid  id    tid  requested     actual     maxuse  max%    dur               funcP name
 6269   0   6269    8388608    8384512       5160     0      0               (nil) main.elf

觀察原本的程式

$ stackusage ./origin.elf 
stackusage log at 2024-03-07 23:57:59 ----------------------------------------
  pid  id    tid  requested     actual     maxuse  max%    dur               funcP name
 6297   0   6297    8388608    8376320     321344     3      0               (nil) origin.elf

可以發現若使用動態陣列的方式可以有效去改善佔用太多堆疊區塊空間的問題。

測驗二

Tim Sort 結合合併排序和插入排序的特點，如今已廣泛用於生活的各個地方，而 TimSort 主要的想法是在現實世界中，許多資料往往是由一些已經部分排序的序列組合而成，所以首先的策略是識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序。

首先在使用 Time Sort 時會先將原本的串列的最後一個節點解除環狀佇列，並將它指向 NULL

而以下程式碼操作的流程為每次呼叫 find_run 後會找到一個 `un , 接下來使用 result.head 和 result.next 記錄整個 run 的頭尾，並且會記錄該 run 的長度在 head->next->prev 當中。

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

下圖為 find_run 所回傳的 struct pair 的 result ， result.head 為此回合找到的 run 。

而在 find_run 中以下程式碼將 size_t 型態的變數強制轉型成 struct list_head * 型態，並且讓 head->next->prev 指標存放這個值，這個寫法個人覺得非常的有趣，因為指標裡頭的內容是存放目標位置，該目標位址的型態為指標的型態，但這邊作法是指標存放 len 裡頭存放的值，透過這指標可能會存取到非法區塊，並且這區塊的型態不是指標所指向的型態。

static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    // 中間省略
    head->next->prev = (struct list_head *) len;
}

所以因為以上緣故，才可以透過 run_size 來存取此 run 的長度。

static inline size_t run_size(struct list_head *head)
{
    if (!head)
        return 0;
    if (!head->next)
        return 1;
    return (size_t) (head->next->prev);
}

經過幾次的 find_run ，串列會被分成若干個 run ，而 tp 會指向堆疊中最上面的 run ，也就是最新的 run 。

之後使用 merge_collapse 檢查堆疊中上面 3 段的 run 的長度是否滿足以下原則：

• A 的長度要大於 B 和 C 的長度總和。
• B 的長度要大於 C 的長度。

在以下情況進行合併

1. A <= B+C && A < C : AB 合併
2. A <= B+C && A >= C : BC 合併
3. B <= C : BC合併

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)))
       {
        // A <= B+C  and A < C => AB 合併
        if (run_size(tp->prev->prev) < run_size(tp)) {
            tp->prev = merge_at(priv, cmp, tp->prev);
        } 
        // A <= B+C  and A>=C => BC 合併
        else {
            tp = merge_at(priv, cmp, tp);
        }
    }
    // B<=C => BC合併
    else if (run_size(tp->prev) <= run_size(tp)) {
        tp = merge_at(priv, cmp, tp);
    } else {
        break;
    }
}

之後會透過 merge_force_collapse 將多個 run 進行合併，直到 run 總數 < 3 為止。

最後因為經過 merge_force_collapse 合併後，run 總數 < 3 ，所以可能的總數為 1 或 2 ，若為 1 則直接呼叫 build_prev_link ， 若為 2 則呼叫 merge_final 合併最後的 run ，如以下程式碼所示。

if (stk_size <= 1) {
    build_prev_link(head, head, stk0);
    return;
}
merge_final(priv, cmp, head, stk1, stk0);

第二周測驗題

題目

測驗一

給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹，但是是運用 Linux 核心的 hash table 實作 來完成實作。

而在 linux 核心中 hash table 視覺圖如下

Hash table 中的元素為 hlist_head ，而 Hash table 中各個 bucket 的節點為 hlist_node

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

使用前序和中序來完成 buildTree ，首先會透過中序建立 hash table ，而雜湊函數的作法是使用 Division method 的方式

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

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);
}

之後使用遞迴的方式呼叫 dfs 來完成建樹的工作

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}

而在 dfs 中 TreeNode tn 的值為前序 index 最低的點(即 pre_low) ，在藉由透過 find 去尋找此點在中序的 index ，再依序 dfs 遞迴左子樹及右子樹完成建樹，而在左子樹和右子樹的前序和中序的 low , high index 的設定如下

• 左子樹
  • pre_low : 為原本的 pre_low + 1
  • pre_high : 為原本的 pre_low + 1 再加上 (idx - in_low) ， (idx - in_low) 表示為中序當前點左子樹的節點個數
  • in_low : 原本的最低索引 in_low
  • in_high : 根節點的左邊

• 右子樹
  • pre_low : 為原本的 pre_high 再減 (in_high - idx - 1) ，(in_high - idx - 1) 為中序根節點右子樹的數量
  • pre_high : 為原本的 pre_high
  • in_low : 根節點的右邊
  • in_high : 原本的最高索引 in_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;

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

測驗二

此題是使用雜湊表來模仿 cache 的實作，考慮以下結構

struct hlist_head {
    struct hlist_node *first;
};
struct hlist_node {
    struct hlist_node *next, **pprev;
};
typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

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

使用 lRUCacheCreate 創建 cache ，透過 hhead[ ] ，可將要存放的資料存入 cache

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
-                             capacity * sizeof(struct list_head));
+                             capacity * sizeof(struct hlist_head));
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}

使用 lRUCachePut 來存放資料
首先會去對應的雜湊表檢查要新增的值是否存在，若存在此 key 則忽略存入此值，並去在 dhead 中更新 LRU 的順序。

struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
    LRUNode *c = list_entry(pos, LRUNode, node);
    if (c->key == key) {
        list_move(&c->link, &obj->dhead);
        cache = c;
    }
}

若沒在 hash table 中沒找到對應的 key ，則需存入該值，則會有以下狀況 :

1. cache 容量已滿 : 需要使用 list_last_entry 尋找 dhead 中最後面的節點 (代表最不常被使用到)，並將它從 dhead 中移動到第一個位置且從原本的雜湊表中移除，這裡值得注意是它並無重新 malloc 一個新的空間給新的值，而是重複使用的舊空間，所以最後才會呼叫 hlist_add_head 將此節點新增到對應的雜湊表。
2. cache 容量未滿 : malloc 一個新的空間給新的值作存放。

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

使用 lRUCacheGet 可以去尋找 cache 中是否有對應的值並取出，若無該 key 則回傳 -1 。

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(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

實作程式

commit - 6040fbf

新增 multiplication hash function 並將原先的 hash function 額外包裝使程式碼更易維護

+int division_hash(LRUCache *obj,int key){
+    return key % obj->capacity;
+}

+int multiplication_hash(LRUCache *obj,int key){
+    double A = (sqrt(5) - 1) / 2;
+    double s = key * A;
+    double x = s - floor(s);
+    return floor(obj->capacity * x);
+}

+int hash_function(LRUCache *obj,int key){
+    if(obj->hash_type==0)
+        return division_hash(obj,key);
+    return multiplication_hash(obj,key);
+}

實作 test.py 比較原先測驗題目中的 division hash function 與我新實作的 multiplication hash function 兩者間的 Hash Collision 次數

從上圖中可以發現 multiplication 的方法碰撞次數相較 division 較為平均

$ python3 test.py 
Total count of division : 315699
mean : 154.14990234375,variance : 276.66877380579814
Total count of multiplication : 315439
mean : 154.02294921875,variance : 268.4845732226276

並且計算兩者的平均和變異數，multiplication 的方法皆比較低

LRU in Linux

linux/include/linux/lru_cache.h
linux/lib/lru_cache.c

lru_cache 是一個輔助的框架，它可以用於追蹤 index 和 label 間的關聯，並更改 Activate Set 中的 Objects 。

This header file (and its .c file; kernel-doc of functions see there)
define a helper framework to easily keep track of index:label associations,
and changes to an "active set" of objects, as well as pending transactions,
to persistently record those changes.

而它主要目的是使用於本地和遠端磁碟複製的 IO 操作， 若在複製節點時發生崩潰，需要重新同步所有曾經被寫入的IO操作的目標區域（使用中或熱區域），因為無法確定這些寫入是否已經存到遠端磁碟中。為了避免完全重新同步，需要持續追蹤這些區域，稱為 write intent log

在 lru_cache.h 中定義了兩個結構

struct lc_element {
	struct hlist_node colision;
	struct list_head list;		 /* LRU list or free list */
	unsigned refcnt;
	/* back "pointer" into lc_cache->element[index],
	 * for paranoia, and for "lc_element_to_index" */
	unsigned lc_index;
	/* if we want to track a larger set of objects,
	 * it needs to become an architecture independent u64 */
	unsigned lc_number;
	/* special label when on free list */
#define LC_FREE (~0U)

	/* for pending changes */
	unsigned lc_new_number;
};

refcnt : 紀錄目前被使用的次數，若為 0 可能會被 lru_cache 移動到 lru 或 free 的串列

struct lru_cache {
	/* the least recently used item is kept at lru->prev */
	struct list_head lru;
	struct list_head free;
	struct list_head in_use;
	struct list_head to_be_changed;

	/* the pre-created kmem cache to allocate the objects from */
	struct kmem_cache *lc_cache;

	/* size of tracked objects, used to memset(,0,) them in lc_reset */
	size_t element_size;
	/* offset of struct lc_element member in the tracked object */
	size_t element_off;

	/* number of elements (indices) */
	unsigned int nr_elements;
	/* Arbitrary limit on maximum tracked objects. Practical limit is much
	 * lower due to allocation failures, probably. For typical use cases,
	 * nr_elements should be a few thousand at most.
	 * This also limits the maximum value of lc_element.lc_index, allowing the
	 * 8 high bits of .lc_index to be overloaded with flags in the future. */
#define LC_MAX_ACTIVE	(1<<24)

	/* allow to accumulate a few (index:label) changes,
	 * but no more than max_pending_changes */
	unsigned int max_pending_changes;
	/* number of elements currently on to_be_changed list */
	unsigned int pending_changes;

	/* statistics */
	unsigned used; /* number of elements currently on in_use list */
	unsigned long hits, misses, starving, locked, changed;

	/* see below: flag-bits for lru_cache */
	unsigned long flags;


	const char *name;

	/* nr_elements there */
	struct hlist_head *lc_slot;
	struct lc_element **lc_element;
};

在 lru_cache.c 中

/**
 * lc_put - give up refcnt of @e
 * @lc: the lru cache to operate on
 * @e: the element to put
 *
 * If refcnt reaches zero, the element is moved to the lru list,
 * and a %LC_STARVING (if set) is cleared.
 * Returns the new (post-decrement) refcnt.
 */
unsigned int lc_put(struct lru_cache *lc, struct lc_element *e)
{
	PARANOIA_ENTRY();
	PARANOIA_LC_ELEMENT(lc, e);
	BUG_ON(e->refcnt == 0);
	BUG_ON(e->lc_number != e->lc_new_number);
	if (--e->refcnt == 0) {
		/* move it to the front of LRU. */
		list_move(&e->list, &lc->lru);
		lc->used--;
		clear_bit_unlock(__LC_STARVING, &lc->flags);
	}
	RETURN(e->refcnt);
}

lc_put 實作中可以看到若 refcnt 為 0 ，會把此 lc_element 移動到 lc_cache->lru 中

/**
 * lc_del - removes an element from the cache
 * @lc: The lru_cache object
 * @e: The element to remove
 *
 * @e must be unused (refcnt == 0). Moves @e from "lru" to "free" list,
 * sets @e->enr to %LC_FREE.
 */
void lc_del(struct lru_cache *lc, struct lc_element *e)
{
	PARANOIA_ENTRY();
	PARANOIA_LC_ELEMENT(lc, e);
	BUG_ON(e->refcnt);

	e->lc_number = e->lc_new_number = LC_FREE;
	hlist_del_init(&e->colision);
	list_move(&e->list, &lc->free);
	RETURN();
}

lc_del 則會將 lru 的 object 移動到 free 的串列

static int lc_unused_element_available(struct lru_cache *lc)
{
	if (!list_empty(&lc->free))
		return 1; /* something on the free list */
	if (!list_empty(&lc->lru))
		return 1;  /* something to evict */

	return 0;
}

再透過 lc_unused_element_available 檢查 lc_cache 中是否可用的區塊