---
# System prepended metadata

title: 2021q1 Homework1 (lab0)
tags: [jserv]

---

# 2021q1 Homework1 (lab0)
contributed by < [paul90317](https://github.com/paul90317) >

## 實驗環境
```shell
$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

$ lscpu
架構：                          x86_64
CPU 作業模式：                   32-bit, 64-bit
Byte Order:                    Little Endian
Address sizes:                 39 bits physical, 48 bits virtual
CPU(s):                        8
On-line CPU(s) list:           0-7
每核心執行緒數：                  2
每通訊端核心數：                  4
Socket(s):                     1
NUMA 節點：                     1
供應商識別號：                    GenuineIntel
CPU 家族：                      6
型號：                          158
Model name:                    Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz
製程：                          10
CPU MHz：                      2400.000
CPU max MHz:                   4100.0000
CPU min MHz:                   800.0000
BogoMIPS:                      4800.00
虛擬：                          VT-x
L1d 快取：                      128 KiB
L1i 快取：                      128 KiB
L2 快取：                       1 MiB
L3 快取：                       8 MiB
NUMA node0 CPU(s)：            0-7
```

## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)

- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
    - 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
    - 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
    - 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
    - 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
    - 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server) 
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
    - 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
        - 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
    - 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
    - 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
    - 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request


## 開發過程

### q_new
檢查 malloc 是否正常運作
```cpp
struct list_head *q_new()
{
    // don't LIST_HEAD maybe it's calloc
    // auto return NULL
    // not a node, just a queue.
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}
```

### q_free
要記得先清掉 value
```cpp
void q_free(struct list_head *l)
{
    if (l == NULL)
        return;
    struct list_head *node = l->next;
    while (node != l) {
        list_del(node);
        q_release_element(container_of(node, element_t, list));
        node = l->next;
    }
    free(l);
}
```

### q_insert_head
一開始我遇到的問題是，我以為以為 head 外面有一個 contaier（資料型別為 element_t） 且包含 value。
然而我後來發現不是，它只是被一個 list_head_meta_t 的 struct 裡的指標所指到，且他的記憶體一開始已經挖好了。

**element_t**
```cpp
typedef struct {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct list_head list;
} element_t;
```
**list_head_meta_t**
```cpp
typedef struct {
    struct list_head *l;
    /* meta data of list */
    int size;
} list_head_meta_t;
```
在 head 右邊插入新的節點
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;
    element_t *new_node = (element_t *) malloc(sizeof(element_t));
    if (new_node == NULL)
        return false;
    list_add(&new_node->list, head);
    int len = strlen(s);
    new_node->value = (char *) malloc(len + 1);
    if (new_node->value == NULL)
        return false;
    memcpy(new_node->value, s, len + 1);
    return true;
}
```

### q_insert_tail
跟 insert head 滿像的
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;
    element_t *new_node = (element_t *) malloc(sizeof(element_t));
    if (new_node == NULL)
        return false;
    list_add_tail(&new_node->list, head);
    int len = strlen(s);
    new_node->value = (char *) malloc(len + 1);
    if (new_node->value == NULL)
        return false;
    memcpy(new_node->value, s, len + 1);
    return true;
}
```

### q_remove_head
移除 head 右邊的節點
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
    element_t *ele = container_of(head->next, element_t, list);
    if (sp) {
        char *src = ele->value;
        int len = min(strlen(src), bufsize - 1);
        memcpy(sp, src, len);
        sp[len] = 0;
    }
    list_del(&(ele->list));
    return ele;
}
```

### q_remove_tail
移除 head 左邊的節點
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
    element_t *ele = container_of(head->prev, element_t, list);
    if (sp) {
        char *src = ele->value;
        int len = min(strlen(src), bufsize - 1);
        memcpy(sp, src, len);
        sp[len] = 0;
    }
    list_del(&(ele->list));
    return ele;
}
```
### q_size
回傳 queue 大小，這是非常數時間的寫法。
原本是常數時間的，但那個解法有錯，因為我以為 list_head_meta_t 是 container (對於 member l 來說)，然而其實 l 型別是 struct list_head*，是一個使到容器的指標，這讓我們無法透過 head 去得到 l_meta 的位置，所以出錯。
還有一點就是 因為 qtest.c 已經 include queue.h 這個檔案，而 struct list_head_meta_t 是在 qtest.c 定義的，導致我不能使用 container_of，必須自己計算出（雖然前面已經證明是不行的，但這是我一開始的做法）。
```cpp
int q_size(struct list_head *head)
{
    if (head == NULL)
        return 0;
    int ret = 0;
    struct list_head *node;
    list_for_each (node, head) {
        ret++;
    }
    return ret;
}
```

