---
# System prepended metadata

title: 2024 q1 Homework 1 (lab0)
tags: [linux-kernel, lab0-c]

---

# 2024q1 Homework 1 (lab0)
[Github](https://github.com/AsaneZeto/lab0-c)
## 實驗環境
```
❯ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

❯ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85
```
## 實作佇列操作
### q_new
使用`malloc`配置一個`list_head`大小的記憶體 (由`sizeof(struct list_head)`決定)，根據`man malloc`：

> On error, these functions return NULL.  NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.

因此在使用`list.h`中定義的`INIT_LIST_HEAD`函式前須檢查這段記憶體位址。
```c
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}
```

### q_free
根據`queue.h`的描述得知，需要釋放所有佇列元素`element_t`及找到佇列整體的`list_head`
> q_free() - Free all storage used by queue, no effect if header is NULL

在`list.h`裡面有定義巨集`list_for_each_entry_safe`，可以安全的逐一走訪並移除包含鏈結串列節點的結構。

```c
void q_free(struct list_head *head) 
{   
    if(!head)
        return;
    
    element_t *ptr, *safe;
    list_for_each_entry_safe(ptr, safe, head, list) {
        q_release_element(ptr);
    }
    
    free(head);
}
```
### q_insert_head
檢查配置後的記憶體是否為有效的(`strdup`也是使用`malloc`)，若不是表示失敗回傳false，否則使用`list_add`把`node`加入佇列開頭後回傳true
```c
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }
    list_add(&node->list, head);
    return true;
}
```
### q_insert_tail

其實就是把佇列的最後一個元素當作head，並對它做`q_insert_head`可以節省重複的程式碼。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}
```
### q_remove_head
如果`head`是無效記憶體位址或是佇列為空的話直接回傳NULL。否則利用`container_of`巨集找到第一個元素的位址`element_t *node`後利用`list_del`把該節點從佇列中移除，接著利用`strncpy`把`node`的字串`node->value`複製到`sp`。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = container_of(head->next, element_t, list);
    list_del(&node->list);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}
```
### q_remove_tail
使用和`q_insert_tail`一樣的概念來減少重複的程式碼，只是這邊的`head`是最後一個元素的前一個(`head->prev->prev`)
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}
```
### q_delete_mid
使用快慢指標技巧找到中間節點。假設佇列大小是`n`，當`n`是
* 基數時會在`fast == head`時結束
* 偶數時會在`fast == head->prev`時結束

且`slow`都會停在第`n/2`個節點，也就是中間節點。
```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *slow = head->next, *fast = head->next->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    list_del_init(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}
```
### q_delete_dup
`struct list_head *node`走訪鏈結串列的節點，`struct list_head *ptr`用來記錄`node`之後的節點，並計算總共有幾個字串相同的節點(`cnt`)，超過一個表示存在副本。因為要刪除需要先從鏈結串列中移除後再釋放記憶體，所以用`element_t *tmp`來指向包含`node`的下一個節點所在的元素後再進行操作，直到副本全部刪除完畢。
```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    struct list_head *node = head;
    while (node->next != head) {
        struct list_head *ptr = node->next;
        int cnt = 1;
        while (ptr->next != head) {
            element_t *curr = list_entry(ptr, element_t, list);
            element_t *next = list_entry(ptr->next, element_t, list);
            if (strcmp(curr->value, next->value) == 0) {
                ptr = ptr->next;
                cnt++;
            } else
                break;
        }

        // found duplicated element
        if (cnt > 1) {
            while (cnt--) {
                element_t *tmp = list_entry(node->next, element_t, list);
                list_del(&tmp->list);
                q_release_element(tmp);
            }
        } else
            node = node->next;
    }
    return true;
}
```
### q_swap
`node`從第一個節點走訪整個鏈結串鍊，把`node`移動到`node->next`後面即可。
```c
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_is_singular(head))
        return;
    struct list_head *node;
    for (node = head->next; node != head && node->next != head;
         node = node->next) {
        list_del(node);
        list_add(node, node->next);
    }
}
```
### q_reverse
`node`指向第一個節點，把`node->next`移到佇列開頭直到`node`為佇列最後一個節點即可反轉佇列。
```c
void q_reverse(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return;

    struct list_head *node = head->next;
    while (node->next != head) {
        struct list_head *next = node->next;
        list_del(next);
        list_add(next, head);
    }
}
```
### q_reverseK
和`q_reverse`概念一樣，每k個節點作為一組子佇列，且`node`指向上一個子佇列的最後一個節點，當反轉下一組子佇列時節點會加在`node`後方。
```c
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_is_singular(head))
        return;

    int count = q_size(head);

    struct list_head *node = head;
    struct list_head *curr, *next;
    while (count >= k) {
        curr = node->next;
        for (int i = 0; i < k - 1; i++) {
            next = curr->next;
            list_del(next);
            list_add(next, node);
        }
        count -= k;
        node = curr;
    }
}
```
### q_descend & q_ascend
這一部分的函式實作會涉及到對`element_t`中的`value`值進行比較，為了讓程式碼更精簡，我參考了[list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h#L9)並自定義一個function pointer type `list_cmp_func_t`，允許透過實作不同的比較函數以滿足不同的需求。考慮到`element_t`的`value`是字串，所以會使用`strcmp`作為基礎比較函數，所以`list_cmp_func_t`回傳值的型別也是int。
```c
typedef int
    __attribute__((nonnull(1, 2))) (*list_cmp_func_t)(const struct list_head *,
                                                      const struct list_head *);

static inline int q_less(const struct list_head *a, const struct list_head *b)
{
    return strcmp(list_entry(a, element_t, list)->value,
                  list_entry(b, element_t, list)->value);
}

static inline int q_greater(const struct list_head *a, const struct list_head *b)
{
    return strcmp(list_entry(b, element_t, list)->value,
                  list_entry(a, element_t, list)->value);
}
```
`q_descend`的功用是要刪除所有後方有比自身更大的值的節點。因為`list_head`是雙向鏈結，直接從最後一個節點往前走訪，並刪除前方任何比它小的節點即可。
`q_ascend`的目標則是和`q_descend`正好相反，因此只需要替換`cmp`，其他的程式碼保持不變，為了避免程式碼的重複，將共用的部分抽出成一個函式`q_remove_cmp`，並讓cmp成為其中一個參數。如此`q_descend`和`q_ascend`只需要呼叫`q_remove_cmp`並傳入`q_less`或`q_greater`即可。
```c
static inline int q_remove_cmp(struct list_head *head, list_cmp_func_t cmp)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head) || list_is_singular(head))
        return q_size(head);

    struct list_head *node = head->prev;
    while (node != head && node->prev != head) {
        if (cmp(node, node->prev) < 0) {
            struct list_head *tmp = node->prev;
            list_del_init(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        } else
            node = node->prev;
    }
    return q_size(head);
}

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    return q_remove_cmp(head, q_greater);
}

int q_ascend(struct list_head *head)
{
    return q_remove_cmp(head, q_less);
}
```
### q_sort
- 首先參考了[Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort)的實驗結果，選擇一開始要將鏈結串列分割成排序好的子串列，注意每個子串列都是單向的。
- 但是在合併階段遇上問題，因為Linux kernel並不支援VLA，需要使用其他方法表達各個子串列。
- 參考[LJP-TW的實作](https://hackmd.io/@LJP/SyRFuull9#q_sort)後發現他使用和[linux/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中相似的技巧: 用sorted sublists開頭節點的`prev`指向上一個sorted sublists的開頭節點，因為在排序過程中皆是考慮單向的串列鏈結，`prev`會失去原本意義。
    - `chain`這個變數名有點難理解它的作用，事實上他會是合併前後sublist的第一個節點，因此在這邊重新命名為`subhead`。
- 最後將排序好的鏈結串列修復成雙向的。
```c
static void merge(struct list_head **head,
                  struct list_head *a,
                  struct list_head *b,
                  list_cmp_func_t cmp)
{
    struct list_head **tail = head;

    while (a && b) {
        if (cmp(a, b) <= 0) {
            *tail = a;
            a = a->next;
        } else {
            *tail = b;
            b = b->next;
        }

        tail = &(*tail)->next;
    }

    if (a) {
        *tail = a;
    } else if (b) {
        *tail = b;
    }
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    list_cmp_func_t q_cmp = descend ? q_greater : q_less;

    // Split original list into sorted sublists.
    struct list_head *h = head->next, *t = head->next;
    struct list_head *sublist = NULL;
    while (h != head) {
        while (t->next != head && q_cmp(t, t->next) <= 0) {
            t = t->next;
        }
        h->prev = sublist;
        sublist = h;
        t = t->next;
        t->prev->next = NULL;
        h = t;
    }

    // Merge sublists.
    struct list_head *tmp, *currsub;
    while (sublist->prev) {
        struct list_head **subhead;

        currsub = sublist;
        subhead = &sublist;
        while (currsub && currsub->prev) {
            tmp = currsub->prev->prev;
            merge(subhead, currsub, currsub->prev, q_cmp);
            subhead = &(*subhead)->prev;
            currsub = tmp;
        }
        *subhead = currsub;
    }
    // Fix doubly linked list
    head->next = sublist;
    tmp = head;
    while (sublist) {
        sublist->prev = tmp;
        tmp = sublist;
        sublist = sublist->next;
    }
    head->prev = tmp;
    tmp->next = head;
}

```
### q_merge
- 因為涉及到排序，所以一開始先把所有佇列變成單向鏈結
- `queue_contex_t`中有`int id`這個成員，我把它當作陣列的索引，使用分段合併
- 和`q_sort`一樣，最後把合併後的串列修復成雙向鏈結。
```c
static inline int get_contex_id(struct list_head *head)
{
    return list_entry(head, queue_contex_t, chain)->id;
}

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    int n_queue = 0;
    queue_contex_t *ptr = NULL;
    list_for_each_entry (ptr, head, chain) {
        n_queue++;
        ptr->q->prev->next = NULL;
    }

    list_cmp_func_t q_cmp = descend ? q_greater : q_less;

    struct list_head *l1, *l2;
    struct list_head *contex1, *contex2;
    for (int interval = 1; interval < n_queue; interval *= 2) {
        contex1 = head->next;
        contex2 = head->next;
        for (int i = 0; i < interval; i++)
            contex2 = contex2->next;

        while (get_contex_id(contex1) + interval < n_queue) {
            l1 = list_entry(contex1, queue_contex_t, chain)->q;
            l2 = list_entry(contex2, queue_contex_t, chain)->q;

            struct list_head *subhead = l1->next;
            struct list_head **indir = &subhead;
            merge(indir, subhead, l2->next, q_cmp);
            l1->next = *indir;
            INIT_LIST_HEAD(l2);
            if (get_contex_id(contex1) + 2 * interval > n_queue)
                break;
            for (int i = 0; i < interval * 2; i++) {
                contex1 = contex1->next;
                contex2 = contex2->next;
            }
        }
    }

    // Fix doubly linked list
    l1 = list_entry(head->next, queue_contex_t, chain)->q;
    struct list_head *prev = l1, *curr = l1->next;
    while (curr) {
        curr->prev = prev;
        prev = curr;
        curr = curr->next;
    }
    l1->prev = prev;
    prev->next = l1;
    return q_size(l1);
}
```
## 研讀論文〈Dude, is my code constant time?〉
### 論文貢獻
用統計分析測量一段程式碼是不是常數時間，藉此規避需要硬體模型的問題

### 方法: Timing Leakage Detection

- 對程式執行時間做leakage detection test
    - 測量兩種資料的執行時間並對它們的分布(timing distribution in this context)做統計檢定
- 三個步驟:Measure execution time, Apply post-processing, Apply statistical test
    - Step 1: Measure execution time:
        1. Classes definition: Leakage detection對需要兩種data class採取兩套測量。例如fix-vs-random tests: 第一種資料會固定在某個常數值(for corner case)，而第二種資料是隨機採樣。
        2. Cycle counters: 用來精確的測量執行時間
        3. Environmental conditions: class assignment和input preparation都在測量執行時間前完成，以最小化環境對測量結果的影響
    - Step 2: Apply post-processing
        1. Cropping: 除去measurment artifacts (e.g., interrupted by OS)或修剪到某個特定的threshold
        2. Higher-order preprocessing: 根據採用的統計檢定，做某些higher-order preprocessing可能有好處。
    - Step 3: Apply statistical test
        - 用統計檢定拒絕虛無假設: 兩筆資料集的執行時間分布相同
        - t-test: Welch’s t-test
        - Non-parametric tests
### Student's t-distribution 
- 在只知道樣本的情況下使用
- 自由度決定PDF的形狀，自由度越高越像常態分佈
- 統計量$t=\frac{\bar{X}_n-\mu}{S_n /\sqrt{N}}$
    - $N$為樣本數
    - $\mu$為母體平均數
    - $\bar{X}_n$為樣本平均數
    - $S_n$為樣本標準差
#### Welch's t-test
- Student's t-test的變化版，在兩樣本有不一樣的變異數及樣本數量的情況下更可靠
- 統計量 $t=\frac{\bar{X}_1-\bar{X}_2}{\sqrt{s^2_{\bar{X}_1}+s^2_{\bar{X}_1}}}$
    - $\bar{X}_i$: 第i種樣本的平均數
    - $s_{\bar{X}_1}=\frac{s_i}{N_i}$: 第i種樣本的標準誤差 (standard error)
    - $s_i=\sqrt{\frac{1}{N_i-1}\sum^N_{j=1}(X_{ij}-\bar{X_i})^2}$: Corrected sample standard deviation
### 補齊lab0-c處理percentile的程式碼
將[oreparaz/dudect](https://github.com/oreparaz/dudect)中處理percentile的程式碼補進lab0-c的dudect裡即可，注意percentiles的記憶體空間要記得釋放。push後即可看到卡比。
![image](https://hackmd.io/_uploads/SyEY4Ih26.png)

## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案
### 研讀[lib/list_sort.c]((https://github.com/torvalds/linux/blob/master/lib/list_sort.c))
#### list_cmp_func_t cmp
```c
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);
```
- `list_cmp_func_t cmp`
    -  is a pointer to function that takes a pointer to void and two pointers to const struct list_head which are non-NULL, returning int.
    - 功用：自定義的排序關係 (ordering relation)
    - 如果要把串列排序成遞增
        - return > 0: 把a排在b後面 (a > b)
        - return <= 0: 把a排在b前面，或是保留相對順序 (a <= b)
    - 讓`list_sort`是stable sort

#### merge
- 給定自定義的compare function，合併兩個sublists`a`和`b`
- tail使用pointer to pointer的技巧
- 視覺化`merge`裡會發生什麼事，假設現在要合併兩個sorted sublists `a=[1,3]`和`b=[2]`成一個遞增的串列
```graphviz
digraph merge{
    rankdir=LR
    graph [fontname="DFKai-SB"];
    node [fontname="DFKai-SB"];
    edge [fontname="DFKai-SB"];
    subgraph sg1 {
        nil[label = "NIL",shape=point]
        head[shape=plaintext]
        tail[shape=plaintext]
        tail->head->nil
    }
    subgraph sgb{
        b[label="b", shape=plaintext]
        ln2[label = "{<value> 2|{<next> next}}", shape=record]
        nil2[label = "",shape=point]
        ln2:next->nil2
        b->ln2:value
    }
    subgraph sga{
        a[label="a" shape=none]
        ln1[label = "{<value> 1|{<next> next}}", shape=record]
        ln3[label = "{<value> 3|{<next> next}}", shape=record]
        nil1[label = "" shape=point]
        a->ln1:value
        ln1:next->ln3
        ln3:next->nil1
    }
}
```
- 第一個迭代`cmp(priv, a, b) <= 0`成立：
    - `head`會指向兩個sublist中最小的節點`a`，並且`head`會成為合併後的第一個節點。
    - `tail`從指向`head`轉為指向`a->next`
    - `a`指向下一個節點
```graphviz
digraph merge{
    rankdir=LR
    graph [fontname="DFKai-SB"];
    node [fontname="DFKai-SB"];
    edge [fontname="DFKai-SB"];

    subgraph sgb{
        b[label="b", shape=plaintext]
        ln2[label = "{<value> 2|{<next> next}}", shape=record]
        nil2[label = "",shape=point]
        ln2:next->nil2
        b->ln2:value
    }
    subgraph sga{
        a[label="a" shape=none]
        ln1[label = "{<value> 1|{<next> next}}", shape=record]
        ln3[label = "{<value> 3|{<next> next}}", shape=record]
        nil1[label = "" shape=point]
    }
    
    head[shape=plaintext]
    tail[shape=plaintext]
    head->ln1
    tail->ln1:next
    ln1:next->ln3
    a->ln3
    ln3:next->nil1
}
```
- 第二個迭代`cmp(priv, a, b) > 0`成立：
    - `*tail = b`: 讓`tail`所指向的`next`指向下一個要加入的節點，這邊是`b`
    - `tail`從指向`a->next`轉為指向`b->next`
    - `b`指向下一個節點
```graphviz
digraph merge{
    rankdir=LR
    graph [fontname="DFKai-SB"];
    node [fontname="DFKai-SB"];
    edge [fontname="DFKai-SB"];

    subgraph sgb{
        b[label="b", shape=plaintext]
        ln2[label = "{<value> 2|{<next> next}}", shape=record]
        nil2[label = "",shape=point]
        ln2:next->nil2
    }
    subgraph sga{
        a[label="a" shape=none]
        ln1[label = "{<value> 1|{<next> next}}", shape=record]
        ln3[label = "{<value> 3|{<next> next}}", shape=record]
        nil1[label = "" shape=point]
    }
    
    head[shape=plaintext]
    tail[shape=plaintext]
    head->ln1
    tail->ln2:next
    ln1:next->ln2
    a->ln3
    ln3:next->nil1
    b->nil2
}
```
- 因為`b`已經是NULL，`if (!b)`成立，表示`b`已經沒有結點要合併，直接讓`tail`接上`a`剩下的節點即可。
```graphviz
digraph merge{
    rankdir=LR
    graph [fontname="DFKai-SB"];
    node [fontname="DFKai-SB"];
    edge [fontname="DFKai-SB"];

    subgraph sgb{
        b[label="b", shape=plaintext]
        ln2[label = "{<value> 2|{<next> next}}", shape=record]
        nil2[label = "",shape=point]
    }
    subgraph sga{
        a[label="a" shape=none]
        ln1[label = "{<value> 1|{<next> next}}", shape=record]
        ln3[label = "{<value> 3|{<next> next}}", shape=record]
        nil1[label = "" shape=point]
    }
    
    head[shape=plaintext]
    tail[shape=plaintext]
    head->ln1
    tail->ln2:next
    ln1:next->ln2
    a->ln3
    ln2:next->ln3
    ln3:next->nil1
    b->nil2
}
```
- 可以獲得結論：`head`會是已合併串列的第一個節點，並且是`merge`的回傳值；`tail`從第一個節點加入後指向已合併串列的最後一個節點的`next`。
#### merge_final
合併最後兩個sorted sublists，並且重新連結prev以復原雙重鏈結串列。
#### list_sort
- 核心思想：維持$2:1$的sublist size，當有兩個$2^k$大小的sublist，且蒐集到第三個大小為$2^k$的sublist時才進行合併。
- 在排序過程中，所有的串列都是單向鏈結且最後一個節點的next指向NULL。
- 變數`pending`:
    - is a prev-linked "list of lists" of sorted sublists awaiting further merging.
    - 排序好的子串列大小必為2的冪
    - 不會有超過2個同樣大小的sublist
- 變數`count`: 
    - 目前pending lists的元素個數
    - 每當增加`count`時，會使某個位元變成1(假設是第k個)，並且第k-1到第0個位元變成0。這時候會合併兩個大小為$2^k$的sublists成一個$2^{(k+1)}$的sublist (counts第一次要到達$2^{(k+1)}$的時候不合併 i.e, 所有位元都是1).
```c
	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);
