# linux2021: AndybnACT
## 測驗 ϵ - 1
解釋上述程式碼運作原理:
在主程式中，我們可以看到有四個進入點，分別是將 memory pool 做初始化的 `mpool_init()`、配空間的 `mpool_alloc`、將空間歸還 memory pool 的 `mpool_repool`、以及釋放整個 memory pool 的 `mpool_free`。
程式運作的核心概念是根據配置大小對 pool 做分類，在每一個類別 (pool) 中用 array 來區隔每個可配置區、然後用 linked-list 將配置出來 array 中每個元素串成 free list 做配置及釋放（repool）的管理。
### `struct mpool`
```
typedef struct {
int cnt; /* actual pool count */
int pal; /* pool array length (2^x ceil of cnt) */
int min_pool, max_pool; /* minimum/maximum pool size */
void **ps; /* pools */
int *sizes; /* chunk size for each pool */
void *hs[1]; /* heads for pools' free lists */
} mpool;
```
程式中，用上列結構來管理 memory pool。其中，`cnt` 是實際 memory pool 可配置分類區的數量。 `pal` 則是取 `cnt` 的 order 2 ceiling，如：若 `cnt` 為 5，則 `pal` 為大於等於 5 之最小 2 的冪次方值，8。這和 `mpool` 的擴充機制有關。
`pal` 會大於等於 `cnt` 的原因可以參考 `add_pool()`。當使用者需要配置某個大小的空間，而對應的 pool 僅剩下一個可配置區塊（free list 已經指向尾端）時，會透過 `mpool_new_pool()` 配置一塊完整的 pool，然後再由 `add_pool()` 將 free list 繼續串下去。而這些新產生的 pool 的管理，就都放在初始索引 `cnt` 之後的位置中、然後再將 `cnt++`。只有在 `cnt` 撞到頂（`cnt == pal`）的時候，透過 `realloc` 將 `pal` 配置為原先的兩倍（為 *dynamic array* 的做法，目的使得尾端的 insertion 和 `repool()/alloc()` 在找到 `i` 之後存取可以有 constant time。`i` 有 constant time 找法，但是 `alloc()` 沒有這樣做 ）。把新產生的 pool 放進 `ps[]` 中還有的好處是：這樣之後在釋放整個 `mpool` 時，就不用再去找 `mpool_new_pool()` 產生的區塊位置，直接將 `ps[]` 的索引走完就即可。
`min_pool` 和 `max_pool` 用來標記 pools 中，能配置給使用者區塊大小的最大及最小值。用來做邊界判斷。
由 `ps`、 `sizes`、`cnt`、`pal` 所組成的 dynamic array 中，`ps` 代表的是分別是實際各 pool 的位置、`sizes` 則是各 pool 中對應的可配置大小，`cnt` 是當前 array 的尾端、`pal` 是當前 array 大小的邊界。
`hs` 在這個結構中，是 *flexible array member*，大小在初始配置時產生。代表的是各個可配置 pool 的 free list。此 array 的大小在初始（`init()`）配置後就是固定的，因為 free list 大小只和可配置區段的範圍有關。
```c++
mpool *mp = malloc(sizeof(mpool) + (cnt - 1) * sizeof(void *));
```
### `mpool_init()`
用來初始化 memory pool、填上 dynamic array 各項初始數值。這裡還沒有實際將可配置區（pools）分配出來。可以看到 `pools`、`sizes`、`hs` 都被初始化成零。
```c++
/* Initialize a memory pool for allocations between 2^min2 and 2^max2,
* inclusive. Larger allocations will be directly allocated and freed
* via mmap / munmap.
* Returns NULL on error.
*/
mpool *mpool_init(int min2, int max2)
{
int cnt = max2 - min2 + 1; /* pool array count */
int palen = iceil2(cnt);
assert(cnt > 0);
mpool *mp = malloc(sizeof(mpool) + (cnt - 1) * sizeof(void *));
void *pools = malloc(palen * sizeof(void **));
int *sizes = malloc(palen * sizeof(int));
if (!mp || !pools || !sizes)
return NULL;
mp->cnt = cnt;
mp->ps = pools;
mp->pal = palen;
mp->sizes = sizes;
mp->min_pool = (1 << min2), mp->max_pool = (1 << max2);
memset(sizes, 0, palen * sizeof(int));
memset(pools, 0, palen * sizeof(void *));
memset(mp->hs, 0, cnt * sizeof(void *));
return mp;
}
```
### `mpool_alloc()`
透過 `mpool_init()` 初始化 memory pool 之後，使用者就可以透過 `mpool_alloc` 向 memory pool 索取空間。
```c++
/* Allocate memory out of the relevant memory pool.
* If larger than max_pool, just mmap it. If pool is full, mmap a new one and
* link it to the end of the current one.
* Returns NULL on error.
*/
void *mpool_alloc(mpool *mp, int sz)
{
void **cur;
int i, p;
assert(mp);
```
如果是超出 memory pool 所能提供的最大可配置大小，就直接用 `mmap()` 的方式和系統要空間。
```c++
if (sz >= mp->max_pool) {
cur = get_mmap(sz); /* just mmap it */
if (!cur)
return NULL;
return cur;
}
```
接著，根據 `sz` 找到對應 pool 的索引值。找尋索引的方式是在每次 iteration 中比較 `i` 對應到的 pool 可配置空間是否大於所需空間，然後再將可配置空間和 `i` 遞增。但其實這裡可以先將 sz 取 order 2 ceiling，若前後相等則再將 sz * 2。得到 sz 之後可用 find first set 的方式得到其為 order N 的配置，配合 `min_pool` 就可以得到 `i`
```c++
long szceil = 0;
for (i = 0, p = mp->min_pool;; i++, p *= 2) {
if (p > sz) {
szceil = p;
break;
}
}
assert(szceil > 0);
```
找到 `i` 之後，如果這是使用者第一次配置，那 free list 會是空的。這時透過 `mpool_new_pool()`，空間才會真正分配出來、串成 linked-list。然後才把 pool 加進 `mpool` 當中、並且也將 free list 指向 linked-list 的頭。
```c++
cur = mp->hs[i]; /* get current head */
if (!cur) { /* lazily allocate and initialize pool */
void **pool = mpool_new_pool(szceil, PAGE_SIZE);
if (!pool)
return NULL;
mp->ps[i] = mp->hs[i] = pool;
mp->sizes[i] = szceil;
cur = mp->hs[i];
}
assert(cur);
```
當中，linked-list 的串法由 `mpool_new_pool()` 完成。作法如下：先向系統請求一段連續區塊，然後將連續區段以可配置大小為單位切成數等分。最後在每一等份的頭，把它當作 `void *`，寫下下一等份的起始位置。
---
after 23:04
---
在 pool 初次配置完成後，`*cur` 內的值應該會是 free list 中第二個元素。除非該 pool 的可配置大小比 `PAGE_SIZE` 還要大的時候，那整個 pool 會只有一個元素，此時 `(*cur)` 會是 `NULL`。其他符合此條件的情形有 free list 被拿到只剩最後一個 element 的時候。在這種情形下，會進入配置新 pool 的程式路徑。
配置的方法和第一次配置一樣，只是這個 pool 的相關資訊會透過 `add_pool()`，被加在 dynamic array 的尾端。因為 `mpool_alloc()` 一開始會檢查使用者需要的空間有沒有大於等於 `mpool->max_pool`，所以比 `max_pool` 還要大的配置不會誤入此區。
```c++
if (!(*cur)) { /* if at end, attach to a new page */
void **np = mpool_new_pool(szceil, PAGE_SIZE);
if (!np)
return NULL;
*cur = &np[0];
assert(*cur);
if (add_pool(mp, np, szceil) < 0)
return NULL;
}
assert(*cur > (void *) PAGE_SIZE);
```
最後，更新 free list。只要將 free list 的頭指向 linked list 下一個元素的位置即完成更新。
```c++
mp->hs[i] = *cur; /* set head to next head */
return cur;
}
```
### `mpool_repool()`
將配置出來的空間歸還給 pool。有了以 linked-list 為基礎的 free list，歸還空間的方式就是 list 的 insertion。因此我們只需要找到對應的 free list、把 free list 的頭替換成使用者歸還空間的位置、最後再將該位置起始 `sizeof(void *)` 的區段，寫成原本 free list 頭的位置，即完成 repool。
```c++
/* Push an individual pointer P back on the freelist for the pool with size
* SZ cells. if SZ is > the max pool size, just munmap it.
* Return pointer P (SZ bytes in size) to the appropriate pool.
*/
void mpool_repool(mpool *mp, void *p, int sz)
{
int i = 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;
```
因此，理想情況下 YYY 不能用一個表達式完成。因為要做的事包含了找到 `i`、以及改寫 `ip` 起始位置的值。可以用以下方式達成
```c++
for(;(mp->min_pool << i) <= sz; i++)
/* find i */;
*ip = mp->hs[i];
```
```c++
YYY;
assert(ip);
mp->hs[i] = ip;
}
```
## 測驗 ϵ - 2
提出效能和功能的改進策略，並予以實作：
可以將所有「找 `i`」的片段做如下更改：
```diff=
+#ifndef NEW
for (i = 0, p = mp->min_pool;; i++, p *= 2) {
if (p > sz) {
szceil = p;
break;
}
}
assert(szceil > 0);
+#else
+ if (sz < mp->min_pool) {
+ i = 0;
+ szceil = mp->min_pool;
+ } else {
+ szceil = iceil2(sz + 1);
+ long ffs_szceil = __builtin_ffs(szceil);
+ i = ffs_szceil - mp->min2 - 1;
+ }
+#endif
```
其中，`min2` 及 `max2` 用來記錄 `min_pool` 和 `max_pool` 二的冪次方
```diff=
typedef struct {
int cnt; /* actual pool count */
int pal; /* pool array length (2^x ceil of cnt) */
int min_pool, max_pool; /* minimum/maximum pool size */
+ int min2, max2;
void **ps; /* pools */
int *sizes; /* chunk size for each pool */
void *hs[1]; /* heads for pools' free lists */
} mpool;
```
測試環境如下：
```
CC = gcc-4.8
CFLAGS = -O2 -std=gnu11
cpuinfo: i9-7900X
```
使用 `perf stat` 執行測試，可以看到 branch miss 在改動過後有顯著減少。推測是少了 loop 的重複判斷所致：
```
[andy@superstorm5 quiz]$ make
gcc -std=gnu11 -O2 mpool.c
[andy@superstorm5 quiz]$ perf stat ./a.out
seed = 5df4ea
Performance counter stats for './a.out':
483.227860 task-clock:u (msec) # 1.002 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
90971 page-faults:u # 0.188 M/sec
558972494 cycles:u # 1.157 GHz
1189304467 instructions:u # 2.13 insn per cycle
279572903 branches:u # 578.553 M/sec
3989406 branch-misses:u # 1.43% of all branches
0.482204055 seconds time elapsed
[andy@superstorm5 quiz]$ make new
gcc -std=gnu11 -O2 -DNEW mpool.c
[andy@superstorm5 quiz]$ perf stat ./a.out
seed = 5df4ea
Performance counter stats for './a.out':
475.900771 task-clock:u (msec) # 1.002 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
90971 page-faults:u # 0.191 M/sec
540317858 cycles:u # 1.135 GHz
1231577718 instructions:u # 2.28 insn per cycle
269399773 branches:u # 566.084 M/sec
2489576 branch-misses:u # 0.92% of all branches
0.474930107 seconds time elapsed
```
## 測驗 ζ - 1
解釋上述程式碼運作原理
## 測驗 ζ - 2
以 epoll 系統呼叫改寫程式碼，並設計實驗來驗證 proxy 程式碼的效率
Sign in with Wallet
Connect another wallet