2023q1 Homework1 (lab0)

contributed by < WangHanChi >

作業要求

完成實作 queue.c 所有功能
make test 取得 100 分
研讀 lib/list_sort.c 並將其加入專案中
實作新的命令 shuffle
完成 entropy 相關命令 / 選項
研讀論文〈Dude, is my code constant time?〉並且解釋 Student’s t-distribution 及程式實作的原理
使用 Valgrind 排除 qtest 實作的記憶體錯誤
開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
實作 select system call 來完成 lab0-c 中的 web 功能

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.

$ lscpu | less
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Address sizes:                   48 bits physical, 48 bits virtual
Byte Order:                      Little Endian
CPU(s):                          12
On-line CPU(s) list:             0-11
Vendor ID:                       AuthenticAMD
Model name:                      AMD Ryzen 5 5600X 6-Core Processor
CPU family:                      25
Model:                           33
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
Stepping:                        0
Frequency boost:                 enabled
CPU max MHz:                     4650.2920
CPU min MHz:                     2200.0000
BogoMIPS:                        7385.75

開發紀錄

以鏈結串列實作佇列

開發過程

常用結構 struct

Linked list_head

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

queue element_t

typedef struct {
    char *value;
    struct list_head list;
} element_t;

queue_contex_t

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

常用巨集

`INIT_LIST_HEAD`

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

將 head 往前指標與往後指標都指向自己, 並且這個 head 不會有資料

`list_entry`

#define list_entry(node, type, member) container_of(node, type, member)

這個巨集主要是藉由 list 取得每個 member 的起始位置, 與 container_of 功能一致
會定義成 list_entry 是為了符合 list 的風格，關於 Container_of 可以參考你所不知道的 C 語言: linked list 和非連續記憶體

`list_for_each_entry_safe`

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

#undef __LIST_HAVE_TYPEOF

這個主要是 list_for_each_safe 與 list_for_each_entry 兩個巨集的功能整合

Entry 代表可以取用到 member 成員的資料
safe 代表它會紀錄下一個 node 來方便使用者刪除目前的 node

queue 功能實作

q_new

根據要求，將回傳一個空的 list_head ，可以從 list.h 找到 INIT_LIST_HEAD 這個函式，並且會把 next 與 prev 都指向 head

實作流程
1. 使用 malloc 分配一個記憶體空間，如果分配失敗就回傳 NULL
2. 使用 INIT_LIST_HEAD 對剛剛的 list_head 進行初始化
3. 回傳初使化的 list_head

完整程式碼

struct list_head *q_new()
{
    struct list_head *empty = malloc(sizeof(struct list_head));
    if (!empty)
        return NULL;
    INIT_LIST_HEAD(empty);
    return empty;
}

q_free

根據要求，需要把所有 queue 所配置的記憶體釋放掉，也因為會需要走訪整個 queue 且又需要釋放記憶體空間，會使用前面提及的巨集 list_for_each_entry_safe 來精簡程式碼

會使用到釋放 queue 節點的函式

static inline void q_release_element(element_t *e)
{
    test_free(e->value);
    test_free(e);
}

實作流程
1. 檢查 list_head 是否為空，若為空就離開函式
2. 宣告用來走訪 list 的迭代器, 當前 queue 節點以及當前 queue 節點的下一個
3. 使用 list_for_each_entry_safe 進行走訪，在每個節點都先釋放 list_head ，接著再使用 q_release_element 這個函式來釋放這個 queue中的資料與自己
4. 釋放 list_head 的 head

完整程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *iter = l;
    element_t *node, *node_safe;
    list_for_each_entry_safe (node, node_safe, iter, list) {
        list_del(&node->list);
        q_release_element(node);
    }
    free(l);
}

q_insert_head

根據引數，會得到鏈結串列的 head 以及字串 s，需要新建一個 queue 的節點，並且將字串拷貝給節點的 value。 :warning: 字串需要以 \0 作為結尾

實作流程
1. 檢查 list_head 是否為空，若為空就回傳 NULL
2. 為新增的 queue 節點配置記憶體空間，並且檢查是否配置成功
3. 配置字串 str 所需要的大小，並且檢查是否配置成功
4. 複製字串 s 給 str ，並且把結尾設置為 \0
5. 使用 list.h 中的函式 list_add 將這個新的節點插入到鏈結串列的 head ，完成後就回傳 true

原本沒有做好的部份

在進行commit 的時候被 cppcheck 檢查出有記憶體未被釋放，於是開始檢查這個函式，發現在成功配置 queue 的節點後，如果字串 str 的配置失敗的情況下，要記得釋放節點 queue 再離開函式
原本程式碼呼叫三次 strlen(s) ，經過老師的提醒後，修改成使用一個變數儲存這個字串的大小

因為 strlen(s) 的時間複雜度為
$O (n)$ 如果大量使用且字串長度變長的話，會降低效能

完整程式碼

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;
    int str_size = (strlen(s) + 1) * sizeof(char);
    node->value = malloc(str_size);
    if (!node->value) {
        free(node);
        return false;
    }
    memcpy(node->value, s, str_size - 1);
    node->value[str_size - 1] = '\0';
    list_add(&node->list, head);
    return true;
}

q_insert_tail

此部份與 q_insert_head 的實作方法大同小異，僅需要將 list_add 的插入點從原本鏈結串列的頭改成尾端即可，需要注意的地方也相同

實作流程
1. 檢查 list_head 是否為空，若為空就回傳 NULL
2. 為新增的 queue 節點配置記憶體空間，並且檢查是否配置成功
3. 配置字串 str 所需要的大小，並且檢查是否配置成功
4. 複製字串 s 給 str ，並且把結尾設置為 \0
5. 使用 list.h 中的函式 list_add 將這個新的節點插入到鏈結串列的 tail ，完成後就回傳 true

