2023q1 Homework1 (lab0)

contributed by < peter91015 >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
架構：                   x86_64
  CPU 作業模式：         32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
供應商識別號：           GenuineIntel
  Model name:            Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz
    CPU 家族：           6
    型號：               158
    每核心執行緒數：     1
    每通訊端核心數：     4
    Socket(s):           1
    製程：               9
    CPU max MHz:         3500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6000.00

開發過程

q_new()

考慮 malloc() 可能會無法配置空間，所以在 malloc() 後面用 if 判斷是否成功並且使用 INIT_LIST_HEAD() 使新建節點的頭尾都指向自身並且回傳。

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (new)
        INIT_LIST_HEAD(new);
    return new;
}

q_free()

釋放佇列原先佔用的記憶體空間。作法是從 head 節點逐一走訪，對於每個節點用 list_entry 找出對應的 element 並且釋放其內部所指的字串以及自身的空間，最後再釋放 head 節點。

(更新：已修改變數名稱並且利用lish.h上的巨集)

void q_free(struct list_head *l)
{
    struct list_head *current = l->next;
    while (current != l) {
        element_t *tmp = list_entry(current, element_t, list);
        current = current->next;
        free(tmp->value);
        free(tmp);
    }
    free(l);
}

tra 並非清晰的簡稱，改進！
將 temp 改為 tmp，並將 while 敘述改為 for 迴圈，可縮短程式碼。
jserv

q_insert_head()

將新的 element 安插在 head 節點下一個位置。先用 malloc() 配置空間給新的 element，由於 element 裡面有字串，所以也需要配置空間並且用 memcpy() 將輸入的字串複製。最後要回傳功能是否正確剛好可以用新生成的 element 是否為 空指標 ??? 來作為判斷所以回傳指標的數值並轉成 bool 型態。
(更新：後續已將回傳的數值改為 true 和 false)

避免說「空指標」，因為漢語的「空」通常對應英語的 "empty" 一詞，但 null pointer 的語境根本不是 empty。可改說，「確認某個指標是否有效」，「有效」就隱含對指標內含值的檢查。
jserv

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_item = malloc(sizeof(element_t));
    if (!new_item)
        return false;
    size_t len_s = strlen(s) + 1;
    new_item->value = (char *) malloc(len_s);
    memcpy(new_item->value, s, len_s);
    list_add(&new_item->list, head);
    return true;
}

詳閱 CONTRIBUTING.md，留意 "Avoid unnecessary nesting levels" 一節，從而改寫程式碼
jserv

q_insert_tail()

和 q_insert_head() 幾乎是一樣的操作，差別只是要將 element 安插在 head node 的上一個位置。

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new_item = malloc(sizeof(element_t));
    if (!new_item)
        return false;
    size_t len_s = strlen(s) + 1;
    new_item->value = (char *) malloc(len_s);
    memcpy(new_item->value, s, len_s);
    list_add_tail(&new_item->list, head);
    return true;
}

詳閱 CONTRIBUTING.md，留意 "Avoid unnecessary nesting levels" 一節，從而改寫程式碼
jserv

(更新：後續修正的程式碼直接修改於上方的區塊。另外老師提到的遇到例外或非預期的情況須及早返回原先呼叫端以前沒有考慮過，謝謝老師的提醒，學到了一課。)

關鍵不是「沒有大括號」，而是遇到例外或非預期的情況，及早返回原本的函式呼叫端，這樣反映在程式碼風格上。
jserv

q_size()

計算輸入的佇列有幾個 element。利用 list.h 裡面的巨集 list_for_each 便可以走訪 doubly-linked list 所有節點並且用一個變數 cnt 計算個數。

注意書寫規範，中英文間用一個半形空白區隔。
雙向鏈結串列的英語是 doubly-linked list，留意連字號的用法。
jserv

int q_size(struct list_head *head)
{
    struct list_head *current = NULL;
    int cnt = 0;  // the counter for the number of element
    list_for_each (current, head)
        cnt++;
    return cnt;
}

q_reverse()

將佇列內的節點順序反轉。想法是走訪每個節點並且交換每個節點中的 next 和 prev 這兩個指標，由於交換的過程會改變原先節點的順序，所以必須使用 list_for_each_safe 以及使用額外的變數 prev 記錄上一個走訪的節點。最後再將 head 節點的兩個指標做交換即完成對佇列反轉。

void q_reverse(struct list_head *head)
{
    struct list_head *prev = head, *current = NULL, *next = NULL;
    list_for_each_safe (current, next, head) {
        current->next = prev;
        current->prev = next;
        prev = current;
    }
    // swap the next and prev pointers of head
    prev = head->next;
    head->next = head->prev;
    head->prev = prev;
}

