2023q1 Homework1 (lab0)

contributed by < chiangkd >

留意細節！唯有重視小處並步步為營，方可挑戰原始程式碼達到三千萬行的 Linux 核心
jserv

Got it! 謝謝老師

作業要求

Request followed 2023 年 Linux 核心設計/實作課程作業 —— lab0

• 修改 queue.[ch] 以完成 make test 自動評分系統的所有項目
  • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，搭配 Massif 視覺化
• 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
• 確保 qtest 提供的 web 命令可以搭配上述佇列使用
• 新增命令 shuffle, 參考 Fisher–Yates shuffle
• 在 qtest 中執行 option entropy 1 並搭配 ih RAND 10，觀察亂數字串分佈
• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 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
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85

改進 queue.c

結構體

list_head 為 doubly-linked list 的 node 或 head

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

element_t 為 linked list 的 element

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

element_t 這個結構體，除了要用來找尋 list 整體的原因，透過嵌入 list_head 給除了
Head 可以搭配 container_or 巨集也可得知

• 參考你所不知道的 C 語言: linked list 和非連續記憶體

typedef struct {
    struct list_head head;
    int size;
} queue_chain_t;

queue_context_t 為 chain of queues

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

在多個 queue 之間的操作，如 do_queue 是透過 chain 來連接起來的，也因此在 q_merge function 中給定的參數為 list_head *head，但查看 do_merge 之後才會看到這裡傳入的是 queue_chain_t 的 chain，也是連接各個 queue 的 linked list。

if (current && exception_setup(true))
    len = q_merge(&chain.head);

做個驗證，在 q_merge 中來測試並呼叫 merge command，函式中暫時先撰寫透過傳入的 chain 找其所屬 element_t 的 value

printf("value = %s\n", list_entry(list_entry(head->next, queue_contex_t, chain)->q->next, element_t, list)->value);

cmd> new
l = []
cmd> ih Hello
l = [Hello]
cmd> it CKD
l = [Hello CKD]
cmd> merge
value = Hello

• 印出 list 的第一個 element_t 的 value

與其複製程式碼，你應揣摩背後的設計考量，特別是你的推理和驗證。

jserv

新增示意圖及個人認為設計考量(待補充)

題外話，在化 graphviz 的時候想要虛線功能，但不知道關鍵字是什麼 (加粗為 bold，直覺認為是 dot)，問了一下 chatGPT 之後它告訴我是 dotted

q_new

struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(*q_head));
    if (!q_head)    // If allocate failed
        return NULL;
    INIT_LIST_HEAD(q_head);
    return q_head;
}

改為更精簡的敘述:

struct list_head *q_head = malloc(sizeof(*q_head));

修正程式碼註解用語。

jserv

Fixed. Thanks!

q_free

void q_free(struct list_head *l) 
{
    if(!l)
        return;
    element_t *c, *n;
    list_for_each_entry_safe(c, n, l, list) {
        list_del(&c->list);
        q_release_element(c);
    }
    free(l);    // q_new function has malloced it
}

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));    // new head element
    if(!new_element)   // If allocate failed
        return false;
    size_t len = strlen(s) + 1; // plus 1 for `\0`
    new_element->value = malloc(len * sizeof(char));
    if (!new_element->value) {   // If allocate failed
        free(new_element);
        return false;
    }
    memcpy(new_element->value, s, len);
    list_add(&new_element->list, head);
    return true;
}

能否避免呼叫 memcpy 並精簡程式碼？

jserv

改為利用 strdup

發現在 harness.c 中已有定義 strdup（test_strdup），此函式回傳輸入 string s 的指標，並回傳一個具有同樣內容的指標，即複製字串。

透過此函式可以直接取代掉原實作方法中的計算長度、分配空間、記憶體複製操作

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));  // new head element
    if (!new_element)                                    // allocated failed
        return false;
-   size_t len = strlen(s) + 1;  // plus 1 for `\0`
-   new_element->value = malloc(len * sizeof(char));
+   new_element->value = strdup(s);
    if (!new_element->value) {  // allocated failed
        free(new_element);
        return false;
    }
-   memcpy(new_element->value, s, len);
    list_add(&new_element->list, head);
    return true;
}

q_insert_tail

和 q_insert_head 思路相同, 僅修改 head 和 tail 的差別

既然 q_insert_tail 和 q_insert_head 存在相似的流程，能否用 q_insert_head 來實作 q_insert_tail 呢？

jserv

新增相關敘述

bool q_insert_tail(struct list_head *head, char *s)
{
    if(!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));     // new tail element
    if(!new_element)    // If allocate failed
        return false;
    size_t len = strlen(s) + 1; // plus 1 for `\0`
    new_element->value = malloc(len * sizeof(char));
    if(!new_element->value) {   // If allocate failed
        free(new_element);
        return false;
    }
    memcpy(new_element->value, s, len);
    list_add_tail(&new_element->list, head);
    return true;
}

