Constellation Scorpius

Technical notes

Threading Primitives in WebKit (Briefly)

The nice overview of threading primitives in Chromium is posted in Chromium Advent Calendar. As Chromium/Blink maintain their own threading primitives, threading primitives in WebKit are also largely changed from the fork. In this post, I introduce threading primitives in WebKit briefly.

WTF::Thread

In old days, we have ThreadIdentifier, which is actually uint32_t identifier to a thread. We have an internal hash table between ThreadIdentifier and PlatformThread like pthread_t.

  1. createThread(String name, Function) -> ThreadIdentifier
  2. waitForCompletion(ThreadIdentifier) -> bool

However, this design has several problems. First, this has very limited extensibility: attaching various additional information to thread is not as easy as we extend class. Second, this interface requires looking up the corresponding thread handle from the hash table every time we call threading operations. Finally, and the worst problem is that we cannot know whether the given ThreadIdentifier is used. The following code explains the above problem. We cannot manage the lifetime of the holder of the thread (in the example, ThreadIdentifier). This means that ThreadIdentifier must be monotonically increasing.

1
2
3
4
5
ThreadIdentifier thread1 = createThread(...);
waitForCompletion(thread1);

ThreadIdentifier thread2 = createThread(...);
// thread1 should not be the same number to thread2 since someone would retrieve some information from thread1.

Thread class in WTF (of course, WTF stands for web template framework) is a brand new abstraction over native threads to solve the above problems. This is ref-counted Thread object. Thread::create(...) -> Ref<Thread> creates it and it offers threading operations as its member functions. For example, thread->waitForCompletion() is join function in WebKit threading.

1
2
3
4
5
6
7
8
9
{
    Ref<Thread> thread = Thread::create("thread name", [&] {
        ...
    });
    thread->waitForCompletion();

    // Thread object is live. But thread is already finished.
}
// Thread is destructed.

This Thread class is portable. It just works (TM) on macOS, Linux (and UNIX environments including FreeBSD), and Windows. It is important to build advanced features on the top of this Thread abstraction.

Thread has one on one correspondence between a native thread and Thread. This ref-counted object is held in thread local storage (TLS) and retained while Thread is running. We can get the current thread from TLS by calling Thread::current() -> Thread&. So, for example, checking whether the given Thread is the current one is done by thread == &Thread::current() pointer comparison.

And user of this thread can retain Thread to perform threading operations onto it. Since Thread is ref-counted, Thread is destroyed when nobody retains it. When (1) no users retain this thread and (2) the thread itself finishes, Thread will be destructed.

By introducing Thread, (1) we can easily attach any information to Thread as we want. Moreover, (2) we can manage the lifetime of the holder of the thread by ref-counted Thread object. We can destroy Thread when it is no longer used. When using ThreadIdentifier, we were not able to recycle unused ThreadIdentifier since it may be used in some places.

Note that Thread::current() works even if we call it from non-WebKit-created threads (a.k.a. external threads). At that time, Thread is created and stored in TLS. If the thread finishes, this TLS and held Thread are automatically destroyed.

Advanced features of Thread

One of the interesting aspect of our Thread is that it has bunch of advanced features that are not typically offered in standard libraries like C++ std::thread. This is derived from the fact that our WTF library is tightly coupled with JavaScriptCore (JSC). Thread offers advanced features that is necessary for JSC.

For example, Thread::suspend() -> Expected<void, PlatformSuspendError> is platform independent way to suspend the thread. This is portable (working in macOS, Linux, and Windows) and used for garbage collection (GC)’s stop the world1. There is a list of such advanced features in our Thread ;). They are building block of our GC in JSC.

  1. Thread::suspend() -> Expected<void, PlatformSuspendError>
  2. Thread::resume() -> void
  3. Thread::getRegisters(PlatformRegisters&) -> size_t
  4. Thread::stack() -> const StackBounds&

In POSIX environment, we have further features.

  1. Thread::signal(int) -> bool

While macOS and Windows have platform APIs to suspend and resume threads, Linux does not have such one. We implement it by using POSIX signal and semaphore, which is typical way to implement stop-the-world GC operation.

Locking

I do not say much about locking in this post since here is very nice blog post in webkit.org. This offers WTF::Lock and WTF::Condition.

WTF::ThreadGroup

Grouping live threads is useful. Consider multi-threaded environment, various threads take a lock of one VM, run JS, and release the lock. When GC happens, conservative GC would like to scan the stack and registers of live threads that touch this VM before.

ThreadGroup offers exact this feature. We can add Thread to ThreadGroup. When Thread finished its execution, Thread cooperatively removes itself from added ThreadGroups. If you take a lock of ThreadGroup, all the threads included in this ThreadGroup is kept alive until the lock is released. We can iterate live threads in ThreadGroup and suspend each thread to perform stop-the-world.

While the concept of ThreadGroup is simple, its implementation is a bit tricky. Thread can concurrently finish, and be removed from ThreadGroup. Any thread can add any Thread to multiple ThreadGroups at any time. If you are interested in the implementation, you can look into the change.

WTF::WorkQueue and WTF::AutomaticThread

WorkQueue is simple abstraction. We can put a task (Function) to queue, and thread running inside the WorkQueue polls and run the task.

There is also a similar abstraction to WorkQueue: AutomaticThread. This is very fancy feature used in JSC. AutomaticThread can poll tasks and run them. While WorkQueue can take any functions as its tasks, AutomaticThread implements the body of the task in its virtual member, but semantics is very similar. The difference is that Thread is automatically destroyed when AutomaticThread becomes idle more than 10 seconds.

Reducing threads significantly affects on the memory consumption of the browser. Outstanding example is malloc. Recent malloc library uses TLS to gain high performance in multi-threaded environment. For example, various malloc implementations (including bmalloc in WebKit) have synchronization-free cache in TLS to speed up the fast case. This cache remains until the thread is destroyed!

