---
tags: 作業
---

# 2019q1 Homework1 (lab0)
contributed by < `ab37695543xs` >
## 開發環境

架構：               x86_64
CPU 作業模式：       32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
每核心執行緒數：     2
每通訊端核心數：     4
Socket(s):           1
NUMA 節點：          1
供應商識別號：       GenuineIntel
CPU 家族：           6
型號：               142
Model name:          Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
製程：               10
CPU MHz：            2099.944
CPU max MHz:         3400.0000
CPU min MHz:         400.0000
BogoMIPS:            3600.00
虛擬：               VT-x
L1d 快取：           32K
L1i 快取：           32K
L2 快取：            256K
L3 快取：            6144K
NUMA node0 CPU(s)：  0-7

## 作業目標
- [x] 英文閱讀
- [x] C 語言程式設計基礎
- [x] 準備 GNU/Linux 開發工具
- [x] 學習使用 Git 與 GitHub
- [ ] 學習效能分析
- [x] 研究自動測試機制

CMU [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 準備了 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知:
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing redundant information in data structures.
* Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

實驗目標為實作 queue
* first in, first out (FIFO)
* last in, first out (LIFO)

## 基本要求
### queue.h
為了滿足 O(1) 的時間要求下，實作出 `q_insert_tail()` 與`q_size()`，便在資料結構上新增了 `tail` 與 `size` 來紀錄

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

### queue.c
#### q_new()
成功分配記憶體的話，就初始化 `q`，反之 `q` 會回傳 `NULL`

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* initialize the queue */
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

#### q_size()
由於透過額外 field 來記錄 queue 的大小，且在 `q_new()` 已初始化，這邊直接回傳即可
> 犯錯的地方：
> 由於初始化是在 q_new() 時進行，需要考慮到未初始化的情況，即 q 為 NULL

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->size;
    else
        return 0;
}

#### q_insert_head()
* 考慮傳入的 `q` 與記憶體分配的 `malloc()` 與 `strdup()` 為 `NULL` 的可能
* 若複製字串空間不夠時，會視為插入失敗，同時釋放該節點
* 需要考慮最初的情況，head 和 tail 為同一個，避免插入失敗
* 有新節點的情況也會需要更新 size

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    /* set the element */
    newh->value = strdup(s);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    newh->next = q->head;
    /* maintain the queue */
    q->head = newh;
    if (q->tail == NULL)  // same element
        q->tail = newh;
    q->size++;
    return true;
}

#### q_insert_tail()
由於透過額外 field 記錄 tail 位置，所以省去遍尋的時間，剩下邏輯同 `q_insert_head()`

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    /* set the element */
    newt->value = strdup(s);
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    newt->next = NULL;
    /* maintain the queue */
    if (q->head == NULL)  // same element
        q->head = newt;
    else
        q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

#### q_free()
* 由於是整個 queue 要 free，沒有必要保留 head，所以透過移動 head 來依序移除
* 字串在儲存時有經由 `strdup()` 分配記憶體，所以要手動 free
* 最後所有節點 free 完後，head 和 tail 也就不復存在，可以直接 free 掉 queue
> 犯錯的地方：
> * 只要有參照指標 q 的地方，都應該檢查 q 是否為 NULL
> * 雖然 free(NULL) 是可行的，但在 while 裡先使用到 `q->head`，所以會先失敗

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    list_ele_t *tmp;
    while (q->head != NULL) {  // next element
        tmp = q->head;
        q->head = tmp->next;
        free(tmp->value);  // strdup()
        free(tmp);
    }
    /* nodes all freed */
    free(q);
}

