G1 write barrier code generation in OpenJDK/HotSpot
OpenJDK/HotSpot での G1 Write Barrier の実装について確認してみました。
世代別 GC の Young に対する GC で root set の他、 Old から Young への参照も検査する必要があるが、すべてやると時間がかかるので、変更があったところを覚えておくため putfield の時にそれを記録しておく。これを write barrier というが、card table や remembered set など実装はいろいろ。すべてを記録すれば簡単が、それなりにリソースも必要になるため、512 bytes の範囲毎に変更があったか否かだけを記録しておき、必要な時はその範囲を詳しく調べるといった card marking にすると putfield 時のオーバーヘッドは小さくなる。
Old が単一の連続領域だとこれでもよいが、G1 の様に連続領域が比較的小さい場合には話が異なってくる。G1 region ではそれに入ってくる参照を覚えておく様にしているので、write barrier では region から関連するデータ構造をたどって記録するので、連続領域の Old に対する card marking とは処理が異なってくる。
putfield 自身はインタプリタでも compiled code でも行われる処理だが、それを担当する関数があって呼び出されているという訳ではない。シンプルな造りではそれでもいいが、それなりのオーバーヘッドが伴うので、速くするための工夫がある。
Interpreter
HotSpot のインタープリタには２種類あり、一つは cpp で書かれた cpp interpreter (CC_INTERP の ifdef で条件分けしてある) で、移植の初期の段階で使われる。もう一つは template interpreter で、CPU アーキテクチャごとに存在する (share/vm/interpreter/template*, cpu/*/vm/templateInter*)。template interpreter は起動時に動的に macro assembler で生成される。
share/vm/interpreter/templateTable.cpp:
void TemplateTable::initialize() { // : def(Bytecodes::_putfield , ubcp|____|clvm|____, vtos, vtos, putfield , f2_byte ); //: void TemplateTable::def(Bytecodes::Code code, int flags, TosState in, TosState out, void (*gen)(), char filler) { assert(filler == ' ', "just checkin'"); def(code, flags, in, out, (Template::generator)gen, 0); }
五番目の putfield が実際にコードを生成する関数の名前で、x86_64 での実体は次のもの。
cpu/x86/vm/templateTable_x86_64.cpp:
#define __ _masm-> // .. void TemplateTable::putfield(int byte_no) { putfield_or_static(byte_no, false); } void TemplateTable::putfield_or_static(int byte_no, bool is_static) { transition(vtos, vtos); // : Label notVolatile, Done; __ movl(rdx, flags); __ shrl(rdx, ConstantPoolCacheEntry::is_volatile_shift); __ andl(rdx, 0x1); // : // atos { __ pop(atos); if (!is_static) pop_and_check_object(obj); // Store into the field do_oop_store(_masm, field, rax, _bs->kind(), false); if (!is_static) { patch_bytecode(Bytecodes::_fast_aputfield, bc, rbx, true, byte_no); } __ jmp(Done); } // ..
putfield_or_static() を見ると movl や shrl など x64 のニーモニックが見て取れる。 write barrier のコード生成は putfield_or_static() から呼び出される do_oop_store() で行われている。
余談だが、atos, vtos というシンボルがある。template interpreter を構成する個々のバイトコードに対する命令列と付随する情報を Codelet と呼ぶが、これらは入力と出力の Top of State (enum TopState)というものを持つ。これはスタックのトップにあるデータのタイプを表しており、atos なら object (への参照) で、itos なら int といった具合。ある codelet の out の tos が次の codelet の in の tos と合致していると stack にその値をセーブ(push)せずに、レジスタ渡しができる仕組み。できることなら４つぐらい register に持たせるともっと速くなりそうだが、top の状態を管理するだけでも結構なコード量になっているので難しいだろう。データ型、サイズも考えると面倒だろう。
do_oop_store() に戻る。
static void do_oop_store(InterpreterMacroAssembler* _masm, Address obj, Register val, BarrierSet::Name barrier, bool precise) { assert(val == noreg || val == rax, "parameter is just for looks"); switch (barrier) { #if INCLUDE_ALL_GCS case BarrierSet::G1SATBCT: case BarrierSet::G1SATBCTLogging: { // flatten object address if needed if (obj.index() == noreg && obj.disp() == 0) { if (obj.base() != rdx) { __ movq(rdx, obj.base()); } } else { __ leaq(rdx, obj); } __ g1_write_barrier_pre(rdx /* obj */, rbx /* pre_val */, r15_thread /* thread */, r8 /* tmp */, val != noreg /* tosca_live */, false /* expand_call */); //.. case BarrierSet::CardTableModRef: case BarrierSet::CardTableExtension: { if (val == noreg) { __ store_heap_oop_null(obj); } else { __ store_heap_oop(obj, val); // flatten object address if needed if (!precise || (obj.index() == noreg && obj.disp() == 0)) { __ store_check(obj.base()); } else { __ leaq(rdx, obj); __ store_check(rdx); } } } break; case BarrierSet::ModRef: case BarrierSet::Other:
さらに下請け関数があるが、BarrierSet::Name barrier の引数で渡される (write) barrier のタイプによって処理が分けれている。この関数が VM 起動時に呼ばれる前に、heap のタイプ (Serial, Parallel, ParallelOld, CMS, G1) と barrier set のタイプは確定している。この型により、生成される write barrier 命令が異なってくる。template interpreter を新しいアーキテクチャに移植する人はこれも考慮しないといけないということだ。(ひょっとすると CC_INTERP 側の CPP で書かれたものを利用できるかもしれないが未確認)
Server Compiler
プログラムの実行が進み、しきい値を超えたコードは HotSpot Compile される。C2 Server Compiler は share/vm/opto 以下にある。メソッドのインライン展開の範囲を決めたりした後、コンパイル範囲のバイトコードが順次パースされる。Parse::do_one_bytecode() は bytecode の番号を使った大きな switch case 文を持つ。
putfield の場合は do_putfield() が呼ばれる。
share/vm/opto/parse2.cpp:
void Parse::do_one_bytecode() { //.. switch (bc()) { case Bytecodes::_nop: // do nothing break; case Bytecodes::_lconst_0: push_pair(longcon(0)); break; // .. case Bytecodes::_putfield: do_putfield(); break;
do_putfiled() は do_field_access() を呼び出す。
share/vm/opto/parse.hpp:
void do_putfield () { do_field_access(false, true); } void do_field_access(bool is_get, bool is_field);
do_field_access() は処理 (get, put) に応じて do_get_xxx, do_put_xxx を呼び出す。
share/vm/opto/parse3.cpp:
void Parse::do_field_access(bool is_get, bool is_field) { //... if (is_get) { (void) pop(); // pop receiver before getting do_get_xxx(obj, field, is_field); } else { do_put_xxx(obj, field, is_field); (void) pop(); // pop receiver after putting } //... void Parse::do_put_xxx(Node* obj, ciField* field, bool is_field) { //.. Node* store; if (bt == T_OBJECT) { const TypeOopPtr* field_type; if (!field->type()->is_loaded()) { field_type = TypeInstPtr::BOTTOM; } else { field_type = TypeOopPtr::make_from_klass(field->type()->as_klass()); } store = store_oop_to_object( control(), obj, adr, adr_type, val, field_type, bt); } else { store = store_to_memory( control(), adr, val, bt, adr_type, is_vol ); }
do_put_xxx は store_oop_to_object() で実際のストアの処理の中間コード(IR) を生成する。これは store_oop() を呼び出す。
share/vm/opto/graphKit.hpp:
Node* store_oop_to_object(Node* ctl,
Node* obj, // containing obj
Node* adr, // actual adress to store val at
const TypePtr* adr_type,
Node* val,
const TypeOopPtr* val_type,
BasicType bt) {
return store_oop(ctl, obj, adr, adr_type, val, val_type, bt, false);
}
store_oop() は実際の oop (Ordinary Object Pointer, object/array などへの参照(ポインタ)) をメモリに保存する中間コードを store_to_memory() で生成するが、それは pre_barrier と post_barrier で挟まれている。
pre_barrier, post_barrier は Barrier Set の型により switch case で処理を分けている。
share/vm/opto/graphKit.cpp:
Node* GraphKit::store_oop(Node* ctl,
Node* obj,
Node* adr,
const TypePtr* adr_type,
Node* val,
const TypeOopPtr* val_type,
BasicType bt,
bool use_precise) {
// Transformation of a value which could be NULL pointer (CastPP #NULL)
// could be delayed during Parse (for example, in adjust_map_after_if()).
// Execute transformation here to avoid barrier generation in such case.
if (_gvn.type(val) == TypePtr::NULL_PTR)
val = _gvn.makecon(TypePtr::NULL_PTR);
set_control(ctl);
if (stopped()) return top(); // Dead path ?
assert(bt == T_OBJECT, "sanity");
assert(val != NULL, "not dead path");
uint adr_idx = C->get_alias_index(adr_type);
assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory" );
pre_barrier(true /* do_load */,
control(), obj, adr, adr_idx, val, val_type,
NULL /* pre_val */,
bt);
Node* store = store_to_memory(control(), adr, val, bt, adr_idx);
post_barrier(control(), store, obj, adr, adr_idx, val, bt, use_precise);
return store;
}
void GraphKit::pre_barrier(bool do_load,
Node* ctl,
Node* obj,
Node* adr,
uint adr_idx,
Node* val,
const TypeOopPtr* val_type,
Node* pre_val,
BasicType bt) {
BarrierSet* bs = Universe::heap()->barrier_set();
set_control(ctl);
switch (bs->kind()) {
case BarrierSet::G1SATBCT:
case BarrierSet::G1SATBCTLogging:
g1_write_barrier_pre(do_load, obj, adr, adr_idx, val, val_type, pre_val, bt);
break;
case BarrierSet::CardTableModRef:
case BarrierSet::CardTableExtension:
case BarrierSet::ModRef:
break;
case BarrierSet::Other:
default :
ShouldNotReachHere();
}
}
g1_write_barrier_pre, post は G1 の write barrier のデータ構造 SATB を参照、変更する中間コードを生成する。C2 の中間コードは Ideal と呼ばれたりするが SSA ベースで、制御構造をデータフローに変換した、明示的な block の無い高度な最適化を狙ったもの。パース時にも正規化、最適化し、さらにグローバルに GVN, Escape Analysis, immediate dominator を利用した loop 変換などを施した後、低レベルの IR に変換して、さらに最適化を加える。いろいろな変換が伴うので、この write barrier の関数が生成した node, edge の構成と実際のコードは並びが違うかもしれない(意味的にはあっていないといけないが)。
share/vm/opto/graphKit.cpp:
// G1 pre/post barriers void GraphKit::g1_write_barrier_pre(bool do_load, Node* obj, Node* adr, uint alias_idx, Node* val, const TypeOopPtr* val_type, Node* pre_val, BasicType bt) { //.. IdealKit ideal(this, true); Node* tls = __ thread(); // ThreadLocalStorage Node* no_ctrl = NULL; Node* no_base = __ top(); Node* zero = __ ConI(0); float likely = PROB_LIKELY(0.999); float unlikely = PROB_UNLIKELY(0.999); BasicType active_type = in_bytes(PtrQueue::byte_width_of_active()) == 4 ? T_INT : T_BYTE; assert(in_bytes(PtrQueue::byte_width_of_active()) == 4 || in_bytes(PtrQueue::byte_width_of_active()) == 1, "flag width"); // Offsets into the thread const int marking_offset = in_bytes(JavaThread::satb_mark_queue_offset() + // 648 PtrQueue::byte_offset_of_active()); const int index_offset = in_bytes(JavaThread::satb_mark_queue_offset() + // 656 PtrQueue::byte_offset_of_index()); const int buffer_offset = in_bytes(JavaThread::satb_mark_queue_offset() + // 652 PtrQueue::byte_offset_of_buf()); // Now the actual pointers into the thread Node* marking_adr = __ AddP(no_base, tls, __ ConX(marking_offset)); Node* buffer_adr = __ AddP(no_base, tls, __ ConX(buffer_offset)); Node* index_adr = __ AddP(no_base, tls, __ ConX(index_offset)); // Now some of the values Node* marking = __ load(__ ctrl(), marking_adr, TypeInt::INT, active_type, Compile::AliasIdxRaw); // if (!marking) __ if_then(marking, BoolTest::ne, zero); { Node* index = __ load(__ ctrl(), index_adr, TypeInt::INT, T_INT, Compile::AliasIdxRaw); if (do_load) { // load original value // alias_idx correct?? pre_val = __ load(no_ctrl, adr, val_type, bt, alias_idx); } // if (pre_val != NULL) __ if_then(pre_val, BoolTest::ne, null()); { Node* buffer = __ load(__ ctrl(), buffer_adr, TypeRawPtr::NOTNULL, T_ADDRESS, Compile::AliasIdxRaw); // is the queue for this thread full? __ if_then(index, BoolTest::ne, zero, likely); { // decrement the index Node* next_index = __ SubI(index, __ ConI(sizeof(intptr_t))); Node* next_indexX = next_index; //..
ここまでくると、オーバーヘッドヘッドの見積もりも大変だ。
