# 2024q1 Homework1 (lab0)
`contributed by Lisa304`
### Reviewed by `marvin0102`
> 你的洞見呢？
在 `q_reverse` 實作時，可以加入 `is_list_singular()` 因為當佇列只有一個節點時，可以直接 return
在引入 list_sort 之後，可以加入 list_sort 與佇列操作中的 `q_sort()` 作實驗比較，測試兩種排序方法的效能差異，同時也可以考慮在不同資料分佈的情況下，各種排序法的效能變化。
# 開發環境
```bash
$ 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) m3-6Y30 CPU @ 0.90GHz
CPU family: 6
Model: 78
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
Stepping: 3
CPU max MHz: 2200.0000
CPU min MHz: 400.0000
BogoMIPS: 2999.93
```
# 指定的佇列操作
### `q_new`
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
:::danger
改進你的漢語表達。
:::
使用 `malloc` 動態配置記憶體區塊，此方法回傳 `void` 類別的指標，並可以轉換成任何資料型別的指標，於是轉換成結構 `list_head` 指標並指派給 `new` 變數，當配置失敗時 `malloc` 方法會回傳空指標，此時函式呼叫 `free` 釋放配置的記憶體區塊並回傳 `NULL` ，如果配置成功，就呼叫 `INIT_LIST_HEAD()` 函式初始化 `new` 指標所指的新建佇列。
#### q_free
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
>
如果傳入的參數為空，則直接跳離函式，否則使用允許刪除動作的 `list_for_each_entry_safe ` 巨集迭代每個佇列的節點，並且呼叫 `q_release_element` 釋放佇列上結構 `element_t` 的節點，最後呼叫 `free` 方法釋放 `head` 配置的記憶體區塊。
#### q_insert_head
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
使用 `malloc` 方法為新建立的節點配置記憶體區塊，配置失敗函式回傳 `false`，呼叫 `strdup` 複製第二參數指標所指向的字串，回傳指向複製後字串的指標，使用 `list_add` 將新節點加入第一
#### q_insert_tail
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
使用 `q_insert_head` 來完成此功能。
```diff
+ if (!head) return false;
+ return q_insert_head(head->prev, s);
```
#### q_remove_head
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
使用 `list_first_entry` 找出第一參數佇列開頭的節點，呼叫 `list_del` 函式將從佇列中移除，如果參數 `sp` 不是 `NULL`，將移除的節點的值複製到參數 `sp` 中，最多複製參數 `bufsize` 個字元（包括空終止符），返回被移除的元素的指針。
一開始是使用 `strncpy` 來做字元比較，但一直出現錯誤，後來就用迴圈先陽春的完成功能了。
:::warning
可以改用 strncpy 或者 memcpy 使程式更加精簡
Reviewed by `marvin0102`
:::
#### q_remove_tail
>[commit Implement remove and insert functions](https://github.com/sysprog21/lab0-c/commit/c48f908d6f6b5fbe63f2eb7ec76ad654f0935fdf)
- 利用 q_remove_head 完成，參數傳入往前移動兩次的 head，原本只往前一次但這樣不對，因為head是獨立一個節點。
```diff
+ if (!head || list_empty(head)) return NULL;
+ return q_remove_head(head->prev->prev, sp, bufsize);
```
#### q_reverse
>[commit Implement sort function](https://github.com/sysprog21/lab0-c/commit/a890963776dace80b9aa33240f74f8bbc8db4aac)
使用 `list_move` 來把節點移動佇列的最前端。
#### `q_reverseK`
>[commit Implement q_reverseK function](https://github.com/sysprog21/lab0-c/commit/b6bc68a324f052bfe1682cf8e2b98c16b10f0690)
運作方式是將佇列切割成三個部分，中間的子佇列會使用先前的 `q_reverse` 來做反轉的動作，在使用 `list_splice_init` 來將三者合併。
:::warning
雙層迴圈會有重複的問題，使函式的時間複雜度為 $O(n^2)$。
Reviewed by `marvin0102`
:::
一開始看 `list_cut_position` 沒有理解到 `node_from` 需要的指向開頭的指標，還有在 i = 0時，會是一個特例，使用 `list_cut_position(&left, &mid, end);` 會出現 segmemtation 錯誤，下面是更改的過程。
```diff
- list_cut_position(&mid, head, cur);
- list_cut_position(&left, cur, end);
+ list_cut_position(&mid, head, end);
+ if(i == 0)
+ list_cut_position(&left, head, cur);
+ else
+ list_cut_position(&left, &mid, cur);
```
#### q_delete_mid
> [commit Implement q_delete_mid function](https://github.com/sysprog21/lab0-c/commit/0419260f418dc164015882ae6ce3e6eae6f4f559)
- 一開始寫 free(indir)，但發現程式報錯空間仍然被佔據，使用 list_entry 取回刪除的節點，然後用 q_release_element 才正確。
#### `q_delete_dup`
> [commit Implement q_delete_dup function](https://github.com/sysprog21/lab0-c/commit/6b0b65ea893e40db41e54059d99d33e7dd3157e3)
下方是第一個想法直接的版本，儲存字串 `compare` 後進行比較，相同就刪除點，不同則更新 `compare`。因為避免當 `while` 最末端使用 `container_of` 在 `head` 上，對於此特例進行 `if (compare && cur->next == head)` 條件判斷。
這個版本相當不精簡，<s>之後會再改進</s>，老師說:「與其說「再改進」，不如闡述哪裡沒做好。」。
- 像是 `compare` 這個變數的使用是可以直接把 `curr_ela->value` 放入 `strcmp` 參數中進行比較，不需要多宣告這個變數。
- 也可以調整一些程式的順序，這樣閱讀起來比較具有可讀性。
#### q_swap
>[commit Implement sort function](https://github.com/sysprog21/lab0-c/commit/a890963776dace80b9aa33240f74f8bbc8db4aac)
本來想要使用間接指標來實作，或許以後會再嘗試。
#### q_sort()
>[commit Implement sort function](https://github.com/sysprog21/lab0-c/commit/a890963776dace80b9aa33240f74f8bbc8db4aac)
搭配另外兩個函式( `q_merge_two` 和 `q_mergesort` )完成此功能。
:::warning
能否透過改變合併時的條件達成 ascend 、 descend 的變換，以省略 `q_reverse` 函式呼叫。
Reviewed by `marvin0102`
:::
#### q_descend 和 q_ascend
>[commit Implement ascend and descend function](https://github.com/sysprog21/lab0-c/commit/cb4640d97bc853f2589263e00a96fd8b8713a471)
本來是使用 `list_first_entry` 來取出 `*prev_ele` 和 `*tmp_ele` 兩個指標，但是會出現 segmentation 錯誤。而 `q_ascend` 實作只有更動 `strcmp` 的比較條件為 `<` 而已。
`container_of` 會回傳指向包含該結構指標的`@type`型別指標，`list_first_entry`回傳指向佇列的第一個元素的指標
#### `q_merge`
> [commit 3d6e098](https://github.com/sysprog21/lab0-c/commit/3a3cc4ea12a8ce7014c60f92cab70e491ac2218b)
作業中第一次使用到 `queue_contex_t` 結構，直觀的用迴圈遍歷一次所有的佇列，都跟第一個佇列使用 `q_merge_two` 合併，再將 `second` 儲存的佇列使用 `list_move_tail` 移到最後。
---
# Valgrind + 自動測試程式
> 使用 Valgrind 來檢測是否發生記憶體流失（memory leak）
> - [作業要求](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b)
使用工具 [Massif](https://valgrind.org/docs/manual/ms-manual.html)，它是 Valgrind 支援的工具之一，用來分析記憶體使用狀況。
參考同學 [var-x](https://hackmd.io/@vax-r/linux2024-homework1#Massif)，將原先 Makefile 文件當中，存在著 check 指令，現在新增 check-massif:
```diff
check: qtest
./$< -v 3 -f traces/trace-eg.cmd
+ check-massif: qtest
+ valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd
```
上面命令最末端，要執行的文件 trace-massif.cmd 內容是對於 q_insert_tail 指令的測試，從 trace-17-complexity.cmd 文件修改而來:
```diff
- # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
+ # Test if time complexity of q_insert_tail is constant option simulation
it
- ih
- rh
- rt
option simulation 0
```
在執行命令 make check-massif 後，執行輸出的檔案（massif.out.xxxxx）後得到程式執行期間的記憶體消耗圖表:
```
圖表
```
消耗圖顯示總共做了 57 次的 snapshot(快照)，快照代表的是對某個時間點的記憶體使用情況的測量，57 次是對於每個heap(堆)分配/釋放一個快照，還有一些額外的快照，底部訊息第二行告訴我們 Detailed snapshot 紀錄的時間點是 1(peak), 24, 28, 32, 45, 50。
解釋這三種快照:
1. Normal snapshot: 以 '.' 來表示，記錄基本信息。
2. Detailed snapshot: 以 '@' 來表示，記錄了有關分配發生位置的信息。
3. peak snapshot: 以 '#' 來表示，每次至多只有一個峰值快照，他是消耗最多記憶體的點，同時他也是個 detailed snapshot。
接下來透過命令 `sudo apt install massif-visualizer` 下載工具後，執行 `massif-visualizer massif.out.5532`，把上方的圖弄得更漂亮，可以觀察到 peak 同樣是發生在第一個時間點:
# 研讀 Linux 核心原始程式碼的 lib/list_sort.c
將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 放到 lab0-c 目錄底下。
對於 `list_sort.c` 將傳入 cmp 參數拿掉，寫一個 `q_list_cmp` 函式來代替，一開始編譯時出現 `element_t` 結構體未定義的情況，才知道要引入 queue.h 標頭檔。
```diff
+ #include <queue.h>
- u8 count = 0;
+ uint8_t count = 0;
```
對於 list_sort.h 檔案新增兩個定義和定義資料型別 `uint8_t` 的標頭檔，以下是對檔案的改動:
```diff
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H
+ #define likely(x) __builtin_expect(!!(x), 1)
+ #define unlikely(x) __builtin_expect(!!(x), 0)
- #include <linux/types.h>
+ #include <stdint.h>
struct list_head;
-typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
- const struct list_head *, const struct list_head *);
__attribute__((nonnull(1)))
- void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+ void list_sort(struct list_head *head);
#endif
```
在 `qtest.c` 檔案中增加排序命令 lsort，並且增加 `do_lsort` 函式。
- command 是「命令」，而非「指令」(instruction)
```diff
+ bool do_lsort(int argc, char *argv[]){...}
+ ADD_COMMAND(lsort, "Use Linux kernel sorting algorithm", "")
```
這時我對於檔案執行 `make` <s>指令</s>命令，出現錯誤 `undefind reference to list_sort`，我反覆檢查確認已經在 qtest.c 和 list_sort.c 兩個檔案引入 list_sort.h，並且在兩個 list_sort 檔案的函式名稱以及參數都沒有錯誤，最後才發現要在 Makefile 加入 `OBJS` 變數，此變數告訴 Make 工具需要處理的所有目標<s>文件</s>檔案 的名稱。
- file 的翻譯是「檔案」，而非「文件」(document)
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
linenoise.o web.o \
+ list_sort.o
```
完成後建立 .cmd 檔案來對新<s>指令</s>命令進行測試:
```
# Test of new version of sorting list_sort
option fail 0
option malloc 0
new
ih RAND 50000
time
lsort
time
free
```
`$ make test` 執行結果如下:
```shell
$ scripts/driver.py -c
--- Trace Points
+++ TESTING trace sort_test:
# Test of new version of sorting list_sort
Elapsed time = 0.118, Delta time = 0.118
Elapsed time = 0.156, Delta time = 0.039
--- sort_test 5/5
--- TOTAL 5/5
```
- lsort 命令程式碼紀錄在 [commit 3d6e098](https://github.com/Lisa304/lab0-c/commit/3d6e0982c97f273b99eb58295483f9c2828f26d3)
- 除了增加 lsort 命令以外，還有新增 timsort 命令，timsort 程式碼紀錄在 [commit cb5eddd](https://github.com/Lisa304/lab0-c/commit/cb5edddcdad1c4183d2a28d2a1f018c77c33c103)。
# tic-tac-toe
> [作業要求](https://hackmd.io/@sysprog/linux2024-ttt#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
- 將 [jserv/ttt](https://github.com/jserv/ttt) 專案的程式碼部分整合進 lab0-c，並完成以下六個要求:
1. 將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出，成為 hlist.h
2. 修改 qtest 程式，使其新增 ttt 命令
3. 擴充上述 ttt 命令，在 qtest 引入新的 option
4. 針對 ttt 命令引入若干 coroutine
5. 嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益。
6. 針對「電腦 vs. 電腦」的對弈模式，統計不同 AI 實作機制對系統負載的使用率
## 整合 [jserv/ttt](https://github.com/jserv/ttt) 進入 lab0-c
將 ttt 專案中的部份程式碼（除了 elo.c 和 main.c 以外）複製進入 lab-0 專案當中，list.h 改名成 hlist.h。
在 console.c 文件中增加指令以及 do_ttt 函數，從 main.c 中取出片段成為 do_ttt 函數的內容，AI 是使用 MCTS，詳細程式碼可以看 [commit b03bbc5](https://github.com/Lisa304/lab0-c/commit/b03bbc5ffcd3926f0bf23aa672f53dd247a22753)，其中對於 AI 的動作選擇只先提取 MCTS 而已，因為初始只需使用 MCTS:
```diff
+ ADD_COMMAND(ttt, "Play Tic-Tac-Toc");
```
遇到的錯誤訊息：
**style: The scope of the variable 'mag01' can be reduced. [variableScope]**
這個警告表示變量 mag01 的作用域可以縮小。這通常意味著你可以將變量的定義放在其實際使用的地方，而不是在更廣泛的範圍內定義它。這樣可以提高代碼的可讀性和維護性。
**error: Null pointer dereference**
已經確定可以使用 MCTS 當作電腦的部份，跟人類玩井字遊戲，功能完成但是 commit 時不斷出現靜態分析工具的報錯，之前在作業二新增 timsort 命令時，也解決這問題很久，最後是在程式碼後方加上 `// cppcheck-suppress nullPointer` 來抑制警告訊息，但在這裡卻不能成功。
先使用 if 條件判斷式確定在使用 hlist_entry 前，hash_table[i].first 不為空，也無法解決。
在 ttt 專案中也是相同的寫法，為何我這裡無法通過靜態分析呢？
=> 可以在 pre-commit 文件裡，將程式檔抑制檢查:
```diff
+ --suppress=nullPointer:zobrist.c
```
- 整合後的程式碼是 [b03bbc5](https://github.com/Lisa304/lab0-c/commit/b03bbc5ffcd3926f0bf23aa672f53dd247a22753)
### 使用 Monte Carlo tree search (MCTS) 演算法
>確保使用定點數來取代原本 jserv/ttt 的浮點數運算。
**MC 和 MCTS**
MC「蒙地卡羅方法」是利用隨機抽樣技術進行模擬以解決數學問題的策略，而 MCTS 是 MC 加上 UCB (Upper Confidence Bound) 演算法。
由於遊戲是完全確定性的，因此可以用遊戲的所有可能結果建立一棵樹，樹的每個節點都給定一個值，確定每個玩家的獲勝或失敗比率。MCTS 在具有高分支因子的遊戲中表現出色，因為與需要完整博弈樹的 minimax 不同，MCTS 可以配置為在所需時間後停止，並且**可以基於部分構建**的博弈樹選擇足夠最優的解決方案。
**UCB**
而 MCTS 所使用的 UCB（Upper Confidence Bound），以一句話總結是他會以**信心區間來表示對於各節點的勝率的確信程度**。更新此區間的流程是會對一個節點進行多次測試，隨著測試次數增加對該節點的信心就會變得更加確定，數字上呈現的是，該節點的信心區間會縮小，所以就比較不會被選擇。
UCB值通常由兩部分組成，利用部分和探索部分。
- 利用部分(exploitation)：表示節點的平均獎勵值，即節點已經被訪問過的次數中獲得的平均獎勵值。
- 探索部分(exploration)：表示節點的探索程度，即節點被訪問過的次數的對數。
UCB公式將這兩個部分結合起來，通過加權平均計算節點的UCB值。這樣做的結果是，對於探索次數較少的節點，其UCB值會更大，從而促使算法更多地探索這些節點。同時，對於已經被訪問過多次且平均獎勵值較高的節點，其UCB值也會增加，從而確保算法能夠充分利用這些有潛力的節點。
**MCTS 有四個基本階段：選擇、擴展、模擬和反向傳播。**
- 選擇: 只會選擇沒有子節點且 UCB 最大的節點
- 擴展: 如果今天是 3*3 的井字遊戲，那麼在最一開始，根節點進行擴展後，會產生九個子節點
- 模擬: 就是執行到分出勝負為止
- 反向傳播: 將下面更新的值，不斷向上更新至根節點
- 1/1 模擬一場中贏了一場，傳上去給上一層的親代節點後，從 2/2 => 3/3，接下來 3/4 => 4/5，最後根節點是 5/9 => 6/10，在十場模擬中能夠贏六場，
**定點數取代原本的浮點數運算**
定點數用於表示實數的近似值。與浮點數不同，定點數的小數點位置是固定的，而不是隨著數字的大小而移動。
要將浮點數轉換成定點數，要先了解程式使用的數據範圍，再決定小數點要放在哪一位，如果要放在第四位，那麼全部的數字都要成上 2 的四次方，透過此轉換應該能提升效能，因為定點數的計算比較快且穩定(他不用四捨五入)。
觀察到現在程式中在分數方面以及 `simulate` 函數會使用到浮點數。
### 擴充上述 ttt 命令，在 qtest 引入新的 option
> 允許使用者切換「人 vs.電腦」或「電腦 vs. 電腦」的對弈，注意後者應該採取 MCTS 以外的演算法 (也可納入你發展的演算法)。
Sign in with Wallet
Connect another wallet