```
- 這邊觀察merge前後(如果需要)`count`和`pending`的狀態，以利了解程式碼。紅色標示`bits`會停在哪個位元(i.e., `tail`會停在pending的哪個sorted sublist)，以及下次迭代會合併的兩個sublists大小。假設我們有16個節點要排序：

| Iteration |    迭代開始時的  counts            | Merge? | 迭代結束時的counts | 迭代結束時的pending                       |
| --------- |:---------------------------:|:------:|:------:| ------------------------------ |
| 0         |              0              |   X    |   1    | 1                              |
| 1         |              1              |   X    |   10   | <font color=red>1-1</font>     |
| 2         |  1<font color=red>0</font>  |   V    |   11   | 1-2                            |
| 3         |             11              |   X    |  100   | <font color=red>1-1</font>-2   |
| 4         | 10<font color=red>0</font>  |   V    |  101   | 1-<font color=red>2-2</font>   |
| 5         | 1<font color=red>0</font>1  |   V    |  110   | <font color=red>1-1</font>-4   |
| 6         | 11<font color=red>0</font>  |   V    |  111   | 1-2-4   |
| 7         |             111             |   X    |  1000  | <font color=red>1-1</font>-2-4 |
| 8         | 100<font color=red>0</font> |   V    |  1001  | 1-<font color=red>2-2</font>-4 |
| 9         | 10<font color=red>0</font>1 |   V    |  1010  | <font color=red>1-1</font>-4-4 |
| 10        | 101<font color=red>0</font> |   V    |  1011  | 1-2-<font color=red>4-4</font> |
| 11        | 1<font color=red>0</font>11 |   V    |  1100  | <font color=red>1-1</font>-2-8 |
| 12        | 110<font color=red>0</font> |   V    |  1101  | 1-<font color=red>2-2</font>-8 |
| 13        | 11<font color=red>0</font>1 |   V    |  1110  | <font color=red>1-1</font>-4-8 |
| 14        | 111<font color=red>0</font> |   V    |  1111  | 1-2-4-8                        |
| 15        | 1111                        |   X    | 10000  | <font color=red>1-1</font>-2-4-8                               |
- 把所有節點都加進pending後`do-while`迴圈就會結束，這時候還不一定是完整的sorted list，所以需要把`pending`所有的sorted sublist合併。
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}
```
- 假設要排序一個8個節點的鏈結串列`[3 6 7 5 1 4 8 2]`，`do-while`迴圈結束時的狀態是
```graphviz
digraph 
{ rankdir=LR
node[shape=box]
nil1[label="" shape=none]
nil2[label="" shape=none]
nil3[label="" shape=none]
nil4[label="" shape=none]
nil5[label="" shape=none]
p[label="pending" shape=plaintext]
2
8
1 4
3 5 6 7
2->8->1->3->nil5 [label=prev]
p->2
2->nil1 [label=next]
8->nil2 [label=next]
1->4->nil3 [label=next]
3->5->6->7->nil4 [label=next]
{rank=same 2 8 1 3 nil5}
}
```
- `for`迴圈結束時的狀態
```graphviz
digraph 
{ rankdir=LR
node[shape=box]
nil1[label="" shape=none]
nil2[label="" shape=none]
nil3[label="NULL" shape=none]
nil4[label="" shape=none]
p[label="pending" shape=plaintext]
l[label="list" shape=plaintext]
n[label="next" shape=plaintext]
2
8
1 4
3 5 6 7
l->1
p->3
n->nil3
1->3->nil3 [label=prev]
1->2->4->8->nil1 [label=next]
3->5->6->7->nil2 [label=next]
{rank=same 1 3 nil3}
}
```
- 最後需要用`merge_final`合併`pending`和`list`，並且重新建立`prev`以復原雙重鏈結。
```c
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
### 引入list_sort到lab0-c專案
1. 將`list_sort.h`、`list_sort.c`放在專案根目錄下
- `list_sort.h`
    - 需要補充定義在`/include/linux/compiler.h`的巨集`likely()`、`unlikeky()`以及`u8`。
    - 為了支援在`qtest`的使用，修改`list_sort`的宣告。
```diff
+    #define likely(x) __builtin_expect(!!(x), 1)
+    #define unlikely(x) __builtin_expect(!!(x), 0)
+    typedef uint8_t u8;


