---
tags: LINUX KERNEL, LKI
---

# [2021 年暑期「Linux 核心」](https://hackmd.io/@sysprog/linux2021-summer)課程先決測驗題

:::info
:information_source: [2021 年暑期「Linux 核心」](https://hackmd.io/@sysprog/linux2021-summer)課程大部分教材 (含解說錄影) 可公開存取 (因此就算報名失敗，也可免費學習)，但之所以要求報名者先通過測驗 (依據作答表現排序) 才能完成報名，是因為授課教師會**逐一批改作業**和針對學員的學習狀況**進行一對一討論**，若不限制名額，實在難以進行，還請包涵。 -- [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)
:::

:::warning
:warning: 注意事項
1. 測驗時間: 2021 年 7 月 6 日到 2021 年 7 月 18 日 23:00
* 可優先作答下方測驗題 $\alpha$ 到 $\zeta$ (並及早填寫[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfAdDd0p7vgDFUjAM_aZ-xQy1olnaV6mlRcLu0fMA43-5-Uaw/viewform))，至於測驗題 $\eta$ 可在指定的 [HackMD](https://hackmd.io/) 建立後，再逐步改進和補充
* ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfAdDd0p7vgDFUjAM_aZ-xQy1olnaV6mlRcLu0fMA43-5-Uaw/viewform)== :notebook:
2. 測驗的目的是為了控制學員的數量，並非評價學員的能力，請斟酌進行
3. 可使用 Google 搜尋，但請不要借助技術論壇提問來進行這些題目，儘量「==誠實面對自己==」
4. 建議用 25 分鐘 (或更長時間) 來進行測驗題
5. 所有測驗題的程式碼都該符合 C99 或 C11 規範
6. 作答儘量用簡短的程式碼，且二元運算子 (binary operator，如 `+` [加法], `-` [減法], `*` [乘法], `^`, `&` [逐位元 AND] 等等) 和運算元 (operand) 之間用一個空白字元 (不多不少!) 區隔，如 `(v >> c)`、逗點 (`,`) 後應該有空白或換行符號，並避免非必要的小括號 (即 `(` 和 `)`)，也該刪去 (trim) 起始/結尾的空白字元
* 程式碼排版風格可見 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format)
7. 顧及批改的便利，本測驗採用 Google 表單自動比對參考答案，難免會有疏漏的答案組合 (特別是程式碼風格的落差)，請發訊息到[授課教師的 Facebook 粉絲專頁](https://www.facebook.com/JservFans)告知和討論
8. 測驗結束後，凡符合報名條件者，會由授課教師以電子郵件聯繫 (來自 `<[e-mail]>`)，通知課程事宜和提供電子書
:::

---

### 測驗 $\alpha$

考慮到位元旋轉 (bitwise rotation 或 bit rotation) 的操作:

以下程式碼可建立針對不同位元的向左/向右位元旋轉的實作:

#include <stdint.h>
  
#define __DECLARE_ROTATE(bits, type)                   \
    static inline type rotl##bits(const type v, int c) \
    {                                                  \
        const int mask = (bits) - (1);                 \
        c &= mask;                                     \
                                                       \
        return (v << c) | (LLL);                      \
    }                                                  \
                                                       \
    static inline type rotr##bits(const type v, int c) \
    {                                                  \
        const int mask = (bits) - (1);                 \
        c &= mask;                                     \
                                                       \
        return (v >> c) | (RRR);                      \
    }

#define DECLARE_ROTATE(bits) __DECLARE_ROTATE(bits, uint##bits##_t)

使用案例:

DECLARE_ROTATE(64);
DECLARE_ROTATE(32);
DECLARE_ROTATE(16);
DECLARE_ROTATE(8);

請填補上述 `LLL` 和 `RRR` 區域的程式碼，限制只能用 `+`, `-`, `|`, `&`, `^`, `<<`, `>>` 等運算子，不得出現 [ternary conditional operator](https://en.wikipedia.org/wiki/%3F:) (即 `?` 搭配 `:`)，且不該出現 `bits`。

==作答區==
LLL = ?
RRR = ?

:::success
延伸問題:
1. 舉出 Linux 核心原始程式碼裡頭 bit rotation 的案例並說明
2. [x86_64 指令集](https://en.wikipedia.org/wiki/X86_instruction_listings)具備 `rotr` 和 `rotl` 指令，上述 C 程式碼經過編譯器最佳化 (例如使用 `gcc`) 後，能否運用到這二個指令呢？
:::

---

### 測驗 $\beta$

以下程式碼可針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址:

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return MMM;       
    }
    return (((sz + mask) / alignment) * alignment);
}

已知 alignment 不為 `0`，參考執行輸出:

align_up(120, 4) = 120
align_up(121, 4) = 124
align_up(122, 4) = 124
align_up(123, 4) = 124

請填補上述 `MMM` 標注的程式碼，使得執行結果符合預期。限制只能用 `+`, `-`, `|`, `&`, `^`, `~`, `<<`, `>>` 等運算子，不得出現 [ternary conditional operator](https://en.wikipedia.org/wiki/%3F:) (即 `?` 搭配 `:`)，且不該出現 `alignment`

==作答區==
MMM = ?

:::success
延伸問題:
1. 說明上述程式碼的運作原理
2. 在 Linux 核心原始程式碼找出類似 `align_up` 的程式碼，並舉例說明其用法
:::

---

### 測驗 $\gamma$

在 GNU/Linux 環境，假設我們編譯的程式都會動態連結到 [glibc](https://www.gnu.org/software/libc/) 提供的 `libc.so.6`，考慮以下程式碼: (檔名: `fork.c`)

#include <stdio.h>
#include <unistd.h>

int main(void)
{
    for (int i = 0; i < NNN; i++) {
        fork();
        printf("-");                         
    }

    fflush(stdout);
    return 0;
}

編譯程式碼:

$ gcc -o fork fork.c

執行並統計有多少 `-` 字元輸出:

$ ./fork | wc -c

若要讓 `./fork | wc -c` 的輸出為 `49152`，那上方程式碼的 `NNN` 應為何值？注意：應該考慮 buffered I/O 的影響，可參考 [CS:APP 第 10 章](https://hackmd.io/@sysprog/H1TtmVTTz)。

==作答區==
NNN = ?

:::success
延伸問題:
1. 解釋上述程式碼輸出 `-` 字元數量的原理
:::

---

### 測驗 $\delta$

考慮以下 C11 程式碼，實作[並行 (concurrent)](https://hackmd.io/@sysprog/concurrency) 的多個生產者、多個消費者的佇列 (multi-producer, multi-consumer queue)，列表如下: (檔名: `queue.c`)

#include <threads.h>

enum { Q_OK, Q_ERROR };

typedef struct { /* Queue node */
    void *value;
    void *next;
} node_t;

typedef struct { /* Two lock queue */
    node_t *first, *last;
    mtx_t *first_mutex, *last_mutex;
} con_queue_t;

/* Free the queue struct. It assumes that the queue is depleted, and it will
 * not manage allocated elements inside of it.
 */
void con_free(con_queue_t *);

#include <stdlib.h>
#include <string.h>

inline static node_t *_con_node_init(void *value)
{
    node_t *node = malloc(sizeof(node_t));
    if (!node)
        return NULL;

    node->value = value;
    node->next = NULL;

    return node;
}

/* Allocates and initializes queue.
 * Returns a pointer to an allocated struct for the synchronized queue or NULL
 * on failure.
 */
con_queue_t *con_init()
{
    /* Allocate queue */
    con_queue_t *queue = malloc(sizeof(con_queue_t));
    if (!queue)
        return NULL;

    if ((queue->first_mutex = malloc(sizeof(mtx_t))) == NULL) {
        free(queue);
        return NULL;
    }
    if ((queue->last_mutex = malloc(sizeof(mtx_t))) == NULL) {
        free(queue->first_mutex);
        free(queue);
        return NULL;
    }

    if (mtx_init(queue->first_mutex, mtx_plain) != thrd_success ||
        mtx_init(queue->last_mutex, mtx_plain) != thrd_success) {
        con_free(queue);
        return NULL;
    }

    node_t *dummy = _con_node_init(NULL);
    if (!dummy) {
        con_free(queue);
        return NULL;
    }

    queue->first = queue->last = dummy;

    return queue;
}

void con_free(con_queue_t *queue)
{
    if (!queue)
        return;

    if (!queue->first)
        free(queue->first);

    if (queue->first_mutex) {
        mtx_destroy(queue->first_mutex);
        free(queue->first_mutex);
    }
    if (queue->last_mutex) {
        mtx_destroy(queue->last_mutex);
        free(queue->last_mutex);
    }

    free(queue);
}

/* Add element to queue. The client is responsible for freeing elementsput into
 * the queue afterwards. Returns Q_OK on success or Q_ERROR on failure.
 */
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 = node;
    mtx_unlock(queue->last_mutex);

    return Q_OK;
}

/* Retrieve element and remove it from the queue.
 * Returns a pointer to the element previously pushed in or NULL of the queue is
 * emtpy.
 */
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;

    mtx_unlock(queue->first_mutex);

    /* Free removed node and return */
    free(node);
    return return_value;
}

#include <assert.h>
#include <stdio.h>

#define N_PUSH_THREADS 4
#define N_POP_THREADS 4
#define NUM 1000000

/* This thread writes integers into the queue */
int push_thread(void *queue_ptr)
{
    con_queue_t *queue = (con_queue_t *) queue_ptr;

    /* Push ints into queue */
    for (int i = 0; i < NUM; ++i) {
        int *pushed_value = malloc(sizeof(int));
        *pushed_value = i;
        if (con_push(queue, pushed_value) != Q_OK)
            printf("Error pushing element %i\n", i);
    }

    thrd_exit(0);
}

/* This thread reads ints from the queue and frees them */
int pop_thread(void *queue_ptr)
{
    con_queue_t *queue = (con_queue_t *) queue_ptr;

    /* Read values from queue. Break loop on -1 */
    while (1) {
        int *popped_value = con_pop(queue);
        if (popped_value) {
            if (*popped_value == -1) {
                free(popped_value);
                break;
            }

            free(popped_value);
        }
    }

    thrd_exit(0);
}

int main()
{
    thrd_t push_threads[N_PUSH_THREADS], pop_threads[N_POP_THREADS];

    con_queue_t *queue = con_init();

    for (int i = 0; i < N_PUSH_THREADS; ++i) {
        if (thrd_create(&push_threads[i], push_thread, queue) != thrd_success)
            printf("Error creating push thread %i\n", i);
    }

    for (int i = 0; i < N_POP_THREADS; ++i) {
        if (thrd_create(&pop_threads[i], pop_thread, queue) != thrd_success)
            printf("Error creating pop thread %i\n", i);
    }

    for (int i = 0; i < N_PUSH_THREADS; ++i) {
        if (thrd_join(push_threads[i], NULL) != thrd_success)
            continue;
    }

    /* Push kill signals */
    for (int i = 0; i < N_POP_THREADS; ++i) {
        int *kill_signal = malloc(sizeof(int)); /* signal pop threads to exit */
        *kill_signal = -1;
        con_push(queue, kill_signal);
    }

    for (int i = 0; i < N_POP_THREADS; ++i) {
        if (thrd_join(pop_threads[i], NULL) != thrd_success)
            continue;
    }

    con_free(queue);
    return 0;
}

程式碼編譯方式:

$ gcc -Wall -std=c11 -o queue queue.c -lpthread

假設 `malloc` 和 `free` 執行過程不會遇到任何錯誤，請補完程式碼，讓這樣的並行佇列得以正確運作，且不會輸出任何錯誤訊息。

==作答區==

AAA = ?
BBB = ?
CCC = ?

:::success
延伸問題:
1. 解釋上述程式碼運作原理並指出實作缺失
2. 以 [lock-free 程式設計](https://hackmd.io/@sysprog/concurrency-lockfree) 改寫上述程式碼
:::

---

### 測驗 $\epsilon$

考慮以下程式碼藉由 [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 系統呼叫來實作 [memory pool](https://en.wikipedia.org/wiki/Memory_pool):

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

#define PAGE_SIZE 4096 /* FIXME: set at runtime */

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;

static void *get_mmap(long sz)
{
    void *p =
        mmap(0, sz, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
    if (p == MAP_FAILED)
        return NULL;
    return p;
}

/* base-2 integer ceiling */
static unsigned int iceil2(unsigned int x)
{
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return XXX;
}

/* mmap a new memory pool of TOTAL_SZ bytes, then build an internal
 * freelist of SZ-byte cells, with the head at (result)[0].
 * Returns NULL on error.
 */
void **mpool_new_pool(unsigned int sz, unsigned int total_sz)
{
    int o = 0; /* o=offset */
    void *p = get_mmap(sz > total_sz ? sz : total_sz);
    if (!p)
        return NULL;
    int **pool = (int **) p;
    assert(pool);
    assert(sz > sizeof(void *));

    void *last = NULL;
    int lim = (total_sz / sz);
    for (int i = 0; i < lim; i++) {
        if (last)
            assert(last == pool[o]);
        o = (i * sz) / sizeof(void *);
        pool[o] = (int *) &pool[o + (sz / sizeof(void *))];
        last = pool[o];
    }
    pool[o] = NULL;
    return p;
}

/* Add a new pool, resizing the pool array if necessary. */
static int add_pool(mpool *mp, void *p, int sz)
{
    assert(p);
    assert(sz > 0);
    if (mp->cnt == mp->pal) {
        mp->pal *= 2; /* RAM will exhaust before overflow */
        void **nps = realloc(mp->ps, mp->pal * sizeof(void **));
        void *nsizes = realloc(mp->sizes, mp->pal * sizeof(int *));
        if (!nps || !nsizes)
            return -1;
        mp->sizes = nsizes;
        mp->ps = nps;
    }

    mp->ps[mp->cnt] = p;
    mp->sizes[mp->cnt] = sz;
    mp->cnt++;
    return 0;
}

/* 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;
}

/* Free a memory pool set. */
void mpool_free(mpool *mp)
{
    assert(mp);
    for (long i = 0; i < mp->cnt; i++) {
        void *p = mp->ps[i];
        if (!p)
            continue;
        long sz = mp->sizes[i];
        assert(sz > 0);
        if (sz < PAGE_SIZE)
            sz = PAGE_SIZE;
        if (munmap(mp->ps[i], sz) == -1)
            fprintf(stderr, "Failed to unmap %ld bytes at %p\n",
                    sz, mp->ps[i]);
    }
    free(mp->ps);
    free(mp);
}

/* 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);
    if (sz >= mp->max_pool) {
        cur = get_mmap(sz); /* just mmap it */
        if (!cur)
            return NULL;
        return cur;
    }

    long szceil = 0;
    for (i = 0, p = mp->min_pool;; i++, p *= 2) {
        if (p > sz) {
            szceil = p;
            break;
        }
    }
    assert(szceil > 0);

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

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

    mp->hs[i] = *cur; /* set head to next head */
    return cur;
}

/* 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;
    assert(ip);
    mp->hs[i] = ip;
}

對應的測試程式如下:

#define PMAX 11

int main(void)
{
    /* Initialize a new mpool for values 2^4 to 2^PMAX */
    mpool *mp = mpool_init(4, PMAX);

    srandom(getpid() ^ (intptr_t) &main); /* Assume ASLR */

    for (int i = 0; i < 5000000; i++) {
        int sz = random() % 64;
        /* also alloc some larger chunks  */
        if (random() % 100 == 0)
            sz = random() % 10000;
        if (!sz)
            sz = 1; /* avoid zero allocations */
        int *ip = (int *) mpool_alloc(mp, sz);
        *ip = 7;

        /* randomly repool some of them */
        if (random() % 10 == 0) /* repool, known size */
            mpool_repool(mp, ip, sz);
        if (i % 10000 == 0 && i > 0) {
            putchar('.');
            if (i % 700000 == 0)
                putchar('\n');
        }
    }

    mpool_free(mp);
    putchar('\n');
    return 0;
}

該 [memory pool](https://en.wikipedia.org/wiki/Memory_pool) 初始化時，指定 $2^4$ 到 $2^{11}$ 範圍的物件預先配置，大於 $2^{11}$ 的物件配置會藉由 [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 系統呼叫達成。

假設上方程式碼的 `mmap`, `munmap`, `malloc`, `free`, `realloc` 均可正確執行，請補完程式碼，使得進行壓力測試的過程中，不會印出錯誤訊息和觸發 assertion。

==作答區==
XXX = ?
YYY = ?

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 提出效能和功能的改進策略，並予以實作
:::

---

### 測驗 $\zeta$

以下程式碼嘗試透過「[高效 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server)」提到的 [poll](https://man7.org/linux/man-pages/man2/poll.2.html) 系統呼叫和「[以 sendfile 和 splice 系統呼叫達到 Zero-Copy](https://hackmd.io/@sysprog/linux2020-zerocopy)」提到 Linux 特有的 splice 系統呼叫，實作出具體而微的 [Port forwarding](https://en.wikipedia.org/wiki/Port_forwarding)。考慮一個情境：我們對外有一台防火牆，在 DNS 設定方面，我們設定 `ftp.mydomain.com` 及 `www.mydomain.com` 都指向這台防火牆。但我們希望所有 HTTP 連線都重新導向到內部的 `192.168.0.2` 這台機器上，而所有 FTP 連線都交由 `192.168.0.3` 來處理。這時候我們就可以使用 port forwarding 的方式來達成。對應的 NAT (Network Address Translation) 的設定如下:

redirect_port tcp 192.168.0.2:80 80
redirect_port tcp 192.168.0.3:20 20
redirect_port tcp 192.168.0.3:21 21

第 1 行的目的就是將 port 80 的 tcp 連線重新導向到 `192.168.0.2` 的 port 80，而第 2 和第 3 行是將 port 20 及 port 21 的連線交由 `192.168.0.3` 來處理。在 `192.168.0.2` 及 `192.168.0.3` 這二台機器上，我們只要設定它們的 gateway 為防火牆的 IP，例如 `192.168.0.1` 即可。

使用 splice 系統呼叫，我們有機會在網路介面控制器的支援下，達到 Zero-copy 資料傳輸。

原始程式碼可見 `proxy.c`。

假設本地機器系統 port 8081 已有網頁伺服器在等待連線。`proxy` 的測試方式為

$ ./proxy localhost 8081

等程式執行後，在另一個終端機畫面中輸入下列命令:

$ telnet localhost 1922

接著你就可以輸入 HTTP 請求字串，如 `GET /index.html`。

此外，你還可以把 port 1922 轉向到 Google 首頁:
先找出 `www.google.com` 的 IP 地址:

$ nslookup www.google.com

得到以下輸出:

Name:	www.google.com
Address: 216.58.200.36

修改上述命令:

./proxy 216.58.200.36 80

重複上述 `telnet` 命令，這時候就會看到 Google 首頁的字串。

以下是 `proxy.c` 程式碼列表:

#define _GNU_SOURCE
#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/poll.h>
#include <sys/socket.h>
#include <unistd.h>

static int connect_to(char *ip, int port)
{
    int sockfd = socket(AF_INET, SOCK_STREAM, 0);
    if (sockfd < 0) {
        printf("Failed to create socket.\n");
        return -1;
    }

    struct sockaddr_in addr;
    memset(&addr, 0, sizeof(addr));

    addr.sin_family = AF_INET;
    addr.sin_port = htons(port);

    if (inet_pton(AF_INET, ip, &addr.sin_addr) <= 0) {
        perror("inet_pton");
        return -1;
    }

    if (connect(sockfd, (struct sockaddr *) &addr, sizeof(addr)) < 0) {
        printf("Failed to connect.\n");
        return -1;
    }

    return sockfd;
}

static void move(int in_fd, int out_fd, int pip[2])
{
    int ret = splice(in_fd, NULL, pip[1], NULL, 8, SPLICE_F_MOVE);
    if (ret == -1) {
        perror("splice(1)");
        return;
    }

    ret = splice(pip[0], NULL, out_fd, NULL, 8, SPLICE_F_MOVE);
    if (ret == -1) {
        perror("splice(1)");
        return;
    }
}

static void proxy(int cl_fd, int target_fd)
{
    if (target_fd == -1)
        return;

    int fds[2];
    if (pipe(fds) == -1) {
        perror("pipe");
        return;
    }

    struct pollfd polls[2] = {
        [1] = {III},
        [0] = {JJJ},
    };

    int ret;
    while ((ret = poll(polls, 2, 1000)) != -1) {
        if (ret == 0)
            continue;

        int from_client = polls[0].revents & POLLIN;
        if (from_client)
            move(cl_fd, target_fd, fds);
        else
            move(target_fd, cl_fd, fds);
    }

    perror("poll");
}

#define PORT 1922

int main(int argc, char *argv[])
{
    if (argc < 3) {
        fprintf(stderr, "Usage: %s <target IP address> <target port>\n",
                argv[0]);
        return -1;
    }

    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in addr;
    memset(&addr, 0, sizeof(addr));

    addr.sin_family = AF_INET;
    addr.sin_addr.s_addr = htonl(INADDR_ANY);
    addr.sin_port = htons(PORT);

    int optval = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEPORT, &optval, sizeof(optval));

    bind(listenfd, (struct sockaddr *) &addr, sizeof(addr));

    listen(listenfd, 1);

    while (1) {
        int connfd = accept(listenfd, (struct sockaddr *) NULL, NULL);
        int target_fd = connect_to(argv[1], atoi(argv[2]));
        if (target_fd >= 0)
            proxy(connfd, target_fd);

        close(connfd);
    }
    return 0; /* should not reach here */
}

請補完程式碼，使其執行符合上述，並且儘量用字元數較少的答覆 (但仍要符合 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format) 排版規範)。

==作答區==
III = ?
JJJ = ?

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 以 [epoll](https://man7.org/linux/man-pages/man7/epoll.7.html) 系統呼叫改寫程式碼，並設計實驗來驗證 proxy 程式碼的效率
:::

---

### 測驗 $\eta$

自上述測驗題 $\alpha$ 到 $\zeta$ 選出至少二項延伸問題，建立 [HackMD](https://hackmd.io/) 頁面、設定權限為「==已登入者可編輯==」(這樣授課教師才能給予眉批)、用固定網址發布筆記 (建議命名為 `linux2021-quiz`)，並依據下方格式來答覆延伸問題:
* 標題: linux2021: **你的 GitHub 帳號名稱**
* 內文: 用 `## ` 開頭並標注題目，如 `## 測驗` $\alpha-1$ 表示「測驗 $\alpha$」的第一個延伸問題

延伸閱讀:
* [HackMD: 筆記權限設定](https://hackmd.io/s/how-to-set-permissions-tw)
* [HackMD: 用固定網址發布筆記](https://hackmd.io/s/how-to-share-note-tw)

---

:::danger
:face_with_cowboy_hat: 感謝您的耐心，瀏覽以上先決測驗題，就算您無緣參加課程，但我相信，練習這些測驗題仍可給您一絲啟發。 -- [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)
:::