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 大小只和可配置區段的範圍有關。

mpool *mp = malloc(sizeof(mpool) + (cnt - 1) * sizeof(void *));

mpool_init()

用來初始化 memory pool、填上 dynamic array 各項初始數值。這裡還沒有實際將可配置區（pools）分配出來。可以看到 pools、sizes、hs 都被初始化成零。

/* 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 索取空間。

/* 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() 的方式和系統要空間。

    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

    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 的頭。

    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 還要大的配置不會誤入此區。

    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 下一個元素的位置即完成更新。

    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。

/* 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 起始位置的值。可以用以下方式達成

for(;(mp->min_pool << i) <= sz; i++)
    /* find i */;
*ip = mp->hs[i];

    YYY;
    assert(ip);
    mp->hs[i] = ip;
}

測驗 ϵ - 2

提出效能和功能的改進策略，並予以實作：
可以將所有「找 i」的片段做如下更改：

+#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 二的冪次方

  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 程式碼的效率