q_insert_head 以及 q_insert_tail 差異僅在新增節點於給定 head 的後一個位置 (next 所指方向)，以及前一個位置 (prev 所指方向)，故可以透過 q_insert_head 來實作 q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    return q_insert_head(head->prev, s);
}

翻譯成白話文的意思就是，在 head 的前面插入節點等效於在 head 的前一個節點的後面插入節點。

q_remove_head

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

• container_of 這個巨集透過給定成員 (member) 的記憶體地址、結構體的型態，以及成員的名稱, 傳回該結構體的起始地址

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

上述雖然可以成功 remove head, 但是產生錯誤訊息

ERROR: Failed to store removed value

查看 qtest.c 中 do_remove 的實作

removes[string_length + STRINGPAD] = '\0';
if (removes[0] == '\0') {
    report(1, "ERROR: Failed to store removed value");
    ok = false;
}

implementation 應翻譯為「實作」，注意「作」和「做」的落差」。
參見 資訊科技詞彙翻譯 的 "implement" 項目。

jserv

已修正，謝謝老師

• removes[0] = '\0' 會報此錯誤, 且 removes 在 qtest.c 已經 malloc 如果在 q_remove 中再次 malloc 一次的話 sp 的地址會被覆蓋掉, 即原先 removes 的地址其實並沒有存東西, 所以這裡的 sp 不該 malloc

在佇列為空時繼續使用命令 rh 會造成 segmentation fault, 當佇列為空時僅有 Head 一個點, 沒辦法通過 container_of 找到對應節點

l = []
cmd> rh
Warning: Calling remove head on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted (core dumped)

加入 list_empty 來判斷該鏈結串列是不是 empty 以及外部 removes 是否有 malloc 成功

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

這裡的 container_of 可以用 list_first_entry 巨集代替, 增加程式可讀性 (defined in list.h)

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

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

• 接下來的 q_remove_tail 也是一樣可以用 list_last_entry 取代 container_of

q_remove_tail

和 q_remove_head 思路相同, 僅修改 head 和 tail 的差別

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

q_size

走訪整個鏈結串列以計算長度

int q_size(struct list_head *head)
{
    if(!head)
        return 0;
    int cnt = 0;
    struct list_head *n = head->next;   // next list node
    while (n != head) {
        n = n->next;
        cnt++;
    }
    return cnt;
}

TODO: 善用既有的巨集，撰寫出更精簡的程式碼

jserv

用 list_for_each 取代現有 for loop

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int cnt = 0;
    struct list_head *n;
    list_for_each (n, head)
        cnt++;

    return cnt;
}

其中 list_for_ecah 定義為

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

q_delete_mid

本例為 circular doubly-linked list，你應該實作更少記憶體操作的程式碼。

jserv

原先版本使用快慢指標，快指標會走訪整個 list 一圈，慢指標會走一半的 list 找到中間點，總共會走大概 1.5 倍長度的 list，參考 freshLiver 過往作業使用到兩個指標前後從佇列頭尾迭代，透過交會點/即將交會點來判斷佇列中間點

• 參考你所不知道的 C 語言: linked list 和非連續記憶體

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head **indir;
    indir = &head;
    for(struct list_head *p = head->prev; (*indir)->next != p && (*indir) != p; ) {
        indir = &(*indir)->next;
        p = p->prev;
    }
    struct list_head *temp = (*indir)->next;
    list_del(temp);
    q_release_element(list_entry(temp, element_t, list));
    return true;
}

在這邊使用 indirect pointer 看起來沒有特別的優勢，反而在過程多了 *indir 這一個記憶體操作

對照編譯器輸出的組合語言和 perf 來確認你的觀點，否則這個「看來」流於武斷。注意編譯器最佳化的影響

jserv

初步分析以補充，待補如果設定編譯器為 -O0 後的組合語言差異

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *n = head->next;
    for(struct list_head *p = head->prev; n->next != p && n != p; ) {
        n = n->next;
        p = p->prev;
    }
    list_del(n);
    q_release_element(list_entry(n, element_t, list));
    return true;
}

且如此運算過後 n 會正好指向要移除之節點，不需要在額外設定指向要刪除的節點進行操作，

編譯器輸出的組合語言

用 objdump -d queue.o 查看編譯器輸出的組合語言

