2025q1 Homework1 (lab0)

contributed by <h0w726>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
    CPU family:           6
    Model:                165
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   62%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5199.98
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-11

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

q_new

想法是使用 malloc 分配 list_head 大小的記憶體，接著使用 INIT_LIST_HEAD 巨集初始化剛剛分配的記憶體，建立佇列的 head。若建立失敗就回傳NULL。

struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;

這時候就有個問題：到底什麼是 NULL ?
以前有聽過指標指向 NULL 會是一塊隨意的記憶體，也有聽過指向記憶體位址為0的記憶體，又有聽過 NULL 就是 0 的說法。

依據 C99 6.3.2.3

An integer constant expression with the value 0, or such an expression cast to type
void *, is called a null pointer constant. If a null pointer constant is converted to a
pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

以及參閱你所不知道的 C 語言：指標篇中的空指標常數(null pointer constant)可知，NULL在C語言是被定義成#define NULL ((void *)0) ，這被稱為空指標常數。若將空指標常數轉型為一般指標(e.g int *ptr = NULL)則稱為空指標, 空指標被保證與任何物件或函式的指標不相等。在一般情況下NULL是指向記憶體位址為0的記憶體，不過也不是所有機器都是一樣的，參閱C-FAQ Null Pointers 5.5

Whenever a programmer requests a null pointer, either by writing 0 or NULL, it is the compiler's responsibility to generate whatever bit pattern the machine uses for that null pointer. (Again, the compiler can tell that an unadorned 0 requests a null pointer when the 0 is in a pointer context; see question 5.2.) Therefore, #defining NULL as 0 on a machine for which internal null pointers are nonzero is as valid as on any other: the compiler must always be able to generate the machine's correct null pointers in response to unadorned 0's seen in pointer contexts. A constant 0 is a null pointer constant; NULL is just a convenient name for it.

所以即使在空指標不指向記憶體位址為0的記憶體的電腦中，#define NULL ((void *)0) 也是可行的，編譯器會負責產生空指標。總而言之，C語言標準只有確保空指標與任何物件或函式的指標不相等，實際上指向何處還是由機器決定。

q_free

element_t *entry = NULL;
element_t *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
    free(entry);
}

一開始想用list_for_each_entry_safe迭代節點逐個使用free刪除，後來發現因為element_t結構裡value也是指向動態配置的記憶體，應該改寫為

element_t *entry = NULL;
element_t *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
    free(entry->value);
    free(entry);
}

最後改為

element_t *entry = NULL;
element_t *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
    list_del(&entry->list);
    q_release_element(entry);
}

q_insert_head and q_insert_tail

element_t *node = malloc(sizeof(element_t));
if (!node) {
    return false;
}
node->value = strdup(s);
if (!node->value) {
    free(node);
    return false;
}

先使用malloc配置element_t結構中大小的記憶體，strdup函式則用來將參數s指向的記憶體裡的內容複製到element_t結構中value指向的記憶體。關於strdup函式的介紹可參閱strdup(3) — Linux manual page裡面提到

The strdup() function returns a pointer to a new string which is a
duplicate of the string s. Memory for the new string is obtained
with malloc(3), and can be freed with free(3).

也就是說上述提到複製到element_t結構中value指向的記憶體，strdup函式呼叫時會自動配置好，呼叫前不用特地配置。

最後再使用list_add或list_add_tail巨集，插入佇列頭部或尾部。

q_remove_head and q_remove_tail

element_t *last = list_last_entry(head, element_t, list);

list_del(&last->list);
if (sp) {
    sp = strncpy(sp, last->value, bufsize);
    sp[bufsize - 1] = '\0';
}

使用list_first_entry或list_last_entry取得首個或最後一個節點的位置，這裡使用strncpy函式而不是strdup是因為參數sp已經有配置記憶體空間了。

依據 C11 7.1.1

A string is a contiguous sequence of characters terminated by and including the first null character.