AutomaticThread is mainly used for concurrent JIT compiler threads in JSC.

WTF::ParallelHelperPool

ParallelHelperPool is an interesting thread pool which is intended to be shared by multiple parallel tasks. We have a task that can be executed in parallel manner e.g. GC’s parallel marking. We set this task to the pool. And the pool run this task in parallel. As is noted in the code, this abstraction is suitable for the use case: there are multiple concurrent tasks that may all want parallelism. Since threads are managed by AutomaticThread, threads will be automatically destroyed if the pool is not used. Currently it is used for GC’s parallel marking (And recently, this thread also performs parallel marking constraint solving).

WTF::ThreadMessage

ThreadMessage is a feature executing lambda while suspending a specified thread. It is constructed on Thread::suspend and Thread::resume.

1
2
3
sendMessage(thread, [] (PlatformRegisters& registers) {
    ...
});

Since suspend and resume are portable, this ThreadMessage feature is also portable. By using sendMessage, we can modify some data while suspending a thread.

In WebKit, it is used to insert trap in running VM (called VM trap). One example is terminating a running VM without introducing runtime cost. You may see a dialog like “Your JS takes too much time. Do you want to stop it?”.

In JSC, we have check_trap bytecode. In optimizing compiler, it just emits nop. When we would like to terminating a running VM, we sendMessage to a thread running this VM. While suspending the thread, we rewrite JIT generated nop with hlt in x86, and then resume the thread. When the resumed thread hits this hlt, it causes fault signal. And we handle this fault in our signal handler. In the signal handler, we throw uncatchable JS exception for VM termination, and VM will be terminated. Since we just execute nop in an usual optimizing JIT code, we do not need to introduce runtime cost for this feature.

WTF::ThreadSpecific

WTF::ThreadSpecific<> offers the portable abstraction of TLS in POSIX and Windows. TLS is a storage to put per-thread data. It is good to achieve high performance in multi-threaded environment since accessing TLS’s data does not require synchronization. WTF::ThreadSpecific<> uses pthread_get_specific and pthread_set_specific in POSIX environment. In Windows, we use fiber local storage (FLS) under the hood.

One interesting feature of TLS is FAST_TLS in Darwin. It is a platform-provided system-reserved TLS slot like __PTK_FRAMEWORK_JAVASCRIPTCORE_KEY3. You can check them in system library header. These slots are intended to be used for system libraries. For these slots, you can use _pthread_getspecific_direct(KEY) and it is compiled to code accessing memory segment register and offset, it is quite fast. It is nice example of co-designing platform and system libraries.

Summary

Webkit has WTF utility library, and it offers various fancy threading primitives. As we encourage more parallelism in WebKit, we will add more features to WTF.

  1. This stop the world functionality is also used to implement sampling profilers in JSC. One sampling profiler thread periodically stops the JS VM thread, retrieves execution context data including stack traces, and resumes the thread. 

Adding Files Into WebKit Xcodeproj in Linux

Old days, WebKit project supported 7 (or 8?) build systems: GYP, CMake, Makefile, waf’s wscript, Xcode’s xcodeproj, Qt’s .pro, and Visual Studio’s vcxproj. But the situation is significantly improved these days. Now there is only 2 build systems: CMake and Xcode.

Adding files into CMakeLists.txt is easy. Just adding filenames to CMakeLists.txt. So for Linux WebKit developers, only one barrier to add new files is adding files into xcodeproj without Xcode!

I created small scripts, adding files into JavaScriptCode.xcodeproj. This script is easily extended to support the other WebKit xcodeproj files. This tool uses slightly modified node-xcode for WebKit xcodeproj. And the code repository is here.

How to Build JavaScriptCore on Your Machine

TL;TR

1
Tools/Scripts/build-webkit --jsc-only

JSCOnly port

WebKit JavaScriptCore (JSC) is a high quality JavaScript engine that is used in many production-quality software. The performance of JSC is comparable to the other JavaScript engines like V8, and SpiderMonkey 1. And its spec conformance reaches 99% in ES6 compat-table 2.

While JSC is responsible to the JavaScript engine part in WebKit, the standalone JavaScript engine cannot be built easily. As a same to V8 and SpiderMonkey, JSC also provides the standalone shell to test itself. In OS X environment, the JSC shell can be built with the command Tools/Scripts/build-jsc without doing nothing before. However, in the other ports (EFL and GTK), we need to build WebKit’s dependencies despite these dependent libraries are not necessary to JSC. Building the dependent libraries takes much time since it includes many fundamental libraries, glib, gtk+, cairo, mesa and so on. In addition, once the dependent libraries are updated, which is noted in jhbuild.modules, we need to rebuild these libraries.

The dependent libraries become obstacles in many cases. For example, if you need to build the old revision of JSC to confirm the performance regression, we need to rebuild the old dependencies for that. Another case is testing on the other platform. If you need to build 32bit JSC on Linux, you may set up the LXC container for that. At that time, you need to build all the dependencies to build JSC on the test box even if those dependencies are not related to JSC.

To overcome this situation, we recently introduce a new port JSCOnly 34. The major goal of this port is the followings; (1) providing the platform-independent way to build JSC with significantly fewer dependencies and (2) providing the playground for new aggressive features. JSCOnly port only builds and maintains JSC and its dependent parts, such as WTF, and bmalloc. Since WTF, bmalloc, and JSC are well-written for the Nix environments, we have very few specific part to maintain this port. This port allow us to build JSC on any platforms with significantly less effort.

How to build

The standalone JSC shell in JSCOnly has only one dependent library (ICU), while building process requires some dependencies (like perl, ruby, python, bison, flex etc.). Before building JSC, we need to install these dependencies via your favorite package manager.

1
sudo apt install libicu-dev python ruby bison flex cmake build-essential ninja-build git gperf

