L01: lab0

請務必詳閱作業描述 (一), (二), (三), (四), (五) 及 (六)

主講人: jserv / 課程討論區: 2023 年系統軟體課程

返回「Linux 核心設計/實作」課程進度表

解說影片

預期目標

• C 語言程式設計 議題，如不定個數參數的處理, signal, setjmp/longjmp 和記憶體管理;
• 學習 GNU/Linux 開發工具
  • Cppcheck: 靜態程式碼分析工具
  • Valgrind: 動態程式分析工具
• 學習使用 Git 與 GitHub
• 樹立一致且易於協作的程式開發規範
• 研究自動測試機制
• 接觸 Linux Programming Interface
• 理解電腦亂數原理、應用場景，和相關的驗證
• 研究 Linux 核心鏈結串列的實作機制，及其高效的排序實作

改寫自 CMU 電腦系統概論的作業

CMU (位於美國賓州匹茲堡的卡內基美隆大學) 電腦科學系的 Introduction to Computer Systems (ICS) 課程準備 C Programming Lab 作為檢閱學生 C 語言程式設計的認知:

• 記憶體管理;
• 建立並管理需要透過指標操作的資料結構;
• 字串操作;
• 改善特定關鍵操作的效能;
• 提高程式碼的穩固程度，例如能夠處理無效的參數，包含 NULL 指標;

在給定的程式碼中，用鏈結串列 (linked list) 來實作佇列 (queue)，請詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」，以得知 Linux 核心原始程式碼風格的鏈結串列實作的考量，並研讀 The Linux Kernel API - List Management Functions。

這過程可用下圖來表示：佇列的上層建構於鏈結串列為基礎的物件。一開始，此資料結構僅包含單一成員 head，之後陸續以鏈結串列增添給定的字串，如 "cab", "bead", "cab" 等等。佇列內的每個節點由單向的鏈結串列構成，每個節點由 list_ele_t 類型的物件來表示，後者包含真正保存字串的 value 和指向下個鏈結串列節點開頭地址的 next。

圖 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 程式碼中，佇列透過 queue_t * 指標型態來操作，程式碼需要考慮以下二種特別狀況，作出對應的處置:

