# 2020q3 Homework1 (lab0)
###### tags: `sysprog2020`
contributed by < [`Msiciots`](https://github.com/Msiciots/lab0-c) >
[**作業說明**](https://hackmd.io/@sysprog/2020-lab0)
## :penguin: 作業要求
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* ==詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* 在提交程式變更前，務必詳閱 [如何寫好 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/2020-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
* 挑戰題
* 參照 [antirez/linenoise](https://github.com/antirez/linenoise)，強化 `qtest` 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 `h` 之後按下 Tab 按鍵，自動接續補上 `elp`，成為完整的 `help` 命令)。除了整合程式碼外，應當說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
* 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
* 截止日期：
* Sep 20, 2020 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高
## 開發紀錄
### 開發環境
- Ubuntu 20.04.1 LTS
- gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
### `queue.h`
首先滿足 `q_insert_tail` 與 `q_size` 須達到 $O(1)$ 時間複雜度的要求，新增指向串列尾端的指標 (tail) 與表示串列元素個數的 (size) ，方便在後續操作中使用。
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### `queue.c`
#### q_new
- 檢查初始化是否分配記憶體成功，若失敗則將錯誤訊息輸出到 `stderr`
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
fprintf(stderr, "malloc() failed: malloc() return NULL\n");
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### q_free
- 參考[第一周上課內容](https://hackmd.io/@sysprog/c-linked-list?type=view)，使用指標的指標移動節點
- 新增 `*tmp` 釋放節點記憶體
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t **indirect = &q->head;
while (*indirect){
list_ele_t *tmp = *indirect;
indirect = &(*indirect)->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
#### q_insert_head & q_insert_tail
兩者功能相似，以 `q_insert_head` 作為舉例
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q || !s)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh) {
fprintf(stderr, "malloc() failed: newh in q_insert_head().\n");
return false;
}
newh->value = strdup(s);
if (!newh->value) {
fprintf(stderr, "strdup() failed: new->value in q_insert_head().\n");
free(newh);
return false;
}
newh->next = q->head;
q->head = newh;
// If newh is the first element.
if (!q->tail)
q->tail = newh;
// Increase amount of elements.
q->size++;
return true;
}
```
每次分配記憶體 (`maclloc()`, `strdup()`) 後檢查，若失敗則印出錯誤訊息並釋放已分配記憶體空間 (`newh`)。
`insert_head`的動作視覺化如下圖:
`newh->next = q->head;`
```graphviz
digraph add_entry {
rankdir=LR;
node [shape=record];
head [label= "q-head"];
tail [label= "q-tail"];
n1 [label="{ <data> | <ref> }"];
n2 [label="{ <data> | <ref> }"];
n3 [label="{ <data> | <ref> }"];
new [label="{ <data> | <ref> }",color=Red];
new:ref:c -> n1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head-> n1;
tail -> n3;
n1:ref:c -> n2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n2:ref:c -> n3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n3:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`q->head = newh;`
```graphviz
digraph add_entry {
rankdir=LR;
node [shape=record];
head [label= "q-head"];
tail [label= "q-tail"];
n1 [label="{ <data> | <ref> }"];
n2 [label="{ <data> | <ref> }"];
n3 [label="{ <data> | <ref> }"];
new [label="{ <data> | <ref> }",color=Red];
new:ref:c -> n1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head-> new;
tail -> n3;
n1:ref:c -> n2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n2:ref:c -> n3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n3:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
如果 `q->tail` 不存在代表第一次新增節點，`q->head`, `q->tail` 一起指向 `newh`
```cpp=
if (!q->tail)
q->tail = newh;
```
```graphviz
digraph add_entry {
rankdir=LR;
node [shape=record];
head [label= "q-head"];
tail [label= "q-tail"];
new [label="{ <data> | <ref> }",color=Red];
head-> new;
tail -> new;
new:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
#### q_remove_head
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *rm = q->head;
if (sp && rm->value) {
strncpy(sp, rm->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
q->head = q->head->next;
free(rm->value);
free(rm);
q->size--;
return true;
}
```
利用 `rm` 指到欲刪除的節點，再將節點內容複製到 `sp`，隨後進行刪除。
#### q_size
```cpp=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
如果 `q` 存在直接回傳`q->size`（初始值為 0）
#### q_reverse
```cpp=
void q_reverse(queue_t *q)
{
if (!q || !q->head || !q->head->next)
return;
list_ele_t *pre = NULL;
list_ele_t *cur = q->head;
list_ele_t *next;
q->head = q->tail;
q->tail = cur;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
}
```
`if (!q || !q->head || !q->head->next)` 在節點為空或只有一個節點時不需 reverse ，直接回傳。利用指標 `pre`, `cur` , `next` 依序紀錄前一個節點、當前節點和下一個節點進行串列反轉。
#### q_sort
```cpp=
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
使用 merge sort 實作排序演算法，找到串列中間節點分成兩份再進行 merge_sort（Divide），之後合併回傳陣列（Conquer）。
```cpp=
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
return merge(l1, l2);
}
```
利用 `strcasecmp()` 比對串列大小，`head` 指到合併後串列的開頭，`*tmp` 指到當前新增的節點
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l1)
return l2;
if (!l2)
return l1;
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
/* sort list elements based on strnatcmp */
while (l1 && l2) {
if (strcasecmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
if (l1)
*tmp = l1;
if (l2)
*tmp = l2;
return head;
}
```
## [Valgrind](https://valgrind.org) 程式執行分析
```
make valgrind
```
利用作業中事先配置好的 `valgrind` 檢查記憶體錯誤，從[執行輸出](https://github.com/Msiciots/lab0-c/blob/master/valgrind-output/make-valgrind)初步沒有發現問題（`malloc() & strdup() failed: ...` 是我 `queue.c` 程式自行輸出的錯誤訊息）
### 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
Todo
## 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
Todo
Sign in with Wallet
Connect another wallet