🐧

WasmLinux: LinuxカーネルをWebAssemblyにする

2023/10/28に公開

Linux

LinuxカーネルがWebブラウザで動いたらどう考えても面白い んだけど、そこに至るまではなかなか難しい道のりになる。その第一歩として、Linuxカーネルのユーザーランド版であるLKL( https://github.com/lkl/linux )をWebAssemblyにコンパイルして、wasm2cでC言語に変換した上、Visual Studio 2022でコンパイルしてWindows上で実行してみた。

まだWebブラウザでは動いていないが、思ったよりは簡単にWasmに移植できた(個人の感想です) ウケが良ければMUSL libc移植編 → デバイスドライバ活用編 → Webブラウザ上動作編と続ける感じで。。

EDIT: Visual Studioのスクリーンショットを撮りなおし。 memory-control はanonymousなmapしか救えないので、ここ数年スパンではエミュレーション(か、専用の実行環境)しか解が無いかなと。。

先駆者

さすがにこのネタには先駆者が居る。自分の記事でも前に LKLでUSB/IPを使ってみた記事で引いている。

↑ はEmscriptenのpthreadエミュレーションを使用して素直に移植している。

達成したこと

とりあえず、WebAssemblyモジュールにしたLinuxカーネルが正常に動作しているっぽい事は確認した。

アプリ側をLKLに標準で付いてくるpthread/Win32ではなくC++20語彙で新規実装したのでよりポータブル -- Windows版とPOSIX版で完全に同一の実装を使っている
pipe(2) で作った fdにユーザーランドプロセス(に見せかけたホストスレッド)から write(2) して、ホストから読み出すの一連の動作を確認した。LKLカーネル内に複数のユーザプロセスを作る例はそこそこレアなはず。
wasm2cの出力をマルチスレッドで使用している。後述のようなちょっとしたハックが必要。

... いやまぁカーネルだけだと何もできないけど、千里の道も一歩からって言うじゃん。。

ビルド

時間無かったので真面目にビルドシステムを組んでいない。まぁ今後の課題ということで。。

ビルドの準備: make ARCH=lkl menuconfig で .config を作る -- リンク先のファイルはUSB/IPが入っているが、後述のようにコレを入れると何故かVisual Studioで動作しなくなる
runbuild.sh: Linuxの Makefile を使って、Linuxをコンパイルし、 lib.a (カーネル内のサポートライブラリ) と vmlinux.a (実際のカーネル本体) を生成させる。
buildline.sh:
- 後述のリンカスクリプトがWebAssemblyのツールチェーンでは使えない問題の対策として、 vmlinux.a からカーネルの初期化時に実行する関数のリストを llvm-nm で抽出して、 initsyms.gen.c を生成する
- 製作したグルーコード類と一緒にClangに渡し、 wasm-ld (Wasm用のLLDリンカ) でリンクさせ、WebAssemblyモジュール化されたLinuxカーネルである lin.wasm を得る
- wasm2c で lin.wasm をC99ソースコードに変換する
CMakeLists.txt: ランタイムコードやテスト用のロジックと一緒に生成された lin.c をVisual Studioでコンパイルし、実行ファイルを得る

3 までのステップで lin.c と lin.h の2つのファイルができる。これがC言語ソースに変換されたLinuxカーネルで、これをWindowsマシンにコピーしてくれば 4 の作業はWindows側で行える。LinuxのソースコードはWindowsではチェックアウトできない -- 禁止ファイル名である aux が使われていたり、大文字小文字を区別するファイルシステムが必須となっている -- まぁWSLをインストール済の環境であればCygwinとかでチェックアウトできるけど。。

LKLとは

IIJLabの解説を参照のこと ↓

LKLは、Linuxカーネルを通常のアプリケーションにリンクできるようにしたもので、 lkl_host_operations にある各種操作 (Mutexのロックとかスレッドの生成等)をアプリ側で実装することで、Linuxカーネルの各種機能、ファイルシステムとかTCP/IPスタックを簡単にアプリに実装できるようにしたものとなっている。

何故wasm2c？

WABT https://github.com/WebAssembly/wabt/ に収録されているWasm2cを使うと、WebAssemblyのバイナリをCソースコードに変換できる。今回は、これを使ってLinuxカーネルを巨大(102MiB)な1つのCソースコードに変換し、アプリケーションにリンクしている。

他のWasm処理系ではなくWasm2cを採用したのは、 LKLは setjmp longjmp やスレッド、TLSのような機能性を要求していてこれらをv8やWasmerのような既存のWebAssembly処理系ではよくサポートできないため。wasm2cは素直なCコードを出力するので、その出力内容を理解していればこれらの機能をアプリ側で実装できる。また、Cコンパイラでコンパイルした後はgdbとかLLDBのようなネイティブデバッガでデバッグできるので、関数にブレークポイントを張ったり、データブレークポイント(watchpoint)を張って不正なメモリアクセスで止めるといった普通のデバッグ処理を普通にこなせる(超重要)。

例えば、Visual StudioのParallel Stacksビューで、各カーネルスレッドのbacktraceを同時に観察できる。

( ↑ よく見ると w2c_kernel_* がLinuxカーネル内部のシンボルになっている)

ただ、Wasm2cの出力には元のプログラムのデバッグ情報が殆ど含まれない(シンボルだけは残る)ため、アセンブラレベルでデバッグしているのと同じという超つらいデバッグを強いられる。我々はそういうデバッグもできるように訓練されているけど。。

( ↑ デバッガで止めても変数名は表示されない)

ネイティブでLKLを試さずに、いきなりWebAssemblyで実験したのは、 一応自分も元カーネル技術者だしカーネル側のコードで困ることは多分無いだろうと予測したので。よっぽどカーネルに自信ニキでなければ、いきなりwasm2cしたりするのではなく、まずネイティブコードで試した方が良いと思う。もっとも、後述のようにWebAssemblyには普通のCPUにあるものが普通に欠けているので、頑張ったけどWasmではダメというオチがあり得るのが難しいところ。。

また、今回は Emscriptenは使用せず、ClangとLLDを直接使ってwasm2cランタイムのみで動作させている 。以前のDOOM移植実験でも同じ構成を使ったが、今回はlibcすら供給していない。EmscriptenはJavaScriptで書かれたブラウザ向けのランタイムかWASIを選択できるが、そもそもLinuxカーネルは外部ライブラリに依存していない(sprintfとかは自前で持っている)のでEmscriptenのランタイムライブラリが活躍するタイミングが無い。このためEmscriptenは不要と判断した。後述のように __builtin_return_address() はちょっと惜しかったけど。。

移植の過程

なんというかELFでは当然のように存在するものがWebAssemblyには無かったりして、 C言語処理系を復習する良い機会になった 気がする。。普通の人生を送っていて、なかなかcomputed gotoが使えない環境に巡り合うことは無いんじゃないだろうか。Visual Studioでは使えないけど(恨)

`lkl_host_operations`(移植層) の実装

LKLを動作させるためには、スレッドの作成やMutexのロックといった様々な操作をアプリケーション側に持たせてやる必要がある。LKLのソースツリーにはpthreadとWin32でのリファレンス実装が入っているが、今回はシステム全体をEmscriptenか何かに通す可能性を考慮してフルスクラッチした。

機能は小分けにしてあって、同期オブジェクト、スレッドとTLS 、 malloc 、タイマー、 setjmp/longjmp とその他に分かれている。

スレッドの中断( pthread_exit(3) )や setjmp/longjmp に相当する機能性はC++標準ライブラリには存在しないので、C++例外で代用している。 wasm2c のコードは特に途中でデストラクタを呼ばないと困る性質のものは無いため、例外を直接投げてしまってもOKとなる。他のWebAssembly処理系ではダメなものもあるかもしれない。どちらのケースも、WebAssembly一般で実現したければBinaryenの Asyncify で中断可能なコードに変換にする必要があるだろう。

例えば、 thread_exit の実装はC++の try 〜 catch と throw で実現している。専用の例外クラス thread_exit を用意して、スレッドのコードは try の内部で実行する:

実際にスレッドを中断したくなったら、 thread_exit を throw すれば良い。

ちなみに、 setjmp や longjmp も同様に実装しているが、LKLのこれらの使い方がC標準に準拠したものかどうかはちょっと自信が無い。。C++例外でこれらを代替できるようにするには、 setjmp/longjmp 用法がC標準に準拠した方法、つまり、厳密にstack unrollのために使用される必要がある。これらが一般的なgreen threadの実装に使えるという誤解は割とあり、しかも、後述する可変長引数関数のキャストと同様、 大抵の CPUで上手く動いてしまう。

メモリ管理

LKLは巨大なmallocを起動時に一回要求し、それをカーネルのアドレス領域として使用する。これはデフォルトでは64MiB で、今のところWebAssembly移植ではカーネルコマンドラインのパースを実装していないので変更できない。

更に、ユーザランドプロセスのためのスタック領域やバッファも別途確保できる必要があるので、1GiBくらい適当に取っておいて内部をmempoolite https://github.com/jefyt/mempoolite を使用して分割している。

mempooliteは SQLiteのmemsys5アロケーターを抜き出してきたmalloc実装となっている。分割対象のメモリはwasm2cのランタイムを使って起動時に取得している。

wasm_rt_grow_memory はLinear memoryを拡大する。これは本来は WebAssemblyの memory.grow 命令に相当する操作となる。

マルチスレッド対応

今回の実験の重要なハイライトは、 wasm2cの出力で本物のマルチスレッドを実現した ことかもしれない。 wasm2c自体はthreadsプロポーサルに一部対応しているものの、ランタイム側に一切のスレッドサポートが無いため、今回のようなユースケースは非常に珍しいのではないだろうか。いやまぁ前やったような Unity全体をwasm2cに掛ける程では無いかも知れないけど。。

Clangを使ってC/C++プログラムをWasmに変換すると、 __stack_pointer というグローバル変数でスタックを表現するようになる。これがスレッドローカル変数となるように管理してやれば、wasm2cの出力を複数のスレッドで同時に使用しても問題なく使用できる。

wasm2cが出力する関数は、全て第1引数としてインスタンスへのポインタを取るようになっている。

u32 w2c_kernel_syscall(w2c_kernel*, u32, u32, u32);

Wasm的な意味のグローバル変数はインスタンスの構造体(今回の場合 wasm2cが生成したヘッダに宣言される w2c_kernel)に含まれているので、インスタンスへのポインタを thread_local で宣言した上で、個々のスレッドに異なるインスタンスとスタックポインタを割り当てることで __stack_pointer がスレッドローカルになるように配慮している。

... 当然、スレッドのスタック領域もWasmのLinear memory内に存在する必要があるため新規に確保している。

ClangでWasmを生成したときのスタックのレイアウトは Basic C ABIプロポーサルに説明されている通りで、新規スレッドのスタックポインタは拡張後のメモリページの末尾 - αを指すことになる。

現在のコードはスレッドが終了してもスタック領域を回収していないのでメモリリークが発生する。終了したスレッドのスタック領域をリサイクルする機構を用意する必要があるだろう。

(今回は比較的真面目にマルチスレッドに対応したが、本来LKLは非 SMP カーネルであり、歴史的なUNIXのようにカーネル内を同時に実行できるスレッドは高々1つに制約されている。ただ、排他をホストOSの同期プリミティブで実施している都合上、スレッドが平行動作する瞬間を避けられないため、比較的ちゃんとしたスレッドサポートが必要となる。)

マルチプロセス対応

LKLは基本的に "カーネル機能をライブラリとして使う" ことを想定してデザインされており、上に単一のLinuxアプリを載せて動かすことはできる(Hijackライブラリ)ものの、通常のLinuxカーネルのように複数のユーザランドプロセスを動作させることは想定されていないようだ。

というわけで、今回はカーネル側に手を入れてプロセス作成用のインターフェースを追加してみた。

アプリケーションからLKL内のsyscallを使う場合、 hostスレッド と呼ばれるダミーのスレッドが使用される。これはカーネルスレッドであるがカーネル内には実際のコードが存在しない特殊なスレッドとして実装されている。つまり、スレッドは空の関数 host_task_stub をエントリポイントとして持つが、このエントリポイントは arch/lkl 内で特別扱いされている(例えば、 copy_threadの処理が途中で終わるようになっている)。

で、このhostスレッドを作成する際のフラグとして、

のように CLONE_THREAD が指定されており、 clone(2) のmanページに書かれている通り、このフラグは呼出し元のプロセスにスレッドを追加する作用となる。LKLにおける通常のシチュエーションでは( host0 として最初に設定されるhostスレッドである) init(8) 、 pid == 1 の子スレッドとして作成されることになる。

... つまり、この CLONE_THREAD を指定せずにhostスレッドを作成する方法を別途用意すれば、新しいpid(や独立したファイルデスクリプタテーブル)を持ったhostスレッドを作成できる。今回は、Linuxカーネル側に wasmlinux_newtask 関数として新規プロセス用と新規スレッド用のhostスレッド生成ルーチンを用意し、

それをユーザーランド側から使う実装とした。

リンカスクリプト使えない問題

これはマジで苦労した。。LKLを含む通常のLinuxでは、カーネル起動時の初期化を行う関数への関数ポインタを特定のセクションに集め、それを配列と見做して順次実行する形でカーネルの初期化を実行している。

通常のCPUアーキテクチャでは ↑ のようにこの処理はリンカスクリプトで実現されるが、 WebAssemblyのリンカではリンカスクリプトが使用できない ので、移植者毎にチャートが異なって面白いポイントになると思う。

↑ のように、他にも悩んでいる人は居る。ちなみに、 ↓ 先駆者は完全に手書きしている。

LKL自体は割と頻繁に更新されており、流石に大きなパッチをLinux側に適用するのは気が引ける。というわけで、今回は一旦連続したダミー変数を用意して、起動時にそこにコピーするという手順で実装した。

Linuxのビルドシステムはリンク前のLinuxを vmlinux.a として残すので、これに llvm-nm を掛けてシンボルリストを抽出する
呼び出し順にソートした表と、関数ポインタの配列を準備しCソースコードを生成する -- 生成したソースコード
カーネル起動時に表から配列へのコピーを行う

更に、通常のLinuxでは初期化関数は static が付いていて外部から参照できないので、 __wasm__ 限定で外すようにカーネル側をパッチしている。

リンカスクリプト対策は他に jiffies のエイリアス名定義、初期スレッドのスタックや、スケジューラークラスの順序で入れている。

まぁぶっちゃけWasm限定であればリンカの作成自体はそこまで難しくないと思うので、たぶんリンカを自作するのが対策としては一番カタいんではないだろうか。。

Computed gotoが使えない問題

GNU系のC言語では goto の飛び先に使うラベルを変数に代入する機能が存在する。で、通常のCPUでは、この時に実際に代入されるのはCPU命令の実際のアドレスになっている。... が、WebAssemblyでは個々の命令はメモリアドレスを持たないので、このラベルの代入機能(computed goto機能)は使えない。

Linuxカーネルでは、デバッグ用にこのComputed goto機能を使って実行時点のアドレスを表示する処理が多用されているので、適当にパッチして使われないようにした。

また、現状のClangはEmscriptenが居ないと __builtin_return_address も使えないので同様に消している。

C言語の未定義挙動への依存問題

LKLは lkl_syscall 関数を提供し、Linuxカーネルのsyscallを呼出せるようにしている。(ただし、実際のLKL活用アプリは、LKLが用意したアプリ向けのライブラリで read(2) 等のsyscallを呼ぶのが本来の用法となっている -- 今回はLKL提供のユーザーランドライブラリは一切使用していない)

しかし、この lkl_syscall の実装には問題があり、 C言語の未定義挙動に依存している 。lkl_syscall の実体は、 syscall_table 配列に格納された関数ポインタを呼ぶだけになっているが、

この syscall_handler_t へのキャストが未定義挙動を引き起す。

C言語の関数ポインタを変換してから呼出す際は "compatible" でなければならないとされており (6.3.2.3) 、

If a converted pointer is used to call a function whose type is not compatible with the referenced type, the behavior is undefined.

関数ポインタが compatible である条件 (6.7.6.3) の1つとして、 ... (ellipsis) の使用有無が一致しているという要求がある。

For two function types to be compatible, both shall specify compatible return types. Moreover, the parameter type lists, if both are present, shall agree in the number of parameters and in use of the ellipsis terminator ; corresponding parameters shall have compatible types.

今回のキャストは、全てのsyscallハンドラが固定長の引数を持つにもかかわらず可変長引数関数型である syscall_handler_t にキャストした上で呼出しを行うため、C言語的に未定義挙動となる。実際にWebAssemblyではこれは正常に動作しない(Clangが使用しているWebAssembly内のABIの都合)。

今回は引数の個数を明示的に渡すAPIを別途作成する形で対策した。

Linuxのsyscallの引数は高々6個までなので、関数ポインタのバリエーションとしても0個〜 6個までの7パターンあれば十分ということになる。というわけで syscall_handler0_t 〜 syscall_handler6_t までの型を用意して正しい型にキャストしてから呼出せば良い。

... ここまで追ったんならアップストリームすれば良いじゃんというのは有るかもしれない。が、実はこのキャスト、つまり 固定長整数引数関数 ←→ 可変長整数引数関数 のキャストは大抵のCPUのABIで 正常に動いてしまう 。WebAssemblyでのLinux syscall -- 世界で自分しか使っていない -- のためにわざわざパッチするのもちょっとなぁということで保留している。

残件

VisualStudio + Win10 かつ USB/IP を組込むと起動しなくなる。これ多分USB/IPがタイマに依存していて、 /init の起動よりも前にタイマが正常動作することを期待している所為なんじゃないかという気がしている。実際 Linux上で動作させても正常に動いていないのでワークアラウンドしていて、この辺を真面目に追わないとUSBが使えない。。まぁ面倒なのでUSB/IPの初期化だけ後回しにするのが簡単な気はする。。

リンカに使っているLLD(wasm-ld)は --start-group や --end-group を何故かサポートしていないので、今のところLinuxのMakefileは完走しない。まぁ実用上は困らないので放置してるけど。。

make -f ./scripts/Makefile.vmlinux_o
wasm-ld: error: unknown argument: --start-group
wasm-ld: error: unknown argument: --end-group
make[2]: *** [scripts/Makefile.vmlinux_o:61: vmlinux.o] エラー 1

かんそう

かんたんだった(KONAMI)

何の役に立つのか

... 正直な所こんなのよりも LinuxのユーザランドABIをWebAssembly上に定義する事のほうが100倍重要で役に立つ と思う。実用上はカーネルまでWebAssemblyにする必要は無くて、 ARMなりRISC-VなりのLinuxカーネル上で、WebAssemblyで配付されるバイナリを実行する環境の方が需要があるはず。

WASIとかWASIX https://wasix.org/ は mmap のような重要な機能性を欠いているので、どうやっても共通バイナリを配付する基盤としては厳しいもんがある。qemu-userを使ってamd64上のDockerでARMバイナリを実行するテクニックがあるように、WasmLinuxのABIだけ定義しておいて(カーネルは無しで)、ABI変換レイヤだけでWebAssemblyなアプリを直接実行するのが美味いんじゃないかなと。

仮にWebブラウザ上で実行したくなったとしても、カーネルをx86エミュレータ上で実行してしまった方がパフォーマンスやユーザビリティの面で優れていると思う。どっちにせよ通常のアプリを実行するためには mmap はエミュレーションしないといけないので。

じゃぁお前がやれよ というのは非常にごもっともなんですが、コレは 妥協と追求のバランスがかなり難しい 。WebAssemblyはかなり特殊なアーキテクチャで、既存のLinux ABIが想定していないような機能的な欠落がある(関数ポインタがメモリアドレスじゃないとか)。それをエミュレーションするのか制約事項にするのかというのを上手いバランスに落とし込むのは相当なカリスマ性が必要かなと。。

可能な限り多くのパートをWebAssemblyで動かす恩恵としては、 自作CPU対応が容易になる という点があるかもしれない。LLVMのバックエンドを自作CPU向けに考えたり、抜けの無いC言語ABIを用意するのはなかなか苦行だが、WebAssemblyの処理系を自前のCPUに載せるだけであれば、そこまで難しくは無いのではないか説。

次の一手

既に MUSL libcは移植してあるので、ユーザランドのバイナリをDLLにして動かせないかなと。。 夢はでっかくBusyBox完走を目指したい ところ。

このためには、

sbrk のようなヒープ確保手法の実装
clone や vfork のようなプロセス/スレッド関連のsyscallエミュレーション
シグナル関連

等が必要で、この辺はLKLだけでは実装できないので自前の簡単なマイクロカーネルを実装してどうにかしたい。

実装としては、PRoot https://github.com/proot-me/proot のように一部のsyscallをフィルタして自前の実装に振り替える形になると考えられる。

ファイルシステムは、まぁ適当な感じで。。ホストシステムとのpipeは既に実現できているので、ちゃんとした奴はFUSEで用意すれば良いだろう。

mmap のエミュレーションは、実は直近では真面目なものは無くても良い -- busyboxはmmapに依存しない。実際の実装では、ホストOS側の mmap を使う(hardmmu)か、 copy/v86 のように全てのload/storeを仮想TLB経由に変換する(softmmu)といった手法が必要になる。特にWebブラウザをサポートするためにはsoftmmuは必須になるが、そのぶん難易度も高い。

... この辺を突き詰めて行くと、 Linux互換カーネルを実装する方向になっていくのではないだろうか。。特にWebブラウザ上ではLinux側のデバイスドライバを使いたいモチベーションって限りなく低いし。。なので、一旦は可能な限りLinux(LKL)を生かして実装したあと、自前のLinux互換カーネルに置き換えていくのは良いアプローチな気はしている。

先駆者