# 2023q1 Homework1 (lab0)
contributed by < [hbx1241](https://github.com/hbx1241) >
## 開發環境
```shell
$ gcc --version
gcc (GCC) 12.2.1 20230201
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 5800U with Radeon Graphics
CPU family: 25
Model: 80
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU(s) scaling MHz: 53%
CPU max MHz: 4505.0781
CPU min MHz: 1600.0000
BogoMIPS: 3792.95
```
## 開發過程
### q_free
```c
void q_free(struct list_head *l)
{
// Keep deleting first entry of the佇列until list is empty
while (l && !list_empty(l)) {
element_t *ptr = list_first_entry(l, element_t, list);
list_del(&ptr->list);
q_release_element(ptr);
}
// free head
free(l);
}
```
釋放佇列中第一個 `element_t` 直到佇列是空的，之後釋放 `l` 。
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *eptr = malloc(sizeof(element_t));
if (!eptr)
return false;
int string_size = strlen(s);
eptr->value = malloc(sizeof(char) * (string_size + 1));
if (!eptr->value) {
q_release_element(eptr);
return false;
}
strncpy(eptr->value, s, string_size + 1);
INIT_LIST_HEAD(&eptr->list);
list_add(&eptr->list, head);
return true;
}
```
利用 malloc 逐步配置 `element_t`, `value` 的記憶體，一旦失敗就釋放已經配置的記憶體並回傳 `false` ，否則將字串寫入 `eptr->value` 並初始化 `element_t` 中的 `list` ，將之加入佇列中。
### q_insert_tail
和 `q_insert_head` 一樣，但第 16 行改爲 `list_add_tail((&eptr->list, head));`
:::warning
從程式碼相似的狀況，思考進一步縮減程式碼的手段。
:notes: jserv
:::
### 新增指令
```c
struct list_head *q_new()
{
VALGRIND_PRINTF_BACKTRACE("hi");
struct list_head *p = malloc(sizeof(struct list_head));
if (!p)
return NULL;
else {
INIT_LIST_HEAD(p);
return p;
}
}
```
利用 `VALGRIND_PRINTF_BACKTRACE()` 得到執行 new 時的 call stack:
```c
==25082== by 0x10F298: q_new (queue.c:26)
==25082== by 0x10C968: do_new (qtest.c:150)
==25082== by 0x10DB0E: interpret_cmda (console.c:181)
==25082== by 0x10E0A2: interpret_cmd (console.c:201)
==25082== by 0x10EC9C: run_console (console.c:691)
==25082== by 0x10CF95: main (qtest.c:1299)
```
可以發現在 `console.c` 的 `interpret_cmda` 函式會比對 link list `cmd_list` 中是否有符合輸入的命令，比對到之後執行結構體 ` __cmd_element` 中 `operation` 所指向的函式；搜尋檔案中的 `cmd_list` 發現可以用 `ADD_COMMAND` 將指令加入 `cmd_list` 中並且根據 `console.h` ：
```c
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
若輸入命令爲 `cmd` ，則建立一個 `do_cmd` 的函式
### 使用 Valgrind 檢查 qtest 記憶體流失
執行 `make valgrind` 可以觀察到程式執行結束後有如下訊息：
```c
==6016== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==6016== at 0x4841888: malloc (vg_replace_malloc.c:381)
==6016== by 0x10ED8F: test_malloc (harness.c:133)
==6016== by 0x10F162: q_new (queue.c:17)
==6016== by 0x10C968: do_new (qtest.c:150)
==6016== by 0x10DB0E: interpret_cmda (console.c:181)
==6016== by 0x10E0A2: interpret_cmd (console.c:201)
==6016== by 0x10E46E: cmd_select (console.c:610)
==6016== by 0x10ED1F: run_console (console.c:705)
==6016== by 0x10CF95: main (qtest.c:1299)
```
valgrind 官網的[常見問題](https://valgrind.org/docs/manual/faq.html#faq.deflost) 5.2 中提及：
> "still reachable" means your program is probably ok -- it didn't free some memory it could have.
因此可以判斷應該是程式結束前沒有完全釋放分配的記憶體； 嘗試執行 `valgrind ./qtest` 並輸入 `new` 命令後直接輸入 `quit` 也會發現相同理由的警告，但在 `quit` 之前執行 `free` 的話就會正常退出程式，符合從文件判斷的結果。
觀察 `qtest.c` main 函式結束的部分可以發現有 `add_quit_helper(q_quit)` 和 `finish_cmd` 兩個看起來跟程式結束有關的函式，進一步追蹤可以知道 `q_quit` 中第一行就 `return true;`
明顯有問題，刪掉之後就不會再報錯了。
除此之外，也可以發現 `qtest` 可以用 `add_quit_helper` ， 以函式指標指向輸入的函式（例如： `q_quit` ） 存於 `quit_helpers` 陣列中，之後執行 `quit` 命令或是程式結束時， `do_quit()` 會呼叫陣列中指向的函式，如此一來就可以模組化 quit 時需要執行的函式。
### Linux 核心 Linked List 排序研究
:::info
TODO
:::
### 在 qtest 提供新的命令 shuffle
Sign in with Wallet
Connect another wallet