# zero-width bit field 問題探討II (未解決)
[zero-width bit field 問題探討I](/wF3UvixFQUWfOYDEyPW9_w)
## 前言
上次做完 [zero-width bit field 問題探討I](/wF3UvixFQUWfOYDEyPW9_w)後，教授給我了一些方向和提議讓我繼續往下實驗，主要是閱讀關於 bit field alignment 的資料與編譯時使用最佳化來觀察程式的行為是否相同。
但是... 目前還是 **無解...** 希望各位大大的能給些指點與方向...
## 目標
1. 閱讀補充在 [zero-width bit field 問題探討I](/wF3UvixFQUWfOYDEyPW9_w)關於 bitfield 和 alignment 的資料。
2. 編譯程式時，加上 gcc 參數 -O0 (抑制最佳化)，並確保在 -O2 編譯時，行為也一致。
## 實驗環境
- OS: Ubuntu 16.04.5 LTS
- Compiler: gcc 8.1
- Little endian
## 主題1： Do not make assumptions
教授給予回饋的時候補充到：
> 程式開發者對 bitfield 和 alignment 做不正確的假設，往往是系統漏洞 (CVE/CWE 有好幾項相關的議題) 的溫床。
並分享了 [Do not make assumptions regarding the layout of structures with bit-fields](https://wiki.sei.cmu.edu/confluence/display/c/EXP11-C.+Do+not+make+assumptions+regarding+the+layout+of+structures+with+bit-fields)， 文章中主要提到兩個關於 bit field 的問題： alignment 和 overlap。
### bit field alignment
這主要是關係到資料在 memory 中會有兩種儲存方式：Big Endian and Little Endian。
- Big endian: 在記憶體中讀取資料時，第一個讀到byte(最小的記憶體位址)會是最大的。(Stores data big-end first. When looking at multiple bytes, the first byte (lowest address) is the biggest.)
- Little endian: 在記憶體中讀取資料時，第一個讀到byte(最小的記憶體位址)會是最小的。(Stores data little-end first. When looking at multiple bytes, the first byte is smallest.)
在 [Understanding Big and Little Endian Byte Order](https://betterexplained.com/articles/understanding-big-and-little-endian-byte-order/) 有更充份的講解。
在教授給的[資料](https://wiki.sei.cmu.edu/confluence/display/c/EXP11-C.+Do+not+make+assumptions+regarding+the+layout+of+structures+with+bit-fields)中的例子：
```cpp
#include <stdio.h>
struct bf
unsigned int m1 : 8;
unsigned int m2 : 8;
unsigned int m3 : 8;
unsigned int m4 : 8;
}; /* 32 bits total */
void function() {
struct bf data;
unsigned char *ptr;
data.m1 = 0;
data.m2 = 0;
data.m3 = 0;
data.m4 = 0;
ptr = (unsigned char *)&data;
(*ptr)++; /* Can increment data.m1 or data.m4 */
printf("m1: %d\nm2: %d\nm3: %d\nm4: %d\n", data.m1, data.m2, data.m3, data.m4);
}
```
我電腦上的輸出:
```
m1: 1
m2: 0
m3: 0
m4: 0
```
可以得知我的電腦是 Little endian；若是 Big endian 的電腦，所增加的則是 m4。
所以，**在不同的電腦 (Big endian or little endian)上對於 bit field 的影響有所不同！**
在 [How Endianness Effects Bitfield Packing](http://mjfrazer.org/mjfrazer/bitfields/) 對於 Big/Little endian 在 memory 的 layout 也有很好的例子：
### bit field overlap
另一個我一開始沒有注意到的現象就是：如果 bit field 宣告的範圍超過一個 byte (e.g. int a: 4; int b: 6;) **那 b 會有 4 bits 存在和 a 同一個 byte? 還是 b 全部的 bits 都在新的 byte?**
[資料](https://wiki.sei.cmu.edu/confluence/display/c/EXP11-C.+Do+not+make+assumptions+regarding+the+layout+of+structures+with+bit-fields)中的例子：
```cpp
struct bf {
unsigned int m1 : 6;
unsigned int m2 : 4;
};
void function() {
unsigned char *ptr;
struct bf data;
data.m1 = 0;
data.m2 = 0;
ptr = (unsigned char *)&data;
ptr++;
*ptr += 1; /* What does this increment? */
printf("m1: %d\nm2: %d\n", data.m1, data.m2);
}
```
我電腦上的 output:
```
m1: 0
m2: 1
```
證明在我的電腦上 b 會全部都在一個新的 byte 裡，也就是：
| b | a |
| :--------: | :--------: |
| _ _ _ _ 0 0 0 1, | _ _ _ 0 0 0 0 0 0 |
而有些電腦會是：
| b | a |
| :--------: | :--------: |
| _ _ _ _ _ _ 0 1, 0 0 | 0 0 0 0 0 0 |
對 b 來說就值會是 4 ！
所以，**在宣告 bit field 的時候要特別注意是否有 overlap (cross byte)的現象，並注意電腦對於 overlap 的處理為何！**
## 主題2： 編譯最佳化
在編譯器提供了最佳化的功能，有四個層級的選項分別為```-O0, -O1, -O2, -O3```，而針對這次鎖鑰使用的```-O0, -O2``` 在 ```man gcc``` 提到：
- -O0 Reduce compilation time and make debugging produce the expected results. This is the default.
- -O2 Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. As compared to -O, this option increases both compilation time and the performance of the generated code.
目前的了解是 ```-O0``` 是抑制最佳化，```-O2``` 針對 code size 和 execution time 有做更多的優化，開啟的 optimization flags 也不同。更詳細的內容還需要在細究。
## 實驗
首先先確定再編譯的時候加上 ```-O0``` 時的程式行為，為方便確認結果，實驗程式碼為：
```cpp
#include <stdio.h>
struct foo {
int a: 3;
int b: 2;
int : 0;
int c: 4;
int d: 3;
};
int main() {
int i = 0xFFFF;
struct foo *f = (struct foo *)&i;
printf("&i: %p\n", &i);
printf("&f: %p\n", &f);
printf("a: %d\nb: %d\nc: %d\nd: %d\n", f->a, f->b, f->c, f->d);
return 0;
}
```
編譯與執行：
```shell
$ gcc -Wall -g -O0 zero_width_bit_field.c \
-o ./zero_width_bit_field_O_0
```
執行5次:
```shell
$ ./zero_width_bit_field_O_0
```
所得到的 output:
```shell
&i: 0x7ffcea515ffc
&f: 0x7ffcea516000
a: -1
b: -1
c: -4
d: -1
&i: 0x7ffcbb8ac38c
&f: 0x7ffcbb8ac390
a: -1
b: -1
c: -4
d: 0
&i: 0x7fff92ff041c
&f: 0x7fff92ff0420
a: -1
b: -1
c: -4
d: 1
&i: 0x7ffcf4889d5c
&f: 0x7ffcf4889d60
a: -1
b: -1
c: -4
d: -3
&i: 0x7ffde55944fc
&f: 0x7ffde5594500
a: -1
b: -1
c: -4
d: -1
```
可以看出 c 和 d 的值仍是依照變數 i 的位址而變化（詳細解釋可參考[zero-width bit field 問題探討I](/wF3UvixFQUWfOYDEyPW9_w)）。得知，**加上 ```-O0``` 後程式行為一樣。**
嘗試 ```-O2``` :
```shell
gcc -Wall -g -O2 ./zero_width_bit_field.c -o ./zero_width_bit_field_O_2
# 執行5次
./zero_width_bit_field_O_2
```
得到 output:
```shell
&i: 0x7ffff894c8ec
&f: 0x7ffff894c8f0
a: -1
b: -1
c: -4
d: -2
&i: 0x7ffd9dde6d4c
&f: 0x7ffd9dde6d50
a: -1
b: -1
c: -4
d: -4
&i: 0x7ffeca52c42c
&f: 0x7ffeca52c430
a: -1
b: -1
c: -4
d: 2
&i: 0x7ffdf3d4d8bc
&f: 0x7ffdf3d4d8c0
a: -1
b: -1
c: -4
d: 3
&i: 0x7ffce205779c
&f: 0x7ffce20577a0
a: -1
b: -1
c: -4
d: 1
```
也可看出 c 和 d 的值仍是根據變數 i 的位址變化。
所以... 加上 ```-O0``` 和 ```-O2``` 對程式沒有影響囉？
將兩個程式做反組譯做比較：
```shell
$ objdump -d -M intel zero_width_bit_field_O_0
# output 57 lines
0000000000400572 <main>:
400572: 55 push rbp
400573: 48 89 e5 mov rbp,rsp
400576: 48 83 ec 20 sub rsp,0x20
40057a: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
400581: 00 00
400583: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
400587: 31 c0 xor eax,eax
400589: c7 45 ec ff ff 00 00 mov DWORD PTR [rbp-0x14],0xffff
400590: 48 8d 45 ec lea rax,[rbp-0x14]
400594: 48 89 45 f0 mov QWORD PTR [rbp-0x10],rax
400598: 48 8d 45 ec lea rax,[rbp-0x14]
40059c: 48 89 c6 mov rsi,rax
40059f: bf c4 06 40 00 mov edi,0x4006c4
4005a4: b8 00 00 00 00 mov eax,0x0
4005a9: e8 c2 fe ff ff call 400470 <printf@plt>
4005ae: 48 8d 45 f0 lea rax,[rbp-0x10]
4005b2: 48 89 c6 mov rsi,rax
4005b5: bf cd 06 40 00 mov edi,0x4006cd
4005ba: b8 00 00 00 00 mov eax,0x0
4005bf: e8 ac fe ff ff call 400470 <printf@plt>
4005c4: 48 8b 45 f0 mov rax,QWORD PTR [rbp-0x10]
4005c8: 0f b6 40 04 movzx eax,BYTE PTR [rax+0x4]
4005cc: 01 c0 add eax,eax
4005ce: c0 f8 05 sar al,0x5
4005d1: 0f be f0 movsx esi,al
4005d4: 48 8b 45 f0 mov rax,QWORD PTR [rbp-0x10]
4005d8: 0f b6 40 04 movzx eax,BYTE PTR [rax+0x4]
4005dc: c1 e0 04 shl eax,0x4
4005df: c0 f8 04 sar al,0x4
4005e2: 0f be c8 movsx ecx,al
4005e5: 48 8b 45 f0 mov rax,QWORD PTR [rbp-0x10]
4005e9: 0f b6 00 movzx eax,BYTE PTR [rax]
4005ec: c1 e0 03 shl eax,0x3
4005ef: c0 f8 06 sar al,0x6
4005f2: 0f be d0 movsx edx,al
4005f5: 48 8b 45 f0 mov rax,QWORD PTR [rbp-0x10]
4005f9: 0f b6 00 movzx eax,BYTE PTR [rax]
4005fc: c1 e0 05 shl eax,0x5
4005ff: c0 f8 05 sar al,0x5
400602: 0f be c0 movsx eax,al
400605: 41 89 f0 mov r8d,esi
400608: 89 c6 mov esi,eax
40060a: bf d6 06 40 00 mov edi,0x4006d6
40060f: b8 00 00 00 00 mov eax,0x0
400614: e8 57 fe ff ff call 400470 <printf@plt>
400619: b8 00 00 00 00 mov eax,0x0
40061e: 48 8b 55 f8 mov rdx,QWORD PTR [rbp-0x8]
400622: 64 48 33 14 25 28 00 xor rdx,QWORD PTR fs:0x28
400629: 00 00
40062b: 74 05 je 400632 <main+0xc0>
40062d: e8 2e fe ff ff call 400460 <__stack_chk_fail@plt>
400632: c9 leave
400633: c3 ret
400634: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
40063b: 00 00 00
40063e: 66 90 xchg ax,ax
$ objdump -d -M intel zero_width_bit_field_O_2
# output 48 lines
00000000004004c0 <main>:
4004c0: 48 83 ec 28 sub rsp,0x28
4004c4: be e4 06 40 00 mov esi,0x4006e4
4004c9: bf 01 00 00 00 mov edi,0x1
4004ce: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
4004d5: 00 00
4004d7: 48 89 44 24 18 mov QWORD PTR [rsp+0x18],rax
4004dc: 31 c0 xor eax,eax
4004de: 48 8d 54 24 0c lea rdx,[rsp+0xc]
4004e3: c7 44 24 0c ff ff 00 mov DWORD PTR [rsp+0xc],0xffff
4004ea: 00
4004eb: 48 89 54 24 10 mov QWORD PTR [rsp+0x10],rdx
4004f0: e8 ab ff ff ff call 4004a0 <__printf_chk@plt>
4004f5: 48 8d 54 24 10 lea rdx,[rsp+0x10]
4004fa: be ed 06 40 00 mov esi,0x4006ed
4004ff: 31 c0 xor eax,eax
400501: bf 01 00 00 00 mov edi,0x1
400506: e8 95 ff ff ff call 4004a0 <__printf_chk@plt>
40050b: 48 8b 44 24 10 mov rax,QWORD PTR [rsp+0x10]
400510: be f6 06 40 00 mov esi,0x4006f6
400515: bf 01 00 00 00 mov edi,0x1
40051a: 44 0f b6 40 04 movzx r8d,BYTE PTR [rax+0x4]
40051f: 0f b6 10 movzx edx,BYTE PTR [rax]
400522: 31 c0 xor eax,eax
400524: 47 8d 0c 00 lea r9d,[r8+r8*1]
400528: 8d 0c d5 00 00 00 00 lea ecx,[rdx*8+0x0]
40052f: 41 c1 e0 04 shl r8d,0x4
400533: c1 e2 05 shl edx,0x5
400536: 41 c0 f9 05 sar r9b,0x5
40053a: 41 c0 f8 04 sar r8b,0x4
40053e: c0 f9 06 sar cl,0x6
400541: c0 fa 05 sar dl,0x5
400544: 45 0f be c9 movsx r9d,r9b
400548: 45 0f be c0 movsx r8d,r8b
40054c: 0f be c9 movsx ecx,cl
40054f: 0f be d2 movsx edx,dl
400552: e8 49 ff ff ff call 4004a0 <__printf_chk@plt>
400557: 48 8b 74 24 18 mov rsi,QWORD PTR [rsp+0x18]
40055c: 64 48 33 34 25 28 00 xor rsi,QWORD PTR fs:0x28
400563: 00 00
400565: 75 07 jne 40056e <main+0xae>
400567: 31 c0 xor eax,eax
400569: 48 83 c4 28 add rsp,0x28
40056d: c3 ret
40056e: e8 0d ff ff ff call 400480 <__stack_chk_fail@plt>
400573: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
40057a: 00 00 00
40057d: 0f 1f 00 nop DWORD PTR [rax]
```
可以看出在 ```-O2``` 的組合語言程式碼比較短，當中的程式碼行為也不太一樣。
但是當我把程式碼還原成：
```cpp=
#include <stdio.h>
struct foo {
int a: 3;
int b: 2;
int : 0;
int c: 4;
int d: 3;
};
int main() {
int i = 0xFFFF;
struct foo *f = (struct foo *)&i;
printf("a: %d\nb: %d\nc: %d\nd: %d\n", f->a, f->b, f->c, f->d);
return 0;
}
```
再執行與編譯：
```shell
$ gcc -Wall -g -O2 ./zero_width_bit_field.c -o ./zero_width_bit_field_O_2
# 執行5次
./zero_width_bit_field_O_2
```
結果得到的 output 為：
```shell
a: -1
b: -1
c: 0
d: 0
a: -1
b: -1
c: 0
d: 0
a: -1
b: -1
c: 0
d: 0
a: -1
b: -1
c: 0
d: 0
a: -1
b: -1
c: 0
d: 0
```
程式行為似乎不同了！當我再用 gdb 去追蹤：
```shell
$ gdb -q zero_width_bit_field_O_2
Reading symbols from zero_width_bit_field_O_2...done.
(gdb) b main
Breakpoint 1 at 0x4004c0: file ./zero_width_bit_field.c, line 12.
(gdb) b 15
Breakpoint 2 at 0x400510: file ./zero_width_bit_field.c, line 18.
(gdb) r
Starting program: zero_width_bit_field_O_2
Breakpoint 1, main () at ./zero_width_bit_field.c:12
12 int main() {
(gdb) n
14 int i = 0xFFFF;
(gdb) n
104 return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
(gdb) n
a: -1
b: -1
c: 0
d: 0
Breakpoint 2, main () at ./zero_width_bit_field.c:18
18 return 0;
```
明明設了中斷點在 15 行，卻顯示中斷點在第 18 行？
在 14 行執行下一步的時候似呼卻略過了中間原本的程式碼？
也跑出了一個 ```return __printf_chk``` ？
在想追蹤指標 f 時：
```shell
(gdb) p f
$1 = (struct foo *) 0x7fffffffd0f4
(gdb) p &i
$2 = (int *) 0x7fffffffd0f4
(gdb) p &f
Can't take address of "f" which isn't an lvalue.
(gdb) p &(f->a)
$3 = (int *) 0x7fffffffd0f4
(gdb) p &(f->c)
$4 = (int *) 0x7fffffffd0f8
```
a 和 c 的位址和原本的編譯時相同 指向 &i 和下一個記憶體位址。但 f 有值，卻沒有 f 的位址值？還有甚麼是 lvalue？
[wiki](https://en.wikipedia.org/wiki/Value_(computer_science)#Assignment:_l-values_and_r-values) 解釋：
> l-values have storage addresses that are programmatically accessible to the running program (e.g., via some address-of operator like "&" in C/C++), meaning that they are variables or dereferenced references to a certain memory location.
[cppreference](https://en.cppreference.com/w/c/language/value_category) 寫到：
> Lvalue expression is any expression with object type other than the type void, which potentially designates an object (the behavior is undefined if an lvalue does not actually designate an object when it is evaluated). In other words, lvalue expression evaluates to the object identity. The name of this value category ("left value") is historic and reflects the use of lvalue expressions as the left-hand operand of the assignment operator in the CPL programming language.
我的理解是： lvalue 是有儲存在記憶體位址的值的表示式。**但不懂為甚麼上述的程式碼在 ```-O2``` 最佳化的時候，f 有值，但卻沒有 &f... 目前還沒有得出一個解釋...**
## 結論與討論
1. 在宣告 bit field 時，若要清楚了解 bit field 在記憶體的位置，則必須確認：
- **電腦為 Big endian 還是 Little endian？**
- **bit field 在 overlap 的時候是否會跨 byte？**
才可以確定 bit field 在記憶體中的排列。
2. 編譯器在開啟最佳化時，會造成程式底層的改變，有時會改變程式行為的表現。但在這次的實驗中還是有很多的疑問：
- 組合語言的改變....
- 為何在 gdb 下中斷點的時候，顯示的中斷點行數不同？而且程式似乎略過了中間的程式碼？
- 為何 f 有值，卻沒有 &f？要如何解釋 f 不是一個 lvalue？
**希望能有各位大大的意見和方向，非常希望可以找出這些程式行為背後的原理和原因！**
自己也需要再加強對於 C 的知識...
:::warning
教授回饋：
gcc 的 -O2 編譯選項已變更資料佈局，可改用 -Og (針對除錯器作調整) 選項，__printf_chk 符號的出現，是因為 glibc 內部對於 vsprintf 系列函式的實作，你的程式可避開呼叫 printf，改為自己寫的函式呼叫，然後搭配 GDB pretty print 及 macro，顯示要追蹤的結構體內容。
:::
## 參考文獻
- [C program to check little vs. big endian](https://stackoverflow.com/questions/12791864/c-program-to-check-little-vs-big-endian/12792301#12792301)
- [gcc 的最佳化功能](http://sp1.wikidot.com/gccoptimization)
- [gcc -o / -O option flags](https://www.rapidtables.com/code/linux/gcc/gcc-o.html)
- [Stack frame layout on x86-64](https://eli.thegreenplace.net/2011/09/06/stack-frame-layout-on-x86-64/)
- [Assembly Language Integer Arithmetic](https://www.csie.ntu.edu.tw/~acpang/course/asm_2004/slides/chapt_07_PartISolve.pdf)
- [Directives BYTE PTR, WORD PTR, DWORD PTR](http://www.c-jump.com/CIS77/ASM/Instructions/I77_0250_ptr_pointer.htm)
- [What are the names of the new X86_64 processors registers?](https://stackoverflow.com/questions/1753602/what-are-the-names-of-the-new-x86-64-processors-registers)
64-bit register | Lower 32 bits | Lower 16 bits | Lower 8 bits
:----:|:----:|:----:|:----:|
rax | eax | ax | al
rbx | ebx | bx | bl
rcx | ecx | cx | cl
rdx | edx | dx | dl
rsi | esi | si | sil
rdi | edi | di | dil
rbp | ebp | bp | bpl
rsp | esp | sp | spl
r8 | r8d | r8w | r8b
r9 | r9d | r9w | r9b
r10 | r10d | r10w | r10b
r11 | r11d | r11w | r11b
r12 | r12d | r12w | r12b
r13 | r13d | r13w | r13b
r14 | r14d | r14w | r14b
r15 | r15d | r15w | r15b
- [lvalue and rvalue in C language](https://www.geeksforgeeks.org/lvalue-and-rvalue-in-c-language/)
- [Value categories](https://en.cppreference.com/w/c/language/value_category)
###### tags: `knowThyself` `linux` `c` `bitField`
Sign in with Wallet
Connect another wallet