2023 年 Linux 核心設計/實作課程作業 —— lab0 (A)

--- 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`。