---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < [chiangkd](https://github.com/chiangkd) >
:::warning
:warning: 留意細節！唯有重視小處並步步為營，方可挑戰原始程式碼達到三千萬行的 Linux 核心
:notes: jserv
> Got it! 謝謝老師
:::
## 作業要求
Request followed [2023 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-f)
- [ ] 修改 `queue.[ch]` 以完成 `make test` 自動評分系統的所有項目
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，搭配 Massif 視覺化
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 確保 `qtest` 提供的 `web` 命令可以搭配上述佇列使用
- [ ] 新增命令 `shuffle`, 參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
- [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10`，觀察亂數字串分佈
- [ ] 研讀論文〈[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) 及程式實作的原理。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
## 改進 `queue.c`
### 結構體
`list_head` 為 doubly-linked list 的 node 或 head
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
```graphviz
digraph list_ele {
rankdir=LR;
node[shape=record];
head [label="{<left>prev|<right>next}", style=bold];
}
```
`element_t` 為 linked list 的 element
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
`element_t` 這個結構體，除了要用來找尋 `list` 整體的原因，透過嵌入 `list_head` 給除了
`Head` 可以搭配 `container_or` 巨集也可得知
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
value [label="{value}"];
head [label="{<prev>prev|<next>next}"];
style=bold;
label=element_t
}
}
```
- 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)
```c
typedef struct {
struct list_head head;
int size;
} queue_chain_t;
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
head [label="{<prev>prev|<next>next}"];
value [label="{size}"];
style=bold;
label=queue_chain_t
}
}
```
`queue_context_t` 為 chain of queues
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_1 {
node [shape=record];
q_1 [label="q|{<prev>prev|<next>next}"];
subgraph cluster_A {
chain [label="<label>chain|{<prev>prev|<next>next}"];
s [label="{size}"];
style="dashed,bold";
color=red;
label=queue_chain_t
}
int [label="{int}"];
style=bold;
label=queue_context_t
}
subgraph cluster_2 {
node [shape=record];
q_2 [label="q|{<prev>prev|<next>next}"];
subgraph cluster_B {
chain_2 [label="<label>chain|{<prev>prev|<next>next}"];
s_2 [label="{size}"];
style="dashed,bold";
color=red;
label=queue_chain_t
}
int_2 [label="{int}"];
style=bold;
label=queue_context_t
}
chain:next->chain_2:label
chain_2:prev->chain:label
}
```
在多個 queue 之間的操作，如 `do_queue` 是透過 `chain` 來連接起來的，也因此在 `q_merge` function 中給定的參數為 `list_head *head`，但查看 `do_merge` 之後才會看到這裡傳入的是 `queue_chain_t` 的 `chain`，也是連接各個 queue 的 linked list。
```c
if (current && exception_setup(true))
len = q_merge(&chain.head);
```
做個驗證，在 `q_merge` 中來測試並呼叫 `merge` command，函式中暫時先撰寫透過傳入的 `chain` 找其所屬 `element_t` 的 value
```c
printf("value = %s\n", list_entry(list_entry(head->next, queue_contex_t, chain)->q->next, element_t, list)->value);
```
```shell
cmd> new
l = []
cmd> ih Hello
l = [Hello]
cmd> it CKD
l = [Hello CKD]
cmd> merge
value = Hello
```
- 印出 list 的第一個 `element_t` 的 `value`
:::warning
與其複製程式碼，你應揣摩背後的設計考量，特別是你的推理和驗證。
:notes: jserv
> 新增示意圖及個人認為設計考量(待補充)
:::
:::info
題外話，在化 graphviz 的時候想要虛線功能，但不知道關鍵字是什麼 (加粗為 `bold`，直覺認為是 `dot`)，問了一下 chatGPT 之後它告訴我是 `dotted`
:::
### q_new
```c
struct list_head *q_new()
{
struct list_head *q_head = malloc(sizeof(*q_head));
if (!q_head) // If allocate failed
return NULL;
INIT_LIST_HEAD(q_head);
return q_head;
}
```
:::warning
改為更精簡的敘述:
```c
struct list_head *q_head = malloc(sizeof(*q_head));
```
修正程式碼註解用語。
:notes: jserv
>Fixed. Thanks!
:::
### q_free
```c
void q_free(struct list_head *l)
{
if(!l)
return;
element_t *c, *n;
list_for_each_entry_safe(c, n, l, list) {
list_del(&c->list);
q_release_element(c);
}
free(l); // q_new function has malloced it
}
```
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_element = malloc(sizeof(element_t)); // new head element
if(!new_element) // If allocate failed
return false;
size_t len = strlen(s) + 1; // plus 1 for `\0`
new_element->value = malloc(len * sizeof(char));
if (!new_element->value) { // If allocate failed
free(new_element);
return false;
}
memcpy(new_element->value, s, len);
list_add(&new_element->list, head);
return true;
}
```
:::warning
能否避免呼叫 `memcpy` 並精簡程式碼？
:notes: jserv
>改為利用 `strdup`
:::
發現在 `harness.c` 中已有定義 `strdup`（`test_strdup`），此函式回傳輸入 string `s` 的指標，並回傳一個具有同樣內容的指標，即複製字串。
透過此函式可以直接取代掉原實作方法中的計算長度、分配空間、記憶體複製操作
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_element = malloc(sizeof(element_t)); // new head element
if (!new_element) // allocated failed
return false;
- size_t len = strlen(s) + 1; // plus 1 for `\0`
- new_element->value = malloc(len * sizeof(char));
+ new_element->value = strdup(s);
if (!new_element->value) { // allocated failed
free(new_element);
return false;
}
- memcpy(new_element->value, s, len);
list_add(&new_element->list, head);
return true;
}
```
### q_insert_tail
和 `q_insert_head` 思路相同, 僅修改 `head` 和 `tail` 的差別
:::warning
既然 `q_insert_tail` 和 `q_insert_head` 存在相似的流程，能否用 `q_insert_head` 來實作 `q_insert_tail` 呢？
:notes: jserv
>新增相關敘述
:::
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element = malloc(sizeof(element_t)); // new tail element
if(!new_element) // If allocate failed
return false;
size_t len = strlen(s) + 1; // plus 1 for `\0`
new_element->value = malloc(len * sizeof(char));
if(!new_element->value) { // If allocate failed
free(new_element);
return false;
}
memcpy(new_element->value, s, len);
list_add_tail(&new_element->list, head);
return true;
}
```
`q_insert_head` 以及 `q_insert_tail` 差異僅在新增節點於給定 `head` 的後一個位置 (`next` 所指方向)，以及前一個位置 (`prev` 所指方向)，故可以透過 `q_insert_head` 來實作 `q_insert_tail`
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
return q_insert_head(head->prev, s);
}
```
翻譯成白話文的意思就是，在 `head` 的前面插入節點等效於在 `head` 的前一個節點的後面插入節點。
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head)
return NULL;
sp = malloc(bufsize);
element_t *rm_element = container_of(head->next, element_t, list);
strncpy(sp, rm_element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return rm_element;
}
```
- `container_of` 這個巨集透過給定成員 (member) 的記憶體地址、結構體的型態，以及成員的名稱, 傳回該結構體的起始地址
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
上述雖然可以成功 remove head, 但是產生錯誤訊息
```
ERROR: Failed to store removed value
```
查看 `qtest.c` 中 `do_remove` 的實作
```c
removes[string_length + STRINGPAD] = '\0';
if (removes[0] == '\0') {
report(1, "ERROR: Failed to store removed value");
ok = false;
}
```
:::warning
implementation 應翻譯為「實作」，注意[「作」和「做」的落差](https://blog.udn.com/mobile/tsengche/3054517)」。
參見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 的 "implement" 項目。
:notes: jserv
> 已修正，謝謝老師
:::
- `removes[0] = '\0'` 會報此錯誤, 且 `removes` 在 `qtest.c` 已經 `malloc` 如果在 `q_remove` 中再次 `malloc` 一次的話 sp 的地址會被覆蓋掉, 即原先 `removes` 的地址其實並沒有存東西, 所以這裡的 `sp` 不該 `malloc`
在佇列為空時繼續使用命令 `rh` 會造成 segmentation fault, 當佇列為空時僅有 `Head` 一個點, 沒辦法通過 `container_of` 找到對應節點
```
l = []
cmd> rh
Warning: Calling remove head on empty queue
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
```
加入 `list_empty` 來判斷該鏈結串列是不是 empty 以及外部 `removes` 是否有 `malloc` 成功
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *rm_element = container_of(head->next, element_t, list);
if (sp) {
strncpy(sp, rm_element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->next);
return rm_element;
}
```
這裡的 `container_of` 可以用 `list_first_entry` 巨集代替, 增加程式可讀性 (defined in `list.h`)
```c
#define list_entry(node, type, member) container_of(node, type, member)
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
- 接下來的 q_remove_tail 也是一樣可以用 `list_last_entry` 取代 `container_of`
### q_remove_tail
和 `q_remove_head` 思路相同, 僅修改 `head` 和 `tail` 的差別
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head))
return NULL;
element_t *rm_element = list_last_entry(head, element_t, list);
if(sp) {
strncpy(sp, rm_element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->prev);
return rm_element;
}
```
### q_size
走訪整個鏈結串列以計算長度
```c
int q_size(struct list_head *head)
{
if(!head)
return 0;
int cnt = 0;
struct list_head *n = head->next; // next list node
while (n != head) {
n = n->next;
cnt++;
}
return cnt;
}
```
:::warning
TODO: 善用既有的巨集，撰寫出更精簡的程式碼
:notes: jserv
> 用 `list_for_each` 取代現有 for loop
:::
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int cnt = 0;
struct list_head *n;
list_for_each (n, head)
cnt++;
return cnt;
}
```
其中 `list_for_ecah` 定義為
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
### q_delete_mid
:::warning
本例為 circular doubly-linked list，你應該實作更少記憶體操作的程式碼。
:notes: jserv
:::
:::info
原先版本使用快慢指標，快指標會走訪整個 list 一圈，慢指標會走一半的 list 找到中間點，總共會走大概 1.5 倍長度的 list，參考 [freshLiver](https://hackmd.io/@freshLiver/2022q1-hw1#%E9%87%9D%E5%B0%8D%E4%BD%87%E5%88%97%E7%9A%84%E6%93%8D%E4%BD%9C) 過往作業使用到兩個指標前後從佇列頭尾迭代，透過交會點/即將交會點來判斷佇列中間點
:::
- 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **indir;
indir = &head;
for(struct list_head *p = head->prev; (*indir)->next != p && (*indir) != p; ) {
indir = &(*indir)->next;
p = p->prev;
}
struct list_head *temp = (*indir)->next;
list_del(temp);
q_release_element(list_entry(temp, element_t, list));
return true;
}
```
在這邊使用 indirect pointer 看起來沒有特別的優勢，反而在過程多了 `*indir` 這一個記憶體操作
:::warning
對照編譯器輸出的組合語言和 `perf` 來確認你的觀點，否則這個「看來」流於武斷。注意編譯器最佳化的影響
:notes: jserv
> 初步分析以補充，待補如果設定編譯器為 `-O0` 後的組合語言差異
:::
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *n = head->next;
for(struct list_head *p = head->prev; n->next != p && n != p; ) {
n = n->next;
p = p->prev;
}
list_del(n);
q_release_element(list_entry(n, element_t, list));
return true;
}
```
且如此運算過後 `n` 會正好指向要移除之節點，不需要在額外設定指向要刪除的節點進行操作，
#### 編譯器輸出的組合語言
用 `objdump -d queue.o` 查看編譯器輸出的組合語言
```c
00000000000002d3 <q_delete_mid>:
2d3: f3 0f 1e fa endbr64
2d7: 48 85 ff test %rdi,%rdi
2da: 74 52 je 32e <q_delete_mid+0x5b>
2dc: 53 push %rbx
2dd: 48 8b 5f 08 mov 0x8(%rdi),%rbx
2e1: 48 39 df cmp %rbx,%rdi
2e4: 74 4e je 334 <q_delete_mid+0x61>
2e6: 48 8b 17 mov (%rdi),%rdx
2e9: 48 8b 43 08 mov 0x8(%rbx),%rax
2ed: 48 39 d3 cmp %rdx,%rbx
2f0: 74 19 je 30b <q_delete_mid+0x38>
2f2: 48 39 c2 cmp %rax,%rdx
2f5: 74 14 je 30b <q_delete_mid+0x38>
2f7: 48 8b 12 mov (%rdx),%rdx
2fa: 48 89 c3 mov %rax,%rbx
2fd: 48 8b 40 08 mov 0x8(%rax),%rax
301: 48 39 da cmp %rbx,%rdx
304: 74 05 je 30b <q_delete_mid+0x38>
306: 48 39 d0 cmp %rdx,%rax
309: 75 ec jne 2f7 <q_delete_mid+0x24>
30b: 48 8b 13 mov (%rbx),%rdx
30e: 48 89 10 mov %rdx,(%rax)
311: 48 89 42 08 mov %rax,0x8(%rdx)
315: 48 8b 7b f8 mov -0x8(%rbx),%rdi
319: e8 00 00 00 00 call 31e <q_delete_mid+0x4b>
31e: 48 8d 7b f8 lea -0x8(%rbx),%rdi
322: e8 00 00 00 00 call 327 <q_delete_mid+0x54>
327: b8 01 00 00 00 mov $0x1,%eax
32c: 5b pop %rbx
32d: c3 ret
32e: b8 00 00 00 00 mov $0x0,%eax
333: c3 ret
334: b8 00 00 00 00 mov $0x0,%eax
339: eb f1 jmp 32c <q_delete_mid+0x59>
```
結果上述的兩個版本編譯器編出來的組合語言竟然是一樣的，查看 `makefile` 發現編譯器優化等級設定在 `-O1`，如果禁用優化改成 `-O0` 編譯出來的組合語言才會有差
#### 使用 [perf](https://en.wikipedia.org/wiki/Perf_(Linux)) 確認上述猜測
- 參考 [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial#%E8%83%8C%E6%99%AF%E7%9F%A5%E8%AD%98)，記得先參考[安裝](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial#%E5%AE%89%E8%A3%9D)章節將權限打開
- 雖然上面已經看到經過編譯器優化後的組合語言相同，可想而知效能一定一樣。
```shell
sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"
```
定義一個測試案例 `trace-demid.cmd`
```shell
option fail 0
option malloc 0
new
ih RAND 500000
time
dm
time
```
輸入命令
```shell
perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-demid.cmd
```
`perf stat` 可以測量單個程序運行時間內的性能係數
- `--repeat 5` 重複 5 次
- `-e` 後面接著 [PMU](https://en.wikipedia.org/wiki/Hardware_performance_counter) 的事件，可以用 `perf list` 查看所有事件
結果如下
```
Performance counter stats for './qtest -f traces/trace-demid.cmd' (5 runs):
1530,3333 cache-misses # 90.230 % of all cache refs ( +- 0.34% )
1658,7721 cache-references ( +- 1.66% )
16,8910,5300 instructions # 0.83 insn per cycle ( +- 0.01% )
19,7202,0142 cycles ( +- 2.88% )
0.5664 +- 0.0189 seconds time elapsed ( +- 3.34% )
```
:::spoiler Iteration process
以 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 舉例
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1", rank=2]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
p [shape=plaintext;label="p"]
p->node7[constraint="false"]
n [shape=plaintext;label="n"]
n->node1[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
p [shape=plaintext;label="p"]
p->node6[constraint="false"]
n [shape=plaintext;label="n"]
n->node2[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
p [shape=plaintext;label="p"]
p->node5[constraint="false"]
n [shape=plaintext;label="n"]
n->node3[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7", color="red"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
p [shape=plaintext;label="p"]
p->node4[constraint="false"]
n [shape=plaintext;label="n"]
n->node4[constraint="false", color=red]
}
```
:::
:::spoiler Old version
利用快慢指標 ([Floyd's tortoise and hare](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare)) 找中間點, 因為在本次作業中已經確保快慢指標 (或龜兔指標) 已經都在環中, 所以設定快指標移動速度為慢指標兩倍, 當快指標繞完一圈時慢指標指向中間點(有 `Head` 節點則差一個節點)
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **indir;
indir = &head;
struct list_head *fast = head;
while(!(fast->next == head || fast->next->next == head)) {
indir = &(*indir)->next;
fast = fast->next->next;
}
q_release_element(list_entry((*indir)->next, element_t, list));
(*indir)->next = (*indir)->next->next;
return true;
}
```
```
cmd> dm
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
Aborted (core dumped)
```
- 這裡如果直接把 `(*indir)->next` 直接 release 掉的話會造成 `(*indir)->next` 指向 `NULL` 這不是我們想要的, 這裡我先用 `list_del((*indir)->next)` 將 `(*indir)` 和 `(*indir)->next->next` linked 起來，在將原先的 `(*indir)->next` release 掉
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **indir;
indir = &head;
struct list_head *fast = head;
while (fast->next!= head && fast->next->next != head) {
indir = &(*indir)->next;
fast = fast->next->next;
}
struct list_head* temp = (*indir)->next;
list_del((*indir)->next);
q_release_element(list_entry(temp, element_t, list));
return true;
}
```
**Iteration Process**
```graphviz
digraph del_mid {
node [shape=box]
rankdir=LR
// backbone
node1 -> node2 -> node3 -> node4
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->head
fast [shape=plaintext;label="fast"]
fast->node1
}
```
```graphviz
digraph del_mid {
node [shape=box]
rankdir=LR
// backbone
node1 -> node2 -> node3 -> node4
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->node1
fast [shape=plaintext;label="fast"]
fast->node3
}
```
以 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 實際演算一次
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1", rank=2]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->head[constraint="false"]
fast [shape=plaintext;label="fast"]
fast->node1[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->node1[constraint="false"]
fast [shape=plaintext;label="fast"]
fast->node3[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->node2[constraint="false"]
fast [shape=plaintext;label="fast"]
fast->node5[constraint="false"]
}
```
```graphviz
digraph del_mid {
node [shape=circle]
rankdir=LR
node1[label="1"]
node2[label="3"]
node3[label="4"]
node4[label="7", color="red"]
node5[label="1"]
node6[label="2"]
node7[label="6"]
// backbone
node1 -> node2 -> node3 -> node4 ->node5->node6->node7
head->node1
// mark
indir [shape=plaintext;label="indir"]
indir->node3[constraint="false", color="red"]
fast [shape=plaintext;label="fast"]
fast->node7[constraint="false"]
}
```
- remove `(*indir)->next` 節點
:::
### q_delete_dup
首先思考使用 `list_for_each_entry_safe` 實作，根據描述
>list_for_each_entry_safe - Iterate over list entries and allow deletes
會走訪整個 list 的 entries (`typeof(entry)`) 並允許刪除當前的節點
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *c, *n; // current and next element
bool is_dup = false;
list_for_each_entry_safe (c, n, head,
list) { // current node (iterator) is allowed to
// be removed from the list.
if (c->list.next != head &&
strcmp(c->value, n->value) == 0) // duplicate string detection
{
list_del(&c->list); // delete node
q_release_element(c);
is_dup = true;
} else if (is_dup) {
list_del(&c->list);
q_release_element(c);
is_dup = false;
}
}
return true;
}
```
執行 `list_for_each_entry_safe` 可以走訪整個 list 但是需要注意在走訪完時 `n` 會指向 `head`，且 `head` 是無法透過 `container_of` 找到節點的，因為它沒有嵌入到結構體中，這時如果對 `n` 取 `contain_of` 會拿到 `NULL` 如果再做取值 `n->value` 會<s>報錯</s> 成為無效的記憶體操作。
> [invalid page fault](https://en.wikipedia.org/wiki/Page_fault)
故在第一個 `if` 條件使用 `c->list.next != head` 來判斷是否來到最後的節點 (雖然 `list_for_each_entry_safe` 本身就有做)，避免在 `strcmp(c->value, n->value) == 0` 時 `n->value` 對 `NULL` 指標取值。
:::warning
TODO: 減少記憶體操作的數量
:notes: jserv
:::
### q_swap
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *n = head->next;
while (n != head && n->next != head) {
struct list_head *t = n;
list_move(n, t->next);
n = n->next;
}
}
```
交換佇列中鄰近的節點，將兩個鄰近的節點中的第一個節點移動至以令一個當作 `head` 節點的開頭 (也就是說會放在另一個節點的 `next`)，移動節點可分為兩步驟(刪除以及插入)，對應到 `list_move` 中定義的兩步驟 `list_del` 以及 `list_add`
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *n, *s, *t;
list_for_each_safe (n, s, head) {
t = n->next;
n->next = n->prev;
n->prev = t;
}
t = head->next;
head->next = head->prev;
head->prev = t;
}
```
一開始原本是考慮到沒有刪除節點的問題所以使用 `list_for_each` 來走訪 list ，但是在 reverse 的過程中的 `node` 會把 `next` 和 `prev` 做交換，會讓原本定義的巨集出現錯誤，導致無法順利走訪。
改用 `list_for_each_safe`
```c
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
在迭代過程中 `safe` 指標會始終維持在 `node` 的下一個節點(沒有 reverse 的)，使用 `node = safe` 以及 `safe = node->next` 確保迭代過程 `node` 不會往回走。
### q_reverseK
此<s>函數</s> 函式需要將 list 中的 k 個節點進行 reverse，直覺來說會利用到上方已經實作完成的 `q_reverse`，為此在使用時符合 `q_reverse` 參數需求，傳入該 list 的 `head`，故使用 `list_cut_position` 對特定長度的 list 進行分割，並在分割下來的 list 頭部新增 `iter` 作為該 list 的 `head` 供 `q_reverse` 使用
:::warning
注意用語，參見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)。上述 "reverse" 應有對應的漢語描述
:notes: jserv
:::
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
struct list_head *n, *s, iter, *tmp_head = head;
int i = 0;
INIT_LIST_HEAD(&iter);
list_for_each_safe (n, s, head) {
i++;
if (i == k) {
list_cut_position(&iter, tmp_head, n);
q_reverse(&iter);
list_splice_init(&iter, tmp_head);
i = 0;
tmp_head = s->prev;
}
}
}
```
- 參考 [25077667](https://hackmd.io/@25077667/lab0-2023#2023q1-Homework1-lab0)，及 [komark06](https://hackmd.io/@komark06/SyCUIEYpj)
### q_sort
實作 merge sort，先將環狀結構斷開後，傳入 `head->next` 進去 `merge_recur`
**merge_two_list**
- 結合兩個「已排序」的鏈結串列
```c
struct list_head *merge_two_list(struct list_head *left,
struct list_head *right)
{
struct list_head head;
struct list_head *h = &head;
if (!left && !right) {
return NULL;
}
while (left && right) {
if (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0) {
h->next = left;
left = left->next;
h = h->next;
} else {
h->next = right;
right = right->next;
h = h->next;
}
}
// after merge, there are still one node still not connect yet
if (left) {
h->next = left;
} else if (right) {
h->next = right;
}
return head.next;
}
```
:::warning
TODO: 撰寫更精簡的程式碼，縮減分支
:notes: jserv
:::
**merge_recur**
- 利用快慢指標將 list 的中間節點找出來並遞迴處理
:::warning
避免使用含糊的「中點」，應有對應的定義及說明。
:notes: jserv
:::
```c
struct list_head *merge_recur(struct list_head *head)
{
if (!head->next)
return head;
struct list_head *slow = head;
// split list
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
struct list_head *mid = slow->next; // the start node of right part
slow->next = NULL;
struct list_head *left = merge_recur(head);
struct list_head *right = merge_recur(mid);
return merge_two_list(left, right);
}
```
**q_sort**
- 傳入 `head->next` 進行 merge sort 可以保留原本的 `head` ，在排序過後在進行 `prev` 以及 `circular` 的修補
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
// disconnect the circular structure
head->prev->next = NULL;
head->next = merge_recur(head->next);
// reconnect the list (prev and circular)
struct list_head *c = head, *n = head->next;
while (n) {
n->prev = c;
c = n;
n = n->next;
}
c->next = head;
head->prev = c;
}
```
### q_descend
此函數會將**右邊存在有嚴格大於的節點的節點**給移除 (remove)
```c
int q_descend(struct list_head *head)
{
struct list_head *c = head->prev, *n = c->prev;
while (n != head) {
if (strcmp(list_entry(n, element_t, list)->value,
list_entry(c, element_t, list)->value) < 0) {
list_del(n);
} else {
c = n;
}
n = n->prev;
}
return q_size(head);
}
```
如果順著 list 方向進行走訪 (以 `next` 指標迭代)，無法確定迭代的過程中會不會遇到嚴格大於的節點(如果遇到則走放過的節點都要移除)，故這邊我以反方向進行迭代(以 `prev` 指標迭代)，找尋下一個節點值只要和當前節點做比較，若下一個節點小於當前節點的話則移除。
執行測試案例的時候發現 `trace-06` 過不了，發現是 `descend` 後被消除的 block 沒有被清掉，一開始看到函式敘述用 `remove` 時以為不用刪除
> Remove every node which has a node with a strictly greater value anywhere to the right side of it
但它也沒有存到像 `q_remove` 系列的 `sp` 中，由 `q_test` 負責刪除，故修正在函式內進行記憶體釋放
```c
int q_descend(struct list_head *head)
{
if (!head)
return 0;
struct list_head *c = head->prev;
element_t *c_ele = list_entry(c, element_t, list);
while (c_ele->list.prev != head) {
element_t *n_ele = list_entry(c_ele->list.prev, element_t, list);
if (strcmp(n_ele->value, c_ele->value) < 0) {
list_del(&n_ele->list);
q_release_element(n_ele);
} else {
c_ele = n_ele;
}
}
return q_size(head);
}
```
### q_merge
先看一下 `do_merge` 要我們做什麼
```c
if (current && exception_setup(true))
len = q_merge(&chain.head);
exception_cancel();
```
- 輸入 chain head 回傳長度
且在 `do_merge` 中會負責把被 merge 掉的 queue 空間 `free` 掉，接著再檢查是否真的有按照 ascending order 來排序
```c
int q_merge(struct list_head *head)
{
if (!head)
return 0;
queue_contex_t *c_cont;
queue_contex_t *n_cont;
struct list_head *sorted = NULL;
list_for_each_entry_safe (c_cont, n_cont, head, chain) { // iterate context
c_cont->q->prev->next = NULL;
c_cont->q->prev = NULL;
sorted = merge_two_list(sorted, c_cont->q->next);
INIT_LIST_HEAD(c_cont->q); // reconnect the lists which are moved and
// merged to "sorted" list;
}
LIST_HEAD(tmp);
struct list_head *t = &tmp;
t->next = sorted;
struct list_head *c = t;
while (sorted) {
sorted->prev = c;
c = sorted;
sorted = sorted->next;
}
c->next = t;
t->prev = c;
int size = q_size(t); // store size before splice to main queue
list_splice(t, list_first_entry(head, queue_contex_t, chain)->q);
return size;
}
```
實作過程中利用在 merge sort 已經寫好的 `merge_two_list` ，不過須注意的是這邊我的 `merge_two_list` 傳入值為兩個**沒有 `head` 的 list**，也就是每一個節點其對應到的 element 都有數值，且不是環狀 linked list ，實做過程將兩個已經 sorted 好的 list 傳入 function 並回傳將兩個 list merged 完成的 list 的第一個節點地址，此時可以把 merged 好的 list 交給主要的 context (迭代中的) 的 list head (其 element 沒有值的那個)
完成之後會有一個 merged 好的 list，接著將環狀的結構復原 (`prev`被各個佇列的 merge 打亂了，僅有 `next` 為正常順序)
最後把處理好的 list 透過 `list_splice` 交給主要 chain `head` 所屬的 `element`
---
## 研讀論文並改進 dudect
- 較細節研讀筆記放在[另外的筆記](https://hackmd.io/@chiangkd/dudect-study)
此節根據〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉修正測試案例 `trace-17-complexity` 檢測程式碼不會常數執行時間的問題，在 `trace-17-complexity` 測試案例中會將 `option simulation` 打開，並執行 insert head (`ih`)、insert tail (`it`)、remove head (`rh`)、remove tail (`rt`) 指令，而在 `qtest.c` 中相對應的 `do_it`、`do_ih`、`do_remove` 都有對應 `simutlation` 開啟狀態下的行為。
### 解釋 simulation 模式
>下述程式碼已在 [#127](https://github.com/sysprog21/lab0-c/commit/bdcfae37505e671c5ba028b8d95fe0e7e40b2afc) 更新
首先查看 `do_ih`
```c
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok = is_insert_head_const();
if (!ok) {
report(1,
"ERROR: Probably not constant time or wrong implementation");
return false;
}
report(1, "Probably constant time");
return ok;
}
```
在 `simulation` 下，對應到三種結果
- 不需要 argument
- 執行測試，且 probably not constant time
- 執行測試，且 probably constant time
是否為 constant time 由 `is_insert_head_const()` 函式回傳判斷，
`is_##x##_const` 系列函式由前置處理器 [concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html) 處理，其中 `insert_head`, `insert_tail`, `remove_head`, `remove_tail` 也都是由前置處理器處理。
:::warning
這技巧稱為 [X macro](https://en.wikipedia.org/wiki/X_Macro)
:notes: jserv
>Got it! Thanks
:::
`constant.c` 中的 `measure` 函式負責判斷 `ih`、`it`、`rh`、`rt` 是否有正常運作 (透過 size 有沒有隨著 insert 以及 remove 正常的變動)
`fixture.c` 中的 `report` 函式則負責測量是否為 constant time
```c
/* Definitely not constant time */
if (max_t > t_threshold_bananas)
return false;
/* Probably not constant time. */
if (max_t > t_threshold_moderate)
return false;
/* For the moment, maybe constant time. */
return true;
```
此處流程可以參照 [preparaz/dudect](https://github.com/oreparaz/dudect)，中的 **Checking your code for constant time** 節
>`dudect` is distributed as a single-file library for easy building. Steps:
>- Copy `dudect.h` to your include directories
>- Add #include "`dudect.h`" from your source files.
>- See [this minimal example](https://github.com/oreparaz/dudect/blob/master/examples/simple/example.c) for a fully contained example. You'll need to write the following functions:
> - `do_one_computation()`,
> - `prepare_inputs()` and
> - call `dudect_main()` from your main function
### Student's t-distribution 及程式實作原理
實作放在 `ttest.c` 相關函式，按照公式計算 `t` 值
$$
t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}}
$$
其中 `t` 值越小代表兩組分佈越接近，注意這裡的 $\bar{X_i}$ 指的是 [sample mean](https://en.wikipedia.org/wiki/Sample_mean_and_covariance)
首先在進入定義全域變數 `t_constext *t`，結構體定義為
```c
typedef struct {
double mean[2];
double m2[2];
double n[2];
} t_context_t;
```
在每一次測試時 (預設測試 10 次 (`TEST_TRIES=10`))，首先呼叫 `init_once()`，在 `init_once()` 中會將 `t` 的各個元素初始化。
接著根據不同的 `mode` (不同的 case 有不同的 mode number) ，進入 `doit` ，在 `prepare_input` 之後進入 `measure` 函式， `measure` 函式根據 `q_size` 判斷 `ih`, `it`, `rh`, `rt` 等操作有沒有順利進行，也計算函式執行時間，以 `insert_head` 為例:
```c
before_ticks[i] = cpucycles();
dut_insert_head(s, 1);
after_ticks[i] = cpucycles();
```
函式若正常執行回傳 `true` 給 `ret`，且更新了 `before_ticks` 以及 `after_ticks` 交給 `differentiate` 進行計算 `exec_time[i] = after_ticks[i] - before_ticks[i]` ，其中 `i` 為每次 `test` 進行的 measurement 次數，預設為 150 次。
接著將計算出的 `exec_time` 及 `classes` 送入 `updata_statistics` ，函式內透過 `t_push` 進行 t-test ，`t_push` 需要的參數包含
- `t_context` 本體 `t`
- 計算出的 `difference` 也就是對應的 `exec_times[i]`
- 對應的 `classes[i]`
在 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 原始碼中有提到可以參考《The Art of Computer Programming, Volume 2 : Seminumerical Algorithms》 (待研究)，看起來是透過取新的 execution time 與當前平均值的差為變化量 (`delta`) 而新的平均值就會是舊平均值加上變化量的平均值 (`delta/n`)，可以避免每次都將所有數值相加取平均的過程，而 `m2` 為變異數尚未平均的值，在後續 `t_compute` 會使用到，每次的 `m2` 更新為舊 `m2` 加上 `delta` 乘上這次的 execution time 與更新過後的平均值的差。
在 `ttest.c` 中
```c
void t_push(t_context_t *ctx, double x, uint8_t class)
{
assert(class == 0 || class == 1);
ctx->n[class]++;
double delta = x - ctx->mean[class];
ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}
```
之後進入 `report` 函式透過 `t_compute` 及取絕對值的 `fabs` 計算 `max_t`， `max_t` 數值就會根據 `t_threshold_xx` 的值來判斷程式是否 constant time，這裡程式的實作如同上述給定的公式
$$
t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}}
$$
再回傳 `t` 值之後會在透過 `fabs` 取絕對值。
### 修改以達成 constant time
當前 `lab0-c` 並未實作 percentile 功能，也就是沒有將測量誤差給 crop 掉，將 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的 percentile 引入後即可順利通過 `trace-17-complexity`
[dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的結構體定義和 `lab0-c` 有一些不一樣，原專案中使用 `dudect_state_t` 將 `ttest_ctx_t` (等效 `lab0-c` 中的 `t_context_t`) 及執行時間、輸入資料、等必要資訊定義在一起，但在 `lab0-c` 都是拆開的，在這邊引入 `percentile` 至 `t_context_t` 中
```diff
typedef struct {
double mean[2];
double m2[2];
double n[2];
+ int64_t *percentiles;
} t_context_t;
```
詳細改動在 [commit](https://github.com/chiangkd/lab0-c/commit/d014538e300e54d5e21e586f23e3e10a561269ee) 中。
---
## 研讀 list_sort.c 並引入專案
- 研讀筆記放在[這裡](https://hackmd.io/erWlfVMfQqyUe9JVbOLlBA?view#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84-list_sortc)
將 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 引入專案，並新增 `makefile` 的 dependency 以及把無關的 include header 移除
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
- linenoise.o web.o
+ linenoise.o web.o list_sort.o
```
`list_sort.h`
```diff
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H
-#include <linux/types.h>
+#include "stdint.h"
+#include "list.h"
-struct list_head;
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif
```
```diff
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;
- u8 count = 0;
+ uint8_t count = 0;
...
}
```
編譯後發現 `likely` 以及 `unlikely` 沒有定義，參考 [linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)，其中的 `__builtin_expect()` 是 gcc 的 built-in function，用來將 branch 的相關資訊提供給 compiler，讓其對程式碼改變分支的順序
- 參考 [6.59 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
- 參考連結 [Linux Kernel 慢慢學: likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/)
在 `list_sort` 的 prototype 中需要三個參數，`priv`, `head`，以及 `cmp`
- `head` 為我們要輸入的 queue 的 `head`
- `cmp` 為 compare function，作為函式指標傳入，根據註解
>The comparison function @cmp must return > 0 if @a should sort after
@b (“@a > @b” if you want an ascending sort), and <= 0 if @a should sort before @b or their original order should be preserved. It is always called with the element that came first in the input in @a, and list_sort is a stable sort, so it is not necessary to distinguish the @a < @b and @a == @b cases.
1. `cmp` return > 0 (a 排在 b 的後面)
2. `cmp` return <=0 (a 排在 b 的前面或保留原本排列)
3. `list_sort` 是一個 [stable sort](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)，故不用區分小於 0 或等於 0
不確定這邊的 `priv` 是要幹麻的，不過根據宣告 `priv` 可以為 `NULL`
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
參考 `do_sort` 新增 `do_lsort` 代表 linux 核心原始程式碼的 `list_sort` 並定義 `cmp`
```c
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *a_ele = list_entry(a, element_t, list); // get mother element
element_t *b_ele = list_entry(b, element_t, list);
return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1;
}
bool do_lsort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
int cnt = 0;
if (!current || !current->q)
report(3, "Warning: Calling sort on null queue");
else
cnt = q_size(current->q);
error_check();
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (current && exception_setup(true))
list_sort(NULL, current->q, cmp);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
if (current && current->size) {
for (struct list_head *cur_l = current->q->next;
cur_l != current->q && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
q_show(3);
return ok && !error_check();
}
```
**提供新命令** `lsort`
在 `qtest.c` 的 `console_init()` 中新增命令
```c
ADD_COMMAND(lsort, "Sort queue in ascending order provided by linux kernel", "");
```
結果呈現
```
cmd> new
l = []
cmd> ih RAND 10
l = [xajlhbj zblfv veqfmhw kuwzmcl qzzsyenvi xfsgs bocazny saskszhgd xqjrd igiecysjj]
cmd> lsort
l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv]
cmd> shuffle
l = [bocazny kuwzmcl xfsgs igiecysjj veqfmhw saskszhgd zblfv qzzsyenvi xajlhbj xqjrd]
cmd> sort
l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv]
```
`git commit` 的時候會被擋下來
```shell
list_sort.c:14:23: style: Variable 'head' is not assigned a value. [unassignedVariable]
struct list_head *head, **tail = &head;
^
```
考慮到不要修正 `list_sort.c` 的原始碼，用 `cppcheck-suppress` 跨過去
```c
// cppcheck-suppress unassignedVariable
struct list_head *head, **tail = &head;
```
### 效能比較
使用 `perf` 進行效能比較，參考 [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
```shell
perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd
```
定義測資
```shell
option fail 0
option malloc 0
new
ih RAND 500000
time
<sort>
time
```
- `<sort>` 可以為原先 `qtest.c` 中撰寫的 `do_sort` 或是引入的 `do_lsort`，透過 `time` 命令獲取 `sort` 執行的時間，設定 `--repeat 5` 重複五次，並透過 `perf` 拿到 `instructions` 以及 `cycles` 的數據
**自行撰寫的 `q_sort`**
| **q_sort** | time |
| ---------- | ----- |
| 1 | 0.487 |
| 2 | 0.477 |
| 3 | 0.488 |
| 4 | 0.486 |
| 5 | 0.529 |
| Instructions | Cycles |
| ------------ | ------------ |
| 20,9111,6747 | 36,2842,8338 |
**list_sort**
| **q_sort** | time |
| ---------- | ----- |
| 1 | 0.411 |
| 2 | 0.417 |
| 3 | 0.423 |
| 4 | 0.501 |
| 5 | 0.460 |
| Instructions | Cycles |
| ------------ | ------------ |
| 21,4157,1467 | 34,1147,9158 |
雖然每次執行這個測試案例時，Instructions 和 Cycles 的數量會些微變動，但整理來看
- Linux kernel 的 `list_sort` 指令較多，Cycles 較少
---
## 在 qtest 提供新的命令 shuffle
- [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
int size = q_size(head);
// shuffle
for (int i = 0; i < size;) { // not iterate i , iterate size
struct list_head *start = head->next;
int rand_idx = rand() % size; // random number in range 0~ (size-1)
for (int j = 0; j < rand_idx; j++) {
start = start->next;
}
list_del(start);
list_add_tail(start, head);
size--;
}
return;
}
```
選取一個隨機數，將該位置元素取出後放到尾端，舉例來說
| 隨機範圍 | 隨機數 | 原始數據 | 結果 |
| -------- | ------ | -------- | ---- |
| | | 12345 | |
| 1~5 | 4 | 1235 | 4 |
| 1~4 | 3 | 125 | 34 |
| 1~3 | 1 | 25 | 134 |
| 1~2 | 1 | 5 | 2134 |
### 在命令直譯器中新增命令 shuffle
在 `qtest.c` 中的 `console_init()` 新增 `shuffle` 指令
```c
ADD_COMMAND(shuffle, "Shuffle queue", "");
```
查看其巨集定義
```c
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
此巨集會將 `cmd` 命令的行為去透過巨集展開 `do_##cmd` 去呼叫對應 handler ，如其他命令 `new` 會去呼叫 `do_new` 函式，故在此定義 `do_shuffle` 函式來 handle `shuffle` 命令
```c
void q_shuffle(struct list_head *head);
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no argu,emts", argv[0]); //return function error
return false;
}
if (!current || !current->q)
report(3, "Warning: Calling shuffle on null queue");
error_check();
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
參考其他函式 handler 的寫法，有些函式內有定義 `bool ok`，有些則無，觀察到 `ok` 都用在佇列長度有更改或者需要判斷佇列是否為空的情形，所以 `reverse`，`swap` 中不需要 `ok` 來處理佇列長度改變，且對應的 `do_reverse` 以及 `do_swap` 中都有相應的 `if(!head)` 來處理空佇列的問題，綜上所述 `do_shuffle` 不需要有 `bool ok` 定義。
```shell
[!] You are not allowed to change the header file queue.h or list.h
```
- 無法將 `q_shuffle` 宣告加在 `queue.h` 所以就放在 `do_shuffle` 的上面
```shell
cmd> new
l = []
cmd> it a
l = [a]
cmd> it b
l = [a b]
cmd> it c
l = [a b c]
cmd> it d
l = [a b c d]
cmd> it e
l = [a b c d e]
cmd> shuffle
l = [a d b c e]
cmd> shuffle
l = [c b d e a]
cmd> shuffle
l = [c e a b d]
```
---
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
首先嘗試用 `valgrind` 跑跑看 `trace-01-ops.cmd` 測資
```shell
valgrind ./qtest -f ./traces/trace-01-ops.cmd
```
```shell
==10230== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==10230== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10230== by 0x10CE33: do_new (qtest.c:147)
==10230== by 0x10E099: interpret_cmda (console.c:181)
==10230== by 0x10E64E: interpret_cmd (console.c:201)
==10230== by 0x10EA4F: cmd_select (console.c:610)
==10230== by 0x10F33B: run_console (console.c:705)
==10230== by 0x10D48B: main (qtest.c:1307)
==10230==
==10230== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==10230== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10230== by 0x10F3AF: test_malloc (harness.c:133)
==10230== by 0x10F7B4: q_new (queue.c:17)
==10230== by 0x10CE6C: do_new (qtest.c:151)
==10230== by 0x10E099: interpret_cmda (console.c:181)
==10230== by 0x10E64E: interpret_cmd (console.c:201)
==10230== by 0x10EA4F: cmd_select (console.c:610)
==10230== by 0x10F33B: run_console (console.c:705)
==10230== by 0x10D48B: main (qtest.c:1307)
```
依據[網站](https://valgrind.org/docs/manual/faq.html#faq.deflost)及作業講解敘述，Valgrind 有 5 種 memory leak
- definitely lost: 真的 memory leak
- indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
- possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
- still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數，即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。
這裡發生的 still reachable 在 `do_new` 及 `test_malloc` 中，但是如果直接執行，`qtest` 且逐行輸入命令不會有這個問題。
沒什麼頭緒，參考 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#Valgrind-%E8%88%87-Address-Sanitizer-%E8%A8%98%E6%86%B6%E9%AB%94%E6%AA%A2%E6%9F%A5)，上述問題已在 [#121](https://github.com/sysprog21/lab0-c/commit/c7d31497c5845bc0af308bf4601e7636c18f0153), [#122](https://github.com/sysprog21/lab0-c/commit/9dcf3ed44617b2d530c4365dbc60c4437e38e622) 被修正
:::warning
TODO: 搞懂別人做了什麼
:::
## 透過 Massif 視覺化 "simulation" 過程中的記憶體使用量
選用 `trace-17-complexity.cmd`
先透過 Valgrind 產生 massif 檔案
```
valgrind --tool=massif ./qtest -f traces/trace-eg.cmd
```
再使用 `massif-visualizer` 查看
```
massif-visualizer ./massif.out.<number>
```
- 這邊參考 [alanjiang85](https://hackmd.io/@alanjian85/lab0-2023#%E9%80%8F%E9%81%8E-Massif-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%BF%E7%94%A8%E9%87%8F) 的說明改用 `trace-eg.cmd` 進行分析
- >alanjiang85: 要注意的是，挑選適當的測試資料時要避免效能類型的測試，因為以 Valgrind 執行測試程式會比較慢，容易導致出現超過時間限制的狀況。
## Reference
:::warning
參考資料不是讓你發表致謝詞的地方
:notes: jserv
> Got it, Thanks!
:::
- [komark06 PR#111](https://github.com/sysprog21/lab0-c/commit/ae7c2985b583126dd62ae6378941a93b2f73785f)
- [ISO/IEC 9899:1999](https://zh.wikipedia.org/zh-tw/C99)
- [3.11 Options That Control Optimization](https://gcc.gnu.org/onlinedocs/gcc-12.2.0/gcc/Optimize-Options.html#Optimize-Options)
- [學習 Shell Scripts](https://linux.vbird.org/linux_basic/centos7/0340bashshell-scripts.php)
- [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor?type=view)
- [ANSI escape code](https://en.wikipedia.org/wiki/ANSI_escape_code)
Sign in with Wallet
Connect another wallet