第13章 正確なGCへの道

本章では、正確なGCのための「正確な」ルート情報をHotspotVMがどのようにしてGCに提供しているか、という点について述べていきます。

13.1 スタックマップ

正確なGCとするために、HotspotVMではVMのスタックマップ(Stack map)*1と呼ばれるものをGCの際に生成します。スタックマップはVMのスタック内にあるすべてのオブジェクトへのポインタの位置を示したものです。

[*1] スタックマップ: 他にもGC map, Oop mapという呼び方がある

プリミティブ型と参照型の変数

リスト13.1: プリミティブ型と参照型

 1: int primitiveType = 1;                // プリミティブ型
 2: Object referenceType = new Object();  // 参照型

Javaの変数に格納される型としてintfloatといったプリミティブ型があります(リスト13.1の1行目)。プリミティブ型はJava上では数値として扱われます。それと同様にC++(HotspotVM)上でもintfloatといった数値として扱われます。

一方、Objectクラス(またはその子クラス)のインスタンスを指す参照型があります(リスト13.1の2行目)。参照型はC++(HotspotVM)上ではオブジェクトへのポインタとして扱われます。

ここで問題となるのがプリミティブ型はVM上で数値として扱われるという点です。つまり、プリミティブ型の値は偽ポインタの可能性があります。したがって、GCを正確なGCとするためには、プリミティブ型と参照型の変数を識別しなければなりません。

HotspotVMのスタック

参照型の識別の前に、HotspotVMのスタックについて簡単に説明しておきましょう。

まず、HotspotVMは基本的にバイトコード(.classファイル)内の命令セットを1つずつ読み込んで、命令に従った処理をこなします。命令セットは実行する操作を定義した1バイトのオペコードと、操作が用いるデータとなるオペランドで構成されています。オペコードは実際には0x32のようなただのバイト列です。しかし、これでは人間が読むにはあまりに辛いため、通常、オペコードを人間が読めるようなaaloadという形式で表現します。これをニーモニックと呼びます。

そして、HotspotVMにはJVMスタックとフレームというものがあります。Cのコールスタック、コールフレームと役割は同じです。Java上のメソッドが呼ばれると対応するフレームがJVMスタックに積まれ、メソッドの実行が終了するとフレームがJVMスタックから降ろされます。

JVMスタック、フレーム

図13.1: JVMスタック、フレーム

また、フレームの中にはローカル変数とオペランドスタックというものがあります。ローカル変数はメソッド内で使用するローカル変数を格納する部分です。また、メソッドの引数もローカル変数として扱われます。

HotspotVMはスタックマシンです。そのため、VM上の計算はスタックを使って処理します。HotspotVMはメソッドフレーム内のオペランドスタックを使って計算を行います。

HotspotVMの実行フロー

では、実際のサンプルコードを使って、ローカル変数とオペランドスタックがどのように使われるか見ていきましょう。

リスト13.2: TwoDifferentLocalVars.java

 1: class TwoDifferentLocalVars {
 2:     public static void main(String args[]){
 3:         int primitiveType = 1;                // プリミティブ型
 4:         Object referenceType = new Object();  // 参照型
 5:     }
 6: }

リスト13.2のmain()メソッドはプリミティブ型と参照型をローカル変数に格納するシンプルなメソッドです。このメソッドをJavaバイトコードに変換したものがリスト13.3です。

リスト13.3: TwoDifferentLocalVars.java:バイトコード

pc( 0): iconst_1
pc( 1): istore_1
pc( 2): new           #2 // class java/lang/Object
pc( 5): dup
pc( 6): invokespecial #1 // Method java/lang/Object."<init>"
pc( 9): astore_2
pc(10): return

リスト13.3内のバイトコードに振られている番号は行番号ではなく、メソッド内のバイトコードに一意に振られているプログラムカウンタ(以下、pc)です。HotspotVMはリスト13.3を上から順番に実行し、ローカル変数にプリミティブ型と参照型の値を格納します。バイトコードは一見難しそうに見えますが、VMの実行フローのイメージと命令セットの意味が多少理解できれば、読み解くのはそれほど難しくありません。

表13.1: ニーモニックと命令内容

