2023q1 Homework1 (lab0)

--- tags: linux2023 --- # 2023q1 Homework1 (lab0) contributed by < `linhoward0522` > :::warning 不用複製作業要求內容，善用超連結。 :notes: jserv ::: ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ 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): 12 On-line CPU(s) list: 0-11 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i5-12400 CPU family: 6 Model: 151 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 2 CPU max MHz: 5600.0000 CPU min MHz: 800.0000 BogoMIPS: 4992.00 ``` ## queue.[ch] ### `q_new` - 使用 `INIT_LIST_HEAD` 來初始化一個空的 `list_head` ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ### `q_free` - 想法是使用 `list_entry` 找出對應的 element 並且釋放其內部所指的字串以及自身的空間 - 在 `queue.h` 中裡面 `q_release_element` 可以用來釋放記憶體 ```c void q_free(struct list_head *l) { if (!l) return; struct list_head *current = l->next; while (current != l) { current = current->next; q_release_element(list_entry(current->prev, element_t, list)); } free(l); } ``` - 後來參考 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)，由於過程中要將節點移除， `list_for_each_entry_safe` 會記錄下一個位置，並可以安全刪除當前節點，進一步精簡程式碼 ```c void q_free(struct list_head *l) { if (!l) return; element_t *pos, *n; list_for_each_entry_safe (pos, n, l, list) q_release_element(pos); free(l); } ``` ### `q_insert_head` - 透過 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 以及 `list.h` ，其中的 `list_add` 將新的 `element_t->list` 加入原有的 head 裡。 - 並且需要配置字串所需的記憶體空間，其中 `strlen` 並不含 ``'\0'``，所以在配置時需要將記憶體空間多加一。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new = malloc(sizeof(element_t)); if (!new) return false; int len = strlen(s); new->value = malloc(sizeof(char) * len + 1); if (!new->value) { q_release_element(new); return false; } strncpy(new->value, s, len + 1); list_add(&new->list, head); return true; } ``` ### `q_insert_tail` - 同 `q_insert_head` ，使用 `list_add_tail` 來實作 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *new = malloc(sizeof(element_t)); if (!new) return false; int len = strlen(s); new->value = malloc((sizeof(char) * len + 1)); if (!new->value) { q_release_element(new); return false; } strncpy(new->value, s, len + 1); list_add_tail(&new->list, head); return true; } ``` ### `q_remove_head` - 利用 `list.h` 裡的 `list_first_entry` ，可以將第一個 element_t 的位址取出 - 並使用 `list_del_init` 確保在移除 entry 後前後節點會互相連結 - 最後要將移除的元素數值複製到 `sp` ，並且複製字串到 `sp` 時要加上 `null terminator` 的空間 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *element = list_first_entry(head, element_t, list); list_del_init(head->next); /*If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/ if (sp) { strncpy(sp, element->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return element; } ``` ### `q_remove_tail` - 同 `q_remove_head` ，使用 `list_last_entry` 將最後一個 `element_t` 的位址取出 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *element = list_last_entry(head, element_t, list); list_del_init(head->prev); /*If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/ if (sp) { strncpy(sp, element->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return element; } ``` ### `q_size` - 利用 `list_for_each` 走訪每個節點並計算長度。 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *pos; int length = 0; list_for_each (pos, head) length++; return length; } ``` ### `q_delete_mid` - 根據[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)，其中老師有提到快慢指標的概念來實作 - 並使用 `list_del_init` 確保在移除 entry 後前後節點會互相連結 - 最後利用 `list_entry` 找出對應的 element 並使用 `q_release_element` 釋放記憶體空間。 ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **indirect = &head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) indirect = &(*indirect)->next; struct list_head *next = *indirect; list_del_init(next); q_release_element(list_entry(next, element_t, list)); return true; } ``` - 後來根據考試時的課後講解，改成用以下方式進行實作 - 透過迴圈來判斷是否相遇 ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *forward = head->next; struct list_head *backward = head->prev; while (forward != backward && forward->next != backward) { forward = forward->next; backward = backward->prev; } list_del_init(backward); q_release_element(list_entry(backward, element_t, list)); return true; } ``` ### `q_delete_dup` - Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well. - 已知為一個排序後的 linked list ，想法是使用 `list_for_each_entry_safe` 進行迭代，能得到當前的以及下一個 `element_t` 的位址 - 使用 `strcmp` 比對字串是否相同 - 變數 `flag` 用來確認如果字串相同，則在下一個迴圈就會刪除另一個重複的元素 ```c bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; element_t *element, *next; bool flag = false; list_for_each_entry_safe (element, next, head, list) { if (&next->list != head && strcmp(element->value, next->value) == 0) { list_del_init(&element->list); q_release_element(element); flag = true; } else if (flag) { list_del_init(&element->list); q_release_element(element); flag = false; } } return true; } ``` ### `q_swap` - Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) - 原本在 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 中有找到 `list_swap` 要來做使用，但在 `list.h` 並沒有看到相關實作，後來改用 `list_move` 來實作 - 由於使用 `list_move` ，所以兩個指標也互換，所以迭代到下一次時就相當於是 current->next->next ，即完成兩兩交換 ```c void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; for (struct list_head *current = head->next; current != head && current->next != head; current = current->next) list_move(current, current->next); } ``` ### `q_reverse` - 使用 `list.h` 裡的 `list_for_each_safe` 進行迭代 - 原本的想法是運用 `prev` 和 `next` 來紀錄前後位置，然後反轉節點 - 後來發現 `list.h` 裡的 `list_move` ，可以將節點移至串列起始點，即完成反轉 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *pos, *n; list_for_each_safe (pos, n, head) list_move(pos, head); } ``` ### `q_reverseK` - Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. - 想法為將每一組的節點逐一往前移至最前面，接著迭代每一組 - 使用 `q_size` 紀錄串列長度，用來確保最後剩下不足 k 個節點不會做反向順序排列 - 透過 `current` 紀錄 `pos->next` 的位址 - 做完 `list_move` 後，相對地 `pos` 會向後移一格 - 所以下一次迭代 `*current` 就會指向下一個要做反向順序排列的節點 - `tmp` 用來紀錄要將節點移動到的地方 ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head) || k < 2) return; int length = q_size(head); for (struct list_head *pos = head->next; pos != head && pos->next != head; pos = pos->next) { struct list_head **current = &pos->next, *tmp = pos->prev; for (int i = 1; i < k; i++) { if (length >= k) list_move(*current, tmp); } length -= k; } } ``` ### `q_sort` - 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) `merge sort` 的實作 #### `merge_list` - 用兩個指標分別指著兩個串列，比較後將較小的放到新的串列裡，然後將指標移至下一個位置 - 運用 indirect pointer 的技巧可以避免配置暫時節點的記憶體空間 - 當迭代完成後，會剩下一個節點尚未加入串列，採 `bit-wsie` 方法來加速運算 ```c struct list_head *merge_list(struct list_head *left, struct list_head *right) { struct list_head *head = NULL, **ptr = &head; for (; left && right; ptr = &(*ptr)->next) { if (strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) < 0) { *ptr = left; left = left->next; } else { *ptr = right; right = right->next; } } *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right); return head; } ``` #### `merge_sort` - 先使用快慢指標的方法來尋找中間節點 - 再呼叫 `merge_list` 將第一個節點開頭的串列及中間節點開頭的串列，合併成一個有序的串列。 - 其中 `slow->next = NULL;` 是必須要將第一個節點開頭的串列尾巴指向`NULL` ```c struct list_head *merge_sort(struct list_head *head) { if (!head || !head->next) return head; struct list_head *fast, *slow = head; for (fast = head->next; fast && fast->next; fast = fast->next->next) { slow = slow->next; } struct list_head *left, *right; right = slow->next; slow->next = NULL; left = merge_sort(head); right = merge_sort(right); return merge_list(left, right); } ``` #### `q_sort` - 執行 `merge_sort` 前要先將 `head` 斷開，使其變成 `singly-linked list` 來避免產生無窮迴圈 - 最後要再迭代一次排序後的串列，因為當前排序過後是 `singly-linked list` ，所以要將 `prev` 指標更新，也需將串列尾巴與串列開頭相互連結，讓串列變回 `circular doubly-linked list` ，以維持 `struct list_head` 的型態 ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; head->prev->next = NULL; head->next = merge_sort(head->next); struct list_head *cur = head, *n = head->next; while (n) { n->prev = cur; cur = n; n = n->next; } cur->next = head; head->prev = cur; } ``` ### `q_descend` - Remove every node which has a node with a strictly greater value anywhere to the right side of it. - Return the number of elements in queue after performing operation - 想法是透過反向順序逐一走訪節點，若下一個節點小於當前節點則將它刪除 ```c int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *cur = head->prev, *n = cur->prev; while (n != head) { if (strcmp(list_entry(n, element_t, list)->value, list_entry(cur, element_t, list)->value) < 0) { list_del_init(n); q_release_element(list_entry(n, element_t, list)); } else cur = n; n = cur->prev; } return q_size(head); } ``` ### `q_merge` - You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { node [shape=record]; head_c [label="head|{<prev>prev|<next>next}"]; size0 [label="{size}"]; style=bold; label=queue_chain_t } head_c:next:e -> chain:w chain:prev:w -> head_c:e chain:next->head_c:x head_c:prev->chain:x subgraph cluster_1 { node [shape=record]; q [label="q"]; chain [label="chain|{<prev>prev|<next>next}"]; size1 [label="{size}"]; id [label="{id}"]; style=bold; label=queue_contex_t } head [label="head|{<prev>prev|<next>next}"]; q:right:e -> head:n subgraph cluster_2 { node [shape=record]; value [label="{value}"]; head_e [label="head|{<prev>prev|<next>next}"]; style=bold; label=element_t } head:next:e -> head_e:w head_e:prev:w -> head:e head_e:next -> head:s head:prev -> head_e:s } ``` - 從 `queue.h` 可以了解 `queue_contex_t` 的結構 - `q` 用來指向 queue 的 head - `chain` 用來將每一個 `queue_contex_t` 結構串連起來 - `size` 表示這個 queue 的長度 - `id` 表示每一個 queue 唯一的編號 - 接著從 `qtest.c` 發現有宣告 `queue_chain_t` 的結構，並從`do_new` 函式可以發現 - 他是用來當 `queue_contex_t` 結構的 head - 並且每次 new 一個新的 `queue_contex_t` 結構，都會將此結構插入到串列的尾端 - 同時在 `qtest.c` 的 `do_merge` 函式可以發現它傳入的參數是 `queue_chain_t` 結構的 head - 因為 `qtest.c` 裡面有宣告 `q_chain_t` 的結構，所以邊界條件不用判斷 `!head` - 所以設置 `list_empty(head)` 與 `list_is_singular(head)` 為邊界條件即可 - 想法就是逐一將所有串列合併到第一個串列 - 與 `q_sort` 差不多，執行 `merge_list` 前要先將 `head` 斷開，使其變成 `singly-linked list` 來避免產生無窮迴圈 - 最後要再迭代一次排序後的串列，讓串列變回 `circular doubly-linked list` - 其中必須要加上 `INIT_LIST_HEAD(pos->q)` 才不會造成 `Segmentation fault` ```c int q_merge(struct list_head *head) { if (list_empty(head)) return 0; if (list_is_singular(head)) return list_entry(head->next, queue_contex_t, chain)->size; queue_contex_t *first = list_entry(head->next, queue_contex_t, chain); queue_contex_t *pos = NULL; struct list_head *tmp = first->q->next; first->q->prev->next = NULL; list_for_each_entry (pos, head, chain) { if (first == pos) continue; pos->q->prev->next = NULL; tmp = merge_list(tmp, pos->q->next); INIT_LIST_HEAD(pos->q); } first->q->next = tmp; struct list_head *cur = first->q, *n = cur->next; while (n) { n->prev = cur; cur = n; n = n->next; } cur->next = first->q; first->q->prev = cur; return q_size(tmp); } ``` :::info 目前 trace-17-complexity 還是無法通過 ::: ## 研讀 Linux 核心原始程式碼的 `lib/list_sort.c` - 閱讀 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e) , [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-list_sort-%E5%AF%A6%E4%BD%9C) ### 嘗試引入到 `lab0-c` 專案 - 參考作業規範中 [`qtest` 命令直譯器的實作](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C) - 將 [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 程式碼複製到 `qtest.c` - 其中有使用到`__attribute__((nonnull(2,3,4)))` 關鍵字 - 為 compiler 指定函式傳入的參數必須為 non-null ，如果傳入 null 則會發出警告 > [參考資料](https://developer.arm.com/documentation/dui0375/g/Compiler-specific-Features/--attribute----nonnull---function-attribute) - 在 [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L222) 有使用到 `likely` 這個巨集，所以需要增添到 `qtest.c` ，而他們被定義在 [/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中 ```c # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) ``` - `__built_expect()` 是 gcc 的內建 function，用來將 branch 的相關資訊提供給 compiler ，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化。 - 而這 `likely` , `unlikely` 兩個巨集，可以讓 compiler 在編譯 assembly code 的時候做一些最佳化，可以告訴 compiler 某段 `if` 敘述為 true 的機率較高或低，讓 compiler 把對應程式碼接在判斷的後面 - 程式碼被放到比較相近的位置，那他們就可能一起被搬到 cache 中，使 cache hit rate 上升，可能可以提升程式的執行效能。 > [參考資料](https://meetonfriday.com/posts/cecba4ef/) - 將 [`list_sort.h`](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h ) 中將 `list_cmp_func_t` 的定義加入到 `qtest.c` ```c typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *); ``` - 為一個 `Function Pointer` ，並且因為 `__attribute__((nonnull(2,3)))` 所以第二以及第三個參數不能為 `null` - 接著根據 [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的註解來實作 `comparison function` - if (a > b) return > 0 - if (a < b) return <= 0 或保留其原本排序 - `list_sort` 是 `stable sort`，所以沒必要區分 a < b 和 a == b 的情況 ```c static int cmp_fun(void *priv, const struct list_head *v1, const struct list_head *v2) { return strcmp(list_entry(v1, element_t, list)->value, list_entry(v2, element_t, list)->value); } ``` - 參考 `do_sort` 函式，實作 `do_linux_sort` - 只要更改這行即可 ```c list_sort(NULL, current->q, cmp_fun); ``` - 並從 `qtest.c` 的 `console_init` 中加入新命令 : ```c ADD_COMMAND(linux_sort, "Sort queue in ascending order by linux kerenl",""); ``` - 但此時編譯的時候會出現錯誤訊息 - `error: unknown type name ‘u8’` - 發現 [第 56 行](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L56) 宣告一個 `count` 變數，型態為 `u8`，被定義在 [/tools/include/linux/types](https://github.com/torvalds/linux/blob/master/tools/include/linux/types.h) 裡 - 去查詢 [/include/linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h ) 後，發現應該是沒有加上 `#include <linux/types.h>` 才出錯，但加上後仍然出現錯誤訊息 - 最後只好將 `#include <linux/types.h>` 改成 `#include <stdint.h>` ，並且將型態 `u8` 改為 `uint8_t` 才不會出現錯誤訊息 ::: info 目前還不知道確切原因 ::: ### 比較你自己實作的 `merge sort` 和 `Linux` 核心程式碼之間效能落差 - 首先參考 [Linux 效能分析工具 : Perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 以及 [`perf Examples`](https://www.brendangregg.com/perf.html) 來做安裝與撰寫 - 寫了兩個 `shell script` 分別用來執行 `linux_sort` 與 `sort` 的效能測試，並使用 `perf report` 將輸出存起來 >[學習怎麼寫 shell scripts](https://linux.vbird.org/linux_basic/centos7/0340bashshell-scripts.php) - 想要檢測的項目有 `cache-misses` , `branches` , `instructions` , `context-switches` ```bash #!/bin/bash for i in ./traces/traces_perf_linux_sort/*.cmd do perf stat --repeat 5 -o "${i%.cmd}"_report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i" done ``` - 在 `lab0-c/traces` 新增兩個目錄，分別存放用來測試 `linux_sort` 與 `sort` 的命令檔 ``` . ├── traces_perf_linux_sort │ ├── RAND_1000000.cmd │ ├── RAND_100000.cmd │ ├── RAND_10000.cmd │ └── RAND_1000.cmd └── traces_perf_sort ├── RAND_1000000.cmd ├── RAND_100000.cmd ├── RAND_10000.cmd └── RAND_1000.cmd ``` - 其中 `RAND_*.cmd` 的內容是參考 `trace-0*-ops.cmd` 來改寫，表示要 sort `*` 個隨機字串 ```cmd option fail 0 option malloc 0 new ih RAND 1000 linux_sort free ``` - 要先啟用 root 權限接著再執行 `.sh` 檔案 - 若執行 `.sh` 檔案顯示 `Permission denied` - 輸入 `chmod u+x *.sh` - `perf report` 內容 ``` # started on Mon Feb 20 14:01:20 2023 Performance counter stats for './qtest -v 0 -f ./traces/traces_perf_linux_sort/RAND_1000.cmd' (5 runs): 1289 cpu_core/cache-misses/ ( +- 43.74% ) 78,1958 cpu_core/branches/ ( +- 0.17% ) 516,3000 cpu_core/instructions/ ( +- 0.14% ) 0 context-switches 0.0008445 +- 0.0000127 seconds time elapsed ( +- 1.50% ) ``` - 實驗結果 - **`sort`** | # node | cache-misses | branches | instructions | context-switches | time | |:------:|:-----------:|:--:|:--:|:--:|:--:| |1000|4443|78,9179|514,5106|0|0.0009679| |10000|2960|621,6845|4248,6763|0|0.0054019| |100000|79,2148|6354,8361|4,2894,2226|0|0.063659| |1000000|4692,1584|6,6668,8777|44,2436,0379|152|1.03455| - **`list_sort`** | # node | cache-misses | branches | instructions | context-switches | time | |:------:|:-----------:|:--:|:--:|:--:|:--:| |1000|1289|78,1958|516,3000|0|0.0008445| |10000|3118|615,8586|4285,4486|0|0.0058063| |100000|37,9827|6297,2125|4,3374,6650|0|0.061114| |1000000|3669,3394|6,6033,1233|44,7728,5288|2|0.96378| - 由實驗結果可以看出上面測試項目基本上 `list_sort` 都比我自己實作的 `sort` 還要優秀，尤其在節點數 1000000 時， `cache-misses` , `context-switches` 數量相差非常大 ## 在 `qtest` 提供新的命令 `shuffle` - 想法是從 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 裡面所提供的 pseudocode : ```c -- To shuffle an array a of n elements (indices 0..n-1): for i from 0 to n−2 do j ← random integer such that i ≤ j < n exchange a[i] and a[j] ``` - 首先先實作一個 `swap` 函式，用來將節點內的數值做交換 ```c void swap(element_t *s1, element_t *s2) { char *tmp = s1->value; s1->value = s2->value; s2->value = tmp; } ``` - 按照 pseudocode 來實作， `tail` 指標紀錄目前串列的最後位置 - `cur` 指標用來紀錄隨機挑出節點的位置 - 接著將 `cur` 指標所紀錄的位置來做交換跟 `tail` 指標所紀錄的位置來做交換 - `tail = tail->prev` 會紀錄下一次要交換節點的位置 ```c void q_shuffle(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *tail = head->prev; for (int i = q_size(head); i > 0; i--) { int ran = rand() % i; struct list_head *cur = head; for (int j = 0; j <= ran; j++) { cur = cur->next; } swap(list_entry(cur, element_t, list), list_entry(tail, element_t, list)); tail = tail->prev; } } ``` - 參考 `qtest.c` 中各個 `do_*` 函式，加入函式 `do_shuffle` - 此函式在執行 `q_shuffle` 之前檢查佇列並發出警告訊息，接著再執行 `q_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 shuffle on null queue"); error_check(); if (exception_setup(true)) q_shuffle(current->q); exception_cancel(); q_show(3); return !error_check(); } ``` - 從 `qtest.c` 的 `console_init` 中加入新命令： ```c ADD_COMMAND(shuffle, "Shuffle the queue by using Fisher–Yates shuffle", ""); ``` - 執行結果 ``` cmd> new l = [] cmd> ih RAND 5 l = [tkjacbs xauofve bjxglmkx sbtgzzd plzss] cmd> shuffle l = [xauofve tkjacbs bjxglmkx plzss sbtgzzd] cmd> shuffle l = [xauofve bjxglmkx sbtgzzd plzss tkjacbs] cmd> shuffle l = [plzss sbtgzzd bjxglmkx tkjacbs xauofve] ``` ### 以統計的原理來分析你的實作 - 參考作業說明 : [統計方法驗證 `shuffle`](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d#%E7%B5%B1%E8%A8%88%E6%96%B9%E6%B3%95%E9%A9%97%E8%AD%89-shuffle) - 將測試程式新增到 `scripts/shuffle_test.py` - 第一行要加上 `#!/bin/python` #### 1. 先計算 chi-squared test statistic $X^2$ - 執行 `python3 ./scripts/shuffle_test.py` - 在測試 shuffle 1000000 次後，24種結果各自的頻率如下表： |排列組合| 觀察到的頻率| 期待的頻率 |${(O_i - E_i)^2 \over E_i}$| | :--------: | :--------: | :--------: |:---:| | [1, 2, 3, 4] | 41,566 | 41,666 |0.240003840061441| | [1, 2, 4, 3] | 41,589 | 41,666 |0.14229827677242837| | [1, 3, 2, 4] | 41,212 | 41,666 |4.9468631498103965| | [1, 3, 4, 2] | 41,533 | 41,666 |0.424542792684683| | [1, 4, 2, 3] | 41,389 | 41,666 |1.8415254644074306| | [1, 4, 3, 2] | 41,778 | 41,666 |0.3010608169730716| | [2, 1, 3, 4] | 41,672 | 41,666 |0.0008640138242211876| |[2, 1, 4, 3]|41,579|41,666|0.1816589065425047| |[2, 3, 1, 4]|41,690|41,666|0.013824221187539001| |[2, 3, 4, 1]|41,989|41,666|2.5039360629770075| |[2, 4, 1, 3]|41,960|41,666|2.0744971919550714| |[2, 4, 3, 1]|41,701|41,666|0.02940047040752652| |[3, 1, 2, 4]|41,553|41,666|0.306460903374454| |[3, 1, 4, 2]|41,758|41,666|0.1858589737435799| |[3, 2, 1, 4]|41,508|41,666|0.5991455863293813| |[3, 2, 4, 1]|41,561|41,666|0.26460423366773866| |[3, 4, 1, 2]|41,825|41,666|0.6067537080593289| |[3, 4, 2, 1]|41,798|41,666|0.41818269092305477| |[4, 1, 2, 3]|41,783|41,666|0.3285412566601066| |[4, 1, 3, 2]|41,567|41,666|0.2352277636442183| |[4, 2, 1, 3]|41,574|41,666|0.20313925022800364| |[4, 2, 3, 1]|41,862|41,666|0.9219987519800317| |[4, 3, 1, 2]|41,623|41,666|0.04437671002736044| |[4, 3, 2, 1]|42,110|41,666|4.731339701435223| |Total|||21.546104737675805| $X^2$ = 21.546104737675805 #### 2. 決定自由度（degrees of freedom） - 對於 N 個隨機樣本而言，自由度為 N - 1 - 本次實驗有 24 個結果，故自由度為 23 #### 3. 選擇顯著水準 - alpha 設定為常見的 0.05 - 從卡方分布表找合適的 P value，我們的自由度為 23 - $X^2$ = 21.546104737675805，因為 19.021 < 21.546104737675805 < 22.337，於是 P value 介於 0.7 和 0.5 之間。 >![](https://i.imgur.com/oTSBGY8.png =500x500) #### 4. 統計檢定的結果不拒絕虛無假說 - 因為 P value（0.5~0.7）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$） - 從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的 ![](https://i.imgur.com/qu2zxpk.png =400x300) ## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉 - 提出了一個工具 `dudcet` ，用來量測程式能否在常數時間執行完成 ### `TIMING LEAKAGE DETECTION` - 透過輸入兩種不同的資料，檢查這兩個的執行時間分布在統計分析上是否不同 #### Step 1 : `Measure execution time` - Classes definition : - leakage detection test 的類型有很多種，差別是在輸入資料類別的不同 - 最常見的就是 `fix-vs-random test` - 第一類輸入資料是一個固定的常數 - 第二類數入資料是亂數 - 其中第一類資料被用來觸發某些特殊的極端狀況( such as low-weight input forarithmetic operations ) - Cycle counters : - 現今的 CPU 提供 cycle counters 來精準的計算執行時間 :::spoiler 在 `dudct/cpucycles.h` `可找到相關程式碼 ```c #ifndef DUDECT_CPUCYCLES_H #define DUDECT_CPUCYCLES_H #include <stdint.h> static inline int64_t cpucycles(void) { #if defined(__i386__) || defined(__x86_64__) unsigned int hi, lo; __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi)); return ((int64_t) lo) | (((int64_t) hi) << 32); #elif defined(__aarch64__) uint64_t val; asm volatile("mrs %0, cntvct_el0" : "=r"(val)); return val; #else #error Unsupported Architecture #endif } #endif ``` ::: - Environmental conditions : - 為了減少運行環境對結果的影響，每次測量都會對應隨機的類別 #### Step 2 : `Apply post-processing` - 在統計分析之前先做一些後處理 - Cropping - 典型的時間分佈為 [`positive skew`](https://en.wikipedia.org/wiki/Skewness) ，可能會因為 OS 或外部程式造成測量誤差，透過裁剪超過 threshold 的測量結果 - Higher-order preprocessing : - 根據統計測試，可能是更有益於 high-order preprocessing #### Step 3 : `Apply statistical test` - 利用統計檢驗來反駁虛無假說"兩個時間分佈相同" - t-test : 使用 [`Welch’s t-test`](https://en.wikipedia.org/wiki/Welch%27s_t-test) >[參考作業說明](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d#Welch%E2%80%99s-t-test) ## 開啟 [`Address Sanitizer`](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤 - 目前執行完下列指令後並沒有發出如作業規範裡類似的[錯誤訊息](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a) ``` make clean make SANITIZER=1 make test ``` ## 運用 `Valgrind` 排除 `qtest` 實作的記憶體錯誤 - 輸入指令 `make valgrind` - 出現很多相同的錯誤訊息，節錄部份 ``` ==70766== 32 bytes in 1 blocks are still reachable in loss record 1 of 2 ==70766== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==70766== by 0x10CC82: do_new (qtest.c:154) ==70766== by 0x10E332: interpret_cmda (console.c:181) ==70766== by 0x10E8E7: interpret_cmd (console.c:201) ==70766== by 0x10ECE8: cmd_select (console.c:610) ==70766== by 0x10F5D4: run_console (console.c:705) ==70766== by 0x10D724: main (qtest.c:1576) ``` - 從報告中指明有一個 32 bytes 的 block 仍然可以訪問，推測可能是沒有正常釋放記憶體 - 檢查函式 `q_free` , `do_free` 都沒有問題 - 但是在 `qtest.c` 中的 `q_quit` 函式，第一行就是 `return ture` ，會導致下面的程式無法正常執行，以至於沒有正常釋放記憶體 - 將第一行的 `return ture` 拿掉後就沒有出現錯誤訊息了 ### 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量 - 首先寫要測試用的命令檔 ```cmd option simulation 1 it option simulation 0 ``` - 再來執行 ```cmd valgrind --tool=massif ./qtest -f traces/trace_it.cmd ``` - 如果想要將結果顯示出來，可以先安裝 [massif-visualizer](https://github.com/KDE/massif-visualizer) 後再來執行 ```cmd massif-visualizer massif.out.* ``` - `simulation` `it` ![](https://i.imgur.com/zIHDnES.png =400x300) - `simulation` `ih` ![](https://i.imgur.com/ESXvHK9.png =400x300) - `simulation` `rt` ![](https://i.imgur.com/PW5Mqqb.png =400x300) - `simulation` `rh` ![](https://i.imgur.com/ejFpTBM.png =400x300) :::info 上述四個的共通點都是記憶體沒有被完全釋放 ::: ## 問題紀錄 :::info GitHub Action 目前都無法正常運作，還沒有找到原因 :::