# 2025q1 Homework1 (lab0)
contributed by < `Jordymalone` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
#### Reviewed by `salmoniscute`
**1. `q_reversek`**
```c
if (!list_empty(head)) {
list_splice_tail_init(head, &result);
}
list_splice_tail_init(&result, head);
```
這段程式碼有點冗長，可以直接透過 `list_splice` 將剩下的節點加到結果的頭部。
**2. `merge_two_lists`、`merge_two_sorted_queues`**
在函式的開頭和結尾都有以下檢查：
```c
if (list_empty(l1)) {
list_splice_tail_init(l2, head);
return;
}
if (list_empty(l2)) {
list_splice_tail_init(l1, head);
return;
}
```
但其實不用檢查到兩次，因為照你目前的寫法，既然兩個鏈結串列其中有一個是空的，他就不會進去迴圈。所以開頭的檢查可以省略讓程式碼看起來更簡潔。
**3. `q_ascend` 、 `q_descend`**
>一開始在撰寫 leetcode ，思路很直接，我是直接寫個 reverseList() 把鏈結串列的頭尾顛倒後，原本右側的節點就會跑到左側，這個反轉的用途是有巧思的!
我想對這段話提出疑問：既然是對雙向且環狀的鏈結串列進行操作，可以運用到 prev 指標，為何不直接從尾巴向前逐一走訪即可？
這樣就不用 reverse 兩次。
## 開發環境
```shell
$ 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](https://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)，同時為了後續寫這份作業更順利，也參考了 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 來理解 Linux 核心原始程式碼風格。
### 常用結構體
**queue 結構**
```c
/* 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](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
### `q_new`
**定義: 建立新的「空」佇列**
> Commit [9742ac4](https://github.com/Jordymalone/lab0-c/commit/9742ac4b3146891add62df942c1273849e078448)
單純建立一個新的 `head` 節點，並分配記憶體空間給他，養成一個好習慣在每次 `malloc` 之後都要檢查是否有 `malloc` 成功，最後再對他做初始化，因為是雙向鏈結串列，要把 `head` 的 `prev` 和 `next` 指標都先指向自己。
```c
/* 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](https://github.com/Jordymalone/lab0-c/commit/1e89cddbe408d65df30f1b6ecb6fdb835b0877e5)
撰寫時，我在想每當我指到一個節點時，我用 `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](https://github.com/Jordymalone/lab0-c/commit/5afea2db95e148c79e2819b4f4e91c9a6f3a4704)
研讀 [Intrusive linked lists](https://www.data-structures-in-practice.com/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 !!!
```c
/* 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` 時遇到的問題
```shell
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...
```
> 參閱 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
上述文件內容表示若使用 `strcpy` 不當，很有可能因為沒去確認 buffer length，而導致將超出這個區域的數據去覆蓋到相鄰的記憶體區域。
因此，將 `strcpy` 改用 `strncpy`，同時在 `malloc` 之後去確認是否有成功 allocate memory 給 `new_element->value`，若沒有就釋放。
```diff -u
/* 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` 的問題，一併修改。
```diff -u
/* 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](https://github.com/Jordymalone/lab0-c/commit/3319d8ef3d4207343ee53ec30e738cd87e0db4dc)
`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 的意思
```c
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;
}
```
目前的這個寫法可以成功把節點從頭移掉，但會有下面這問題
```shell
l = [3 2 1]
cmd> rh
ERROR: Failed to store removed value
Removed from queue
l = [2 1]
```
看起來是我的 `strdup` 用錯方式了，同時我的 if 條件式也在亂寫，因此重新寫
> TODO: 釐清 `strdup` 與 `strncpy`
**修改**
```c
/* 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](https://github.com/Jordymalone/lab0-c/commit/3319d8ef3d4207343ee53ec30e738cd87e0db4dc)
實作流程與 `q_remove_head` 類似，差別只在於這邊要 remove 佇列中尾巴的節點。
### `q_size`
**定義: 計算目前佇列的節點總量**
> Commit [c4ed8b8](https://github.com/Jordymalone/lab0-c/commit/c4ed8b8d92480bb90433b04bdb9150ee01b20603)
實作想法，定義一個新的指標，從 `head->next` 開始往後計算，直到繞一圈回到 `head` 為止，這時候就可以用到 `list_for_each` 由 `define` 所定義的 marco function 來去 iterate 整條 circular doubly-linked list。
### `q_delete_mid`
**定義: 將佇列中位於中間的節點刪除**
> Commit [b380c09](https://github.com/Jordymalone/lab0-c/commit/b380c098c1c066799ca0106ef2c654d7d946145b)
> 詳見 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/)
實作之前，先去撰寫 leetcode，我使用的是 Two Pointers 來去寫這題，同理套用到 `q_delete_mid` 上。
**原始寫法**
```c=
/* 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` 測試發現
```shell
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 的問題。
**調整後**
```diff -u
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](https://github.com/sysprog21/lab0-c/commit/ceca2debb1578beebadd4b7c693ff1dfd929d6a2)
> 詳見 [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)
寫完 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](https://github.com/Jordymalone/lab0-c/commit/e91a25c8c7c877bf328b2ab5131586e1cdc68256)
> 詳見 [24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/)
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](https://github.com/sysprog21/lab0-c/commit/e5beef77f89774cf4e61fec7af8b6dbfc40cb031)
> 參考 [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/)
首先，我們宣告三個指標:
* `current`: 代表當前待調整的節點
* `front`: 指向 `current->next` 的位置
* `last`: 指向 `current->prev` 的位置
我們從鏈結串列的 `head` 節點開始，初始時設定 `front = head->prev` 與 `last = head->next`，然後交換 `head` 節點中的 `next` 與 `prev` 指標。依照這順序對每一個節點進行指標反轉操作，最終即可得到一個順序完全反轉的鏈結串列。
### `q_reverseK`
**定義: 類似 `q_reverse`，但每次反轉鏈結串列的 k 個節點**
> Commit [b3b452d](https://github.com/sysprog21/lab0-c/commit/b3b452dcf20adca5f7a79250109d27df28ebb968)
> 詳見 [25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)
參考[第二週問答簡記](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view#Cheng5840)的討論，給了我一點啟發。
函式實作上，我運用到了多個 `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](https://github.com/sysprog21/lab0-c/commit/a0878e7687f592b6e84050e159b91ce42668c714)
> 參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 來得知實作手法
> 參考 [ItisCaleb](https://hackmd.io/@ItisCaleb/linux2023-lab0#q_sort)
參考上述內容，我選擇使用 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](https://github.com/sysprog21/lab0-c/commit/f8ea3d0751f3908664b0349a77b409061eca647c)
> 詳見 [2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)
**疑問**:
去確認 `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](https://github.com/sysprog21/lab0-c/commit/f8ea3d0751f3908664b0349a77b409061eca647c)
實作概念同 `q_ascend`，只差在一個是大於一個是小於。
### `q_merge`
**定義: 合併所有已排序的佇列，並合而為一個新的已排序佇列**
> Commit [5737c39](https://github.com/sysprog21/lab0-c/commit/5737c39c7e19aedc585778801f2804d20f2d25cc)
在正式實作這個函式之前，需要先去理解 `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
> 參考 [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh)
## 在 qtest 提供新的命令 `shuffle`
### Fisher–Yates shuffle 演算法
> 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Fisher%E2%80%93Yates-shuffle)
> Commit [65a04fb](https://github.com/Jordymalone/lab0-c/commit/65a04fba362c6e62f2bcc4828dc60611c414729e)
演算法流程:
1. 先用 q_size 取得 queue 的大小 len。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。
為了實作演算法並增加命令 `shuffle`，我們得先去知道該如何新增命令。
我們可以看到在 `console.h` 中定義好的 API
```c
/* 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 來說，撰寫以下的程式
```c
ADD_COMMAND(shuffle, "Shuffle the queue randomly", "");
```
透過以上的巨集，他就會展開成
```c
add_cmd("shuffle", do_shuffle, "Shuffle the queue randomly", "")
```
所以我們只要去實作出 `do_xxx` ，並配上 `ADD_COMMAND` 的部分，就可以實作出我們要的 xxx，並在命令行介面看到我們定義的命令囉！
### 統計原理來分析實作
透過[作業說明](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)所提供的測試程式碼來呈現
**結果**:
```shell
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 的特性，分成了以下三個步驟:
1. Measure execution time
* 在這步驟中，工具會反覆測量加密函數在不同輸入下的執行時間。主要分成兩組，一組使用固定的輸入值，另一組則採用隨機輸入，這樣就能夠收集到各自的執行時間分布，同時利用 CPU 的 cycle counters 來確保數據的準確性
2. Apply post-processing
* 收集到的原始數據可能會受到環境或外部因素影響，導致出現極端值。因此，在這一步會先對數據做預處理，比如說把那些明顯偏離正常範圍的數據給去除 (Cropping)，又或是進行更高階的預處理。
3. Apply stastical test
* 使用統計檢驗來比較兩組數據的分布
### 釐清 Simulation
> 參考 [I-HSIN Cheng](https://hackmd.io/@vax-r/linux2024-homework1#%E8%A7%A3%E9%87%8B-simulation-%E5%81%9A%E6%B3%95)
由於完成上述佇列操作的程式碼實作，所得的分數仍然卡在 `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 的敘述，仔細閱讀[作業要求](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#computer-%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89%E9%87%8D%E9%BB%9E%E6%8F%90%E7%A4%BA)可以從維基百科去摸索
> 參考 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)，[Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test#Assumptions)，[Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)，[Student’s t-distribution in Statistics](https://www.geeksforgeeks.org/students-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，作者建議可以丟棄大於某 $p$ % 百分位值的量測，目的在於排除雜訊太大的量測結果，讓統計檢定能更容易看出是否真的有時間分佈的差異。
[oreparaz/dudect](https://github.com/oreparaz/dudect) (原始碼) 中的 `percentile()` 和 `prepare_percentiles` 函式，正是實作這個概念的核心。
`percentile()` 用來查詢排序後的執行時間陣列中，第 $p$ % 百分位位置的數值。也就是說，這個函式能夠回傳第 $p$ % 百分位的執行時間。
```c
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()` 這函式會先將所有的執行時間資料做排序，在以不同的百分比值計算出多個裁減的門檻，目的在於後續統計檢定時，看看在剔除極大值後，是否仍然能觀察到明顯的差異
```c
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 分別代入，可得到非線性的結果
```c
1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)
```
以他的實作流程來看，這個公式主要是為每個 i 計算一個對應的百分位值 (threshold)，並存入 `ctx->percentiles[i]` 中。這些門檻用來裁減執行時間資料，也就是在 `update_statistics()` 下面這個函式
```c
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
我新增了以下這些函式:
```c
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](https://github.com/sysprog21/lab0-c/commit/65fe951767ab6972b3e8d841c6f1c1bce7602eee)
至此，可看到星之卡比了!!!
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
我們可以透過在 terminal 輸入以下命令，來開啟 Address Sanitizer
```shell
$ make SANITIZER=1
```
可以透過這個功能去強化執行時期的記憶體檢測，後續執行 `make test` 沒有遇到錯誤。
## Valgrind + 自動測試程式
## 整合網頁伺服器
### 解釋 select 系統呼叫
可以從 `web.c` 和 `console.c` 的程式碼中看到 select 的身影，但在探討 select 在程式中的用途之前，我們得先去理解他的定義
> 參閱 [select](https://man7.org/linux/man-pages/man2/select.2.html)
`select()` 是一個系統呼叫，其內部實作由作業系統 Kernel 負責處理。當你呼叫 `select()` 時，Kernel 會根據你所提供的 `fd_set` 來檢查每個檔案描述符的狀態。
```c
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 readfds`
* `readfds` 指向一個 `fd_set` 結構，該集合中包含需要監控讀取的文件描述符。當文件描述符有數據可以讀取時，對應的位會保留在集合中，否則，函式返回後，該位會被清除。
* `_Nullable` - 表示 `readfds` 可以為 NULL
* `restrict` - 如果不為 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 中的結構定義如下:
```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 時，會自動重試，直到達到要求或是遇到真正的錯誤。
分成兩種類型:
1. RIO Unbuffered Input and Output Functions
可以通過調用 `rio_readn` 和 `rio_writen` 函式直接在記憶體和檔案之間做傳輸。
```c
#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
```
2. RIO Buffered Input Functions
透過封裝函式 `rio_readlineb` 來提升讀取文字的效率，避免使用 `read()` 一次讀取 1 個字元。
console.c 中的實作利用類似 RIO 套件中的 `rio_t` 結構，將一次性從檔案中讀取的大量資料存放在緩衝區，再從這個緩衝區中逐一取出字元。
其中的 `readline()` 函式正是利用這個機制來達到高效率的機制。當我們呼叫 `readline()` 時，它不是每次都直接對檔案呼叫 `read()`，而是先檢查目前緩衝區內還有沒有剩餘的資料。如果發現資料已經用完，就會自動呼叫 `read()` 補充一整塊新的資料到緩衝區中，如同下面這段程式碼所示:
```c
/* 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 的情況，資料仍能完整、連續地傳送給使用者。
Sign in with Wallet
Connect another wallet