Then, build your JSC shell. Of course, you need to check out the WebKit tree.

1
git clone git://git.webkit.org/WebKit.git

And then, build JSC.

1
Tools/Scripts/build-webkit --jsc-only

That’s it.

In addition to that, you can build the JSC shell with the static JSC library.

Updated according to the comment.

1
Tools/Scripts/build-webkit --jsc-only --cmakeargs="-DENABLE_STATIC_JSC=ON -DUSE_THIN_ARCHIVES=OFF"

Reading the Paper, "ELI: Bare-Metal Performance for I/O Virtualization"

P.S.

あったほうがわかりやすいかもということで, 当初抜いていた簡易 Overview 再掲.

Note: This article is written in Japanese. In this article, we introduces the paper by A. Belay et al., “ELI: Bare-Metal Performance for I/O Virtualization” [Abel Gordon et al. ASPLOS ‘12].

この記事は, システム系論文紹介 Advent Calendar 2015 12/22 の記事として書かれました.

Reference

  • Abel Gordon, Nadav Amit, Nadav Har’El, Muli Ben-Yehuda, Alex Landau, Assaf Schuster, Dan Tsafrir. ELI: Bare-Metal Performance for I/O Virtualization, In Proc. of 17th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ‘12), 2012, pp 411-422.

Overview

VT-x, そして後の EPT 拡張によって, CPU, memory の virtualization は efficient に達成された. じゃああとは device ということで, VT-d によって, multiplexing はできないけれども, device によらず, isolation を壊さずに VM に device を efficient に assign することができた (pass-through).

とおもいきや, device が遅い場合がある. 調べたところ, interrupt が大量に入るような device ではなんと native 性能の 60% しかでてなかった. これは, VT-d の interrupt remapping は, 別に hypervisor を bypass して interrupt が入るわけではなく, interrupt は結局 VM exit して host に戻るという仕組みに存在した……

interrupt は実際は VM の管理 domain / host ではなくほとんど guest 向けのものになる. のならば, すべての interrupt を guest に直接渡してしまって, で, host に来るべきものだけ, host に戻せばいいのではないだろうか? しかし, guest の interrupt descriptor table (IDT) をそのまま使ってしまっては, host の受け取るべき interrupt を malicious な guest が乗っ取るかもしれない. この構図は, shadow page table の時の構図とほぼ同じだ.

ELI は IDT を shadowing し, shadow IDT を提供する. もちろんこの shadow IDT は guest からは直接触れない. host は guest IDT の変更を write protect で検知し(good old shadowing!), shadow IDT に反映する. VM exit を起こさず, guest の interrupt はすべて guest 内で処理される, Exit-Less-Interrupt (ELI) を提案する.

評価の結果, unmodified かつ untrusted guest が 97 - 100% の performance (compared to bare-metal) を達成した.

Background & Motivation

I/O は disk controller や NIC など, 仮想化環境において支配的な処理であり, direct device assignment (pass-through) の motivation となっている. I/O-intensive workloads においては, direct device assignment がなければ unacceptable な performance になるのだが, direct device assignment を行ったとしても bare-metal 環境と比較し, 60 - 65% 程度の performance しか出すことができない. direct device assignment はその I/O path において host の処理をほぼ全て取り除いているにも関わらずである (DMA remapping による host の介在しない DMA の発行, EPT による BAR の map による MMIO の direct access).

performance degradation は interrupt の処理で起きている.

interrupt handling

上の図の一番下が bare-metal. 対して一番上が現状の direct device assignment の時の interrupt の handle のされ方だ. 仮想化環境において, guest mode である場合,

  1. interrupt が起こるとまず VM exit が起きて host に戻る.
  2. そして host は hardware に interrupt completion を発行する.
  3. VM entry の際の virtual interrupt injection によって guest に interrupt を inject し resume.
  4. guest は物理マシンだと思っているので, 自分も interrupt completion を同様に発行する.
  5. guest の interrupt completion はまた VM exit を起こし host にもどる.
  6. host は interrupt completion の emulation をおこなって guest に resume.

ということが行われる. VM exit / entry の cost は non-I/O-intensive な workload にとってはそれほど問題がないが, I/O-intensive な workload + 近年の high performance storage / NIC にとっては, frequent な interrupt の生成により, これらは大きな問題となった.

これに対して, interrupt を減らすという手法をとる (例えば, polling や interrupt coalescing) こともできる.

  1. polling は OS handler の呼ばれる回数もコントロールできるが (batching すれば), batching する場合は latency が上がる. また, event がないときには CPU cycle を無駄にし, idle state になれないために power consuming でもある.
  2. interrupt と polling を組み合わせる hybrid な手法もある (interrupt 入ったらしばらく polling して… というやつ, NAPI では by default) が, dynamic に切り替える手法は実際には常にうまく行くというわけではない. その理由の一つは, 将来どれくらい interrupt が来るのか予測しなければならないという難しさだ (予測して interrupt / polling どちらのほうが cost が低いかを判断して切り替えるのだから).
  3. interrupt coalescing は, device に一定時間中の interrupt を coalescing して1回送らせる, もしくは一定回数の interrupt を coalescing して1回送らせるよう設定するものだ. これはもちろん latency が上がるという欠点があるが, それ以外に, 例えば TCP traffic の burst を引き起こしたりもする. coalescing の適切な parameter を求めるのは困難で, workload に依存する.

SR-IOV による asssignment ではいずれも高い CPU 利用率を bare-metal に対して示している. これについて, interrupt が大きなオーバーヘッドであることが demonstrate されている. 仮想化環境での interrupt の additional なオーバーヘッドを下げる研究についてもいくつか存在するが, hardware extension を要求する, Network device には適用できない (PV block device の virtual interrupt の coalescing を in flight な command 数に応じて行っている), polling を行うため前に述べた欠点がある, などの問題がある.

Design: ELI

