# 2025q1 Homework1 (lab0)
contributed by <[``Ian-Yen``](https://github.com/Ian-Yen/lab0-c)>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## Reviewed by BennyWang1007
1. 倉庫並不包含指定commit `4a2ff9f`，並且應使用 rebase 而不是直接 merge，見 commit `60486bc`。
2. 此份筆記不是讓你展示所有程式碼的地方，只展示部分即可。
3. `q_delete_dup` 中，多次使用到 `pos->list`，既然如此可以改成使用 macro `list_for_each_safe` 增加效率並使程式碼更簡潔。
4. `q_shuffle` 將 `if (!num)` 判斷式往前移，能夠減少不必要的運算。
5. 請問 listsort 的 CDF 是指完成排序的比例嗎？為什麼橫軸會是 0.6M cycle 開始？差距的效率又是多少？
6. 缺乏的部分如 tiny web server 等，有空可以慢慢補上。
## 開發環境
```
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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.
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
供應商識別號： AuthenticAMD
Model name: AMD Ryzen 7 5800H with Radeon Graphics
CPU 家族： 25
型號： 80
每核心執行緒數： 2
每通訊端核心數： 8
Socket(s): 1
製程： 0
Frequency boost: enabled
CPU(s) scaling MHz: 37%
CPU max MHz: 4463.0000
CPU min MHz: 400.0000
```
---
## queue.c實作
### q_new
>[Commit 37081b1](https://github.com/sysprog21/lab0-c/commit/37081b1e6ac60a892e292afa194d8265aa1f13d8)
```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` 分配記憶體空間，當分配失敗的時候回傳 `NULL` ，分配成功的話就用 `INIT_LIST_HEAD` 做初始化，最後回傳。
### q_free
>[Commit fce7fec](https://github.com/sysprog21/lab0-c/commit/fce7fecbe164f5c2bd8e217dd491f664ae779e92)
先確認 `head` 不是空指標，接著用 `list_for_each_entry_safe` 走訪所有的節點，並在每個節點把那個節點的 `value` 與他本身釋放掉，最後釋放`list_head`。
>>[Commit c6b00cc](https://github.com/sysprog21/lab0-c/commit/c6b00ccd2fa1a8b9b5469f4c4e004b063578a07c)
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *pos = NULL, *n;
list_for_each_entry_safe (pos, n, head, list)
q_release_element(pos);
free(head);
}
```
把釋放的動作交給 `q_release_element` 讓程式碼看起來更簡潔。
### q_insert_head 與 q_insert_tail
>[Commit 4b91c52](https://github.com/sysprog21/lab0-c/commit/4b91c528e0c62013f56474dc8f81c226fe84fc80)
在觀察完題目後發現，這兩個函式做的事情極為相似，所以我就直接做一個 `q_insert` ，可以把一個節點放在 `head->next` 。
首先確認 `head` 與 `s` 不是空指標，接著使用 `malloc` 分配一塊記憶體給這個 `element_t` 確認分配成功之後再次使用 `malloc` 分配記憶體給他的 `value` 這邊要特別注意的地方有分配的記憶體大小要多一個 `char` 的空間，因為字串最後要使用 `\0` 作為他的結尾，最後用 `list_add` 把它放進 `queue` 裡面。
>>[Commit 9996f75](https://github.com/sysprog21/lab0-c/commit/9996f756703fad8b033956aa3a1c8b324f0be15e)
```c
bool q_insert(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(&ele->list, head);
return true;
}
```
在上一個Commit中，雖然有發現要用`\0`最為結尾所以多開一個`char`的空間，但沒有把`\0`賦值給他，這次修改使用了`strdup`，除了可以讓程式碼變簡潔以外，也解決了這個問題。
在 `q_insert_head` 使用 `q_insert(head, s)` ，在 `q_insert_tail` 裡面先判斷 `head` 是否為空指標，接著使用 `q_insert(head->prev, s)`。
### q_remove_head 與 q_remove_tail
>[Commit c8fc20c](https://github.com/sysprog21/lab0-c/commit/c8fc20c7141486a931d7fa990476bc4af1b71a90)
這兩個函式做的事情與 `insert` 一樣極為相似，所以我就直接做一個 `q_remove` ，可以 `remove` 當個節點。
首先確認`meow`，接著使用`list_entry`來找到他的`entry`，然後使用`list_del`來`remove`找到的節點，最後使用`memcpy`把`bufsize-1`長度的`value`複製到給定的位置，並將`value`的第`bufsize`個位置改成`\0`。
>>[Commit c53c698](https://github.com/sysprog21/lab0-c/commit/c53c69898edea7b3b82404f53fe4bda8910c3feb)
```c
element_t *q_remove(struct list_head *head, char *sp, size_t bufsize)
{
element_t *ele = list_entry(head, element_t, list);
list_del(&ele->list);
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
這邊把判斷`head` 是否為空指標或是一個空的`queue`加上去，並檢查`sp`是不是`NULL`，
在 `q_remove_head` 與 `q_remove_tail` 裡面先判斷 `head` 是否為空指標或是一個空的`queue`，接著 `q_remove_head`使用 `q_remove(head->next, sp, bufsize)`，`q_remove_tail`使用 `q_remove(head->prev, sp, bufsize)`。
### q_size
>[Commit a480992](https://github.com/sysprog21/lab0-c/commit/a480992fc78e889c48b25504214167e673efdd96)
```c
int q_size(struct list_head *head)
{
if (!head)
return -1;
struct list_head *pos;
size_t count = 0;
list_for_each (pos, head) {
count++;
}
return count;
}
```
先檢查 `head` 是不是空指標，不是的話用 `list_for_each` 走訪所有節點，宣告一個變數 `count` 走訪一個變數就加一，最後回傳 `count` 。
### q_delete_mid
>[Commit 36ef953](https://github.com/sysprog21/lab0-c/commit/36ef953ec16a6e1eded134ac71f7a90a60d4b196)
使用 `list_for_each_safe` 走訪所有節點，宣告一個 `list_head` 的 `pointer` `tmp` 來紀錄 `mid` 的位置。
剛開始 `tmp` 設為 `head` ，進迴圈時 `tmp = tmp->next` ，之後每走訪兩個節點， `tmp` 就往 `next` 前進一格，最後用 `list_del` 把它移出 `queue` ，且把它的記憶體釋放掉。
>>[Commit 9330115](https://github.com/sysprog21/lab0-c/commit/93301155d8b3b5ba1ec6e28828dfef94fa891c51)
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *h = head->next, *t = head->prev;
while (h != t && t->next != h) {
h = h->next;
t = t->prev;
}
q_del_element(t);
return true;
}
```
上面那個方法雖然可以得出正確答案，但它有點太慢了，總共要走訪 `1.5` 個 `queue` 的節點，所以我用了兩個指標分別從頭與尾往後與往前搜尋直到相遇。這樣最多只要走訪一個 `queue + 1` 個節點比上面的好很多，甚至還更加精簡。
### q_delete_dup
>[Commit 071dfd1](https://github.com/sysprog21/lab0-c/commit/071dfd19af9c8dbe9e132f6b36add3ce2afb03b9)
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || head->next == head)
return false;
element_t *pos = NULL, *n, *prev;
bool del = false;
list_for_each_entry_safe (pos, n, head, list) {
if (pos->list.prev == head)
continue;
prev = list_entry(pos->list.prev, element_t, list);
if (strcmp(pos->value, prev->value) == 0) {
q_del_element(&(prev->list));
del = true;
} else if (del) {
q_del_element(&(prev->list));
del = false;
}
}
if (del)
q_del_element(head->prev);
return true;
}
```
先宣告一個布林值代表有沒有連續，用 `list_for_each_entry_safe` 按照順序走訪，如果現在的跟上一個的 `value` 一樣那個布林值就變成 `true` 然後使用 `q_del_element` 刪掉前一個，如果不一樣但是那個布林值是 `true` ，也刪掉前一個，並把那個布林值設為 `false` ，這樣能確保所有的連續都可以被刪掉。
### q_swap
>[Commit d655fdf](https://github.com/sysprog21/lab0-c/commit/d655fdf53b9af3d0d07d2f80630f9793fa1ca8be)
這邊我先宣告一個布林值`swap = false`代表要不要跟前一個交換，用`list_for_each_safe`走訪所有節點，到每個節點的時候`swap = !swap`然後看`swap`是否為`true`來決定是否交換。交換的方式是使用`linux kernel`的`list_swap`，但`list.h`裡面沒有這個所以我複製了一份需要的原始碼過去。
>>[Commit 3692130](https://github.com/sysprog21/lab0-c/commit/3692130aa18745e91c711d7afa4c4a81e0730c87)
```c
void q_swap(struct list_head *head)
{
int k = 2;
q_reverseK(head, k);
}
```
這邊是我在實作完 `q_reverseK` 的時候發現他跟 `q_swap` 很像，把 `K` 設為 2 時做出來的行為會是一樣的。所以我就把它簡化成 `q_reverseK(head, 2)` 了。
### q_reverse
>[Commit 8327b6d](https://github.com/sysprog21/lab0-c/commit/8327b6d56c83512d2e8b0e5a959d6da1e454ff2b)
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *pos = NULL, *n;
list_for_each_safe (pos, n, head) {
pos->next = pos->prev;
pos->prev = n;
}
n = head->next;
head->next = head->prev;
head->prev = n;
}
```
首先檢查 `head` 是否為空，否則用 `list_for_each_safe` 來走訪所有節點並把它們反轉，使用 `safe` 的性質就不用把 `next` 存到一個 `tmp` 裡面來完成交換，讓程式碼便簡潔，最後把 `head` 反轉。
### q_reverseK
>[Commit 4c0ba40](https://github.com/sysprog21/lab0-c/commit/4c0ba404368d8fbcc596310d3ef48b08ea849da0)
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
struct list_head *l = head, *r = head->next;
for (;; l = r->prev) {
for (int i = 0; i < k; i++, r = r->next)
if (r == head)
return;
LIST_HEAD(tmp);
list_cut_position(&tmp, l, r->prev);
q_reverse(&tmp);
list_splice(&tmp, l);
}
}
```
首先檢查 `head` 是否為空或是 `singular` ，接著使用一個 `for loop` 來走訪這個 `queue` ，比較特別是一次走訪 `k` 個，在裡面野放一個`for loop`走訪 `k` 個節點，確認後面有 `k` 個節點後，把它用 `list_cut_position` 放在一個暫時的 `queue` 裡面，把那個 `queue` 拿去 `q_reverse` 再用 `list_splice` 把它放回去。
### q_sort
先寫一個可以把兩個 `descend/ascend` 排序好的 `queue` 合併起來的涵式
#### 先做mergeTwoLists
>[Commit f96c2e5](https://github.com/sysprog21/lab0-c/commit/f96c2e5aac4800f102dc9ddce8322d49a472e108)
```c
void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend)
{
element_t *e1 = list_entry(L1->next, element_t, list),
*e2 = list_entry(L2->next, element_t, list), *tmp;
while (&e1->list != L1 && &e2->list != L2) {
if (((strcmp(e1->value, e2->value)) > 0) ^ descend) {
tmp = list_entry(e2->list.next, element_t, list);
list_move(&e2->list, e1->list.prev);
e2 = tmp;
} else
e1 = list_entry(e1->list.next, element_t, list);
}
list_splice_tail(L2, L1);
return;
}
```
先宣告兩個 `entry` 為 `e1, e2` ，在 `e2` 不為空的 `queue` 且 `e1` 不是 `head` 的情況下都要繼續跑的 `while loop` (走訪的數量最多是`L1`與 `L2` 的 `q_size` 相加)，比較兩個 `value` 大小，用 `xor` 的特性來看他要動哪一個，最後會把結果全部合併到 `L1` ，所以如果是動 `L1` 就單純往後一個，如果是動 `L2` 就把他用 `list_move` 移動到 `e1` 的前一個。
最後，當其中一邊走訪到盡頭後把 `L2` 使用 `list_splice_tail` 移動到L1的最後面完成合併。
```c
while (&e1->list != L1 && &e2->list != L2) {
if (((strcmp(e1->value, e2->value)) > 0) ^ descend) {
tmp = list_entry(e2->list.next, element_t, list);
list_move(&e2->list, e1->list.prev);
e2 = tmp;
} else
e1 = list_entry(e1->list.next, element_t, list);
}
```
---
#### 實作q_sort
>[Commit c762d5a](https://github.com/sysprog21/lab0-c/commit/c762d5a96dec991f2ebd630f40226a2f19f20eec)
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *mid, *h = head->next, *t = head->prev;
while (h != t && t->next != h) {
h = h->next;
t = t->prev;
}
mid = t;
LIST_HEAD(tmp);
list_cut_position(&tmp, mid, head->prev);
q_sort(head, descend);
q_sort(&tmp, descend);
mergeTwoLists(head, &tmp, descend);
return;
}
```
用 `while loop` 分別從頭尾往中間做逼近，直到相遇找到中間點，然後遞迴一半的 `queue` 在排序後使用上面的 `mergeTwoLists` 把結果合併。
### q_ascend
>[Commit ce5b2dd](https://github.com/sysprog21/lab0-c/commit/ce5b2ddcd64483013dadc80c15176c38af69c13c)
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
const char *smallest = NULL;
int cnt = 0;
element_t *ele = NULL;
for (struct list_head *pos = (head)->prev, *n = head->prev->prev;
pos->prev != head; pos = n, n = pos->prev) {
ele = list_entry(pos, element_t, list);
if (!smallest || strcmp(smallest, ele->value) >= 0) {
cnt++;
smallest = ele->value;
continue;
}
list_del(&ele->list);
}
return cnt;
}
```
因為 `list.h` 沒有 `list_for_each_reverse_safe` 所以我自己寫了一個，從後面開始走訪然後紀錄目前看到最小的`value`，如果看到了一個比紀錄的 `value` 還要大的值，就用 `list_del` 把它刪掉。
### q_descend
>[Commit b48092f](https://github.com/sysprog21/lab0-c/commit/b48092ffea0a5ae2624d9798efd6abd4b602da4a)
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
const char *biggest = NULL;
int cnt = 0;
element_t *ele;
for (struct list_head *pos = (head)->prev, *n = head->prev->prev;
pos != head; pos = n, n = pos->prev) {
ele = list_entry(pos, element_t, list);
if (!biggest || strcmp(biggest, ele->value) <= 0) {
cnt++;
biggest = ele->value;
continue;
}
q_del_element(&ele->list);
}
return q_size(head);
}
```
跟上面的 `ascend` 基本一樣，但是把最小值的紀錄改成最大值的紀錄，然後遇到比紀錄的 `value` 還要小的值，就用 `list_del` 把它刪掉。
### q_merge
>[Commit 238c2b5](https://github.com/sysprog21/lab0-c/commit/238c2b5f9552bd85feb34ef7eeb48d896fc775f1)
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
return list_entry(head->next, queue_contex_t, chain)->size;
}
queue_contex_t *merged_list = list_entry(head->next, queue_contex_t, chain);
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
if (node == head->next) {
continue;
}
queue_contex_t *temp = list_entry(node, queue_contex_t, chain);
list_splice_init(temp->q, merged_list->q);
}
q_sort(merged_list->q, descend);
return merged_list->size;
}
```
用一個 `list_for_each_safe` 來走訪所有在 `chain` 上的節點，然後把它們串在一起，最後把他丟給 `q_sort` 。
## 亂數與論文閱讀
### 在 qtest 提供新的命令 shuffle
#### q_shuffle
>[Commit d8c4e70](https://github.com/sysprog21/lab0-c/commit/d8c4e705a832b942838b578f1b3163ce7fc1f441)
```c
static void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *tmp = head->next;
int len = q_size(head) + 1;
int num;
while (--len) {
struct list_head *current = tmp;
num = rand() % len;
for (int i = 0; i < num; i++) {
current = current->next;
}
if (!num) {
tmp = tmp->next;
continue;
}
list_del(current);
list_add_tail(current, tmp);
}
}
```
使用 `Fisher–Yates shuffle` 演算法來把一個 `queue` 裡面的東西以亂序排列。
先使用 `q_size` 計算 `queue` 中有 `len` 個節點，找一個 `1 ~ len` 之間的隨機數 `num` ，將還存在 `queue` 裡面的第 `num` 個取出來，放到最前面，接著 `len` 就當作少一個，再找一個 `1 ~ len-1` 之間的隨機數`num`，把第 `num + 1` 個節點放到第 `2` 個位置以此類推直到做了 `q_size` 次。
#### 在q_test添加指令shuffle
>[Commit 4d9f7bd](https://github.com/sysprog21/lab0-c/commit/4d9f7bdc0b37b65f595b5f01f304c81aea8cb7cc)
首先可以先發現所有的指令都有在ADD_COMMAND那邊被註冊。
```c
ADD_COMMAND(shuffle, "shuffle", "");
```
接著，根據在 `console.h` 裡面的下面這行我們可以發現我們需要寫一個 `do_shuffle` 的函式。
`#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)`
所以來實做 `do_shuffle` ，首先先做一些針對不合法操作的例外處理。
```c
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q) {
report(3, "Warning: Calling merge on null queue");
return false;
}
```
接著執行 `q_shuffle` 然後如果有錯誤的話就會回到 `exception_setup` 然後回傳 `false` 再跳到 `exception_cancel` 。
參考 `qtest` 其他地方的程式碼可以發現 `current->q` 是現在在用的 `queue` 。所以傳進去函式的參數就用 `current->q` 。
```c
error_check();
if (current && exception_setup(true))
q_shuffle(current->q);
exception_cancel();
q_show(3);
return true;
```
#### 使用測試程式測試亂度
在作業說明的地方有一個亂序的測試程式，使用卡方檢定來驗證 `shuffle` 後的 `queue` 是否有用亂序排列。
但是我發現下面那邊的字串加法真的非常耗時間，於是從網路上查找資料發現它每次用一個 `+` 操作都需要分配一個新的空間來除存兩個字串，這會非常耗時間。
既然發現是分配空間在佔用時間，那就讓它分配少次一點就好，於是我把 `test_count /= 10` ，然後一次給它 `10` 個 `shuffle` ，然後把 `expectation = expectation * 10 + 6` ，果然速度就便快很多了。
```python
...
test_count = 1000000
input = "new\nit 1\nit 2\nit 3\nit 4\n"
for i in range(test_count):
input += "shuffle\n"
input += "free\nquit\n"
...
expectation = test_count // len(s)
```
變成下面這樣。
```python
import subprocess
import re
import random
from itertools import permutations
import random
# 測試 shuffle 次數
test_count = 100000
input = "new\nit 1\nit 2\nit 3\nit 4\n"
for i in range(test_count):
input += "shuffle\nshuffle\nshuffle\nshuffle\nshuffle\nshuffle\nshuffle\nshuffle\nshuffle\nshuffle\n"
input += "free\nquit\n"
# 取得 stdout 的 shuffle 結果
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
s = completedProcess.stdout
startIdx = s.find("l = [1 2 3 4]")
endIdx = s.find("l = NULL")
s = s[startIdx + 14 : endIdx]
Regex = re.compile(r'\d \d \d \d')
result = Regex.findall(s)
def permute(nums):
nums=list(permutations(nums,len(nums)))
return nums
def chiSquared(observation, expectation):
return ((observation - expectation) ** 2) / expectation
# shuffle 的所有結果
nums = []
for i in result:
nums.append(i.split())
# 找出全部的排序可能
counterSet = {}
shuffle_array = ['1', '2', '3', '4']
s = permute(shuffle_array)
# 初始化 counterSet
for i in range(len(s)):
w = ''.join(s[i])
counterSet[w] = 0
# 計算每一種 shuffle 結果的數量
for num in nums:
permutation = ''.join(num)
counterSet[permutation] += 1
# 計算 chiSquare sum
expectation = (test_count // len(s)) * 10 + 6
c = counterSet.values()
chiSquaredSum = 0
for i in c:
chiSquaredSum += chiSquared(i, expectation)
print("Expectation: ", expectation)
print("Observation: ", counterSet)
print("chi square sum: ", chiSquaredSum)
```
輸出的結果為
```
Expectation: 41666
Observation: {'1234': 41735, '1243': 41678, '1324': 41682, '1342': 41477, '1423': 41619, '1432': 41617, '2134': 41662, '2143': 41870, '2314': 41603, '2341': 41644, '2413': 41360, '2431': 41787, '3124': 41685, '3142': 41969, '3214': 41804, '3241': 42045, '3412': 41396, '3421': 41793, '4123': 41796, '4132': 41551, '4213': 41572, '4231': 41507, '4312': 41536, '4321': 41612}
chi square sum: 15.06734507752124
```
`1234` 總共有 `4!` 也就是 `24` 種組合方式，在知道其他 `23` 組的情況下，就能知道剩下那一組，所以自由度是 `23` 。
使用相對常見的 `0.05` 作為顯著水準，使用以下程式碼找出 `P值` 。
```python
from scipy.stats import chi2
print(1 - chi2.cdf(15.06734507752124, 23))
```
得出 `P值` 的結果為 `0.8922036350325095` 大於顯著水準 `0.05` ，故無證據說此分佈不均勻。
### Dude, is my code constant time?
>[Commit e8138b5](https://github.com/sysprog21/lab0-c/commit/e8138b5934b58b01ecf0d8bfc2053013e287d387)
在這篇論文中，在探討是否能用常數時間來完成任務來避免時序攻擊。
利用這篇論文裡面寫的東西，我們可以來幫 `qtest` 做修正確保它測到的時間是常數時間不被其他地方影響。
在把所有的函式實做完成後，會發現第 `17` 筆測試有高機率不會過，得到一個下面的訊息。
`ERROR: Probably not constant time or wrong implementation`
但這個訊息的出現是隨機的，所以我們可以猜到因為某些原因，它會得到錯誤的測量時間，於是就去看 `qtest` 的第 `17` 筆測資是怎麼做的，發現他的輸入為下面這段。
```
option simulation 1
it
ih
rh
rt
option simulation 0
```
從 `qtest` 可以發現，他們 `(it, ih, rh, rt)` 的 `do_##cmd` 都會導到 `fixture.h` 的
```c
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
```
接著就可以在 `fixture.c` 找到我們的目標： `test_const` 。
```c
define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) \
{ \
return test_const(#op, DUT(op)); \
}
#define _(x) DUT_FUNC_IMPL(x)
```
觀察 `test_const` 就會發現要用 `doit(mode)` 來取得結果，且一共要找到 `ENOUGH_MEASURE` 筆資料的時候 `doit(mode)` 回傳 `true` 就會通過測試。
在 `doit(mode)` 裡面的 `prepare_inputs` 負責把資料分成兩個 `class` 一個是 `0 (代表input_data = 0)`、 `1 (代表input_data = random)`
接著使用 `measure()` 也是我開始覺得不太對的地方，首先measure會先根據每個 `input_data` 在 `queue` 裡面放一些的隨機字串(如果是 `class 0` 就只會放一個)，接著紀錄 `CPU` 開始週期執行一次目標操作後紀錄 `CPU` 結束週期，驗證是否有完成操作後 `return` 。
但我覺的比較奇怪的地方是它原本的 `for loop` 如下，只測量了中間的值。
```c
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++)
```
在 `measure` 後，用 `differenate` 去計算花費的總時間。
```c
for (size_t i = 0; i < N_MEASURES; i++)
```
這邊測了全部的時間，但是明明前後的 `DROP_SIZE` 個都沒有做測量，感覺明顯不對，所以我把上面的 `measure` 的 `for` 迴圈也改成跟下面一樣。
接著是使用 `update_statistics` 去上傳測到的資料，在這個函式可以發現它用了 `tpush()` 紀錄了 `class 0, 1` 分別的數量、平均值及$S_{xx}$。
在 `update_statistics` 裡面原本的 `for` 迴圈也長這樣
```c
for (size_t i = 0; i < N_MEASURES; i++)
```
最後接著使用裡面的數據計算 `Welch’s t-test` 的 `t` 值拿到 `report` 去做檢定，利用與 `t_threshold_bananas` 、 `t_threshold_moderate` 做比較，得出是否為常數時間的結論。
那問題究竟出在哪裡，為什麼每次測驗的結果是不穩定的呢？
論文裡面有提到下面這段話，所以我猜想會不會是因為這個原因，所以結果被影響到。
```
"The upper tail may be more influenced by data-independent noise."
```
為了驗證它，我將 `exec_times` 的數據用 `C` 內建的 `qsort` 去做排序，然後將 `upper_tail` 捨棄掉 `DROP_SIZE * 2` 個數據，因為它可能被其他因素影響，會選這個數字是因為原本 `measure` 就只打算做這多次，其他捨去。
所以我把 `update_statistic` 的 `for` 迴圈改成下面這樣。
```c
for (size_t i = 0; i < N_MEASURES - DROP_SIZE * 2; i++)
```
在跑幾次測試後發現果然都非常穩定的通過了，驗證了是因為 `upper_tail` 不穩定才造成了驗證不穩定的結果。
拿到卡比~~
超級開心~~
## linux核心的鏈結串列排序
### list_sort解讀
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
head->prev->next = NULL;
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
}
```
第一階段：看那個 `do_while` 迴圈，這個迴圈要做的事是把 `list` 的東西一個一個拆開變成一個 `單向 linklist` 放在 `pending` 的最後面，以一個排序過的單向 `linklist` 的形式放在裡面，且決定要不要合併，還有要合併哪些。
第二階段：合併剩下的東西。
#### 把東西一個一個拆開
可以看到它找到下一個節點的第一件事是把它的 `next` 改成 `NULL` 使它變成一個單向 `linklist` ，然後把他的 `prev` 接到 `pending` 裡面最後的節點，所以這是一個類似作業裡面 `q_contex_t` 的 `chain` 每一個節點都有一個排序好的 `單向 linklist` 。
#### 決定是否合併
看到它中間的那個 `for` 迴圈可以發現，他是根據 `count` 來決定是否合併，這樣可以在保證有 $3×2^k$ 個節點的時候把其中的 $2^k$ 跟 $2^k$ 個節點合併。
拿 8 個節點為例子
| Count | 確定有幾個節點|Count_in_binary | bits_in_binary | 是否合併 |
| - | - | - | - | - |
| 0 | 1 | 0000 | 0000 | NO|
| 1 | 2 | 0001 | 000 | NO|
| 2 | 3 | 0010 | 0010 | YES|
| 3 | 4 | 0011 | 00 | NO|
| 4 | 5 | 0100 | 0100 | YES|
| 5 | 6 | 0101 | 010 | YES|
| 6 | 7 | 0110 | 0110 | YES|
| 7 | 8 | 0111 | 0 | NO|
#### 要合併哪些節點
可以發現，他在確認要不要合併的時候，`&(*tail)->prev` 這邊的 `tail` 一直往前找，有幾個 `1` 就往前找幾個，最後會找到最後一個 `0` 是在從後面數第幾個出現的， `tail` 就會是倒數第幾個節點，且那個節點的 `queue` 的 `q_size` 會跟他的 `prev` 一樣，把這兩個節點結合後，加上這次的 `loop` 會出現的最新的節點，這兩個節點後面出現的所有節點的 `q_size` 加起來應該會跟`tail`與 `tail->prev` 的 `q_size` 相等，還可以個結論就是 $\lfloor log_2(count+1)+1 \rfloor$ 會是節點的數量。
#### 合並剩下的東西
以 `8` 個節點為例，剩下的東西會是 `size` 為 `4 -> 2 -> 1 -> 1`
的 `pending` 。 這邊從比較小的開始合併所以會變成 `4 -> 2 -> 2` ， `4 -> 4` ， `8` -> 合併完成，也完成排序。
### merge解讀
```c
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
#### 函式cmp
```c
static int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
struct debug_el *ela, *elb;
ela = container_of(a, struct debug_el, list);
elb = container_of(b, struct debug_el, list);
check(priv, ela, elb);
return ela->value - elb->value;
}
```
這邊可以看到，如果 `cmp <= 0` ，就代表 `b` 節點的 `value` 大於等於 `a` 節點的 `value` 。
所以根據上面程式碼很明顯可以看出 `merge` 是照升冪排序。
### 實驗速度差距
>[Commit 5902e9e](https://github.com/sysprog21/lab0-c/commit/5902e9ed1e3aa4017987cc56d62f26bc601250ae)
```c
if (current && exception_setup(true)) {
int64_t ticks = cpucycles();
list_sort(current->q);
ticks = cpucycles() - ticks;
FILE *file = fopen("list_sort_output.csv", "a");
if (file == NULL) {
printf("Failed to open file");
return false;
}
fprintf(file, "%ld\n", ticks);
fclose(file);
}
```
首先修改 `qtest` 裡面 `sort` 的地方，讓它會測時間，且把數據丟進一個檔案。
>[Commit e083f8a](https://github.com/sysprog21/lab0-c/commit/e083f8a253c1cd44d09437ce6a8760a007d5f11f)
把 `list_sort.h` 實做出來。
>[Commit 858bb93](https://github.com/sysprog21/lab0-c/commit/858bb938beffca41ea691ac9b3c65c8255bce916)
修改測試亂度的程式碼讓它改成執行 `qsort` 。
```python
import subprocess
import re
import random
from itertools import permutations
test_count = 1000
input = "new\nit RAND 100000\nsort\nfree\n"
for i in range(test_count):
input += "new\nit RAND 100000\nsort\nfree\n"
input += "quit\n"
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
```
>[Commit e701711]("https://github.com/sysprog21/lab0-c/commit/e701711cbf645acf6c4bbe88aecbf47b0569d925")
用 `matplotlib` 畫出CDF關係圖。
從這邊可以很明顯的看出差距
Sign in with Wallet
Connect another wallet