---
# System prepended metadata

title: 'linux2021: st9540808'
tags: [linux2021]

---

# 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 出多少個行程

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

令 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。

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


> #### 比較
> `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},
};
```