2022q1 Homework1 (lab0)

contributed by < leewei05 >

tags: linux2022

安裝開發工具

$ sudo apt install -y linux-cloud-tools-5.13.0-28-generic linux-tools-5.13.0-28-generic gcc gnuplot make
$ sudo apt install -y build-essential git-core valgrind libc6-dbg
$ sudo apt install -y cppcheck clang-format aspell colordiff

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           61
Model name:                      Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
Stepping:                        4
CPU MHz:                         600.000
CPU max MHz:                     2700.0000
CPU min MHz:                     500.0000
BogoMIPS:                        4389.77
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3

$ cppcheck --version
Cppcheck 1.90

作業要求

實作 queue.c 的函式，包含以下：

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
• q_release_element: 釋放特定節點的記憶體空間;
• q_size: 計算目前佇列的節點總量;
• q_delete_mid: 移走佇列中間的節點，包括釋放記憶體空間。
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點。
• q_swap: 交換佇列中鄰近的節點。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
• q_sort: 以遞增順序來排序鏈結串列的節點。

• q_delete_mid: 利用 double linked list 的特性重構
• q_swap: 利用 XOR swap 重構
• q_sort: 試著利用 list.h 所提供的 API 來實作，並且比較不同 sorting algorithm
• q_shuffle
• 整合 tiny web server
• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理

q_new

queue.c 引用 queue.h，而 queue.h 裡引用 list.h，所以可以直接使用 INIT_LIST_HEAD 來初始化一個空的 list head。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));

    if (head) {
        INIT_LIST_HEAD(head);
        return head;
    }

    return NULL;
}

q_free

根據 Linux 核心原始程式碼巨集: container_of 的說明，可以透過 container_of 巨集反向存取結構體的記憶體起始位置。有了起始位置後，就能透過 q_release_element(element_t *e) 來釋放節點記憶體。

// node: struct list_head 的物件
// type: 包裝 struct list_head 的結構體，這裡為 element_t
/*
typedef struct {
    char *value;
    struct list_head list;
} element_t;
*/
// member: struct list_head 位於 element_t 裡的名稱，這裡為 list
#define list_entry(node, type, member) container_of(node, type, member)

首先檢查 l 是否為 NULL。透過 list_empty 檢查 list 是否有 node 連接帶入的 head，有的話則呼叫 list_del 刪除 node 並斷開與 list 的連結以及呼叫 list_entry(包裝 container_of) 清除記憶體。

void q_free(struct list_head *l)
{
    if (!l)
      return;

    // list_empty Return: 0 - list is not empty !0 - list is empty
    while (!list_empty(l)) {
        struct list_head *del = l->next;
        list_del(del);
        q_release_element(list_entry(del, element_t, list));
    }

    free(l);
    return;
}

q_insert_head

首先檢查傳入的 head 是否為 NULL。接著配置一個 element_t(定義為 linked list 的 element) 的記憶體空間給 node。檢查 node 是否為 NULL，如果不是 NULL 即初始化 node。以下為INIT_LIST_HEAD 的註解：

This can also be used to initialize a unlinked list node.

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

    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;

    INIT_LIST_HEAD(&node->list);

The strdup() function returns a pointer to the duplicated string, or NULL if insufficient memory was available.

如果 node->value 配置記憶體失敗，需要釋放 node 配置的記憶體，否則 trace-11-malloc 會失敗。

// 沒有釋放節點所佔用的記憶體
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 3 blocks are still allocated
---	trace-11-malloc	0/6

// 有釋放節點所佔用的記憶體
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6

    int size = sizeof(char) * (strlen(s) + 1);
    node->value = malloc(size);
    if (!node->value) {
        free(node);
        return false;
    }

    // strncpy will insert null byte at the end
    strncpy(node->value, s, size);
    node->value[size - 1] = '\0';
    list_add(&node->list, head);

    return true;
}

重構 insert，把 insert head 跟 insert tail 重複使用到的程式碼獨立出來：

