2021q1 Homework1 (lab0)

# 2021q1 Homework1 (lab0) contributed by < `cyrong` > ## 實作過程為了讓 `q_size` 以及 `q_insert_tail` 時間複雜度為 $O(1)$ 修改 `queue.h` 新增 size 以及 tail 兩個元素 ```c /* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ int size; /* Size of linked list */ list_ele_t *tail; /* Tail of linked list */ } queue_t; ``` ### `q_new()` 建立一個 `queue` 如果成功回傳此 `queue` 否則回傳 `NULL` 先 `malloc` 給 `q` 檢查 `malloc` 有無成功成功就初始 `q` ， head : `NULL` 、 tail : `NULL` 、 size : `0` 失敗就回傳 `NULL` ```c queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (q != NULL) { q->head = NULL; q->size = 0; q->tail = NULL; } return q; } ``` ### `q_free()` 釋放 `q` 中所有分配的記憶體檢查 `q` 是否為 `NULL` 釋放字串 -> 釋放元素 -> 釋放 `q` ```c void q_free(queue_t *q) { if (q) { list_ele_t *tmp = q->head; while (q->head) { q->head = q->head->next; free(tmp->value); free(tmp); tmp = q->head; } } else return; free(q); } ``` ### `q_insert_head()` 從頭插入一個元素檢查 `q` 以及分配的 `newh`, `newh->value` 是否為 `NULL` 再來就是把 `newh` 加進 `q` 若是 `q` 中沒有元素， `q->tail` 也要作設定最後 `q->size += 1` ```c bool q_insert_head(queue_t *q, char *s) { if (!q) return false; list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(sizeof(char) * strlen(s) + 1); if (!newh->value) { free(newh); return false; } strncpy(newh->value, s, strlen(s) + 1); newh->next = q->head; q->head = newh; if (q->size == 0) q->tail = newh; q->size += 1; return true; } ``` ### `q_insert_tail()` 從尾端插入一個元素整體來說與 `q_insert_head()` 差不多最後加到 `tail` 的話要把原本 `tail->next` 設定成 `newt` ```c bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; list_ele_t *newt; newt = malloc(sizeof(list_ele_t)); if (!newt) return false; newt->value = malloc(sizeof(char) * strlen(s) + 1); if (!newt->value) { free(newt); return false; } strncpy(newt->value, s, strlen(s) + 1); newt->next = NULL; if (q->size == 0) q->head = newt; else q->tail->next = newt; q->tail = newt; q->size += 1; return true; } ``` ### `q_remove_head()` 從 `head` 移除一個元素，成功時回傳 `true` 否則回傳 `false` 檢查 `q` 是否是 `NULL` 再來才是檢查 `head` 、 `tail` 為了 `q` 是 `NULL` 時 `dereference` 到 `NULL` ```c bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q) return false; if (q->size == 0) return false; list_ele_t *tmp = q->head; if (sp) { int maxlen = bufsize - 1 > strlen((q->head)->value) ? strlen((q->head)->value) : bufsize - 1; strncpy(sp, (q->head)->value, maxlen); sp[maxlen] = '\0'; } q->head = tmp->next; q->size -= 1; free(tmp->value); free(tmp); return true; } ``` ### `q_size()` 回傳 `q` 的元素個數若 `q` 是 `empty` 或 `NULL` 回傳 `0` 否則回傳元素個數 ```c int q_size(queue_t *q) { return q ? q->size : 0; } ``` ### `q_reverse()` 將 `q` 中的元素順序反轉 ```c void q_reverse(queue_t *q) { if (!q) return; if (q->size <= 1) return; list_ele_t *prev = NULL; list_ele_t *cur = q->head; list_ele_t *next = NULL; q->tail = q->head; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } q->head = prev; } ``` ### `q_sort` 利用的 sort 手法是 mergesort 因此新增 `merge` 與 `mergeSortList` 兩個函式其中 `merge` 使用的是 iterative 版本使用 recursive 版本會導致自動評分程式複雜度測試 fail 應該是重複呼叫函式的成本過高 ```c list_ele_t *merge(list_ele_t *l1, list_ele_t *l2) { list_ele_t *result; list_ele_t **tmp = &result; while (l1 && l2) { if (strcmp(l1->value, l2->value) < 0) { *tmp = l1; l1 = l1->next; } else { *tmp = l2; l2 = l2->next; } tmp = &((*tmp)->next); } if (l1) *tmp = l1; if (l2) *tmp = l2; return result; } ``` ```c list_ele_t *mergeSortList(list_ele_t *head) { if (!head) return head; if (!head->next) return head; list_ele_t *fast = head->next; list_ele_t *slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; list_ele_t *l1 = mergeSortList(head); list_ele_t *l2 = mergeSortList(fast); return merge(l1, l2); } ``` [參考文章](https://npes87184.github.io/2015-09-12-linkedListSort/) ## 使用Address Sanitizer 開啟 Address Sanitizer 後執行 `qtest` 並在 cmd 輸入 help 會得到以下錯誤 ```c cmd> help Commands: # ... | Display comment free | Delete queue help | Show documentation 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 new | Create new queue option [name val] | Display or set options quit | Exit program reverse | Reverse queue rh [str] | Remove from head of queue. Optionally compare to expected value str rhq | Remove from head of queue without reporting value. show | Show queue contents size [n] | Compute queue size n times (default: n == 1) sort | Sort queue in ascending order source file | Read commands from source file time cmd arg ... | Time command execution Options: ================================================================= ==19783==ERROR: AddressSanitizer: global-buffer-overflow on address 0x562cb765a3c0 at pc 0x562cb76437bd bp 0x7ffde7d1b7a0 sp 0x7ffde7d1b790 READ of size 4 at 0x562cb765a3c0 thread T0 #0 0x562cb76437bc in do_help_cmd /home/amagi/linux2021/lab0-c/console.c:307 #1 0x562cb76438d0 in interpret_cmda /home/amagi/linux2021/lab0-c/console.c:221 #2 0x562cb76440b5 in interpret_cmd /home/amagi/linux2021/lab0-c/console.c:244 #3 0x562cb76457f8 in run_console /home/amagi/linux2021/lab0-c/console.c:660 #4 0x562cb76423e5 in main /home/amagi/linux2021/lab0-c/qtest.c:780 #5 0x7f3263fd60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #6 0x562cb763fb8d in _start (/home/amagi/linux2021/lab0-c/qtest+0x8b8d) 0x562cb765a3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x562cb765a3c0) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /home/amagi/linux2021/lab0-c/console.c:307 in do_help_cmd Shadow bytes around the buggy address: 0x0ac616ec3420: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 0x0ac616ec3430: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0ac616ec3440: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 0x0ac616ec3450: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 0x0ac616ec3460: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 =>0x0ac616ec3470: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 0x0ac616ec3480: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 0x0ac616ec3490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac616ec34a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac616ec34b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac616ec34c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==19783==ABORTING ``` 從中可以發現是 `console.c` 有問題看到 summary 的地方發現是 global variable '`echo`' 發生了錯誤進入 `console.c` 觀察 `echo` ```c /* Parameters */ static int err_limit = 5; static int err_cnt = 0; static bool echo = 0; ``` `echo` 型態是 `bool` 接下來繼續尋找 `echo` 的足跡在函式 `init_cmd()` 中 ```c add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); ``` 函式 `set_echo` 中 ```c void set_echo(bool on) { echo = on ? 1 : 0; } ``` 其餘出現部份都是在 if 中因此不會改變到 `echo` 的值其中 `set_echo()` 看起來沒什麼問題因此聚焦在 `add_param` ```c void add_param(char *name, int *valp, char *documentation, setter_function setter) { param_ptr next_param = param_list; param_ptr *last_loc = &param_list; while (next_param && strcmp(name, next_param->name) > 0) { last_loc = &next_param->next; next_param = next_param->next; } param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param"); ele->name = name; ele->valp = valp; ele->documentation = documentation; ele->setter = setter; ele->next = next_param; *last_loc = ele; } ``` 功能是最終建立一個 element 並指派到 `last_loc` type 是 `param_ptr` 因此前去觀察 `param_ptr` 在 `console.h` 中 ```c /* Integer-valued parameters */ typedef struct PELE param_ele, *param_ptr; struct PELE { char *name; int *valp; char *documentation; /* Function that gets called whenever parameter changes */ setter_function setter; param_ptr next; }; ``` 從中觀察到對 `echo` 進行數值指派之處在 `valp` ，type 是 `int *` 但是傳入 `add_param` 的 `echo` 是被強制轉變成 `int *` 的 `bool` 導致後續使用到 `last_loc` 的地方看到一開始標出的錯誤位置 ```c #0 0x562cb76437bc in do_help_cmd /home/amagi/linux2021/lab0-c/console.c:307 ``` ```c static bool do_help_cmd(int argc, char *argv[]) { cmd_ptr clist = cmd_list; report(1, "Commands:", argv[0]); while (clist) { report(1, "\t%s\t%s", clist->name, clist->documentation); clist = clist->next; } param_ptr plist = param_list; report(1, "Options:"); while (plist) { report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, //<-- here 307 plist->documentation); plist = plist->next; } return true; } ``` `*plist->valp` 的部份出錯了因此初步判斷是 `echo` 的 type 問題因為 type `bool` 占的空間和 `int` 不一樣 (`bool` 1 byte `int` 4 bytes) `%d` 會去存取的大小會是 `int` 的大小所以存取身為 `bool` 的 `echo` 會超出記憶體範圍修改成以下的樣子 ```c static int echo = 0; ``` 而執行 `make test` 時也出現相同狀況 ```c amagi@amagi-MacBookAir:~/linux2021/lab0-c$ make test scripts/driver.py -c --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings --- trace-06-string 6/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of sort with random and descending orders # 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-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity ================================================================= ==19755==ERROR: AddressSanitizer: global-buffer-overflow on address 0x56197ae895e0 at pc 0x56197ae71ae8 bp 0x7ffe3caddf50 sp 0x7ffe3caddf40 READ of size 4 at 0x56197ae895e0 thread T0 #0 0x56197ae71ae7 in do_option_cmd /home/amagi/linux2021/lab0-c/console.c:369 #1 0x56197ae708d0 in interpret_cmda /home/amagi/linux2021/lab0-c/console.c:221 #2 0x56197ae710b5 in interpret_cmd /home/amagi/linux2021/lab0-c/console.c:244 #3 0x56197ae722e1 in cmd_select /home/amagi/linux2021/lab0-c/console.c:594 #4 0x56197ae7285b in run_console /home/amagi/linux2021/lab0-c/console.c:667 #5 0x56197ae6f3e5 in main /home/amagi/linux2021/lab0-c/qtest.c:780 #6 0x7f45471c70b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #7 0x56197ae6cb8d in _start (/home/amagi/linux2021/lab0-c/qtest+0x8b8d) 0x56197ae895e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x56197ae895e0) of size 1 'simulation' is ascii string '' SUMMARY: AddressSanitizer: global-buffer-overflow /home/amagi/linux2021/lab0-c/console.c:369 in do_option_cmd Shadow bytes around the buggy address: 0x0ac3af5c9260: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac3af5c9270: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac3af5c9280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac3af5c9290: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0ac3af5c92a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 =>0x0ac3af5c92b0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 0x0ac3af5c92c0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9 0x0ac3af5c92d0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 0x0ac3af5c92e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ac3af5c92f0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 0x0ac3af5c9300: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==19755==ABORTING --- trace-17-complexity 0/5 --- TOTAL 95/100 ``` 觀察 `simulation` ```c /* Some global values */ bool simulation = 0; ``` 在 `init_cmd` ```c add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL); ``` 型態 `bool` 並被強制轉換 `int *` 看起來與 `echo` 是相同問題因此修改 `console.c` 以及 `console.h` `console.c` ： ```c /* Some global values */ int simulation = 0; ``` `console.h` ：原 ```c /* Simulation flag of console option */ extern bool simulation; ``` 修改後 ```c /* Simulation flag of console option */ extern int simulation; ``` 最終執行結果： ```c ./qtest cmd> help Commands: # ... | Display comment free | Delete queue help | Show documentation 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 new | Create new queue option [name val] | Display or set options quit | Exit program reverse | Reverse queue rh [str] | Remove from head of queue. Optionally compare to expected value str rhq | Remove from head of queue without reporting value. show | Show queue contents size [n] | Compute queue size n times (default: n == 1) sort | Sort queue in ascending order source file | Read commands from source file time cmd arg ... | Time command execution Options: echo 1 Do/don't echo commands 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 malloc 0 Malloc failure probability percent simulation 0 Start/Stop simulation mode verbose 4 Verbosity level cmd> quit Freeing queue ``` ```c make test scripts/driver.py -c --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings --- trace-06-string 6/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of sort with random and descending orders # 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-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` ## 使用[Valgrind](https://valgrind.org/) 執行以下命令 ```shell make valgrind ``` 會得到以下訊息 ```c # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '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 linenoise.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 .linenoise.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 linenoise.o LD qtest make[1]: Leaving directory 'lab0-c' cp qtest /tmp/qtest.BK0T2K chmod u+x /tmp/qtest.BK0T2K sed -i "s/alarm/isnan/g" /tmp/qtest.BK0T2K scripts/driver.py -p /tmp/qtest.BK0T2K --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head ==21222== 5 bytes in 1 blocks are still reachable in loss record 1 of 3 ==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==21222== by 0x4A4C50E: strdup (strdup.c:42) ==21222== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236) ==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==21222== by 0x10C22C: main (qtest.c:769) ==21222== ==21222== 95 bytes in 19 blocks are still reachable in loss record 2 of 3 ==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==21222== by 0x4A4C50E: strdup (strdup.c:42) ==21222== by 0x11000E: linenoiseHistoryAdd (linenoise.c:1236) ==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==21222== by 0x10C22C: main (qtest.c:769) ==21222== ==21222== 160 bytes in 1 blocks are still reachable in loss record 3 of 3 ==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==21222== by 0x11005A: linenoiseHistoryAdd (linenoise.c:1224) ==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==21222== by 0x10C22C: main (qtest.c:769) ==21222== --- trace-01-ops 6/6 ... ``` 以下還有更多訊息不過大多數合 trace-01 一樣的問題可以關注這幾段 ```c ==21222== by 0x4A4C50E: strdup (strdup.c:42) ==21222== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236) ==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==21222== by 0x10C22C: main (qtest.c:769) ``` 追蹤出現問題的地方 `linenoiseHistory` ```c int linenoiseHistoryAdd(const char *line) { char *linecopy; if (history_max_len == 0) return 0; /* Initialization on first call. */ if (history == NULL) { history = malloc(sizeof(char *) * history_max_len); if (history == NULL) return 0; memset(history, 0, (sizeof(char *) * history_max_len)); } /* Don't add duplicated lines. */ if (history_len && !strcmp(history[history_len - 1], line)) return 0; /* Add an heap allocated copy of the line in the history. * If we reached the max length, remove the older line. */ linecopy = strdup(line); //<-here 1236 if (!linecopy) return 0; if (history_len == history_max_len) { free(history[0]); memmove(history, history + 1, sizeof(char *) * (history_max_len - 1)); history_len--; } history[history_len] = linecopy; history_len++; return 1; } ``` `linenoiseHistoryLoad` ```c int linenoiseHistoryLoad(const char *filename) { FILE *fp = fopen(filename, "r"); char buf[LINENOISE_MAX_LINE]; if (fp == NULL) return -1; while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) { char *p; p = strchr(buf, '\r'); if (!p) p = strchr(buf, '\n'); if (p) *p = '\0'; linenoiseHistoryAdd(buf); //<-here 1325 } fclose(fp); return 0; } ``` `main` ```c /* Trigger call back function(auto completion) */ linenoiseSetCompletionCallback(completion); linenoiseHistorySetMaxLen(HISTORY_LEN); linenoiseHistoryLoad(HISTORY_FILE);// <-here 769 ``` 而 `strdup` 在 `string.h` still reachable 代表的是有東西還沒 free 主要原因是輸入方式手動輸入命令和自命令歷史記錄檔案 `history` 讀取的輸入會不一樣輸入命令會把命令寫進 `history` 在 `run_console` 中可以發現這一點 ```c bool run_console(char *infile_name) { if (!push_file(infile_name)) { report(1, "ERROR: Could not open source file '%s'", infile_name); return false; } if (!has_infile) { char *cmdline; while ((cmdline = linenoise(prompt)) != NULL) { interpret_cmd(cmdline); linenoiseHistoryAdd(cmdline); /* Add to the history. */ linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */ linenoiseFree(cmdline); } } else { while (!cmd_done()) cmd_select(0, NULL, NULL, NULL, NULL); } return err_cnt == 0; } ``` 其中的 `has_infile` 條件判斷裡可以發現這一點 `linenoiseFree` 也是在沒有檔案的情況下作因此推測此 memory error 與是否有讀檔有關作以下實驗自行輸入 `trace-eg.cmd` 中的命令和讀檔讀檔 ```shell $ valgrind --leak-check=yes ./qtest -v 3 -f traces/trace-eg.cmd cmd> cmd> # Demonstration of queue testing framework cmd> # Use help command to see list of commands and options cmd> # Initial queue is NULL. cmd> show q = NULL cmd> # Create empty queue cmd> new q = [] cmd> # Fill it with some values. First at the head cmd> ih dolphin q = [dolphin] cmd> ih bear q = [bear dolphin] cmd> ih gerbil q = [gerbil bear dolphin] cmd> # Now at the tail cmd> it meerkat q = [gerbil bear dolphin meerkat] cmd> it bear q = [gerbil bear dolphin meerkat bear] cmd> # Reverse it cmd> reverse q = [bear meerkat dolphin bear gerbil] cmd> # See how long it is cmd> size Queue size = 5 q = [bear meerkat dolphin bear gerbil] cmd> # Delete queue. Goes back to a NULL queue. cmd> free q = NULL cmd> # Exit program cmd> quit Freeing queue ==29205== 5 bytes in 1 blocks are still reachable in loss record 1 of 3 ==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==29205== by 0x4A4C50E: strdup (strdup.c:42) ==29205== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236) ==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==29205== by 0x10C22C: main (qtest.c:770) ==29205== ==29205== 91 bytes in 19 blocks are still reachable in loss record 2 of 3 ==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==29205== by 0x4A4C50E: strdup (strdup.c:42) ==29205== by 0x11000E: linenoiseHistoryAdd (linenoise.c:1236) ==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==29205== by 0x10C22C: main (qtest.c:770) ==29205== ==29205== 160 bytes in 1 blocks are still reachable in loss record 3 of 3 ==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==29205== by 0x11005A: linenoiseHistoryAdd (linenoise.c:1224) ==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325) ==29205== by 0x10C22C: main (qtest.c:770) ==29205== ``` 自行輸入 ```shell $ valgrind --leak-check=yes ./qtest cmd> cmd> show q = NULL cmd> new q = [] cmd> ih dolphin q = [dolphin] cmd> ih bear q = [bear dolphin] cmd> ih gerbil q = [gerbil bear dolphin] cmd> it meerkat q = [gerbil bear dolphin meerkat] cmd> it bear q = [gerbil bear dolphin meerkat bear] cmd> reverse q = [bear meerkat dolphin bear gerbil] cmd> size Queue size = 5 q = [bear meerkat dolphin bear gerbil] cmd> free q = NULL cmd> quit Freeing queue ``` 因此在 `main` 中發生錯誤的地方加上條件判斷 ```c /* Trigger call back function(auto completion) */ if (!infile_name) { linenoiseSetCompletionCallback(completion); linenoiseHistorySetMaxLen(HISTORY_LEN); linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */ } ``` 重新 make ```c $ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/amagi/linux2021/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 linenoise.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 .linenoise.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 linenoise.o LD qtest make[1]: Leaving directory '/home/amagi/linux2021/lab0-c' cp qtest /tmp/qtest.4RAvVj chmod u+x /tmp/qtest.4RAvVj sed -i "s/alarm/isnan/g" /tmp/qtest.4RAvVj scripts/driver.py -p /tmp/qtest.4RAvVj --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings --- trace-06-string 6/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of sort with random and descending orders # 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-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity 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.4RAvVj --valgrind -t <tid> ```

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.