# 2019q3 Homework2 (lab0)

contributed by < `kaeteyaruyo` >

## 作業要求

- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [x] ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改。
- [x] 編輯「[作業區](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)，探討一種以實驗而非理論驗證時間複雜度的方法
- [x] 留意 `MAGICHEADER`, `MAGICFREE`, `MAGICFOOTER`, `FILLCHAR` 等巨集的使用，並探討其動機和用法

## 開發記錄

* [GitHub Repo](https://github.com/kaeteyaruyo/lab0-c)

* 由於以下的文件要求，所以我在 `queue.h` 中的 `queue_t` 中新增了 `tail` 和 `size` 兩個欄位

> Two of the functions: q_insert_tail and q_size will require some effort on your part to meet the required performance standards. Naive implementations would require O(n) steps for a queue with n elements. We require that your implementations operate in time O(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. You can do this by including other fields in the queue_t data structure and managing these values properly as list elements are inserted, removed and reversed.

* 在 `q_new()` 當中加入了 error handling ，僅在成功配置記憶體時進行 queue 的初始化
* 由於我需要先知道有 node 在 linked list 裡的記憶體使用狀況是如何，才可以進一步思考要怎麼釋放這些記憶體，所以我先行完成了 `q_insert_head()` 與 `q_insert_tail()` 這兩個函式
* 又因為這兩個函式大部分的內容是一樣的（create 一個新的 node 的部份），所以我把重複的內容額外再包裝成了一個函式，以供重複利用
* 在 create node 時，因為是先配置 node 本身的記憶體，才配置字串用的記憶體，因此在配置字串的記憶體失敗時，需要先釋放 node 的記憶體才可以 return false ，否則會造成 memory leak
* 這兩個函式在第一個 node 被插入佇列時都需要做額外的檢查，以避免 `head` 或 `tail` 其中一人應指到但未指到東西
* 因為在實作 `q_insert_head()` 和 `q_insert_tail()` 時需要用到 `q_size()` ，所以也順手實作了。由於附有 NULL pointer checking 的功能，任何需要查詢佇列大小的地方都應該呼叫此函式，而非直接讀取 `size`
* 可以插入就應該要可以移除 node ，所以接著實作 `q_remove_head()`
* 此函數的註解內說明了「若 `sp` 指標非 `NULL`，則複製被移除的 node 當中的字串出來」，換言之，如果 `sp` 指標為空就什麼都不用做，由此可知這個函式可以單純用來釋放記憶體，因此稍候可以直接在 `q_free()` 中使用此函式
* 在移除 queue 中的唯一一個 node 時，需要額外將 `tail` 也指向 `NULL` ，否則會造成 dangling pointer
* 在複製字串時，需要注意在尾端補上 `'\0'`
* 有了移除一個 node 的功能，在 `q_free()` 當中可以直接重複呼叫 `q_remove_head()` 直到佇列被清空為止，再釋放佇列本身的記憶體即可
* `q_reverse()` 的部份，由於不能使用新的記憶體，因此直接調整各個 node 的 `next` ，使其指向自己的前一個元素，如此可在不額外使用記憶體的情況下，在 $O（n）$ 的時間內完成

:::danger
注意共筆書寫原則：中英文之間用空白字元區隔
:notes: jserv
:::
:::info
已修正~
:::

:::danger
下方仍有類似的不一致問題，請掃描共筆內容。紀律和慣例的建立很重要
:notes: jserv
:::

## 自動評分系統

執行 `make test` 將會生成執行檔 `qtest` 並且自動執行 15 項評分。

進入 Makefile ，可以看到裡頭 `test` 那項寫著：

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

:::info
為何不是 `cmake`?
:::

:::warning
`cmake` 和 shell-based 的語法落差很大
:notes: jserv
:::

亦即在 `qtest` 和 `scripts/driver.py` 都存在的情況下，執行 `scripts/driver.py` 這個指令（因為第一行寫了 `#!/usr/bin/python` ，所以會由 python 執行）。

於是再進入 `scripts/driver.py` 這個檔案，看到最下面

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

往上看有看到 `run()` ，裡頭定義了這個 driver 會做的事：

* 不帶參數執行時，使用預設的設定（執行檔叫作 `qtest` 跑完所有的 15 個測試、僅印出測試的名字與得分...等）進行評分
* 參數 `-h` 會印出這個 driver 的使用方法
* 參數 `-p PROG` 可以設定執行檔的名字
* 參數 `-t TID` 可以指定要跑哪一個測驗
* 參數 `-v VLEVEL` 可以設定要印出哪些資訊（分成 0-3 四個等級，數字愈大印出的東西愈多）
* 參數 `-A` 會讓測驗結束之後多生成一個記錄得分的 json object （我猜是給助教快速評分用的？）
* 參數 `--valgrind` 決定要不要啟用 valgrind

指定完參數之後，會生成一個 `Tracer` 的物件。此物件裏面定義了 trace 檔的檔名與路徑，透過呼叫此物件的 `run()` 來進行評分。當中最重要的一個迴圈說明了評分的過程:

for t in tidList:
...
    ok = self.runTrace(t)
    maxval = self.maxScores[t]
    tval = maxval if ok else 0
...

針對每一個 trace id ，此物件對其呼叫了 `runTrace()` ，在 `runTrace()` 裏面，透過 `subprocess.call()` 來執行 `qtest` 讀取不同的 `.cmd` 檔，若可以成功返回 0 (則 `ok` 會是 `true` )，則此題得分，否則將印出錯誤訊息，並且此題算 0 分。每題的配分也定義在 `Trace` 類別當中。

由於 `runTrace()` 被包在 try-catch block 裏面，所以就算執行 `qtest` 後遭遇了錯誤，也不會造成整個 `driver.py` 停止運作，可以繼續完成所有評分。

在全部的評分項目都執行完後，將會輸出總分。

此外，執行 `make valgrind` 可以在啟用 valgrind 的模式下進行評分。(需要將 `.valgrindrc` 中的 `--quiet` 註解掉才看得到訊息)

## `qtest` 的行為與技巧

`qtest` 是用來操作我們寫的佇列的功能的使用者介面，此專案將 `qtest` 的不同功能分拆在以下幾個檔案中：

* `qtest.c`: 入口檔案，以及呼叫佇列操作函式的定義、訊號處理等
* `queue.[hc]`： 佇列行為的定義
* `console.[hc]`: 與命令列介面有關的大部份操作，包含輸入輸出、解析輸入字串、命令列本身的生命週期控制等
* `harness.[hc]`: 重載原生的記憶體配置函式（以進行錯誤偵測和評分）、記憶體區段確認、例外處理等
* `report.[hc]`: 與檔案讀寫有關的函式

在 `qtest` 中，可以看到一些訊號處理或程式設計的技巧：

* 將是否有錯誤發生、是否可以結束程式、是否有執行緒被 block 住、是否可以 prompt 資料等，都以旗標的方式進行檢查（而不是直接呼叫對應的處理函式）。是在嵌入式系統中很常見的模擬多執行序的技巧
* 在 `queue_init()` 中，有描述到 `SIGSEGV` 和 `SIGALRM` 兩個訊號的處理方法。這兩個訊號最終都會由 `trigger_exception()` 處理，藉由 `siglongjmp()` 這個內建函式，讓程式可以回到上一次例外發生的地方繼續執行，而非直接 crush （ segmentation fault 的情況）或停止回應（執行逾時的情況）
* 透過以下三行定義來重載系統原生的記憶體操作函式：

#define malloc test_malloc
#define free test_free
#define strdup test_strdup

* 透過 `MAGICHEADER`、 `MAGICFREE`、 `MAGICFOOTER`、 `FILLCHAR`等巨集來進行記憶體使用情況的管理
* `MAGICHEADER`： 用來填充每個已被配置的記憶體的最開頭，以供之後辨識是不是合法使用的記憶體區段
* `MAGICFREE`： 用來填中每個被釋放了的記憶體區段的開頭跟尾巴，由於 `free()` 不會去變更被釋放的記憶體區段的內容，所以之後如果讀取到了這樣的非法區段，也可以透過內容物辨識
* `MAGICFOOTER`： 用來填充每個已被配置的記憶體的尾端，以供之後辨識是不是有記憶體區段損毀的狀況發生
* `FILLCHAR`： 在還沒有填入任何資料以前 / 所有資料應該被清除之後，拿來暫時填充未使用的記憶體的值

## Valgrind 的運作原理

待補充

## dudect

待補充