# 2021q1 Homework1 (lab0)
contributed by < `jameshuang890902` >
## 進度列表
### 修改 queue.[ch] 和連帶的檔案
- [x] `q_new`: 建立新的「空」佇列。
- [x] `q_free`: 釋放佇列所佔用的記憶體。
- [x] `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)。
- [x] `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)。
- [x] `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的元素。
- [x] `q_size`: 計算佇列中的元素數量。
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素。
- [x] `q_sort`: 「Linux 核心設計」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法。
### 進行測試
- [x] 以 Address Sanitizer，修正 qtest 執行過程中的錯誤。
- [x] 運用 Valgrind 排除 qtest 實作的記憶體錯誤。
- [ ] 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量（需要設計對應的實驗）。
### 其他任務
- [x] 在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能。
- [x] 嘗試整合 tiny-web-server，將 FORK_COUNT 變更為 0，並以 coroutine 取代原本的 fork 系統呼叫。
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
- [ ] 比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)。
- [ ] 說明 antirez/linenoise 的運作原理，注意到 termios 的運用。
- [ ] 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案。
- [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request。
## 目前著手問題
- [ ] 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量（需要設計對應的實驗）。
## 環境設置
### 作業環境
- 本作業在 **macOS Big Sur** 安裝的 **Parallels Desktop 16 for Mac** 中的 **Ubuntu** 執行。
```shell
$ lsb_release -d
Description: Ubuntu 20.04.2 LTS
$ gcc -- version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
lsb_release -d
```
### 安裝必要套件
```shell
$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff
$ sudo apt install libc6-dbg
```
## 修改 queue.[ch] 和連帶的檔案
### 修改 queue.h 中的`queue_t`資料結構
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Point to the tail of linked list */
int size; /* Number of elements in the linked list */
} queue_t;
```
上述程式碼添加`list_ele_t *tail;` 和` list_ele_t *tail;`，其用意會在下方對應函式`q_size` 與 `q_insert_tail`中多做說明。
### 在 queue.h 新增 merge( )
```cpp
/*
* For merge_sort (recursive)
* Merge two list.
*/
list_ele_t *merge(list_ele_t *list1, list_ele_t *list2);
/*
* Merge_sort (recursive)
* Applied in q_sort()
*/
list_ele_t *merge_sort(list_ele_t *head);
```
- 其用意會在下方對應函式`q_sort`中多做說明。
### `q_new`: 建立新的「空」佇列
#### `queue_t *q_new()`
- Create empty queue.
- Return `NULL` if could not allocate space.
``` cpp
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
### `q_free`: 釋放佇列所佔用的記憶體
- Free all storage used by queue.
- Freeing the list elements and the strings.
- Free queue structure.
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *temp = q->head;
while (q->head) {
q->head = q->head->next;
free(temp->value);
free(temp);
temp = q->head;
}
free(q);
}
```
### `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)
- 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.
- What should you do if the q is NULL?
- Don't forget to allocate space for the string and copy it.
- What if either call to malloc returns NULL?
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = (char *) 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;
if (q->size == 0)
q->tail = newh;
q->size++;
return true;
}
```
### `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)
- 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.
- It should operate in O(1) time.
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (q->size == 0) {
q->head = newt;
} else
q->tail->next = newt;
q->tail = newt;
q->size++;
return true;
}
```
### `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的元素
- 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.
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
list_ele_t *indirect = q->head;
if (sp) {
int copy_len = bufsize - 1 > strlen(q->head->value)
? strlen(q->head->value)
: bufsize - 1;
sp[copy_len] = '\0';
strncpy(sp, q->head->value, copy_len);
}
q->head = indirect->next;
free(indirect->value);
free(indirect);
indirect = NULL;
q->size--;
return true;
}
```
:::info
:bell: 需要在 strncpy 的最後一位加入`'\0'` 解決下面的錯誤。
```c=
sp[copy_len] = '\0';
strncpy(sp, q->head->value, copy_len);
```
未加入`'\0'` 在正確位置時的錯誤訊息。
```shell=
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR: Removed value ３meerkat_panda_squirrel_vulture_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value aardvark_bear_dolphin_gerbil_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil
ERROR: Removed value aardvark_bear_dolphin_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin
ERROR: Removed value meerkat_panda_squirrel_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel
ERROR: Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat
Error limit exceeded. Stopping command execution
--- trace-06-string 0/6
```
:::
### `q_size`: 計算佇列中的元素數量
- Return number of elements in queue.
- Return 0 if q is NULL or empty.
- It should operate in O(1) time.
```c=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
:::info
:bell: 在執行 q_insert_head, q_insert_tail, q_remove_head 時就紀錄 q->size，並藉由直接回傳 q->size 來達到 $O(1)$ 的複雜度。
:::
### `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.
```cpp
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
q->tail = q->head;
list_ele_t *middle, *trail;
middle = NULL;
while (q->head) {
trail = middle;
middle = q->head;
q->head = q->head->next;
middle->next = trail;
}
q->head = middle;
}
```
- 參考基礎資料結構—使用C語言第二版4.5.1。
### `q_sort`: 以遞增順序來排序鏈結串列的元素
可參閱 Linked List Sort 得知實作手法
- 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.
- 採用時間複雜度為 $O(n\log n)$ 的 **Merge sort**進行實作。
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
if (l1)
*tmp = l1;
if (l2)
*tmp = l2;
return head;
}
list_ele_t *merge_sort(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 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
return merge(l1, l2);
}
void q_sort(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
- 參考 [`ccs100203`](https://hackmd.io/@cccccs100203/linux2020-lab0)的作業。
:::info
:beetle: 下面舊版程式碼出現以下問題，推測是 sort 的效能未達到要求。
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
int cmp_result = strcmp(l1->value, l2->value);
if (cmp_result <= 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
```
- 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)。
```shell=
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 0/6
```
因為 merge_sort, merge 都是遞迴函式，merge 被呼叫的頻率又更高，因此從 merge 著手進行優化，將其改為迭代形式。
:::
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
### 先照指示修正 `cmd>help` 時的錯誤
先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除。
```shell=
$ make clean
$ make SANITIZER=1// 開啟 Address Sanitizer
$ ./qtest
cmd>help
...
==228285==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55aa5a70b3c0 at pc 0x55aa5a6f47bd bp 0x7fffa6c3edf0 sp 0x7fffa6c3ede0
READ of size 4 at 0x55aa5a70b3c0 thread T0
#0 0x55aa5a6f47bc in do_help_cmd /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:307
#1 0x55aa5a6f48d0 in interpret_cmda /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:221
#2 0x55aa5a6f50b5 in interpret_cmd /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:244
#3 0x55aa5a6f67f8 in run_console /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:660
#4 0x55aa5a6f33e5 in main /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/qtest.c:780
#5 0x7f54f59440b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55aa5a6f0b8d in _start (/media/psf/Home/Desktop/Linux2021/lab0-c/qtest+0x8b8d)
0x55aa5a70b3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55aa5a70b3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ab5cb4d9620: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ab5cb4d9630: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab5cb4d9640: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ab5cb4d9650: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab5cb4d9660: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ab5cb4d9670: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ab5cb4d9680: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ab5cb4d9690: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab5cb4d96a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab5cb4d96b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab5cb4d96c0: 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
==228285==ABORTING
```
```
SUMMARY: AddressSanitizer: global-buffer-overflow /home/jameshuang890902/Desktop/Parallels Shared Folders/Home/Desktop/Linux2021/lab0-c/console.c:307 in do_help_cmd
```
根據上面的錯誤訊息可以得知，應該要檢查 console.c ，下面把錯誤發生的區段 `do_help_cmd` 提出來分析。
```c=
/* Part of code in console.c*/
// Near by line 307
static bool do_help_cmd(int argc, char *argv[])
{
...
param_ptr plist = param_list;
...
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
...
}
```
把該行被呼叫的 report 也抽出來看。
```c=
/* Part of code in report. c*/
void report(int level, char *fmt, ...)
{
if (!verbfile)
init_files(stdout, stdout);
if (level <= verblevel) {
va_list ap;
va_start(ap, fmt);
vfprintf(verbfile, fmt, ap);
fprintf(verbfile, "\n");
fflush(verbfile);
va_end(ap);
if (logfile) {
va_start(ap, fmt);
vfprintf(logfile, fmt, ap);
fprintf(logfile, "\n");
fflush(logfile);
va_end(ap);
}
}
}
```
:::info
:bulb: 這段程式碼當中用到 `stdarg.h` 的操作。
:::
由於上面是針對`verbfile, logfile` 的讀寫，猜測也許問題是出在某變數的 type 與給定的 format （上面的 fmt）不相同，所以把 plist 的資料結構找出來看。
```c=
/* Part of code in console.h*/
/* Integer-valued parameters */
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
因為在 report 中的 `plist`是經過`param_ptr plist = param_list;` 的初始化，所以要確認`param_list`是否正確。下面是 `param_list` 的宣告。
```c=22
//console.c
static param_ptr param_list = NULL;
```
發現 `param_list` 的資料指派是在 `qtest`中呼叫 `init_cmd()` 時發生。所以對其做檢查。
因為之前錯誤訊息中的 `0x55aa5a70b3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55aa5a70b3c0) of size 1` ，所以去檢查 `echo` 有沒有問題。
```c=86
// console.c
/* Initialize interpreter */
void init_cmd()
{
...
param_list = NULL;
...
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);
...
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
...
}
```
這裡在 `(int *) &echo` 和`(int *) &simulation`都有做一個型態轉換。
下面先確認傳入`add_param`的是(int *)型態，所以不是問題所在。
```c=
/* Add a new parameter */
void add_param(char *name,
int *valp,
char *documentation,
setter_function setter)
{
...
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
...
ele->valp = valp;
...
}
```
所以找出 `echo` 與 `simulation `的定義與操作，改為 `int` 的形式。
```diff=
-static bool echo = 0;
+static int echo = 0;
-extern bool simulation;
+extern int simulation;
-bool simulation = false;
+int simulation = 0;
```
經過上面的操作解決了之前的錯誤訊息。
## 運用 [Valgrind](https://valgrind.org/) 排除 qtest 實作的記憶體錯誤
```shell=
$ valgrind --version
valgrind 3.15.0
$ make clean
$ make valgrind
...
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.maBz2U --valgrind -t <tid>
```
發現在每個 trace遇到的問題都遇到像同問題，所以下面只顯示 trace 01：
```shell=
$ scripts/driver.py -p /tmp/qtest.Il7I6E --valgrind -t 01
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==164050== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==164050== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==164050== by 0x4A4C50E: strdup (strdup.c:42)
==164050== by 0x110091: linenoiseHistoryAdd (linenoise.c:1236)
==164050== by 0x110C24: linenoiseHistoryLoad (linenoise.c:1325)
==164050== by 0x10C22C: main (qtest.c:769)
==164050==
==164050== 70 bytes in 13 blocks are still reachable in loss record 2 of 3
==164050== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==164050== by 0x4A4C50E: strdup (strdup.c:42)
==164050== by 0x110005: linenoiseHistoryAdd (linenoise.c:1236)
==164050== by 0x110C24: linenoiseHistoryLoad (linenoise.c:1325)
==164050== by 0x10C22C: main (qtest.c:769)
==164050==
==164050== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==164050== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==164050== by 0x110051: linenoiseHistoryAdd (linenoise.c:1224)
==164050== by 0x110C24: linenoiseHistoryLoad (linenoise.c:1325)
==164050== by 0x10C22C: main (qtest.c:769)
==164050==
--- trace-01-ops 6/6
--- TOTAL 6/6
```
根據作業說明:
>still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。
應該要去找程式結束時有未釋放的記憶體的 global 變數。
> "Still reachable". This covers cases 1 and 2 (for the BBB blocks) above. A start-pointer or chain of start-pointers to the block is found. Since the block is still pointed at, the programmer could, at least in principle, have freed it before program exit. "Still reachable" blocks are very common and arguably not a problem. So, by default, Memcheck won't report such blocks individually. https://valgrind.org/docs/manual/mc-manual.html#mc-manual.errormsgs
從 trace 01 的錯誤訊息與程式碼比對得知，錯誤發生在 `linenoiseHistoryLoad` 所呼叫的 `linenoiseHistoryAdd` 中的兩行，下面特別標示。
```c=
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len); // <-line 1224
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line); // <-line 1236
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
```
>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).
https://linux.die.net/man/3/strdup
我覺得 `n bytes in m blocks are still reachable in loss record` （n, m 表示某正整數）的問題應該是經由下列程式碼：
```c=
history = malloc(sizeof(char *) * history_max_len); // <-line 1224
linecopy = strdup(line); // <-line 1236
```
所分配的記憶體最後還是 reachable by 全域變數 `history` 才會顯示上面的訊息，目前看來不影響程式運作。
```c=
static char **history = NULL;
```
應該要檢查程式結束時 history 的所有記憶體是否已經被釋放。
:::warning
:warning: 由於尚未找出改善上述訊息之作法，先在 `.valgrindrc` 中關閉`reachable`提示，檢查後發現只有上面的問題，並無其他狀況。
```diff
--quiet
--memcheck:leak-check=full
--memcheck:show-leak-kinds=all
--error-exitcode=1
+--show-reachable=no
```
:::
## 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量（需要設計對應的實驗）
備註：
## 在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
嘗試整合 tiny-web-server，將 FORK_COUNT 變更為 0，並以 coroutine 取代原本的 fork 系統呼叫。
```c=
static void console_init()
{
...
add_cmd("web", do_web, " | Run web server");
...
}
```
```c=
static bool do_web(int argc, char *argv[])
{
...
// int i = 0;
// for (; i < FORK_COUNT; i++) {
pid_server = fork();
if (pid_server == 0) { // child
while (1) {
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
} else if (pid_server > 0) { // parent
printf("child pid is %d\n", pid_server);
longjmp(jmpbuffer, 1);
} else {
perror("fork");
}
// }
while (1) {
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
return 0;
}
```
```c=
int main(int argc, char *argv[])
{
...
setjmp(jmpbuffer);
ok = ok && run_console(infile_name);
...
}
```
在這行等待 request
`connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);`
也有完成自動關閉子 pid 的程序。
Sign in with Wallet
Connect another wallet