第11章 退避

本章ではG1GCの退避の実装を解説します。この章でも『アルゴリズム編』ですでに紹介した内容は省略していきます。

11.1 退避の全体像

退避の全体像をおさらいしていきましょう。

実行ステップ

退避はおおまかに次の3ステップにわかれています。

  1. 回収集合選択
  2. ルート退避
  3. 退避

1.は退避対象のリージョンを選択するステップです。並行マーキングで得た情報を参考に回収集合を選びます。

2.は回収集合内のルートから直接参照されているオブジェクトと、他リージョンから参照されているオブジェクトを空リージョンに退避するステップです。

3.は退避されたオブジェクトを起点として子オブジェクトを退避するステップです。3. が終了した段階で、回収集合内にある生存オブジェクトはすべて退避済みとなります。

また退避は必ずセーフポイントで実行されます。そのため、すべてのミューテータは退避中に停止した状態になっています。

退避の実行タイミング

退避は『アルゴリズム編 5.8』で説明したとおり、新世代リージョン数が上限に達したタイミングで実行します。オブジェクトのアロケーションでは新世代リージョンに対してオブジェクトをわりあてていき、新世代リージョン数が上限に達した際に退避を実行します。

では、実際のソースコードを見てみましょう。「4.4.2 G1GCのVMヒープへメモリ割り当て」で少し紹介したattempt_allocation_slow()メンバ関数の中で退避を呼び出しています。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