完整程式碼

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;
    int str_size = (strlen(s) + 1) * sizeof(char);
    node->value = malloc(str_size);
    if (!node->value) {
        free(node);
        return false;
    }
    memcpy(node->value, s, str_size - 1);
    node->value[str_size - 1] = '\0';
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

根據要求，此函式會將 queue 的 head 節點移除，並且根據 bufsize 把原本節點的資料存進 *sp 這個字串中。可以從Difference between “delete” and “remove”中得知 delete 與 remove 這兩個的不同

實作流程
1. 檢查 head 是否為 NULL 以及透過 list_empty 這個函式檢查鏈結串列是否為空的
2. 使用 list_entry 取得要移除的節點
3. 檢查 bufsize 是否為0，之後再進行字串的拷貝
4. 使用 list.h 中提供的 list_del 將這個節點移除並且把他的前後兩個節點相連
5. 回傳指向我們所移除節點的指標

完整程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove_node = list_entry(head->next, element_t, list);
    if (bufsize) {
        strncpy(sp, remove_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_node->list);
    return remove_node;
}

q_remove_tail

此部份與 q_remove_head 的實作方法大同小異，僅需要將 list_del 的移除點從原本鏈結串列的開頭改成尾端即可，也就是在 list_entry 的 ptr 部份把 head->next 改成 head->prev，其他需要注意的地方也相同

實作流程
1. 檢查 head 是否為 NULL 以及透過 list_empty 這個函式檢查鏈結串列是否為空的
2. 使用 list_entry 取得要移除的節點
3. 檢查 bufsize 是否為0，之後再進行字串的拷貝
4. 使用 list.h 中提供的 list_del 將這個節點移除並且把他的前後兩個節點相連
5. 回傳指向我們所移除節點的指標

TODO
在聽過老師的 Code Review 後，學到了一種更簡潔且程式碼共用行高的寫法

完整程式碼

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove_node = list_entry(head->prev, element_t, list);
    if (bufsize) {
        strncpy(sp, remove_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_node->list);
    return remove_node;
}

q_size

根據要求，可以使用 list_for_each 這個走訪的函式來進行實作

實作流程
1. 檢查 head 是否為 NULL 以及透過 list_empty 這個函式檢查鏈結串列是否為空的
2. 走訪節點並且每經過一個節點就將計數器＋１
3. 回傳計數器的值

完整程式碼

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int count = 0;
    list_for_each (head->next, head) {
        ++count;
    }
    return count;
}

q_delete_mid

Leetcode

struct ListNode* deleteMiddle(struct ListNode* head){
    if(!head || head->next == NULL)
        return NULL;
    struct ListNode *rabbit = head, *turtle = head;
    while(!(rabbit->next == NULL) && !(rabbit->next->next == NULL)){
        rabbit = rabbit->next->next;
        if(rabbit == NULL || rabbit->next == NULL)
            break;
        turtle = turtle->next;
    }
    turtle->next = turtle->next->next;
    return head;
}

根據要求，將鏈結串列中點刪除。在 2095. Delete the Middle Node of a Linked List 上我所採用的方式為d快慢指標的方式，設定一個指標 rabbit 一次移動2個 node，另一個指標 turtle 一次移動1個 node 。當 rabbit 移動到結尾的時候， turtle 的下一個 node 便是中點。於是我將這樣的思路搬到 q_delete_mid 上

實作流程
1. 檢查 head 是否為 NULL 以及透過 list_empty 這個函式檢查鏈結串列是否為空的
2. 將 rabbit 與 turtlr 的起點都設定在 head
3. 使用 do-while 迴圈
  - do : 先將 rabbit 移動兩個 node 後，檢查是否到達鏈結串列的尾端或是回到 head ，若尚未到達就將 turtle 移動一個 node
  - while : 檢查 rabbit 檢查是否到達鏈結串列的尾端或是回到 head
4. 將 turtle 的下一個 node 使用 list_entry 取得佇列的元素，再將其刪除

發現可以改進的地方

原本使用的快慢指標適用於環狀與非環狀的 Linekd list，並且他的時間複雜度為

O (\frac{n}{2})

可以近似於

O (n)

，但是他的缺點是 rabbit 指標每次移動時會需要讀取兩次 next ，而 turtle 則需要讀取一次 next ，加總來看，每次移動需要花費三個記憶體操作的時間。

但是在環狀的 Linked-list 有一種方法也可以在相同的時間複雜度完成要求並且記憶體操作為快慢指標的

\frac{2}{3}

也就是每次移動花費2個記憶體操作時間

實作步驟如下

檢查 head 是否為 NULL 以及透過 list_empty 這個函式檢查鏈結串列是否為空的
設定一個指標 front 往 next 的方向移動，另一個 back 往 prev 的方向移動
當兩者交會之際及為中點
再將其刪除即可

修改過後的程式碼也在下方的完整程式碼

圖解說明

快慢指標

初始位置

快指標(rabbit) 移動兩個節點，慢指標(turtle)移動一個節點

最終快指標(rabbit) 移動到了尾端之前，慢指標(turtle) 所指的就是中間節點

反向迭代

初始位置

前指標(front) 往前移動一個節點，後指標(back) 往後移動一個節點

當兩個指標交錯或是相遇時，便可找到中間節點

完整程式碼

修改後的（反向迭代）

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 *front = head->next, *back = head->prev;
    if (front == back)
        return false;
    while (front != back && front->next != back) {
        back = back->prev;
        if (back == front || front->next == back)
            break;
        front = front->next;
    }
    element_t *node = list_entry(front->next, element_t, list);
    list_del(&node->list);
    q_release_element(node);
    return true;
}

原先的（快慢指標）

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 *rabbit = head, *turtle = head;
    do {
        rabbit = rabbit->next->next;
        if (rabbit == head->prev || rabbit == head) {
            break;
        }
        turtle = turtle->next;
    } while (!(rabbit == head->prev) && !(rabbit == head));

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

q_delete_dup

