HackMDLinux 核心專題: 回顧 bitops 並改進
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
__gen_fls與gen_fls只差在bit_len這項輸入。想問分開的好處？有兩個好處。
- 呼叫者不需要輸入
bit_len參數，因為這可以從輸入型別直接推得，不過我想您想問的應該不是這點。 bit_len這項輸入在__gen_fls中用上兩次，如下
#define __gen_fls(in_type, out_type, start_from, fn_name, bit_len) \ static __always_inline out_type fn_name(in_type x) \ { \ /* ... */ \ shift = bit_len >> 1; \ bits = bit_len - 1 + start_from; \如果不以一個參數包裝
sizeof(in_type) * 8，我們就需要在__gen_fls中寫兩遍sizeof(in_type) * 8，這增加了維護程式碼的一咪咪成本。使用間接的巨集生成函式不僅避免這個成本，同時不影響編譯完的結果，所以我採用此方法。換言之，增加一層間階層同時讓:
- 呼叫者呼叫的更優雅
- 實作者簡化實作邏輯
可謂兩邊都受惠 OwO
希望這樣有解答您的提問。Shiritai
- 呼叫者不需要輸入
任務簡述
Linux 核心的 include/asm-generic/bitops 存在若干實作不一致的狀況，本任務嘗試追蹤 git log 和 LKML，以理解發展脈絡，並嘗試用精簡有效的方式改寫，最後嘗試貢獻程式碼到 Linux 核心。
TODO: 理解 bitops 實作風格和目標
bitops 本身為 Linux kernel 中的一個套件，當中實作 ffs 系列函式，他們被用在核心的其餘諸多地方，這點可以簡單利用 vscode 對 ffs, __ffs, fls, __fls, fls64, ffz 這些函式進行搜尋便可得知。一個經典的應用是 CFS (completely fair scheduler) 的排程上，會呼叫 bitops/sched.h 中的 sched_find_first_bit 函式，後者又呼叫 __ffs。
由 clz 系列函式的實作為引子，經翻閱 Linux 原始碼中 ffs 系列函式後，整理其概況與問題，列敘如下。
ffs 及 __ffs 加雙底線與否的不同
首先先釐清 ffs 及 __ffs (是否加雙底線) 的不同之處：參考 bitops 系列對外的介面: arch/arc/include/asm/bitops.h 中的註解得知
__XXX系列: 以 index 0 索引，範圍為0 ~ {length of input type - 1}XXX系列: 以 index 1 索引，範圍為1 ~ {length of input type}
採用硬體實作與否
GCC 除了提供 __builtin__c{l,t}z 對硬體指令包裝的內建函式外，實際上也存在 __builtin_ffs。就算沒有此函式，用前兩個也足以解決 ffs 和 fls 的實作。不過並不是所有指令集都實作對應的硬體指令，所以才有 linux 核心中 ffs 系列的軟體實作。核心透過條件編譯決定最後應該採用哪種實作，而本子項目的重點將先放在軟體實作的部分。
接著來探討現有實作的問題。
詭異的實作不一致性與例外情況
凡是掛名 __builtin_XXX 的函式本身以 CPU 硬體指令實作，過濾例外情況 ffs, fls 時輸入
不過有趣的是，bitops 目錄下大家眾口一詞：有的說例外情況的判斷交由 caller 檢查，有的沒特別說 (只說其與 builtin ffs 有同樣的 routine)，有的直接為
- 例外情況的判斷交由 caller 檢查
// __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)// 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; ... - 為
/** * 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 的存在意義
arch/arc/include/asm/bitops.h 中存在一函式 constant_fls，簽名與部分實作如下:
static inline int constant_fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xffff0000u)) {
x <<= 16;
...
}
其目的是利用 gcc __builtin_constant_p 協助於編譯時期進行 Constant folding (propagation)，於你所不知道的 C 語言：編譯器和最佳化原理篇介紹過其觀念。以下節錄 gcc 官方文件，說明 __builtin_constant_p 的使用:
You can use the built-in function
__builtin_constant_pto determine if a value is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value. …… A return of
0does 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-Ooption.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
1when you call the inline function with a string constant or compound literal (see Compound Literals) and does not return 1 when you pass a constant numeric value to the inline function unless you specify the-Ooption.
表示當 __builtin_constant_p 用於 macro 或 inline function 時，傳入的參數為 常數數值，當開啟編譯器最佳化 -O 選項後即會進行 constant folding。
綜觀 constant_fls 函式，我們看不出其與 bitops/fls 有任何差別。這表示就算不實作 constant_fls，也能利用上述 bitops/fls 函式協助編譯器進行 constant folding。
那麼問題就出現了：
constant_fls實作的意義為何？- 若調整
bitops/flz或constant_fls的實作，對於bitops.h中fls傳入參數為__builtin_constant_p(x) == 1時的效能是否有影響？即是否有可能影響 constant folding？
另附上唯一的呼叫者 bitops.h 中 fls 函式以供參考。
/*
* 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 亦同)
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 亦同) 可沒打算那樣做:
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 (就是前述沒有存在意義的函式) 倒是考慮到了這點。
目標
透過觀察前述古怪現象，其中一個解決方法便是使用我分析 clz 軟體實作的成果: 以 button-up 的角度分析位元運算版實作，一步步將 Magic Number 抽象出來，在不斷維持原功能的相容性下擴展新功能。好處有以下：
- 程式碼簡潔
- 可以輕鬆維護並同步現有不同輸入輸出型別之
f{f,l}s系列函式的軟體實作 - 統一 Undefined behavior 的處理方式
- 為未來
但若直接移植我的解決方案而不經任何調整，將會有以下缺點：
- 舊方案無法處理有無雙底線如
__ffs等函式的實作 - 效能降低
對於第一項，我們可以調整函式的生成邏輯，增加可控變因來嘗試完成。對於第二項，目前將透過進一步理解編譯器的優化行為嘗試解決。
TODO: 用一致的實作手段改寫 bitops 程式碼
擴展巨集的功能
透過定義額外兩個供其他開發者使用的巨集常數
#define __FFLS_START_INDEX_FROM_ZERO 0
#define __FFLS_START_INDEX_FROM_ONE 1
我調整 ffs (fls 同理) 函式如下:
/**
* 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 組語小實驗開始
我嘗試將自己的舊版 ffs 巨集生成函式置於 util.h 轉為組語，其在 main.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 帶優化的編譯，產生的組語節錄如下：
...
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。
__gen_ffs中mask變數確實透過編譯器的協助轉為常數65535(0xffff)，這符合預期。- 更進一步的，將上述
util.h第 13 行改為mask = (in_type) ~(_ONES << shift);後編譯為組語，發現得到一樣的結果。 - 本來顧慮到不使用全部直接是常數的巨集產開下可能導致 gcc 不會正確預先求出
mask常數，事實證明編譯器實在太聰明了！
- 更進一步的，將上述
my_ffs(使用巨集生成的ffs函式) 組語迴圈也很有趣。- 查詢
x86的test指令發現，原來其非迴圈條件判斷，而是 bitwise AND 運算，對應第 13 行x & shift的部分。 - 原來編譯器自動幫我將
while轉為do-while，不得不說真的很聰明，直接體會到編譯器的強大。
- 查詢
實作 Loop unroll
編譯器神通廣大，即使沒修過編譯器的我都聽過其中一個知名的功能：loop unrolling。透過將迴圈展開為只向下執行的程式碼，降低指令往前轉跳的 control hazard 和 instruction cache 成本。
參考本討論串，其討論到適合使用 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 這個 gcc 編譯參數，其嘗試在編譯時期展開可預測迴圈執行次數的迴圈:
cc main.c -O -funroll-loops -std=c99 -S
(左: 原版，右：unroll loops 版)
成功得到展開後的迴圈，而且由於將邏輯迴圈化之前的重複次數本來就很少，展開後才只多七行，除了預見效能的提升外想不到其他可能。
更令我驚訝的是，除了能正確的 unroll loop，針對整數輸入型別展開為 5 次 x 做無謂的運算，也就是 .L6 中不存在對 %eax (x) 的右移指令。
換言之，若將我的巨集生成函式應用於 Linux Kernel ffs/fls 系列函式的實作，有可能不會影響其效能。實際上是真的不會，詳見後續實驗，但在此之前有個問題，就是如果需要調整 kernel 編譯時的編譯參數，恐怕會影響其他程式碼，我們應該限制 loop unroll 只作用在由我們巨集生成函式產生的迴圈上。
精準最佳化：調整 compile 時特定位置採取的優化策略
同前述，我們希望 kernel 於編譯時，與 ffs 相關的部分採用 GCC 編譯時傳入 unroll-loops 參數的效果。
直接調整編譯參數有點不切實際，原因如下：
- 只希望 unroll 生成出來的函式，不希望影響到其他函式。
Linux 的 makefile 們 trace 起來好痛苦
另一方面，我想到 gcc 可能提供了額外的標記來解決問題，於是找到本討論串，其介紹了兩種方法：
pragma + GCC global optimize + push pop: 在函式前為 GCC 增加全域優化設定，函式後取消該新增。pragma表示編譯提示。#pragma GCC push_options #pragma GCC optimize ("unroll-loops") // function with loops to be unrolled #pragma GCC pop_options- 新增
attribute: 在函式前加上__attribute__((optimize("unroll-loops"))) // function with loops to be unrolled
於是我嘗試實驗這兩者於以下編譯環境：
> gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
發現後者沒有效果，前者雖然有，但不知為何在巨集生成函式下沒有效果。我嘗試過以下做法：
-
直接暴力放
pragma
會報錯，在define中不能用#...，故#pragma不能使用。(語法錯誤)。#define ... \ #pragma GCC push_options \ #pragma GCC optimize ("unroll-loops") \ \ /* function with loops to be unrolled */ \ \ #pragma GCC pop_options -
利用 C99 的功能:
_Pragma運算子替代#pragma巨集
這下語法不會錯誤了。但奇妙的是，這樣寫編譯後發現沒有效果！#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: 前述方法都是針對整個函式，經查找 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運算子將程式改為：#define ... \ ... \ _Pragma("GCC unroll 6") \ do { \ ... \ } while (shift); \ ...指定
不過此時讀者可能會好奇，這樣不就限制我抽象為巨集生成函式的作法只能用於
答案是其實不會！
雖然規格書沒有詳細提及，不過我以實驗測試 unroll 次數自 0 至 100。結果表明，當可 unroll 的次數
funroll-loops本來就有能力分析迴圈合理的展開次數。更進一步的，若未來出現
更進一步，實作 clz/ffs 系列函式全家桶
Linux kernel 中尚未針對 c{l,t}z 系列函式直接提供軟體實作。以下嘗試沿用 f{f/s}s 的成果，以接近相同的實作一口氣實作 clz/ffs 系列函式全家桶。
clz/ffs 全家桶說明
常見的 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)
他們針對不同的
- 輸入
- 輸出
- 未定義行為
而有不同的實作。不過一個很有趣的現象是 clz 函式們彼此間的關係，以下式說明。
可見這些函式實際上可能只需實作 clz/ctz 或 ffs/fls 即可，其他函式只需調整一些即可。
實作全家桶
在我的實作中，全家桶的關係如下圖：方形表對面向使用者的函式，橢圓表巨集生成函式 (__ffs、__fls、ffz、constant_fls 等請見 bitops-patch 子項目)。
透過活用一開始設計來提供使用者客製化用的之巨集常數 __FFLS_START_INDEX_FROM_{ZERO,ONE}，以 f{f,l}s 實作 c{l,t}z 只在彈指之間。節錄實作如下：
#define __FFLS_START_INDEX_FROM_ZERO 0
#define __FFLS_START_INDEX_FROM_ONE 1
// hidden implementation
#define __gen_ffs(in_type, out_type, start_from, fn_name, bit_len) \
... // just like ctz
// developers should call this
#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))
// hidden implementation
#define __gen_fls(in_type, out_type, start_from, fn_name, bit_len) \
... // just like clz
// developers should call this
#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))
// hidden implementation
#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); \
}
// developers should call this
#define gen_clz(in_type, out_type, fn_name) \
__gen_clz(in_type, out_type, fn_name, (sizeof(in_type) * 8))
// developers should call this
#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))
// hidden implementation
#define __gen_ffz(in_type, out_type, fn_name, bit_len) \
__gen_ffs(in_type, out_type, \
__FFLS_START_INDEX_FROM_ZERO, \
__ffs_##fn_name, bit_len); \
static __always_inline out_type fn_name(in_type x) \
{ \
return __ffs_##fn_name(~x); \
}
#define gen_ffz(in_type, out_type, fn_name) \
__gen_ffz(in_type, out_type, fn_name, (sizeof(in_type) * 8))
可以發現實作 clz 和 ffz 的過程中額外生成了幫手 fls (__fls_##fn_name)、ffs (__ffs_##fn_name) 函式，至於對於
- 程式碼多餘與否
- 機械碼長度
- 執行時期效能
等指標而言是不是一個好的做法，又是一個可以加以探討的話題。
效能探討
今以以下簡單的程式來測試，後者 (巨集生成迴圈版) 有兩個版本，一個是尚未使用 loop unroll 的版本，另一個有使用。
// 原始版本
for (long long i = 1; i < 1000000; ++i) {
assert(__builtin_ffsll(i) == ffs_ll(i));
assert(__builtin_ffsll(i + __INT32_MAX__) ==
ffs_ll(i + __INT32_MAX__));
}
// 巨集生成迴圈版 (no loop unroll)
for (long long i = 1; i < 1000000; ++i) {
assert(__builtin_ffsll(i) == my_ffs_ll(i));
assert(__builtin_ffsll(i + __INT32_MAX__) ==
my_ffs_ll(i + __INT32_MAX__));
}
// 巨集生成迴圈版 (loop unroll)
for (long long i = 1; i < 1000000; ++i) {
assert(__builtin_ffsll(i) == my_ffs_lu_ll(i));
assert(__builtin_ffsll(i + __INT32_MAX__) ==
my_ffs_lu_ll(i + __INT32_MAX__));
}
實驗環境如下。
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 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
以 perf 為測試工具，測試指令如下：
gcc main.c -std=c99 -O -o a -g3 && sudo perf stat --repeat 1000 ./a
分別測試上述三種不同的實作，得到如下結果：
| index | 原始版本 | 巨集生成迴圈版 no loop unroll |
巨集生成迴圈版 loop unroll |
|---|---|---|---|
| Execution time (ms) |
3.48 | 9.26 | 3.52 |
| Branches | 15.35M | 32.34M | 15.34M |
| Branch miss (% of all branch) |
0.18 | 0.16 | 0.19 |
| IPC | 3.65 | 2.89 | 3.62 |
可見在尚未配合編譯器優化前的實作與原始相比，執行時間大約為原始的 2.6 倍，雖然 branch miss 比率較低，但總 branches 指令為原本的近兩倍 (這是高度可以預期的，因為每輪迴圈都需要一次結束判定)，故 IPC 比原本低，影響執行時長。
而採用 loop unroll 編譯器精準優化後，執行時間為原本的 1.094 倍，幾乎不受影響，而 branches 數也說明 loop unroll 成功把迴圈結束判定的邏輯給展開去除，得到近乎一樣的結果，在 branch 數與 branch miss 相近的情況下，IPC 也很接近，執行時長自然相近。
實驗結論是：本專題的優化幾乎不會影響效能。
TODO: 確認改寫的程式碼得以在 Linux 核心運作
應搭配 user-mode-linux 或 virtme (第 7 週教材) 來驗證
實作
在實作精準的 loop unroll 後，下一步是實作於 Linux kernel。
首先我建立新檔案 ffls_gen.h，加入前述 ffs、fls 巨集生成函式。接著修改 ffs.h、fls.h、__ffs.h、__fls.h、fls64.h、bitops.h 等檔案，調整實作如下兩例，其餘皆依樣畫葫蘆：
// in __ffs.h
gen_ffs(unsigned long, unsigned long, __FFLS_START_INDEX_FROM_ZERO, __ffs);
// in ffs.h
gen_ffs(unsigned int, int, __FFLS_START_INDEX_FROM_ONE, ffs);
初步測試
為了測試方便，我先粗暴的調整 __builtin-ffs.h、__builtin-__ffs.h 等一系列採用硬體指令版的實作為與軟體版的相同，並以 User mode linux 編譯運行，得到無任何錯誤的編譯、運行結果。
TODO: 統計/預估藉由導入上述程式碼的修改後，現行 Linux 核心原始程式碼可減少幾行程式碼，及簡述提升程式碼維護的效益
減少程式碼行數
在 10 處重複實作的程式碼中 (不考慮註解的話):
- 實作巨集函式們於
include/asm-generic/bitops/ffls_gen.h: 增加clz/ctz/ffz巨集，若連註解都算的話增加 tools/include/asm-generic/bitops和include/asm-generic/bitops下一樣的實作__ffs.h: 減少__fls.h: 減少fls.h: 減少fls64.h: 減少
include/asm-generic/bitops/ffs.h減少arch/arc/include/asm/bitops.h減少
共計減少 clz/ctz/ffz 巨集都算的話減少
提升程式碼維護的效益
- 對於所有輸入輸出資料型別、長度、起始索引為零或一，統一其未定義行為，保證安全。
gen_ffs/gen_ctz產生的函式於輸入為gen_fls產生的函式於輸入為- (承上)
gen_clz輸入為 gen_ffz輸入為全一時輸出為
- 針對位元運算迴避有號輸入型別可能產生的符號擴展，保證安全。
- 向舊有程式碼 (起始索引為 0 或 1，各式輸入輸出型別) 兼容的同時，在不用調整編譯參數的情況下擁有近乎相同的效能。
- 對未來比如 128 bits 的資料型別，僅需微調巨集展開次數與全一立即數，即可產生向長度 128 bits 以下兼容的程式碼，優雅。
- 要實作其他輸入輸出型別的 ffs/fls/ffz/cls/ctz 函式，每次僅需撰寫一行即可產生固定邏輯的函式，四兩撥千斤，優雅且利他。
我認為是值得出現在 linux kernel 的程式碼。
TODO: 提供程式碼貢獻到 LKML
To be continue… Shiritai
