Try   HackMD

2024q1 Homework1 (lab0)

contributed by < wu81177 >

開發環境

$ 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:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
    CPU family:          6
    Model:               140
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         4700.0000
    CPU min MHz:         400.0000
    BogoMIPS:            5606.40

指定的佇列操作

q_new

實作 q_new 過程中,我學習到 list.hlist_headINIT_LIST_HEAD 的部份

LIST_HEAD

從結構成員可以發現 list_head 組成的佇列是雙向佇列,同時我也理解到 list_head 除了獨立當作佇列的頭,也會嵌入佇列成員結構體中,佇列成員在這份作業中為 element_t

INIT_LIST_HEAD

函數 函式是用來初始化已存在的 list_head ,如果要同時宣告並初始化可用 LIST_HEAD()

無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

q_free

list_for_each_safelist_for_each_entry_safe 都能確保釋放當前節點不會遺失下一個節點,然而後者有使用 list_entry ,選用它就能輕鬆獲得元素的指標並釋放成員
迴圈中使用 q_release_element 來釋放空間,最後再釋放 head

改進你的漢語表達。

而在運行 q_test 的時候發現有問題因此使用 Valgrind 檢查,以下為檢察結果 :

ERROR: Attempted to free unallocated block.  Address = 0x4b8e850
==31792== Invalid read of size 8
==31792==    at 0x10F43C: find_header (harness.c:98)
==31792==    by 0x10F43C: test_free (harness.c:181)
==31792==    by 0x10F72E: q_release_element (queue.h:120)
==31792==    by 0x10F72E: q_free (queue.c:30)
...

發現少檢查 head 為空的情況

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

原先 value 是直接使用 s 的空間,後來參考別人的發現應該使用 strdup ,因為 s 可能會被改動

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
-    e->value = s;
+    e->value = strdup(s);

    list_add(&e->list, head);
    return true;
}

使用 list_add 可以將新元素放置在 head 後面, list_add_tail 則可以放到 head 前面
發現應該要檢查 strdup 是否成功,如果失敗應該要釋放當前元素,如下

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
+   if(!e->value){
+       free(e);
+       return false;
+   }
    list_add(&e->list, head);
    return true;
}

q_remove_head & q_remove_tail

list.h 中可以發現 container_oflist_entry 的功能完全相同,我選擇了前者來獲取 element_t 的指標
移除元素有 list_dellist_del_init 可用,我選用後者,否則再次使用已移除的元素時可能會出錯

  • 發現沒有排除佇列為空的情況,原先的程式在下列第四行會出錯
-   if (!head)
+   if (!head || list_empty(head))
        return NULL;
    element_t *e = container_of(head->next, element_t, list);

q_size

使用 list_for_each 走訪佇列並且計數

q_delete_mid

我使用的方法是從鏈結串列頭 head 出發,同時使用兩個指標進行走訪,一個指標順行,另一個指標則逆行,直到它們相遇(奇數個元素情況)或者在交會前一步(偶數個元素情況)再刪除順行指標所指向的元素

  • 發現使用 q_release_element 後再用 free 釋放元素內容是多餘的
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *forward = head->next;
    struct list_head *backward = head->prev;
    while (forward != backward && forward->next != backward) {
        forward = forward->next;
        backward = backward->prev;
    }
    element_t *e = container_of(forward, element_t, list);
    list_del(forward);
    q_release_element(e);
-    free(forward)
    return true;
}

:warning: 留意詞彙的使用:

q_delete_dup

