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

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

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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` 命令