2024q1 Homework1 (lab0)

contributed by < rain20010126 >

詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

了解，感謝老師指正！

Reviewed by `Shawn531`

實作前先釐清每個函式的用處與形式，譬如在queue.h有說明每個函式要達成甚麼目的，這樣可以加速開發。
可以多表達自己的第一手想法。
善用diff表達程式碼的差異。

Reviewed by `ShawnXuanc`

在提交 commit 時可以增加對功能的說明

可以將相同的程式碼再利用，像是 q_insert, q_remove 中有需多重複的程式碼

可以使用美式英文當作程式碼的註解

開發環境

    $ gcc --version 
    gcc (Ubuntu 13.2.0-4ubuntu3) 13.2.0
    $ lscpu
    Architecture:           aarch64
        CPU op-mode(s):       64-bit
        Byte Order:           Little Endian
    CPU(s):                 8
        On-line CPU(s) list:  0-7
    Vendor ID:              Apple
      Model name:           Blizzard-M2
        Model:              0
        Thread(s) per core: 1
        Core(s) per socket: 4
        Socket(s):          1
        Stepping:           0x1
        Frequency boost:    enabled
        CPU(s) scaling MHz: 38%
        CPU max MHz:        2424.0000
        CPU min MHz:        600.0000
        BogoMIPS:           48.00

注意標示的方法。

GCC 編譯器

$ gcc -o stack -g -no-pie stack.c

-o : 指定特定輸出的檔案名稱

-g : 可以配合 gdb 做除錯如$ gdb -q stack，其中-q 的目的為讓他安靜一點

-no-pie: 抑制 PIE，簡單來說就是將原本執行檔是把一段位置寫進去(直接的地址)，使用 PIE 的話就是改成相對位置，來避免針對內存位置的攻擊，所以使用 PIE 後需要對執行檔做追蹤的話會比較麻煩

我在調整風格時遇到以下問題，有嘗試做 sudo apt upgrade gdb 仍然無法解決此問題

(gdb) set disassembly-flavor intel
No symbol "disassembly" in current context.

另外的問題是我在使用 disas main 的輸出的結果如下，不知道要怎麼和老師在你所不知道的 C 語言：函式呼叫篇中的 rbp 和 rsp 做對應

(gdb) disas main
Dump of assembler code for function main:
   0x0000000000400638 <+0>:	stp	x29, x30, [sp, #-32]!
   0x000000000040063c <+4>:	mov	x29, sp
   0x0000000000400640 <+8>:	mov	w0, #0x1                   	// #1
   0x0000000000400644 <+12>:	bl	0x40061c <funcA>
   0x0000000000400648 <+16>:	str	w0, [sp, #28]
   0x000000000040064c <+20>:	mov	w0, #0x0                   	// #0
   0x0000000000400650 <+24>:	ldp	x29, x30, [sp], #32
   0x0000000000400654 <+28>:	ret
End of assembler dump.

你所不知道的 C 語言 : 函示呼叫篇

malloc & calloc 比較:

malloc 盡可能用已經用過並且釋放掉的記憶體空間； calloc 則是配置記憶體空間並將內容歸零（通常會使用沒有被使用過的記憶體空間或是 calloc 過後但沒有做進一步修改的記憶體空間），如果要配置歸零後的記憶體空間使用 malloc ，相比於使用 malloc + memset 的速度來的快，如果沒有歸零的需求，先使用 malloc ，因為 malloc 的記憶體配置成功率較高

Parameter & Argument :

Parameter 為形式， Argument 為實際值

stack :

概念為後入先出，使用區域變數會配置在 stack 中。
stack frame 為一層的區域

rsp(stack pointer) : 指向 stack 頂端
rbp(base pointer) : 指向 stack 底部

heap(heap allocator) :

概念為分堆，會分成不同大小，例如由小到大為 first bit small bit big bit 等等，會有不同的配置策略。

使用 malloc, free 等配置記憶體或是釋放記憶體都有關係，以下為 heap 和 stack 的範例

long *arr = malloc((n + 1) * sizeof(*arr));  // heap
long arr[n+1]; // stack

你所不知道的 C 語言：遞迴呼叫篇

遞迴 VS 迭代

遞迴使用 function，在 function 中呼叫相同的一個 function (直接遞迴)，或是 function A 會呼叫 function B ，而 function B 會呼叫 function A (間接遞迴)

遞迴與非遞迴比較

遞迴優點 : 較精簡且易理解、變數較少、函式記憶體空間較省
非遞迴優點 : 通常效率較高、不須額外 stack 空間

&& (Logical AND) operator 與 || (Logical OR) operator

針對佇列操作的程式碼實作

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

在安裝完 Ubuntu Linux，熟悉鏈結串列和 git 的操作後我開始嘗試寫作業，順序即是每個函式的順序，因為一開始不知道怎麼下手，就先參考其他同學的格式並思考如何下手，首先看到 Jackiempty q_new 的部份後，發現我也不知道有 INIT_LIST_HEAD(list_head) 的函式存在，以及同學其他呼叫的函式都不太熟悉，在了解我到不是很熟悉下列網站後 (https://github.com/torvalds/linux/blob/master/include/linux/list.h#L35) ，所以我寫作業的方法主要是先參考同學的寫法，了解大概有什麼函式是需要用的，理解完需要用到的函式後，再自己下手。

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
改進你的漢語描述。

`q_new`

在了解到是要建立一個空佇列後，考慮到可能會有記憶體空間配置失敗的問題，因此簡單加上條件判斷是否有成功配置記憶體空間並搭配 INIT_LIST_HEAD 即順利完成此函式的建立。

`q_free`

你不該花太多時間在「查找資料」，閱讀、思考，然後闡述自己的洞見，才是課程在意的議題。

好的，謝謝老師。

在理解 list_for_each_entry_safe 時遇到了不小的困難，後來在~~查找資料~~ 時，發現我的理解大有問題，首先 #define 的意思是一個巨集指令，和一般定義一個函式的方式有些不同，我原先以為他的意思和定義函數是一樣的意思，再來參照 aa860630 及 nelson0720j，將巨集的輸入設定成 entry 和 safe 後，了解到此巨集主要的作用是在刪除當前節點時，能同時知道下一個節點的位置，有這樣的理解後，完成了 q_free 的建立。

`q_insert_head`

本該如此，有何好說？
自己嘗試！

~~這次我是自己從頭嘗試看看~~，但配置新的節點後，我遇到了一個問題是該怎麼知道配置 node->value 的記憶體空間，於是我詢問 chatgpt 來嘗試自己解決問題，結果他給我一段範例程式碼，所以在我閱讀後，了解到可以使用 strlen 來知道字串的長度，同時加 1 是為了~~存儲字符串結束符~~ （\0），以及需要考慮到記憶體配置失敗的問題，下一個問題是我要怎麼把輸入的字串複製過去，之後在閱讀 nelson0720j 的說明後了解到可以使用 strncpy ，於是以下是我的初步程式碼。

注意詞彙：

string 是字串
character 是字元
store 是儲存

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;

    // 獲得字串字數並使用strncpy將字串複製過去配置好的記憶體空間
    node -> value = malloc(strlen(s) + 1);
    strncpy(node->value, s, strlen(s) + 1);

    if (!node -> value)
        return false;

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

接著我使用 make test 進行測試後發現函式有誤，同時有內存洩漏的問題，於是我參考了 csotaku0926 的作法，檢查我出錯的地方，發現我少考慮到了單個字體的大小，以及在 return false 前應該要把配置失敗的記憶體釋放掉，接著就成功了~~~

`q_insert_tail`

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

有了 q_insert_head 的經驗，於是我就將 q_insert_head 的最後一行程式碼從 list_add(&node->list, head); 修改成 list_add_tail(&node->list, head); 。

另外有看到 csotaku0926 的作法，覺得他的作法聰明許多，他是直接利用先前寫的 q_insert_head 來完成函式，即將函式輸入部份從原先的 *head 改成 head->prev 就完成了，這種作法就可以省去重複的程式碼。

`q_remove_head`

在一開始，我初步對這個函式的理解是'移除' head 中和 *sp 指標指向相同的元素開始後的 bufsize 個元素，因為不確定我的想法是否正確，所以我查看了 csotaku0926 的程式碼，發現我的想法大錯特錯，了解到 bufsize 是用來存取 head->value 的大小的，同時 sp 是用來儲存 head->value 的原先值的，並搭配 list_del_init 斷開head的連結，因此在有這些了解後完成了程式碼。
我比較疑惑的部份是為什麼 remove 需要刪除節點內的 value
另外一開始在撰寫程式時沒注意到 queue empty 的情況

`q_remove_tail`

因為有先前 q_insert_head 和 q_insert_tail 的經驗，所以也嘗試看能不能用 q_remove_head 的方式撰寫本函式，但是失敗了，於是我參考了 csotaku0926 的程式碼，發現是要使用 head->prev->prev

但依然遇到了以下問題

ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar

不理解就說不理解，不要裝可憐。理工人員說要精準。

已解決，將 list_del_init 修改成 list_del ，但是~~有點不太了解其中原因~~，有查看你所不知道的 C 語言: linked list 和非連續記憶體的說明，但不懂兩者的差別為何會造成一個編譯成功一個編譯失敗的問題

static inline void list_del(struct list_head *entry)
      {
          __list_del_entry(entry);
          entry->next = LIST_POISON1;
          entry->prev = LIST_POISON2;
      }

static inline void list_del_init(struct list_head *entry)
      {
          __list_del_entry(entry);
          INIT_LIST_HEAD(entry);
      }

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫
注意程式碼的標示和張貼方式，避免非必要的縮排

`q_size`

參考自牛刀小試，透過 list_for_each 走訪每個節點，同時經過一個節點時 len 加一

`q_delete_mid`

在閱讀完你所不知道的 C 語言: linked list 和非連續記憶體後，我有一個初步的了解是可以使用快慢指標來找到中間的節點，以下是我第一次完成的程式碼

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

    while (fast!=tail && fast->next!=tail) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    
    slow = slow-> next; // 這裡有誤
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

但是遇到了以下問題

ERROR: Attempted to free unallocated block.  Address = 0xdeadbeef Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

後來在參考 nosba0957 ，發現迴圈結束後不需要再做一次 slow = slow-> next; ，但修改後仍然出現同的問題，最後在解決前面 q_remove_tail 的問題後就沒有出現上述問題了

另外在 git commit 時收到了將 tail 設定成常數的建議

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

q_delete_dup

了解函式的目標是在已經排序的狀況，移走佇列中具備重複內容的節點，我初步的想法是重複的元素會相鄰，我就從頭一個一個檢查看節點的內容，ㄖ，並了解可以使用 strcmp ，若是兩者字串相等的話會回傳0，並不使用 node = node->next 以便再重新檢查和下一個元素是否也出現重複得情況，若兩字串不相等，則使用 node = node->next ，對下一個節點進行檢查，以下是我初步的程式碼

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

    element_t *current, *next;
    struct list_head *node = head->next, *delete;

    while(node!=head){
        current = container_of(node, element_t, list);
        next = container_of(node->next, element_t, list);

        if (!strcmp(current->value, next->value)){
            delete = node->next;
            list_del(delete);
            q_release_element(container_of(delete, element_t, list));
        }
        else
            node = node->next;
    }

    return true;
}

接著我在使用 git commit 後收到了針對 current 變數的警告，要在使用這個變數的區域內聲明它，以減少其作用範圍，增加程式碼的可讀性和維護性。

另外在 q_test 出現了以下問題

Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted

接著我查看了 csotaku0926 後發現我沒有正確理解題目的意思，重複的每個節點都需要刪除，所以我新增了以下程式碼如下，同時使用 remove_cur判斷是否有刪除節點，但是在 q_test 依然出現了相同的問題。

element_t *del = NULL;
if (remove_cur){
    del = node->prev; 
    list_del_init(del); //這邊有誤
    q_release_element(del);
}

因為找不到問題所在，同時我發現我先前的程式碼沒有考慮到有重複多次的情形，所以我將迴圈改成 while 的寫法，以下是我的最終版本，我參考了 csotaku0926 的作法，改進了我先前沒有繼續檢查的問題。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;

    struct list_head *current = head->next, *next = current->next;
    bool remove_cur;

    while (current != head && current->next != head) {
        next = current->next;
        remove_cur = false;
        element_t *entry;
        
        // 此處條件有誤
        while (!strcmp(list_entry(next, element_t, list)->value,
                list_entry(current, element_t, list)->value)){
            remove_cur = true;
            list_del(next);
            entry = container_of(next, element_t, list); 
            q_release_element(entry);
            next = current->next;
        }

        current = current->next;
        if (remove_cur){
            struct list_head *del = current->prev;
            list_del(del);
            entry = container_of(del, element_t, list);
            q_release_element(entry); 
        }
    }
    return true;
}

再來我在執行 qtest 再有多目標需要刪除時會出現以下問題，經過了解後，我發現需要在以上 while 迴圈有誤處考慮 next 為 null 的情況，因次在條件部份補上 && next 即完成程式碼

l = [jiji kiki lili mimi mimi bibi bibi]
cmd> dedup
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted

避免非必要的項目縮排 (即 * )，以清晰、明確，且流暢的漢語書寫。

`q_swap`

一開始我沒有很理解題目的意思，但在查看完 nosba0957 的文字說明後，就了解題目是兩兩節點進行交換，交換完後再到下兩個節點進行交換，並參考該同學的程式碼，使用 list_move 對節點進行移除再插入。

`q_reverse`

我的初步想法是把 head->next 也就是 first 插入到 tail 後，再重新設定 first，以下是我初步的程式碼。

void q_reverse(struct list_head *head) {
    struct list_head *first = head->next;
    struct list_head *tail = head->prev;
    while(first!=head){
        list_move(first, tail);
        first = head->next;
    }

}

但出現以下錯誤

l = [yiyi iyiy gigi igig]
cmd> reverse
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

後來發現我條件部份沒設定好，會出現無窮迴圈的情況，將條件重新設定成 while(tail->prev!=head) 即完成函式的建立。

`q_reverseK`

我的想法是把tail設定到需要反轉部份的尾端，然後再用先前 q_reverse 的方法完成，以下為我的程式碼。

void q_reverseK(struct list_head *head, int k)
{
    struct list_head *first = head->next, *tail = head;

    for (int i = 0; i < k; i++) {
        tail = tail->next; // 找到需要反轉區間的尾端
    }
    while (tail->prev != head) {
        list_move(first, tail);
        first = head->next;
    }
}

後來同學在查看我的程式碼後指出我理解錯題目的要求了，題目要求是將 k 個為一組的元素進行反轉，所以我使用了 size 來判別剩下的元素還有沒有 k 個，沒有的話即跳出迴圈，接著利用前面 reverse 的方法，不斷更新 head 和 tail ，並利用 this_term_head 來存取此次循環的 head 作為 while 迴圈判斷使用。

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    int size = q_size(head);
    struct list_head *tail = head;
    struct list_head *this_term_head = head;
    struct list_head *next_term_head = head;

    while (size >= k) {
        size = size - k;

        for (int i = 0; i < k&& tail->next; i++) {
            tail = tail->next;
        }
        struct list_head *first = this_term_head->next;
        next_term_head = first;
        while (tail->prev != this_term_head) {
            list_move(first, tail);
            first = this_term_head->next;
        }
        tail = next_term_head;
        this_term_head = next_term_head;
    }
}

`q_sort`

在觀看 Linked List Sort ，並了解不同作法的原理後，我選擇以時間複雜度較低的方法： Merge Sort ，也就是先找到佇列的中點，慢慢拆分到每個佇列只包含一個元素，再兩兩合併成完整的一個佇列，於是我開始實做。

在實做過程中，首先我遇到的困難是我該如何儲存每個斷開節點的位置，於是我查看了 WangHanChi 的程式碼和說明

但實做的第一次結果遇到了以下問題，所以我慢慢針對不同的函式下去做修正

l = [yiyi hihi jiji kiki ioio]
cmd> sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted (core dumped)

以下為我 merge_two_nodes的程式碼

struct list_head *merge_two_nodes(struct list_head *L, struct list_head *R)
{
    if (!L && !R) {
        return NULL;
    }
    
    struct list_head *head = NULL;

    while(L && R){
        if (strcmp(list_entry(L, element_t, list)->value,
                   list_entry(R, element_t, list)->value) <= 0){
            head = L;
            head = head->next;
            L = L->next;
        }  

        else{
            head = R;
            head = head->next;
            R = R->next;
        }
    }
    
    if (L){
        head->next = L;
    } 
    if{
        head->next = R;
    }
    return head;
}

什麼是「虛擬」的節點？

後來發現我回傳的數值有問題，需要再額外存取 head 的位置再做回傳，後來我了解到可以使用~~虛擬節點~~ ??? （改正：可以使用額外的一個 h 來初始化 head，這樣可以讓 head 在迴圈外部始終指向正確的位置，也不用特別處理第一個元素）方式更好的解決此問題，也就是以下

struct list_head *merge_two_nodes(struct list_head *L, struct list_head *R)
{
    if (!L && !R) {
        return NULL;
    }
    
    struct list_head h;
    struct list_head *head = &h;

    while (L && R) {
        if (strcmp(list_entry(L, element_t, list)->value,
                   list_entry(R, element_t, list)->value) <= 0) {
            head->next = L;
            L = L->next;
        } 
        else {
            head->next = R;
            R = R->next;
        }
        head = head->next;
    }

    // Link the remaining elements to the head
    if (L) {
        head->next = L;
    }
    if (R) {
        head->next = R;
    }

    return h.next;
}

程式碼的註解都該用美式英語書寫，不要出現漢字。

你如何確保測試的過程已涵蓋排序演算法的最差狀況？

`q_descend`

了解到題目是要移除當該節點右側有大於該節點的節點，則刪除該節點，初步想法就是按照順序一個一個檢查，但想一想覺得這個方法會重複確認很多次，於是我就參考了 csotaku0926 的說明，了解到可以從尾端往前檢查，看有沒有比自己小的節點做刪除。

清楚標註你參照的 GitHub 帳號名稱

另外看到函式需要回傳一個數值，查看同學 csotaku0926的程式碼了解是要回傳佇列的節點數量，於是完成我以下的程式碼

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    struct list_head *ptr = head->prev;
    while (ptr != head && ptr->prev != head) {
        int compare = strcmp(list_entry(ptr, element_t, list)->value,
                         list_entry(ptr->prev, element_t, list)->value);
        if (compare >= 0) {
            element_t *entry = container_of(ptr->prev, element_t, list);
            list_del(ptr->prev);
            q_release_element(entry);
        }

        else
            ptr = ptr->prev;
    }
    return q_size(head);
}

`q_merge`

我採用了比較直觀的做法，同樣先把環形串列修改成非環形的，並將第一個串列使用 merge_two_nodes 不斷與後續的進行連接，最後與 q_sort 使用相同的作法將串列修改回雙向環狀的

Valgrind + 自動測試程式

目前使用 make valgrind 在程式碼中沒有找出記憶體的相關問題，但使用 make test 時無法通過第17項的測試

實作 shuffle

Fisher–Yates shuffle

此方法是透過一個迴圈去迭代，從最後一個元素開始，與前面的隨機一個元素進行交換，此作法的好處是，可以確保交換過得位置不會再被交換，且時間複雜度為 O(n) ，機率分佈也是均勻的

新增的方法參考 willwillhi ，目前 qtest 中的 do_shuffle 沒有檢查可能的錯誤

在實作 q_shuffle 時，遇到了以下問題

l = [1 2 3 4]
cmd> shuffle
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

在檢查完程式碼後，發現第 16 行部份有誤，在與前面交換後，原本 temp 所在的位置變為 pick 所在，因此往前更新應該修改為 temp = pick->prev



















void q_shuffle(struct list_head *head){
    if (!head) 
        return;
    
    int size = q_size(head);
    struct list_head *temp = head->prev;

    while(size>=1){
        int index = rand() % size;
        struct list_head *pick = temp;
        for(;index>0;index--){
            pick = pick->prev;
        }

        swap(temp,pick);
        temp = temp->prev;  // error here
        size--;
    }
}

但在進行腳本測試時的結果如下

Expectation:  41666
Observation:  {'1234': 0, '1243': 0, '1324': 0, '1342': 0, '1423': 0, '1432': 0, '2134': 0, '2143': 0, '2314': 0, '2341': 0, '2413': 0, '2431': 0, '3124': 0, '3142': 0, '3214': 0, '3241': 0, '3412': 0, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0}
chi square sum:  999984.0

