# 2021q1 Homework1 (lab0)
contributed by < `tigger12613` >
> [作業要求](https://hackmd.io/@sysprog/linux2021-lab0)
## 基本實作
詳細的程式內容請參見 [GitHub](https://github.com/tigger12613/lab0-c)
### Queue structure
``` c
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
* tail: 指向 queue 的尾端，目的是為了 $O(1)$ 的 insert tail
* size: 計算 queue 的大小，目的是為了 $O(1)$ 得到 queue size
### New
新增一個 queue 並且初始化數據
time complexity = $O(1)$
### Free
從頭開始一個一個刪除 element 以及 element 裡的 value
記得要先確認 queue 的存在。然後一個一個
time complexity = $O(n)$
### Insert head/tail
新增一個 element 並且放入 value ， 把 element 放到queue的head/tail
time complexity = $O(1)$
* 我的失誤
* 所有 pointer 都要自己寫入 NULL ， c pointer 並沒有 default value
* 如果第二個 malloc 失敗，要記得 free 第一個 allocated space
* strncpy 並不一定會加上 \0 要手動加上
* 如果 queue 為空，要同時改動head跟tail
### Remove head
刪除 head 指向的 element ， head 指向下一個 element
time complexity = $O(1)$
### Queue size
回傳 queue 的長度，如果沒有 queue return 0
因為有紀錄 size ，所以 time complexity = O(1)
### Reverse queue
反轉 queue
time complexity = $O(n)$
### Sort
我選擇使用 merge sort [參考資料](https://npes87184.github.io/2015-09-12-linkedListSort/)
經過 merge sort 之後 tail 會跑掉，要重新找到 tail
time complexity = $O(nlogn)$
``` c
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;
}
}
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *head = NULL;
list_ele_t *tail = NULL;
while (left && right) {
if (strcmp(left->value, right->value) <= 0) {
if (!head) {
head = left;
tail = left;
} else {
tail->next = left;
tail = left;
}
left = left->next;
} else {
if (!head) {
head = right;
tail = right;
} else {
tail->next = right;
tail = right;
}
right = right->next;
}
}
if (left) {
tail->next = left;
}
if (right) {
tail->next = right;
}
return head;
}
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *left = merge_sort(head);
list_ele_t *right = merge_sort(fast);
return merge(left, right);
}
```
## 小結
通過測資 100/100
## Qtest help error
第一步重現錯誤
``` shell
$ make clean
$ make SANITIZER=1
$ ./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:
=================================================================
==12203==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55fc196ec3c0 at pc 0x55fc196d57bd bp 0x7fff4e970150 sp 0x7fff4e970140
READ of size 4 at 0x55fc196ec3c0 thread T0
#0 0x55fc196d57bc in do_help_cmd /home/tigger/linux2021/lab0-c/console.c:307
#1 0x55fc196d58d0 in interpret_cmda /home/tigger/linux2021/lab0-c/console.c:221
#2 0x55fc196d60b5 in interpret_cmd /home/tigger/linux2021/lab0-c/console.c:244
#3 0x55fc196d77f8 in run_console /home/tigger/linux2021/lab0-c/console.c:660
#4 0x55fc196d43e5 in main /home/tigger/linux2021/lab0-c/qtest.c:780
#5 0x7ff8d7dae0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55fc196d1b8d in _start (/home/tigger/linux2021/lab0-c/qtest+0x8b8d)
0x55fc196ec3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55fc196ec3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/tigger/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac0032d5820: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ac0032d5830: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac0032d5840: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac0032d5850: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac0032d5860: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac0032d5870: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ac0032d5880: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac0032d5890: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac0032d58a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac0032d58b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac0032d58c0: 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
==12203==ABORTING
```
由上面的提示來看應該是下面這段程式出了問題
``` c
while (plist) {
/*這行有錯誤*/
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
plist = plist->next;
}
```
使用 valgrind 分析，出現預期外的問題
```shell=
$make clean
$make SANITIZER=1
$valgrind -q --leak-check=full ./qtest
==24379==ASan runtime does not come first in initial library list; you should either link runtime to your application or manually preload it with LD_PRELOAD.
```
如果在 make 的時候不加上 SANITIZER=1 ，valgrind並未發現記憶體問題
```shell=
$make clean
$make
$valgrind -q --leak-check=full ./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
```
問題出現在 `console.c` 的下面這兩行的 `simulation`, `echo` 都是 `bool` 變數，在轉換成 `int` 會有長度不一樣的問題， `sizeof(int)` = 4, `sizeof(bool)` = 1
``` cpp=104
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",NULL);
```
``` cpp=108
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
我的第一個想法是把 `bool` 轉成 `int` ，但是這種作法無法釋放新增的記憶體，會導致 memory leak
```cpp=673
int* btoi(bool b){
int *tmp = malloc(sizeof(int));
if(!tmp){
return NULL;
}
*tmp = b;
return tmp;
}
```
``` cpp=104
add_param("simulation", btoi(simulation), "Start/Stop simulation mode",NULL);
```
``` cpp=108
add_param("echo", btoi(echo), "Do/don't echo commands", NULL);
```
### Solution
接著我想就直接更改 `simulation`, `echo` 的 type
```cpp=11
extern bool simulation;
```
```cpp=21
bool simulation = 0;
```
```cpp=59
static bool echo = 0;
```
```cpp=11
extern int simulation;
```
```cpp=21
int simulation = 0;
```
```cpp=59
static int echo = 0;
```
更改過後，執行順利，也正確的釋放記憶體
```shell
$ make clean
$ make SANITIZER=1
$ ./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
cmd> quit
Freeing queue
```
Sign in with Wallet
Connect another wallet