---
# System prepended metadata

title: 2024q1 Homework1 (lab0)

---

# 2024q1 Homework1 (lab0)
contributed by < [han1018](https://github.com/Han1018) >

#### Reviewed by `HenryChaing`
>可以在 list_sort.c 效能比較中，新增比較次數以及快取記憶體頁面失誤的測試項目。
其餘的 review 在底下有留言

## 開發環境
```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
    Frequency boost:     enabled
    CPU max MHz:         4208.2031
    CPU min MHz:         2200.0000
    BogoMIPS:            7200.08
```

:::danger
不需要複製作業要求，提出你的洞見和成果
:::

### 常需注意的程式撰寫風格
程式撰寫風格建議貼近 Linux 樣式，更易閱讀也易於協作。
1. C 語言縮排處理 switch 敘述的縮排方式是讓 case 與 switch 對齊
```c
    switch (c) {
    case 'h':
        usage(argv[0]);
        break;
```
2. 空格使用
關鍵字前後需加上空格，e.g., if/else, do/while, 
```c
    if (x == true) {
        do_y();
    } else {
        do_z();
    }
    do {
        /* body of do-loop */
    } while (condition);
```


4. 二元運算子和三元運算子周圍新增一個空格
e.g., `= + - < > * / % | & ^ <= >= == != ? :`

5. `,` 點後需要加上空格
```c
    typedef struct {
        int width, height;
    } screen_t;
```

:::warning
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，operator 是「運算子」
:::

## Valgrind 分析記憶體問題
Valgrind 是個在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能。
由 dynamic Binary Instrumentation (DBI) 著重於二進位執行檔的追蹤與資訊彙整後，進行資料分析。shadow values 技術來實作，後者要求對所有的暫存器和使用到的主記憶體做 shadow (即自行維護的副本)，這也使得 Valgrind 相較其他分析方法會較慢。
* shadow value：指的是保留每一個暫存器以及被使用到的主記憶體的複製版本，也因此需花費更多時間。
* 參見 [Valgrind: a framework for heavyweight dynamic binary instrumentation](https://dl.acm.org/doi/10.1145/1273442.1250746)

簡易而言，Valgrind 用作追蹤/分析程式的效能以及安全性(e.g., Memory Leak,  Invalid Memory Access)。每次完成階段開發，便可以用於檢測。

### 使用案例
1. Memory Leak

:::danger
改進漢語表達。

台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的語言模型差。
:::

Memory Leak 類型
>definitely lost: 真的 memory leak
indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。

:::warning
"command" 一詞的翻譯是「命令」，常見於終端機裡頭執行的 shell，而 "instruction" 的翻譯是「指令」，特別指在 CPU (central processing unit，中央處理單元) 所執行的 instruction。儘管在漢語中，這兩個詞彙很容易相互混淆，但「Linux 核心設計/實作」課程特別強調兩者差異，並期望學員務必使用精準的用語。
:::

完成 C/C++ 程式編譯後，下命令 <s>指令</s>檢查: 
```shell
$ valgrind -q --leak-check=full [執行程式檔]
```

`-q`：安靜模式，只輸出錯誤訊息。
`--leak-check=full`: Valgrind 在程式運行結束後進行完整的記憶洩漏檢查。這意味著 Valgrind 將檢查在程式執行期間動態分配的所有記憶體，並且報告未被釋放的記憶體區塊。

2. Invalid Memory Access
檢查配置記憶體是否在合法範圍之外的地方進行記憶體操作，或用了已釋放的記憶體。可能造成 segmentation fault

> segmentation fault：程式試圖存取不被允許存取或不存在的暫存位置，從而導致作業系統終止程式。

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
程式範例：
```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main(void) {
    /* 1. Invalid write */
    char *str = malloc(4);
    strcpy(str, "Briant");
    free(str);

    /* 2. Invalid read */
    int *arr = malloc(3);
    printf("%d", arr[4]);
    free(arr);

    /* 3. Invalid read */
    printf("%d", arr[0]);

    /* 4. Invalid free */
    free(arr);
    return 0;
}
```

Valgrind 預期產生的報告輸出：
```
==13415== Invalid write of size 2
==13415==    at 0x1086FA: main (case2.c:7)
==13415==  Address 0x522d044 is 0 bytes after a block of size 4 alloc'd
==13415==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x1086EB: main (case2.c:6)
==13415== 
==13415== Invalid write of size 1
==13415==    at 0x108700: main (case2.c:7)
==13415==  Address 0x522d046 is 2 bytes after a block of size 4 alloc'd
==13415==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x1086EB: main (case2.c:6)
==13415== 
==13415== Invalid read of size 4
==13415==    at 0x108726: main (case2.c:12)
==13415==  Address 0x522d0a0 is 13 bytes after a block of size 3 alloc'd
==13415==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x108719: main (case2.c:11)
==13415== 
==13415== Invalid read of size 4
==13415==    at 0x10874B: main (case2.c:16)
==13415==  Address 0x522d090 is 0 bytes inside a block of size 3 free'd
==13415==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x108746: main (case2.c:13)
==13415==  Block was alloc'd at
==13415==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x108719: main (case2.c:11)
==13415== 
==13415== Invalid free() / delete / delete[] / realloc()
==13415==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x10876B: main (case2.c:19)
==13415==  Address 0x522d090 is 0 bytes inside a block of size 3 free'd
==13415==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x108746: main (case2.c:13)
==13415==  Block was alloc'd at
==13415==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13415==    by 0x108719: main (case2.c:11)
```

輸出報告以換行作為每一個錯誤的輸出，依據每一個換行切分段落觀看錯誤訊息。
以第一個段落為例：
>Invalid write of size 2
at 0x1086FA: main (case2.c:7)
Address 0x522d044 is 0 bytes after a block of size 4 alloc'd
at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
by 0x1086EB: main (case2.c:6)

`Invalid write of size 2` : 指出程式的錯誤
`at` : 觸發錯誤的程式位置和行數
`Address 0x522d044 is 0 bytes after a block of size 4 alloc'd` : 造成錯誤記憶體位置的詳細資訊
`by` : 錯誤發生原因的程式位置和行數

### `Linux/list.h` 中<s>常用方法</s>



:::danger
「常用」是怎麼看出來？你對整個 Linux 核心原始程式碼做分析了嗎？
:::

`list_head` 結構體 : struct list_head { struct list_head *prev, *next; }; 用於指定鏈結串列前/後一個 Node。

`list_add / list_add_tail`：將指定的 `node` 插入 linked list `head` 的開頭或者結尾

`list_del` : `node` 從其所屬的 linked list 結構中移走，但未被釋放需自行負責釋放。

`list_empty` : 檢查 `head` 的 `next` 是否指向自身，確認 list 是否為 empty 狀態

`list_is_singular` : 確認 linked list 是否只有一個節點。

`list_move / list_move_tail` : 將 `node` 從原本的 linked list 移動到另一個 linked list `head` 的開頭或尾端。

`list_entry` : 取出 list_head 指向物件的地址

`list_for_each` : 不能更改 `node` 的迴圈使用方法

`list_for_each_safe` : 可以移走目前的 `node` 的迴圈，透過 safe 紀錄

## 指定的佇列操作
> 注意事項：
> 1. 使用 git commit -a 取代 git commit -m 
[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
> 2. `$ git commit --amend`：命令即可打開最近一次 Commit 的 message 檔案，提供修改。
> 3. `$ clang-format -i [modified code]` : 修改程式撰寫風格至符合專案風格

list 示意圖如下圖：
![list示意圖](https://hackmd.io/_uploads/ByHFSCRit.png)

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

### Lab0 的目標
用鏈結串列實作的佇列。每個鏈結串列節點都有個 value 指標，指向一段連續的記憶體 (即 C-style string，以 NULL 字元結尾的字串)，如下圖所示：
![By7YQr-nT](https://hackmd.io/_uploads/BkUM70B2T.png)

> queue 是一種具有先進先出 (FIFO, First-In-First-Out) 性質的資料容器，也就是最先被放入的資料會被最先取出。
<s> [資料來源](https://hackmd.io/@Ben1102/S1zcfIqnu) </s>
[更正資料來源](https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html)

:::danger
優先引用權威材料。Wikpedia 本身不算權威資料，其指向的材料才是。
:::

### q_new
預防記憶體不足以新增一個 `list_head`，增加 `Return null` 的處理。
>「空」(empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;

根據作業要求，`INIT_LIST_HEAD` 可以滿足空佇列開頭 (head) 值為 `NULL` 的條件。

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

台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的語言模型差。
$\to$ [2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)
:::

```c
/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (head == NULL)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}
```

:::warning
不需要額外對 `malloc` 進行轉型，亦即 `(struct list_head *)` 是多餘。請參照 C 語言規格書，以理解相關行為。
:::

:::danger
allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯
:::

根據 C11 標準（N1570），使用 `void *` 或其他非字元類型來接收 malloc() 返回值時，編譯器會自動執行適當的轉換。這種情形下，如果知道所<s>分配</s> 的記憶區塊實際上屬於特定的結構體類型，則可直接將它們視作該結構體類型的指標。
> C99 2007 7.20.3 Memory management functions 提到:
> The order and contiguity of storage allocated by successive calls to the **calloc**, **malloc**, and **realloc** functions is unspecified. **The pointer returned if the allocation succeeds ==is suitably aligned== so that ==it may be assigned to a pointer to any type of object== and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated)**. 
> 
> The **lifetime of an allocated object extends from the allocation until the deallocation.** Each such allocation shall yield a pointer to an object disjoint from any other object.
> 
>   **The pointer returned points to the start (lowest byte address) of the allocated space.** **If the space cannot be allocated, a null pointer is returned.** 
> 
> If the size of the space **requested is zero, the behavior is implementation-defined**: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

C 語言 malloc 成功時是回傳開頭位址，並且會自動對齊，因此使用上根本不需要做轉型。

```diff    
/* Create an empty queue */
struct list_head *q_new()
{
-    struct list_head *head =
-        (struct list_head *) malloc(sizeof(struct list_head));
+    struct list_head *head = malloc(sizeof(struct list_head));
    if (head == NULL)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}
```

### q_insert_head
<s>實做</s> 實作 `list_add` 插入節點至鏈結串列頭部。

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

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

參考資料 : [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{   
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;

    // 複製字串
    new_node->value = malloc(strlen(s) + 1); // +1為'\0'
    if (new_node->value == NULL) {
        free(new_node); 
        return false;
    }
    strcpy(new_node->value, s);
     
    list_add(&new_node->list, head);
    return true;
}

```
> `make test` 警告：
> Dangerous function detected in /home/deepcat/Documents/Course/linux2024/lab0-c/queue.c
52:    strcpy(new_node->value, s);

更改strcpy -> strncpy
```diff
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{   
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;

    // 複製字串
    new_node->value = malloc(strlen(s) + 1); // +1為'\0'
    if (new_node->value == NULL) {
        free(new_node); 
        return false;
    }
-    strcpy(new_node->value, s);
+    strncpy(new_node->value, s, strlen(s) + 1);
    list_add(&new_node->list, head);
    return true;
}
```

### q_free
Todo Q&A:
> #define list_entry(node, type, member) container_of(node, type, member)
> 「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#list_entry)」中`container_of 等價的包裝，符合以 list_ 開頭的命名慣例，此處的 entry 就是 list 內部的節點。`
> 。
`container_of :「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」`

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

Q1 : Node 與 Entry 分別是什麼 / 各自差異？
A1 : 目前想法是Node 是指標且指向串列節點。而 Entry 為Node指標的實體。但有一個盲點是如果Node是指標，為何不 *Node 即可以得到 Entry
```c
/* Free all storage used by queue */
void q_free(struct list_head *l) {
    struct list_head *list_iter, *_safe;
    element_t *entry;

    list_for_each_safe(list_iter, _safe, l) {
        entry = list_entry(list_iter, element_t, list);
        list_del(list_iter);
        free(entry->value);
        free(entry);
    }
    free(l);
}
```

:::warning
使用 GDB 觀察
:::

### q_insert_tail 

`strncpy` : 原本使用 strcpy 在編譯時提醒為不安全的寫法，因此做了變更。使用了安全的 string copy 方法。

`list_add_tail` / `list_add` : 這兩個方法很方便的增加 node 至 鏈結串列的頭尾部

```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;

    // 複製字串
    new_node->value = malloc(strlen(s) + 1);  // +1為'\0'
    if (new_node->value == NULL) {
        free(new_node);
        return false;
    }
    strncpy(new_node->value, s, strlen(s) + 1);

    list_add_tail(&new_node->list, head);

    return true;
}
```

### q_insert_head 

```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;

    // 複製字串
    new_node->value = malloc(strlen(s) + 1);  // +1為'\0'
    if (new_node->value == NULL) {
        free(new_node);
        return false;
    }
    strncpy(new_node->value, s, strlen(s) + 1);

    list_add(&new_node->list, head);

    return true;
}
```

### q_remove_head
解決 Error : 
> ERROR: Attempted to free unallocated block.  Address = 0x55a3f6cf93b0
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x55a3f6cf93b0
ERROR: Corruption detected in block with address 0x55a3f6cf93b0 when attempting to free it
Segmentation fault occurred.  

添加了 `entry->value = NULL;` 以避免使用已經釋放的值。

```diff

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (list_empty(head))
        return NULL;

    element_t *entry = list_entry(head->next, element_t, list);
    if (entry->value != NULL) {
        strncpy(sp, entry->value, bufsize);
        free(entry->value);
+        entry->value = NULL;
    }

    // check if head is the only element
    if (head->next == head->prev) {
        list_del_init(head->next);
        return entry;
    } else {
        list_del(head->next);
        return entry;
    }
}
```

因為無論如何都需要刪除 node 所以無需檢查是否為串列尾和頭是否為同一個
```diff
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (list_empty(head))
        return NULL;

    element_t *entry = list_entry(head->next, element_t, list);
    if (entry->value != NULL) {
        strncpy(sp, entry->value, bufsize);
        free(entry->value);
        entry->value = NULL;
    }

-    // check if head is the only element
-    if (head->next == head->prev) {
-        list_del_init(head->next);
-        return entry;
-    } else {
-        list_del(head->next);
-        return entry;
-    }
    
+    list_del(head->next);
+    return entry;
}
```

### q_remove_tail

```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (list_empty(head))
        return NULL;

    element_t *entry = list_entry(head->prev, element_t, list);
    if (entry->value != NULL) {
        strncpy(sp, entry->value, bufsize);
        free(entry->value);
        entry->value = NULL;
    }

    // check if head is the only element
    if (head->next == head->prev) {
        list_del_init(head->prev);
        return entry;
    } else {
        list_del(head->prev);
        return entry;
    }
}
```

因為無論如何都需要刪除 node 所以無需檢查是否為串列尾和頭是否為同一個
```diff
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (list_empty(head))
        return NULL;

    element_t *entry = list_entry(head->next, element_t, list);
    if (entry->value != NULL) {
        strncpy(sp, entry->value, bufsize);
        free(entry->value);
        entry->value = NULL;
    }

-    // check if head is the only element
-    if (head->next == head->prev) {
-        list_del_init(head->prev);
-        return entry;
-    } else {
-        list_del(head->prev);
-        return entry;
-    }
    
+    list_del(head->prev);
+    return entry;
}
```
`make test` 時 trace-07-string 一直無法正確，參照 [Jackiempty](https://github.com/Jackiempty) 程式注意到 stncpy 後<s>應當在最後一個位元設結束位元</s> ????，來避免 buffer size 小於 string 長度時無法將結束字元貼上而造成 segmentation fault。

> 應當在字串尾端設置結束位元，來避免 buffer size ${-1}$ 小於等於 string 長度時無法將結束位元貼上而造成的 segmentation fault。
> [name=HenryChaing]

:::danger
你在說什麼？位元是 bit，但字串是由一組連續的位元組 (byte) 構成。翻閱 C 語言規格書，用精準的術語來闡述你的所為。
:::

更正： 根據 C 語言規格書的規定，字串需要以一個 Null 結束位元組來表示字串的結尾。因此，在 buffersize - 1 位元組上指定 '\0'，以表示字串的結束。
> $ C99 6.4.4.4 example 12 : The construction '\0' is commonly used to represent the null character.
> $ C99 5.2.1 : 
> In a character constant or string literal, members of the execution character set shall be
represented by corresponding members of the source character set or by escape
sequences consisting of the backslash \ followed by one or more characters. <b>A byte with all bits set to 0, called the null character, shall exist in the basic execution character set;</b> itis used to terminate a character string.

```diff
if (entry->value != NULL) {
    strncpy(sp, entry->value, bufsize);
+        sp[bufsize - 1] = '\0';
}
```

### q_delete_mid
參考[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)實作

```c
// 快慢指標, fast 走兩步, slow 走一步, fast 到達終點時 slow 剛好是一半
while (fast->next != head->prev && fast->next->next != head->prev) {
    slow = slow->next;
    fast = fast->next->next;
}
slow = slow->next;

// 取出node, remove, delete
```

> 註解採用美式英文命名較恰當，參閱 [CONTRIBUTING.md](https://github.com/HenryChaing/lab0-c/blob/master/CONTRIBUTING.md#coding-convention)。
> [name=HenryChaing]

### q_delete_dup

:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

1. 將串列升冪排序，以便讓相同的字串或數字彼此相鄰。
2. <s>遍歷</s> 串列，刪除相鄰重複的項目。

> 可以使用走訪一詞。 參閱： [詞彙釋義]([https:/](https://hackmd.io/@sysprog/it-vocabulary#%E8%A9%9E%E5%BD%99%E9%87%8B%E7%BE%A9)/)
> [name=HenryChaing]
```c
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return true;

    // Step 1: Sort the list in ascending order
    q_sort(head, false);

    // Step 2: Delete duplicate string nodes
    struct list_head *li, *tmp;
    bool last_dup = false;

    list_for_each_safe (li, tmp, head) {
        element_t *entry = list_entry(li, element_t, list);
        element_t *next_entry = list_entry(tmp, element_t, list);

        if (tmp != head && !strcmp(entry->value, next_entry->value)) {
            last_dup = true;
            list_del(li);
            free(entry->value);
            free(entry);
        } else if (last_dup) {
            last_dup = false;
            list_del(li);
            free(entry->value);
            free(entry);
        }
    }
    return true;
}
``` 


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

### q_swap
1. 在迴圈中取出當前節點和下一個節點。
2. 交換兩個節點的值。

```c

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (head == NULL || list_is_singular(head))
        return;

    struct list_head *li, *tmp;

    list_for_each_safe (li, tmp, head) {
        if (li == head->prev)
            return;

        element_t *node = list_entry(li, element_t, list);
        element_t *next_node = list_entry(tmp, element_t, list);

        // swap node and next node string
        char *tmp_string = node->value;
        node->value = next_node->value;
        next_node->value = tmp_string;
    }
}
```

原方法是轉換字串的位置，而不是轉換整個 Node，使用現有函示+更簡潔方式轉換 Node。
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_is_singular(head) || list_empty(head))
        return;

    struct list_head *li, *tmp;

    for (li = head->next, tmp = li->next; li != head && tmp != head;
         li = li->next, tmp = li->next) {
        list_move(li, tmp);
    }
}
```
### q_reverse & q_reverse
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

Reverse :
1. 在迴圈中取出下一個節點並將其放置於串列的頭部。
2. <s>遍歷</s>迴圈後可得到反轉的串列。

Reverse_K : 
1. 在 Reverse 基礎上進行一些改變。
2. 每經過 k 次迴圈後，從前 k 個節點中取出並反轉
3. 將反轉串列放回原始串列。

```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head *end = head->prev;
    struct list_head *current = head->next;
    while (current != end) {
        struct list_head *next = current->next;
        list_move(current, head);
        current = next;
    }
    list_move(current, head);  // add last node
}
```

```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node, *safe, target, *last_k_head = head;
    int count = 0;
    INIT_LIST_HEAD(&target);
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            list_cut_position(&target, safe, node);  // cut k nodes
            q_reverse(&target);                      // reverse k nodes
            list_splice_init(&target, last_k_head);
            count = 0;
            last_k_head = safe->prev;
        }
    }
}
```
增加 list_head 為空的判斷，避免 segmentation fault
```c
if (!head || list_empty(head) || list_is_singular(head))
    return;
```


### q_sort

:::danger
避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。

授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程所在意的事。

濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。
:::

實作 `quick sort` 遞迴版本。
1. 取出第一個節點作為 pivot。
2. 根據需求，比較 pivot 的值，將較小或較大的值放入新的串列中，然後進行分割。
3. 對新串列執行快速排序。
4. 最後將排序好的串列加回原始串列。

