2024q1 Homework1 (lab0)

contributed by < youjiaw >

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。

好的

Reviewed by yu-hsiennn

    // Add remaining elements
-   if (!list_empty(head1))
-       list_splice_tail_init(head1, &merged);
-   if (!list_empty(head2))
-       list_splice_tail_init(head2, &merged);
+   (!list_empty(head1)) ? list_splice_tail_init(head1, &merged) : list_splice_tail_init(head2, &merged);

改寫程式碼 ( q_sort )，使其更為精簡。

感謝提醒，已修改。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i9-10900X CPU @ 3.70GHz
    CPU family:          6
    Model:               85
    Thread(s) per core:  2
    Core(s) per socket:  10
    Socket(s):           1
    Stepping:            7
    CPU max MHz:         4700.0000
    CPU min MHz:         1200.0000
    BogoMIPS:            7399.70
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   320 KiB (10 instances)
  L1i:                   320 KiB (10 instances)
  L2:                    10 MiB (10 instances)
  L3:                    19.3 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-19

指定的佇列操作

實做 queue

對照 Dictionary.com 對 implement 一詞的解釋:

• to fulfill; perform; carry out:
• to put into effect according to or by means of a definite plan or procedure.
• Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
• to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ 資訊科技詞彙翻譯

q_new

配置記憶體，並用 INIT_LIST_HEAD 初始化。

q_free

一開始實作時，沒有確認 head 是否有成功配置到記憶體，在 make test 的 "Test of malloc failure on new" 會出現錯誤。

void q_free(struct list_head *head)
{
+   if (!head)
+       return;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        q_release_element(entry);
    free(head);
}

q_insert_head, q_insert_tail

原本未檢查記憶體配置情況，在 make test 的 "Test of malloc failure on insert_head, insert_tail" 出現錯誤。

    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
+   if (!new->value) {
+       free(new);
+       return false;
+   }

q_remove_head, q_remove_tail

使用 API 的 list_entry 取得開頭的 element ，將值複製到 sp 並從佇列移除。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->next;
    element_t *element = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return element;
}

q_remove_tail 的做法相同，但改取尾端的 element。

-   struct list_head *node = head->next;
+   struct list_head *node = head->prev;

q_size

使用教材提供的做法。

列出程式碼的目的是討論和檢討，倘若你沒有如此的舉措，就不用列出。

好的，已修正。

q_delete_mid

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

好的，謝謝老師提醒。

我原本的做法如下，除了沒有考慮到 q_size 逐一走訪每個節點的成本，使用 indirect pointer 來實作此函式的優缺點也需討論。

int mid_node = q_size(head) / 2;
struct list_head **indir = &head;
for (int i = 0; i <= mid_node; i++)
    indir = &((*indir)->next);
    
element_t *element = list_entry(*indir, element_t, list);
list_del(*indir);
q_release_element(element);

在參考 chun61205 以及 yanjiew1 的建議後，決定使用兩個指標，從頭尾往中間找，以此減少記憶體的存取次數。

commit 85a19ba

struct list_head *left = head->next, *right = head->prev;
while (!(left == right) && !(right->next == left)) {
    left = left->next;
    right = right->prev;
}
list_del(left);
q_release_element(list_entry(left, element_t, list));

q_delete_dup

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

由於是傳入已排序的佇列，因此，只需檢查相鄰節點的值是否相同。
使用 list_for_each_entry_safe 逐一走訪每個節點，若 current 與 next 的值相同，就刪除 current，而 flag 的作用為刪除最後一個重複的節點。

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    element_t *current, *next;
    bool flag = false;
    list_for_each_entry_safe (current, next, head, list) {
        if (current->list.next == head)
            break;

        if (strcmp(current->value, next->value) == 0) {
            list_del(&current->list);
            q_release_element(current);
            flag = true;
        } else if (flag) {
            list_del(&current->list);
            q_release_element(current);
            flag = false;
        }
    }
    return true;
}

目前發現 make test 有時後會出現以下錯誤：
ERROR: Duplicate strings are in queue or distinct strings are not in queue
在經過 ./qtest 測試不同測資後，發現如果最後一個節點有重複的話，會直接被跳過，因此加入檢查程式碼。

