# 2021q1 Homework1 (lab0) contributed by < `shanihsu` > ###### tags: `linux2021` > [作業要求](https://hackmd.io/@sysprog/linux2021-lab0) ## 開發環境 ``` $ cat /etc/os-release NAME="Ubuntu" VERSION="20.04.1 LTS (Focal Fossa)" $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 ``` ## 實作程式 > [GitHub](https://github.com/shanihsu/lab0-c) ### 定義 `queue_t` 為了使 `q_insert_tail` 和 `q_size` 滿足 O(1) 時間複雜度,加入`tail`跟`size`。 * `tail` : queue的尾端記憶體位置 * `size` : queue的元素個數 ```c= typedef struct { list_ele_t *head; int size; list_ele_t *tail; } queue_t; ``` ### 實作 `q_new` * 將 `size` 跟 `tail` 初始化 * 當 `malloc` 回傳 NULL 時,代表記憶體分配空間錯誤,則 `q_new` 所指向的位置為 NULL。 ```c= queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ### 實作 `q_free` * 先檢查 `q` 是否為空,若 `q` 有指向的記憶體位置,則至 `queue` 的 `head` 開始搜尋可釋放的空間。 * 使用 while loop ,從 `queue` 的 `head` 開始,依次將 `queue` 中的元素及儲存 `value` 的記憶體釋放掉。 * 最後再將 `q` 釋放。 ```c= void q_free(queue_t *q) { if (q) { while (q->head) { list_ele_t *tmp; tmp = q->head; free(tmp->value); q->head = tmp->next; free(tmp); } free(q); } } ``` ### 實作 `q_insert_head` * 當 `q` 非空時, `malloc` 一段記憶體空間給 `queue` ,並確保記憶體空間足夠,同時以 `newh` 儲存 `queue` 的起始記憶體位置。 * 計算字串所需長度:字元 `s` 長度,加上一個結束字元 `\0` * `malloc` 一段記憶體空間儲存欲插入元素的 `value`,若 `malloc`錯誤,需將先前儲存 `newh` 的記憶體區段釋放,以避免 memory leak 。 * 若 `q->head` 是 NULL ,表示 queue 中沒有元素,插入元素 `newh` 後,該 queue 的 `head` 跟 `tail` 均為此新元素 `tail` 。 ```c= bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (!q) return false; if (!(newh = malloc(sizeof(list_ele_t)))) return false; size_t len = strlen(s) + 1; if (!(newh->value = malloc(len * sizeof(char)))) { free(newh); return false; } memcpy(newh->value, s, len); newh->next = q->head; if (!q->head) q->tail = newh; q->head = newh; q->size++; return true; } ``` ### 實作`q_insert_tail` * 新增 `tail` 在 struct `queue_t` 中,以達成 O(1) 時間複雜度 * 在 insert 新的元素時,可直接將 `queue` 的 `tail->next` 設成新元素,不須每次重新搜尋 `queue` 的尾端 ```c= bool q_insert_tail(queue_t *q, char *s) { list_ele_t *newh; if (!q) return false; if (!(newh = malloc(sizeof(list_ele_t)))) return false; size_t len = strlen(s) + 1; if (!(newh->value = malloc(len * sizeof(char)))) { free(newh); return false; } memcpy(newh->value, s, len); newh->next = NULL; if (!q->head) { q->head = newh; } else { q->tail->next = newh; } q->tail = newh; q->size++; return true; } ``` ### 實作 `q_remove_head` * 檢查 `q` 跟 `q->head` 是否為空 * 檢查 `sp` 是否為空,並比較 `head->value` 字元長度與 `bufsize` 大小,並將 `head->value` 字元儲存到 `sp` 。 * 最後再將 `head` 及儲存 `head->value` 的記憶體釋放掉 ```c= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head) return false; size_t len = strlen(q->head->value); if (sp) { if (len < bufsize) { memcpy(sp, q->head->value, len); sp[len] = '\0'; } else { memcpy(sp, q->head->value, bufsize - 1); sp[bufsize - 1] = '\0'; } } list_ele_t *tmp; tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); q->size--; return true; } ``` * 當 `head->value` 字元長度小於 `bufsize` 時,字元 `head->value` 在存入 `sp` 後,需加上 `\0` ,也就是上面程式碼中的第9行,若沒有加,會導致 `bufsize` 找不到終止字元不斷輸出,而產生以下情況: ``` $ ./qtest cmd> new q = [] cmd> ih monkey q = [monkey] cmd> rh Removed monkeyXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX from queue q = [] ``` * 原本在上述程式碼中的第17,18行中間有加入以下程式碼: ```c= if (!q->head){ free(q->tail->value); free(q->tail); } ``` `make` 後執行得到以下錯誤訊息: ``` $ ./qtest cmd> new q = [] cmd> ih monkey q = [monkey] cmd> rh ERROR: Attempted to free unallocated block. Address = 0x5555555555555555 Bus error (core dumped) ``` 由上述錯誤訊息得知,當 `queue` 中只剩下一個元素時,其 `head` 跟 `tail` 指向的記憶體位置相同,若將 `tail` free 掉之後,再 free `head` 會導致 free unallocated block 。 ### 實作 `q->size` * 檢查 `q` 跟 `q->head` 是否為空,若為空,直接 return 0,若非空,則 return `q->size` 。 ```c= int q_size(queue_t *q) { if (!q || !q->head) { return 0; } return q->size; } ``` * 原先在上述程式碼中第4行是寫: ```c=4 q->size = 0; ``` `make` 後執行得到以下錯誤訊息: ``` $ ./qtest cmd> free q = NULL cmd> size Warning: Calling size on null queue Segmentation fault occurred. You dereferenced a NULL or invalid pointer Aborted (core dumped) ``` 由上述得知,因為 `queue` 是 NULL,所以 `q->size` 尚未被宣告,將其賦值會出錯。 ### 實作 `q_reverse` * 當 `q` 及 `q->head` 及 `q->head->next`都非空時,需要做 reverse * 使用 while loop ,反覆執行將 node 斷開後重新反向鏈結,直到 `q->head->next` 為空, while loop 中的變數意義如下: * `prev` : 儲存當下已完成 reverse 的 `queue` 之 `head` * `q->head` : 儲存當下欲斷開 link 的 node 位置 * `current` : 儲存當下欲斷開 link 的 node 所連接的下一個 node 位置 ```c= void q_reverse(queue_t *q) { if (!(!q || !q->head || !q->head->next)) { list_ele_t *current = q->head->next; list_ele_t *prev = q->head; prev->next = NULL; q->tail = prev; q->head = current; while (q->head->next) { current = q->head->next; q->head->next = prev; prev = q->head; q->head = current; } q->head->next = prev; } } ``` * 開發初期,第七行程式碼漏加, reverse 後沒有設定好 `tail` ,導致 queue 在 reverse 後, cmd 中執行 `size` 指令結果跟 `queue` 中實際的元素個數不同,其後執行的指令均有誤,且最後 `free` 時,無法完全釋放記憶體,造成以下錯誤訊息: ``` $ ./qtest cmd> new q = [] cmd> ih dog q = [dog] cmd> ih cat q = [cat dog] cmd> ih monkey q = [monkey cat dog] cmd> reverse q = [dog cat monkey] cmd> it fish q = [dog fish] cmd> size Queue size = 4 q = [dog fish] cmd> free q = NULL ERROR: Freed queue, but 4 blocks are still allocated ``` ### 實作 `q_sort` * 使用 merge sort 排序,排序後將 `tail` 重新設置 * merge sort 分成 split 跟 merge排序 兩部份,在 split 部份使用 recursive ,在 merge 排序部份使用 while loop * 使用 strcmp 函式先比 `value` 大小,再由此順序排序 ```c= void q_sort(queue_t *q) { if (!q || !q->head || !q->head->next) { return; } q->head = merge_sort(q->head); list_ele_t *tmp = q->head; while (tmp->next) { tmp = tmp->next; } q->tail = tmp; } list_ele_t *merge_sort(list_ele_t *head) { if (!head || !head->next) return head; list_ele_t *fast = head->next; list_ele_t *slow = head; // split list while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; // sort each list list_ele_t *lhs = merge_sort(head); list_ele_t *rhs = merge_sort(fast); // merge sorted lhs and sorted rhs list_ele_t *tmp = NULL; if (lhs && rhs) { if (strcmp(lhs->value, rhs->value) < 0) { head = lhs; lhs = lhs->next; } else { head = rhs; rhs = rhs->next; } } tmp = head; while (lhs && rhs) { if (strcmp(lhs->value, rhs->value) < 0) { tmp->next = lhs; tmp = tmp->next; lhs = lhs->next; } else { tmp->next = rhs; tmp = tmp->next; rhs = rhs->next; } } if (lhs) tmp->next = lhs; if (rhs) tmp->next = rhs; return head; } ``` * 最一開始參考[作業要求](https://hackmd.io/@sysprog/linux2021-lab0)中的 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 資料,將 merge sort 的 merge 部份也用 recursive 完成,實作後發現會 segmentation fault ,改用 while loop 完成 merge 部份,即可通過評分。 * 下方為 merge 部份使用 recursive 完成的程式碼: ```c= void q_sort(queue_t *q) { if (!q || !q->head || !q->head->next) { return; } q->head = merge_sort(q->head); list_ele_t *tmp = q->head; while (tmp->next) { tmp = tmp->next; } q->tail = tmp; } list_ele_t * merge(list_ele_t *lhs, list_ele_t *rhs) { // merge with recursive if (!rhs){ return lhs; } if (!lhs){ return rhs; } if (strcmp(lhs->value, rhs->value) < 0) { lhs->next = merge(lhs->next, rhs); return lhs; } else { rhs->next = merge(lhs, rhs->next); return rhs; } } list_ele_t *merge_sort(list_ele_t *head) { if (!head || !head->next) return head; list_ele_t *fast = head->next; list_ele_t *slow = head; // split list while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; // sort each list list_ele_t *lhs = merge_sort(head); list_ele_t *rhs = merge_sort(fast); return merge(lhs, rhs); } ``` `make` 後執行結果,在 `queue` 元素個數小於 1000000 個時,均可正常排序,但在 `queue` 元素個數大於 1000000 個時(例如 : trace-15-perf.cmd 檔案),會造成 Segmentation fault ,使用 Valgrind 追蹤 trace-15-perf.cmd 這個檔案,結果如下: ``` $ valgrind -q --leak-check=full ./qtest -v 3 -f traces/trace-15-perf.cmd ==9406== ./.valgrindrc was not read as it is either not a regular file, ==9406== or is world writeable, or is not owned by the current user. ==9406== Invalid read of size 8 ==9406== at 0x10B09B: do_sort (qtest.c:564) ==9406== by 0x10CE65: interpret_cmda (console.c:221) ==9406== by 0x10D2FC: interpret_cmd (console.c:244) ==9406== by 0x10DB3F: cmd_select (console.c:594) ==9406== by 0x10DE0C: run_console (console.c:667) ==9406== by 0x10C2BF: main (qtest.c:788) ==9406== Address 0x0 is not stack'd, malloc'd or (recently) free'd ==9406== Segmentation fault occurred. You dereferenced a NULL or invalid pointer Aborted (core dumped) ``` :::warning 由上述錯誤訊息得知,造成 segmentation fault 的原因是 `Invalid read of size 8` ,試圖讀取一個非法的區域,更進一步追蹤結果如下: ::: ``` $ scripts/driver.py -p /tmp/qtest.p1jRLH --valgrind -t 15 --- Trace Points +++ TESTING trace trace-15-perf: ==10126== ./.valgrindrc was not read as it is either not a regular file, ==10126== or is world writeable, or is not owned by the current user. ==10126== Memcheck, a memory error detector ==10126== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==10126== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==10126== Command: /tmp/qtest.p1jRLH -v 1 -f ./traces/trace-15-perf.cmd ==10126== # Test performance of insert_tail, size, reverse, and sort ==10126== Stack overflow in thread #1: can't grow stack to 0x1ffe801000 ==10126== Stack overflow in thread #1: can't grow stack to 0x1ffe801000 ==10126== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1: ==10126== no stack segment ==10126== ==10126== Process terminating with default action of signal 11 (SIGSEGV) ==10126== Access not within mapped region at address 0x1FFE8010A8 ==10126== Stack overflow in thread #1: can't grow stack to 0x1ffe801000 ==10126== at 0x10E589: merge (queue.c:257) ==10126== If you believe this happened as a result of a stack ==10126== overflow in your program's main thread (unlikely but ==10126== possible), you can try to increase the size of the ==10126== main thread stack using the --main-stacksize= flag. ==10126== The main thread stack size used in this run was 8388608. ==10126== Stack overflow in thread #1: can't grow stack to 0x1ffe801000 ==10126== ==10126== Process terminating with default action of signal 11 (SIGSEGV) ==10126== Access not within mapped region at address 0x1FFE801F70 ==10126== Stack overflow in thread #1: can't grow stack to 0x1ffe801000 ==10126== at 0x4831134: _vgnU_freeres (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_core-amd64-linux.so) ==10126== If you believe this happened as a result of a stack ==10126== overflow in your program's main thread (unlikely but ==10126== possible), you can try to increase the size of the ==10126== main thread stack using the --main-stacksize= flag. ==10126== The main thread stack size used in this run was 8388608. ==10126== ==10126== HEAP SUMMARY: ==10126== in use at exit: 207,010,436 bytes in 4,000,050 blocks ==10126== total heap usage: 4,000,094 allocs, 44 frees, 207,015,514 bytes allocated ==10126== ==10126== LEAK SUMMARY: ==10126== definitely lost: 0 bytes in 0 blocks ==10126== indirectly lost: 0 bytes in 0 blocks ==10126== possibly lost: 0 bytes in 0 blocks ==10126== still reachable: 207,010,436 bytes in 4,000,050 blocks ==10126== suppressed: 0 bytes in 0 blocks ==10126== Rerun with --leak-check=full to see details of leaked memory ==10126== ==10126== For lists of detected and suppressed errors, rerun with: -s ==10126== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) --- trace-15-perf 0/6 --- TOTAL 0/6 ``` :::warning 由上述追蹤結果發現, 錯誤訊息顯示 `Stack overflow in thread #1: can't grow stack to 0x1ffe801000` ,懷疑其是因為執行 recursive 過程, stack 不斷堆疊沒有釋放,導致記憶體不足而 segmentation fault ,為了驗證此推論,使用 Massif 工具加以分析,得到以下的圖。 ::: ![](https://i.imgur.com/646qfHI.png) :::warning * 由上圖可看出記憶體使用狀況,在 recursive 過程不斷升高,但因在 trace-15-perf.cmd 檔案中的指令本身就沒有 `free` ,所以這樣的記憶體使用狀況是合理的,無法由此看出 segmentation fault 的原因。 * 因為暫時無法找出哪裡出錯,我將 merge sort 中 merge 的部份改用 while loop 代替 recursive 實作,以通過評分。 ::: :::info 疑問 : 目前還無法肯定導致 segmentation fault 的原因,只能歸納出以下兩種可能 : 1. merge sort 中 merge 的部份如果使用 recursive 來撰寫,會影響其記憶體使用空間。 2. 在我上述已撰寫的程式碼中, function `merge` 邏輯考慮不完整,導致讀取一個非法的區域。 ::: ## 以 Valgrind 分析記憶體問題 ### 安裝 ``` $ sudo apt install massif-visualizer ``` ### 測試 ``` $ make valgrind ``` 執行後某部份結果如下 : ``` +++ TESTING trace trace-17-complexity: ==19887== ./.valgrindrc was not read as it is either not a regular file, ==19887== or is world writeable, or is not owned by the current user. ==19887== Memcheck, a memory error detector ==19887== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==19887== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==19887== Command: /tmp/qtest.lRmLYV -v 1 -f ./traces/trace-17-complexity.cmd ==19887== # Test if q_insert_tail and q_size is constant time complexity Probably constant time Probably constant time ==19887== ==19887== HEAP SUMMARY: ==19887== in use at exit: 311 bytes in 21 blocks ==19887== total heap usage: 94,736,463 allocs, 94,736,442 frees, 4,922,653,226 bytes allocated ==19887== ==19887== LEAK SUMMARY: ==19887== definitely lost: 0 bytes in 0 blocks ==19887== indirectly lost: 0 bytes in 0 blocks ==19887== possibly lost: 0 bytes in 0 blocks ==19887== still reachable: 311 bytes in 21 blocks ==19887== suppressed: 0 bytes in 0 blocks ==19887== Rerun with --leak-check=full to see details of leaked memory ==19887== ==19887== For lists of detected and suppressed errors, rerun with: -s ==19887== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` 由上述執行結果可知 * 在 HEAP SUMMARY 中, `total heap usage: 94,736,463 allocs, 94,736,442 frees, 4,922,653,226 bytes allocated` ,由此可看出,==還有 `94,736,463 - 94,736,442 = 21` 的記憶體沒有被釋放,但程式並沒有因此出錯,是為何呢?== * 在 LEAK SUMMARY 中, `still reachable: 311 bytes in 21 blocks` ,表示程式結束時有未釋放的記憶體,==較疑惑的是,既然記憶體沒有被完全釋放,為何評分程式會給過呢?== 也可使用以下指令測試單一個 case , `<tid>` 為 cmd 檔案的編號。 ``` $ scripts/driver.py -p /tmp/qtest.lRmLYV --valgrind -t <tid> ``` ### 搭配視覺化工具 Massif * 執行以下指令可產生一個 massif.out 檔, e.g. massif.out.20796 * 參數 <test-data> 為欲 test 的 file 名稱, e.g. traces/trace-0x-ops.cmd ``` $ valgrind --tool=massif ./qtest -f <test-data> ``` * 執行以下指令,將上述指令產生的 massif.out 檔視覺化 * 參數 <file-name> 為上述指令產生的 massif.out 檔案名稱, e.g. massif.out.20796 ``` $ massif-visualizer <file-name> ``` 執行結果如下 : ![](https://i.imgur.com/stHf1po.png) :::info 當程式執行結束時,記憶體需要被完全釋放,故此圖最終點應落在 0。 :::