00000000000002d3 <q_delete_mid>:
 2d3:	f3 0f 1e fa          	endbr64 
 2d7:	48 85 ff             	test   %rdi,%rdi
 2da:	74 52                	je     32e <q_delete_mid+0x5b>
 2dc:	53                   	push   %rbx
 2dd:	48 8b 5f 08          	mov    0x8(%rdi),%rbx
 2e1:	48 39 df             	cmp    %rbx,%rdi
 2e4:	74 4e                	je     334 <q_delete_mid+0x61>
 2e6:	48 8b 17             	mov    (%rdi),%rdx
 2e9:	48 8b 43 08          	mov    0x8(%rbx),%rax
 2ed:	48 39 d3             	cmp    %rdx,%rbx
 2f0:	74 19                	je     30b <q_delete_mid+0x38>
 2f2:	48 39 c2             	cmp    %rax,%rdx
 2f5:	74 14                	je     30b <q_delete_mid+0x38>
 2f7:	48 8b 12             	mov    (%rdx),%rdx
 2fa:	48 89 c3             	mov    %rax,%rbx
 2fd:	48 8b 40 08          	mov    0x8(%rax),%rax
 301:	48 39 da             	cmp    %rbx,%rdx
 304:	74 05                	je     30b <q_delete_mid+0x38>
 306:	48 39 d0             	cmp    %rdx,%rax
 309:	75 ec                	jne    2f7 <q_delete_mid+0x24>
 30b:	48 8b 13             	mov    (%rbx),%rdx
 30e:	48 89 10             	mov    %rdx,(%rax)
 311:	48 89 42 08          	mov    %rax,0x8(%rdx)
 315:	48 8b 7b f8          	mov    -0x8(%rbx),%rdi
 319:	e8 00 00 00 00       	call   31e <q_delete_mid+0x4b>
 31e:	48 8d 7b f8          	lea    -0x8(%rbx),%rdi
 322:	e8 00 00 00 00       	call   327 <q_delete_mid+0x54>
 327:	b8 01 00 00 00       	mov    $0x1,%eax
 32c:	5b                   	pop    %rbx
 32d:	c3                   	ret    
 32e:	b8 00 00 00 00       	mov    $0x0,%eax
 333:	c3                   	ret    
 334:	b8 00 00 00 00       	mov    $0x0,%eax
 339:	eb f1                	jmp    32c <q_delete_mid+0x59>

結果上述的兩個版本編譯器編出來的組合語言竟然是一樣的，查看 makefile 發現編譯器優化等級設定在 -O1，如果禁用優化改成 -O0 編譯出來的組合語言才會有差

使用 perf 確認上述猜測

• 參考 Linux 效能分析工具: Perf，記得先參考安裝章節將權限打開
• 雖然上面已經看到經過編譯器優化後的組合語言相同，可想而知效能一定一樣。

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

定義一個測試案例 trace-demid.cmd

option fail 0
option malloc 0
new
ih RAND 500000
time
dm
time

輸入命令

perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-demid.cmd

perf stat 可以測量單個程序運行時間內的性能係數

• --repeat 5 重複 5 次
• -e 後面接著 PMU 的事件，可以用 perf list 查看所有事件

結果如下

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

         1530,3333      cache-misses              #   90.230 % of all cache refs      ( +-  0.34% )
         1658,7721      cache-references                                              ( +-  1.66% )
      16,8910,5300      instructions              #    0.83  insn per cycle           ( +-  0.01% )
      19,7202,0142      cycles                                                        ( +-  2.88% )

            0.5664 +- 0.0189 seconds time elapsed  ( +-  3.34% )

Iteration process

以 2095. Delete the Middle Node of a Linked List 舉例

Old version

利用快慢指標 (Floyd's tortoise and hare) 找中間點, 因為在本次作業中已經確保快慢指標 (或龜兔指標) 已經都在環中, 所以設定快指標移動速度為慢指標兩倍, 當快指標繞完一圈時慢指標指向中間點(有 Head 節點則差一個節點)

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head **indir;
    indir = &head;
    struct list_head *fast = head;
    while(!(fast->next == head || fast->next->next == head)) {
        indir = &(*indir)->next;
        fast = fast->next->next;
    }
    q_release_element(list_entry((*indir)->next, element_t, list));
    (*indir)->next = (*indir)->next->next;
    return true;
}

cmd> dm
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
Aborted (core dumped)

• 這裡如果直接把 (*indir)->next 直接 release 掉的話會造成 (*indir)->next 指向 NULL 這不是我們想要的, 這裡我先用 list_del((*indir)->next) 將 (*indir) 和 (*indir)->next->next linked 起來，在將原先的 (*indir)->next release 掉

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head **indir;
    indir = &head;
    struct list_head *fast = head;
    while (fast->next!= head && fast->next->next != head) {
        indir = &(*indir)->next;
        fast = fast->next->next;
    }
    
    struct list_head* temp = (*indir)->next;
    list_del((*indir)->next);
    q_release_element(list_entry(temp, element_t, list));

    return true;
}

Iteration Process

以 2095. Delete the Middle Node of a Linked List 實際演算一次

• remove (*indir)->next 節點

q_delete_dup

首先思考使用 list_for_each_entry_safe 實作，根據描述

