# 2025q1 Homework1 (lab0)
contributed by <[eric895888](https://github.com/eric895888/lab0-c)>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.9) 2.35
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 6220.80
```
## queue.c 開發過程
#### q_new
在實作過程中發現到`new_node`要先檢查 `head` 是否為 `NULL`，原本沒有檢查是否成功配置記憶體位置給`new_node`會導致執行錯誤 。
```c
if (!new_node) {
return NULL;
}
```
#### q_free
先依序訪問各個節點並將其刪除且釋放記憶體，一開始忘記最後加上`free(head)`導致鏈結串列已空但仍有記憶體佔用的情況發生。
```c
list_for_each_entry_safe (curr, safe, head, list)
q_release_element(curr);
```
#### q_insert_head
確保記憶體分配成功後才進行插入節點`node`到`head`後方，使用 `strdup()` 複製字串，避免修改原字串導致錯誤，再更新雙向鏈結串列的 `next` 和 `prev` 指標，確保鏈結完整，使用的是list.h裡的`list_add()`去完成。
#### q_insert_tail
跟上面的區別在於更新雙向鏈結串列的連接不同改成插入節點 `node` 到 `head` 前方，使用的是 list.h 裡的`list_add_tail()`去完成。
#### q_remove_head
一開始判斷是否為空,後來利用 `container_of()` 找出 head 的 `next` 節點，把`node->value`的值存 bufsize 給sp，而sp的最後一個字元改成結束符號'\0'。
```c
if (sp && node->value) {
strncpy(sp, node->value, bufsize );
sp[bufsize - 1] = '\0';
}
```
刪除節點的方式是利用list.h裡`list_del()`改變前後節點的連結。
#### q_remove_tail
一開始判斷是否為空,後來利用 `container_of()` 找出 `head` 的 `next` 節點，其餘與`q_insert_tail()` 作法相同。
#### q_size
針對雙向連結串列走訪一次判斷是不是又回到 `head` ，並使用 `count` 紀錄個數。
#### q_delete_mid
這邊採用的是快慢指標的方式去尋找中間節點，再利用 `list_del` 刪除鏈結串列找到的中間節點及`q_release_element()` 釋放那個節點的記憶體。
```c
struct list_head *slow = head->next, *fast = head->next; //first element
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
```
#### q_delete_dup
用 `list_for_each_safe()` 來走訪鏈表，其中 `curr` 指向當前節點，`safe` 指向下一個節點，以確保在刪除節點時不影響遍歷。在循環中，若 `curr` 和 `safe` 的值相同則刪除 `curr`，並標記 `dup = true` 表示當前值有重複。如果 `dup` 為 `true`，代表前一個元素是重複的，因此刪除 `node`，直到遇到不同的值時，將 `dup` 重置為 `false`。最後，成功執行後返回 `true`，表示刪除了重複元素。
但是原始 leecode 中的題目只會給排序好的鏈結串列作為輸入，我的作法目前也只能刪除連續的重複值。
#### q_swap
做到 `q_reverseK()` 才發現 `q_swap()` 相當於 `q_reverseK(head, 2)`。
#### q_reverse
如 head <-> A <-> B <-> C <-> D <-> head，`curr`初始指向`head`，針對每一個節點的`next`及`prev`做反轉。
```c
truct list_head *prev = head->prev, *curr = head, *next = head->next;
while (next != head) {
next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
```
#### q_reverseK
用`len` 計算是否等於k再運用`list_cut_position()`，切下長度為k的連結串列存到`splited_list_head`中，再把`splited_list_head`反轉，透過`list_splice（）`去原本的位置。
#### q_sort
使用另外撰寫的`merge_sort（）`先拆分成一半分成左右區塊再繼續遞迴呼叫`merge_sort（）`繼續拆分，之後使用`two_list_merge（）`進行合併再依照 descend 的布林值決定是否降序排列。
#### q_ascend
對於任意一個在佇列中的節點，其前面的節點必定要小於自己，且其後面的節點必定大於自己。
#### q_descend
對於任意一個在佇列中的節點，其前面的節點必定要大於自己，且其後面的節點必定小於自己。
#### q_merge
會使用到 `queue_contex_t` 這個結構，看了許多資料才知道使用這個結構來做這題會更方便實作，使用`list_for_each_entry（）` 走訪鏈表中每個 `queue_contex_t` ，並將每個佇列 `(curr->q)` 中的元素移動到 `tmp` 中，最後呼叫`q_sort（）`對`tmp` 排序，並放回 head 所指向的第一個佇列。
```c
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
queue_contex_t *curr;
list_for_each_entry(curr, head, chain){
list_splice_init(curr->q, &tmp);
}
q_sort(&tmp, descend);
list_splice_init(&tmp, first->q);
```
## 以 Valgrind 分析記憶體問題
學習使用 Valgrind，搭配 Massif 可以量測你的程式用了多少的 heap memory。
產生範例 test-massif.cmd。
```c
new
ih head 100000
it tail 100000
reverse
sort
size
quit
```
例如下方使用 valgrind，之後會產生像這樣格式的 massif.out.43407 檔案。
```
valgrind --tool=massif ./qtest -f traces/test-massif.cmd
```
安裝圖形化顯示工具 massif-visualizer 方便觀看及分析。
```
sudo apt install massif-visualizer
```
顯示執行結果
```bash
massif-visualizer massif.out.43407
```
可以搭配 massif.out.43407 檔案內的文字紀錄搭配視覺化圖片得知， heap 的峰值主要是在 ih head, it tail產生資料。
## tiny-web-server
在查看Linux manual pageg 時會看到像是 select(2) 函數中代了數字，參考 [Linux manual page](https://man7.org/linux/man-pages/man7/man-pages.7.html) 可以代表的意義。
#### 研讀 select(2)
[select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫允許程式監控多個 file descriptors ，「非阻塞」地進行讀、寫或錯誤檢查，例如監控 socket。
```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);
```
nfds: 要監控的 file descriptors 數量上限，實際上是最大值 + 1，例如如果你要監控 fd = 4，那 nfds 就應該設為 5。
readfds：指向 fd_set 結構，代表哪些是否可讀？可為 NULL。
writefds：指向 fd_set 結構，代表哪些是否可寫入？可為 NULL。
exceptfds：指向 fd_set 結構，是否有異常狀況?可為 NULL。
回傳值0：有文件描述符準備好了，-1：錯誤。
File descriptor set：
FD_ZERO(&set) 清空集合。
FD_SET(fd, &set) 把 fd 加入集合。
FD_CLR(fd, &set) 把 fd 從集合中移除。
FD_ISSET(fd, &set) 查某 fd 是否在集合中。
timeval: 設成 NULL：永遠阻塞直到某個 fd 準備好，設成 {0, 0}：非阻塞查詢（立即回傳)。
#### 研讀 signal(7)
[signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html) 用來通知某個程序（process）發生了某件事情，產生什麼行為。
Signal 可分為兩大類：標準信號（Standard Signals）與即時信號（Real-Time Signals）。
* 標準信號是的 POSIX 信號，如 SIGINT（中斷）、SIGTERM（終止）、SIGSEGV（記憶體存取錯誤）、SIGKILL（強制終止）等，其特點是不能攜帶附加資料，且同一種信號同時僅會儲存一筆（可能會被覆蓋。
* 標即時信號則是 POSIX Real-Time 擴充的一部分，編號通常從 SIGRTMIN 開始，它們支援排隊傳送，且可以攜帶額外資料，例如使用 sigqueue() 傳送。
當 signal 發生時，系統會依據 signal 的「處置方式（disposition）」來決定如何反應，包括預設終止（Term）、忽略（Ign）、產生核心轉儲（Core）、停止（Stop）或繼續執行（Cont）。使用者可透過 signal() 或 sigaction() 安裝 signal handler，進一步自訂 signal 的處理行為，Signal 可由多種方式發送，如 kill()、raise()、pthread_kill() 等，並可透過 mask 機制來阻擋、延後處理或同步接收 signal。
#### 解決 favicon.ico 的問題
參考 [作業敘述](https://hackmd.io/@sysprog/linux2025-lab0-c#%E8%A7%A3%E6%B1%BA-faviconico-%E7%9A%84%E5%95%8F%E9%A1%8C) 修改解決 favicon.ico 的問題讓網頁也能夠使用web指令了
但是使用curl指令時會產生以下的問題，回傳時會把它當成瀏覽器回應把整個html都回傳到了終端機。
```bash
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="#"><h2>Success!</h2></head><body><table>
```
一開始會想到可能是依照header去判斷是誰負責請求，首先先宣告一個全域變數負責存 header 資訊 `char user_agent_buf[MAXLINE] = ""; ` 然後在`parse_request()` 中的 `while ()` 中新增了一段程式碼。
```c
if (strncmp(buf, "User-Agent: ", 12) == 0) {
strncpy(user_agent_buf, buf + 12, MAXLINE - 1);
user_agent_buf[MAXLINE - 1] = '\0';
char *crlf = strchr(user_agent_buf, '\r');
if (crlf) *crlf = '\0';
printf("User-Agent: %s\n", user_agent_buf); //print test
}
```
送出指令的時候可以看到上排的是使用 curl 的 header 而下排則是使用瀏覽器的 header。
```
cmd> User-Agent: curl/7.81.0
cmd> User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/134.0.0.0 Safari/537.36
```
而 buffer 則依照 user_agent_buf 內儲存的內容不同來決定那一種回傳格式。
```c
char *buffer;
if (strstr(user_agent_buf, "curl")) {
buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
} else {
buffer = "HTTP/1.1 200 OK\r\n"
"Content-Type: text/html\r\n\r\n"
"<html><head><style>"
"body{font-family: monospace; font-size: 13px;}"
"td {padding: 1.5px 6px;}"
"</style><link rel=\"shortcut icon\" href=\"#\">"
"<h2>Success!</h2>"
"</head><body><table>\n";
}
```
這樣子網頁跟終端機都能正常顯示回傳了。
## 在 qtest 提供新的命令 shuffle
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 在實作 shuffle。
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
int len = q_size(head);
struct list_head *pos, *tmp;
for (pos = head->prev, tmp = pos->prev; pos != head && len;
pos = tmp, tmp = pos->prev, len--) {
int r = rand() % len;
struct list_head *pick = head->next;
for (int i = 0; i < r; i++)
pick = pick->next;
if (pick != pos)
swap(pos, pick);
}
}
```
以課程提供的 python 程式碼進行測試以及顯示出來的圖表，以圖表和數值來看大致符合 uniform distribution，需要進一步繼續用其他評估方式分析。
```
Expectation: 41666
Observation: {'1234': 41573, '1243': 41666, '1324': 41613, '1342': 41539, '1423': 41612, '1432': 41696, '2134': 41556, '2143': 41783, '2314': 41658, '2341': 41850, '2413': 41712, '2431': 41913, '3124': 41715, '3142': 41870, '3214': 41904, '3241': 41321, '3412': 41873, '3421': 41933, '4123': 41387, '4132': 41490, '4213': 41530, '4231': 41766, '4312': 41594, '4321': 41446}
chi square sum: 16.295252724043586
```
## 論文〈Dude, is my code constant time?〉
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
#### `__attribute__((nonnull(2,3)))`
`__attribute__` 屬於 function attribute，nonnull(2,3) 表示第二、第三的輸入參數必定不為 NULL。
參考 [2023 年 Linux 核心設計/實作課程作業 —— lab0 (E)](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e#L01-lab0) 內的數學證明去理解 sort 的過程，及2019年的 [commit b5c56e0c](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 開發者探討了 merge sort 的三種實作方式，分別為 top-down mergesort、bottom-up mergesort 和 queue-mergesort。
2025年1月的 [Commit e420460](https://github.com/torvalds/linux/commit/e420460ba443e8ad1cd71568c50b6e09d13fb106) 時候特別強調了函數必須滿足的數學性質，特別是反對稱性和遞移性，提出了曾有 [[1]](https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail.com)[[2]](https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmail.com)[[3]](https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmail.com)[[4]](https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmail.com ) 違反了遞移性導致排序結果發生錯誤。
```c
* The comparison function must adhere to specific mathematical properties
* to ensure correct and stable sorting:
* - Antisymmetry: cmp(@a, @b) must return the opposite sign of
* cmp(@b, @a).
* - Transitivity: if cmp(@a, @b) <= 0 and cmp(@b, @c) <= 0, then
* cmp(@a, @c) <= 0.
```
從上述資料學習到要搭配 commit message 去理解過去修改的原因及過程，例如我前面作業部份都是修改幾個函式再 commit 所有異動，這會導致閱讀的人不便。
#### 將 list_sort.c 以及 list_sort.h 加入 lab0-c
看到 likely 時不知道是什麼所以參考[[Linux Kernel慢慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/)， 提到 likely 或 unlikely 的敘述來幫助編譯器做最佳化，`__built_expect()` 是 gcc 的內建 function，用來將 branch 的相關資訊提供給編譯器，以便對程式碼改變分支順序來進行優化，使用 likely 表示這段敘述 (x) 為 true 的機率比較大。
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
接著把list_sort.c 以及 list_sort.h的內容移進lab0-c，並修改部份內容讓程式能夠執行
qtest.c 的部份則是根據 sort 的 do_sort() 多一個給 list_sort 並新增 ADD_COMMAND
```c
ADD_COMMAND(lsort, "Use Linux kernel sorting algorithm", "");
```
再來`list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)` priv 的部份可以帶入NULL。
而 cmp 的部份則是在 qtest.c 中新增一個函式判斷 list_head *a 和 list_head *b 指向的值。
根據 list_sort.c 的註解。
```c
/* The comparison function @cmp must return > 0 if @a should sort after
* @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
* sort before @b *or* their original order should be preserved. It is
* always called with the element that came first in the input in @a,
* and list_sort is a stable sort, so it is not necessary to distinguish
* the @a < @b and @a == @b cases.*/
```
* return > 0 (a 排在 b 的後面)。
* return <=0 (a 排在 b 的前面或保留原本排列)。
* list_sort 是一個 stable sort，故不用區分小於0和等於0的狀況。
```c
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *a_ele = list_entry(a, element_t, list);
element_t *b_ele = list_entry(b, element_t, list);
return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1;
}
```
#### 使用perf進行效能分析
參考[Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
```
perf stat --repeat 5 -e instructions,cycles ./qtest -f ./traces/trace-sort.cmd
```
trace-sort.cmd 裡面的內容
```c
option fail 0
option malloc 0
new
ih RAND 500000
time
sort (另一份是lsort)
time
```
| q_sort | time |
| -------- | -------- |
| 1 | 0.766 |
| 2 | 0.764 |
| 3 | 0.764 |
| 4 | 0.771 |
| 5 | 0.776 |
| instructions | cycles |
| -------- | -------- |
| 4,778,363,882 | 5,267,510,435 |
| list_sort | time |
| -------- | -------- |
| 1 | 0.594 |
| 2 | 0.594 |
| 3 | 0.603 |
| 4 | 0.595 |
| 5 | 0.594 |
| instructions | cycles |
| -------- | -------- |
| 4,705,154,742 | 4,419,841,615 |
可以看到 list_sort 的 cycle 明顯比較少。
git commit 時目前會遇到以下錯誤，因此無法上傳，原因在於3/11號lab0-c新增的fmtscan.c功能，似乎也有其他人遇到。
```
Running static analysis...
tools/fmtscan.c:664:26: warning: Either the condition 'nextch2!=256' is redundant or isxdigit() argument nr 1 can have invalid value. The value is 256 but the valid values are '0:255'. [invalidFunctionArg]
if (isxdigit(nextch2)) {
^
tools/fmtscan.c:657:17: note: Assuming that condition 'nextch2!=256' is not redundant
if (LIKELY(nextch2 != PARSER_EOF)) {
^
tools/fmtscan.c:664:26: note: Invalid argument
if (isxdigit(nextch2)) {
^
nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingInclude]
Fail to pass static analysis.
```
Sign in with Wallet
Connect another wallet