# 2022q1 Homework1 (lab0)
contributed by < `mm0809` >
## 實驗環境
==~~目前暫時使用虛擬機器~~==
:::spoiler 虛擬機配置(舊)
> TODO: 描述 hypervisor 及其配置
> :notes: jserv
> VMware Workstation 16 Player
> OS: ubuntu~20.04
> RAM: 4GB
> Number of processor cores: 2
>
> Host computer:
> OS: windows10
> CPU: i5-8400H
> RAM: 16GB
```shell
$gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Byte Order: Little Endian
Address sizes: 45 bits physical, 48 bits virtual
CPU(s): 2
On-line CPU(s) list: 0,1
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 2
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Stepping: 10
CPU MHz: 2304.004
BogoMIPS: 4608.00
Hypervisor vendor: VMware
Virtualization type: full
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 16 MiB
NUMA node0 CPU(s): 0,1
```
:::
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz
Stepping: 3
CPU MHz: 841.179
CPU max MHz: 3400.0000
CPU min MHz: 800.0000
BogoMIPS: 6385.34
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT disabled
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT disabled
Vulnerability Meltdown: Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP disabled, RSB filling
Vulnerability Srbds: Mitigation; Microcode
Vulnerability Tsx async abort: Not affected
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm consta
nt_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr
pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault invpcid_single pti ssbd ibrs ibpb stibp tp
r_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
```
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [x] 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [ ] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [x] 在提交程式變更前，務必詳閱 [如何寫好 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/)
- [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
- [ ] 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
## queue 實作結果與過程
### q_new
> Create empty queue.
> Return NULL if could not allocate space.
```c
struct list_head *q_new()
{
struct list_head *queue = malloc(sizeof(struct list_head));
if (queue != NULL)
INIT_LIST_HEAD(queue);
return queue;
}
```
* C99 7.20.3 **Memory management functions**
> If the space cannot be allocated, a null pointer is returned.
從規格書可知， `malloc` 是有可能回傳 NULL 的。 Linux 核心原始程式碼提供的 `INIT_LIST_HEAD` 並沒有考慮到輸入為 NULL 的情況，因此在初始化佇列時，必續先做判斷。
> Linux 核心原始程式碼提供的 API 繼承了 C 語言的精神，他假定使用者知道自己在幹嘛，不會做出不符合預期的操作。這個重點在接下來的題目都會一直出現。
題目要求 **Return NULL if could not allocate space** 恰好與規格書中 malloc 的行為一樣，因此針對這一點我們無須做額外的判斷。
### q_free
> Free all storage used by queue
```c
void q_free(struct list_head *l)
{
if (!l)
return;
// iterate over the list entries and remove it
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
雖然我們在操作 list 時都只在意 `list_head` 這個結構體，但事實上它只是 `element_t` 的成員之一，因次在做 `q_free` 我們要 free 的是後者而不是前者。
Linux 核心原始程式碼提供很多種方法做 traversal ，我們必須根據需求慎選。根據題意我們需要 free 每個 `element_t` 也就是每個 `entry` ，這意味著會修改到 list ，所以我選擇使用 `list_for_each_entry_safe` 。
### q_insert_head
> Attempt to insert element at head of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
// allocate memory for element_t
element_t *new_entry = malloc(sizeof(element_t));
if (!new_entry)
return false;
size_t len = strlen(s) + 1;
// allocate memory for 'value' in element_t
new_entry->value = malloc(len);
if (!(new_entry->value)) {
free(new_entry);
return false;
}
memcpy(new_entry->value, s, len);
list_add(&new_entry->list, head);
return true;
}
```
這題我們必須先透過 `strlen(s)` 取得 s 的長度，然後使用 `malloc` allocate 出等長的空間，最後把 s 的資料複製到新的 entry 裡面。最後在把新的 node 插在 list 的對前端。
接下來讓我們看看 C99 規格書中有關 string length 的敘述：
* C99 7.1.1 **Definitions of terms**
> The length of a string is the number of bytes preceding the null character
* C99 7.21.6.3 **The strlen function**
>The strlen function computes the length of the string pointed to by s
> The strlen function returns the number of characters that precede the terminating nullcharacter.
由以上敘述可知包括 null character ，我們需要 `strlen(s) + 1` bytes 的空間。我們在取得 `strlen(s)` 可以把它存起來，因為後面還會再用到一次，如果不先存起來，那就必須需得在執行一次時間複雜度為 O(n) 的操作。
在把 `s` 的資料複製到 `new_entry` 的階段有兩個選擇使用 `memcpy` 或 `strncpy`。
* C99 7.21.2.4 **The strncpy function**
> The strncpy function copies not more than n characters (characters that followanull 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.
根據 C99 規格書我們可以推敲到 `strncpy` 的實作需要一直確認是否遇到 null character ， `memcpy` 則不需要一直做確認，再加上我們在這個階段的複製是在**已知資料長度**的狀況下進行，因此在這裡我選擇使用 `memcpy`。
::: info
目前我在虛擬機上測試出來的結果是 `memcpy` 確實會比 `strncpy` 效率還要好。等正式安裝系統後再做一次嚴謹的測試。
:::
最後呼叫 `list_add` 把新的 node 加入到 list 中。在[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 有提到，我們可以把 head 用 pointer to pointer 的形式傳入 function 這樣可以直接更改 head 不用再以 return 的方式去更新。 在 `lsit_add` 很顯然並沒有使用這種方法，這裡的 list 是使用 [dummy head](https://stackoverflow.com/questions/37324972/what-is-a-dummy-head) 這個技巧。除了可以避免前面所述更新 head 的問題外，還可以避免掉一些需要額外判斷的特殊條件。
### q_insert_tail
> Attempt to insert element at tail of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
// allocate memory for element_t
element_t *new_entry = malloc(sizeof(element_t));
if (!new_entry)
return false;
size_t len = strlen(s) + 1;
// allocate memory for 'value' in element_t
new_entry->value = malloc(len);
if (!(new_entry->value)) {
free(new_entry);
return false;
}
memcpy(new_entry->value, s, len);
list_add_tail(&new_entry->list, head);
return true;
}
```
`q_insert_tail` 和 `q_insert_heaed` 幾乎一樣，唯一的不同是 `list_add` 被替換為 `lsit_add_tail` 。
### q_remove_head
> Attempt to remove element from head of queue.
Return target element.
Return NULL if queue is NULL or empty.
If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
NOTE: "remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
if (sp) {
element_t *entry = list_first_entry(head, element_t, list);
size_t len = strlen(entry->value);
len = (bufsize - 1) > len ? len : (bufsize - 1);
memcpy(sp, entry->value, len);
sp[len] = '\0';
list_del(&entry->list);
return entry;
}
return NULL;
}
```
先透過 `list_first_entry` 取得第一個 entry 的地址。
因為不確定目標的字串長度是否有大於 `bufsize` 因此中間必須判斷哪個長度比較小後再進行資料的複製。
### q_remove_tail
> Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
if (sp) {
element_t *entry = list_last_entry(head, element_t, list);
size_t len = strlen(entry->value);
len = (bufsize - 1) > len ? len : (bufsize - 1);
memcpy(sp, entry->value, len);
sp[len] = '\0';
list_del(&entry->list);
return entry;
}
return NULL;
}
```
除了一開始用 `list_last_entry` 不同以外，其餘均與 `q_remove_head` 相同。
### q_release_element
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
`q_release_element` 中必須要注意我們除了要 deallocate element_t 以外，其成員 value 也要 deallocate 。
### q_size
> Return number of elements in queue.
Return 0 if q is NULL or empty
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *trv;
list_for_each (trv, head)
len++;
return len;
}
```
參考 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 解說
### q_delete_mid
> Delete the middle node in list.
The middle node of a linked list of size n is the
⌊n / 2⌋th node from the start using 0-based indexing.
If there're six element, the third member should be return.
Return true if successful.
Return false if list is NULL or empty.
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow, *fast;
for (slow = head->next, fast = slow->next;
fast != head && fast != head->prev;
slow = slow->next, fast = fast->next->next)
;
// if fast == head this is an odd number list
// otherwise it is an even number list
slow = (fast == head) ? slow : slow->next;
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
使用 Floyd Cycle Detection Algorithm ，當 `fast` 抵達終點時 `slow` 剛好會在中間的位置。~~這題還要需要考慮到奇數或偶數的 list 。~~
:::info
~~TODO: 理論上存在可以不用判斷奇數偶數的方法。接下來會分析如何達到不用判斷並且修改。~~ :heavy_check_mark:
:::
調整 `slow` 和 `fast` 的初始值就可以避免最後針對 `slow` 做修正的判斷。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow, *fast;
for (slow = head->next, fast = slow; fast != head && fast != head->prev;
slow = slow->next, fast = fast->next->next)
;
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### q_delete_dup
> Delete all nodes that have duplicate string,
leaving only distinct strings from the original list.
Return true if successful.
Return false if list is NULL.
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_empty(head))
return true;
const char *last_value = NULL;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
if (!last_value)
last_value = entry->value;
else {
if (strncmp(last_value, entry->value, strlen(last_value) + 1) ==
0) {
list_del(&entry->list);
q_release_element(entry);
} else {
last_value = entry->value;
}
}
}
return true;
}
```
因為有可能會移除節點所以使用 `list_for_each_entry_safe` traverse 每個 entry ，同時使用 `last_value` 追蹤前一個值，用來比較是否是重複的結點。
::: info
~~接下來會調整`list_for_each_entry_safe` 的參數，並且更改 `last_value` 初始化的方式避免在 for 迴圈中不必要的判斷。~~ :heavy_check_mark:
:::
把 `const char *last_value` 的初始值設為 `""` 就可以減少在 for 迴圈中的 if-else 判斷。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_empty(head))
return true;
const char *last_value = "";
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(last_value, entry->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
} else {
last_value = entry->value;
}
}
return true;
}
```
### q_swap
> Attempt to swap every two adjacent nodes.
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_is_singular(head))
return;
struct list_head *n1, *n2;
for (n1 = head->next, n2 = n1->next; n1 != head && n2 != head;
n1 = n1->next, n2 = n1->next) {
list_del(n2);
n2->prev = n1->prev;
n2->next = n1;
n1->prev->next = n2;
n1->prev = n2;
}
}
```
兩兩一組做交換，先把 n2 結點移除，在把 n2 放到 n1 前面。
### q_reverse
> Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
const struct list_head *const first = head->next;
for (struct list_head *new_first = first->next; first->next != head;
new_first = first->next) {
list_del(new_first);
list_add(new_first, head);
}
}
```
先固定一個指標指向第一個結點，在這裡只的是 `first` 。
接下來不斷的把 `first->next` 往前移到最前面，直到 `first` 變成最後一個節點。
### q_sort
> Sort elements of queue in ascending order
No effect if q is NULL or empty. In addition, if q has only one
element, do nothing.
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
// break the structure of circular linked list
head->prev->next = NULL;
head->next = mergesort(head->next);
// circular linked list reconstuct
struct list_head *prev = head, *cur = head->next;
for (; cur != NULL; prev = cur, cur = cur->next) {
cur->prev = prev;
}
prev->next = head;
head->prev = prev;
}
```
在 `q_sort` 我選用的是 mergesort ，但在正式開始 sorting 前我們必須先做一點準備
* 我們的 linked list 有一個 dummy head ，我們必須決定是在接下來的過程中(指 `mergesort`的過程)是否要保留這個 node 。選擇保留的話代表接下來做 list 的分割就要再創建新的 `head_node` 。選擇捨棄就要在 `q_sort` 結束前讓他回復原狀。在這裡我選擇捨棄，因為我是用 recursive 的方式去實現 mergesort ，這代表我可能在做 sorting 的過程中分割了很多個 list 那這樣我就必須 `malloc` 很多額外的 `head_node` ，增加 heap 的負擔。
> 這裡說的 "捨棄" 並不是真的把它給 deallocate 而是指在傳入 function 、或其他操作時不要考慮它。
```c
head->next = mergesort(head->next);
```
* 我們的 list 是 circular linked list 在做 divide 的階段我們必須知道我分割出來的 list 的頭尾在哪，但我們在上個選擇中決定捨棄 dummy head ，已經無法追蹤 `tail` 的位置，因此我這邊決定把我們 list 暫時的轉成一般的 linked list，使得 `tail->next == NULL`。最後再重新連起來。
>這裡指的 `head/tail` 是指有 entry 的結點。
```c
// break the structure of circular linked list
head->prev->next = NULL;
// MERGE
// circular linked list reconstuct
struct list_head *prev = head, *cur = head->next;
for (; cur != NULL; prev = cur, cur = cur->next) {
cur->prev = prev;
}
prev->next = head;
head->prev = prev;
```
最後就是實作 mergesort 的部分了。此部分有參考[你所不知道的-C-語言-linked-list-和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)
```c
struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head->next;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
slow = head;
struct list_head *l1 = mergesort(slow);
struct list_head *l2 = mergesort(fast);
return merge(l1, l2);
}
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *nl = NULL, **ptr = &nl;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0) {
*ptr = l1;
l1 = l1->next;
} else {
*ptr = l2;
l2 = l2->next;
}
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return nl;
}
```
## qtest-shuffle
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
if (!l_meta.l)
report(3, "Warning: Calling shuffle on null queue");
error_check();
for (size_t len = l_meta.size; len > 0; len--) {
// get an random index and move the target to tail
size_t index = rand() % len;
struct list_head *tar = l_meta.l->next;
while (index--)
tar = tar->next;
list_del(tar);
list_add_tail(tar, l_meta.l);
}
show_queue(3);
return ok && !error_check();
}
```
```c
ADD_COMMAND(shuffle, " | Shuffle");
```
參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
我實現這個演算法的方法是隨機選一個 node 搬到最後面去，然後再縮小一單位的選取範圍 (`len`)，直到選取範圍為 0 。
## Valgrind 排除 qtest 記憶體錯誤
:::warning
這部分需要 trace 大量的 code，可以善用 grep，但還是使用 [ctags 跟 CScope](https://www.youtube.com/watch?v=9NcM-Tj2UZI)。
:::
首先執行 `$ make valgrind` 會出現以下訊息
```shell
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==247490== 2 bytes in 1 blocks are still reachable in loss record 1 of 3
==247490== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==247490== by 0x4A4C50E: strdup (strdup.c:42)
==247490== by 0x1109F0: linenoiseHistoryAdd (linenoise.c:1236)
==247490== by 0x111583: linenoiseHistoryLoad (linenoise.c:1325)
==247490== by 0x10C79D: main (qtest.c:980)
```
從上方的資訊是 function call 的順序，他告訴我們 `malloc` 是被誰觸發的。其中 `linenoiseHistoryAdd` 最值得觀察，因為 `malloc` 跟 `strdup` 都是預設的 library 的 function 會出現 memory leak 一定是使用者沒有恰當使用，因此我選擇先觀察 `linenoiseHistoryAdd`。
```c=1235
// part of function `linenoiseHistoryAdd` in linenoise.c
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;
```
根據 valgrind 的錯誤訊息可以看先 linenoise.c:1236，呼叫 `strdup` 的部分。`strdup` 回傳的結果被存在 `history` 裡面。
且`$ man strdup` 裡有說：
* Memory for the new string is obtained with malloc(3), and can be freed with free(3).
所以我們可以推測是 `history` 裡的東西沒有 `free` 才導致 memory leak。
這時候如果去找 `history` 的 declaration 可以發現他是 `static`。
```c
static char **history = NULL;
```
* 6.2.1 Scopes of identifiers
>If the declarator or type specifier that declares the identifier appears outside of any block or list of parameters, the identifier has file scope, which terminates at the end of the translation unit.
* 6.2.2 Linkages of identifiers
> An identifier declared in different scopes or in the same scope more than once can be made to refer to the same object or function by a process called **linkage**.
>In the set of translation units and libraries that constitutes an entire program, each declaration of a particular identifier with **external linkage** denotes the same object or function. Within one translation unit, each declaration of an identifier with **internal linkage** denotes the same object or function.
>If the declaration of a **file scope identifier** for an object or a function contains the storageclass specifier **static**, the identifier has **internal linkage**.
根據 C99 這裡的 `static char **history` 具有 **internal linkage** 。換句話說只有在這個 translation unit 的 function 才能 `free` 他，所以我們需要在這個檔案裡面具續搜查。接下來會發現兩個 static function 分別為 `freeHistory` 和 `linenoiseAtExit` ，後者是前者的 caller 。`linenoiseAtExit` 沒有被其他人呼叫，但是在 `enableRawMode` 他被當作參數傳入 `atexit`。
* 7.20.4.2 The atexit function
> The atexit function registers the function pointed to by func, to be called without arguments at normal program termination.
根據 C99 可以知道，只要正常的終止程式有被註冊的 function 就會被呼叫。我們在執行的時候確定是正常退出的但 `history` 沒有被 free 這代表 `enableRawMode` 沒被呼叫，因此我們繼續往上追查。
`enableRawMode` 被兩個 function 呼叫，分別是 `linenoisePrintKeyCodes` 和 `linenoiseRaw` ，前者在我們的 Lab 中沒被呼叫到，而後者被 `linenoise` 呼叫。 在 `runconsole` 裡面 `linenoise` **可能** 會被呼叫，這會被 `has_file` 的數值影響。
```c
// part of `runconsole` in console.c
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);
}
```
`has_file` 初始值是 false ，但是有可能會被透過 `push_file` 被改為 true 。所以問題就在這邊。因為 `has_file` 為 true 導致 `linenoise` 沒被執行，間接造成沒有註冊 `linenoiseAtExit` 到 `atexit`。
做一個簡單的小結， memory leak 起因於 `linenoiseHistoryLoad` 被呼叫且 `linenoise` 沒被呼叫。所以我們有兩種方法修復：
* 不要呼叫 `linenoiseHistoryLoad`
* 呼叫 `linenoise`
根據 `linenoise.c` 的 comment 我推測 `linenoiseHisotry` 相關的 function 會把我們在 command line 輸入的紀錄保存在一個叫 `.cmd_history` 的檔案內。以下實驗驗證我的想法。
```shel
kuan@Athena:~/linux2022/lab0-c$ ./qtest
cmd> new
l = []
cmd> ih 1
l = [1]
cmd> ih 2
l = [2 1]
cmd> ih 3
l = [3 2 1]
cmd> sort
l = [1 2 3]
cmd> quit
Freeing queue
kuan@Athena:~/linux2022/lab0-c$ cat .cmd_history
new
ih 1
ih 2
ih 3
sort
quit
kuan@Athena:~/linux2022/lab0-c$
```
但是執行完 `$ make check` 或 `$ make test` ， `.cmd_history` 卻不會有任何改變。他們倆者有個共通點是都是從 `*.cmd` 讀取指令。如果再往 `Makefile` 看，可以看到 `make check` 在執行的時候會加一個 `-f` ，而 `make test` 會執行 `driver.py`， `driver.py` 在執行 `qtest` 時也會加 `-f`。 在 `qtest` 的 main 裡面有一個區域在做這方面的處理，如果有 `-f` 就會設定一個檔案名稱，這個設定會導致 `has_infile` 變成 true。
最後可以歸納出 `make check` 和 `make test` 都用不到 `.cmd_history`。所以我決定當有檔案讀取時，不要呼叫 `linenoiseHistoryLoad`。所以更改成如下：
```c
if (!infile_name)
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
最後再執行一次 `$ make test` ，前面的錯誤訊息沒了，但是在 trace-17 還有。
```shell
+++ 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
ERROR: Probably not constant time
Probably constant time
Probably constant time
==249796== 32 bytes in 1 blocks are still reachable in loss record 1 of 29
==249796== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==249796== by 0x10CE48: malloc_or_fail (report.c:189)
==249796== by 0x10D8D2: add_cmd (console.c:89)
==249796== by 0x10DC5C: init_cmd (console.c:408)
==249796== by 0x10C594: main (qtest.c:973)
```
在 `add_cmd` 裡， `malloc_or_fail` 會把 `malloc` 出來的 address 存在 `cmd_list` 裡面。 `cmd_list` 在 `do_quit` 被 free 。 `do_quit` 會被 `finish_cmd1` 呼叫。最後可以追蹤到 `qtest.c` 裡的 `main` 有這一段程式碼。
```c
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
```
只要 `finish_cmd` 有被呼叫，就會不有 memory leak ，然而 memory leak 還是發生了， 故可以推測 `finish_cmd` 沒有被呼叫，這可能是 `&&` 觸發了 `Short circuit` 的現象。
* 6.5.13 Logical AND operator
> Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; there is a sequence point after the evaluation of the first operand. If the first operand compares equal to 0, **the second operand is not evaluated**.
只要把 `ok` 和 `finish_cmd` 的順序對調就可以解決這個問題了。為了驗證我的想法決定再繼續 trace code。
如果 `short circuit` 被觸發，代表 `ok = false` 。我們可以再往 `run_console` 看他的回傳值。
```c
return err_cnt == 0;
```
`err_cnt` 在 `record_error` 會被更改。
```c
static void record_error()
{
err_cnt++;
if (err_cnt >= err_limit) {
report(1, "Error limit exceeded. Stopping command execution");
quit_flag = true;
}
}
```
由此可知，是因為 trace-17 有一個非 constant time 的 error ，導致 `err_cnt` 不為 0 造成 shirt circuit。
Sign in with Wallet
Connect another wallet