Fight the Future

Java言語とJVM、そしてJavaエコシステム全般にまつわること

作って学ぶガベージコレクタをやってみた

2019年2月のFOSDEMというイベントが、ベルギーのブリュッセルでありました。 FOSDEMは、Free and Open Source Developer's European Meetupの頭文字です。

そこで、「Build your own GC with OpenJDK in 20 minutes」というセッションがありました。 録画もあり、こちらから視聴できます。

FOSDEM 2019 - Build your own GC with OpenJDK in 20 minutes

私は、FOSDEM開催前からセッション一覧をチェックしていて、このセッションが非常に気になっていました。 内容は、何もしないGCであるEpsilon上に、GCを自分で実装するという、まさに私が求めていたものでした。 スピーカーは、レッドハット社のGCに取り組んでおられる方で、実装自体は、なんと私のこのブログでもよく引用させてもらている、Alekseyさんでした。 セッションでは、実装の詳しい説明はなかったのですが、後日、そのコードがAlekseyさんのサイトで公開されました。

Do It Yourself (OpenJDK) Garbage Collector

OpenJDKのソースに、公開されたパッチを適用してビルドすれば、このGCが動作するJDKができます。 Alekseyさんのサイトにあるとおり、Spring PetClinicを動かしてみました。

github.com

$ build/macosx-x86_64-server-fastdebug/jdk/bin/java -Xlog:gc -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC -Xmx128m -jar target/*.jar
...
[60.102s][info][gc] GC(10) Step 0: Prologue 0.132ms
[60.315s][info][gc] GC(10) Step 1: Mark 212.816ms
[60.370s][info][gc] GC(10) Step 2: Calculate new locations 55.006ms
[60.821s][info][gc] GC(10) Step 3: Adjust pointers 451.887ms
[60.874s][info][gc] GC(10) Step 4: Move objects 52.915ms
[60.877s][info][gc] GC(10) Step 5: Epilogue 2.079ms
[60.877s][info][gc] GC(10) GC Stats: 57654 (7.66%) reachable from roots, 694677 (92.34%) reachable from heap, 637637 (84.75%) moved, 12844 (1.71%) markwords preserved                                                                      
[60.877s][info][gc] GC(10) Heap: 128M reserved, 128M (100.00%) committed, 32791K (25.02%) used
[60.877s][info][gc] GC(10) Lisp2-style Mark-Compact (Allocation Failure) 127M->32M(128M) 775.043ms

127M->32MにGCできました。ベースとなるEpsilonがexperimetalなので、-XX:+UnlockExperimentalVMOptionsをつけ、-XX:+EpsilonSlidingGCが今回実装したGCを使うための新規フラグです。

GC時間が、775msなので、実用には耐えないですね。試しにシリアルGCでやってみると、こんな感じです。

build/macosx-x86_64-server-fastdebug/jdk/bin/java -Xlog:gc -XX:+UnlockExperimentalVMOptions -XX:+UseSerialGC -Xmx128m -jar target/*.jar
...
[25.451s][info][gc] GC(18) Pause Young (Allocation Failure) 49M->19M(123M) 117.059ms
[28.998s][info][gc] GC(20) Pause Young (Allocation Failure) 54M->21M(123M) 67.372ms
[40.406s][info][gc] GC(28) Pause Young (Allocation Failure) 67M->34M(123M) 37.391ms

GCインタフェース

ただ動かすだけでは、学びにならないので、セッションや記事以外の部分を調べます。 Epsilonは何もしないGCであり、ベースとして十分ではあるものの、GCアルゴリズムに必要な処理を自分で追加していかなければなりません。ただ、GCアルゴリズムには、どんなものにも必要な処理というものがあります。代表的なものは、以下のものです。

  • Javaヒープそのもの
  • バリア

JDK 9までも、多少の共通コードはありましたが、JDK 10でGCインタフェースとして、全GCアルゴリズムが使用するものがまとめられました。ここでのインタフェースは、Javaのインタフェースではありません。やり取りの窓口、のような感じです。なお、GCは、現時点ではすべてC++コードです。

JEP 304: Garbage Collector Interface

これにより、今回の実装でも、低レベルの処理はGCインタフェースのものを使うだけで済んでいます。GCインタフェースは、src/hotspot/share/gc/sharedにあります。今回の実装で使うのは、次のものです。

  • src/hotspot/share/gc/shared/collectedHeap
  • src/hotspot/share/gc/shared/markBitMap

collectedHeapは、「an implementation of a java heap for HotSpot」とあるように、HotSpotのJavaヒープ実装です。これは、GCインタフェース導入前からあります。このクラスは抽象クラスで、各GCが具象クラスをそれぞれ作成します。

 CollectedHeap
   GenCollectedHeap
     SerialHeap
     CMSHeap
   G1CollectedHeap
   ParallelScavengeHeap
   ShenandoahHeap
   ZCollectedHeap

そのため、このEpsilonベースのGCアルゴリズムも、CollectedHeapを継承したクラスを作成する必要があります(後述)。

Epsilonがすでにやっていること

Epslionが何もしないGCだからといって、まったく何も書かれていない空実装、というわけではありません。Alekseyさんのサイトによると、こういったものです。

  • アロケーション
  • バリア
  • モニタリングへのフック

Epsilonが、すでにこれらのことをやっているので、GC実装では気にする必要がなくなります。

アロケーション

GCは、実際には回収のみでなく、アロケーションにも関わります。ガベージコレクタは、実際にはメモリマネージャです。要求されたサイズのものを、直接ヒープに、またはTLABから割り当てます。TLABって何?という方は、こちらのエントリも参照ください。

www.sakatakoichi.com

バリア

並行でGCを実行する場合など、整合性の観点でアプリケーションからヒープにアクセスがあると、バリアを使い必要な処理を実行する必要があります。たとえば、移動対象のリージョンにあるオブジェクトへの書き込みが発生した場合は、コピーを作ります。フォワーディングポインタを使っている場合は、読み取り時にアクセスしたオブジェクトではなく、フォワーディングポインタをデリファレンスして、そこにあるオブジェクトを参照します。

  • リードバリア(読み取り時)
  • ライトバリア(書き込み時)
  • ロードバリア(ロード時)

モニタリングへのフック

JVMのモニタリングで、GC関連のことを処理する必要があります。diagnosticコマンドや、MXBeanなどです。

実装対象のGCアルゴリズム

今回実装するGCアルゴリズムは、マークコンパクトコレクタです。コンパクションは、Lisp 2アルゴリズムのスライディングコンパクションを使います。このあたりの内容は、書籍「ガベージコレクション」の第3章にあります。

ガベージコレクション 自動的メモリ管理を構成する理論と実装

ガベージコレクション 自動的メモリ管理を構成する理論と実装

端的に言うと、ヒープ中のライブオブジェクトをマークし、マークがあるオブジェクトだけを順にヒープの先頭から詰めることで、コンパクションする、という感じです。もちろん、オブジェクト間の参照を更新する必要もあります。

マーク

ライブオブジェクトをマークする、と言っても、どのようにマークを実装するのか、決める必要があります。このGCは、ビットマップマーキングです。別のビットマップを用意し、ヒープと対応させて、マークを管理します。これを実装するのは、既存のmarkBitMapを使うだけで済みます。デフォルトでは、ヒープの64ビットをmarkBitMapの1ビットに対応させます。つまり、ヒープの64ビット内にライブオブジェクトがいれば、markBitMapをマークするということです。よって、markBitMapのサイズは、ヒープ領域の1/64の大きさ、となります。これは、GC開始時に確保すればよい領域で、GCが完了すれば解放できます。markBitMapは、ヒープではなくネイティブメモリに作成します。

フォワーディング

コンパクションするということは、オブジェクトを移動させるということです。オブジェクトAからBへの参照があるとき、Bを移動させれば、Bの新しいアドレスでAを更新する必要があります。その新しいアドレスは、どこかに保存しておく必要があります。この実装では、オブジェクトのマークワードに書き込みます。マークワードは、オブジェクトヘッダにあります。このGCは、Stop the WorldなGCなので、マークワードを利用して書き込んでも、問題は起こりません。

スライディングコンパクション

スライディングコンパクションは、ヒープの先頭からオブジェクトを詰めているので、ヒープ内のオブジェクトは、GC前と同じ順序になります。並べ替えをしないので、逆に言うと参照しているオブジェクトを近くに置くといった再配置はしない、というのがデメリットです。このあたりは、私の文章での説明より、Alekseyさんのサイトにある絵を見てもらう方がよいです。

計算量

オーダーは、ヒープにあるオブジェクトの数に対してO(N)です。ただし、このGCでは、何度もヒープ内をwalkします。

  1. 全オブジェクトをスキャンし、ライブオブジェクトをマークする
  2. ライブオブジェクトに対し、移動先のアドレスを計算する
  3. ライブオブジェクトに対し、参照オブジェクトのアドレスを、移動先のアドレスに変更する
  4. ライブオブジェクトを、移動先のアドレスに移動させる

4回です。

バリア

Stop the WorldするGCなので、バリアは必要ありません。ただ、バリアが必要ない、ということをJVMに伝える必要はあります。そのため、Epsilonの既存の実装である、EpsilonBarrierSetを使います。EpsilonBarrierSetは、GCインタフェースにあるBarrierSetを継承して、ThreadLocalDataの作成と破棄をしているだけです。

  • src/hotspot/share/gc/epsilon/epsilonBarrierSet

実装

4ファイルを「変更」するだけです。

  • M src/hotspot/share/gc/epsilon/epsilonHeap.cpp
  • M src/hotspot/share/gc/epsilon/epsilonHeap.hpp
  • M src/hotspot/share/gc/epsilon/epsilon_globals.hpp
  • M src/hotspot/share/runtime/vmOperations.hpp

epsilon_globalsとvmOperationsは、フラグやテンプレートを追加する少量の変更だけなので、実質epsilonHeapのみです。epsilonHeapは、CollectedHeapを継承したクラスです。では、epsilonHeapを見ていきます。

アロケート時にGCできるようにする

ベーズとなるEpsilonはGCをしないため、ヒープがなくなればOutOfMemoryErrorとなるだけです。そのため、今回アロケートに失敗すれば、GCを実行する、という処理を追加します。前述のとおり、アロケートには、2つのパターンがあります。

  • TLABにアロケートする -> allocate_new_tlab()
  • ヒープに直接アロケートする -> mem_allocate()

どちらの関数も、アロケート自体はallocate_work()を呼び出しています。この呼び出しを、「アロケートに失敗すれば、GCを実行する」関数に置き換えます。その関数の名前を、allocate_or_collect_work()とします。

allocate_new_tlab()

HeapWord* EpsilonHeap::allocate_new_tlab(size_t min_size,
                                         size_t requested_size,
                                         size_t* actual_size) {
...
  // All prepared, let's do it!
  HeapWord* res = allocate_work(size);
...
}
HeapWord* EpsilonHeap::allocate_new_tlab(size_t min_size,
                                         size_t requested_size,
                                         size_t* actual_size) {
...
  // All prepared, let's do it!
  HeapWord* res = allocate_or_collect_work(size);
...
}

mem_allocate()

HeapWord* EpsilonHeap::mem_allocate(size_t size, bool *gc_overhead_limit_was_exceeded) {
  *gc_overhead_limit_was_exceeded = false;
  return allocate_work(size);
}
HeapWord* EpsilonHeap::mem_allocate(size_t size, bool *gc_overhead_limit_was_exceeded) {
  *gc_overhead_limit_was_exceeded = false;
  return allocate_or_collect_work(size);
}

allocate_or_collect_work()

HeapWord* EpsilonHeap::allocate_or_collect_work(size_t size) {
  HeapWord* res = allocate_work(size);
  if (res == NULL && EpsilonSlidingGC) {
    vmentry_collect(GCCause::_allocation_failure);
    res = allocate_work(size);
  }
  return res;
}

allocate_or_collect_work()では、allocate_work()でアロケートを実行し、NULL、つまりアロケートに失敗し、かつ今実装しているEpsilonSlidingGCがフラグで有効になっていれば、vmentry_collect()を呼び出してGCを実行し、再度allocate_work()でアロケートをする、という処理です。

vmentry_collect()

void EpsilonHeap::vmentry_collect(GCCause::Cause cause) {
  VM_EpsilonCollect vmop(cause);
  VMThread::execute(&vmop);
}

VM_EpsilonCollectは、VM_Operationを継承したもので、セーフポイント下でコレクションサイクルを実行します。

class VM_EpsilonCollect: public VM_Operation {
private:
  const GCCause::Cause _cause;
  EpsilonHeap* const _heap;
  static size_t _last_used;
public:
  VM_EpsilonCollect(GCCause::Cause cause) : VM_Operation(),
                                            _cause(cause),
                                            _heap(EpsilonHeap::heap()) {};

  VM_Operation::VMOp_Type type() const { return VMOp_EpsilonCollect; }
  const char* name()             const { return "Epsilon Collection"; }

  virtual bool doit_prologue() {
...
  }

  virtual void doit() {
...
  }

  virtual void doit_epilogue() {
...
  }
};

関数は3つです。

  • doit_prologue()
  • doit()
  • doit_epilogue()

簡潔に言えば、前処理、本処理、後処理ですね。これがVMThreadのexecute()内で、順に呼び出されます。

doit_prologue()

  virtual bool doit_prologue() {
    // Need to take the Heap lock before managing backing storage.
    // This also naturally serializes GC requests, and allows us to coalesce
    // back-to-back allocation failure requests from many threads. There is no
    // need to handle allocation failure that comes without allocations since
    // last complete GC. Waiting for 1% of heap allocated before starting next
    // GC seems to resolve most races.
    Heap_lock->lock();
    size_t used = _heap->used();
    size_t capacity = _heap->capacity();
    size_t allocated = used > _last_used ? used - _last_used : 0;
    if (_cause != GCCause::_allocation_failure || allocated > capacity / 100) {
      return true;
    } else {
      Heap_lock->unlock();
      return false;
    }
  }

doit_prologue()では、trueを返すと処理を継続し、falseを返すと処理をキャンセルします。アロケーション失敗時、容量をオーバーしたならtrueを返します。また、ヒープをロックします。

doit()

  virtual void doit() {
    _heap->entry_collect(_cause);
  }

entry_collect()を呼び出すだけです。entry_collect()が、今回実装するGCアルゴリズムのすべてです。すでに、このアルゴリズムでは、4回ヒープをwalkすると書きました。言い換えると、entry_collect()は4つのパートに分けられます。

  1. マーク
  2. 新しいアドレスの計算
  3. ポインタの整備
  4. オブジェクトの移動

加えて、GC自体の前処理や後処理、検証といった処理があります。

基本的には、Alekseyさんのサイトにある説明がわかりやすいので、そちらを読んでもらえればと思います。

https://shipilev.net/jvm/diy-gc/#_implementing_gc_core

私の学習メモとして、以下記載します。

前処理

    GCTraceTime(Info, gc) time("Step 0: Prologue", NULL);

    // Commit marking bitmap memory. There are several upsides of doing this
    // before the cycle: no memory is taken if GC is not happening, the memory
    // is "cleared" on first touch, and untouched parts of bitmap are mapped
    // to zero page, boosting performance on sparse heaps.
    if (!os::commit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size(), false)) {
      log_warning(gc)("Could not commit native memory for marking bitmap, GC failed");
      return;
    }

    // We do not need parsable heap for this algorithm to work, but we want
    // threads to give up their TLABs.
    ensure_parsability(true);

    // Tell various parts of runtime we are doing GC.
    CodeCache::gc_prologue();
    BiasedLocking::preserve_marks();

    // Derived pointers would be re-discovered during the mark.
    // Clear and activate the table for them.
    DerivedPointerTable::clear();

if (!os::commit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size(), false)) {は、前述の、markBitMapの作成です。あとは、ヒープのparsabilityを有効にする、コードキャッシュにGCの開始を伝える、BiasedLockのロックのマークを保存させる、Derivedなポインタ用のテーブルをクリアする、という前処理をしています。

マーク

    GCTraceTime(Info, gc) time("Step 1: Mark", NULL);

    // Marking stack and the closure that does most of the work. The closure
    // would scan the outgoing references, mark them, and push newly-marked
    // objects to stack for further processing.
    EpsilonMarkStack stack;
    EpsilonScanOopClosure cl(&stack, &_bitmap);

    // Seed the marking with roots.
    process_roots(&cl);
    stat_reachable_roots = stack.size();

    // Scan the rest of the heap until we run out of objects. Termination is
    // guaranteed, because all reachable threads would be marked eventually.
    while (!stack.is_empty()) {
      oop obj = stack.pop();
      obj->oop_iterate(&cl);
      stat_reachable_heap++;
    }

    // No more derived pointers discovered after marking is done.
    DerivedPointerTable::set_active(false);

基本的には、GCルートからwalkしてライブオブジェクトにマークをつけていくだけです。マークを付ける処理は、EpsilonScanOopClosureが実行します。

process_roots()は、最終的にルートのwalkをするdo_roots()を呼び出します。

void EpsilonHeap::do_roots(OopClosure* cl, bool everything) {
  // Need to tell runtime we are about to walk the roots with 1 thread
  StrongRootsScope scope(1);

  // Need to adapt oop closure for some special root types.
  CLDToOopClosure clds(cl, ClassLoaderData::_claim_none);
  MarkingCodeBlobClosure blobs(cl, CodeBlobToOopClosure::FixRelocations);

  // Walk all these different parts of runtime roots. Some roots require
  // holding the lock when walking them.
  {
    MutexLockerEx lock(CodeCache_lock, Mutex::_no_safepoint_check_flag);
    CodeCache::blobs_do(&blobs);
  }
  {
    MutexLockerEx lock(ClassLoaderDataGraph_lock);
    ClassLoaderDataGraph::cld_do(&clds);
  }
  Universe::oops_do(cl);
  Management::oops_do(cl);
  JvmtiExport::oops_do(cl);
  JNIHandles::oops_do(cl);
  WeakProcessor::oops_do(cl);
  ObjectSynchronizer::oops_do(cl);
  SystemDictionary::oops_do(cl);
  Threads::possibly_parallel_oops_do(false, cl, &blobs);

  // This is implicitly handled by other roots, and we only want to
  // touch these during verification.
  if (everything) {
    StringTable::oops_do(cl);
  }
}

OopClosure、今回はEpsilonScanOopClosureなのですが、CLDToOopClosureやMarkingCodeBlobClosureがこれをラップして、ClassLoaderDataGraphやCodeCacheに処理を実行させています。その前に、各々ロックをしている感じです。ここにある分が、GCルートということですね。では、EpsilonScanOopClosure自体を見てみます。

class EpsilonScanOopClosure : public BasicOopIterateClosure {
private:
  EpsilonMarkStack* const _stack;
  MarkBitMap* const _bitmap;

  template <class T>
  void do_oop_work(T* p) {
    // p is the pointer to memory location where oop is, load the value
    // from it, unpack the compressed reference, if needed:
    T o = RawAccess<>::oop_load(p);
    if (!CompressedOops::is_null(o)) {
      oop obj = CompressedOops::decode_not_null(o);

      // Object is discovered. See if it is marked already. If not,
      // mark and push it on mark stack for further traversal.
      if (_bitmap->par_mark(obj)) {
         _stack->push(obj);
      }
    }
  }

public:
  EpsilonScanOopClosure(EpsilonMarkStack* stack, MarkBitMap* bitmap) :
                        _stack(stack), _bitmap(bitmap) {}
  virtual void do_oop(oop* p)       { do_oop_work(p); }
  virtual void do_oop(narrowOop* p) { do_oop_work(p); }
};

do_oop_work()では、前半部分はoop(Ordinary Object Pointer)を取り出しています。CompressedOops(圧縮OOP)の仕組みがあるので、そこを考慮しています。後半部分は、markBitMapのマークをし、ここで初めてマークしたオブジェクトならスタックにプッシュします。

この処理を、UniverseやMangementやJVMTIや、といったGCルートすべてに適用します。

    // Seed the marking with roots.
    process_roots(&cl);
    stat_reachable_roots = stack.size();

    // Scan the rest of the heap until we run out of objects. Termination is
    // guaranteed, because all reachable threads would be marked eventually.
    while (!stack.is_empty()) {
      oop obj = stack.pop();
      obj->oop_iterate(&cl);
      stat_reachable_heap++;
    }

GCルートのwalkが終われば、スタックに多くのオブジェクトが積まれているはずです。今度は、スタックからオブジェクトをポップして、そのオブジェクトの参照をたどり、それらをすべてマークします。

新しいアドレスの計算

次は、ライブオブジェクトをwalkして、新しいアドレスを計算します。

  // We are going to store forwarding information (where the new copy resides)
  // in mark words. Some of those mark words need to be carefully preserved.
  // This is an utility that maintains the list of those special mark words.
  PreservedMarks preserved_marks;

  // New top of the allocated space.
  HeapWord* new_top;

  {
    GCTraceTime(Info, gc) time("Step 2: Calculate new locations", NULL);

    // Walk all alive objects, compute their new addresses and store those
    // addresses in mark words. Optionally preserve some marks.
    EpsilonCalcNewLocationObjectClosure cl(_space->bottom(), &preserved_marks);
    walk_bitmap(&cl);

    // After addresses are calculated, we know the new top for the allocated
    // space. We cannot set it just yet, because some asserts check that objects
    // are "in heap" based on current "top".
    new_top = cl.compact_point();

    stat_preserved_marks = preserved_marks.size();
  }

walk_bitmap()に渡している、EpsilonCalcNewLocationObjectClosureが、その処理です。_space->bottom()は、ヒープの先頭の位置です。PreservedMarksは、今からマークワードに新しいアドレスを書き込んでしまうので、もし書き込む前の内容を保存するためのものです。

class EpsilonCalcNewLocationObjectClosure : public ObjectClosure {
private:
  HeapWord* _compact_point;
  PreservedMarks* const _preserved_marks;

public:
  EpsilonCalcNewLocationObjectClosure(HeapWord* start, PreservedMarks* pm) :
                                      _compact_point(start),
                                      _preserved_marks(pm) {}

  void do_object(oop obj) {
    // Record the new location of the object: it is current compaction point.
    // If object stays at the same location (which is true for objects in
    // dense prefix, that we would normally get), do not bother recording the
    // move, letting downstream code ignore it.
    if ((HeapWord*)obj != _compact_point) {
      markOop mark = obj->mark_raw();
      if (mark->must_be_preserved(obj)) {
        _preserved_marks->push(obj, mark);
      }
      obj->forward_to(oop(_compact_point));
    }
    _compact_point += obj->size();
  }

  HeapWord* compact_point() {
    return _compact_point;
  }
};

if ((HeapWord*)obj != _compact_point) {は、対象のオブジェクトがもともとあった位置が、移動する先のアドレスと同じかどうかを見ています。同じであれば、そのオブジェクトを移動させる必要がないので、処理をスキップします。

obj->forward_to(oop(_compact_point));で、新しいアドレスを書き込んでいます。

// Used by scavengers
void oopDesc::forward_to(oop p) {
  assert(check_obj_alignment(p),
         "forwarding to something not aligned");
  assert(Universe::heap()->is_in_reserved(p),
         "forwarding to something not in heap");
  assert(!is_archived_object(oop(this)) &&
         !is_archived_object(p),
         "forwarding archive object");
  markOop m = markOopDesc::encode_pointer_as_mark(p);
  assert(m->decode_pointer() == p, "encoding must be reversable");
  set_mark_raw(m);
}

forward_to()は、結局markOop m = markOopDesc::encode_pointer_as_mark(p);がすべてですね。そのアドレスを持ったoopから、markOopが作られます。

  void do_object(oop obj) {
...
      obj->forward_to(oop(_compact_point));
    }
    _compact_point += obj->size();
...
};

そして、そのオブジェクトのサイズ分、compact_pointの位置をずらします。compact_pointは、次のオブジェクトを配置する、開始位置となります。

この処理を呼び出している関数walk_bitmap()は、こうです。

// Walk the marking bitmap and call object closure on every marked object.
// This is much faster that walking a (very sparse) parsable heap, but it
// takes up to 1/64-th of heap size for the bitmap.
void EpsilonHeap::walk_bitmap(ObjectClosure* cl) {
   HeapWord* limit = _space->top();
   HeapWord* addr = _bitmap.get_next_marked_addr(_space->bottom(), limit);
   while (addr < limit) {
     oop obj = oop(addr);
     assert(_bitmap.is_marked(obj), "sanity");
     cl->do_object(obj);
     addr += 1;
     if (addr < limit) {
       addr = _bitmap.get_next_marked_addr(addr, limit);
     }
   }
}

markBitMapにある、マークしたオブジェクトを順番に見ています。オブジェクトをEpsilonCalcNewLocationObjectClosureのdo_object()に渡して、処理をさせています。

ポインタの整備

処理の流れは、前節と同じです。walk_bitmap()する際に、適用する処理が変わるだけです。

    GCTraceTime(Info, gc) time("Step 3: Adjust pointers", NULL);

    // Walk all alive objects _and their reference fields_, and put "new
    // addresses" there. We know the new addresses from the forwarding data
    // in mark words. Take care of the heap objects first.
    EpsilonAdjustPointersObjectClosure cl;
    walk_bitmap(&cl);

    // Now do the same, but for all VM roots, which reference the objects on
    // their own: their references should also be updated.
    EpsilonAdjustPointersOopClosure cli;
    process_roots(&cli);

    // Finally, make sure preserved marks know the objects are about to move.
    preserved_marks.adjust_during_full_gc();

今度は、処理の内容が、EpsilonAdjustPointersObjectClosureに変わりました。

class EpsilonAdjustPointersObjectClosure : public ObjectClosure {
private:
  EpsilonAdjustPointersOopClosure _cl;
public:
  void do_object(oop obj) {
    // Apply the updates to all references reachable from current object:
    obj->oop_iterate(&_cl);
  }
};

ここで、Adjust(整備)するのは、たとえば、オブジェクトAがBを参照しているときの、AからBへの参照です。コンパクションにより移動するので、新しいアドレスで更新する必要があります。EpsilonAdjustPointersObjectClosureでは、oop_iterate()に、名前が似ていてわかりづらいですが、EpsilonAdjustPointersOopClosureを渡しています。

class EpsilonAdjustPointersOopClosure : public BasicOopIterateClosure {
private:
  template <class T>
  void do_oop_work(T* p) {
    // p is the pointer to memory location where oop is, load the value
    // from it, unpack the compressed reference, if needed:
    T o = RawAccess<>::oop_load(p);
    if (!CompressedOops::is_null(o)) {
      oop obj = CompressedOops::decode_not_null(o);

      // Rewrite the current pointer to the object with its forwardee.
      // Skip the write if update is not needed.
      if (obj->is_forwarded()) {
        oop fwd = obj->forwardee();
        assert(fwd != NULL, "just checking");
        RawAccess<>::oop_store(p, fwd);
      }
    }
  }

public:
  virtual void do_oop(oop* p)       { do_oop_work(p); }
  virtual void do_oop(narrowOop* p) { do_oop_work(p); }
};

実際の処理はdo_oop_work()です。前半は、以前にも出てきたCompressedOopsのデコードです。後半、if (obj->is_forwarded()) {がtrueであれば、マークワードから新しいアドレスを取得し、そのオブジェクトへの参照を更新します。

オブジェクトの移動

ここでようやく、実際にオブジェクトを移動させます。

    GCTraceTime(Info, gc) time("Step 4: Move objects", NULL);

    // Move all alive objects to their new locations. All the references are
    // already adjusted at previous step.
    EpsilonMoveObjects cl;
    walk_bitmap(&cl);
    stat_moved = cl.moved();

    // Now we moved all objects to their relevant locations, we can retract
    // the "top" of the allocation space to the end of the compacted prefix.
    _space->set_top(new_top);

EpsilonMoveObjectsです。

class EpsilonMoveObjects : public ObjectClosure {
private:
  size_t _moved;
public:
  EpsilonMoveObjects() : ObjectClosure(), _moved(0) {}

  void do_object(oop obj) {
    // Copy the object to its new location, if needed. This is final step,
    // so we have to re-initialize its new mark word, dropping the forwardee
    // data from it.
    if (obj->is_forwarded()) {
      oop fwd = obj->forwardee();
      assert(fwd != NULL, "just checking");
      Copy::aligned_conjoint_words((HeapWord*)obj, (HeapWord*)fwd, obj->size());
      fwd->init_mark_raw();
      _moved++;
    }
  }

  size_t moved() {
    return _moved;
  }
};

マークワードから新しいアドレスを取得して、Copy::aligned_conjoint_words()で移動させます。最後に、もうマークワードは使用しないので、init_mark_raw()で初期化します。

後処理

PreservedMarksに保存しておいたものを戻したり、コードキャッシュやBiasedLockなどなどに、GCが完了したことを伝えます。

    GCTraceTime(Info, gc) time("Step 5: Epilogue", NULL);

    // Restore all special mark words.
    preserved_marks.restore();

    // Tell the rest of runtime we have finished the GC.
    DerivedPointerTable::update_pointers();
    BiasedLocking::restore_marks();
    CodeCache::gc_epilogue();
    JvmtiExport::gc_epilogue();

    // Marking bitmap is not needed anymore
    if (!os::uncommit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size())) {
      log_warning(gc)("Could not uncommit native memory for marking bitmap");
    }

    // Return all memory back if so requested. On large heaps, this would
    // take a while.
    if (EpsilonUncommit) {
      _virtual_space.shrink_by((_space->end() - new_top) * HeapWordSize);
      _space->set_end((HeapWord*)_virtual_space.high());
    }

!os::uncommit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size())は、GC開始時に作成したmarkBitMapの領域を解放しています。

EpsilonUncommitは、今回実装しているフラグに1つで、有効にしていると、GCの結果不要になったメモリをOSに返します。

検証

  if (EpsilonVerify) {
    GCTraceTime(Info, gc) time("Step 6: Verify", NULL);

    // Verify all roots are correct.
    EpsilonVerifyOopClosure cl;
    process_all_roots(&cl);

    // Verify all objects in heap are correct. Since we have compacted everything
    // to be beginning, the heap is parsable right now, and we can just walk all
    // objects and verify them.
    EpsilonVerifyObjectClosure ocl;
    walk_heap(&ocl);

    // Ask parts of runtime to verify themselves too
    Universe::verify(VerifyOption_Default, "");
  }

同じくEpsilonVerifyというフラグを新しく作っており、有効であれば、ルートを含む全オブジェクトをを検証します。

これで、GCの処理はすべてです!

doit_epilogue()

VM_EpsilonCollectに戻ります。

  virtual void doit_epilogue() {
    _last_used = _heap->used();
    Heap_lock->unlock();
  }

使用量の保存と、ヒープのロックを解除します。

フラグの追加

あとは、フラグの追加部分のみです。

src/hotspot/share/gc/epsilon/epsilon_globals.hpp

+  experimental(bool, EpsilonSlidingGC, false,                               \
+          "Actually does sliding mark-compact GC.")                         \
+                                                                            \
+  experimental(bool, EpsilonUncommit, false,                                \
+          "Uncommits all unneeded memory after GC.")                        \
+                                                                            \
+  experimental(bool, EpsilonVerify, false,                                  \
+          "Does the additional GC verification step.")                      \
+                                                                            \

EpsilonSlidingGC、EpsilonUncommit、EpsilonVerifyの3つのフラグを追加します。-XX:+EpsilonSlidingGCのようにすれば、フラグを有効にできます。

src/hotspot/share/runtime/vmOperations.hpp

+  template(EpsilonCollect)                        \

私は、この部分が明確に何のためのものか、よくわかっていません。C++のテンプレート機能でしょうか??

テスト

テストは、jtregを使って作成します。jtregについては、こちらのエントリも参照ください。

www.sakatakoichi.com

今回の実装にも、簡単なテストが作られています。Javaコードです。

  • test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java
package gc.epsilon;

/**
 * @test TestSlidingGC
 * @key gc
 * @requires vm.gc.Epsilon & !vm.graal.enabled
 * @summary Epsilon sliding GC works
 * @library /test/lib
 * @run main/othervm -Xmx512m -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC                                         gc.epsilon.TestSlidingGC
 * @run main/othervm -Xmx512m -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC -XX:+EpsilonVerify                      gc.epsilon.TestSlidingGC
 * @run main/othervm -Xmx512m -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC -XX:+EpsilonVerify -XX:+EpsilonUncommit gc.epsilon.TestSlidingGC
 */

