# 2021q1 Homework1 (lab0) contributed by < `tiffany6022` > ###### tags: `linux2021` > [作業說明](https://hackmd.io/@sysprog/linux2021-lab0) - [x] C Programming Lab - [x] q_new - [x] q_free - [x] q_insert_head - [x] q_insert_tail - [x] q_remove_head - [x] q_size - [x] q_reverse - [x] q_sort - [x] Address Sanitizer - [x] Valgrind - [ ] Coroutine - [ ] 解釋 select 系統 - [ ] 說明 antirez/linenoise 的運作原理 - [ ] 研讀論文 - [ ] 指出現有程式的缺陷 ## C Programming Lab 以下為實做方式以及遇到過的問題 ### 開始 * 進入 `queue.c` 和 `queue.h` 進行修改 * 輸入 `make` 、 `clean` 分別執行 編譯檔案 及 清除編譯檔案 * 輸入 `make test` 執行自動評分系統 * 輸入 `./qtest -f traces/[trace file].cmd` 執行單一測試檔 ### q_new * 建一個 empty queue ### q_free * 若一個已動態配置記憶體的 struct，裡面也有成員已動態配置記憶體了，那在釋放時應先從裡面的成員開始釋放，避免從 struct 先釋放而導致要釋放成員時找不到記憶體位置 :::warning 改進你的漢語表達，上面那句到底是什麼意思？在面試或者電話會議的場合中，你若說「從裡面 free 出來」，到底多少人可會意？ :notes: jserv ::: > 已修正 ```cpp= ... free(q->head->value); free(q->head); free(q); ... ``` ### q_insert_head * 當 newh->value 動態配置記憶體失敗時，要記得釋放掉之前 newh 配置的記憶體 * 計算分配記憶體長度給 value 時，除了 strlen(s) 還要 +1，因為 `strlen` 計算的長度不包含 terminating null byte ('\0') * `strncpy` 複製字串時，會連同 '\0' 一起複製 ```cpp= ... 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)); ... ``` ### q_insert_tail * 同 `q_insert_head` * 由於要達到 $O(1)$ 的常數時間複雜度，新增 `list_ele_t *tail` 這個新成員到 `struct queue_t` ```cpp= typedef struct { ... list_ele_t *tail; } queue_t; ``` * 要記得考慮只有當 q->tail 不是 NULL 時，才可以設 q->tail->next (一開始沒考慮到，造成 `trace-17-complexity` 錯誤) ```cpp= ... if (q->tail) q->tail->next = newt; ... ``` ### q_remove_head * 需要考慮字串最長的長度 bufsize，當字串超過限制長度時，要複製原有的字串，長度設為 bufsize - 1 ，因為要留一位給 '\0' (一開始看不懂忽略它XD，造成 `trace-06-string` 錯誤) ```cpp= ... if (sp) { if (strlen(q->head->value) < bufsize) { strncpy(sp, q->head->value, (strlen(q->head->value) + 1)); } else { strncpy(sp, q->head->value, (bufsize - 1)); sp[bufsize - 1] = '\0'; } } ... ``` ### q_size * 由於要在 $O(1)$ 的常數時間內執行完成，新增 `int size` 這個新成員到 `struct queue_t` ```cpp= typedef struct { ... int size; } queue_t; ``` ### q_reverse * 利用3個 pointer 紀錄目前位置及前後位置，將他們的 next 轉換 ```cpp= ... list_ele_t *_prev = NULL; list_ele_t *_curr = q->head; list_ele_t *_next = q->head->next; q->tail = _curr; while (_next) { _curr->next = _prev; _prev = _curr; _curr = _next; _next = _curr->next; } _curr->next = _prev; q->head = _curr; ``` ### q_sort * 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 merge sort * 原先用 `strcmp` 比較字串可以實做，但之後發現 `qtest.c` 裡面是用 `strcasecmp` 測試我們的程式，兩者的差別在於 `strcasecmp` 會自動忽略大小寫的差異，因而改用 `strcasecmp` 做比較 * 原本 merge() 是利用以下遞迴的方式寫，但會造成 `trace-15-perf` 發生 segmentation fault (core dumped) ```cpp= list_ele_t *merge(list_ele_t *l1, list_ele_t *l2) { if (!l2) return l1; if (!l1) return l2; if (strcasecmp(l1->value, l2->value) < 0) { l1->next = merge(l1->next, l2); return l1; } else { l2->next = merge(l1, l2->next); return l2; } } ``` * 改成沒有遞迴的版本 * 先比較兩個 list 的第一個 node 記錄起始位置 ```cpp= list_ele_t *merge(list_ele_t *l1, list_ele_t *l2) { list_ele_t *temp, *head; if (strcasecmp(l1->value, l2->value) < 0) { temp = l1; l1 = l1->next; } else { temp = l2; l2 = l2->next; } head = temp; while (l1 && l2) { if (strcasecmp(l1->value, l2->value) < 0) { temp->next = l1; temp = temp->next; l1 = l1->next; } else { temp->next = l2; temp = temp->next; l2 = l2->next; } } if (l1) temp->next = l1; if (l2) temp->next = l2; return head; } ``` * 利用2個 pointer，找到分割點，一個一次走1步，另一個一次走2步，當走得快的那個到終點時，慢的那個的位置就是 list 的中間 ```cpp= list_ele_t *mergeSortList(list_ele_t *head) { ... list_ele_t *slow = head; list_ele_t *fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; ... } ``` ### 結果 > 過程中遇到測資沒過，還傻傻的以為要改其他檔案的程式，其實到目前為止都只有改 `queue.c` 和 `queue.h` 這兩個檔案 ``` --- TOTAL 100/100 ``` :::danger 文字訊息不要用圖片展現！ :notes: jserv ::: > 好 --- ## Address Sanitizer ### 簡介 * [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) * 動態檢測 C/C++ 記憶體錯誤的工具 (程式執行時分析) * 錯誤類型︰ * Heap / Stack / Global buffer overflow * Stack: 儲存函式的區域變數 * Heap: 動態配置變數 * Golbal: 全域 * Use after free/return/scope * Initialization order bugs * Memory leaks ### 作業要求 * 開啟 Address Sanitizer，修正 `qtest` 執行過程中的錯誤 * 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除 ### 測試之前程式 ```shell $ make SANITIZER=1 $ make test ``` * ~~發現原本的100分是假的~~，`trace-17-complexity` 出錯了 * 不合法操作 `READ` 發生了 `global-buffer-overflow` 的錯誤，在 `console.c` 裡的 `simulation` 變數 ``` ==6540==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55ea3ce4f620 at pc 0x55ea3ce37c3a bp 0x7ffdf55fbd40 sp 0x7ffdf55fbd30 READ of size 4 at 0x55ea3ce4f620 thread T0 #0 0x55ea3ce37c39 in do_option_cmd /home/tiffany/linux2021/lab0-c/console.c:369 #1 0x55ea3ce36a22 in interpret_cmda /home/tiffany/linux2021/lab0-c/console.c:221 #2 0x55ea3ce37207 in interpret_cmd /home/tiffany/linux2021/lab0-c/console.c:244 #3 0x55ea3ce38433 in cmd_select /home/tiffany/linux2021/lab0-c/console.c:594 #4 0x55ea3ce389ad in run_console /home/tiffany/linux2021/lab0-c/console.c:667 #5 0x55ea3ce35531 in main /home/tiffany/linux2021/lab0-c/qtest.c:788 #6 0x7fbf5b4bd0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #7 0x55ea3ce32b8d in _start (/home/tiffany/linux2021/lab0-c/qtest+0x8b8d) 0x55ea3ce4f621 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55ea3ce4f620) of size 1 'simulation' is ascii string '' SUMMARY: AddressSanitizer: global-buffer-overflow /home/tiffany/linux2021/lab0-c/console.c:369 in do_option_cmd ``` #### 關於 global-buffer-overflow ```cpp // RUN: clang -O -g -fsanitize=address %t && ./a.out int global_array[100] = {-1}; int main(int argc, char **argv) { return global_array[argc + 100]; // BOOM } ``` * argc 一定大於等於 1 * 全域變數 global_array 想存取到超過它被配置的記憶體空間 #### 修改過程 * 打開 `console.c` 找到 `simulation`，發現問題出在 `simulation` 在初始化時是 `boolean` 型態，但在 `add_param` 函式的第二個參數是需要 `integer pointer` 型態，所以它就把 `bool` 強制轉成 `(int *)`，`bool` 配置的記憶體長度是 1 個位元組，而 `int` 則是 4 個位元組，因此發生錯誤 ```cpp= /* --- console.c 原本程式碼 --- */ bool simulation = false; ... add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL); ``` ```cpp= /* --- console.h 原本程式碼 --- */ extern bool simulation; ``` * 將 `simulation` 的初始化改成 `int` 型態 ```cpp= /* --- console.c 更改後程式碼 --- */ int simulation = 0; ... add_param("simulation", &simulation, "Start/Stop simulation mode", NULL); ``` ```cpp= /* --- console.h 更改後程式碼 --- */ extern int simulation; ``` ### 實做作業要求 ```shell $ make SANITIZER=1 $ ./qtest cmd> help ``` * 不合法操作 `READ` 發生了 `global-buffer-overflow` 錯誤，在 `console.c` 裡的 `echo` 變數 ``` ==6627==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5592c5c3c400 at pc 0x5592c5c2590f bp 0x7ffefd4bdf40 sp 0x7ffefd4bdf30 READ of size 4 at 0x5592c5c3c400 thread T0 #0 0x5592c5c2590e in do_help_cmd /home/tiffany/linux2021/lab0-c/console.c:307 #1 0x5592c5c25a22 in interpret_cmda /home/tiffany/linux2021/lab0-c/console.c:221 #2 0x5592c5c26207 in interpret_cmd /home/tiffany/linux2021/lab0-c/console.c:244 #3 0x5592c5c2794a in run_console /home/tiffany/linux2021/lab0-c/console.c:660 #4 0x5592c5c24531 in main /home/tiffany/linux2021/lab0-c/qtest.c:788 #5 0x7f23725460b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #6 0x5592c5c21b8d in _start (/home/tiffany/linux2021/lab0-c/qtest+0x8b8d) 0x5592c5c3c401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5592c5c3c400) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /home/tiffany/linux2021/lab0-c/console.c:307 in do_help_cmd ``` #### 修改過程 * 與上述問題相似 ```cpp= /* --- console.c 原本程式碼 --- */ static bool echo = 0; ... add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); ``` * 將 `echo` 的初始化改成 `int` 型態 ```cpp= /* --- console.c 更改後程式碼 --- */ static int echo = 0; ... add_param("echo", &echo, "Do/don't echo commands", NULL); ``` --- ## Valgrind ### 簡介 * 使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。 ### 作業要求 * 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤 * 並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗 ### 排除 qtest 實作的記憶體錯誤 #### 執行 ```shell $ make valgrind ``` * 發現每一個測資都會出現以下錯誤訊息 * 訊息中指明 * 有 1 個 16 bytes 的 block 被偵測為 “still reachable” * 有 19 個 129 bytes 的 block 被偵測為 “still reachable” * 有 1 個 160 bytes 的 block 被偵測為 “still reachable” * `still reachable`︰程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數 ``` ==9056== 16 bytes in 1 blocks are still reachable in loss record 1 of 3 ==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==9056== by 0x4A4F50E: strdup (strdup.c:42) ==9056== by 0x110134: linenoiseHistoryAdd (linenoise.c:1236) ==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325) ==9056== by 0x10C287: main (qtest.c:777) ==9056== ==9056== 129 bytes in 19 blocks are still reachable in loss record 2 of 3 ==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==9056== by 0x4A4F50E: strdup (strdup.c:42) ==9056== by 0x1100A8: linenoiseHistoryAdd (linenoise.c:1236) ==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325) ==9056== by 0x10C287: main (qtest.c:777) ==9056== ==9056== 160 bytes in 1 blocks are still reachable in loss record 3 of 3 ==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==9056== by 0x1100F4: linenoiseHistoryAdd (linenoise.c:1224) ==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325) ==9056== by 0x10C287: main (qtest.c:777) ==9056== ``` #### 修改過程 * 打開 `linenoise.c` 的 1236 行 (下方程式碼的第7行) 發現 `strdup` 函式出現問題 * `strdup` 是可以把要複製的內容複製給沒有初始化的指標，因為它會自動 malloc 給它，但使用結束後應手動 free 記憶體空間 * 程式中 `linecopy` 複製 `line` 的內容，而到後面 `history[history_len]` 又指向 `linecopy` 這個 char pointer，因此這邊的問題應該是出在最後 `history` 的記憶體位置沒有釋放乾淨 ```cpp= /* --- linenoise.c --- */ int linenoiseHistoryAdd(const char *line) { char *linecopy; ... linecopy = strdup(line); 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; } ``` * 找出與變數 `history` 釋放相關的程式碼 ==TODO== ### Massif 視覺化記憶體使用量 #### 執行測試 ```shell $ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd ``` * 產生的 massif.out.<pid> 檔，可以用以下指令輸出以文字呈現的圖表，以及詳細內容 ```shell $ ms_print massif.out.<pid> ``` * 也可用 [massif-visualizer](https://github.com/KDE/massif-visualizer) 進行視覺化分析 ```shell $ sudo apt-get install massif-visualizer $ massif-visualizer massif.out.<pid> ``` ![](https://i.imgur.com/c5OCUF8.png) #### 設計實驗 ==TODO==
Last changed by  
 
Tiffany Chen
329

Read more

2021q1 Homework2 (quiz2)

contributed by < tiffany6022 >

2/23/2024
2021q1 Homework4 (quiz4)

contributed by < tiffany6022 > 作業說明 [x] 解釋上述程式碼運作原理，包含 timeout 處理機制，指出改進空間並實作 [ ] 研讀 atomic_threadpool，指出其 atomic 操作的運用方式，並說明該 lock-free 的手法 [ ] 嘗試使用 C11 Atomics 改寫上述程式碼，使其有更好的 scalability 解釋程式運作原理 程式結構

5/28/2021
2021q1 Homework1 (quiz1)

contributed by < tiffany6022 >

4/23/2021
2021q1 Homework3 (quiz3)

contributed by < tiffany6022 > 作業說明 [x] 解釋上述程式碼運作原理，並提出改進方案; [x] 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 的函式實作; [ ] 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference，善用 GDB 追蹤和分析，確認字串的確符合預期地配置於 stack 或 heap; [ ] 嘗試將 quiz2 提到的 string interning 機制整合，提出對空間高度最佳化的字串處理工具函式庫 [ ] 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說;

4/14/2021
Read more from Tiffany Chen
Published on HackMD