# 2018q3 Homework2 (lab0)
Contributed by <`aben20807`>

###### tags: `sysprog2018`

## 開發記錄

### 環境

$ uname -a
Linux ben-UX410UQK 4.15.0-23-generic #25-Ubuntu SMP Wed May 23 18:02:16 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version 
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

### 結果

:::success
[專案連結](https://github.com/aben20807/lab0-c)，已達到 100/100
:::

### 結構
+ 要求：`q_insert_tail()`、`q_size()` 需要 $O(1)$
+ 解決：在結構中加上指向 tail 的 pointer 和 queue 的 size 即可在常數時間存取

### `q_new()`
+ `q` `malloc()` 後必須不是 `NULL` 才有 `head` 成員可以被指向
+ 而不管 `malloc()` 成功與否都要回傳 (失敗回傳 `NULL`)
+ 所以此處最簡潔語法就是當 `q != NULL` 時再去對成員初始化
+ [score]: `trace-10-malloc 7/7`

### malloc 機率性失敗
+ 遇到 `malloc` 失敗時，必須要有對應的處理方式
+ 例如 element 失敗可以直接回傳 `false`
+ 但若是 element 成功，但是 element 的 value 失敗，就需要先把剛剛的 element free 掉才能回傳 `false`
+ 解決：雖然處理例外的行數不多，但還是採用下水道式的設計，利用 `goto` 來做流程控制

### head、tail
+ 在第一個元素被插入時必須注意要把 `head`、`tail` 指向同一個元素，因為該元素是第一個也是最後一個
+ 從尾端加入時要另外注意 `tail == NULL` 的情況，因為是單向 linked list 所以一定要透過 `tail->next` 來插入尾端

### 複製字串

#### 長度
+ `strlen()` 的計算是不包含 `'\0'`
+ e.g. `strlen("abcd")` 是 4
+ 作業要求中的 `bool q_remove_head(queue_t *q, char *sp, size_t bufsize)` 若 `sp` 不為 `NULL` 就要複製 `bufsize - 1` 個字元並在最後加上一個 `'\0'`

#### `strncpy()` 的危險性
+ man page 中警告 `strncpy()` 不會自動在複製完後加上 `'\0'`
+ `char *strncpy(char *dest, const char *src, size_t n);`：從 `src` 複製 `n` 個字元到 `dest`
+ 其中有提及簡單的實作：

           char *
           strncpy(char *dest, const char *src, size_t n)
           {
               size_t i;
               for (i = 0; i < n && src[i] != '\0'; i++)
                   dest[i] = src[i];
               for ( ; i < n; i++)
                   dest[i] = '\0';
               return dest;
           }

+ 也就是當原始長度大於想要複製的長度時，目標字串就不會有 `'\0'` 結尾
+ "abcd\0" -4-> "abcd"
+ 一般測試時並不會有異狀，但這是很危險的，尤其是 `malloc` 不保證回傳的記憶體區塊會清空，而這次作業也有出現相關的測試[下方討論](https://hackmd.io/s/Bk_oVbiKm#%E4%B8%8D%E4%B9%BE%E6%B7%A8%E7%9A%84%E5%8D%80%E5%A1%8A)
+ 因此若只使用 `strncpy(sp, rm->value, bufsize - 1);` 會因為沒有 `'\0'` 結尾就印出一堆奇怪的東西
+ 解法1：給定 bufsize - 1 個字元後要在最後加上 `'\0'`
+ 解法2：改用 `snprintf()`
+ `int snprintf(char *str, size_t size, const char *format, ...);`
+ 保證目標會以 `'\0'` 結束
+ "abcd\0" -4-> "abc\0"

### `free(NULL);`
+ 因為 `free` 不是系統的，所以對 `NULL` free 會發生錯誤！[[link]](https://github.com/aben20807/lab0-c/blob/master/harness.c#L156-L160)

## 測試程式研究

### `malloc()`

#### 可以追蹤使用者行為
+ 有一個變數 `INTERNAL` [[link]](https://github.com/aben20807/lab0-c/blob/master/harness.h#L14) 是用來隔離呼叫 `malloc()` 的行為
+ 有定義 `INTERNAL` 的地方是使用 glibc 提供的 malloc
+ 沒定義就是呼叫 harness.c 所定義的 malloc，這樣就可以記錄使用者的使用情況甚至可以給定失敗的機率

#### 不乾淨的區塊
+ `malloc` 原本就不保證回傳區塊會是空的，只有 `calloc` 保證
+ 本次作業中實作的 `malloc` 會初始化成非空 [[link]](https://github.com/aben20807/lab0-c/blob/master/harness.c#L172)
+ e.g.

    char *s = malloc(30);
    printf("%s\n", s);

    UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU����

### Test

#### `scripts/driver.py`

+ `$ make test` 會去執行 `scripts/driver.py`
+ `scripts/driver.py -v [0-3]` 可以改變輸出的訊息量
+ 利用 `subprocess` 來執行 /traces 中的 .cmd 檔案 [[link]](https://github.com/aben20807/lab0-c/blob/master/scripts/driver.py#L68)，可解讀成

$ ./qtest -v [level] -f [cmd file]

+ 比較特別的是 verblevel (全名： Verbosity level) 設定，如果用 `$./qtest` level 會是 4 所以在輸入指令時可以看到 queue 中間的內容

#### `harness`

+ 定義自訂的 `malloc` 與 `free`

#### `qtest`

+ 一開始在處理 option 時有一個技巧，以輸入檔為例，宣告檔名變數時使用先給定 NULL，等到有指定的 option (-f xxx.cmd) 時，先將檔名寫進一開始有給空間的 buffer 再賦值給檔名變數，這樣做可以避免使用到 malloc 動態配置。簡易流程如下

char buf[BUFSIZE];
char *infile_name = NULL;
strncpy(buf, optarg, BUFSIZE);
infile_name = buf;

+ interpreter 初始化，加入 help、option、time 等指令，是利用 console.c 中的 `cmd_list` 記錄指令以及對應的 callback 函式 [[link]](https://github.com/aben20807/lab0-c/blob/master/console.c#L116)，結構如下：
+ 參數 (param) 同樣利用 `param_list`

typedef bool (*cmd_function)(int argc, char *argv[]);
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

+ qtest 在印出 queue 時是直接印出 queue 中的內容，而不是另存一個陣列，所以插入會刪除時能夠看到實際結果 [[link]](https://github.com/aben20807/lab0-c/blob/master/qtest.c#L434-L440)

#### `console`
+ [`int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);`](https://github.com/aben20807/lab0-c/blob/master/console.c#L595)
+ monitor multiple file descriptors
+ 可以達到 non-blocking，不必非要等待事件的發生
+ timeout
+ NULL：blocking
+ 0：non-blocking and return immediately
+ 大於 0：blocking until timeout
+ [[Ref] select()函數分析](http://darkmomo.blogspot.com/2008/11/select.html)

## 遭遇問題記錄
#### `[!] cppcheck not installed. Unable to perform static analysis.`
+ `$ sudo apt install cppcheck`