# 2021q1 Homework1 (lab0)
contributed by < `cyrong` >
## 實作過程
為了讓 `q_size` 以及 `q_insert_tail` 時間複雜度為 $O(1)$
修改 `queue.h`
新增 size 以及 tail 兩個元素
```c
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
int size; /* Size of linked list */
list_ele_t *tail; /* Tail of linked list */
} queue_t;
```
### `q_new()`
建立一個 `queue` 如果成功回傳此 `queue` 否則回傳 `NULL`
先 `malloc` 給 `q`
檢查 `malloc` 有無成功
成功就初始 `q` ， head : `NULL` 、 tail : `NULL` 、 size : `0`
失敗就回傳 `NULL`
```c
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->size = 0;
q->tail = NULL;
}
return q;
}
```
### `q_free()`
釋放 `q` 中所有分配的記憶體
檢查 `q` 是否為 `NULL`
釋放 字串 -> 釋放 元素 -> 釋放 `q`
```c
void q_free(queue_t *q)
{
if (q) {
list_ele_t *tmp = q->head;
while (q->head) {
q->head = q->head->next;
free(tmp->value);
free(tmp);
tmp = q->head;
}
} else
return;
free(q);
}
```
### `q_insert_head()`
從頭插入一個元素
檢查 `q` 以及分配的 `newh`, `newh->value` 是否為 `NULL`
再來就是把 `newh` 加進 `q`
若是 `q` 中沒有元素， `q->tail` 也要作設定
最後 `q->size += 1`
```c
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = 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 += 1;
return true;
}
```
### `q_insert_tail()`
從尾端插入一個元素
整體來說與 `q_insert_head()` 差不多
最後加到 `tail` 的話要把原本 `tail->next` 設定成 `newt`
```c
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = 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 += 1;
return true;
}
```
### `q_remove_head()`
從 `head` 移除一個元素，成功時回傳 `true` 否則回傳 `false`
檢查 `q` 是否是 `NULL`
再來才是檢查 `head` 、 `tail` 為了 `q` 是 `NULL` 時 `dereference` 到 `NULL`
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q)
return false;
if (q->size == 0)
return false;
list_ele_t *tmp = q->head;
if (sp) {
int maxlen = bufsize - 1 > strlen((q->head)->value)
? strlen((q->head)->value)
: bufsize - 1;
strncpy(sp, (q->head)->value, maxlen);
sp[maxlen] = '\0';
}
q->head = tmp->next;
q->size -= 1;
free(tmp->value);
free(tmp);
return true;
}
```
### `q_size()`
回傳 `q` 的元素個數
若 `q` 是 `empty` 或 `NULL` 回傳 `0` 否則回傳元素個數
```c
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
### `q_reverse()`
將 `q` 中的元素順序反轉
```c
void q_reverse(queue_t *q)
{
if (!q)
return;
if (q->size <= 1)
return;
list_ele_t *prev = NULL;
list_ele_t *cur = q->head;
list_ele_t *next = NULL;
q->tail = q->head;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
q->head = prev;
}
```
### `q_sort`
利用的 sort 手法是 mergesort
因此新增 `merge` 與 `mergeSortList` 兩個函式
其中 `merge` 使用的是 iterative 版本
使用 recursive 版本會導致自動評分程式複雜度測試 fail
應該是重複呼叫函式的成本過高
```c
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *result;
list_ele_t **tmp = &result;
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 result;
}
```
```c
list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head)
return head;
if (!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 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
return merge(l1, l2);
}
```
[參考文章](https://npes87184.github.io/2015-09-12-linkedListSort/)
## 使用Address Sanitizer
開啟 Address Sanitizer 後
執行 `qtest`
並在 cmd 輸入 help 會得到以下錯誤
```c
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:
=================================================================
==19783==ERROR: AddressSanitizer: global-buffer-overflow on address 0x562cb765a3c0 at pc 0x562cb76437bd bp 0x7ffde7d1b7a0 sp 0x7ffde7d1b790
READ of size 4 at 0x562cb765a3c0 thread T0
#0 0x562cb76437bc in do_help_cmd /home/amagi/linux2021/lab0-c/console.c:307
#1 0x562cb76438d0 in interpret_cmda /home/amagi/linux2021/lab0-c/console.c:221
#2 0x562cb76440b5 in interpret_cmd /home/amagi/linux2021/lab0-c/console.c:244
#3 0x562cb76457f8 in run_console /home/amagi/linux2021/lab0-c/console.c:660
#4 0x562cb76423e5 in main /home/amagi/linux2021/lab0-c/qtest.c:780
#5 0x7f3263fd60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x562cb763fb8d in _start (/home/amagi/linux2021/lab0-c/qtest+0x8b8d)
0x562cb765a3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x562cb765a3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/amagi/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac616ec3420: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ac616ec3430: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac616ec3440: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac616ec3450: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac616ec3460: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac616ec3470: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ac616ec3480: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac616ec3490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac616ec34a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac616ec34b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac616ec34c0: 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
==19783==ABORTING
```
從中可以發現是 `console.c` 有問題
看到 summary 的地方發現是 global variable '`echo`' 發生了錯誤
進入 `console.c` 觀察 `echo`
```c
/* Parameters */
static int err_limit = 5;
static int err_cnt = 0;
static bool echo = 0;
```
`echo` 型態是 `bool`
接下來繼續尋找 `echo` 的足跡
在函式 `init_cmd()` 中
```c
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
函式 `set_echo` 中
```c
void set_echo(bool on)
{
echo = on ? 1 : 0;
}
```
其餘出現部份都是在 if 中因此不會改變到 `echo` 的值
其中 `set_echo()` 看起來沒什麼問題
因此聚焦在 `add_param`
```c
void add_param(char *name,
int *valp,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_list;
while (next_param && strcmp(name, next_param->name) > 0) {
last_loc = &next_param->next;
next_param = next_param->next;
}
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
ele->name = name;
ele->valp = valp;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
```
功能是最終建立一個 element 並指派到 `last_loc`
type 是 `param_ptr`
因此前去觀察 `param_ptr`
在 `console.h` 中
```c
/* 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;
};
```
從中觀察到對 `echo` 進行數值指派之處在 `valp` ，type 是 `int *`
但是傳入 `add_param` 的 `echo` 是被強制轉變成 `int *` 的 `bool`
導致後續使用到 `last_loc` 的地方
看到一開始標出的錯誤位置
```c
#0 0x562cb76437bc in do_help_cmd /home/amagi/linux2021/lab0-c/console.c:307
```
```c
static bool do_help_cmd(int argc, char *argv[])
{
cmd_ptr clist = cmd_list;
report(1, "Commands:", argv[0]);
while (clist) {
report(1, "\t%s\t%s", clist->name, clist->documentation);
clist = clist->next;
}
param_ptr plist = param_list;
report(1, "Options:");
while (plist) {
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, //<-- here 307
plist->documentation);
plist = plist->next;
}
return true;
}
```
`*plist->valp` 的部份出錯了
因此初步判斷是 `echo` 的 type 問題
因為 type `bool` 占的空間和 `int` 不一樣 (`bool` 1 byte `int` 4 bytes)
`%d` 會去存取的大小會是 `int` 的大小 所以存取身為 `bool` 的 `echo` 會超出記憶體範圍
修改成以下的樣子
```c
static int echo = 0;
```
而執行 `make test` 時也出現相同狀況
```c
amagi@amagi-MacBookAir:~/linux2021/lab0-c$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
=================================================================
==19755==ERROR: AddressSanitizer: global-buffer-overflow on address 0x56197ae895e0 at pc 0x56197ae71ae8 bp 0x7ffe3caddf50 sp 0x7ffe3caddf40
READ of size 4 at 0x56197ae895e0 thread T0
#0 0x56197ae71ae7 in do_option_cmd /home/amagi/linux2021/lab0-c/console.c:369
#1 0x56197ae708d0 in interpret_cmda /home/amagi/linux2021/lab0-c/console.c:221
#2 0x56197ae710b5 in interpret_cmd /home/amagi/linux2021/lab0-c/console.c:244
#3 0x56197ae722e1 in cmd_select /home/amagi/linux2021/lab0-c/console.c:594
#4 0x56197ae7285b in run_console /home/amagi/linux2021/lab0-c/console.c:667
#5 0x56197ae6f3e5 in main /home/amagi/linux2021/lab0-c/qtest.c:780
#6 0x7f45471c70b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x56197ae6cb8d in _start (/home/amagi/linux2021/lab0-c/qtest+0x8b8d)
0x56197ae895e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x56197ae895e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/amagi/linux2021/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
0x0ac3af5c9260: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3af5c9270: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3af5c9280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3af5c9290: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac3af5c92a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ac3af5c92b0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9
0x0ac3af5c92c0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
0x0ac3af5c92d0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac3af5c92e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3af5c92f0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ac3af5c9300: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 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
Shadow gap: cc
==19755==ABORTING
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
觀察 `simulation`
```c
/* Some global values */
bool simulation = 0;
```
在 `init_cmd`
```c
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);
```
型態 `bool` 並被強制轉換 `int *`
看起來與 `echo` 是相同問題
因此修改 `console.c` 以及 `console.h`
`console.c` ：
```c
/* Some global values */
int simulation = 0;
```
`console.h` ：
原
```c
/* Simulation flag of console option */
extern bool simulation;
```
修改後
```c
/* Simulation flag of console option */
extern int simulation;
```
最終執行結果：
```c
./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
```
```c
make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
## 使用[Valgrind](https://valgrind.org/)
執行以下命令
```shell
make valgrind
```
會得到以下訊息
```c
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory 'lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o linenoise.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .linenoise.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
make[1]: Leaving directory 'lab0-c'
cp qtest /tmp/qtest.BK0T2K
chmod u+x /tmp/qtest.BK0T2K
sed -i "s/alarm/isnan/g" /tmp/qtest.BK0T2K
scripts/driver.py -p /tmp/qtest.BK0T2K --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==21222== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==21222== by 0x4A4C50E: strdup (strdup.c:42)
==21222== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236)
==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==21222== by 0x10C22C: main (qtest.c:769)
==21222==
==21222== 95 bytes in 19 blocks are still reachable in loss record 2 of 3
==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==21222== by 0x4A4C50E: strdup (strdup.c:42)
==21222== by 0x11000E: linenoiseHistoryAdd (linenoise.c:1236)
==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==21222== by 0x10C22C: main (qtest.c:769)
==21222==
==21222== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==21222== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==21222== by 0x11005A: linenoiseHistoryAdd (linenoise.c:1224)
==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==21222== by 0x10C22C: main (qtest.c:769)
==21222==
--- trace-01-ops 6/6
...
```
以下還有更多訊息 不過大多數合 trace-01 一樣的問題
可以關注這幾段
```c
==21222== by 0x4A4C50E: strdup (strdup.c:42)
==21222== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236)
==21222== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==21222== by 0x10C22C: main (qtest.c:769)
```
追蹤出現問題的地方
`linenoiseHistory`
```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);
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); //<-here 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--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
`linenoiseHistoryLoad`
```c
int linenoiseHistoryLoad(const char *filename)
{
FILE *fp = fopen(filename, "r");
char buf[LINENOISE_MAX_LINE];
if (fp == NULL)
return -1;
while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
char *p;
p = strchr(buf, '\r');
if (!p)
p = strchr(buf, '\n');
if (p)
*p = '\0';
linenoiseHistoryAdd(buf); //<-here 1325
}
fclose(fp);
return 0;
}
```
`main`
```c
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE);// <-here 769
```
而 `strdup` 在 `string.h`
still reachable 代表的是有東西還沒 free
主要原因是輸入方式
手動輸入命令和自命令歷史記錄檔案 `history` 讀取的輸入會不一樣
輸入命令會把命令寫進 `history`
在 `run_console` 中可以發現這一點
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
其中的 `has_infile` 條件判斷裡可以發現這一點
`linenoiseFree` 也是在沒有檔案的情況下作
因此推測此 memory error 與是否有讀檔有關
作以下實驗
自行輸入 `trace-eg.cmd` 中的命令 和 讀檔
讀檔
```shell
$ valgrind --leak-check=yes ./qtest -v 3 -f traces/trace-eg.cmd
cmd>
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
q = [gerbil bear dolphin meerkat]
cmd> it bear
q = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
q = [bear meerkat dolphin bear gerbil]
cmd> # See how long it is
cmd> size
Queue size = 5
q = [bear meerkat dolphin bear gerbil]
cmd> # Delete queue. Goes back to a NULL queue.
cmd> free
q = NULL
cmd> # Exit program
cmd> quit
Freeing queue
==29205== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==29205== by 0x4A4C50E: strdup (strdup.c:42)
==29205== by 0x11009A: linenoiseHistoryAdd (linenoise.c:1236)
==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==29205== by 0x10C22C: main (qtest.c:770)
==29205==
==29205== 91 bytes in 19 blocks are still reachable in loss record 2 of 3
==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==29205== by 0x4A4C50E: strdup (strdup.c:42)
==29205== by 0x11000E: linenoiseHistoryAdd (linenoise.c:1236)
==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==29205== by 0x10C22C: main (qtest.c:770)
==29205==
==29205== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==29205== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==29205== by 0x11005A: linenoiseHistoryAdd (linenoise.c:1224)
==29205== by 0x110C2D: linenoiseHistoryLoad (linenoise.c:1325)
==29205== by 0x10C22C: main (qtest.c:770)
==29205==
```
自行輸入
```shell
$ valgrind --leak-check=yes ./qtest
cmd>
cmd> show
q = NULL
cmd> new
q = []
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> it meerkat
q = [gerbil bear dolphin meerkat]
cmd> it bear
q = [gerbil bear dolphin meerkat bear]
cmd> reverse
q = [bear meerkat dolphin bear gerbil]
cmd> size
Queue size = 5
q = [bear meerkat dolphin bear gerbil]
cmd> free
q = NULL
cmd> quit
Freeing queue
```
因此在 `main` 中發生錯誤的地方加上條件判斷
```c
/* Trigger call back function(auto completion) */
if (!infile_name) {
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
```
重新 make
```c
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/amagi/linux2021/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o linenoise.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .linenoise.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
make[1]: Leaving directory '/home/amagi/linux2021/lab0-c'
cp qtest /tmp/qtest.4RAvVj
chmod u+x /tmp/qtest.4RAvVj
sed -i "s/alarm/isnan/g" /tmp/qtest.4RAvVj
scripts/driver.py -p /tmp/qtest.4RAvVj --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.4RAvVj --valgrind -t <tid>
```
Sign in with Wallet
Connect another wallet