# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 11 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 Linux 記憶體管理、POSIX shared memory, POSIX semaphore 和 split/epoll 系統呼叫的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSe_Ka_m1O9oj0KjULO3VpXBDnsU2c4eliFJxtJQ_HF58X7tiA/viewform)==

---

### 測驗 `1`

考慮一個使用 POSIX shared memory 和 semaphore 開發的 [key-value store](https://en.wikipedia.org/wiki/Key-value_database) 實作，測試程式碼:

static void sig_handler(int dummy) {
    kv_delete_db();
    exit(0);
}

int main()
{
    signal(SIGINT, sig_handler);
    signal(SIGQUIT, sig_handler);
    signal(SIGTSTP, sig_handler);

    // Check create
    kv_store_create("/STORE");

    // Check write
    kv_store_write("MyKey", "content [A]");
    kv_store_write("MyKey", "content [B]");

    for (size_t k = 0; k < 17; k++) {
        char str[5];
        sprintf(str, "[%zu]", k);
        kv_store_write("MyKey", str);
    }

    for (int i = 0;; i++) {
        char *p = kv_store_read("MyKey");
        if (!p) break;
        free(p);
    }

    // Check read_all
    char **v = kv_store_read_all("MyKey");
    for (size_t i = 0; v[i]; i++) {
        printf("%zu => '%s'\n", i, v[i]);
        free(v[i]);
    }

    free(v);

    // Check destroy
    kv_store_destroy("/STORE");

    return 0;
}

參考執行輸出:

0 => 'content [A]'
1 => 'content [B]'
2 => '[0]'
3 => '[1]'
4 => '[2]'
5 => '[3]'
6 => '[4]'
7 => '[5]'
8 => '[6]'
9 => '[7]'
10 => '[8]'
11 => '[9]'
12 => '[10]'
13 => '[11]'
14 => '[12]'
15 => '[13]'
16 => '[14]'
17 => '[15]'
18 => '[16]'

原始程式碼可見 [kv.c](https://gist.github.com/jserv/9db8ca1fe174a99eaccbfaebbf47b2bb)。

這份實作應該能在 multi-process 和 multi-thread 環境運作。

請補完上述 `kv.c` 程式碼。

==作答區==

AAA = ?
* `(a)` `open`
* `(b)` `shm_open`

BBB = ?
* `(a)` `store->clients`
* `(b)` `store->clients++`
* `(c)` `++store->clients`
* `(d)` `store->clients--`
* `(e)` `--store->clients`

CCC = ?
* `(a)` 0
* `(b)` `cache_idx`
* `(c)` `cache_idx++`
* `(d)` `cache_idx--`

DDD = ?
* `(a)` 0
* `(b)` `cache_idx`
* `(c)` `cache_idx++`
* `(d)` `cache_idx--`

:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出實作缺陷並改進
2. 設計實驗並探討改進存取效率的手法
:::

---

### 測驗 `2`

以下程式碼嘗試透過 epoll 和 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

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

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

原始程式碼可見 [proxy.c](https://gist.github.com/jserv/99ad84d0b9ef8a5836cf93fc42b4f435)，其 `list.h` 取自 [list.h](https://github.com/sysprog21/linux-list/blob/master/include/list.h)，改寫自 Linux 核心原始程式碼。

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

$ ./proxy 8082 localhost 80

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

$ telnet localhost 8082

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

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

$ nslookup www.google.com

得到以下輸出:

Name:	www.google.com
Address: 216.58.200.228

修改上述命令:

./proxy 8082 216.58.200.228 80

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

請補完程式碼。

==作答區==

EEE = ?
* `(a)` `num_events`
* `(b)` `num_events++`
* `(c)` `num_events--`
* `(d)` `++num_events`
* `(e)` `--num_events`

FFF = ?
* `(a)` 不需要加入程式碼
* `(b)` `buf->bytes += n`
* `(c)` `buf->bytes -= n`
* `(d)` `buf->bytes--`
* `(e)` `buf->bytes++`

:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出實作缺陷並改進
2. 將 DNS 解析的機制納入，允許用 [FQDN](https://en.wikipedia.org/wiki/Fully_qualified_domain_name) 作為輸入
3. 嘗試克服連線數量的限制，設計實驗並探討如此 port forwarding 的效率
:::