commit bb834f2

-   if (current->list.next == head)
+   if (current->list.next == head) {
+       if (flag) {
+           list_del(&current->list);
+           q_release_element(current);
+       }
        break;
+   }

q_swap

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

使用 list_for_each 逐一走訪每個節點。
使用 list_move 將 next 移到 prev 後方，等同於將 current 與 next 交換位置。

struct list_head *current;
list_for_each (current, head) {
    if (current->next == head)
        break;

    list_move(current->next, current->prev);
}

q_reverse

用指標 first 指向開頭節點，並不斷將 next 移動至 head 後方。

struct list_head *first = head->next;
while (first->next != head)
    list_move(first->next, head);

q_reverseK

參考 koty6069 的做法，以每 k 個節點為一組執行 q_reverse。

struct list_head *current, *safe, *ptr = head;
int cnt = 0;
list_for_each_safe (current, safe, head) {
    if (++cnt == k) {
        LIST_HEAD(tmp);
        list_cut_position(&tmp, ptr->next, current);
        q_reverse(&tmp);
        list_splice(&tmp, ptr);
        ptr = safe->prev;
        cnt = 0;
    }
}

q_sort

分為 q_sort 及 list_merge。

1. q_sort

• 使用快慢指標及 list_cut_position 將佇列對半切。
• 不斷遞迴，直到所有節點被分割成單一節點，再進行 list_merge。

    struct list_head *fast = head->next, *slow = head;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head second_half;
    list_cut_position(&second_half, head, slow);
    q_sort(head, descend);
    q_sort(&second_half, descend);
    list_merge(head, &second_half, descend);

2. list_merge

• 比較兩個佇列的開頭節點值，依照結果和排序方式將指定節點移動到 merged （用來存放排序過的節點）。
• 當其中一個佇列空了，就將另一個移動到 merged 尾端。

static void list_merge(struct list_head *head1,
                       struct list_head *head2,
                       bool descend)
{
    struct list_head merged;
    INIT_LIST_HEAD(&merged);

    while (!list_empty(head1) && !list_empty(head2)) {
        int compare_result =
            strcmp(list_entry(head1->next, element_t, list)->value,
                   list_entry(head2->next, element_t, list)->value);

        if ((descend && compare_result > 0) ||
            (!descend && compare_result < 0)) {
            struct list_head *tmp = head1->next;
            list_move_tail(tmp, &merged);
        } else {
            struct list_head *tmp = head2->next;
            list_move_tail(tmp, &merged);
        }
    }

    // Add remaining elements
    if (!list_empty(head1))
        list_splice_tail_init(head1, &merged);
    if (!list_empty(head2))
        list_splice_tail_init(head2, &merged);

    INIT_LIST_HEAD(head1);
    list_splice(&merged, head1);
}

你如何確認目前的測試程式已涵蓋排序演算法的最差狀況？

q_ascend

由尾端向 head 走訪，並比較當前與前一個節點的 value：

1. 若 prev 大於 current，就刪除 prev。

2. 其餘情況，則 current 指向 prev。

struct list_head *current = head->prev;
while (current->prev != head) {
    struct list_head *prev = current->prev;
    if (strcmp(list_entry(current, element_t, list)->value,
                  list_entry(prev, element_t, list)->value) <= 0) {
        list_del_init(prev);
        q_release_element(list_entry(prev, element_t, list));
    } else
        current = current->prev;
}

q_descend

想法與 q_ascend 相同，但將條件改為：若 prev 小於 current，就刪除 prev。

