March 24, 2007

藝術與核心

以前修過一些通識課程,不能說沒有收穫,但現在只記得課程名稱,大概就是「藝術與人生」或「藝術導論」一類的,具體內容大概忘光了,然,這些訓練是否能讓工學院的學生,發揮藝術素養推廣到其他領域,值得商榷,但 Linux Kernel hackers 做到了。

前幾天在 IRC 上聊到 LKML (Linux Kernel Mailing-List) 有一份由 Rusty Russell 所提交的 patch:[Use more gcc extensions in the Linux headers],實在令人讚嘆!在探討這個 patch 之前,稍早在 blog [sizeof 在語言層面的陷阱] 提及 C/C++ 程式語言可透過 sizeof 運算子來取得陣列的元素個數,比方說 macro 定義:
#define getNumberInArray(a) \
	(sizeof(a) / sizeof(a[0]))
想法很簡單,但充斥許多陷阱,首先 macro 根本不能作型態檢查,只是笨笨的代入,當然,能夠從事低階開發者應該不至於犯下這類會造成 pre-processor 無法正確運作的小錯誤。但這類名如 getNumberInArray 的 macro 總是讓人誤解,很直觀就可能把 char * 代入,而非正確的 char [],如此一來,造成的錯誤就相當嚴重 (實際計算一次就知道),在之前的 blog [C-style 字串的最佳化] 即提過這兩者表示在本質上的落差。

回過來看 Rusty Russell 提交的 patch:
diff -r f0ff8138f993 include/linux/kernel.h
--- a/include/linux/kernel.h	Fri Mar 09 16:40:25 2007 +1100
+++ b/include/linux/kernel.h	Fri Mar 09 16:44:04 2007 +1100
@@ -35,7 +35,9 @@ extern const char linux_proc_banner[];
 #define ALIGN(x,a)		__ALIGN_MASK(x,(typeof(x))(a)-1)

 #define __ALIGN_MASK(x,mask)	(((x)+(mask))&~(mask))
 
-#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)

 #define FIELD_SIZEOF(t, f) (sizeof(((t*)0)->f))
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
 #define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
看來我們一廂情願的簡單寫法被推翻,改為上述由三行組成的 macro 定義。寫個簡單的程式來看其運作的情況:
#include <stdio.h>
#define ARRAY_SIZE(arr) \
  (sizeof(arr) / sizeof((arr)[0]) \
  + sizeof(typeof(int[1 - \
                      2*!!__builtin_types_compatible_p(typeof(arr), \
                                                       typeof(&arr[0]))]))*0)
int main()
{
        char array[50];
        char *ptr = NULL;

        printf("array size of array = %d\n", ARRAY_SIZE(array));
        printf("array size of ptr = %d\n", ARRAY_SIZE(ptr));
        return 0;
}
我們特意把 char * 代入 ARRAY_SIZE 中,看看編譯器會怎麼處理::
$ gcc -o sizeof-new sizeof-new.c 
sizeof-new.c: In function 'main':
sizeof-new.c:13: error: size of array 'type name' is negative
"typeof" 是 C99 提出的新運算子,簡單定義就是 "referring to the type of an expression",在 Linux kernel 中也做了相容舊編譯器的 macro,不過這不是本文的重點。第十三行就是 ARRAY_SIZE(ptr),編譯器阻止了 typeof 的操作,因為得到非正整數長度的陣列,也就是說,"1 - 2 * *!!__builtin_types_compatible_p(typeof(arr), typeof(&arr[0]))" 表示式運算結果為 -1。看到 "__builtin_" 開頭的函式就知道,一定又是 GCC extensions,而 __builtin_types_compatible_p 用以判斷一個變數的類型是否為某指定的類型,若是則回傳 1,反之傳回 0,詳情可參考 GCC 文件 [Other built-in functions provided by GCC],以下節錄重點:
    The type int[] and int[5] are compatible. On the other hand, int and char * are not compatible, even if the size of their types, on the particular architecture are the same. Also, the amount of pointer indirection is taken into account when determining similarity. Consequently, short * is not similar to short **. Furthermore, two types that are typedefed are considered compatible if their underlying types are compatible.
所以我們可透過這樣的機制來斷定 char * 與 char [] 的不相容型態,所以我們理解方括號 (也就是 "[" 與 "]" 所包圍的表示式) 中的奧義,那麼,為何最後要乘以零呢?考量到編譯器的語意分析,這個技巧可避免可能的編譯影響,又,__builtin_types_compatible_p 總是回傳 0 或 1,所以上述的 "!!" 事實上可忽略,"!!" 其實就是兩個 "!" (not) 運算子,這也是另一個技巧,想一想 !(! 100) 與 !(! -100) 的輸出就知道為何了,這可確保輸出必定是 0 或 1 二元結果。

因為這些組合實在頗為「花俏」,Linus Torvalds 就 [回覆] 說:
    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.
嗯,"that's a work of art.",多麼奇妙的藝術啊!我們上了一堂名為「藝術與核心」的課程 *笑*

喔,後面的討論也很有趣,除了中間考慮 Intel C/C++ compiler 的 [相容性] 外,其他開發者還戲謔的加入 "GCC is awesome." 與 "GCC leaves me speechless." 一類的註解,Randy Dunlap 還正經的補充:
    "awesome" can mean "inspiring awe or admiration or wonder" (amazing) or it can mean "awful" (as in terrifying). 8)
事實上,我們也可將上述 macro 改寫為:
#define ARRAY_SIZE(arr) \
    (sizeof(arr) / sizeof(((typeof(arr)){})[0]))
簡單多了,先不看裡面的「魔法」(別盯著 "{" 與 "}" 猛看,是的,就是那樣),我們寫個小程式測試:
#include <stdio.h>
#define ARRAY_SIZE(arr) \
   (sizeof(arr) / sizeof(((typeof(arr)){})[0]))

int main()
{
        char array[50];
        char *ptr = NULL;

        printf("array size of array = %d\n", ARRAY_SIZE(array));
        printf("array size of ptr = %d\n", ARRAY_SIZE(ptr));
        return 0;
}
同樣也是拿來編譯,看看有什麼輸出:
$ gcc -c sizeof-new2.c
sizeof-new2.c: In function 'main':
sizeof-new2.c:10: error: empty scalar initializer
sizeof-new2.c:10: error: (near initialization for '(anonymous)')
一言以蔽之,這還是「魔法」,只是工程意味比較重,沒有上面的作法來得「藝術」,但都達到避免 pointer 代入 macro 的功能。作個簡化的程式,用以解說上面的作法:
#include <stdio.h>
int main()
{
        char array[10];
        printf("Magic=%d\n", sizeof((typeof(array)[10]) { "\0" }));
        return 0;
}
編譯並執行:
$ gcc -Wall sizeof-new2.c
$ ./a.out
Magic=100
這裡用到一個 GCC extension,可直接作 assignment,當我們以 typeof 運算子取得該型態後,隨即建立 10 個單元的陣列,並賦予其初始值。事實上我們還可進一步簡化 '{ "\0" }' 為 "{}",然後將第二個 [10] 移去,就接近上述的表示法。分別以 char [] 與 char * 代入時,可發現 GCC 回報不同的訊息,前者可通過編譯 (符合 GCC extension),後者則有 "empty scalar initializer" 的錯誤。

當然,這只是冰山一角,Linux kernel 裡面尚有無窮盡的「藝術」,值得我們去探討。美學大師蔣勳曾說過:「美的本質是創造力」,我想這是 Linux 迷人之處,透過自由開放的發展,將創造力激發得淋漓盡致。
由 jserv 發表於 March 24, 2007 12:42 AM
迴響

真是篇易懂好讀又精彩的文章!

penk 發表於 March 24, 2007 03:24 AM

我寫了一篇文章,以避免使用 extension
http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/236

Thinker 發表於 March 24, 2007 03:07 PM

oops, 我沒聽過

> "typeof" 是 C99 提出的新運算子

翻了翻幾個 C99 的文件,沒有提到 typeof 過,
雖然這一直是我很想要有的東西。在 C++ 中,
boost 有實作一個 macro 叫 BOOST_TYPEOF
http://www.boost.org/regression-logs/cs-win32_metacomm/doc/html/typeof.html
(在寫 template metaprogramming 時很有用)

另外我 google 了一下找到這個:

http://tigcc.ticalc.org/doc/gnuexts.html#SEC69

所以看起來是 gcc extension.
我個人對 C 和 gcc extension 都沒有研究過,
所以剛看到時覺得有點詫異 :)

godfat 真常 發表於 March 24, 2007 03:57 PM

To godfat,

感謝指正,typeof 的確不在 final C99 中,所以前文描述有誤,但出現於 C Standard Committee Draft 內容,沒記錯的話,我曾讀到 IBM 與 Cygnus Solutions (現為 RedHat) 遞交的提案。

To Thinker,

Excellent! 的確可以這麼解,非常感謝。

jserv 發表於 March 24, 2007 07:39 PM
發表迴響









記住我的資訊?