# 2025q1 Homework1 (lab0)
contributed by < `ihost1002` >
{%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 phy
sical, 48 b
its virtual
Byte Order: Little Endi
an
CPU(s): 6
On-line CPU(s) list: 0-5
Vendor ID: GenuineInte
l
Model name: Intel(R) Co
re(TM) i5-8
400 CPU @ 2
.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU(s) scaling MHz: 20%
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
註： Ubuntu使用的是 24.04.2-LTS
## 背景知識
### C 語言規格書
C99 ( `ISO/IEC 9899:1999` ):
pdf 版本: [N1256](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
網頁版本: [N1256](https://port70.net/~nsz/c/c99/n1256.html)
註： pdf 版本來自[你所不知道的C語言：開發工具和規格標準](https://hackmd.io/@sysprog/c-standards) ，打開後右上角顯示 `ISO/IEC 9899:TC3`， 所以網頁版也是相同版本，由 google 搜尋關鍵字 `n1256 html draft` 。
## 針對佇列操作的分支命名
`分支`命名如下:
以 `wip/` 開頭後接 `6` 個分支名稱: `alloc`，`insert`，`size` ，`delete` ，`sort` ，`queue`。
`wip/alloc`:
此`分支`存放 `q_new()`， `q_free()` 兩個函式的 `commit`。
`wip/insert`:
此`分支`存放 `q_insert_head()`， `q_insert_tail()`，`q_remove_head()`， `q_remove_tail()` 四個函式的 `commit`。
`wip/size`:
此`分支`存放 `q_size()` 一個函式的 `commit`。
`wip/delete`:
此`分支`存放 `q_delete_mid()`， `q_delete_dup()` 兩個函式的 `commit`。
`wip/sort`:
此`分支`存放 `q_sort()`， `q_ascend()`，`q_descend()`， `q_swap()`， `q_reverse()`， `q_reverseK()` ，`q_merge()` 七個函式的 `commit`。
`wip/queue`:
此`分支`合併上述所有的 `commit`。等到 `16` 個函式都完成且經測試沒問題，再合併到 `master`。
另外下面程式碼實作對應的 commit 來自 wip/queue。 由於前述分支是透過其他分支 rebase 再 merge 而得，因此會在對應的原始分支看到相同的 commit 但可能是 相同/不同的 hash。個人理解是除了 wip/queue 以外的分支都是個人整理用，只對內給自己看，好處是可以馬上知道這個分支做了哪些修改。一旦確認實作正確，隨時可合併出新的 wip/queue 分支
## 針對佇列操作的程式碼實作
概述: 此作業延續自 [2024q1 Homework1 (lab0)](https://hackmd.io/@ihost1002/2024q1-Homework1)，由於自身基礎不足及私人原因，無法完成，這次再次嘗試撰寫，目標先訂為完成所有 `make test` 測試，即執行結果為 `100/100`。目前結果為 `95/95`， `trace-017` 不符要求： `q_insert_head` 、 `q_insert_tail` 、 `q_remove_head` 、 `q_remove_tail` 要求執行後為 `constant time` ，細節及個人想法在對應實作內容 `q_insert_head` 裡。另外所有的程式碼可能很醜，請老師及同學見諒。
### `q_size`
計算目前佇列的節點總量。去年的紀錄: commit [2c3dcd6](https://github.com/ihost1002/lab0-c_2024/commit/2c3dcd602e4aac9645006263ab38c3295af2a282)，這次用 list_for_each 重寫
```diff
+ /* Return zero if queue is NULL or empty */
- const struct list_head *count = head;
- while (count->next != head) {
- count = count->next;
+ const struct list_head *node = NULL;
+ list_for_each(node, head)
```
comit [fd560e4](https://github.com/ihost1002/lab0-c/commit/fd560e41c3781232a5b88c3e67e42bb7100a2b97)
### `q_new`
建立新的「空」佇列。去年的紀錄: commit [7eb7ee4](https://github.com/ihost1002/lab0-c_2024/commit/7eb7ee4ec942f5876b7fe56fdfed39347399eda9)、commit [97b841f](https://github.com/ihost1002/lab0-c_2024/commit/97b841f74ae52d0676f34f586b643c80d6f694f0)、commit [498c33b](https://github.com/ihost1002/lab0-c_2024/commit/498c33b745f684c93b73312a7cbb15ee6488fc87)。這次重寫，用到的內建函式用註解的方式說明，並說明 malloc 被 test_malloc 取代， commit message 只寫出應完成的結果， [commit 86d2439](https://github.com/ihost1002/lab0-c/commit/86d24392b5dafc35bec91abc26b5e724e891eb4f)
### `q_insert_head`
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。舊的紀錄: commit [360627d](https://github.com/ihost1002/lab0-c_2024/commit/360627dfe69f8d4461963a9ae63f75b6636a0772)， 這次用輔助函式 q_insert 把實作內容寫在前者，並使用 function pointer: insert 依據 position 來判斷呼叫 list_add / list_add_tail ，
```diff
/*
* Define pointer to function of type
* void (*)(struct list_head *, struct list_head *)
* refer to list_add(), list_add_tail().
*/
+typedef void (*list_insert)(struct list_head *node, struct list_head *head);
+
/* Do q_insert* operation */
+static inline void insert_operation(list_insert operation,
+ struct list_head *node,
+ struct list_head *head)
+{
+ operation(node, head);
+}
/* Helper function of q_insert_* */
+static inline bool q_insert(struct list_head *head, char *s, bool position)
+{
+ ...
+ list_insert insert = position ? list_add : list_add_tail;
+ insert_operation(insert, &element->list, head);
+ ...
+}
bool q_insert_head(struct list_head *head, char *s)
{
- return true;
+ return q_insert(head, s, 1);
}
bool q_insert_tail(struct list_head *head, char *s)
{
- return true;
+ return q_insert(head, s, 1);
}
```
commit [29b3593](https://github.com/ihost1002/lab0-c/commit/29b3593a1a6bebe3ee415394d454f236c5f078bc) 。前述實作無法通過 constant time 測試，當時第一個想到的是那篇論文 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，英文不好，所以我先參考了 **Holy** 同學整理的 [論文閱讀：Dude, is my code constant time?](https://hackmd.io/@Holy/BkwZl273w) 知道為 timing attack。 駭客會透過比較字串的時間長短而推論出正確的字串，我當時理解成這個想法：假設一個平行宇宙中，大家用某種餐點的時間都固定，然後一次只能吃一種餐點且用餐期間不會做其他事。大雄喜歡宜靜，想知道她喜歡吃什麼，接著宜靜走進某間餐館吃飯：假如咖喱飯 20 分鐘、 涼麵 15 分、其他餐點...等，那大雄在外面紀錄宜靜用餐的時間不就知道她喜歡吃什麼了嗎？那假如宜靜不想讓別人知道，她只要用餐完後做些其他的事情佔用時間，這樣大雄不就無法得知靜香到底吃了什麼！ 回到實作內容，想法是讓**每次複製字串的時間都相同**，要做到這件事需要知道最大輸入的字串長度，經過測試 (2025/03/19) ， qtest 上最大輸入的字串長度為 4092， 由於 4096 為 2 的倍數，所以我以前述數字為基準。實作時先用以下方法： s 字串複製到 element_t->value， 另外複製 4096 減去前述字串長度，完成複製總字元長度為至少 4096 個字元
```diff
+ /* Fake copy */
+ char fake_string[4096] = "1";
+ fake_string[4096 - length - 1] = '\0';
+ char fake_copy[4096] = {0};
+ strncpy(fake_copy, fake_string, 4096 - length);
```
commit [10b23d7](https://github.com/ihost1002/lab0-c/commit/10b23d7d2416763f35ebb7dfc5056a0e73c51765)，但仍無法通過 constant time 測試。後來想到了，可能是複製到 element_t->value 才行，改成
```diff
- char fake_string[4096] = "1";
- fake_string[4096 - length - 1] = '\0';
- char fake_copy[4096] = {0};
- strncpy(fake_copy, fake_string, 4096 - length);
+ const char *fake_string = "1";
+ int goal = (4096 - length) >> 1;
+ for (int i = 1; i < goal; i++)
+ strncpy(element->value, fake_string, 2);
```
commit [b5c1e0b](https://github.com/ihost1002/lab0-c/commit/b5c1e0bf4bf40be3fc6fd92b86e5c71822b9d835)， 但是 option simulation 1 測試時出現以下錯誤 `ERROR message: Corruption detected in block with address 0x????????????
when attempting to free it.`。 這是由於修改到 MAGICFOOTER 導致的錯誤，只把額外宣告的字元複製到 element_t->value 造成前者錯誤發生，這讓我產生疑惑，難道只能複製 s 的內容到前述 value 中？因此我重複複製 s 內容到 elemet_t->value，並確保至少複製總共 4096 個字元
```diff
- /* Fake copy */
- const char *fake_string = "1";
- int goal = (4096 - length) >> 1;
- for (int i = 1; i < goal; i++)
- strncpy(element->value, fake_string, 2);
+ /*
+ * Copy Strings to element_t->value and make sure to copy at least
+ * 4096 characters in length.
+ */
+ for (int i = 0; i <= 4096; i += length)
+ strncpy(element->value, s, length);
```
commit [f0bb601](https://github.com/ihost1002/lab0-c/commit/f0bb601d500c20f0a6cb79a6abac77e7a4150827)，誤打誤撞通過 constant time 測試，後來以為成功就做成紀錄，結果 trace 17 之前的**效能測試失敗**了。我應確實了解 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉及 commit [b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 但沒做到。
### `q_insert_tail`
在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。舊的紀錄： commit [ee66c58](https://github.com/ihost1002/lab0-c_2024/commit/ee66c58bfc5f955f7a2dd6b481332b05de4ec4a2)，其餘參考 q_insert_head
### `q_free`
釋放佇列所佔用的記憶體。舊的紀錄： commit [f24e239](https://github.com/ihost1002/lab0-c_2024/commit/f24e239b352420b3986eea193b54d56c0d318e4e) 是錯的，修正後可執行
```diff
struct list_head *q = head->next;
- element_t *t = NULL;
while (q->next != head) {
struct list_head *r = q->next;
- free(q);
+ INIT_LIST_HEAD(q);
+ t = container_of(q, element_t, list);
+ free(t->value);
+ free(t);
q = r;
}
- free(q);
+ INIT_LIST_HEAD(q);
+ t = container_of(q, element_t, list);
+ free(t->value);
+ free(t);
free(head);
```
commit [4202d34](https://github.com/ihost1002/lab0-c_2024/commit/4202d34e8e6e03290c08baad0009907634493d22) 。這次用內建 list_for_each_safe 走訪所有節點 、 INIT_LIST_HEAD 斷開鏈結 、 q_release_element 釋放對應記憶體， commit [d80404d](https://github.com/ihost1002/lab0-c/commit/d80d04d95e2fa93c4821f20b1083b2fc9a2c4712)
### `q_remove_head`
在佇列開頭 (head) 移去 (remove) 給定的節點。舊的紀錄： commit [48ba2b7](https://github.com/ihost1002/lab0-c_2024/commit/48ba2b7d44154cb0a3125594ce618be61092ad4f)， 含 q_remove_tail 實作， 除了移除節點的是 頭 或 尾 其餘是重複的程式碼。後來跑 traces/trace-xx 的時候發現錯誤，修正後
```diff
- removed_e->value[bufsize - 1] = '\0';
+ size_t str_n = strlen(removed_e->value);
+ size_t size = str_n <= bufsize ? str_n + 1 : bufsize;
+ if (str_n > bufsize) {
+ removed_e->value[size - 1] = '\0';
+ }
- strncpy(sp, removed_e->value, bufsize);
+ strncpy(sp, removed_e->value, size);
- removed_e->value[bufsize - 1] = '\0';
+ size_t str_n = strlen(removed_e->value);
+ size_t size = str_n <= bufsize ? str_n + 1 : bufsize;
+ if (str_n > bufsize) {
+ removed_e->value[size - 1] = '\0';
+ }
- strncpy(sp, removed_e->value, bufsize);
+ strncpy(sp, removed_e->value, size);
```
commit [97fee47](https://github.com/ihost1002/lab0-c_2024/commit/97fee47713c25271558a5ac3837f485265fba3dd)。
這次重寫，使用輔助函式 q_remove 避免重複相同的程式碼及 position 判斷是移出 頭 或 尾端節點
```diff
/* Helper function of q_remove_* */
+static inline element_t *q_remove(struct list_head *head,
+ char *sp,
+ size_t bufsize,
+ bool position)
+{
+ /* Set terminating char */
+ size_t string_length = strlen(element->value);
+ size_t size = string_length <= bufsize ? (string_length + 1) : bufsize;
+ if (string_length > bufsize)
+ element->value[size - 1] = '\0';
+ /* Copy string:value of element into sp */
+ strncpy(sp, element->value, size);
+}
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- return NULL;
+ return q_remove(head, sp, bufsize, 1);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
- return NULL;
+ return q_remove(head, sp, bufsize, 0);
}
```
commit [2034b7f](https://github.com/ihost1002/lab0-c/commit/2034b7fa5f1184efabe2552606e1bcfcb2772f4a)
### `q_remove_tail`
在佇列尾端 (tail) 移去 (remove) 給定的節點。參考 q_remove_head
### `q_delete_mid`
移走佇列中間的節點。舊的紀錄： commit [b2190a3](https://github.com/ihost1002/lab0-c_2024/commit/b2190a36ad3a12a9625c8a80cb6dbd13d4534b22)。 這次參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf) 其中快慢指標技巧重寫， commit [cdcf471](https://github.com/ihost1002/lab0-c/commit/cdcf471407cb4da0982485f0bcb7298f1d535e47)。
### `q_delete_dup`
在已經排序的狀況，移走佇列中具備重複內容的節點。舊紀錄： commit [eb8ac29](https://github.com/ihost1002/lab0-c_2024/commit/eb8ac29144c3e0ba7134024f32b8d96167db7cdf)。 本次些微修改變數名稱及使用內建函式 q_release_element 重寫， commit [ec3fa27](https://github.com/ihost1002/lab0-c/commit/ec3fa272a7c2b47f3e7dfe89b979aba4c2d39b70)。使用 indirect pointer 好處在移除節點時不用更新節點內容
### `q_swap`
交換佇列中鄰近的節點。舊紀錄： commit [e592eb6](https://github.com/ihost1002/lab0-c_2024/commit/e592eb674ded5ba90d2b096131180d40f19455f6)， 當初是想用 xor 來交換數值，但發現無法使用 unitptr_t， 所以就自建輔助程式 swap 來交換每個節點對應的 next 、 prev 的值，現在來看寫得很醜，可能會看不懂。這次重寫發現其功能等同呼叫 q_reverseK 其 k 為 2 ，後續參考 q_reverseK
### `q_reverse`
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點。與 q_reverseK 合併，功能等於前述函式帶入 k = 總節點數，參考 q_reverseK
### `q_reverseK`
類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列。舊紀錄： commit [29763b4](https://github.com/ihost1002/lab0-c_2024/commit/29763b453b3cb8707276bf61775806807e45f7fe)。也有使用 commit [e592eb6](https://github.com/ihost1002/lab0-c_2024/commit/e592eb674ded5ba90d2b096131180d40f19455f6) 的 swap， 所以很醜。本次與 q_swap 、 q_reverse 合併，用 list_move 、 list_move_tail 完成節點交換， commit [a1d7692](https://github.com/ihost1002/lab0-c/commit/a1d7692805dec79a439883b25f653b8c73798753)。 使用 indirect pointer 好處在搬移節點時不用更新節點內容
### `q_sort`
以遞增/遞減順序來排序鏈結串列的節點。 本來想自己想一個符合時間複雜度 O(nlogn) 的實作，但結果是怎樣想都只想出 O(n^2^) ， commit [f9001a0](https://github.com/ihost1002/lab0-c_2024/commit/f9001a044d62d9470c11d694ada3536777e96ccf)，不得已只好參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf) 其中 遞迴方式 且 top-down 的 merge sort 實作，但沒有真懂。用到自建的輔助函式 merge_two_list 來合併兩個佇列， merge_sort_list 遞迴呼叫自己並在把佇列從中切兩半，後半用 mid 作佇列頭，再遞迴呼叫自己完成 merge sort 實作， commit [af4ec1d](https://github.com/ihost1002/lab0-c/commit/af4ec1d455955e4ee45c0afcbc8f686d5b85b5a2)
### `q_ascend`
`element_t ` 結構有兩個成員： `value` 、 `list` ， 每個節點都是前述**結構**中的 `list` ，而 `value` 儲存`字串` 。對每個節點 n1 ，其右邊節點 n2 對應的`字串`與自身`字串`相比為`小`時刪除此節點 n1。舊紀錄： commit [c58a2f4](https://github.com/ihost1002/lab0-c_2024/commit/c58a2f498151606ed64639832c2a6020466fde56) 含 q_descend 實作。本次自建輔助函式 q_delete_strictly 取代重複的程式碼，作法是從最後的節點往前找，帶入 descend 決定是 q_ascend 還是 q_descend， commit [ff9b18d](https://github.com/ihost1002/lab0-c/commit/ff9b18dd2b3c994366c841397363480addbe64e2)
### `q_descend`
與 q_ascend 相似，比較結果為`大`時刪除節點 n1。參考 q_ascend
### `q_merge`
合併所有已排序的佇列，並合而為一個新的已排序佇列。目前是一個可執行的實作，但是當合併越多時越沒效率，commit [c68ad41](https://github.com/ihost1002/lab0-c/commit/c68ad4187b460aa349845d4eaf2e50eabdf6a0e3)
## 閱讀指定的論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### 以及 commit [b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09)
進行中
Sign in with Wallet
Connect another wallet