# 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)