---
# System prepended metadata

title: 2020q3 Homework1(lab0)
tags: [sysprog2020]

---

# 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
```
![](https://i.imgur.com/OUoV5rN.png)



## [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