cost となる 2つの exit (interrupt delivery と interrupt completion) を取り除くべく, この論文では ELI (Exit-Less-Interrupt) を提案する. 重要な点は, ある CPU core に来るほとんどすべての physical interrupt は, その CPU core で動いている guest に向けたもの だということだ. その理由は, high-performance を志向する guest は pinned な CPU core を専有しているであろうということ, そして I/O-intensive workload のために device assignment を SR-IOV を用いて行っていること, そして interrupt rate はふつうは実行時間に比例するということである.

Exitless Interrupt Delivery

仮想化の key は, ほとんどすべての時間を guest に使わせること. host の介在はなければないほどよい. ほとんどすべて guest への interrupt なのであれば, guest に interrupt を送ればよい.

ELI ではすべての physical interrupts を guest に送る (VT-x の制約上 all or nothing なので all しか選べない). そして, guest に関係のない, host のための interrupt は exit を起こして host に戻させる. この時, ELI は guest が trusted であったり, para-virtualized であったりといったことを求めない. ELI は unmodified かつ untrusted guest に対してこれを実現する.

ELI

guest が unmodified かつ untrusted であっても安全に host の interrupt を exit できるようにするために, ELI は Interrupt Descriptor Table (IDT)1 を shadowing し, shadow IDT を作成する. shadow IDT はおなじみ shadow page table に非常に近い. guest は自身の guest IDT が設定されていると思っているが, 実際には shadow IDT が設定されている. shadow IDT は guest IDT と in sync である.

上の Figure は ELI の interrupt delivery flow を示している. physical interrupt はすべて guest に exit なく伝えられ, shadow IDT によって assigned device については exit なく guest によって処理が行われる. 一方本来 host に伝えられるべきであった interrupt は, exit を起こすことによって guest を抜け, host にて処理がなされる.

shadow IDT は guest が通常触らない(普通のメモリとして使わない)が IDT として指定可能な空間である device PCI BAR に余分にページを増やし, そこに設置される2. shadow IDT は host に割り当てられた interrupt については non-present 状態にしておく. すると, interrupt が送られると NP exception が起こり, VM exit が発生する.

guest IDT は write-protect な状態に置かれ, 変更を検知し, shadow IDT へ反映する. これは shadow paging の手法とコンセプトは同じ. shadow IDT も guest による modify を避けるため write-protect 状態に置かれる3.

Exitless Interrupt Completion

もうひとつの exit, interrupt completion も取り除きたい. interrupt completion は EOI LAPIC register に書き込むことによって行われる. old interface では LAPIC area の一部に存在し, ほぼすべての LAPI access は exit を起こすが, 新しい x2APIC では MSR (Machine Specific Register) に書き込むことができる. MSR はそれぞれの MSR ごとに細粒度で exit するかどうかを control することができる.

そこで ELI では EOI x2APIC MSR を exit を起こさないで書き込めるように設定し guest の direct access を許可する. これによって interrupt completion についても exit を起こさずにすむ4.

Evaluations

筆者らは KVM 上に ELI を実装し評価を行っている. また性能向上のために host では huge pages を有効にしている. 確認したいのはそもそもの発端, I/O-intensive な workload における bare-metal に対する throughput や latency だ.

Throughput

Bare-metal に対する Throughput を示している. それぞれ Netperf TCP stream の write, Apache に向かって ApacheBench を用いて評価したもの, Memcached に向かって libmemcached の Memslap bench を (get 90%, set 10%) で実行したものだ.

それぞれの ELI の機能の contribution によって throughput は改善し, full ELI ではそれぞれ 98%, 97%, 100% の throughput (compared to bare-metal) を示している. interrupt delivery のほうが interrupt completion よりも寄与が大きいのは, host が interrupt を handling する処理のほうが複雑で, それが取り除かれたためであるとのこと.

Latency

次に, Netperf UDP の ping-pong を行い, その latency を評価する. Baseline (ELI なし) が bare-metal の 129% の高い latency を示しているのに対して, full ELI では 102% にまで改善している.

Conclusion

x86 仮想化が direct device assignment において interrupt の処理に host の介在が必要であることが high-performance storage and NIC にとって overhead となることを示し, ELI (shadow IDT, x2APIC MSR) の techniques を用いることによって, assigned device の interrupt の処理における VM exit を除去し, bare-metal throughput & latency を達成した. また, それを unmodified かつ untrusted guest に対して可能にした5.

Thoughts

問題が鮮やかで, 解法も従来の仮想化の手法を応用し, かつ特に何も犠牲にしておらず, 非常に堅実なものに思える. まあ動くからいいでしょ… としておいたものが, 環境が変わって (high-performance storange / NIC の登場など) 問題となるケース, かっこいいですね.

  1. IDT は interrupt の番号とそれぞれの handler をひも付ける 

  2. IDT は kernel address space に map されている必要がある. map され, map され続け, かつ通常アクセスしない場所として device の PCI BAR に余分なページを増やしてそこに設置する. Pass-through の際, 例えば Xen では仮想 device を作る. 仮想化された PCI configuration space に元の device と同じ設定を置いておき, EPT を用いて host に見えている BAR の host physical address と, guest における guest physical address をひも付けて MMIO の direct access を許可する. この時, typical には (Linux / Windows) pci resource の大きさを query しそのサイズ全域を kernel address space に map する. ので, ここで例えば, 本来 1MB のものを 2MB だと宣言しておき, 後ろ 1MB を device の BAR ではない普通の memory に EPT でひも付けておけば, そこを shadow IDT として利用可能だ. 

  3. EPT の該当エントリを read only に設定しておけばいけるか. 

  4. じゃあなんで今までからしなかったのと言われれば, もちろん問題があったからだ. guest には例えば virtual な keyboard によって生成され inject された virtual interrupt と assigned device による physical interrupt の区別がつかない. しかし, virtual interrupt の場合は, EOI は host の emulation に向かって行われるべきで, physical な EOI x2APIC MSR に書き込まれるのは問題である. そこで, ELI では virtual interrupt を inject するときには injection mode という mode に fallback する. host が virtual interrupt を入れるとき, ELI は guest VM を injection mode にしてから inject する. injection mode は guest の IDT を shadow IDT から guest IDT に戻し, 代わりに interrupt の exit や EOI MSR 書き込みの exit を有効にする. 早い話が, ELI なしの普通の状態に一時的に戻す. すると virtual interrupt は普通に今までの方法で処理される. そして virtual interrupt の EOI を exit によって無事受け取ったらまた guest VM を ELI の mode に戻す. 

  5. security についてはもう少しあったが補足で. 例えば guest が interrupt を disable にしたままにしてしまったら interrupt で exit しない以上 timer 割り込みも exit を起こさず, guest が走ったままになってしまう. これについては x86 virtualization の preemption timer を用いれば, unconditional exit を起こすことができる. 

