2020q3 Homework1 (lab0)

--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework1 (lab0) contributed by < `RinHizakura` > ## 簡介 lab 中使用許多工具協助養成良好的寫程式習慣，包含： * Git pre-commit hook * [git-good-commit](https://github.com/tommarshall/git-good-commit): 學習撰寫良好的 Git commit message * [cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具 * [clang-format](https://clang.llvm.org/docs/ClangFormat.html): 確保一致的程式風格 * [GNU Aspell](http://aspell.net/): 拼字檢查 * [valgrind](https://valgrind.org/): 動態程式分析工具 * [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer): 檢查記憶體的使用等...... 詳細的環境設定以及lab的相關說明請參閱 [I01: lab0](https://hackmd.io/@sysprog/2020-lab0?fbclid=IwAR2YOjtMYzE_kB5vqvBUOSM9OlR5hgvz7NHUGg21NOcN9Hb8vccxEV-yC3o)、[C Programming Lab: Assessing Your C Programming Skills](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) ## 如何測試測試所有的測資: > make test 針對單一個測試可以用: > ./qtest -f <command file> 得到更詳細的程式運行狀況，方便修改程式的錯誤 ## 基本實作詳細的程式內容請參見 [GitHub](https://github.com/RinHizakura/lab0-c)，這裡僅會記載大致的重點，以及本人因愚蠢而踩到的各種地雷:D :::warning :warning: GitHub repository 預設指定 master 或 main 分支，確認其中的程式碼可接受 code review :notes: jserv ::: > :ok_hand: 已經將作業程式碼 merge 到 master 上！ ### Queue structure ``` c= typedef struct { list_ele_t *head; list_ele_t *tail; int size; } queue_t; ``` 除了原始的head之外，加入了 * tail: 指向 queue 的尾端，目的是為了 $O(1)$ 的 insert tail * size: 計算 queue 的大小，目的是為了 $O(1)$ 得到 queue size ### New 產生一個新的 queue，記得初始化 queue 相關的資料結構即可。 ### Free 釋放 queue 前務必先檢查 queue 是否為 NULL。之後，先釋放 queue 上的每個 element 所用的空間(包含字串 allocate 的)，再釋放掉 queue 本身。 ### Insert head/tail 為新的 list element 和儲存的字串分配出相應的空間，串接在 queue 的 head / tail 端，再更新 q->head / q->tail 即可。需注意在 queue 為空(q->size = 0)的特例處理，此時需同時把 q->head, q->tail 指向新增的 element。另外有幾個需要特別小心的地方: :::info :bell: allocate 字串空間時的大小是 **strlen()+1**！記得要預留 `\0` 的位置！ ``` c= char *tmp = malloc(sizeof(char)*(strlen(s)+1)); ``` ::: :::info :bell: 注意 **free** 的地方！我們在要 list_ele_t 中的 char *value 的空間時，如果要不到而必須 return，務必記得把有要到但後來發現用不到的部份還回去！ ```c= list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); ... char *tmp = malloc(sizeof(char) * (strlen(s) + 1)); if (tmp == NULL){ /*** remember to release newh!! ***/ free(newh); return false; } ``` ::: ::: info :bell: [被禁止的 strcpy](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) ::: ### Remove head Remove 之前，首先要檢查 queue 是否為空，以及參數中的 sp 是否為具有空間的 buffer。q->head 指到的 element 是移除的目標，根據要求，先把目標中儲存字串複製到 sp 中，調整 q->head 指到的地方後，再釋放原本 q->head 的 element 所使用的空間。 ::: info :bell: 在釋放 element 本身前，記得先釋放 element 中使用的 char pointer ```c= free(tmp->value); free(tmp); ``` ::: :::info ```c= if (bufsize > strlen(q->head->value)) { strncpy(sp, q->head->value, strlen(q->head->value)); sp[strlen(q->head->value)] = '\0'; } else { strncpy(sp, q->head->value, bufsize-1); sp[bufsize-1] = '\0'; } ``` 需注意題目中說的 ***up to a maximum of bufsize-1 characters, plus a null terminator***，copy正確長度的字串！ ::: ### Get size 我們在 add / remove node 時會維護 queue 的大小，因此直接回傳 q->size 即可達到 $O(1)$ 的執行速度 ### Reverse 大致上，只要注意在調整 next 指向的 element 時，先讓 next 原本指向的 element 有一個 temp pointer 追蹤，避免遺失掉某個 element 的 referenece 即可。 ### Sort ~~有得抄真的很棒~~: [Merge sort of linked list](https://www.techiedelight.com/merge-sort-singly-linked-list/) 但要記得排序後把 q->head / q->tail 也指去對的地方！ :::info :bell: 使用stcmp來做字串的比大小! ::: ### Take care of queue 所有的 function 都必須處理 **queue == NULL** 以及 **q->head == NULL(empty)**，防止使用者錯誤的使用。 ### Segmentation fault 在第15個測資發生了core dump！我們可以用 AddressSanitizer 來找出出問題的地方。 > make SANITIZER=1 然後我們就可以看到以下的錯誤訊息，原來是遞迴到爆炸了... ``` ==24761==ERROR: AddressSanitizer: stack-overflow on address 0x7fffc6bf5fe8 (pc 0x7f407ce8ce6f bp 0x7fffc6bf6850 sp 0x7fffc6bf5fb0 T0) #1 0x56354e65eead in sorted_merge /home/rin/linux-internel/lab0-c/queue.c:221 ``` 所以我們需要一些不用遞迴的作法，可以參考 [Merge two sorted linked lists的Method 1 (Using Dummy Nodes)](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/)，網站上已經詳細解釋了程式的邏輯思維。大概注意這些事之後，然後你或許就可以拿到幾霸昏了(!?) ![](https://i.imgur.com/PKcIRkK.png) ## 使用qtest 可以在 driver.py 下面找到 traceDict、tracrProbs、maxScores，我們可以在下面加入新的測資，並設定該測資的分數。 ## Natural sort 此部份中，我們要修改排序的函式為 [natural sort](https://github.com/sourcefrog/natsort)。注意到 natural sort 分成 strnatcmp() 與 strnatcasecmp() 兩種，大致差異為是否轉換為大寫來比較字串(細節待補)，實驗中使用 strnatcasecmp() 來做 natural sort。把 strnatcmp.c 與 strnatcmp.h 加進專案並調整 Makefile 編譯後，便可以 include 函式庫然後使用了。 :::info 除了修改 `queue.c` 之外(257 行 )，記得也要調整 `qtest.c` 中的561行 ```c= if (strnatcasecmp(e->value, e->next->value) > 0) ``` ::: ~~你會發現，你會訝異，測資沒辦法通過~~。 ![](https://i.imgur.com/wg9aThA.png) 這裡其實帶出了一個很重要的概念，如果我們一開始是直接從natural sort下手來寫merge sort，當我們發現了 TLE，可能會首先懷疑是 merge sort 出了問題。然而事情的真相卻可能不是如此。既然我們發現了 strcmp 和 strnatcmp 可能是造成時間差異的地方，不妨簡單的練習一下如何產生視覺化的比較吧！可以參考 [C program for Time Complexity plot of Bubble, Insertion and Selection Sort using Gnuplot](https://www.geeksforgeeks.org/c-program-for-time-complexity-plot-of-bubble-insertion-and-selection-sort-using-gnuplot/)以及 [gnuplot 語法](https://hackmd.io/@sysprog/Skwp-alOg?type=view)來產生下面的圖。 ![](https://i.imgur.com/6yMoca0.png) 可以非常明顯的見到，隨著需要比較的字串數目增加，strnatcmp 所需耗費的時間成長劇烈。 :::info 延伸閱讀：[Speeding up string compare and sorting (compared to vanilla strcmp)](http://mgronhol.github.io/fast-strcmp/) ::: ## Valgrind & Massif 接下來，我們要練習使用Valgrind和Massif工具。 ### 執行Valgrind > make valgrind ### 執行Massif > valgrind --tool=massif ./qtest 印出massif的相關分析 > ms_print outputfile 透過 [massif-visulaizer](https://github.com/KDE/massif-visualizer) 視覺化分析的結果 ![](https://i.imgur.com/vkvEyLk.png) - [ ] 設計實驗，透過 Massif 對照記憶體用量的差異 ## dudect 論文內容~~英翻中練習~~請參閱[論文閱讀筆記](https://hackmd.io/@RinHizakura/S1PfuxJkv) ### 實作原理分析我們可以從 `qtest.c` 找到兩個相關的測試項目 * is_size_const * is_insert_tail_const 顧名思義，就是檢查 get size 跟 insert tail 是否可以 $O(1)$ 時間完成。 #### `is_size_const` ``` c= typedef struct { double mean[2]; double m2[2]; double n[2]; } t_ctx; ``` t 是 t_ctx 的資料結構，可以看到是用來儲存做 ttest 需要的統計資料。對照 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 和實作程式就不難推敲出這些變數代表的意義。 * mean: 平均值 * m2: 即為了求出標準差 $$ \sqrt[]{\frac{1}{n-1}\sum\limits_{i = 1}^n{(x_{i}-\bar{x})^2}} $$ 的 $$ \sum\limits_{i = 1}^n{(x_{i}-\bar{x})^2} $$ 部份 * n: 是樣本數量 for 迴圈中會進行 test_tries 次數的測量。`init_once` 會先初始化 t 跟 q (即我們 implement 的 queue_t)。接著的 for 迴圈中，`doit` 執行(number_measurements - drop_size * 2) 次數的測試，總計會進行 enough_measurements = 10000次。 #### `doit` 首先，配置需要的記憶體空間。然後按照 ***prepareinputs() -> measure() -> differentiate() -> updatestatistics() -> report()*** 的順序執行函式。 #### `prepare_input` 隨機產生 number_measurements 數量的字串。`input_data` 共有 number_measurements 個，每個單元的大小為 `chunk_size(16) * sizeof(uint8_t)`，會隨機產生，代表的是 insert 時要插入的字串長度。 `prepare_input` 函式會隨機決定每組資料的 classes(0 或 1、論文提到的 fix 或 random)。其中，class 0 的 input data 前兩個 byte 會被設為 0。這個階段也會順便生成隨機的字串 #### `measure` 根據 `mode` 參數進行對應的測試，可以看到透過 `drop_size` 會排除測試某些部份的資料(應該是對應論文中的 cropping 方法？)。然後就是 new 一個新的 queue 之後，insert 剛剛產生的字串。注意到 insert 的長度為 `(uint16_t *) (input_data + i * chunk_size) % 10000) `。由此可以看出 class 0 的資料會直接插入空字串。最後，就是把要測試的函式放在兩個 `cpucycles()` 間，得到函式的執行時間。 #### `differentiate` 透過 measure 得到的結果計算時間 #### `updatestatistics` 匯入 t-test 需要的資料，會過濾掉疑似 overflow 的資料 #### `report` 使用 `t_compute` 計算出 t 值 :::info :bell: **Hint** is_insert_tail_const 的架構大同小異，基本上差異只在doit的參數 ***mode*** 不同，因此是對不同的 function 進行測試。 ::: - [ ] 思考現有 dudect 實作的缺陷並提出解決方案 ## Select system call ### Select [select](https://man7.org/linux/man-pages/man2/select.2.html) [Beej’s Guide to Network Programming - Using Internet Sockets - 9.19. select()](http://beej-zhtw.netdpi.net/09-man-manual/9-19-select) ```c= int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); ``` * nfds: 三種 file descriptor 中的最高值加 1 * timeout: 設定 timeout 的時間，用來告訴 select() 要等待多久的時間。 select 會被 block 直到 * file descriptor 已經準備好 * system call 被 signal handler 中斷(interrupt)掉 * timeout 時間用完 * 3個fd_set * 如果你想要知道 set 上的哪些 sockets 有資料可以接收（就緒可讀），則將這個 set 放在 readfds 參數 * 如果你想要知道 set 上的哪些 sockets 有資料可以傳送（就緒可寫），則將這個 set 放在 writefds 參數 * 若你想知道哪些 sockets 有例外（錯誤）發生，則可以將 set 擺在 exceptfds 參數 * fd_set 的相關 MACRO * FD_SET(int fd, fd_set *set): 將 fd 新增至 set。 * FD_CLR(int fd, fd_set *set): 從 set 中移除 fd。 * FD_ISSET(int fd, fd_set *set): 若 fd 在 set 中則傳回 true。 * FD_ZERO(fd_set *set): 將 set 清為零。 * return * 成功時，傳回 3 個 set 中的 descriptors 總數 * 發生 timeout 回傳 0 * 錯誤時傳回 -1（並設定相對應的 errno） * sets 會被改過，用以表示哪幾個 sockets 是已經就緒的。 ### `console.c` 的實作 #### `run_console` `qtest` 會呼叫 `run_console()`。`push_file()` 首先檢查 `qtest` 的輸入是否是檔案，如果是檔案，判斷該檔案是否可以讀入;如果輸入是 NULL，則轉為接受 STDIN(鍵盤輸入)。接著，迴圈呼叫 `cmd_selct()` #### `cmd_select` ``` c= while (!block_flag && read_ready()) { cmdline = readline(); interpret_cmd(cmdline); prompt_flag = true; } ``` * `read_ready()` 會檢查 `buf_stack` 中使否有完整的的 cmd( \n 結尾的字串)。 * `readline()` 將 buf_stack 中的指令讀出，並透過 `interpret_cmd()` 解析cmd進行對應的行為 ```c= /* Process any commands in input buffer */ if (!readfds) readfds = &local_readset; /* Add input fd to readset for select */ infd = buf_stack->fd; FD_SET(infd, readfds); ``` * 如果 `readfds` 為 NULL ，把他指向 `local_readset` * 將 `buf_stack` 中檔案的 file descriptor 加到 readfds 中，為後面的 select system call 做好準備。 ```c= int result = select(nfds, readfds, writefds, exceptfds, timeout); if (result <= 0) return result; infd = buf_stack->fd; if (readfds && FD_ISSET(infd, readfds)) { /* Commandline input available */ FD_CLR(infd, readfds); result--; cmdline = readline(); if (cmdline) interpret_cmd(cmdline); } ``` 透過 select ，如果 readfds 中的 file 可讀，會得到 >0 的 result 。讀出 file 中的 commmand 且解析對應操作，並將該 file 從 readset 移除。 - [ ] 研究 [CS:APP RIO](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的 RIO 套件，重新 trace code 補充程式的細節 - [ ] 比照 qtest 實作，撰寫獨立的終端機命令解譯器 ## Address Sanitizer 使用指令: > make SANITIZER=1 > make test 開啟 Address Sanitizer，會發生記憶體的存取問題，並且在 `make test` 的第 17 個測試中無法通過效能測試。此外，我也發現 strnatcmp 會產生額外的問題！為了簡單化 debug 流程暫時先換回 strcmp，然後逐一來把問題解決！。 ### global-buffer-overflow ``` ==17733==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564872dc3ae0 at pc 0x564872bb34c7 bp 0x7ffcb721f7c0 sp 0x7ffcb721f7b0 ...... global variable 'simulation' defined in 'console.c:20:6' (0x55c4034e4ae0) of size 1 ``` 發現問題是在 console.c 的指令。 ```c= add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL); ``` 如果試圖把 bool pointer 型態轉成 int pointer，C 語言不知道從 1 byte 的 bool 到 8 bytes int 的該怎麼擴展，因而產生 undefined behavior。嘗試執行下面的程式，即使你預期第 9 行的會印出 1，但事實是，它會印出甚麼你根本無從得知。不過，多執行幾次，觀察每一次印出的最後一個 byte，應該就能看出端倪。 ```c= #include <stdio.h> #include <stdbool.h> int main(int argc, char **argv) { bool a = true; printf(" %x\n",a); printf(" %x\n",*(int *)&a); return 0; } ``` ``` $ ./a.out 1 d92a0001 $ ./a.out 1 2dc80001 $ ./a.out 1 d5a30001 $ ./a.out 1 87470001 ``` 直接把 simulation 的型態換成 int 就可以解決問題吧！然而這表示需要使用額外 3 byte 來表示一個 bool。調整作法為： ```c= typedef struct PELE param_ele, *param_ptr; struct PELE { ... void *valp; int type_size; ... }; ``` * 將 PELE 的指標改成 `void *`，並且增加一個 type_size 欄位紀錄指標原始 type 使用的位元數 ``` c= void add_param( ... void *valp, int type_size, ... ); ``` * 函式 `add_param` 也要做相對應的修改！當然也包含呼叫時傳入的參數，需要根據 `valp` 的原始型別傳入 `sizeof(bool)` 或者 `sizeof(int)` ```c= int valp_deref(param_ptr plist){ if(plist->type_size == sizeof(bool)) return *(bool *)plist->valp == true? 1:0; else return *(int *)plist->valp; } ``` * 設計函式 `val_deref()` 會根據指標的原始長度進行 dereference，在 `do_option_cmd()` 或者 `report()` 函式中會使用到，使對這些函式的輸入參數符合預期。 ```c= int oldval = 0; oldval = valp_deref(plist); if(plist->type_size == sizeof(bool)) memcpy(plist->valp, &value, sizeof(bool)); else memcpy(plist->valp, &value, sizeof(int)); ``` * 修改 `do_option_cmd()` ，可以看到透過 valp_deref 使 oldval 接受符合預期的 int，並且利用 memcpy ，根據原指標的長度 assign value。 :::warning 延伸思考: 如果使用的型態並非 bool 和 int?是否這個設計需要進一步修改？ ::: ## linenoise 的實作原理參照 [antirez/linenoise](https://github.com/antirez/linenoise) 改善 qtest 命令列。 ### 單行或多行編輯命令的輸入可以區分成 Single-line 或者 multi-line 的模式。前者會隨著單行的輸入內容溢出，而把輸入的 echo 向左滾動，在需要輸入大量內容又不想文字填滿整個視窗時可以使用這種模式;原始的 qtest 則是屬於後者，輸入超過單行可容納的量時，往下一行 echo。 linenoise 中的 API 為： ```c= void linenoiseSetMultiLine(int ml) { mlmode = ml; } ``` 透過去修改 `mlmode` 這個變數，決定使用的模式。輸入的時候，刷新 echo 的程式路徑為 linenoise -> linenoiseRaw -> linenoiseEdit -> inenoiseEditInsert -> refreshLine ```c= static void refreshLine(struct linenoiseState *l) { if (mlmode) refreshMultiLine(l); else refreshSingleLine(l); } ``` 先來檢視 refreshSingleLine 的實作。 ```c= struct abuf { char *b; int len; }; ``` ```c= static void refreshSingleLine(struct linenoiseState *l) { char seq[64]; size_t plen = strlen(l->prompt); int fd = l->ofd; char *buf = l->buf; size_t len = l->len; size_t pos = l->pos; struct abuf ab; ``` * `plen` 是 prompt 的長度，以 qtest 為例，就是前面的 `cmd>` * `buf` 是輸入的整體內容、`len` 是 `buf` 長度，`pos` 是往 `buf` 寫入的下個位置 * linenoise 會透過一個 append buffer 的結構，置放要顯示在單行中的內容 ```c= while((plen+pos) >= l->cols) { buf++; len--; pos--; } while (plen+len > l->cols) { len--; } ``` `l->cols` 是 shell 單行的長度，因此這裡是在把 `buf` 調整到倒數可顯示字元數的位置，計算可顯示的字元數量 `len`，以及 cursor 需要調整到的位置 `pos`。注意到因為 linenoise 支援往前(鍵盤往左鍵)移動 cursor，所以 `pos` 不會總是等於 `len` `l->cols` 由 `getColumns(stdin_fd, stdout_fd)` 所取得。`getColumns` 會先使用 [ioctl](https://man7.org/linux/man-pages/man2/ioctl.2.html) 這個 system call，嘗試透過 `ioctl(1, TIOCGWINSZ, &ws)` (參見 [ioctl_tty](https://man7.org/linux/man-pages/man2/ioctl_tty.2.html))，取得 terminal 的資訊。 * `1` 是 [file descriptor](https://en.wikipedia.org/wiki/File_descriptor)，在 POSIX 標準下就等同於 STDOUT_FILENO * TIOCGWINSZ 參數使得可以從 `ws`，得到 windows 大小的資訊因此這裡 `l->cols` 的取得可以簡單歸納成： ```c= struct winsize ws; ioctl(1, TIOCGWINSZ, &ws); l->cols = ws.ws_col; ``` 如果 `ioctl` 失敗，linenoise 會嘗試換方式得到資訊。嘗試改成透過 `getCursorPosition` 來獲得座標資訊(在 `getColumns` 中會透過控制碼移動 cursor，計算出單行的長度後再還原 cursor，細節暫時先不細看)。 ```c= static int getCursorPosition(int ifd, int ofd) { char buf[32]; int cols, rows; unsigned int i = 0; /* Report cursor location */ if (write(ofd, "\x1b[6n", 4) != 4) return -1; /* Read the response: ESC [ rows ; cols R */ while (i < sizeof(buf)-1) { if (read(ifd,buf+i,1) != 1) break; if (buf[i] == 'R') break; i++; } buf[i] = '\0'; /* Parse it. */ if (buf[0] != '\x1b' || buf[1] != '[') return -1; if (sscanf(buf+2,"%d;%d",&rows,&cols) != 2) return -1; return cols; } ``` * 首先，對 STDOUT 寫入 `\x1b[6n` (`ESC [6n`，查詢了一下是 [ANSI / VT100](https://www.csie.ntu.edu.tw/~r88009/Java/html/Network/vt100.htm) 的控制碼，用來 query cursor 的位置？這部份之後會再研究清楚)。 * 回應會是 `ESC [ rows ; cols R` 的格式，分析這個結果就可以得到 cursor 的位置可以試試用下面的 main 測試，注意到這裡會先透過 `tcgetattr` 得到 STDIN(fd = 0) 原始的 attribute，然後改變之(注意是設定成 **not** ICANON / ECHO) * ICANON: 啟用標準模式 (canonical mode)。允許使用特殊字元 * ECHO: 將輸入 echo 回螢幕上 ```c= int main(){ int start; struct termios term, restore; tcgetattr(0, &term); tcgetattr(0, &restore); term.c_lflag &= ~(ICANON|ECHO); tcsetattr(0, TCSAFLUSH, &term); start = getCursorPosition(0, 1); printf("%d \n", start); tcsetattr(0, TCSAFLUSH, &restore); return 0; } ``` ```c= abInit(&ab); /* Cursor to left edge */ snprintf(seq,64,"\r"); ``` 初始化 append buffer，並且把 cursor 移動到最左邊(從最左邊開始輸出) ``` c= abAppend(&ab,seq,strlen(seq)); /* Write the prompt and the current buffer content */ abAppend(&ab,l->prompt,strlen(l->prompt)); if (maskmode == 1) { while (len--) abAppend(&ab,"*",1); } else { abAppend(&ab,buf,len); } /* Show hits if any. */ refreshShowHints(&ab,l,plen); /* Erase to right */ snprintf(seq,64,"\x1b[0K"); abAppend(&ab,seq,strlen(seq)); /* Move cursor to original position. */ snprintf(seq,64,"\r\x1b[%dC", (int)(pos+plen)); abAppend(&ab,seq,strlen(seq)); if (write(fd,ab.b,ab.len) == -1) {} /* Can't recover from write error. */ abFree(&ab); } ``` * 把 "\r" append 進 append buffer * 把 `l->prompt` append 進 append buffer * 把 `buf` append 進 append buffer(maskmode 先不討論) * `refreshShowHints` 是 linenoise 可以自動補字的功能(可以參考 [linenoise: Hint](https://github.com/antirez/linenoise#hints)，暫且先不討論) * `\x1b[0K` 也是控制碼，清除 cursor 至行末。 * `\r\x1b[%dC` 移動 cursor 至正確位置 * 最後，把 buffer 寫到 STDOUT 上，釋放 append buffer ## 整合 linenoise 至 qtest ### 事前準備為了可以更好的使用 linenoise 的 API，需要對程式進行一些調整 ```c= bool run_console(char *infile_name) { if(infile_name == NULL){ char *line; while (!quit_flag && (line = linenoise("cmd> ")) != NULL) { interpret_cmd(line); free(line); } } else{ if (!push_file(infile_name)) { report(1, "ERROR: Could not open source file '%s'", infile_name); return false; } while (!cmd_done()) cmd_select(0, NULL, NULL, NULL, NULL); } return err_cnt == 0; } ``` 如果我們只是想要得到 linenoise 的功能，不考慮沿用原本 RIO + select 的讀取命令，一個比較粗暴的方法是把命令解譯器的部份修改成 linenoise 的 API。但發現 parsing 時會有問題，有亂碼產生。 :::warning 這個作法等於是捨棄在使用命令解譯器模式時 RIO + select 的使用，正在思考是否可能基於原本的實作強化其功能，將其與 linenoise 很好的整合在一起。初步是想不知道可否先用 linenoise 接受 standard input 在自己的結構上做處理(達到單行或者多行編輯的需求等)，然後再把從讀出的結果導回 RIO 處理的 `buf_stack`，讓 `readline` 去對 `buf_stack` 進行對應的處理。為了可以整合程式，下一步會研究 RIO 在此的應用。 ::: ``` $ ./qtest cmd> hello Unknown command 'hello' cmd> he Unknown command 'he��?V' ``` 追究其原因，是因為原本 `readline` 讀出的內容會在輸入後 append 一個 `\n` 加上一個 `\0`，但是 linenoise 處理的字串只有 append `\0`，導致在 `parse_args` 的處理與預期的格式不一致( `isspace(c)` 不會成立，因此 `dst` 不會被加上 `\0`) 為此，我們可以透過讓 `dst` 的末端都會 append 一個 `\0` 來簡單的修正。 ```c= static char **parse_args(char *line, int *argcp) { ... while ((c = *src++) != '\0') { if (isspace(c)) { if (!skipping) { /* Hit end of word */ *dst++ = '\0'; skipping = true; } } else { if (skipping) { /* Hit start of new word */ argc++; skipping = false; } *dst++ = c; } } /* 額外加入這一行！ */ *dst = '\0'; ... } ``` ### 單行或多行編輯我把 linenoise 使用單行或多行編輯選項的 API 加入到 qtest 的參數中。如果用 `./qtest --editmode 1` 的話可以用多行編輯啟動，如果用 `./qtest --editmode 0` 或者 `./qtest` 預設則會是單行編輯。此外，因為原始的 qtest 會透過 [getopt](https://www.man7.org/linux/man-pages/man3/getopt.3.html) 來解析參數，但是由於 getopt 只限定於短參數(一個減號加上單字元，例如 `-h`)，考慮強化命令列後參數的增加，不想把每個參數都用一個字元概括，因此調整成使用 [getopt_long](https://linux.die.net/man/3/getopt_long) 來 parsing，後者可以接受字串參數(兩個減號加上字串，例如 `--help`)。 ```c= struct option opts[] = { {"verbose", 1, NULL, 'v'}, {"file", 1, NULL, 'f'}, {"help", 0, NULL, 'h'}, {"log", 1, NULL, 'l'}, {"editmode", 1, NULL, 0}, }; while ((c = getopt_long(argc, argv, "hv:f:l:", opts, &option_index)) != -1) { switch (c) { case 0: if(!strcmp(opts[option_index].name, "editmode")) linenoiseSetMultiLine(atoi(optarg)); break; ...... ``` ### History ```c= bool run_console(char *infile_name) { ... while (!quit_flag && (line = linenoise("cmd> ")) != NULL) { linenoiseHistoryAdd(line); interpret_cmd(line); free(line); } ``` 在 run_console 中額外加入 `linenoiseHistoryAdd(line)` 就可以支援歷史命令的處理(通過上下鍵回復之前輸入的命令，btw 預設可以保留 100 筆歷史輸入) ### 命令自動補完我們需要註冊一個 callback function ```c= linenoiseSetCompletionCallback(completion); ``` 而 `completion` 的實作如下，這裡我透過從 `clist` 中取出 `add_cmd` 註冊過的命令，並透過 `cmd_maybe` 去比對如何補齊。如此一來，使用 `add_cmd` 去增加命令就可以讓 linenoise 自動添加，不需要對 completion 做額外的修改。 `add_param` 也同理，如果前面已經輸入 `option `(加上空白)，也可以補齊參數的部份(注意到參數的部份如果太長，目前是採直接忽略避免發生錯誤，之後也可以思考改進的方式)。 ```c= static bool cmd_maybe(char *target, const char *src){ for(int i = 0;i < strlen(src); i++){ if(target[i] == '\0') return false; if (src[i] != target[i]) return false; } return true; } static void completion(const char *buf, linenoiseCompletions *lc) { if(strncmp("option ", buf, 7) == 0){ param_ptr plist = param_list; while (plist) { char str[128] = ""; // if parameter is too long, now we just ignore it if(strlen(plist->name) > 120) continue; strcat(str, "option "); strcat(str, plist->name); if(cmd_maybe(str, buf)) linenoiseAddCompletion(lc, str); plist = plist->next; } return; } cmd_ptr clist = cmd_list; while (clist) { if(cmd_maybe(clist->name, buf)) linenoiseAddCompletion(lc, clist->name); clist = clist->next; } } ```

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.