# 2021q1 Homework1 (lab0)
contributed by < `AmyLin0210` >
###### tags: `2021q1 Linux`
> [2020q1 lab0 作業解說](https://hackmd.io/@sysprog/linux2021-lab0)
## 基本實做
### queue_t
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
為了要達成時間複雜度 $O(1)$，加上 `*tail` 與 `size`。
:::warning
需要更多解釋，包含後續的使用和資料更新方式。
:notes: jserv
:::
>`tail` 指向 linked list 的最末端，用途為在尾端插入數值時，可以不用從最前方走訪所有節點，使得時間複雜度降為 $O(1)$ 。它會在 list 的最末端有變動時，例如 `q_insert_tail`, `q_sort`, `q_reverse` 等函式執行時變更他的位置，以確保它正確指向最末端。
>
>`size` 用於紀錄 linked list 的長度，所以在呼叫 `q_size` 時，不用遍歷整串 linked list，時間複雜度降為 $O(1)$。它會在 linked list 的長度有變化時被改變，例如 `q_insert_tail`, `q_insert_head`, `q_remove_head`。
### q_new
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
確認 malloc 的回傳值是否合法，然後將所有參數初始化。
### q_free
```cpp
void q_free(queue_t *q)
{
list_ele_t *tmp_e = NULL;
if (q) {
while (q->head) {
if (q->head->value)
free(q->head->value);
tmp_e = q->head;
q->head = tmp_e->next;
free(tmp_e);
}
free(q);
}
}
```
將所有動態分配 ( malloc ) 的空間給釋放。
### q_insert_head, q_insert_tail
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *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;
}
snprintf(newh->value, BUFFER_SIZE, "%s", s);
newh->next = q->head;
q->head = newh;
(q->size)++;
if (!q->tail)
q->tail = q->head;
return true;
}
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *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;
}
if (!q->head)
q->head = newt;
else
q->tail->next = newt;
snprintf(newt->value, BUFFER_SIZE, "%s", s);
newt->next = NULL;
q->tail = newt;
(q->size)++;
return true;
}
```
這兩個函式實做的部份差不多，在第 13 行與 41 行的部份曾經犯過一個錯誤，記得檢查是否有成功 malloc 給 value，但在發現 malloc 失敗時直接 return false，忘記先清掉前面 malloc 給 list_element_t 的空間。
:::warning
避免說「採過一個坑」這樣不精準的話，請記住，這份共筆可能是日後代表你程度的作品，務必斟酌用詞。
:notes: jserv
> 已修正
:::
### q_remove_head
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !(q->head))
return false;
list_ele_t *tmp = q->head;
snprintf(sp, bufsize, "%s", tmp->value);
q->head = q->head->next;
(q->size)--;
free(tmp->value);
free(tmp);
if (!q->head)
q->tail = NULL;
return true;
}
```
### q_size
```cpp
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
為了實做時間複雜度 $O(1)$，故在 queue_t 中新增`size`，儲存目前 list 的長度。
### q_reverse
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *prev = q->head, *next = q->head->next;
q->tail = q->head;
q->head->next = NULL;
while (next) {
q->head = next;
next = next->next;
q->head->next = prev;
prev = q->head;
}
}
```
有想過否要使用遞迴的方式，程式碼會比較直覺簡單，但是空間複雜度會變成 $O(n)$，相比較之下，迴圈的空間複雜度為 $O(1)$ ，所以最終是使用迴圈來實做。
### q_sort
最初是使用 quick sort，但它的 worst case 可能發生在大多數需要被排序的數的優先序相同，時間複雜度為 $O(n^2)$，而在測試資料中就有對應的項目，故之後會改用時間複雜度為 $O(n\log n)$ 的 merge sort 來實做。
```cpp
list_ele_t *merge(list_ele_t *front, list_ele_t *back)
{
if (!front)
return back;
if (!back)
return front;
list_ele_t *tmp = front;
list_ele_t **result = &tmp;
list_ele_t *head =
(strcasecmp(back->value, front->value) >= 0) ? front : back;
while (front && back) {
while (front && strcasecmp(back->value, front->value) >= 0) {
result = &((*result)->next);
front = front->next;
}
*result = back;
if (!front) {
break;
}
while (back && strcasecmp(front->value, back->value) >= 0) {
result = &((*result)->next);
back = back->next;
}
*result = front;
}
return head;
}
void mergesort(list_ele_t **list, int list_len)
{
list_ele_t *tmp = *list;
list_ele_t *front = *list;
list_ele_t *back = NULL;
if (list_len <= 1)
return;
for (int i = 0; i < (list_len / 2) - 1; ++i) {
tmp = tmp->next;
}
back = tmp->next;
tmp->next = NULL;
mergesort(&front, list_len / 2);
mergesort(&back, list_len - list_len / 2);
*list = merge(front, back);
}
```
## 分析 Makefile
參考資料：
[Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)
[gcc(1) — Linux manual page](https://linux.die.net/man/1/gcc)
開始看 Makefile 之後又發現自己的一無所知，接下來就是一連串找資料、學習、寫筆記的開始，在此感謝同學 [randy870819](https://hackmd.io/@randy870819/system-prog-lab0#Makefile-%E5%88%86%E6%9E%90) 與 [KYG-yaya573142](https://hackmd.io/@KYWeng/S1DPSVSQ8#%E5%88%86%E6%9E%90-Makefile) 的共筆！
```
CFLAGS = -O1 -g -Wall -Werror -Idudect -I.
```
- 在這裡用到了 gcc 的一些參數
- `-O1` : 在編譯器裡有 `-O0` `-O1` `-O2` `-O3` 四個優化程度可以選擇，`-O0` 為不優化而 `-O3` 的優化級別最高
- `-g` : 產生 debugging information
- `-Werror` : 讓每個 warnings 變成 error
- `-Idir` : 會在編譯時先在 dir 尋找有沒有符合的 header file，找不到才會依照常規順序繼續尋找
### sanitizer
在編譯時加入一些 sanitizer 的參數
```
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
### verbosity
在這裡決定要不要印出詳細的編譯過程
- 當 VERBOSE 為 1 時會印出詳細編譯過程
- `@` 的作用是不顯示執行的指令
- `@true`可以使該行命令被視作成成功
```
# Control the build verbosity
ifeq ("$(VERBOSE)","1")
Q :=
VECHO = @true
else
Q := @
VECHO = @printf
endif
```
```
qtest: $(OBJS)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
```
### objects and dependencies
這邊使用了 [Auto-Dependency Generation](http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/) 來處理 dependency 的問題
- 第 5 行: 將所有 `OBJS` 中的 `.o` 檔代換成 `.檔案名稱.o.d`
- 第 10 行: 在建立 object file 的同時也建立 dependency file
- 第 12 行: include 所有的 dependency file
- `-MMD` the driver uses its argument but with a suffix of .d, and mention only user header files, not system header files
- `-MF` overrides the default dependency output file
當目標 ( target ) 比起自己的相依項目 ( dependency ) 還要建立的更早時，表示其相依項目已經被修改，在此利用 GNU make 中 auto-rebuild 的特徵重新建立目標。
```=
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
linenoise.o
deps := $(OBJS:%.o=.%.o.d)
%.o: %.c
@mkdir -p .$(DUT_DIR)
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
-include $(deps)
```
### valgrind
```
tid := 0
# Control test case option of valgrind
ifeq ("$(tid)","0")
TCASE :=
else
TCASE := -t $(tid)
endif
```
```
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
```
// 施工研究中
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤
```
$ make clean
$ make SANITIZER=1// 開啟 Address Sanitizer
$ ./qtest
```
以下是錯誤訊息的節錄
```=
==22083==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555ca3a7b400 at pc 0x555ca3a647bd bp 0x7fff08f34f00 sp 0x7fff08f34ef0
READ of size 4 at 0x555ca3a7b400 thread T0
#0 0x555ca3a647bc in do_help_cmd /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:307
#1 0x555ca3a648d0 in interpret_cmda /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:221
#2 0x555ca3a650b5 in interpret_cmd /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:244
#3 0x555ca3a667f8 in run_console /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:660
#4 0x555ca3a633e5 in main /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/qtest.c:780
#5 0x7f6b23bfa0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x555ca3a60b8d in _start (/home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/qtest+0x8b8d)
0x555ca3a7b401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555ca3a7b400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:307 in do_help_cmd
```
從第 11 行來看，我們要從 `console.c` 去尋求進一步的線索。
在 `console.c` 的第 59 行，有一個變數宣告
```cpp
static bool echo = 0;
```
往下搜尋還有其他哪些地方有用到這個 `echo` 變數，發現以下程式碼的第 21 行對 `echo` 進行了強制轉型，但是原 `echo` 的型態為 bool ，它卻將指向 bool 位置的指標改成指向 int 位置的指標。
```cpp=
void init_cmd()
{
cmd_list = NULL;
param_list = NULL;
err_cnt = 0;
quit_flag = false;
add_cmd("help", do_help_cmd, " | Show documentation");
add_cmd("option", do_option_cmd,
" [name val] | Display or set options");
add_cmd("quit", do_quit_cmd, " | Exit program");
add_cmd("source", do_source_cmd,
" file | Read commands from source file");
add_cmd("log", do_log_cmd, " file | Copy output to file");
add_cmd("time", do_time_cmd, " cmd arg ... | Time command execution");
add_cmd("#", do_comment_cmd, " ... | Display comment");
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);
init_in();
init_time(&last_time);
first_time = last_time;
}
```
當 add_param 以為該指標指向 integer 但實際上是指向 bool 時，就有可能會發生 buffer overflow 的問題。
在我的電腦中執行以下程式碼， int 和 bool 的大小不同增強了我對那段程式碼的懷疑。
```cpp
#include <stdbool.h>
#include <stdio.h>
int main() {
printf("bool size: %ld\n", sizeof(bool));
printf("int size: %ld\n", sizeof(int));
return 0;
}
```
```
bool size: 1
int size: 4
```
在 `console.c` 中有一段程式碼
```cpp=
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,
plist->documentation);
plist = plist->next;
}
return true;
}
```
在第 12 行中的 `*plist->valp` 存取到的就是上述所提的 `echo` 變數，但它卻是用 %d 來讀取一個 1 byte 的數值，因此 buffer overflow。
目前我想到的改善方式是改變該程式碼中 `echo` 與有相同問題的 `simulation` ，將他們由 bool 改為 int ，但改變資料型態後可能會造成其餘相關程式碼出現問題，所以還在思考有沒有更優雅的改法。
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
以下擷取自 `make valgrind` 後得到的訊息
```
==46210== 10 bytes in 1 blocks are still reachable in loss record 1 of 3
==46210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210== by 0x4A5250E: strdup (strdup.c:42)
==46210== by 0x1100B6: linenoiseHistoryAdd (linenoise.c:1236)
==46210== by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210== by 0x10C22C: main (qtest.c:769)
==46210==
==46210== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==46210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210== by 0x110076: linenoiseHistoryAdd (linenoise.c:1224)
==46210== by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210== by 0x10C22C: main (qtest.c:769)
==46210==
==46210== 170 bytes in 19 blocks are still reachable in loss record 3 of 3
==46210== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210== by 0x4A5250E: strdup (strdup.c:42)
==46210== by 0x11002A: linenoiseHistoryAdd (linenoise.c:1236)
==46210== by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210== by 0x10C22C: main (qtest.c:769)
```
首先我們看到 valgrind 的錯誤訊息，`still reachable` 表示程式結束時有未釋放的記憶體，不過卻還有指標指著。
接下來我們找到 `qtest.c` 的第 769 行。
```cpp
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
接下來看看 `linenoise.c` 的 1325 行，可以發現又呼叫了另一個函式。
```cpp
linenoiseHistoryAdd(buf);
```
在這份程式碼中，有使用一個名為 history 的參數，型態為 `char**` ，當中做的事情是儲存字串，而 `linenoiseHistoryAdd` 做的就是將這些字串加入 history。
因此我猜測由於 `history` 所指向的記憶體空間在程式結束前沒有被成功的清掉，所以才會出現 `still reachable` 這項錯誤。
最後我在程式結束前將 history 指向的空間清掉，就不會再跳出錯誤訊息了。
Sign in with Wallet
Connect another wallet