import java.util.concurrent.*;

import jdk.test.lib.process.OutputAnalyzer;
import jdk.test.lib.process.ProcessTools;

public class TestSlidingGC {

  static int SIZE  = Integer.getInteger("size", 10_000_000);
  static int COUNT = Integer.getInteger("count", 100_000_000); // ~2.4 GB allocation

  static Object[] sink;

  public static void main(String... args) {
    sink = new Object[SIZE];
    for (int c = 0; c < COUNT; c++) {
      sink[ThreadLocalRandom.current().nextInt(SIZE)] = new Object();
    }
  }

}

実行します。

$ CONF=macosx-x86_64-server-fastdebug make run-test TEST=test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java
Building target 'run-test' in configuration 'macosx-x86_64-server-fastdebug'
Skip building of Graal unit tests because 3rd party libraries directory is not specified
Skip building of Graal unit tests because 3rd party libraries directory is not specified
Test selection 'test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java', will run:
* jtreg:test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java

Running test 'jtreg:test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java'
Passed: gc/epsilon/TestSlidingGC.java
Test results: passed: 1
Report written to /Users/koichi.sakata/code/jdk-jdk/build/macosx-x86_64-server-fastdebug/test-results/jtreg_test_hotspot_jtreg_gc_epsilon_TestSlidingGC_java/html/report.html
Results written to /Users/koichi.sakata/code/jdk-jdk/build/macosx-x86_64-server-fastdebug/test-support/jtreg_test_hotspot_jtreg_gc_epsilon_TestSlidingGC_java
Finished running test 'jtreg:test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java'
Test report is stored in build/macosx-x86_64-server-fastdebug/test-results/jtreg_test_hotspot_jtreg_gc_epsilon_TestSlidingGC_java

==============================
Test summary
==============================
   TEST                                              TOTAL  PASS  FAIL ERROR   
   jtreg:test/hotspot/jtreg/gc/epsilon/TestSlidingGC.java
                                                         1     1     0     0   
==============================
TEST SUCCESS

Finished building target 'run-test' in configuration 'macosx-x86_64-server-fastdebug'

テストをパスしました!また、こんな感じのレポートファイルが出力されます。

f:id:jyukutyo:20190313180759p:plain

最後に

私は、JVMが非常に好きなのですが、C++の経験がまったくないため、途方に暮れていました。このGCのコンテンツは、コード量も少なく、またGCを作るというインパクトもあり、非常にすばらしいものでした。Alekseyさんを始め、作成されたRichardさん、Romanさん、Cyrilleさんに感謝します。