LKL: 重用 Linux 核心的成果

貢獻者: jserv

Linux Kernel Library (LKL) 設計為 Linux 核心的移植版本，在目錄 arch/lkl 中，約有 3500 行的程式碼。LKL 與應用程式連結，以運作於使用者空間，依賴由主機作業系統提供的一組主機端的功能，例如 semaphore, POSIX Threads, malloc、計時器 (timer) 等。LKL 擁有良好定義的外部介面，例如系統呼叫及 virtio-net。LKL 允許 FreeBSD, macOS, Windows, 和(舊版的) Linux 存取各式 Linux 核心的成果。

LKL 執行在非特權的使用者空間，無需記憶體保護機制，只依賴由本機作業系統配置一塊記憶體空間。LKL 的記憶體管理遵循與常規 Linux 核心相同的原則，也就是 SLUB/SLAB 演算法。

使用 LKL 的情境

其中一個應用場景是，搭配 FUSE，掛載 Linux 核心支援的多種檔案系統。

藉由 LKL，可將 TCP/IP 的處理從核心空間轉移到使用者空間，而不必修改標的應用程式。LKL 還提供使用 DPDK 支援的選項，這能提供快速的 TCP/IP 通訊協定堆疊處理。二者都能降低網路通信中的瓶頸。

上圖的左半部分顯示 Node.js 應用程式如何運作於 Linux。右半部分展示改進的方案，包含 LKL 和 DPDK。

此外，LKL 允許在使用者空間中對 Linux 核心程式碼進行模糊測試 (fuzzing)，可搭配 libFuzzer 使用。該手法的優點包括：

• 在 x86-64 平台上達到高效能的模糊測試
• 模糊測試工具輕量化，無需借助虛擬機器
• 容易進行除錯和崩潰重現，還可搭配 gdb
• 支援硬體模擬，例如 PCI

示意圖如下:

為了讓模糊測試行為更可預測 (deterministic)，甚至可在 LKL 中引入特製的排程器，作法是在核心的同步處理機制 (如 spinlock 和 mutex) 前後插入 yield point。

延伸閱讀:

• A Library Version of Linux Kernel, FOSDEM 2020

  video

• LKL: A way to reuse Linux kernel in userland, 2018
• User Space TCP based on LKL, 2016

  video, paper

• Minimize Node.js I/O Bottlenecks with Linux Kernel Library and Data Plane Developer Kit
• Fuzzing Host-to-Guest Attack Surface in Android Protected KVM, 2022
• How to Fuzz Your Way to Android Universal Root: Attacking Android Binder, 2024
• Android Binder Attack Matrix: Fuzzing Binder with Linux Kernel Library (LKL)

編譯和測試

確保檔案系統有 6 GB 以上的可用空間，否則後續操作會失敗。

取得原始程式碼:

$ git clone https://github.com/lkl/linux lkl --depth=1
$ cd lkl

安裝依賴的套件:

$ sudo apt-get install fuse3 libfuse3-dev libarchive-dev xfsprogs

編譯 LKL:

$ make -C tools/lkl -j$(nproc)

若要執行內建的測試，需要安裝以下套件:

$ sudo apt-get install btrfs-progs
$ pip3 install yamlish junit_xml

執行內建測試:

$ cd tools/lkl
$ make run-tests

參考執行結果:

  ...
  TEST       ok       cleanup 
  SUITE               config
  ...
Summary: 25 suites run, 151 tests, 135 ok, 0 not ok, 16 skipped

在上述的 tools/lkl 目錄，預期可見名為 lklfuse 的執行檔，以下示範藉由 LKL 掛載 ext2 檔案系統，不依賴作業系統原生的檔案系統實作。

$ truncate -s 10m /tmp/ext2.img
$ mkfs.ext2 /tmp/ext2.img
$ mkdir /tmp/mnt
$ ./lklfuse -o type=ext2 /tmp/ext2.img /tmp/mnt

可將檔案放入掛載的 /tmp/mnt 目錄，隨後執行 umount 卸載。
相關工具:

