# 2024q1 Homework1 (lab0)
contributed by < `rain20010126` >
:::danger
詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
> 了解，感謝老師指正！
:::
### Reviewed by `Shawn531`
* 實作前先釐清每個函式的用處與形式，譬如在`queue.h`有說明每個函式要達成甚麼目的，這樣可以加速開發。
* 可以多表達自己的第一手想法。
* 善用`diff`表達程式碼的差異。
### Reviewed by `ShawnXuanc`
在提交 `commit` 時可以增加對功能的說明
可以將相同的程式碼再利用，像是 `q_insert`, `q_remove` 中有需多重複的程式碼
可以使用美式英文當作程式碼的註解
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.2.0-4ubuntu3) 13.2.0
$ lscpu
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: Apple
Model name: Blizzard-M2
Model: 0
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 0x1
Frequency boost: enabled
CPU(s) scaling MHz: 38%
CPU max MHz: 2424.0000
CPU min MHz: 600.0000
BogoMIPS: 48.00
```
:::warning
注意標示的方法。
:::
### GCC 編譯器
```
$ gcc -o stack -g -no-pie stack.c
```
`-o` : 指定特定輸出的檔案名稱
`-g` : 可以配合 `gdb` 做除錯如`$ gdb -q stack`，其中`-q` 的目的為讓他安靜一點
`-no-pie`: 抑制 PIE，簡單來說就是將原本執行檔是把一段位置寫進去(直接的地址)，使用 PIE 的話就是改成相對位置，來避免針對內存位置的攻擊，所以使用 PIE 後需要對執行檔做追蹤的話會比較麻煩
==我在調整風格時遇到以下問題==，有嘗試做 `sudo apt upgrade gdb` 仍然無法解決此問題
```
(gdb) set disassembly-flavor intel
No symbol "disassembly" in current context.
```
==另外的問題是我在使用 `disas main` 的輸出的結果如下==， 不知道要怎麼和老師在 [你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function) 中的 `rbp` 和 `rsp` 做對應
```c
(gdb) disas main
Dump of assembler code for function main:
0x0000000000400638 <+0>: stp x29, x30, [sp, #-32]!
0x000000000040063c <+4>: mov x29, sp
0x0000000000400640 <+8>: mov w0, #0x1 // #1
0x0000000000400644 <+12>: bl 0x40061c <funcA>
0x0000000000400648 <+16>: str w0, [sp, #28]
0x000000000040064c <+20>: mov w0, #0x0 // #0
0x0000000000400650 <+24>: ldp x29, x30, [sp], #32
0x0000000000400654 <+28>: ret
End of assembler dump.
```
### 你所不知道的 C 語言 : 函示呼叫篇
#### malloc & calloc 比較:
`malloc` 盡可能用已經用過並且釋放掉的記憶體空間； `calloc` 則是配置記憶體空間並將內容**歸零**（通常會使用沒有被使用過的記憶體空間或是 `calloc` 過後但沒有做進一步修改的記憶體空間），如果要配置歸零後的記憶體空間使用 `malloc` ，相比於使用 `malloc + memset` 的速度來的快，如果沒有歸零的需求，先使用 `malloc` ，因為 `malloc` 的記憶體配置成功率較高
#### Parameter & Argument :
`Parameter` 為形式， `Argument` 為實際值
#### stack :
概念為後入先出，使用區域變數會配置在 `stack` 中。
`stack frame` 為一層的區域
- rsp(stack pointer) : 指向 stack 頂端
- rbp(base pointer) : 指向 stack 底部
#### heap(heap allocator) :
概念為**分堆**，會分成不同大小，例如由小到大為 `first bit` `small bit` `big bit` 等等，會有不同的配置策略。
使用 `malloc`, `free` 等配置記憶體或是釋放記憶體都有關係，以下為 `heap` 和 `stack` 的範例
```c
long *arr = malloc((n + 1) * sizeof(*arr)); // heap
long arr[n+1]; // stack
```
### 你所不知道的 C 語言：遞迴呼叫篇
#### 遞迴 VS 迭代
遞迴使用 function，在 function 中呼叫相同的一個 function (直接遞迴)，或是 `function A` 會呼叫 `function B` ，而 `function B` 會呼叫 `function A` (間接遞迴)
遞迴與非遞迴比較
- 遞迴優點 : 較精簡且易理解、變數較少、函式記憶體空間較省
- 非遞迴優點 : 通常效率較高、不須額外 stack 空間
`&&` (Logical AND) operator 與 `||` (Logical OR) operator
## 針對佇列操作的程式碼實作
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
在安裝完 Ubuntu Linux，熟悉鏈結串列和 git 的操作後我開始嘗試寫作業，順序即是每個函式的順序，因為一開始不知道怎麼下手，就先參考其他同學的格式並思考如何下手，首先看到 [Jackiempty](https://hackmd.io/@Jackiempty/HJv_2m7np) `q_new` 的部份後，發現我也不知道有 `INIT_LIST_HEAD(list_head)` 的函式存在，以及同學其他呼叫的函式都不太熟悉，在了解我到不是很熟悉下列網站後 (https://github.com/torvalds/linux/blob/master/include/linux/list.h#L35) ，所以我寫作業的方法主要是先參考同學的寫法，了解大概有什麼函式是需要用的，理解完需要用到的函式後，再自己下手。
:::danger
1. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
2. 改進你的漢語描述。
:::
### `q_new`
- 在了解到是要建立一個空佇列後，考慮到可能會有記憶體空間配置失敗的問題，因此簡單加上條件判斷是否有成功配置記憶體空間並搭配 `INIT_LIST_HEAD` 即順利完成此函式的建立。
### `q_free`
:::danger
你不該花太多時間在「查找資料」，閱讀、思考，然後闡述自己的洞見，才是課程在意的議題。
> 好的，謝謝老師。
:::
在理解 ` list_for_each_entry_safe` 時遇到了不小的困難，後來在<s>查找資料</s> 時，發現我的理解大有問題，首先 `#define` 的意思是一個巨集指令，和一般定義一個函式的方式有些不同，我原先以為他的意思和定義函數是一樣的意思，再來參照 [aa860630](https://hackmd.io/@qOvjgDvTQrGZGAlv5oHqsA/linux2024-homework1) 及 [nelson0720j](https://hackmd.io/@woLves-1822/linux2024-homework1)，將巨集的輸入設定成 `entry` 和 `safe` 後，了解到此巨集主要的作用是在刪除當前節點時，能同時知道下一個節點的位置，有這樣的理解後，完成了 `q_free` 的建立。
### `q_insert_head`
:::danger
本該如此，有何好說？
自己嘗試！
:::
<s>這次我是自己從頭嘗試看看</s>，但配置新的節點後，我遇到了一個問題是該怎麼知道配置 `node->value` 的記憶體空間，於是我詢問 chatgpt 來嘗試自己解決問題 ，結果他給我一段範例程式碼，所以在我閱讀後，了解到可以使用 `strlen` 來知道字串的長度，同時加 1 是為了<s>存儲字符串結束符</s> （\0），以及需要考慮到記憶體配置失敗的問題，下一個問題是我要怎麼把輸入的字串複製過去 ，之後在閱讀 [nelson0720j](https://hackmd.io/@woLves-1822/linux2024-homework1) 的說明後了解到可以使用 `strncpy` ，於是以下是我的初步程式碼。
:::danger
注意詞彙：
* string 是字串
* character 是字元
* store 是儲存
:::
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
// 獲得字串字數並使用strncpy將字串複製過去配置好的記憶體空間
node -> value = malloc(strlen(s) + 1);
strncpy(node->value, s, strlen(s) + 1);
if (!node -> value)
return false;
list_add(&node->list, head);
return true;
}
```
接著我使用 `make test` 進行測試後發現函式有誤，同時有內存洩漏的問題，於是我參考了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的作法，檢查我出錯的地方，發現我少考慮到了單個字體的大小，以及在 `return false` 前應該要把配置失敗的記憶體釋放掉，接著就成功了~~~
### `q_insert_tail`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
有了 `q_insert_head` 的經驗，於是我就將 `q_insert_head` 的最後一行程式碼從 `list_add(&node->list, head);` 修改成 `list_add_tail(&node->list, head);` 。
另外有看到 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的作法，覺得他的作法聰明許多，他是直接利用先前寫的 `q_insert_head` 來完成函式，即將函式輸入部份從原先的 `*head` 改成 `head->prev` 就完成了，這種作法就可以省去重複的程式碼。
### `q_remove_head`
在一開始，我初步對這個函式的理解是'移除' `head` 中和 `*sp` 指標指向相同的元素開始後的 `bufsize` 個元素，因為不確定我的想法是否正確，所以我查看了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的程式碼，發現我的想法大錯特錯，了解到 `bufsize` 是用來存取 `head->value` 的大小的，同時 `sp` 是用來儲存 `head->value` 的原先值的，並搭配 `list_del_init` 斷開head的連結，因此在有這些了解後完成了程式碼。
我比較疑惑的部份是為什麼 `remove` 需要刪除節點內的 `value`
另外一開始在撰寫程式時沒注意到 queue empty 的情況
### `q_remove_tail`
因為有先前 `q_insert_head` 和 `q_insert_tail` 的經驗，所以也嘗試看能不能用 `q_remove_head` 的方式撰寫本函式，但是失敗了，於是我參考了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的程式碼，發現是要使用 `head->prev->prev`
但依然遇到了以下問題
```
ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
```
:::danger
不理解就說不理解，不要裝可憐。理工人員說要精準。
:::
已解決，將 `list_del_init` 修改成 `list_del` ，但是<s>有點不太了解其中原因</s>，有查看 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) 的說明，但不懂兩者的差別為何會造成一個編譯成功一個編譯失敗的問題
```c
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
```
:::danger
1. 減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫
2. 注意程式碼的標示和張貼方式，避免非必要的縮排
:::
### `q_size`
參考自 [牛刀小試](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a) ，透過 `list_for_each` 走訪每個節點，同時經過一個節點時 `len` 加一
### `q_delete_mid`
在閱讀完[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)後，我有一個初步的了解是可以使用快慢指標來找到中間的節點，以下是我第一次完成的程式碼
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast = head, *slow = head;
while (fast!=tail && fast->next!=tail) {
fast = fast->next->next;
slow = slow->next;
}
slow = slow-> next; // 這裡有誤
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
但是遇到了以下問題
```
ERROR: Attempted to free unallocated block. Address = 0xdeadbeef Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
後來在參考 [nosba0957](https://hackmd.io/@chucknos/linux2024-homework1) ，發現迴圈結束後不需要再做一次 `slow = slow-> next;` ，但修改後仍然出現同的問題，最後在解決前面 `q_remove_tail` 的問題後就沒有出現上述問題了
另外在 `git commit` 時收到了將 `tail` 設定成常數的建議
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### q_delete_dup
了解函式的目標是在已經排序的狀況，移走佇列中具備重複內容的節點，我初步的想法是重複的元素會相鄰，我就從頭一個一個檢查看節點的內容，ㄖ，並了解可以使用 `strcmp` ，若是兩者字串相等的話會回傳0，並不使用 `node = node->next` 以便再重新檢查和下一個元素是否也出現重複得情況，若兩字串不相等，則使用 `node = node->next` ，對下一個節點進行檢查，以下是我初步的程式碼
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *current, *next;
struct list_head *node = head->next, *delete;
while(node!=head){
current = container_of(node, element_t, list);
next = container_of(node->next, element_t, list);
if (!strcmp(current->value, next->value)){
delete = node->next;
list_del(delete);
q_release_element(container_of(delete, element_t, list));
}
else
node = node->next;
}
return true;
}
```
接著我在使用 `git commit` 後收到了針對 current 變數的警告，要在使用這個變數的區域內聲明它，以減少其作用範圍，增加程式碼的可讀性和維護性。
另外在 `q_test` 出現了以下問題
```
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted
```
接著我查看了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 後發現我沒有正確理解題目的意思，重複的每個節點都需要刪除，所以我新增了以下程式碼如下，同時使用 `remove_cur`判斷是否有刪除節點 ，但是在 `q_test` 依然出現了相同的問題。
```c
element_t *del = NULL;
if (remove_cur){
del = node->prev;
list_del_init(del); //這邊有誤
q_release_element(del);
}
```
因為找不到問題所在，同時我發現我先前的程式碼沒有考慮到有重複多次的情形，所以我將迴圈改成 `while` 的寫法，以下是我的最終版本，我參考了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的作法，改進了我先前沒有繼續檢查的問題。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
struct list_head *current = head->next, *next = current->next;
bool remove_cur;
while (current != head && current->next != head) {
next = current->next;
remove_cur = false;
element_t *entry;
// 此處條件有誤
while (!strcmp(list_entry(next, element_t, list)->value,
list_entry(current, element_t, list)->value)){
remove_cur = true;
list_del(next);
entry = container_of(next, element_t, list);
q_release_element(entry);
next = current->next;
}
current = current->next;
if (remove_cur){
struct list_head *del = current->prev;
list_del(del);
entry = container_of(del, element_t, list);
q_release_element(entry);
}
}
return true;
}
```
再來我在執行 `qtest` 再有多目標需要刪除時會出現以下問題，經過了解後，我發現需要在以上 while 迴圈有誤處考慮 `next` 為 null 的情況，因次在條件部份補上 `&& next` 即完成程式碼
```
l = [jiji kiki lili mimi mimi bibi bibi]
cmd> dedup
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted
```
:::danger
避免非必要的項目縮排 (即 `* `)，以清晰、明確，且流暢的漢語書寫。
:::
### `q_swap`
一開始我沒有很理解題目的意思，但在查看完 [nosba0957](https://hackmd.io/@chucknos/linux2024-homework1#q_delete_mid) 的文字說明後，就了解題目是兩兩節點進行交換，交換完後再到下兩個節點進行交換，並參考該同學的程式碼，使用 `list_move` 對節點進行移除再插入。
### `q_reverse`
我的初步想法是把 `head->next` 也就是 `first` 插入到 `tail` 後，再重新設定 `first`，以下是我初步的程式碼。
```c
void q_reverse(struct list_head *head) {
struct list_head *first = head->next;
struct list_head *tail = head->prev;
while(first!=head){
list_move(first, tail);
first = head->next;
}
}
```
但出現以下錯誤
```
l = [yiyi iyiy gigi igig]
cmd> reverse
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
```
後來發現我條件部份沒設定好，會出現無窮迴圈的情況，將條件重新設定成 `while(tail->prev!=head)` 即完成函式的建立。
### `q_reverseK`
我的想法是把tail設定到需要反轉部份的尾端，然後再用先前 `q_reverse` 的方法完成，以下為我的程式碼。
```c
void q_reverseK(struct list_head *head, int k)
{
struct list_head *first = head->next, *tail = head;
for (int i = 0; i < k; i++) {
tail = tail->next; // 找到需要反轉區間的尾端
}
while (tail->prev != head) {
list_move(first, tail);
first = head->next;
}
}
```
後來同學在查看我的程式碼後指出我理解錯題目的要求了，題目要求是將 k 個為一組的元素進行反轉，所以我使用了 `size` 來判別剩下的元素還有沒有 k 個，沒有的話即跳出迴圈，接著利用前面 `reverse` 的方法，不斷更新 `head` 和 `tail` ，並利用 `this_term_head` 來存取此次循環的 `head` 作為 while 迴圈判斷使用。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
int size = q_size(head);
struct list_head *tail = head;
struct list_head *this_term_head = head;
struct list_head *next_term_head = head;
while (size >= k) {
size = size - k;
for (int i = 0; i < k&& tail->next; i++) {
tail = tail->next;
}
struct list_head *first = this_term_head->next;
next_term_head = first;
while (tail->prev != this_term_head) {
list_move(first, tail);
first = this_term_head->next;
}
tail = next_term_head;
this_term_head = next_term_head;
}
}
```
### `q_sort`
在觀看 [ Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) ，並了解不同作法的原理後，我選擇以時間複雜度較低的方法： `Merge Sort` ，也就是先找到佇列的中點，慢慢拆分到每個佇列只包含一個元素，再兩兩合併成完整的一個佇列，於是我開始實做。
在實做過程中，首先我遇到的困難是我該如何儲存每個斷開節點的位置，於是我查看了 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-lab0) 的程式碼和說明
但實做的第一次結果遇到了以下問題，所以我慢慢針對不同的函式下去做修正
```
l = [yiyi hihi jiji kiki ioio]
cmd> sort
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
```
以下為我 `merge_two_nodes`的程式碼
```c
struct list_head *merge_two_nodes(struct list_head *L, struct list_head *R)
{
if (!L && !R) {
return NULL;
}
struct list_head *head = NULL;
while(L && R){
if (strcmp(list_entry(L, element_t, list)->value,
list_entry(R, element_t, list)->value) <= 0){
head = L;
head = head->next;
L = L->next;
}
else{
head = R;
head = head->next;
R = R->next;
}
}
if (L){
head->next = L;
}
if{
head->next = R;
}
return head;
}
```
:::danger
什麼是「虛擬」的節點？
:::
後來發現我回傳的數值有問題，需要再額外存取 `head` 的位置再做回傳，後來我了解到可以使用<s>虛擬節點</s> ??? （改正：可以使用額外的一個 h 來初始化 head，這樣可以讓 head 在迴圈外部始終指向正確的位置，也不用特別處理第一個元素） 方式更好的解決此問題，也就是以下
```c
struct list_head *merge_two_nodes(struct list_head *L, struct list_head *R)
{
if (!L && !R) {
return NULL;
}
struct list_head h;
struct list_head *head = &h;
while (L && R) {
if (strcmp(list_entry(L, element_t, list)->value,
list_entry(R, element_t, list)->value) <= 0) {
head->next = L;
L = L->next;
}
else {
head->next = R;
R = R->next;
}
head = head->next;
}
// Link the remaining elements to the head
if (L) {
head->next = L;
}
if (R) {
head->next = R;
}
return h.next;
}
```
:::danger
程式碼的註解都該用美式英語書寫，不要出現漢字。
你如何確保測試的過程已涵蓋排序演算法的最差狀況？
:::
### `q_descend`
了解到題目是要移除當該節點右側有大於該節點的節點，則刪除該節點，初步想法就是按照順序一個一個檢查，但想一想覺得這個方法會重複確認很多次，於是我就參考了 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1) 的說明，了解到可以從尾端往前檢查，看有沒有比自己小的節點做刪除。
:::danger
清楚標註你參照的 GitHub 帳號名稱
:::
另外看到函式需要回傳一個數值，查看<s>同學</s> [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1)的程式碼了解是要回傳佇列的節點數量，於是完成我以下的程式碼
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
struct list_head *ptr = head->prev;
while (ptr != head && ptr->prev != head) {
int compare = strcmp(list_entry(ptr, element_t, list)->value,
list_entry(ptr->prev, element_t, list)->value);
if (compare >= 0) {
element_t *entry = container_of(ptr->prev, element_t, list);
list_del(ptr->prev);
q_release_element(entry);
}
else
ptr = ptr->prev;
}
return q_size(head);
}
```
### `q_merge`
我採用了比較直觀的做法，同樣先把環形串列修改成非環形的，並將第一個串列使用 `merge_two_nodes` 不斷與後續的進行連接，最後與 `q_sort` 使用相同的作法將串列修改回雙向環狀的
## Valgrind + 自動測試程式
目前使用 `make valgrind` 在程式碼中沒有找出記憶體的相關問題，但使用 `make test` 時無法通過第17項的測試
## 實作 shuffle
### Fisher–Yates shuffle
此方法是透過一個迴圈去迭代，從最後一個元素開始，與前面的隨機一個元素進行交換，此作法的好處是，可以確保交換過得位置不會再被交換，且時間複雜度為 *O(n)* ，機率分佈也是均勻的
新增的方法參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023) ，目前 `qtest` 中的 `do_shuffle` 沒有檢查可能的錯誤
在實作 `q_shuffle` 時，遇到了以下問題
```
l = [1 2 3 4]
cmd> shuffle
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
```
在檢查完程式碼後，發現第 16 行部份有誤，在與前面交換後，原本 `temp` 所在的位置變為 `pick` 所在，因此往前更新應該修改為 `temp = pick->prev`
```clike=
void q_shuffle(struct list_head *head){
if (!head)
return;
int size = q_size(head);
struct list_head *temp = head->prev;
while(size>=1){
int index = rand() % size;
struct list_head *pick = temp;
for(;index>0;index--){
pick = pick->prev;
}
swap(temp,pick);
temp = temp->prev; // error here
size--;
}
}
```
但在進行腳本測試時的結果如下
```
Expectation: 41666
Observation: {'1234': 0, '1243': 0, '1324': 0, '1342': 0, '1423': 0, '1432': 0, '2134': 0, '2143': 0, '2314': 0, '2341': 0, '2413': 0, '2431': 0, '3124': 0, '3142': 0, '3214': 0, '3241': 0, '3412': 0, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0}
chi square sum: 999984.0
```
於是重新利用 `qtest` 進行檢查，發現在執行第二次 shuffle 時會出現以下問題
```
l = [1 2 3 4]
cmd> shuffle
l = [3 1 4 2]
cmd> shuffle
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
```
接著我比較了自己的程式碼與 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023) 的差別，發現我的 `swap` 函式需要考慮當交換元素是相鄰的情況，只需做一次 `list_del` 與 `list_add` 即可，最後我的 `q_shuffle` 的結果如下
```
Expectation: 41666
Observation:
{'1234': 41472, '1243': 41759, '1324': 41898, '1342': 41787,
'1423': 41762, '1432': 41896, '2134': 41434, '2143': 41604,
'2314': 41916, '2341': 41627, '2413': 41577, '2431': 41962,
'3124': 41547, '3142': 41829, '3214': 41259, '3241': 41485,
'3412': 41506, '3421': 41420, '4123': 41392, '4132': 41662,
'4213': 41752, '4231': 41858, '4312': 42075, '4321': 41521}
chi square sum: 24.648538376614027
```
### 亂數
Entropy 定義是某個隨機事件平均每個結果發生時所能傳達出的資訊量，公式如下
$$
S = - \sum_{i=1}^{n} P(x_i) log_bP(x_i) = - \sum_{i=1}^{n} P(x_i) I(x_i)
$$其中
$$
I(x_i) = \log_b\left(\frac{1}{P(x_i)}\right)
$$ $I(x_i)$為期望值，由上式可知，當一個事件的機率越低，所獲得的資訊量則越多
## 論文〈Dude, is my code constant time?〉
### INTRODUCTION
面對時序攻擊，舉例來說就是根據密碼的執行時間來推斷密碼，這時判斷執行時間是否是常數時間$O(1)$就十分重，因此本篇論文開發出一種工具 `dudect` ，一個透過統計分析的程式判斷程式是否是以常數時間執行，解決了底層硬體的問題，也就是無法獲得 CPU 運作訊息的問題
### APPROACH
`dudect` 所使用的方法是 `timing leakeage detection tests` ，首先測量兩種不同輸入數據類型的執行時間，然後檢查這兩種時間分佈是否在統計上有顯著差異，運用 fix-vs-random 產生兩種測試資料，第一種資料是常數，第二種資料是亂數，而第一種資料通常會給定一個較特別的值，來了解極端狀況
在統計分析前會先進行後處理如 Cropping: 從一組測量值中刪除或捨棄那些偏離正常值或超出 threshold 的測量值，減少不符合正常情況數據的影響，或是其他高階處理
接著是應用統計測試來嘗試反駁 null hypothesis: `the two timing distributions are equal` ，若是成功反駁此假說，則說明執行時間非常數時間，在本論文中使用 Welch’s t-test 來檢測兩個分佈是否相同
**以下為 Welch’s t-test 在本文應用的說明**
在進行 Welch’s t-test 時， $t$ 越接近 0 代表兩組數據的差異越小，在論文中 $t$ 的 threshold 為 4.5 ， t 的定義如下
$$
t = \frac{\bar{X}_1 - \bar{X}_2}{\sqrt{\frac{\sigma_1^2}{n_1} + \frac{\sigma_2^2}{n_2}}}
$$
- $\bar{X}_1$ 為 class1 採樣的執行時間的平均值
- $\bar{X}_2$ 為 class2 採樣的執行時間的平均值
- $n_1$ 為 class1 採樣的大小
- $n_2$ 為 class2 採樣的大小
- $\sigma_1$ 為 class1 採樣的執行時間的標準差
- $\sigma_2$ 為 class2 採樣的執行時間的標準差
### 實作
在作業要求中有提到在 [oreparaz/dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無，因此實作目標為在 `lab0-c/dudect` 中新增此項功能，根據 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 可以了解 `percentile` 的作用為設定閾值，也就是先前所說的後處理的技巧 `Cropping`
## 研讀 Linux 核心原始程式碼 list_sort.c
Sign in with Wallet
Connect another wallet