以及stpncpy(3) — Linux manual page可知，若字串複製長度太長會直接截斷，所以最後要補上null character。

q_size

list_for_each迭代節點並計算節點數量。

q_delete_mid

struct list_head **indir = &head->next;
for (const struct list_head *fast = head->next;
    fast != head && fast->next != head; fast = fast->next->next)
    indir = &(*indir)->next;

參閱你所不知道的 C 語言: linked list 和非連續記憶體使用指標的指標，搭配快慢指標找出中間的節點並刪除。

q_delete_dup

使用list_for_each_entry_safe迭代節點，藉由布林值紀錄節點的值是否重複。
這裡比較值使用的函式是 strncmp，特別須注意的是，這裡是比較字串的大小，也就是比較兩字串間的ASCII值。

q_swap

struct list_head *node1,*node2;
list_for_each_safe(node1,node2,head){
    if (node2 == head)
        break;
    node1->prev->next = node2;
    node1->next = node2->next;
    node2->next = node1;
    node2->next->prev = node1;
    node2->prev = node1->prev;
    node1->prev = node2;
    node2 = node1->next;

初步想法是使用list_for_each_safe巨集迭代節點，以及藉由調整要交換的兩個節點與前後節點之間的指標關係達成交換。

然而寫完發現測試時會陷入無限迴圈

+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

於是參考 vax-r 的實作

struct list_head *node1, *node2;
list_for_each_safe (node1, node2, head) {
    if (node2 == head)
        break;
    node1->prev->next = node2;
    node2->prev = node1->prev;
    node1->next = node2->next;
    node1->prev = node2;
    node2->next->prev = node1;
    node2->next = node1;
    node2 = node1->next;
}

以及將指標間的調整關係畫出圖後
相片 2025-3-9 凌晨1 17 13
發現自己錯誤更新了指標，在調整鏈結串列的關係時，把圖畫出來較好。
TODO:使用graphviz

q_reverse

使用list_for_each_safe巨集迭代節點，再用list_move逐一移到鏈結串列的頭部便達到反轉的效果。

q_reverseK

想法是先用list_cut_position巨集將要反轉的K個節點切下，反轉後接上暫存的鏈結串列，最後再將整段接回原來的head。

mergeTwoLists

此函式將兩個linked list 合併並以遞增或是遞減排序，參考 weihsinyeh 。

q_sort

參閱你所不知道的 C 語言: linked list 和非連續記憶體，遞迴地呼叫q_sort使用快慢指標找出鏈結串列的中間節點，將鍊結串列切成兩半，直到每個節點都獨立，最後利用mergeTwoLists將鍊結串列排序。

q_ascend and q_descend

一開始的想法是宣告一個空指標用來指向當下的最大或最小值

element_t *entry, *safe;
char *value = NULL; 
int count = 0;

list_for_each_entry_safe(entry, safe, head, list) {
    if (!value || strcmp(entry->value, value) < 0) {
        value = entry->value;
        count++;
    } else {
        list_del(&entry->list);
        q_release_element(entry);
    }
}

但是在commit時會過不了靜態分析

queue.c:237:13: style: Condition '!value' is always true [knownConditionTrueFalse]
        if (!value || strcmp(entry->value, value) < 0) {
            ^
queue.c:233:19: note: Assignment 'value=NULL', assigned value is 0
    char *value = NULL;
                  ^
queue.c:237:13: note: Condition '!value' is always true
        if (!value || strcmp(entry->value, value) < 0) {
            ^

後來改宣告element_t類型的指標去指向含有最大或最小值的節點。

const element_t *max_node = list_first_entry(head, element_t, list);
list_for_each_entry_safe (entry, safe, head, list) {
    if (strcmp(entry->value, max_node->value) > 0) {
        list_del(&entry->list);
        q_release_element(entry);
    } else {
        max_node = entry;
    }
}

TODO:了解為什麼靜態分析無法通過

q_merge

想法是使用list_for_each_entry巨集迭代佇列，將各個佇列指向的鏈結串列用list_splice_tail_init都接到第一個queue的鏈結串列後，最後呼叫q_sort函式完成排序。

在 qtest 提供新的命令 shuffle

參閱2025 年 Linux 核心設計課程作業 —— lab0 (D)

利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
1. 先用 q_size 取得 queue 的大小 len。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。

執行./qtest結果如下：

cmd> it RAND 5
l = [uocslla ghgrnfqq yramdso kelpz rnznempk]
cmd> shuffle
l = [ghgrnfqq yramdso kelpz rnznempk uocslla]
cmd> shuffle
l = [uocslla rnznempk ghgrnfqq yramdso kelpz]
cmd> shuffle
l = [uocslla yramdso kelpz ghgrnfqq rnznempk]
cmd> shuffle
l = [ghgrnfqq kelpz uocslla rnznempk yramdso]

但是這樣看不出來洗牌是不是公平的，若有3個元素進行洗牌，排列方式有

3! = 6

種，我們實作的洗牌必須確保這六種出現的機率是相同的，才是公平的洗牌。
於是使用2025 年 Linux 核心設計課程作業 —— lab0 (D)的測試程式進行模擬，並用直方圖畫出各種排列情形的次數，判斷實作是不是公平的洗牌。
模擬結果如下：is_in

Expectation:  41666
Observation:  {'1234': 41438, '1243': 41780, '1324': 41813, '1342': 41729, '1423': 41660, '1432': 41624, '2134': 41588, '2143': 41583, '2314': 41644, '2341': 41520, '2413': 41380, '2431': 41571, '3124': 41680, '3142': 41560, '3214': 41734, '3241': 41573, '3412': 41836, '3421': 41419, '4123': 41591, '4132': 41786, '4213': 41512, '4231': 42018, '4312': 41759, '4321': 42202}
chi square sum:  19.108049728795663

參閱2025 年 Linux 核心設計課程作業 —— lab0 (D)，使用統計方法驗證shuffle

1. 先計算 chi-squared test statistic

$X^{2}$

X^{2} = \sum_{i = 1}^{N} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

$X^{2}$ : Pearson's cumulative test statistic
$O_{i}$ : the number of observations of type i
$E_{i}$ : the expected count of type i

程式模擬已經算出來

X^{2}

= 19.108049728795663

2. 決定自由度（degrees of freedom）
對於 N 個隨機樣本而言，自由度為 N - 1。這裡有

4! = 24

個樣本，所以自由度為23。

3. 選擇顯著水準

顯著水準（Significance level）α 代表在虛無假說（
$H_{0}$ ）為真下，錯誤地拒絕（
$H_{0}$ ）的機率，即型一錯誤發生之機率。
α = P(拒絕
$H_{0}$ ｜
$H_{0}$ 為真)
我們 alpha 設定為常見的 0.05。
P value
從卡方分布表找合適的 P value，我們的自由度為 23，
$X^{2}$ 為 19.108049728795663，因為 11.689 < 19.108049728795663 < 28.429 ，於是 P value 介於 0.975 和 0.2 之間。

4. 統計檢定的結果不拒絕虛無假說
因為得到的P Value > α ，統計檢定的結果不拒絕虛無假說（

H_{0}

），也就是shuffle的結果不拒絕是遵循Uniform distribution。

將各種排列出現次數畫成直方圖也能看出大致上符合 Uniform distribution。
Figure_1

然而在與同學討論時，他發現我的實作中沒有 srand(time(NULL)) ，一開始我不確定它的作用，所以參閱C語言規格書

依據C99 7.20.2.2

The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is called before any calls to srand have been made, the same sequence shall be generated as when srand is first called with a seed value of 1.

以及依據C99 7.20.2.1

The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.
The value of the RAND_MAX macro shall be at least 32767

可以發現，原來平常呼叫 rand 所產生的隨機數如果沒有改變 seed 的話，產生出的數字其實是一樣的，PRNG Tools 提到若使用 gcc 編譯器時，呼叫 rand 得到的值與 seed 之間的關係。
於是我嘗試在 q_shuffle 中引入 srand(time(NULL)) ，以為可以讓洗牌的亂度更亂，執行出來卻反而不是 Uniform distribution
Figure_12
接著我參考 weihsinyeh 發現他有對這部份進行研究，原來一開始實作的程式碼能夠符合 Uniform distribution 是 qtest.c 中有 srand(os_random(getpid() ^ getppid())); 設置 seed ，其中這段程式碼的註解為

/* A better seed can be obtained by combining getpid() and its parent ID
* with the Unix time.
*/
srand(os_random(getpid() ^ getppid()));

這時我以為 srand(os_random(getpid() ^ getppid())) 是因為其為比較好的 seed 所以才能符合 Uniform distribution ，於是將 qtest.c 中的 srand(os_random(getpid() ^ getppid())) 改為 srand(time(NULL)) ，會是什麼情形，q_shuffle 中的 srand(time(NULL)) 刪除，結果發現其符合 Uniform distribution。

後來我嘗試保留 q_shuffle 中的 srand(time(NULL)) ，刪除 qtest.c 中的 srand(os_random(getpid() ^ getppid())) ，這時卻又不符合Uniform distribution了。於是我將 q_shuffle 中的 srand(time(NULL)) 改為 srand(os_random(getpid() ^ getppid())) ，這時又符合Uniform distribution。可以發現不是因為在 q_shuffle 中重設 seed 造成不符合Uniform distribution，而是 srand(time(NULL)) 設的 seed 不夠亂，srand(os_random(getpid() ^ getppid())) 確實為比較好的 seed。

那為什麼將 qtest.c 中的 srand(os_random(getpid() ^ getppid())) 改為 srand(time(NULL)) 還是能符合 Uniform distribution 呢，要知道答案必須先知道 rand 是基於 Linear congruential generator 實作的，其產生的數字在某個週期之後會重複，但一般編譯器這週期不會太快重複，所以如果只在第一次執行初始化 seed，也就是在 qtest.c 中使用 srand(time(NULL)) ，表現反而會比每次 shuffle 都重設 seed 好，但這其實不是正確的方法，因為 LCG 產生的亂數會影響到下一次的 shuffle ，導致無法真正知道 shuffle 是不是公平的。

如果我們不想讓產生的亂數影響到 shuffle ，應該在每次 shuffle 前，重設一個足夠好的 seed ，每次都能得到不同且更隨機的 seed，而不是如 srand(time(NULL)) ，若短時間呼叫多次，得到的 seed 還是不變。採用的作法是在 shuffle 前，使用srand(os_random(getpid() ^ getppid())) 重設 seed，不讓亂數影響到 shuffle 。
Figure_31
測試結果為 Uniform distribution 。 (Commit 90ce388)

亂數

在分析前，我想先知道當執行 ./qtest 後，搭配 it RAND 10 指令所產生的隨機字串是怎麼來的。首先在 qtest.c中的 queue_insert 發現

 if (!strcmp(inserts, "RAND")) {
    need_rand = true;
    inserts = randstr_buf;
}

也就是說隨機字串是被存在 randstr_buf 中，接著可以在 fill_rand_string 發現隨機字串是怎麼生成的

uint64_t randstr_buf_64[MAX_RANDSTR_LEN] = {0};
randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
for (size_t n = 0; n < len; n++)
    buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];

buf[len] = '\0'

其中 randombytes 其實就是呼叫 linux_getrandom

static int linux_getrandom(void *buf, size_t n)
{
    size_t offset = 0;
    int ret;
    while (n > 0) {
        /* getrandom does not allow chunks larger than 33554431 */
        size_t chunk = n <= 33554431 ? n : 33554431;
        do {
            ret = getrandom((char *) buf + offset, chunk, 0);
        } while (ret == -1 && errno == EINTR);
        if (ret < 0)
            return ret;
        offset += ret;
        n -= ret;
    }
    assert(n == 0);
    return 0;
}

可以發現 getrandom 是用來產生隨機數的函式，但我不知道是怎麼產生的，於是參閱 getrandom(2) 理解 getrandom 的用途，

The getrandom() system call fills the buffer pointed to by buf with up to buflen random bytes.These bytes can be used to seed user-space random number generators or for cryptographic purposes.
By default, getrandom() draws entropy from the urandom source (i.e., the same source as the /dev/urandom device).This behavior can be changed via the flags argument.

getrandom 可以從 /dev/urandom 獲取一連串的 random bytes，但我不知道 /dev/urandom 是什麼，參閱 Linux 核心專題: 亂數產生器研究以及 Documentation and Analysis of the Linux Random Number Generator 得知，在 Linux 中，/dev/urandom 和 /dev/random 都是用來產生隨機數的文件，它們收集環境噪音（例如：磁碟操作、鍵盤的輸入）數據，再將這些數據利用 LFSR 添加一些隨機性，存入 entropy pool。當呼叫 getrandom 時，entropy pool 會提供隨機數，使用 /dev/urandom 和 /dev/random 根據 getrandom 中 flags 參數而定， urandom 和 random 差異在於 random 會因 entropy pool 中隨機數不夠而阻塞等待有足夠的熵可使用。

在 fill_rand_string 的這行程式碼使用指標轉型

randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));

