# 2019q1 Homework1 (lab0)
contributed by <``jeffcarl67``>

## 要求
* 實做 queue
* first in, first out
* first in, last out
* 完成以下函式
* 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
* q insert tail: Attempt to insert a new element at the tail of the queue
* q remove head: Attempt to remove the element at the head of the queue
* q size: Compute the number of elements in the queue
* q reverse: Reorder the list so that the queue elements are reversed in order
* 解釋自動評分系統運作的原理
* 提及 qtest 的行為和裡頭的技巧

## 環境

Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP 

## 實做

### q_new
分配一個 queue，要注意 ``malloc`` 失敗後的錯誤處理以及 ``queue_t`` 結構的初始化

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### q_free
釋放 queue 使用的所有記憶體，此處的作法是每次都刪除第一個元素，直到 linked list 中沒有元素為止

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *cur = NULL;
    if (!q)
        return;
    while (q->head) {
        cur = q->head;
        q->head = q->head->next;
        if (cur->value)
            free(cur->value);
        free(cur);
    }
    free(q);
}

### q_insert_head
在 queue 的開頭插入一個元素，要比較注意的地方是在用於儲存字串的指針 ``newh->value`` 取得記憶體失敗後，在錯誤處理時除了 ``return false`` 外還要將先前取得的記憶體一併釋放，才不會有記憶體洩漏的問題

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh = NULL;
    /* What should you do if the q is NULL? */
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;
    memcpy(newh->value, s, strlen(s) + 1);
    q->size++;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    if (!q->tail)
        q->tail = newh;
    return true;
}

### q_insert_tail
在 queue 的尾端插入一個元素

/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
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 */
    list_ele_t *newh = NULL;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    memcpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    if (!q->head)
        q->head = newh;
    if (!q->tail)
        q->tail = newh;
    else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

### q_remove_head
從 queue 前端移除一個元素，並在參數 ``char *sp`` 不為 ``NULL`` 的情況下將被刪除元素的字串複製最多 ``bufsize-1`` 長度到 ``char *sp`` 中

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  If sp is non-NULL and an element is removed, copy the removed string to *sp
  (up to a maximum of bufsize-1 characters, plus a null terminator.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *cur;
    size_t len;
    if (!q)
        return false;
    if (!q->head)
        return false;
    cur = q->head;
    len = strlen(cur->value) < bufsize - 1 ? strlen(cur->value) : bufsize - 1;
    if (sp) {
        memcpy(sp, cur->value, len);
        sp[len] = '\0';
    }
    q->head = q->head->next;
    free(cur->value);
    free(cur);
    q->size--;
    return true;
}

### q_size
用於取得 queue 中元素總數

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
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 || !q->head)
        return 0;
    return q->size;
}

### q_reverse
在不使用額外分配記憶體的情況下翻轉 queue 中元素的順序，此處使用了三個指針``prev`` ``curr`` ``next`` ，在循環中 ``curr`` 從 queue 中第一個元素開始走訪到最後一個元素，每次 ``prev``指向 ``curr`` 前一個元素而 ``next`` 指向後一個元素，透過更改這三個元素間的連接達成逆序的目的。在迴圈結束時 ``curr`` 指向 ``NULL`` 而 ``prev`` 指向最後一個元素

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *prev, *curr, *next;

    if (!q)
        return;
    if (!q->head)
        return;

    prev = NULL;
    curr = q->head;
    q->tail = q->head;
    next = NULL;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    q->head = prev;
}

## 自動評分系統

### driver
在輸入 ``make test`` 進行測試時，Makefile 並沒有直接執行 ``qtest``, 觀察 Makefile 中的規則可以發現, Makefile 以 ``scripts/driver.py`` 調用 ``qtest`` 進行測試

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

再看到 ``scipts/driver.py`` 中的內容, 其中最主要的程式碼都在 ``class Tracer`` 中, 這個 class 負責按照變數 ``traceDirectory`` 與 ``traceDict`` 中紀錄的測試檔案逐一調用 ``qtest`` 進行測試，可以發現變數 ``traceDirectory``紀錄了測試檔案所在資料夾而 ``traceDict`` 中紀錄了測試檔的檔名

class Tracer:
    
    traceDirectory = "./traces"
    qtest = "./qtest"
    command = qtest
    verbLevel = 0
    autograde = False
    useValgrind = False

    traceDict = {
        1 : "trace-01-ops",
        2 : "trace-02-ops",
        3 : "trace-03-ops",
        4 : "trace-04-ops",
        5 : "trace-05-ops",
        6 : "trace-06-string",
        7 : "trace-07-robust",
        8 : "trace-08-robust",
        9 : "trace-09-robust",
        10 : "trace-10-malloc",
        11 : "trace-11-malloc",
        12 : "trace-12-malloc",
        13 : "trace-13-perf",
        14 : "trace-14-perf",
        15 : "trace-15-perf"
        }

......

在 ``class Tracer`` 的函式 ``run`` 中, 調用 ``runTrace`` 執行單項測試後依據 ``qtest`` 的返回值判斷是否通過測試並統計得分

        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
        print("---\tTOTAL\t\t%d/%d" % (score, maxscore))