將以上的函式實作完成後，就可以通過 make check 上面用到的操作了。

q_delete_mid()

這一題曾經在leetcode上面有寫過，不過當時在寫的時候是使用 singly-linked list。而這次使用的作法善用了 doubly-linked list 可以雙向走訪的特性，將兩個變數 next 和 prev 分別初始化為 head 節點的前一個和後一個節點，在每次迴圈都各自往前和往後一個，並且根據佇列內的節點數不同，會有兩種狀況表示 next 已經指在中點上：

• next 和 prev 指在同一個節點上
• 當下 next 所指的下一個節點是 prev 所指的節點

後續再使用 list_del 將節點移出，並且釋放節點所在的 element 以及 element 所指的字串之空間。

和 singly-linked list 的方法比較

singly-linked list 所使用的方法為用兩個指標進行走訪(一個比較快一次走兩步、另外一個一次走一步)當比較快的指標走到終點的時候，慢的指標所指的節點即為中點，而這個方法所需要走訪節點的個數為

$\lfloor \frac{n}{2}\rfloor +n$次，其中

$n$ 為節點的個數。而上面用在 doubly-linked list 的方法則只需要走訪

$2\cdot \lfloor \frac{n}{2}\rfloor$ 次，雖然時間複雜度都是

$O(n)$，實際上執行時的 data access 的次數還是相對較少，會相對地有效率。

bool q_delete_mid(struct list_head *head)
{
    struct list_head *next = NULL, *prev = NULL;
    for(next = head->next, prev = head->prev; next!=prev->prev && next != prev; prev= prev->prev, next = next->next);
    // next will be the node deleted after for loop
    list_del(next);
    element_t *pop_item = list_entry(next, element_t, list);
    free(pop_item->value);
    free(pop_item);
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    return true;
}

q_sort()

將整個佇列排序，且因為節點的資料是字串所以使用字典排序。原先是採用 quick sort，不過在某些情況下會有效率的問題所以後續改成實作 merge sort 。整個流程分成幾個部份：

• 將佇列從中間分割成兩個 list
• 分別將兩個分割出來的 list 做遞迴呼叫執行排序
• 合併(merge)兩個排序好的 list

以前曾經使用過陣列實作 merge sort，在分割 list 的部份可以在

$O(1)$ 的時間做好，但是在合併的時候需要

$O(n)$ 額外空間；這次使用 doubly-linked list 在合併上只需要

$O(1)$、但在分割的部份需要用

$O(n)$ 的時間複雜度找到中間的節點執行分割。剛好這部份 q_delete_mid 有相同的操作，可以使用相同的方法找到中點，並且可以透過巨集 list_cut_position 將中點以前的節點分割到另外一個 list 上。在合併 list 的部份則是額外獨立成一個函式 merge_2_list 並且可以用在後續的 q_merge 上面。

void q_sort(struct list_head *head)
{
    if (!head || head->next == head->prev)
        return;
    struct list_head *next = NULL, *prev = NULL;
    // divide the list into two lists
    LIST_HEAD(first);
    // meet the middle node
    for (next = head->next, prev = head->prev;
         next != prev->prev && next != prev;
         prev = prev->prev, next = next->next)
        ;

    list_cut_position(&first, head, next);
    q_sort(&first);
    q_sort(head);
    merge_2_list(head, &first);
}

和 Linux 核心原始程式碼比較

TODO

q_delete_dup()

將佇列裡面有重復字串的節點全數刪除。直觀上的想法是先走訪佇列找出哪些佇列是有重複字串的並且記錄，再走一遍把節點刪除，同時也要考慮儲存重複字串的方式讓後續查詢速度不能太慢。首先第一個想到其實是使用類似 C++ std::map 的結構去存放，但是 C 語言好像沒有內建。不過，昨天上課有提到 hash table 也是搜尋效率很快的資料結構，就找到了 C 語言也有內建 的函式 hcreate() 和 hsearch () 來建立 hash table，藉此讓查詢比較有效率。

C 語言的規範「沒有」提供上述函式，而是 POSIX 規範才有，請詳閱 hcreate(3p)。
jserv

