# 2025q1 Homework1 (lab0)
contributed by < `lumynou5` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
程式碼位於 [`impl` 分支](https://github.com/lumynou5/lab0-c/tree/impl)。
## Reviews
### Reviewed by `HeatCrab`
對於 [lab0-c](https://github.com/sysprog21/lab0-c) 來說，同學可能做了很多的貢獻，也發現了許多有趣值得改良的問題。
但是筆記內並沒有過多的紀錄與 [2025 年 Linux 核心設計課程作業 —— lab0](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a) 內中作業說明，或是作業要求有關的內容。
我在查看了 [同學的 Github](https://github.com/lumynou5/lab0-c) 後發現也沒有找到明確同學的 commit 紀錄，如果有 rebase 過的話，應該可以直接清晰地在整個 commit 紀錄的最上端，但卻只有找到跟 upstream 相關的紀錄。
> 我有一些還在測試有沒有比較好而沒有提交的變更，不過確實我過程紀錄得太少了。
## 事前準備
我決定繼續上次未完的開發，首先將上次的提交重定基底到 `master` 分支，並修改提交訊息符合新的規範。
:::danger
不要打錯專案的名稱。
:::
根據 [Gerrit 文件](https://gerrit-review.googlesource.com/Documentation/user-changeid.html)最後一節，只要在提交訊息後加上 `Change-Id`（由於 `master` 上的提交已經有了，不需要自己加），其後續的提交便會自動加上，但我發現這不適用於重定基底，因為 `pick` 不會觸發提交掛鉤程式。解決方法是使用 `reword` 重新編輯提交訊息，正好需要移除訊息中的 backtick。若不需要修改提交訊息，可以使用 `git -c rebase.instructionFormat='%s%nexec git commit --amend --no-edit' rebase master`，利用修補使之視為新提交。
過程中我發現程式碼靜態分析無法通過，輸出
```
queue.c:28:5: error: There is an unknown macro here somewhere. Configuration is required. If list_for_each_entry_safe is a macro then please configure it. [unknownMacro]
list_for_each_entry_safe (entry, safe, head, list)
^
```
原因是 `list.h` 中的條件編譯，導致 Cppcheck 認為巨集可能（`--force` 選項會檢查每種情況）不存在（[#210](https://github.com/sysprog21/lab0-c/issues/210)）：
```c=447
#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, typeof(*entry), member), \
safe = list_entry(entry->member.next, typeof(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, typeof(*entry), member))
#endif
```
解決方法有:
1. 不使用 `--force`，並加上 `-D__LIST_HAVE_TYPEOF`，只檢查有 `typeof` 的情況。但如此影響太大。
2. 使用 `#error` 導引。但如此就沒必要存在 `__LIST_HAVE_TYPEOF`，因為若以沒有 `typeof` 的實作編譯便會報錯，程式碼強制依賴於 `typeof`。
3. 加上一個 `#else` 分支定義假巨集。如此在沒有 `typeof` 的情況，不使用 `list_for_each_entry` 等巨集的部分仍可編譯。（[#211]）
4. 給這些巨集加上 `type` 參數，就像 `list_entry` 等巨集。如此這些巨集便不再依賴於 `typeof`，但更改了介面。
:::danger
`#error` 是 [preprocessor directives](https://cplusplus.com/doc/tutorial/preprocessor/)，注意用語！
> 已改譯為「導引」，和 command 與 instruction 區別。
> [name=Lumynous]
:::
`cppcheck-suppress-macro` 註解可以抑制使用巨集的地方產生的錯誤，但因為此例巨集根本沒定義，自然也就不能用了。
在 [#211] 合併後有[同學回報](https://github.com/sysprog21/lab0-c/pull/211#issuecomment-2690577631) Cppcheck 2.13.0（即 [Ubuntu 24.04 LTS 提供的版本](https://packages.ubuntu.com/noble/cppcheck)）會出現 `Label 'int' is not used. [unusedLabel]` 的錯誤，這是 Cppcheck 的 bug 導致的誤報（false positive，在其 bug 回報中常縮寫為 FP），於 [#215](https://github.com/sysprog21/lab0-c/pull/215) 改成能繞過該 bug 的寫法。後者錯誤地刪除了指派值給 `safe` 的程式碼，導致 Cppcheck 可能會抱怨變數未初始化，於 [#228](https://github.com/sysprog21/lab0-c/pull/228) 修復。
## 其他
### [#213] Refine trace command descriptions
不知道為什麼被老師提及了，並提了一些意見。這個 PR 針對 trace 的描述做出改善，補上所有會呼叫的函式，當測試不通過時便知道是哪些函式中有錯誤。
### [#226] Remove similar trailer keys from commit hook
我注意到 [#214](https://github.com/sysprog21/lab0-c/pull/214) 中加入的尾標鍵有些重複，`Close` 和 `Closes` 是同一個詞，`Bug` 與其也沒什麼差異。
另外，GitHub 將 PR 連結到 issue 的功能不確定能不能在動詞和 issue 編號間加入冒號，[文件](https://docs.github.com/en/issues/tracking-your-work-with-issues/using-issues/linking-a-pull-request-to-an-issue#linking-a-pull-request-to-an-issue-using-a-keyword)中寫的語法只有如「KEYWORD #ISSUE-NUMBER」的形式，範例中亦皆僅以空格分隔的。後來測試確定了 GitHub 能夠辨識尾標格式的連結 issue，我便藉此機會向 GitHub 文件貢獻，現在這項資訊能夠在官方文件中找到了：[github/docs#36607](https://github.com/github/docs/pull/36607)。
### [#242] Introduce EditorConfig
之前在改 `scripts/` 目錄下的 hook 時，剛好看到有些地方縮排不對。在修正後，我決定引入 EditorConfig，其內建於多個編輯器中，因此不需要額外設定便能讓編輯器自動使用正確的縮排。
[老師希望能夠自動檢查](https://github.com/sysprog21/lab0-c/pull/242#issuecomment-2710774231)，但 EditorConfig 不同於 clang-format，旨在提供協作的開發者在不同編輯器上能夠簡單地有一致的程式碼樣式，就如它的名字，只是編輯器的設定，它沒辦法知道語法，也就無法針對 Bash here-document（有兩種語法，分別不能使用空格縮排和完全不能縮排）做出處理。因此其僅僅只是避免人為失誤造成像此提交之前的錯誤縮排（由於主流文字編輯器和 IDE 都支援之），而無法避免開發者蓄意加入錯誤的縮排，不過這也提供了彈性，讓開發者可以選擇對人類更可讀的格式，例如以空格對齊未完而分成兩行的命令引數。
### [#260] Improve aspell dictionary
我遇到一些縮寫 aspell 不認識想要加到自訂的字典時，發現裡面很亂，有些詞語還重複了兩次。如果字典經過排序的話，就能更好看出某個字是不是已經在裡面了，避免重複加入。
至於目前已經很亂的字典，可以利用 `sort(1)` 排序，並加上 `-u` 選項刪除重複項目。不過字典檔開頭有一行標頭，不應該被排序，我使用 [`bat`](https://github.com/sharkdp/bat) 的 `-r` 選項來輸出檔案的特定範圍，再以管道傳給 `sort`。
```shell
$ bat -r 2: scripts/aspell-pws | sort -du
```
不過 `bat` 不是 coreutils 的工具，要加入到版本庫的 `pre-commit.hook` 不適合使用。我發現 `tail(1)` 也能從絕對行數開始輸出，因此改以 `tail -n +2` 替換。
值得注意的是，`sort` 會將排序過的字典輸出到標準輸出流，當然也可以加上 `-o` 選項輸出到檔案，不過這樣標頭會消失，可以用 `sed` 或 `cat` 等工具在排序完之後將標頭加回第一行。
```shell
# With GNU extension:
$ tail -n +2 scripts/aspell-pws | sort -duo scripts/aspell-pws && sed -i '1ipersonal_ws-1.1 en 500' scripts/aspell-pws
```
### [#285] Fix string operation truncation
在測試性能時，我發現若改以 `-O3` 編譯會出錯，因為 `Makefile` 中指定了 `-Werror`，`stringop-truncation` 警告提升到錯誤而中止編譯，這個警告會在 `strncpy` 等字串操作可能導致目的字串沒有 null-terminator 時出現。使用 `-O1` 沒有報錯是[因為這種複雜的分析是由編譯器最佳化元件負責的](https://stackoverflow.com/questions/66915714/why-flto-silent-gccs-warning-stringop-truncation/66915982#66915982)，因此 `-O1` 時 GCC 不會檢查到這項問題。
報錯的其中一處是因為加上 null-terminator 的變數寫錯了，`lbuf` 誤寫成 `buf`；另一處則是依賴的 linenoise 並未傳入緩衝區大小給 callback，`strncpy` 的第三個引數是來源字串的長度，這可能導致緩衝區溢位，因此改為傳入緩衝區的大小。
之中我學到了對函式簽名的更動都應該說明清楚為什麼要這麼做、為什麼必須這麼做等問題，否則在追溯更改時可能就找不回改動的原因了，而且這樣的更動可能會影響到其他人的開發。在本例中，除了緩衝區溢位的安全問題外，更重要的是這會導致程式直接無法通過編譯，因此修正是必要的。
### [#291] Ignore spell of indented lines in commit messages
讓提交訊息中可以用縮排（兩個空格）來引用程式碼等，輔助說明更動的目的。
### [#293] Allow inline assembly
因為對三路比較的最佳化用到了 inline assembly 而延伸出的議題。
fmtscan 會檢查所有字串字面值，包含 inline assembly 中的，但這顯然不是我們想要的，因為 mnemonics 不太可能有「正確的拼寫」。所以我參考既有的 `skip_comments` 和 `skip_macros` 函式，實作了跳過 inline assembly 的功能。並在老師的提醒上，增加對 `__asm__` 和 `__asm` 關鍵字的支援，其中後者是目前 GCC 文件不記錄的歷史遺留。
接著我發現，Cppcheck 無法辨識[顯式暫存器變數](https://gcc.gnu.org/onlinedocs/gcc/Explicit-Register-Variables.html)的語法，會誤報 `syntaxError`，且沒有任何繞過的方法，在 Cppcheck 修正前只能關掉整個 `syntaxError`，所幸若真有語法錯誤便根本無法編譯，很容易發現而不仰賴 Cppcheck。
### [#294] Fix the commit message hook
之前 [#291] 因為編輯器括號自動成對的 bug，意外導致提交訊息的行數計算功能壞掉，我沒發現，因而在此 PR 中修正。並且忽略縮排的行的功能也不正確，只有第一行會跳過，我當時的測試並不完整。
## 實作
### `q_sort`
我選擇以快速排序（quick sort）實作，因其有優秀的時間複雜度 $O(n \log n)$。
:::danger
注意是否有 stable sorting 的要求。
:::
### `q_ascend`、`a_descend` 最佳化
原本是由一個函式統一實作，透過分別傳入不同的比較函式（小於和大於），來達到不同的順序。由於老師上課時提到 retpoline，讓我意識到透過函式指標間接呼叫會有額外的成本（即便沒有額外安全機制，函式呼叫也讓程式多出跳轉），而且兩個函式實作幾乎重複也是一種壞味道。因此我將兩個比較函式整合成一個類似 C++ 三路比較運算子 `<=>`（俗稱「太空梭運算子」）的函式，回傳 `-1` 表示左運算元小於右運算元、`0` 表示等於、`1` 表示大於。
之所以將回傳值限制在這三個值，而不直接使用 `strcmp` 的回傳值是為了讓 `ascend_descend_impl` 的統一實作更簡單，只要判斷三路比較的結果是否等於傳入的 `1` 或 `-1` 即可。
實作為：
```c
int x = strcmp(lhs->value, rhs->value);
return (x > 0) - (x < 0);
```
於 `strcmp` 之後的組合語言（gcc 14.2.1 `-O3`）為：
```
xorl %edx, %edx ;; 歸零 %edx。
testl %eax, %eax ;; 如果 %eax（回傳值）……
setg %dl ;; 大於 0，將 %dl（%edx 低 8 位元）設為 1。
shrl $31, %eax ;; 邏輯右移 %eax 31 位，變成 1 代表負數，反之為 0。
subl %eax, %edx ;; %edx -= %eax，現在 %edx 就是三路比較結果。
```
### 三路比較最佳化
因為好奇是否能讓三路比較結果更有效率，在 [#285] 合併後，便開始測試和比較性能。一開始，我用 `perf stat` 測試 `qtest`，並以 Python 產生了 10000 個隨機值作為佇列的元素（每次執行是一樣的 trace。[程式碼](https://gist.github.com/lumynou5/47ff4684d750ab38f8e5f1f70ecbccdd#file-gen_trace-py)），但每次結果卻都不相同，推測是要測試的 `q_ascend` 在整個 `qtest` 佔比太小，還有 I/O（讀取 trace 等）的外在因素干擾了結果。
我試著用 `perf_event_open` 系統呼叫記錄指令數和 CPU 週期數，將程式碼加到 `ascend_descend_impl` 裡就能只測到 `q_ascend`，然而 CPU 週期數會受到 frequency scaling 影響，我不知道怎麼得出可比較的數值。manpage 提到有不受其影響的 CPU 週期事件，但我的電腦似乎不支援，會回傳 `ENOENT`，表示通用事件不支援。
因此我試著計算這些指令需要多少個週期。由於這些指令沒有存取記憶體，不用考慮存取資料可能會有快取的問題。[表格](https://www.agner.org/optimize/instruction_tables.pdf)中列有每種指令的延遲（latency）和吞吐量倒數（reciprocal throughput）：前者表示指令的結果要幾個週期後才能得出，也就是會造成該指令之後依賴其結果的指令延遲那麼多週期；後者表示一連串同類型且不互相依賴（independent）的指令，從指令開始執行到下一道指令可以開始執行需要的平均週期數。例如 `IMUL` 的吞吐量倒數為 1，代表連續兩道獨立的 `IMUL` 指令，第二道可以在第一道開始 1 個週期後執行（1 個週期後第一道才進行到不同的階段，讓第二道能開始），而其延遲為 3，代表結果要在 3 個週期後才算完。而 `XOR` 的吞吐量倒數為 1/3 代表一個週期可以處理 3 道 `XOR` 指令。
- 週期 1
- `XOR` 開始執行。
- `TEST` 和 `XOR` 沒有依賴關係，得益於超純量（superscalar）和多個 ALU，可以同時執行。
- `SHR` 和 `XOR`、`TEST`、`SETcc` 沒有依賴關係，得益於暫存器重新命名（register renaming），可以和 `TEST` 並行不悖。
因為以上指令都只包含一個微操作（micro-ops），以 AMD Zen 2 微架構（microarchitecture）為例有 4 個 ALU，每週期最多分派（dispatch）6 個微操作。
- 週期 2
- `SETcc` 依賴 `TEST` 設定的旗標，後者延遲為 1，因此現在才能開始。
- 週期 3
- `SUB` 依賴 `SETcc` 和 `SHR` 的結果，兩者延遲皆為 1，因此現在才能開始。
#### 嘗試 1
我一開始的想法是，算術右移後就是以符號位填充整個暫存器，也就是正數、零、負數分別變成 {0, 0, -1}，這樣就直接得到 -1 了。並且位移會將進位旗標（CF）設為最後移出的位元，如果將符號位移出 CF 就是符號位了，但對 32 位元暫存器至多只能位移 32 位，因此得先複製到 64 位元暫存器上。最後的程式碼是：
```
movsxl %eax, %rdx
sarq $32, %rdx
sbbq $0, %rdx
negl %eax
adcq $0, %rdx
```
`sbb` 指令會將 `%rdx` 減去 0 和 CF 的值，因此會變成 {0, 0, -2}；而 `neg` 會根據來源運算元是否為 0 清除或設定 CF，因此 `adc` 後便是 {1, 0, -1}。
但依賴鏈 `MOVSX` -> `SAR` -> `SBB` -> `ADC` 需要 4 個週期（每種指令延遲都是 1，`neg` 可與其他指令平行），表現更差。
接著進行實際測試，透過以組合語言撰寫，並重複足夠多次來減少干擾（[程式碼](https://gist.github.com/lumynou5/47ff4684d750ab38f8e5f1f70ecbccdd#file-test-s)）。嘗試判讀 `perf stat` 測量的結果：
```
Performance counter stats for './test' (1000 runs):
146.22 msec task-clock # 0.996 CPUs utilized ( +- 0.11% )
12 context-switches # 82.069 /sec ( +- 3.12% )
0 cpu-migrations # 0.000 /sec
17 page-faults # 116.265 /sec ( +- 0.13% )
2,100,782,472 instructions # 3.49 insn per cycle
# 0.00 stalled cycles per insn ( +- 0.00% )
602,546,852 cycles # 4.121 GHz ( +- 0.00% )
350,652 stalled-cycles-frontend # 0.06% frontend cycles idle ( +- 0.67% )
300,173,261 branches # 2.053 G/sec ( +- 0.00% )
4,808 branch-misses # 0.00% of all branches ( +- 0.64% )
0.146746 +- 0.000163 seconds time elapsed ( +- 0.11% )
```
要測試的程式碼有 5 道指令，加上迴圈的 `dec` 和 `jnz` 是 7 道，$7 \times 3 = 21$ 符合預期。實際耗費的週期數卻遠比預期低，只有約 2 個週期。推測是 `SBB` 和 `ADC` 重疊了，而 `ADC` 依賴 `SBB` 運算結果則靠 bypass network 發送至之前的流水線階段，`SAR` 同理。
> The ALU pipelines carry out integer arithmetic and logical operations and evaluate branches. Each ALU pipeline is headed by a scheduler with a 16-entry micro-op queue. The scheduler tracks the availability of operands and issues up to one micro-op per cycle which is ready for execution, oldest first, to the ALU. Together all schedulers in the core can issue up to 11 micro-ops per cycle, this is not sustainable however due to the available dispatch and retire bandwidth. ==The PRF or the bypass network supply up to two operands to each pipeline. The bypass network enables back-to-back execution of dependent instructions by forwarding results from the ALUs to the previous pipeline stage.== Data from load operations is superforwarded through the bypass network, obviating a write and read of the PRF.
> —[WikiChip](https://en.wikichip.org/wiki/amd/microarchitectures/zen_2)
- 週期 1
- `MOVSX` 寫入 `%rdx`
- `NEG`
- 週期 2
- `SAR` 讀寫 `%rax`
- `SBB` 讀寫 `%rdx`，使用 `SAR` 的旗標
- `ADC` 讀寫 `%rdx`，使用 `NEG` 的旗標
不過與原本的程式比較發現並沒有性能上的差異，因為原本認為分別會在第二和第三個週期執行的 `SETcc` 和 `SUB` 也能得益於相同的技術於同一個週期完成，最終也是 2 個週期。那麼就沒有理由使用這個版本的程式碼，因其使用了組合語言、64 位元暫存器卻沒有效益，且在較舊的 CPU 上表現可能更差。
#### 嘗試 2
繼續嘗試最佳化。`CDQ` 指令將 `%eax` 的符號位複製到 `%edx` 的每個位元，能一道指令就達到 {0, 0, -1}，將零和負數兩種情況都完成。
```
cmpl $0, %eax
cdq
movl $1, %eax
cmovgl %eax, %edx
```
之後以 `CMOVcc` 在正數的情況下將 `%edx` 設為 1。因為 `CMOVcc` 運算元不能是立即值，要先將 1 寫到 `%eax`（隨便一個地方）。不用 `SETcc` 則是因為這樣在負數時會覆蓋掉 `CDQ` 的結果。
使用 `CMOVcc` 相比原本的 `SETcc`，可避免在較早的 CPU 上使用部分暫存器（partial register）的額外成本。雖然在現代 CPU 上同樣需要 2 個週期，但少了 1 道指令，仍相比原本的版本更好。
這段程式還能更進一步：`cmpl $0, %eax` 可以用 `testl %eax, %eax` 替代，能讓二進位檔小 1 個位元組。
參考資料：<https://stackoverflow.com/questions/692718/how-many-cpu-cycles-are-needed-for-each-assembly-instruction/44980899#44980899>、<https://www.felixcloutier.com/x86/>
感謝 Mes 和 visitorckw 的討論。
[#211]: https://github.com/sysprog21/lab0-c/pull/211
[#213]: https://github.com/sysprog21/lab0-c/pull/213
[#226]: https://github.com/sysprog21/lab0-c/pull/226
[#242]: https://github.com/sysprog21/lab0-c/pull/242
[#260]: https://github.com/sysprog21/lab0-c/pull/260
[#285]: https://github.com/sysprog21/lab0-c/pull/285
[#291]: https://github.com/sysprog21/lab0-c/pull/291
[#293]: https://github.com/sysprog21/lab0-c/pull/293
[#294]: https://github.com/sysprog21/lab0-c/pull/294
Sign in with Wallet
Connect another wallet