list_for_each_entry_safe - Iterate over list entries and allow deletes

會走訪整個 list 的 entries (typeof(entry)) 並允許刪除當前的節點

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    element_t *c, *n;  // current and next element
    bool is_dup = false;
    list_for_each_entry_safe (c, n, head,
                              list) {  // current node (iterator) is allowed to
                                       // be removed from the list.
        if (c->list.next != head &&
            strcmp(c->value, n->value) == 0)  // duplicate string detection
        {
            list_del(&c->list);  // delete node
            q_release_element(c);
            is_dup = true;
        } else if (is_dup) {
            list_del(&c->list);
            q_release_element(c);
            is_dup = false;
        }
    }

    return true;
}

執行 list_for_each_entry_safe 可以走訪整個 list 但是需要注意在走訪完時 n 會指向 head，且 head 是無法透過 container_of 找到節點的，因為它沒有嵌入到結構體中，這時如果對 n 取 contain_of 會拿到 NULL 如果再做取值 n->value 會報錯 成為無效的記憶體操作。

invalid page fault

故在第一個 if 條件使用 c->list.next != head 來判斷是否來到最後的節點 (雖然 list_for_each_entry_safe 本身就有做)，避免在 strcmp(c->value, n->value) == 0 時 n->value 對 NULL 指標取值。

TODO: 減少記憶體操作的數量

jserv

q_swap

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n = head->next;
    while (n != head && n->next != head) {
        struct list_head *t = n;
        list_move(n, t->next);
        n = n->next;
    }
}

交換佇列中鄰近的節點，將兩個鄰近的節點中的第一個節點移動至以令一個當作 head 節點的開頭 (也就是說會放在另一個節點的 next)，移動節點可分為兩步驟(刪除以及插入)，對應到 list_move 中定義的兩步驟 list_del 以及 list_add

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n, *s, *t;
    list_for_each_safe (n, s, head) {
        t = n->next;
        n->next = n->prev;
        n->prev = t;
    }
    t = head->next;
    head->next = head->prev;
    head->prev = t;
}

一開始原本是考慮到沒有刪除節點的問題所以使用 list_for_each 來走訪 list ，但是在 reverse 的過程中的 node 會把 next 和 prev 做交換，會讓原本定義的巨集出現錯誤，導致無法順利走訪。

改用 list_for_each_safe

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

在迭代過程中 safe 指標會始終維持在 node 的下一個節點(沒有 reverse 的)，使用 node = safe 以及 safe = node->next 確保迭代過程 node 不會往回走。

q_reverseK

此函數 函式需要將 list 中的 k 個節點進行 reverse，直覺來說會利用到上方已經實作完成的 q_reverse，為此在使用時符合 q_reverse 參數需求，傳入該 list 的 head，故使用 list_cut_position 對特定長度的 list 進行分割，並在分割下來的 list 頭部新增 iter 作為該 list 的 head 供 q_reverse 使用

注意用語，參見 資訊科技詞彙翻譯。上述 "reverse" 應有對應的漢語描述

jserv

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n, *s, iter, *tmp_head = head;
    int i = 0;
    INIT_LIST_HEAD(&iter);
    list_for_each_safe (n, s, head) {
        i++;
        if (i == k) {
            list_cut_position(&iter, tmp_head, n);
            q_reverse(&iter);
            list_splice_init(&iter, tmp_head);
            i = 0;
            tmp_head = s->prev;
        }
    }
}

• 參考 25077667，及 komark06

q_sort

實作 merge sort，先將環狀結構斷開後，傳入 head->next 進去 merge_recur

merge_two_list

• 結合兩個「已排序」的鏈結串列

struct list_head *merge_two_list(struct list_head *left,
                                 struct list_head *right)
{
    struct list_head head;
    struct list_head *h = &head;
    if (!left && !right) {
        return NULL;
    }
    while (left && right) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) < 0) {
            h->next = left;
            left = left->next;
            h = h->next;
        } else {
            h->next = right;
            right = right->next;
            h = h->next;
        }
    }
    // after merge, there are still one node still not connect yet

    if (left) {
        h->next = left;
    } else if (right) {
        h->next = right;
    }
    return head.next;
}

TODO: 撰寫更精簡的程式碼，縮減分支

jserv

merge_recur

• 利用快慢指標將 list 的中間節點找出來並遞迴處理

避免使用含糊的「中點」，應有對應的定義及說明。

jserv

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

    struct list_head *slow = head;
    // split list
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next) {
        slow = slow->next;
    }

    struct list_head *mid = slow->next;  // the start node of right part
    slow->next = NULL;

    struct list_head *left = merge_recur(head);
    struct list_head *right = merge_recur(mid);

    return merge_two_list(left, right);
}

q_sort

