# 2020q3 Homework1 (lab0)
contributed by < guyleaf >
## 環境
``` shell
$ uname -a
Linux guyleaf-GS637RD 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
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.
```
## 作業要求
- [x] 詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
- [x] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。
## 程式實做
詳細程式內容: [Github](https://github.com/guyleaf/lab0-c)
### Macro
``` c=
#define min(a, b) (a < b ? a : b)
#define IS_NULL_EMPTY(s) (!s)
```
新增兩個 macro
* `min(a, b)` 用於取最小值
* `IS_NULL_EMPTY(s)` 用於檢查指標為NULL或變數為0
### Queue structure
``` c=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
新增 tail 指標以及 list size
* tail: 指向 queue 的尾端，用於實現 insert_from_tail 時間複雜度為 **O(1)**
* size: 紀錄該 queue 的 list 個數，用於實現 q_size 時間複雜度為 **O(1)**
### New queue
``` c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (IS_NULL_EMPTY(q))
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### 功能: 初始化 queue
特別注意，在分配記憶體空間後，需檢查是否有分配成功
有則回傳指標，沒有則回傳NULL
### Free queue
``` c=
void q_free(queue_t *q)
{
if (IS_NULL_EMPTY(q))
return;
/* Free the list elements and the strings */
list_ele_t *current = q->head;
while (current) {
q->head = current->next;
free(current->value);
current->value = NULL;
current->next = NULL;
free(current);
current = q->head;
}
/* Free queue structure */
q->size = 0;
free(q);
}
```
#### 功能: 釋放 queue 所有的記憶體空間
個人偏向釋放記憶體之前，先把變數內容全部歸零，清除敏感資料
### Insert from head
``` c=
bool q_insert_head(queue_t *q, char *s)
{
if (IS_NULL_EMPTY(q))
return false;
list_ele_t *newh = NULL;
newh = malloc(sizeof(list_ele_t));
if (IS_NULL_EMPTY(newh))
return false;
/* allocate space and copy the string into it */
newh->value = malloc(strlen(s) + 1);
if (IS_NULL_EMPTY(newh->value)) {
free(newh);
return false;
}
memcpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
if (IS_NULL_EMPTY(q->size))
q->tail = newh;
q->size++;
return true;
}
```
#### 功能: 新增一個 list node 並從 head 插入
* 特別注意，有用到 malloc 分配 heap 記憶體空間，記得都需要檢查是否分配成功
* 第二個 malloc 分配記憶體空間給 newh->value，如果分配失敗，回傳 false 前，記得釋放指標所指的記憶體空間
### Insert from tail
``` c=
bool q_insert_tail(queue_t *q, char *s)
{
if (IS_NULL_EMPTY(q))
return false;
list_ele_t *newt = NULL;
newt = malloc(sizeof(list_ele_t));
if (IS_NULL_EMPTY(newt))
return false;
/* allocate space and copy the string into it */
newt->value = malloc(strlen(s) + 1);
if (IS_NULL_EMPTY(newt->value)) {
free(newt);
return false;
}
memcpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (IS_NULL_EMPTY(q->size))
q->head = newt;
else
q->tail->next = newt;
q->tail = newt;
q->size++;
return true;
}
```
#### 功能: 新增一個 list node 並從 tail 插入
* 時間複雜度需為 **O(1)**
* 從 tail 插入時，記得更新原先 tail 的 next 指標，在實做過程中，造成無法找到後面的 node
### Remove from head
``` c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
return false;
list_ele_t *oldh = q->head;
q->head = q->head->next;
if (!IS_NULL_EMPTY(sp)) {
size_t length = min(strlen(oldh->value), bufsize - 1);
memcpy(sp, oldh->value, length);
sp[length] = '\0';
}
oldh->next = NULL;
free(oldh->value);
free(oldh);
q->size--;
if (IS_NULL_EMPTY(q->size))
q->tail = NULL;
return true;
}
```
#### 功能: 移除 queue 的最前面 node
* 如果 sp 指標不為NULL ，需把該 node 所儲存的文字內容，複製到該指標內
* 特別注意，bufsize 需與原先儲存在 node 內的文字空間比較，取其中最小值，複製適當的字數至 sp 指標，避免 Segmentation Fault
### Get queue's Size
``` c=
int q_size(queue_t *q)
{
return IS_NULL_EMPTY(q) ? 0 : q->size;
}
```
#### 功能: 取得該 queue 所擁有的 list node 數量
這裡也需要判斷 queue 是否為 NULL ，沒有則回傳0
### Reverse queue
``` c=
void q_reverse(queue_t *q)
{
if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
return;
list_ele_t *cursor = q->head, *prev = NULL;
while (cursor) {
list_ele_t *next = cursor->next;
cursor->next = prev;
prev = cursor;
cursor = next;
}
q->tail = q->head;
q->head = prev;
}
```
#### 功能: 反轉在 queue 中所有的 list node
* 需注意，除了判斷 queue 是否為 NULL ，也需要判斷該 queue 中是否有 list node
``` c=
if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
return;
```
### Queue sort
``` c=
/*
* Merge two lists in ascending order
* return head of list
*/
list_ele_t *merge(list_ele_t *a, list_ele_t *b)
{
list_ele_t newh;
list_ele_t *current, *head;
newh.next = NULL;
current = head = &newh;
while (a && b) {
int tmp = strcmp(a->value, b->value);
if (tmp > 0) {
current->next = b;
current = current->next;
b = b->next;
} else {
current->next = a;
current = current->next;
a = a->next;
}
current->next = NULL;
}
if (a)
current->next = a;
if (b)
current->next = b;
head = head->next;
return head;
}
/*
* Split list into two lists
* return head of 2nd splited list
*/
list_ele_t *splitList(list_ele_t *head, size_t size)
{
for (size_t halfSize = size / 2; halfSize > 1; halfSize--) {
head = head->next;
}
list_ele_t *tmp = head;
head = head->next;
tmp->next = NULL;
return head;
}
/*
* Do merge sort algorithm
* return head of sorted list
*/
list_ele_t *mergeSort(list_ele_t *head, size_t size)
{
if (size <= 1)
return head;
list_ele_t *node = splitList(head, size);
size_t halfSize = size / 2;
return merge(mergeSort(head, halfSize), mergeSort(node, size - halfSize));
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
return;
q->head = mergeSort(q->head, q->size);
list_ele_t *current = q->head;
while (current->next) {
current = current->next;
}
q->tail = current;
}
```
#### 功能: 依 node 儲存的文字由小到大排列
* 參考 [Linked list sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 之 merge sort 的寫法
* 時間複雜度為 **O(n*logn)**
* 實做時，卡在 merge 的部份，參考 [Merge two sorted linked list](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/) 的 dummy node 的方式後解決
## AddressSanitizer - global buffer overflow
使用 make SANITIZER=1 並 make test ，遇到 global buffer overflow ，發現是關於_Bool (C99 新增) 記憶體位址轉型為 `int *` 存取時所發生的錯誤
* `sizeof(_Bool)`: 1 byte
* `sizeof(int)`: 4 bytes
原先空間只有 1 byte 的 `bool` 型態 ，其記憶體位址轉型成 `int *`，並由 `int *valp` 所指向，造成 `*valp` 存取時比原先多讀取 3 bytes，直接存取記憶體中的其他資料，造成錯誤
### 情境模擬
假如使用以下程式碼進行測試，如果未開啟 AddressSanitizer ，正常情況下也很難察覺會有問題
``` c=
#include <stdio.h>
#include <stdlib.h>
_Bool simulation = 0;
int main(void)
{
int *test = (int *)&simulation; /* it's ok here to do type casting */
int test2 = *test; /* global buffer overflow */
printf("sizeof(bool): %ld, sizeof(int): %ld\n", sizeof(_Bool), sizeof(int));
printf("bool: %d, int: %d\n", simulation, test2);
return 0;
}
```
### 解決方法
1. 改變 `struct PELE` 之儲存方式，改由使用 `void *` 以及 type size
``` c=
struct PELE {
char *name;
void *valp;
size_t valp_size;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
2. 修改 `add_param` 之傳入參數，一樣改成傳入 `void *` 以及 type size
``` c=
void add_param(char *name,
void *valp,
size_t valp_size,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_list;
while (next_param && strcmp(name, next_param->name) > 0) {
last_loc = &next_param->next;
next_param = next_param->next;
}
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
ele->name = name;
ele->valp = valp;
ele->valp_size = valp_size;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
```
3. 新增 `read_valp` 和 `write_valp` function
* 依照 type size 判斷型態，日後也可新增其他型態
* `write_valp` 的 `size` 參數為 value 之大小
``` c=
static int read_valp(void *valp, size_t size)
{
if (size == sizeof(bool))
return *(bool *) valp;
else
return *(int *) valp;
}
static bool write_valp(void *valp, void *value, size_t size)
{
if (!valp || !value)
return false;
memcpy(valp, value, size);
return true;
}
```
4. 原先有用到 param 的 function ，依原本功能比照修改對應程式碼
## Valgrind - massif 視覺化記憶體用量
* 進入qtest初始化後，在 `push_file` function 會先allocate大約 9.9Kib 的空間給 `rio_ptr` 型態的 `rnew` ，如果輸入 `./qtest` 時，沒有輸入 `-f <input_file>` ，就會改成讀取 stdin 的方式，再由 `rio_ptr` 型態的 `buf_stack` 指向 `rnew` ， 呼叫 `readline` function 讀取 `buf_stack->fd` 資料流，讀取 cmd 或 檔案中的指令
* 之後隨著指令執行插入、刪除，由下圖可知輸入 `ih head 20` 時，記憶體用量上升， 輸入 `rhq` 多次，可以看到記憶體用量以階梯式逐漸減少，最後輸入 `free` 時，直接下降到當初初始化完成後的用量，再輸入 `new` 時，圖表顯示微微上升，輸入 `quit` 結束程式並完全釋放
## Dude, is my code constant time?
* TODO
Sign in with Wallet
Connect another wallet