# 2019q3 Homework1 (review) contributed by < `shaojason999` > ###### tags: `sysprog2019` [作業要求](https://hackmd.io/@sysprog/rJM4SPw8S) ## 測驗 `1` 考慮以下 C 程式的 `align4` 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。 ```cpp #include <stdio.h> #define align4(x) (((x) + K) & (-4)) int main(void) { int p = 0x1997; printf("align4(p) is %08x\n", align4(p)); return 0; } ``` 預期程式輸出 `align4(p) is 00001998` ，求 K 為多少 ### 先備知識 首先，我們要先知道 alignment 的作用是把記憶體位置對齊 因為一般的 processor 在抓取記憶體資料時，是以 4 or 8 bytes 一口氣抓取的(不是一個一個 byte 去抓)，因此我們存放資料的方式會影響抓取資料的速度 #### 影響抓取資料的速度 ```cpp struct mystruct { char c; // one byte int i; // four bytes short s; // two bytes } ``` * 以上的結構因為 int 佔 4 個 bytes，因此會以 4 個 bytes 為單位去 alignment，這樣去讀取資料時會很方便(快) * ![](https://i.imgur.com/pnx00Bd.png) * 但如果沒有做 padding，而是直接塞在一起的話，今天如果你要讀取 0x0001 (int i) * ![](https://i.imgur.com/9Z7sHDI.png) * 假設是在 32-bit 的 processor (一般會一次抓取 4 個 bytes) * 要先抓取 0x0000 ，然後往左 `shift` 1，存在一個 register * 接著抓取 0x0000 ，然後往右 `shift` 3，存在另一個 register * 然後把以上兩個 register 做 `or`，存在 result register * 這些步驟比有 padding 的版本多了兩個 `shift` 還有一個 `or` ### 解題方式 我們現在來分析以下這段題目中程式碼做的事 ```cpp #define align4(x) (((x) + K) & (-4)) ``` * 首先先看 & (-4) 的作用 * 從二進位來看 -4 相當於 11...11100 * 因此我們不論你輸入的記憶體位置是多少，最後 2 個 bits 都會被丟棄掉，而這就是 4-byte alignment * 接著來看 +k 的作用是甚麼 * 因為是 4-byte alignment，所以每 4 個 bytes 為一組，會對應到一個 align 後的位置 * 以這題來看就是 0x1995 ~ 0x1998 align 後要到 0x1998 * 可以推得 K 為 3 :::success 延伸問題: 在 Linux 核心原始程式碼找出類似的 alignment 巨集並解釋其作用 ::: #### 舉例 1 在 [linux/scripts/dtc/fdtdump.c](https://lxr.missinglinkelectronics.com/linux/scripts/dtc/fdtdump.c#L17) 的 line 17, 18 可以看到 ```cpp #define ALIGN(x, a) (((x) + ((a) - 1)) & ~((a) - 1)) #define PALIGN(p, a) ((void *)(ALIGN((unsigned long)(p), (a)))) ``` line 17 跟這題的概念一樣: x 為輸入地址 a 為 alignment 的 byte 數量 * 如果 a 為 4，則這句就會變成 `(((x) + 3) & (-4))`，也就是跟題目一模一樣，在這就不再解釋一次 line 18 是針對 pointer 的部分，可以看到在 [line 105](https://lxr.missinglinkelectronics.com/linux/scripts/dtc/fdtdump.c#L104) 的地方會呼叫 ```cpp s = p; p = PALIGN(p + strlen(s) + 1, 4); ``` 在這裡做的事是先把上一次的 p 傳給 s，並且計算下一次的 p 的位置應該要是多少 * 下一次的 p 的位置取決於原本的 p + 原本的 p 指向的的字串長度 + 一個終止空字符長度(1 byte)，並且以 4-byte alignment #### 舉例 2 在[linux/tools/virtio/ringtest/ptr_ring.c](https://lxr.missinglinkelectronics.com/linux/tools/virtio/ringtest/ptr_ring.c#L18) 的 line 18 可以看到 ```cpp #define ALIGN(x, a) (((x) + (a) - 1) / (a) * (a)) ``` 前半段跟這題的概念一樣，至於後半段先除 a，再乘以 a，做的就是把最後幾個 bit 給丟掉 比如說 `(11011101 >> 4) <<4` 結果就是 `11010000`，概念上還是跟這題一樣 :::danger 如此作法的效益為何？你做了==量化==分析了嗎？你可以接受 Apple 和 Google 工程師只是「憑感覺」去修改程式碼嗎？這樣做出來的手機，你敢每天帶在身邊用嗎？快去做實驗！ :notes: jserv ::: ### 相關教材整理 在閱讀了第一周教材的 [你所不知道的C語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7?type=view#data-alignment) ，我有一個地方不懂 :::info 老師寫說: ```cpp for (int i = 0; i < 10000; ++i) { char *z; z = malloc(sizeof(char)); } ``` 結果用 gdb 測過之後，發現位址的結尾的確都是 0 結尾，表示真的是以 16-byte 做對齊。 可是我自己寫了一個程式: ```cpp for(i=0;i<10;++i){ char *z; z=malloc(sizeof(char)); printf("%p\n",z); } ``` 結果卻是 ``` 0xf24010 0xf25040 0xf25060 0xf25080 0xf250a0 0xf250c0 0xf250e0 0xf25100 0xf25120 0xf25140 ``` 看起來是 32-byte 對齊，甚至第一個是 48-byte 我想不到為甚麼會是這樣? ::: :::danger 回頭看 man-page，找出 alignment 相關描述 :notes: jserv ::: ### 參考資料 [86. UNALIGNED MEMORY ACCESSES - The Linux Kernel](https://www.infradead.org/~mchehab/kernel_docs/unsorted/unaligned-memory-access.html) [Purpose of memory alignment - stack overflow](https://stackoverflow.com/questions/381244/purpose-of-memory-alignment) [What is meant by “memory is 8 bytes aligned”? - stack overflow](https://stackoverflow.com/questions/2846914/what-is-meant-by-memory-is-8-bytes-aligned) ## 測驗 `2` 考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候: * 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`; * 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4` ```cpp #include <stdint.h> #define INT_SIZE_OF(n) \ ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y)) ``` * 參考資訊: [Memory access and alignment](https://lwn.net/Articles/260832/) ### 解題方式 這題跟第一題的想法也很像，因此我們一樣用記憶體的角度來看 ```cpp ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y)) ``` * 程式碼的前半段是在確保可以進到記憶體的下一個區段 (區段長度為 sizeof(int)) * 因此 sizeof(n) 要加上的就是 `區段長度 - 1` = `sizeof(int) - 1` * 後半段是在做 mask，也就是把 alignment 後的 bit 都丟掉，這樣才可以回到區段的頭 * 只要先 -1 再反轉就好 * 舉例一下: 如果要把比如說第 3 個 bit 之後的 bits 都丟掉好了 * ~(00000100 - 1) = ~(00000011) = 11111100 因此 X 跟 Y 的都是 -1 長得跟[linux/scripts/dtc/fdtdump.c](https://lxr.missinglinkelectronics.com/linux/scripts/dtc/fdtdump.c#L17) 的 line 17 一樣 > 可以看上面第一題的講解 ```cpp #define ALIGN(x, a) (((x) + ((a) - 1)) & ~((a) - 1)) ``` :::success 延伸題目: 解釋運作原理並在 GitHub 找出實際應用的程式碼 ::: 實際應用我查好久查不到，只找到一個類似的: 在 [TLSF](https://github.com/mattconte/tlsf/blob/master/tlsf.c#L468) 這種動態記憶體配置法中有用到 :::danger 請尊重台灣繁體中文科技術語，memory allocation 應該翻譯為「記憶體配置」，algorithm 是「演算法」 :notes: jserv ::: ```cpp static size_t align_up(size_t x, size_t align) { tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two"); return (x + (align - 1)) & ~(align - 1); } ``` 其中 align 這個參數會因為你的處理器不同，而在程式一開始先 #define 了，並不是真的每次傳參數進來(我不懂作者為甚麼要用參數的方式傳進來) :::danger 做實驗分析，對照輸出的組合語言 (記得開 `-Os` 編譯選項) :notes: jserv ::: ## 測驗 `3` 考慮以下 C 程式碼: ```cpp #include <stdbool.h> bool func(unsigned int x) { return x && ((x & (~x + 1)) == x); } ``` 可改寫為以下等價的程式碼: 求出Z ```cpp bool func(unsigned int x) { unsigned int unknown = 0; while (x && unknown <= 1) { if ((x & Z) == 1) unknown++; x >>= 1; } return (unknown == 1); } ``` ### 解題方式 首先來思考 `(x & (~x + 1))` 的意義 * 首先要先能看出 (~x+1) 為 x 的 2's complement * 隨便舉幾個例子來觀察看看 |x|(~x+1)|x & (~x+1)| |:----:|:----:|:----:| |11100110|00011010|00000010| |01100111|10011001|00000001| |00110000|11010000|00010000| * 會發現 & 後的結果剛好會是本來 x 的最後一個 bit 被 set 而已，所以就是尋找 x 的最後一個 bit 那麼當 x 為多少時 `((x & (~x + 1)) == x)` 為 true? * 當 x 為 power of 2 時 * 因為只有 power of 2 只有一個 bit 為 1 因此 `return x && ((x & (~x + 1)) == x)` 的意思就是檢驗 x 是否為 power of 2 (但要扣除 0) 現在來思考第二段程式碼 ```cpp bool func(unsigned int x) { unsigned int unknown = 0; while (x && unknown <= 1) { if ((x & Z) == 1) unknown++; x >>= 1; } return (unknown == 1); ``` 可以看到只有當 unknown 為 1 時才會 return true，那麼結合我們從第一段程式碼得知的訊息，可以推知 unknown 在紀錄的是 x 有幾個 bit 為 1 ```cpp if ((x & Z) == 1) unknown++; ``` 接著我們可以看到當 if 判斷式為 true 時 unknown 會 +1，可以推知可能是在檢驗某一個 bit 是否為 1 又可以從 `(x & Z) == 1` 推測檢驗的是最右邊的 bit，因此 `Z` 為 1 :::success 延伸題目: 舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。 ::: 想好久，終於想到兩個類似的例子，雖然很簡單，<s>而且好像有在哪看過</s>，但我還是把它寫下來吧 :::danger 工程人員說話要精準，不要「憑感覺」，及早脫離 Ptt 鄉民口中的「文組」 :notes: jserv ::: 假設 a 為 32-bit integer #### 例子1 * non-const time: 當 a >= 0 時才去做 a++ 的運算 ```cpp if (a >= 0) a++; return a; ``` * const time: ```cpp a = a + (a >> 31) + 1; return a ``` 分為三種狀況去證明具有一樣的運算效果 * a > 0 : 這種情況時 a >> 31 的結果還是 0，因此運算式變成 a = a + 0 +1，也就是 a = a + 1 * a == 0 : 這種情況 a >> 31 的結果也還是 0，因此運算式變成 a = a + 0 +1，也就是 a = a + 1 * a < 0 : 這種情況 a >> 31 的結果變成 111...111，也就是 -1，因此運算式變成 a = a + (-1) + 1，也就是 a = a #### 例子2 * non-const time: 當 a > 0，才去做某個運算 ```cpp if (a > 0) b = b + a; return b; ``` * const time: ```cpp b = b + (a & ~(a >> 31)); return b; ``` * a >= 0 :這種情況時 a >> 31 的結果為 0，反轉後變成 0xffffffff，因此 & 之後就還是 a * a < 0 : 這種情況時 a >> 31 的結果為 0xffffffff，反轉後變成 0，因此 & 之後就變成 0