-    __attribute__((nonnull(2,3)))
-    void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
+    __attribute__((nonnull(2))) void list_sort(void *priv,
+                                               struct +list_head *head,
+                                               bool descend);
```
- `list_sort.c`
    - 實作compare function 
    - `q_less(a,b)`< 0時表示`a < b`，`a`要優先加入已排序的串列，最後會得到遞增數列。
    - `q_greater(a,b)` < 0時表示`a > b`，`a`要優先加入已排序的串列，實作只需要交換`q_less(a,b)`的順序。最後會得到遞減數列。
```diff
+    static inline int q_less(void *priv,
+                             const struct list_head *a,
+                             const struct list_head *b)
+    {
+        element_t *elem_a = list_entry(a, element_t, list);
+        element_t *elem_b = list_entry(b, element_t, list);
+        return strcmp(elem_a->value, elem_b->value);
+    }

+    static inline int q_greater(void *priv,
+                                const struct list_head *a,
+                                const struct list_head *b)
+    {
+        return q_less(priv, b, a);
+    }
```
- `list_sort()`需要補上判斷使用哪個compare function的表達式。
```diff
__attribute__((nonnull(2))) void list_sort(void *priv,
                                           struct list_head *head,
                                           bool descend)
{ 
    ...
+   list_cmp_func_t q_cmp = descend ? q_greater : q_less;
    ...
    do{
        ...
        if (likely(bits)) {
            ...
-           a = merge(priv, cmp, b, a);
+           a = merge(priv, q_cmp, b, a);
            ...
        }
        ...
    } while (list);
    ...
    for (;;) {
        ...
-       list = merge(priv, cmp, pending, list);
+       list = merge(priv, q_cmp, pending, list);
        ...
    }

-    merge_final(priv, cmp, head, pending, list);
+    merge_final(priv, q_cmp, head, pending, list);
}
```
3. `qtest.c`
    - 為了未來可擴充不同排序演算法，事先對演算法排編號，並定義一個靜態全域變`sort`，在`do_sort`裡面就可以依據`sort`的值搭配`switch`來切換 (預設就是`q_sort`)。
    - 在`console_init()`裡加上`sort`參數後，在命令列就可以使用`option sort [value]`來取代`sort`的值。
```diff
+   #include "list_sort.h"
+   /* Which sorting algorithm will be used? */
+   #define LISTSORT 1
+   static int sort = 0;

    bool do_sort(int argc, char *argv[])
    {
        ...
        if (current && exception_setup(true)) {
-            q_sort(current->q, descend);
+            switch (sort) {
+            case LISTSORT:
+               list_sort(NULL, current->q, descend);
+               break;
+           default:
+               q_sort(current->q, descend);
+               break;
+           }
        }
        ...
    }

    static void console_init()
    {
+        add_param("sort", &sort, "Specify the sorting algorithm.", NULL);
    }
