---
# System prepended metadata

title: 2019q3 Homework1 (review)
tags: [sysprog2019]

---

# 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