ニーモニック命令内容
iconst_'i''i'の部分にあたるintの定数をオペランドスタックに積む
istore_'n'ローカル変数配列の'n'番目にオペランドスタックの先頭のint型の値を格納する
new新たなオブジェクトを生成し、オペランドスタックに積む
dupオペランドスタックの先頭にある値を複製し、オペランドスタックに複製した値を積む
invokespecialインスタンス初期化メソッドなどの特殊なメソッドを呼び出す
astore_'n'ローカル変数配列の'n'番目にオペランドスタックの先頭の参照型の値を格納する
returnメソッドからvoidをリターンする

表13.1にはリスト13.3に登場するニーモニックとその命令内容を示しています。

バイトコード実行フロー

図13.2: バイトコード実行フロー

図13.2はバイトコードの実行フローを示しています。最終的にローカル変数1に1が格納され、ローカル変数2にはObjectクラスのインスタンスのアドレスが格納されています。ローカル変数1はリスト13.2内のprimitiveType変数であり、ローカル変数2はreferenceType変数です。

また、上記のようにバイトコードを読み込みながら命令セットを1つずつ実行するインタプリタを「バイトコードインタプリタ」といいます。

さて、GCの話に戻りましょう。もし、プログラムカウンタ(pc)10の状態でGCが実行された場合は、GCはローカル変数2が参照するオブジェクトのみを確実に生きていると判断しなければなりません。そして、プリミティブ型の値が格納されているローカル変数1はGC対象ではないということを識別する必要があります。HotspotVMはどのようにしてローカル変数(またはオペランドスタック)内の値を識別しているのでしょうか?

スタックマップとは?

ここで注目するのがJavaの型情報です。リスト13.3を見るとローカル変数やオペランドスタックに格納される際のニーモニックが、プリミティブ型と参照型で異なっていることがわかります。プリミティブ型の場合はistore_1となっており、参照型の場合はastore_2となっていますね。

HotspotVMはバイトコードの型情報を利用して、GC発生時のスタック上のフレームに対するスタックマップを作成します。スタックマップとはその名前のとおり、参照型を格納しているローカル変数やオペランドスタックの位置を示した地図です。実際のスタックマップは00100というようなビット列で表され、ビット列のビットが立っている部分に対応するローカル変数(またはオペランドスタック)に参照型の値が格納されていることを示しています。

抽象的インタプリタ

スタックマップは抽象的インタプリタによって作成されます。抽象的インタプリタとは簡単にいえば型情報のみを記録するインタプリタのことです。抽象的インタプリタは、ローカル変数とオペランドスタック内に格納された値の型だけを記録します。実際に格納された値について、抽象的インタプリタは無関心です。

では、前の「HotspotVMの実行フロー」で説明したバイトコード(リスト13.3)を使って、抽象的インタプリタと通常のインタプリタの動作を見比べていきましょう。

リスト13.4: TwoDifferentLocalVars.java:バイトコード実行フロー(抽象的インタプリタ)

BasicBlock#0
pc( 0): locals = 'r  ', stack = ''   // iconst_1
pc( 1): locals = 'r  ', stack = 'v'  // istore_1
pc( 2): locals = 'rv ', stack = ''   // new           #2
pc( 5): locals = 'rv ', stack = 'r'  // dup
pc( 6): locals = 'rv ', stack = 'rr' // invokespecial #1
pc( 9): locals = 'rv ', stack = 'r'  // astore_2
pc(10): locals = 'rvr', stack = ''   // return

抽象的インタプリタの実行フローは簡単に書き表すことができます。リスト13.4がその実行フローです。リスト13.4中のlocalsはローカル変数、stackはオペランドスタックです。ローカル変数やオペランドスタックにあるr(reference)は参照型、v(value)はプリミティブ型と考えてください。ローカル変数内の半角スペースはまだ初期化されていないという意味です。また、BasicBlock#0の役割については後の「13.1.7 条件分岐時のスタックマップ」の項で説明しますので、今は無視してください。

抽象的インタプリタは、ある命令セット実行前のローカル変数とオペランドスタックの型情報を記録します。例えばpc0ではiconst_1の実行前の型情報が記録されています。そのため、ローカル変数(locals)には引数のargsの型を表すrのみが記録されています。続いて、pc1でiconst_1を実行した結果、オペランドスタック(stack)には1の型を表すvのみが記録されます。

