# 2021q1 Homework1 (lab0)
contributed by < `tiffany6022` >
###### tags: `linux2021`
> [作業說明](https://hackmd.io/@sysprog/linux2021-lab0)
- [x] C Programming Lab
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_size
- [x] q_reverse
- [x] q_sort
- [x] Address Sanitizer
- [x] Valgrind
- [ ] Coroutine
- [ ] 解釋 select 系統
- [ ] 說明 antirez/linenoise 的運作原理
- [ ] 研讀論文
- [ ] 指出現有程式的缺陷
## C Programming Lab
以下為實做方式以及遇到過的問題
### 開始
* 進入 `queue.c` 和 `queue.h` 進行修改
* 輸入 `make` 、 `clean` 分別執行 編譯檔案 及 清除編譯檔案
* 輸入 `make test` 執行自動評分系統
* 輸入 `./qtest -f traces/[trace file].cmd` 執行單一測試檔
### q_new
* 建一個 empty queue
### q_free
* 若一個已動態配置記憶體的 struct，裡面也有成員已動態配置記憶體了，那在釋放時應先從裡面的成員開始釋放，避免從 struct 先釋放而導致要釋放成員時找不到記憶體位置
:::warning
改進你的漢語表達，上面那句到底是什麼意思？在面試或者電話會議的場合中，你若說「從裡面 free 出來」，到底多少人可會意？
:notes: jserv
:::
> 已修正
```cpp=
...
free(q->head->value);
free(q->head);
free(q);
...
```
### q_insert_head
* 當 newh->value 動態配置記憶體失敗時，要記得釋放掉之前 newh 配置的記憶體
* 計算分配記憶體長度給 value 時，除了 strlen(s) 還要 +1，因為 `strlen` 計算的長度不包含 terminating null byte ('\0')
* `strncpy` 複製字串時，會連同 '\0' 一起複製
```cpp=
...
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, (strlen(s) + 1));
...
```
### q_insert_tail
* 同 `q_insert_head`
* 由於要達到 $O(1)$ 的常數時間複雜度，新增 `list_ele_t *tail` 這個新成員到 `struct queue_t`
```cpp=
typedef struct {
...
list_ele_t *tail;
} queue_t;
```
* 要記得考慮只有當 q->tail 不是 NULL 時，才可以設 q->tail->next (一開始沒考慮到，造成 `trace-17-complexity` 錯誤)
```cpp=
...
if (q->tail)
q->tail->next = newt;
...
```
### q_remove_head
* 需要考慮字串最長的長度 bufsize，當字串超過限制長度時，要複製原有的字串，長度設為 bufsize - 1 ，因為要留一位給 '\0' (一開始看不懂忽略它XD，造成 `trace-06-string` 錯誤)
```cpp=
...
if (sp) {
if (strlen(q->head->value) < bufsize) {
strncpy(sp, q->head->value, (strlen(q->head->value) + 1));
} else {
strncpy(sp, q->head->value, (bufsize - 1));
sp[bufsize - 1] = '\0';
}
}
...
```
### q_size
* 由於要在 $O(1)$ 的常數時間內執行完成，新增 `int size` 這個新成員到 `struct queue_t`
```cpp=
typedef struct {
...
int size;
} queue_t;
```
### q_reverse
* 利用3個 pointer 紀錄目前位置及前後位置，將他們的 next 轉換
```cpp=
...
list_ele_t *_prev = NULL;
list_ele_t *_curr = q->head;
list_ele_t *_next = q->head->next;
q->tail = _curr;
while (_next) {
_curr->next = _prev;
_prev = _curr;
_curr = _next;
_next = _curr->next;
}
_curr->next = _prev;
q->head = _curr;
```
### q_sort
* 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 merge sort
* 原先用 `strcmp` 比較字串可以實做，但之後發現 `qtest.c` 裡面是用 `strcasecmp` 測試我們的程式，兩者的差別在於 `strcasecmp` 會自動忽略大小寫的差異，因而改用 `strcasecmp` 做比較
* 原本 merge() 是利用以下遞迴的方式寫，但會造成 `trace-15-perf` 發生 segmentation fault (core dumped)
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (strcasecmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
```
* 改成沒有遞迴的版本
* 先比較兩個 list 的第一個 node 記錄起始位置
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *temp, *head;
if (strcasecmp(l1->value, l2->value) < 0) {
temp = l1;
l1 = l1->next;
} else {
temp = l2;
l2 = l2->next;
}
head = temp;
while (l1 && l2) {
if (strcasecmp(l1->value, l2->value) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return head;
}
```
* 利用2個 pointer，找到分割點，一個一次走1步，另一個一次走2步，當走得快的那個到終點時，慢的那個的位置就是 list 的中間
```cpp=
list_ele_t *mergeSortList(list_ele_t *head)
{
...
list_ele_t *slow = head;
list_ele_t *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
...
}
```
### 結果
> 過程中遇到測資沒過，還傻傻的以為要改其他檔案的程式，其實到目前為止都只有改 `queue.c` 和 `queue.h` 這兩個檔案
```
--- TOTAL 100/100
```
:::danger
文字訊息不要用圖片展現！
:notes: jserv
:::
> 好
---
## Address Sanitizer
### 簡介
* [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)
* 動態檢測 C/C++ 記憶體錯誤的工具 (程式執行時分析)
* 錯誤類型︰
* Heap / Stack / Global buffer overflow
* Stack: 儲存函式的區域變數
* Heap: 動態配置變數
* Golbal: 全域
* Use after free/return/scope
* Initialization order bugs
* Memory leaks
### 作業要求
* 開啟 Address Sanitizer，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除
### 測試之前程式
```shell
$ make SANITIZER=1
$ make test
```
* ~~發現原本的100分是假的~~，`trace-17-complexity` 出錯了
* 不合法操作 `READ` 發生了 `global-buffer-overflow` 的錯誤，在 `console.c` 裡的 `simulation` 變數
```
==6540==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55ea3ce4f620 at pc 0x55ea3ce37c3a bp 0x7ffdf55fbd40 sp 0x7ffdf55fbd30
READ of size 4 at 0x55ea3ce4f620 thread T0
#0 0x55ea3ce37c39 in do_option_cmd /home/tiffany/linux2021/lab0-c/console.c:369
#1 0x55ea3ce36a22 in interpret_cmda /home/tiffany/linux2021/lab0-c/console.c:221
#2 0x55ea3ce37207 in interpret_cmd /home/tiffany/linux2021/lab0-c/console.c:244
#3 0x55ea3ce38433 in cmd_select /home/tiffany/linux2021/lab0-c/console.c:594
#4 0x55ea3ce389ad in run_console /home/tiffany/linux2021/lab0-c/console.c:667
#5 0x55ea3ce35531 in main /home/tiffany/linux2021/lab0-c/qtest.c:788
#6 0x7fbf5b4bd0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55ea3ce32b8d in _start (/home/tiffany/linux2021/lab0-c/qtest+0x8b8d)
0x55ea3ce4f621 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55ea3ce4f620) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/tiffany/linux2021/lab0-c/console.c:369 in do_option_cmd
```
#### 關於 global-buffer-overflow
```cpp
// RUN: clang -O -g -fsanitize=address %t && ./a.out
int global_array[100] = {-1};
int main(int argc, char **argv) {
return global_array[argc + 100]; // BOOM
}
```
* argc 一定大於等於 1
* 全域變數 global_array 想存取到超過它被配置的記憶體空間
#### 修改過程
* 打開 `console.c` 找到 `simulation`，發現問題出在 `simulation` 在初始化時是 `boolean` 型態，但在 `add_param` 函式的第二個參數是需要 `integer pointer` 型態，所以它就把 `bool` 強制轉成 `(int *)`，`bool` 配置的記憶體長度是 1 個位元組，而 `int` 則是 4 個位元組，因此發生錯誤
```cpp=
/* --- console.c 原本程式碼 --- */
bool simulation = false;
...
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL);
```
```cpp=
/* --- console.h 原本程式碼 --- */
extern bool simulation;
```
* 將 `simulation` 的初始化改成 `int` 型態
```cpp=
/* --- console.c 更改後程式碼 --- */
int simulation = 0;
...
add_param("simulation", &simulation, "Start/Stop simulation mode", NULL);
```
```cpp=
/* --- console.h 更改後程式碼 --- */
extern int simulation;
```
### 實做作業要求
```shell
$ make SANITIZER=1
$ ./qtest
cmd> help
```
* 不合法操作 `READ` 發生了 `global-buffer-overflow` 錯誤，在 `console.c` 裡的 `echo` 變數
```
==6627==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5592c5c3c400 at pc 0x5592c5c2590f bp 0x7ffefd4bdf40 sp 0x7ffefd4bdf30
READ of size 4 at 0x5592c5c3c400 thread T0
#0 0x5592c5c2590e in do_help_cmd /home/tiffany/linux2021/lab0-c/console.c:307
#1 0x5592c5c25a22 in interpret_cmda /home/tiffany/linux2021/lab0-c/console.c:221
#2 0x5592c5c26207 in interpret_cmd /home/tiffany/linux2021/lab0-c/console.c:244
#3 0x5592c5c2794a in run_console /home/tiffany/linux2021/lab0-c/console.c:660
#4 0x5592c5c24531 in main /home/tiffany/linux2021/lab0-c/qtest.c:788
#5 0x7f23725460b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5592c5c21b8d in _start (/home/tiffany/linux2021/lab0-c/qtest+0x8b8d)
0x5592c5c3c401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5592c5c3c400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/tiffany/linux2021/lab0-c/console.c:307 in do_help_cmd
```
#### 修改過程
* 與上述問題相似
```cpp=
/* --- console.c 原本程式碼 --- */
static bool echo = 0;
...
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
* 將 `echo` 的初始化改成 `int` 型態
```cpp=
/* --- console.c 更改後程式碼 --- */
static int echo = 0;
...
add_param("echo", &echo, "Do/don't echo commands", NULL);
```
---
## Valgrind
### 簡介
* 使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。
### 作業要求
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤
* 並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
### 排除 qtest 實作的記憶體錯誤
#### 執行
```shell
$ make valgrind
```
* 發現每一個測資都會出現以下錯誤訊息
* 訊息中指明
* 有 1 個 16 bytes 的 block 被偵測為 “still reachable”
* 有 19 個 129 bytes 的 block 被偵測為 “still reachable”
* 有 1 個 160 bytes 的 block 被偵測為 “still reachable”
* `still reachable`︰程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
```
==9056== 16 bytes in 1 blocks are still reachable in loss record 1 of 3
==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9056== by 0x4A4F50E: strdup (strdup.c:42)
==9056== by 0x110134: linenoiseHistoryAdd (linenoise.c:1236)
==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325)
==9056== by 0x10C287: main (qtest.c:777)
==9056==
==9056== 129 bytes in 19 blocks are still reachable in loss record 2 of 3
==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9056== by 0x4A4F50E: strdup (strdup.c:42)
==9056== by 0x1100A8: linenoiseHistoryAdd (linenoise.c:1236)
==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325)
==9056== by 0x10C287: main (qtest.c:777)
==9056==
==9056== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==9056== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9056== by 0x1100F4: linenoiseHistoryAdd (linenoise.c:1224)
==9056== by 0x110CC7: linenoiseHistoryLoad (linenoise.c:1325)
==9056== by 0x10C287: main (qtest.c:777)
==9056==
```
#### 修改過程
* 打開 `linenoise.c` 的 1236 行 (下方程式碼的第7行) 發現 `strdup` 函式出現問題
* `strdup` 是可以把要複製的內容複製給沒有初始化的指標，因為它會自動 malloc 給它，但使用結束後應手動 free 記憶體空間
* 程式中 `linecopy` 複製 `line` 的內容，而到後面 `history[history_len]` 又指向 `linecopy` 這個 char pointer，因此這邊的問題應該是出在最後 `history` 的記憶體位置沒有釋放乾淨
```cpp=
/* --- linenoise.c --- */
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
...
linecopy = strdup(line);
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--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
* 找出與變數 `history` 釋放相關的程式碼
==TODO==
### Massif 視覺化記憶體使用量
#### 執行測試
```shell
$ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd
```
* 產生的 massif.out.<pid> 檔，可以用以下指令輸出以文字呈現的圖表，以及詳細內容
```shell
$ ms_print massif.out.<pid>
```
* 也可用 [massif-visualizer](https://github.com/KDE/massif-visualizer) 進行視覺化分析
```shell
$ sudo apt-get install massif-visualizer
$ massif-visualizer massif.out.<pid>
```
#### 設計實驗
==TODO==
Sign in with Wallet
Connect another wallet