# 2025q1 Homework1 (lab0)
contributed by < PigeonSir >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
#### Reviewed by `kk908676`
部份 commit message 可以描述的更加詳細
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 6
On-line CPU(s) list: 0-5
每核心執行緒數： 1
每通訊端核心數： 6
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
製程： 10
CPU MHz： 2800.000
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
虛擬： VT-x
L1d 快取： 192 KiB
L1i 快取： 192 KiB
L2 快取： 1.5 MiB
L3 快取： 9 MiB
NUMA node0 CPU(s)： 0-5
```
## 修改 queue.c
### q_new
分配 list_head 的空間，再透過 INIT_LIST_HEAD 將 prev 和 next 指向自身。
```c
struct list_head *q_new()
{
struct list_head *obj = malloc(sizeof(struct list_head));
if (!obj)
return NULL;
INIT_LIST_HEAD(obj);
return obj;
}
```
後來加入對 malloc 失敗時做處置， c 語言規格書 ISO/IEC 9899:2024 7.24.3 節的第一段提到
> If the space cannot be allocated, a null pointer is returned.
在後續的實作中遇到 malloc 都要這麼做
### q_insert_head/q_insert_tail
> commit [d95ee65](https://github.com/sysprog21/lab0-c/commit/d95ee65a8430452d78a573bd51617cc0e0e14804)
再新增節點時需要字串的複製，作業解說提到的 strcpy 屬於危險的操作，原因如下
> The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
> CERN Compter Security
故選擇使用 strncpy ，需注意當愈複製的長度小於目標地址配置的大小時會自動補 '\0' ，反之則會被截斷，所以複製完後再強制將最後一個字節設為 '\0'
#### constant time 測試
後續發現以上方法未能通過 constant time 測試，初步推測為 strlen() 和 strncpy() 造成的，因為這兩個函式會隨著字串的長度增加執行時間
> 在 csappE3 5.4 節中提到 strlen() 對執行時間的影響， 並給出 strlen() 的簡單版本如下 ：
> ```c
> size_t strlen(const char *s)
> {
> long length = 0;
> while (*s != '\0') {
> s++;
> length++;
> }
> return length;
> }
> ```
> 而觀看手冊中 strncpy 的實現方式，其執行時間亦會使用 strlen，故推測這兩個函式造成 insert_head 和 insert_tail 無法通過 constant time 測試。
待後續閱讀論文以及研究 simulaion 的測試條件後再著手改善
#### 精簡程式碼
> commit [6530b15](https://github.com/sysprog21/lab0-c/commit/6530b15318b56e0dea120deb646245da2a68265e)
研究關於字串複製的方式，發現 strdup 可以更精簡程式碼，但還是無法通過 constant time 的測試
### queue_del_mid
> commit [785ea1b](https://github.com/sysprog21/lab0-c/commit/785ea1b235fa925499602689e9481d40eb7bacdf)
>
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 當中對於快慢指標的操作，在節點個數 $n$ 為偶數時移除第 $n / 2 + 1$ 個節點
#### 圖解流程
1. 前置檢查
* 如果 `head` 為 `NULL` 或 queue 為空，直接返回 `false`。
* 初始化 `temp` 為 `head->next` 的指標的指標，作為慢指標。
* 初始化 `fast` 指標為 `head->next`，作為快指標。
* 圖片中為了畫面整潔暫忽略 `head->prev` 和 `node5->next`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="<h>head|{<left>prev|<right>next}", style="bold", color=grey];
e1 [label="<h>node 1|{<left>prev|<right>next}", style="bold"];
e2 [label="<h>node 2|{<left>prev|<right>next}", style="bold"];
e3 [label="<h>node 3|{<left>prev|<right>next}", style="bold"];
e4 [label="<h>node 4|{<left>prev|<right>next}", style="bold"];
e5 [label="<h>node 5|{<left>prev|<right>next}", style="bold"];
node [shape=none]
temp [label = "temp"];
fast [label = "fast"];
head:right:e -> e1:h:w[arrowhead=normal, arrowtail=normal];
e1:right:e -> e2:h:w[arrowhead=normal, arrowtail=normal];
e2:right:e -> e3:h:w[arrowhead=normal, arrowtail=normal];
e3:right:e -> e4:h:w[arrowhead=normal, arrowtail=normal];
e4:right:e -> e5:h:w[arrowhead=normal, arrowtail=normal];
e1:left:w -> head:h:e[arrowhead=normal, arrowtail=normal];
e2:left:w -> e1:h:e[arrowhead=normal, arrowtail=normal];
e3:left:w -> e2:h:e[arrowhead=normal, arrowtail=normal];
e4:left:w -> e3:h:e[arrowhead=normal, arrowtail=normal];
e5:left:w -> e4:h:e[arrowhead=normal, arrowtail=normal];
temp -> head:right:s;
fast -> e1:h:n;
}
```
2. 進行迴圈
* 在迴圈內部更新 `temp` : `*temp` 為下一個節點的記憶體位置，故 `temp = &(*temp)->next` 會將 `temp` 指向下一個節點的 `next`
* 每一輪執行完更新 `fast` : 執行 `fast = fast->next->next` 讓 `fast` 指向下下一個節點
* `fast` 為最後一個節點或 `head` 時跳出迴圈
* 圖片中 fast 和 temp 的下標 0, 1, 2 代表各輪執行後的狀態
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="<h>head|{<left>prev|<right>next}"];
e1 [label="<h>node 1|{<left>prev|<right>next}"];
e2 [label="<h>node 2|{<left>prev|<right>next}"];
e3 [label="<h>node 3|{<left>prev|<right>next}"];
e4 [label="<h>node 4|{<left>prev|<right>next}"];
e5 [label="<h>node 5|{<left>prev|<right>next}"];
node [shape=none]
temp [label = "temp_0", fontcolor=gray];
fast [label = "fast_0", fontcolor=gray];
temp1 [label = "temp_1", fontcolor=gray];
fast1 [label = "fast_1", fontcolor=gray];
temp2 [label = "temp_2"];
fast2 [label = "fast_2"];
head:right:e -> e1:h:w[arrowhead=normal, arrowtail=normal];
e1:right:e -> e2:h:w[arrowhead=normal, arrowtail=normal];
e2:right:e -> e3:h:w[arrowhead=normal, arrowtail=normal];
e3:right:e -> e4:h:w[arrowhead=normal, arrowtail=normal];
e4:right:e -> e5:h:w[arrowhead=normal, arrowtail=normal];
e1:left:w -> head:h:e[arrowhead=normal, arrowtail=normal];
e2:left:w -> e1:h:e[arrowhead=normal, arrowtail=normal];
e3:left:w -> e2:h:e[arrowhead=normal, arrowtail=normal];
e4:left:w -> e3:h:e[arrowhead=normal, arrowtail=normal];
e5:left:w -> e4:h:e[arrowhead=normal, arrowtail=normal];
temp -> head:right:s[style=dashed, color=gray];
fast -> e1:h:n[style=dashed, color=gray];
temp1 -> e1:right:s[style=dashed,color=gray];
fast1 -> e3:h:n[style=dashed, color=gray];
temp2 -> e2:right:s;
fast2 -> e5:h:n;
}
```
3. 移除節點
* 此時 `temp` 指向 `node2` 的 `next`，所以移除的節點是 `*temp`，但要先定義另一個節點 `del` 指向 `*temp` ，才能使用 `list_del` 和 `q_release_element` 移除 `del`
### q_swap, q_reverse, q_reverseK
> commit [b99d99b](https://github.com/sysprog21/lab0-c/commit/b99d99baaed77a9ae965d047b33594cb84fc2cda)
在課堂上有提到 q_swap 和 q_reverse 都只是 q_reverseK 的特例，實現 q_reserveK 後 q_swap 和 q_reserve 分別只要將 K 代入 2 和 queue size 即可
```c
void q_swap(struct list_head *head) {
q_reverseK(head, 2);
}
void q_reverse(struct list_head *head) {
q_reverseK(head, q_size(head));
}
```
#### 圖解 q_reverseK 流程
以 k ＝ 3 為例
1. 前置檢查
* 若 head 為 NULL 、 佇列為空或 singular 即返回
* 初始化指標 start 和 end ，在反轉時反覆的從 end 斷開節點再依序從 start 之後接上
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="<h>head|{<left>prev|<right>next}", style="bold", color=grey];
e1 [label="<h>node 1|{<left>prev|<right>next}", style="bold"];
e2 [label="<h>node 2|{<left>prev|<right>next}", style="bold"];
e3 [label="<h>node 3|{<left>prev|<right>next}", style="bold"];
e4 [label="<h>node 4|{<left>prev|<right>next}", style="bold"];
e5 [label="<h>node 5|{<left>prev|<right>next}", style="bold"];
e6 [label="<h>node 6|{<left>prev|<right>next}", style="bold"];
node [shape=none]
end [label = "end"];
start [label = "start"];
head:right:e -> e1:h:w;
e1:right:e -> e2:h:w;
e2:right:e -> e3:h:w;
e3:right:e -> e4:h:w;
e4:right:e -> e5:h:w;
e5:right:e -> e6:h:w;
e1:left:w -> head:h:e;
e2:left:w -> e1:h:e;
e3:left:w -> e2:h:e;
e4:left:w -> e3:h:e;
e5:left:w -> e4:h:e;
e6:left:w -> e5:h:e;
start -> head:h:n;
end -> e1:h:n;
}
```
2. 進行迴圈
* 移動 `end` k - 1 次，此時 `start` 和 `end` 間的區間即要反轉的節點
* 運用指標 `temp` 指向 `end->next` ，以更新下一輪的 `end`
* 斷開 `start->next->prev`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="<h>head|{<left>prev|<right>next}", style="bold", color=grey];
e1 [label="<h>node 1|{<left>prev|<right>next}", style="bold"];
e2 [label="<h>node 2|{<left>prev|<right>next}", style="bold"];
e3 [label="<h>node 3|{<left>prev|<right>next}", style="bold"];
e4 [label="<h>node 4|{<left>prev|<right>next}", style="bold"];
e5 [label="<h>node 5|{<left>prev|<right>next}", style="bold"];
e6 [label="<h>node 6|{<left>prev|<right>next}", style="bold"];
// 特殊節點
node [shape=none];
null [label="NULL", shape=none];
end [label="end"];
start [label="start"];
temp [label="temp"];
// 連接節點
head:right:e -> e1:h:w;
e1:right:e -> e2:h:w;
e2:right:e -> e3:h:w;
e3:right:e -> e4:h:w;
e4:right:e -> e5:h:w;
e5:right:e -> e6:h:w;
e2:left:w -> e1:h:e;
e3:left:w -> e2:h:e;
e4:left:w -> e3:h:e;
e5:left:w -> e4:h:e;
e6:left:w -> e5:h:e;
start -> head:h:n;
end -> e3:h:n;
temp -> e4:h:n;
null -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=back];
}
```
### mergeTwo
> commit [9b1be79](https://github.com/sysprog21/lab0-c/commit/9b1be797595a2062f46036a07b0aff583cda1170)
新增函式 `mergeTwo` 以合併兩個已經排序完成的 `queue` ， 在 `q_sort` 和 `q_merge` 中都需要使用到 `mergeTwo` ，參考教材中的實作方式合併兩個斷開且單向的鏈結串列並在過程中僅維護 `next` 指標，升序排列的合併流程如下
#### 圖解流程
1. 輸入參數
`struct list_head * L, R` : 分別指向兩個生序排列的鍊結串列的第一個節點
`bool descend` : 為 `true` 時使用降序合併，此範例中為 `false`
2. 初始化
* `temp` 最初為 `NULL`，它將存儲合併後的新鍊結串列的起始節點。
* `indirect` 是一個指標的指標，用來追蹤新鏈表的尾端，以便逐步建立新的鏈表。
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l1 [label = "{<data>1 |<ref>}"];
l2 [label = "{<data>3 |<ref>}"];
l3 [label = "{<data>5 |<ref>}"];
r1 [label = "{<data>2 |<ref>}"];
r2 [label = "{<data>4 |<ref>}"];
r3 [label = "{<data>6 |<ref>}"];
node [shape=none]
n [label = "node"];
L;
R;
nu [label = "NULL"]
lnull [label = "NULL"];
rnull [label = "NULL"];
edge[weight=2];
L -> l1;
l1:ref:c -> l2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l2:ref:c -> l3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l3:ref:c -> rnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r1:ref:c -> r2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r2:ref:c -> r3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r3:ref:c -> lnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
R -> r1;
temp -> null;
indirect -> temp;
n -> nu;
}
```
3. 進入迴圈
* `node` 是 指標的指標，其值為 `&left` 或 `&right`，指向該輪中應該接到 `indirect` 上的節點
* 根據 `strcmp` 的結果選擇節點，範例中 `strcmp` 結果為負，因此在升序排列的情況下，`node` 和 `indirect` 指向 `L`
* 首次執行時，`indirect` 存放的是 `temp` 的記憶體位置，因此 `*indirect = *node` 等價於 `temp = L`，後續操作中 `temp` 的值將不再改變
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l1 [label = "{<data>1 |<ref>}"];
l2 [label = "{<data>3 |<ref>}"];
l3 [label = "{<data>5 |<ref>}"];
r1 [label = "{<data>2 |<ref>}"];
r2 [label = "{<data>4 |<ref>}"];
r3 [label = "{<data>6 |<ref>}"];
node [shape=none]
L;
R;
n [label = "node"];
lnull [label = "NULL"];
rnull [label = "NULL"];
edge[weight=2];
L -> l1;
temp;
temp ->l1;
l1:ref:c -> l2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l2:ref:c -> l3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l3:ref:c -> rnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
R -> r1;
r1:ref:c -> r2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r2:ref:c -> r3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r3:ref:c -> lnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
indirect -> temp;
n -> L;
}
```
4. 迴圈中更新指標
* 先更新 `indirect` 指向合併完的節點的 `next` 的記憶體位置
* 迴圈結束後再更新 `*node` （即更新 `L` ）指向該鍊結串列的下一個節點
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l1 [label = "{<data>1 |<ref>}"];
l2 [label = "{<data>3 |<ref>}"];
l3 [label = "{<data>5 |<ref>}"];
r1 [label = "{<data>2 |<ref>}"];
r2 [label = "{<data>4 |<ref>}"];
r3 [label = "{<data>6 |<ref>}"];
node [shape=none]
L;
R;
n [label = "node"];
lnull [label = "NULL"];
rnull [label = "NULL"];
edge[weight=2];
L -> l2;
temp;
temp ->l1;
l1:ref:c -> l2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l2:ref:c -> l3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l3:ref:c -> rnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
R -> r1;
r1:ref:c -> r2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r2:ref:c -> r3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r3:ref:c -> lnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
indirect -> l1:ref:s;
n -> L;
}
```
6. 接上剩餘的節點
* 反覆合併到 `L` 或 `R` 為 `NULL` 後跳出迴圈
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l1 [label = "{<data>1 |<ref>}"];
l2 [label = "{<data>3 |<ref>}"];
l3 [label = "{<data>5 |<ref>}"];
r1 [label = "{<data>2 |<ref>}"];
r2 [label = "{<data>4 |<ref>}"];
r3 [label = "{<data>6 |<ref>}"];
node [shape=none]
L;
R;
n [label = "node"];
lnull [label = "NULL"];
rnull [label = "NULL"];
edge[weight=2];
L -> rnull;
temp;
temp ->l1;
l1:ref:c -> r1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r1:ref:c -> l2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l2:ref:c -> r2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
R -> r3;
r2:ref:c -> l3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l3:ref:c -> rnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r3:ref:c -> lnull [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
indirect -> l3:ref:s;
n -> L;
}
```
* 最後將 `L` 或 `R` 中剩餘的節點接上 `indirect` 並返回 `temp`
### q_merge
> commit[49bd087](https://github.com/sysprog21/lab0-c/commit/49bd08758fa1dcb43f2d9e764f8bcc9ef2e42b8f)
q_merge 會用到結構體 queue_contex_t ，其中保存了 queue 的 size, id 和 queue 的 head ， 並透過 chain 鍊結。
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
含有兩個 queue 的示意圖如下
```graphviz
digraph linked_list {
rankdir=LR;
//graph [splines=ortho, ranksep=1.5, nodesep=1.0];
node [shape=plaintext];
head [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" BGCOLOR="DeepSkyBlue">
<TR><TD PORT="head" COLSPAN="2"><B>head</B></TD></TR>
<TR>
<TD PORT="prev">prev</TD>
<TD PORT="next">next</TD>
</TR>
</TABLE>
>];
node0 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD COLSPAN="2" BGCOLOR="lightgray"><B>queue 0</B></TD></TR>
<TR><TD COLSPAN="2">id</TD></TR>
<TR><TD COLSPAN="2">size</TD></TR>
<TR><TD PORT="q" COLSPAN="2">q</TD></TR>
<TR>
<TD COLSPAN="2">
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" BGCOLOR="lightblue">
<TR><TD PORT="chain" COLSPAN="2"><B>chain</B></TD></TR>
<TR>
<TD PORT="prev">prev</TD>
<TD PORT="next">next</TD>
</TR>
</TABLE>
</TD>
</TR>
</TABLE>
>];
node1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD COLSPAN="2" BGCOLOR="lightgray"><B>queue 1</B></TD></TR>
<TR><TD COLSPAN="2">id</TD></TR>
<TR><TD COLSPAN="2">size</TD></TR>
<TR><TD PORT="q" COLSPAN="2">q</TD></TR>
<TR>
<TD COLSPAN="2">
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" BGCOLOR="lightblue">
<TR><TD PORT="chain" COLSPAN="2"><B>chain</B></TD></TR>
<TR>
<TD PORT="prev">prev</TD>
<TD PORT="next">Next</TD>
</TR>
</TABLE>
</TD>
</TR>
</TABLE>
>];
rankdir=LR;
{rank=same; head;}
head:next -> node0:chain:w;
head:prev -> node1:chain:w;
node0:next -> node1:chain;
node0:prev -> head:head;
node1:next:e -> head:head;
node1:prev -> node0:chain;
node0:q -> head1;
node1:q -> head2;
}
```
先透過最容易實現的方法實做，將每一個 queue 都和第一個 queue 執行 mergeTwo
#### 頭尾合併
## 研讀並引入 lib/list_sort.c
list_srot 內包含三個函式 ： merge, merge_final 和 list_sort ，將這些函式修改後加入 queue.c
### 研讀並加入 list_sort
#### unlikely
```c
#ifndef likely
#define likely(x) __builtin_expect(!!(x), 1)
#endif
#ifndef unlikely
#define unlikely(x) __builtin_expect(!!(x), 0)
#endif
```
#### 比較函式
在 list_sort.c 中，cmp 參數是一個**比較函式的指標**，被定義於 list_sort.h：
```c
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(
void *, const struct list_head *, const struct list_head *);
```
上述程式碼定義了一種函式指標類型 list_cmp_func_t 指向一個接收三個參數並回傳 int 的函式：
* __attribute__((nonnull(2,3))) 指示編譯器第二和第三個參數不能為 NULL
* void *：用來傳遞額外資訊
* 兩個 const struct list_head *：指向被比較的節點
這樣做是為了在呼叫 list_sort() 時，傳遞不同的比較函式來決定排序方式。而我選擇直接在 queue.c 中定義比較函式為一個全域的函式，直接在排序的過程中呼叫它，參考 list_sort.c 中對於比較函式的描述：
> 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.
>
> The comparison function must adhere to specific mathematical properties to ensure correct and stable sorting: - Antisymmetry: cmp(a, b) must return the opposite sign of cmp(b, a). - Transitivity: if cmp(a, b) <= 0 and cmp(b, c) <= 0, then cmp(a, c) <= 0.
>
> This is compatible with two styles of cmp function: - The traditional style which returns <0 / =0 / >0, or - Returning a boolean 0/1. The latter offers a chance to save a few cycles in the comparison (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
考量 cmp (a, b)
* 回傳值 <= 0 : a 排在 b 之前
* 回傳值 > 0 : a 排在 b 之後
當 a > b
* 升序時 (ascending) 要回傳正值
* 降序時 （descending) 要回傳零或負值
若先計算 ret = a - b ，升序時回傳 ret (正數) 因為 a 要排在後面，而降序時回傳 -ret (負數)，實作細節如下
```c
int cmp (struct list_head *a, struct list_head *b, bool descend) {
element_t *A = list_entry(a, element_t, list);
elsment_t *B = list_entry(b, element_t, list);
int ret = strcmp(A->value, B->value);
return descend ? -ret : ret
}
```
#### list_sort
#### 修改 qtest.c
> commit [af0ee40](https://github.com/sysprog21/lab0-c/commit/af0ee4008388203a71482c5a070077cb340fcec8)
在 console_init() 中新增命令 listSort ，並新增函式 do_listSort ，其內容和 do_sort 相同。
```c
ADD_COMMAND(listSort, "");
```
### 比較執行時間
撰寫比較兩個排序法執行時間用的 command file
```
option fail 0
option malloc 0
new
ih RAND <10000 50000 100000 500000>
time
<listSort / sort>
time
reverse
time
<listSort / sort>
time
free
```
此測試會對四種不同數量的元素（10,000 / 50,000 / 100,000 / 500,000）執行排序，並計算：
1. 第一次排序的時間 (隨機插入)
2. 反轉 queue 後再次排序的時間
測試結果如下：
**第一次排序**
|資料數 |q_sort|list sort|
|----- | -----|---------|
|10000 |0.0044|0.0034 |
|50000 |0.0454|0.0362 |
|100000|0.1230|0.090 |
|500000|0.7658|0.5580 |
**反轉後排序**
|資料數 |q_sort|list sort|
|----- |----- | --------|
|10000 |0.0028|0.0012 |
|50000 |0.0530|0.0418 |
|100000|0.1442|0.1052 |
|500000|0.9460|0.6144 |
發現 list sort 在各個資料數下都快於 q_sort
### 使用 perf
接下來運用效能分析工具 [pref](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 分析此效能
，執行 500000 個元素的排序五次，監控 instructions, cycles 和 branches
```
$ sudo perf stat --repeat 5 -e instructions,cycles,branches ./qtest -f traces/traceTest.cmd
```
list sort
```
Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):
4,092,947,424 instructions # 0.51 insn per cycle ( +- 0.08% )
8,109,857,850 cycles ( +- 0.38% )
554,107,769 branches ( +- 0.14% )
2.1554 +- 0.0183 seconds time elapsed ( +- 0.85% )
```
q_sort
```
Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):
4,134,313,258 instructions # 0.43 insn per cycle ( +- 0.02% )
9,322,393,713 cycles ( +- 1.02% )
577,098,583 branches ( +- 0.02% )
2.5141 +- 0.0267 seconds time elapsed ( +- 1.06% )
```
從 cycles 來看，q_sort 需要更多的 CPU cycle，且執行時間比 list sort 長。
### cache 比較
listSort
Cache miss 率較高（差約 3%），但總存取次數少很多 → 記憶體開銷相對小
因此雖然 miss 多，但總時間反而更短
```
Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):
66883168 cache-misses # 32.89% of all cache refs ( +- 0.27% )
203344938 cache-references ( +- 0.86% )
2.4113 +- 0.0106 seconds time elapsed ( +- 0.44% )
```
q_sort
Cache miss 率較低，但總存取次數多、運算開銷較大 → 反而慢
如果要優化，應該檢查是否可以降低存取次數，例如改善 partition 過程的 cache locality 或減少多餘遞迴
```
Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):
69276991 cache-misses # 29.79% of all cache refs ( +- 0.13% )
232529964 cache-references ( +- 0.19% )
2.94021 +- 0.00834 seconds time elapsed ( +- 0.28% )
```
### cmp 呼叫次數
為了分析兩種排序法進行比較的次數，更新 `q_sort` 的比較方式為呼叫 `cmp`
> commit [4c2ac8b](https://github.com/PigeonSir/lab0-c/commit/4c2ac8b96489be2dd4481146255176e607f83814)
透過 perf probe 加入觀察點於 `cmp`
```
$ sudo perf probe -x ./qtest cmp
```
但加入觀察點後執行 record 發現次數為 0
```
$ sudo perf record -e probe_qtest:cmp -aR ./qtest -f traces/traceTest.cmd
... ...
$ sudo perf script | grep cmp | wc -l
0
```
發現 `cmp` 的呼叫次數為 0，表示 perf probe 未能成功攔截 `cmp`，需要進一步調查問題可能的原因
## 在 qtest 提供新的命令 shuffle
## 研讀論文 ＆ simulaion 的測試條件
### 研讀 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
該論文介紹了名為 dudect 的工具，主要用來檢測某段程式碼是否以 constant-time 執行，有別於傳統檢測方式，dudect 採用的是「統計分析」的方法而非傳統的「靜態分析」，具體步驟如下：
#### step 1 : Measure execution time
* 定義輸入類別 (class)
第一類 fix：輸入固定為某個常數值。
第二類 random ：輸入為每次隨機選擇的數據。
* 使用 CPU 週期計數器或計時器測量執行時間
* 隨機選擇輸入類別，降低環境影響
#### step 2 : Apply post-processing
* 過濾異常數據（Cropping），避免系統中斷、測量誤差影響分析結果
* 應用高階預處理（Higher-order preprocessing），利用更精細的統計方法增強時間洩漏的檢測能力
#### step 3 : Apply statistical test
* 使用統計檢定來驗證「兩組執行時間分佈是否相同」
* t-test & Non-parametric tests
### simulation
在 qtest.c 中函式 `queue_insert` 和 `queue_remove` 都會依據全域變數 simulation 決定是否進行 constant time 檢查，且檢查都是發生在實際插入/移除節點之前，檢查方式如下
```c
// in queue_insert
bool ok = pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
// in queue_remove
bool ok = pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();
```
定義於 dudect/constant.h
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
```
在 fixture.h 展開成函式
```c
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
```
在 fixture.c 定義函式的內容
```c
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _
```
經過展開後變為呼叫 test_const 的函式，其中 DUT() 代表該測試的編號
```c
bool is_insert_head_const(void) { return test_const("insert_head", DUT(insert_head)); }
bool is_insert_tail_const(void) { return test_const("insert_tail", DUT(insert_tail)); }
bool is_remove_head_const(void) { return test_const("remove_head", DUT(remove_head)); }
bool is_remove_tail_const(void) { return test_const("remove_tail", DUT(remove_tail)); }
```
Sign in with Wallet
Connect another wallet