# 2023q1 Homework1 (lab0)
contributed by < `gaberplaysgame` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11400 @ 2.60GHz
CPU family: 6
Model: 167
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 5184.00
```
:::warning
在終端機執行 `export LC_ALL=C`，再執行上述命令。`lscpu` 套件目前的中文翻譯品質不佳。
:notes: jserv
:::
## 開發過程
### 嘗試改進 lab0-c
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔
:notes: jserv
:::
#### q_new()
依據作業規範，`q_new()` 應配置可容納 `list_head` 的記憶體空間，並對節點進行設定，這部份`list.h`有`INIT_LIST_HEAD(head)`可以做到，故這裡就直接用內建函式處理。考慮到 malloc 有可能無法配置空間，所以用一個if處理空間分配失敗的狀況，若失敗則 head 為 NULL 。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
#### q_insert_head()
與下面的 insert_tail 是同樣道理，分了三次 if 來去排除掉可能 malloc 錯誤或者 head 為 NULL 的情況。
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔
:notes: jserv
:::
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false; //if head == NULL, return false
element_t *new = malloc(sizeof(element_t));
if (!new)
return false; //if malloc() failed
size_t len_s = strlen(s) + 1;
new->value = (char *) malloc(len_s * sizeof(char));
if (!new->value){
free(new);
return false; //if malloc() failed, free new and return false
}
//copy string value
memcpy(new->value, s, len_s);
//utilize function of list.h
list_add(&new->list, head);
return true;
}
```
#### q_insert_tail()
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false; //if head == NULL, return false
element_t *new = malloc(sizeof(element_t));
if (!new)
return false; //if malloc() failed
size_t len_s = strlen(s) + 1;
new->value = (char *) malloc(len_s);
if (!new->value){
free(new);
return false; //if malloc() failed, free new and return false
}
//copy string value
memcpy(new->value, s, len_s);
//utilize function of list.h
list_add_tail(&new->list, head);
return true;
}
```
#### q_size()
```c
int q_size(struct list_head *head)
{
//if head is NULL or head->next = head, the queue has no element
if (!head || list_empty(head))
return 0;
int count = 0;
struct list_head *iter;
list_for_each(iter, head)
count++;
return count;
}
```
#### q_free()
這邊利用內建的函式來做 free ，用 for 迴圈<s>遍歷</s> --- 整個鏈結串列，複雜度為 O(n)。
:::warning
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 並改進漢語表達。
:notes: jserv
:::
```c
void q_free(struct list_head *l)
{
if (!l)
return; // if head is NULL
element_t *iter, *next;
list_for_each_entry_safe (iter, next, l, list) {
list_del(&iter->list); // delete node
q_release_element(iter); // free element
}
free(l);
}
```
#### q_remove_head()
與下方的`remove_tail`是一樣的，只是改`head->next`或`head->prev`。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) //there is no element in list
return NULL;
element_t *remove = list_entry(head->next, element_t, list);
list_del(&remove->list); //an element in list is removed
if (sp && bufsize) { //sp != NULL and bufsize != 0
memcpy(sp, remove->value, bufsize);
sp[bufsize - 1] = '\0';
}
return remove;
}
```
#### q_remove_tail()
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) //there is no element in list
return NULL;
element_t *remove = list_entry(head->prev, element_t, list);
list_del(&remove->list); //an element in list is removed
if (sp && bufsize) { //sp != NULL and bufsize != 0
memcpy(sp, remove->value, bufsize);
sp[bufsize - 1] = '\0';
}
return remove;
}
```
#### q_delete_mid()
利用 [Floyd Tortoise and Hare Algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare) ，原理是給定兩個迭代節點分別跑一步與兩步，若兩個節點同時在除起點外同個位置時則代表鏈結串列有閉環。因為 linux 的鏈結串列是用循環雙向的方式做的，因此可以利用該演算法，在 Hare 第一次跑到鏈結串列的尾端時，Tortoise 會剛好在中間節點。
由於鏈結串列的長度會有分單雙數的情況，單數時 Hare 可以剛好跑到尾端，雙數則會多跑一<s>格</s> ?? 到 head 指標。由於 Hare 一次跑兩格，所以跑到尾端和跑到 Head 的事件不會同時發生，可以當作 while 判斷式的中止條件。
:::warning
注意量詞，翻閱辭典以理解「格」的使用時機。
:notes: jserv
:::
```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
*tortoise = head->next,
*hare = head->next; // given two node points to 0th node, using floyd's
// tortoise and hare algorithm.
while (hare != head &&
hare != head->prev) { // when hare reaches end of list or head,
// tortoise will be in the middle of the list
tortoise = tortoise->next;
hare = hare->next->next;
}
element_t *element = list_entry(tortoise, element_t, list);
list_del(&element->list);
q_release_element(element);
return true;
}
```
#### q_delete_dup()
原本寫的程式碼：利用一個`flag`和`strcmp`進行兩個元素的比較，若`strcmp`出來0則`flag`為 true 並刪除`cur`的元素，下次若是`strcmp`非0，`flag`為 true 時亦會刪除元素。如此便有三點要處理：
1. 當`next == head`時，由於`head`沒有數值，不能進行`strcmp`，因此只能進到`flag`判斷。
2. 當`strcmp == 0`時，進行元素刪除。
3. 當`flag == true`時，進行元素刪除。
下面是第一版的程式碼（節錄）：
```c
element_t *cur, *next;
bool flag = false;
list_for_each_entry_safe (cur, next, head, list) {
if (&next->head != head) {
int cmp = strcmp(cur->value, next->value);
if (!cmp) {
flag = true;
list_del(&cur->list);
q_release_element(cur);
}
} else if (flag) {
flag = false;
list_del(&cur->list);
q_release_element(cur);
}
}
```
可以看到上面程式碼用了很多 if，尤其`list_del`的部份有重複，自己都認為沒有品味，因此花了一些時間在改進程式碼方面。
首先嘗試了把上面提到的重複部份整理一頓，先忽略了`next->list`可能為`head`的情形，利用`cmp`與`flag`兩個數值相反的特性將區塊合併。
1. 當 cmp 為0時，`flag`會被設為 true ，這代表如果下一圈 cmp 不是0時仍可以刪除 cur 的元素
2. 沿述，當 cmp 不是0時，若 flag 為 true ，則刪除元素；若 flag 為 false ，則代表沒有需要刪除元素，可以進到下一圈。
排除掉未刪除元素的可能性後，可以看到`flag = !cmp`的性質，且可以放在程式最後面執行，因此只要把 cmp 非0，flag 為 false 的情況先擋掉，就可以把兩個區塊合併。
```c
if (cmp && !flag)
continue;
list_del(&cur->list);
q_release_element(cur);
flag = !cmp;
```
再來就是解決`next->list`可能為 head 的情形了。若此狀況發生，cmp 沒辦法決定值，因此給這段加上了一個三元判斷式判定若該狀況發生，指定 cmp 為 true 。如此可以保證`if (cmp && !flag)`能被觸發，再來若 flag 為 true 可以保證元素能被刪除。
改進過後的程式碼：
:::danger
不用張貼完整程式碼，只要列出差異的部分，善用 `diff`
:notes: jserv
:::
<s>
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false; // list is NULL
element_t *cur, *next;
bool flag = false;
list_for_each_entry_safe (cur, next, head, list) {
int cmp = &next->list != head ?
strcmp(cur->value, next->value) :
true; // no comparison if next is head,
// comparison gives 0 or nonzero value
if (cmp && !flag)
continue;
list_del(&cur->list);
q_release_element(cur);
flag = !cmp;
}
return true;
}
</s>
~~目前只有這個函式還沒有去做正確性的測試，等sort與reverse等做完後才能進一步確認是否運行順利。~~ 經過測試後確定可以順利通過<s>autojudge測資。</s>
:::danger
注意看程式碼，`lab0-c` 使用 `autograde` 一詞，「測試案例」不該簡稱「測資」。
:notes: jserv
:::
#### q_swap()
因為下方的 reverse 函式會用到 swap <s>的技術</s>，所以將實際將兩個節點進行交換的步驟給獨立出來。
:::warning
改進你的漢語表達。
:notes: jserv
:::
```c
void swap(struct list_head *n1, struct list_head *n2)
{
struct list_head *tmp = n1->next;
n1->next = n2->next;
n2->next->prev = n1;
n2->next = tmp;
n2->next->prev = n2;
tmp = n2->prev;
n2->prev = n1->prev;
n1->prev->next = n2;
n1->prev = tmp;
n1->prev->next = n1;
}
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *n1 = head->next, *n2 = n1->next;
while (n1 != head && n2 != head) {
swap(n1, n2);
n1 = n1->next;
n2 = n1->next;
}
}
```
#### q_reverse()
本意上用到的是頭尾交換的想法，由於是循環陣列容易找到鏈結串列尾，故用這個方法實作。
```c
void reverse(struct list_head *start, struct list_head *end)
{
while (start != end && start != end->next) {
swap(start, end);
struct list_head *tmp = end->next;
end = start->prev;
start = tmp;
}
}
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
reverse(head->next, head->prev);
}
```
#### q_reverseK()
方法目前只有想到類似硬破法，將佇列拆為 k 個（或更少）一組，然後分別進行 reverse 操作。
```c
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 *start = head->next, *end = start;
while (end != head) {
int count = 1;
while (count != k && end->next != head) {
end = end->next;
count++;
}
struct list_head *tmp = end->next;
reverse(start, end);
start = tmp, end = start;
}
}
```
#### q_sort()
這裡的 sort 是使用 mergesort 來實作，方法有參考[你所不知道的C語言：Merge Sort的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)與間接指標的應用，但有用到將循環鏈結串列斷開成一般鏈結串列的操作，還沒有想到有沒有可以保持循環鏈結串列的實作方式。
```c
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *new_head = NULL, **indirect = &new_head;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0) {
*indirect = l1;
l1 = l1->next;
} else {
*indirect = l2;
l2 = l2->next;
}
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return new_head;
}
struct list_head *mergeSort(struct list_head *head, struct list_head *tail)
{
if (head == tail)
return head;
struct list_head *start = head, *end = tail;
while (start != end && start != end->prev) {
start = start->next;
end = end->prev;
}
if (start == end)
end = end->next;
start->next = NULL;
end->prev = NULL;
struct list_head *l1 = mergeSort(head, start), *l2 = mergeSort(end, tail);
return merge(l1, l2);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) ||
list_is_singular(head)) // if head == NULL or empty or one element
return;
struct list_head *start = head->next, *end = head->prev;
// Break the circular linked list
start->prev = NULL;
end->next = NULL;
// Mergesort
struct list_head *new_head = mergeSort(start, end);
start = new_head;
end = start->next;
// Rebuild circular linked list
for (; end != NULL; start = start->next, end = end->next) {
end->prev = start;
}
start->next = head;
new_head->prev = head;
head->next = new_head;
head->prev = start;
}
```
#### q_merge()
有用到前面 merge 的想法，並且用 Devide & Conquer 的方式處理合併，使時間複雜到可以降到 O(NlogK)。
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔
:notes: jserv
:::
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
int interval = 1, list_amount = 0;
queue_contex_t *contex = NULL;
list_for_each_entry (contex, head, chain) {
list_amount++;
contex->q->prev->next = NULL;
}
struct list_head *l1 = NULL, *l2 = NULL;
while (interval < list_amount) {
for (int i = 0; i < list_amount - interval; i += interval * 2) {
list_for_each_entry (contex, head, chain) {
if (contex->id == i)
l1 = contex->q;
else if (contex->id == i + interval)
l2 = contex->q;
}
l1->next = merge(l1->next, l2->next);
l2->prev = l2;
l2->next = l2;
}
interval *= 2;
}
struct list_head *start, *end;
head = l1;
start = head->next;
end = start->next;
// Rebuild circular linked list
for (; end != NULL; start = start->next, end = end->next) {
end->prev = start;
}
start->next = head;
head->next->prev = head;
head->prev = start;
return q_size(head);
}
```
#### q_descend()
這函式用了兩個指標 `left` 與 `right` 來處理數值比較，當 right 指到 head 時結束操作並回傳佇列大小。其餘實作方式基本可以參考 remove 系列。
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔
:notes: jserv
:::
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head)) // if head == NULL or empty or one element
return 0;
if (list_is_singular(head))
return 1;
int count = 1;
struct list_head *left = head->next, *right = left->next;
while (right != head) {
element_t *left_entry = list_entry(left, element_t, list);
if (strcmp(left_entry->value,
list_entry(right, element_t, list)->value) < 0) {
left = left->next;
list_del(&left_entry->list);
q_release_element(left_entry);
count--;
} else {
right = right->next;
count++;
}
}
return count;
}
```
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔
:notes: jserv
:::
### 引進 lib/list_sort.c
引入`linux/list_sort.[c, h]` 並做了些特別的修改，主要是為了繞開不能修改 `queue.h` 的限制，所以將 `list_sort.[c, h]` 作為新的引入檔，以 q_list_sort 作為在 `qtest.c` 的呼叫函式。
```c
ADD_COMMAND(lsort, "Sort queue in ascending order in linux kernel way", "");
```
cmp 函式以此方式實作，由於不太確定 priv 傳入值的用處，加上可以為 NULL 值，cmp 函式就將此刪除：
```c
__attribute__((nonnull(1,2)))
int q_list_cmp(const struct list_head *a, const struct list_head *b)
{
element_t *element_a = list_entry(a, element_t, list);
element_t *element_b = list_entry(b, element_t, list);
int res = strcmp(element_a->value, element_b->value);
return res;
}
```
這邊以原本進行 make 是沒有問題的，但在更新 GitHub 時有遇到 cppcheck 的 "Null pointer dereference" ，指向 list_entry 的用法。
```shell
list_sort.c:24:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *element_a = list_entry(a, element_t, list);
```
起初不太知道這個錯誤應該如何解決，以為是程式碼本身的錯誤，在這個程式碼上面花了一點時間。觀摩 [jasperlin1996](https://hackmd.io/@jasperlin1996/linux2022-lab0) 後發現說可能是 cppcheck 的問題。由於學長已經做過了 cppcheck 1.9~2.7 的測試，自己把最新版的 2.10 安裝之後這個錯誤仍存在，最後只好使用 cppcheck suppression 的方式解決，即使用 `cppcheck-suppress nullPointer`繞過。這邊引用學長對於這個錯誤的敘述以及當屆[討論](https://www.facebook.com/groups/system.software2022/permalink/1983461425168591/)：
> 這邊是因為 list.h 中 container_of 的實作中，有一行是 __typeof__(((type *) 0)->member) 而 (type *) 0 的確是 null pointer。不過這邊的用法是為了取得 member 的 type，且這個用法是符合 ANSI C 的標準的，詳細的說明可以看這篇：https://stackoverflow.com/questions/13723422/why-this-0-in-type0-member-in-c
以及規格書的第 6.3.2 章關於 pointer 的說明：http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
另外直接引入 `list_sort.[c, h]` 會遇到 [likely & unlikely](https://meetonfriday.com/posts/cecba4ef/) 巨集的問題，雖然這段編碼只是為了優化 gcc ，但為了不過度影響程式效能自己還是從`compiler.h` 抓入相關部份並放入`list_sort.c`。
:::danger
注意書寫規範，中英文間用一個半形空白字元區隔。
改進你的漢語表達。
:notes: jserv
:::
### 對自撰 sort 與 list_sort 進行效能分析
利用 [Perf](https://en.wikipedia.org/wiki/Perf_(Linux)) 進行效能分析，執行 10 次並取平均，測試程式如下：
```
new
ih RAND <number>
time
sort/lsort
time
free
```
<s>Perf 似乎無法支援筆電 CPU ，導致部份如 instruction, cycles 的測試無法進行，這邊先貼上部份的測試結果，之後預計會換回桌機進行測試。</s>筆電使用 i7-7700 CPU 無法進行有關 instruction 與 cycles 等的測試，換回桌機使用 i5-11400 已解決問題，故以下會使用桌機數據重新進行紀錄。
:::warning
清楚列舉硬體型號和相關系統資訊，這樣他人才能協助排除問題。
:notes: jserv
:::
- 註：q 為 `q_sort` ，l 為 `q_list_sort`
| number | instruction | time | cycles | page fault | branch |
| - | - | - | - | - | - |
| **1024_q** | 5,934,943 | 0.91 ms | 3,884,975 | 112 | 911,195 |
| **2048_q** | 10,164,886 | 1.48 ms | 6,164,264 | 150 | 1,509,771 |
| **4096_q** | 18,852,459 | 4.76 ms | 19,931,933 | 220 | 2,755,409 |
| **10240_q** | 45,017,257 | 6.47 ms | 27,146,322 | 438 | 6,533,543 |
| **102400_q** | 448,797,359 | 100.75 ms | 425,198,490 | 3677 | 65,891,213 |
| **409600_q** | 1,824,311,621 | 649.45 ms | 2,562,835,035 | 14477 | 270,998,617 |
| **1024_l** | 5,504,024 | 1.76 ms | 3,135,236 | 112 | 797,843 |
| **2048_l** | 9,005,109 | 2.62 ms | 10,824,548 | 148 | 1,229,047 |
| **4096_l** | 16,449,283 | 6.55 ms | 12,042,236 | 221 | 2,164,575 |
| **10240_l** | 38,676,693 | 18.08 ms | 18,684,006 | 437 | 4,955,814 |
| **102400_l** | 372,969,154 | 46.82 ms | 197,921,647 | 3677 | 46,956,545 |
| **409600_l** | 1,488,046,316 | 177.62 ms | 725,989,221 | 14477 | 187,069,862 |
這邊取的是平均值的數值，實際的時間差在正負 10ms 左右。可以看到在 instruction, cycle, branch 上 list sort 都比自己寫的 sort 還有好。由於時間差落在正負 10ms ，因此在數量級小的情況下兩個演算法難分軒輊，但若是數量級大則可以明顯看到 list sort 的表現比自己寫的還要消耗更少時間。綜合以上數據可以發現 list sort 在各方面都優於自己實作的 merge sort 。
### 利用 Valgrind 排除 qtest 實作的記憶體錯誤
執行`make valgrind`可以得到以下結果（節錄）：
```
--- trace-01-ops 0/5
--- trace-02-ops 0/6
--- trace-03-ops 0/6
--- trace-04-ops 0/6
--- trace-05-ops 0/6
--- trace-06-ops 0/6
--- trace-07-string 0/6
--- trace-08-robust 6/6
--- trace-09-robust 0/6
--- trace-10-robust 6/6
--- trace-11-malloc 6/6
--- trace-12-malloc 6/6
--- trace-13-malloc 0/6
--- trace-14-perf 6/6
--- trace-15-perf 6/6
--- trace-16-perf 6/6
```
這邊取`trace-01-ops`的問題進行細部觀察，可以看到大致由三種問題組成：
:::spoiler
```
gaberil0903@host:~/linux2023/lab0-c$ valgrind ./qtest -f traces/trace-01-ops.cmd
# Test of insert_head and remove_head
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
==12508== Invalid read of size 8
==12508== at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f3d8 is 8 bytes before a block of size 2,049 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10C0ED: do_remove (qtest.c:371)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x4852B00: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f3d0 is 16 bytes before a block of size 2,049 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10C0ED: do_remove (qtest.c:371)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x4852AE4: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f3c8 is 24 bytes before a block of size 2,049 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10C0ED: do_remove (qtest.c:371)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x4852AF0: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f3c0 is 32 bytes before a block of size 2,064 in arena "client"
==12508==
Removed dolphin from queue
l = [bear gerbil]
==12508== Invalid read of size 8
==12508== at 0x4852947: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f030 is 3 bytes after a block of size 45 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F29C: test_malloc (harness.c:133)
==12508== by 0x10F765: q_insert_head (queue.c:48)
==12508== by 0x10CAA5: do_ih (qtest.c:224)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x485294F: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f038 is 11 bytes after a block of size 45 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F29C: test_malloc (harness.c:133)
==12508== by 0x10F765: q_insert_head (queue.c:48)
==12508== by 0x10CAA5: do_ih (qtest.c:224)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x4852934: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f040 is 19 bytes after a block of size 45 alloc'd
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F29C: test_malloc (harness.c:133)
==12508== by 0x10F765: q_insert_head (queue.c:48)
==12508== by 0x10CAA5: do_ih (qtest.c:224)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== Invalid read of size 8
==12508== at 0x485293F: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f048 is 24 bytes after a block of size 48 in arena "client"
==12508==
==12508== Invalid read of size 1
==12508== at 0x4852A10: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F89C: memcpy (string_fortified.h:29)
==12508== by 0x10F89C: q_remove_head (queue.c:96)
==12508== by 0x10C333: do_remove (qtest.c:404)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Address 0x4b7f420 is 64 bytes inside a block of size 2,049 free'd
==12508== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10C3B3: do_remove (qtest.c:454)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508== Block was alloc'd at
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10C0ED: do_remove (qtest.c:371)
==12508== by 0x10C4DB: do_rh (qtest.c:461)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
==12508== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10CD3D: do_new (qtest.c:146)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
==12508== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==12508== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508== by 0x10F29C: test_malloc (harness.c:133)
==12508== by 0x10F6A1: q_new (queue.c:20)
==12508== by 0x10CD76: do_new (qtest.c:150)
==12508== by 0x10DF86: interpret_cmda (console.c:181)
==12508== by 0x10E53B: interpret_cmd (console.c:201)
==12508== by 0x10E93C: cmd_select (console.c:610)
==12508== by 0x10F228: run_console (console.c:705)
==12508== by 0x10D378: main (qtest.c:1270)
==12508==
```
:::
```
==12311== Invalid read of size 8
==12311== at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311== by 0x10F89C: memcpy (string_fortified.h:29)
==12311== by 0x10F89C: q_remove_head (queue.c:96)
==12311== by 0x10C333: do_remove (qtest.c:404)
==12311== by 0x10C4DB: do_rh (qtest.c:461)
==12311== by 0x10DF86: interpret_cmda (console.c:181)
==12311== by 0x10E53B: interpret_cmd (console.c:201)
==12311== by 0x10E93C: cmd_select (console.c:610)
==12311== by 0x10F228: run_console (console.c:705)
==12311== by 0x10D378: main (qtest.c:1270)
==12311== Address 0x4b7f3d8 is 8 bytes before a block of size 2,049 alloc'd
==12311== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311== by 0x10C0ED: do_remove (qtest.c:371)
==12311== by 0x10C4DB: do_rh (qtest.c:461)
==12311== by 0x10DF86: interpret_cmda (console.c:181)
==12311== by 0x10E53B: interpret_cmd (console.c:201)
==12311== by 0x10E93C: cmd_select (console.c:610)
==12311== by 0x10F228: run_console (console.c:705)
==12311== by 0x10D378: main (qtest.c:1270)
==12311== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12311== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311== by 0x10CD3D: do_new (qtest.c:146)
==12311== by 0x10DF86: interpret_cmda (console.c:181)
==12311== by 0x10E53B: interpret_cmd (console.c:201)
==12311== by 0x10E93C: cmd_select (console.c:610)
==12311== by 0x10F228: run_console (console.c:705)
==12311== by 0x10D378: main (qtest.c:1270)
```
第一、二個問題源自 bufsize 大小為 1025，然而測試字串 dolphin 的大小長度只有 8 ，所以在 `memcpy(sp, remove->value, bufsize);` 中會造成記憶體空間錯誤。所以只要將 `bufsize` 更改為`bufsize > strlen(remove->value) + 1 ? strlen(remove->value) : bufsize` 就好。
```c
if (sp && bufsize) { // sp != NULL and bufsize != 0
memcpy(sp, remove->value, bufsize > strlen(remove->value) + 1 ? strlen(remove->value) + 1 : bufsize);
sp[bufsize - 1] = '\0';
}
```
根據執行順序，判斷第三個訊息來自於把佇列清空後沒有正常釋放記憶體所導致，根據`q_quit`函式可以看到有個不正常的`return true`在程式第3行被執行，導致後續沒有進行 free 佇列。將不正常的程式碼移除後即可解決這個錯誤。
:::spoiler
```c=
static bool q_quit(int argc, char *argv[])
{
return true;
report(3, "Freeing queue");
if (current && current->size > BIG_LIST_SIZE)
set_cautious_mode(false);
if (exception_setup(true)) {
struct list_head *cur = chain.head.next;
while (chain.size > 0) {
queue_contex_t *qctx, *tmp;
tmp = qctx = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
q_free(qctx->q);
free(tmp);
chain.size--;
}
}
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;
}
```
:::
再次執行`make valgrind`可以看到問題皆以修復。
### 利用 massif 視覺化 simulation
這邊設計一個實驗組與一個對照組，採用的是前章節出問題的 removehead <s>指令</s> ---，可以得出兩種結果，前者為<s>優化前，後者為優化後</s>：
:::warning
去查詢 optimize 的意思，留意 optimal 的定義。不要濫用詞彙。
:notes: jserv
:::
利用`valgrind --tool=massif ./qtest -f traces/sim-rh.cmd`與 Valgrind User Manual 9.3 的 massif-visualizer 來顯示結果：
```shell
massif-visualizer massif.out.14944
```
```shell
massif-visualizer massif.out.14972
```
可以看到在針對 q_quit 函式進行修復後，有改善記憶體的釋出，但程式執行最後仍未完全釋放記憶體。
### TODO: 利用 Address Sanitizer 修正 qtest 執行過程中的錯誤
使用 Address Sanitizer 後進行 `make test` 後發現編號第 14 的測試案例因超時無法順利通過，而編號第 17 的測試案例中，常數時間測試在 remove_head/tail 時為常數時間時非常數時間。<s>比對過其他人程式碼後還沒有找到問題在哪裡，預計會再進行深入研究。</s>
:::warning
不要說「其他人」，明確列出你參照的帳號名稱，還有你如何實驗。
:notes: jserv
:::
### 在 q_test 添加<s>指令</s> 命令 shuffle
:::warning
command 的翻譯是「命令」，instruction 的翻譯是「指令」，二者語境落差大。
:notes: jserv
:::
參考 [Fisher-Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法的<s>偽代碼</s> 虛擬碼進行實作。
:::warning
台灣的慣用翻譯風格中，少用「偽」，反過來說，中共的刊物就常見。
:notes: jserv
:::
```c
void q_shuffle(struct list_head *head, size_t len)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *tail = head->prev;
for (int i = len - 1; i > 0; i--) {
struct list_head *cur = head;
int j = rand() % (i + 1);
for (int tmp = 0; tmp <= j; tmp++)
cur = cur->next;
shuffle_swap(cur, tail);
tail = cur->prev;
}
}
```
實作完成後利用範例的[測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)進行卡方（$X^2$）的計算，得出約等於 22.9521 。$[1, 2, 3, 4]$ 的排序中共有 24 種排列組合，故自由度（P）為 23 。根據卡方分布圖查詢可知 P-value 介於 0.25~0.5 之間，大於常見的顯著水準 alpha (0.05) 。統計結果鑑定不拒絕虛無假說。
:::spoiler
```
Expectation: 41666
Observation: {'1234': 41341, '1243': 41787, '1324': 41601, '1342': 41794, '1423': 41864, '1432': 41914, '2134': 41506, '2143': 41670, '2314': 41623, '2341': 41579, '2413': 41635, '2431': 41982, '3124': 41732, '3142': 41633, '3214': 41552, '3241': 41843, '3412': 41806, '3421': 41728, '4123': 41406, '4132': 41222, '4213': 41999, '4231': 41325, '4312': 41783, '4321': 41675}
chi square sum: 22.952143234291746
```
:::
Sign in with Wallet
Connect another wallet