# linux2021: st9540808
###### tags: `linux2021`
## 測驗 $α - 1$
我翻了 Linux 所有 `ror` `rol` 系列的操作，發現他們大多使用在密碼學的操作上，如 SHA-256。Linux kernel 當中以 [Crypto API](https://www.kernel.org/doc/html/latest/crypto/index.html) 封裝好的介面提供給開發者使用。
[lib/crypto/sha256.c
](https://elixir.bootlin.com/linux/latest/source/lib/crypto/sha256.c#L50)
```c=55
#define e0(x) (ror32(x, 2) ^ ror32(x, 13) ^ ror32(x, 22))
#define e1(x) (ror32(x, 6) ^ ror32(x, 11) ^ ror32(x, 25))
#define s0(x) (ror32(x, 7) ^ ror32(x, 18) ^ (x >> 3))
#define s1(x) (ror32(x, 17) ^ ror32(x, 19) ^ (x >> 10))
```
`SHA256_ROUND` 裡面就有使用到以上用 circular shift 定義的巨集，`SHA256_ROUND` 總共會做 64 次，完成後便是用 SHA-256 演算法計算出的雜湊值。
```c=65
#define SHA256_ROUND(i, a, b, c, d, e, f, g, h) do { \
u32 t1, t2; \
t1 = h + e1(e) + Ch(e, f, g) + SHA256_K[i] + W[i]; \
t2 = e0(a) + Maj(a, b, c); \
d += t1; \
h = t1 + t2; \
} while (0)
```
而在 Linux kernel 何時會用到 SHA-256 呢?，其中一個應用是與 RSA 合併使用產生數位簽章，當 kernel module 載入到 kernel 時，會檢查雜湊值和在 kernel 內部計算的雜湊值是否相等，如此一來便能避免惡意的 kernel module 破壞系統，而在沒有 RSA key 或是 unsigned 的情況下，kernel 就會被標示為 tainted。
參考: https://www.kernel.org/doc/html/v5.0/admin-guide/module-signing.html
---
## 測驗 $β - 1$
`align_up` 以數學來說就是 round up to next multiple of `sz`
因為 2 的 $n$ 次在二進位有很好的性質，只有第 $n$ 個位元為 1，而對 2 的冪次減 1，則會第 $n$ 個位元的右邊全為 1，其他為 0。
```c
uintptr_t mask = alignment - 1;
return (sz + mask) & ~mask;
```
以上述程式碼解說，假設 `sz` 不為 `alignment` 的倍數，則 `(sz + mask)` $\geq$ `alignment` 的下一個倍數。做 `& ~mask` 會將第 n 個位元右邊清為 0，讓最終數值為 `alignment` 的倍數。
反之若 `sz` 為 `alignment` 倍數，則 `(sz + mask)` $<$ `alignment` 的下一個倍數。做完 `& ~mask` 後數值仍為 `sz`。
## 測驗 $γ - 1$
先仔細看這一題使用的命令
```bash
$ ./fork | wc -c
```
`./fork` 的 stdout 輸出會被重新導向到 pipe 中，所以 `./fork` 輸出不會遇到 `\n` 就清空緩衝區，雖然本題也沒有印出換行字元，但還是要注意差異 (我在測試的時候就遇到印到終端機，跟重導至 `wc` 兩者結果不符合的情況)。
再來看程式中總共會 fork 出多少個行程
令 i=2，則題目產生的行程就跟上圖程式碼生成的行程數目一樣，第一次呼叫 `fork` 會產生一個子行程，總共為 2 個行程，第二次呼叫 `fork` 時這兩個行程會各自再產生一個行程，最後總共為 4 個行程，因此可以歸納，題目中總共會產生的行程為 $2^{NNN}$ 個。
```c
for (int i = 0; i < 2; i++) {
fork();
printf("%d -\n", getpid());
}
fflush(stdout);
```
最後考慮 buffered IO 造成的影響，每次呼叫 `fork` 都會產生一個與父行程相同的子行程，這也包括在緩衝區內的資料。第一次迴圈結束時，兩個行程的緩衝區中都有一個 "-"，到了第二次迴圈，fork 會把父行程的資料複製給子行程，所以最後四個行程的緩衝區都有兩個 "-"。因此上面程式碼最後應輸出 $2^2 \times 2 = 8$ 個 "-"
因此輸出 "-" 個數用 NNN 表示為
$2^{NNN} \times NNN$
把這串 $2^x \times x = 49152$ 丟到 Wolfram 就可以解出 $x$ 了。
$x = 12$
## 測驗 $δ - 1$
我這題前兩個子題是寫錯的，但在我的機器上執行印出錯誤訊息。
### AAA (寫錯)
想法: 將新分配的節點插入佇列的最後一個元素，插入的操作是在臨界區間內進行。
```diff
int con_push(con_queue_t *restrict queue, void *restrict new_element)
{
/* Prepare new node */
node_t *node = _con_node_init(new_element);
if (!node)
return Q_ERROR;
/* Add to queue with lock */
mtx_lock(queue->last_mutex);
- AAA;
+ queue->last->next = node;
queue->last = node;
mtx_unlock(queue->last_mutex);
return Q_OK;
}
```
### BBB (寫錯) and CCC
想法: 將 `node` 的值取出後放到 return value，佇列的第二個元素變成首位元素。
```diff
void *con_pop(con_queue_t *queue)
{
mtx_lock(queue->first_mutex);
node_t *node = queue->first; /* Node to be removed */
node_t *new_header = queue->first->next; /* become the first in the queue */
/* Queue is empty */
if (!new_header) {
mtx_unlock(queue->first_mutex);
return NULL;
}
/* Queue not empty: retrieve data and rewire */
- void *return_value = BBB;
- CCC;
+ void *return_value = node->value;
+ queue->first = new_header;
mtx_unlock(queue->first_mutex);
/* Free removed node and return */
free(node);
return return_value;
}
```
## 測驗 $ϵ - 1$
`mpool` 有數個相同大小的 memory pool，每一個 memory pool 大小均為一個頁面 (4096 bytes)，分別能夠提供 $2^4$ 到 $2^{11}$ bytes 的記憶體區塊，當呼叫 `mpool_alloc` 時會選擇一個適當的 memory pool，並從中拿出一個合乎使用者指定大小的 block 出來。
例如當呼叫
```c
mpool_alloc(mp, 53)
```
表示使用者要求一塊大小為 53 bytes 的記憶體區塊，因此題目的程式會選擇能提供 $2^6$ bytes 大小的 memory pool，並從中挑選一個 64 bytes 區塊給使用者。
實作 memory pool 記憶體分配最重要的機制是 free list，題目中實作的是單向鏈結串列，在第一次需要特定範圍大小記憶體時，lazily allocate 一個 memory pool 的並初始化 free list 串列。
以下為一個 memory pool 剛初始化完成的 memory dump，`0x7ffff7ffb000` 是這個 memory pool 的起始位址，它能提供的物件大小最大為 32 bytes，前 8 個 byte 指向下一個記憶體區塊，當提供給使用者時這個值會被覆蓋掉。
```
0x7ffff7ffb000: 0xf7ffb020 0x00007fff 0x00000000 0x00000000
0x7ffff7ffb010: 0x00000000 0x00000000 0x00000000 0x00000000
0x7ffff7ffb020: 0xf7ffb040 0x00007fff 0x00000000 0x00000000
0x7ffff7ffb030: 0x00000000 0x00000000 0x00000000 0x00000000
0x7ffff7ffb040: 0xf7ffb060 0x00007fff 0x00000000 0x00000000
0x7ffff7ffb050: 0x00000000 0x00000000 0x00000000 0x00000000
0x7ffff7ffb060: 0xf7ffb080 0x00007fff 0x00000000 0x00000000
0x7ffff7ffb070: 0x00000000 0x00000000 0x00000000 0x00000000
```
`mpool` 實作的 memory pool 長的像下面這張圖，`mp->ps` 指標陣列每一個元素會指向一個 memory pool，而每一個 memory pool 分別提供不同大小的記憶體區塊，並以單向鏈結串列的形式維護 free list。
> #### 比較
> `mp->ps[i]` 指向 memory pool 的起始位址
> `mp->hs[i]` 為 free list，維護所有能使用的記憶體區塊
最後當使用者要回收一塊記憶體時，會呼叫 `mpool_repool`，`mp->hs` 中的每個元素本質上也是一個單向鏈結串列，指向的是所有 free block 的 head
## 測驗 $ϵ - 2$
### 改進方法
在 `mpool_repool` 的實作中，回收時會將記憶體指標插入 `mp->hs[0]` 此串列的 head，但因為不同大小的記憶體區塊都會被回收到 `mp->hs[0]`，所以如果再次從 `mp->hs[0]` 提供記憶體給使用者，則會出現較嚴重的 *internel fragmentation*，因為 `mp->hs[0]` 這個串列能提供的大小為 16 bytes，但是此串列其實有更大的記憶體區塊。
因此比較好的實作方式是重新找到要插入的 free list，例如提供 32 bytes 記憶體區塊的 memory pool ，要回收時就插入此對應的 free list (也就是 `mp->hs[1]`)，而不是全部都塞給 `mp->hs[0]`。
以下為一個可能的 `mpool_repool` 實作，已通過壓力測試
```diff
void mpool_repool(mpool *mp, void *p, int sz)
{
- int i = 0;
+ int i = max(__builtin_ctz(iceil2(sz)) - mp->min_pool, 0);
if (sz > mp->max_pool) {
if (munmap(p, sz) == -1)
fprintf(stderr, "Failed to unmap %d bytes at %p\n", sz, p);
return;
}
void **ip = (void **) p;
*ip = mp->hs[i];
assert(ip);
mp->hs[i] = ip;
}
```
上面新增的程式碼也可以套用在 `mpool_alloc`，將計算 szceil 的方法用相同的想法改寫。
下表的程式碼位於 `mpool_alloc` 函式中
```diff=160
long szceil = 0;
- for (i = 0, p = mp->min_pool;; i++, p *= 2) {
- if (p > sz) {
- szceil = p;
- break;
- }
- }
+ i = max(__builtin_ctz(iceil2(sz)) - mp->min_pool, 0);
+ szceil = mp->min_pool << i;
assert(szceil > 0);
```
### 效能評估
使用 [bench](https://hackage.haskell.org/package/bench) 對題目提供的壓力測試做 microbenchmark
實驗平台
| CPU | Distro | Kernel |
| -------- | -------- | -------- |
| i7-11700 (8C16T) | Ubuntu 20.04-LTS | 5.11.0 |
#### 原始版本
```a
time 283.5 ms (281.0 ms .. 285.4 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 284.1 ms (283.0 ms .. 284.7 ms)
std dev 987.2 μs (527.0 μs .. 1.321 ms)
variance introduced by outliers: 16% (moderately inflated)
```
#### 改進後版本
```a
time 201.6 ms (200.6 ms .. 202.6 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 200.7 ms (200.1 ms .. 201.3 ms)
std dev 854.5 μs (660.3 μs .. 1.040 ms)
variance introduced by outliers: 14% (moderately inflated)
```
僅僅是修改幾行程式碼效能就變成原來的 ==1.41== 倍！
## 測驗 $ζ - 1$
題目實作一個 port forwarding 的 proxy，遠端伺服器傳給本機的資料都會經過 proxy，反之亦然。
首先 main 會監聽 1922 埠號，當使用者連線到 proxy，會再建立另一個 socket 連線到 argv 指定的 IP (本題為 www.google.com 的 IP) 接著就控制權就交給 `proxy` 函式。
到了 `proxy` 函式，`poll(2)` 會檢查本機連到 proxy 的 socket，和 proxy 連到遠端伺服器的 socket 是否就緒，也就是本機有東西要傳送的時候 (如發出 `GET /index.html` HTTP Request 時)，或者是遠端伺服器傳送東西給 proxy (如收到 HTTP Response)，這時會呼叫 `move`。
`move` 是用 Linux 特有的系統呼叫 `splice(2)` 實作，用法類似 `sendfile(2)` 能夠將兩個 fd (file descriptor) "併接"，直接將一個 fd 的資料複製到另一個 fd，而不須經過任何 user-space 的緩衝區，以實作 zero copy 提升傳輸效率。
在任一時間點當有兩個 socket 有其中一個就緒時，就會將呼叫 `move`，傳輸時不用經過 proxy 的緩衝區即可將資料複製給另一個 socket。
另外我提交以下程式碼在 google 表單得到錯誤的結果，我在實際測試時只成功傳輸第一次 HTTP Request 並得到 Response，之後再送出 HTTP Request 便沒有回應，推測應該是這個有關，但我還不知道原因。
```c=66
struct pollfd polls[2] = {
[1] = {.fd = target_fd, .events = POLLIN},
[0] = {.fd = cl_fd, .events = POLLIN},
};
```
Sign in with Wallet
Connect another wallet