# 2019q1 Homework1 (lab0)
contributed by < `Rispolyv0n` >
:::danger
認真看作業要求，除了提及如何逐步達到要求，還需要進行:
1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧
還未達成符合預期目標，請繼續付出！
:notes: jserv
:::
## 題目要求
根據[C Programming Lab in CMU](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)，此作業需修改 queue.c, queue.h 兩個檔案，實作以下七個函式：
* `q_new()` : 建立一個新的空佇列
* `q_free()` : 清空一個佇列所用到的空間
* `q_insert_head()` : 試圖在佇列頭端插入一個節點 (用於LIFO)
* `q_insert_tail()` : 試圖在佇列尾端插入一個節點 (用於FIFO)
* `q_remove_head()` : 試圖刪除佇列頭端的第一個節點
* `q_size()` : 計算佇列所含的節點數量
* `q_reverse()` : 將佇列中的節點做倒序，並且不得 free 或 allocate 佇列中的節點，只能做重新排列。
不能對佇列中所儲存的字串長度設上限。
`q_insert_tail()` 及 `q_size()` 兩個函式需為 $O(1)$ 。
測試檔會測試超過 1,000,000 個節點的佇列，作業分數會利用15個 trace 檔做計算(自動評分系統)。
## 程式說明
### queue.h
作業要求 `q_insert_tail()` 及 `q_size()` 兩個函式需為 $O(1)$ ，因此修改 `struct queue_t ` 如下 (註解標示處)：
```c=
typedef struct {
list_ele_t *head;
unsigned int size; // 新增此field用來紀錄 queue size
list_ele_t *tail; // 新增此field用來紀錄 tail element 的位置
} queue_t;
```
### queue.c
有了以上的結構，就可以在必要的地方對 queue.h 中所定義的各個 field 做適當的操作，如下 (註解標示處)：
`q_new()` 第 5 ～ 7 行將 structure 中 各 field 初始化，包括將 q->head, q->tail 初始化為 NULL， 以及將 q->size 初始化為 0 ：
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL; // 新增 queue 時將 q->head, q->tail 初始化為 NULL
q->size = 0; // 將 q->size 初始化為 0
q->tail = NULL;
}
return q;
}
```
`q_insert_head()` 第 14 ～ 17 行，在確定插入節點時將 q->size 加 1, 並調整 q->tail ：
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q) {
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh) {
newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
if (newh->value) {
memset(newh->value, '\0', strlen(s) + 1);
strcpy(newh->value, s);
newh->next = q->head;
q->head = newh;
q->size += 1; // insert 新節點時，將 q->size 加 1
if (q->size == 1) { // 若新增的節點為第一個節點，則 q->tail 也需指向此節點
q->tail = newh;
}
return true;
}
free(newh);
}
}
return false;
}
```
`q_remove_head()` 第 12 ～ 14 行，在確定移除節點時將 q->size 減 1, 並調整 q->tail ：
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q && q->size > 0) {
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size -= 1; // 移除節點時將 q->size 減 1
if (q->size == 0) // 若移除節點後， queue 為空，則需將 q->tail 變為 NULL
q->tail = NULL;
return true;
}
return false;
}
```
有了以上適當的操作後，即可將 `q_insert_tail()` 及 `q_size()` 兩個函式修改為如下，以達到 $O(1)$ ：
`q_insert_tail()` 中可直接找到 queue 的 tail 位置，對其插入節點，不用從頭遍歷整個 queue ，因此執行時間就不會受 queue 長度影響：
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (q) {
list_ele_t *newh; // newh 為即將被 insert 的新節點
newh = malloc(sizeof(list_ele_t));
if (newh) {
newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
if (newh->value) {
memset(newh->value, '\0', strlen(s) + 1);
strcpy(newh->value, s);
newh->next = NULL;
if (q->tail) // 若 q->tail 已指向某節點，則將該節點的 next 指向新節點 newh
q->tail->next = newh;
else // 若 q->tail 尚未指向任何節點，表示此時 queue 中無任何節點，因此也需要將 q->head 指向新節點 newh
q->head = newh;
q->tail = newh; // 直接將 q->tail 指到新的 element 上，不用每次都從 q->head 走過整個 linked-list 直到尾端
q->size += 1;
return true;
}
free(newh);
}
}
return false;
}
```
`q_size()` 函式中可直接 return structure `queue_t` 中的 field `size` ，不用每次都遍歷 queue 中所有節點，邊計算節點數，因此執行時間就不會受 queue 長度影響：
```c=
int q_size(queue_t *q)
{
if (q) {
return q->size;
}
return 0;
}
```
## 自動評分系統運作原理
### 啟動評分系統
執行 `$make test` 時，會去呼叫 scripts/driver.py ，而 scripts/driver.py 中紀錄著所有測試檔的檔名 (`traceDict`) 及測試檔所在的資料夾位置 (`traceDirectory`)。若執行時無特別指定測試檔編號，則會依序利用所有 `traceDict` 中的測試檔做測試。可於 `runTrace()` 函式中看到利用 `subprocess.call()` 執行了 `$./qtest` ，同時指定用某測試檔去做測試。 (如以下程式碼的第 7, 9 行) :
```python=
# in scripts/driver.py
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
```
### 執行測試檔內容
首先 console.h 中定義了 `cmd_ele` 的 `struct` ，用來紀錄各個 command 及其相關資訊。如下：
```c=
// in console.h
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name; // command 名稱
cmd_function operation; // 要執行的 function
char *documentation; // command 描述
cmd_ptr next; // 指向下一個 cmd_ele
};
```
qtest.c 的 `main()` 中呼叫 `init_cmd()` 及 `console_init()` 定義了各種 command 、有關 command 的描述、以及讀取該 command 後要呼叫的函式，並將這些 command element 用 console.c 中的 `add_cmd()` 以 linked list 的方式紀錄於 `cmd_list` 。如下：
```c=
// in console.c
void add_cmd(char *name, cmd_function operation, char *documentation)
{
cmd_ptr next_cmd = cmd_list;
cmd_ptr *last_loc = &cmd_list;
while (next_cmd && strcmp(name, next_cmd->name) > 0) {
last_loc = &next_cmd->next;
next_cmd = next_cmd->next;
}
cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
ele->name = name;
ele->operation = operation;
ele->documentation = documentation;
ele->next = next_cmd;
*last_loc = ele;
}
```
而測試檔中所寫的就是這些 command ，qtest.c 中的 `run_console()` 會去一行行讀取測試檔中的 command ，並在 `interpret_cmda()` 中從 `cmd_list` 找到對應的 `cmd_ele` ，呼叫對應函式。
### 錯誤處理
qtest.c 中的 `main()` 接完參數後，會呼叫 `queue_init()` ，其中將 `SIGSEGV` 及 `SIGALRM` 兩個訊號各利用 `signal()` 設定了各自的 signal handler ，以便處理「 access 到不合法的記憶體」與「超時操作」兩種情況，如下：
```c=
// in qtest.c
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
而兩個 signal handler 中皆會傳各自的 message 給 harness.c 中的 `trigger_exception()` 。其中 `jmp_ready` 為一 `volatile` 變量，是為了防止編譯器完全根據程式碼中的上下文去優化，導致執行時的值可能與實際上 `jmp_ready` 記憶體中的值不一樣而產生不可預期的執行結果，這樣可以強迫編譯器每次用到 `jmp_ready` 時都要乖乖的去記憶體中重新讀取它當下的值。此處為了防止讀取 `jmp_ready` 值時，值又被意外更動的可能，用了 type `sig_atomic_t` ，確保讀取的動作不會被中斷。
```c=
// in harness.c
static volatile sig_atomic_t jmp_ready = false;
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
由以上程式碼可知，當 `jmp_ready` 為真時，就跳到上次做 `sigsetjump()` 時所存的 `env` 下。而 `sigsetjump()` 會在每次讀取新 command 時要呼叫大家自己實作的函式前，在 `exception_setup()` 中被呼叫，因此若執行自己實作的函式時發生「超時操作」與「 access 到不合法的記憶體」兩種情況，即可回溯記憶體環境至執行自己實作的函式前，並且跳過已知執行後會出錯的函式，結束整個執行 command 的包裝函式。
由 [linux man page](https://linux.die.net/man/3/sigsetjmp) 可知若是從 `siglongjmp()` 返回，則 `segsetjump()` 會返回非零，因此 `exception_setup()` 中即可對「初始程式回溯點」與「console指令函式後續操作發生錯誤而啟動 `trigger_exception()` 返回回溯點」兩種情況做對應處理。
而 `jmp_ready` 的值在準備要呼叫大家自己寫的 queue.c 中的 function 前會被設為 `true` ，若安全執行完沒有出錯，或者中途執行時出錯了返回程式回溯點，都會將 `jmp_ready` 設回 `false` 。
```c=
// in harness.c
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_setup()` 會返回 `true` 。而若為「 console 指令函式後續操作發生錯誤而啟動 `trigger_exception()` 返回回溯點」，則 `exception_setup()` 會返回 `false` 。因此只要像其它 console 指令函式一樣，將可能引起錯誤的程式碼片段用 `if (exception_setup())` 包起來，第一次執行時，初始程式回溯點完，就會繼續執行 `if` 中有風險的程式碼。萬一執行過程中發生錯誤，就會跳回到 `if (exception_setup())` ，這時 `exception_setup()` 會返回 `false` ，即可安全的跳過會引起錯誤的程式碼，繼續完成 console 指令函式。以下拿 `do_new()` 函式為範例：
```c=
// in qtest.c
bool do_new(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
if (q != NULL) {
report(3, "Freeing old queue");
ok = do_free(argc, argv);
}
error_check();
if (exception_setup(true)) // 此處設下程式回溯點
q = q_new(); // 此行呼叫大家自己寫的可能引起錯誤的 q_new() 函式，若出錯則會返回273行，且excpetion_setup()返回零，因此整個 if 中的程式碼會被跳過，直接執行下一行的 exception_cancel()
exception_cancel();
qcnt = 0;
show_queue(3);
return ok && !error_check();
}
```
## 其它筆記
### "volatile" qualifier
> 1498 114) A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function.
> —— [The New C Standard](http://c0x.coding-guidelines.com/6.7.3.html)
被宣告 `volatile` 的變數，會防止編譯器根據程式碼上下文對該變數做過度優化。以下為一編譯器優化後卻導致非預期的執行結果範例：
```c=
uint32 status = 0;
while (status == 0)
{
/*
* 假設變數status並沒有在此迴圈中的程式碼被更新，
* 而我們實際上期待變數status會在迴圈進行到某個階段時
* 被其它不同步的線程或硬體更新後即跳出迴圈
*/
}
```
則以上程式碼可能因編譯器不知道變數 `status` 的值可能意外被改變，只根據程式碼判定變數 `status` 從頭到尾並未被更動，因此直接將迴圈改為一個無限迴圈如 `while(1)` ，減少訪問變數 `status` 值的次數，以達到優化目的。而這樣的編譯結果卻與我們所預期的不一樣，導致執行結果錯誤。因此我們需要 `volatile` 這個 qualifier，去防止編譯器過度優化，每次都去重新讀取變數 `status` 的值。
被宣告為 `volatile` 的變數代表它可能有著以下特性：
- Memory-mapped peripheral registers (硬體可直接讀寫的已定義的記憶體位址)
- Global variables modified by an interrupt service routine (會被中斷處理機制所更改的全域變數)
- Global variables within a multi-threaded application (多線程應用中通用的全域變數)
也就是此變數的值可能被硬體更新，或者被其它同時執行中的線程更新，不是完全根據當下執行中程式碼上下文的操作去做更動。讓編譯器知道變數具有這樣的特性，編譯器就不會對被宣告為 `volatile` 的變數做過度的優化了。
#### 參考
- [Introduction to the volatile keyword](https://www.embedded.com/electronics-blogs/beginner-s-corner/4023801/Introduction-to-the-Volatile-Keyword)
- [C語言: 認識關鍵字volatile](http://newscienceview.blogspot.com/2013/09/c-volatile.html) (上文翻譯)
- [The New C Standard](http://c0x.coding-guidelines.com/6.7.3.html)
- [程式碼參考](https://www.geeksforgeeks.org/understanding-volatile-qualifier-c-set-1-introduction/)
## TO-DO
- valgrind
- popen.returncode
Sign in with Wallet
Connect another wallet