2024 q1 Homework 1 (lab0)

# 2024q1 Homework 1 (lab0) [Github](https://github.com/AsaneZeto/lab0-c) ## 實驗環境 ``` ❯ 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: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 3800.0000 CPU min MHz: 800.0000 BogoMIPS: 5599.85 ``` ## 實作佇列操作 ### q_new 使用`malloc`配置一個`list_head`大小的記憶體 (由`sizeof(struct list_head)`決定)，根據`man malloc`： > On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero. 因此在使用`list.h`中定義的`INIT_LIST_HEAD`函式前須檢查這段記憶體位址。 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (head) INIT_LIST_HEAD(head); return head; } ``` ### q_free 根據`queue.h`的描述得知，需要釋放所有佇列元素`element_t`及找到佇列整體的`list_head` > q_free() - Free all storage used by queue, no effect if header is NULL 在`list.h`裡面有定義巨集`list_for_each_entry_safe`，可以安全的逐一走訪並移除包含鏈結串列節點的結構。 ```c void q_free(struct list_head *head) { if(!head) return; element_t *ptr, *safe; list_for_each_entry_safe(ptr, safe, head, list) { q_release_element(ptr); } free(head); } ``` ### q_insert_head 檢查配置後的記憶體是否為有效的(`strdup`也是使用`malloc`)，若不是表示失敗回傳false，否則使用`list_add`把`node`加入佇列開頭後回傳true ```c bool q_insert_head(struct list_head *head, char *s) { element_t *node = malloc(sizeof(element_t)); if (!node) return false; node->value = strdup(s); if (!node->value) { free(node); return false; } list_add(&node->list, head); return true; } ``` ### q_insert_tail 其實就是把佇列的最後一個元素當作head，並對它做`q_insert_head`可以節省重複的程式碼。 ```c bool q_insert_tail(struct list_head *head, char *s) { return q_insert_head(head->prev, s); } ``` ### q_remove_head 如果`head`是無效記憶體位址或是佇列為空的話直接回傳NULL。否則利用`container_of`巨集找到第一個元素的位址`element_t *node`後利用`list_del`把該節點從佇列中移除，接著利用`strncpy`把`node`的字串`node->value`複製到`sp`。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *node = container_of(head->next, element_t, list); list_del(&node->list); if (sp) { strncpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return node; } ``` ### q_remove_tail 使用和`q_insert_tail`一樣的概念來減少重複的程式碼，只是這邊的`head`是最後一個元素的前一個(`head->prev->prev`) ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { return q_remove_head(head->prev->prev, sp, bufsize); } ``` ### q_delete_mid 使用快慢指標技巧找到中間節點。假設佇列大小是`n`，當`n`是 * 基數時會在`fast == head`時結束 * 偶數時會在`fast == head->prev`時結束且`slow`都會停在第`n/2`個節點，也就是中間節點。 ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *slow = head->next, *fast = head->next->next; while (fast != head && fast->next != head) { fast = fast->next->next; slow = slow->next; } list_del_init(slow); q_release_element(list_entry(slow, element_t, list)); return true; } ``` ### q_delete_dup `struct list_head *node`走訪鏈結串列的節點，`struct list_head *ptr`用來記錄`node`之後的節點，並計算總共有幾個字串相同的節點(`cnt`)，超過一個表示存在副本。因為要刪除需要先從鏈結串列中移除後再釋放記憶體，所以用`element_t *tmp`來指向包含`node`的下一個節點所在的元素後再進行操作，直到副本全部刪除完畢。 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; struct list_head *node = head; while (node->next != head) { struct list_head *ptr = node->next; int cnt = 1; while (ptr->next != head) { element_t *curr = list_entry(ptr, element_t, list); element_t *next = list_entry(ptr->next, element_t, list); if (strcmp(curr->value, next->value) == 0) { ptr = ptr->next; cnt++; } else break; } // found duplicated element if (cnt > 1) { while (cnt--) { element_t *tmp = list_entry(node->next, element_t, list); list_del(&tmp->list); q_release_element(tmp); } } else node = node->next; } return true; } ``` ### q_swap `node`從第一個節點走訪整個鏈結串鍊，把`node`移動到`node->next`後面即可。 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (!head || list_is_singular(head)) return; struct list_head *node; for (node = head->next; node != head && node->next != head; node = node->next) { list_del(node); list_add(node, node->next); } } ``` ### q_reverse `node`指向第一個節點，把`node->next`移到佇列開頭直到`node`為佇列最後一個節點即可反轉佇列。 ```c void q_reverse(struct list_head *head) { if (!head || list_is_singular(head)) return; struct list_head *node = head->next; while (node->next != head) { struct list_head *next = node->next; list_del(next); list_add(next, head); } } ``` ### q_reverseK 和`q_reverse`概念一樣，每k個節點作為一組子佇列，且`node`指向上一個子佇列的最後一個節點，當反轉下一組子佇列時節點會加在`node`後方。 ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_is_singular(head)) return; int count = q_size(head); struct list_head *node = head; struct list_head *curr, *next; while (count >= k) { curr = node->next; for (int i = 0; i < k - 1; i++) { next = curr->next; list_del(next); list_add(next, node); } count -= k; node = curr; } } ``` ### q_descend & q_ascend 這一部分的函式實作會涉及到對`element_t`中的`value`值進行比較，為了讓程式碼更精簡，我參考了[list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h#L9)並自定義一個function pointer type `list_cmp_func_t`，允許透過實作不同的比較函數以滿足不同的需求。考慮到`element_t`的`value`是字串，所以會使用`strcmp`作為基礎比較函數，所以`list_cmp_func_t`回傳值的型別也是int。 ```c typedef int __attribute__((nonnull(1, 2))) (*list_cmp_func_t)(const struct list_head *, const struct list_head *); static inline int q_less(const struct list_head *a, const struct list_head *b) { return strcmp(list_entry(a, element_t, list)->value, list_entry(b, element_t, list)->value); } static inline int q_greater(const struct list_head *a, const struct list_head *b) { return strcmp(list_entry(b, element_t, list)->value, list_entry(a, element_t, list)->value); } ``` `q_descend`的功用是要刪除所有後方有比自身更大的值的節點。因為`list_head`是雙向鏈結，直接從最後一個節點往前走訪，並刪除前方任何比它小的節點即可。 `q_ascend`的目標則是和`q_descend`正好相反，因此只需要替換`cmp`，其他的程式碼保持不變，為了避免程式碼的重複，將共用的部分抽出成一個函式`q_remove_cmp`，並讓cmp成為其中一個參數。如此`q_descend`和`q_ascend`只需要呼叫`q_remove_cmp`並傳入`q_less`或`q_greater`即可。 ```c static inline int q_remove_cmp(struct list_head *head, list_cmp_func_t cmp) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head) || list_is_singular(head)) return q_size(head); struct list_head *node = head->prev; while (node != head && node->prev != head) { if (cmp(node, node->prev) < 0) { struct list_head *tmp = node->prev; list_del_init(tmp); q_release_element(list_entry(tmp, element_t, list)); } else node = node->prev; } return q_size(head); } int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ return q_remove_cmp(head, q_greater); } int q_ascend(struct list_head *head) { return q_remove_cmp(head, q_less); } ``` ### q_sort - 首先參考了[Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort)的實驗結果，選擇一開始要將鏈結串列分割成排序好的子串列，注意每個子串列都是單向的。 - 但是在合併階段遇上問題，因為Linux kernel並不支援VLA，需要使用其他方法表達各個子串列。 - 參考[LJP-TW的實作](https://hackmd.io/@LJP/SyRFuull9#q_sort)後發現他使用和[linux/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中相似的技巧: 用sorted sublists開頭節點的`prev`指向上一個sorted sublists的開頭節點，因為在排序過程中皆是考慮單向的串列鏈結，`prev`會失去原本意義。 - `chain`這個變數名有點難理解它的作用，事實上他會是合併前後sublist的第一個節點，因此在這邊重新命名為`subhead`。 - 最後將排序好的鏈結串列修復成雙向的。 ```c static void merge(struct list_head **head, struct list_head *a, struct list_head *b, list_cmp_func_t cmp) { struct list_head **tail = head; while (a && b) { if (cmp(a, b) <= 0) { *tail = a; a = a->next; } else { *tail = b; b = b->next; } tail = &(*tail)->next; } if (a) { *tail = a; } else if (b) { *tail = b; } } /* Sort elements of queue in ascending order */ void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; list_cmp_func_t q_cmp = descend ? q_greater : q_less; // Split original list into sorted sublists. struct list_head *h = head->next, *t = head->next; struct list_head *sublist = NULL; while (h != head) { while (t->next != head && q_cmp(t, t->next) <= 0) { t = t->next; } h->prev = sublist; sublist = h; t = t->next; t->prev->next = NULL; h = t; } // Merge sublists. struct list_head *tmp, *currsub; while (sublist->prev) { struct list_head **subhead; currsub = sublist; subhead = &sublist; while (currsub && currsub->prev) { tmp = currsub->prev->prev; merge(subhead, currsub, currsub->prev, q_cmp); subhead = &(*subhead)->prev; currsub = tmp; } *subhead = currsub; } // Fix doubly linked list head->next = sublist; tmp = head; while (sublist) { sublist->prev = tmp; tmp = sublist; sublist = sublist->next; } head->prev = tmp; tmp->next = head; } ``` ### q_merge - 因為涉及到排序，所以一開始先把所有佇列變成單向鏈結 - `queue_contex_t`中有`int id`這個成員，我把它當作陣列的索引，使用分段合併 - 和`q_sort`一樣，最後把合併後的串列修復成雙向鏈結。 ```c static inline int get_contex_id(struct list_head *head) { return list_entry(head, queue_contex_t, chain)->id; } /* Merge all the queues into one sorted queue, which is in ascending order */ int q_merge(struct list_head *head, bool descend) { // https://leetcode.com/problems/merge-k-sorted-lists/ int n_queue = 0; queue_contex_t *ptr = NULL; list_for_each_entry (ptr, head, chain) { n_queue++; ptr->q->prev->next = NULL; } list_cmp_func_t q_cmp = descend ? q_greater : q_less; struct list_head *l1, *l2; struct list_head *contex1, *contex2; for (int interval = 1; interval < n_queue; interval *= 2) { contex1 = head->next; contex2 = head->next; for (int i = 0; i < interval; i++) contex2 = contex2->next; while (get_contex_id(contex1) + interval < n_queue) { l1 = list_entry(contex1, queue_contex_t, chain)->q; l2 = list_entry(contex2, queue_contex_t, chain)->q; struct list_head *subhead = l1->next; struct list_head **indir = &subhead; merge(indir, subhead, l2->next, q_cmp); l1->next = *indir; INIT_LIST_HEAD(l2); if (get_contex_id(contex1) + 2 * interval > n_queue) break; for (int i = 0; i < interval * 2; i++) { contex1 = contex1->next; contex2 = contex2->next; } } } // Fix doubly linked list l1 = list_entry(head->next, queue_contex_t, chain)->q; struct list_head *prev = l1, *curr = l1->next; while (curr) { curr->prev = prev; prev = curr; curr = curr->next; } l1->prev = prev; prev->next = l1; return q_size(l1); } ``` ## 研讀論文〈Dude, is my code constant time?〉 ### 論文貢獻用統計分析測量一段程式碼是不是常數時間，藉此規避需要硬體模型的問題 ### 方法: Timing Leakage Detection - 對程式執行時間做leakage detection test - 測量兩種資料的執行時間並對它們的分布(timing distribution in this context)做統計檢定 - 三個步驟:Measure execution time, Apply post-processing, Apply statistical test - Step 1: Measure execution time: 1. Classes definition: Leakage detection對需要兩種data class採取兩套測量。例如fix-vs-random tests: 第一種資料會固定在某個常數值(for corner case)，而第二種資料是隨機採樣。 2. Cycle counters: 用來精確的測量執行時間 3. Environmental conditions: class assignment和input preparation都在測量執行時間前完成，以最小化環境對測量結果的影響 - Step 2: Apply post-processing 1. Cropping: 除去measurment artifacts (e.g., interrupted by OS)或修剪到某個特定的threshold 2. Higher-order preprocessing: 根據採用的統計檢定，做某些higher-order preprocessing可能有好處。 - Step 3: Apply statistical test - 用統計檢定拒絕虛無假設: 兩筆資料集的執行時間分布相同 - t-test: Welch’s t-test - Non-parametric tests ### Student's t-distribution - 在只知道樣本的情況下使用 - 自由度決定PDF的形狀，自由度越高越像常態分佈 - 統計量$t=\frac{\bar{X}_n-\mu}{S_n /\sqrt{N}}$ - $N$為樣本數 - $\mu$為母體平均數 - $\bar{X}_n$為樣本平均數 - $S_n$為樣本標準差 #### Welch's t-test - Student's t-test的變化版，在兩樣本有不一樣的變異數及樣本數量的情況下更可靠 - 統計量 $t=\frac{\bar{X}_1-\bar{X}_2}{\sqrt{s^2_{\bar{X}_1}+s^2_{\bar{X}_1}}}$ - $\bar{X}_i$: 第i種樣本的平均數 - $s_{\bar{X}_1}=\frac{s_i}{N_i}$: 第i種樣本的標準誤差 (standard error) - $s_i=\sqrt{\frac{1}{N_i-1}\sum^N_{j=1}(X_{ij}-\bar{X_i})^2}$: Corrected sample standard deviation ### 補齊lab0-c處理percentile的程式碼將[oreparaz/dudect](https://github.com/oreparaz/dudect)中處理percentile的程式碼補進lab0-c的dudect裡即可，注意percentiles的記憶體空間要記得釋放。push後即可看到卡比。 ![image](https://hackmd.io/_uploads/SyEY4Ih26.png) ## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案 ### 研讀[lib/list_sort.c]((https://github.com/torvalds/linux/blob/master/lib/list_sort.c)) #### list_cmp_func_t cmp ```c typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *); ``` - `list_cmp_func_t cmp` - is a pointer to function that takes a pointer to void and two pointers to const struct list_head which are non-NULL, returning int. - 功用：自定義的排序關係 (ordering relation) - 如果要把串列排序成遞增 - return > 0: 把a排在b後面 (a > b) - return <= 0: 把a排在b前面，或是保留相對順序 (a <= b) - 讓`list_sort`是stable sort #### merge - 給定自定義的compare function，合併兩個sublists`a`和`b` - tail使用pointer to pointer的技巧 - 視覺化`merge`裡會發生什麼事，假設現在要合併兩個sorted sublists `a=[1,3]`和`b=[2]`成一個遞增的串列 ```graphviz digraph merge{ rankdir=LR graph [fontname="DFKai-SB"]; node [fontname="DFKai-SB"]; edge [fontname="DFKai-SB"]; subgraph sg1 { nil[label = "NIL",shape=point] head[shape=plaintext] tail[shape=plaintext] tail->head->nil } subgraph sgb{ b[label="b", shape=plaintext] ln2[label = "{<value> 2|{<next> next}}", shape=record] nil2[label = "",shape=point] ln2:next->nil2 b->ln2:value } subgraph sga{ a[label="a" shape=none] ln1[label = "{<value> 1|{<next> next}}", shape=record] ln3[label = "{<value> 3|{<next> next}}", shape=record] nil1[label = "" shape=point] a->ln1:value ln1:next->ln3 ln3:next->nil1 } } ``` - 第一個迭代`cmp(priv, a, b) <= 0`成立： - `head`會指向兩個sublist中最小的節點`a`，並且`head`會成為合併後的第一個節點。 - `tail`從指向`head`轉為指向`a->next` - `a`指向下一個節點 ```graphviz digraph merge{ rankdir=LR graph [fontname="DFKai-SB"]; node [fontname="DFKai-SB"]; edge [fontname="DFKai-SB"]; subgraph sgb{ b[label="b", shape=plaintext] ln2[label = "{<value> 2|{<next> next}}", shape=record] nil2[label = "",shape=point] ln2:next->nil2 b->ln2:value } subgraph sga{ a[label="a" shape=none] ln1[label = "{<value> 1|{<next> next}}", shape=record] ln3[label = "{<value> 3|{<next> next}}", shape=record] nil1[label = "" shape=point] } head[shape=plaintext] tail[shape=plaintext] head->ln1 tail->ln1:next ln1:next->ln3 a->ln3 ln3:next->nil1 } ``` - 第二個迭代`cmp(priv, a, b) > 0`成立： - `*tail = b`: 讓`tail`所指向的`next`指向下一個要加入的節點，這邊是`b` - `tail`從指向`a->next`轉為指向`b->next` - `b`指向下一個節點 ```graphviz digraph merge{ rankdir=LR graph [fontname="DFKai-SB"]; node [fontname="DFKai-SB"]; edge [fontname="DFKai-SB"]; subgraph sgb{ b[label="b", shape=plaintext] ln2[label = "{<value> 2|{<next> next}}", shape=record] nil2[label = "",shape=point] ln2:next->nil2 } subgraph sga{ a[label="a" shape=none] ln1[label = "{<value> 1|{<next> next}}", shape=record] ln3[label = "{<value> 3|{<next> next}}", shape=record] nil1[label = "" shape=point] } head[shape=plaintext] tail[shape=plaintext] head->ln1 tail->ln2:next ln1:next->ln2 a->ln3 ln3:next->nil1 b->nil2 } ``` - 因為`b`已經是NULL，`if (!b)`成立，表示`b`已經沒有結點要合併，直接讓`tail`接上`a`剩下的節點即可。 ```graphviz digraph merge{ rankdir=LR graph [fontname="DFKai-SB"]; node [fontname="DFKai-SB"]; edge [fontname="DFKai-SB"]; subgraph sgb{ b[label="b", shape=plaintext] ln2[label = "{<value> 2|{<next> next}}", shape=record] nil2[label = "",shape=point] } subgraph sga{ a[label="a" shape=none] ln1[label = "{<value> 1|{<next> next}}", shape=record] ln3[label = "{<value> 3|{<next> next}}", shape=record] nil1[label = "" shape=point] } head[shape=plaintext] tail[shape=plaintext] head->ln1 tail->ln2:next ln1:next->ln2 a->ln3 ln2:next->ln3 ln3:next->nil1 b->nil2 } ``` - 可以獲得結論：`head`會是已合併串列的第一個節點，並且是`merge`的回傳值；`tail`從第一個節點加入後指向已合併串列的最後一個節點的`next`。 #### merge_final 合併最後兩個sorted sublists，並且重新連結prev以復原雙重鏈結串列。 #### list_sort - 核心思想：維持$2:1$的sublist size，當有兩個$2^k$大小的sublist，且蒐集到第三個大小為$2^k$的sublist時才進行合併。 - 在排序過程中，所有的串列都是單向鏈結且最後一個節點的next指向NULL。 - 變數`pending`: - is a prev-linked "list of lists" of sorted sublists awaiting further merging. - 排序好的子串列大小必為2的冪 - 不會有超過2個同樣大小的sublist - 變數`count`: - 目前pending lists的元素個數 - 每當增加`count`時，會使某個位元變成1(假設是第k個)，並且第k-1到第0個位元變成0。這時候會合併兩個大小為$2^k$的sublists成一個$2^{(k+1)}$的sublist (counts第一次要到達$2^{(k+1)}$的時候不合併 i.e, 所有位元都是1). ```c do { size_t bits; struct list_head **tail = &pending; /* 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; } /* Move one element from input list to pending */ list->prev = pending; pending = list; list = list->next; pending->next = NULL; count++; } while (list); ``` - 這邊觀察merge前後(如果需要)`count`和`pending`的狀態，以利了解程式碼。紅色標示`bits`會停在哪個位元(i.e., `tail`會停在pending的哪個sorted sublist)，以及下次迭代會合併的兩個sublists大小。假設我們有16個節點要排序： | Iteration | 迭代開始時的 counts | Merge? | 迭代結束時的counts | 迭代結束時的pending | | --------- |:---------------------------:|:------:|:------:| ------------------------------ | | 0 | 0 | X | 1 | 1 | | 1 | 1 | X | 10 | 1-1 | | 2 | 10 | V | 11 | 1-2 | | 3 | 11 | X | 100 | 1-1-2 | | 4 | 100 | V | 101 | 1-2-2 | | 5 | 101 | V | 110 | 1-1-4 | | 6 | 110 | V | 111 | 1-2-4 | | 7 | 111 | X | 1000 | 1-1-2-4 | | 8 | 1000 | V | 1001 | 1-2-2-4 | | 9 | 1001 | V | 1010 | 1-1-4-4 | | 10 | 1010 | V | 1011 | 1-2-4-4 | | 11 | 1011 | V | 1100 | 1-1-2-8 | | 12 | 1100 | V | 1101 | 1-2-2-8 | | 13 | 1101 | V | 1110 | 1-1-4-8 | | 14 | 1110 | V | 1111 | 1-2-4-8 | | 15 | 1111 | X | 10000 | 1-1-2-4-8 | - 把所有節點都加進pending後`do-while`迴圈就會結束，這時候還不一定是完整的sorted list，所以需要把`pending`所有的sorted sublist合併。 ```c /* End of input; merge together all the pending lists. */ list = pending; pending = pending->prev; for (;;) { struct list_head *next = pending->prev; if (!next) break; list = merge(priv, cmp, pending, list); pending = next; } ``` - 假設要排序一個8個節點的鏈結串列`[3 6 7 5 1 4 8 2]`，`do-while`迴圈結束時的狀態是 ```graphviz digraph { rankdir=LR node[shape=box] nil1[label="" shape=none] nil2[label="" shape=none] nil3[label="" shape=none] nil4[label="" shape=none] nil5[label="" shape=none] p[label="pending" shape=plaintext] 2 8 1 4 3 5 6 7 2->8->1->3->nil5 [label=prev] p->2 2->nil1 [label=next] 8->nil2 [label=next] 1->4->nil3 [label=next] 3->5->6->7->nil4 [label=next] {rank=same 2 8 1 3 nil5} } ``` - `for`迴圈結束時的狀態 ```graphviz digraph { rankdir=LR node[shape=box] nil1[label="" shape=none] nil2[label="" shape=none] nil3[label="NULL" shape=none] nil4[label="" shape=none] p[label="pending" shape=plaintext] l[label="list" shape=plaintext] n[label="next" shape=plaintext] 2 8 1 4 3 5 6 7 l->1 p->3 n->nil3 1->3->nil3 [label=prev] 1->2->4->8->nil1 [label=next] 3->5->6->7->nil2 [label=next] {rank=same 1 3 nil3} } ``` - 最後需要用`merge_final`合併`pending`和`list`，並且重新建立`prev`以復原雙重鏈結。 ```c /* The final merge, rebuilding prev links */ merge_final(priv, cmp, head, pending, list); ``` ### 引入list_sort到lab0-c專案 1. 將`list_sort.h`、`list_sort.c`放在專案根目錄下 - `list_sort.h` - 需要補充定義在`/include/linux/compiler.h`的巨集`likely()`、`unlikeky()`以及`u8`。 - 為了支援在`qtest`的使用，修改`list_sort`的宣告。 ```diff + #define likely(x) __builtin_expect(!!(x), 1) + #define unlikely(x) __builtin_expect(!!(x), 0) + typedef uint8_t u8; - __attribute__((nonnull(2,3))) - void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) + __attribute__((nonnull(2))) void list_sort(void *priv, + struct +list_head *head, + bool descend); ``` - `list_sort.c` - 實作compare function - `q_less(a,b)`< 0時表示`a < b`，`a`要優先加入已排序的串列，最後會得到遞增數列。 - `q_greater(a,b)` < 0時表示`a > b`，`a`要優先加入已排序的串列，實作只需要交換`q_less(a,b)`的順序。最後會得到遞減數列。 ```diff + static inline int q_less(void *priv, + const struct list_head *a, + const struct list_head *b) + { + element_t *elem_a = list_entry(a, element_t, list); + element_t *elem_b = list_entry(b, element_t, list); + return strcmp(elem_a->value, elem_b->value); + } + static inline int q_greater(void *priv, + const struct list_head *a, + const struct list_head *b) + { + return q_less(priv, b, a); + } ``` - `list_sort()`需要補上判斷使用哪個compare function的表達式。 ```diff __attribute__((nonnull(2))) void list_sort(void *priv, struct list_head *head, bool descend) { ... + list_cmp_func_t q_cmp = descend ? q_greater : q_less; ... do{ ... if (likely(bits)) { ... - a = merge(priv, cmp, b, a); + a = merge(priv, q_cmp, b, a); ... } ... } while (list); ... for (;;) { ... - list = merge(priv, cmp, pending, list); + list = merge(priv, q_cmp, pending, list); ... } - merge_final(priv, cmp, head, pending, list); + merge_final(priv, q_cmp, head, pending, list); } ``` 3. `qtest.c` - 為了未來可擴充不同排序演算法，事先對演算法排編號，並定義一個靜態全域變`sort`，在`do_sort`裡面就可以依據`sort`的值搭配`switch`來切換 (預設就是`q_sort`)。 - 在`console_init()`裡加上`sort`參數後，在命令列就可以使用`option sort [value]`來取代`sort`的值。 ```diff + #include "list_sort.h" + /* Which sorting algorithm will be used? */ + #define LISTSORT 1 + static int sort = 0; bool do_sort(int argc, char *argv[]) { ... if (current && exception_setup(true)) { - q_sort(current->q, descend); + switch (sort) { + case LISTSORT: + list_sort(NULL, current->q, descend); + break; + default: + q_sort(current->q, descend); + break; + } } ... } static void console_init() { + add_param("sort", &sort, "Specify the sorting algorithm.", NULL); } ``` 5. Makefile的dependency需要加上`list_sort.o` ```diff - linenoise.o web.o + linenoise.o web.o list_sort.o ``` - 發送commit時出現靜態分析失敗，錯誤訊息說在`list_sort.c`的`q_less`出現Null pointer dereference，但`list_entry`是`container_of`的包裝，`0`只是當作運算元而不會真正去存取，因此cppcheck誤判`list_entry`有dereference `0`。 > 參考：[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) ``` list_sort.c:16:25: error: Null pointer dereference: (struct element_t*)0 [nullPointer] element_t *elem_a = list_entry(a, element_t, list); ^ ``` * 查閱[Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf)，提及可以直接使用註解作inline suppression (p.17)： ``` You can suppress a warning aaaa with: // cppcheck-suppress aaaa ``` * 加上`// cppcheck-suppress nullPointer`後能夠順利commit。 ```diff static inline int q_less(void *priv, const struct list_head *a, const struct list_head *b) { + // cppcheck-suppress nullPointer element_t *elem_a = list_entry(a, element_t, list); + // cppcheck-suppress nullPointer element_t *elem_b = list_entry(b, element_t, list); return strcmp(elem_a->value, elem_b->value); } ``` P.S. 在`script/pre-commit.hook`裡也能看到對`queue.c`和`qtest.c`有一樣的抑制。 ### 比較效能 [list_sort論文研讀](https://hackmd.io/@ri_0LQgKRHOwpfTXUW3Rxg/By7w2_Oaa) ## References 1. [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort) 2. [2022q1 Homework1 (lab0) by LJP-TW](https://hackmd.io/@LJP/SyRFuull9#2022q1-Homework1-lab0) 3. [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 4. [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf)