# 2020q1 Homework4 (khttpd)
contributed by < `eecheng87` >
###### tags: `linux2020`

## 自我檢查清單
### 解釋 $ sudo insmod khttpd.ko port=1999 這命令是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？
首先透過 `$modinfo khttpd.ko` 可以看到核心模組的資訊裡面包含了參數 `port` 和 `backlog`，還有他們的型態。這是透過呼叫 `module_param` 來達成。如果在 insmod 時有指定 `port` 的值，就會覆蓋掉原本 `main.c` 內的 `static ushort port = DEFAULT_PORT`。

打開 `moduleparam.h` 可以找到 `module_param` 的定義，接著往下找到最深層，發現巨集 `__module_param_call` 就是負責註冊參數的關鍵：

#define __module_param_call(prefix, name, ops, arg, perm, level, flags)	\
	/* Default value instead of permissions? */			\
	static const char __param_str_##name[] = prefix #name;		\
	static struct kernel_param __moduleparam_const __param_##name	\
	__used								\
    __attribute__ ((unused,__section__ ("__param"),aligned(sizeof(void *)))) \
	= { __param_str_##name, THIS_MODULE, ops,			\
	    VERIFY_OCTAL_PERMISSIONS(perm), level, flags, { arg } }

用來紀錄模組參數的資料結構是 `struct kernel_param`，找出這個結構的定義：

struct kernel_param {
	const char *name;
	struct module *mod;
	const struct kernel_param_ops *ops;
	const u16 perm;
	s8 level;
	u8 flags;
	union {
		void *arg;
		const struct kparam_string *str;
		const struct kparam_array *arr;
	};
};

可以發現 `{ __param_str_##name, THIS_MODULE, ops, \
VERIFY_OCTAL_PERMISSIONS(perm), level, flags, { arg } }` 和結構成員剛好對應的上，可見找對東西了。

### 參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？
CS:APP 裡面所提到 client 和 server 如何溝通的流程是很常見的流程，如下:

在 khttpd 也可以找到對應的流程，唯一的差別是所有的呼叫都改成 kernel 版本的呼叫。因為 khttpd 是 sever，所以我們預期找到類似上面 server 的呼叫流程。當 khttpd 被載入核心時，先做 khttp_init，在模組初始化的一開始，會執行自定義的函數 `open_listen_socket`，仔細看這個函數:

static int open_listen_socket(ushort port, ushort backlog, struct socket **res)
{
..
    int err = sock_create(PF_INET, SOCK_STREAM, IPPROTO_TCP, &sock);
..
    err = kernel_bind(sock, (struct sockaddr *) &s, sizeof(s));
..
    err = kernel_listen(sock, backlog);
..
}

可以找到固定流程的前幾個呼叫。接著回到 init，開了一條 thread 專門來做 server_daemon。而這個 daemon 定義在 http_server.c 底下。在 `http_server_daemon` 內很快地就能找到標準流程的下個呼叫 accept ( 注意，`accecpt` 會回傳一個新的 `fd` 給未來的 `send` 和 `recv`，而原本的 `fd` 繼續聽 )，等待 client 的 request。

 while (!kthread_should_stop()) {
        int err = kernel_accept(param->listen_socket, &socket, 0);
..
        worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
..
    }

