# 2024q1 Homework1 (lab0)
contributed by < `chloe0919` >
### Reviewed by `david965154`
1.
自 `q_insert_head` 函式後就開始貼上完整程式碼，可以嘗試用實作想法或只貼上實作的關鍵程式碼。
2.
> 在 `strcpy` `strncpy` 之間選擇 `strncpy` 是因為 `strcpy` 會有緩衝區溢位的問題，而 `strncpy` 可以解決這問題，但是 `strncpy` 不會自動補上'\0'，所以需要自己手動增加。
事實上， `strncpy` 沒辦法避免溢位，以下實驗
```c
#include <stdio.h>
#include <string.h>
#define MAX 9
int main() {
char source[MAX] = "123456789";
char source1[MAX] = "123456789";
char destination[MAX] = "abcdefg";
char destination1[MAX] = "abcdefg";
int i = 5;
/* This is how strcpy works */
printf("destination is originally = '%s'\n", destination);
strcpy(destination, source);
printf("after strcpy, dest becomes '%s'\n\n", destination);
/* This is how strncpy works */
printf( "destination1 is originally = '%s'\n", destination1);
strncpy(destination1, source1, 9);
printf( "After strncpy, destination1 becomes '%s'\n", destination1 );
return 0;
}
```
而輸出為
```
destination is originally = 'abcdefg'
after strcpy, dest becomes '123456789123456789abcdefg'
destination1 is originally = '123456789abcdefg'
After strncpy, destination1 becomes '123456789abcdefg'
*** stack smashing detected ***: terminated
```
我既使用了 `strncpy` ，也提供了要複製過去的大小，但多輸出了 `9abcdefg` ，若將問題歸咎至未將 `destination1` 最後補上 '\0' ，那麼 `strcpy` 也能達到避免緩衝區溢位的問題。
只要字串的複製來源一超出指定大小，便要做出避免溢位的處理，那麼 `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.
C 語言規格書也完全沒有提到他用來避免緩衝區溢位的問題。
參考 [Why should you use strncpy instead of strcpy?](https://stackoverflow.com/questions/1258550/why-should-you-use-strncpy-instead-of-strcpy)
雖然為 stack overflow，但也可以看到 C 中字串處理方法和問題。
> [name=Chloexyw] 感謝提醒，我會修正以下的說明。
> 後來我去檢查以上提供的程式碼，發現最主要的問題是在宣告 char 時配置的空間就不足了，若能使用以下命令對程式進行檢查
```
$gcc -fsanitize=address -g filename.c
```
> 之後會輸出以下的檢查過程，就能先在宣告變數 source 的時候就發現記憶體位址溢位的問題
```shell
This frame has 4 object(s):
[32, 41) 'source' (line 5) <== Memory access at offset 41 overflows this variable
[64, 73) 'source1' (line 6)
[96, 105) 'destination' (line 7)
[128, 137) 'destination1' (line 8)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
(longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow ../../../../src/libsanitizer/asan/asan_interceptors.cpp:439 in __interceptor_strcpy
Shadow bytes around the buggy address:
0x10001ee195a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee195b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee195c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee195d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee195e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10001ee195f0: 00 00 00 00 f1 f1 f1 f1 00[01]f2 f2 00 01 f2 f2
0x10001ee19600: 00 01 f2 f2 00 01 f3 f3 00 00 00 00 00 00 00 00
0x10001ee19610: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee19620: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee19630: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10001ee19640: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
```
是的，我在一開始就沒對 `source` 提供足夠大的空間 ( 因為需要添加 '\0' 於最後， MAX 應為 10 )，因為編譯器不會對此進行警告，而我想讓 `strncpy` 發生記憶體位址溢位的問題，因此我刻意選擇不對 `source` 提供足夠大的空間，只要 `q_remove_head` 一提供錯誤的 `bufsize` 且實作時沒有檢查就會出現錯誤。
> 你的洞見呢？
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 43 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 3600 6-Core Processor
CPU family: 23
Model: 113
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
BogoMIPS: 7200.10
```
## 佇列實作與改進
### `q_new`
首先宣告一個 `list_head` 的指標 head ，並且使用 list.h 中的`INIT_LIST_HEAD` 建立並初始化一個 list head 分配給 head 記憶體位置。
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### q_free
:::danger
詳閱[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，理解詞彙背後的考量因素和使用精準詞彙。
> [name=Chloexyw] 好的，謝謝老師
:::
利用 `list_for_each_entry_safe` 的兩個指標 `node` 和 `n` 去逐一走訪 head 的所有節點，並且將它刪除掉，這裡不使用 `list_for_each_entry` 的是因為若使用 `q_release_element` 後會破壞掉原本的鏈結關係，導致無法找到當前節點連接的下一個節點
#### q_free 的程式碼：
```c
void q_free(struct list_head *l)
{
// Release all elements first, and then release the head.
if (!l)
return;
element_t *n;
element_t *node = list_first_entry(l, element_t, list);
list_for_each_entry_safe (node, n, l, list)
q_release_element(node);
free(l);
}
```
:::danger
使用作業指定的程式碼縮排風格。
> [name=Chloexyw] 好的，已更改
:::
### q_insert_head
剛開始實作時是使用 `memcpy` ，而且計算 s 的字元數量時使用的是 `sizeof(s)` ，因為 `sizeof` 計算的是變量或類型所占用的字元數量，所以在 make test 的截斷字串的測試中就會產生錯誤，應該使用 `strlen` 來計算出字串的個數才對。
:::danger
string 是「字串」，character 是「字元」
memory 是「(主) 記憶體」
byte 是「位元組」
考慮到科技文化延續議題，我們尊重台灣資訊科技前輩的篳路藍縷、理解詞彙背後的考量因素，和使用精準詞彙，其實後者也是工程素養的一環。
> [name=Chloexyw] 好的，已更改
:::
另外在配置記憶體的部份也要設置條件來判斷是否有配置成功，如果失敗需要釋放出配置的記憶體。
:::warning
改進你的漢語描述。
台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的語言模型差。
$\to$ [2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)
:::
#### q_insert_head 的程式碼：
```c
bool q_insert_head(struct list_head *head, char *s){
if(!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if(!new)
return false;
INIT_LIST_HEAD(&new->list);
char *value = malloc(sizeof(char)*(strlen(s) + 1));
if(!value){
free(new);
return false;
}
//memcpy(value,s ,strlen(s) + 1);
strncpy(value, s, strlen(s));
value[strlen(s)] = 0;
new->value = value;
list_add(&new->list, head);
return true;
}
```
剛開始是使用 `memcpy` 去複製字串到 value ，但是發現這樣會比較慢，所以後來改成使用 `strncpy` ，另外還需要在後面補上'\0'。
### q_insert_tail
實作方法和 `q_insert_head` 類似，只有將 `list_add` 改成 `list_add_tail` 。
### q_remove_head
想法是利用 `list_first_entry` 先找到head的記憶體位置，再來根據 `list.h` 的說明，如果 sp 為非空而且有一個 element 被移除掉，需要複製被移除的字串到 sp ，最後將 `tmp` 指向的 node 利用 `list_del_init` 移除並且初始化。
#### q_remove_head 的程式碼
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *tmp = list_first_entry(head, element_t,list); // list_first_entry : find the address of first element
if (sp){
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = 0;
}
list_del_init(&tmp->list);
return tmp;
}
```
根據 [C 語言規則書](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
> 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.
>
`strncpy` 可以將不超過 n 個字元從 s2 複製到 s1 ，不過並不會自動複製 `\0` 所以需要自己手動增加。
:::danger
查詢第一手材料，例如 C 語言規格書和 Linux man-pages
:::
另外在 `list_del` 和 `list_del_init` 的選擇上，根據下面提供的圖表，需要選擇 `list_del_init` 才能將需要 remove 的節點原始的鏈結狀態初始化，因為 `list_del` 並不會破壞掉即將被移除的節點本身的鏈結關係。
list_del :
```graphviz
digraph {
node[shape=circle]
{
// rankdir = LR
A[label=A]
B[label=B,color=red]
C[label=C]
B->A[color=blue]
B->C[color=blue]
A->C[dir=both]
// A->B->C[color=white]
}
rankdir = "LR"
}
```
list_del_init :
```graphviz
digraph graphname{
node[shape=circle]
{
// rankdir = LR
A[label=A]
B[label=B,color=red]
C[label=C]
B->B[color=blue]
A->C[dir=both]
A->B->C[color=white]
}
rankdir = "LR"
}
```
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記內文。
> [name=Chloexyw] 好的，已更改
:::
### q_remove_tail
實作方法和 `q_remove_head` 類似，只有將 `list_first_entry` 改成 `list_last_entry` 找出最後節點的位置即可。
### q_size
參考〈[2024 年 Linux 核心設計/實作課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)〉，利用 `list_for_each` 逐一走訪所有節點並且每次都將 `len+=1` 。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
> [name=Chloexyw] 好的，已更改
:::
### q_delete_mid
首先，透過 `left` 和 `right` 分別從左右兩邊開始尋找中點，再來利用 `list_entry` 找出目前指到的中點的 entry 並且使用 `q_release_element` 釋放掉此 element 。
#### q_delete_mid的程式碼：
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *left = head->next;
struct list_head *right = head->prev;
while ((left != right) && (left->next != right)) {
left = left->next;
right = right->prev;
}
list_del(right);
element_t *del = list_entry(right, element_t, list);
q_release_element(del);
return true;
}
```
### q_delete_dup
:::danger
注意標點符號的使用，這裡該用 `〈` 和 `〉`
> [name=Chloexyw] 好的，已更改
:::
參考〈[Linux 核心專題: 改進 lab0](https://hackmd.io/@sysprog/HJmB5x5Hn)〉，利用 `list_for_each_entry_safe` 的兩個指標 `curr` 和 `nex` ，判斷 `curr` 是否等於 `nex` ，如果相等就將目前 `curr` 指到的節點使用 `list_del` 改變鏈結關係，再用 `q_release_element` 將此節點的 element 釋放掉，另外，使用布林值 flag 用來判斷上一次是否有刪除過，如果有且這次沒有出現重複的節點，則需要再移除一次目前節點，因為要達到的目標是需要移除到==全部==有連續重複的節點。ihe
#### q_delete_dup 的程式碼
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
bool flag = false;
element_t *curr, *nex;
list_for_each_entry_safe(curr, nex, head, list) {
if (&nex->list != head && strcmp(curr->value, nex->value) == 0) {
flag = true;
list_del(&curr->list);
q_release_element(curr);
} else if (flag) {
flag = false;
list_del(&curr->list);
q_release_element(curr);
}
}
return true;
}
```
### q_swap
宣告一個整數 count 來紀錄目前到達佇列的第幾個索引的節點，因為需要完成==每兩個節點==就進行交換的動作，所以當 `count%2 == 1` 的時候就要交換。
另外用 `list_for_each_safe` 來紀錄目前目前節點跟下一個節點，這裡不使用 `list_for_each` 的原因是：
在 `list.h` 中有說明 `list_for_each_safe` 的流程是每次迭代都會將 `curr = n，n = curr->next` ，而當我們在使用 `list_move` 時會改變掉 `curr` 指向的節點的相對位置，此時就要利用 `n` 指標來將 `curr` 指回正確的位置，程式才不會產生錯誤。
#### q_swap 的程式碼
```c
void q_swap(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
struct list_head *curr, *n;
struct list_head *tmp = head;
int count = 0;
list_for_each_safe(curr, n, head) {
if (count % 2 == 1) {
list_move(curr, tmp);
tmp = curr->next;
}
count++;
}
}
```
### q_reverse
剛實作時使用 `list_for_each` ，導致一直無法正確 reverse ，經過幾次 trace 後發現因為 `list_move` 會將改變鏈結關係，將 `curr` 指到的位置移到 head 之後，所以需要使用 `list_for_each_safe` ，在每次迭代後都將 `curr` 只指回到原始位置的下一個節點，才能成功 reverse 。
#### q_reverse的程式碼：
```c
void q_reverse(struct list_head *head)
{
if(!head || list_is_singular(head))
return;
struct list_head *curr,*n;
list_for_each_safe(curr, n, head){
list_move(curr, head);
}
}
```
用以下圖表說明 reverse 實作想法：
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
tmp[label=tmp,shape=plaintext,fontcolor=red]
curr[label=curr,shape=plaintext,fontcolor=blue]
n[label=n,shape=plaintext,fontcolor=blue]
H[label=H]
A[label=A]
B[label=B]
C[label=C]
H->A->B->C[dir=both]
C->H[dir=both]
{rank=same tmp->H;}
{rank=same curr->A;}
{rank=same n->B;}
}
rankdir = "LR"
}
```
經過第一次的迭代後，會形成：
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
tmp[label=tmp,shape=plaintext,fontcolor=red]
curr[label=curr,shape=plaintext,fontcolor=blue]
n[label=n,shape=plaintext,fontcolor=blue]
H[label=H]
A[label=A]
B[label=B]
C[label=C]
H->A->B->C->H[dir=both]
{rank=same tmp->H;}
{rank=same curr->B;}
{rank=same n->C;}
}
rankdir = "LR"
}
```
再來使用 `list_move` 會將 B 插入到 `tmp` 所指到的 head 後面
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
tmp[label=tmp,shape=plaintext,fontcolor=red]
curr[label=curr,shape=plaintext,fontcolor=blue]
n[label=n,shape=plaintext,fontcolor=blue]
H[label=H]
A[label=A]
B[label=B]
C[label=C]
H->B->A->C->H[dir=both]
{rank=same tmp->H;}
{rank=same curr->B;}
{rank=same n->C;}
}
rankdir = "LR"
}
```
再經過一次迭代 `curr = n，n = curr->next` 後：
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
tmp[label=tmp,shape=plaintext,fontcolor=red]
curr[label=curr,shape=plaintext,fontcolor=blue]
n[label=n,shape=plaintext,fontcolor=blue]
H[label=H]
A[label=A]
B[label=B]
C[label=C]
H->B->A->C->H[dir=both]
{rank=same tmp->H;}
{rank=same curr->C;}
n->H
}
rankdir = "LR"
}
```
這時候將 C 插入 head 之後
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
tmp[label=tmp,shape=plaintext,fontcolor=red]
curr[label=curr,shape=plaintext,fontcolor=blue]
n[label=n,shape=plaintext,fontcolor=blue]
H[label=H]
A[label=A]
B[label=B]
C[label=C]
H->C->B->A->H[dir=both]
{rank=same tmp->H;}
{rank=same curr->C;}
n->H
}
rankdir = "LR"
}
```
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記內文。
> [name=Chloexyw] 好的，已更改
:::
最後，經過最後一次迭代 `curr = n，n = curr->next` 後，形成 reverse 結果
### q_reverseK
採用和 `q_reverse` 和 `q_swap` 的作法，一樣是有使用 整數 countK 去紀錄位置，另外還有定義整數 n 為 `n = q_size(head) / k` 來當作臨界點，當滿足 k 個一組的時候才可以 reverse ，而 `tmp` 用來紀錄往後 `list_move` 時要插入的位置，所以只有在 `countK % k == 0` 時才會改變其位置。
```c
list_for_each_safe (curr, safe, head) {
if (countK % k == 0) {
tmp = curr->prev;
}
if ((countK / k) < n)
list_move(curr, tmp);
countK++;
}
```
### q_sort
:::danger
注意標點符號的使用，這裡該用 `〈` 和 `〉`
> [name=Chloexyw] 好的，已更改
:::
參考〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)〉以及〈[Linux 核心專題: 改進 lab0](https://hackmd.io/@sysprog/HJmB5x5Hn)〉，採用 Divide and Conquer 的想法先將佇列拆成子佇列，再透過 `mergeTwoLists` 將佇列排序並合併。
###### mergeTwoLists 的==原始==程式碼：
```c
void mergeTwoLists(struct list_head *L1, struct list_head *L2){
if (!L1 || !L2)
return;
struct list_head *Lnode = L1->next, *Rnode = L2->next;
while(Lnode != L1 && Rnode != L2){
if(strcmp(list_entry(Lnode, element_t, list)->value,list_entry(Rnode, element_t, list)->value) < 0){
Lnode = Lnode->next;
} else{
list_move(Rnode, Lnode->prev);
Rnode = Rnode->next;
}
}
if (q_size(L2) != 0) {
list_splice_tail(L2, L1);
}
}
```
其中，如果先執行 `list_move(Rnode, Lnode->prev)` 則會將 Rnode 插入到 L1 中，這樣下一次執行 `Rnode = Rnode->next` 時， Rnode 會變成指向 Lnode 的資料，這時會發生錯誤。
因此，將原始程式碼的這兩行指令改成以下才會成功
```c
Rnode = Rnode->next;
list_move(Rnode->prev, Lnode->prev);
```
在 `q_sort` 實現 Divide and Conquer 的想法，先利用 `fast` 和 `slow` 找出佇列的中點，接著宣告一個 list right 並初始化，再利用 `list_cut_position` 將中點左邊和右邊切開並且遞迴將左右切的更小，最後使用 `mergeTwoLists` 將兩個 list 排序並合併。
#### q_sort的程式碼：
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head->next;
for (struct list_head *fast = head->next;
fast != head && (fast->next) != head; fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow;
LIST_HEAD(right);
list_cut_position(&right, head, mid->prev);
q_sort(head, 1);
q_sort(&right, 1);
mergeTwoLists(head, &right);
}
```
### q_ascend
參考〈[Linux 核心專題: 改進 lab0](https://hackmd.io/@sysprog/HJmB5x5Hn)〉的想法，先從佇列的最右邊開始逐步去看在 `curr` 右邊的 `nex` 指向的值是否有小於 `curr` ，如果小於則需要使用 `list_del` 和 `q_release_element` 將指向 `curr` 的節點刪除掉，每次都只需要看在 `curr` 右邊的值就好了，因為更右邊的值已經確定了是不需要被刪掉的節點了，代表他們一定是呈現升序。
另外在參考資料中是從 `head->prev` 開始看，但是實際上最右邊的點一定不會被移除掉，因為它的右邊並沒有值，所以可以從 `head->prev->prev` 開始執行。
#### q_ascend的程式碼：
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return 1;
struct list_head *curr = head->prev->prev;
while (curr != head) {
struct list_head *nex = curr->next;
element_t *f = list_entry(curr, element_t, list);
element_t *s = list_entry(nex, element_t, list);
if (strcmp(f->value, s->value) > 0) {
struct list_head *del = curr;
list_del(del);
curr = curr->prev;
q_release_element(list_entry(del, element_t, list));
} else
curr = curr->prev;
}
return q_size(head);
}
```
### q_descend
實作概念和 `q_ascend` 類似，只有比較時需要改成 `strcmp(f->value, s->value) > 0`
### q_merge
先透過 `list_entry` 算出 `queue_contex_t *queue_head` 的記憶體位置，也就是第一個節點的位置，然後逐一走訪佇列並透過 `mergeTwoLists()` 將第二個以後的佇列合併進第一個佇列中，然後再使用 `INIT_LIST_HEAD` 將已經合併過的佇列初始化，而且長度被設為0 。
:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
3. 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
> [name=Chloexyw] 好的，我會再改進
:::
##### q_merge的程式碼：
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head)
return 0;
queue_contex_t *queue_head = list_entry(head->next, queue_contex_t, chain);
for (struct list_head *curr = head->next->next; curr != head;
curr = curr->next) {
queue_contex_t *queue = list_entry(curr, queue_contex_t, chain);
mergeTwoLists(queue_head->q, queue->q);
INIT_LIST_HEAD(queue->q);
queue->size = 0;
}
return queue_head->size;
}
```
## 研讀 Linux 核心原始程式碼的 list_sort
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
根據 [__attribute__((nonnull)) function attribute](https://developer.arm.com/documentation/dui0375/g/Compiler-specific-Features/--attribute----nonnull---function-attribute) 定義：
> This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.
表示 `__attribute__` 屬於 function attribute，當第二、第三位置的 pointer 是 NULL 時發出警告。
首先利用`head->prev->next = NULL;`將 head 的最後節點指向 NULL
```
/* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k， they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
```
在 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的註解中提到這裡 merge sort 的實作重點。方法為以下的特點 ：
* 兩個要被合併的 list 至少是$2^{k+1}$：$2^k$ = 2 : 1的平衡狀態
* `list_sort` 和 `fully-eager bottom-up mergesort` 不同的是，前者是出現兩個 $2^k$ 的 list 時不會立刻合併，而後者是只要出現兩個 $2^k$ 就會合併
實作的方法是利用整數 count 紀錄==有多少數量的 element 在 pending list 中==，而且根據 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 之中 list_sort 的介紹還有上述的規則，我們可以歸納出以下的規律：
如果要產生 $2^{k+1}$ 的鏈結佇列的話，需要兩個長度為 $2^k$ 的 list，還要確定後面的元素個數達到 $2^k$ ，這時可以確保差距不會超過 $2^{k+1}$：$2^k$ = 2 : 1
*$\Longrightarrow$ : 表示合併*
* $2^0$
* $2^0$ + $2^0$ ( no merge )
* $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^0$
* $2^1$ + $2^0$ + $2^0$ ( no merge )
* $2^1$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^1$ + $2^0$
* $2^1$ + $2^1$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^0$ + $2^0$
* $2^2$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^1$ + $2^0$
整理出以上合併原則試著帶入 `count` 進行歸納：
* $2^0$ $\rightarrow$
* count = 1 = $1_2$ $\rightarrow$ $2^0$ + $2^0$ ( no merge )
* count = 2 = $10_2$ $\rightarrow$ $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^0$ ( 需要 merge 出 $2^1$)
* count = 3 = $11_2$ $\rightarrow$ $2^1$ + $2^0$ + $2^0$ ( no merge )
* count = 4 = $100_2$ $\rightarrow$ $2^1$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^1$ + $2^0$ ( 需要 merge 出 $2^1$)
* count = 5 = $101_2$ $\rightarrow$ $2^1$ + $2^1$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^0$ + $2^0$ ( 需要 merge 出 $2^2$)
* count = 6 = $110_2$ $\rightarrow$ $2^2$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^1$ + $2^0$ ( 需要 merge 出 $2^1$)
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
可以觀察到需要 merge 出的大小可利用 `count` 的二進位數字的最小位元的位置計算出，透過以上程式碼中的 for 迴圈可以計算出 `count` 的最低位元，並且找到此輪要 merge 的兩個 list，並且利用 `*tail` 往 `prev` 走 k 步找到 $2^k$ 大小的 list a
```c
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
```
而 `*b = a->prev` 可以找到另一個大小也為 $2^k$ 的 list b ，並且將兩者合併。
另外，也可以發現到只有在 `count` 為 $2^k-1$ 的時候，不會有 merge 的動作。
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
接著輸入下一個元素 ：
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
沒有待輸入的元素的時候，將剩下的字串使用 `merge` 由大到小合併 ：
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
最後執行 `merge_final` 合併兩條子串列 ：
```c
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。及早更正上方的議題。
:::
### 將 list_sort 引入到 lab0-c 專案
> ###### 參考至 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-lab0#%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)
1. 將 [list_sor.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 加入至與 `queue.c` 相同層級的目錄中
1. 修改 `Makefile` 中 OBJS，新增一個 `list_sort.o`
```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
+ linenoise.o web.o list_sort.o
```
3. 修改 `qtest.c`
* 加入 `#include "list_sort.h"`
* 設定變數決定是否使用 `list_sort`
```c
static int use_list_sort = 0;
```
* 加入一個用來執行比較的函式
```c
static int cmp(void* priv,
const struct list_head *l1,
const struct list_head *l2)
{
return strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value);
}
```
* 修改 `do_sort`中執行 sort 的部份，決定是否使用 `list_sort`
```diff
if (current && exception_setup(true))
- q_sort(current->q, descend);
+ use_list_sort ? list_sort(NULL, current->q, cmp)
+ : q_sort(current->q, descend);
exception_cancel();
```
* 最後使用 `add_param` 將 `listsort` 指令加入到 `help` 選單中
```c
add_param("listsort", &use_list_sort,
"Use the sort which is made by linux kernel developers", NULL);
```
#### 安裝 perf
根據老師的安裝教學 [perf 原理和實務](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 即可順利安裝成功，特別要注意的是如果不是切換到 root 的情況下輸入
```
$ perf top
```
會出現以下錯誤畫面 ：
可以透過
```
$ cat /proc/sys/kernel/perf_event_paranoid
```
來獲取權限值 。如果要將權限全開，用以下指令完成
```
$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"
```
#### 用 perf 進行效能比較
開始比較 `q_sort` 與 `list_sort` 這兩個排序的效能差別，分別測試資料比數從 10 萬筆資料到 100 萬筆資料
| 資料數 | q_sort | list_sort |
| --------- | ------ | --------- |
| 100,000 | 0.034 | 0.031 |
| 200,000 | 0.111 | 0.108 |
| 300,000 | 0.187 | 0.179 |
| 400,000 | 0.268 | 0.267 |
| 500,000 | 0.366 | 0.354 |
| 600,000 | 0.434 | 0.428 |
| 700,000 | 0.526 | 0.522 |
| 800,000 | 0.643 | 0.609 |
| 900,000 | 0.706 | 0.694 |
| 1,000,000 | 0.810 | 0.783 |
| 項目 | q_sort | list_sort |
| ---- | ------ | --------- |
|cache-misses |3,5196 |3,4884 |
|cache-references |13,6690 |13,6938 |
|% of all caches refs|25.75% |25.47% |
|instructions |160,8820 |160,8588 |
|cycles |197,2961 |202,2427 |
|insn per cycle |0.82 | 0.80 |
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### Timing Leakage Detection
執行 leakage detection test 測試兩筆不同資料的執行時間來檢查兩者的時間分佈是否具有顯著性的差異。
* Step 1 : Measure execution time
針對屬於兩個不同資料類別的輸入，重複測量在加密函數 (cryptographic function) 的執行時間
a) Classes definition
採用 fix-vs-random tests，給定兩個不同的輸入資料
* 固定資料 ：經常選擇某些固定值來觸發 corner-case 的情形
* 隨機資料
b) Cycle counters
現在 CPU 提供 Cycle counters，可以準確的取得執行時間測量值。
c) Environmental conditions
為了減少環境變化對結果的影響，每次測量都對應於一個隨機選擇的類別
另外，類別分配和輸入準備任務在測量階段之前完成
* Step 2 : Apply post-processing
可以對每個單獨的測量值進行一些後處理 (post-processing)
a) Cropping
典型的時序分佈在較長的執行時間中會呈現 positive skewness
這可能是由於測量誤差或主要的程序被 OS 或其他外部的無關活動中斷所引起的，在這種情況下可以裁剪掉測量值來避免誤差
b) Higher-order preprocessing
根據所應用的統計測試，應用一些高階預處理，例如 centered product、mimicking higher-order DPA attacks
* Step 3 : Apply statistical test
利用統計測試來反駁虛無假說『 兩個時間分佈相等 』
a) Cropping
一個簡單的實作為 [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) ，適用於且兩群體都為常態分布且變異數未知但不相同時。
當 t-test 與 Cropping preprocessing 結合時，不只是測試均值相等性，而且還測試更高階統計情境，因為 Cropping 是一種非線性轉換
b) Non-parametric tests
這些測試的優點是對於基本分佈的假設較少，缺點是他們可能收斂速度較慢並且需要更多樣本，例如 [Kolmogorov-Smirnov](https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test)
### 解釋 simulation 模式
首先在 `qtest.c` 可以看到 simulation 的三種模式
```c
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok =
pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();
if (!ok) {
report(1,
"ERROR: Probably not constant time or wrong implementation");
return false;
}
report(1, "Probably constant time");
return ok;
}
```
* 不需要 arguments
* Probably not constant time
* Probably constant time
### Student's t-distribution 及程式實作原理
$$
t = \cfrac{\bar{x_1} - \bar{x_2}}{\sqrt{\cfrac{s_1^2}{n_1} + \cfrac{s_2^2}{n_2}}}
$$
假設 t 值越大則代表兩組資料的分佈差異越大，在 `dudect/ttest.c` 中由以下程式碼進行計算
```c
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
```
`fixture.c` 中的 `report` 函式計算出 t 值
```c
double max_t = fabs(t_compute(t));
```
最後量測是否為 constant time
```c
/* Definitely not constant time */
if (max_t > t_threshold_bananas)
return false;
/* Probably not constant time. */
if (max_t > t_threshold_moderate)
return false;
/* For the moment, maybe constant time. */
return true;
```
### 修改程式以達成 constant time
> [commit](https://github.com/sysprog21/lab0-c/commit/c272652408a0e1849422766cda2bb2baf47e3f43)
> 參考 [chiangkd](https://hackmd.io/duPg38XOTL-XKa7_h0Ielw?view#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E4%B8%A6%E6%94%B9%E9%80%B2-dudect)
根據 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 在 `lab0-c` 也加入 percentile 的處理，但是在 `dudect.h` 中有定義 `dudect_ctx_t` 結構體將所有資訊定義在一起，包括執行時間、輸入資料、類別等，而 `lab0-c` 中沒有
```c
typedef struct {
int64_t *ticks;
int64_t *exec_times;
uint8_t *input_data;
uint8_t *classes;
dudect_config_t *config;
ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
int64_t *percentiles;
} dudect_ctx_t;
```
所以另外要在 `t_context_t` 中定義 `int64_t *percentiles`
```c
typedef struct {
double mean[2];
double m2[2];
double n[2];
int64_t *percentiles;
} t_context_t;
```
### 觀察論文和實際操作的程式碼
在 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉提到以下：
> Pre-processing: We pre-process measurements prior to
statistical processing. We discard measurements that are larger than the p percentile, for various values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise. This (heuristic) process gives good
empirical results (makes detection faster); nevertheless we also process measurements without pre-processing.
這邊的操作主要是為了把極端值去除，其中在 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 實際計算的公式為：
$$
f(i) = 1 - {0.5}^{10 \cdot \frac{i+1}{N}}
$$
接下來將這個公式使用 python 畫出來，其中 x 軸代表的是 $i$ 分別為 0-99 的值，而 y 軸則為對應 $i$ 值使用上述公式計算出來的 $f(i)$
可以看到這個公式收斂到 1 的速度很快，當 i 為 33 時
$$
f(33) = 1 - {0.5}^{10 \cdot \frac{33+1}{N}} \approx 0.905
$$
代表 i 為 33 以後所取的都是剩下的大於 0.9 的
:::danger
指出程式碼和論文描述的出入之處。
:::
---
## 在 `qtest` 提供新的命令 `shuffle`
> commit [69db7e5](https://github.com/sysprog21/lab0-c/commit/69db7e599be1993012abe57c351fb0a81b28aa44)
:::danger
使用你 fork 之後得到的 git repository 對應的超連結。
:::
[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
舉例 1~5 的 shuffle 過程
每次都從原始數據中選出一個隨機數放到尾端，直到所有的數字都被取出
| 隨機數取值 index 範圍 | 隨機數 | 原始數據 | 結果 |
| --------------------- | ------------- | -------- | ---- |
| | | 12345 | |
| 0~4 | 4 (index = 3) | 1235 | 4 |
| 0~3 | 2 (index = 1) | 135 | 24 |
| 0~2 | 1 (index = 0) | 35 | 124 |
| 0~1 | 5 (index = 1) | 3 | 5124 |
實作方法是利用 `rand_idx` 每次都在指定的範圍內取出隨機數在佇列中的索引，再來透過 `for` 迴圈去找出該索引所指到的節點，最後利用 `list_del` 改變鏈結關係後再用 `list_add_tail` 加入到原始數據的尾端
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *tmp = head;
for (int i = size; i > 1; i--) {
int rand_idx = rand() % i;
struct list_head *rand_num = head;
for (int j = 0; j <= rand_idx; j++)
rand_num = rand_num->next;
list_del(rand_num);
list_add_tail(rand_num, tmp);
tmp = tmp->prev;
}
return;
}
```
另外，也需要在 `qtest.c` 中定義 shuffle 的命令，其中在撰寫 `do_shuffle` 時參考 `do_swap` 的寫法，而且因為無法更改` list.h` 的內容，所以將 `void q_shuffle(struct list_head *head);` 定義在 `do_shuffle` 之前。
## 使用 Valgrind 排除記憶體錯誤
根據 [以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b) 執行命令 `make valgrind` ，檢查是否存在記憶體錯誤。
檢查出來的結果如下，看起來都是相同問題，所以只擷取部份內容
```
==6123== 72,800 bytes in 91 blocks are definitely lost in loss record 4 of 4
==6123== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6123== by 0x110BE0: doit (fixture.c:163)
==6123== by 0x110BE0: test_const (fixture.c:209)
==6123== by 0x110DA1: is_remove_tail_const (fixture.c:225)
==6123== by 0x10C55A: queue_remove (qtest.c:313)
==6123== by 0x10C9D1: do_rt (qtest.c:426)
==6123== by 0x10E13E: interpret_cmda (console.c:181)
==6123== by 0x10E6F3: interpret_cmd (console.c:201)
==6123== by 0x10EAF4: cmd_select (console.c:610)
==6123== by 0x10F3E0: run_console (console.c:705)
==6123== by 0x10D530: main (qtest.c:1301)
```
根據教材可看到 memory lost 分成幾種類型：
* definitely lost : 真的 memory leak
* indirectly lost : 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak
* possibly lost : allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
* still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數，即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。
後來去檢查 `doit` 才發現之前在定義 `t->percentiles` 時使用 `calloc` 動態分配記憶體時忘記釋放，因此修改下列程式。
```diff
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
+free(t->percentiles);
return ret;
```
再執行一次 `make valgrind` 後問題就解決了。
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
## 透過 Massif 分析記憶體使用量
在 valgrind 使用的參數列表中加入 `--tool=massif`
```
$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
```
之後可以在檔案中找到一張 `massif.out.XXXXX`，接著輸入
```
$ massif-visualizer massif.out.XXXXX
```
就可以獲得 Massif 所分析在執行 `traces/trace-17-complexity.cmd` 的記憶體使用量圖表了
接下來分析執行以下測試項目時的記憶體使用量
```
option simulation 1
it
option simulation 0
```
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
參考 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-lab0#%E4%BD%BF%E7%94%A8-Valgrind-%E6%8E%92%E9%99%A4-qtest-%E5%AF%A6%E4%BD%9C%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E9%8C%AF%E8%AA%A4)
相較於 valgrind ，Address Sanitizer 適用對於記憶體錯誤進行更快速的檢測，在 `Makefile` 可以看到以下規則：
```c
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
所以只需要輸入 `make SANITIZER=1` 就可以直接使用，不過要特別注意的是，Anitizer 與 Valgrind 是不可以同時使用的，所以在執行前要先 `make clean` 清除之前編譯的內容。
:::danger
改進授課教師要求更正的地方。
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
本筆記的標題不符合規範。
:::
## 分析 List_sort 和 Timsort
> 參考筆記：[vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E6%AF%94%E8%BC%83-timsort-%E8%88%87-list_sort)
> commit [41c3f48](https://github.com/chloe0919/linux_hw2/commit/41c3f48c758914c55422cb5d9b11f09063c392d2?diff=unified&w=0)
使用 [Timsort](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 提供的 `main.c` 檔，測試看看資料數 10-100000 筆時，`timesort` 和 `list_sort` 各自的 CPU Clock Elapsed 以及 Comparisons 的表現
1. 首先是在資料呈現**隨機分佈**的時候，使用 `rand()` 建立隨機資料
```
Creating sample
==== Testing timesort for SAMPLES = 10 ====
CPU Clock Elapsed : 0.000000 seconds
Comparisons: 26
List is sorted
==== Testing list_sort for SAMPLES = 10 ====
CPU Clock Elapsed : 0.000000 seconds
Comparisons: 21
List is sorted
Creating sample
==== Testing timesort for SAMPLES = 100 ====
CPU Clock Elapsed : 0.000003 seconds
Comparisons: 586
List is sorted
==== Testing list_sort for SAMPLES = 100 ====
CPU Clock Elapsed : 0.000002 seconds
Comparisons: 543
List is sorted
Creating sample
==== Testing timesort for SAMPLES = 1000 ====
CPU Clock Elapsed : 0.000048 seconds
Comparisons: 10072
List is sorted
==== Testing list_sort for SAMPLES = 1000 ====
CPU Clock Elapsed : 0.000046 seconds
Comparisons: 8693
List is sorted
Creating sample
==== Testing timesort for SAMPLES = 10000 ====
CPU Clock Elapsed : 0.000704 seconds
Comparisons: 135965
List is sorted
==== Testing list_sort for SAMPLES = 10000 ====
CPU Clock Elapsed : 0.000679 seconds
Comparisons: 121006
List is sorted
Creating sample
==== Testing timesort for SAMPLES = 100000 ====
CPU Clock Elapsed : 0.010123 seconds
Comparisons: 1681266
List is sorted
==== Testing list_sort for SAMPLES = 100000 ====
CPU Clock Elapsed : 0.009377 seconds
Comparisons: 1542859
List is sorted
Creating sample
==== Testing timesort for SAMPLES = 1000000 ====
CPU Clock Elapsed : 0.180587 seconds
Comparisons: 20362814
List is sorted
==== Testing list_sort for SAMPLES = 1000000 ====
CPU Clock Elapsed : 0.149971 seconds
Comparisons: 18687079
List is sorted
```
根據以上實驗結果可以發現 list_sort 和 timsort 皆不會在任一個特定的資料量大小表現特別優秀，因此以下實驗皆以資料量 10000 進行比較實驗
2. 再來比較看看**資料分佈皆為升序**的結果，這邊不比較降序的原因是，在 timsort 操作 `findrun()` 時，會將找到的 run 進行反轉
```
Creating sample
==== Testing timesort ====
CPU Clock Elapsed : 0.000028 seconds
Comparisons: 9999
List is sorted
==== Testing list_sort ====
CPU Clock Elapsed : 0.000169 seconds
Comparisons: 65344
List is sorted
```
3.最後比較資料分佈為 worse case 的情況，以 timsort 來看，worse case 則是在**資料升序降序反覆的時候** ，例如 [ 1，4，3，5，2，6 ] 因為此時 timsort 所計算出來的 run 數最多，而當 run 數變多時，就需要更多的比較和合併的時間
```
Creating sample
==== Testing timesort ====
CPU Clock Elapsed : 0.000654 seconds
Comparisons: 128818
List is sorted
==== Testing list_sort ====
CPU Clock Elapsed : 0.000636 seconds
Comparisons: 121133
List is sorted
```
:::danger
探討不同的資料分布對於排序演算法的影響。
:::
### 結論：
根據實驗結果我們可以發現在資料分佈為 `rand()` 和 `worse case` 的時候 list sort 的表現都是優於 timsort 的，而在資料為排序好的情況時，timsort 就會明顯比 list sort 還要來的好，這個實驗結果的原因我覺得是因為 list sort 在決定合併與否不會受到資料的實際大小的影響，而 timsort 則是會在 `findrun()` 時就會因為資料的實際分佈而影響到 run 的數量，例如在 worse case 就會因為 run 數很多而需要逐一比對數量再進行合併
---
## tic-tac-toe
[jserv/ttt](https://github.com/jserv/ttt) 專案提供可跟電腦對弈的互動環境，並且提供多種對弈時的演算法，因為不理解遊戲進行的流程，在理解演算法之前，先對程式碼進行初步的理解之後才能順利將遊戲整合至 `lab0-c` 中
:::danger
文字訊息不要用圖片展現
:::
* `check_win` ：判斷棋盤上贏家，若是平手則會回傳 D
* `draw_board` ：畫出棋盤
* `record_move` ：紀錄每一步選擇的位置到 `static int move_record[N_GRIDS]` 中
* `get_input` ：獲取使用者的移動位置
* `print_moves` ：印出所有使用者和 AI 移動的位置
使用以上函式完成操作，並且定義一個 `char table[N_GRIDS]` 紀錄目前棋盤上的遊戲畫面，並且每次都使用 `draw_board(table)` 顯示畫面
```c
if (turn == ai) {
int move = mcts(table, ai);
if (move != -1) {
table[move] = ai;
record_move(move);
}
}
```
如果此時為 ai 的輪次，會使用演算法(這邊使用 Monte Carlo Tree Search )去計算出 ai 下一個要移動的位置，接下來將 `move` 存到 `table` 和 `move_record` 中
反之如果是使用者輪次，則用 `get_input` 紀錄下一步位置並且一樣存到 `table` 和 `move_record` 中
```c
turn = turn == 'X' ? 'O' : 'X';
```
最後使用此判斷式更換輪次
> 支援 MCTS AI 的 tic-tac-toe 程式碼 ：[efc314f](https://github.com/sysprog21/lab0-c/commit/efc314ff84abe9122bf73115fced2d14fe80f17e)
### Monte Carlo Tree Search
> 參考 [Monte Carlo Tree Search 解說](https://www.youtube.com/watch?v=J3I3WaJei_E)
模擬進行幾次遊戲，將遊戲的結果紀錄在一個 tree 裡，再根據最後模擬的結果來選擇最好的動作
步驟：
1. Selection ：選擇要對 tree 上的那一個 node 進行更新，在 Select 時只會選擇 leaf node (沒有 chlidren 的 node)
1. Expand or Rollout
(目前節點為全新的就進行 Rollout，若已經更新過則進行 Expand )
* Expansion : 對某一個節點往下產生新的子節點
* Simulation ：以目前的狀態開始完成一次對局的模擬
3. Backpropagation ：將節點沿著原路一直往上傳直到達到 root 為止，並且更新此路線上節點的權重
在 Selection 的步驟中，會使用 UCB (Upper Confidence Bound) 給於節點權重，並且以 UCB 的值決定要選擇的節點
$$
\cfrac{w_i}{n_i} + c \sqrt{\cfrac{ln(N_i)}{n_i}}
$$
* $w_i$ 代表目前該節點贏的次數
* $n_i$ 代表目前該節點總共進行的模擬次數
* $N_i$ 代表該節點的父節點總共進行的模擬次數
* $c$ 可自行調整的常數，通常定為 $\sqrt{2}$
公式的前一項代表 exploitation ，可以使公式獲得目前已知最好策略的資訊，而公式的後一項代表的則是 exploration ，也就是探索其他策略，exploitation 和 exploration 需要達到良好的平衡，才能在選擇的時候不是只有選擇目前最好的策略而不去探索別的路線，或是只探索勝率很低的路線而導致效率太差
### 定點數
先觀察 Monte Carlo Tree Search 的實作中需要由浮點數轉換成定點數的地方有哪些
1. **`score` 的宣告**
原始宣告為 `double`，這邊改為 `uint64_t`
2. **`simulate` 函式中若為平手會 return 0.5**
浮點數 0.5 的定點數相當於將 `1ULL` 往左移縮放位元 - 1 個位置
4. **`calculate_win_value` 函式中的 return 值**
```diff
double calculate_win_value(char win, char player)
{
if (win == player)
- return 1.0;
+ return 1ULL << FIXED_SCALING_BITS;
if (win == (player ^ 'O' ^ 'X'))
- return 0.0;
+ return 0ULL;
- return 0.5;
+ return 1ULL << (FIXED_SCALING_BITS - 1);
}
```
4. `uct_score` 的計算
```c
score / n_visits +
EXPLORATION_FACTOR * sqrt(log(n_total) / n_visits);
```
#### sqrt 改為定點數計算
> 參考 [SuNsHiNe-75](https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/r1V9YJI26)
>
此函示採用[二分法](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%88%86%E6%B3%95_(%E6%95%B8%E5%AD%B8))，假設我們的目標要計算出 $x\approx\sqrt{n}$ 中的 $x$，將兩邊分別平方後會得到 $x^2\approx n$，也就是需要找出 $x$ 使得 $x^2$ 逼近 $n$
##### 實作流程:
1. 先將左右兩邊區間 ( left，right ) 設為 `0ULL` 和 `n` (其中 `n` 為定點數)
2. 以 `fixed_power_int(mid,2)` 計算出 $mid^2$ 並且判斷是否大於 $n$
* 大於 : 改變區間 ( left，right ) 為 ( left，mid )
* 小於 : 改變區間 ( left，right ) 為 ( mid，right )
3. 計算 left 和 right 的中心點為 mid
1. 以 `abs(mid-last) > eps` 判斷上次的 mid 和這次算出來的 mid 差距是否小於 eps，若小於則結束逼近，大於則回到步驟 2 繼續進行判斷，其中 eps 設定為 `1ULL`，而 `mid` 和 `last` 都是以定點數進行表示
2. 最後 return `mid`
實驗時會用以下巨集將定點數轉回浮點數，其中 `LOAD_INT` 是算出整數部分，而 `LOAD_FRAC` 是算出小數部份
```c
#define FIXED_1 (1<<FIXED_SCALING_BITS)
#define LOAD_INT(x) ((x) >> FIXED_SCALING_BITS)
#define LOAD_FRAC(x) \
((double)((x) & (FIXED_1 - 1))) / ((double)(1 << FIXED_SCALING_BITS))
```
以下為使用二分法找出近似於 $\sqrt{n}$ 的實驗結果
另外，剛開始的實驗的時候因為初始化的區間設定在 ( left，right ) = ( `1ULL`，`n` )，而 $x$ 介於 0 到 1 之間時，$\sqrt{n}$ 的數值會大於 $n$，所以假設不調整初始化的區間，在介於 0 到 1 區間時，$\sqrt{n}$ 的結果最多只能為 `n`，如下圖
所以需要在程式碼中預先判斷是否介於 0 到 1 之間，如果是就需要調整初始化的區間到 ( left，right ) = (`n`，`1ULL << FIXED_SCALING_BITS`)，經過調整後誤差值降低了很多
##### sqrt 以定點數計算程式碼：
```c
uint64_t fixed_sqrt(uint64_t n)
{
uint64_t eps = 1ULL;
uint64_t left = 0ULL;
uint64_t right = n;
uint64_t mid = 0;
uint64_t last;
if (n < 0)
return 0;
if (n < (1 << FIXED_SCALING_BITS)) {
left = n;
right = 1ULL << FIXED_SCALING_BITS;
mid = n;
}
do {
if (fixed_power_int(mid, 2) > n)
right = mid;
else
left = mid;
last = mid;
mid = left + ((right - left) / 2);
} while (abs(mid - last) > eps);
return mid;
}
```
#### log 改為定點數計算
此函式的作法一樣採用[二分法](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%88%86%E6%B3%95_(%E6%95%B8%E5%AD%B8))逼近，但是現在我們的目標是要計算出 $\ln n = x$，也就是 $e^x = n$，所以一樣逐步逼近，找出對應的 $x$
###### 數學方法：
用區間 $e^s$ 和 $e^d$ 逐步逼近 n
每次迭代都去計算出 $\sqrt{e^{s+d}}=e^{\frac{s+d}{2}}$ 並判斷 n 落在 ($e^{\frac{s+d}{2}}$ ，right ) 還是 ( left，$e^{\frac{s+d}{2}}$）以改變下次區間
###### 實作流程：
1. 在定義初始化區間( left，right )之前先定義出次方的值，其中 `d` 利用 `(31 - __builtin_clz(n | 1) + 1` 找出 `n` 最高位元 bit 的位置 + 1，之後扣掉設定好的縮放位元是因為 n 為定點數，最後需要再 `<< FIXED_SCALING_BITS` 轉成定點數儲存
例如 $n$ 為 $23$ 的定點數，先算出最高位元 + 1 為 $16+1=17$，扣掉縮放位元 12 後為 5 ，最後再轉成定點數儲存，原因是 $n = 23$ 的最高區間不會超過 $e^5$
```c
uint64_t s = 1 << FIXED_SCALING_BITS;
uint64_t d = ((31 - __builtin_clz(n | 1)) + 1 - FIXED_SCALING_BITS )
<< FIXED_SCALING_BITS;
```
2. 設定初始化區間( left，right )為 $e^s$ 和 $e^d$ 的定點數，因為初始化時 $s$ 和 $d$ 都是用定點數表示的整數，所以可以使用 `fixed_power_int` 進行計算
```c
uint64_t left = fixed_power_int(e, s >> FIXED_SCALING_BITS);
uint64_t right = fixed_power_int(e, d >> FIXED_SCALING_BITS);
```
3. 判斷新區間為( left，mid )還是( mid，right )
4. 計算 mid 為 $\sqrt{e^{s+d}}$，並且儲存 ${\frac{s+d}{2}}$ 到 `expp` 中
5. 以 `abs(mid-last) > eps` 判斷上次的 mid 和這次算出來的 mid 差距是否小於 eps，若小於則結束逼近，大於則回到步驟 3
6. 最後 return `expp`，也就是 $e^x \approx n$ 中的近似值 $x$
##### log 以定點數計算程式碼：
```c
uint64_t fixed_log(uint64_t n)
{
uint64_t eps = 1ULL;
uint64_t e = (uint64_t)(2.71828 * (1 << FIXED_SCALING_BITS)); // e = 11134
uint64_t s = 1 << FIXED_SCALING_BITS;
uint64_t d = ((31 - __builtin_clz(n | 1)) - FIXED_SCALING_BITS + 1)
<< FIXED_SCALING_BITS;
uint64_t left = fixed_power_int(e, s >> FIXED_SCALING_BITS);
uint64_t right = fixed_power_int(e, d >> FIXED_SCALING_BITS);
uint64_t mid = left;
uint64_t last;
uint64_t expp = s;
if (n < 1)
return 0;
do {
if (mid > n) {
right = mid;
d = expp;
} else {
left = mid;
s = expp;
}
last = mid;
mid = mysqrt_2((left * right) >> FIXED_SCALING_BITS);
expp = (s + d) / 2;
} while (abs(mid - last) > eps);
return expp;
}
```
##### 實驗結果：
測試 $\ln x$ 的 $x$ 大於 1000 時的結果：
Sign in with Wallet
Connect another wallet