886: HeapWord* G1CollectedHeap::attempt_allocation_slow(size_t word_size,
887:                            unsigned int *gc_count_before_ret) {

906:     {
907:       MutexLockerEx x(Heap_lock);

           /* 省略: 空きリージョンの取得&オブジェクト割り当て */

           /* 成功したらreturnする */
911:       if (result != NULL) {
912:         return result;
913:       }

933:     }

937:       result = do_collection_pause(word_size, gc_count_before, &succeeded);

906行目から933行目にかけて、新しい空きリージョンを確保しようとします。新世代リージョン数が上限に達したら新しい空きリージョンは確保できずに失敗します。失敗した場合は937行目でdo_collection_pause()を呼びます。

do_collection_pause()は次のようにVMオペレーションを実行します。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

3025: HeapWord* G1CollectedHeap::do_collection_pause(size_t word_size,
3026:                                                unsigned int gc_count_before,
3027:                                                bool* succeeded) {

3030:   VM_G1IncCollectionPause op(gc_count_before,
3031:                              word_size,
3032:                              false,
3033:                              g1_policy()->max_pause_time_ms(),
3034:                              GCCause::_g1_inc_collection_pause);
3035:   VMThread::execute(&op);
3036:
3037:   HeapWord* result = op.result();

3044:   return result;
3045: }

そして、VM_G1IncCollectionPausedoit()で退避が実行されます。

share/vm/gc_implementation/g1/vm_operations_g1.cpp

72: void VM_G1IncCollectionPause::doit() {
73:   G1CollectedHeap* g1h = G1CollectedHeap::heap();

104:   _pause_succeeded =
105:     g1h->do_collection_pause_at_safepoint(_target_pause_time_ms);
106:   if (_pause_succeeded && _word_size > 0) {

           /* 省略:新しくできた空き領域にメモリ割り当て */

112:   }
113: }

105行目のdo_collection_pause_at_safepoint()で退避は実行されます。成功すれば退避で空いた領域にメモリを割り当て、VMオペレーションを終了します。

do_collection_pause_at_safepoint()

do_collection_pause_at_safepoint()の説明に必要な部分を抜き出すと次のようになります。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

3188: bool
3189: G1CollectedHeap::do_collection_pause_at_safepoint(
        double target_pause_time_ms) {

            /* 1. 回収集合選択 */
3336:       g1_policy()->choose_collection_set(target_pause_time_ms);

            /* 2.,3. 退避 */
3362:       evacuate_collection_set();

3494:   return true;
3495: }

do_collection_pause_at_safepoint()は引数にGC停止時間の上限を受け取ります。3336行目のchoose_collection_set()は回収集合を選択するメンバ関数です。この関数では、引数に受け取るGC停止時間上限を超えないような回収集合を選択します。

3362行目のevacuate_collection_set()は選択した回収集合の生存オブジェクトを退避するメンバ関数です。

退避用記憶集合維持スレッド

『アルゴリズム編 3.4』で紹介した退避用記憶集合維持スレッドはConcurrentG1RefineThreadというクラスに実装されています。

ConcurrentG1RefineThreadクラスのインスタンスはConcurrentG1Refineクラスのコンストラクタで生成されます。

share/vm/gc_implementation/g1/concurrentG1Refine.cpp

48: ConcurrentG1Refine::ConcurrentG1Refine() :
60: {

77:   _n_worker_threads = thread_num();
79:   _n_threads = _n_worker_threads + 1;
80:   reset_threshold_step();
81:
82:   _threads = NEW_C_HEAP_ARRAY(ConcurrentG1RefineThread*, _n_threads);
83:   int worker_id_offset = (int)DirtyCardQueueSet::num_par_ids();
84:   ConcurrentG1RefineThread *next = NULL;
85:   for (int i = _n_threads - 1; i >= 0; i--) {
86:     ConcurrentG1RefineThread* t =
           new ConcurrentG1RefineThread(this, next, worker_id_offset, i);
89:     _threads[i] = t;
90:     next = t;
91:   }
92: }

77行目のthread_num()で生成するConcurrentG1RefineThreadインスタンスの数が決まります。このthread_num()の値は、言語利用者が起動オプションに指定できるG1ConcRefinementThreadsという値でも変更可能です。

ConcurrentG1RefineThreadクラスはインスタンスを作った時点でスレッドの生成・起動をおこないます。86行目でインスタンスを生成すると同時に、退避用記憶集合維持スレッドは動き出します。

ConcurrentG1RefineのコンストラクタはG1CollectedHeapinitialize()で呼び出されます。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

1794: jint G1CollectedHeap::initialize() {

1816:   _cg1r = new ConcurrentG1Refine();

そのため、VMヒープを生成するタイミングで退避用記憶集合維持スレッドも動きはじめることになります。

11.2 ステップ1—回収集合選択

最初のステップである回収集合選択からみていきましょう。回収集合選択はG1CollectorPolicy_BestRegionsFirstクラスのchoose_collection_set()に実装されています。

回収集合選択で利用される予測時間の計算はほとんど『アルゴリズム編 4.2 退避時間の予測』で紹介した内容ですので、計算内容は省略します。

新世代リージョン選択

『アルゴリズム編 5.1』の中で説明したとおり、すべての新世代リージョンは回収集合に選択されます。

share/vm/gc_implementation/g1/g1CollectorPolicy.cpp:choose_collection_set():前半

2853: void
2854: G1CollectorPolicy_BestRegionsFirst::choose_collection_set(
2855:                              double target_pause_time_ms) {

2866:   double base_time_ms = predict_base_elapsed_time_ms(_pending_cards);
2867:   double predicted_pause_time_ms = base_time_ms;
2869:   double time_remaining_ms = target_pause_time_ms - base_time_ms;

2897:   if (in_young_gc_mode()) {

          /* 新世代リージョンを回収集合へ */
2932:     _collection_set = _inc_cset_head;
2933:     _collection_set_size = _inc_cset_size;
2934:     _collection_set_bytes_used_before = _inc_cset_bytes_used_before;

2940:     time_remaining_ms -= _inc_cset_predicted_elapsed_time_ms;
2941:     predicted_pause_time_ms += _inc_cset_predicted_elapsed_time_ms;

2974:   }

2866行目のpredict_base_elapsed_time_ms()はリージョンを退避する処理以外の部分の停止時間を予測します。内部では過去の停止予測時間と実際の停止時間を保持しており、実行を繰り返すたびに予測時間の精度が上がるようになっています。2867行目のpredicted_pause_time_msが予測停止時間を保持するローカル変数で、2869行目のtime_remaining_msが残りの停止可能時間です。

2897行目のin_young_gc_mode()はG1GCが世代別方式であるかを示すフラグを返します。G1GCは必ず世代別G1GC方式で動作しますので、in_young_gc_mode()trueを必ず返します。

2932〜2934行目に掛けて新世代リージョンを回収集合に設定しています。_collection_setメンバ変数が回収集合を表すものです。

2940〜2941行目であらかじめ計算していた停止予測時間を使って、predicted_pause_time_mstime_remaining_msを計算します。『アルゴリズム編 5.6 新世代リージョン数上限決定』で説明したとおり、過去の実行履歴でこの停止予測時間は算出されます。

旧世代リージョン選択

部分的新世代GCの場合は旧世代のリージョンも回収集合に追加します。

share/vm/gc_implementation/g1/g1CollectorPolicy.cpp:choose_collection_set():後半

2976:   if (!in_young_gc_mode() || !full_young_gcs()) {

2981:     do {
2982:       hr = _collectionSetChooser->getNextMarkedRegion(time_remaining_ms,
2983:                                                       avg_prediction);
2984:       if (hr != NULL) {
2985:         double predicted_time_ms = predict_region_elapsed_time_ms(hr, false);
2986:         time_remaining_ms -= predicted_time_ms;
2987:         predicted_pause_time_ms += predicted_time_ms;
2988:         add_to_collection_set(hr);

              /* 省略: should_continueの値設定 */
2997:       }
3002:     } while (should_continue);

3007:   }

3019: }

2976行目のfull_young_gc()は全新世代GCを示すフラグを返すメンバ関数です。もしfalseを返す場合は、部分的新世代GCのモードにあることを示します。

2982行目で残りの停止可能時間内で追加可能なリージョンを取得します。もし存在しなければNULLを返します。

存在する場合、2985行目のpredict_region_elapsed_time_ms()で予測停止時間を算出して、2988行目で回収集合に追加します。最終的にtime_remaining_msがマイナスになった場合はshould_continuefalseにして、whileループを抜けます。

11.3 ステップ2—ルート退避

ルート退避はルートから直接参照可能な回収集合内のオブジェクトを別の空きリージョンに退避するステップです。

evacuate_collection_set()

「11.1.3 do_collection_pause_at_safepoint()」で説明したとおり、退避はevacuate_collection_set()で実行されます。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

4785: void G1CollectedHeap::evacuate_collection_set() {

4792:   int n_workers = (ParallelGCThreads > 0 ? workers()->total_workers() : 1);
4793:   set_par_threads(n_workers);
4794:   G1ParTask g1_par_task(this, n_workers, _task_queues);

4802:   if (G1CollectedHeap::use_parallel_gc_threads()) {
4806:     workers()->run_task(&g1_par_task);
4807:   } else {
4809:     g1_par_task.work(0);
4810:   }

evacuate_collection_set()では「10.2.3 G1GCのルートスキャン」で登場したG1ParTaskを生成し、(可能な場合は並列で)実行します。

G1ParTaskはすでに説明した通り、process_strong_roots()を使ってすべてのルートをスキャンし、G1GCの場合はG1ParScanAndMarkExtRootClosureクラスのdo_oop()を適用します。このdo_oop()にはオブジェクトを退避する処理が実装されています。

オブジェクト退避

do_oop()は最終的にG1ParCopyHelperクラスのcopy_to_survivor_space()を呼び出し、オブジェクトを空きリージョンに退避します。この中の処理は『アルゴリズム編 3.8.1 オブジェクト退避』で詳細に述べたため省略します。

コピー関数

とはいえ、全部見ないもの何か味気ないものですので、ここからは著者が読んでいて面白かった「オブジェクトのコピーに使う関数」を紹介しておきます。

以下はG1GCでオブジェクトをコピーする部分だけ抜き出したものです。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

4397:     Copy::aligned_disjoint_words((HeapWord*) old, obj_ptr, word_sz);

aligned_disjoint_wordsCopyクラスの静的メンバ関数です。

share/vm/utilities/copy.hpp

114:   static void aligned_disjoint_words(HeapWord* from,
                                          HeapWord* to, size_t count) {
115:     assert_params_aligned(from, to);
116:     assert_disjoint(from, to, count);
117:     pd_aligned_disjoint_words(from, to, count);
118:   }

引数にはfromto、そしてコピーするデータのワード数を引数に取ります。115行目のassert_params_aligned()fromtoがアラインメントされた値かをチェックします。116行目ではfromからtoへ、コピーする際にメモリ領域が重ならないことをチェックしています。117行目のpd_aligned_disjoint_words()は各OSごとに定義されている静的メンバ関数です。

ここではOSがLinuxでCPUがx86のものに対するpd_aligned_disjoint_words()を見てみます。

os_cpu/linux_x86/vm/copy_linux_x86.inline.hpp

73:  static void pd_disjoint_words(HeapWord* from, HeapWord* to, size_t count) {
74:  #ifdef AMD64
75:    switch (count) {
76:    case 8:  to[7] = from[7];
77:    case 7:  to[6] = from[6];
78:    case 6:  to[5] = from[5];
79:    case 5:  to[4] = from[4];
80:    case 4:  to[3] = from[3];
81:    case 3:  to[2] = from[2];
82:    case 2:  to[1] = from[1];
83:    case 1:  to[0] = from[0];
84:    case 0:  break;
85:    default:
86:      (void)memcpy(to, from, count * HeapWordSize);
87:      break;
88:    }
89:  #else
         /* 省略: その他 */
108: #endif // AMD64
109: }

139: static void pd_aligned_disjoint_words(HeapWord* from,
                                           HeapWord* to, size_t count) {
140:   pd_disjoint_words(from, to, count);
141: }

pd_aligned_disjoint_words()pd_disjoint_words()をそのまま呼び出します。

pd_disjoint_words()はCPUがAMD64の場合と、そうでない場合で処理が異なります。まず、AMD64だった場合を見てみましょう。8ワード以下の場合、76〜84行目までのcase文に当てはまり、=演算子によるメモリコピーがおこなわれます。それ以外はmemcpy()を呼び出しています。たぶん、コピーするデータがあまりにも小さいと関数呼び出しのコストの方がバカにならないのでmemcpy()の呼び出しをケチっているのでしょう。

os_cpu/linux_x86/vm/copy_linux_x86.inline.hpp

73:   static void pd_disjoint_words(HeapWord* from, HeapWord* to, size_t count) {
74:   #ifdef AMD64
          /* 省略 */
89:   #else
91:    intx temp;
92:    __asm__ volatile("        testl   %6,%6       ;"
93:                     "        jz      3f          ;"
94:                     "        cmpl    $32,%6      ;"
95:                     "        ja      2f          ;"
96:                     "        subl    %4,%1       ;"
97:                     "1:      movl    (%4),%3     ;"
98:                     "        movl    %7,(%5,%4,1);"
99:                     "        addl    $4,%0       ;"
100:                    "        subl    $1,%2        ;"
101:                    "        jnz     1b          ;"
102:                    "        jmp     3f          ;"
103:                    "2:      rep;    smovl       ;"
104:                    "3:      nop                  "
105:                    : "=S" (from), "=D" (to), "=c" (count), "=r" (temp)
106:                    : "0"  (from), "1"  (to), "2"  (count), "3"  (temp)
107:                    : "memory", "cc");
108: #endif // AMD64
109: }

AMD64以外はインラインアセンブラを使ってコピーを自前で実装しています。簡単に概要だけ説明します。

92〜93行目はcount0でないことをチェックする処理です。92行目のtestlcountのANDをとっています。もしcountが0の場合は93行目のjzで104行目にジャンプします。

94〜95行目はcount32以下であることチェックする処理です。もしcount32より大きければ、95行目のjaは103行目にジャンプします。

103行目はrepを使ったストリングス命令smovlの実行です。countの分だけsmovlを繰り返し、fromからtoへデータをコピーします。

96〜102行目ではジャンプによるループでコピーをおこなっています。countが32以下であればこっちを使います。96行目はfromtoをオフセットを求め、toのレジスタに格納します。97行目でfromの1ワード分のデータをtempのレジスタに格納。98行目でtempのデータをfrom + オフセットの位置(最初はtoの先頭)へコピー。99行目でオフセット加算。100行目でcount1減らす。101行目でcount0になってないか確認。0じゃければ97行目にジャンプ。もし0であれば103行目のjmpで104行目にジャンプ。

と、こんな感じです。はたしてこれはmemcpy()よりも速いのでしょうか。卜部さんのかかれた次の記事では(これはmemset64についてですが)興味深い実験結果と考察が書かれています。ぜひ読んでみてください。

memset64の用途では上記の結果になりますが、memcpy()の場合はどうなんでしょうね。また、x86ではどう変化するでしょうか。興味がある方はぜひ比較してみてください。

インラインアセンブラの読み方に関しては次の記事を参考にしました。

11.4 ステップ3—退避

ルート退避で退避したオブジェクトのフィールドは退避キューに保持されています。このステップではその退避キュー内に保持したフィールドが参照している子オブジェクトを次々に退避していきます。

G1ParTaskwork()では、ルート退避完了後にG1ParEvacuateFollowersClosuredo_void()を呼び出します。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

4620:   void work(int i) {

          /* 省略: ルート退避 */

4666:     {

4668:       G1ParEvacuateFollowersClosure evac(_g1h, &pss, _queues, &_terminator);
4669:       evac.do_void();

4674:     }

do_void()の中では退避キューが保持するオブジェクトを次々に退避していきます。

share/vm/gc_implementation/g1/g1CollectedHeap.cpp

4565: void G1ParEvacuateFollowersClosure::do_void() {
4566:   StarTask stolen_task;
4567:   G1ParScanThreadState* const pss = par_scan_state();
4568:   pss->trim_queue();

        /* 省略: タスクスティーリング */

4587: }

4567行目のG1ParScanThreadStateのインスタンス内部で退避キューを保持しています。この退避キューはスレッドローカルなもので、ほかの退避スレッドと競合しません。4568行目のtrim_queue()で退避キューが空になるまでオブジェクト退避を続けます。

ほかのスレッドが退避対象が多すぎた場合は、タスクスティーリングを使って仕事量が偏り過ぎないように調整します。


御意見・御感想・誤植の指摘などは@nari3もしくはauthorNari/g1gc-impl-book - GitHubまでお願いします。

Webサイトのトップページ

(C) 2011-2012 Narihiro Nakamura