2023q1 Homework1 (lab0)

contributed by < chiangkd >

Image Not Showing Possible Reasons

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

Learn More →

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

Image Not Showing Possible Reasons

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

Learn More →

jserv

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;
};

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    head [label="{<left>prev|<right>next}", style=bold];
}

element_t 為 linked list 的 element

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

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

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        node [shape=record];
        value [label="{value}"];
        head [label="{<prev>prev|<next>next}"];
        style=bold;
        label=element_t
    }    
}

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

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

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        node [shape=record];
        head [label="{<prev>prev|<next>next}"];
        value [label="{size}"];
        
        style=bold;
        label=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;

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_1 {
        node [shape=record];
        q_1 [label="q|{<prev>prev|<next>next}"];
            subgraph cluster_A {
            chain [label="<label>chain|{<prev>prev|<next>next}"];
            s [label="{size}"];
            style="dashed,bold";
            color=red;
            label=queue_chain_t
        }
        int [label="{int}"];
        style=bold;
        label=queue_context_t
    }
    subgraph cluster_2 {
    node [shape=record];
    q_2 [label="q|{<prev>prev|<next>next}"];
        subgraph cluster_B {
        chain_2 [label="<label>chain|{<prev>prev|<next>next}"];
        s_2 [label="{size}"];
        style="dashed,bold";
        color=red;
        label=queue_chain_t
    }
    int_2 [label="{int}"];
    style=bold;
    label=queue_context_t
}
    chain:next->chain_2:label
    chain_2:prev->chain:label
}

在多個 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

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

Image Not Showing Possible Reasons

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

Learn More →

jserv

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

題外話，在化 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));

修正程式碼註解用語。

Image Not Showing Possible Reasons

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

Learn More →

jserv

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 並精簡程式碼？

Image Not Showing Possible Reasons

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

Learn More →

jserv

改為利用 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 呢？

Image Not Showing Possible Reasons

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

Learn More →

jserv

新增相關敘述

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" 項目。

Image Not Showing Possible Reasons

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

Learn More →

jserv

已修正，謝謝老師

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: 善用既有的巨集，撰寫出更精簡的程式碼

Image Not Showing Possible Reasons

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

Learn More →

jserv

用 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，你應該實作更少記憶體操作的程式碼。

Image Not Showing Possible Reasons

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

Learn More →

jserv

原先版本使用快慢指標，快指標會走訪整個 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 來確認你的觀點，否則這個「看來」流於武斷。注意編譯器最佳化的影響

Image Not Showing Possible Reasons

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

Learn More →

jserv

初步分析以補充，待補如果設定編譯器為 -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 舉例

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1", rank=2]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    p [shape=plaintext;label="p"]
    p->node7[constraint="false"]
    
    n [shape=plaintext;label="n"]
    n->node1[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    p [shape=plaintext;label="p"]
    p->node6[constraint="false"]
    
    n [shape=plaintext;label="n"]
    n->node2[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    p [shape=plaintext;label="p"]
    p->node5[constraint="false"]
    
    n [shape=plaintext;label="n"]
    n->node3[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7", color="red"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    p [shape=plaintext;label="p"]
    p->node4[constraint="false"]
    
    n [shape=plaintext;label="n"]
    n->node4[constraint="false", color=red]
}

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

digraph del_mid {
    node [shape=box]
    rankdir=LR

    // backbone
    node1 -> node2 -> node3 -> node4
    head->node1

    // mark
    indir [shape=plaintext;label="indir"]
    indir->head

    fast [shape=plaintext;label="fast"]
    fast->node1
}

digraph del_mid {
    node [shape=box]
    rankdir=LR

    // backbone
    node1 -> node2 -> node3 -> node4
    head->node1

    // mark
    indir [shape=plaintext;label="indir"]
    indir->node1

    fast [shape=plaintext;label="fast"]
    fast->node3
}

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

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1", rank=2]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    indir [shape=plaintext;label="indir"]
    indir->head[constraint="false"]
    
    fast [shape=plaintext;label="fast"]
    fast->node1[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    indir [shape=plaintext;label="indir"]
    indir->node1[constraint="false"]
    
    fast [shape=plaintext;label="fast"]
    fast->node3[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    indir [shape=plaintext;label="indir"]
    indir->node2[constraint="false"]
    
    fast [shape=plaintext;label="fast"]
    fast->node5[constraint="false"]
}

digraph del_mid {
    node [shape=circle]
    rankdir=LR
    node1[label="1"]
    node2[label="3"]
    node3[label="4"]
    node4[label="7", color="red"]
    node5[label="1"]
    node6[label="2"]
    node7[label="6"]
    // backbone
    node1 -> node2 -> node3 -> node4 ->node5->node6->node7
    head->node1
    // mark
    indir [shape=plaintext;label="indir"]
    indir->node3[constraint="false", color="red"]
    
    fast [shape=plaintext;label="fast"]
    fast->node7[constraint="false"]
}

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: 減少記憶體操作的數量

Image Not Showing Possible Reasons

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

Learn More →

jserv

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" 應有對應的漢語描述

Image Not Showing Possible Reasons

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

Learn More →

jserv

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: 撰寫更精簡的程式碼，縮減分支

Image Not Showing Possible Reasons

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

Learn More →

jserv

merge_recur

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

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

Image Not Showing Possible Reasons

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

Learn More →

jserv

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

Image Not Showing Possible Reasons

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

Learn More →

jserv

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{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}} \]
其中 t 值越小代表兩組分佈越接近，注意這裡的 \(\bar{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{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{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.

cmp return > 0 (a 排在 b 的後面)
cmp return <=0 (a 排在 b 的前面或保留原本排列)
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

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

Image Not Showing Possible Reasons

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

Learn More →

jserv

Got it, Thanks!

Kenny Cheng

2023/02/28 23:23:00

```c 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); } ```

這邊應該是 n = c->prev ? (Edited)

坤諦江

2023/03/01 13:36:43

這裡我想表達的 c 以及 n 都屬於指向 list_head 結構體的指標，可以等效寫成 ``` struct list_head *c = head->prev; struct list_head *n = c->prev; ``` 以下有個參考連結 https://edoras.sdsu.edu/doc/c/pointers-1.2.2/

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2023q1 Homework1 (lab0)

作業要求

開發環境

改進 queue.c

結構體

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

編譯器輸出的組合語言

使用 perf 確認上述猜測

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_descend

q_merge

研讀論文並改進 dudect

解釋 simulation 模式

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

修改以達成 constant time

研讀 list_sort.c 並引入專案

效能比較

在 qtest 提供新的命令 shuffle

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

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

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

Reference

改進 `queue.c`