# 2025q1 Homework1 (lab0)
contributed by <[JimmyChongz](https://github.com/JimmyChongz)>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 安裝 Ubuntu 24.04
[在 Windows 11 安裝 Ubuntu 24.04.1 LTS](https://hackmd.io/@Jimmy-Xu/SkAXnK7LJx)
## 環境
```bash
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 24.04.2 LTS
Release: 24.04
Codename: noble
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
```
## queue.c 的疑難雜症
### q_new
> commit: [ab7b291](https://github.com/sysprog21/lab0-c/commit/ab7b291b65738ade55561cbd638d73ac36378d02)
#### 我沒注意記憶體分配失敗的處理。
記憶體配置不能保證成功，而是可能返回 null 指標。若直接使用 malloc 回傳的值而不檢查分配是否成功，則有可能會造成 segmentation fault on the null pointer dereference。
### q_free
> commit: [1f7493b](https://github.com/sysprog21/lab0-c/commit/1f7493b5451b8462a81e44668a6a608ca2c1539c)
#### 怎麼完整 free 掉整個 Linked List 而不會發生 Memory leak ?
使用迴圈來釋放鏈結串列中所有的節點。另外，若 `struct` 中含有**動態配置的記憶體指標**，則要先 `free` 該指標所指向的記憶體空間，再 `free` 該結構體。還有 `head` 的結構與節點不同，`head` 並沒有 `element_t` 結構，故只需單獨 `free`。
```clike
free(list_entry(tmp, element_t, list)->value);
free(list_entry(tmp, element_t, list));
```
善用 Linux kernel API `q_release_element`
> commit: [84ee2f1](https://github.com/sysprog21/lab0-c/commit/84ee2f1407da8bccdea176d0be8baa2ec59c943d)
### q_insert
> commit: [a202b1e](https://github.com/sysprog21/lab0-c/commit/a202b1e11ecb64ddb73a5e9f22d65e7a3651489c)
>
#### 為什麼不能直接 newNode->value = s ？
Ans: 這樣只會讓 `newNode->value` 指向 `s`，但不會複製內容，若之後修改 `s`，那 `newNode->value` 也會跟著改變。例如：
```c
char *s;
char str[] = "Hello World!";
s = str;
printf("s: %s, str: %s\n", s, str);
strcpy(str, "123");
printf("s: %s, str: %s\n", s, str);
```
```
// output
s: Hello World!, str: Hello World!
s: 123, str: 123
```
又或者當 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 的記憶體空間。
- `strncpy(str1, str2, n)` :
將 `str2` 的前 `n` 個字元複製到 `str1` 中。要注意預留一個 byte 的空間給 null character。
#### 那 `strdup` 跟 `strncpy` 用哪個會比較好？
`strdup` 比較好，因為 `strdup` 會自動分配記憶體，而 `strncpy` 只是單純複製字串，**但仍然需要手動分配記憶體**，例如：
```c
newNode->value = malloc(strlen(s) + 1); // 需要自己分配記憶體
strncpy(newNode->value, s, strlen(s));
newNode->value[strlen(s)] = '\0'; // 確保結尾有 '\0'
```
### q_remove
> commit: [a202b1e](https://github.com/sysprog21/lab0-c/commit/a202b1e11ecb64ddb73a5e9f22d65e7a3651489c)
#### 為什麼參數有 `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](https://github.com/sysprog21/lab0-c/commit/a8f430359a1ef246afdcd8f2cfc8e94062728ca7)
#### 基於下方的程式碼 `deleteMiddle` 還有沒有更好的寫法？
```clike
int len = 0;
struct ListNode **indirect = &head;
while (*indirect) {
len++;
indirect = &(*indirect)->next;
}
int pos = len / 2;
len = 0;
indirect = &head;
while (len != pos) {
len++;
indirect = &(*indirect)->next;
}
*indirect = (*indirect)->next;
```
利用「快慢指標」，讓 fast 指標以兩倍速在走訪整個鏈結串列，slow 則以一倍速走訪鏈結串列，當 fast 完成走訪整個鏈結串列時，slow 指標剛好會停在中間的位置。例如：
```clike
struct ListNode *fast = head;
struct ListNode *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow = slow->next;
```
### q_delete_dup
> commit: [a8f4303](https://github.com/sysprog21/lab0-c/commit/a8f430359a1ef246afdcd8f2cfc8e94062728ca7)
思路：用巢狀迴圈，外層迴圈用於檢測兩兩節點的值是否相同，若相同則進入第二層迴圈，在第二層迴圈中刪除重複的節點。
#### 還有改進空間嗎？
用 Hash Table ...
### q_swap
> commit: [244dc15](https://github.com/sysprog21/lab0-c/commit/244dc156ad2ab4a00350e9184d3b5a046a638850)
思路：利用 `list_for_each(cur, head)` 去走訪整個鏈結串列，再透過 `list_move(cur, cur->next)`，由此一來每一輪的 `cur->next` 都會被插入到 `cur` 前面，又執行完 `list_move` 後，`cur` 無形中會自動跑到下一個節點，如下圖所示：
#### 依照上述做法會出現問題，當鏈結串列長度為奇數時，會多換一次，導致最後一個節點被移到最前面，怎麼解決？
多加一個判斷式，當 cur->next == head 時，就 break迴圈，避免發生交換即可。
> commit: [8904527](https://github.com/sysprog21/lab0-c/commit/89045277c7ccbfe472c76b45c06e59e6b708563d)
#### 當完成 `q_reverseK` 時，即可將 `q_swap` 寫成：
```c
q_reverseK(head, 2);
```
### q_reverse
> commit: [244dc15](https://github.com/sysprog21/lab0-c/commit/244dc156ad2ab4a00350e9184d3b5a046a638850)
作法：利用 `list_for_each_safe(cur, next, head)` 去走訪整個鏈結串列，再透過 `list_move(cur, head)` 將每一個點都重新插入 `head`，即可完成 reverse 操作。
### q_reverseK
> commit: [fcd4d2c](https://github.com/sysprog21/lab0-c/commit/fcd4d2c084a539ea43d10ecd245a91b373d28a0c)
作法：先得出鏈結串列的長度 `count`，當 `count` 大於 K 時，準備 `prev` 跟 `next` 兩個輔助指標做 Reverse K-group，做完後要 `count -= k`。
### q_descend
> commit: [13ffad8](https://github.com/sysprog21/lab0-c/commit/13ffad81caea17b9c5625fb63ec21e286171380b)
#### 有更好的做法，怎麼做？
我最一開始的思路是先找出串列中的最大值 `max`，再利用遞迴找出 `max->next` 子串列的最大值回傳給 `max->next`，如下程式碼所示，但會 Time out 時間複雜度為 $O(n^2)$ 等級。
用兩個指標來進行反向走訪：
- `max`：追蹤目前反向走訪過程中遇到的最大值節點（初始指向 `head->prev`，即尾部節點）。
- `cur`：負責走訪 `max` 前方的節點（初始指向 `max->prev` ）。
走訪過程：
- 如果 `cur` 所指的值**小於或等於** `max`，則刪除該節點。
- 如果 `cur` 所指的值**大於** `max`，則更新 `max` 為 `cur`，確保 `max` 始終指向目前反向走訪過程中遇到的最大值。
- 移動 `cur` 到 `prev`，繼續走訪。
如此一來就可以有效地保留遞減序列的節點，並刪除不符合條件的節點。
### q_ascend
> commit: [13ffad8](https://github.com/sysprog21/lab0-c/commit/13ffad81caea17b9c5625fb63ec21e286171380b)
>
作法與 `q_descend` 相似，一樣是透過反向走訪的思路，差別在走訪過程的條件，`q_ascend` 要刪除**大於等於** `min` 的值，若 `cur` 所指的值**小於** `min`，則更新 `min` 為 `cur`，以確保 `min` 始終指向目前反向走訪過程中遇到的最小值。如此一來就可以有效地 **保留遞增序列的節點，並刪除不符合條件的節點**。
### q_sort
> commit: [e5f1033](https://github.com/sysprog21/lab0-c/commit/e5f10336478bebd2c575aebf3f9e6d7671de41a8)
我原先參考了 [第二周測驗一 的 list_quicksort 實作](https://hackmd.io/@sysprog/linux2025-quiz2)，我將其轉換成 Linux kernel 風格的鏈結串列：
```c
struct list_head list_less, list_greater;
element_t *pivot;
element_t *item = NULL, *is = NULL;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, element_t, list);
list_del(&pivot->list);
if (!descend) {
list_for_each_entry_safe (item, is, head, list) {
if (strcmp(item->value, pivot->value) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
q_sort(&list_less, false);
q_sort(&list_greater, false);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
#### 使用 quick sort 為什麼會超時？
因為在 Worst Case 的情況下，Quick Sort 的時間複雜度會來到 $O(n^2)$ 等級。例如在全部節點值都相同的情況下，使用 **Singely-Linked-List** 示意：
令 $n$ 表示傳入的串列長度，第一個節點當作 `pivot`
再將剩餘的 $n-1$ 個節點做分割，比 `pivot` 小的節點插入到 `list_less` 串列中，反之則插入 `list_greater` 串列中。在此例中，當執行完 `list_for_each_entry_safe` 迴圈後，並無法分割串列，因為全部的節點都相同，因此都會被插入到 `list_greater` 中，還是得到長度為 $n-1$ 的子串列。
再遞迴呼叫 `q_sort`，所以都是透過設 `pivot` 在做分割串列，每回合只切一個節點，由此可推得時間函數式為 $T(n) = T(n-1) + cn$ ，其中 $c$ 為常數，$cn$ 表示執行 `list_for_each_entry_safe` 迴圈的時間，經化簡後得 $T(n) = O(n^2)$
\begin{gather} T(n) = T(n-1) + cn\\=T(n-2) + n + (n-1)\\ = T(n-3) + cn + c(n-1) + c(n-2)\\ ...... \\ = T(0)+cn+c(n-1)+c(n-2)+...+c \\ \because T(0) = 0 \\ \therefore T(n) = c[n+(n-1)+(n-2)+...+1] \\ = \frac {cn(n-1)}{2} = O(n^2)\end{gather}
故無法滿足時間複雜度 $O(nlogn)$ 的要求。
#### 如何優化？
改用 **Merge Sort** ，因為不管在什麼情況下，時間複雜度皆為 $O(nlogn)$ 等級。
> 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 之 Merge Sort
#### 這樣寫 Merge Sort，會出現 Segmentation Fault，是什麼問題？
```c=234
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
LIST_HEAD(left);
list_cut_position(&left, head, slow);
q_sort(head, descend);
q_sort(&left, descend);
struct list_head *merged = mergeTwoLists(&left, head, descend);
INIT_LIST_HEAD(head);
list_splice(merged, head);
```
使用 [Valgrind](https://valgrind.org) 分析，執行以下命令：
```bash
$ valgrind -q --leak-check=full ./qtest -v 3 -f traces/trace-04-ops.cmd
```
發現是 Stack Overflow ，看起來是第 248 列的遞迴沒寫好。
```
cmd> sort
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223== Can't extend stack to 0x1ffe8010b8 during signal delivery for thread 1:
==4012223== no stack segment
==4012223==
==4012223== Process terminating with default action of signal 11 (SIGSEGV)
==4012223== Access not within mapped region at address 0x1FFE8010B8
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223== at 0x1104B2: q_sort (queue.c:248)
```
先用簡單的例子來追蹤程式碼：
在執行完 while loop 後：
:::warning
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);` 修改即可。
```diff
- list_cut_position(&left, head, slow);
+ list_cut_position(&left, head, slow->prev);
```
接著，**Merge Sort** 會用到 `merge_two_lists` 輔助函數，用來合併由 `q_sort` 函數切割成兩半的子串列，比較特別的是要「 做 ascending / descending 的判斷 」。其中，為了要確保是 **Stable Sorting**，因此當遇到重複的數字時應保持原排列順序，以 ascending 為例，當目前左半子串列的值小於等於當前右半子串列的值時，應優先合併左半子串列的值。
### q_merge
> commit: [3e931f4](https://github.com/sysprog21/lab0-c/commit/3e931f4b8f70c3cac27a86e0d1667f6bf1492851)
先了解 `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](https://github.com/sysprog21/lab0-c/blob/master/scripts/driver.py) 這個 Python 程式。快速瀏覽發現這個自動評分程式就是將 traces/trace-XX-CAT.cmd 這樣形式的命令序列提供給 `qtest.c` 內的命令直譯器，然後依據給定的檢驗標準，逐一判定該給測試者多少分數。
## 整合網頁伺服器
### File descriptor (fd)
> [Reference 1](https://kkc.github.io/2020/08/22/file-descriptor/)
> [Reference 2](https://man7.org/training/download/lusp_fileio_slides.pdf)
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：
```c
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; // Skip "." and ".."
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;
}
// Get the target of the symbolic link
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");
}
// Get the type of the file descriptor
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);
}
```
查看建立 socket 前跟後 FD Table 的差異，以及當有新的 client 連進來後的差異：
:::spoiler 完整測試程式碼
```c
#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; // Skip "." and ".."
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;
}
// Get the target of the symbolic link
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");
}
// Get the type of the file descriptor
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();
// Create a socket descriptor
int server_fd;
if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
perror("Socket creation failed");
return -1;
}
list_open_fds();
// Eliminates "Address already in use" error from bind
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;
}
// Set up server address
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);
// Bind socket
if (bind(server_fd, (struct sockaddr*)&server_addr, sizeof(server_addr)) < 0) {
perror("Bind failed");
close(server_fd);
return -1;
}
// Listen for connections
if (listen(server_fd, SOMAXCONN) < 0) {
perror("Listen failed");
close(server_fd);
return -1;
}
printf("伺服器已啟動，等待連接...\n");
// Initialize client array and file descriptor sets
client_info_t clients[MAX_CLIENTS];
for (int i = 0; i < MAX_CLIENTS; i++) {
clients[i].client_fd = -1; // Mark as unused
}
fd_set read_fds; // read_fds represent a set of file descriptors
int max_fd = server_fd; // init the highest-numbered file descriptor to server_fd
while (1) {
// Clear and set file descriptor sets
FD_ZERO(&read_fds); // Clear
FD_SET(server_fd, &read_fds);
// Add active client sockets to 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;
}
}
}
// Use select to monitor sockets
if (select(max_fd + 1, &read_fds, NULL, NULL, NULL) < 0) { // max_fd + 1 -> nfds
perror("Select failed");
continue;
}
// Check for new connection
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;
}
// Get client socket information
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();
// Find an empty slot for the new client
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;
}
}
// Check for data from clients
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);
// Send echo message back to client
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");
}
}
}
// Cleanup
close(server_fd);
printf("伺服器關閉\n");
return 0;
}
```
:::
:::spoiler 預期輸出
```
Open file descriptors for process 305949:
FD Type Target
---------------------------------------------
0 Character Device /dev/pts/5
1 Character Device /dev/pts/5
2 Character Device /dev/pts/5
3 Directory /proc/305949/fd
19 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteTelemetry.log
20 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/ptyhost.log
21 Character Device /dev/ptmx
22 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteagent.log
23 Character Device /dev/ptmx
24 Character Device /dev/ptmx
Open file descriptors for process 305949:
FD Type Target
---------------------------------------------
0 Character Device /dev/pts/5
1 Character Device /dev/pts/5
2 Character Device /dev/pts/5
3 Socket socket:[3259968]
4 Directory /proc/305949/fd
19 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteTelemetry.log
20 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/ptyhost.log
21 Character Device /dev/ptmx
22 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteagent.log
23 Character Device /dev/ptmx
24 Character Device /dev/ptmx
伺服器已啟動，等待連接...
客戶端 140.116.245.209:46472 已連接
Open file descriptors for process 305949:
FD Type Target
---------------------------------------------
0 Character Device /dev/pts/5
1 Character Device /dev/pts/5
2 Character Device /dev/pts/5
3 Socket socket:[3259968]
4 Socket socket:[3259974]
5 Directory /proc/305949/fd
19 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteTelemetry.log
20 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/ptyhost.log
21 Character Device /dev/ptmx
22 Regular File /home/jimmy/.vscode-server/data/logs/20250428T121627/remoteagent.log
23 Character Device /dev/ptmx
24 Character Device /dev/ptmx
```
:::
### select system call
> [Manual page](https://man7.org/linux/man-pages/man2/select.2.html)
#### 運作原理：
Select 系統呼叫透過 fd_set 位元陣列來監控多個 file descriptor，檢查它們是否準備好進行讀取（readfds）、寫入（writefds）或是否有例外狀況（exceptfds），若已準備好，則使用 FD_SET() 將準備好之文件的 fd 對應到該 fd_set 的 bit 設為 1，告訴 select() 幫我監聽這個 fd 是否可讀。例如：使用 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 的狀態：
```c
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);
}
}
}
```
接著，寫程式來實驗看看 Select：
:::spoiler server 完整測試程式碼
```c
#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() {
// Create a socket descriptor
int server_fd;
if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
perror("Socket creation failed");
return -1;
}
// Eliminates "Address already in use" error from bind
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;
}
// Set up server address
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);
// Bind socket
if (bind(server_fd, (struct sockaddr*)&server_addr, sizeof(server_addr)) < 0) {
perror("Bind failed");
close(server_fd);
return -1;
}
// Listen for connections
if (listen(server_fd, SOMAXCONN) < 0) {
perror("Listen failed");
close(server_fd);
return -1;
}
printf("伺服器已啟動，等待連接...\n");
// Initialize client array and file descriptor sets
client_info_t clients[MAX_CLIENTS];
for (int i = 0; i < MAX_CLIENTS; i++) {
clients[i].fd = -1; // Mark as unused
}
fd_set read_fds; // read_fds represent a set of file descriptors
int max_fd = server_fd; // init the highest-numbered file descriptor to server_fd
printf("Init read_fds:\n");
print_fd_set(&read_fds, max_fd);
while (1) {
// Clear and set file descriptor sets
FD_ZERO(&read_fds); // Clear
printf("After execute FD_ZERO:\n");
print_fd_set(&read_fds, max_fd);
FD_SET(server_fd, &read_fds); // pull up the server_fd(index) bit in read_fds
printf("After execute FD_SET with server_fd:\n");
print_fd_set(&read_fds, max_fd);
// Add active client sockets to read_fds
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);
// Use select to monitor sockets
if (select(max_fd + 1, &read_fds, NULL, NULL, NULL) < 0) { // max_fd + 1 -> nfds
perror("Select failed");
continue;
}
printf("After call select:\n");
print_fd_set(&read_fds, max_fd);
// Check for new connection
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);
// Get client socket information
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);
// Find an empty slot for the new client
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;
}
}
// Check for data from clients
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);
// Send echo message back to client
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);
}
}
}
// Cleanup
close(server_fd);
printf("伺服器關閉\n");
return 0;
}
```
:::
::: spoiler client 完整測試程式碼
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <errno.h>
#define CONNECT_HOST "140.116.245.209"
#define CONNECT_PORT 1234
#define BUF_SIZE 1024
int main() {
// Create socket
int client_fd = socket(AF_INET, SOCK_STREAM, 0);
if (client_fd < 0) {
perror("Socket creation failed");
return 1;
}
// Set up server address
struct sockaddr_in server_addr;
memset(&server_addr, 0, sizeof(server_addr)); // Initialize server_addr structure to zero
server_addr.sin_family = AF_INET;
server_addr.sin_port = htons(CONNECT_PORT);
// Convert the CONNECT_HOST from string to binary
if (inet_pton(AF_INET, CONNECT_HOST, &server_addr.sin_addr) <= 0) {
perror("Invalid address");
close(client_fd);
return 1;
}
// Connect to server
if (connect(client_fd, (struct sockaddr*)&server_addr, sizeof(server_addr)) < 0) {
perror("Connection failed");
close(client_fd);
return 1;
}
// Get local address and port
struct sockaddr_in local_addr;
socklen_t addr_len = sizeof(local_addr);
if (getsockname(client_fd, (struct sockaddr*) &local_addr, &addr_len) < 0) {
perror("Getsockname failed");
close(client_fd);
return 1;
}
// Get local address
char local_ip[INET_ADDRSTRLEN];
inet_ntop(AF_INET, &local_addr.sin_addr, local_ip, INET_ADDRSTRLEN);
int local_port = ntohs(local_addr.sin_port); // ntohs: Network to Host Short (16-bits integer)
printf("本機: %s:%d\n", local_ip, local_port);
while(1) {
// Get input
char input[BUF_SIZE];
printf("輸入訊息: ");
if (fgets(input, BUF_SIZE, stdin) && input[0] == '\n') {
printf("輸入的訊息不得為空\n");
continue;
}
// Remove newline character("\n") from input
input[strcspn(input, "\n")] = 0;
// Send echo message back to client
if (send(client_fd, input, strlen(input), 0) < 0) {
perror("Send failed");
close(client_fd);
return 1;
}
printf("訊息已傳送...\n");
// Receive response
char buffer[BUF_SIZE]; // To store recevied message
ssize_t bytes_received = recv(client_fd, buffer, BUF_SIZE - 1, 0);
if (bytes_received < 0) {
perror("Receive failed");
break;
} else if (bytes_received == 0) {
printf("伺服器已斷開連線\n");
break;
} else {
buffer[bytes_received] = '\0';
printf("收到訊息: %s\n", buffer);
}
}
// Cleanup
close(client_fd);
printf("客戶端已中止...\n");
return 0;
}
```
:::
\
預期輸出：
- 在尚未有客戶端連線時，可以看到 `read_fds` 中 `fd 3` 被設為 1，而程式 block 在 select()，因為還尚未有 fd 可讀。
```bash
jimmy@NEAT:~/linux2025/socket_exam$ ./server_select
伺服器已啟動，等待連接...
Init read_fds:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1,
-----------------------------------------------------------------
After execute FD_ZERO:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 0,
-----------------------------------------------------------------
After execute FD_SET with server_fd:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1,
-----------------------------------------------------------------
After execute FD_SET with client_fd:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1,
-----------------------------------------------------------------
```
:::info
為什麼在尚未有客戶端連線時，server_fd 是不可讀的？
> server_fd 是監聽狀態的 socket，因此，在當有新的 client 執行 connect() 後，也就是有一個 connection 在等待被 accept() 時，監聽 socket 才可讀。
:::
- 在當有客戶端連線時，可以發現多了以下的輸出內容，首先是 select 發現 `fd 3` 可讀了（因為有新的連線），當新的連線進來後，因為新連線的 fd 值會大於 max_fd，因此需將 max_fd 更新為最新連線的 fd，接著就重複程式中迴圈的流程（參考上述 server 完整測試程式碼）。
```bash
After call select:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1,
-----------------------------------------------------------------
After accept client connection:
fd_set contents (up to 3):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1,
-----------------------------------------------------------------
客戶端 140.116.245.209:36360 已連接
After execute FD_ZERO:
fd_set contents (up to 4):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 0, fd 4: 0,
-----------------------------------------------------------------
After execute FD_SET with server_fd:
fd_set contents (up to 4):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1, fd 4: 0,
-----------------------------------------------------------------
After execute FD_SET with client_fd:
fd_set contents (up to 4):
fd 0: 0, fd 1: 0, fd 2: 0, fd 3: 1, fd 4: 1,
-----------------------------------------------------------------
```
註：由於 select 能監視的 file descriptor 有限（被巨集 FD_SETSIZE 限制，通常為 1024），故現在需支援大量服務的系統不再使用，改用 poll(2) 或 epoll(7) 替代。
## shuffle 實作
### q_shuffle
> commit: [484b7ea](https://github.com/sysprog21/lab0-c/commit/484b7ea9ed552612c31aacd5081eb9da5ef354a7)
參考 [你所不知道的 C 語言：Fisher–Yates shuffle](https://hackmd.io/@sysprog/c-linked-list#Fisher–Yates-shuffle) 演算法實作，透過 Pencil-and-paper method 對 Linux Kernel 的環狀雙向鏈結串列進行隨機洗牌，每次隨機選取一個節點並將其移動到 `new` 串列，直到所有節點都被移動。
### do_shuffle
> commit: [484b7ea](https://github.com/sysprog21/lab0-c/commit/484b7ea9ed552612c31aacd5081eb9da5ef354a7)
在 `qtest.c` 中新增 `do_shuffle` 函數，參考 `do_swap` 寫法，將 `q_swap(current->q);` 改成 `q_shuffle(current->q);`。詳細流程我還要弄清楚。
### 分析 q_shuffle 是否 Uniform distribution
透過統計方法驗證 shuffle，利用作業提供的測試檔測試，結果如下：
```bash
$ python3 test_shuffle.py
Expectation: 41666
Observation: {'1234': 70538, '1243': 5611, '1324': 33258, '1342': 13650, '1423': 15627, '1432': 5872, '2134': 79863, '2143': 82082, '2314': 50809, '2341': 31226, '2413': 17591, '2431': 54725, '3124': 25432, '3142': 66487, '3214': 52806, '3241': 7783, '3412': 39009, '3421': 62571, '4123': 46892, '4132': 35171, '4213': 85991, '4231': 7836, '4312': 58659, '4321': 50511}
chi square sum: 363008.4137186195
```
測試出來不太均勻，需要調整。
### 解決方法
> commit: [e28bbdd](https://github.com/JimmyChongz/lab0-c/commit/e28bbdd2500f58dcfbe9b880eb7b6e7e4a47d041)
後來，我發現是程式碼中使用 `srand(time(NULL))` 的問題，因為這個函數會根據時間（1970 年 1 月 1 日到現在的秒數）初始化亂數種子，由於 `time(NULL)` 的精度只有秒，當在短時間內重複呼叫 `q_shuffle()` 時，其中的 `srand(time(NULL))` 會產生相同的亂數種子，導致每次產生的亂數「序列」相同。
**驗證：在短時間內重複呼叫 `srand(time(NULL))` 會產生相同的亂數種子，且每次產生的亂數「序列」相同。**
:::spoiler 完整驗證程式碼
```c
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void test() {
srand(time(NULL));
printf("random seed: %lu\n", time(NULL));
for (int i = 0; i < 5; i++) {
printf("%d ", rand());
}
printf("\n");
}
int main() {
int count = 5;
while (count-- > 0) {
test();
}
return 0;
}
```
:::
:::spoiler 預期輸出（亂數種子相同、序列相同）
```
random seed: 1745983409
1042424400 1453791513 1018818495 61690579 736732418
random seed: 1745983409
1042424400 1453791513 1018818495 61690579 736732418
random seed: 1745983409
1042424400 1453791513 1018818495 61690579 736732418
random seed: 1745983409
1042424400 1453791513 1018818495 61690579 736732418
random seed: 1745983409
1042424400 1453791513 1018818495 61690579 736732418
```
:::
因此，當在執行 `test_shuffle.py` 時，在 1,000,000 次的洗牌中，會有部分的洗牌順序相同，導致不均勻洗牌。
再次測試：
```bash
$ python3 test_shuffle.py
Expectation: 41666
Observation: {'1234': 41430, '1243': 41914, '1324': 41566, '1342': 41802, '1423': 41328, '1432': 41663, '2134': 41660, '2143': 41646, '2314': 41720, '2341': 41667, '2413': 41614, '2431': 41952, '3124': 41714, '3142': 41739, '3214': 41585, '3241': 41503, '3412': 41947, '3421': 41556, '4123': 41554, '4132': 41802, '4213': 41511, '4231': 41509, '4312': 41626, '4321': 41992}
chi square sum: 16.01344021504344
```
可以發現，1234 的各種排列組合出現的次數皆為四萬多次，均勻多了。
## 讀論文 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
> 參考作業提供的 [論文重點提示](https://hackmd.io/@sysprog/linux2025-lab0-d#-論文%E3%80%88Dude-is-my-code-constant-time〉重點提示)
從引言的敘述中，推測 **Timing Leakage** 指的是程式執行時間與秘密數據之間的關聯性，導致攻擊者可以透過測量加密實作的執行時間來推測出機密資訊，例如：在 1996 年 Paul Kocher 發現 RSA 私鑰解密的運算執行時間取決於私鑰位元值，所以攻擊者就可以透過測量解密運算的執行時間來逐步恢復私鑰。這也是為什麼要探討 is my code constant time 的重要原因，以確保程式碼在不同輸入條件下的執行時間是固定的，以減少被 side-channel attacks 的可能性。
## 參考論文提供的 [GitHub](https://github.com/oreparaz/dudect) 來修改
> commit: [42af940](https://github.com/JimmyChongz/lab0-c/commit/42af94069697c218a80297bed43e25bcb4ef464d)
### Macro 中的 `##` 是什麼？
參考規格書對 ## operator 的敘述：
得知 ## 是在巨集中的「token 連接符號」，在 C 的預處理器中，## 可以將兩個 token 合併成一個 token，當參數為空時，C 預處理器會插入 placemarker，它最終會被刪除，不會影響程式碼的執行結果，例如：
```c
#include <stdio.h>
#define A(x) Value_##x
#define B(x, y) x##y
int main(int argc, const char * argv[]) {
int A(1) = 9;
int A(a) = 21;
printf("%d, %d\n", Value_1, Value_a);
int B(a, 1) = 21;
int B(b, 1) = 9;
printf("%d, %d\n", a1, b1);
printf("%d\n", B(123, )); // 空參數由 placemarker 代替
}
```
```
//output
9, 21
21, 9
123
Program ended with exit code: 0
```
Sign in with Wallet
Connect another wallet