2021q1 Homework1 (lab0)

# 2021q1 Homework1 (lab0) contributed by < `yellow-hank` > ###### tags: `LinuxKernel` :::danger 注意書寫規範：中英文間用一個半形空白字元區隔 :notes: jserv ::: ## Queue 實作 ### Structure ### queue ```cpp typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; /* End of list */ size_t size; /* list size */ } queue_t; ``` #### linked list ```cpp typedef struct ELE { /* Pointer to array holding string. * This array needs to be explicitly allocated and freed */ char *value; struct ELE *next; } list_ele_t; ``` ### functions #### q_new :::spoiler code ```cpp /* * Create empty queue. * Return NULL if could not allocate space. */ queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); // check malloc whether allocating space sucess or not if (!q) { return q; } q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ::: - 產生一個新的 queue 的資料結構，若是配置記憶體失敗，則回傳 NULL ，餅切初始化 queue 的變數 #### q_free :::spoiler code ```cpp /* Free all storage used by queue */ void q_free(queue_t *q) { if (!q) { return; } /* go through each list node to release value's space. * After release value's space, release list node */ for (; q->head != NULL;) { free(q->head->value); list_ele_t *delete_node = q->head; q->head = q->head->next; free(delete_node); } free(q); } ``` ::: **釋放一個 queue ，裡面有兩個節點的示意圖** ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> delete_node"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct3; struct3:f1 -> struct4; } ``` 更改第一個 next 指向方式，並且讓 head 指向下一個節點 ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> delete_node"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; } ``` 釋放 delete_node 指向的空間，並且讓 delete_node 指向下一個節點 ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> delete_node"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct3; } ``` #### q_insert_head :::spoiler code ```cpp /* * Attempt to insert element at head of queue. * Return true if successful. * Return false if q is NULL or could not allocate space. * Argument s points to the string to be stored. * The function must explicitly allocate space and copy the string into it. */ bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; char *s_new; // check malloc whether allocating space sucess or not if (!q) { return false; } newh = malloc(sizeof(list_ele_t)); if (!newh) { return false; } // allocate space for string s_new = malloc(sizeof(char) * (strlen(s) + 1)); if (!s_new) { free(newh); return false; } // deal with the first time inserting node if (!q->head) { q->tail = newh; } newh->next = q->head; q->head = newh; newh->value = s_new; /*using memcpy because strcpy may cause source string won't * have a teminating character and it may crash program. */ memcpy(s_new, s, strlen(s) + 1); q->size++; return true; } ``` ::: - 這裡使用 memcpy ，是因為 strcpy 會導致 '\0' 有機會不會被放入，可能會使程式存取到非法的空間，使程式終止。 - 在進行除錯時，發現如果在第二次配置記體失敗時，要記得將先前配置的空間釋放掉，第一次撰寫未注意到導致測試未通過。 **示意圖** ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> newh"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> newh"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct3:f1 -> struct4:f0; struct2:f1 -> struct4; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> newh"]; struct2 [label="<f0> head"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct3:f1 -> struct4:f0; struct2:f1 -> struct3; } ``` #### q_insert_tail :::spoiler code ```cpp /* * Attempt to insert element at tail of queue. * Return true if successful. * Return false if q is NULL or could not allocate space. * Argument s points to the string to be stored. * The function must explicitly allocate space and copy the string into it. */ bool q_insert_tail(queue_t *q, char *s) { list_ele_t *newh; char *s_new; if (!q) { return false; } newh = malloc(sizeof(list_ele_t)); if (!newh) { return false; } s_new = malloc(sizeof(char) * (strlen(s) + 1)); if (!s_new) { free(newh); return false; } newh->next = NULL; if (q->tail) { q->tail->next = newh; } else { q->head = newh; } q->tail = newh; newh->value = s_new; /*using memcpy because strcpy may cause source string won't * have a teminating character and it may crash program. */ memcpy(s_new, s, strlen(s) + 1); q->size++; return true; } ``` ::: - 這裡使用 memcpy ，是因為 strcpy 會導致 '\0' 有機會不會被放入，可能會使程式存取到非法的空間，使程式終止。 - 為了實現時間複雜度為 O(1) ，在 queue 的結構中加入一個變數紀錄 list 的末端，如此一來，可以在常數時間內加入資料在末端。 **示意圖** ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> tail"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; struct3:f1 -> struct4:f0; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> tail"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="<f0> newh"]; struct6 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; struct3:f1 -> struct4:f0; struct5:f1 -> struct6; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> tail"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="<f0> newh"]; struct6 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; struct3:f1 -> struct4:f0; struct5:f1 -> struct6; struct4:f1 -> struct6:f0; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> tail"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="<f0> newh"]; struct6 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct6; struct3:f1 -> struct4:f0; struct5:f1 -> struct6; struct4:f1 -> struct6:f0; } ``` #### q_remove_head :::spoiler code ```cpp /* * Attempt to remove element from head of queue. * Return true if successful. * Return false if queue is NULL or empty. * 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.) * The space used by the list element and the string should be freed. */ bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { list_ele_t *delete_ptr; if (!q) { return false; } if (!q->head) { return false; } if (sp) { memcpy(sp, q->head->value, bufsize); sp[bufsize - 1] = '\0'; } free(q->head->value); delete_ptr = q->head; q->head = q->head->next; free(delete_ptr); q->size--; return true; } ``` ::: - 這裡需要注意的是節點中的 value 需要被釋放，因為先前是透過 malloc 配置，若不進行釋放記憶體使用量會隨時間增加，可能會導致記憶體不足的情況 - 先釋放 value 空間，而後釋放整個節點。 **示意圖** ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> delete_ptr"]; struct3 [label="<f0> tail"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct4; struct2:f1 -> struct4; struct3:f1 -> struct5:f0; struct4:f1 -> struct5:f0; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct2 [label="<f0> delete_ptr"]; struct3 [label="<f0> tail"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct5; struct2:f1 -> struct4; struct3:f1 -> struct5:f0; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> head"]; struct3 [label="<f0> tail"]; struct5 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct5; struct3:f1 -> struct5:f0; } ``` #### q_size :::spoiler code ```cpp /* * Return number of elements in queue. * Return 0 if q is NULL or empty */ int q_size(queue_t *q) { /* using a variable in queue_t to store size.After insert or remove * operation increase or decrease size.With this implement, to reach time * complexity O(1) */ if (!q) { return 0; } return q->size; } ``` ::: - 為了實現時間複雜度為 O(1) ，在 queue 的結構中加入一個變數紀錄節點的個數，而個數的增加或減少則是在新增函示或是移除函示中進行變動。 - 注意的是 queue 為空時，個數為零。 #### q_reverse :::spoiler code ```cpp /* * Reverse elements in queue * No effect if q is NULL or empty * This function should not allocate or free any list elements * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head). * It should rearrange the existing ones. */ void q_reverse(queue_t *q) { list_ele_t *prev = NULL, *current, *next, *swap; if (!q) { return; } for (current = q->head; current != NULL;) { next = current->next; current->next = prev; prev = current; current = next; } swap = q->head; q->head = q->tail; q->tail = swap; } ``` ::: **示意圖** 用三個指標個別指向三個個別節點 ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> prev"]; struct2 [label="<f0> current"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="<f0> next"]; struct6 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; struct3:f1 -> struct4:f0; struct5:f1 -> struct6; struct4:f1 -> struct6:f0; } ``` 把個別指向的節點中的 next 指向反向， current 指向 prev ， next 指向 current ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> prev"]; struct2 [label="<f0> current"]; struct3 [label="{<f0> value|<f1> next\n}"]; struct4 [label="{<f0> value|<f1> next\n}"]; struct5 [label="<f0> next"]; struct6 [label="{<f0> value|<f1> next\n}"]; struct1:f1 -> struct3; struct2:f1 -> struct4; struct4:f1 -> struct3:f0; struct5:f1 -> struct6; struct6:f1 -> struct4:f0; } ``` #### q_sort :::spoiler code ```cpp /* insert node at list tail and change head and tail pointer*/ void list_insert_tail(list_ele_t **head, list_ele_t **tail, list_ele_t *node) { if (*tail == NULL) { *tail = node; *head = node; } else { (*tail)->next = node; (*tail) = node; } } list_ele_t *merge(list_ele_t *first, list_ele_t *second) { list_ele_t *result_head = NULL, *result_tail = NULL; while (first && second) { // compare and put the smaller one in result if (strcmp(first->value, second->value) <= 0) { list_insert_tail(&result_head, &result_tail, first); first = first->next; } else { list_insert_tail(&result_head, &result_tail, second); second = second->next; } } // Find the list that still have data, and add it in result if (first) { list_insert_tail(&result_head, &result_tail, first); } if (second) { list_insert_tail(&result_head, &result_tail, second); } return result_head; } list_ele_t *mergesort(list_ele_t *list) { if (!list->next) { return list; } list_ele_t *slow = list, *fast = list->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } list_ele_t *tmp = slow->next; slow->next = NULL; return merge(mergesort(list), mergesort(tmp)); } /* * Sort elements of queue in ascending order * No effect if q is NULL or empty. In addition, if q has only one * element, do nothing. */ void q_sort(queue_t *q) { if (!q || !q->head || !q->head->next) { return; } list_ele_t *i; q->head = mergesort(q->head); // update tail's information for (i = q->head; i->next != NULL; i = i->next) ; q->tail = i; } ``` ::: - 第一次實作時使用 Quick Sort ，尚未注意到測試中有考慮到時間複雜度需要達到 O(nlgn) ， Quick Sort 最差的時間複雜度會是 O(n^2^) 。為了達成目標，我去尋找較為接近的演算法，後來選擇 Merge Sort ，平均時間複雜度為 O(nlgn) ，在實作中遇到的問題是很容易發生 segmentation fault ，需要了解出錯的地點，很容易在這邊打轉。 - 第一次將 Merge Sort 實作出來，但是因為在加入節點的設計使用到重頭開始移動到尾巴再將其加入，這樣耗費許多時間，雖然結果是正確的。後來，我新增一個變數紀錄尾巴，如同上述 q_insert_tail 的做法，減少許多時間。 ## 修正 qtest 使用 Adress Sanitizer 分析 qtest 執行 help 指令發生的錯誤 ``` ==234967==ERROR: AddressSanitizer: global-buffer-overflow on address 0x557eaae33400 at pc 0x557eaae1c90f bp 0x7ffcc876bad0 sp 0x7ffcc876bac0 READ of size 4 at 0x557eaae33400 thread T0 #0 0x557eaae1c90e in do_help_cmd /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:307 #1 0x557eaae1ca22 in interpret_cmda /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:221 #2 0x557eaae1d207 in interpret_cmd /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:244 #3 0x557eaae1e951 in run_console /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:660 #4 0x557eaae1b531 in main /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/qtest.c:788 #5 0x7f19f18b10b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #6 0x557eaae18b8d in _start (/home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/qtest+0x8b8d) 0x557eaae33401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x557eaae33400) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:307 in do_help_cmd Shadow bytes around the buggy address: 0x0ab0555be630: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0ab0555be640: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0ab0555be650: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 0x0ab0555be660: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 0x0ab0555be670: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 =>0x0ab0555be680:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 0x0ab0555be690: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 0x0ab0555be6a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab0555be6b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab0555be6c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab0555be6d0: 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 ==234967==ABORTING ``` 這裡發現在存取 echo 變數時，會發生 global-buffer-overflow 。查詢 C99 規格書發現 bool 的空間是足夠放 0 和 1 。 - C99 [6.2.5] **Types** > An object declared as type _Bool is large enough to store the values 0 and 1. 下列程式碼使用 plist->valp 整數指標去指向 echo 空間，會導致指標直接存取 4bytes 的空間，但是實際上 echo 的空間不足 4bytes ，會導致 global-buffer-overflow ```cpp report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation); ``` 也實測 bool 和 int 的空間大小，得到 bool 1bytes, int 4 bytes ```cpp printf("%ld %ld\n",sizeof(bool), sizeof(int)) // 1 4 ``` ### 嘗試解決方式 - 可以將 echo 變數的宣告型態提升至 int ，但是接下來 simulation 會遇到相同的問題， simulation 是外部的變數，不一定能夠更動型態。 - 把 plist->valp 轉型成 bool* ，但是需注意到原本是 int* ，這是非常危險的方式，有機會導致資訊量減少，得到錯誤的結果，這個方式需要評估原本的 int 有沒有超過 1bytes 的空間，在這裡因為 option length 使用數字 1024 ，所以不適用。 ### 解決方式 - 在結構 PELE 中加入一個變數紀錄是布林值還是整數值 ```cpp struct PELE { char *name; int *valp; char *documentation; /* Function that gets called whenever parameter changes */ setter_function setter; param_ptr next; bool checkboolint; }; ``` - 在加入參數時，設定此值是布林值還是整數值 ```cpp void add_param(char *name, int *valp, char *doccumentation, setter_function setter); setter_function setter, bool setbool); ``` - 在 report 的地方分為布林值解決方式或是整數值解決方式 ```cpp if (plist->checkboolint) report(1, "\t%s\t%d\t%s", plist->name, *(bool *) plist->valp, plist->documentation); else report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation); ``` ## 使用 valgrind 排除 queue 實作時記憶體錯誤使用 make valgrind 針對記憶體進行除錯 - 錯誤結果 (擷取第一個測試錯誤) ``` +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head ==288083== Invalid read of size 8 ==288083== at 0x4842C30: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8ff8 is 8 bytes before a block of size 2,049 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10B3B4: do_remove_head (qtest.c:334) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842C3B: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8ff0 is 16 bytes before a block of size 2,049 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10B3B4: do_remove_head (qtest.c:334) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842C1C: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8fe8 is 24 bytes before a block of size 2,049 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10B3B4: do_remove_head (qtest.c:334) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842C28: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8fe0 is 32 bytes before a block of size 2,064 in arena "client" ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842A8F: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8c50 is 3 bytes after a block of size 45 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10DEDF: test_malloc (harness.c:138) ==288083== by 0x10E399: q_insert_head (queue.c:64) ==288083== by 0x10BC57: do_insert_head (qtest.c:216) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842A97: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8c58 is 11 bytes after a block of size 45 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10DEDF: test_malloc (harness.c:138) ==288083== by 0x10E399: q_insert_head (queue.c:64) ==288083== by 0x10BC57: do_insert_head (qtest.c:216) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842A7C: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8c60 is 19 bytes after a block of size 45 alloc'd ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10DEDF: test_malloc (harness.c:138) ==288083== by 0x10E399: q_insert_head (queue.c:64) ==288083== by 0x10BC57: do_insert_head (qtest.c:216) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== ==288083== Invalid read of size 8 ==288083== at 0x4842A87: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba8c68 is 24 bytes after a block of size 48 in arena "client" ==288083== ==288083== Invalid read of size 1 ==288083== at 0x4842B60: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10E4DF: memcpy (string_fortified.h:34) ==288083== by 0x10E4DF: q_remove_head (queue.c:144) ==288083== by 0x10B57A: do_remove_head (qtest.c:368) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Address 0x4ba9040 is 64 bytes inside a block of size 2,049 free'd ==288083== at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10B68D: do_remove_head (qtest.c:413) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== Block was alloc'd at ==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==288083== by 0x10B3B4: do_remove_head (qtest.c:334) ==288083== by 0x10CEA1: interpret_cmda (console.c:224) ==288083== by 0x10D338: interpret_cmd (console.c:247) ==288083== by 0x10DBA0: cmd_select (console.c:601) ==288083== by 0x10DE6D: run_console (console.c:674) ==288083== by 0x10C2D1: main (qtest.c:789) ==288083== --- trace-01-ops 0/6 ``` - 問題分析 - 發現在 q_remove_head 中的 memmove 有發生 invalid read 的情況 ### 嘗試解決方式 - 閱讀資料針對 memcpy 可能發生的問題進行解決，在規格書中發現 memcpy 和 memmove 雖然都是複製字串，但是 memcpy 針對 [overlapping](https://cs50.stackexchange.com/questions/14615/memory-overlap-in-c) 的問題， memcpy 會發生未定義行為。 - C99 [7.21.2.1] **The memcpy function** > The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. - 相對 memmove 可以針對 overlapping 進行處置，是透過複製到一個暫存的陣列來解決 - C99 [7.21.2.2] **The memmove function** > The memmove function copies n characters from the object pointed to by s2 into the object pointed to by s1. Copying takes place as if the n characters from the object pointed to by s2 are first copied into a temporary array of n characters that does not overlap the objects pointed to by s1 and s2, and then the n characters from the temporary array are copied into the object pointed to by s1. - memcpy 的好處是效率快速，前提是沒有 overlapping - 所以將 memcpy 替換成 memmove ### 解決方式 - 發現到 memcpy 中的 size 都是使用 buffersize 並沒有針對 q->head->value 做適度的調整導致 sp 的大小都是 bufsize。 ```cpp memcpy(sp, q->head->value, bufsize); sp[bufsize - 1] = '\0'; ``` - 去檢查原本字串的長度，如果超過 bufsize 則另行處理 ```cpp if (bufsize < string_len + 1) { memmove(sp, q->head->value, bufsize); sp[bufsize - 1] = '\0'; } else { memmove(sp, q->head->value, string_len + 1); sp[string_len] = '\0'; } ``` ### 視覺化 simulation 的記憶體使用量 - 使用 valgrind 中的 massif 進行分析 ```bash valgrind --tool=massif ./qtest -v 3 -f ./traces/trace-17-complexity.cmd #印出結果 ms_print massif.out.258408 ``` - 結果 (直接執行上述實做的 queue) ``` -------------------------------------------------------------------------------- Command: ./qtest -v 3 -f ./traces/trace-17-complexity.cmd Massif arguments: (none) ms_print arguments: massif.out.258408 -------------------------------------------------------------------------------- MB 1.231^ # | # | # | # : : | # : : : | # : : :: : : @ | # : : :: : : @ | # : : :: : : @ : | # :: : : : :: : : @ : : | # : : : :::: : : : @ : : | #: : : : :::: : : : @: : :: | #: : ::: : :::: : : : @: : : :: | #: : ::: : @::::: : : : @::: : : : ::@ | #: : ::: : @ :::: : : : @:: : : : ::@ | #: :: : ::: : : @ :::: : ::: : @:: ::: : : ::@ | #: : : ::: : : @ :::: : :: : @:: :::@: : ::@ | #::: : : :::@: : @ :::: : :: : : : @:: :::@: : ::@ | #:: : : : :::@:::@ : @ ::::::: : :: : : : @:: :::@: ::::@ | #:: : : : :::@:::@ : @ ::::: : : :: ::: ::@:: :::@: ::::@ | #:: : : : :::@:::@:: @ : @ ::::: : ::::: :::@@::@:: :: :::@::::::@ 0 +----------------------------------------------------------------------->Gi 0 26.97 Number of snapshots: 65 Detailed snapshots: [1, 2 (peak), 14, 18, 21, 25, 41, 44, 54, 64] -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 0 0 0 0 0 0 1 451,350,369 304,816 250,300 54,516 0 82.12% (250,300B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->76.75% (233,955B) 0x10DEDF: test_malloc (harness.c:138) | ->41.34% (126,000B) 0x10E375: q_insert_head (queue.c:59) | | ->41.34% (126,000B) 0x10E9FE: measure (constant.c:65) | | ->41.34% (126,000B) 0x10EB7E: doit (fixture.c:136) | | ->41.34% (126,000B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->41.34% (126,000B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->41.34% (126,000B) 0x10CEA1: interpret_cmda (console.c:224) | | ->41.34% (126,000B) 0x10D338: interpret_cmd (console.c:247) | | ->41.34% (126,000B) 0x10DBA0: cmd_select (console.c:601) | | ->41.34% (126,000B) 0x10DE6D: run_console (console.c:674) | | ->41.34% (126,000B) 0x10C2D1: main (qtest.c:789) | | | ->35.36% (107,787B) 0x10E399: q_insert_head (queue.c:64) | | ->35.36% (107,787B) 0x10E9FE: measure (constant.c:65) | | ->35.36% (107,787B) 0x10EB7E: doit (fixture.c:136) | | ->35.36% (107,787B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->35.36% (107,787B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->35.36% (107,787B) 0x10CEA1: interpret_cmda (console.c:224) | | ->35.36% (107,787B) 0x10D338: interpret_cmd (console.c:247) | | ->35.36% (107,787B) 0x10DBA0: cmd_select (console.c:601) | | ->35.36% (107,787B) 0x10DE6D: run_console (console.c:674) | | ->35.36% (107,787B) 0x10C2D1: main (qtest.c:789) | | | ->00.06% (168B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.98% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->02.70% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->02.70% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->02.70% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.29% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.38% (7,249B) in 10 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 2 744,872,031 1,290,600 1,051,284 239,316 0 81.46% (1,051,284B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->80.19% (1,034,939B) 0x10DEDF: test_malloc (harness.c:138) | ->43.18% (557,256B) 0x10E375: q_insert_head (queue.c:59) | | ->43.18% (557,256B) 0x10E9FE: measure (constant.c:65) | | ->43.18% (557,256B) 0x10EB7E: doit (fixture.c:136) | | ->43.18% (557,256B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->43.18% (557,256B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->43.18% (557,256B) 0x10CEA1: interpret_cmda (console.c:224) | | ->43.18% (557,256B) 0x10D338: interpret_cmd (console.c:247) | | ->43.18% (557,256B) 0x10DBA0: cmd_select (console.c:601) | | ->43.18% (557,256B) 0x10DE6D: run_console (console.c:674) | | ->43.18% (557,256B) 0x10C2D1: main (qtest.c:789) | | | ->37.00% (477,515B) 0x10E399: q_insert_head (queue.c:64) | | ->37.00% (477,515B) 0x10E9FE: measure (constant.c:65) | | ->37.00% (477,515B) 0x10EB7E: doit (fixture.c:136) | | ->37.00% (477,515B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->37.00% (477,515B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->37.00% (477,515B) 0x10CEA1: interpret_cmda (console.c:224) | | ->37.00% (477,515B) 0x10D338: interpret_cmd (console.c:247) | | ->37.00% (477,515B) 0x10DBA0: cmd_select (console.c:601) | | ->37.00% (477,515B) 0x10DE6D: run_console (console.c:674) | | ->37.00% (477,515B) 0x10C2D1: main (qtest.c:789) | | | ->00.01% (168B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.27% (16,345B) in 11 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 3 1,196,716,406 705,968 575,645 130,323 0 4 1,525,314,876 273,712 224,842 48,870 0 5 2,195,497,317 49,640 43,108 6,532 0 6 2,590,737,257 28,976 26,331 2,645 0 7 3,086,439,722 445,488 364,123 81,365 0 8 3,814,260,269 201,520 166,510 35,010 0 9 4,121,127,632 34,864 31,125 3,739 0 10 4,581,428,795 787,120 641,617 145,503 0 11 5,246,308,143 629,680 514,129 115,551 0 12 5,757,754,359 600,040 490,065 109,975 0 13 6,249,528,173 1,058,480 861,461 197,019 0 14 6,579,996,777 274,864 226,034 48,830 0 82.23% (226,034B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->76.29% (209,689B) 0x10DEDF: test_malloc (harness.c:138) | ->41.09% (112,952B) 0x10E375: q_insert_head (queue.c:59) | | ->41.09% (112,952B) 0x10E9FE: measure (constant.c:65) | | ->41.09% (112,952B) 0x10EB7E: doit (fixture.c:136) | | ->41.09% (112,952B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->41.09% (112,952B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->41.09% (112,952B) 0x10CEA1: interpret_cmda (console.c:224) | | ->41.09% (112,952B) 0x10D338: interpret_cmd (console.c:247) | | ->41.09% (112,952B) 0x10DBA0: cmd_select (console.c:601) | | ->41.09% (112,952B) 0x10DE6D: run_console (console.c:674) | | ->41.09% (112,952B) 0x10C2D1: main (qtest.c:789) | | | ->35.17% (96,673B) 0x10E399: q_insert_head (queue.c:64) | | ->35.17% (96,673B) 0x10E9FE: measure (constant.c:65) | | ->35.17% (96,673B) 0x10EB7E: doit (fixture.c:136) | | ->35.17% (96,673B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->35.17% (96,673B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->35.17% (96,673B) 0x10CEA1: interpret_cmda (console.c:224) | | ->35.17% (96,673B) 0x10D338: interpret_cmd (console.c:247) | | ->35.17% (96,673B) 0x10DBA0: cmd_select (console.c:601) | | ->35.17% (96,673B) 0x10DE6D: run_console (console.c:674) | | ->35.17% (96,673B) 0x10C2D1: main (qtest.c:789) | | | ->00.02% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->03.31% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->02.99% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->02.99% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->02.99% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.32% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.64% (7,249B) in 10 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 15 7,075,699,585 394,544 322,629 71,915 0 16 7,488,785,369 200,112 164,754 35,358 0 17 7,819,253,909 837,352 682,465 154,887 0 18 8,232,339,793 211,304 174,359 36,945 0 82.52% (174,359B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->74.78% (158,014B) 0x10DEDF: test_malloc (harness.c:138) | ->40.28% (85,120B) 0x10E375: q_insert_head (queue.c:59) | | ->40.28% (85,120B) 0x10E9FE: measure (constant.c:65) | | ->40.28% (85,120B) 0x10EB7E: doit (fixture.c:136) | | ->40.28% (85,120B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->40.28% (85,120B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->40.28% (85,120B) 0x10CEA1: interpret_cmda (console.c:224) | | ->40.28% (85,120B) 0x10D338: interpret_cmd (console.c:247) | | ->40.28% (85,120B) 0x10DBA0: cmd_select (console.c:601) | | ->40.28% (85,120B) 0x10DE6D: run_console (console.c:674) | | ->40.28% (85,120B) 0x10C2D1: main (qtest.c:789) | | | ->34.47% (72,830B) 0x10E399: q_insert_head (queue.c:64) | | ->34.47% (72,830B) 0x10E9FE: measure (constant.c:65) | | ->34.47% (72,830B) 0x10EB7E: doit (fixture.c:136) | | ->34.47% (72,830B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->34.47% (72,830B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->34.47% (72,830B) 0x10CEA1: interpret_cmda (console.c:224) | | ->34.47% (72,830B) 0x10D338: interpret_cmd (console.c:247) | | ->34.47% (72,830B) 0x10DBA0: cmd_select (console.c:601) | | ->34.47% (72,830B) 0x10DE6D: run_console (console.c:674) | | ->34.47% (72,830B) 0x10C2D1: main (qtest.c:789) | | | ->00.03% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->04.30% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->03.89% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->03.89% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->03.89% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.42% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.29% (4,849B) in 9 places, all below massif's threshold (1.00%) | ->01.14% (2,400B) 0x10EB30: doit (fixture.c:127) ->01.14% (2,400B) 0x10EDD6: is_insert_tail_const (fixture.c:168) ->01.14% (2,400B) 0x10B7F2: do_insert_tail (qtest.c:263) ->01.14% (2,400B) 0x10CEA1: interpret_cmda (console.c:224) ->01.14% (2,400B) 0x10D338: interpret_cmd (console.c:247) ->01.14% (2,400B) 0x10DBA0: cmd_select (console.c:601) ->01.14% (2,400B) 0x10DE6D: run_console (console.c:674) ->01.14% (2,400B) 0x10C2D1: main (qtest.c:789) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 19 8,810,659,780 65,512 56,001 9,511 0 20 9,471,596,719 48,688 42,333 6,355 0 21 9,884,682,472 91,880 77,400 14,480 0 84.24% (77,400B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->66.45% (61,055B) 0x10DEDF: test_malloc (harness.c:138) | ->35.72% (32,816B) 0x10E375: q_insert_head (queue.c:59) | | ->35.72% (32,816B) 0x10E9FE: measure (constant.c:65) | | ->35.72% (32,816B) 0x10EB7E: doit (fixture.c:136) | | ->35.72% (32,816B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->35.72% (32,816B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->35.72% (32,816B) 0x10CEA1: interpret_cmda (console.c:224) | | ->35.72% (32,816B) 0x10D338: interpret_cmd (console.c:247) | | ->35.72% (32,816B) 0x10DBA0: cmd_select (console.c:601) | | ->35.72% (32,816B) 0x10DE6D: run_console (console.c:674) | | ->35.72% (32,816B) 0x10C2D1: main (qtest.c:789) | | | ->30.55% (28,071B) 0x10E399: q_insert_head (queue.c:64) | | ->30.55% (28,071B) 0x10E9FE: measure (constant.c:65) | | ->30.55% (28,071B) 0x10EB7E: doit (fixture.c:136) | | ->30.55% (28,071B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->30.55% (28,071B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->30.55% (28,071B) 0x10CEA1: interpret_cmda (console.c:224) | | ->30.55% (28,071B) 0x10D338: interpret_cmd (console.c:247) | | ->30.55% (28,071B) 0x10DBA0: cmd_select (console.c:601) | | ->30.55% (28,071B) 0x10DE6D: run_console (console.c:674) | | ->30.55% (28,071B) 0x10C2D1: main (qtest.c:789) | | | ->00.18% (168B) in 1+ places, all below ms_print's threshold (01.00%) | ->09.90% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->08.94% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->08.94% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->08.94% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.96% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.61% (2,400B) 0x10EB30: doit (fixture.c:127) | ->02.61% (2,400B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | ->02.61% (2,400B) 0x10B7F2: do_insert_tail (qtest.c:263) | ->02.61% (2,400B) 0x10CEA1: interpret_cmda (console.c:224) | ->02.61% (2,400B) 0x10D338: interpret_cmd (console.c:247) | ->02.61% (2,400B) 0x10DBA0: cmd_select (console.c:601) | ->02.61% (2,400B) 0x10DE6D: run_console (console.c:674) | ->02.61% (2,400B) 0x10C2D1: main (qtest.c:789) | ->01.31% (1,208B) 0x10EAE8: doit (fixture.c:122) | ->01.31% (1,208B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | ->01.31% (1,208B) 0x10B7F2: do_insert_tail (qtest.c:263) | ->01.31% (1,208B) 0x10CEA1: interpret_cmda (console.c:224) | ->01.31% (1,208B) 0x10D338: interpret_cmd (console.c:247) | ->01.31% (1,208B) 0x10DBA0: cmd_select (console.c:601) | ->01.31% (1,208B) 0x10DE6D: run_console (console.c:674) | ->01.31% (1,208B) 0x10C2D1: main (qtest.c:789) | ->01.31% (1,208B) 0x10EAF8: doit (fixture.c:123) | ->01.31% (1,208B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | ->01.31% (1,208B) 0x10B7F2: do_insert_tail (qtest.c:263) | ->01.31% (1,208B) 0x10CEA1: interpret_cmda (console.c:224) | ->01.31% (1,208B) 0x10D338: interpret_cmd (console.c:247) | ->01.31% (1,208B) 0x10DBA0: cmd_select (console.c:601) | ->01.31% (1,208B) 0x10DE6D: run_console (console.c:674) | ->01.31% (1,208B) 0x10C2D1: main (qtest.c:789) | ->01.31% (1,200B) 0x10EB08: doit (fixture.c:124) | ->01.31% (1,200B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | ->01.31% (1,200B) 0x10B7F2: do_insert_tail (qtest.c:263) | ->01.31% (1,200B) 0x10CEA1: interpret_cmda (console.c:224) | ->01.31% (1,200B) 0x10D338: interpret_cmd (console.c:247) | ->01.31% (1,200B) 0x10DBA0: cmd_select (console.c:601) | ->01.31% (1,200B) 0x10DE6D: run_console (console.c:674) | ->01.31% (1,200B) 0x10C2D1: main (qtest.c:789) | ->01.11% (1,024B) 0x4A2AE83: _IO_file_doallocate (filedoalloc.c:101) | ->01.11% (1,024B) 0x4A3B04F: _IO_doallocbuf (genops.c:347) | ->01.11% (1,024B) 0x4A3A0AF: _IO_file_overflow@@GLIBC_2.2.5 (fileops.c:745) | | ->01.11% (1,024B) 0x4A38834: _IO_new_file_xsputn (fileops.c:1244) | | ->01.11% (1,024B) 0x4A38834: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1197) | | ->01.11% (1,024B) 0x4A1FAF1: __vfprintf_internal (vfprintf-internal.c:1373) | | ->01.11% (1,024B) 0x10C8C9: vfprintf (stdio2.h:130) | | ->01.11% (1,024B) 0x10C8C9: report_noreturn (report.c:122) | | ->01.11% (1,024B) 0x10DB5E: readline (console.c:534) | | ->01.11% (1,024B) 0x10DB5E: cmd_select (console.c:599) | | ->01.11% (1,024B) 0x10DE6D: run_console (console.c:674) | | ->01.11% (1,024B) 0x10C2D1: main (qtest.c:789) | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | ->00.23% (209B) in 1+ places, all below ms_print's threshold (01.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 22 10,417,751,127 23,984 22,279 1,705 0 23 11,017,665,208 222,640 183,631 39,009 0 24 11,497,596,509 47,792 41,589 6,203 0 25 12,097,510,777 518,248 423,278 94,970 0 81.67% (423,278B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->78.52% (406,933B) 0x10DEDF: test_malloc (harness.c:138) | ->42.34% (219,408B) 0x10E375: q_insert_head (queue.c:59) | | ->42.34% (219,408B) 0x10E9FE: measure (constant.c:65) | | ->42.34% (219,408B) 0x10EB7E: doit (fixture.c:136) | | ->42.34% (219,408B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->42.34% (219,408B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->42.34% (219,408B) 0x10CEA1: interpret_cmda (console.c:224) | | ->42.34% (219,408B) 0x10D338: interpret_cmd (console.c:247) | | ->42.34% (219,408B) 0x10DBA0: cmd_select (console.c:601) | | ->42.34% (219,408B) 0x10DE6D: run_console (console.c:674) | | ->42.34% (219,408B) 0x10C2D1: main (qtest.c:789) | | | ->36.17% (187,461B) 0x10E399: q_insert_head (queue.c:64) | | ->36.17% (187,461B) 0x10E9FE: measure (constant.c:65) | | ->36.17% (187,461B) 0x10EB7E: doit (fixture.c:136) | | ->36.17% (187,461B) 0x10EDD6: is_insert_tail_const (fixture.c:168) | | ->36.17% (187,461B) 0x10B7F2: do_insert_tail (qtest.c:263) | | ->36.17% (187,461B) 0x10CEA1: interpret_cmda (console.c:224) | | ->36.17% (187,461B) 0x10D338: interpret_cmd (console.c:247) | | ->36.17% (187,461B) 0x10DBA0: cmd_select (console.c:601) | | ->36.17% (187,461B) 0x10DE6D: run_console (console.c:674) | | ->36.17% (187,461B) 0x10C2D1: main (qtest.c:789) | | | ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.76% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->01.59% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->01.59% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->01.59% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.17% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.40% (7,249B) in 10 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 26 12,457,459,255 580,072 473,733 106,339 0 27 13,057,373,388 970,088 790,451 179,637 0 28 13,417,321,965 764,976 623,253 141,723 0 29 14,017,235,984 1,125,296 916,184 209,112 0 30 14,377,184,366 993,072 809,010 184,062 0 31 14,857,115,714 215,272 177,607 37,665 0 32 15,577,012,612 1,144,552 931,820 212,732 0 33 16,056,943,800 23,656 22,024 1,632 0 34 16,627,378,405 257,840 212,026 45,814 0 35 17,288,316,182 93,104 78,407 14,697 0 36 17,949,253,519 1,027,888 837,327 190,561 0 37 18,279,722,221 388,656 318,568 70,088 0 38 18,940,659,559 261,864 215,480 46,384 0 39 19,601,597,277 134,576 112,087 22,489 0 40 20,097,300,581 725,864 592,461 133,403 0 41 20,427,769,452 125,104 104,329 20,775 0 83.39% (104,329B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->70.33% (87,982B) 0x10DEDF: test_malloc (harness.c:138) | ->37.91% (47,432B) 0x10E375: q_insert_head (queue.c:59) | | ->37.91% (47,432B) 0x10EAA3: measure (constant.c:76) | | | ->37.91% (47,432B) 0x10EB7E: doit (fixture.c:136) | | | ->37.91% (47,432B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->37.91% (47,432B) 0x10AE1A: do_size (qtest.c:482) | | | ->37.91% (47,432B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->37.91% (47,432B) 0x10D338: interpret_cmd (console.c:247) | | | ->37.91% (47,432B) 0x10DBA0: cmd_select (console.c:601) | | | ->37.91% (47,432B) 0x10DE6D: run_console (console.c:674) | | | ->37.91% (47,432B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->32.36% (40,486B) 0x10E399: q_insert_head (queue.c:64) | | ->32.36% (40,486B) 0x10EAA3: measure (constant.c:76) | | | ->32.36% (40,486B) 0x10EB7E: doit (fixture.c:136) | | | ->32.36% (40,486B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->32.36% (40,486B) 0x10AE1A: do_size (qtest.c:482) | | | ->32.36% (40,486B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->32.36% (40,486B) 0x10D338: interpret_cmd (console.c:247) | | | ->32.36% (40,486B) 0x10DBA0: cmd_select (console.c:601) | | | ->32.36% (40,486B) 0x10DE6D: run_console (console.c:674) | | | ->32.36% (40,486B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->00.05% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->07.27% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->06.57% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->06.57% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->06.57% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.70% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->03.88% (4,851B) in 10 places, all below massif's threshold (1.00%) | ->01.92% (2,400B) 0x10EB30: doit (fixture.c:127) ->01.92% (2,400B) 0x10EEB7: is_size_const (fixture.c:188) | ->01.92% (2,400B) 0x10AE1A: do_size (qtest.c:482) | ->01.92% (2,400B) 0x10CEA1: interpret_cmda (console.c:224) | ->01.92% (2,400B) 0x10D338: interpret_cmd (console.c:247) | ->01.92% (2,400B) 0x10DBA0: cmd_select (console.c:601) | ->01.92% (2,400B) 0x10DE6D: run_console (console.c:674) | ->01.92% (2,400B) 0x10C2D1: main (qtest.c:789) | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 42 21,088,706,911 311,472 255,648 55,824 0 43 21,584,410,151 179,760 148,603 31,157 0 44 22,080,113,397 979,816 797,457 182,359 0 81.39% (797,457B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->79.72% (781,110B) 0x10DEDF: test_malloc (harness.c:138) | ->43.00% (421,344B) 0x10E375: q_insert_head (queue.c:59) | | ->43.00% (421,344B) 0x10EAA3: measure (constant.c:76) | | | ->43.00% (421,344B) 0x10EB7E: doit (fixture.c:136) | | | ->43.00% (421,344B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->43.00% (421,344B) 0x10AE1A: do_size (qtest.c:482) | | | ->43.00% (421,344B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->43.00% (421,344B) 0x10D338: interpret_cmd (console.c:247) | | | ->43.00% (421,344B) 0x10DBA0: cmd_select (console.c:601) | | | ->43.00% (421,344B) 0x10DE6D: run_console (console.c:674) | | | ->43.00% (421,344B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->36.71% (359,702B) 0x10E399: q_insert_head (queue.c:64) | | ->36.71% (359,702B) 0x10EAA3: measure (constant.c:76) | | | ->36.71% (359,702B) 0x10EB7E: doit (fixture.c:136) | | | ->36.71% (359,702B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->36.71% (359,702B) 0x10AE1A: do_size (qtest.c:482) | | | ->36.71% (359,702B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->36.71% (359,702B) 0x10D338: interpret_cmd (console.c:247) | | | ->36.71% (359,702B) 0x10DBA0: cmd_select (console.c:601) | | | ->36.71% (359,702B) 0x10DE6D: run_console (console.c:674) | | | ->36.71% (359,702B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.67% (16,347B) in 12 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 45 22,410,582,233 691,504 564,228 127,276 0 46 22,906,285,509 575,408 470,207 105,201 0 47 23,567,223,065 102,120 85,737 16,383 0 48 24,228,160,705 47,848 41,635 6,213 0 49 24,558,629,618 413,360 338,365 74,995 0 50 24,852,151,295 309,352 253,855 55,497 0 51 25,145,673,018 803,944 655,724 148,220 0 52 25,439,194,714 441,576 361,213 80,363 0 53 25,732,716,420 338,920 277,857 61,063 0 54 26,026,238,269 375,984 308,165 67,819 0 81.96% (308,165B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->77.61% (291,818B) 0x10DEDF: test_malloc (harness.c:138) | ->41.81% (157,192B) 0x10E375: q_insert_head (queue.c:59) | | ->41.81% (157,192B) 0x10EAA3: measure (constant.c:76) | | | ->41.81% (157,192B) 0x10EB7E: doit (fixture.c:136) | | | ->41.81% (157,192B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->41.81% (157,192B) 0x10AE1A: do_size (qtest.c:482) | | | ->41.81% (157,192B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->41.81% (157,192B) 0x10D338: interpret_cmd (console.c:247) | | | ->41.81% (157,192B) 0x10DBA0: cmd_select (console.c:601) | | | ->41.81% (157,192B) 0x10DE6D: run_console (console.c:674) | | | ->41.81% (157,192B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->35.79% (134,562B) 0x10E399: q_insert_head (queue.c:64) | | ->35.79% (134,562B) 0x10EAA3: measure (constant.c:76) | | | ->35.79% (134,562B) 0x10EB7E: doit (fixture.c:136) | | | ->35.79% (134,562B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->35.79% (134,562B) 0x10AE1A: do_size (qtest.c:482) | | | ->35.79% (134,562B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->35.79% (134,562B) 0x10D338: interpret_cmd (console.c:247) | | | ->35.79% (134,562B) 0x10DBA0: cmd_select (console.c:601) | | | ->35.79% (134,562B) 0x10DE6D: run_console (console.c:674) | | | ->35.79% (134,562B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->00.02% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->02.42% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->02.19% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->02.19% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->02.19% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.23% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.93% (7,251B) in 11 places, all below massif's threshold (1.00%) -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 55 26,319,760,052 627,304 512,013 115,291 0 56 26,613,281,750 87,728 74,028 13,700 0 57 26,906,803,465 106,856 89,523 17,333 0 58 27,200,325,223 553,392 452,071 101,321 0 59 27,493,846,934 201,704 166,547 35,157 0 60 27,787,368,701 697,960 569,144 128,816 0 61 28,080,890,458 595,944 486,374 109,570 0 62 28,374,412,178 895,280 729,489 165,791 0 63 28,667,933,895 219,368 180,804 38,564 0 64 28,961,455,583 521,904 426,399 95,505 0 81.70% (426,399B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->78.57% (410,052B) 0x10DEDF: test_malloc (harness.c:138) | ->42.35% (221,032B) 0x10E375: q_insert_head (queue.c:59) | | ->42.35% (221,032B) 0x10EAA3: measure (constant.c:76) | | | ->42.35% (221,032B) 0x10EB7E: doit (fixture.c:136) | | | ->42.35% (221,032B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->42.35% (221,032B) 0x10AE1A: do_size (qtest.c:482) | | | ->42.35% (221,032B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->42.35% (221,032B) 0x10D338: interpret_cmd (console.c:247) | | | ->42.35% (221,032B) 0x10DBA0: cmd_select (console.c:601) | | | ->42.35% (221,032B) 0x10DE6D: run_console (console.c:674) | | | ->42.35% (221,032B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->36.21% (188,956B) 0x10E399: q_insert_head (queue.c:64) | | ->36.21% (188,956B) 0x10EAA3: measure (constant.c:76) | | | ->36.21% (188,956B) 0x10EB7E: doit (fixture.c:136) | | | ->36.21% (188,956B) 0x10EEB7: is_size_const (fixture.c:188) | | | ->36.21% (188,956B) 0x10AE1A: do_size (qtest.c:482) | | | ->36.21% (188,956B) 0x10CEA1: interpret_cmda (console.c:224) | | | ->36.21% (188,956B) 0x10D338: interpret_cmd (console.c:247) | | | ->36.21% (188,956B) 0x10DBA0: cmd_select (console.c:601) | | | ->36.21% (188,956B) 0x10DE6D: run_console (console.c:674) | | | ->36.21% (188,956B) 0x10C2D1: main (qtest.c:789) | | | | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) | | | ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.74% (9,096B) 0x10C946: malloc_or_fail (report.c:189) | ->01.57% (8,216B) 0x10CFF9: push_file (console.c:457) | | ->01.57% (8,216B) 0x10DDDE: run_console (console.c:659) | | ->01.57% (8,216B) 0x10C2D1: main (qtest.c:789) | | | ->00.17% (880B) in 1+ places, all below ms_print's threshold (01.00%) | ->01.39% (7,251B) in 11 places, all below massif's threshold (1.00%) ``` ## web server 實作 - web-server 引用自 [tiny-web_server](https://github.com/7890/tiny-web-server) - 修正裡面使用 sprintf 的實作，改用 snprintf ，對於長度過長不會發生溢位。 - 修正 local variable 的 scope ，不需要宣告在較大的 scope 中。 - 新增 web 指令在 qtest 中，可以開啟 web server ```cpp add_cmd("web", do_open_web, " | run a webserver"); ``` - 新增 closeweb 指令在 qtest 中，可以關閉 web-server ```cpp add_cmd("closeweb", do_close_web, " | close webserver"); ``` - 若沒手動關閉 web server ，程式也會在 quit 後，自動關閉 web server - 目前為了讓 web server 可以在 qtest 的背景執行，使用 fork 實作，之後會改成 coroutine

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.