---
# System prepended metadata

title: 'linux2021: yiidtw'

---

# linux2021: yiidtw

## 測驗 $\beta$
MMM = `(sz + mask) & ~mask`

## 測驗 $\beta$-1

> 說明上述程式碼的運作原理


透過程式碼我們可以得知，給定一數值 alignment (僅討論為 alignment 自然數的情況下)，「 輸出大於等於 alignment 的記憶體對齊地址」的一般式為`(((sz + mask) / alignment) * alignment)`，而且當 alignment 為 2 的冪次時，求特殊解

這邊再細分兩小題，一小題是確認 `(alignment & mask) == 0` 確實為「alignment 為 power of 2 」的充要條件；另一小題是證明上述的一般式在此條件的特殊解為 `(sz + mask) & ~mask`

第一小題，首先我們觀察到
- `x`若為奇數，則 2 進位的`x`與`x - 1`比較，只差 LSB 的 1 個 bit，可得`x & (x - 1) = x - 1`
- `x`若為 2 的冪次，可假設`x`為 2<sup>k</sup>，以 2 進位表示，則`x`為 1 後面接著 k 個 0，`x - 1`為 k 個 1，是故 `x & (x - 1) = 0`，不過這只能證明必要條件成立
- `x`若為自然數時，`x - 1`會由 2 進位的`x`的最低位非零的 bit 借 1 位來減 1，因此我們可就上述兩點觀察得到`x & (x - 1)`一般情況的推論，claim: `x & (x - 1) =`(2 進位的`x`去掉最低位非零的 bit)

回到`x`為 2 的冪次的情況，由於此時 2 進位表示的`x`只有一個非零的 bit，因此`x`為 2 的冪次若且唯若`x & (x - 1) == 0`