• 傳入 head->next 進行 merge sort 可以保留原本的 head ，在排序過後在進行 prev 以及 circular 的修補

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    // disconnect the circular structure
    head->prev->next = NULL;
    head->next = merge_recur(head->next);
    // reconnect the list (prev and circular)
    struct list_head *c = head, *n = head->next;
    while (n) {
        n->prev = c;
        c = n;
        n = n->next;
    }
    c->next = head;
    head->prev = c;
}

q_descend

此函數會將右邊存在有嚴格大於的節點的節點給移除 (remove)

int q_descend(struct list_head *head)
{
    struct list_head *c = head->prev, *n = c->prev;

    while (n != head) {
        if (strcmp(list_entry(n, element_t, list)->value,
                   list_entry(c, element_t, list)->value) < 0) {
            list_del(n);
        } else {
            c = n;
        }
        n = n->prev;
    }
    return q_size(head);
}

如果順著 list 方向進行走訪 (以 next 指標迭代)，無法確定迭代的過程中會不會遇到嚴格大於的節點(如果遇到則走放過的節點都要移除)，故這邊我以反方向進行迭代(以 prev 指標迭代)，找尋下一個節點值只要和當前節點做比較，若下一個節點小於當前節點的話則移除。

執行測試案例的時候發現 trace-06 過不了，發現是 descend 後被消除的 block 沒有被清掉，一開始看到函式敘述用 remove 時以為不用刪除

Remove every node which has a node with a strictly greater value anywhere to the right side of it

但它也沒有存到像 q_remove 系列的 sp 中，由 q_test 負責刪除，故修正在函式內進行記憶體釋放

int q_descend(struct list_head *head)
{
    if (!head)
        return 0;
    struct list_head *c = head->prev;
    element_t *c_ele = list_entry(c, element_t, list);
    while (c_ele->list.prev != head) {
        element_t *n_ele = list_entry(c_ele->list.prev, element_t, list);
        if (strcmp(n_ele->value, c_ele->value) < 0) {
            list_del(&n_ele->list);
            q_release_element(n_ele);
        } else {
            c_ele = n_ele;
        }
    }
    return q_size(head);
}

q_merge

先看一下 do_merge 要我們做什麼

if (current && exception_setup(true))
    len = q_merge(&chain.head);
exception_cancel();

• 輸入 chain head 回傳長度

且在 do_merge 中會負責把被 merge 掉的 queue 空間 free 掉，接著再檢查是否真的有按照 ascending order 來排序

int q_merge(struct list_head *head)
{
    if (!head)
        return 0;
    queue_contex_t *c_cont;
    queue_contex_t *n_cont;
    struct list_head *sorted = NULL;

    list_for_each_entry_safe (c_cont, n_cont, head, chain) {  // iterate context
        c_cont->q->prev->next = NULL;
        c_cont->q->prev = NULL;
        sorted = merge_two_list(sorted, c_cont->q->next);
        INIT_LIST_HEAD(c_cont->q);  // reconnect the lists which are moved and
                                    // merged to "sorted" list;
    }
    LIST_HEAD(tmp);
    struct list_head *t = &tmp;
    t->next = sorted;
    struct list_head *c = t;
    while (sorted) {
        sorted->prev = c;
        c = sorted;
        sorted = sorted->next;
    }
    c->next = t;
    t->prev = c;
    int size = q_size(t);  // store size before splice to main queue
    list_splice(t, list_first_entry(head, queue_contex_t, chain)->q);
    return size;
}

實作過程中利用在 merge sort 已經寫好的 merge_two_list ，不過須注意的是這邊我的 merge_two_list 傳入值為兩個沒有 head 的 list，也就是每一個節點其對應到的 element 都有數值，且不是環狀 linked list ，實做過程將兩個已經 sorted 好的 list 傳入 function 並回傳將兩個 list merged 完成的 list 的第一個節點地址，此時可以把 merged 好的 list 交給主要的 context (迭代中的) 的 list head (其 element 沒有值的那個)

完成之後會有一個 merged 好的 list，接著將環狀的結構復原 (prev被各個佇列的 merge 打亂了，僅有 next 為正常順序)

最後把處理好的 list 透過 list_splice 交給主要 chain head 所屬的 element

---

研讀論文並改進 dudect

• 較細節研讀筆記放在另外的筆記

此節根據〈Dude, is my code constant time?〉修正測試案例 trace-17-complexity 檢測程式碼不會常數執行時間的問題，在 trace-17-complexity 測試案例中會將 option simulation 打開，並執行 insert head (ih)、insert tail (it)、remove head (rh)、remove tail (rt) 指令，而在 qtest.c 中相對應的 do_it、do_ih、do_remove 都有對應 simutlation 開啟狀態下的行為。

解釋 simulation 模式

下述程式碼已在 #127 更新

首先查看 do_ih

