# 2024q1 Homework1 (lab0)
contributed by < [SHChang-Anderson](https://github.com/SHChang-Anderson) >
:::danger
不要寫錯自己的 GitHub 帳號名稱
:::
### Reviewed by `SimonLee0316`
* 在效能分析上面可以使用 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 來做
>想請問是針對那一個部份使用 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 進行分析? 在 [嘗試引入 lib/list_sort.c](https://hackmd.io/8ouUoyqPSVyDYcxD5g96oQ?view#%E5%AF%A6%E9%A9%97) 的實驗步驟中我使用了 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 進行 clock cycles 的分析，想請問您認為我對於這個部份可以進行跟多面向的實驗嗎？亦或是針對其他實作部份進行 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 效能分析？ 謝謝。[name=SH]
### Reviewed by `Shiang1212`
* 在實作佇列操作時，問題描述以及開發思路都紀錄得十分清晰明瞭，但在 commit 時卻沒有撰寫 commit message。即便該 commit 只有簡單的程式更動，仍應該在 commit message 中描述程式碼更動的重點，加速其他開發人員理解這份程式更動的脈絡，進而提高專案的可維護性。
## 開發環境
```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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
```
:::warning
將語系設定為 `C`，亦即執行 `export LC_ALL=C`，再執行上方的命令，這樣才會得到英文的訊息。
> 收到[name=SH]
:::
## 指定的佇列操作
### `q_new`
使用 `malloc()` 配置記憶體，再透過 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `INIT_LIST_HEAD()` 將該記憶體初始化為鏈結串列的開頭。
``` c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
return head;
}
return NULL;
}
```
嘗試精簡 `q_new` 程式碼，根據 C99 規格書原文摘錄如下 :
> *The left operand of a comma operator is evaluated as a void expression; there is a sequence point after its evaluation. Then the right operand is evaluated; the result has its type and value. If an attempt is made to modify the result of a comma operator or to access it after the next sequence point, the behavior is undefined.*
根據 C99 的規格書的內容，(INIT_LIST_HEAD(head), head) 這段程式碼中，逗號運算符左邊的 INIT_LIST_HEAD(head) 會先被執行，並將結果視為無效並丟棄，接著，逗號運算符右邊的 head 會被評估，這整個表達式的結果就是 head 。
```diff
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
- if (head) {
- INIT_LIST_HEAD(head);
- return head;
- }
- return NULL;
+ return head ? (INIT_LIST_HEAD(head), head) : NULL;
}
```
### `q_free`
`list_for_each_entry_safe` 是一個用於走訪雙向鏈結串列的巨集，並允許在走訪過程中安全地刪除目前節點的功能。
* entry：指向目前節點的指標。
* safe：指向目前節點的下一個節點的指標，確保下一個節點在刪除當前節點後仍然可被訪問。
* head：指向整個鏈結串列的起始點的指標。
* member：鏈結串列中不同項目的 list_head 成員變數的名稱。
一開始在實作過程中，考慮先釋放開頭節點的記憶體空間，然後再釋放開頭指標本身。但遇到 "Attempted to free unallocated block" 錯誤。經過思考後，發現 `list_for_each_entry_safe` 的過程已經處理了開頭指標內的指標的刪除。
```diff
void q_free(struct list_head *l)
{
if (l) {
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
q_release_element(entry);
}
- free(l->prev);
- free(l->next);
free(l);
}
}
```
修正後的程式碼：
```c
void q_free(struct list_head *l)
{
if (l) {
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
q_release_element(entry);
}
free(l);
}
}
```
### `q_insert_head`
`q_insert_head` 函式的目的是將一個 `element_t` 結構加入鏈結串列的開頭。在 queue.h 的註解中明確指出，我們必須配置足夠的記憶體空間以儲存字串 S，並將其複製到該空間，隨後再將這個 `element_t` 加入到鏈結串列。
作業說明中提到，在 C 語言中，字串是由連續的 `char` 型態物件排列而成，對於大多數硬體而言， `char` 型態的大小為 1 個 byte。為了存儲長度為 l 的字串，至少需要 l + 1 個 `char` 節點，最後一個用於存放結束符 `\0` 。因此，配置的空間大小應為字串長度 + 1 乘上 `char` 物件型態的大小。
此外，[linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 提供了 `list_add()` 巨集，用於將節點新增到鏈結串列中。需要特別注意的是，必須傳遞節點的 list 參數指標，而不是 list 本身。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = malloc(sizeof(element_t));
if (node) {
node->value = malloc(sizeof(char) * (strlen(s) + 1));
if (node->value) {
strcpy(node->value, s);
list_add(&node->list, head);
return true;
} else {
return false;
}
}
return false;
}
```
提交時，這段程式碼遇到以下問題：
* Dangerous function detected in strcpy(node->value, s);
* 出現 error: Memory leak: node [memleak] return false; 的錯誤，這可能是由於記憶體配置失敗後未釋放潛在的記憶體空間導致的。
根據 https://security.web.cern.ch/recommendations/en/codetools/c.shtml 了解到 strcpy 內建函式並不檢查緩衝區的長度。因此改用 strncpy 以提高程式碼的安全性。
同時，為了解決記憶體洩漏問題，需確保在動態記憶體分配失敗的情況下，進行適當的資源釋放。
修正後的程式碼：
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = malloc(sizeof(element_t));
if (node) {
node->value = malloc(sizeof(char) * (strlen(s) + 1));
if (node->value) {
- strcpy(node->value, s);
+ strncpy(node->value, s, (strlen(s) + 1));
list_add(&node->list, head);
return true;
} else {
+ free(node);
return false;
}
}
return false;
}
```
:::danger
使用 diff，而非列出完整程式碼。
:::
### `q_insert_tail`
[linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 提供了 `list_add_tail()` API，用於將節點新增到鏈結串列的結尾。用與 `q_insert_head` 相同的邏輯完成 `q_insert_tail`。
### `q_remove_head`
參閱 `queue.h` 中對於 `q_remove_head` 函式的註解，指出此函式的目的是移除鏈結串列的第一個節點。若字串指針 `*sp` 不為空且成功移除元素，則將被移除的字串複製至 `*sp` 中。在此上下文中，"remove" 表示解除元素的鏈接，且元素和字串所使用的空間應該保持未釋放的狀態。
根據規格書中 strncpy 函式的描述：
> The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1 If copying takes place between objects that overlap, the behavior is undefined.
由於 q_remove_head 註解中提到 bufsize 大小包含計算 `\0` 字符，因此我將 bufsize 作為 strncpy 函式的參數 n 進行字串複製。
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && head->next) {
element_t *removed_element = list_first_entry(head, element_t, list);
strncpy(sp, removed_element->value, bufsize);
head->next = removed_element->list.next;
return removed_element;
}
return NULL;
}
```
值得注意的是在 `q_remove_head` 的第 6 行程式碼，將 `head->next = removed_element->list->next;` 更正為 `head->next = removed_element->list.next;` 。這是因為 `removed_element` 是指向結構體的指標，而該結構體內含 `list` 的結構體，其中的 `list` 結構體擁有 `next` 的成員。因此，應使用 `removed_element->list.next` 來存取下一個指標，而非 `removed_element->list->next` 。
在重新檢閱 `q_remove_head` ，發現沒有使用到 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 提供的 API 將節點移除，這似乎有些奇怪。進一步觀察，發現 `list_del()` 僅刪除節點與鏈結串列的鏈結，不釋放被移除節點的記憶體。這和 `q_remove_head` 所要達成的目的相同。此外，由於這是一個雙向鏈結串列，使用 `list_del()` 可確保將節點徹底移出串列，因此更加適合此處的需求。
修改後的程式碼
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && head->next) {
element_t *removed_element = list_first_entry(head, element_t, list);
strncpy(sp, removed_element->value, bufsize);
- head->next = removed_element->list.next;
+ list_del(&removed_element->list);
return removed_element;
}
return NULL;
}
```
### `q_remove_tail`
`q_remove_tail` 實作的邏輯與 `q_remove_head` 類似，透過 `list_last_entry` 巨集取得最後一個節點的位置，將被移除的字串複製至 `*sp` 中，然後使用 `list_del()` 從鏈結串列中移除該節點。
### `q_size`
使用 `list_for_each` 走訪整個鏈結串列計算節點數量，若需要頻繁查詢鏈結串列的長度且對時間複雜度有高要求，可能導致執行 `q_size` 時花費大量時間。為提升效能，考慮在修改鏈結串列時同時維護一個計數器，使得在 `O(1)` 的時間複雜度下即可直接獲得鏈結串列的長度。
然而，上述做法需要額外空間來存儲計數器的資訊，需權衡是否值得花費額外空間以換取時間效能的提升。
### `q_delete_mid`
由於本作業所使用的是雙向鏈結串列，我宣告了兩個指標，一個指向鏈結串列的第一個節點，另一個指向鏈結串列的最後一個節點。透過這兩個指標，我能夠迅速地存取第一個節點與最後一個節點的位置。在操作中，這兩個指標不斷向著中心點移動，直到找到中間節點後將其刪除。
```c
bool q_delete_mid(struct list_head *head)
{
if (head) {
struct list_head *first, *last;
first = head->next;
last = head->prev;
while (first != head && last != head) {
if (first == last->prev || first == last) {
list_del(first);
q_release_element(list_entry(first, element_t, list));
return true;
}
first = first->next;
last = last->prev;
}
}
return false;
}
```
這引發了一個值得思考的問題：若在修改鏈結串列時同時維護一個計數器，就能夠在實作 `q_delete_mid` 時直接將計數器除以 2，並透過 for 迴圈找到需要刪除的節點，而無需另外創立一個 last 指標，這種作法不曉得是否有效益。
本想嘗試修改 `list.h` 加入一個計數器到 `list_head` 但提交時收到 [!] You are not allowed to change the header file queue.h or list.h 的警告，只好放棄此想法。
:::warning
本作業希望學員熟悉 List API
:::
### `q_delete_dup`
在已經排序好的鏈結串列上執行刪除重複的字串操作時，可能會因為排序的特性而提高效能。因此，我認為應該在完成 sort 實作後再回來處理刪除重複字串的部分。
完成排序後，仿照 `q_ascend` 和 `q_descend` 的實作方式進行處理。這裡我使用一個 `cur` 指標，它指向鏈結串列的前端節點。在走訪的過程中，我會比較 cur 與目前節點是否相同，如果相同，就刪除該節點。同時，我會檢查 `cur` 是否曾經與其他節點進行比較並且相同，如果是，我會刪除 `cur`，然後將 `cur` 設置為目前正在走訪的節點。
在實作過程中，我發現原來題目的要求和我一開始的理解有所不同。題目提到會傳入一個**已經排序好的鏈結串列**，而實際上所需完成的功能僅僅是將相鄰相同的節點刪除，無需在函式開頭先進行排序。這個錯誤的理解導致了測試持續失敗的問題。
此經驗讓我深刻體會到在開始實作之前，應該更仔細地閱讀並理解題目的要求，而不僅僅是大致了解。這是一個重要的教訓，未來我會更謹慎地處理題目，確保我對要求的理解是正確的。
```c
bool q_delete_dup(struct list_head *head)
{
if (list_is_singular(head))
return 0;
struct list_head *node, *safe;
char *cmp_str = list_entry(head->next, element_t, list)->value;
list_for_each_safe (node, safe, head) {
if(node != head->next) {
if (!strcmp(list_entry(node, element_t, list)->value,cmp_str)) {
list_del_init(node);
q_release_element(list_entry(node, element_t, list));
} else {
cmp_str = list_entry(node, element_t, list)->value;
}
}
}
return true;
}
```
以上程式碼模仿 `q_ascend` 和 `q_descend` 的實作方式，然而這樣會出現一個問題：被比較的節點並沒有被正確刪除，因此我需要進行改進。
```diff
{，，
if (list_is_singular(head))
return 0;
- struct list_head *node, *safe;
+ struct list_head *node, *safe, *cur;
char *cmp_str = list_entry(head->next, element_t, list)->value;
+ cur = head->next;
+ bool need_del = 0;
list_for_each_safe (node, safe, head) {
- if(node != head->next) {
- if (!strcmp(list_entry(node, element_t, list)->value,cmp_str)) {
- list_del_init(node);
- q_release_element(list_entry(node, element_t, list));
- } else {
- cmp_str = list_entry(node, element_t, list)->value;
- }
+ if (node != head->next) {
+ if (!strcmp(list_entry(node, element_t, list)->value, cmp_str)) {
+ list_del_init(node);
+ q_release_element(list_entry(node, element_t, list));
+ need_del = 1;
+ } else {
+ if (need_del) {
+ list_del(cur);
+ q_release_element(list_entry(cur, element_t, list));
+ need_del = 0;
+ }
+ cmp_str = list_entry(node, element_t, list)->value;
+ cur = node;
+ }
}
}
+ if (need_del) {
+ list_del(cur);
+ q_release_element(list_entry(cur, element_t, list));
+ }
return true;
}
```
為了刪除被比較的節點，程式碼變得非常冗長，可以再改進！
:::danger
列出改進的規劃。
>好的收到。[name=SH]
:::
目前程式碼合併相似有兩個相似的 if 判斷條件可以考慮合併。此外目前程式碼的邏輯有些冗餘，可以嘗試簡化。例如，可以先檢查 `need_del`是否為真，然後再進行後續操作，避免不必要的比較和刪除操作。
### `q_swap`
最初考慮使用 `list_for_each_safe` 巨集，將 `safe` 與 `node` 交換位置，實際實作後發現，由於這個鏈結串列是雙向的，這樣的操作會導致節點指標的混亂，並且無法持續地對下一組節點進行交換。
經過思考後，我想到一種方法：若我將一組節點透過 list_del 刪除後，再以順序相反的方式新增至鏈結串列的結尾，這樣不僅可以善用已經完成的功能，同時每次只需針對鏈結串列開頭的節點進行刪除並插入至結尾，就能達到預期的效果。刪除再新增至結尾的功能可以透過 `list_move_tail` 達成，因此使用 `list_move_tail` 完成 `q_swap`。
```c
void q_swap(struct list_head *head)
{
if (head && head->next != head && head->next->next != head) {
struct list_head *newhead = head->next->next;
list_move_tail(head->next->next, head);
list_move_tail(head->next, head);
while (head->next != newhead && head->next->next != newhead) {
list_move_tail(head->next->next, head);
list_move_tail(head->next, head);
}
if (head->next != newhead)
list_move_tail(head->next, head);
}
}
```
這樣的實作方式相對冗長，因為我將交換的節點加入至鏈結串列的末端。因此，我需要確認是否已經完成了節點的交換，同時避免無法進入 `while loop`。
```c
void q_swap(struct list_head *head)
{
if (head && head->next != head && head->next->next != head) {
struct list_head *newhead = head->next->next;
do {
list_move_tail(head->next->next, head);
list_move_tail(head->next, head);
} while (head->next != newhead && head->next->next != newhead);
if (head->next != newhead) {
list_move_tail(head->next, head);
}
}
}
```
使用 `do while` 不須避開進入 `while loop` 的條件，使程式更加簡潔。
:::warning
TODO: 嘗試善用 List API，撰寫出更精簡的程式碼
:::
### `q_reverse`
經過對 `q_swap` 的實作經驗，我認為反轉鏈結串列的過程可能和 `list_move` 或 `list_move_tail` 相關。因此，我進行了一些嘗試，透過從鏈結串列的開頭逐一將節點向前或向後移動，經過數次測試後發現，從鏈結串列的開頭逐一將節點向前移動最終會將鏈結串列反轉。
```c
void q_reverse(struct list_head *head)
{
if (head) {
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
}
```
在這段程式碼中，特別需要注意的是，不能使用 `list_for_each` 來走訪節點，因為操作中涉及到節點的刪除，導致無法繼續走訪。因此，更適合使用 `list_for_each_safe` 進行安全的節點走訪，以確保在操作過程中節點的正確移動。
### `q_sort`
參考 [Linked List Sort
](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge Sort 實作進行改寫，但有兩點需要修改：
* [Linked List Sort
](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge Sort 適用於單向鏈結串列，而本作業需要處理雙向鏈結串列。
* 本作業所使用的鏈結串列頭部內並沒有放資料，而 [Linked List Sort
](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge Sort 是基於節點內有資料進行排序的。
:::warning
注意超連結的參照，應有對應的主題名稱。
:::
因此，我需要對以上兩點進行修改，以符合雙向鏈結串列的特性，同時考慮到鏈結串列頭部不放置資料的情況。
在參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge Sort 進行修改時，主要的思路是新增一個空的鏈結串列。使用快慢指標找到中間的節點後，透過 `list_cut_position` 將一半的節點移動到新的鏈結串列中。在 merge 函式中，可以使用 list_add_tail 來取代原本連接節點的過程。
然而，在進行測試時，發現出現 "FATAL ERROR: Calls to malloc disallowed" 的錯誤，這表示無法使用 malloc 函數，因此無法建立更多的鏈結串列來實作 Merge Sort。
為了克服這個問題，需要討論在無法使用動態記憶體分配的情況下如何實作 Merge Sort。另外，也可以考慮修改原始的 Merge Sort 實作，以避免使用 `malloc` <s>函數</s>函式 。這可能需要重新思考演算法的結構，以符合無法動態分配記憶體的限制。
:::danger
對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 [time](https://man7.org/linux/man-pages/man2/time.2.html) 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
>收到，已修正。[name=SH]
:::
在進行測試後，我發現使用 `q_new` 來建立新的鏈結串列的開頭節點會遇到無法使用 `malloc` 的問題。然而，若我改為使用區域變數宣告一個額外的鏈結串列開頭節點，例如 `struct list_head newhead; INIT_LIST_HEAD(&newhead);`，這樣的方式可以成功編譯。這可能是因為這樣的宣告方式是使用區域變數，避免了對動態記憶體的需求，進而解決了 malloc 的問題。
當我用區域變數當作新鏈結串列串列的開頭的時候，我發現了一個問題。因為是用區域變數，所以 `merge` 結束之後的結果沒辦法回傳並正確接收結果，導致錯誤。
由於我實在想不到 merge 結束後的回傳方式，所以我參考了 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023#q_merge_two) 針對 merge_two 的實作方式，並加入了我自己的快慢指標分割串列的部分，待完成其他部份後再回來思考可能的解法。
:::danger
列出筆記的超連結，而非 `@`
>收到，已修正。[name=SH]
:::
### `q_ascend`
~~在檢視此部份的註解時，我注意到此部份不宜從鏈結串列的開頭節點開始走訪，因為這樣可能需要耗費大量時間在尋找鏈結串列至尾部。我認為更有效率的方式是從鏈結串列的尾部開始走訪，這樣能夠更迅速地找到右側的最大值。~~
~~考慮到從尾部開始走訪在 list.h 中並沒有提供相應的巨集，因此我認為一種解決方式是將整個鏈結串列進行反轉 `q_reverse`，然後刪除節點，最後再次進行反轉以達到預期的效果。~~
為了提高 `q_ascend` 功能的效率，直接從鏈結串列的開頭開始走訪是不太合適的。因為這樣需要經歷大量的步驟，才能到達鏈結串列的結尾，從而完成該功能。相反，如果從鏈結串列的結尾開始走訪，效率會更高。為了利用 `list_for_each_safe API` ，我先將串列反轉，使得走訪從尾部開始。直到走訪到最後一個節點後，再次將串列反轉，從而實現 `q_ascend` 功能。這樣的做法可以較好地利用 `list_for_each_safe` ，同時提高了效率。
```c
int q_ascend(struct list_head *head)
{
if (!head || head->next == head)
return 0;
q_reverse(head);
struct list_head *node, *safe, *cur;
cur = head->next;
list_for_each_safe (node, safe, head) {
if (strcmp(list_entry(node, element_t, list)->value,
list_entry(cur, element_t, list)->value) > 0) {
list_del_init(node);
q_release_element(list_entry(node, element_t, list));
} else
cur = node;
}
q_reverse(head);
return q_size(head);
}
```
:::danger
改進你的漢語表達。
:::
### `q_merge`
為了完成這個部分的工作,先需要了解整個系統中所有佇列的存取方式。在 `queue.h` 中定義了 `queue_context_t` 結構體,可以透過它獲取佇列的開頭節點及佇列的大小。我原本打算利用已實作的 `merge_two` 函數,針對每個佇列進行合併操作。但在實際執行過程中,發現一直存在記憶體未被確實釋放的問題。
最終，我參考了 [brianlin314](https://hackmd.io/@Brianlin314/lab0-2023) 的作法，採取了一種較為簡單的方式來完成 `q_merge` 這個功能。將所有佇列中的節點加入到第一個佇列中，再對整個佇列進行排序。以這種做法避開了之前遇到的記憶體管理問題，成功實作了佇列合併的需求，然而由於題目說明，需要 `merge` 的佇列都已經排序完畢，這樣的作法需要檢視是否會花費較多的時間。
:::danger
列出筆記的超連結，而非 `@`
>收到，已修正。[name=SH]
:::
### `q_reverseK`
在實作 `q_reverseK` 的過程中，我借鑒了先前在 `q_sort` 和 `q_descend` 的實作經驗。這些經驗讓我意識到，透過暫時鏈結串列的宣告方式以及呼叫其他已完成的函式，可以更有效地實作功能。同時，我也發現了使用 List API 的優勢。
初步思考 `q_reverseK` 時，我考慮將整個鏈結串列分解為以 k 個節點為一組的子串列，然後對這些子串列進行反轉。我使用一個臨時鏈結串列的開頭，透過計數器追蹤目前走訪的節點數量。當目前計數器的數量 % k 等於 0 時，表示已經走訪了 k 的倍數個節點。這時，我將這之前的所有節點移至另一個臨時鏈結串列，然後對這個臨時鏈結串列進行 q_reverse。最後，將反轉後的串列移至原始鏈結串列的結尾。這個步驟一直持續，直到計數器的數量與原始鏈結串列的節點數量相等為止。
```c
void q_reverseK(struct list_head *head, int k)
{
if (head && !list_is_singular(head)) {
struct list_head tmp_head;
INIT_LIST_HEAD(&tmp_head);
int ct = 0;
int size = q_size(head);
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
ct += 1;
if (ct % k == 0 || ct == size) {
list_cut_position(&tmp_head, head, node);
q_reverse(&tmp_head);
list_splice_tail_init(&tmp_head, head);
}
if (ct == size)
break;
}
}
}
```
## 檢討
目前剩下 `q_reverseK` 尚未完成，目前測試得分為:
> TOTAL 77/100
在不考慮尚未實作 `q_reverseK` 以及時間複雜度問題的情況下 `trace-07` `trace-08` 有出現問題，我決定先進行檢討。
### `trace-08`
`trace-08` 的錯誤主要來自於針對空鏈結串列 `remove_head` 與 `q_sort` ，`remove_head` 錯誤主要因為我使用 ` if (head && head->next)`，來判斷鏈結串列是否為空，然而此鏈結串列為雙向鏈結串列，因此不該使用 `head->next` 來作判斷，應使用 `list_empty(head)`。
```diff
- if (head && head->next)
+ if (head && !list_empty(head))
```
另外針對 `q_sort` 的問題，我並沒有判斷若鏈結串列沒有節點的情況，因此我需要加入以下判斷式。
```diff
+ if (!head || list_empty(head) || list_is_singular(head)) {
+ return;
+ }
```
以上更改後順利通過 `trace-08`
### `trace-07`
經過測試後發現，主要問題出於 `remove_head` ，我在實作 `remove_head` 時並沒有詳閱說明:
> *If sp is non-NULL and an element is removed, copy the removed string to \*sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*
題目的敘述為：若 `bufsize` 小於 `element.value` 的 size 要截斷字串並且補上結束字元。
```diff
- strncpy(sp, removed_element->value, bufsize);
+ strncpy(sp, removed_element->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
```
以上修正完畢後目前測試得分為:
> TOTAL 89/100
剩下 `trace-06` 以及 `trace-17` 尚未通過。
### `trace-06`
完成 `q_reverseK` 後順利通過 `trace-06` 。
截至完成最後一個功能後，測試得分為:
> TOTAL 95/100
剩餘 `trace-17` 尚未通過。
### `trace-17`
在執行 trace-17 測試時，我注意到 `remove_head` 函數出現了 `Segmentation fault occurred.` 的錯誤。我猜測可能是由於在處理傳入參數時沒有檢查是否為空指標的情況所導致。
在仔細檢查後，我發現在處理 `sp` 指標時沒有進行空指標檢查，這是一個嚴重的疏忽。在實現過程中，我們應該仔細檢查這些條件，以避免造成錯誤。以下是修改後的程式碼：
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *removed_element = list_first_entry(head, element_t, list);
- strncpy(sp, removed_element->value, bufsize - 1);
- sp[bufsize - 1] = '\0';
+ if (sp) {
+ strncpy(sp, removed_element->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
+ }
list_del(&removed_element->list);
return removed_element;
}
return NULL;
}
```
實作時應注意空指標檢查，確保在處理時不會出現未定義的行為。
最後以同樣的方式修改 `q_remove_tail` 最終通過 `trace-17` 測試。
> TOTAL 100/100
---
## 研讀並嘗試引入 Linux 核心原始程式碼的 `lib/list_sort.c`
### 嘗試引入 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) 引入本專案中，將這兩個檔案放入專案資料夾。在進行編譯時，遭遇一些錯誤。
一開始，出現與 include 相關的錯誤，檢查是否有多餘或不必要的 include 指令。這樣的刪減可以簡化專案結構並減少錯誤發生的機率。
若在編譯過程中遭遇到 `unknown type name ‘u8’` 的錯誤，查看相關定義。在 [linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 中，u8 被定義為 `uint8_t`，而 `uint8_t` 是由 `stdint.h` 提供的。因此在 `list_sort.h` 中新增 `#include <stdint.h>` ，以確保相關型別的定義正確。
```diff
- u8 count = 0;
+ uint8_t count = 0;
```
```diff!
+ #include <stdint.h>
```
接著，我遇到了一個警告： `warning: implicit declaration of function ‘unlikely’` 。經過查閱 [/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 後發現，likely 與 unlikely 是兩個已經被預先定義好的巨集。參考 [[Linux Kernel慢慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) 中對 likely 與 unlikely 的解釋，我了解到這兩個巨集可在編譯器編譯組合語言代碼時進行最佳化。它們可通過將組合語言代碼進行移動，以優化程式碼結構，以空間局部性（Spatial Locality）降低快取未命中（cache miss）的可能性。
```diff
+ # define likely(x) __builtin_expect(!!(x), 1)
+ # define unlikely(x) __builtin_expect(!!(x), 0)
```
最後修改 `makefile` 使 `list_sort.c` 可以正常編譯。
`list_sort.c` 的設計中須傳入 `cmp` 比較函式，我參考了 ＠gaberplaysgame 實作 `q_list_cmp` 的方式將此函式放入 `list_sort.c` 中，並刪除了 `cmp` 的傳入參數。
新增 `lsort` 指令進入 `qtest.c` 中，並模仿 `do_sort` 的實作方式完成 `do_lsort` 。
```diff
+ ADD_COMMAND(lsort, "Use Linux kernel sorting algorithm", "");
```
### 實驗
參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#%E6%95%88%E8%83%BD%E6%AF%94%E8%BC%83) 的實驗方式，先隨機產生 500000 個字串加入到鏈結串列中，使用不同的 `perf` 效能分析工具分析兩種不同的排序方式效能上的差異，此外，我加入了 cache-misses 的觀察。
sort_test.cmd:
```
option fail 0
option malloc 0
new
ih RAND 50000
time
sort/lsort
time
free
```
**執行時間**
* 我實作的排序演算法：
|q_sort|Execuate Time|
|-|-|
|1|1.2210s|
|2|1.2000s|
|3|1.1290s|
|4|1.1400s|
|5|1.1280s|
每次執行平均產生了 53,193,626 cache-misses
* list_sort：
|q_sort|Execuate Time|
|-|-|
|1|1.043s|
|2|0.969s|
|3|0.987s|
|4|0.966s|
|5|0.953s|
每次執行平均產生了 44,604,156 cache-misses
根據上述實驗結果，相較於我自己實作的排序演算法，list_sort 在執行時間和快取失效次數方面均呈現出更佳的效能表現。
接著我撰寫了一支程式用來測試兩種排序方式再不同的節點數量下，所花費的 cycles 數量差距，主要的撰寫方式是修改 sort_test.cmd 中產生隨機字串的數量，並執行`perf` 效能分析工具分析不同的節點數量花費的 clock cycles 數量，最後產生結果。
> commit [291d60a](https://github.com/sysprog21/lab0-c/commit/291d60ad3fcffb930caca26ef70c7686cdf6b32d)
不同節點數量下，兩種排序方式花費的 clock cycles 數量。
不同節點數量下，兩種排序方式產生的 cahce misses 數量。
由於 100000 個節點時產生的 cahce misses 數量差距不大，因此實驗新增至 500000 個節點作比較。
由結果可觀察，節點逐漸增加的情況下，兩種排序方式花費的 cycles 數量差距會逐漸增加，而在大多情況下， `list_sort` 的 cahce misses 數量也小於我所實作的排序方式。
### Linux Kernel Linked List 排序演算法探究
[linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 中 `list_sort`、 `merge` 、和 `merge_final` 函式的設計與一般的合併排序算法有一些不同之處:
* **單向鏈結串列的使用** :`list_sort` 在操作排序前，事先將鏈結串列改為單向鏈結串列，使得在操作的過程中節省空間，並提高操作效率。
* **Bottom-Up 合併演算法** : `list_sort` 使用了 Bottom-Up 合併演算法，與傳統的 Top-Down 合併排序演算法相比，可以減少分割的步驟，節省了時間。
* **合併方式的優化** : `list_sort` 在進行合併時，根據走訪過的節點數量來控制合併的時機。只有當走訪節點數量達到一定程度時，才會進行合併操作 ( 參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84-liblist_sortc) 對於 `list_sort` 合併的解釋)。這樣的設計確保了兩個子串列的數量能夠保持平衡，從而降低了比較的次數。同時，這樣的合併方式有助於避免 Cache Thrashing 的問題，提高了效率，也進而印證了實驗結過中，`list_sort` cache misses 數量較低的情況。
---
## Fisher–Yates shuffle 演算法
### 在 `qtest` 提供新的命令 `shuffle`
事先閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 以及作業說明對於 Fisher–Yates shuffle 演算法的說明，實作出來並加入 `qtest` 命令。
> commit [26fafd6](https://github.com/sysprog21/lab0-c/commit/26fafd698f4d692298b835a4f49d7666d3afd93d)
```
cmd> new
l = []
cmd> ih RAND 10
l = [gkubgpty wcqqn djnvqbr grxjr zodqki hwnlc ieglduo evemzt cssla pfumgx]
cmd> shuffle
l = [djnvqbr hwnlc grxjr cssla wcqqn pfumgx evemzt gkubgpty zodqki ieglduo]
cmd> shuffle
l = [ieglduo grxjr wcqqn hwnlc gkubgpty zodqki pfumgx evemzt djnvqbr cssla]
```
### 統計的原理分析亂度
透過統計原理進行分析並在實驗過程中發現，我先前所撰寫的 Fisher–Yates 洗牌算法程式存在錯誤。主要問題出在邊界條件未被清楚設定，導致無法生成特定種類的排列。因此，我重新審視了程式碼並進行改進。
修正後的 shuffle 演算法程式：
> commit [4a14c27](https://github.com/sysprog21/lab0-c/commit/4a14c27cdf0ecc8b2ca3cd29057789b9b9d6caca)
閱讀了作業說明中對於 [統計方法驗證 shuffle](https://hackmd.io/@sysprog/linux2024-lab0-d#%E7%B5%B1%E8%A8%88%E6%96%B9%E6%B3%95%E9%A9%97%E8%AD%89-shuffle) 的方式後，理解到了某特定事件在樣本中觀察到的頻率分佈與特定理論分佈一致，事件必須是互斥且機率為 1，觀察到的頻率與測試出的頻率應相符。
我透過 python 撰寫測試程式用來測試 shuffle 後產生的鏈結串列是否符合 Uniform distribution 。我建立了一個鏈結串列放入 a b c 三個節點，紀錄下產生的鏈結串列節點順序，並透過圖表呈現分佈情況。
> commit [849551c](https://github.com/sysprog21/lab0-c/commit/849551c8cb255822200f4605365e7971249ad015)
測試 10 萬次的分佈情形：
測試 20 萬次的分佈情形：
測試 40 萬次的分佈情形：
---
## 〈Dude, is my code constant time?〉
### 研讀論文
本篇論文詳細探討了 `dudect` 這一工具，它被用於檢測程式是否以常數時間運行，從而闡明了計時攻擊（Timing attacks）所帶來的安全隱患。通過分析 dudect 的工作原理和應用，確保程式執行時間不受處理數據影響的重要性。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
>收到，已修正。[name=SH]
:::
- 輸入兩組不同類型的實驗數據:一組為固定值，另一組為隨機產生的值。這種對照測試稱為 fix-vs-random 測試，用於檢測潛在的時間洩漏問題。
- 使用 Welch's t-test 和非參數檢驗 (Non-parametric tests) 兩種方法，檢驗 "兩組時間分布相等" 的虛無假設是否成立。
- Welch's t-test 是檢測程式是否符合 constant time 的常用方法。它主要測試兩個獨立樣本常態分佈的平均值差異是否顯著。首先計算兩組樣本平均值和樣本方差，根據公式計算 $t$ 統計量。若 $t$ 值接近0，則兩組數據差異較小。然後根據自由度計算 p 值,若 p 值小於預設閥值，則拒絕虛無假設，即兩組數據有顯著差異。
- 非參數檢驗不假設數據遵循任何特定分佈，如 Kolmogorov-Smirnov 檢驗。它直接分析數據的分布差異，無需滿足常態分佈等前提條件。
### dudect.h 探討
接著我針對 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 進行探討，首先觀察到 `dudect_ctx_t` 結構體，此結構體用於儲存配置、輸入數據、執行時間等訊息。在 `dudect_main` 中會使用 `prepare_inputs` 來處理準備輸入的數據。接著會執行 `measure` 函式：
```c
static void measure(dudect_ctx_t *ctx) {
for (size_t i = 0; i < ctx->config->number_measurements; i++) {
ctx->ticks[i] = cpucycles();
do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
}
for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
}
}
```
在 `measure` 程式碼中可以觀察到存在兩個迴圈，第一個迴圈會執行 `ctx->config->number_measurements` 次迭代並紀錄下每次迭代前當下的 cpu cycle，接著使用 `do_one_computation` 傳入資料並執行。再第二個迴圈會解析出每次執行的時間以便接下來的執行時間分析。
接著程式會檢查 `ctx->percentiles` 是否初始化，若尚未初始化，將執行 `prepare_percentiles` 。
```c
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
`prepare_percentiles` 先將執行時間進行排序，接著從排序後的 `ctx->exec_times` 執行時間資料中給定百分位數對應的值。
我猜測這樣的作法目的在於計算出一系列執行時間閾值，用於後續過濾極端值(outliers)。通過設置不同的閾值，可以有選擇地過濾掉測量值中的極端大值或極端小值，從而獲得更加準確的統計結果。
最後 `report` 函式會根據更新後的統計數據生成報告，判斷被測試函數在不同輸入下的執行時間是否存在顯著差異。如果存在差異，就有可能存在潛在的時間側信道漏洞風險;反之，則被測試函數可能是恆定時間執行的。該函式的回傳值 `ret` 表示這一輪測試的最終結果。
整個過程是一個迭代的統計檢測，透過不斷收集新的測量數據、更新統計數據、設置合理的閾值過濾極端值，最終得出被測試函數是否存在 Timing leakage 風險。
### 專案中的測試程式探討
接著我看到本專案中 `dudect` 的部份，本專案會將 `simulation` 設為 1 以進行效能的測試，接著執行 `it` `ih` `rh` `rt` 對 `insert tail` 、 `insert head` 、 `remove head` 、 `remove tail` 分別進行效能的評估。
在本專案的 [dudect/fixture.c](https://github.com/sysprog21/lab0-c/blob/master/dudect/fixture.c) 中，我發現了 `doit` 這個函式實現了與 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 主要實現功能類似，因此我針對這部份作更深入的探討。
在 `doit` 函式中，首先呼叫 `prepare_inputs` 準備了欲輸入測試的使用的資料，接著去測量執行程式的時間並紀錄，值得注意的是 `measure` 函式中，針對不的插入或刪除功能進行測量，紀錄測試前 CPU cycles 與測試後的 CPU cycles 數量。測試結束後使用 `differentiate` 計算每一次測試的執行時間，更新數據之後產生最終的結果。
我比較了專案中的測試程式與 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的測試方式發現，專案中的測試程式少了 `prepare_percentiles` 這個部份，因此我猜想本專案的程式並沒有針對極端值進行過濾，為了驗證我的猜想，我重新審閱了 [dudect/fixture.c](https://github.com/sysprog21/lab0-c/blob/master/dudect/fixture.c) 程式碼中 `prepare_percentiles` 程式將計算出的閥值存入 `dudect_ctx_t` 結構體中 `percentiles` 陣列內，我追蹤程式對於 `percentiles` 的處理，發現在 `update_statistics` 函式中使用到了這個閥值。
```c
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
```
`update_statistics` 主要的實作方式是捨去前 10 個測量的值，接著透過一個迴圈來處理多個不同的閾值，檢查執行時間是否小於這些閾值。如果執行時間低於閾值，這個時間差異就被記錄下來，用於後續的統計分析，而大於閾值的數據就會被剔除過濾測量到的極端數值。
接著我對比專案的程式碼比較差異。
```c
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
觀察 `fixture.c` 可以發現在 `update_statistics` 並沒有對資料集進行以上閥值的探討。
為了改進這個部份，我需要先實作 `prepare_percentiles` 這個功能，我仿照了 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的作法完成 `prepare_percentiles` 實現，以及在 `update_statistics` 執行前先執行 `prepare_percentiles` 以實現前面所探討的功能。
> commit [197e5c8](https://github.com/sysprog21/lab0-c/commit/197e5c8ab933bdf9512d11c6851e88942642dbba)
修改完畢後再次執行 `make test` 發現 `q_insert_tail, q_insert_head` 成功通過測試，然而測試 `remove_head` 卻又發生 `Segmentation fault occurred. You dereferenced a NULL or invalid pointer` 的錯誤，因此我重新審閱檢討 `remove_head` 程式碼。
>[檢討 `trace-17` ](https://hackmd.io/8ouUoyqPSVyDYcxD5g96oQ?view#trace-17)
## 整合 tic-tac-toe 遊戲
### 將 jserv/ttt 專案的程式碼部分整合進 lab0-c
首先，從 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中提取與雜湊列表相關的標頭檔，並將其添加到 `lab0-c` 專案中。
> commit [6b5c6df](https://github.com/SHChang-Anderson/lab0-c/commit/6b5c6dfda3ab079329b5012a1430b0e54494edf1)
:::danger
command 是「命令」，而非「指令」(instruction)
:::
將 `hlist.h` 加入專案後，需要新增 `ttt` 命令以執行人機對戰的井字遊戲。我先暫時移除與強化學習相關的功能，然後從 [jserv/ttt](https://github.com/jserv/ttt) 的 `main.c` 檔案中提取與遊戲相關的程式碼到專案中的 `console.c`。接著，新增<s>指令</s>命令 `ttt` 以開始遊戲。當輸入指令 `ttt` 後，將繼續執行原始 `main.c` 中的內容，以啟動井字遊戲。
<s>
</s>
```
cmd> ttt
1 |
2 |
3 |
4 |
---+-------------
A B C D
X>
```
:::danger
文字訊息不要用圖片展現。
:::
> commit [44a563f](https://github.com/SHChang-Anderson/lab0-c/commit/44a563f861ffbf299a36942df7bba1b0eb36c64b)
### MCTS 探究
蒙地卡羅搜尋樹 (Monte Carlo Tree Search,MCTS) 是一種在不完全訊息或不確定性環境下進行決策的演算法，已經在許多領域取得了成功應用，包括棋類和桌上遊戲。MCTS 通常適用於具有巨大搜索空間和高度複雜性的遊戲。
MCTS 結合了蒙地卡羅方法和搜索樹方法，透過模擬大量的遊戲對局來評估每個可能的移動和決策。MCTS 的核心思想是通過擴展和模擬遊戲樹來搜索最佳的行動。它使用一個樹狀結構來表示遊戲的狀態和可能的行動，並使用蒙地卡羅模擬來估計每個行動的價值。MCTS 通過不斷擴展和選擇最有潛力的節點來探索遊戲空間，同時使用 backpropagation 來更新節點的評估結果。
以下為實際操作步驟:
* Selection : 從目前的遊戲決策樹中選擇一個節點進行擴展。通常採用 Upper Confidence Bound (UCB) 的策略來平衡探索和利用性。
* Expansion : 對選擇的節點進行擴展，產生可能的子節點。這些子節點代表了遊戲中的可能行動。
* Simulation : 對每個子節點進行模擬，模擬遊戲的隨機對局直到達到終止條件。通常使用蒙特卡羅模擬來生成隨機對局。
* Backpropagation : 將評估結果回溯更新到<s>父節點</s>親代節點和祖先節點中，以更新整個遊戲樹。
:::danger
避免父權主義的遺毒，應將 parent node 翻譯為「親代節點」，而非「父節點」或「母節點」，不僅更中性，也符合英文原意。若寫作「父」，則隱含「母」的存在，但以二元樹來說，沒有這樣成對關連性。若用「上代」會造成更多的混淆，在漢語中，「上一代」沒有明確的血緣關係 (例如「[炎黃子孫](https://dict.revised.moe.edu.tw/dictView.jsp?ID=155219)」與其說是血緣關係，不如說是傾向文化認同)，但「[親](https://dict.concised.moe.edu.tw/dictView.jsp?ID=25345)」的本意就是指名血緣和姻親關係。
> 延伸閱讀: [「新中國」和「中華民族」—— 梁啟超悔之莫及的發明](https://www.thenewslens.com/article/122516)
$\to$ [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)
:::
### 引入 MCTS 方法並改用定點數做計算
將 MCTS 方法從浮點數修改為定點樹之前，首先先將原始的 MCTS 整合進 `lab0-c` 專案中，使玩家可以和電腦對對弈。
成功引入 MCTS ，並測試沒問題後準備提交時卻出現以下警告：
```
agents/mcts.c:147:21: warning: Possible null pointer dereference: best_node [nullPointer]
int best_move = best_node->move;
^
agents/mcts.c:139:30: note: Assignment 'best_node=NULL', assigned value is 0
struct node *best_node = NULL;
^
agents/mcts.c:142:31: note: Assuming condition is false
if (root->children[i] && root->children[i]->n_visits > most_visits) {
^
agents/mcts.c:147:21: note: Null pointer dereference
int best_move = best_node->move;
^
agents/mcts.c:67:10: style: The scope of the variable 'win' can be reduced. [variableScope]
char win;
^
```
閱讀並分析這些錯誤後得到幾個啟發，首先 `agents/mcts.c:147:21: warning: Possible null pointer dereference: best_node [nullPointer] int best_move = best_node->move;`
這個警告表示在 `main` 函式中存取 `best_node` 時，可能會出現空指標的情況。因此應該要使用一些條件判斷，或其他方式避免可能出現空指標出現引發錯誤。
```diff
- int best_move = best_node->move;
+ int best_move = -1;
+ if (best_node)
+ best_move = best_node->move;
free_node(root);
return best_move;
```
再來 `agents/mcts.c:67:10: style: The scope of the variable 'win' can be reduced. [variableScope] char win;`
這是一個風格建議，指出 `win` 變數的作用域可以減小，以提高程式的可讀性和效率。我將嘗試將變數 `win` 宣告在作用的迴圈內以提高可讀性。
```diff
static double simulate(char *table, char player)
{
- char win;
char current_player = player;
char temp_table[N_GRIDS];
memcpy(temp_table, table, N_GRIDS);
while (1) {
+ char win;
int *moves = available_moves(temp_table);
```
修改以上問題後不再出現警告，成功提交。
> commit [ae42aec](https://github.com/sysprog21/lab0-c/commit/ae42aecfb238de7ecaab30082ecf9758e1491092)
將 MCTS 方法引入 lab0 專案中作為電腦對手後，接著針對 MCTS 方法中使用到浮點數的部分進行修改，我觀察了程式碼發現有以下幾個部分需要做修改:
* `struct node`: MCTS 使用 `double` 資料型態儲存分數參數，我認為將其改為 `int64_t` 是可行的方法，使得 `score` 成為足夠大的整數型態。
* `uct_score`: 計算 UCT 也需要將其改為整數型態的運算，比較需要思考的是如何用整數進行開根號運算以及整數取對數的方式。
* `simulate`: 當模擬局面平手時，需要回傳浮點數 `0.5` 應該要針對此部分改為整數型態回傳。
閱讀作業說明中對於 [linux/kernel/sched/loadavg.c](https://elixir.bootlin.com/linux/v5.3/source/kernel/sched/loadavg.c#L110") 中 `fixed_power_int` 的說明，了解到我或許可以模仿其中的實作方式，以二進位來思考進行定點數的計算。
若將除法的部份改為 bitwise 操作，可以解決浮點數運算問題，若是除以 2 的操作，向右移動一個 bit 即可，然而 `num / x` 無法使用這樣的方式進行，因此需要實作 bitwise 除法函式解決這個問題。
參考 [Mips Division](https://hackmd.io/@sysprog/cpu-arch-lecture#MIPS-Division) 實現 bitwise 的除法功能。
```c
unsigned divide(unsigned num, unsigned divisor) {
if (divisor == 0) {
return 0;
}
unsigned quotient = 0;
unsigned remainder = 0;
for (int i = 31; i >= 0; i--) {
remainder <<= 1;
remainder |= (num >> i) & 1;
if (remainder >= divisor) {
remainder -= divisor;
quotient |= (1 << i);
}
}
return quotient;
}
```
主要的實作概念是比較 `remainder` 和除數 `divisor` 的大小。如果 `remainder >= divisor` ，可以將目前商數位設為 1 ，因此用 `remainder -= divisor` 減去一個除數，並用 `quotient |= (1 << i) `將目前商數位設為 1。
經過後來的思考，發現乘法和除法操作似乎不需要像那麼複雜。可以使用 `fixed_power_int` 所描述的方法,在執行乘法或除法運算後，進行位移 (shift) 操作來修正結果。因此，我將乘法和除法分別寫成了函數，以便後續的調用。
```c
unsigned long fixed_mul(unsigned long a, unsigned long b)
{
unsigned long long tmp = (unsigned long long) a * b;
return (unsigned long) ((tmp + (1U << (FIXED_SCALE_BITS - 1))) >>
FIXED_SCALE_BITS);
}
```
```c
unsigned long fixed_div(unsigned long a, unsigned long b)
{
unsigned long long tmp = ((unsigned long long) a << FIXED_SCALE_BITS) / b;
return (unsigned long) tmp;
}
```
在建置完成上述函式後，我開始修改 `mcts.c` 檔案。我設計了一個 `FIXED_SCALE_BITS` 作為位移量，並將其設定為 15，同時將 `score` 設為 `unsigned long` 型態，以儲存更多的浮點數位元資訊。接著，我將計算 UCB (Upper Confidence Bound) 的相關數學計算都改為使用自行撰寫好的定點數計算操作。
在完成程式修改後，我進行測試，發現若使用定點數計算，在一開始計算 UCB 時，由於使用定點數計算而忽略了小數位，很容易導致計算出的 UCB 值為 0。這會造成程式在選擇 (selection) 時找不到節點進行選擇。另外，由於 `unsigned long` 的最小值為 0，當所有子節點的 UCB 值皆為 0 時，將找不到最佳節點。因此，為了排除這個問題，我新增了一個條件判斷，若全部的子節點皆為 0 時，則隨機選擇一個子節點繼續模擬。
```c
if (!best_node) {
while (1) {
best_node = node->children[rand() % N_GRIDS];
if (best_node)
break;
}
}
```
最終將修改過方法引入專案中。
> commit [701981b](https://github.com/sysprog21/lab0-c/commit/701981bf3598bb510d8211b576f56dee1a75af81)
:::danger
補上對應的數學分析，與雙精度浮點數的誤差比較。
:::
### 浮點數與定點數的分析探討
關於浮點數與定點數的分析探討，在原始的蒙地卡羅樹搜索 (MCTS) 方法實作中，使用 double 資料型態來儲存與計算score,也就是蒙地卡羅樹搜索中的 UCB 計算值。而 IEEE 754 對於[雙精度浮點數](https://en.wikipedia.org/wiki/Double-precision_floating-point_format)有明確的規範。
相較於單精度浮點數僅有 32 位元 (4個位元組)，雙精度浮點數使用 64 位元(8個位元組)來儲存一個浮點數，它可以表示二進位制的 53 位有效數字，其可以表示的數字絕對值範圍為 $[2^{-1024}, 2^{1024}]$。
在我的實作方法中,我使用了 `unsigned long` 儲存 `score` 資訊，[C 資料型態](https://en.wikipedia.org/wiki/C_data_types)中說明 `unsigned long` 表示的數字絕對值範圍為 $[0, 4294967295]$。由於不需要儲存負數，因此有足夠範圍來進行定點數的數學計算以及位移運算。
在實作浮點數與定點數的轉換過程，須 `FIXED_SCALE_BITS` 的位移量大小，因此我想要探究在不同的 `FIXED_SCALE_BITS` 下，浮點數與定點數計算出的結果會有多大的誤差。
### 定點數的 `log` 與 `sqrt` 實作
在完成上述的程式乘除法實作後，還缺少對於 `log` 以及 `sqrt` 的定點數實作。
參考 [Natural logarithm](https://en.wikipedia.org/wiki/Natural_logarithm) 中的敘述，可以了解到自然對數可以使用泰勒展開是進行近似。
${\displaystyle {\begin{aligned}\ln(x)&={\frac {2(x-1)}{x+1}}\sum _{k=0}^{\infty }{\frac {1}{2k+1}}{\left({\frac {(x-1)^{2}}{(x+1)^{2}}}\right)}^{k}\\&={\frac {2(x-1)}{x+1}}\left({\frac {1}{1}}+{\frac {1}{3}}{\frac {(x-1)^{2}}{(x+1)^{2}}}+{\frac {1}{5}}{\left({\frac {(x-1)^{2}}{(x+1)^{2}}}\right)}^{2}+\cdots \right)\end{aligned}}}$
在這個泰勒展開近似中，我可以使用我實作完成的定點數乘除法功能實現 log 近似。
```c
unsigned long fixed_log(unsigned long x)
{
unsigned long x_plus_1 = x + (1U << FIXED_SCALE_BITS);
unsigned long x_minus_1 = x - (1U << FIXED_SCALE_BITS);
unsigned long denominator = fixed_div(x_minus_1, x_plus_1);
unsigned long term;
unsigned long result = 1U << FIXED_SCALE_BITS;
unsigned long ratio = fixed_mul(denominator, denominator);
unsigned long k = 1;
while (1) {
term = fixed_div(ratio, ((2 * k + 1) << FIXED_SCALE_BITS));
if (k > 10)
break;
result += term;
ratio = fixed_mul(ratio, ratio);
k++;
}
result <<= 1;
return fixed_mul(result, denominator);
}
```
使用 `restore_double` 函式將定點數 log 運算結果恢復為雙精度浮點數做比較。
```c
double restore_double(unsigned long tmp) {
double scaled_tmp = (double)tmp;
return scaled_tmp / pow(2, FIXED_SCALE_BITS);
}
```
實驗比較定點數計算 log 與 雙精度浮點數計算 log 的誤差。
實驗結果顯示數值超過 20 時，將會產生較大的誤差，目前猜測原因為定點數的乘除法會造成精度的損失，需要設法解決此問題。
### 實作電腦 vs. 電腦
引入 `Negamax` 方法與 `MCTS` 方法進行電腦與電腦對戰並加入一個顯示時間的函式，在每個決策開始前顯示時間。
```c
void display_current_time() {
time_t current_time;
struct tm* time_info;
char time_string[80];
current_time = time(NULL);
time_info = localtime(¤t_time);
strftime(time_string, sizeof(time_string), "%Y-%m-%d %H:%M:%S", time_info);
printf("Current Time: %s\r\n", time_string);
fflush(stdout);
}
```
```
Current Time: 2024-03-19 22:04:29
1 |
2 | ×
3 | ○ ×
4 |
---+-------------
A B C D
Current Time: 2024-03-19 22:04:29
1 |
2 | × ○
3 | ○ ×
4 |
---+-------------
A B C D
Current Time: 2024-03-19 22:04:29
1 |
2 | × ○
3 | ○ ×
4 | ×
---+-------------
A B C D
Current Time: 2024-03-19 22:04:29
1 | ○
2 | × ○
3 | ○ ×
4 | ×
---+-------------
A B C D
```
以上實作完成提交時不斷出現:
```
zobrist.c:63:17: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
^
Fail to pass static analysis.
```
參考 var-x 同學的 [commit 紀錄](https://github.com/sysprog21/lab0-c/commit/7ed7190ef6deec2dbaf9100ba81a231a339cb35b#diff-2bb15801e367b215fa5f060dc9d93329346560591dcdaaf21ac8f38fd8488a71) 才知道要修改 `scripts/pre-commit.hook`，才能避免出現這個錯誤。
```diff
--suppress=nullPointerRedundantCheck:harness.c \
--suppress=nullPointer:queue.c \
--suppress=nullPointer:qtest.c \
+ --suppress=nullPointer:zobrist.c \
--suppress=returnDanglingLifetime:report.c \
--suppress=constParameterCallback:console.c \
--suppress=constParameterPointer:console.c \
```
參考 [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf) 中對於 suppress 的敘述 :
>If you want to filter out certain errors from being generated, then it is possible to suppress these.
If you encounter a false positive, then please report it to the Cppcheck team so
that it can be fixed.
如果想要避免不想產生的錯誤，可以使用 `suppress` 避免這些錯誤訊息出現，最終成功提交。
> commit [3a1c25c](https://github.com/sysprog21/lab0-c/commit/3a1c25c582400640e59fb9850c2aa7e0d7978299)
### 並行程式理解
閱讀 [coroutine 實作體驗-協同式多工](https://hackmd.io/@sysprog/concurrent-sched#coroutine-%E5%AF%A6%E4%BD%9C%E9%AB%94%E9%A9%97) 嘗試理解 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 的實作方式。
在 [coro.c](https://github.com/sysprog21/concurrent-programs/blob/master/coro/coro.c) 的程式碼中首先定義了兩個結構體，分別為 `struct task` 與 `struct arg` 。
`struct task` 是用來表示一個 coroutine 的執行狀態和相關資料的結構體，結構體中包含以下的成員：
* `jmp_buf env` : 用於儲存 coroutine 執行環境的 buffer ，提供 `setjmp` 和 `longjmp` 使用。
* `struct list_head list` : 一個鏈結串列用於存放需要被執行的任務。
* `char task_name[10]`：字元陣列用於儲存 coroutine 中的任務名稱。
* `int n int i`：用於儲存任務相關參數值。
`struct arg` 用於儲存傳遞參數的結構體。
:question: 疑問：為何須要額外新增一個結構體 `arg` 來儲存傳遞參數，為何不直接使用 `task` 結構體來儲存所有的參數資訊？
在 `struct task` 的結構體中調用 `setjmp` 與 `longjmp` 。 參考 [C99](https://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 規格書中對於 `setjmp.h` 標頭檔的定義與說明：
>TThe header <setjmp.h> defines the macro setjmp, and declares one function and one type, for bypassing the normal function call and return discipline.
在 `setjmp.h` 標頭檔中定義了 `setjmp` 這巨集，並宣告了一個函式以及一個變數型態。其中 `jmp_buf` 是一種適合儲存所需資訊的陣列型態，以還原任務環境 (calling environment)。
`longjmp` 函式，它會根據儲存在 `jmp_buf` 中的資訊，將程式的執行回到先前呼叫 `setjmp` 的地方，並從該處繼續執行下去。
>It is unspecified whether setjmp is a macro or an identifier declared with external linkage. If a macro definition is suppressed in order to access an actual function, or a program defines an external identifier with the name setjmp, the behavior is undefined.
值得注意的是在規格書關於 `setjmp.h` 標頭檔敘述的最後一段題到了，如果程式 suppress `setjmp` 的巨集定義，試圖訪問實際的函式，或者自行定義了 `setjmp` ，這樣的行為是 `undefined behavior` 。這個規定的目的是為了確保正確使用預處理器提供的 `setjmp` 巨集，避免自行定義 `setjmp` 或將其當作一般函式來呼叫，從而保證了 `setjmp` 巨集的行為是可移植和正確的。
---------
`static void task_add(struct task *task)`: 這個函式的作用是將傳入的任務結構體加入到一個全域的任務鏈結串列`tasklist`中。使用了 `list_add_tail` 的函數將 `task->list` 節點加入到 `tasklist` 的尾端。
```c
static void task_add(struct task *task)
{
list_add_tail(&task->list, &tasklist);
}
```
`static void task_switch()`: 從 `tasklist` 中取出第一個任務，並切換到該任務的執行環境中。調用 `list_first_entry` 取得第一個 `task` 結構體，將其從串列中移除。然後將 `cur_task` 設置為該任務，並使用 `longjmp` 將執行流程轉移到該任務之前中斷的位置。
```c
static void task_switch()
{
if (!list_empty(&tasklist)) {
struct task *t = list_first_entry(&tasklist, struct task, list);
list_del(&t->list);
cur_task = t;
longjmp(t->env, 1);
}
}
```
`void schedule(void)`：協同式多工的主要入口。首先呼叫 `setjmp(sched)` 來保存目前的執行環境。之後進入一個迴圈，每次從 `args` 陣列中取出一個 `arg` 結構體，並呼叫對應的 `tasks` 函式，傳入該 `arg` 結構體的位址作為參數。
```c
void schedule(void)
{
static int i;
setjmp(sched);
while (ntasks-- > 0) {
struct arg arg = args[i];
tasks[i++](&arg);
printf("Never reached\n");
}
task_switch();
}
```
接下來 `coro.c` 中定義了兩個 `task` 分別為 `task0` `task1` 。
```c
void task0(void *arg)
{
struct task *task = malloc(sizeof(struct task));
strcpy(task->task_name, ((struct arg *) arg)->task_name);
task->n = ((struct arg *) arg)->n;
task->i = ((struct arg *) arg)->i;
INIT_LIST_HEAD(&task->list);
printf("%s: n = %d\n", task->task_name, task->n);
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
task = cur_task;
for (; task->i < task->n; task->i += 2) {
if (setjmp(task->env) == 0) {
long long res = fib_sequence(task->i);
printf("%s fib(%d) = %lld\n", task->task_name, task->i, res);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
printf("%s: complete\n", task->task_name);
longjmp(sched, 1);
}
```
在看到 `if (setjmp(task->env) == 0)` 這樣的條件判斷感到很困惑，因此我找到了 [setjmp(3) — Linux manual page](https://man7.org/linux/man-pages/man3/longjmp.3.html) 閱讀相關的說明。
>The setjmp() function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by longjmp(). In this case, setjmp() returns 0.
由以上說明了解到 `setjmp()` 執行後會儲存跳躍目標位置到 `jmp_buf` 中，同時儲存程式跳躍時所需之資訊，而在直接呼叫 `setjmp()` 時其傳回值為 0 。而這樣做的目的是**輪流將 `task` 放入 `tasklist` 當中。**
```c
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
```
```c
setjmp(sched);
while (ntasks-- > 0) {
struct arg arg = args[i];
tasks[i++](&arg);
printf("Never reached\n");
}
```
具體來說，當第一次執行 `task` 函式時，會使用 `setjmp` 函式來記錄目前的執行位置，然後將這個 `task` 加入 `tasklist` 中。接著，使用 `longjmp` 函式回到 `schedule` 函式中。由於 `schedule` 函式包含一個 `while` 迴圈，用於遍走訪所有的 `task function` ，因此 `schedule` 函式將持續走訪並執行 `task`，直到所有的任務都被添加到串列中。
接著繼續探討 `task0` 中剩餘的程式碼。在將所有的 `task` 放入 `tasklist` 後，`schedule` 函式會呼叫 `task_switch` 函式，該函式尋找鏈結串列中的第一個任務，並使用 `longjmp` 回到該任務最初使用 `setjmp` 儲存的程式碼位置。值得注意的是，當任務回到 `setjmp` 儲存的程式碼位置時，回傳值為 1。因此，程式並不會再次執行將 `task` 放入 `tasklist` 的步驟，而是跳過此步驟繼續往下執行。
```c
task = cur_task;
for (; task->i < task->n; task->i += 2) {
if (setjmp(task->env) == 0) {
long long res = fib_sequence(task->i);
printf("%s fib(%d) = %lld\n", task->task_name, task->i, res);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
```
接下來觀察到程式進入迴圈並執行本任務核心的程式碼。在迴圈開始時，同樣透過 `if (setjmp(task->env) == 0)` 紀錄目前的執行位置，然後執行任務核心的程式碼。接著使用 `task_add(task);` 再次將任務加入串列中，並使用 `task_switch();` 執行目前鏈結串列的第一個任務。由於每個 task 都按順序放入鏈結串列中，因此也是輪流依序執行。特別的是，當本任務下一次回到 `setjmp` 的位置時，由於回傳值不是 1，所以會執行 `task = cur_task;` 恢復執行環境，然後透過迴圈繼續執行任務核心的程式碼。
### 引入 coroutine
經過研究並理解了 [coroutine 實作體驗-協同式多工](https://hackmd.io/@sysprog/concurrent-sched#coroutine-%E5%AF%A6%E4%BD%9C%E9%AB%94%E9%A9%97) 中的實作方式後，我發現協同式多工的輪流執行任務的方法非常適合用於井字遊戲中的「電腦 vs. 電腦」對弈模式。因此，我嘗試將 `coro.c` 中的實作方式修改為適用於井字遊戲 AI 對弈的方式。
若要引入 AI 對弈，首先應該先修改任務結構體與參數結構。
```diff
struct task {
jmp_buf env;
struct list_head list;
char task_name[10];
- int n;
- int i;
+ char table[N_GRIDS];
+ char turn;
};
struct arg {
char table[N_GRIDS];
char turn;
char *task_name;
- int n;
- int i;
+ char table[N_GRIDS];
+ char turn;
};
```
加入棋盤與目前棋手符號作為參數。
然而以上的宣告方式存在問題，若我將棋盤以 `char table[N_GRIDS];` 形式宣告，每個任務皆有自行的棋盤，下一個任務無法讀取更新後的棋盤，也就無法達成對弈的效果。因此我需要將棋盤以指標的形式作為參數，每一個任務都針對同一個棋盤進行修改。
```diff
struct task {
jmp_buf env;
struct list_head list;
char task_name[10];
- char table[N_GRIDS];
+ char *table;
char turn;
};
struct arg {
char table[N_GRIDS];
char turn;
char *task_name;
- char table[N_GRIDS];
+ char *table;
char turn;
};
```
將不同策略的 AI 棋手分別設為 `task0` 與 `task1` 實現交互對弈效果。
```c
void task0(void *arg)
{
struct task *task = malloc(sizeof(struct task));
// strncpy(task->task_name, ((struct arg *) arg)->task_name, 5);
task->turn = ((struct arg *) arg)->turn;
task->table = ((struct arg *) arg)->table;
INIT_LIST_HEAD(&task->list);
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
task = cur_task;
for (;;) {
if (setjmp(task->env) == 0) {
char win = check_win(task->table);
if (win == 'D') {
draw_board(task->table);
printf("It is a draw!\n");
break;
} else if (win != ' ') {
draw_board(task->table);
printf("%c won!\n", win);
break;
}
int move = mcts(task->table, task->turn);
if (move != -1) {
task->table[move] = task->turn;
record_move(move);
}
draw_board(task->table);
task_add(task);
task_switch();
}
task = cur_task;
}
printf("%s: complete\n", task->task_name);
longjmp(sched, 1);
}
```
> commit [e9164f0](https://github.com/sysprog21/lab0-c/commit/e9164f046bc62e7817f8e8386b6ce8102bb45174)
:::info
TODO: 使用 (preemptive) coroutine 實作鍵盤事件處理。
:::
Sign in with Wallet
Connect another wallet