このように、抽象的インタプリタは実際の値は気にせず、型情報のみを淡々と記録します。そして、スタックマップは、1つのバイトコード実行に対応する、抽象的インタプリタが記録した型情報から作成されます。

スタックマップの作成

GCは基本的に命令セット実行中のさまざまなタイミングで発生します。オブジェクトを生成する命令セット実行中にGCが発生するかもしれませんし、足し算のおこなう命令セット実行中にGCが発生するかもしれません。

もしある命令セット実行中にGCが発生したとき、フレーム内のローカル変数とオペランドスタック内にある参照型が指すオブジェクトはGCに確実に生きていると判断されなければなりません。そのためには、GCが発生時の命令セット実行時のスタックマップを作成する必要があります。

リスト13.4のpc5の命令セット(dupオペコード)を実行中にGCが発生したと想定し、どのようにスタックマップが作成されるかを見ていきましょう。

スタックマップ作成

図13.3: スタックマップ作成

図13.3は生成したスタックマップを示しています。ローカル変数の先頭とオペランドスタックの先頭に対応するビットが立っていることがわかります。GCは、このスタックマップを見て「ローカル変数の先頭とオペランドスタックの先頭には参照型の値が格納されている」と判断し、それらが参照するオブジェクトは確実に「生きている」と判断します。

条件分岐時のスタックマップ

今までは条件分岐なしのサンプルプログラムを例にとってスタックマップの作成を見てきましたが、実は条件分岐が1つ入るだけで、スタックマップの作成は格段と難しくなります。次のサンプルコードを見てください。

リスト13.5: TwoControlPath.java

 1: class TwoControlPath {
 2:     static public void main(String args[]){
 3:         if (args.length == 0) {
 4:             Object referenceType = new Object();
 5:             return;
 6:         } else {
 7:             int primitiveType = 1;
 8:             return;
 9:         }
10:     }
11: }

リスト13.5は引数であるargsのサイズを判断して、ローカル変数のreferenceTypeか、primitiveTypeにそれぞれ値を格納します。

リスト13.5のmain()メソッドのバイトコードは次のとおりです。

リスト13.6: TwoControlPath.java:バイトコード

pc( 0): aload_0
pc( 1): arraylength
pc( 2): ifne          14
pc( 5): new           #2 // class java/lang/Object
pc( 8): dup
pc( 9): invokespecial #1 // Method java/lang/Object."<init>"
pc(12): astore_1
pc(13): return
pc(14): iconst_1
pc(15): istore_1
pc(16): return

リスト13.6には新しくifneというニーモニックが登場しています。ifneの命令内容は「オペランドスタックの先頭のint型の値を取り出し、その値は0でなければ指定したpcにジャンプする」です。pc2ではifne 14となっていますので、オペランドスタックの先頭の値(args.length)が0ではない場合、pc14にジャンプします。

さて、ここで注目して欲しいのはpc12とpc15です。どちらともローカル変数1に対して、プリミティブ型、参照型の値をそれぞれ格納しています。つまり、条件分岐によってはローカル変数に格納される値が変わるということです。pc13の時点でGCが発生すれば、ローカル変数1の型は参照型ですが、pc16の時点でGCが発生すれば、ローカル変数1の型はプリミティブ型なのです。

そのため、抽象的インタプリタはすべての状況における型情報を記録しなければなりません。リスト13.5ではargs.length0であった場合と、それ以外の場合の型情報を記録しなければなりません。

そこで抽象的インタプリタはバイトコードを「ベーシックブロック」という単位に切り分けます。リスト13.6の場合は次のようになります。

リスト13.7: TwoControlPath.java:バイトコード実行フロー(抽象的インタプリタ)

BasicBlock#0
pc( 0): locals = 'r ' stack = ''    // aload_0
pc( 1): locals = 'r ' stack = 'r'   // arraylength
pc( 2): locals = 'r ' stack = 'v'   // ifne 14

BasicBlock#2
pc( 5): locals = 'r ' stack = ''    // new
pc( 8): locals = 'r ' stack = 'r'   // dup
pc( 9): locals = 'r ' stack = 'rr'  // invokespecial
pc(12): locals = 'r ' stack = 'r'   // astore_1
pc(13): locals = 'rr' stack = ''    // return

BasicBlock#1
pc(14): locals = 'r ' stack = ''    // iconst_1
pc(15): locals = 'r ' stack = 'v'   // istore_1
pc(16): locals = 'rv' stack = ''    // return