bool q_delete_dup(struct list_head *head)
{
    element_t *current = NULL, *next = NULL;
    hcreate(HASH_TABLE_SIZE);
    ENTRY e;
    ENTRY *ep;
    list_for_each_entry_safe (current, next, head, list) {
        int str_len = strlen(current->value) + 1;
        e.key = malloc(str_len);
        memcpy(e.key, current->value, str_len);
        e.data = malloc(sizeof(int));
        *((int *) (e.data)) = 1;
        ep = hsearch(e, FIND);
        if (!ep) {
            ep = hsearch(e, ENTER);
            if (!ep)
                return false;
        } else
            *((int *) (ep->data)) = 2;
    }
    list_for_each_entry_safe (current, next, head, list) {
        e.key = current->value;
        e.data = 0;
        ep = hsearch(e, FIND);
        if (*((int *) ep->data) == 2) {
            list_del(&current->list);
            free(current->value);
            free(current);
        }
    }
    hdestroy();
    return true;
}

但是上面的程式碼還有問題，在整個函式結束之後，原本儲存在 hash table 裡面的指標沒有釋放記憶體（hdestroy() 本身只有釋放 ENTRY 本身而沒有釋放指標指向的空間)。為了解決這個問題，必須要有這些 hash table 裡面指標的資訊，所以用了新的結構 h_table_list 搭配 list_head 去存每個 hash table 的 key 和 data 並且在函示結束前將記憶體釋放。

typedef struct {
    struct list_head list;
    int *dup;
    char *key;
} h_table_list;

有了 h_talbe_list 的結構紀錄所有資料後，就可以在函式結束的時候把所有 hash table 上指標所指的空間全數釋放。

使用 Linux 核心的 hash table 改寫，見 Linux 核心的 hash table 實作。你應該一併比較記憶體操作的效率。
jserv

用 Linux 核心風格 hash table 進行修改

Linux 核心的 hash table 實作所用到的結構體為 hlist_node 和 hlist_head，宣告在 linux/types.h 的標頭檔以及相關的 API 都和本次作業使用的 list_head 在 linux/list.h，因為 user space 無法直接使用 linux kernel 相關的標頭檔，所以和這次作業的 list.h 一樣額外使用一個新的標頭檔 hlist.h 將 hash table 相關的宣告和使用到的 API 都放在裡面。

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

實作的方法為宣告一個 hlist_head 的陣列 hash_table[]，陣列的每個 entry 都是 hash table 中的一個 bucket，而鏈結串列節點的 key 則用字串中的所有字元做 XOR 的結果，如下方的 compute_key 函式所示；計算 bucket 位置的方式依據 Linux 核心的 hash table 實作，使用 golden ration 作為常數。

static unsigned compute_key(char *const value)
{
    char *current = NULL;
    char accumulate = 0;
    for (current = value; *current; current++)
        accumulate = accumulate ^ *current;
    return (unsigned) accumulate;
}

hash table 的每一筆資料也可以仿照 Linux kernel 風格的鏈結串列，將 hlist_node 本身嵌入到結構體並用 hlist_entry 或 container_of 之類的巨集，從 hlist_node 去存取結構體本身的位址：

typedef struct {
    char *value;
    struct hlist_node hlist;
    int flag;
} hash_element_t;

此外，hlist_node 的 API 之中很多和雙向鏈結串列相似，也有 hlist_for_each_entry_from 之類的巨集可以走訪同一個 bucket 裡面的所有節點，藉由比對 hash_element_t 儲存的字串進行比對，來找出重複節點。
演算法和之前的做法一樣，都是先對雙向鏈結串列走訪一圈記錄重複的節點，再走第二圈將重複的節點進行刪除，最後再將 hash_table 的空間逐個釋放即可以完成跟之前的函式相同的功能。

記憶體操作之比較

TODO

q_swap

將佇列的每個節點兩兩互換。做法是每走訪兩個節點就和前面的節點順序交換。但是實作完 q_reverseK 才發現 q_swap 是這個函式

$k=2$ 的特例，所以其實可以直接寫成q_reverseK(head, 2) 讓程式碼再簡潔一點，並且在時間複雜度上也是

$O(n)$。

q_descend

把佇列中的節點刪除使佇列裡面的順序呈現嚴格遞減的形式。因為是 doubly-linked list，可以很方便地從最後面的節點走訪，並且在走訪的過程中記錄目前走過最大的節點數值以及刪除小於最大值的節點，整個過程只需要走訪一次而使時間複雜度是

$O(n)$

q_merge

將所有已經排序的佇列進行合併。看到這邊才發現原來整個系統可以存多個佇列也才終於讀到 qtest.c 是有個 chain 變數在記錄佇列的，也才終於用到 queue.h 裡面的 queue_contex_t。
實作的想法是，讓第一個佇列逐次和後面的所有佇列進行合併，並且將合併兩個佇列的過程獨立寫成一個函式 merge_2_list，除了讓程式碼看起來比較簡潔之外，前面實作的 q_sort 也可以使用這個函式來實作 merge sort，可以讓函式整體的行數再少一點。