依據C11 6.3.2.3

A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object.

也就是說在 C 語言中，指標的轉型是被允許的，前提是轉換後的指標必須符合記憶體對齊的要求

0    1    2    3    4 
|----|----|----|----|----|
     ^
    char*

若轉為

0    1    2    3    4 
|----|----|----|----|----|
     ^
    int*

會是 undefined behavior，因為 int 要求以 4 bytes 對齊。

在 random.c 實作 Xorshift

使用 ENT 比較 Xorshift 和 /dev/random 兩種產生亂數的方法，總共測試 10485760 個 bytes。

PRNG	內建	Xorshift64
Entropy	7.999983	7.999982
Compression	0 %	0 %
Chi square distribution	243.60	249.06
confidence level	59.3 %	26.26%
Arithmetic mean vlue	127.5352	127.5180
Monte Carlo value	3.141239602	3.141905648
Serial correlation coefficient	0.000385	-0.000652

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

閱讀論文

論文中提到 Timing attacks 是一種攻擊者可以透過測量程式的執行時間的不同，達到推測密碼的攻擊。儘管許多演算法在設計上為常數時間，但還是有洩漏時間資訊的風險，例如程式中含有分支，或是記憶體存取模式的不同，需要透過人工或工具進一步檢測。然而，目前的工具的困難是硬體模型不容易建立，作者便提出了 dudect 此工具，在任何 CPU 上都可直接執行，實現可以分為以下幾個步驟。

