2024q1 Homework1 (lab0)

contributed by < Vincent550102 >

Reviewed by `weihsinyeh`

Fix some implement mistake commit 66d7745 可以將具體修正寫在在 commit 的描述中。
commit cdb194b 沒有寫修改的原因。
commit 9126285 這裡參閱規格書中 free 的說明。
有一些中文字打錯字。

Reviewed by `w96086123`

在 q_free 中的實作註記的第一段有一個無意義的空格。
commit e2df64f 只有寫可以解決什麼問題，但沒有提出本來的問題是由哪裡出現。另外，在 queue.h 中有提供 q_release_element 可以解決相同的問題。
在 commit 中，有使用 Fix 可以在說明中寫修改原因。

開發環境

$ gcc --version
gcc (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 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
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      46 bits physical, 57 bits virtual
CPU(s):                             32
On-line CPU(s) list:                0-31
Thread(s) per core:                 1
Core(s) per socket:                 8
Socket(s):                          4
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              106
Model name:                         Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz
Stepping:                           6
CPU MHz:                            2899.998
BogoMIPS:                           5799.99
Virtualization:                     VT-x
Hypervisor vendor:                  KVM
Virtualization type:                full
L1d cache:                          1 MiB
L1i cache:                          1 MiB
L2 cache:                           128 MiB
L3 cache:                           64 MiB

事前準備

list_entry / container_of

透過研讀老師的你所不知道的 C 語言: linked list 和非連續記憶體，~~個人總結~~ 出以下結論:

該巨集利用一種巧妙的技巧，通過一個被繼承結構中的成員變量，反向追蹤以獲取繼承它的結構體，展現了一種反向繼承鏈的實踐方法。
它的存在旨在透過模仿一些高級語言所具備的特性（如繼承）來實現特定的功能，展現了一種模擬高級語言特性的技術。
此技術使得繼承關係更加松散，減少了耦合度，無需額外定義反向繼承機制，從而提升了程式碼的靈活性和可維護性。

列出關於「反向繼承機制」的權威材料 (如語言規格書和技術報告)，並充分討論 Linux 核心風格的鏈結串列與其到底有什麼關聯。

另外，我想到一件很有趣的事情，若 container_of 能回傳一個物件的上一層繼承的物件，那如果這個物件上一層繼承的物件尚未初始化，那這時候再對其 container_of 會發生什麼事？

以下程式碼，我們對一個物件初始化 list_head，並且取得上一層繼承的物件 element_t 的成員 value。

struct list_head *li = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(li);
element_t *e = list_entry(li, element_t, list);
e->value = strdup("test");
printf("%s\n", e->value);

發現輸出是 test，且無錯誤產生，進一步驗證可用 gdb 觀察 stack frame

指定的佇列操作

q_new

commit f6ee1dc

回傳一個空的 list_head。確認 malloc 成功後，我們可以透過 INIT_LIST_HEAD 這個巨集來初始化這個 list_head。

q_free

commit e2df64f

接下來使用 list_for_each_entry_safe 進行走訪，對每個走訪到的節點都先透過 list_del 將這個節點從鏈結串列中移開，之後再釋放該元素，走訪完畢後再釋放 head。

實作註記:
透過實作 e_free 等函式，讓 element_t 的物件能夠完整釋放，當初忘記釋放 e->value 而直接釋放 e 導致釋放不完全。

q_insert_* / q_remove_*

commit e171a43

實作上類似的函式，須注意使用 strncpy 使該 buf 能控制寫入長度，否則會導致緩衝區溢位等資安問題。

並且要在 sp[bufsize - 1] = '\0';，避免造成記憶體位置洩漏。

q_delete_mid

透過快慢指標的技巧以及 list_for_each 巨集完成在環狀雙向的鏈結串列上找中點並刪除。

commit 9126285

發現原本的實作多加到一處 fast = fast->next 造成每次迴圈會使得快指標多跑一次（共三次），將其刪除即可修正。 commit f3dddbe

     struct list_head *slow = head, *fast;
     list_for_each (fast, head) {
-        fast = fast->next;
         if (fast != head && fast->next != head)
             fast = fast->next;
         else
             break;
         slow = slow->next;
     }

q_swap

commit d188f4b

透過 list_for_each 走訪每個元素，並且嘗試取得下個元素，若有，則將兩者交換。

q_reverse

透過 list_for_each_safe 走訪每個元素，並且每次都將該元素放到 head，達到反轉的效果。

commit 930e774

q_reverseK

參考了 WangHanChi 同學的實作，過程中透過 list_for_each_safe 走訪各個元素，並且每第 k 個元素都做以下事情:

使用 list_cut_position 將 i ~ i+k-1 的元素剪下，並放到 tmp_head
透過 q_reverse 將 tmp_head 反轉
使用 list_splice_init 將 tmp_head 的內容串回原鏈結串列，並重制 tmp_head

commit 2c415ed

q_delete_dup

觀察性質可以知道，由於此鏈結串列是排序好的，因此同樣的元素會~~兩兩相臨~~ 兩兩相鄰。

透過 list_for_each_entry_safe 走訪各個元素，維護一個 flag，每個元素和下個元素數值相同，則將目前這個元素刪除，並將 flag 啟用，以便下次迴圈也將該元素移除，若不同則將 flag 重制置。

commit eb67d38

q_sort

commit ab859cf

首先，先將此環狀鏈結串列的 head->prev->next 設為 NULL，使得退化為單向的鏈結串列。

我們透過快慢指標的技巧找到該鏈結串列的中點，再用分治技巧中的分（Divide）將鏈結串列分為多個小點，接下來，治（conquer）的過程中我們用間接指標的技巧輔助，將兩個已排序的鏈結串列合併為一個已排序的鏈結串列，最後我們便可以得到一個排序好的鏈結串列，最後再將回邊接回來即可。

在檢查過程中，由於測試資料是 1~12，但這個作業是以字串形式處理，所以 strcmp 的時候會以字典序排列，導致以下的狀況誤判實作沒做好，造成多餘的排錯時間浪費。

l = []
l = [3]
l = [3 1]
l = [3 1 5]
l = [3 1 5 10]
l = [3 1 5 10 11]
l = [3 1 5 10 11 12]
l = [3 1 5 10 11 12 9]
l = [1 10 11 12 3 5 9]
Freeing queue

參考了你所不知道的 C 語言: linked list 和非連續記憶體中的實作。

q_merge

使用很直覺的做法，透過 list_for_each_safe 走訪每個元素，並將該元素使用 list_splice_init 串到第一個元素並重製，結束走訪後，使用 q_sort 將其排序。

TODO: 可透過 mergesort 的技巧直接對 head 做事，由於符合對應的性質。

commit 2279bd2

q_descend / q_ascend

這題是個經典的單調序列問題，我們的最終目標為找到給定序列中的單調遞增/遞減序列，因此需要維護一個目前最大值 max_val，用 list_for_each_safe 走訪每個元素，當目前的元素比 max_val 大就更新它，否則就將這個元素移除。

遞增或遞減兩者作法雷同，遞減只要先將原序列反轉，處理完後再將結果反轉即為答案。

commit 3d14944

研讀論文〈Dude, is my code constant time?〉

這篇論文介紹了一種名為 dudect 的工具，該工具用於評估特定平台上的代碼是否以恆定時間執行，這對於避免時間攻擊（Timing Attack）相當重要。

與需要對硬件體行為進行建模的先前方法不同，dudect 通過不假設這些前提，使用執行時間的統計分析，使其適合於黑盒測試。

時間攻擊（Timing Attack）

是一種旁路攻擊（Side-channel attack），透過電腦系統的實作缺陷而洩漏的資訊來做的攻擊，而不是利用演算法本身的弱點

此論文首先先進行了時間攻擊的檢測，他們使用了 fix-vs-random tests，也就是準備兩筆測資，其中一筆是固定的常數，另一個則為隨機的選定。他們進行了 null hypothesis the two timing distributions are equal。

改進 qtest 中的常數複雜度判斷

可以發現，當我們在測試資料中使用 option simulation 1 時，將會進行 q_insert_head / q_insert_tail / q_remove_head / q_remove_tail 的常數時間複雜度檢查。

對應的程式碼如下:

constant.h

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

fixture.c

static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
    for (size_t i = 0; 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]);
    }
}

