# 2019q1 Homework5 (daemon)
contributed by < `grant7163` >
###### tags: `sysprog2019_q1`
## 作業要求
依據 [F09: daemon](https://hackmd.io/s/r14Qu9hYV)
1. 指出 [kecho 程式碼](https://github.com/sysprog21/kecho) 實作的缺失 (注意像是 buffer overflow 一類的問題)，並在你 fork 出來的 repository 中予以改進
* Linux 核心版本至少為 `4.15`, 可嘗試熱騰騰的 `linux-5.1`
* 留意 kernel API 的變更
3. 參閱相關材料，設計足以驗證 `kecho` 效能的實驗，過程中留意到 concurrency;
4. 在 `kecho` 的程式碼基礎上，引入 [Concurrency Managed Workqueue (cmwq)](https://www.kernel.org/doc/html/v4.15/core-api/workqueue.html)，配合 (2) 的實驗，提出效能改善計畫和落實;
5. 研究 KernelHTTP，整合到 `kecho` 目錄中，以另外一個 Linux 核心模組或者共用程式碼的方式存在，比照 [Kernel HTTPd](https://paper.dropbox.com/doc/Kernel-HTTP--AbVuMmS_1IXB9OFPxLvNOsdDAQ-3WwKZiKh6TAMkIOgRtG8Y) 共筆的實驗，檢驗效能和正確性;
## 前置測試
從老師的 [github](https://github.com/sysprog21/kecho) 上 fork 完 kecho 之後，開始嘗試編譯。
```shell
$ git clone https://github.com/grant7163/kecho
$ make
```
接著將 fastecho module 載入到 kernel 中並執行它。
```shell
$ sudo insmod fastecho.ko
$ telnet localhost 12345
```
測試輸入字元，發現除了會回應剛剛打的字元外還多出其它的亂碼。
```shell
$ telnet localhost 12345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
test
test
F�'�; 0
```
使用 dmesg 命令觀察 fastecho moudle 發生了什麼事。
前面在做一些初始化的動作接著等待 client 端傳送訊息，從 get request 訊息中看到除了回應原本要傳的字串外，後面還多了多餘的字串。
```shell
[ 5782.831266] fastecho: socket create ok....
[ 5782.831270] fastecho: setsockopt ok....
[ 5782.831274] fastecho: socket bind ok....
[ 5782.831278] fastecho: socket listen ok....
[ 5787.735509] fastecho: socket create ok....
[ 5787.735513] fastecho: setsockopt ok....
[ 5787.735516] fastecho: socket bind ok....
[ 5787.735520] fastecho: socket listen ok....
[ 5787.735524] fastecho: start get response
...
[ 7491.804434] fastecho: get request = test
F\xa8'\xd2; 0
```
## 開發紀錄
接著回頭來看原始碼，在 fastecho_module.c 中，觀察模組初始化做了哪些事。
fastecho_init_module :
* sock_create(PF_INET, SOCK_STREAM, IPPROTO_TCP, &sock)
* Protocol family : AF_ 前綴代表 address family，PF_ 前綴代表 protocol family (還是要依據實作，一般來說 AF_XXX = PF_XXX)
* PF_INET(protocol family) : 使用 IPv4 protocol
* PF_INET6(protocol family) : 使用 IPv6 protocol
* AF_KEY : 提供加密安全姓
* type of socket :
* SOCK_STREAM : 提供一個序列化以及可靠的 byte stream
* SOCK_DGRAM : 提供一個不可靠的數據包應用在網路廣播
* SOCK_RAW : 提供一個直接存取IP協定的數據
* protocol of sockets :
* IPPROTO_TCP (0) : 指定使用 TCP 協定
* IPPROTO_UDP (0) : 指定使用 UDP 協定
* IPPROTO_SCTP : 指定使用 SCTP 協定
* IPPROTO_UDPLITE : 指定使用 UDP extension 協定
* kernel_setsockopt(sock, SOL_TCP, TCP_NODELAY, (char *) &opt, sizeof(opt))
* SOL_TCP (IPPROTO_TCP) : 提供 TCP level 的相關設定 (TCP_xxx)
* SOL_SOCKET : 提供 socket level 的相關設定 (SO_xxx)
* SO_REUSEADDR :
* TCP_NODELAY : 關閉 TCP 資料處理的 Nagle’s Algorithm
參考 [TCP 參數對延遲和傳輸量的影響](https://medium.com/fcamels-notes/tcp-%E5%8F%83%E6%95%B8%E5%B0%8D%E5%BB%B6%E9%81%B2%E5%92%8C%E5%82%B3%E8%BC%B8%E9%87%8F%E7%9A%84%E5%BD%B1%E9%9F%BF-12910f8d82bd)
* kernel_bind(sock, (struct sockaddr *) &addr, sizeof(addr))
* 給 socket 綁定一個指定的位址
* kernel_listen(sock, DEFAULT_BACKLOG)
* 當使用 socket() 創建一個 socket 時，初始為一個主動的 socket，會用於發起一個 connect，listen() 會將一個 socket 從主動轉為被動 (接受連線請求)，TCP state machine 會從 closed 轉為 listen
* DEFAULT_BACKLOG : 用於指定不完整連接隊列和完整連接 queue 兩者總數的最大值
(因為 client 端有可能在 server 呼叫 accept() 之前就呼叫 connect() 或 server busy)
* 不完整連接隊列中包含每個已從 client 接收到的 SYN（同步請求）entry，此時服務器正等待完成 TCP handshake。這些 socket 的狀態為 SYN_RCVD（同步已接收）
* 完整連接隊列中包含每個已完成 TCP 三次握手的 client entry。此時，這些 socket 的狀態為 ESTABLISHED
* 當這些列隊都滿的話，server 端會忽略該 request，client 的 TCP 重傳機制將重新在發送 request
* kthread_run(echo_server_daemon, ¶m, MODULE_NAME)
* 建立一個 kernel thread 並執行它
依據[/include/linux/kthread.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/kthread.h#L44) 中的定義
echo_server_daemon :
* kernel_accept(param->listen_sock, &sock, 0)
* 一個典型的伺服器通常只創建一個 listen socket，並在伺服器的整個生命周期內持續存在。而每當有一個客戶端連接被接受（即完成了 TCP 三次握手），內核會為該連接創建一個新的 connect socket。當伺服器完成對某個客戶端的服務後，應關閉該已連接套接字
* accept 的第一個參數稱為 listening socket
* accept 的返回值則稱為 connected socket
參考[CS:APP 第 11 章](https://hackmd.io/s/ByPlLNaTG)
## TCP Connection Establishment and Termination
接著建立一個主要來處理字串接收與傳送的函式，發現在 echo_server_worker() 中
用來接收與傳送的 buf 未經初始化的步驟就直接使用，才會導致在終端機上看到亂碼出現。
```shell
int echo_server_daemon(void *arg)
{
...
/* start server worker */
thread = kthread_run(echo_server_worker, sock, MODULE_NAME);
...
}
static int echo_server_worker(void *arg)
{
...
buf = kmalloc(BUF_SIZE, GFP_KERNEL);
if (!buf) {
printk(KERN_ERR MODULE_NAME ": kmalloc error....\n");
return -1;
}
while (!kthread_should_stop()) {
res = get_request(sock, buf, BUF_SIZE - 1);
if (res <= 0) {
if (res) {
printk(KERN_ERR MODULE_NAME ": get request error = %d\n", res);
}
break;
}
res = send_request(sock, buf, strlen(buf));
if (res < 0) {
printk(KERN_ERR MODULE_NAME ": send request error = %d\n", res);
break;
}
}
...
}
```
在 send_request() 中使用 strsep() 只擷取換行('\n')之前的字串來解決亂碼出現的問題。
```clike=
static int send_request(struct socket *sock, unsigned char *buf, size_t size)
{
int length;
struct kvec vec;
struct msghdr msg;
char *tmp = buf;
char *pString = NULL;
msg.msg_name = NULL;
msg.msg_namelen = 0;
msg.msg_control = NULL;
msg.msg_controllen = 0;
msg.msg_flags = 0;
pString = strsep(&tmp, "\n");
vec.iov_base = pString;
vec.iov_len = strlen(pString);
printk(MODULE_NAME ": start send request.\n");
length = kernel_sendmsg(sock, &msg, &vec, 1, strlen(pString) - 1);
printk(MODULE_NAME ": send request = %s\n", pString);
return length;
}
```
從終端機上看到不會有亂碼出現了，不過有趣的是 `\n test` 具然也可以顯示出來。
```shell
$ telnet localhost 12345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
test
test
1234567
1234567
\n test
\n test
```
### buffer overflow
為了容易讓 buffer overflow 的現象產生，將 BUF_SIZE 修改為 5 byte，此時在終端機上看到亂碼又出現了。
```shell
$ telnet localhost 12345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
12345678
1234T[��¤4�T[���4�T[��__para5678T[��¤4�T[���4�T[��__para
```
觀察印出配置記憶體給 buf 後裡面的內容，果然裡面已經存在不符合預期的資料。
又因為輸入的字串超過 buf 的長度，從網路底層的緩衝區只能讀取出 4 byte 並將複製到 buf 前 4 byte 中，使的 send_request() 中 strsep() 會連同不符合預期的資料一起判斷直到搜尋到換行的符號或字串的結束符號。
```shell
[113904.441721] fastecho: buf = :\xa44\xecT[\x95\xb9¤4\xecT[\x95\xb9\xaa4\xecT[\x95\xb9__param
...
[113904.766557] fastecho: get request = 1234T[\x95\xb9¤4\xecT[\x95\xb9\xaa4\xecT[\x95\xb9__param
[113904.766561] fastecho: start send request.
[113904.766621] fastecho: send request = 1234T[\x95\xb9¤4\xecT[\x95\xb9\xaa4\xecT[\x95\xb9__param
[113904.766623] fastecho: start get response
[113904.766627] fastecho: get request = 5678T[\x95\xb9¤4\xecT[\x95\xb9\xaa4\xecT[\x95\xb9__param
[113904.766630] fastecho: start send request.
[113904.766659] fastecho: send request = 5678T[\x95\xb9¤4\xecT[\x95\xb9\xaa4\xecT[\x95\xb9__param
```
在配置記憶體給 buf 之後馬上初始化 buf 來解決亂碼出現的問題。
```shell
static int echo_server_worker(void *arg)
{
...
buf = kmalloc(BUF_SIZE, GFP_KERNEL);
if (!buf) {
printk(KERN_ERR MODULE_NAME ": kmalloc error....\n");
return -1;
}
memset(buf,'\0',BUF_SIZE);
...
}
```
這次回應的結果沒亂碼產生了，不過從終端機上看到資料有少。
```shell
$ telnet localhost 12345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
12345678
123567
```
使用 dmesg 觀察 printk 的訊息，發現接收與傳送確實沒有漏掉資料，在 send_request() 中發現傳送的長度用先作減一的動作，將此減一動作拿掉。
```shell
[ 175.829208] fastecho: start get response
[ 180.992999] fastecho: get request = 1234
[ 180.993000] fastecho: start send request.
[ 180.993014] fastecho: send request = 1234
[ 180.993014] fastecho: start get response
[ 180.993015] fastecho: get request = 5678
[ 180.993016] fastecho: start send request.
[ 180.993035] fastecho: send request = 5678
```
最後終於可以顯示正常字串了。
```shell
$ telnet localhost 12345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
12345678
12345678
```
### 效能分析
實驗環境
```shell
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
製程： 9
CPU MHz： 900.044
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5616.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s)： 0-7
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d
$ cat /proc/version
Linux version 4.15.0-50-generic (buildd@lcy01-amd64-013) (gcc version 7.3.0 (Ubuntu 7.3.0-16ubuntu3))
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.2 LTS"
```
參考 [arut github](https://github.com/arut/htstress) 的作法，建立執行緒執行 client 端的程式(啟動連線並收發訊息一次後關閉連線)，使用 epoll_create()
```shell
$ ./clienttest -n 10000 -c 1 -t 1
requests: 10000
good requests: 10000 [100%]
seconds: 0.474
requests/sec: 21088.727
```
```shell
$ ./clienttest -n 10000 -c 1 -t 4
requests: 10000
good requests: 10000 [100%]
seconds: 0.466
requests/sec: 21474.204
```
加入 cmwq 機制
```shell
$ ./clienttest -n 10000 -c 1 -t 1
requests: 10000
good requests: 10000 [100%]
seconds: 0.240
requests/sec: 41632.147
```
```shell
$ ./clienttest -n 10000 -c 1 -t 4
requests: 10000
good requests: 10000 [100%]
seconds: 0.229
requests/sec: 43723.110
```
### kernelHTTP
```shell
```
Sign in with Wallet
Connect another wallet