HackMD
2025q1 Homework1 (lab0)
contributed by < Jordymalone >
開發環境
$ 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: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 7800X3D 8-Core Processor
CPU family: 25
Model: 97
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
CPU(s) scaling MHz: 46%
CPU max MHz: 5050.0000
CPU min MHz: 545.0000
BogoMIPS: 8400.02
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 8 MiB (8 instances)
L3: 96 MiB (1 instance)
針對佇列操作的程式碼實作
在正式進入實作程式碼環節前，先研讀 C Programming Lab，同時為了後續寫這份作業更順利，也參考了 The Linux Kernel API - List Management Functions 來理解 Linux 核心原始程式碼風格。
常用結構體
queue 結構
/* Linked list element */
typedef struct list_ele {
char *value;
struct list_ele *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* First element in the queue */
} queue_t;
所有 struct list_head 的操作都應參考 The Linux Kernel API
q_new
定義: 建立新的「空」佇列
Commit 9742ac4
單純建立一個新的 head 節點，並分配記憶體空間給他，養成一個好習慣在每次 malloc 之後都要檢查是否有 malloc 成功，最後再對他做初始化，因為是雙向鏈結串列，要把 head 的 prev 和 next 指標都先指向自己。
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *new_head = malloc(sizeof(struct list_head));
if (!new_head) {
return NULL;
}
INIT_LIST_HEAD(new_head);
return new_head;
}
q_free
定義: 釋放佇列所佔用的記憶體
Commit 1e89cdd
撰寫時，我在想每當我指到一個節點時，我用 free() 就可以把整個節點給 free 掉嗎?
答案是不行，因為我們定義 element_t 的結構中有用到 指標 char *value ，所以我們得手動將這個指標給 free 掉。
後來發現有 q_release_element 函式可以一次幫我做到我要的功能。
同時使用 #define list_for_each_entry_safe(entry, safe, head, member) 即可做到將鏈結串列中的節點一個一個給釋放掉，最後再把 head 給釋放掉就達到目的了 !
q_insert_head
定義: 插入一個 element 在佇列開頭
Commit 5afea2d
研讀 Intrusive linked lists 理解該如何去操作 element_t 結構中的 list_head list ，再透過list_add 將新增的節點插入在開頭
因為我們需要把參數中的 char *s 給複製到 element_t 中的 char *value 中，所以我們需要用到 C library 的函式，目前是用 strcpy 將 s 複製到 value 中，但有個疑問是使用 strcpy 他的 return value 何去何從？
要記得分配記憶體給 element 中的 value !!!
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *new_element = malloc(sizeof(element_t));
if (!new_element) {
return false;
}
new_element->value = malloc(strlen(s) + 1);
strcpy(new_element->value, s);
list_add(&new_element->list, head);
return true;
}
實作後並使用 git commit -a 時遇到的問題
Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/jordan/jserv/lab0-c/queue.c
42: strcpy(new_element->value, s);
62: strcpy(new_element->value, s);
Read 'Common vulnerabilities guide for C programmers' carefully.
https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
Running static analysis...
上述文件內容表示若使用 strcpy 不當，很有可能因為沒去確認 buffer length，而導致將超出這個區域的數據去覆蓋到相鄰的記憶體區域。
因此，將 strcpy 改用 strncpy，同時在 malloc 之後去確認是否有成功 allocate memory 給 new_element->value，若沒有就釋放。
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
...
new_element->value = malloc(strlen(s) + 1);
+ if (!new_element->value) {
+ free(new_element);
+ return false;
+ }
- strcpy(new_element->value, s);
+ strncpy(new_element->value, s, strlen(s));
+ new_element->value[strlen(s)] = '\0';
list_add(&new_element->list, head);
return true;
}
q_insert_tail
類似 q_insert_head ，只是這個函式是將 element 插入到佇列的尾巴。
遇到同 q_insert_head 的問題，一併修改。
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
...
new_element->value = malloc(strlen(s) + 1);
+ if (!new_element->value) {
+ free(new_element);
+ return false;
+ }
- strcpy(new_element->value, s);
+ strncpy(new_element->value, s, strlen(s));
+ new_element->value[strlen(s)] = '\0';
list_add_tail(&new_element->list, head);
return true;
}
q_remove_head
定義: 將佇列開頭的節點移除 (remove)
Commit 3319d8e
sp 的用途是什麼？
使用 strdup 內部的函式會再做 memcpy
If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)
TODO: 補足 remove 的意思
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head) {
return NULL;
}
if (list_empty(head)) {
return NULL;
}
element_t *elem = list_first_entry(head, element_t, list);
list_del_init(&elem->list);
if (bufsize == strlen(elem->value)) {
sp = strdup(elem->value);
}
return elem;
}
目前的這個寫法可以成功把節點從頭移掉，但會有下面這問題
l = [3 2 1]
cmd> rh
ERROR: Failed to store removed value
Removed from queue
l = [2 1]
看起來是我的 strdup 用錯方式了，同時我的 if 條件式也在亂寫，因此重新寫
TODO: 釐清
strdup與strncpy
修改
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head) {
return NULL;
}
if (list_empty(head)) {
return NULL;
}
element_t *remove_elem = list_first_entry(head, element_t, list);
list_del_init(&remove_elem->list);
if (sp) {
strncpy(sp, remove_elem->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return remove_elem;
}
q_remove_tail
定義: 將佇列尾巴的節點移除 (remove)
Commit 3319d8e
實作流程與 q_remove_head 類似，差別只在於這邊要 remove 佇列中尾巴的節點。
q_size
定義: 計算目前佇列的節點總量
Commit c4ed8b8
實作想法，定義一個新的指標，從 head->next 開始往後計算，直到繞一圈回到 head 為止，這時候就可以用到 list_for_each 由 define 所定義的 marco function 來去 iterate 整條 circular doubly-linked list。
q_delete_mid
定義: 將佇列中位於中間的節點刪除
Commit b380c09
實作之前，先去撰寫 leetcode，我使用的是 Two Pointers 來去寫這題，同理套用到 q_delete_mid 上。
原始寫法
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head)) {
return false;
}
struct list_head *fast = head;
struct list_head *slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
list_del_init(slow);
element_t *to_delete = list_entry(slow, element_t, list);
q_release_element(to_delete);
return true;
}
使用 ./qtest 測試發現
cmd> dm
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
我才意識到我很愚蠢的錯誤，q_delete_mid 是建立在 doubly Linked list 的資料結構上，因此在第 10 行會遇到 infinite loop 的問題。
調整後
struct list_head *fast = head->next;
struct list_head *slow = head->next;
- while(fast != NULL && fast->next != NULL) {
+ while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
q_delete_dup
定義: 從佇列中刪除所有包含重複字串的節點，最終只保留那些在原始佇列中只出現一次的字串
Commit ceca2de
寫完 leetcode 的題目再來實作這個函式，已經有個大致上的架構，首先 leetcode 上的資料結構是單向鏈結串列，因此我利用一個 dummy 節點，及兩個指標 prev 和 cur，只要遇到連續重複的 value，就把它整段跳過，讓前一個節點直接連到重複區段之後的新節點。
接下來，透過同樣的邏輯移植到 q_delete_dup 這個函式上，dummy 節點可以用 head 來代替，一樣宣告了兩個 list_head 指標 start 和 end，start 指向當前確認的節點，然後用 end 往後找，直到遇到一個 value 與 start 不同的節點就停止，這樣 [start, end) 就是一個連續重複的區段
q_swap
定義: 交換佇列中鄰近的兩個節點
Commit e91a25c
LeetCode 的題目主要是透過修改各自的指標來達成目的，同理套用到這個函式上，差別在於 LeetCode 的題目是 singly Linked list，但我們作業的函式是 doubly linked list，因此不免俗的，我們一樣要來先確認 list.h 是否有可以直接拿來用的巨集。
發現我們可以使用 list_add 和 list_del 來達到目的
list_del: 負責從原來的位置移除節點。list_add: 用來將一個特定的節點插入到我們指定的head節點之後，因此在使用時，要注意參數的順序。
函式一開始會先檢查鏈結串列是否為空或是只有一個節點 (透過 list_empty 和 list_is_singular)，在這兩種情況下就不需要做交換。接著，利用迴圈，每次同時取得兩個相鄰的節點，然後先將前一個節點刪除，再通過 list_add 插入到後一個節點之後，這樣叫做到交換位置的功用了。
q_reverse
定義: 反轉佇列中的元素
Commit e5beef7
首先，我們宣告三個指標:
current: 代表當前待調整的節點front: 指向current->next的位置last: 指向current->prev的位置
我們從鏈結串列的 head 節點開始，初始時設定 front = head->prev 與 last = head->next，然後交換 head 節點中的 next 與 prev 指標。依照這順序對每一個節點進行指標反轉操作，最終即可得到一個順序完全反轉的鏈結串列。
q_reverseK
定義: 類似 q_reverse，但每次反轉鏈結串列的 k 個節點
Commit b3b452d
參考第二週問答簡記的討論，給了我一點啟發。
函式實作上，我運用到了多個 list.h 中定義的 API，首先去確認鏈結串列是否為空，或是只有一個節點，又或是傳入的 k 不合理，就直接返回。
使用 q_size 來得到佇列的大小，每次從 head 中取出 k 個節點，並利用 list_add 插入至 tmp 佇列後面，來達成反轉的目的，再將這 k 個節點透過 list_splice_tail_init 來將反轉後的段落接到 result 佇列中。
若原先佇列不足 k 個節點，將剩餘節點直接接到 result 佇列 (保持原順序)，最後再將結果整段從 result 接回 head，以此更新原先的鏈結串列成新的順序。
q_sort
定義: 以遞增順序來排序鏈結串列的節點
Commit a0878e7
參閱 Linked List Sort 來得知實作手法
參考 ItisCaleb
參考上述內容，我選擇使用 merge sort 來實作我的 q_sort。
首先，我定義了一個輔助函式 merge_two_lists，我們將兩個以排序好的鏈結串列 (l1 和 l2) 合併在一起，形成一個新的鏈結串列 (head)。這個函式首先處理了特殊情況，如果兩個鏈結串列都為空，或者其中一個為空 ，就直接將非空的列表內容拼接到目標鏈表。當兩個列表都有數據時，函式會進入一個 while 迴圈，不斷從兩個列表中各取出第一個元素 (透過 list_first_entry 取得 element_t 結構)，然後依據字串比較結果決定把哪一個元素移動到結果鏈表的尾巴。最後，如果其中一個列表還有剩餘的元素，就將他們通通拼接到結果鏈表中。
q_sort 函式則實現了整個鏈表的排序過程。首先，它檢查鏈表是否為空或僅包含一個節點，如果是這種情況，直接返回，不需要進行排序。否則，q_sort 採用快慢指針來找到鏈結串列中的中間位置，經典的分割方法!接著，將原始鏈結串列的所有節點移動到一個臨時鏈結串列 (right) 中，然後利用 list_cut_position 將 right 中的 head 到 slow 這段範圍的節點分割給 left。接下來就是對這兩個子串列分別遞迴調用 q_sort 進行排序。排序完成後，使用 merge_two_lists 將兩個以排序好的子串列合併回原始鏈結串列 head。
最後，如果希望最終的結果為 descend，則調用 q_reverse 將合併後的鏈結串列反轉。
q_ascend
定義: 檢查每一個節點，若其右側任意位置存在一個值嚴格小於當前的節點，則將該節點移除，最後回傳佇列長度
Commit f8ea3d0
疑問:
去確認 queue.h 的註解如下
q_descend() - Remove every node which has a node with a strictly greater value anywhere to the right side of it.
…
Memory allocated to removed nodes must be freed.
開頭敘述是 remove 節點，這樣不就代表單純是移除節點而不需要 free 嗎?為什麼後面的註解還特別說要把移除的節點做 free 呢?
此函式的用意就是得到一個非遞減的佇列。
一開始在撰寫 leetcode ，思路很直接，我是直接寫個 reverseList() 把鏈結串列的頭尾顛倒後，原本右側的節點就會跑到左側，這個反轉的用途是有巧思的!
這題的要求是: 如果一個節點右側存在一個比它大的值，那這個節點應該被刪除，但這樣子做就會很難一次便利就解決，因為每個節點右側有可能有很多節點需要檢查。
這時，我們先做個反轉，原本的右側部分就變成了左側，這樣在逐一走訪反轉後的鏈結串列時，我們就可以維持一個最大值的概念。
也就是說:
- 反轉之後，等同於我們從原先鏈結串列的尾巴開始逐一走訪，此時，當前節點 (這邊以指標
cur表示) 就是目前為止的最大值，也就是原先鏈結串列右側最大的值。 - 接著，如果發現
cur的值小於cur->next的值，就意味著原先cur->next在原順序中其右側存在一個比它小的值 (也就是cur)，所以cur->next應該被刪除。
因此，以這個概念來去實作 q_ascend 這個函式，思路就很清晰了。
-
反轉鏈結串列 (q_reverse)
- 透過反轉鏈結串列，我們可以從原本的尾部開始進行逐一走訪，這樣可以確保對每個節點而言，我們只需要關注他右側已出現的最小值 (或最大值，對於
q_descend而言)，從而在逐一走訪過程中決定是否刪除節點
- 透過反轉鏈結串列，我們可以從原本的尾部開始進行逐一走訪，這樣可以確保對每個節點而言，我們只需要關注他右側已出現的最小值 (或最大值，對於
-
更新與刪除節點
- 在逐一走訪的過程中，我持續維持了一個變數
min_value，每當遇到一個值比min_value還小的節點時，代表這個節點在原順序中不會有右側比他小的值，因此更新min_value，反之，則表示順序中其右側存在更小的值，比需刪除這個節點。
- 在逐一走訪的過程中，我持續維持了一個變數
-
恢復原始順序
- 完成後，再次反轉鏈結串列，使得最終結果與原來的順序保持一致
這個實作流程同樣可以應用在 q_descend 上，只需將比較條件調整為檢查是否存在更大的值即可。
q_descend
定義: 檢查每一個節點，若其右側任意位置存在一個值嚴格大於當前的節點，則將該節點移除，最後回傳佇列長度
Commit f8ea3d0
實作概念同 q_ascend，只差在一個是大於一個是小於。
q_merge
定義: 合併所有已排序的佇列，並合而為一個新的已排序佇列
Commit 5737c39
在正式實作這個函式之前，需要先去理解 queue_context_t 的結構體以及存取方式。
在 list.h 中有明確定義 queue_context_t 結構體，同時在 qtest.c 中也有定義 queue_chain_t 的結構體。
每個 queue_context_t 是用來管理整個佇列資訊。這個結構中有個指標 q，指向實際由多個 element_t 組成的佇列，同時他還有個 chain 成員，這個成員也是個 list_head，用來把所有佇列都串接在一起。換句話說，每個 queue_context_t 不僅記錄了他所管理的佇列中有多少 element_t 以及他唯一的 ID，同時也可以作為鏈中的一環，讓我們可以把多個獨立的佇列串接起來。
最後，queue_chain_t 則提供了一個統一的入口，他把自己當作 head 將所有 queue_context_t 串成一條鏈。這樣一來，不論我們有多少個獨立的佇列，都可以從這個入口出發，逐一走訪每個佇列的資訊，進行統一的操作，比如說我們要實作的這個函式 q_merge，合併所有佇列。
實作流程:
首先，我定義了一個輔助函式 merge_two_sorted_queues，他主要負責合併兩個已排序的佇列。函式首先確認兩個輸入的佇列是否為空，如果其中一個佇列為空，就直接將非空的佇列拼接到目標位置，如果兩個佇列都有元素，則利用一個臨時暫存的鍊表 (result) 來存放合併過程中的排序結果。
在 while 迴圈中，我們分別從兩個佇列取出第一個元素，然後根據 descend 參數比較規則，若是 descend 則把字串較大的元素移動 result 的尾巴，若是 ascend，則反之。當其中一個佇列的元素全部轉移後，將剩餘的元素直接插到 result 尾巴，最後再將 result 的內容移回 l1。
接著，q_merge 函式的作用是將一個由多個 queue_context_t 組成的佇列鏈結合併成一個排序好的佇列。首先，不免俗的一樣要確認傳進來的佇列是否有效或只含一個佇列，若只有一個就可以直接返回其大小。
接著，以鏈中的第一個 queue_context_t 為基準，逐一走訪後續所有佇列，並利用前面實作的 merge_two_sorted_queues 函式逐個將其他佇列合併進來，同時累加個佇列的元素數量。
研讀並引入 lib/list_sort.c
在 qtest 提供新的命令 shuffle
Fisher–Yates shuffle 演算法
Commit 65a04fb
演算法流程:
- 先用 q_size 取得 queue 的大小 len。
- 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
- 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。
為了實作演算法並增加命令 shuffle，我們得先去知道該如何新增命令。
我們可以看到在 console.h 中定義好的 API
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
那 ADD_COMMAND 定義好的 add_cmd(#cmd, do_##cmd, msg, param) 又是什麼？
#cmd- 這邊的#代表 Stringification，能使得一個表示式變成字串do_##cmd- 這邊的##代表 concatenation 連結的意思
以實例來看，以這次要新增的函式 shuffle 來說，撰寫以下的程式
ADD_COMMAND(shuffle, "Shuffle the queue randomly", "");
透過以上的巨集，他就會展開成
add_cmd("shuffle", do_shuffle, "Shuffle the queue randomly", "")
所以我們只要去實作出 do_xxx ，並配上 ADD_COMMAND 的部分，就可以實作出我們要的 xxx，並在命令行介面看到我們定義的命令囉！
統計原理來分析實作
透過作業說明所提供的測試程式碼來呈現
結果:
Expectation: 41666
Observation: {'1234': 41623, '1243': 41657, '1324': 41332, '1342': 41533, '1423': 41980, '1432': 41504, '2134': 41220, '2143': 41970, '2314': 41400, '2341': 41845, '2413': 41474, '2431': 41463, '3124': 41709, '3142': 41913, '3214': 42197, '3241': 41460, '3412': 41833, '3421': 41754, '4123': 41857, '4132': 41500, '4213': 41550, '4231': 41897, '4312': 41793, '4321': 41536}
chi square sum: 31.560216963471415
可以看到結果呈現 uniform distribution 的情況。
研讀論文〈Dude, is my code constant time?〉
這篇論文一開始介紹到了 Timing attacks 是一類廣泛的 side-channel attacks。主要是透過測量加密實作的執行時間，來去推斷秘密資訊，比如說金鑰或是密碼。源自於 1996 年 Kocher 首次提出的論文，有關於利用執行時間的數據依賴性來恢復密鑰的方法。
接著，論文指出，理想狀況下，我們希望所有加密程式都能夠在 constant time 內執行，但往往看似 constant time 的程式，實際上卻並非如此，這也引出了我們可能很難去偵測到 timing leaks ，卻會因此造成嚴重後果的論點。
傳統上，為了驗證一個程式是否為 constant time，通常需要手動檢查 assembly code 來去確認程式中沒有根據輸入數據而改變執行路徑或記憶體訪問的部分。然而，這種方式非常耗時，尤其當程式規模變大或是編譯器中的選項改變時，每次都要重複這種工作。
因此，作者提出了一個全新的解決工具 - dudect，這個工具的核心概念是利用統計方法，不依賴傳統的靜態分析，來自動檢測程式的執行時間是否在 constant time 內。
方法: 透過 Timing Leakage Detection 來判斷一段程式是否真正達到了 constant time 的特性，分成了以下三個步驟:
- Measure execution time
- 在這步驟中，工具會反覆測量加密函數在不同輸入下的執行時間。主要分成兩組，一組使用固定的輸入值，另一組則採用隨機輸入，這樣就能夠收集到各自的執行時間分布，同時利用 CPU 的 cycle counters 來確保數據的準確性
- Apply post-processing
- 收集到的原始數據可能會受到環境或外部因素影響，導致出現極端值。因此，在這一步會先對數據做預處理，比如說把那些明顯偏離正常範圍的數據給去除 (Cropping)，又或是進行更高階的預處理。
- Apply stastical test
- 使用統計檢驗來比較兩組數據的分布
釐清 Simulation
參考 I-HSIN Cheng
由於完成上述佇列操作的程式碼實作，所得的分數仍然卡在 95/100 ，因此去確認 trace-17-complexity.cmd 中測試了些什麼。
有看到測試中有寫 option simulation 1 ，但目前還不知道是什麼意思。
我們可以從 qtest.c 中找到有關 simulation 的蹤跡
當 simulation 為 1 時，我們會去執行 is_insert_tail_const()、is_insert_head_const、is_remove_tail_const 或 is_remove_head_const 的函式去判斷這些操作是否為 constant。
解釋 Student's t-distribution 及程式實作的原理
原先確認這篇論文，並沒有提及 Student's t-distribution 的敘述，仔細閱讀作業要求可以從維基百科去摸索
參考 Student's t-distribution，Student's t-test，Welch's t-test，Student’s t-distribution in Statistics
Student's t-distribution 最初是由 William Sealy Gosset (筆名 "Student") 提出，主要用於統計推斷，尤其是在我們希望從一個小樣本來估計母體平均值，或是當母體的標準差未知的情況下，根據樣本數據去計算 t 統計量的分布。換句話說， t-distribution 告訴我們在這些條件下，樣本平均值偏離母體平均值的程度應該如何分布，其尾巴比標準正態分布更厚，以反映額外的不確定性。
Student's t-test 則是一種統計測驗，用來檢驗兩個樣本的平均值之間是否存在統計上顯著的差異
也就是說我們可以把 Student's t-distribution 當作是數學模型，Student's t-test 則是應用這個模型來進行統計推斷的工具
TODO: Ongoing
Welch's t-test
TODO: Ongoing
Welch's t-test 則是在 Student's t-test 的基礎上，放寬了等方差或等變異數的假設
我們可以從 ttest.c 這份檔案中看到 Welch's t-test 的實作
主要有三個函式:
t_push(): 對單筆資料進行歸類，並更新統計輛t_compute(): 進行統計量 (t-value) 的計算，用來衡量兩組平均值是否顯著不同的指標t_init():
改進 percentile 的處理
在論文中 Step 2: Apply post-processing 提到
Typical timing distributions are positively skewed … We discard measurments that are larger than the p percentile …
在這部分，也就是論文中提及的 Cropping，作者建議可以丟棄大於某
oreparaz/dudect (原始碼) 中的 percentile() 和 prepare_percentiles 函式，正是實作這個概念的核心。
percentile() 用來查詢排序後的執行時間陣列中，第
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];
}
prepare_percentiles() 這函式會先將所有的執行時間資料做排序，在以不同的百分比值計算出多個裁減的門檻，目的在於後續統計檢定時，看看在剔除極大值後，是否仍然能觀察到明顯的差異
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
目前還不清楚為什麼是這個公式，但若把 i = 0~100 分別代入，可得到非線性的結果
1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)
以他的實作流程來看，這個公式主要是為每個 i 計算一個對應的百分位值 (threshold)，並存入 ctx->percentiles[i] 中。這些門檻用來裁減執行時間資料，也就是在 update_statistics() 下面這個函式
static void update_statistics(dudect_ctx_t *ctx) {
...
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
...
可以看到對於每個裁減門檻，當差值小於該門檻時，才會將該資料納入統計，這也呼應了論文中的 Cropping。
lab-0 與 原始碼的差別
TODO: Ongoing
我新增了以下這些函式:
static int cmp(const void *a, const void *b);
static int64_t percentile(int64_t *a_sorted, double which, size_t size);
static void prepare_percentiles(int64_t *exec_times);
同時修改了現有的程式碼，使得與實作方式論文的敘述雷同
Commit 65fe951
至此，可看到星之卡比了!!!
開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
我們可以透過在 terminal 輸入以下命令，來開啟 Address Sanitizer
$ make SANITIZER=1
可以透過這個功能去強化執行時期的記憶體檢測，後續執行 make test 沒有遇到錯誤。
Valgrind + 自動測試程式
整合網頁伺服器
解釋 select 系統呼叫
可以從 web.c 和 console.c 的程式碼中看到 select 的身影，但在探討 select 在程式中的用途之前，我們得先去理解他的定義
參閱 select
select() 是一個系統呼叫，其內部實作由作業系統 Kernel 負責處理。當你呼叫 select() 時，Kernel 會根據你所提供的 fd_set 來檢查每個檔案描述符的狀態。
int select(int nfds, fd_set *_Nullable restrict readfds,
fd_set *_Nullable restrict writefds,
fd_set *_Nullable restrict exceptfds,
struct timeval *_Nullable restrict timeout);
可以看到 select 中需要多個參數，參數解釋如下:
int nfds- 此參數指定了待檢查的文件描述符上限，即所有監控的文件描述符最大值加 1。由於文件描述符是從 0 開始計算，因此若最大描述符為 N，則 nfds 應設為 N+1。所以nfds的值fd_set *_Nullable restrict readfdsreadfds指向一個fd_set結構，該集合中包含需要監控讀取的文件描述符。當文件描述符有數據可以讀取時，對應的位會保留在集合中，否則，函式返回後，該位會被清除。_Nullable- 表示readfds可以為 NULLrestrict- 如果不為 NULL，則select()只會通過readfds這個指針來讀取和修改fd_set的內容，不會有其他指針指向相同的記憶體位址。
fd_set *_Nullable restrict writefds-writefds指向一個fd_set結構，該集合中包含需要監控寫入事件的文件描述符。當文件描述符能夠進行寫入 (不會造成阻塞) 時，其位元會保留，反之，在返回後，該位會被清除。fd_set *_Nullable restrict exceptfds-exceptfds指向一個fd_set結構，該集合中包含需要監控異常狀況的文件描述符。當文件描述符發生異常事件時，對應的位會保留，反之，在返回後，該位會被清除。struct timeval *_Nullable restrict timeout- 指向一個struct timeval結構，這個結構會記錄當遇到 blocking waiting 時，他會等待的最大時間，以下做詳細解釋:- 如果超過這個時間後沒有任何事情發生，函式將返回 0。
- 如果在等待期間有事情發生，則函式會在返回前修改
struct timeval結構，並更新成剩餘的等待時間。 - 如果傳入 NULL，則表示無限期等待，直到有文件描述符就緒。
那 fd_set 又是什麼？
fd_set 是一個結構，由 __fd_mask 元素所組成的陣列，陣列大小被定義為 __FD_SETSIZE / __NFDBITS
__FD_SETSIZE- 表示這個集合能夠容納的最大文件描述符數量 (這裡設定為 1024)__NFDBITS- 表示每個__fd_mask變數中能夠儲存的位數，這邊定義為8 * (int) sizeof (__fd_mask)
fd_set 中每一位都代表一個文件描述符，也就是說，我們可以透過 fd_set 來去監控每一個文件描述符的狀況。
可以透過以下 4 種巨集來去操作 fd_set:
FD_SET: 將指定的文件加入到集合中FD_CLR: 從集合中移除指定的文件描述符FD_ISSET: 檢查指定的文件描述符是否在集合中FD_ZERO: 清空整個文件描述符集合
分析 console.c 的實作
先研讀 CSAPP RIO 的套件
RIO 是什麼?
又稱作 Robust I/O
在 lab0-c 中的結構定義如下:
typedef struct __rio {
int fd; /* File descriptor */
int count; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
struct __rio *prev; /* Next element in stack */
} rio_t;
主要設計用來解決 short count 的問題，那什麼是 short count?
意指在進行讀取或寫入的系統呼叫時，實際處理的位元組數量少於請求的數量，這可能會導致資料傳輸不完整或錯誤。
為了應對這個問題， RIO 提供了一組包裝函式 (基於 read，write 系統呼叫去進一步做封裝)，這些函式在發生 short count 時，會自動重試，直到達到要求或是遇到真正的錯誤。
分成兩種類型:
- RIO Unbuffered Input and Output Functions
可以通過調用 rio_readn 和 rio_writen 函式直接在記憶體和檔案之間做傳輸。
#include "csapp.h"
ssize_t rio_readn(int fd, void *usrbuf, size_t n);
ssize_t rio_writen(int fd, void *usrbuf, size_t n);
Returns: number of bytes transferred if OK, 0 on EOF (rio_readn only), −1 on error
- RIO Buffered Input Functions
透過封裝函式 rio_readlineb 來提升讀取文字的效率，避免使用 read() 一次讀取 1 個字元。
console.c 中的實作利用類似 RIO 套件中的 rio_t 結構，將一次性從檔案中讀取的大量資料存放在緩衝區，再從這個緩衝區中逐一取出字元。
其中的 readline() 函式正是利用這個機制來達到高效率的機制。當我們呼叫 readline() 時，它不是每次都直接對檔案呼叫 read()，而是先檢查目前緩衝區內還有沒有剩餘的資料。如果發現資料已經用完，就會自動呼叫 read() 補充一整塊新的資料到緩衝區中，如同下面這段程式碼所示:
/* Need to read from input file */
buf_stack->count = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE);
buf_stack->bufptr = buf_stack->buf;
利用了 RIO 的機制，保證了即使遇到 short count 的情況，資料仍能完整、連續地傳送給使用者。
