---
# System prepended metadata

title: 2024q1 Homework1 (lab0)
tags: [linux2024]

---

# 2024q1 Homework1 (lab0)
contributed by < `fennecJ` >

#### Reviewed by `HenryChaing`
> 學到很多之前曾未想過得串列實作方式，其他留言放在內文。

## 開發環境
```bash!
# 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.

# lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 7600X 6-Core Processor
    CPU family:          25
    Model:               97
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5453.0000
    CPU min MHz:         400.0000
    BogoMIPS:            9381.96
```

### `q_insert_head`
> commit [56af0a](https://github.com/fennecJ/lab0-c/commit/56af0a32d63075c8841efdd85244605e77edd505) 

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

一開始我的作法如下：
```c!
bool q_insert_head(struct list_head *head, char *s)
{
    ...
    list_add(&(ele->list), head);
    return true;
}
```

:::warning
不要寫錯重要軟體的名稱。
:::

但這樣在嘗試 commit 的時候會一直被 Cppcheck 擋下來：
```
error: Memory leak: ele [memleak]
```

一開始嘗試查閱 [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf) ，但卻沒能解決我的問題。
花了一些時間後我猜 `ele->list` 如果沒有初始化的話 `list->next`, `list->prev` 不知道會指到哪邊造成潛在的錯誤。因此一開始以 INIT_LIST_HEAD 初始化 `ele->list` 的方式通過 Cppcheck。 但仔細檢視 list_add 後留意到它會明確將 `list->next`, `list->prev` 指到原本的 `head->next` 和 `head` ，不符前述假設。
之後做了許多嘗試，最後發現問題出在最後面的 `list_add(&(ele->list), head)` ，將其改為 `list_add(&ele->list, head)` （移除 ele->list 前後的括號）後就能通過 Cppcheck 的靜態檢查。

```diff
bool q_insert_head(struct list_head *head, char *s)
{
    ...
-   list_add(&(ele->list), head);
+   list_add(&ele->list, head);
    return true;
}
```

### `q_remove_head`
看到 remove 這個字的時候，一開始直覺認為會需要 free 記憶體空間，直到檢視 `queue.h` 中的註解：
```!
NOTE: "remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.
```

才知道只需 unlink 即可。
檢視 [List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) ，留意到 `list_del` 這個 API ，到 `list.h` 中可看到對應實作僅有將 node 進行 unlink:
```c!
static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}
```

同時可以留意裡面的 LIST_POISONING 會將 node 的前後指向非法的記憶體位址，用來防止 access via deleted node's next/prev，為何不將 node's next/prev 直接指向 NULL，這是為了能幫助我們更好的 debug ，可參考 [What is the role of LIST_POISON1 and LIST_POISON2](https://lists.kernelnewbies.org/pipermail/kernelnewbies/2016-March/015888.html) 的討論，若我們知道 page fault 的 addr 是 LIST_POISON1/2 ，我們能更容易定位到可能出錯的程式碼有哪些。
> 對照 [2024-02-{20,27} 問答簡記](https://hackmd.io/@sysprog/H1QORp-h6)

> 授課老師有建議可以多使用中文專有名詞，如節點。
> [name=HenryChaing]

### `q_merge`
> commit [285041](https://github.com/fennecJ/lab0-c/commit/2850412984dfccf483b1e686315f4841d7a29796)

不斷的將第二個以後的 queue merge 到第一個 queue 中即可。而在 merge 二個已排序的雙向鏈結串列時，為了方便處理迴圈結束的判斷條件，會將二個鏈結串列都改為 singular list
```c !
...
entry->q->prev->next = NULL;
...
```

最後透過一個 helper function [rebuild_list_link](https://github.com/fennecJ/lab0-c/blob/1e64e3ee14b40767bf3caf65d5dab3062393cb81/queue.c#L325)
將全部合併完的 list 回復為雙向鏈結串列。
值得一提的是在合併比較時用了一個 bitwise 的小技巧：
```c!
node = ((strcmp(ele1->value, ele2->value) < 0) ^ descend) ? &l1 : &l2;
```

直接用 xor descend 來判斷接下來的 node 應該是接 l1 的 node 或是 l2 的 node ，但會導致 sort unstable 的問題。

> 可以了解互斥或操作，但想請教您為何結果會 unstable
> [name=HenryChaing]


> 您好，stable sort 的定義為若存在元素 A, B 滿足兩者鍵值相等，則 sort 後 A, B相對位置不變。現在我們檢視上述透過互斥或的操作，假設 ele1->value 和 ele2->value 相等且 ele1 在 ele2 前面，若要滿足 stability ， ele1 在排序後也需要在 ele2 前面。若此時 descend = ture ，則 (strcmp(...) < 0 ) ^ descend 會等於 (0) ^ 1 = 1 。導致 ele2 先於 ele1 被放進 sorting 後的佇列中， ele1, ele2 兩者的前後關係發生改變。造成結果 unstable 。 在這裡用 ^ descend 的問題為，在 ele1, ele2 兩者相等時也會達成交換順序的條件。
> [name=fennecJ]

### `q_delete_mid`
> commit [e51e73](https://github.com/fennecJ/lab0-c/commit/e51e737f4f415f5c5ac7d1562f5503f30b8c51ac)

:::danger
改進你的漢語表達。
:::

我的作法是用兩個指標 forward, backward 以對向、相同移動速度來存取節點。由於這裡處理的是雙向鏈結串列，因此當兩個指標以相反等速的方向移動時，他們最終會相遇，下圖是一個簡單的示意：
![image](https://hackmd.io/_uploads/ryYHGyETa.png)

為了說明為何他們相遇在中間點，現在我們將他們的起點切開，把圓攤平：
![image](https://hackmd.io/_uploads/HyevX1ET6.png)

此時我們假設 Backward 和 Forward 相遇時， Backward 移動了 K 個距離。由於 Forward 以相同的速度移動，因此 Forward 的移動距離亦為 K 。我們可以得到
$$
2 K = L \\
K = \dfrac{L}{2}
$$

因此他們相遇的地方就在中間點。取出中間點後把它刪除即可。
```c 
...
struct list_head *forward, *backward;
forward = head->next;
backward = head->prev;
while(forward != backward && forward->next != backward){
    forward = forward->next;
    backward = backward->prev;
}
// backward will be the target we want to delete
```

### `q_reverse`
> commit [b7150e](https://github.com/fennecJ/lab0-c/commit/b7150ed37c51c53496df2276620a9678e2500a92)

將每個 node 的 prev 和 next 對調即可。
```c!
list_for_each_safe (n, sf, head) {
    tmp = n->next;
    n->next = n->prev;
    n->prev = tmp;
}
```

不過要注意 list_for_each 系列的 MACRO 都是從 head->next 開始 traverse ，所以要記得另外更新 head 的 prev 和 next
```c!
tmp = head->next;
head->next = head->prev;
head->prev = tmp;
```

### `q_reverseK`
> commit [1e64e3e](https://github.com/fennecJ/lab0-c/commit/1e64e3ee14b40767bf3caf65d5dab3062393cb81)

`q_reverseK` 的處理步驟如下：
* 將 list 以 K 個 node 為一組切成數組 sublists
* 找到每個 sublists 的 start 和 tail nodes，若找不到 tail (i.e. 剩餘 nodes 不足 K 個 ) 則直接 return
* 除了 start 和 tail node 之外，sublist 中其餘 node 的處理方式都和 q_reverse 相同：將 node 的 prev 和 next 對調。
* 最後單獨處理 start 和 tail ：
    * start->next 指向原本的 tail->next
    * start->prev 指向原本的 start->next
    * tail->next 指向原本的 tail->prev
    * tail->prev 指向原本的 start->prev

### `q_descend`, `q_ascend`
> commit [1e64e3e](https://github.com/fennecJ/lab0-c/blob/1e64e3ee14b40767bf3caf65d5dab3062393cb81)

由於處理 `q_descend` 和 `q_ascend` 的主要邏輯相同，因此這裡只介紹 q_decend 的作法：
從最後一個 node `head->prev` 開始往前面的 node 看，並紀錄目前看過得最大 string max_str 。若往前看時該 node 的值小於 max_str ，則移除該 node。

---

## 網頁伺服器
研讀 [整合網頁伺服器](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c) 時，學到了一個系統呼叫 [select()](https://man7.org/linux/man-pages/man2/select.2.html) 。
目前的理解如下：
使用者可將多個 file descriptor 傳入同一個集合 set 中，而 select 會同時 monitor 這些 file descriptor ，並透過 return value 告知使用者本次讀到的 file descriptor 是哪一個 file descriptor。
:::warning
用數位邏輯裡頭的 MUX 解釋。
:::

Mux （多工器）在數位邏輯中指的是可根據 sel 訊號從多個 input 中選擇一個訊號傳送到 output 的硬體，一個常見的 2-to-1 mux 構造如下：
![image](https://hackmd.io/_uploads/Hy76BFrT6.png)
以硬體描述語言 (HDL) 展現其行為：
```verilog!
module Mux(
    input i0,
    input i1,
    input sel,
    output out
)
assign out = (sel == 0) ? i0 : i1;
endmodule;
```

而 `select()` 系統呼叫可被視為：
* 可同時接收多個 I/O 輸入訊號。
* 根據不同的 I/O event 選擇對應的訊號輸出。

![image](https://hackmd.io/_uploads/Hk89vYSp6.png)

* 我們可以透過 `FD_ISSET()` 得知 select 訊號 S0 為何

Demux （解多工器） 在數位邏輯中指的是可根據 sel 訊號將一個訊號傳送到指定的接收端的硬體，一個常見的 1-to-2 demux 構造如下：

![image](https://hackmd.io/_uploads/H13-v3L66.png)

我們透過 `FD_ISSET()` 得知 select 訊號 S0 之後，可以根據 S0 進行後續的處理，就像是 Demux 的行為一樣：
![image](https://hackmd.io/_uploads/ByJROnUp6.png)

可對照 `console.c` 中 `cmd_select 的實做`：
```c!
    if (readfds && FD_ISSET(infd, readfds)) {
        // readline from stdin
        ...
    } else if (readfds && FD_ISSET(web_fd, readfds)) {
        // read cmd from web server
        ...
    }
```


### line_edit()
在 `linenoise.c` 中，主要讀取使用者輸入的 function 是 `line_edit()` 這個 function ：
```c!
...
while (1) {
    signed char c;
    int nread;
    char seq[5];

    nread = read(l.ifd, &c, 1);
...
}
```

這裡的 l.ifd 會是 stdin 的 fd ，透過 read 從 stdin 讀取一個 char 到 c 在交由後續進行處理。 若要讓 linenoise 也支援透過網頁伺服器接收命令，我們可以用 select() function 做 I/O multiplexing ，並依據收到的輸入是經由網路還是 stdin 做對應的處理。

### web command

:::danger
file 的翻譯是「檔案」，而非「文件」(document)
:::

檢視 `console.c` ，可以看到 `do_web` 這個 function ，透過字串查找卻沒有看到有哪個<s>文件</s> 檔案有透過 `do_web(` 呼叫這個 function 。然而透過 ./qtest 開啟程式後輸入命令 web
```bash!
# ./qtest
cmd> web
listen on port 9999, fd is 3
```

:::warning
對照閱讀[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)
:::

可以看到它會去執行 `do_web` 函式。仔細檢視和 web 相關的程式碼，發現 console.c 中有使用到一個巨集：
```c!
...
ADD_COMMAND(web, "Read commands from builtin web server", "[port]");
...
```

`ADD_COMMAND` 巨集展開如下：

```c!
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```

可以看到它會藉由 `do_##cmd` 將 `ADD_COMMAND(web,...)` 展開為
`add_cmd(web, do_web, ...)`
當 console 接收到 web 命令時，就會執行對應的 do_web() ，這裡我們簡單檢視其實作（詳見 [github](?) ：

:::danger
改進上方描述
:::

```c!
static bool do_web(int argc, char *argv[])
{
    ...
    web_fd = web_open(port);
    if (web_fd > 0) {
        printf("listen on port %d, fd is %d\n", port, web_fd);
        use_linenoise = false;
    } 
    ...
}
```

可以注意到其中的 `use_linenoise = false` ，這是因為藉由 curl 透過網頁伺服器傳命令到 console 中必須要傳輸完整的命令，用不上自動補全，所以當啟用 web 命令後會將 `use_linenoise` 設為 false

檢視 `run_console()` 可得知 console 處理 input 的流程：
```c!
bool run_console(char *infile_name)
{
...
    if (!has_infile) {
        char *cmdline;
        while (use_linenoise && (cmdline = linenoise(prompt))) {
            interpret_cmd(cmdline);
            line_history_add(cmdline);       /* Add to the history. */
            line_history_save(HISTORY_FILE); /* Save the history on disk. */
            line_free(cmdline);
            while (buf_stack && buf_stack->fd != STDIN_FILENO)
                cmd_select(0, NULL, NULL, NULL, NULL);
            has_infile = false;
        }
        if (!use_linenoise) {
            while (!cmd_done())
                cmd_select(0, NULL, NULL, NULL, NULL);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
...
}
```
先判斷是否有指定輸入檔案，若無 (i.e. stdin or via web) 則接著判斷是否能用 use_linenoise ，並透過 cmd_select 處理 input 。
cmd_select 是一個根據不同的 fd (stdin or web_fd) 進行對應處理的 function ，其實作可見 [github](https://github.com/sysprog21/lab0-c/blob/39c85e97b1b5b7b222a23e9d2066419463ab750b/console.c#L557)

#### 上述實作的缺陷
當開啟 web server 後，便再也不能使用 linenoise 的功能。有沒有辦法能同時支援 web server 又支援 linenoise 呢？ 

#### 我的作法
> commit [ed8a2ad](https://github.com/fennecJ/lab0-c/commit/ed8a2ad68c1ff80112098bf026620f66dfcb1b5f) 

由於使用 `web` 命令後便會把 linenoise 的功能關掉，因此我決定新增一個命令 `web_close` 讓使用者能在開啟 web server 後把它關起來，而在關掉 web server 的同時會再次將 linenoise 的功能打開。

#### 嘗試改善
> millaker's [commit](https://github.com/millaker/lab0-c/commit/039b945a7066215b706704693047973562f9c72c)
 
增加 `web_close` 讓使用者能夠重新開啟 linenoise 的功能，但在 web server 運作時仍會導致 linenoise 失效。可否進一步使 web server 運作的同時 console 中的 linenoise 也能同時運作呢？
強者我朋友 millaker 提出了一個解決思路：
無論何時都 call 到 linenoise 中，在 line_edit 內才分辨目前的 fd 是 stdin 還是 web_fd ，並根據對應的 fd 做後續的處理：
只要是 std_in 就進行 linenoise 的自動補全；只要是 web_fd 就直接處理 web_fd 傳來的命令。

但這樣還是會有一個缺陷，就是當使用者在 console 中使用了自動補全之後，經由 curl 傳到 web server 的命令沒辦法立刻被收到，要等到使用者在 console 中按下 enter 後才會被接收到。和 millaker 討論後，我們發現 linenoise 中的 complete_line() 有一個 while loop ，直到使用者按下 enter 後才會離開這個迴圈，這時程式才有機會注意到 web_fd 中有尚未讀取的 data 的原因導致這個現象。我們可以很直接的修改 complete_line() 中處理的流程來解決 curl 被 linenoise 阻塞住的問題，但這會導致 linenoise 套件的運作邏輯被大幅改動，不利於後續的維護。

查資料的過程中，大致看了 SIGIO/poll/epoll 等等可以用來處理 socket data 的作法，但無論是哪個 function 似乎都不能很好 / 優雅的處理上述的問題。
如果要作到兩邊都能即時有反應，我目前只想到透過 context switch 的方式輪流處理 stdin 和 web_fd ，不知道還有什麼好方法？
:::warning
對照 https://github.com/sysprog21/lab0-c/pull/162
:::

[vax-r](https://hackmd.io/@vax-r) 同學也對同時使用網頁伺服器和 linenoise 提出他的 [解決方案](https://github.com/sysprog21/lab0-c/pull/162) ，我十分贊同他 「盡可能對 linenoise 做最小改動」的這個想法，由於 linenoise 是額外整合在作業中的套件，日後若要將其 sync 到 upstream ，較小的改動能讓我們更容易進行更新的維護以及減少 bug 發生的機會。

我嘗試了 vax-r 同學的 repo 但仍會出現前述問題。
為了清楚說明，我將開啟兩個 terminal 並分成兩個名字： term_stdin, term_web
其中 term_stdin 用來透過終端機藉由 linenoise 直接和 qtest 互動 
term_web 僅會透過 curl 將命令傳入 qtest 中的網頁伺服器。
依照下列步驟執行可重現我的問題：
* 在 term_stdin 輸入 web 開啟網頁伺服器
* 在 term_stdin 輸入 ne ，其後按下 `tab` 使其自動補全為 new
* 補全後不要在 term_stdin 中按下任何鍵，直接切換到 term_web (此時 term_std 畫面如下)
```
cmd> web
listen on port 9999, fd is 3
cmd> new▮
```
( ▮ 為游標符號 )
* 移動到 term_web 視窗，輸入 curl `http://localhost:9999/it/a` 並按下 enter ，會發現該命令被 block 住， qtest 不會處理它
* 這時回到 term_stdin 按下 enter 後會發現 it a 命令在 new 之後才被處理，此時term_stdin 畫面如下：
```
cmd> web
listen on port 9999, fd is 3
cmd> new
l = []
cmd> 
l = [a]
cmd> 
```
我認為先送出的命令 (it a 先被 enter 送出） 應先被處理較合理，但顯然 output 不符合先送出先處理的原則。（若先處理 it a 預期應可見到 `Warning: Calling insert tail on null queue` 等訊息）
:::warning
> [name=I-HSIN Cheng]
經過測試後，上述問題的發生是由於函式 `complete_line` 當中的 `read` 函式呼叫引起的阻塞問題，當我們按下 tab ( `line_edit` 當中的 main loop 監聽) 進行自動補全後，程式行為實際上是交給 `complete_line` 來進行自動補全，並在補全後依然停留在 `complete_line` 當中的 `read` 函式等待使用者進一步輸入，造成此 `./qtest` 這個 process 阻塞在此處。
同時您在 term_web 下達的 `curl` 命令則被寫入 socket fd 指向的 file 當中等待讀取，直到您在 term_stdin 按下 `ENTER` 使得 `./qtest` 跳出 `complete_line` 的迴圈並完成對應命令後，才去處理 socket fd 當中的指令。
:::
:::warning
> [name=fennecJ]
原來如此，謝謝您耐心解釋程式流程和前述現象發生的原因。
:::

:::warning
> [name=I-HSIN Cheng]
此處我認為有兩個解決方法。第一種是同時間處理多個請求的話，利用多執行緒的方法分開處理，畢竟 `linenoise` 原本的設計就建立在面對單一命令輸入的情形。第二種是同樣利用 `web_eventmux` 在`complete_line` 內做監聽，將 `term_web` 傳送進來的命令暫存，並在 `complete_line` 回傳時讓 `line_edit` 有兩個命令必須執行。我認為第一個方法較為恰當，第二個方法會大幅改動到 `linenoise` 套件預設行為（試想如果同時開啟 n 個 terminal 並對 `./qtest` 發送請求，此方法就要暫存 `n` 條指令）。 此處應請教 Jserv 老師何種變更較為合適。
我認為還有一種較暴力的可能方法是在 `web_eventmux` 當中若收到網路封包請求就直接執行 `interpret_cmd` 將該命令直接執行，執行完後回到 `linenoise` 中的 `complete_line` 或 `line_edit` 繼續監聽 standard input 的命令，但此方法同樣涉及大量改動與變更 `web` 預設行為，我認為能讓功能執行但不適當。
:::
:::warning
> [name=fennecJ]
原先我和 [millaker](https://hackmd.io/@millaker/HyXNtXmna) 討論的解法也是您提到的第二點 - 在 complete_line 中進行 I/O 的監聽，但正如您提到的，此種方法將大幅改動 `linenoise` 原先的行為，可能導致後續維護上的困難。
:::
:::warning
> [name=I-HSIN Cheng]
我使用一個替代方案，依據我上次提交的 PR ，如果在開啟 `web` 命令後，在 command-line 寫入任何指令（不按 tab ），並在另一個 terminal 傳入 command ，則程式會將 command buffer 當中的指令替換成 web request 傳送進來的指令，於是原本 command-line 的命令會被丟棄。如果此行為是可接受的，那只要在 `complete_line` 當中進行以下更動，即可做到相同的行爲。如果此行為是可接受的，我將於近日提交新的 PR 以修復此問題。

```diff
                ls->pos = saved.pos;
                ls->buf = saved.buf;
            } else {
                refresh_line(ls);
            }

+        if (eventmux_callback != NULL) {
+            int result = eventmux_callback(ls->buf);
+            if (result != 0) {
+                free_completions(&lc);
+                return ENTER;
+            }
+        }  
```
:::

:::warning
當初設計這項作業時，希望引導學員引入 coroutine 來解決問題，例如 [Coroutines in C](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)，工程領域本來就常見殊途同歸，很難說一個方法就絕對優於另一者，尚有其他的權衡 (trade-off) 因素，如程式碼的維護成本、持續擴充的考量。
:notes: jserv
:::

### 實作 q_shuffle
> commit [7002a4](https://github.com/fennecJ/lab0-c/commit/7002a49a82858ff2f52fb18ab5bbbe351a52f1ea)

照著教授提供的 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法可很容易的實作出來，比較特別的是和 [404allen404](https://hackmd.io/@404allen404) 討論時他指出其實不用特別花心思處理要交換的 `node->prev`, `next` 等 link 的資料，而是可以直接交換 node 中 element 存的值。我覺得這個想法很好，因此用這個方法進行交換。

### 研讀論文〈Dude, is my code constant time〉


#### Misc
* make valgrind trace-17 每次都會過（目前試過 7 次），但 make test trace-17 幾乎都會 failed （ 14 次僅一次 pass）
* q_merge() 改良（改成頭尾兩兩合併）

:::warning
研讀指定的論文
:::

# ttt

## 將 ttt 引入 lab0-c
為了方便後續的維護，我將 ttt 獨立為一個目錄並整合進 lab0-c 中，詳見 commit [613374](https://github.com/fennecJ/lab0-c/commit/613374acf04088ba2ec4b4820b0f20aa65b06429)

## Concurrent programming
我將 ttt 的運作過程分為幾個並行程式：
* listen_keyboard 負責監聽任何按下按鍵的事件
* player_X_move 負責下 X 的 agent, ai 為 negamax
* player_O_move 負責下 O 的 agent, 根據 ttt_mode 的 option
* update_screen 負責顯示時間資訊和重新繪製棋盤等工作
* game_manager 負責判斷是否有人獲勝或是以滿足平手條件

task 的 schedule 則參考 [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched) 中的實做，同時在必要的地方直接呼叫 `schedule()` 將 cpu 使用權交出去增進使用體驗。

要注意的是，由於任一邊（ O 或 X ）下完之後都有可能滿足獲勝或平手的條件，因此實做上需要在 player_X_move/player_O_move 後都呼叫一次 game_manager 。另外也記得要分別呼叫 update_screen ，避免

```c 
task_add(listen_keyboard, g_args);
task_add(player_X_move, g_args);
task_add(update_screen, g_args);
task_add(game_manager, g_args);
task_add(player_O_move, g_args);
task_add(update_screen, g_args);
task_add(game_manager, g_args);
```
此外，為了方便不同並行程式間的溝通，我定義了一個結構 `game_arg` ：
```c 
typedef int(game_agent_t)(char *table, char mark);
typedef struct {
    char turn;
    char table[N_GRIDS];
    bool game_play;
    game_agent_t *agentX;
    game_agent_t *agentO;
    int pX_score;
    int pO_score;
    int draw;
    char *pX_name;
    char *pO_name;
    bool echo;
} game_arg;
```
而 `player_X_move` 和 `player_O_move` 運作上會分別呼叫 `agentX` 和 `agentO` 來決定要下在哪裡，如此只要替換掉 更改 agentX 和 agentO 指向的 function 便能很簡單的替換不同的 ai 邏輯。

### ai vs ai
> commit [2628ae](https://github.com/fennecJ/lab0-c/commit/2628ae2ccd06ba2a7696738dc5d481bb41bd56e8)


### listen_keyboard
> commit [4a2111](https://github.com/fennecJ/lab0-c/commit/4a2111e53c992bbd89e25af3b6ebdb97ead7009f)

我留意到大部分同學在進行 ai vs human 的作業時無法同時顯示出當前的時間（精確到秒），而想要達到這樣的效果需要解決一個問題，就是若直接透過 `read()` 去捕捉使用者的輸入，則因為 nonblocking read 以及處理 IO 時會關閉 preemption 的關係，若使用者完全沒有在進盤上進行任何輸入，則畫面會直接卡在那邊無法透過 scheduler 跳到別的 coroutine 執行。
這裡我嘗試透過 `poll()` 系統呼叫，當 poll 偵測到 stdin 有新的 input ，則會直接由 read 讀取一個字元並寫入 input buffer ，直到偵測到使用者按下 enter 後才根據 input buffer 內容執行對應操作。若 poll 尚未偵測到 stdin 有新的 input ，則會直接呼叫 scheduler 進行排程讓畫面時間能夠刷新。而由於只有在明確知道有字元需要讀取時才會呼叫 `read()` ，此時由於 STDIN 有尚未讀取的字元存在所以立刻會處理完往後執行，而不會卡在那邊等新的輸入，如此便能造成即時反應的效果達到顯示出當前的時間（精確到秒）的功能。

```c 
nfds_t nfds = 1;

while (run_ttt) {
    poll(&pfd, nfds, 0);
    if (!(pfd.revents & POLLIN))
        schedule();

    // read part
    preempt_disable();
    (void) !read(STDIN_FILENO, &c, 1);
    ...
```


### ai vs human
> commit [76d90c](https://github.com/fennecJ/lab0-c/commit/76d90c424c2cd2e28969c0cfa0c497953b0a6be3)

為了讓 ai vs human 也能順利顯示出當前的時間（精確到秒），我們仍需要 scheduler 的介入適時切換到印出時間資訊的 task 。

我在 listen_keyboard 中額外處理了 ENTER 和 BACKSPACE 事件，讓使用者能藉由 listen_keyboard 輸入座標並顯示在終端機上，同時透過 shceduler 來呼叫 update_screen 使時間能順利更新。

以下為 demo 影片：
{%youtube s2wYWHZ0K3s %}


## 定點數運算
### log
實做主要參考 Clay S. Turner 提出的 [A Fast Binary Logarithm Algorithm](http://www.claysturner.com/dsp/BinaryLogarithm.pdf) 以及對應的實現 [程式碼](https://github.com/dmoulding/log2fix)

### sqrt
使用牛頓法進行開根號運算：
假設我們要以牛頓法求 val 之根：
令方程式 
$$f(x) = x^2 - val$$
我們要求的根 a 滿足
$$f(a) = 0$$
用牛頓法進行迭代，假設 a 初始值為 $a_0$ ， 可得
$$e_0 = f(a_0) = a_0^2 - val$$

已知
$$f'(x) = 2x$$
則我們可以得出過點 ($a_0, e_0$) 之切線方程 L1 為
$$L1(x) = 2a_0 * x + e_0 - 2a_0^2$$
令 $a_1$ 為 $L1(x) = 0$ 的根，則可求出
$$ a_1 = \dfrac {2a_0^2 - e_0}{2a_0} $$
$$ = a_0 - \dfrac{e_0}{2a_0} $$
$$ = a_0 - \dfrac{a_0^2 - val}{2a_0} $$
$$ = a_0 - \dfrac{a_0}{2} + \dfrac{val}{2a_0} $$
$$ = \dfrac{1}{2}(a_0 + \dfrac{val}{a_0}) $$
之後我們便能再用 a_1 進行後續的迭代。

加速牛頓法的迭代
若初始值足夠靠近目標點則可以用更少的迭代次數取得足夠的精度。
已知 $val = 2^{MSB} + ...$ ，則我們可以知道 $\sqrt{val}$ 必定滿足
$\sqrt{val} >= 2^{\lfloor \frac{MSB}{2} \rfloor}$
因此我們可將初始值設為
```c 
int x = 1 << (MSB >> 1);
```
而 MSB 的計算可由
```
MSB = 32 - __builtin_clz(val); 
```
得出。
然而這種估計方式只對整數域有效，假設傳入的定點數小數域共有 PRECISION 個 bits ，則
```c 
int x = 1 << (MSB >> 1);
```
會變成
```c 
int x = (1 << PRECISION) << (MSB >> 1);
// to express 1 in fixed point, we need to left shift PRECISION bits
```
且在計算 MSB 時，也要把 PRECISION 佔的 bit 數剪掉：
```
MSB = 32 - PRECISION - __builtin_clz(val); 
```
最後將其整理為初始值的計算公式：
$$ (1 << PRECISION) << (MSB >> 1) $$
$$ = 1 << (PRECISION + (MSB >> 1) $$
$$ = 1 << (PRECISION + (32 - PRECISION - CLZ) >> 1) $$
$$ = 1 << ((PRECISION >> 1) + 16 - (CLZ >> 1)) $$

```c 
uint32_t clz_res = __builtin_clz(val);
uint64_t x = 1 << ((precision >> 1) + 16 - (clz_res >> 1));
```

目前取 PRECISION 為 20 bits ，經過實驗，只要進行四次牛頓法就能收斂到可接受的誤差範圍。
之所以取 20 的原因是因為 mcts 演算法中的 ITERATION 次數為 $10^6 \approx 2^{20}$ 而計算 ust 的公式為
$$\dfrac{wins}{ITERATION} +\sqrt{\dfrac{2 * log(parent\_try)}{ITERATION}}$$
因此小數部份需要能有 $10^{-6} \approx 2^{-20}$  的精度，因此取 20 bits 。
最後我們可以實做出對應的開根號運算：
```c 
uint32_t sqrtFix(uint32_t val){
clz_res =(uint32_t) __builtin_clz(val | 1);
    uint64_t x = 1 << ((PRECISION >> 1) + 16 - (clz_res >> 1));
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    x = (x + fixDiv(val, x, PRECISION)) >> 1;
    return x;
}
```

## div/mult
直接進行乘除運算後記得 div 要左移; mult 要右移 PRECISION 位即可。

```c!
uint32_t fixMult(uint32_t a, uint32_t b, int precision){
    uint64_t res = a * b;
    return (uint32_t)(res >> precision);
}

uint32_t fixDiv(uint32_t a, uint32_t b, int precision){
    uint64_t t_a = (uint64_t)a << precision;
    // or 1 to prevent div by zero
    uint32_t res = t_a / (b | 1);
    return res;
}
```