---
tags: 2022Linux核心實作
---
# 2022q1 Homework1 (lab0)
contributed by < `bochengC` >
### 待辦事項
- [x] `q_new`: 建立新的「空」佇列;
- [x] `q_free`: 釋放佇列所佔用的記憶體;
- [x] `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- [x] `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- [x] `q_remove_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/) 得知實作手法;
### 環境
```
$uname -a
Linux RTX2070s1 5.11.0-49-generic #55-Ubuntu SMP Wed Jan 12 17:36:34 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
$gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1) 10.3.0
Copyright (C) 2020 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: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping: 10
CPU MHz: 3200.000
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown: Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds: Mitigation; Microcode
Vulnerability Tsx async abort: Mitigation; Clear CPU buffers; SMT vulnerable
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d
```
### q_size
嘗試跟著文件做所有的步驟，在 `git commit` 之前要先用 `clang-format -i queue.c` 整理排版，再用 `git commit -a` ，標題的首字需要大寫
### q_new
回傳一個指向 list_head 空間的指標即可
:::spoiler 完整程式碼
```c
struct list_head *q_new()
{
struct list_head *p = malloc(sizeof(struct list_head));
if (!p)
return NULL;
INIT_LIST_HEAD(p);
return p;
}
```
:::
### q_free
1. 要注意除了`list_head` 每個 element 都是 `element_t` 所以要用 `list_head` 與 `container_of` / `list_entry` 回推，原本在 `list_for_each_safe` 中增加了 `if(p)` 的判斷式，但這部分會由 macro 處理，不必多此一舉。
2. 原本只有手動 free `element_t` 本身，會發生 `ERROR: Corruption detected in block with address 0x559b9fa683a0 when attempting to free it ` 的錯誤，很明顯的是一個跟記憶體相關的問題，但是在 free 裡面又沒有其他的問題， 因此檢查 `element_t` 發現， `element_t->value` 包含一整個字串，需要將整個字串 free ，也發現有 `q_release_element` 可以使用。
:::spoiler 完整程式碼
```c
void q_free(struct list_head *l)
{
struct list_head *p, *q;
if(l->next) {
list_for_each_safe (p, q, l) {
list_del(node);
q_release_element(list_entry(node, element_t, list));
}
}
free(l);
}
```
:::
### q_insert_head
如果在 `element_t *p = malloc(sizeof(element_t));` 前面加上 struct 會發生 incomplete type的狀況
~~1. element 是在 `queue.h` 裡，所以可以直接call ~
~2. list_head 在 `queue.h` 的include 所以要用 `struct list_head`~~
`element_t ` 有用 `typedef` 所以能用 `element_t` 。
1. 要複製字串，沒有先做出連續的記憶體空間
2. 做出連續記憶體空間之後，才能利用 `strncpy` 複製字串
原先版本
```c
char *sc = malloc(strlen(s));
strcpy(sc, s);
p->value = sc;
```
這裡在後續處理 `q_free()` 時發現錯誤， `ERROR: Corruption detected in block with address 0x55fb207433a0 when attempting to free it` ，必須將 `char *sc = malloc(strlen(s));` 改成， `char *sc = malloc(strlen(s)+1);` ， `strlen()` 回傳的長度不包含 `\0` 終止符號，所以事實上終止符號被放置在一個不允許的地方，因此在free的時候會報錯！ 又或者是利用 `strdup()` 直接複製整個字串包含終止符號，解決這個問題。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *p = malloc(sizeof(element_t));
if (!p)
return false;
char *sc = malloc(strlen(s)+1);
strcpy(sc, s);
p->value = sc;
list_add(&(p->list), head);
return true;
}
```
後續在 `make test` 的時候又發現，在測試12、13 `test of malloc failure` 的時候都沒辦法拿到完整的分數。經過思考發現有可能發生 `element_t` 正確建立了，但是 `char *sc` 建立失敗的可能，因此加入新的判斷條件，程式碼改進為。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *p = malloc(sizeof(element_t));
if (!p)
return false;
char *sc = malloc(strlen(s)+1);
if (!sc)
return false;
strcpy(sc, s);
p->value = sc;
// p->value = strdup(s);
list_add(&(p->list), head);
free(p);
return true;
}
```
最後的 `free(p)` 是因為 `git commit -a` 的時候會有 ` error: Memory leak: p [memleak]` 的問題才加入，但是 free(p) 的話，會讓程式出現 segamentation fault
:::spoiler
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *p = malloc(sizeof(element_t));
if (!p)
return false;
char *sc = malloc(strlen(s)+1);
if (!sc)
return false;
strcpy(sc, s);
p->value = sc;
// p->value = strdup(s);
list_add(&(p->list), head);
free(p);
return true;
}
```
:::
### q_insert_tail
同上，不多說
:::spoiler 完整程式碼
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *p = malloc(sizeof(element_t));
if (!p)
return false;
char *sc = malloc(strlen(s)+1);
if (!sc){
free(p);
return false;
}
strcpy(sc, s);
p->value = sc;
// p->value = strdup(s);
list_add_tail(&p->list, head);
return true;
}
```
:::
### q_remove_head
:::spoiler 完整程式碼
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *p = container_of(head->next, element_t, list);
if (bufsize) {
strncat(sp, p->value, bufsize - 1);
strncat(sp, "\0", 1);
}
list_del(head->next);
return p;
}
```
:::
### q_delete_mid
:::spoiler
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || head->next == head->prev)
return false;
struct list_head *p1 = head->next, *p2 = head->next;
while (p1 != head && p1->next != head) {
p1 = p1->next->next;
p2 = p2->next;
}
list_del(p2);
element_t *ptr = list_entry(p2, element_t, list);
q_release_element(ptr);
return true;
}
```
:::
### q_delete_dup
這是一個已經被 sort 的 linkedlist
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || head->next == head || head->next == head->prev ||
head->next->next == head->prev)
return false;
struct list_head *p, *q;
// element_t *p_element, *q_element;
char *s = malloc(sizeof(char));
list_for_each_safe (p, q, head) {
element_t *p_element = container_of(p, element_t, list);
element_t *q_element = container_of(q, element_t, list);
if (!strcmp(p_element->value, q_element->value)) {
strcpy(s, p_element->value);
list_del(p);
} else if (!strcmp(s,
p_element->value)) { // strcmp return 0 means equal
list_del(p);
}
}
return true;
}
```
在定義某個東西的同時，順便將值給入，是比較好的做法。
上述的程式碼會有 segmentation fault ，理由是在 `list_for_each_safe` 中，如果 `q_element` 是 NULL 的時候， `q_element->value` 會是一個非法的存取，要改成下
```c
if (!strcmp(s,
p_element->value)) { // strcmp return 0 means equal
list_del(p);
q_release_element(p_element);
} else if (!strcmp(p_element->value, q_element->value)) { // equal 原本把
s = strdup(p_element->value);
list_del(&p_element->list);
q_release_element(p_element);
}
```
### q_swap
1. 要利用 head 指標確認結尾，所以必須要另外創造三個指標，來指出三個位子
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | curr | <next> }"]
b [label="{ <prev> | ptrA | <next> }"];
c [label="{ <prev> | ptrB | <next> }"];
d [shape=box label="....."];
a:next:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:next:c -> d
}
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | curr | <next> }"]
b [label="{ <prev> | ptrA | <next> }", fontcolor=red];
c [label="{ <prev> | ptrB | <next> }"];
d [shape=box label="....."];
a:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:next:c -> d
}
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | curr | <next> }"]
b [label="{ <prev> | ptrA | <next> }", fontcolor=red];
c [label="{ <prev> | ptrB | <next> }"];
d [shape=box label="....."];
a:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:next:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
b:next:c -> d
}
```
::: spoiler 完整程式碼
```c
void q_swap(struct list_head *head)
{
if (!head || head->next == head || list_is_singular(head))
return;
struct list_head *odd = NULL, *even = NULL, *curr = head->next;
// https://leetcode.com/problems/swap-nodes-in-pairs/
while (curr != head && curr->next != head) {
odd = curr;
even = curr->next;
list_move(even, curr->prev);
list_move(odd, even);
curr = curr->next;
}
}
```
:::
### q_reverse
:::spoiler 初始版本
```
void q_reverse(struct list_head *head)
{
if (!head || (head->next == head))
return;
struct list_head *p = head->next, *tmp;
while (p != head) {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = p->prev;
}
tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
:::
:::spoiler API版本
```c
void q_reverse(struct list_head *head)
{
if (!head || (head->next == head))
return;
struct list_head *p = head->next, *tmp;
while (p != head) {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = p->prev;
}
tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
:::
### q_sort
```c
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
// printf("enter merge \n");
struct list_head *head = NULL, **ptr = &head; //, **node;
for (; l1 && l2; ptr = &(*ptr)->next) {
char *l1_ch = list_entry(l1, element_t, list)->value;
char *l2_ch = list_entry(l2, element_t, list)->value;
// printf("l1 is %s l2 is %s\n", l1_ch, l2_ch);
if (strcmp(l1_ch, l2_ch) >= 0) {
// printf("enter l2 %s\n", l2_ch);
*ptr = l2;
l2 = l2->next;
} else {
// printf("enter l1 %s\n", l1_ch);
*ptr = l1;
l1 = l1->next;
}
// *ptr = *node;
// ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
// printf("out merge \n");
return head;
}
// 切開 in this part every head have value
struct list_head *mergesort(struct list_head *head)
{
// printf("enter mergesort \n");
if (!head || !head->next) {
// printf("single node out mergesort \n");
return head;
}
struct list_head *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
// set the left part cut point
slow->prev->next = NULL;
struct list_head *left = mergesort(head);
struct list_head *right = mergesort(slow);
// printf("out mergesort \n");
// struct list_head* new_head = merge(left, right);
// list_for_each(element_t, new_head, list){
// printf("%s \n", element_t->value);
// }
// return new_head
return merge(left, right);
}
/*
* 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)
{
// printf("enter qsort \n");
if (!head || head->next == head || list_is_singular(head)) {
// printf("what \n");
return;
}
// use merge sort I can use 老師的資料
// set the terminated situatino
head->prev->next = NULL;
head->next = mergesort(head->next);
// printf("back qsort \n");
struct list_head *node = head->next;
// element_t* el_t ;
while (node->next != NULL) {
// el_t = list_entry(node, element_t, list);
// printf("node is %s", el_t->value);
node->next->prev = node;
node = node->next;
}
head->next->prev = head; 整
head->prev = node;
node->next = head;
}
```
:::
### 每個 function 都要注意的部分
1. `if (!head || head->next == head)` 要確認 head 不為 NULL 或是 只有單獨 head 節點，但是沒有 element_t 的狀況。
2. 有 `malloc` 那就要有 `free` ， 注意 `strdup()` 背後也使用了 `malloc` 的行為，所以要記得 `free` 。
3. `strcpy ` 是有機會發生問題的函數，因此利用 `strncpy` 處理
### make valgrind 檢查
```
# Test of insert_head and remove_head
==52383== 14 bytes in 1 blocks are still reachable in loss record 1 of 3
==52383== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383== by 0x4A4B3BE: strdup (strdup.c:42)
==52383== by 0x112415: linenoiseHistoryAdd (linenoise.c:1677)
==52383== by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383== by 0x10D810: main (qtest.c:1026)
==52383==
==52383== 122 bytes in 19 blocks are still reachable in loss record 2 of 3
==52383== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383== by 0x4A4B3BE: strdup (strdup.c:42)
==52383== by 0x112389: linenoiseHistoryAdd (linenoise.c:1677)
==52383== by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383== by 0x10D810: main (qtest.c:1026)
==52383==
==52383== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==52383== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383== by 0x1123D5: linenoiseHistoryAdd (linenoise.c:1665)
==52383== by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383== by 0x10D810: main (qtest.c:1026)
==52383==
```
根據圖片上的描述問題出在strdup 裡面，
```c=
if(fp) // 有兩種狀況 1. 有讀取檔案 2. 純粹執行
freeHistory(); // add here ?
```
在 `linenoiseHistoryLoad` 的最後加上這倆行程式碼，會讓一般的 `./qtest ` 出問題，
這個問題的步驟是
1. `./qtest`
2. quit 就會發生 `free(): double free detected in tcache 2 `的問題
因此這應該是個錯誤的解決方式，後來在程式碼中，發現錯誤原因應該是在 `atexit(linenoiseAtExit);` 上
>`int atexit(void (*func)(void));`
>The C library function int atexit(void (*func)(void)) causes the specified function func to be called when the program terminates. You can register your termination function anywhere you like, but it will be called at the time of the program termination.
從 `linenoise` -> `linenoiseRaw` -> `enableRawMode` -> `atexit(linenoiseAtExit);` 讓上述設置在 `linenoiseHistoryLoad` 的 freeHistory(); 發生重複free的狀況。
因此回頭尋找為何原先手動執行的時候不會發生 `history` 沒有被 free() 的狀況，發現以下程式碼。
```c
if (!atexit_registered) { // add this? check the normal version
atexit(linenoiseAtExit);
atexit_registered = 1;
}
```
將這段程式碼新加入到 `linenoiseHistoryLoad` 內，就可以解決問題了。
目前剩下 trace-17-complexity 會發生在 add_cmd add_param 的問題，但是個問題有時候會出現有時候不會出現。
### 將 lib/list_sort.c 合併入 lab0
要求: 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
在 list_sort.c 中有長長一段說明，其中提到了，利用這種二的冪合併方式，可以避免 cache thrashing ，只要 cache 可以容納 (2^k)*3 大小的 list。
> 在聽老師 week4的時候有感受到這部分實作的優勢，因為每次都是往最近對讀取的 sublist/node 排序，所以除非 cache 已經滿了，需要重新從 memory抓資料，才會需要用 cache 的更換
以下舉的例子是在節錄在 list_sort.c 中的程式碼片段執行結果
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
兩個例子分別是 count = 8 跟 count = 9 的狀況，利用這兩個狀況可以比較快的了解這個演算法是如何 sort的
count = 8 = 1000b 時， 此時在 pending list 內共有8個 nodes ， `*tail` 指向 h node ， bit = 1000b ，起始狀態圖如下
```graphviz
// note : e右 s下 w左 n上
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | H | <next> }"]
b [label="{ <prev> | I | <next> }"];
c [label="{ <prev> | J | <next> }"];
d [label="{ <prev> | K | <next> }"];
e [label="{ <prev> | F | <next> }"];
f [label="{ <prev> | G | <next> }"];
g [label="{ <prev> | E | <next> }", fontcolor = red];
h [label="{ <prev> | D(pending) | <next> }", fontcolor = red];
i [label="{ <prev> | C(list) | <next> }"];
j [label="{ <prev> | B | <next> }"];
k [label="{ <prev> | A | <next> }"];
// pending list
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:next:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
e:prev:n -> a:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
e:next:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
g:prev:n -> e:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
h:prev:n -> g:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// list
// i:prev:n -> h:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// i:next:e -> j:prev:c [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, label="prev" ];
i:next:e -> j:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
j:next:e -> k:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
h -> i [ style=invis ];
}
```
在進入 if 之前， `*tail` 指向 h node ，因此進入 if 後， 會是 g,h node進行 merge ，下圖是離開 if 後的結果。
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | H | <next> }"]
b [label="{ <prev> | I | <next> }"];
c [label="{ <prev> | J | <next> }"];
d [label="{ <prev> | K | <next> }"];
e [label="{ <prev> | F | <next> }"];
f [label="{ <prev> | G | <next> }"];
g [label="{ <prev> | E | <next> }", fontcolor = red];
h [label="{ <prev> | D(pending) | <next> }", fontcolor = red];
i [label="{ <prev> | C(list) | <next> }"];
j [label="{ <prev> | B | <next> }"];
k [label="{ <prev> | A | <next> }"];
// pending list
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:next:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
e:prev:n -> a:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
e:next:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
g:prev:n -> e:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
g:next:c -> h:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// list
// i:prev:n -> h:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// i:next:e -> j:prev:c [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, label="prev" ];
i:next:e -> j:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
j:next:e -> k:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
h -> i [ style=invis ];
}
```
count = 9 = 1001b 時， 此時在 pending list 內共有9個 nodes ， `*tail` 指向 i node ， bit = 1000b ，起始狀態圖如下
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | H | <next> }"]
b [label="{ <prev> | I | <next> }"];
c [label="{ <prev> | J | <next> }"];
d [label="{ <prev> | K | <next> }"];
e [label="{ <prev> | F | <next> }"];
f [label="{ <prev> | G | <next> }"];
g [label="{ <prev> | D | <next> }", ];
h [label="{ <prev> | E | <next> }", ];
i [label="{ <prev> | C(pending) | <next> }",fontcolor = red];
j [label="{ <prev> | B(list) | <next> }"];
k [label="{ <prev> | A | <next> }"];
// pending list
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:next:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
e:prev:n -> a:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
e:next:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
g:prev:n -> e:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
g:next:c -> h:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
// list
// i:prev:n -> h:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// i:next:e -> j:prev:c [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, label="prev" ];
i:prev:n -> g:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
j:next:e -> k:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
i -> j [ style=invis ];
}
```
此輪 count = 1001b ，故 bits = 1001b ， `tail = &(*tail)->prev ;` 會執行一次， 此時， `*tail` 指向 G node， 接著會進入 if 之內，將 G,E 兩個 sublist 合併，此輪結束的結果如下圖
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <prev> | H | <next> }"]
b [label="{ <prev> | I | <next> }"];
c [label="{ <prev> | J | <next> }"];
d [label="{ <prev> | K | <next> }"];
e [label="{ <prev> | F | <next> }"];
f [label="{ <prev> | G | <next> }"];
g [label="{ <prev> | E | <next> }", fontcolor = red];
h [label="{ <prev> | D | <next> }", ];
i [label="{ <prev> | C | <next> }"];
j [label="{ <prev> | B(pending) | <next> }",fontcolor = red];
k [label="{ <prev> | A(list) | <next> }"];
// pending list
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:next:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
e:prev:n -> a:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
e:next:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
f:next:c -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
g:next:c -> h:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// list
// i:prev:n -> h:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
// i:next:e -> j:prev:c [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, label="prev" ];
i:prev:n -> e:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
j:prev:n -> i:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
j -> k [ style=invis ];
}
```
可以往後推斷， bits = 1010b 時，會是 I,J node 合併， bits = 1011b 時，才會是 A,E 子串列合併。
在文件中的敘述表示利用這種方式可以降低 cache thrashing 的次數。
#### 排序方式比較，實驗設計
以 .cmd 檔，分別對兩種排序方式進行十萬個 node 的排序測試，為了降低字串長度的差別影響實際的結果，將每個節點的字串長度設定為6(在 qtest.c 144)，利用 `perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles,l1d_pend_miss.pending,L1D_PEND_MISS.PENDING_CYCLES,L1D.REPLACEMENT ./qtest -v 3 -f traces/trace-Rand.cmd`，進行五次測試，並且測量純粹產生十萬個node需要的指令數，扣掉之後再進行分析。
`sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"`
`sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'`
`sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"`
先利用這三個 cmd 准許 perf
:::spoiler about l1D miss
> l1d.replacement
[L1D data line replacements]
l1d_pend_miss.pending
[L1D miss outstandings duration in cycles]
l1d_pend_miss.pending_cycles
[Cycles with L1D load Misses outstanding]
這兩個有什麼差別
:::
以下是三種分別的結果
```
by my sort
119,000,695 cache-misses # 53.881 % of all cache refs ( +- 0.74% ) (57.07%)
220,859,095 cache-references ( +- 0.43% ) (57.18%)
2,675,143,084 instructions # 0.51 insn per cycle ( +- 0.19% ) (71.46%)
5,263,504,595 cycles ( +- 0.22% ) (71.48%)
4,641,818,427 l1d_pend_miss.pending ( +- 0.50% ) (71.54%)
3,521,064,443 L1D_PEND_MISS.PENDING_CYCLES ( +- 0.46% ) (71.45%)
84,211,551 L1D.REPLACEMENT ( +- 0.24% ) (71.28%)
1.15522 +- 0.00383 seconds time elapsed ( +- 0.33% )
by linux list_sort
90,458,525 cache-misses # 56.776 % of all cache refs ( +- 2.67% ) (56.74%)
159,324,058 cache-references ( +- 2.03% ) (56.99%)
2,652,501,582 instructions # 0.56 insn per cycle ( +- 0.51% ) (71.44%)
4,729,713,609 cycles ( +- 0.36% ) (71.60%)
4,611,768,094 l1d_pend_miss.pending ( +- 2.87% ) (71.73%)
3,259,718,213 L1D_PEND_MISS.PENDING_CYCLES ( +- 0.87% ) (71.66%)
65,302,933 L1D.REPLACEMENT ( +- 1.21% ) (71.27%)
1.04382 +- 0.00410 seconds time elapsed ( +- 0.39% )
by rand
16,454,796 cache-misses # 85.709 % of all cache refs ( +- 0.17% ) (56.00%)
19,198,404 cache-references ( +- 0.81% ) (56.06%)
1,743,048,580 instructions # 1.57 insn per cycle ( +- 0.29% ) (70.73%)
1,111,946,653 cycles ( +- 0.73% ) (71.98%)
368,212,084 l1d_pend_miss.pending ( +- 0.12% ) (73.23%)
366,997,770 L1D_PEND_MISS.PENDING_CYCLES ( +- 0.21% ) (72.01%)
8,174,014 L1D.REPLACEMENT ( +- 0.17% ) (70.71%)
0.24576 +- 0.00230 seconds time elapsed ( +- 0.93% )
將兩個排序扣掉製作 nodes 的時間與步驟
my sort
102545899 cache-misses
201660691 cache-references
932094504 instructions
4151557942 cycles
4273606343 l1d_pend_miss.pending
3154066673 L1D_PEND_MISS.PENDING_CYCLES
76037537 L1D.REPLACEMENT
0.90946 seconds
linux list_sort
74003729 cache-misses
140125654 cache-references
909453002 instructions
3617766956 cycles
4243556010 l1d_pend_miss.pending
2892720443 L1D_PEND_MISS.PENDING_CYCLES
57128919 L1D.REPLACEMENT
0.79806 seconds
```
由上方的分析可以發現，在兩種不同的 sort的方式下， list_sort.c 的演算法是一個 cache-friendly 的演算法，增加了比較的次數，但是可以降低 cache-miss的次數，我自己實現的 q_sort 是基於 merge_sort 的方式建立，理論上可以達到最佳的 O(nlogn) 的時間複雜度，但是在實際的實驗中可以發現在 L1Dcache-miss 上有約莫三千萬次的差距，因為大量的 cache-miss 讓理論上最快的 O(nlogn) 的演算法反而比 cache-friendly 的演算法慢了一成，十分值得引以為戒。
### 增加 shuffle cmd
>在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
這個演算法簡單來說就是在還沒有亂序過的子序列中挑出一個，放到後面的序列中。
:::spoiler
```c=
void q_shuffle(struct list_head* head){
if (!head || head->next == head || list_is_singular(head))
return ;
int cnt = 0 ;
struct list_head* ptr=head->next;
while(ptr != head){
cnt++;
ptr = ptr->next;
}
int rand_num = 0 ;
while( cnt !=1){
ptr = head->next ; // if rand_num = 0 means remove the first node
rand_num = rand();
rand_num = rand_num % cnt ;
while(rand_num){
ptr = ptr->next;
rand_num--;
}
list_move_tail(ptr, head);
cnt--;
}
}
```
:::
### 加入 tiny-web-server
在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
:::warning
整份 tiny-web-server 的code直接抄過來會有滿滿的問題，審慎使用
:::
整套功能簡單來說就是開啟一個web server 之後，會持續接受資訊，如果有人給出指令，會執行指令
上述想法， 先做出list_sortk的 cmd 然後再看原本的cmd的呼叫方式依樣葫蘆做出一樣的呼叫方式，最後再研究shuffle 與 web 有 time 可以使用 可以簡單比較效能
1. 先把整份 tiny-web 的code 全部放到 linenoise去
2. 依照提示修改 process
3. 在 http_request 中加入 `char* function_name` 成員
5. 修改 run_console
6. 在 `linenoiseEdit` 加入 non-blocking 的程式碼 在 linenoise.h 加上 `extern int listenfd` ， 因為這個變數在 console.c 跟 linenoise.c 裡面都會用到
>Q : non-blocking 的修改要放在哪裡? 一開始放在 linenoiseEdit， 後來改到 do_web 函數。
>```c
>int flags = fcntl(listenfd, F_GETFL);
>fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
>```
>```c
>static bool do_web(int argc, char *argv[])
>{
> listenfd = open_listenfd(9999);
> noise = false;
> // add for non-blocking
> int flags = fcntl(listenfd, F_GETFL);
> fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
> return true;
>}
>```
6. 把 socket_init 換成 open_listenfd(9999 )
7. 原本在 handle_request 的部分 直接把 parse_request 拿來用，但是會發生 seg fault ，研究了一下發現應該是 read 會有個讀取的指標往後移動， 因為是同樣的 fd 所以再次 read 的時候會出現問題 ，所以最後決定在 `parse_request` 函式把 `req->function_name` 建立好
8. 加入以下程式碼，讓 LOG可以出現
```c
#ifndef NO_LOG_ACCESS
#define LOG_ACCESS
#endif
```
9. `log_access` 的 `req->filename` 改成 `req->function_name`
10. 解決問題: `style: Redundant condition: If 'EXPR', the comparison 'EXPR != '\0'' is always true. [redundantCondition] while (*p && (*p) != '\0') { // 整理 function name`
```
linenoise.c:1215:15: style: Redundant condition: If 'EXPR', the comparison 'EXPR != '\0'' is always true. [redundantCondition]
while (*p && (*p) != '\0') { // 整理 function name
^
linenoise.c:1163:13: portability: %lu in format string (no. 2) requires 'unsigned long *' but the argument type is 'size_t * {aka unsigned long *}'. [invalidScanfArgType_int]
sscanf(buf, "Range: bytes=%lu-%lu", &req->offset, &req->end);
^
linenoise.c:1158:5: warning: sscanf() without field width limits can crash with huge input data. [invalidscanf]
sscanf(buf, "%s %s", method, uri); /* version is not cared */
^
改成 這裡為什麼不是 1024 ?
sscanf(buf, "%1023s %1023s", method, uri); /* version is not cared */
```
#### 其他問題
建好 web server 之後，會遇到另外兩個個問題
問題1，`./qtest` 輸出狀態會變成以下的模式，會有嚴重的echo 影響，必須手動利用 `option echo 0` 關閉。
```
cmd> new
cmd> new
l = []
cmd> ih a
cmd> ih a
l = [a]
```
這個部分的問題是明明都是執行 `./qtest` 但是在還沒有加入 web-server 之前都不用手動關閉 `echo` ，但是加入 web-server 之後，就必須要手動關閉 `echo` 了，關鍵在 lab0 的修改中改掉了 `if (has_infile)` 的部分
```diff=
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);
- }
```
在 `readline()` 中，有以下的程式碼片段會多輸出一次 `>cmd` 必須使用 `options echo 0 `手動關閉功能。
```c
if (echo) {
report_noreturn(1, prompt); // because echo > 0 ? so print?
report_noreturn(1, linebuf);
}
```
問題二: tab 鍵 自動完成的效果會消失，這部分功能的實現在 `linenoiseEdit` 中， `linenoise()->linenoiseRaw()->linenoiseEdit()`
```c
if (c == 9 && completionCallback != NULL) {
c = completeLine(&l);
/* Return on errors */
if (c < 0)
return l.len;
/* Read next character when 0 */
if (c == 0)
continue;
}
```
在下列的問題與解決，讓沒有開 web server的狀態，能夠正常的補齊。但是如何在 web_server 的狀態下，讓自動補齊可以使用？
問題: 為何會直接卡在 `accept request, fd is -1, pid is 7673`?
問題分析：
```c=
if (!has_infile) {
char *cmdline;
while (noise && (cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(
HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
if (!noise) {
while (!cmd_done()) {
cmd_select(0, NULL, NULL, NULL, NULL);
}
}
} else {
while (!cmd_done()) {
cmd_select(0, NULL, NULL, NULL, NULL);
}
}
```
在上述的程式碼中，如果 `noise ` 為1的狀況下，會依序進入 `linenoise()` `linenoiseRaw()` `linenoiseEdit` function，根據 web-server 的修改步驟，此時 `linenoiseEdit` 中已經有以下的程式碼
```c=
while (1) {
char c;
int nread;
char seq[3];
fd_set set;
FD_ZERO(&set);
FD_SET(listenfd, &set);
FD_SET(stdin_fd, &set);
int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof clientaddr;
int connfd;
switch (rv) {
case -1:
perror("select"); /* an error occurred */
continue;
case 0:
printf("timeout occurred\n"); /* a timeout occurred */
continue;
default:
if (FD_ISSET(listenfd, &set)) {
connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
char *p = process(connfd, &clientaddr);
strncpy(buf, p, strlen(p) + 1);
close(connfd);
free(p);
return strlen(p);
} else if (FD_ISSET(stdin_fd, &set)) {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
}
break;
}
}
```
在第八跟第九行的 `FD_SET()` macro 將 `stdin_fd` 與 `listenfd` 加入 `set` 之中，代表在沒有任何錯誤的狀態下，在 switch 中，必然會進入 23行的 default，則必然會進入第一個 if 但此時 web 還沒有被開啟，也不會有 request 進入該程式，因此會在 `process()` 內的 `parse_request()` 內的 while 迴圈持續執行，而不會跳出
```c
while (buf[0] != '\n' && buf[1] != '\n') { /* \n || \r\n */
rio_readlineb(&rio, buf, MAXLINE);
if (buf[0] == 'R' && buf[1] == 'a' && buf[2] == 'n') {
sscanf(buf, "Range: bytes=%lu-%lu", &req->offset,
(unsigned long *) (&req->end));
// Range: [start, end]
if (req->end != 0) {
req->end++;
}
}
}
```
如果以 24行的作法的話會讓程式卡在 `cmd> accept request, fd is -1, pid is 5973` 無法進行近一步的處理。
解決： 將一開始在 `linenoiseEdit` 的修改取消就可以了！
### 未完成
* 除了修改程式，也要編輯「[作業區](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" 過程中的記憶體使用量，需要設計對應的實驗
`Massif` 是 valgrind 其中一個東西
[massif的使用參考](https://hackmd.io/@ChialiangKuo/linux2021-homework1)
:::warning
massif-visualizer 不知道怎麼處理遇到的問題，先擱置
:::
### 解釋 select
解釋 [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)
`int select(int nfds, fd_set *restrict readfds,
fd_set *restrict writefds, fd_set *restrict exceptfds,
struct timeval *restrict timeout);`
cmd_select ,linenoiseEdit 都有 select
與select 主要相關的行為有以下幾個
> FD_ZERO(): This macro clears (removes all file descriptors from) set. It should be employed as the first step in initializing a file descriptor set.
FD_SET(): This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.
FD_CLR(): This macro removes the file descriptor fd from set. Removing a file descriptor that is not present in the set is a no-op, and does not produce an error.
FD_ISSET(): select() modifies the contents of the sets according to the rules described below. After calling select(), the FD_ISSET() macro can be used to test if a file descriptor is still present in a set. FD_ISSET() returns nonzero if the file descriptor fd is present in set, and zero if itis not.
簡而言之， `FD_ZERO()` 清空整個 fd set 會用在初始化， `FD_SET()` 將 fd 加入到 fd set 中， `FD_CLR()` 移除某個 fd ， `FD_ISSET()` 確認某個 fd 是否在 fd set 中。
* 研讀論文〈[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
>WARNING: select() can monitor only file descriptors numbers that are less than FD_SETSIZE (1024)—an unreasonably low limit for many modern applications—and this limitation will not change. All modern applications should instead use poll(2) or epoll(7), which do not suffer this limitation.
### 提供的內建函數
`INIT_LIST_HEAD`
`list_add`
`list_add_tail`
`list_del`
`list_del_init`
`list_empty`
`list_is_singular`
`list_splice` - 把 Alist 加到 Blist 的前面
`list_splice_tail`
`list_splice_init`
`list_cut_position`
`list_move` - move a list node to the beginning of the list
`list_move_tail()` - Move a list node to the end of the list
`list_entry()` - Calculate address of entry that contains list node
`list_first/last_entry()` - get first/last entry of the list
`list_for_each` - iterate over list nodes
用` make check `檢查 `make test` 評分
### 後記
在用 make test 的時候看到可以顯示目前運行多少，就去查了一下 qtest 的原始碼看到神奇的一行
`printf("\033[A\033[2K");`
便去查了一下到底這行在幹嘛
[By this](https://wiki.bash-hackers.org/scripting/terminalcodes)可以知道他是ansi的控制碼，可以操控游標的行為。
再從這個網站拿到方塊格子的輸入方式 [這個網站](https://tw.piliapp.com/symbol/square/) ，拼湊出一個進度條
```c
#include <iostream>
#include <unistd.h>
using namespace std;
int main()
{
cout<<"Hello World" << endl;
int j , cnt = 0;
bool status = true;
for(int i = 1 ; i < 100000000000 ; i++){
//printf("\033[A\033[2K");
cnt =0;
if(status){
j = i%20;
}else{
j = 20 - i%20;
}
printf("progress:[");
while( cnt < j){
//usleep(20);
cnt++;
//printf("*");
printf("▉");
printf("\033[32m");
//printf(" \033[34m");
}
int spare_cnt = 20-j ;
while( spare_cnt > 0 ){
printf(" ");
spare_cnt--;
}
printf("] %d / %d ％", j*5 , 100);
printf("\n");
if( i%40 == 39){
status = true;
}else if( i%20 ==19){
status = false;
}
printf("\033[A\033[2K");
usleep(200000);
//printf("meas: %7.2lf M \n ", (i / 1e6));
}
return 0;
}
```
```
char *bar = (char *)malloc(sizeof(char) * (len + 1));
printf("progress:[%s]%d%%\r", bar+len-i, i+1);
```
[%s] 可以直接輸出某段string
`gcc -o list_sort -g list_sort.c -I/usr/src/linux-headers-5.4.0-99-generic/include` -I 是加入including path
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
head [label="{ {<f2>head|{prev| next}}} }",fontcolor="red" ];
a [label="{ { | {< f0 >prev| next}| val} }"];
b [label="{ { |{< f0 >prev| next}| val} }"];
c [label="{ { |{<f0>prev| next}| val} }"];
d [label="{ { |{<f0>prev|<f1> next}| val} }"];
head:e -> a:f0:sw [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
head:sw -> d:f1:se [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
a:e -> b:f0:sw[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:e -> c:f0:sw[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:e -> d:f0:sw[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
d:e -> head:f2:s[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
a:w -> head:f0:next [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
b:f0:w -> a:f0:next [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:f0:w -> b:f0:next [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
d:f0:w -> c:f0:next [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
}
```
// note : e右 s下 w左 n上
a:next:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:next:c -> d
Sign in with Wallet
Connect another wallet