2025q1 Homework1 (lab0)

# 2025q1 Homework1 (lab0) contributed by < [tyj513](https://github.com/tyj513) > ### Reviewed by `SimonLiu423` 1. 作業書寫規範中提到 > HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」 2. `queue.h` 中已有 `q_release_element()` 函式可以去釋放指定的 element，為了增加可讀性及可維護性，建議將 `q_free()`、`q_delete_mid()` 等有進行釋放節點行為的函式，改為利用這個函式達成。 3. 開發日誌中針對 queue 的實作，經常看到 `queue_info` 的出現，但都沒有針對該 struct 的說明。該 struct 第一次出現於 Commit [b7a62be](https://github.com/tyj513/lab0-c/commit/b7a62be77e0bf269cb4f95e3310def2904f630e3)，然而其 commit message 也沒有去描述為何需要這個 struct。 5. 數學公式建議改以 LaTeX 書寫，看起來更專業並且有更好的排版，閱讀起來也較容易，如 `t = (x̄₁ - x̄₂) / sqrt(s₁²/n₁ + s₂²/n₂)` 改寫為： $$ t ={(\bar{x}_1 - \bar{x}_2) / \sqrt{{s_1^2 \over n_1} + {s_2^2 \over n_2}}} $$ 3. 作業要求中是希望利用 Massif 分析 `simulation` 過程中的記憶體用量，而非只針對第一組測資。 {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 Copyright (C) 2023 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: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 10 BogoMIPS: 5184.01 ``` ## Record ### `q_new` ```c /* Create an empty queue */ struct list_head *q_new() { struct queue_info *q = malloc(sizeof(struct queue_info)); if (!q) return NULL; INIT_LIST_HEAD(&q->head); q->size = 0; return &q->head; } ``` 配置 `queue_info` 的記憶體，如果記憶體配置失敗則返回 `NULL`。接著初始化佇列的 `head` 欄位，並將 `size` 設為 0，最後返回指向 `head` 的指標。 ### `q_free` ```c /* Free all storage used by queue */ void q_free(struct list_head *head) { if (!head) return; struct queue_info *q = container_of(head, struct queue_info, head); struct list_head *pos, *tmp; list_for_each_safe (pos, tmp, head) { element_t *entry = list_entry(pos, element_t, list); free(entry->value); free(entry); } free(q); } ``` 釋放佇列使用的所有節點。首先檢查 `head` 是否為 `NULL`，若是則直接返回。使用 `container_of` 獲取包含 `head` 的 `queue_info` 。接著使用 `list_for_each_safe` 安全地遍歷佇列中的每個節點，釋放每個元素的值和元素本身。最後釋放整個 `queue_info` 。 ### `q_insert_head` ```c /* Insert an element at head of queue */ bool q_insert_head(struct list_head *head, char *s) { if (!head || !s) return false; struct queue_info *q = container_of(head, struct queue_info, head); element_t *new = malloc(sizeof(element_t)); if (!new) return false; new->value = strdup(s); if (!new->value) { free(new); return false; } list_add(&new->list, head); q->size++; return true; } ``` ### `q_insert_tail` ```c /* Insert an element at tail of queue */ bool q_insert_tail(struct list_head *head, char *s) { if (!head || !s) return false; struct queue_info *q = container_of(head, struct queue_info, head); element_t *new = malloc(sizeof(element_t)); if (!new) return false; new->value = strdup(s); if (!new->value) { free(new); return false; } list_add_tail(&new->list, head); q->size++; return true; } ``` 使用 `malloc` 分配 `element_t` 的記憶體，若分配失敗則返回 `false`使用 `strdup` 複製字串 `s`，確保新節點擁有自己的儲存空間，避免外部修改影響佇列內部數據。若 `strdup` 失敗，釋放已分配的節點記憶體並返回 `false`，防止記憶體洩漏。使用 `list_add` 將 `new` 插入至 `head` 之後，使其成為佇列的第一個元素。透過 `container_of` 取得佇列的 `queue_info` 結構，並增加 `size`，確保佇列的大小資訊同步更新。 ### `q_remove_head` ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { struct queue_info *q = container_of(head, struct queue_info, head); if (!head || list_empty(head)) return NULL; element_t *item = list_first_entry(head, element_t, list); if (sp && bufsize > 0) { strncpy(sp, item->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&item->list); q->size--; return item; } ``` ### `q_remove_tail` ```c /* Remove an element from tail of queue */ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { struct queue_info *q = container_of(head, struct queue_info, head); if (!head || list_empty(head)) return NULL; element_t *item = list_last_entry(head, element_t, list); if (sp && bufsize > 0) { strncpy(sp, item->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&item->list); q->size--; return item; } ``` 釋放佇列使用的所有節點。首先檢查 `head` 是否為 `NULL`，若是則直接返回。使用 `container_of` 獲取包含 `head` 的 `queue_info` 。接著使用 `list_for_each_safe` 安全地遍歷佇列中的每個節點，釋放每個元素的值和元素本身。最後釋放整個 `queue_info`。 ### `q_size` ```c /* Return number of elements in queue */ int q_size(struct list_head *head) { if (!head) return 0; const struct queue_info *q = container_of(head, struct queue_info, head); return q->size; } ``` 使用`container_of` 取得 `queue_info` 結構，該結構包含佇列的 size，以此算出節點數。 ### `q_delete_mid` ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { struct queue_info *q = container_of(head, struct queue_info, head); if (!head || list_empty(head)) return false; struct list_head *slow = head->next; struct list_head *fast = head->next; while (fast != head && fast->next != head) { slow = slow->next; fast = fast->next->next; } element_t *mid = list_entry(slow, element_t, list); list_del(slow); free(mid->value); free(mid); q->size--; return true; } ``` ### `q_delete_dup` ```c /* Delete all nodes that have duplicate string */ bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) { return false; } element_t *curr = NULL, *next = NULL; bool check = false; list_for_each_entry_safe (curr, next, head, list) { if (&next->list != head && !strcmp(curr->value, next->value)) { list_del_init(&curr->list); q_release_element(curr); check = true; } else if (check) { list_del_init(&curr->list); q_release_element(curr); check = false; } } return true; } ``` ### `q_swap` ```c /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *node; list_for_each (node, head) { if (node->next == head) break; list_move(node, node->next); } } ``` 一開始會先檢查傳入的 head 是否為 `NULL` 或整個串列是否只有一個節點，這種情況下就沒必要進行交換了。先抓取串列中的第一個節點 first，然後在迴圈中處理每一對節點。 `list_del_init()` 把第一個節點從串列中拔掉，再透過`list_add()`把它加到第二個節點的後面，這樣就完成了兩個節點的前後順序交換。做完一次交換後，把 first 指標移到下一個未處理的節點，繼續處理下一對節點，直到整個串列處理完畢。 ### `q_reverse` ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *current = head, *prev = head->prev, *next = NULL; do { next = current->next; current->next = prev; current->prev = next; prev = current; current = next; } while (current != head); } ``` 運用了`list_for_each_safe` 走訪整個串列，每次遇到一個節點，就用 `list_move()` 把它移到串列的頭部。因為每次都是把節點移到最前面，最後的結果能夠達成整個串列反轉。 ### `q_reverseK` ```c /* Reverse the nodes of the list k at a time */ void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head) || k <= 1) return; struct list_head *current = head->next, *prev = head; while (current != head) { struct list_head *start = prev->next; int count = 0; // Move count declaration inside the loop while (count < k && current != head) { current = current->next; count++; } if (count == k) { struct list_head *end = current->prev; struct list_head *p = start, *n, *tmp; while (p != current) { n = p->next; tmp = p->prev; p->prev = p->next; p->next = tmp; p = n; } prev->next = end; end->prev = prev; start->next = current; current->prev = start; prev = start; } } } ``` ### `q_sort` 根據[你所不知道的C 語言: linked list 和非連續記憶體中](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)的[Merge Sort](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)，把功能拆成三個函式： `merge`, `merge_sort`, `q_sort`。 ### `merge` ```c /* Sort elements of queue in ascending/descending order */ struct list_head *merge(struct list_head *left, struct list_head *right, bool descend) { struct list_head dummy; INIT_LIST_HEAD(&dummy); struct list_head *tail = &dummy; while (left && right) { const element_t *l = list_entry(left, element_t, list); const element_t *r = list_entry(right, element_t, list); if ((strcmp(l->value, r->value) <= 0) ^ descend) { tail->next = left; left->prev = tail; left = left->next; } else { tail->next = right; right->prev = tail; right = right->next; } tail = tail->next; } tail->next = left ? left : right; if (tail->next) tail->next->prev = tail; return dummy.next; } ``` 透過 `dummy node` 讓 `tail` 指向目前串列的最後一個節點，簡化鏈結操作。 `strcmp(l->value, r->value) <= 0` 決定合併順序，透過 `descend` 參數控制升降序排列。最後的 `tail->next = left ? left : right;` 確保剩餘未合併的節點直接連接到結果串列。 ### `merge_sort` ```c /* Sort elements of queue in ascending/descending order */ struct list_head *merge_sort(struct list_head *head, bool descend) { if (!head || !head->next) return head; struct list_head *slow = head, *fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } struct list_head *mid = slow->next; slow->next = NULL; struct list_head *left = merge_sort(head, descend); struct list_head *right = merge_sort(mid, descend); return merge(left, right, descend); } ``` 利用快慢指標（slow-fast pointer）來找到串列的中點，將串列從中間切分，`slow->next = NULL` 讓左半部變成獨立的鏈結串列，右半部則從 `mid` 開始。遞迴處理左半部與右半部，確保它們分別排序完成。透過 `merge` 函式合併兩個排序後的子串列，確保整體排序完成。最終回傳合併後的有序串列。 ### `q_sort` ```c void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *first = head->next; struct list_head *last = head->prev; last->next = NULL; first->prev = NULL; struct list_head *sorted = merge_sort(first, descend); head->next = sorted; sorted->prev = head; struct list_head *tail = sorted; while (tail->next) tail = tail->next; tail->next = head; head->prev = tail; } ``` 將環狀雙向鏈結串列轉換為單向鏈結串列，讓 `merge_sort` 能夠順利運作，排序完成後再將其恢復為環狀雙向鏈結串列。由於 `merge_sort` 只處理單向鏈結串列，因此需要先讓 `head` 的前驅與最後一個節點的後繼指向 `NULL`： - `last->next = NULL;` 讓原本的最後一個節點不再連接 `head`，確保 `merge_sort` 能夠正確處理終止條件。 - `first->prev = NULL;` 使 `merge_sort` 將 `first` 當作真正的起點，避免影響前驅指標的處理。排序函式 `merge_sort` 會對 `first` 進行遞迴拆分與排序，並依據 `descend` 參數決定升序或降序排列，最後回傳排序後的鏈結串列。 `head->next` 重新指向排序後的 `sorted`，並將 `sorted->prev` 指回 `head`，確保 `head` 與首節點相連。透過 `while (tail->next)` 找到 `sorted` 的最後一個節點 `tail`，確保其 `next` 指向 `head`，並讓 `head->prev` 指回 `tail`，完整恢復環狀雙向鏈結串列的結構。 ### `q_ascend` ```c /* Remove every node which has a node with a strictly less value anywhere to * the right side of it */ int q_ascend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *cur = head->prev; const element_t *cur_e = list_entry(cur, element_t, list); while (cur != head) { struct list_head *prev = cur->prev; if (prev == head) break; element_t *prev_e = list_entry(prev, element_t, list); if (strcmp(prev_e->value, cur_e->value) > 0) { list_del(prev); free(prev_e->value); free(prev_e); struct queue_info *q = container_of(head, struct queue_info, head); q->size--; } else { cur = prev; cur_e = prev_e; } } return q_size(head); } ``` 先抓取最後一個節點 cur 及其對應的元素值 cur_e。在迴圈中，檢查 cur 前面的節點 prev 及其元素值 prev_e。如果 prev_e 的值比 cur_e 大（使用`strcmp` 比較字串），則移除 prev 節點，並釋放相關的記憶體，同時更新串列的大小。如果 prev_e 的值不大於 cur_e，則將 cur 更新為 prev，繼續往前遍歷。 ### `q_descend` ```c /* Remove every node which has a node with a strictly greater value anywhere to * the right side of it */ int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *cur = head->prev; const element_t *cur_e = list_entry(cur, element_t, list); while (cur != head) { struct list_head *prev = cur->prev; if (prev == head) break; element_t *prev_e = list_entry(prev, element_t, list); if (strcmp(prev_e->value, cur_e->value) < 0) { list_del(prev); free(prev_e->value); free(prev_e); struct queue_info *q = container_of(head, struct queue_info, head); q->size--; } else { cur = prev; cur_e = prev_e; } } return q_size(head); } ``` 移除串列中任何左側的節點，如果這些節點的值嚴格小於其右側的任何節點：同樣從串列的最後一個節點開始，往前遍歷。如果 prev_e 的值比 cur_e 小（strcmp 結果小於 0），則移除 prev 節點。否則更新 cur 為 prev，繼續遍歷。 ### `q_merge` ```c /* Merge all the queues into one sorted queue, which is in ascending/descending * order */ int q_merge(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; queue_contex_t *first = list_entry(head->next, queue_contex_t, chain); struct list_head *cur, *safe; list_for_each_safe (cur, safe, head) { if (cur == head->next) continue; queue_contex_t *ctx = list_entry(cur, queue_contex_t, chain); list_splice_init(ctx->q, first->q); } q_sort(first->q, descend); return q_size(first->q); } ``` 實作 `q_merge` 前，必須先熟知 `queue_contex_t` 這個資料結構，以及 `list_head` 所管理的佇列。該函式的目標是將 `head` 指向的所有 queue 內容合併到第一個佇列，並根據 `descend` 參數決定排序方式。首先，透過 `head->next` 取得第一個 `queue_contex_t`，作為合併後的佇列，並透過 `list_for_each_safe` 迭代 `head` 內的所有佇列。對於每個佇列，使用 `list_splice_init` 將其節點遷移到 `first->q`，確保佇列的串接與清理。在合併完成後，呼叫 `q_sort` 進行排序，並回傳最終佇列的大小，確保結果符合要求。 ## 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf) 這篇論文《Dude, is my code constant time?》介紹了一種稱為「dudect」的工具，用於評估特定程式碼在給定平台上是否以恆定時間執行。讓我來深入解析這個工具的「simulation」模式原理，以及其如何透過實驗而非理論分析來驗證時間複雜度。 ### dudect的核心原理 dudect的核心思想是運用「洩漏檢測技術」(leakage detection techniques)來評估程式的時間行為。這種方法不同於傳統的靜態分析或形式化驗證，而是直接在目標平台上測量程式的實際執行時間，然後應用統計分析來確定時間是否與輸入數據有關聯。 #### 基本流程包含三個主要步驟： 1. 對兩組不同輸入資料類別測量函數的執行時間 2. 對收集到的時間數據進行預處理 3. 應用統計測試來判斷兩組分佈是否有顯著差異 #### 輸入類別的設計 dudect採用「固定對隨機」(fix-vs-random)的測試方式。第一類輸入固定為常數值，第二類則為每次測量隨機選擇的值。這種測試策略已被證明能捕捉到廣泛的潛在洩漏。為減少環境變化的影響，dudect會隨機選擇每次測量的類別。 #### 時間測量機制在實際實現中，dudect利用現代CPU提供的週期計數器(如x86架構的TSC暫存器)來獲取精確的執行時間測量。這些硬體計數器能提供高精度的時間資訊，適合用於檢測微小的時間差異。 #### 統計分析與t檢定 dudect的核心統計方法是Welch's t-test，為 Student's t-test 的改良版本。用於確定兩個樣本是否來自具有相同平均值的總體。在dudect的情境中，t檢定用於判斷兩種輸入類別的執行時間分佈是否具有相同的平均值。 t統計量的計算公式為： ``` t = (x̄₁ - x̄₂) / sqrt(s₁²/n₁ + s₂²/n₂) ``` 其中： - μ₁, μ₂ 是兩組樣本的平均值 - s₁², s₂² 是兩組樣本的變異數 - n₁, n₂ 是兩組樣本的大小 #### percentile處理的重要性 dudect中的一個關鍵特性是對測量數據進行預處理，特別是通過百分位數(percentile)裁剪。典型的時間分佈通常向較大執行時間傾斜，這可能是由測量誤差、作業系統中斷或外部活動引起的。通過丟棄大於固定閾值(如第90百分位)的測量值，dudect能更準確地聚焦於執行時間分佈的主體部分。 ### 實作細節與問題分析讀取資料，原始的 dudect 實作約 300 行 C 程式碼，其中包含了以下關鍵處理： 1. **測量值篩選**：實作中會丟棄前 10 個測量值和最後一個測量值，因為這些可能受到快取預熱或其他系統因素的影響。 2. **百分位數處理（Percentile）**：原始 dudect 實作會丟棄大於特定百分位數的測量值，這是為了排除那些異常大的測量值，使統計分析更加穩健。 3. **排序處理**：測量值會先排序，然後再丟棄離群值。和lab0-c的比較，以下是一些可能存在的可改善的方向： 1. **缺乏百分位數處理**：lab0-c中缺少percentile處理機制，這會導致異常值(outlier)對統計分析產生過大影響，進而去影響統計結果。 2. **沒有對測量值進行排序**：lab0-c 直接丟棄前 10 個和最後一個測量值，而沒有先排序，這減弱了離群值處理的效果。 3. **前處理不足**：當測試數量超過 10000 筆時，原始實作會對測量值做 Centered product 前處理，但 lab0-c 沒有實作這一點。 ### 改進方案針對上述問題，以下是可能的改進方案： **實現robust的百分位數處理**： ```c // 對測量數據進行排序 qsort(measurements, num_measurements, sizeof(double), compare_doubles); // 根據百分位數裁剪數據 int cutoff_index = (int)(percentile * num_measurements / 100.0); int valid_measurements = num_measurements - cutoff_index; // 只使用未被裁剪的數據進行統計分析 double *valid_data = measurements + cutoff_index; ``` ### 解決方案針對上述問題，可以提出以下解決方案： 1. **添加百分位數處理**： - 實作一個機制，能夠計算測量值的百分位數，並丟棄超過特定百分位數（如 95% 或 99%）的測量值。 2. **測量值排序**： - 在丟棄離群值之前，先對所有測量值進行排序，這樣可以更準確地識別和排除真正的離群值。 3. **實作 Centered product 前處理**： - 針對大量測量數據（如超過 10000 筆），實作 Centered product 前處理，以增強統計檢定的能力。改進後的dudect實作應能夠更可靠地檢測時間側通道漏洞，特別是那些微小但可能被攻擊者利用的時間差異。通過結合實驗測量和嚴謹的統計分析，這種方法無需依賴對底層硬體行為的詳細建模，可以在各種平台上有效應用。 ## 研讀 lib/list_sort.c 研讀了 Linux 核心中 [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的實作後，此實作特別之處在於它與教科書*Introduction to Algorithms* 26.3 Parallel merge sort 所提及的合併排序演算法有顯著差異。 ### 程式碼組成概述此實作包含三個主要函式： 1. `merge` - 執行兩個已排序串列的基本合併 2. `merge_final` - 結合最終合併並恢復雙向鏈結結構 3. `list_sort` - 主要排序函式，採用優化的自底向上方法 ### 創新之處：平衡合併的buttom up方法此實作的特別之處在於其平衡合併的方法： - 使用「pending lists」的方式維護已排序的子串列 - 只在有效益時進行合併（維持 2:1 的平衡） - 透過確保 3*2^k 個元素能放入快取來避免快取衝突（Cache thrashing） ### 演算法運作方式 `list_sort` 函式順序遍歷串列，並在過程中建立已排序的子串列： 1. 維護一系列待處理的已排序子串列 2. 每個子串列的大小為 2 的冪次（2^k） 3. 利用 `count` 變數的巧妙位元操作技術來決定何時合併 `count` 變數追蹤已處理的元素數量，其二進制表示決定了哪些子串列需要合併。每次 `count` 增加時，它會設置一個位元（位元 k）並清除位元 k-1 至 0。合併發生在： - 我們有兩個大小為 2^k 的子串列 - 且我們有足夠的後續元素（另一個 2^k） ### 合併過程合併過程是透過檢查 `count` 中最低的清零位元來處理。當演算法決定合併兩個子串列時： 1. 它選擇適當大小的最近創建的兩個子串列 2. 使用保持穩定性的 `merge` 函式合併它們 3. 將合併結果放回待處理串列結構中 ### 最終步驟一旦所有元素都被處理，剩餘的待處理子串列會從最小到最大依序合併。`merge_final` 函式完成最後的合併，同時恢復串列的循環雙向鏈結結構。 ### 性能考量此實作做了幾項改善： - 透過策略性合併避免快取衝突 - 它是穩定的（相同元素保持原始順序） - 不需要額外空間（除了待處理串列指針的 O(log n)） - 相較於標準合併排序減少了比較次數實作過程中，走訪時一一將 `next` 斷開並且把 `next` 當成執行 merge 動作時走訪的鏈結，比較[「你所不知道的 C 語言: linked list 和非連續記憶體」](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)所提及的遞迴與非遞迴，省去了 divide 這部分，也避免了使用堆疊可能產生的深度限制問題。 ## Valgrind 排除 qtest 實作的記憶體錯誤 [Valgrind](https://valgrind.org/)提供動態分析，用來追蹤及分析程式效能，幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。最初在未啟用 ASan 時，執行make valgrind，測試則全部通過，沒有顯示記憶體錯誤資訊。 ``` tyler@tyler:~/lab0-c$ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/tyler/lab0-c' rm -f 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 .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o CC shannon_entropy.o CC linenoise.o CC web.o LD qtest make[1]: Leaving directory '/home/tyler/lab0-c' cp qtest /tmp/qtest.UMIOyd chmod u+x /tmp/qtest.UMIOyd sed -i "s/alarm/isnan/g" /tmp/qtest.UMIOyd scripts/driver.py -p /tmp/qtest.UMIOyd --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of 'q_new', 'q_insert_head', and 'q_remove_head' --- trace-01-ops 5/5 +++ TESTING trace trace-02-ops: # Test of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_remove_tail', and 'q_delete_mid' --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of 'q_new', 'q_insert_head', 'q_remove_head', 'q_reverse', 'q_sort', and 'q_merge' --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of 'q_new', 'q_insert_tail', 'q_insert_head', 'q_remove_head', 'q_size', 'q_swap', and 'q_sort' --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', 'q_swap', and 'q_sort' --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: # Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_delete_dup', 'q_sort', 'q_descend', and 'q_reverseK' --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: # Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort' --- trace-07-string 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue: 'q_new', 'q_remove_head', 'q_reverse', 'q_size', and 'q_sort' --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test 'q_remove_head' with NULL argument: 'q_new', 'q_insert_head', and 'q_remove_head' --- trace-09-robust 6/6 +++ TESTING trace trace-10-robust: # Test operations on NULL queue: 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', and 'q_sort' --- trace-10-robust 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on 'q_insert_head': 'q_new', and 'q_insert_head' --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on 'q_insert_tail': 'q_new', 'q_insert_head', and 'q_insert_tail' --- trace-12-malloc 6/6 +++ TESTING trace trace-13-malloc: # Test of malloc failure on 'q_new': 'q_new' --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort' Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000. --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse' # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse' --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant Testing insert_tail...(5/10) Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.UMIOyd --valgrind -t <tid> ``` 在啟用 `Address Sanitizer`後，發生了 segmentation fault 和 time limit exceeded 的問題。 ``` +++ TESTING trace trace-14-perf: # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort' ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Insertion of dolphin failed (1 failures total) ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Insertion of gerbil failed (2 failures total) Warning: Skip checking the stability of the sort because the number of elements 1749161 is too large, exceeds the limit 100000. --- trace-14-perf 0/6 ``` ``` +++ TESTING trace trace-16-perf: # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse' ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Insertion of dolphin failed (1 failures total) ERROR: Freed queue, but 1 blocks are still allocated --- trace-16-perf 0/6 ``` ## Massif 使用 Massif 觀察記憶體使用情況，輸入命令`valgrind -v --tool=massif ./qtest -f traces/trace-01-ops.cmd` 產生輸出檔 `massif.out.394797` 接著輸入命令`massif-visualizer ./massif.out.394797`讀取上述指令產生的輸出檔，以下為結果: ![image](https://hackmd.io/_uploads/SyP1jrCsJx.png) 以`traces/trace-01-ops.cmd` 為例，可以發現所有分配的記憶體在最後會完全被釋放 ## 研讀 select(2) select(2)是Linux系統用於同步I/O分頻多工。允許程序監視多個文件描述符，等待其中之一或多個變為"Ready"狀態，而無需持續輪詢。關於超時處理機制 select的一個關鍵特性是它的超時參數： ```c struct timeval { time_t tv_sec; /* 秒 */ suseconds_t tv_usec; /* 微秒 */ }; ``` 因此select能夠成為實現超時檢測的工具： - 設置timeout為NULL時，select會無限期阻塞 - 設置timeout的兩個字段都為0時，select立即返回（輪詢模式） - 設置特定的超時值時，select會等待指定時間後返回 ### 內建Web伺服器實現 1.編譯專案 (確認已安裝所有依賴) ```c $ make clean && make ``` 2.啟動 qtest 互動式介面 ```c $ ./qtest ``` 3.在 qtest 提示符下執行 web 命令 ```c (base) tyler@tyler:~/lab0-c$ ./qtest cmd> web listen on port 9999, fd is 3 cmd> l = [] cmd> l = [] cmd> l = [reference link] ``` 4.開啟另一個終端機以此來驗證 Web 伺服器 ```c (base) tyler@tyler:~$ cd lab0-c/ (base) tyler@tyler:~/lab0-c$ curl http://localhost:9999/new (base) tyler@tyler:~/lab0-c$ curl http://localhost:9999/new (base) tyler@tyler:~/lab0-c$ curl http://localhost:9999/new ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.