# 2023q1 Homework1 (lab0)
contributed by < [fewletter](https://github.com/fewletter/lab0-c) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 6
On-line CPU(s) list: 0-5
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
Stepping: 10
CPU MHz: 3000.000
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-5
```
## 開發過程
### 常用結構體
**list_head**
```cpp
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
**element_t**
```cpp
typedef struct {
char *value;
struct list_head list;
} element_t;
```
### q_new
根據 `list.h` 中的 `INIT_LIST_HEAD` 來實作 `q_new` ，此巨集可產生一個 `prev` 和 `next` 都指向自己的 `list_head` 指標，並且沒有包含資料
```cpp
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
**實作流程:**
使用 `malloc` 分配記憶體空間，當配置記憶體空間失敗時，回傳 `NULL` ，若成功則產生一個 `prev` 和 `next` 都指向自己的 `list_head` 指標，並且回傳此結構
```cpp
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
利用 `list.h` 的巨集 `list_for_each_safe` ，其中 `entry` 代表著進行迭代的節點， `safe` 則是 `entry` 的下一個節點， `head` 則指向我們要釋放的串列
```cpp
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
**實作流程:**
* 先偵測 `l` 是否為 `NULL` ，若不為 `NULL` 則進行下面的步驟
* 利用巨集 `list_for_each_safe` 走過每個節點並且移除每個節點
* 將每個移除的節點釋放記憶體
* 最後再釋放 `l` 的記憶體空間
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *node, *next;
list_for_each_entry_safe (node, next, l, list) {
list_del(&node->list);
q_release_element(node);
}
free(l);
}
```
### q_insert_head
實作步驟:
* 檢查 `head` 指向是否為 `NULL` ，是的話回傳 false
* 使用 `malloc` 配置出 `element_t` 大小的記憶體空間，若配置空間失敗，同樣回傳 false
* 利用 `strlen` 計算出 `s` 的長度
* 使用 `malloc` 配置出 `s` 長度再加上1的記憶體空間，若配置空間失敗，同樣回傳 false
* 將字串複製到 `element` 中，再利用 `list_add` 將它加入到 head 後面
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
INIT_LIST_HEAD(&element->list);
int len = strlen(s);
element->value = malloc((len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, len);
*(element->value + len) = '\0';
list_add(&element->list, head);
return true;
}
```
### q_insert_tail
此函式和 `q_insert_head` 的程式幾乎相同，除了倒數第二行從 `list_add` 改成`list_add_tail`
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
INIT_LIST_HEAD(&element->list);
int len = strlen(s);
element->value = malloc((len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, len);
*(element->value + len) = '\0';
list_add_tail(&element->list, head);
return true;
}
```
### q_remove_head
利用巨集 `list_first_entry` ，得到開頭節點的字串
```cpp
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
**實作流程:**
* 檢測此串列是否存在和是否為空，如果不存在或者串列為空的話回傳`NULL`
* 利用 `list_first_entry`，創造出一個 element_t 包含第一個節點和第一個節點的字串
* 將字串複製給 `sp` 後，刪除此節點並且將開頭交給原本串列的第二項
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, target->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del_init(&target->list);
return target;
}
```
### q_remove_tail
此函式和 `q_remove_head` 幾乎相同，只有 `list_first_entry` 需改成`list_last_entry`
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, target->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del_init(&target->list);
return target;
}
```
### q_size
本函式讓指標 `*node` 走訪過每個節點，每走過一個讓 `size+1` ，邏輯並不複雜，所以主要考慮的點為讓程式碼盡量精簡
```cpp
int q_size(struct list_head *head)
{
int size = 0;
struct list_head *node = NULL;
list_for_each (node, head)
size++;
return size;
}
```
### q_delete_mid
本函式利用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉提及的快慢指標來找尋一個串列中間的節點，通過兩個指標不同的速度，讓其中一個指標走完全程時，另一個在此串列的中間。
**實作流程:**
* 建立兩個指標 `fast` 和 `slow`，`fast` 為 `slow` 的兩倍速度
* 走完整個串列，當 `fast` 迭代到底或是迭代到 `head` 時，`slow` 即為我們要找的中點
* 移除 `slow` 並釋放記憶體
```cpp
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 false;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
上面是 Leetcode 的<s>標準</s> 常見解法，但是此題並不只是單向的鏈結串列，而是具備環狀雙向特性，於是除了可指向後一個節點的 `*next` 以外，尚有參照前一節點的 `*prev`，運用前述特性，實作下面程式碼。
**實作流程:**
* 建立兩個指標 `left` 和 `right`，`left` 為從頭開始走的指標，`right` 為從尾巴開始走的指標，兩者速度相同
* 迴圈檢查兩者相遇的地點，移除並且刪掉 `right` 指標
```diff
@@ -4,14 +4,14 @@ bool q_delete_mid(struct list_head *head
if (!head || list_empty(head))
return false;
- struct list_head *fast = head->next;
- struct list_head *slow = head->next;
+ struct list_head *left = head->next;
+ struct list_head *right = head->prev;
- while (fast != head && fast->next != head) {
- fast = fast->next->next;
- slow = slow->next;
+ while (left != right && left->next != right) {
+ left = left->next;
+ right = right->prev;
}
- list_del(slow);
- q_release_element(list_entry(slow, element_t, list));
+ list_del(right);
+ q_release_element(list_entry(right, element_t, list));
return true;
}
```
:::warning
善用 `diff` 展現程式碼變異處，查閱 [diff(1)](https://man7.org/linux/man-pages/man1/diff.1.html) 以熟悉相關用法。
:notes: jserv
:::
### q_delete_dup
```cpp
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head) || list_is_singular(head))
return false;
bool diff = false;
struct list_head *curr, *safe;
list_for_each_safe (curr, safe, head) {
struct list_head *next = curr->next;
element_t *curr_entry = list_entry(curr, element_t, list);
element_t *next_entry = list_entry(next, element_t, list);
if ((next != head) && (!strcmp(curr_entry->value, next_entry->value))) {
list_del(curr);
q_release_element(curr_entry);
diff = true;
} else if (diff) {
list_del(curr);
q_release_element(curr_entry);
diff = false;
}
}
return true;
}
```
### q_swap
本函式使用 `list_move` 來達成兩兩互換的串列
```cpp
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
原本想利用 `list_for_each_safe` 來實作此題的迴圈，但是其中迭代時的其中一行迭代的程式 `node = safe` 會造成迴圈停止，因為此時 `node` 已經移到 `safe` 後面，所以迭代時要使用 `node = node->next` 來進行迭代。
```cpp
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node, *safe;
for (node = (head)->next, safe = node->next; node != (head) && safe != head;
node = node->next, safe = node->next) {
list_move(node, safe);
}
}
```
**實作流程**
下面是一個一般的串列
```graphviz
digraph{
node[shape=box];
h [label="head"]
1 [label="node"]
2 [label="safe"]
rankdir=LR
h->1->2->3->4
4->3->2->1->h
}
```
* `list_del` 將 `node` 從原本的地方移除
```graphviz
digraph{
node[shape=box];
h [label="head"]
1 [label="node"]
2 [label="safe"]
rankdir=LR
1
h->2->3->4
4->3->2->h
}
```
* `list_add` 將 `node` 接在 `safe` 後面
```graphviz
digraph{
node[shape=box];
h [label="head"]
1 [label="node"]
2 [label="safe"]
rankdir=LR
h->2->1->3->4
4->3->1->2->h
}
```
* 讓 `node = node->next` 和 `safe = node->next`，然後依照上面步驟再做一次
```graphviz
digraph{
node[shape=box];
h [label="head"]
3 [label="node"]
4 [label="safe"]
rankdir=LR
h->2->1->3->4
4->3->1->2->h
}
```
### q_reverse
本函式的目的為將 `next` 和 `prev` 相互交換，方法是將指標由指向 `next` 改成指向 `prev` ， 指向 `prev` 改成指向 `next` 。
```cpp
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *front = head->prev, *now = head, *next = NULL;
while (next != head) {
next = now->next;
now->next = front;
now->prev = next;
front = now;
now = next;
}
}
```
**實作流程**
* 將需要迭代的節點 `front` 指向 `head->prev`， `now` 指向 `head`, `next` 指向`head->next`
```graphviz
digraph{
rankdir=LR
node[shape=record]
front [label="front|{<left>prev|<right>next}", style="bold"]
now [label="now|{<left>prev|<right>next}", style="bold"]
next [label="next|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
front:right:e -> now:w
now:right:e -> next:w
now:left:w -> front:e
next:right:e -> node3:w
next:left:w -> now:e
node3:left:w -> next:e
}
```
* 將節點 `now` 的 `*next` 指到節點 `front`， 節點 `now` 的 `*prev` 指到節點 `next` ，交換 `front` 和 `next` 的位置
```graphviz
digraph{
rankdir=LR
node[shape=record]
front [label="next|{<left>prev|<right>next}", style="bold"]
now [label="now|{<left>prev|<right>next}", style="bold"]
next [label="front|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
front:right:e -> now:w
now:right:e -> next:w
now:left:w -> front:e
next:right:e -> node3:w
next:left:w -> now:e
node3:left:w -> next:e
}
```
* 進行下一次的迭代位置
```graphviz
digraph{
rankdir=LR
node[shape=record]
front [label="0|{<left>prev|<right>next}", style="bold"]
now [label="front|{<left>prev|<right>next}", style="bold"]
next [label="now|{<left>prev|<right>next}", style="bold"]
node3 [label="next|{<left>prev|<right>next}", style="bold"]
front:right:e -> now:w
now:right:e -> next:w
now:left:w -> front:e
next:right:e -> node3:w
next:left:w -> now:e
node3:left:w -> next:e
}
```
### q_reverseK
本函式利用 `list_move`，將每個需要被反轉的節點，依序接到另行建立的 `empty` 節點，再用 `list_splic_init` 連接已觸及的節點。
```cpp
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || k <= 1)
return;
struct list_head *node, *start, *anchor = head;
LIST_HEAD(empty);
int count = 0;
int time_mark = 0;
int size = q_size(head);
list_for_each_safe (node, start, head) {
count++;
if (count <= k && (size - time_mark) >= k) {
list_move(node, &empty);
if (count == k) {
list_splice_init(&empty, anchor);
count = 0;
time_mark += k;
anchor = start->prev;
}
}
}
}
```
:::warning
撰寫更精簡的程式碼。
:notes: jserv
:::
**實作流程**
* 下面以 `k=2` 作為舉例
```graphviz
digraph{
node[shape=box];
rankdir=LR
empty[label="empty"]
h[label="head"]
h->1->2->3->4->5->6
6->5->4->3->2->1->h
}
```
* `list_move` 第一個節點到 `empty` 後
```graphviz
digraph{
node[shape=box];
rankdir=LR
empty[label="empty"]
empty->1
1->empty
h[label="head"]
h->2->3->4->5->6
6->5->4->3->2->h
}
```
* `list_move` 第二個節點到 `empty` 後，得到反轉後的串列
```graphviz
digraph{
node[shape=box];
rankdir=LR
empty[label="empty"]
empty->2->1
1->2->empty
h[label="head"]
h->3->4->5->6
6->5->4->3->h
}
```
* `list_splic_init` 接回去
```graphviz
digraph{
node[shape=box];
rankdir=LR
h[label="head"]
h->2->1->3->4->5->6
6->5->4->3->1->2->h
}
```
### q_descend
仿照 `list_for_each_safe` 的迴圈方法，寫一個 `prev` 的迴圈版本，想法是將所有節點與迭代中的最大值做比較。
**實作流程**
* 建立 `char *s` 來記錄結尾的字串
* 建立迴圈，走訪每個節點，但是結尾字串不比較
* 若 `s` 小於節點的內含值，`s` 則變為節點的值，反之則將節點刪除並且釋放記憶體空間
```cpp
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
struct list_head *node, *safe;
char *s = list_entry(head->prev, element_t, list)->value;
for (node = (head)->prev, safe = node->prev; node != (head);
node = safe, safe = node->prev) {
element_t *tmp = list_entry(node, element_t, list);
if (node != head->prev) {
if (strcmp(s, tmp->value) < 0) {
s = tmp->value;
} else {
list_del(&tmp->list);
q_release_element(tmp);
}
}
}
return q_size(head);
}
```
:::warning
上方程式碼迴圈內的 if-if-else 可簡化。
:notes: jserv
:::
### q_merge
此函式會使用到下面的結構體
```cpp
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
:::warning
避免只用圖示來解釋 `queue_context_t`，你應該先用清晰的文字敘述，再搭配圖解。
:notes: jserv
:::
`queue_contex_t` 結構體， `head` 與 `chain` 的關係
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold]
h [label="head|{<prev>prev|<next>next}"]
node[shape=record, style=bold];
subgraph cluster_1 {
q [label="q"];
chain [label="chain|{<prev>prev|<next>next}"];
size1 [label="{size}"];
id [label="{id}"];
style=bold;
label=queue_contex_t
}
h:next:e -> chain:w
node[shape=record, style=bold]
subgraph cluster_2 {
next_q [label="q"];
next_chain [label="chain|{<prev>prev|<next>next}"];
next_size1 [label="{size}"];
next_id [label="{id}"];
style=bold;
label=queue_contex_t
}
chain:next:e -> next_chain:w
chain:prev:w -> h:e
next_chain:prev -> chain:e
}
```
此函式必須要靠著 `head` 迭代出所有結構體 `queue_contex` 當中的串列 `q`，然後把每一個串列 `q` 以由小到大排序的順序串接起來，其中必須先將串列 `q` 利用指標 `q->prev->next` 指向 `NULL` 變成 singly-linked list，最後頭尾再接起來形成完整的 doubly-linked list。
**實作流程**
* 先切斷每個節點部分的連接， `iter->q->prev->next = NULL`
* 再將兩個串列利用 `mergeTwolists` 合併
```cpp
queue_contex_t *iter;
list_for_each_entry (iter, head, chain) {
iter->q->prev->next = NULL;
merge_node = mergeTwolists(merge_node, iter->q->next);
INIT_LIST_HEAD(iter->q);
}
```
* 走過整個串列後，形成完整的 doubly-linked list，最後回傳`q_size(q_head)`
```cpp
struct list_head *curr = q_head->q, *next = curr->next;
while (next) {
next->prev = curr;
curr = next;
next = next->next;
}
curr->next = q_head->q;
q_head->q->prev = curr;
```
### q_sort
參考〈[你所不知道的 C 語言: linked list 和非連續記憶體: Merge Sort 的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)〉和〈[Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort#Merge-Sort-%E8%88%87%E5%AE%83%E7%9A%84%E8%AE%8A%E5%8C%96)〉中的 merge sort 的遞迴程式碼。
#### mergeTwolists
本函式的目的為將兩個串列以由小到大排序的順序連接在一起，並利用間接指標 `**ptr` 來指向兩個串列中迭代到的節點，避免使用 `malloc` 配置多的記憶體，無法釋放記憶體空間，此函式也是實作 `merge` 時會利用到的函式。
**實作流程**
* 利用 `list_entry` 將兩個串列個別節點的 `value` 相互比較
* 將 `*node` 指向 `value` 比較過後較小的節點
* 將 `*ptr` 指向 `*node` ，最後再迭代到下一個節點
```cpp
struct list_head *mergeTwolists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
while (L1 && L2) {
element_t *L1_entry = list_entry(L1, element_t, list);
element_t *L2_entry = list_entry(L2, element_t, list);
node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
*node = (*node)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
#### merge_sort
本函式的想法即為將一個串列從中間一直切成兩份並在最後結合在一起
**實作流程**
* 利用快慢指標找到中間的節點
```cpp
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
```
* 利用遞迴將每個節點一個個分開，再利用 `mergeTwolists` 將兩個節點以由小到大排序的順序一直合併
```cpp
struct list_head *left = merge_sort(head), *right = merge_sort(mid);
return mergeTwolists(left, right);
```
#### sort
**實作流程**
* 將頭尾切開
* 利用 `merge_sort` 一直分開和合併節點
* 走過每個節點形成一個完整的 circular doubly linked list
```cpp
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *curr = head, *next = curr->next;
while (next) {
next->prev = curr;
curr = next;
next = next->next;
}
curr->next = head;
head->prev = curr;
}
```
---
### 研讀 Linux 核心原始程式碼 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
:::danger
與其逐行列出程式碼，你應該先闡述 Linux 核心開發者到底要解決什麼問題，以及這些考量如何反映在設計中。
:notes: jserv
> 了解，謝謝老師
:::
研讀 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)前，第一個問題是自己所寫 `merge sort` 有什麼問題需要解決？
從[Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e)中可以知道，自己所寫 `merge sort` 為 `Top-down mergesort` 是透過不停的 `partition` (分割)，最後在兩兩串列合併成最後的串列，並且過程中完全沒有考慮到 `cache` 。
```
* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
```
從以上註解可知道 Linux 核心開發者採用了只有合併串列，並且避免 `cache thrashing` 的合併方法，此種方法少了`partition` (分割)這樣一直更新串列的動作，同時也對 `cache` 更友善。
閱讀 list_sort.c 程式碼時可以發現，此程式碼由三個函式 `merge` ， `merge_final` ， `list_sort` 所組成。
`merge` 此函式可以看到 `cmp(priv, a, b)` ， 從 `list_sort.h` 中可以看到其定義。
```cpp
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))
static int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
element_t *list1_entry = list_entry(list1, element_t, list);
element_t *list2_entry = list_entry(list2, element_t, list);
return strcmp(list1_entry->value, list2_entry->value) < 0 ? 0 : 1;
}
```
雖然還不知道 `__attribute__((nonnull(2,3)))` 是什麼，但是從下面的程式可以看出這是一個比較大小的函式，放到 `merge` 裡面的程式碼中，就可以看出如果當一個串列是以<s>升冪</s> --- 由小到大排序的方式傳入， `merge` 就會以由小到大排序的方式結合兩個串列，反之由大到小排序也是相同情況。
:::warning
查閱教育部辭典「[升冪](https://dict.revised.moe.edu.tw/dictView.jsp?ID=132234)」:
> 數學代數式中，某一字母的指數，由低順次至高，稱為此一字母的「升冪」。
這裡不是多項式。
:notes: jserv
:::
```cpp
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;
}
}
}
```
:::warning
對解說的程式碼以一致的程式碼風格排版，善用 `clang-format`
:notes: jserv
:::
### 嘗試引入 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 到 `lab0-c` 專案中
參考[ **`qtest`** 命令直譯器的實作](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)
* 複製 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 程式碼到 `list_sort.c` 和所需要的標頭檔到 `list_sort.h`
標頭檔程式碼
```cpp
#ifndef _LIST_SORT_H
#define _LIST_SORT_H
#include <stdint.h>
#include "list.h"
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif
```
* 從 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中可以知道需要巨集 `likely`，`unlikely` 和函式指標 `list_cmp_func_t`
* 增加 `linux_sort` 到 `qtest.c` 中，可以讓自己手動測試
為了能夠分別測試 `list_sort` 和實作的 `sort` ，所以按照[ **`qtest`** 命令直譯器的實作](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)的步驟在 `qtest`裡面新增命令 `linux_sort` 。
:::warning
研讀 `option` 相關程式碼，以此切換排序的實作，這樣就不用引入彆扭的 `linux_sort` 新命令，日後可繼續在 `option` 擴充新的排序演算法，但不用新增命令。
:notes: jserv
:::
```cpp
ADD_COMMAND(linux_sort,
"Sort queue in ascending order by using Linux kernel", "");
```
仿照 `do_sort` 實作 `do_linux_sort` ，作法是將下面程式碼
```cpp
if (current && exception_setup(true))
q_sort(current->q);
```
改成
```cpp
if (current && exception_setup(true))
list_sort(NULL, current->q, cmp);
```
* 增加 `trace-linux_sort.cmd` 和 `trace-sort.cmd` 來自動測試 `list_sort` 和 `sort`
**`trace-linux_sort.cmd`**
```cpp
option fail 0
option malloc 0
new
ih RAND 100000
linux_sort
time
```
**`trace-sort.cmd`**
```cpp
option fail 0
option malloc 0
new
ih RAND 100000
sort
time
```
### 比較 `merge sort` 與 Linux 核心程式碼效能
執行 `trace-sort_compare.cmd` ，執行以下命令:
```
./qtest -f traces/trace-linux_sort.cmd
./qtest -f traces/trace-sort.cmd
```
執行結果如下
```cpp
l = []
l = [itisgpj stgknec uwget ermhm lqfrjs rgbdzwkia niyuvs pmpwnspem igpiww ngtfqwzri pytuioyh vlmcweivt aricspdeo lgsbl dvbhfohee ervqwsuj owpubrys cswmotz pppoocle dfrsbh wcsuq txlgnm xymdctq clviiyx ksvodq qiavlv funhx ztivnniyz rqplaqwh rmndrks ... ]
l = [aaakfol aaalei aaapry aaayu aabihget aablmstks aabnmex aabnqexg aabogae aabuq aabwzdvd aabxpat aacchunqy aacmwy aacwzasyh aacxvldzv aaczhmu aadajyh aadgxr aadmyblgk aadnufbz aadwf aadzx aaeby aaeffxrkn aaejrpx aaejvwhle aaemen aaenfh aaevvyptr ... ]
Elapsed time = 0.159, Delta time = 0.159
```
```cpp
l = []
l = [xfxddnmsv quamfmmc ogadbq hncje puoqkxjz rysllv lutjl mmsbruz ctqhmyl jkxwbywy myedjyr ohjmzyy zvolja xolyhka fppekszq ymummjic ootvvl hyxhm sfbtu ysgujjdl fspczebyo grmukar ewasih ylcay jgeqj cbzohwigb wkfyq dvxoi eecsqda rfwefxcj ... ]
l = [aaafp aaaojws aaatw aaayfm aaayzjud aabbxbdde aabfbux aabfjeji aabgbbco aabnxncu aabpj aabpyou aabso aabtoavy aabvaqgx aacbp aacdkjlz aacdrzhbv aacfzhhx aacuco aadvgu aadvx aaeea aaeetqcvi aaega aaehhuak aaejhhb aaelvp aaenapv aaeouak ... ]
Elapsed time = 0.179, Delta time = 0.179
```
**ih RAND 100000**
| | q_sort | list_sort |
|:------------:|:------:|:---------:|
| Elapsed time | 0.179 | 0.159 |
| Delta time | 0.179 | 0.159 |
**ih RAND 500000**
| | q_sort | list_sort |
|:------------:|:------:|:---------:|
| Elapsed time | 1.1014 | 0.808 |
| Delta time | 1.1014 | 0.808 |
**ih RAND 1000000**
| | q_sort | list_sort |
|:------------:|:-----------------:|:---------:|
| Elapsed time | Time limit exceed | 1.725 |
| Delta time | Time limit exceed | 1.725 |
接著利用 [perf 原理和實務](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg#perf-%E5%8E%9F%E7%90%86%E5%92%8C%E5%AF%A6%E5%8B%99x96)檢測 `cache-misses`，`cache-references`，`instructions`，`cycles` 四個項目
**ih RAND 500000**
| | q_sort | list_sort |
|:----------------:|:------------:|:------------:|
| cache-misses | 5032,7722 | 3538,6984 |
| cache-references | 8940,8835 | 6581,8426 |
| instructions | 21,2075,2982 | 21,1753,5235 |
| cycles | 45,0536,4432 | 33,9000,1693 |
從上面數據可以看到除了 `instructions` 大約相同外，其他項目 `linux_sort` 都比 `q_sort` 還少
:::warning
TODO: 針對排序演算法的限制，設計足以產生 worst-case 的測試案例。
:notes: jserv
:::
參考[Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e#Linux-%E6%A0%B8%E5%BF%83%E6%8E%92%E5%BA%8F%E5%AF%A6%E4%BD%9C%E7%9A%84%E6%BC%94%E9%80%B2)
想法：
* `list_sort` 是一種只有合併的 `mergesort` ， 代表其 worst-case 是比較次數較多的串列
* 將比較次數最大化，即為將一個完全是由大到小排序的串列傳入
實作流程：
* 先給一個隨機的串列
* 利用 `list_sort` 將串列排列
* 將已經排序的的串列排成由大到小排序順序(reverse)
* 分別紀錄 `list_sort` 和 `q_sort` 的時間
測試結果如下：
* 串列大小 30000
**q_sort**
```
Elapsed time = 0.057, Delta time = 0.057
Elapsed time = 0.074, Delta time = 0.017
Performance counter stats for './qtest -f traces/trace-worst-sort.cmd':
179,5892 cache-misses # 35.594 % of all cache refs
504,5521 cache-references
1,3893,6266 instructions # 0.55 insn per cycle
2,5346,8567 cycles
0.075241075 seconds time elapsed
```
開始排序時間為 0.57，排序完成時間為 0.74，排序時間為 0.17
**list_sort**
```
Elapsed time = 0.045, Delta time = 0.045
Elapsed time = 0.063, Delta time = 0.018
Performance counter stats for './qtest -f traces/trace-worst-linux_sort.cmd':
205,1925 cache-misses # 43.335 % of all cache refs
473,5060 cache-references
1,3853,7035 instructions # 0.54 insn per cycle
2,5478,4476 cycles
0.064160188 seconds time elapsed
```
開始排序時間為 0.45，排序完成時間為 0.63，排序時間為 0.18
| 串列大小 / merge 種類 | q_sort | list_sort |
|:------------------:|:------:|:---------:|
| 10000 | 0.02 | 0.03 |
| 30000 | 0.17 | 0.18 |
| 100000 | 0.97 | 0.59 |
**串列大小 10000**
| | q_sort | list_sort |
|:----------------:|:---------:|:---------:|
| cache-misses | 10,7731 | 21,2893 |
| cache-references | 136,5123 | 132,8497 |
| instructions | 4637,2298 | 4617,1204 |
| cycles | 5828,7503 | 6080,4767 |
**串列大小 30000**
| | q_sort | list_sort |
|:----------------:|:-----------:|:-----------:|
| cache-misses | 179,5892 | 205,1925 |
| cache-references | 504,5521 | 473,5060 |
| instructions | 1,3893,6266 | 1,3853,7035 |
| cycles | 2,5346,8567 | 2,5478,4476 |
**串列大小 100000**
| | q_sort | list_sort |
|:----------------:|:------------:|:-----------:|
| cache-misses | 1189,0006 | 1050,7305 |
| cache-references | 2089,1345 | 1916,7928 |
| instructions | 4,7343,4558 | 4,6870,1310 |
| cycles | 11,5324,7931 | 9,4894,3256 |
從上面四個表格可以看出，即使是在 `list_sort` 排序的最壞情況，時間都可以幾乎跟 `q_sort` 一樣，但是在 `cache-misses` 這項指標中，在 `list_sort` 排序的最壞情況，串列大小越小， `list_sort` 比 `q_sort` 多了很多，代表此項指標影響速度的程度很大，要降低排序時間首先的目標是要降低此項指標。
---
## 在 qtest 提供新的命令 shuffle
參考[ **`qtest`** 命令直譯器的實作](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)
* 在 `qtest.c` 中加入下面程式碼
```cpp
ADD_COMMAND(shuffle, "Shuffle the queue", "");
```
* 實作 `q_shuffle` 於 `qtest.c` 中
* 利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
* `q_size` 取得整體串列大小
* 隨機選取節點並將其移至尾巴
```cpp
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int len = q_size(head);
while (len != 0) {
struct list_head *node = head->next;
int pos = rand() % len;
for (int i = 0; i < pos; i++)
node = node->next;
list_move_tail(node, head);
len--;
}
};
```
* 實作 `do_shuffle` 程式碼，主要是讓自己所寫的 `q_shuffle` 可以在 `qtest.c` 中測試
* 程式碼
```cpp
if (exception_setup(true))
q_shuffle(current->q);
```
* 測試結果
```cpp
cmd> new
l = []
cmd> ih RAND 5
l = [cnytb rbjjuwnh afwpqjmpz cayfh kkzddhit]
cmd> sort
l = [afwpqjmpz cayfh cnytb kkzddhit rbjjuwnh]
cmd> shuffle
l = [cnytb afwpqjmpz kkzddhit cayfh rbjjuwnh]
```
### 統計方法驗證 shuffle
為了讓[測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)可以在本地端直接使用 `make shuffle` 命令執行，所以執行下面的流程
* 開啟新檔案將[測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)程式碼貼到新檔案中
* 將新檔案檔名加入到 `Makefile` 中
```
shuffle:
python3 scripts/shuffle.py
```
* 執行 `make shuffle` 命令即可得到一個串列 `shuffle` 過後的出現次數的直方圖
* 測試結果
```
0.3513854055416222
0.28514514058056234
0.0021660086640346563
0.24725498901995607
6.000024000096e-06
0.3313513254053016
Expectation: 166666
Observation: {'123': 166908, '132': 166884, '213': 166647, '231': 166463, '312': 166667, '321': 166431}
chi square sum: 1.2173088692354768
```
由上圖來看，此圖符合 uniform distribution。
* 計算chi-squared test statistic
$$X^2 = \sum\limits_{i=1}^{n}\frac{(O_i-E_i)^2}{E_i}$$
| | 公式計算 | chi-squared |
|:-----:|:------------------------------------:|:-----------:|
| $123$ | $$\frac{(166908-166666)^2}{166666}$$ | $0.3514$ |
| $132$ | $$\frac{(166884-166666)^2}{166666}$$ | $0.2851$ |
| $213$ | $$\frac{(166647-166666)^2}{166666}$$ | $0.0026$ |
| $231$ | $$\frac{(166463-166666)^2}{166666}$$ | $0.2473$ |
| $312$ | $$\frac{(166667-166666)^2}{166666}$$ | $6\times10^{-6}$ |
| $321$ | $$\frac{(166431-166666)^2}{166666}$$ | $0.3314$ |
| 總和 | | $1.2173$ |
* 統計檢定的結果不拒絕虛無假說
$α = P$(拒絕 $H_0$ | $H_0$ 為真)
:::warning
改用 LaTeX 重寫數學式
:notes: jserv
:::
在此將 $α$ 設為 0.05。
由於 [1,2,3] 有六種排列情形，所以它有 5 個自由度，根據[卡式分佈表](https://en.wikipedia.org/wiki/Chi-squared_distribution)， $P$ value 介於 0.95 到 0.9 之間，因為 $P$ value（0.95~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）。
---
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
本篇論文在討論 `dudect` ，一項工具來評估一段程式是否可以在給定時間(constant time)運行。
而為什麼 `constant time` 對一段程式碼如此重要，可以參考[解讀計算機編碼：在資訊安全的應用](https://hackmd.io/@sysprog/binary-representation#%E7%AC%AC%E4%B8%89%E9%83%A8%E5%88%86%EF%BC%9A%E5%9C%A8%E8%B3%87%E8%A8%8A%E5%AE%89%E5%85%A8%E7%9A%84%E6%87%89%E7%94%A8)，又或是論文上的這段話
```
Kocher writes in 1996 his seminal paper on recovering cryptographic
keys by measuring the execution time of cryptographic
implementations [Koc96 ]. More concretely, he exploits data-
dependent variance in the execution time of RSA, DSS or Diffie-
Hellman to recover secret key bits in a divide-and-conquer
fashion. Since then, timing attacks have been broken numerous
variable-time implementations, including high-impact systems
such as TLS [ AP13 ]. In comparison to other side-channel
attacks, timing attacks require minimal interaction with the
target and can be mounted remotely [BB03].
```
簡單來說就是通過程式實作時的一些指標，比如說程式執行時間，來推斷程式碼隱藏的東西。
`dudect` 是一種不需要知道 CPU 硬體結構也可以實作的檢測方法，此論文提及一些其他的研究作法，不過其他研究的共同缺點是都需要知道 CPU 硬體結構。
以下是此論文所提及的**檢測步驟**：
1. 在有可能造成洩漏 (potential leakages) 測試範圍分成兩種測試方法，一種是固定測試(constant)，一種是隨機測試 (random)。
2. 資料後處理 (post-processing)， `Cropping` 主要是修剪掉較長的執行時間， `Higher-order preprocessing` 則是根據統計檢測來應用。
3. 應用統計測試，主要有兩種測試方法，第一種為 `Welch’s t-test` ， 第二種則為 `Non-parametric tests` 。
### 解釋 Student’s t-distribution 及程式實作的原理
* **Student's t-distribution** 主要是作為兩組數據的抽樣檢查，只要兩組數據越多，越接近常態分布，之後檢查兩者分布如果越相近，便會主張兩者皆為 `constant time` 。
* **Student's t-distribution** 通常假設兩者的變異數相同，所以 **Welch’s t-test** 此種可以應用在不同變異數的統計測試方法被提出。
* **Welch’s t-test** 中的 t 定義如下
$$t=\frac{\overline{X}_0-\overline{X}_1}{\sqrt{\frac{var_0}{N_0}+\frac{var_1}{N_1}}}$$
* 由於兩組數據變異數不相同，因此需要對 t 分布的自由度做加權後才可以檢定，加權過後的自由度定義如下
$$df^{'}=\frac{(\frac{var_1^2}{n_1}+\frac{var_2^2}{n_2})^2}{\frac{var_1^2/n_1}{n_1-1}+\frac{var_2^2/n_2}{n_2-1}}$$
**`simulation` 程式實作原理**
* 首先先查看 `qtest.c` 中有關 `simulation` 的命令
```cpp
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok = 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;
}
```
* 由上面可以看到，如果進入 `simulation` 模式，重點是 `is_insert_head_const()` 此函式會傳出 `do_ih` 執行時間是否為 `constant time`。
* 尋找 `is_insert_head_const()` ，在 `fixure.h` 中找到下面這項巨集
```cpp
#define _(x) bool is_##x##_const(void);
```
* 在 `fixure.c` 中找到下面巨集
```cpp
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
```
* 然後再沿著 `test_const()` 此項函式繼續尋找，路徑大概如下 `test_const()` $\to$ `doit()` $\to$ `report()` ，得知決定 `is_insert_head_const()` 是 true 或是 false 的關鍵在 `report()` 中
```cpp
double max_t = fabs(t_compute(t));
double number_traces_max_t = t->n[0] + t->n[1];
double max_tau = max_t / sqrt(number_traces_max_t);
```
* `t_compute()` 就是在計算 **Welch’s t-test** 中的 t
```cpp
double t_compute(t_context_t *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
* 從 `report()` 中可以看到有三種情況會讓 `qtest.c` 中的 `ih` 測試結果不是 `constant time`
* 第一種是測量的 cpu cycle 太少
```cpp
if (number_traces_max_t < ENOUGH_MEASURE) {
printf("not enough measurements (%.0f still to go).\n",
ENOUGH_MEASURE - number_traces_max_t);
return false;
}
```
* 第二、三種是從 **Welch’s t-test** 計算出來的 t 太大無法通過測試標準
```cpp
/* Definitely not constant time */
if (max_t > t_threshold_bananas)
return false;
/* Probably not constant time. */
if (max_t > t_threshold_moderate)
return false;
```
* 要讓 `trace-17-complexity.cmd` 通過最簡單的方法就是調整測試標準，不過此方法就代表上述統計檢驗方法完全沒用到，所以還在研究其他方法中。
```cpp
enum {
t_threshold_bananas = 50000, /* Test failed with overwhelming probability*/
t_threshold_moderate = 100, /* Test failed*/
};
```
* 測試結果
```
+++ 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
```
* [ oreparaz/dudect ](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)還在研究中
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
TODO
Sign in with Wallet
Connect another wallet