--- tags: linux2023 --- # 2023q1 Homework1 (lab0) contributed by < `visitorckw` > ## 開發環境 ```bash $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 12 On-line CPU(s) list: 0-11 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 165 Model name: Intel(R) Core(TM) i5-10500 CPU @ 3.10GHz Stepping: 3 CPU MHz: 3100.000 CPU max MHz: 4500.0000 CPU min MHz: 800.0000 BogoMIPS: 6199.99 Virtualization: VT-x L1d cache: 192 KiB L1i cache: 192 KiB L2 cache: 1.5 MiB L3 cache: 12 MiB NUMA node0 CPU(s): 0-11 ``` ## 開發過程 > Current score: 83/100 ### q_new 一開始的實作如下: ```c struct list_head *q_new() { struct list_head *head = (struct list_head *) malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` 後來想到可以寫得更精簡，當 malloc 配置記憶體成功後，才使用 `INIT_LIST_HEAD` 巨集。 ```c struct list_head *q_new() { struct list_head *head = (struct list_head *) malloc(sizeof(struct list_head)); if (head) INIT_LIST_HEAD(head); return head; } ``` ### q_free 使用 `list_for_each_entry_safe` 巨集逐一釋放每個單元占用的空間。 ```c void q_free(struct list_head *l) { if (!l) return; element_t *entry; element_t *safe; list_for_each_entry_safe (entry, safe, l, list) { free(entry->value); free(entry); } free(l); } ``` ### q_insert_head 使用 malloc 函式去配置記憶體，若失敗就先用 free 函式釋放記憶體後 return false ，否則利用 list_add macro 來將新的節點加入到 list 之中。 原先採用 strcpy 函式進行字串的複製，但在 git commit 時會遇到以下錯誤: ``` Dangerous function detected in /home/student1/linux2023/lab0-c/queue.c 90: strcpy(sp, delNode->value); ``` 因此定義了 strlcpy 巨集，在複製時需指定長度，透過改成 sprintf 函式來實作: ```c #ifndef strlcpy #define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src)) #endif ``` 最後完整的 q_insert_head 函式如下: ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *newNode = (element_t *) malloc(sizeof(element_t)); if (!newNode) return false; newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1)); if (!newNode->value) { free(newNode); return false; } strlcpy(newNode->value, s, strlen(s) + 1); list_add(&newNode->list, head); return true; } ``` ### q_insert_tail 邏輯與 q_insert_head 函式相同。唯一的不同之處是原先使用 list_add 巨集來完成，這裡是要從尾端加入新節點，因此要改用 list_add_tail 巨集。 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *newNode = (element_t *) malloc(sizeof(element_t)); if (!newNode) return false; newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1)); if (!newNode->value) { free(newNode); return false; } strlcpy(newNode->value, s, strlen(s) + 1); list_add_tail(&newNode->list, head); return true; } ``` ### q_remove_head 先用 list_entry macro 抓出將要 remove 的節點，將節點的 value 字串的內容複製給 sp 之後，再用 list_del macro 刪除。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *delNode = list_entry(head->next, element_t, list); size_t length = bufsize < strlen(delNode->value) + 1 ? bufsize : strlen(delNode->value) + 1; strlcpy(sp, delNode->value, length); list_del(head->next); return delNode; } ``` 後來發現須要先檢查 sp 的值是否是 NULL，若是 NULL則不應該將字串複製給它。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *delNode = list_entry(head->next, element_t, list); size_t length = bufsize < strlen(delNode->value) + 1 ? bufsize : strlen(delNode->value) + 1; if (sp && bufsize) strlcpy(sp, delNode->value, length); list_del(head->next); return delNode; } ``` ### q_remove_tail 跟 q_remove_head 的邏輯相同，差在要抓的節點是 head->prev。 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *delNode = list_entry(head->prev, element_t, list); size_t length = bufsize < strlen(delNode->value) + 1 ? bufsize : strlen(delNode->value) + 1; strlcpy(sp, delNode->value, length); list_del(head->prev); return delNode; } ``` 和 q_remove_head 一樣，後來加入了 sp 是否為 NULL 的檢查機制。 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *delNode = list_entry(head->prev, element_t, list); size_t length = bufsize < strlen(delNode->value) + 1 ? bufsize : strlen(delNode->value) + 1; if (sp && bufsize) strlcpy(sp, delNode->value, length); list_del(head->prev); return delNode; } ``` ### q_size 使用 list_for_each 巨集走訪整個 list 計算節點的數量。 ```c= int q_size(struct list_head *head) { if (!head) return 0; int ctr = 0; struct list_head *node; list_for_each (node, head) ++ctr; return ctr; } ``` ### q_delete_mid 慢指標一次移動一格，快指標一次移動兩格。 因此當快指標走完整個 list 時，慢指標的位置會剛好只走了快指標的一半。 ```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; struct list_head *fast = head; while (1) { slow = slow->next; if (fast->next == head || fast->next->next == head) break; fast = fast->next->next; } element_t *delNode = list_entry(slow, element_t, list); list_del(slow); free(delNode->value); free(delNode); return true; } ``` ### q_delete_dup 使用 list_for_each 巨集走訪整個鏈結串列。 額外用一個字串 str 來記錄當前節點的 value 字串內容。 並且再另外用一個 while 迴圈來找字串內容相同的元素，並使用 list_del 巨集對節點做 remove 。 - 待解決的問題: 在執行完 q_delete_dup 過後接著執行 q_free 會產生以下錯誤: ``` ERROR: There is no queue, but 3 blocks are still allocated ``` 目前猜測是由於刪除時有發生 memory leak 的情形，需用 valgrind 等工具檢查錯誤產生的原因。 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head)) return true; struct list_head *cur; list_for_each (cur, head) { if (cur->next == head) break; element_t *L = list_entry(cur, element_t, list); element_t *R = list_entry(cur->next, element_t, list); if (strcmp(L->value, R->value)) continue; char *str = (char *) malloc(sizeof(char) * (strlen(L->value) + 1)); strlcpy(str, L->value, strlen(L->value) + 1); struct list_head *prev = cur->prev; while (prev->next != head) { element_t *node = list_entry(prev->next, element_t, list); if (strcmp(str, node->value)) break; list_del(prev->next); free(node->value); free(node); } cur = prev; } return true; } ``` ### q_swap 迴圈每次將指標移動兩格，將自身與下一個節點的 value 交換。 交換採用三次 bitwise xor 的技巧。 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ for (struct list_head *cur = head->next; (long int) cur ^ (long int) head; cur = cur->next->next) { if (cur->next == head) return; element_t *L = list_entry(cur, element_t, list); element_t *R = list_entry(cur->next, element_t, list); L->value = (char *) ((long int) L->value ^ (long int) R->value); R->value = (char *) ((long int) L->value ^ (long int) R->value); L->value = (char *) ((long int) L->value ^ (long int) R->value); } } ``` :::warning 撰寫更精簡的程式碼。 :notes: jserv ::: 修正後的程式碼如下，使用 flag 變數來記錄是否跟前一個節點交換 value 。 ```c void q_swap(struct list_head *head) { int flag = 0; struct list_head *cur, *safe; list_for_each_safe (cur, safe, head) { if (flag & 1) { element_t *L = list_entry(cur, element_t, list); element_t *R = list_entry(cur->prev, element_t, list); R->value = (char *) ((long int) L->value ^ (long int) R->value); L->value = (char *) ((long int) L->value ^ (long int) R->value); } flag ^= 1; } } ``` ### q_reverse 將所有節點的 next 和 prev 的值交換 ( 須包含 head )。 交換採用 3 次 bitwise xor 的技巧。 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *cur = head; do { cur->prev = (struct list_head *) ((long int) cur->prev ^ (long int) cur->next); cur->next = (struct list_head *) ((long int) cur->prev ^ (long int) cur->next); cur->prev = (struct list_head *) ((long int) cur->prev ^ (long int) cur->next); cur = cur->prev; } while ((long int) cur ^ (long int) head); } ``` ### q_reverseK 將每 k 個拆成一段獨立出來的 list 。 呼叫前面所實作好的 q_reverse 函式之後，再拼接回原本的鏈結串列中。 ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ struct list_head *ptr = head; struct list_head *cur = head; while (1) { for (int i = 0; i < k; i++) { cur = cur->next; if (cur == head) break; } if (cur == head) break; struct list_head *next = cur->next; element_t ele; struct list_head *dummy = &(ele.list); dummy->next = ptr->next; dummy->prev = cur; ptr->next->prev = dummy; cur->next = dummy; q_reverse(dummy); ptr->next = dummy->next; dummy->next->prev = ptr; dummy->prev->next = next; next->prev = dummy->prev; ptr = cur = dummy->prev; } } ``` ### mergeTwoLists 由於實作 q_sort 以及 q_merge 兩個函式時都需要用到合併已排序連結串列的操作。因此額外實作本函式以利後續開發與維護。 合併兩個已經由小到大排序好的 list 合併。 採用 indirect pointer 技巧使程式碼更簡潔易讀。 ```c struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2) { struct list_head **ptr = &L1; struct list_head *ptr1 = L1->next; struct list_head *ptr2 = L2->next; while (ptr1 != L1 && ptr2 != L2) { element_t *node1 = list_entry(ptr1, element_t, list); element_t *node2 = list_entry(ptr2, element_t, list); if (strcmp(node1->value, node2->value) < 0) { (*ptr)->next = ptr1; ptr1->prev = *ptr; ptr1 = ptr1->next; } else { (*ptr)->next = ptr2; ptr2->prev = *ptr; ptr2 = ptr2->next; } ptr = &(*ptr)->next; } while (ptr1 != L1) { (*ptr)->next = ptr1; ptr1->prev = *ptr; ptr1 = ptr1->next; ptr = &(*ptr)->next; } while (ptr2 != L2) { (*ptr)->next = ptr2; ptr2->prev = *ptr; ptr2 = ptr2->next; ptr = &(*ptr)->next; } (*ptr)->next = L1; L1->prev = *ptr; return L1; } ``` ### q_sort 先利用和前面實作 q_delete_mid 所用到的快慢指針技巧找到將 list 拆分成兩半的位置。然後加入 dummy node 形成兩個獨立的 list。分別 sort 兩個list 之後，再將兩個排序好的 list 利用前面實作的 mergeTwoLists 函式合併。 ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *slow = head->next; struct list_head *fast = head->next; while (fast->next != head && fast->next->next != head) { slow = slow->next; fast = fast->next->next; } element_t ele; struct list_head *dummy = &(ele.list); struct list_head *mid = slow->next; struct list_head *last = head->prev; mid->prev->next = head; head->prev = mid->prev; dummy->next = mid; dummy->prev = last; last->next = dummy; mid->prev = dummy; q_sort(head); q_sort(dummy); mergeTwoLists(head, dummy); } ``` ### q_descend 類似於 monotonic stack 的概念，反向迭代整個 list ，並同時記錄當前所遇到最大的 value 。若當前的 value 比過去最大的 value 還要小則利用 list_del 函式來進行 remove 的動作。 ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ char str[50000] = ""; // unsafe for possible larger length struct list_head *next; for (struct list_head *cur = head->prev; cur != head; cur = next) { next = cur->prev; element_t *node = list_entry(cur, element_t, list); if (strcmp(node->value, str) < 0) { list_del(cur); free(node->value); free(node); } else strlcpy(str, node->value, 50000); } return q_size(head); } ``` ### q_merge 採用頭尾兩兩合併的方式，不斷重複直到剩下一個 list 為止。 - 待解決的問題: 在執行 make test 指令時發現，由於 merge 過後會造成當前指向的 queue 被設為 null 進而導致後續的一串指令都失效。 ```c int q_merge(struct list_head *head) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return list_entry(head->next, queue_contex_t, chain)->size; int queueSize = q_size(head); while (queueSize > 1) { struct list_head *node; list_for_each (node, head) { queue_contex_t *que1 = list_entry(node, queue_contex_t, chain); queue_contex_t *que2 = list_entry(head->prev, queue_contex_t, chain); if (que1 == que2) break; que1->q = mergeTwoLists(que1->q, que2->q); que2->q = NULL; que2->size = 0; list_del(head->prev); } queueSize = (queueSize + 1) / 2; } list_entry(head->next, queue_contex_t, chain)->size = q_size(list_entry(head->next, queue_contex_t, chain)->q); return list_entry(head->next, queue_contex_t, chain)->size; } ``` ### Valgrind 自動檢測 執行 ```make valgrind``` 過後，發現多數結果都如下: ```text ==616700== 2,049 bytes in 1 blocks are still reachable in loss record 46 of 47 ==616700== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==616700== by 0x10C0C9: do_remove (qtest.c:373) ==616700== by 0x10C4B7: do_rh (qtest.c:463) ==616700== by 0x10E053: interpret_cmda (console.c:181) ==616700== by 0x10E623: interpret_cmd (console.c:201) ==616700== by 0x10EA60: cmd_select (console.c:610) ==616700== by 0x10F36B: run_console (console.c:705) ==616700== by 0x10D3E0: main (qtest.c:1276) ==616700== ``` 代表檢測到程式結束時，仍然有著還沒被釋放的記憶體，但有指標依然指向它。可能是由於 globla 變數所導致的現象。 ### q_shuffle 首先在 qtest.c 裡面增加 shuffle 命令: ``` ADD_COMMAND(shuffle, "Shuffle the queue with Fisher–Yates shuffle algorithm", ""); ``` 然後參考其他 `do_` 開頭的函式實作 `do_shuffle` ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current || !current->q) report(3, "Warning: Calling sort on null queue"); error_check(); set_noallocate_mode(true); if (exception_setup(true)) q_shuffle(current->q); exception_cancel(); set_noallocate_mode(false); q_show(3); return !error_check(); } ``` 另外由於 commit hook 不允許更動 queue.h 之中的程式碼，因此另外用一個標頭檔 shuffle.h 並在裡面增加 q_shuffle 函式的宣告 ```c= #ifndef SHUFFLE_H #define SHUFFLE_H void q_shuffle(struct list_head *head); #endif ``` 並在 qtest.c 之中引入此標頭檔。 --- ### `lib/list_sort.c` 由於 list_sort.c 程式碼中所引入的標頭檔都是 linux 核心之中的標頭檔，因此需要自己做對應的修改才能順利的執行。 :::danger 改進漢語描述，注意作業書寫規範。 :notes: jserv ::: 1. 將 u8 改為 uint8_t 2. likely 以及 unlikely 巨集是定義在 linux/compiler.h 之中的巨集，因此需要在 list_sort.h 之中自己加入以下程式碼: ```c #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) ``` 3. 需要自己實作比較函式，如下: ```c int cmp(void *_, const struct list_head *a, const struct list_head *b) { char *strA = list_entry(a, element_t, list)->value; char *strB = list_entry(b, element_t, list)->value; return strcmp(strA, strB); } ``` ### 論文閱讀 - Dude, is my code constant time? * 本論文介紹了 dutect 工具，用於評估代碼在特定平台上是否以恆定時間運行，並且不需要對硬體有特別的要求。 * 方法步驟 1. Measure execution time * 進行測量時，首先需要定義兩種不同的數據類別，一種是固定的數據類別，而另一種是隨機的數據類別。 * 現代 CPU 提供週期計數器（例如 x86 系列中的 TSC 寄存器，或 ARM 可用的 systick 外設），可用於準確地獲取執行時間測量。 * 為了最小化環境變化對結果的影響，在進行測量時，每次測量對應一個隨機選擇的輸入數據類別。類別分配和輸入準備任務在測量階段之前執行。 2. Apply post-processing * 在進行統計分析前，應對每個單獨的測量進行一些處理。 * 典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量數據本身的問題，或者是主進程被操作系統或其他外部因素干擾所致。因此可以捨棄大於固定閾值的測量值。 * 根據應用的統計檢驗方法，可以進行一些高階前處理。 3. Apply statistical test * T 檢定: 可以使用 Welch’s t-test。需要注意的是，當 t 檢定與裁剪預處理結合使用時，不僅測試平均值是否相等，還測試更高階的統計矩，因為裁剪是一種非線性變換。 * 非參數檢定 * percentile 處理 percentile 是論文中步驟二所提及的 cropping 處理，目的是為了去除極值。
Last changed by  
 
visitor CKW
315
Published on HackMD