bool alloc_helper(element_t *node, char *s)
{
    if (!node)
        return false;

    INIT_LIST_HEAD(&node->list);
    int size = sizeof(char) * (strlen(s) + 1);
    node->value = malloc(size);
    if (!node->value) {
        free(node);
        return false;
    }

    // strncpy will insert null byte at the end
    strncpy(node->value, s, size);
    node->value[size - 1] = '\0';
    return true;
}

重構後 q_insert_head 如下：

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

    element_t *node = malloc(sizeof(element_t));
    bool is_alloc = alloc_helper(node, s);
    if (!is_alloc)
        return false;

    list_add(&node->list, head);
    return true;
}

q_insert_tail

實作思路如同 q_insert_head，唯一不同的只有最後呼叫的函式 list_add_tail。這個函式是利用 strdup 來實作，似乎也是可以通過測試。如果之後有問題再改成跟 q_insert_head 相同的實作方法。

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

    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;

    INIT_LIST_HEAD(&node->list);
    char *str = strdup(s);
    if (!str) {
        free(node);
        return false;
    }
    
    node->value = str;
    list_add_tail(&node->list, head);

    return true;
}

重構 insert，把 insert head 跟 insert tail 重複使用到的程式碼獨立出來：

bool alloc_helper(element_t *node, char *s)
{
    if (!node)
        return false;

    INIT_LIST_HEAD(&node->list);
    int size = sizeof(char) * (strlen(s) + 1);
    node->value = malloc(size);
    if (!node->value) {
        free(node);
        return false;
    }

    // strncpy will insert null byte at the end
    strncpy(node->value, s, size);
    node->value[size - 1] = '\0';
    return true;
}

重構後 q_insert_tail 如下：

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

    element_t *node = malloc(sizeof(element_t));
    bool is_alloc = alloc_helper(node, s);
    if (!is_alloc)
        return false;

    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

Remove 不同於 delete，前者只需要斷開與 list 的連結而不需要釋放 node 的記憶體。檢查 head 是否為 NULL 以及 queue 是否是一個空的 queue。

呼叫 list_first_entry 取得 head 的 node，呼叫 list_del 把 node 從 list 中斷並檢查 sp 是否為 NULL。如果 sp 不是 NULL 則複製已移除 node 的字串內容至 sp。

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

    if (list_empty(head))
        return NULL;
    
    element_t *del = list_first_entry(head, element_t, list);
    list_del(&del->list);
    if (!sp)
        return del;

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

一開始忘記在字串後插入 \0，用 ./qtest 測試功能都沒問題。

cmd> new
l = []
cmd> ih dog
l = [dog]
cmd> ih bear
l = [bear dog]
cmd> rh bear
Removed bear from queue
l = [dog]
cmd> 

在跑 make test 時出現 Error limit exceeded，才想到要插入 terminating null byte ('\0')。查閱 strncpy 手冊，有以下敘述：

If there is no terminating null byte in the first n bytes of src, strncpy() produces an unterminated string in dest. You can force termination using something like the following:

strncpy(buf, str, n);
if (n > 0)
    buf[n - 1]= '\0';

---	trace-06-ops	0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_jXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value aardvark_bear_dolphin_gerbilXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil
ERROR: Removed value aardvark_bear_dolphinXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin
ERROR: Removed value meerkat_panda_squirrelXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---	trace-06-ops	0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_jXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value aardvark_bear_dolphin_gerbilXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil
ERROR: Removed value aardvark_bear_dolphinXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin
ERROR: Removed value meerkat_panda_squirrelXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel
Error limit exceeded.  Stopping command execution
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel
Error limit exceeded.  Stopping command execution

q_remove_tail

思唯如同 q_remove_head 但只是移除 tail node。

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

    if (list_empty(head))
        return NULL;

    element_t *del = list_last_entry(head, element_t, list);
    list_del(&del->list);
    if (!sp)
        return del;

    strncpy(sp, del->value, bufsize);
    sp[bufsize - 1] = '\0';

    return del;
}

q_size

根據牛刀小試，利用 list_for_each 走訪各個 node。

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

由於底層的 list 為 doubly-linked list，所以可以運用 Floyd’s Cycle detection 來找到中間的節點。兔子一次走訪兩個節點，烏龜一次走訪一個節點，考慮到兩種可能：

