第4章　アロケータ

この章ではHotspotVM内のメモリアロケータについて説明します。

G1GCにおけるオブジェクトのアロケーションの概要をVMヒープの初期化から順を追ってみていきましょう。

図4.1: (1)VMヒープの予約

まず、G1GCのVMヒープ（G1GCヒープとパーマネント領域）の最大サイズ分をメモリ領域に予約します（図4.1）。最大G1GCヒープサイズと最大パーマネント領域サイズは言語利用者が指定できます。未指定の場合は、G1GCヒープの最大サイズが64Mバイト、パーマネント領域の最大サイズが64Mバイト、合わせて128Mバイトがデフォルトとして設定されます（使用するOSによってデフォルト値は多少異なります）。また、G1GCのVMヒープはリージョンのサイズでアラインメントされます。

ここまでの段階では、メモリ領域をただ予約するだけで、実際に物理メモリは割り当てられない、ということに注意してください。

図4.2: (2)VMヒープの確保

次に、予約しておいたVMヒープに必要最小限のメモリ領域を確保します。ここで実際に物理メモリが割り当てされます。G1GCヒープの方はリージョン単位で確保されます（図4.2）。

図4.3: (3)オブジェクトのアロケーション

パーマネント領域のアロケーションの説明をここからは除外し、G1GCヒープ内へのアロケーションのみを見ています。G1GCヒープにはリージョンが確保されました。そのリージョンに対してオブジェクトがアロケーションされます（図4.3）。

図4.4: (4)G1GCヒープの拡張

オブジェクトのアロケーションによってリージョンが枯渇すると、予約しておいたメモリ領域からメモリを確保し、新たにリージョンを1個割り当て、G1GCヒープを拡張します（図4.4）。そして、割り当てたリージョンの中にオブジェクトをアロケーションします。

ここからはVMヒープの予約が実際どのように実装されているか見ていきたいと思います。

それぞれのVMヒープの初期化はCollectedHeapクラスを継承した子クラスのinitialize()に記述されます。G1GCの場合は、G1CollectedHeapのinitialize()です。VMヒープの予約はこのinitialize()に記述されています。VMヒープの予約処理部分だけを抜き出したものを次に示します。

