---
# System prepended metadata

title: 進階電腦系統理論與實作 lab0

---

# 進階電腦系統理論與實作 lab0
[I01: lab0 宅色夫](https://hackmd.io/@sysprog/2020-lab0#I01-lab0)
[My github](https://github.com/a5932016)

# 作業要求
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
    * 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github)
* 詳細閱讀 C Programming Lab ，依據指示著手修改 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](https://autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
* 除了修改程式，也要編輯「作業區」，增添開發紀錄和 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 的運作原理，注意到 [termios](https://man7.org/linux/man-pages/man3/termios.3.html) 的運用
    * 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
    * 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request

# 環境
```
$ uname -a
Linux zihyan 5.7.0-kali1-amd64 #1 SMP Debian 5.7.6-1kali2 (2020-07-01) x86_64 GNU/Linux

$ gcc --version
gcc (Debian 10.2.0-9) 10.2.0
Copyright (C) 2020 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.

```

# 在 GitHub 上 fork lab0-c
照教學步驟完成即可
[我的lab0-c](https://github.com/a5932016/lab0-c)

# 開始撰寫queue.[ch]
## 如何測試
在目標資料夾後執行

方法1
```
make check
```
方法2
```
make test
```

方法3
```
make
./qtest
help
#依自行需求執行測試
```
結束後皆要執行`make clean`做清除

## q_size
### queue.h
`queue_t`結構新增`int size`
```
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    int size; /* Size of queue */
} queue_t;
```
### queue.c
修改function`q_size`，確認參數是否為NULL，如果為TRUE則傳回`q->size`
```
int q_size(queue_t *q)
{
    if (!q || !q->size)
        return 0;
    return q->size;
}
```

## q_new
### queue.h
`queue_t`結構新增`list_ele_t *tail;`
```
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size; /* Size of queue */
} queue_t;
```
### queue.c
`queue_t`因新增`size`和`tail`故需要做初始化
要確認是否成功分配記憶體，避免操作到空指標
```
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}
```

## q_free
傳入參數`queue_t`
先確認參數是否為NULL
依參數`q`使用`while loop`依序對`head`和`value`執行`free`
最後結束不要忘記對`q`執行`free`
```
void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}
```

## q_insert_head
加入新值在`head`前
指派一個新的`list_ele_t`，確認是否有建立成功
指派一個`char`，長度為`sizeof(char) * (strlen(s) + 1)`，額外留一個空間存`\0`
`tmp`指派到`newh`並指派為`q->head`，若`!q->tail`則指派到`q->tail`
`q->size`加1
```
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)
        return false;

    int len = sizeof(char) * (strlen(s) + 1);
    char *tmp = malloc(len);
    if (!tmp) {
        free(newh);
        return false;
    }

    memcpy(tmp, s, len);
    newh->value = tmp;
    newh->next = q->head;
    q->head = newh;

    if (!q->tail) {
        q->tail = q->head;
    }

    q->size += 1;

    return true;
}
```

## q_insert_tail
作法大致上與`q_insert_head`一樣
```
bool q_insert_tail(queue_t *q, char *s)
{
    if (!q || !s)
        return false;

    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    int len = sizeof(char) * (strlen(s) + 1);
    char *tmp = malloc(len);
    if (!tmp) {
        free(newt);
        return false;
    }
    memcpy(tmp, s, len);
    newt->value = tmp;
    newt->next = NULL;

    if (!q->head) {
        q->head = newt;
    }
    if (q->tail) {
        q->tail->next = newt;
    }

    q->tail = newt;
    q->size += 1;

    return true;
}
```

## q_remove_head
確認q是否為空
暫存`q->head`
將`q->head`指派`q->head->next`
`q->size -= -1` 如果`size`為`0`，則將`q->tail`指派為`NULL`
如果`sp`不為空，則把欲`free`的值指派到`sp`
最後執行對`tmp`和`tmp->value`執行`free`
```
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    q->size -= 1;
    if (!q->size) {
        q->tail = NULL;
    }

    if (sp) {
        size_t len =
            bufsize > strlen(tmp->value) ? strlen(tmp->value) : bufsize - 1;
        memset(sp, '\0', len + 1);
        strncpy(sp, tmp->value, len);
    }

    free(tmp->value);
    free(tmp);

    return true;
}
```

## q_reverse
反轉鏈結串列
參考 [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
`while loop`完成後要記得`q->head->next = NULL`和指派新的`head` `tail`
```
void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;

    list_ele_t *tmp;
    list_ele_t *prev = NULL;
    list_ele_t *curr = q->head;
    while (curr) {
        tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    q->head->next = NULL;

    tmp = q->head;
    q->head = q->tail;
    q->tail = tmp;
}
```

## q_sort
使用合併排序法
```
void mergeSort(list_ele_t **head)
{
    if (!*head || !(*head)->next)
        return;
    list_ele_t *l1 = (*head)->next;
    list_ele_t *l2 = *head;

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

    mergeSort(&l2);
    mergeSort(&l1);

    *head = NULL;
    list_ele_t **tmp = head;

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

    *tmp = l1 ? l1 : l2;
}

void q_sort(queue_t *q)
{
    if (!q || !q->head || q->size <= 1)
        return;
    mergeSort(&q->head);

    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}
```

# Valgrind 實驗
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
## 透過 Massif 視覺化 simulation 過程中的記憶體使用量
## 設計對應的實驗
//TODO

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