```

5. Makefile的dependency需要加上`list_sort.o`
```diff
-    linenoise.o web.o
+    linenoise.o web.o list_sort.o
```
- 發送commit時出現靜態分析失敗，錯誤訊息說在`list_sort.c`的`q_less`出現Null pointer dereference，但`list_entry`是`container_of`的包裝，`0`只是當作運算元而不會真正去存取，因此cppcheck誤判`list_entry`有dereference `0`。
> 參考：[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
```
list_sort.c:16:25: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *elem_a = list_entry(a, element_t, list);
                    ^
```
* 查閱[Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf)，提及可以直接使用註解作inline suppression (p.17)：
```
You can suppress a warning aaaa with:
// cppcheck-suppress aaaa
```
* 加上`// cppcheck-suppress nullPointer`後能夠順利commit。
```diff
 static inline int q_less(void *priv,
                         const struct list_head *a,
                         const struct list_head *b)
 {
+   // cppcheck-suppress nullPointer
    element_t *elem_a = list_entry(a, element_t, list);
+   // cppcheck-suppress nullPointer
    element_t *elem_b = list_entry(b, element_t, list);
    return strcmp(elem_a->value, elem_b->value);
 }
```
P.S. 在`script/pre-commit.hook`裡也能看到對`queue.c`和`qtest.c`有一樣的抑制。
### 比較效能
[list_sort論文研讀](https://hackmd.io/@ri_0LQgKRHOwpfTXUW3Rxg/By7w2_Oaa)
## References
1. [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort)
2. [2022q1 Homework1 (lab0) by LJP-TW](https://hackmd.io/@LJP/SyRFuull9#2022q1-Homework1-lab0)
3. [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
4. [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf)