# 2022q1 Homework1 (lab0)
contributed by < `freshLiver` >
###### tags: `linux2022`
## 環境
```shell
$ gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1) 10.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 167
Model name: 11th Gen Intel(R) Core(TM) i5-11400 @ 2.60GHz
Stepping: 1
CPU MHz: 2600.000
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 5184.00
Virtualization: VT-x
L1d cache: 288 KiB
L1i cache: 192 KiB
L2 cache: 3 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 實作 queue 相關函式
### 結構體說明
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
`struct list_head` 為 `list.h` 中定義的結構體，這個結構體中包含了 `prev` 與 `next` 兩個定義於 `list_head` 的指標，分別藉由指向前、後一個節點，以便實作出 circular doubly-linked list。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
`struct element_t` 為 `queue.h` 中定義的結構體，而在這個結構體中，除了定義 `value` 來儲存資料之外，也定義了結構體 `list_head` 的變數，並讓 `list_head` 中定義的 `prev` 以及 `next` 分別指向前、後一個佇列節點中的 `list`，以便在佇列中的各個節點間移動。
#### 為什麼 `element_t` 中包含了 `list_head`
這次作業檔案 `lsit.h` 中除了定義結構體 `list_head` 之外還包含了數個相關的函式以及巨集，是 [Linux 原始碼中的 list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的簡化版（少了一些 `list_head` 相關的操作函式以及 `hlist` 相關的部份）。
:::info
關於本次作業的 `list.h` 與 Linux 專案中的 `list.h` 的細節差異在[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list?type=view#Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)中有更詳細的解說
:::
而這個結構體也[在 Linux 專案中被大量重複使用](https://github.com/torvalds/linux/search?l=C&q=struct+list_head)，除了包含了 [circular doubly-linked list 相關的基本操作](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#list-management-functions)之外，若是想要在它之上定義其他變數的話，只需要另外定義新的結構體並在其中定義一個 `list_head` 的變數就可以進行擴充，而在擴充的結構體相關的操作中也可以直接使用 `list.h` 中的相關函式，而不用為每個新定義的結構體實作基本操作的函式，藉此來達到類似於其他語言中「繼承」的概念，也能夠藉由使用用這些函式以及巨集使得程式碼更簡潔、更具有可讀性。
:::warning
為什麼在這次作業要實作的相關操作函式中，都是以 `list_head` 作為參數而不是直接使用 `element_t` 作為參數？
> TODO: 思索這樣規劃帶來的效益
> :notes: jserv
在這次要完成的佇列相關操作函式幾乎都需要透過 `head` 這個節點來走訪佇列，但在 `list_head` 構成的雙向鏈結串列中， `head` 節點只負責指向串列的開頭以及結尾的節點，實際上不需要儲存資料，因此若是使用 `element_t` 作為參數的話，會出現閒置的空間造成浪費。且在走訪串列時實際還是透過 `list_head` 結構體來進行，因此也會造成存取首位、末位節點時需要使用像是 `head->list->next` 或 `head->list->prev` 這樣的額外操作。
:::
### 巨集說明
```c
#include <stddef.h>
size_t offsetof(type, member);
```
根據 [Linus manual page 中對 offsetof 的說明](https://man7.org/linux/man-pages/man3/offsetof.3.html)，`offsetof` 是一個定義在 `<stddef.h>` 中的巨集，而 `offsetof` 可以用來獲取給定結構體 `type` 中某個 field `member` 相對於該結構體起始位置的位元組偏移量。
而在 [GitHub 上 Linux 專案原始碼中的 stddef.h](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h) 檔案中有明確定義 `offsetof` 這個巨集的實作為：
```c
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#endif
```
從這邊可以看到，當編譯器沒有定義 `__compiler_offsetof` 時，會將 `offsetof` 這個巨集定義為 `((size_t)&((TYPE *)0)->MEMBER)`，而在這個定義中透過將 0 強制轉型成 `TYPE` 的指標使得該結構體的開頭地址為 0，接著再透過對該結構體中的 field `MEMBER` 取址來計算出 `MEMBER` 在這個結構體中的位元組偏移量。
:::warning
TODO : 是否會造成 null pointer dereference
:::
:::warning
TODO : man page 有提到 padding 的問題，嘗試找到關於其的詳細說明
> This macro is useful because the sizes of the fields that compose a structure can vary across implementations, and compilers may insert different numbers of padding bytes between fields. Consequently, an element's offset is not necessarily given by the sum of the sizes of the previous elements.
:::
:::warning
是否能找到 `offsetof` 的實作，~~參考：https://en.wikipedia.org/wiki/Offsetof~~
> 顯然「第一手材料」就在 Linux 核心原始程式碼，不要翻閱 Wikipedia (裡頭可能存在若干錯誤)。
> :notes: jserv
回覆老師：
我原先是透過 include 找到 `offsetof` 這個巨集在系統中 stddef.h 這個標頭檔中的定義是：
```
#define offsetof(t, d) __builtin_offsetof(t, d)
```
但是並沒有找到關於 `__builtin_offsetof(t, d)` 的實作，在老師提醒後我去翻閱 [GitHub 上 Linux 中專案中於 stddef.h 的原始碼](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h)就有找到實際的定義了，感謝老師的提醒！
:::
```c
#if defined(__GNUC__)
#define __LIST_HAVE_TYPEOF 1
#endif
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
:::warning
格式化問題：在上方的巨集中可發現 (ptr) -offsetof 的 - 與 offsetof 間缺少空格。
以 `clang-format-11` 及 `clang-format-12` 進行測試，若是將 [Clang-format Style Option](https://clang.llvm.org/docs/ClangFormatStyleOptions.html) 中的 **SpaceAfterCStyleCast** 設為 `false` 會發現 `(ptr)` 與 `-offset` 間的空白消失：
> 嘗試用新版的 clang-format，例如 `clang-format-12`，後者已被 Ubuntu Linux 收錄。在 [.ci/check-format.sh](https://github.com/sysprog21/lab0-c/blob/master/.ci/check-format.sh) 中，指定用 `clang-format-12`
> :notes: jserv
```c
#define container_of(ptr, type, member) \
((type *)((char *)(ptr)-offsetof(type, member)))
```
```text
// .clang-format
...
SpaceAfterCStyleCast: false
```
因此推測是 clang-format 將前面的 `(char *) (ptr)` 當成是轉型，而後面的 `-offsetof` 則被判斷成負數，造成減號 `-` 後的空格被移除。
可透過將 `(char *) (ptr)` 加上額外的括號，使排版與預期相符：
```c
#define container_of(ptr, type, member) \
((type *) (((char *) (ptr)) - offsetof(type, member)))
```
```text
// .clang-format
...
SpaceAfterCStyleCast: true
```
:::
`container_of` 是一個透過使用 `offsetof` 來獲取給定的結構體 `type` 中某個 field `member` 的指標 `ptr` 所屬的結構體物件的地址。
主要的計算方式為使用 `offsetof` 獲取 `member` 相對於結構體 `type` 開頭的位元組偏移量，再將 `member` 的指標 `ptr` 中儲存的地址扣除該偏移量以計算出結構體的開頭地址。
然而在 [C 語言標準文件](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)中的 **6.5.6 Additive operators** 有關於加法以及減法運算子的說明，而在該節的第 7 項有說明當對一指向某物件的指標進行加減法時，會和對陣列的首個元素的地址進行加減運算有著相同表現。
> 7. For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
而在其後的第 8 項則有關於對指向陣列元素的指標進行加減運算時會有什麼表現：
> 8. When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression.
綜合第 7 項與第 8 項我們可以知道若是直接對一指標進行加減運算（假設 `ptr + k` ）的話，其效果就猶如陣列索引的移動，而不是對記憶體位置直接加減 `k` 個位元組。
```c
((type *) ((char *) (ptr) - offsetof(type, member)))
```
也因此在 `container_of` 這個巨集的定義中：可以看到它是先將指標的型別轉成 `char *` 使其在進行加減運算時能夠確實的將記憶體位置以**一個位元組**的單位進行計算，以搭配 `offsetof` 的計算結果來得到正確的結構體物件的開頭地址。
:::info
相似的概念有也在[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)中的**回頭看 C 語言規格書**的部份被提及
:::
:::warning
延伸問題：是否能將 `char *` 夠改成 `void *`？
根據規格書中 6.5.6 Addit ive operators 對加法運算部份的描述：
> 2. For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to a complete object type and the other shall have integer type. (Incrementing is equivalent to adding 1.)
可以看到加法運算有兩種情境：
1. 兩運算元皆為算術型態
2. 一運算元為指向 Complete Object Type 的指標，另一運算元整數型別
而在 `container_of` 這個巨集中，很明顯的屬於第二種情境，因此需要檢查的就是 `void *` 是否為一個「指向 Complete Object Type 的指標」。
然而在規格書中的 6.2.5 Types 的部份則說明了型別的類型以及 `void` 是什麼類型的型別：
> 1. The meaning of a value stored in an object or returned by a function is determined by the type of the expression used to access it. (An identifier declared to be an object is the simplest such expression; the type is specified in the declaration of the identifier.) **Types are partitioned into object types (types that describe objects) and function types (types that describe functions). At various points within a translation unit an object type may be incomplete (lacking sufficient information to determine the size of objects of that type) or complete (having sufficient information)**.
在第 1 項就將 type 分成 object type 以及 function type 兩類，而 object type 又可以再分成 complete 與 incomplete 兩種。
> 19. The void type comprises an empty set of values; it is an incomplete object type that cannot be completed.
第 19 項則說明了 `void` 型別是一個 **incomplete object type**。
從綜合以上可以知道 `void` **不是** Complete Object Type，因此 `void *` 也不會是「指向 Complete Object Type 的指標」，所以若是將巨集中的 `char *` 改成 `void *` 的話，該巨集將不屬於加法運算的任一種情境。
:::
```c
const __typeof__(((type *) 0)->member) *__pmember = (ptr);
```
除了計算結構體開頭地址的部份之外，在定義中還使用到了 `__typeof__` 這個 [GNU C Extension](https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html) 中定義的[關鍵字 `typeof`](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 的 [Alternate Keyword](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html)，透過使用這個關鍵字並配合另一個 GNU C Extension [Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html#Statement-Exprs) 使用，這個巨集會先使用結構體 `type` 的 null pointer 來存取目標 field `member` 的類別，然後宣告一個該類別的變數 `__pmember` 並將 `ptr` 中的地址賦值給它，以達到檢查行別的效果。
可以透過簡單的實驗看到這個型別確認會帶來什麼效果：
```shell
$ cat test.c && gcc test.c && echo ">>done<<"
#include <stdio.h>
#include <stddef.h>
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))
typedef struct TEST {
int foo;
struct TEST *bar;
} test;
int main(int argc, char const *argv[])
{
test t = {.foo = 1, .bar = &t};
test *a = container_of(&t.foo, test, bar);
return 0;
}
>>done<<
```
當沒有使用 `typeof` 進行型別檢查時，透過 gcc 可以順利的編譯過，且沒有任何錯誤或是警告。但若是加上 `typeof` 進行型別檢查的話，雖然一樣可以編譯過，但這次就出現了型別警告的訊息了。
```shell
$ cat test.c && gcc test.c && echo ">>done<<"
#include <stddef.h>
#include <stdio.h>
#define container_of(ptr, type, member) \
({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct TEST {
int foo;
struct TEST *bar;
} test;
int main(int argc, char const *argv[])
{
test t = {.foo = 1, .bar = &t};
test *a = container_of(&t.foo, test, bar);
return 0;
}
test.c: In function ‘main’:
test.c:7:61: warning: initialization of ‘struct TEST * const*’ from incompatible pointer type ‘int *’ [-Wincompatible-pointer-types]
7 | const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
| ^
test.c:21:15: note: in expansion of macro ‘container_of’
21 | test *a = container_of(&t.foo, test, bar);
| ^~~~~~~~~~~~
test.c:7:61: note: (near initialization for ‘a’)
7 | const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
| ^
test.c:21:15: note: in expansion of macro ‘container_of’
21 | test *a = container_of(&t.foo, test, bar);
| ^~~~~~~~~~~~
>>done<<
```
<!-- 然而由於 `typeof` 並非標準 C 語言中提供的關鍵字，因此在這個巨集中也使用了 `__GNUC__` 來確保只有在使用 GNU 編譯器時才會使用有 `typeof` 版本的定義，以免造成編 -->
:::warning
TODO :
在上面的巨集定義中使用了 `#ifdef __LIST_HAVE_TYPEOF` 來決定是有要使用 GNU C 的兩個擴充語法，但 `__LIST_HAVE_TYPEOF` 會隨著 `__GNUC__` 的定義被定義，是否有需要在其中使用 `__extension__` 以及 `typeof` 的 Alternate Keywork 來避免編譯器錯誤
-std=c89
參考：
https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html
https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html
:::
### 針對佇列的操作
#### `q_new`
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
// check malloc not return null (implies error or size is 0)
if (head != NULL)
INIT_LIST_HEAD(head);
return head;
}
```
根據 [The GNU C Library](https://www.gnu.org/software/libc/manual/html_node/index.html) 中 3.2.3.1 Basic Memory Allocation 的說明，`malloc` 會在 size 為 0 或是無法分配空間時回傳 null pointer，因此需要在 `malloc` 後檢查 `head` 是否為 `NULL`。
#### `q_size`
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int count = 0;
for (struct list_head *ptr = head->next; ptr != head; ptr = ptr->next)
++count;
return count;
}
```
> 將 `head == NULL` 改為 `!head`，保持程式碼的精簡
> :notes: jserv
#### `q_insert_head` 及 `q_insert_tail`
> 避免濫用 `&`，否則很難區分 operator 和英語的原本意思
> :notes: jserv
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false; // head should not be null
element_t *node = malloc(sizeof(element_t));
if (!node)
return false; // malloc for new node failed
node->value = malloc(strlen(s) + 1);
if (!node->value) {
free(node);
return false; // malloc for string failed
}
// copy string content
memcpy(node->value, s, strlen(s));
node->value[strlen(s)] = '\0';
// insert new node after head
node->list.prev = head;
node->list.next = head->next;
head->next = &node->list;
node->list.next->prev = &node->list;
return true;
}
```
若要加入一個節點 node 到佇列首位的話，需要修改到 4 個連結：
1. head 指向首位節點的連結
2. node 指向前一節點的連結
3. node 指向後一節點的連結
4. 原本首位節點指向前一個節點的連結
而其中要注意的部份是第 4 項的連結，若是一開始就將首位節點 `head->next` 更新的話，後面會沒辦法直接取得原本的首位節點（假設沒另外存起來的話）。
而其實新增節點的操作在 `list.h` 中就有被以函式的形式被實作了，叫做 `list_add`，所以其實 `q_insert_head` 可以再簡化成：
```c
bool q_insert_head(struct list_head *head, char *s)
{
...
// insert new node after head
list_add(&node->list, head);
return true;
}
```
`q_insert_tail` 要做的是跟 `q_insert_head` 相似，只有更新節點間連結的部份不同：
1. head 指向**末**位節點的連結
2. node 指向前一節點的連結
3. node 指向後一節點的連結
4. 原本**末**位節點指向**後**一個節點的連結
而這個操作也有在 `list.h` 中被實作出來，所以可以用 `list_add_tail` 簡單的完成。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
...
// insert new node after head
list_add_tail(&node->list, head);
return true;
}
```
除了使用 `list.h` 中提供的巨集簡化程式碼之外，也使用 `strdup` 來簡化 `malloc`、`memcpy`、`string[size] = '\0'` 的操作：
```c
...
node->value = strdup(s);
if (!node->value) {
free(node);
return false; // malloc for string failed
}
// insert new node after head
list_add(&node->list, head); // or list_add_tail
return true;
```
#### `q_remove_head` 和 `q_remove_tail`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL; // cannot remove a node from NULL or empty list
// get node and unlink (remove) this node from list
element_t *first_entry = list_first_entry(head, element_t, list);
list_del(head->next);
// copy target node's value if need
if (sp) {
strncpy(sp, first_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return first_entry;
}
```
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL; // cannot remove a node from NULL or empty list
// get node and unlink (remove) this node from list
element_t *last_entry = list_last_entry(head, element_t, list);
list_del(head->prev);
// copy target node's value if need
if (sp) {
strncpy(sp, last_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return last_entry;
}
```
`q_remove_head` 跟 `q_remove_tail` 也有類似 `list_add` 的函式可以用，叫做 `list_del`，而這個函式可以用在任一節點上，所以只需要透過 `list_first_entry` 和 `list_last_entry` 兩個巨集拿到頭尾節點後就可以使用 `list_del` 移除連結並釋放資源。
#### `q_delete_mid`
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false; // NULL or empty list
// move to mid node
struct list_head *ptr = head->next;
for (struct list_head *rev = head->prev; rev != ptr && rev != ptr->next;) {
ptr = ptr->next;
rev = rev->prev;
}
// remove this node
list_del(ptr);
// delete entry
element_t *entry = list_entry(ptr, element_t, list);
free(entry->value);
free(entry);
return true;
}
```
用兩個指標 `ptr` 與 `rev` 分別從佇列頭尾而行，直到兩指標交會或是 `rev` 指到 `ptr` 的下一個節點，此時 `ptr` 即為中間點。
#### `q_sort` 和 `mergesort`
在 singly-linked list 中，若要實作一個遞迴版的 mergesort 的話，可以簡單的透過以下程式碼：
```c=
struct list_head *mergesort(struct list_head *start, struct list_head *end)
{
// if only one node, just return
if (start == end)
return start;
// find mid point and split into 2 parts
struct list_head *mid = start, *flag = start;
for (; flag->next && flag->next->next; flag = flag->next->next)
mid = mid->next;
flag = mid->next;
mid->next = NULL;
// do mergesort on both parts
struct list_head *left = mergesort(start, mid);
struct list_head *right = mergesort(flag, end);
// merge 2 sorted list
struct list_head tmp_head, *ptmp = &tmp_head;
for (element_t *l, *r; left && right; ptmp = ptmp->next) {
l = list_entry(left, element_t, list);
r = list_entry(right, element_t, list);
if (strcmp(l->value, r->value) < 0) {
ptmp->next = left;
left = left->next;
} else {
ptmp->next = right;
right = right->next;
}
}
ptmp->next = left ? left : right;
return tmp_head.next;
}
```
雖然這個方式也可以應用在 circular doubly-linked list 中，但很明顯的有以下幾點問題需要解決：
- 頭尾相連
- 擁有 `node->prev`
因此需要對上面的 mergesort 進行一些修補以避免破壞 circular doubly-linked list 的特性：
```c
struct list_head *mergesort(struct list_head *start, struct list_head *end)
{
...
ptmp->next = left ? left : right;
// repair prev links
for (ptmp = tmp_head.next; ptmp->next != NULL; ptmp = ptmp->next)
ptmp->next->prev = ptmp;
return tmp_head.next;
}
```
在原本 singly-linked list 的版本中，在 merge 兩個 sorted linked list 時只需要比對 `left` 以及 `right` 的值，並將較小的節點 append 到 `tmp_head` 即可。但若是對 doubly linked list 進行一樣的操作的話，會造成排序後的節點的 `node->prev` 所指向的節點與預期中的前一個節點不同，因此在 doubly 的版本中，在 merge 完之後需要再依序走訪 `new_head` 並將各節點的 `node->prev` 指向正確的節點。
除了 `node->prev` 需要指向正確的節點之外，還需要注意到 `head` 是一個頭尾相連的 **circular** linked list，而 mergesort 中第 9 列用來尋找中間點的 for 迴圈的結束條件是 `fast->next == NULL` 或 `fast->next->next == NULL`，因此在傳入佇列的首尾節點之前，需要將佇列的尾端節點的 `next` 指向 `NULL`，以免造成無限迴圈。
```c
void q_sort(struct list_head *head)
{
if (head == NULL || head->prev == head->next)
return;
// do merge sort on list
struct list_head *start = head->next, *end = head->prev;
end->next = NULL;
// connect head and sorted list
head->next = mergesort(start, end);
head->next->prev = head;
// repair head.prev
for (; end->next != NULL; end = end->next)
;
end->next = head;
head->prev = end;
}
```
而在 mergesort 結束後，由於 `head->next` 有可能並非實際擁有最小值的節點，因此需要將 `head` 與 mergesort 回傳的 list 重新建立雙向鏈結；相似地，`head->prev` 在 mergesort 前已改指向 `NULL`，因此需要移動到最後一個節點，並將其與 `head` 重新建立雙向鏈結。
#### 簡化 `mergesort`
##### 以指標的指標改寫 merge 部份
```c
...
// merge 2 sorted list
struct list_head *new_head = start, **phead = &new_head;
for (element_t *l, *r; left && right; phead = &(*phead)->next) {
l = list_entry(left, element_t, list);
r = list_entry(right, element_t, list);
struct list_head **next;
next = strcmp(l->value, r->value) < 0 ? &left : &right;
*phead = *next;
*next = (*next)->next;
}
*phead = left ? left : right;
...
```
`**next` 會被 cppcheck 的 style 檢查抱怨 scope 可以縮小，所以需要放在迴圈內，而長度限制則會讓它分成兩行，所以就乾脆讓 `**next` 的宣告與賦值分成兩行了。
##### 排序完再修復 `prev` 連結
```c
void q_sort(struct list_head *head)
{
if (!head || head->prev == head->next)
return;
// do merge sort on list
struct list_head *start = head->next, *end = head->prev;
end->next = NULL;
// connect head and sorted list
head->next = mergesort(start, end);
head->next->prev = head;
// repair all prev links
for (end = head; end->next; end = end->next)
end->next->prev = end;
end->next = head;
head->prev = end;
}
```
在以指標的指標重新實作時發現，其實 `mergesort` 中可以不使用 `prev`，所以可以把最後修復 `prev` 的 `for` 迴圈移除，改在 `q_sort` 最後一次完成，不僅可以讓程式碼更精簡，也能避免在遞迴呼叫時重複修正已修正過的 `prev` 連結。
#### 迭代 mergesort
:::warning
TODO
:::
#### 使用 bitwise OR 替代 `ptmp->next = left ? left : right;` 以減少分支
#### `q_delete_dup`
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL)
return false;
LIST_HEAD(duplist);
element_t *ptr = NULL, *next;
bool found = false;
char *prev = "";
list_for_each_entry_safe (ptr, next, head, list) {
if (strcmp(prev, ptr->value) == 0) {
found = true;
list_move(&ptr->list, &duplist);
}
else {
if (found)
list_move(ptr->list.prev, &duplist);
found = false;
prev = ptr->value;
}
}
list_for_each_entry_safe (ptr, next, &duplist, list) {
free(ptr->value);
free(ptr);
}
return true;
}
```
`q_delete_dup` 的實作概念是額外建立一個佇列 `duplist` 來存放 `head` 中重複的節點。
這個實作想法利用了 `head` 為遞增排序的特性，因此走訪每個節點時只須與前一個節點比較即可，若當前節點與前一個節點擁有相同值的話，就將其移動到 `duplist` 中。
待 `head` 中的所有節點都走訪過之後，再搭配 `container_of` 相關的 macro 來釋放 `duplist` 中的所有節點以及它們的資料。
:::danger
上方的 `q_delete_dup` 實作在 [6edd0f0](https://github.com/sysprog21/lab0-c/commit/6edd0f02d1c659ed58cd35ddd987ccb5cafd7cdd) 的修正後就會被檢查出錯誤，因此需要進行修正。
:::
#### 修正並簡化 `q_delete_dup`
原版是從首位節點開始依序與**前一個節點**進行比較，直到走到最後一個節點為止，然而當最後 2 個（或更多）節點相同時，最後一個節點需要在 `list_for_each_entry_safe` 後進行額外的確認，但又因為 `list_for_each_entry_safe` 的結束條件是 `ptr->list != head`，所以在結束後需要用 `ptr->list.prev` 才能取得最後一個節點，所以我決定直接重寫這部份。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
LIST_HEAD(duplist);
bool prev = false;
element_t *ptr = list_entry(head->next, element_t, list), *next = ptr;
for (bool same; next->list.next != head; ptr = next) {
next = list_entry(ptr->list.next, element_t, list);
same = !strcmp(ptr->value, next->value);
if (same || prev)
list_move(&ptr->list, &duplist);
prev = same;
}
// don't forget last node
if (prev)
list_move(&ptr->list, &duplist);
// delete each element in dup list
list_for_each_entry_safe (ptr, next, &duplist, list) {
free(ptr->value);
free(ptr);
}
return true;
}
```
修正後的版本則是從首位節點開始依序與**後一個節點**進行比較，並將 `list_for_each_entry_safe` 替換成以 `next->list.next != head` 為結束條件的 `for` 迴圈，讓 `ptr` 在結束迴圈時的狀態是指向最後一個節點，以便檢查是否需要將最後一個節點也移入 `duplist` 中。此外，也透過新增一個布林變數來簡化迴圈內所需的操作。
## 理解 [Linux 核心中的排序實作](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### 圖解 list_sort 的 `do while` 部份
:::warning
在第一次看這段程式碼的時候，想了很久都不知道在幹麻，因此只好直接畫出來一步步觀察它的規律以及奧妙，並參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-list_sort-%E5%AF%A6%E4%BD%9C) 和 [blueskyson](https://hackmd.io/@blueskyson/linux2022-lab0#%E8%B5%B0%E8%A8%AA%E6%95%B4%E5%80%8B-list-%E5%90%8C%E6%99%82%E5%9F%B7%E8%A1%8C-merge-sort) 以及 [kdnvt](https://hackmd.io/@5ux520T8Sd-OoYfdxZR55Q/SyzDKJ9y9#%E7%A0%94%E8%AE%80-liblist_sortc) 的開發紀錄來輔助理解這部份到底在做什麼。
:::
#### `do while` 部份程式碼
```c=
do {
size_t bits;
struct list_head **tail = &pending;
// part 1, shift all trailing 1s
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
// part 2, merge sorted pending
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
a->prev = b->prev;
*tail = a;
}
// part3, add node to pending
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
首先，為了方便後面說明，將 `do while` 中的程式碼分成三個 part。
#### 每個 count 的操作
:::warning
由於還不太熟悉 graphviz 的語法導致畫不出看起來整齊的圖，因此這邊使用 drawio 自己畫、自己移動指標觀察規律。而為了簡化圖示，沒有箭頭的格子就代表指向 `NULL`。
:::
- `0b0000`
- 初始化後 `pending` 會是空的，而 `list` 則指向當前未排序串列的首位節點 (後面統一稱作 `first` )。
- 而進入 `do while` 的部份後，則因為 `count` 以及 `bits` 都為 0，因此只會進行新增節點到 `pending` 串列的步驟 (**part3**)。
- 而在 **part3** 結束後 `pending` 將會指向 `first`，而 `list` 將會移動到 `first` 的下一個節點 (後面統一稱作 `second`)。
- `0b0001`
- 接著進入到 `count == 0b0001`，由於尾端有 `1`，所以會先進行右移檢查的部份 (**part1**)。而由於只有最後一位元是 `1`，因此 tail 會往前走一次，最後指向節點 5 `prev`，但因為右移結束後不會進入到 `if` 區塊，因此這段其實不會被用到。
- 再來會進行 **part3** 的操作，將 `first` 加入到 `pending` 中，並在停在 `pending` 指向 `first (4)`、`list` 指向 `second (3)` 的狀態。
:::warning
到這邊為止有幾個需要注意的地方：
- 將 `first` 新增到 `pending` 後，`first` 的 `next` 會被指向 `NULL`，也就是說節點被加到 `pending` 串列後就不能以 `next` 依序拜訪。
- 雖然加入 `pending` 後 `next` 連結都會被指向 `NULL`，但是在加入前一輪時其實已經有將 `list->next` 指向 `pending`，而 `list` 其實就是下一輪的 `first`，也就是說其實可以用 `prev` 依序拜訪 `pending` 中的串列。
:::
- `0b0010`
- 再來是 `count == 0b0010` 的情況，由於最低位元不是 `1`，因此不用做 **part1**，但因為 `bits != 1` 因此要先進行合併 `pending` 中節點 (**part2**) 的操作。
- 合併前 `a` 會先移動到當前 `tail` **指向的指標所指向的節點**（圖中的節點 `4` ），而 `b` 則會指向 `a` 的前一個節點 (圖中的節點 `5`)。
- 合併後 4 的 `next` 會指向 5 ，而 `a` 則會指向排序後串列的首位節點（在此次合併中為 4），並需要將 `a->prev` 指向 `b->prev`（在此次合併中為 `NULL`）以及將 `tail` **指向的指標**指向 `a`。
- 而合併後則需要再進行 **part3** 的操作，最後 `pending` 會指向 `first (2)`，而 `list` 則會指向 `second (3)`。
- `0b0011`
- 而當 `count == 0b0011` 時，首先會先進行 **part1** 移除尾端的連續 1、將 `tail` 指向 4 的 `prev`，但因為 `bits` 為 0，所以其實沒有作用。
- 然後是 **part3** 的新增節點以及移動指標的操作。最終 `pending` 會指向 `first (3)`，而 `list` 則會指向 `7`。
:::warning
進行到這邊，除了單純位移以及新增節點到 `pending` 串列中之外，還進行了合併 (**part2**) 的操作，有幾個細節可以注意：
- 如同合併函式的註解說明，將兩個排序好的串列 `a`、`b` 進行合併時只會將 `next` 連結指向正確的節點，`prev` 則不會被改變。而合併結束後就用了這個特性，讓新的已排序串列的首位節點的 `prev` 指向串列 `b` 的 `prev` 所指向的節點。
- 在前面的注意事項有說到 `pending` 中的節點是以 `prev` 作為連結互相連結，而 `next` 雖然在剛被加入 `pending` 時會被指向 `NULL`，但是在合併時 `next` 會被正確的連接、形成正確排序的串列。
- 雖然在合併前 `a`、`b` 節點可以被正確的透過 `prev` 依序走訪，但是在合併後，不論合併後的已排序串列的首位節點是 `a` 還是 `b`，最後能夠透過 `pending` 以及 `prev` 連結指標走訪的節點只有排序後串列的首位節點而已（第 14、15 行在做的事）。
:::
- `0b0100`
- 在 `count == 0b0100` 時，由於尾端沒有連續的 1，因此不須進行位移以及移動 `tail` 的 **part1**。但由於 `bits != 0`，因此需要進行 **part2** 的合併。
- 首先要先決定要合併的兩個串列，由於 **part1** 沒有做，因此一已排序串列 `a` 會指向 3，而另一已排序串列 `b` 則會指向 2。
- 而這兩個已排序串列合併後新的首位節點 2 將會變成變成新的 `a`，其 `prev` 連結則會指向原本 `b->prev` 指向的 4（由於首位節點沒變，因此指向的節點也沒變），且 `tail` 指向的 `pending` 指標則會改指向合併後的首位節點 `a`。
- 最後則是 **part3** 的新增節點以及移動指標。操作完成後 `pending` 將會指向 `first (7)`，而 `list` 則會指向 `second (6)`。
:::warning
到這邊為止則是又重複了一次 `count == 0b0010` 的操作，只是這次是兩個不一樣的節點。
:::
- `0b0101`
- 當 `count == 0b0101` 時，會先進行 **part1** 將 `tail` 指向 7 的 `prev`，接著再進行 **part2** 的合併。
- 由於 `part1` 有進行，因此 `a` 為 7 的 `prev` 所指向的節點，也就是 2，而 `b` 則為它的前一個節點 4。而合併後會產生一個新的已排序串列，此時將 `a` 更新成該串列的首位節點 `2`，並且將 `a->prev` 更新、 `tail` 指向的指標指向 2。
- 最後再將 `first (6)` 新增到 `pending` 中，並將 `list` 指向 `NULL`，而由於 `list` 指向 `NULL` 因此 `do while` 的部份就結束了。
:::danger
到這邊為止，大概可以抓到一個規律是：當合併( **part2** )發生時，`*tail` 會指向最接近 `pending` 開頭的兩個大小皆為 $2^k$ 的子串列，並進行合併。
但：
1. 為什麼合併時總會剛好有一對相同大小的子串列能夠進行合併？
2. 為什麼 `part1` 還能夠剛好將 `*tail` 移動到到最近一對相同大小的子串列？
還在思考是否能以二進制的規律理解
// TODO :
The cost distribution of queue-mergesort, optimal mergesorts, and
power-of-two rules
Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen
Journal of Algorithms 30(2); Pages 423--448, February 1999
https://doi.org/10.1006/jagm.1998.0986
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380
:::
#### 合併的規律
| count | 合併前 (上輪結果) | 本輪動作 (位置) |
| ------ |:----------------- |:--------------- |
| 0b0000 | [] | add |
| 0b0001 | [1] | add |
| 0b0010 | [1,1] | merge(0), add |
| 0b0011 | [1,2] | add |
| 0b0100 | [1,1,2] | merge(0), add |
| 0b0101 | [1,2,2] | merge(1), add |
| 0b0110 | [1,1,4] | merge(0), add |
| 0b0111 | [1,2,4] | add |
| 0b1000 | [1,1,2,4] | merge(0), add |
| 0b1001 | [1,2,2,4] | merge(1), add |
| 0b1010 | [1,1,4,4] | merge(0), add |
| 0b1011 | [1,2,4,4] | merge(2), add |
| 0b1100 | [1,1,2,8] | merge(0), add |
| 0b1101 | [1,2,2,8] | merge(1), add |
| 0b1110 | [1,1,4,8] | merge(0), add |
| 0b1111 | [1,2,4,8] | add |
表格中間 column 的陣列代表該該輪合併前 pending 串列的狀態，每個元素都代表一個「已排序」的串列（如前面圖中著有相同顏色的節點），該元素的數值則代表該串列的長度，而陣列最左側的元素就是當下 `pending` 指標指向的串列。
### `merge_final` 部份
而當 `list` 指向 `NULL` 時，代表所有節點都走訪過了，且全部的節點都在 pending 串列中因此最後還需要依序兩兩合併所有 pending 中的已排序串列：
```c=25
...
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
}
```
而要合併 `pending` 中的子串列可以用類似 **iterative merge k sorted list** 的方式，依序從 pending 開頭合併到剩下最後兩個子串列。
:::warning
為什麼剩最後兩個子串列時就停了？
到目前為止的合併過程都只有保證 `next` 連結會指向正確的節點，而 `prev` 連結則是用來指向下一個 `pending` 中的子串列（僅各個子串列的首位節點的 `prev` 能用來走訪 `pending` 串列，其他合併後非首位的節點的 `prev` 則不應該被使用），因此需要趁最後合併時將 `prev` 復原、指向正確的節點。
:::
```c
static void merge_final(void *priv,
list_cmp_func_t cmp,
struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *tail = head;
uint8_t count = 0;
// part1, merge 2 sorted non-null list
for (;;) {
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
// part2, link remain nodes
tail->next = b;
do {
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
// make circular
tail->next = head;
head->prev = tail;
}
```
最後的合併大致上與 merge 要做的事相同，首先是 **part1** 的部份，依序比較兩串列的首位節點，並將較小的節點加到雙向串列的尾端 (`tail`)，直到其中一個串列為空。
當 `part1` 完成後，不像是單向鏈結串列可以直接將剩餘的接在後面，由於有 `prev` 連結需要處理，所以要依序將剩餘的節點加入到尾端並恢復 `prev` 連結。
:::warning
問題一：
為什麼要在 **part2** 中加上 `if (unlikely(!++count)) cmp(priv, b, b);`？
首先可以先來看原本的註解寫了什麼：
```c
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
```
從這說明可以知道這是為了兩個子串列非常不平衡時設計的一個分支，每當新增一個節點時就會 `++count`，看起來沒什麼意義，但回去看 `count` 宣告時的型別會發現它是 `uint8_t`（原始程式碼中是另外[使用 typedef 將 `u8` 定義成 `u_int8_t`](https://github.com/torvalds/linux/blob/master/include/linux/types.h)，這邊為了方便解釋直接替換成 `uint8_t`），所以若是剩餘的節點非常多的時候會因為 overflow 而從頭開始計算，而在 overflow 時就會呼叫 `cmp` 函數，因此可以達成定期呼叫 `cmp` 函式的效果。
:::
:::warning
問題二：
為什麼需要定期呼叫 `cmp`？
裡面提到的 `cond_resched` 是什麼？
// TODO
:::
### `likely` 與 `unlikely` 巨集
這兩個巨集被定義在 [include/linux/compile.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中。
[相關 extension](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
:::warning
TODO
:::
### 其他相關論文
Bottom-up Mergesort: A Detailed Analysis
Wolfgang Panny, Helmut Prodinger
Algorithmica 14(4):340--354, October 1995
https://doi.org/10.1007/BF01294131
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260
Queue-Mergesort
Mordecai J. Golin, Robert Sedgewick
Information Processing Letters, 48(5):253--259, 10 December 1993
https://doi.org/10.1016/0020-0190(93)90088-q
https://sci-hub.tw/10.1016/0020-0190(93)90088-Q
## 使用 Valgrind 對 qtest 進行分析
### 問題 - 1 `atexit`
#### 尋找問題
原本想直接對 make test 的過程使用 Valgrind 檢查，但是發現自動測試程式是用 python 進行的，所以只好使用 Valgrind 分別檢查各個測資。
若以 Valgrind 執行 `qtest` 並以 `trace-01-ops.cmd` 作為輸入測資的話：
```shell
$ make && valgrind ./qtest < traces/trace-01-ops.cmd
CC qtest.o
LD qtest
Freeing queue
==3555496== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==3555496== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496== by 0x4A5A14E: strdup (strdup.c:42)
==3555496== by 0x110BF8: linenoiseHistoryAdd (linenoise.c:1236)
==3555496== by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496== by 0x10CAAB: main (qtest.c:1101)
==3555496==
==3555496== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==3555496== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496== by 0x110BB8: linenoiseHistoryAdd (linenoise.c:1224)
==3555496== by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496== by 0x10CAAB: main (qtest.c:1101)
==3555496==
==3555496== 199 bytes in 19 blocks are still reachable in loss record 3 of 3
==3555496== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496== by 0x4A5A14E: strdup (strdup.c:42)
==3555496== by 0x110B6C: linenoiseHistoryAdd (linenoise.c:1236)
==3555496== by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496== by 0x10CAAB: main (qtest.c:1101)
==3555496==
```
可以從上方執行紀錄看到有在 `linenoiseHistory` 時使用到的 `malloc` 與 `strdup` 分配到的空間沒被釋放。
```c=1222
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
```
而實際到該函式檢查則會發現這個函式是在在新增紀錄到 `history` 這個 `char **` 的全域變數中（字串的陣列），而出問題的 1224 行是在分配空間給 `history`、1236 則是在分配空間給要新增的命令歷史紀錄，而它後來又存到 `history` 的某個欄位中。到這邊為止可以發現這兩個問題都是跟 `history` 相關，所以依次檢查 `history` 是否有哪邊處理的不完善。
依序檢查了 `linenoise.c` 中使用到 `history` 的部份似乎都沒什麼問題，所以參考了 [laneser](https://hackmd.io/@laneser/linux2022_lab0#%E9%81%8B%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) 以及 [Risheng](https://hackmd.io/@Risheng/linux2022-lab0#%E9%81%8B%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) 兩位的開發紀錄，並在其中看到似乎是在以檔案形式輸入測資時，沒有正確呼叫 `freeHistory` 造成的錯誤，因此改從 `freeHistory` 開始回推發生錯誤的原因。
而從 `freeHistory` 往回推會發現該函式只會被 `linenoiseAtExit` 呼叫，而 `linenoiseAtExit` 則是由 `atexit` 這個函式呼叫，而根據 [atexit 的 man page](https://www.man7.org/linux/man-pages/man3/atexit.3.html) 中的說明可以知道這個函式會在程式**正常結束**時呼叫設定的函式 `function`，也就是說 `linenoiseAtExit` 這個函式只有在 `qtest` 結束時才會被呼叫。
```c
#include <stdlib.h>
int atexit(void (*function)(void));
```
知道了可能的問題後，接著對 `linenoiseAtExit` 函式設定中斷點看看會發生什麼事：
1. 不使用測資、直接執行 `qtest` 時，程式會在結束後（輸入 `quit`）進入到 `linenoiseAtExit` 函式，無 memory leak 相關錯誤。
2. 使用 `<` 將測資[重新導向](https://www.vbird.org/linux_basic_train/centos8/unit08.php#8.2)至 `qtest` 執行時，程式結束後**不會**進入 `linenoiseAtExit` 函式，**會出現** memory leak 相關錯誤。
3. 使用 `-f` 指定測資執行 `qtest` 時，程式結束後**不會**進入 `linenoiseAtExit` 函式，**會出現** memory leak 相關錯誤。
可以發現與參考的兩位同學開發紀錄中提到的情況相同，而接下來為了找出是什麼原因造成這個差異，所以使用 GDB 逐步執行並比較不同的輸入方式會發現：
1. 直接執行並手動輸入測資時，會經由 `linenoise` 進入到 `linenoiseRaw` 函式
3. 若是用重新導向來輸入測資時，會經由 `linenoise` 進入到 `linenoiseNoTTY` 函式
4. 若是用 `-f` 參數指定測資檔案，則會直接進入到 `cmd_select` 函式，而不會進入到 `linenoise` 函式
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
綜合執行結果以及進入的函式差異，可以推測問題可能出在 `linenoiseRaw` 這個函式中，而 `linenoiseRaw` 中又呼叫了 `enableRawMode` 函式，下方為該函式的其中一部份，可以看到在第 8 行出現了前面提到的 `atexit` 以及 `linenoiseAtExit`，且 `atexit` 並沒有在其他地方被呼叫，因此合理推測這就是問題所在。
```c=
static int enableRawMode(int fd)
{
struct termios raw;
if (!isatty(STDIN_FILENO))
goto fatal;
if (!atexit_registered) {
atexit(linenoiseAtExit);
atexit_registered = 1;
}
if (tcgetattr(fd, &orig_termios) == -1)
goto fatal;
...
```
#### 嘗試解決問題
推測出問題所在後開始嘗試修改程式碼來解決這個問題：
為了讓三種輸入方式都能夠呼叫到 `atexit(linenoiseAtExit)`，我在 `linenoise.h` 以及 `linenoise.c` 中新增了一函式 `setAtExit`，並將 `atexit` 相關的部份移到該函式內：
```c
void setAtExit(void)
{
if (!atexit_registered) {
atexit(linenoiseAtExit);
atexit_registered = 1;
}
}
```
並在三種輸入方法都有呼叫到的 `run_console` 中呼叫此函數來設定在 `qtest` 結束後需要呼叫 `linenoiseAtExit` 來釋放資源。
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
setAtExit();
...
}
```
而重新編譯並用 valgrind 測試 `trace-01-ops.cmd` 後，可以看到不論是用 `-f` 指定測資、還是透過重新導向輸入測資，錯誤訊息就如預期的消失了：
```shell
$ make && valgrind ./qtest -f traces/trace-01-ops.cmd
make: 對「all」無需做任何事。
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbil]
cmd> ih bear
l = [bear gerbil]
cmd> ih dolphin
l = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil]
cmd> rh bear
Removed bear from queue
l = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
l = []
cmd>
Freeing queue
```
```shell
$ make && valgrind ./qtest < traces/trace-01-ops.cmd
make: 對「all」無需做任何事。
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
```
### 問題 - 2 `test_malloc`
#### 尋找問題
在解決 `atexit` 的問題後，繼續以 Valgrind 對其他測資進行測試，發現在執行 `trace-14-perf.cmd` 這個測資時會跳出大約 300 行的錯誤訊息，查看了測資後發現是在測 `reverse` 以及 `sort` 兩函式的效率，而這兩個操作的測試函式 `do_reverse` 及 `do_sort` 中有使用 `alarm` 來中斷執行過久的函式。
若將 `harness.c` 中的 `time_limit` 調高到 `99999` 的話，會發現操作都能順利完成， Valgrind 也不會跳錯誤訊息，所以初步推測問題是出在 singal 相關操作的部份。
而為了簡化問題，先將 `trace-14-perf.cmd` 中的 `sort` 操作移除：
```plain
# Test performance of insert_tail, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
```
接著再重新以 Valgrind 檢查問題：
```shell
$ make && valgrind ./qtest < traces/trace-14-perf.cmd
make: 對「all」無需做任何事。
l = []
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 20741 blocks are still allocated
==1199500== 48 bytes in 1 blocks are possibly lost in loss record 1 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10E8D3: test_strdup (harness.c:217)
==1199500== by 0x10EB23: q_insert_head (queue.c:67)
==1199500== by 0x10C322: do_ih (qtest.c:201)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
==1199500== 56 bytes in 1 blocks are still reachable in loss record 2 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10EA83: q_new (queue.c:22)
==1199500== by 0x10C46A: do_new (qtest.c:128)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
==1199500== 64 bytes in 1 blocks are definitely lost in loss record 3 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10EB0E: q_insert_head (queue.c:62)
==1199500== by 0x10C322: do_ih (qtest.c:201)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
==1199500== 64 bytes in 1 blocks are definitely lost in loss record 4 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10EB7F: q_insert_tail (queue.c:92)
==1199500== by 0x10C01D: do_it (qtest.c:290)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
==1199500== 497,712 bytes in 10,369 blocks are still reachable in loss record 5 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10E8D3: test_strdup (harness.c:217)
==1199500== by 0x10EB23: q_insert_head (queue.c:67)
==1199500== by 0x10C322: do_ih (qtest.c:201)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
==1199500== 663,680 bytes in 10,370 blocks are still reachable in loss record 6 of 6
==1199500== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500== by 0x10E65B: test_malloc (harness.c:138)
==1199500== by 0x10EB0E: q_insert_head (queue.c:62)
==1199500== by 0x10C322: do_ih (qtest.c:201)
==1199500== by 0x10D5AE: interpret_cmda (console.c:185)
==1199500== by 0x10DAE6: interpret_cmd (console.c:208)
==1199500== by 0x10E593: run_console (console.c:651)
==1199500== by 0x10CAD0: main (qtest.c:1117)
==1199500==
```
可以從這些錯誤訊息發現，這些沒被釋放的記憶體空間都是從 `harness.c` 中的 `test_malloc` 這個函式中產生的，而根據[作業說明](https://hackmd.io/dPYu4WH8TuqXnAJvfxm-JA?view#%E8%BF%BD%E8%B9%A4%E8%A8%98%E6%86%B6%E9%AB%94%E9%85%8D%E7%BD%AE%E5%92%8C%E9%87%8B%E6%94%BE%E7%9A%84%E7%8B%80%E6%B3%81)以及查看 `harness.c` 中的程式碼，會知道這個函式是用來包裝 `malloc` 並紀錄已分配的記憶體，來檢查 `q_free` 等功能是否有正確被實作。
而在 `qtest` 的錯誤訊息中可以看到在 Freeing queue 時，由於超出 `alarm` 設定的時間，因此有部份應該被釋放的記憶體空間尚未被釋放：
```shell
Freeing queue
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 20741 blocks are still allocated
```
若在程式碼中尋找 **Freeing queue** 這個訊息的話，會發現這個訊息是當 `qtest` 收到 `quit` 命令後的提示訊息，而在印出訊息後就會進行 `q_free`：
```c
static bool queue_quit(int argc, char *argv[])
{
report(3, "Freeing queue");
if (lcnt > big_list_size)
set_cautious_mode(false);
if (exception_setup(true))
q_free(l_meta.l);
exception_cancel();
set_cautious_mode(true);
size_t bcnt = allocation_check();
if (bcnt > 0) {
report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
bcnt);
return false;
}
return true;
}
```
因此這邊猜測是 `q_free` 進行到一半時就因 `alarm` 的設定而產生 `SIGALRM` ，而在 `queue_init` 中又有透過 `signal(SIGALRM, sigalrmhandler);` 設定當 `SIGALRM` 發生時要進行的處理（使用 `siglongjmp` 跳到 `exception_setup` 進行後續處理），造成 `q_free` 沒辦法釋放所有 `allocated` 串列中紀錄的記憶體空間。
#### 嘗試解決
從上面的過程可以推測出問題出在 `q_free` 沒辦法釋放 `allocated` 這個鏈結串列中紀錄的記憶體空間，因此這邊嘗試為檢查是否有空間尚未被釋放的函式 `allocation_check` 新增一個參數來決定是否要在檢查後釋放所有空間：
```c
size_t allocation_check(bool do_release)
{
size_t remain = allocated_count;
if (do_release) {
for (block_ele_t *ptr = allocated, *next; ptr; ptr = next) {
next = ptr->next;
free(ptr);
}
allocated_count = 0;
}
return remain;
}
```
並且為 `qtest` 中使用到此函式的部份進行修改（傳送參數 `true` ），接著再重新以 valgrind 測試在超時後是否仍有記憶體沒被釋放：
```shell
$ make && valgrind ./qtest < traces/trace-14-perf.cmd
CC qtest.o
CC harness.o
CC queue.o
LD qtest
l = []
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 68081 blocks are still allocated
```
可以看到這次雖然仍然因為超時而中斷 `q_free` 的操作，並且有 68081 個 blocks 偵測出沒被正確釋放，但是後面卻沒出現 Valgrind 的錯誤訊息了，這與上述修改的預期結果相符。
:::danger
若是多執行幾次會發現，其實這個問題沒有完全解決，Valgrind 仍**有機會**跳出錯誤訊息：
```c
$ make && valgrind ./qtest < traces/trace-14-perf.cmd
make: 對「all」無需做任何事。
l = []
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 106095 blocks are still allocated
==1670281== 48 bytes in 1 blocks are definitely lost in loss record 1 of 1
==1670281== at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1670281== by 0x10E65B: test_malloc (harness.c:138)
==1670281== by 0x10E8D3: test_strdup (harness.c:217)
==1670281== by 0x10EB3B: q_insert_head (queue.c:67)
==1670281== by 0x10C322: do_ih (qtest.c:201)
==1670281== by 0x10D5AE: interpret_cmda (console.c:185)
==1670281== by 0x10DAE6: interpret_cmd (console.c:208)
==1670281== by 0x10E593: run_console (console.c:651)
==1670281== by 0x10CAD0: main (qtest.c:1117)
==1670281==
```
可以看到這個錯誤仍發生在 `test_malloc` 中，但這次卻只有一個 block 沒被釋放，且這個記憶體位址是 **definitely lost in loss record**。
若是回到 `test_malloc` 中會發現函式中其實只是呼叫 `malloc` 後再紀錄到 `allocated` 這個串列中而已，因此初步推測是在 `malloc` 後，但是在新增到 `allocated` 之前發生了 `SIGALRM`，所以即使在 `allocation_check` 時手動釋放了 `allocated` 中的紀錄，也會因為這個 block 根本沒被紀錄而造成 memory leak 的發生。
初步解法：
若是有辦法暫時暫停 `alarm` 的計時器的話，或許能夠讓所有 `test_malloc` 中 `malloc` 的空間能夠被正確加入到 `allocated` 串列中，以確保後它能夠在後去操作被正確釋放。
:::
### 問題 - 3
#### 尋找問題
#### 嘗試解決
## 為 qtest 新增 shuffle 功能
### 新增命令
可以在 `console_init` 中透過 `ADD_COMMAND` 或是 `add_cmd` 新增測試時的命令，兩者的差異在於前者是透過巨集的 [Stringizing](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html) 以及 [Concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html) 來簡化呼叫 `add_cmd` 要傳遞的參數，而 `ADD_COMMAND` 則會根據參數來設定命令的名稱以及執行命令時要呼叫的對應函式。
### Signal
### 實作 shuffle 命令
```c
static bool do_shuffle(int argc, char *argv[])
{
// check queue length
if (!l_meta.l)
report(3, "Warning: Calling shuffle on null queue");
else if (q_size(l_meta.l) == 0)
report(3, "Warning: Calling shuffle on empty queue");
error_check();
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
show_queue(3);
return !error_check();
}
```
當 `shuffle` 命令被執行時，會先呼叫此函式，而這個函式參考了 `do_sort` 加入了佇列的檢查以及設定例外，接著才會呼叫 `q_shuffle` 函式。
:::warning
TODO : check argc
:::
```c
void q_shuffle(struct list_head *head)
{
// check queue length
int len = q_size(head);
if (len <= 1)
return; // NULL, empty, only 1 node
// do shuffle
for (struct list_head *ptr = head->prev; --len; ptr = ptr->prev) {
// pick random node and put at node[len]
int target = rand() % (len + 1);
// swap if target != len
if (target != len) {
// move to target node
struct list_head *node = head->next;
for (int i = 0; i < target; ++i)
node = node->next;
// swap node data
element_t *ptr_entry = container_of(ptr, element_t, list);
element_t *node_entry = container_of(node, element_t, list);
char *tmp = ptr_entry->value;
ptr_entry->value = node_entry->value;
node_entry->value = tmp;
}
}
}
```
而在 `shuffle` 函式則是參考了 [Fisher–Yates shuffle 的 modern method](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method) 進行實作。
## 為 qtest 新增 web 功能
### 實作 web 命令
Sign in with Wallet
Connect another wallet