# 2020q1 Homework4 (khttpd)
contributed by < `AndybnACT` >
###### tags: `linux2020`
## `khttpd` 的實作問題與解決方法
編譯及載入 `khttpd` 完成後，可透過開啟網址 `http://localhost:8081/`，和 `dmesg` 檢查 `khttpd` 的運作，搭配閱讀原始程式碼，發現 `khttpd` 的實作存在若干嚴重問題。
### `http_server_worker` 沒有被正確地釋放
首先，若是使用網頁瀏覽器開啟網頁，在卸載（`rmmod`）之後，接下來的操作（如：重新整理、關閉瀏覽器等…）都會導致 kernel page fault：
```
[16029.728411] khttpd: module unloaded
[16052.062048] BUG: unable to handle kernel paging request at ffffffffc0ebfb94
[16052.062055] IP: 0xffffffffc0ebfb94
[16052.062057] PGD 4520e067 P4D 4520e067 PUD 45210067 PMD 24e4ee067 PTE 0
[16052.062062] Oops: 0010 [#1] SMP PTI
[16052.062102] snd_soc_core thunderbolt nvme_core snd_compress snd_pcm_dmaengine ac97_bus idma64 snd_hda_intel ecdh_generic snd_hda_codec rfkill nvmem_core sbs acpi_als sbshc snd_hda_core kfifo_buf industrialio snd_hwdep snd_seq snd_seq_device snd_pcm mei_me snd_timer snd mei apple_bl soundcore shpchp i915 spi_pxa2xx_platform i2c_algo_bit drm_kms_helper uas crc32c_intel drm usb_storage intel_lpss_pci intel_lpss applespi(OE) video [last unloaded: khttpd]
[16052.062125] CPU: 0 PID: 29508 Comm: khttpd Tainted: G OE 4.16.6-202.fc27.x86_64 #1
[16052.062127] Hardware name: Apple Inc. MacBookPro14,1/Mac-B4831CEBD52A0C4C, BIOS 204.0.0.0.0 12/16/2019
[16052.062129] RIP: 0010:0xffffffffc0ebfb94
[16052.062131] RSP: 0018:ffffa73e850c3d80 EFLAGS: 00010282
...
[16052.062146] Call Trace:
[16052.062160] ? kthread+0x113/0x130
[16052.062163] ? kthread_create_worker_on_cpu+0x70/0x70
[16052.062165] ? do_syscall_64+0x74/0x180
[16052.062167] ? SyS_exit+0x13/0x20
[16052.062170] ? ret_from_fork+0x35/0x40
[16052.062172] Code: Bad RIP value.
[16052.062180] RIP: 0xffffffffc0ebfb94 RSP: ffffa73e850c3d80
[16052.062181] CR2: ffffffffc0ebfb94
[16052.062183] ---[ end trace 53ee86b85fdc21e6 ]---
```
仔細一看關於 page fault 的描述是 `Bad RIP value` 、又發生在卸載之後的 `kthread` 裡面，推測是卸載時沒有將對應的 `kthread` 一併釋放。這點可以由 `ps` 看出：
```shell
$ sudo insmod khttpd.ko
$ ps -ef | grep khttpd
andy 2411 2409 1 10:30 pts/0 00:03:35 /usr/share/atom/atom --executed-from=/home/andy/khttpd --pid=2392 .
root 32462 2 0 15:16 ? 00:00:00 [khttpd]
andy 32471 29511 0 15:16 pts/1 00:00:00 grep --color=auto khttpd
### open web browser, load url: localhost:8081
$ ps -ef | grep khttpd
root 32462 2 0 15:16 ? 00:00:00 [khttpd]
root 32529 2 0 15:18 ? 00:00:00 [khttpd]
$ sudo rmmod khttpd
$ ps -ef | grep khttpd
-pid=2392 .
root 32529 2 0 15:18 ? 00:00:00 [khttpd]
```
檢查程式碼發現，在 `http_server_daemon()` 裡面透過 `kthread_run()` 產生新的 `kthread` 之後，沒有任何等待、檢查執行結果、或是回收的機制。一般來說，產生新的行程後，父行程應該要註冊 `SIGCHLD` handler、或在某處透過 `waitpid` 來回收新產生出來的行程。
值得注意的地方是，和 POSIX `fork()` 不同之處在新產生的核心行程，其 `ppid` 都不是 `http_server_daemon()` 的 `pid (32462)`，而是 `kthreadd (2)`。這可能也部分解釋為什麼 `http_server_daemon()` 不需要作這些處理。
- [ ] `kthread` 的回收機制。
再看看被產生出來的 `kthread`，也就是 `http_server_worker()` 的行為。可以看出只要 `HTTP` 連線屬於 Keep-Alive（瀏覽器通常會開啟此一選項）、沒有被通知（`kthread_should_stop()`）應該要結束、或者 socket 沒有被中斷，這個 `kthread` 都會不斷地等待、處理 socket 的資料。
```cpp
while (!kthread_should_stop()) {
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
if (ret)
pr_err("recv error: %d\n", ret);
break;
}
http_parser_execute(&parser, &setting, buf, ret);
if (request.complete && !http_should_keep_alive(&parser))
break;
}
```
這也是爲什麼我們在卸載模組之後、`ps` 還看得到他正在執行，因為他還在等待遠端連線送過來的訊息。然後當我們的瀏覽器重新整理，將 HTTP header 送進來之後返回模組程式碼，導致 Bad RIP value，因為程式碼片段早已卸載。
:::warning
TODO: 搭配 [kecho](https://hackmd.io/@sysprog/linux2020-kecho) 提供的 `drop-tcp-socket` 核心模組進行實驗，阻擋特定的 TCP 連線
:notes: jserv
:::
#### 解決方法
因為每當有一個新的連線，就會產生一個 `kthread` 處理、再加上我們無法預測 `http_server_worker()` 的結束時機和情形。因此我們需要在 daemon 和 worker 之間共用一個 list，才能夠在最後需要釋放模組的時候，正確地將所有還沒被釋放的 worker 結束。整個 list 由 daemon 負責加入 worker 資料、然後 worker 結束之際，由 woker 釋放自己在 list 中的資料。
```cpp
struct worker {
struct task_struct *tsk;
struct socket *socket;
struct list_head list;
};
struct httpd_worker {
struct semaphore sem;
struct worker workers;
} daemon_stat;
```
- `semaphore`：因為資源共享於 daemon 與 worker 之間、list 的操作亦非 atomic，所以需要一個鎖來幫忙保護資料（目前沒有想到 lock-free 的實作方法）。同時，我們會在握有鎖的情形下呼叫過程中可能配置記憶體的函數 `kthread_run()`（由 `kthread_create_on_node()` 可能回傳 `ENOMEM` 判斷），所以這邊沒辦法使用 spinlock（`kmalloc` may sleep）。使用 semaphore 而非 mutex 的原因是 daemon 和 worker 會共用一段操作 list 的 critical section。因此 daemon 獲取 semaphore 之後，待 worker 操作完，再由 worker 釋放 semaphore。
- <s>使用 semaphore 會比較合適的原因是這樣一來我們可以在 daemon <s>上鎖</s>，等到 worker 開始執行，把資料填其全之後，再由 worker 解鎖。</s>
:::danger
避免不精準的用詞，在 mutex lock (或簡稱 lock) 中，取得 (acquire) 和釋放 (release) 對應口語是「上鎖」和「解鎖」，是因為有 ownership，但在 semaphore 本質上是 counter，你該說 down (`P` 操作) 和 up (`V` 操作)，口語可說「取得」和「釋放」(沒有 ownership 的隱喻)
:notes: jserv
:::
接下來，daemon 在每次新連線進來、工作開始之前，作以下的操作，將資料正確地放入 list 中：
```cpp
while (!kthread_should_stop()) {
int err = kernel_accept(param->listen_socket, &socket, 0);
...
worker = kmalloc(sizeof(struct worker), GFP_KERNEL);
if (!worker) {
pr_err("can't create more worker metadata\n");
return -1;
}
worker->socket = socket;
INIT_LIST_HEAD(&worker->list);
down(&daemon_stat.sem);
list_add(&worker->list, &(daemon_stat.workers.list));
worker_tsk = kthread_run(http_server_worker, worker, KBUILD_MODNAME);
if (IS_ERR(worker_tsk)) {
pr_err("can't create more worker process\n");
up(&daemon_stat.sem);
continue;
}
```
在模組卸載時，daemon 會取得 semaphore ，傳送 `SIGTERM` 給每個還在 list 中的 worker，然後等待 worker 執行結束：
```cpp
head = &(daemon_stat.workers.list);
down(&daemon_stat.sem);
list_for_each_entry_safe (worker, next, head, list) {
pr_debug("freeing still active worker pid = %d\n", worker->tsk->pid);
send_sig(SIGTERM, worker->tsk, 1);
kthread_stop(worker->tsk);
}
up(&daemon_stat.sem);
```
worker 的部分，在開始之後，先從 `arg->socket` 拿到 socket 資料、填上 `worker->tsk` 之後，釋放 semphore：
```cpp
static int http_server_worker(void *arg)
{
struct worker *worker = (struct worker *) arg;
...
socket = worker->socket;
worker->tsk = current;
up(&daemon_stat.sem);
...
```
worker 結束之際，需要將自己移出 list，這時會動到共享的資源，所以需要取得 semaphore 。但是，如果這個 worker 是被 daemon 叫停的話，semaphore 已經是取得的狀態，不需要再獲取一次；這樣的情形可以用 `kthread_should_stop()` 來幫助判斷：
```cpp
should_stop = kthread_should_stop();
while (down_timeout(&daemon_stat.sem, 1)) {
should_stop = kthread_should_stop();
if (likely(should_stop))
break;
}
list_del(&worker->list);
if (!should_stop)
up(&daemon_stat.sem);
...
return 0;
}
```
使用 `down_timeout()` 的原因是我們可以在獲取失敗後，讓出一段時間，再回來檢查狀態。
完成之後，重新執行 `make check`、重複原先會發生問題的操作，沒有發現錯誤。
### Potential Out-of-Bound Read
檢查程式碼，發現在 worker 裡面，`buf` 的配置方式用 `kmalloc(RECV_BUFFER_SIZE, GFP_KERNEL)` ，用來暫存 socket 送來的資料。雖然是用 `RECV_BUFFER_SIZE - 1` 的大小來存，但 `kmalloc` 不會保證 `buf` 最後一個 byte 是 null terminator。這時，如果送來的 header 剛好大小爲 `RECV_BUFFER_SIZE - 1`、傳到 parser 裡面，如果裡面如果用到 C 語言常見沒有做邊界檢查的函式時，就「可能」發生越界讀取。
解決的方式是補上 `buf[RECV_BUFFER_SIZE - 1] = '\0';`
### Potential Out-of-Bound Write
此外，發現在 `http_parser_callback_request_url()` 裡面，`strncat` 沒有確保 `request->request_url` 的長度加上 `len` 不會超過 `request_url` 的長度。這裡如果越界寫入發生在鄰近結構的 function pointer 上，將造成 remote code execution。
```cpp
static int http_parser_callback_request_url(http_parser *parser,
const char *p,
size_t len)
{
struct http_request *request = parser->data;
strncat(request->request_url, p, len);
return 0;
}
```
改用以下方式可以解決問題：
```diff
@@ -3,6 +3,10 @@ static int http_parser_callback_request_
size_t len)
{
struct http_request *request = parser->data;
+ size_t pos;
+ for (pos = 0; pos < 128 && request->request_url[pos]; pos++)
+ ; /* strlen */
+ len = (pos + len >= 128) ? 128 - pos - 1 : len;
strncat(request->request_url, p, len);
return 0;
}
```
## Concurrency Managed Work Queue
根據 [kernel.org](https://www.kernel.org/doc/html/v4.15/core-api/workqueue.html) 對 CMWQ 的描述，它將需要 asynchronous 執行的任務 (`work_struct`)，用 queue 的方式管理 (`workqueue_struct`)。然後以 preallocated thread pools，也就是 `kworker` 當作執行單元，在有任務需要執行的時候，根據 `work_struct` 的描述執行對應的函式。
使用 CMWQ 的好處在於，開發者不需要額外管理產生新任務需要的配置與釋放；而這些預先配置的執行單元 `kworker` 也得益於 preallcation 的好處，降低回應的延遲。此外，CMWQ 也提供便於任務管理的機制，可以指定 queue 的排程特性。
配合閱讀程式碼之後，整理三個主要的 API
- `alloc_workqueue()`：配置一個 workqueue。其中，透過第二個參數 [`flag`](https://elixir.bootlin.com/linux/latest/source/include/linux/workqueue.h#L308) 可以指定排程上的特性。
- `queue_work()`：將任務加入 workqueue 中，交給屬於目前處理器上的 `kworker`。
- `destroy_workqueue()`：等待 workqueue 的工作完成後，將 workqueue 釋放。
引入 CMWQ 的過程大致如下：
首先，將 `struct worker` 的內容改掉。因為 Linux 會自行管理 CMWQ 內的 `kworker`。所以這邊不再需要用串列紀錄他們的狀態。取而代之的是描述任務用的 `work_struct`。
```diff
struct worker {
- struct task_struct *tsk;
struct socket *socket;
+ struct work_struct work;
- struct list_head list;
};
- struct httpd_worker {
- struct semaphore sem;
- struct worker workers;
- } daemon_stat;
```
然後需要用一個指標指向 workqueue，我們將其放在 `http_server.h` 裡面。
```diff
struct http_server_param {
struct socket *listen_socket;
};
+ extern struct workqueue_struct *wq_regular;
```
配置 workqueue 在 module 初始化區段內進行、而釋放 workqueue 則是在卸載 module 時呼叫。使用 `WQ_UNBOUND` 的原因是讓 `khttpd` 在應付大量請求的時候由系統調度可用的處理器資源，而不會限制在本地的處理器上。
```cpp
static int __init khttpd_init(void)
{
int err = open_listen_socket(port, backlog, &listen_socket);
if (err < 0) {
pr_err("can't open listen socket\n");
return err;
}
wq_regular = alloc_workqueue("khttp-wq", WQ_UNBOUND | WQ_SYSFS, 0);
if (!wq_regular) {
pr_err("cannot allocate wq_regular\n");
goto out_free_sock;
}
...
out_free_reg:
destroy_workqueue(wq_regular);
out_free_sock:
close_listen_socket(listen_socket);
return -ENOMEM;
}
```
在跳出事件迴圈之後，也就是當我們需要退出 daemon 時，只需要呼叫 `destroy_workqueue()` 就能夠等待所有 workqueue 工作執行結束，然後結束 daemon 這個 `kthread`。
在 daemon 之中，原本用 `kthread_run` 來產生的執行單元，現在改由 `INIT_WORK()` 先透過 function pointer 指派任務內容、再由 `queue_work()` 的方式分配工作。
```cpp
while (!kthread_should_stop()) { /* Event Loop */
...
/* queue work */
INIT_WORK(&worker->work, khttp_wq_worker);
worker->socket = socket;
if (!queue_work(param->wq, &worker->work))
pr_err("ERROR, cannot queue (worker is not freeed!!)\n");
}
```
任務內容，也就是 function pointer 的部分，其實就是一個 wrapper function，從 `struct work` 拿到要傳遞給 `http_server_worker` 之後，然後呼叫。
```cpp
void khttp_wq_worker(struct work_struct *w)
{
struct worker *arg = container_of(w, struct worker, work);
http_server_worker(arg);
return;
}
```
在 worker 裡面，我們也不在需要自己維護一個 list，要離開時直接 return 即可。
```diff
...
- should_stop = kthread_should_stop();
- while (down_timeout(&daemon_stat.sem, 1)) {
- should_stop = kthread_should_stop();
- if (likely(should_stop))
- break;
- }
- list_del(&worker->list);
- if (!should_stop)
- up(&daemon_stat.sem);
kfree(worker);
return 0;
}
```
簡單的效能測試發現有改善，以下為 `make check` 十次平均：
| Item | `kthread` (first import) | `kthread` (semaphore) | CMWQ | CPU |
| ------------- | -------- |-| -------- | ------- | ---- |
| requests/sec | 24177.805 (baseline)| 18308.407 (-24.28%)| 58204.986 (+40.74%)| `i5-6400`, `CONFIG_PREEMPT(4.16.1)` |
| requests/sec | <s>48895.7173 (baseline)</s>|<s> 42813.029 (-12.44%)</s>| 52231.4911 (+6.82%)| `i5-6400` (isolcpus=1) `CONFIG_PREEMPT(4.16.1)`|
| requests/sec | 18546.200 (baseline)| 14513.8887 (-21.10%)| 29206.1609 (+58.76%)| `i5-2500` `CONFIG_PREEMPT_VOLUNTARY(5.5.7)` |
:::danger
TODO: 解釋這兩款 microarchitecture 對 kHTTPd 效能的影響
:notes: jserv
:::
## `insmod` 的參數傳遞
## 與 `fibdrv` 的整合
首先，為了把 [`ABN`](https://hackmd.io/V0uA_6CSSdqBEUqrFFeOhg#%E5%B0%8D%E6%9B%B4%E5%A4%A7%E6%95%B8%E7%9A%84%E6%94%AF%E6%8F%B4%EF%BC%88Arbitrary-Big-Number%EF%BC%89) 整合進 kernel 我們在檔頭檔尾重新作以下定義
```cpp
#define KERNEL_MODE
#ifndef KERNEL_MODE
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "debug.h"
#endif /* !KERNEL_MODE */
#ifdef KERNEL_MODE
#include <linux/types.h>
#include <linux/slab.h>
#define malloc(size) kmalloc((size), GFP_KERNEL)
#define free(ptr) kfree(ptr)
#define CONFIG_DEBUG_LEVEL 2
#define dprintf(lvl, fmt, args...) \
do { \
if (CONFIG_DEBUG_LEVEL && (lvl) <= CONFIG_DEBUG_LEVEL) \
printk((fmt), ##args); \
} while(0)
#define printf(fmt, args...) { \
printk(fmt, ##args); \
}
#endif /* KERNEL_MODE */
.... Original Content of abn.h ....
#ifdef KERNEL_MODE
#undef malloc
#undef free
#undef printf
#endif /* KERNEL_MODE */
```
若無意外，這樣就可以移植進入 kernel 當中了。接著，在我們將 `abn.h` 加入到 `http_server.c` 後，修改 `http_server_response()` 判斷 `url == "/fib/*"` 時，讀出後面的數字 `k`，代入 `abn_calculate_fib()` 之後計算費波那契數，然後回傳 hex-based 的結果字串。
```cpp
static int http_server_response(struct http_request *request, int keep_alive)
{
char *response;
char *res_buf;
char *res;
int rc;
unsigned long clen;
unsigned long k = 0;
unsigned long size = 0;
pr_info("requested_url = %s\n", request->request_url);
if (request->method != HTTP_GET)
response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
else
response = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY
: HTTP_RESPONSE_200_DUMMY;
size += strlen(response);
if (strncmp(request->request_url, "/fib/", 5) == 0 &&
request->request_url[5] != '-') {
rc = kstrtol(request->request_url + 5, 10, &k);
if (rc) {
pr_err("cannot convert number in url\n");
k = 0;
}
res = abn_calculate_fib(k);
if (!res) {
pr_err("cannot allocate space for result buffer\n");
goto err;
}
} else {
res = kmalloc(12, GFP_KERNEL);
if (!res) {
pr_err("cannot allocate space for result buffer\n");
goto err;
}
memcpy(res, "Hello-World", 12);
}
clen = strlen(res) + 1; // Content-length
size += clen;
size += count_digit(clen); // length of Content-length
res_buf = (char *) kmalloc(size, GFP_KERNEL);
if (!res_buf) {
pr_err("cannot allocate space for response bufer");
goto err_free_res;
}
snprintf(res_buf, size, response, clen, res);
http_server_send(request->socket, res_buf, size);
pr_info("sending %s\n", res_buf);
kfree(res_buf);
err_free_res:
kfree(res);
err:
return 0;
}
```
`abn_calculate_fib()` 在輸出字串時，沿用 `bn_print()` 的實作方式，只是 `printf()` 改成 `snprintf()` 。而 `bn_fib_doubling()` 則和 `ABN` 用來測試費波那契數的函式相同：
```cpp
static char *abn_calculate_fib(unsigned long k)
{
char *res;
uint64_t *num;
unsigned long digit = 10;
bn a;
pr_info("k = %ld\n", k);
bn_init(&a);
a = bn_fib_doubling(k);
digit = a.cnt * 16 + 2 + 1; // 2 for "0x"
// bn_print(&a);
num = bn_getnum(&a);
res = (char *) kmalloc(digit + 1, GFP_KERNEL);
if (!res)
return NULL;
snprintf(res, 19, "0x%016llx", num[a.cnt - 1]);
for (int i = a.cnt - 2, j = 18; i >= 0; i--, j += 16)
snprintf(res + j, 17, "%016llx", num[i]);
bn_free(&a);
return res;
}
```
:::warning
需要考慮到如果 Fibonacci 數求值過程太長，對整體系統的回應時間是否有衝擊。查閱 Linux 核心文件關於 "Voluntary Kernel Preemption" 的描述。
參考資訊: [Understanding Linux Kernel Preemption](https://devarea.com/understanding-linux-kernel-preemption/)
:notes: jserv
:::
### `schdule()`
有一次想測試負數會不會導致讀取錯誤，網址欄寫下 `localhost:8081/-10` 然後電腦就卡住了。可見在處理大量運算時，需要一些改進
為了讓 `khttpd` 在處理大量計算時，還能應付其他的連線請求，我們嘗試在 CMWQ 的幫忙下，再新增一組 `WQ_UNBOUND` workqueue，`wq_intensive`，專門用來處理大量連線。
```cpp
extern struct workqueue_struct *wq_intensive;
```
原本嘗試用 `apply_workqueue_attrs()` 設定 qorkqueue 的 nice 值，但是編譯 module 的時候 link 失敗。檢查程式碼發現 kernel 沒有對該函式做 `EXPORT_SYMBOL_GPL()`。折衷的方法是可以透過 `sysfs` 設定，目錄位於 `/sys/device/virtual/workqueue/`
配置完成之後，我們在 server worker 解析完將帶入費氏數列的 `k` 值之後，判定若 `k > THRESHOLD` 就把計算工作放到 `wq_intensive` 裡面，然後透過一個 semaphore 等待工作執行的結果。
```cpp
#define FIB_KTHRESHOLD 5000000
...
struct fib_worker {
struct semaphore sem;
unsigned long k;
bn result;
struct work_struct work;
};
void khttp_wq_fibworker(struct work_struct *w)
{
struct fib_worker *arg = container_of(w, struct fib_worker, work);
arg->result = bn_fib_doubling(arg->k);
up(&arg->sem);
return;
}
static char *abn_calculate_fib(unsigned long k)
{
char *res;
unsigned long long *num;
unsigned long digit = 10;
bn a;
pr_info("k = %ld\n", k);
bn_init(&a);
if (k >= FIB_KTHRESHOLD) {
struct fib_worker work;
sema_init(&work.sem, 0);
INIT_WORK(&work.work, khttp_wq_fibworker);
work.k = k;
queue_work(wq_intensive, &work.work);
down(&work.sem);
a = work.result;
} else {
a = bn_fib_doubling(k);
}
```
同時，在計算費氏數列的函式裡面，安插了數個 `might_resched()` 提示 kernel 此時可以做任務切換。需要注意的是這個 macro 只有在 [`CONFIG_PREEMPT_VOLUNTARY`](https://www.linuxtopia.org/online_books/linux_kernel/kernel_configuration/re152.html) 是有用的。在 `CONFIG_PREEMPT` 的情形下，只要 kernel 當前未持有 spinlock、或者是沒有另外關閉 preemption，都可以被其他 process 搶佔。
```cpp
for (int i = (64 - clz), cnt = 0; i > 0; i--, cnt++) {
if (!(cnt % 4) || cnt >= 17)
resched = true;
else
resched = false;
SAFE_OP(bn_assign(&bb, &b));
SAFE_OP(__bn_shld(&bb, 1));
bn_sub(&tmp, &bb, &a);
if (resched)
rc += might_resched();
SAFE_OP(bn_mul_comba(&t1, &a, &tmp));
if (resched)
rc += might_resched();
SAFE_OP(bn_mul_comba(&asquare, &a, &a)); // comba square is ready on my mac
if (resched)
rc += might_resched();
SAFE_OP(bn_mul_comba(&bsquare, &b, &b)); // comba square is ready
if (resched)
rc += might_resched();
SAFE_OP(bn_add(&t2, &asquare, &bsquare));
SAFE_OP(bn_assign(&a, &t1));
SAFE_OP(bn_assign(&b, &t2));
if (k & (1ull << (i - 1))) { // current bit == 1
SAFE_OP(bn_add(&t1, &a, &b));
SAFE_OP(bn_assign(&a, &b));
SAFE_OP(bn_assign(&b, &t1));
f_i = (f_i * 2) + 1;
} else {
f_i = f_i * 2;
}
}
```
> 作為 web service (原本 kHTTPd 不算提供具體服務，但整合 Fibonacci 數運算就是了)，修改過的 kHTTPd 需要考慮到對客戶端請求的回應品質 (即 resoinsiveness)，比方說同時間有 `/fib/10`, `/fib/100`, `/fib/1000`, `/fib/10000` 等等需求進來，這時候都會加入 workqueue，但是能透過 TCP 回應給客戶端的運算卻會有時間落差，加入 `might_resched` 是個強化 kernel preemption 的手段，但不該只考慮 Fibonacci 數運算本身。
實驗執行 `htstress` ，只是同時間有數個，以 x 軸表示個數的 `/fib/6000000`「大請求」。這些請求的運算會被丟到 `wq-intensive` 當中。觀察透過 `sysfs` 設定 `wq-intensive` 的 nice value 對 `htstress` 執行成效的影響。可以發現，在大請求數量大的時候，對`wq-intensive` 設定較高的 nice value 才有稍微顯著的影響；但是，會增加數值震盪的範圍。（已經關閉 turbo mode，參數設定如 `fibdrv`）
### ftrace
盲目地在 fibonacci 計算過程加上 `might_resched` 並不是科學化的解決方式。為了精準分析各函式的執行時間，選擇使用 kernel 提供的 ftrace 機制。我們使用 ftrace 裡面的 `function_graph` 功能追蹤各函式執行的時間開銷。
```bash
sudo sh -c 'echo function_graph > /sys/kernel/tracing/current_tracer'
```
透過 `set_ftrace_filter` 設定要觀察的函式、而 `enabled_functions` 和 `available_filter_functions` 可以列出被選中以及可選的函式。其中，我們這樣設定要追蹤的函式。
```bash
sudo sh -c 'echo "http*" > /sys/kernel/tracing/set_ftrace_filter'
sudo sh -c 'echo "abn*" >> /sys/kernel/tracing/set_ftrace_filter'
sudo sh -c 'echo "bn*" >> /sys/kernel/tracing/set_ftrace_filter'
```
<!-- https://embeddedbits.org/tracing-the-linux-kernel-with-ftrace/ -->
<!-- https://blog.selectel.com/kernel-tracing-ftrace/ -->
<!-- README in sysfs of ftrace -->
然後透過以下開始記錄：
```bash
sudo sh -c ' echo 1 > /sys/kernel/tracing/tracing_on'
sudo sh cat /sys/kernel/tracing/trace_pipe
```
用 `wget -q localhost:8081/fib/6000` 觸發函式的執行：
```
------------------------------------------
3) kthread-2 => kworker-24324
------------------------------------------
3) | http_server_worker [khttpd]() {
3) ==========> |
3) | smp_irq_work_interrupt() {
3) | irq_enter() {
3) 0.179 us | rcu_irq_enter();
3) 0.151 us | irqtime_account_irq();
3) 0.887 us | }
3) | __wake_up() {
3) | __wake_up_common_lock() {
3) 0.190 us | _raw_spin_lock_irqsave();
3) | __wake_up_common() {
3) 9.482 us | autoremove_wake_function();
3) + 10.029 us | }
3) 0.154 us | _raw_spin_unlock_irqrestore();
3) + 10.919 us | }
3) + 11.190 us | }
3) | irq_exit() {
3) 0.155 us | irqtime_account_irq();
3) 0.140 us | idle_cpu();
3) 0.147 us | rcu_irq_exit();
3) 1.115 us | }
3) + 14.061 us | }
3) <========== |
3) | kernel_sigaction() {
3) 0.261 us | _raw_spin_lock_irq();
3) 0.629 us | }
3) | kernel_sigaction() {
3) 0.121 us | _raw_spin_lock_irq();
3) 0.368 us | }
3) | kmem_cache_alloc_trace() {
3) | _cond_resched() {
3) 0.121 us | rcu_all_qs();
3) 0.387 us | }
3) 0.120 us | should_failslab();
3) 0.130 us | memcg_kmem_put_cache();
3) 1.784 us | }
3) 0.135 us | http_parser_init [khttpd]();
3) 0.133 us | kthread_should_stop();
3) | http_server_recv.constprop.0 [khttpd]() {
3) | kernel_recvmsg() {
3) | sock_recvmsg() {
3) | security_socket_recvmsg() {
3) 0.701 us | selinux_socket_recvmsg();
3) 1.017 us | }
3) | inet_recvmsg() {
3) 3.630 us | tcp_recvmsg();
3) 4.027 us | }
3) 5.462 us | }
3) 5.783 us | }
3) 6.119 us | }
3) | http_parser_execute [khttpd]() {
3) 0.139 us | http_parser_callback_message_begin [khttpd]();
3) 0.208 us | parse_url_char [khttpd]();
3) 0.209 us | parse_url_char [khttpd]();
3) 0.122 us | parse_url_char [khttpd]();
3) 0.121 us | parse_url_char [khttpd]();
3) 0.125 us | parse_url_char [khttpd]();
3) 0.126 us | parse_url_char [khttpd]();
3) 0.147 us | parse_url_char [khttpd]();
3) 0.121 us | parse_url_char [khttpd]();
3) 0.121 us | parse_url_char [khttpd]();
3) 0.186 us | http_parser_callback_request_url [khttpd]();
3) 0.154 us | http_parser_callback_header_field [khttpd]();
3) 0.134 us | http_parser_callback_header_value [khttpd]();
3) 0.125 us | http_parser_callback_header_field [khttpd]();
3) 0.129 us | http_parser_callback_header_value [khttpd]();
3) 0.124 us | http_parser_callback_header_field [khttpd]();
3) 0.124 us | http_parser_callback_header_value [khttpd]();
3) 0.146 us | http_parser_callback_header_field [khttpd]();
3) 0.124 us | http_parser_callback_header_value [khttpd]();
3) 0.127 us | http_parser_callback_header_field [khttpd]();
3) 0.125 us | http_parser_callback_header_value [khttpd]();
3) 0.125 us | http_parser_callback_headers_complete [khttpd]();
3) 0.154 us | http_should_keep_alive [khttpd]();
3) | http_parser_callback_message_complete [khttpd]() {
3) 0.126 us | http_should_keep_alive [khttpd]();
3) | printk() {
3) | vprintk_func() {
3) 4.113 us | vprintk_default();
3) 4.510 us | }
3) 4.828 us | }
3) | abn_calculate_fib [khttpd]() {
3) | bn_fib_doubling [khttpd]() {
3) 0.824 us | bn_realloc.part.0 [khttpd]();
3) 0.433 us | bn_realloc.part.0 [khttpd]();
3) + 11.021 us | bn_realloc.part.0 [khttpd]();
3) 0.679 us | bn_realloc.part.0 [khttpd]();
3) 0.407 us | bn_realloc.part.0 [khttpd]();
3) 0.589 us | bn_realloc.part.0 [khttpd]();
3) 0.463 us | bn_realloc.part.0 [khttpd]();
3) 0.462 us | bn_realloc.part.0 [khttpd]();
3) 0.505 us | bn_alloc.part.0 [khttpd]();
3) 0.464 us | bn_alloc.part.0 [khttpd]();
3) 0.422 us | bn_realloc.part.0 [khttpd]();
3) 0.632 us | bn_realloc.part.0 [khttpd]();
3) 0.801 us | bn_realloc.part.0 [khttpd]();
3) 0.561 us | bn_realloc.part.0 [khttpd]();
3) 0.575 us | bn_realloc.part.0 [khttpd]();
3) 0.454 us | bn_alloc.part.0 [khttpd]();
3) 0.434 us | bn_alloc.part.0 [khttpd]();
3) 0.547 us | bn_alloc.part.0 [khttpd]();
3) 0.619 us | bn_realloc.part.0 [khttpd]();
3) 0.502 us | bn_realloc.part.0 [khttpd]();
3) 0.698 us | bn_realloc.part.0 [khttpd]();
3) 0.493 us | bn_realloc.part.0 [khttpd]();
3) 0.499 us | bn_alloc.part.0 [khttpd]();
3) 0.442 us | bn_alloc.part.0 [khttpd]();
3) 0.503 us | bn_alloc.part.0 [khttpd]();
3) 0.701 us | bn_realloc.part.0 [khttpd]();
3) 0.781 us | bn_realloc.part.0 [khttpd]();
3) 0.653 us | bn_realloc.part.0 [khttpd]();
3) 0.885 us | bn_realloc.part.0 [khttpd]();
3) 0.936 us | bn_realloc.part.0 [khttpd]();
3) 0.559 us | bn_alloc.part.0 [khttpd]();
3) 0.460 us | bn_alloc.part.0 [khttpd]();
3) 0.146 us | kfree();
3) 0.434 us | kfree();
3) 0.261 us | kfree();
3) 0.145 us | kfree();
3) 0.165 us | kfree();
3) 0.192 us | kfree();
3) 0.327 us | kfree();
3) + 79.063 us | }
3) | __kmalloc() {
3) 0.134 us | kmalloc_slab();
3) 0.175 us | _cond_resched();
3) 0.131 us | should_failslab();
3) 0.125 us | memcg_kmem_put_cache();
3) 1.220 us | }
3) 0.200 us | kfree();
3) + 86.827 us | }
3) | __kmalloc() {
3) 0.211 us | kmalloc_slab();
3) | _cond_resched() {
3) 0.134 us | rcu_all_qs();
3) 0.388 us | }
3) 0.124 us | should_failslab();
3) 0.150 us | memcg_kmem_put_cache();
3) 1.655 us | }
3) | http_server_send [khttpd]() {
3) | kernel_sendmsg() {
3) + 48.478 us | sock_sendmsg();
3) + 49.009 us | }
3) + 49.377 us | }
3) 0.400 us | kfree();
3) 0.176 us | kfree();
3) ! 147.607 us | }
3) ! 165.837 us | }
3) 0.175 us | http_should_keep_alive [khttpd]();
3) 0.170 us | kthread_should_stop();
3) | http_server_recv.constprop.0 [khttpd]() {
3) | kernel_recvmsg() {
3) | sock_recvmsg() {
3) | security_socket_recvmsg() {
3) 0.260 us | selinux_socket_recvmsg();
3) 0.712 us | }
3) | inet_recvmsg() {
3) | tcp_recvmsg() {
3) # 1460.636 us | }
3) ==========> |
3) 6.173 us | smp_irq_work_interrupt();
3) <========== |
3) # 1468.984 us | }
3) # 1470.158 us | }
3) # 1470.449 us | }
3) # 1470.781 us | }
3) | printk() {
3) | vprintk_func() {
3) | vprintk_default() {
3) | vprintk_emit() {
3) 0.128 us | __printk_safe_enter();
3) 0.130 us | _raw_spin_lock();
3) 1.361 us | vprintk_store();
3) 0.123 us | __printk_safe_exit();
3) 0.405 us | __down_trylock_console_sem.isra.0();
3) 0.235 us | console_trylock.part.0();
3) 0.678 us | console_unlock();
3) 0.244 us | wake_up_klogd();
3) 4.892 us | }
3) 5.161 us | }
3) 5.457 us | }
3) 5.741 us | }
3) | kernel_sock_shutdown() {
3) | inet_shutdown() {
3) | lock_sock_nested() {
3) | _cond_resched() {
3) 0.126 us | rcu_all_qs();
3) 0.373 us | }
3) 0.153 us | _raw_spin_lock_bh();
3) 0.120 us | __local_bh_enable_ip();
3) 1.151 us | }
3) 0.135 us | tcp_shutdown();
3) 0.134 us | sock_def_wakeup();
3) | release_sock() {
3) 0.121 us | _raw_spin_lock_bh();
3) 0.122 us | tcp_release_cb();
3) | _raw_spin_unlock_bh() {
3) 0.129 us | __local_bh_enable_ip();
3) 0.382 us | }
3) 1.175 us | }
3) 3.393 us | }
3) 3.740 us | }
3) | sock_release() {
3) | __sock_release() {
3) | inet_release() {
3) 0.130 us | ip_mc_drop_socket();
3) | tcp_close() {
3) 0.318 us | lock_sock_nested();
3) 0.142 us | _raw_write_lock_bh();
3) 0.178 us | _raw_write_unlock_bh();
3) 0.120 us | _raw_spin_lock();
3) 0.122 us | __release_sock();
3) 1.719 us | inet_csk_destroy_sock();
3) 0.129 us | __local_bh_enable_ip();
3) 0.298 us | release_sock();
3) 2.400 us | sk_free();
3) 6.918 us | }
3) 7.482 us | }
3) 0.127 us | module_put();
3) | iput() {
3) 0.170 us | _raw_spin_lock();
3) | evict() {
3) 0.325 us | inode_wait_for_writeback();
3) 0.291 us | truncate_inode_pages_final();
3) 0.229 us | clear_inode();
3) 0.130 us | _raw_spin_lock();
3) 0.243 us | wake_up_bit();
3) 1.644 us | destroy_inode();
3) 3.962 us | }
3) 4.701 us | }
3) + 12.903 us | }
3) + 13.147 us | }
3) 0.357 us | kfree();
3) | kfree() {
3) 0.158 us | __slab_free();
3) 0.526 us | }
3) # 1689.907 us | }
```
## `epoll()` 系統呼叫
## 效能分析
## 效能改進
Sign in with Wallet
Connect another wallet