1. NULL 佇列：是指標值為 NULL;
2. 「空」(empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;

另一種解讀方式:
若你有空的紅包袋，裡面的東西是 empty;
若你連紅包袋都沒有，就可以說 NULL;

queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

• 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
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
• q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
• q_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group
• q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;
• q_descend: 參閱 LeetCode 2487. Remove Nodes From Linked List
• q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists

"delete" 和 "remove" 看似都是「刪去某物」，在 Linux 核心的 include/list.h 中，這二個動作並存，但實際行為卻不同。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 的程式碼註解可見到更詳盡的資訊，包括如何處理無效的操作 (如，從「空」佇列或 NULL 佇列中刪除)，及應具有的副作用和返回值。你的程式碼將透過 1,000,000 個以上節點的佇列進行測試。

「Linux 核心設計/實作」課程延伸 C Programming Lab 並追加以下機制:

1. 探索 GNU/Linux 開發環境並善用 Git 進行版本控制
   • 整合 Valgrind 動態程式分析工具，作為精準的記憶體分析和除錯
2. 除了原本對佇列的插入、刪除、反轉等操作外，額外要求針對佇列和鏈結串列撰寫排序程式，並思考高效能的實作;
   • 原本作業註解提示 It should operate in O(1) time 卻未有自動評分，本課程參照 dudect 工具及對應的論文 Dude, is my code constant time?，提出以實驗而非理論驗證時間複雜度的方法
3. 支援 Address Sanitizer，強化執行時期的記憶體檢測;
4. 引入 Git pre-commit hook
   • 引入 git-good-commit，以互動操作來提示學員撰寫良好的 Git commit message
   • 透過 clang-format 確保一致的程式風格
   • 透過 GNU Aspell 進行拼字檢查;
   • 開啟更多 Cppcheck 靜態程式碼檢查功能;
   • 依據 CERN Common vulnerabilities guide for C programmers
     建議而移除 gets / sprintf / strcpy 等不安全的函式;
5. 改善 Makefile，使其更加模組化;
6. 縮減程式碼，移除不使用的部分;
7. 引入 Git pre-push hook
   • 檢查是否自給定的 GitHub repository 進行 fork;
   • 當提交 master 分支到遠端時確認程式碼可通過編譯;
   • 提示學員 Why is Git always asking for my password?

上述的素養對於接觸有一定規模的開放原始碼專案 (特別是 Linux 核心)，是非常關鍵的前期訓練。

給定的程式碼在編譯後，會得到名為 qtest 的執行檔，後者提供許多測試這次作業可用的工具，執行 qtest 後，輸入 help 即有各命令的解說。參考執行過程: (以 $ 開頭的字串表示應當在命令列執行的命令)

$ ./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

"command" 一詞的翻譯是「命令」，常見於終端機裡頭執行的 shell，而 "instruction" 的翻譯是「指令」，特別指在 CPU (central processing unit，中央處理單元) 所執行的 instruction。儘管在漢語中，這兩個詞彙很容易相互混淆，但「Linux 核心設計/實作」課程特別強調兩者差異，並期望學員務必使用精準的用語。

本程式內建自動評分程式，以下是參考執行輸出。一開始什麼都沒做，當然是零分:

 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

開發環境設定

由於 lab0-c 進行前一節所提的客製化，對 GNU/Linux 和開發工具有高度依賴，所以學員務必依據下方描述，事先做好開發環境設定，再修改給定程式碼

1. 依據 GNU/Linux 開發工具共筆 的指引，設定好 Ubuntu Linux (建議是 22.04 或更新的版本，針對本作業中，可透過虛擬機器安裝), git, GitHub 帳號, vim (或其他你偏好的編輯器) gnuplot

   你註冊 GitHub 帳號所用的電子郵件信箱應該是自己常用的，之後自動評分程式、授課教師，甚至是其他學員進行 code review 時，會發電子郵件到註冊帳號時指定的信箱
   虛擬機器的選擇: 針對 macOS，可安裝 lima；針對 Microsoft Windows 11，可安裝 WSL

2. 安裝必要的開發工具套件
   ​​​​$ sudo apt install build-essential git-core valgrind
   ​​​​$ sudo apt install cppcheck clang-format aspell colordiff
   

3. 如果你之前尚未設定或使用過 GitHub 服務，請依循 GitHub 設定指引。當然，你需要學習 git，可參考線上中文教材 《為你自己學 Git》
4. 學員需要知曉 GNU/Linux 命令列的操作，可參考成功大學校友鳥哥 (蔡德明博士) 整理的 鳥哥的 Linux 私房菜 進行線上學習。相關的章節:
   • Linux 的檔案權限與目錄配置
   • Linux 檔案與目錄管理
   • 檔案與檔案系統的壓縮、打包與備份
5. 在 Ubuntu Linux 20.04-LTS 的 Cppcheck 套件版本較舊，可能會使後文給定的程式碼進行靜態分析時，遇到 false positive，因此最好升級到 Cppcheck v1.90，可用 $ cppcheck --version 檢查版本，若小於 1.90 則需要額外準備:
   • 可從 Cppcheck 原始程式碼 開始編譯，這樣可取得最新發展的 Cppcheck，有助於揭露和修正問題。首先移除現有 Cppcheck 套件: $ sudo apt remove cppcheck，再依據 Cppcheck Developer Info 網頁指示，編譯並安裝 Cppcheck;

"If I had eight hours to chop down a tree, I’d spend six hours sharpening my axe." – Abraham Lincoln

「如果我有 8 小時可以砍 1 棵樹，我會花 6 小時把斧頭磨利。」 – 亞伯拉罕．林肯
(類似漢語「工欲善其事，必先利其器」)

取得程式碼並進行開發

如果你在 2023 年 2 月 14 日 15:00 之前，已從 GitHub sysprog21/lab0-c 進行 fork，請參考下方流程，對舊的 repository 做對應處置，然後 sync fork

自 sysprog21/lab0-c fork 後的 repository 名稱應該為 lab0-c，請確保名稱符合這規範，否則後續操作可能會失敗

操作流程

處置既有的 repository

• 方法一: 命令列
  建立 repository， 如 https://github.com/<username>/lab0-c_20XX.git,
  隨後在命令列，將本地端原有的工作區推送至新的 repository

git remote set-url origin https://github.com/<username>/lab0-c_20XX
git push

• 方法二: GitHub 網頁
  利用 GitHub 網站提供的 import repository
  

• 同步 lab0-c
  使用 GitHub 提供的 sync fork
  

  
  如果有與 upstream 不一致的 commit ，會出現 discard commit 的提示

首先，在 Ubuntu Linux 環境建立適合開發的目錄 (directory)，例如 /home/ubuntu/linux2023:

$ cd ~
$ mkdir -p linux2023

避免在 Ubuntu Linux 的「桌面」建立開發用的目錄，因為一旦路徑中出現漢字，在後續開發可能會遭遇困難，而且命令列輸入也不便。

"directory" 一詞的翻譯是「目錄」，不要跟 folder (檔案夾) 搞混了，後者是 Microsoft Windows 提出的用語。"directory" 這詞彙已行之有年，我們會說 UNIX directory，而非 folder。

在剛才建立的新目錄，自 GitHub 取得 lab0-c 程式碼:

$ git clone https://github.com/sysprog21/lab0-c

一旦你 fork 後，可將上面 sysprog21 換為你的 GitHub 帳號，對應的命令會是:

$ git clone [e-mail]:你的帳號名稱/lab0-c

或

$ git clone https://github.com/你的帳號名稱/lab0-c

切換到 lab0-c 目錄並嘗試編譯程式碼:

$ 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

也可清除編譯輸出的檔案:

$ make clean

若你想知道編譯過程的細節，可執行以下命令:

$ 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 核心設計/實作」課程特別想讓學員體會到的精神。

關於上述 make 的行為，可參見 Makefile 語法和示範
上述 gcc 和 -o 一類的參數使用，可參見 你所不知道的 C 語言：編譯器和最佳化原理篇

參閱 lab0-c 的文件 (即 README.md 檔案) 後，我們得知能用以下命令測試 qtest:

$ 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 檔案內容指派給 qtest，進行以下操作: (僅列出部分)

1. new: 建立新的佇列;
2. ih: 從佇列開頭 (head) 插入一個字串，內容是 "dolphin";
3. ih: 繼續從佇列開頭插入一個字串，內容是 "bear";
4. ih: 繼續從佇列開頭插入一個字串，內容是 "gerbil" (沙鼠);
5. it: 從佇列尾端 (tail) 插入一個字串，內容是 "meerkat" (狐獴);
6. it: 繼續從佇列尾端 (tail) 插入一個字串，內容是 "bear";
7. reverse: 將佇列內部的鏈結串列順序予以反向;

你注意到檔名叫做 trace-eg 嗎？顯然這是個示範的檔案，但為何叫作 eg 呢？為何不用 "example" 開頭兩個字母來簡稱 "ex" 呢？這可有學問！"e.g." 是拉丁文 "exempli gratia" 的縮寫，意思是「例如」、「舉例來說」，即英文的 "for example" 或 "for instance"。
需要特別注意的是，沒有 e.x. 這種縮寫 而且 ex. 的意思是「範例或練習」，也就是英文的 "exercise"。別再把 ex. 放到句子裡當「例如」的用途！

qtest 的 new 命令可建立新的佇列，而 prev 和 next 命令可在這些佇列間切換 (內部是另一層環狀佇列)，示意如下:

w₁, w₂, w₃ 皆為藉由 new 建立的佇列

由於 lab0-c 已整合 linenoise，我們可善用其中的自動補齊 (auto-complete) 功能，假如目前已輸入 he:

cmd> he
       |___ 游標在此

按下 tab 鍵，則完整的命令 help 會自動補齊，同樣地，若我們已輸入 op 再按下 tab 鍵，則會得到 option。此外，在 cmd> 命令提示列中，我們可按「上」和「下」來切換歷史紀錄的命令。

初步理解 qtest 運作機制後，就可前進到 lab0-c 的自動評分系統。操作命令如下:

$ make test

實際就是執行 scripts/driver.py 這個 Python 程式。同樣地，請不要因為自己沒學過 Python 程式語言就退堂 (或「退選」)，你可以快速瀏覽，應能發現，這個自動評分程式就是將 traces/trace-XX-CAT.cmd 這樣形式的命令序列提供給 qtest 內建的命令直譯器，然後依據給定的檢驗標準，逐一判定該給測試者多少分數。

或許你會糾結於 driver.py 這個檔名，在你的印象中，"driver" 的翻譯是「驅動程式」，不就是該用低階程式語言撰寫嗎？怎麼會跟 Python 和自動評分系統有關？

查閱 dictionary.com 的 "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) 領域中，"driver" 可以是軟體，也能是硬體，顯然上述的 "driver.py" 是軟體，其作用是控制電腦程式 (這裡指給定的命令序列，如 ih 及 it) 和特定的單元，後者就是由 qtest 所提供的命令直譯器。平常我們看到「驅動程式」的翻譯方式，其實是 device driver 的簡稱，在程式設計中，我們可見到類似的 "driver" 案例，如:

• database driver: JDBC driver
• compiler driver: gcc 本身就是
• test driver: 在 Unit testing 常見;

另外，lab0-c 專案支援透過 $ make SANITIZER=1 開啟 Address Sanitizer 從而強化執行時期的記憶體檢測，隨後 $ 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)。請搭配閱讀以下簡報:

