---
title: 2023 年 Linux 核心設計/實作課程作業 —— lab0 (A)
image: https://i.imgur.com/robmeiQ.png
description: 改寫自 CMU Introduction to Computer Systems 課程第一份作業,擴充 GNU/Linux 開發工具的使用並強化自動分析機制。
tags: linux2023
---
# L01: [lab0](https://hackmd.io/@sysprog/linux2023-lab0)
:::warning
:warning: 請務必詳閱作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e) 及 [(六)](/@sysprog/linux2023-lab0-f)
:::
> 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2023 年系統軟體課程](https://www.facebook.com/groups/system.software2023/)
:mega: 返回「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表
==[解說影片](https://youtu.be/LhTU-DfV1T4)==
## :memo: 預期目標
* [C 語言程式設計](https://hackmd.io/@sysprog/c-programming) 議題,如[不定個數參數的處理](https://en.wikibooks.org/wiki/C_Programming/stdarg.h), [signal](https://en.wikibooks.org/wiki/C_Programming/signal.h), [setjmp/longjmp](https://en.wikibooks.org/wiki/C_Programming/setjmp.h) 和記憶體管理;
* 學習 [GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev)
- [Cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具
- [Valgrind](https://valgrind.org/): 動態程式分析工具
* 學習使用 Git 與 GitHub
* 樹立一致且易於協作的程式開發規範
* 研究自動測試機制
* 接觸 [Linux Programming Interface](http://man7.org/tlpi/)
* 理解電腦亂數原理、應用場景,和相關的驗證
* 研究 Linux 核心鏈結串列的實作機制,及其高效的排序實作
### :rocket: 改寫自 CMU 電腦系統概論的作業
[CMU](https://www.cmu.edu/) (位於美國賓州匹茲堡的卡內基美隆大學) 電腦科學系的 [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 課程準備 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知:
* 記憶體管理;
* 建立並管理需要透過指標操作的資料結構;
* 字串操作;
* 改善特定關鍵操作的效能;
* 提高程式碼的穩固程度,例如能夠處理無效的參數,包含 `NULL` 指標;
在給定的程式碼中,用鏈結串列 ([linked list](https://en.wikipedia.org/wiki/Linked_list)) 來實作佇列 ([queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))),請詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」,以得知 Linux 核心原始程式碼風格的鏈結串列實作的考量,並研讀 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)。
這過程可用下圖來表示:佇列的上層建構於鏈結串列為基礎的物件。一開始,此資料結構僅包含單一成員 `head`,之後陸續以鏈結串列增添給定的字串,如 `"cab"`, `"bead"`, `"cab"` 等等。佇列內的每個節點由單向的鏈結串列構成,每個節點由 `list_ele_t` 類型的物件來表示,後者包含真正保存字串的 `value` 和指向下個鏈結串列節點開頭地址的 `next`。
![圖 1](https://i.imgur.com/uZqLc9b.png)
> 圖 1: 透過鏈結串列實作的佇列。每個鏈結串列節點都有個 `value` 指標,指向一段連續的記憶體 (即 C-style string,以 NULL 字元結尾的字串),字元依據 ASCII 編碼 (以十六進位顯示)。
C 語言中,字串以連續的`char` 型態物件的排列來表示,對多數的硬體來說,`char` 型態表示為 1 個 byte。而為了儲存長度 `l` 的字串,需要至少 `l + 1` 個 `char` 節點,並在最後設定為 `\0` 字元。上圖的 `[cab, bead, cab]`,其中字元 `a` 和 `e` 以十六進位表示為 ASCII 編碼的 `61` 和 `65`。觀察上圖,字串 `"cab"` 和 `"bead"` 在執行時期可能對應到兩段不相鄰的記憶體。
在給定的 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 程式碼中,佇列透過 `queue_t *` 指標型態來操作,程式碼需要考慮以下二種特別狀況,作出對應的處置:
1. `NULL` 佇列:是指標值為 `NULL`;
2. 「空」(empty) 的佇列是指向有效結構,但開頭 (`head`) 的值為 `NULL`;
:::info
另一種解讀方式:
若你有空的紅包袋,裡面的東西是 empty;
若你連紅包袋都沒有,就可以說 NULL;
:::
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作,需要由學員補完並逐步精進,包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
* `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_reverseK`: 類似 `q_reverse`,但指定每 k 個節點為一組,進行反向順序排列,詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點,可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
* `q_descend`: 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
* `q_merge`: 合併所有==已排序==的佇列,並合而為一個新的已排序佇列,詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
:::info
:information_source: "delete" 和 "remove" 看似都是「刪去某物」,在 Linux 核心的 [include/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中,這二個動作並存,但實際行為卻不同。[Difference between "delete" and "remove"](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove) 其中的解釋可知:
* "remove" 這動作對於 linked list 來說,是斷開節點和節點的關聯,也就是說原本若是 A $\to$ B $\to$ C,在 `remove(B)` 操作完成後,就會變成 A $\to$ C 的節點關係。特別注意到 B 這個節點其實還存在於記憶體中,只是我們無法從節點間的關係看出來。於是 "remove" 可解讀為 "take away" (將某物帶走)
* "delete" 則有 "erase" 的涵義,若用於 linked list,則指某個節點將被「抹除」,對應的記憶體就會有變化
:::
在檔案 [queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 的程式碼註解可見到更詳盡的資訊,包括如何處理無效的操作 (如,從「空」佇列或 `NULL` 佇列中刪除),及應具有的副作用和返回值。你的程式碼將透過 `1,000,000` 個以上節點的佇列進行測試。
「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程延伸 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 並追加以下機制:
1. 探索 [GNU/Linux 開發環境](https://hackmd.io/@sysprog/gnu-linux-dev)並善用 [Git](https://git-scm.com/) 進行版本控制
* 整合 [Valgrind](https://valgrind.org/) 動態程式分析工具,作為精準的記憶體分析和除錯
3. 除了原本對佇列的插入、刪除、反轉等操作外,額外要求針對佇列和鏈結串列撰寫排序程式,並思考高效能的實作;
* 原本作業註解提示 `It should operate in O(1) time` 卻未有自動評分,本課程參照 [dudect](https://github.com/oreparaz/dudect) 工具及對應的論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf),提出以實驗而非理論驗證時間複雜度的方法
5. 支援 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer),強化執行時期的記憶體檢測;
6. 引入 [Git pre-commit hook](https://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks)
* 引入 [git-good-commit](https://github.com/tommarshall/git-good-commit),以互動操作來提示學員撰寫[良好的 Git commit message](https://chris.beams.io/posts/git-commit/)
* 透過 [clang-format](https://clang.llvm.org/docs/ClangFormat.html) 確保一致的程式風格
* 透過 [GNU Aspell](http://aspell.net/) 進行拼字檢查;
* 開啟更多 [Cppcheck](http://cppcheck.sourceforge.net/) 靜態程式碼檢查功能;
* 依據 CERN [Common vulnerabilities guide for C programmers
](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 gets / sprintf / strcpy 等不安全的函式;
4. 改善 Makefile,使其更加模組化;
5. 縮減程式碼,移除不使用的部分;
6. 引入 [Git pre-push hook](https://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks)
* 檢查是否自給定的 GitHub repository 進行 fork;
* 當提交 master 分支到遠端時確認程式碼可通過編譯;
* 提示學員 [Why is Git always asking for my password?](https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password)
上述的素養對於接觸有一定規模的開放原始碼專案 (特別是 Linux 核心),是非常關鍵的前期訓練。
給定的程式碼在編譯後,會得到名為 `qtest` 的執行檔,後者提供許多測試這次作業可用的工具,執行 `qtest` 後,輸入 `help` 即有各命令的解說。參考執行過程: (以 `$ ` 開頭的字串表示應當在命令列執行的命令)
```shell
$ ./qtest
cmd> help
Commands:
# ... | Display comment
dedup | Delete all nodes that have duplicate string
descend | Remove every node which has a node with a strictly greater value anywhere to the right side of it
dm | Delete middle node in queue
free | Delete queue
help | Show summary
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
merge | Merge all the queues into one sorted queue
new | Create new queue
next | Switch to next queue
option [name val] | Display or set options. See 'Options' section for details
prev | Switch to previous queue
quit | Exit program
reverse | Reverse queue
reverseK [K] | Reverse the nodes of the queue 'K' at a time
rh [str] | Remove from head of queue. Optionally compare to expected value str
rt [str] | Remove from tail of queue. Optionally compare to expected value str
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source | Read commands from source file
swap | Swap every two adjacent nodes in queue
time cmd arg ... | Time command execution
web [port] | Read commands from builtin web server
Options:
echo 1 | Do/don't echo commands
entropy 0 | Show/Hide Shannon entropy
error 5 | Number of errors until exit
fail 30 | Number of times allow queue operations to return false
length 1024 | Maximum length of displayed string
malloc 0 | Malloc failure probability percent
simulation 0 | Start/Stop simulation mode
verbose 4 | Verbosity level
```
:::info
:notebook: "command" 一詞的翻譯是「命令」,常見於終端機裡頭執行的 [shell](https://en.wikipedia.org/wiki/Unix_shell),而 "instruction" 的翻譯是「指令」,特別指在 CPU (central processing unit,中央處理單元) 所執行的 instruction。儘管在漢語中,這兩個詞彙很容易相互混淆,但「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程特別強調兩者差異,並期望學員務必使用精準的用語。
:::
本程式內建自動評分程式,以下是參考執行輸出。一開始什麼都沒做,當然是零分:
```
Test performance of insert_tail, size, and reverse
ERROR: Need to allocate separate string for each list element
ERROR: Insertion of gerbil failed (1 failures total)
ERROR: Computed queue size as 0, but correct value is 2
ERROR: Computed queue size as 0, but correct value is 2
--- trace-17-complexity 0/5
--- TOTAL 0/100
```
## :package: 開發環境設定
:::warning
:warning: 由於 [lab0-c](https://github.com/sysprog21/lab0-c) 進行前一節所提的客製化,對 GNU/Linux 和開發工具有高度依賴,所以學員務必依據下方描述,事先做好開發環境設定,再修改給定程式碼
:::
1. 依據 [GNU/Linux 開發工具共筆](https://hackmd.io/@sysprog/gnu-linux-dev) 的指引,設定好 Ubuntu Linux (建議是 22.04 或更新的版本,針對本作業中,可透過虛擬機器安裝), git, [GitHub](https://github.com/) 帳號, vim (或其他你偏好的編輯器) gnuplot
> :warning: 你註冊 [GitHub](https://github.com/) 帳號所用的電子郵件信箱應該是自己常用的,之後自動評分程式、授課教師,甚至是其他學員進行 code review 時,會發電子郵件到註冊帳號時指定的信箱
> 虛擬機器的選擇: 針對 [macOS](https://github.com/lima-vm/lima),可安裝 [lima](https://github.com/lima-vm/lima);針對 Microsoft Windows 11,可安裝 [WSL](https://learn.microsoft.com/zh-tw/windows/wsl/install)
2. 安裝必要的開發工具套件
```shell
$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff
```
3. 如果你之前尚未設定或使用過 GitHub 服務,請依循 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)。當然,你需要學習 git,可參考線上中文教材 ==《[為你自己學 Git](https://gitbook.tw/)》==
4. 學員需要知曉 GNU/Linux 命令列的操作,可參考成功大學校友[鳥哥](http://linux.vbird.org/vbird/) (蔡德明博士) 整理的 ==[鳥哥的 Linux 私房菜](http://linux.vbird.org/)== 進行線上學習。相關的章節:
* [Linux 的檔案權限與目錄配置](https://linux.vbird.org/linux_basic/centos7/0210filepermission.php)
* [Linux 檔案與目錄管理](https://linux.vbird.org/linux_basic/centos7/0220filemanager.php)
* [檔案與檔案系統的壓縮、打包與備份](https://linux.vbird.org/linux_basic/centos7/0240tarcompress.php)
5. 在 Ubuntu Linux 20.04-LTS 的 [Cppcheck](http://cppcheck.sourceforge.net/) 套件版本較舊,可能會使後文給定的程式碼進行靜態分析時,遇到 [false positive](https://en.wikipedia.org/wiki/False_positives_and_false_negatives),因此最好升級到 Cppcheck `v1.90`,可用 `$ cppcheck --version` 檢查版本,若小於 `1.90` 則需要額外準備:
* 可從 [Cppcheck 原始程式碼](https://github.com/danmar/cppcheck/) 開始編譯,這樣可取得最新發展的 Cppcheck,有助於揭露和修正問題。首先移除現有 Cppcheck 套件: `$ sudo apt remove cppcheck`,再依據 [Cppcheck Developer Info](http://cppcheck.sourceforge.net/devinfo/) 網頁指示,編譯並安裝 Cppcheck;
:::success
"If I had eight hours to chop down a tree, I’d spend six hours sharpening my axe." -- Abraham Lincoln
> 「如果我有 8 小時可以砍 1 棵樹,我會花 6 小時把斧頭磨利。」 -- 亞伯拉罕.林肯
> (類似漢語「工欲善其事,必先利其器」)
:::
## :dart: 取得程式碼並進行開發
:::warning
:warning: 如果你在 2023 年 2 月 14 日 15:00 之前,已從 GitHub [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 進行 fork,請參考下方流程,對舊的 repository 做對應處置,然後 sync fork
:notebook: 自 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) fork 後的 repository 名稱應該為 `lab0-c`,請確保名稱符合這規範,否則後續操作可能會失敗
:::spoiler 操作流程
#### 處置既有的 repository
- [ ] 方法一: 命令列
建立 repository, 如 `https://github.com/<username>/lab0-c_20XX.git`,
隨後在命令列,將本地端原有的工作區推送至新的 repository
```shell
git remote set-url origin https://github.com/<username>/lab0-c_20XX
git push
```
- [ ] 方法二: GitHub 網頁
利用 GitHub 網站提供的 `import repository`
![](https://i.imgur.com/bAATlsd.png =40%x)
- [ ] 同步 lab0-c
使用 GitHub 提供的 sync fork
![](https://i.imgur.com/l2Nv2lm.png =40%x)
如果有與 upstream 不一致的 commit ,會出現 discard commit 的提示
:::
首先,在 Ubuntu Linux 環境建立適合開發的目錄 (directory),例如 `/home/ubuntu/linux2023`:
```shell
$ cd ~
$ mkdir -p linux2023
```
:::info
:warning: 避免在 Ubuntu Linux 的「桌面」建立開發用的目錄,因為一旦路徑中出現漢字,在後續開發可能會遭遇困難,而且命令列輸入也不便。
:warning: "directory" 一詞的翻譯是「目錄」,不要跟 folder (檔案夾) 搞混了,後者是 Microsoft Windows 提出的用語。"directory" 這詞彙已行之有年,我們會說 UNIX directory,而非 folder。
:::
在剛才建立的新目錄,自 GitHub 取得 [lab0-c](https://github.com/sysprog21/lab0-c) 程式碼:
```shell
$ git clone https://github.com/sysprog21/lab0-c
```
:::success
一旦你 fork 後,可將上面 `sysprog21` 換為你的 GitHub 帳號,對應的命令會是:
```shell
$ git clone git@github.com:你的帳號名稱/lab0-c
```
或
```shell
$ git clone https://github.com/你的帳號名稱/lab0-c
```
:::
切換到 `lab0-c` 目錄並嘗試編譯程式碼:
```shell
$ cd lab0-c
$ make
```
預期會看到以下輸出:
```
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
```
也可清除編譯輸出的檔案:
```shell
$ make clean
```
若你想知道編譯過程的細節,可執行以下命令:
```shell
$ make VERBOSE=1
```
預期輸出:
```
gcc -o qtest.o -O1 -g -Wall -Werror -c -MMD -MF .qtest.o.d qtest.c
gcc -o report.o -O1 -g -Wall -Werror -c -MMD -MF .report.o.d report.c
gcc -o console.o -O1 -g -Wall -Werror -c -MMD -MF .console.o.d console.c
gcc -o harness.o -O1 -g -Wall -Werror -c -MMD -MF .harness.o.d harness.c
gcc -o queue.o -O1 -g -Wall -Werror -c -MMD -MF .queue.o.d queue.c
gcc -o qtest qtest.o report.o console.o harness.o queue.o
```
不難發現,名為 `qtest` 的執行檔正是編譯過程最終的輸出。請不要被上述一堆看似嚇人的參數給迷惑。UNIX 風格 (當然 GNU/Linux 也繼承這優良傳統) 是儘量揭露系統資訊給使用者,這也是「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程特別想讓學員體會到的精神。
:::info
:+1: 關於上述 make 的行為,可參見 ==[Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)==
:+1: 上述 gcc 和 `-o` 一類的參數使用,可參見 ==[你所不知道的 C 語言:編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)==
:::
參閱 [lab0-c](https://github.com/sysprog21/lab0-c) 的文件 (即 `README.md` 檔案) 後,我們得知能用以下命令測試 `qtest`:
```shell
$ make check
```
對應的程式輸出如下:
```
./qtest -v 3 -f traces/trace-eg.cmd
cmd>
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
```
參閱 `qtest` 的 `help` 命令輸出,我們可得知以下:
|qtest comand | function |
|---|---|
| new | Create new queue |
| free | Delete queue |
| ih str [n] | Insert string str at head of queue n times (default: n == 1) |
| it str [n] | Insert string str at tail of queue n times (default: n == 1) |
也就是說,`$ make check` 將 [traces/trace-eg.cmd](https://github.com/sysprog21/lab0-c/blob/master/traces/trace-eg.cmd) 檔案內容指派給 `qtest`,進行以下操作: (僅列出部分)
1. ==new==: 建立新的佇列;
2. ==ih==: 從佇列開頭 (head) 插入一個字串,內容是 "dolphin";
3. ==ih==: 繼續從佇列開頭插入一個字串,內容是 "bear";
4. ==ih==: 繼續從佇列開頭插入一個字串,內容是 "gerbil" ([沙鼠](https://zh.wikipedia.org/wiki/%E6%B2%99%E9%BC%A0));
5. ==it==: 從佇列尾端 (tail) 插入一個字串,內容是 "meerkat" ([狐獴](https://zh.wikipedia.org/wiki/%E7%8B%90%E7%8D%B4));
6. ==it==: 繼續從佇列尾端 (tail) 插入一個字串,內容是 "bear";
7. ==reverse==: 將佇列內部的鏈結串列順序予以反向;
:::info
:notebook: 你注意到檔名叫做 `trace-eg` 嗎?顯然這是個示範的檔案,但為何叫作 `eg` 呢?為何不用 "example" 開頭兩個字母來簡稱 "ex" 呢?這可有學問!"e.g." 是拉丁文 "exempli gratia" 的縮寫,意思是「例如」、「舉例來說」,即英文的 "for example" 或 "for instance"。
:notebook: 需要特別注意的是,==沒有 e.x. 這種縮寫== 而且 ==ex.== 的意思是「範例或練習」,也就是英文的 "exercise"。別再把 `ex.` 放到句子裡當「例如」的用途!
:::
`qtest` 的 `new` 命令可建立新的佇列,而 `prev` 和 `next` 命令可在這些佇列間切換 (內部是另一層環狀佇列),示意如下:
![](https://hackmd.io/_uploads/SyNxRdP6j.png)
> w~1~, w~2~, w~3~ 皆為藉由 `new` 建立的佇列
由於 [lab0-c](https://github.com/sysprog21/lab0-c) 已整合 [linenoise](https://github.com/antirez/linenoise),我們可善用其中的自動補齊 (auto-complete) 功能,假如目前已輸入 `he`:
```
cmd> he
|___ 游標在此
```
按下 tab 鍵,則完整的命令 `help` 會自動補齊,同樣地,若我們已輸入 `op` 再按下 tab 鍵,則會得到 `option`。此外,在 `cmd> ` 命令提示列中,我們可按「上」和「下」來切換歷史紀錄的命令。
初步理解 `qtest` 運作機制後,就可前進到 [lab0-c](https://github.com/sysprog21/lab0-c) 的自動評分系統。操作命令如下:
```shell
$ make test
```
實際就是執行 [scripts/driver.py](https://github.com/sysprog21/lab0-c/blob/master/scripts/driver.py) 這個 Python 程式。同樣地,請不要因為自己沒學過 Python 程式語言就退堂 (或「退選」),你可以快速瀏覽,應能發現,這個自動評分程式就是將 traces/trace-XX-CAT.cmd 這樣形式的命令序列提供給 `qtest` 內建的命令直譯器,然後依據給定的檢驗標準,逐一判定該給測試者多少分數。
或許你會糾結於 `driver.py` 這個檔名,在你的印象中,"driver" 的翻譯是「驅動程式」,不就是該用低階程式語言撰寫嗎?怎麼會跟 Python 和自動評分系統有關?
查閱 [dictionary.com](https://www.dictionary.com/) 的 "[driver](https://www.dictionary.com/browse/driver)" 詞目,我們會發現:
> Computers. software or hardware that controls the interface between a computer and a peripheral device.
> Electronics. a circuit whose output provides the input of another circuit
在電子電機電腦科學 (即 [EECS](https://en.wikipedia.org/wiki/Computer_Science_and_Engineering)) 領域中,"driver" 可以是軟體,也能是硬體,顯然上述的 "driver.py" 是軟體,其作用是控制電腦程式 (這裡指給定的命令序列,如 `ih` 及 `it`) 和特定的單元,後者就是由 `qtest` 所提供的命令直譯器。平常我們看到「驅動程式」的翻譯方式,其實是 device driver 的簡稱,在程式設計中,我們可見到類似的 "driver" 案例,如:
* database driver: [JDBC driver](https://en.wikipedia.org/wiki/JDBC_driver)
* compiler driver: gcc 本身就是
* test driver: 在 [Unit testing](http://softwaretestingfundamentals.com/unit-testing/) 常見;
另外,[lab0-c](https://github.com/sysprog21/lab0-c) 專案支援透過 `$ make SANITIZER=1` 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 從而強化執行時期的記憶體檢測,隨後 `$ make test` 執行過程中會見到類似以下輸出:
```
==8522==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x55ea517092cb bp 0x7ffe778b4900 sp 0x7ffe778b4900 T0)
==8522==The signal is caused by a READ memory access.
==8522==Hint: address points to the zero page.
#0 0x55ea517092ca in q_remove_head lab0-c/queue.c:74
#1 0x55ea51704880 in do_remove_head lab0-c/qtest.c:311
#2 0x55ea51707054 in interpret_cmda lab0-c/console.c:217
#3 0x55ea51707a58 in interpret_cmd lab0-c/console.c:240
#4 0x55ea51708725 in cmd_select lab0-c/console.c:568
#5 0x55ea51708b42 in run_console lab0-c/console.c:627
#6 0x55ea51705c7d in main lab0-c/qtest.c:700
#7 0x7facce0d8b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
#8 0x55ea51703819 in _start (lab0-c/qtest+0x5819)
```
這是**符合預期**的結果,請不要慌張。你可依循上述訊息,追查程式碼檔名及行號,推測為何會觸發 SIGSEGV (在 UNIX 及其相容系統上,意味著 [Segmentation fault](https://en.wikipedia.org/wiki/Segmentation_fault))。請搭配閱讀以下簡報:
* ==[Address/Thread/Memory Sanitizer](https://www.slideshare.net/sermp/sanitizer-cppcon-russia)==
* ==[A look into the sanitizer family (ASAN & UBSAN)](https://www.slideshare.net/CysinfoCommunity/a-look-into-the-sanitizer-family-asan-ubsan-by-akul-pillai)==
### clang-format 工具和一致的程式撰寫風格
[lab0-c](https://github.com/sysprog21/lab0-c) 採用的程式碼開發風格可參見 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md),後者與 Linux 核心的規範相近。
使用一致的 [programming style](https://en.wikipedia.org/wiki/Programming_style) 很重要,我們可透過 [clang-format](https://clang.llvm.org/docs/ClangFormat.html) 這個工具來調整作業程式要求的風格,使用方式如下:
```shell
$ clang-format -i *.[ch]
```
課程要求的 C 程式撰寫風格簡述:
* 使用 ==4 個空白字元==來進行縮排,不用 Tab;
- 為何不比照 Linux 核心都用 tab 呢?
- 首先是為了 code review 的便利,4 個空白字元可避免程式碼過寬,從而易於課堂討論,且和共筆系統 (這裡指 [HackMD](https://hackmd.io/)) 預設的縮排方式相符。
- 再者是考慮到不同的編輯器 (editor) 對於 tab 行為有落差,而且 [Google C++ Style Guide](https://google.github.io/styleguide/cppguide.html) 也建議使用空白字元而非 tab,這樣的風格被許多開放原始碼專案所採納;
* 將單一行程式碼寬度控制在 80 個字元內
- 任何一行超過 80 列寬度的敘述都該拆分成多個行
* switch 敘述的縮排方式是讓 case 與 switch 對齊,範例:
```cpp
switch (c) {
case 'h':
usage(argv[0]);
break;
```
* 延續 [K&R C](https://en.wikipedia.org/wiki/The_C_Programming_Language) 風格去處理大括號 (`{ }` 英語: curly brackets, 又稱花括號) 與空格
- Kernighan 和 Ritchie 在撰寫《[The C Programming Language](https://en.wikipedia.org/wiki/The_C_Programming_Language)》一書所用的程式範例,是把左大括號 `{` 放在行末,把右大括號 `}` 放在行首,如:
```cpp
if (x == true) {
do_y();
} else {
do_z();
}
do {
/* body of do-loop */
} while (condition);
```
- 然而有個特殊的例子,就是函式:函式的左大括號應該放在行首,如:
```cpp
int function(int x)
{
body of function
}
```
* 在不降低可讀性的前提下,儘可能減少空行的數量。無用的換行一旦減少,那就有更多的空行來寫註解。
* Linux 核心風格對於空格,體現於一些關鍵字的運用,即在關鍵字之後增添一個空格。值得關注的例外是一些長得像函式的關鍵字,如: `sizeof`, `typeof`, `alignof`, `__attribute__` (註: 這是 [gcc 延展的功能](https://gcc.gnu.org/onlinedocs/gcc/Attribute-Syntax.html)),在 Linux 核心中,這些關鍵字的使用都會帶上一對括號,儘管在 C 語言的使用上並不需帶上括號
* `sizeof` 不是函式,而是 operator!
* 在這些關鍵字之後新增一個空格: `if`, `switch`, `case`, `for`, `do`, `while`
- 但不要新增在 `sizeof`, `typeof`, `alignof`, `__attribute__` 之後
- 期望見到的用法是
```cpp
s = sizeof(struct file);
```
* 不要在括號周圍多此一舉的新增空格
- 下面這個例子糟透了
```cpp
s = sizeof( struct file );
```
* 在宣告指標或者返回值為指標的函式時,指標 (即 `*` 符號) 的位置應該緊靠著變數名稱或函式名稱,而非型別名稱,例如:
```cpp
char *linux_banner;
unsigned long long memparse(char *ptr, char **retptr);
char *match_strdup(substring_t *s);
```
* 在二元操作符和三元操作符周圍新增一個空格
- 例如: `= + - < > * / % | & ^ <= >= == != ? :`
- 但不要在一元操作符之後新增空格: `&*+-~!` `sizeof` `typeof` `alignof` `__attribute__` `defined`
- 不要在後綴的 `++` `--` 運算子之前新增空格 (即 `i++`)
- 不要在開頭的 `++` `--` 之後新增空格 (即 `++i`)
- 不要在結構體成員運算子 (即 `.` 和 `->`) 周圍新增空格
* 不要在行末新增多餘的空格
- 某些編輯器的「智慧」縮排會幫你在行首新增一些空格,好讓你在下一行可以立即撰寫程式碼。但某些編輯器不會自動刪去多餘的空格,儘管你已經寫完了一行程式碼。比如你只想留一行空行,但是編輯器卻「好心」地幫你填上了一些空格。這樣一來,你就在行末添加多餘的空格。
* 變數和函式命名力求簡潔且精準
- C 是種==簡潔粗獷==的語言,因此命名也該簡潔
- C 程式設計師不會像 Pascal 程式設計師那樣使用 `ThisVariableIsATemporaryCounter` 這種「可愛」的名字,相反地,一個 C 程式設計師會把這種變數命名為 `tmp`,如此簡潔易寫。
- 全域變數 (只有當你真正需要的時候才用它) 和全域函式 (也就是沒有用 `static` 宣告的函式) 需要使用描述性的名稱。若你有個計算活躍使用者數量的函式,你應該用 count_active_users() 一類的名稱,避免用 `cntusr()` 這樣不易望文生義的名稱。
- 起一個包含函式型別的名字([匈牙利命名法](https://en.wikipedia.org/wiki/Hungarian_notation))是摧殘大腦的行為,編譯器知道函式的型別並且會檢查型別,這樣的名字不會起到任何幫助,它僅僅會迷惑程式設計師。
- 區域變數名應該簡短,若你需要寫一個迴圈,定義一個計數器,在不產生歧義的情況下,你大可命名為 `i`。反過來說,命名為 `loop_counter` 是生產力很低的行為。同樣地,`tmp` 可以是任何型別的區域變數。
:::info
:-1: 你可以想像 Apple 和 Google 的工程師隨便安置程式碼,然後不用管合作的議題嗎?
:balloon: 「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程希望引導學員最終能夠欣然面對 Linux 核心或者有一定規模的軟體專案,不再只是「[舉燭](https://dict.revised.moe.edu.tw/dictView.jsp?ID=158282&la=0&powerMode=0)」,而是真正和世界各地的高手協作,上述看似繁雜的程式開發風格就會是相當基本且該貫徹的基本素養。
:+1: 或許你會反問:「只是一個作業,有必要這樣自虐嗎?」不妨這樣想:即便一個人寫作業,其實是三人的參與 —— 過去的你、現在的你,以及未來的你
:::
### [Git Hooks](https://www.atlassian.com/git/tutorials/git-hooks) 進行自動程式碼排版檢查
首次執行 `make` 後,Git pre-commit / pre-push hook 將自動安裝到現行的工作區 (workspace),之後每次執行 `git commit` 時,Git hook 會檢查 C/C++ 原始程式碼的風格是否一致,並透過 [Cppcheck](http://cppcheck.sourceforge.net/) 進行靜態程式碼檢查。
:::warning
:warning: 任何人都可以寫出機器看得懂的程式碼 (在 Windows 檔案總管裡面,隨便選一個 EXE 檔,按右鍵複製,隨後再貼上即可),但我們之所以到資訊工程系接受訓練,為了寫出人看得懂、可持續維護和改進的程式
:::
下圖展示 Git pre-commit hook 偵測到開發者的修改並未遵守一致的 coding style,主動回報並提醒開發者:
![](https://i.imgur.com/g7DQtYF.png)
紅色標注的二行程式碼 (即 `int member1;` 和 `int member2;`) 不符合指定的 4 個空白縮排方式,在 git pre-commit 階段就成功阻擋這樣風格不一致的程式碼變更。
### 撰寫 Git Commit Message 和自動檢查機制
![](https://i.imgur.com/stK5oBN.png)
Git commit message 是什麼呢?在取得 [lab0-c](https://github.com/sysprog21/lab0-c) 程式碼後,執行 `$ git log` 的輸出就是了。你或許會納悶,commit message 又不是程式碼,充其量只能算是「程式開發的軌跡」,為何要特別探討?
:::info
:notebook: 可安裝 `tig` 套件,更便利地瀏覽 git repository 資訊。
安裝方式: `$ sudo apt install tig`
參考執行畫面如下:
![](https://i.imgur.com/pMRybxY.png)
:::
Peter Hutterer 在 [On commit messages](https://who-t.blogspot.com/2009/12/on-commit-messages.html) 說得很精闢:
> 「重新了解一段程式碼更動的脈絡很浪費腦力。雖然這件事情沒辦法完全避免,但是我們可以盡量[降低](https://www.osnews.com/story/19266/wtfsm/)這件事情的複雜度。Commit messages 正可以做到這點,而**我們可以從 commit message 看出一個開發者是否為一位好的合作對象**。」
一個專案是否能長期且成功地運作 (撇除其他影響的因素),取決於它的可維護性,而在這件事上沒有其他工具比專案本身的開發軌跡更為強大。因此花時間學習如何撰寫與維護專案的開發紀錄,是件值得投資的事。一開始你可能會覺得麻煩,但它很快就會變成一種習慣,甚至能成為你之所以感到自豪及具備生產力的因素。
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 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/)) 提出,好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
[lab0-c](https://github.com/sysprog21/lab0-c) 內建 Git pre-commit hook 就包含依循上述七條規則的自動檢查,可阻擋不符合規則的 git commit message,此外還透過 [GNU Aspell](http://aspell.net/) 對 commit message 的標題進行拼字檢查。
:::info
:warning: 既然我們著眼於 Linux 核心,當然要用英語撰寫 commit message,英語不該只是大學畢業門檻,更該要活用,「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程還兼英語寫作的功效,真划算!
:::
以下實際操作 Git。
事先編輯檔案 `queue.h` 後,執行 `$ git commit` 會發現:
```shell
$ git commit
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
modified: queue.h
no changes added to commit
```
原來要指定變更的檔案,用命令 `$ git add`:
```shell
$ git add queue.h
```
:::success
:notebook: 可改用 `$ git commit -a` 這道命令,讓 Git 自動追蹤變更的檔案並提交
:::
重新 `git commit`,這時可發現安裝的 Git hooks 發揮作用:
```shell=
$ git commit -m "add fields to point to the tail"
add fields to point to the tail [line 1]
- Capitalize the subject line
Proceed with commit? [e/n/?] e
add fields to point to the tail [line 1]
- Capitalize the subject line
Proceed with commit? [e/n/?] y
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
e - edit commit message
n - abort commit
? - print help
Proceed with commit? [e/n/?] ?
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
e - edit commit message
n - abort commit
? - print help
Proceed with commit? [e/n/?] e
[master 23f7113] Add fields to point to the tail
```
Git pre-commit hook 提示我們:
* 第 4 行輸入 `e`,可編輯 git commit message;
* 第 7 行輸入 `y`,因為 y 不是有效選項, 所以出現 help;
* 第 17 行輸入 `e`, 再次編輯訊息,因訊息有限制標題開頭要大寫;
注意:請避免用 `$ git commit -m`,而是透過編輯器調整 git commit message。許多網路教學為了行文便利,用 `$ git commit -m` 示範,但這樣很容易讓人留下語焉不詳的訊息,未能提升為 [好的 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/)。因此,從今以後,不要用 `git commit -m`, 改用 `git commit -a` (或其他參數) 並詳細查驗變更的檔案。
在 Ubuntu Linux 預設組態中,執行 `$ git commit -a` 會呼叫 [GNU nano](https://www.nano-editor.org/) 來編輯訊息,可透過變更 `EDITOR` 環境變數,讓 git 找到你偏好的編輯器,例如指定 vim 就可以這樣做:
```shell
export EDITOR=vim
```
你也可把上述變更加到 bash 設定檔案中,例如:
```shell
$ echo "export EDITOR=vim" >> ~/.bashrc
```
或藉由 `git config` 命令,將偏好的編輯器寫入 git 組態,例如:
```shell
$ git config --global core.editor vim
```
> 延伸閱讀: [Customizing Git - Git Configuration](https://git-scm.com/book/en/v2/Customizing-Git-Git-Configuration)
一番折騰後,終於順利提交 (commit) 我們的變更:
``` shell
$ git commit -a
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
```
需要注意的是,目前提交的變更**僅存在於這台電腦中**,還未發佈到 GitHub 上,於是我們需要執行 `git push`
> 下方的 `jserv` 是示範帳號,請換為你自己的 GitHub 帳號名稱
```shell
$ git push
Username for 'https://github.com': jserv
Password for 'https://jserv@github.com':
Hint: You might want to know why Git is always asking for my password.
https://help.github.com/en/github/using-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
Pre-push check passed!
Counting objects: 4, done.
Delta compression using up to 64 threads.
Compressing objects: 100% (4/4), done.
Writing objects: 100% (4/4), 709 bytes | 709.00 KiB/s, done.
Total 4 (delta 3), reused 0 (delta 0)
remote: Resolving deltas: 100% (3/3), completed with 3 local objects.
To https://github.com/sysprog21/lab0-c
d2d7711..b42797a master -> master
```
不難發現上面訊息提到 [Why is Git always asking for my password?](https://help.github.com/en/github/using-git/why-is-git-always-asking-for-my-password) 這個超連結,如果你厭倦每次 `$ git push` 都需要輸入帳號及密碼,可參考超連結內容去變更設定。
又因 pre-push hook 使然,每次發布變更到 GitHub 服務時,只要是 `master` branch (主要分支) 就會觸發編譯要求,只有通過編譯的程式碼才能發布,但 `master` 以外的 branch 不受此限,換言之,我們鼓勵學員運用 `git branch` 進行各項實驗,請參照線上中文教材 ==《[為你自己學 Git](https://gitbook.tw/)》==。
### GitHub Actions 設定
GitHub Actions 是 GitHub 提供的 CI/CD 服務,CI/CD 代表的是 Continuous Integration 持續整合與 Continuous Deployment 持續部署,簡單來說就是將程式流程自動化。`lab0-c` 提供幾項自動化測試,包含:檢查排版、編譯結果和自動評分等等。這裡需要注意的是 fork 完成後,預設情況下 GitHub Action 不會被啟動,所以==需要手動開啟 GitHub Actions==,在你所 fork 出的 repository 的 Actions 內點選 `I understand my workflows, go ahead and enable them`,如下圖:
![](https://hackmd.io/_uploads/rkCn3UPJ9.png)
開啟 GitHub Actions 後,當每次 push 到遠端時,GitHub 就會自動測試作業設計的檢查項目,當有錯誤時會收到 CI failed 的 email 通知。
> 延伸閱讀: [Disabling and enabling a workflow](https://docs.github.com/en/actions/managing-workflow-runs/disabling-and-enabling-a-workflow)
在現有的 GitHub Actions 對應的測試項目中,一旦收到 `git push` 的事件,系統就會自動執行 `make test`,並在失敗時發信件通知學員。如下圖:
![](https://hackmd.io/_uploads/BJ05FPDJ9.png)
點擊信件中的 `View workflow run` 即可在 GitHub 網站中得知 GitHub Actions 的測試狀況。
> ![](https://hackmd.io/_uploads/SJUiXauJc.png)
### 牛刀小試
若你很有耐心地讀到這裡,恭喜你,終於可著手修改 [lab0-c](https://github.com/sysprog21/lab0-c) 程式碼。
這裡我們嘗試實作函式 `q_size`,首先找出 [`queue.c`](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 檔案中對應的註解:
> Return number of elements in queue.
> Return 0 if q is NULL or empty
修改 `queue.c` 檔案,嘗試撰寫以下程式碼: (`list_for_each` 是 Linux 核心風格的鏈結串列所提供的巨集,詳見 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html))
```cpp
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;
}
```
執行 `$ make check`,儘管無法通過指定的測試,但 `q_size` 的確正確執行,訊息如下:
```
cmd> # Create empty queue
cmd> new
l = NULL
cmd> # See how long it is
cmd> size
Warning: Calling size on null queue
Queue size = 0
l = NULL
```
看到 `Queue size = 0` 字樣,就表示上面的 `q_size` 已被呼叫。
如果你的開發環境裡頭沒有設定 git,請依據 [初次設定 Git](https://git-scm.com/book/zh-tw/v2/%E9%96%8B%E5%A7%8B-%E5%88%9D%E6%AC%A1%E8%A8%AD%E5%AE%9A-Git) 進行設定:
```shell
$ git config --global user.name 你偏好的英文或拼音名稱
$ git config --global user.email 你的電子郵件信箱
```
我們可用 `git commit` 命令來提交修改。不過當我們執行 `$ git commit -a` 時,會遇到程式碼排版和風格檢查的錯誤:
```diff
--- modified queue.c
+++ expected coding style
@@ -91,7 +91,8 @@ void q_release_element(element_t *e)
*/
int q_size(struct list_head *head)
{
- if (!head) return 0;
+ if (!head)
+ return 0;
int len = 0;
struct list_head *li;
[!] queue.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i queue.c
```
請依據指示,先執行 `clang-format -i queue.c` 再執行 `git commit`。