# 2020q3 Homework1 (lab0)
contributed by < `justapig9020` >
###### tags: `sysprog2020`
## Outline
[TOC]
## Link
[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
[lab-0](https://hackmd.io/@sysprog/2020-lab0)
[作業區](https://hackmd.io/@sysprog/2020-homework1)
## 作業要求
* [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* [x] ==詳細閱讀 [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" 過程中的記憶體使用量，需要設計對應的
## 環境
```shell
~ uname -r
5.4.0-45-generic
~ 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.
```
## lab0 實作
### main structure
```cpp=
/* Linked list element (You shouldn't need to change this) */
typedef struct ELE {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t **tail;
size_t size;
} queue_t;
```
在結構部分，於 `queue_t` 中新增兩成員， `tail` 、 `size` 。
上述兩成員變數將會在後續用到的時候討論。
在使用 `struct` 的成員變數此一用詞時，突然發現自己只能肯定此用法在 `cpp` `class` 的狀況下正確，然而並不肯定可以使用於 `c` `struct` 的情況下。
既然有問題只好學學大文豪查字典了。
:::info
以下節錄自 c99 commit draft
a ==member== of a structure, union, or enumeration
:notebook: 6.2.1
A structure or union shall not contain a ==member== with incomplete or function type
:notebook: 6.7.2.1
由於與 `staruct` 相關章節中多次使用 ==member== 一詞，因此認定
:::
### new
```cpp=
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->size = 0;
q->head = NULL;
q->tail = &q->head;
return q;
}
```
本 function 實作只需考慮 `queue` malloc 失敗的情況。
根據 [男人](https://man7.org/linux/man-pages/man3/malloc.3.html) ， ` On error, these functions return NULL.` ， `malloc` 再失敗時會返回 `NULL` ，透過判斷回傳值來迴避失敗的情況。
其餘的部分依照題目需求來初始化數值，其中為了滿足 `size` 以及 `insert tail` O(1) 的要求，新增變數 `size` 、 `tail` ，兩者分別紀錄 `queue` 當前節點個數以及 `指向最後一個節點的指標的指標` ，亦即指向倒數第二節點 `next` 成員的指標。
關於 `tail` 的設計思考，未來有時間再新增篇幅討論。
### free
```cpp=
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *buf = q->head;
q->head = buf->next;
free(buf->value);
buf->value = NULL;
free(buf);
}
free(q);
}
```
:::info
依據理解以及與友人的討論得出 - 為避免資安上 `uaf` 以及 `double free` 的風險，被 free() 的指標應該被立即 assign 成 `NULL` 的結論。
然而在 `free(q);` 後加上 `q = NULL;` 則會導致 `pre-commit` 失敗。
```shell
queue.c:67:5: warning: Assignment of function parameter has no effect outside the function. Did you forget dereferencing it? [uselessAssignmentPtrArg]
q = NULL;
```
:::
首先檢查 `q` 是否存在，若存在則利用 `q->head` 作為 buffer 將整個 `queue` 從頭清空。
其中 `list_ele_t` 中的成員 `value` 是指向 `char` 的指標，須在 `free` 整個節點前先行將其 `free` 。
在實作此函數時重新思考了自己對 `malloc` 、 `free` 的認知。主要思考議題如下。
1. 若 `malloc` 嘗試分配 size 為 `0` 的空間時行為為何。
2. 若嘗試 `free` 上述空間時會發生什麼狀況。
根據[男人](https://man7.org/linux/man-pages/man3/malloc.3.html)敘述 `If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().` 可得知上述兩問題之解答。
1. Size 為 0 的 `malloc` 基本上會回傳 NULL。
2. 即便並非回傳 NULL ，這個回傳過後的位址依然可以被正常 `free` 。
綜上所述，在 `malloc` 時需要考慮回傳為 `NULL` 的情況，以及在有可能 `malloc` size 為 0 的空間時，要注意不要在 size 為 0 的情況下讀寫該記憶體位址。
### size
```cpp=
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
透過在 `queue_t` 中新增成員變數 `size` 來紀錄當前結點個數，以達成 O(1) 之複雜度要求。
每逢新增刪除都需要對應的加減 `size`。
### insert head
```cpp=
static list_ele_t *new_ele(char *s)
{
list_ele_t *newE = malloc(sizeof(list_ele_t));
if (!newE)
goto fail;
size_t len = strlen(s) + 1;
newE->value = malloc(len);
if (!newE->value)
goto freeEle;
strncpy(newE->value, s, len);
newE->next = NULL;
return newE;
freeEle:
free(newE);
newE = NULL;
fail:
return NULL;
}
```
首先考量之後還有其他 insert 系列 function 因此實作了一個靜態函數 `new_ele` 來提昇代碼的重用性。
判斷各個 `malloc` 的成功與否，並透過 `goto` 的方式構成一個類似於 `try catch` 的架構。實作此架構是為了確保任意的錯誤都能在返回前妥善的處理已經取用的資源。
此外需要注意的是，根據[男人](https://www.man7.org/linux/man-pages/man3/strlen.3.html)所述， ` The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').` ， strlen 並不會包含 '\0' 因此在記憶體分配上需要將此數值加一以確保獲得的記憶體有足夠的空間保存 '\0' 。
```cpp=
/*
* 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.
*/
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
newh = new_ele(s);
if (!newh)
return false;
newh->next = q->head;
q->head = newh;
if (*q->tail == q->head)
q->tail = &q->head->next;
q->size += 1;
return true;
}
```
透過 `new_ele` 函數生成新節點，透過回傳值判斷新節點是否有成功建立。
將新節點插入 queue 的 `head` ，並考慮當前 queue 為空時，要設定 `tail` 指向當前節點的成員變數 `next` 。
### remove head
```cpp=
/*
* 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.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *buf = q->head;
if (&q->head->next == q->tail)
q->tail = &q->head;
q->head = q->head->next;
q->size -= 1;
if (sp) {
strncpy(sp, buf->value, bufsize);
sp[bufsize - 1] = '\0';
}
free(buf->value);
buf->value = NULL;
free(buf);
return true;
}
```
### insert tail
```cpp=
/*
* 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.
*/
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newE = new_ele(s);
if (!newE)
return false;
*q->tail = newE;
q->tail = &newE->next;
q->size += 1;
return true;
}
```
重複使用 `new_ele` 新增節點，由於 `tail` 為指向最後一個節點的 `next` 的指標，因此在 insert tail 的操作不用將 `queue` 為空時視為特殊狀況，可以直接更新。
### reverse
```cpp=
/*
* 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.
*/
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *ptr = q->head;
list_ele_t *prev = NULL;
q->tail = &ptr->next;
while (ptr) {
list_ele_t *next = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = next;
}
q->head = prev;
}
```
使用 `prev` `ptr` `next` 三個指標進行節點反轉作業。
`prev` 用以保存前一個指標，在反轉後他將會成為 `ptr` 節點的 `next`。
`ptr` 指向當前操作的節點。
`next` 則指向原本的下一個節點，以確保 `ptr` 在其成員變數 `next` 更新後仍可以順利前往原本的下一節點。
### half
``` cpp=
static list_ele_t **find_mid_ele(list_ele_t **head)
{
list_ele_t **faster = head;
list_ele_t **slower = head;
while (*faster && (*faster)->next) {
slower = &(*slower)->next;
faster = &(*faster)->next->next;
}
return slower;
}
void q_half(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t **ptr = find_mid_ele(&q->head);
printf("%s\n", (*ptr)->value);
}
```
首先再實作 `sort` 前，先實作 `half` 來找出 `queue` 的中間點 (實際上為 $n/2+1$ )。
藉由 2:1 的快慢指標找出 queue 的中間節點。
`find_mid_ele` 考量到後續操作實際上同時也需要改變 $n/2$ 的 `next`， 因此返回值為指標的指標。
### sort
:::info
在實作時一度困惑於如何決定排序之順序，最後參考 [ZhuMon](https://hackmd.io/@ZhuMon/lab0-c) 的開發紀錄才發現是使用 `strcmp` 作為排序依據。在文件上是否有需要對於排序依據有更清楚的指示？
:::
Sort 的實現參考 [linked list sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 使用 `merge sort` 作為排序演算法，並拆分成三個部分進行。
```cpp=
/*
* 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.
*/
static list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t **ptr = find_mid_ele(&head);
list_ele_t *mid = *ptr;
*ptr = NULL;
head = merge_sort(head);
mid = merge_sort(mid);
list_ele_t *mergered = NULL;
ptr = &mergered;
while (head && mid) {
list_ele_t *smeller;
if (strcmp(head->value, mid->value) > 0) {
smeller = mid;
mid = mid->next;
} else {
smeller = head;
head = head->next;
}
*ptr = smeller;
ptr = &(*ptr)->next;
}
while (head) {
*ptr = head;
head = head->next;
ptr = &(*ptr)->next;
}
while (mid) {
*ptr = mid;
mid = mid->next;
ptr = &(*ptr)->next;
}
*ptr = NULL;
return mergered;
}
void q_sort(queue_t *q)
{
if (!q || !q->head)
return;
q->head = merge_sort(q->head);
while (*q->tail) {
q->tail = &(*q->tail)->next;
}
}
```
首先透過 `find_mid_ele` 找到指向中間節點的指標的指標。透鍋該指標可以便利的找出後半截 `queue` 的起始節點位址以及改動前半截 `queue` 的最後一個 `next` 為 `NULL` 以分割 `queue` 。
如同常規的 `merge sort` 藉由遞迴的方式將 `queue` 分割至最小單位，並依照大小逐一重組。
透過參考 [ZhuMon](https://hackmd.io/@ZhuMon/lab0-c#%E5%AF%A6%E4%BD%9C%E6%B5%81%E7%A8%8B) 的實作，改進忽略 linked list 特性，而歷遍已經串好的串列。並且修復 `tail` 指向錯誤位址的 bug 。
## Valgrind 分析
首先透過 `Valgrind` 逐一測試 `trace` 的測試腳本，發現以下腳本會發生警告。
1. **13**
```
# Test performance of insert_tail
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000
reverse
it jaguar 1000
```
發生 memory leak 。
2. **14**
```
# Test performance of size
option fail 0
option malloc 0
new
ih dolphin 1000000
size 1000
```
發生 memory leak 。
3. **15**
```
# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000
```
Valgrind 發生 `core dumped` 。
---
透過 `masasif` 產生 log 並藉由 `massif-visualizer` 視覺化，產生以下圖表(下圖為 `trace-13` 所產生的圖表)。
比對圖表與腳本後可以發現，在程式結束前，有大量的記憶體未被施放。而這歇腳本的共通點皆為未在最後執行 `free` 命令。
原本推測是 `qtest` 中並未在結束前檢查並施放記憶體，然而發現實際上在 `main` 裡就會透過 `add_quit_helper` 將 `queue_quit` (其中會引用 q_free() ) 存入 function pointer array `quit_helpers` ，最終在處理 `quit` 指令會依序執行 `quit_helper` 中的函數。
### qtest
Sign in with Wallet
Connect another wallet