第二小題，想要證明`(((sz + mask) / alignment) * alignment)`在`x`為 2 的冪次時，特殊解為`(sz + mask) & ~mask`，我們知道[除以二](https://zh.wikipedia.org/zh-tw/%E9%99%A4%E4%BB%A5%E4%BA%8C)在電腦科學上有特殊意義，可用右移 k 位加速除以 2<sup>k</sup>的計算，同理，又由於`uintptr_t`為 unsigned integer type，我們可以用邏輯左移 k 位加速乘以 2<sup>k</sup>的計算；因此若假設`alignment`為 2<sup>k</sup>，`(((sz + mask) / alignment) * alignment)` 這裡可視為對`(sz + mask)`先右移 k 位，再左移 k 位，即`(sz + mask)`去掉 2 進位表示法後最小 k 個位數的 bits

又由第一小題的觀察得知，此時`mask = alignment - 1 =`(2 進位表示法為 k 個 1)，可知`~mask`的 2 進位表示法為 k 個 0，恰可作為「去掉 2 進位表示法後最小 k 個位數的 bits」的遮罩，得證

Reference:
* [位元運算整理 - 前言 - HackMD](https://hackmd.io/@0xff07/ARIARIARIARI)
* [c - How to allocate aligned memory only using the standard library? - Stack Overflow](https://stackoverflow.com/questions/227897/how-to-allocate-aligned-memory-only-using-the-standard-library/227900)

## 測驗 $\gamma$
NNN = `12`

## 測驗 $\gamma$-1
> 解釋上述程式碼輸出 - 字元數量的原理

我們稍作觀察，設`n`為`-`打印出的數量
- `NNN = 1`，`n = 2`
- `NNN = 2`，`n = 8`
- `NNN = 3`，`n = 24`
- 推論一般式為`n = NNN * 2`<sup>`NNN`</sup>

推論歸推論，還是需要做一些實驗來證明

我們先稍微改一下程式碼，把`printf("-")`，換成打印更多訊息的`fprintf(stdout, "[%d] %d -> %d\n", i, getppid(), getpid());`，將 PID、parent PID 輸出至 stdout，並多加一行`wait(NULL);`，避免 parent process 在 child process 結束前先結束，整體改動如下
```language=c
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    for (int i = 0; i < 2; i++) {
        fork();
        // printf("-");        
        fprintf(stdout, "[%d] %d -> %d\n", i, getppid(), getpid());
        wait(NULL);	
    }
    
    fflush(stdout);
    return 0;
}
```

command line 執行方式如下，將 `fork` 執行結果 redirect 至 `2.stdout`
```
$ gcc -o fork fork.c && ./fork >2.stdout
```

`2.stdout` 內容如下 (不失一般性，我們假設 PID 剛好從 10000 開始取)
```
$ cat 2.stdout 
[0] 10001 -> 10002
[1] 10002 -> 10003
[0] 10001 -> 10002
[1] 10001 -> 10002
[0] 10000 -> 10001
[1] 10001 -> 10004
[0] 10000 -> 10001
[1] 10000 -> 10001
```

如同我們預期的，總共有 `n = 2 * 2`<sup>`2`</sup>`= 8`行輸出，這是由於當`fork()`發生時，parent process 的 memory 會以 [Copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write) 的方式複製一份給 child process，意即當改動發生，child process 會保有獨有改動的部分，其他 memory footprint 仍為 parent process 的內容

而從[CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)我們可以知道，這是由於 stdout 預設是 buffered I/O ，要寫入 stdout 的內容會先塞入 buffer ，直到 stdout 被 flush

綜合上述的背景知識，我們知道 child process 會將 parent process 要輸出的內容在`fork`的時候照搬一份，只改動自己修改過的變數內容，其餘保持不變，我們使用 unbuffered I/O 的 stderr 再試一次，將`fprintf(stdout, "[%d] %d -> %d\n", i, getppid(), getpid());` 改為`fprintf(stderr, "[%d] %d -> %d\n", i, getppid(), getpid());`，執行方法如下

```
$ gcc -o fork fork.c && ./fork >2.stderr 2>&1
```

我們將 stderr redirect 至 stdout ，看一下結果 (同樣在不失一般性下，我們假設 PID 剛好從 10000 開始取)
```
$ cat 2.stderr
[0] 10000 -> 10001
[0] 10001 -> 10002
[1] 10001 -> 10002
[1] 10002 -> 10003
[1] 10000 -> 10001
[1] 10001 -> 10004
```

可以發現 unbuffered I/O 此時只有 6 行輸出，我們畫個圖來看`fork()`的執行過程會更清楚

![](https://i.imgur.com/ZoEFjUb.png)

箭頭代表`fork()`，黑球代表 unbuffered I/O 的輸出，白球(以及斜體字)代表 buffered I/O 的額外輸出，是由其 parent process 複製而來的，因此我們可以觀察其規律，claim 如下

- `unbuffer I/O 輸出的 "-" = (黑球)的個數 = 2`<sup>`NNN + 1`</sup>`- 2`
- `buffer I/O 輸出的 "-" = (黑球 + 白球)的個數 = NNN * 2`<sup>`NNN`</sup>

我們再進一步觀察，可以發現 unbuffered I/O 與 buffered I/O 的輸出順序也不同

- unbuffered I/O 是按照程式邏輯的語義輸出，以上圖來說，就是由左至右、由上至下順序輸出，忽略白球不計
```
    [0] 10000 -> 10001
    [0] 10001 -> 10002
    [1] 10001 -> 10002
    [1] 10002 -> 10003
    [1] 10000 -> 10001
    [1] 10001 -> 10004
```
- buffered I/O 則是將每個 PID 看作是 N-way tree 的一個 node，依照 post-order 輸出，我們可將黑白球的圖右轉 90 度，可能更方便理解為一顆 N-way tree 如下圖，並以 PID 為單位，兩兩一組(若為 N-way 則為 N 筆輸出為一組)，依照 post-order(RLN) 輸出，`PID:10003 -> PID:10002 -> PID:10004 -> PID:10001`，其中打 * 號者為白球輸出

    ![](https://i.imgur.com/f5UuPDU.png)
```
    [0] 10001 -> 10002 * (copy from PID: 10002)
    [1] 10002 -> 10003
    [0] 10001 -> 10002
    [1] 10001 -> 10002
    [0] 10000 -> 10001 * (copy from PID: 10001)
    [1] 10001 -> 10004
    [0] 10000 -> 10001
    [1] 10000 -> 10001
```

到此我們在`fork()`時，unbuffered 與 buffered I/O 輸出的差異，除了用 unbuffered I/O stream (如 stderr) ，我們也可以透過提早做`fflush(stdout)`，使得執行結果如程式邏輯的預期；下面提供`NNN = 3`時的執行結果供讀者作驗算，一樣不失一般性假設 PID 由 10000 開始，
- 3-way tree post-order(RLN) 為
```
    PID:10004 
    -> PID:10003 
    -> PID:10005 
    -> PID:10002 
    -> PID:10007 
    -> PID:10006 
    -> PID:10008 
    -> PID:10001
```
- buffered I/O output when`NNN = 3`，`count = 3 * 2`<sup>3</sup>`= 24`
```
    [0] 10001 -> 10002 * (copy from PID:10003)
    [1] 10002 -> 10003 * (copy from PID:10003)
    [2] 10003 -> 10004
    [0] 10001 -> 10002 * (copy from PID:10002)
    [1] 10002 -> 10003
    [2] 10002 -> 10003
    [0] 10001 -> 10002 * (copy from PID:10002)
    [1] 10001 -> 10002 * (copy from PID:10002)
    [2] 10002 -> 10005
    [0] 10001 -> 10002
    [1] 10001 -> 10002
    [2] 10001 -> 10002
    [0] 10000 -> 10001 * (copy from PID:10006)
    [1] 10001 -> 10006 * (copy from PID:10006)
    [2] 10006 -> 10007
    [0] 10000 -> 10001 * (copy from PID:10001)
    [1] 10001 -> 10006
    [2] 10001 -> 10006
    [0] 10000 -> 10001 * (copy from PID:10001)
    [1] 10000 -> 10001 * (copy from PID:10001)
    [2] 10001 -> 10008
    [0] 10000 -> 10001
    [1] 10000 -> 10001
    [2] 10000 -> 10001
```
- unbuffered I/O output when `NNN = 3`，`count = 2`<sup>3 + 1</sup>`- 2 = 14`
```
    [0] 10000 -> 10001
    [0] 10001 -> 10002
    [1] 10001 -> 10002
    [1] 10002 -> 10003
    [2] 10002 -> 10003
    [2] 10003 -> 10004
    [2] 10001 -> 10002
    [2] 10002 -> 10005
    [1] 10000 -> 10001
    [1] 10001 -> 10006
    [2] 10001 -> 10006
    [2] 10006 -> 10007
    [2] 10000 -> 10001
    [2] 10001 -> 10008
```

Reference:
* [一个fork的面试题 | 酷 壳 - CoolShell](https://coolshell.cn/articles/7965.html)