2025q1 Homework1 (lab0)
contributed by <JimmyChongz>
作業書寫規範:
- 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
- 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
- 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
- 不要在筆記內加入
[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 字元
安裝 Ubuntu 24.04
在 Windows 11 安裝 Ubuntu 24.04.1 LTS
環境
queue.c 的疑難雜症
q_new
commit: ab7b291
我沒注意記憶體分配失敗的處理。
記憶體配置不能保證成功，而是可能返回 null 指標。若直接使用 malloc 回傳的值而不檢查分配是否成功，則有可能會造成 segmentation fault on the null pointer dereference。
q_free
commit: 1f7493b
怎麼完整 free 掉整個 Linked List 而不會發生 Memory leak ?
使用迴圈來釋放鏈結串列中所有的節點。另外，若 struct 中含有動態配置的記憶體指標，則要先 free 該指標所指向的記憶體空間，再 free 該結構體。還有 head 的結構與節點不同，head 並沒有 element_t 結構，故只需單獨 free。
善用 Linux kernel API q_release_element
commit: 84ee2f1
q_insert
commit: a202b1e
為什麼不能直接 newNode->value = s ？
Ans: 這樣只會讓 newNode->value 指向 s，但不會複製內容，若之後修改 s，那 newNode->value 也會跟著改變。例如：
又或者當 s 被釋放（即 free(s)），而 s 與 newNode->value 都指向同一塊記憶體空間，此時 newNode->value 就會變成 dangling pointer。如果之後程式碼使用 newNode->value，就會出現不可預期的錯誤。
那怎麼解決？
解決方法：使用 strdup 或 strncpy 來賦值給 newNode->value
-
strdup(s) :
複製傳入參數 s 指向的字串到一塊新的記憶體空間。意思就是說此函數會先 malloc s 指向字串的 size，再透過 memcpy 將 s 指向的字串複製到先前 malloc 的記憶體空間。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
-
strncpy(str1, str2, n) :
將 str2 的前 n 個字元複製到 str1 中。要注意預留一個 byte 的空間給 null character。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
那 strdup 跟 strncpy 用哪個會比較好？
strdup 比較好，因為 strdup 會自動分配記憶體，而 strncpy 只是單純複製字串，但仍然需要手動分配記憶體，例如：
q_remove
commit: a202b1e
為什麼參數有 char *sp 跟 size_t bufsize ?
-
sp 是一個指向字串緩衝區的指標，若不為 NULL，則函式應將被移除元素之成員 (即 node->value) 複製到這個字串緩衝區。
用途： 讓使用者可以立刻取得移除節點所儲存的字串，而不需透過訪問回傳的 element_t 結構體取得。
如果 sp == NULL： 代表 呼叫者 不需要移除節點所儲存的字串，只需要刪除節點並回傳該元素的指標。
-
bufsize 是 sp 的最大可用空間（包含 \0 ），避免 緩衝區溢位（buffer overflow）。
用途： 確保 strncpy() 不會超過 sp 的範圍，並手動添加 \0 來確保字串結尾安全。
q_delete_mid
commit: a8f4303
基於下方的程式碼 deleteMiddle 還有沒有更好的寫法？
利用「快慢指標」，讓 fast 指標以兩倍速在走訪整個鏈結串列，slow 則以一倍速走訪鏈結串列，當 fast 完成走訪整個鏈結串列時，slow 指標剛好會停在中間的位置。例如：
q_delete_dup
commit: a8f4303
思路：用巢狀迴圈，外層迴圈用於檢測兩兩節點的值是否相同，若相同則進入第二層迴圈，在第二層迴圈中刪除重複的節點。
還有改進空間嗎？
用 Hash Table …
q_swap
commit: 244dc15
思路：利用 list_for_each(cur, head) 去走訪整個鏈結串列，再透過 list_move(cur, cur->next)，由此一來每一輪的 cur->next 都會被插入到 cur 前面，又執行完 list_move 後，cur 無形中會自動跑到下一個節點，如下圖所示：
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
依照上述做法會出現問題，當鏈結串列長度為奇數時，會多換一次，導致最後一個節點被移到最前面，怎麼解決？
多加一個判斷式，當 cur->next == head 時，就 break迴圈，避免發生交換即可。
commit: 8904527
當完成 q_reverseK 時，即可將 q_swap 寫成：
q_reverse
commit: 244dc15
作法：利用 list_for_each_safe(cur, next, head) 去走訪整個鏈結串列，再透過 list_move(cur, head) 將每一個點都重新插入 head，即可完成 reverse 操作。
q_reverseK
commit: fcd4d2c
作法：先得出鏈結串列的長度 count，當 count 大於 K 時，準備 prev 跟 next 兩個輔助指標做 Reverse K-group，做完後要 count -= k。
q_descend
commit: 13ffad8
有更好的做法，怎麼做？
我最一開始的思路是先找出串列中的最大值 max，再利用遞迴找出 max->next 子串列的最大值回傳給 max->next，如下程式碼所示，但會 Time out 時間複雜度為 等級。
用兩個指標來進行反向走訪：
max：追蹤目前反向走訪過程中遇到的最大值節點（初始指向 head->prev，即尾部節點）。cur：負責走訪 max 前方的節點（初始指向 max->prev ）。
走訪過程：
- 如果
cur 所指的值小於或等於 max，則刪除該節點。
- 如果
cur 所指的值大於 max，則更新 max 為 cur，確保 max 始終指向目前反向走訪過程中遇到的最大值。
- 移動
cur 到 prev，繼續走訪。
如此一來就可以有效地保留遞減序列的節點，並刪除不符合條件的節點。
q_ascend
commit: 13ffad8
作法與 q_descend 相似，一樣是透過反向走訪的思路，差別在走訪過程的條件，q_ascend 要刪除大於等於 min 的值，若 cur 所指的值小於 min，則更新 min 為 cur，以確保 min 始終指向目前反向走訪過程中遇到的最小值。如此一來就可以有效地 保留遞增序列的節點，並刪除不符合條件的節點。
q_sort
commit: e5f1033
我原先參考了 第二周測驗一 的 list_quicksort 實作，我將其轉換成 Linux kernel 風格的鏈結串列：
使用 quick sort 為什麼會超時？
因為在 Worst Case 的情況下，Quick Sort 的時間複雜度會來到 等級。例如在全部節點值都相同的情況下，使用 Singely-Linked-List 示意：
令 表示傳入的串列長度，第一個節點當作 pivot
再將剩餘的 個節點做分割，比 pivot 小的節點插入到 list_less 串列中，反之則插入 list_greater 串列中。在此例中，當執行完 list_for_each_entry_safe 迴圈後，並無法分割串列，因為全部的節點都相同，因此都會被插入到 list_greater 中，還是得到長度為 的子串列。
再遞迴呼叫 q_sort，所以都是透過設 pivot 在做分割串列，每回合只切一個節點，由此可推得時間函數式為 ，其中 為常數， 表示執行 list_for_each_entry_safe 迴圈的時間，經化簡後得
故無法滿足時間複雜度 的要求。
如何優化？
改用 Merge Sort ，因為不管在什麼情況下，時間複雜度皆為 等級。
參考 Linked List Sort 之 Merge Sort
這樣寫 Merge Sort，會出現 Segmentation Fault，是什麼問題？
使用 Valgrind 分析，執行以下命令：
發現是 Stack Overflow ，看起來是第 248 列的遞迴沒寫好。
先用簡單的例子來追蹤程式碼：
在執行完 while loop 後：
TODO: Explain how list_cut_position(&left, head, slow) exactly do …
將 head 到 slow (包含 slow) 的節點接到 left 上，若 left 不為空的話，則會將其原本的節點都覆蓋過去，即原本節點都會被 "Remove"（不會被釋放）。
在執行完 list_cut_position(&left, head, slow); 後：
此時，再執行 q_sort(&left, descend); 時，會發現 left 就是原本的 head，根本沒切到，導致無限遞迴，造成 Stack Overflow !
修正：
把 list_cut_position(&left, head, slow); 修改即可。
接著，Merge Sort 會用到 merge_two_lists 輔助函數，用來合併由 q_sort 函數切割成兩半的子串列，比較特別的是要「 做 ascending / descending 的判斷 」。其中，為了要確保是 Stable Sorting，因此當遇到重複的數字時應保持原排列順序，以 ascending 為例，當目前左半子串列的值小於等於當前右半子串列的值時，應優先合併左半子串列的值。
q_merge
commit: 3e931f4
先了解 queue_contex_t 結構體定義：
思路：首先，新增一個指標指向第一條 queue，作為合併的目標。接下來，將其餘所有 queue 依序合併到第一條 queue 中。我使用 list_for_each_entry_safe 走訪從第二條開始的每一條 queue，並透過 merge_two_lists 將當前走訪到的 queue 合併至第一條 queue。同時，需即時更新第一條 queue 的 size。當所有 queue 都合併完成後，回傳第一條 queue 的最終 size。
如何驗證 queue.c 實作的 method？
在終端機輸入 make test 後，會發生什麼？
執行 scripts/driver.py 這個 Python 程式。快速瀏覽發現這個自動評分程式就是將 traces/trace-XX-CAT.cmd 這樣形式的命令序列提供給 qtest.c 內的命令直譯器，然後依據給定的檢驗標準，逐一判定該給測試者多少分數。
整合網頁伺服器
File descriptor (fd)
Reference 1
Reference 2
File Descriptor 是一個非負整數，代表 File Descriptor Table 中的一個 entry 的索引。File Descriptor Table 是儲存在 PCB （即 Linux 中的 task_struct）中的一個資料結構，用來記錄程序所開啟檔案的相關資訊。每個 entry 會指向一個 Open File Table 的項目，該表中包含與檔案操作有關的詳細資料，例如檔案的偏移量、開啟模式等。Open File Table 中的每個項目則會對應到一個 i-node（Linux 檔案系統中的資料結構），而 i-node 中則紀錄了檔案的屬性資訊，例如檔案的路徑、大小、權限等。可以使用以下的 function 來查看當前 process 的 File Descriptor Table：
查看建立 socket 前跟後 FD Table 的差異，以及當有新的 client 連進來後的差異：
完整測試程式碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <errno.h>
#include <sys/select.h>
#include <dirent.h>
#include <sys/stat.h>
#define SERVER_PORT 1234
#define BUF_SIZE 1024
#define MAX_CLIENTS 100
void list_open_fds() {
char path[512];
snprintf(path, sizeof(path), "/proc/%d/fd", getpid());
DIR *dir = opendir(path);
if (!dir) {
perror("opendir");
return;
}
struct dirent *entry;
printf("Open file descriptors for process %d:\n", getpid());
printf("FD\tType\t\tTarget\n");
printf("---------------------------------------------\n");
while ((entry = readdir(dir)) != NULL) {
if (entry->d_name[0] == '.') continue;
char fd_path[512], target_path[512];
int written = snprintf(fd_path, sizeof(fd_path), "/proc/%d/fd/%s", getpid(), entry->d_name);
if (written < 0 || written >= sizeof(fd_path)) {
fprintf(stderr, "Path truncated: %s\n", entry->d_name);
continue;
}
ssize_t len = readlink(fd_path, target_path, sizeof(target_path) - 1);
if (len != -1) {
target_path[len] = '\0';
} else {
snprintf(target_path, sizeof(target_path), "Unknown");
}
struct stat statbuf;
if (stat(fd_path, &statbuf) == 0) {
char *type;
if (S_ISREG(statbuf.st_mode)) {
type = "Regular File";
} else if (S_ISDIR(statbuf.st_mode)) {
type = "Directory";
} else if (S_ISCHR(statbuf.st_mode)) {
type = "Character Device";
} else if (S_ISBLK(statbuf.st_mode)) {
type = "Block Device";
} else if (S_ISFIFO(statbuf.st_mode)) {
type = "FIFO (Pipe)";
} else if (S_ISSOCK(statbuf.st_mode)) {
type = "Socket";
} else {
type = "Unknown";
}
printf("%s\t%-15s\t%s\n", entry->d_name, type, target_path);
} else {
printf("%s\tUnknown\t\t%s\n", entry->d_name, target_path);
}
}
closedir(dir);
}
typedef struct {
int client_fd;
char client_ip[INET_ADDRSTRLEN];
int client_port;
} client_info_t;
int main() {
list_open_fds();
int server_fd;
if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
perror("Socket creation failed");
return -1;
}
list_open_fds();
int opt = 1;
if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt)) != 0) {
perror("Error setting SO_REUSEADDR on socket");
close(server_fd);
return -1;
}
struct sockaddr_in server_addr;
memset(&server_addr, 0, sizeof(server_addr));
server_addr.sin_family = AF_INET;
server_addr.sin_port = htons(SERVER_PORT);
server_addr.sin_addr.s_addr = htonl(INADDR_ANY);
if (bind(server_fd, (struct sockaddr*)&server_addr, sizeof(server_addr)) < 0) {
perror("Bind failed");
close(server_fd);
return -1;
}
if (listen(server_fd, SOMAXCONN) < 0) {
perror("Listen failed");
close(server_fd);
return -1;
}
printf("伺服器已啟動，等待連接...\n");
client_info_t clients[MAX_CLIENTS];
for (int i = 0; i < MAX_CLIENTS; i++) {
clients[i].client_fd = -1;
}
fd_set read_fds;
int max_fd = server_fd;
while (1) {
FD_ZERO(&read_fds);
FD_SET(server_fd, &read_fds);
for (int i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].client_fd != -1) {
FD_SET(clients[i].client_fd, &read_fds);
if (clients[i].client_fd > max_fd) {
max_fd = clients[i].client_fd;
}
}
}
if (select(max_fd + 1, &read_fds, NULL, NULL, NULL) < 0) {
perror("Select failed");
continue;
}
if (FD_ISSET(server_fd, &read_fds)) {
struct sockaddr_in client_addr;
socklen_t client_len = sizeof(client_addr);
int client_fd = accept(server_fd, (struct sockaddr*)&client_addr, &client_len);
if (client_fd < 0) {
perror("Accept failed");
continue;
}
char client_ip[INET_ADDRSTRLEN];
inet_ntop(AF_INET, &client_addr.sin_addr, client_ip, INET_ADDRSTRLEN);
int client_port = ntohs(client_addr.sin_port);
printf("客戶端 %s:%d 已連接\n", client_ip, client_port);
list_open_fds();
int i;
for (i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].client_fd == -1) {
clients[i].client_fd = client_fd;
strncpy(clients[i].client_ip, client_ip, INET_ADDRSTRLEN);
clients[i].client_port = client_port;
break;
}
}
if (i == MAX_CLIENTS) {
printf("太多客戶端，拒絕連接\n");
close(client_fd);
} else if (client_fd > max_fd) {
max_fd = client_fd;
}
}
for (int i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].client_fd != -1 && FD_ISSET(clients[i].client_fd, &read_fds)) {
char buffer[BUF_SIZE];
ssize_t bytes_received = recv(clients[i].client_fd, buffer, BUF_SIZE - 1, 0);
if (bytes_received <= 0) {
if (bytes_received < 0) {
perror("Connection error");
} else {
printf("客戶端 %s:%d 已斷開連線\n", clients[i].client_ip, clients[i].client_port);
}
close(clients[i].client_fd);
clients[i].client_fd = -1;
continue;
}
buffer[bytes_received] = '\0';
printf("收到來自 %s:%d 的訊息: %s\n", clients[i].client_ip, clients[i].client_port, buffer);
if (send(clients[i].client_fd, buffer, bytes_received, 0) < 0) {
perror("Connection error");
close(clients[i].client_fd);
clients[i].client_fd = -1;
continue;
}
printf("訊息已送出...\n");
}
}
}
close(server_fd);
printf("伺服器關閉\n");
return 0;
}
預期輸出
select system call
Manual page
運作原理：
例如：使用 accept() 系統呼叫得到一個 socket_fd 假設是 4，那麼因為 socket_fd 是要接收客戶端的訊息，所以 readfds 的第 4 個 bit 就設為 1，也就是告訴 select() 幫我監聽這個 fd 是否可讀，若沒有 client 連線，則 select() 會 block 程式，直到有 fd 就緒可讀或 Timeout。另外，當 select() return 後，會將 readfds 中除了可讀 fd bit 之外的所有 bit 清 0。此外 fd_set 的 size 由 nfds 記錄，表示目前共監聽幾個 file descriptors，而監聽的上限則由巨集 FD_SETSIZE 限制。另外，我透過以下方式來查看 fd_set 的狀態：
接著，寫程式來實驗看看 Select：
server 完整測試程式碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <errno.h>
#include <sys/select.h>
#define SERVER_PORT 1234
#define BUF_SIZE 1024
#define MAX_CLIENTS 100
void print_fd_set(fd_set *fds, int max_fd) {
printf("fd_set contents (up to %d):\n", max_fd);
for (int i = 0; i <= max_fd; i++) {
if (FD_ISSET(i, fds)) {
printf("fd %d: 1, ", i);
} else {
printf("fd %d: 0, ", i);
}
}
puts("");
printf("-----------------------------------------------------------------\n");
}
typedef struct {
int fd;
char ip[INET_ADDRSTRLEN];
int port;
} client_info_t;
int main() {
int server_fd;
if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
perror("Socket creation failed");
return -1;
}
int opt = 1;
if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt)) != 0) {
perror("Error setting SO_REUSEADDR on socket");
close(server_fd);
return -1;
}
struct sockaddr_in server_addr;
memset(&server_addr, 0, sizeof(server_addr));
server_addr.sin_family = AF_INET;
server_addr.sin_port = htons(SERVER_PORT);
server_addr.sin_addr.s_addr = htonl(INADDR_ANY);
if (bind(server_fd, (struct sockaddr*)&server_addr, sizeof(server_addr)) < 0) {
perror("Bind failed");
close(server_fd);
return -1;
}
if (listen(server_fd, SOMAXCONN) < 0) {
perror("Listen failed");
close(server_fd);
return -1;
}
printf("伺服器已啟動，等待連接...\n");
client_info_t clients[MAX_CLIENTS];
for (int i = 0; i < MAX_CLIENTS; i++) {
clients[i].fd = -1;
}
fd_set read_fds;
int max_fd = server_fd;
printf("Init read_fds:\n");
print_fd_set(&read_fds, max_fd);
while (1) {
FD_ZERO(&read_fds);
printf("After execute FD_ZERO:\n");
print_fd_set(&read_fds, max_fd);
FD_SET(server_fd, &read_fds);
printf("After execute FD_SET with server_fd:\n");
print_fd_set(&read_fds, max_fd);
for (int i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].fd != -1) {
FD_SET(clients[i].fd, &read_fds);
if (clients[i].fd > max_fd) {
max_fd = clients[i].fd;
}
}
}
printf("After execute FD_SET with client_fd:\n");
print_fd_set(&read_fds, max_fd);
if (select(max_fd + 1, &read_fds, NULL, NULL, NULL) < 0) {
perror("Select failed");
continue;
}
printf("After call select:\n");
print_fd_set(&read_fds, max_fd);
if (FD_ISSET(server_fd, &read_fds)) {
struct sockaddr_in client_addr;
socklen_t client_len = sizeof(client_addr);
int client_fd = accept(server_fd, (struct sockaddr*)&client_addr, &client_len);
if (client_fd < 0) {
perror("Accept failed");
continue;
}
printf("After accept client connection:\n");
print_fd_set(&read_fds, max_fd);
char client_ip[INET_ADDRSTRLEN];
inet_ntop(AF_INET, &client_addr.sin_addr, client_ip, INET_ADDRSTRLEN);
int client_port = ntohs(client_addr.sin_port);
printf("客戶端 %s:%d 已連接\n", client_ip, client_port);
int i;
for (i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].fd == -1) {
clients[i].fd = client_fd;
strncpy(clients[i].ip, client_ip, INET_ADDRSTRLEN);
clients[i].port = client_port;
break;
}
}
if (i == MAX_CLIENTS) {
printf("太多客戶端，拒絕連接\n");
close(client_fd);
} else if (client_fd > max_fd) {
max_fd = client_fd;
}
}
for (int i = 0; i < MAX_CLIENTS; i++) {
if (clients[i].fd != -1 && FD_ISSET(clients[i].fd, &read_fds)) {
char buffer[BUF_SIZE];
ssize_t bytes_received = recv(clients[i].fd, buffer, BUF_SIZE - 1, 0);
if (bytes_received <= 0) {
if (bytes_received < 0) {
perror("Connection error");
} else {
printf("客戶端 %s:%d 已斷開連線\n", clients[i].ip, clients[i].port);
}
close(clients[i].fd);
clients[i].fd = -1;
continue;
}
buffer[bytes_received] = '\0';
printf("收到來自 %s:%d 的訊息: %s\n", clients[i].ip, clients[i].port, buffer);
if (send(clients[i].fd, buffer, bytes_received, 0) < 0) {
perror("Connection error");
close(clients[i].fd);
clients[i].fd = -1;
continue;
}
printf("訊息已送出...\n");
print_fd_set(&read_fds, max_fd);
}
}
}
close(server_fd);
printf("伺服器關閉\n");
return 0;
}
client 完整測試程式碼
預期輸出：
- 在尚未有客戶端連線時，可以看到
read_fds 中 fd 3 被設為 1，而程式 block 在 select()，因為還尚未有 fd 可讀。
為什麼在尚未有客戶端連線時，server_fd 是不可讀的？
server_fd 是監聽狀態的 socket，因此，在當有新的 client 執行 connect() 後，也就是有一個 connection 在等待被 accept() 時，監聽 socket 才可讀。
- 在當有客戶端連線時，可以發現多了以下的輸出內容，首先是 select 發現
fd 3 可讀了（因為有新的連線），當新的連線進來後，因為新連線的 fd 值會大於 max_fd，因此需將 max_fd 更新為最新連線的 fd，接著就重複程式中迴圈的流程（參考上述 server 完整測試程式碼）。
註：由於 select 能監視的 file descriptor 有限（被巨集 FD_SETSIZE 限制，通常為 1024），故現在需支援大量服務的系統不再使用，改用 poll(2) 或 epoll(7) 替代。
shuffle 實作
q_shuffle
commit: 484b7ea
參考 你所不知道的 C 語言：Fisher–Yates shuffle 演算法實作，透過 Pencil-and-paper method 對 Linux Kernel 的環狀雙向鏈結串列進行隨機洗牌，每次隨機選取一個節點並將其移動到 new 串列，直到所有節點都被移動。
do_shuffle
commit: 484b7ea
在 qtest.c 中新增 do_shuffle 函數，參考 do_swap 寫法，將 q_swap(current->q); 改成 q_shuffle(current->q);。詳細流程我還要弄清楚。
透過統計方法驗證 shuffle，利用作業提供的測試檔測試，結果如下：
測試出來不太均勻，需要調整。
解決方法
commit: e28bbdd
後來，我發現是程式碼中使用 srand(time(NULL)) 的問題，因為這個函數會根據時間（1970 年 1 月 1 日到現在的秒數）初始化亂數種子，由於 time(NULL) 的精度只有秒，當在短時間內重複呼叫 q_shuffle() 時，其中的 srand(time(NULL)) 會產生相同的亂數種子，導致每次產生的亂數「序列」相同。
驗證：在短時間內重複呼叫 srand(time(NULL)) 會產生相同的亂數種子，且每次產生的亂數「序列」相同。
完整驗證程式碼
預期輸出（亂數種子相同、序列相同）
因此，當在執行 test_shuffle.py 時，在 1,000,000 次的洗牌中，會有部分的洗牌順序相同，導致不均勻洗牌。
再次測試：
可以發現，1234 的各種排列組合出現的次數皆為四萬多次，均勻多了。
參考作業提供的 論文重點提示
從引言的敘述中，推測 Timing Leakage 指的是程式執行時間與秘密數據之間的關聯性，導致攻擊者可以透過測量加密實作的執行時間來推測出機密資訊，例如：在 1996 年 Paul Kocher 發現 RSA 私鑰解密的運算執行時間取決於私鑰位元值，所以攻擊者就可以透過測量解密運算的執行時間來逐步恢復私鑰。這也是為什麼要探討 is my code constant time 的重要原因，以確保程式碼在不同輸入條件下的執行時間是固定的，以減少被 side-channel attacks 的可能性。
commit: 42af940
lab0-c 中的 Welch's test 測試項目
參考 課程作業：Welch’s t-test
用 GBD backtrace test_constant:
Macro 中的 ## 是什麼？
參考規格書對 ## operator 的敘述：
得知 ## 是在巨集中的「token 連接符號」，在 C 的預處理器中，## 可以將兩個 token 合併成一個 token，當參數為空時，C 預處理器會插入 placemarker，它最終會被刪除，不會影響程式碼的執行結果，例如：
課程問答
在 ASCII code 中，為什麼 Z 後並沒有馬上接 a？
如何使用 bitwise 的方式，實現字串不區分大小寫比對？
- hint: a 與 A ascii code 相差 32
HackMD