# 2021q1 Homework1 (lab0)
contributed by < `jonathanyang0227` >
## Week 1
- [ ] 透過 Computer Systems: A Programmer’s Perspective 學習系統軟體
- [x] 軟體缺失導致的危害
- [x] 解讀計算機編碼
- [x] 你所不知道的 C 語言：指標篇
- [ ] linked list 和非連續記憶體操作
## 作業要求
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* ==詳細閱讀 [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/linux2021-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 在 `qtest` 中實作 [coroutine](https://en.wikipedia.org/wiki/Coroutine)，並提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)，將 `FORK_COUNT` 變更為 `0`，並以 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 取代原本的 fork 系統呼叫
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
* 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
## queue.c 開發過程
:::warning
以下是我的開發想法跟思路
有:bell:的地方是一開始未注意的地方
:question: 則是帶釐清的地方
:::
### q_new
建立新的「空」佇列。
:::info
1.利用 malloc 產生新的 queue :bell:: malloc 失敗會回傳 NULL
2.依照下列題目要求新增 head, tail, size 並初始化
:::
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q)
return NULL;
q->size = 0;
q->head = NULL;
q->tail = NULL;
return q;
}
```
:::danger
不要只張貼程式碼，你的「思路」才更關鍵。還記得標題叫做「開發紀錄」吧？
:notes: jserv
:::
>謝謝老師提醒 會盡快補上思路～
### q_free
釋放佇列所佔用的記憶體。
:::info
一一釋放佇列的記憶體
:bell: ：最後要記得釋放 queue 本身 另外若先釋放 queue 本身會造成[memory leak](https://en.wikipedia.org/wiki/Memory_leak)
:::
```c
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *del;
while (q->head) {
del = q->head->next;
free(q->head->value);
free(q->head);
q->head = del;
}
q->size = 0;
/* Free queue structure */
free(q);
return;
}
```
### q_insert_head
在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)。
:::info
在最開頭新增元素
:bell: strncpy()複製字串長度要 +1（結尾符號 '\0')
:bell: malloc完都要記得確認有沒有成功
:bell: 最後要記得檢查 q->tail 是否存在, 若不存在代表先前 q 內並無元素 ,故 tail 為本次新增的元素 （被這個耽誤超久:cry:）
:::
```c
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if(!newh)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
q->size++;
if (!q->tail)
q->tail = newh;
return true;
}
```
### q_insert_tail
在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)。
:::info
在尾端新增元素
:bell: 需要檢查 q->head 是否存在，若不存在則此佇列先前並無元素
:question: 成功存入的 newh 以及其 value 不能 free 的原因（因為存入 linklist 內是用 pointer 存取 若 free 掉則該位置無東西可存取）
:::
```cpp
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)
return false;
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newt->value) {
free(newt);
return false;
}
newt->next = NULL;
strncpy(newt->value, s, strlen(s) + 1);
if (!q->head) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
q->size++;
return true;
}
```
### q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的元素。
:::info
從佇列開頭開始刪除元素並將元素內的字串存進 sp 中
:bell: 最後複製字串的時候最後要加上結尾符號
:question: 為什麼 bufsize+1 不能改成 strlen(rh->value)+1
:::
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *rh;
rh = q->head;
q->head = q->head->next;
q->size--;
if (sp) {
strncpy(sp, rh->value, bufsize +1);
sp[bufsize - 1] = '\0';
}
free(rh->value);
free(rh);
return true;
}
```
### q_size
計算佇列中的元素數量。
:::info
若 q 不為 NULL 則回傳值
:::
```cpp
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### q_reverse
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
:::info
透過逐一走訪 iter ，讓 next 指向 prev ，達到反轉的效果
:bell: 要先在未反轉時先讓 tail=head 以免事後花時間重新找一次
:::
```cpp
void q_reverse(queue_t *q)
{
if (!q || q->size == 1)
return;
list_ele_t *iter = q->head;
list_ele_t *prev = NULL, *next = NULL;
q->tail = q->head;
while (iter != NULL) {
next = iter;
iter = iter->next;
next->next = prev;
prev = next;
}
q->head = next;
}
```
### q_sort
以遞增順序來排序鏈結串列的元素。
:::warning
已稍做經簡化 但人沒有太大差別 考慮用別的方式 :cry:
:::
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
// merge with pseudo node
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
list_ele_t *tmp = NULL;
list_ele_t *head = NULL;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
if(!tmp){
head = l1;
tmp = head;
l1 = l1->next;
}
else{
tmp->next = l1;
l1 = l1->next;
tmp = tmp->next;
}
} else {
if(!tmp){
head = l2;
tmp = head;
l2 = l2->next;
}
else{
tmp->next = l2;
l2 = l2->next;
tmp = tmp->next;
}
}
}
while (l1 || l2) {
if (l1) {
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
return head;
}
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
void q_sort(queue_t *q)
{
if (!q || q->size == 1 || !q->head)
return;
q->head = mergeSortList(q->head);
list_ele_t *result = q->head;
while (result->next) {
result = result->next;
}
q->tail = result;
}
```
:::danger
上方 merge sort 實作存在大量改進空間，你應該探討並著手落實。
:notes: jserv
:::
>感謝老師 因為我現在尚有很多待補完整的地方
會盡快進行改進
#### make test結果
```c
joanathan@jonathan:~/linux2021/lab0-c$ make testscripts/driver.py -c
--- 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
```
:::warning
:-1: 有時候會 trace-15-perf 出事應該是 sort 時間太久 待更正
```c
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-15-perf 0/6
```
:::
## 使用 Address Sanitizer 進行檢測
### 使用方法
```c
$ make SANITIZER=1
$ ./qtest
cmd>help
```
:::info
:bell:如果之前就 `make test` 過了，要先 `make clean` 才能使用 `make SANITIZER=1`
:::
### 分析
```c
joanathan@jonathan:~/linux2021/lab0-c$ ./qtest
cmd> help
Commands:
# ... | Display comment
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
time cmd arg ... | Time command execution
Options:
=================================================================
==17298==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5647af6f53c0 at pc 0x5647af6de7bd bp 0x7ffea46d0620 sp 0x7ffea46d0610
READ of size 4 at 0x5647af6f53c0 thread T0
#0 0x5647af6de7bc in do_help_cmd /home/joanathan/linux2021/lab0-c/console.c:307
#1 0x5647af6de8d0 in interpret_cmda /home/joanathan/linux2021/lab0-c/console.c:221
#2 0x5647af6df0b5 in interpret_cmd /home/joanathan/linux2021/lab0-c/console.c:244
#3 0x5647af6e07f8 in run_console /home/joanathan/linux2021/lab0-c/console.c:660
#4 0x5647af6dd3e5 in main /home/joanathan/linux2021/lab0-c/qtest.c:780
#5 0x7f09bbf920b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5647af6dab8d in _start (/home/joanathan/linux2021/lab0-c/qtest+0x8b8d)
0x5647af6f53c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5647af6f53c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/joanathan/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac975ed6a20: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ac975ed6a30: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac975ed6a40: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac975ed6a50: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac975ed6a60: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac975ed6a70: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ac975ed6a80: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac975ed6a90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac975ed6aa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac975ed6ab0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac975ed6ac0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==17298==ABORTING
```
```c
==17298==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5647af6f53c0 at pc 0x5647af6de7bd bp 0x7ffea46d0620 sp 0x7ffea46d0610
READ of size 4 at 0x5647af6f53c0 thread T0
#0 0x5647af6de7bc in do_help_cmd /home/joanathan/linux2021/lab0-c/console.c:307
#1 0x5647af6de8d0 in interpret_cmda /home/joanathan/linux2021/lab0-c/console.c:221
#2 0x5647af6df0b5 in interpret_cmd /home/joanathan/linux2021/lab0-c/console.c:244
#3 0x5647af6e07f8 in run_console /home/joanathan/linux2021/lab0-c/console.c:660
#4 0x5647af6dd3e5 in main /home/joanathan/linux2021/lab0-c/qtest.c:780
#5 0x7f09bbf920b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5647af6dab8d in _start (/home/joanathan/linux2021/lab0-c/qtest+0x8b8d)
```
首先上述是在講一個 大小為 4 的 `read` 有 global-buffer-overflow
最明顯的地方就是在 `console.h` 307行那邊有問題
於是去找那行是在講什麼
```c
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation);
plist = plist->next;
}
```
由於他說大小為 4 故可以判斷應為 `*pist->valp` 這邊出問題，因為 intager 的關係
我們可以追朔到
```c
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
得知是 echo 這個變數出了問題
```c
static bool echo = 0;
```
我猜想是 echo 是 bool 的型態被強至轉形成 int 產生問題
:::info
expected: int (4 bite)
now: bool (1 bite)
:::
在這裡可能會想直接設定 echo 為 int 就好
於是我再分析一次
```c
joanathan@jonathan:~/linux2021/lab0-c$ ./qtest
cmd> help
Commands:
# ... | Display comment
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
time cmd arg ... | Time command execution
Options:
echo 1 Do/don't echo commands
error 5 Number of errors until exit
fail 30 Number of times allow queue operations to return false
length 1024 Maximum length of displayed string
malloc 0 Malloc failure probability percent
=================================================================
==26154==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5592e6f56a00 at pc 0x5592e6f470b5 bp 0x7fff0b917410 sp 0x7fff0b917400
READ of size 4 at 0x5592e6f56a00 thread T0
#0 0x5592e6f470b4 in do_help_cmd /home/joanathan/linux2021/lab0-c/console.c:307
#1 0x5592e6f471c8 in interpret_cmda /home/joanathan/linux2021/lab0-c/console.c:221
#2 0x5592e6f479ad in interpret_cmd /home/joanathan/linux2021/lab0-c/console.c:244
#3 0x5592e6f490f3 in run_console /home/joanathan/linux2021/lab0-c/console.c:660
#4 0x5592e6f46463 in main /home/joanathan/linux2021/lab0-c/qtest.c:780
#5 0x7f89c32de0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5592e6f44acd in _start (/home/joanathan/linux2021/lab0-c/qtest+0x4acd)
0x5592e6f56a01 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5592e6f56a00) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/joanathan/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ab2dcde2cf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d10: 00 00 00 00 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0ab2dcde2d20: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0ab2dcde2d30: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
=>0x0ab2dcde2d40:[01]f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab2dcde2d50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2dcde2d90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==26154==ABORTING
```
看到它寫說 `stimulation` 也有一樣問題
```c
0x5592e6f56a01 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5592e6f56a00) of size 1
'simulation' is ascii string ''
```
於是我將 `stimulation` 也改成 int
```c
int simulation = 0;
```
但是這樣編譯不會過，因為在 `console.h` 中也需要改 `stimulation`
```c
extern int simulation;
```
之後再執行一次
```c
joanathan@jonathan:~/linux2021/lab0-c$ ./qtest
cmd> help
Commands:
# ... | Display comment
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
time cmd arg ... | Time command execution
Options:
echo 1 Do/don't echo commands
error 5 Number of errors until exit
fail 30 Number of times allow queue operations to return false
length 1024 Maximum length of displayed string
malloc 0 Malloc failure probability percent
simulation 0 Start/Stop simulation mode
verbose 4 Verbosity level
```
發現成功了
## 以 Valgrind 分析記憶體問題
### 使用方式
```c
$ make valgrind
```
### 分析
```c
joanathan@jonathan:~/linux2021/lab0-c$ make valgrind
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==18190== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18190== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18190== by 0x4A5750E: strdup (strdup.c:42)
==18190== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18190== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18190== by 0x10C234: main (qtest.c:769)
==18190==
==18190== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18190== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18190== by 0x4A5750E: strdup (strdup.c:42)
==18190== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18190== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18190== by 0x10C234: main (qtest.c:769)
==18190==
==18190== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18190== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18190== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18190== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18190== by 0x10C234: main (qtest.c:769)
==18190==
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
==18192== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18192== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18192== by 0x4A5750E: strdup (strdup.c:42)
==18192== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18192== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18192== by 0x10C234: main (qtest.c:769)
==18192==
==18192== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18192== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18192== by 0x4A5750E: strdup (strdup.c:42)
==18192== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18192== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18192== by 0x10C234: main (qtest.c:769)
==18192==
==18192== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18192== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18192== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18192== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18192== by 0x10C234: main (qtest.c:769)
==18192==
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
==18201== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18201== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18201== by 0x4A5750E: strdup (strdup.c:42)
==18201== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18201== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18201== by 0x10C234: main (qtest.c:769)
==18201==
==18201== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18201== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18201== by 0x4A5750E: strdup (strdup.c:42)
==18201== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18201== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18201== by 0x10C234: main (qtest.c:769)
==18201==
==18201== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18201== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18201== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18201== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18201== by 0x10C234: main (qtest.c:769)
==18201==
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
==18202== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18202== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18202== by 0x4A5750E: strdup (strdup.c:42)
==18202== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18202== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18202== by 0x10C234: main (qtest.c:769)
==18202==
==18202== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18202== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18202== by 0x4A5750E: strdup (strdup.c:42)
==18202== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18202== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18202== by 0x10C234: main (qtest.c:769)
==18202==
==18202== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18202== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18202== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18202== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18202== by 0x10C234: main (qtest.c:769)
==18202==
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
==18203== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18203== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18203== by 0x4A5750E: strdup (strdup.c:42)
==18203== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18203== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18203== by 0x10C234: main (qtest.c:769)
==18203==
==18203== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18203== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18203== by 0x4A5750E: strdup (strdup.c:42)
==18203== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18203== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18203== by 0x10C234: main (qtest.c:769)
==18203==
==18203== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18203== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18203== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18203== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18203== by 0x10C234: main (qtest.c:769)
==18203==
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
==18204== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18204== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18204== by 0x4A5750E: strdup (strdup.c:42)
==18204== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18204== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18204== by 0x10C234: main (qtest.c:769)
==18204==
==18204== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18204== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18204== by 0x4A5750E: strdup (strdup.c:42)
==18204== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18204== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18204== by 0x10C234: main (qtest.c:769)
==18204==
==18204== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18204== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18204== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18204== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18204== by 0x10C234: main (qtest.c:769)
==18204==
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
==18207== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18207== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18207== by 0x4A5750E: strdup (strdup.c:42)
==18207== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18207== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18207== by 0x10C234: main (qtest.c:769)
==18207==
==18207== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18207== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18207== by 0x4A5750E: strdup (strdup.c:42)
==18207== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18207== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18207== by 0x10C234: main (qtest.c:769)
==18207==
==18207== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18207== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18207== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18207== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18207== by 0x10C234: main (qtest.c:769)
==18207==
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
==18208== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18208== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18208== by 0x4A5750E: strdup (strdup.c:42)
==18208== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18208== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18208== by 0x10C234: main (qtest.c:769)
==18208==
==18208== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18208== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18208== by 0x4A5750E: strdup (strdup.c:42)
==18208== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18208== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18208== by 0x10C234: main (qtest.c:769)
==18208==
==18208== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18208== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18208== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18208== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18208== by 0x10C234: main (qtest.c:769)
==18208==
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
==18209== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18209== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18209== by 0x4A5750E: strdup (strdup.c:42)
==18209== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18209== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18209== by 0x10C234: main (qtest.c:769)
==18209==
==18209== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18209== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18209== by 0x4A5750E: strdup (strdup.c:42)
==18209== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18209== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18209== by 0x10C234: main (qtest.c:769)
==18209==
==18209== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18209== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18209== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18209== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18209== by 0x10C234: main (qtest.c:769)
==18209==
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
==18210== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18210== by 0x4A5750E: strdup (strdup.c:42)
==18210== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18210== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18210== by 0x10C234: main (qtest.c:769)
==18210==
==18210== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18210== by 0x4A5750E: strdup (strdup.c:42)
==18210== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18210== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18210== by 0x10C234: main (qtest.c:769)
==18210==
==18210== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18210== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18210== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18210== by 0x10C234: main (qtest.c:769)
==18210==
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
==18211== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18211== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18211== by 0x4A5750E: strdup (strdup.c:42)
==18211== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18211== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18211== by 0x10C234: main (qtest.c:769)
==18211==
==18211== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18211== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18211== by 0x4A5750E: strdup (strdup.c:42)
==18211== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18211== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18211== by 0x10C234: main (qtest.c:769)
==18211==
==18211== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18211== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18211== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18211== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18211== by 0x10C234: main (qtest.c:769)
==18211==
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
==18212== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18212== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18212== by 0x4A5750E: strdup (strdup.c:42)
==18212== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18212== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18212== by 0x10C234: main (qtest.c:769)
==18212==
==18212== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18212== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18212== by 0x4A5750E: strdup (strdup.c:42)
==18212== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18212== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18212== by 0x10C234: main (qtest.c:769)
==18212==
==18212== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18212== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18212== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18212== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18212== by 0x10C234: main (qtest.c:769)
==18212==
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
==18213== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18213== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18213== by 0x4A5750E: strdup (strdup.c:42)
==18213== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18213== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18213== by 0x10C234: main (qtest.c:769)
==18213==
==18213== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18213== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18213== by 0x4A5750E: strdup (strdup.c:42)
==18213== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18213== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18213== by 0x10C234: main (qtest.c:769)
==18213==
==18213== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18213== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18213== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18213== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18213== by 0x10C234: main (qtest.c:769)
==18213==
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
==18217== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18217== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18217== by 0x4A5750E: strdup (strdup.c:42)
==18217== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18217== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18217== by 0x10C234: main (qtest.c:769)
==18217==
==18217== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18217== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18217== by 0x4A5750E: strdup (strdup.c:42)
==18217== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18217== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18217== by 0x10C234: main (qtest.c:769)
==18217==
==18217== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18217== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18217== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18217== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18217== by 0x10C234: main (qtest.c:769)
==18217==
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==18222== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18222== by 0x4A5750E: strdup (strdup.c:42)
==18222== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18222== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18222== by 0x10C234: main (qtest.c:769)
==18222==
==18222== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18222== by 0x4A5750E: strdup (strdup.c:42)
==18222== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18222== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18222== by 0x10C234: main (qtest.c:769)
==18222==
==18222== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18222== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18222== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18222== by 0x10C234: main (qtest.c:769)
==18222==
--- 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
==18229== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18229== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18229== by 0x4A5750E: strdup (strdup.c:42)
==18229== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18229== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18229== by 0x10C234: main (qtest.c:769)
==18229==
==18229== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18229== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18229== by 0x4A5750E: strdup (strdup.c:42)
==18229== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18229== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18229== by 0x10C234: main (qtest.c:769)
==18229==
==18229== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18229== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18229== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18229== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18229== by 0x10C234: main (qtest.c:769)
==18229==
--- 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
==18230== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==18230== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18230== by 0x4A5750E: strdup (strdup.c:42)
==18230== by 0x1100A0: linenoiseHistoryAdd (linenoise.c:1236)
==18230== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18230== by 0x10C234: main (qtest.c:769)
==18230==
==18230== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==18230== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18230== by 0x4A5750E: strdup (strdup.c:42)
==18230== by 0x110014: linenoiseHistoryAdd (linenoise.c:1236)
==18230== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18230== by 0x10C234: main (qtest.c:769)
==18230==
==18230== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==18230== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==18230== by 0x110060: linenoiseHistoryAdd (linenoise.c:1224)
==18230== by 0x110C33: linenoiseHistoryLoad (linenoise.c:1325)
==18230== by 0x10C234: main (qtest.c:769)
==18230==
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.cXwndf --valgrind -t <tid>
```
超級多的.....看到這裡真的很崩潰
只好硬著頭皮一個一個看
首先 我們看到每個部份都是有一些東西 still reachable 看起來好像都是在 `qtest.c::769` `linenoise.c:1236` `linenoise.c:1325`
* qtest.c::769
```c
linenoiseHistoryLoad(HISTORY_FILE);
```
* linenoise.c:1236 （在`linenoiseHistoryAdd(const char *line)`內）
```c
linecopy = strdup(line);
```--show-reachable=no
* linenoise.c:1325 （在`linenoiseHistoryLoad(const char *filename)`內）
```c
linenoiseHistoryAdd(buf);
```
我猜測應該問題都出現在 `linenoise.c:1236` 的 `strdup` 中
於是我就google `man strdup`
```c
The strdup() function returns a pointer to a new string which is a duplicate of the string s.
Memory for the new string is obtained with malloc(3), and can be freed with free(3).
```
看起來好像真的是 `strdup()` allocate 的記憶體沒有 free() 掉
我試了兩個方法
* 使用不同的函式複製字串
* 在結尾 free 掉 histroy
但都沒有成功 :cry:，後來參考 `DDerveialm` 大大的筆記，才懂原理
```c=
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;
}
```
只要避免在讀檔時 free 掉就可以解決的，因此將函式改成下面這樣久可以解決
```c=
if(!infile_name){
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
```
```c
joanathan@jonathan:~/linux2021/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: 進入目錄「/home/joanathan/linux2021/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 linenoise.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 .linenoise.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
CC linenoise.o
LD qtest
make[1]: 離開目錄「/home/joanathan/linux2021/lab0-c」
cp qtest /tmp/qtest.e3XyB6
chmod u+x /tmp/qtest.e3XyB6
sed -i "s/alarm/isnan/g" /tmp/qtest.e3XyB6
scripts/driver.py -p /tmp/qtest.e3XyB6 --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-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
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.e3XyB6 --valgrind -t <tid>
```
### 透過 Massif 視覺化記憶體使用量
首先先安裝 `massif-visualizer` 跑出圖表
```c
$ sudo apt-get install massif-visualizer
```
再來以 **trace-16-perf.cmd** 為例
```c
valgrind --tool=massif ./qtest -f traces/trace-16-perf.cmd
```
會生成 massif 圖檔，輸入以下指令將其開啟
```c
massif-visualizer massif.out.11729
```
以下就是所生成的圖檔
:::info
TODO massif實驗
:::
## select system call ＆ 分析 console.c
根據[select(2) — Linux manual page](https://man7.org/linux/man-pages/man2/select.2.html)
> select() allows a program to monitor multiple file descriptors,
> waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible).
> A file descriptor is considered ready if it is possible to perform a corresponding I/O operation
:::info
**file descriptors:** 開啟檔案之後都會回一個 file descriptor，之後操作檔案皆須透過此參數
:::
### the use of `select()`
* monitors multiple file descriptors.
* waiting until one or more of the file descriptors become “ready” for some class of I/O operation (e.g., input possible).
### Arguments
* **`nfds`**: This argument should be set to the highest-numbered filedescriptor in any of the three sets, plus 1.
* **`readfds`**: The file descriptors in this set are watched to see if they are ready for reading.
* **`writefds`**: The file descriptors in this set are watched to see if they are ready for writing.
* **`exceptfds`**: The file descriptors in this set are watched for "exceptional conditions".
* **`timeout`**: The timeout argument is a timeval structure (shown below) that specifies the interval that select() should block waiting for a file descriptor to become ready.
> The call will block until either:
>* a file descriptor becomes ready
>* the call is interrupted by a signal handler
>* the timeout expires
### File descriptor sets
* **`FD_ZERO()`**: clears set.(initializing a file descriptor set)
* **`FD_SET()`**: adds the file descriptor fd to set.
* **`FD_CLR()`**: removes the file descriptor from set.
* **`FD_ISSET()`**: tests to see if a file descriptor is part of the set
### return value
* if success, return **the number of file descriptors**
* return **zero** if the timeout expired before any file descriptors became ready.
* **-1** is returned, and errno is set to indicate the error; the file descriptor sets are unmodified, and timeout becomes undefined.
### `console.c` 中 `select()` 的實作
```c
int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
int infd;
fd_set local_readset;
if (cmd_done())
return 0;
if (!block_flag) {
/* Process any commands in input buffer */
if (!readfds)
readfds = &local_readset;
/* Add input fd to readset for select */
infd = buf_stack->fd;
FD_SET(infd, readfds);
if (infd == STDIN_FILENO && prompt_flag) {
printf("%s", prompt);
fflush(stdout);
prompt_flag = true;
}
if (infd >= nfds)
nfds = infd + 1;
}
if (nfds == 0)
return 0;
int result = select(nfds, readfds, writefds, exceptfds, timeout);
if (result <= 0)
return result;
infd = buf_stack->fd;
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
if (has_infile) {
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
}
return result;
}
```
在 blog flag = false 的情況下（程式中恆為false 為什麼要設這個)＝>後來參考別人筆記得知是殘存的程式碼
```cpp
if (!readfds)
readfds = &local_readset;
```
若 readfds 為 NULL ，則指向 local_readset
```c
infd = buf_stack->fd;
FD_SET(infd, readfds);
```
新增 buffer 中的 file descriptors 新增到 set 中，送到 select()
```c
int result = select(nfds, readfds, writefds, exceptfds, timeout);
if (result <= 0)
return result;
```
select會回傳有多少 file descriptors 準備好，若值<=0 為沒有或有錯誤， return
```c
infd = buf_stack->fd;
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
if (has_infile) {
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
}
```
:::info
接著這邊是對 file descriptor的操作，目前了解操作完之後減少 result 的數量，其餘部份還不清楚
:::
### 說明其中運用 CS:APP RIO 套件 的原理和考量點
TODO
還在研讀cs:app
## 說明 antirez/linenoise 的運作原理
說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
## 實作 coroutine
[coroutine](https://en.wikipedia.org/wiki/Coroutine)
## 研讀 Dude, is my code constant time?
[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
Sign in with Wallet
Connect another wallet