2023q1 Homework7 (ktcp)

contributed by < linhoward0522 >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4992.00

`CMWQ`

Concurrency Managed Workqueue

Introduction

許多情況下需要非同步來執行 process ，這個情況下最常用的方法就是 workqueue 的 API
當需要這樣非同步來執行 process 時，會將工作放入 queue 中。一個獨立的thread 會進行非同步執行

queue 稱為 workqueue
thread 稱為 worker
當 workqueue 上有工作時， worker 會依序地執行與該工作關聯的功能
當 workqueue 沒有工作時， worker 就會 idle

Why cmwq?

原本的 workqueue 有兩種方式:

multi thread : 每個 CPU 有一個 worker ，每一個 multi thread 需要保持與 CPU 大致相同的 worker 數量
single thread : 整個系統內只有一個 worker

使用multi thread 方法會消耗許多的資源，且並行的效果不盡人意

Concurrency Managed Workqueue (cmwq) 是針對 workqueue 的改善，並著重於以下目標 :

保持與原始 workqueue API 的兼容性
每個 CPU 共享所有的 Worker Pools 並根據不同需求提供彈性的並行等級，減少資源浪費
自動調整 worker pool 和並行等級，使 API 使用者無需擔心這些細節

The Design

為了簡化非同步執行，所以引入了 work item 的概念。是一個簡單的結構包含指向非同步執行函式的函式指標，當想要非同步執行函式時，必須設置一個指向該函式的 work item ，並放入 workqueue
worker thread 依序會處理 workqueue 中的任務，若沒有任務 thread 會變為 idle 狀態，而由worker-pools 負責管理這些 threads
有兩種 worker-pools :
- Bound : 服務綁定在特定的 CPU 上的 work item ，在指定的 CPU 上執行。且又分兩個 worker-pools，一種用於正常優先級的 work item ，另一種用於高優先級 work item
- Unbound : worker 可以在多個 CPU 上調度，且 worker-pools 裡面的 worker 數量是動態的
對於 worker-pools 的實作，管理並行等級（有多少任務同時工作）是一個問題。 CMWQ 會將並行保持在最低但足夠的等級，以節省資源
每當 worker 醒來或是睡覺時， worker-pool 都會收到通知，並持續追蹤當前可工作的 worker
通常 work item 不會佔用 CPU 很多週期，表示保持足夠的並行性來防止工作停止是最佳的
只要 CPU 上有一個或多個可運行的 worker ， worker-pool 就不會開始執行新工作，但是當最後一個運行的 worker 進入睡眠狀態時，它會立即排程一個新的 worker ，這樣 CPU 就不會在有待處理的 work item 時閒置
除了 kthreads 的記憶體空間外，保持閒置的 worker 不會花費任何成本，因此 CMWQ 在釋放它們的系統資源之前會保留閒置的 worker 一段時間

給定的 `kecho` 已使用 `CMWQ`，請陳述其優勢和用法，應重現相關實驗

kecho_mod.c 中的 71 行利用 alloc_workqueue 來創建 workqueue

struct workqueue_struct *kecho_wq;
kecho_wq = alloc_workqueue(MODULE_NAME, bench ? 0 : WQ_UNBOUND, 0);

其中 WQ_UNBOUND flag 表示 work item 不需要綁定在特定的 CPU 上執行
進入到 unbound workqueue 的 work item 會被盡快執行，這樣雖然犧牲了 locality ，但有以下好處 :

並行等級的波動是被預期的，若使用 bound workqueue 可能會創建大量的 worker 卻未使用到
系統排程器可以更好地管理長時間在 CPU 運行的工作

Work items queued to an unbound wq are served by the special worker-pools which host workers which are not bound to any specific CPU. This makes the wq behave as a simple execution context provider without concurrency management. The unbound worker-pools try to start execution of work items as soon as possible. Unbound wq sacrifices locality but is useful for the following cases.

Wide fluctuation in the concurrency level requirement is expected and using bound wq may end up creating large number of mostly unused workers across different CPUs as the issuer hops through different CPUs.

Long running CPU intensive workloads which can be better managed by the system scheduler.

kecho_mod.c 中的 86 行利用 destroy_workqueue 來將 workqueue 釋放

destroy_workqueue(kecho_wq);

Safely destroy a workqueue. All work currently pending will be done first.

echo_server.c 中的 109 行利用 INIT_WORK 來將任務初始化，透過 function pointer 指派任務內容

INIT_WORK(&work->kecho_work, echo_server_worker);

initialize all of a work item in one go

echo_server.c 中的 160 行利用 queue_work 來將任務加入 workqueue 中

/* start server worker */
queue_work(kecho_wq, work);

We queue the work to the CPU on which it was submitted, but if the CPU dies it can be processed by another CPU.

比較 `kecho` 和 `user-echo-server` 的效能

kecho 的效能

實驗 bench 不論設為 true 或是 false ，效能都差不多

user-echo-server 的效能

可以看出因為 kecho 是在 kernel 執行，並且又引入了 CMWQ，所以執行時間比 user-echo-server 快很多

引入 `Concurrency Managed Workqueue (cmwq)`，改寫 `kHTTPd`，分析效能表現和提出改進方案

參考 kecho 來作修改

`http_server.h`

http_service 用來管理 workqueue

is_stopped 用來取代本來 worker 內的 kthread_should_stop，改變 is_stopped 可以通知所有 worker 停止
worker 使用 List 來維護，可以利用 The Linux Kernel API 來做新增或刪除