if (simulation) {
    if (argc != 1) {
        report(1, "%s does not need arguments in simulation mode", argv[0]);
        return false;
    }
    bool ok = is_insert_head_const();
    if (!ok) {
        report(1,
               "ERROR: Probably not constant time or wrong implementation");
        return false;
    }
    report(1, "Probably constant time");
    return ok;
}

在 simulation 下，對應到三種結果

• 不需要 argument
• 執行測試，且 probably not constant time
• 執行測試，且 probably constant time

是否為 constant time 由 is_insert_head_const() 函式回傳判斷，

is_##x##_const 系列函式由前置處理器 concatenation 處理，其中 insert_head, insert_tail, remove_head, remove_tail 也都是由前置處理器處理。

這技巧稱為 X macro

jserv

Got it! Thanks

constant.c 中的 measure 函式負責判斷 ih、it、rh、rt 是否有正常運作 (透過 size 有沒有隨著 insert 以及 remove 正常的變動)

fixture.c 中的 report 函式則負責測量是否為 constant time

/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;

/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

/* For the moment, maybe constant time. */
return true;

此處流程可以參照 preparaz/dudect，中的 Checking your code for constant time 節

dudect is distributed as a single-file library for easy building. Steps:

• Copy dudect.h to your include directories
• Add #include "dudect.h" from your source files.
• See this minimal example for a fully contained example. You'll need to write the following functions:
  • do_one_computation(),
  • prepare_inputs() and
  • call dudect_main() from your main function

Student's t-distribution 及程式實作原理

實作放在 ttest.c 相關函式，按照公式計算 t 值

$$t=\frac{\overline{X_0}-\overline{X_1}}{\sqrt{\frac{s_1^2}{N_1}+\frac{s_2^2}{N_2}}}$$
其中 t 值越小代表兩組分佈越接近，注意這裡的

$\overline{X_i}$ 指的是 sample mean

首先在進入定義全域變數 t_constext *t，結構體定義為

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
} t_context_t;

在每一次測試時 (預設測試 10 次 (TEST_TRIES=10))，首先呼叫 init_once()，在 init_once() 中會將 t 的各個元素初始化。

接著根據不同的 mode (不同的 case 有不同的 mode number) ，進入 doit ，在 prepare_input 之後進入 measure 函式， measure 函式根據 q_size 判斷 ih, it, rh, rt 等操作有沒有順利進行，也計算函式執行時間，以 insert_head 為例:

before_ticks[i] = cpucycles();
dut_insert_head(s, 1);
after_ticks[i] = cpucycles();

函式若正常執行回傳 true 給 ret，且更新了 before_ticks 以及 after_ticks 交給 differentiate 進行計算 exec_time[i] = after_ticks[i] - before_ticks[i] ，其中 i 為每次 test 進行的 measurement 次數，預設為 150 次。

接著將計算出的 exec_time 及 classes 送入 updata_statistics ，函式內透過 t_push 進行 t-test ，t_push 需要的參數包含

• t_context 本體 t
• 計算出的 difference 也就是對應的 exec_times[i]
• 對應的 classes[i]

在 dudect.h 原始碼中有提到可以參考《The Art of Computer Programming, Volume 2 : Seminumerical Algorithms》 (待研究)，看起來是透過取新的 execution time 與當前平均值的差為變化量 (delta) 而新的平均值就會是舊平均值加上變化量的平均值 (delta/n)，可以避免每次都將所有數值相加取平均的過程，而 m2 為變異數尚未平均的值，在後續 t_compute 會使用到，每次的 m2 更新為舊 m2 加上 delta 乘上這次的 execution time 與更新過後的平均值的差。

在 ttest.c 中

void t_push(t_context_t *ctx, double x, uint8_t class)
{
    assert(class == 0 || class == 1);
    ctx->n[class]++;

    double delta = x - ctx->mean[class];
    ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
    ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}

之後進入 report 函式透過 t_compute 及取絕對值的 fabs 計算 max_t， max_t 數值就會根據 t_threshold_xx 的值來判斷程式是否 constant time，這裡程式的實作如同上述給定的公式

$$t=\frac{\overline{X_0}-\overline{X_1}}{\sqrt{\frac{s_1^2}{N_1}+\frac{s_2^2}{N_2}}}$$
再回傳 t 值之後會在透過 fabs 取絕對值。

修改以達成 constant time

當前 lab0-c 並未實作 percentile 功能，也就是沒有將測量誤差給 crop 掉，將 dudect.h 中的 percentile 引入後即可順利通過 trace-17-complexity

dudect.h 中的結構體定義和 lab0-c 有一些不一樣，原專案中使用 dudect_state_t 將 ttest_ctx_t (等效 lab0-c 中的 t_context_t) 及執行時間、輸入資料、等必要資訊定義在一起，但在 lab0-c 都是拆開的，在這邊引入 percentile 至 t_context_t 中

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
+   int64_t *percentiles;
} t_context_t;

詳細改動在 commit 中。