#### q_remove_head()
* 要移除 head 一定要先檢查 head 存不存在
* 這邊要將刪除的 head 所存的字串複製到終點 `sp`，同時有限制複製的字元數不超過 `bufsize`
* 考慮到超過 `bufsize` 的字串不會複製到 `'\0'`，這邊是先將 `sp` 統一設為 `'\0'`，再將 `bufsize - 1` 以內的字元複製過去
* 刪除節點同樣需要更新 size
> 犯錯的地方：
> * 一開始只考慮到檢查 head 而已，忽略了 q 為 NULL 的情況
> * 字串複製時忽略了 sp 為 NULL 時，會造成無法寫入的情形

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    /* pop the element */
    if (sp != NULL) {
        memset(sp, (int) '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    free(q->head->value);
    /* maintain the queue */
    list_ele_t *tmp = q->head;
    q->head = tmp->next;
    free(tmp);
    q->size--;
    return true;
}

#### q_reverse()
反轉的部分一開始寫的是後面的版本 (由尾到頭依序)，後來改良的是以下版本 (由頭到尾依序)

* 改良版的運作如下圖，透過三個指標 `prev`、`head` 和 `next` 來完成交換。
* 迴圈前為圖 1, 2，先記錄一開始的 head 為 `newt`，需要考慮最後完成的 tail 要接 NULL
* 迴圈操作為圖 3, 4
1. 記錄 head 下一個節點為 next
2. 將 head 連接至 prev，完成反轉
3. 將 prev 移至 head
4. 將 head 移至 next，繼續下一輪
* 完成情況如下
1. head 移到原 tail 的下一個 (NULL)，跳出迴圈
2. 因為是透過 head 來遍尋 queue，所以將 head 移至 prev (原 tail)
3. 將 tail 移至一開始記錄的 newt，完成整個 queue 的反轉

void q_reverse(queue_t *q)
{
    if (q == NULL)
        return;
    /*
    start from head to tail
    link current(head) and prev then jump to next
    */
    list_ele_t *newt = q->head;
    list_ele_t *prev = NULL;
    while (q->head != NULL) {
        list_ele_t *next = q->head->next;
        q->head->next = prev;
        prev = q->head;
        q->head = next;
    }
    q->head = prev;  // prevent NULL
    q->tail = newt;  // origin head
}

* 原始版的運作如下圖，透過兩個指標 `tmp` 和 `tail` 來完成交換，缺點是每次都需要從頭找到 tail 前一個
* 首先記錄一開始的 tail 為 `newh`
* 迴圈操作為圖 2, 3, 4
1. tmp 從 head 開始遍尋
2. 直到下一個節點為 tail 時停下來
3. 將 tail 連接至 tmp，完成反轉
4. tail 移至 tmp，作為下一次的中斷點
* 完成情況如下
1. tail 與 head 重合時，跳出迴圈
2. 將目前 head (新 tail) 連接至 NULL
3. 將 head 移至一開始記錄的 newh，完成整個 queue 的反轉

    /* start from tail to head */
    list_ele_t *newh = q->tail;
    while (q->tail != q->head) {
        list_ele_t *tmp = q->head;
        while (tmp->next != q->tail)
            tmp = tmp->next;
        q->tail->next = tmp;    // reverse the link of tail
        q->tail = tmp;
    }
    q->head->next = NULL;
    q->head = newh; // origin tail

## 自動評分系統
### makefile
* 執行 `make test` 會等同執行 makefile 裡以下指令
* 第一列是代表相依的檔案，第二列為執行的命令

test: qtest scripts/driver.py
    scripts/driver.py

### scripts/driver.py
* 執行 `driver.py` 後，首先會檢查有沒有後續的引數

if __name__ == "__main__":
    run(sys.argv[0], sys.argv[1:])

* 提供了幾種引數，`-p` 可以決定待測試的程式，`-t` 挑選測資題目，`-v` 決定細節顯示 (0~3 越高越細)，或是 `--valgrind` 以 valgrind 開啟程式
> 有個隱藏引數是 `-A`，開啟 autograde (以 JSON 字串印出)，但因為過程中就會自動計算分數，所以預設不會用到

print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]" % name)
print("  -h        Print this message")
print("  -p PROG   Program to test")
print("  -t TID    Trace ID to test")
print("  -v VLEVEL Set verbosity level (0-3)")

### scripts/driver.py/run()
* 執行 `run` 後，主要處理上述引數
* 預設情況下會執行以下片段建立 class 並執行 function `run`

t = Tracer(qtest = "", verbLevel = 1, autograde = False, useValgrind = False)
t.run(0)

### scripts/driver.py/Tracer.run()
* 根據是否有執行 valgrind，腳本的指令也會相對不同
* 上半部對應到的是 `valgrind ./qtest`
* 下半部對應到的是 `./qtest`
> 事實上下半部的 command 可以不用再次賦值，預設就是 `./qtest`，不過這樣可以增加可讀性

if self.useValgrind:
    self.command = 'valgrind'
else:
    self.command = self.qtest
    self.qtest = ''

