# 2020q3 Homework1 (lab0)
contributed by < `Holychung` >
[2020q3 Homework1 (lab0) 題目](https://hackmd.io/@sysprog/2020-lab0)
## Outline
[TOC]
## 開發環境
```shell
$ uname -a
Linux holy-VirtualBox 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 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.
```
## 作業要求
詳細閱讀 [C Programming Lab ](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
* `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`: 以==遞增順序==來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;
## 開發過程
### `queue.h`
要在 $O(1)$ 內完成 `q_insert_tail` 與 `q_size` 的話，必須在 `queue_t` 中加入 `size` 與 `tail`。
```c
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### `queue.c`
#### q_new
* Create empty queue
* Return NULL if could not allocate space
```c
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### q_free
* Free all storage used by queue
```c
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *target = q->head;
while (target) {
q->head = target;
target = target->next;
free(q->head->value);
free(q->head);
}
free(q);
}
```
#### q_insert_head
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *new;
new = malloc(sizeof(list_ele_t));
if (!new)
return false;
/* Allocate space for the string and copy it */
new->value = malloc(sizeof(char) * (strlen(s) + 1));
if (new->value == NULL) {
free(new);
return false;
}
memset(new->value, '\0', strlen(s) + 1);
strncpy(new->value, s, strlen(s));
/* Insert element to head */
new->next = q->head;
q->head = new;
if (q->tail == NULL)
q->tail = new;
q->size += 1;
return true;
}
```
#### q_insert_tail
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *new;
new = malloc(sizeof(list_ele_t));
if (!new)
return false;
/* Allocate space for the string and copy it */
new->value = malloc(sizeof(char) * (strlen(s) + 1));
if (new->value == NULL) {
free(new);
return false;
}
memset(new->value, '\0', strlen(s) + 1);
strncpy(new->value, s, strlen(s));
new->next = NULL;
/* Insert element to tail */
if (q->tail == NULL) {
q->tail = new;
q->head = new;
} else {
q->tail->next = new;
q->tail = new;
}
q->size += 1;
return true;
}
```
#### q_remove_head
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
* The space used by the list element and the string should be freed.
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
/* Copy the removed string to *sp */
if (sp) {
size_t head_size = strlen(q->head->value);
size_t size = head_size > bufsize - 1 ? bufsize - 1 : head_size;
strncpy(sp, q->head->value, size);
sp[size] = '\0';
}
/* Remove head element */
list_ele_t *tmp = q->head;
q->head = tmp->next;
if (q->head == NULL) {
/* Queue is empty after removing */
q->tail = NULL;
}
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
```
#### q_size
* Return number of elements in queue.
* Return 0 if q is NULL or empty
```c
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
#### q_reverse
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
```c
void q_reverse(queue_t *q)
{
if (!q || q->size == 0 || q->size == 1)
return;
list_ele_t *prev_ele = NULL;
list_ele_t *current_ele = q->head;
list_ele_t *next_ele;
q->tail = q->head;
while (current_ele) {
next_ele = current_ele->next;
current_ele->next = prev_ele;
prev_ele = current_ele;
current_ele = next_ele;
}
q->head = prev_ele;
}
```
#### q_sort
為了達到時間複雜度 $O(NlogN)$，參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 使用 Merge Sort，排序的過程中把 q->head 指向最左邊的位置，排序完後也需額外尋找尾端來更新。
* 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.
```c
void merge_sort(list_ele_t **head)
{
if (*head == NULL || (*head)->next == NULL)
return;
/* Partition */
list_ele_t *slow = *head;
list_ele_t *fast = (*head)->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
slow = *head;
merge_sort(&slow);
merge_sort(&fast);
/* Start merge elements of queue in ascending order */
list_ele_t *prev;
if (strcmp(slow->value, fast->value) < 0) {
prev = slow;
slow = slow->next;
} else {
prev = fast;
fast = fast->next;
}
/* Find queue head */
*head = prev;
/* Merge elements of queue in ascending order */
while (slow && fast) {
if (strcmp(slow->value, fast->value) < 0) {
prev->next = slow;
prev = slow;
slow = slow->next;
} else {
prev->next = fast;
prev = fast;
fast = fast->next;
}
}
prev->next = slow ? slow : fast;
}
void q_sort(queue_t *q)
{
if (!q || q->size == 0 || q->size == 1)
return;
merge_sort(&q->head);
/* Find queue tail */
while (q->tail->next)
q->tail = q->tail->next;
}
```
## Valgrind
使用 [Valgrind](https://valgrind.org/) 動態程式分析工具，對記憶體進行分析和除錯，使用方式如下。
```
$ valgrind --tool=<toolname> <program>
```
lab0 已整合 Valgrind 找出記憶體相關的問題，使用方式如下
```
$ make valgrind
```
程式輸出
```
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/holy/linux2020/lab0-c'
.
.
scripts/driver.py -p /tmp/qtest.cduVEu --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
(略)
+++ TESTING trace trace-16-perf:
# 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
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.cduVEu --valgrind -t <tid>
```
### massif
搭配記憶體分析工具 Massif 使用，Massif 是一個 heap profiler，可以追蹤程式使用 heap memory 的狀況，使用方式如下，更細節可以參考 [User Manual](https://valgrind.org/docs/manual/ms-manual.html) 操作。
```
$ valgrind --tool=massif <program>
```
執行完後，當前目錄底下會出現 massif.out.<執行程式 PID>， 透過 `ms_print` 顯示分析結果。若程式有正確釋放記憶體，會看到最終記憶體使用量會回到 0。
```
$ ms_print massif.out.<執行程式 PID>
```
Massif starts by taking snapshots for every heap allocation/deallocation
然後 snapshots 又分三種：
- `:` Normal snapshot
- `@` Detail snapshot
- `#` Peak snapshot
### massif-visualizer
相比 ms_print，[massif-visualizer](https://kde.org/applications/en/massif-visualizer) 有圖形化的介面更方便分析，不過需要額外安裝
```
$ sudo apt-get install -y massif-visualizer
```
使用方式如下
```
$ massif-visualizer massif.out.<執行程式 PID>
```
### 設計實驗
假設在 `q_free` 當中忘記把 q->head->value 給釋放掉，就會造成 memory leak
```diff=
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *target = q->head;
while (target) {
q->head = target;
target = target->next;
- free(q->head->value);
+ // free(q->head->value);
free(q->head);
}
free(q);
}
```
```
$ valgrind --tool=massif ./qtest -f traces/trace-16-perf.cmd
```
可以明顯看出最後的記憶體沒有完全釋放掉，接下來使用 `make valgrind` 來觀察，可以看到很多記憶體 still reachable，代表程式結束時有未釋放的記憶體，不過卻還有指標指著。
```
+++ TESTING trace trace-16-perf:
# 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
ERROR: Freed queue, but 10000 blocks are still allocated
ERROR: Freed queue, but 60000 blocks are still allocated
ERROR: Freed queue, but 160000 blocks are still allocated
==29127== 4 bytes in 1 blocks are still reachable in loss record 1 of 29
==29127== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29127== by 0x5277A29: strdup (strdup.c:42)
==29127== by 0x10F285: linenoiseHistoryAdd (linenoise.c:1236)
==29127== by 0x10FE3B: linenoiseHistoryLoad (linenoise.c:1325)
==29127== by 0x10B48F: main (qtest.c:769)
==29127==
==29127== 32 bytes in 1 blocks are still reachable in loss record 2 of 29
==29127== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29127== by 0x10BB12: malloc_or_fail (report.c:189)
==29127== by 0x10C55A: add_cmd (console.c:127)
==29127== by 0x10C63B: init_cmd (console.c:96)
==29127== by 0x10B30C: main (qtest.c:762)
==29127==
```
## 研讀論文 Dude, is my code constant time?
[論文閱讀：Dude, is my code constant time?](https://hackmd.io/@Holy/BkwZl273w)
## linenoise
參照 [antirez/linenoise](https://github.com/antirez/linenoise) 改善 `qtest` 命令列。
[研讀筆記 linenoise](https://hackmd.io/@Holy/Syc2IgUnv)
### 強化 `qtest` 命令列功能
linenoise 的 API 相當的完善，可以直接應用到 `qtest` 當中，不過我 fork 作業的時候(9/18 以後)老師已經把 linenoise 整合 merge 進去，所以看到的 code 是已經整合過的>< 不過底下還是稍微提一下 trace 的過程。
先找到 `qtest.c` main function 裡面，找到 `run_console` 的地方，再到 `console.c` 看到這個函式，`run_console` 有呼叫到 `readline` 這個函式，把這邊替換成 linenoise 的 API。
```cpp=
while (!block_flag && read_ready()) {
cmdline = readline();
interpret_cmd(cmdline);
prompt_flag = true;
}
```
```cpp=
while (!has_infile && !block_flag &&
(cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
prompt_flag = true;
linenoiseFree(cmdline);
}
```
#### completion
一樣在啟動時要先註冊 callback function，然後這邊會用 `cmd_list` 去記下輸入過的 command，用 `cmd_maybe` 去跟現在 buf 的字串比對，如果比對相似就會呼叫 `linenoiseAddCompletion`。
#### history
這邊在一開始呼叫 `linenoiseHistoryLoad` 去讀實體的檔案 `.cmd_history`，再直接呼叫 linenoise 的 API，每次輸入指令後就加入 history 並且儲存到 `HISTORY_FILE` 當中。
```cpp=
#define HISTORY_FILE ".cmd_history"
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
## TODO
:::info
TODO
- AddressSanitizer
- 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)
:::
Sign in with Wallet
Connect another wallet