void merge_2_list(struct list_head *l1, struct list_head *l2)
{
    struct list_head tmp;
    INIT_LIST_HEAD((&tmp));
    list_splice(l1, &tmp);  // temporarily put l1 into tmp
    INIT_LIST_HEAD(l1);
    for (; !list_empty(&tmp) && !list_empty(l2);) {
        char *str_1 = list_entry(tmp.next, element_t, list)->value,
             *str_2 = list_entry(l2->next, element_t, list)->value;
        strcmp(str_1, str_2) < 0 ? list_move_tail(tmp.next, l1)
                                 : list_move_tail(l2->next, l1);
    }
    // splice the rest of queue
    list_empty(&tmp) ? list_splice_tail(l2, l1) : list_splice_tail(&tmp, l1);
    INIT_LIST_HEAD(&tmp);
    INIT_LIST_HEAD(l2);
}

不過 merge_2_list 是以實作 q_merge 為出發點去實作的，會把合併的結果放回 l1 當中

q_reverseK

讓佇列每 k 個節點就反轉一次，如果最後不滿 k 個節點則不反轉維持原樣。反轉的部分和 q_reverse 是一樣的，所以在實作的時候就是想辦法用到前面已經寫好了 q_reverse 並且考慮怎麼將這 k 個節點形成一個新的 sublist ，同時也要考慮迴圈走訪的形式。

走訪的迴圈寫法：

for (current = head->next, tail = traverse_k_node(head, current, k);
         tail != head && current != head;
         current = current->next, tail = traverse_k_node(head, current, k))

其中 current 是目前走到的節點(sublist的頭)、 tail 透過 traverse_k_node 函式所找到往後

$k-1$ 步的節點(如果途中遇到 head 節點則為 head 節點)。而在每個迴圈裡面則是將 current 到 tail 之中所有的節點形成新的 list 並且執行 q_reverse ，再把翻轉過的 list 接回原先的 list 上。此時 current 和 tail 的位置就會對調，所以 current 下一個要走訪的節點剛好就是 current->next、 下一個 tail 則是 current 往後走

$k-1$ 步所走到的節點。

struct list_head *traverse_k_node(struct list_head *head,
                                  struct list_head *start,
                                  int k)
{
    int i;
    struct list_head *current = NULL;
    for (i = 0, current = start; i < k - 1 && current != head;
         i++, current = current->next)
        ;
    return current == head ? head : current;
}

traverse_k_node 只有使用在 q_reverseK 之中，但是為了簡化迴圈還是把這個步驟獨立出來變成一個函式。

至此，將上方所有的函式寫完便幾乎 可以達成 make test 除了最後一個以外的所有測試資料(95/100)。

用語要精準，「幾乎」是怎樣？明明可量化，為何不說清楚？
jserv

回覆：已修改。

---

研讀 Dude, is my code constant time? 並且修改 lab0 有關 dudect 部份

一開始剛實作完 queue.c 的所有函式卻一直無法通過 make test 的最後一個測試，還很狀況外地一直在想到底有哪邊函式沒有寫好或者是哪邊還可以更好，後來觀摩了 yanjiew1 的筆記才知道那個部份和 dudect 有關，也參照了大大所提到的部份去進行修改：在論文的本身在記錄完測試時間之後會有個步驟刪除某些執行時間花比較久的紀錄，原因是執行時間的計算是拿執行前後的 cpucycle 去進行相減，但是這其中可能有作業系統中斷的情況發生，為了減少這類的狀況才要把執行時間高的部份給去掉。
(題外話：在還沒有修改這部份之前也是有幾次 make test 完全成功的，猜測會成功的原因大概是當時作業系統發生中斷的時間少才會成功）

修改的部份

其實 lab0-c 的程式碼之中大部分的函式都和 dudect.h 是幾乎一樣的，只是需要再把實作 percentile 的部份再補上去，包含了 prepare_percentile 和 相關的函式 以及需要在 update_statistic 、 doit 和 report 函式上面增加一些步驟。

static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
    for (size_t i = 0; i < N_MEASURES; i++) {
        int64_t difference = exec_times[i];
        /* CPU cycle counter overflowed or dropped measurement */
        if (difference <= 0)
            continue;

        /* do a t-test on the execution time */
        t_push(t, difference, classes[i]);

+        for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
+             crop_index++) {
+            if (difference < percentile_arr[crop_index])
+                t_push(t_crops[crop_index], difference, classes[i]);
+        }
    }
}

