# 2020q1 Homework1 (lab0)
contributed by < `Gorilla0823` >
## 實驗環境
```shell
$ uname -a
Linux 5.3.0-28-generic Linux ubuntu 4.15.0-51-generic #55-Ubuntu SMP Wed May 15 14:27:21 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
```
## 作業要求
- 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式
- 修改排序所用的比較函式，變更為 `natural sort`，在 “simulation” 也該做對應的修改，得以反映出 `natural sort` 的使用。
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 :arrow_forward: 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
## 開發過程
### queue.h
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t;
```
根據作業要求，增加了 `size` 來記錄 queue 的大小以及 `tail` 指向 queue 中的最後一個元素。
:::warning
考量點為何？考慮到 side effect 嗎？你需要探討
:notes: jserv
:::
> 考量點如下：
不加 `q_size` 的話就需要花費 $O(N)$，因為作業要求 $O(1)$。 [name=gorilla]
### queue.c
#### q_new
- 建立一個空的 queue
- 當 `malloc` 失敗時需要回傳 `NULL`
```cpp
queue_t q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return NULL;
}
q->tail = NULL;
q->head = NULL;
q->size = 0;
return q;
}
```
1. 將 `tail` 及 `head` 指向 `NULL`
2. 將 queue `size` 設為 `0`
#### q_size
- 回傳 queue 的元素數量
- queue 為 `NULL` 時 return `0`
```cpp
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
```
:::warning
考慮以下改寫:
```cpp
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
:notes: jserv
:::
> 已修改，謝謝老師。 [name=gorilla]
#### q_free
- 釋放 queue 所占用的記憶體
- 當 queue 為 `NULL` 時，直接回傳
```cpp
void q_free(queue_t *q)
{
if (!q) {
return;
}
list_ele_t *tmp = NULL;
while (q->head) {
tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
q->tail = NULL;
q->head = NULL;
q->size = 0;
free(q);
}
```
1. 設立 1 個指向 `NULL` 的 `list_ele_t` 結構，從 `head` 刪到 `tail` ，並且 `free` 掉每個 Node 及其包含的字串。
2. 將 `tail` 及 `head` 指向 `NULL` ，並且將 queue 的 `size` 歸 `0` 。
#### q_insert_head
- 從 queue 的 `head` 插入一個元素
- 當 queue 為 NULL 或 `malloc` 失敗時 回傳 false
- `*s` 指向要被插入的元素
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q) {
return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
size_t length = strlen(s);
char *str = malloc(length + 1);
if (newh && str) {
strncpy(str, s, length);
str[length] = '\0';
newh->value = str;
newh->next = q->head;
q->head = newh;
if (!q->tail) {
q->tail = newh;
}
q->size++;
return true;
} else {
free(newh);
free(str);
return false;
}
}
```
1. 這個部分修改了很多次，原本採用 `strcpy` 來複製欲新增的元素，因為 Git pre-commit hook 的檢查機制警告這種行為會造成 buffer overrun ，所以改為 `strncpy` 。
2. 剛開始以為 `malloc` 失敗只會回傳 `NULL` pointer， 查了資料後發現也會回傳 `non-null` pointer ， 所以改用 `if-else`來回收記憶體。
經過查詢[Linux man page](https://linux.die.net/man/3/malloc)後得知其對於`malloc` 回傳值的敘述如下：
> The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().
#### q_insert_tail
- 從 queue 的 `tail` 新增元素
- 如果成功新增則回傳 `true`
- 若 queue 為 `NULL` 或配置記憶體失敗時則回傳 `false`
- `*s` 指向要被插入的元素
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q || !q->head) {
return false;
}
list_ele_t *tmp = q->head;
if (sp) {
memset(sp, 0, bufsize);
strncpy(sp, tmp->value, bufsize - 1);
}
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
此 function 與 `insert_head` 類似。
#### q_remove_head
- 將 queue 從 `head` 刪除
- 如果成功刪除則回傳 `true`
- 當 queue 為空或為 `NULL` 時回傳 `false`
- 若 `sp` 是 `non-NULL` 且一個元素被刪除時，複製被刪除的元素到 `*sp` 中。( 上限為 `bufsize-1`並且 `*sp` 的最後一位須為 null terminator。 )
- 被 list 元素使用的記憶體及其字串需要被 `free`。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
list_ele_t *tmp = q->head;
if (sp) {
memset(sp, 0, bufsize);
strncpy(sp, tmp->value, bufsize - 1);
}
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
#### q_reverse
- 將 queue 的元素反轉
- queue 為 `NULL` 或 `empty` 時直接回傳
- 不可配置新的記憶體位址和 `free` 原有的記憶體位址
``` cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
list_ele_t *curr = q->head, *prev = NULL, *next = NULL;
q->tail = q->head;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->head = prev;
}
```
1. 設定 `1` 個分別指向 `head` 的 `*curr` 及 `2` 個指向 `NULL` 的 `prev` 和 `next`，並將 `head` 指向 `tail` 。
2. 接著從 `head` 走到 `NULL` ，過程中運用 pointer 將 queue 轉向。
3. 最後將 `head` 指向 `*prev` 。
#### q_sort
- 將 queue 中元素小到大做排序
- 如果 queue 是 `NULL` 或 `empty`，直接回傳。
- 如果 queue 裡面只有 `1` 個元素，不做任何動作。
- 使用 natural sort ( 額外新增 )
``` cpp
void q_sort(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
q->head = mergeSortList(q->head);
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
```
1. 將 `mergeSortList` function sort 的結果傳給 `head`。
2. 移動至 `tail` 並設立 `tail` 。
#### merge 和 mergeSortList
``` cpp
#include "natsort/strnatcmp.c"
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (strnatcmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
return merge(l1, l2);
}
```
:::warning
`merge` 和 `mergeSortList` 這兩個函式都僅限於同一個 C 程式碼中使用，應該在宣告加註 `static`，使其 visibility 不會變為公開可見 (exposed)，也有利編譯器施加更多最佳化。
:notes: jserv
:::
>已修改，謝謝老師。[name=gorilla]
採用 merge sort 進行排序，實作的部份參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)；比較字串部分採用 [natsort](https://github.com/sourcefrog/natsort)。
目前得分如下：
```
scripts/driver.py
--- 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-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 0/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 94/100
```
#### Revised q_sort
#### mergeSortList
```cpp=
static list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *temp = NULL;
list_ele_t **p = &temp;
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
*p = l1;
l1 = l1->next;
} else {
*p = l2;
l2 = l2->next;
}
p = &(*p)->next;
}
if (l1)
*p = l1;
if (l2)
*p = l2;
return temp;
}
```
1. 發現在 ` traces/trace-015-ops.cmd` 內 insert 大量的字串後做 sort ，所以更改了判斷方式。
#### mergeSortList
```cpp=
static list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
return merge(l1, l2);
}
```
```
gorilla@ubuntu:~/Desktop/linux2020/lab0-c$ make test
scripts/driver.py
--- 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-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 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
```
雖然說可以拿到100分了，但是有時候 `trace-15-perf` 會 `TLE` 變成 94 分，方法還有待
改進。
## 遇到的問題
### 1. Permission denied
不知道為什麼每次都要 `sudo make install`，改了幾次資料夾權限( `sudo chmod -R 777 lab0-c` )放久了又會出現如下的敘述：
```
gorilla@ubuntu:~/Desktop/linux2020/lab0-c$ make test
CC queue.o
queue.c:288:1: fatal error: opening dependency file .queue.o.d: Permission denied
}
```
:::warning
因為你之前用了 superuser 的權限來編譯或測試本程式，先試著移除編譯過程中所產生的 `*.o.d` 檔案 (順便思考其作用)，然後回到一般使用者的權限來開發。養成好習慣，從正確地使用權限開始。
:notes: jserv
:::
> 謝謝老師的建議。
> ~~根據 [stack overflow](https://stackoverflow.com/questions/6642137/why-when-do-i-need-a-clean-target) 上的這篇文章以及 [GNU Make](http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/) 的內容提到避免在未將編譯過程所產生的`*.o .d` 檔案清除前執行 `make` ，會造成某些功能與舊版本不相容。~~
[name=gorilla]
:::danger
請仔細看 stackoverflow 上的討論，絕對不是「某些功能與舊版本不相容」，依據原本討論脈絡，是指 symbol / exposed function (不可翻譯為「功能」)。
:notes: jserv
:::
> 已修改，謝謝老師。
>
> 根據 [stack overflow](https://stackoverflow.com/questions/6642137/why-when-do-i-need-a-clean-target)上的這篇文章， `make clean` 會刪除所有在此期間建立的 **object files** ， 如果絕對的安全，必須在 `make` 前執行 `make clean` 。
>
> 如果在從未執行 `make clean` 下 （ 保留舊有的 object file ) 可能會造成一些問題，假設已經存在 1 個 object file 且他與某些先前版本的 library 做鏈結 （ linked againast previous version of some library ) 。
>
>而當你更新這些 library 到較新的版本後， 但是其中有一些 function 與舊版本的不兼容 ( incompatible ) ，此時你的 object file 期望使用舊的版本，導致鏈結過程（ linking process ) 失敗。
>[name=gorilla]
### 2. 無法執行 `make valgrind`
```
gorilla@ubuntu:~/Desktop/linux2020/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/gorilla/Desktop/linux2020/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/gorilla/Desktop/linux2020/lab0-c'
cp qtest /tmp/qtest.xP2SMu
chmod u+x /tmp/qtest.xP2SMu
sed -i "s/alarm/isnan/g" /tmp/qtest.xP2SMu
scripts/driver.py -p /tmp/qtest.xP2SMu --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-01-ops.cmd' failed: [Errno 2] No such file or directory
--- trace-01-ops 0/6
+++ TESTING trace trace-02-ops:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-02-ops.cmd' failed: [Errno 2] No such file or directory
--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-03-ops.cmd' failed: [Errno 2] No such file or directory
--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-04-ops.cmd' failed: [Errno 2] No such file or directory
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-05-ops.cmd' failed: [Errno 2] No such file or directory
--- trace-05-ops 0/5
+++ TESTING trace trace-06-string:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-06-string.cmd' failed: [Errno 2] No such file or directory
--- trace-06-string 0/6
+++ TESTING trace trace-07-robust:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-07-robust.cmd' failed: [Errno 2] No such file or directory
--- trace-07-robust 0/6
+++ TESTING trace trace-08-robust:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-08-robust.cmd' failed: [Errno 2] No such file or directory
--- trace-08-robust 0/6
+++ TESTING trace trace-09-robust:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-09-robust.cmd' failed: [Errno 2] No such file or directory
--- trace-09-robust 0/6
+++ TESTING trace trace-10-malloc:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-10-malloc.cmd' failed: [Errno 2] No such file or directory
--- trace-10-malloc 0/6
+++ TESTING trace trace-11-malloc:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-11-malloc.cmd' failed: [Errno 2] No such file or directory
--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-12-malloc.cmd' failed: [Errno 2] No such file or directory
--- trace-12-malloc 0/6
+++ TESTING trace trace-13-perf:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-13-perf.cmd' failed: [Errno 2] No such file or directory
--- trace-13-perf 0/6
+++ TESTING trace trace-14-perf:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-14-perf.cmd' failed: [Errno 2] No such file or directory
--- trace-14-perf 0/6
+++ TESTING trace trace-15-perf:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-15-perf.cmd' failed: [Errno 2] No such file or directory
--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-16-perf.cmd' failed: [Errno 2] No such file or directory
--- trace-16-perf 0/6
+++ TESTING trace trace-17-complexity:
Call of 'valgrind /tmp/qtest.xP2SMu -v 1 -f ./traces/trace-17-complexity.cmd' failed: [Errno 2] No such file or directory
--- trace-17-complexity 0/5
--- TOTAL 0/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.xP2SMu --valgrind -t <tid>
```
已確認過 valgrind 可正常執行（ 測試方式：[抓漏 - 使用valgrind檢查C語言memory Leak](http://wen00072.github.io/blog/2014/11/29/catching-leakage-use-valgrind-checking-c-memory-leak/) ) 。
## 參考資料
* [2020 春季 lab0c 作業說明](https://hackmd.io/@sysprog/linux2020-lab0)
* [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [Why/when do I need a 'clean' target?](https://stackoverflow.com/questions/6642137/why-when-do-i-need-a-clean-target)
* [ Auto-Dependency Generation ](http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/)
* [抓漏 - 使用valgrind檢查C語言memory Leak](http://wen00072.github.io/blog/2014/11/29/catching-leakage-use-valgrind-checking-c-memory-leak/)
Sign in with Wallet
Connect another wallet