2025q1 Homework1 (lab0)

contributed by < ihost1002 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

$ 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
網頁版本: N1256
註： pdf 版本來自你所不知道的C語言：開發工具和規格標準 ，打開後右上角顯示 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)，由於自身基礎不足及私人原因，無法完成，這次再次嘗試撰寫，目標先訂為完成所有 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，這次用 list_for_each 重寫

+     /* 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

q_new

建立新的「空」佇列。去年的紀錄: commit 7eb7ee4、commit 97b841f、commit 498c33b。這次重寫，用到的內建函式用註解的方式說明，並說明 malloc 被 test_malloc 取代， commit message 只寫出應完成的結果， commit 86d2439

q_insert_head

在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。舊的紀錄: commit 360627d， 這次用輔助函式 q_insert 把實作內容寫在前者，並使用 function pointer: insert 依據 position 來判斷呼叫 list_add / list_add_tail ，

/*
 * 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 。前述實作無法通過 constant time 測試，當時第一個想到的是那篇論文 〈Dude, is my code constant time?〉，英文不好，所以我先參考了 Holy 同學整理的 論文閱讀：Dude, is my code constant time? 知道為 timing attack。 駭客會透過比較字串的時間長短而推論出正確的字串，我當時理解成這個想法：假設一個平行宇宙中，大家用某種餐點的時間都固定，然後一次只能吃一種餐點且用餐期間不會做其他事。大雄喜歡宜靜，想知道她喜歡吃什麼，接著宜靜走進某間餐館吃飯：假如咖喱飯 20 分鐘、 涼麵 15 分、其他餐點…等，那大雄在外面紀錄宜靜用餐的時間不就知道她喜歡吃什麼了嗎？那假如宜靜不想讓別人知道，她只要用餐完後做些其他的事情佔用時間，這樣大雄不就無法得知靜香到底吃了什麼！ 回到實作內容，想法是讓每次複製字串的時間都相同，要做到這件事需要知道最大輸入的字串長度，經過測試 (2025/03/19) ， qtest 上最大輸入的字串長度為 4092， 由於 4096 為 2 的倍數，所以我以前述數字為基準。實作時先用以下方法： s 字串複製到 element_t->value， 另外複製 4096 減去前述字串長度，完成複製總字元長度為至少 4096 個字元

+    /* 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，但仍無法通過 constant time 測試。後來想到了，可能是複製到 element_t->value 才行，改成

-    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， 但是 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 個字元

-    /* 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，誤打誤撞通過 constant time 測試，後來以為成功就做成紀錄，結果 trace 17 之前的效能測試失敗了。我應確實了解 〈Dude, is my code constant time?〉及 commit b5c56e0 但沒做到。

q_insert_tail

在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。舊的紀錄： commit ee66c58，其餘參考 q_insert_head

q_free

釋放佇列所佔用的記憶體。舊的紀錄： commit f24e239 是錯的，修正後可執行

     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 。這次用內建 list_for_each_safe 走訪所有節點 、 INIT_LIST_HEAD 斷開鏈結 、 q_release_element 釋放對應記憶體， commit d80404d

q_remove_head

在佇列開頭 (head) 移去 (remove) 給定的節點。舊的紀錄： commit 48ba2b7， 含 q_remove_tail 實作， 除了移除節點的是 頭 或 尾 其餘是重複的程式碼。後來跑 traces/trace-xx 的時候發現錯誤，修正後

-    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。
這次重寫，使用輔助函式 q_remove 避免重複相同的程式碼及 position 判斷是移出 頭 或 尾端節點

/* 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

q_remove_tail

在佇列尾端 (tail) 移去 (remove) 給定的節點。參考 q_remove_head

q_delete_mid

移走佇列中間的節點。舊的紀錄： commit b2190a3。 這次參考你所不知道的 C 語言: linked list 和非連續記憶體 其中快慢指標技巧重寫， commit cdcf471。

q_delete_dup

在已經排序的狀況，移走佇列中具備重複內容的節點。舊紀錄： commit eb8ac29。 本次些微修改變數名稱及使用內建函式 q_release_element 重寫， commit ec3fa27。使用 indirect pointer 好處在移除節點時不用更新節點內容

q_swap

交換佇列中鄰近的節點。舊紀錄： commit e592eb6， 當初是想用 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。也有使用 commit e592eb6 的 swap， 所以很醜。本次與 q_swap 、 q_reverse 合併，用 list_move 、 list_move_tail 完成節點交換， commit a1d7692。 使用 indirect pointer 好處在搬移節點時不用更新節點內容

q_sort

以遞增/遞減順序來排序鏈結串列的節點。 本來想自己想一個符合時間複雜度 O(nlogn) 的實作，但結果是怎樣想都只想出 O(n²) ， commit f9001a0，不得已只好參考 你所不知道的 C 語言: linked list 和非連續記憶體 其中 遞迴方式 且 top-down 的 merge sort 實作，但沒有真懂。用到自建的輔助函式 merge_two_list 來合併兩個佇列， merge_sort_list 遞迴呼叫自己並在把佇列從中切兩半，後半用 mid 作佇列頭，再遞迴呼叫自己完成 merge sort 實作， commit af4ec1d

q_ascend

element_t 結構有兩個成員： value 、 list ， 每個節點都是前述結構中的 list ，而 value 儲存字串 。對每個節點 n1 ，其右邊節點 n2 對應的字串與自身字串相比為小時刪除此節點 n1。舊紀錄： commit c58a2f4 含 q_descend 實作。本次自建輔助函式 q_delete_strictly 取代重複的程式碼，作法是從最後的節點往前找，帶入 descend 決定是 q_ascend 還是 q_descend， commit ff9b18d

q_descend

與 q_ascend 相似，比較結果為大時刪除節點 n1。參考 q_ascend

q_merge

合併所有已排序的佇列，並合而為一個新的已排序佇列。目前是一個可執行的實作，但是當合併越多時越沒效率，commit c68ad41

閱讀指定的論文〈Dude, is my code constant time?〉

以及 commit b5c56e0

進行中