原本的 dudect.h 其實還有 second test ，但只有在 measurement 超過 10000 次的時候才會進行，以原本預設的次數來看不會觸發就沒有放 second test 的部份了。
另外，也需要在 doit 函式之中把 prpare_percentile 加進去，並且需要做對應的初始化(配置空間)以及釋放空間。
其實到這邊為止還沒有完全明白程式碼的內容在做什麼，只是依樣畫葫蘆，並且做了一些對應的修改例如 dudech.h 的一些參數是使用 dudect_ctx_t 這個自定義的結構去管理的而 lab0 之中的 fixture.c 則沒有，所以必須修改部份函式傳遞的參數。

完成 make test 所有測試資料

將 dudect 的部份修改完後， make test 的評分項目總算可以到 100/100 了。

---

Valgrind

在 make file 裡面有 make valgrind 可以使用 Valgrind 程式對於 qtest 進行記憶體的分析並且執行 make test 所執行的項目。起初跑完一遍發現跳出了很多訊息大多和有多餘空間沒有釋放有關，後來發現原來 qtest 之中有個 q_quit 的函式沒有正確地釋放空間導致；另外有些錯誤是對於某些函式的實作之中沒有處理輸入為 NULL 的情況而導致 Invalid read 的情況發生。

實作 shuffle 演算法和亂數分析

shuffle 演算法

要在 command line 裡面新增一個新的命令 shuffle 來對當前的佇列進行"洗牌"。跟之前把 queue.h 所有的函式實作不同，這次是要新增新的命令，所以必須從 qtest.c 新增新的函式 do_shuffle 和在 console_init 加入新的巨集 ADD_COMMAND 來處理這個命令。

Fisher–Yates shuffle

Wiki 頁面已經有介紹外加使用虛擬碼寫成的演算法，且是以陣列的形式去儲存，而使用陣列的方式去儲存對於隨機存取某個元素會比用 linked list 來的快，所以實作上第一步要先用陣列將 doubly-linked list 的每個節點位址記錄下來：

struct list_head **node_arr = malloc(size * sizeof(struct list_head *)),
    *current = NULL;
    int i = 0;
    list_for_each (current, head)
        node_arr[i++] = current;

之後便可以照著 wiki 的虛擬碼去做洗牌：

for (i = size - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        struct list_head *tmp = node_arr[i];
        node_arr[i] = node_arr[j];
        node_arr[j] = tmp;
    }

最後只要再依照陣列的順序，以 insert_tail 的方式插入到 head 節點就完成了。

亂數研究

TODO: 在檢討第一次作業的時候有提到上述隨機取值的方法會有偏差，可能還需要再做一些實驗去分析並且改用 uniform 的隨機取值

修改 web 相關命令

在原先的程式碼裡面， web 命令已經寫好了但是有一些問題：原先在 command line 套用的 linenoise 會在開啟 web 命令的時候會設成關閉，原因如同 整合 tiny-web-server中所述，所以開啟伺服器的時候先要將 linenoise 關閉，如果同時開啟會導致其中一邊輸入會卡住。

要解決 linenoise 和 socket 會阻塞的方法是採用 select() 函式，首先先宣告一個 fd_set 型態的變數作為 file descriptor 的集合並且將我們要監控的 I/O 加入(包含 std_in 和 socket)其中， select() 函式便可以監控輸入的 fd_set ，這次是要監聽有沒有輸入以及需要讀取，要將 fd_set 的變數放在參數列的第二個欄位(第三、四個分別為監控寫入和例外的欄位)；當 std_in 或 socket 有輸入時便可以接收。

程式碼的部份幾乎等同於 tiny-web-server 的第一個區塊，差別只在於有些變數上的不同，例如 listen_fd 在這次的作業裡應該對應為 web_fd 並且需要做 extern 的宣告（ web_fd 在 console.c 裡面，並且需要將原本的 static 宣告改掉），或是 process 函式應該對應到 web.h 之中的函式 web_recv ，其餘會用到的資料結構宣告也都在 web.c 裡面。將此一部分的程式碼加入至 line_edit 函式並且對於 web_fd 是否有被開啟做一些判斷（將 web_fd 初始為 -1 如果 web_fd 等於 -1 的話就維持原先程式碼的行為）， linenoise 就可以在 web 開啟時一樣能在命令提示列中運作。

但是目前還有問題：即使 linenoise 的功能依舊可以在 web 輸入之後運行，在使用 curl 命令後會得到這樣的訊息：

curl: (52) Empty reply from server

查詢了一下可能的原因是網頁伺服器沒有回傳任何東西導致，但確實可以去操作命令提示列。