根據要求，需要將鏈結串列中有重複字串的節點刪除，可以從 82. Remove Duplicates from Sorted List II 中對於題目的敘述得知，head 所指的鏈結串列是已經 Sorted ，因此只需要考慮重複的節點會是相鄰的即可，也就是下面的第一張圖的情況

實作流程
1. 檢查 head 是否為 NULL , 透過 list_empty 這個函式檢查鏈結串列是否為空的以及使用 list_is_singular 這個函式來檢查鏈結串列是否只有 head 與一個節點
2. 設定一個旗標變數 flag 並給予初始值 0，他的用途是檢測字串是否有出現重複
3. 使用 list_for_each_entry_safe 來走訪每個節點，使用 str 這個變數來儲存下一個節點的字串內容
4. 若是下一個節點不是鏈結串列的 head 並且目前節點與下一個節點的字串不一致且 flag 為 0 就進行正常迭代，若是 flag 為 1，就刪除目前的節點
5. 若是下一個節點的字串與當前節點的字串一致的話，就刪除目前的節點，並且把旗標變數 flag 設定為 1，接著進行迭代
6. 完成走訪後回傳 true

完整程式碼

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head))
        return true;
    element_t *node, *safe;
    bool flag = 0;
    list_for_each_entry_safe (node, safe, head, list) {
        char *str = list_entry(node->list.next, element_t, list)->value;
        if (node->list.next != head && !strcmp(str, node->value)) {
            list_del(&node->list);
            q_release_element(node);
            flag = 1;
        } else if (flag) {
            list_del(&node->list);
            q_release_element(node);
            flag = 0;
        }
    }
    return true;
}

q_swap

根據要求，需要將鏈結串列中的兩兩一對位置交換，從 24. Swap Nodes in Pairs 可以得知，我們僅能交換節點的位置來達成目的，並不可以透過更改節點的字串的指標來完成。

實作流程
1. 檢查 head 是否為 NULL，並且透過 list_is_sigular 這個函式來判斷使否需要進行 swap
2. 設定兩 list_head 的指標，分別指向 head->next (以下稱為後者) 與 head->next->next (以下稱為前者)
3. 使用 for-loop 進行迭代，需要進行以下步驟
  1. 使用 list_del 將前者與鏈結串列斷開連結
  2. 將後者的 prev 指派給前者的 prev
  3. 將後者指派給前者的 next
  4. 將前者指派給後者的 prev->next
  5. 將前者指派給後者的 prev

圖解說明

設定兩個相鄰的指標，分別為後者 back = head->next 與前者 front = back->next

斷開前者 front 的與鏈結串列的連結

將 back 的 prev 指派給 front 的 prev

將 front 的 next 指向 back

將 front 指派給 back 的 prev->next

將 front 指派給 back 的 prev

完成一次交換，將 back 與 frnot 都往前移動兩個節點

TODO
在聽過老師的 Code Review 之後，發現 q_swap 與 q_reverseK 是可以共用程式碼的，因此想要找時間比較目前的 q_swap 與直接呼叫 q_reverseK 的效能差異

完整程式碼

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/

    if (!head || list_is_singular(head))
        return;
    struct list_head *node, *next;
    for (node = head->next, next = node->next; node != head && next != head;
         node = node->next, next = node->next) {
        list_del(next);
        next->prev = node->prev;
        next->next = node;
        node->prev->next = next;
        node->prev = next;
    }
}

q_reverse

根據要求，需要將鏈結串列中的節點反向連接，並且不可以使用 q_insert_head 或是 q_remove_head 這類有 malloc 或是 free 的指令。可以從 206. Reverse Linked List 完成 Single-Linked_list 的解法，再將其延伸到環狀雙向的版本

struct ListNode *reverseList(struct ListNode *head)
{
    if (!head || !head->next)
        return head;
    struct ListNode *ret = malloc(sizeof(struct ListNode));
    ret->val = head->val;
    ret->next = NULL;
    head = head->next;
    while (head)
    {
        struct ListNode *tmp = ret;
        ret = head;
        head = head->next;
        ret->next = tmp;
    }
    return ret;
}

實作流程
1. 檢查 head 是否為 NULL，並且透過 list_empty檢查是否為空的鏈結串列
2. 使用 list_head 的指標，分別是 before , current , after
3. 使用 while-loop 進行迭代，迭代過程中需要進行以下幾個步驟會使用 Graphviz進行表示

圖解說明

設定三個指標分別是 before = head->prev, current = head, after = NULL

進入 while-loop ，直到 after 指到 head 為止
把 after 指向 current->next

把 current->next 指派到 before ， current->prev 指派到 after

把 current 指派給 before

把 after 指派給 current

接著利用 while-loop 迭代即可

完整程式碼

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *before = head->prev, *current = head, *after = NULL;
    while (after != head) {
        after = current->next;
        current->next = before;
        current->prev = after;
        before = current;
        current = after;
    }
}

q_reverseK

根據要求， reverseK 是 reverse 與 swap 的混合體。在一條鏈結串列中，每 K 個元素進行 reverse ，若是 K 的值大於剩下的節點數，就不做任何的改變。

在實作當中會使用到以下兩個在 list.h 中所定義的函式

list_cut_position

這個函式的用途是把一條鏈結串列切成兩條

傳入的引數
- head_to : 被切下的 linked_list 所要接入的點
- head_from : 被切下的 linked_list 的前一個節點
- node : 被切下的 linked_list 的點

static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

list_splice

把 linled_list 插入到另外一條中

static inline void list_splice(struct list_head *list, struct list_head *head)
{
    struct list_head *head_first = head->next;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->next = list_first;
    list_first->prev = head;

    list_last->next = head_first;
    head_first->prev = list_last;
}

list_splice_init

static inline void list_splice_init(struct list_head *list,
                                    struct list_head *head)
{
    list_splice(list, head);
    INIT_LIST_HEAD(list);
}