測量執行時間
為測試程式碼設計兩種數據，一是固定輸入，也就是選擇一個固定值作為輸入。另一則是隨機輸入，每次測試會使用不同的隨機值進行輸入，輸入為固定值還是隨機值也是隨機決定的，避免輸入順序可能也會造成影響。以及透過高精確度的計時器測量時間，例如 x86 CPU 的 TSC 暫存器。
後處理
測量出來的執行時間可能會因某些原因造成結果過於極端，dudect會選擇閾值捨棄偏差過大的數據，也會引入 High-order-processing，因為有時洩漏時間不一定在平均值能發現，需要透過 High-order-processing讓後續的檢定能檢測到。
統計測試
此篇論文透過Welch´s t-test檢定兩組數據是否有顯著不同，若無法拒絕兩者無顯著不同，則判斷程式碼為常數時間。

解釋Student's t-distribution

我們在進行假設檢定時，通常會使用常態分佈估計，但這只適用於樣本數夠大的情況（中央極限定理）。Student t-distribution 用於在樣本數小的情況下，Student t-distribution的機率密度函數相較於常態分佈，在兩側的部份會有更大的尾巴，因為在小樣本中，極端值造成的影響較大，這會造成臨界值更往兩側靠近，也就是說會更難拒絕

H_{0}

