# 2021q1 Homework1 (lab0)
contributed by < `secminhr` >
## 牛刀小試
根據 [牛刀小試](https://hackmd.io/@sysprog/linux2021-lab0#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6) 小節實做 `q_size`
根據 `queue.[hc]` 之中的註解以及小節中的指示，為了使 `q_size(queue_t *)` 在 $O(1)$ 時間內達成，我們在 `queue.h` 的 `struct queue_t` 裡加入成員 `int size` 來維護 queue 的長度。
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
int size;
} queue_t;
```
接著修改 `queue.c` 中的 `q_size(queue_t *)`，使其回傳 `q->size`。
```cpp
int q_size(queue_t *q)
{
return q->size;
}
```
[commit 209521c6e7](https://github.com/secminhr/lab0-c/tree/209521c6e7f284ea21416bfccf511e5605e87810)
## C Programming Lab
### 實做 q_new
根據 `queue.c` 裡面的註解：
> TODO: What if malloc returned NULL?
我們知道需要處理錯誤時 `malloc` 傳回 `NULL` 的情況，另外也要記得將 `size` 初始化成0。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->size = 0;
}
return q;
}
```
[commit 8474de3c94](https://github.com/secminhr/lab0-c/tree/8474de3c949221f341ddde26a98270d8f3239ab9)
### 實做 q_free
根據 `queue.c` 裡的 `TODO` 註解：
> TODO: How about freeing the list elements and the strings?
`q_free` 註解：
> Free all storage used by queue
和 `queue.h` 在 `struct ELE` 對 `char *value` 的註解：
> Pointer to array holding string.
> This array needs to be explicitly allocated and freed
我們知道 `q_free` 需要釋放 `q` 、所有 `list_ele_t` 和其 `char *value`。
```cpp
void q_free(queue_t *q)
{
if (q == NULL) {
return;
}
/* Free all list elements and strings */
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
/* Free queue structure */
free(q);
}
```
[commit 69a395b98e](https://github.com/secminhr/lab0-c/tree/69a395b98ea890a497261b3d5b87684f71bd1055)
### 實做 q_insert_head
首先根據 `queue.c` 的註解：
> TODO: What should you do if the q is NULL?
我們先在 `q_insert_head` 加上一個 NULL check
```c=
if (q == NULL) {
return false;
}
```
再來就是把新的 `list_ele_t *` 跟 `char *` `malloc` 出來。加上 NULL check 並在 `malloc` 失敗時回傳 `false`。
```cpp
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
char *str = malloc(strlen(s) + 1);
if (str == NULL) {
free(newh);
return false;
}
```
注意 `str` 申請的空間長度是 `strlen(s) + 1` ，因為 `strlen` 不計算結尾 `\0` 。
最後設定 `newh` 和 `str` 並維護 `q` 。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
char *str = malloc(strlen(s) + 1);
if (str == NULL) {
free(newh);
return false;
}
strncpy(str, s, strlen(s) + 1);
newh->next = q->head;
newh->value = str;
q->head = newh;
q->size++;
return true;
}
```
[commit 9714cc6d37](https://github.com/secminhr/lab0-c/tree/9714cc6d37d23676fadab882681ae78abc40e234)
### 實做 q_insert_tail
根據 `queue.c` 的註解：
> Remember: It should operate in O(1) time
要在 $O(1)$ 時間內插入元素到串列尾端，我們可以在 `queue_t` 裡多維護一個成員 `list_ele_t *tail` 。
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
定義 `tail` 的表示如圖
**single element**
```graphviz
digraph tail_single_ele {
Head[shape=box]
Tail[shape=box]
Ele[shape=box]
Head -> Ele
Tail -> Ele
}
```
**multiple elements**
```graphviz
digraph tail_mul_ele {
node [shape=box]
Head -> Ele1
Tail -> Ele2
Ele1 -> Ele2
{rank=same;Ele1 Ele2}
}
```
#### 修改 q_new
加上對於 `tail` 的初始化
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
#### 修改 q_insert_head
當 q 是 empty queue 時，須更新 `tail`
```cpp
if (q->size == 0) {
q->tail = newh;
}
```
#### q_insert_tail
新節點的處理跟 `q_insert_head` 都一樣。
但是在把新節點加入 queue 時會因為 queue size 不同而有不同的操作。
```cpp
if (q->size) {
q->tail->next = newt;
} else {
q->head = newt;
}
```
最後，維護 `q`。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (newt == NULL) {
return false;
}
char *str = malloc(strlen(s) + 1);
if (str == NULL) {
free(newt);
return false;
}
strncpy(str, s, strlen(s) + 1);
newt->next = NULL;
newt->value = str;
if (q->size) {
q->tail->next = newt;
} else {
q->head = newt;
}
q->tail = newt;
q->size++;
return true;
}
```
[commit a1b0028600](https://github.com/secminhr/lab0-c/tree/a1b0028600b4ae9e444f2f8088d313e4a2bcb879)
### 實做 q_remove_head
根據 `queue.c` 的註解：
> Attempt to remove element from head of queue.
> Return true if successful.
> Return false if queue is NULL or empty.
先在開頭加上 NULL 或者 empty 判定
```cpp
if (q == NULL || q->size == 0) {
return false;
}
```
再來就是對 `q` 的維護，並且把舊的 `head` 和其 `value` 釋放。
注意當 `size` 是 1 的時候， `tail` 也需要更新。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->size == 0) {
return false;
}
list_ele_t *old_head = q->head;
q->head = q->head->next;
if (q->size == 1) {
q->tail = NULL;
}
q->size--;
if (sp != NULL) {
strncpy(sp, old_head->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
free(old_head->value);
free(old_head);
return true;
}
```
[commit c487dafce0](https://github.com/secminhr/lab0-c/tree/c487dafce032b70f87dd72d2f66f6665fe455c3e)
### 實做 q_reverse
根據 `queue.c` 的註解
> Reverse elements in queue
> No effect if q is NULL or empty
先加入 NULL 或 empty 的判定
```cpp
if (q == NULL || q->size == 0) {
return;
}
```
接下來走過整個 queue，把 `next` 改成上一個就好。最後更新 `q` 的 `head` 和 `tail` 。
```cpp
void q_reverse(queue_t *q)
{
if (q == NULL || q->size == 0) {
return;
}
list_ele_t *prev = NULL;
list_ele_t *cur = q->head;
while (cur) {
list_ele_t *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
q->tail = q->head;
q->head = prev;
}
```
[corresponding commit]()
### 修正 q_size
這時候發現測試的 `trace-07` 有問題如下：
> +++ TESTING trace trace-07-robust:
> \# Test operations on NULL queue
> Segmentation fault occurred. You dereferenced a NULL or invalid pointer
> --- trace-07-robust 0/6
透過逐一執行 `trace-07` 內含的命令後，可以發現 segmentation fault 的原因是 `q_size` 缺少了 NULL check。
根據 `queue.c` 的註解：
> Return number of elements in queue.
> Return 0 if q is NULL or empty
加入 NULL check
```cpp
int q_size(queue_t *q)
{
return q == NULL ? 0 : q->size;
}
```
再測試可發現 `trace-07` 的問題已修正。
[commit 06f035eed0](https://github.com/secminhr/lab0-c/tree/06f035eed044b2567f99d812ec67d3886327ea1b)
### 提取重複
發現 `q_insert_tail` 和 `q_insert_head` 在配置空間時的動作一致，將它提取出來。
```cpp
static list_ele_t *alloc_ele(queue_t *q, size_t value_size)
{
if (q == NULL) {
return NULL;
}
list_ele_t *new = malloc(sizeof(list_ele_t));
if (new == NULL) {
return NULL;
}
char *value = malloc(value_size);
if (value == NULL) {
free(new);
return NULL;
}
new->value = value;
return new;
}
```
[commit 33bdf06be8](https://github.com/secminhr/lab0-c/tree/33bdf06be855bd569baf10613b2db15fd69aa9f3)
### 實做 q_sort
這裡使用 merge sort 來實做
原因在於：
- trace-16 要求 q_sort 應達到時間複雜度 $O(nlogn)$
> sorting algorithms with O(nlogn) time complexity are expected pass
- 要達到 $O(nlogn)$ ，想到的就是 quicksort 或 merge sort
- merge sort 不論是最佳、平均或者最差情況都是 $O(nlogn)$ ，但是 quicksort 最差的表現可能達到 $O(n^2)$
- <s>我比較熟悉 merge sort</s>
:::warning
需要提及你對 sorting 演算法的選擇考量
:notes: jserv
:::
`q_sort` 的內容很直接
```cpp
void q_sort(queue_t *q)
{
if (q == NULL || q->size == 0 || q->size == 1) {
return;
}
queue_t q1, q2;
split(q, &q1, &q2);
q_sort(&q1);
q_sort(&q2);
merge(q1, q2, q);
}
```
`split` 會將 `q` 分成兩半，並把前半放在 `q1` 、後半放在 `q2`。
```cpp
static void split(queue_t *q, queue_t *q1, queue_t *q2)
{
int split_pos = q->size / 2 - 1;
q1->size = split_pos + 1;
q1->head = q->head;
q2->size = q->size - q1->size;
q2->tail = q->tail;
list_ele_t *split_ele = q->head;
for (int i = 0; i < split_pos; i++) {
split_ele = split_ele->next;
}
q1->tail = split_ele;
q2->head = split_ele->next;
q1->tail->next = NULL;
}
```
其中 `int split_pos = q->size / 2 - 1`， `-1` 是為了避免切出 empty queue 。
`merge` 則是合併 `q1` 和 `q2` 到 `dest` 。
```cpp
static void merge(queue_t q1, queue_t q2, queue_t *dest)
{
list_ele_t **merge_cur = &(dest->head);
while (q1.head && q2.head) {
if (strcmp(q1.head->value, q2.head->value) < 0) {
*merge_cur = q1.head;
q1.head = q1.head->next;
} else {
*merge_cur = q2.head;
q2.head = q2.head->next;
}
merge_cur = &((*merge_cur)->next);
}
queue_t last = q1.head ? q1 : q2;
*merge_cur = last.head;
dest->tail = last.tail;
}
```
至此，評分程式的要求已全數完成。
> --- TOTAL 100/100
[commit 66d400790b](https://github.com/secminhr/lab0-c/tree/66d400790bf35b1b1bcbbef834446214a7756b24)
## Address Sanitizer
### 尋找錯誤
先打開 Adress Sanitizer 。
```shell
$ make clean
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 *~)
$ make SANITIZER=1
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
```
看錯誤訊息。
```shell
$ ./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:
=================================================================
==3161==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5614b90293c0 at pc 0x5614b90127bd bp 0x7ffeeea60bd0 sp 0x7ffeeea60bc0
READ of size 4 at 0x5614b90293c0 thread T0
#0 0x5614b90127bc in do_help_cmd /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:307
#1 0x5614b90128d0 in interpret_cmda /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:221
#2 0x5614b90130b5 in interpret_cmd /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:244
#3 0x5614b90147f8 in run_console /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:660
#4 0x5614b90113e5 in main /home/ioncamp/Desktop/linux_ncku/lab0-c/qtest.c:780
#5 0x7fc2e9eba0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5614b900eb8d in _start (/home/ioncamp/Desktop/linux_ncku/lab0-c/qtest+0x8b8d)
0x5614b90293c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5614b90293c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac3171fd220: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ac3171fd230: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac3171fd240: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac3171fd250: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac3171fd260: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac3171fd270: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ac3171fd280: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac3171fd290: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3171fd2a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3171fd2b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac3171fd2c0: 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
==3161==ABORTING
```
錯誤出現在 `console.c:307`
> #0 0x5614b90127bc in do_help_cmd /home/ioncamp/Desktop/linux_ncku/lab0-c/console.c:307
直接到錯誤訊息指定的地方看
```c=307
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
```
錯誤中有一段寫：
> READ of size 4 at 0x5614b90293c0 thread T0
所以我們知道是在 307 行試圖讀取 4 個 bytes 的時候出了錯，而這行只有三個讀取
- `plist->name`
- `*plist->valp`
- `plist->documentation`
我們可以從型態下手，看看其中有沒有長度正好是 4 個 bytes 的。可以在上面幾行找到 `plist` 的定義。
```c=304
param_ptr plist = param_list;
```
在 `console.h` 可以找到 `param_ptr` 。
```c=30
/* 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;
};
```
看來是讀取 `valp` 的時候出了錯， int 的長度是 4 個 bytes 。
做個實驗把 `console.c:307` 改成直接印出 `*plist->valp` ，果然錯誤再度出現。
這裡讀取的錯誤很可能代表這個 `param_list` 裡面有錯誤的值。我們發現在 `console.c` 裡只有 `add_param()` 在對 `param_list` 做更改。
(`init_cmd()` 裡面只給 `param_list = NULL` ，只是初始化這個變數而已)
查看 `add_param()` 的呼叫者
```c=104
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);
add_param("verbose", &verblevel, "Verbosity level", NULL);
add_param("error", &err_limit, "Number of errors until exit", NULL);
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
`(int *) &echo` 和 `(int *)simulation` 這兩個強轉型很顯眼及奇怪。
查看兩者宣告分別是
```c=
static bool echo = 0;
```
```c=
bool simulation = false;
```
到這裡，問題已經顯現出來。
`bool` 的長度只有一個 byte ，但是他們的指標被強轉成 `int *` ，會一次讀 4 個 bytes ，於是不正常的讀取行為就發生了。
### 修正
先修正 `echo` ，因為這正是錯誤訊息描述的
> 0x5614b90293c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5614b90293c0) of size 1
先查看一下 `echo` 可以發現，它所有的操作在型態變成 `int` 的情況下都可以運作。
所以可以直接把 `echo` 的型態換成 `int` 。
```c=
static int echo = 0;
//...
add_param("echo", &echo, "Do/don't echo commands", NULL);
```
試著再跑一次 Address Sanitizer ，發現下個錯誤確實在 `simulation` 發生。
> 0x5555ef8345e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5555ef8345e0)
但是這次沒辦法直接換型態了，因為在 `console.h`中：
```c=11
extern bool simulation;
```
如果直接改型態將會向外影響。
我們再看看 `add_param()` 的定義：
```c=
void add_param(char *name,
int *valp,
char *doccumentation,
setter_function setter);
```
`setter_function` 的定義：
```c=
typedef void (*setter_function)(int oldval);
```
及 `struct PELE` 的對 `setter` 的註解：
> Function that gets called whenever parameter changes
我們既然有 `valp` 被改變時會呼叫的 function ，這代表我們可以維護一個 int 型態的變數，並利用 `setter` 來與 `simlation` 連動，在該變數被更新時一起更新 `simulation` 。
```c=
bool simulation = false;
static int simulation_backing = 0;
//...
static void simulation_setter(int oldVal)
{
simulation = simulation_backing ? true : false;
}
//...
add_param("simulation", &simulation_backing, "Start/Stop simulation mode",
simulation_setter);
```
修正後，`help` 命令將不會出現錯誤訊息。
[commit 0215e12577](https://github.com/secminhr/lab0-c/tree/0215e1257785f012e58d7f5e30b153f1f4a2d088)
:::danger
留意到 instruction (指令) 和 command (命令) 這兩個不同語義的詞彙。細節！
:notes: jserv
:::
## Valgrind
看訊息
```shell=
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/ioncamp/Desktop/linux_ncku/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/ioncamp/Desktop/linux_ncku/lab0-c'
cp qtest /tmp/qtest.pt5fTC
chmod u+x /tmp/qtest.pt5fTC
sed -i "s/alarm/isnan/g" /tmp/qtest.pt5fTC
scripts/driver.py -p /tmp/qtest.pt5fTC --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==3737== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==3737== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3737== by 0x4A4D50E: strdup (strdup.c:42)
==3737== by 0x11006E: linenoiseHistoryAdd (linenoise.c:1236)
==3737== by 0x110C01: linenoiseHistoryLoad (linenoise.c:1325)
==3737== by 0x10C234: main (qtest.c:769)
==3737==
==3737== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==3737== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3737== by 0x11002E: linenoiseHistoryAdd (linenoise.c:1224)
==3737== by 0x110C01: linenoiseHistoryLoad (linenoise.c:1325)
==3737== by 0x10C234: main (qtest.c:769)
==3737==
==3737== 178 bytes in 19 blocks are still reachable in loss record 3 of 3
==3737== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3737== by 0x4A4D50E: strdup (strdup.c:42)
==3737== by 0x10FFE2: linenoiseHistoryAdd (linenoise.c:1236)
==3737== by 0x110C01: linenoiseHistoryLoad (linenoise.c:1325)
==3737== by 0x10C234: main (qtest.c:769)
==3737==
--- trace-01-ops 6/6
...
```
這個訊息發生多次，雖然寫的是 still reachable ，但還是檢查一下。
看 `linenoise.c` ，可以發現訊息指出的地方都是把 `malloc` 拿到的結果放在全域變數 `history` ，沒有流失。
```c=1224
history = malloc(sizeof(char *) * history_max_len);
```
```c=1236
linecopy = strdup(line);
...
history[history_len] = linecopy;
```
### massif
TODO:
Sign in with Wallet
Connect another wallet