# 2020q3 Homework1 (lab0)
contributed by <`hsiehong`>
###### tags: `進階電腦系統理論與實作`
[作業要求](https://hackmd.io/@sysprog/2020-lab0)
## outline
[TOC]
實做[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c)以下功能
* `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`==: 「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程所新增，以==遞增順序==來排序鏈結串列的元素，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
---
## 開發紀錄
#### `q_new`
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
q->size = 0;
q->head = NULL;
q->tail = NULL;
return q;
}
```
* 若 malloc failed ，return `NULL` pointer
* 初始化 queue
#### `q_free`
```c=
void q_free(queue_t *q)
{
if (q == NULL)
return;
while (q->head) {
list_ele_t *tmp;
tmp = q->head;
q->head = q->head->next;
if (tmp->value)
free(tmp->value);
free(tmp);
}
free(q);
}
```
* 很直覺的方法，要注意每個 node 的 value 也要釋放記憶體
#### `q_insert_head`
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
free(newh);
return false;
}
int len = strlen(s) + 1;
newh->value = (char *) malloc(len * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len);
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
++q->size;
return true;
}
```
* 若 queue is `NULL` , 無法新增，回傳 `NULL` , 若 queue is empty , 更新 `q->head` , `q->tail` , `q->size`
* `newh->value` 要注意是新增 `strlen(s) + 1` 的大小，要保留 `\0` 的空間
* 依據 [CERN Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 建議而移除 strcpy 等不安全的函式 , 這裡使用strncpy()
* line20 原本是要處理 q->size == 0 的情況，後來覺得讀性不是很好，所以改成下面
```c
if (q->size == 0) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
```
:::warning
不懂 line 15，為什麼不是 `free(newh->value)` , 測資會過不了
:::
#### `q_insert_tail`
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt) {
free(newt);
return false;
}
size_t len = strlen(s) + 1;
newt->value = (char *) malloc(len * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, len);
newt->next = NULL;
if (!q->tail) {
q->head = newt;
} else
q->tail->next = newt;
q->tail = newt;
++q->size;
return true;
}
```
* 概念同 `q_insert_head`，換湯不換藥
* 同樣處理 q->size == 0 的特殊狀況且增加可讀性，line19-23 改成下面
```c
if (q->size == 0) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
```
#### `q_remove_head`
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
if (q->head->value)
strncpy(sp, q->head->value, bufsize);
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
--q->size;
return true;
}
```
* 移除當前 head node 並更新 head node，`q->size` - 1
* 若 head node value 不為空，將值複製到 `*sp`
#### `q_size`
```c=
int q_size(queue_t *q)
{
if (q != NULL)
return q->size;
else
return 0;
}
```
#### `q_reverse`
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *curr, *pre, *nxt;
curr = q->head;
pre = NULL;
q->head = q->tail;
q->tail = curr;
while (curr) {
nxt = curr->next;
curr->next = pre;
pre = curr;
curr = nxt;
}
}
```
* 參考[文章](https://www.geeksforgeeks.org/reverse-a-linked-list/)作法
* 若 queue 為 `NULL` 或 empty 不用動作
#### `q_sort`
```c=
void q_sort(queue_t *q)
{
if (!q || q->size == 1)
return;
list_ele_t *curr, *pre, *tmp, *tail;
tail = NULL;
while (q->head != q->tail) {
curr = pre = q->head;
while (curr && curr->next && curr->next != tail) {
if (strcmp(curr->value, curr->next->value) > 0) {
tmp = curr->next;
curr->next = tmp->next;
tmp->next = curr;
if (curr == q->head) {
q->head = tmp;
pre = tmp;
} else {
pre->next = tmp;
pre = pre->next;
}
} else {
if (curr != q->head)
pre = pre->next;
curr = curr->next;
}
}
tail = curr;
}
}
```
* 參考 [文章](https://npes87184.github.io/2015-09-12-linkedListSort/) 作法，這裡選擇 [bubble sort](https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F)，不過不意外測資全過不了 (TLE) QQ
依據上面程式碼第一次跑完的成績，有排序的部份都沒過
`--- TOTAL 71/100`
----
改成 [merge sort](https://en.wikipedia.org/wiki/Merge_sort)，也是參考上篇[文章](https://npes87184.github.io/2015-09-12-linkedListSort/)作法
```c=
list_ele_t *merge_2_list(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *n_head = NULL;
list_ele_t **tmp = &n_head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) > 0) {
*tmp = l2;
l2 = l2->next;
} else {
*tmp = l1;
l1 = l1->next;
}
tmp = &((*tmp)->next);
}
if (l1)
*tmp = l1;
else
*tmp = l2;
return n_head;
}
```
* 參考 [`ZhuMo`](https://hackmd.io/@cccccs100203/linux2020-lab0) 同學的，使用到 pointer to pointer
```c=+
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast, *slow;
fast = head->next;
slow = head;
// split list into 2 half list
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
slow = head;
list_ele_t *left = merge_sort(slow);
list_ele_t *right = merge_sort(fast);
return merge_2_list(left, right);
}
```
```c=+
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
// sorting by merge sort
q->head = merge_sort(q->head);
q->tail = q->head;
while (q->tail && q->tail->next)
q->tail = q->tail->next;
}
```
* 排序完得更新新的 `q->tail`
* 大多數測資都能通過 `--- TOTAL 94/100`
## Valgrind 記憶體分析
執行 `make valgrind`
結果：`--- TOTAL 94/100`
問題在 test06
```
+++ TESTING trace trace-06-string:
# Test of truncated strings
```
錯誤訊息如下
```
==7368== 32 bytes in 1 blocks are still reachable in loss record 1 of 30
==7368== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7368== by 0x10B490: malloc_or_fail (report.c:189)
==7368== by 0x10BFA2: add_cmd (console.c:123)
==7368== by 0x10C083: init_cmd (console.c:93)
==7368== by 0x10ACAC: main (qtest.c:759)
```
* 看到 `truncated strings`，直覺告訴我是 remove head 的部份出問題了，回去看了一次程式碼如下，還有 spec ，發現是字串結尾沒有忘記加上 `null terminator`
```c
if (!q || !q->head)
return false;
if (q->head->value)
strncpy(sp, q->head->value, bufsize);
else
return false;
```
修改如下
```c
if (!q || !q->head)
return false;
if (q->head->value) {
strncpy(sp, q->head->value, bufsize-1);
sp[bufsize - 1] = '\0';
} else
return false;
```
test06過了，但換 test09 錯誤如下
```
# Test remove_head with NULL argument
==9611== Invalid write of size 1
==9611== at 0x4C3331F: __strncpy_sse2_unaligned (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9611== by 0x10CD7A: strncpy (string_fortified.h:106)
==9611== by 0x10CD7A: q_remove_head (queue.c:124)
==9611== by 0x109F10: do_remove_head_quiet (qtest.c:430)
==9611== by 0x10B992: interpret_cmda (console.c:220)
==9611== by 0x10BF06: interpret_cmd (console.c:243)
==9611== by 0x10C4D4: cmd_select (console.c:569)
==9611== by 0x10C71C: run_console (console.c:628)
==9611== by 0x10AE41: main (qtest.c:772)
==9611== Address 0x0 is not stack'd, malloc'd or (recently) free'd
```
原來沒注意到 `sp` 也有可能是 `NULL`，判斷條件補上
```c
...
if (q->head->value && sp)
...
```
這樣就沒問題了
```
--- TOTAL 100/100
```
## Massidf 視覺化記憶體使用量
`$ valgrind --tool=massif ./qtest`
利用第 16 筆測資來做範例，測試腳本如下
```
# 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 0
new
ih RAND 10000
sort
reverse
sort
free
new
ih RAND 50000
sort
reverse
sort
free
new
ih RAND 100000
sort
reverse
sort
free
```
```
$ valgrind --tool=massif ./qtest < traces/trace-16-perf.cmd
```
```
$ massif-visualizer massif.out.<PID>
```
* 可以看到 `memory heap consumption` 的使用量是隨著 item 的數目升高的，並且可以看到每次 free 完 queue 記憶體幾乎都會被釋放，但有個問題是第一次釋放完跟第二次釋放完 queue 記憶體並不是回到相同的狀態，這部份還不知道怎麼回事。而程式結束時 `memory heap consumption` 也隨著歸零
## TODO :
* ~~Valgrind 記憶體分析~~
* ~~Massif 視覺化記憶體使用量~~
* 設計相關實驗，查看記憶體使用狀態
* 論文閱讀 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
Sign in with Wallet
Connect another wallet