# 2018q3 Homework2 (lab0)

contributed by < [`jason53415`](https://github.com/jason53415/lab0-c) >

>commit 應切分為更小的 commit，每個 commit 都應該專注在小部份的修改
>[name=課程助教][color=red]

## 測試環境

$ uname -a
Linux scream-47860 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

## 實做內容

### queue.h
* 為了要達成可以 $O(1)$ 時間取得 queue 的大小以及從尾端插入元素，需要在 queue.h 中的 `queue_t` 增加 `list_ele_t *tail` 指向 queue 的末端，以及 `int size` 記錄 queue 的大小。

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

### queue.c
* q_new
* 使用 `malloc()` 配置記憶體，並且初始所有的變數。
* 需要注意在 `malloc()` 失敗時要回傳 `NULL` 。

* q_free
* 因為每個 queue 的節點中都有一個指向字串的指標，所以在處理時必須先釋放掉字串的記憶體，再釋放節點的記憶體。
* 確認所有節點都被釋放掉後，最後則是將 queue 本身佔用的記憶體釋放掉。

* q_insert_head
* 配置節點的記憶體，並且依照傳入字串的大小配置字串的記憶體，最後使用 `strcpy()` 將字串內容複製過去。
* 如果 queue 本來就還沒建立，或者配置記憶體沒有成功，則回傳 `false` 。
* 建立完節點之後，要讓這個節點的 `next` 先指向原本的 `head` ，再將 queue 的 `head` 指向這個節點。
* 加入新的節點後，將 queue 的 `size` 增加 1 ，並且回傳 `true` 。
* 需要特別注意在配置記憶體失敗時要回傳 `NULL` ，尤其是配置字串的記憶體失敗時，還要記得把先前配置給節點的記憶體也釋放掉。
* 時間複雜度： $O(1)$

* q_insert_tail
* 因為我們有新增一個指標 `tail` 指向 queue 的末端，大致內容與 `q_insert_head()` 一樣，只是建立完節點之後要先讓原本的 `tail->next` 指向新增的節點，再讓 queue 的 `tail` 指向新節點。
* 時間複雜度： $O(1)$

* q_remove_head
* 先確認 queue 是否有建立以及 queue 是否是空的，如果是空的直接回傳 `false` 。
* 先使用 `memset()` 將 `sp` 的內容全部初始為 `\0 ` 後，在將 `head` 所指到的節點的字串使用 `strncpy()` 複製到 `sp` ，以避免超過 `bufsize` 。
* 最後先用一個指標存下目前 `head` 的位址，然後將 `head` 指向下一個節點後，把指標所指的節點的字串以及本身的記憶體釋放掉。
* 刪除節點後，將 queue 的 `size` 減少 1 ，並且回傳 `true` 。
* 時間複雜度： $O(1)$

* q_size
* 因為在 queue 中插入或刪除資料時都會更新 `size` 的大小，所以除非 queue 本身沒有建立時要直接回傳 0 之外，都可以直接回傳 queue 中記錄的 `size` 。
* 時間複雜度： $O(1)$

* q_reverse
* 如果 queue 還沒建立，或者 queue 的 `size` 小於等於 1 時，就直接 return 。
* 為了要實現在不新增節點的情況下將 queue 顛倒過來，利用了三個指標 `last` 、 `curr` 、 `next` 指向三個連續的節點，來將 `curr` 中所指的下一個節點從 `next` 改為 `last` ，並且不斷將全部的指標移往下一個節點。
* 最後要交換 `head` 及 `tail` ，讓指標正確指向 queue 的頭尾端。
* 時間複雜度： $O(n)$

## 評分結果

$ make test
scripts/driver.py
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---     trace-05-ops    6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---     trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---     trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---     trace-15-perf   7/7
---     TOTAL           100/100

## 自動評分系統運作原理

從 Makefile 中可以得知，執行 `$ make test` 時實際上就是執行 scripts/driver.py 這個程式。

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

透過執行 `$ scripts/driver.py -h` 可以看到有許多參數可以調整。

$ scripts/driver.py -h
Usage: scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL]
  -h        Print this message
  -p PROG   Program to test
  -t TID    Trace ID to test
  -v VLEVEL Set verbosity level (0-3)