Gave a Talk About CSS JIT

Once again, I had a chance to talk about CSS Selector JIT at x86/x64 optimization meetup. And I gave a presentation that is updated from the previous one.

Updated slides include the following differences.

  • Example flow of JIT compiled CSS Selector state machine
  • Rough performance evaluation with Dromaeo cssquery benchmark

Introducing the Paper, "Dune: Safe User-level Access to Privileged CPU Features"

Note: This article is written in Japanese. In this article, we introduces the paper by A. Belay et al., “Dune: Safe User-level Access to Privileged CPU Features” [A. Belay et al. OSDI ‘12].

この記事は, システム系論文紹介 Advent Calendar 2014 12/15 の記事として書かれました. ご意見, ご指摘, ご感想お待ちしております.

Reference

お気に入りの論文をとの事で, ここでは “Dune: Safe User-level Access to Privileged CPU Features” を紹介する. 著者らのグループは後に OSDI ‘14 にてこの Dune を基盤に “IX: A Protected Dataplane Operating System for High Throughput and Low Latency” を発表し, これは OSDI ‘14 の best paper の1つである. GPUnet [OSDI ‘14] にしようかと思ったが, 今回はこちらで.

Overview

この論文の提案することはまさに Abstract に一文で書かれている.

Dune uses the virtualization hardware in modern processors to provide a process, rather than a machine abstraction.

Intel VT-x (考え方自体に本質的な limitation はないが, 今回は主にこれ対象), AMD SVM といった virtualization hardware は VMM の構成要素として重要な役割を果たし効率的な VM を提供してきた. が, しかし, よく考えれば, VT-x で構築する abstraction は別に VM に限る必要はない.

Dune は発想を変え, VT-x を machine でなく, process abstraction を提供するために用いる. つまり machine の連続した physical memory space, devices, CPUs といった abstraction を構築するのではなく, process 環境, 大まかに言えば sparse な virtual memory space, system call interface (downcalls), signals (upcalls) といったものを VT-x を使って提供しようということだ. より具体的に言えば, process を VMX non-root で実行する. 結果 Dune は process に対して, ring 0 を与えることができる.

ring 0 を与えられた process は OS の持っていた特権機能を自由につかうことができる, すなわち ring protection, page tables, tagged TLB (Process Context ID) といった privileged hardware features だ. 特権の公開によって Dune は様々な application を実現, 最適化することができる. (e.g. sandboxing, privilege separation facility and GC.) しかも, process であり machine ではないので, process はこの特権にアクセス可能なこと以外は, 基本的に通常の process と同様に動く. つまり typical な Library OS のように stack を全部積み直したり, host との連携がないということはなく, system call を叩くこともできるのだ.

Dune の overview はこのくらいにして, 詳しく紹介していこう.

Background & Motivation

OS の特権, 例えば page table の dirty bit 情報などを適切に process に公開すると, application が便利に利用できるということは知られていて, 例えば page table の情報の公開による GC 最適化, process migration の user-space 実装などがあげられる.

しかし, 実現方法として, 「ある特権が user-space でほしい」となったらそのたびに kernel を intrusive に変更というのは現実的ではないし, 複数の applications から複数の特権が同時に必要, となった時にそのための kernel の変更が composable かどうかはわからない.

では application を specialized kernel (Library OS 等) と bundle して VM に載せてしまうというのはどうか? VM として動かせば, VMM によって host とは隔離され, 安全かつ効率的に特権を公開できるだろう. が, その場合, process と比較して host との poor integration が起こる. (host の FS も叩けない, process を fork したり UNIX domain socket で通信したりも出来ない etc.) また特定の application 向けに specialized kernel を構築するというのは small task ではない. 結果, 例えば, 「ある process の GC を高速にしたい」という motivation に対して, 「Library OS を構築して VM に載せて…」, というのは問題がある.

Proposal

そこで, Dune は virtualization hardware を用いて, machine の代わりに process abstraction を提供する. Dune mode になった process は Dune 特有の機能を使わなければ通常の process として動作することが出来る. つまり system call も利用できるし, なんら host OS との integration が process に対して劣ることはない. これに加えて Dune process は privileged hardware features を触ることができ, 様々な機能の実現や最適化が可能となる. そして同時に, virtualization hardware によって host の ring 0 に対して isolation が保証される. Dune では full の machine の abstraction を提供する必要がないため, Dune は (conventional VMM に対して) simple かつ高速である.

Dune overview

論文中の Figure 1 で持って Dune の概要を示す. VT-x の terminology を用いてざっくり説明する. まず host は VMX root の ring 0 で動作している. そして通常の process は VMX root, ring 3 で動作している. process は Dune の system call (Dune device への ioctl で実現されている) を用いることで, 不可逆に Dune process になることができる. Dune process は VMX non-root の ring 0 で動作が開始される. この結果 ring 0 向け特権が Dune process に対して公開される一方, VMX root である host に対して Dune process は適切に isolate された状態にある. Dune process は ring 0-3 を持っている状態にあり, この ring protection 自体も Dune process に公開された特権の一つだ.

