OSv page faultに出てくるballooningまわり追ってみました

## またお会いしましたね
どうもです。[前回](http://qiita.com/akachochin/items/8f6de53d4c0aa90ac42e)スケジューラの実装に書いてみた@akachochinです。
さて、今回は仮想記憶周りを読んだときに、私の不勉強ゆえballooningが今一つわかっていなかったので、これを良い機会に調べてみることにしました。
けれど.....全部調べるところまで至りませんでした。これも未熟ゆえですが、調べるとAdvent calendarに間に合わないため、"Done is better than perfect"ということで許してくだせえ、お代官様。

## まずはページフォルトハンドラから

こんな感じです。Linuxのと比べると本当にシンプルです。

```cpp:core/mmu.cc
void vm_fault(uintptr_t addr, exception_frame* ef)
{
    trace_mmu_vm_fault(addr, ef->get_error());
    if (fast_sigsegv_check(addr, ef)) {
        vm_sigsegv(addr, ef); 
        trace_mmu_vm_fault_sigsegv(addr, ef->get_error(), "fast");
        return;
    }    
    addr = align_down(addr, mmu::page_size);
    WITH_LOCK(vma_list_mutex.for_read()) {
        auto vma = vma_list.find(addr_range(addr, addr+1), vma::addr_compare());        if (vma == vma_list.end() || access_fault(*vma, ef->get_error())) {
            vm_sigsegv(addr, ef);
            trace_mmu_vm_fault_sigsegv(addr, ef->get_error(), "slow");
            return;
        }        
        vma->fault(addr, ef);
    }        
    trace_mmu_vm_fault_ret(addr, ef->get_error());
}
```

さて、以下のところ。メソッド呼出があります。

```cpp:core/mmu.cc
vma->fault(addr, ef);
```

その実体を探してみると、以下3つのメソッドがあります。

```cpp:core/mmu.cc
void vma::fault(uintptr_t addr, exception_frame *ef)
/* 略 */
void jvm_balloon_vma::fault(uintptr_t fault_addr, exception_frame *ef)
/* 略 */
void file_vma::fault(uintptr_t addr, exception_frame *ef)
/* 略 */
```

ここで、ballooningが出てきました。
balloonって？コンストラクタを読めば何か分かるかもしれません。

```cpp:core/mmu.cc
// Balloon is backed by no pages, but in the case of partial copy, we may have
// to back some of the pages. For that and for that only, we initialize a page
// allocator. It is fine in this case to use the noinit allocator. Since this
// area was supposed to be holding the balloon object before, so the JVM will
// not count on it being initialized to any value.
jvm_balloon_vma::jvm_balloon_vma(unsigned char *jvm_addr, uintptr_t start,      
                                 uintptr_t end, balloon_ptr b, unsigned perm, unsigned flags)
    : vma(addr_range(start, end), perm_rw, flags | mmap_jvm_balloon, true, page_allocator_noinitp),
      _balloon(b), _jvm_addr(jvm_addr),
      _real_perm(perm), _real_flags(flags & ~mmap_jvm_balloon), _real_size(end - start)
{
}
```

日本語に訳すとこんな感じでしょうか。

>Balloonには裏打ちされたページはないが、部分的なコピーが成された場合、いくばくかのページがバッキングストアとなるかもしれない。まさにそれゆえ、ページアロケータを初期化する。この場合、「noinit allocator」を使うのがよい。なぜなら、(ページを割り当てる)前にはそこの空間にはballoon objectがあるという前提があるので、JVMはそこのエリアが如何なる値にも初期化されていることをあてにしていない。

コンストラクタの中身を見る限り、事実上vmaのインスタンスをこしらえるだけのようにも見えます。(Linuxとかと同じ仮想アドレス空間内の一領域です。)
うーん。余計わからなくなった。なら、google先生に聞いてみましょう。

## ballooningってなによ
「jvm」「ballooning」で調べると....。出てきました。とりわけ、[vmwareのページ](https://pubs.vmware.com/vfabric5/index.jsp?topic=/com.vmware.vfabric.tc-server.2.6/em4j/em4j-about.html)や[takaochan氏のページ](http://d.hatena.ne.jp/takaochan/20101117/1290004225)が参考になります。

ハイパーバイザからは、ゲストOSがメモリをどう管理しているのかはわからないのが原則ですが、それだとゲストOSが使っていないメモリ空間が無駄になってしまいます。
そこで、バルーンドライバを使って、本来は意識しないハイパーバイザに対してゲストOSが認識するかたちでメモリを回収する仕組みを導入しました。これがballooning driverと呼ばれるものらしいです。
(特に、日本語で読める記事としてはtakaochan氏の記事は大変秀逸かと思います。)
これを踏まえて雰囲気だけでも掴んでみたいと思います。

## さて、jvm_balloon_vma::faultは

jvm_balloon_vma::faultがどうなっているのかを読むことにしましょう。

```cpp:core/mmu.cc
void jvm_balloon_vma::fault(uintptr_t fault_addr, exception_frame *ef) 
{
    if (jvm_balloon_fault(_balloon, ef, this)) {                                
        return;
    }    
    // Can only reach this case if we are doing partial copies
    assert(_effective_jvm_addr);
    // FIXME : This will always use a small page, due to the flag check we have
    // in vma::fault. We can try to map the original worker with a huge page,
    // and try to see if we succeed. Using a huge page is harder than it seems,
    // because the JVM is not guaranteed to copy objects in huge page
    // increments - and it usually won't.  If we go ahead and map a huge page
    // subsequent copies *from* this location will not fault and we will lose
    // track of the partial copy count.
    vma::fault(fault_addr, ef);
}
```

jvm_balloon_faultがtrueでない場合は汎用のfaultメソッドが呼ばれるように見えます。
気になるのはjvm_balloon_fault。そこをみましょう。

```cpp:java/jvm_balloon.cc
// We have created a byte array and evacuated its addresses. Java is not ever
// expected to touch the variable itself because no code does it. But when GC
// is called, it will move the array to a different location. Because the array
// is paged out, this will generate a fault. We can trap that fault and then
// manually resolve it.
//
// However, we need to be careful about one thing: The JVM will not move parts
// of the heap in an object-by-object basis, but rather copy large chunks at
// once. So there is no guarantee whatsoever about the kind of addresses we
// will receive here. Only that there is a balloon in the middle. So the best
// thing to do is to emulate the memcpy in its entirety, not only the balloon
// part.  That means copying the part that comes before the balloon, playing
// with the maps for the balloon itself, and then finish copying the part that
// comes after the balloon.
bool jvm_balloon_fault(balloon_ptr b, exception_frame *ef, mmu::jvm_balloon_vma *vma)
{
    // 例外時のエラーコードが取得できる場合。
    // 例外時のスタックフレームはページフォルトの場合、どう考えても
    // とれるはずなので非NULLだろう。
    if (!ef || mmu::is_page_fault_write_exclusive(ef->get_error())) {
        if (vma->effective_jvm_addr()) {
            return false;
        }
        trace_jvm_balloon_close(vma->start(), vma->end(), "write");
        delete vma;
        return true;
    }
```

例外時のスタックフレームって、どんなんだっけ、という人のためにexception_frameをみましょう。

```cpp:arch/aarch64/exceptions.hh
struct exception_frame {
    ulong r15;
    ulong r14;
    ulong r13;
    ulong r12;
    ulong r11;
    ulong r10;
    ulong r9; 
    ulong r8; 
    ulong rbp;
    ulong rdi;
    ulong rsi;
    ulong rdx;
    ulong rcx;
    ulong rbx;
    ulong rax;
    u16 error_code;
    ulong rip;
    ulong cs; 
    ulong rflags;
    ulong rsp;
    ulong ss; 

    void *get_pc(void) { return (void*)rip; }
    unsigned int get_error(void) { return error_code; }
};
```

x86のスタックフレームがどうなっているかは、以下のIntel SDMから抜粋した図が一番わかりやすいですね。

![exception_stack.png](https://qiita-image-store.s3.amazonaws.com/0/19975/581872b6-6acd-e72c-e2f6-6dd6b865a99b.png)

**ページフォルト例外の場合**、error codeは以下のフォーマットです。

![page_fault_errcode.png](https://qiita-image-store.s3.amazonaws.com/0/19975/1d22ce22-84cc-f83e-031d-f0428165c83e.png)

判定に使われているis_page_fault_write_exclusive()は以下の実装です。

```cpp:arch/x64/mmu.cc
enum {
    page_fault_prot  = 1ul << 0,
    page_fault_write = 1ul << 1,
    page_fault_user  = 1ul << 2,
    page_fault_rsvd  = 1ul << 3,
    page_fault_insn  = 1ul << 4,
};
/* 略 */
bool is_page_fault_write_exclusive(unsigned int error_code) {
    return error_code == page_fault_write;
}
```

以上のことより、is_page_fault_write_exclusive(ef->get_error())とは、ページフォルトで要因がメモリへの書き込みの場合かどうかを判定する処理ということになります。

次に、vma->effective_jvm_addr()をみましょう。

## vma->effective_jvm_addr()とは

```cpp:include/osv/mmu.hh
class jvm_balloon_vma : public vma {
public:
/* 略 */
    unsigned char *effective_jvm_addr() { return _effective_jvm_addr; }    
private:
    unsigned char *_effective_jvm_addr = nullptr;
/* 略 */
};
```

どうやら、privateメンバの_effective_jvm_addrがポイントのようです。
これはcore/mmu.ccに説明があります。

```cpp:core/mmu.cc
// IMPORTANT: This code assumes that opportunistic copying never happens during
// (以下長いコメント)
```

これだけだと後で忘れてしまいそうなので、日本語訳してみました。

>重要:このコードは楽観的なコピーはpartial copy中に起きないという仮定のもとに実装している。一般的にこの仮定は誤っている。同じオブジェクトから両者のコピーを同時に実行することを妨げるものは何もない。しかしながら、hotspotはそれをしなさそうであり、それゆえコードを大いに単純にできた。
>
>この仮定が前提とする何らかの現実的なシナリオが成り立たないと(hotspotのcorner caseや他のJVMが動作するなど)アサーションの条件であるeff == _effective_jvm_addrにひっかかりクラッシュするだろう。必要ならこのケースを捌くことも不可能ではないだろう: 成すべきことはeffective addressのリストを作り、partial countを独立して保つことである。
>
>partial copyについての説明
>多くのスレッドを使うことによって、GCが大きなオブジェクトを並行してコピーする。このとき各スレッドはそれぞれの(コピーの担当分である)オブジェクトの一部に対して責任を持つ。
>
>このようなことが起こると、balloonの単純な移動アルゴリズムは破綻する。しかし、コピー元のオフセットxはコピー先のオフセットxにコピーされる(コピー元領域の先頭からのオフセットxにあるデータがコピー先領域の先頭からのオフセットxの位置にコピーされるという意味)ので、最終的なコピー先オブジェクト(の位置)を計算可能である。このアドレスが以下のコードで使われている_effective_jvm_addr である。
>
>問題は、この時点では未だ新たなballoonがopenできないことである。JVMはオブジェクトのほんの一部をコピーしているだけだと信じているので、コピー先は正しいオブジェクトを含むかもしれず(というよりいつもそうだが),別のオブジェクトをそこにインストール(配置)する前にそのオブジェクトはどこか別の場所に移されないといけない。
>
>また、誰かがオブジェクトに書き込みを行うと、完全にそのオブジェクトをcloseすることはできない。: なぜならオブジェクトの一部は既に解放され、JVMは先に進みその場所に別のオブジェクトをコピーするかもしれないし、またそうするだろう。このケースを捌くために、_partial_copyという変数を使うが、その変数はどのくらいデータがその場所からどこか別の場所にコピーされたのかを記録するために使われる。JVMがオブジェクトの全体をコピーしなければならないことはわかっているので、そのvma内で期待するバイト数分に_partial_copyの値が達すると、そのオブジェクトをcloseできるということを意味する(楽観的コピーは無いという前提)
>
>partial copy中に該当領域に書き込みが発生することもまた有り得る。オブジェクトに対して上書きが発生することは間違えているのだが、すでにコピー済みの領域に対して上書きが発生することは全く問題ない。これはfault handlerで捌くが、その方法は現在balloon vmaな領域にページをマップすることで行う。その時点で、匿名メモリ領域(annonymous)がその位置に作ることになるだろう。

我ながら長すぎです(苦笑)。
色々分からん単語が出てきました。hotspot、そしてpartial copy。

実はこのあたりの話、[ragozin氏のブログ](http://blog.ragozin.info/2011/12/garbage-collection-in-hotspot-jvm.html)や[伊藤智博氏の記事](http://gihyo.jp/dev/serial/01/jvm-arc/0006)が参考になります。

どうやらhotspotやpartial copyはGCの高速化の技術で、領域を小さく分割し、それを平行でGCかける技術のようです。

_effective_jvm_addrはどうやらpartial copyを実施しているアドレスを指すと推定できそうです。

もう一度先のコードに戻りましょう。

```cpp:java/jvm_balloon.cc
bool jvm_balloon_fault(balloon_ptr b, exception_frame *ef, mmu::jvm_balloon_vma *vma)
{
    if (!ef || mmu::is_page_fault_write_exclusive(ef->get_error())) {
        if (vma->effective_jvm_addr()) {
            return false;
        }
        trace_jvm_balloon_close(vma->start(), vma->end(), "write");
        delete vma;
        return true;
```

つまり、partial copy中の場合はfalse、つまりこの関数を抜けて一般的なpage faultを実施することになりそうです。

上記引用のソースはどうやら、さっきの超長い日本語訳の後半部分に相当しそうです。

* partial copyの最中(effective_jvm_addr()がNULLでない)場合は、先の日本語訳の「partial copy中に該当領域に書き込みが発生することもまた有り得る。....これはfault handlerで捌くが、....作ることになるだろう。」に合致すると思われます。
* partial copyをしていないとき(effective_jvm_addr()がNULL)は、「また、誰かがオブジェクトに書き込みを行うと、完全にそのオブジェクトをcloseすることはできない。.....そのオブジェクトをcloseできるということを意味する」ところにつながってきそうです。

## 今回はここまで

これはなかなか勉強になります。GCの進歩についてはほとんどマークできていませんでしたが、引用したブログ記事などを読むと他にも読むべき記事が紹介されていたりします。

次回は何らかの形で続きを読んでみて、もう少し深いところまで切り込んで全体像がみえるようにしたいですね。

やっぱりOSSのカーネルソース、とりわけOSvを読むのは楽しいですね。
それでは、Happy code reading!