LKL.js: Linux kernelを直接JavaScript上で動かす
Linux kernelを直接JavaScript上で動かした． つまり，JSLinuxのようにEmulatorをJavaScriptで作成し， その上でLinuxを動かすのではなく， JavaScriptで書かれたLinuxを生成し，それを動かす，ということである．
リポジトリは以下の通り．
なお lkl.js Demo にデモを用意した． SharedArrayBufferを有効にして試してみてほしい．
Linux Kernel Library (LKL)
ここでは，Linux kernelをLibrary OSの形態の1つであるAnykernelにする
Linux Kernel Library (LKL)を利用する．
LKLはLinux kernelのforkとして存在し，arch/lklにのみLKL specificな
コードをおき，その他は全く変更を加えずに動作するように設計されている．
これによりmainlineへの追従性を高めている．(現在はv4.16)
LKLはAnykernelであるので，
LinuxやFreeBSD, Windowsなど様々なOSのユーザ空間で動作する．
Emscripten
EmscriptenはLLVMを利用したC/C++からJavaScript/WebAssemblyへのトランスパイラである． Emscriptenはlibcやpthreadなどへも対応しており，Unix-likeな環境を用意している．
LKLをEmscriptenでJavaScriptに移植できるか？
LKLは様々なOSで動作し，EmscriptenはUnix-likeな環境を用意する． では，LKLはEmscriptenでJavaScriptに移植することはできるだろうか．
移植する前に
clangでのLinux kernelのビルドの現状
そもそもLinux kernelとは，gcc拡張に依存しており， clangなどではそもそも扱えないのでは，という疑問がある． かつてLLVM Linuxというプロジェクトが立ち上がるぐらいには Linux kernelをclangでコンパイルするのは困難であった． しかし，2017年頃より，Androidの開発者らにより， Linux kernelがclangでもコンパイル可能となった．
Linux kernelのビルドの流れ
Linux kernelのビルドの流れをみていく．
最初に，makeが行われると，kconfigの設定からビルドされるソースコード(.c/.S)が決定され，
コンパイルが行われる．コンパイルにより生成されたオブジェクトファイル(*.o)は
一度機能ごとにarによりbuilt-in.oなどの名前でアーカイブ化される．
最後に，まとめて得られたbuilt-in.oをリンクすることによりvmlinuxを得る．
以上がLinux kernelにおける簡単なビルドの流れとなっている．
LKLをEmscriptenで移植
では，実際にどのようにLKLをEmscriptenで移植していくのかをみていく．
Emscriptenに限らず，LLVMを利用する場合，次のような流れでターゲットにコンパイルする．
Source -> LLVM IR -> Target
このように一度LLVM IR (.bc/.ll)に変換してからターゲットに変換される． なお，Emscriptenでは通常のリンクに当たる部分がLLVM IRからJavaScriptへの変換となっている． このため，最初に全て(Emscriptenの用意するlibcなども含めて)をLLVM IRに変換する必要がある．
vmliux.bcの生成
emcc (Emscripten clangのwrapper)でのビルドは次のようになっている
make -C tools/lkl CC="$CC $CFLAGS" AR="$PY $PWD/ar.py" V=1
ここで重要なのが$CFLAGSとar.pyの2つである．それぞれみていく．
(なお，CC="$CC $CFLAGS"となっているのは無理やりCFLAGSを渡すためである)
$CFLAGSは次のようになっている．
CFLAGS="$CFLAGS -s WASM=0"
CFLAGS="$CFLAGS -s ASYNCIFY=1"
CFLAGS="$CFLAGS -s EMULATE_FUNCTION_POINTER_CASTS=1"
CFLAGS="$CFLAGS -s USE_PTHREADS=1"
CFLAGS="$CFLAGS -s PTHREAD_POOL_SIZE=4"
CFLAGS="$CFLAGS -s TOTAL_MEMORY=1342177280"
ここでは，Emscriptenに渡すオプションを指定している． 詳細についてはEmscriptenのマニュアルを参考にしてほしい．
さらに以下のような定義を指定している．
CFLAGS="$CFLAGS -DMAX_NR_ZONES=2"
CFLAGS="$CFLAGS -DNR_PAGEFLAGS=20"
CFLAGS="$CFLAGS -DSPINLOCK_SIZE=0"
CFLAGS="$CFLAGS -DF_GETLK64=12"
CFLAGS="$CFLAGS -DF_SETLK64=13"
CFLAGS="$CFLAGS -DF_SETLKW64=14"
これらは本来Linux kernelビルド時に空のファイルをコンパイルするなど して得られる値であり，今回の場合，これらは直接得ることができない． そのため，あらかじめx86_64でビルドしたときに得られた値をここで指定している．
次にar.pyをみていく．以下のような簡単なものとなっている．
filename = "objs"
def main():
if not os.path.exists(filename):
with open(filename, "w") as fp:
pass
objs = []
for i, arg in enumerate(sys.argv):
if ".o" in arg and not "built-in" in arg and i > 2:
objs.append(arg)
with open(filename, "aw") as fp:
for obj in objs:
if not obj is "":
fp.write(obj + " ")
return 0
先に説明したように，本来Linux kernelでは
コンパイルによって得られたオブジェクトファイルを
arによりまとめ，最後にリンクを行うことでvmlinuxを得る．
Emscriptenで扱うにはvmlinuxをLLVM bitcodeとして得る必要がある．
LLVMにはllvm-linkという複数のLLVM bitcodeファイルをリンクして
1つのLLVM bitcodeを得るリンカが存在する．
vmlinux.bcを得るにはllvm-linkを利用する必要があるが，
ここで1つ問題がある．llvm-linkは通常のリンカのように，
アーカイブファイルを引数としてとることができない．
そのため，本来アーカイブにされるオブジェクトファイルを記録しておく必要がある．
ここでは，objsにそれらをまとめてファイルパスとして記録しておく．
次に実際にvmlinux.bcが生成される部分をみていく．
scripts/link-vmlinux.shに次のような変更が加えられている．
info CLEAN obj
python "${srctree}/clean-obj.py"
info GEN link-vmlinux.sh
python "${srctree}/link-vmlinux-gen.py"
info LINK vmlinux
bash "${srctree}/link-vmlinux.sh"
clean-obj.pyでは先に得られたobjsより重複するファイルパスを削除する．
次にlink-vmlinux-gen.pyではobjsよりllvm-linkを行う
vmlinux-link.sh(scripts/link-vmlinux.shとは異なる)を生成する．
最後にlink-vmlinux.shを実行し，vmlinux.bcを得る．
以上がvmlinux.bcを得るまでの流れとなっている．
boot.jsの生成
次に実際にJavaScriptが生成されるまでをみていく．
先に説明したとおり，LKLはLibray OSの1つであるので，vmlinuxそれ単体では動作せず，
アプリケーションとなる部分があってはじめて動作する．ここでは，LKLのHello, worldに相当する
tools/lkl/tests/bootをターゲットとする．
$LINK -o $LKL/tests/boot.bc \
$LKL/tests/boot-in.o $LKL/lib/liblkl-in.o $LKL/lib/lkl.o
まず，先に生成したvmlinux.bc ($LKL/lib/lkl.o)と
ホスト依存部分$LKL/lib/liblkl-in.o，
アプリケーション部分$LKL/tests/boot-in.oをリンクして$LKL/tests/boot.bcを得る．
次に以下のようなことを行う．
$DIS -o $LKL/tests/boot.ll $LKL/tests/boot.bc
$CP ~/.emscripten_cache/asmjs/dlmalloc.bc js/dlmalloc.bc
$CP ~/.emscripten_cache/asmjs/libc.bc js/libc.bc
$CP ~/.emscripten_cache/asmjs/pthreads.bc js/pthreads.bc
$DIS -o js/dlmalloc.ll js/dlmalloc.bc
$DIS -o js/libc.ll js/libc.bc
$DIS -o js/pthreads.ll js/pthreads.bc
$PY rename_symbols.py $LKL/tests/boot.ll $LKL/tests/boot-mod.ll
最初にboot.bcをllvm-disを用いてLLVM bitcodeからLLVM IRへ変換する．
次にEmscriptenのdlmalloc.bcやlibc.bc，pthreads.bcなどのファイルを
LLVM IRへと変換する．
最後にrename_symbols.pyをboot.llに対して実行する．
このようなことを行うのには理由がある．
それは，Linux kernelで利用されている関数名とlibcなどで利用されている関数名が
衝突してしまうからである．
通常のLKLでは，ELFの仕様を利用しうまくLinux kernelの関数を隠匿化することにより
この衝突を回避している．一方で，Emscriptenでは名前空間などが存在しないために，
このような衝突が発生してしまう．
そこで，あらかじめリンクされる予定のLLVM bitcodeをLLVM IRに変換し，
衝突するであろう関数名をrename_symbols.pyで書き換えることにより衝突を回避している．
また，rename_symbols.pyでは，
Linux kernelに含まれる，inline asmをEmscriptenのemscripten_asm_const_int
に変換するなどの操作も行なっている．
以上によって得られたboot-mod.llより
EMCC_DEBUG=1 $CC -o js/boot.html $LKL/tests/boot-mod.ll $CFLAGS -v
によりHTMLとJSを得る．
動かすための修正
以上により得られた「完全に」JavaScriptで書かれたLinux kernelとそれを利用した アプリケーションboot.jsであるが，このままでは動作しない． これは，通常のマシンとJavaScriptとではそもそものアーキテクチャが 大きく異なっていることに由来する．それでもいくつかの修正を加える．
inline assemblyの置換
Linux kernelでは基本的にarch以下にアーキテクチャ依存のコードをおき，
それ以外ではアーキテクチャ非依存のコードとなるように配置されている．
しかし，一部のコードでは，コンパイラによる最適化により意味のあるコードが
コンパイル時に失われないように空のinline assemblyが挿入されている場合がある．
以下はその一例，kernel/time/time.cのset_normalized_timespec64である．
void set_normalized_timespec64(struct timespec64 *ts, time64_t sec, s64 nsec)
{
while (nsec >= NSEC_PER_SEC) {
/*
* The following asm() prevents the compiler from
* optimising this loop into a modulo operation. See
* also __iter_div_u64_rem() in include/linux/time.h
*/
asm("" : "+rm"(nsec));
nsec -= NSEC_PER_SEC;
++sec;
}
while (nsec < 0) {
asm("" : "+rm"(nsec));
nsec += NSEC_PER_SEC;
--sec;
}
ts->tv_sec = sec;
ts->tv_nsec = nsec;
}
このようなinline assemblyはLLVM bitcodeからJavaScriptへの変換に失敗する要因となる．
このため，asm("" : "+rm"(nsec));をEmscriptenで定義されている
CからJSのコードを呼ぶinline assemblyemscripten_asm_const_intに置き換えることで対応する．
early_paramの修正
Linux kernelでは，early_paramというものが存在する．
これは，include/linux/init.hに以下のように定義される．
struct obs_kernel_param {
const char *str;
int (*setup_func)(char *);
int early;
};
/* snip */
#define __setup_param(str, unique_id, fn, early) \
static const char __setup_str_##unique_id[] __initconst \
__aligned(1) = str; \
static struct obs_kernel_param __setup_##unique_id \
__used __section(.init.setup) \
__attribute__((aligned((sizeof(long))))) \
= { __setup_str_##unique_id, fn, early }
/* snip */
#define early_param(str, fn) \
__setup_param(str, fn, fn, 1)
つまり，early_paramはマクロであり，strとfnを引数にとり，
.init.setupセクションに置かれるobs_kernel_param構造体であることがわかる．
通常のLKLのビルドで生成されるarch/lkl/kernel/vmlinux.ldsを参照すると
以下のようであることから，.init.setupは__setup_startと__setup_endで
挟まれたように配置されることがわかる．
__setup_start = .; KEEP(*(.init.setup)) __setup_end = .;
これらのシンボルはinit/main.cにおいて次のように使われる．
ここでは，Linux kernelのboot parameter(param)の1つについて，
.init.setupにあるobs_kernel_paramのstrと比較を行い，
一致した場合に設定してある(*setup_func)(char*)を
valを引数として実行している．
/* Check for early params. */
static int __init do_early_param(char *param, char *val,
const char *unused, void *arg)
{
const struct obs_kernel_param *p;
for (p = __setup_start; p < __setup_end; p++) {
if ((p->early && parameq(param, p->str)) ||
(strcmp(param, "console") == 0 &&
strcmp(p->str, "earlycon") == 0)
) {
if (p->setup_func(val) != 0)
pr_warn("Malformed early option '%s'\n", param);
}
}
/* We accept everything at this stage. */
return 0;
}
まとめると，do_early_paramではearly_paramによって登録されている
setup_funcをboot parameterにより実行する，という形になっている．
ただ，これはELFのシンボルを利用しているために，JavaScriptでは正しく実行されない． このため，ここで呼ばれるであろう関数について，以下のようにハードコードする．
static int __init do_early_param(char *param, char *val,
const char *unused, void *arg)
{
/* XXX: There is a lot of early_param, but hardcode in init/main.c */
const char *early_params[MAX_INIT_ARGS+2] = { "debug", "quiet", "loglevel", NULL, };
int i;
for (i = 0; early_params[i]; i++) {
if (strcmp(param, early_params[i]) == 0 ||
(strcmp(param, "console") == 0 &&
strcmp(early_params[i], "earlycon") == 0)
) {
switch (i) {
case 0: /* debug */
if (debug_kernel(val) != 0)
pr_warn("Malformed early option '%s'\n", param);
break;
case 1: /* quiet */
if (quiet_kernel(val) != 0)
pr_warn("Malformed early option '%s'\n", param);
break;
case 2: /* loglevel */
if (loglevel(val) != 0)
pr_warn("Malformed early option '%s'\n", param);
break;
default:
pr_warn("Unknown early option '%s'\n", param);
}
}
}
/* We accept everything at this stage. */
return 0;
}
initcallの修正
先のearly_param同様，初期化で呼ばれるinitcallも
ELFのシンボルを用いて呼ばれる関数を管理している．
JavaScript単体では，どの関数が呼ばれるべきかはわからない．
そのため，通常のLKLのビルドで生成されるSystem.map
を用いて関数をあらかじめ取得し，そこから関数呼び出しを行う．
with open(sys.argv[1], "r") as fp:
for line in fp:
if SIG in line:
symbol = line[:-1].split(" ")[2]
try:
level = int(symbol[-1])
initcall = symbol[symbol.index(SIG)+len(SIG):len(symbol)-1]
initcalls[level].append(initcall)
except ValueError:
pass
for level, row in enumerate(initcalls):
print("/* initcall{} */".format(level))
print("EM_ASM({")
for initcall in row:
if initcall in blacklist:
print(" /* _"+initcall+"(); */")
else:
print(" _"+initcall+"();")
print("});")
これによって得られるコードをdo_initcallsにハードコードする．
EM_ASMはCにJSのコード直接記述するinline assemblyである．
static void __init do_initcalls(void)
{
/* XXX: initcalls are broken, so hardcode here */
/* initcall0 */
EM_ASM({
_net_ns_init();
});
/* initcall1 */
EM_ASM({
_lkl_console_init();
_wq_sysfs_init();
_ksysfs_init();
/* snip */
});
}
デモと結果
冒頭で紹介したように，lkl.jsではpthreadを利用しているため， SharedArrayBufferを有効にする必要がある． 現在のブラウザではSharedArrayBufferが実装されているものの， Spectreのmitiagtionのため，デフォルトでは無効になっている． そのためこれを有効にした上で実行してみてほしい．
start_kernelの実行結果を以下に示す．
[ 0.000000] Linux version 4.16.0+ (akira@akira-Z270) () #13 Tue Jul 17 23:01:19 JST 2018
[ 0.000000] bootmem address range: 0x675000 - 0x1674000
[ 0.000000] On node 0 totalpages: 4095
[ 0.000000] Normal zone: 36 pages used for memmap
[ 0.000000] Normal zone: 0 pages reserved
[ 0.000000] Normal zone: 4095 pages, LIFO batch:0
[ 0.000000] pcpu-alloc: s0 r0 d32768 u32768 alloc=1*32768
[ 0.000000] pcpu-alloc: [0] 0
[ 0.000000] Built 1 zonelists, mobility grouping off. Total pages: 4059
[ 0.000000] Kernel command line: mem=16M loglevel=8
[ 0.000000] Parameter is obsolete, ignored
[ 0.000000] Parameter is obsolete, ignored
[ 0.000000] Dentry cache hash table entries: 2048 (order: 1, 8192 bytes)
[ 0.000000] Inode-cache hash table entries: 1024 (order: 0, 4096 bytes)
[ 0.000000] Memory available: 16144k/16380k RAM
[ 0.000000] SLUB: HWalign=32, Order=0-3, MinObjects=0, CPUs=1, Nodes=1
[ 0.000000] NR_IRQS: 1024
[ 0.000000] lkl: irqs initialized
[ 0.000000] clocksource: lkl: mask: 0xffffffffffffffff max_cycles: 0x1cd42e4dffb, max_idle_ns: 881590591483 ns
[ 0.000100] lkl: time and timers initialized (irq1)
[ 0.001100] pid_max: default: 4096 minimum: 301
[ 0.009400] Mount-cache hash table entries: 1024 (order: 0, 4096 bytes)
[ 0.009900] Mountpoint-cache hash table entries: 1024 (order: 0, 4096 bytes)
[ 0.327100] console [lkl_console0] enabled
[ 0.329600] clocksource: jiffies: mask: 0xffffffff max_cycles: 0xffffffff, max_idle_ns: 19112604462750000 ns
[ 0.329700] xor: automatically using best checksumming function 8regs
[ 0.341199] NET: Registered protocol family 16
[ 0.388999] clocksource: Switched to clocksource lkl
[ 0.414100] NET: Registered protocol family 2
[ 0.437700] tcp_listen_portaddr_hash hash table entries: 512 (order: 0, 4096 bytes)
[ 0.438199] TCP established hash table entries: 1024 (order: 0, 4096 bytes)
[ 0.439000] TCP bind hash table entries: 1024 (order: 0, 4096 bytes)
[ 0.439600] TCP: Hash tables configured (established 1024 bind 1024)
[ 0.443200] UDP hash table entries: 256 (order: 0, 4096 bytes)
[ 0.444000] UDP-Lite hash table entries: 256 (order: 0, 4096 bytes)
[ 0.472100] workingset: timestamp_bits=30 max_order=12 bucket_order=0
[ 0.863100] SGI XFS with ACLs, security attributes, no debug enabled
[ 0.923700] jitterentropy: Initialization failed with host not compliant with requirements: 2
[ 0.924599] io scheduler noop registered
[ 0.924900] io scheduler deadline registered
[ 0.933099] io scheduler cfq registered (default)
[ 0.933500] io scheduler kyber registered
[ 1.633500] NET: Registered protocol family 10
[ 1.658400] Segment Routing with IPv6
[ 1.660800] sit: IPv6, IPv4 and MPLS over IPv4 tunneling driver
[ 1.674200] ------------[ cut here ]------------
[ 1.675500] WARNING: CPU: 0 PID: 0 at arch/lkl/kernel/setup.c:188 (null)
[ 1.675899] Call Trace:
[ 1.676200]
[ 1.676999] ---[ end trace 941dc55fe0966cff ]---
[ 1.684299] Warning: unable to open an initial console.
[ 1.685200] This architecture does not have kernel memory protection.
pthread_join((pthread_t)tid, NULL): No such process
lkl_start_kernel(&lkl_host_ops, "mem=16M loglevel=8") = 0
現在の問題点
以上より，JavaScript上で直接Linux kerenlが起動したことが確認できた． しかし，現状ではdmesgが出力されるだけで全く実用には適さない． これには次のような問題点が存在するためである．
- kthreadの生成に失敗する
- rootfsのマウントに失敗する
- init
また，Emscriptenでのpthreadのサポートがあまりよくない． Little Kernel(LK)からsemaphore, mutex, threadの機能を抜き出し， これらをgreen threadとして扱うLKLを作成した．
これを用いたLKL.jsを作成することを予定している．
まとめ
JavaScriptで書かれたLinux kernelをLKLからEmscriptenにより生成し， これが起動し，dmesgが出力されることを確認した． 通常のマシンとJavaScriptではアーキテクチャが大きく異なるが， いくつかの修正とworkaroundを加えることにより， 多少なりとも動作することがわかった．
参考文献
- https://github.com/lkl/linux
- https://github.com/kripken/emscripten
- https://llvm.org/
- https://clang.llvm.org/
- https://wiki.linuxfoundation.org/llvmlinux
- https://lwn.net/Articles/734071/
- http://llvm.org/docs/CommandGuide/llvm-link.html
- https://0xax.gitbooks.io/linux-insides/Concepts/linux-cpu-3.html
- https://github.com/littlekernel/lk