2022q1 Homework6 (ktcp)

contributed by < YiChianLin >

作業說明
 作業區

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                 x86_64
CPU op-mode(s):               32-bit, 64-bit
Byte Order:                   Little Endian
Address sizes:                39 bits physical, 48 bits virtual
CPU(s):                       16
On-line CPU(s) list:          0-15
Thread(s) per socket:         2
Core(s) per socket:           8
Socket(s):                    1
NUMA node(s):                 1
Vendor ID:                    GenuineIntel
CPU family:                   6
model:                        158
Model name:                   Intel(R) Core(TM) i9-9900KF CPU @ 3.60GHz
Stepping:                     12
CPU MHz:                      3600.000
CPU max MHz:                  5000.0000
CPU min MHz:                  800.0000
BogoMIPS:                     7200.00
L1d cache:                    256 KiB
L1i cache:                    256 KiB
L2 cache:                     2 MiB
L3 cache:                     16 MiB
NUMA node0 CPU(s):            0-15

`htstress.c` 流程

htstress.c 為 client，做為發送給 server 的測試，未傳入參數時可以得到參數的設定模式，如下

$./htstress
Usage: htstress [options] [http://]hostname[:port]/path
Options:
   -n, --number       total number of requests (0 for inifinite, Ctrl-C to abort)
   -c, --concurrency  number of concurrent connections
   -t, --threads      number of threads (set this to the number of CPU cores)
   -u, --udaddr       path to unix domain socket
   -h, --host         host to use for http request
   -d, --debug        debug HTTP response
   --help             display this message

對應在 script/test.sh 中的敘述:

./htstress -n 100000 -c 1 -t 4 http://localhost:8081/

-n : 表示對 server 請求連線的數量
-c : 表示總體對 server 的連線數量
-t : 表示使用多少執行緒

參考 KYG-yaya573142/khttpd

main 中主要建立與 server 的連線

設定參數 : 透過 getopt_long() 獲得輸入的參數，再透過 swtich 設定對應的變數
設定連線所需的資訊 : getaddrinfo 取得多個 addrinfo 結構，裡面含有 server 的 IP 位址
計算時間 : start_time() 紀錄時間，使用 gettimeofday() 計算運行時間
測試 server 連線 : 使用 pthread_create 創立參數所設定的執行數數量，執行 worker() 函式對應到每一個創建 client，發送連線請求給 server
印出測試結果

再來看到 worker() 函式，與 server 進行連線過程，分別要建立與 server 連線的 client 與 epoll 程序監聽

建立 epoll_event 結構陣列儲存監聽資料，變數名稱為 evts[MAX_EVENT] (MAX_EVENT 為設定監聽事件數量的最大值)

struct epoll_event
{
  uint32_t events;	/* Epoll events */
  epoll_data_t data;	/* User data variable */
} __EPOLL_PACKED;

epoll_create (變數為 efd)建立總體對 server 的 concurrency(1) 連線

不過自從 Linux2.6.8 後 epoll_create 中 size 的引數是被忽略的，建立好後占用一個 fd，使用後必須呼叫 close() 關閉，否則會導致資源的浪費

socket 連線方式，定義於函式 init_conn()，並設定 epoll 程序
- socket 連線定義於 struct econn ecs[concurrency], *ec 中，進行初始化將 efd(epoll fd) 與 socket(ecs) 傳入 init_conn() 中
- 先透過 socket() 建立與 server 的連線，並返回 fd，傳入 ec->fd 中
- fcntl() : file control，對 fd 更改特性，fctrl(ec->fd, F_SETFL, O_NONBLOCK) 將 socket 的 fd 更改為非阻塞式，相比於阻塞式的方式，不會因為讀取不到資料就會停著
- connect() : 為系統呼叫，根據 socket 的 fd (ec->fd) 與 server 的 IP 地址連線，因為是 nonblocking 的型式，所以不會等待連線成功的時候才會返回，因此在未連線時會回傳一巨集 EAGAIN 表示未連線，所以將 connect() 在迴圈中執行到連線成功
- epoll_ctl() : 將連線成功的 socket (ec->fd)加入在 epoll 監聽事件(efd)中，所使用到 EPOLL_CTL_ADD 巨集加入監聽事件，並將 efd 事件設定為可寫的狀態，使用 EPOLLOUT

static void init_conn(int efd, struct econn *ec)
{
    int ret;

    // 建立連線
    ec->fd = socket(sss.ss_family, SOCK_STREAM, 0);
    ...

    // 設定 fd 控制權為 nonblock 形式
    fcntl(ec->fd, F_SETFL, O_NONBLOCK);

    // sys call 連線
    do {
        ret = connect(ec->fd, (struct sockaddr *) &sss, sssln);
    } while (ret && errno == EAGAIN);
    ...
    
    // 設定 epoll fd 的事件狀態，並指向 socket
    struct epoll_event evt = {
        .events = EPOLLOUT, .data.ptr = ec,
    };
    
    // 加入已完成連線的 socket 加入 epoll 監聽程序中
    if (epoll_ctl(efd, EPOLL_CTL_ADD, ec->fd, &evt)) {
        ...
    }
}

連線的初始化完成後，繼續看 worker() 處理 I/O 事件的無限 for-loop

epoll 監聽 :
- 進入無限的 for-loop 中處理所有的連線請求
  - 使用 epoll_wait 輪詢的方式將可用的 fd 儲存至 evts 陣列中
- 在 htstress.c 中 evts.event 表示事件狀態的巨集:
  - EPOLLIN : 表示對應 fd 可讀
  - EPOLLOUT : 表示對應 fd 可寫
  - EPOLLERR : 表示對應 fd 發生錯誤
  - EPOLLHUP : 表示對應 fd 被結束連線
epoll 的錯誤處理，以 if (evts[n].events & EPOLLERR){ ... } 判斷事件是否為錯誤狀態
- getsockopt() : 可以獲得 epoll 監聽 socket 的狀態，透過巨集 SO_ERROR 紀錄錯誤訊息(0 為沒有錯誤的產生)，看到宣告方式 if (getsockopt(efd, SOL_SOCKET, SO_ERROR, (void *) &error, &errlen) == 0)，讀取到 efd 的資料將檢查的結果寫入至 error 變數中
- atomic_fetch_add() : 使用到 atomic 的操作方式，紀錄錯誤產生的數量，確保在記錄錯誤數量的時候不會被多執行緒干擾(每個 socket 都有機會互相干擾程序，所以要確保計數的正確性)
- close() : 將有錯誤連線的 socket 連線關閉，避免系統的佔用

ISO/IEC 9899:2011 (P.283) : atomic_fetch function
These operations are atomic read-modify-write operations.

if (evts[n].events & EPOLLERR) {
    /* normally this should not happen */
    ...
    if (getsockopt(efd, SOL_SOCKET, SO_ERROR, (void *) &error, &errlen) == 0) {...}
    ...
    // 計數錯誤
    atomic_fetch_add(&socket_errors, 1);
    // 關閉有錯誤的 socket fd
    close(ec->fd);
    ...
    // 重新初始化連線
    init_conn(efd, ec);
}

client 傳送數據至 server :
- 事件狀態為 EPOLLOUT(表示可寫) : 先確認是事件的狀態為可寫，並確保連線的狀態是可用的，使用 send() 函式開啟要傳送資料的 fd，再來傳送資料(包含傳送的資料與長度，以檔案的 offset 表示)，傳送成功後會返回傳送資料的長度
- 若傳送有問題時，紀錄錯誤訊息(使用 write()，注意到 write 的第一個引數為 fd，這裡使用 2，參考文章解釋，0 表示 STDIN 標準輸入(鍵盤)，1 表示 STDOUT 標準輸出(終端機視窗)，2 表示 STDERR 標準錯誤輸出(將錯誤訊息輸出至終端機))
- 確認資料是否有完整傳送至 server，將事件改為 EPOLLIN 可讀的狀態，等待 server 傳送資料
server 傳送數據至 client :
- 事件狀態為 EPOLLIN，使用 recv() 得到從 server 傳送來的資料，從 socket 的 fd 獲得，將獲得的資料存入 buffer(inbuf) 中。
關閉 client 與 server 連線:
- 當處理完所有的通訊資料後(也就是 ret = 0) 時，使用 close() 關閉 client 的 fd(要關閉否則會占用資源)，這裡要注意的是在建立 epoll 監聽與 socket 連線，同時都要有對應的 close() 關閉其 fd，不過在 htstress.c 中沒有看到對 epoll 的 fd 進行 close() 的敘述。

來自 epoll_create man page 的敘述:
對應的 epoll_create() 要透過 close() 將 epoll fd 關閉，不過若 epoll 所監聽所有的 fd 已被關閉，kernel 就會直接釋放 epoll 的相關資源
When no longer required, the file descriptor returned by epoll_create() should be closed by using close(2). When all file descriptors referring to an epoll instance have been closed, the kernel destroys the instance and releases the associated resources for reuse.

// client 傳送訊息，確認事件狀態為可寫
if (evts[n].events & EPOLLOUT) {
    ret = send(ec->fd, outbuf + ec->offs, outbufsize - ec->offs, 0);
    ...

// 將錯誤訊息存入
if (debug & HTTP_REQUEST_DEBUG)
    write(2, outbuf + ec->offs, outbufsize - ec->offs);
    ...
        
/* write done? schedule read */
if (ec->offs == outbufsize) {
    evts[n].events = EPOLLIN;
    evts[n].data.ptr = ec;
    ...
        
// 事件可讀狀態
if (evts[n].events & EPOLLIN) {
    ...
    // 獲得從 server 傳來的資料
    ret = recv(ec->fd, inbuf, sizeof(inbuf), 0);           
    ...

// 所有請求處理結束
if (!ret) {
    // 關閉 socket 連線
    close(ec->fd);
    ...
}

kHTTPd 實作的缺失

recv error

編譯 kHTTPd 原始碼

$ cd khttpd
$ make

可以得到 htstress 執行檔與 khttpd.ko 核心模組，進行測試:

# ./htstress -n 1000 -c 1 -t 4 http://localhost:8081/
$ make check

對 google 網站進行測試

$ ./htstress -n 1000 -c 1 -t 4 http://www.google.com/

kHTTPd 掛載時可指定 port 號碼: (預設是 port=8081)

$ sudo insmod khttpd.ko port=1999

使用 wget 工具可得到 index.html 所得到的內容為: Hello World!

$ wget localhost:1999
http://localhost:1999/
正在查找主機 localhost (localhost)... 127.0.0.1
正在連接 localhost (localhost)|127.0.0.1|:1999... 連上了。
已送出 HTTP 要求，正在等候回應... 200 OK
長度: 12 [text/plain]
儲存到：`index.html.1'

利用 dmesg 查看可發現在 kernel 中出現了錯誤的訊息

[ 1817.693113] khttpd: module unloaded
[ 1929.381711] khttpd: requested_url = /
[ 1929.382944] khttpd: recv error: -104

由 errno.h 查詢到 #define ECONNRESET 104 表示 Connection reset by peer 一端的 socket 被關閉造成(主動關閉或是異常斷開)，而另一端繼續發送封包而導致，而這個問題來自於在連線時採取 keep-alive 機制，對 server 端不會造成影響，只會顯示出錯誤訊息

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;
    }

取消 keep-alive，參考到 HTTP Options 即可避免這種狀況

$ wget localhost:1999 --no-http-keep-alive

buffer 未歸零

看到 Risheng1128 同學提出的 pull request 他發現在 http_server.c 中的 http_server_worker() 函式，在處理到每一個 client 的連線時，將由 client 端所傳送到的資料放入 buf 中，但是每經過一次的連線處理時並沒有把 buf 內的資料歸零，很可能會導致資料的錯誤，包含在第一次 buf 經過 kmalloc 後並未初始化資料

將 buf 經過了連線後獲得的資使用 dmesg 查看就會發現以下的結果，buf 的資料有錯誤並不是我們所預期的 buf: GET / HTTP/1.1

[373881.087239] buf: GET / HTTP/1.1
[373881.735451] buf: 
                T / HTTP/1.1  /* error */

因此將增加初始化 buf 的程式碼如下:

- int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
+ int ret;
+ memset(buf, 0, RECV_BUFFER_SIZE);
+ ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);

重新執行後，可以得到正確的結果

[373881.087239] buf: GET / HTTP/1.1
[373881.735451] buf: GET / HTTP/1.1

在看到這則 commit 後，思考有沒有其他的方式改善，memset 使用在 http_server_recv() 之前，目的是要初始化 kmalloc 的資料，因此嘗試找有無其他的方式如 calloc() 的方式將一開始配置的記憶體就先做一次初始化的動作，而在 kernel 配置記憶體的函式中 kzalloc() 就有這樣的作用

kzalloc - allocate memory. The memory is set to zero.

更改為:

- buf = kmalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
+ buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
...
while (!kthread_should_stop()) {
-       int ret;
-       memset(buf, 0, RECV_BUFFER_SIZE);
-       ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
+       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;
+       memset(buf, 0, RECV_BUFFER_SIZE);    
    }

實測後的結果也能達到一樣的效果，避免到 buf 的資料錯誤。不過要思考到從 kmalloc() 轉變成使用 kzalloc() 後是否會影響到處理的速度，所以使用到 ktime 相關 API 測試花費的時間，分別測試 kmalloc() 、 kzalloc() 、memset() 所花費的時間，測出的時間為奈秒(ns)，在原程式碼中加入:

ktime_t kt;
kt = ktime_get();
buf = kmalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
kt = ktime_sub(ktime_get(), kt);
printk("kmalloc: %lld", ktime_to_ns(kt));

kt = ktime_get();
buf2 = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
kt = ktime_sub(ktime_get(), kt);
printk("kzalloc: %lld", ktime_to_ns(kt));
    
kt = ktime_get();
memset(buf, 0, RECV_BUFFER_SIZE); 
kt = ktime_sub(ktime_get(), kt);   
printk("memset: %lld", ktime_to_ns(kt));

編譯後，插入 khttpd.ko 核心模組，並使用 telnet localhost 8081 進行連線，測試兩次的連線，再用 dmesg 輸出結果得到:

[377464.512577] start
[377464.512580] kmalloc: 336
[377464.512581] kzalloc: 114
[377471.228783] memset: 450
[377472.052154] khttpd: requested_url = /
[377472.052220] memset: 460
[377598.501730] start
[377598.501750] kmalloc: 372
[377598.501751] kzalloc: 123
[377605.291851] memset: 501
[377605.444165] khttpd: requested_url = /

可以發現 kzalloc() 所花費的時間比 kmalloc() 、 memset() 還要短很多，而且這樣的執行順序可以將 memset() 放在判斷式後執行，若中途 client 端結束了連線，在判斷式中就會跳出連線的迴圈，減少 buf 再執行一次 memset() 過程，而面對一次更多的 client 連線請求可以減少更多的處理時間

TODO: 查看 kmalloc、 kzalloc man pages 或是相關文件，直觀推測來看 kzalloc 比起 kmalloc 所花的時間應該要比較多，但實測上並沒有

引入 CMWQ 至 khttp

參考了 kecho 的作法引用到 khttp 中

http_server.h
使用 http_service 管理 workqueue ，http_server 管理 work ，連接的方式都是採取 list_head 方式，將 work 、 workqueue 連接一起

// manage workqueue
struct http_service {
    bool is_stopped;
    struct list_head worker;
};

// manage work
struct http_server {
    struct socket *sock;
    struct list_head list;
    struct work_struct http_work;
};

http_server.c

宣告 workqueue ，並在使用 workqueue 相關 API 時 include workqueue.h

workqueue_struct 定義於 workqueue.c 中，裡面有 CMWQ 文件中所提及的 unbound_attrs 可以設定 workqueue 在 unbound 條件下的屬性;還有提到 struct worker *rescuer 為確保在釋放記憶體時不會產生 deadlock 的情形
alloc_workqueue 定義於 workqueue.c 中初始化一個 workqueue 並在 flag 的設定為 WQ_UNBOUND 表示不會被特定的 CPU 所限制，使資源不會被閒置，可以透過切換的方式執行未完成的任務
http_server_daemon() 為每一個連線的請求建立一個 work 進行處理(work = create_work(socket);)，而建立出來的 work 會由作業系統分配 worker 執行，配置後由 khttp_wq 將每一個 work 用 list_head 的 linked list 進行管理，使用到 queue_work() 將 work 放入 workqueue 中

#include <linux/workqueue.h>
struct http_service daemon = {.is_stopped = false};
struct workqueue_struct *khttp_wq;  // set up workqueue

int http_server_daemon(void *arg)
{
    ...
    struct work_struct *work;
    // CMWQ
    khttp_wq = alloc_workqueue("khttp_wq", WQ_UNBOUND, 0);/* workqueue.h API*/
    if (!khttp_wq)
        return -ENOMEM;
    // initial workqueue head 
    INIT_LIST_HEAD(&daemon.worker);
    
    while (!kthread_should_stop()) {
        ...
        // CMWQ
        work = create_work(socket);
        if (!work) {
            pr_err("can't create work\n");
            continue;
        }
        queue_work(khttp_wq, work);
    }
    daemon.is_stopped = true;
    return 0;
}

http_worker() : 建立新的 worker 透過 container_of 找到結構中的 struct work_struct http_work 建立 socket 連線任務與對應 worker 處理

static void http_worker(struct work_struct *work)
{
    struct http_server *worker =
        container_of(work, struct http_server, http_work);
    http_server_worker(worker->sock);
}

create_work():為每一個連線請求進行 kernel space (kmalloc) 的動態記憶體配置，並進行初始化，再透過 list_add 加入到 workqueue 中

// ref : kecho create_work
static struct work_struct *create_work(struct socket *sk)
{
    struct http_server *client;
    // GFP_KERNEL the flag of allocation
    // https://elixir.bootlin.com/linux/latest/source/include/linux/gfp.h#L341
    client = kmalloc(sizeof(struct http_server), GFP_KERNEL);

    if (!client)
        return NULL;

    client->sock = sk;

    INIT_WORK(&client->http_work, http_worker);
    list_add(&client->list, &daemon.worker);
    return &client->http_work;
}

free_work():用於釋放掉所建立連線的所分配的記憶體空間，使用 list_for_each_entry_safe 巨集走訪每一個在 workqueue 中所管理的 work
kernel_sock_shutdown(): 斷開 socket 的連線(包含傳送與接收的功能)，對應的巨集 SHUT_RDWR 關閉方式
flush_work():等待當前的的 work 執行完畢
sock_release(): 根據文件的註解，將 socket 釋放在 stack，也會斷開對應連接的 fd
kfree():釋放掉從 kmalloc 所配置出的記憶體空間

static void free_work(void)
{
    struct http_server *tmp, *target;
    // list : member
    list_for_each_entry_safe (target, tmp, &daemon.worker, list) {
        kernel_sock_shutdown(target->sock, SHUT_RDWR);
        flush_work(&target->http_work);
        sock_release(target->sock);
        kfree(target);
    }
}
int http_server_daemon(void *arg)
{
    ...
    // free work and workqueue
    free_work();
    destroy_workqueue(khttp_wq);
}

make check 後比較引入 CMWQ 後處理 100000 筆的請求很明顯看出在處理的速度上加快了很多，提升約有 4 倍的速度

origin:                             CMWQ: 
requests:      100000               requests:      100000
good requests: 100000 [100%]        good requests: 100000 [100%]
bad requests:  0 [0%]               bad requests:  0 [0%]
socker errors: 0 [0%]               socker errors: 0 [0%]
seconds:       3.252                seconds:       0.860
requests/sec:  30750.166            requests/sec:  116314.099

核心模組掛載機制

參照 Linux 核心模組掛載機制，在掛載核心時，對應到引數 port=1999 的設定方式

$ sudo insmod khttpd.ko port=1999

在執行掛載核心模組時，加入 strace 可以追蹤 insmod khttpd.ko port=1999 使用了甚麼系統呼叫

sudo strace insmod khttpd.ko port=1999

執行後的結果為下列所示:













execve("/usr/sbin/insmod", ["insmod", "khttpd.ko", "port=1999"], 0x7ffca946b440 /* 26 vars */) = 0
brk(NULL)                               = 0x562c0e74f000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffe0754e040) = -1 EINVAL (不適用的引數)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (沒有此一檔案或目錄)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=83155, ...}) = 0
...
...
finit_module(3, "port=1999", 0)         = 0
munmap(0x7f6eb0201000, 1368232)         = 0
close(3)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

可以看到第一行 execve() 為執行程式的系統呼叫，將輸入的命令執行

查看 execve(2) man page

#include <unistd.h>
int execve(const char *pathname, char *const argv[], char *const envp[]);

第一個引數為 : 執行引數的檔案路徑
第二個引數為 : 儲存引數字串的陣列指標，也就是分別將 "insmod" "khttpd.ko" "port=1999"] 這些命令存入

(argv is an array of pointers to strings passed to the new program as its command-line arguments.)

第三個引數為 : 傳送檔案執行新環境的地址
再來看到第 9 行中 finit_module(3, "port=1999", 0)，查看 finit_module man page finit_module() 實作方式，來源自 kernel/module.c

SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
    ...
	return load_module(&info, uargs, flags);
}

再繼續看到 load_module() 字串中的 "port=1999" 就是將 main.c 中的 port 引數 8081(default 值) 改為 1999，當中就是利用 strndup_user() 函式，把使用者的參數設定輸入進去
而再根據註解的意思透過此函式將模組(module)載入

/* Allocate and load the module: note that size of section 0 is always
   zero, and we rely on this for optional sections. */
static int load_module(struct load_info *info, const char __user *uargs,
		       int flags)
{
    ...
    /* Now copy in args */
	mod->args = strndup_user(uargs, ~0UL >> 1);
    ...
}

而 strndup_user() 被定義在 mm/util.c 中，根據註解的解釋將存在的字串複製，將使用者輸入的參數複製到指定字串中，類似的作法如 strncpy() 的方式

/*
 * strndup_user - duplicate an existing string from user space
 * @s: The string to duplicate
 * @n: Maximum number of bytes to copy, including the trailing NUL.
 */
char *strndup_user(const char __user *s, long n)
{
    ...
}

再回到參數設定中的 finit_module()

int finit_module(int fd, const char *param_values, int flags);

我們注意對第二個引數 param_values 中的敘述:
The param_values argument is a string containing space-delimited specifications of the values for module parameters (defined inside the module using module_param() and module_param_array()).
為由字串所存下參數的在模組資訊，實際定義在 module_param() 中

在 Linux kernel 中設定參數必須藉助 module_param() 巨集完成，詳細定義於 linux/moduleparam.h

/**
 * module_param_named - typesafe helper for a renamed module/cmdline parameter
 * @name: a valid C identifier which is the parameter name.
 * @type: the type of the parameter
 * @perm: visibility in sysfs.
 * ...
 */
#define module_param(name, type, perm)				\
	module_param_named(name, name, type, perm)

參數說明:
- name 為傳入變數名稱，以專案舉例傳入 port 的變數作為設定
- type 為傳入變數之變數宣告，以專案舉例傳入 ushort (typedef unsigned short int)
- perm 為存取 sysfs 的權限，以專案舉例設定參數為 S_IRUGO (為 stat.h 中的巨集)

S_IRUGO 巨集，表示可被所有人進行讀取(不能寫)，巨集定義參考
#define S_IRUGO (S_IRUSR|S_IRGRP|S_IROTH)
其中有三個變數分別定義為 00400 00040 00004 ，其 4 表示權限為讀取
S_IRUSR 為允許擁有者、S_IRGRP 為允許擁有者群組、S_IROTH 為允許其他使用者

參數設定完後，可以看到 insmod 命令動態載入一個核心模組，會辨認到 module_init() 的系統呼叫，初始化函式，以本例的 main.c 中:

module_init(khttpd_init); /* khttpd_init 自定義函式 */

參考 include/linux/module.h 的函式說明

/* Each module must use one module_init(). */
#define module_init(initfn)					\
	static inline initcall_t __maybe_unused __inittest(void)		\
	{ return initfn; }					\
	int init_module(void) __attribute__((alias(#initfn)));

看到一開始的敘述 static inline ... ，裡面的 __maybe_unused 巨集可展開為 __attribute__((unused)) 表示該函式可能是未使用的，因此 GCC 不會為此函式產生警告

參考 What is "__maybe_unused"?

linux/init.h 中 initcall_t 宣告 typedef int (*initcall_t)(void) 為函式指標，透過 __inittest(void) 判斷傳入的函式是否合法(需要與 initcall_t 型態一樣)不然編譯器會報錯，得以回傳 initfn (khttpd_init())
參考 GCC手冊 對於 __attribute__((alias(#initfn))) 解釋:

alias ("target")
用於宣告不同名稱("別名")，以本例來說宣告 #initfn 的函式名稱，而透過前置處理器的展開可以得知， initfn 就是 khttpd_init() 注意到 # 的使用為 Stringizing 字串化，於前置處理器篇有提到
The alias attribute causes the declaration to be emitted as an alias for another symbol, which must have been previously declared with the same type, and for variables, also the same size and alignment.

再來看到 init_module()，insmod 會呼叫到此系統呼叫的函式，藉此將自定義的函式載入至 kernel space 中

init_module man page
init_module() loads an ELF image into kernel space, performs any necessary symbol relocations, initializes module parameters to values provided by the caller,…

Web 伺服器流程

講解在 CS:APP 第 11 章 web 伺服器流程，參考到課程的講義的架構圖:

基本的 Client-Server 運作概念:
1. client 發送一個連線請求
2. server 接收到請求後，再根據 server 本身的資源處理相對應請求
3. server 回應(回傳相關資訊)
4. client 獲得從 server 回傳的結果

再來看到細部的運作流程，左半部分為 client，右半部分為 server

在 client 與 server 先透過 getaddrinfo() 啟用程序，回傳值為 struct addrinfo 的結構，裡面就含有連線所需要的資料，如:IP 位址、 port (通訊埠)、 server 名稱…等等
再來 client 與 server 呼叫(call) socket() 建立連接，回傳值為 file descriptor ，注意只有建立連結但不會操作系統，也不會往網路上傳送任何內容

socket man page
socket() creates an endpoint for communication and returns a file descriptor that refers to that endpoint.

server 使用 bind() 函式將 socket 與特定的 IP 位址和 port 連接起來(在 kernel space 中進行)
server 開啟監聽狀態，呼叫 listen() ，準備接受來自 client 的請求
server 就可以使用 accept() 將 client 連接
而 client 使用 connect() 發送 Connection request 等待 server accept
成功取得連線後，client 與 server 就可以進行通訊，使用 read 、 write 的方式(rio, reliable I/O，一部分來自 Unix I/O 系統，可用於讀寫 rom 並處理一些底層 I/O 的操作)
當 client 結束連線，會發送結束連線的請求(EOF, End of file)，server 獲得此訊息後結束對 client 的連線。
結束一個 client 的連線後，server 可以再接續下一個 client 的連線或是關閉整個 server

此流程只能用於單一的 server/client 的連線，依照需求適用於小型連線系統，如:路由器內部系統設定

在 CS:APP 第 12 章(並行程式設計)中，有提到接收多個 client 的連線方式，與 khttpd 的方式相近，架構圖:

來源 : 課程錄影

server 開啟監聽過程，當有任何一個 client 請求連線時，server 就會 fork 行程去處理到對應的 client ，所以在處理的過程中，子行程只要對應 client 就好，不會干涉到其他子行程的運作(Address space 獨立)，能完成多 client 的連線需求。

以 server 的角度就是持續的接受連線的請求

講解 `htstress.c` 用到 `epoll` 系統呼叫

首先看到 I/O 事件的模型為:

在 user space 中使用到 select 的系統呼叫，同時間監聽多個 fd(file descriptor)，但是有一定的數量限制，相比於 epoll 是沒有監聽的數量限制

select() can monitor only file descriptors numbers that are less than FD_SETSIZE (1024)
epoll API : monitoring multiple file descriptors to see if I/O is possible on any of them.

因此在 user space 透過 epoll_wait 系統呼叫後，經過 mode transition，開始在核心中監聽，透過監聽的時間決定(參數 timeout 決定)，注意到在 htstress.c 的設定為 -1，epoll_wait 會保持 blocking 的方式直到任一個 I/O 事件變為就緒，就緒後會切回 user space 中，而在回傳的數值為監聽到的事件數量(epoll_wait() returns the number of file descriptors ready for the requested I/O)，根據數量來做對應的處理。
另外使用到其他 epoll 函式:
- epoll_ctl : 對建立出的 epollfd 進行添加、修改或刪除對 fd 上事件的監聽，分別有三個巨集 EPOLL_CTL_ADD 、 EPOLL_CTL_MOD 、 EPOLL_CTL_DEL
- epoll_create : 建立一個 epoll 並返回一個 epollfd
epoll 中的監聽機制:
- Level-triggered: epoll 不進行設定的話會採取的作法，當一有事件觸發，將會把特定的電位狀態從 0 改至 1 ，在 CPU 發出命令停止前都會保持同一個狀態，也就是會不斷持續接收來自 client 連線請求，直到緩衝區的空間為空，不需要一直返回。
- Edge-triggered:當有事件觸發時發出一個脈衝表示中斷請求，在過程中不能被其他的 I/O 事件所打斷，處理一個請求後才能再處理下一個事件，每接受一次就會通知系統一次

理解相關背景知識

HTTP 1.1 的 keep-alive 實作機制

參考: Http 文章

HTTP 1.0

HTTP 協定(HyperText Transfer Protocol，超文本傳輸協定)，其中在 1996 年發布了 Http 1.0 的版本，規定 client 和 server 保持短暫的連線，而 client 每次的請求都需要與 server 建立一個 TCP 的連線，但是在 server 處理完 client 一次的請求後即關閉 TCP 的連線，server 不會留下任何紀錄。

造成問題:
- 無法重複連線
- 每一次傳送請求都需要再連線一次 TCP，過程中連線與釋放的成本高
- 隊頭阻塞(head of line blocking): 1.0 版本中規定下一個請求必須在前一個請求響應之前才能傳送，若前一個請求沒有到達 server，導致下一個請求無法傳送，而使下一個請求阻塞。

HTTP 1.1

於 1999 年發布 HTTP 1.1 版本，改善了 HTTP 1.0 的效能問題，在 HTTP 1.1 中增加 Connection 欄位可設定 Keep-Alive 保持與 HTTP 連線不中斷，避免每次的請求要重複建立 TCP 的連線(1.0 版本預設沒有 Keep-Alive，1.1 版本預設有)

來源

Keep-Alive 模式:
優點 : Keep-Alive 模式更加高效，因為避免了建立和釋放的過程
缺點 : 長時間的 TCP 連線容易導致系統資源無效佔用，浪費系統資源

在長連線的情況下要如何判斷一次的請求完成方式
- Context Length(實體內容的長度) : client 透過這個欄位判斷當前請求的資料是否已經全部接收，用於請求靜態資源的時候，server 能明確知道返回內容的長度，但若是 server 不知道請求結果的長度時(動態資源，如一動態頁面/資料)，Context Length 就無法作用
- Transfer-Encoding(傳輸編碼) : chunked 告知 client 當前的編碼是一塊一塊的，所以當 client 接收到一塊長度為 0 的 chunked 時即得知請求內容已全部接收。

使用 telnet 對 www.google.com 發送請求

$ telnet www.google.com 80
Trying 2404:6800:4012::2004...
Connected to www.google.com.
Escape character is '^]'.
GET / HTTP/1.1
Host: www.google.com

回應:

HTTP/1.1 200 OK  // 200 表示連線成功
Date: Tue, 31 May 2022 03:49:55 GMT
...
Server: gws
...
Transfer-Encoding: chunked

Keep-Alive timeout 機制:
為 HTTP 的守護機制，提供 Keep-Alive timeout 時間設定引數，表示一個 http 所產生的 tcp 連線在完成最後一個響應後，還需要持續 timeout 的時間，才會開始關閉這個連線。確保 client 是否還請求傳送到 server

TCP handshake

參考文章 : Tcp-3-way-handshake-process

為 TCP 傳輸中建立連線傳送的方式，又稱三向交握

過程中有三個重要的步驟:
1. client 傳送同步封包(SYN，Synchronize Sequence Number)給 server 準備建立起連線，client 隨機選取初始序號 1(Seq1)，封包內的 flags 中的 Synchronize 位元會被設定成 1 表示送出 SYN 資訊，(注意:同步傳輸的意思是指，傳送端在傳送出封包後，會等待接受端的確認，在傳送下一個封包，而不是直接將封包不斷地傳送出去)
2. 當 server 收到後回傳 SYN2 + ACK1(Acknowledgement)，server 隨機選取的初始序號 2(Seq2)，Acknowledge Number 為第一階段 client 的序號 Seq1 + 1，主要用來告知收到了 SYN1 這個封包，將 TCP 的 flags 中的 Synchronize 與 Ackownledge 位元設定 1
3. client 收到了來自 server 傳送的 SYN2 + ACK1 封包後，回傳 ACK2 的封包，裡面的 Sequence Number 為 Seq1 + 1 與 ACK2 一樣，表示告訴 server 已經收到了 SYN2 封包，在 TCP 封包 flags 中 Acknowledge 位元設為 1
4. 經過上述三個步驟，表示連線成功，即可以開始互相傳送資料，若其中一步遺失則整個步驟都要重新來過

與 UDP 相比不需要這些步驟，沒有連線要求、連線終止或是流量控制的管理程序，優點在於傳輸速率較快，主要應用少量、即時性的傳輸，資料的正確性要求不高(語音或視訊)，相對的在傳輸過程可能會有資料重覆、資料未依序到達、資料遺失等等問題

Ethernet 的 frame 大小及範圍

參考 IEEE 802.3 CSMA/CD 網路簡介

Ethernet(乙太網路) 是由 Intel 、 Xerox 和 Digital 所共同制定，遵循 IEEE 802.3 協定的網路硬體標準，也是大部分區域網路的標準，其中在有線連接的情況使用 CSMA/CD (Carrier Sense Multiple Access with Collision Detection，載波偵聽多路存取)的通訊協定，無線連接的情況使用 CSMA/CA (Collision Avoidance)通訊協定

CSMA/CD(以網路匯流排(BUS)架構舉例)，包含期以下幾項特性

訊框(frame)格式 IEEE 802.3 CSMA/CD frame
傳輸媒介可為同軸電纜(Coaxial cable)、無遮蔽式雙絞線(UTP)、或光纖(Fiber)
以廣播式傳播(Broadcasting)，工作站將訊號送上傳輸媒介廣播至每個工作站，frame 會有廣播性質
若有兩個或兩個工作站同時傳送 frame 會造成碰撞(Collision)，而發生碰撞的 frame 無法有效的辨認，因此會被視為無效的 frame 而丟棄，解決方式有:
- CS(Carrier Sense)用來偵測集線器的匯流排中是否有資料在傳輸(無法偵測到已同時傳輸的碰撞)
- CD(Collision Detection)偵測機制(CS 沒有作用時)，當 CD 偵測到碰撞快要發生前，會發出一個 JAM(Jamming Signal，擾亂訊號)的訊號，告訴所有工作站，網路已發生碰撞現象，停止傳送訊號，再使用到後退演算法(backoff algorithm)，計算出一個隨機的時間，將兩台電腦下次送出的時間錯開

frame 格式(IEEE 802.3 的 MAC-frame)，分別包含:
- Preamble: 包含 7 個位元組(101010…1010)，主要的目的是達到接收的同步功能(synchronization)
- SFD(Start Frame Delimiter): 1 個位元組，表示 frame 的開始
- DA(Destination Address): 2 個或 6 個位元組，目的地工作站位址(MAC)，表示 frame 要送到哪一個工作站
- SA(Source Address): 2 個或 6 個位元組，原始工作站的位址(MAC)，表示 frame 由哪個工作站送出
- Length: 2 個位元組，紀錄 LLC (Logical Link Control) 的長度
- LLC: 主要工作是控制訊號的交換，控制資料的流量，解釋上層通訊協定傳來的命令並且產生回應，以及克服資料在傳送的過程當中所可能發生的種種問題，不同工作站之網路層通訊協定可透過 LLC 來溝通，最長為 1500 位元組，(參考文章)
- PAD(Padding): 當 LLC 的 frame 長度小於 46 位元組時，利用此填塞欄位將 LLC 的 frame 填補位元組，填補的位元組沒有特別的意義，可為任意值
- FCS(Frame Check Sequence): 4 個位元組，紀錄 frame 的檢查碼，採用 CRC-32 技術，檢查 frame 內的資料使否發生錯誤

frame 的大小為 DA 到 FCS 間的位元組數目，而一個 frame 長度必須大於或等於 64 位元組，主要是要能夠再傳送完畢之前偵測衝撞(Collison)，每一個工作站的監聽時間為 1 個時槽時間(51.2微秒，以實際上元件處理的時間為 46.38 微秒，考慮到 2 的冪次方處理上的方便)

網路的傳輸速度為 10 Mbps，所以在一個時槽的時間內可以傳送:
$10^{7} \times 51.2 \times 10^{- 6} = 512 b i t s = 64 b y t e s$

所以每一個 frame 必須大於或等於 64 位元組，否則在 frame 可能在衝撞尚未偵測出來之前被傳送完畢，傳送的結果是成功還是失敗無法確定，在 PAD 欄位是當 LLC 的長度不夠時用來增加長度，DA(6) + SA(6) + Length(2) + FCS(4) = 18 位元組，所以 LLC + PAD(LLC 長度不夠才需要補) 的長度要大於等於 64 - 18 = 46 位元組，而為了避免某一個工作站佔用傳輸媒介太久，每一筆 frame 的最大長度也受到限制，為 1518 位元組(LLC 1500 位元組 + 18 位元組)，不含 Preamble 和 SFD 欄位

packet loss 的處置方式

Packet loss 為通訊傳輸中無法將資料封包傳送到指定的位址，常見造成的情況有:
1. 壅塞問題(Network Congestion): 為網路傳輸中因為延遲或是網路的頻寬無法負荷時，導致封包的遺失。解決方式:壅塞控制(Congestion Control)，增加頻寬、改變傳輸路線的權重，使能避開壅塞線路、控制封包數量減輕負載，拒絕新的連接、若策略無法成功則將封包丟棄
2. 實體傳輸纜線缺陷: 在有線連接傳輸中，實體的傳輸線有缺陷導致傳輸失敗
3. 網路攻擊(Network Attack): 如: DDoS 攻擊(Distributed Denial-of-Service attack)，透過大量的封包造成網路的阻塞，導致封包遺失

參照 TCP 協定 RFC 793 page.40
Because segments may be lost due to errors(checksum test failure), or network congestion, TCP uses retransmission (after a timeout) to ensure delivery of every segment.Duplicate segments may arrive due to network or TCP retransmission.

TCP 超時重傳是保證資料可靠度的機制，當傳送一個數據後開啟計時器，若在一定的時間內沒有傳送資料回報的 ACK(三向交握的確認文)，就會在重新發送一次資料直到傳送成功，重傳機制一般會在超時之後，傳送端收到 3 個以上的 ACK 則要得知有 packet loss 的狀況需要重新傳遞，不需要等待計時器，為快速重傳。

理解 OSI 中的 Layer2 (Data Link Layer)

為資料連接層，介於 OSI 實體層(第一層)與網路層(第三層)之間，傳輸中的最小單位為 frame 可在同一個區域網路中的設備進行傳輸與接收，其中包含錯誤偵測、網路資料連線等等。可以使用橋接器(Network Bridge) 連接 LAN 的分段區域，創建單獨的廣播區域從而創建 VLAN，為一個獨立的邏輯網路，將設備獨立於 LAN 的物理位置，若無橋接和 VLAN，以乙太網路特性會廣播到所有的設備中，使所有的設備都要檢測 LAN 上的所有封包。

第二層中包含兩個子層:

邏輯連接控制(LLC):負責管理通信連接和處理 frame 資料
媒體存取控制(MAC):用於管理對物理網路的通訊協定存取權，透過分配給交換器上所有埠的 MAC 地址(實體地址)，在相同物體連接到多設備可以互相的辨認

來源

CMWQ (Concurrency Managed Workqueue)介紹

簡介

Linux 中含有 Workqueue 的機制，使用 struct list_head 將要處理的每一個任務連接，依次取出處理，處理結束的在從 queue 中刪除，目的是要簡化執行續的建立，可以根據當前系統的 CPU 個數建立執行緒，使得並行化執行緒。

Workqueue 有兩種方式:

Multi Thread:每一個 CPU 有一個 worker，而 worker 的數量會等於 CPU 的個數，而 worker 之間是相互獨立的，若出現 I/O blocking 的情況，其他 worker 可能會因為這個 blocking 而導致只能等待
Single Thread:整個系統中只有一個 worker，等待前面一個任務執行完後才能執行下一個任務，若出現 A 、 B 兩個任務，B 需要 A任務的執行結果，但是 B 先於 A 執行就會造成 DeadLock

在 Multi Thread 方式下會造成系統資源上的浪費，更別說 Single Thread 的影響，而並行的效果也有限，所以進行對 Workqueue 的改善(CMWQ)，有以下三個目標:

維持原始 Workqueue 的 API 的相容性
將每個 CPU 統一所有的 Worker pools 並按照不同層級的並行等級執行，減少資源的浪費
自動調整 worker pool 和並行等級，使 API 的使用者不需要擔心裡面的細節

worker pool 管理每個 worker
workqueue 連接所有的 work 所形成的 queue

CMWQ 架構圖:

設計方式

引入了 work item 的概念，為一個簡單的結構包含函式指標指向非同步任務運作的函式，執行時創建一個 work item 和(放入) workqueue。而處理這些任務的執行緒為 worker threads 用於一個接一個處理這些任務，而在任務結束後 thread 會變為 idle 狀態，而 worker-pools 就是用來管理這些 threads

兩種 worker-pools 類型:

Bound 類型:綁定特定的 CPU，使管理的 worker 執行在指定的 CPU 上執行，而每個 CPU 中會有兩個 worker-pools 一個為高優先級的，另一個給普通優先級的，透過不同的 flags 影響 workqueue 的執行優先度
Unbound 類型:thread pool 用於處理不綁定特定 CPU，其 thread pool 是動態變化，透過設定 workqueue 的屬性創建對應的 worker-pools

CMWQ 優勢

拆開 workqueue 與 worker-pools，可單純地將 work 放入 queue 中不必在意如何分配 worker 去執行，根據設定的 flags 決定如何分配，適時的做切換，減少 worker 的 idle 情況，讓系統使用率提升
若任務長時間佔用系統資源(或是有 blocking 的情況產生)，CMWQ 會動態建立新的執行緒並分配給其他的 CPU 執行，避免過多的執行緒產生
使不同的任務之間能被更彈性的執行(所有的 workqueue 共享)，會根據不同的優先級執行

將 create_workqueue 改以 alloc_workqueue

引入 alloc_workqueue 來自這則 commit 中提到 workqueue 有很多的功能存在，皆是利用參數去調控，在調整上可利用 flag 各式巨集去新增功能(如:WQ_UNBOUND 、 WQ_DFL_ACTIVE)

引用自原文:
Now that workqueue is more featureful, there should be a public workqueue creation function which takes paramters to control them. Rename _create_workqueue() to alloc_workqueue() and make 0 max_active mean WQ_DFL_ACTIVE. In the long run, all create_workqueue*() will be converted over to alloc_workqueue().

#define create_workqueue(name)					\
-	__create_workqueue((name), WQ_RESCUER, 1)
+	alloc_workqueue((name), WQ_RESCUER, 1)

可以看到在這則之前的 commit 建立一個 real time 的 workqueue 在 __create_workqueue 巨集中要更改到整個函式的 prototype，而使用到此巨集的的函式皆要跟著改動所有的函式宣告配合巨集，在新增功能的時候會花費大量時間去改動相關的函式，舉例:

-#define __create_workqueue(name, singlethread, freezeable)	\
+#define __create_workqueue(name, singlethread, freezeable, rt)	\

-#define create_workqueue(name) __create_workqueue((name), 0, 0)
+#define create_workqueue(name) __create_workqueue((name), 0, 0, 0)

更改後相關的 workqueue 實作以新增巨集或是修改巨集為主要方向，在未來有更多的想法上都是透過這樣的方式，如:
workqueue: remove WQ_SINGLE_CPU and use WQ_UNBOUND instead

-	WQ_SINGLE_CPU		= 1 << 1, /* only single cpu at a time */
+	WQ_UNBOUND		= 1 << 1, /* not bound to any cpu */
-	WQ_UNBOUND		= 1 << 6, /* not bound to any cpu */

自我檢查清單

參照 Linux 核心模組掛載機制，解釋 $ sudo insmod khttpd.ko port=1999 這命令是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？

過程參考你所不知道的 C 語言：連結器和執行檔資訊
參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？
htstress.c 用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？
理解相關背景知識:
- HTTP 1.1 的 keep-alive 實作機制
- 解釋 TCP handshake
- Ethernet 的 frame 大小及範圍
- packet loss 的處置方式
- 理解 OSI 中的 Layer2(Data Link layer)
給定的 kecho 已使用 CMWQ，請陳述其優勢和用法
核心文件 Concurrency Managed Workqueue (cmwq) 提到 “The original create_*workqueue() functions are deprecated and scheduled for removal”，請參閱 Linux 核心的 git log (不要用 Google 搜尋!)，揣摩 Linux 核心開發者的考量
解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用
是否理解 bench 原理，能否比較 kecho 和 user-echo-server 表現？佐以製圖
解釋 drop-tcp-socket 核心模組運作原理。TIME-WAIT sockets 又是什麼？

參考文章

Jim Huang

2022/06/06 04:19:03

參考: [Http 文章](https://www.cloudflare.com/zh-tw/learning/ddos/glossary/hypertext-transfer-protocol-http/) -

避免參照「農場」，儘量看權威材料 (這個領域的先行者)，例如: https://www.cloudflare.com/zh-tw/learning/performance/what-is-http3/ (Edited)

YiChianLin

2022/06/06 04:58:49

好的，學生會再多注意 (Edited)

2022/06/18 04:32:47

直觀推測來看 kzalloc 比起 kmalloc 所花的時間應該要比較多，但實測上並沒有

你需要理解 slab 的原理，才能解釋這現象 (Edited)

2022/06/18 04:33:06

請提交 pull request! (Edited)