図中の Dune Module が kernel module として host 側に存在する. Dune process は libDune を利用することもできる. libDune は privileged hardware feature を user-space でうまく用いるための薄い library だ.

Dune は process に対して通常の process とほぼ変わらない環境を与えつつ特権を与える. これはどうすれば達成できるのか? 鍵は virtual memory, system call, そして signal である.

Memory Management

Dune process には特権を利用しない場合は通常の process と同様に動いてほしい, ということは process の virtual memory space を Dune process は保持していなければならない. Dune はこれを Extended Page Table (EPT)1 を用いて実現する. 通常の process の page table を EPT で実現するのだ.

Dune virtual memory overview

論文中の Figure 2 は Dune process と通常の process の page table の関係を示している. 右側が通常の process, 左側が Dune process だ. この EPT と kernel page table (KPT) は全く同じ内容を持っていると考えて良い. KPT の translation を EPT にさせることで, VMX non-root の page table を Dune process に開放する. この時興味深いことに, EPT によって実現される memory space は, machine abstraction のようなほぼ連続な空間ではなく, sparse になる2.

本当は KPT を EPT としてそのまま用いることができれば最良であるが, technical にはいくつかの問題が存在する. (1) EPT は KPT とは format が異なる. (2) x86 の場合, EPT の address width, つまり guest physical address <-> host physical address は同じ幅でなければならない. Dune では guest physical address space として KPT の host virtual address space の幅を与えたいので本来は 48bit になるが, host physical address 側は 36bit physical limit があるため, guest physical address space は 36bit までに制限されてしまう.

(1) に対して Dune は EPT を EPT fault handling で埋めることで対応している. EPT を empty の状態で開始しておき, fault が起こると KPT (Dune process は通常の process なので, Dune mode では実際に使いはしないが KPT を持っている) に query をかけ, 必要な値を埋めるのだ. KPT から値が落とされた/変更された場合は MMU notifier (Linux の機能) で EPT からも落とす.

(2) は work around を持って対応している. Dune では Dune process に map される memory region を制限している, beggining of process (heap 等), mmap region, stack の 3つが Dune によって EPT に map され, これらをそれぞれ 4GB までに制限し, EPT の最初の 12GB 分(34bit) に埋めている. 将来的には, KPT の sparse な region を EPT に pack し, Dune process に remap するよう通知するなどをして対応可能ではあろうとしている.

System Call

次は system calls. Dune は Dune process に対して, 通常の process と同様の system call への interface を提供する必要がある.

Dune syscall

上の図は Dune の発表スライドの図を元に作成した, Dune の syscall のアーキテクチャ図である. 一般に system call は SYSCALL instruction によって発行される. ここが大変興味深いことではあるが, SYSCALL を trap するのは Dune process ring 0 である. つまり Dune process が発行した SYSCALL が Dune process によって trap されるのだ. これは sandboxing としては面白いが (例えばここで filtering などが可能), このままでは host の system call は発行できない.

そこで Dune は system call に VMCALL を用いる. VMCALL は hypercall 発行のための x86 instruction であり, VMX root に VM exit することができる. Dune kernel module は system call に対応する hypercall を備えており, hypercall を発行することで host OS に向かって system call を発行することができる.

しかしこのままでは SYSCALL をすべて VMCALL におきかえた library をつかう必要がある. そこで libDune は ring 0 で発行された SYSCALL を自動的に VMCALL に変換するメカニズムを提供し, 既存 library が変更なしに system call を発行できるようにしている.

Signals

最後に signals である. これについては Dune は大きく仕組みを変更しており, 互換な interface は持っていない. また通常の process とは状況が大きく異なる.

まず, 多くの signal は host から受ける必要はなく, Dune process であれば特権を利用して効率的な方法で handle できる. 例えば, SIGSEGV は, hardware page faults を直接用いることで, より効率的に扱うことができる.

外部から inject されるタイプの signal, 例えば SIGINT については, SIGSEV のようにはいかない. この場合 Dune kernel module は fake hardware interrupt を Dune process に inject する. これによって Dune process は効率的にこれら signal を扱えるだけでなく, hardware interrupt が発行されると ring 3 から ring 0 への transition が起こるため, Dune process 内で privileged mode を変更し sandboxing といったことをしていたとしても, ring 0 が signal に対処することが可能だ.

これらへの対処は通常の signal とは異なるため, libDune の提供する, dune_signal という抽象によって取り扱うこととなる, という limitation が存在する.

Applications

ここまでで Dune の architecture, すなわち Dune process が host との integration を犠牲にせず privileged hardware features を利用できる仕組みを紹介してきた. 次に実際に特権を利用してどのようなことが可能なのかについて, Dune を用いた3つの applications を紹介する.

Sandboxing

Dune process は ring 0 を持っている. これは大きな利点で, 例えば他の binary を ring 3 で動かすといった形で sandboxing を実現することが可能だ. sandboxing は NaCL のような例や, secure な OS container, secure な mobile phone application といったことに役立てられてきた.

Dune による sandboxing は ring 3 で untrusted binary を動作させることで実現される. sandbox 中から触れる memory は page table の supervisor bit によって制限をかけることができる. sandbox が exception を起こそうが, system call を呼ぼうが, それらはすべて Dune process ring 0 によって handle することが可能だ. ここで呼び出し可能な system call を制限するといったことをすると, untrusted binary に対しての filtering / restriction をすることができる. さらに, この handler で変換処理を行えば, host とは全く異なる system call interface を untrusted binary に見せるといったことも可能だ. Dune では sandboxing を拡張し, firewall (connect, bind を trap して filter) や checkpointing (ring 3 の memory, regs, descriptors を disk に save / restore ) も作成している.

