# Dig into bits of Linux Kernel > 從數值系統出發，動手修改 Linux Kernel！ 專題成果報告，contributed by [NTHU CS 109062274 楊子慶](https://github.com/Shiritai)。 本專題的討論基於 Linux kernel 6.4.0 source code。 ```bash $ make kernelversion > 6.4.0-rc1 ``` 實驗環境於 intel i3-12100, OS: Ubuntu 22.04，使用 GCC 11.3.0 編譯。 |CPU|RAM|Disk|OS| |:-:|:-:|:-:|:-:| |Intel Core i3-12100 3.3GHz|16GB|512GB SSD|Ubuntu 22.04| ```bash $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i3-12100 CPU family: 6 Model: 151 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 5 CPU max MHz: 5500.0000 CPU min MHz: 800.0000 BogoMIPS: 6604.80 ``` ## 專題概述 本專題起於為了實現生成費氏數列之 Linux 核心模組 [`fibdrv`](https://github.com/Shiritai/fibdrv) 於超越 $64$ bits 數值範圍的費氏數實作，我從數值系統與位元運算出發，研究眾多位元運算的技巧，並以此為基礎實現確定性的 `clz`、`ctz` (count leading/tailing zero，後稱 `clz` 系列) 等函式，實驗表明本專題首創在不影響效能的情況下，利用前處理器實現客製化型別之 `clz` 系列函式的生成。 之後我進一步以 C 語言開發物件導向風格 (沒錯，C 語言做得到) 且兼顧大數運算與位元運算功能的資料結構與演算法 `inf_bits` (infinite bits)，最終希望與 [Linux mpi](https://github.com/torvalds/linux/tree/master/lib/mpi)、[sysprog21/bignum](https://github.com/sysprog21/bignum) 等大數運算函式庫進行效能比較，同時透過條件編譯，期望 `inf_bits` 在 User space 和 Linux kernel 內皆可編譯運行。 為了以地表最強編輯器 vscode 完成前述 `fibdrv`、`inf_bits` 等的開發，我以 Python + makefile 開發出 [`make2IntelliSense`](https://github.com/Shiritai/make2IntelliSense) 腳本，協助開發者以一行 `make` 指令設定好 vscode，以進行 kernel module 的開發。 與前述 `clz` 系列函式緊密相關的，Linux Kernel 中 [`bitops`](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 套件內也實作了相似的 `ffs`、`fls` (find first/last set) 系列函式，它們廣泛用於 Linux Kernel 的各個套件中，其中一個便是應用於 [CFS ](https://en.wikipedia.org/wiki/Completely_Fair_Scheduler) 的排程上。但經過 trace code 後發現其有諸多缺點，於是我利用前述 `clz` 系列函式、[`make2IntelliSense`](https://github.com/Shiritai/make2IntelliSense) 等研究成果，基於 Linux Kernel 6.4.0 [著手調整 `bitops` 套件](https://github.com/Shiritai/linux-bitops-patch)，並以 User Mode Linux (UML) 進行測試。待確認所有調整皆符合 Linux 的開發者社群規範後，預計將發起人生第一個 Patch，期待能在未來的 Linux kernel 中留下足跡。 簡言之，本專題由 0, 1 出發，目標是向 Linux Kernel 邁進。 ## 研究動機 初入 01 世界二年半載有餘，一開始便憧憬著 Linux kernel 這些資訊界乃至於全世界分工協作的曠世工程。但礙於實力不濟與轉學課業壓力而止步於瞻仰。而於清大資工系的訓練至今，有了資料結構、演算法、計算機結構和作業系統等基礎後，我決定透過專題的機會進一步向 Linux kernel 邁進。 向 Linux kernel 邁進的第一步是深厚扎實的 C 語言能力（當然，未來更需要 Rust 語言的精進），這包括但不限於清楚最基本的數值系統、函式呼叫與 ABI、前處理器技巧、編譯器，甚至物件導向風格之 C 語言技術，同時需擁有閱讀並應用 C 語言、GCC、Linux Manual 等規格書等的能力。沒有這些基本功就想探討 Linux kernel 的設計、實作與改善只能淪為妄言，於是我的專題便從這些基礎開始出發。 很感謝指導教授給予我充分自由研究的機會，讓我得以用旁聽的身份自行參與台灣知名的 Linux 核心實作課程。在盡可能的跟上該課程的教材與作業之餘，我以其中一份作業: `fibdrv` 這個生成費氏數的 kernel module 為引子，在研究並推導 fast doubling 演算法加速費氏數計算的原理後，嘗試實作該演算法，並希望透過 `clz`、`ctz` (count leading/tailing zero) 的技巧加速之，為此我開始研究 `clz` 系列函式的軟體和硬體實作。 針對其軟體實作，對於厭惡 Magic number 且對程式風格有一定程度堅持的資工系學生而言，當今常見的實作讓我的良心過意不去，滿坑滿谷的 Magic 與可讀性極差的風格。這讓我想到圖靈獎得主 Butler Lampson 所言： > All problems in computer science can be solved by another level of indirection. 於是我對程式碼進行抽象和使用前處理器的技巧實現正確、簡潔且高泛用性的軟體版 `clz` 系列實作，成功加速 fast doubling 演算法。更進一步的，由於起於 0 之費氏數於 $fib(93)$ 時將超越 `int64_t` 的範圍，為了實現更高項的費氏數，且鍛鍊自身數值系統的能力，我打算實現同時能進行大數運算與各式位元運算，包含前述 `clz` 系列運算的資料結構與演算法，命名為 `inf_bits`。 同時作為輔助，為了使用地表最強編輯器開發 Linux kernel module 乃至於未來的目標 Linux kernel，我著手研究 vscode 的各項設定，並希望以腳本的方式實作懶人式的一鍵準備好開發相關的環境設定，命名為 `make2IntelliSense`。 與前述 `clz` 系列運算相關的 Linux kernel 便是位於 `asm-generic/bitops` 底下的 `ffs` 系列運算。由於好奇 Kernel 開發者的實作手法，經過簡單的 trace code 後，愕然發現那部份的程式碼仍然活在劍與魔法的世界，讓我心中抱有一絲失望，不過這又讓我想到 Linus Torvalds 的那句名言： > I am not a visionary. I'm an engineer. I'm happy with the people who are wandering around looking at the stars but I am looking at the ground and I want to fix the pothole before I fall in. 也燃起路見不平，拿 Patch 來填的想法，著手開始更大範圍的 trace code 和實作調整，並將此 patch 的開發命名為 `bitops-patch`。 我的專題便是圍繞著數值系統與入門 Linux kernel 的一件又一件兼具理論與實作的問題。 ## 研究目標 目的即一句話：向 Linux kernel 邁進。為此衍伸出以下五個具體而微的子項目，彼此相互聯繫： * 費氏數演算法 Fast doubling 的理論、程式化與實作、效能分析。 * `clz` 系列運算的原理、實現與實驗。 * `inf_bits`: 實現兼具大數運算與位元運算功能 C 語言物件導向風格函式庫，力求對所有位元的極致使用。 * `make2IntelliSense`: 實現協助設定 vscode 開發 kernel module 乃至於 kernel 本身的腳本。 * `bitops-patch`: 改善 Linux kernel 中 `bitops` 的實作缺陷，實作並驗證從正確性、效能、可讀性、優雅程度等都與 Linux kernel 門當戶對的 patch，而後發起人生第一個 patch。 經過這些項目的歷練，我希望能正式入門資訊工程乃至於 Linux kernel 的世界。 ## Fast doubling 演算法的實作 ### 現有研究概況與比較 對於任意費氏數的計算，以下為常見的方法。 #### 樹狀遞迴版 即最原始的 top-down 費氏數遞迴計算演算法，遞迴關係描述如下。 $$ fib :: \mathbb{R} \rightarrow \mathbb{R} \\ fib(0) = 0 \\ ‍‍‍‍‍‍fib(1) = 1 \\ ‍‍‍‍‍‍fib(n+2) = fib(n+1) + fib(n) $$ #### 線性遞迴版 即 button-up 版的費氏數遞迴計算演算法，若為 top-down 追加記憶性質，亦可達到同樣的效率。 $$ fib2 :: \mathbb{R} \rightarrow (\mathbb{R}, \mathbb{R}) \\ fib2(0) = (0, 1) \\ ‍‍‍‍‍‍fib2(n+1) = (y, x + y) \\ where\ (x, y) = fib2(n) $$ #### 公式解: Binet’s Formula $$ \dfrac{1}{\sqrt{5}} \Big( \big( \dfrac{1 + \sqrt{5}}{2} \big)^n - \big( \dfrac{1 - \sqrt{5}}{2} \big)^n \Big) $$ 當中指數與根號運算造成的計算誤差和複雜度都不容小覷。[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number#%E8%A7%A3%E6%B1%BA%E9%81%8B%E7%AE%97%E7%B2%BE%E6%BA%96%E5%BA%A6%E7%9A%84%E5%95%8F%E9%A1%8C)一文使用 GNU 的 `GMP`, `MPFFR` 這倆透過盡情使用記憶體資源計算遞迴版 (下述分解法)和本公式解的運算時間，得到前者大勝後者的結果。 ### 設計原理 #### 分解法與 Fast Doubling > 最早可追溯至 [Nikolai. N. Vorobev 提出的方法](https://www.amazon.com/Fibonacci-Numbers-Dover-Books-Mathematics/dp/048648386X)。 由費氏數列的遞迴定義，也許你會猜測是否能尋找費氏數列中各項的關聯，分解法便是對此疑問的解答。令費氏數第 $n$ 項為 $f_n$，則 $$ f_{n+k} = f_{n-1} \cdot f_k + f_n \cdot f_{k+1} $$ 上式對 $n \ge 1, k \ge 0 \ \land n, k \in \mathbb{R}$ 成立。 如果根據費氏數列定義拆解此式，可以得到如回音般的結果。 $$ f_{n+k} = f_{n-1} \cdot f_k + f_n \cdot f_{k+1} \\ = f_{n-1} \cdot f_k + f_{n} \cdot \big( f_{k} + f_{k-1} \big) \\ = \big( f_{n-1} + f_{n} \big) \cdot f_{k} + f_n + f_{k-1} \\ = f_{n+1} \cdot f_k + f_n \cdot f_{k-1} $$ 這樣的結果與原本分解式的展開只差在 $n$ 和 $k$ 的互換。並不能給我們額外的結論，也許我們應該另尋其道。通常遇到這種難以直接證明的，我們可以用終極絕招數學歸納法: * Base case: 帶入即正確。 $$ f_{1} = f_{1+0} = f_{0} \cdot f_{0} + f_{1} \cdot f_{1} = f{1} = 1 $$ * Inductive case 假設分解式對 $t \le n$ 成立，則當 $t = n + 1$ 時，利用費氏數列的定義和 $t \le n$ 的情況，可得 $$ f_{(n+1)+k} \stackrel{\rm{def\ of\ fib}}{=} f_{n+k} + f_{(n-1)+k} \\ \stackrel{\rm{eq\ when\ }t \le n}{=} f_{n-1} \cdot f_k + f_n \cdot f_{k+1} + f_{n-2} \cdot f_k + f_{n-1} \cdot f_{k+1} \\ = \big( f_{n-1} + f_{n-2} \big) \cdot f_k + \big( f_{n} + f_{n-1} \big) \cdot f_{k+1} \\ \stackrel{\rm{def\ of\ fib}}{=} f_{n} \cdot f_k + f_{n+1} \cdot f_{k+1} $$ 由數學歸納法得證。 以分解法為基礎，今若要求 $f_{2n}$，有 $$ f_{2n} = f_{n+n} = f_{n-1} \cdot f_{n} + f_{n} \cdot f_{n+1} \\ = f_{n-1} \cdot f_{n} + f_{n} \cdot (f_{n} + f_{n-1}) \\ = f_{n-1} \cdot 2 f_{n} + f_{n} \cdot f_{n} = f_n \cdot (2f_{n-1} + f_{n}) $$ 可以發現 $f_{2n}$ 需要 $f_{n-1}, f_{n}$。那麼 $f_{2n-1}$ 呢？ $$ f_{2n-1} = f_{n+(n-1)} = f_{n-1} \cdot f_{n-1} + f_{n} \cdot f_{n} = f_{n-1}^2 + f_n^2 $$ 也需要 $f_{n-1}, f_{n}$，真好。 不過其實有其他做法，同樣考慮 $f_{2n}$，有 $$ f_{2n} \stackrel{\rm{prev\ result}}{=} f_n \cdot (2f_{n-1} + f_{n}) \\ = f_n \cdot (2f_{n+1} - f_{n}) $$ 由於我們透過合併改關注 $n+1$ 項，故改成考慮 $2n+1$ 項 $f_{2n+1}$，有 $$ f_{2n+1} = f_{(n+1)+n} = f_{n} \cdot f_{n} + f_{n+1} \cdot f_{n+1} = f_{n}^2 + f_{n+1}^2 $$ 後者的結論是 $f_{2n}$ 和 $f_{2n+1}$ 都需要 $f_n$ 和 $f_{n+1}$，是[原文](https://hackmd.io/@sysprog/fibonacci-number#Vorobev-%E7%AD%89%E5%BC%8F)中的方法，兩者的結果都很漂亮，畢竟是等價的東西。 以前者 ($f_{2n}$, $f_{2n-1}$ 需 $f_{n}, f_{n-1}$) 為例，取得二的冪就不是問題，假設我們想知道 $f_{16}$，可以藉由以下順序求得: ![](https://hackmd.io/_uploads/rJnMHT0E2.png) <!-- ```graphviz digraph twos_power { rankdir=LR; node[shape=record]; edge[arrowsize=0.5] 12[label="<b> f2|<a> f1"]; 34[label="<b> f4|<a> f3"]; 78[label="<b> f8|<a> f7"]; 16[label="f16"]; 12:a -> 34:a -> 78:a -> 16; 12:b -> 34:b -> 78:b -> 16; 12:a -> 34:b -> 78:a; 12:b -> 34:a -> 78:b; } ``` --> 繼續以前者為例，那如果是任意數呢？假設要計算 $f_{21} = f_{2n-1}$，我們需要 $f_n = f_{11}$ 和 $f_{n-1} = f_{10}$，為此我們還需要 $f_6, f_5$，同樣我們又需要 $f_3, f_2$, 最後回到 $f_2, f_1$ 便皆大歡喜。看來無論哪個正整數，都可以使用此演算法。下圖圖像化這段流程，與上圖不同在於稍作一點簡化。 ![](https://hackmd.io/_uploads/S1S4BTCNh.png) <!-- ```graphviz digraph flow_21 { rankdir=LR; node[shape=square]; 1[label="f2 \n f1"]; 2[label="f3 \n f2"]; 3[label="f6 \n f5"]; 4[label="f11 \n f10"]; 5[label="f22 \n f21"]; 1 -> 2 -> 3 -> 4 -> 5; } ``` --> 另外前述「前者」與「後者」的差異可透過上圖描述。前者是以數字大者 (比如 $[22, 21]$ 中的 $22$) 為主視角，後者則是以數字小者 ($[22, 21]$ 中的 $21$) 為主視角，兩者實際上會畫出一樣的關係圖。 #### Fast doubling 的程式化 根據前述演算法，下圖以 $f_{21}$ 為例，當初我們以 top-down 的角度分析，實作時勢必需要遞迴，如果不想使用遞迴呢？我們要如何知道接下來是單純從 $(5, 6)$ 爬兩倍到 $(10, 11)$，還是額外加一，從 $(2, 3)$ 到 $(5, 6)$？ ![](https://hackmd.io/_uploads/BytHBp04n.png) <!-- ```graphviz digraph flow_21 { rankdir=LR; node[shape=square]; subgraph 1 { 3[label="f6 \n f5"]; 4[label="f11 \n f10"]; 3 -> 4; } subgraph 2 { 1[label="f3 \n f2"]; 2[label="f6 \n f5"]; 1 -> 2; } } ``` --> 把之前的流程圖加上是否「加一」的標記：令以 $1$ 表加一，以 $0$ 表不加，同時將 $f_0, f_1$ 這個 trivial 項補回來... ![](https://hackmd.io/_uploads/rySwSpAE2.png) <!-- ```graphviz digraph flow_21 { rankdir=LR; node[shape=square]; 0[label="f1 \n f0"]; 1[label="f2 \n f1"]; 2[label="f3 \n f2"]; 3[label="f6 \n f5"]; 4[label="f11 \n f10"]; 5[label="f22 \n f21"]; 0 -> 1 [label="1"]; 1 -> 2 [label="0"]; 2 -> 3 [label="1"]; 3 -> 4 [label="0"]; 4 -> 5 [label="1"]; } ``` --> 敏銳的你想必已經觀察到了，標記的 $10101_{2}$ 不正是二進制版的 $21_{10}$ 嗎？這顯然不是巧合，因為前述問題實際上等價於: > 給定兩種操作：乘二、加一。 > 如何從 $0$ 開始用最少計算次數抵達某正整數 $n$？ 上述是在任意進位制的角度下問的問題，換成熟悉二進制與位元運算的你所熟悉的語言就是: > 給定兩種操作：左移一位、加一。 > 如何從 $0$ 開始用最少計算次數產生某二進制數 $n$？ 這一問等於白問，因為答案即藏在 $n$ 的二進制編碼！ ### 實作 #### Fast doubling 實作: version1 不考慮大數運算的情況下，針對 `long long`，為了實現 Fast doubling，首先須取得目標費波那契數的二進制編碼，接著由高至低走訪這些編碼完成乘二和加一的邏輯。 取得一個數字精確的二進制編碼，有以下兩個針對 `long long` 的 gcc 內建函式: 1. `__builtin_clzll`: 其在 intel x86_64 架構下可能使用硬體指令 bit search reverse 找尋首個 `1` bit，接著以 63 減去而取得領導的 `0` bit 數量。 2. `__builtin_ctzll` 同理在 intel x86_64 可能使用 bit search forward，最終取得末尾的 `0` bit 數量。 前者的使用可以加速略過領導之 `0` bits 的過程，後者則由於 fast doubling 的「加一與否」牽扯到 branching，而且很難直接避免而轉換成 branchless，不過若所有位元皆為零就不需顧慮 branch 操作，故可以透過後者完成末尾 `0` bits 的 branchless 乘二操作，同時降低 branching 時的比較開銷。 具體實作解釋如下。 1. 取得領導、末尾 `0` bits 數量，並調整 $f(n)$ 的 $n$，將領導的 `1` bit 上調至最高位元。 > 注意 `c{l,t}z_long_long` 為[自己實作的函式](https://hackmd.io/@Eroiko/fibdrv-impl)，以巨集控制編譯時要採用何者。 ```c= long long fn = 0ll, // f(n) fnp1 = 1ll; // f(n+1) n plus 1 #ifdef MY_CZ const int lz = clz_long_long(n); const int tz = ctz_long_long(n); #else const int lz = __builtin_clzll(n); const int tz = __builtin_ctzll(n); #endif /* MY_CZ */ n <<= lz; // so now there is no leading zeros ``` 2. Branching 部分: 根據當前最高位元，處理「乘二」和「是否加一」，注意到「乘二」的邏輯可使用 bitwise left shift 完成，且 branching 的條件只需考慮是否還有 `1` bit 的存在，即 $n$ 是否為零。 ```c= while (n) { // exists "1" bit long long f2n = fn * ((fnp1 << 1) - fn), f2np1 = fn * fn + fnp1 * fnp1; if (n & 0x8000000000000000ll) { fn = f2np1, fnp1 = f2np1 + f2n; } else { fn = f2n, fnp1 = f2np1; } n <<= 1; } ``` 3. Branchless 部分: 完成末尾 `0` bits 所代表之「乘二」邏輯。 ```c= // speed up for tailing zeros: branchless for (int i = 0; i < tz; ++i) { long long f2n = fn * ((fnp1 << 1) - fn), f2np1 = fn * fn + fnp1 * fnp1; fn = f2n, fnp1 = f2np1; } return fn; ``` #### Fast doubling 實作: version2 以下是取絕對值的極致軟體實作，其利用數值系統的特性規避了 branching： ```c int absWithoutBranching(int number) { // 對 number > 0 來說，mask = 0x00000000 (0) // 對負數來說， mask = 0xffffffff (-1) const int mask = number >> 31; // 二補數的「負數取正」為「減一後位元反轉」 // 對負數來說 // 加上 mask 相當於 -1，相當於「減一」 // 對 -1 = 0xffffffff 取 XOR 相當於「位元反轉」得到負數取正 // 對正數來說 // 加上 mask = 0 等於沒影響 // 對 0 取 XOR 相當於沒影響，保持原數 return (mask + number) ^ mask; } ``` 我採納此技巧，將原本的 branching 調整成 branchless，不過還是保留第三階段的 branchless，以達到效能的最大提升。以下展示原 branching 調整的部分。 ```diff while (n) { // exists "1" bit long long f2n = fn * ((fnp1 << 1) - fn), f2np1 = fn * fn + fnp1 * fnp1; + long long is_one = -!!(n & 0x8000000000000000ll); + fn = (f2np1 & is_one) + (f2n & ~is_one); + fnp1 = f2np1 + (f2n & is_one); - if (n & 0x8000000000000000ll) { - fn = f2np1, fnp1 = f2np1 + f2n; - } else { - fn = f2n, fnp1 = f2np1; - } n <<= 1; } ``` ### 實驗與效能評估 前述提供我的兩個實作，透過 perf 分析不做優化時計算 $fib(92)$ 的效能，執行一萬次下的平均: ||Ver1|Ver2| |:-:|:-:|:-:| |time|$0.000323559$<br>$\pm 0.000000303$|$0.000320931$<br>$\pm 0.000000296$| |IPC|1.22|1.28| |branches|149057|156423| |branch miss|3511|2513| 可見前後者 branch 數近乎相同，這是因為 $0\sim 92$ 間所有數字的 $1$ 其實也不多，兩者效能幾乎沒有明顯差距。後者雖然 IPC 較高，這可能是因為 `while` 迴圈內邏輯較複雜導致，但實際上並不會因此提速，因為部分計算是不會被採納的。 同時，該演算法的實作雖然適用於非 long long 型別，但假設導入大數運算，上述的一個簡單的加法或位元運算的開銷即不容小覷，故我們可以簡單得出版本一更適合大數運算版實作的結論。這便是一個即使將邏輯轉為 branchless 也不見得可獲得效能成長的例子。 另一個角度而言，對學過計算機結構的我們可能會聯想到調整成 branchless 的效益可能如下： * 降低 control hazard 於 pipeline CPU 下 Branch predictor unit 猜錯的負擔 * 影響因素可能有 Branch predictor、編譯器優化等 * 降低轉跳距離過長時 instruction cache miss 的負擔 對於本演算法，由於一個隨機給的位元為 `0` 或 `1` 的機率分別為 $\frac{1}{2}$，故很難利用編譯器與 branch predictor 得到效能提升。不過由於程式碼轉跳距離較低，或者説若用上大數運算必然發生難以迴避的函式轉跳，此時使用 branch 的負擔就不明顯，實務上不如強化大數運算效能較有明顯效益。 ### 貢獻與小結 針對 Fast doubling，本子項目提供從原理論述、演算法分析與圖示化，至實作、效能層面的分析。另外成為引發我實現與優化 `clz` 系列運算軟體實作的楔子。 ## `clz` 系列運算 ### 現有研究概況與比較 首先我定義 `clz` 系列函式有以下數個，當中 leading、tailing、first、last 的定義存在模糊空間，故標註其針對的是 MSB 抑或 LSB: * count leading zeros (MSB) * count tailing zeros (LSB) * find first set (LSB) * find last set (MSB) * find first zero (LSB) 他們針對不同的 * 輸入 * 輸出 * 未定義行為 而有不同的實作，都是需善用位元運算的例子。 #### 分析常見運用位元運算的函數 以下舉隅數個位元運算的經典應用。 * 二補數中 `x & (x - 1) == 0` 能判斷是否為二的冪 要說明原因，首先定義 `x` $$ x := \{X...X\}_{part2}1\{0...0\}_{part1} $$ 可推得 `x - 1` 後各個位元變成 $$ \rightarrow x - 1 = \{X...X\}_{part2}0\{1...1\}_{part1} $$ 其中 $\{\}$ 內兩部分的位元數前後相同。則 `x & (x - 1)` 為 $$ \{X...X\}_{part2}0\{0...0\}_{part1} $$ 與 `x` 相比，表去除最低位的 $1$。故 `x & (x - 1) == 0` 為真時，表示 $\{X...X\}_{part2}0\{0...0\}_{part1}$ 為零，也就是高位都為零。換言之，可用來判斷 $x$ 是否為二的冪。 * 以 XOR 調換數字 ``` a ^= b ^= a ^= b; // X= 從右邊結合 a ^= (b ^= (a ^= b)); // 配合下文標記說明 a'' ^= (b' ^= (a' ^= b)); ``` 以上成立是因為 XOR 的交換率，對位元 $a_n, b_n \forall n \in [0,bits-1]$ 而言，以上操作即 $$ a_n' = a_n \oplus b_n $$ $$ b_n' = b_n \oplus a_n' = b_n \oplus a_n \oplus b_n \\ = a_n \oplus b_n \oplus b_n = a_n \oplus 0 = a_n $$ $$ a_n'' = a_n' \oplus b_n' = (a_n \oplus b_n) \oplus (a_n) = b_n \oplus 0 = b_n $$ 故所有位元都得到交換，且全程 in-place，即不另外使用暫存器或記憶體。 * 避免溢位的相加除二 ```c (x & y) + ((x ^ y) >> 1) ``` 以上行為相當於模擬加法器：`x & y` 為「進位」，`x ^ y` 為「位元和」。再透過將後者右移一位，前者不左移而是留在原地，得到將加法結果除以二的值。 * (前面提及過的) 取絕對值 ```c int absWithoutBranching(int number) { // 對 number > 0 來說，mask = 0x00000000 (0) // 對負數來說， mask = 0xffffffff (-1) const int mask = number >> 31; // 二補數的「負數取正」為「減一後位元反轉」 // 對負數來說 // 加上 mask 相當於 -1，相當於「減一」 // 對 -1 = 0xffffffff 取 XOR 相當於「位元反轉」得到負數取正 // 對正數來說 // 加上 mask = 0 等於沒影響 // 對 0 取 XOR 相當於沒影響，保持原數 return (mask + number) ^ mask; } ``` * 位元反轉 ```c unsigned char reverse(unsigned char n) { n = (n & 0xF0) >> 4 | (n & 0x0F) << 4; n = (n & 0xCC) >> 2 | (n & 0x33) << 2; n = (n & 0xAA) >> 1 | (n & 0x55) << 1; return n; } ``` 實作原理十分精妙，讓我來分析其中原委。 要完成位元反轉，一種做法是對 $i$ 位位元，將其位移至 $7-i$ 位，對高 $4$ 位同理。也就是我們需要建立一個映射，使 $$ i \rightarrow 7 - i, \forall i \in \mathbb{N} \land \in [0, 7] $$ 對於 2 進制，我們可以看得更仔細： ```c (before: i) 000 001 010 011 100 101 110 111 (after: 7-i) 111 110 101 100 011 010 001 000 ``` 映射結果即原本位置二進制的 bitwise flip。實作上，對於 $i$ 位置位元，為 $0$ 時向 MSB 位移相應的距離，為 $1$ 時向 LSB。從組成 $7$ 之二進制數 $4$ 開始，位置 $4$ 為 $0$ 者向 MSB，位置 $4$ 為 $1$ 者向 LSB。 如果用 bit mask 來區別向 MSB 或向 LSB 的位元們的話，區別向 MSB 的 mask 應該長得像: $$ 0b00001111 = \tt{0x0F} $$ 同時區別向 LSB 的 mask 應該長得像: $$ 0b11110000 = \tt{0xF0} $$ 其他位置 ($2$, $1$) 同理，如此便解釋了前述玄妙的實作原理。 * 位元反轉變體 另一種常見的做法是查表：既然對於輸入 $n$ 對應的輸出只與 $n$ 有關，且 $n$ 本身只有 1 個 byte，選擇建表查詢也是好方法。 ```c static unsigned char table[16] = { 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, }; unsigned char reverse(unsigned char n) { return (table[n & 0b1111] << 4) | table[n >> 4]; } ``` 以位元運算所實作的函數們，各自有著不同的原理，實作出的函式與 naïve 相比，得益於硬體指令的加速與規避 branching、迴圈等操作，常常有明顯的增長。但另一個顯著的缺點是可讀性極差，撰成程式碼若不適度予以解釋便難以閱讀。 #### Count leading zeros 的實作 Count leading zeros 的實作五花八門，從最 naïve 的迴圈掃描，到利用 Harley’s algorithm、De Bruijn method，甚至利用如 `x86` 提供的 `bsr` 硬體指令等作法都有。 [本文](https://hackmd.io/rdTVGkmxSzyTGV9j05qZvw?view)連同兩種位元運算、迴圈版位元運算，甚至利用硬體指令的 `__builtin_clz` (gcc macro) 等六項不同的演算法進行說明與比較，結論是除了硬體指令之餘，位元運算版的實作為軟體實作中最高效的，而普通迴圈版是最慢的，儘管其相較之下程式碼中更少 Magic number。 #### Count leading zero 位元運算版的實作原理 這是經典的 `clz` 位元運算版實作。 ```c= int clz (int x){ if (x == 0) return 32; int n = 0; if ((x & 0xFFFF0000) == 0) {n += 16; x <<= 16;} if ((x & 0xFF000000) == 0) {n += 8; x <<= 8;} if ((x & 0xF0000000) == 0) {n += 4; x <<= 4;} if ((x & 0xC0000000) == 0) {n += 2; x <<= 2;} if ((x & 0x80000000) == 0) n += 1; return n; } ``` 想法是拿一把長度為二的冪的尺，從輸入 `x` 的最高位開始測量是否在尺的長度內為全零。若是，則認可這些 $0$ 並統計之，若否則不作調整，只管繼續換下一把二分之一長的尺，直到尺長度為一。 ### `clz` 系列函式的設計原理與研究步驟 方才提到位元運算的優缺點，可讀性低是其中一個缺點，另一個實務上明顯的缺點是，通常對於輸入輸出的型別有針對性。 又以前述取位元反轉為例，於 C/C++ 中，可見針對 `unsigned long long` 型別者為針對 `unsigned char` 實作的概念向上擴充，但 mask 的長度不同： ```c unsigned long long reverse_ull(unsigned long long n) { n = (n & 0xFFFFFFFF00000000) >> 32 | (n & 0x00000000FFFFFFFF) << 32; n = (n & 0xFFFF0000FFFF0000) >> 16 | (n & 0x0000FFFF0000FFFF) << 16; n = (n & 0xFF00FF00FF00FF00) >> 8 | (n & 0x00FF00FF00FF00FF) << 8; n = (n & 0xF0F0F0F0F0F0F0F0) >> 4 | (n & 0x0F0F0F0F0F0F0F0F) << 4; n = (n & 0xCCCCCCCCCCCCCCCC) >> 2 | (n & 0x3333333333333333) << 2; n = (n & 0xAAAAAAAAAAAAAAAA) >> 1 | (n & 0x5555555555555555) << 1; return n; } unsigned char reverse_char(unsigned char n) { n = (n & 0xF0) >> 4 | (n & 0x0F) << 4; n = (n & 0xCC) >> 2 | (n & 0x33) << 2; n = (n & 0xAA) >> 1 | (n & 0x55) << 1; return n; } ``` 若希望對所有感興趣的型別都實現位元反轉，我們就得實作大量重複的程式碼，這點實在令人揪心，也增加維護成本。舉例而言，由於 `clz` 系列函式存在 Undefined behavior (簡稱 UB)，若實作時不慎就有可能出現針對不同型別的 UB 處理不同的亂象。 另一個很有趣的現象是 `clz` 函式們彼此間的關係，以下式說明。 $$ \begin{cases} clz(x) = 64 - fls(x), & x > 0 \\ ctz(x) + 1 = ffs(x), & x > 0 \\ ffz(x) = ffs(\neg x) - 1, & x \ne \rm{all\ ones} \\ \end{cases} $$ 可見這些函式實際上可能只需實作 `clz/ctz` 或 `ffs/fls` 即可，其他函式只需調整一些即可。 於是問題就來了：針對 `clz` 運算，我希望能實作出效率如同位元運算實作，可讀性如同迴圈版實作，同時兼顧對不同型別的處理、統一未定義行為；針對 `clz` 系列運算，我又希望能根據它們彼此間的關係來實作，減少開發運營的成本。 我的做法是從 button-up 的角度分析位元運算版實作，一步步將 Magic Number 抽象出來，在不斷維持原功能的相容性下擴展功能，將於下一節介紹。 ### 實作 #### 調整成迴圈版，消除 Bad smell 我們從原本位元運算版的實作開始。 ```c= int clz (int x){ if (x == 0) return 32; int n = 0; if ((x & 0xFFFF0000) == 0) {n += 16; x <<= 16;} if ((x & 0xFF000000) == 0) {n += 8; x <<= 8;} if ((x & 0xF0000000) == 0) {n += 4; x <<= 4;} if ((x & 0xC0000000) == 0) {n += 2; x <<= 2;} if ((x & 0x80000000) == 0) n += 1; return n; } ``` 假設我們希望支援 `long long` 作為輸入，可能可以這樣調整： ```diff int clz_ll(long long x){ if (x == 0) return 64; int n = 0; + if ((x & 0xFFFFFFFF00000000) == 0) {n += 32; x <<= 32;} if ((x & 0xFFFF000000000000) == 0) {n += 16; x <<= 16;} if ((x & 0xFF00000000000000) == 0) {n += 8; x <<= 8;} if ((x & 0xF000000000000000) == 0) {n += 4; x <<= 4;} if ((x & 0xC000000000000000) == 0) {n += 2; x <<= 2;} if ((x & 0x8000000000000000) == 0) n += 1; return n; } ``` 計算時間一樣是確定的 (deterministic)，不過實在有失優雅。主要有三點: * `== 0` 邏輯可以簡化 * 近乎相同的位移、加法邏輯重複寫好幾遍，即 bad smell * 針對每個不同的型別都要重寫，明明內容都差不多，這又是 bad smell 第一點要調整可以採用 `!(x & __)`。第二點的做法可能根據考量點而有所不同，比如[此文提供一個很有趣的想法](https://stackoverflow.com/questions/45221914/number-of-trailing-zeroes)，考量最後一步的效能，他利用 bitwise 操作將分支與加法合併： ```diff - if ((x & 0x8000000000000000) == 0) n += 1; + n += (x & 1) ^ 1; ``` 若考慮消去 bad smell 的話，採用迴圈可能是更好的做法。雖然效能上可能會稍微降低，不過程式碼會變的簡潔易讀，且容易擴展。搭配前置處理器技巧，想擴展至更多型別便不是問題。 首先將函式調整成迴圈版，也就是歸納 magic number 的變化：分為過濾輸入 x 的 `mask` 和調整 x 每次經過 `if` 後的位移量 `shift`。 ```c= int clz(long long x){ if (x == 0) return 64; int n = 0; long long mask = 0xFFFFFFFF00000000; int shift = 32; while (shift) { if (!(x & mask)) { n += shift; x <<= shift; } shift >>= 1; mask <<= shift; } return n; } ``` 可以發現，透過改成迴圈版，我們將與 `long long` 型別有關的變因獨立在迴圈之前。 #### 引入前置處理器 承上，是不是調整這些變因就可以適用於其他型別呢？沒錯，並且搭配前置處理器，將程式碼的前段變成: ```c= #define __CZ_MAX_ONES 0xFFFFFFFFFFFFFFFF #define __clz(type, fn_name, bit_len, ones) \ static int fn_name(type x) \ { \ if (!x) \ return bit_len; \ int bits = 0; \ int shift = bit_len >> 1; \ type mask = (type) (ones << shift); \ /* ... */ /** * Macro to generate "count leading zeros" * for type which length is less than int64_t * Named: "name" */ #define clz(type, fn_name) \ __clz(type, fn_name, (sizeof(type) * 8), __CZ_MAX_ONES) ``` 中間使用一層隱藏層 `__clz` 是希望讓使用者能更加愉悅的使用，而不用重複傳遞隱含在 `type` 參數中的資料長度資訊。另注意到使用 `__CZ_MAX_ONES = 0xFFFFFFFFFFFFFFFF` 協助一開始 `mask` 的生成，長度為 $64$ bits，適應所有 $64$ bits 以內的函式邏輯。 如此一來，我們可以輕鬆產生長度在 $64$ bits 內的所有 `clz`，產生方法舉例如下: ```c= #include <stdint.h> clz(long long, my_long_long); ctz(long long, my_long_long); clz(int, my_int); clz(short, my_short); clz(char, my_char); clz(int8_t, my_int8); clz(int16_t, my_int16); clz(int32_t, my_int32); clz(int64_t, my_int64); clz(uint8_t, my_uint8); clz(uint16_t, my_uint16); clz(uint32_t, my_uint32); clz(uint64_t, my_uint64); ``` 上百行的函式就這麼樸實無華的產生了。`ctz` 同理，只要進行如下的調整： > 注意到 `ctz` 中第一個差異使用 `~` 而非反方向位移是因為右移與型別 (`type`) 的符號有關，對於有號數，全一再怎麼 (算數) 右移都是全一。 ```diff #define __ctz(type, fn_name, bit_len, ones) \ static int fn_name(type x) \ { \ if (!x) \ return bit_len; \ int bits = 0; \ int shift = bit_len >> 1; \ - type mask = (type) ones << shift; \ + type mask = (type) ~(ones << shift); \ while (shift) { \ if (!(x & mask)) { \ bits += shift; \ - x <<= shift; \ + x >>= shift; \ } \ shift >>= 1; \ - mask <<= shift; \ + mask >>= shift; \ } \ return bits; \ } ``` 如此，我們又可以使出四兩撥千斤之術生成 `ctz_XXX` 函式們，一勞永逸。 #### `ffs`、`fls` 和 `ffz` 我們可以用同樣的方法實現 `ffs` 和 `fls`，亦可直接對前述 `clz`、`ctz` 套一層皮完成實作。 不過有趣的是，`ffs` 和 `fls` 似乎比 `clz`、`ctz` 還常用，這點可見 `bitops-patch` 子項目的研究，當中討論到 Linux kernel 中實作的變體，我發現若以 `ffs`、`fls` 為首進行實作可以更簡單的統合 `clz` 全家桶，故調整新的實作如下 (節錄)，當中出現的新巨集 `__FFLS_START_INDEX_FROM_ZERO` 將於 `bitops-patch` 子項目介紹。 ```c #define __FFLS_START_INDEX_FROM_ZERO 0 #define __FFLS_START_INDEX_FROM_ONE 1 #define __gen_ffs(in_type, out_type, start_from, fn_name, bit_len) \ ... // just like ctz #define gen_ffs(in_type, out_type, start_from, fn_name) \ __gen_ffs(in_type, out_type, start_from, fn_name, (sizeof(in_type) * 8)) #define __gen_fls(in_type, out_type, start_from, fn_name, bit_len) \ ... // just like clz #define gen_fls(in_type, out_type, start_from, fn_name) \ __gen_fls(in_type, out_type, start_from, fn_name, (sizeof(in_type) * 8)) #define __gen_clz(in_type, out_type, fn_name, bit_len) \ __gen_fls(in_type, out_type, \ __FFLS_START_INDEX_FROM_ONE, \ __fls_##fn_name, bit_len); \ static __always_inline out_type fn_name(in_type x) \ { \ return bit_len - __fls_##fn_name(x); \ } #define gen_clz(in_type, out_type, fn_name) \ __gen_clz(in_type, out_type, fn_name, (sizeof(in_type) * 8)) #define gen_ctz(in_type, out_type, fn_name) \ __gen_ffs(in_type, out_type, \ __FFLS_START_INDEX_FROM_ZERO, \ fn_name, (sizeof(in_type) * 8)) ``` 他們的關係如下圖，方形表對面向使用者的函式，橢圓表巨集生成函式 (`__ffs`、`__fls`、`ffz`、`constant_fls` 等請見 `bitops-patch` 子項目)。 ![](https://hackmd.io/_uploads/B1pqS6043.png) <!-- ```graphviz digraph dg { graph[rankdir=BT]; gen_ffs; gen_fls; gen_clz; gen_ctz; ffs[shape=record]; fls[shape=record]; __ffs[shape=record];__fls[shape=record]; ffz[shape=record]; constant_fls[shape=record]; clz[shape=record]; ctz[shape=record]; __gen_clz -> __gen_fls; gen_fls -> __gen_fls; gen_ffs -> __gen_ffs; ffs -> gen_ffs; fls -> gen_fls; __ffs -> gen_ffs; __fls -> gen_fls; gen_clz -> __gen_clz; clz -> gen_clz; ctz -> gen_ctz; ffz -> __ffs; constant_fls -> gen_fls; gen_ctz -> __gen_ffs; } ``` --> ### 實驗 實驗方法有二，一是利用 perf 進行統計分析，二是編譯為組合語言分析上下文。 利用 perf 分析的程式如下： * 原位元運算版 (`clz_ll` 對照組為前述轉為迴圈版介紹的版本) ```c #pragma GCC push_options #pragma GCC optimize("O0") int main(void) { for (int i = 1; i < 1000000; ++i) { assert(__builtin_clzll(i) == clz_ll(i)); } } #pragma GCC pop_options ``` * 巨集迴圈版 ```c gen_clz(long long, int, my_clz_ll); // generate function int main(void) { for (int i = 1; i < 1000000; ++i) { assert(__builtin_clzll(i) == my_clz_ll(i)); } } ``` 兩者運算的結果皆需與 `__builtin_clzll` 進行比較，同時以 `#pragma` 關閉編譯器最佳化，以避免將整串程式碼於編譯時期計算完並優化掉。 編譯為組語使用的指令如下： ```bash cc main.c -O0 -std=c99 -S ``` ### 效能評估與成果 #### 效能影響 如果直接評估上述程式碼的效能，其實連實驗本身都不需做就知道巨集展開版必定遜於原版，畢竟多了額外判斷的額外負擔，也沒有因此增加 branch prediction 猜對機會等效果，以下實驗結果說明這個事實。 ||原位元運算版|巨集迴圈版| |:-:|:-:|:-:| |time|$0.0036428$<br>$\pm 0.0000107$|$0.0187004$<br>$\pm 0.0000165$| |IPC|4.40|1.28| |branches|11,167,018|15,163,749| |branch miss|2,990|5,182| 唯一的好處可能是生成的機器碼會比較短這點，將於下一小節探討。 #### 機器碼長度分析 以下以 `clz` 生成之組合語言為例，扣除處理輸入為零的邏輯，說明長度差異。 * 原位元運算版 ```python= testl $-65536, %edi jne .L9 sall $16, %edi movl $16, %eax .L9: testl $-16777216, %edi jne .L10 addl $8, %eax sall $8, %edi .L10: testl $-268435456, %edi jne .L11 addl $4, %eax sall $4, %edi .L11: testl $-1073741824, %edi jne .L12 addl $2, %eax sall $2, %edi .L12: cmpl $-2147483648, %edi adcl $0, %eax ``` * 巨集回圈版 ```python= movl $-65536, -12(%rbp) movl $16, -4(%rbp) movl $32, -8(%rbp) .L4: movl -20(%rbp), %eax andl -12(%rbp), %eax testl %eax, %eax jne .L3 movl -4(%rbp), %eax subl %eax, -8(%rbp) movl -4(%rbp), %eax movl %eax, %ecx sall %cl, -20(%rbp) .L3: sarl -4(%rbp) movl -4(%rbp), %eax movl %eax, %ecx sall %cl, -12(%rbp) cmpl $0, -4(%rbp) jne .L4 ``` 長度前者 22 行，後者 20 行，幾乎沒有差異。那對於 `long long` 型別的情況為何？以下省略組語，直接呈現行數： * 原位元運算版: 增為 33 行，除了多一個 case 外，各個 case 都多一個 `movabsq` 指令，[參考本文第七頁](https://www.lri.fr/~filliatr/ens/compil/x86-64.pdf)提到該指令是用來將立即數移至 64 位元暫存器。 * 巨集迴圈版: 變為 21 行，幾乎不變。 此實驗表明遇到 `long long` 下可能導致執行檔的增大，而較短之型別就不怎麼受影響，另外也取決於編譯時硬體提供的指令。 #### 如何迴圈化的副作用 迴圈化所帶來的副作用是顯著的，若又要馬跑又要馬吃草，現有於程式碼上的調整已經很難做到，但也並非束手無策。別忘了從高階語言至機器碼之間有神通廣大的編譯器的存在，其中一個鼎鼎大名的優化便是 loop unrolling：透過分析有限次數之迴圈並予以展開而提升效能。這部分的實作牽涉到更多與編譯器相關的細節，在此容我賣個關子，於 `bitops-patch` 子項目進一步討論。 ### 貢獻與小結 首先本項目分析了眾多得益於位元運算的高效實作，說明他們的原理、並討論使用位元運算的優缺點。之後以 `clz` 系列運算為例，透過將 Magic Numbers 抽象為迴圈，而後引入前置處理器，使我們能輕易生成針對不同資料型別的實作，並透過實驗說明這樣的做法可能帶來的副作用，也是後續可以持續優化的地方。 ## `inf_bits` ### 現有研究概況與比較 大數運算現有的研究與實作眾多，從最 naïve 的以整數陣列、字串陣列實作，到著名的有 [GNU 提供的 GMP](https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library)、[Linux 的 MPI (multiprecision maths library)](https://github.com/torvalds/linux/tree/master/lib/mpi)、[CPython 的 `libmpdec` 模組](https://github.com/python/cpython/tree/main/Modules/_decimal)等，另我旁聽之 Linux 核心實作課程中也提供了 [`sysprog21/bignum`](https://github.com/sysprog21/bignum) 這個實作。 關於大數運算的研究算較為透徹，由此存在著各式各樣的優化手法。比如運用 C++ `vector` 動態陣列的原理，為配置資料結構時多預留一些空間，降低頻繁配置記憶體的效能損耗。[Linux MPI](https://github.com/torvalds/linux/blob/master/include/linux/mpi.h) 就採用這樣的資料結構。另外對於乘法，採用 [Karatsuba algorithm](https://en.wikipedia.org/wiki/Karatsuba_algorithm) 是常見的做法。Linux MPI 便是一個例子，利用本演算法可以將乘法複雜度降低至 $$ \Theta(n^{\log_2{3}}), \rm{where\ } n \rm{\ is\ } 2^k \rm{\ for\ some\ integer\ } k $$ 更多激進的做法諸如於乘法中嵌入組合語言、使用 GCC 提供之 `__int128` 型別等，都是改善實作的好方法。 ### 設計原理 要實現大數運算函式庫談何容易，本子項目並不期待能在專題成果發表前完成所有實作與實驗。不過在深入瞭解位元運算與 trace 其他函式庫後，我發現有部分過去沒有被實現的優化空間，同時作為 `fibdrv` 的作業一部分，我希望能嘗試從頭設計一套資料結構與演算法，實踐我的觀察與想法。 以下幾點我認為是和常見實作不同的 * 資料結構的定義 * 紀錄使用到的 bits，限制運算時須顧慮的範圍 * 對於符號 (有號無號)，利用 Linux 紅黑樹的技巧隱藏於資料結構中，節省空間的使用 * 演算法的調整 * 由於已知使用位元的範圍，可以加速許多運算 * 乘法使用 lazy 方式建表加速 * 工程上的調整 * 善用前處理器，設計 Linux 風格的巨集並消滅 Magic number * 需維護使用位元的範圍 * 於部分位元運算下的調整與妥協 另外我手刻一套測試平台，同樣善用巨集與前處理器讓撰寫新測試時更為人性化，以下讓我娓娓道來這些細節。 #### 物件與成員 由於 64 bits CPU 硬體可以直接支援的資料長度最大為 64 bits，故起出設計時就採用 `uint64_t` 為資料儲存型別的首選，這與[改善方案 4: 善用 64 位元微處理器特性](https://hackmd.io/@sysprog/linux2023-fibdrv-d#%E6%94%B9%E5%96%84%E6%96%B9%E6%A1%88-4-%E5%96%84%E7%94%A8-64-%E4%BD%8D%E5%85%83%E5%BE%AE%E8%99%95%E7%90%86%E5%99%A8%E7%89%B9%E6%80%A7)不謀而合。 不過相較之下，我希望自己的 `__inf_bits` 直接模擬一串 bit string，可以以二補數的方式解釋並運算，而無需在意正負號，這點較為激進，但可以因此獲得二補數提供的一些優良性質。 對不同數字需要的位元數不同，故我以 `vector` 動態陣列資料結構的設計發想，設計 `capacity` 和 `use` 兩成員，分別為位元容量和使用位元數。特別注意 `use` 實際上與 [bignum](https://github.com/sysprog21/bignum/blob/master/bn.h) 不同，`use` 更進一步地表示「從最高位 `1` 以降，使用多少個位元」。另外為了提升多數運算的效能，我設計成員 `low`，表最低位之 `1` bit。 另外很有趣的是，對於 bit stream 的部分，我使用上課提及之[零長度陣列](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)的技巧設計物件。最終結構體定義如下。 ```c struct __inf_bits { int capacity; // bit capacity int use; // bit length using int low; // starting bit which is not zero ib_data_t arr[0]; // determines in runtime }; /** * A infinite bit stream container supporting many bitwise and arithmetic * operations */ typedef struct __inf_bits **inf_bits; ``` 特別注意到末行定義 `inf_bits` 為 `struct __inf_bits **` 作為出現在使用者面前的型別。之所以需要間接指標是因為 1. 物件中有零長度陣列，這意味著每次產生新物件時基本上都會呼叫 `malloc` 等函式分配記憶體，這使本物件至少要是指標型別。雖然也可以在 stack 記憶體上初始化，但這僅限使用者在自己的 scope 上使用，違反物件導向從物件的生成到死亡都由實作方完成的習慣。 2. 設計之 `inf_bits` 應支援 in place 操作，比如 in place 的左右移、單個位元的設定與加減法等。如果物件的實體只由普通指標管理，由於產生物件後 `arr` 成員的長度也確定下來，今若需改變長度，只有重新建立物件才行，此時舊的指標會被拋棄，那就需要想辦法讓使用者可以取得新的指標。對此，我們可以提高一層視角，使用指標的指標。第一層指向結構指標，第二層才是真的指向結構。這樣一來就可以讓使用者在不替換變數的情況下修改內部結構的長度。 ![](https://hackmd.io/_uploads/H1ihS6AV2.png) <!-- ```graphviz digraph { graph[rankdir=LR]; node[shape=record]; origin[label="inf_bits (struct __inf_bits **)"] content[label="old struct __inf_bits *"]; content2[label="new struct __inf_bits *"]; origin -> content[label="deallocate this"]; origin -> content2[label="allocate and link to new structure"]; } ``` --> #### 方法封裝結構 對外公開的方法使用結構體 `inf_bits_ops` 封裝，並留下一全域實例 `ib_methods` 以供使用者呼叫方法。 ```c // in file __inf_bits.h /** * inf_bits is a infinite bit stream supporting * many bitwise and arithmetic operations such as * addition, subtraction and left/right shift * * Support multiplication in simulative way */ struct inf_bits_ops { /* ... */ } /** * Methods of inf_bits object * * Initialize ib_methods by calling inf_bits_init() */ extern struct inf_bits_ops ib_methods; ``` 與[你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHJLyQaQMl)中 stack 的設計不同的是，我將成員與方法分成兩個結構體，是因為將 function pointer 嵌入實例會消耗額外的空間，故獨立出來使用。以下提供用例: ```c inf_bits bn = ib_methods.construct(0xffffffff); // new inf_bits ib_methods.show_hex(bn); // print ib_methods.left_shift_in_place(bn, 3); // left shift ib_methods.show_hex(bn); // print ib_methods.finalize(bn); // delete ``` #### 封裝 物件導向一大特色即封裝，規定成員與方法的私有性來避免用戶不正當的使用物件。我不知道 C 語言要使成員私有化應如何完成，不過方法的私有化倒不難。利用 `static` 關鍵字便可編譯出僅檔案內部知曉函式位置的 object file。使用者透過呼叫我為 `__inf_bits.h` 留下的函式 `inf_bits_init` (實作於 `__inf_bits.c`) 初始化 `ib_methods` 的成員函式指標們，將 `__inf_bits.c` 中想提供給使用者調用的函式位置記在 `ib_methods` 內，使用者便能正常的呼叫方法。 ```c // in __inf_bits.h void inf_bits_init(); // in __inf_bits.c struct inf_bits_ops ib_methods; void inf_bits_init() { ib_methods = (struct inf_bits_ops){ .construct = construct, .finalize = finalize, .show_hex = show_hex, /* ... */ } } ``` ### 實作與部分小實驗 接下來才是重頭戲：盡可能高效的~~使用奇技淫巧~~實現眾多方法，並測試其正確性。 #### 實作前的準備 後續將會使用大量 bitwise 操作，自然會用到很多神奇的位移量、各種常數和 mask。可以預期如果這些 Magic number 充斥整份程式碼，未來調整時將多麽痛苦。為了防止該慘劇，我先定義很可能常用的常數，預期是消滅所有魔法。 ```c #define __BITS_IN_BYTE 8 #define __BITS_IN_ULL (sizeof(ib_data_t) * __BITS_IN_BYTE) /** * Offset of ULL from 0: i.e. (bits of ULL) - 1 */ #define __ULL_OFFSET (__BITS_IN_ULL - 1) /** * Default 4 words, 2 long long */ #define __DEFAULT_ULL_LEN 2 #define __ULL_ONES ((ib_data_t) ~0) #define __LOG_BITS_IN_ULL (LOG2(__BITS_IN_ULL)) ``` 可以注意到當中使用 `LOG2` 巨集，其引自[數值系統](https://hackmd.io/@sysprog/c-numerics#Count-Leading-Zero)的介紹。另外受 Linux 中 `list_head` API 的啟發，我定義數個巨集函式，讓諸多位元運算的意義一目瞭然，以下舉最重要的兩例。 ```c /** * Get index limit (upper bound) of given __inf_bits instance * Round up */ #define ib_up_index(bits) \ (((bits) >> __LOG_BITS_IN_ULL) + !!((bits) & __ULL_OFFSET)) /** * Get index base (lower bound) of given __inf_bits instance * Round down */ #define ib_dn_index(bits) ((bits) >> __LOG_BITS_IN_ULL) ``` `ib_up_index` 的意義在給定位元數 $bits$，得到可包含該所有位元的 `ib_data_t` 數。比如有 $65$ 個位元，那便需要 $2$ 個 `unsigned long long` 才能裝得下。 該巨集的實作為 `(((bits) >> __LOG_BITS_IN_ULL) + !!((bits) & __ULL_OFFSET))`，分為前後兩段。前者相當於對 `ib_data_t` 的長度進行整數除法，後者為確認餘數是否非零，非零則透過 `!!` 轉為 `1`。 #### 物件生命週期相關方法 下圖所有 in-degree 為零的節點都是公開方法。 ![](https://hackmd.io/_uploads/HJ10BaRE3.png) <!-- ```graphviz digraph DG { graph[rankdir=BT]; __ib_malloc[label="__ib_malloc (malloc)"]; __ib_free[label="__ib_free (free)"]; construct -> __ib_new -> __ib_malloc; construct -> __ib_malloc; finalize -> __finalize; finalize -> __ib_free; __finalize -> __ib_free; copy -> ib_copy -> inner_copy -> __ib_new; ib_copy -> __ib_malloc; assign; expand -> inner_copy; expand -> __ib_free; } ``` --> ##### 配置與釋放 `__ib_malloc` 和 `__ib_free` 的來歷請見[依賴函式庫議題](https://hackmd.io/@Eroiko/from-bits-to-kernel#%E4%BE%9D%E8%B3%B4%E5%87%BD%E5%BC%8F%E5%BA%AB%E8%AD%B0%E9%A1%8C%E8%88%87%E5%88%9D%E6%AD%A5%E8%A7%A3%E6%B3%95)，可簡單視為 `malloc` 和 `free`，可以配置、釋放 pointer 或 pointer-to-pointer。`__ib_new` 和 `__finalize` 這兩個很 C++ 味的私有方法負責完成 pointer (`struct __inf_bits` 本體) 的配置、釋放，並調整 `capacity` 成員。`construct` 和 `finalize` 則是簡化參數，並將 pointer 和 pointer-to-pointer 的配置與釋放包在一起，開放給用戶簡潔的方法。以下舉 `__ib_new` 這個配置 `struct __inf_bits` 本體的私有方法為例，可見其利用巨集函式增加使用 bitwise 操作的可讀性。 ```c // implementation of private method "__ib_new" const int sz = sizeof(struct __inf_bits) + ib_ull_as_bytes(num_ull); struct __inf_bits *ret = __ib_malloc(sz); memset(ret, 0, sz); ret->capacity = ib_ull_as_bits(num_ull); return ret; ``` ##### 複製與所有權共享 (i.e. deep copy and shallow copy) 記憶體管理中，複製物件是一個重要的議題。由於希望對內設計的邏輯盡可能不要重複且功能充足，對外簡單明瞭而無需知道細節。首先是 `inner_copy`，負責處物件本體的複製，`ib_copy` 將其包裝間接指標，`copy` 則隱藏 `ib_copy` 不必要公開的參數，讓使用者傳入舊的 `inf_bits` 即可。 ```c // implementation of public method "copy" return ib_copy(self, ib_up_index((*self)->use)); ``` `assign` 對外的意義為複製參考，也就是讓新的 `inf_bits` 共享舊的 `inf_bits` 的所有權 (並不會轉移)，以費氏數列的計算為例，使用方法如下。 ```c // in test.c::dump_fib, i.e. user perspective // doing (a, b) = (a + b, a) inf_bits a_ = ib_methods.copy(a); // a_ = a ib_methods.add_in_place(a, b); // a += b ib_methods.finalize(b); // deconstruct b // void assign(struct __inf_bits ***dest, struct __inf_bits **src) // notice that inf_bits is struct __inf_bits ** ib_methods.assign(&b, a_); // b = a_ ``` 實作上，由於要確保 1. 修改 `dest` 的值 2. 不修改也不釋放 `dest` 內部的物件，因為不確定是否有其他 pointer-to-pointer 持有之 3. 不修改 `src` 及其內部物件的值 可見 `dest` 需為 pointer-to-pointer 的地址，也就是 `***`；`src` 則保持 pointer-to-pointer 即可。而實作僅一行 ```c // implementation of public method "assign" *dest = src; ``` 另外擴容的私有方法 `expand` 相對簡單，就不介紹了。 #### 輸出方法 提供的方法有二：`show_hex` 和 `dump`，皆為公開方法，前者輸出所有成員 (Metadata) 和 16 進制的 bit stream 內容，每 $64$ 位元以 `_` 隔開；後者將 16 進制的 bit stream 內容寫入指定檔案。 以下以 `show_hex` 為例，當中 format string 使用將 `i` 非零時轉成 `1` 的技巧來存取字元陣列；同時由於[依賴函式庫的議題](https://hackmd.io/@Eroiko/from-bits-to-kernel#%E4%BE%9D%E8%B3%B4%E5%87%BD%E5%BC%8F%E5%BA%AB%E8%AD%B0%E9%A1%8C%E8%88%87%E5%88%9D%E6%AD%A5%E8%A7%A3%E6%B3%95)，印出使用的 `__ib_print` 將由適當的函式取代。 ```c // implementation of public method "show_hex" __ib_print( "[Metadata] addr: %p cap: %d, use %d, low: %d\n[Data] addr: %p, arr: ", &(*self)->capacity, (*self)->capacity, (*self)->use, (*self)->low, (*self)->arr); int cap_ull = ib_up_index((*self)->capacity); for (int i = cap_ull - 1; i >= 0; --i) __ib_print("%016lx%c", (*self)->arr[i], "\n_"[!!i]); ``` #### Zeros 相關方法與特殊情況 Zero 相關方法對效能乃至於正確性而言至關重要。一旦平時維護 `use`、`low` 兩成員，即可在各式計算過程中略過大量未使用的位元，增加幾乎所有運算的效率。維護所需的成本在不同方法中有所不同。Worse case 複雜度與位元數成正比，`__ib_c{l,t}z` 私有方法正是在最糟情況下維護該成員們的手段。 ![](https://hackmd.io/_uploads/Bk7IqKySh.png) <!-- ```graphviz digraph dg { graph[rankdir=BT] ib_clz; ib_ctz; __ib_clz; __ib_ctz; refresh -> __ib_clz -> ib_clz; refresh -> __ib_ctz -> ib_ctz; ib_clz -> __ib_clz[style=dashed, color=gray]; ib_ctz -> __ib_ctz[style=dashed, color=gray]; is_zero -> __ib_clz[style=dashed, color=gray]; is_zero -> __ib_ctz[style=dashed, color=gray]; } ``` --> 上圖中 in-degree 為零者為公開方法。有了 `use` 和 `low` 成員，`is_zero` 的實作便僅需一行。 ```c // implementation of public method "is_zero" return (*self)->use == (*self)->low; ``` #### Counting Zero 實作的根源是 [Counting Zero 的實作](/qwJmNVgBTnyvz-z8swc6Jg#Count-leading-zeros-%E5%AF%A6%E4%BD%9C)中我使用的生成技巧，搭配以下兩行完成函式的生成: ```c clz(ib_data_t, ib_data); // clz_ib_data ctz(ib_data_t, ib_data); // ctz_ib_data ``` 便能使用。亦可使用 `__builtin_c{l,t}zll`，不過要注意輸入為零時存在的 undefined behavior，我同時採用這兩者，根據條件編譯決定要如何使用，預計用於效能測試。以下舉 `__ib_clz` 為例，可見 `__builtin_c{l,t}z` 的版本稍微比較不美觀一點。 以下為版本一，branching 判斷 `(*self)->arr[i]` 是否為零: ```c // implementation of private method "__ib_clz" int cap_ull = ib_up_index((*self)->capacity); int res = 0, i = cap_ull; do { --i; #ifdef MY_CZ res += clz_ib_data((*self)->arr[i]); #else if ((*self)->arr[i]) res += __builtin_clzll((*self)->arr[i]); else // avoid undefined behavior res += __BITS_IN_ULL; #endif } while (i > 0 && !(*self)->arr[i]); // automatically refresh use member (*self)->use = (*self)->capacity - res; return res; ``` 為了避免 branching，我實現以下版本，利用將 $0, 1$ 映射為全一、全零的技巧實現。 ```diff #else + ib_data_t _is_zero = !(*self)->arr[i]; + res += -!_is_zero & __builtin_clzll((*self)->arr[i]) + -_is_zero & __BITS_IN_ULL; - if ((*self)->arr[i]) - res += __builtin_clzll((*self)->arr[i]); - else // avoid undefined behavior - res += __BITS_IN_ULL; #endif ``` 經過 `__ib_c{l,t}z` 方法調整 `use` 和 `low` 成員後，`ib_c{l,t}z` 便能直接取用結果回傳。 ```c // implementation of public method "ib_clz" /** * Happily we've maintained capacity and use, * just use them directly :) */ return (*self)->capacity - (*self)->use; ``` 另由於我將 branching 改為 branchless，自然會想做實驗確認前後的差異，我以本文最前方的開發環境，以 `cc -O2 -std=c99 -S __inf_bits.c` 編譯得到 `x86` 組語，擷取重點如下: * Version 1 (branch in loop) ```python= .L70: movq 8(%rdi,%rdx,8), %rax testq %rax, %rax je .L68 bsrq %rax, %rax xorq $63, %rax addl %eax, %ecx .L69: subl %ecx, %esi movl %esi, 4(%rdi) ret .L68: subq $1, %rdx addl $64, %ecx testl %edx, %edx jg .L70 jmp .L69 ``` 迴圈的範圍很詭異，竟然是 `.L68` 和 `.L70` 之間來回跳，`.L69` 則是收尾回傳。 * Version 2 (branchless in loop) ```python= .L69: movq 16(%r9,%rcx,8), %rax testq %rax, %rax sete %sil bsrq %rax, %rdx xorq $63, %rdx movzbl %sil, %r8d negq %rax sbbl %eax, %eax subl %r8d, %edx andl %edx, %eax andl $64, %eax addl %eax, %edi testl %ecx, %ecx setg %al subq $1, %rcx testb %sil, %al jne .L69 subl %edi, %r10d movl %r10d, 4(%r9) ret ``` 迴圈的範圍很容易界定，於第 18 行跳回第 1 行就是，其餘地方沒有出現轉跳。另外可見 `__builtin_clzll` 對應的 x86 `bsrq` 指令於第 5 行。 上方實驗可見 branchless 版與 branching 版行數相近，不過有趣的是 branching 版的實際上說明我的程式碼依然有改善的空間: 編譯器意識到只有當 `(*self)->arr[i]` 為零時，迴圈才會繼續，可以發現 branching 版只會呼叫 `bsrq` 指令一次！ 這讓我大開眼界：表示我還能再優化！因為隨機情況下 `(*self)->arr[i]` 為零的機會比較小，故編譯器為我以 `likely non zero` 的方式安排組語，實際上這不一定與現實相同。考慮當 `inf_bits` 進行一定程度的加減乘法後，leading zero 可能會比想像的多，此時若以 `unlikely` 的邏輯安排有機會增加效率；於此同時，安排為 `unlikely` 的話程式只會轉跳一次後便結束函式，可以預期最多僅有一次回圈內轉跳。 於是 Version 3 登場，原本的迴圈變為以下: ```c while (--i >= 0 && !(*self)->arr[i]) ++res; #ifdef MY_CZ res = (res << __LOG_BITS_IN_ULL) + clz_ib_data((*self)->arr[i]); #else res = (res << __LOG_BITS_IN_ULL) + __builtin_clzll((*self)->arr[i]); #endif ``` 對應的迴圈部分組合語言如下: ```c= .L38: addl $1, %eax .L36: subl $1, %edx js .L37 movslq %edx, %rcx cmpq $0, 16(%rsi,%rcx,8) je .L38 .L37: sall $6, %eax movslq %edx, %rdx bsrq 16(%rsi,%rdx,8), %rdx xorq $63, %rdx addl %edx, %eax subl %eax, %edi movl %edi, 4(%rsi) ret ``` 與原本 Version 1 相比，Version 3 只在 `.L38` 間來回跳，不像原本在兩個 tag 間來回跳。且回圈內的指令變的更加簡單、轉跳距離也更近，應該是更為理想的程式碼。 ##### Refresh 方法與成員的維護 另外針對 `refresh` 需要特別說明，該方法有兩種不同的簽名註解。 ```c // in __inf_bits.c (implementation) /** * Refresh "use", "low" members * If you're not maintain "use" and "low", * please call this method to make sure __inf_bits works correctly */ // p.s. the implementation is: __ib_clz(self); __ib_ctz(self); // in __inf_bits.h (user perspective) /** * Refresh members * Call this method to make sure __inf_bits works correctly * after using single bitwise operations */ ``` 對內 `refresh` 方法用途多多，當進行某運算後難以直接維護 `use` 或 `low`，便可呼叫來以 $O(\#\ of\ bn\_data\_t)$ 複雜度重新維護之。對外原本理當盡可能不暴露此方法，但礙於[單個位元運算](#%E5%96%AE%E5%80%8B%E4%BD%8D%E5%85%83%E9%81%8B%E7%AE%97)中所有操作複雜度都是 $O(1)$，但若要維護該兩成員的話複雜度只能變為 $O(\#\ of\ bn\_data\_t)$，實在划不來。所以權衡一下，將此方法暴露於外，並在所有單個位元運算的簽名註解中加上提示，以 `mark` 方法為例。 ```c /** * Note: Always call "refresh" method to make sure __inf_bits is ready for * non-single-bitwise operations after using single bit operations * * Set a bit at "which" position * Does nothing if "which" is out of range */ void (*mark)(inf_bits, int); ``` #### 單個位元運算 `mark`, `clear`, `flip` 和 `test` 四個方法大同小異，複雜度皆為 $O(1)$。參考[你所不知道的 C 語言：數值系統](https://hackmd.io/@sysprog/c-numerics)和[數值系統閱讀紀錄](https://hackmd.io/y_jVeGzDQhetNS6A-XxPmA#%E4%BD%8D%E5%85%83%E7%B4%B0%E7%B7%BB%E6%93%8D%E4%BD%9C)，後者筆記正好用到前者針對 bitstream 的擴展： ```c // void Bitmap::Mark(int which) map[which / BitsInWord] |= 1 << (which % BitsInWord); ``` 為了避免除法跟取餘數，我改善此實作為 ```c // implementation of public method "mark" (*self)->arr[ib_dn_index(which)] |= 1ULL << (which & __ULL_OFFSET); ``` 當中利用 bitwise 操作進行除法和取餘數，並利用巨集改善可讀性與消滅 Magic Number。 #### 位移運算 i.e. `>>`, `>>=`, `<<`, `<<=` 與其變體。 ![](https://hackmd.io/_uploads/HyYbLaAE2.png) <!-- ```graphviz digraph dg { graph[rankdir=BT]; left_shift -> left_shift_in_place; left_long_shift -> left_long_shift_in_place; left_arb_shift -> left_arb_shift_in_place; left_arb_shift_in_place -> left_shift_in_place; left_arb_shift_in_place -> left_long_shift_in_place; right_shift -> right_shift_in_place; right_long_shift -> right_long_shift_in_place; right_arb_shift -> right_arb_shift_in_place; right_arb_shift_in_place -> right_shift_in_place; right_arb_shift_in_place -> right_long_shift_in_place; } ``` --> 圖看似複雜，實則為 * 有無 `_in_place` (無 `_in_place` 的方法直接依賴 `_in_place` 者) * 實作為複製一份後執行 `_in_place` 版 * 有 `_long` 表位移單位為 `ib_data_t`，沒有表位移單位為 $bits$ * 位移量在 $[0, 64)$ 之間 * `_arb` 表位移量為任意非負整數 想必讀者已經猜到 `_arb` 的實作就是有無 `_long` 的套皮。目前以上全部皆為公開方法，未來考慮只公開有 `_arb` 的版本，功能最強大且隱藏不必要的細節 (`ib_data_t` 的長度)。 實作上大量利用 bitwise 操作，舉例如下。 ```c // inside implementation of "left_shift_in_place" // after init local variables and handle "expand" case // special case ib_data_t carry = n_bn->arr[use_ull - 1] >> (__BITS_IN_ULL - shift); n_bn->arr[use_ull - 1] <<= shift; if (use_ull < ib_dn_index(n_bn->capacity)) n_bn->arr[use_ull] |= carry; // append carrying bits for (int i = use_ull - 2; i >= low_ull; --i) { ib_data_t carry = n_bn->arr[i] >> (__BITS_IN_ULL - shift); n_bn->arr[i] <<= shift; n_bn->arr[i + 1] |= carry; // append carrying bits } ``` `left_shift_in_place` 中 in place 的左移為了避免覆蓋未位移的資料，必須從高位開始，不過需考慮最高索引的特殊情況，故獨立 4~7 行於迴圈之外。 迴圈內先取得要移至高位的 `carry`，注意到在 `shift` 範圍為 $[0, 64)$ 的條件下，左移 `shift` 位元至更高位的取值即往右移 `__BITS_IN_ULL - shift` 位的結果。 對於 `use` 和 `low` 成員的維護，`left_shift` 系列非常容易做到，只要增加對應的數值即可；`right_shift` 則不然，要考慮位移可能超過使用量而導致最後的值為負數。 另我使用以下技巧完成**無分支**的 $\max(num, 0)$ 的邏輯。 ```c // inside implementation of "right_shift_in_place" // bitwise max(use, 0) n_bn->use -= shift; n_bn->use &= -!(n_bn->use < 0); ``` * 當 `use` 為正數或零，`!(use < 0)` 為 `1`，取負數為 `0xFFFFFFFF (-1)`，拿去 `&=` 後不改變值。 * 當 `use` 為負數，`!(use < 0)` 為 `0`，取負數為 `0 (-0)`，拿去 `&=` 後將數值設為零。 #### 加減法與相關運算 i.e. `++`, `--`, `+`, `+=`, `-`，注意沒有 `-=`，因為我的實作方式無法做到 in place 的減法。 ![](https://hackmd.io/_uploads/SyZXU604n.png) <!-- ```graphviz digraph dg { graph[rankdir=BT]; increment; decrement; add -> add_in_place; sub -> ib_minus; ib_minus -> minus_in_place; sub -> add_in_place; minus -> ib_minus; } ``` --> 上圖中，`ib_minus` 是為了隱藏 `minus` 不必要暴露的參數，功能上相當於 `-num`；實作減法利用到加法跟取加法反元素 (`ib_minus`) 的特色。另外由於 `minus_in_place` 的簽名沒有暴露內部的實作，且有公開的意義，故直接作為公開方法，其餘都是 in-degree 為零的節點才是公開方法。 ##### increment `++` 的實作是 `+=` 的縮影，經依樣畫葫蘆後也能實作出 `--`。分為三步: 1. 加法 由於僅需 $+1$，利用 `carry` 技巧性地把進位變成迴圈的進行與否與 `carry` 值掛鉤，並利用邏輯判斷來更新 `carry` 的值。 ```c const int lim = ib_up_index((*self)->capacity); _Bool carry = 1; for (int i = 0; carry && i < lim; ++i) { carry = (*self)->arr[i] == __ULL_ONES; ++(*self)->arr[i]; } ``` 2. 額外進位: 擴展位元的例外 上述加法沒有考慮位元溢位與否，由於我們的目標是任意位元的 bit stream，溢位時必須擴展。注意需擴展與否一事難以事先得知 (或者說事先得知的效率很低)，而且僅有唯一情況：所有位元為 `1`，故只需針對此例外單獨處理即可。 ```c if (carry) { // overflow, but we're arbitrary bit stream! expand(self, lim + 1); (*self)->arr[lim] = 1; } ``` 3. 調整 `use`、`low` 注意事先得知 `use` 和 `low` 要如何改變，基本上只能等加完才知道 (或者低效的掃描一遍所有位元)，不好直接維護，故直接呼叫 `refresh` 更實在。 ```c refresh(self); ``` ##### decrement 與 [increment](#increment) 類似，特別的是不用考慮借位不夠借的問題，因為本 bit stream 直接模擬二補數的行為。 ```c // implementation of public method "decrement" const int lim = ib_up_index((*self)->capacity); _Bool borrow = 1; for (int i = 0; borrow && i < lim; ++i) { borrow = (*self)->arr[i] == 0; --(*self)->arr[i]; } // it's ok for twos complement that borrow is now true refresh(self); ``` ##### 加法流程變化 流程與 [increment](#increment) 很相似，但改為提前檢測加法前後是否隱含擴展。 考慮二進制加法，只有當被加數與加數位元數相等時才必然進位。原因說明如下: 1. 說明最高位相等時會進位 考慮 edge case: 僅最高位為一即可。 ```c 1000...0000 +) 1000...0000 --------------- 1000...00000 ``` 最高位相等的條件下，最難進位的兩數相加，即乘二，結果是左移一位。 2. 說明最高位相等最多進一位 考慮 edge case: 全一即可。 ```c 1111...1111 +) 1111...1111 --------------- 1111...11110 ``` 最高位相等的條件下，最可能進位的兩數相加，即乘二，結果是左移一位。 利用 `capacity` 和 `use` 成員，是否需要擴展可以快速決定，故將隱含的擴展提至加法運算前。 ##### 加法技巧 在加法運算的迴圈中可以看到如下的技巧，當中 `mask` 為 `0x7fffffffffffffff`，此技巧是為了擷取「進位」。 ```c // inside implementation of "add_in_place" _Bool carry = 0; const ib_data_t mask = ~(1ULL << __ULL_OFFSET); for (int i = low_b_ull; i < use_b_ull; ++i) { // add b // addition with carry bit detection ib_data_t tmp = ((*a)->arr[i] & mask) + ((*b)->arr[i] & mask) + carry; // highest two bits ib_data_t msb2 = ((*a)->arr[i] >> __ULL_OFFSET) + ((*b)->arr[i] >> __ULL_OFFSET) + (tmp >> __ULL_OFFSET); (*a)->arr[i] = (tmp & mask) | ((msb2 & 1) << __ULL_OFFSET); carry = msb2 >> 1; } ``` 針對每組 `ib_data_t`，考慮[加法流程變化](https://hackmd.io/ajmUBopQTdKHlU_KyQbUiw?both#%E5%8A%A0%E6%B3%95%E6%B5%81%E7%A8%8B%E8%AE%8A%E5%8C%96)對加法的簡單分析，得知相同的最高位決定「兩個」二進制數是否進位。雖然加法過程中有另一 `carry` 的存在，不過 `carry` 最高為 1，不影響前面的推論。 我使用 bitwise 操作過濾最高位元，`tmp` 即忽略最高位元的加法，其值不溢位。 > 因為考慮極端情況: > > ```c > 0111...1111 > 0111...1111 > +) 1 > --------------- > 111...11111 > ``` 第九行針對最高為進行加法後，以 or 運算將低 63 位和最高位 (`msb2` 之最低位) 的加法結果合併；新的 `carry` 便是 `msb2` 次低位，利用左移方能適應次低位為 0 或 1 兩種情況。 ##### Minus: additive inverse 由於本 bit stream 實現的是二補數的運算，那麼便可以利用對某元素的減法為加上加法反元素的特性完成減法實作，為此衍伸出 `minus` 系列方法。 實作上與正常的加法器有點像，由低位起將一個 `ib_data_t` 內容 flip 與加一；另外 `use` 和 `low` 兩成員難以事先確認，故在最後需呼叫 `refresh`。 ```c // implementation of public method "minus_in_place" const int cap_ull = ib_up_index((*a)->capacity); _Bool carry = 1; // default add one for (int i = 0; i < cap_ull; ++i) { // negate and add one (*a)->arr[i] = ((*a)->arr[i] ^ __ULL_ONES) + carry; // check carry up carry = !(*a)->arr[i]; } refresh(a); ``` 特別的是，由於 minus 預設是提供給減法使用，故要考慮有號長度擴展的議題。對此我實作 `ib_minus` 完成擴展邏輯。說是如此，也只需要 `ib_copy` 一下即可，因為 `minus_in_place` 會照顧到所有位元。 ```c // implementation of private method "ib_minus" struct __inf_bits **res = ib_copy(a, expand_to); minus_in_place(res); return res; ``` ##### 減法 有了 `add_in_place` 和 `minus`，減法變得非常簡單： ```c // implementation of public method "sub" const int use_a_ull = ib_up_index((*a)->use), use_b_ull = ib_up_index((*b)->use), expand_to = use_a_ull > use_b_ull ? use_a_ull : use_b_ull; struct __inf_bits **res = ib_minus(b, expand_to); add_in_place(res, a); return res; ``` #### 乘法 ##### 概念 乘法是目前最複雜的實作，雖然沒有用上特別精妙的演算法，不過還是用上了資工系學生常用的 DP 跟 lazy evaluation。概念上源自最簡單的實作：見乘數某位元為 $1$ 時，將被乘數複製並位移，與回傳結果相累加，worse case 複雜度為 $O(mn)$，$m$、$n$ 分別為被乘數和乘數的 `ib_data_t` 數。 這樣的實作對於長度很大且 $1$ 很多的乘數來說極其低效，同時可預期乘數內不同 $1$ 數量的乘法運行時間大相徑庭，效能難以預期。仔細想會發現，若將乘數切成等長而更細的 bit slice，會發現程式碼存在大量重複的加法，比如下例。假設乘數如下 (方便起見，以一個 byte 為例)： ![](https://hackmd.io/_uploads/B1tN8pCNn.png) <!-- ```graphviz digraph dg { node[shape=record]; n[label="1|0|1|0|0|1|1|0"]; } ``` --> 若兩兩為一組看，變成 ![](https://hackmd.io/_uploads/HyOH8pCE2.png) <!-- ```graphviz digraph dg { node[shape=record]; n_ [label="1|0"]; n__ [label="1|0"]; n___ [label="0|1"]; n____[label="1|0"]; } ``` --> 如果我們紀錄被乘數乘以各組 bit slice 的結果，便可重複利用部分乘法、加法的計算結果，將問題切成重複的子問題，此時就可以掏出 DP 來用。 抽象上每次對被乘數移動一個 byte 進行乘法，建表的目標是暫存被乘數乘以 $0 \sim 255$ 的結果，若下次乘以乘數的一個 byte 時發現以前已經乘過，便可直接使用暫存下的計算結果。 ```c some multiplicand x) 1010101110101011 --------------------- become... some multiplicand x) 0000000010101011 // and cache mul 10101011 --------------------- plus some multiplicand x) 1010101100000000 // same mul, use cached result --------------------- ``` #### 建乘法表的演算法 假設今遇到乘以 $n$ 這個 byte 的情況，且 $n$ 目前沒有暫存在表中。透過過往研究 fast doubling 的經驗，我們可以利用二進制的性質完成 lazy 風格的「乘以 $n$」邏輯。 首先將 byte $n$ 看作 $$ \tt{0b n_{7} n_{6} \cdots n_1 n_0} $$ 若今已經知道被乘數乘以 $\tt{0b0 n_{6} n_{5} \cdots n_1}$ 的值，想知道乘以 $n$ 的結果便輕而易舉，設被乘數為 $a$： $$ a \times \tt{0b n_{7} n_{6} \cdots n_1 n_0} \\ = a \times \tt{0b0 n_{6} n_{5} \cdots n_1} \times 2 + a \times n_0 $$ 當中 $\times 2$ 的部分實作起來便是左移一位。如此一來，我們便建立起對乘法表請求的遞迴關係式： $$ query(n) = query(n/2) \times 2 + n_0 $$ 以 $n = \tt{0b00000111}$ 為例，以下說明我們的遞迴請求，注意遞迴中 $query(0)$ 和 $query(1)$ 為初始條件： $$ query(0b111) = query(0b11) \times 2 + 1 \\ = (query(0b1) \times 2 + 1) \times 2 + 1 $$ #### 乘法演算法 1. 首先建立表格 `table`，大小為 $256 \times 8$，每格預計放一個暫存的 `inf_bits`，除第 `[0][0:3]`、`[1][0:3]` 需初始化外，其他位置都留空。 2. 初始化最終結果 `res` 3. 自低位遍歷乘數正在使用的資料，一次走訪一組 $64$ bits 1. 取得當前走訪之乘數的資料 $64$ bits 2. 以一個 sliding `mask` 遍歷，自 `0x000...0ff`, `0x0...0ff00`, ..., `0xff0...0` 一路滑動，目的是取得暫存之 $64$ bits 的每個 byte。 1. 檢查是否已經暫存該 byte 2. 若無，以 button-up 的方式套用前述建乘法表的遞迴關係演算法。 1. 建表時，同時複製同樣的結果 $8$ 份並位移至 $64$ bits 中次低 byte ~ 最高 byte 共 $8$ 個位置，暫存於 `table[n][0~8]`，以適應不同位置下乘以相同 byte 的結果。(優化空間：將此處改為 lazy) 3. 使用暫存結果，加入 `res` 4. 釋放 `table` 與回傳 `res` #### 實作 ```c static struct __inf_bits **mul(struct __inf_bits **self, struct __inf_bits **other) { // initialize result and constant variables struct __inf_bits **res = ib_malloc(sizeof(struct __inf_bits *)); ... // initialize dp table const int table_lim = 256, // magic table upper bound, can include 256 cases (8 bits) step = LOG2(table_lim), slices = BITS_IN_DATA / step; // const -> no worries of division initialization :) struct __inf_bits **table[table_lim][slices]; // initialize basic cases of table ... // run mutiplication algo for (int ull_cnt = low_b_ull; ull_cnt < use_b_ull; ++ull_cnt) { int collect = (*other)->arr[ull_cnt]; // col_mask: 0x00000000000000ff, 0x000000000000ff00, 0x0000000000ff0000, // ..., // 0x00ff000000000000, 0xff00000000000000 // # of iteration is "slices" for (ib_data_t col_mask = table_lim - 1, slice = 0; col_mask; col_mask <<= LOG2(table_lim), ++slice) { // fetch current step (byte) const int cur_step = (collect & col_mask) >> (slice << LOG2(step)); if (cur_step && !test(&table_mk, cur_step)) { // need dp-growing // mask: 0b00000011, 0b00000111, 0b00001111, ..., end // 0b (11) 11111111 (notice that this is in binary) for (int mask = 0x3; mask < table_lim; mask = (mask << 1) | 1) { const int _masked = cur_step & mask, // current masked cur_step _mask_off = LOG2(_masked); // mask offset if (!test(&table_mk, _masked)) { // rename calculated lower instance (i.e. not including // current MSB) struct __inf_bits **lower = table[cur_step & (mask >> 1)][0]; // copy into new instance struct __inf_bits **cp = ib_copy(lower, _mask_off + use_a_ull); // add MSB in place left_shift_in_place(self, _mask_off); add_in_place(cp, self); right_shift_in_place(self, _mask_off); // save into dp table table[_masked][0] = cp; for (int i = 1; i < slices; ++i) { struct __inf_bits **ref = left_shift(cp, i * step); table[_masked][i] = ref; } mark(&table_mk, _masked); } } } // collect cur_step to result if (cur_step && !is_zero(table[cur_step][slice])) add_in_place_long_shift(res, table[cur_step][slice], ull_cnt); } } // free table and return ... return res; } ``` ### 效能評估與成果 想評估本大數運算函式庫，我建立起測試框架，以下讓我娓娓道來。 #### Basic 除錯最簡單的即印出資料，`show_hex` 方法便由此而生，是第一個完成方法。一開始的測試方法非常粗暴: ```c // in test.c int main() { inf_bits bn1 = ib_methods.construct(0xffffffff); ib_methods.show_hex(bn1); ib_inner_methods.left_shift(bn1, 3); ib_methods.show_hex(bn1); ib_methods.mark(bn1, pos); ib_methods.show_hex(bn1); printf("%d\n", ib_methods.test(bn1, pos)); /* ... */ } ``` 這種除錯方法顯然過於低效，如果有專屬 `inf_bits` 物件的「相等檢查」將能簡化除錯流程，`equals` 方法因此誕生，該實作盡可能利用 `use`、`low` 成員縮減比較範圍。 ```c // main implemantation part of public method "equals" const int use_ull = ib_up_index((*self)->use), low_ull = ib_dn_index((*self)->low); for (int i = low_ull; i < use_ull; ++i) if ((*self)->arr[i] != (*other)->arr[i]) return 0; ``` 這樣至少就能在不相等時才印出資料，讓除錯訊息不會過於冗長。 #### 以巨集實作友善的 Assert 測試時常用斷言來實現，比如 Rust 語言中執行 cargo test，通常會以有沒有觸發 `assert_eq` 等來判斷是否運行正確。C 語言有 assert 可用，不過比起直接引發 panic，我希望能印出錯誤訊息並繼續執行其他測試。故我將 `equals` 利用巨集包裝，其包含對人很友善的錯誤訊息。用法如下： ```c // in test.c::sub_test inf_bits sub = ib_methods.sub(added, a); show_and_abort_if_not_equal(sub, a); ``` 實作如下： ```c #define show_and_abort_if_not_equal(bn, correct) \ if (!ib_methods.equals(bn, correct)) { \ printf("\n<Assertion failed at line %d in file %s>\n", __LINE__, \ __FILE__); \ printf("Incorrect value: "); \ ib_methods.show_hex(bn); \ printf("Ground true: "); \ ib_methods.show_hex(correct); \ printf("Abort testing.\n\n"); \ return 0; \ } ``` 利用 [Standard Predefined Macros](https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html)，印出的訊息包含檔案與行數等編譯時期可確定的訊息，錯誤訊息舉例如下: ``` <Assertion failed at line 468 in file test.c> Incorrect value: [Metadata] addr: 0x6093b80 cap: 128, use 65, low: 1 [Data] addr: 0x6093b90, arr: 0000000000000001_4a6d6986c7b0b3f2 Ground true: [Metadata] addr: 0x659b7e0 cap: 128, use 63, low: 1 [Data] addr: 0x659b7f0, arr: 0000000000000000_4a6d6986c7b0b3f2 Abort testing. ``` #### 以巨集裝飾測試函式 有了前述巨集，撰寫測試函式變的簡單許多，於是測試函式們一一登場。我另外撰寫 `test_all` 函式來呼叫這些測試函式。 ```c _Bool test_all() { if (!shift_test()) { printf("shift_test failed"); return 0; } if (!single_bit_test()) { printf("single_bit_test failed"); return 0; } /* ... */ } ``` 上述程式碼怎麼看怎麼冗余，有沒有更好的使用方法？由於 `failed` 前的字串即函式名，當然可以選擇為函式包一層函式 (i.e. decorator)，其執行函式本身並印出函式名，這要求該函式需同時傳遞函式與函式名。此時若改用巨集的字串串接可以寫得更加簡潔： ```c #define run_test(test_name) \ { \ printf("INFO: "#test_name"\n"); \ if (!test_name()){ \ printf("ERROR: " #test_name " failed\n"); \ return 0; \ } \ printf("INFO: passed "#test_name" \n"); \ } ``` 訊息的效果如下： ```log ... INFO: passed single_bit_test INFO: copy_test INFO: passed copy_test INFO: sub_test <Assertion failed at line 345 in file test.c> Incorrect value: [Metadata] addr: 0x6520800 cap: 128, use 62, low: 0 [Data] addr: 0x6520810, arr: 0000000000000000_369f8b3100f3f8d9 Ground true: [Metadata] addr: 0x6143f90 cap: 128, use 0, low: 0 [Data] addr: 0x6143fa0, arr: 0000000000000000_0000000000000000 Abort testing. ERROR: sub_test failed ``` 更進一步的，某些測試函式我想透過 Python 協助驗證，這要求執行的函式多一個檔名參數。利用巨集 `__VA_ARGS__` 同樣可以完成要求，且為了避免重複寫近乎相同的巨集，我將前面的巨集拆分為以下奇妙的樣子： ```c #define __run_test_front(test_name) \ { \ printf("INFO: " #test_name "\n"); \ if (! #define __run_test_mid_no_arg(test_name) test_name() #define __run_test_mid_args(test_name, ...) test_name(__VA_ARGS__) #define __run_test_end(test_name) \ ) \ { \ printf("ERROR: " #test_name " failed\n"); \ return 0; \ } \ printf("INFO: passed " #test_name " \n"); \ } ``` 如此方能以巨集生成巨集：需參數與不需參數版的 `run_test`。 ```c #define run_test(test_name) \ __run_test_front(test_name) __run_test_mid_no_arg(test_name) \ __run_test_end(test_name) #define run_test_args(test_name, ...) \ __run_test_front(test_name) __run_test_mid_args(test_name, __VA_ARGS__) \ __run_test_end(test_name) ``` 經這一番折騰，功能的測試程式碼變得極其簡單美觀，人類可輕鬆閱讀並擴充：） ```c _Bool test_all() { run_test(shift_test); run_test(single_bit_test); ... // test that need to dump file run_test_args(dump_fib, "output/fib_output.txt"); run_test_args(inc_dec_test, "output/inc_dec_output.txt"); ... return 1; } ``` #### 目前遇到的問題 ##### 正負號問題 利用二補數的性質，加減法目前看似天下太平，但其實迴避了一個嚴重的問題: 當前 bit stream 究竟「是不是負數」。 假設 bit stream 的內容為 `0xffffffffffffffff`，其是表示的是正還是負數無從得知。新的實作在概念上加入新成員 `sign`，需在各個運算中維護此數。利用 [Linux 中紅黑樹的節點著色技巧](https://hackmd.io/@sysprog/linux-rbtree#%E9%A1%8F%E8%89%B2)，由於 `capacity` 成員最低六個位元實際上沒有用到，可以在那裡紀錄 $6$ bits 內的額外資訊。 此為目前主要在調整的實作內容。 ##### 算術運算演算法 * 現有乘法演算法的實作中存在需不斷位移被乘數的 overhead，我透過調整 `add_in_place_long_shift` 減少部分位移的成本，不過建表時依然還有冗余的位移效能損耗 * 嘗試搭配 Karatsuba algorithm 加速 ##### 重構 此項目重無到有至今逾兩千多行，當中有許多地方值得重構，諸如 * 檔案結構調整：讓分工與測試更加容易管理 * 巨集重構：去除少用的巨集、為部分巨集的使用加上規則 * 嘗試引入物件導向「介面」的概念：`inf_bits` 透過實作 bitwise 系列、算術運算系列函式 ##### 效能測試 待除錯與重構進度完善後，我將導入效能測試框架，進一步與 Linux MPI 等比較效能，並進一步優化乘法演算法。 ##### 依賴函式庫議題與初步解法 可以發現資料的型別為 `ib_data_t`，原本我將其定義為依賴 `stdint.h` 的: ```c #include <stdint.h> /** * Define inner data type */ #define ib_data_t uint64_t ``` 但編譯時會產生以下錯誤。 ```bash make -C /lib/modules/5.19.0-38-generic/build M=/home/eroiko/repos/linux2023/fibdrv modules ... In file included from /home/eroiko/repos/linux2023/fibdrv/fibdrv.c:9: /home/eroiko/repos/linux2023/fibdrv/util.h:69:10: fatal error: stdint.h: No such file or directory 69 | #include <stdint.h> | ^~~~~~~~~~ compilation terminated. ... make: *** [Makefile:18: run] Error 2 ``` 也就是找不到 `stdint.h`。這是因為 `fibdrv` 本身即 kernel module，我們的 include path 中也不存在 C 語言標準函式庫，自然無法編譯。 [參考本文](https://stackoverflow.com/questions/14541536/using-linux-types-h-in-user-programs-or-stdint-h-in-driver-module-code-do)，提到 Linux kernel 其實也定義好諸多型別可供使用，在 `asm-generic/int-ll64.h` 中。由於我希望此函式庫可同時適用於 kernel 和 user space，最終我利用條件編譯完成在兩種不同環境下的編譯。 ```c #ifdef __KERNEL__ #include <asm-generic/int-ll64.h> /** * Define inner data type */ #define ib_data_t u64 #else #include <stdint.h> /** * Define inner data type */ #define ib_data_t uint64_t #endif ``` 同樣的問題也適用在其他地方，比如配置記憶體、列印資料等原本依賴 C 語言標準函式庫的功能，其在 kernel 內不存在。此時可以利用 `lab0-c` 中提及的 [function hooking](https://en.wikipedia.org/wiki/Hooking) 技巧，將 kernel 中對應 C 標準函式庫功能的函式重新包裝，搭配條件編譯便可在 user space 或 kernel 中編譯本函式庫，以下擷取用例。 ```c // in inf_bits.c // conditional compilation #ifdef __KERNEL__ #include <linux/printk.h> #include <linux/slab.h> #define __ib_print(fmt, ...) printk(KERN_ALERT fmt, __VA_ARGS__) #define __ib_malloc(size) kmalloc(size, GFP_KERNEL) #define __ib_free(ptr) kfree(ptr) #else #include <stdio.h> #include <stdlib.h> #include <string.h> #define __ib_print(fmt, ...) printf(fmt, __VA_ARGS__) #define __ib_malloc(size) malloc(size) #define __ib_free(ptr) free(ptr) #endif ``` 不過事情沒有我想的簡單，遇到下面的情況目前我無法解決。 我在 `inf_bits.c` 中實作 `dump` 函式，其依賴 `fopen`, `fclose` 等 File R/W 標準函式，[本討論串](https://stackoverflow.com/questions/1184274/read-write-files-within-a-linux-kernel-module)提供看似開箱即用的解法，[另外此文](https://www.twblogs.net/a/5b7aede72b7177392c972a80)詳細說明這些 API 的行為，於是我嘗試翻閱原始碼，但... ![](https://i.imgur.com/Y1M3kvs.png) > 恩，不是我眼睛業障中吧？！ 對，並沒有，但很抱歉那是以前有的 0.0 ![](https://i.imgur.com/8Z6ibTC.png) 可見與核心相關的函式隨版本的更迭可能有所變動，這限制本程式碼於不同 kernel 下編譯的成功與否，故我先在此打住，僅利用條件編譯略過 `dump` 函式，即 kernel space 中的本函式庫無 `inf_bits::dump` 的定義與實作。 ### 貢獻與小結 本函式庫的設計使用過去經典實作中未有之紀錄使用位元範圍 `use`、`low` 的邏輯以加速許多運算，其背後隱含的便是過去探討過之子項目的 `clz` 系列函式；實作上應用諸多 C 語言程式設計技巧（指標與物件導向、前處理器與巨集、間接指標等），並試圖導入 Linux 風格之巨集與紅黑樹中標記節點顏色的技巧來紀錄符號，這也是目前已知實作中的首創。 這些設計思路若能盡付實現，很可能進一步提升工程上大數運算的效率。 ## `make2IntelliSense` 向 Linux kernel 邁進時，如果能善用地表最強編譯器 vscode 的協助，便能以最舒服的姿勢 trace 與調整 kernel。為此誕生的便是本子項目：其名的意義為將 `makefile` 執行時的資訊轉為給予 vscode `intelliSense` 的提示。 ### 現有研究概況與比較 要完善 intelliSense 的設定，網路上各論壇提供許多解決方法，以下整理之。 #### Include Path 設定 以 `fibdrv` 這個作業專案為例，如果純粹將 reposiroty clone 好後使用 VSCode 開啟比如 `fibdrv.c`，相信會看到貼心的 IntelliSense 的警告。 ![vscode-intellisense-error](https://i.imgur.com/xoUqDkX.png) 這是因為預設的 include path 並不包含我們需要的核心標頭檔。 ##### 常規做法 由前車之鑑 [1](https://stackoverflow.com/questions/58386640/how-to-develop-linux-kernel-module-with-vscode-without-incorrect-error-detection) 和 [2](https://github.com/microsoft/vscode-cpptools/issues/5588) 得知 IntelliSense 需要調整 [C/C++ Extension](https://marketplace.visualstudio.com/items?itemName=ms-vscode.cpptools) 設定檔: `c_cpp_properties.json`。 1. 準備 Linux 設定檔模板 ```json { "configurations": [ { "name": "Linux", "browse": { "limitSymbolsToIncludedHeaders": true, "databaseFilename": "" }, "intelliSenseMode": "linux-gcc-x64", "compilerPath": "/usr/bin/gcc", "cStandard": "c99", "cppStandard": "gnu++17" } ], "version": 4 } ``` 2. 加入 `includePath` 設定 ```json ... "name": "Linux", "includePath": [ "${workspaceFolder}/**", "/usr/include", "/usr/local/include", "/usr/src/LINUX_KERNEL_HEADER/include", "/usr/src/LINUX_KERNEL_HEADER/arch/x86/include", "/usr/src/LINUX_KERNEL_HEADER/arch/x86/include/generated", "/usr/lib/gcc/x86_64-linux-gnu/GCC_VERSION/include" ], "browse": { ... ``` 要調整兩點。 * `LINUX_KERNEL_HEADER` 換成自己的 kernel header 路徑名。 * `GCC_VERSION` 換成自己的 GCC 版本。 基本上 `includePath` 中前五項都是開發 Kernel Module 的常客，當然第七項編譯器本身也是。第六項本次實作會用到，不過未來開發其他模組的話可能會引入其他的標頭檔。 尋找標頭檔的方法為至 `include` 資料夾下尋找被 include 的標頭檔，將其所在的資料夾加入 `includePath`。 #### defines 設定 又以 `lab0-c` 作業中探討 `list_sort.c` 為例，即使直接將 `linux` 這個 repository clone 下來並修正 include path 問題，還是會發現一些巨集或函式無法被識別，而被 IntelliSense 自動猜測為 `int FUNC_NAME()`。 ![vscode-define-err](https://i.imgur.com/ukWixLv.png) likely 和 unlikely 兩巨集為編譯器提供的巨集，為了提示編譯器判斷分支發生的可能性，編譯器便可以根據此提示進行最佳化，[此文提供了詳細的說明](https://meetonfriday.com/posts/cecba4ef/)。 使用時須引入 `<linux/compiler.h>`，同時可以進入[原始碼](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)查看巨集的細節。發現與 `__KERNEL__` 以及其他數個巨集有關: > 以下展示部分，前面還有另一個定義。 ![def-likely](https://i.imgur.com/RkYh2Xs.png) 這些巨集定義都影響著 IntelliSense 的運作，若不告訴它我們編譯時定義的巨集，IntelliSense 就不會正常運作。 ##### 常規做法 `defines` 是為了解決條件編譯的問題，當中加入的字串會使 IntelliSense 在 indexing 時看見需指定條件編譯後才會編譯到的程式碼。 基本上加入以下巨集定義就能解決大部分條件編譯的影響。 ```json ... "compilerPath": "/usr/bin/gcc", "defines": [ "__GNUC__", "__KERNEL__", "MODULE" ], "cStandard": "c99", ... ``` 由於前面設定正確的 include path，並加入 `__KERNEL__` 等巨集， IntelliSense 復活了 :) > Include Path 的例子 ![vscode-intellisense-good](https://i.imgur.com/9B5yt8R.png) > Include Path + 巨集設定的例子 ![vscode-define-ok](https://i.imgur.com/9EnpFbF.png) #### 編譯後目錄雜亂的問題 正常進行編譯後，以 Linux 核心為例，可能會看到目錄看見以下: :::spoiler 不怎麼美觀的目錄 ![](https://i.imgur.com/M0SDk7x.png) ![](https://i.imgur.com/xZ3SIz0.png) ::: 不僅不美觀，VSCode 更會去遞迴的解析這些不必要解析的檔案，從而降低 VSCode 的速度，增加搜尋程式碼的負擔。 對此，[VSCode 有很多設定](https://code.visualstudio.com/docs/editor/codebasics#_advanced-search-options)可以調整對特定檔案的排除，不過最便捷的應該是以下兩種。 1. 直接套用 `.gitignore` 的設定 ```json // .vscode/settings.json { "explorer.excludeGitIgnore": true, } ``` 2. 利用 `files.exclude` 決定檔案的去留 ```json // .vscode/settings.json "files.exclude": { "**/*.a": true, "**/*.cmd": true, "**/*.d": true, "**/*.elf": true, ... "**/Module.symvers": true, "**/Thumbs.db": true, "**/client": true, "**/dkms.conf": true, "**/modules.order": true, "**/out": true } ``` 後者若要手動添加會有點麻煩... ### 設計原理 如果能透過某種方法自動偵測編譯時期的巨集定義與想要隱藏的檔案，我們便能撰寫腳本來蒐集這些資訊，將結果寫入前述諸項設定。 ### 研究方法與步驟 前人的方法非常費人力，且面對更為龐大的 kernel module 乃至於最遠大的目標: Linux kernel 而言，手動調整實在是不切實際。以 Linux 核心原始碼為例，如果打開其 [Makefile](https://github.com/torvalds/linux/blob/master/Makefile)，我們會看到 ![linux-makefile](https://hackmd.io/_uploads/rJ6R6mySh.png) :::info 以 Linux 6.4.0 為例，兩千一百多行的根目錄 `Makefile`...(`scripts` 目錄下還有滿坑滿谷的 `Makefile`) 別開玩笑了，這不是肉眼可以追蹤的量吧。對小的專案沒問題，但我們的目標是 Linux 核心... ::: 不過在開發已經打好基礎之模組的情況下，若存在完好的 `Makefile` 和 `.gitignore`，我們有機會自動生成設定檔。因為 `MakeFile` 是告訴我們編譯方法的第一手資料、`.gitignore` 則是告訴我們哪些檔案沒有顯示的必要。 對此，[本網站](https://iotexpert.com/stupid-python-tricks-vscode-c_cpp_properties-json-for-linux-kernel-development/)提供很暴力但可行的解決方法: 利用 `make` 的 [`--just-print`](https://www.gnu.org/software/make/manual/html_node/Instead-of-Execution.html) 功能 (其會印出若真的運行時會執行的命令)，以獲得包含 `includePath`，`defines` 等訊息，透過 Python 腳本解析後生成[方才](#常規做法)提及之常規做法的模板。 本方法的特色有二 * 一次擷取所有需要的 include 路徑 * 巨集可以對個別電腦客製化 但由於一次粗暴的解析所有編譯時加入的巨集，故有兩缺點: * 解析出的巨集量過多，導致 VSCode 解析程式碼變得緩慢 * 不同程式/模組所需的巨集不同，一次定義好所有巨集不保證適用於所有模組 針對第一個缺點，我提出了改進版的腳本。當中加入了一些例外處理與客製化設定，另根據[Makefile 語法](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)和官方文件練習寫簡單的 `Makefile`。 ### 實現與實驗 透過一次次產出編譯 linux kernel 的資訊，利用重新導向成文字檔分析，佐以對 Linux 下尋找路徑相關的命令、編譯器設定的查詢，逐步實作出 Python + makefile 腳本。新的腳本目前引入以下功能： #### 加入對排除檔案的調整 * `exclude`: 手動加入想排除之 pattern 的列表 * `bypass`: 不希望排除之 pattern 的列表 預設加入 `.vscode` 避免其被忽略。 ```python bypass = { '.vscode' } ``` * `replace`: 將指定偵測到的排除檔案置換成自己想要的 pattern * 預設為以下，如此便不會因為 Linux kernel 中有 `.*` (匹配以 `.` 為首之任意長度字串) 忽略 `.vscode` 資料夾。 ```python replace = { ".*": ".[!v]*" # exclude files start with . but not .v } ``` > VSCode 採用 Unix 下經典的 [glob](https://en.wikipedia.org/wiki/Glob_(programming)) 語法匹配檔名 pattern，但不同於 `bash`，VSCode 並不支援 glob 的擴充語法，不如 regex 靈活。不過語法規則少很多，相信看維基就能理解了。 #### `make clean` 命令 嘗試刪除目標資料夾下 .vscode 內的設定檔。 #### 針對 `c_cpp_properties.json`，新增自動偵測以下客製化設定 * 編譯器路徑 * 使用之 C/C++ 語言標準 * 會採用最低標準，比如若有 `gnu11` 和 `gnu99`，則會採用 `gnu99`。 * 若都沒有指定語言標準，則預設標準為 `c99`，這可能會使 IntelliSense 有些許不符合預期。 實作方法為使用 regex，正好把以前不願面對的它重新學了一遍。 ### 貢獻 我將該腳本公開於 Github，作為已知少數能自動完成 vscode 設定 C/C++ 之 intelliSense 的 repository 提供其他開發者檢閱與使用。 ### 效能評估與成果 在我實現最初版的 `make2IntelliSense` 後於臉書公開，除了收到部分正面的評價： > 李建勳 > 最近在Visual Studio編寫C++程式有遇到Intellisense的false error不知何解 我來研究一下 感謝這個repo > > 羅習五 > 這個計劃案很棒 更有趣的是，有來自英國的工程師給我批評與指教，引述如下： > Gao Tianyi > Hi, sorry for being discouraging, but I want to point out that editing `includePath` or other items in `c_cpp_properties.json` is not really the best solution for 2023. The recommended way is to generate `compile_commands.json` by `./scripts/clang-tools/gen_compile_commands.py` under kernel source code. Following are some related links that may be helpful: > 1. https://www.mail-archive.com/kernelnewbies@kernelnewbies.org/msg22110.html > 2. https://lore.kernel.org/all/CAKwvOdkQTFEGaSXj5kHpuqTQ9hFYPWkCAyegQ4jienLaH5x9Ng@mail.gmail.com/t/#me025ddd2bffdd1835f5f19ba4fe657c879fb7056 > 3. https://stackoverflow.com/questions/70819007/can-not-use-clangd-to-read-linux-kernel-code/71543187#71543187 > 4. https://howardlau.me/programming/debugging-linux-kernel-with-vscode-qemu.html > 5. https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1821917.html > 6. https://github.com/amezin/vscode-linux-kernel > > As you can see, there are only separate discussions over this but I personally can not find a correct and complete post for this. Hope you are further updating your post if possible which will really benefit everyone! 其提到雖然當前並沒有能完美解決 vscode 設定的方案，不過我的方法於 2023 年仍有改進空間。他更進一步給我許多參考文獻能收到這樣的批評實屬珍貴，我將於未來閒暇之餘持續更新。 ## `bitops-patch` ### 現有研究概況與比較 `bitops` 本身為 Linux kernel 中的一個套件，當中實現了 `ffs` 系列函式，他們被用在核心的其餘諸多地方，這點可以簡單利用 vscode 對 `ffs`、`__ffs`、`fls`、`__fls`、`fls64`、`ffz` 這些函式進行搜尋便可得知。一個經典的應用是 CFS (completely fair scheduler) 的排程上，會調用 `bitops/sched.h` 中的 `sched_find_first_bit` 函式，其又會調用 `__ffs`。 由子項目 `clz` 系列函式的實作為引子，我 trace linux kernel 中的 `ffs` 系列函式，很好奇當中究竟如何實現，但結果卻令我略有失望，以下說明現有概況。 #### 概念：`ffs`、`__ffs` 的不同 首先先釐清 `ffs`、`__ffs` 的不同之處：參考 `bitops` 系列對外的介面: [`arch/arc/include/asm/bitops.h`](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 中的註解得知 * `__XXX` 系列: 以 index 0 索引，範圍為 `0 ~ {length of input type - 1}` * `XXX` 系列: 以 index 1 索引，範圍為 `1 ~ {length of input type}` #### 採用硬體實作與否 GCC 除了提供我在子項目 `clz` 系列中提到的 `__builtin__c{l,t}z` 硬體指令的包裝函式外，實際上也存在 `__builtin_ffs`。就算沒有此函式，用前兩個也足以解決 `ffs` 和 `fls` 的實作。不過並不是所有指令集都實作對應的硬體指令，所以才有 linux kernel 中 `ffs` 系列的軟體實作。Kernel 透過條件編譯決定最後應該採用哪種實作，而本子項目的重點將先放在軟體實作的部分。 接著來看看我發現的現有問題。 #### 詭異的實作不一致性與例外情況 凡是掛名 `__builtin_XXX` 的函式本身以 CPU 硬體指令實作，過濾例外情況 $0$ 作為輸入以避免 undefined behavior 是必備手續；同時使用 `ffs`, `fls` 時輸入 $0$ 本身就是極其不合理的事，此時檢查例外情況依然重要。 不過有趣的是，`bitops` 目錄下大家眾口一詞：有的說例外情況的判斷交由 caller 檢查，有的沒特別說 (只說其與 builtin ffs 有同樣的 routine)，有的直接為 $0$ 為輸入定義對應輸出... * 例外情況的判斷交由 caller 檢查 ```c // __ffs.h /** * __ffs - find first bit in word. * @word: The word to search * * Undefined if no bit exists, so code should check against 0 first. */ static __always_inline unsigned long __ffs(unsigned long word) ``` * 沒特別說，但自主處理例外情況 (只說其與 `builtin ffs` 有同樣的 routine) ```c // ffs.h /** * ffs - find first bit set * @x: the word to search * * This is defined the same way as * the libc and compiler builtin ffs routines, therefore * differs in spirit from ffz (man ffs). */ static inline int ffs(int x) { int r = 1; if (!x) return 0; ... ``` * 為 $0$ 為輸入定義對應輸出 ```c /** * fls - find last (most-significant) bit set * @x: the word to search * * This is defined the same way as ffs. * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. */ static __always_inline int fls(unsigned int x) ``` 所謂魔鬼藏在細節裡。這樣的不一致性往往導致開發時的不可控風險，屬於 bad smell 的一種。 #### [`constant_fls`](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 的存在意義 [`arch/arc/include/asm/bitops.h`](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 中存在一函式 `constant_fls`，簽名與部分實作如下: ```c static inline int constant_fls(unsigned int x) { int r = 32; if (!x) return 0; if (!(x & 0xffff0000u)) { x <<= 16; ... } ``` 其目的是利用 [gcc `__builtin_constant_p`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fconstant_005fp) 協助於編譯時期進行 [Constant folding (propagation)](https://en.wikipedia.org/wiki/Constant_folding)，於[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization?type=view#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B7%A8%E8%AD%AF%E5%99%A8%E5%92%8C%E6%9C%80%E4%BD%B3%E5%8C%96%E5%8E%9F%E7%90%86%E7%AF%87)介紹過其觀念。以下節錄 gcc 官方文件，說明 `__builtin_constant_p` 的使用: > You can use the built-in function `__builtin_constant_p` to determine if a value is known to be constant at compile time and <font color=#cd5c5c>**hence that GCC can perform constant-folding on expressions involving that value**.</font> ... > > ... A **return of `0` does not indicate that the value is not a constant**, but merely that GCC cannot prove it is a constant with the specified value of the `-O` option. > > You may use this built-in function in either a macro or an inline function. **However, if you use it in an inlined function and pass an argument of the function as the argument to the built-in**, GCC never returns `1` when you call the inline function with a string constant or compound literal (see Compound Literals) and **does not return 1 when you <font color=#cd5c5c>pass a constant numeric value</font> to the inline function <font color=#cd5c5c>unless you specify the `-O` option**</font>. 表示當 `__builtin_constant_p` 用於 macro 或 inline function 時，傳入的參數為 常數數值，當開啟編譯器最佳化 `-O` 選項後即會進行 constant folding。 綜觀 `constant_fls` 函式，我們看不出其與 [`bitops/fls`](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/fls.h) 有任何差別。這表示就算不實現 `constant_fls`，也能利用上述 `bitops/fls` 函式協助編譯器進行 constant folding。 那麼問題就出現了： * `constant_fls` 實現的意義為何？ * 若調整 `bitops/flz` 或 `constant_fls` 的實作，對於 [`bitops.h` 中 `fls`](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h)傳入參數為 `__builtin_constant_p(x) == 1` 時的效能是否有影響？即是否有可能影響 constant folding？ 另附上 [`bitops.h` 中 `fls`](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 函式以供參考。 ```c /* * fls = Find Last Set in word * @result: [1-32] * fls(1) = 1, fls(0x80000000) = 32, fls(0) = 0 */ static inline __attribute__ ((const)) int fls(unsigned int x) { if (__builtin_constant_p(x)) return constant_fls(x); return 32 - clz(x); } ``` #### 另一細節的不一致性 有一個小小細節是: 使用 `if-else` 實作系列函式的一個優點是可以略過部分不必要的操作，比如 `__fls` 函式: (這點 `__ffs` 亦同) ```c static __always_inline unsigned long __fls(unsigned long word) { int num = BITS_PER_LONG - 1; ... if (!(word & (~0ul << (BITS_PER_LONG-2)))) { num -= 2; word <<= 2; } if (!(word & (~0ul << (BITS_PER_LONG-1)))) num -= 1; // bypass "word <<= 1" instruction here return num; } ``` 但隔壁鄰居 `fls` (`ffs` 亦同) 可沒打算那樣做: ```c static __always_inline int fls(unsigned int x) { int r = 32; ... if (!(x & 0xc0000000u)) { x <<= 2; r -= 2; } if (!(x & 0x80000000u)) { x <<= 1; // meaningless?! r -= 1; } return r; } ``` 更有趣的是他的遠親 `constant_fls` 倒是考慮到了這點。 ### 設計原理 透過觀察 Linux kernel 中數個古怪現象，其中一個解決方法便是使用我第一個子項目的成果: 巨集生成函式來針對不同輸入輸出型別進行實作的統一。好處有以下： * 程式碼簡潔 * 組合語言變短 * 可以輕鬆維護並同步所有`ffs` 系列函式的軟體實作 * 統一 Undefined behavior 的處理方式 * 為未來 $128$ bits 版的實作乃至於其他型別的實作給出輕鬆擴展的解決方案 但若要移植我的解決方案，將會有以下缺點： * 舊方案無法處理有無雙底線如 `__ffs` 等函式的實作 * 效能降低 * 尚不清楚貢獻核心的手續 先不考慮最後一項，我們來討論解決辦法。對於第一項，我們可以調整函式的生成邏輯，增加可控變因來嘗試完成。對於第二項，便是前面賣的關子之一的議題，將透過進一步理解編譯器的行為來嘗試解決。 ### 研究方法 有了 `clz` 系列函式的研究，我們已經研究清楚 `ffs` 函式的實現手法；有了 `make2IntelliSense` 腳本，我們已經準備好以 vscode 進行 Linux kernel 的調整。接下來便是利用打下的前處理器基礎來研究如何擴展巨集，並利用自 fast doubling 以來研讀組合語言與閱讀編譯器規格書等完成效能上的優化。 ### 實現與實驗 #### 擴展巨集的功能 透過定義額外兩個供其他開發者使用的巨集常數 ```c #define __FFLS_START_INDEX_FROM_ZERO 0 #define __FFLS_START_INDEX_FROM_ONE 1 ``` 我調整 `ffs` (`fls` 同理) 函式如下: ```c= /** * Hidden generator of ffs to hide evaluation of size of type */ #define __gen_ffs(in_type, out_type, start_from, fn_name, bit_len) \ static __always_inline out_type fn_name(in_type x) \ { \ int bits, shift; \ in_type mask; \ if (!x) \ return 0; \ bits = start_from; \ shift = bit_len >> 1; \ mask = (in_type) ~(0xFFFFFFFFFFFFFFFF << shift); \ do { \ if (!(x & mask)) { \ bits += shift; \ x >>= shift; \ } \ shift >>= 1; \ mask >>= shift; \ } while (shift); \ return bits; \ } /** * gen_ffs() - Macro to generate function series of * ffs series - find first (least-significant) bit set. * * Generated function parameter: * @x: the object to search * * Macro arguments: * @in_type: input type of ffs * @out_type: output type of ffs * @start_from: starting index of generated ffs to generate both * ffs series (return 1 ~ 64) and __ffs series (return 0 ~ 63) * * Note if: * start_from is __FFLS_START_INDEX_FROM_ZERO, then ffs(0) = 0, * ffs(1) = 0, ffs(object leads with 1) = sizeof object - 1. * start_from is __FFLS_START_INDEX_FROM_ONE, then ffs(0) = 0, * ffs(1) = 1, ffs(object leads with 1) = sizeof object. * @fn_name: Function name to be generated */ #define gen_ffs(in_type, out_type, start_from, fn_name) \ __gen_ffs(in_type, out_type, start_from, fn_name, (sizeof(in_type) * 8)) ``` 根據我所寫的 kernel doc，其他開發者可以為 `start_from` 參數指派 `__FFLS_START_INDEX_FROM_ZERO` 或 `__FFLS_START_INDEX_FROM_ONE` 調整其起始索引值，如此一來無論是 `__ffs` 抑或 `ffs` 都能以同樣的規格實現。 原理可見程式碼第 11 行，初始化 `bits` (輸出) 時採用不同的起始索引。由於編譯器能自動識別並簡化這些常數，因此這些調整對效能沒有影響。 #### Loop unroll ##### 從一個 `x64` 組語小實驗開始 我嘗試將自己的 loop 版 `ffs` 置於 `util.h` 轉為組語，其在 `main.c` 中被呼叫並印出結果，以下節錄實作： <!-- 使用行數標注是因為下文敘述會用到 --> ```c= // util.h #define __gen_ffs(in_type, out_type, start_from, fn_name, bit_len) \ static __always_inline out_type fn_name(in_type x) \ { \ int bits, shift; \ in_type mask; \ if (!x) \ return 0; \ bits = start_from; \ shift = bit_len >> 1; \ mask = (in_type) ~(_ONES << (bit_len >> 1)); \ while (shift) { \ if (!(x & mask)) { \ bits += shift; \ x >>= shift; \ } \ shift >>= 1; \ mask >>= shift; \ } \ return bits; \ } #define gen_fls(in_type, out_type, start_from, fn_name) \ __gen_fls(in_type, out_type, start_from, fn_name, (sizeof(in_type) * 8)) // generate gen_ffs(__unsigned_int, int, START_INDEX_FROM_ONE, my_ffs); // main.c int main(void) { printf("%d\n", my_ffs((rand() % (__INT32_MAX__ - 1)) + 1)); } ``` `main.c` 中故意使用 `srand`、`time(NULL)` 和 `rand` 是為了不希望 compiler 將輸入設為常數；使用 `printf` 是希望 compiler 沒有機會把生成的 inline function 整個優化掉，強迫一定要取得結果並印出。 使用 `cc main.c -O -std=c99 -S` 帶優化的編譯，產生的組語節錄如下： ```python ... movl $0, %edi addl $1, %eax je .L2 # if (!x) return 0; movl $5, %esi movl $16, %ecx movl $1, %edi movl $65535, %edx jmp .L4 .L3: sarl %ecx shrl %cl, %edx subl $1, %esi je .L2 .L4: testl %edx, %eax jne .L3 addl %ecx, %edi shrl %cl, %eax jmp .L3 .L2: movl %edi, %edx leaq .LC0(%rip), %rsi movl $1, %edi movl $0, %eax call __printf_chk@PLT ... ``` 這裡可以觀察到一些有趣的現象，以下討論根據 [x86 cheat sheet](https://web.stanford.edu/class/cs107/resources/x86-64-reference.pdf)。 * `__gen_ffs` 中 `mask` 變數確實透過編譯器的協助轉為常數 `65535` (`0xffff`)，這符合預期。 * 更進一步的，將上述 `util.h` 第 13 行改為 `mask = (in_type) ~(_ONES << shift);` 後編譯為組語，發現得到一樣的結果。 * 本來顧慮到不使用全部直接是常數的巨集產開下可能導致 gcc 不會正確預先求出 `mask` 常數，事實證明編譯器實在太聰明了！ * `my_ffs` (使用巨集生成的 `ffs` 函式) 組語迴圈也很有趣。 * 查詢 `x86` 的 [`test` 指令](https://en.wikipedia.org/wiki/TEST_(x86_instruction))發現，原來其非迴圈條件判斷，而是 bitwise AND 運算，對應第 13 行 `x & shift` 的部分。 * 原來編譯器自動幫我將 `while` 轉為 `do-while`，不得不說真的很聰明，直接體會到編譯器的強大。 ##### 實現 Loop unroll 編譯器神通廣大，即使沒修過編譯器的我都聽過其中一個知名的功能：loop unrolling。透過將迴圈展開為只向下執行的程式碼，降低指令往前轉跳的 control hazard 和 instruction cache 成本。 參考[本討論串](https://stackoverflow.com/questions/24196076/is-gcc-loop-unrolling-flag-really-effective)，其討論到適合使用 loop unrolling 的時機： > 對次數少的小迴圈有效，反之則要付出大代價。 平常依靠編譯器自動最佳化即可，正如 Donald Knuth 所言： > We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. 明顯前述 `gen_ffs` 或者說 `my_ffs` 屬於適合 loop unrolling 的情況，於是我嘗試使用 [`-funroll-loops`](https://gcc.gnu.org/onlinedocs/gcc-4.5.2/gcc/Optimize-Options.html) 這個 gcc 編譯參數，其嘗試在編譯時期展開可預測迴圈執行次數的迴圈: ```bash cc main.c -O -funroll-loops -std=c99 -S ``` (左: 原版，右：unroll loops 版) ![](https://hackmd.io/_uploads/ByRqh5_E2.png) 成功得到展開後的迴圈，而且由於將邏輯迴圈化之前的重複次數本來就很少，展開後才只多七行，除了預見效能的提升外想不到其他可能。 更令我驚訝的是，除了能正確的 unroll loop，針對整數輸入型別展開為 5 次 $(i.e. 16, 8, 4, 2, 1)$ 以外，編譯器甚至聰明到把最後一個 $1$ 的情況優化成不去對 `x` 做無謂的運算，也就是 `.L6` 中不存在對 `%eax (x)` 的右移指令。 換言之，若將我的巨集生成函式應用於 Linux Kernel `ffs/fls` 系列函式的實作，有可能不會影響其效能。那麼下一步便是搞清楚 Linux Kernel 是如何編譯這些檔案，以確認迴圈展開與常數傳遞等效果是否真正的被編譯器採用。 ##### 精準最佳化：調整 compile 時特定位置採取的優化策略 希望調整 kernel 於編譯時，至少與 `ffs` 相關的部分採用 GCC 編譯時傳入 `unroll-loops` 參數的效果。 直接調整編譯參數有點不切實際，原因如下： * 只希望 unroll 生成出來的函式，不希望影響到其他函式。 * Linux 的 makefile 們 trace 起來好痛苦 另一方面，我想到 gcc 可能提供了額外的標記來解決問題，於是找到[本討論串](https://stackoverflow.com/questions/4071690/tell-gcc-to-specifically-unroll-a-loop)，其介紹了兩種方法： * [`pragma + GCC global optimize + push pop`](https://gcc.gnu.org/onlinedocs/gcc/Function-Specific-Option-Pragmas.html#Function-Specific-Option-Pragmas): 在函式前為 GCC 增加全域優化設定，函式後取消該新增。 > `pragma` 表示編譯提示。 ```c #pragma GCC push_options #pragma GCC optimize ("unroll-loops") // function with loops to be unrolled #pragma GCC pop_options ``` * 新增 [`attribute`](https://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html): 在函式前加上 ```c __attribute__((optimize("unroll-loops"))) // function with loops to be unrolled ``` 於是我嘗試實驗這兩者於以下編譯環境： ```bash > gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 ``` 發現後者沒有效果，前者雖然有，但不知為何在巨集生成函式下沒有效果。我嘗試過以下做法： * 直接暴力放 `pragma` 會報錯，在 `define` 中不能用 `#...`，故 `#pragma` 不能使用。(語法錯誤)。 ```c #define ... \ #pragma GCC push_options \ #pragma GCC optimize ("unroll-loops") \ \ /* function with loops to be unrolled */ \ \ #pragma GCC pop_options ``` * 利用 C99 的功能: [`_Pragma` 運算子](https://gcc.gnu.org/onlinedocs/cpp/Pragmas.html)替代 `#pragma` 巨集 這下語法不會錯誤了。但奇妙的是，這樣寫編譯後發現沒有效果！ ```c #define ... \ _Pragma("GCC push_options") \ _Pragma("GCC optimize (\"unroll-loops\")") \ \ /* function with loops to be unrolled */ \ \ _Pragma("GCC pop_options") ``` 於是我改為去掉最後一行 `_Pragma("GCC pop_options")`，編譯後發現竟然有效，但這樣調整全域優化設定非常不好，畢竟會影響到其他程式碼，我所追求的是只針對本函式的 loop unroll。 * 利用 GCC [Loop-Specific Pragmas](https://gcc.gnu.org/onlinedocs/gcc/Loop-Specific-Pragmas.html): 前述方法都是針對整個函式，經查找 GCC 規格書後發現還有此方法，透過標記在迴圈前一行告訴 GCC 要 unroll 幾次，語法為 `#pragma GCC unroll n`。 > 以下節錄 GCC 規格書，說明語法中 `n` 的意義： > n is an integer constant expression specifying the unrolling factor. The values of 0 and 1 block any unrolling of the loop. 於是我結合前述 `_Pragma` 運算子將程式改為： ```c #define ... \ ... \ _Pragma("GCC unroll 6") \ do { \ ... \ } while (shift); \ ... ``` 指定 $n = 6$ 是因為對於 $64$ 位元而言，迴圈將走訪 $shift = 2^5, 2^4, \sim, 2^0$ 這幾項可能。 不過此時讀者可能會好奇，這樣不就限制我抽象為巨集生成函式的作法只能用於 $64$ bits？ 答案是其實不會！ 雖然規格書沒有詳細提及，不過我以實驗測試 unroll 次數自 0 至 100。結果表明，當可 unroll 的次數 $n_{avai}$ 小於指派的次數，結果只會展開 $n_{avai}$ 次。畢竟 GCC 原本的 `funroll-loops` 本來就有能力分析迴圈合理的展開次數。 #### 實作階段 在實現精準的 loop unroll 後，下一步是實作於 Linux kernel。 首先我定義 `ffls_gen.h`，加入前述 `ffs`、`fls` 巨集生成函式。接著修改 `ffs.h`、`fls.h`、`__ffs.h`、`__fls.h`、`fls64.h`、`bitops.h` 等檔案，調整實作如下兩例，其餘皆依樣畫葫蘆： ```c // in __ffs.h /** * __ffs - find first bit in word. * @word: The word to search * * Undefined if no bit exists, so code should check against 0 first. */ gen_ffs(unsigned long, unsigned long, __FFLS_START_INDEX_FROM_ZERO, __ffs); // in ffs.h /** * ffs - find first bit set * @x: the word to search * * This is defined the same way as * the libc and compiler builtin ffs routines, therefore * differs in spirit from ffz (man ffs). */ gen_ffs(unsigned int, int, __FFLS_START_INDEX_FROM_ONE, ffs); ``` #### 初步測試 為了測試方便，我額外調整 `__builtin-ffs.h`、`__builtin-__ffs.h` 等一系列採用硬體指令版的實作為與軟體版的相同，並以 User mode linux 編譯運行，得到無任何錯誤的編譯、運行結果。 ![](https://hackmd.io/_uploads/SyxJl4JB3.png) ### 貢獻 調整至此，我 fork Linux kernel 6.4.0 並加上前述研究成果。待確認我的研究沒有疏漏，並理解貢獻 Linux kernel 的手續後，我將嘗試發起人生第一個 Linux kernel patch，希望能提供更加良好而不混亂的實作。 ### 效能評估與成果 透過本研究，成功實現了在同樣效能下更好的簡化程式碼、提升可讀性、統一未定義行為、提升擴展靈活性等，集眾優點於一身。 我們都學過[馬斯洛的需求層次理論](https://en.wikipedia.org/wiki/Maslow%27s_hierarchy_of_needs)，實際上[仿間](https://www.dein.fr/posts/2015-02-18-maslows-pyramid-of-code-review)也流傳程式設計的馬斯洛金字塔如下圖： ![image](https://hackmd.io/_uploads/rJMZjcCVh.png) 說明好的程式碼應該首先正確，其次安全，其次可讀性高，其次優雅，最後是利他。 本研究提供的實作首先透過與 `__builtin_XXX` 系列函式驗證正確性，符合正確層次。接著透過統一未定義行為，讓程式執行的安全性得以保障。再來透過合理的 kernel doc 註解與開發者可調參數和公開的開發紀錄，確保程式碼的可讀性，然後是以巨集生成函式的方式不失優雅的向舊有程式碼兼容，並提供額外擴展的功能。最後巨集生成函式的做法本身即利他行為，對未來新的輸入輸出型別的擴展提供一個開箱即用的實作方法；另外公開已準備好的開發紀錄也可說是一大利他。 此子項目的方方面面可說是做到不令我羞愧的研究成果。 ## 團隊合作方式 本專題雖由我個人進行，不過會和朋友謝承恩同學一同進行小書報。即使彼此的研究主題大相徑庭，仍時常給予彼此許多有趣建議，在此特別感謝。 ## 結論 從 fast doubling 的探討為起點，開始了我具體而微的專題研究。 在 fast doubling 子項目中，我梳理其理論、程式化的原理並以實驗探討效能議題。由此衍伸出 `clz` 系列函式的子項目研究，我探討數個位元運算的經典用例，說明它們演算法與位元運算的實作利弊，並以 `clz` 系列的巨集抽象解決位元運算的弊端，同時增加程式碼的復用性。 由 fast doubling 為引子，搭配 `clz` 系列函式引發的靈感，我著手設計與當今主流大數運算尚未考量到的兩個優化想法：紀錄真正使用位元的首尾範圍、以 Linux 紅黑樹著色技巧儲存符號，並探討相應一系列的實作議題，也介紹我設計的利用遞迴關係惰性建乘法表以進行大數乘法的演算法等，都是現今大數運算可以持續研究的議題。 另由於開始接觸 kernel module 與 linux kernel，我開發 `make2IntelliSense` 腳本，為所有想以 vscode 提升 C/C++ 開發體驗的開發者一個有趣的工具，雖其尚不成熟，但能部分的解決問題，我也將持續改善之。 最後基於前述種種研究成果，開始了本專題的最後一個子項目: Linux kernel trace code 之旅，並發現了當前的實作缺失。經過研究與實驗後得出目前的研究成果有助於改善 Linux kernel 中 `bitops` 套件的 `ffs` 系列函式之軟體實作，待經過更加縝密的驗證與理解 Linux 社群貢獻者的規範後，我將嘗試以 patch 為本研究畫下真正的句點。 透過本專題，我期待能在這些精實硬核的實作中成長並有所貢獻。 ## 參考文獻 1. [數值系統 閱讀紀錄](https://hackmd.io/@Eroiko/c-numerics-rec) (我的學習筆記) 2. [手刻一套 C 語言大數運算之物件導向函式庫](https://hackmd.io/@Eroiko/impl-big-num) (我的旁聽額外紀錄) 4. [VSCode 開發 Linux Kernel Module 的準備](https://hackmd.io/@Eroiko/vscode-for-linux-kernel) (我的旁聽額外紀錄) 5. [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 23. [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHJLyQaQMl) 48. [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization?type=view#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B7%A8%E8%AD%AF%E5%99%A8%E5%92%8C%E6%9C%80%E4%BD%B3%E5%8C%96%E5%8E%9F%E7%90%86%E7%AF%87) 10. [費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number#%E8%A7%A3%E6%B1%BA%E9%81%8B%E7%AE%97%E7%B2%BE%E6%BA%96%E5%BA%A6%E7%9A%84%E5%95%8F%E9%A1%8C) 25. [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree) 29. [內核層讀寫應用層文件，使用filp_open函數](https://www.twblogs.net/a/5b7aede72b7177392c972a80) 33. [[Linux Kernel慢 慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) 1. [2023q1 Homework3 (fibdrv)](https://hackmd.io/@Eroiko/fibdrv-impl) (我的旁聽作業紀錄) 3. [2023q1 Homework5 (assessment)](https://hackmd.io/@Eroiko/linux2023-assessment) (我的旁聽作業紀錄) 7. [make2IntelliSense](https://github.com/Shiritai/make2IntelliSense) (我的 Github repository) 8. [bitops-patch](https://github.com/Shiritai/linux-bitops-patch) (bitops-patch 子項目調整之 repository) 9. [CFS wiki](https://en.wikipedia.org/wiki/Completely_Fair_Scheduler) 11. [Fibonacci Numbers (Dover Books on Mathematics)](https://www.amazon.com/Fibonacci-Numbers-Dover-Books-Mathematics/dp/048648386X) 12. [In C/C++ what's the simplest way to reverse the order of bits in a byte?](https://stackoverflow.com/questions/2602823/in-c-c-whats-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte) 13. [C03: clz](https://hackmd.io/rdTVGkmxSzyTGV9j05qZvw?view) 14. [Number of trailing zeroes](https://stackoverflow.com/questions/45221914/number-of-trailing-zeroes) 15. [Notes on x86-64 programming](https://www.lri.fr/~filliatr/ens/compil/x86-64.pdf) 16. [Linux MPI source code](https://github.com/torvalds/linux/tree/master/lib/mpi) 17. [GNU Multiple Precision Arithmetic Library](https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library) 18. [CPython source code: libmpdec](https://github.com/python/cpython/tree/main/Modules/_decimal) 19. [An incomplete arbitrary-precision integer arithmetic library](https://github.com/sysprog21/bignum) 20. [Karatsuba algorithm](https://en.wikipedia.org/wiki/Karatsuba_algorithm) 21. [L04: fibdrv](https://hackmd.io/@sysprog/linux2023-fibdrv-d) 22. [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 24. [Standard Predefined Macros](https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html) 26. [Using <linux/types.h> in user programs, or <stdint.h> in driver module code...does it matter?](https://stackoverflow.com/questions/14541536/using-linux-types-h-in-user-programs-or-stdint-h-in-driver-module-code-do) 27. [Hooking](https://en.wikipedia.org/wiki/Hooking) 28. [Read/write files within a Linux kernel module](https://stackoverflow.com/questions/1184274/read-write-files-within-a-linux-kernel-module) 30. [How to develop Linux Kernel Module with vscode without incorrect error detection](https://stackoverflow.com/questions/58386640/how-to-develop-linux-kernel-module-with-vscode-without-incorrect-error-detection) 31. [An IntelliSense Bug When Coding Linux Kernel Module](https://github.com/microsoft/vscode-cpptools/issues/5588) 32. [C/C++ for Visual Studio Code](https://marketplace.visualstudio.com/items?itemName=ms-vscode.cpptools) 34. [Linux kernel source code: compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 35. [Advanced search options](https://code.visualstudio.com/docs/editor/codebasics#_advanced-search-options) 36. [Stupid Python Tricks: VSCODE c_cpp_properties.json for Linux Kernel Development](https://iotexpert.com/stupid-python-tricks-vscode-c_cpp_properties-json-for-linux-kernel-development/) 37. [Instead of Executing Recipes](https://www.gnu.org/software/make/manual/html_node/Instead-of-Execution.html) 38. [glob (programming)](https://en.wikipedia.org/wiki/Glob_(programming)) 39. [Re: Linux kernel environment setup in VSCode](https://www.mail-archive.com/kernelnewbies@kernelnewbies.org/msg22110.html) 40. [[PATCH 0/3] kbuild: clang-tidy](https://lore.kernel.org/all/CAKwvOdkQTFEGaSXj5kHpuqTQ9hFYPWkCAyegQ4jienLaH5x9Ng@mail.gmail.com/t/#me025ddd2bffdd1835f5f19ba4fe657c879fb7056) 41. [Can not use clangd to read linux kernel code](https://stackoverflow.com/questions/70819007/can-not-use-clangd-to-read-linux-kernel-code/71543187#71543187) 42. [https://howardlau.me/programming/debugging-linux-kernel-with-vscode-qemu.html](https://howardlau.me/programming/debugging-linux-kernel-with-vscode-qemu.html) 43. [[PATCH] scripts: add a tool to produce a compile_commands.json file](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1821917.html) 44. [https://github.com/amezin/vscode-linux-kernel](https://github.com/amezin/vscode-linux-kernel) 45. [Linux kernel source code: bitops.h](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 46. [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fconstant_005fp) 47. [Constant folding](https://en.wikipedia.org/wiki/Constant_folding) 49. [CS107 x86-64 Reference Sheet](https://web.stanford.edu/class/cs107/resources/x86-64-reference.pdf) 50. [TEST (x86 instruction)](https://en.wikipedia.org/wiki/TEST_(x86_instruction)) 51. [Is GCC loop unrolling flag really effective?](https://stackoverflow.com/questions/24196076/is-gcc-loop-unrolling-flag-really-effective) 52. [Options That Control Optimization](https://gcc.gnu.org/onlinedocs/gcc-4.5.2/gcc/Optimize-Options.html) 53. [Tell gcc to specifically unroll a loop](https://stackoverflow.com/questions/4071690/tell-gcc-to-specifically-unroll-a-loop) 54. [Function Specific Option Pragmas](https://gcc.gnu.org/onlinedocs/gcc/Function-Specific-Option-Pragmas.html#Function-Specific-Option-Pragmas) 55. [Pragmas](https://gcc.gnu.org/onlinedocs/cpp/Pragmas.html) 56. [Loop-Specific Pragmas](https://gcc.gnu.org/onlinedocs/gcc/Loop-Specific-Pragmas.html) 57. [Maslow's pyramid of code review](https://www.dein.fr/posts/2015-02-18-maslows-pyramid-of-code-review)