# 2021q1 Homework1 (lab0)
contributed by < `hapion` >
## 作業要求
完成以下程式
- q_new: 建立新的「空」佇列;
- q_free: 釋放佇列所佔用的記憶體;
- q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
- q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
- q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的元素。
- q_size: 計算佇列中的元素數量。
- q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
- q_sort
## 實作
### Queue structure
- 為了使 insert_tail 跟 size 可以在$O(1)$ 實現，增加 tail 跟 size
``` c=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### q_new
- 產生一個新的 queue，先配置記憶體空間，記得初始化剛剛增加的 tail 跟 size
``` c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
- 釋放的時候要先檢查 queue 是否為 NULL，透過 while 迴圈，先釋放 queue 上 element 所佔空間，最後在釋放 queue 本身
``` c=
void q_free(queue_t *q)
{
if (q == NULL)
return;
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_insert_head/tail
- head 跟 tail 在新增節點的方式一樣，差別在於後面 head 與 tail 的處理
- 使用 strncpy 來處理字串，要記得加 \0
- 一開始測試 q_insert_tail 時，沒注意到要將新節點指向 NULL ，出現segmantation fault ，導致 memory leak
``` c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
}
memset(newh->value, '\0', (strlen(s) + 1));
strncpy(newh->value, s, strlen(s));
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size++;
return true;
}
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (newt == NULL)
return false;
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newt->value == NULL) {
free(newt);
return false;
}
memset(newt->value, '\0', (strlen(s) + 1));
strncpy(newt->value, s, strlen(s));
newt->next = NULL;
if (q->head == NULL) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
q->size++;
return true;
}
```
### q_remove_head
- 釋放 element 本身前，要記得先釋放 element 中存放的 char pointer
``` c=
{
if (q == NULL || q->head == NULL || sp == NULL)
return false;
memset(sp, '\0', bufsize);
strncpy(sp, q->head->value, bufsize - 1);
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_size
``` c =
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
return q->size;
}
```
### q_reverse
``` c=
void q_reverse(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
q->tail = q->head;
list_ele_t *cur = q->head;
list_ele_t *next = NULL;
list_ele_t *prev = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
q->head = prev;
}
```
- 圖例
Declare
```graphviz
digraph graphname{
NULL[label=NULL,shape=plaintext]
node[shape=box]
head[shape=plaintext,fontcolor=red]
tail[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=blue]
{
rankdir = LR
rank="same"
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
head->A
tail->C
}
A->B->C->NULL1
cur->A
next->NULL
prev->NULL
}
```
while loop
```cpp
next = cur->next;
```
```graphviz
digraph graphname{
NULL[label=NULL,shape=plaintext]
node[shape=box]
head[shape=plaintext,fontcolor=red]
tail[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=blue]
{
rank="same"
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
head->A
tail->C
}
A->B->C->NULL1
cur->A
next->B
prev->NULL
}
```
``` c
cur->next = prev;
```
```graphviz
digraph graphname{
head[shape=plaintext,fontcolor=red]
tail[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=blue]
{
rank="same"
NULL[label=NULL,shape=plaintext]
node[shape=box]
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
head->A
NULL->A [dir=back];
tail->C
}
B->C->NULL1
cur->A
next->B
prev->NULL
}
```
``` c
prev = cur;
```
```graphviz
digraph graphname{
head[shape=plaintext,fontcolor=red]
tail[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
pre[shape=plaintext,fontcolor=blue]
{
rank="same"
NULL[label=NULL,shape=plaintext]
node[shape=box]
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
head->A
NULL->A [dir=back];
tail->C
}
B->C->NULL1
cur->A
next->B
pre->A
}
```
``` c
cur = next;
```
```graphviz
digraph graphname{
head[shape=plaintext,fontcolor=red]
tail[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
pre[shape=plaintext,fontcolor=blue]
{
rank="same"
NULL[label=NULL,shape=plaintext]
node[shape=box]
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
head->A
NULL->A [dir=back];
tail->C
}
B->C->NULL1
cur->B
next->B
pre->A
}
```
### q_sort
- 主要是參考 [Merge Sort for Linked Lists](https://www.geeksforgeeks.org/merge-sort-for-linked-list/) 來實作 Merge sort
### Address Sanitizer
在開啟 Address Sanitizer 後，出現錯誤
``` c=
==13804==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b29afcf5e0 at pc 0x55b29afb7ae8 bp 0x7ffddadb7e50 sp 0x7ffddadb7e40
READ of size 4 at 0x55b29afcf5e0 thread T0
#0 0x55b29afb7ae7 in do_option_cmd /home/hapion/linux2021/lab0-c/console.c:369
#1 0x55b29afb68d0 in interpret_cmda /home/hapion/linux2021/lab0-c/console.c:221
#2 0x55b29afb70b5 in interpret_cmd /home/hapion/linux2021/lab0-c/console.c:244
#3 0x55b29afb82e1 in cmd_select /home/hapion/linux2021/lab0-c/console.c:594
#4 0x55b29afb885b in run_console /home/hapion/linux2021/lab0-c/console.c:667
#5 0x55b29afb53e5 in main /home/hapion/linux2021/lab0-c/qtest.c:780
#6 0x7f157e5070b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55b29afb2b8d in _start (/home/hapion/linux2021/lab0-c/qtest+0x8b8d)
0x55b29afcf5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55b29afcf5e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/hapion/linux2021/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
0x0ab6d35f1e60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6d35f1e70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6d35f1e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6d35f1e90: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab6d35f1ea0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ab6d35f1eb0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9
0x0ab6d35f1ec0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
0x0ab6d35f1ed0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab6d35f1ee0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6d35f1ef0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ab6d35f1f00: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
```
發生 global over flow，錯誤偵測點在`369`行，對應到`do_option_cmd`函式中的
`int oldval = *plist->valp;`
判定是在參數傳遞出現問題，因此往前追蹤`plist`的來源，其來自於`param_ptr param_list`且在`add_param`中賦予值
接著繼續往前尋找`add_param`的呼叫點，是在`init_cmd`函式底下
```c=
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);
```
發現問題源於`simulation`、`echo`兩個全域變數
`simulation`、`echo` 最初是宣告成 `bool` 佔一個 bytes，
上面這段程式將其轉成 `int` 因此產生 `global-buffer- overflow`
(存取到超出 `bool` 本身一個 byte 大小的空間造成錯誤)
- 可以將所有 bool 都改成 int，但會需要連帶修改其他東西，不好維護，且需要使用額外 3 byte 來表示一個 bool
參考 [RinHizakura](https://hackmd.io/@RinHizakura/ByuY_q6AU#Address-Sanitizer) 發現可以利用判斷資料型別大小來解決
調整方法
- 先將 PELE 中`valp`修改為`void *`，新增一個 type_size 來記錄原始 type 所用的 bytes
```c=
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name;
void *valp;
int type_size;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
- function`add_param`也要修改
- 設計一個函式`valp_deref`來判斷型別並回傳，此 function 在`do_option_cmd`、`report`會使用到
``` c=
int valp_deref(param_ptr plist)
{
if (plist->type_size == sizeof(bool))
return *(bool *) plist->valp == true ? 1 : 0;
else
return *(int *) plist->valp;
}
```
- 修改`do_option_cmd`來讓輸入符合需求，利用`memcpy`來 assign value
```c=
* Find parameter in list */
param_ptr plist = param_list;
while (!found && plist) {
if (strcmp(plist->name, name) == 0) {
int oldval = valp_deref(plist);
if (plist->type_size == sizeof(bool))
memcpy(plist->valp, &value, sizeof(bool));
else
memcpy(plist->valp, &value, sizeof(int));
if (plist->setter)
plist->setter(oldval);
found = true;
} else
plist = plist->next;
}
Sign in with Wallet
Connect another wallet