# 2024q1 Homework1 (lab0)
contributed by < `Grace258` >
### Reviewed by `HenryChaing`
>可以再詳閱課程教材補充背景知識，指標觀念可以再補強。
>其餘的 review 在底下有留言
## 開發環境
```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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
CPU family: 6
Model: 166
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 3199.92
```
:::warning
在終端機執行 `export LC_ALL=C` 並執行上述命令，可得到英語的輸出訊息，原本中文訊息用語不精準。
:::
## 指定的佇列操作
> 請附上 commit 紀錄，以及 github repository 連結， 你的 [github](https://github.com/Grace258/lab0-c)。
> [name=HenryChaing]
### `q_new`
建立一個的 `struct list_head *` ，如果沒有足夠空間配置的話，回傳 `NULL` 。
如果有成功配置空間，將其初始化成符合環狀雙向鏈結串列的 `head` 指標。
> 我們要請求配置 `struct list_head` 的記憶體空間，成功的話指標會指向剛才配置成功的空間。
> [name=HenryChaing]
### `q_free`
```c
list_for_each_safe (current, next_node, head) {
element_t *node = list_entry(current, element_t, list);
list_del(current);
q_release_element(node);
}
free(head);
```
因為要刪除 `current` 所在的節點，所以使用定義在 `list.h` 的 `list_for_each_safe` 走訪所有的節點，讓 `next_node` 記住 `current` 要移動到的下一個位置，最後再刪除剩下的 `head` 指標。
> `head` 指標並沒有被刪除，我們做的是釋放 `head` 所指向的記憶體空間，參閱： [課程教材](https://hackmd.io/@sysprog/c-memory#%E8%83%8C%E6%99%AF%E7%9F%A5%E8%AD%98)。
> [name=HenryChaing]
### `q_insert_head`
```c
element_t *new_element = malloc(sizeof(element_t));
new_element->value = malloc(strlen(s) + 1);
strncpy(new_element->value, s, strlen(s) + 1);
list_add(&new_element->list, head);
```
將要插入到 `head` 的字串 `s` 用 `element_t` 將其存取，因為 `element_t` 才是鏈結串列節點的資料型態，因為 `s` 和 `new_element->value` 都是指標，因此要用 `strncpy` 來複製，因為對指標使用 `＝` 是指向的意思。
> 指標也是紀錄資料，但是紀錄的是記憶體位置，因此 $=$ 依舊是賦予數值的作用 。
> [name=HenryChaing]
:::danger
改進你的漢語表達。
:::
### `q_insert_tail`
```c
element_t *new_element = malloc(sizeof(element_t));
new_element->value = malloc(strlen(s) + 1);
strncpy(new_element->value, s, strlen(s) + 1);
list_add_tail(&new_element->list, head);
```
操作原理和 `q_insert_head` 相似，差別在於使用 `list_add_tail` 將節點插到最後面。
> 將節點插入串列尾端。
> [name=HenryChaing]
### `q_remove_head`
```c
struct list_head *first = head->next;
element_t *first_element = list_entry(first, element_t, list);
strncpy(sp, first_element->value, bufsize);
list_del(first);
```
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
建立一個指標 `first` 指向鏈結串列中的第一個節點，建立一個 `element_t` 來取得要移除的節點的字串，將字串內容複製到 `sp` 中，並且要注意字串的最後是 `\0` 因此長度是字母數量 `+1` 。
> 字串長度+1較恰當，電腦科學用語中字元才是單位量詞。
> [name=HenryChaing]
### `q_remove_tail`
```c
struct list_head *last = head->prev;
element_t *last_element = list_entry(last, element_t, list);
strncpy(sp, last_element->value, bufsize);
list_del(last);
```
操作原理和 `q_remove_head` 相似，差別在於指標一開始是指向鏈結串列的最後一個節點。
### `q_size`
```c
list_for_each (current, head) {
count++;
}
```
使用 `list_for_each` 走訪每一個節點，用 `count` 來計算走過得節點數量。
### `q_delete_mid`
```c
list_for_each (fast, head) {
fast = fast->next;
slow = slow->next;
if (fast == head)
break;
}
list_del(slow);
element_t *deleted_element = list_entry(slow, element_t, list);
if (deleted_element->value != NULL) {
free(deleted_element->value);
}
free(deleted_element);
```
使用 `list_for_each` 和快慢指標走訪， `fast` 一次走兩個節點， `slow` 一此走一個節點，當 `fast` 走完整個 `list` 後，就代表 `slow` 已經走到中間的節點，此時將其刪除，刪除不同於移除，需要釋放記憶體空間。
### `q_delete_dup`
```c
bool last_check = false;
list_for_each_safe (current, next_node, head) {
element_t *nodeA = list_entry(current, element_t, list);
element_t *nodeB = list_entry(next_node, element_t, list);
if (next_node != head && strcmp(nodeA->value, nodeB->value) == 0) {
last_check = true;
list_del(current);
q_release_element(nodeA);
}
else if (last_check) {
last_check = false;
list_del(current);
q_release_element(nodeA);
}
}
```
要刪除所有重複的節點（包含當前的節點），因此會用到一個 `bool` 的 `flag` `last_check` 可以用來檢查當前節點是否是要刪除的最後一個節點，因為是 `delete` 所以會用到 `q_release_element` 來釋放記憶體空間。
### `q_swap`
```c
q_reverseK(head, 2);
```
相鄰的兩個節點互換其實就是以 `2` 為單位反轉節點，因此可以直接使用 `q_reverseK`。
### q_reverse
```c
list_for_each_safe (current, next_node, head) {
list_move(current, head);
current = next_node;
}
```
這裡的想法是走訪每一個節點，並將當前節點移至 `list` 的最前面。
### q_reverseK
```c
INIT_LIST_HEAD(&start);
end = head;
list_for_each_safe (current, next_node, head) {
count++;
if (count == k) {
list_cut_position(&start, end, current);
q_reverse(&start);
list_splice_init(&start, end);
count = 0;
end = next_node->prev;
}
}
```
先初始化一個指標 `start` 用來標示 `group K` 的第一個節點，在反轉之後將其接到 `group K` 的下一個節點的前面。
### q_sort
```c
merge_sort(head);
if (descend)
q_reverse(head);
```
對 `list` 做 `merge sort` ，因為我寫的 `merge sort` 是上升排序，所以如果`descend` 為真，要對整個 `list` 做反轉。
### q_ascend
```c
list_for_each_entry_safe (current, next_node, head, list) {
element_t *scan = list_entry(&next_node->list, element_t, list);
while (&scan->list != head) {
if (strcmp(scan->value, current->value) < 0) {
list_del(¤t->list);
q_release_element(current);
break;
}
scan = list_entry(scan->list.next, element_t, list);
}
}
```
用兩個迴圈走訪節點，當內圈迴圈走訪到的節點小於外圈迴圈所在的節點時，表示此時的 `list` 不是上升排序，因此要刪除外圈迴圈的當前節點。
:::warning
撰寫出更精簡的程式碼。
:::
### `q_descend`
```c
list_for_each_entry_safe (current, next_node, head, list) {
element_t *scan = list_entry(&next_node->list, element_t, list);
while (&scan->list != head) {
if (strcmp(scan->value, current->value) > 0) {
list_del(¤t->list);
q_release_element(current);
break;
}
scan = list_entry(scan->list.next, element_t, list);
}
}
```
操作和 `q_ascend` 相似，差別在於刪除節點的時機是當內圈迴圈走訪到的節點大於外圈迴圈所在的節點時。
### `q_merge`
```c
queue_contex_t *m_queue = list_entry(head->next, queue_contex_t, chain);
queue_contex_t *node;
list_for_each_entry (node, head->next, chain) {
if (node == list_entry(head, queue_contex_t, chain))
break;
list_splice_tail_init(node->q, m_queue->q);
m_queue->size += node->size;
node->size = 0;
}
```
將所有的 `queue` 接在一起，使用的資料型態是 `queue_contex_t` 用來表示多個 `list` 。
---
## Valgrind 排除記憶體錯誤
```
==7733== 40 bytes in 1 blocks are still reachable in loss record 34 of 40
==7733== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==7733== by 0x10DB6C: malloc_or_fail (report.c:215)
==7733== by 0x10EA73: add_param (console.c:105)
==7733== by 0x10D32D: console_init (qtest.c:1055)
==7733== by 0x10D32D: main (qtest.c:1238)
```
:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類。
:::
這個錯誤訊息表示在程式結束時仍有一些動態分配的記憶體（使用malloc分配的）沒有被釋放，導致這些記憶體被視為 `reachable` ，也就是說，程式結束時仍然可以訪問到這些記憶體。
:::danger
詳閱 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)。
:::
`==7733==` : 是 `Valgrind` 的`process ID`
`at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)` : 表示記憶體分配操作發生的位置
`by 0x10DB6C: malloc_or_fail (report.c:215)` : 表示程式執行中的呼叫堆疊，以及記憶體操作是被 `malloc_or_fail` 這個 `function` 使用的，並且這個 `function` 位於 `report.c`的第`215`行。
---
## 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
### 透過實驗(非理論)驗證時間複雜度
* **Timing leakage detection**
1. 測量執行時間: 針對兩個不同資料型態的輸入，重複測量加密函式的執行時間。通常利用CPU提供的 `cycle counter` 來實現。(例如 `x86` 系列的 `TSC register` 或 `ARM` 架構中的[systick](https://www.keil.com/pack/doc/CMSIS/Core/html/group__SysTick__gr.html) 外設 )
2. 套用 `post-processing` : 在進行系統分析之前，可以對每個單獨的測量套用一些 `post-preocessing` (包含 [cropping](https://en.wikipedia.org/wiki/Cropping_(image))) 或套用更高階的 `preprocessing` (例如 `centered product`)模仿高階 `DPA` 攻擊。
3. 套用統計測試: 採用統計測試來驗證兩個時間分布是否相等。使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 和 [Kolmogorov-Smirnov test](https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test)。
* 綜上所述，程式的` simulatioin` 是基於實際執行時間的測量和統計分析，以及使用統計測試來驗證兩個不同資料型態輸入的執行式間是否有顯著差異，因此 `simulatioin` 是通過實驗來驗證程式碼的時間複雜度，而不是依賴理論推導。
:::danger
現有程式碼和論文描述哪裡不同？
:::
---
### 研讀 Linux 核心原始程式碼 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
```c
// SPDX-License-Identifier: GPL-2.0
```
[GNU General Public License v2.0](https://www.gnu.org/licenses/old-licenses/gpl-2.0.html)
`GNU General Public License` 可以縮寫成 `GNU GPL` 或 `GPL`，這一行的意思是指其使用 `GPL` 的 `2.0` 版本，大多數軟體的許可證用意是剝奪使用者分享和修改的自由，相較之下， `GPL` 的用意是保證所有使用者分享和更改軟體的自由。
```c
__attribute__((nonnull(2,3,4)))
```
告知編譯器第二、三、四個傳遞的參數不可為 `NULL` ，可以幫助開發者避免由傳遞 `NULL` 指標引起的意外行為或崩潰，提高程式碼的可維護性和可靠性。
#### `merge`
根據註解:
```c
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
```
可以得知 `merge` 沒有維護到 `prev` 指標
```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;
}
```
可以發現傳遞的參數有一個自定義的函式 `list_cmp_func_t` ，可以在 `list_sort.h` 中找到。
```c
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
這裡定義了一個函式指標 `list_cmp_func_t` ，它會接收三個參數，它們的資料型態分別是 `void*` 和兩個 `const struct list_head*` ，最後會返回一個整數，而 `__attribute__((nonnull(2,3)))` 表示編譯器會檢查該函式指標的使用，確保第二個和第三個參數不為 `NULL`。
根據 `list_sort.c` 的註解:
```c
* The comparison function @cmp must return > 0 if @a should sort after
* @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
* sort before @b *or* their original order should be preserved. It is
* always called with the element that came first in the input in @a,
* and list_sort is a stable sort, so it is not necessary to distinguish
* the @a < @b and @a == @b cases.
```
可以得知:
1. 以升冪排列
2. 如果 `a > b` 那麼回傳 `> 0`
3. 如果 `a < b` 那麼回傳 `<= 0` (表示 `a` 應該在 `b` 之前或維持原本的排序)
4. `list_sort` 是一個穩定排序，因此不需要考慮 `a <= b` 的情況
所以當 `cmp` 回傳的值 `<= 0` 時，要將 `a` 放到已排序的鏈結串列的尾端，因為 `a` 要比 `b` 先被排序。
---
#### `merge_final`
根據註解:
```c
* Combine final list merge with restoration of standard doubly-linked
* list structure. This approach duplicates code from merge(), but
* runs faster than the tidier alternatives of either a separate final
* prev-link restoration pass, or maintaining the prev links
* throughout.
```
可以得知 `merge_final` 會將鏈結串列恢復成雙向的。
```c
__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
這裡的註解提到當 `merge` 非常不平衡時，舉例來說，儘管輸入都是已排序的節點，但是迴圈可能還是會跑很多次，這時可以定期調用 `cond_resched()` 解決此問題。
此處使用的函式 `unlikely()` 可以在 `/include/linux/compiler.h` 中找到。
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
[__builtin_expect()](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 是 `gcc` 內建函式，作用是將執行頻率高的分支標示為 `likely` ，執行頻率低的分枝則標示為 `unlikely` ，所以 `merge_final()` 中的 `unlikely` 是用來檢查是否已經對鏈結串列 `b` 中的節點進行多次迭代，如果是的話，則調用 `cmp` 函式來觸發回調。
使用 `!!(x)` 兩個 `!` 的原因是將表達是轉換成布林值的 `0` 或 `1` 。
#### `list_sort`
Sign in with Wallet
Connect another wallet