---
tags: linux2021,
---
# 2021q1 Homework1 (lab0)
contributed by < `lofoz` >
## 程式碼實作
### queue.h
#### queue_t
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
/* tail -> record the last ELE
* size -> record the queue size
*/
list_ele_t *tail;
int size;
} queue_t;
```
宣告 `int size` 紀錄 queue 的長度
為了達到 `insert tail` Time complexity $O(1)$ 的要求，宣告 `list_ele_t tail`
### queue.c
#### q_new()
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* Got a null pointer */
if (!q)
return NULL;
q->head = NULL;
/* initialize queue tail */
q->tail = NULL;
/* initialize queue size */
q->size = 0;
return q;
}
```
變數初始化
#### q_insert_head()
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* Got a null pointer */
if (q == NULL) return false;
/* allocate spcae */
newh = malloc(sizeof(list_ele_t));
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (newh == NULL || newh->value == NULL) return false;
/* Copy string */
strcpy(newh->value, s);
newh->next = q->head;
q->head = newh;
/* initialize queue tail when queue size is 0 */
if (q->size == 0) q->tail = q->head;
/* update queue size */
q->size++;
return true;
}
```
上方的版本在第 7 和第 8 行，會發生 Error: Memory leak ，第 12 行的 `strcpy`() 為 Dangerous function，下方為修改後
```cpp
/* allocate spcae */
newh = malloc(sizeof(list_ele_t));
/* Got a null pointer */
if (!newh)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (!newh->value) {
free(newh);
return false;
}
```
```cpp
/* Copy string and check if the string size is too long */
int buf_len = strlcpy(newh->value, s, strlen(newh->value) + 1);
if (buf_len >= strlen(newh->value) + 1 || buf_len < 0) {
free(newh->value);
free(newh);
return false;
}
```
:::warning
若 `char *s` 傳入時為 NULL，會發生什麼事？查閱 man page 以理解實作行為。
:notes: jserv
:::
#### q_insert_tail()
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
/* Got a null pointer */
if (!q)
return false;
/* allocate space */
newt = malloc(sizeof(list_ele_t));
/* Got a null pointer */
if (!newt)
return false;
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (!newt->value) {
free(newt);
return false;
}
/* Copy string and check if the string size is too long */
int buf_len = strlcpy(newt->value, s, strlen(newt->value) + 1);
if (buf_len >= strlen(newt->value) + 1 || buf_len < 0) {
free(newt->value);
free(newt);
return false;
}
newt->next = NULL;
if (q->size == 0) {
q->head = newt;
q->tail = q->head;
} else {
q->tail->next = newt;
q->tail = newt;
}
/* update queue size */
q->size++;
return true;
}
```
#### q_remove_head()
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *tmp;
/* Check if queue is NULL or empty */
if (!q || q->size == 0)
return false;
/* Copy string */
if (sp) {
size_t len = strlen(q->head->value) + 1;
len = len > bufsize ? bufsize : len;
strncpy(sp, q->head->value, len);
sp[len - 1] = '\0';
}
tmp = q->head;
q->head = q->head->next;
/* update queue size */
q->size--;
/* Check tail */
if (q->size == 0)
q->tail = NULL;
/* Free space */
free(tmp->value);
free(tmp);
return true;
}
```
#### q_reverse()
```cpp
void q_reverse(queue_t *q)
{
/* Check if q is NULL */
if (q) {
list_ele_t *cur = q->head;
list_ele_t *prev = NULL;
list_ele_t *tmp = NULL;
/* traversal queue */
while (cur) {
tmp = cur;
cur = cur->next;
tmp->next = prev;
prev = tmp;
}
/* Swap tail and head */
tmp = q->head;
q->head = q->tail;
q->tail = tmp;
}
}
```
#### q_free()
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *cur = q->head;
while (cur) {
list_ele_t *tmp = cur;
cur = cur->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
#### q_sort()
```cpp
void q_sort(queue_t *q)
{
/* forget !q->head */
if (!q || !q->head)
return;
merge_sort(&q->head);
/* more efficiency way to find tail? */
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
## 測試結果
### make test 得分
:::danger
文字訊息不要用圖片展現，避免排版和日後檢索的困難，同時也對視覺障礙者更友善。
:notes: jserv
:::
## 遇到的困難
### 1. VIM 縮排長度
```diff
queue_t *q = malloc(sizeof(queue_t));
/* Got a null pointer */
if (!q)
- return NULL;
+ return NULL;
```
VIM 預設縮排寬度和 Git hook 需求不同
#### 解法
1. 使用 clang-format 自動修正排版
```shell
$ clang-format -i *.[ch]
```
2. 或許可以透過調整 VIM 設定檔(待確認)
:::warning
善用 [EditorConfig](https://editorconfig.org/)
:notes: jserv
:::
### 2. Dangerous function : strcpy()
遇到的錯誤訊息
```cpp
Dangerous function detected in /home/lofoz/linux2020/lab0-c/queue.c
54: strcpy(newh->value, s);
85: strcpy(newt->value, s);
```
#### 解法
查閱 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 後，了解為何 strcpy 是有風險的函式:
> The strcpy built-in function does ==not check buffer lengths== and may very well ==overwrite memory zone contiguous to the intended destination==. In fact, the whole family of functions is similarly vulnerable: **strcpy**, **strcat** and **strcmp**.
從說明中得知除了 **strcpy**，還有其他同家族的函式(**strcat**, **strcmp**)等，皆是有風險的函式
使用 snprintf() 有效的執行字串複製，並確保記憶體複寫(overwrite)的問題
修改如下
```cpp=
#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif
```
並且在使用到 strlcpy() 的部分修改為
```cpp=
/* Copy string and check if the string size is too long */
int buf_len = strlcpy(newh->value, s, strlen(newh->value) + 1);
if (buf_len >= strlen(newh->value) + 1 || buf_len < 0) {
return false;
}
```
strlcpy() 會回傳字串 s 的長度 buf_len (不包含終止符號 '\0')，若 buf_len 長度 $\geq$ strlen(newh->value) + 1，則 return false
### 3. Warning: nullPointerRedundantCheck
```cpp=
queue.c:53:5: warning: Either the condition '!newh' is redundant or there is possible null pointer dereference: newh. [nullPointerRedundantCheck]
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
^
queue.c:55:9: note: Assuming that condition '!newh' is not redundant
if (!newh || !newh->value)
^
queue.c:53:5: note: Null pointer dereference
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
^
queue.c:87:5: warning: Either the condition '!newt' is redundant or there is possible null pointer dereference: newt. [nullPointerRedundantCheck]
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
^
queue.c:89:9: note: Assuming that condition '!newt' is not redundant
if (!newt || !newt->value)
^
queue.c:87:5: note: Null pointer dereference
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
^
```
透過 qtest 測試認為程式是沒有問題後，執行 commit ，結果跳出一長串的 warning (有被嚇到 :P)
透過仔細查看程式碼後，發現問題是未檢查 nullPointerRedundantCheck 就直接使用 pointer
舉 q_insert_head() 的片段，狀況如下
```cpp=
/* allocate spcae */
newh = malloc(sizeof(list_ele_t));
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (!newh || !newh->value)
return false;
```
#### 解法
將程式碼修改成如下
```cpp=
/* allocate spcae */
newh = malloc(sizeof(list_ele_t));
/* Got a null pointer */
if (!newh)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (!newh->value)
return false;
```
雖然寫起來較為繁雜，但卻能確保記憶體空間的正確獲取。
### 4. Error: Memory leak
e.g. 在 q_insert_head() 中發生 Memory leak
```cpp=
/* allocate spcae */
newh = malloc(sizeof(list_ele_t));
/* Got a null pointer */
if (!newh)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Got a null pointer */
if (!newh->value)
return false;
```
問題發生於上方的第 8 行，若 `newh->value` 沒有拿到記憶體空間，則回傳 false，乍看之下沒有問題，但函式返回時並未釋放 newh 的記憶體空間。
#### 解法
修改如下
在 return false 前，釋放 newh 的記憶體空間
```cpp
/* Got a null pointer */
if (!newh->value) {
free(newh);
return false;
}
```
### 5. Segmentation fault occurred: Dereferenced a NULL or invalid pointer
就在我寫完所有 function 開心的下了 make test 之後，<s>噴了一堆錯誤</s>，其中最先要解決的是 Dereferenced a NULL or invalid pointer。
:::danger
避免說「噴了一堆錯誤」，這符合漢語的慣例嗎？工程人員說話要精準。
:notes: jserv
:::
如下方的錯誤訊息
```cpp=
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
ERROR: Removed value bear != expected value meerkat
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-05-ops 0/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-06-string 0/6
+++ 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 file ，得知某些 function 漏掉檢查 queue 是否為 NULL 或 q->head 是否為 NULL
### 6.
```
==5696==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55c58770e620 at pc 0x55c5876f6ae8 bp 0x7ffc96c1c5e0 sp 0x7ffc96c1c5d0
READ of size 4 at 0x55c58770e620 thread T0
#0 0x55c5876f6ae7 in do_option_cmd /home/lofoz/linux2020/lab0-c/console.c:369
#1 0x55c5876f58d0 in interpret_cmda /home/lofoz/linux2020/lab0-c/console.c:221
#2 0x55c5876f60b5 in interpret_cmd /home/lofoz/linux2020/lab0-c/console.c:244
#3 0x55c5876f72e1 in cmd_select /home/lofoz/linux2020/lab0-c/console.c:594
#4 0x55c5876f785b in run_console /home/lofoz/linux2020/lab0-c/console.c:667
#5 0x55c5876f43e5 in main /home/lofoz/linux2020/lab0-c/qtest.c:780
#6 0x7ff6754580b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55c5876f1b8d in _start (/home/lofoz/linux2020/lab0-c/qtest+0x8b8d)
0x55c58770e621 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55c58770e620) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/lofoz/linux2020/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
0x0ab930ed9c70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab930ed9c80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab930ed9c90: 00 00 00 00 00 00 00 00 f9 f9 f9 f9 00 f9 f9 f9
0x0ab930ed9ca0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab930ed9cb0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ab930ed9cc0: f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ab930ed9cd0: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ab930ed9ce0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab930ed9cf0: 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 f9
0x0ab930ed9d00: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ab930ed9d10: 04 f9 f9 f9 f9 f9 f9 f9 00 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
==5696==ABORTING
```
:::info
**Todo:** 了解 EditorConfig, char *s 傳入時為 NULL 之行為
:::
Sign in with Wallet
Connect another wallet