--- tags : linux kernel, jserv, lab0-c --- # 2023q1 Homework1 (lab0) contributed by < [`WangHanChi`](https://github.com/WangHanChi) > ## 作業要求 :::info - [x] 完成實作 queue.c 所有功能 - [x] `make test` 取得 100 分 - [x] 研讀 `lib/list_sort.c` 並將其加入專案中 - [x] 實作新的命令 `shuffle` - [ ] 完成 entropy 相關命令 / 選項 - [x] 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)並且解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理 - [x] 使用 Valgrind 排除 qtest 實作的記憶體錯誤 - [x] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤 - [ ] 實作 `select` system call 來完成 lab0-c 中的 web 功能 ::: ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. $ lscpu | less Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 48 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 12 On-line CPU(s) list: 0-11 Vendor ID: AuthenticAMD Model name: AMD Ryzen 5 5600X 6-Core Processor CPU family: 25 Model: 33 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 0 Frequency boost: enabled CPU max MHz: 4650.2920 CPU min MHz: 2200.0000 BogoMIPS: 7385.75 ``` ## 開發紀錄 ### 以鏈結串列實作佇列 :::info - [x] q_new - [x] q_free - [x] q_insert_head - [x] q_insert_tail - [x] q_remove_head - [x] q_release_element - [x] q_size - [x] q_delete_mid - [x] q_delete_dup - [x] q_swap - [x] q_reverse - [x] q_reverseK - [x] q_sort - [x] q_merge - [x] q_descend ::: ## 開發過程 ### 常用結構 struct #### Linked list_head ```c struct list_head { struct list_head *prev; struct list_head *next; }; ``` #### queue element_t ```c typedef struct { char *value; struct list_head list; } element_t; ``` #### queue_contex_t ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` ### 常用巨集 #### `INIT_LIST_HEAD` ```c static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` 將 `head` 往前指標與往後指標都指向自己, 並且這個 `head` 不會有資料 #### `list_entry` ```c #define list_entry(node, type, member) container_of(node, type, member) ``` 這個巨集主要是藉由 `list` 取得每個 `member` 的起始位置, 與 `container_of` 功能一致 會定義成 `list_entry` 是為了符合 `list` 的風格，關於 `Container_of` 可以參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) ```graphviz digraph container { rankdir=LR; node[shape=record]; compound=true; style=bold; subgraph cluster_0 { container [label = "container" style=filled,color=white]; subgraph cluster_1 { node [shape=record]; element [label="|{|}", style="bold"]; label = "member" } } element -> container[ltail=cluster_1, lhead=cluster_0]; } ``` #### `list_for_each_entry_safe` ```c #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = list_entry((head)->next, __typeof__(*entry), member), \ safe = list_entry(entry->member.next, __typeof__(*entry), member); \ &entry->member != (head); entry = safe, \ safe = list_entry(safe->member.next, __typeof__(*entry), member)) #undef __LIST_HAVE_TYPEOF ``` 這個主要是 `list_for_each_safe` 與 `list_for_each_entry` 兩個巨集的功能整合 - `Entry` 代表可以取用到 `member` 成員的資料 - `safe` 代表它會紀錄下一個 `node` 來方便使用者刪除目前的 `node` ### queue 功能實作 ### **q_new** 根據要求，將回傳一個空的 `list_head` ，可以從 `list.h` 找到 `INIT_LIST_HEAD` 這個函式，並且會把 `next` 與 `prev` 都指向 `head` - 實作流程 1. 使用 `malloc` 分配一個記憶體空間，如果分配失敗就回傳 `NULL` 2. 使用 `INIT_LIST_HEAD` 對剛剛的 `list_head` 進行初始化 3. 回傳初使化的 `list_head` :::spoiler 完整程式碼 ```c struct list_head *q_new() { struct list_head *empty = malloc(sizeof(struct list_head)); if (!empty) return NULL; INIT_LIST_HEAD(empty); return empty; } ``` ::: --- ### **q_free** 根據要求，需要把所有 `queue` 所配置的記憶體釋放掉，也因為會需要走訪整個 `queue` 且又需要釋放記憶體空間，會使用前面提及的巨集 `list_for_each_entry_safe` 來精簡程式碼 會使用到釋放 `queue` 節點的函式 ```c static inline void q_release_element(element_t *e) { test_free(e->value); test_free(e); } ``` - 實作流程 1. 檢查 `list_head` 是否為空，若為空就離開函式 2. 宣告用來走訪 `list` 的迭代器, 當前 `queue` 節點以及當前 `queue` 節點的下一個 3. 使用 `list_for_each_entry_safe` 進行走訪，在每個節點都先釋放 `list_head` ，接著再使用 `q_release_element` 這個函式來釋放這個 `queue`中的資料與自己 4. 釋放 `list_head` 的 `head` :::spoiler 完整程式碼 ```c void q_free(struct list_head *l) { if (!l) return; struct list_head *iter = l; element_t *node, *node_safe; list_for_each_entry_safe (node, node_safe, iter, list) { list_del(&node->list); q_release_element(node); } free(l); } ``` ::: ### **q_insert_head** 根據引數，會得到鏈結串列的 `head` 以及字串 `s`，需要新建一個 `queue` 的節點，並且將字串拷貝給節點的 `value`。 :warning: 字串需要以 `\0` 作為結尾 - 實作流程 1. 檢查 `list_head` 是否為空，若為空就回傳 `NULL` 2. 為新增的 `queue` 節點配置記憶體空間，並且檢查是否配置成功 3. 配置字串 `str` 所需要的大小，並且檢查是否配置成功 4. 複製字串 `s` 給 `str` ，並且把結尾設置為 `\0` 5. 使用 `list.h` 中的函式 `list_add` 將這個新的節點插入到鏈結串列的 `head` ，完成後就回傳 `true` :::info 原本沒有做好的部份 1. 在進行commit 的時候被 **cppcheck** 檢查出有記憶體未被釋放，於是開始檢查這個函式，發現在成功配置 `queue` 的節點後，如果字串 `str` 的配置失敗的情況下，要記得釋放節點 `queue` 再離開函式 2. 原本程式碼呼叫三次 `strlen(s)` ，經過[老師的提醒](https://github.com/WangHanChi/lab0-c/commit/e44265da6283a55d446970003bf3a6449acf09ee)後，修改成使用一個變數儲存這個字串的大小 > 因為 `strlen(s)` 的時間複雜度為 $O(n)$ 如果大量使用且字串長度變長的話，會降低效能 ::: :::spoiler 完整程式碼 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *node = malloc(sizeof(element_t)); if (!node) return false; int str_size = (strlen(s) + 1) * sizeof(char); node->value = malloc(str_size); if (!node->value) { free(node); return false; } memcpy(node->value, s, str_size - 1); node->value[str_size - 1] = '\0'; list_add(&node->list, head); return true; } ``` ::: --- ### **q_insert_tail** 此部份與 `q_insert_head` 的實作方法大同小異，僅需要將 `list_add` 的插入點從原本鏈結串列的**頭**改成**尾端**即可，需要注意的地方也相同 - 實作流程 1. 檢查 `list_head` 是否為空，若為空就回傳 `NULL` 2. 為新增的 `queue` 節點配置記憶體空間，並且檢查是否配置成功 3. 配置字串 `str` 所需要的大小，並且檢查是否配置成功 4. 複製字串 `s` 給 `str` ，並且把結尾設置為 `\0` 5. 使用 `list.h` 中的函式 `list_add` 將這個新的節點插入到鏈結串列的 `tail` ，完成後就回傳 `true` :::spoiler 完整程式碼 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *node = malloc(sizeof(element_t)); if (!node) return false; int str_size = (strlen(s) + 1) * sizeof(char); node->value = malloc(str_size); if (!node->value) { free(node); return false; } memcpy(node->value, s, str_size - 1); node->value[str_size - 1] = '\0'; list_add_tail(&node->list, head); return true; } ``` ::: --- ### **q_remove_head** 根據要求，此函式會將 `queue` 的 `head` 節點移除，並且根據 `bufsize` 把原本節點的資料存進 `*sp` 這個字串中。可以從[Difference between “delete” and “remove”](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove)中得知 **delete** 與 **remove** 這兩個的不同 - 實作流程 1. 檢查 `head` 是否為 `NULL` 以及透過 `list_empty` 這個函式檢查鏈結串列是否為空的 2. 使用 `list_entry` 取得要移除的節點 3. 檢查 bufsize 是否為0，之後再進行字串的拷貝 4. 使用 `list.h` 中提供的 `list_del` 將這個節點移除並且把他的前後兩個節點相連 5. 回傳**指向**我們所**移除節點的指標** :::spoiler 完整程式碼 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *remove_node = list_entry(head->next, element_t, list); if (bufsize) { strncpy(sp, remove_node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&remove_node->list); return remove_node; } ``` ::: --- ### **q_remove_tail** 此部份與 `q_remove_head` 的實作方法大同小異，僅需要將 `list_del` 的移除點從原本鏈結串列的**開頭**改成**尾端**即可，也就是在 `list_entry` 的 `ptr` 部份把 `head->next` 改成 `head->prev`，其他需要注意的地方也相同 - 實作流程 1. 檢查 `head` 是否為 `NULL` 以及透過 `list_empty` 這個函式檢查鏈結串列是否為空的 2. 使用 `list_entry` 取得要移除的節點 3. 檢查 bufsize 是否為0，之後再進行字串的拷貝 4. 使用 `list.h` 中提供的 `list_del` 將這個節點移除並且把他的前後兩個節點相連 5. 回傳**指向**我們所**移除節點的指標** :::info TODO 在聽過老師的 [Code Review](https://www.youtube.com/watch?v=ARnVSDu5j14&ab_channel=.GUTS) 後，學到了一種更簡潔且程式碼共用行高的寫法 ::: :::spoiler 完整程式碼 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *remove_node = list_entry(head->prev, element_t, list); if (bufsize) { strncpy(sp, remove_node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&remove_node->list); return remove_node; } ``` ::: --- ### **q_size** 根據要求，可以使用 `list_for_each` 這個**走訪**的函式來進行實作 - 實作流程 1. 檢查 `head` 是否為 `NULL` 以及透過 `list_empty` 這個函式檢查鏈結串列是否為空的 2. 走訪節點並且每經過一個節點就將計數器＋１ 3. 回傳計數器的值 :::spoiler 完整程式碼 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; int count = 0; list_for_each (head->next, head) { ++count; } return count; } ``` ::: --- ### **q_delete_mid** :::spoiler Leetcode ```c struct ListNode* deleteMiddle(struct ListNode* head){ if(!head || head->next == NULL) return NULL; struct ListNode *rabbit = head, *turtle = head; while(!(rabbit->next == NULL) && !(rabbit->next->next == NULL)){ rabbit = rabbit->next->next; if(rabbit == NULL || rabbit->next == NULL) break; turtle = turtle->next; } turtle->next = turtle->next->next; return head; } ``` ::: 根據要求，將鏈結串列中點刪除。在 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 上我所採用的方式為d快慢指標的方式，設定一個指標 `rabbit` 一次移動2個 `node`，另一個指標 `turtle` 一次移動1個 node 。當 `rabbit` 移動到結尾的時候， `turtle` 的下一個 node 便是中點。於是我將這樣的思路搬到 `q_delete_mid` 上 - 實作流程 1. 檢查 `head` 是否為 `NULL` 以及透過 `list_empty` 這個函式檢查鏈結串列是否為空的 2. 將 `rabbit` 與 `turtlr` 的起點都設定在 `head` 3. 使用 **do-while** 迴圈 - **do** : 先將 `rabbit` 移動兩個 node 後，檢查是否到達鏈結串列的尾端或是回到 `head` ，若尚未到達就將 `turtle` 移動一個 node - **while** : 檢查 `rabbit` 檢查是否到達鏈結串列的尾端或是回到 `head` 4. 將 `turtle` 的下一個 node 使用 `list_entry` 取得佇列的元素，再將其刪除 :::info 發現可以改進的地方 原本使用的快慢指標適用於**環狀**與**非環狀**的 Linekd list，並且他的時間複雜度為 $O(\frac{n}{2})$ 可以近似於 $O(n)$ ，但是他的缺點是 `rabbit` 指標每次移動時會需要讀取兩次 `next` ，而 `turtle` 則需要讀取一次 `next` ，加總來看，每次移動需要花費三個記憶體操作的時間。 但是在**環狀**的 Linked-list 有一種方法也可以在相同的時間複雜度完成要求並且記憶體操作為快慢指標的 $\frac{2}{3}$ 也就是每次移動花費2個記憶體操作時間 實作步驟如下 1. 檢查 `head` 是否為 `NULL` 以及透過 `list_empty` 這個函式檢查鏈結串列是否為空的 2. 設定一個指標 `front` 往 `next` 的方向移動，另一個 `back` 往 `prev` 的方向移動 3. 當兩者交會之際及為中點 4. 再將其刪除即可 修改過後的程式碼也在下方的 完整程式碼 ::: - 圖解說明 - 快慢指標 - 初始位置 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> head [color = purple] turtle -> head [color = green] } ``` - 快指標(rabbit) 移動兩個節點，慢指標(turtle)移動一個節點 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> e2 [color = purple] turtle -> e1 [color = green] } ``` - 最終**快指標(rabbit)** 移動到了尾端之前，**慢指標(turtle)** 所指的就是中間節點 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> e5 [color = purple] turtle -> e3 [color = green] } ```` - 反向迭代 - 初始位置 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front"] back [shape=plaintext;label="back"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> head [color = purple] back -> head [color = green] } ``` - **前指標(front)** 往==前==移動一個節點，**後指標(back)** 往==後==移動一個節點 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front"] back [shape=plaintext;label="back"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> e1 [color = purple] back -> e5 [color = green] } ``` - 當兩個指標**交錯**或是**相遇**時，便可找到中間節點 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front", rank=max] back [shape=plaintext;label="back", rank=max] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> e3 [color = purple] back -> e3 [color = green] } ``` :::spoiler 完整程式碼 - 修改後的 （反向迭代） ```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 *front = head->next, *back = head->prev; if (front == back) return false; while (front != back && front->next != back) { back = back->prev; if (back == front || front->next == back) break; front = front->next; } element_t *node = list_entry(front->next, element_t, list); list_del(&node->list); q_release_element(node); return true; } ``` - 原先的 （快慢指標） ```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 *rabbit = head, *turtle = head; do { rabbit = rabbit->next->next; if (rabbit == head->prev || rabbit == head) { break; } turtle = turtle->next; } while (!(rabbit == head->prev) && !(rabbit == head)); element_t *node = list_entry(turtle->next, element_t, list); list_del(&node->list); q_release_element(node); return true; } ``` ::: --- ### **q_delete_dup** 根據要求，需要將鏈結串列中有重複字串的節點刪除，可以從 [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 中對於題目的敘述得知，`head` 所指的鏈結串列是已經 **Sorted** ，因此只需要考慮重複的節點會是相鄰的即可，也就是下面的第一張圖的情況 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2", color=lightblue2 style=filled] e3 [label="2", color=lightblue2 style=filled] e4 [label="4"] e5 [label="5"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 } ``` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2", color=lightblue2 style=filled] e3 [label="3"] e4 [label="2", color=lightblue2 style=filled] e5 [label="4"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 } ``` - 實作流程 1. 檢查 `head` 是否為 `NULL` , 透過 `list_empty` 這個函式檢查鏈結串列是否為空的以及使用 `list_is_singular` 這個函式來檢查鏈結串列是否只有 `head` 與一個節點 2. 設定一個旗標變數 `flag` 並給予初始值 0，他的用途是檢測字串是否有出現重複 3. 使用 `list_for_each_entry_safe` 來走訪每個節點，使用 `str` 這個變數來儲存下一個節點的字串內容 4. 若是下一個節點不是鏈結串列的 `head` 並且目前節點與下一個節點的字串不一致且 `flag` 為 0 就進行正常迭代，若是 `flag` 為 1，就刪除目前的節點 5. 若是下一個節點的字串與當前節點的字串一致的話，就刪除目前的節點，並且把旗標變數 `flag` 設定為 1，接著進行迭代 6. 完成走訪後回傳 `true` :::spoiler 完整程式碼 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; if (list_empty(head) || list_is_singular(head)) return true; element_t *node, *safe; bool flag = 0; list_for_each_entry_safe (node, safe, head, list) { char *str = list_entry(node->list.next, element_t, list)->value; if (node->list.next != head && !strcmp(str, node->value)) { list_del(&node->list); q_release_element(node); flag = 1; } else if (flag) { list_del(&node->list); q_release_element(node); flag = 0; } } return true; } ``` ::: --- ### **q_swap** 根據要求，需要將鏈結串列中的兩兩一對位置交換，從 [24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) 可以得知，我們僅能交換節點的位置來達成目的，並不可以透過更改節點的字串的指標來完成。 - 實作流程 1. 檢查 `head` 是否為 `NULL`，並且透過 `list_is_sigular` 這個函式來判斷使否需要進行 **swap** 2. 設定兩 `list_head` 的指標，分別指向 `head->next` (以下稱為後者) 與 `head->next->next` (以下稱為前者) 3. 使用 `for-loop` 進行迭代，需要進行以下步驟 1. 使用 `list_del` 將**前者**與鏈結串列斷開連結 2. 將**後者**的 `prev` 指派給**前者**的 `prev` 3. 將**後者**指派給**前者**的 `next` 4. 將**前者**指派給**後者**的 `prev->next` 5. 將**前者**指派給**後者**的 `prev` - 圖解說明 - 設定兩個相鄰的指標，分別為後者 `back = head->next` 與前者 `front = back->next` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 斷開前者 `front` 的與鏈結串列的連結 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 //e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 //e2 -> e1 e1 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 將 `back` 的 `prev` 指派給 `front` 的 `prev` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 //e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 將 `front` 的 `next` 指向 `back` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 將 `front` 指派給 `back` 的 `prev->next` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e2 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 將 `front` 指派給 `back` 的 `prev` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e2 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> e2 e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] } ``` - 完成一次交換，將 `back` 與 `frnot` 都往前移動兩個節點 :::info TODO 在聽過老師的 [Code Review](https://www.youtube.com/watch?v=ARnVSDu5j14&ab_channel=.GUTS) 之後，發現 `q_swap` 與 `q_reverseK` 是可以共用程式碼的，因此想要找時間比較目前的 q_swap 與 直接呼叫 q_reverseK 的效能差異 ::: :::spoiler 完整程式碼 ```c /* Swap every two adjacent nodes */ 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, *next; for (node = head->next, next = node->next; node != head && next != head; node = node->next, next = node->next) { list_del(next); next->prev = node->prev; next->next = node; node->prev->next = next; node->prev = next; } } ``` ::: --- ### **q_reverse** 根據要求，需要將鏈結串列中的節點反向連接，並且不可以使用 `q_insert_head` 或是 `q_remove_head` 這類有 malloc 或是 free 的指令。 可以從 [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) 完成 Single-Linked_list 的解法，再將其延伸到環狀雙向的版本 ```c struct ListNode *reverseList(struct ListNode *head) { if (!head || !head->next) return head; struct ListNode *ret = malloc(sizeof(struct ListNode)); ret->val = head->val; ret->next = NULL; head = head->next; while (head) { struct ListNode *tmp = ret; ret = head; head = head->next; ret->next = tmp; } return ret; } ``` - 實作流程 1. 檢查 `head` 是否為 `NULL`，並且透過 `list_empty`檢查是否為空的鏈結串列 2. 使用 `list_head` 的指標，分別是 `before` , `current` , `after` 3. 使用 `while-loop` 進行迭代，迭代過程中需要進行以下幾個步驟會使用 Graphviz進行表示 - 圖解說明 - 設定三個指標分別是 `before = head->prev`, `current = head`, `after = NULL` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> NULL [color=purple] } ``` - 進入 `while-loop` ，直到 `after` 指到 `head` 為止 - 把 `after` 指向 `current->next` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> e1 [color=purple] } ``` - 把 `current->next` 指派到 `before` ， `current->prev` 指派到 `after` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [color = red;label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [color = red; label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> e1 [color=purple] } ``` - 把 `current` 指派給 `before` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> head [color=green] current -> head [color=orange] after -> e1 [color=purple] } ``` - 把 `after` 指派給 `current` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> head [color=green] current -> e1 [color=orange] after -> e1 [color=purple] } ``` - 接著利用 `while-loop` 迭代即可 :::spoiler 完整程式碼 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *before = head->prev, *current = head, *after = NULL; while (after != head) { after = current->next; current->next = before; current->prev = after; before = current; current = after; } } ``` ::: --- ### **q_reverseK** 根據要求， `reverseK` 是 `reverse` 與 `swap` 的混合體。在一條鏈結串列中，每 **K** 個元素進行 `reverse` ，若是 **K** 的值大於剩下的節點數，就不做任何的改變。 在實作當中會使用到以下兩個在 `list.h` 中所定義的函式 1. **list_cut_position** 這個函式的用途是把一條鏈結串列切成兩條 - 傳入的引數 - head_to : 被切下的 `linked_list` 所要接入的點 - head_from : 被切下的 `linked_list` 的前一個節點 - node : 被切下的 `linked_list` 的點 ```c static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) { struct list_head *head_from_first = head_from->next; if (list_empty(head_from)) return; if (head_from == node) { INIT_LIST_HEAD(head_to); return; } head_from->next = node->next; head_from->next->prev = head_from; head_to->prev = node; node->next = head_to; head_to->next = head_from_first; head_to->next->prev = head_to; } ``` 2. **list_splice** 把 `linled_list` 插入到另外一條中 ```c static inline void list_splice(struct list_head *list, struct list_head *head) { struct list_head *head_first = head->next; struct list_head *list_first = list->next; struct list_head *list_last = list->prev; if (list_empty(list)) return; head->next = list_first; list_first->prev = head; list_last->next = head_first; head_first->prev = list_last; } ``` 3. **list_splice_init** ```c static inline void list_splice_init(struct list_head *list, struct list_head *head) { list_splice(list, head); INIT_LIST_HEAD(list); } ``` - 實作流程 1. 檢查 `head` 是否為 `NULL`，並且透過 `list_empty` 檢查是否為空的鏈結串列以及使用 `list_is_singular` 確保鏈結串列裡面有不只一個節點 2. 因為要使用 `list_cut_position` 這個函式，所以我們先使用 `LIST_HEAD` 這個巨集建立一個新的 list_head 3. 因為會將鏈結串列切開，所以要使用 `list_for_each_safe` 這個函式來完成迭代 4. 設定一個變數 `num`，當 `num` 等於 `k` 的時候，就執行剪下 `K` 個節點，並且 `reverse` ，最終再將其接回原本的點。 5. 重複步驟(4)直到鏈結串列的尾端 - 圖解說明 - 主要講解置換的過程，首先先宣告三個指標 `node`, `safe`, `tmp = head` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head ->e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 tmp -> head } ``` - 利用巨集 `LIST_HEAD` 建立一個新 `list-head` 的 `head` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head } ``` - 假設 `k` 目前為 3 ，也就是 `list_for_each_safe` 進行三次迭代才會開始進行切斷...等等動作，下圖展示的是第三次迭代 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] node0 -> e3 [color=green] safe -> e4 [color=purple] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head } ``` - 首先先使用巨集切出第二條鏈結串列 `list_cut_position(&new_head, tmp, node);`，從 `tmp` 得下一個節點到 `node` 切下後貼去 `new_head` ，可以看到下面變成兩條鏈結串列了 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e4 e1 -> e2 e2 -> e3 e3 -> new_head e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> e1 node0 -> e3 [color=green] safe -> e4 [color=purple] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> head e3 -> e2 e2 -> e1 e1 -> new_head new_head -> e3 // pointer 初始化 tmp -> head } ``` - 將 `new_head` 進行 `reverse` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; //head [label="Head"] new_head [label="new_head"] e1 [label="3"] e2 [label="2"] e3 [label="1"] //e4 [label="4"] //e5 [label="5"] //e6 [label="6"] //e7 [label="7"] node0 [shape=plaintext;label="node"] //safe [shape=plaintext;label="safe"] //tmp [shape=plaintext;label="tmp"] // next 方向 //head -> e4 e1 -> e2 e2 -> e3 e3 -> new_head //e4 -> e5 //e5 -> e6 //e6 -> e7 //e7 -> head new_head -> e1 node0 -> e1 [color=green] //safe -> e4 [color=purple] // prev 方向 //head -> e7 //e7 -> e6 //e6 -> e5 //e5 -> e4 //e4 -> head e3 -> e2 e2 -> e1 e1 -> new_head new_head -> e3 // pointer 初始化 //tmp -> head } ``` - 將 `new_head` 插入 `tmp` 之後，再初始化 `new_head` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e3 e3 -> e2 e2 -> e1 e1 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e1 e1 -> e2 e2 -> e3 e3 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head safe -> e4 node0 -> e3 } ``` - 最後再將 `tmp` 移動到 `safe` 的前一個，便完成了一次的迭代 :::spoiler 完整程式碼 ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *node, *safe, *tmp = head; LIST_HEAD(new_head); int num = 0; list_for_each_safe (node, safe, head) { ++num; if (num == k) { list_cut_position(&new_head, tmp, node); q_reverse(&new_head); list_splice_init(&new_head, tmp); num = 0; tmp = safe->prev; } } } ``` ::: --- ### **q_sort** 根據要求，需要將鏈結串列進行由小到大排序。這題參考自 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf) 中的`Merge_Sort` 以及 [陳日昇](https://hackmd.io/@Risheng/linux2022-lab0) 同學的實作。 - 實作流程 - **q_merge** 1. 檢查 `head` 是否為 `NULL`，並且透過 `list_empty` 檢查是否為空的鏈結串列 2. 將環狀結構斷開 3. 把 `head->next` 作為 `merge_divide` 的引數以及函式回傳值 4. 當由有到大後，每個節點的 `prev` 都是亂掉的以及環狀結構尚未接回，因此要走訪每個節點，並且把 `prev` 都接上，最後再把尾端接回 `head` - **merge_divide** 1. 檢查 `head` 是否為 `NULL`，並且檢查 `head->next` 是否 `NULL` ，若是就直接回傳 `head` 2. 使用上面所使用過的 **快慢指標** 來找到中點 3. 將中點切開成兩條獨立的 `list_head` ，再呼叫自己進行迭代 4. 將每個節點都切開後傳入 `merge_two_nodes` - **merge_two_nodes** 1. 利用 **indirect pointer** 來進行每個節點的走訪 2. 逐一比較 `left` 與 `right` 的字串大小 3. 最後若是其中一方已經到盡頭，便會直接把餘剩的一方接在排序完的尾端 - 圖解說明 `merge_divide` 這個函式主要在進行下面**橘色**框框的動作，而 `merge_two_nodes` 是在進行**藍色**及**綠色**框框 ```graphviz digraph G { compound=true node[shape=box, height=.1];sorted_1 sorted_2 sorted_3 sorted_4 sorted_5 sorted_6 sorted_7 sorted_8; node[shape=record, height=.1];input result divide_41 divide_42 divide_21 divide_22 divide_23 divide_24 merge_21 merge_22 merge_23 merge_24 merge_41 merge_42; input[label="<f0>2|<f1>5|<f2>4|<f3>6|<f4>8|<f5>1|<f6>7|<f7>3"] result[label="<f0>1|<f1>2|<f2>3|<f3>4|<f4>5|<f5>6|<f6>7|<f7>8"] divide_41[label="<f1>2|<f2>5|<f3>4|<f4>6"] divide_42[label="<f1>8|<f2>1|<f3>7|<f4>3"] divide_21[label="<f0>2|<f1>5"] divide_22[label="<f0>4|<f1>6"] divide_23[label="<f0>8|<f1>1"] divide_24[label="<f0>7|<f1>3"] sorted_1[label="1"] sorted_2[label="2"] sorted_3[label="3"] sorted_4[label="4"] sorted_5[label="5"] sorted_6[label="6"] sorted_7[label="7"] sorted_8[label="8"] merge_21[label="<f0>2|<f1>5"] merge_22[label="<f0>4|<f1>6"] merge_23[label="<f0>1|<f1>8"] merge_24[label="<f0>3|<f1>7"] merge_41[label="<f1>2|<f2>4|<f3>5|<f4>6"] merge_42[label="<f1>1|<f2>3|<f3>7|<f4>8"] subgraph cluster_0 { style=filled; color="#ef6548"; label="divide"; divide_pad[label="----------------------", style=invis] divide_pad -> divide_23[style=invis] input -> divide_41 input -> divide_42 divide_41 -> divide_21 divide_41 -> divide_22 divide_42 -> divide_23 divide_42 -> divide_24 } divide_21:f0 -> sorted_2 divide_21:f1 -> sorted_5 divide_22 -> sorted_4 divide_22 -> sorted_6 divide_23:f0 -> sorted_8 divide_23:f1 -> sorted_1 divide_24:f0 -> sorted_7 divide_24:f1 -> sorted_3 subgraph cluster_1 { style=filled; color="#a6cee3"; label="sorted lists"; sorted_1; sorted_2; sorted_3; sorted_4; sorted_5; sorted_6; sorted_7; sorted_8; } sorted_2 -> merge_21:f0 sorted_5 -> merge_21:f1 sorted_4 -> merge_22:f0 sorted_6 -> merge_22:f1 sorted_8 -> merge_23:f1[constraint=false] sorted_1 -> merge_23:f0 sorted_7 -> merge_24:f1 sorted_3 -> merge_24:f0 subgraph cluster_2 { style=filled; color="#b2df8a"; label="merge"; merge_pad[label="--------------------", style=invis] rank=same; merge_41; merge_pad; merge_42 rank=same; merge_41; merge_42; merge_pad; merge_22 -> merge_pad[style=invis] merge_23 -> merge_pad[style=invis] merge_pad -> result[style=invis] merge_21 -> merge_41 merge_22 -> merge_41 merge_23 -> merge_42 merge_24 -> merge_42 merge_41 -> result merge_42 -> result } } ``` :::spoiler 完整程式碼 ```c struct list_head *merge_two_nodes(struct list_head *left, struct list_head *right) { struct list_head *new_head = NULL, **indirect = &new_head, **iter = NULL; for (; left && right; *iter = (*iter)->next) { iter = strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) >= 0 ? &right : &left; *indirect = *iter; indirect = &(*indirect)->next; } *indirect = (struct list_head *) ((uint64_t) left | (uint64_t) right); return new_head; } struct list_head *merge_divide(struct list_head *head) { if (!head || !head->next) return head; struct list_head *rabbit = head, *turtle = head, *middle; for (; rabbit && rabbit->next; rabbit = rabbit->next->next, turtle = turtle->next) ; middle = turtle; // cut off the link turtle->prev->next = NULL; struct list_head *left = merge_divide(head); struct list_head *right = merge_divide(middle); return merge_two_nodes(left, right); } /* Sort elements of queue in ascending order */ void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; // cut off the link head->prev->next = NULL; head->next = merge_divide(head->next); struct list_head *before = head, *after = head->next; for (; after != NULL; after = after->next) { after->prev = before; before = after; } before->next = head; head->prev = before; } ``` ::: --- ### **q_descend** :::spoiler Leetcode 解法 ```c struct ListNode *reverseList(struct ListNode *head) { if (!head || !head->next) return head; struct ListNode *ret = malloc(sizeof(struct ListNode)); ret->val = head->val; ret->next = NULL; head = head->next; while (head) { struct ListNode *tmp = ret; ret = head; head = head->next; ret->next = tmp; } return ret; } struct ListNode* removeNodes(struct ListNode* head){ head = reverseList(head); struct ListNode *node = head, *node_next = node->next; while(node_next != NULL){ if(node_next->val >= node->val){ node = node->next; node_next = node_next->next; } else { node->next = node_next->next; node_next = node_next->next; } } head = reverseList(head); return head; } ``` ::: 這題 leetcode 解法是參考自 [Youtube](https://youtu.be/SicFs7BGDyY?t=144) 影片中所講解的第二種思路(Approach 2) ![](https://i.imgur.com/tfxDf1S.png) 由於 Leetcode 是單向的 `linked_list` 因此由左邊比較到右邊較為複雜，因此這題的關鍵點就在於 **reverse** ，只要先將原本的鏈結串列 `reverse` ，就可以方便地進行比較所有節點大小的動作，最後再將鏈結串列 `reverse` 即可達成要求 而實作 `q_descend` 的時候就更為方便，因為使用的是環狀雙向鏈結串列，可以不須經過反向，直接透過 `prev` 操作即可，以下為實作流程 - 實作流程 1. 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列 2. 使用 `list_head` 的指標 `node` 指向 `head->prev` 以及 `node_prev` 指向 `node->prev` 3. 利用 `list_entry` 各別取得佇列內的資料 4. 接著反向走訪所有節點，假如 `ndoe` 的字串比 `node_prev` 的字串還小的時候，就不進行移除節點，將兩個節點都分別往 `prev` 的方向移動一格 5. 若是`ndoe` 的字串比 `node_prev` 的字串還大，就將 `node_prev` 移除(**delete**)，然後再進行下一輪的走訪 :::spoiler 完整程式碼 ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; int num = 0; struct list_head *node = head->prev, *node_prev = node->prev; element_t *que = list_entry(node, element_t, list); element_t *que_prev = list_entry(node_prev, element_t, list); while (&que_prev->list != head) { if (strcmp(que->value, que_prev->value) < 0) { que_prev = list_entry(que_prev->list.prev, element_t, list); que = list_entry(que->list.prev, element_t, list); ++num; } else { list_del(&que_prev->list); q_release_element(que_prev); que_prev = list_entry(que->list.prev, element_t, list); } } return ++num; } ``` ::: --- ### **q_merge** 根據要求，**傳入的 `head` 為 `queue_contex_t` 的 `head` ，因此也會需要將節點往 `next` 移動一格才開始存取每個`queue` 的 `head`**。 他可以視作 merge sort 的延伸版，透過已經實作好的merge_two_nodes 這個函式，可以把兩段長度不相同的鏈結串列由小至大合併，因此只需要將每個 `queue` 的 `head` 都加入後便可以把所有的點併入一條 - 實作流程 1. 檢查 `head` 是否為 `NULL`，並且透過 `list_empty` 檢查是否為空的鏈結串列 2. 取得第一條 `queue` 的節點個數，再走訪每個 `queue_contex_t` 的 `q` 3. 在每個走訪的過程，都先將每條鏈結串列變成非環狀的，再使用 `merge_two_nodes` 這個函式將兩條鏈結串列合併成一條 4. 使用 `INIT_LIST_HEAD` 將每個空的 `head` 都指向自己，避免出錯 5. 最後的作法與 `q_sort` 的實作一樣，需要將 每個節點的`prev` 都接回，並且把它接回環狀的 :::spoiler 完整程式碼 ```c int q_merge(struct list_head *head) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head || list_empty(head)) return 0; int num = 0; struct list_head *master = list_entry(head->next, queue_contex_t, chain)->q; num += q_size(master); master->prev->next = NULL; struct list_head *node = head->next->next; while (node != head) { struct list_head *slave = list_entry(node, queue_contex_t, chain)->q; num += q_size(slave); slave->prev->next = NULL; master->next = merge_two_nodes(master->next, slave->next); INIT_LIST_HEAD(slave); node = node->next; } struct list_head *before = master, *after = master->next; for (; after != NULL; after = after->next) { after->prev = before; before = after; } before->next = master; master->prev = before; return num; } ``` ::: --- ## 研讀 Linux 核心原始程式碼的 `lib/list_sort.c` 先去取得 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)，接著開始研讀程式碼，因為怕篇幅太長超過限制，因此，我將研讀的筆記額外放在這[Lab0 lib/list_sort.c 學習筆記](https://hackmd.io/Jp_0L3KWQoqSHm7c30M_zw?view) ### 將 list_sort.c 加入專案 接下來要將 list_sort 加入專案中 1. 將 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 加入至與 `queue.c` 同個層級的目錄 2. 將 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 這個標頭檔也加入跟原始檔一樣層級的目錄下 3. 因為會使用到 `unlikely` 與 `likely` 這樣的巨集，因此需要將 [compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中的這兩行加入 `list_sort.h` 中 ```c # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) ``` 4. 在 `list_sort.c` 的檔案中，有使用到 `u8` 這樣的型別，所以也將其以巨集的方式定義在 `list_sort.h` 下 ```c #include <stdint.h> typedef uint8_t u8; ``` 5. 接著修改 `Makefile` 中 OBJS，新增一個 `list_sort.o` ```diff=40 OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o + linenoise.o web.o list_sort.o ``` 6. 最後修改 `qtest.c` 這個檔案 - 加入 `include "list_sort.h"` - 設定一個變數決定是否使用 list_sort ```c static int use_list_sort = 0; ``` - 編寫一個比較的函式 ```c static int cmp(void* priv, const struct list_head *l1, const struct list_head *l2) { return strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value); } ``` - 根據該該所設定的變數決定是否使用 list_sort ，於是著手修改 `do_sort` 中的執行 sort的部份 ```c if (current && exception_setup(true)) use_list_sort ? list_sort(NULL, current->q, cmp): q_sort(current->q); exception_cancel(); ``` - 最後在將我們所將入的參數使用 `add_param` 加入 `help` 的選單中 ```c add_param("listsort", &use_list_sort, "Use the sort which is made by linux kernel developers", NULL); ``` 可以看到下方的 `option` 有多了 `listsort` 這個選項 ``` cmd> help Commands: # ... | Display comment dedup | Delete all nodes that have duplicate string descend | Remove every node which has a node with a strictly greater value anywhere to the right side of it dm | Delete middle node in queue free | Delete queue help | Show summary ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1) it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1) log file | Copy output to file merge | Merge all the queues into one sorted queue new | Create new queue next | Switch to next queue option [name val] | Display or set options. See 'Options' section for details prev | Switch to previous queue quit | Exit program reverse | Reverse queue reverseK [K] | Reverse the nodes of the queue 'K' at a time rh [str] | Remove from head of queue. Optionally compare to expected value str rt [str] | Remove from tail of queue. Optionally compare to expected value str show | Show queue contents shuffle | Shuffle all the nodes in the queue in a random method size [n] | Compute queue size n times (default: n == 1) sort | Sort queue in ascending order source | Read commands from source file swap | Swap every two adjacent nodes in queue time cmd arg ... | Time command execution web [port] | Read commands from builtin web server Options: echo 1 | Do/don't echo commands entropy 0 | Show/Hide Shannon entropy error 5 | Number of errors until exit fail 30 | Number of times allow queue operations to return false length 1024 | Maximum length of displayed string listsort 0 | Use the sort which is made by linux kernel developers malloc 0 | Malloc failure probability percent simulation 0 | Start/Stop simulation mode verbose 4 | Verbosity level ``` :::info 貼心提醒(x) 採雷實錄(o) 在使用 `clang-format -i` 的時候，記得不要對 Makefile 使用 ::: ### 安裝 perf 由於我的電腦是這學期重灌到 **ubuntu-22.04** 的，所以效能測試工具 [perf](https://zh.wikipedia.org/zh-tw/Perf) 需要重新下載，跟著[老師的筆記](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg)一步一步即可，不過這邊要特別注意，我們一般安裝的 `kernel.perf_event_paranoid` 會是 **4** ，可以透過 `$ cat /proc/sys/kernel/perf_event_paranoid` 來進行查看，但是我們如果想要把權限全部打開的話，必須使用這條指令 `$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"` 來將權限值設為 **-1** 再來可以輸入 `$ perf top` 來確認自己是否有拿到最高權限值 ### 進行效能比較 在 trace 這個目錄下創建一個新的測試命令集 `trace-sort.cmd` ，裡面的測試如下 ``` # Test performance of sort betweem q_sort() and list_sort() # You can modify the option listsort and the RAND to meet your need option listsort 0 new it RAND 500000 time sort time ``` 接著執行它 `$ ./qtest -f traces/trace-sort.cmd ` 就可以得到 ```shell $ ./qtest -f traces/trace-sort.cmd # Test performance of sort betweem q_sort() and list_sort() # You can modify the option listsort and the RAND to meet your need l = [] l = [uivpdik xfbkwkz gmbzaf ysygwrx vkssukdk ongishsxd jhxbjqsny dmxgkd iocxyll adojbg btznx equevnb fpxfr ldurei mbolzsokz gaviuvdl ylifpbvs cawtwi mxyyk ytova aihdgcca dhhcjjyvb bxldmra iovvqwa ftogdizpo ouham nlbkp mwwxth ihpymm rxxlvju ... ] Elapsed time = 0.167, Delta time = 0.167 l = [aaaaizu aaabrr aaabvyd aaacf aaacgxla aaacpcf aaacqqfg aaacwmp aaadqam aaaeo aaahahyow aaahi aaajzhtau aaamxvbgy aaano aaaoge aaaqpjab aaaryjsxv aaatohdfj aaatolb aaavjefox aaavtfpgc aaavuwipm aaawrad aaaxx aaaycpd aaayh aaaykau aaazhb aaaztnh ... ] Elapsed time = 0.601, Delta time = 0.435 Freeing queue ``` 可以看到我們使用了 qtest 中的 `time` 功能，來取得我們執行 `sort` 所花費的時間，最後的那個 Delta time 就是我們所希望得到的 接著開始比較 `q_sort` 與 `list_sort` 這兩個排序的效能差別 我們分別測試資料比數從 10 萬筆資料到 100 萬筆資料 並且重複做三次 | 資料數 | 1. q_sort() | 2. q_sort() | 3. q_sort() | 平均 | | -------- | ----------- | ------------ | ------------ | ----- | | 10 萬筆 | 0.038 | 0.036 | 0.039 | 0.038 | | 20 萬筆 | 0.095 | 0.089 | 0.096 | 0.093 | | 30 萬筆 | 0.198 | 0.192 | 0.218 | 0.203 | | 40 萬筆 | 0.313 | 0.309 | 0.340 | 0.321 | | 50 萬筆 | 0.440 | 0.427 | 0.491 | 0.453 | | 60 萬筆 | 0.556 | 0.592 | 0.616 | 0.588 | | 70 萬筆 | 0.697 | 0.702 | 0.762 | 0.720 | | 80 萬筆 | 0.846 | 0.831 | 0.901 | 0.859 | | 90 萬筆 | 0.975 | 0.960 | 0.996 | 0.976 | | 100 萬筆 | 1.123 | 1.098 | 1.119 | 1.113 | | 資料數 | 1. list_sort() | 2. list_sort() | 3. list_sort() | 平均 | | -------- | -------------- | --------------- | --------------- | ----- | | 10 萬筆 | 0.023 | 0.023 | 0.023 | 0.023 | | 20 萬筆 | 0.069 | 0.064 | 0.060 | 0.064 | | 30 萬筆 | 0.129 | 0.124 | 0.132 | 0.128 | | 40 萬筆 | 0.213 | 0.220 | 0.216 | 0.216 | | 50 萬筆 | 0.296 | 0.290 | 0.290 | 0.290 | | 60 萬筆 | 0.411 | 0.401 | 0.392 | 0.401 | | 70 萬筆 | 0.498 | 0.507 | 0.505 | 0.503 | | 80 萬筆 | 0.645 | 0.611 | 0.600 | 0.619 | | 90 萬筆 | 0.708 | 0.680 | 0.708 | 0.699 | | 100 萬筆 | 0.805 | 0.808 | 0.791 | 0.801 | ![](https://i.imgur.com/0wUVGJP.png) 可以看到他 list_sort 比起 q_sort 的效能大約都好了 30% ~ 40% 接下來使用 `perf` 這個工具來看更詳細的對比資料 根據[老師的筆記](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg)，可以使用以下指令來取得 `cache-misses`, `cache-references`, `instructions`, `cycles` 這些項目的資訊 `$ perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./qtest -f trace/trace-sort.cmd` 這條指令會重複跑**10**次 `./qtest -f trace/trace-sort.cmd` 這個命令，並且將我們所設定要取得的資訊統計出來，如下面所列 ``` Performance counter stats for './qtest -f traces/trace-sort.cmd' (10 runs): 20,633,385 cache-misses # 34.793 % of all cache refs ( +- 0.15% ) 58,757,193 cache-references ( +- 0.76% ) 2,275,963,009 instructions # 0.93 insn per cycle ( +- 0.02% ) 2,400,840,346 cycles ( +- 0.57% ) 0.53341 +- 0.00388 seconds time elapsed ( +- 0.73% ) ``` 接著，我因為覺得每次都要打這麼長的命令很不人性化，因此我將它加入 `Makefile` 裡面 ```makefile export cycle ?= 5 perf: qtest perf stat --repeat $(cycle) -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-sort.cmd ``` 這樣以後只要輸入 `make perf` 就可使用了 接著來比較兩者的差異在 **50萬** 比資料下的狀況 | 項目 | q_sort | list_sort | | -------------------- | ------------- | ------------- | | cache-misses | 27,057,256 | 20,610,754 | | cache-references | 75,094,812 | 59,647,674 | | % of all caches refs | 35.770 % | 34.833 % | | instructions | 2,292,705,155 | 2,276,127,334 | | cycles | 3,545,449,526 | 2,488,046,136 | | insn per cycle | 0.70 | 0.95 | 可以看到 list_sort 在 cache-misses 的數量上少了將近 **35%** ，這樣該就是老師在[作業提示](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e)這邊所說的，linux kernel 開發者有針對 `cache` 來做演算法的設計，因此才可以減少這麼多的 cache-misses，並且同時也減少了 instructions ，所以 list_sort 的 IPC 會比起 q_sort 好 **35%** --- ## 在 `qtest` 提供新的命令 `shuffle` 根據 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法的概念，可以得知該演算法的實作步驟分為以下幾點 - 實作步驟 1. 取得一個 **N** 個的鏈結串列，並且運用 `q_size` 取的節點個數 2. 隨機產生一個介於1到剩餘節點的數字 **R** 3. 從最小的開始數，將第 **R** 個數字移動到自己這條鏈結串列的尾端 5. 重複 (2) 到 (3) 的步驟 6. 當節點個數 == **0** 的時候，便是 `shuffle` 完成之際 觀察 `lab0-c` 的檔案結構可以知道如果要加入新的命令需修改 `qtest.c` 這個檔案，首先先實作 `q_shuffle` 這個功能 ```c /* Shuffle all the nodes in the queue in a random method */ void q_shuffle(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; int num = q_size(head); struct list_head *node = head->next; while (num != 0) { // step 2 int random = rand() % num; for (int i = 0; i < random; ++i) node = node->next; // step 3 list_del(node); list_add_tail(node, head); node = head->next; --num; } } ``` 當主要的功能實作完成之後，再來需要的就是將執行他的函式實作出來，這邊主要進行的就是**引數**的檢查, 還有啟用 `set_noallocate_mode` 這個功能後，就開始執行 `q_shuffle` ，再來就是判斷是否執行超過時間，最後再將 `set_noallocate_mode` 取消啟用即可，回傳值使用 `q_show(3)` 接著開始研究 `q_show` 這個函式，假如們希望印出正確的回應 ( 例如 `l = [ a b c d e ]` ) ，就必須要通過像是雙向環狀或是非 `NULL` 這樣的條件，才可以透過**第893行**將正確的值輸出 ```c=867 static bool q_show(int vlevel) { bool ok = true; if (verblevel < vlevel) return true; int cnt = 0; if (!current || !current->q) { report(vlevel, "l = NULL"); return true; } if (!is_circular()) { report(vlevel, "ERROR: Queue is not doubly circular"); return false; } report_noreturn(vlevel, "l = ["); struct list_head *ori = current->q; struct list_head *cur = current->q->next; if (exception_setup(true)) { while (ok && ori != cur && cnt < current->size) { element_t *e = list_entry(cur, element_t, list); if (cnt < BIG_LIST_SIZE) { report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value); if (show_entropy) { report_noreturn( vlevel, "(%3.2f%%)", shannon_entropy((const uint8_t *) e->value)); } } cnt++; cur = cur->next; ok = ok && !error_check(); } } ... } ``` 經過上述，我們可以實作出 `do_shuffle` 這個函式 ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } set_noallocate_mode(true); if (current && exception_setup(true)) q_shuffle(current->q); exception_cancel(); set_noallocate_mode(false); return q_show(3); } ``` ## 使用 Valgrind 排除 qtest 實作的記憶體錯誤 首先研讀了老師的作業提示[以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b)，可以知道 Valgrind 這個工具的強大 並且我們只要在終端機輸入 ```shell $ make valgrind ``` 就可以執行 Makefile 內預先寫好的腳本，以下是 Makefile 中關於 valgrind 的部份 ```makefile valgrind_existence: @which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1) valgrind: valgrind_existence # Explicitly disable sanitizer(s) $(MAKE) clean SANITIZER=0 qtest $(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX)) cp qtest $(patched_file) chmod u+x $(patched_file) sed -i "s/alarm/isnan/g" $(patched_file) scripts/driver.py -p $(patched_file) --valgrind $(TCASE) @echo @echo "Test with specific case by running command:" @echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>" ``` 可以看上面的 `valgrind_existence` 是用來檢查是否安裝了 valgrind 接著繼續看到 `valgrind` 的腳本，可以看到它會利用 `mktemp` 建立一個暫存的檔案，接著複製檔案過去，再幫該檔案加上所有使用者( +a )都可以執行( +x )的權限 :::info 這邊我認為在 `chmod u+x $(patched_file)` 這行指令應該要使用 root 權限，從[鳥高私房菜-改變權限, chmod](https://linux.vbird.org/linux_basic/centos7/0210filepermission.php) 這篇文章中的範例來看，要執行 chmod 操作是需要切換到 root 身份的。所以我覺得這行應該改為 `sudo chmod u+x $(patched_file)` 會比較恰當，或是在執行 make 腳本時要使用 `sudo make valgrind` 。 > 提交 pull request? > :notes: jserv 後來詳細觀察了檔案權限以及程式碼，發現是我搞錯了，加上 `sudo` 會使得編譯出的檔案變成僅限 root 權限的，在之後的刪除 make clean 會產生問題，下次會再更加謹慎的。[錯誤的提交](https://github.com/sysprog21/lab0-c/pull/132) ::: 接著執行 `make valgrind` ，可以發現執行的速度下降了許多，符合老師所提及的 最後發現並沒有洩漏的記憶體 接著使用 Massif 視覺化工具 可以在 valgrind 使用的參數列表中加入 `--tool=massif` ``` $ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd ``` 就可以得到一張 massif.out.XXXXX，其中的 XXXXX 會是一串數字 接著要去[massif-visualizer](https://apps.kde.org/zh-tw/massif-visualizer/) 安裝 [massif-visualizer桌面版](appstream://org.kde.massif-visualizer.desktop) 接著輸入 ``` $ massif-visualizer massif.out.XXXXX ``` 就可以得到 massif 記憶體分析的圖了! ![](https://i.imgur.com/33doFD3.png) --- ## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤 根據 Makefile 中關於 Sanitizer 的部份，可以看到 ```makefile # Enable sanitizer(s) or not ifeq ("$(SANITIZER)","1") # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common LDFLAGS += -fsanitize=address endif ``` 若是執行 `make` 的時候一起加上了 SANITIZER=1 這樣的參數就可以開啟 Sanitizer，來檢查程式碼 :::info :warning: Sanitizer 與 Valgrind 是不可以同時使用的，所以假如在 `make` 的時候有加上了`SANITIZER=1` 這樣的參數的話，就要記得先執行 `make clean` 清除先前所編譯好的才能正常使用 Valgrind ::: SANITIZER 使用步驟如下: > $ make SANITIZER=1 > $ make test // 若是沒有報錯就可以清除 > $ make clean --- ### 研讀論文〈Dude, is my code constant time?〉 #### 論文筆記 [論文連結](https://eprint.iacr.org/2016/1123.pdf) 原本針對程式碼的偵測工具，是針對不同的硬體所設計的，因此換了一個平台，例如不同的 CPU 或是 micro-code 更新，原本的工具就沒有辦法使用了，為此，這篇文章提出了基於統計機率的方法來檢測程式碼。 論文使用的方法是 **TIMING LEAKAGE DETECTION**，首先測量兩個不同輸入數據類型的執行時間，然後檢查這兩個時間分布是否在統計上不同 1. Measure execution time 反覆測量我們所使用的函數 (在 lab0-c 中就是 `it`, `ih`, `rh` 及 `rt`) 對屬於兩個不同輸入資料類型的輸入的執行時間。 - Classes definition 這邊主要在定義所使用的類別為兩種不同類型的，第一種為固定的資料類別，另外一種為隨機的資料類別 - Cycle counters 使用 CPU 自帶的週期計數器，在 X86-64 平台下可以使用 `RDTSC` ，而在 aarch64 平台下可以使用 `mrs` 個暫存器搭配內嵌組合語言的方式來呈現，詳情可以看[這裡](https://github.com/sysprog21/lab0-c/blob/master/dudect/cpucycles.h) - Environmental conditions 為了最小化環境變化對結果的影響，每次測量都對應於一個隨機選擇的類別，**特別注意 ： 類別分配和輸入準備任務在測量階段之前完成** 2. Apply post-processing - Cropping 典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量不準確、被作業系統或其他外部活動中斷造成的。在這種情況下，可以透過裁剪測量的數據來避免誤差 - Higher-order preprocessing 3. Apply statistical test - t-test 使用 [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 這個方法進行檢測，這個測試方法也是 dudect 所使用的 - Non-parametric tests 虛無假說可以參考[這裡](https://en.wikipedia.org/wiki/Null_hypothesis) #### 提出的改進方法 研讀 [lab0-c/dudect 筆記](https://hackmd.io/@wanghanchi/B1WRwrCCi) [oreparaz/dudect](https://github.com/oreparaz/dudect/tree/master/src/dudect.h) 可以知道從原始的實作來看，**PERCENTILE** 可以去除掉極端值，但是在 leb0-c 並沒有相關的實作，因此這會是其中一個改變的方向。 再來是上面所提到的 **Classes definition** ，在 lab0-c 的實作中， 固定資料的字串是用 0 來進行填充的，但是 0 在 ascii 碼中代表的是 '\0' ，這與字串的結尾符號一致，所以這可能會導致問題。 再來是在 measure 這個函式中，使用了兩個 int 來保存插入或是移除前後的個數是否為正確的，但是這樣的檢查僅只有確認個數，但卻沒有明確知道它是否為插入在頭尾...等等，因此這也是一個問題 故目前發現的問題為 1. PERCENTILE 2. 隨機 / 固定生成字串的結尾符號 3. q_size() 的使用不恰當 #### 根據上述所提的問題，實施相對應的實作 - PERCENTILE 首先因為老師原本的參數是散裝的，但在原本的 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中是使用 struct 來包住許多的參數 ```c int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t)); int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t)); int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t)); uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t)); uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t)); ``` 所以我把上面替換成下面，這邊的 struct 也與原本的有所不同，原本的 ticks 是儲存在同一個陣列的，但我改成像是原本的定義，分成 before_ticks 與 after_ticks 。 ```c typedef struct { int64_t *before_ticks; int64_t *after_ticks; int64_t *exec_times; uint8_t *input_data; uint8_t *classes; dudect_config_t *config; ttest_ctx_t *ttest_ctxs[DUDECT_TESTS]; int64_t *percentiles; } dudect_ctx_t; ``` 同時也新增了關於 percenteils 相關的巨集以及函式 特別注意，因為我把上述這些參數都改成 struct 了，所以相關函式的引數都要進行更改。 - 隨機 / 固定生成字串的結尾符號 可以看到原本的老師對於 fix string 的部份是以 0 來進行 memset 的填充，但是在 ascii 碼中， 0 代表的是 '\0'，也就是字串的結尾符號，我認為在這邊不應該使用結尾符號來進行填充，所以我將 'a' 填充進去，並且在字串的結尾使用 '\0' 。同理，在隨機生成的的話，就會需要避免隨機產生的數字為 0 ，所以我將隨機生成的數字加上了 65，以避免這問題。 ```c void prepare_inputs(uint8_t *input_data, uint8_t *classes) { randombytes(input_data, N_MEASURES * CHUNK_SIZE); for (size_t i = 0; i < N_MEASURES; i++) { classes[i] = randombit(); if (classes[i] == 0) { memset(input_data, 'a', CHUNK_SIZE - 1); input_data[CHUNK_SIZE - 1] = '\0'; } else { uint8_t rand; for (size_t i = 0; i < CHUNK_SIZE - 1; i++) { randombytes(&rand, 1); input_data[i] = (rand % 50) + 65; } input_data[CHUNK_SIZE - 1] = '\0'; } } } ``` - q_size() 的使用不恰當 在 `measure` 這個函式中，以 insert_tail 這個函式為例 ```c ... case DUT(insert_tail): for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) { char *s = get_random_string(); dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000); int before_size = q_size(l); before_ticks[i] = cpucycles(); dut_insert_tail(s, 1); after_ticks[i] = cpucycles(); int after_size = q_size(l); dut_free(); if (before_size != after_size - 1) return false; } break; ... ``` 可以看到它取得了插入前後的 q_size()，並且相減來比對是否有插入，但是這樣的檢查僅能檢查出**是否有插入成功**，並不能知道它是否插在尾巴，所以這個檢查的操作我就先將其移除，畢竟在 `make test` 的前面也有檢查過 insert head 等等的功能了。 在經過這樣的修改過後， `make test` 就可以得到 100 分了 :::info TODO 把 lab0-c/dudect 下的檔案整理的好看一些 ::: ## 實作 `select` system call 來完成 lab0-c 中的 web 功能 --- ## 參考資料 - [L01:lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a) - [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) - [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) - [Linked List in Linux Kernel](https://www.cntofu.com/book/46/linux_kernel/20.md)