# 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`
## 測試結果
```shell
$ 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;`用來記錄目前的長度。
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### q_new()
首先是建立一個queue ，過程沒太大問題，要注意`malloc` 有可能會返回`NULL` ，所以在第29行要針對這個情況特別處理。
```cpp=25
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 去對每一個節點做處理。
```cpp=40
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 增加。
```cpp=66
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` 改成指向即將插入的節點。
```cpp=104
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)。
```cpp=139
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)$。
```cpp=165
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`。也是很直觀的做法，但一開始因為題目敘述理解錯誤，誤解為不能多使用額外空間設置變數來處理。
```cpp=182
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 前的狀態)。
```cpp=239
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 關閉。
```cpp=267
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
```cpp
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 等巨集的使用，並探討其動機和用法
## 參考資料
Sign in with Wallet
Connect another wallet