---

研讀 list_sort.c 並引入專案

• 研讀筆記放在這裡

將 list_sort.c 以及 list_sort.h 引入專案，並新增 makefile 的 dependency 以及把無關的 include header 移除

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

list_sort.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H

-#include <linux/types.h>
+#include "stdint.h"
+#include "list.h"
-struct list_head;

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif

static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b)
{
	struct list_head *tail = head;
-	u8 count = 0;
+	uint8_t count = 0;

        ...
}

編譯後發現 likely 以及 unlikely 沒有定義，參考 linux/compiler.h，其中的 __builtin_expect() 是 gcc 的 built-in function，用來將 branch 的相關資訊提供給 compiler，讓其對程式碼改變分支的順序

• 參考 6.59 Other Built-in Functions Provided by GCC

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

• 參考連結 Linux Kernel 慢慢學: likely and unlikely macro

在 list_sort 的 prototype 中需要三個參數，priv, head，以及 cmp

• head 為我們要輸入的 queue 的 head
• cmp 為 compare function，作為函式指標傳入，根據註解

The comparison function @cmp must return > 0 if @a should sort after
@b (“@a > @b” if you want an ascending sort), and <= 0 if @a should sort before @b or their original order should be preserved. It is always called with the element that came first in the input in @a, and list_sort is a stable sort, so it is not necessary to distinguish the @a < @b and @a == @b cases.

1. cmp return > 0 (a 排在 b 的後面)
2. cmp return <=0 (a 排在 b 的前面或保留原本排列)
3. list_sort 是一個 stable sort，故不用區分小於 0 或等於 0

不確定這邊的 priv 是要幹麻的，不過根據宣告 priv 可以為 NULL

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)

參考 do_sort 新增 do_lsort 代表 linux 核心原始程式碼的 list_sort 並定義 cmp

int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
    element_t *a_ele = list_entry(a, element_t, list);  // get mother element
    element_t *b_ele = list_entry(b, element_t, list);
    return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1;
}
bool do_lsort(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    int cnt = 0;
    if (!current || !current->q)
        report(3, "Warning: Calling sort on null queue");
    else
        cnt = q_size(current->q);
    error_check();

    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        list_sort(NULL, current->q, cmp);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;
    if (current && current->size) {
        for (struct list_head *cur_l = current->q->next;
             cur_l != current->q && --cnt; cur_l = cur_l->next) {
            /* Ensure each element in ascending order */
            /* FIXME: add an option to specify sorting order */
            element_t *item, *next_item;
            item = list_entry(cur_l, element_t, list);
            next_item = list_entry(cur_l->next, element_t, list);
            if (strcmp(item->value, next_item->value) > 0) {
                report(1, "ERROR: Not sorted in ascending order");
                ok = false;
                break;
            }
        }
    }

    q_show(3);
    return ok && !error_check();
}

提供新命令 lsort

在 qtest.c 的 console_init() 中新增命令

ADD_COMMAND(lsort, "Sort queue in ascending order provided by linux kernel", "");

結果呈現

cmd> new
l = []
cmd> ih RAND 10
l = [xajlhbj zblfv veqfmhw kuwzmcl qzzsyenvi xfsgs bocazny saskszhgd xqjrd igiecysjj]
cmd> lsort
l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv]
cmd> shuffle
l = [bocazny kuwzmcl xfsgs igiecysjj veqfmhw saskszhgd zblfv qzzsyenvi xajlhbj xqjrd]
cmd> sort
l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv]

git commit 的時候會被擋下來

list_sort.c:14:23: style: Variable 'head' is not assigned a value. [unassignedVariable]
    struct list_head *head, **tail = &head;
                      ^

考慮到不要修正 list_sort.c 的原始碼，用 cppcheck-suppress 跨過去

// cppcheck-suppress unassignedVariable
struct list_head *head, **tail = &head;

效能比較

使用 perf 進行效能比較，參考 Linux 效能分析工具: Perf

perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd 

定義測資

option fail 0
option malloc 0
new
ih RAND 500000
time
<sort>
time

• <sort> 可以為原先 qtest.c 中撰寫的 do_sort 或是引入的 do_lsort，透過 time 命令獲取 sort 執行的時間，設定 --repeat 5 重複五次，並透過 perf 拿到 instructions 以及 cycles 的數據

自行撰寫的 q_sort

q_sort	time
1	0.487
2	0.477
3	0.488
4	0.486
5	0.529

Instructions	Cycles
20,9111,6747	36,2842,8338

list_sort

q_sort	time
1	0.411
2	0.417
3	0.423
4	0.501
5	0.460

Instructions	Cycles
21,4157,1467	34,1147,9158

雖然每次執行這個測試案例時，Instructions 和 Cycles 的數量會些微變動，但整理來看

• Linux kernel 的 list_sort 指令較多，Cycles 較少