* 在預設 `tid` 未指定測資的情況下，會依序跑完所有測資

for t in tidList:
    tname = self.traceDict[t]
    if self.verbLevel > 0:
        print("+++ TESTING trace %s:" % tname)
    ok = self.runTrace(t)

* 分數是透過每個測資的滿分加總決定，無論是錯在該題的哪個地方，該題都是以 0 分計算，所以會需要 `verbLevel` 幫助了解

    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

### scripts/driver.py/Tracer.runTrace()
* 依序將前面所得的對應指令結合，便完成對應的腳本，再透過 python 的 `subprocess.call` 來呼叫 qtest
> 這邊事實上也可以將 `fname` 的部份全部預設寫在 dict 裡面，拆開來只是為了精簡過程中顯示的文字

fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, self.qtest, "-v", vname, "-f", fname]
try:
    retcode = subprocess.call(clist)

## qtest 行為與技巧
### C 與 Python 擷取引數的差別
* 在 `qtest.c` 裡，使用的是 [getopt()](http://man7.org/linux/man-pages/man3/getopt.3.html)
* 字串中的` h` `v:` `f:` `l:` 即是代表要處理的引數
* 輸入指令時必須是以 `-h`、`-v` 這樣的形式才會擷取
* `:`表示後面需要有對應的資訊，如 `-f test.txt`，該資訊會存在 `optarg` 這個固定的變數
* 成功擷取會回傳對應的字元，失敗則根據情況會回傳 `-1`、`?` 和 `：`

int c;
while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
    switch (c) {
    case 'h':
        usage(argv[0]);
        break;
    case 'f':
        strncpy(buf, optarg, BUFSIZE);
        buf[BUFSIZE - 1] = '\0';
        infile_name = buf;
        break;
    case 'v':
        level = atoi(optarg);
        break;
    case 'l':
        strncpy(lbuf, optarg, BUFSIZE);
        buf[BUFSIZE - 1] = '\0';
        logfile_name = lbuf;
        break;
    default:
        printf("Unknown option '%c'\n", c);
        usage(argv[0]);
        break;
    }
}