• 偶數節點：兔子剛好會繞一圈回到 head
• 奇數節點：兔子的下一個節點為 head

只要滿足上述任一條件，則烏龜的節點為中間節點。找到節點後再利用 list_entry, list_del, q_release_element 函式移除節點並釋放記憶體。

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

    struct list_head *rabbit = head->next->next;
    struct list_head *turtle = head->next;

    while ((rabbit != head) && (rabbit->next != head)) {
        rabbit = rabbit->next->next;
        turtle = turtle->next;
    }

    element_t *del = list_entry(turtle, element_t, list);
    list_del(&del->list);
    q_release_element(del);
    return true;
}

q_swap

走訪 list 中的節點，互換各個 node 直到下一個節點為 head。目前的程式碼不夠直覺，需要再想看看有沒有方法可以最佳化它。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if ((!head) || list_empty(head))
        return;

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        // swap nodes
        struct list_head *first = node, *second = node->next;
        second->prev = first->prev;
        first->prev = second;
        second->next->prev = first;
        second->prev->next = second;
        first->next = second->next;
        second->next = first;
        // traverse to next after swapped
        node = node->next;
    }
}

q_reverse

根據下方的圖 [cat, eat, fat] 需要反轉為 [fat, eat, cat]。利用 *tmp 指標，互換各個 node 的 prev, next 直到回到 head。

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

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

    struct list_head *tmp = head->prev;
    head->prev = head->next;
    head->next = tmp;
} 

是否有一個通用的方法可以不用額外處理 head?

q_sort

在研讀 你所不知道的 C 語言: linked list 和非連續記憶體 的 Merge Two Sorted Lists 案例時，想不通為什麼倒數第二行的 *ptr 也就是 head 不用指到 head->next。查看規格書之後得知：

6.8.5.3 The for statement
1 The statement
for ( clause-1 ; expression-2 ; expression-3 ) statement
behaves as follows: The expression expression-2 is the controlling expression that is
evaluated before each execution of the loop body. The expression expression-3 is
evaluated as a void expression after each execution of the loop body.

ptr = &(*ptr)->next 是在每一個 loop statement 執行完成之後才執行。所以 ptr 最後會指到一個 NULL，這也是為什麼倒數第二行直接指派剩餘的 node 給 ptr 而非 ptr = &(*ptr)->next。

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2) { 
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

為了避免分支 *ptr = list1 ? list1 : list2;，這個實作選擇用 OR 運算取代條件判斷。運算元 A 對 0 做 OR 運算返回的值也會是 A，上述的程式碼即是使用此特性。NULL pointer 轉換成 uintptr_t 型別即為 0。此行程式碼 *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2); 剛好有同學在 討論區發問，藉此也查閱規格書：

7.18.1.4 Integer types capable of holding object pointers
The following type designates a signed integer type with the property that any valid
pointer to void can be converted to this type, then converted back to pointer to void,
and the result will compare equal to the original pointer:
intptr_t
The following type designates an unsigned integer type with the property that any valid
pointer to void can be converted to this type, then converted back to pointer to void,
and the result will compare equal to the original pointer:
uintptr_t
These types are optional.

針對 lab0 的 q_sort 實作，因為現在的 list 為 doubly linked list，為了可以使用上述的 merge sort 程式碼，我想要把 list 先拆成兩個 singly linked list。剛好可以運用 Floyd’s Cycle detection 來取得中間值，並從該節點切分為兩個 linked list。但 sort 完之後需要把頭尾相接，恢復成原本的 doubly linked list。

原本想要使用 indirect pointer 來實作並且把 if else 拿掉，但是一直噴 l1, l2 is not changed in loop 的錯誤，試了很久還找不到問題只好先改成下列的實作方式。

試著把中間的 if else 條件拿掉

struct list_head *mergelists(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head;
    struct list_head **ptr = &head;
    for (; l1 && l2; ptr = &(*ptr)->next) {
        element_t *l1_entry = list_entry(l1, element_t, list);
        element_t *l2_entry = list_entry(l2, element_t, list);
        // a negative value if s1 is less than s2;
        if (strcmp(l1_entry->value, l2_entry->value) < 0) {
            *ptr = l1;
            l1 = l1->next;
        } else {
            *ptr = l2;
            l2 = l2->next;
        }
    }

    *ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}

