# 2025q1 Homework1(lab0)
contributed by < [`charliechiou`](https://github.com/charliechiou?tab=repositories) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ 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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
CPU family: 6
Model: 141
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU(s) scaling MHz: 37%
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 384 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 10 MiB (8 instances)
L3: 24 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 原始檔研讀
欲了解如何測試撰寫的程式，第一步便是閱讀原始程式中的內容。
從 Makefile 中可以理解到下列功能：
- **qtest** : 將 `OBJS` 中檔案連結 (Link) 並依照設定編譯成執行檔 `qtest` ，而 qtest 實際連結的檔案補充於後述。
- **%.o** : 將對應的 `.c` 編譯為 `.o` 檔
- **check** : 執行 qtest 並傳入指定的參數 v 及 f
- **test** : 執行測試腳本 `driver.py`
- **valgrind_existence**、**valgrind** : 確認 valgrind 有安裝並用其測試
- **clean**、**disclean** ： 刪除編譯過程中產生的檔案
為了充分理解，我們需要進一步閱讀原始檔中所包含的程式，以整理出下手的方向。
- **qtest.c**：測試佇列的主要程式
- **report.[ch]**：回報特殊事件及錯誤
- **console.[ch]**：建構使用者介面
- **harness.[ch]**：重載 malloc 及 free 使其能夠檢查常見的記憶體分配錯誤
- **queue.[ch]**：lab0須自行完成的部份
- **list.h**：Linux形式的雙向鏈結串列
- **log2_ksguft16.h**
- **random.[ch]**
- **shannon_entropy.c**
- **linenoise.[ch]**
- **web.[ch]**
作業要求為實做 **a chain of circular queues** ，從字面上意思可知並非實做單一一個 circular queue 而是使用 linked list 所串起的多個 circular queues ，因此我們大量使用到 **list.h** 中的 function 來完成 `struct list_head` 相關的操作，並參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#)來學習 Linux 核心中 linked list 的操作。
## Queues 基本操作
### q_new
>Commit : [8158079](https://github.com/charliechiou/lab0-c/commit/81580796e60e44af28469dec56984de20bdaba7c)
q_new 主要目的是創造一個新的佇列供後續操作，先使用 malloc 分配記憶體空間，大小為`sizeof(struct list_head)`。
進一步去了解 malloc 這樣看似操控硬體的程式碼是如何分配記憶體的?
```c
struct list_head *new_queue =
(struct list_head*)malloc(sizeof(struct list_head));
```
點開 malloc 的定義後發現，原始碼中有將 malloc 定義為 test_malloc 重新導向成自定義的 malloc。
其中，使用了 alloc 來代替 malloc 的操作，原先的 `malloc(sizeof(...))` 被替換成 `alloc(TEST_MALLOC, size)` 。進一步查看 alloc 的操作，先確認目前是否是可以 malloc 的模式(i.e., 確認 `noallocate_mode` )，並使用 `fail_allocation` 來確認 alloc 是否正常，而 fail_allocation 會使用一個隨機的數字來模擬記憶體分配失敗的情況。
通過測試後便使用 malloc 分配記憶體，而這邊分配的記憶體則額外又分配了 `block_element_t` 作為其餘資訊使用。
查看 `block_element_t` 為記憶體附上的額外資訊
```c
typedef struct __block_element {
struct __block_element *next, *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_element_t;
```
### q_free
>Commit : [2b1542c](https://github.com/charliechiou/lab0-c/commit/2b1542c8b50901ef95f8f04609844704c4c6009f)
和 q_new 相反， q_free 需要把所有佇列中的內容正確釋放。由於過程中會刪除目前的節點，因此會使用到前述所提到過的 `list_for_each_safe`。
實作的過程中一直遇到本地端可以 make 且 q_free 的功能也正常，但要 git commit 時卻一直無法推送，錯誤訊息如下。
```bash
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:36:16: style: The scope of the variable 'entry' can be reduced. [variableScope]
element_t *entry;
^
Fail to pass static analysis.
```
將程式碼做下列更動後便可順利推送至 github 。
```diff
- element_t *entry;
list_for_each_safe (node, safe, head) {
- entry = list_entry(node, element_t, list);
list_del(node);
+ free(list_entry(node, element_t, list)->value);
+ free(list_entry(node, element_t, list));
- free(entry->value);
- free(entry);
```
分析錯誤原因在於程式碼未通過靜態分析。從改動中可以理解到， cppcheck 偵測到不需要使用 entry 作為變數，直接放在 free 的 function 裡面即可以減少記憶體浪費。
實作這部份時，和 [EricccTaiwan](https://hackmd.io/@ericisgood/linux2025-homework1/edit) 討論 list_del 的用途及 Linux 封裝資料的方式，作為開發過程的討論因此也紀錄於此。參考[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 內提及的資料封裝方式，程式碼中 `list_head` 將 linked list 常用到的 `prev` 及 `next` 封裝，再藉由 `container_of` 巨集得知 list 個別節點的地址。
討論後我們認為，若未使用 list_del 直接 free ，會導致內部的 node 記憶體空間被釋放掉，但 prev 及 next 未被移除。相當於 linked list 中存在一個空的 list_head ，造成 ./qtest 及 make 都可以正常操作，但在需要 commit 時候無法通過 cppcheck 的靜態檢查。
>Commit : [bd3a1a7](https://github.com/charliechiou/lab0-c/commit/bd3a1a710dec80e14eac5c3b00e0a33e3766d6c0)
重新檢視原始檔中 test free 的內容，在 free 的過程中已經將 node 移除了。
```c
/* Unlink from list */
block_element_t *bn = b->next;
block_element_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
```
因此我將 list_del 從 q_free 中移除。
重新討論上述的結論後，發現上述部份的 unlink 是移除 block_element_t 的內容而非 linst_head 的內容，會有此誤解出自於自己沒有仔細閱讀過 test_free 及 test_malloc 的實作方式，以下補充自己閱讀後的理解。
當 queue.c 引入 harness.h 時，會透過 function hooking 把 malloc 及 free 替換成 test_malloc 和 test_free 。其所分配及釋放的記憶體結構如下：
```c
typedef struct __block_element {
struct __block_element *next, *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_element_t;
```
透過結構中的 *next 及 *prev 會把所有分配的記憶體串連，同時利用 payload_size 儲存 payload 的大小，並透過 magic_head 及 magic_footer 標記 payload 的空間 ( magic_head 及 magic_footer 分別為 `0xdeadbeef` 和 `0xbeefdead` )
而使用者也可以透過 find_footer 找到找到 magic number 的位置或透過 find_header 找到所份配記憶體的開頭，而 test_free 也是透過這個方式來將使用者傳入的 payload 位置反推結構體的空間。
因此，上面提到 test_free 已經移除掉 node ，實際上是對於 linst_head 和 block_element 這兩個 linked list 指標混淆導致。
### q_insert_head & q_insert_tail
>Commit : [14954ff](https://github.com/charliechiou/lab0-c/commit/14954ffb212f3f5c3e603548fd5eca41e66108fe)
q_insert_head 和 q_insert_tail 兩者實作細節類似，因此我將兩者開發紀錄一同紀錄並提交至 GitHub 上。前述提及過 malloc 和 INIT_LIST_HEAD 的使用，直接用類似的方式來分配記憶體。分類完成後需要將 function input 的 character 傳給 value 。
然而，這時候我發現自己並不確定應該使用 strcpy 或 strdup ?
分別查看兩者的原始程式碼，和 malloc 相同原始檔中也同樣有將 strdup 做檢查，使用 `test_strdup` 取代，由於前面敘述過 test_malloc 做檢查後用 memcpy 複製記憶體。
參考 stack overflow 上的討論 : [strcpy vs strdup](https://stackoverflow.com/questions/14020380/strcpy-vs-strdup)， strcpy 和`while(*ptr2++ = *ptr1++)`等價，而 strdup 則和底下這兩行等價。
```c
ptr2 = malloc(strlen(ptr1)+1);
strcpy(ptr2,ptr1);
```
可以發現，差別僅在於 strdup 會自動分配需要的空間，而 strcpy 單純複製記憶體內容。因此對於這題實作來說，使用 strdup 會較為方便。
檢查完成是否正確複製 `char *s` 後，依照 insert_head 或 insert_tail 分別使用 `list_add` 及 list_add_tail 將其插入至 head 或 tail 。
### q_remove_head & q_remove_tail
>Commit : [bd9e352](https://github.com/charliechiou/lab0-c/commit/bd9e35291035f5275f9261925dbb72f581a6c62c)
同樣的， q_remove_head 和 q_remove_tail 兩者實作細節類似，我將兩者的開發紀錄及 Github commit 合併紀錄及推送。
remove_head 及 remove_tail 差別在於使用 list_first_entry 或 list_last_entry 來取得要移除的 element ，並使用 list_de 來移除，要注意的是在這邊是 remove 而非 delete 因此 element 僅是和 list 失去連結了，因此仍可以用於後續操作。(也同時不禁尋思 list_del 是否應該命名為 list_remove 而非 list_del ?)
判斷完需要複製的大小後 `copy_size` ，前述有提及過 strcpy 及 strdup 的差異，由於此處已經判斷過複製的大小了，因此使用 strcpy 即可。另一方面為了避免超出設定的 buffer size 因此而使用 strncpy 而非 strcpy ，並在最後補上 `\0` 作為結尾。
```c
/* Copy SRC to DEST. */
extern char *strcpy (char *__restrict __dest, const char *__restrict __src)
__THROW __nonnull ((1, 2));
/* Copy no more than N characters of SRC to DEST. */
extern char *strncpy (char *__restrict __dest,
const char *__restrict __src, size_t __n)
__THROW __nonnull ((1, 2));
```
>Commit : [ea6c94d](https://github.com/charliechiou/lab0-c/commit/ea6c94d181651dd501fff6a5a775e2e148bfc28e)
由於無法通過 Test-17-complexity 的測試，我將 char *sp 的檢查和最一開頭的檢查分開，避免因為 sp 指標錯誤而導致無法移除 node 。
```diff
- if (!head || list_empty(head) || !sp) {
+ if (!head || list_empty(head)) {
return NULL;
}
element_t *first = list_first_entry(head, element_t, list);
list_del(&first->list);
+ if (!sp) {
+ return NULL;
+ }
```
>Commit : [501cc9c](https://github.com/charliechiou/lab0-c/commit/501cc9cafe6c8b1ac84dcbeb60810d900b3da1e8)
雖然這樣能夠通過 Test-17-complexity ，但因為回傳值錯誤而導致無法正確釋放空間，改為回傳 first 後即可通過測試。
```diff
if (!sp) {
- return NULL;
+ return first;
}
```
### q_size
>Commit : [656f662](https://github.com/charliechiou/lab0-c/commit/656f662070d5a289167ad72aa4232928996ac225)
q_size的部份參考[老師課程講義](https://hackmd.io/@sysprog/linux2025-lab0-a#-%E9%96%8B%E7%99%BC%E7%92%B0%E5%A2%83%E8%A8%AD%E5%AE%9A)來實作，原先的構想是使用 for 迴圈遍歷整個 linked list 來統計內部有多少元素。
參考 list.h 中已經定義好的 list_for_each ，可以更精簡的表示遍歷這個行為。同時，也注意到有 list_for_each_safe 及 list_for_each_safe 這兩個差異。
```c
/*list_for_each*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
/*list_for_each_safe*/
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
前者單純遍歷迴圈，後者在遍歷的過程中會先儲存下一個元素。對於統計佇列大小而言，使用 list_for_each 便足夠。
以上便完成 queue 基本的操作。
## Queue 延伸操作
### q_delete_mid
>Commit : [913decf](https://github.com/charliechiou/lab0-c/commit/913decf5b991de68a2c0a62e8fc649d08ff3d813)
Linked list 常使用快慢指標來完成內部指定位置 node 的查找，其分析可參考[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)一文。由於此處的 linked list 為環狀的，因此中止條件設定為 head 而非 NULL 。
```c
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
```
### q_delete_dup
>Commit : [6e8c8be](https://github.com/charliechiou/lab0-c/commit/6e8c8be362345d49c5eaf510ef0756c81ed06889)
```c
list_for_each_safe (node, safe, head) {
element_t *first = list_entry(node, element_t, list);
element_t *second = list_entry(safe, element_t, list);
if (safe != head && !strcmp(first->value, second->value)) {
list_del(node);
free(first->value);
free(first);
dup = true;
} else if (dup) {
element_t *first = list_entry(node, element_t, list);
list_del(node);
free(first->value);
free(first);
dup = false;
}
}
```
在 cppcheck 的過程中遇到以下兩個問題，分別是 shadowVariable 及 constVariablePointer
```bash
queue.c:187:24: style: Local variable 'first' shadows outer variable [shadowVariable]
element_t *first = list_entry(node, element_t, list);
```
[shadowVariable](https://en.wikipedia.org/wiki/Variable_shadowing) 是由於我前面已經定義了 first 而後面 else if 中又重複定義一次，因此無法通過靜態測試。
```diff
- element_t *first = list_entry(node, element_t, list);
+ element_t *temp = list_entry(node, element_t, list);
list_del(node);
- free(first->value);
+ free(temp->value);
- free(first);
+ free(temp);
dup = false;
```
將其更改為其他參數名稱後即可。
```bash
queue.c:180:20: style: Variable 'second' can be declared as pointer to const [constVariablePointer]
element_t *second = list_entry(safe, element_t, list);
```
第二個問題是由於我後面並未更改到 second 這個變數，因此需要將其更改成 const 。
```diff
- element_t *second = list_entry(safe, element_t, list);
+ const element_t *second = list_entry(safe, element_t, list);
```
### q_swap
>Commit : [1dfa41e](https://github.com/charliechiou/lab0-c/commit/1dfa41effe7209088811683d7c72749bde704d6b)
在兩個 node 互換時因為會改動到原先的 node ，因此這邊選擇使用 list_for_each_safe ，可以再次見到這個 function 的方便性。
### q_reverse
>Commit : [bb0ae0c](https://github.com/charliechiou/lab0-c/commit/bb0ae0cca5458c80954240ce7a0e65d5c77ad610)
同樣選擇 list_for_each_safe 來遍歷 node ，由於迴圈最後會停在倒數兩個 node ，因此在迴圈外額外再交換一次節點。
### q_reverseK
>Commit : [e5c1905](https://github.com/charliechiou/lab0-c/commit/e5c1905969930310c264adabdfe4ae093caa82b9)
reverseK 最主要的想法是把 list 切成一段一段後把每一段反轉再拼接回去，因此會需要使用到 list.h 內部裁切跟拼接的 function 。先用 list_for_each 來將 tail 設在目標裁切點的後一個 node ，再使用 list_cut_position 做裁切。
```c
int j = 0;
list_for_each (tail, head) {
if (j >= k) {
break;
}
j++;
}
list_cut_position(&tmp, head, tail->prev);
```
裁切完後便使用前面的 q_reverse 做反轉 `q_reverse(&tmp);` ，接下來的問題便是要如何將 tmp 拼接回去?
在 list.h 中共有三種拼接的方式，列於底下
- list_splice_init : 拼接於最前端
- list_splice_tail : 拼接最末端
- list_splice_tail_init : 將 list 中的頭拼接於指定 list 的尾部
因此使用 list_splice_tail_init 將 tmp 拼接於末端
```c
list_splice_tail_init(&tmp, &new_head);
```
### q_sort
>Commit : [00f619d](https://github.com/charliechiou/lab0-c/commit/00f619d153f4d7fad2c27af879b3a589b2b8cbad)
在排序的部份我使用了 [merge sort](https://en.wikipedia.org/wiki/Merge_sort)，為了方便實作我選擇先把它轉為非環狀的 linked list 。
```c
struct list_head *first = head->next;
first->prev->next = NULL;
head->prev->next = NULL;
```
merge_sort_list 的部份則使用快慢指標來找到中間點，後將第一個及中間的 node 重複傳入 merge_list 來完成。
```c
head = merge_two_list(head, cmp);
second = merge_two_list(second, cmp);
```
因此整個的順序為 : q_sort ( 決定 descend 或 ascend ) -> merge_sort (將 list 轉為 non-circular ) -> merge_two_list (遞迴呼叫 merge_list 來合併)
### q_ascend & q_descend
>Commit : [4c63a68](https://github.com/charliechiou/lab0-c/commit/4c63a687b13e0d8c65f5b85c6db87b375d5d9395)
類似題目有多種解法，可以用 stack 等方式來完成。因為原先的 linked list 是雙向的結構，因此我這邊選擇從後往前確認是否需要刪除，並額外紀錄最大/最小值。
由於原本 list.h 的操作方向是由前往後，因此參考 list_for_each_safe 的操作自行實作了一個由後往前的版本。
```c
for (current = (head)->prev, safe = current->prev; current != head;
current = safe, safe = current->prev) {}
```
### q_merge
>Commit : [aab8d8b](https://github.com/charliechiou/lab0-c/commit/aab8d8b0ebc0297e9f30afa0a36ed680737ec35f)
q_merge 逐一比對需要合成的兩個佇列
```c
element_t *element_min = strcmp(element_1->value, element_2->value) < 0
? element_1
: element_2;
```
若其中一個要合成的佇列已經空掉，則將剩餘的佇列全部接在尾端。
```c
list_splice_tail_init(first, &tmp);
list_splice_tail_init(second, &tmp);
```
最後再把合成完成的 tmp 接回去原始的進入點。
```c
list_splice(&tmp, first);
```
在主程式部份，則是先計算需要的次數 `int count = (size % 2) ? size / 2 + 1 : size / 2;` 後再使用迴圈一個一個將兩個佇列合併。
參考 [EricccTaiwan](https://hackmd.io/@ericisgood/linux2025-homework1/edit) 實作內容，我也嘗試將我 merge_sort所使用到的 sort_list 使用在 q_merge 中，然而由於我在 merge_sort 中所使用到的合併方式是將 linked list 轉為非環狀的再實作，和 q_merge中直接搬移 node 的方法有蠻大落差，需要同時考量 merge_sort 及 q_merge 的使用才能更改，因此先列入 to do list 。
雖然在本地端能夠通過 make test ，但推送到雲端後無法完成檢測。
因此利用 vscode 的搜尋功能查找 `const` 尋找相關的 function ，發現除了 `q_test` 及測試 17 的程式碼外 fixture.c 也和常數時間的測量相關，下一步先進行論文的閱讀。
## 論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)閱讀
### 理論
(To be done ...)
### Marco
使用 error 訊息 `ERROR: Probably not constant time or wrong implementation` 下去搜尋全部檔案，可以找到 `is_insert_tail_const` 函式會確認 insert 是否是 constant time，進一步點開 define 卻發現並沒有和過往一樣跳轉到函式中，反而跳轉到 define
```c
/* Interface to test if function is constant */
#ifndef DUDECT_FIXTURE_H
#define DUDECT_FIXTURE_H
#include <stdbool.h>
#include "constant.h"
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
#endif
```
從命名上可以看出是由 is_##x##_const 帶入 DUT_FUNCS 來完成一條 define 定義四個 function。但這邊又遇到為何是 `##` 及為何是 `_` 的問題。
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
```
逐步拆解這邊的 define 方式
首先第一條 `#ifndef DUDECT_FIXTURE_H` 參考規格書中 6.10.1 關於 `#ifndef` 的說明
>Preprocessing directives of the forms
>#ifdef identifier new-line groupopt #ifndef identifier new-line groupopt check whether the identifier is or is not currently defined as a macro name. Their conditions are equivalent to #if defined identifier and #if !defined identifier respectively.
可以了解到他是和後面一組的，透過這個 define 可以確認是否正確的使用 identifier並確保只會 define 一次，根據規格書的敘述，其相當於 `#if !defined(identifier)` 當程式碼已經 define 過一次便不會再重複使用後面的部份 `#define DUDECT_FIXTURE_H`。
接著進到最看不懂的部份，先搜尋規格書中關於 `##` 的說明，在 6.10.3.3 中寫到
>If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence; however, if an argument consists of no preprocessing tokens, the parameter is replaced by a placemarker preprocessing token instead.
因此如果某個參數的前面或後面緊接著 `##` ，那麼該參數將被對應的 argument 所取代，然後與 ## 另一側的 token 進行拼接。
回頭檢視原本的程式碼才發現 `_` 其實是定義的 identifier，而 x 是輸入的參數，因此照著前述規格書的說明 `##` 會把 `is_` , `x` , `_const(void)` 連在一起。
```c
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
```
先定義好 `_(x)` 後，再使用 `DUT_FUNCS` 來定義每個函式，這邊也可以理解為何是使用 `_(insert_head)` 的形式了，和一般輸入函式的概念大同小異。
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
```
理解了先前不了解的 `##` 及 `_` 後再進一部看是如何完成所有 define 的。
```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 _
};
```
首先在第一行先將所有 DUT_FUNCS 透過 `_(x)` 解析成為
```c
bool is_insert_head_const(void);
bool is_insert_tail_const(void);
bool is_remove_head_const(void);
bool is_remove_tail_const(void);
```
接著在第七行用同樣的方法定義 DUT(x)，並在第十行同樣定義 `_(x)`，因此第 11 行會展開成 `DUT(insert_head)`,`DUT(insert_tail)`,`DUT(remove_head)`,`DUT(remove_tail)` 而每一個又會被第七行的 DUT(x) 展開為 `DUT_insert_head` ,`DUT_insert_tail` , `DUT_remove_head` , `DUT_remove_tail` ，至此完成所有展開。
接著實際測試展開的結果,
先建立一個檔案並在內部定義好前述的內容
```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 _
};
```
按照先前的說明,在 enum 中應該會展開成對應的四個函式,使用指令讓 gcc 編譯過程停在 preprocess 的階段
```bash
gcc -E tmp.c > out.c
```
檢視輸出檔案
```c
# 0 "tmp.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "tmp.c"
# 9 "tmp.c"
enum {
DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail,
};
```
可以看見 enum 內部確實被置換成對應的四個 function 。
### 實作
>Commit : [d583e8b](https://github.com/charliechiou/lab0-c/commit/d583e8bfcac7047147dbdf54869ac85a0adc12d9)
論文內將 dudect 的實作分為三步驟
- Measure execution time
- Apply post processing
- Apply statistical test
因此照著這個脈絡去查看dudect的[原始碼](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)。
程式碼中會先呼叫 `dudect_init` 作為初始化後再呼叫 `dudect_main` 來執行測試，以下是 `dudect_main` 的內容。
```c
dudect_state_t dudect_main(dudect_ctx_t *ctx) {
prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
measure(ctx);
bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
return ret;
}
```
先透過 prepare_inputs 完成三步驟中的 measure execution time 。對應到作業原始碼中下列段落。
```c
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
```
在 dudect 程式碼中有提到，它會丟棄第一次的執行結果並用 prepare percentile 取而代之。
```c
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
```
但在作業原始檔中卻直接進行 update_statics 的測試。
因此我先將 update_statics 中的部份迴圈跳過
```diff
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
- for (size_t i = 0; i < N_MEASURES; i++) {
+ for (size_t i = 5; 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]);
}
}
```
並把 dudect 程式碼中的 percentile 部份新增至作業原始檔案中。
由於原先的程式碼中輸入的是它封裝好的 class ，而作業中的 execute_time 則是 int64_t 因此同樣需要做改動。查看程式碼的說明，這段程式碼將 measurements 根據數據的分佈來排除極端值，因此能夠讓 time complexity 的測試更加穩定。
```c
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
/*
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.
*/
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
改動完重新推送到 github 便通過測試，但這部份我仍還沒徹底理解為何本地測試會通過但遠端無法。此外，在這部份實作我充分受益於 dudect 作者原始碼中的註解，更加體現了老師在課程講義中所提到的
>任何人都可以寫出機器看得懂的程式碼 (在 Windows 檔案總管裡面，隨便選一個 EXE 檔，按右鍵複製，隨後再貼上即可)，但我們之所以到資訊工程系接受訓練，為了寫出人看得懂、可持續維護和改進的程式
## Valgrind + 自動測試程式
### Valgrind
Valgrind 是一個可以在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架。
User space 及 Kernel space 差異參考[維基百科](https://en.wikipedia.org/wiki/User_space_and_kernel_space)所述，主要差異在於可存取的記憶體範圍不同，透過 Virtual memory 來區分兩個區塊避免一般程式在執行時修改到核心，而當 user space 中的程式需要使用到系統資源時則必須通過 system call 來達成。
Valgrind 在執行程式時，當程式碼執行到感興趣的階段會透過 just-in-time (JIT) 編譯技術把機械碼轉換成 IR ，在跳到對應的處理工具插入特定的分析程式碼在轉換回機寫碼繼續執行，因此在分析過程中會造成程式碼執行速度下降。
記憶體的處理方式在前述 [q_free](###q_free) 有提及因此不再重複記錄，這邊實際使用 valgrind 搭配 mass-if 來實際觀察記憶體分配狀況。
### 觀察記憶體分配
首先先在環境中安裝所需要的視覺化工具 mass-if
```bash
$ # install massif-visualizer
$ sudo apt install massif-visualizer -y
```
並在 Makefile 中新增我們要測試的程式，這邊我們簡單使用 q_insert 來觀察 test_malloc 及 malloc 對記憶體的影響。
```diff
+ check-massif: qtest
+ valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd
```
並複製並更改 trace-17-complexity.cmd 來製作 trace-massif.cmd 測試用的檔案。
```cmd
# Test of q_insert_tail
option simulation 1
it
option simulation 0
```
接著便可使用剛剛加入到 Makefile 的命令來測試。
```bash
$ make check-massif
```
完成後會在資料夾中生成一個輸出檔案 `massif.out.xxx` 其中 xxx 是隨機的編號。接著便可使用 ms-print 或 massif-visualizer 來查看結果，這邊我們使用 ms-print 來查看。
先測試使用 test_malloc 的方法的輸出
```bash
MB
1.233^#
|# @
|# @ : :
|# @ : : : : :
|# @ : : : : :
|# @ @ : : : : :
|# @ @ : : :: : : : :
|# @ @ : : :: : :: : : :
|# @ @ : : : :: : :: : :: :: : :
|# @ @ : : : :: : : ::: :: :: : : :
|# @: @ : : :: :: : : ::: :: :: : : :
|# @: @ :: @: :: :: : : ::: ::@:: : : :
|# @:::@ :: @: :: : :: : :: : ::::: ::@:: : : :
|# @:::@ :: @::::::: : ::: : :: : : :::::@: ::@:: : : : :
|# @:::@ :: @::::::: : ::: :: :: : : :::::@: ::@:: : : : ::
|# @:::@::: @::::::: : ::: :: :: :: :: : ::::::@: ::@:: : : : :: :
|# @:::@::: @::::::: :@::: :: :: :: :: : ::::::@::::@:: : : : :: :
|# @:::@::::@:::@::::@:: :@::: :: :: :: :: : ::::::@::::@:: :: ::::::::
|#:@:::@::::@:::@::::@: :@::: :: :: :::: :: : ::::::@::::@:::::::::@::::
|#:@:::@::::@:::@::::@: :@:::::: :: :::: :: ::::::::@::::@:::::::::@::::
0 +----------------------------------------------------------------------->Gi
0 16.00
```
而 mass-if 僅有在 heap allocation/deallocation 時才會 snapshot，參考[說明文件](https://valgrind.org/docs/manual/ms-manual.html)三個用來表示得符號分別為
- `.` : normal snapshot
- `@` : detailed snapshot
- `#` : peak snapshot, only taken after a deallocation happens
觀察其他輸出，可以發現 test_malloc 所使用到的記憶體高達 86.42%
```bash
86.42% (1,117,705B) 0x10FAE3: test_malloc (harness.c:176)
```
而第二高的記憶體消耗為 test_strdup
```bash
37.02% (478,801B) 0x10FCA4: test_strdup (harness.c:231)
```
接著將程式碼中原先 test_malloc 及 test_free 的部份改為 stdlib.h 的 malloc 再同樣確認結果。
```bash
KB
634.0^#
|#
|# :
|# : : : :
|# : : : : :
|# @@ : : : : : : :
|#: @ : : : : :: : : : :
|#: @ : : ::: : :: : : : :
|#: : : : @ : : ::: ::::: :: : : : : :
|#: : : : @ : : ::: : :: :: : : : :: : :
|#: : : : @ : : ::: : :: :: : : : : :: : ::
|#: : : : @ : : ::: : :: :: : : : : : ::: : ::
|#: : : :: @ : : ::: : :: :: : ::: :: : ::::: : ::
|#:: : : :: @ : : ::: : :: :: ::::: :: : ::::: : :@:
|#:: : :: :: @ @ : :::@::: : :: :: :@::::: :: :: ::::::: :@:
|#:: : : :: :: : @ @ : :::@::: : :: :::::@::::: :: :: ::::::: :@:
|#:: : :: ::: ::::: @ :@ ::::::@:::@: :: :::::@::::: :: :@ :::@::: :@:
|#:: : :: :::: ::: : @ :@ ::::::@:::@: :: :::::@::::@ ::::@ :::@::: :@:
|#::::: :: :::::::: : @ :@:::::::@:::@: @: :::::@::::@ ::::@ :::@:::::@:
|#::::::::::::::::: : @ :@:::::::@:::@: @: :::::@::::@:::::@ :::@:::::@:
0 +----------------------------------------------------------------------->Gi
0 5.987
```
同樣觀察前兩高的記憶體使用量，可以發現和前面使用 test_malloc 相比記憶體用量少了許多，這部份是由於 test_malloc 會額外在分配的記憶體前後安插其餘資訊，造成額外的記憶體開銷，詳細分配的原理可以參考前述 [q_free](q_free) 中的敘述。
```bash
50.91% (330,539B) (heap allocation functions) malloc/new/new[], --alloc-fns,etc.
```
```bash
12.03% (78,078B) 0x4A0135E: strdup (strdup.c:42)
```
### Signal處理及應用
參考 lab0(B) 中內容理解 linux 中 signal 的應用。
首先在 q_init 會註冊 SIGSEGV 和 SIGALRM 對應的處理常式 (handler)，查閱 [signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html) 對應的處理分別是
| Signal | Standard | Action | Comment |
| -------- | -------- | -------- |-------- |
| SIGSEGV | P1990 | Core | Invalid memory reference|
| SIGALRM | P1990 | Term | Timer signal from alarm(2)|
當 precess 接受到 signal 時便必須放下工作執行對應的操作。因此
```c
signal(SIGSEGV, sigsegv_handler);
signal(SIGALRM, sigalrm_handler);
```
的操作分別表示若系統發生 Segmentation Fault 時必須跳到 sigsegv_handler 的處理，而系統超時則跳到 sigalrm_handler 處理。而後者的處理函式及對應使用到的函式如下
```c
void sigalrm_handler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
其中 trigger_exception 會設定 error message 並判斷是否 jmp_ready ，若從 siglongjmp 返回則只呼叫 report_event() 輸出錯誤訊息不終止程式。
## 整合網頁伺服器
### 實作
這部份主要敘述 web.c 的運作流程。
```c
static bool do_web(int argc, char *argv[])
{
int port = 9999;
if (argc == 2) {
if (argv[1][0] >= '0' && argv[1][0] <= '9')
port = atoi(argv[1]);
}
web_fd = web_open(port);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
line_set_eventmux_callback(web_eventmux);
use_linenoise = false;
} else {
perror("ERROR");
exit(web_fd);
}
return true;
}
```
首先透過 console.c 中 do_web 函式中的 `web_fd = web_open(port);` 開啟監聽。函式中使用 `listenfd = socket(AF_INET, SOCK_STREAM, 0))` 來建立一個 TCP (SOCK_STREAM) 的 IPv4 (AF_INET) socket 。
設定好相關的 serveraddr，參考 [socket(2)](https://man7.org/linux/man-pages/man2/socket.2.html) 及 [htonl(3p)](https://man7.org/linux/man-pages/man3/htons.3p.html) 查閱這部份設定的內容。其中，`AF_INET` 表示使用 IPv4 protocal，而 `htonl(INADDR_ANY)` 則表示接收任何訊息，而`htons` 則表示接收的 port 。
```c
/* Address to accept any incoming messages. */
#define INADDR_ANY ((in_addr_t) 0x00000000)
```
```c
serveraddr.sin_family = AF_INET;
serveraddr.sin_addr.s_addr = htonl(INADDR_ANY);
serveraddr.sin_port = htons((unsigned short) port);
```
再透過 `bind` 來綁定 socket 到特定的 IP 上，並透過 `listen` 持續監聽。
```c
if (bind(listenfd, (struct sockaddr *) &serveraddr, sizeof(serveraddr)) < 0)
return -1;
/* Make it a listening socket ready to accept connection requests */
if (listen(listenfd, LISTENQ) < 0)
return -1;
```
開啟監聽後透過 web_eventmux 來決定輸入是由終端機輸入或是 web 輸入，參考 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html)的內容並對照程式碼。fd_set 為一個檔案描述符
>fd_set
>A structure type that can represent a set of file descriptors. According to POSIX, the maximum number of file descriptors in an fd_set structure is the value of the macro FD_SETSIZE.
可透過`FD_ZERO(&listenset);` 先將其設定為 0
>FD_ZERO()
>This macro clears (removes all file descriptors from) set.It should be employed as the first step in initializing a >file descriptor set.
後續便透過判斷`server_fd` 是否有來自網路的訊息來決定儲存的資料，並透過 `FD_SET` 將所要監聽的檔案描述符加入到 fd_set 中。
>FD_SET()
>This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.
並且透過 `select` 來監聽多個 fd ， 參考 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 的敘述 select 可以接收來自不同的輸入，且會阻塞 (blocking) 直到 `listenset` 變為 ready，而輸入後面的三個 NULL 則分別表示不監聽可寫入的 fd, 異常事件及超時，因此 result 會一直等到有輸入才繼續下一步。
>select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking.
```c
int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
```
隨後，若判斷有接收到網路的訊息及 fd 已經設定，則透過 `web_rev` 來解析接收到的 url ，最後透過 `wev_sed` 回傳訊息，結束一次完整的傳輸。
開啟兩個終端機器後，其中一個執行 ./qtest 並輸入 web 以監聽 web 傳入的命令。
```bash
cmd> web
listen on port 9999, fd is 3
```
而令一個終端機使用 curl 來傳輸並透過 `127.0.0.1:9999` 連接到本地端及接口執行 new 命令
```bash
$ curl 127.0.0.1:9999/new
```
可以發現令一個終端機成功接收到 curl 傳來的命令
```bash
cmd>
l = []
```
同樣的方式開啟瀏覽器並在網址列輸入，可以發現輸出錯誤訊息。
```bash
cmd>
Unknown command 'favicon.ico'
```
### favicon.ico 問題修正
參考作業說明中[解決 favicon.ico 問題](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-c)來改進瀏覽器傳送命令所遇到的問題。
>Commit : [0ca168e](https://github.com/charliechiou/lab0-c/commit/0ca168ef3bc49b038ca4aa10812352cd3f96ef45)
由於部份網頁會要求 response 需要包含 favicon.ico ，因此 web.h 中需要更改回傳的內容。
```diff
char *p = web_recv(web_connfd, &clientaddr);
- char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
+ char *buffer =
+ "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
+ "Content-Type: text/html\r\n\r\n"
+ "<html><head><style>"
+ "body{font-family: monospace; font-size: 13px;}"
+ "td {padding: 1.5px 6px;}"
+ "</style><link rel=\"shortcut icon\" href=\"#\">"
+ "<h2>Success!</h2>"
+ "</head><body><table>\n";
web_send(web_connfd, buffer);
strncpy(buf, p, strlen(p) + 1);
free(p);
```
從更改後的回傳中 Content-Type 可以了解到我們把它改為回應 html 檔案而非原先單純的回傳文字 ok ，同時我也在回應表單中加入 `<h2>Success!</h2>` ，當成功的時候則會在網頁顯示 Success !。
### Curl 及瀏覽器判斷
>Commit : [b6b1f27](https://github.com/charliechiou/lab0-c/commit/b6b1f27ed8f0dd9073f1f5c0f852d595e7d25e77)
因為更改了回傳的內容，因此使用終端機也同樣會跳出一大串 html 檔案的內容。
```bash
$ curl 127.0.0.1:9999/new
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="#"><h2>Success!</h2></head><body><table>
```
參考 [How can I tell a curl request vs browser request](https://stackoverflow.com/questions/26558888/how-can-i-tell-a-curl-request-vs-browser-request) 的內容，可以透過判斷 user-agent 來知道是 curl 或是 browser ，因此將原始檔做對應的修改。
將接收的 http_request_t 中增加對應的結構
```diff
typedef struct {
char filename[512];
off_t offset; /* for support Range */
size_t end;
+ char user_agent[256];
} http_request_t;
```
並判斷接收的 buf 內是否有 `User-Agent` ，若有的話則存入 req 中
```diff
if (req->end != 0)
req->end++;
}
+ if (strncmp(buf, "User-Agent:", 11) == 0) {
+ strncpy(req->user_agent, buf + 12, sizeof(req->user_agent) - 1);
+ req->user_agent[sizeof(req->user_agent) - 1] = '\0';
+ }
}
```
並增加 is_curl 參數判斷是否使使用 curl 並回應相對應的檔案
```diff
-char *web_recv(int fd, struct sockaddr_in *clientaddr)
+char *web_recv(int fd, struct sockaddr_in *clientaddr, int *is_curl)
{
http_request_t req;
parse_request(fd, &req);
+ *is_curl = 0;
+
+ if (strstr(req.user_agent, "curl") != NULL) {
+ *is_curl = 1;
+ }
+
char *p = req.filename;
```
```diff
- char *p = web_recv(web_connfd, &clientaddr);
- char *buffer =
- "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
- "Content-Type: text/html\r\n\r\n"
- "<html><head><style>"
- "body{font-family: monospace; font-size: 13px;}"
- "td {padding: 1.5px 6px;}"
- "</style><link rel=\"shortcut icon\" href=\"#\">"
- "<h2>Success!</h2>"
- "</head><body><table>\n";
+ char *p = web_recv(web_connfd, &clientaddr, &is_curl);
+ char buffer[2048];
+ if (is_curl) {
+ snprintf(buffer, sizeof(buffer),
+ "HTTP/1.1 200 OK\r\n"
+ "Content-Type: text/plain\r\n\r\n"
+ "Success! Request detected from curl.\n");
+ } else {
+ snprintf(buffer, sizeof(buffer),
+ "HTTP/1.1 200 OK\r\n"
+ "Content-Type: text/html\r\n\r\n"
+ "<html><head><style>"
+ "body{font-family: monospace; font-size: 13px;}"
+ "td {padding: 1.5px 6px;}"
+ "</style><link rel=\"shortcut icon\" href=\"#\">"
+ "</head><body>"
+ "<h2>Success! Request detected from browser.</h2>"
+ "</body></html>\n");
+ }
web_send(web_connfd, buffer);
```
完成後若是從 curl 傳輸則會回傳
```bash
$ curl 127.0.0.1:9999/it/1
Success! Request detected from curl.
```
若是 browser 則是回傳
判斷完 user-agent 後，我發現使用 Edge 和 Firefox 網頁所回傳的資訊不相同。若使用 Edge 在網址列輸入 `127.0.0.1:9999/it/1` 會回傳兩次到 web server 中
而同樣的輸入在 Firefox 則只會回傳一次(第二條為 cache 不會回傳)
這樣的差異也造成如果是使用 Edge 來操作會導致 it 1 指令一次在佇列增加兩個 node ，這邊需要在討論兩個不同瀏覽器的差異。
## 亂數
### Fisher-Yates shuffle
>Commit : [61a461a](https://github.com/charliechiou/lab0-c/commit/61a461ab9e141a5bc0ff56c1063ac11c1ae0fea7)
使用 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 來實作洗牌，每次從剩餘的部份中隨機抽取一個 node 後將其插入到最末端。
在測試過程中，由於 queue.h 不能做改動，因此在推送至 GitHub 時後我將 qtest 中相關的部份註解掉，並將 queue.h 中的定義移除。
### 測試
>Commit : [45f93eb](https://github.com/charliechiou/lab0-c/commit/45f93eb7e8f811504c17d2a8ab15dd0b0083c534)
參考 [lab0](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d) 提供的測試程式來測試。
將輸入存在變數 `input` 中並輸入到 subporecess 中，解碼輸出的 `completedProcess` 後得到 std 的輸出。透過 permute 來取得所有可能的組合並將洗牌後的結果對應的計數加一。
卡方測試期望值 $E$ 為
$$
E =\frac{總測試次數}{總共可能排列組合數}
$$
```python
expectation = test_count // len(s)
```
後計算卡方值 $X^2$ 並累加，其中公式內的 $O$ 為觀測值
$$
X^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}
$$
```python
def chiSquared(observation, expectation):
return ((observation - expectation) ** 2) / expectation
c = counterSet.values()
chiSquaredSum = 0
for i in c:
chiSquaredSum += chiSquared(i, expectation)
```
觀察輸出
```bash
Expectation: 41666
Observation: {'1234': 41936, '1243': 42184, '1324': 41409, '1342': 41552, '1423': 41885, '1432': 41490, '2134': 41702, '2143': 41495, '2314': 41687, '2341': 41689, '2413': 41756, '2431': 41801, '3124': 41422, '3142': 41585, '3214': 41758, '3241': 41391, '3412': 41755, '3421': 41706, '4123': 41935, '4132': 41788, '4213': 41574, '4231': 41768, '4312': 41506, '4321': 41226}
chi square sum: 25.009792156674507
```
所計算出的卡方值為 25.0098 ，由於共 24 總組合因此自由度為 23 並將[顯著水準 alpha](https://en.wikipedia.org/wiki/Statistical_significance) 設為常見的 0.05 ，對照[卡方圖](https://people.richland.edu/james/lecture/m170/tbl-chi.html)查詢 P-value 介於 0.1 至 0.9 大於顯著水準，因此不拒絕虛無假說（$𝐻_0$）意味著樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution。
進一步確認分佈如下，確實遵循 Uniform distribution 。
### 亂度
閱讀作業說明以理解亂度，作業中說明亂度的概念後提及可用 Shannon entropy 來計算資訊含量，公式如下。
$$
S = - \sum^{n}_{i=1} P(x_i) log_b P(x_i)=\sum^{n}_{i=1} P(x_i)I(x_i)
$$
其中 Self-information 的期望值為 $I(x_i)$ 計算公式如下
$$
I(x_i)=log_b (\frac{1}{P(x_i)})
$$
可見當一個事件發生的機率 $P$ 上升，其包含的資訊量 $I$ 便下降。透過將發生機率與資訊量相乘，便可計算出其期望值 $S$ 以得知一個系統所攜帶的資訊量。
理解完上述的概念後，我進一步思考平常再做機器學習時所用到的 [Cross-Entropy](https://en.wikipedia.org/wiki/Cross-entropy) 的概念，其公式如下和 Shannon entropy 類似
$$
H(p, q) = -\sum_{x} p(x) \log q(x)
$$
對照前述的 Shannon entropy 公式，其中 $q(x)$ 是模型預測分佈，而 $p(x)$ 為真實分佈。因此若模型預測 $q(x)$ 越接近實際分佈，其 Cross-Entropy 會越接近 Shannon entropy ，藉此可得知模型的優劣。
### 實作 - ent 亂度
我們可以使用 ent 來測試亂度，分別生成兩個檔案作為測試用的 txt 檔分別為
讀取 linux 內建的 PRNG 前 1024 位元
```bash
head -c 1024 /dev/random > random.txt
```
重複輸出 ABCDEF 的字串並且擷取前 1024 位元。
```bash
yes "ABCDEF" | head -c 1024 > nonrandom.txt
```
再使用 ent 測試，可以得到下列結果
| File | Entropy | Chi square distribution |
| -------- | -------- | -------- |
| random.txt | 7.835973 bits per byte | 219.00 |
| nonrandom.txt | 2.807348 bits per byte | 36425.50 |
可以了解到 random.txt 因為內容隨機因此每一位元所包含的資料量較大，反應在 Entropy 上，接近 1 byte 包含 8 bits 的資訊量。而 nonrandom.txt 的內容為重複的 6 個數字，因此每一個數字出現機率為 1/6 ，透過公式計算
$$
S = - \sum^{n}_{i=1} P(x_i) log_b P(x_i)=-6 \times (\frac{1}{6}) \times \log_2 \frac{1}{6} = 2.5849
$$
和實際的測試結果吻合，表示 1 byte 僅攜帶約 2.8 bits 的資訊量。
由於我們使用了 1024 個位元，因此自由度為 $1024-1 = 1023$
參考 [P-value from Chi sq test statistic in Python](https://stackoverflow.com/questions/11725115/p-value-from-chi-sq-test-statistic-in-python) 計算P-value
```python
>>> 1 - stats.chi2.cdf(219.00,1023)
1.0
>>> 1 - stats.chi2.cdf(36425.5,1023)
0.0
```
可以得知前者數據為隨機的，而後者則否。
### 實作 - qtest 亂度
在 qtest 中執行 `option entropy 1` 並搭配 `ih RAND 10` 來觀察亂數的分佈，其輸出結果如下
```bash
cmd> it RAND 10
l = [fpdwgzckg(35.94%) ezssnpxa(32.81%) hfjwaruy(35.94%) qhgze(26.56%) ajynb(26.56%) najfcvyv(32.81%) wklmv(26.56%) eazql(26.56%) oemwjzzba(35.94%) zgglzmc(26.56%)]
```
其熵的計算是透過 `shannon_entropy.c` 來計算，因此需要檢視其程式碼細節。
計算過程中首先先將字串長度儲存在 `count` 變數中，並使用 `bucket[256]` 來儲存 256 個 ASCII 的內容，並初始化為 0 。
```c
for (uint32_t i = 0; i < count; i++)
bucket[s[i]]++;
```
隨後計算 Shannon entropy
```c
for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i]) {
uint64_t p = bucket[i];
p *= LOG2_ARG_SHIFT / count;
entropy_sum += -p * log2_lshift16(p);
}
}
```
其公式和先前提及相同
$$
S = - \sum^{n}_{i=1} P(x_i) log_b P(x_i)
$$
完成計算後在將結果正規化至 100 %
```c
return entropy_sum * 100.0 / entropy_max;
```
以結果中第一個 `fpdwgzckg(35.94%)` 為例，計算每個數字出現的機率如下
| words | times | probability | $log_2 p(x)$ | $-p(x)log_2 p(x)$
| -------- | -------- | -------- |-------- |-------- |
| f | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| p | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| d | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| w | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| g | 2 | 2/9 = 0.2222|-2.17 |0.4822 |
| z | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| c | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| k | 1 | 1/9 = 0.1111|-3.17 |0.3522 |
| sum | 1 | | |2.9476 |
總和為 2.9476，又因為使用 1byte 編碼 最大可包含的資訊量為 8bits，因此可透過下列公式正規化。
$$
Entropy = \frac{2.9476}{8} \times 100 = 36.845
$$
與程式計算大致吻合。
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
為了讀懂 linux 核心中 list_sort 的內容花了很長的時間研究，主要困難處有以下幾點
- pointer to pointer 的使用方法
- 如何利用 count 判斷合併時機
- pending 及 list 的作用
- merge 如何實作的
list_sort 為了避免 cache thrashing 因此將合併：不合併維持在 2：1，換句話說當有 $3 \times 2 ^ {k}$ 個節點時，會合併前面兩個 $2^{k}$ 變為 $2^{k+1}$。以 k=3 為例，表示目前有 $3 \times 2^{3} = 24$ 個節點，會將前面兩組 8 ($2^{3}$) 個節點的部份合併為 16 ($2^{3+1}$) 個節點。而我們以 pending 來儲存已經合併的節點數，因此當 pending 數量來到 $2^k$ 時便需要進行合併。
為了判斷合併時機，使用 count 來紀錄 pending 內部的節點數，當節點數為 $2^k$ 的時候便需要進行合併。
| count 變化 | count 二進位 | merge | pending 上的節點 |
| ----------- | ------------------- | ----------- | ----------------------------------------- |
| 0 $\to$ 1 | 0000 $\to$ 0001 | no（$2^0$） | 1 |
| 1 $\to$ 2 | 0001 $\to$ 0010 | no（$2^1$） | 1 $\gets$ 1 |
| 2 $\to$ 3 | 0010 $\to$ 001==1== | yes | (2) $\gets$ 1 |
| 3 $\to$ 4 | 0011 $\to$ 0100 | no（$2^2$） | 2 $\gets$ 1 $\gets$ 1 |
| 4 $\to$ 5 | 0100 $\to$ 010==1== | yes | 2 $\gets$ (2) $\gets$ 1 |
| 5 $\to$ 6 | 0101 $\to$ 01==1==0 | yes | (4) $\gets$ 1 $\gets$ 1 |
| 6 $\to$ 7 | 0110 $\to$ 011==1== | yes | 4 $\gets$ (2) $\gets$ 1 |
| 7 $\to$ 8 | 0111 $\to$ 1000 | no（$2^3$） | 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 8 $\to$ 9 | 1000 $\to$ 100==1== | yes | 4 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 9 $\to$ 10 | 1001 $\to$ 10==1==0 | yes | 4 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 10 $\to$ 11 | 1010 $\to$ 101==1== | yes | 4 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 11 $\to$ 12 | 1011 $\to$ 1==1==00 | yes | (8) $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 12 $\to$ 13 | 1100 $\to$ 110==1== | yes | 8 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 13 $\to$ 14 | 1101 $\to$ 11==1==0 | yes | 8 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 14 $\to$ 15 | 1110 $\to$ 111==1== | yes | 8 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 15 $\to$ 16 | 1111 $\to$ 10000 | no（$2^4$） | 8 $\gets$ 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
觀察上述的表格，當 count = $2^{k}$ 時即表示 count 是偶數，此時最低位便會是0，而進行合併。因此這邊需要決定兩件事
- 是否進行合併？
- 要從哪個位置開始合併？
前者透過確認 count 最低位是否為零決定，而後者則是透過移動 tail 來完成。回頭檢視程式碼如下
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
...
}
```
for 迴圈中會一次一次的左移 bits 並檢查最低位的是否為 0 ，當移動到最低位變為 0 時便停止迴圈，同時這時候 tail 也走到需要合併的位置。此時再透過確認 bits 是否為 0 來決定是否要合併。
當 count = 3 時，其二進位制為 0011 且不需要合併，for 迴圈會在執行兩次後碰到0，此時 bits 儲存 0 因此不進入 merge 的階段。
當 count = 4 時，其二進位制為 0100 且需要合併，for 迴圈仍未執行時便跳出，此時 bits 儲存 0100 因此進入 merge ，而此時 tail 位於 pending 的位置，因此從 pending 開始合併。
接著查看 merge 的實作，
```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;
}
```
這部份和過去使用 merge 的方法相同，要注意的便是 `__attribute__((nonnull(2,3,4)))` 及 `cmp` 的用法
參考 [GCC online document](https://gcc.gnu.org/onlinedocs/) 中 [6.33.1 Common Function Attributes](https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Function-Attributes.html)提到
>The nonnull attribute may be applied to a function that takes at least one argument of a pointer type. It indicates that the referenced arguments must be non-null pointers.
表示 2,3,4 這幾個參數必須是 nonnull 的指標。
而 `cmp` 部份，實作如下
```c
/* `priv` is the test pointer so check() can fail the test if the list is invalid. */
static int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
struct debug_el *ela, *elb;
ela = container_of(a, struct debug_el, list);
elb = container_of(b, struct debug_el, list);
check(priv, ela, elb);
return ela->value - elb->value;
}
```
和平常使用比較不相同的地方，它多了一個 `priv` 用來傳入額外的資訊做檢查，進一部檢視 check 的內容。
```c
static void check(struct kunit *test, struct debug_el *ela, struct debug_el *elb)
{
struct debug_el **elts = test->priv;
KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element");
KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element");
KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison");
}
```
可以發現這邊使用到一系列 KUNIT 的單元測試。(To be done... )
完成 merge 後便將下一個 list 的元素增加到 pending 中等待下一次的合併。
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
將所有 list 中的元素搬至 pending 後，再從尾端開始把所有 pending 內的元素兩兩合併，最後由 merge_final 建構回原本的雙向鍊結串列，至此完成 list_sort。
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
>Commit : [4458440](https://github.com/charliechiou/lab0-c/commit/44584401a0279057ab83aba4c03e6fadbb0dd415)
理解程式碼後，將其複製至原先的 queue.c 中，並做簡單的修改去除 priv 這樣用於單元測試的參數，並將原先的 `u8` 改為 `unsigned char` ，最後保留我原先 merge_sort 所使用到的 compare function 即可在 queue.c 中使用 list_sort 。
## Linux 核心並行處理
TBD
## Pull Request
老師於課堂中曾說過，即使是對於文字敘述簡單的修改都有提 Pull Request 的價值，而我過去也不曾提出過 PR。因此趁這次的作業練習提交 PR 的流程，以期待日後能夠在更大的專案做出貢獻。
### [Fix console hang after exceeding input limit #248](https://github.com/sysprog21/lab0-c/pull/248)
> 與 [EricccTaiwan](https://github.com/EricccTaiwan) 一同討論並提交這次的 patch
當編譯完成的 qtest 連續輸入五次錯誤後，會造成使用者即使輸入 quit 也無法退出終端機。如下圖所示
```shell
$ ./qtest
cmd> ak # 任意錯誤指令
Unknown command 'ak'
cmd> bk
Unknown command 'bk'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
Error limit exceeded. Stopping command execution.
cmd> quit # 沒用
cmd> # 只能使用 `Ctrl` + c 跳出
```
當輸入錯誤超過次數會將 quit_flag 設置為 true，進而導致 interpret_cmd 因為判斷 `quit_flag == True` 而直接返回 false。
```c
static void record_error()
{
err_cnt++;
if (err_cnt >= err_limit) {
report(1, "Error limit exceeded. Stopping command execution");
quit_flag = true; //超過限制後一律設成 true
}
}
...
static bool interpret_cmd(char *cmdline)
{
if (quit_flag)
return false; //導致無法進一步輸入指令
...
}
```
這樣的錯誤導致程式碼會陷入無法跳出也無法執行其餘指令的困境，而當使用者使用 `CTRL + c` 則可能導致記憶體洩漏。
確認問題後我們第一個想法便是在指令達到上限後直接呼叫 `do_quit` 退出程式碼，由於原先的內容 `do_quit` 在 `record_error` 後面，因此會需要預先宣告函式。
```diff
+static bool do_quit(int argc, char *argv[]);
static void record_error()
{
err_cnt++;
if (err_cnt >= err_limit) {
report(
1,
- "Error limit exceeded. Stopping command execution");
+ "Error limit exceeded. Stopping command execution, and quitting");
+ do_quit(0, NULL);
}
}
```
提交 PR 後面便收到老師的回覆需要引入 helper function 來完成，因此我們引入 `force_quit` 讓 `do_quit` 及 `record_error` 可以做使用。
```diff
+/* Handles forced console termination for record_error and do_quit */
+static bool force_quit(int argc, char *argv[])
+{
+ cmd_element_t *c = cmd_list;
+ bool ok = true;
+ while (c) {
+ cmd_element_t *ele = c;
+ c = c->next;
+ free_block(ele, sizeof(cmd_element_t));
+ }
+
+ param_element_t *p = param_list;
+ while (p) {
+ param_element_t *ele = p;
+ p = p->next;
+ free_block(ele, sizeof(param_element_t));
+ }
+
+ while (buf_stack)
+ pop_file();
+
+ for (int i = 0; i < quit_helper_cnt; i++) {
+ ok = ok && quit_helpers[i](argc, argv);
+ }
+
+ quit_flag = true;
+ return ok;
+}
+
static void record_error()
{
err_cnt++;
report(
1,
"Error limit exceeded. Stopping command execution, and quitting");
- do_quit(0, NULL);
+ force_quit(0, NULL);
}
}
/* Built-in commands */
static bool do_quit(int argc, char *argv[])
{
- cmd_element_t *c = cmd_list;
- bool ok = true;
- while (c) {
- cmd_element_t *ele = c;
- c = c->next;
- free_block(ele, sizeof(cmd_element_t));
- }
-
- param_element_t *p = param_list;
- while (p) {
- param_element_t *ele = p;
- p = p->next;
- free_block(ele, sizeof(param_element_t));
- }
-
- while (buf_stack)
- pop_file();
-
- for (int i = 0; i < quit_helper_cnt; i++) {
- ok = ok && quit_helpers[i](argc, argv);
- }
-
- quit_flag = true;
- return ok;
+ return force_quit(argc, argv);
}
```
經過改動後，在使用者超過上限後便會直接退出 console。
```shell
$ ./qtest
cmd> ak # 任意錯誤指令
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
Error limit exceeded. Stopping command execution, and quitting
Freeing queue
$
```
### [Correct order of Co-authored-by in commit footer #249](https://github.com/sysprog21/lab0-c/pull/249)
> 同樣與 [EricccTaiwan](https://github.com/EricccTaiwan) 一同討論並提交這次的 patch
這次的錯誤是在上一個 PR 修改時發現的，原先的 `commit-msh.hook` 會在 commit message 最後加入 change-id ，但若有 `co-authored-by:` 出現時會使 change-id 出現在 co-authored-by 之前，進而導致錯誤。
```git
Test title
testing context.
Change-Id: I6d0048910ab1be8c9543d8df76141fbc378fe0c4
Co-authored-by: test_user <test_email@gmail.com>
```
在這次的改動，我們修改了輸出 change-Id 的方法，先判斷 Co-authored-by: 的位置
```diff
numlines = split(lines, footer, "\n")
+ # Find the last line that starts with a comment character.
+ coauthorIndex = 0
+ for (line = 1; line <= numlines; line++) {
+ if (match(tolower(footer[line]), /^co-authored-by:/)) {
+ coauthorIndex = line
+ }
+ }
```
如果並沒有 Co-authored-by 存在的話會直接輸出 change-Id，如果存在的話則將 footer 先輸出，再輸出 change-ID。
```diff
if (unprinted && match(tolower(footer[line]), changeIdAfter) != 1) {
- unprinted = 0
- print "Change-Id: I'"$id"'"
+ # If the Change-Id is the first line in the footer, print it first.
+ if (coauthorIndex == 0 || line > coauthorIndex) {
+ print "Change-Id: I'"$id"'"
+ unprinted = 0
}
}
print footer[line]
+ if(line == coauthorIndex && unprinted) {
+ print "Change-Id: I'"$id"'"
+ unprinted = 0
+ }
}
if (unprinted) {
print "Change-Id: I'"$id"'"
```
透過這樣的改動便可確保每次產生的 change-Id 都在 Co-authored-by 後面。
### [Ensure all trailers remain after Change-Id #251](https://github.com/sysprog21/lab0-c/pull/251)
接著，我們發現不只 Co-authored-by 會有這樣的情況，其他如 Reported-by 也會有類似的情況，因此我們又提了一次 PR 來修正相關的問題。
前一次的 PR 主要透過 match 來比對是否有對應的字詞產生，
```c
match(tolower(footer[line]), /^co-authored-by:/)
```
而這次要比對的較多，因此我們用類似的方法來比對所有字詞。
```c
match(tolower(footer[line]), /^(signed-off-by|acked-by|co-authored-by|reviewed-by|tested-by|suggested-by|reported-by):/)
```
接著便收到老師的回覆
也因此才了解到 git-hook 有使用到正則化的表示方法來對應相關的字詞，我們可以透過修改
`build_commit_trailer_regex` 的內容來直接對應到要搜尋的詞。
先比對 `git config` 裡面有沒有設置對應的 trailer 如果有便存為`trailers_by` 使用它作為我們搜尋字詞的目標。並建立全域變數 `TRAILERS_BY_REGEX` 。
```c
TRAILERS_BY_REGEX="^($(IFS='|'; echo "${trailers_by[*]}")):"
```
在測試後確定 Change-Id 會輸出於其他 footer 後方。
### [Ensure proper footer sorting of footer #256](https://github.com/sysprog21/lab0-c/pull/256)
在確認我們 PR 的過程中，發現了實際上一般的 git config 是不會預先設定好 trailer 的，因此會導致我的 `TRAILERS_BY_REGEX` 永遠是空的，而無法正確的排序。
因此在這次的 PR 中我們定義了幾個 trailers 作為預設值
```diff
+KNOWN_TRAILERS_BY=(
+ 'Signed-off-by'
+ 'Reviewed-by'
+ 'Co-authored-by'
+ 'Acked-by'
+ 'Suggested-by'
+ 'Tested-by'
+ 'Reported-by'
+)
```
並將在老師的回覆中將原本的 trailer_test 用定義的全域變數擴充
```diff
+ trailers_test=(
+ 'CC' 'Change-Id' 'Closes'
+ "${KNOWN_TRAILERS_BY[@]}"
+ )
```
```diff
- TRAILERS_BY_REGEX="^($(IFS='|'; echo "${trailers_by[*]}")):"
-
+ TRAILERS_BY_REGEX="/($(IFS='|'; echo "${trailers_by[*]}" | tr '[:upper:]' '[:lower:]'))/"
```
此外，原先的寫法無法讀取到 awk 以外的內容，因此也同樣需要做修改
```diff
- if (match(tolower(footer[line]), TRAILERS_BY_REGEX)) {
+ if (match(tolower(footer[line]), '"$TRAILERS_BY_REGEX"')) {
```
如此便能夠正確排序 footer，以下舉例修正後的作用。
原先commit message為
```
Test title
Test context
Co-authored-by: user <mail>
Co-designed-by: user <mail>
Co-worked-by: user <mail>
Reported-by: user <mail>
```
由於 `Co-authored-by` 及 `Reported-by` 是我們定義過的 trailer ，因此會被放置在最後面，而沒有定義過的 trailer 則會放在前面，在經過 git-hooker 後 commit-message 會如下，為排序過的版本。
```
Test title
Test context
Co-designed-by: user <mail>
Co-worked-by: user <mail>
Co-authored-by: user <mail>
Reported-by: user <mail>
```
Sign in with Wallet
Connect another wallet