實作流程
1. 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列以及使用 list_is_singular 確保鏈結串列裡面有不只一個節點
2. 因為要使用 list_cut_position 這個函式，所以我們先使用 LIST_HEAD 這個巨集建立一個新的 list_head
3. 因為會將鏈結串列切開，所以要使用 list_for_each_safe 這個函式來完成迭代
4. 設定一個變數 num，當 num 等於 k 的時候，就執行剪下 K 個節點，並且 reverse ，最終再將其接回原本的點。
5. 重複步驟(4)直到鏈結串列的尾端

圖解說明

主要講解置換的過程，首先先宣告三個指標 node, safe, tmp = head

利用巨集 LIST_HEAD 建立一個新 list-head 的 head

假設 k 目前為 3 ，也就是 list_for_each_safe 進行三次迭代才會開始進行切斷…等等動作，下圖展示的是第三次迭代

首先先使用巨集切出第二條鏈結串列 list_cut_position(&new_head, tmp, node);，從 tmp 得下一個節點到 node 切下後貼去 new_head ，可以看到下面變成兩條鏈結串列了

將 new_head 進行 reverse

將 new_head 插入 tmp 之後，再初始化 new_head

最後再將 tmp 移動到 safe 的前一個，便完成了一次的迭代

完整程式碼

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/

    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node, *safe, *tmp = head;
    LIST_HEAD(new_head);

    int num = 0;
    list_for_each_safe (node, safe, head) {
        ++num;
        if (num == k) {
            list_cut_position(&new_head, tmp, node);
            q_reverse(&new_head);
            list_splice_init(&new_head, tmp);
            num = 0;
            tmp = safe->prev;
        }
    }
}

q_sort

根據要求，需要將鏈結串列進行由小到大排序。這題參考自你所不知道的 C 語言: linked list 和非連續記憶體中的Merge_Sort 以及陳日昇同學的實作。

實作流程
q_merge
1. 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列
2. 將環狀結構斷開
3. 把 head->next 作為 merge_divide 的引數以及函式回傳值
4. 當由有到大後，每個節點的 prev 都是亂掉的以及環狀結構尚未接回，因此要走訪每個節點，並且把 prev 都接上，最後再把尾端接回 head
merge_divide
1. 檢查 head 是否為 NULL，並且檢查 head->next 是否 NULL ，若是就直接回傳 head
2. 使用上面所使用過的 快慢指標 來找到中點
3. 將中點切開成兩條獨立的 list_head ，再呼叫自己進行迭代
4. 將每個節點都切開後傳入 merge_two_nodes
merge_two_nodes
1. 利用 indirect pointer 來進行每個節點的走訪
2. 逐一比較 left 與 right 的字串大小
3. 最後若是其中一方已經到盡頭，便會直接把餘剩的一方接在排序完的尾端
圖解說明
merge_divide 這個函式主要在進行下面橘色框框的動作，而 merge_two_nodes 是在進行藍色及綠色框框

完整程式碼

struct list_head *merge_two_nodes(struct list_head *left,
                                  struct list_head *right)
{
    struct list_head *new_head = NULL, **indirect = &new_head, **iter = NULL;
    for (; left && right; *iter = (*iter)->next) {
        iter = strcmp(list_entry(left, element_t, list)->value,
                      list_entry(right, element_t, list)->value) >= 0
                   ? &right
                   : &left;
        *indirect = *iter;
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((uint64_t) left | (uint64_t) right);
    return new_head;
}

struct list_head *merge_divide(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *rabbit = head, *turtle = head, *middle;

    for (; rabbit && rabbit->next;
         rabbit = rabbit->next->next, turtle = turtle->next)
        ;
    middle = turtle;
    // cut off the link
    turtle->prev->next = NULL;
    struct list_head *left = merge_divide(head);
    struct list_head *right = merge_divide(middle);

    return merge_two_nodes(left, right);
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    // cut off the link
    head->prev->next = NULL;
    head->next = merge_divide(head->next);

    struct list_head *before = head, *after = head->next;
    for (; after != NULL; after = after->next) {
        after->prev = before;
        before = after;
    }
    before->next = head;
    head->prev = before;
}

q_descend

Leetcode 解法

struct ListNode *reverseList(struct ListNode *head)
{
    if (!head || !head->next)
        return head;
    struct ListNode *ret = malloc(sizeof(struct ListNode));
    ret->val = head->val;
    ret->next = NULL;
    head = head->next;
    while (head)
    {
        struct ListNode *tmp = ret;
        ret = head;
        head = head->next;
        ret->next = tmp;
    }
    return ret;
}


struct ListNode* removeNodes(struct ListNode* head){
    head = reverseList(head);
    struct ListNode *node = head, *node_next = node->next;
    while(node_next != NULL){
        if(node_next->val >= node->val){
            node = node->next;
            node_next = node_next->next;
        } else {
            node->next = node_next->next;
            node_next = node_next->next;
        }
    }
    head = reverseList(head);
    return head;
}

這題 leetcode 解法是參考自 Youtube 影片中所講解的第二種思路(Approach 2)

由於 Leetcode 是單向的 linked_list 因此由左邊比較到右邊較為複雜，因此這題的關鍵點就在於 reverse ，只要先將原本的鏈結串列 reverse ，就可以方便地進行比較所有節點大小的動作，最後再將鏈結串列 reverse 即可達成要求

而實作 q_descend 的時候就更為方便，因為使用的是環狀雙向鏈結串列，可以不須經過反向，直接透過 prev 操作即可，以下為實作流程

實作流程
1. 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列
2. 使用 list_head 的指標 node 指向 head->prev 以及 node_prev 指向 node->prev
3. 利用 list_entry 各別取得佇列內的資料
4. 接著反向走訪所有節點，假如 ndoe 的字串比 node_prev 的字串還小的時候，就不進行移除節點，將兩個節點都分別往 prev 的方向移動一格
5. 若是ndoe 的字串比 node_prev 的字串還大，就將 node_prev 移除(delete)，然後再進行下一輪的走訪

完整程式碼

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/

    if (!head || list_empty(head))
        return 0;

