2025q1 Homework1 (lab0)

contributed by < lumynou5 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

程式碼位於 impl 分支。

Reviews

Reviewed by HeatCrab

對於 lab0-c 來說，同學可能做了很多的貢獻，也發現了許多有趣值得改良的問題。
但是筆記內並沒有過多的紀錄與 2025 年 Linux 核心設計課程作業 —— lab0 內中作業說明，或是作業要求有關的內容。
我在查看了 同學的 Github 後發現也沒有找到明確同學的 commit 紀錄，如果有 rebase 過的話，應該可以直接清晰地在整個 commit 紀錄的最上端，但卻只有找到跟 upstream 相關的紀錄。

我有一些還在測試有沒有比較好而沒有提交的變更，不過確實我過程紀錄得太少了。

事前準備

我決定繼續上次未完的開發，首先將上次的提交重定基底到 master 分支，並修改提交訊息符合新的規範。

不要打錯專案的名稱。

根據 Gerrit 文件最後一節，只要在提交訊息後加上 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）：

#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，但更改了介面。

#error 是 preprocessor directives，注意用語！

已改譯為「導引」，和 command 與 instruction 區別。
Lumynous

cppcheck-suppress-macro 註解可以抑制使用巨集的地方產生的錯誤，但因為此例巨集根本沒定義，自然也就不能用了。

在 #211 合併後有同學回報 Cppcheck 2.13.0（即 Ubuntu 24.04 LTS 提供的版本）會出現 Label 'int' is not used. [unusedLabel] 的錯誤，這是 Cppcheck 的 bug 導致的誤報（false positive，在其 bug 回報中常縮寫為 FP），於 #215 改成能繞過該 bug 的寫法。後者錯誤地刪除了指派值給 safe 的程式碼，導致 Cppcheck 可能會抱怨變數未初始化，於 #228 修復。

其他

#213 Refine trace command descriptions

不知道為什麼被老師提及了，並提了一些意見。這個 PR 針對 trace 的描述做出改善，補上所有會呼叫的函式，當測試不通過時便知道是哪些函式中有錯誤。

#226 Remove similar trailer keys from commit hook

我注意到 #214 中加入的尾標鍵有些重複，Close 和 Closes 是同一個詞，Bug 與其也沒什麼差異。

另外，GitHub 將 PR 連結到 issue 的功能不確定能不能在動詞和 issue 編號間加入冒號，文件中寫的語法只有如「KEYWORD #ISSUE-NUMBER」的形式，範例中亦皆僅以空格分隔的。後來測試確定了 GitHub 能夠辨識尾標格式的連結 issue，我便藉此機會向 GitHub 文件貢獻，現在這項資訊能夠在官方文件中找到了：github/docs#36607。

#242 Introduce EditorConfig

之前在改 scripts/ 目錄下的 hook 時，剛好看到有些地方縮排不對。在修正後，我決定引入 EditorConfig，其內建於多個編輯器中，因此不需要額外設定便能讓編輯器自動使用正確的縮排。

老師希望能夠自動檢查，但 EditorConfig 不同於 clang-format，旨在提供協作的開發者在不同編輯器上能夠簡單地有一致的程式碼樣式，就如它的名字，只是編輯器的設定，它沒辦法知道語法，也就無法針對 Bash here-document（有兩種語法，分別不能使用空格縮排和完全不能縮排）做出處理。因此其僅僅只是避免人為失誤造成像此提交之前的錯誤縮排（由於主流文字編輯器和 IDE 都支援之），而無法避免開發者蓄意加入錯誤的縮排，不過這也提供了彈性，讓開發者可以選擇對人類更可讀的格式，例如以空格對齊未完而分成兩行的命令引數。

#260 Improve aspell dictionary

我遇到一些縮寫 aspell 不認識想要加到自訂的字典時，發現裡面很亂，有些詞語還重複了兩次。如果字典經過排序的話，就能更好看出某個字是不是已經在裡面了，避免重複加入。

至於目前已經很亂的字典，可以利用 sort(1) 排序，並加上 -u 選項刪除重複項目。不過字典檔開頭有一行標頭，不應該被排序，我使用 bat 的 -r 選項來輸出檔案的特定範圍，再以管道傳給 sort。

$ bat -r 2: scripts/aspell-pws | sort -du

不過 bat 不是 coreutils 的工具，要加入到版本庫的 pre-commit.hook 不適合使用。我發現 tail(1) 也能從絕對行數開始輸出，因此改以 tail -n +2 替換。

值得注意的是，sort 會將排序過的字典輸出到標準輸出流，當然也可以加上 -o 選項輸出到檔案，不過這樣標頭會消失，可以用 sed 或 cat 等工具在排序完之後將標頭加回第一行。

# 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 沒有報錯是因為這種複雜的分析是由編譯器最佳化元件負責的，因此 -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 無法辨識顯式暫存器變數的語法，會誤報 syntaxError，且沒有任何繞過的方法，在 Cppcheck 修正前只能關掉整個 syntaxError，所幸若真有語法錯誤便根本無法編譯，很容易發現而不仰賴 Cppcheck。

#294 Fix the commit message hook

之前 #291 因為編輯器括號自動成對的 bug，意外導致提交訊息的行數計算功能壞掉，我沒發現，因而在此 PR 中修正。並且忽略縮排的行的功能也不正確，只有第一行會跳過，我當時的測試並不完整。

實作

q_sort

我選擇以快速排序（quick sort）實作，因其有優秀的時間複雜度

$O(n\log n)$。

注意是否有 stable sorting 的要求。

q_ascend、a_descend 最佳化

原本是由一個函式統一實作，透過分別傳入不同的比較函式（小於和大於），來達到不同的順序。由於老師上課時提到 retpoline，讓我意識到透過函式指標間接呼叫會有額外的成本（即便沒有額外安全機制，函式呼叫也讓程式多出跳轉），而且兩個函式實作幾乎重複也是一種壞味道。因此我將兩個比較函式整合成一個類似 C++ 三路比較運算子 <=>（俗稱「太空梭運算子」）的函式，回傳 -1 表示左運算元小於右運算元、0 表示等於、1 表示大於。

之所以將回傳值限制在這三個值，而不直接使用 strcmp 的回傳值是為了讓 ascend_descend_impl 的統一實作更簡單，只要判斷三路比較的結果是否等於傳入的 1 或 -1 即可。

實作為：

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。程式碼），但每次結果卻都不相同，推測是要測試的 q_ascend 在整個 qtest 佔比太小，還有 I/O（讀取 trace 等）的外在因素干擾了結果。

我試著用 perf_event_open 系統呼叫記錄指令數和 CPU 週期數，將程式碼加到 ascend_descend_impl 裡就能只測到 q_ascend，然而 CPU 週期數會受到 frequency scaling 影響，我不知道怎麼得出可比較的數值。manpage 提到有不受其影響的 CPU 週期事件，但我的電腦似乎不支援，會回傳 ENOENT，表示通用事件不支援。

因此我試著計算這些指令需要多少個週期。由於這些指令沒有存取記憶體，不用考慮存取資料可能會有快取的問題。表格中列有每種指令的延遲（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 可與其他指令平行），表現更差。

接著進行實際測試，透過以組合語言撰寫，並重複足夠多次來減少干擾（程式碼）。嘗試判讀 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

• 週期 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 的討論。