# 2024q1 Homework1 (lab0)
conftributed by < `jason50123` >
### Reviewed by `jimmy01240397`
1. 依據[中文文案排版指北](https://github.com/sparanoid/chinese-copywriting-guidelines)，英文與中文間請空一格，標點符號請用正確。
2. [q_new](#q_new)：函式即將返回之處，沒必要再多加一段 `else` 的區塊。
```diff
if (!head)
return NULL;
- else {
INIT_LIST_HEAD(head);
return head;
- }
```
3. [q_remove_head and q_remove_tail](#q_remove_head-and-q_remove_tail)：依據 [glibc 2.36](https://sourceware.org/git/glibc.git) 的實作，沒必要額外計算字串長度後再後面添加 `'\0'`
```c
char *
STRNCPY (char *s1, const char *s2, size_t n)
{
size_t size = __strnlen (s2, n);
if (size != n)
memset (s1 + size, '\0', n - size);
return memcpy (s1, s2, size);
}
```
```diff
- size_t copy_size;
- if (strlen(tmp->value) < (bufsize)) {
- copy_size = strlen(tmp->value);
- } else {
- copy_size = bufsize - 1;
- }
- strncpy(sp, tmp->value, copy_size);
- sp[copy_size] = '\0';
+ strncpy(sp, tmp->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
```
4. 善用巨集展開以減少重複的程式碼，例如：
```c
#define q_remove_base(head, sp, bufsize, from) \
if (!head || list_empty(head)) \
return NULL; \
element_t *tmp = list_##from##_entry(head, element_t, list); \
if (sp) { \
size_t copy_size; \
if (strlen(tmp->value) < (bufsize)) { \
copy_size = strlen(tmp->value); \
} else { \
copy_size = bufsize - 1; \
} \
strncpy(sp, tmp->value, copy_size); \
sp[copy_size] = '\0'; \
} \
list_del(&tmp->list); \
return tmp;
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, first);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, last);
}
```
- q_insert_head
- q_insert_tail
- q_remove_head
- q_remove_tail
5. [q_delete_mid](#q_delete_mid)：沒必要多做一次 `q_size` 進行<s>遍歷</s> ? 來取得長度且請避免非必要的浮點數，可以參考「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」，善用快慢指標解決取得中間節點的問題。
6. [q_delete_dup](#q_delete_dup)：可使用變數儲存比較結果來減少多餘的分支
```diff
+ bool dup = false, now_dup = false;
+ now_dup = &safe->list != head && !strcmp(tmp->value, safe->value);
+ if(now_dup || dup) {
- if(&safe->list != head && !strcmp(tmp->value, safe->value)) {
list_del(&tmp->list);
q_release_element(tmp);
+ dup = now_dup;
- dup = true;
- } else if (dup) {
- list_del(&tmp->list);
- q_release_element(tmp);
- dup = false;
}
```
7. `merge_two_queues`: 刪除非必要的分支
```diff
int merge_two_queues(struct list_head *q1, struct list_head *q2, bool descend)
{
element_t *entry, *safe;
struct list_head *q1_head, *q2_head;
q1_head = q1;
q2_head = q2;
int count = q_size(q1) + q_size(q2);
+ long long key = &&ret ^ &&conti;
+ goto (list_empty(q2) * key) ^ &&conti;
+conti:
- if (list_empty(q2)) {
- return count;
- }
q2 = q2->next;
list_for_each_entry_safe (entry, safe, q1, list) {
- if (descend) {
- while (strcmp(entry->value,
+ while (((!!descend) * 2 - 1) * strcmp(entry->value,
list_entry(q2, element_t, list)->value) < 0) {
- if (q2->next == q2_head) {
q2 = q2->next;
list_move(q2->prev, entry->list.prev);
+ key = &&out ^ &&whi;
+ goto (onout * key) ^ &&whi;
+whi:
- goto out;
- } else {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- }
}
- } else {
- while (strcmp(entry->value,
- list_entry(q2, element_t, list)->value) > 0) {
- if (q2->next == q2_head) {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- goto out;
- } else {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- }
- }
- }
}
out:
list_splice_tail_init(q2_head, q1_head);
+ret:
return count;
}
```
> 量化分析上述更動到底可省下多少次分支，工程人員說話要有證據。 :notes: jserv
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz
CPU family: 6
Model: 167
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
```
## 指定佇列的操作
### `q_new`
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
這邊使用 `malloc()` 來先配置一個 `struct list_head` 的記憶體空間，並用指標 head 去記錄他的位置。
- 先判斷使否有 `malloc()` 成功，有則運用 `INIT_LIST_HEAD()` 來把 `head` 的 prev、next 指到自己。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
else {
INIT_LIST_HEAD(head);
return head;
}
}
```
### `q_free`
運用 `list_for_each_entry_safe()` 來存取整條 `list_head` 的結構，且因為會有 `remove` 掉當前節點的動作，所以必須使用 `list_for_each_entry_safe()` 而非 `list_for_each_entry()` ，參考以下註解得到此結論。
- 透過 `list_for_each_entry_safe()` 存取完整條鏈結串列的過程中，運用 `q_release_element()` 去 free 掉 `struct element_t` 這個結構，而非將 `struct list_head()` 從鏈結串列 free 掉而已，重複此步驟來達到 q_free() 的效果。
```c
list_for_each_entry - Iterate over list entries
* The nodes and the head of the list must be kept unmodified while
* iterating through it. Any modifications to the the list will cause undefined
* behavior.
```
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
### `q_insert_head`, `q_insert_tail`
這邊在試著用 `strcpy()` 的方式把原本的 input 複製到自己所 malloc 出的節點中，但在 git-push 的時候發現該方法並不安全，引述自 [CERN Computer Security](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
- The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
:::danger
避免非必要的項目縮排 (即 `* ` 或 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
也因為這樣所以改用 `strndup()` 來實作
```diff
bool q_insert_head(struct list_head *head, char *s)
{
...
- size_t size = strlen(s)+1;
- node ->value = malloc(sizeof(size));
- strcpy(node->value, s);
+ node->value = strndup(s, strlen(s));
list_add(&node->list, head);
return true;
}
```
最後又試著用 `strncpy()` 來完成
```diff
bool q_insert_head(struct list_head *head, char *s)
{
...
- node->value = strndup(s, strlen(s));
+ strncpy(node->value, s, strlen(s));
+ node->value[strlen(s)] = '\0';
list_add(&node->list, head);
return true;
}
```
### `q_remove_head` and `q_remove_tail`
原本的想法是直接透過 `list_first_entry()` 來拿到整條鏈結串列中的第一個 `struct element_t` ，並將他的 `char *value` 直接透過 `strlen()` 取得該字串的長度並直接 malloc 一塊記憶體空間給他，但後來發現在執行測試的時候會出現 core dump 的警告，也因此作了以下修改。
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
...
if (sp) {
size_t copy_size;
- copy_size = strlen(tmp ->value);
+ if (strlen(tmp->value) < (bufsize)) {
+ copy_size = strlen(tmp->value);
+ } else {
+ copy_size = bufsize - 1;
+ }
strncpy(sp, tmp->value, copy_size);
sp[copy_size] = '\0';
}
list_del(&tmp->list);
return tmp;
}
```
==可以改進的地方==: q_remove_tail() 可以用 q_remove_head(head ->prev) 來完成就可以
### `q_delete_mid`
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
運用`q_size()`求出整個鏈結串列的長度，再用 for loop 讓 pointer 可以走到對的位置並 delete 掉該點
- 此處由於是要做 delete ，而不是只有 remove ，所以我除了將該 element 中的 `struct list_head` 用 `list_del()` 移除後，再使用 `queue_release_element()` 把該點 free 掉
### `q_delete_dup`
在遍歷鏈結串列的過程中，運用 `strcmp()` 去比較目前的節點的值是否跟下一個節點的值相同，若有則先將 `bool dup` 設成 true ，並將下面的節點進行刪除後，再回過頭將目前的 node 刪除
```c
bool q_delete_dup(struct list_head *head){
...
list_for_each_entry_safe (tmp, safe, head, list) {
if (&safe->list != head && !strcmp(tmp->value, safe->value)) {
list_del(&tmp->list);
q_release_element(tmp);
dup = true;
} else if (dup) {
list_del(&tmp->list);
q_release_element(tmp);
dup = false;
}
}
}
```
### `q_swap`
總共紀錄4個點，分別是 `slow ->prev`, `slow`, `fast`, `fast->next` ，每次去修改這四個點的 prev 以及 next ，此處應該使用 ==macro 將程式碼改得更為精簡==。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
struct list_head *fast, *slow, *fasttmp, *slowtmp;
slow = head->next;
fast = slow->next;
while (fast != head && slow != head) {
slowtmp = slow->prev;
fasttmp = fast->next;
slow->next = fast->next;
slow->prev = fast;
fast->prev = slowtmp;
fast->next = slow;
slowtmp->next = fast;
fasttmp->prev = slow;
slow = fasttmp;
fast = slow->next;
}
}
```
### `q_reverse`
每次修改 current 以及前後 node 的 pointer
### `q_reverseK`
先運用 `q_size()` 去除以 input "K" 來得到總共有幾個 `groups` ，並且在每個迴圈中做完的時候去把 `count++` ，藉此來計算已經 reverse 了幾個 groups，然後在每一個小的 group 自己要做reverse時候，將 current node 透過 `list_move()` 來把它移到 group head 來達到 reverse 的效果。
:::danger
改進你的漢語表達。
:::
```c
void q_reverseK(struct list_head *head, int k)
{
list_for_each (first, head) {
struct list_head *tmp;
tmp = first->prev;
if (count < groups) {
for (int i = 1; i < k; i++) {
second = first->next;
list_move(second, tmp);
}
}
count++;
}
}
```
### `q_merge`
- q : pointer to element_t, 也就是排序過的佇列
- chain : 串了多個佇列, 也就是可能會有多條的佇列
- size : q 有幾個 element
- id : unique id
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
### q_sort()
運用 merge sort 去實現
sol:
1. 找到中間的節點
2. 切斷 list 製作出兩個出兩個獨立的 list
3. 遞迴 1
4. merge
參考 [link list 實作 merge sort](https://npes87184.github.io/2015-09-12-linkedListSort/), 和這篇文章不同的點是在 merge 以及 split 兩條 list 的時候，我們切出來的兩條 link list 會有額外的`struct list_head`需要去處理。
==TODO==:把他先處理成單向的 link list 在做處理。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
## 研讀並引入lib/list_sort.c
> 參考 [marvin0102](https://hackmd.io/@marvin0102/linux2024-homework1#%E7%A0%94%E8%AE%80%E4%B8%A6%E5%BC%95%E5%85%A5liblist_sortc)
在研讀 `list_sort` 的時候法現有像以下的程式碼，但不知道他的意思，所以就去查閱了相關資料 [Function-Attributes](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Function-Attributes.html)，才知道除了 `packed` 、 `aligned` 此種對記憶體管理的 function 外，還有這些像是下面的 `nonnull` ，可以對哪幾個傳入的參數進行非空的限制．
```c
typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
struct list_head const *, struct list_head const *);
```
且經過閱讀程式碼後發現， `list_sort` 裡面的 `*priv` 主要是用來當 counter 且可以不用傳值進去的，所以也就在這邊把它拿掉。
```diff
- void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
+ void list_sort(struct list_head *head, list_cmp_func_t cmp)
```
然後在引入的過程中會發現缺少一些相關的標頭檔以及巨集，所以要在這邊將他補上。
```diff
#list_sort.c
- #include <linux/kernel.h>
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
- #include <linux/string.h>
- #include <linux/list_sort.h>
- #include <linux/list.h>
+ #include "./list_sort.h"
```
```diff
#list_sort.h
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+typedef unsigned char u8;
```
並在 `q_test.c` 裡面加上新的 command `lsort` 來提供給使用者呼叫
```diff
+ ADD_COMMAND(lsort, "Do list_sort", "");
```
[commit ]()
:::danger
補上對應的 git commit 超連結，並確認已進行 rebase
:::
---
## 亂數
在 trace code 的過程中可以先找到原本我們加了 `RAND` 參數後， `./qtest` 會透過 `strcmp()` 來把 `need_rand` 變數修改成 true ， 並在後續透過 `fill_rand_string()` 來產生亂數，所以以下模仿這樣的寫法，新增一個 `Xorshift` 的選項。
``` diff
if (!strcmp(inserts, "RAND")) {
need_rand = true;
inserts = randstr_buf;
}
+ if (!strcmp(inserts, "XORS")) {
+ need_xor = true;
+ inserts = randstr_buf;
+ }
```
研讀 [Xorshift](https://en.wikipedia.org/wiki/Xorshift) 後發現這個方法是 [Linear-feedback shift register (LFSR)](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) 的子集合，藉由閱讀以上文獻，目前對於 `LFSR` 的理解為:移動前一個 bit 的 output 來當成下一個 bit 的 input，而其中 `Xorshift` 有一段範例程式碼，如下所示，還沒有辦法理解為什麼要左移以及右移這樣數量的 bit 。
```c
struct xorshift32_state {
uint32_t a;
};
/* The state must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
uint32_t x = state->a;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return state->a = x;
}
```
- [XORshift](https://github.com/jason50123/lab0-c/commit/90b6013a032bae4fd3647c9769bc05aa1dd4f42e)
實驗步驟 :
透過一個 `global buffer` 來把每一次的 `RAND、XORS` 生成的亂數都存下來，然後再使用 `ent` 來做分析。而且在這之前我想先知道原本 用 `ent` 實驗中的範例`linux 內建的 PRNG /dev/random` 所生成出來的格式和內容是甚麼所以我就去執行了一遍。
```bash
$ head -c 100 /dev/random
B�#�!��d��]>��-��Z��5g�BKOe���_fi��d��\�KV�o�;Ϊ��������lų�̒㤛�C��`e-��P]G���(���%
```
結果就像上面得到了一坨的亂碼，查閱了相關資料後發現 `terminal` 會自己試著用 `UTF-8` 的方式把內容印出來，但這些字符沒有辦法以這樣的方式輸出，所以要透過16進制的方式把它印出來，也就成功印出了以下的數據
```bash
$ head -c 10 /dev/random |xxd -p
5f9c103b79ab75bb34b8
```
但也從這邊可以看到原本實驗的 `ent` 的範例 input 是沒有任何的空白鍵的，但我們目前 `./qtest` 所產生的亂數，中間還會有空白鍵做分割，可能會影響到實驗效果，所以這邊做了一下比較。
```bash
#RAND 所生成的20組亂數並放到 ent 裡面的內容(有空白鍵)
mlmjir wajxqc isdrnfsj oblprodt lqixigdc ccdvnx lohhvovvs tdwoqm yeqbynkq irobrrjjc gditoxm zlppbgwon kljkaebpg auqit cxzghwghz dkxryaa hscsjgm nyhvbyxpp nrlekvurf asrjo
# ent 實驗的輸出
$ ent random_data.txt
Entropy = 4.594609 bits per byte.
Optimum compression would reduce the size
of this 170 byte file by 42 percent.
#去掉空白鍵之後
$ ent random_data.txt
Entropy = 4.641885 bits per byte.
Optimum compression would reduce the size
of this 151 byte file by 41 percent.
```
可以從上述的內容發現將空白鍵刪除後確實會讓亂數更亂，所以些接下來實驗就會以沒有空白鍵的亂數作為輸入值。
但在上面的結果我發現我們的 `entropy` 值，會比我們預期的值要小的很多，所以這中間可能是生成出來的亂數並不夠亂，所以這邊我就針對我們生成亂數的 `charset` 進行改動，並做了相對應的實驗，來證明說在`charset`裡面可以加入大小寫以及數字來讓亂數更亂。
==TODO : 這邊應該可以加入其他特殊符號來讓亂數更亂==
```diff
- static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
+static const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
```
```bash
#原本 charset 的結果(只有大小寫)
$ent random_data.txt
Entropy = 4.699479 bits per byte.
#加入數字的實驗結果
$ ent random_data.txt
Entropy = 5.159285 bits per byte.
#加入大小寫跟數字
$ ent random_data.txt
Entropy = 5.949377 bits per byte.
```
從這邊的實驗結果可以得到 `charset` 應使用有大小寫英文字母以及數字來進行後續實驗可以得到較好的`entropy`值。
後續用 `Xorshift` 、`RAND` 各生成亂數並做比較會發現 `RAND` 方法產生的亂數的 `entropy` 會比 `Xorshift` 來的高一點。
```bash
#Xorshift
Entropy = 4.483300 bits per byte.
Optimum compression would reduce the size
of this 501603 byte file by 43 percent.
Chi square distribution for 501603 samples is 5509651.63, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 87.2729 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.016055 (totally uncorrelated = 0.0).
#RAND
Entropy = 5.949742 bits per byte.
Optimum compression would reduce the size
of this 501789 byte file by 25 percent.
Chi square distribution for 501789 samples is 1583614.88, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 87.4574 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.001818 (totally uncorrelated = 0.0).
```
這邊將輸出的文字檔用 python 分析後發現每個音文字母的出現次數確實沒有均勻分佈，目前還在嘗試如何解決該問題
## web
> 本部分與 [HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework1) 協作
中間修改過程看到 `select`, `accept` 等系統呼叫，但完全不知道這些系統呼叫的運作原理，所以又找了一些參考資料來閱讀，打算先理解 TCP Client/Server 的原理，[參考資料](https://man7.org/linux/man-pages/man7/tcp.7.html)，而且在閱讀這些 `Linux manual page` 的時候看到後面都有不同的數字，因此去查閱了 [man-pages](https://man7.org/linux/man-pages/man7/man-pages.7.html) 才發現這些參數代表了許多涵義。
```
1 User commands (Programs)
Commands that can be executed by the user from within a
shell.
2 System calls
Functions which wrap operations performed by the kernel.
3 Library calls
All library functions excluding the system call wrappers
(Most of the libc functions).
```
:::danger
為何不閱讀第一手材料，像是 Linux man pages 和電腦網路的教科書呢？
> [name=jason50123] 感謝老師提醒，已經試著去閱讀第一手的資料，並從中獲得有效資訊
:::
先找到整個 command line 運行的過程，會看到從 `qtest.c` 中的 `main` 呼叫 `run_console` ，並從 `run_console` 的註解中可以知道他會 `run command loop` 所以這邊就先看一下 `run_console` 會做什麼事。
而從程式碼中可以看到，裡面會先去看 `use_linenoise` 與否，如果沒有用的話則會跳去執行 `cmd_select`，且從以下程式碼可以看到，在原本程式中執行 `do_web` 之後，就會將 `line_noise` 關閉。
```c
static bool do_web(int argc, char *argv[])
{
...
web_fd = web_open(port);
int flags = fcntl(web_fd, F_GETFL);
fcntl(web_fd, F_SETFL, flags | O_NONBLOCK);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
use_linenoise = false;
...
}
```
在[作業指引](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c)中可以看到要使用 `select` 來處理 `stdin`、`socket` ，而在參閱了 [Select man-page](https://man7.org/linux/man-pages/man2/select.2.html#top_of_page) 後才了解到，我們要先用 `FD_SET` 來初始化 `file descriptor set` ，並在後續用 `FD_SET` 來把對應的 Fd 加到此 set 裡面，在看完跟 `select` 相關的文件後，接著繼續看 `do_web` 裡面用到的 function call， 發現會用 `web_open` 去處理跟 `socket` 相關的內容。
從 [tcp(7)](https://man7.org/linux/man-pages/man7/tcp.7.html) 可以得知 `web_open` 裡面如何完成 `tcp socket` ，其中在呼叫 `web_open` 的時候，會先透過 `socket()` 來建立一個 tcp socket，接著透過` setsocketopt()` 來設定和 socket 相關的參數，然後透過 `bind()` 把 socket 跟local socket address 綁在一起，最後透過 `listen()` 來讓 socket 可以接受新的連線。
嘗試先從 console.c 修改，透過[作業指引](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c)了解到將 `socket` 改成 `non-blocking` ，會跟`fcntl()` 有關係，因此先去找 `fcntl` 如何使用 [fcntl(2)](https://man7.org/linux/man-pages/man2/fcntl.2.html)
```c
int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
//把 listenfd 設成 non-blocking
```
F_SETFL (int) : 透過此 F_SETFL 將 file descroptor 的 flag 設置成不同 access mode 、 file creation flag 。
接著 `run_console` 就會進到 `linenoise()` 裡面，而 `linenoise()` 主要的流程會像 `linenoise()->linenoiseRaw()->linenoiseEdit()`。
### 整合 socket 以及 linenoise 套件
[commit 074a790](https://github.com/jason50123/lab0-c/commit/074a79011d39bf331e566a3cdea9f8b8b4977dd9)
:::danger
改進書寫和處理授課教師要求的改正，從小處做起！
:::
## 引入 tic-toc-toe
依照[作業要求提示](https://hackmd.io/@sysprog/linux2024-ttt#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)可以知道要先找到 `zobrist.ch` 裡面用到的 `hlist` 相關內容並擷取 `linux/hlist` 的部分程式碼，並獨立成 `hlist.h`。
並在 `qtest.c` 中先新增一個 command
```diff
+ ADD_COMMAND(ttt, "tic-tac-toe", "");
```
查看 `ttt/Makefile` 來把 `ttt` 需要的檔案複製到 `lab-0c` 專案<s>資料夾</s> 中，並把原本的 `ttt/main.c` 改為 `ttt/ttt.c`。
:::danger
directory 是「目錄」，而非「檔案夾」(folder)
:::
而在要著手修改 `mcts` 的時候，會發現在 make 的時候產生以下錯誤
```bash
/usr/bin/ld: ttt.o: in function `ttt':
/home/shrimp/linux2024/lab0-c/ttt.c:139: undefined reference to `mcts'
collect2: error: ld returned 1 exit status
make: *** [Makefile:54：qtest] 錯誤 1
```
後來發現這個錯誤是因為編譯器無法找到 `mcts` 的相關定義，從而導致了 `"undefined reference to mcts"` 的錯誤，所以在 `makefile` 內作了以下更動
``` diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o
...
+ agents/mcts.o
```
且在準備將目前進度做 `git-commit` 的時候會發現有許多 `null pointer` 以及 `variable scope` 的相關問題須做修正，修正的相關 commit 如下
[commit 060e467](https://github.com/jason50123/lab0-c/commit/060e46759112867c7e300601c23301e0640ad183)
而在 trace `mcts()` 的過程中會發現裡面的 `calculate_win_value()`、`simulate()`、`uct_score()`都會用到浮點數運算，但根據[作業要求](https://hackmd.io/@sysprog/linux2024-ttt#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)告訴我們要把這些運算都改為固定精度表示，所以這邊找了 c library 提供的 [libfixmatrix](https://www.nongnu.org/fixmath/doc/index.html)
:::danger
不！你該自行實作 fixed point 操作，避免使用現有的函式庫，考慮因素是:
1. 針對場景設計符合自身需求、兼顧精度和空間效率的實作
2. 你該自己先實作過，才去比較其他實作的落差
:notes: jserv
:::
Sign in with Wallet
Connect another wallet