    int num = 0;
    struct list_head *node = head->prev, *node_prev = node->prev;

    element_t *que = list_entry(node, element_t, list);
    element_t *que_prev = list_entry(node_prev, element_t, list);
    while (&que_prev->list != head) {
        if (strcmp(que->value, que_prev->value) < 0) {
            que_prev = list_entry(que_prev->list.prev, element_t, list);
            que = list_entry(que->list.prev, element_t, list);
            ++num;
        } else {
            list_del(&que_prev->list);
            q_release_element(que_prev);
            que_prev = list_entry(que->list.prev, element_t, list);
        }
    }
    return ++num;
}

q_merge

根據要求，傳入的 head 為 queue_contex_t 的 head ，因此也會需要將節點往 next 移動一格才開始存取每個queue 的 head。他可以視作 merge sort 的延伸版，透過已經實作好的merge_two_nodes 這個函式，可以把兩段長度不相同的鏈結串列由小至大合併，因此只需要將每個 queue 的 head 都加入後便可以把所有的點併入一條

實作流程
1. 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列
2. 取得第一條 queue 的節點個數，再走訪每個 queue_contex_t 的 q
3. 在每個走訪的過程，都先將每條鏈結串列變成非環狀的，再使用 merge_two_nodes 這個函式將兩條鏈結串列合併成一條
4. 使用 INIT_LIST_HEAD 將每個空的 head 都指向自己，避免出錯
5. 最後的作法與 q_sort 的實作一樣，需要將每個節點的prev 都接回，並且把它接回環狀的

完整程式碼

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/

    if (!head || list_empty(head))
        return 0;

    int num = 0;
    struct list_head *master = list_entry(head->next, queue_contex_t, chain)->q;
    num += q_size(master);
    master->prev->next = NULL;
    struct list_head *node = head->next->next;

    while (node != head) {
        struct list_head *slave = list_entry(node, queue_contex_t, chain)->q;
        num += q_size(slave);
        slave->prev->next = NULL;
        master->next = merge_two_nodes(master->next, slave->next);
        INIT_LIST_HEAD(slave);
        node = node->next;
    }

    struct list_head *before = master, *after = master->next;
    for (; after != NULL; after = after->next) {
        after->prev = before;
        before = after;
    }
    before->next = master;
    master->prev = before;

    return num;
}

研讀 Linux 核心原始程式碼的 `lib/list_sort.c`

先去取得 lib/list_sort.c，接著開始研讀程式碼，因為怕篇幅太長超過限制，因此，我將研讀的筆記額外放在這Lab0 lib/list_sort.c 學習筆記

將 list_sort.c 加入專案

接下來要將 list_sort 加入專案中

將 list_sort.c 加入至與 queue.c 同個層級的目錄
將 list_sort.h 這個標頭檔也加入跟原始檔一樣層級的目錄下
因為會使用到 unlikely 與 likely 這樣的巨集，因此需要將 compiler.h 中的這兩行加入 list_sort.h 中

 # define likely(x)	__builtin_expect(!!(x), 1)
 # define unlikely(x)	__builtin_expect(!!(x), 0)

在 list_sort.c 的檔案中，有使用到 u8 這樣的型別，所以也將其以巨集的方式定義在 list_sort.h 下

#include <stdint.h>
typedef uint8_t u8;

接著修改 Makefile 中 OBJS，新增一個 list_sort.o





OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
-        linenoise.o web.o
+        linenoise.o web.o list_sort.o

最後修改 qtest.c 這個檔案

加入 include "list_sort.h"
設定一個變數決定是否使用 list_sort

static int use_list_sort = 0;

編寫一個比較的函式

static int cmp(void* priv, const struct list_head *l1, const struct list_head *l2)
{
return strcmp(list_entry(l1, element_t, list)->value,
              list_entry(l2, element_t, list)->value);
}

根據該該所設定的變數決定是否使用 list_sort ，於是著手修改 do_sort 中的執行 sort的部份

if (current && exception_setup(true))
    use_list_sort ? list_sort(NULL, current->q, cmp): q_sort(current->q);
exception_cancel();

最後在將我們所將入的參數使用 add_param 加入 help 的選單中

add_param("listsort", &use_list_sort, 
          "Use the sort which is made by linux kernel developers", NULL);

可以看到下方的 option 有多了 listsort 這個選項

cmd> help
Commands:
  #           ...          | Display comment
  dedup                    | Delete all nodes that have duplicate string
  descend                  | Remove every node which has a node with a strictly greater value anywhere to the right side of it
  dm                       | Delete middle node in queue
  free                     | Delete queue
  help                     | Show summary
  ih          str [n]      | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  it          str [n]      | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  log         file         | Copy output to file
  merge                    | Merge all the queues into one sorted queue
  new                      | Create new queue
  next                     | Switch to next queue
  option      [name val]   | Display or set options. See 'Options' section for details
  prev                     | Switch to previous queue
  quit                     | Exit program
  reverse                  | Reverse queue
  reverseK    [K]          | Reverse the nodes of the queue 'K' at a time
  rh          [str]        | Remove from head of queue. Optionally compare to expected value str
  rt          [str]        | Remove from tail of queue. Optionally compare to expected value str
  show                     | Show queue contents
  shuffle                  | Shuffle all the nodes in the queue in a random method
  size        [n]          | Compute queue size n times (default: n == 1)
  sort                     | Sort queue in ascending order
  source                   | Read commands from source file
  swap                     | Swap every two adjacent nodes in queue
  time        cmd arg ...  | Time command execution
  web         [port]       | Read commands from builtin web server
Options:
  echo        1            | Do/don't echo commands
  entropy     0            | Show/Hide Shannon entropy
  error       5            | Number of errors until exit
  fail        30           | Number of times allow queue operations to return false
  length      1024         | Maximum length of displayed string
  listsort    0            | Use the sort which is made by linux kernel developers
  malloc      0            | Malloc failure probability percent
  simulation  0            | Start/Stop simulation mode
  verbose     4            | Verbosity level

