Linux kernel - GCC 的藝術 - Alignment

收錄在 AIoT Ameba 2020 - Just for Fun

--
GCC 今年進到二位數了
https://gcc.gnu.org/gcc-10/changes.html

Jserv 大神 有個 你所不知道的 C 語言講座 , 影片: youtube 頻道
和這張圖:

GNU 有很多 C extension, Linux kernel 也很常見到使用 GNU extension,  譬如 typeof

而這張圖是 Rusty Russell 在 2007 年提交 patch 的故事. 
( 在 Jserv 2007 年的 blog 也有提到 - http://blog.linux.org.tw/~jserv/archives/001888.html )

https://lwn.net/Articles/226010/

__builtin_types_compatible_p() has been around since gcc 2.95, and we
don't use it anywhere.  This patch quietly fixes that.

-#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])         \
+ + sizeof(typeof(int[1 - 2*!!__builtin_types_compatible_p(typeof(arr), \
+   typeof(&arr[0]))]))*0)

https://lwn.net/Articles/226011/

Linus 回答: 

Whee.

Rusty, that's a work of art.

However, I would suggest that you never show it to anybody ever again. I'm 
sure that in fifty years, it will be worth much more. So please keep it 
tightly under wraps, to keep people from gouging their eyes out^W^W^W^W^W^W^W 
make a killing in the art market.

Please.

  Linus

"真的是藝術呀. 希望不要再拿出來, 避免大家把自己的眼睛挖出來.. "

( 用時下的話語就是: 亮瞎了我的鈦合金眼... )

的確在十多年後看到仍覺得驚豔, 且這方式越來越受重視. 

 ( 2017 年時, Rusty Russell 在 Linux kernel 已貢獻了 20 年, 離開 Linux maintainer 的職位

( 投身 bitcoin 產業? ) Farewell From Rusty Russell )

這方法目前在 linux kernel 又更簡潔了: 

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))

#define __must_be_array(a) BUILD_BUG_ON_ZERO(__same_type((a), &(a)[0]))

#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))

#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))

這邊用到了幾個技巧: 

1. int __builtin_types_compatible_p (type1, type2)

    https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

    type1 和 type2 是否相同. 相同回傳 1, 不相同回傳 0

    而 &(a)[0] 是指標 而非 陣列, 所以  __same_type((a), &(a)[0])

    如果 a 是陣列會傳回 0, 不是陣列的話傳回 1



2. sizeof(struct { int: -!!(e); })

   https://stackoverflow.com/questions/9229601/what-is-in-c-code

    乍看之下看不懂, 我們一步步拆解: 

    (1) (e)  : 先把這表達式計算出來

    (2) !(e) : 做 NOT, 也就是 (e) 如果為 0 會得到 1, 而 (e) 如果非 0則得到 0

    (3) !!(e) : 再 NOT 一次, 就會得到 0 或 1 值

    (4) -!!(e) : negative 運算, 得到 0 或 -1 值

    (5) struct { int:0 } / struct { int:-1} 

          這邊就是一般 structure 定義 bit 長度 的方法. 可以發現 -1 是錯誤的寫法.

     (6) sizeof (struct {int:0}) 是 0, 所以不會影響到原本計算的結果

     可以發現這寫法又比原本 sizeof(typeof(int[1 - 2 * !!(e)])) * 0 要簡潔

     所以 BUILD_BUG_ON_ZERO(e) 當 e 為 0 時 ok, e 不為 0 時就會產生 compile error.

      ./include/linux/build_bug.h:16:51: error: negative width in bit-field

     那為什麼不用 assert 呢, 因為 assert 是 run-time 時才能決定, 

     而這可以在 compiler time 就能判斷是否正確.



範例:     github






執行結果: 

           a is array

           b is not array

           c is char *

           char *b and int *c are different



====

我們再看另一個 Linux 常用到的 alignment. 

例如 硬體設計是 8bytes 一個 block, 我們有資料大小為 20 bytes, 
就會變成 8 * 2 + 4,  第三個 block 未滿 8 bytes, 會補 4 bytes padding, 
總長度就變成 24 為 8 bytes alignment



常見的做法: 

例如在這邊 有位仁兄把 rtl8822bu driver 放上來, 意外地竟有 37 顆星
( 非官方 release. 不予置評.. )
https://github.com/ulli-kroll/rtl8822bu/blob/master/include/osdep_service.h



這邊的 8 byte alignment 做法: 





   
可以發現, 這作法會有 branch 判斷, 有可能造成 pipeline 中斷而變慢. 
Linux kernel 對於 2的次方數字的, 有個快速的方式


/* @a is a power of 2 value */

#define ALIGN(x, a)        __ALIGN_KERNEL((x), (a))

#define __ALIGN_KERNEL(x, a)             __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)

#define __ALIGN_KERNEL_MASK(x, mask)     (((x) + (mask)) & ~(mask))



( 另外 對於一般非2次方數字的, 也有一個不用 branch 判斷的方式,
  可以發現, 這邊又再用到 typeof 的技巧, 可以宣告一個變數 __y 來取代 y,
  避免 y 被 define macro 重複執行而產生錯誤 )

#define roundup(x, y) (     \
{       \
 typeof(y) __y = y;    \
 (((x) + (__y - 1)) / __y) * __y;  \
}

我們用 GO 寫一下看看兩個方式的差異: 

https://github.com/neojou/go-ameba/tree/master/align-bench

go test -bench=. -benchtime=2s

function 計算太快,都是 26.3 ns/op看不出差異
可以用 2s 能執行的總測試次數來比較

執行結果:


BenchmarkRND8-4     81116832    26.3 ns/op
BenchmarkAlign8-4   89701135    26.3 ns/op

(這次執行大概有 10% increase)

BenchmarkRND8-4     85409115    26.3 ns/op
BenchmarkAlign8-4   88812963    26.3 ns/op

(這次執行大概有 4% increase)


的確沒有 branch 的方式會快一些. 

PS: 意外發現這位仁兄也在做 rtw88-usb
    https://github.com/ulli-kroll/rtw88-usb
    不過 usb_tx 還沒實現, 
    剛提供了正在開發的部分, 看有沒有機會合作^^
    https://github.com/neojou/rtw88-usb