owned this note
owned this note
Published
Linked with GitHub
# 2022q1 Homework1 (lab0)
contributed by < `Korin777` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping: 10
CPU MHz: 1800.000
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## queue.c 實作
### q_new
* 一開始我是直接 `malloc` 一個 `head` 並回傳 , 後來發現這樣就無法透過 `list.h` 所提供的 `list_empty` 來判斷 list 是否為空 , 且這樣的 linked list 也並不是雙向環狀的
* 後來透過 `list.h` 提供的 `INIT_LIST_HEAD` 將 `head` 的 `prev` 及 `next` 都指向自己 , 完成雙向環狀的 linked list
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
* 透過 `list.h` 提供的 `list_for_each_entry_safe` 遍歷 list 並釋放每個 `entry` 所配置過的記憶體空間
* list 的每個 `entry` 皆為 `element_t`
* 一個 `entry` 要先釋放 `element_t ->value` 在釋放 `element_t`
* 最後還要再釋放 list 的 `head` , 因為它並不是 `list` 中的一個 `entry` 而是用來當作 list 的開頭
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *ele, *tmpele;
list_for_each_entry_safe (ele, tmpele, l, list)
free(ele->value), free(ele);
free(l);
}
```
### q_insert_head
* `malloc` 一個 `element_t` 作為 list 中一個 `entry`
* `element_t->value` 的 size 為 `strlen(s)+1` , 最後一個字元用來存放空字元 `\0`
* `element_t->list` 是 `struct list_head` 的型態 , 為實際 linked list 互相連接的節點 , 透過 `list.h` 提供的 `list_add` 來將它加在 linked list 的最前面(不包含`head`)
* 當配置 `element_t ->value` 記憶體失敗時 , 要釋放`element_t` 的記憶體 , 才不會產生 memory leak
* 特別用一個 `len` 變數來儲存 `s` 的長度 , 減少重複呼叫 `strlen` 所花的時間 , 不過在測試 time complexity 有時還是會沒通過
* 後來發現 time complexity 沒過得原因在 q_reverse 寫錯了
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
int len = strlen(s);
ele->value = malloc(len + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, len);
ele->value[len] = '\0';
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail
* 和 `q_insert_head` 差再需用 `list.h` 提供的`list_add_tail` 來連接節點
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
int len = strlen(s);
ele->value = malloc(len + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, len);
ele->value[len] = '\0';
list_add_tail(&ele->list, head);
return true;
}
```
### q_remove_head
* 透過 `list.h` 所提供的 `list_entry` , 有了包含在 `element_t` 中的 `list` 記憶體位置 , 就能算出此 `element_t` 的記憶體位置
* 將 `element_t->value` 複製到 `sp` 並將最後一個字元設為空字元 `\0`
* 透過 `list.h` 所提供的 `list_del` , 將節點移除
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *node = head->next;
element_t *ele = list_entry(node, element_t, list);
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(node);
return ele;
}
```
### q_remove_tail
* 和 `q_remove_head` 差在移除的節點為 `head->prev`
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *node = head->prev;
element_t *ele = list_entry(node, element_t, list);
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(node);
return ele;
}
```
### q_size
* 透過 `list.h` 提供的 `list_for_each` 遍歷 linked list 來取長度
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
* `h` 一開始為第一個節點 , `t` 一開始為最後一個節點
* `h` 一直往後走 , `t` 則一直往前走 , 當兩者相同或 `h->next` 與 `t` 相同時 , `h` 恰好為中點
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *h = head->next, *t = head->prev;
while (h != t) {
if (h->next == t)
break;
h = h->next, t = t->prev;
}
element_t *ele = list_entry(h, element_t, list);
list_del(h);
free(ele->value), free(ele);
return true;
}
```
### q_delete_dup
* `tmp` 為字元指標 , 配置記憶體前 `tmp` 不為 NULL 要先釋放 `tmp` 的記憶體 , 以免產生 memory leak
* `tmp`為 NULL 或 `tmp` 和當前 `entry` 的字串不同 , 就看下個 `entry` 的字串是否與當前字串一樣 , 來判斷是否該移除當前節點及釋放對應的記憶體
* `tmp` 和當前 `entry` 的字串相同 , 直接移除當前節點及釋放對應的記憶體
* 若 `tmp` 最後不為 NULL 要釋放 `tmp` 記憶體
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
char *tmp = NULL;
element_t *ele, *tmpele;
list_for_each_entry_safe (ele, tmpele, head, list) {
if (!tmp || strcmp(tmp, ele->value) != 0) {
if (ele->list.next && ele->list.next != head) {
element_t *elen = list_entry(ele->list.next, element_t, list);
if (strcmp(elen->value, ele->value) == 0) {
if (tmp)
free(tmp);
tmp = malloc(sizeof(ele->value));
strncpy(tmp, ele->value, strlen(ele->value));
list_del(&ele->list);
free(ele->value), free(ele);
}
}
} else {
list_del(&ele->list);
free(ele->value), free(ele);
}
}
if (tmp)
free(tmp);
return true;
}
```
### q_swap
* `li` 為相鄰 node 的第一個 node , `tmp` 則為第二個 node , 並將兩者互換
* 當 `li` 為 `head` 或 `tmp` 為 `head` , 表示已經沒有相鄰的 node 需要互換
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *li = head->next, *tmp;
while (li != head) {
tmp = li->next;
if (tmp == head)
break;
li->prev->next = tmp;
tmp->next->prev = li;
li->next = tmp->next;
tmp->next = li;
tmp->prev = li->prev;
li->prev = tmp;
li = li->next;
}
}
```
### q_reverse
* `h` 一開始為第一個節點 , `t` 一開始為最後一個節點
* `h` 一直往後走 , `t` 則一直往前走 , 因為 `h` 跟 `t` 互換 , `h` 要更新為 `t->next` , `t` 則更新為 `h->next`
* 當 `h` 與 `t` 相同或 `t->next->prev` 與 `t` 相同 , linked list 已反轉完畢
```c
void q_reverse(struct list_head *head)
{
struct list_head *tmp, *htmp, *ttmp;
if (!head || list_is_singular(head))
return;
struct list_head *h = head->next, *t = head->prev;
head->next = t;
head->prev = h;
while (h != t) {
htmp = h->next;
ttmp = t->prev;
tmp = h->next;
h->next = h->prev;
h->prev = tmp;
tmp = t->next;
t->next = t->prev;
t->prev = tmp;
if (t->next->prev == t)
break;
h = htmp, t = ttmp;
}
if (h == t) {
tmp = h->prev;
h->prev = h->next;
h->next = tmp;
}
}
```
* 原本以為 `trace-17-complexity` 有時會沒 pass 的原因只跟 q_insert_tail, q_insert_head, q_remove_tail, q_remove_head 有關 , 後來發現原來是我 q_reverse 寫錯了 , `t->prev` 是 `t->next` 才對 , 而 `tmp` 的宣告也是多餘的
* 不過上面那個錯的 `reverse` 還是能成功將 reverse 後的 linke list show 出來 , 儘管前半段 linked list 節點的 `prev` 應該都是錯的
* 後來推上 github `trace-17-complexity` 還是沒過 , 在本地端測試確實有時不會過 , 還要在看看是那出了問題
```c
void q_reverse(struct list_head *head)
{
struct list_head *htmp, *ttmp;
if (!head || list_is_singular(head))
return;
struct list_head *h = head->next, *t = head->prev;
head->next = t;
head->prev = h;
while (h != t) {
htmp = h->next;
ttmp = t->prev;
h->next = h->prev;
h->prev = htmp;
t->prev = t->next;
t->next = ttmp;
if (t->next->prev == t)
break;
h = htmp, t = ttmp;
}
if (h == t) {
htmp = h->prev;
h->prev = h->next;
h->next = htmp;
}
}
```
### q_sort
* 參考 [geekforgeek](https://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/) 實作出適用於 Circular Doubly Linked List 的遞迴法（Top-down） Merge Sort
* 在 Test performance 無法 pass , 在 `qtest` 跑 `trace-14-perf.cmd` 的測資 ， 發現會 Segmetation Fault
* 自己測試後發現 , list 的 size 在約 1400000 就會 Segmetation Fault , 應該是 function 遞迴太多次的關係 , 所以下面改用迭代法（Bottom-up）實作
```c
struct list_head *merge(struct list_head *first, struct list_head *second)
{
if (!first)
return second;
if (!second)
return first;
element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list);
// elef->value < eles->value
if(strcmp(elef->value,eles->value) < 0)
{
first->next = merge(first->next,second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else // elef->value >= eles->value
{
second->next = merge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
struct list_head *split(struct list_head *head)
{
struct list_head *fast = head, *slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
struct list_head *temp = slow->next;
slow->next = NULL;
return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
if (!head || !head->next) {
return head;
}
struct list_head *second = split(head);
head = mergeSort(head);
second = mergeSort(second);
return merge(head, second);
}
```
* 改用迭代法（Bottom-up）實作
* 在 Test performance 還是無法 pass , 在 qtest 跑 trace-14-perf.cmd 的測資 ， 雖然解決了 Segmentation Fault 的問題 卻產生了 time limit exceeded
* 因為 linked list 記憶體並不連續 , 無法像陣列那樣直接取得某個位置的值 , 而必須慢慢往後走 , 導致當要 merge 兩個子 list 前會產生許多很長的走訪
* 所以我沿用原本的遞迴 merge sort ， 但將 merge 的過程改為迭代
```c
void merge_iterative(struct list_head *first, struct list_head *second, int
ls, int rs) {
int l = 0, r = 0;
element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list); while(l < ls && r < rs) {
if(strcmp(elef->value,eles->value) < 0)
{
first = first->next;
l++;
if(l < ls)
elef = list_entry(first,element_t,list);
}
else // elef->value >= eles->value
{
struct list_head *tmp = second->next;
list_del(second);
list_add_tail(second,first);
second = tmp;
r++;
if(r < rs)
eles = list_entry(second,element_t,list);
}
}
}
void mergeSort_iterative(struct list_head *head,int size)
{
int sz = 1,n = size;
while(sz < n) {
struct list_head *f = head->next,*s = head->next, *nf = f, *ns;
int i = 0;
int j;
for(j = 0; j < sz; j++)
s = s->next;
ns = s;
while(i < n-1) {
if(size - i <= sz)
break;
int l = sz, r = sz;
if(n-i-sz < sz)
r = n-i-sz;
for(j = 0; j < sz*2; j++) {
if(nf->next)
nf = nf->next;
if(ns->next)
ns = ns->next;
}
merge_iterative(f,s,l,r);
f = nf;
s = ns;
i += sz*2;
}
sz += sz;
}
}
```
* 將 merge 改為迭代的遞迴 mergesort , 總算通過 Test performance
* merge 用來將兩個子 list 合併 , 回傳合併後的head
* split 將 list 切半為兩個子 list
```c
struct list_head *merge(struct list_head *first, struct list_head *second)
{
if (!first)
return second;
if (!second)
return first;
struct list_head *tmphead = NULL, *tf = first, *ts = second;
element_t *elef = list_entry(first, element_t, list),
*eles = list_entry(second, element_t, list);
while (first && second) {
if (strcmp(elef->value, eles->value) < 0) {
if (!tmphead)
tmphead = first;
tf = first;
first = first->next;
if (first)
elef = list_entry(first, element_t, list);
} else // elef->value >= eles->value
{
if (!tmphead)
tmphead = second;
struct list_head *tmp = second->next;
struct list_head *next = second->next;
struct list_head *prev = second->prev;
if (next)
next->prev = prev;
if (prev->next == second)
prev->next = next;
prev = first->prev;
if (prev->next == first)
prev->next = second;
if (second->next)
second->next = first;
second->prev = prev;
first->prev = second;
ts = second;
second = tmp;
if (second)
eles = list_entry(second, element_t, list);
}
}
if (first) {
ts->next = first;
first->prev = ts;
}
if (second) {
tf->next = second;
second->prev = tf;
}
return tmphead;
}
struct list_head *split(struct list_head *head)
{
struct list_head *fast = head, *slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
struct list_head *temp = slow->next;
slow->next = NULL;
return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
if (!head || !head->next) {
return head;
}
struct list_head *second = split(head);
head = mergeSort(head);
second = mergeSort(second);
return merge(head, second);
}
```
* 將 linked list 最後一個節點的 `next` 改為 null , 在 `split` 時才不會又跑回最前面
* 做完 merge sort 要更改 `head` 的 `prev` 、 最後一個節點的 `next` 及第一個節點的 `prev`
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = mergeSort(head->next);
struct list_head *li = head;
while (li->next) {
li = li->next;
}
head->prev = li;
head->prev->next = head;
head->next->prev = head;
}
```
* 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中的 `mergeTwoLists` , 透過指標的指標實做 `merge` 函式 , 簡化程式碼
* 用這方式 merge 完後的 linked list `prev` 指標並不會被修改 , 必須在 `mergeSort` 後把它改回來
```c
struct list_head *merge(struct list_head *first, struct list_head *second)
{
struct list_head *head = NULL, **ptr = &head, **node;
for(node = NULL; first && second; *node = (*node)->next) {
element_t *elef = list_entry(first, element_t, list), *eles = list_entry(second, element_t, list);
node = (strcmp(elef->value, eles->value) <= 0) ? &first : &second;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *)((uintptr_t) first | (uintptr_t) second);
return head;
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = mergeSort(head->next);
struct list_head *fix_prev ,*li = head;
while (li->next) {
fix_prev = li;
li = li->next;
li->prev = fix_prev;
}
head->prev = li;
head->prev->next = head;
}
```
## Linux list_sort
### 引入 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 到 lab0-c
* 將 linux listsort 程式碼拿到 `queue.c` 中
* 宣告用來比較 queue 每個 `entry` 的字串大小的 compare 函式
```c
int list_val_cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *elea = list_entry(a,element_t,list), *eleb = list_entry(b,element_t,list);
// elea->value <= eleb->value return <= 0
// elea->value > eleb->value return > 0
return strcmp(elea->value,eleb->value);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
list_sort(NULL,head,list_val_cmp);
}
```
### 比較自己實做的 Merge Sort 和 Linux 核心程式碼之間效能落差
沿用 `trace-14-perf.cmd` 的測資 , 並透過 `qtest` 所提供的 `time` 命令來測量排序時間
```
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
time
sort
time
```
| 排序函式 | 執行時間 |
| --- | --- |
| My MergeSort | 0.95s |
| Linux MergeSort | 0.55s |
## 在 qtest 提供新的命令 shuffle
### 在 qtest.c 加上 shuffle 指令
* 在 `console_init` 新增 shuffle 指令
* `ADD_COMMAND` 是定義在 `console.h` 的巨集 `#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)` , 也是為什麼當我們想新增一個指令 `cmd` , 對應的 function 一定要是 `do_cmd`
```c
ADD_COMMAND(shuffle, " | Do Fisher–Yates shuffle in queue");
```
```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: Try to access null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
### 實做 Fisher–Yates shuffle
* Fisher–Yates shuffle
1. 有一長度為 len 的 list , 設 i 初始為 len
2. 每次隨機取一數 j , 0 <= j <= i
3. 將第 j 個節點與第 i 個節點互換 , 並將 i - 1
4. 重複步驟 2 、 3 直到 i = 1
* `shuffle_point` 為當前要調換位置的節點 , `next_shuffle_point` 為下一個要調換的節點
* 當要互換的節點是同一個節點 , 不做任何事
* 當要互換的節點相鄰 , 移除第一個節點並接在第二個之後
* 其餘的情況 , 先移除第一個節點並接在第二個之後 , 再移除第二個節點並接在原本第一個節點的 `prev` 之後
* `next_shuffle_point` 在互換節點相鄰時 , 節點互換後這時`shuffle_point` 即為下次的 `shuffle_point` , 所以 `next_shuffle_point` 要改為 `shuffle_point->prev`
```c
void shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int len = q_size(head), x, it;
struct list_head *li, *shuffle_point = head->prev, *tmp, *next_shuffle_point = shuffle_point->prev;
while(len-- > 1) {
li = head->next, it = 0, x = rand() % len;
while (it++ < x) {
li = li->next;
}
if(li == shuffle_point);
else if(li->next == shuffle_point) {
list_del(li);
list_add(li,shuffle_point);
}
else {
tmp = li->prev;
list_del(li);
list_add(li,shuffle_point);
list_del(shuffle_point);
list_add(shuffle_point, tmp);
}
if(next_shuffle_point != shuffle_point) {
shuffle_point = next_shuffle_point;
next_shuffle_point = next_shuffle_point->prev;
next_shuffle_point = shuffle_point->prev;
}
else {
next_shuffle_point = shuffle_point->prev;
}
}
}
```
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
透過 make valgrind 可以看到以下訊息 , 這裡取 `trace-01-ops` 產生的訊息來看 , 看起來像是有記憶體沒有釋放
```
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==19148== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==19148== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148== by 0x4A4D50E: strdup (strdup.c:42)
==19148== by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19148== by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148== by 0x10C861: main (qtest.c:1016)
==19148==
==19148== 137 bytes in 19 blocks are still reachable in loss record 2 of 3
==19148== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148== by 0x4A4D50E: strdup (strdup.c:42)
==19148== by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19148== by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148== by 0x10C861: main (qtest.c:1016)
==19148==
==19148== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==19148== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148== by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19148== by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148== by 0x10C861: main (qtest.c:1016)
==19148==
--- trace-01-ops 5/5
```
`qtest.c`
```c
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
`linenoise.c`
```c
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;
}
int linenoiseHistoryLoad(const char *filename)
{
FILE *fp = fopen(filename, "r");
char buf[LINENOISE_MAX_LINE];
if (fp == NULL)
return -1;
while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
char *p;
p = strchr(buf, '\r');
if (!p)
p = strchr(buf, '\n');
if (p)
*p = '\0';
linenoiseHistoryAdd(buf);
}
fclose(fp);
return 0;
}
```
* 一開始以為是 `linenoiseHistoryAdd` 的 `linecopy` 沒有釋放 , 因為他透過 `strdup` 配置記憶體卻沒釋放 , 便嘗試在函式結束前將它釋放 , 結果訊息卻便多了
```
+++ TESTING trace trace-01-ops:
==19917== Invalid read of size 1
==19917== at 0x483FED4: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917== Address 0x4ba1ed0 is 0 bytes inside a block of size 5 free'd
==19917== at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917== Block was alloc'd at
==19917== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x4A4D50E: strdup (strdup.c:42)
==19917== by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917==
==19917== Invalid read of size 1
==19917== at 0x483FEE8: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917== Address 0x4ba21f1 is 1 bytes inside a block of size 14 free'd
==19917== at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917== Block was alloc'd at
==19917== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x4A4D50E: strdup (strdup.c:42)
==19917== by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917==
# Test of insert_head and remove_head
==19917== 160 bytes in 1 blocks are still reachable in loss record 1 of 1
==19917== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917== by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19917== by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917== by 0x10C861: main (qtest.c:1016)
==19917==
--- trace-01-ops 0/5
```
* 決定先看看 `linenoiseHistoryLoad(HISTORY_FILE)` 的 `HISTORY_FILE` 是什麼 , 發現原來是紀錄 `qtest cmd` 曾打過的指令紀錄 `.cmd_history` , 而這些紀錄會記在 `**history` 這個類似字串陣列裡頭
* 所以嘗試把這個 `histroy` 給釋放 , 寫了一個freeHistory 的函式來完成 , 卻發現 `linenoise.c` 原本就有定義這個函式了
* 最後 , 在 `linenoise.c` 裡寫一個函式 `freelinenoise` 來呼叫釋放 histroy 記憶體的函式 `linenoiseAtExit` , 並在 `qtest` 主程式結束前呼叫它 , 成功解決 memory leak 的問題
```c
void freelinenoise() {
linenoiseAtExit();
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