リスト13.7を見ると、if文の真文、偽文のそれぞれがベーシックブロックに分けられていることがわかります(BasicBlock#1BasicBlock#2)。BasicBlock#1のpc14と、BasicBlock#2のpc5のローカル変数、オペランドスタックの型情報は、BasicBlock#0のpc2の実行後のものです。BasicBlock#2では真文のバイトコードを実行しその型情報を記録しています。一方、BasicBlock#1は偽文の型情報を記録しています。

また、リスト13.7のpc13とpc16の時点のローカル変数1の型情報が異なる点に注目してください。つまり、pc13とpc16の時点でGCが発生してもローカル変数1の型をスタックマップによってきちんと識別できるのです。

このベーシックブロックという仕組みによって、メソッド内のさまざまな状況の型情報を記録することが可能です。ベーシックブロックは条件分岐だけではなく、ループやswitch文、try-catch文などにも同様に使用されます。リスト13.2のように条件分岐などがメソッド内に登場に登場しない場合は、メソッド内のすべてのバイトコードがBasicBlock#0として扱われます。

メソッド呼び出し時のスタックマップ

今までは実行中フレームのみのスタックマップがどのように作られるかを見てきました。今度はJVMスタックにフレームが複数積まれていた場合のスタックマップ生成を見てみましょう。

複数フレームのスタックマップ作成

図13.4: 複数フレームのスタックマップ作成

次はメソッド呼び出し時のスタックマップがどのように作られるかを見てみましょう。次のサンプルコードを見てください。

リスト13.8: MethodCall.java

 1: class MethodCall {
 2:     static public void main(String args[]){
 3:         Object referenceType = new Object();
 4:         int primitiveType = 1;
 5:         gcCall(referenceType, primitiveType);
 6:     }
 7: 
 8:     static void gcCall(Object a, int b){
 9:         System.gc();  // GCの実行
10:     }
11: }

リスト13.8がリスト13.2と違う点は5行目のgcCall()メソッドを呼び出している点です。gcCall()メソッドはGCの実行をおこなうメソッドです。参照型とプリミティブ型の引数を受け取りますが、これは説明のためのもので、実際には使用しません。

リスト13.8のmain()メソッドのバイトコードは次のようになります。

リスト13.9: MethodCall.java:バイトコード

pc( 0): iconst_1
pc( 1): istore_1
pc( 2): new           #2 // class java/lang/Object
pc( 5): dup
pc( 6): invokespecial #1 // Method java/lang/Object."<init>"
pc( 9): astore_2
pc(10): iload_1
pc(11): aload_2
pc(12): invokestatic  #3 // Method gcCall
pc(15): return

リスト13.9がリスト13.3と異なるのはpc10~pc15です。ここではgcCall()メソッドの呼び出しを行っています。pc10、pc11でオペランドスタックにgcCall()メソッド用の引数を積み、pc12でgcCall()メソッドを呼び出します。

次に、リスト13.9を抽象的インタプリタにかけてみましょう。

リスト13.10: TwoControlPath.java:バイトコード実行フロー(抽象的インタプリタ)

BasicBlock#0
pc( 0): locals = 'r  ' stack = ''   // iconst_1
pc( 1): locals = 'r  ' stack = 'v'  // istore_1
pc( 2): locals = 'rv ' stack = ''   // new
pc( 5): locals = 'rv ' stack = 'r'  // dup
pc( 6): locals = 'rv ' stack = 'rr' // invokespecial
pc( 9): locals = 'rv ' stack = 'r'  // astore_2
pc(10): locals = 'rvr' stack = ''   // iload_1
pc(11): locals = 'rvr' stack = 'v'  // aload_2
pc(12): locals = 'rvr' stack = 'vr' // invokestatic
pc(15): locals = 'rvr' stack = ''   // return

gcCall()メソッドでGCが発生しますので、スタックマップはリスト13.10のpc12時点のものが作成されます。

スタックマップ作成(メソッド呼び出し時)

図13.5: スタックマップ作成(メソッド呼び出し時)

図13.5を見てください。実はメソッド呼び出し側のフレームのスタックマップを作成する際、メソッドの引数に渡すオペランドスタックの値を無視します。これは引数として渡すオペランドスタックの値が呼び出したメソッドのローカル変数として扱われるためです。無視したオペランドスタックの値は、呼び出したメソッドフレームのローカル変数としてスタックマップを使って正しく識別されます。

コンパイル済みフレーム

JITではメソッドをマシン語にコンパイルする際にスタックマップも一緒に生成します。コンパイル済みメソッドに対するスタックマップは、ある地点のマシンスタックのフレーム内のどこに参照型があるか、またどのレジスタに参照型があるか、を示すものです。

JITでスタックマップを生成する際に気を付けなければならないのは、どの地点のマップを生成するか、という点です。マシン語の1命令を実行するごとにスタックやレジスタの状態は刻々と変わっていきます。ですので、本当は1命令ごとに対応するマップを生成しなければなりません。ただ、それをやってしまうとマップが膨大な量になってしまうため、基本的に次の4つのタイミングのマップのみを生成します。

  1. 後方分岐(例: ループで後ろにジャンプするなど)
  2. メソッド呼び出し
  3. return
  4. 例外が発生するかもしれない命令の実行時

上記のタイミングが「9.3 セーフポイント」で説明したセーフポイントにあたる部分です。上記のタイミング以外でGCが必要なっても、上記のタイミングのいずれかまで進めるか、巻き戻すかして、セーフポイント上でGCを実行させます。

コンパイル済みメソッドをHotspotVMで呼び出すとコンパイル済みフレームと呼ばれるものがJVMスタックに積まれます(図13.6を参照)。

コンパイル済みフレーム

図13.6: コンパイル済みフレーム

コンパイル済みフレームはGCが発生したタイミングのマップを必ず持っているはずですので、そのマップとほかの抽象的インタプリタが導きだしたマップ合成してスタックマップを生成し、ルート情報としてGCに提供します。

ここで筆者が少し疑問だったのは「JITコンパイル時にスタックマップが決定するのか?」という点でした。ですがよくよく考えてみれば、Javaのニーモニックの型情報から参照型の値はわかりますし、マシン語に変換するコンパイラは自前で持っており、スタックやレジスタの使用方法も完全に自分でコントロールできるので、JITコンパイル時に決定できても不思議ではありません。

13.2 ハンドルエリアとハンドルマーク

これまではJVMスタックに対する正確なGCのための工夫を見てきました。ここからはネイティブな(C++の)コールスタックに対する工夫を見ていきましょう。

HotspotVMはハンドルエリアハンドルマークを使ってコールスタック内のオブジェクトへのポインタを管理しています。このやり方はV8のものにとてもよく似ています。V8はHotspotVMを参考にして作られていますので、正確にはV8がHotspotVMのやり方を真似したということになります。

リスト13.11はハンドラのみを生成するサンプルコードです。

リスト13.11: ハンドラの生成

 1: void make_handles(oop obj1, oop obj2) {
 2:      Handle h1(obj1);  // ハンドラ1生成
 3:      Handle h2(obj2);  // ハンドラ2生成
 4: }

HotspotVMのハンドラはスレッドごとにある「ハンドルエリア」に確保されます。そのため、リスト13.11で生成されたハンドラは図13.7のように確保されます。

make_handles()実行イメージ

図13.7: make_handles()実行イメージ

このままだと、ハンドラが確保されたままになってしまうので、HotspotVMにはもう1つ「ハンドルマーク」というハンドルスコープとほぼ同じ機能があります。

リスト13.12はリスト13.11にハンドルマークを追加したサンプルコードです。

リスト13.12: ハンドラの生成:ハンドルマーク有り

 1: void make_handles(oop obj1, oop obj2) {
 2:      HandleMark hm;
 3:      Handle h1(obj1);
 4:      Handle h2(obj2);
 5: }

2行目に登場するHandleMarkクラスは、コンストラクタでハンドルアリーナの先頭をマーク(記録)します。そして、HandleMarkクラスのデストラクタでは、マークしておいた位置にハンドルアリーナの先頭を移動させます。

図13.8はリスト13.12の実行イメージです。

make_handles()実行イメージ:ハンドルマーク有り

図13.8: make_handles()実行イメージ:ハンドルマーク有り

ただし、HotspotVMは多くの処理をJava言語で実装するというポリシーがありますので、上記の機能を使う機会はあまりありません。



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

Webサイトのトップページ

(C) 2011-2012 Narihiro Nakamura