其中 TID 表示要使用哪一筆測試資料，預設的 TID 為 0 ，用來表示要使用所有的測試資料； verbosity level 則表示執行時所印出的訊息的多寡程度，以下利用了第一筆測試資料來實驗不同 verbosity level 的差異：

$ scripts/driver.py -t 1 -v 0
---     Trace           Points
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 1
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 2
---     Trace           Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
cmd>ih gerbil
cmd>ih bear
cmd>ih dolphin
cmd>rh dolphin
Removed dolphin from queue
cmd>rh bear
Removed bear from queue
cmd>rh gerbil
Removed gerbil from queue
cmd>
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 3
---     Trace           Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
q = []
cmd>ih gerbil
q = [gerbil]
cmd>ih bear
q = [bear gerbil]
cmd>ih dolphin
q = [dolphin bear gerbil]
cmd>rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd>rh bear
Removed bear from queue
q = [gerbil]
cmd>rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
---     trace-01-ops    6/6
---     TOTAL           6/6

可以看出當 verbosity level 為 0 時只會印出分數，為 1 的時候會印出測試的項目，為 2 會印出執行的每一個指令，為 3 時則會將執行完每一個指令後的 queue 的內容一起印出。

處理完輸入的參數後， scripts/driver.py 接下來就會依此去執行 qtest ，讓 qtest 從 trace 資料夾中讀取相對應的 .cmd 檔來測試。

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

第 9 行的 [`subprocess.call()`](https://docs.python.org/2/library/subprocess.html#using-the-subprocess-module) 是 python 中增加子行程的函式，可以直接執行外部程式並且加上執行時需要的命令列參數，直到外部程式結束後回傳 return code 。

觀察以上整段 `runTrace()` 後可以發現只有當 qtest 回傳的 `retcode` 等於 `0` 的時候，整個函式才有可能回傳 `True`，並且存在下面 `run()` 函式第 7 行的 `ok` 中。

def run(self, tid = 0):
    ...
    score = 0
    ...
    for t in tidList:
        ...
        ok = self.runTrace(t)
        maxval = self.maxScores[t]
        tval = maxval if ok else 0
        ...
        score += tval
        ...

又因為只有當 `ok` 為 `True` 時才能得到整題的分數 `maxval` ，我們可以推論是否能得到分數完全取決於 qtest 最後的回傳值是否等於 `0` 。

## qtest 的行為與技巧

在 harness.h 中有以下的程式碼，將原本 C 語言定義的函式 `malloc()` 與 `free()` 重新定義到 `test_malloc()` 與 `test_malloc()` 。

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_malloc

其中 `test_malloc()` 會呼叫 `fail_allocation()` 這個函式，並依據當前的 malloc 失敗機率 `fail_probability` 決定這次配置記憶體是否成功。

/* Should this allocation fail? */
static bool fail_allocation()
{
    double weight = (double) random() / RAND_MAX;
    return (weight < 0.01 * fail_probability);
}

在 harness.c 中可以發現，實際上所有透過 `test_malloc()` 配置的記憶體會使用以下的資料結構存成一個 doubly-linked list。

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;

這裡的 `payload[0]` 是一個長度為零的陣列，放在 struct 的最後面，可以用來標示其後所接的記憶體的起始位置。

void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    ...
    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);
    ...
    return p;
}

上面第四行的程式碼顯示，我們實際上配置的記憶體大小是由 `block_ele_t` 加上我們原本要配置的記憶體大小 `size` ，以及一個 footer 所組成。

因此我們以為用 `malloc()` 配置到的一整塊記憶體實際上是跟在一個 `block_ele_t` 的 struct 後面，並且最後還跟著一個 footer，而且從第十行程式碼可以看到 `test_malloc()` 回傳的指標 `p` 就是指向 payload 所在的位址。

void test_free(void *p)
{
    ...
    block_ele_t *b = find_header(p);
    ...
    /* 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_malloc()` 相對應的，使用 `test_free()` 時則會先呼叫 `find_header()` ，並且如以下的程式碼所示，減掉 `block_ele_t` 的大小來往前找到當初宣告記憶體的起始位址，之後會再對 doubly-linked list 的指標進行操作後，把整塊配置的記憶體釋放掉。

static block_ele_t *find_header(void *p)
{
    ...
    block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));
    ...
    return b;
}