# 2024q1 Homework1 (lab0)
contributed by < `chishuo9810` >
### Reviewed by `Chloexyw`
> 在執行 q_new 時僅僅做了初始化並未看見透過 queue_context_t 型態將不同佇列串接在一起的操作。
```
* q_merge() - Merge all the queues into one sorted queue, which is in
* ascending/descending order.
```
在 `list.h` 中有提到 `q_merge` 的目的是合併所有佇列到已排序的佇列中，所以此操作會需要先找出連接著The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and continually determines the next element in the shuffled sequence by randomly drawing an element from the list until no elements remain.[1] The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm takes time proportional to the number of items being shuffled and shuffles them in place. 各個 queue 的結構體的位置並且需要使用 `queue_contex_t` 去進行管理
```
q_new() - Create an empty queue whose next and prev pointer point to itself
```
而 `q_new` 是創造一個空的佇列並且配置記憶體給 head ，既然不需要管理佇列和佇列間的關係，就不用使用 `queue_contex_t` 去連結不同佇列
### Reviewed by `ChiTingCheng`
### Reviewed by `david965154`
**1**.
> 此巨集將 `list_entry` 定義為 `container_of` ，目前仍然看不懂 `container_of` 的寫法，暫時先使用，往後回頭細讀再做補充。
可以看 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
**2**.
q_insert_head, q_insert_tail
內的
```diff
element_t *node = malloc(sizeof(element_t));
if (!node) {
- free(node);
return false;
}
```
`free(node)` 應是不必要的，在配置失敗時會回傳 `NULL`，因此 `node` 仍為 `NULL Pointer` ，無須再去釋放配置空間。
**3**.
在 github 的 sort 中，先配置 1000000 個指標，在下一行判斷如果 `listSize` 超出上限即反轉並返回，請問反轉的意義是?
```c
struct list_head *lists[1000000] = {NULL};
if (listsSize > 1000000) {
q_reverse(head);
return;
}
```
這是當初<s>第 14 筆測資</s> 過不了，無聊加上去，後來寫完沒刪掉，目前已更正。
:::danger
本處是「測試項目」(item)，而非「資料」，查閱辭典以理解二者的落差。
:::
並且最直接的缺點是無法排序超過 1000000 長度的佇列，可以嘗試如果超過上限就先做前半部分，再做後半部分，之後透過 `mergeTwoLists` 合併，若長度更多則可以嘗試切成更多再合併。
**4**.
函式
```c
int q_descend(struct list_head *head)
```
內 `pointer to struct` `max` 應改為 `min` 會更好。
另外<s>建議</s> 可以嘗試使用 `GDB` 只要 command `gdb ./qtest` ，並以原本的方式測試，可以得到更額外的錯誤資訊非只有 segmentation fault ，例如:類似 `strcmp file not found` ，即代表傳遞給 strcmp 的參數可能為 head (無 `element_t` 之成員 `value` 可做比較)。
5.
`原本需要進行 log1000000 回合，總共 1000000 * log1000000 = 20000000 次操作，經過改量，只需要進行 1 回合，總共 1000000 * 1 = 1000000 次操作，快了 20 倍左右。`
參考 [Time Complexities of all Sorting Algorithms](https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/)
> Time Complexity:
> Time Complexity is defined as the number of times a particular instruction set is executed rather than the total time taken. It is because the total time taken also depends on some external factors like the compiler used, the processor’s speed, etc.
參考 [What is the time complexity of a comparison or substitution operation?](https://stackoverflow.com/questions/59394539/what-is-the-time-complexity-of-a-comparison-or-substitution-operation)
比較次數並未被計算進你的「操作」次數，只要比較次數沒辦法恆定為常數，那麼就應該透過一變數計算。
## 系統安裝
照著 [雙系統安裝教學](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBks3DypY-) 安裝 `ubuntu` ，完成後重開機卻沒有出現 `GRUB` 界面，而是直接進入 `windows` ，在安裝步驟確認沒錯的情況下懷疑是 `windows boot manager` 設定出問題。最後參考 [Ask Ubuntu](https://askubuntu.com/questions/844490/no-grub-after-installing-ubuntu-beside-windows-10) ，在 `windows` 以系統管理原身份執行
```
bcdedit /set {bootmgr} path \EFI\ubuntu\grubx64.efi
```
成功完成環境安裝。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
CPU family: 6
Model: 141
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
```
## 指定佇列的操作
> 目前分數 ： 100
### `q_new`
:::danger
採用作業指定的程式碼縮排風格
:::
根據作業給的提示（紅包袋的比喻），在使用 `list.h` 中的 `INIT_LIST_HEAD` 之前先檢查記憶體是否有配置成功。原先檢查的程式碼如下：
```c
if (new_head != NULL) {
return NULL;
}
```
想當然，這是一個謬誤，得到的回饋是 `[nullPointerRedundantCheck]`
起初我沒想過邏輯錯誤並不斷的查閱規格書，後來才發現自己錯的離譜
==反思：認真閱讀錯誤訊息後再進行除錯，避免事倍功半。==
### `q_insert_head`, `q_insert_tail`
實作函式時起初使用 `strcpy` 將字串複製到新加入的節點中，得到以下回饋：
```
Dangerous function detected in /home/chishuo/linux2024/lab0-c/queue.c
39: strcpy(node->value, s);
```
參考 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
並查閱 C99 規格書 7.21.2.3
> The strcpy function copies the string pointed to by s2 (including the terminating nullcharacter) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.
`list.h` 中描述 `q_insert_head` 提到
```
The function must explicitly allocate space and copy the string into it.
```
而 `strcpy` 並未分配記憶體，而是將指標指向要複製的字串位址，因此使用 `strdup` 取而代之。
第 11、12 筆測資出現錯誤訊息如下 ：
```
ERROR: Freed queue, but 7 blocks are still allocated
```
頭先無法理解為什麼這兩個函式需要釋放記憶體，查看 `trace-11-malloc.cmd` 才注意到這兩筆測資在測試 `malloc` 失敗時的處理。加上條件判斷後即排除。
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = malloc(sizeof(element_t));
if (!node) {
+ free(node);
return false;
}
INIT_LIST_HEAD(&node->list);
node->value = strdup(s);
+ if (!node->value) {
+ free(node->value);
+ free(node);
+ return false;
+ }
list_add(&node->list, head);
return true;
}
```
### `q_remove_head` `q_remove_tail`
以前學習鏈結串列時的結構如下 (以 C++ 為例)
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
```
因此起初撰寫時嘗試透過 `head->next->value` 取值，仔細閱讀才注意到 `element_t` 內並沒有指標，因此要取值的話必須透過
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
此巨集將 `list_entry` 定義為 `container_of` ，目前仍然看不懂 `container_of` 的寫法，暫時先使用，往後回頭細讀再做補充。
### `q_delete_mid`
沒有遇到程式上的問題，但對於 `queue.h` 的說明有疑慮
```
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six elements, the third member should be returned.
```
:::warning
針對電腦技術，避免引用 Wikipedia 中文詞目，因為其中內容常過時且充斥錯誤。
:::
:::info
我已更換成英文詞目。
:::
根據[維基百科--自然數](https://en.wikipedia.org/wiki/Natural_number) 定義，計算機科學領域定義 0 屬於自然數，而數論則相反。
用以下陣列作說明:
```c
int arr[] = {0, 2, 4, 6, 8, 10};
// ⌊n / 2⌋ = ⌊6 / 2⌋ = 3;
```
如果是 **0-base indexing**，`arr[3] = 6` 即為所求。
但是最後一句話中 ==the third member== 的敘述為計數的概念， [Cambridge Dictionary](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/member) 對於 `memeber` 一詞有定義：
```
a person, animal, or thing that is part of a group
```
量詞 `a` 代表 1，the third member 翻譯為**第三名成員**，而在 C 語言中，陣列的索引從 0 開始，因此第三個元素的索引應該是 `arr[2] = 4`。
語句前後矛盾，[leetcode](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 題目敘述更為明確易懂
```
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using
0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
```
因此我認為最後一句說明很多餘。
:::warning
太好了，提交 pull request 來澄清。
:::
### `q_delete_dup`
參考 [vax-r](https://github.com/vax-r/lab0-c/blob/master/queue.c) 。
編譯一直遇到記憶體區段錯誤，最後才想到因為是環狀鏈結串列，結束的判斷必須修正，如下 ：
```diff=
-if (&future->list == NULL)
+if (&future->list == head)
```
### `q_reverse`
<s>
<style>
.blue {
color: #84b9f0;
}
.red {
color: red;
}
.green {
color: green;
}
</style>
> <span class="red">-void q_reverse(struct list_head *head) </span>
> <span class="green">+void q_reverse(struct list_head *head) </span>
</s>
```diff=
-void q_reverse(struct list_head *head)
+void q_reverse(struct list_head *head)
```
:::warning
使用 diff 標示程式碼之間的差異，避免使用 CSS
:::
執行 `clang-format -i queue.c` 後解決，卻始終不知道差異在哪。
:::warning
可運用 hexdump 一類的工具，逐位元組的內容來觀察差異。
:::
### `q_reverseK`
處理最久的問題為指標要往哪裡指，剛開始空想了許多方法一直失敗，最後配合平板作圖成功實作。
==特此紀錄，提醒自己實際圖像畫能更有效的規劃程式邏輯==
```c
current_head->next->next = future->next;
future->next->prev = current_head->next;
current_head->next = future;
future->prev = current_head;
future->next = current;
current_head = current->next;
// current->next = future->next;
// current->next->prev = current;
// future->next = current;
// current_head->next = future;
// future->prev = current_head;
// current_head = current;
// current = current->next;
// future = current->next;
```
### `q_ascend` `q_descend`
參考了 [leetcode](https://leetcode.com/problems/remove-nodes-from-linked-list/description/) 的提示 `Iterate on nodes in reversed order.` 卻一直遇到記憶體區段存取錯誤，猜測試是指標的指派錯誤。不斷嘗試無果，另闢蹊徑，先使用 `q_reverse` 將佇列反轉，接著用 `list_for_each_entry_safe` 走訪節點並進行刪除。
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
q_reverse(head);
/* descend 操作 */
q_reverse(head);
return q_size(head);
}
```
* 好處 ： 直觀操作，對於撰寫者比較不會出錯。
* 壞處 ： `q_reverse` <s>遍歷</s> ?? 走訪整個佇列，前後各一，增加了 2n 次的操作。
找時間再做修正，會以此為折衷方案是因為即使增加了 2n 的時間複雜度，時間複雜度為 `O(n+n+n)` = `O(n)`，影響並不是太大。
### `q_sort`
起初使用 `插入排序法` 實作，然而此排序法最糟的複雜度為 O(n^2^)，無法通過第 15 筆測資。
```c
list_for_each_safe (current, future, head) {
temp = current->prev;
while (temp != head->prev) {
compare = list_entry(temp, element_t, list);
current_value = list_entry(current, element_t, list);
if (temp == head && temp->next == current) {
break;
} else if (temp == head) {
list_move(current, head);
current = future->prev;
break;
} else if (strcmp(compare->value, current_value->value) > 0) {
temp = temp->prev;
} else if (temp->next != current) {
list_move(current, temp);
current = future->prev;
break;
} else {
break;
}
}
if (descend) {
q_reverse(head);
}
}
```
研讀 [非遞迴merge sort 實作](https://hackmd.io/@sysprog/c-linked-list#%E9%9D%9E%E9%81%9E%E8%BF%B4%E7%9A%84%E5%AF%A6%E4%BD%9C) ，將排序的演算法改為 `合併排序法` 並成功通過第15筆測資。
首先將所有的節點內的指標 `next` 指向 `NULL`，並存入 `lists[i]` 中
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
element_A [label="lists[i]| prev\l next\l}", style=filled, fillcolor=gray];
element_A -> NULL;
}
```
```c
while (listsSize > 1) {
for (int i = 0, j = listsSize - 1; i < j; i++, j--) {
lists[i] = mergeTwoLists(lists[i], lists[j]);
}
listsSize = (listsSize + 1) / 2;
}
```
:::danger
查閱辭典關於「軸心」的解釋，看是否合適。
> 參考 [教育部重編國語辭典修訂本](https://dict.revised.moe.edu.tw/dictView.jsp?ID=115845&la=0&powerMode=0)， `軸心` 用於比喻組織中最重要的部分。改成 `基礎` ，解釋為「事物的根本」，在此表示此段程式碼為本函式的根本更為貼切合宜。
:::
接著以上面那段程式碼為 <s>軸心</s> 基礎，利用我另外寫的函式 `mergeTwoLists` 將 `lists` 內的節點們按照順序兩兩合併
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
element_A [label="lists[i]| prev\l next\l}", style=filled, fillcolor=gray];
element_B [label="lists[i]| prev\l next\l}", style=filled, fillcolor=gray];
element_A -> NULL
element_B -> element_A
}
```
測試後發現只要超過 1200000 筆資料進行排序時，會出現 `Time limit exceeded`，然而第 15 筆測資有通過代表時間複雜度確實屬於 `O(nlogn)` 。參考[第 1 週測驗題 測驗2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) ，利用 `Timsort` 透過檢查已排序好的子序列來減少合併次數，這樣遇上資料中有大量已排序的子序列時可以大幅度降低時間複雜度。
以第 14 筆測資為例 :
```
# Test performance of insert_tail, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
sort
```
原本需要進行 log1000000 回合，總共 1000000 * log1000000 = 20000000 次操作，經過改量，只需要進行 1 回合，總共 1000000 * 1 = 1000000 次操作，快了 20 倍左右。
```diff=
while (result != head) {
if (result->next == head) {
lists[k] = result;
lists[k++]->next = NULL;
break;
}
+ if (strcmp(list_entry(result, element_t, list)->value,
+ list_entry(result->next, element_t, list)->value) <= 0) {
+ lists[k] = result;
+ do {
+ result = result->next;
+ } while (result->next != head &&
+ strcmp(list_entry(result, element_t, list)->value,
+ list_entry(result->next, element_t, list)->value) <=
+ 0);
+ result = result->next;
+ result->prev->next = NULL;
+ } else {
struct list_head *temp;
lists[k] = result;
result = result->next->next;
lists[k]->next->next = NULL;
temp = lists[k]->next;
lists[k]->next = NULL;
lists[k] = mergeTwoLists(lists[k], temp);
+ }
k++;
}
```
遇到問題 : 按照此`q_sort` 邏輯，每一回合的合併操作 n 次，第一回合的合併檢查了已排序(由小到大)的子序列，假設為共有 `k` 筆資料屬於已排序的子序列，共 `j` 個子序列：
\begin{cases}
k \geq 2 (至少兩筆資料才會形成子序列)\\
j \geq \frac{k}{2}\geq 1
\end{cases}
總共會進行的回合數為 log(n-k+j) 回合，由於 k - j > 0，必定小於合併排序法需要進行的回合數 logn 。
即使如此，在超過一百萬筆的隨機資料時，依然出現 `Time limit exceeded`，合理推測是我的合併排序法寫法有問題，但目前仍未找出我合併排序的問題所在。
<!-- 不斷的迭代最後可得到正確排序。 -->
:::danger
你如何確認目前的測試已涵蓋排序演算法的最差情況？
:::
### `q_merge`
首先，其他函式的參數都是傳入 `struct list_head *head` ，根據 [Linked list 在 Linux 核心原始程式碼](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) ， 佇列結構應該如下圖 ：
<s>
</s>
:::danger
使用 Graphviz 製圖，並嵌入到 HackMD 筆記。
:::
這也是我閱讀 `queue.h`、`list.h` 以及實作 `q_new`、`q_insert` 觀察得到的結果。
`q_merge` 的說明 ：
```
Merge all the queues into one sorted queue, which is in ascending/descending order.
```
以及 `queue.h` 中的 `queue_contex_t` 結構
```c
/**
* queue_contex_t - The context managing a chain of queues
* @q: pointer to the head of the queue
* @chain: used by chaining the heads of queues
* @size: the length of this queue
* @id: the unique identification number
*/
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
大概可以猜測整個系統中不同的佇列間關係應該如同 [25077667](https://hackmd.io/@25077667/SkpLspWnT#%E8%A3%9C%E9%BD%8A%E6%8C%87%E5%AE%9A%E7%9A%84%E4%BD%87%E5%88%97%E6%93%8D%E4%BD%9C) 同學所繪製 ：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
queue_context_1 [label="{queue_contex_t|+ q: list_head*\l+ chain: list_head\l+ size: int\l+ id: int\l}", style=filled, fillcolor=lightblue];
queue_context_2 [label="{queue_contex_t|+ q: list_head*\l+ chain: list_head\l+ size: int\l+ id: int\l}", style=filled, fillcolor=lightblue];
queue_context_3 [label="{queue_contex_t|+ q: list_head*\l+ chain: list_head\l+ size: int\l+ id: int\l}", style=filled, fillcolor=lightblue];
// Define the elements as entries of a queue, now explicitly shown
element_A [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
element_B [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
element_C [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
element_1 [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
element_2 [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
element_3 [label="{element_t|+ value: char*\l+ list: list_head\l}", style=filled, fillcolor=lightgray];
// Define the conceptual queue through element_t chain, now removed for direct visualization
queue1 [label="Conceptual Queue (chain of element_t)", shape=ellipse, style=dashed];
queue2 [label="Conceptual Queue (chain of element_t)", shape=ellipse, style=dashed];
queue3 [label="Conceptual Queue (chain of element_t)", shape=ellipse, style=dashed];
// Define the global chain of queues managed by queue_context
// global_chain [label="Global Chain of queue_context", shape=ellipse, style=dashed];
// Relationships
queue_context_1 -> queue1 [label="manages (q points to first element_t)"];
queue_context_2 -> queue2 [label="manages (q points to first element_t)"];
queue_context_3 -> queue3 [label="manages (q points to first element_t)"];
queue1 -> element_A;
queue2 -> element_1;
element_A -> element_B;
element_B -> element_A;
element_B -> element_C;
element_C -> element_B;
element_C -> element_A;
element_A -> element_C;
// global_chain -> queue_context_1 [label="part of", dir=none];
// global_chain -> queue_context_2 [label="part of", dir=none];
element_1 -> element_2;
element_2 -> element_1;
element_2 -> element_3;
element_3 -> element_2;
element_3 -> element_1;
element_1 -> element_3;
queue_context_1 -> queue_context_2;
queue_context_2 -> queue_context_1;
queue_context_2 -> queue_context_3;
queue_context_3 -> queue_context_2;
queue_context_3 -> queue_context_1;
queue_context_1 -> queue_context_3;
}
```
但是在執行 `q_new` 時僅僅做了初始化
<!-- <s>
</s> -->
```graphviz
digraph QueueRelationships {
rankdir=LR;
node [shape=record, fontname="Arial"];
element_A [label="{ prev | next}", style=filled, fillcolor=gray];
element_A:prev -> element_A:next [arrowtail=normal, arrowhead=normal, dir=both, headport=e, tailport=w]
}
```
:::danger
使用 Graphviz 製圖，並嵌入到 HackMD 筆記。
> 已改進
:::
並未看見<s>通過</s> 透過 `queue_context_t` 型態將不同佇列串接在一起的操作。
:::danger
注意用語，你該如何區分 pass 的翻譯「通過」？
> 已改成 `透過`
:::
參考了幾乎所有同學此 <s>函數</s> 函式的實作方法，大都是直接引用。目前也是了解 `queue_context_t` 的結構後做使用，日後想通再做補充。
參考 [Han1018](https://github.com/Han1018/lab0-c/blob/master/queue.c)，透過 `list_for_each_entry` 走訪所有的佇列，並把從第二個開始的每一個佇列透過 `list_splice_init` 接到第一個佇列上，最後在使用函式 `q_sort` 做排序。
```c
list_for_each_entry (current, head, chain) {
if (current != result) {
list_splice_init(current->q, result->q);
result->size = result->size + current->size;
}
}
q_sort(result->q, descend);
```
## 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)
### 名詞解釋
整篇論文一直遇到不熟悉的字眼導致閱讀困難，在此整理出一些我有疑慮的詞彙。
* [high resolution timer](https://stackoverflow.com/questions/17236039/high-resolution-timers-vs-low-resolution-timers) :
以高頻率持續更新 current value 的硬體暫存器。
* [Null hypothesis](https://en.wikipedia.org/wiki/Null_hypothesis) :
可以用來描述兩組數據並沒有存在關聯性，本篇的虛無假設為「兩個時間分佈相同」。
* [Welch's t-test](https://en.wikipedia.org/wiki/Welch's_t-test) ：
是一種用於比較兩個獨立樣本平均值是否存在顯著差異的統計檢驗方法。與傳統的 Student’s t-test 相比， Welch's t-test 在樣本大小和方差不相等時更為準確。
* [smoke test](https://en.wikipedia.org/wiki/Smoke_testing_(software)) :
是一種軟件測試方法，旨在驗證軟件的基本功能是否能夠運行。
### 簡述
許多被認為屬於常量時間的實作卻因為 timing leakage 導致實際結果與預期不符，進而出現資安疑慮，傳統上依賴手動檢查組合語言檢查是否存在 timing leakage （記憶體索引或分支），然而對於稍大一些的代碼庫來說十分耗時。
有多工具可以用來檢測 variable time code，例如 Valgrind、Flow-tracker 等，但他們需要模擬硬體，而正確的建模十分不易，涉及硬體供應商提供資訊不足以及硬體的更新。
這篇論文介紹了一個名為 dudect 的工具，用於檢測給定平台上某段代碼是否以常量時間運行。dudect 不依賴於靜態分析，而是依賴於對目標平台上執行時間測量的統計分析，透過這種方式，避免了對底層硬體進行建模的問題。
### 方法
***TIMING LEAKAGE DETECTION***
測量兩種不同輸入資料的執行時間，並比較兩者時間分佈是否不同。
* **Step 1 : Measure execution time**
1. Classes definition
`fix-vs-random tests` 被認為可以捕捉各種潛在洩漏，其中固定資料會選擇可能觸發邊界條件的特殊值。
2. Cycle counters
用於準確獲取執行時間測量。
3. Environmental conditions
每次隨機選擇類別以及輸入都應該在測量前完成以降低環境造成的影響。
* **Step 2 : Apply post-processing**
1. Cropping
典型的計時分佈執行時間呈現正偏斜，可能是測量工作、主要進程被操作系統或其他外部活動中斷所導致。在這種情況下，必須裁剪測量值（或丟棄大於固定的、與類別無關的閾值的測量值）來降低誤差。
2. Higher-order preprocessing
根據應用的統計測試，進行一些高階的預處理。
* **Step 3 : Apply statistical test**
利用統計測試反駁 `null hypothesis`
1. t-test
一種簡單的統計測試是 Welch's t-test，用於測試均值的等效性，因此，當該測試失敗時，可以很容易地得出結論說存在一個一階時間 `timing leakage`。當 `t-test` 與裁剪預處理結合時，不僅僅是測試均值的相等性，還在測試更高階的統計情境，因為裁剪是一個非線性轉換。
2. Non-parametric tests
使用更通用的非參數測試，例如 Kolmogorov-Smirnov 測試。優點在於這些測試通常對於基本分佈的假設較少；缺點在於它們可能收斂速度較慢，需要更多的樣本。
## 解釋 simulation 模式
在 `qtest.c` 中的 `queue_insert` 和 `queue_remove` 裡發現當變數 `simulation` 若被設為 1 則會進行檢查此二項操作是否符合常數時間。
接著毫無頭緒，於是參考了 [var-x](https://hackmd.io/@vax-r/linux2024-homework1#%E8%A7%A3%E9%87%8B-simulation-%E5%81%9A%E6%B3%95) 同學並模仿其操作。
```c
#define DUT(x) DUT_##x
```
看不懂以上代碼，參考 C99 規格書 [6.10.3.3]
> If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence; however, if an argument consists of no preprocessing tokens, the parameter is replaced by a placemarker preprocessing token instead.
接著使用 `gcc -E -P` 解析
:::info
`-E` ：告訴 `gcc` 在預處理階段停止。
`-P` ：不輸出行號。
:::
`dudect/fixture.c` 當中寫了函式的實作
```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); }
```
在 `dudect/fixture.c` 中加入 `cmp`、`percentile`、`prepare_percentile` 三個函式，並修改函式 `doit`
```diff=
differentiate(exec_times, before_ticks, after_ticks);
+ prepare_percentiles(exec_times);
update_statistics(exec_times, classes);
```
* `differentiate` 計算執行的時間
* `prepare_percentiles` 為每次 cropping measurements 設置不同的 threshold
* `update_statistics` 對執行時間進行 t-test
:::info
不知其所以然，對整篇論文以及程式理解有限，即使參考了別人的筆記仍然一知半解。
TODO :
1. 學習 [Linux kernel coding style](https://www.kernel.org/doc/html/v4.10/process/coding-style.html#macros-enums-and-rtl)
2. 理解 `prepare_percentiles` 中 threshold 的計算方式
$1 - \left(0.5^{10 \times \frac{i + 1}{N\_PERCENTILES}}\right)$
:::
## 在 qtest 提供新的命令 shuffle
閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 實作了新的命令 `shuffle`
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次，結果如下 ：
```
Expectation: 41666
Observation: {'1234': 41560, '1243': 41638, '1324': 42063, '1342': 41818, '1423': 41527, '1432': 41586, '2134': 41484, '2143': 41598, '2314': 41710, '2341': 41996, '2413': 41587, '2431': 41474, '3124': 41600, '3142': 41663, '3214': 41949, '3241': 41435, '3412': 41578, '3421': 41690, '4123': 41695, '4132': 41601, '4213': 41772, '4231': 41550, '4312': 41589, '4321': 41837}
chi square sum: 14.90918254692075
```
從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
看不懂以下
```c
if (likely(bits))
```
參考 [Linux Kernel慢慢學likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) ，在`/usr/src/linux-hwe-6.5-headers-6.5.0-26/include/linux/compiler.h
` 中找到 `likely` 和 `unlikely` 兩個巨集的定義
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
其中 `!!(x)` 技巧可以確保值一定是0或1。
由於規格書沒有提及，網路查閱大致上知道它是為了效能優化，後來閱讀了 [What every Programmer should know about Memory](https://www.akkadia.org/drepper/cpumemory.pdf) 這篇論文的第 57 頁，程式中的條件判斷常常有不平衡的問題，亦即某一種條件成立的可能性遠大於另一種可能，而 `likely` 用於提示編譯器某個條件可能是「真」的，使分支預測偏向於 `likely` 的跳轉指令。如果預測正確，則不需要進行跳轉相關指令。如果預測錯誤，則處理器 pipeline 需要被清空，可能需要多幾個週期。因此當預測大部分時間都是正確時，可以使效能優化。
再來看到函式 `merge` ，其中一段
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
```
在第一周課程後閱讀 [沒有「雙指標」只有「指標的指標」](https://https://hackmd.io/@sysprog/c-pointer#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D)，我仍然搞不太懂，起初一直認為 `*tail` 指向 `a` 所指向的節點，接著 `tail` 指向 `a` 的下一個節點，這樣第二個敘述不就蓋掉第一個了嘛？而且中間完全沒有使用到 `head`，最後卻是回傳 `head`，完全不合理，一定是我哪裡搞錯。於是我放棄畫有指標的有向圖，嘗試把每個變數存取的值以及他們的位址一個一個畫出來。
中間的格子代表變數名稱，左邊的格子代表變數的位址，右邊的格子代表變數存的值。
起始宣告
```c
struct list_head *head, **tail = &head;
```
可以知道 `tail` 裡面存的值是 `&head`
```graphviz
digraph QueueRelationships {
rankdir=LR;
node [shape=record, fontname="Arial"];
element_A [label="{ &tail | tail | &head}", style=filled, fillcolor=gray];
element_A
}
```
所以 `*tail` 其實代表的是 `head` 這個變數，而將 `a` 指派給 `*tail` 實際上是將 `a` 指派給 `head` ，也就是把 `a` 放到 `head` 這個串列上，這個函式最後是要把兩個已排序好的串列合併，最後回傳的是 `head`，這樣一切就說的通了！
理解過後回來看我自己寫的合併排序法，發現其實做的事情一模一樣，差別在於我沒有使用 pointer to pointer 的技巧，導致我前面必須多好幾行先判斷 `head` 的擺放位置，因此我將此一技巧加入我的 sort 中完成改善。
```diff=
struct list_head *mergeTwoLists(struct list_head *first,
struct list_head *second)
{
- struct list_head *head, *result;
+ struct list_head *head, **result = &head;
- if (strcmp(list_entry(first, element_t, list)->value,
- list_entry(second, element_t, list)->value) <= 0) {
- head = first;
- first = first->next;
- if (!first) {
- head->next = second;
- }
- } else {
- head = second;
- second = second->next;
- if (!second) {
- head->next = first;
- }
- }
- result = head;
while (1) {
if (strcmp(list_entry(first, element_t, list)->value,
list_entry(second, element_t, list)->value) <= 0) {
- head->next = first;
- head = head->next;
+ *result = first;
+ result = &first->next;
first = first->next;
if (!first) {
+ *result = second;
- head->next = second;
break;
}
} else {
- head->next = second;
- head = head->next;
+ *result = second;
+ result = &second->next;
second = second->next;
if (!second) {
+ *result = first;
- head->next = first;
break;
}
}
}
- return result;
+ return head;
}
```
## tic-tac-toe
### 整合進 lab0-c
將 [jserv/ttt](https://github.com/jserv/ttt) 專案的程式碼部分整合進 [lab0-c](https://github.com/chishuo9810/lab0-c) ，發現我完全看不懂 Makefile，回去惡補第一週的課程 [Makefile 語法和示範](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)，搭配網路上的入門教學影片[「Makefile的写法」](https://www.youtube.com/watch?v=E1_uuFWibuM&t=759s)。
更新了 Makefile 並在 console.c 中加入指令 ttt，成功執行與人類對弈的井字遊戲。
[commit 8f6e8a0](https://github.com/chishuo9810/lab0-c/commit/8f6e8a0bcef083a8770f30edf7091237aa67b774)
Sign in with Wallet
Connect another wallet