2022q1 Homework1 (lab0)

contributed by < zoanana990 >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  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
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping:                        9
CPU MHz:                         900.106
CPU max MHz:                     3800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5599.85
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

作業要求

在 GitHub 上 fork lab0-c
依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
利用 Valgrind 分析 q_test
在 qtest 提供新的命令 shuffle ，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
閱讀論文 Dude, is my code constant time?

作業 1. 修改`queue.[ch]`

`q_new` 實作

一開始的想法，要先初始化一個佇列(queue)，再將佇列中的 list_head 初始化，寫下以下程式碼：

struct list_head *q_new()
{
    // make an element
    element_t *q = malloc(sizeof(element_t));

    // if not malloc memory
    if (!q){
        free(q);
        return NULL;
    }
        
    // Initial the list node and value
    q->value = NULL;
    INIT_LIST_HEAD(&q->list);

    return &q->list;
}

然而這個程式碼無法編譯成功，顯示錯誤為 Attempted to free unallocated block ，這給我兩個想法：

element_t 沒有分配成功，因此不需要為了它去free

struct list_head *q_new()
{
    // make an element
    element_t *q = malloc(sizeof(element_t));

    // if not malloc memory
    if (!q){
        return NULL;
    }
    q->value = malloc(sizeof(char));
    if(!q->value){
        free(q);
        return NULL;
    }

    // Initial the list node and value
    q->value = NULL;
    INIT_LIST_HEAD(&q->list);

    return &q->list;
}

這邊仍然會出現錯誤，因此我改變 Makefile 指定測試13，看一下出現結果，目前我沒有在對上面版本的程式碼繼續調整

WARNING: Malloc returning NULL
l = NULL
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
l = []
cmd> new
Freeing old queue
ERROR: Attempted to free unallocated block.

函式回傳值要求為 struct list_head ，直接做一個 struct list_head 回傳就好， element_t 可以使用 list_entry 呼叫。

struct list_head *q_new()
{
    // make an element
    struct list_head *l = malloc(sizeof(struct list_head));

    // if not malloc memory
    if (!l)
        return NULL;

    // Initial the list node
    INIT_LIST_HEAD(l);

    return l;
}

這個程式碼可以繼續成功運行

`q_free` 實作

這個函式突顯了 container_of 的重要性，之前上課的時候完全不覺的 container_of 可以有什麼大的作用。在寫這個函式之後，完全沒有頭緒，因此回去重看了你所不知道的 C 語言: linked list 和非連續記憶體這時候才理解為什麼老師上課說 container_of 非常重要可以幫助程式變得很簡潔

一開始的程式碼：

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *curr;
    list_for_each (curr, l)
        q_release_element(list_entry(curr, element_t, list));
    free(l);
}

這裡直接報錯，原因是 curr 指向的佇列被刪除後， curr 也會被刪除，會出現 segmentation fault 錯誤
因此需要調整成先創立一個節點，等現在的節點跑到下一個之後，再把之前的節點獨立出來，在刪掉

最終程式碼：

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *curr = l->next;
    while(curr != l){
        struct list_head *prev = curr;
        curr = curr->next;
        list_del(prev);
        q_release_element(list_entry(prev, element_t, list));
    }
    free(l);
}

圖解說明：

一開始:

將 prev 紀錄 curr 及 curr 右移，程式碼對應如下：

struct list_head *prev = curr;
curr = curr->next;

刪除 bear ，先將節點獨立出來，再將記憶體釋放，程式碼對應如下

list_del(prev);
q_release_element(list_entry(prev, element_t, list));

利用 container_of 找到 queue 的位址進行刪除，經過n個迴圈後剩下原本的 head
將 head 釋放
結束

`q_insert` 實作

q_insert_head 和 q_insert_tail 很像，而重複的地方我寫成 q_insert ，這個函式主要是開 element_t 的空間及 char* 的空間，如果 element_t * 的空間沒有開成功則回傳false，如果 char * 的空間沒有開成功則須先釋放 element_t 的空間，再回傳false，否則會出現 Allocated Blocks 的錯誤

/*
 * Due to the repeated code in q_insert_head and q_insert_tail
 * write a functionto replace them
 */
element_t *q_insert(char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;
    q->value = malloc(sizeof(char) * (strlen(s) + 1));
    if(!q->value){
        free(q);
        return NULL;
    }
    strncpy(q->value, s, strlen(s));
    q->value[strlen(s)] = '\0';
    return q;
}