### q_delete_mid
我是先計算出中間位置在哪裡，在用 list_for_each 到那個位置把節點刪除，非常數時間。
```cpp
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    int size = q_size(head);
    if (head == NULL || size == 0)
        return false;
    struct list_head *node;
    size = size / 2;
    list_for_each (node, head) {
        if (size == 0) {
            list_del(node);
            q_release_element(container_of(node, element_t, list));
            break;
        }
        size--;
    }
    return true;
}
```

### q_delete_dup
把重複的節點一個不留的刪除，輸入是以排序 queue
```cpp
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (head == NULL)
        return false;
    struct list_head *node = head->next, *next;
    while (node != head) {
        int flag = 0;
        while ((next = node->next) != head && n_cmp(node, next) == 0) {
            list_del(next);
            q_release_element(container_of(next, element_t, list));
            flag = 1;
        }
        if (flag) {
            list_del(node);
            q_release_element(container_of(node, element_t, list));
        }
        node = next;
    }
    return true;
}
```
### q_swap
節點位置兩兩交換
若長度是奇數，最後一個不動
作法： 先從 head 取出兩個節點，再變換順序堆入 tail。
```cpp
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    int size = q_size(head);
    if (head == NULL || size <= 1)
        return;
    struct list_head *a;

    for (int i = 0; i < size / 2; i++) {
        a = head->next;
        list_del(a);
        struct list_head *b = head->next;
        list_del(b);
        list_add_tail(b, head);
        list_add_tail(a, head);
    }
    if ((size & 0b1) == 1) {
        a = head->next;
        list_del(a);
        list_add_tail(a, head);
    }
}
```

### q_reverse
先宣告新的 queue h2 ，頭尾接到 head 的 prev, next，這代表 h2 會有跟 head 相同的 element。
接著將 head 初始化，把 h2 所有 element 從頭取出放進 head 的前面，達到反轉。
```cpp
void q_reverse(struct list_head *head)
{
    if (head == NULL)
        return;

    struct list_head h2;
    int size = q_size(head);
    h2.next = head->next;
    h2.prev = head->prev;
    head->next->prev = &h2;
    head->prev->next = &h2;
    INIT_LIST_HEAD(head);
    for (int i = 0; i < size; i++) {
        struct list_head *node = h2.next;
        list_del(node);
        list_add(node, head);
    }
}
```
有看到別人是將每個 element 的 prev, next 反轉，應該之後會改(等到 action 拿到滿分後)

以下是改進版
```cpp
inline void swap_child(struct list_head *node)
{
    struct list_head *t;
    t = node->next;
    node->next = node->prev;
    node->prev = t;
}
void q_reverse(struct list_head *head)
{
    if (head == NULL || head->next == NULL || head->prev == NULL)
        return;

    struct list_head *node;
    swap_child(head);
    for (node = head->prev; node != head; node = node->prev) {
        swap_child(node);
    }
}
```
### q_sort
merge sort，我是採用迴圈寫法，但這個跑在 action 會 TLE，我覺得應該是我移動到中間節點的方式是用迴圈慢慢移，應該有更快的方法。
```cpp
static inline struct list_head *merge(struct list_head *a,
                                      struct list_head *b,
                                      int asize,
                                      int bsize)
{
    struct list_head *tmp, htmp, *h;
    h = a->prev;
    INIT_LIST_HEAD(&htmp);
    int i = 0, j = 0;
    while ((i < asize) || (j < bsize)) {
        if ((j == bsize) || ((i < asize) && (n_cmp(a, b) < 0))) {
            tmp = a->next;
            list_del(a);
            list_add_tail(a, &htmp);
            a = tmp;
            i++;
        } else {
            tmp = b->next;
            list_del(b);
            list_add_tail(b, &htmp);
            b = tmp;
            j++;
        }
    }
    tmp = h->next;  // last

    tmp->prev = htmp.prev;
    htmp.prev->next = tmp;

    h->next = htmp.next;
    htmp.next->prev = h;

    return tmp;
}
```
```cpp
void q_sort(struct list_head *head)
{
    int size = q_size(head);
    if (head == NULL || size <= 1)
        return;
    for (int iter = 1; iter < size; iter <<= 1) {
        int rem = size;
        struct list_head *a = head->next;
        while (rem > iter) {
            rem -= iter;
            struct list_head *b = a;
            for (int i = 0; i < iter; i++)
                b = b->next;
            a = merge(a, b, iter, min(iter, rem));
            rem -= iter;
        }
    }
}
```
### qsort 改進
我覺得我之前寫的 merge sort 之所以會跑的慢，應該是因為我太拘泥於使用 linux list.h 內建的函式。