。

source

程式的 "simulation" 模式及實作Percentile

在自動評分系統有一項是測試實作的 q_insert_tail, q_insert_head, q_remove_tail,q_remove_head函式是否為常數時間。

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant

不過在測試時會出現有時通過有時不通過的情況，所以先嘗試了解測試是怎麼進行的。

在qtest.c可以發現測試是否為常數時間是透過is_remove_tail_const 和 is_remove_head_const函式

#if !(defined(__aarch64__) && defined(__APPLE__))
    if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok =
            pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
    }
#endif

在dudect/fixture.h

#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

發現函式如此定義，但是看不懂這在寫什麼，後來在dudect/constant.h找到DUT_FUNCS的定義

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

但是不理解##符號是什麼意思，於是參閱C語言規格書

依據 C99 6.10.3.3

If,in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence.

也就是說會產生

bool is_insert_head_const(void);
bool is_insert_tail_const(void);
bool is_remove_head_const(void);
bool is_remove_tail_const(void);

在dudect/fixture.c有函式的定義

#define DUT_FUNC_IMPL(op) 
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

接著看test_const發現doit函式，其中doit函式寫道

bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();

其中differentiate 計算執行一次函式的時間。
update_statistics 將執行時間依照輸入類別分類並使用t-test驗證實作的函式是否為常數時間。
所以我們實作percentile在update_statistics進行t-test前，剔除執行時間的極端值。
參閱dudect: dude, is my code constant time?
引入三個函式在dudect/fixture.c

