# 2021q1 Homework1 (lab0) contributed by < `Jings1017` > ###### tags: `linux2021` ## 測試環境 ``` $ cat /etc/os-release NAME="Ubuntu" VERSION="20.04.2 LTS (Focal Fossa)" $ cat /proc/version Linux version 5.8.0-44-generic (buildd@lgw01-amd64-054) (gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #50~20.04.1-Ubuntu SMP Wed Feb 10 21:07:30 UTC 2021 ``` ## 作業要求 [參考連結](https://hackmd.io/@sysprog/linux2020-homework1) ## 實作 Queue ### 定義 queue structure 為了達到作業要求 - 需在 $O(1)$ 時間內完成， 故需要兩個指標分別指向 queue 的頭尾 另外需得知 queue size 多大，存放在 size 中 ```c= typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; } queue_t; ``` ### q_new() 因為 malloc() 在取長度為0或是記憶體發生錯誤時會回傳NULL，所以可利用其回傳值來判斷是否有成功取得 queue_t 之空間 若成功取得，便將 head , tail 初始化成 NULL，而 size 初始化成 0，否則回傳 NULL ```c= { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ### q_free(queue_t *q) 可利用 while 走訪整個 queue 結構，先將 value的 空間釋放，再釋放該元素的空間，最後釋放出 q 的空間，避免造成 memory leak ```c= { if (!q) return; list_ele_t *node = q->head; while (node) { list_ele_t *tmp = node->next; free(node->value); free(node); node = tmp; q->size--; } free(q); } ``` ### q_insert_head(queue_t *q, char *s) 首先，判斷 queue 是否存在，否則回傳 false 再配置一個新的 node 的空間，存放欲插入之 node， 並配置該 node->value 所需之空間，並將 s 複製到其中 最後再連接到 queue 上，並更新 q->size 之值 ```c= { if (!q) return false; list_ele_t *newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(strlen(s) + 1); if (!newh->value) { free(newh); return false; } strncpy(newh->value, s, strlen(s) + 1); if (!q->tail) q->tail = newh; newh->next = q->head; q->head = newh; q->size++; return true; } ``` ### q_insert_tail(queue_t *q, char *s) 在配置記憶體空間的部分與 `q_insert_head` 雷同， 相異之處在於下方程式碼 line 10 ，須明確設定 `newh->next=NULL` 因為插入在尾端，須確保後面沒有接其他節點 最後則是判斷此次插入是否為該 queue 之第一個元素，是的話則須更新 q->head 的值為 newh，確保執行其他操作不會導致有 `q->head==NULL` 的狀況發生 ```c= { if (!q) return false; list_ele_t *newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->next = NULL; newh->value = malloc(strlen(s) + 1); if (!newh->value) { free(newh); return false; } strncpy(newh->value, s, strlen(s) + 1); if (!q->head) q->head = newh; else q->tail->next = newh; q->tail = newh; q->size++; return true; } ``` ### q_remove_head(queue_t *q, char *sp, size_t bufsize) 再作業要求中有提到，須對欲刪除之字串進行處理，處理方式為將此字串複製到 sp 中存放，但為了避免 bufsize 小於原字串之長度，故統一在 sp 最後一個字元放入 `'\0'` ```c= { if (!q || !q->head) return false; list_ele_t *node = q->head; q->head = q->head->next; if (sp) { strncpy(sp, node->value, bufsize); sp[bufsize - 1] = '\0'; } free(node->value); free(node); if (!q->head) q->tail = NULL; q->size--; return true; } ``` ### q_size(queue_t *q) 根據作業要求，直接回傳 q->size 能確保此函式能在 $O(1)$ 內完成 若 q 或 q->head 未取得記憶體位置，則回傳 0 ```c= { if (!q || !q->head) return 0; return q->size; } ``` ### q_reverse(queue_t *q) 可以利用 while 從頭走訪每個元素，逐一反轉接到 rev_list，走訪完即可得到反轉之queue ```c= { if (!q || !q->head || q->size <= 1) return; list_ele_t *rev_list = q->head; list_ele_t *aux_list = q->head->next; q->tail = rev_list; rev_list->next = NULL; while (aux_list) { list_ele_t *tmp = aux_list; aux_list = aux_list->next; tmp->next = rev_list; rev_list = tmp; } q->head = rev_list; } ``` ### q_sort(queue_t *q) 在排序的部份，因作業要求須再 $O(nlgn)$ 內完成， 所以採用 merge sort 的方式實作，可確保在 worst case 中也是在 $O(nlgn)$ 的範圍內完成 ```c= { if (!q || !q->head || q->size <= 1) return; q->head = mergeSort(q->head); list_ele_t *tail = q->head; while (tail->next) { tail = tail->next; } q->tail = tail; } ``` ### merge(list_ele_t *l1, list_ele_t *l2) ```c= { if (!l2) return l1; if (!l1) return l2; list_ele_t *curr, *head; /* choose head */ if (strcmp(l1->value, l2->value) < 0) { head = l1; l1 = l1->next; } else { head = l2; l2 = l2->next; } curr = head; while (l1 && l2) { if (strcmp(l1->value, l2->value) < 0) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; } if (l1) curr->next = l1; if (l2) curr->next = l2; return head; } ``` ### mergeSort(list_ele_t *head) ```c= { if (!head || !head->next) return head; /* divide two parts */ 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 = mergeSort(head); list_ele_t *l2 = mergeSort(fast); return merge(l1, l2); } ``` ## 利用 Valgrind 檢測記憶體空間管理 ### 安裝 ``` $ sudo apt instal massif-visualizer ``` ### 測試 ``` $ make valgrind ``` ### 視覺化記憶體之使用情形 先執行以下指令，可得到ㄧ輸出檔 massif.out file valgrind --tool=massif ./qtest -f <test-data> 再將此輸出檔，利用以下指令開啟，會得到視覺化的分析圖表 massif-visualizer <massif.out file> :::info 正常的記憶體用量應該回到 0 KB 之使用量， 表示所有動態產生的記憶體空間皆有被歸還， 即 Total Memory Heap Consumption 最後會回到 0 若 Total Memory Heap Consumption 沒有回到 0 ， 則表示有記憶體空間未被歸還 故可由此工具容易判斷是否有 memory leak 的現象產生 ::: ### 實際指令 ``` $ make valgrind $ valgrind --tool=massif ./qtest -f ./traces/trace-16-perf.cmd $ massif-visualizer massif.out.5708 ``` ![](https://i.imgur.com/w2tQXl4.png) ``` $ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd $ massif-visualizer massif.out.5733 ``` ![](https://i.imgur.com/CtcRpwu.png) ## Address Sanitizer ``` $ make clean $ make SANITIZER=1 ``` ``` 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 ``` ``` $ ./qtest -v 3 -f traces/trace-17-complexity.cmd ``` ``` cmd> # Test if q_insert_tail and q_size is constant time complexity cmd> option simulation 1 ================================================================= ==3798==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5591927ca5e0 at pc 0x5591927b2ae8 bp 0x7ffdc3ee4940 sp 0x7ffdc3ee4930 READ of size 4 at 0x5591927ca5e0 thread T0 #0 0x5591927b2ae7 in do_option_cmd /home/jingsian/linux2021/lab0-c/console.c:369 #1 0x5591927b18d0 in interpret_cmda /home/jingsian/linux2021/lab0-c/console.c:221 #2 0x5591927b20b5 in interpret_cmd /home/jingsian/linux2021/lab0-c/console.c:244 #3 0x5591927b32e1 in cmd_select /home/jingsian/linux2021/lab0-c/console.c:594 #4 0x5591927b385b in run_console /home/jingsian/linux2021/lab0-c/console.c:667 #5 0x5591927b03e5 in main /home/jingsian/linux2021/lab0-c/qtest.c:780 #6 0x7f43416d20b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #7 0x5591927adb8d in _start (/home/jingsian/linux2021/lab0-c/qtest+0x8b8d) 0x5591927ca5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5591927ca5e0) of size 1 'simulation' is ascii string '' SUMMARY: AddressSanitizer: global-buffer-overflow /home/jingsian/linux2021/lab0-c/console.c:369 in do_option_cmd Shadow bytes around the buggy address: 0x0ab2b24f1460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab2b24f1470: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab2b24f1480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab2b24f1490: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0ab2b24f14a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 =>0x0ab2b24f14b0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 0x0ab2b24f14c0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9 0x0ab2b24f14d0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 0x0ab2b24f14e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0ab2b24f14f0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 0x0ab2b24f1500: 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 ==3798==ABORTING ``` * 把錯誤訊息擷取出來 ``` SUMMARY: AddressSanitizer: global-buffer-overflow /home/jingsian/linux2021/lab0-c/console.c:369 in do_option_cmd ``` 故可得知，須檢查 console.c ，針對 do_option_cmd 進行分析 ```c= /* line 340 in console.c */ static bool do_option_cmd(int argc, char *argv[]) { if (argc == 1) { param_ptr plist = param_list; report(1, "Options:"); while (plist) { report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation); plist = plist->next; } return true; } for (int i = 1; i < argc; i++) { char *name = argv[i]; int value = 0; bool found = false; /* Get value from next argument */ if (i + 1 >= argc) { report(1, "No value given for parameter %s", name); return false; } else if (!get_int(argv[++i], &value)) { report(1, "Cannot parse '%s' as integer", argv[i]); return false; } /* Find parameter in list */ param_ptr plist = param_list; while (!found && plist) { if (strcmp(plist->name, name) == 0) { int oldval = *plist->valp; // here *plist->valp = value; if (plist->setter) plist->setter(oldval); found = true; } else plist = plist->next; } /* Didn't find parameter */ if (!found) { report(1, "Unknown parameter '%s'", name); return false; } } return true; } ``` 並檢查 report function ```c= /* line 91 in report.c */ void report(int level, char *fmt, ...) { if (!verbfile) init_files(stdout, stdout); if (level <= verblevel) { va_list ap; va_start(ap, fmt); vfprintf(verbfile, fmt, ap); fprintf(verbfile, "\n"); fflush(verbfile); va_end(ap); if (logfile) { va_start(ap, fmt); vfprintf(logfile, fmt, ap); fprintf(logfile, "\n"); fflush(logfile); va_end(ap); } } } ``` 主要原因是因為這邊讀取時 type 是 int (4 byte) 但在 simulation 宣告時 type 為 bool (1 byte)，所以會出錯 * 修正 ```c= bool simulation = false; -> 改成 -> int simulation = false; extern bool simulation; -> 改成 -> extern int simulation; static bool echo = 0; -> 改成 -> static int echo = 0; ``` * 再執行一次指令 ``` $ make clean $ make SANITIZER=1 $ ./qtest -v 3 -f traces/trace-17-complexity.cmd ``` * 結果 ``` cmd> # Test if q_insert_tail and q_size is constant time complexity cmd> option simulation 1 cmd> it Probably constant time cmd> size Probably constant time cmd> option simulation 0 Freeing queue ```
Last changed by  
 
Jings27
312

Read more

Linux2021 Homework2(bitcpy)

contributed by < Jings1017 > GitHub 1. 解釋程式碼運作原理 #include <stdint.h> void bitcpy(void *_dest, /* Address of the buffer to write to */ size_t _write, /* Bit offset to start writing to */ const void *_src, /* Address of the buffer to read from */

6/28/2021
2021-04-06 `Jings1017`

contributed by < Jings1017 > 測驗 2 dequeue( ) static void dequeue(queue_t *q, int *fd) { node_t *old_head; pthread_mutex_lock(q->head_lock); /* Wait until signaled that queue is non_empty. * Need while loop in case a new thread manages to steal the queue

4/6/2021
2021q1 Homework2 (quiz2)

contributed by < Jings1017 > 測驗 1 程式碼分析 list.h list_add_tail Add a list node to the end of the list

3/30/2021
2021q1 Homework1 (quiz1)

contributed by < Jings1017 > 測驗題 解析 node 結構定義 typedef struct __node{ int value; struct __node *next; } node_t

3/18/2021
Read more from Jings27
Published on HackMD