Wedge

Wedge は privilege separation system というものだ. まあ具体的にはどういうことかというと, sthread という新しい抽象を導入する. これは fork-like な isolation を提供しつつも thread-like な performance を提供するというものだ. sthread は thread と同様に resource (memory, file descriptor, system calls policy etc.) を共有するが, この時この共有を policy によって制限をかけられる. 例えば server の場合, request を sthread で処理できれば, application code を isolate しつつ performance も得られ都合が良い.

Dune を使った Wedge では, sthread の作成高速化のために recycle を行う. これは最初の sthread 作成時に checkpoint をとっておき, 以降の sthread 作成をここから作ろうというものだ. original の sthread の memory をとっておき, 実行した後, dirty bit のたった page だけ original の memory で上書きすることで, 高速に sthread を restore することができる. 他にも ring protection による実行可能な system call の制限, page table による sthread の accessible な memory region の制限, tagged TLB (Process Context ID をつかう3) による高速な context switching を実現している.

Garbage Collection

Dune の特権を用いれば GC の高速化を行うことが可能だ. 具体的には以下の利用が考えられる.

  1. Fast faults: GC では mprotect による fault を用いる場合がある. Dune では fault を hardware interrupt として host を介さず process 内で処理することができ高速である.
  2. Dirty bits: Dune では page table の dirty bit を読みとることができるので, 触られた memory を memory barrier なしに検知することができる.
  3. Page table: 例えば compaction を行う場合, page table の entry を書き換えるだけで page の内容を別の virtual address region に移してくることが可能だ. また, backing phyiscal page を落としておけば参照した時に fault が起こるので, compaction などを行い, object が移動した時, ある object の保持している別の object への reference が old のままだったとしても, fault handling で検知することが可能だ.
  4. TLB control: GC では memory mapping を触るということが多く行われる. page table を Dune process が保持していれば, TLB invalidation を batch するといったことを行うことができる.

Dune では BoehmGC をこれらによって最適化している.

Evaluation

ここで Dune の評価を確認する. Dune の呈する overhead とはなんだろうか? 1つは VM enter / VM exit のコストだ. Dune process の system call には VM exit / VM enter が必要であり, これは通常の system call よりもコストが高い. また EPT fault 時には VM exit / VM enter が起こり, これもコストが高い. 2つめは, TLB miss コストの増大だ. TLB miss のコストは EPT を用いていた場合高くなる, なぜなら page walk が2段階になるからだ.

Dune table 1

論文中の Table 2 がこのコストを端的に示す. getpid system call はそれ自体はほとんど何もしないので (current から値を読みとるくらいのことしかしない), system call 自体の overhead をみることが可能だ. ここで, (1) system call は処理自体がもっと時間がかかるはず, (2) page fault も頻繁には起きない, ということを踏まえれば, 問題は TLB miss だろう. これは memory locality の低い program においては Dune が overhead になりうることを示している. これが問題になることは Figure 3 が明らかにする.

Dune overhead

Figure 3 は Dune による sandboxing の中で SPEC2000 を動かした時の native に対する slow down を示す, つまり lower is better だ. この時 (black) overall には非常に低い overhead (avg. 2.9%) での sandboxing に成功している一方, mcf, ammp は高い overhead を示している. これらは 高い TLB miss rate を呈した, さきほどの overhead が顕在化した例だ. そこで, TLB miss のコスト及び TLB miss rate を下げるため Dune の sandboxing application にて large page を利用する最適化を行っている (gray). sandboxing は ring 3 からの system call を trap することが可能なため, mmap が発行された場合, huge page を利用するよう flag を modify するのだ (要は, mmap とかを trap して MAP_HUGETLB を立てとこうって話). これによって overhead は改善する. これとほぼ同じ発想でもって huge page を利用する libhugetlbfs をもちいた Linux native 版 (white) と比較してもほぼ同じ結果になっていることがわかる.

Wedge については sthread の作成は fork の 40x, そして context switching は 3x 高速であったとしている. 作成コスト削減は recycle と kernel intervention の削除, context switching は tagged TLB で説明がつく.

Dune GC

最後に GC についてだ. いくつかの application について, Dune: Dune による direct port, Dune TLB: Dune + TLB invalidation を controlling, Dune dirty: Dune TLB + dirty bit を利用することによる memory protection を使わない version となっている. Table 6 がその評価結果となる. Dune は改善が overhead との相殺でどっこいどっこい. Dune TLBDune dirty は素晴らしい改善をみせている. XML の評価だけ改善が見られないが, これは application 中に garbage になるような object が十分に作成されないので, GC の最適化が EPT overhead を償却できてないとのこと. 見ると memory use の allocation と heap がほとんど同じなので, alloc したもの大体 live という状況になってしまっているのがわかる. XML file を複数もらって, process したら破棄して次みたいな事を繰り返すと十分に garbage が出来, 改善した. 10 の 150MB の XML files input で Dune dirty は 12.8% の改善をみせた.

Conclusion

Dune は virtualization hardware を用いて machine abstraction ではなく process abstraction を提供する. process の持つべき memory space, system call interface といった process abstraction を構成するものを VT-x 上で構築していくことで, process に対して privileged hardware feature を isolation を維持したまま見せることに成功した. そして特権によって様々な機能の実現, 最適化が可能なことを demonstrate した.