```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    struct list_head list_less, list_greater;
    element_t *pivot;
    element_t *item = NULL, *tmp = NULL;

    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    pivot = list_first_entry(head, element_t, list);
    list_del(&pivot->list);

    list_for_each_entry_safe (item, tmp, head, list) {
        if (descend == false) {
            if (strcmp(item->value, pivot->value) < 0)
                list_move_tail(&item->list, &list_less);
            else
                list_move_tail(&item->list, &list_greater);
        } else {
            if (strcmp(item->value, pivot->value) > 0)
                list_move_tail(&item->list, &list_less);
            else
                list_move_tail(&item->list, &list_greater);
        }
    }

    q_sort(&list_less, descend);
    q_sort(&list_greater, descend);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}
```
預期 quick sort 可以達到 O(nlogn) 的時間複雜度，但在測資上無法通過因此改實作 Merge sort，並通過了測資 O(nlogn) 要求。
:::warning
你好，想請問 quick sort 無法達到 O(nlogn) ,除了測資以外, 還有使用什麼方式來確認或推導呢?

> 這裡我修改是因為無法通過測試項目的時間複雜度 O(nlogn)，根據 [quick sort](https://zh.wikipedia.org/zh-tw/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) 解釋，只有在極端情況下才會讓時間複雜度成為 $O(n^2)$ ，極大部分時間複雜度為 $O(n logn)$。檢查程式碼後我覺得是因為我 pivot 沒有隨機取，而是取第一個 `node` 為 `pivot`，才導致演算法沒有達到 $O(n logn)$。
:::

```c
void merge(struct list_head *l_head,
           struct list_head *r_head,
           struct list_head *head)
{
    while (!list_empty(l_head) && !list_empty(r_head)) {
        element_t *l_entry = list_entry(l_head->next, element_t, list);
        element_t *r_entry = list_entry(r_head->next, element_t, list);

        if (strcmp(l_entry->value, r_entry->value) <= 0)
            list_move_tail(l_head->next, head);
        else
            list_move_tail(r_head->next, head);
    }
    if (!list_empty(l_head))
        list_splice_tail_init(l_head, head);
    else
        list_splice_tail_init(r_head, head);
}

void merge_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    // Find middle node
    struct list_head *slow = head, *fast = head;
    do {
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != head && fast->next != head);

    LIST_HEAD(l_head);
    LIST_HEAD(r_head);

    // Split list into two parts - Left and Right
    list_splice_tail_init(head, &r_head);
    list_cut_position(&l_head, &r_head, slow);
    // Recursively split the left and right parts
    merge_sort(&l_head);
    merge_sort(&r_head);
    // Merge the left and right parts
    merge(&l_head, &r_head, head);
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    merge_sort(head);

    if (descend)
        q_reverse(head);
}
```

### q_ascend / q_descend
1. 進行升冪排序，使用迴圈尋找並比較前一個最小的值。
2. 若遇到比前一個更小的值，則從串列中刪除前一個最小值的位置到當前節點。
3. 進行降冪排序，尋找比前一個最大的值更大的值。

```c
/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    struct list_head *last_biggest, *tmp, *li;
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;

    element_t *last_biggest_entry = list_entry(head->next, element_t, list);
    last_biggest = head->next;

    list_for_each_safe (li, tmp, head) {
        element_t *entry = list_entry(tmp, element_t, list);
        if (li == head->prev) {
            continue;
        }
        if (strcmp(entry->value, last_biggest_entry->value) < 0) {
            while (last_biggest != tmp) {
                struct list_head *next = last_biggest->next;
                last_biggest_entry = list_entry(last_biggest, element_t, list);

                list_del(last_biggest);
                free(last_biggest_entry->value);
                free(last_biggest_entry);

                last_biggest = next;
            }
            last_biggest_entry = list_entry(last_biggest, element_t, list);
        }
    }

    // calculate size
    int size = 0;
    list_for_each_safe (li, tmp, head) {
        size++;
    }
    return size;
}
```

### q_merge

1. 將串列中所有佇列插入至第一個佇列
2. 排序第一個佇列

```c
/* Merge all the queues into one sorted queue, which is in
 * ascending/descending order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    // insert all queue into one queue
    queue_contex_t *output = list_entry(head->next, queue_contex_t, chain);
    queue_contex_t *current = NULL;
    list_for_each_entry (current, head, chain) {
        if (current == output)
            continue;
        list_splice_init(current->q, output->q);
        output->size = output->size + current->size;
        current->size = 0;
    }

    // sort
    q_sort(output->q, descend);
    return 0;
}
```
:::warning
你好，我在 `q_merge` 這個函式參考了你的寫法，其中 `queue.h` 中有說明回傳值為合併後的佇列大小，我想你似乎沒注意到。
> 謝謝 我再修正！
:::
根據提醒，回傳了合併後的佇列大小：

```diff
// calculate size
+int size = 0;
+struct list_head *li, *tmp;
+list_for_each_safe (li, tmp, output->q) {
+    size++;
+}
+return size;
-return 0;
```

---

## lib/list_sort.c 並嘗試引入到 lab0-c 專案
閱讀 `lib/list_sort.c` 對於程式中的 `likely` 感到疑惑，發現這是存在於 Linux 中的巨集。
```c
# define likely(x)	__builtin_expect(!!(x), 1)     
# define unlikely(x)	__builtin_expect(!!(x), 0)
```

<s>
[__built_expect()](https://www.ibm.com/docs/en/zos/2.4.0?topic=performance-builtin-expect) 是gcc的內建function，提供表達式和預期的值給編譯器，讓編譯器對程式碼進行優化。
</s>

:::danger
參照 GCC 手冊。
:::

而 `!!(x)` 意思，透過兩次 NOT 操作以確保值一定是 0 或 1。因為 if 內邏輯敘述的值可以是 0 或是非 0 的整數的，所以如果不做!!(x)就無法確保值一定是 0 或 1。

### 引入 list_sort.c

- 下載 list_sort.c & list_sort.h 程式至 lab0-c 專案底下，並在 queue.c 中加入標頭檔

更改 u8 至 uint8_t,  定義兩個 list_sort 中使用的兩個巨集, 刪除沒用到的 priv
```c
typedef unsigned char uint8_t;
# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)
```

- 修改 makefile 檔進行讓 list_sort 可以被編譯
```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 \
+       list_sort.o \
        linenoise.o web.o
```

詳細程式 : [df0aaf7](https://github.com/han1018/lab0-c/commit/df0aaf7f8c1ee4fc71b6082d64a3a61dee8356c9)

### 效能比較
參考 [ chiangkd ](https://hackmd.io/duPg38XOTL-XKa7_h0Ielw?view#%E7%A0%94%E8%AE%80-list_sortc-%E4%B8%A6%E5%BC%95%E5%85%A5%E5%B0%88%E6%A1%88)效能比較方法。隨機加入一百萬個 `node` 至佇列，比較 `my_sort` 和 `list_sort` 執行速度。

`qtest.c` 中 `console_init()` 中新增命令 list_sort 以及實作 do_list_sort()
```c
ADD_COMMAND(list_sort, "Sort queue in ascending order provided by linux kernel", "");
```

撰寫測試項目 traces/trace-sort.cmd
- `[sort]` 可以選擇剛新增的 `list_sort` 或是已寫好的 `sort`。(已經寫好的 `sort` 是實作 merge sort)。
- 透過 time 命令獲取 sort 執行的時間
- 設定 `--repeat 5` 重複五次
```bash
option fail 0
option malloc 0
new
ih RAND 1000000
time
[sort]
time
```

使用 `perf` 進行效能比較，參考 [Linux 效能分析工具: Perf ](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
- 排序執行時間
- cycles
- instructions

```shell
perf stat --repeat 5 ./qtest -f traces/trace-sort.cmd
```

排序時間：
|  | my sort | list sort |
| -------- | -------- | -------- |
| 1     | 0.785s     | 0.808s   |
| 2      | 0.810s   | 0.803s     |
| 3      | 0.798s     | 0.809s     |
| 4    | 0.817s | 0.807s |
| 5    | 0.826s | 0.801s |

list_sort 的運行時間穩定在 0.803 的上下浮動。而 my_sort 雖然有時候比 list_sort 快，但大多數情況下比 list_sort 慢，而且在慢的時候表現更為明顯。

cycles & instructions 結果如下：
```shell 
/*my sort */
 Performance counter stats for './qtest -f traces/trace-sort.cmd' (5 runs):
           1523.71 msec task-clock                       #    0.999 CPUs utilized               ( +-  0.46% )
                 6      context-switches                 #    3.938 /sec                        ( +- 13.94% )
                 1      cpu-migrations                   #    0.656 /sec                        ( +- 67.82% )
            3,5234      page-faults                      #   23.124 K/sec                       ( +-  0.00% )
      63,2367,9181      cycles                           #    4.150 GHz                         ( +-  0.13% )  (83.35%)
       1,9661,4495      stalled-cycles-frontend          #    3.11% frontend cycles idle        ( +-  2.03% )  (83.37%)
      33,1120,7963      stalled-cycles-backend           #   52.36% backend cycles idle         ( +-  0.37% )  (83.37%)
      50,1536,8542      instructions                     #    0.79  insn per cycle            
                                                  #    0.66  stalled cycles per insn     ( +-  0.14% )  (83.38%)
       7,6236,8673      branches                         #  500.337 M/sec                       ( +-  0.13% )  (83.38%)
         4822,7328      branch-misses                    #    6.33% of all branches             ( +-  0.28% )  (83.15%)

           1.52451 +- 0.00698 seconds time elapsed  ( +-  0.46% )
           
 /*list_sort */
 Performance counter stats for './qtest -f traces/trace-sort.cmd' (5 runs):

           1506.33 msec task-clock                       #    1.000 CPUs utilized               ( +-  0.31% )
                 4      context-switches                 #    2.655 /sec                        ( +- 20.92% )
                 0      cpu-migrations                   #    0.000 /sec                      
            3,5235      page-faults                      #   23.391 K/sec                       ( +-  0.00% )
      62,7764,9618      cycles                           #    4.168 GHz                         ( +-  0.34% )  (83.32%)
       2,0760,8002      stalled-cycles-frontend          #    3.31% frontend cycles idle        ( +-  4.76% )  (83.38%)
      31,2053,1984      stalled-cycles-backend           #   49.71% backend cycles idle         ( +-  0.69% )  (83.38%)
      49,3407,5477      instructions                     #    0.79  insn per cycle            
                                                  #    0.63  stalled cycles per insn     ( +-  0.36% )  (83.38%)
       7,6812,7783      branches                         #  509.934 M/sec                       ( +-  0.20% )  (83.38%)
         4863,2496      branch-misses                    #    6.33% of all branches             ( +-  0.30% )  (83.16%)

           1.50704 +- 0.00467 seconds time elapsed  ( +-  0.31% )
```

整理重要項為表格 :
|  | my sort | list sort |
| -------- | -------- | -------- |
| cycles     | 63,2367,9181     | 62,7764,9618     |
| task clock     | 1523.71 msec   | 1510.40 msec     |
| context switches     | 6     | 4     |
| instructions    | 50,1536,8542 | 49,3407,5477 |

list_sort 確實有比 my_sort 更加快速

> 可以觀察比較次數以及快取頁面失誤的改善，參閱： [共筆示範](https://hackmd.io/@sysprog/linux2022-sample-lab0#%E7%94%A8%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E5%B7%A5%E5%85%B7%E6%AF%94%E8%BC%83-list_sortc-%E5%8F%8A%E8%87%AA%E5%B7%B1%E5%AF%A6%E4%BD%9C%E7%9A%84%E6%8E%92%E5%BA%8F)
> [name=HenryChaing]

---

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

參考論文 [<Dude, is my code constant time?>](https://eprint.iacr.org/2016/1123.pdf) 、[dudect](https://github.com/oreparaz/dudect)、以及 [chiangkd](https://hackmd.io/@chiangkd/dudect-study)、[Lccgth](https://hackmd.io/@subsidium/linux2024-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87-%E3%80%88-Dude-is-my-code-constant-time-%E3%80%89) 撰寫的導讀筆記

論文介紹的量測程式碼的方法 [dudect](https://github.com/oreparaz/dudect)，用以量測其時間複雜度是否為常數時間 O(1)。

### 實驗方法
對執行時間進行洩漏檢測，然後分析時間分佈是否存在差異。

1. 量測方法：
採用 fix-vs-random 的方法，將第一組輸入設定為固定值，而第二組輸入則會根據每次的量測隨機設定
2. 後處理 :
在進行統計分析之前，需要對每次的量測結果進行後處理。由於大部分的量測值會集中在較小的執行時間，但也會有一小部分量測值出現特別高的執行時間，這可能導致時間分佈呈現正偏態。因此，需要對結果進行篩選或取捨，以確保統計分析的準確性。
    > 負偏態 : 左右不對稱，眾數偏右，眾數>中位數>平均數。
    常態 : 左右對稱，眾數在中間，眾數=中位數=平均數。
    正偏態 : 左右不對稱，眾數偏左，眾數<中位數<平均數。
    ![image alt](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Negative_and_positive_skew_diagrams_%28English%29.svg/800px-Negative_and_positive_skew_diagrams_%28English%29.svg.png)

3. 統計測試:
使用 Welch 的 t 檢驗來測試兩組數據的時間分佈是否相等(e.g., 平均數是否相同)。如果檢驗結果顯示不相等，則可能意味著存在時間洩漏。

### 解釋 [Student's t-distribution](https://zh.wikipedia.org/wiki/%E5%8F%B8%E5%BE%92%E9%A0%93t%E5%88%86%E5%B8%83) 
t 分佈是一種機率分佈，通常用於小樣本來估計未知標準差的母體期望值。t 分佈的自由度 v 控制其分佈的形狀，當 v 值越低時，出現極端值的概率較高，而當 v 值越高時，分佈越接近常態分佈

![image alt](https://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Student_t_pdf.svg/650px-Student_t_pdf.svg.png)

### 現有實作存在若干致命缺陷，請討論並提出解決方案

如同前面提到的，用小樣本來估計未知標準差的母體時可能會出現一些極端值，形成正偏態，量測出特別高的執行時間。因此，需要對結果進行篩選或取捨，以確保統計分析的準確性。

作業要求中提到「在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無」。這是一個潛在問題，如果沒有針對極端值進行篩選掉，會影響到分析的準確性。對照 lab0-c 中程式碼，確實沒有發現對 percentile 的處理。

參考了 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E8%A7%A3%E9%87%8B-simulation-%E5%81%9A%E6%B3%95) 對 simulation 的解釋，發現檢測常數時間的函式位於 `./dudect/fixture.c` 中。參照 `dudect` 的實作，在該檔案中增加了 percentile 處理，並補上了 dudect 實作的函式。在 doit 函式中的 update_statistics 前加入了 prepare_percentiles() 函式，去除極端值。
```c
static int cmp(const int64_t *a, const int64_t *b)
{
    return (int) (*a - *b);
}

static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
  size_t array_position = (size_t)((double)size * (double)which);
  assert(array_position < size);
  return a_sorted[array_position];
}

/*
 set different thresholds for cropping measurements.
 the exponential tendency is meant to approximately match
 the measurements distribution, but there's not more science
 than that.
*/
static void prepare_percentiles(int64_t *exec_times) {
    qsort(exec_times, N_MEASURES, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
    for (size_t i = 0; i < N_MEASURES; i++) {
        exec_times[i] = percentile(exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / N_MEASURES)), N_MEASURES);
    }
}
```
在 `dudect` 中 update_statistics() 放棄了前 10 個量測值，而非從頭開始，於是在 lab0-c 也做了對應的更改。
```diff
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
-    for (size_t i = 0; i < N_MEASURES; i++) {
+    for (size_t i = 10; i < N_MEASURES; i++) {
```
修改後，通過了 trace-17-complexity 測資，達到 100/100。

## 在 qtest 提供新的命令 shuffle
實作 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#cite_note-knuth-5) 演算法現代版本 - [Algorithm P (Shuffling)](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#cite_note-knuth-5) 對佇列洗牌

步驟：
1. 從佇列中取出最後一個節點，將其標記為 `last`，表示尚未進行隨機排序。
2. 在佇列中隨機選擇一個節點 K，與 `last` 節點進行交換。
3. 更新 `last` 為 `last` 前一個節點
4. 重複步驟 2 和 3，直到 `last` 為佇列的首節點。

時間複雜度 : O(n)

> 第四步驟的 last 應該只會移動到佇列首節點的下個節點，在你附的 Wikipedia 當中虛擬碼所述。
> [name=HenryChaing]

參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Modern-method)，實作 q_shuffle 和對應的命令。

> commit : [d9c7543](https://github.com/Han1018/lab0-c/commit/d9c75430d9e6b0fd57a27c374d8eb045834f3b32)
```c
void q_shuffle(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return;

    int size = q_size(head);
    struct list_head *last = head->prev;

    while (last != head && --size) {
        int index = rand() % size;
        struct list_head *node = head->next, *temp = last->prev;
        while (index--)
            node = node->next;

        list_move(last, node->prev);
        if (node != temp)
            list_move(node, temp);
        last = node->prev;
    }
}
```

---

## 整合 tic-tac-toe

### 轉移 ttt 至 Lab0-c 專案
轉移的方法是將 ttt 下除了 main.c 外所有的 .c 和 .h 檔案複製至 lab0-c 專案中。在 ttt 下的棋程式中，有多種演算法可供與人對弈，我首先引入至 lab0-c 專案的是 ttt 專案中預設的 negamax 演算法。

> 例如， train.c , elo.c 應該不用加入專案中。 
> [name=HenryChaing]

接著，將 ttt 專案中的 main.c 程式碼複製到 qtest.c 檔案中。將控制遊戲運行的 main 函式重新命名為 do_ttt()，並在命令列中新增一個命令 ttt 來執行遊戲。
```c
ADD_COMMAND(ttt, "Tic-Tac-Toe Game", "");
```

在提交時，發現 mt19937-64.c 程式碼中有一些<s>語句</s> 敘述 (statement) 無法通過 precommit-hook 的檢查。由於希望盡可能不修改原始程式碼，因此在 pre-commit.hook 中忽略了對 mt19937-64.c 的檢查。
```shell
--suppress=nullPointer:zobrist.c \
```
> commit [d467084](https://github.com/Han1018/lab0-c/commit/d467084)

:::warning
實際需要調整的程式碼不多，你該嘗試更改。
> ok! 已做對應修改 commit [adfa401](https://github.com/Han1018/lab0-c/commit/adfa401)
:::
### Monte Carlo tree search (MCTS) 演算法

使用 mcts 取代預設的 `negamax` 演算法，並且刪除 `negamax` 相關的程式碼，mt19937-64、negamax、train.c、zobrist。
> commit [adfa401](https://github.com/Han1018/lab0-c/commit/adfa401)

TODO : 使用定點數來取代原本 jserv/ttt 的浮點數運算。

### 引入新的 option 命令，提供電腦對奕
增加 `option` 指令 `ai_mode`，讓 AI 和 AI 對弈，使用的演算法是 `negamax`。
```c
static int ai_ai_mode = 0;
if (ai_ai_mode) {
            draw_board(table);
            int move = negamax_predict(table, turn).move;
            if (move != -1) {
                table[move] = turn;
                record_move(move);
            }
add_param("ai_mode", &ai_ai_mode, "Set AI vs AI mode", NULL);
```
預設值為 0，欲更改時需要設定 `ai_mode` 的參數。在 `qtest` 要下的命令是：`option ai_mode 1`
> commit : [13ad69f](https://github.com/Han1018/lab0-c/commit/13ad69f)

螢幕顯示當下的時間 (含秒數):
```c
static void show_time()
{
    struct timeval currentTime;
    gettimeofday(&currentTime, NULL);
    time_t rawtime;
    time(&rawtime);
    struct tm *timeinfo = localtime(&rawtime);
    printf("Current Time: %02d:%02d:%02d:%02ld\n", timeinfo->tm_hour,
           timeinfo->tm_min, timeinfo->tm_sec, currentTime.tv_usec / 10000);
}

```
> commit : [a52b4ca](https://github.com/Han1018/lab0-c/commit/a52b4ca)

### 引入若干 coroutine

## 問題詢問
>參考一：#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)
         
> 參考二：linux/list.h 是 Linux 核心中相當實用的 circular doubly-linked list (雙向環狀鏈結串列，以下簡稱 list) 封裝，只要在自定義的結構中加入 struct list_head，就可以搭配 Linux 中一系列的 linked list 操作 (詳見The Linux Kernel API - List Management Functions) 來建立自定義結構的 linked list。
> [資料來源](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)


1. 為何是 `node != (head);` 而不是`node != (head)->next` 在 `Linux/list.h` 中串列為 `circular linked list`，最後一個節點的 Next 指向的節點以為第一個？

    Ans : 最後一個節點指向下一個節點的 list_head 是指向 head，這樣形成了循環<s>鏈表</s>，而第一個節點是接在 `head` 之後的。

:::danger
linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「[表](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)

circular linked list 翻譯為「環狀鏈結串列」。
:::

2. <s>測資七</s>主要是測試哪些方法？嘗試用 make valgrind 找出錯誤地方但只有出現 `32 bytes in 1 blocks are still reachable in loss record 1 of 43`

:::danger
這裡是「測試項目」(item)，而非「資料」(data)，請查閱辭典以理解二者的差異。
> 暸解！
:::

>+++ TESTING trace trace-07-string:
> Test of truncated strings 
>ERROR: Removed value meerkat_panda_squirrel_vulture_XX...省略...XXX != expected value meerkat_panda_squirrel_vulture

:::warning
TODO: 嘗試變更測試計畫
> ok!
:::


> 合併方式是當有 $3 \times 2^k$ 個節點時，合併前兩個 $2^k$ 變成 $2^{k + 1}$，並留下一個 $2^k$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要 $3 \times 2^k$ 可以放得進 L1 cache，可以避免 cache thrashing。`count` 為 pending list 中節點的數量，在 `count` 變 `count + 1` 後，可以觀察到第 `k` 個位元會改為 1，0 ~ `k - 1` 個 bit 會變 0，此時會將 2 個 $2^k$ 合併，並留下一個 $2^k$。

3. 在[Linux核心的鏈結串列排序](https://hackmd.io/-CaD-D3aS-q_-MvsoDRQqA?view#)中提到合併方式是當有 $3 \times 2^k$ 個節點時，我想請問老師 $3 \times 2^k$ 個節點的意思是什麼？因為後面提到將「$3 \times 2^k$ 可以放得進 L1 cache」時，我想到記憶體位置通常是2的倍數，這部分我無法理解為什麼是3。
    Ans : [為什麼 list_sort 中串列大小的比例差距限制是 2 : 1](https://hackmd.io/-CaD-D3aS-q_-MvsoDRQqA?view#%E7%82%BA%E4%BB%80%E9%BA%BC-list_sort-%E4%B8%AD%E4%B8%B2%E5%88%97%E5%A4%A7%E5%B0%8F%E7%9A%84%E6%AF%94%E4%BE%8B%E5%B7%AE%E8%B7%9D%E9%99%90%E5%88%B6%E6%98%AF-21)
5. 「因為只要可以放得進 L1 cache，可以避免 cache thrashing」這句話不理解，<s>想請問老師下什麼關鍵字搜尋比較適合？</s>

:::danger
不要只想找關鍵字，為何不閱讀計算機組織/計算機結構的教科書呢？你需要全面而非零碎的知識來源。
> 好！會再查閱計算機組織書籍
:::


6. 閱讀[fork 帶來的 vm_area_struct 開銷](https://hackmd.io/@sysprog/unix-fork-exec#fork-%E5%B8%B6%E4%BE%86%E7%9A%84-vm_area_struct-%E9%96%8B%E9%8A%B7)時有疑問，為何講說 `fork` 後執行 `exec` 的記憶體開銷會轉瞬即逝很難捕捉到，為什麼沒辦法知道記憶體使用狀況？
> 和上個部份的分頁表開銷一樣，這個 vm_area_struct 物件的開銷也是轉瞬即逝的，很難捕捉到。無論如何這個開銷是沒有必要的，根本原因還是一樣，fork 中的全面複製沒有必要！

7. 「在執行新行程層面，clone 可僅僅 CLONE_VM 實作 LWP 來達成快速 exec，避免不必要的資源複製;
」這裡不理解為什麼 Linux 在行程 Clone 時需要設定 CLONE_VM。我查閱 linux manuel page，其說明設定 `CLONE_VM` 可以共享親代行程的記憶體空間。

    >  Linux manual page:
    If CLONE_VM is set, the calling process and the child process run in the same memory space.

- 問題一：如果需要共享記憶體空間爲什麼不直接建立執行緒？什麼情況下會需要設定 `CLONE_VM`？
- 問題二：共享記憶體空間後 `exec` 會覆蓋既有行程，即失去 `Fork` 替換的用意？
