--- tags: jserv-Linux --- # 2021q1 Homework1 (lab0) contributed by < `jw910731` > # 環境設定 我用的是Arch Linux，在這邊紀錄遇到的雷 1. aspell 沒有字典 - 需要額外安裝 `aspell-en` 來下載英文字典 2. clang-format 找不到套件 - 在 Arch Linux 裡面的 `clang-format` 指令是放在 `clang` 套件裡面，安裝即可 此外的套件名稱以我的印象都是一樣，不然就是名稱改動甚小，隨意搜尋馬上就可找到 # 基礎作業實作 - 基礎的Linked List based Queue ## 進度 - [x] new - [x] free - [x] insert_head - [x] Implement - [x] Test - [x] insert_tail - [x] Implement - [x] Test - [x] remove_head - [x] size - [x] reverse - [ ] sort - [x] Mental Implementation - [ ] Implementation - [ ] Test ## Queue struct ```diff /* Queue structure */ typedef struct { - list_ele_t *head; /* Linked list of elements */ + list_ele_t *head, *tail; /* Linked list of elements */ + int size; } queue_t; ``` ## Helper Functions 本人~~生性健忘~~，所以需要 Helper Function 統一重複操作 - ele_create ```cpp= /* * Create New Node * Return false if malloc failed * Otherwise return true */ static inline bool ele_create(list_ele_t **newh, char *s) { *newh = malloc(sizeof(list_ele_t)); // return false if malloc failed if (*newh == NULL) return false; // copy string content size_t len = strlen(s) + 1; // count in additional space for c string null terminator // malloc string space (*newh)->value = malloc(len); if ((*newh)->value == NULL) { // when malloc for string failed // prevent memory leak on failed memory allocation free(*newh); return false; } // copy string content strncpy((*newh)->value, s, len); // initialize fields (*newh)->next = NULL; return true; } ``` - ele_delete ```cpp= /* * Delete a node * Passed pointer is advance to next node automatically * Passed pointer must not be null nor pointed to NULL * Otherwise, the result is not guaranteed */ static inline void ele_delete(list_ele_t **del) { free((*del)->value); // free string list_ele_t *tmp = (*del)->next; // save pointer for next node free(*del); *del = tmp; } ``` ## new / free - **new** :::spoiler **Code** ```cpp= queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); // when allocation failed return NULL if (q == NULL) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ::: - **free** :::spoiler **Code** ```cpp= void q_free(queue_t *q) { // free iterated through lists if (q != NULL) { for (list_ele_t *it = q->head; it != NULL;) { ele_delete(&it); } } /* Free queue structure */ free(q); } ``` ::: `new` 基本上只要把每個要使用的 properties 初始化過就好，特別注意 `malloc` 失敗時的狀況就好 `free` 稍微麻煩一些，但基本上要注意的不外乎是 1. 參數為NULL 特判掉 2. 走訪 Linked List 走過去就 `free` 掉 ## insert_head / insert_tail - **insert_head** :::spoiler **Code** ```cpp= bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; // when q is NULL return false if (q == NULL) return false; // handle node creation failed if (!ele_create(&newh, s)) { return false; } newh->next = q->head; q->head = newh; // correctly initialize tail when is NULL if (q->tail == NULL) q->tail = q->head; // maintain size ++(q->size); return true; } ``` ::: - **insert_tail** :::spoiler **Code** ```cpp= bool q_insert_tail(queue_t *q, char *s) { list_ele_t *newh; // when q is NULL return false if (q == NULL) return false; // if create node fail, return false if (!ele_create(&newh, s)) { return false; } // concat to existed list // prevent empty list if (q->tail != NULL) { // concat node to current list q->tail->next = newh; } else { // is the first element in list q->head = newh; } // set tail to new node q->tail = newh; // maintain size ++(q->size); return true; } ``` ::: 主要還是要注意參數為 `NULL` 的狀況與 `malloc` 爛掉的狀況 此外就是分配空件與使用 `strncpy` 時要考慮到 C String NULL Terminator 所佔據的空間 我因此直接將內部計算好的字串長度(實作為 `strlen` 的回傳值)直接加 1 ### insert_head 為了在 Queue 為空時可以好好維護 `tail` ，因此特判為空的狀況，有想過有沒有比較優雅的解，但好想睡所以之後再想辦法 ### insert_tail 基本上如法泡製 `insert_head` 的實作後，只有少數幾個點要注意。當整個 Queue 為空的時候，應該要在此時額外維護 `head` 的狀態。 :::danger 目前遇到自動檢測程式對於我的`insert_tail`的實作是不是常數時間複雜度的測試，給出的答案並不穩定，目前還沒什麼頭緒為什麼會爛掉 ::: ## reverse :::spoiler **Code** ```cpp= void q_reverse(queue_t *q) { // let the q_size do the null check if (q_size(q) <= 1) return; list_ele_t *prev = NULL, *tail = q->tail; q->tail = q->head; for (list_ele_t *it = q->head; it != NULL;) { // forward iterator temp list_ele_t *tmp = it->next; // reverse linkage it->next = prev; prev = it; // advance prev it = tmp; // advance iterator } q->head = tail; } ``` ::: 基本上是直觀的 in-place reverse 實作 額外要注意的是要好好更新 `head` 與 `tail` 指標，不然之後的存取操作可能出錯！ ## sort 目前打算要以 Merge Sort 來實作，過程不用複製，且每個函數的區域變數極少，推估空間複雜度 ( 主要是 Stack 花費 ) 可到 $\mathcal{O}(\log n)$ **尚未實作，只完成精神實作而已** # 抓蟲 ## 使用 ASan 尋找傳說中的 Invalid Memory Access 先使用 `make SANITIZER=1` 召喚 ASan 現身，然後我就得到了 ``` ==28994==ERROR: AddressSanitizer: global-buffer-overflow on address 0x560f4b4bb6c0 at pc 0x560f4b4a50ca bp 0x7ffffe755390 sp 0x7ffffe755380 READ of size 4 at 0x560f4b4bb6c0 thread T0 #0 0x560f4b4a50c9 in do_help_cmd /lab0-c/console.c:307 #1 0x560f4b4a51dd in interpret_cmda /lab0-c/console.c:221 #2 0x560f4b4a59ab in interpret_cmd /lab0-c/console.c:244 #3 0x560f4b4a7082 in run_console /lab0-c/console.c:660 #4 0x560f4b4a3d82 in main /lab0-c/qtest.c:780 #5 0x7f6f2d5c8b24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24) #6 0x560f4b4a15cd in _start (/lab0-c/qtest+0x85cd) 0x560f4b4bb6c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x560f4b4bb6c0) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /lab0-c/console.c:307 in do_help_cmd ``` 然後來抓個關鍵字 "global buffer overflow" 告訴我們這個爛掉的記憶體存取是來自全域變數，且存取點是在 `console.c` 的第 307 行 然後 "READ of size 4" 告訴我他**可能**把他當 `int` 存取，但爛掉了！ 然後找找 307 做了什麼 ```cpp=296 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, plist->documentation); plist = plist->next; } return true; } ``` 看來是 `*plist->valp` 存取爛掉了呢 (整行就他一個整數存取，或精確而言的 4 byte read access) 然後就回溯回去看是誰的錯吧！ 使用神奇 CLion 幫我找到 `plist` 的寫入點，會找到 `add_param` 這個函數是唯一的寫入點，以下是節錄的函數 prototype ： > 其實這個功能gdb也有, 名字叫做hardware watchpoint(也有人說這叫hardware breakpoint), 相關操作可以在[這裡](https://sourceware.org/gdb/onlinedocs/gdb/Set-Watchpoints.html#Set-Watchpoints)看看 > [name=asef18766] ```cpp=134 void add_param(char *name, int *valp, char *documentation, setter_function setter) { // 略 ele->valp = valp; // 依舊略 } ``` 再溯源到 `add_param` 的 invoker 會找到所有呼叫者都在 `init_cmd` 裡面，其中的 108 行就是我們要找的問題了！ ```cpp=88 void init_cmd() { cmd_list = NULL; param_list = NULL; err_cnt = 0; quit_flag = false; add_cmd("help", do_help_cmd, " | Show documentation"); add_cmd("option", do_option_cmd, " [name val] | Display or set options"); add_cmd("quit", do_quit_cmd, " | Exit program"); add_cmd("source", do_source_cmd, " file | Read commands from source file"); add_cmd("log", do_log_cmd, " file | Copy output to file"); add_cmd("time", do_time_cmd, " cmd arg ... | Time command execution"); add_cmd("#", do_comment_cmd, " ... | Display comment"); add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL); add_param("verbose", &verblevel, "Verbosity level", NULL); add_param("error", &err_limit, "Number of errors until exit", NULL); add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); init_in(); init_time(&last_time); first_time = last_time; } ``` 我們會發現 108 行裡面 ```cpp=108 add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); ``` 一個 bool 變數被取指標後，指標被轉型成 `int`，但 `int` 的長度是 4 個 byte，但 bool 卻是 1 byte ( 在我的機器上是這樣，前面對行別長度的描述不是 portable 的 ) `int` 並不保證與 `bool` 型態等長，所以會導致對這個轉型後的指標 ( `(int *) &echo` ) 進行操作時導致記憶體存取錯誤！ 要順便注意其實 `(int *) &simulation` 也有剛才上述的問題，也要記得一併清除，同時因為 `simulation` 是一個 exported symbol ，所以還要注意需要對 header 做對應的修改。