貼心提醒(x) 採雷實錄(o)
在使用 clang-format -i 的時候，記得不要對 Makefile 使用

安裝 perf

由於我的電腦是這學期重灌到 ubuntu-22.04 的，所以效能測試工具 perf 需要重新下載，跟著老師的筆記一步一步即可，不過這邊要特別注意，我們一般安裝的 kernel.perf_event_paranoid 會是 4 ，可以透過

$ cat /proc/sys/kernel/perf_event_paranoid

來進行查看，但是我們如果想要把權限全部打開的話，必須使用這條指令

$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"

來將權限值設為 -1

再來可以輸入 $ perf top 來確認自己是否有拿到最高權限值

進行效能比較

在 trace 這個目錄下創建一個新的測試命令集 trace-sort.cmd ，裡面的測試如下

# Test performance of sort betweem q_sort() and list_sort()
# You can modify the option listsort and the RAND to meet your need

option listsort 0
new
it RAND 500000
time
sort
time

接著執行它

$ ./qtest -f traces/trace-sort.cmd

就可以得到

$ ./qtest -f traces/trace-sort.cmd 
# Test performance of sort betweem q_sort() and list_sort()
# You can modify the option listsort and the RAND to meet your need
l = []
l = [uivpdik xfbkwkz gmbzaf ysygwrx vkssukdk ongishsxd jhxbjqsny dmxgkd iocxyll adojbg btznx equevnb fpxfr ldurei mbolzsokz gaviuvdl ylifpbvs cawtwi mxyyk ytova aihdgcca dhhcjjyvb bxldmra iovvqwa ftogdizpo ouham nlbkp mwwxth ihpymm rxxlvju ... ]
Elapsed time = 0.167, Delta time = 0.167
l = [aaaaizu aaabrr aaabvyd aaacf aaacgxla aaacpcf aaacqqfg aaacwmp aaadqam aaaeo aaahahyow aaahi aaajzhtau aaamxvbgy aaano aaaoge aaaqpjab aaaryjsxv aaatohdfj aaatolb aaavjefox aaavtfpgc aaavuwipm aaawrad aaaxx aaaycpd aaayh aaaykau aaazhb aaaztnh ... ]
Elapsed time = 0.601, Delta time = 0.435
Freeing queue

可以看到我們使用了 qtest 中的 time 功能，來取得我們執行 sort 所花費的時間，最後的那個 Delta time 就是我們所希望得到的

接著開始比較 q_sort 與 list_sort 這兩個排序的效能差別
我們分別測試資料比數從 10 萬筆資料到 100 萬筆資料
並且重複做三次

資料數	1. q_sort()	2. q_sort()	3. q_sort()	平均
10 萬筆	0.038	0.036	0.039	0.038
20 萬筆	0.095	0.089	0.096	0.093
30 萬筆	0.198	0.192	0.218	0.203
40 萬筆	0.313	0.309	0.340	0.321
50 萬筆	0.440	0.427	0.491	0.453
60 萬筆	0.556	0.592	0.616	0.588
70 萬筆	0.697	0.702	0.762	0.720
80 萬筆	0.846	0.831	0.901	0.859
90 萬筆	0.975	0.960	0.996	0.976
100 萬筆	1.123	1.098	1.119	1.113

資料數	1. list_sort()	2. list_sort()	3. list_sort()	平均
10 萬筆	0.023	0.023	0.023	0.023
20 萬筆	0.069	0.064	0.060	0.064
30 萬筆	0.129	0.124	0.132	0.128
40 萬筆	0.213	0.220	0.216	0.216
50 萬筆	0.296	0.290	0.290	0.290
60 萬筆	0.411	0.401	0.392	0.401
70 萬筆	0.498	0.507	0.505	0.503
80 萬筆	0.645	0.611	0.600	0.619
90 萬筆	0.708	0.680	0.708	0.699
100 萬筆	0.805	0.808	0.791	0.801

可以看到他 list_sort 比起 q_sort 的效能大約都好了 30% ~ 40%
接下來使用 perf 這個工具來看更詳細的對比資料

根據老師的筆記，可以使用以下指令來取得 cache-misses, cache-references, instructions, cycles 這些項目的資訊

$ perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./qtest -f trace/trace-sort.cmd

這條指令會重複跑10次 ./qtest -f trace/trace-sort.cmd 這個命令，並且將我們所設定要取得的資訊統計出來，如下面所列

 Performance counter stats for './qtest -f traces/trace-sort.cmd' (10 runs):

        20,633,385      cache-misses              #   34.793 % of all cache refs      ( +-  0.15% )
        58,757,193      cache-references                                              ( +-  0.76% )
     2,275,963,009      instructions              #    0.93  insn per cycle           ( +-  0.02% )
     2,400,840,346      cycles                                                        ( +-  0.57% )

           0.53341 +- 0.00388 seconds time elapsed  ( +-  0.73% )

接著，我因為覺得每次都要打這麼長的命令很不人性化，因此我將它加入 Makefile 裡面

export cycle ?= 5

perf: qtest
	perf stat --repeat $(cycle) -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-sort.cmd

這樣以後只要輸入 make perf 就可使用了

接著來比較兩者的差異在 50萬 比資料下的狀況

項目	q_sort	list_sort
cache-misses	27,057,256	20,610,754
cache-references	75,094,812	59,647,674
% of all caches refs	35.770 %	34.833 %
instructions	2,292,705,155	2,276,127,334
cycles	3,545,449,526	2,488,046,136
insn per cycle	0.70	0.95

可以看到 list_sort 在 cache-misses 的數量上少了將近 35% ，這樣該就是老師在作業提示這邊所說的，linux kernel 開發者有針對 cache 來做演算法的設計，因此才可以減少這麼多的 cache-misses，並且同時也減少了 instructions ，所以 list_sort 的 IPC 會比起 q_sort 好 35%

在 `qtest` 提供新的命令 `shuffle`

