位元組對齊和結構體記憶體佈局
之前遇到一個問題,需要動態計算 C 語言結構體(struct)的記憶體佈局。在此記錄一下。
問題
我使用 MetalKit 實現 GLES 的一些介面。於是在執行時,將 GLSL 在轉換成 Metal Shader Language(下文簡寫成 MSL),之後再編譯這個 MSL。
在轉換 Shader 時,GLSL 的 uniform、attribute、varying 變數分別收集起來,組成一個結構(struct)。比如
uniform float val0; uniform bool val1; uniform float val2[16]; uniform int val3;
會轉換成
struct MtlFragmentUniforms { float val0; bool val1; float val2[16]; int val3; };
在 Metal 中,CPU 往 Shader 中傳遞資料,會使用 Buffer,設定到對應的索引中。CPU 往 Buffer 中寫入二進位制資料,假如這串二進位制資料的記憶體佈局跟 MtlFragmentUniforms 結構一致。Shader 就可以正確獲取到 uniforms 的每個數值。
這裡內部佈局是指結構體本身的大小、結構體內每個欄位的大小,以及每個欄位在結構體中的偏移值。知道欄位的偏移和大小,才能往二進位制資料中正確填入資料。
日常程式設計中,沒有必要過多考慮結構體的記憶體佈局,編譯器在編譯的時候已計算好了。但這裡,MSL 內的結構體是動態生成的,在編譯時期根本還沒有這個結構體,為了使得 CPU 傳入的二進位制資料跟 Shader 中的結構體精確對應,就需要自己來計算內部佈局。
位元組對齊
結構體記憶體佈局涉及到位元組對齊。位元組對齊是指資料放在記憶體中,起始地址的限制。比如 4 位元組對齊,起始地址就需要是 4 的倍數。8 位元組對齊,起始地址就需要是 8 的倍數。假如起始地址為 8,8 是 4 的倍數,因此是 4 位元組對齊,同樣也是 8 位元組對齊。假如起始地址為 9,它就不是 4 位元組對齊了。
為什麼需要位元組對齊呢?
現代計算機中,記憶體每個位元組都有自己的地址,理論上可以從任何起始地址訪問任意型別的變數。但估計是為了簡化電路設計,實際上計算機會將位元組組成一個大點的格子,32 位機器,就以 4 個位元組作為一個格子。64 位機器,就以 8 位元組作為一個格子。在 64 位機上,就算讀取 1 位元組的數值,也需要讀取整個 8 位元組的格子。
下面都是以 LLVM 編譯器,在 64 位機(8 位元組格子)上分析。4 位元組或者 8 位元組的格子,一個緊挨一個,從 0 開始放,因此每個格子必然是位元組對齊的。地址 [0, 8) 是一個格子,[8, 16) 是一個格子。
假如不考慮位元組對齊,就很容易出現數據跨兩個格子的情況。
比如下面結構
struct Base { bool val0; double val1; };
假如不考慮位元組對齊,資料就會一個緊挨著一個。val1 的偏移就是 1,它的大小為 sizeof(double) = 8。假設結構存放在地址 0 位置,val1 佔據的地址就為 [1, 9), 就會同時佔據地址為 [0, 8), [8, 16) 兩個格子了。當記憶體地址不對齊,資料同時佔據兩個格子時,某些機器內部可能自動處理一下,讀取兩個格子的資料,將 double 資料拼接起來,再返回讀取結果,但這樣速度就慢了。而有些機器根本就不支援這種做法,當地址不對齊時,程式會直接崩潰。
因此編譯器在編譯程式碼的時候,會考慮位元組對齊,目的是儘量讓欄位不要跨越兩個格子。這樣做雖然犧牲了一點點記憶體空間,但執行速度會更快,也更安全。
通常來說,在 64 位機下,對於基礎資料型別,它的位元組對齊就是它的 sizeof。比如 bool 型別,sizeof(bool) = 1, 要求 1 位元組對齊,1 位元組對齊就相當於不對齊。而 int 型別,sizeof(int) = 4, 就要求 4 位元組對齊。double 型別,sizeof(double) = 8,要求 8 位元組對齊。
假如是 32 位機,其最大的對齊為 4 位元組。double 型別,雖然 sizeof(double) = 8,但也有可能是 4 位元組對齊,而非 8 位元組對齊。只是我沒有 32 位機,就沒有去測試了。
結構體佈局計算
假如沒有位元組對齊,計算結構體記憶體佈局會很容易。上例中,Shader 中的結構為
struct MtlFragmentUniforms { float val0; bool val1; float val2[16]; int val3; };
我們在轉換時,可以知道每個欄位的名字和型別。也可以知道 sizeof(float) = 4, sizeof(bool) = 1, sizeof(float[16] ) = 64, sizeof(int) = 4。
假如沒有位元組對齊,結構體欄位就會一個緊挨一個。整個結構的大小就為 sizeof(float) + sizeof(bool) + sizeof(float[16]) + sizeof(int) = 73。欄位 val2 的偏移就會為 sizeof(float) + sizeof(bool) = 5。
但一但考慮自己對齊,就有
- val0 型別為 float,偏移為 0, 佔據 4 位元組。
- val1 型別為 bool, 偏移為 4,佔據 1 位元組。
- val2 型別為 float[16],本來應該挨著 val1, 偏移為 4 + 1 = 5。但要求 4 位元組對齊。於是偏移調整為 8,佔據 64 位元組。
- val2 型別為 int, 偏移為 8 + 64 = 72,佔據 4 位元組。
於是資料總大小為 72 + 4 = 76,而結構體內部欄位最大對齊值為 4 位元組。資料總大小為 76,是 4 的倍數,不用調整。於是整個結構體大小為 76 位元組。
要驗證我們的計算也很簡單,在測試程式碼中定義結構體,使用offsetof(struct MtlFragmentUniforms, val0)
就可以取得偏移值。只是我們原始問題根本就沒有結構體,也就不能使用 offsetof,需要自己來計算。
假如覺得自己列印 offsetof 麻煩,可以寫下列測試程式碼
// main.cpp struct MtlFragmentUniforms { float val0; bool val1; float val2[16]; int val3; }; int main(int argc, char **argv) { return sizeof(MtlFragmentUniforms); }
之後使用命令
clang -cc1 -fdump-record-layouts main.cpp
就可以打印出
*** Dumping AST Record Layout 0 | struct MtlFragmentUniforms 0 |float val0 4 |_Bool val1 8 |float [16] val2 72 |int val3 | [sizeof=76, dsize=76, align=4, |nvsize=76, nvalign=4]
sizeof = 76, 就為整個結構的大小。align=4 為結構整個結構要求的對齊值,MtlFragmentUniforms 結構本身需要 4 位元組對齊。而 dsize、nvsize、nvalign 幾個欄位跟 C++ 有關,不用關心。
正式程式碼
LLVM 編譯器中 C 結構的佈局計算可以參考程式碼DataLayout.cpp 。
C++ 的佈局計算可以參考RecordLayoutBuilder.cpp
,實際上,上面命令輸出的詳細布局,對應於檔案中DumpRecordLayout
函式。
RecordLayoutBuilder.cpp 的程式碼有點複雜,我們還是看 DataLayout.cpp 的程式碼。對於 C 結構,它們的計算結果是一樣的。
StructLayout::StructLayout(StructType *ST, const DataLayout &DL) { assert(!ST->isOpaque() && "Cannot get layout of opaque structs"); StructAlignment = 0; StructSize = 0; IsPadded = false; NumElements = ST->getNumElements(); // Loop over each of the elements, placing them in memory. for (unsigned i = 0, e = NumElements; i != e; ++i) { Type *Ty = ST->getElementType(i); unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty); // Add padding if necessary to align the data element properly. if ((StructSize & (TyAlign-1)) != 0) { IsPadded = true; StructSize = alignTo(StructSize, TyAlign); } // Keep track of maximum alignment constraint. StructAlignment = std::max(TyAlign, StructAlignment); MemberOffsets[i] = StructSize; StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item } // Empty structures have alignment of 1 byte. if (StructAlignment == 0) StructAlignment = 1; // Add padding to the end of the struct so that it could be put in an array // and all array elements would be aligned correctly. if ((StructSize & (StructAlignment-1)) != 0) { IsPadded = true; StructSize = alignTo(StructSize, StructAlignment); } }
可以看到 StructAlignment 儲存了結構體自身需要的對齊值,為結構體所有欄位最大的對齊值。最終結構體的 StructSize 會調整成這個 StructAlignment 的整數倍。比如下面例子
// main.cpp struct Test { double v0; int v1; }; struct Test2 { int v0; Test v1; }; int main(int argc, char **argv) { return sizeof(Test2); }
使用命令clang -cc1 -fdump-record-layouts main.cpp
打印出。
*** Dumping AST Record Layout 0 | struct Test 0 |double v0 8 |int v1 | [sizeof=16, dsize=16, align=8, |nvsize=16, nvalign=8] *** Dumping AST Record Layout 0 | struct Test2 0 |int v0 8 |struct Test v1 8 |double v0 16 |int v1 | [sizeof=24, dsize=24, align=8, |nvsize=24, nvalign=8]
觀察 Test 的輸出。Test 的 v2, 偏移為 8,佔據 4 個位元組。Test 的 size 本來應該是 12 位元組,但 Test 包含了 double,double 的對齊為 8,整個 Test 的對齊也應該為 8。於是 Test 的 size 也被調整成 8 位元組對齊,變為了 16 位元組。
為什麼結構體本身的 size 也需要對齊呢?不能直接是 12 位元組嗎,這樣會省些記憶體。
考慮下面程式碼,我們經常類似下面那樣,動態分配記憶體。
Test* p = malloc(2 * sizeof(Test));
假如 Test 的 size 不調整對齊,為 12 位元組,兩個 Test 直接緊挨著。記憶體佈局如下
p + 0| struct Test p + 0|double v0 p + 8|int v1 p + 12 | struct Test p + 12 |double v0 p + 20 |int v1
觀察到第 2 個 Test 的 v0 欄位。它的地址為 p + 12, 而 double 本身為 8 個位元組,於是 v0 就會佔據 [p + 12, p + 20) 的記憶體,這實際就會跨越 [p + 8, p + 16), [p + 16,p + 24) 兩個格子。
為了預防這種跨格子的情況,結構體於是就需調整自身的 size。Test 大小調整為 16,無論怎麼排列,內部的欄位也不會跨越兩個格子。
64 位機下,對於基礎型別,比如 int, double 之類,它的對齊值為它的 size。但對於結構體,它的對齊值是其中所有欄位對齊值的最大值。結構體需要保持自身的對齊值,這樣當結構體巢狀的情況,計算方式就完全一樣了。
位元組對齊對程式碼的影響
平常很少需要自己計算 struct 的佈局,但位元組對齊會影響程式碼寫法。比如我們定義結構時,需要注意欄位的排列順序,不然白白浪費記憶體。如下定義
struct Color { float r; float g; float b; float a; }; struct FrameInfo { Color color; bool isColorDirty; float depth; bool isDepthDirty; };
sizeof(FrameInfo) = 28,佔據了 28 個位元組。但其它程式碼不用改,只需要調整欄位的順序,將兩個 bool 放在一起。
struct FrameInfo { bool isColorDirty; bool isDepthDirty; Color color; float depth; };
調整後 sizeof(FrameInfo) = 24, 每個結構節省了 4 位元組。當類似的結構很多時,節省的記憶體也挺可觀的。
大家可能會說,現在的記憶體這樣大,何必還死扣這種位元組呢。只是在這種情況下,隨手就改好了,不花什麼成本,也影響程式碼可讀性,也有收益,何樂而不為呢。俗話說,蚊子肉也是肉啊。
位元組對齊有時也會影響檔案的讀取寫入。比如我們將一些字串寫到二進位制檔案中。為了方便讀取,我們先寫入 4 位元組的字串長度,再寫入字串本身內容。
當寫入 "hello", "world" 兩個字串,二進位制檔案中就有內容
5(佔4位元組),"hello"(佔5位元組),4(佔4位元組),“world”(佔5位元組)
我們將整個檔案都讀入記憶體(或者使用 mmap),再讀取字串。
class File { File(const std::string &path) { _data = readDataFromFile(path); } std::string readString() { // 先讀取長度 int len = *((int *)_data); _data += sizeof(int); // 再讀取字串內容 std::string result(_data, _data + len); _data += len; return result; } private: uint8_t *_data; } File file(path); std::string str0 = file.readString(); std::string str1 = file.readString();
上述程式碼實際上是有問題的,在讀取長度的時候,使用了一個指標強轉。int len = *((int *)_data);
簡單分析就可以知道,在讀取 "hello" 字串後,因為它只佔據 5 位元組。於是之後讀取 "world" 的長度時,指標 _data 就不是 4 位元組對齊。強轉成 int*,就會跨越兩個格子。對於某些機器,內部可能幫忙拼接。但對於一些機器,程式可能就直接崩潰了。
這種問題可以在寫入檔案和讀取檔案兩個角度防止。很多檔案格式,在寫入字串時,就要求對齊。比如 4 位元組對齊,當字串長度並非 4 位元組倍數時,會在後面填充一些 0。比如上例中寫入 "hello", "world" 兩個字串,最終為
5(佔4位元組),"hello"(佔5位元組),補0(3位元組),4(佔4位元組),“world”(佔5位元組),補0(三位元組)
這樣讀取函式 readString,就被修改為
std::string readString() { // 先讀取長度 int len = *((int *)_data); _data += sizeof(int); // 再讀取字串內容 std::string result(_data, _data + len); _data += alignTo(len, 4); return result; }
alignTo 函式就是將 len 調整成 4 位元組對齊。
在讀取時候防止,就是讀取任何欄位的時候都不應該強轉。可以使用 memcpy 來讀入長度,就為
int len = 0; memcpy(&len, _data, sizeof(int)); _data += sizeof(int);
但實際上,這種讀取方式也不一定是正確的,因為沒有考慮位元組順序,但我們在這裡先忽略這個問題。現在可接觸到的機器基本都是小尾機。
為了安全,寧願在讀取的時候使用 memcpy,也不要直接強轉。但直接強轉速度會快一些,要求寫入資料的時候,預先位元組對齊。
在編譯的時候,假如不修改 #pragma pack 之類的編譯器對齊選項,編譯出來的結構資料就是自然對齊的。當資料儲存成二進位制資料再讀取時,就需要特別注意了。