# 2025q1 Homework1 (lab0)
contributed by [<fcu-D0812998>](https://github.com/fcu-D0812998)
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
#### Reviewed by `salmoniscute`
1. 許多中英文穿插的部分沒有添加空白，閱讀起來有點吃力
2. 有些地方的表達不清楚也不通順，以下舉例：
>利用list_first_entry先取得queue的第一個element的地址且因為是remove所以要將移除點的直放進sp中且最多只複製bufsize - 1的字元，因為超過就無法補\0，且最後也需要手補\0來表示結束。
3. 部分 [commit message](https://github.com/sysprog21/lab0-c/commit/87ab87888d7266a4e5341dc27fc5c84a6ceafdbd) 很長，一行內超過了規定的 72 字元，是否 Git pre-commit hook 沒有如預期執行？
## 開發環境
開發與實驗環境
---
~$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
~$lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 6
On-line CPU(s) list: 0-5
供應商識別號： GenuineIntel
Model name: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
CPU 家族： 6
型號： 158
每核心執行緒數： 1
每通訊端核心數： 6
Socket(s): 1
製程： 10
CPU(s) scaling MHz: 61%
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
## queue 實作結果與過程
### q_new
>Create an empty queue whose next and prev pointer point to itself
>Return: NULL for allocation failed
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
if (!new)
return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
使用 `malloc` 動態分配記憶體來建立一個 `struct list_head` 節點，並初始化其 next 和 prev 指向自身，形成一個空佇列。
去規格書參考有關 malloc 相關的資料，看到
>* 7.20.3 Memory management functions
>If the space cannot be allocated, a null pointer is returned.
這跟函式規則 Return: NULL for allocation failed 剛好一致，所以無需判斷。
### q_free
>Free all storage used by queue, no effect if header is NULL
先判斷 queue 中有無節點，有節點的話利用 list_for_each_entry_safe 依序刪除往後的節點，迴圈出來後再 free head 的空間。
```c
void q_free(struct list_head *head)
{
if (!head) {
return;
}
element_t *entry = NULL, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
list_del(&entry->list);
q_release_element(entry);
}
free(head);
}
```
### q_insert_head
>Insert an element in the head.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
Return: true for success, false for allocation failed or queue is NULL
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
int len = strlen(s) + 1;
new->value = malloc(len);
if (!(new->value)) {
free(new);
return false;
}
memcpy(new->value, s, len);
list_add(&new->list, head);
return true;
}
```
先利用 `strlen(s)` 取得 s 的字串長度，再利用 malloc 分配出等成的空間給字串 s，再把 s 的資料複製到 new 中，再利用 `list_add` 插在queue的最前端。
然後根據 C99 規格書中有關 string length 的敘述。
* C99 7.1.1 **Definitions of terms**
> The length of a string is the number of bytes preceding the null character
根據規格書中的說明，在C語言當中，字串的長度不包含結尾的 \0。
再去看看規格書中說明strlen的部分。
* C99 7.21.6.3 **The strlen function**
> The strlen function returns the number of characters that precede the terminating null character
這段說明`strlen` 返回的是 null 字符 `(\0)` 之前的字元數量，所以如果我們需要正確儲存一個C語言字串，應該分配 `strlen(s) + 1`，確保有額外空間存放 `\0`。
接下來要將字串複製到new中，根據規格書中`7.21.2.4`章節說明如果 `src` 的前 n 個字元中沒有` \0 `，則結果不會有` null `終止符，這樣 `new_entry->value` 可能變成未終止的字串，在後續使用時可能導致未定義行為，因此選擇使用 `memcpy`
* C99 7.21.2.4 **The strncpy function**
> The strncpy function copies not more than n characters (characters that followanull character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.
最後再利用 `list_add` 把新的 new 加入到 list 中。
### q_insert_tail
> Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
size_t len = strlen(s) + 1;
new->value = malloc(len);
if (!(new->value)) {
free(new);
return false;
}
memcpy(new->value, s, len);
list_add_tail(&new->list, head);
return true;
}
```
這邊想法跟 `q_insert_head` 一樣，差在最後要使 `list_add_tail` 確保值插入在尾端
### q_remove_head
> Attempt to remove element from head of queue.
Return target element.
Return NULL if queue is NULL or empty.
If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
NOTE: "remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove_node = list_first_entry(head, element_t, list);
list_del(&remove_node->list);
if (sp) {
memcpy(sp, remove_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return remove_node;
}
```
使用 list_first_entry 取得 queue 中第一個元素的指標。因為這是 remove ，接著會透過 list_del 將該元素從鏈結串列中移除。如果提供了 sp 緩衝區，則會將該元素的字串值複製進 sp 中，最多複製 bufsize - 1 個字元，以預留空間在最後補上結束字元 \0 ，避免字串未正確終止的錯誤。最後回傳被移除的節點指標。
### q_remove_tail
> Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove_node = list_last_entry(head, element_t, list);
list_del(&remove_node->list);
if (sp) {
memcpy(sp, remove_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return remove_node;
}
```
跟 `q_remove_head` 一樣，除了前面一開始要使用 `list_last_entry` 。
### q_size
> Return number of elements in queue.
Return 0 if q is NULL or empty
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *node;
int size = 0;
list_for_each (node, head)
size++;
return size;
}
```
`list_for_each` 會保證完整遍歷鏈結串列， `size` 就是鏈結串列內的節點數。
### q_delete_mid
> Delete the middle node in list.
The middle node of a linked list of size n is the
⌊n / 2⌋th node from the start using 0-based indexing.
If there're six element, the third member should be return.
Return true if successful.
Return false if list is NULL or empty.
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return 0;
struct list_head *slow = head->next, *fast = slow->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != head)
slow = slow->next;
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
使用快慢指標找出中間的位置再將此節點刪除。
### q_delete_dup
> Delete all nodes that have duplicate string,
leaving only distinct strings from the original list.
Return true if successful.
Return false if list is NULL.
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
element_t *entry = NULL, *safe;
bool dup = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (entry->list.next != head &&
strcmp(entry->value,
list_entry(entry->list.next, element_t, list)->value) == 0) {
dup = true;
list_del(&entry->list);
q_release_element(entry);
} else if (dup) {
list_del(&entry->list);
q_release_element(entry);
dup = false;
}
}
return true;
}
```
因為要刪除節點所以使用 `list_for_each_entry_safe` ，利用 `strcmp` 判斷 entry 和下一個節點的 value 是否相同，直到判斷到不同，再將 entry 的 list 全部刪除掉。
### q_swap
> Attempt to swap every two adjacent nodes.
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *node = head->next;
while (node != head && node->next != head) {
struct list_head *node2 = node->next;
list_del(node);
list_add(node, node2);
node = node->next;
}
}
```
想法是先設 node 跟 node2 為頭兩個節點，先斷開第一個節點，再將 node2 插入到 node 前面，這樣就完成了 相鄰節點的交換。
### q_reverse
> Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *pos, *safe;
list_for_each_safe (pos, safe, head)
list_move(pos, head);
}
```
使用 `list_move` 從第一個節點開始將每個節點插入在 head 後面，這樣就完成反轉。
### q_reverseK
>Given the head of a linked list, reverse the nodes of the list k at a time.
No effect if queue is NULL or empty. If there has only one element, do nothing.
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
struct list_head *pos, *safe, *cut = head;
int count = 0;
list_for_each_safe (pos, safe, head) {
count++;
if (count % k == 0) {
LIST_HEAD(tmp);
count = 0;
list_cut_position(&tmp, cut, pos);
q_reverse(&tmp);
list_splice(&tmp, cut);
cut = safe->prev;
}
}
}
```
利用 `count` 做記數，當 `count % k == 0` 的話就能確保k個一組做反轉，先用 `list_cut_position` 把要反轉的節點剪切出來，存入 tmp ，再利用剛剛 `q_reverse` 做反轉，再用 `list_splice` 把它存回去。
### q_ascend && q_descend
>Remove every node which has a node with a strictly less value anywhere to the right side of it.
Remove every node which has a node with a strictly greater value anywhere to the right side of it.
No effect if queue is NULL or empty. If there has only one element, do nothing.Memory allocated to removed nodes must be freed.
```c
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *right = list_entry(head->prev, element_t, list);
element_t *left = list_entry(head->prev->prev, element_t, list);
while (&left->list != head) {
if (strcmp(right->value, left->value) < 0) {
list_del(&left->list);
element_t *tmp = left;
left = list_entry(left->list.prev, element_t, list);
free(tmp->value);
free(tmp);
} else {
left = list_entry(left->list.prev, element_t, list);
right = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
```
利用 `strcmp` 比較最後兩個節點的大小，若 left 大於 right 的話，就用 `list_del()` 從 queue 中移除 left ，但不會釋放記憶體，然後再用 `tmp` 暫存 left 指向的節點，這樣我們可以稍後 `free(tmp)`，再將 left 往前指到前一個節點。
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || list_is_singular(head))
return 0;
element_t *right = list_entry(head->prev, element_t, list);
element_t *left = list_entry(head->prev->prev, element_t, list);
while (&left->list != head) {
if (strcmp(right->value, left->value) > 0) {
list_del(&left->list);
free(left->value);
free(left);
left = list_entry(right->list.prev, element_t, list);
} else {
left = list_entry(left->list.prev, element_t, list);
right = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
```
descend 一樣的原理只是將 `strcmp` 中改成大於。
### q_sort
>Sort elements of queue in ascending/descending order.
No effect if queue is NULL or empty. If there has only one element, do nothing.
```c
void _list_merge(struct list_head *left, struct list_head *right, bool descend)
{
struct list_head head;
INIT_LIST_HEAD(&head);
while (!list_empty(left) && !list_empty(right)) {
int cmp = strcmp(list_first_entry(left, element_t, list)->value,
list_first_entry(right, element_t, list)->value);
if ((descend && cmp > 0) || (!descend && cmp <= 0)) {
list_move_tail(left->next, &head);
} else {
list_move_tail(right->next, &head);
}
}
if (!list_empty(right))
list_splice_tail(right, &head);
list_splice(&head, left);
}
```
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *mid = head;
int size = q_size(head) / 2;
for (int i = 0; i < size; i++)
mid = mid->next;
struct list_head left, right;
INIT_LIST_HEAD(&left);
INIT_LIST_HEAD(&right);
list_cut_position(&left, head, mid);
list_cut_position(&right, head, head->prev);
q_sort(&left, descend);
q_sort(&right, descend);
_list_merge(&left, &right, descend);
list_splice(&left, head);
}
```
參考了老師放在作業要求上的[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)知道了 `merge_sort` 的複雜度為 `O(nlogn)` 為所有排序法中複雜度最低的，所以想法是實作 merge sort ，首先先用 `list_cut_position` 且在用**遞迴**的方式將 queue 切成一個一個，再另外寫一個函式 `_list_merge` 主要是判斷傳入的兩個字串比較大小，再用把 `list_splice` 把 head 內的排序結果合併到 left ，讓 left 變成合併後的完整 queue 。
### q_merge
```c
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
else if (list_is_singular(head))
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
queue_contex_t *tmp = NULL,
*first = list_first_entry(head, queue_contex_t, chain);
list_for_each_entry (tmp, head, chain) {
if (tmp && tmp->q && tmp != first) {
list_splice_tail_init(tmp->q, first->q);
first->size += tmp->size;
tmp->size = 0;
}
}
q_sort(first->q, descend);
return first->size;
}
```
想法是將要 merge 的 queue 全都塞進一個 queue 裡，再呼叫剛剛寫好的 `q_sort` 去做排序。
## qtest 提供新的命令 shuffle
看了老師在作業放的 [Fisher–Yates shuffle 演算法](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
j ← random integer such that i ≤ j ≤ n-1
exchange a[i] and a[j]
```
```c
bool q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return false;
srand(time(NULL));
struct list_head *cur = head->next, *tail = head->prev;
for (int i = q_size(head); i > 0; i--) {
int rd_num = rand() % (i);
for (int j = 0; j < rd_num; j++) {
cur = cur->next;
}
struct list_head *tmp = cur->next;
list_move_tail(cur, tail);
tail = tail->prev;
cur = tmp;
}
return true;
}
```
想法很簡單，就先用兩個指標指到 queue 的頭尾，頭代表每次取到隨機數字就可以從頭開始往下指，尾的部分就是交換後完再將尾的部分往前指一個，並在 `qtest.c` 加入 ` shuffle` 命令。
```c
ADD_COMMAND(shuffle,
"Shuffle the queue with Fisher–Yates shuffle algorithm", "");
```
並在` qtest.c `新增` do_shuffle() `測試
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current) {
report(3, "Warning: Try to operate null queue");
return false;
}
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
q_show(0);
return !error_check();
}
```
後來還是測不過，發生錯誤
```
[!] You are not allowed to change the header file queue.h or list.h
```
詢問同學[h0w726](https://hackmd.io/@how123/Bk0vmygske#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle)，才知道需要加入標頭檔。
```c
bool q_shuffle(struct list_head *head);
```
### 統計方法驗證 shuffle
1. 首先先計算 chi-squared test statistic
$$
x^2 = \sum_{i=0}^n\frac{(O_i-E_i)^2}{E_i}
$$
後來先將 test_count 降到1000次先觀察每種結果各自的頻率，發現只有某四種結果有出現過，後來發現是 [srand(time(NULL))](https://stackoverflow.com/questions/64166806/c-any-way-to-initialize-srand-multiple-times)的問題，是因為當你在極短時間內重複呼叫到` srand(time(NULL)) `，那麼 ` time(NULL) `傳回的值是一樣的（精度只有秒），你等於執行了多次 `srand(相同的值)`，導致後續` rand() `產生的亂數序列也一樣。
在測試 shuffle 1000000 次後，每種結果各自的頻率如下表：
| | 觀察到的頻率 | 期待的頻率 | $$\frac{(O_i-E_i)^2}{E_i}$$ |
| ------------ | ------------ | ---------- | --- |
|[1, 2, 3, 4]|41526|41666|0.47040752652042434|
|[1, 2, 4, 3]|41810|41666|0.497671962751404|
|[1, 3, 2, 4]|41780|41666|0.3119089905438487|
|[1, 4, 2, 3]|41522|41666|0.497671962751404|
|[1, 4, 3, 2]|42020|41666|3.0076321221139537|
|[2, 1, 3, 4]|41352|41666|2.3663418614697833|
|[2, 1, 4, 3]|41724|41666|0.08073729179666875|
|[2, 3, 1, 4]|41519|41666|0.5186242979887679|
|[2, 3, 4, 1]|41435|41666|1.2806844909518553|
|[2, 4, 1, 3]|41776|41666|0.2904046464743436|
|[2, 4, 3, 1]|41520|41666|0.5115921854749677|
|[3, 1, 2, 4]|41725|41666|0.08354533672538761|
|[3, 1, 4, 2]|41351|41666|2.381438103009648|
|[3, 2, 1, 4]|41727|41666|0.08930542888686219|
|[3, 2, 4, 1]|41968|41666|2.1889310228963663|
|[3, 4, 1, 2]|41685|41666|0.00866413862621802|
|[3, 4, 2, 1]|41603|41666|0.09525752412038592|
|[4, 1, 2, 3]|41779|41666|0.306460903374454|
|[4, 1, 3, 2]|41227|41666|4.625378006048097|
|[4, 2, 1, 3]|41592|41666|0.13142610281764508|
|[4, 2, 3, 1]|41920|41666|1.5484087745403927|
|[4, 3, 1, 2]|41957|41666|2.0323765180242885|
|[4, 3, 2, 1]|41604|41666|0.09225747611961792|
|Total|||23.417126674026782|
2. **決定自由度（degrees of freedom）**
* suffle 4個數字所以有24種結果，所以自由度為23
3. **選擇顯著水準**
* alpha 設為常見的0.05
* 從卡方分布表找合適的 P value，自由度為23，$X^2$ 為 23.417126674026782，因為 22.037 < 23.417126674026782 < 26.018，於是 P value 介於 0.5 和 0.3 之間。
4. **統計檢定的結果不拒絕虛無假說**
* 因為 P value（0.3~0.5）> alpha（0.05），統計檢定的結果不拒絕虛無假說($H_0$)
* 從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的
## 研讀論文〈Dude, is my code constant time?〉
[Side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack) 是一種不是針對密碼學演算法本身的破解方式，而是利用程式或硬體實作中非預期的特徵，來側面推測機密資訊。非預期的特徵就像是 [Timing Attack](https://en.wikipedia.org/wiki/Timing_attack)，它會透過觀察程式執行所花的時間差異，來分析輸入資料是否接近正確。
比方說，某段程式會一個字元一個字元地比對密碼，只要遇到不符就立即結束並回傳錯誤。
攻擊者可以藉由大量嘗試，觀察執行時間的長短，就可能一步步推敲出正確密碼的內容。
為了對抗這種攻擊，現在已經有一些工具可以用來檢測程式是否有時間上的漏洞，像是
* ctgrind：是 Valgrind 的延伸工具，透過動態追蹤程式的行為。
* ctverif：則是利用形式化驗證進行靜態分析。
但這些工具有個共通限制，它們需要對底層硬體（如 CPU）做詳細建模。而這在實務上很困難，因為晶片製造商往往不會公開這些內部細節。
為了解決這個方法這篇論文就開發了一套叫做 dudect 的工具，它不透過靜態分析，而是直接執行程式，並大量蒐集執行時間，再用統計方法分析差異。
這種方式稱作 leakage detection test，它只需要在目標平台上執行就可以使用，完全不需要了解或模擬硬體的細節。因此 dudect 特別適合用來驗證程式在實際環境下是否為 constant-time，不受限於特定硬體或理論模型。
方法部分主要分成三種
* **Step 1: Measure execution time**
測試時會使用兩組不同特性的輸入資料，在同樣的環境下計算他們兩者的時間分佈，分別
一組是固定輸入，另一組是隨機輸入
* **Step 2: Apply post-processing**
a) Cropping : dudect 是靠收集執行時間來做統計分析的，但實際在跑測試時，這些時間數據中可能會混入 Noise ，像是測量過程被 OS 中斷、背景程式干擾，實際上 dudect 在實作上會刪除過於極端的時間
b) Higher-order preprocessing 統計測試可以透過 high-order preprocessing 得到更有效的分析結果，因為在有些情況下，洩漏時間不一定在平均值能發現。
* **Step 3: Apply statistical test**
dudect 會將之前收集到的執行時間分為兩組，使用統計檢定來驗證「這兩組資料是否來自同一個分布」。主要採用 Welch’s t-test，來判斷兩組平均值是否顯著不同。如果有差異，就代表該程式可能會洩漏 timing 資訊，不符合 constant-time 的安全要求。
### 解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
當我們在進行統計檢定時，通常會用常態分布來估計資料的行為，但這只有在樣本數夠多的情況下才適用。當樣本數較小時，資料本身的變異性較大，這時使用常態分布可能會低估極端值出現的機率，導致檢定結果不夠保守。為了解決這個問題，就會使用 Student’s t-distribution（學生 t 分布）。t 分布與常態分布長得類似，都是中間高、兩側低的鐘形曲線，不同的是 t 分布在自由度較小時，兩側尾巴會更厚，表示更高的極端值機率，能反映小樣本時的不確定性。隨著樣本數增加，t 分布會漸漸趨近標準常態分布。這種分布通常會用在像 t-test 這類的假設檢定中，特別是當我們要比較兩組平均值是否顯著不同，而又不知道母體標準差時。在 dudect 這類工具中，Student’s t-distribution 被用來統計分析「固定輸入」與「隨機輸入」在執行時間上的差異，進而判斷一段程式是否具備 constant-time 性質，避免時間洩漏發生。
### 解釋本程式的 "simulation" 模式
在 lab0-c 中，simulation 模式被設計來測試 queue 函式的時間複雜度是否為constant-time。就分成剛剛上面提及的三步驟來做分析
* **Step 1: Measure execution time**
首先要計算兩組不同特性的輸入資料的時間差，在 `/dudect/fixture.c` 可以看到
```c
exec_times[i] = after_ticks[i] - before_ticks[i];
```
這段程式會把每次操作的「結束時間 - 開始時間」算出來，記錄成每一次操作的實際執行時間，再來丟進下面一點的程式碼中
```c
int64_t difference = exec_times[i];
t_push(t, difference, classes[i]);
```
把所有執行時間資料根據類別(固定or隨機)分組後，餵進 t-test 所需的統計計算中
* **Step 2: Apply post-processing(在 lab0-c 實作 percentile )**
因為 lab0-c 沒有具備 percentile 的處理，所以參考了老師給的[oreparaz/dudect](https://github.com/oreparaz/dudect)，主要核心在這段程式碼
```c
/*
set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that.
*/
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
先利用 q_sort 將執行時間排序從小到大，會利用 cmp 去比較執行時間大小
```c
static int cmp(const int64_t *a, const int64_t *b) {
if (*a == *b)
return 0;
return (*a > *b) ? 1 : -1;
}
```
percentile 則是利用來判斷在這個百分比下對應到的是排序好的執行時間陣列裡的哪一個地方
```c
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
....
return a_sorted[array_position];
```
所以這邊就要來在 lab0 中實作 percentile 的功能，先把 cmp 跟 percentile 這兩個 function 放入 lab0-c/dudect/ttest.c 以方便 fixture.c 呼叫。
而在 fixture.c 中在 doit 中放入 prepare_percentiles 函式讓他能避免掉極端值影響。
* **Step 3: Apply statistical test**
最後在 t_compute() 中利用公式
$$t = \frac{\bar{x}_0 - \bar{x}_1}{\sqrt{ \frac{s_0^2}{n_0} + \frac{s_1^2}{n_1} }}
$$
分子為 兩組輸入的執行時間平均值
分母為 「標準誤差（standard error）」，是衡量兩組平均值的差異有多可靠的依據
而根據[論文](https://ieeexplore.ieee.org/document/7927267)中提及
```
A t value larger than 4.5 provides strong statistical evidence that the distributions
are different.
```
當 t 值絕對值大於 4.5，表示兩個輸入類別的執行時間分布統計上有顯著差異
## 用Valgrind分析記憶體問題
觀看老師的[以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b#%E4%BB%A5-Valgrind-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E5%95%8F%E9%A1%8C)後，使用指令
```shell
$ make valgrind
```
```shell
$ valgrind -q --leak-check=full [執行程式檔]
```
來檢測我 queue 的操作會發生什麼樣的記憶體問題，因為我在 make valgrind 的時候分數太低，多半時前面的 test 就會出現問題，我就用 valgrind 去測試我的 qtest ，發現在 remove head 的時候會發生
```
==44119== Invalid read of size 8
==44119== at 0x4852E17: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==44119== by 0x11009F: memcpy (string_fortified.h:29)
==44119== by 0x11009F: q_remove_head (queue.c:83)
==44119== by 0x10CAC7: queue_remove (qtest.c:356)
==44119== by 0x10CC6F: do_rh (qtest.c:413)
==44119== by 0x10E843: interpret_cmda (console.c:181)
==44119== by 0x10EE08: interpret_cmd (console.c:201)
==44119== by 0x10F8F2: run_console (console.c:659)
==44119== by 0x10DC32: main (qtest.c:1465)
==44119== Address 0x4b70a10 is 6 bytes after a block of size 42 alloc'd
==44119== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==44119== by 0x10FA01: alloc (harness.c:146)
==44119== by 0x10FB54: test_malloc (harness.c:176)
==44119== by 0x10FF64: q_insert_head (queue.c:46)
==44119== by 0x10CF1B: queue_insert (qtest.c:235)
==44119== by 0x10D0EC: do_ih (qtest.c:283)
==44119== by 0x10E843: interpret_cmda (console.c:181)
==44119== by 0x10EE08: interpret_cmd (console.c:201)
==44119== by 0x10F8F2: run_console (console.c:659)
==44119== by 0x10DC32: main (qtest.c:1465)
```
這段 valgrind 報錯意思看起來是說我原本在 q_remove_head 中有撰寫是有關 memcpy 非法讀取的記憶體位址，於是我去察看規格書發現在 7.21.2.1 跟 7.21.2.4 有描述有關 memcpy 跟 strncpy 的差別，意思是說今天當我來源字串長度小於目的 buffer 大小時 memcpy 是不會自動補 \0 的，而 strncpy 則能自動幫我填補後面空閒的記憶體位址，若使用 memcpy 就會讀到未配置的記憶體，進而產生 [Buffer Over-read](https://en.wikipedia.org/wiki/Buffer_over-read) 的狀況。
>* 7.20.3 Memory management functions
>The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1.
>* 7.21.2.4 The strncpy function
>The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1.
調整成 strncpy 就能通過測試，但在最後的 constant-time 的 valgrind 測試沒有通過測試
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
==49952== 4,896 bytes in 102 blocks are definitely lost in loss record 1 of 8
==49952== at 0x484D953: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==49952== by 0x1113D3: init_once (fixture.c:188)
==49952== by 0x1113D3: test_const (fixture.c:201)
==49952== by 0x11145B: is_insert_tail_const (fixture.c:221)
==49952== by 0x10CCB8: queue_insert (qtest.c:193)
==49952== by 0x10D0D0: do_it (qtest.c:289)
==49952== by 0x10E843: interpret_cmda (console.c:181)
==49952== by 0x10EE08: interpret_cmd (console.c:201)
==49952== by 0x10F097: cmd_select (console.c:593)
==49952== by 0x10F975: run_console (console.c:673)
==49952== by 0x10DC32: main (qtest.c:1465)
==49952==
==49952== 4,896 bytes in 102 blocks are definitely lost in loss record 2 of 8
```
沒通過第一點是我在 doit() 中 calloc 了空間給 ctx->percentiles ，但後面我沒有 free 掉，造成 Memory Leak 。
第二點想了很久，最後從錯誤來看發現在 test_const 中每次初始化一個 dudect_ctx_t ，但都沒有對應的 free ，後來新增了 free_ctx 函式將每次初始化的 dudect_ctx_t 給 free 掉就能通過測試了。
```c
static void free_ctx(dudect_ctx_t *ctx)
{
for (int i = 0; i < DUDECT_TESTS; i++) {
if (ctx->ttest_ctxs[i]) {
free(ctx->ttest_ctxs[i]);
ctx->ttest_ctxs[i] = NULL;
}
}
}
```
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案
### [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 加入lab0-c
新增 list_sort.c 進 lab0-c 中，並在 qtest.c 引入 list_sort 函式原型
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
新增 compareFun 函式和宣告 list_cmp_func_t 函式原型，用來當作 list_sort.c 內比較函數的描述實作
```c
const int compareFun(void *priv,
const struct list_head *a,
const struct list_head *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
```c
typedef int
__attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
const struct list_head *,
const struct list_head *);
```
在看 list_sort.c 中看到這樣的邏輯
```c
if (likely(bits))....
```
尋找了一下他的定義，它是用來給編譯器分支預測的提示，幫助 CPU 提高 if 判斷效率， likely() 用來提示編譯器'x'為真的機率比較高，而 unlikely() 用來提示編譯器'x'為假的機率比較高
```c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
```
接下來新增 linux_sort 的指令
```c
ADD_COMMAND(linux_sort,"Sort queue in ascending/descening order use list_sort", "");
```
並模仿 do_sort 去實作 do_linux_sort
```diff
if (current && exception_setup(true))
- q_sort(current->q, descend);
+ list_sort(NULL, current->q, compareFun);
```
實作後結果
```
cmd> new
l = []
cmd> ih RAND 10
l = [qykegxhwa qtbruuo nlpmx nalrpqcx sfexj ildzncfyf jwngxayvu yszdgnr pttec kzjlwygen]
cmd> linux_sort
l = [ildzncfyf jwngxayvu kzjlwygen nalrpqcx nlpmx pttec qtbruuo qykegxhwa sfexj yszdgnr]
```
### 比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
研讀 [運用 Perf 分析程式效能並改善](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux-perf#%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4%E6%A6%82%E8%A6%BD)
首先先新增兩個目錄分別為 perf_test 和 perf_report ，分別為命令檔和效能分析結果
```
.
├── perf_test
├── test-sort-1000000.cmd
├── test-sort-100000.cmd
├── test-sort-10000.cmd
├── test-sort-1000.cmd
├── test-linux_sort-1000000.cmd
├── test-linux_sort-100000.cmd
├── test-linux_sort-10000.cmd
└── test-linux_sort-1000.cmd
```
```
.
├── perf_report
├── test-sort-1000000_perf_report
├── test-sort-100000_perf_report
├── test-sort-10000_perf_report
├── test-sort-1000_perf_report
├── test-linux_sort-1000000_perf_report
├── test-linux_sort-100000_perf_report
├── test-linux_sort-10000_perf_report
└── test-linux_sort-1000_perf_report
```
設定自動執行檔 perf_report.sh
```shell
#!/bin/bash
for cmd_file in ./perf_test/test*.cmd
do
outputfile=$(echo "${cmd_file}" | sed 's/perf_test/perf_report/')
perf stat --repeat 5 -o "${outputfile%.cmd}"_report -e cache-misses,branches,instructions,context-switches,cache-references,cycles ./qtest -f ${cmd_file}
done
```
當中遇到了權限問題，所以提高 perf_report.sh 的權限
```cmd
chmod +x perf_report.sh
```
執行在 ./perf_report 資料夾中的 `test.sh` 可以印出所有 report 的內容可以觀看，以下是執行結果
- [ ] list_sort
| #Node | cache-misses | branches | instructions | contex switchs | times |
| ------- | -------------|-------------|----------------|----------------|---------|
| 1000 | 2,833,095 | 112,257,782 | 631,494,835 | 374 | 0.5645 |
| 10000 | 3,013,495 | 118,546,266 | 688,760,988 | 371 | 0.5681 |
| 100000 | 8,861,869 | 187,052,969 | 1,289,263,126 | 369 | 0.6069 |
| 1000000 | 129,381,717 | 902,558,519 | 7,431,136,094 | 391 | 2.5278 |
- [ ] sort
| #Node | cache-misses | branches | instructions | contex switchs | times |
| ------- | -------------|-------------|----------------|----------------|---------|
| 1000 | 2,830,342 | 112,566,306 | 633,336,904 | 372 | 0.600 |
| 10000 | 3,006,941 | 119,555,156 | 693,769,085 | 367 | 0.5055 |
| 100000 | 9,590,520 | 196,632,207 | 1,330,031,085 | 366 | 0.6264 |
| 1000000 | 154,280,201 | 980,762,759 | 7,779,900,456 | 394 | 2.7961 |
很明顯 list_sort 不管在 cache-misses 、 branches 、 instructions 以及 times 上都比 sort 來的要好，在節點變多的情況下越是明顯，sort 因為每次排序時會切斷並重建 linked list ，導致記憶體存取分散，因此 cache-misses 增高。同時，它在合併時需頻繁比較節點值，造成分支預測不穩定，讓 branches 和 instructions 數量上升。而 Linux 的 list_sort 採用 bottom-up merge sort 與桶式合併邏輯，在固定模式下合併節點，避免重複記憶體分配與過多邏輯分支。
Sign in with Wallet
Connect another wallet