---

在 qtest 提供新的命令 shuffle

• Fisher–Yates shuffle

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int size = q_size(head);

    // shuffle
    for (int i = 0; i < size;) {  // not iterate i , iterate size
        struct list_head *start = head->next;
        int rand_idx = rand() % size;  // random number in range 0~ (size-1)
        for (int j = 0; j < rand_idx; j++) {
            start = start->next;
        }
        list_del(start);
        list_add_tail(start, head);
        size--;
    }
    return;
}

選取一個隨機數，將該位置元素取出後放到尾端，舉例來說

隨機範圍	隨機數	原始數據	結果
		12345
1~5	4	1235	4
1~4	3	125	34
1~3	1	25	134
1~2	1	5	2134

在命令直譯器中新增命令 shuffle

在 qtest.c 中的 console_init() 新增 shuffle 指令

ADD_COMMAND(shuffle, "Shuffle queue", "");

查看其巨集定義

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

此巨集會將 cmd 命令的行為去透過巨集展開 do_##cmd 去呼叫對應 handler ，如其他命令 new 會去呼叫 do_new 函式，故在此定義 do_shuffle 函式來 handle shuffle 命令

void q_shuffle(struct list_head *head);

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

    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

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

    set_noallocate_mode(false);

    q_show(3);
    return !error_check();
}

參考其他函式 handler 的寫法，有些函式內有定義 bool ok，有些則無，觀察到 ok 都用在佇列長度有更改或者需要判斷佇列是否為空的情形，所以 reverse，swap 中不需要 ok 來處理佇列長度改變，且對應的 do_reverse 以及 do_swap 中都有相應的 if(!head) 來處理空佇列的問題，綜上所述 do_shuffle 不需要有 bool ok 定義。

[!] You are not allowed to change the header file queue.h or list.h

• 無法將 q_shuffle 宣告加在 queue.h 所以就放在 do_shuffle 的上面

cmd> new
l = []
cmd> it a
l = [a]
cmd> it b
l = [a b]
cmd> it c
l = [a b c]
cmd> it d
l = [a b c d]
cmd> it e
l = [a b c d e]
cmd> shuffle
l = [a d b c e]
cmd> shuffle
l = [c b d e a]
cmd> shuffle
l = [c e a b d]

---

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

首先嘗試用 valgrind 跑跑看 trace-01-ops.cmd 測資

valgrind ./qtest -f ./traces/trace-01-ops.cmd 

==10230== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==10230==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10230==    by 0x10CE33: do_new (qtest.c:147)
==10230==    by 0x10E099: interpret_cmda (console.c:181)
==10230==    by 0x10E64E: interpret_cmd (console.c:201)
==10230==    by 0x10EA4F: cmd_select (console.c:610)
==10230==    by 0x10F33B: run_console (console.c:705)
==10230==    by 0x10D48B: main (qtest.c:1307)
==10230== 
==10230== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==10230==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10230==    by 0x10F3AF: test_malloc (harness.c:133)
==10230==    by 0x10F7B4: q_new (queue.c:17)
==10230==    by 0x10CE6C: do_new (qtest.c:151)
==10230==    by 0x10E099: interpret_cmda (console.c:181)
==10230==    by 0x10E64E: interpret_cmd (console.c:201)
==10230==    by 0x10EA4F: cmd_select (console.c:610)
==10230==    by 0x10F33B: run_console (console.c:705)
==10230==    by 0x10D48B: main (qtest.c:1307)

依據網站及作業講解敘述，Valgrind 有 5 種 memory leak

• definitely lost: 真的 memory leak
• indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
• possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
• still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數，即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。

這裡發生的 still reachable 在 do_new 及 test_malloc 中，但是如果直接執行，qtest 且逐行輸入命令不會有這個問題。

沒什麼頭緒，參考 yanjiew1，上述問題已在 #121, #122 被修正

TODO: 搞懂別人做了什麼

透過 Massif 視覺化 "simulation" 過程中的記憶體使用量

選用 trace-17-complexity.cmd

先透過 Valgrind 產生 massif 檔案

valgrind --tool=massif ./qtest -f traces/trace-eg.cmd 

再使用 massif-visualizer 查看

massif-visualizer ./massif.out.<number>

• 這邊參考 alanjiang85 的說明改用 trace-eg.cmd 進行分析

• alanjiang85: 要注意的是，挑選適當的測試資料時要避免效能類型的測試，因為以 Valgrind 執行測試程式會比較慢，容易導致出現超過時間限制的狀況。

Reference

參考資料不是讓你發表致謝詞的地方

jserv

Got it, Thanks!

• komark06 PR#111
• ISO/IEC 9899:1999
• 3.11 Options That Control Optimization
• 學習 Shell Scripts
• 你所不知道的 C 語言：前置處理器應用篇
• ANSI escape code