# 2021q1 Homework1 (lab0) contributed by < `YingMuo` > ###### tags: `linux2021` ## 環境設定 1. 安裝必要工具套件 ```shell $ sudo apt install build-essential git-core valgrind $ sudo apt install cppcheck clang-format aspell colordiff ``` 2. clang-format 設定 - vscode - [x] editor: format on save - C_Cpp: Clang_format_fallback Style 設定的跟.clang-format一樣 3. 引入 git-good-commit ## queue - [x] new - [x] free - [x] insert_head - [x] insert_tail - [x] remove_head - [x] size - [x] reverse - [x] sort ### struct ```cpp /* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; } queue_t; ``` ### new/free - 需要檢查 q 不是 null - 就 malloc/free ### insert_head/insert_tail - 需要檢查 1. q 不是 null 2. malloc element 不是 null 3. malloc string 不是 null - malloc 二個空間給 head/tail 和 value - 如果是第一次 insert head/tail 需要補上 tail/head - size++ ### remove_head - 需要檢查 q 不是 null、q->head 不是 null - 如果 sp 有值就用 strncpy 複製 q->head->value 過去 - 要 free head 和 value - size-- ### size - 需要檢查 q 不是 null - 回傳 q->size ### reverse - 需要檢查 q 不是 null、q->head 不是 null - tail 指向 head - 把所有 element 的 link 方向反轉 ### q_sort - 需要檢查 q 不是 null、q->head 不是 null - merge sort ## 找蟲 ### address sanitizer 在編譯時帶入 sanitizer ```shell make SANITIZER=1 ``` 接著執行 `./qtest`並輸入 `help`會看到 ```c ==4977==ERROR: AddressSanitizer: global-buffer-overflow on address 0x560410f423c0 at pc 0x560410f2b7dd bp 0x7ffc0dee4950 sp 0x7ffc0dee4940 READ of size 4 at 0x560410f423c0 thread T0 #0 0x560410f2b7dc in do_help_cmd /home/yingmuo/Desktop/linux2021/lab0-c/console.c:307 #1 0x560410f2b8f0 in interpret_cmda /home/yingmuo/Desktop/linux2021/lab0-c/console.c:221 #2 0x560410f2c0d5 in interpret_cmd /home/yingmuo/Desktop/linux2021/lab0-c/console.c:244 #3 0x560410f2d818 in run_console /home/yingmuo/Desktop/linux2021/lab0-c/console.c:660 #4 0x560410f2a405 in main /home/yingmuo/Desktop/linux2021/lab0-c/qtest.c:780 #5 0x7fe36fa3e0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #6 0x560410f27bad in _start (/home/yingmuo/Desktop/linux2021/lab0-c/qtest+0x8bad) 0x560410f423c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x560410f423c0) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /home/yingmuo/Desktop/linux2021/lab0-c/console.c:307 in do_help_cmd ``` ### 分析 裡面有說到幾個重點： 1. READ of size 4 代表有一個地方有 4 byte 的操作 ( 猜測是 int ) 2. 'echo' defined of size 1 被操作的 echo 只有 1 byte ```c=59 static bool echo = 0; ``` 3. /linux2021/lab0-c/console.c:307 in do_help_cmd 在這地方有被使用到，那就來看這裡的 code ```c=304 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; } ``` 看起來是對 plist 的操作，而 plist 則是 param_list，那麼往上追 param_list ```c=23 static param_ptr param_list = NULL; ``` ```c=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; } ``` 可以找到 param_list 是一個全域變數，並會在 init_cmd 透過 init_cmd() 裡的 add_param() 去對他初始化，會發現裏頭有用到 echo ```c=108 add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); ``` 其中使用 (int \*) 對 echo 進行強制轉型，但是 echo 的型態是 _Bool 只有 1 byte ，所以才會發生 overflow ### 改正 把 echo 改成 int 就可以了 ```c=59 static int echo = 0; ``` ### BUT，又出現新的錯誤了QQ 不過看起來跟 echo 是一樣的問題，所以就不放細節了 ```c=21 bool simulation = false; ``` 一樣改成 int 就沒事了 ## valgrind `make valgrind`會看到 ```c +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head ==11264== 4 bytes in 1 blocks are still reachable in loss record 1 of 3 ==11264== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==11264== by 0x4A4F50E: strdup (strdup.c:42) ==11264== by 0x11010E: linenoiseHistoryAdd (linenoise.c:1236) ==11264== by 0x110CA1: linenoiseHistoryLoad (linenoise.c:1325) ==11264== by 0x10C24C: main (qtest.c:769) ==11264== ==11264== 160 bytes in 1 blocks are still reachable in loss record 2 of 3 ==11264== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==11264== by 0x1100CE: linenoiseHistoryAdd (linenoise.c:1224) ==11264== by 0x110CA1: linenoiseHistoryLoad (linenoise.c:1325) ==11264== by 0x10C24C: main (qtest.c:769) ==11264== ==11264== 164 bytes in 19 blocks are still reachable in loss record 3 of 3 ==11264== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==11264== by 0x4A4F50E: strdup (strdup.c:42) ==11264== by 0x110082: linenoiseHistoryAdd (linenoise.c:1236) ==11264== by 0x110CA1: linenoiseHistoryLoad (linenoise.c:1325) ==11264== by 0x10C24C: main (qtest.c:769) ``` 看起來是有記憶體沒有被 free 掉，在 `linenoise.c` 可以看到要觸發 `freeHistory()` 必須執行到 `linenoise()`，然而要執行到 linenoise() 必須是在有 infile_name 的情況 ```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; } ``` 我選擇把 `freeHistory()` 的 static 拿掉，在 qtest.c 最後 call freeHistory()，就可以解決了 ```c ok = ok && run_console(infile_name); ok = ok && finish_cmd(); freeHistory(); ```