---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [`kuihao`](https://github.com/kuihao) >
## 實驗環境
* gcc version
```shell
$ gcc --version
```
輸出:
```shell
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
```
* lscpu
```shell
$ lscpu
```
輸出:
```shell
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
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: Not affected
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 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 avx2 smep bmi2 erms invpcid 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
```
:::warning
輸出呢？
:notes: jserv
:::
## 作業要求:penguin:
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0#K01-lab0)
- [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] [`queue.[ch]` 需修改的項目](https://hackmd.io/@sysprog/linux2022-lab0#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E9%9B%BB%E8%85%A6%E7%B3%BB%E7%B5%B1%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD):
- [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
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
- [x] q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- [x] q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;
- [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)，讓程式碼更精簡且有效
- [ ] 研讀 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)
- [x] 除了修改程式，也要編輯「[作業區](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
* 截止日期：
* Mar 1, 2022 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高
## ==開發過程==
### 開發準備
1. 將 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) fork 至自己的 GitHub 帳號下並 pull 至本地端
2. **開啟 [GitHub Actions](https://github.com/features/actions) 功能**
3. 確定 Cppcheck 套件版本至少 `v1.90`，執行方語法檢視目前版本：
```shell
$ cppcheck --version
```
顯示結果符合要求
```shell
Cppcheck 1.90
```
:warning: **If your Cppcheck version is lower than 1.90**: [Follow here! (the ordered list $5^{\circ}$)](https://hackmd.io/@sysprog/linux2022-lab0#-%E9%96%8B%E7%99%BC%E7%92%B0%E5%A2%83%E8%A8%AD%E5%AE%9A)
4. 閱讀文件 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
* **關於 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)**
> list (Circular doubly-linked list) 的關鍵概念是，將結構體 list_head 嵌入到所需的結構體中，再藉由稍後會提及的 container_of 巨集得知 list 個別節點的地址。示意如下圖:
> 
> ([原文: "你所不知道的 C 語言: linked list 和非連續記憶體"](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC))
> [name=Jim Huang] [time=2018] <!--[color=#907bf7]-->
* **作業所使用的結構**<br>由上述得知，**Linux Kernel 的 linked-list 結構稱為 list_head**，list_head 專職於指向其他非連續記憶體並且有另一個專有名詞稱作 **head**，其存放著 list_head 型別的位址，其功用是找到整條 linked-list。
* head 的程式碼與示意圖
```clike
list_head *head;
```
```graphviz
digraph structs {
layout=neato;
node [shape=Mrecord, color=turquoise];
list_head [label="<p> prev|<n> next", xlabel="list_head *head"];
}
```
此外，作業中用來封裝 list_head 的節點結構稱為 **element_t**，由下方 queue.h 中的程式碼可知 element_t 的 **value 也是一個指標**，用來指向另一個實際存放字串的記憶體空間。==由此可見這就是 Linux Kernel 管理非連續記憶體的方式：==
:::info
1. 透過指標存取非連續記憶體的資料 (char \*value）
2. 透過封裝著 list_head 的結構體 （e.g. element_t）來管理眾多的指標 (char \*value)
:::
我認為這樣的**程式設計** (OS: 此時才驚覺原來這才是程式設計) 正是為了方便協作及開發大型的程式專案。各項資料結構的用途專一、各司其職，char \*value 專注於資料位址的存取、list_head 專注於串接各個 element_t，element_t 專注於管理多個指標。
* element_t 的程式碼與示意圖
```c
/* Linked list element */
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
```graphviz
digraph structs {
layout=neato;
node [shape=Mrecord, color=turquoise];
element_t [label="{<a0> value|{list_head}}", xlabel="element_t"];
}
```
* 本作業欲開發的 Linux Kernel 風格的 queue 的示意圖：
```graphviz
digraph structs_listhead {
layout=neato;
# digraph: diagram graph 圖表型別 (內部可定義多種結構及其相互關係)/
# structs: 自定義名稱，此 digraph 的圖表名稱
node [shape=Mrecord, color=turquoise];
# node: 節點型別，對此 digraph 的節點的形狀進行定義
# shape=record: 定義 shape 為 record 形狀
# record-base node 可以定義各種標籤，很適合描述資料結構
# shape=Mrecord: 形狀的角變圓滑 (rounded corners)
# color: 邊框顏色
# 範例:
# xxx []: xxx 繪製一顆 xxx 節點，可於 [] 對各個節點進行定義
# label: 節點內文字
# xlabel: External label
# <> portname 表示特定文字的變數，其後跟著欲顯示文字
## 定義 node
list_head [pos="1,2!" label="<p> prev|<n> next", xlabel="list_head *head"];
element_t1 [pos="2,1!" label="{<v> value|{<p> prev|<n> next}}", xlabel="element_t"];
element_t2 [pos="1,0!" label="{<v> value|{<n> next|<p> prev}}", xlabel="element_t"];
element_t3 [pos="0,1!" label="{<v> value|{<p> prev|<n> next}}", xlabel="element_t"];
## 定義關係
list_head:n -> element_t1 [len=2] #len: neato only
element_t1:n -> element_t2 [len=2]
#{rank=same element_t1 element_t3}
element_t2:n -> element_t3 [len=2]
element_t3:n -> list_head [len=2]
list_head:p -> element_t3
element_t3:p -> element_t2
element_t2:p -> element_t1
element_t1:p -> list_head
# node [shape=plaintext];
# shape=plaintext 純文字
# {rank=same/source/min node1 -> node2}
}
```
<!--
```graphviz
graph {
B -- A [taillabel = "tail"]
}
```
-->
註: 上述示意圖可使用 [`graphviz playground (線上繪圖編輯器)`](http://magjac.com/graphviz-visual-editor/) 協助繪製
* list.h Function 功能簡記
| Function | Description |
| ---------------- | --------------------------- |
| INIT_LIST_HEAD() | 產生一個指向自己的 Head_ptr |
| list_add | 於 head 向前插入一個新 node <br> 可用於實作 Stacks (like liunx kernel api document descriped, ["This is good for implementing stacks."](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)) |
| list_add_tail | 於 head 向後插入一個新 node <br> 可用於實作 Queues (like liunx kernel api document descriped, ["This is useful for implementing queues."](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)) |
| list_del | 將其他指向此 node 的鍵斷開，並重新相連時跳過此 node |
| list_del_init | 此 node 不但被斷鍵 (list_del) 同時也將本身的鍵初始化 |
| list_empty | 向前為空：next 指向 head |
| list_is_singular | next, prev 指向 head |
| list_splice | head 向前插入一條新的 linked list |
| list_splice_tail | head 向後插入一條新的 linked list (方向維持正確，舊鏈的尾巴接新鏈的尾巴) |
| list_splice_init | 執行 list_splice() 並順便把新鏈的 head 給初始化 (變成空鏈) |
| list_splice_tail_init | 執行 list_splice_tail() 並順便把新鏈的 head 給初始化 (變成空鏈) |
| list_cut_position | 將一個環切成兩個環 |
| list_move | 將目標 Node 移動至 Head->next |
| list_move_tail | 將目標 Node 移動至 Head->prev |
* Entry
* Such an container object is called entry.
* [Linked Lists](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/linked%20lists.html)
* [Stacks and Queues](https://www.andrew.cmu.edu/course/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html)
* list_cut_position() 說明
將一個環切成兩個環，並指派給新的 head (head_to)
````clike=
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
````
初始狀態
```graphviz
digraph structs {
layout=neato; #繪圖引擎
graph [rankdir="TB"]; # 圖設定 splines = ortho
node[shape=record] #組合式節點
head_from [pos="0.5,3!" color=orangered label="{<listnode>head_from}"]
head_from_next [pos="2,2!" label="{<listnode>head_from_next}"]
node_split [pos="0.7,0!" color=hotpink label="{<listnode>node}"]
node_next [pos="-0.5,1!" label="{<listnode>node_next}"]
Nameless1 [pos="2,1!" label="{<listnode>Nameless1}"]
Nameless2 [pos="-0.5,2!" label="{<listnode>Nameless2}"]
head_to [pos="2.5,3!" color=navy label="{<listnode> head_to}"]
node[shape=plaintext] #無匡節點
head_from_first [pos="4,2!" label="head_from_first"]
# struct list_head *head_from_first
head_from_first -> head_from_next;
# 順時針 (next)
head_from -> head_from_next [label="next" color=cornflowerblue];
head_from_next -> Nameless1 [label="next"];
node_split -> node_next [label="next" color=cornflowerblue];
Nameless1 -> node_split [label="next" constraint=false];
node_next -> Nameless2 [label="next"];
Nameless2 -> head_from [label="next"];
# 逆時針 (prev)
head_from -> Nameless2 [label="prev"];
Nameless2 -> node_next [label="prev"];
node_next -> node_split [label="prev" constraint=false color=cornflowerblue];
node_split -> Nameless1 [label="prev"];
Nameless1 -> head_from_next [label="prev"];
head_from_next -> head_from [label="prev" color=cornflowerblue];
}
```
---
程式碼第 15、16 行
```graphviz
digraph structs {
layout=neato; #fdp #繪圖引擎
node[shape=record] #組合式節點
head_from [pos="0,2!" color=orangered label="{<listnode>head_from}"]
head_from_next [pos="1,1!" label="{<listnode>head_from_next}"]
node_split [pos="0,0!" color=hotpink label="{<listnode>node}"]
node_next [pos="-1.5,0!" label="{<listnode>node_next}"]
Nameless1 [pos="1.5,0!" label="{<listnode>Nameless1}"]
Nameless2 [pos="-2,1.5!" label="{<listnode>Nameless2}"]
head_to [pos="2,2!" color=navy label="{<listnode> head_to}"]
node[shape=plaintext] #無匡節點
head_from_first [pos="3,1!" label="head_from_first"]
# struct list_head *head_from_first
head_from_first -> head_from_next;
# 順時針 (next)
head_from -> node_next [label="next" constraint=false color=red]; # constraint=false dir=both arrowsize=0.5
head_from_next -> Nameless1 [label="next"];
node_split -> node_next [label="next" color=cornflowerblue];
Nameless1 -> node_split [label="next"];
node_next -> Nameless2 [label="next"];
Nameless2 -> head_from [label="next"];
# 逆時針 (prev)
head_from -> Nameless2 [label="prev"];
Nameless2 -> node_next [label="prev"];
node_next -> head_from [label="prev" color=red];
node_split -> Nameless1 [label="prev"];
Nameless1 -> head_from_next [label="prev"];
head_from_next -> head_from [color=cornflowerblue label="prev"];
}
```
---
程式碼第 18 至 21 行
```graphviz
digraph structs {
layout=neato; #繪圖引擎
graph [rankdir="TB"]; # 圖設定 splines = ortho
node[shape=record]; #組合式節點
head_from [pos="1,3!" color=orangered label="{<listnode>head_from}"];
head_from_next [pos="2.5,2!" label="{<listnode>head_from_next}"];
node_split [pos="4.5,2!" color=hotpink label="{<listnode>node}"];
node_next [pos="1.5,1!" label="{<listnode>node_next}"];
Nameless1 [pos="4,1!" label="{<listnode>Nameless1}"];
Nameless2 [pos="0,2!" label="{<listnode>Nameless2}"];
head_to [pos="3.5,3!" color=navy label="{<listnode> head_to}"];
node[shape=plaintext] #無匡節點
head_from_first [pos="2.3,3!" label="head_from_first"];
# struct list_head *head_from_first
head_from_first -> head_from_next;
# 順時針 (next)
head_to -> head_from_next [label="next" constraint=false color=blue];
head_from -> node_next [label="next"];
head_from_next -> Nameless1 [label="next"];
node_split -> head_to [label="next" color=red];
Nameless1 -> node_split [label="next"];
node_next -> Nameless2 [label="next"];
Nameless2 -> head_from [label="next"];
# 逆時針 (prev)
head_to -> node_split [label="prev" color=blue];
head_from -> Nameless2 [label="prev"];
Nameless2 -> node_next [label="prev"];
node_next -> head_from [label="prev"];
node_split -> Nameless1 [label="prev"];
Nameless1 -> head_from_next [label="prev"];
head_from_next -> head_to [label="prev" color=red];
}
```
* container_of
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* Parameters 說明:
* ptr: member 的位址
* type: container 的型別
* member: member 的名稱
* 演算法簡述:
先利用 container 的型別與 member 的名稱，得到 container 與 member 之間的 offset。
```c
offsetof(type, member);
```
再透過 member 的位址減去 offset，得到 container 的位址。
* [參考](https://radek.io/2012/11/10/magical-container_of-macro/)
### q_new
:::spoiler {state="open"} (程式碼修改紀錄)
```clike
/* old version */
struct list_head *q_new()
{
/*read and write head of queue*/
element_t *rw_head = malloc(sizeof(element_t));
if (!rw_head) {
return NULL;
}
// struct list_head **indirect = &(rw_head->list;
INIT_LIST_HEAD(&(rw_head->list));
return &(rw_head->list);
}
```
git commit -a 時會被偵測出 memory leak 問題，原因[ 2022 年系統軟體系列課程討論區: commit 的時候出現 memory leak](https://www.facebook.com/groups/system.software2022/posts/1982813305233403) ，並學習使用 valgrind 動態檢測。
:::
後來參考同學們的實作方式才發現我當初誤會 head 的意義，head 不必實作成 element_t，只需生成 list_head (*) 指標作為新生成的空 Queue。
```clike
/* new version */
struct list_head *q_new()
{
struct list_head *q_head = malloc(sizeof(struct list_head));
if (q_head) {
INIT_LIST_HEAD(q_head);
}
return q_head;
}
```
* 配置一個 list_head 的實際空間，並將 q_head ptr 指向該實際空間。
```graphviz
digraph {
layout=neato;
node [shape=Mrecord, color=turquoise];
list_head [pos="" label="<p> prev|<n> next"];
node[shape=plaintext]; #無匡節點
q_head [pos="0,1" label="q_head"];
q_head -> list_head;
}
```
### q_free
:::spoiler {state="open"} code edition history
```clike=
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
struct list_head **indirect = &l;
/* Traverse will stop if the next ptr point to head itself */
while ((*indirect)->next != l) {
indirect = &(*indirect)->next;
free(list_entry((*indirect)->prev, element_t, list)->value);
free(list_entry((*indirect)->prev, element_t, list));
}
free(l);
return;
}
```
Indirect pointer 風格的實作方式，每次先判斷 next pointer 是否指向 q_head ($l$)，若否，表示還有 node 可以 free，先將 indirect pointer 指向下一個 node 的 next pointer，並將前一顆 node 釋放掉；反之，將 q_head 釋放。
**然而，此寫法再執行時會指向並釋放 Null Address，主要問題發生在第 7 至 9 行，凸顯出我這個寫法不適合使用 indirect pointer。第 7 行，indirect 先指向 head 的 next 指標的位址，但並非直接指向 next node 的位址，當第 9 行釋放 head 的記憶體位置，便會連帶 head 的 next 指標一起釋放，因此 indirect 就指向非法記憶體位址。並且另一個問題是通常 head 所指的位置一開始不應該被釋放掉，這會導致演算法設計上不易追蹤 queue 的所在位置。** 後來仔細研讀 list.h 發現 list_for_each_entry_safe，可以預先存取下下顆 node 的位址，如此一來即使釋放掉下顆 node，也能將指標指向下下顆位址。
:::
```clike
void q_free(struct list_head *l)
{
if (!l) {
return;
}
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
q_release_element(entry);
}
free(l);
}
```
### q_insert_head
```clike
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
INIT_LIST_HEAD(&new_node->list);
new_node->value = strdup(s);
if (!new_node->value) {
free(new_node);
return false;
}
list_add(&new_node->list, head);
return true;
}
```
### q_insert_tail
```clike
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
INIT_LIST_HEAD(&new_node->list);
new_node->value = strdup(s);
if (!new_node->value) {
free(new_node);
return false;
}
list_add_tail(&new_node->list, head);
return true;
}
```
### q_remove_head
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *node = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp && bufsize) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return node;
}
```
### q_remove_tail
```clike
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
/* Ref. https://hackmd.io/@blueskyson/linux2022-lab0 */
if (!head || list_empty(head)) {
return NULL;
}
element_t *node = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (sp && bufsize) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return node;
}
```
### q_release_element
```clike
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
```clike
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;
}
```
* 思考改進方式:
也許能透過修改 queue 節點的 struct，或另外準備一個儲存空間專門存放 queue 的節點數量，並於生成、新增、刪除時都順便修改該數值，q_size 函式就能改為直接讀取該儲存值以提升效能。
### q_delete_mid
```clike
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (head->next == NULL) {
return false;
} else {
struct list_head *current = head->next;
int size = q_size(head);
for (int i = 0; i < size / 2; i++) {
current = current->next;
}
list_del(current);
free(list_entry(current, element_t, list)->value);
free(list_entry(current, element_t, list));
return true;
}
}
```
### q_delete_dup
核心想法：設置一個回收桶存放暫存的副本，最後再一次清空回收桶。
1. 利用指向 head->next 的 inderect pointer (pointer's poniter) 來處理 node 的移動或釋放。
2. 每次走訪都會檢視 head->next 與 head->next->next
3. 當發現 duplicates (副本) 發生，若 duplicates 的字串是第一次出現，則將第一次出現的副本先放入回收桶，後續副本與路圾桶內的 node 比較；若 duplicate 已出現於回收桶，就直接將 duplicate 釋放
5. 最後清空垃圾桶
```clike
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head) {
return false;
}
if (list_empty(head) || list_is_singular(head) ||
head->prev == head->next) {
return true;
}
/* 指向「指向當前 Node 的指標」的指標 */
struct list_head **inderect = &head->next;
/* 一個環狀垃圾桶 */
struct list_head *GarbageCan = q_new();
INIT_LIST_HEAD(GarbageCan);
for (; *inderect != head;) { // && (*inderect)->next!=head
char *first_node_str = list_entry(*inderect, element_t, list)->value;
char *second_node_str =
list_entry((*inderect)->next, element_t, list)->value;
/* 垃圾桶最上層將存放最新的副本，Node 優先與垃圾桶比對 */
if ((GarbageCan->next != GarbageCan) &&
(strcmp(list_entry(GarbageCan->next, element_t, list)->value,
first_node_str) == 0)) {
struct list_head *directly_recycle = *inderect;
list_del(directly_recycle);
q_release_element(list_entry(directly_recycle, element_t, list));
} else {
/* 垃圾桶內找不到才跟下一個 Node 比對 */
if (!strcmp(first_node_str, second_node_str)) {
struct list_head *goto_GarbageCan = *inderect;
struct list_head *directly_recycle = (*inderect)->next;
list_del(goto_GarbageCan);
list_add(goto_GarbageCan, GarbageCan);
list_del(directly_recycle);
q_release_element(
list_entry(directly_recycle, element_t, list));
} else
inderect = &(*inderect)->next;
}
}
q_free(GarbageCan); // 清空垃圾桶
return true;
}
```
### q_swap
```clike
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 *current = head;
for (; current->next != head && current->next->next != head;
current = current->next->next) {
list_move(current->next->next, current);
}
}
```
### q_reverse
```clike
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head) ||
head->next == head->prev)
return;
// [1]-> [2]-> [3]-> [4]
struct list_head *current = head;
do {
struct list_head *tmp = current->next;
current->next = current->prev;
current->prev = tmp;
current = current->next;
} while (current != head);
}
```
### q_sort
參考 [「你所不知道的 C 語言: linked list 和非連續記憶體」的 indirect pointer 版本 mergeTwoLists、Mergesort_list](https://hackmd.io/@sysprog/c-linked-list)
```clike
struct list_head *Merge2Lists(struct list_head *list1, struct list_head *list2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; list1 && list2; *node = (*node)->next) {
node =
signbit((float) strcmp(list_entry(list1, element_t, list)->value,
list_entry(list2, element_t, list)->value))
? &list1
: &list2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) list1 | (uintptr_t) list2);
return head;
}
```
```clike
struct list_head *Mergesort_list(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = Mergesort_list(head), *right = Mergesort_list(mid);
return Merge2Lists(left, right);
}
```
如何運用原本用於普通非環狀 linked list 的 Merge sort?
```clike
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = Mergesort_list(head->next);
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next) {
ptr->next->prev = ptr;
}
ptr->next = head;
head->prev = ptr;
}
```
* 先將 linux kernel 的`環狀 list` 從 tail 切開 (head->prev->next = NULL) 變成非環狀 linked list，套用 Mergesort_list()，排序完成後再將尾端上鏈並順時針將每個 node 的 prev pointer 重新上鏈
## 關於 Linux 的其他收穫
### gdb
* [GNU debugger 文件](https://sourceware.org/gdb/current/onlinedocs/gdb/index.html#SEC_Contents)
* **使用 gdb 開啟執行檔之後，務必記得下斷點及執行的命令**。若未下斷點 (breakpoints) 及未使用 *run* 命令，就直接使用 *print* 命令對變數 assign 數值，gdb 會顯示 **Cannot access memory address 0xXXXX.**
### 協助產生或解釋C語言宣告: [cdecl](http://manpages.ubuntu.com/manpages/bionic/man1/cdecl.1.html)
### 剪貼簿套件: [xclip](http://manpages.ubuntu.com/manpages/focal/man1/xclip.1.html)
* 將命令的標準輸出存入剪貼簿 (clipboard)
```shell
$ <command> | xclip -selection clipboard
```
可簡寫為
```shell
$ <command> | xclip -sel c
```
* 將檔案內容存入剪貼簿
```shell
$ xclip -selection clipboard <path>
```
可簡寫為
```shell
$ xclip -sel c <path>
```
### 多顯示器套件 (Multi-monitor): [xrandr](https://wiki.ubuntu.com/X/Config/Resolution)
* 檢視目前與系統相連接的輸出
```shell
$ xrandr
```
> ***xrandr*** shows you the names of different outputs available on your system (LVDS, VGA-0, etc.) and resolutions available on each. [For more details](https://wiki.archlinux.org/title/xrandr)
* 將 HDMI顯示器 (e.g. HDMI-1) 與目前的顯示器 (eDP-1) **畫面同步**
```shell
$ xrandr --output eDP-1 --same-as HDMI-1
```
### HackMD 常用鍵盤快捷鍵 ([keymap](https://hackmd.io/c/tutorials-tw/%2F%40docs%2Fkeyboard-shortcuts-tw))
| Discription | Keymap |
| ----------- | ------ |
| 複製前一行並向下新增 | Shift + Ctrl + D |
| 整行向上移動 | Shift + Ctrl + Up |
| 整行向下移動 | Shift + Ctrl + Down |
| 選取下一個相同的 Occurrence | Ctrl + D |
| 選取所有相同的 Occurrence | Alt + F3 |
### Github SSH keys 及將本地端 remote's URL 從 https 變更為 SSH
* 依 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github) 於 Github 新增 SSH Public Key
* 當本地端執行 `git push` 時出現以下警告:
```
remote: Support for password authentication was removed on August 13, 2021. Please use a personal access token instead.
remote: Please see https://github.blog/2020-12-15-token-authentication-requirements-for-git-operations/ for more information.
fatal: Authentication failed for 'https://github.com/XXXX/XXXX/'
```
表示本地端的 Remote's URL 尚未設定成 SSH 模式，
依 [Switching remote URLs from HTTPS to SSH](https://docs.github.com/en/get-started/getting-started-with-git/managing-remote-repositories#switching-remote-urls-from-https-to-ssh) 之步驟可順利更改設定，並成功執行 `git push`
###### tags: `linux2022`
Sign in with Wallet
Connect another wallet