• fs2tar: 將檔案系統轉為 tar
• cptofs/cpfromfs: 將檔案入放置/取自給定的檔案系統映像檔

整合 LKL

前述編譯成功後，預期會在 tools/lkl 目錄產生 liblkl.a 檔案，我們可用來整合，下方的程式碼和操作也在 tools/lkl 目錄中進行。

準備以下 C 程式 (檔名: min.c)

#include "lkl_host.h"
#include "lkl.h"
int main()
{
    lkl_init(&lkl_host_ops);
    lkl_start_kernel("mem=128M");
    return 0;
}

編譯和連結:

$ gcc -o min min.c -I./include liblkl.a -lpthread -lrt

該程式得以在 Linux (或 LKL 支援的作業系統) 環境中，執行部分 Linux 功能，以下是參考輸出:

$ ./min
[    0.000000] Linux version 6.6.0+ (jserv@node1) (gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #1 Mon May 27 22:09:09 CST 2024
[    0.000000] memblock address range: 0x7f5d04000000 - 0x7f5d0c000000
[    0.000000] Zone ranges:
[    0.000000]   Normal   [mem 0x00007f5d04000000-0x00007f5d0bffffff]
[    0.000000] Movable zone start for each node
[    0.000000] Early memory node ranges
[    0.000000]   node   0: [mem 0x00007f5d04000000-0x00007f5d0bffffff
...
[    0.050217] This architecture does not have kernel memory protection.
[    0.050223] Run /init as init process

當 LKL 停留在最後一行訊息 Run /init as init process，就意味著其無法讀取到有效的 init 程式，作為 PID=1 的行程 (相當於 systemd 一類的系統程式)。

接著準備以下 C 程式 (檔名: readfs.c)

#include <assert.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>                                                                                  
#include "lkl.h"
#include "lkl_host.h"

int main(int argc, const char *argv[])
{
    const char *fsimage = argv[1], *fstype = argv[2], *file_to_dump = argv[3];

    lkl_init(&lkl_host_ops);

    struct lkl_disk disk;
    memset(&disk, 0, sizeof(disk));
    disk.fd = open(fsimage, O_RDONLY);
    assert(disk.fd >= 0);

    int disk_id = lkl_disk_add(&disk);
    assert(disk_id >= 0);

    lkl_start_kernel("mem=128M");

    char mpoint[128];
    int ret = lkl_mount_dev(disk_id, 0 /* part */, fstype, LKL_MS_RDONLY, NULL,
                            mpoint, sizeof(mpoint));

    if (ret < 0) {
        fprintf(stderr, "lkl_mount_dev failed: %s\n", lkl_strerror(ret));
        close(disk.fd);
        exit(1);
    }

    struct lkl_dir *dir = lkl_opendir(mpoint, &ret);
    struct lkl_linux_dirent64 *dent;
    while ((dent = lkl_readdir(dir)))
        fprintf(stderr, "Directory entry: %s\n", dent->d_name);
    lkl_closedir(dir);
    
    char tmp[256];
    char buffer[65536];
    snprintf(tmp, sizeof(tmp), "%s/%s", mpoint, file_to_dump);
    int fd = lkl_sys_open(tmp, LKL_O_RDONLY, 0);
    fprintf(stderr, "fd = %d\n", fd);
    assert(fd >= 0);
    int count = lkl_sys_read(fd, buffer, sizeof(buffer));
    write(STDERR_FILENO, buffer, count); 
    lkl_sys_close(fd);
    
    return 0;
}

編譯並連結:

$ gcc -o readfs readfs.c -Iinclude liblkl.a -lpthread -lrt

接著準備提供給 LKL 掛載為 rootfs 的檔案系統:

$ mke2fs ext4.img -t ext4 32M
$ mkdir -p /tmp/mnt
$ ./lklfuse -o type=ext4 ext4.img /tmp/mnt
$ echo -e "Hello world\!\nTEST" > /tmp/mnt/test.txt
$ umount /tmp/mnt

至此我們終於可指定 rootfs 並啟動 LKL:

$ ./readfs  ext4.img ext4 test.txt

參考執行輸出:

[    0.000000] Linux version 6.6.0+ (jserv@node1) (gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #1 Mon May 27 22:09:09 CST 2024
[    0.000000] memblock address range: 0x7fb568000000 - 0x7fb570000000
...
[    0.047948] Run /init as init process
[    0.048719] EXT4-fs (vda): mounted filesystem 4cbc1b7f-0e84-4092-b70a-f32cd2398a53 ro with ordered data mode. Quota mode: disabled.
Directory entry: lost+found
Directory entry: test.txt
Directory entry: ..
Directory entry: .
fd = 0
Hello world\!
TEST

知曉 LKL 的使用，我們來嘗試傾印 /proc 目錄的所有內容。
準備以下 C 程式: (檔名: cat_proc.c)

#include <dirent.h>                           
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include "lkl.h"
#include "lkl_host.h"

static void close_fd(int fd)
{
    int r = lkl_sys_close(fd);
    if (r < 0)
        lkl_printf("LKL close error: %d\n", r);
}

static int cat_file(char *path)
{
    int fd = lkl_sys_open(path, LKL_O_RDONLY, 0);
    if (fd < 0) {
        lkl_printf("LKL open error: %d\n", fd);
        return fd;
    }
    int ret = 0;
    for (;;) {
        char buf[1024];
        int len = lkl_sys_read(fd, buf, 1024);
        if (len < 0) {
            lkl_printf("LKL read error: %d\n", len);
            ret = len;
            goto out;
        }
        if (len == 0)
            break;
        for (int written = 0; written < len;) {
            int n = write(STDOUT_FILENO, buf + written, len - written);
            if (n < 0) {
                lkl_printf("write error: %d\n", n);
                ret = n;
                goto out;
            }
            written += n;
        }
    }
out:
    close_fd(fd);
    return ret;
}

int main(int n, char **args)
{
    lkl_init(&lkl_host_ops);
    lkl_start_kernel("mem=10M");
    int ret = lkl_sys_mkdir("/proc", 0777);
    if (ret < 0) {
        lkl_printf("LKL mkdir error: %d\n", ret);
        return 1;
    }
    ret = lkl_sys_mount("none", "/proc", "proc", 0, 0);
    if (ret < 0) {
        lkl_printf("LKL mount error: %d\n", ret);
        return 1;
    }
    char *path = "/proc";
    int fd = lkl_sys_open(path, LKL_O_RDONLY | LKL_O_DIRECTORY, 0);
    if (fd < 0) {
        lkl_printf("LKL open error: %d\n", fd);
        return 1;
    }
    for (;;) {
        char buf[1024];
        struct lkl_linux_dirent64 *d = (void *) buf;
        int n = lkl_sys_getdents64(fd, d, sizeof(buf));
        if (n < 0) {
            lkl_printf("LKL getdents error: %d\n", n);
            return 1;
        }
        if (n == 0)
            break;
        char pathbuf[1024];
        while ((char *) d < buf + n) {
            snprintf(pathbuf, sizeof(pathbuf), "%s/%s", path, d->d_name);
            lkl_printf("path: %s\n", pathbuf);
            if (d->d_type == DT_REG && strcmp(d->d_name, "kmsg") != 0) {
                if (cat_file(pathbuf) < 0)
                    return 1;
            }
            d = (void *) ((char *) d + d->d_reclen);
        }
    }
    close_fd(fd);
    lkl_sys_halt();
    return 0;
}

編譯並連結:

$ gcc -o cat_proc cat_proc.c -I./include liblkl.a -lpthread -lrt

參考執行輸出:

$ ./cat_proc
[    0.000000] Linux version 6.6.0+ (jserv@node1) (gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #1 Mon May 27 22:09:09 CST 2024
...
183 hw_random
127 vga_arbiter
path: /proc/stat
cpu  0 0 3 0 0 0 0 0 0 0
...
path: /proc/pagetypeinfo
Page block order: 10
Pages per block:  1024
...
[    0.562821] reboot: Restarting system

執行緒管理

LKL 不提供建立執行緒的服務給使用它的程式，不過在 LKL 內部仍仰賴執行緒確保 Linux 核心得以正確運作。在 LKL 的早期版本中，藉由內部執行緒來模擬 Linux 核心所需要的機制，但後者必須有單獨的堆疊，而堆疊的配置是由主機作業系統完成，結果 LKL 無法為執行緒配置新的堆疊，不得不將主機作業系統配置的堆疊分成多個部分。因此，每個執行緒的堆疊大小會隨著 LKL 核心中的執行緒數量成比例地減少，對模擬的執行緒數量施加嚴格的限制。開發人員最終決定放棄在 LKL 內部模擬執行緒的想法，倘若 Linux 核心需要執行緒，LKL 會要求本機作業系統建立執行緒，實作二個中介方法：一個呼叫系統呼叫 thread_create，另一個呼叫系統呼叫 thread_exit。關於 LKL 的主機端操作介面，可見 arch/lkl/include/uapi/asm/host_ops.h， LKL 的主機端操作介面

struct lkl_host_operations {
    ...
    lkl_thread_t (*thread_create)(void (*f)(void *), void *arg);                                                                                          
    void (*thread_detach)(void);
    void (*thread_exit)(void);
    int (*thread_join)(lkl_thread_t tid);
    lkl_thread_t (*thread_self)(void);
    int (*thread_equal)(lkl_thread_t a, lkl_thread_t b);
    void *(*thread_stack)(unsigned long *size);
    ...

tools/lkl/lib/posix-host.c 是針對 POSIX 相容作業系統的橋接實作，提供上方操作介面的功能：

static lkl_thread_t thread_create(void (*fn)(void *), void *arg)                                                                                              
{
    pthread_t thread;
    if (WARN_PTHREAD(pthread_create(&thread, NULL, (void* (*)(void *))fn, arg)))
        return 0;
    else
        return (lkl_thread_t) thread;
}

不過這種方法在解決堆疊問題的同時，產生新問題：Linux 核心必須確保它控制執行緒切換，但使用上述方法，執行緒切換由主機作業系統控制。為了解決這個問題，LKL 中設計模擬執行緒管理的機制。

如何在 LKL 中實作執行緒管理的模擬？需要施加一個特殊限制：在任何給定時刻，LKL 只能在一個執行緒中運行。這個限制顯著降低核心的性能，但簡化執行緒系統的實作。單執行緒透過在設定檔中指定相應的項目來實作，例如指定核心是針對單處理器架構，也就是取消核心選項 CONFIG_SMP。LKL 從本機作業系統建立執行緒，並獲取相應的系統 semaphore。由於此資源是從主機作業系統獲取的，因此透過回呼函式實作。

Linux 排程器在 LKL 改寫，顧及二個層次：一個系統層次（為此我們從系統獲取 semaphore），另一個屬於 LKL 的內部層次（管理 LKL 內部的執行緒邏輯）。

• 在核心的架構相關部分中，Linux 核心的通用結構（lock, semaphore、執行緒）使用經由 lkl_host_ops 提供的回呼函式實作。
• 對於核心架構相關部分的內部用途，直接呼叫來自 lkl_host_ops 的回呼函式。

為了理解負責執行緒管理如何從主機作業系統獲取外部資源 (執行緒和 semaphore)，以下分析排程器的主要函式 __schedule()，其程式碼在檔案 kernel/sched/core.c 中。該函式是排程器的關鍵操作，進入該函式會發生於以下情況：

• 阻塞式同步處理：mutex, semaphore, waitqueue
• 中斷和從使用者形成返回。
• 喚醒執行緒不會導致呼叫 __schedule()

在切換行程時，排程器除了其他工作外，還處理上下文切換。在 __schedule() 函式中，呼叫函式 context_switch(rq, prev, next)，然後呼叫在檔案 linux/include/asm-generic/switch_to.h 中定義的巨集 switch_to(prev, next, last)：

#define switch_to(prev, next, last)

在此操作過程中，呼叫函式 __switch_to(struct task_struct *, struct task_struct *)，其位於專為 LKL 設計的檔案 linux/arch/lkl/kernel/threads.c 中。這就是在 LKL 中的 Linux 核心內部實作執行緒管理邏輯的地方。

當在 LKL 中由 Linux 核心建立執行緒時，執行下方回呼函式：

lkl_ops->sem_alloc(0)

並將其添加到 threadinfo 結構體中，該結構體定義於 arch/lkl/include/asm/thread_info.h

這個結構保存執行緒的信息。結構體中的 void *sched_sem，是內部執行緒排程器用來啟動/停止執行緒的 semaphore。在初始化時，每個新執行緒被配置一個由主機作業系統配置的 semaphore，初始值為零：

ti->sched_sem = lkl_ops->sem_alloc(0)

因此，新建立的 semaphore 將被阻塞，直到 LKL 排程器決定啟動此執行緒。修改排程器的主要工作實作於函式：

struct task_struct *__switch_to(struct task_struct *prev, struct task_struct *next)

該函式的實作在檔案 arch/lkl/kernel/thread.c 中。函式的主要三個操作階段是：

1. 保存正在切換的執行緒的 task_struct 指標。
2. 使用對應的回呼函式呼叫解鎖要切換到的執行緒的 semaphore：
   ​​​​lkl_ops->sem_up(_next->sched_sem);
   

3. 使用以下方式阻塞目前正在切換的執行緒：
   ​​​​lkl_ops->sem_down(ei.sched_sem);
   

__switch_to 函式返回一個指向呼叫 __switch_to 函式的行程的 task_struct 的指標。步驟 1 中保存正在切換的執行緒的 task_struct 指標，確保總是返回被切換行程的 task_struct 指標。

例如：假設在給定時刻，LKL 中的 Linux 核心在執行緒 1 中運行。__switch_to 函式被呼叫，經由 sem_up 切換到執行緒 2，然後執行緒 1 使用 sem_down 自行阻塞。在此之前，執行緒 1 將其 task_struct 指標保存到全域變數 abs_prev 中，該變數對所有 __switch_to 函式呼叫都是通用的。結果，__switch_to 函式將返回指向執行緒 1 的 task_struct 的指標。假設在後續工作中，切換到執行緒 3，並且執行緒 3 在其 __switch_to 函式呼叫中喚醒執行緒 1。這樣，函式返回指向執行緒 3 的 task_struct 的指標，而此時執行緒 1 正在執行。

因此，當內部執行緒排程器需要切換到新執行緒時，它會關閉目前執行緒的外部 semaphore，並打開所需執行緒的外部 semaphore。由於所有其他執行緒都被 semaphore 封鎖，主機系統排程器只能啟動內部 LKL 執行緒排程器所需的那一個執行緒。如果不這樣做，外部執行緒排程器可以按照其邏輯啟動執行緒，內部 LKL 執行緒排程器將失去對執行緒啟動順序的控制，破壞 Linux 核心的內部邏輯。與此同時，內部 LKL 層如常運行，封鎖同步的執行緒等。內部 LKL 執行緒排程器根據從其核心接收到的執行緒封鎖/啟動請求打開和關閉外部 lock。

待整理

• LKL.js: Running Linux Kernel on JavaScript, 2018

  slides

• Playing BBR with a userspace network stack, 2017
• UX/RT - a QNX-like OS based on seL4, 2022

  LKL for device drivers, disk filesystems, and network stack.
  Linux compatibility environment based on a library/loader and several special filesystems.

• Booting LKL inside Haiku
• rkt-io: A Direct I/O Stack for Shielded Execution, EuroSys 2021
• verker: Linux kernel library functions formally verified
• kBdysch is a collection of fast Linux kernel specific fuzzing harnesses supposed to be run in userspace in a guided fuzzing manner
• node-lkl uses the Linux Kernel Library project to provide access to filesystem drivers from NodeJS in a cross-platform way.
• ebpf-fuzzer: a fuzzer for Linux eBPF module, built on top of LKL
• Mount Btrfs USB disks on non-root Android using the Linux Kernel Library
• Howto: DPDK with LKL
• WasmLinux: create WebAssembly "native" Linux environment, both kernel and userland.
• LKL 尚未支援 SMP，但有對應的雛形設計