# 2025q1 Homework1 (lab0)
contributed by < `wurrrrrrrrrr` >
### Reviewed by `nyraa`
> 部分 inline code 前後沒有插入空白。
依照規範，在英文單字建議都要插入空白
> q_free() 中可以使用對於刪除節點友善的巨集
`list_for_each_safe` 這個巨集可以刪除當個節點而不影響迭代， `q_release_element` 這個巨集可以釋放一個節點的記憶體空間。
### Reviewed by `liangchingyun`
> 空格的使用需統一，如 [q_new()](https://hackmd.io/yn0qmHn_TXaR0wjX-H2pbA?both#q_new) 中的敘述
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU family： 6
model： 165
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Socket(s): 5
CPU max MHz: 4800.0000
CPU min MHz: 800.0000
BogoMIPS: 5799.77
```
在開始前我先詳閱了這個[好的 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/) 一個好的 commit message 是非常重要的。
**其中關鍵的就是==以下這7點:==**
1. 用一行空白行分隔標題與內容
1. 限制標題最多只有 50 字元
1. 標題開頭要大寫
1. 標題不以句點結尾
1. 以祈使句撰寫標題
1. 內文每行最多 72 字
1. 用內文解釋 what 以及 why vs. how
## 實作指定佇列操作
### q_new()
由於之前沒有先看過大概的程式碼就開始實做，因此原本不是用`INIT_LIST_HEAD` 初始化，後來才在 `list.h` 檔中發現到這個函式就改為使用 `INIT_LIST_HEAD` 初始化 head。
```c
struct list_head *q_new()
{
struct list_head *new_qhead =
(struct list_head *) malloc(sizeof(struct list_head));
if (!new_qhead) {
return NULL;
}
INIT_LIST_HEAD(new_qhead);
return new_qhead;
}
```
經過同學對我的提問我才發現到我並不知道 malloc 這個函式分配失敗是否是回傳 NULL ，因此我查閱了 c99 並看到相關的論述。
**c99(7.20.3)**
> The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementationdefined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object
**c99(7.20.3.3)**
>The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.
Returns
The malloc function returns either a null pointer or a pointer to the allocated space.
### q_insert_head() && q_insert_tail()
分別利用了 `list.h` 檔中的 `list_add` 和 `list_add_tail` 來去完成實做，但在經由友人的提醒之後發現到其實並不需要實做兩個類似的函式，只須完成其中之一的函式，而另一個函式只要呼叫已經實做完成的那個函式即可，改進完的程式碼更為優雅更簡潔。
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
return q_insert_head(head->prev, s);
}
```
### q_free()
在實做之前我先閱讀了 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 來去了解到 `container_of` 的實作手法，並把它引入我的實做當中。
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if(!head) {
return ;
}
struct list_head * temp_ptr = head->next;
while(temp_ptr != head) {
temp_ptr = temp_ptr->next;
free(list_entry(temp_ptr->prev, element_t, list)->value);
free(list_entry(temp_ptr->prev, element_t, list));
}
free(head);
}
```
### q_remove_head() && q_remove_tail()
在開始實做前我發現到有兩個函式都能用來複製字串，一個為 `strncpy` 另一個為 `strcpy` ，於是我好奇兩個有什麼樣的差異，因此我看了 c99 才知道兩個的不同， `strcpy` 來源和目標 (destination) 的記憶體區域不應該有重疊，而另一個 `strncpy` 則是不會複製`\0`。
**c99(7.21.2.3)**
>The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.
**c99(7.21.2.4)**
>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 If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.
在原本的實做中我使用了 bufsize 而不是 ==bufsize-1== 結果會導致以下的錯誤。
```diff
if (sp) {
memset(sp, '\0', bufsize);
- strncpy(sp, container_of(head->next, element_t, list)->value,
- bufsize);
+ strncpy(sp, container_of(head->next, element_t, list)->value,
+ bufsize-1);
}
```
這是其中一個的錯誤訊息:
```
+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value meerkat_panda_squirrel_vulture_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
```
於是我開始找尋該測試的 cmd 檔案發現到這裡的 `option` 剛好設置為==字串的長度== ，因此我的 bufsize 會剛好等於字串的長度導致讀出來的字串會沒有 `\0` 造成上述的錯誤。
```
option length 30
rh meerkat_panda_squirrel_vulture
```
### q_delete_mid()
在實做這題前我先解決了 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 這題我的解法是先製作了一個 `fake` 節點來去指向 `head` ，再用 `first` 去指向 `middle` 的前一個節點
[圖參考來源](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List)
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>2 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
first;
last;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
first -> 7:ref;
last -> 8:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>2 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
first;
last;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
first -> 5:ref;
last -> 2:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
first;
last;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
first -> 5:ref;
}
```
但在 lab0-c 是雙向鏈結因此不用跑過串列一次去知道串列的大小，只需要一個指向 `head->next` 而另一個指向 `head->prev` ，然後當兩個指標相遇或是第一個指標的 `next` = 第二個指標時就為 `middle` 。
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head)) {
return false;
}
struct list_head *first = head->next;
struct list_head *last = head->prev;
while (first != last && first->next != last) {
first = first->next;
last = last->prev;
}
list_del(last);
free(list_entry(last, element_t, list)->value);
free(list_entry(last, element_t, list));
return true;
}
```
### q_swap()
這題對應到 [Leetcode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/) 我使用兩個指標來去指向一個節點和該節點的下一個節點，並使用 `list.h` 中所提供的 `list_move()` 去做交換。
[圖參考來源](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List)
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>2 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
l1;
l2;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
l1 -> 5:ref;
l2 -> 2:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>2 |<ref>}"];
2 [label = "{<data>5 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
l2;
l1;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
l2 -> 5:ref;
l1 -> 2:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>7 |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>2 |<ref>}"];
2 [label = "{<data>5 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
l1;
l2;
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
l1 -> 9:ref;
l2 -> 1:ref;
}
```
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *l1 = head->next;
struct list_head *l2 = head->next->next;
while (l1 != head && l2 != head) {
list_move(l1, l2);
l1 = l1->next;
l2 = l1->next;
}
}
```
### q_reversek()
實做之前我先完成 [Leetcode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/) 這題中我先實作一個函式，該函式的功用為傳入一個串列就能將該==串列反轉==，再用兩個指標去紀錄上一個的 ==end node== 跟當前組的 ==end node==。(以下例子 k = 3)
[圖參考來源](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List)
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>dummy |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>8 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>2 |<ref>}"];
10 [label = "{<data>10 |<ref>}"];
11 [label = "{<data>11 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none2 [label = "NULL"];
prevGroup;
tail;
edge[weight=1];
edge[weight=2];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 10 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
10:ref:c -> 11 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
11:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
prevGroup -> 7:ref;
tail -> 9:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>dummy |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>2 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>8 |<ref>}"];
10 [label = "{<data>10 |<ref>}"];
11 [label = "{<data>11 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none2 [label = "NULL"];
prevGroup;
tail;
edge[weight=1];
edge[weight=2];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 10 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
10:ref:c -> 11 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
11:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
prevGroup -> 2:ref;
tail -> 11:ref;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>dummy |<ref>}"];
1 [label = "{<data>1 |<ref>}"];
8 [label = "{<data>2 |<ref>}"];
5 [label = "{<data>5 |<ref>}"];
2 [label = "{<data>8 |<ref>}"];
10 [label = "{<data>10 |<ref>}"];
11 [label = "{<data>11 |<ref>}"];
9 [label = "{<data>9 |<ref>}"];
node [shape=none]
none2 [label = "NULL"];
prevGroup;
tail;
edge[weight=1];
edge[weight=2];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 10 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
10:ref:c -> 11 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
11:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
prevGroup -> 2:ref;
tail -> 9:ref;
}
```
後來我參考了[ vax-r ](https://hackmd.io/@vax-r/linux2024-homework1#q_reverseK)來完成相關的實作。
### q_ascend() && q_descend()
在實做這個函式之前我先完成相關的 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/) 發現到這個函式基本是循著==嚴格遞增==或==嚴格遞減==的方式，像是下面是單向鏈結 `q_descend()` 的例子。可以看到最後結果為嚴格遞減，由於這題是雙向鏈結串列因此只需從 ==head->prev== 開始往 prev 找尋==嚴格遞增==，而 `q_ascend()` 是從==head->next==開始往 `next` 找尋==嚴格遞增==。[圖參考來源](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List)
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>5 |<ref>}"];
1 [label = "{<data>2 |<ref>}"];
8 [label = "{<data>13 |<ref>}"];
5 [label = "{<data>3 |<ref>}"];
9 [label = "{<data>3 |<ref>}"];
2 [label = "{<data>4 |<ref>}"];
3 [label = "{<data>8 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 8 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
8:ref:c -> 5 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 9 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
9:ref:c -> 1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
7 [label = "{<data>13 |<ref>}"];
3 [label = "{<data>8 |<ref>}"];
node [shape=none]
none1 [label = "head"];
none2 [label = "NULL"];
edge[weight=2];
none1 -> 7 [arrowhead=vee];
7:ref:c -> 3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=0];
}
```
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return 0;
}
char *tmp_max = list_entry(head->prev, element_t, list)->value;
struct list_head *cur = head->prev->prev;
while (cur != head) {
element_t *cur_node = list_entry(cur, element_t, list);
char *tmp1 = cur_node->value;
if (strcmp(tmp1, tmp_max) > 0) {
tmp_max = tmp1;
cur = cur->prev;
}
else {
cur = cur->prev;
element_t *free_node = list_entry(cur->next, element_t, list);
list_del(&free_node->list);
free(free_node->value);
free(free_node);
}
}
return q_size(head);
}
```
### q_sort()
在實做前我先詳閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 來了解相關的實做，在詳閱後發現要通過指定測資的排序方法只有 `merge sort` ，而其他的排序方式都會達不成測資所要求的==時間複雜度==和 ==stable== ，而 `merge sort` 相關的實作方法有兩種，這兩種的方式都是遞迴下去切割元素只有在 `merge` 所採用的策略有所不同，而一開始我所採用的是遞迴版本的 `merge` 。
```c
// Merges two sorted lists into one sorted list
struct list_head *merge(struct list_head* l1, struct list_head* l2, bool descend) {
// merge with recursive
if (!l2) {
return l1;
}
if (!l1) {
return l2;
}
element_t *node1 = list_entry(l1, element_t, list);
element_t *node2 = list_entry(l2, element_t, list);
if (descend) {
if(strcmp(node1->value, node2->value) < 0) {
l2->next = merge(l1, l2->next, descend);
return l2;
}
else {
l1->next = merge(l1->next, l2, descend);
return l1;
}
}
else {
if(strcmp(node1->value, node2->value) <= 0) {
l1->next = merge(l1->next, l2, descend);
return l1;
}
else {
l2->next = merge(l1, l2->next, descend);
return l2;
}
}
}
```
但發現到不管如何修改我的程式都無法通過測試，原本以為是我的程式出了問題，但反覆觀察程式碼後都找不出原因，後來查看了該測資發現到它是塞入了大量的字串去做排序，由於前面幾筆有關於排序的測試都能通過，而本項測試與前面測試最大的不同只在於資料數量的不同，因此我猜測是否為 `merge` 這個函式遞迴的次數太多導致 [stack overflow](https://zh.wikipedia.org/zh-tw/Stack_Overflow)的問題，所以我調整了測資來驗證我的猜測是否屬實，發現到確實是遞迴版本的 `merge` 導致我的 ==stack overflow== 。
```
cmd> new
l = []
cmd> ih dolphin 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
程式記憶體區段錯誤 (核心已傾印)
```
```
cmd> new
l = []
cmd> ih dolphin 10000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 10000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd>
```
以下為修改後不是遞迴的版本:
```c
struct list_head *merge(struct list_head *l1,
struct list_head *l2,
bool descend)
{
if (!l2)
return l1;
if (!l1)
return l2;
struct list_head dummy;
struct list_head *temp = &dummy;
dummy.next = NULL;
dummy.prev = NULL;
while (l1 && l2) {
element_t *node1 = list_entry(l1, element_t, list);
element_t *node2 = list_entry(l2, element_t, list);
if (!descend) {
if (strcmp(node1->value, node2->value) <= 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
} else {
if (strcmp(node1->value, node2->value) < 0) {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
} else {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
}
}
}
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return dummy.next;
}
```
### q_merge()
#### lab0-c 中 queue_contex_t 與 element_t 的結構是下列這張圖:（trace-03）用到了merge
---
經過我的測試發現有兩個 id 為 0 的 `queue_contex_t` ，但我並不清楚有何作用。[圖參考來源](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-e)
此題是要將每個 `queue_contex_t` 結構上 `head` 節點所指的鏈結串列去做合併，而每個合併的串列都是事先排序好的因此我們可以運用到上方的 `merge` 函式來做合併，確定好方向後開始以下的實做，當最後都合併完之後必須要將鏈結串列去做重新的串接，因為我是將其視為單向鏈結串列來去實做因此只有保證鏈結串列往 `next` 的方向是正確的。
```c
/* Merge all the queues into one sowu@wu-Pro-E500-G6-WS720T:~/linux2025/lab0-c$ ./qtest
cmd> new
l = []
'cmd> ih RAND 10
l = [ppdaxq zrsqbseq jqrwe rmyxq tolkbcz fksdh mcbdmci arotglxvf wlwtuxdm zlkfbs]
cmd> option entropy 1
cmd> show
Current queue ID: 0
l = [ppdaxq(26.56%) zrsqbseq(29.69%) jqrwe(26.56%) rmyxq(26.56%) tolkbcz(32.81%) fksdh(26.56%) mcbdmci(26.56%) arotglxvf(37.50%) wlwtuxdm(32.81%) zlkfbs(29.69%)]
cmd>
cmd>
Freeing queuerted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
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 *node = list_entry(head->next, queue_contex_t, chain);
node->q->prev->next = NULL;
struct list_head *temp = node->chain.next;
for (int i = 0; i < ((node->size) - 1); i++) {
queue_contex_t *next_node = list_entry(temp, queue_contex_t, chain);
next_node->q->prev->next = NULL;
node->q->next = merge(node->q->next, next_node->q->next, descend);
INIT_LIST_HEAD(next_node->q);
temp = temp->next;
}
struct list_head *curr = node->q->next;
struct list_head *pre = node->q;
while (curr->next != NULL) {
curr->prev = pre;
pre = curr;
curr = curr->next;
}
curr->prev = pre;
curr->next = node->q;
node->q->prev = curr;
return q_size(node->q);
}
```
### 目前測試結果為==95/100==。
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
這篇論文的目標是檢測加密演算法是否有時間變異，以確保其在真實硬體上不會因為執行時間不同而洩漏秘密資訊。
這篇論文測量加密函式在兩組不同輸入資料類別下的執行時間，然後檢查這兩組計時分佈是否在統計上存在顯著差異。在測試中第一組輸入數據被==固定為一個恆定值==，而第二組輸入數據則在每次測量時==隨機選取==，這種測試叫做 `fix-vs-random test` 。
**null hypothesis**
這篇論文主要是用應用統計檢定來試圖推翻 ==null hypothesis==，也就是「兩組執行時間的分佈是相等的」這個假設，而這個作者使用 Welch’s t-test 的方式去驗證兩組數據的均值是否相等，更嚴格的說兩組結果的變異數 (variance) 也應該相等，如果這個檢定失敗（即結果顯示兩組均值不同），那麼就明顯表示存在一階時間資訊洩漏。
```
static void measure(dudect_ctx_t *ctx) {
for (size_t i = 0; i < ctx->config->number_measurements; i++) {
ctx->ticks[i] = cpucycles();
do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
}
for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
}
}
```
### simulation
在 `qtest.c` 中可以看到下列幾行，當 `simulation` 被設為 1 時會執行測試指令是否為 `constant time` 。這個模式下總共會有10000次的測試總共十輪，只要其中一次小於 lab0-c 所設定的 t 值時就視為常數時間。
```c
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok =
pos == POS_TAIL ? is_insert_tail_const() : 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;
```
論文中在統計處理前，他們對測量數據進行預處理，包括==丟棄超過某個百分位數 p 的數據==。
在論文中有提到典型的計時分佈通常大多數執行時間較短，但仍然會有一些較長的執行時間，導致分佈偏向 `positively skewed` 為以下這張圖:
>Typical timing distributions are positively skewed towards larger execution times. This may be caused by measurement artifacts, the main process being interrupted by the OS or other extraneous activities
**positively skewed**
[圖參考來源](https://corporatefinanceinstitute.com/resources/data-science/positively-skewed-distribution/)
因此論文有提到截尾（Cropping）：限制測量範圍，例如只保留較短的執行時間數據，去掉異常長的數據點。
>In this case, it may be convenient to crop the measurements (or discard measurements that are larger than a fixed, class-independent threshold).
根據我對[ dudect ](https://github.com/oreparaz/dudect/blob/master/src/dudect.h的觀察可以看到)原始程式碼的觀察我發現`prepare_percentiles`這個函式會呼叫一個`percentile`的函式，而這個函式的輸入為一個排序完的`exec_times`陣列和你測試資料的數量，最後還有一個`double`的浮點數，這個浮點數的作用為你要裁切你資料％數的位置把超過這個％數後的資料去捨棄掉。
```c
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);
}
```
可以看到上述程式有一個 ==1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)== ，這個式子就是剛剛所提到的浮點數，而當我們實際畫圖則會發現到這個式子收斂的速度非常的快，因為就像上面提到的典型的計時分佈通常大多數分佈偏向 `positively skewed` 所以要專注在裁切掉後半部的部份。
可改善的地方在於原始程式碼中只使用了一個陣列去儲存程式執行時間，
而在 lab0-c 中我發現到是使用了兩個陣列去保存執行前執行後的數值分別為 ==before_ticks[i]== 跟 ==after_ticks[i]== 。
```c
for (size_t i = 0; i < ctx->config->number_measurements; i++) {
ctx->ticks[i] = cpucycles();
do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
}
for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
}
```
這段是用 `percentile` 這個函式先算出要的百分點位置在陣列中哪個 `index` ，並且把超過這個 `index` 的資料去做捨棄。
```c
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
```
在原本的程式中參考了[ var-x ](https://hackmd.io/@vax-r/linux2024-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)的程式，將 `percentile` 和 `prepare_percentiles` 引入到 `fixture.c` 中並把上述的 `ctx->percentiles[i]` 替換成 `exec_times[i]` ，這樣可以讓大部分執行時間數據反映較長的執行時間，進而更能凸顯整體效能瓶頸。。
但我發現到在我原本的實做中我的排序並沒有把標籤和執行時間去做配對，這樣會導致排序完後的執行時間跟標籤會和原本有所差異，沒有配對的話就像是將標籤去隨機分配到你已經排序完後的資料上，這在原始程式碼會是正確的，因為在原始程式碼中==它做排序只是為了抓到上述所說的百分點位==置不會改變標籤，而在我的程式碼實做中則是對執行時間做排序後直接使用，因此我先做了個結構叫做 `Pair` 來將執行時間和 `class` 做配對，因此當 `qsort` 完執行時間後可以根據這個配對對 `class` 做排序，這樣確保了執行時間不會因為做排序而改變它對應的 `class` 。
而當我在實做之前我先去量測了 `fix` 跟 `random` 的執行時間，結果發現到 `fix` 跟 `random` 的執行時間有極大的落差，下列為測試執行時間的結果( 當 `fix` 為 ==0== 的字串)
由圖中可以發現前面幾筆的測試資料都是與後面的數據相比都是有極大的差異，因此在 [Dude](https://eprint.iacr.org/2016/1123.pdf) 中會去捨棄掉前十筆的測試資料在去做相關的測試，但可以發現到 `fix` 的每筆資料的執行時間都是顯著低於我 `random` 的執行時間，因此我在想是不是 `0` 會在電腦中做特殊的處理導致執行時間較短，所以我嘗試將測試資料更改為不同的 `fix` 字串，以下為得出的執行結果。
此測試為將 `fix` 字串改動為 ==0xAA== ，可以看到資料的分佈大致相同且通過了 `trace 17` 的測試。
此測試為將 `fix` 字串改動為 ==0xCC== ，可以看到資料的分佈也大致相同且通過了 `trace 17` 的測試。
此測試為將 `fix` 字串改動為 ==0xFF== 來去測試邊界，可以看到這個例子會讓 fix 的執行時間平均起來大於 `random` 但是也還是能通過 `trace 17` 的測試。
:::info
至於為什麼 0 會有這種特別的現象是我不懂的地方。
:::
### Student's t-distribution
當母群體為常態分佈且無法得知變異數和抽樣的樣本數不夠大的這種情況下我們不能去計算[ z 分數](https://zh.wikipedia.org/zh-tw/%E6%A8%99%E6%BA%96%E5%88%86%E6%95%B8)這時就要採用樣本的標準差來估計母群體的標準差，像這樣子的分佈我們稱為 ==Student's t-distribution==。
Student's t-distribution 分佈的平均數為 0 且是對稱的分佈為下列這張圖它跟常態分佈不同的地方在於 t 分佈是依據自由度(樣本數 - 1)來改變他的分佈形狀，隨著樣本數越大會越接近常態分佈，當樣本數超過 30 以上的時候就能使用常態分佈的 z 值去取代 t 值( 自由度是統計學中可自由變動的數據數量，代表在計算某個統計量時，有多少個數據點是可以自由變化的。)簡單來說自由度 = 可自由變動的數據數量，受限制的數據點越多，自由度就越少。
==紅色的線為他的分佈==
(自由度為 1 )
(自由度為 30 )
可以看到當自由度逐漸增加 t 分佈就逐漸和常態分佈越來越相似，還有在探討兩個樣本平均值之差異是否顯著的時候，我們必須先做變異數檢定，假設母群體變異數相同時我們可以套用下列式子
$S_p^2 = \frac{(n_1 - 1) S_1^2 + (n_2 - 1) S_2^2}{n_1 + n_2 - 2}$
也就是合併兩個樣本的變異數 $S1^2$ 和 $S2^2$ 來去估計共同的變異數也就是 $S_p^2$ 這時的 t 值就為下列的公式
$t = \frac{(\bar{x}_1 - \bar{x}_2) - (\mu_1 - \mu_2)}
{\sqrt{\frac{S_p^2}{n_1} + \frac{S_p^2}{n_2}}}$
另一種情況為母群體變異數==不相同==時
$t = \frac{(\bar{x}_1 - \bar{x}_2) - (\mu_1 - \mu_2)}
{\sqrt{\frac{S_1^2}{n_1} + \frac{S_2^2}{n_2}}}$
知道了 t 值那我們還需要自由度才能夠去查表那我們在母群體變異數==不相同==時的自由度計算方式就為這個公式
$v = \frac{\left( \frac{S_1^2}{n_1} + \frac{S_2^2}{n_2} \right)^2}
{\frac{\left( \frac{S_1^2}{n_1} \right)^2}{n_1 - 1} +
\frac{\left( \frac{S_2^2}{n_2} \right)^2}{n_2 - 1}}$
## 實作 shuffle 命令
### 實作 Fisher-Yates shuffle Algorithm
在實做這項之前我先去閱讀了[ Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)我採用的是他現今的版本是專為電腦使用而設計，由 Richard Durstenfeld 於 1964 年提出。
```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
利用 [lab0-d](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 提供之測試腳本進行實驗，結果如下。
這是跑了 ==1000 次==的結果，經過幾次測試下來，我發現到說每一次的數據結果的變異性大，尚無法得出具統計意義的結論，因此我進一步擴大測試範圍以獲取更穩定的結果。
```
Expectation: 41666
Observation: {'1234': 41481, '1243': 41517, '1324': 41850, '1342': 41807, '1423': 41956, '1432': 41674, '2134': 41686, '2143': 41600, '2314': 41309, '2341': 41941, '2413': 41747, '2431': 41760, '3124': 41436, '3142': 41838, '3214': 41974, '3241': 41599, '3412': 41524, '3421': 41595, '4123': 41215, '4132': 41794, '4213': 41593, '4231': 41627, '4312': 41824, '4321': 41653}
chi square sum: 21.033072529160467
```
以下是跑了==1000000次==的結果
## 比較亂數產生器 (Xorshift vs. 內建) 的品質
首先要必須先了解到當執行 ==ih RAND 100== 會發生什麼事情，因此我閱讀了原代碼 `qtest.c` 和 `console.c` 發現到 `console.c` 實現了一個簡單的指令列介面，當我輸入 ih RAND 100 時 `interpret_cmd` 這個函式會去解析我的這段指令並呼叫 `parse_args` ，這個函式把它分割為 `ih` 和 `RAND` 還有 `100` 再用 `argv` 這個陣列去保存，隨後交由 `interpret_cmda` 這個函式去執行我的命令，其中 `interpret_cmda` 這個函式裡使用了叫做 `cmd_element_t` 的結構體儲存 `CLI` 的指令資訊，並且使用鏈結串列來管理所有可用的指令。
在閱讀完後我發現到了 `q_show` 中主要確認開啟 `entropy` 分析的在這行：
```c
if (show_entropy) {
report_noreturn(
vlevel, "(%3.2f%%)",
shannon_entropy((const uint8_t *) e->value));
}
```
當你在 `cmd` 中輸入 `option entropy 1` 時它就會將 `show_entropy` 這個值設為 `1` 也就是 true 。
你原本輸入 ih RAND 10 是不會去做分析的也就是下面這段。
```
l = [ppdaxq zrsqbseq jqrwe rmyxq tolkbcz fksdh mcbdmci arotglxvf wlwtuxdm zlkfbs]
```
隨後我們執行 `option entropy 1` 可以分別看到個別的字串的 p 值。
```
Current queue ID: 0
l = [ppdaxq(26.56%) zrsqbseq(29.69%) jqrwe(26.56%) rmyxq(26.56%) tolkbcz(32.81%) fksdh(26.56%) mcbdmci(26.56%) arotglxvf(37.50%) wlwtuxdm(32.81%) zlkfbs(29.69%)]
```
程式要如何的得知要插入的是亂數字串呢？就必須依靠 ih 後面的 RAND，這個參數會在 `queue_insert()` 中的這段去做檢查，當檢查到有輸入 RAND 時會將 `need_rand` 設為 true 在把輸入的字串替換成 randstr_buf 。
```c
if (!strcmp(inserts, "RAND")) {
need_rand = true;
inserts = randstr_buf;
}
```
當 `need_rand` 為 true 時會執行叫做 `fill_rand_string` 的函式，這個函式會將 `randstr_buf` 填入亂數字串當作我要插入的資料。
```c
if (need_rand)
fill_rand_string(randstr_buf,sizeof(randstr_buf));
```
了解完大概的流程之後我們開始將 `Xorshift` 這一組新的命令去引入 lab0-c ，首先先設計指令檢查到 `Xorshift` 就執行 `Xorshift` 這個命令。
```c
if (!strcmp(inserts, "Xorshift")) {
need_Xorshift = true;
inserts = Xorshiftstr_buf;
}
```
在來就是就設計**生出 n 個隨機位元組的函式**，我把它命名叫做 `randombytes_xor` 也就是以下這個式子
```c
uint64_t xorshift64(void)
{
xorshift64_state ^= xorshift64_state << 13;
xorshift64_state ^= xorshift64_state >> 7;
xorshift64_state ^= xorshift64_state << 17;
return xorshift64_state;
}
void randombytes_xor(uint8_t *buf, size_t n)
{
for (size_t i = 0; i < n; i++)
buf[i] = (uint8_t)(xorshift64() & 0xFF);
}
```
後來我依據 `fill_rand_string` 這個函式去實做了一個 `fill_Xorshift_string` 的函式主要就是去呼叫 `randombytes_xor` 這個函式來去填充 `Xorshiftstr_buf` 這個 `buffer` 。
**以下為兩種的方式測試 1000 次的測試結果**
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試改進
### 引入 list_sort.c 到 lab0-c
* 用 `bottom up` 實作 `merge sort` 對 `cache` 較友善，因為過程中就是一直合併， `cache` 被參照到的機會更大。
* 而 `top down` 是會先做 `partition` 再來 `merge` ，但 `partition` 本身對 `cache` 不友善，在 `cache` 移進移出（內容不斷更新，導致 `cache thrashing` ）。
### 何時合併
每當 `count + 1` ，可能會有==兩種情況==：
**1. 當 count + 1 後為 $2^k$ 就不合併（只有 leading 1 是 1，其餘都為 0）**
**2. 當 count + 1 後不為 $2^k$，就合併**
在 `lib/list_sort.c` 的基礎上，我進行了一部分的修改後引入到 lab0-c 之程式碼當中。在開發過程中使用 `make test` 報出了以下的錯誤，第一步我開始思考什麼叫做這裡所提到的 `implicit declaration of function` 。
```
queue.c: In function ‘list_sort’:
queue.c:478:17: error: implicit declaration of function ‘list_merge’; did you mean ‘list_move’? [-Werror=implicit-function-declaration]
```
於是我上網看了[你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function)才發現到甚麼是隱式函式也就是在 早期的 C 編譯器（ANSI C 之前），當你呼叫一個未事先宣告的函式，編譯器不會報錯，而是自動假設它回傳 int，並允許程式繼續編譯，這種行為稱為 `Implicit Function Declaration` 。
但在現在 Implicit Function Declaration 已經被移除掉。
**c99**(page10)
>— remove implicit function declaration
### 測試 Top down 和 Buttom up merge sort 的效能落差
首先我實做了一個測試程式能夠去相比 `Top down Merge sort` 和 `Buttom up Merge sort` 的執行速率，其中關於隨機字串我做了一個函式來去生成隨機字串，來去當作我 `q_insert_head()` 中的 `char *s` 的參數此字串的長度我將它設定為 `10` 個 `char` 。
```c
const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
for (int i = 0; i < len; i++) {
int key = rand() % (sizeof(charset) - 1);
str[i] = charset[key];
}
str[len] = '\0';
return str;
```
以下測試的 `clock cycle` 都還有額外加上 `generate_random_string()` 和 `q_insert_head()` 還有 `q_new()` 執行所需的 `clock cycles` ，因此跟單獨執行 `Merge sort` 有實際的落差。
這個是 `Top down` 的 `Merge sort` 所執行出來的結果( ==test 10000==)
```
Performance counter stats for './linklisttest' (100 runs):
3.85 msec task-clock # 0.944 CPUs utilized ( +- 0.17% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
212 page-faults # 55.064 K/sec ( +- 0.03% )
17,629,607 cycles # 4.579 GHz ( +- 0.10% )
26,215,945 instructions # 1.49 insn per cycle ( +- 0.01% )
4,934,918 branches # 1.282 G/sec ( +- 0.00% )
109,388 branch-misses # 2.22% of all branches ( +- 0.21% )
0.00408039 +- 0.00000817 seconds time elapsed ( +- 0.20% )
```
可以看到第二個 `clock cycle` (16,955,761) 相比第一個 (17,629,607)，減少了 673,846 個 `cycle` ，相當於 提升了約 ==3.82%== 的效率。
這個是 `Buttom up` 的 `Merge sort` 所執行出來的結果( ==test 10000==)
```
Performance counter stats for './linklisttest' (100 runs):
3.70 msec task-clock # 0.940 CPUs utilized ( +- 0.13% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
212 page-faults # 57.283 K/sec ( +- 0.03% )
16,955,761 cycles # 4.582 GHz ( +- 0.11% )
26,228,216 instructions # 1.55 insn per cycle ( +- 0.01% )
4,565,037 branches # 1.233 G/sec ( +- 0.00% )
109,184 branch-misses # 2.39% of all branches ( +- 0.10% )
0.00393548 +- 0.00000593 seconds time elapsed ( +- 0.15% )
```
這個是 `Top down` 的 `Merge sort` 所執行出來的結果( ==test 50000==)
```
Performance counter stats for './linklisttest' (100 runs):
20.97 msec task-clock # 0.986 CPUs utilized ( +- 0.23% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
837 page-faults # 39.915 K/sec ( +- 0.01% )
96,190,817 cycles # 4.587 GHz ( +- 0.23% )
134,174,518 instructions # 1.39 insn per cycle ( +- 0.01% )
25,198,595 branches # 1.202 G/sec ( +- 0.01% )
598,313 branch-misses # 2.37% of all branches ( +- 0.10% )
0.0212657 +- 0.0000525 seconds time elapsed ( +- 0.25% )
```
這個是 `Buttom up` 的 `Merge sort` 所執行出來的結果( ==test 50000==)
```
Performance counter stats for './linklisttest' (100 runs):
19.77 msec task-clock # 0.986 CPUs utilized ( +- 0.19% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
837 page-faults # 42.332 K/sec ( +- 0.01% )
90,649,422 cycles # 4.585 GHz ( +- 0.18% )
134,543,086 instructions # 1.48 insn per cycle ( +- 0.00% )
23,118,201 branches # 1.169 G/sec ( +- 0.00% )
596,671 branch-misses # 2.58% of all branches ( +- 0.04% )
0.0200463 +- 0.0000388 seconds time elapsed ( +- 0.19% )
```
第二個 `clock cycle` (90,649,422) 相比第一個 (96,190,817)，減少了 5,541,395 個 `cycle` ，相當於提升了約 ==5.76%== 的效率。
以下是測試`list node`從 5000 到 50000 的實驗結果("Each step size is 5000")
**class 0 為 ==Top down== 的 Merge sort**
**class 1 為 ==Buttom up== 的 Merge sort**
### 引入 timsort 並測試效能
在這次測試中，我選擇使用一個由一半已排序與一半亂序元素組成的串列進行排序操作。結果顯示，在處理 50,000 筆資料時，速度提升達到了 ==16%== :
然而，必須注意的是，在 worst case（也就是所有資料完全亂序的情況下），timsort 的效能會比 bottom-up merge sort 和 top-down merge sort 略顯不足。這主要是因為 timsort 在處理局部已排序的情形時能夠大幅提升效率，但當所有資料都處於亂序狀態時，這一優勢就無法發揮，反而會因額外的遞迴調用和臨時空間開銷，使得其效能不如傳統的合併排序變種。
## [Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b)
### 使用 valgrind 排除 qtest 記憶體問題
根據以 [Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b) 執行命令 make valgrind ，檢查是否存在記憶體錯誤。
檢查出來的結果如下，可以看到說目前的實做並沒有[ Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b)以下所提到的這幾個 ==memory lost==。
* `definitely lost` : 真的 memory leak
* `indirectly lost` : 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
* `possibly lost` : allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
* `still reachable` : 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。
```
+++ 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
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.4wVZMs --valgrind -t < tid >
```
### Massif 視覺化 "simulation" 過程中的記憶體使用量
**實驗：嘗試減少 heap memory 用量**
首先，我將 measure 函式中原本需要輸入兩個陣列的設計，改為只需使用一個陣列，因為在測量操作的執行時間時，並不需要分別存儲執行前後的時間點。只需在陣列中記錄操作開始的 CPU cycles，然後在操作結束後，再以當前的 CPU cycles 減去先前儲存的值，即可計算出執行時間。
```diff
bool measure(
+ int64_t *exec_time,
- int64_t *before_ticks,
- int64_t *after_ticks,
uint8_t *input_data,
int mode);
```
並去改動 contant.c 中的程式碼：
```diff
int before_size = q_size(l);
- before_ticks[i] = cpucycles();
+ exec_time[i] = cpucycles();
dut_insert_head(s, 1);
- after_ticks[i] = cpucycles();
+ exec_time[i] = cpucycles() - exec_time[i];
int after_size = q_size(l);
```
透過這兩項改動，我們成功將兩個陣列的記憶體使用量減少為一個，從而提升了程式的記憶體效率。同時，這種方式不影響執行時間的準確性，因為我們仍然能夠精確地計算出操作的執行時間，僅使用一個陣列來存儲起始時間，並在操作完成後直接計算時間差。這樣不僅減少了不必要的記憶體分配，也讓程式的結構變的加簡潔。
```diff!
- int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
- int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
- free(before_ticks);
- free(after_ticks);
```
以下為實驗結果在最高峰的記憶體使用量減少約 ==1 %==：
### signal處理及應用
在說明 signal 處理及應用之前我先閱讀了 [signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html)，並把觀察紀錄下來 [signal(7)](https://hackmd.io/@Guanchun0803/signal7)
在 lab0-c 中可以發現到在 qtest.c 中 q_init 這個函式會註冊 SIGSEGV 和 SIGALRM 對應的 signal handler 也就是下列這段：
```c
static void q_init()
{
fail_count = 0;
INIT_LIST_HEAD(&chain.head);
signal(SIGSEGV, sigsegv_handler);
signal(SIGALRM, sigalrm_handler);
}
```
**sigsegv_handler**
sigsegv_handler 是用來處理當程式觸發 Segmentation Fault（SIGSEGV） 時的情況。
這通常是因為程式嘗試存取非法記憶體位址，例如解參 NULL 指標或超出邊界。
在這個 handler 中：
* 使用 write() 輸出錯誤訊息，避免使用像 printf() 這類非重入（non-reentrant）函式。
* 接著呼叫 abort()，強制送出 SIGABRT 訊號，這會讓程式異常終止，並觸發 core dump，方便之後用除錯工具（如 gdb）分析錯誤發生時的狀態。
```c
/* Signal handlers */
static void sigsegv_handler(int sig)
{
/* Avoid possible non-reentrant signal function be used in signal handler */
assert(write(1,
"Segmentation fault occurred. You dereferenced a NULL or "
"invalid pointer",
73) == 73);
/* Raising a SIGABRT signal to produce a core dump for debugging. */
abort();
}
```
**sigalrm_handler**
sigalrm_handler 的作用為，當使用者程式執行時間超過限制時，透過 SIGALRM 觸發這個 handler，報告「Time Limit Exceeded」並結束執行。
```c
static void sigalrm_handler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
```
**exception_setup()**
在每個測試開始前呼叫，作用如下：
* 透過 sigsetjmp() 設定一個跳躍點（儲存執行狀態），可用於錯誤回復
* 若 limit_time == true，則啟用 alarm() 設定執行時間限制
* 若之後在程式中呼叫 trigger_exception()，會透過 siglongjmp() 跳回此處並 return false
* 否則第一次呼叫會正常回傳 true
**trigger_exception()**
當發生錯誤（如超時、記憶體存取錯誤等）時呼叫此函式：
* 記錄錯誤訊息與狀態
* 若有有效的 jmp_ready，會 siglongjmp() 回到最近的 exception_setup()
* 否則直接呼叫 exit(1) 結束程式
**exception_cancel()**
用於成功完成受保護區段後的清理動作：
* 取消時間限制（alarm(0)）
* 重設錯誤相關狀態
* 關閉 jmp_ready
## 解釋 select 系統
要解釋 select 系統就必須先了解 select 是什麼，於是我先閱讀了 [select](https://man7.org/linux/man-pages/man2/select.2.html)，了解到 select 是一個 同步 I/O Multiplexing 的方法，允許程式同時監視多個檔案描述符，以判斷哪些描述符已準備好進行 I/O 操作。
select() 的主要參數是 三個 fd_set（檔案描述符集合）：
* readfds（讀取集合）：監視哪些 fd 可讀。
>The file descriptors in this set are watched to see if they are ready for reading.
* writefds（寫入集合）：監視哪些 fd 可寫。
>The file descriptors in this set are watched to see if they are ready for writing.
* exceptfds（異常集合）：監視哪些 fd 發生異常。
>The file descriptors in this set are watched for "exceptional conditions".
```c
int select(int nfds, fd_set *_Nullable restrict readfds,
fd_set *_Nullable restrict writefds,
fd_set *_Nullable restrict exceptfds,
struct timeval *_Nullable restrict timeout);
```
**fd_set**
這是一種結構體類型，可用於表示一組檔案描述符。在 POSIX 標準中，一個 fd_set 結構內最多能容納 FD_SETSIZE 個描述符（1024 個）。
> WARNING: select() can monitor only file descriptors numbers that are less than FD_SETSIZE (1024)
File descriptors sets 可以利用以下巨集操作
* FD_ZERO(set) 清空 fd_set（移除所有描述符）。
>This macro clears (removes all file descriptors from) set. It should be employed as the first step in initializing a file descriptor set.
* FD_SET(fd, set) 將 fd 加入 set。
>This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.
* FD_CLR(fd, set) 從 set 移除 fd。
>This macro removes the file descriptor fd from set. Removing a file descriptor that is not present in the set is a no-op, and does not produce an error.
* FD_ISSET(fd, set) 檢查 fd 是否在 set 中存在於集合中，0 表示不在集合內。
>After calling select(), the FD_ISSET() macro can be used to test if a file descriptor is still present in a set. FD_ISSET() returns nonzero if the file descriptor fd is present in set, and zero if it is not.
最後要提到 select 的==限制==
**select() 只能監控數值小於 FD_SETSIZE（1024）的檔案描述符。**
因此如果是 web 伺服器、大規模網路應用來說的話是無法勝任的
所以有提到這段話。
> All modern applications should instead use poll(2) or epoll(7), which do not suffer this limitation.
而 select 在 lab0-c 中的使用方式為去監聽 0 和 3。其中 0 代表標準輸入也就是終端機，而 3 是伺服器所監聽的 socket 描述符這個 用來監聽來自 HTTP 用戶端的請求。而當 server_fd 可讀時代表有新的用戶端嘗試連線，這時會執行 accept() 接受這個連線，並返回一個新的 並返回一個新的文字描述符為 4 給予 web_connfd 這個變數，在將網頁資訊寫入該文字描述符最後回傳網頁值給使用者並去釋放該文字描述符。
```
pselect6(4, [0 3], NULL, NULL, NULL, NULL) = 1 (in [3])
accept(3, {sa_family=AF_INET, sin_port=htons(41216), sin_addr=inet_addr("127.0.0.1")}, [16]) = 4
read(4, "GET /new HTTP/1.1\r\nHost: localho"..., 1024) = 81
write(4, "HTTP/1.1 200 OK\r\n%s%s%s%s%s%sCon"..., 209) = 209
close(4)
```
當我閱讀完上述的文件後發現到題目的敘述中還有提到了 console.c 的實作運用到了 CS:APP RIO 套件，因此我閱讀了[ RIO 套件](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf)並把發現記錄下來[ System-Level I/O ](https://hackmd.io/@Guanchun0803/SystemIO#104-Robust-Reading-and-Writing-with-the-RIO-Package)。
在仔細觀察完程式碼後發現在 console.c 中有模仿了 select() 行為函式的實做。
它實際上是根據內部緩衝區（buf_stack）和網頁伺服器的狀態來決定讀取哪個輸入來源，並將讀取到的命令交給命令解析器來執行。
```c
static int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
```
於是我開始找尋 cmd_select 這個函式會在 console.c 中哪一段被呼叫，最後發現到 ==run_console== 這個函式，於是我觀察這個函式的程式碼後發現到 run_console 這個函式在於這個 console.c 這個檔案中是作 console.c 的主要執行函式，他的輸入為 ==char *infile_name== ，而 run_console 中的 push_file 會去看 infile_name 的值否為 NULL ，如果為 NULL 則將會把輸入設為 STDIN_FILENO (也就是標準輸入)，如果不為 NULL 則會去查找是否有這個檔案假如沒有則會執行以下的程式：
>report(1, "ERROR: Could not open source file '%s'", infile_name);
假如執行 push_file 成功的話則會去執行該檔案的命令，當檔案中的命令全部執行完後就退出程式，如果為沒有輸入檔案時將會執行一個迴圈不斷的去接收看看有哪個文件表示符就緒。
console.c 會將檔案塞入以下結構業就是類似[ RIO 套件](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf)中所提到的：
```c
typedef struct __rio {
int fd; /* File descriptor */
int count; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
struct __rio *prev; /* Next element in stack */
} rio_t;
```
此處相比[ RIO 套件](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf)還多增加了 prev 這個參數使得此結構能做成單向鏈結串列。
上述的結構這就是 CS:APP RIO 中所提到的第二種函式**有緩衝（Buffered）輸入函式**，可以看到在 console.c 中 readline() 這個函式就實現了類似 readlineb() 的結構，就是從當前的緩衝區（buf_stack）中讀取一行文字，直到讀到換行符或達到緩衝區限制，其中該函式最關鍵的是在下列這行。
```c
buf_stack->count = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE);
```
簡單來說就是從該檔案中讀取 RIO_BUFSIZE 位元的資料並存入 buf_stack 的暫存區( ==buf_stack 是一個指向 rio_t 結構的指標，而且 buf_stack 總是指向最新產生的 rio_t 結構==)，這樣的好處就是**不用反覆執行 read() 與核心做溝通**，在原本可能讀一個檔案要不斷的使用 read 去讀取每一行指令，而在此結構下在buf_stack尚未用完時只須從應用層級的緩衝區來去讀取就好。
舉個例子:就像你今天想喝水每次都要到飲水機去喝，這樣不是很麻煩，所以我們就有了水壺能去裝滿水，只要還沒喝完之前都不用去飲水機裝水要喝水在原地就好。
web.c 中則是直接引入[ RIO 套件](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf)中的 rio_read 、 rio_readlineb 、rio_readinitb 以及 writen 這些函式來使得 web.c 能將 web_connfd 中 HTTP Request 內容是透過讀取並寫入 rio 。
Sign in with Wallet
Connect another wallet