# 2023q1 Homework7 (ktcp)
contributed by < `Jerejere0808` >
### $ sudo insmod kecho.ko port=1999 是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？
首先透過 `$modinfo khttpd.ko` 可以看到核心模組的資訊裡面包含了參數 `port` 和 `backlog`，還有他們的型態。這是透過呼叫 `module_param` 來達成。
```c
filename: /home/jeremy/linux2023/kecho/kecho.ko
version: 0.1
description: Fast echo server in kernel
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: B6A03CB250D9012096D9EDC
depends:
retpoline: Y
name: kecho
vermagic: 5.19.0-35-generic SMP preempt mod_unload modversions
parm: port:ushort
parm: backlog:ushort
parm: bench:bool
```
根據 [The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/#passing-command-line-arguments-to-a-module) `moduleparam.h` 可以找到 `module_param` 的定義，接著往下找到最深層，發現巨集 `__module_param_call` 就是負責註冊參數的關鍵：
```c
#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 } }
```
若是以 kecho_mod.c 的 port 為例，會展開成以下結果:
```c
static const char __param_str_port[] = "port";
static struct kernel_param __moduleparam_const __param_port
__used
__attribute__ ((unused,__section__ ("__param"),aligned(sizeof(void *))))
= {
__param_str_port, THIS_MODULE, &ushort_param_ops,
VERIFY_OCTAL_PERMISSIONS(S_IRUGO), 0, 0, { DEFAULT_PORT }
};
```
解釋如下：
__param_str_port：定義了一個字串，用於表示參數名稱，值為 "port"。
__param_port：定義了一個靜態結構體，代表了參數的相關屬性，包括參數名稱、所屬的內核模組、操作函數指標、參數的許可權、層級、標誌和預設值。其中的 __used 屬性表示這個結構體是被使用的，__section__ 屬性指定了這個結構體的分區（section），aligned 屬性則指定了結構體的對齊方式。
ushort_param_ops：一個操作函數指標，指向了一個用於解析和設定 ushort 型別參數的操作函數。
VERIFY_OCTAL_PERMISSIONS(S_IRUGO)：表示設定了參數的許可權為 S_IRUGO，即允許讀取。
0：表示參數的層級為 0，即不限制讀取和修改的權限。
0：表示參數的標誌為 0，即無特定屬性。
{ DEFAULT_PORT }：表示參數的預設值為 DEFAULT_PORT，這是一個預先定義的預設值。
綜上所述，這個函數呼叫將 port 變數定義為一個名稱為 "port" 的模組參數，允許在模組載入時讀取
### user-echo-server 的 epoll 系統呼叫
user-server 內使用了 epoll 去達成 I/O multiplexing ， 如此一來可以讓一個 thread 處理多個 client socket 連線，且 server 本身可以持續接受連線而不會 block 住。
以下是 epoll 的介紹:
:::warning
注意用語並改進漢語描述！
:notes: jserv
:::
變數：
epfd 或 epollfd：可以想成是 epoll 的一個物件，它上面有兩個列表，即 interset list 和 ready list，後者是前者的子集。當資料從不可讀變成可讀時，會出現在 ready list 中。
fd：在建立 socket 時回傳的檔案描述子(file descriptor)，有時會命名為 listen_sock，用來表示監聽的 socket。
events 或 ev：用來描述檔案描述子(fd)的資料結構。例如，ev.events = EPOLLIN 表示 fd 為可讀的資料。
註：這裡的 events 變數有別於 user-echo-server.c 範例中的 struct epoll_event events，後者是準備給 epoll_wait 函數使用的參數，用來記錄改變的 epfd。
函式：
epoll_create：建立一個 epoll 物件，可以想成是建立前述 epfd 的實例 (instance)，類似於 C++ 中的 new epoll()。
`epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)`：對前面建立的 epfd 進行操作，例如新增或刪除監聽成員。其中，epfd 是掌管目前 interset list 和 ready list 的資料結構，op 參數可以填入一些巨集來指示想要進行的操作，fd 是要新增或刪除的某個 socket 的檔案描述子，event 是用來記錄 fd 更多資訊的資料結構。
`epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)`：用來通知使用者目前可用(可讀/可寫)的 fd 有哪些。epoll_wait 會檢查 ready list 上有哪些 fd，並將其通知到 events 參數上，因此通常 events 是一個陣列。timeout 參數可以設定等待的時間。回傳值若大於等於 0，表示 ready 的 fd 數量，否則表示沒有。
與 select 的差異:
select 也是一種達成 I/O multiplexing 的方式，原理是將已連接的 Socket 放到一個 fd 集合中，然後呼叫 select 函數將 fd 集合複製到 kerenl 中，讓 kerenl 檢查是否有網絡事件產生。 kerenl 會透過遍歷每個 fd 的方式來檢查每個 fd 是否有事件產生，並將有事件的 fd 標記為可讀或可寫，之後再傳出到 userspace，然後再次遍歷 fd 集合找到被標記為可讀或可寫的檔案描述子，並進行相應的處理。
所以使用 select 的方式需要走訪兩次 fd 集合，一次在 kerenl 裡，一次在 userspace 裡。
此外，使用 select 還需要進行兩次複製 fd 集合，一次是從 userspace 傳入 kerenl 空間，由 kerenl 進行修改，再傳出到 userspace 。這樣的複製操作可能會增加系統開銷。
epoll 通過兩個方面，很好解決了 select 的問題。
第一點，epoll 在 kerenl 裡使用紅黑樹來跟踪所有待檢測的 fd ，把需要監控的 socket 通過 epoll_ctl() 函數加入 kerenl 中的紅黑樹裡，因此增刪改一般時間複雜度是 O(logn)。而 select kerenl 裡沒有類似 epoll 紅黑樹這種保存所有待檢測的 socket 的資料結構，所以 select/poll 每次操作時都傳入整個 fd 集合給 kerenl ，而 epoll 因為在 kerenl 維護了紅黑樹，可以保存所有待檢測的 fd ，所以只需要傳入一個待檢測的 fd，減少了 kerenl 跟 usersapce 之間的複製資料成本。
第二點，epoll 使用事件驅動的機制， kerenl 裡維護了一個列表(剛剛提過的 ready list )來記錄就緒事件，當某個 fd 有事件發生時，通過回調函數內核會將其加入到這個就緒事件列表中，當使用者調用 epoll_wait() 函數時，只會返回有事件發生的檔案描述子的個數，不需要像 select 那樣輪詢掃描整個 fd 集合，也就是說不用一個一個查看(如果 fd 很多就會導致效能線性下降)而是在 epoll_wait 時先睡覺若在 timeout 到之前有 fd 準備好資料就喚醒，大大提高了檢測的效率。
### 以下 khttpd 部分待整理....
### 引入 Concurrency Managed Workqueue (cmwq)，改寫 kHTTPd
在原本的實作中可以看到 server 會在有新的 client 連線時，創造一個新的 kthread 去跑 function http_server_worker()，專門處理處理這個 client 發出的要求。 這種做法在連線數量非常多的時候，會需要創造許多 thread ，造成額外的時間花費。
```c
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
if (IS_ERR(worker)) {
pr_err("can't create more worker process\n");
continue;
}
```
若要改用 Concurrency Managed Workqueue，就必須幫每個 socket 建立一個 struct work_struct 資料結構，並放到 Workqueue 裡面，輪到其執行時就找到對應的 socket ，並接收 client 要求。 另外 ， 因為 server 結束運行時也要 flush 每個 work ， 所以要有一個 linked list 紀錄所在位置。 綜上所述，我們會需要自己創造一個資料結構，如下:
```c
struct http_work {
struct socket *socket;
struct work_struct khttpd_work;
struct list_head node;
};
```
```c
static struct work_struct *create_work(struct socket *sk)
{
struct http_work *work;
//創建立一個 http_work
if (!(work = kmalloc(sizeof(struct http_work), GFP_KERNEL)))
return NULL;
work->socket = sk;
//指定 worker 執行到這個 http_work 的 work 時，要執行的函數
INIT_WORK(&work->khttpd_work, http_server_worker_CMWQ);
//用 linked list 追蹤每個 http_request，方便最後找到要釋放的記憶體位置
list_add(&work->node, &daemon_list.head);
return &work->khttpd_work;
}
```
因為放進 cmwq work queue 的是 work，但是執行時相對應的函數(也就是接收並處理 client 的要求)時，必須要有對應到此 work 的 socket。所以在執行時，必須先透過 container_of 找到包含它的 http_request 記憶體起始位置，再存取到socket。
```c
static void http_server_worker_CMWQ(struct work_struct *work)
{
struct http_work *worker =
container_of(work, struct http_request, khttpd_work);
...
```
最後 server 停止時，也必須把 struct http_work 裡面的 socket 關閉也把 work 釋放掉(這時候就用的到剛剛建立struct http_work 時裡的放進 linked list 的 node 了)
```c
static void free_work(void)
{
struct http_work *l, *tar;
/* cppcheck-suppress uninitvar */
list_for_each_entry_safe (tar, l, &daemon_list.head, node) {
kernel_sock_shutdown(tar->socket, SHUT_RDWR);
flush_work(&tar->khttpd_work);
sock_release(tar->socket);
kfree(tar);
}
}
```
使用 ./htstress http://localhost:8081 -t 3 -c 20 -n 200000 做 throughput 測試
以下的 throghput 情境為未使用 Concurrency Managed Workqueue Queue 並且在每次 server 用 buffer 接收 client 要求後，用 pr_info() 去觀察 buffer 裡的值。
```c
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
pr_info("buf = %s\n", buf);
```
Throughput:
```
./htstress http://localhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 1 [0%]
seconds: 11.750
requests/sec: 17021.581
```
註解掉 pr_info() 後的 throughput，可以發現有上升，代表 pr_info() 所花的時間是相當可觀。
Throughput:
```
./htstress http://localhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 9.513
requests/sec: 21023.756
```
以下為使用 Concurrency Managed Workqueue Queue 的 Throughput，一下提升到 54048.342 requests/sec。可見 Concurrency Managed Workqueue Queue 讓 thread 在 workqueue 中沒有任務時會維持等待任務的狀態，而不是在任務完成後就被釋放，如此可以省下大量創建 thread 的時間。
Throughput:
```
./htstress http://localhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 3.700
requests/sec: 54048.342
```
### 使用 Transfer-Encoding 傳送資料夾檔案資訊
當使用普通模式，即非 KeepAlive 模式時，每個請求/應答客戶和服務器都要新建一個連接，完成 之後立即斷開連接（ HTTP 協議爲無連接的協議）；當使用 Keep-Alive 模式（又稱持久連接、連接重用）時， Keep-Alive 功能使客戶端到服 務器端的連接持續有效，當出現對服務器的後繼請求時， Keep-Alive 功能避免了建立或者重新建立連接。
Keep-Alive 模式發送玩數據 HTTP 服務器不會自動斷開連接，客戶端用兩種方法判斷請求所得到的響應數據已經接收完成:
Conent-Length
顧名思義， Conent-Length 表示實體內容長度，客戶端（服務器）可以根據這個值來判斷數據是否接收完成。
Chunked-transfer-encoding
chunk 編碼將數據分成一塊一塊的發生。 Chunked 編碼將使用若干個 Chunk 串連而成，由一個標明長度爲 0 的 chunk 標示結束。每個 Chunk 分爲頭部和正文兩部分，頭部內容指定正文的字符總數（十六進制的數字）和數量單位（一般不寫），正文部分就是指定長度的實際內容，兩部分之間用回車換行( CRLF ) 隔開。在最後一個長度爲0的 Chunk 中的內容是稱爲 footer 的內容，是一些附加的 Header 信息（通常可以直接忽略）
傳送資料夾內的檔案資訊因為事先不會知道實體內容長度為多少(不知道有幾個檔案)，所以這邊就以 Chunked-transfer-encoding 來傳送。若是要傳送檔案內容就使用 Conent-Length 。
以下為傳送資料夾內檔案資訊的部分，可以看到 iterate_dir() 函數，其用來迭代資料夾的目錄。 程式碼第 2 行，將把函式 iterate_dir 導向到函式 tracedir ，換言之就是在執行函式 iterate_dir 的過程中會呼叫 tracedir。
```c=
...
request->dir_context.actor = tracedir;
...
if (S_ISDIR(fp->f_inode->i_mode)) {
char send_buf[SEND_BUFFER_SIZE] = {0};
snprintf(send_buf, SEND_BUFFER_SIZE, "%s%s%s", "HTTP/1.1 200 OK\r\n",
"Content-Type: text/html\r\n",
"Transfer-Encoding: chunked\r\n\r\n");
http_server_send(request->socket, send_buf, strlen(send_buf));
snprintf(send_buf, SEND_BUFFER_SIZE, "7B\r\n%s%s%s%s",
"<html><head><style>\r\n",
"body{font-family: monospace; font-size: 15px;}\r\n",
"td {padding: 1.5px 6px;}\r\n",
"</style></head><body><table>\r\n");
http_server_send(request->socket, send_buf, strlen(send_buf));
iterate_dir(fp, &request->dir_context);
snprintf(send_buf, SEND_BUFFER_SIZE,
"16\r\n</table></body></html>\r\n");
http_server_send(request->socket, send_buf, strlen(send_buf));
snprintf(send_buf, SEND_BUFFER_SIZE, "0\r\n\r\n");
http_server_send(request->socket, send_buf, strlen(send_buf));
}
...
```
可以看到每次呼叫 tracedir() 就會把讀報的檔案名或資料夾名透過 Chunked-transfer-encoding 傳送。
```c=
static int tracedir(struct dir_context *dir_context,
const char *name,
int namelen,
loff_t offset,
u64 ino,
unsigned int d_type)
{
if (strcmp(name, ".") && strcmp(name, "..")) {
struct http_request *request =
container_of(dir_context, struct http_request, dir_context);
char buf[SEND_BUFFER_SIZE] = {0};
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", name, name);
http_server_send(request->socket, buf, strlen(buf));
}
return 0;
}
```
### 使用 Ftrace 觀察 kHTTPd
做到這裡，先用 ftrace 測量並觀察一下執行時間的瓶頸在哪裡，可以發現第 48 行 iterate_dir() 花了 619.143 us，若可以改善就能省下不少時間。
```=
http_server_worker_CMWQ [khttpd]() {
7) | kernel_sigaction() {
7) 0.660 us | _raw_spin_lock_irq();
7) 0.182 us | _raw_spin_unlock_irq();
7) 1.453 us | }
7) | kernel_sigaction() {
7) 0.172 us | _raw_spin_lock_irq();
7) 0.176 us | _raw_spin_unlock_irq();
7) 0.848 us | }
7) | kmem_cache_alloc_trace() {
7) 0.167 us | __cond_resched();
7) 0.168 us | should_failslab();
7) 1.133 us | }
7) 0.173 us | http_parser_init [khttpd]();
7) | kernel_recvmsg() {
7) | sock_recvmsg() {
7) | security_socket_recvmsg() {
7) 0.678 us | apparmor_socket_recvmsg();
7) 1.031 us | }
7) | inet_recvmsg() {
7) 3.910 us | tcp_recvmsg();
7) 4.263 us | }
7) 5.863 us | }
7) 6.226 us | }
7) | http_parser_execute [khttpd]() {
7) 0.185 us | http_parser_callback_message_begin [khttpd]();
7) 0.200 us | parse_url_char.part.0 [khttpd]();
...
7) 0.169 us | parse_url_char.part.0 [khttpd]();
7) 0.229 us | http_parser_callback_request_url [khttpd]();
7) 0.168 us | http_parser_callback_header_field [khttpd]();
7) 0.175 us | http_parser_callback_header_value [khttpd]();
7) 0.185 us | http_parser_callback_headers_complete [khttpd]();
7) 0.177 us | http_message_needs_eof [khttpd]();
7) 0.183 us | http_should_keep_alive [khttpd]();
7) | http_parser_callback_message_complete [khttpd]() {
7) 0.169 us | http_should_keep_alive [khttpd]();
7) | _printk() {
7) 7.532 us | vprintk();
7) 7.964 us | }
7) | directory_handler.isra.0 [khttpd]() {
7) 0.466 us | kmem_cache_alloc_trace();
7) + 11.456 us | filp_open();
7) + 41.726 us | http_server_send.isra.0 [khttpd]();
7) + 28.557 us | http_server_send.isra.0 [khttpd]();
7) ! 619.143 us | iterate_dir();
7) + 22.697 us | http_server_send.isra.0 [khttpd]();
7) + 19.107 us | http_server_send.isra.0 [khttpd]();
7) 2.910 us | filp_close();
7) 0.292 us | kfree();
7) ! 749.799 us | }
7) ! 758.680 us | }
7) ! 768.669 us | }
```
至於改善的方法，目前想到可以用 server cache 的概念，將之前讀過的資料存在 memory 就不用每次都重複讀，做法是建立一個 hash table， key 為 url , value 為對應的檔案資料或資料夾目錄，若之前讀過的資料可以先放置在 hash table ， 過一段時間若沒有存取就把它消除，並透過 RCU 的機制讓 reader 可以不被 block 住，若有資料要被刪除就等待 grace period ， 若有幾個特定 url 被頻繁讀取會使讀的次數遠大於修改和刪除，因此很適合使用 RCU。
### 實作 request cache
:::danger
中英文間用一個半形空白字元區隔
:notes: jserv
:::
Sign in with Wallet
Connect another wallet