根據 Fisher–Yates shuffle 演算法的概念，可以得知該演算法的實作步驟分為以下幾點

實作步驟
1. 取得一個 N 個的鏈結串列，並且運用 q_size 取的節點個數
2. 隨機產生一個介於1到剩餘節點的數字 R
3. 從最小的開始數，將第 R 個數字移動到自己這條鏈結串列的尾端
4. 重複 (2) 到 (3) 的步驟
5. 當節點個數 == 0 的時候，便是 shuffle 完成之際

觀察 lab0-c 的檔案結構可以知道如果要加入新的命令需修改 qtest.c 這個檔案，首先先實作 q_shuffle 這個功能

/* Shuffle all the nodes in the queue in a random method */
void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int num = q_size(head);
    struct list_head *node = head->next;


    while (num != 0) {
        // step 2
        int random = rand() % num;
        for (int i = 0; i < random; ++i)
            node = node->next;

        // step 3
        list_del(node);
        list_add_tail(node, head);
        node = head->next;
        --num;
    }
}

當主要的功能實作完成之後，再來需要的就是將執行他的函式實作出來，這邊主要進行的就是引數的檢查, 還有啟用 set_noallocate_mode 這個功能後，就開始執行 q_shuffle ，再來就是判斷是否執行超過時間，最後再將 set_noallocate_mode 取消啟用即可，回傳值使用 q_show(3)

接著開始研究 q_show 這個函式，假如們希望印出正確的回應 ( 例如 l = [ a b c d e ] ) ，就必須要通過像是雙向環狀或是非 NULL 這樣的條件，才可以透過第893行將正確的值輸出









































static bool q_show(int vlevel)
{
    bool ok = true;
    if (verblevel < vlevel)
        return true;

    int cnt = 0;
    if (!current || !current->q) {
        report(vlevel, "l = NULL");
        return true;
    }

    if (!is_circular()) {
        report(vlevel, "ERROR:  Queue is not doubly circular");
        return false;
    }

    report_noreturn(vlevel, "l = [");

    struct list_head *ori = current->q;
    struct list_head *cur = current->q->next;

    if (exception_setup(true)) {
        while (ok && ori != cur && cnt < current->size) {
            element_t *e = list_entry(cur, element_t, list);
            if (cnt < BIG_LIST_SIZE) {
                report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value);
                if (show_entropy) {
                    report_noreturn(
                        vlevel, "(%3.2f%%)",
                        shannon_entropy((const uint8_t *) e->value));
                }
            }
            cnt++;
            cur = cur->next;
            ok = ok && !error_check();
        }
    }
    
    ...
}

經過上述，我們可以實作出 do_shuffle 這個函式

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();
    set_noallocate_mode(false);

    return q_show(3);
}

使用 Valgrind 排除 qtest 實作的記憶體錯誤

首先研讀了老師的作業提示以 Valgrind 分析記憶體問題，可以知道 Valgrind 這個工具的強大

並且我們只要在終端機輸入

$ make valgrind

就可以執行 Makefile 內預先寫好的腳本，以下是 Makefile 中關於 valgrind 的部份

valgrind_existence:
	@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

可以看上面的 valgrind_existence 是用來檢查是否安裝了 valgrind

接著繼續看到 valgrind 的腳本，可以看到它會利用 mktemp 建立一個暫存的檔案，接著複製檔案過去，再幫該檔案加上所有使用者( +a )都可以執行( +x )的權限

這邊我認為在 chmod u+x $(patched_file) 這行指令應該要使用 root 權限，從鳥高私房菜-改變權限, chmod 這篇文章中的範例來看，要執行 chmod 操作是需要切換到 root 身份的。所以我覺得這行應該改為 sudo chmod u+x $(patched_file) 會比較恰當，或是在執行 make 腳本時要使用 sudo make valgrind 。

提交 pull request?
:notes: jserv

後來詳細觀察了檔案權限以及程式碼，發現是我搞錯了，加上 sudo 會使得編譯出的檔案變成僅限 root 權限的，在之後的刪除 make clean 會產生問題，下次會再更加謹慎的。錯誤的提交

接著執行 make valgrind ，可以發現執行的速度下降了許多，符合老師所提及的
最後發現並沒有洩漏的記憶體

接著使用 Massif 視覺化工具

可以在 valgrind 使用的參數列表中加入 --tool=massif

$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd

就可以得到一張 massif.out.XXXXX，其中的 XXXXX 會是一串數字
接著要去massif-visualizer 安裝 massif-visualizer桌面版

接著輸入

$ massif-visualizer massif.out.XXXXX

就可以得到 massif 記憶體分析的圖了!

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

根據 Makefile 中關於 Sanitizer 的部份，可以看到

# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
    # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
    CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
    LDFLAGS += -fsanitize=address
endif

若是執行 make 的時候一起加上了 SANITIZER=1 這樣的參數就可以開啟 Sanitizer，來檢查程式碼

:warning: Sanitizer 與 Valgrind 是不可以同時使用的，所以假如在 make 的時候有加上了SANITIZER=1 這樣的參數的話，就要記得先執行 make clean 清除先前所編譯好的才能正常使用 Valgrind

SANITIZER 使用步驟如下:

$ make SANITIZER=1
$ make test
// 若是沒有報錯就可以清除
$ make clean

研讀論文〈Dude, is my code constant time?〉

論文筆記

論文連結

原本針對程式碼的偵測工具，是針對不同的硬體所設計的，因此換了一個平台，例如不同的 CPU 或是 micro-code 更新，原本的工具就沒有辦法使用了，為此，這篇文章提出了基於統計機率的方法來檢測程式碼。

論文使用的方法是 TIMING LEAKAGE DETECTION，首先測量兩個不同輸入數據類型的執行時間，然後檢查這兩個時間分布是否在統計上不同