static int cmp(const int64_t *a, const int64_t *b)
{
    if (*a == *b)
        return 0;
    return (*a > *b) ? 1 : -1;
}

判斷a和b大小，若a>b回傳1，反之回傳-1。

static int64_t percentile(int64_t *a_sorted, double which, size_t size)
{
    size_t array_position = (size_t) ((double) size * (double) which);
    assert(array_position < size);
    return a_sorted[array_position];
}

對於已排序好的陣列，取出某個百分比的值，若陣列大小為10，size*which取出50%，也就是a_sorted[5]。

static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles)
{
    qsort(exec_times, N_MEASURES, sizeof(int64_t),
          (int (*)(const void *, const void *)) cmp);
    for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
        percentiles[i] = percentile(
            exec_times,
            1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),因為我在篩選出極端值後
            N_MEASURES);
    }
}

qsort 會以遞增排序exec_times，1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES則用來篩選出極端的數據,寫到這裡我發現第一次commit的部份沒有做到剔除極端值的功能（Commit f83a330）,因為我在篩選出極端值後,沒有做剔除或其他動作,但是卻通過了評分測試,後來發現原因在prepare_percentiles會對執行時間進行排序以及 if (first_time)的分支,只要有對執行時間排序,測試出來就會是常數時間
。原始程式碼會根據不同閾值刪除執行時間,進行t-test觀察閾值對測試結果的影響。我改為刪除百分之一的數據（Commit 1da1975）,雖然可以通過測試,但是我的實作中是存在分支以及 strdup 這類會因輸入不同影響執行時間的函式,我認為應是時間差距不大所以被認為是常數時間。

研讀lib/list_sort.c

Valgrind

+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
==86634== Invalid read of size 8
==86634==    at 0x11063D: q_descend (queue.c:290)
==86634==    by 0x10BC4A: do_descend (qtest.c:790)
==86634==    by 0x10E74D: interpret_cmda (console.c:181)
==86634==    by 0x10ED12: interpret_cmd (console.c:201)
==86634==    by 0x10EFA1: cmd_select (console.c:593)
==86634==    by 0x10F87F: run_console (console.c:673)
==86634==    by 0x10DB3C: main (qtest.c:1444)