# 2020q3 Homework1 (lab0)
contributed by <`fdsa654hg`>
###### tags: `sysprog2020`

## 測試環境

$ cat /etc/os-release
NAME="Ubuntu"
VERSION="20.04.1 LTS (Focal Fossa)"
$ cat /proc/version
Linux version 5.4.0-47-generic (buildd@lcy01-amd64-014) (gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)) #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020

## :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) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;

## `queue.h` & `queue.c` 實作

### `queue.h`

- 這個檔案有修改的部份很少，主要是應題目的要求 `q_instert_tail()` 和 `q_size()` 兩個函式要在 $O(1)$ 時間內完成，由於作業給予的 Linked List 為單向的結構，所以如果從 `head` 開始走直到找到 `tail` 時間複雜度是 $O(n)$ 無法控制在常數時間內完成，因此須在 `queue` 結構裡新建一個跟 `head` 相似的指標-- `tail` ，`q_size()` 也是同樣的道理，只要新建一個型別為 int 的變數 `size` 即可。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* new */
    int size;         /* new */
} queue_t;

* 另外我額外宣告了 merge sort 函式

void merge_sort(list_ele_t **q);

### `queue.c`

- 函式的實作幾乎都在這個檔案

##### `q_new()`

- 很簡單的函式，功能是建立一個新的空佇列，由於 `malloc` 未必能成功分配記憶體，故先檢查是否成功，否就回傳 `NULL` ，成功的話就初始化所有的變數，並回傳指標 `q`

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;

    return q;
}

##### `q_free()`

- 為了 `free` 整個佇列，先用 `cur` 存當前的 `q->head` ，再讓 `head` 變成它所指向的下一個位置，並使用 `cur` 指標釋放其所儲存的記憶體，重複做以下動作便能走訪整個佇列並清空它

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *cur = q->head;
    while (q->head) {
        q->head = q->head->next;
        cur->next = NULL;
        free(cur->value);
        free(cur);
        cur = q->head;
    }

    free(q);
}

##### `q_insert_head()`

- 函式的開頭就是分配記憶體，再檢查有沒有 `malloc` 成功，之後我原本想用 `strcpy` 將 `s` 的值傳給 `new_head->value` ，並使用 `memset` 加上'\0'，但根據 `cern` 指出這樣有 `buffer overflow` 的風險，所以我改用 `snprintf` ，而且它會自己補'\0'所以就不用使用 `memset` 了

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *new_head;
    new_head = malloc(sizeof(list_ele_t));
    if (!new_head)
        return false;

    new_head->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!new_head->value) {
        free(new_head);
        return false;
    }

    q->size += 1;

    snprintf(new_head->value, (size_t) strlen(s) + 1, "%s", s);
    new_head->next = q->head;
    q->head = new_head;

    if (!q->tail) {
        list_ele_t **tmp = &q->head;
        while ((*tmp)->next)
            tmp = &(*tmp)->next;
        q->tail = *tmp;
        q->tail->next = NULL;
    }
    return true;
}

##### `q_insert_tail()`

- 這個函式基本上跟 `q_insert_head` 是一樣的道理，只是它改變的是 `tail`

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *new_tail;
    new_tail = malloc(sizeof(list_ele_t));
    if (!new_tail)
        return false;

    new_tail->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!new_tail->value) {
        free(new_tail);
        return false;
    }

    q->size += 1;

    snprintf(new_tail->value, (size_t) strlen(s) + 1, "%s", s);
    if (!q->tail) {
        q->tail = q->head = new_tail;
        q->tail->next = q->head->next = NULL;
        return true;
    }

    q->tail->next = new_tail;
    q->tail = new_tail;
    q->tail->next = NULL;

    return true;
}

##### `q_remove_head()`

- 這個函式目的是將 `head` 刪除，並將其賦值給 `sp` ，開頭一樣先檢查指標是否不為空指標，一樣用 `snprintf` 將 `q->head->value` 傳給 `sp`，只是這裡的參數有 `bufsize` 所以不用自己算長度了，之後就是將 `head` 改為 `head->next` 並將原本的 `head` 及其內容物 `free` 掉

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    if (sp)
        snprintf(sp, bufsize, "%s", q->head->value);

    q->size -= 1;

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    tmp->next = NULL;

    free(tmp->value);
    free(tmp);
    return true;
}

##### `q_size()`

- 由於 `queue_t` 的 struct member 有 `size` ，故在確認指標是否正常及是否為空佇列後，直接回傳 `q_size` 即可

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;

    return q->size;
}

##### `q_reverse()`

- `head` 最後會變成 `tail` 所以先將其紀錄起來，之後可以直接賦值給新的 `tail`，由於 `head->next` 已經被 `cur` 存起來，所以可以將其指向 `NULL`，之後便利用 `prev`,`cur`,`next` 將整個佇列反轉，最後再重新設定 `head` 跟 `tail` 的值

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t *old_head = q->head;
    list_ele_t *prev = q->head, *next, *cur = q->head->next;
    q->head->next = NULL;

    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    q->head = prev;
    q->tail = old_head;
}

