2024q1 Homework1 (lab0)

contributed by < allenliao666 >

Reviewed by `brian049`

可以補充說明為何 q_delete_dup 函式中要使用 chiankd 的程式碼。
語意通順且研究過程紀錄完整，包括適當引用規格書。
commit message 當中像是 861c80b, f8c79d6 等等，有關於 Modify 的 commit message 皆有補述使用什麼方式去更改。:+1:

已補充相關說明，感謝 review !

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ 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) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7

實做實作指定的佇列操作

對照 Dictionary.com 對 implement 一詞的解釋:

to fulfill; perform; carry out:
to put into effect according to or by means of a definite plan or procedure.
Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

\to

資訊科技詞彙翻譯

結構體

為了更好的了解佇列的結構，參考 chiangkd 開發紀錄的結構圖：

首先 list_head 為雙向鍊結串列，由 prev 和 next 指標組成，其結構如下：

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

*prev: 指向前一個 list_head
*next: 指向下一個 list_head

element_t 由上述的 list_head 和 value 指標組成，結構如下：

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

如下圖所示，element_t 透過 link_head 連接彼此。其中 Head 為一個特別的 list_head ，他的功能為標示佇列的起終點，所以 Head 不是 element_t 而是 list_head。

`q_new`

建立空佇列，並使用 INIT_LIST_HEAD 初始化。

C99[7.20.3] Memory management functions

The order and contiguity of storage allocated by successive calls to the calloc,malloc, and realloc functions is unspecified. The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated). The lifetime of an allocated object extends from the allocation until the deallocation. Each such allocation shall yield a pointer to an object disjoint from any other object. The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementationdefined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

查詢規格書得知 malloc 可能回傳 NULL ，故需判斷記憶體是否配置成功。

    if (!p) {
        free(p);
        return NULL;
    }

`q_free`

釋放佇列所佔的記憶體空間。

明確標注你參考的 GitHub 帳號。

一開始自己寫了迴圈逐一走訪佇列中每個節點並釋放其記憶體空間，後來參考~~同學們~~ Jackiempty 的開發紀錄後發現可以直接使用 list_for_each_entry_safe 巨集。查閱 list.h 的過程後發現有 list_for_each_entry_safe 和 list_for_each_safe 兩種巨集。此處的 entry 即為前面提到的 element ，故兩個巨集的差異為 list_for_each_safe 走訪的對象為 list_head ，而 list_for_each_entry_safe 則是 list_head 所對應的節點。參閱註解後得知，entry 的定義為:

The list nodes are usually embedded in a container structure which holds the actual data. Such container structure is called entry.

`q_insert_head`

插入新的節點到佇列的 head 端。

明確標注你參考的 GitHub 帳號。

在第一版實作時，誤用 q_new 新增至佇列前端。~~參考同學的共筆~~ Jackiempty 的開發紀錄後才終於搞懂 queue 、list 和 element_t 之間的關係(已更新於前面結構體段落)。另外效彷 chiangkd 把原先使用的 malloc 更改為 harness.c 中已有定義 strdup（test_strdup） ，此函式將字串 s 指標輸入後，回傳一個具有同樣內容的指標，其功能即複製字串。透過此函式可以取代掉原方法中的計算長度、分配空間、記憶體複製操作，使程式碼更為整潔。

`q_insert_tail`

插入新的節點到佇列的 tail 端。

其和 q_insert_head 的唯一差異在於插入的位置，故將 q_insert_head 修改後回傳，增加程式碼的可讀性。

    return q_insert_head(head->prev, s);

改進你的漢語表達。

`q_remove_head`

自佇列的 head 端移除節點。

最初不知道參數 bufsize 的用途，參考 nosba0957 的實作:

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_first_entry(head, element_t, list);

    if (sp) {
        memcpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);
    return node;
}

了解 bufsize 在函式 strncpy 中限制 element->value 的長度。

`q_delete_mid`

刪除佇列最中間的節點並釋放其記憶體空間。

運用先前學到的快慢指標概念找到最中間的節點，然後斷開串列並釋放其記憶體空間。

     if (!head || list_empty(head)) {
         return false;
     }
-    struct list_head *fast, *slow, *tail;
+    struct list_head *fast, *slow;
     fast = slow = head->next;
-    tail = head->prev;
-    while (fast->next != tail || fast != tail) {
+    while (fast->next->next != head && fast->next != head) {
         fast = fast->next->next;
         slow = slow->next;
     }

在第一版實作中，沒有刪除最中間的節點，反而誤刪其他節點。故修改 while 迴圈的判斷式，使 slow 指標可以確實指向最中間的節點，並減少程式碼中使用到的指標，維持程式碼的整潔。

`q_delete_dup`

刪除已排序完成的佇列中有相同字串的節點。

參考 chiangkd 的作法，發現他的風格十分簡潔，且善用現有巨集和函式，提高程式碼易讀性。

bool is_dup = false;
list_for_each_entry_safe (c, n, head, list) {
    if (c->list.next != head && strcmp(c->value, n->value) == 0) {
        list_del(&c->list);
        q_release_element(c);
        is_dup = true;
    } else if (is_dup) {
        list_del(&c->list);
        q_release_element(c);
        is_dup = false;
    }
}

對於其中的 is_dup 感到疑惑。用例子執行過一次後發現，因為相同的字串即代表至少有兩個以上，以兩兩一組的方式。在釋放第一個相同字串的節點時把 is_dup 設定為 true ，接著釋放第二個節點時把 is_dup 設定為 false （表示已把重複的節點都刪除了，故重置is_dup ）,之後再檢查下一個節點。

改進你的漢語表達。

`q_swap`

把佇列中的節點兩兩一組交換順序。
參考 ChenFuhuangKye，發現他使用 q_move 令節點前後調換，並且保持程式碼整潔。

list_for_each_safe (n, s, head) {
    if (s == head)
        break;
    list_move(n, s);
    s = n->next;
}

`q_reverse`

反轉佇列中的所有節點。
一開始使用 list_for_each_safe () 走訪佇列所有節點，改變節點的 prev 和 next 指標。後來參考 nosba0957 的方法，使用一個間接指標 indir ，指向第一個節點的 next 。

`q_reverseＫ`

以Ｋ個節點一組，反轉佇列中的節點，直到剩餘節點數量不足Ｋ個。
一開始使用前面提到的 q_reverse 及 list_cut_position 、 list_splice_init 對佇列進行切割及接合。參考 nosba0957 後採用間接指標 indir ，指向第一個節點的 next ，及使用計數器實作。

`q_sort`

依 value 大小對佇列進行排序。
一開始使用快速排序法實作，但在進行 qtest 時時間複雜度超過要求。原因是 qtest 的測資分為隨機亂排及由大到小排序兩種類型，正好快速排序法對由大到小的資料類型最不適合，其時間複雜度會高達

O (n^{2})

。因此採用合併排序法，使用merge_two_list 和 merge_recur 協助實作。

首先把環狀鏈結斷開，並使用 merge_recur 對節點合併排序。最後再重建節點的 prev 指標，使佇列保持雙向環狀的性質。

`merge_two_list`

比較兩個節點的 value ，並依照 value 由小到大連接節點，完成排序。

`merge_recur`

該函式的功能為完成合併排序法中的 divide ，並把分割後的節點透過 merge_two_list 完成合併。實作使用前面提到的快慢指標找到佇列的中間節點，並且把佇列自中間節點切一半，以中間節點為右半佇列的 head ，對左右兩個佇列各自遞迴，直到所有節點之間皆無連結，最後將節點傳遞給 merge_two_list 進行合併。

`q_ascend`

把佇列中的節點依 value 大小檢查，若右側的 value 較小，則刪除該節點。
透過將最左側 value 設為最小值，並逐一和後續節點比較大小，若後續出現 value 較小的節點，則設定該節點為新的最小值，並刪除先前的最小值節點。

`q_descend`

把佇列中的節點依 value 大小檢查，若左側的 value 較大，則刪除該節點。
實作邏輯與 q_ascend 相同，但改為從佇列右側反向比較 value 大小。

`q_merge`

把所有佇列依 value 大小合併排序成一條佇列。特別的是，前面所有函式都是操作佇列中的節點，但 q_merge 則是操作佇列，所以這裡會使用到 queue_cnotext_t 結構體進行實作。

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

queue_cnotext_t 類似 element_t 都是透過串列連結彼此。
首先將佇列透過 lsit_splice_init 合併，再使用 q_sort 排序。

使用 valgrind 檢測記憶體問題

使用 valgrind 檢測時，發現執行速度下降很多，特別是 trace-17 檢測時間複雜度會花很多時間。
檢測後並無發現問題。

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

`attribute (nonnull(2,3,4))`

__attribute__ 為 GCC extension 的定義函數屬性，可以讓編譯器在編譯時做些特殊處理或是檢查動作。
nonnull(2,3,4)表示第二、三、四個引數不能為空。
第一個參數 priv ，在 /lib/test_list_sort.c 當中發現 priv 的功能是讓 check 函式經過 KUnit 測試後可以 failed 。

參考 GNU C __attribute__ 機制簡介

__attribute__ 可以設置函數屬性（Function Attribute）、變量屬性（Variable Attribute）和類型屬性（Type Attribute）

其中函數屬性(Function Attribute)中講到

函數屬性可以幫助開發者把一些特性添加到函數聲明中，從而可以使編譯器在錯誤檢查方面的功能更強大。__attribute__機制也很容易同非GNU應用程序做到兼容之功效。

參考 9.40 attribute((nonnull)) function attribute

This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.

合併規則

合併方式是當有

3 \times 2^{k}

個節點時，合併前兩個

2^{k}

變成

2^{k + 1}

，並留下一個

2^{k}

不動，維持著合併：不合併的比例為 2 : 1 ，因為只要

3 \times 2^{k}

可以放得進 L1 cache，即可避免 cache thrashing。

count 表示 pending list 中節點的數量，在數量自 count 增加為 count + 1 時，例如(2 -> 3)，第 k 個位元設定為 1； k - 1 .. 0 位元清除為 0，此時會將 2 個

2^{k}

合併，並留下一個

2^{k}

。
詳細合併規則請參作業說明(E)。

`merge`

比較 a 、 b 兩個指標的大小，把小的一方加入 head 串列，直到 a 、 b 其中一條串列所有節點都完成比較。最後回傳 head 串列。值得注意的是，為了保持 stable 的特性，若 a == b 則把 a 加入 head 串列。

`merge_final`

顧名思義為最後一次合併，和 merge 的不同點為，此函式維護的串列為環狀雙向鏈結串列，但 merge 回傳的串列為單向串列。

`list_sort`

此函式的精妙之處在於下面的 do-while 迴圈，將 list 中的節點一個接一個加入 pending list 中，並且對 bit 執行 bitwise 操作。依照其結果更新 tail 的位置，若 count 符合前述合併規則就合併，即可保持2:1的比例。

do {
    size_t bits;
    struct list_head **tail = &pending;

    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }

    /* Move one element from input list to pending */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);

引入 list_sort 到 lab0-c 當中

參考 vax-r 的程式碼，修改 list_sort 後加入 lab0-c 。

刪除 priv : priv 不影響排序，故刪除之。
以unsigned char 取代 u8。
實作 cmpfunc : 參考 lib/test_list_sort.c 中 cmp 的實作。

研讀 <Dude, is my code constant time?>

內文概要

Welch’s t test

Welch’s t test 用於當假設兩母群體變異數不相等時，檢測兩母群體的平均值是否相同。相反的，Student's t test適用於兩母群體變異數相等時，因為我們並不知道文中兩類型輸入資料的分佈，即不能保證他們的變異數相等，故本文採用 Welch's t test 。

虛無假說

本文的虛無假說為：兩輸入資料分布相同。若無法拒絕虛無假說表示時序資料洩漏(timing informmation leakage)。臨界值設定為4.5，即 t value > 4.5 表示兩輸入資料分布不同，反之無法拒絕虛無假說。

本文討論許多時間複雜度為常數等級的實作其實存在 timing leakage ，可能遭受 timing attack 。作者介紹一種用於檢測一段代碼是否以恆定時間運行的工具 dudect ，並使用 Welch’s t test 在不模擬硬體的情況下對執行時間進行 time leakage 的檢測。

在測試資料的部分，作者採用 fix-vs-random tests ，將看似常數等級的演算法實作分為兩組，一組為固定值（能夠觸發特定 corner case 的 processing），另一組為隨機測資。

隨後針對 memory comparison 、 AES 、 Curve25519 on an ARM7TDMI 等項目檢測是否存在 time leakage 。

改進 lab-0

在執行 qtest 的 trace-17 時，會出現 not constant 的錯誤訊息。原因是專案中的 dudect 缺少百分位數（percentile）的功能，此功能使原 dudect 原始程式碼略過執行時間超過臨界值的資料，故需要在 lab0-c 中導入 percentile 的功能。
實作 percentile 後終於通過 trace-17!

2024q1 Homework1 (lab0)

Reviewed by brian049

開發環境

實做 實作指定的佇列操作

結構體

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseＫ

q_sort

merge_two_list

merge_recur

q_ascend

q_descend

q_merge