1794: jint G1CollectedHeap::initialize() {

1810:   size_t max_byte_size = collector_policy()->max_heap_byte_size();

1819:   PermanentGenerationSpec* pgs = collector_policy()->permanent_generation();

1825:   ReservedSpace heap_rs(max_byte_size + pgs->max_size(),
1826:                         HeapRegion::GrainBytes,
1827:                         UseLargePages, addr);

1810行目のcollector_policy()メンバ関数はG1GCに関するフラグや設定値などが定義されているG1CollectorPolicyインスタンスへのポインタを返し、max_heap_byte_size()メンバ関数は名前のとおり、最大G1GCヒープサイズを返します。したがって、max_byte_sizeローカル変数には最大G1GCヒープサイズが格納されます。

1819行目のpgsにはパーマネント領域に関する設定値などが定義されているPermanentGenerationSpecが格納されます。

1825行目でReservedSpaceクラスのインスタンスを生成しています。この際に実際にVMヒープを予約しています。ReservedSpaceクラスのインスタンス生成には次の引数を渡します。1827行目のほかの引数（UseLargePages、addr）については使用されませんので無視してください。

1. 最大G1GCヒープサイズ + 最大パーマネント領域サイズ
2. リージョンサイズ（HeapRegion::GrainBytes）

1. は予約するメモリ領域のサイズです。2.はメモリ領域のアラインメントに使います。

肝心のReservedSpaceクラスの定義は次のとおりです。

32: class ReservedSpace VALUE_OBJ_CLASS_SPEC {
33:   friend class VMStructs;
34:  private:
35:   char*  _base;
36:   size_t _size;
38:   size_t _alignment;

35行目の_baseメンバ変数には予約したメモリ領域の先頭アドレスが格納されます。_sizeにはメモリ領域のサイズ、_alignmentにはメモリ領域がアラインメントされた値がそれぞれ格納されます。

ここでは実装の詳細は書きませんが、今の段階ではこのReservedSpaceクラスを生成するとメモリ領域が予約されると考えてもらえばよいでしょう。

1794: jint G1CollectedHeap::initialize() {

        /* 省略：ReservedSpace生成 */

1884:   ReservedSpace g1_rs   = heap_rs.first_part(max_byte_size);

1889:   ReservedSpace perm_gen_rs = heap_rs.last_part(max_byte_size);

ReservedSpaceクラスのインスタンスを生成し終えると、G1GCヒープとパーマネント領域を分割して、それぞれに対応したローカル変数（g1_rs・perm_gen_rs）に格納します。

予約したVMヒープ用のメモリ領域を実際に確保していくクラスがVirtualSpaceクラスです。

143: class G1CollectedHeap : public SharedHeap {

176:   VirtualSpace _g1_storage;

G1CollectedHeapクラスにはVirtualSpaceクラスのインスタンスをもつメンバ変数が定義されています（ポインタではないことに注意してください）。

1794: jint G1CollectedHeap::initialize() {

        /* 省略：G1GCヒープ用メモリ領域の予約 */

1891:   _g1_storage.initialize(g1_rs, 0);

1891行目で_g1_storageメンバ変数を初期化します。第1引数に生成したG1GCヒープ用のReservedSpaceのポインタを渡し、第2引数には確保するサイズを指定します。この場合は0です。したがって、まだメモリ領域は確保されていません。

では、実際に確保する処理を見てみましょう。

1794: jint G1CollectedHeap::initialize() {

1809:   size_t init_byte_size = collector_policy()->initial_heap_byte_size();

        /* 省略：G1GCヒープ用メモリ領域の予約 */

1937:   if (!expand(init_byte_size)) {

initialize()の1809行目でinit_byte_sizeに起動時に確保するメモリ領域サイズを格納します。そして、expand()メンバ関数内でメモリ領域を確保します。

expand()は指定されたメモリ領域分のリージョンを確保するメソッドです。VMヒープの初期化時、空きリージョンが枯渇したときに呼び出されます。

1599: bool G1CollectedHeap::expand(size_t expand_bytes) {

        /* 省略:
         * expand_bytesをリージョンサイズで切り上げて
         * aligned_expand_bytes に設定
         */

1610:   HeapWord* old_end = (HeapWord*)_g1_storage.high();
1611:   bool successful = _g1_storage.expand_by(aligned_expand_bytes);
1612:   if (successful) {
1613:     HeapWord* new_end = (HeapWord*)_g1_storage.high();
1624:     expand_bytes = aligned_expand_bytes;
1625:     HeapWord* base = old_end;
1626:
1627:     // old_endからnew_endまでのヒープリージョン作成
1628:     while (expand_bytes > 0) {
1629:       HeapWord* high = base + HeapRegion::GrainWords;
1630:
1631:       // リージョン生成
1632:       MemRegion mr(base, high);
1634:       HeapRegion* hr = new HeapRegion(_bot_shared, mr, is_zeroed);
1635:
1636:       // HeapRegionSeqに追加
1637:       _hrs->insert(hr);
1638:       _free_list.add_as_tail(hr);

1643:       expand_bytes -= HeapRegion::GrainBytes;
1644:       base += HeapRegion::GrainWords;
1645:     }

1667:   return successful;
1668: }

前半部分で引数に受け取ったexpand_bytesをリージョンサイズで切り上げ、aligned_expand_bytesに設定します。

1610行目で確保中メモリ領域の終端を受け取ります。VMヒープ初期化時にはメモリ領域はまだ確保されていませんので、予約されたVMヒープ用メモリ領域の先頭アドレスが戻ります。同行に登場するHeapWord*はVMヒープ内のアドレスを指す場合に使用します。

1611行目にあるVirtualSpaceのexpand_by()で実際のメモリ領域の確保を行います。expand_by()は確保するメモリ領域のサイズを引数に取ります。ここでは引数にaligned_expand_bytes、つまり確保するリージョン分のバイト数を渡しています。

メモリ領域の確保に成功した場合は、リージョンを管理するHeapRegionを生成します。

1629行目でbaseからリージョン1個分先のアドレスをhighに設定します。1632行目のMemRegionクラスはアドレスの範囲を管理するクラスです。コンストラクタの引数には範囲の先頭アドレスと終端アドレスを渡します。そして、1634行目でHeapRegionクラスのインスタンスを生成します。第1引数の_bot_sharedと第3引数のis_zeroedは特に関係ありませんので、ここでは無視します。

1637行目で生成したHeapRegionインスタンスへのポインタをHeapRegionSeqに追加し、1638行目で_free_region_listにつなげばリージョン1個分のメモリ領域確保は終了です。あとはこれを確保したメモリ領域（aligned_expand_bytes）の分、繰り返すだけです。

メモリ領域の予約・確保は実際どのように実装されているのでしょうか。実装方法はそれぞれのOSによって異なります。まずはWindowsの実装方法を調べていきましょう。

WindowsにはVirtualAlloc()というAPIがあります。HotspotVMではこのAPIを使ってメモリ確保の予約、確保を実現しています。

VirtualAlloc()は仮想アドレス空間内のページ領域を予約または確保する、そのものズバリなAPIです。引数には次の情報を渡します。

1. 確保、また予約したいメモリ領域の開始アドレス。NULLの場合、システムがメモリ領域の開始アドレスを決定
2. サイズ
3. 割り当てのタイプ
4. アクセス保護のタイプ

では、実際にメモリ領域を予約しているos::reserve_memory()メンバ関数を見てみましょう。

2717: char* os::reserve_memory(size_t bytes, char* addr, size_t alignment_hint) {
2721:   char* res = (char*)VirtualAlloc(addr, bytes, MEM_RESERVE, PAGE_READWRITE);
2724:   return res;
2725: }

2721行目の第3引数に渡されているMEM_RESERVEがメモリ領域を予約する際のフラグです。MEM_RESERVEが渡されると指定されたサイズのメモリ領域は予約されるだけで実際には物理メモリに割り当てされません。

次に、メモリ領域を確保するos::commit_memory()メンバ関数を見てみましょう。不要な部分は省略しました。

2857: bool os::commit_memory(char* addr, size_t bytes, bool exec) {

2866:   bool result = VirtualAlloc(addr, bytes, MEM_COMMIT, PAGE_READWRITE) != 0;

2872:     return result;

2874: }

2866行目の第3引数に渡されているMEM_COMMITがメモリ領域を確保する際のフラグです。MEM_COMMITが渡されると指定されたサイズ分のメモリ領域が物理メモリとして実際に割り当てられます。

Linuxではメモリ領域の予約・確保をmmap()で実装しています。

Linuxにはメモリ領域を予約するという概念はなく、mmap()するとメモリ領域は確保されてしまいます。ただし、メモリ領域は確保されてもすぐに物理メモリが割り当てられるわけではありません。物理メモリが割り当てられるのは確保したメモリ領域に実際にアクセスされたときです。

メモリ領域の予約にあたる部分であるos::reserve_memory()メンバ関数のLinux版を見ていきましょう。

2787: char* os::reserve_memory(size_t bytes, char* requested_addr,
2788:                          size_t alignment_hint) {
2789:   return anon_mmap(requested_addr, bytes, (requested_addr != NULL));
2790: }

2751: static char* anon_mmap(char* requested_addr, size_t bytes, bool fixed) {
2752:   char * addr;
2753:   int flags;
2754:
2755:   flags = MAP_PRIVATE | MAP_NORESERVE | MAP_ANONYMOUS;
2756:   if (fixed) {
2758:     flags |= MAP_FIXED;
2759:   }

2763:   addr = (char*)::mmap(requested_addr, bytes, PROT_READ|PROT_WRITE,
2764:                        flags, -1, 0);

2776:   return addr == MAP_FAILED ? NULL : addr;
2777: }

os::reserve_memory()は内部でos::anon_mmap()を呼び出すだけです。os::anon_mmap()はMAP_ANONYMOUSを使ってメモリ領域を確保します。Linux版ではメモリ領域を予約するのではなく、実際は確保する点に注意してください。

VMヒープはリージョンのサイズでアラインメントされています。つまり、VMヒープの先頭アドレスはリージョンサイズの倍数になっているということです。HotspotVMではこのアラインメントをどのようにして実現しているのでしょうか？

実装方法は拍子抜けするほどシンプルです。具体的には次の手順で処理を行います。ここでは説明を簡単にするため、アラインメントサイズ（リージョンサイズ）を1Kバイト、VMヒープのサイズは1Kバイトよりも大きいと仮定します。

1. VMヒープサイズ分のメモリ領域を予約
2. 1.で予約したメモリ領域の範囲に1Kバイトの倍数アドレスを記録
3. 予約したメモリ領域を破棄
4. 2.で記録しておいたアドレスを指定し、再度VMヒープサイズ分のメモリ領域を予約
5. 4.に失敗した場合は1.に戻る

図4.5: アラインメントされたVMヒープの予約

まず、1.でVMヒープサイズ分のメモリ領域を予約してしまいます。メモリ領域の予約にはos::reserve_memory()関数を使います。

予約したメモリ領域の範囲内には1Kバイトの倍数アドレスがどこかにはあるはずです。1Kバイト以上のメモリ領域を予約しているのですから当然ですね。その1Kバイトの倍数アドレスが、アラインメントされたアドレスになります。ここで重要なのは上記で取得したアラインメントされたアドレスが、OSが「このメモリ領域は使えるよ」と返してきたものだということです。2.ではそのアドレスを記録しておきます。

3.では1.で予約したメモリ領域を一度破棄してしまいます。メモリ領域は予約しているだけであり、実メモリには割り当てられてはいませんので、破棄にかかるコストは微々たるものです。

4.では2.で保持しておいたアドレスを指定して、VMヒープサイズ分のメモリ領域を予約します。メモリ領域の予約を実際におこなうmmap()やVirtualAlloc()は予約するメモリ領域の先頭アドレスを指定できますので、これを利用します。

ただし、2.の段階では使ってよかったはずのアドレスが、4.の段階で使えなくなっていることも考えられます。そのため、失敗した場合は1.に戻り成功するまで処理を繰り返します。

次はVMヒープ上の確保されたリージョンからオブジェクトをアロケーションする部分を見ていきましょう。

CollectedHeapの共通のインタフェースから、実際のG1GCのVMヒープからオブジェクトが割り当てられるまでのシーケンス図を図4.6に示します。

図4.6: オブジェクトアロケーションの流れ

まず、VMはオブジェクトの割り当て要求としてCollectedHeap::obj_allocate()を呼び出します。次に、CollectedHeapはUniverse::heap()を呼び出して、起動オプションで選択されたVMヒープクラス（この場合はG1CollectedHeap）のインスタンスを取得します。そして、VMヒープクラス共通のmem_allocate()を呼び出し、必要なサイズのメモリ領域の割り当てを行います。G1CollectedHeap内部でVMヒープから適切にメモリを切り出し、最終的にCollectedHeapに割り当てたメモリ領域を返します。その後、指定されたオブジェクト種類に応じたセットアップを行い、VMに返却します。

G1CollectedHeap内でおこわれる、VMヒープへのメモリ割り当てを見ていきましょう。まずは、G1CollectedHeapのmem_allocate()です。

830: HeapWord*
831: G1CollectedHeap::mem_allocate(size_t word_size,
832:                               bool   is_noref,
833:                               bool   is_tlab,
834:                               bool*  gc_overhead_limit_was_exceeded) {

843:     HeapWord* result = NULL;

845:       result = attempt_allocation(word_size, &gc_count_before);

849:     if (result != NULL) {
850:       return result;
851:     }

         /* 省略: GC実行 */

884: }

845行目でオブジェクトのサイズを指定してattempt_allocation()を呼び出します。もし割り当てられなければGCを実行してVMヒープに空きを作るのですが、ここでは省略します。

63: inline HeapWord*
64: G1CollectedHeap::attempt_allocation(size_t word_size,
65:                                     unsigned int* gc_count_before_ret) {

70:   HeapWord* result = _mutator_alloc_region.attempt_allocation(word_size,
71:                                                       false /* bot_updates */);
72:   if (result == NULL) {
73:     result = attempt_allocation_slow(word_size, gc_count_before_ret);
74:   }

79:   return result;
80: }

70行目のattempt_allocation()はG1AllocRegionのメンバ関数で、リージョンからオブジェクトを割り当てようと試みます。G1AllocRegionはオブジェクトを割り当てるリージョンを管理するクラスで、空きのあるリージョンを内部で1つだけ保持しています。

もしG1AllocRegion内のリージョンに必要な分の空きがなく、割り当てに失敗したら、73行目でattempt_allocation_slow()が呼び出されます。attempt_allocation_slow()ではG1AllocRegionに対して、新たな空きリージョンが設定され、リージョンに対して必要なサイズ分が割り当てられます。処理の内容については本筋とはそれほど関係ありませんので割愛します。

55: inline HeapWord* G1AllocRegion::attempt_allocation(size_t word_size,
56:                                                    bool bot_updates) {

59:   HeapRegion* alloc_region = _alloc_region;

62:   HeapWord* result = par_allocate(alloc_region, word_size, bot_updates);
63:   if (result != NULL) {

65:     return result;
66:   }

68:   return NULL;
69: }

59行目に登場する_alloc_regionメンバ変数が、G1AllocRegionが管理する空きリージョンです。62行目でその空きリージョンを引数にpar_allocate()を呼び出します。

par_allocate()からいくつかの関数を経由し、最終的に空きリージョン（HeapRegion）のallocate_impl()メンバ関数を呼び出します。

allocate_impl()はHeapRegionが継承しているContiguousSpaceクラスに定義してあるメンバ関数で、実際にリージョンからメモリ領域を確保する役割を持ちます。

827: inline HeapWord* ContiguousSpace::allocate_impl(size_t size,
828:                                                 HeapWord* const end_value) {
838:   HeapWord* obj = top();
839:   if (pointer_delta(end_value, obj) >= size) {
840:     HeapWord* new_top = obj + size;
841:     set_top(new_top);
843:     return obj;
844:   } else {
845:     return NULL;
846:   }
847: }

allocate_impl()の引数であるsizeにはオブジェクトサイズのバイト数ではなく、ワード数が渡されます。もう1つの引数、end_valueにはリージョン内チャンクの終端アドレスが渡されます。

839行目のpointer_delta()は指定されたアドレスの差分をワード数で戻す関数です。ここでは、リージョン内の空き領域の先頭を指す_topと、end_valueの差分を求め、空きメモリ領域のサイズをワード数で返します。もし、size分の空きがなければ845行目でNULLを戻します。

リージョンに充分な空きがあれば、840行目でobjをsize分ずらして、841行目でチャンクの先頭アドレスに設定します。そして、確保したメモリ領域の先頭（obj）を843行目で戻します。

アロケーションの工夫の1つとしてTLABについて簡単に説明しておきましょう。

VMヒープはすべてのスレッドの共有領域です。そのため、VMヒープからオブジェクトをアロケーションする際にはVMヒープ全体をロックし、ほかのスレッドからのアロケーションが割り込まないようにする必要があります。

しかし、せっかく別々のCPUコアで動作していたスレッドをアロケーション時にいちいちロックしてしまうのは嬉しくありません。その問題を解決するためにそれぞれのスレッド専用のアロケーション用バッファを持たせてロックの回数を少なくしよう、というのがTLABの考えです。

あるスレッドの最初のオブジェクトアロケーション時に、一定サイズのメモリ領域をVMヒープからアロケーションし、スレッド内にバッファとして貯め込みます。このバッファをTLABと呼びます。VMヒープのロックが必要なのは、TLABを確保するときのみです。

同スレッドからの次のオブジェクトアロケーション時には、TLAB内からオブジェクトサイズ分アロケーションします。この時は他スレッドからアクセスされる可能性がないため、VMヒープのロックは必要ありません。

図4.7: TLABによるアロケーション

TLABは通常はオフになっていますが、言語利用者がJavaの起動オプションによってオンにできます。さらにTLABのサイズも指定可能です。