-   if (strcmp(list_entry(current, element_t, list)->value,
-                 list_entry(prev, element_t, list)->value) <= 0) {
+   if (strcmp(list_entry(current, element_t, list)->value,
+                 list_entry(prev, element_t, list)->value) >= 0) {
        list_del_init(prev);
        q_release_element(list_entry(prev, element_t, list));
    } 

由下圖可發現，若由尾端向左邊走訪，只需紀錄最大值，並將小於當前最大值的節點移除即可。

q_merge

目前作法是將所有佇列接起來，再執行 q_sort。

    if (list_is_singular(head))
            return q_size(head);

    queue_contex_t *cur = NULL,
                   *qhead = list_first_entry(head, queue_contex_t, chain);
    list_del_init(&qhead->chain);

    list_for_each_entry (cur, head, chain) {
        list_splice_init(cur->q, qhead->q);
        qhead->size += cur->size;
    }

    list_add(&qhead->chain, head);
    q_sort(qhead->q, descend);

    // https://leetcode.com/problems/merge-k-sorted-lists/
    return qhead->size;

改進你的漢語表達。

分析記憶體問題

執行 make valgrind 以及開啟 Address Sanitizer 後，都沒有偵測到記憶體錯誤。

在 qtest 提供新的命令 shuffle

make 時產生 eror

directory 的翻譯是「目錄」，而非「資料夾」(folder)

好的，已修正。

我在寫完 shuffle 函式後，做了以下幾個步驟：

1. 在 scripts 資料夾 目錄中新增一個 python 檔，內容為教材提供的測試程式。
2. 在終端機確認是否有安裝 python。
3. 執行 make。

接著就出現數行錯誤訊息，以下節錄其中兩行做紀錄

/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:884: undefined reference to `__asan_report_load8'
/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:887: undefined reference to `__asan_report_load8'

這與 Address Sanitizer 有關，查閱 GCC 手冊。

好，謝謝老師提醒。

就我的觀察，所有的 .c 檔均有產生此錯誤，內容格式為

/usr/bin/ld: [路徑名稱]: undefined reference to `xxx`

嘗試解決：
首先，刪除測試的 Python 檔案和 shuffle 函式，確保在 Visual Studio Code 的版本控制中，沒有任何更改過的項目（版本與成功執行 make valgrind 時一致）。但仍有相同的錯誤訊息。

在老師提醒這與 Address Sanitizer 有關後，我嘗試執行 make clean 及 make SANITIZER=0 來關閉它，隨後便可順利執行 make test。

統計方法驗證 shuffle

函式按照 Fisher–Yates shuffle 演算法來實作，以下為測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖。

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

閱讀論文

Dudect 使用 leakage detection tests 在目標平台上進行統計分析，以決定該程式是否能在常數時間內完成，此方法解決了相關研究中，需要對硬體進行建模的困難。

我的疑惑是，為什麼兩種輸入資料的執行時間分佈相同時，就代表此演算法可以在常數時間內完成？

在查閱了 leakage detection 的論文後得知，在兩種輸入資料下，如果演算法的執行時間分佈在統計上沒有顯著差異，則代表演算法的性能不受輸入資料分佈的影響，即時間複雜度為常數時間。

解釋本程式的 "simulation" 模式

由 trace-17-complexity.cmd 可得知，在測試 it, ih, rh 及 rt 是否為常數時間時，會開啟 simulation 模式，讓 qtest.c 的 queue_insert() 與 queue_remove() 函式可以使用 dudect 目錄中的 test_const() 進行測試。

test_const() 會依照預先設定的測試次數，持續呼叫 doit() 來獲得測試結果，此函式可分為三個部分，分別對應到 dudect 中的 dudect_init(), dudect_main() 及dudect_free()。

處理 percentile

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);
}

在 dudect_main() 裡，會捨棄部份的第一批測量結果，根據論文所述，大於閾值 p 的測量值會被捨棄，目的是要讓結果與測量值的分佈盡可能的相符，我目前還不是很理解此意思。

若不是第一次測試，會呼叫 update_statistics()，可以發現在 dudect 中的函式會捨棄前 10 次的結果，而 lab0-c 則是沒有捨棄。

// dudect
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {

// lab0-c
for (size_t i = 0; i < N_MEASURES; i++) {

因此，我們要改進的部份如下：

• 將處理 percentile 的函式加入 lab0-c。
• 更改 update_statistics() 的迴圈走訪範圍。

做完上述的改進後（commit cb0eb09），make test 的 trace-17-complexity 就可以順利通過了。

嘗試引入 lib/list_sort.c 引入到 lab0-c 專案