# [2022 Homework 7]()

contributed by <shawn5141>

## 自我檢查清單

- [x] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 參照 [Linux 核心模組掛載機制](https://hackmd.io/@sysprog/linux-kernel-module)，解釋 `$ sudo insmod khttpd.ko port=1999` 這命令是如何讓 `port=1999` 傳遞到核心，作為核心模組初始化的參數呢？

> 過程中也會參照到 [你所不知道的 C 語言：連結器和執行檔資訊](https://hackmd.io/@sysprog/c-linker-loader)

- [ ] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 參照 [CS:APP 第 11 章](https://hackmd.io/s/ByPlLNaTG)，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？
- [ ] <input class="task-list-item-checkbox" disabled="" type="checkbox">`htstress.c` 用到 [epoll](http://man7.org/linux/man-pages/man7/epoll.7.html) 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？
- [x] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 給定的 `kecho` 已使用 CMWQ，請陳述其優勢和用法
- [ ] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 核心文件 [Concurrency Managed Workqueue (cmwq)](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) 提到 “The original create_`*`workqueue() functions are deprecated and scheduled for removal”，請參閱 Linux 核心的 git log (不要用 Google 搜尋!)，揣摩 Linux 核心開發者的考量
- [x] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 解釋 `user-echo-server` 運作原理，特別是 [epoll](http://man7.org/linux/man-pages/man7/epoll.7.html) 系統呼叫的使用
- [x] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 是否理解 `bench` 原理，能否比較 `kecho` 和 `user-echo-server` 表現？佐以製圖
- [ ] <input class="task-list-item-checkbox" disabled="" type="checkbox"> 解釋 `drop-tcp-socket` 核心模組運作原理。`TIME-WAIT` sockets 又是什麼？

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

####

透過 insmod 這個程式（可執行檔）來將 kecho.ko 植入核心中。因為 insmod 會呼叫相關管理記憶體的 system call，將在 user space 中 kernel module 的資料複製到 kernel space 中。[finit_module](https://elixir.bootlin.com/linux/latest/source/kernel/module.c#L4189) 就是所謂的system call。

以下為 執行 `sudo strace insmod kecho.ko port=1999` 的部分結果，可看到 port 1999 被當作參數傳入 `finit_module` 中。

openat(AT_FDCWD, "/home/shawn/linux2022/hw7/kecho/kecho.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6)               = 6
lseek(3, 0, SEEK_SET)                   = 0
fstat(3, {st_mode=S_IFREG|0664, st_size=13096, ...}) = 0
mmap(NULL, 13096, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f80a355c000
finit_module(3, "port=1999", 0)         = 0                 = 0

但要如何讓這個參數(port=1999)實際被讀到呢？ 參考 [The Linux Kernel Module Programming Guide - 4.5 Passing Command Line Arguments to a Module](https://sysprog21.github.io/lkmpg/#:~:text=module_exit(cleanup_hello_4)%3B-,4.5%20Passing%20Command%20Line%20Arguments%20to%20a%20Module,The%20example%20code%20should%20clear%20up%20my%20admittedly%20lousy%20explanation.,-The%20module_param()%20macro)，可以知道需要設定 `module_param` 與對應的參數。而我們的確在 `kecho_mod.c` 中找到 `module_param` 這個參數，而 `port` 就在其中。

/* module_param(foo, int, 0000) 
 * The first param is the parameters name. 
 * The second param is its data type. 
 * The final argument is the permissions bits, 
 * for exposing parameters in sysfs (if non-zero) at a later stage. 
 */ 
module_param(port, ushort, S_IRUGO);
module_param(backlog, ushort, S_IRUGO);
module_param(bench, bool, S_IRUGO);

而 `module_param` 定義在 [include/linux/moduleparam.h](https://elixir.bootlin.com/linux/latest/source/include/linux/moduleparam.h#L102)。
- module_param

#define module_param(name, type, perm)				\
module_param_named(name, name, type, perm)

- module_param_named

/**
 * module_param_named - typesafe helper for a renamed module/cmdline parameter
 * @name: a valid C identifier which is the parameter name.
 * @value: the actual lvalue to alter.
 * @type: the type of the parameter
 * @perm: visibility in sysfs.
 *
 * Usually it's a good idea to have variable names and user-exposed names the
 * same, but that's harder if the variable must be non-static or is inside a
 * structure.  This allows exposure under a different name.
 */
#define module_param_named(name, value, type, perm)			   \
	param_check_##type(name, &(value));				   \
	module_param_cb(name, &param_ops_##type, &value, perm);		   \
	__MODULE_PARM_TYPE(name, #type)

- param_check_##type: 在preprocess之後，會替換成像是 param_check_int， 而此function 底下包著是`__param_check`，會執行 compile-time type checking

__param_check(name, p, type)
    
#define __param_check(name, p, type) \
	static inline type __always_unused *__check_##name(void) { return(p); }
    

- module_param_cb 和 __module_param_call

/**
 * module_param_cb - general callback for a module/cmdline parameter
 * @name: a valid C identifier which is the parameter name.
 * @ops: the set & get operations for this parameter.
 * @arg: args for @ops
 * @perm: visibility in sysfs.
 *
 * The ops can have NULL set or get functions.
 */
#define module_param_cb(name, ops, arg, perm)				      \
	__module_param_call(MODULE_PARAM_PREFIX, name, ops, arg, perm, -1, 0)


/* This is the fundamental function for registering boot/module
   parameters. */
#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 __section("__param")					\
	__aligned(__alignof__(struct kernel_param))			\
	= { __param_str_##name, THIS_MODULE, ops,			\
	    VERIFY_OCTAL_PERMISSIONS(perm), level, flags, { arg } }

只要是產生 `kernel_param` object

 struct kernel_param {
    const char *name;
    const struct kernel_param_ops *ops;
    u16 perm;
    s16 level;
    union {
      void *arg;
      const struct kparam_string *str;
      const struct kparam_array *arr;
  };
};

`__section("__param")` 透過 GCC extension 的 [__aribute__((__section__(name)))](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124982450.htm#:~:text=9.65%20__attribute__((section(%22name%22)))%20variable%20attribute) 會把 data 放到 `__param` 的 位置。

>Normally, the ARM compiler places the objects it generates in sections like .data and .bss. However, you might require additional data sections or you might want a variable to appear in a special section, for example, to map to special hardware.
If you use the section attribute, read-only variables are placed in RO data sections, read-write variables are placed in RW data sections unless you use the zero_init attribute. In this case, the variable is placed in a ZI section.

### 參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？

### htstress.c 用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？

### 給定的 kecho 已使用 CMWQ，請陳述其優勢和用法

<details>
<summary><a href="https://kernel.meizu.com/linux-workqueue.html">Work Queue 簡介 </a>
</summary>

####
- work: 工作。
- work_queuem: 工作的集合。workqueue 和 work 是一对多的关系。
- worker: 工人，每个执行 work 的线程叫做 worker。在代码中 worker 对应一个 work_thread() 内核线程。
- worker_pool: 工人的集合。worker_pool 和 worker 是一对多的关系。CMWQ 对 worker_pool 分成两类：
- normal worker_pool，给通用的 workqueue 使用
> 大部分的 work 都是通过 normal worker_pool 来执行的 ( 例如通过 schedule_work()、schedule_work_on() 压入到系统 workqueue(system_wq) 中的 work)，最后都是通过 normal worker_pool 中的 worker 来执行的。这些 worker 是和某个 CPU 绑定的，work 一旦被 worker 开始执行，都是一直运行到某个 CPU 上的不会切换 CPU。
- unbound worker_pool，给 WQ_UNBOUND 类型的的 workqueue 使用
> unbound worker_pool 相对应的意思，就是 worker 可以在多个 CPU 上调度的。但是他其实也是绑定的，只不过它绑定的单位不是 CPU 而是 node。所谓的 node 是对 NUMA(Non Uniform Memory Access Architecture) 系统来说的，NUMA 可能存在多个 node，每个 node 可能包含一个或者多个 CPU。
- pwq(pool_workqueue): 中间人 / 中介，负责建立起 workqueue 和 worker_pool 之间的关系。
> workqueue 和 pwq 是一对多的关系，pwq 和 worker_pool 是一对一的关系。

最终的目的还是把 work( 工作 ) 传递给 worker( 工人 ) 去执行，中间的数据结构和各种关系目的是把这件事组织的更加清晰高效。

#### worker_pool 动态管理 worker
worker_pool 怎么来动态增减 worker，这部分的算法是 CMWQ 的核心。其思想如下：

- worker_pool 中的 worker 有 3 种状态：idle、running、suspend；
- 如果 worker_pool 中有 work 需要处理，保持至少一个 running worker 来处理；
- running worker 在处理 work 的过程中进入了阻塞 suspend 状态，为了保持其他 work 的执行，需要唤醒新的 idle worker 来处理 work；
- 如果有 work 需要执行且 running worker 大于 1 个，会让多余的 running worker 进入 idle 状态；
- 如果没有 work 需要执行，会让所有 worker 进入 idle 状态；
- 如果创建的 worker 过多，destroy_worker 在 300s(IDLE_WORKER_TIMEOUT) 时间内没有再次运行的 idle worker。

<details>
<summary>影片： <a href="https://www.youtube.com/watch?v=Ht6AK_6dTRE">9. Workqueues in Linux | Bottom Half </a>
</summary>
</details>

</details>

#### Concurrency Managed Workqueue (cmwq)
cmwq is a reimplementation of wq with focus on the following goals.

- Maintain compatibility with the original workqueue API.
- Use per-CPU unified worker pools shared by all wq to provide flexible level of concurrency on demand without wasting a lot of resource.
- Automatically regulate worker pool and level of concurrency so that the API users don’t need to worry about such details.

### 參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？

### 解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用

#### Prerequisite:
1.
<details>
<summary>節錄部分 <a href="http://shihyu.github.io/books/ch37.html">Linux系統編程-Socket</a> 的內容，提供對於socket API更加深入的認識。
</summary>


- int socket(int family, int type, int protocol);
> socket()打開一個網絡通訊連接埠，如果成功的話，就像open()一樣返回一個檔案描述符，應用程序可以像讀寫檔案一樣用read/write在網絡上收發數據，如果socket()調用出錯則返回-1。對於IPv4，family參數指定為AF_INET。對於TCP協議，type參數指定為SOCK_STREAM，表示面向流的傳輸協議。如果是UDP協議，則type參數指定為SOCK_DGRAM，表示面向數據報的傳輸協議。protocol參數的介紹從略，指定為0即可。\

- int bind(int sockfd, const struct sockaddr *myaddr, socklen_t addrlen);
> 伺服器程序所監聽的網絡地址和連接埠號通常是固定不變的，客戶端程序得知伺服器程序的地址和連接埠號後就可以向伺服器發起連接，因此伺服器需要調用bind綁定一個固定的網絡地址和連接埠號。bind()成功返回0，失敗返回-1。

> bind()的作用是將參數sockfd和myaddr綁定在一起，使sockfd這個用於網絡通訊的檔案描述符監聽myaddr所描述的地址和連接埠號。前面講過，struct sockaddr *是一個通用指針類型，myaddr參數實際上可以接受多種協議的sockaddr結構體，而它們的長度各不相同，所以需要第三個參數addrlen指定結構體的長度。

- myaddr

            bzero(&servaddr, sizeof(servaddr));
            servaddr.sin_family = AF_INET;
            servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
            servaddr.sin_port = htons(SERV_PORT);

> 首先將整個結構體清零，然後設置地址類型為AF_INET，網絡地址為INADDR_ANY，這個宏表示本地的任意IP地址，因為伺服器可能有多個網卡，每個網卡也可能綁定多個IP地址，這樣設置可以在所有的IP地址上監聽，直到與某個客戶端建立了連接時才確定下來到底用哪個IP地址，連接埠號為SERV_PORT，我們定義為8000。
- int listen(int sockfd, int backlog);
> 典型的伺服器程序可以同時服務于多個客戶端，當有客戶端發起連接時，伺服器調用的accept()返回並接受這個連接，如果有大量的客戶端發起連接而伺服器來不及處理，尚未accept的客戶端就處于連接等待狀態，listen()聲明sockfd處于監聽狀態，並且最多允許有backlog個客戶端處于連接待狀態，如果接收到更多的連接請求就忽略。listen()成功返回0，失敗返回-1。

- int accept(int sockfd, struct sockaddr *cliaddr, socklen_t *addrlen);
> 三方握手完成後，伺服器調用accept()接受連接，如果伺服器調用accept()時還沒有客戶端的連接請求，就阻塞等待直到有客戶端連接上來。cliaddr是一個傳出參數，accept()返回時傳出客戶端的地址和連接埠號。addrlen參數是一個傳入傳出參數（value-result argument），傳入的是調用者提供的緩衝區cliaddr的長度以避免緩衝區溢出問題，傳出的是客戶端地址結構體的實際長度（有可能沒有占滿調用者提供的緩衝區）。如果給cliaddr參數傳NULL，表示不關心客戶端的地址。
</details>

2.
<details>
<summary> <a href="https://man7.org/linux/man-pages/man7/epoll.7.htm">epoll manual</a> 整理: </summary>

#### epoll 通過監控多個檔案描述符來檢視任何一個(被監控的)檔案描述符是否可能有IO操作

[詳細拆解 epoll ](https://inf.news/technique/10cdedfe9449802a7aeb674863882af5.html)

- int epoll_create(int size);
> 建立一個epoll instance 並且返回一個指代該例項的檔案描述符

- int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
> 特定檔案描述符 (fd) 通過 epoll_ctl 註冊到 epoll instance (epfd)。
> op: 通過指定op來新增(EPOLL_CTL_ADD)/修改(EPOLL_CTL_MOD)/刪除(EPOLL_CTL_DEL)需要偵聽的檔案描述符及其事件
> fd 是想新增/刪減的某 socket 的 fd。
> event 則是記錄著 fd 更多的資料

- epoll_wait:
> waits for I/O events(等待IO事件)，如果沒有 event 回傳的話，會把 call thread 擋住。

- epfd:
> The interest list
> The ready list: subset of interest list

- event:
> 描述連結於 fd 的 object。 epoll_event 的結構如下

typedef union epoll_data {
void *ptr;
int fd;
uint32_t u32;
uint64_t u64;
} epoll_data_t;

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

- The data member of the epoll_event structure specifies data that the kernel should save and then return (via epoll_wait(2)) when this file descriptor becomes ready.

EPOLLIN 是監聽讀的事件，而 EPOLLET 是 edge-triggered，

    static struct epoll_event ev = {.events = EPOLLIN | EPOLLET};

> 水平觸發:就是只有高電平(1)或低電平(0)時才觸發通知,只要在這兩種狀態就能得到通知。邊緣觸發:只有電平發生變化(高電平到低電平,或者低電平到高電平)的時候才觸發通知。簡單理解，在水平觸發的時候，可以時刻監測IO的狀態，而邊緣觸發，只有下次IO活動到來的時候，才進行通知。因此，當監視數量描述符多的時候，邊緣觸發的epoll效率更高

</details>

> 延伸閱讀 [Beej's Guide to Network Programming](https://beej.us/guide/bgnet/html/#system-calls-or-bust) 不錯的C Socket 介紹

int main(void)
{
    static struct epoll_event events[EPOLL_SIZE];
    struct sockaddr_in addr = {
        .sin_family = PF_INET,
        .sin_port = htons(SERVER_PORT), // htons 表示將16位的SERVER_PORT 從主機位元組序轉換為網絡位元組序
        .sin_addr.s_addr = htonl(INADDR_ANY), // htonl表示將32位的 INADDR_ANY 長整數從主機位元組序轉換為網絡位元組序，
    };
    socklen_t socklen = sizeof(addr);

    client_list_t *list = NULL;
    int listener; // file desiptor 
    // 對於TCP協議，type參數指定為SOCK_STREAM，表示面向流的傳輸協議
    // 指定協議，應該用PF_xxxx，設置地址時應該用AF_xxxx。但混用好像也沒差
    if ((listener = socket(PF_INET, SOCK_STREAM, 0)) < 0)
        server_err("Fail to create socket", &list);
    printf("Main listener (fd=%d) was created.\n", listener);

    // 把 fd 設為 non blocking的
    if (setnonblock(listener) == -1)
        server_err("Fail to set nonblocking", &list);
    // 使 listener 這個用於網絡通訊的檔案描述符監聽 addr 所描述的地址和連接埠號
    if (bind(listener, (struct sockaddr *) &addr, sizeof(addr)) < 0)
        server_err("Fail to bind", &list);
    printf("Listener was binded to %s\n", inet_ntoa(addr.sin_addr));

    // listen()聲明 listener 處于監聽狀態，並且最多允許有 backlog 個客戶端處于連接待狀態，
    // 這邊設定為 128 (default attribute of /proc/sys/net/core/somaxconn)
    if (listen(listener, 128) < 0)
        server_err("Fail to listen", &list);

    int epoll_fd;
    if ((epoll_fd = epoll_create(EPOLL_SIZE)) < 0)
        server_err("Fail to create epoll", &list);

    // epoll_event 初始化設定 `EPOLLIN | EPOLLET`
    // EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
    // 将EPOLL设为边缘触发(Edge Triggered)模式
    static struct epoll_event ev = {.events = EPOLLIN | EPOLLET};
    ev.data.fd = listener;
    if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, listener, &ev) < 0)
        server_err("Fail to control epoll", &list);
    printf("Listener (fd=%d) was added to epoll.\n", epoll_fd);

    while (1) {
        struct sockaddr_in client_addr;
        int epoll_events_count;
        if ((epoll_events_count = epoll_wait(epoll_fd, events, EPOLL_SIZE,
                                             EPOLL_RUN_TIMEOUT)) < 0)
            server_err("Fail to wait epoll", &list);
        printf("epoll event count: %d\n", epoll_events_count);
        clock_t start_time = clock();
        for (int i = 0; i < epoll_events_count; i++) {
            /* EPOLLIN event for listener (new client connection) */
            if (events[i].data.fd == listener) {
                int client;
                // 如果有新的 connection 的話，透過 epoll_ctl 登入到 epoll object 中，並且把他設定成 nonblock。再把這個 client 放進 list 裡面
                while (
                    (client = accept(listener, (struct sockaddr *) &client_addr,
                                     &socklen)) > 0) {
                    printf("Connection from %s:%d, socket assigned: %d\n",
                           inet_ntoa(client_addr.sin_addr),
                           ntohs(client_addr.sin_port), client);
                    setnonblock(client);
                    ev.data.fd = client;
                    if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, client, &ev) < 0)
                        server_err("Fail to control epoll", &list);
                    push_back_client(&list, client,
                                     inet_ntoa(client_addr.sin_addr));
                    printf(
                        "Add new client (fd=%d) and size of client_list is "
                        "%d\n",
                        client, size_list(list));
                }
                if (errno != EWOULDBLOCK)
                    server_err("Fail to accept", &list);
            } else {
                /* EPOLLIN event for others (new incoming message from client)
                 */
                if (handle_message_from_client(events[i].data.fd, &list) < 0)
                    server_err("Handle message from client", &list);
            }
        }
        printf("Statistics: %d event(s) handled at: %.6f second(s)\n",
               epoll_events_count,
               (double) (clock() - start_time) / CLOCKS_PER_SEC);
    }
    close(listener);
    close(epoll_fd);
    exit(0);
}

static int handle_message_from_client(int client, client_list_t **list)
{
    int len;
    char buf[BUF_SIZE];
    memset(buf, 0, BUF_SIZE);
    // 取出 message
    if ((len = recv(client, buf, BUF_SIZE, 0)) < 0)
        server_err("Fail to receive", list);
    // 如果取完的話，關閉 client
    if (len == 0) {
        if (close(client) < 0)
            server_err("Fail to close", list);
        *list = delete_client(list, client);
        printf("After fd=%d is closed, current numbers clients = %d\n", client,
               size_list(*list));
    } else {
        printf("Client #%d :> %s", client, buf);
        if (send(client, buf, BUF_SIZE, 0) < 0)
            server_err("Fail to send", list);
    }
    return len;
}

### 是否理解 bench 原理，能否比較 kecho 和 user-echo-server 表現？佐以製圖
- pthread & condition variable：
在 `bench_worker` 可以看到使用 `pthread_mutex_lock`，`pthread_mutex_unlock`，`pthread_cond_broadcast` 和 `pthread_cond_wait`。

pthread_mutex_lock(&worker_lock);
if (++n_retry == MAX_THREAD) {
    // wake up every waiting thread
    pthread_cond_broadcast(&worker_wait);
} else {
    while (n_retry < MAX_THREAD) {
        if (pthread_cond_wait(&worker_wait, &worker_lock)) {
            puts("pthread_cond_wait failed");
            exit(-1);
        }
    }
}
pthread_mutex_unlock(&worker_lock);                                              

thread 1 一開始會取得 lock。然後進到 line 2 判斷目前的 `thread` 數量是否為 MAX_THREAD 數量。如果不是的話就會進到 line6 的環圈，並且呼叫`pthread_cond_wait(&worker_wait, &worker_lock)` 後進入 `wait`（這邊注意 `pthread_cond_wait` 會入下圖把前面鎖起來的 `mutex` 打開再進入阻塞）。
等到足夠的 thread 數量後，會呼叫 `pthread_cond_broadcast` 把所有的 thread 喚醒，開始建立 `socket`。 可以注意到在廣播之前，先把 ready 設成 true，這是為了避免在廣播時還有人嘗試想睡在 condition variable 上(若 ready 為真，則不會呼叫 pthread_cond_wait)。既然廣播了，那我們又要回到 bench_worker 繼續做事。從 pthread_cond_wait 繼續往下做。

- socket
`bench_worker` 的後半段基本上就是在建立 socket。會去評估一次傳送和一次接受所需要的時間：

if (connect(sock_fd, (struct sockaddr *) &info, sizeof(info)) == -1) {
        perror("connect");
        exit(-1);
}

gettimeofday(&start, NULL);
send(sock_fd, msg_dum, strlen(msg_dum), 0);
recv(sock_fd, dummy, MAX_MSG_LEN, 0);
gettimeofday(&end, NULL);

shutdown(sock_fd, SHUT_RDWR);
close(sock_fd);    
    

- kecho 和 user-echo-server 表現

kecho:

user-echo-server:

# Reference
- IO管理 https://blog.csdn.net/qq_41453285/article/details/89810683 - [kernel thread](https://www.cs.fsu.edu/~cop4610t/lectures/project2/kthreads/kthreads.pdf)