使用兩層迴圈比對,原本都想用 list_for_each ,後來發現會重複比對,改成以下這樣

    list_for_each (outer, head) {
-        list_for_each(inner, head){
+        for (inner = (outer)->next; inner != (head); inner = inner->next) {
            ...
        }
    }

發現當沒有元素或單元素應該 return true

-   if (!head || head->prev == head->next) {
+   if (!head)
        return false;
+   if (head->prev == head->next)
+       return true;

原先的寫法一直無法順利運作

bool q_delete_dup(struct list_head *head)

// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head | head->prev == head->next) {
return false;

struct list_head *outer, *inner, *tmp;
element_t *outer_ele, *inner_ele;
for (outer = (head)->next; outer != (head)->prev; outer = outer->next) {
for (inner = (outer)->next; inner != (head);) {
outer_ele = container_of(outer, element_t, list);
inner_ele = container_of(inner, element_t, list);
if (strcmp(outer_ele->value, inner_ele->value) == 0) {
tmp = inner->next;
list_del(inner);
q_release_element(inner_ele);
inner = tmp;
} else {
inner = inner->next;
}
}
}
return true;
}

明確標注同學的 GitHub 帳號名稱

於是換了寫法,經過同學 kkkkk1109 提醒發現輸入的佇列是已排序的,因此改用他的寫法

你的洞見和檢討呢?

原先針對為排序的串列要使用兩層迴圈檢查有沒有重複,但由於輸入串列已排序,相同的鍵值一定會相鄰,因此只需要檢查相鄰的節點,如果和前者相同即刪除,如此一來可以將時間複雜度降低 N 倍

q_reverse

使用 list_for_each_safe 走訪佇列,沿途使用 list_move 將元素移至首位,如此一來就能倒轉順序
原先想將 q_reverse 視為 q_reverseK 的特例,後來覺得在 q_reverseK 中呼叫 q_reverse 比較好實作

  • 多檢查空元素和單元素的情況以提早退出
-   if (!head)
+   if (!head || head->prev == head->next)
        return;

q_reverseK

使用 list_cut_position 剪下子佇列,用 q_reverse 倒序後再用 list_splice 接回去
list_cut_position(head_to, head_from, node) 剪下的部份並不包含 head_fromnode 兩個節點

q_swap

視為 q_reverseK k 為2的特例

q_ascent

從 head 逆向走訪佇列,如果下一個元素大於當前元素則使用 list_del 刪除下個元素,如此一來就能留下遞增元素
學會 strcmp () 怎麼用,此函數會開始比較每一個字串的第一個字元。 如果它們彼此相等,會繼續往下進行配對,直到字元不同或到達較短字串的結尾

q_descent

從 head 逆向走訪佇列,如果下一個元素小於當前元素則使用 list_del 刪除下個元素,如此一來就能留下遞減元素

q_sort

由於我在 q_merge 中會使用這個函式,在使用的前一步它已經是分段排序的佇列,這時候如果用 merge sort 會有不錯的效果,所以我選擇用 merge sort實作之
用來合併兩以排序佇列的函式我定義為 merge_two ,在裡面原先判斷是否遞減和兩元素比較大小的部份使用兩層 if ,後來改為以下較緊湊的寫法

 while (!list_empty(l1) && !list_empty(l2)) {
        element_t *ele_l1 = list_first_entry(l1, element_t, list);
        element_t *ele_l2 = list_first_entry(l2, element_t, list);
-       if(descend){
-           if(strcmp(ele_l1->value, ele_l2->value) < 0)
-                list_move_tail(l2->next, &tmp_head);
-           else
-                list_move_tail(l1->next, &tmp_head);
-       } else {
-            if(strcmp(ele_l1->value, ele_l2->value) < 0)
-                list_move_tail(l1->next, &tmp_head);
-            else
-                list_move_tail(l2->next, &tmp_head);
-        }
+        if (descend == (strcmp(ele_l1->value, ele_l2->value) < 0)) {
+            list_move_tail(l2->next, &tmp_head);
+        } else {
+            list_move_tail(l1->next, &tmp_head);
+        }
 }

而在 q_sort 中,使用先前 q_delete_mid 函式中的方法找到中點,再使用 list_cut_position 剪下後半段,用遞迴的方式分別排序前後兩段再用 merge_two 合併

q_merge

我首先去理解 queue_contex_t 的運作原理
每個 queue_contex_t 代表了一個佇列,其中 q 會指向佇列的頭,而 chain 則是用來連接不同的 queue_contex_t
在這個函式中,我將所有的佇列使用 list_splice 拼接到第一個佇列,並且使用 list_del_init 移除已合併的佇列,最後再使用 q_sort 排序

  • 取第一個佇列時誤用 list_entry,後來使用 list_first_entry
-queue_contex_t *first_q = list_entry(&head->next, queue_contex_t, chain);
+queue_contex_t *first_q = list_first_entry(head, queue_contex_t, chain);

有時會出現 merge 完佇列消失的情況

l = [c r z]
cmd> merge
l = []

後來發現在清空佇列後不移除當前 queue_contex_t 就好了

list_for_each_entry_safe (curr, safe, head, chain) {
        if (curr == first_q)
            continue;
        first_q->size += curr->size;
        list_splice_init(curr->q, first_q->q);
-       list_del_init(&curr->chain);
}

結果

使用 make test 測試,只剩 trace-17 無法通過

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
---     trace-17-complexity     0/5
---	TOTAL		95/100
make: *** [Makefile:60: test] Error 1

可以看到唯 itih 無法通過,有時候 it 會通過,分數為95
最後經由底下修改 lab0/dudect 後可以得到100分

使用 Valgrind 檢查錯誤

先前使用 Valgrind 發現了實作 q_free 的暇疵,而最後我也嘗試使用它來找出 trace-17itih 無法通過的原因,使用過程如下

$ valgrind -q --leak-check=full ./qtest 
cmd> option simulation 1
cmd> it
Probably constant time
cmd> ih
Probably constant time
cmd> rh
Probably constant time
cmd> rt
Probably constant time
cmd> option simulation 0
cmd> quit
Freeing queue

Valgrind 沒有找到記憶體使用問題,同時也發現可能在通過邊緣,上面單獨測試itih 沒問題

實作 Shuffle

queue.c 中加上 q_shuffle 函式, q_test 中加上 do_shuffle 函式檢查是否為空或單節點,還有 console_init 中加上 ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");

* void q_shuffle(struct list_head *head) {
    if (!head || head->next == head->prev)
        return;
    for (int len = q_size(head)-1; len > 0; len--) {
        int random = 1 + rand() % len;
        struct list_head *old = NULL, *new = NULL;
        int j = 1;
        struct list_head *pos;
        list_for_each(pos, head) {
            if (j == random) {
                old = pos;
            }
            if (j == len + 1) {
                new = pos;
                break;
            }
            j++;
        }
        struct list_head *pre_new = new->prev;
        struct list_head *pre_old = old->prev;
        if(old->next == new){
            list_del(old);
            list_add(old,new);
+       } else {
+           list_del(new);
+           list_del(old);
+           list_add(new, pre_old);
+           list_add(old, pre_new);
        }
    }
}

使用 git diffdiff -u 來產生程式碼之間的變異清單,不要憑感覺填入,注意位移量。

首先在外層迴圈把 len 減少,裡面抽出要交換的 index 後用 list_for_each 找到要交換的 oldnew ,最後交換節點
,交換的部份原先的寫法沒考慮到兩節點相鄰的狀況

實驗結果

Figure_1
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖,可以看到結果很平均


改進 lab0-c 的 constant time test

閱讀 〈Dude, is my code constant time?〉

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

檢查程式是否為常數運行時間很重要是因為如果不是,有機會受到時序攻擊,資安上存在疑慮
而作者提出了 dudect 工具來測試程式是否為 constant time ,且相較於其他常見工具, dudect 不需要對硬體行為進行建模,也使用了 cropping 預處理,捨棄掉大於 p percentile 的資料,避免離群值過分影響統計結果,而 t value 的計算是使用 Welch’s t 檢定法。

修改 lab0/dudect

檢查 fixture.c 發現沒有進行 cropping ,因此從作者的原始碼以 percentile 為關鍵字找到 percentileprepare_percentiles 函式,接著將前述兩個函式和他們會使用到的函式複製到 fixture.c 裡面,再修改 data type 就可以通過 trace-17-complexity,得到滿分

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

Linux 核心鏈結串列排序

研讀 Linux 核心原始程式碼的 lib/list_sort.c (commit b5c56e) ,首先覺得陌生的就是__attribute__((nonnull())),後來了解到__attribute__ 是 gcc 中用來附加屬性給函式或結構的用法,提供編譯器額外的訊息,而 nonnull(2,3,4,5) 是用來表示函式內的第 2,3,4,5 個參數不能為空,如此一來就不用在函式內檢查,接下來逐一記錄研讀 list_sort.c 中函式的心得。

不要「舉燭」,你該質疑 Linux 核心開發者「如果不這樣做,會怎樣?」

merge

此函式是用來合併已排序鏈結串列,過程中走訪兩個傳入的串列並且使用 cmp(priv, a, b) 來比較 a, b 節點中 priv 的大小,決定誰要排在前面,最後回傳合併的串列
值得注意的是,根據註解的說法,此函式回傳的是單向並且非環狀的串列,這樣比較適合多次合併使用。

merge_final

for (;;) { /* if equal, take 'a' -- important for sort stability */ if (cmp(priv, a, b) <= 0) { tail->next = a; a->prev = tail; tail = a; a = a->next; if (!a) break; } else { tail->next = b; b->prev = tail; tail = b; b = b->next; if (!b) { b = a; break; } } }

前面的 for 迴圈中,除了將兩個串列合併之外,也建立了雙向的連接,然而就算是 b 先結束, a 剩下部份的開頭也統一改名為 b

tail->next = b; do { /* * If the merge is highly unbalanced (e.g. the input is * already sorted), this loop may run many iterations. * Continue callbacks to the client even though no * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ if (unlikely(!++count)) cmp(priv, b, b); b->prev = tail; tail = b; b = b->next; } while (b); /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; }

這段主要是將 b 剩下的部份改成雙向串列,並且在最後將頭尾相接使其形成環狀,但 if (unlikely(!++count)) 這段看不懂,經過查找資料後了解 unlikely 是一個巨集被定義為 # define unlikely(x) __builtin_expect(!!(x), 0) ,其中 !!(x) 會確保輸入值轉變為布林值 ,而 __builtin_expect 是 gcc 的內建函式,查看手冊中 Built-in Function: long __builtin_expect (long exp, long c) 舉例:

if (__builtin_expect (x, 0))
  foo ();

foo () 被執行的情況很罕見的時候可以這樣寫,幫助編譯器最佳化
而在 merge_finalcount 增加,就會變非 0 ,執行 cmp(priv, b, b) ,但我還是不知道為什麼要執行 cmp(priv, b, b) 比較 b 自己,而且由於 ++ 是在前面,所以在執行第一次的時候 count 就會是非 0

list_sort

/* Find the least-significant clear bit in count */ for (bits = count; bits & 1; bits >>= 1) tail = &(*tail)->prev; /* Do the indicated merge */ if (likely(bits)) { struct list_head *a = *tail, *b = a->prev; a = merge(priv, cmp, b, a); /* Install the merged result in place of the inputs */ a->prev = b->prev; *tail = a;

for 迴圈會逐位尋找二進位 count ,直到遇到第一個 0 結束迴圈,接下來判斷如果剩餘的位數存在 1 就進行合併,這樣做相當於當 count+1 不為

2k 時合併,參考何時合併的表格:

count 變化 count 二進位 merge pending 上的節點
0
1
0000
0001
no(
20
1
1
2
0001
0010
no(
21
1
1
2
3
0010
0011
yes (2)
1
3
4
0011
0100
no(
22
2
1
1
4
5
0100
0101
yes 2
(2)
1
5
6
0101
0110
yes (4)
1
1
6
7
0110
0111
yes 4
(2)
1
7
8
0111
1000
no(
23
4
2
1
1
8
9
1000
1001
yes 4
2
(2)
1
9
10
1001
1010
yes 4
(4)
1
1
10
11
1010
1011
yes 4
4
(2)
1
11
12
1011
1100
yes (8)
2
1
1
12
13
1100
1101
yes 8
2
(2)
1
13
14
1101
1110
yes 8
(4)
1
1
14
15
1110
1111
yes 8
4
(2)
1
15
16
1111
10000
no(
24
8
4
2
1
1

而整個函式會逐一把原始串列 list 的節點移到待處理串列 pending , 而 pending 中已排序的子串列會以前段提到的規則合併,直到原始 list 輸入完,接著在最後的 for 迴圈中會繼續合併 pending 中子串列,在這個階段是取最後一個和倒數第二個子串列合併成一個,直到只剩兩個子串列就結束迴圈,執行 final_merge 完成全部的合併

閱讀 < BOTTOM-UP MERGESORT A Detailed Analysis >

Merge sort 可分成 bottom-up 和 top-down , top-down 為課本典型的演算法,將待排序序列分成左右兩個子序列,左右又繼續分裂直到子序列長度是一再合併,適合遞迴處理; bottum-up 則是將待排序序列元素逐一處理,在適當的時機合併,適合非遞迴實作,commit b5c56e 屬於 bottom-up 的一種變形,也是逐一將元素讀入,差別在於合併的時機不同。
下表為 bottom-up 和 top-down 的性能較比較:

Case Best Case Average Case Worst Case
Top-Down 1 2N lg N - 0.146N N lg N - 1.248N
Bottom-Up 1 2N lg N - 0.146N N lg N - 0.965N

雖然 bottom-up 的最差情況效能略輸 top-down , 但是 bottom-up 不需要預先知道序列長度,適合 link-list 實作的序列,這點使得它的實用性大於 top-down。

閱讀 Queue-Mergesort

這篇文章主要介紹一種合併排序的變體稱為 Queue Mergesort ,使用佇列存放待合併序列,先將每個元素單獨作為一個待排序序列存放於佇列,之後不斷從頭部取出兩個進行合併後放到尾部,直到佇列中剩下一個序列即完成排序。
作者也證明這種方法是 optiml mergesort ,也就是對任何待排序元素個數 N ,最差情況下比較次數不比其他 mergesort 算法 演算法多

algorithm 是「演算法」,而「算法」是 the way you calculate,也就是你在國中小學數學測驗卷上的「計算過程」,二者不同。

閱讀 The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules

當兩個要合併的序列長度比值是2的冪時,也就是使用 power-of-2 rules ,有機會使得整體的時間複雜度隨著 N 變大時線性成長,既使合併兩序列的複雜度是超線性,因此相較於 half-half rules ,使用 power-of-2 rules 可以在 N 很大的時候顯著降低運算時間,而在 commit b5c56e 中選用合併序列長度比值上限為 2 是因為不論 N 多少每一步合併都能限制在這個比值以下。

引入 lib/list_sort.c 到 lab0-c

經過了上面的理解,我意識到自己之前實作 q_sort 的方法是多麼天真且愚蠢,因此我引入 lib/list_sort.c 的算法 演算法到 lab0-c (commit 9837691)
過程中做了一些改寫,為了簡化實作,刪去了編譯器優化的部份__attribute__((nonnull()), likelyunlikely ,還有以 strcmp 取代 cmp 函式,因此也刪減了有關函式的傳入參數 prev, cmp