# 2020q3 Homework1 (lab0)
contributed by < `dalaoqi` >
## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux tsunghan-VirtualBox 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
每核心執行緒數： 1
每通訊端核心數： 1
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
製程： 10
CPU MHz： 3696.002
BogoMIPS: 7392.00
Hypervisor 供應商： KVM
虛擬型態： 全部
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 12288K
NUMA node0 CPU(s)： 0
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_known_freq pni pclmulqdq monitor ssse3 cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_single pti fsgsbase avx2 invpcid rdseed clflushopt md_clear flush_l1d
```
## 使用工具
* Git pre-commit hook
* Valgrind: 動態程式分析工具
* AddressSanitizer: 記憶體使用分析
## 作業要求
於 `queue.[c/h]` 中完成下列功能
* `q.new`
* `q.free`
* `q.insert head`
* `q.insert tail`
* `q.remove head`
* `q.size`
* `q.reverse`
* 功能需要在 $O(1)$ 時間內執行
## 開發過程
### `queue.h`
作業要求有一項是要在 queue 的尾端新增元素，而且限制要在 $O(1)$ 時間內執行完畢。若每次都從頭開始iterate到尾巴，這樣的時間複雜度為 $O(N)$ ，不符合要求，因此需要在 `queue.h` 新增 `list_ele_t *tail` 到 `struct queue_t` 。`list_ele_t *tail` 的目的是紀錄 queue 的尾端，如此一來當執行 `q.insert tail` 就能夠在 $O(1)$ 時間內執行完畢。
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### `queue.c`
#### `q_size`
因需要滿足 $O(1)$ 時間複雜度，因此在 `queue.h` 新增 `int size` 到 `struct queue_t`。如此，呼叫此函式可以直接回傳大小。
```cpp
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
```
#### `q_new`
根據上述的結果， `q_new` 就會長成這樣，目的為當新的 queue 分配到新的記憶體空間後，需要做初始化的動作。
```cpp
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### `q_free`
釋放 queue 中所有節點以及節點內所使用到的記憶體。
原本一開始提交的 code 是長得像下面這樣：
```cpp
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q) {
return;
}
list_ele_t *tmp;
while (q->head) {
tmp = q->head;
tmp->next = NULL;
q->head = q->head->next;
free(tmp->next);
free(tmp);
}
free(q);
}
```
結果在 `$ git commit` 的時候出現下列的錯誤：
```shell
Following files need to be cleaned up:
queue.c
queue.c:30:17: style: The scope of the variable 'tmp' can be reduced. [variableScope]
list_ele_t *tmp;
^
Fail to pass static analysis.
```
這個錯誤就是說， `*tmp` 在宣告的這個 scope 中沒有被使用到，所以把 `list_ele_t *tmp;` 移動到 while 迴圈中就可以解決，如下所示。
```cpp
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q) {
return;
}
while (q->head) {
list_ele_t *tmp = q->head;
tmp->next = NULL;
q->head = q->head->next;
free(tmp->next);
free(tmp);
}
free(q);
}
```
:::info
在差不多完成 `q_sort()` 後，預期的 test 分數應該要往上衝才對，但是很遺憾的只有42/100，出現的錯誤大多是
```shell
ERROR: Freed queue, but xxx blocks are still allocated
```
直覺是 `q_free` 那裡有問題，果然在針對 value 釋放記憶體的時候誤打成 next 了...
修改完後，得到71/100，還有下列錯誤需要處理。
```shell
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
:::
#### `q_insert_head`
從 queue 的 head 插入一個新的 node ，若 queue 為 NULL 或是在分配空間時沒有成功分配的話，需要 return false 且釋放新分配的記憶體空間。在 `q->tail` 為 NULL 時也要將它指向新的節點。
在作業的說明中有提到
>依據 CERN [Common vulnerabilities guide for C programmers
](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 gets / sprintf / strcpy 等不安全的函式;
將原本要使用的 `strcpy` 改為 CERN 所提供替代方案 `strlcpy` ，不過不是 BSD system ，所以又更改為 `snprintf` 函式進行操作。
```cpp
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;
}
size_t length = strlen(s) + 1;
newh->value = (char *) malloc(length * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
snprintf(newh->value, length, "%s", s);
newh->next = q->head;
q->head = newh;
if (!q->tail) {
q->tail = newh;
}
q->size++;
return true;
}
```
#### `q_remove_head`
將 queue 中的第一個 node (head) 移除，若成功移除則回傳 true ，若 queue 為空或 NULL ，則回傳 false 。如果 `sp` 不是 NULL 且節點移除成功，需要將被移除的節點中的值存放在 `sp` 中， `sp` 的最後一位為 null terminator。
```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) {
snprintf(sp, bufsize, "%s", tmp->value);
}
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
#### `q_reverse`
原本 `q_reverse` 是以下方的方式執行：
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
list_ele_t *tmp = NULL;
q->tail->next = q->head;
while (tmp != q->tail) {
tmp = q->head->next;
q->head->next = tmp->next;
tmp->next = q->tail->next;
q->tail->next = tmp;
}
tmp->next = q->tail->next;
q->tail = q->head;
q->tail->next = NULL;
q->head = tmp;
return;
}
```
但在做 test 時在 trace-03 發生超時錯誤
```shell
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Removed value dolphin != expected value squirrel
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Removed value vulture != expected value gerbil
Error limit exceeded. Stopping command execution
```
經過調整測試修改 while 迴圈的條件可以減少程式執行的時間
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
list_ele_t *tmp = NULL;
q->tail->next = q->head;
while (q->head->next != q->tail) {
tmp = q->head->next;
q->head->next = tmp->next;
tmp->next = q->tail->next;
q->tail->next = tmp;
}
q->tail = q->head;
q->tail->next = NULL;
q->head = tmp;
return;
}
```
但執行 test 時 trace-03 還是發生錯誤，推斷 `q_reverse` 還是沒有寫好。
```shell
ERROR: Removed value bear != expected value squirrel
ERROR: Removed value meerkat != expected value gerbil
ERROR: Removed value gerbil != expected value bear
ERROR: Removed value vulture != expected value meerkat
ERROR: Removal from queue failed (1 failures total)
Error limit exceeded. Stopping command execution
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
為了驗證上述的推論，我試著執行下面的指令，運行的結果是正確的
```shell
new
ih dolphin
ih bear
ih gerbil
rh gerbil
rh bear
rh dolphin
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
```
回去看 `q_reverse` 函式，發現在 tail 的那個節點會被遺漏，因此再修改一次 while 迴圈的條件，也順便將 Segmentation fault 修好（ tmp 在宣告的時候給值）。
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
list_ele_t *tmp = q->head->next;
q->tail->next = q->head;
while (tmp != q->tail) {
q->head->next = tmp->next;
tmp->next = q->tail->next;
q->tail->next = tmp;
tmp = q->head->next;
}
q->tail = q->head;
q->tail->next = NULL;
q->head = tmp;
return;
}
```
#### `q_sort`
使用 mergeSort 當作排序的演算法，參考 [npes87184](https://npes87184.github.io/2015-09-12-linkedListSort/) 方式，修改成可作為字串比較的函式。
* `merge` 函式
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
size_t len_l1 = strlen(l1->value), len_l2 = strlen(l2->value);
if (len_l1 < len_l2) {
len_l1 = len_l2;
}
if (strncmp(l1->value, l2->value, len_l1) <= 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1->next, l1);
return l2;
}
}
```
* `mergeSort` 主程式
```cpp
/*
* mergeSort for q_sort()
*/
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);
}
```
* `q_sort`
```cpp
/*
* 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.
*/
void q_sort(queue_t *q)
{
if (!q || !q->head) {
return;
}
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
以上函式完成應當在 test 的時候會全部 pass ，結果如下
```shell
$ make test
```
分數結果如下：
<font color=Green>trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6</font>
<font color=Red>trace-04-ops 0/6
trace-05-ops 0/5
trace-06-string 0/6</font>
<font color=Green>trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-per 6/6
trace-14-per 6/6</font>
<font color=Red>trace-15-per 0/6
trace-16-per 0/6</font>
<font color=Green>trace-17-complexity 5/5</font>
<font color=Red>TOTAL 71/100</font>
於是，我去看 trace-04-ops 指令並用 `$ valgrind ./qtest` 做測試：
```
cmd> new
cmd> new
q = []
cmd> ih gerbil
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> it meerkat
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> sort
```
在 sort 時結果出現錯誤：
```shell
==17829== Invalid read of size 8
==17829== at 0x109D22: do_sort (qtest.c:561)
==17829== by 0x10BA22: interpret_cmda (console.c:220)
==17829== by 0x10BF96: interpret_cmd (console.c:243)
==17829== by 0x10C705: cmd_select (console.c:607)
==17829== by 0x10C7AC: run_console (console.c:628)
==17829== by 0x10AED1: main (qtest.c:772)
==17829== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==17829==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
==17829== 5 bytes in 1 blocks are still reachable in loss record 1 of 32
==17829== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17829== by 0x10B642: strsave_or_fail (report.c:230)
==17829== by 0x10BF56: parse_args (console.c:190)
==17829== by 0x10BF56: interpret_cmd (console.c:242)
==17829== by 0x10C705: cmd_select (console.c:607)
==17829== by 0x10C7AC: run_console (console.c:628)
==17829== by 0x10AED1: main (qtest.c:772)
==17829==
==17829== 8 bytes in 1 blocks are still reachable in loss record 2 of 32
==17829== at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17829== by 0x10B59F: calloc_or_fail (report.c:208)
==17829== by 0x10BF27: parse_args (console.c:187)
==17829== by 0x10BF27: interpret_cmd (console.c:242)
==17829== by 0x10C705: cmd_select (console.c:607)
==17829== by 0x10C7AC: run_console (console.c:628)
==17829== by 0x10AED1: main (qtest.c:772)
...
```
猜測是在執行 `q_sort` 時發生問題，進一步檢查發現在 merge 時候有誤
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
size_t len_l1 = strlen(l1->value), len_l2 = strlen(l2->value);
if (len_l1 < len_l2) {
len_l1 = len_l2;
}
if (strncmp(l1->value, l2->value, len_l1) <= 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
//這行
l2->next = merge(l1, l2->next);
return l2;
}
}
```
除完蟲之後再執行一次 `$ make test`
<font color=Green> trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5</font>
<font color=Red> trace-06-string 0/6 </font>
<font color=Green> trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-per 6/6
trace-14-per 6/6 </font>
<font color=Red> trace-15-per 0/6 </font>
<font color=Green> trace-16-per 6/6
trace-17-complexity 5/5 </font>
<font color=Red>TOTAL 88/100 </font>
我去看 trace-06-string 指令並用 `valgrind ./qtest` 做測試，發現說如果 queue 在只有一個元素的狀況下做 `q_reverse` 會有下列錯誤：
```shell
==18020== Invalid read of size 8
==18020== at 0x10CE68: q_reverse (queue.c:159)
==18020== by 0x109EA2: do_reverse (qtest.c:463)
==18020== by 0x10BA22: interpret_cmda (console.c:220)
==18020== by 0x10BF96: interpret_cmd (console.c:243)
==18020== by 0x10C705: cmd_select (console.c:607)
==18020== by 0x10C7AC: run_console (console.c:628)
==18020== by 0x10AED1: main (qtest.c:772)
==18020== Address 0x8 is not stack'd, malloc'd or (recently) free'd
==18020==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
==18020== 8 bytes in 1 blocks are still reachable in loss record 1 of 30
==18020== at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18020== by 0x10B59F: calloc_or_fail (report.c:208)
==18020== by 0x10BF27: parse_args (console.c:187)
==18020== by 0x10BF27: interpret_cmd (console.c:242)
==18020== by 0x10C705: cmd_select (console.c:607)
==18020== by 0x10C7AC: run_console (console.c:628)
==18020== by 0x10AED1: main (qtest.c:772)
==18020==
==18020== 8 bytes in 1 blocks are still reachable in loss record 2 of 30
==18020== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18020== by 0x10B642: strsave_or_fail (report.c:230)
==18020== by 0x10BF56: parse_args (console.c:190)
==18020== by 0x10BF56: interpret_cmd (console.c:242)
==18020== by 0x10C705: cmd_select (console.c:607)
==18020== by 0x10C7AC: run_console (console.c:628)
==18020== by 0x10AED1: main (qtest.c:772)
...
```
所以再去修改 `q_reverse`，在一開始的判斷式內新增 `q->size == 1` 的情況。修改完後重新執行 `make test`
<font color=Green> trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5
trace-06-string 6/6
trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-perf 6/6
trace-14-perf 6/6 </font>
<font color=Red> trace-15-perf 0/6 </font>
<font color=Green> trace-16-perf 6/6
trace-17-complexity 5/5 </font>
<font color=Red>TOTAL 94/100 </font>
使用 AddressSanitizer 找問題，執行
```
$ make SANITIZER=1
$ make test
```
發現下列錯誤：
```
==20647==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdd6d22fc8 (pc 0x7f1678355576 bp 0x7ffdd6d23850 sp 0x7ffdd6d22fd0 T0)
#0 0x7f31776f8e6e (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x59e6e)
#1 0x562475d82e44 in merge /home/tsunghan/linux2020/lab0-c/queue.c:178
#2 0x562475d82ebd in merge /home/tsunghan/linux2020/lab0-c/queue.c:179
#3 0x562475d82ebd in merge /home/tsunghan/linux2020/lab0-c/queue.c:179
#4 0x562475d82ebd in merge /home/tsunghan/linux2020/lab0-c/queue.c:179
```
結果是堆疊溢位，需要把 `q_sort` 修改成不需要遞迴的做法。參考 [Method 2 (Using Local References) ](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/) 方式做修改再重新執行指令。
<font color=Green> trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5
trace-06-string 6/6
trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-perf 6/6
trace-14-perf 6/6 </font>
<font color=Red> trace-15-perf 0/6 </font>
<font color=Green> trace-16-perf 6/6
trace-17-complexity 5/5 </font>
<font color=Red>TOTAL 94/100 </font>
```
==8384==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x56075bc7c4f5 bp 0x7ffd69807750 sp 0x7ffd69807740 T0)
==8384==The signal is caused by a READ memory access.
==8384==Hint: address points to the zero page.
#0 0x56075bc7c4f4 in do_sort /home/tsunghan/linux2020/lab0-c/qtest.c:561
#1 0x56075bc7f68a in interpret_cmda /home/tsunghan/linux2020/lab0-c/console.c:220
```
錯誤是來自於嘗試去存取一些不合法的記憶體位址，如未被分配出的空間。
在 `merge` 函式中的比較字串大小的地方使用的是 `strncmp` ，兩個字串的比較長度以最長的那個為準，所以在存取較短的字串時就有可能存取到不合法的空間。將之改成 `strcmp`，就可以解決，因為他是比兩字串的字串直到碰到結尾 '\0' 。
```shell
$ make test
```
<font color=Green> trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5
trace-06-string 6/6
trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-perf 6/6
trace-14-perf 6/6
trace-15-perf 6/6
trace-16-perf 6/6
trace-17-complexity 5/5
TOTAL 100/100 </font>
```shell
$ make valgrind
```
<font color=Green> trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5
trace-06-string 6/6
trace-07-robust 6/6
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-perf 6/6
trace-14-perf 6/6
trace-15-perf 6/6
trace-16-perf 6/6
trace-17-complexity 5/5
TOTAL 100/100 </font>
## 程式優化&除錯
紀錄在實作過程中，遇到的非個人實作部份的問題。
如下方在執行 `./qtest -f traces/trace-17-complexity.cmd
` 時在執行到 `option simulation 1` 會發生 `global-buffer-overflow` 錯誤，存取到非法的記憶體空間。
```
==17371==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55d74f604a00 at pc 0x55d74f3f591e bp 0x7fff3a083930 sp 0x7fff3a083920
READ of size 4 at 0x55d74f604a00 thread T0
#0 0x55d74f3f591d in do_option_cmd /home/tsunghan/linux2020/lab0-c/console.c:368
#1 0x55d74f3f453a in interpret_cmda /home/tsunghan/linux2020/lab0-c/console.c:220
#2 0x55d74f3f4f3e in interpret_cmd /home/tsunghan/linux2020/lab0-c/console.c:243
#3 0x55d74f3f5c27 in cmd_select /home/tsunghan/linux2020/lab0-c/console.c:569
#4 0x55d74f3f6044 in run_console /home/tsunghan/linux2020/lab0-c/console.c:628
#5 0x55d74f3f315d in main /home/tsunghan/linux2020/lab0-c/qtest.c:772
#6 0x7fb2cc42cb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
#7 0x55d74f3f08b9 in _start (/home/tsunghan/linux2020/lab0-c/qtest+0x68b9)
0x55d74f604a01 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55d74f604a00) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/tsunghan/linux2020/lab0-c/console.c:368 in do_option_cmd
Shadow bytes around the buggy address:
0x0abb69eb88f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abb69eb8900: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abb69eb8910: 00 00 00 00 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0abb69eb8920: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0abb69eb8930: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
=>0x0abb69eb8940:[01]f9 f9 f9 f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9
0x0abb69eb8950: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0abb69eb8960: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abb69eb8970: 00 00 00 00 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
0x0abb69eb8980: f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0abb69eb8990: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
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
==17371==ABORTING
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
為了排除這個錯誤，去 `console.c` 中找到宣告為 bool 型態 simulation 變數。 但在 `init_cmd()` 函式初始化參數中，是以 `int` 型態去讀取 simulation 的記憶體位址。
```cpp
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL);
```
原因是因為當初 simulation 時是以 bool 型態來做宣告 (1 byte)，但在 `init_cmd()` 中，為配合 `add_param()` 函式，在讀 simulation 時強制轉型為 int* 型態 (4 bytes)，造成在讀取的時候超出可讀取的範圍。所以將 simulation 型態改成 int 型態就可以解決這項錯誤。
## Valgrind Massif 實驗
練習使用 Valgrind 搭配 Massif，參考 [massif官方說明](https://valgrind.org/docs/manual/ms-manual.html) 操作。
massif 為 heap profiler，可以分析並記錄我們程式的 heap 使用量。
操作方式為指定工具 massif
```shell
$ valgrind --tool=massif 執行程式
```
執行完後，當前資料夾底下會出現 massif.out.<執行程式 PID>， 透過 `ms_print` 顯示分析結果
```shell
$ ms_print massif.out.<執行程式 PID>
```
以 trace-16-perf.cmd 為範例：
```shell
--------------------------------------------------------------------------------
Command: ./qtest -f ./traces/trace-16-perf.cmd
Massif arguments: (none)
ms_print arguments: massif.out.4265
--------------------------------------------------------------------------------
MB
12.83^ #############
| # ::::::::::
| ::# :: :
| :::# :: :
| :::# :: ::
| :::::# :: ::
| ::::::# :: ::
| @::::::# :: ::
| :@::::::# :: ::
| @:@::::::# :: ::
| @@@@@@@::::: :@:@::::::# :: ::
| :@ : : ::@:@::::::# :: ::
| :@ : : :::@:@::::::# :: :::
| :::@ : : ::::@:@::::::# :: :::
| :::@ : : @::::@:@::::::# :: ::@
| :::::@ : : :@::::@:@::::::# :: ::@
| :::::@ : : :::@::::@:@::::::# :: ::@
| :::::::@ : : ::::@::::@:@::::::# :: ::@
| @: ::::::::@ : : ::::@::::@:@::::::# :: ::@
| @: :::::::::@ : :: :::::@::::@:@::::::# :: ::@
0 +----------------------------------------------------------------------->Mi
0 495.3
Number of snapshots: 61
Detailed snapshots: [2, 18, 29, 35, 38, 47 (peak), 57]
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
0 0 0 0 0 0
1 7,457,859 643,248 499,627 143,621 0
2 15,767,905 1,354,744 1,050,291 304,453 0
77.53% (1,050,291B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->76.78% (1,040,189B) 0x10C7CE: test_malloc (harness.c:137)
| ->41.34% (560,000B) 0x10CC2B: q_insert_head (queue.c:52)
| | ->41.34% (560,000B) 0x10A864: do_insert_head (qtest.c:212)
| | ->41.34% (560,000B) 0x10B9CD: interpret_cmda (console.c:220)
| | ->41.34% (560,000B) 0x10BF41: interpret_cmd (console.c:243)
| | ->41.34% (560,000B) 0x10C50F: cmd_select (console.c:569)
| | ->41.34% (560,000B) 0x10C757: run_console (console.c:628)
| | ->41.34% (560,000B) 0x10AE7C: main (qtest.c:772)
| |
| ->35.44% (480,125B) 0x10CC52: q_insert_head (queue.c:57)
| | ->35.44% (480,125B) 0x10A864: do_insert_head (qtest.c:212)
| | ->35.44% (480,125B) 0x10B9CD: interpret_cmda (console.c:220)
| | ->35.44% (480,125B) 0x10BF41: interpret_cmd (console.c:243)
| | ->35.44% (480,125B) 0x10C50F: cmd_select (console.c:569)
| | ->35.44% (480,125B) 0x10C757: run_console (console.c:628)
| | ->35.44% (480,125B) 0x10AE7C: main (qtest.c:772)
| |
| ->00.00% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->00.75% (10,102B) in 1+ places, all below ms_print's threshold (01.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
3 23,453,176 1,354,656 1,050,261 304,395 0
4 28,845,644 1,354,656 1,050,261 304,395 0
5 36,050,846 493,792 384,107 109,685 0
6 40,597,339 893,616 693,605 200,011 0
7 47,999,774 1,544,176 1,196,899 347,277 0
8 53,713,837 2,047,696 1,585,950 461,746 0
9 58,710,600 2,487,960 1,926,667 561,293 0
10 65,134,400 3,052,248 2,363,619 688,629 0
11 70,488,913 3,523,224 2,728,127 795,097 0
12 74,773,885 3,900,288 3,019,744 880,544 0
13 80,844,693 4,433,200 3,432,074 1,001,126 0
14 85,484,153 4,841,568 3,748,130 1,093,438 0
15 91,194,395 5,343,664 4,137,005 1,206,659 0
16 94,765,012 5,658,096 4,380,328 1,277,768 0
17 100,832,364 6,192,128 4,793,704 1,398,424 0
18 107,970,808 6,730,104 5,210,146 1,519,958 0
77.42% (5,210,146B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->77.27% (5,200,044B) 0x10C7CE: test_malloc (harness.c:137)
| ->41.60% (2,800,000B) 0x10CC2B: q_insert_head (queue.c:52)
（略）
```
massif 會在程式執行期間製作多個 snapshots，顯示程式 heap memory 執行時期的使用量。其中：
* :, Normal snapshot
* @, Detail snapshot
* #, Peak snapshot
若程式有正確釋放記憶體，會看到最終記憶體使用量會回到0。
透過 massif ，我們可以分析程式 heap 的用量，並透過 stack trace，優化程式。
透過 massif-visulizer 視覺化的結果：
把 `q_free` 拿掉，發現直到程式結束前記憶體用量都沒有下降，造成 memory leak。
Sign in with Wallet
Connect another wallet