Blog posts by @retrage

mirror of https://retrage.github.io/

LKL.js: Linux kernelを直接JavaScript上で動かす

Linux kernelを直接JavaScript上で動かした. つまり,JSLinuxのようにEmulatorをJavaScriptで作成し, その上でLinuxを動かすのではなく, JavaScriptで書かれたLinuxを生成し,それを動かす,ということである.

f:id:retrage01:20180721131907p:plain
LKL.js Architecture

リポジトリは以下の通り.

なお 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であるので, LinuxFreeBSD, Windowsなど様々なOSのユーザ空間で動作する.

Emscripten

EmscriptenLLVMを利用したC/C++からJavaScript/WebAssemblyへのトランスパイラである. Emscriptenはlibcやpthreadなどへも対応しており,Unix-likeな環境を用意している.

LKLをEmscriptenJavaScriptに移植できるか?

LKLは様々なOSで動作し,EmscriptenUnix-likeな環境を用意する. では,LKLはEmscriptenJavaScriptに移植することはできるだろうか.

移植する前に

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

ここで重要なのが$CFLAGSar.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で扱うにはvmlinuxLLVM 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.bcllvm-disを用いてLLVM bitcodeからLLVM IRへ変換する. 次にEmscriptendlmalloc.bclibc.bcpthreads.bcなどのファイルを LLVM IRへと変換する. 最後にrename_symbols.pyboot.llに対して実行する. このようなことを行うのには理由がある. それは,Linux kernelで利用されている関数名とlibcなどで利用されている関数名が 衝突してしまうからである. 通常のLKLでは,ELFの仕様を利用しうまくLinux kernelの関数を隠匿化することにより この衝突を回避している.一方で,Emscriptenでは名前空間などが存在しないために, このような衝突が発生してしまう. そこで,あらかじめリンクされる予定のLLVM bitcodeをLLVM IRに変換し, 衝突するであろう関数名をrename_symbols.pyで書き換えることにより衝突を回避している.

また,rename_symbols.pyでは, Linux kernelに含まれる,inline asmをEmscriptenemscripten_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.cset_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はマクロであり,strfnを引数にとり, .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_paramstrと比較を行い, 一致した場合に設定してある(*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が出力されるだけで全く実用には適さない. これには次のような問題点が存在するためである.

  1. kthreadの生成に失敗する
  2. rootfsのマウントに失敗する
  3. init

また,Emscriptenでのpthreadのサポートがあまりよくない. Little Kernel(LK)からsemaphore, mutex, threadの機能を抜き出し, これらをgreen threadとして扱うLKLを作成した.

これを用いたLKL.jsを作成することを予定している.

まとめ

JavaScriptで書かれたLinux kernelをLKLからEmscriptenにより生成し, これが起動し,dmesgが出力されることを確認した. 通常のマシンとJavaScriptではアーキテクチャが大きく異なるが, いくつかの修正とworkaroundを加えることにより, 多少なりとも動作することがわかった.

参考文献