---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [`DennisLiu16`](https://github.com/DennisLiu16) >
## 實驗環境
```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): 20
On-line CPU(s) list: 0-19
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i9-10900F CPU @ 2.80GHz
Stepping: 5
CPU MHz: 2800.000
CPU max MHz: 5200.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
Virtualization: VT-x
L1d cache: 320 KiB
L1i cache: 320 KiB
L2 cache: 2.5 MiB
L3 cache: 20 MiB
NUMA node0 CPU(s): 0-19
```
### 事前
* 熟悉 Git 命令和 commit 格式 -- [個人筆記](https://computer-knowledge.notion.site/Git-148cfefd97e945e9a04e820f80f2aac5)
* 熟悉 [Makefile 語法](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)
* 熟悉 [Valgrind](https://valgrind.org/)
* 熟悉 [Cppcheck](https://github.com/danmar/cppcheck/)
* 詳閱 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
* 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
* fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 設定 [GitHub Actions](https://hackmd.io/dPYu4WH8TuqXnAJvfxm-JA?both#:~:text=%E8%87%AA%E5%B7%B1%E5%AD%B8%20Git%E3%80%8B%E3%80%82-,GitHub%20Actions%20%E8%A8%AD%E5%AE%9A,-GitHub%20Actions%20%E6%98%AF)
### queue 實做
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_release_element`: 釋放特定節點的記憶體空間;
* `q_size`: 計算目前佇列的節點總量;
* `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/)
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
### qtest 相關
* 提供新命令 ```shuffle```，能透過 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 對佇列中所有節進行洗牌 (shuffle) 動作
* 提供新命令 ```web```，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令，並嘗試整合 tiny-web-server[ -- github](https://github.com/7890/tiny-web-server)
### 其他
* 使用 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 修正錯誤
* 使用 Valgrind 進行記憶體錯誤排查
* 解釋 [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
## 環境設定紀錄
### 套件檢查 & 安裝
1. 必要套件
``` shell
$ sudo apt install build-essential git valgrind
$ sudo apt install clang-format aspell colordiff tig
```
2. Cppcheck
* [How to install latest Cppcheck using Git and CMake](https://github.com/danmar/cppcheck/blob/main/readme.txt#:~:text=*%20clang%2B%2B-,cmake,cmake%20%2D%2Dbuild%20.,-If%20you%20want)
``` bash
# clone the repo
git clone git://github.com/danmar/cppcheck.git
cd cppcheck
# build and install
mkdir build && cd build && cmake .. && cmake --build .
make install
# reload terminal or open a new one
source ~/.bashrc
# check
which cppcheck
# /usr/local/bin/cppcheck
cppcheck --version
# Cppcheck 2.7
# make a test file test.c
echo -e "int main(){ \n\tchar a[10]; \n\ta[10] = 0; \n}" >> test.c
# test some file
cppcheck --enable=all test.c
# some error will show
# test.c:3:3: error: Array 'a[10]' accessed at index 10, which is out of bounds.[arrayIndexOutOfBounds]
# a[10] = 0;
# ^
# test.c:3:8: style: Variable 'a[10]' is assigned a value that is never used. [unreadVariable]
# a[10] = 0;
# ^
```
3. 安裝 [tig](https://jonas.github.io/tig/) (較好檢視 git commit)
### 開通 [GitHub Actions](https://hackmd.io/dPYu4WH8TuqXnAJvfxm-JA?view#:~:text=%E8%87%AA%E5%B7%B1%E5%AD%B8%20Git%E3%80%8B%E3%80%82-,GitHub%20Actions%20%E8%A8%AD%E5%AE%9A,-GitHub%20Actions%20%E6%98%AF)
## Queue
### `q_new`
* 思路
:::info
回傳型別是 ```list_head *``` 且沒有引數，需使用 malloc 在 heap 上申請大小同 ```struct list_head``` 的記憶體空間，[malloc 在某些情況下會回傳 NULL](https://stackoverflow.com/a/16186593)，需於 [```INIT_LIST_HEAD```](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html?highlight=init_list_head#c.INIT_LIST_HEAD) 初始化前檢查，避免輸入 NULL 造成例外。
:::
* ```void *``` 的思考
malloc 回傳 ```void *``` 型別指標，根據 [你所不知道的C語言：指標篇 -- ```void *```之謎](https://hackmd.io/@sysprog/c-pointer?type=view#void--%E4%B9%8B%E8%AC%8E)，```void *``` 的存在是確保使用者確實轉型，那是否需要進行強制轉型呢？
參考問題 [Do I cast the result of malloc?](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) 下的三個回答:
* [Issue of cast and sizeof. (Someone said this answer should update)](https://stackoverflow.com/a/605858)
* [In C, you don't need to cast the return value of malloc.](https://stackoverflow.com/a/605856)
* [You do cast.](https://stackoverflow.com/a/14879184)
:::warning
問題使我困惑，目前對本例(即 malloc)而言，評論中贊同 C 中要 casting 主要立場是 C/C++ 有更好的相容性和能讓編譯器提出轉型相關的警告。不贊同要 casting 的主張 malloc 內部已經包含能使 ```void *```安全轉型成各種 pointer 的實做，因此不需要多此一舉，造成閱讀困難。目前看起來不應該使用 casting 比合理，因為可以透過 extern 界面達到 C/C++ 的兼容，所以看起來沒有一定要使用 casting 的理由？
> C 和 C++ 已是截然不同的程式語言，在 C++ 混用 malloc 可能會造成非預期的行為，另外，C++ 有專用的運算子，如 `static_cast`，本質上不該仰賴 C 語言風格的 casting。本課程要求學員撰寫出簡短、有效，和符合規格的程式碼，因此你不需要額外對 `void *` 型態的 `malloc` 返回值進行 casting，因為編譯器會幫你做。不用看太多網際網路上面的討論，應該儘量閱讀規格書並運用其中的條款來分析程式碼的運作。
> :notes: jserv
:::
一致的是，大家建議在 ```sizeof``` 中使用 dereference of lvalue，避免更動左值時忘記更動型別。
* ```INIT_LIST_HEAD``` 的變革 ([WRITE_ONCE 的使用](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC))
最新版本中(v5.17-rc5)，被定義於```include/linux/list.h```之下的```INIT_LIST_HEAD```的程式如下
```c
/**
* INIT_LIST_HEAD - Initialize a list_head structure
* @list: list_head structure to be initialized.
*
* Initializes the list_head to point to itself. If it is a list header,
* the result is an empty list.
*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}
```
而在 v4.5-rc1 之前的版本如下
```c
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
```
* **程式**
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (head != NULL)
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
:::spoiler list 走訪 macro
* [`list_entry`](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L345)
>list_entry 透過 `container_of` 與輸入 `list_head *` 可返回指向 entry「結構體」指標，本作業中即返回指向結構 `element_t` 的指標，而非返回指向 list_head 的指標。可使用該返回值對結構體進行 `->` 操作。
::: warning
list 之中有眾多走訪巨集，以下分析適用情境
:::
* [```list_for_each```](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L378)
此種走訪適用於**讀取鏈結串列資訊 (read only)** e.g. ```q_size```，註解同樣提到若改動 list 中的 element (list_head) 可能產生 UB。
> The nodes and the head of the list must be kept unmodified while
iterating through it. Any modifications to the the list will cause undefined
behavior.
* [```list_for_each_entry```](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L394)
* ```member``` 是 ```list_head``` 在 ```entry``` 的變數名
此種走訪適用於**讀取結構體參數 (read only)**，註解提到若改動 list 中的 element (list_head) e.g. 指標指向，則可能產生 UB。
* [```list_for_each_safe```](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L409)
此種走訪適用於**更改鏈結串列資訊 (R/W)**，透過多輸入 ```safe``` 指標儲存下一個 ```list_head``` node 確保修正不造成鏈結串列毀損
* [```list_for_each_entry_safe```](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L425)
此種走訪適用於**更改結構體參數 (R/W)**，可修改原理同上
:::
* 思路
:::info
釋放結構體時，需考慮結構體中的[指標是否由 ```malloc``` 動態配置](https://stackoverflow.com/questions/4915369/how-to-free-a-struct-that-contains-only-pointers)，因此要觀察 queue 內的元素組成。由 ```q_remove_head``` 可知佇列中的元素類型 ```element_t``` (包含 list 和字串)， ``` queue.h ``` 中的定義為：
```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;
```
1. 註解中提到 ```value``` 用於保存字串，需由我們進行配置和「刪除」，因此刪除節點前應先刪除 ```char *``` 記憶體空間
2. ```element``` 是透過 ```q_insert_xxx``` 申請的
3. ```l``` 也是我們利用 ```malloc``` 申請的
因此三者皆需刪除。由於需要修改 (free) ```entry``` 內部，因此要用 [```list_for_each_entry_safe```](https://github.com/DennisLiu16/lab0-c/blob/981b12b53600ce094c8d9daf641594c50bdb1196/list.h#L425)走訪。
:::
:::warning
```free``` 可以用 q_release_element 代替
:::
* **程式**
```c
/* Free all storage used by queue */
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(entry->value);
//free(entry);
}
free(l);
}
```
### `q_insert_head`
* 思路
:::info
* 從頭插入，即將鏈表插入到 ```head->next```，對應```list_add```
:::
* [```strlcpy```](https://en.cppreference.com/w/c/string/byte/strdup)
不使用 ```strcpy``` 的原因是容易造成記憶體溢位。代替方法可以使用 [```strlcpy```](https://security.web.cern.ch/recommendations/en/codetools/c.shtml#:~:text=strcpy(str1%2Cstr2)%3B-,Mitigation,-The%20best%20way)，透過直接輸入長度確保不溢位。[CERN](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 有提供 ```strlcpy``` 的實做
```c
#include <stdio.h>
#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif
```
由 ```snprtinf``` 實現所以會自動添加中止符```'\0'```，即僅複製 ```sz - 1``` 個字元，以下是測試：
```c
#include <stdio.h>
#include <stdlib.h>
#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif
int main() {
size_t bufsize = 10;
char *sp = malloc(sizeof(*sp) * bufsize);
char *s = "stop at->nothing should show out";
strlcpy(sp, s, bufsize);
printf("%s", sp);
}
// return "stop at->", 9 char + '\0' == 10 char
```
* **程式**
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *entry;
if (!head || !(entry = malloc(sizeof(*entry))))
return false;
size_t len = strlen(s) + 1;
if (!(entry->value = malloc(sizeof(char) * len)))
return false;
strlcpy(entry->value, s, len);
list_add(&entry->list, head);
return true;
}
```
### `q_insert_tail`
* 思路
:::info
* 實做概念同 ```q_insert_head```
:::
* **程式**
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *entry;
if (!head || !(entry = malloc(sizeof(*entry))))
return false;
size_t len = strlen(s) + 1;
if (!(entry->value = malloc(sizeof(char) * len)))
return false;
strlcpy(entry->value, s, len);
list_add_tail(&entry->list, head);
return true;
}
```
### `q_remove_head`
* 思路
:::info
* 可以透過巨集 ```list_first_entry``` 得到首個 entry
* 由 ```list_del``` 移除該 entry
* 若 ```sp``` 地址有效才複製
* ```strlcpy``` 會自動加上 ```'\0'```，因此不用特別修改 ```bufsize```
:::
* **程式**
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_first_entry(head, element_t, list);
list_del(&entry->list);
if (sp)
strlcpy(sp, entry->value, bufsize);
return entry; // memory leak if user forget to check ret
}
```
### `q_remove_tail`
* 思路
:::info
* 實做概念同 ```q_remove_head```，重複程式之後再透過其他函式包裝？
:::
* **程式**
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_last_entry(head, element_t, list);
list_del(&entry->list);
if (sp)
strlcpy(sp, entry->value, bufsize);
return entry; // memory leak if user forgets to check ret
}
```
### `q_release_element`
* 題目說不能動
* **程式**
```c
void q_release_element(element_t *e)
{
free(e->value); // free(NULL) is ok.
free(e);
}
```
### `q_size`
* **程式**
```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`
* 思路
:::info
* 先檢查 ```head``` 是否有效
* 透過 ```list_for_each``` 初始式先走快指針，於迴圈中再一起走一步，之後靠迴圈和迴圈內雙重檢查可以讓佇列中不論是奇數或偶數都讓慢指針停在正確的位置
* 透過 ```list_entry``` 得到 entry指標，並透過 list_del 移除該entry
* 移除完成後要釋放，透過 ```free``` 或 ```q_release_element``` 都可以
:::
:::warning
透過 indirect pointer 的實做待補
:::
* **程式**
```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;
// using fast and slow pointer
struct list_head *fast = head, *slow = head;
list_for_each(fast, head) {
fast = fast->next;
slow = slow->next;
if(fast == head)
break;
}
element_t *e = list_entry(slow, element_t, list);
list_del(&e->list);
q_release_element(e);
/* using indirect pointer
*/
return true;
}
```
### `q_delete_dup`
* 思路
* ```list_for_each_entry_safe``` 注意事項
```list_for_each_entry_safe``` 中僅保證對 entry 的操作安全，並不保證對 safe 的操作是安全的
```c
// my.c, compile cmd : gcc -o my my.c queue.o harness.o report.o
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "queue.h"
int main()
{
struct list_head *head = q_new();
char* s = "test";
q_insert_head(head, s);
q_insert_head(head, s);
q_insert_head(head, s);
element_t *e, *safe;
list_for_each_entry_safe(e, safe, head, list) {
printf("safe->list is head : %d, value:%s\n",&safe->list == head,safe->value);
}
}
```
會得到
```
safe->list is head : 0, value:test
safe->list is head : 0, value:test
Segmentation fault (core dumped)
```
* **程式**
### `q_swap`
* 思路
* **程式**
### `q_reverse`
* 思路
* **程式**
### `q_sort`
* 思路
* **程式**
Sign in with Wallet
Connect another wallet