圖解說明：以插入頭為例

一開始

先分配佇列空間並檢驗是否分配成功
在分配字串空間並檢驗是否分配成功，若分配失敗須釋放佇列空間，否則會出現 allocated blocks 的錯誤

利用 linux API 直接插入即可

如此， q_insert_head 和 q_insert_tail 就可以寫出來：

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    // Boundary Condition
    if (!head)
        return false;

    // make a new element
    element_t *q = q_insert(s);

    if(!q)
        return NULL;

    // INIT_LIST_HEAD(&q_head->list);
    list_add(&q->list, head);

    return true;
}

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    // Boundary Condition
    if (!head)
        return false;

    // make a new element
    element_t *q = q_insert(s);

    if(!q)
        return s;

    list_add_tail(&q->list, head);

    return true;
}

`q_remove_head` 實作

q_remove_head 是將佇列的開頭移出鏈結串列中，因此需要利用 container_of 找出佇列的位址：
```
element_t *q_head = list_first_entry(head, element_t, list);
```

將節點斷開後，利用 memset, memcpy 或 strncpy等函式將字串複製到 sp 中，程式碼如下：

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *q_head = list_first_entry(head, element_t, list);
    list_del_init(&q_head->list);
    
    sp = realloc(sp, sizeof(char) * bufsize);
    
    if (sp) {
        strncpy(sp, q_head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return q_head;
}

然後直接報錯，因為
```
sp = realloc(sp, sizeof(char) * bufsize);
```
會出現 copying of string in remove_head overflowed destination buffer
如果把上面的程式碼換成：
```
sp = calloc(bufsize, sizeof(char));
```
則會發生Failed to store removed value
如果都沒有寫的話，則會通過測試，這裡是因為記憶體分配的問題，這幾天會看你所不知道的C語言找答案

最終程式碼：

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *q_head = list_first_entry(head, element_t, list);
    list_del_init(&q_head->list);

    if (sp) {
        strncpy(sp, q_head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return q_head;
}

圖解說明：

一開始

與 q_free 相同，先將 bear 獨立出來後利用 container_of 返回佇列

element_t *q_head = list_first_entry(head, element_t, list);
list_del_init(&q_head->list);

`q_remove_tail` 實作

可以直接使用 q_remove_head 的結果

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` 實作

這個函式老師在上課的時候有做範例，於是我也在 leetcode 2095 寫一下草稿：

struct ListNode* deleteMiddle(struct ListNode* head){
    if(!head) return NULL;
    struct ListNode *fast=head, **slow=&head;
    while(fast && fast->next){
        fast=fast->next->next;
        slow=&(*slow)->next;
    }
    (*slow) = (*slow)->next;
    return head;
}

將函式移植到作業時需要做一些調整：

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 *fast=head->next, *slow = head->next;
    for (;fast != head && fast->next!= head; fast = fast->next->next)
        slow = slow->next;

    
    q_release_element(list_entry(slow, element_t, list));
    list_del(slow);

    return true;
}

於是就順利的報錯了，錯誤內容 Segmentation fault occurred. You dereferenced a NULL or invalid pointer 也就是對空指標進行操作
這邊感謝 <Risheng1128> 的協助，問題出在下面這兩行：
```
q_release_element(list_entry(slow, element_t, list));
list_del(slow);
```
我先把整的佇列刪除了，如果再把 list_head 刪掉會造成重複刪除，就會報上面那個錯誤，所以應該先把節點抓出來再將佇列刪除，這樣就部會造成上面那個錯誤
```
list_del(slow); 
q_release_element(list_entry(slow, element_t, list));
```

最終程式碼：

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 *fast=head->next, *slow = head->next;
    for (;fast != head && fast->next!= head; fast = fast->next->next)
        slow = slow->next;

    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

圖解說明

一開始，slow 和 fast 設置在 head->next 。龜兔賽跑開始，設定迴圈終止條件為 fast != head 及fast->next != head

第一次迴圈， slow 前進一格、 fast 前進兩格

第二次迴圈，slow前進一格、fast前進兩格，達成終止條件

將 gerbil 刪除，如前面做法相似

`q_delete_dup` 實作

與前幾題相同，先利用leetcode82打草稿，這邊我是使用間接指標(indirect pointer)，屬於疊代法

由於 leetcode 屬於單向鏈結串列，這邊需要因為 linux kernel 調整程式碼的

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    struct list_head *prev = NULL, *curr = head->next, *next = curr->next;
    while (curr != head && next != head) {
        element_t *q_curr = list_entry(curr, element_t, list);
        element_t *q_next = list_entry(next, element_t, list);
        while (next != head && !strcmp(q_curr->value, q_next->value)) {
            prev = curr;
            list_del(next);
            q_release_element(list_entry(next, element_t, list));
            next = curr->next;
            q_next = list_entry(next, element_t, list);
        }
        if (prev) {
            list_del(prev);
            q_release_element(list_entry(prev, element_t, list));
            prev = NULL;
        }
        curr = next;
        next = curr->next;
    }
    return true;
}

`q_swap` 實作

先利用 leetcode 24 打草稿：

struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode **indirect=&head, *future=NULL, *current=head;
    while((*indirect) && (*indirect)->next){
        current = *indirect;
        future = current->next;
        current->next = future->next;
        future->next = current;
        *indirect = future;
        indirect = &(current)->next;
    }
    return head;
}

這邊需要對幾個地方做調整，

`q_reverse` 實作

在寫這題之前，我先去 leetcode 206 打草稿，草稿寫完如下：

大致上思路是很簡單的，用個指標一個一個前進，然後改變所只的方向即可，當然也可以使用遞迴呼叫的方式，但是作業的回傳值是 void 所以我使用比較直觀的方式去寫，以這題leetcode來說，遞迴法是比較好的選擇

遞迴法：

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL || head->next == NULL){
        return head;
    }
    struct node* next = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return next;
}

疊代法：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *prev=NULL;
    while(head){
        struct ListNode* next=head->next;
        head->next=prev;
        prev=head;
        head=next;
    }
    return prev;
}

作業是用疊帶法去寫的，但是仍然需要做一些調整：

linux_kernel 屬於doubly-circular linked list，因此 while 迴圈的中止條件及每個節點的連結需要調整
作業中的函式回傳值為 void 因此避免改動 head
改動完如下所示：

void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *curr = head, *prev = head->prev;
    while (next != head) {
        struct list_head *next = curr->next;
        curr->next = prev;
        curr->prev = next;
        prev = curr;
        curr = next;
    }
}

於是就順利的報錯了，主要的原因出在 struct list_head *next = curr->next; 及 curr->prev = next; 的關聯，如果是單向鏈結串列，這個寫法沒有問題，但是他是雙向，因此我們必須保留每個節點的存在，調整方式很簡單，只要把 next 在外面宣告即可

void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *curr = head, *prev = head->prev, *next = NULL;
    while (next != head) {
        next = curr->next;
        curr->next = prev;
        curr->prev = next;
        prev = curr;
        curr = next;
    }
}

`q_sort` 實作

本題我採用 merge sort 進行，在寫這題之前，我先對 leetcode 21, leetcode 148 進行練習，而本函式的撰寫即是這兩題的結合。

合併的程式碼有參考你所不知道的 C 語言: linked list 和非連續記憶體中的案例一 leetcode 21 的解說，程式碼如下：

struct ListNode* merge(struct ListNode* left, struct ListNode* right){
    // leetcode 21
    struct ListNode *head = NULL, **ptr = &head, **node;
    for(node = NULL; left && right; *node = (*node)->next){
        node = left->val > right->val ? &right : &left;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) left | (uintptr_t) right);
    struct ListNode* h = head;

    return head;
}

struct ListNode* sortList(struct ListNode* head){
    // leetcode 148
    if(!head || !head->next) return head;
    struct ListNode *fast = head->next, *slow = head;
    for(;fast && fast->next; fast = fast->next->next)
        slow = slow->next;
    struct ListNode *next = slow->next;
    slow->next = NULL;
    return merge(sortList(head), sortList(next));
}

實際程式碼如下，這邊有參考<Risheng1128>的建議

struct list_head *merge(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; left && right; *node = (*node)->next) {
        element_t *q_left = list_entry(left, element_t, list);
        element_t *q_right = list_entry(right, element_t, list);
        node = strcmp(q_left->value, q_right->value) < 0 ? &left : &right;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);

    return head;
}

struct list_head *MergeSort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *fast = head->next, *slow = head;
    for (; fast && fast->next; fast = fast->next->next)
        slow = slow->next;
    struct list_head *next = slow->next;
    slow->next = NULL;

    return merge(MergeSort(head), MergeSort(next));
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = MergeSort(head->next);

    struct list_head *curr, *prev = head;
    for (curr = head->next; curr; curr = curr->next) {
        curr->prev = prev;
        prev = curr;
    }

    prev->next = head;
    head->prev = prev;
}

作業 2. 以 `Valgrind` 分析記憶體問題

目前使用 valgrind進行分析時發現程式碼有記憶體洩漏的問題

==27236== 8 bytes in 1 blocks are still reachable in loss record 1 of 33
==27236==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==27236==    by 0x4A5250E: strdup (strdup.c:42)
==27236==    by 0x110E1D: linenoiseHistoryAdd (linenoise.c:1236)
==27236==    by 0x1119B0: linenoiseHistoryLoad (linenoise.c:1325)
==27236==    by 0x10CC24: main (qtest.c:1175)

作業 3. Shuffle

參考作業說明將 shuffle 命令 (Command) 加入，寫下以下程式碼

bool do_shuffle(int argc, char *argv[]){
    ...
}
...
add_cmd("shuffle", do_shuffle, "                | Shuffle the list");

已經參閱 Fisher–Yates shuffle 演算法，並且實作出來，程式碼如下

void shuffle(struct list_head *l, size_t size){
    if(size < 2) return;
    for(size_t i=size; i>0; i--){
        size_t index = rand()%i + 1;
        struct list_head *node = l;
        for(int j=0; j<index; j++)
            node = node->next;
        list_move_tail(node, l);
    }
}

其原理如下：隨機選取一個數字，該數字小於目前鏈結串列的尺寸。
例如：打亂下面這個鍊結串列，首先說隨機有一個索引目標假設現在是3，就會將 gerbil 移到最後面

如此就完成置換，重複這個動作，直到所有節點都被移動過為止

分析 Linux 核心原始程式碼的 `list_sort.c`

有了 shuffle 的功能，就可以分析 linux kernel 裡面的 list_sort 了，這邊使用老師提供的連結進行調整

說明效能如下表所示：

	10000	60000
My sort	0.004068	0.032433
linux kernel	0.003466	0.017465
linux kernel (消除檢查機制)	0.004291	0.039406

接下來讓我們探討速度落差在哪裡：

注意書寫規範：中英文間用一個空白字元區隔
:notes: jserv

作業 4. 加入 `Web` 命令

這邊有參考 <laneser> 的筆記進行實作，由於背景知識不足，這邊也先去閱讀 CS:APP 第11章

2022q1 Homework1 (lab0)

實驗環境

作業要求

作業 1. 修改`queue.[ch]`

`q_new` 實作

`q_free` 實作

`q_insert` 實作

`q_remove_head` 實作

`q_remove_tail` 實作

`q_delete_mid` 實作

`q_delete_dup` 實作

`q_swap` 實作

`q_reverse` 實作

`q_sort` 實作

作業 2. 以 `Valgrind` 分析記憶體問題

作業 3. Shuffle

分析 Linux 核心原始程式碼的 `list_sort.c`

作業 4. 加入 `Web` 命令

作業 5. 閱讀論文並實做

論文閱讀

程式實作

參考資料

2022q1 Homework1 (lab0)

實驗環境

作業要求

作業 1. 修改queue.[ch]

q_new 實作

q_free 實作

q_insert 實作

q_remove_head 實作

q_remove_tail 實作

q_delete_mid 實作

q_delete_dup 實作

q_swap 實作

q_reverse 實作

q_sort 實作

作業 2. 以 Valgrind 分析記憶體問題

作業 3. Shuffle

分析 Linux 核心原始程式碼的 list_sort.c

作業 4. 加入 Web 命令

作業 5. 閱讀論文並實做

論文閱讀

程式實作

參考資料

Read more

biRISC-V

Linux patch 心得

Linux 檔案系統

RISCV ISA

作業 1. 修改`queue.[ch]`

`q_new` 實作

`q_free` 實作

`q_insert` 實作

`q_remove_head` 實作

`q_remove_tail` 實作

`q_delete_mid` 實作

`q_delete_dup` 實作

`q_swap` 實作

`q_reverse` 實作

`q_sort` 實作

作業 2. 以 `Valgrind` 分析記憶體問題

分析 Linux 核心原始程式碼的 `list_sort.c`

作業 4. 加入 `Web` 命令