# 2020q3 Homework1(lab0)
contributed by < `joe-U16` >
###### tags: `sysprog2020`
:::warning
由於對Git 的不熟悉，導致有兩個帳號commit 這個作業，但這兩個帳號都是我的。
Github 上commit 的有 \<papd32> \<joe-U16>
:::
## Outline
[TOC]
## 環境
```bash=
Linux papd-Aspire-M7720 5.4.0-45-generic #49-Ubuntu SMP Wed Aug 26 13:38:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 作業要求
在 ``queue.[c/h]`` 中完成以下實作
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素
## 實作流程
### queue.h
* q_size
* 實作函式 q_size
* 要讓q->size存取可在constant time所以在struct新增size
* 新增 int size 這個新成員到 struct queue_t
* 修改 q_size 的傳回值，改成傳回 q->size
* list_ele_t *tail
* 在實做 queue.c中的 q_insert_tail，控制時間複雜度為O(1)
* 新增 *tail 在struct queue_t中
```cpp=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* 一開始make check都是segment fault，原因是因為讓NULL指向其他地址，要注意這個地方
* q_size
* 要先判斷queue是不是null，否則會讓null指向size，發生segment fault
```cpp=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
* q_new
* 如果queue沒有分到記憶體就回傳null。
* 建立一個empty 的queue，裡面都沒有東西，所以head指向NULL，tail也指向NULL，size 為0。
```cpp=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q) return q;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
* q_free
* 要把整個linked list 的node和value都清空。
```cpp=
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *tmp = q->head;
while (q->head) {
q->head = q->head->next;
tmp->next = NULL;
free(tmp->value);
free(tmp);
tmp = q->head;
}
free(q);
}
```
* q_insert_head
* 在做insert時，出現ERROR: Need to allocate and copy string for new list element
* 將newh->value = s; 更改為 strcpy(newh->value, s);
* 結果變Segmentation fault occurred. You dereferenced a NULL or invalid pointer
* 試很久還是segmentation fault occurred， 回頭看文件。
* 要記得幫新的node配置記憶體。
* 使用[malloc](https://en.wikibooks.org/wiki/C_Programming/Memory_management)，他可以配置一段記憶體，並傳回這段記憶體的第一個位址。
* 要記得幫string 配置記憶體。
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *tmp;
tmp = malloc(sizeof(char) * (strlen(s) + 1));
if (!tmp) {
free(newh);
return false;
}
newh->value = tmp;
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
if (!q->size) {
q->tail = q->head;
}
q->size += 1;
return true;
}
```
* q_insert_tail
* 跟insert head很像。
* 要記得配置記憶體
* 要把q->tail放到新加的tail上
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
char *tmp;
tmp = malloc(sizeof(char) * (strlen(s) + 1));
if (!tmp) {
free(newt);
return false;
}
newt->value = tmp;
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (q->size) {
q->tail->next = newt;
q->tail = newt;
} else {
q->head = newt;
q->tail = newt;
}
q->size += 1;
return true;
}
```
* q_remove_head
* 一開始的寫法先配置一段記憶體空間給一個pointer variable
* 把q->head->value 丟到這個記憶體空間。
* 再把sp 指向這個有string的記憶體空間。
* 這個方法錯在這個function裡的sp指向了這個位址
* 但在外面的sp的位址並沒有變。
* [C 語言中，萬物皆是數值 (everything is a value)，函式呼叫當然只有 call-by-value。「指標的指標」(英文就是 a pointer of a pointer) 是個常見用來改變「傳入變數原始數值」的技巧。](https://hackmd.io/@sysprog/c-pointer?type=view)
* 後來發現，不用配置，他已經配置好了，大小為bufsize，只要將q->head-value 丟到sp這個位址就好了。
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
if (sp) {
size_t buf;
if (bufsize > strlen(q->head->value)) {
buf = strlen(q->head->value);
} else {
buf = bufsize - 1;
}
strncpy(sp, q->head->value, buf);
*(sp + buf) = '\0';
}
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
list_ele_t *node;
node = q->head;
q->head = q->head->next;
node->next = NULL;
free(node->value);
free(node);
q->size -= 1;
return true;
}
```
* q_reverse
* 需要完成的事
* 將q->head以及q->tail互換
* 講每個node->next從指向右邊變成指向左邊
* 利用三個指標，重複執行
1. 將原本指向right的node->next，指向left
2. 將三個指標往前一格
```cpp=
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
q->tail = q->head;
list_ele_t **node = &q->head;
list_ele_t *left = NULL;
list_ele_t *right = (*node)->next;
while (right) {
(*node)->next = left;
left = (*node);
(*node) = right;
right = right->next;
}
(*node)->next = left;
q->head = (*node);
return;
}
```
* q_sort
* 一開始參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)的merge sort，結果sort 失敗。
* 因為在merge時，比較不該直接用==(slow->value < fast->value)==做判斷。
* 該改成使用 ==strcasecmp(slow->value, fast->value)==
* sort 可成功跑後，發生trace-15-perf 0/6 ，上面寫performance of insert_tail, size, reverse, and sort 不好。
* 想說是用遞迴寫，造成記憶體資源消耗太多。
* 後來參考[@ZhuMon](https://hackmd.io/ZhuMon/lab-0)寫的方法，改成用pointer to pointer 紀錄head的位置，就成功了。
* 開啟 **make = SANITIZER=1** 後，**TESTING trace-15-perf**出現Segmentation fault occurred
```cpp=
void splitlist(list_ele_t *head, list_ele_t **left, list_ele_t **right)
{
*left = head;
*right = head->next;
while (*right && (*right)->next) {
*left = (*left)->next;
*right = (*right)->next->next;
}
*right = (*left)->next;
(*left)->next = NULL;
(*left) = head;
}
void MergeList(list_ele_t **head)
{
if (!*head || !(*head)->next)
return;
list_ele_t *l1;
list_ele_t *l2;
splitlist(*head, &l1, &l2);
MergeList(&l1);
MergeList(&l2);
*head = NULL;
list_ele_t **tmp = head;
while (l1 && l2) {
if (strcasecmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &(*tmp)->next;
}
*tmp = l2 ? l2 : l1;
}
void q_sort(queue_t *q)
{
if (!q || !q->head) {
return;
}
MergeList(&q->head);
q->tail = q->head;
while (q->tail->next) {
q->tail = q->tail->next;
}
return;
}
```
## 除錯
* 輸入
```bash=
make SANITIZER=1
```
原本分數為100/100，結果變成89/100
* trace-15-perf
```bash=
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-15-perf 0/6
```
* trace-17-complexity:
```bash=
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
=================================================================
==137216==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55a2cfa34a60 at pc 0x55a2cfa23a24 bp 0x7ffe1c5207c0 sp 0x7ffe1c5207b0
READ of size 4 at 0x55a2cfa34a60 thread T0
```
## 透過Massif 視覺化 "simulation"過程中的記憶體使用量
* 根據lab-0說明，使用valgrind
```bash=
make valgrind
```
* 跑完後就會見到：
```bash
Test with specific case by by running command:
scripts/driver.py -p /tmp/qtest --valgrind -t <tid>
```
* 使用massif 做視覺化分析
```bash=
valgrind --tool=massif /tmp/qtest
```
* 使用[massif-visualizer](https://github.com/KDE/massif-visualizer) 將上一步產生的資料圖形化
```bash=
massif-visualizer massif.out.81012
```
## [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
* 解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度
* simulation是一個option 可以打開關上。
* simulation=1時，會call dudect裡的is_insert_tail_constant
* is_insert_tail_constant 會call ```bool doit(int mode)```, 來對執行時間做分析。
* Student’s t-distribution
* 根據小樣本估計成常態分佈且變異數未知的總體的平均值
* 樣本均值：$\bar{X_n} = {X_1 + ... + X_n} \over n$
* 樣本變異數：$S_n^2 = {1 \over {n-1}}\sum(X_i - \bar{X_n})^2$
* 呈現常態分佈且均值和變異數分別為0和1
* 常態分佈：機率密度函數呈鐘形
* 機率密度函數(PDF):將一個取值點附近區域進行積分，用以描述隨機變量的輸出值。
* 隨機變數為0的機率較高
* T-statistics：$T={{\bar{X_n} - \mu} \over {S_n \over \sqrt{n}}}$
* Two sample t-test：檢測兩組樣本的平均值是否不同
* 程式實作的原理
* 使用公式 $t = {{\bar{X_1} - \bar{X_2}} \over \sqrt{{s_1^2 \over N_1} + {s_2^2 \over N_2}}}$ ，得出的結果是一個統計值，這個值若是正，則將此值到無限大做積分後乘於2，得到t超過此極值的機率(p-value)。
* 若此機率(p-value)小於$\rho=0.5$則反駁原先虛無假說，轉而支持對立假說，代表這兩組資料存在顯著性差異，也代表不為constant
* $\rho=0.5$代表的是兩組數據具備顯著性差異的可能性為95％。
* 程式所運作為判斷t是否超過一定值，來決定是否為constant time
```cpp=
bool report(void)
{
...
if (max_t > t_threshold_bananas) {
return false;
} else if (max_t > t_threshold_moderate) {
return false;
} else { /* max_t < t_threshold_moderate */
return true;
}
}
```
## Todo
* 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
* 程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案
* 挑戰題
* 參照 antirez/linenoise，強化 qtest 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 h 之後按下 Tab 按鍵，自動接續補上 elp，成為完整的 help 命令)。除了整合程式碼外，應當說明 antirez/linenoise 的運作原理，注意到 termios 的運用
* 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
* 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request
## Reference
* https://www.khanacademy.org/math/ap-statistics/two-sample-inference/two-sample-t-test-means/v/two-sample-t-test-for-difference-of-means
* https://www.khanacademy.org/math/statistics-probability/significance-tests-one-sample/more-significance-testing-videos/v/z-statistics-vs-t-statistics
* https://medium.com/@wenwu53/sas-proc-ttest-d4e3da82bb88
* https://en.wikibooks.org/wiki/C_Programming
Sign in with Wallet
Connect another wallet