static bool test_const(char *text, int mode)
{
    bool result = false;
    t = malloc(sizeof(t_context_t));

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        init_once();
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }
    free(t);
    return result;
}

#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

同時，發現到論文中有提及會將測量後的第一批結果丟棄，也閱讀了 dudect 的原始碼後，他會將迴圈從 10 開始:

fixture.c

static void update_statistics(dudect_ctx_t *ctx) {
  for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
    int64_t difference = ctx->exec_times[i];

    if (difference < 0) {
      continue; // the cpu cycle counter overflowed, just throw away the measurement
    }

研讀 lib/list_sort.c 並嘗試改進

首先，在檔案中時常出現形如 __attribute__((nonnull(2,3))) 的語法，該語法有出現在 gcc 的手冊中，被稱為 Function-Attributes，大意就是標示這個函式的第 2, 3 個參數不能是 null。

在此檔案中實作了三個函式，分別為 list_sort merge merge_final，將特點註記：

`list_sort`

整體是透過 bottom up 的方式來達成，充分發揮 cache 機制。
透過 head->prev->next = NULL; 將此環狀鏈結串列變單向的。
透過 count 變數來控制合併。
控制合併的數量來確保可以放的進 L1 cache。

`merge`

重複的程式碼，參考你所不知道的 C 語言: linked list 和非連續記憶體中的案例探討: LeetCode 21. Merge Two Sorted Lists，可進行以下程式碼縮減。

-  struct list_head *head, **tail = &head;
+  struct list_head *head, **tail = &head, **node;

-  for (;;) {
+  for (node = NULL; a && b; *node = (*node)->next) {
     /* 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;
-      }
-    }
+    node = cmp(priv, a, b) <= 0 ? &a : &b;
+    *tail = *node;
+    tail = &(*node)->next;
   }
+  *tail = (struct list_head *)((uintptr_t)a | (uinptr_t)b);
   return head;
 }

`merge_final`

進行最後一次合併，並將各個斷鍊結點接回來。