* 在 `driver.py` 裡，使用的是 [getopt.getopt()](https://docs.python.org/3.6/library/getopt.html) C-style parser，而 python 也有提供比較強大的模組是 [argparse](https://docs.python.org/3.6/library/argparse.html#module-argparse)
* 這邊的長引數 `valgrind` 是透過 list 來儲存，在 C 則需要呼叫 `getopt_long()`，以特別的 struct 來儲存
* 回傳值 `optlist` 和 `args` 可以更改變數名稱，前者以 list 儲存所有擷取到的引數，後者是儲存擷取後剩餘的引數
* 回傳的 list 每個元素都是以 `(option, value)` 形式儲存，`value` 只有在指定 `:` 時才會一併把資訊放入

optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
for (opt, val) in optlist:
    if opt == '-h':
        usage(name)
    elif opt == '-p':
        prog = val
    elif opt == '-t':
        tid = int(val)
    elif opt == '-v':
        vlevel = int(val)
        levelFixed = True
    elif opt == '-A':
        autograde = True
    elif opt == '--valgrind':
        useValgrind = True
    else:
        print("Unrecognized option '%s'" % opt)
        usage(name)

### 測試過程
#### qtest.c
* qtest 也提供了幾種可用的引數，`-f` 和 `-v` 對應到上述自動評分提及的腳本與細節顯示，`-l` 則是指定紀錄檔存放的位置

printf("Usage: %s [-h] [-f IFILE][-v VLEVEL][-l LFILE]\n", cmd);
printf("\t-h         Print this information\n");
printf("\t-f IFILE   Read commands from IFILE\n");
printf("\t-v VLEVEL  Set verbosity level\n");
printf("\t-l LFILE   Echo results to LFILE\n");

* 執行 qtest 後會先根據需要的 [signal](http://man7.org/linux/man-pages/man7/signal.7.html) 註冊 signal handler
* 這邊只有考慮兩種事件，`SIGSEGV` 處理記憶體錯誤，`SIGALRM` 則處理定時器

static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

* handler 裡面會直接呼叫 `harness.c` 的 `trigger_exception()`，注意 handler 會有固定一個參數儲存信號

void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}

* 在每個與 `queue.c` 對應的函式裡，扣除引數的檢查後，都會先檢查 q 是否為 NULL
* 接著執行 `harness.c` 的 `error_check()`，因為尚未測試 queue，這邊忽略回傳值，目的只是重設 `error_occurred`

if (q == NULL)
    report(3, "Warning: Calling insert tail on null queue");
error_check();

bool error_check()
{
    bool e = error_occurred;
    error_occurred = false;
    return e;
}

* 以 `do_new()` 為例，完成上述步驟後會先設置一個存檔點，`true` 表示允許開啟定時器，~~畢竟闖關就是要存檔~~，完成後就會解除定時器

if (exception_setup(true))
    q = q_new();
exception_cancel();

* 部份測試會開啟額外的模式，如做完 `do_free()` 會開啟 `harness.c` 的 `cautious_mode`，確保任何要 free 的區塊目前都 allocated，但似乎不會用到 (?)
> 影響到 `find_header()`，只有 `test_free()` 用到，但沒有呼叫到 `test_free()` 的機會

set_cautious_mode(true);

* `do_reverse()` 也會開關 `noallocate_mode`，開啟的情況下會禁止 `test_malloc()` 和 `test_free()`
> 一樣沒有呼叫到兩個函式的機會

set_noallocate_mode(true);
if (exception_setup(true))
    q_reverse(q);
exception_cancel();
set_noallocate_mode(false);

#### harness.c
* 以下變數是為了處理例外發生，可以搭配參考 [setjmp.h](https://zh.wikipedia.org/wiki/Setjmp.h)
* `env` 會儲存當下的 stack 資訊，宣告雖然可以用 `jmp_buf`，但可以改成 `sigjmp_buf` 比較有一致性
* `volatile` 表示該變數能夠在 set 和 jump 之間存取，且**不會套用編譯器的最佳化**，避免影響變數的更新
* `sig_atomic_t` 表示變數的更動需要在一個指令內完成，所以兩個關鍵字常一併出現
* `time_limited` 表示是否有開啟定時器
* `time_limit` 表示定時器的間隔，預設一秒

static jmp_buf env;
static volatile sig_atomic_t jmp_ready = false;
static bool time_limited = false;
static int time_limit = 1;

* 當 handler 捕捉到對應信號時，記錄要顯示的錯誤資訊，並使用 [siglongjmp()](https://linux.die.net/man/3/siglongjmp) 跳回上一個存檔點

void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

* 這邊存檔點的設置使用的是 [sigsetjump()](https://linux.die.net/man/3/sigsetjmp)，算是 setjump() 的改良版，差別在可以處理信號內容
* 比較複雜的 context switch 可以參考 [setcontext()](https://linux.die.net/man/2/setcontext)
* `savesigs` 的位置傳入 1，根據 [signal](http://man7.org/linux/man-pages/man7/signal.7.html)，表示能夠處理 SIGHUP 程序中斷的情況
* 建立存檔點時，固定呼叫 `exception_setup(true)`
1. 先經由 if 建立存檔點，`sigsetjmp()` 成功會是回傳 0，跳到 else
2. 允許 jump 並開啟定時器
3. 因定時器間隔一秒，正常是還不會觸發 `SIGALRM` 就回傳 `true`
* 假設在執行 queue.c 的函式時發生 `SIGSEGV`
1. 捕捉到信號會立即執行 `trigger_exception()`，記錄對應的訊息
2. 接著 `siglongjmp()` 會回到上一個存檔點 `sigsetjmp()`
3. jump 回來會使得回傳值非 0，進入 if
4. 禁止 jump 並關閉定時器
5. 印出對應的錯誤訊息並跳出
6. 因為 false 使得原本 `qtest.c` 測試的 if 區塊不再執行

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;
    }
}

* 無論執行過程中是否有 `SIGSEGV`，最終都會呼叫 `exception_cancel()`，差別在發生例外的情況下會多做一次而已

void exception_cancel()
{
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    jmp_ready = false;
    error_message = "";
}

#### qtest.c
* 執行完測試的指令後，仍會再次執行 `harness.c` 的 `error_check()`
* 如果正常執行，那麼仍會維持執行前的 `error_occurred = false`
* 反之只要有發生 `trigger_exception()`，就會維持 `error_occurred = true`，使得最終回傳值為 false，表示失敗

return ok && !error_check();

bool error_check()
{
    bool e = error_occurred;
    error_occurred = false;
    return e;
}