# 2024q1 Homework1 (lab0)
contributed by < `nelson0720j` >
:::danger
詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::
## 開發環境
```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 | less
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: 12th Gen Intel(R) Core(TM) i5-12500H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 3
BogoMIPS: 6220.79
```
## 指定的佇列操作
### `q_new`
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)；
:::
確保成功建立佇列並用 `INIT_LIST_HEAD` 初始化其中元素。
```c
struct list_head *head = malloc(sizeof(struct list_head));
if (!head) {
return NULL;
}
INIT_LIST_HEAD(head);
}
```
### `q_free`
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
藉由 `list_for_each_entry_safe` 逐一走訪鏈結串列的各元素，來釋放整個佇列。
```c
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
q_release_element(entry);
}
free(head);
}
```
### `q_insert_head`
由 `strdup` 來複製字串並得到新複製字串的指標，再透過 `list_add` 新增 `new` 中的鏈結串列。
```c
element_t *new = malloc(sizeof(element_t));
new->value = strdup(s);
if(!new) {
return false;
}
if (!new->value) {
free(new);
return false;
}
list_add(&new->list, head);
return true;
```
在 commit 時，被檢查工具告知 `new` 參數並未檢查她是否為 `NULL`，因此我將檢查 `new` 的順序移到給它 `value` 值之前。
```diff
-new->value = strdup(s);
if (!new) {
return false;
}
+new->value = strdup(s);
if (!new->value) {
free(new);
return false;
}
```
### `q_insert_tail`
用 `list_add_tail` 來插入到尾端。
```c!
element_t *new = malloc(sizeof(element_t));
if (!new) {
return false;
}
new->value = strdup(s)
if (!new->value) {
free(new);
return false;
}
list_add_tail(&new->list, head);
```
### `q_remove_head`
用 `list_first_entry` 來找到第一個節點，再用 `strncpy` 來將 value 成員的存取限制在函式內部，並提供一個安全的方式讓呼叫者獲取值。
另外，選取 `strncpy` 而非`strscpy`，原因擷取自[The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
> Preferred to strncpy() since it always returns a valid string, and doesn't unnecessarily force the tail of the destination buffer to be zero padded.
:::danger
改進你的漢語表達。
:::
```c
element_t *entry = list_first_entry(head, element_t, list);
if (sp && entry) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&entry->list);
```
### `q_remove_tail`
同 `remove_head` ，差別在使用 `list_last_entry` 來找最後一個要去除的節點。
### `q_size`
### `q_delete_mid`
原本看完 leetcode 後打算採用快慢指標，但想到此佇列是採用雙向鏈結串列，因此可以直接得知第一和最後一項的節點，同步往中間移動即可找到中間節點。
實作中也更清楚 `list_head` 和 `element_t` 分開結構的好處。
```c
struct list_head *first = head->next;
struct list_head *end = head->prev;
if (list_empty(head))
return false;
while (first != end && first->next != end) {
first = first->next;
end = end->prev;
}
element_t *entry = list_entry(first, element_t, list);
list_del(first);
q_release_element(entry);
```
### `q_delete_dup`
用 `list_for_each_entry_safe` 來遍歷佇列中的各節點來刪除重複的節點，但會發生 `Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted`。
於是透過`qtest` 來測試，發現是可以正確找出重複節點，但刪除前就發生錯誤，真正錯誤原因尚未找出，因此改用 `list_for_each_safe` 用鏈結串列搭配 `list_entry` 來找出節點位址，進而比較其 `value`。
```c
// list_for_each_entry_safe
element_t *entry, *safe;
bool dup = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
dup = true;
} else if (dup) {
dup = false;
list_del(&entry->list);
q_release_element(entry);
}
}
```
```c
// list_for_each_safe
struct list_head *cur, *next;
bool dup = false;
list_for_each_safe (cur, next, head) {
element_t *entry = list_entry(cur, element_t, list);
element_t *safe = list_entry(next, element_t, list);
if (cur->next != head && strcmp(entry->value, safe->value) == 0) {
printf("entry dup: %s\n", entry->value);
printf("safe dup: %s\n", safe->value);
list_del(cur);
q_release_element(entry);
dup = true;
} else if (dup) {
dup = false;
list_del(cur);
q_release_element(entry);
}
}
```
### `q_swap`
`
### `q_reverse`
:::danger
- [x] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
用 `list_move` 逐一走訪每個節點，將節點往前移到佇列開頭，來達成反轉佇列中節點的順序。
>list_move() - Move a list node to the beginning of the list
```c
struct list_head *cur, *next = NULL;
list_for_each_safe (cur, next, head) {
list_move_tail(cur, head);
}
```
### `q_ascend`
倒數第一個節點必為當下最小值，因此不用檢查，由佇列倒數第二個節點( `head->prev->prev` )開始，往左檢查，若遇到比目前最大值還小，則刪除。
用兩個指向 `element_t` 的指標分別指向當前節點與下一個要檢查的節點，再用 `strcmp` 來比較兩個節點的大小。
```c
struct list_head *cur = head->prev->prev;
while (cur != head) {
struct list_head *nex = cur->next;
element_t *min_entry = list_entry(cur, element_t, list);
element_t *nex_entry = list_entry(nex, element_t, list);
if (strcmp(min_entry->value, nex_entry->value) > 0) {
struct list_head *del = cur;
list_del(del);
cur = cur->prev;
q_release_element(list_entry(del, element_t, list));
} else
cur = cur->prev;
}
```
### `q_descend`
與`q_ascend` 不同之處在換紀錄最大值。
### `q_sort`
`q_delete_mid` 的方式找到中間值來分割，並用 `merge sort` 的方式來排序和合併。
採用遞迴方式實作，未來可根據[merge sort 與他的變化](https://hackmd.io/@lambert-wu/list-merge-sort#%E9%81%9E%E8%BF%B4%E7%89%88)改採迭代方式增進效率。
:::danger
你選定合併排序演算法，該如何確定現有的測試方法涵蓋合併排序的最差狀況呢？
:::
### `q_merge`
用 `queue_contex_t` 來管理多個佇列。
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
### 錯誤解決
```
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
ERROR: At least one node violated the ordering rule
ERROR: Removed value c != expected value d
ERROR: Removed value d != expected value c
ERROR: Removal from queue failed (1 failures total)
ERROR: Removal from queue failed (2 failures total)
Error limit exceeded. Stopping command execution
--- trace-06-ops 0/6
```
發現 descend 和 ascend 判斷大小弄相反，修正後。
```diff
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
- ERROR: At least one node violated the ordering rule
ERROR: Removed value c != expected value d
ERROR: Removed value a != expected value c
ERROR: Removed value a != expected value b
ERROR: Removal from queue failed (1 failures total)
```
descend 仍有錯誤，換成從後端往回檢查並用兩個節點指標獲取值來比大小後，剩下時間複雜度測試未通過。
```
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
研讀論文後加入 percentile 功能，成功解決。
```
--- TOTAL 100/100
```
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)；
:::
---
## valgrind
### 工具
* 分析記憶體使用狀況 [**Massif**](https://valgrind.org/docs/manual/ms-manual.html)
### 測試
`scripts/driver.py -p /tmp/qtest.UAgJqu --valgrind -t <tid>`
## 自動測試程式
### 追蹤記憶體配置和釋放的狀況
* harness.h 和 harness.c
建立一個新的結構體 `block_ele_t`，用來檢測記憶體是否正確釋放，並有 `find_header` 和 `find_footer` 達到類似 `container_of` 的功能。
`find_header` 可找到 `block_ele_t` 的 開頭位址，可用來找到要釋放記憶體的位址。
`find_footer` 可找到 `payload` 尾端 `magic number` 的位址，可用來檢測是否越界存取。
## `lib/list_sort.c`
### 專題解說
* natural runs : 未排序的序列中，已經排序好的子序列。
* timsort :
1. 分割: 從佇列中取出元素經 `insertion sort` 再丟到 stack 中
2. 合併: 形成新的 run 趁還在 cache 時就先進行合併，且 runs 長度不一。
3. 合併策略: 與長度較小的先合併。(因此後面提到要記錄 runs 的大小)
4. 比較次數: 排序好的子序列會直接加入同一個 run ，效率較佳。
5. cache miss : 採用類似 linux kernel 的 mergesort 方法，深度優先。
6. 測量執行時間: 參考< Dude, is my code constant time? >之measure execution time 方法。
7. timsort 優於 list_sort 且有顯著差異。
* in-place timsort (解決 kernel stack 相當有限問題)
待排序鏈結串列當成單向，第一個節點的 prev 來存 stack (存放所有的 runs ) ，第二個存 runs 大小。
### merge into lab0-c
觀察 ```void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)```
參考 [API](https://www.kernel.org/doc/html/next/core-api/kernel-api.html#c.list_sort)
>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.
有 `cmp` 這個需要自行定義的 function 。
從 linux kernel 引入 `lib/list_sort.c` 和 `lisrt_sort.h`
`list_sort.h` 中定義會用到的 macros
```clike
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
typedef unsigned char u8;
```
並在 `qtest` 中新增 command ， `do_lisort` 和定義一個新的函式 `cmp` 並使用 `strcmp` 來實作
```clike
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
### 分析
:::success
TODO:
:::
## 在 `qtest` 提供新的命令 `shuffle`
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實現
### 實現
考慮到 `queue.h` 改動會被 commit 拒絕的情況下，利用創建 `shuffle.h` 和 `shuffle.c` 來實現新命令。
根據 `console.h`中
```
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
在 `q_test.c` 中新增命令和 `do_shuffle()`，會根據使用者所輸入的 `shuffle` 命令來去執行對應的 `do_shuffle`， `do_shuffle` 會去檢查此執行是否合法，合法則執行 `shuffle.c` 中的 `q_shuffle` ，反之顯示錯誤訊息。
```clike
ADD_COMMAND(shuffle, "Shuffle the queue", "");
```
```clike
// do_shuffle()
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return error_check();
}
if (!current || !current->q) {
report(3, "Warning: Calling shuffle on null queue");
return error_check();
}
if (current->size < 2) {
report(3, "Warning: Calling shuffle on single node of queue");
return error_check();
}
if (exception_setup(true))
q_shuffle(current->q);
q_show(3);
return !error_check();
```
其中 `error_check()` 用來檢查程序或函數執行中是否出現了錯誤，可使代碼更易讀懂並提高擴展性。
### 分析洗牌亂度
:::success
TODO:
:::
## 研讀論文[〈 Dude, is my code constant time? 〉](chrome-extension://bocbaocobfecmglnmeaeppambideimao/pdf/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2016%2F1123.pdf)
### 摘要: 介紹 dedeuct
a tool to assess whetherapieceofcoderuns inconstant timeornotonagiven platform.
### 方法
run it with different inputs, measure execution time and apply statistics.
* steps:
1. Measure execution
2. Apply post-processing
a. Cropping
b. Higher-order preprocessing:
3. Apply statistical
a. t-test
也稱 Student's t-distribution: 根據小樣本來估計母體呈常態分布
b. Non-parametric tests
採取像是[Kolmogorov-Smirnov](https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test)
## percentile 的處理問題
根據論文
>Pre-processing:Wepre-processmeasurementspriorto statisticalprocessing.Wediscardmeasurements thatarelarger thantheppercentile, forvarious2valuesofp.Therationale here is to test a restricteddistributionrange, especially the lowercyclecount tail.Theupper tailmaybemoreinfluenced bydata-independentnoise.This(heuristic)processgivesgood empirical results(makesdetectionfaster);neverthelesswealso processmeasurementswithoutpre-processing.
和 [`deduct.h`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的註解
> set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that
得知 percentile 去除大於某個百分位數的測量值為 "統計處理之前對測量進行預處理的步驟"，來去除極端值。
lab0-c 中沒有加入 percentile 的功能，因此會把一些時間結果異常的極端值也納入統計，因此這裡我們根據 `deduct.h` 對 lab0-c 中的 `fixture.c` 加入 percnetile 功能。
## ttt
### merge ttt into lab0-c
將 `ttt` 當中需要的檔案移入，並修正會引用到 `hlist.h` 的檔案，使其引用到正確的開頭檔。
修改 `game.c` 中的參數加上 `const`，保證被指向的字串不會在函式內部被修改。
```
int *available_moves(const char *table)
```
commit 時會出問題
```
zobrist.c:63:21: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
^
nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingInclude]
```
在 [`pre-commit.hook`](https://pre-commit.com/) 中加入
```
--suppress=nullPointer:zobrist.c"
```
來移除對 `zobrist.c` 檢查
成功執行 ttt 遊戲!
Sign in with Wallet
Connect another wallet