# 2019q1 Homework1 (lab0)
contributed by < `0n3t04ll` >
說明
- [作業說明](https://hackmd.io/s/BJA8EgFB4)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 作業要求
### 實作 FIFO、LIFO 的 Queue
- q_new(): Create a new, empty queue
- q_free(): Free all storage used by a queue
- q_insert_head(): Attempt to insert a new element at the head of the queue (LIFO discipline).
- q_insert_tail(): Attempt to insert a new element at the tail of the queue (FIFO discipline).
- q_remove_head(): Attempt to remove the element at the head of the queue.
- q_size(): Compute the number of elements in the queue.
--- 以上節錄自 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 環境
```shell
$ uname -a
Linux starpt-K55VD 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
```
## 實作
### queue.h
在 queue.h 中看到 queue structure 的註解有說要加入其他 fields 來更有效率的實作 q_size(), q_insert_tail() ，在此我添加了 tail pointer 指向 queue 的尾端，用 size 在新增刪除中更新 queue 的大小，考慮到 size 應該不會出現負數，我用 unsigned int 來保存 data 。
```clike
typedef struct{
list_ele_t *head; /*linked list of elements*/
list_ele_t *tail;
unsigned int size;
}
```
### q_new()
透過 malloc 要一個 queue structure 的空間並初始化，需要判斷 malloc 成功與否。
```clike
/*
Create empty queue.
Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = (queue_t *) malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q)
return NULL;
// initial queue
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free()
用一個 element pointer curr 來遍歷整個 queue。
用另一個 element pointer tmp 來接收準備要被 free 掉的 element ，在 curr 更新後再 free 掉 tmp
```clike
/* Free all storage used by queue */
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
if (q) {
list_ele_t *curr = q->head;
while (curr != NULL) {
if (curr->value)
free(curr->value);
list_ele_t *tmp = curr;
curr = curr->next;
free(tmp);
}
free(q);
}
}
```
### q_insert_head()
要確認 newh, value 都有 malloc 成功，失敗就要 free 掉之前 malloc 的空間。
以 strlen(), strcpy() 來存資料，新增的同時也要更新 q->size ，由於增加了 tail pointer ，所以我透過 q->size 判斷是否要更新 `q->tail`。
```clike
bool q_insert_head(queue_t *q, char *s)
{
/* What should you do if the q is NULL? */
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newh) // allocate fail
return false;
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh->next = NULL;
newh->value = (char *) malloc(strlen(s) + 1);
if (!(newh->value)) {
free(newh);
return false;
}
strcpy(newh->value, s);
newh->next = q->head;
q->head = newh;
q->size += 1;
if (q->size == 1) // the first one
q->tail = newh;
return true;
}
```
### q_insert_tail()
先判斷 newh, value 是否 malloc 成功，其中一個失敗就要 free 掉先前 malloc 的。
insert tail 的時候要特別注意 tail, head 的更新。
```clike
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
if (!q)
return false;
list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->next = NULL;
newh->value = (char *) malloc(strlen(s) + 1);
if (!(newh->value)) {
free(newh);
return false;
}
strcpy(newh->value, s);
if (q->tail)
q->tail->next = newh;
q->tail = newh;
if (!(q->head))
q->head = q->tail;
q->size += 1;
return true;
}
```
### q_remove_head()
先判斷 queue 的 pointer 和 size，確保不為 NULL 或 empty。
用 tmp pointer 接收原本的 head 再對 queue 做更新，再判斷 sp 地址的有無來決定要不要複製 head->value ，最後 free 掉 tmp。
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (!q || q->size == 0) // q is NULL or q is empty
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
q->size -= 1;
if (q->size <= 1)
q->tail = q->head;
// if(sp && q->head != tmp)
if (sp) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(tmp->value);
free(tmp);
return true;
}
```
### q_size()
由於在增減 queue 的過程就在維護 queue 的 size ，故在此只需回傳 q->size 即可
```clike
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (!q)
return 0;
return q->size;
}
```
### q_reverse()
reverse 的部份我是以三個 pointer: prev, curr, last 來遍歷整個queue ，每經過一個 element 就修正 next pointer ，使其指回 prev ，最後更新這三個 pointer 。
head, tail 的更新是當所有 element reverse 後將 head assign 給 tail ， last assign 給 head。
```clike
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (!q)
return;
if (q->size == 0 || q->size == 1)
return;
list_ele_t *prev = NULL;
list_ele_t *curr = q->head;
list_ele_t *last = NULL;
while (curr != q->tail) {
last = curr->next;
// reverse link
curr->next = prev;
// update
prev = curr;
curr = last;
}
last->next = prev;
q->tail = q->head;
q->head = last;
}
```
## Valgrind Test
之前有用過 valgrind 一個一個測試過 qtest ，大致上跟 Naetw 說的一樣，會在13、14的時候壞掉，不過那時有看到 Naetw 跟老師說會 PR ，所以我就乖乖的等更新。
實際跑過一次是沒有問題的，只不過在測試13、14、15的時後跑的特別慢，讓我一度以為壞掉。
:::warning
「路見不平，拿 patch 來填」，請見 [PR #5](https://github.com/sysprog21/lab0-c/pull/5)
:notes: jserv
:::
```shell
$ make valgrind
cp qtest /tmp/qtest.TLAtCE
chmod u+x /tmp/qtest.TLAtCE
sed -i "s/alarm/isnan/g" /tmp/qtest.TLAtCE
scripts/driver.py -p /tmp/qtest.TLAtCE --valgrind
...
+++ TESTING trace trace-01-ops:
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
--- trace-05-ops 6/6
+++ TESTING trace trace-06-string:
--- trace-06-string 7/7
+++ TESTING trace trace-07-robust:
--- trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
--- trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
--- trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
--- trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
--- trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
--- trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
--- trace-13-perf 7/7
+++ TESTING trace trace-14-perf:
--- trace-14-perf 7/7
+++ TESTING trace trace-15-perf:
--- trace-15-perf 7/7
--- TOTAL 100/100
```
## AddressSanitizer 檢測
修改了 Makefile 中的 CFLAGS ，添加 sanitizer 參數，若有發生 UAF, heap overflow, memory leak 就會報錯。
參數如下：
```make=
CFLAGS = -O0 -g -Wall -Werror -fsanitize=address
```
因為沒有問題，所以什麼都沒顯示。
## 研究 q_test
### q_test.c
qtest.c main function 中的 while loop 主要是用來接收外部傳進來的參數，像是 verbose level, testcase file 等等，在此先忽略避免程式區塊過大。
後續主要程式如下：
```c=
queue_init(); // set q ptr, file_cnt, signalhandler
init_cmd(); // use linked list to link global cmd structure, paramter
// structure
console_init(); // same with above but linked queue function
set_verblevel(level);
if (level > 1) {
set_echo(true);
}
if (logfile_name)
set_logfile(logfile_name);
add_quit_helper(queue_quit);
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
```
queue_init() 負責初始化 queue pointer 為 NULL 和註冊 sigsegv, sigalrm 的 handler 。
init_cmd() 用 add_cmd() 函數把跟 queue 無關的 cmd 用 cmd_ptr 保存並串成 linked list 。
之所以用 linked list ，個人猜測是為了之後修改做的彈性設定。
下面是 cmd 的 structure ：
```c=
struct CELE {
char *name;
cmd_function operation; // funtion ptr point to cmd function
char *documentation;
cmd_ptr next;
};
```
而 console_init() 用了一樣的方式串連跟 queue 相關的 cmd 成 linked list 。
### interpret_cmda
真正處理 cmd 的輸入和操作是在 cmd_select() 內部 ，可以分為從檔案讀取 cmd 或是從 stdin 讀取。
讀取後後進入 interpret_cmd ，在裡面做 parse 接著傳給 interpret_cmda() 操作該 cmd ，方法是遍歷 cmd_list 並用 strcmp() 比對 cmd name 並且用該 cmd structure 中的 function ptr 執行 cmd 。
```c=
static bool interpret_cmda(int argc, char *argv[])
{
if (argc == 0)
return true;
/* Try to find matching command */
cmd_ptr next_cmd = cmd_list;
bool ok = true;
while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
next_cmd = next_cmd->next;
if (next_cmd) {
ok = next_cmd->operation(argc, argv);
if (!ok)
record_error();
} else {
report(1, "Unknown command '%s'", argv[0]);
record_error();
ok = false;
}
return ok;
}
```
### Exception Handler
cmd 操作都是透過 function ptr ，而在我比對所有的 cmd 後發現執行自己寫的 queue 操作前都會有一段應該跟 exception handler 相關的 statement ，以 do_new() 的 13~15 為例：
```c=
bool do_new(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
if (q != NULL) {
report(3, "Freeing old queue");
ok = do_free(argc, argv);
}
error_check();
if (exception_setup(true))
q = q_new();
exception_cancel();
qcnt = 0;
show_queue(3);
return ok && !error_check();
}
```
從名稱上來看應該是 exception 的前置作業，進入後發現用了 sigsetjmp ，該 function 從 manual 來看是用來保存 stack context/ environment ，好在處理 interrupt 或 error 後可以繼續執行。
```c=
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;
}
}
```
而專司處理 signal 的兩個 handler 內部都是執行 harness.c 中的 trigger expression
其中的 siglongjmp() 根據 manual 描述為回復在 sigsetjmp 中保存的 env 好返回先前執行狀態以便繼續執行，達到 exception handler 的效果。
```c=
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
因為對 signal 處理過程不熟，所以決定親自用 gdb 跟蹤一次。
若用單純的下斷點對 signal 是行不通的，必須要用 handle 處理，根據這份[manual](https://sourceware.org/gdb/onlinedocs/gdb/Signals.html)，必須用
```shell=
gdb$ handle SIGSEGV pass
```
讓該 sigsegv pass 到 handler 才能繼續，不然 gdb 只會卡死在發生 sigsegv 的指令上。
發現過程如下：
1. 進入 sigsegvhandler
2. 進入 trigger_expression
3. 由 jmp_ready 判斷 sigjmp_buf 是否準備好
* 若尚未準備好，立即 exit(1)
* 準備好則進入下個步驟
> 這邊我是參考 0xff77 同學的描述
4. 由 siglongjmp() 跳回 exception_setup() 中的 sigsetjmp() ， code 如下：
```c=
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;
```
5. 由於是從 siglongjmp 過來，故 return value 不為 0 ，進入 if scope ，重設好相關變數並印出錯誤訊息，最後返回至 exception_cancel()
6. exception_cancel() 取消 alarm 限制和重設
至此完成了一個 exception handler 的過程。
### test_malloc, test_free
在跟進 harness.c 後，發現裡面有個比較特別的 test_malloc, test_free ，在 harness.h 找了一下後發現程式測試的 malloc, free 會被 test_malloc, test_free 取代：
```c=57
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
下面為 test_malloc 程式碼，我把程式碼分為數個片段搭配文字解釋。
line 122 中用 noallocate_mode 來決定要不要 malloc 。
```c=120
void *test_malloc(size_t size)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
```
比較有趣的是 fail_allocation() ，用隨機的方式判斷 malloc 有沒有成功，我以前都是直接測完全失敗或完全成功，用隨機的方式進行測試應該是模擬 malloc 突然壞掉的情形下有無做好檢查。
```c=+
}
if (fail_allocation()) {
report_event(MSG_WARN, "Malloc returning NULL");
return NULL;
}
```
malloc 出來的 chunk 還要再包一層 block_ele_t ， block_ele_t 在實作上用到了之前在 C_and_CPP 板上看到的[一篇](https://www.ptt.cc/bbs/C_and_CPP/M.1545460670.A.A20.html)討論提過的技巧，透過 zero length array 可以動態改變 struct 空間，這邊因為 user 要求的空間不固定但又想包在同個 struct 所以用這種方法。
```c=
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;
```
malloc 出來的 block 會拆分為三個部分：原本放 data 的空間、額外的 block metadata 空間、 footer 空間。
```c=+
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
if (new_block == NULL) {
report_event(MSG_FATAL, "Couldn't allocate any more memory");
error_occurred = true;
}
```
從下面程式碼可以看出 qtest 透過 double linked list 維護 malloc 出來的 block。
除了自己用 double linked list 維護 block 外， test_malloc 還在 block 的 header, footer 加上 MAGICHEADER, MAGICFOOTER 兩個常數，猜測是為了要檢查有無 heap overflow 的發生。
```c=+
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
```
test_free() 對 test_malloc() 出來的 block 做操作，開頭先判斷有無設定 noallocate_mode 和 p 的合法性。
```c=
void test_free(void *p)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to free disallowed");
return;
}
if (p == NULL) {
report(MSG_ERROR, "Attempt to free NULL");
error_occurred = true;
return;
}
```
透過找出 block footer 位置並且比對 MAGICFOOTER 有無被修改來確認是否發生 heap overflow ，驗證了上面的猜想。這種設計理念跟 canary 如出一轍。
```c=+
block_ele_t *b = find_header(p);
size_t footer = *find_footer(b);
if (footer != MAGICFOOTER) {
report_event(MSG_ERROR,
"Corruption detected in block with address %p when "
"attempting to free it",
p);
error_occurred = true;
}
```
在 header, footer 的地方放上 MAGICFREE ，在 data 的地方填上 FILLCHAR ，表示該 block 已經被 free 掉。把要 free 的 block 從 double linked list 中 unlink 掉後再將之 free 。
```c=+
b->magic_header = MAGICFREE;
*find_footer(b) = MAGICFREE;
memset(p, FILLCHAR, b->payload_size);
/* Unlink from list */
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
free(b);
allocated_count--;
}
```
test_free(), test_malloc() 之所以用額外的 double linked list 做串連是為了在測試結束後，透過遍歷 block list 評估 leak memory 的情形。這點在 do_free() 中的 allocation_check() 得到解答。
## /scripts/driver.py
從 Makefile 的 test 可以發現用來自動評測的方式是透過 python script 實現。
主要的評測 class 為 Tracer ，而評測主要的 method 為 Tracer.run() 。
scoreDict 用字典保存 testcase 和相對應的得分， tid 顧名思義為 testcase 的 id 。
```python3=
def run(self, tid = 0):
scoreDict = { k : 0 for k in self.traceDict.keys() }
print("---\tTrace\t\tPoints")
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
print("ERROR: Invalid trace ID %d" % tid)
return
tidList = [tid]
score = 0
maxscore = 0
if self.useValgrind:
self.command = 'valgrind'
else:
self.command = self.qtest
self.qtest = ''
```
從 self.traceDict[t] 取出 testcase name 輸出測是訊息，接著把從 tidList 取出的 t 傳入 self.runTrace() ，裡面會透過 subprocess 執行：
```shell=
./qtest -v 1 -f [testcase name]
```
subprocess 的回傳值再傳回給 Tracer.run ，並將字串格式化輸出檔名、得分、總分。然後把該項得分加總至 score 當作最後的總分。
```python3=
for t in tidList:
tname = self.traceDict[t]
if self.verbLevel > 0:
print("+++ TESTING trace %s:" % tname)
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
print("---\t%s\t%d/%d" % (tname, tval, maxval))
score += tval
maxscore += maxval
scoreDict[t] = tval
```
Sign in with Wallet
Connect another wallet