##### `q_sort()`

- 參考 [Linked List sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge sort 演算法做出來的
- 為了將 Linked List 分成兩部份，我原本想直接用 q->size/2+1 直接找出 `l2` 但演算法使用了 `fast` 跟 `slow` 兩個走訪 Linked List 速度不同的兩個變數來找 `l2` ，我完全沒想過這個方法，於是我學了起來
- 整個流程基本上跟網站上的演算法差不多，唯一的差別是我用了 `strncmp` 來防止 `buffer overflow` ，還有把 `merge` 的部份從遞迴改成迭代了，因為我 `trace16` 一直過不了，我看了一下裡面的指令要排序好幾萬個 string ，似乎是 `stack` 爆了，不過我無法確定，因為即使我把 `valgrind` 的參數 `--stack` 設成 `yes` 但還是它沒有顯示出 `stack` 的狀態

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;

    merge_sort(&q->head);
    while ((q->tail->next))
        q->tail = q->tail->next;
}

void merge_sort(list_ele_t **head)
{
    if (!(*head) || !((*head)->next))
        return;

    list_ele_t *l1 = *head;
    list_ele_t *l2 = (*head)->next;

    while (l2 && l2->next) {
        l1 = l1->next;
        l2 = l2->next->next;
    }
    l2 = l1->next;
    l1->next = NULL;
    l1 = *head;

    merge_sort(&l1);
    merge_sort(&l2);

    list_ele_t **tmp = head;

    while (l1 && l2) {
        if (strncmp(l1->value, l2->value, strlen(l2->value)) < 0) {
            *tmp = l1;
            l1 = l1->next;
        } else {
            *tmp = l2;
            l2 = l2->next;
        }
        tmp = &((*tmp)->next);
    }

    if (l1)
        *tmp = l1;
    else
        *tmp = l2;
}

### Git 使用

- Commit 成功

(base) jiahao@jiahao-GP63-Leopard-8RE:~/Desktop/code/lab0-c$ git commit -a
Following files need to be cleaned up:
queue.c
queue.h
[master 110414a] Implement all function correctly
 2 files changed, 151 insertions(+), 18 deletions(-)

### Clang-format 使用

- 透過 ```clang-format -i queue``` 直接改 coding-style

(base) jiahao@jiahao-GP63-Leopard-8RE:~/Desktop/code/lab0-c$ git commit -a
--- modified queue.c
+++ expected coding style
@@ -1,9 +1,9 @@
+#include "queue.h"
+#include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <assert.h>
 #include "harness.h"
-#include "queue.h"
 
 
  * Create empty queue.
@@ -12,12 +12,13 @@
 queue_t *q_new()
 {
     queue_t *q = malloc(sizeof(queue_t));
-    if(!q)return NULL;
+    if (!q)
+        return NULL;
 
     q->head = NULL;
     q->tail = NULL;
     q->size = 0;
-    
+
     return q;
 }
 
 
/***其他程式碼，請容許我省略***/
/***其他程式碼，請容許我省略***/
/***其他程式碼，請容許我省略***/


[!] queue.c does not follow the consistent coding style.

Make sure you indent as the following:
    clang-format -i queue.c


Make sure you indent as the following:
    clang-format -i queue.h

Following files need to be cleaned up:
queue.c
queue.h

### Valgrind 使用
- 我快把程式寫完的時候才發現有這個東西可以用
- 不過這也幫助我找到幾個 `bug` ，使用 ```valgrind ./qtest``` 會進入一個很像 `python` 直譯器的模式，裡面輸入指令會一行一行執行，我用這個工具找到問題
- 如：在 `trace16` 裡

# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
option fail 0
option malloc 1
new
ih RAND 10000
sort
reverse
sort
free
new
ih RAND 50000
sort
reverse
sort
free
new
ih RAND 100000
sort
reverse
sort
free

- 我發現每次只要先 `sort` 後再 `revese` 就會爆炸，仔細研究之後，知道是我在 `sort` 的時候 `head` 不小心改到它的值

- massif 圖例(執行 trace17 時記憶體使用情形）


- 以下是我不小心造成了無窮迴圈的情形，可注意到在圖表的最後記憶體並沒有歸零( trace05 )


- 自動測試軟體也發出了以下錯誤訊息

ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

### 研讀論文 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉

#### `dudect` 的運作原理：
- 經由多次測量程式執行的時間取得大量樣本，並使用統計學的方法，從而推得執行時間是否為常數時間
- 論文中提供了兩個方法：
- t-test:
- Welch’s t-test ( `dudect` 使用了此方法)
- non-parametric test:
- Kolmogorov-Smirnov

- 剩下的部份來不及做完了