#define MODULE_NAME "khttpd"

struct http_service {
    bool is_stopped;
    struct list_head worker;
};

khttpd 用來管理 work

struct khttpd {
    struct socket *sock;
    struct list_head list;
    struct work_struct http_work;
};

`main.c`

原本 khttpd 核心模組是採用系統預設的 workqueue ，為了要引入 CMWQ，必須在掛載以及卸載模組時用到 workqueue ，所以需要 alloc_workqueue 以及 destroy_workqueue

-#include <linux/kthread.h>
 #include <linux/sched/signal.h>
 #include <linux/tcp.h>
 #include <linux/version.h>
 ...
+struct workqueue_struct *khttpd_wq;

static int __init khttpd_init(void)
{
    ...
+   khttpd_wq = alloc_workqueue(MODULE_NAME, WQ_UNBOUND, 0);
    http_server = kthread_run(http_server_daemon, &param, KBUILD_MODNAME);
    ...
}
         
static void __exit khttpd_exit(void)
{
    send_sig(SIGTERM, http_server, 1);
    kthread_stop(http_server);
    close_listen_socket(listen_socket);
+   destroy_workqueue(khttpd_wq);
    pr_info("module unloaded\n");
}

`http_server.c`

首先使用全域變數 is_stopped ，可以用來通知所有 worker 是否停止，以及一個指標指向 workqueue

struct http_service daemon = {.is_stopped = false};
extern struct workqueue_struct *khttpd_wq;

http_server_worker
- 建立一個 worker ，並使用 container_of 巨集來獲得 socket 資料
- while 迴圈使用 is_stopped 來判斷是否結束

-static int http_server_worker(void *arg)
+static void http_server_worker(struct work_struct *work)
 {
+    struct khttpd *worker = container_of(work, struct khttpd, http_work);
     char *buf;
     ...
     struct http_request request;
-    struct socket *socket = (struct socket *) arg;
+    struct socket *socket = worker->sock;

     allow_signal(SIGKILL);
     allow_signal(SIGTERM);
static int http_server_worker(void *arg)
     buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
     if (!buf) {
         pr_err("can't allocate memory!\n");
-        return -1;
+        return;
     }

     request.socket = socket;
     http_parser_init(&parser, HTTP_REQUEST);
     parser.data = &request;
-    while (!kthread_should_stop()) {
+    while (!daemon.is_stopped) {
         int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
         if (ret <= 0) {
             if (ret)
         }
     ...    
     kernel_sock_shutdown(socket, SHUT_RDWR);
     sock_release(socket);
     kfree(buf);
-    return 0;
 }

create_work
- 使用 kmalloc 為每一個 work_item 動態配置 kernel space 的記憶體空間
- 利用 INIT_WORK 來將任務初始化，透過 function pointer 將 work_item 綁在對應的函式上
- 最後使用 list_add 來加入到 workqueue 中
free_work
- 使用 list_for_each_entry_safe 走訪整個 linked list
- kernel_sock_shutdown斷開 socket 的連線
- flush_work 等待 work_item 執行完畢
- sock_release 關閉 socket
- kfree 釋放從 kmalloc 所配置的記憶體空間
http_server_daemon
- 使用 create_work 會為每一個連線的請求建立一個 work_item 進行處理
- queue_work 會將 work_item 放入 workqueue 中排隊
- 最後當 daemon 結束，呼叫 free_work 來釋放掉建立連線所分配的記憶體空間

int http_server_daemon(void *arg)
{
    struct socket *socket;
    struct work_struct *work;
    struct http_server_param *param = (struct http_server_param *) arg;

    allow_signal(SIGKILL);
    allow_signal(SIGTERM);

    INIT_LIST_HEAD(&daemon.worker);

    while (!kthread_should_stop()) {
        int err = kernel_accept(param->listen_socket, &socket, 0);
        if (err < 0) {
            if (signal_pending(current))
                break;
            pr_err("kernel_accept() error: %d\n", err);
            continue;
        }
        if (unlikely(!(work = create_work(socket)))) {
            printk(KERN_ERR MODULE_NAME
                   ": create work error, connection closed\n");
            kernel_sock_shutdown(socket, SHUT_RDWR);
            sock_release(socket);
            continue;
        }

        /* start server worker */
        queue_work(khttpd_wq, work);
    }

    printk(MODULE_NAME ": daemon shutdown in progress...\n");

    daemon.is_stopped = true;
    free_work();
    return 0;
}

實驗結果

使用 make check 來實驗原始版本，以及引入 CMWQ 後的效能

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:       1.207                seconds:       0.588
requests/sec:  82870.570            requests/sec:  169943.171

可以發現 requests/sec 提昇了將近一倍

2023q1 Homework7 (ktcp)

開發環境

CMWQ

Introduction

Why cmwq?

The Design

給定的 kecho 已使用 CMWQ，請陳述其優勢和用法，應重現相關實驗

比較 kecho 和 user-echo-server 的效能

引入 Concurrency Managed Workqueue (cmwq)，改寫 kHTTPd，分析效能表現和提出改進方案

http_server.h

main.c

http_server.c

實驗結果

Read more

2023q1 Homework1 (lab0)

Demystifying the Linux CPU Scheduler 閱讀筆記

關於 BORE 及 schedgraph 的描述

2023q1 Homework3 (fibdrv)