### htstress.c 用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？
epoll 系統呼叫是類似 `lab0.c` 中有用到的 [select](http://man7.org/linux/man-pages/man2/select.2.html)。都是能夠 non-blocking 的監聽有沒有請求。但是 epoll 有別於 select，沒有監聽數量的限制，而且在找尋是透過紅黑樹搜尋，找尋的複雜度是 $O(logN)$，而後者是 $O(N)$。

#### epoll 變數
簡單說明一下常見的 epoll 相關變數 ( 命名皆參考 man. 範例 )
* `epfd` 或 `epollfd` 可以想成是 epoll 的一個 object，這個 object 上面有 interset list 和 ready list，後者是前者的子集。若資料從不可讀變成可讀，則會出現在 ready list。
* `fd` 在 create socket 時回傳的 file descriptor。有時會命名成 `listen_sock`。
* `events` 或 `ev` 可以想成是用來描述 `fd` 的資料結構。例如: `ev.events = EPOLLIN` 就是描述 `fd` 為可讀的資料。

#### epoll 函數
接著解釋常見的函數
* `epoll_create` 創立一個 epoll object。聽起來很抽象，但可以想成就是把前面 `epfd` 實體化。用 c++ 的概念大概就是: `epfd = new epoll()`。
* `epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)` 是對前面創立的 `epfd` 做操作( 如: 新增監聽成員 )。參數 `epfd` 就是掌管目前 interest list 和 ready list 的資料結構。`op` 可以填入一些巨集，表明想刪除或添加等。`fd` 是想新增/刪減的某 socket 的 fd。而 `event` 則是記錄著 `fd` 更多的資料。
* `int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)` 的功能就是告知使用者目前可以用(讀/寫)的 `fd` 有誰。參數 `epfd` 內含兩條 list，`epoll_wait` 會檢查 ready list 上有誰並告知。參數 `events` 就是前面提到的告知的地方，`epoll_wait` 會把 ready 的 `fd` 存到 `events` 上，所以通常 `events` 是一個陣列。參數 `timeout` 可以設定等待的時間。而回傳值若 >= 0 代表 ready 的個數，反之則沒有。除了以上所說之外，可以參考這篇[文章](https://medium.com/@copyconstruct/the-method-to-epolls-madness-d9d2d6378642)，整理得蠻好的。

#### 解釋 manual 提供的範例程式

/* Code to set up listening socket, 'listen_sock',
              (socket(), bind(), listen()) omitted */

..
for (;;) {
   nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
   if (nfds == -1) {
       perror("epoll_wait");
       exit(EXIT_FAILURE);
   }

   for (n = 0; n < nfds; ++n) {
       if (events[n].data.fd == listen_sock) {
           conn_sock = accept(listen_sock,
                              (struct sockaddr *) &addr, &addrlen);
           if (conn_sock == -1) {
               perror("accept");
               exit(EXIT_FAILURE);
           }
           setnonblocking(conn_sock);
           ev.events = EPOLLIN | EPOLLET;
           ev.data.fd = conn_sock;
           if (epoll_ctl(epollfd, EPOLL_CTL_ADD, conn_sock,
                       &ev) == -1) {
               perror("epoll_ctl: conn_sock");
               exit(EXIT_FAILURE);
           }
       } else {
           do_use_fd(events[n].data.fd);
       }
   }
}

省略的部分是標準的操作，先 `create` 再 `ctl`。真正需要注意的是下面的 for loop，當執行 `wait` 後，`events` 會更新目前有變動的 `fd`，接著遍歷 `events` 來處理改動狀態的 `fd`。接著有兩種情況，第一種情況是: 改動的 `fd` 為目前 server 監聽的 `fd`，這個代表有 client 想要和 server 做連接，所以我們需要透過 `accept` 建立新的連接，同時產生新的 file descriptor 讓兩者溝通 ( 注意: 需要將新產生的 `fd` 透過 `ctl` 加入 epoll 的 interest list )。第二種狀況是: 改動的不是目前監聽的 `fd`，這個代表是上一種狀況新增的 `fd` 有變動，所以代表有 client 的資料已經 ready。

#### htstress.c 運作原理
運作原理簡述就是，把 htstress 當成 client，透過 thread 達成同時有 n 個人向我們指定的 server ( 如: localhost:8081 ) 做請求。直到請求數達到我們要求的總次數，再結束計時。這個時間就可以拿來評估那個 server 的效能 ( 處理 request 的能力 )。

解著解釋幾個重點:

for (int n = 0; n < num_threads - 1; ++n)
    pthread_create(&useless_thread, 0, &worker, 0);

worker(0);

著邊是在 main 裡面，主要是開 thread 來執行 worker。這邊需要注意的是充分利用 thread，第 n 個 thread 我們用在 main thread 來呼叫 worker，這樣我們就可以少 create 一次 thread。(註: 這裡的 epoll 是用在 client 端，和典型在 server 用的不一樣，範例可參考[stackoverflow: How to code an epoll based sockets client in C](https://stackoverflow.com/questions/51777259/how-to-code-an-epoll-based-sockets-client-in-c))

緊接著是計算完成某個 request 數量後花了多少時間。

double delta =
    tve.tv_sec - tv.tv_sec + ((double) (tve.tv_usec - tv.tv_usec)) / 1e6;

再來看看 `worker` 在幹嘛。首先進入 worker 時，我們需要做一個 client 向 server 請求連線的動作 ( 如前面所說，我們需要製造出有一堆人想對 server 做連線的情境 )，而這個動作是透過 `init_conn` 來完成，裡面包含 `connect` ( 試圖讓 server 的 listen 聽到 )，若 server 真的 `accept` 了，那我們就要把剛剛透過 `socket` 拿到的 `fd` 加入 epoll 裡面 (`epoll_ctl`)，方便未來偵測 `fd` 的狀態改變。

再來回到 worker，因為目前 epoll 上的 interset list 已經維護好了，我們接著要做的事只有 `wait`，等待 `fd` 的狀態改變 ( 如: server 想傳東西過來 )。所以接著我們就透過:

if (evts[n].events & EPOLLOUT) {
    ret = send(ec->fd, outbuf + ec->offs, outbufsize - ec->offs, 0);
..

} else if (evts[n].events & EPOLLIN) {
    for (;;) {
        ret = recv(ec->fd, inbuf, sizeof(inbuf), 0);
..
    }

來判斷 server 想幹嘛。以上就算是完成一次 request，接著改變我們的全域變數，`good_request` 等等。

if (!ret) {
    close(ec->fd);
    int m = atomic_fetch_add(&num_requests, 1);
    if (max_requests && (m + 1 > (int) max_requests))
        atomic_fetch_sub(&num_requests, 1);
..
    init_conn(efd, ec);
}

最後要注意的是，雖然完成一次 request 但是這個 thread 還需要繼續做事，所以要再呼叫 `init_conn` 來製造想和 server 連線的情境。而每個 thread 不停重複，直到 request 總數達到要求。

## 把 fib 引入 khttpd
因為作業要求有指出這次的 fib 運算需要考慮大數，所以找出作業二使用的 [bignum](https://github.com/eecheng87/fibdrv/blob/master/bigOper.c) 函式庫沿用。雖然這次要把 bignum 移到 kernel，但是好在 `linux/string.h` 底下幾乎都有足夠的函式來替代原本 user-level 的函式，所以我們就不用重寫了。

而作業描述希望達到 parser 可以解析 `/fib` 和接下來的引數，並給予答案作為回應。首先，在 http_server.c 底下找到相關線索 `http_server_response`，看起來這個檔案就是專門處理 request 和 response。所以我們在這裡面添加 `fib` 運算。函式的原形訂成：`static char *fib(unsigned long long k)`，之所以要回傳字串型態是因為預估未來將會以字元的樣子顯示在網頁上。以下提供 `fib` ，省略 fast doubling 運算:

static char *fib(unsigned long long k)
{
    char *newstr, *p;
    int index = 0;
    bignum a, b;
    int i = 31 - __builtin_clz(k);
    bignum big_two;
    int_to_bignum(0, &a);
    int_to_bignum(1, &b);
    int_to_bignum(2, &big_two);
    for (; i >= 0; i--) {
    /* fast doubling */
        ...
    }
    newstr = kmalloc(a.lastdigit + 1, GFP_KERNEL);
    if (!newstr)
        return NULL;
    p = newstr;
    /* copy the string. */
    while (index < a.lastdigit) {
        *p++ = a.digits[index];
        index++;
    }
    *p = '\0';
    return newstr;
}

這裡唯一需要注意的是字串尾端要記得補`\0`。

接著來找哪個函數是處理 url 的，可以發現 `request->request_url` 或許就是我們要找的。透過 `pr_info` 來檢查發現沒錯，原始的版本會印出 `\`。接著我們要來寫一個函數 `parse_url` 來判斷是否為 '/fib'。將函數的原形訂成 `char *parse_url(char *url, int keep_alive)` 預期能回傳一個字串，這個字串又固定格式，必須包含 `Content-Type: text/plain` 等等的訊息 ( 不確定這個是否是 protocol 規定要這樣傳，才能顯示在 localhost 的頁面上。在 CS:APP 的 network programing 第 43 頁有說明這種格式 )。而 `url` 就是準備傳入前面所提到的 `request->request_url`，而 `keep_alive` 是用來決定前面所提到的固定格式的字串內 `Connection` 的值。

首先將剛剛所説的**特定格式**做修改，改成能夠傳送我們想要傳的訊息( e.g. fib 的結果 )。將原本的

#define HTTP_RESPONSE_200_DUMMY                               \
    ""                                                        \
    "HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF     \
    "Content-Type: text/plain" CRLF "Content-Length: 12" CRLF \
    "Connection: Close" CRLF CRLF "Hello World!" CRLF

改成

#define HTTP_RESPONSE_200_DUMMY                               \
    ""                                                        \
    "HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF     \
    "Content-Type: text/plain" CRLF "Content-Length: %d" CRLF \
    "Connection: Close" CRLF CRLF "%s" CRLF

把想要傳的文字改成 `%s`，稍後可以透過類似 sprintf 寫到一個新的 `char *`。另外長度目前也是未知，所以要改成 `%d` 同樣等等處理。

再來以下是 `parse_url` 的實做：

static char *parse_url(char *url, int keep_alive)
{
    size_t size;
    char const *del = "/";
    char *token, *tmp = url, *fib_res = NULL, *res;
    char *msg = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY
                           : HTTP_RESPONSE_200_DUMMY;
    tmp++;
    token = strsep(&tmp, del);
    if (strcmp(token, "fib") == 0) {
        /* expected tmp is number now */
        long k;
        kstrtol(tmp, 10, &k);
        fib_res = fib((unsigned long long) k);
    }
    if (!fib_res)
        return NULL;
    size = strlen(msg) + strlen(fib_res) *　2 - 4;
    res = kmalloc(size, GFP_KERNEL);
    snprintf(res, size, msg, strlen(fib_res), fib_res);

    return res;
}

這段邏輯很簡單，只是判斷兩個 `/` 間是否為 fib，如果是就要在擷取下一段，預期拿到數字，透過核心提供的 `kstrol` 類似 `atoi` 的功能，然後傳入剛剛移植到核心的 `fib`，得到字串 `fib_res`。再來我們要回傳一段字串，作為 `http_server_send` 的回應訊息。前面有提到這段文字需要照著特定格式，所以使用較安全的 [snprinf](http://www.cplusplus.com/reference/cstdio/snprintf/)。而這個字串的長度要事先算好，要先減去 `%d` 和 `%s` 共 4 個字，然後加上 fib 結果 `fib_res` 的長度，和數字的長度。

接著對 `http_server_response` 稍做修改，主要是拿回剛剛處理過後的特定格式字串：

else
    response = parse_url(request->request_url, keep_alive);
if (response)
    http_server_send(request->socket, response, strlen(response));

## 驗證 fib 正確性腳本
我從 [Facebook 討論串](https://www.facebook.com/groups/system.software2020/permalink/345124729755066/)找了[黃鈺盛](https://gist.github.com/wilson6405/c8b86f71ce680efee26850298c9c237c?fbclid=IwAR0MOyjBYvAgFEtpdyeYQgGXIo4i3kpezI8trpJzpSVtF7X7MErdJT8_g8o)同學的 python 驗證程式，並稍做修改。黃同學主要是透過 python 爬取線上提供的答案來和執行檔做比對，我這邊改後半部，改成到 `localhost:port` 爬取文字，而這串文字即 fib 的結果，再拿來和答案比對。爬取 localhost 的文字如下：

link = "http://localhost:"+args.port+"/fib/"+args.index
RESULT = requests.get(link).text

然後 makefile 只要簡單加一句，就能執行：

verify:
	@python3 scripts/verify.py -p $(PORT) -i $(INDEX)

## 引入 Concurrency Managed Workqueue
### cmwq 內部架構

若有 n 個 cpu，則建立 2n 個專屬某 cpu 的 thread pool。另外還有公共用的 unbounded thread pool。
### cmwq 改善了什麼
* 避免使用者建立過多執行緒，拖慢效能。 cmwq 提供 thread pool 讓使用者不用在管理 thread (如: 一直 create)。
* 解決 asynchronous 問題，尤其是在單執行緒上。若原本的單執行緒一定是一個接著一個做，儘管前面 block，後面的人仍要等。但是 cmwq 有類似 thread pool 的概念，當有 thread 被 block 時會偵測到，並會建立新的 work thread 來做後面的任務。
* 增加 unbound 特性，原本的 work queue 上的任務，無法在不同 cpu 上遊走，儘管目前的 cpu 在 blocking 中。但是 cmwq 有提供一個 unbounded thread pool 給有需求的人用。
* 讓不同任務更有彈性的被執行，增加 flag 讓使用者描述該任務特性。如：高優先權。前面有提到每個 cpu 會有 2 個 thread pool，分別就是給高優先權和低優先權的 pool。

### 修改原本 server
其實 cmwq 只有一個新的 api : `alloc_workqueue`，其他和原本的 workqueue 作法都差不多，而且步驟很少就能完成，前面提到的複雜議題都已經被包在裡面做了，使用者可以很方便的使用。

* 首先需要創造一個專屬的 working queue，型態為 `struct workqueue_struct`。
* 呼叫範例: wq = alloc_workqueue("queue name", flag, maxsize)
* flag 有各種，可在[文件]()查詢。舉例: `WQ_UNBOUND` 表示 thread 不一定被限制在某個 cpu 上。
* 第二個步驟，讓型態 `work_struct` (等等要放到 queue 上的變數)的變數和 `work` (使用者自訂的函數)綁在一起。
* 呼叫範例: INIT_WORK(&ws, function)
* 最後，把 `work_struct` 型態的變數放到 working queue 裡
* 呼叫範例: queue_work(wq, &ws) 　

致敬 [kecho](https://github.com/sysprog21/kecho) 實做流程後 ( 完整修改參考分支 [cmwq](https://github.com/eecheng87/khttpd/tree/cmwq) ) ，得到明顯的效能提昇

requests:      100000
good requests: 100000 [100%]
bad requests:  0 [0%]
socker errors: 0 [0%]
seconds:       3.162
requests/sec:  31623.183

註: 在做 socket programing 的 driver 建議在虛擬機測試，確認功能完成後再回到實機上評估效能。因為 socket programing 很容易沒寫好就當機，或者是整個模組毀損導致無法 rmmod，得重複開機才能修好，很浪費時間。

:::warning
TODO:
1. `htstress` 實際只測試靜態內容，不足以反映出 Fibonacci 數求值運算和透過 TCP 傳回給客戶端，請設計新的實驗，允許來自客戶端同時數個連線，實際要求 `/fib/?` 並由 kHTTPd 予以回應，例如同時 10 個連線要求計算 $Fib(x)$，其中 x 介於 1 到 300。這個實驗更能看出 CMWQ 的效益;
2. 考慮到特定的 $Fib(x)$ 運算需要較長時間，如何在 HTTP 1.1 Keep-Alive 的設定下，確保客戶端能夠等待到 kHTTPd 傳回正確數值？
3. 倘若客戶端連線已失效或 timeout，kHTTPd 能否得知？又，能否自行移除已經無效的 `fib` 運算？
4. 假設我們可預先配置記憶體空間，能否將 $Fib(x)$ 運算結果快取 (cache) 呢？cache replacement policy 又該如何設計才有效益？(如 LRU)

:notes: jserv
:::

## Reference
[module_param](https://danielmaker.github.io/blog/linux/kernel_parameter_parsing.html)