C Struct Hack - Structure with variable length array

前些日子在書上看到一種很特別的structure：


其中值得注意的是romfs_super_block這個structure中包含了一個size為0的name陣列
Array的size為0?
為啥要這樣特別宣告一個"不佔空間"的array?

在搜尋了GCC manual後發現這樣的"Zero length array"其實是有意義的...

6.17 Arrays of Length Zero

Zero-length arrays are allowed in GNU C. They are very useful as the last element of a structure that is really a header for a variable-length object:

     struct line {
       int length;
       char contents[0];
     };
   
     struct line *thisline = (struct line *)
       malloc (sizeof (struct line) + this_length);
     thisline->length = this_length;

In ISO C90, you would have to give contents a length of 1, which means either you waste space or complicate the argument to malloc.

In ISO C99, you would use a flexible array member, which is slightly different in syntax and semantics:

• Flexible array members are written as contents[] without the 0.
• Flexible array members have incomplete type, and so the sizeof operator may not be applied. As a quirk of the original implementation of zero-length arrays, sizeof evaluates to zero.
• Flexible array members may only appear as the last member of a struct that is otherwise non-empty.
• A structure containing a flexible array member, or a union containing such a structure (possibly recursively), may not be a member of a structure or an element of an array. (However, these uses are permitted by GCC as extensions.)

GCC versions before 3.0 allowed zero-length arrays to be statically initialized, as if they were flexible arrays. In addition to those cases that were useful, it also allowed initializations in situations that would corrupt later data. Non-empty initialization of zero-length arrays is now treated like any case where there are more initializer elements than the array holds, in that a suitable warning about "excess elements in array" is given, and the excess elements (all of them, in this case) are ignored.

Instead GCC allows static initialization of flexible array members. This is equivalent to defining a new structure containing the original structure followed by an array of sufficient size to contain the data. E.g. in the following, f1 is constructed as if it were declared like f2.

     struct f1 {
       int x; int y[];
     } f1 = { 1, { 2, 3, 4 } };
   
     struct f2 {
       struct f1 f1; int data[3];
     } f2 = { { 1 }, { 2, 3, 4 } };

The convenience of this extension is that f1 has the desired type, eliminating the need to consistently refer to f2.f1.

This has symmetry with normal static arrays, in that an array of unknown size is also written with [].

Of course, this extension only makes sense if the extra data comes at the end of a top-level object, as otherwise we would be overwriting data at subsequent offsets. To avoid undue complication and confusion with initialization of deeply nested arrays, we simply disallow any non-empty initialization except when the structure is the top-level object. For example:

     struct foo { int x; int y[]; };
     struct bar { struct foo z; };
   
     struct foo a = { 1, { 2, 3, 4 } };        // Valid.
     struct bar b = { { 1, { 2, 3, 4 } } };    // Invalid.
     struct bar c = { { 1, { } } };            // Valid.
     struct foo d[1] = { { 1 { 2, 3, 4 } } };  // Invalid.

會有這樣的用法是我們希望可以宣告一個structure包含一個不定大小的記憶體空間
如同上述GCC manual的範例：

struct line {
    int length;
    char contents[0];
};
 
struct line *thisline = (struct line *)
  malloc (sizeof (struct line) + this_length);
thisline->length = this_length;

我們希望line這個structure後面可以接著一個this_length大小的記憶體空間
(其中this_length為我們自己定的值)
也就是此structure的size為：4 (int length) + this_length
而contents這個陣列的所在位址正好會等同於這段this_length大小的記憶體空間的開頭

由於sizeof()用在char contents[0]本身會回傳0
因此sizeof(line)會回傳的值即為4 (也就是int length的大小)
但除此之外，在使用malloc()的時候我們亦多分配了this_length大小的記憶體空間

由於GNU C compiler預設並不會檢查"Array index out of bounds"這個問題
因此透過這樣的方式，我們便可以透過contents來存取structure line後面的this_length大小的記憶體空間：

strncpy(contents, "Frank Chang", strlen("Frank Chang") + 1); // (+1 for '\0')

如此，contents的內容就會變為"Frank Chang"這個字串

但在C90之前，Zero-length array是不被允許的
因此以前的C Struct Hack用的方法是將contents改宣告為size為1的array
但在使用malloc()配置記憶體空間時要多扣掉contents本身所佔的空間 (char [1])：

struct line {
    int length;
    char contents[1];
};
 
struct line *thisline = (struct line *)
  malloc (sizeof (struct line) + this_length - 1);
thisline->length = this_length;

(實際上，我們還要考慮到padding的問題，因此在此的sizeof(struct line)會回傳8，而不是原先所預期的5)

總之，不管是用哪種方法，都是透過GNU C compiler預設並不會檢查"Array index out of bounds"這個問題的技巧來存取我們所分配給structure的多餘空間

