# LKL: 重用 Linux 核心的成果
> 貢獻者: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
[Linux Kernel Library](https://github.com/lkl/linux) (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](https://en.wikipedia.org/wiki/Filesystem_in_Userspace)，掛載 Linux 核心支援的多種檔案系統。
藉由 LKL，可將 TCP/IP 的處理從核心空間轉移到使用者空間，而不必修改標的應用程式。LKL 還提供使用 [DPDK](https://www.dpdk.org/) 支援的選項，這能提供快速的 TCP/IP 通訊協定堆疊處理。二者都能降低網路通信中的瓶頸。
上圖的左半部分顯示 Node.js 應用程式如何運作於 Linux。右半部分展示改進的方案，包含 LKL 和 DPDK。
此外，LKL 允許在使用者空間中對 Linux 核心程式碼進行模糊測試 (fuzzing)，可搭配 [libFuzzer](https://llvm.org/docs/LibFuzzer.html) 使用。該手法的優點包括：
* 在 x86-64 平台上達到高效能的模糊測試。
* 模糊測試工具輕量化，無需借助虛擬機器。
* 容易進行除錯和崩潰重現，還可搭配 gdb。
* 支援硬體模擬，例如 PCI。
示意圖如下:
為了讓模糊測試行為更可預測 (deterministic)，甚至可在 LKL 中引入特製的排程器，作法是在核心的同步處理機制 (如 spinlock 和 mutex) 前後插入 yield point。
延伸閱讀:
* [A Library Version of Linux Kernel](https://archive.fosdem.org/2020/schedule/event/uk_linux/), FOSDEM 2020
> [video](https://youtu.be/EYMqDS1qasg)
* [LKL: A way to reuse Linux kernel in userland](https://static.sched.com/hosted_files/lc32018/e0/lkl-lc3-2018-china.pdf), 2018
* [User Space TCP based on LKL](https://www.netdevconf.info/1.2/slides/oct6/03_jerry_chu_usTCP_LKL.pdf), 2016
> [video](https://youtu.be/xP9crHI0aAU), [paper](https://netdevconf.org/1.2/papers/jerry_chu.pdf)
* [Minimize Node.js I/O Bottlenecks with Linux Kernel Library and Data Plane Developer Kit](https://www.intel.cn/content/www/cn/zh/developer/articles/technical/minimize-nodejs-io-bottlenecks.html)
* [Fuzzing Host-to-Guest Attack Surface in Android Protected KVM](https://kvm-forum.qemu.org/2022/%5BKVM%20Forum%202022%5D%20-%20Virtio%20fuzzing%20%28go_kvm-forum-fuzzing-22%29.pdf), 2022
* [How to Fuzz Your Way to Android Universal Root: Attacking Android Binder](https://androidoffsec.withgoogle.com/posts/attacking-android-binder-analysis-and-exploitation-of-cve-2023-20938/offensivecon_24_binder.pdf), 2024
* [Android Binder Attack Matrix: Fuzzing Binder with Linux Kernel Library (LKL)](https://utkarshcodes.medium.com/android-binder-attack-matrix-fuzzing-binder-with-linux-kernel-library-lkl-article-3-62e931161eb5)
## 編譯和測試
:::warning
:warning: 確保檔案系統有 6 GB 以上的可用空間，否則後續操作會失敗。
:::
取得原始程式碼:
```shell
$ git clone https://github.com/lkl/linux lkl --depth=1
$ cd lkl
```
安裝依賴的套件:
```shell
$ sudo apt-get install fuse3 libfuse3-dev libarchive-dev xfsprogs
```
編譯 LKL:
```shell
$ make -C tools/lkl -j$(nproc)
```
若要執行內建的測試，需要安裝以下套件:
```shell
$ sudo apt-get install btrfs-progs
$ pip3 install yamlish junit_xml
```
執行內建測試:
```shell
$ 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 檔案系統，不依賴作業系統原生的檔案系統實作。
```shell
$ 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` 卸載。
## 整合 LKL
前述編譯成功後，預期會在 `tools/lkl` 目錄產生 `liblkl.a` 檔案，我們可用來整合，下方的程式碼和操作也在 `tools/lkl` 目錄中進行。
準備以下 C 程式 (檔名: `min.c`)
```c
#include "lkl_host.h"
#include "lkl.h"
int main()
{
lkl_init(&lkl_host_ops);
lkl_start_kernel("mem=128M");
return 0;
}
```
編譯和連結:
```shell
$ 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`)
```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;
}
```
編譯並連結:
```shell
$ gcc -o readfs readfs.c -Iinclude liblkl.a -lpthread -lrt
```
接著準備提供給 LKL 掛載為 rootfs 的檔案系統:
```shell
$ 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:
```shell
$ ./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`)
```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;
}
```
編譯並連結:
```shell
$ 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](https://github.com/lkl/linux/blob/master/arch/lkl/include/uapi/asm/host_ops.h)， LKL 的主機端操作介面
```c
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](https://github.com/lkl/linux/blob/master/tools/lkl/lib/posix-host.c) 是針對 POSIX 相容作業系統的橋接實作，提供上方操作介面的功能：
```c
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)`：
```c
#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 核心建立執行緒時，呼叫回呼函式如下：
```c
lkl_ops->sem_alloc(0)
```
並將其添加到 `threadinfo` 結構中，該結構定義於 `arch/lkl/include/asm/thread_info.h`
這個結構保存執行緒的信息。結構體中的 `void *sched_sem`，是內部執行緒排程器用來啟動/停止執行緒的 semaphore。在初始化時，每個新執行緒被配置一個由主機作業系統配置的 semaphore，初始值為零：
```c
ti->sched_sem = lkl_ops->sem_alloc(0)
```
因此，新建立的 semaphore 將被阻塞，直到 LKL 排程器決定啟動此執行緒。修改排程器的主要工作實作於函式：
```c
struct task_struct *__switch_to(struct task_struct *prev, struct task_struct *next)
```
該函式的實作在檔案 `arch/lkl/kernel/thread.c` 中。函式的主要三個操作階段是：
1. 保存正在切換的執行緒的 task_struct 指標。
2. 使用對應的回呼函式呼叫解鎖要切換到的執行緒的信號量：
```c
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 正在執行。
因此，當內部執行緒排程器需要切換到新執行緒時，它會關閉目前執行緒的外部信號量，並打開所需執行緒的外部信號量。由於所有其他執行緒都被信號量封鎖，主機系統排程器只能啟動內部 LKL 執行緒排程器所需的那一個執行緒。如果不這樣做，外部執行緒排程器可以按照其邏輯啟動執行緒，內部 LKL 執行緒排程器將失去對執行緒啟動順序的控制，破壞 Linux 核心的內部邏輯。與此同時，內部 LKL 層如常運行，封鎖同步的執行緒等。內部 LKL 執行緒排程器根據從其核心接收到的執行緒封鎖/啟動請求打開和關閉外部 lock。
## 待整理
* [LKL.js: Running Linux Kernel on JavaScript](https://retrage.github.io/2018/07/25/lkl-js-en.html/), 2018
> [slides](https://speakerdeck.com/retrage/lkl-dot-js-running-linux-kernel-on-javascript-star-directly-star?slide=14)
* [Playing BBR with a userspace network stack](https://netdevconf.org/2.1/session.html?tazaki), 2017
* [UX/RT - a QNX-like OS based on seL4](https://archive.fosdem.org/2022/schedule/event/awarkentin/), 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](https://www.haiku-os.org/blog/lucian/2010-07-08_booting_lkl_inside_haiku/)
* [rkt-io: A Direct I/O Stack for Shielded Execution](https://lsds.doc.ic.ac.uk/sites/default/files/rkt-io-eurosys21.pdf), EuroSys 2021
* [verker: Linux kernel library functions formally verified](https://github.com/evdenis/verker)
* [kBdysch](https://github.com/atrosinenko/kbdysch) is a collection of fast Linux kernel specific fuzzing harnesses supposed to be run in userspace in a guided fuzzing manner
* [node-lkl](https://github.com/balena-io-modules/node-lkl) uses the Linux Kernel Library project to provide access to filesystem drivers from NodeJS in a cross-platform way.
* [ebpf-fuzzer](https://github.com/ssrg-vt/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](https://hackweek.opensuse.org/projects/mount-btrfs-usb-disks-on-non-root-android-using-the-linux-kernel-library)
* [Howto: DPDK with LKL](https://github.com/lkl/linux/wiki/Howto:-DPDK-with-LKL)
* [WasmLinux](https://github.com/okuoku/wasmlinux-project): create WebAssembly "native" Linux environment, both kernel and userland.
* LKL 尚未支援 SMP，但有對應的[雛形設計](https://github.com/lkl/linux/issues/370)
Sign in with Wallet
Connect another wallet