自分としては, virtualization hardware は VMM に使うんだという固定観念を崩す, 大変興味深い論文だった. この後, Dune の isolation を application / data plane / control plane の isolation に利用する IX へ進んでいく. generic な概念が出たら次 I/O へというのよくある感じするので, なにか出てきたら, この concept に I/O が絡んだ時にどうなるか, とか考えていきたいものだと思う.

  1. VT-x の機能のうちの一つ (追加された). 2段階の page table の解決を用いて virtual address を解決する. もともと, guest virtual address を guest page table に対する変更/監視なしに host physical address まで変換する仕組みを作るために導入された. (guest page table は guest virtual address を guest physical address に変換するので, guest physical address から host physical address の変換 phase があれば guest page table に変更は必要ない) 

  2. ちなみに今回 article 上では省略したが初めての VMLAUNCH の時にどうやって process の定常状態まで持っていくかという問題がある. これは technical には OS の bootstrapping に酷似する. Dune では通常 process の時に libDune が identical な map を行う page table を作って (guest virtual address (GVA) <-> guest physical address (GPA) table, かつ GVA, GPA の値が同じ), これを VMLAUNCH 時に CR3 として利用するという形になる. この時, Linux が mmap, stack, heap に使う部分を予め全部 map しておけば, mmap などが呼ばれたとしてもいちいち guest page table も更新する必要はない (もちろん, 実際に Dune process が mmap してない部分を触れば, page table は pass したとしても EPT fault が起こる). CR3 及びその page table entry/directory の address は当然のことながら physical address であることが求められるため面倒そうに思える. が, Dune では GPA は host virtual address (HVA) に等しいため, HVA 上で page table を作って (before entring Dune mode), それを初期 CR3 として渡せば特に労なく動作する. 渡された後の page table をどうするかは Dune process ring 0 の自由だ. 

  3. 論文中にはないが, 少し寄り道して tagged TLB の話を確認しておこう. Intel 64 and IA-32 Architectures Software Developer’s Manual の section 4.5 によると, CR4.PCIDE が 1 の場合は CR311:0 が PCID として解釈されることになっている. section 4.10.1 を見ると, PCID が有効な場合, TLB の entry は PCID に関連付けられる. そして TLB を利用する場合, 現在の PCID に関連する entry しか利用しないとのことだ. つまり, PCID ごとに論理 TLB があるくらいの感覚で良いのだろう. PCID は 12bit なので全てで 4096 entries 存在することになる. Process 数が 4096 に制限されるのはまずいので, OS ならばひと工夫必要だろう (個人的には process を 4096 色に coloring して必要なときだけ INVPCID を発行するというのが良さそうと感じる). が, PCID の 4096 entries は寿命の短い sthread の, しかも user-space 実装の id としては十分だろう. Dune process は PCID という特権機能ももちろん用いることができる. Dune の sthread では PCID を用いることで sthread ごとに論理 TLB を割り当てる. これによって TLB flush なしの context switching を実現できる. 

Importing Hidden (Non-exported) Kernel Symbols

I’ve created import-kernel-symbols, which is a tiny python script to generate headers importing non-exported (non EXPORT_SYMBOL decorated) kernel symbols.

Motivation

When crafting / testing / experimenting kernel modules, occationally you need to call non-exported kernel symbols. If you can call non-exported symbols without attaching EXPORT_SYMBOL to those symbols, you can try using these functions without modifying / recompiling the kernel. In addition to this benefit, you can keep your kernel module simple, loadable and external. It’s a desirable feature for in-house kernel modules. (When you to upstream it, you simply modify the kernel :))

This python script generates references to the specified non-exported symbols. It extracts symbol kernel space address from System.map, and generates header for easy use.

Usage

First you need to create the importing header template, imported.h.in. This sample is located under example/ directory.

1
2
3
4
5
6
7
8
9
10
11
/*
 * Header importing symbols.
 */
#ifndef SAMPLE_H_
#define SAMPLE_H_
#include <linux/mm.h>

IMPORT_SYMBOL_PROLOGUE

IMPORT_SYMBOL(handle_mm_fault);
#endif  /* SAMPLE_H_ */

Next, passing it and appropriate System.map to import-kernel-symbols.py script. System.map is a file containing symbols and addresses in kernel itself. Typically (in Ubuntu case) it is located under /boot/System.map-$(uname -r), or /lib/modules/$(uname -r)/build/System.map. Note that this System.map file permission is sometimes set as -rw------- with owner root. In this case, you need to sudo to read System.map or change permission of this file. After hitting the command such as python import-kernel-symbols.py imported.h.in System.map, it will dump the generated header. The example is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * Header importing symbols.
 */
#ifndef SAMPLE_H_
#define SAMPLE_H_
#include <linux/mm.h>

#define IMPORT_SYMBOL_VALUE_FOR_handle_mm_fault (0xffffffff81198a10UL)
#define IMPORT_SYMBOL(name) \
    static typeof(&name) IMPORTED(name) __attribute__((unused)) = (typeof(&name))IMPORT_SYMBOL_VALUE_FOR_ ## name
#define IMPORTED(name) __i__ ## name


IMPORT_SYMBOL(handle_mm_fault);
#endif  /* SAMPLE_H_ */

OK! Now, since all symbols are resolved by this header correctly, you can call the hidden symbol via special syntax. In the case of handle_mm_fault,

1
ret = IMPORTED(handle_mm_fault)(mm, vma, addr, flags);

Note that since it skips EXPORT_SYMBOL_GPL license check, take care of the license of your module. In this case, maybe, releasing code as GPL is the most conservative approach I think.

Happy Hacking ;)

WebKit CSS JIT Internals

Recently, I’ve been contributing to WebKit CSS Selector JIT compiler. There’s a nice overview about it written by Benjamin Poulain, he leads the CSS JIT project.

Yesterday, I gave a presentation about WebKit CSS Selector Compiler. In this slide, I show the details of CSS JIT, mainly focusing on backtracking and code generation. I hope you like it!

P.S.

I've heard that CSS JIT is shipped in iOS 8 beta 3 with ARM64/ARMv7s/ARMv7 support. So it will be enabled on the all Apple platforms; iPhone 5, 5c, 5s! Exciting!

P.S.

Once again, I had a chance to talk about CSS Selector JIT and gave a presentation that is updated from the following one.