Measure execution time
反覆測量我們所使用的函數 (在 lab0-c 中就是 it, ih, rh 及 rt) 對屬於兩個不同輸入資料類型的輸入的執行時間。
- Classes definition
  這邊主要在定義所使用的類別為兩種不同類型的，第一種為固定的資料類別，另外一種為隨機的資料類別
- Cycle counters
  使用 CPU 自帶的週期計數器，在 X86-64 平台下可以使用 RDTSC ，而在 aarch64 平台下可以使用 mrs 個暫存器搭配內嵌組合語言的方式來呈現，詳情可以看這裡
- Environmental conditions
  為了最小化環境變化對結果的影響，每次測量都對應於一個隨機選擇的類別，特別注意：類別分配和輸入準備任務在測量階段之前完成
Apply post-processing
- Cropping
  典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量不準確、被作業系統或其他外部活動中斷造成的。在這種情況下，可以透過裁剪測量的數據來避免誤差
- Higher-order preprocessing
Apply statistical test
- t-test
  使用 Welch’s t-test 這個方法進行檢測，這個測試方法也是 dudect 所使用的
- Non-parametric tests
  虛無假說可以參考這裡

提出的改進方法

研讀 lab0-c/dudect 筆記

oreparaz/dudect

可以知道從原始的實作來看，PERCENTILE 可以去除掉極端值，但是在 leb0-c 並沒有相關的實作，因此這會是其中一個改變的方向。再來是上面所提到的 Classes definition ，在 lab0-c 的實作中，固定資料的字串是用 0 來進行填充的，但是 0 在 ascii 碼中代表的是 '\0' ，這與字串的結尾符號一致，所以這可能會導致問題。再來是在 measure 這個函式中，使用了兩個 int 來保存插入或是移除前後的個數是否為正確的，但是這樣的檢查僅只有確認個數，但卻沒有明確知道它是否為插入在頭尾…等等，因此這也是一個問題

故目前發現的問題為

PERCENTILE
隨機 / 固定生成字串的結尾符號
q_size() 的使用不恰當

根據上述所提的問題，實施相對應的實作

PERCENTILE

首先因為老師原本的參數是散裝的，但在原本的 dudect 中是使用 struct 來包住許多的參數

int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));

所以我把上面替換成下面，這邊的 struct 也與原本的有所不同，原本的 ticks 是儲存在同一個陣列的，但我改成像是原本的定義，分成 before_ticks 與 after_ticks 。

typedef struct {
    int64_t *before_ticks;
    int64_t *after_ticks;
    int64_t *exec_times;
    uint8_t *input_data;
    uint8_t *classes;
    dudect_config_t *config;
    ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
    int64_t *percentiles;
} dudect_ctx_t;

同時也新增了關於 percenteils 相關的巨集以及函式

特別注意，因為我把上述這些參數都改成 struct 了，所以相關函式的引數都要進行更改。

隨機 / 固定生成字串的結尾符號

可以看到原本的老師對於 fix string 的部份是以 0 來進行 memset 的填充，但是在 ascii 碼中， 0 代表的是 '\0'，也就是字串的結尾符號，我認為在這邊不應該使用結尾符號來進行填充，所以我將 'a' 填充進去，並且在字串的結尾使用 '\0' 。同理，在隨機生成的的話，就會需要避免隨機產生的數字為 0 ，所以我將隨機生成的數字加上了 65，以避免這問題。

void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
    randombytes(input_data, N_MEASURES * CHUNK_SIZE);
    for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0) {
            memset(input_data, 'a', CHUNK_SIZE - 1);
            input_data[CHUNK_SIZE - 1] = '\0';
        } else {
            uint8_t rand;
            for (size_t i = 0; i < CHUNK_SIZE - 1; i++) {
                randombytes(&rand, 1);
                input_data[i] = (rand % 50) + 65;
            }
            input_data[CHUNK_SIZE - 1] = '\0';
        }
    }
}

q_size() 的使用不恰當

在 measure 這個函式中，以 insert_tail 這個函式為例

...
case DUT(insert_tail):
    for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
        char *s = get_random_string();
        dut_new();
        dut_insert_head(
            get_random_string(),
            *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
        int before_size = q_size(l);
        before_ticks[i] = cpucycles();
        dut_insert_tail(s, 1);
        after_ticks[i] = cpucycles();
        int after_size = q_size(l);
        dut_free();
        if (before_size != after_size - 1)
            return false;
    }
    break;
...

可以看到它取得了插入前後的 q_size()，並且相減來比對是否有插入，但是這樣的檢查僅能檢查出是否有插入成功，並不能知道它是否插在尾巴，所以這個檢查的操作我就先將其移除，畢竟在 make test 的前面也有檢查過 insert head 等等的功能了。

在經過這樣的修改過後， make test 就可以得到 100 分了

TODO
把 lab0-c/dudect 下的檔案整理的好看一些

2023q1 Homework1 (lab0)

作業要求

開發環境

開發紀錄

以鏈結串列實作佇列

開發過程

常用結構 struct

Linked list_head

queue element_t

queue_contex_t

常用巨集

INIT_LIST_HEAD

list_entry

list_for_each_entry_safe

queue 功能實作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_descend

q_merge

研讀 Linux 核心原始程式碼的 lib/list_sort.c

將 list_sort.c 加入專案

安裝 perf

進行效能比較

在 qtest 提供新的命令 shuffle

使用 Valgrind 排除 qtest 實作的記憶體錯誤

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

研讀論文〈Dude, is my code constant time?〉

論文筆記

提出的改進方法

根據上述所提的問題，實施相對應的實作

實作 select system call 來完成 lab0-c 中的 web 功能

參考資料

Read more

cm4hbm

2023q1 Homework3 (fibdrv)

rbtmalloc 開發紀錄

2023q1 Homework6 (quiz5)

`INIT_LIST_HEAD`

`list_entry`

`list_for_each_entry_safe`

研讀 Linux 核心原始程式碼的 `lib/list_sort.c`

在 `qtest` 提供新的命令 `shuffle`

實作 `select` system call 來完成 lab0-c 中的 web 功能