# 2018q3 Homework2 (lab0)
contributed by < [`pjchiou`](https://github.com/pjchiou)>
---
## Overview
- 前置準備
- 測試環境
- 作業要求
- 開發過程
* q_new
* q_free
* q_insert_head
* q_insert_tail
* q_remove_head
* q_size
* q_reverse
- 現況
- 測試原理分析
* 為什麼不能用 `strdup` ?
* harness.c 與 harness.h 內的偵錯機制
* console.h 與 console.c 內如何管理各個指令與參數
* report.h 與 report.c 如何做到例外處理與輸出。
* qtest.c 的內容
* 如何測每個功能的執行時間?
- 自動測試
---
## 前置準備
- clang-format 的[使用方法](https://clang.llvm.org/docs/ClangFormat.html)中有提到可以與 vim 結合使用，其中第二個方法寫著可以把以下的指令加入 `.vimrc` 檔內，如此一來就會在存檔時自動修好格式。
```python
function! Formatonsave()
let l:formatdiff = 1
pyf ~/llvm/tools/clang/tools/clang-format/clang-format.py
endfunction
autocmd BufWritePre *.h,*.cc,*.cpp call Formatonsave()
```
但是如果你跟我一樣，最近才安裝 vim 與 clang-format 可能會跟我遇到一樣的問題。
1. clang-format.py 在哪?
2. 修正上述指令的路徑
3. 加入 `*.c`
首先我下載了 [clang](https://github.com/llvm-mirror/clang) 整個專案之後會得到 `clang-format.py` 這個檔案，之後試著在 vim 內存檔，會看到以下訊息。
:::warning
E319: Sorry, the command is not available in this version.
:::
後來 google 了很久，發現是 python 版本的問題，把指令 `pyf` 改成 `py3f` 如下，就搞定了。
```python
function! Formatonsave()
let l:formatdiff = 1
py3f ~/clang/tools/clang-format/clang-format.py
endfunction
autocmd BufWritePre *.c,*.h,*.cc,*.cpp call Formatonsave()
```
---
## 測試環境
```
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/
legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
$ cat /proc/version
Linux version 4.16.0-041600-generic (kernel@kathleen)
(gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3.2))
#201804012230 SMP Sun Apr 1 22:31:39 UTC 2018
```
---
## 作業要求
- [解說](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
- 其中提到一個重點:==可以自行加入變數到 queue_t 這個 structure==
Two of the functions: q_insert_tail and q_size will require some effort on your part to meet the required performance standards. Naive implementations would require O(n) steps for a queue with n elements. We require that your implementations operate in time O(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. You can do this by including other fields in the queue_t data structure and managing these values properly as list elements are inserted, removed and reversed.
---
## 開發過程
- Null queue 指的是 `q==NULL`;
- Empty queue 指的是 `q->head == NULL`;
因為先知道了會需要 O(1) 得到長度與 insert_tail 的操作，所以先改 structure 。
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head, *tail; /* Linked list of elements */
unsigned int iSize;
} queue_t;
```
### q_new
```cpp=1
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return (NULL);
q->head = q->tail = NULL;
q->iSize = 0;
return q;
}
```
### q_free
```cpp=1
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *ptr;
while (q->head) {
free(q->head->value);
ptr = q->head;
q->head = q->head->next;
free(ptr);
}
q->iSize = 0;
free(q);
}
```
- 想法是一直把 head 刪掉，直到沒有為止。
### q_insert_head
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
int iStringSize = 0;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
while (s && s[iStringSize++] != '\0')
;
newh->value = malloc(sizeof(char) * iStringSize);
if (!newh->value) {
free(newh);
return false;
}
for (int i = 0; i < iStringSize; i++)
newh->value[i] = s[i];
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
q->iSize++;
return true;
}
```
- 根據 `man strdup` 的描述， strdup 會自己去呼叫 malloc ，並傳回一個可以被 free 的 pointer。
- 本來只要 `newh->value = strdup(s)` 就好，但後面會提不能用的理由，所以只能自己來。
- 如果字串的空間要不到也算失敗。
- q->head 與 q->tail 只有可能==同時為 NULL 或 同時不為 NULL== 。
### q_insert_tail
```cpp=1
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
int iStringSize = 0;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->next = NULL;
while (s && s[iStringSize++] != '\0')
;
newh->value = malloc(sizeof(char) * iStringSize);
if (!newh->value) {
free(newh);
return false;
}
for (int i = 0; i < iStringSize; i++)
newh->value[i] = s[i];
if (q->tail)
q->tail->next = newh;
q->tail = newh;
if (!q->head)
q->head = newh;
q->iSize++;
return true;
}
```
### q_remove_head
```cpp=1
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (!q || !q->head)
return (false);
if (sp && q->head->value) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *ptr = q->head;
q->head = q->head->next;
if (!q->head)
q->tail = NULL;
free(ptr->value);
free(ptr);
q->iSize--;
return true;
}
```
- strncpy 不會呼叫 `malloc` 或 `free` 還可以用。
> #4 如果 `q = NULL`，是不是就不能再做 `q->head`了？[name=YanJiun][time=Sat, Sep 29, 2018 3:30 PM][color=#FCF538]
> > ` || ` 左邊如果是 true 後面就不會去做了，因此沒關係。所以說 `if (!q || !q->head)` 絕對不能反過來。可以參考 [The C programming language](http://www.dipmat.univpm.it/~demeio/public/the_c_programming_language_2.pdf) 2.6 節的描述與範例。
> > More interesting are the logical operators &&, and ||. Expressions connected by && or || are evaluated left to right, and evaluation stops as soon as the truth or falsehood of the result is known.
> > 意即在==確認結果是 true or false 的時候會立刻停下。==
> > [name=pjciou][time=2018 Sep 29 Sat 15:44]
> > >了解了。我英文很爛 QQ，我一直在逃避規格書。
> > >看來我該看一下 [The C programming language](http://www.dipmat.univpm.it/~demeio/public/the_c_programming_language_2.pdf) 了。
> > >謝謝你，受教了。[name=YanJiun][time=Sat, Sep 29, 2018 4:57 PM][color=#FCF538]
### q_size
```cpp=1
int q_size(queue_t *q)
{
return q ? q->iSize : 0;
}
```
### q_reverse
```cpp=1
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *ori_head = q->head, *ori_tail = q->tail;
list_ele_t *cur = q->head, *next = q->head->next, *prev;
while (next) {
prev = cur;
cur = next;
next = next->next;
cur->next = prev;
}
q->head = ori_tail;
q->tail = ori_head;
q->tail->next = NULL;
}
```
用張圖來說明這個想法，簡單來說就是把==把 *cur 走過的點轉向==。
:::info
初始化的時候。
```graphviz
digraph linkedList{
{rank=same; node1,node2,node3,node4}
node1->node2
node2->node3
node3->node4
prev
cur -> node1
next -> node2
}
```
1. 先把現在的位置記下。 `prev = cur;`
```graphviz
digraph linkedList{
{rank=same; node1,node2,node3,node4}
node1->node2
node2->node3
node3->node4
prev ->node1
cur -> node1
next -> node2
}
```
2. 移動到下個位置。 `cur = next;`
```graphviz
digraph linkedList{
{rank=same; node1,node2,node3,node4}
node1->node2
node2->node3
node3->node4
prev -> node1
cur -> node2
next -> node2
}
```
3. 在轉向前先記好下個位置。 `next = next->next;`
```graphviz
digraph linkedList{
{rank=same; node1,node2,node3,node4}
node1->node2
node2->node3
node3->node4
prev -> node1
cur -> node2
next -> node3
}
```
4. 轉向，然後重覆 (1.) 直到沒有下個點為止。 `cur->next = prev;`
```graphviz
digraph linkedList{
{rank=same; node1,node2,node3,node4}
node1->node2
node2->node1
node3->node4
prev -> node1
cur -> node2
next -> node3
}
```
:::
---
## 結果
:::success
Test performance of insert_tail, size, and reverse
--- trace-15-perf 7/7
--- TOTAL 100/100
:::
:::danger
意外發現有個 bug ，就是如果在 insert_head 與 remove_head 中使用 strdup 去複製字串，然後刪除的過程中完全不要去釋放字串的空間，還是可以拿滿分。
:::
---
## 測試原理分析
這個程式一共由
- report.h, report.c
- harness.h, harness.c
- queue.h, queue.c
- console.h, console.c
- qtest.c
等九個檔案所編繹而成。queue.h 與 queue.h 是我們所寫。其餘檔案我從以下議題開始逐步分析這個程式手動輸入的時候如何做到程式如何偵錯、如何分析使用者的指令、如何管理各項參數、如何輸出、最後做到自動測試。
1. 為什麼不能用 `strdup` ?
2. 程式如何知道我 double free? 探討 harcess.h 與 harness.c 內的偵錯機制。
3. 程式怎麼知道每個指令要做什麼? 觀察 console.h 與 console.c 內如何管理各個指令與參數。
4. report.h, report.c 如何做到例外處理與輸出。
5. qtest.c 的內容。
6. 如何測每個功能的執行時間?
### 為什麼不能用 `strdup`
首先我們從 `man strdup` 看
:::info
The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
:::
`strdup` 的行為是去呼叫 `malloc` 並把字串複製進這個新建立的位址，最後 return 這個新建的位址。跟我們要的功能一致，但在 `harness.c` 內有一段。
:::warning
```cpp
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
:::
換句話說，在 `queue.c` 內的 `malloc` 與 `free` 會被置換成一個自定義的函式。若使用 `strdup` ，就會變成在用 `malloc` 與 `test_free` ，程式就會出錯。
### harness.h 與 harness.c 內的偵錯機制
- 這個測驗機制，跟這篇 [malloc tutorial](http://danluu.com/malloc-tutorial/) 很像，不同的點在這個方法改用 `doubly linked list` 來做。
- [structure 在記憶體內的配置方式](https://fresh2refresh.com/c-programming/c-structure-padding/)與 structure 內變數宣告的順序有關，而這個測試機制會利用這一點，所以不能改 `harness.c` 內 `block_ele_t` 的宣告順序。更精確一點地說，最後一定要是 `magic_header` 然後是 `payload[0]` 。
```cpp
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_ele_t;
```
- 下圖是我們要用來做測試的資料結構，與 `block_ele_t` 有一點小小的差距，因為我們要 malloc 的空間會變，所以不能把 `magic_footer` 也寫進來，不過在 malloc 的時候，要留空間給 `magic_footer` ，因此可以看到在 `harness.c` 裡面寫著下方程式碼
```cpp
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
`size` 就是我們要的空間，最後的 sizeof(size_t) 就是留給 `magic_footer` 的空間。
:::info
```graphviz
digraph block_ele{
node[shape=record]
payload [label="這裡是 &payload ", shape=plaintext]
ptrofblock [label="這裡是 &block_ele_t ", shape=plaintext]
prevblock [label="<prev> ...前一個 block_ele_t..."]
block [label="<nextptr> *next|<prevptr> *prev|payload_size|magic_header|<ptr> 這裡是我們要的空間|magic_footer"]
nextblock [label="<next> ...下一個 next block_ele_t..."]
ptrofblock -> block:nextptr:nw
block:nextptr -> nextblock:next:nw
block:prevptr -> prevblock:prev:nw
payload -> block:ptr:nw
}
```
:::
- `payload[0]` 的意義在於==定位 *next, *prev, payload_size, magic_header== 這些額外資訊在記憶體內結束的位置，本身確實不佔空間。而且這個位置就是呼叫 `test_malloc` 時，回傳的位置；也是呼叫 `test_free` 時傳入的位置。
- 因此我們可以有以下關係式
- 我們要的空間大小為 `payload_size` bytes
- $block_ele_t = &payload - sizeof(block_ele_t)
- &magic_footer = &block_ele_t + sizeof(block_ele_t) + payload_size
- 定義幾個變數
```cpp
/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
/* Byte to fill newly malloced space with */
#define FILLCHAR 0x55
/* 永遠指向最新加入的 block_ele_t ，初始為 NULL */
static block_ele_t *allocated = NULL;
/* 記錄有幾個 test_malloc 出來的空間 */
static size_t allocated_count = 0;
```
接下來說明整個測驗的機制，首先假設我們做了 `test_malloc(10);` 會 `return` 一個 `(void *)p` ，如下圖所示。內部的值，可以透過上述三個關係式去設定。
```graphviz
digraph block_ele{
node[shape=record]
payload [label="<ptrofpayload> *p "]
ptrofblock [label="<blockptr> allocated "]
block [label="<nextptr> *next=NULL|<prevptr> *prev=NULL|10|0xdeadbeef|<ptr> 10 個 bytes 每個都存 0x55|0xbeefdead"]
ptrofblock:blockptr -> block:nextptr:nw
payload:ptrofpayload -> block:ptr:nw
}
```
這時如果再做一個 `test_malloc(5);` 會變成下圖，傳回 `*p` 。
```graphviz
digraph block_ele{
node[shape=record]
payload [label="<ptrofpayload> *p "]
ptrofblock [label="<blockptr> allocated "]
block [label="<nextptr> *next|<prevptr> *prev=NULL|5|0xdeadbeef|<ptr> 5 個 bytes 每個都存 0x55|0xbeefdead"]
block2 [label="<nextptr> *next=NULL|<prevptr> *prev|10|0xdeadbeef|<ptr> 10 個 bytes 每個都存 0x55|0xbeefdead"]
ptrofblock:blockptr -> block:nextptr:nw
block:nextptr -> block2:nextptr:nw
block2:prevptr ->block:nextptr:nw
payload:ptrofpayload -> block:ptr:nw
}
```
如果我們做了一個 `free(p)` ，開始檢查幾個項目
1. p == NULL ?
2. 設 block_ele_t *ptr = (size_t)p-sizeof(block_ele_t); 再由 allocated 為起點，逐步走訪每個 block_ele_t 看 ptr 是否在其中。如果不存在表示 free 了一個沒有 malloc 的位置。
3. 檢查 magic_head == 0xdeadbeef? 如果不相等，表示這個地方被改值了，有 Undefined behavior 出現。
4. 檢查 magic_foot == 0xbeefdead? 如果不是，表示用超過之前 malloc 的空間，這個值被覆寫了。
接著把這塊空間移出這個 doubly linked list ，然候真的 free 掉。
:::info
仔細觀察上述 `malloc` 行為可以發現，如果我們都使用 `strdup` 去複製字串，在 `free` 的時候都不要去 `free` 字串的記憶體，還是可以拿滿分。因為用 `strdup` 得到的空間，並不會在上述的 doubly linked list 內，因此偵測不到它的存在。
我的 [github](https://github.com/pjchiou/lab0-c/tree/NoFree) 內有另一個分支 NoFree ，就是利用這個漏洞拿滿分的版本。
:::
- 這個過程好像沒有規定我們得到的空間一定要是 `magic_head` 、然候緊接著的是我們要的空間、最後是 `magic_foot` 。看了`siahuat0727` 同學的共筆，我發現我忽略了 alignment 的問題，如果我們把 `block_ele_t` 改成下列方式會有什麼問題?
:::info
```cpp
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header;
char dummy //這裡加一個變數
unsigned char payload[0];
} block_ele_t;
```
我們的結構變為下圖
```graphviz
digraph block_ele{
node[shape=record]
payload [label="這裡是 &payload ", shape=plaintext]
ptrofblock [label="這裡是 &block_ele_t", shape=plaintext]
sizeofblk [label="sizeof(block_ele_t)", shape=plaintext]
block [label="<nextptr> *next|<prevptr> *prev|payload_size|magic_header|dummy|<ptr> 7 bytes空白|<sizeblk> 這裡是我們要的空間|magic_footer"]
ptrofblock:blockptr -> block:nextptr:nw
payload -> block:ptr:nw
sizeofblk -> block:sizeblk:nw
}
```
:::
因為我是 64 位元的系統，所以會有 7 bytes 的 padding，如果是 32 位元應該只會有 3 bytes(這裡我怕有錯，希望有人手邊有 32 位元系統幫驗證) 。當結構變為這樣， ==$block_ele_t = &payload - sizeof(block_ele_t)== 就不會成立。
別忘了， `&payload` 是同時是 `malloc` 與 `free` 傳出、傳入的位置，如果記憶體內的配置變成這樣，我們無法在 `free` 的時候從 &payload 推得 &block_ele_t 的位置。
如果改成下方 structure ，做手動對準，又會沒問題。
```cpp
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header;
char dummy[8] //手動對準
unsigned char payload[0];
} block_ele_t;
```
所以 `unsigned char payload[0]` 前方會是一個 `size_t` 的變數，這樣的設計就可以保證對準。
### console.h 與 console.c 內如何管理各個指令與參數
這個程式會把所有可用的指令、參數以及準備讀取的資料用 ==linked list== 去存， console.h 內有以下程式碼。
```cpp
typedef bool (*cmd_function)(int argc, char *argv[]);
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name; //命令名稱
cmd_function operation; //這個命令對應到的 function
char *documentation; //這個命令的說明，執行 qtest 打 help 可以看到
cmd_ptr next; //指向下一個命令
};
typedef void (*setter_function)(int oldval);
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name; //參數名
int *valp; //參數值位址(參數都是全域變數)
char *documentation; //參數說明
setter_function setter; //值改變時要做的事(目前沒作用)
param_ptr next; //下一個參數
};
```
而程式內靠著以下函式將全部可用的指令，在程式開始執行初期加入到這個 linked list 內。(參數的版本也很類似，就不多做解釋了)
```cpp=1
void add_cmd(char *name, cmd_function operation, char *documentation)
{
cmd_ptr next_cmd = cmd_list;
cmd_ptr *last_loc = &cmd_list;
while (next_cmd && strcmp(name, next_cmd->name) > 0) {
last_loc = &next_cmd->next;
next_cmd = next_cmd->next;
}
cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
ele->name = name;
ele->operation = operation;
ele->documentation = documentation;
ele->next = next_cmd;
*last_loc = ele;
}
```
這程式碼有點熟悉阿...跟 [Week3 隨堂測驗](https://hackmd.io/s/BkyQskjK7#)最後一題有點像，就是==由小到大排的插入排序法==
另外在 console.c 內有一個 structure 用以儲存每個 input file 。一樣是用 linked list 的方式將所有的檔案連起來。( `stdin` 也算是其中一個**檔案** )
```cpp
#define RIO_BUFSIZE 8192
typedef struct RIO_ELE rio_t, *rio_ptr;
struct RIO_ELE {
int fd; /* File descriptor */
int cnt; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
rio_ptr prev; /* Next element in stack */
};
```
- 如果使用者在啟動程式的時候，沒有指定讀取檔案，這個 linked list 內就只會有一個 object 代表 `stdin` 。
- 注意到這個程式內所有的指令函式都宣告成 func(int argc,char *argv[]) 的形式，這有助於統一管理全部的 function ，讓我們可以將所有的指令用同一種 pointer 去存取。不用寫一大堆的 if 去判斷該去呼叫哪個程式，而各自需要的參數自行由 argc, argv 之中去解析。
```cpp
bool do_quit_cmd(int argc, char *argv[]);
bool do_help_cmd(int argc, char *argv[]);
bool do_option_cmd(int argc, char *argv[]);
bool do_source_cmd(int argc, char *argv[]);
bool do_log_cmd(int argc, char *argv[]);
bool do_time_cmd(int argc, char *argv[]);
bool do_comment_cmd(int argc, char *argv[]);
bool do_new(int argc, char *argv[]);
bool do_free(int argc, char *argv[]);
bool do_insert_head(int argc, char *argv[]);
bool do_insert_tail(int argc, char *argv[]);
bool do_remove_head(int argc, char *argv[]);
bool do_remove_head_quiet(int argc, char *argv[]);
bool do_reverse(int argc, char *argv[]);
bool do_size(int argc, char *argv[]);
bool do_show(int argc, char *argv[]);
```
- 所以理所當然會有函式把 command line 的輸入轉成上述型式。並執行。
```cpp
//將 cmdline 變成 argc, argc[]
bool interpret_cmd(char *cmdline);
//去所有的指令中尋找名稱與 argv[0] 相等的，然候執行。
static bool interpret_cmda(int argc, char *argv[]);
```
總結一下手動測試的流程
1. 程式開始時有三個 linked list ，分別是 cmd_list, para_list, file_list 。存有所有的指令、參數、輸入檔(包含 `stdin` )
2. 當使用者輸入指令後，到 cmd_list 尋找對應的函式執行。這個對應的函式核心的部份就是我們在 queue.h, queue.c 中寫的，再加上許多的例外判斷。
3. 逐行執行指令，一旦觸發例外，記錄之，視其嚴重程度決定是否提早結束。
4. 當 file_list 空時(手動輸入這個不會達到)，或使用者輸入 `quit` 就會結束，並逐步釋放 cmd_list, para_list, file_list 及 我們在 queue.c 使用的空間。
### report.h, report.c 如何做到例外處理與輸出。
- 這兩個檔案跟其它檔比起來比較特別，兩者都沒有 #include 這個專案內的其它檔案，因此**最泛用**，可以拿到任何其它專案用去使用。
- 首先這個專案內把所有的例外狀況分級，並分別對應到不同的後續行為。
* MSG_WARN: 只是輸出一些訊息。
* MSG_ERROR: 用在函式的行為跟預期不符的情況。
* MSG_FATAL: 如果是 fatal error 的話會強制結束程式。
```cpp
typedef enum { MSG_WARN, MSG_ERROR, MSG_FATAL } message_t;
```
- 可以將輸出導入檔案，如果沒有指定的話就會導向 `stdout`
:::info
有一個比較特別的函式 `vfprintf` 我是第一次看到，可以先 `man vfprintf` 看一下其與相關函式的用法。
利用這個函式就可以做到==變動參數個數==的輸出，類似 `printf`
:::
接下來有兩個最主要的函式
```cpp=1
void fail_fun(char *format, char *msg)
{
sprintf(fail_buf, format, msg);
/* Tack on return */
fail_buf[strlen(fail_buf)] = '\n';
/* Use write to avoid any buffering issues */
rval = write(STDOUT_FILENO, fail_buf, strlen(fail_buf) + 1);
if (logfile) {
/* Don't know file descriptor for logfile */
fputs(fail_buf, logfile);
}
if (fatal_fun)
fatal_fun();
if (logfile)
fclose(logfile);
exit(1);
}
```
```cpp=1
void report_event(message_t msg, char *fmt, ...)
{
va_list ap;
bool fatal = msg == MSG_FATAL;
char *msg_name = msg == MSG_WARN
? "WARNING"
: msg == MSG_ERROR ? "ERROR" : "FATAL ERROR";
int level = msg == MSG_WARN ? 2 : msg == MSG_ERROR ? 1 : 0;
if (verblevel < level)
return;
if (!errfile)
init_files(stdout, stdout);
va_start(ap, fmt);
fprintf(errfile, "%s: ", msg_name);
vfprintf(errfile, fmt, ap);
fprintf(errfile, "\n");
fflush(errfile);
va_end(ap);
if (logfile) {
va_start(ap, fmt);
fprintf(logfile, "Error: ");
vfprintf(logfile, fmt, ap);
fprintf(logfile, "\n");
fflush(logfile);
va_end(ap);
fclose(logfile);
}
if (fatal) {
if (fatal_fun)
fatal_fun();
exit(1);
}
}
```
前者一旦觸發，程式一定會強制結束。使用在 malloc 空間來存指令、參數、輸入檔的時候，一旦無法拿到所需要的記憶體時；後者只有在 fatal error 時才會強制結束，其它狀況下會依使用者設定的參數決定是否輸出。這個參數可以在 ./qtest 內以 `option verbose [number]` 指令設定。
- 最後在這裡面定義了幾個變數，來模擬各種情況的發生，與記錄現在的記憶體使用量。
* mblimit：記錄最大可用記憶體空間 (mega bytes)
* timelimit：記錄最大允許執行時間
* allocate_cnt：malloc 的次數
* allocate_bytes： malloc 得到的總空間
* free_cnt：free 的次數
* free_bytes：free 的總空間
* peak_bytes：過程中最大的使用 bytes 數
* last_peak_bytes：看不出跟 peak_bytes 的差別...
* current_bytes：現在透過 malloc 使用的 bytes 即尚未 free 掉的空間
### qtest.c 的內容
檔案的開頭可以看到一堆指令被塞到存指令的 linked list (我在 console.c 提過的那個)內，為什麼這些指令要寫在 qtest.c 內而不是 console.c 內？我自己的想法是因為這些指令都==直接操作題目要的那個 linked list 內的元素==，題目要的 linked list q 就作為一個全域變數宣告在 qtest.c 內。
:::info
`getopt` 函式我是第一次看到，以前不知道有那麼方便的函式可以自動解析程式代入的參數，建議跟我一樣第一次看到的人先 `man getopt` 看看在做什麼，對閱讀 qtest.c 會大有幫助。
:::
qtest.c 裡大致上有兩個功能
- 初始化變數
- 提供另一種方式測試
如果我們輸入
```
./qtest -h
```
可以看到它提供了==直接從檔案讀取指令的功能==。我們可以用
```
./qtest -v 3 -f traces/trace-01-ops.cmd
```
看 qtest 去執行這個檔案內的所有指令的過程。看到這裡對如何做==自動==測試已經有個底了，就是利用一個 script 去丟一堆存有預設好指令的檔案，而這些檔案就存在 traces 資料夾內。
### 如何測每個功能的執行時間?
前面幾個段落我討論了這個測驗機制的原理，但最後幾個測試是在看 performance ，這個程式利用 `signal` 函式來達到這樣的效果。
```cpp
typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);
```
簡單來說這個功能可以指定當程式執行途中接收到編號 `signum` 訊號的時候，去執行 `handler` 這個函式。以下兩個 `signum` 在這個程式內有用到。[更多 signum 可以參考這裡](http://www.yolinux.com/TUTORIALS/C++Signals.html)
|signum|description|
|:--:|:--|
|SIGALRM|Alarm clock (POSIX) Indicates expiration of a timer. Used by the alarm() function.|
|SIGSEGV|(Signal Segmentation Violation) Invalid access to storage − When a program tries to read or write outside the memory it is allocated for it.|
在 qtest.c 可以看到以下程式碼
```cpp=1
/* Signal handlers */
void sigsegvhandler(int sig)
{
trigger_exception(
"Segmentation fault occurred. You dereferenced a NULL or invalid "
"pointer");
}
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
而 `alarm(unsigned int sec)` 函式可以讓我們在 sec 秒後，發一個 SIGALRM 訊號到程式。因此我們可以利用以下流程來做效能測試。
1. 設定 sec 秒後，發一個 SIGALRM 訊號。
2. 執行目標函式。
3. 若在 sec 秒內返回，則用 `alarm(0)` 取消尚未發出的 SIGALRM 。
4. 若沒有在 sec 秒內返回，則進入 `signal` 設定的函式內。
接下來還有最後一個問題要釐清。
:::warning
如果程式進了無窮迴圈，就算發出 SIGALRM 到自定義的函式內，但是離開自定義的函式後，不是又回到了無窮迴圈內?測試還是要繼續下去吧。
:::
以上這個問題利用 `sigsetjmp` 與 `siglongjmp` 兩個函式來處理，這兩個函式簡單來說就是==跨函式的 goto== 。我們觀察 qtest.c 內 `do_reverse` 有一段
```cpp
...
if (exception_setup(true))
q_reverse(q);
exception_cancel();
...
```
假設我的 `q_reverse` 寫到進無窮迴圈，我來看一下 `exception_setup` 與 `exception_cancel` 是怎樣讓我跳離無窮迴圈?以下程式碼在 harness.c 內
```cpp=1
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
/* Got here from longjmp */
jmp_ready = false;
if (time_limited) {
alarm(0);
time_limited = false;
}
if (error_message) {
report_event(MSG_ERROR, error_message);
}
error_message = "";
return false;
} else {
/* Got here from initial call */
jmp_ready = true;
if (limit_time) {
alarm(time_limit);
time_limited = true;
}
return true;
}
}
void exception_cancel()
{
if (time_limited) {
alarm(0);
time_limited = false;
}
jmp_ready = false;
error_message = "";
}
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
我們看 `man sigsetjmp` 的描述，有幾個重點
:::info
```cpp
int sigsetjmp(sigjmp_buf env, int savesigs);
void siglongjmp(sigjmp_buf env, int val);
```
setjmp() and sigsetjmp() return 0 when called directly; on the "fake" return that occurs after longjmp() or siglongjmp(), the nonzero value specified in val is returned.
The longjmp() or siglongjmp() functions do not return.
:::
1. 直接呼叫 `sigsetjmp` 會 return 0 ，如果是從 `siglongjmp` 回來的話會 return val 。
2. siglongjmp 不會 return 。
所以當我們執行以下程式的時候
```cpp
...
if (exception_setup(true))
q_reverse(q);
exception_cancel();
...
```
1. 先進入到 `exception_setup` #16~#22 內設定好 sec 秒(預設是 1 )內發出 SIGALRM ，然後 jmp_ready=true, return true 。
2. 執行 q_reverse ，在我們的假設下進無窮迴圈，發出 SIGALRM 訊號。
3. 進入到 `trigger_exception` jmp_ready==true ， 所以做 `siglongjmp(env,1)` 回到 `exception_setup #3` 的判斷式，因為這次是從 `siglongjmp` 回來，會 return 1 (也就是 `siglongjmp` 的第二個參數)，所以執行 #4~#14 ， jmp_ready=false 並記錄下發生的例外後， return false 。
4. 注意因為 siglonjmp 不會 return ，所以這時不是回到 `trigger_exception #41` ，而是回到 call `exception_setup` 的地方。也就是判斷要不要做 q_reverse 之前。
5. 因為得到 false ，所以跳過 q_reverse ，程式繼續執行。
---
## 自動測試
透過 Makefile 的內容我們可以知道輸入 `make test` 的時候實際上是去執行 `scripts/driver.py` 這個檔案。一打開我們就可以看到 15 個測試分別對應到的指令檔。許多部分都只是輸出而已，比較主要的是以下函式。
```python=
def runTrace(self, tid):
if not tid in self.traceDict:
print("ERROR: No trace with id %d" % tid)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.qtest, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
print("Call of '%s' failed: %s" % (" ".join(clist), e))
return False
return retcode == 0
```
從這之中我們可以知道兩點
1. 測試是用 `./qtest -v 1 -f [filename]` 這樣的方式去呼叫 qtest
2. 利用 qtest.c `main` 之中的 return 去判斷是否成功，所以每個測試只會有滿分跟零分兩種可能。
其餘的部分就是用一個陣列 hard code 所有的測試檔，然後逐個執行上述指令。
Sign in with Wallet
Connect another wallet