---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `eric88525` >
## 實驗環境
```shell!
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 48 bits physical, 48 bits virtual
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 25
Model: 33
Model name: AMD Ryzen 7 5800X 8-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 2200.000
CPU max MHz: 4850.1948
CPU min MHz: 2200.0000
BogoMIPS: 7585.34
Virtualization: AMD-V
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 4 MiB
L3 cache: 32 MiB
NUMA node0 CPU(s): 0-15
```
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
* 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
* 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
* 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
* 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
* 截止日期：
* Mar 1, 2022 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高
指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
- [x] `q_new`: 建立新的「空」佇列;
- [x] `q_free`: 釋放佇列所佔用的記憶體;
- [x] `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- [x] `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- [x] `q_
_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- [x] `q_release_element`: 釋放特定節點的記憶體空間;
- [x] `q_size`: 計算目前佇列的節點總量;
- [x] `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- [x] `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- [x] `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
# 開發過程
## q_new
建立空的list_head，並閱讀linux kernel api和list.h來簡化相關程式
```c
struct list_head *q_new()
{
struct list_head *p = malloc(sizeof(struct list_head));
// allocate space fail, return null
if (p == NULL)
return NULL;
// init pointer
INIT_LIST_HEAD(p);
return p;
}
```
## q_free
+ 參考 kernel api，list_for_each_entry_safe 會用暫存n來記錄下一個位置，就可以安全刪除當前節點
+ [link](https://www.cnblogs.com/yangguang-it/p/11667772.html)
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *pos = NULL, *n = NULL;
list_for_each_entry_safe (pos, n, l, list)
q_release_element(pos);
free(l);
}
```
## q_insert_head
+ kernel api 已經提供相關實作，只需要處理記憶體管理和字串拷貝
> list_add: Insert a new entry after the specified head. This is good for implementing stacks.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
// create new node and assign value to it
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
new_node->value = strdup(s);
if (!new_node->value) {
q_release_element(new_node);
return false;
}
list_add(&new_node->list, head);
return true;
}
```
## q_insert_tail
+ kernel api 已經提供相關實作，只需要處理記憶體管理和字串拷貝
> list_add_tail: Insert a new entry before the specified head. This is useful for implementing queues.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!s || !head)
return false;
// create new node and assign value to it
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
new_node->value = strdup(s);
if (!new_node->value) {
q_release_element(new_node);
return false;
}
list_add_tail(&new_node->list, head);
return true;
}
```
## q_remove_head
+ 呼叫 list_first_entry 來取得第一個entry
+ 用 list_del 來確保前後節點在移除 entry 後仍然互相連接。
+ 複製字串到sp
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *p = list_first_entry(head, element_t, list);
list_del_init(&(p->list));
if (sp) {
strncpy(sp, p->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return p;
}
```
## q_release_element
+ 無變動
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
## q_size
+ 遍歷整個 list 來計算size
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int size = 0;
struct list_head *p = NULL;
list_for_each (p, head)
size++;
return size;
}
```
## q_delete_mid
+ 運用快/慢指標，找出中心點
+ 找出中心後，用 list_del_init 確保 linked list 串接正常
+ 釋放記憶體
```c
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head **p = &head->next;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next)
p = &(*p)->next;
struct list_head *to_delete = (*p);
list_del_init(to_delete);
q_release_element(container_of(to_delete, element_t, list));
return true;
}
```
## q_delete_dup
+ 首先讓 double pointer p 指向 head 的 next 指標
+ 如果遇到重複的節點，透過prev來暫存即將被刪除的節點，並讓curr往下移動，並刪除prev
+ 把 p 移動到下一個節點的next指標上
+ 如果 curr 或是 curr->next 為 head 就結束
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **p = &(head->next);
struct list_head *curr = head->next, *prev = NULL;
while (curr != head && curr->next != head) {
if (strcmp(container_of(curr, element_t, list)->value,
container_of(curr->next, element_t, list)->value) == 0) {
do {
prev = curr;
curr = curr->next;
list_del(prev);
q_release_element(container_of(prev, element_t, list));
} while (curr->next != head &&
strcmp(container_of(curr, element_t, list)->value,
container_of(curr->next, element_t, list)->value) ==
0);
}
p = &((*p)->next);
curr = curr->next;
}
return true;
}
```
## q_swap
+ 兩兩交換節點
+ 如果有a和b節點需要交換，首先把b抽出來，接著加入a的前面
+ 原本是使用 list_add_tail 而不是 list_add，會需要額外的指標來記錄 a 前面的節點，如果用 list_add_tail就可以省下
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *curr = head->next;
struct list_head *next = NULL;
while (curr && curr->next && curr != head && curr->next != head) {
next = curr->next;
list_del(next);
list_add_tail(next, curr);
curr = curr->next;
}
}
```
## q_reverse
+ 運用prev和next來紀錄前後位置，逐一反轉節點
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *prev = head->prev, *curr = head, *next = NULL;
while (next != head) {
next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
## q_sort
+ 參考老師提供的merge sort，改成有prev的版本
+ 一開始要先把 head 拆出來，變成單向的 linking list ，最後串回來
+ merge sort相較於quick sort能有更穩定的速度(都是 nlogn)
+ 更新： 在進入q_sort後要先用 list_empty來檢查一次，不然 test17 會出問題
```c
struct list_head *merge(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
struct list_head *prev_node = NULL;
for (node = NULL; L1 && L2; prev_node = *node, *node = (*node)->next) {
// let node point to smaller node pointer(L1/L2)
node = strcmp(container_of(L1, element_t, list)->value,
container_of(L2, element_t, list)->value) > 0
? &L2
: &L1;
*ptr = *node;
(*node)->prev = prev_node;
ptr = &(*ptr)->next;
}
*node = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
*ptr = *node;
(*node)->prev = prev_node;
return head;
}
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head->next;
struct list_head *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
struct list_head *L1 = merge_sort(head);
struct list_head *L2 = merge_sort(fast);
return merge(L1, L2);
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *last_node = head->prev;
last_node->next = NULL;
head->next->prev = NULL;
struct list_head *sorted_list = merge_sort(head->next);
INIT_LIST_HEAD(head);
head->next = sorted_list;
sorted_list->prev = head;
// move last_node pointer to
for (last_node = sorted_list; last_node->next != NULL;
last_node = last_node->next) {
}
head->prev = last_node;
last_node->next = head;
}
```
## 最後一個測試的 bug
+ 在本地有時會顯示 ERROR: Probably not constant time ，有時則會通過，這似乎只是本機上的問題，丟到遠端還是會通過
## shuffle 命令
> 參考[作業說明](https://hackmd.io/@sysprog/linux2022-lab0#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C) 的 qtest 命令直譯器介紹來實作
在 qtest.c 的 `console_init()`內加入這行，可以新增命令、function、訊息顯示
```c
ADD_COMMAND(shuffle, " | Shuffle every nodes in queue");
```
`ADD_COMMAND` 是把 `add_cmd()` 再包裝一次，由於巨集展開後會把 `cmd` 和 do_`cmd` 的 function 相連，因此要連結的 function名稱應該以 do_開頭
```c
// console.h
void add_cmd(char *name, cmd_function operation, char *documentation);
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
在 qtest.c 加入 `do_shuffle` 函式，有做 arguments 和 null 的檢查
```c
// qtest.c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Calling sort on null queue");
error_check();
if (exception_setup(true))
q_shuffle(l_meta.l);
show_queue(3);
return !error_check();
}
```
在 qtest.c 內實作 shuffle，這邊會檢查 head 是否為null或empty，接著每次從還沒被 shuffle 的節點中，選一個來移動到尾端
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
int n = q_size(head);
if (n == 1)
return;
int i;
for (i = n; i > 1; i--) {
int randNum = rand() % i;
struct list_head *tmp = head->next;
while (randNum--)
tmp = tmp->next;
list_move_tail(tmp, head);
}
}
```
# 引入 lib/list_sort.c
+ [linux 的 list_sort ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 定義如下
+ priv 是要傳入給 cmp 的資料
+ cmp 為用來比較的 function
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
cmp argument 的格式
```c
// list_cmp_func_t is a function pointer, it takes (void *, const struct list_head *, const struct list_head *) as argument and return int
typedef int (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *)
```
要套用到本專案的話，單獨把 `list_sort.h` `list_sort.c` 抽出並放入專案目錄，並做以下修改
```diff
// list_sort.h
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H
#include <linux/types.h>
// 從 linux/compiler.h 抽出 likely(x) 和 unlikely(x)
+ #define likely(x) __builtin_expect(!!(x), 1)
+ #define unlikely(x) __builtin_expect(!!(x), 0)
struct list_head;
typedef int
__attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
const struct list_head *,
const struct list_head *);
// 測試程式中，會嘗試傳入 NULL 到 sort 內
// 因此刪除 __attribute__((nonnull(2,3))) 的 function attribute
- __attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif
```
+ 簡化標頭檔的使用
```diff
// list_sort.c
- #include <linux/kernel.h>
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
- #include <linux/string.h>
- #include <linux/list_sort.h>
- #include <linux/list.h>
+ #include "list_sort.h"
+ #include "list.h"
```
+ 刪除 function attribute並加入 null 判斷
```diff
// list_sort.c
- __attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
+ if (head == NULL)
+ return;
```
+ 加入 compare function 在 q_test.c ， 也要 include 標頭檔
```diff
// q_test.c
+ #include "list_sort.h"
// the compare function of element_t compare
+ int compare_element_t(void *priv,
+ const struct list_head *l,
+ const struct list_head *r)
+ {
+ return strcmp(container_of(l, element_t, list)->value,
+ container_of(r, element_t, list)->value);
+ }
```
+ 修改 `qtest.c` 的 do_sort() ，讓執行 sort 時後面加入 `linux` 參數可切換為 linux 版本的 sort
```diff
bool do_sort(int argc, char *argv[])
{
- if (argc != 1) {
- report(1, "%s takes no arguments", argv[0]);
+ if (argc > 2)
+ report(1, "%s takes <=2 arguments", argv[0]);
if (!l_meta.l)
report(3, "Warning: Calling sort on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (exception_setup(true)) {
- q_sort(l_meta.l);
+ if (argc == 2 && !strcmp(argv[1], "linux")) {
+ list_sort(NULL, l_meta.l, compare_element_t);
+ } else {
+ q_sort(l_meta.l);
+ }
}
```
+ 在 makefile 的 `OBJS` 加入 `list_sort.o`
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
- linenoise.o
+ linenoise.o list_sort.o
```
### 比較效能
+ 執行命令檔來比較效能
```c
# Comapre performance of my merge sort with linux sort
option fail 0
option malloc 0
# 30k sample
new
ih a 10000
ih b 10000
ih c 10000
time sort
reverse
time sort linux
free
# 300k sample
new
ih a 100000
ih b 100000
ih c 100000
time sort
reverse
time sort linux
free
# 3M sample
new
ih a 1000000
ih b 1000000
ih c 1000000
time sort
reverse
time sort linux
free
```
+ 在不同 sample 數量下的執行時間比較
| | my merge sort | linux sort |
| -------- | -------- | -------- |
| 30k samples | 0.003 | 0.001 |
| 300k samples | 0.044 | 0.023 |
| 3M samples | 0.619 | 0.350 |
# linux 的 sort 分析
篇幅過長，另外開筆記 [link](https://hackmd.io/@eric88525/list_sort)
# tiny web server
# 運用 Valgrind 排除 qtest 實作的記憶體錯誤
1. 用 valgrind 檢查記憶體，每種測試都有以下問題，都跟 `linenoiseHistoryAdd` 或 `linenoiseHistoryLoad` 有關，而這兩個 function 都在 linenoise.h 被定義。
問題點的呼叫順序為 main -> linenoiseHistoryLoad -> linenoiseHistoryAdd -> linenoiseHistoryAdd -> strdup
```
$ make valgrind
# Test of insert_head and remove_head
==2070491== 10 bytes in 1 blocks are still reachable in loss record 1 of 3
==2070491== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2070491== by 0x4A5850E: strdup (strdup.c:42)
==2070491== by 0x110A27: linenoiseHistoryAdd (linenoise.c:1236)
==2070491== by 0x1115BA: linenoiseHistoryLoad (linenoise.c:1325)
==2070491== by 0x10C82A: main (qtest.c:1010)
```
:::spoiler linenoiseHistoryAdd 的實做 (linenoise.c)
```c=
/* This is the API call to add a new entry in the linenoise history.
* It uses a fixed array of char pointers that are shifted (memmoved)
* when the history max length is reached in order to remove the older
* entry and make room for the new one, so it is not exactly suitable for huge
* histories, but will work well for a few hundred of entries.
*
* Using a circular buffer is smarter, but a bit more complex to handle. */
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
:::
2. 根據 linenoiseHistory 的描述，可以推斷 history 為一個 pointer array，裡面最多紀錄 history_max_len 個 char pointer。 valrind 的報告指出問題會出在 line29: strdup 這裡，當新加入了 line 後，程式有確實的把被移出的 line 給釋放掉，那問題或許會出在 history 在程式執行完成後沒全部釋放
在 linenoise.c 有宣告history
```c=132
static char **history = NULL;
```
:::spoiler main at qtest.c
```c=
#define BUFSIZE 256
int main(int argc, char *argv[])
{
/* sanity check for git hook integration */
if (!sanity_check())
return -1;
/* To hold input file name */
char buf[BUFSIZE];
char *infile_name = NULL;
char lbuf[BUFSIZE];
char *logfile_name = NULL;
int level = 4;
int c;
while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
switch (c) {
case 'h':
usage(argv[0]);
break;
case 'f':
strncpy(buf, optarg, BUFSIZE);
buf[BUFSIZE - 1] = '\0';
infile_name = buf;
break;
case 'v': {
char *endptr;
errno = 0;
level = strtol(optarg, &endptr, 10);
if (errno != 0 || endptr == optarg) {
fprintf(stderr, "Invalid verbosity level\n");
exit(EXIT_FAILURE);
}
break;
}
case 'l':
strncpy(lbuf, optarg, BUFSIZE);
buf[BUFSIZE - 1] = '\0';
logfile_name = lbuf;
break;
default:
printf("Unknown option '%c'\n", c);
usage(argv[0]);
break;
}
}
srand((unsigned int) (time(NULL)));
queue_init();
init_cmd();
console_init();
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
set_verblevel(level);
if (level > 1) {
set_echo(true);
}
if (logfile_name)
set_logfile(logfile_name);
add_quit_helper(queue_quit);
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
```
:::
3. 回到 qtest.c 觀察 main ，在呼叫 `linenoiseHistoryLoad` 後，似乎沒有做任何事來讓 history 被釋放，因此第二點的推論或許是正確的
4. 從 linenoice.h 中看到以下宣告，猜測這跟釋放 history 或 line 有關
```c
void linenoiseFree(void *ptr);
```
5. 回去 linenoice.c 中查找實做，發現了沒被 header file 宣告的函式，此函式可以把 history 釋放
```c
/* Free the history, but does not reset it. Only used when we have to
* exit() to avoid memory leaks are reported by valgrind & co. */
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
}
}
```
6. 而在 linenoise.c ，只有另一個函式呼叫 freeHistory
```c
/* At exit we'll try to fix the terminal to the initial conditions. */
static void linenoiseAtExit(void)
{
disableRawMode(STDIN_FILENO);
freeHistory();
}
```
7. 嘗試找出 `linenoiseAtExit` 和 `freeHistory` 在專案有哪些地方會被執行，結果完全沒有，證實了第 2 點的猜想，根本沒有去釋放 history
8. 因此要修復記憶體問題，就只有手動呼叫 `linenoiseAtExit` 或是 `freeHistory` 了
+ 把 `linenoiseAtExit` 從 static void 改成 void 來改變可視範圍，並移動宣告到 header file
```diff=174
// linenoise.c
- static void linenoiseAtExit(void);
```
```diff=73
// linenoise.h
+ void linenoiseAtExit(void);
```
+ 由於 qtest.c 內並沒有 include `linenoise.h` ，因此嘗試加在`finish_cmd()` 內，會選擇加在這是因為: qtest.c 在 main 結束前有呼叫 `finish_cmd()` 來檢驗程式有沒有正確關閉
```diff=589
// console.c
bool finish_cmd()
{
bool ok = true;
if (!quit_flag)
ok = ok && do_quit(0, NULL);
has_infile = false;
+ linenoiseAtExit();
return ok && err_cnt == 0;
}
```
9. 重新執行 make valgrind 後問題解決，沒有任何記憶體洩漏
Sign in with Wallet
Connect another wallet