但其實這樣的Hack技巧本身是違反C Standard的
這也是為何C語言的作者 - Dennis Ritchie 會稱這樣的技巧為： "Unwarranted chumminess with the C implementation"

因此在C99後，多新增了"Flexible array member"的技巧來完成上面所述之需求

struct line {
    int length;
    char contents[];
};
 
struct line *thisline = (struct line *)
  malloc (sizeof (struct line) + this_length);
thisline->length = this_length;

其中contents本身為一個incomplete type的陣列
sizeof()在處理一個incomplete type的陣列時會自動忽略
因此sizeof(struct line)仍會回傳4

但就如同GCC manual所述，sizeof()並不可使用在incomplete type的變數上
因此：

sizeof(thisline->contents);

在編譯時會產生："Invalid application of 'sizeof' to incomplete type 'char []'"的錯誤訊息

此外，Flexible array member只可宣告為一個non-empty structure的最後一個成員
因此以下的宣告方式都會造成編譯錯誤：

// Error: flexible array member in otherwise empty struct
struct line {
    char contents[];
};

// Error: flexible array member not at end of struct
struct line {
    char contents[];
    int length;
};

不過GCC manual所述： A structure containing a flexible array member, or a union containing such a structure (possibly recursively), may not be a member of a structure or an element of an array. (However, these uses are permitted by GCC as extensions.)
(P.S. Flexible array member本身不可以被宣告在union之中)
在個人的測試中卻都是可以使用GCC compiler編譯成功的...
(或許就是上述最後一句，GCC將此當作extensions來處理了所以才不會產生編譯錯誤)

但在使用上很有可能會造成嚴重的潛在問題
如下面的範例：


在此範例中，我們宣告了一個struct line包含了一個flexible array member - char contents[]
另外又在宣告了一個struct lines包含了struct line
在main()中我們宣告了一個struct lines的ls變數和包含10個struct line的line_array陣列

這樣的程式使用GCC是可以編譯成功的
但在執行時會發生"*** stack smashing detected ***"的錯誤
原因就在於我們所宣告的ls為一個區域變數
Compiler替我們分配的空間就是struct lines的大小： 8 (sizeof(struct line) + sizeof(int) = 4 + 4)
但由於contents的記憶體位址等同於line_num的記憶體位址
因此當我們複製超過4個bytes的資料時便會破壞了stack
進而造成了"*** stack smashing detected ***"的錯誤

除此之外，假設我們將第19行的strncpy()註解掉
使其不會破壞stack內容，程式便可順利執行完畢
但line_array[5]的內容同樣會被破壞
原因類似於上述stack的問題
line_array[4]中contents的記憶體位址等同於line_array[5]中length的記憶體位址
因此當我們複製任何資料給line_array[4].contents時便會修改到line_array[5].length及其後的內容

第一個stack的問題可以透過改用malloc()的方式來避免
或是將struct lines ls改宣告成全域變數
(但當複製超過4個bytes資料時，可能還是會碰壞到.bss section或是.data section內的內容?!)

但第二個陣列的問題則完全沒有方法可以避免.....

個人認為使用這種Struct Hack技巧在程式的維護上是相當麻煩的
在寫程式的時候應該盡量避免使用到這樣的方法

況且我們通常只會在structure中包含一個指標指向其他的記憶體空間來避免這樣的問題
E.x.

struct line {
    int length;
    char *contents;
};

我們只要再將其中的contents指標指向其他的記憶體空間即可
但為何還是會有這樣的用法呢?

原因就在於使用這樣的方式會有以下的好處：

• 使用flexible array member所宣告出來的陣列其記憶體空間是與其他的structure members的記憶體空間連續的 (因為可以透過一個malloc()來分配所需的記憶體空間)，若該structure會被經常性的存取，則這樣的方式可以增加cache hit的機率 (基於Spatial locality的因素)

此外，某些自訂的資料結構就是規定該不定長度的空間就是得接續著其他的structure members
如本篇文章最初所舉之romfs_super_block這個structure
該name陣列 (為不定長度) 就是規定其記憶體空間得接在checksum變數之後
(romfs_super_block為ROM filesystem的檔案系統頭訊息，其layout如下：

由此可見，volume name (為不定長度) 必定得接在checksum之後才行)

但不論如何，除非必要，而且你/妳非常清楚自己在做些什麼
否則還是盡量少用這樣的Struct Hack技巧
以免造成日後除錯及維護上的困難
畢竟這樣的技巧所導致的錯誤是很難直觀地被發現的.....

------------------

額外參考資料：

• Zero Length - Using the GNU Compiler Collection (GCC)
• Questions & Answers: Creating Variable-size structs | Dr Dobb's
• Question 2.6 - C Struct Hack
• C Struct Hack | My Blog   (P.S. 該文中說無法定義"Zero length array"在C90之後是可行的)
• Struct Hack - GeeksforGeeks | GeeksforGeeks