msort 透過遞迴的方式來實作，持續把 linked list 對半切分直到 return call stack。

struct list_head *msort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *rabbit = head;
    struct list_head *turtle = head;

    while (rabbit && rabbit->next) {
        rabbit = rabbit->next->next;
        turtle = turtle->next;
    }

    struct list_head *mid = turtle;
    // divide two list
    turtle->prev->next = NULL;
    struct list_head *list1 = msort(head);
    struct list_head *list2 = msort(mid);
    return mergelists(list1, list2);
}

把 linked list 尾巴斷開後進行 merge sort 排序。因為排序完只有單向是有順序的，所以需要再走訪每個 node 把反向的指標補齊。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    head->prev->next = NULL;
    head->next = msort(head->next);

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

q_delete_dup

在已經排序的狀況，移走佇列中具備重複內容的節點。初步想法是利用 list_for_each_entry_safe，參考 quiz1 測驗三的作法。初步的實作，在本地端測試都過但是在跑 CI 時出現以下錯誤

queue.c: In function ‘q_delete_dup’:
queue.c:240:20: error: ‘dup’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
240 | } else if (strcmp(dup, entry->value) == 0) {
| ^~~~~~~~~~~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors

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

    element_t *entry, *s;
    char *dup;
    list_for_each_entry_safe (entry, s, head, list) {
        if (entry->list.next != head &&
            strcmp(entry->value,
                   list_entry(entry->list.next, element_t, list)->value) == 0) {
            /* store duplicate value */
            dup = list_entry(entry->list.next, element_t, list)->value;
            list_del(&entry->list);
            q_release_element(entry);
        } else if (strcmp(dup, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
        }
    }

    return true;
}

以下透過 valgrind 進行記憶體使用分析

➜  lab0-c git:(master) make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/lee/linux2022/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o linenoise.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .linenoise.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
queue.c: In function ‘q_delete_dup’:
queue.c:240:20: error: ‘dup’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
  240 |         } else if (strcmp(dup, entry->value) == 0) {
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors
make[1]: *** [Makefile:50: queue.o] Error 1
make[1]: Leaving directory '/home/lee/linux2022/lab0-c'
make: *** [Makefile:63: valgrind] Error 2

Valgrind will use this information to determine if a change to the stack pointer is an item pushed onto the stack
or a change over to a new stack. Use this if you're using a user-level thread package and are noticing crashes in
stack trace recording or spurious errors from Valgrind about uninitialized memory reads.

讀完 Valgrind 的手冊並且再看了自己的程式碼，發現如果沒有沒有重複的 node 則 dup 不會有值，所以會出現 unintialized read。故改成以下的程式碼:

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

    element_t *entry, *s;
    bool dup = false;
    list_for_each_entry_safe (entry, s, head, list) {
        if (entry->list.next != head &&
            strcmp(entry->value,
                   list_entry(entry->list.next, element_t, list)->value) == 0) {
            /* store duplicate value */
            dup = true;
            list_del(&entry->list);
            q_release_element(entry);
        } else if (dup) {
            list_del(&entry->list);
            q_release_element(entry);
            dup = false;
        }
    }
    return true;
}

qtest - shuffle

需求：在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作

根據 lab0 的說明：

一旦事先提供 do_* 函式，並在 console_init 中呼叫 add_cmd("<instruction>", <do_*>, "<documentation>")，即可增加新命令。以下示範在console.c 檔案新增名為 hello 的命令。先準備 do_hello 函式:

先使用 do_hello 的範例實作 shuffle:

bool do_shuffle(int argc, char *argv[])
{
   return (bool) printf("Hello, World\n");
} 

Fisher Yates 演算法實作步驟

1. 假設 array 長度為 8，定義變數 j 為 7
2. 從 0 到 j 隨機取一個數 i
3. array[i] 與 array[j] 進行互換
4. j 減 1
5. 重複步驟 2 到 4 直到 j 為 1

qtest - web

在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
可依據前述說明，嘗試整合 tiny-web-server