# 2021q1 Homework1 (lab0)
contributed by < [`andy78644`](https://github.com/andy78644) >
###### tags: `2021 linux`
## 實驗環境資訊
```shell
$ uname -a
Linux andy78644-GP72VR-7RFX 5.4.0-66-generic #74-Ubuntu SMP Wed Jan 27 22:54:38 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
```
:::danger
注意共筆寫作規範：中英文間用一個空白字元區隔。
:notes: jserv
:::
## 開發過程
### `q_new`
* 分派一個 queue_t 的空間給 q，須確定是否有分派成功
* 進行初始化，將 head 與 tail 均指向 NULL ，以及 size 設為0
```clike=
queue_t *q_new()
{
queue_t *q;
if (!(q = malloc(sizeof(queue_t))))
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### `q_free`
* 如果 q 為空，沒有空間須釋放可直接返回
* 要先將字串空間釋放掉在釋放節點空間
```clike=
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
}
free(q);
}
```
### `q_size`
* 為了達成 O(1) 因此可以在佇列的結構上加入 size ，在呼叫 q_size 時即可直接回傳 size ，不須在經過搜尋每個節點計算 size 大小
```clike=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### `q_insert_head`
* 須分別分配空間給節點與字串，並確定是否 malloc 成功
```clike=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
size_t slen = strlen(s) + 1;
/* TODO: What should you do if the q is NULL? */
if (!q) {
return false;
}
if (!(newh = malloc(sizeof(list_ele_t))))
return false;
if (!(newh->value = malloc(slen))) {
free(newh->value);
free(newh);
return false;
}
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
memcpy(newh->value, s, slen);
if (!q->head)
q->tail = newh;
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
### `q_insert_tail`
* 為了達成 O(1) ，須加入 tail 的指標指向串列的最後一個節點，在尾端插入節點時，只要直接使用 tail 的指標去作梗改不須重串列的第一個節點開始尋找
* 如果串列為空，須將 head 的指標指向新插入的節點
```clike=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
size_t slen = strlen(s) + 1;
if (!(newh = malloc(sizeof(list_ele_t))))
return false;
if (!(newh->value = malloc(sizeof(char) * (slen + 1)))) {
free(newh->value);
free(newh);
return false;
}
memcpy(newh->value, s, slen);
newh->next = NULL;
if (q->head)
q->tail->next = newh;
else
q->head = newh;
q->tail = newh;
q->size++;
return true;
}
```
### `q_remove_head`
* 須先確定是否有 sp 的空間可以存取，可能不須回傳 sp
* 須確定長度不能超過 bufsize 會產生超出記憶體空間的問題
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !(q->head))
return false;
list_ele_t *tmp = q->head;
q->head = tmp->next;
int len = strlen(tmp->value);
if (sp) {
memset(sp, 0, bufsize);
if (len < bufsize) {
memcpy(sp, tmp->value, len);
} else {
memcpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### `q_reverse`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
tmp[shape=plaintext,fontcolor=red]
NULL2[label=NULL,shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
cur->B
}
{
rankdir=LR;
tmp->NULL2
}
A->B->C->NULL1
}
```
```graphviz
digraph graph2{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
tmp[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->B
}
{
rank="same";
cur->C
}
{
rank="same";
tmp->A
}
rankdir = LR
B->C->NULL1
A->B[style="dashed"]
}
```
```graphviz
digraph graph2{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
tmp[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->B
}
{
rank="same";
cur->C
}
{
rank="same";
tmp->A
}
B->C->NULL1
rankdir =RL
B->A
}
```
```clike=
void q_reverse(queue_t *q)
{
if (!q)
return;
list_ele_t *cur;
list_ele_t *tmp = NULL;
if (!(q->head))
return;
q->tail = q->head;
while (q->head) {
cur = q->head;
q->head = cur->next;
cur->next = tmp;
tmp = cur;
}
q->head = cur;
}
```
### `q_sort`
* 利用 mergesort 進行排序已達到 O(nlogn)
```clike=
static list_ele_t *merge(list_ele_t *, list_ele_t *);
static list_ele_t *mergesort(list_ele_t *);
void q_sort(queue_t *q)
{
if (!q)
return;
if (!(q->head) || !(q->head->next))
return;
q->head = mergesort(q->head);
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
static list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *tmp, *q;
int compare = 0;
if (right && left)
compare = strcmp(left->value, right->value);
if (compare < 0 || !(right)) {
tmp = left;
left = left->next;
} else {
tmp = right;
right = right->next;
}
q = tmp;
while (left && right) {
compare = strcmp(left->value, right->value);
if (compare < 0) {
tmp->next = left;
left = left->next;
tmp = tmp->next;
} else {
tmp->next = right;
right = right->next;
tmp = tmp->next;
}
}
if (!left) {
tmp->next = right;
} else {
tmp->next = left;
}
return q;
}
static list_ele_t *mergesort(list_ele_t *head)
{
if (!(head) || !(head->next)) {
return head;
}
list_ele_t *right = head->next;
list_ele_t *left = head;
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
head = mergesort(head);
right = mergesort(right);
return merge(head, right);
}
```
## Address Sanitizer
使用 `make SANITIZER=1` 進行編譯後，執行後輸入 `help` 產生下列錯誤
```shell=
==49502==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55fbea41f3c0 at pc 0x55fbea4087bd bp 0x7ffc1b66fc00 sp 0x7ffc1b66fbf0
READ of size 4 at 0x55fbea41f3c0 thread T0
#0 0x55fbea4087bc in do_help_cmd /home/e24064135/linux2021/lab0-c/console.c:307
#1 0x55fbea4088d0 in interpret_cmda /home/e24064135/linux2021/lab0-c/console.c:221
#2 0x55fbea4090b5 in interpret_cmd /home/e24064135/linux2021/lab0-c/console.c:244
#3 0x55fbea40a7f8 in run_console /home/e24064135/linux2021/lab0-c/console.c:660
#4 0x55fbea4073e5 in main /home/e24064135/linux2021/lab0-c/qtest.c:780
#5 0x7f59835b40b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55fbea404b8d in _start (/home/e24064135/linux2021/lab0-c/qtest+0x8b8d)
0x55fbea41f3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55fbea41f3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/e24064135/linux2021/lab0-c/console.c:307 in do_help_cmd
```
在console.c內59行
```clike=
static bool echo = 0;
```
查詢307行可看到以下結果
```clike=
while (plist) {
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,plist->documentation);
plist = plist->next;
}
```
往前找尋 plist 宣告的型態為 param_ptr
```clike=
param_ptr plist = param_list;
```
在 console.c 中可找到 `echo` 在 add_param 以強轉型的方式放入，而 echo 本身為 bool 型態因此會產生 address 的問題
```clike=
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
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;
}
```
將 echo 改為宣告 int 即可解決
```clike=
static int echo = 0;
```
在進行 `make test`中會產生令一項錯誤
```shell=
==45984==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5617dab125e0 at pc 0x5617daafaae8 bp 0x7ffdea15c900 sp 0x7ffdea15c8f0
READ of size 4 at 0x5617dab125e0 thread T0
#0 0x5617daafaae7 in do_option_cmd /home/e24064135/linux2021/lab0-c/console.c:369
#1 0x5617daaf98d0 in interpret_cmda /home/e24064135/linux2021/lab0-c/console.c:221
#2 0x5617daafa0b5 in interpret_cmd /home/e24064135/linux2021/lab0-c/console.c:244
#3 0x5617daafb2e1 in cmd_select /home/e24064135/linux2021/lab0-c/console.c:594
#4 0x5617daafb85b in run_console /home/e24064135/linux2021/lab0-c/console.c:667
#5 0x5617daaf83e5 in main /home/e24064135/linux2021/lab0-c/qtest.c:780
#6 0x7f03f6fb90b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x5617daaf5b8d in _start (/home/e24064135/linux2021/lab0-c/qtest+0x8b8d)
0x5617dab125e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5617dab125e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/e24064135/linux2021/lab0-c/console.c:369 in do_option_cmd
```
與上面的 echo 相同，也是在 add_param 的參數中有強轉型的 simulation 為 bool 型態，因此產生錯誤
console.c
```clike=
int simulation = false;
```
console.h
```clike=
extern int simulation;
```
Sign in with Wallet
Connect another wallet