# 2024q1 Homework1 (lab0)
contributed by < `Vincent550102` >
### Reviewed by `weihsinyeh`
1. Fix some implement mistake [commit 66d7745](https://github.com/sysprog21/lab0-c/commit/66d774537544ab71133c3686650ffbf5eeafe6e7) 可以將具體修正寫在在 commit 的描述中。
2. [commit cdb194b](https://github.com/Vincent550102/lab0-c/commit/cdb194b7b68861e3f43ad067bfd607f3d1f12e97) 沒有寫修改的原因。
3. [commit 9126285](https://github.com/Vincent550102/lab0-c/commit/912628531dea01d3938a9001a56c871a0ae5066f) 這裡參閱規格書中 free 的說明。
4. 有一些中文字打錯字。
### Reviewed by `w96086123`
1. 在 q_free 中的實作註記的第一段有一個無意義的空格。
2. [commit e2df64f](https://github.com/sysprog21/lab0-c/commit/e2df64fb3feae5e4ba31f96efcc573eb8c715507) 只有寫可以解決什麼問題，但沒有提出本來的問題是由哪裡出現。另外，在 `queue.h` 中有提供 `q_release_element` 可以解決相同的問題。
3. 在 commit 中，有使用 Fix 可以在說明中寫修改原因。
## 開發環境
```shell
$ gcc --version
gcc (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 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
Byte Order: Little Endian
Address sizes: 46 bits physical, 57 bits virtual
CPU(s): 32
On-line CPU(s) list: 0-31
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 4
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 106
Model name: Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz
Stepping: 6
CPU MHz: 2899.998
BogoMIPS: 5799.99
Virtualization: VT-x
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 1 MiB
L1i cache: 1 MiB
L2 cache: 128 MiB
L3 cache: 64 MiB
```
### 事前準備
#### list_entry / container_of
透過研讀老師的 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/linux-macro-containerof)，<s>個人總結</s> 出以下結論:
- 該巨集利用一種巧妙的技巧，通過一個被繼承結構中的成員變量，反向追蹤以獲取繼承它的結構體，展現了一種反向繼承鏈的實踐方法。
- 它的存在旨在透過模仿一些高級語言所具備的特性（如繼承）來實現特定的功能，展現了一種模擬高級語言特性的技術。
- 此技術使得繼承關係更加松散，減少了耦合度，無需額外定義反向繼承機制，從而提升了程式碼的靈活性和可維護性。
:::warning
列出關於「反向繼承機制」的權威材料 (如語言規格書和技術報告)，並充分討論 Linux 核心風格的鏈結串列與其到底有什麼關聯。
:::
另外，我想到一件很有趣的事情，若 `container_of` 能回傳一個物件的上一層繼承的物件，那如果這個物件上一層繼承的物件尚未初始化，那這時候再對其 `container_of` 會發生什麼事？
以下程式碼，我們對一個物件初始化 `list_head`，並且取得上一層繼承的物件 `element_t` 的成員 `value`。
```c
struct list_head *li = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(li);
element_t *e = list_entry(li, element_t, list);
e->value = strdup("test");
printf("%s\n", e->value);
```
發現輸出是 `test`，且無錯誤產生，進一步驗證可用 gdb 觀察 stack frame
## 指定的佇列操作
### q_new
> commit [f6ee1dc](https://github.com/Vincent550102/lab0-c/commit/f6ee1dce0f82423347f1e59724c5a629d6df7b90)
回傳一個空的 `list_head`。確認 `malloc` 成功後，我們可以透過 `INIT_LIST_HEAD` 這個巨集來初始化這個 `list_head`。
### q_free
> commit [e2df64f](https://github.com/Vincent550102/lab0-c/commit/e2df64fb3feae5e4ba31f96efcc573eb8c715507)
接下來使用 `list_for_each_entry_safe` 進行走訪，對每個走訪到的節點都先透過 `list_del` 將這個節點從鏈結串列中移開，之後再釋放該元素，走訪完畢後再釋放 `head`。
實作註記:
透過 實作 `e_free` 等函式，讓 `element_t` 的物件能夠完整釋放，當初忘記釋放 `e->value` 而直接釋放 `e` 導致釋放不完全。
### q_insert_* / q_remove_*
> commit [e171a43](https://github.com/Vincent550102/lab0-c/commit/e171a43d2dc99e10abad9ce62c50d65165cded0e)
實作上類似的函式，須注意使用 `strncpy` 使該 buf 能控制寫入長度，否則會導致[緩衝區溢位](https://www.cloudflare.com/zh-tw/learning/security/threats/buffer-overflow/) 等資安問題。
並且要在 `sp[bufsize - 1] = '\0';`，避免造成記憶體位置洩漏。
### q_delete_mid
透過快慢指標的技巧以及 `list_for_each` 巨集完成在環狀雙向的鏈結串列上找中點並刪除。
commit [9126285](https://github.com/Vincent550102/lab0-c/commit/912628531dea01d3938a9001a56c871a0ae5066f)
發現原本的實作多加到一處 `fast = fast->next` 造成每次迴圈會使得快指標多跑一次（共三次），將其刪除即可修正。 commit [f3dddbe](https://github.com/Vincent550102/lab0-c/commit/f3dddbeceec711ba82a9397b75e376650c1eab0c)
```diff
struct list_head *slow = head, *fast;
list_for_each (fast, head) {
- fast = fast->next;
if (fast != head && fast->next != head)
fast = fast->next;
else
break;
slow = slow->next;
}
```
### q_swap
> commit [d188f4b](https://github.com/Vincent550102/lab0-c/commit/d188f4b0a679d4ab3d022548875188f115bc8112)
透過 `list_for_each` 走訪每個元素，並且嘗試取得下個元素，若有，則將兩者交換。
### q_reverse
透過 `list_for_each_safe` 走訪每個元素，並且每次都將該元素放到 head，達到反轉的效果。
commit [930e774](https://github.com/Vincent550102/lab0-c/commit/930e774a9dfe8a54af071f0baa0b08f34b73a8ec)
### q_reverseK
參考了 WangHanChi 同學的 [實作](https://hackmd.io/tqrBvKRgTTm-LZzlde0V5A?both#q_reverseK)，過程中透過 `list_for_each_safe` 走訪各個元素，並且每第 k 個元素都做以下事情:
- 使用 `list_cut_position` 將 i ~ i+k-1 的元素剪下，並放到 `tmp_head`
- 透過 `q_reverse` 將 `tmp_head` 反轉
- 使用 `list_splice_init` 將 `tmp_head` 的內容串回原鏈結串列，並重制 `tmp_head`
commit [2c415ed](https://github.com/Vincent550102/lab0-c/commit/2c415ed5449961c0f3f80450af58371d7f4548f7)
### q_delete_dup
觀察性質可以知道，由於此鏈結串列是排序好的，因此同樣的元素會<s>兩兩相臨</s> 兩兩相鄰。
透過 `list_for_each_entry_safe` 走訪各個元素，維護一個 flag，每個元素和下個元素數值相同，則將目前這個元素刪除，並將 flag 啟用，以便下次迴圈也將該元素移除，若不同則將 flag 重<s>制</s>置。
commit [eb67d38](https://github.com/Vincent550102/lab0-c/commit/eb67d389e958b006b76b5d55ac54d72a9a4ad63e)
### q_sort
> commit [ab859cf](https://github.com/Vincent550102/lab0-c/commit/ab859cf8fbd452f83d5e09c73ff4518c89edac5b)
首先，先將此環狀鏈結串列的 `head->prev->next` 設為 NULL，使得退化為單向的鏈結串列。
我們透過快慢指標的技巧找到該鏈結串列的中點，再用分治技巧中的分（Divide）將鏈結串列分為多個小點，接下來，治（conquer）的過程中我們用間接指標的技巧輔助，將兩個已排序的鏈結串列合併為一個已排序的鏈結串列，最後我們便可以得到一個排序好的鏈結串列，最後再將回邊接回來即可。
在檢查過程中，由於測試資料是 1~12，但這個作業是以字串形式處理，所以 `strcmp` 的時候會以字典序排列，導致以下的狀況誤判實作沒做好，造成多餘的排錯時間浪費。
```
l = []
l = [3]
l = [3 1]
l = [3 1 5]
l = [3 1 5 10]
l = [3 1 5 10 11]
l = [3 1 5 10 11 12]
l = [3 1 5 10 11 12 9]
l = [1 10 11 12 3 5 9]
Freeing queue
```
參考了 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTH) 中的實作。
### q_merge
使用很直覺的做法，透過 `list_for_each_safe` 走訪每個元素，並將該元素使用 `list_splice_init` 串到第一個元素並重製，結束走訪後，使用 `q_sort` 將其排序。
TODO: 可透過 mergesort 的技巧直接對 `head` 做事，由於符合對應的性質。
commit [2279bd2](https://github.com/Vincent550102/lab0-c/commit/2279bd27475e1d76031cb5a28f385be8de4978b5)
### q_descend / q_ascend
這題是個經典的單調序列問題，我們的最終目標為找到給定序列中的單調遞增/遞減序列，因此需要維護一個目前最大值 `max_val`，用 `list_for_each_safe` 走訪每個元素，當目前的元素比 `max_val` 大就更新它，否則就將這個元素移除。
遞增或遞減兩者作法雷同，遞減只要先將原序列反轉，處理完後再將結果反轉即為答案。
commit [3d14944](https://github.com/Vincent550102/lab0-c/commit/3d14944b10404846353dc850d3b33f19cbc98fd6)
---
## 研讀論文〈Dude, is my code constant time?〉
這篇論文介紹了一種名為 [dudect](https://github.com/oreparaz/dudect) 的工具，該工具用於評估特定平台上的代碼是否以恆定時間執行，這對於避免時間攻擊（[Timing Attack](https://en.wikipedia.org/wiki/Timing_attack)）相當重要。
與需要對硬<s>件</s>體行為進行建模的先前方法不同，dudect 通過不假設這些前提，使用執行時間的統計分析，使其適合於黑盒測試。
:::info
時間攻擊（[Timing Attack](https://en.wikipedia.org/wiki/Timing_attack)）
是一種旁路攻擊（Side-channel attack），透過電腦系統的**實作**缺陷而洩漏的資訊來做的攻擊，而不是利用演算法本身的弱點
:::
此論文首先先進行了時間攻擊的檢測，他們使用了 **fix-vs-random tests**，也就是準備兩筆測資，其中一筆是固定的常數，另一個則為隨機的選定。他們進行了 **null hypothesis** the two timing distributions are equal。
### 改進 qtest 中的常數複雜度判斷
可以發現，當我們在測試資料中使用 `option simulation 1` 時，將會進行 q_insert_head / q_insert_tail / q_remove_head / q_remove_tail 的常數時間複雜度檢查。
對應的程式碼如下:
constant.h
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
#define DUT(x) DUT_##x
enum {
#define _(x) DUT(x),
DUT_FUNCS
#undef _
};
```
fixture.c
```c
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
```c
static bool test_const(char *text, int mode)
{
bool result = false;
t = malloc(sizeof(t_context_t));
for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
init_once();
for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
++i)
result = doit(mode);
printf("\033[A\033[2K\033[A\033[2K");
if (result)
break;
}
free(t);
return result;
}
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _
```
同時，發現到論文中有提及會將測量後的第一批結果丟棄，也閱讀了 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的原始碼後，他會將迴圈從 10 開始:
fixture.c
```c
static void update_statistics(dudect_ctx_t *ctx) {
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
int64_t difference = ctx->exec_times[i];
if (difference < 0) {
continue; // the cpu cycle counter overflowed, just throw away the measurement
}
```
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試改進
首先，在檔案中時常出現形如 `__attribute__((nonnull(2,3)))` 的語法，該語法有出現在 gcc 的手冊中，被稱為 [Function-Attributes](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html)，大意就是標示這個函式的第 2, 3 個參數不能是 null。
在此檔案中實作了三個函式，分別為 `list_sort` `merge` `merge_final`，將特點註記：
### `list_sort`
- 整體是透過 bottom up 的方式來達成，充分發揮 cache 機制。
- 透過 `head->prev->next = NULL;` 將此環狀鏈結串列變單向的。
- 透過 `count` 變數來控制合併。
- 控制合併的數量來確保可以放的進 L1 cache。
### `merge`
- 重複的程式碼，參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 中的 案例探討: LeetCode 21. Merge Two Sorted Lists，可進行以下程式碼縮減。
```diff
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node;
- for (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* 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;
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
}
+ *tail = (struct list_head *)((uintptr_t)a | (uinptr_t)b);
return head;
}
```
### `merge_final`
- 進行最後一次合併，並將各個斷鍊結點接回來。
Sign in with Wallet
Connect another wallet