於是重新利用 qtest 進行檢查，發現在執行第二次 shuffle 時會出現以下問題

l = [1 2 3 4]
cmd> shuffle
l = [3 1 4 2]
cmd> shuffle
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted (core dumped)

接著我比較了自己的程式碼與 willwillhi 的差別，發現我的 swap 函式需要考慮當交換元素是相鄰的情況，只需做一次 list_del 與 list_add 即可，最後我的 q_shuffle 的結果如下

Expectation:  41666
Observation:  
{'1234': 41472, '1243': 41759, '1324': 41898, '1342': 41787, 
'1423': 41762, '1432': 41896, '2134': 41434, '2143': 41604, 
'2314': 41916, '2341': 41627, '2413': 41577, '2431': 41962, 
'3124': 41547, '3142': 41829, '3214': 41259, '3241': 41485, 
'3412': 41506, '3421': 41420, '4123': 41392, '4132': 41662, 
'4213': 41752, '4231': 41858, '4312': 42075, '4321': 41521}
chi square sum:  24.648538376614027

亂數

Entropy 定義是某個隨機事件平均每個結果發生時所能傳達出的資訊量，公式如下

S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i}) = - \sum_{i = 1}^{n} P (x_{i}) I (x_{i})

其中

I (x_{i}) = \log_{b} (\frac{1}{P (x_{i})})

I (x_{i})

為期望值，由上式可知，當一個事件的機率越低，所獲得的資訊量則越多

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

INTRODUCTION

面對時序攻擊，舉例來說就是根據密碼的執行時間來推斷密碼，這時判斷執行時間是否是常數時間

O (1)

就十分重，因此本篇論文開發出一種工具 dudect ，一個透過統計分析的程式判斷程式是否是以常數時間執行，解決了底層硬體的問題，也就是無法獲得 CPU 運作訊息的問題

APPROACH

dudect 所使用的方法是 timing leakeage detection tests ，首先測量兩種不同輸入數據類型的執行時間，然後檢查這兩種時間分佈是否在統計上有顯著差異，運用 fix-vs-random 產生兩種測試資料，第一種資料是常數，第二種資料是亂數，而第一種資料通常會給定一個較特別的值，來了解極端狀況

在統計分析前會先進行後處理如 Cropping: 從一組測量值中刪除或捨棄那些偏離正常值或超出 threshold 的測量值，減少不符合正常情況數據的影響，或是其他高階處理

接著是應用統計測試來嘗試反駁 null hypothesis: the two timing distributions are equal ，若是成功反駁此假說，則說明執行時間非常數時間，在本論文中使用 Welch’s t-test 來檢測兩個分佈是否相同

以下為 Welch’s t-test 在本文應用的說明

在進行 Welch’s t-test 時，

t

越接近 0 代表兩組數據的差異越小，在論文中

t

的 threshold 為 4.5 ， t 的定義如下

t = \frac{{\bar{X}}_{1} - {\bar{X}}_{2}}{\sqrt{\frac{σ_{1}^{2}}{n_{1}} + \frac{σ_{2}^{2}}{n_{2}}}}

${\bar{X}}_{1}$ 為 class1 採樣的執行時間的平均值
${\bar{X}}_{2}$ 為 class2 採樣的執行時間的平均值
$n_{1}$ 為 class1 採樣的大小
$n_{2}$ 為 class2 採樣的大小
$σ_{1}$ 為 class1 採樣的執行時間的標準差
$σ_{2}$ 為 class2 採樣的執行時間的標準差

實作

在作業要求中有提到在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無，因此實作目標為在 lab0-c/dudect 中新增此項功能，根據 dudect 可以了解 percentile 的作用為設定閾值，也就是先前所說的後處理的技巧 Cropping

2024q1 Homework1 (lab0)

Reviewed by Shawn531

Reviewed by ShawnXuanc

開發環境

GCC 編譯器

你所不知道的 C 語言 : 函示呼叫篇

malloc & calloc 比較:

Parameter & Argument :

stack :

heap(heap allocator) :

你所不知道的 C 語言：遞迴呼叫篇

遞迴 VS 迭代

針對佇列操作的程式碼實作

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