# 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)

## 環境

$ 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`。

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` 也會跟著改變。例如：

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` 只是單純複製字串，**但仍然需要手動分配記憶體**，例如：

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` 還有沒有更好的寫法？

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 指標剛好會停在中間的位置。例如：

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` 寫成：

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 風格的鏈結串列：

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，是什麼問題？

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) 分析，執行以下命令：

$ 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);` 修改即可。

- 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：

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 完整測試程式碼

#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 的狀態：

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 完整測試程式碼

#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 完整測試程式碼

#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 可讀。

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 完整測試程式碼）。

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，利用作業提供的測試檔測試，結果如下：

$ 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 完整驗證程式碼

#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 次的洗牌中，會有部分的洗牌順序相同，導致不均勻洗牌。

再次測試：

$ 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，它最終會被刪除，不會影響程式碼的執行結果，例如：

#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