• Address/Thread/Memory Sanitizer
• A look into the sanitizer family (ASAN & UBSAN)

clang-format 工具和一致的程式撰寫風格

lab0-c 採用的程式碼開發風格可參見 CONTRIBUTING.md，後者與 Linux 核心的規範相近。

使用一致的 programming style 很重要，我們可透過 clang-format 這個工具來調整作業程式要求的風格，使用方式如下:

$ clang-format -i *.[ch]

課程要求的 C 程式撰寫風格簡述:

• 使用 4 個空白字元來進行縮排，不用 Tab;
  • 為何不比照 Linux 核心都用 tab 呢？
  • 首先是為了 code review 的便利，4 個空白字元可避免程式碼過寬，從而易於課堂討論，且和共筆系統 (這裡指 HackMD) 預設的縮排方式相符。
  • 再者是考慮到不同的編輯器 (editor) 對於 tab 行為有落差，而且 Google C++ Style Guide 也建議使用空白字元而非 tab，這樣的風格被許多開放原始碼專案所採納;
• 將單一行程式碼寬度控制在 80 個字元內
  • 任何一行超過 80 列寬度的敘述都該拆分成多個行
• switch 敘述的縮排方式是讓 case 與 switch 對齊，範例:
  ​​​​    switch (c) {
  ​​​​    case 'h':
  ​​​​        usage(argv[0]);
  ​​​​        break;
  

• 延續 K&R C 風格去處理大括號 ({ } 英語: curly brackets， 又稱花括號) 與空格
  • Kernighan 和 Ritchie 在撰寫《The C Programming Language》一書所用的程式範例，是把左大括號 { 放在行末，把右大括號 } 放在行首，如:
  ​​​​if (x == true) {
  ​​​​    do_y();
  ​​​​} else {
  ​​​​    do_z();
  ​​​​}
  ​​​​do {
  ​​​​    /* body of do-loop */
  ​​​​} while (condition);
  

  • 然而有個特殊的例子，就是函式：函式的左大括號應該放在行首，如：
  ​​​​int function(int x)
  ​​​​{
  ​​​​    body of function
  ​​​​}
  

• 在不降低可讀性的前提下，儘可能減少空行的數量。無用的換行一旦減少，那就有更多的空行來寫註解。
• Linux 核心風格對於空格，體現於一些關鍵字的運用，即在關鍵字之後增添一個空格。值得關注的例外是一些長得像函式的關鍵字，如: sizeof, typeof, alignof, __attribute__ (註: 這是 gcc 延展的功能)，在 Linux 核心中，這些關鍵字的使用都會帶上一對括號，儘管在 C 語言的使用上並不需帶上括號
  • sizeof 不是函式，而是 operator!
• 在這些關鍵字之後新增一個空格: if, switch, case, for, do, while
  • 但不要新增在 sizeof, typeof, alignof, __attribute__ 之後
  • 期望見到的用法是
  ​​​​s = sizeof(struct file);
  

• 不要在括號周圍多此一舉的新增空格
  • 下面這個例子糟透了
  ​​​​s = sizeof( struct file );
  

• 在宣告指標或者返回值為指標的函式時，指標 (即 * 符號) 的位置應該緊靠著變數名稱或函式名稱，而非型別名稱，例如：
  ​​​​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() 這樣不易望文生義的名稱。
  • 起一個包含函式型別的名字(匈牙利命名法)是摧殘大腦的行為，編譯器知道函式的型別並且會檢查型別，這樣的名字不會起到任何幫助，它僅僅會迷惑程式設計師。
  • 區域變數名應該簡短，若你需要寫一個迴圈，定義一個計數器，在不產生歧義的情況下，你大可命名為 i。反過來說，命名為 loop_counter 是生產力很低的行為。同樣地，tmp 可以是任何型別的區域變數。

你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？
「Linux 核心設計/實作」課程希望引導學員最終能夠欣然面對 Linux 核心或者有一定規模的軟體專案，不再只是「舉燭」，而是真正和世界各地的高手協作，上述看似繁雜的程式開發風格就會是相當基本且該貫徹的基本素養。
或許你會反問：「只是一個作業，有必要這樣自虐嗎？」不妨這樣想：即便一個人寫作業，其實是三人的參與 —— 過去的你、現在的你，以及未來的你

Git Hooks 進行自動程式碼排版檢查

首次執行 make 後，Git pre-commit / pre-push hook 將自動安裝到現行的工作區 (workspace)，之後每次執行 git commit 時，Git hook 會檢查 C/C++ 原始程式碼的風格是否一致，並透過 Cppcheck 進行靜態程式碼檢查。

任何人都可以寫出機器看得懂的程式碼 (在 Windows 檔案總管裡面，隨便選一個 EXE 檔，按右鍵複製，隨後再貼上即可)，但我們之所以到資訊工程系接受訓練，為了寫出人看得懂、可持續維護和改進的程式

下圖展示 Git pre-commit hook 偵測到開發者的修改並未遵守一致的 coding style，主動回報並提醒開發者:

紅色標注的二行程式碼 (即 int member1; 和 int member2;) 不符合指定的 4 個空白縮排方式，在 git pre-commit 階段就成功阻擋這樣風格不一致的程式碼變更。

撰寫 Git Commit Message 和自動檢查機制

Git commit message 是什麼呢？在取得 lab0-c 程式碼後，執行 $ git log 的輸出就是了。你或許會納悶，commit message 又不是程式碼，充其量只能算是「程式開發的軌跡」，為何要特別探討？

可安裝 tig 套件，更便利地瀏覽 git repository 資訊。
安裝方式: $ sudo apt install tig
參考執行畫面如下:

Peter Hutterer 在 On commit messages 說得很精闢：

「重新了解一段程式碼更動的脈絡很浪費腦力。雖然這件事情沒辦法完全避免，但是我們可以盡量降低這件事情的複雜度。Commit messages 正可以做到這點，而我們可以從 commit message 看出一個開發者是否為一位好的合作對象。」

一個專案是否能長期且成功地運作 (撇除其他影響的因素)，取決於它的可維護性，而在這件事上沒有其他工具比專案本身的開發軌跡更為強大。因此花時間學習如何撰寫與維護專案的開發紀錄，是件值得投資的事。一開始你可能會覺得麻煩，但它很快就會變成一種習慣，甚至能成為你之所以感到自豪及具備生產力的因素。

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how

lab0-c 內建 Git pre-commit hook 就包含依循上述七條規則的自動檢查，可阻擋不符合規則的 git commit message，此外還透過 GNU Aspell 對 commit message 的標題進行拼字檢查。

既然我們著眼於 Linux 核心，當然要用英語撰寫 commit message，英語不該只是大學畢業門檻，更該要活用，「Linux 核心設計/實作」課程還兼英語寫作的功效，真划算！

以下實際操作 Git。
事先編輯檔案 queue.h 後，執行 $ git commit 會發現:

$ 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:

$ git add queue.h

可改用 $ git commit -a 這道命令，讓 Git 自動追蹤變更的檔案並提交

重新 git commit，這時可發現安裝的 Git hooks 發揮作用:

$ 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。因此，從今以後，不要用 git commit -m, 改用 git commit -a (或其他參數) 並詳細查驗變更的檔案。

在 Ubuntu Linux 預設組態中，執行 $ git commit -a 會呼叫 GNU nano 來編輯訊息，可透過變更 EDITOR 環境變數，讓 git 找到你偏好的編輯器，例如指定 vim 就可以這樣做:

export EDITOR=vim

你也可把上述變更加到 bash 設定檔案中，例如:

$ echo "export EDITOR=vim" >> ~/.bashrc

或藉由 git config 命令，將偏好的編輯器寫入 git 組態，例如：

$ git config --global core.editor vim

延伸閱讀: Customizing Git - Git Configuration

一番折騰後，終於順利提交 (commit) 我們的變更:

$ 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 帳號名稱

$ git push
Username for 'https://github.com': jserv
Password for 'https://[e-mail]':
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? 這個超連結，如果你厭倦每次 $ git push 都需要輸入帳號及密碼，可參考超連結內容去變更設定。

又因 pre-push hook 使然，每次發布變更到 GitHub 服務時，只要是 master branch (主要分支) 就會觸發編譯要求，只有通過編譯的程式碼才能發布，但 master 以外的 branch 不受此限，換言之，我們鼓勵學員運用 git branch 進行各項實驗，請參照線上中文教材 《為你自己學 Git》。

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，如下圖:

開啟 GitHub Actions 後，當每次 push 到遠端時，GitHub 就會自動測試作業設計的檢查項目，當有錯誤時會收到 CI failed 的 email 通知。

延伸閱讀: Disabling and enabling a workflow

在現有的 GitHub Actions 對應的測試項目中，一旦收到 git push 的事件，系統就會自動執行 make test，並在失敗時發信件通知學員。如下圖:

點擊信件中的 View workflow run 即可在 GitHub 網站中得知 GitHub Actions 的測試狀況。

牛刀小試

若你很有耐心地讀到這裡，恭喜你，終於可著手修改 lab0-c 程式碼。

這裡我們嘗試實作函式 q_size，首先找出 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)

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 進行設定:

$ git config --global user.name 你偏好的英文或拼音名稱
$ git config --global user.email 你的電子郵件信箱

我們可用 git commit 命令來提交修改。不過當我們執行 $ git commit -a 時，會遇到程式碼排版和風格檢查的錯誤:

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