---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [ShiaoLin](https://github.com/ShiaoLin) >
:::danger
不要打錯自己的 GitHub 帳號名稱
:notes: jserv
:::
## 實驗環境
```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): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
Stepping: 3
CPU MHz: 2700.000
CPU max MHz: 3300.0000
CPU min MHz: 800.0000
BogoMIPS: 5399.81
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
```
## :penguin: 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [x] 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [x] 在提交程式變更前，務必詳閱 [如何寫好 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/)
- [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [x] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 在 `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) 觸發錯誤，應予以排除
- [x] 運用 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
## 針對佇列的操作
### q_new
配置一空間給新的 list
```c
struct list_head *q_new()
{
struct list_head *n = malloc(sizeof(struct list_head));
if (!n)
return NULL;
INIT_LIST_HEAD(n);
return n;
}
```
### q_free
除了釋放 list 所配置的空間之外，也要釋放該 list 所代表的 element_t 結構體的其他變數，了解如何透過 `list_entry` 這個巨集取得 list 所在的結構體的開頭地址，額外參考[這篇文章](https://cnblogs.com/yangguang-it/p/11667772.html)
:::warning
使用通順的漢語表達，平常就做好這些「逐字稿」，日後你在面試場合才會表現更好。
:notes: jserv
:::
另外要進行走訪 list 所有的結構體要使用 list_for_each_entry ，但因為涉及節點的變動，使用 list_for_each_entry_safe 來確保執行操作時不造成指標錯誤，最後額外對 l 進行釋放
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *pos, *n;
list_for_each_entry_safe (pos, n, l, list)
q_release_element(pos);
free(l);
}
```
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
q_release_element(e);
return false;
}
list_add(&e->list, head);
return true;
}
```
### q_insert_tail
與 q_insert_head 類似，僅改用 list_add_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
q_release_element(e);
return false;
}
list_add_tail(&e->list, head);
return true;
}
```
### q_remove_head
使用 list_first_entry 取得第一個 entry 的結構體指標，再進行字串操作
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *e = list_first_entry(head, element_t, list);
list_del(&e->list);
if (sp != NULL) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
:::success
原先 `Git Action` 都會卡在 `trace-17-complexity` 測試，後來將 `if (sp != NULL)` 改成 `if(sp)` 就通過測試了
:::
### q_remove_tail
類似 q_remove_head操作，改用 list_last_entry 取得最後一個 entry 結構體指標
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *e = list_last_entry(head, element_t, list);
list_del(&e->list);
if (sp != NULL) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
### q_size
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int size = 0;
struct list_head *pos;
list_for_each (pos, head)
++size;
return size;
}
```
### q_delete_mid
參考[ LeetCode 的 Discuss ](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/discuss/1715218/C-solution-with-indirect-pointer)利用快慢指標尋找中間節點
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast, *slow;
for (fast = head->next, slow = head->next;
fast != head && fast->next != head;
fast = fast->next->next, slow = slow->next)
;
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### q_delete_dup
比較前後兩節點內的資料是否相等，如有相等先將第一個節點紀錄在 prev 中，然後依序移除往後的節點，最後再執行移除首個節點
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return NULL;
if (list_empty(head))
return true;
struct list_head *start = head->next, *end = NULL, *prev = NULL;
while (end != head) {
end = start->next;
element_t *e1 = list_entry(start, element_t, list);
element_t *e2 = list_entry(end, element_t, list);
while (end != head && !strcmp(e1->value, e2->value)) {
prev = start;
struct list_head *next = end->next;
list_del(end);
q_release_element(e2);
end = next;
e2 = list_entry(end, element_t, list);
}
if (prev) {
e1 = list_entry(prev, element_t, list);
list_del(prev);
q_release_element(e1);
prev = NULL;
}
start = end;
}
return true;
}
```
### q_swap
參考 linux/lish.h 內提供的 list_swap 進行操作
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *n;
for (n = head->next; n != head && n->next != head; n = n->next) {
struct list_head *next = n->next;
list_del(n);
list_add(n, next);
}
}
```
### q_reverse
```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 範例](https://npes87184.github.io/2015-09-12-linkedListSort/)以及[ linked list 講座](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)實做，用快慢指標以及遞迴進行 lists 的分割，利用指標的指標進行 lists 的合併，在進行 merge sort 之前須先將原本的 doubly linked list 破壞，待排序後再復原
```c
struct list_head *merge_two_lists(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; l1 && l2; *node = (*node)->next) {
node = strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) <= 0
? &l1 : &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return head;
}
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head->next, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
return merge_two_lists(merge_sort(head), merge_sort(fast));
}
void q_sort(struct list_head *head)
{
if (q_size(head) <= 1)
return;
struct list_head *list = head->next;
head->prev->next = NULL;
list = merge_sort(list);
head->next = list;
struct list_head *n;
for (n = head; n->next != NULL; n = n->next)
n->next->prev = n;
head->prev = n;
n->next = head;
}
```
>但是目前在 GitHub Action 上的 Testing trace-14-sort-perf 沒有得到分數，待詳讀[ lib/list.c ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)後再做修改
### 比較 q_sort 和 Linux list_sort 核心程式碼之間效能落差
* 在 `qtest.c` 內實作 `list_sort()`，在 `qtest` 中使用指令進行效率上的比較
```c
bool do_linux_sort(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 no 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))
list_sort(NULL, l_meta.l, cmp_func);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
if (l_meta.size) {
for (struct list_head *cur_l = l_meta.l->next;
cur_l != l_meta.l && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcasecmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
show_queue(3);
return ok && !error_check();
}
```
* 參考 `trace-15-perf.cmd` 的方式建立了一個 `trace-sort-cmp.cmd` 命令檔，測試兩種排序項目，其中隨機資料排序用兩種 `merge sort` 各作五次
```
# Test performance of sort between q_sort and list_sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
time sort
reverse
time linux_sort
free
new
ih RAND 100000
time sort
free
new
ih RAND 100000
time linux_sort
free
...
```
:::spoiler 得到下列結果
```
$ ./qtest -f ./traces/trace-sort-cmp-perf.cmd
cmd> # Test performance of sort between q_sort and list_sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> time sort
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
Delta time = 1.001
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> time linux_sort
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
Delta time = 0.460
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [bjtev wowcbj rkfdbt glbkeoy zpjueen koahqbus nhjgp rlratpv gwcblbrr sssautfn xsuuihg fqbybnaiq knosuv ehtpwhmx fwmcrim lanpzzifh oxebip ieuuw cxmqf njiimk epksn mitzx svbcnqb gowfe nulpwo jlrhsp nabvyqsgx wmzulwaac eyqjomly mnkmkh ... ]
cmd> time sort
l = [aaanapyij aaapdsead aaavvoa aaaxvfbbo aaaylzvkm aabfiz aablxwhsp aabrmepi aabxx aabzlgu aacckhhlb aacepwzkf aaclc aacqrnaru aacsn aacssu aactfga aacvk aacxw aaddbydt aadpclu aadqfe aadsccwv aadxpnxe aadxzcpf aaeernc aaegs aaehmwkil aaekt aaemffiv ... ]
Delta time = 0.127
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [zkhonz fikikk yuxpgawo qlufh jctdy eclokd dyuplwpuu qwykazzu mjrjyn frxmnay ogscyn xovfk udmtw qwqhg guxtvvfk ytsjn vrhvnx pnlzykoom xwnosipmj znqasoq azvqbz sulljkows aetwlybcf whroz ybtomvvtn sdugd xijjzesq sjmqjafg yewnamx ebmqv ... ]
cmd> time linux_sort
l = [aaahz aaanhge aaaooiei aaaswhodc aaazgb aabboftqy aabkasej aabkkj aabnp aabpp aabtlgac aabzvqh aacgde aacgyjlh aacjqtu aacpq aacqe aacrclyve aacszd aacwlo aadaxciin aadgscpfq aadrksw aadrqgexw aadstgc aadtmxcfx aadwzjtp aadzlokrh aaecfjpsx aaenxuqq ... ]
Delta time = 0.096
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [jbbavpw whlhofcbg uowxegfgh yrwln lcyif cqigzajcl fewjlvduc rgoghx pidhkbej nlcjlbhx sshovc xvkrchv matglwbsy lseuexpta djuch xsjbv hktvnck gfxybms rziegned mjshql czyuq thijnefy tubtxnbsf oeofwwlqb ckzdmivp gfsfhnun ctqab juqvyzh zxctne vgbmm ... ]
cmd> time sort
l = [aaafvwm aaagr aaaqfqeuo aaarxjoem aaauaj aaawgpts aabfako aabhb aabiu aabkqlgbu aabmcyjm aabrimm aabxg aabzycix aacaixrce aacdrd aacehqcyq aacfpl aacfy aacmjrxcf aacsevw aacublgx aadajabfk aadgclivj aadgx aadjkqrd aadmp aadurqpq aaduwpvd aaeqxa ... ]
Delta time = 0.170
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [khedi unudtcjz jrkmb radwp jggdegetd ajcpp owlkdoxgq syzap vzned fuuhbnbzk pqbugp dlgnmujbf qqbah hpzdq jkzlupj kdhkrqrn rdubnv wmszgyk vvfpx cvpsnjjri gjbsg oezzoqcc cfrbd avjvdemcq yxnoyofkk vhvrxjxsp jqzkag sjnnoqzz cbhfmqhx bkjyl ... ]
cmd> time linux_sort
l = [aaacrntdg aaadvlr aaafz aaahvaxg aaamev aaaqqq aaatt aabain aabdkfgw aabdlzi aabenw aabginr aabqymixn aabzu aabzzcox aacgnwem aacgylt aacnpdomg aacwj aadggrcg aadgpi aadktlkwu aadmp aadqgwuzl aadqs aadvajamy aaehwybwv aaeluc aaeswfd aaetavo ... ]
Delta time = 0.106
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [pfrous kszwlpwxk cmnvxo yahobtdz ysqkkro vcgbjqt ckddqb lmqbb dhksajz zeygyuh rptqnwr kezaxnty anqwslp sxlqzdt tbvroqdto dplwc eemwapd mwltmdxq dguceevbt osceqfnja fbppmj jtwmzxwir puowdj nxiksg cfbihs hzwygittq pxehgyy kvewmju zgihvrohm wmqjs ... ]
cmd> time sort
l = [aaabck aaabosrad aaaev aaalnkz aaass aabfyhetn aabmvci aaboucp aabtudvvy aacerdi aacgv aacgy aachfq aaclrfcfq aacmirih aacoicl aacrnqyd aadjbo aadjmw aadjvbef aadpgezo aadseeiyn aadtnnau aadzpjhhx aaebjgw aaech aaeigff aaekvabbf aaelvng aaeodityb ... ]
Delta time = 0.166
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [ihfgkdn nnybop yfgvuoepb maoouhzy npxgtuo zskhdv zwhlmat iicldfgcr jjxuq oeoqlwj ebmtiztbv cfirbvxns qwhuzkz fkxzsrl trjwyvn osjkjki wopkufrj qbqrebfm ejtturz kjfvpmgqh rrjya wojoplv dwbqlfhj clqjhhp wfdheqz itlncp plvuafwr yjsixn pgascj nkzry ... ]
cmd> time linux_sort
l = [aaadafc aaagndesw aaaknpus aaaprgcz aaaqlp aabadhas aabakgbc aabjis aabnvols aabojcbkc aabozk aabrrkwe aacbx aaccb aaccofgtp aacee aaceq aacgjsesc aackcsiow aaclbaav aacpnx aadbbk aaddjdr aadnb aadnvcqs aadzuvmpr aaebc aaeennb aaefof aaejpsj ... ]
Delta time = 0.102
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [sgyvoh ibnfgzok pzsdij aoconpjk hlxfm ahqmgryl etwwamzmv rzyyom ltywc mzrfq kilbxafsl ymspjfrs bukomctrw ajwkbjgk jwkvr tlqrc ksluhoic lvque bdakwrna hbkmbo kjstihtn cyjtpac nzdjfych rrqjzm hyfncoqrj kegzywe peqpg viedhd nanuodvw seibazd ... ]
cmd> time sort
l = [aaaausrfs aaadgnpf aaaluq aaalzfomq aaamyeust aaauio aaavaivm aaazqnl aabka aabkmxat aabpthecm aabtu aabvpdmf aacbqwf aacolxg aacvuu aadacxhze aadbdxvh aadfj aaekgetzg aaeshtgqx aaetzjmrw aafakfopq aaffg aafjb aafol aafutkx aagiegnld aagmcnve aagnou ... ]
Delta time = 0.173
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [cijszeaq slhbkfiy lttptppvv twqccso eeccxlhj asaql ovowqd igawri ygnnrao mjggtejgb ahplnyure alvxmncui ddvxkgwvh trfrnk bunoiaauz wxumue lmxqjeeln owiycgov oahqcgxsq qtuxpmyz ibxsaylg qzivex ztgjspg ycmgu smffnadd ihixh cmtuknis mosdina gftpxm dswrmh ... ]
cmd> time linux_sort
l = [aaabr aaakms aaammn aaamphx aaayjzzkr aabbhkq aacaut aaclbv aacotrcdm aacpsgk aacvf aadklkt aadoa aadsbejxm aadtagk aadthu aadxemjyp aaeegfg aaefwz aaegmf aaegvhq aaeigawde aaellsf aaemuqlcl aaeqjjfsh aaeqpwsjm aaervpmm aaeyluxoo aaeyuht aafooabex ... ]
Delta time = 0.099
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [tkwfvf axdjyen uorus lhoike eswhc faevxsldq rkegcxbo ofxvujvt iaqsxyyb maups hpmxw geivgedr gemeap hgdqh chspcugjq qqiiuwywd vtnbu beykscr ihqdnoaft voebs dzhobf zbrcdhte yzpzac dohcyyvlt jvnbbo yhnombblh vzmpszkp lzemopvsr rrnvwrzd geavmky ... ]
cmd> time sort
l = [aaabiic aaaly aabcez aabjqm aabqhqvgp aabvony aabvz aabwgkiiv aacbcmc aaciaund aacjrte aacrklab aactyix aacvzvfl aacwzvlwm aadfudny aadltcisn aadoy aadptc aadptdnfx aaeacd aaefr aaemv aaenoiwm aaepxg aaewzkvwp aaeyey aafcvtoxw aafmuqy aafofins ... ]
Delta time = 0.171
cmd> free
l = NULL
cmd> new
l = []
cmd> ih RAND 100000
l = [saclec esalqugw mpvvdbpbm gkhio yjgiptso eclcqfmio olkhng wshjbmig ixmtkr cltawhz jmohljezc drpjuj bvqwl xyztvl edubhe hovoy rscvxmwx rjplave vjmmgu epykc hlnyur ujmpxh zrcuuhjgn crgzzp oswmuuo vuddnkd mhpbwfjgc eetzkxcw jhcpiq ujmhgppq ... ]
cmd> time linux_sort
l = [aaaal aaafavbks aaagrdqr aaaiijt aaajjnr aaaqkqrz aaarlwgw aaarqw aaazbuya aabctdt aabmz aabqadey aabrmw aabrx aabspmvn aabzf aabznxxd aacalqx aacbjiyz aaceopih aacipkuij aaclp aacslicfz aacztxtx aaddvxkah aadgbe aaduinkw aadymohi aadywp aaecreb ... ]
Delta time = 0.102
cmd> free
l = NULL
Freeing queue
```
:::
看到在 `dolphin` 與 `gerbil` 項目測試中，`list_sort` 比起 `q_sort` 快上 ==54％==，而同樣在隨機排序中 `list_sort` 平均耗費時間為 0.101 sec，`q_sort` 平均為 0.161 sec，也就是速度快上約 ==37％== 左右
#### 原因分析
:::warning
TODO
:::
## qtest解析
從作業指示知道 `qtest` 會經過下列一路的流程
```
main → run_console → cmd_select → interpret_cmd → parse_args
```
```
while ((c = getopt(argc, argv, "hv:f:l:")) != -1)
```
得知 `qtest` 本身有提供4種 option 輸入，分別是 `-h`、`-f filename`、`-v vlevel` 及 `-l lfile`，所以我們可利用的命令參數舉例如下：
```
$ ./qtest -h
$ ./qtest -f ./traces/trace-01-ops.cmd
$ ./qtest -v 1
$ ./qtest -l cmd_log
```
透過 `run_console` 可分出帶有命令檔案的批次操作或手動輸入命令的操作
:::spoiler run_console()
```c=
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
:::
* 如果沒有 `-f filename` ，則會進入 `line: 8-15` 的操作
* 如果有，則進入 `line: 16-19`的操作
:::spoiler cmd_select()
```c=
int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
int infd;
fd_set local_readset;
if (cmd_done())
return 0;
if (!block_flag) {
/* Process any commands in input buffer */
if (!readfds)
readfds = &local_readset;
/* Add input fd to readset for select */
infd = buf_stack->fd;
FD_SET(infd, readfds);
if (infd == STDIN_FILENO && prompt_flag) {
printf("%s", prompt);
fflush(stdout);
prompt_flag = true;
}
if (infd >= nfds)
nfds = infd + 1;
}
if (nfds == 0)
return 0;
int result = select(nfds, readfds, writefds, exceptfds, timeout);
if (result <= 0)
return result;
infd = buf_stack->fd;
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
if (has_infile) {
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
}
return result;
}
```
:::
:::warning
TODO 解析
:::
:::spoiler interpret_cmd()
```c=
static bool interpret_cmd(char *cmdline)
{
if (quit_flag)
return false;
#if RPT >= 6
report(6, "Interpreting command '%s'\n", cmdline);
#endif
int argc;
char **argv = parse_args(cmdline, &argc);
bool ok = interpret_cmda(argc, argv);
for (int i = 0; i < argc; i++)
free_string(argv[i]);
free_array(argv, argc, sizeof(char *));
return ok;
}
```
:::
函式內部使用 `line:11 bool ok = interpret_cmda(argc, argv);` 去依序比對命令是否批配 `cmd_list` 中的命令，如果批配則執行
:::spoiler parse_args()
```c=
static char **parse_args(char *line, int *argcp)
{
/*
* Must first determine how many arguments there are.
* Replace all white space with null characters
*/
size_t len = strlen(line);
/* First copy into buffer with each substring null-terminated */
char *buf = malloc_or_fail(len + 1, "parse_args");
buf[len] = '\0';
char *src = line;
char *dst = buf;
bool skipping = true;
int c;
int argc = 0;
while ((c = *src++) != '\0') {
if (isspace(c)) {
if (!skipping) {
/* Hit end of word */
*dst++ = '\0';
skipping = true;
}
} else {
if (skipping) {
/* Hit start of new word */
argc++;
skipping = false;
}
*dst++ = c;
}
}
/* Now assemble into array of strings */
char **argv = calloc_or_fail(argc, sizeof(char *), "parse_args");
src = buf;
for (int i = 0; i < argc; i++) {
argv[i] = strsave_or_fail(src, "parse_args");
src += strlen(argv[i]) + 1;
}
free_block(buf, len + 1);
*argcp = argc;
return argv;
}
```
:::
* 將 `command line` 的命令整理成類似二維字串陣列指標 `**arg`，將空白鍵轉為 `*argv[len] = '\0'` 作為字串的結尾，並且複寫命令陣列的字串數量 `argc`
## 在 `qtest` 提供新的命令 `shuffle`
* 觀察 `command` 的運作模式，透過 `ADD_COMMAND` 加入命令，而 `ADD_COMMAND` 本身是透過 macro 定義在 `console.h` 中，所以我們可以新增一 `ADD_COMMAND` 命令
```
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
`add_cmd` 會將 `name`、`operation`、`documentation` 推入 `cmd_list` 中，`cmd_list` 本身是個 `linked list` 結構體，使 `interpret_cmda` 在執行的過程中可以去比對輸入的 `command` 是否與 `cmd_list` 中的命令名稱匹配
:::spoiler cmd_ele結構體
```
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
:::
* 了解[ Fisher–Yates shuffle ](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)演算法，其核心定義為透過生成真隨機亂數 `k` ，將位於 `k` 的資料向後插入，而插入的位置則向前遞增，實做算法如下：
```c
bool q_shuffle(struct list_head *head, int cnt)
{
if (!head || list_empty(head))
return false;
for (struct list_head *result = head->prev; --cnt; result = result->prev) {
int target = rand() % (cnt + 1);
struct list_head *scratch = head->next;
for (int i = 0; i < target; i++)
scratch = scratch->next;
element_t *r = list_entry(result, element_t, list);
element_t *s = list_entry(scratch, element_t, list);
char *tmp = r->value;
r->value = s->value;
s->value = tmp;
}
return true;
}
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 shuffle on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling shuffle on single node");
error_check();
bool ok = false;
set_noallocate_mode(true);
if (exception_setup(true))
ok = q_shuffle(l_meta.l, cnt);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return ok && !error_check();
}
```
:::spoiler 實做結果如下：
```
$ ./qtest
cmd> new
l = []
cmd> it 1
l = [1]
cmd> it 2
l = [1 2]
cmd> it 3
l = [1 2 3]
cmd> it 4
l = [1 2 3 4]
cmd> it 5
l = [1 2 3 4 5]
cmd> it 6
l = [1 2 3 4 5 6]
cmd> it 7
l = [1 2 3 4 5 6 7]
cmd> it 8
l = [1 2 3 4 5 6 7 8]
cmd> it 9
l = [1 2 3 4 5 6 7 8 9]
cmd> shuffle
l = [7 5 8 4 3 1 9 2 6]
cmd> sort
l = [1 2 3 4 5 6 7 8 9]
cmd> shuffle
l = [4 3 6 7 2 5 1 9 8]
cmd> sort
l = [1 2 3 4 5 6 7 8 9]
cmd> shuffle
l = [6 1 2 7 9 4 5 3 8]
cmd>
Freeing queue
```
:::
## 嘗試整合 tiny-web-server
:::warning
TODO
:::
## 以 Valgrind 分析記憶體問題
了解 `qtest` 的運作機制，使用命令：
```
$ valgrind -q --leak-check=full ./qtest -f ./traces/trace-01-ops.cmd
```
會得到下列結果
```
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbil]
cmd> ih bear
l = [bear gerbil]
cmd> ih dolphin
l = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil]
cmd> rh bear
Removed bear from queue
l = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
l = []
cmd>
Freeing queue
==75875== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==75875== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==75875== by 0x4A4D50E: strdup (strdup.c:42)
==75875== by 0x11113C: linenoiseHistoryAdd (linenoise.c:1236)
==75875== by 0x111CCF: linenoiseHistoryLoad (linenoise.c:1325)
==75875== by 0x10CF53: main (qtest.c:1314)
==75875==
==75875== 155 bytes in 19 blocks are still reachable in loss record 2 of 3
==75875== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==75875== by 0x4A4D50E: strdup (strdup.c:42)
==75875== by 0x1110B0: linenoiseHistoryAdd (linenoise.c:1236)
==75875== by 0x111CCF: linenoiseHistoryLoad (linenoise.c:1325)
==75875== by 0x10CF53: main (qtest.c:1314)
==75875==
==75875== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==75875== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==75875== by 0x1110FC: linenoiseHistoryAdd (linenoise.c:1224)
==75875== by 0x111CCF: linenoiseHistoryLoad (linenoise.c:1325)
==75875== by 0x10CF53: main (qtest.c:1314)
==75875==
```
從錯誤訊息回推得知
* 有 `malloc` 產生的記憶體空間並未釋放
* 原因出在執行 `./qtest` 時，不論是否引入檔案與否皆會引用 `linenoiseHistoryLoad(HISTORY_FILE)` 這行程式碼，其中 `linenoiseHistoryAdd` 會進行 `malloc` 配置記憶體空間
* 然後在 `run_console` 時，有引入檔案的部份會走到下列程式碼中，而 `cmd_select` 並不會透過 `linenoise()` 間接啟動 `atexit(linenoiseAtExit())` 使 `./qtest` 結束時進行記憶體空間的釋放
```c
else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
```
* 解決方法如下，不使用 `.cmd` 檔案進行操作時就不要使用 `linenoiseHistoryLoad` ，所以做了條件式的新增，以及補上使用手動輸入命令時所需要的 `linenoiseHistoryLoad`
```c
...
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
if (!infile_name) {
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
set_verblevel(level);
...
```
```c
...
if (!has_infile) {
linenoiseHistoryLoad(HISTORY_FILE);
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
...
```
:::spoiler 最後的執行結果：
```
$ valgrind -q --leak-check=full ./qtest -f ./traces/trace-01-ops.cmd
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbil]
cmd> ih bear
l = [bear gerbil]
cmd> ih dolphin
l = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil]
cmd> rh bear
Removed bear from queue
l = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
l = []
cmd>
Freeing queue
```
:::
#### 使用 massif 視覺化
```
$ valgrind -q --tool=massif ./qtest -f traces/trace-01-ops.cmd
$ massif-visualizer massif.out.*
```
Sign in with Wallet
Connect another wallet