# 2019q3 Homework2 (lab0)
contribyted by < `nckuoverload` >
###### tags: `sysprog2019`

## 作業要求

* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
* ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== (英文閱讀正是我們想強化的議題，你應該在共筆上摘要題目要求)，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改。
* 在提交程式前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 不用理會 [Autolab](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/BkZ4h5xPB)」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
- [x] 解釋自動評分系統運作的原理
- [x] 提及 `qtest` 的行為和裡頭的技巧，特別是 signal handler
- [ ] 解析 Valgrind 的運作原理和針對本程式的使用
- [ ] 根據 [dudect](https://github.com/oreparaz/dudect) 工具以及提出的對應論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，探討一種以實驗而非理論驗證時間複雜度的方法
- [ ] 留意 `MAGICHEADER`, `MAGICFREE`, `MAGICFOOTER`, `FILLCHAR` 等巨集的使用，並探討其動機和用法
* 截止日期：
* Oct 2, 2019 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高

## 實驗環境
Operating System: `Ubuntu 16.04 64bit`
Compiler: `gcc 8.3.0`

## 測試結果

$ python ./scripts/driver.py -A
---     Trace           Points
---     trace-01-ops    6/6
---     trace-02-ops    6/6
---     trace-03-ops    6/6
---     trace-04-ops    6/6
---     trace-05-ops    6/6
---     trace-06-string 7/7
please new a queue first
---     trace-07-robust 7/7
---     trace-08-robust 7/7
---     trace-09-robust 7/7
---     trace-10-malloc 7/7
---     trace-11-malloc 7/7
---     trace-12-malloc 7/7
---     trace-13-perf   7/7
---     trace-14-perf   7/7
---     trace-15-perf   7/7
---     TOTAL           100/100

## 實作紀錄
### queue_t
在`queue.h`中，修改`queue_t`結構。
新增`list_ele_t *tail;`用來指向尾巴。
新增`int size;`用來記錄目前的長度。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

### q_new()
首先是建立一個queue ，過程沒太大問題，要注意`malloc` 有可能會返回`NULL` ，所以在第29行要針對這個情況特別處理。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        free(q);
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### q_free()
釋放佇列，主要使用一個loop 去對每一個節點做處理。

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

### q_insert_head(queue_t *q, char *s)
和`_insert_tail()` 可以搭配一起來看，主要在第一個`if` 判斷該佇列是否為空，第二、三個判斷`malloc` 是否返回`NULL` (在測資中，會針對這個部分做測試)。
從頭插入的部分主要是新增一個節點，並將該節點指向原本的head ，並將佇列的head 指向該節點，並且size 增加。

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        free(newh);
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newh->value == NULL) {
        free(newh->value);
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->tail = newh;
    }
    q->head = newh;
    q->size += 1;
    return true;
}

### q_insert_tail(queue_t *q, char *s)
和`q_insert_head()` 相似，前三個判斷式相同效果，但應該有更好的寫法。
從尾端插入的部分，主要是將原本的尾端指向即將插入的節點，並將佇列中的`tail` 改成指向即將插入的節點。

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 == NULL) {
        return false;
    }
    list_ele_t *newQ;
    newQ = malloc(sizeof(list_ele_t));
    if (newQ == NULL) {
        free(newQ);
        return false;
    }
    newQ->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newQ->value == NULL) {
        free(newQ->value);
        free(newQ);
        return false;
    }
    strcpy(newQ->value, s);
    q->tail->next = newQ;
    q->tail = newQ;
    newQ->next = NULL;
    q->size += 1;
    return true;
}

### q_remove_head(queue_t *q, char *sp, size_t bufsize)
主要要注意測試中，有兩種測試方式，一個為`rh [str]` 和`rhq` ，前者主要會和輸入的字串做判斷，在這個部分要特別注意**輸入字串的大小是否大於佇列中第一個節點的大小**，在第147行針對這個部分做處理，如果超過不處理的話會造成溢出(overflow)。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0) {
        return false;
    }
    if (bufsize != 0) {
        memset(sp, '\0', bufsize);
        if (strlen(q->head->value) > bufsize) {
            strncpy(sp, q->head->value, bufsize - 1);
        } else {
            strcpy(sp, q->head->value);
        }
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

### q_size(queue_t *q)
使用額外的`int size` 來儲存佇列大小，為了符合題目的$O(1)$。

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 == NULL) {
        return 0;
    }
    return q->size;
}

### q_reverse(queue_t *q)
總共寫了兩個版本，原先使用類似bubble sort 的演算法來做倒轉，簡單來說就是模擬bubble sort 最壞情況，每一個迴圈讓一個節點移到適當的位置，並讓其他節點往前移一個位置，複雜度為$O(n^2)$。但這樣做的話在test 會一直因為時間超過而無法通過。
第二個版本主要是多用了三個暫存變數，每一次將一個節點的指標轉向，並在最後處理`q`的`head` 和`tail`。也是很直觀的做法，但一開始因為題目敘述理解錯誤，誤解為不能多使用額外空間設置變數來處理。

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->size < 2) {
        return;
    }
    list_ele_t *temp;
    list_ele_t *now = q->head->next;
    list_ele_t *pre = q->head;

    while (now != NULL) {
        temp = now->next;
        now->next = pre;
        pre = now;
        now = temp;
    }
    q->tail = q->head;
    q->head = pre;
    q->tail->next = NULL;
}

## 討論
### 解釋自動評分系統運作的原理
主要使用Makefile 來自動評分，Makefile 寫起來類似shell script 但又不盡相同，詳細可以參考[這篇範例](https://mropengate.blogspot.com/2018/01/makefile.html)，或是網路上應該有許多其他解說。
在原始的Makefile 中，主要是編譯後，呼叫`scripts/driver.py` 來評分，所以也可以在`~/lab0-c` 中直接使用`python driver.py` 來評分。
`driver.py` 又可以使用四個參數來使用。
`h` : 主要用來說明有哪些參數，類似一般使用的help 。
`p` : 可以選擇用哪個檔案來評分。 (不太確定式不是這個意思)
`t` : 可以選擇要選第幾個腳本來測試，腳本都在`~/lab0-c/traces` 底下。
`v` : 有0~3的級別，可以選擇要顯示多少測試的腳本資料。
`A` : 自動評分，功能等同於使用 `make test` 。
`--valgrind` : 如果直接搜尋會找到 [Wikipedia](https://en.wikipedia.org/wiki/Valgrind) 的解說，是一款GNU 的工具，用來處理記憶體除錯。稍後會再針對這部分解釋。

### 提及 `qtest` 的行為和裡頭的技巧，特別是 signal handler
在 `qtest.c` 中，會有許多 method 用來做測試，每一個都會使用 `exception_setup() exception_cancel()` 兩個來對 exception 做處理，同時裡面也有使用到 signal 的機制。
首先會先執行 `queue_init()` 並且呼叫兩個 signal ，`SIGSEGV` 用來處理記憶體部分的例外狀況；`SIGALRM` 用來處理執行時間的例外狀況。
之後以 `do_new()` 為例，在第107行的部分，當要執行 `q_new()` 前，會先執行 `exception_setup(true)` ，用來開啟 signal ，並且在執行完成後使用 `exception_cancel()` 關閉。
`exception_setup()` 和 `exception_cancel()` 都在 `harness.c` 中。以下將分別敘述。

- exception_setup():
這邊可以分成兩個流程來說明，分別是正常運作和 `exception` 發生時的狀況。
- 正常運作: 在正常運作下，會從 `do_new()` 等執行 `exception_setup()` 跳入，因為是正常情況，所以 `sigsetjmp()` 並不會被執行，會直接跳到253 行執行，`jmp_ready` 參數主要是用來紀錄在 exception 發生後，是否可以執行 jump 。並且這時候會在257 行給予一個執行時間，程式必須在時間內完成，否則會觸發 signal 並且丟出 `sigalrmhandler` 讓 `qtest.c` 中的 `sigalrmhandler()` 去處理例外。並且會將狀態恢復到未執行 `q_new()` 前的狀態繼續往下執行。
- 例外狀況: 如果有發生例外狀況，因為一開始有先使用 `sigsetjmp` 來保存 stack 環境等，所以會把剩下的時間返回，並且將錯誤訊息印出，之後在兩個 handler 中都有使用到 `trigger_exception()` 去處理，`trigger_exception()` 會使用 `siglongjmp` 將環境恢復到原本儲存的狀態(尚未進入會發生例外狀況的 method 前的狀態)。

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

- exception_cancel():
當 method 順利執行完後，把 signal 關閉。

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

小結， `qtest.c` 因為不能確保每次執行實作者在 `queue.c` 中實作的 method 都是可靠的，所以每次要進入 `queue.c` 的方法前，都會先使用 `sigsetjmp` 保存狀態，並且開啟 signal ，如果例外狀況沒發生，則會使用 `exception_cancel()` 去關閉所有上述機制。如果例外狀況發生，則會使用 `trigger_exception()` 中的 `siglongjmp()` 來恢復到進入有問題方法前的環境。

- 實驗
很簡單的實驗，可以把限制時間長度的 signal 關閉，並且把 `q_reverse` 的部分改回第一版本氣泡排序法去執行，可以發現並不會有時間錯誤的問題出現，在第13個測試 `trace-13-perf.cmd` 正常情況下會發生錯誤。
- `q_reverse()` using bubble sorting

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL) {
        return;
    }
    int temp = q->size;
    list_ele_t *t;
    for (int i = 0; i < q->size; i++) {
        temp--;
        t = q->head;
        for (int z = 0; z < temp; z++) {
            *(t->value) ^= *(t->next->value);
            *(t->next->value) ^= *(t->value);
            *(t->value) ^= *(t->next->value);
            t = t->next;
        }
    }
}

### 未完成
- [ ] 解析 Valgrind 的運作原理和針對本程式的使用
- [ ]根據 dudect 工具以及提出的對應論文 Dude, is my code constant time?，探討一種以實驗而非理論驗證時間複雜度的方法
- [ ]留意 MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR 等巨集的使用，並探討其動機和用法

## 參考資料