我發現，其實要排序 linked list，只要一個指標 (prev) 就夠了，而 next 就可以用來指向其他以排序的列表，而 prev 只想列表內已經排序的元素
![](https://i.imgur.com/W5pyOCc.png)
經過預處理後如下
![](https://i.imgur.com/qDkEjUI.png)
我們可以看橫向的每個元素都是以排序的列表，他們是各自列表唯一的元素。

接著我們就能進行 merge，先將最左兩以排序列表取出（無須查找中間點），進行合併，並且放到最右，這個操作相當於用迭代寫法 merge 兩個序列，並且當隨著時間推移我們一開始合併的序列，又會來到最左，這相當於迭代寫法合併序列長度增大，但不一樣的是，迭代寫法需要跳出巢狀迴圈把合併序列長度增加，但是我的改進版從頭到尾只用做同一件事。
![](https://i.imgur.com/H48nToJ.png)

當合併到剩下兩個序列的時候，需要跳出迴圈，進行最後的合併，再去把剩下的一條垂直序列變成 linux doubly linked list，完成。

為何不要合併到剩最後一條時，再轉成 doubly linked list，原因是我在合併前，會先把兩條序列取出，可是當我們取出剩下的兩條時，front 會變成 null，這樣在推到 back 時，就需要多一 if 取檢測 front 是否為 null，且要多傳遞一個變數到 h_push ，不符合 C 語言簡潔的風格。

**程式碼**
```cpp
static inline void h_push(struct list_head *node, struct list_head **back)
{
    (*back)->next = node;
    node->next = NULL;
    *back = node;
}
static inline struct list_head *h_pop(struct list_head **front)
{
    struct list_head *node = *front;
    *front = node->next;
    return node;
}
static inline void v_push(struct list_head *node, struct list_head **back)
{
    (*back)->prev = node;
    node->prev = NULL;
    *back = node;
}
static inline struct list_head *v_pop(struct list_head **front)
{
    struct list_head *node = *front;
    *front = node->prev;
    return node;
}
```
```cpp
static inline struct list_head *merge(struct list_head *a, struct list_head *b)
{
    struct list_head front = {0, 0}, *back = &front;
    struct list_head *tmp;
    while (a || b) {
        if (!b || (a && n_cmp(a, b) < 0)) {
            tmp = v_pop(&a);
        } else {
            tmp = v_pop(&b);
        }
        v_push(tmp, &back);
    }
    return front.prev;
}

void q_sort(struct list_head *head)
{
    if (head == NULL || q_size(head) <= 1)
        return;

    struct list_head *front = head->next, *back = head->prev;

    // make vertival one node
    struct list_head *node;
    list_for_each (node, head) {
        node->prev = NULL;
    }
    back->next = NULL;  // cut down horizonal back

    while (front->next != back) {
        node = h_pop(&front);
        node = merge(node, h_pop(&front));
        h_push(node, &back);
    }

    front = merge(front, back);
    INIT_LIST_HEAD(head);
    for (node = front; node; node = back) {
        back = node->prev;
        list_add_tail(node, head);
    }
}
```