觀察調用 ``qtest`` 的函式 ``runTrace`` 後可知, 當執行 ``make test`` 時, 對於 ``qtest`` 的調用為命令 ``./qtest -v 1 -f ./traces/trace-XX-XXXX``, 其中 ``trace-XX-XXXX``為對應的測試檔名, 此命令的意思為設定 ``verblevel`` 為 1 並將 ``trace-XX-XXXX`` 作為輸入檔案

    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.command, 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

### qtest

* getopt
在 ``main`` 的開頭會先初始化一些區域變數, 緊接著就直接調用 ``getopt`` 函式對命令行參數進行處理, 從程式碼中可知 ``qtest`` 接受 4 種選項, 分別為 ``-h`` ``-f`` ``-v`` ``-l``, 功能如下：
* h : 印出幫助消息
* f : 後接一個參數, 指名要輸入的檔案
* v : 後接一個數字參數, 指名 verblevel
* l : 後接一個參數, 指名要輸出的檔案

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

資料參考自:
> http://man7.org/linux/man-pages/man3/getopt.3.html
* queue_init
設定 signal handler 用於處理 ``SIGSEGV`` 及 ``SIGALRM`` 兩種信號, ``SIGSEGV`` 為發生 segment fault 後產生的信號, ``SIGALRM`` 為設定的定時器到時觸發的信號

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

``qtest`` 中用於處理 signal 函式都在 ``harness.c`` 中,

為了學習 ``qtest`` 中對於 ``SIGSEGV``, 寫了一個簡單的小程式嘗試使用 ``SIGSEGV`` 的 signal handler, 程式碼如下：

#include <stdio.h>
#include <signal.h>

void sigsegvhandler(int sig)
{
  printf("sig:%d \n",sig);
}

int main()
{
  int *p = NULL;
  signal(SIGSEGV, sigsegvhandler);
  *p = 100;
  return 0;
}

然而執行後卻發現 signal handler 被不停調用, 而非如預想中只執行一次, 經過資料搜尋與驗證後得知當 signal handler 返回後回到引發 ``SIGSEGV`` 的代碼繼續執行, 因此 ``SIGSEGV`` 一直被相同的程式碼觸發, 然而如此無法達到處理 ``SIGSEGV`` 的目的, 必須找出辦法在 signal handler 結束後不再執行惠引發錯誤的程式碼, 一種方法就是 ``qtest`` 中使用的 ``sigsetjmp`` 與 ``siglongjmp`` 函數, ``sigsetjmp`` 能夠存儲執行環境而 ``siglongjmp`` 能跳轉回預先除存的執行環境, 且 ``sigsetjmp`` 在直接調用時會返回 0, 在 ``siglongjmp`` 跳轉時會返回非 0 值, 在 ``qtest`` 中就利用了這個方式：

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

資料參考自：
> https://blog.csdn.net/work_msh/article/details/8470277
> http://man7.org/linux/man-pages/man2/signal.2.html

* init_cmd
在 ``init_cmd`` 中會調用 ``add_cmd`` 與 `add_param`` 函式將一些命令存入一個 linked list 中, 並設定輸入檔案與時間
* console_init
在 ``console_init`` 中會將剩下的所有命令都加入 linked list 中, 至此所有在 ``qtest`` 中可用的命令都已經加入了 linked list 中
* run_console
``run_console`` 是 ``qtest`` 程式用於處理輸入並且選擇指令執行的程式, 其中最主要執行命令的函式為 ``interpret_cmda``, 其他相關函式大部分只用於分離命令與參數
* finish_cmd
這個函式負責 ``qtest`` 最後的收尾工作, 其效果與直接輸入 ``quit`` 是一樣的, 而從 ``main``函式的最後幾行可以發現, 只要在 ``run_console`` 與 ``finish_cmd`` 中發生一次諸如命令錯誤或記憶體洩漏, ``qtest`` 在最後都會返回非 0 值, 代表程式執行中發生錯誤, ``scripts/driver.py`` 就是利用這一點進行分數計算

    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;

### qtest 進行記憶體檢測的方式
在 ``harness.h`` 有這一段 macro:

#else
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
#endif

因此在 queue.c 中所有的 ``malloc`` ``free`` ``strdup`` 都被替換為 ``qtest`` 自己實現的函數, 在分配記憶體時 ``qtest`` 會將所有的記憶體放入一個 linked list 中, 並利用 ``MAGICHEADER`` ``MAGICFREE`` ``MAGICFOOTER`` ``FILLCHAR`` 紀錄該塊記憶體的狀況，若是已分配的就用 ``MAGICHEADER`` 反之用 ``MAGICFREE``, 並在既已體的末端填入 ``MAGICFOOTER`` 且在記憶體剛分配時將payload全部初始化為 ``FILLCHAR``

/* 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

在檢查是否存在記憶體洩漏或破壞時只須檢測 linked list 中記憶體塊的分配情況與 magic number 是否被改寫就能進行判斷, 例如在函式 ``test_free`` 中的這一段程式碼:

    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;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);