# 2021q1 Homework1 (lab0)
contributed by < `gyes00205` >
###### tags: `linux2021`
> [作業要求](https://hackmd.io/@sysprog/linux2021-lab0)
## 開發過程
### q_size
計算 queue 的 size
使用這個方法有個前提，在 insert head 和 tail 時`q->size++`，remove head 和 tail 時`q->size--`，這樣 `q->size` 在 insert 和 remove 時就會更新，不需要再透過 `while` 走訪串列所有節點，時間複雜度從 **$O(n)$** 降為 **$O(1)$**
```cpp
int q_size(queue_t *q)
{
return (!q) ? 0 : q->size;
}
```
:::warning
你應該說明你的考量，畢竟取得 linked list 的有效節點個數的方法很多，但為何要這樣實作。
:notes: jserv
:::
### q_new
初始化 queue_t 的 fields
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_insert_head
將 element 插入 head
`newh->value` malloc 失敗時，要釋放 `newh` 的記憶體，否則會 memory leak
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
int len = strlen(s);
/* TODO: What should you do if the q is NULL? */
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh->value);
free(newh);
return false;
}
memset(newh->value, 0, len + 1);
strncpy(newh->value, s, len);
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (q->size == 0)
q->tail = newh;
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
:::warning
若沒有 memset 初始化字串的話，會產生亂碼 e.g.
cmd> ih dolphin
q = [dolphinU���]
:::
### q_insert_tail
與 q_insert_head 相似，差別在於處理 special case 的方法不同
```cpp
if (q->size == 0) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
```
### q_free
釋放 list elements 和 strings 的記憶體
利用 for 迴圈敘述走訪整個串列的節點，並釋放每個 element 和 string 過去所配置的記憶體空間。
```cpp
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
/* Free queue structure */
if (!q)
return;
for (list_ele_t *cur = q->head; cur;) {
list_ele_t *tmp = cur;
cur = cur->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_remove_head
之前在釋放 tmp 的記憶體空間時，會先 `tmp->next = NULL`，原因是怕會釋放到 `tmp->next` 所指的節點記憶體空間，後來發現這是多餘的行為，因為不會影響到。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *tmp;
int len;
if (!q || q->size == 0)
return false;
tmp = q->head;
len = strlen(tmp->value);
if (sp) {
memset(sp, 0, bufsize);
(bufsize > len) ? strncpy(sp, tmp->value, len)
: strncpy(sp, tmp->value, bufsize - 1);
}
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_reverse
原本的想法是分配記憶體給新的 queue ，將所有節點的 value 複製到新的 queue，最後釋放舊的 queue 的記憶體空間。但因為要求不能分配和釋放記憶體，所以想了下面的方法：
其中`q->tail->next = NULL;` 很重要，避免造成 circular list
```cpp
void q_reverse(queue_t *q)
{
list_ele_t *cur, *tmp;
if (!q || q->size == 0)
return;
q->tail = q->head;
cur = q->head->next;
q->tail->next = NULL;
while (cur) {
tmp = cur->next;
cur->next = q->head;
q->head = cur;
cur = tmp;
}
}
```
### q_sort
參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 merge sort ，需要更改的程式碼為比大小的部份，這次的作業要比較的內容為字串，因此改成 `strcmp(l1->value, l2->value)` ，如果`< 0` 代表`l1`較小，`== 0`代表一樣大，`> 0`代表`l2`較小。
但改完這個部份後仍然會出現 `malloc disallowed` 和 `free disallowed` 的訊息。因此我參考了 [ccs100203](https://hackmd.io/@cccccs100203/linux2020-lab0#q_sort") 的 `q_sort` 實做方法。
在 4～11 行判斷 `head` 為 `l1` 或 `l2` ，並用 `tmp` 和 `q` 指向 `head`，這樣就不需要使用 `malloc` ，直接回傳 `q` 也不需要用到 `free`。
* 第一個版本
需要先判斷 `head` 為 `l1` 或 `l2`
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
// merge with pseudo node
list_ele_t *tmp, *q;
if (strcmp(l1->value, l2->value) < 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
q = tmp;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
tmp->next = l1;
tmp = tmp->next;
l1 = l1->next;
} else {
tmp->next = l2;
tmp = tmp->next;
l2 = l2->next;
}
}
if (l1)
tmp->next = l1;
if (l2)
tmp->next = l2;
return q;
}
```
* 第二個版本
使用 pointer to pointer 的技巧，減少判斷 special case 的部份。並且改成 `strcmp(l1->value, l2->value) <= 0` 確保 merge sort 為 stable 。
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t **indirect, *result = NULL;
indirect = &result;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) <= 0) {
*indirect = l1;
l1 = l1->next;
} else {
*indirect = l2;
l2 = l2->next;
}
indirect = &(*indirect)->next;
}
if (l1)
*indirect = l1;
if (l2)
*indirect = l2;
return result;
}
```
mergeSortList 的主要功能是將 list 分成兩半，while 迴圈敘述會使 fast 指向 list 的尾端，slow 指向 list 的中間，`fast = slow->next;
slow->next = NULL;` 切成兩個 list。
```cpp
list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// 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);
}
```
在經過 mergeSortList 後，我們必須重新尋找 `q->tail` 該指向哪個節點，因為這時候的 list 可能與一開始不同了。但我們也不需要從 `q->head` 走訪整個 list ，我們可以從 `q->tail` 開始走訪就好，因為 `q->tail` 比 `q->head` 離實際的 tail 還要近。
```cpp
void q_sort(queue_t *q)
{
if (!q || q->size == 0)
return;
q->head = mergeSortList(q->head);
while (q->tail->next)
q->tail = q->tail->next;
}
```
### make test 結果
## Valgrind＆Massif-Visualizer
### 安裝 massif-visualizer
`$ sudo snap install massif-visualizer --edge`
### valgrind 使用範例
`$ make valgrind`
得到以下訊息
```cpp
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==42809== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==42809== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42809== by 0x4A4F50E: strdup (strdup.c:42)
==42809== by 0x110135: linenoiseHistoryAdd (linenoise.c:1236)
==42809== by 0x110CC8: linenoiseHistoryLoad (linenoise.c:1325)
==42809== by 0x10C234: main (qtest.c:769)
==42809==
==42809== 95 bytes in 19 blocks are still reachable in loss record 2 of 3
==42809== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42809== by 0x4A4F50E: strdup (strdup.c:42)
==42809== by 0x1100A9: linenoiseHistoryAdd (linenoise.c:1236)
==42809== by 0x110CC8: linenoiseHistoryLoad (linenoise.c:1325)
==42809== by 0x10C234: main (qtest.c:769)
==42809==
==42809== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==42809== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42809== by 0x1100F5: linenoiseHistoryAdd (linenoise.c:1224)
==42809== by 0x110CC8: linenoiseHistoryLoad (linenoise.c:1325)
==42809== by 0x10C234: main (qtest.c:769)
==42809==
--- trace-01-ops 6/6
--- TOTAL 6/6
```
其中 still reachable：程式結束時有未釋放的記憶體，不過卻還有指標指著。`by 0x10C234: main (qtest.c:769)` 應該是在 qtest.c 的第769行發生錯誤。
### valgrind 搭配 massif 工具
```
$ valgrind --tool=massif ./qtest
cmd> new
q = []
cmd> ih RAND 1000
q = [roarxqvtu ebejcv zjhth opgoxhoc sfxgz xepofzzqm sisqldwx kjikdcmom dkgkxclzx mnzkt lntcwqh cvgjhk olddmw xklyr btuvnlhj dfumeo ijnqvze sbkldnucu zxhxer npacsms yaguukrbd orvsyeol veqqgy vocrxtuc ukbpjchgw radblovol ehmiy bcvxb udvae rgnixe ... ]
cmd> sort
q = [aafbh aaspzcvmb aayflw actgvr adrbrwzx aeuycyzz afsbskil ahguc ahiolasch aiqbksnb aivgoxiy ajktmq aksvz aktya akuwybr alnammkfs alsyys amekvu anqqwwee apfbo apnxxfi aqynmq arqkmdz aslkcg aswkkgpxv auxgqp awmoz awyoh aynttepa azklrafr ... ]
cmd> quit
Freeing queue
```
### 使用 massif-visualizer
`$ massif-visualizer`
進入 GUI 界面後，開啟 massif.out.%pid 如下：
## Address Sanitizer
### make SANITIZER=1 錯誤訊息
```
$ make SANITIZER=1
$ ./qtest
cmd> help
```
得到以下訊息
### 解決方法
從上圖中可以發現，問題出在 `variable 'echo'` ，所以觀察 console.c 第 59 行 `static bool echo = 0;` ，在第 108 行又可以發現 `＆echo` 被強制轉型成 `(int*)` 。因此我把 `echo` 的資料型態改成 `int` 並重新執行 `$ make SANITIZER=1` 得到以下訊息
```cpp
==7167==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5587e4b9c5e0 at pc 0x5587e4b837b7 bp 0x7ffc4863a050 sp 0x7ffc4863a040
READ of size 4 at 0x5587e4b9c5e0 thread T0
#0 0x5587e4b837b6 in do_help_cmd /home/gyes00205/linux2021/lab0-c/console.c:307
#1 0x5587e4b838ca in interpret_cmda /home/gyes00205/linux2021/lab0-c/console.c:221
#2 0x5587e4b840af in interpret_cmd /home/gyes00205/linux2021/lab0-c/console.c:244
#3 0x5587e4b857f5 in run_console /home/gyes00205/linux2021/lab0-c/console.c:660
#4 0x5587e4b823e5 in main /home/gyes00205/linux2021/lab0-c/qtest.c:780
#5 0x7f84eb7f20b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5587e4b7fb8d in _start (/home/gyes00205/linux2021/lab0-c/qtest+0x8b8d)
0x5587e4b9c5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5587e4b9c5e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/gyes00205/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
```
於是我又將 console.c 和 console.h 的 `simulation` 改為 `int` 型態，並重新執行 `$ make SANITIZER=1`
這次終於解決 global-buffer-overflow 的問題了。
Sign in with Wallet
Connect another wallet