RSet和卡表
試想一下，當(dāng)在ygc時(shí)，我們需要掃描整個(gè)新生代。當(dāng)新生代的對象被老年代引用，則此對象就不能回收。那么怎么判斷這點(diǎn)呢，總不能掃描老年代吧。所以這里需要使用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)：RSet和卡表。
卡表：一種points-out結(jié)構(gòu)，每個(gè)card記載有沒有引用別的heap分區(qū)，它是全局表，對于一些熱點(diǎn)card，會放入Hot card cache，它也是全局表；
RSet：一種points-in結(jié)構(gòu)，在卡表基礎(chǔ)上實(shí)現(xiàn)，每個(gè)Heap一個(gè)，用來記錄別的Heap指向自己的指針，并標(biāo)記這些指針在卡表哪些范圍內(nèi)。
image.png
在程序運(yùn)行中，如果對象的引用發(fā)生變化，就必須更新RSet。而point in結(jié)構(gòu)有個(gè)缺點(diǎn)就是，對象被引用的次數(shù)不確定。為了提高效率，G1使用了動(dòng)態(tài)化的存儲方式，主要有以下三種粒度：
- 稀疏PRT（Per region Table）：hash表方式存儲
- 細(xì)粒度PRT：PRT指針數(shù)組
- 粗粒度：位圖，記錄引用者對象對應(yīng)的分區(qū)
具體我們看下RSet如何管理引用的代碼
// 添加引用者對象對應(yīng)的卡表地址到RSet中
void OtherRegionsTable::add_reference(OopOrNarrowOopStar from, int tid) {
uint cur_hrm_ind = hr()->hrm_index();
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr("ORT::add_reference_work(" PTR_FORMAT "->" PTR_FORMAT ").",
from,
UseCompressedOops
? (void *)oopDesc::load_decode_heap_oop((narrowOop*)from)
: (void *)oopDesc::load_decode_heap_oop((oop*)from));
}
int from_card = (int)(uintptr_t(from) >> CardTableModRefBS::card_shift);
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr("Table for [" PTR_FORMAT "...): card %d (cache = "INT32_FORMAT")",
hr()->bottom(), from_card,
FromCardCache::at((uint)tid, cur_hrm_ind));
}
// 提高處理效率，使用卡表緩存，緩存中有表示已處理
if (FromCardCache::contains_or_replace((uint)tid, cur_hrm_ind, from_card)) {
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr(" from-card cache hit.");
}
assert(contains_reference(from), "We just added it!");
return;
}
// Note that this may be a continued H region.
HeapRegion* from_hr = _g1h->heap_region_containing_raw(from);
RegionIdx_t from_hrm_ind = (RegionIdx_t) from_hr->hrm_index();
// If the region is already coarsened, return.
//如果Rset中已經(jīng)是粗粒度關(guān)系，也就是說RSet中記錄是對應(yīng)的分區(qū)，直接返回
if (_coarse_map.at(from_hrm_ind)) {
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr(" coarse map hit.");
}
assert(contains_reference(from), "We just added it!");
return;
}
// Otherwise find a per-region table to add it to.
// 添加RPT引用關(guān)系到RSet中
size_t ind = from_hrm_ind & _mod_max_fine_entries_mask;
PerRegionTable* prt = find_region_table(ind, from_hr);
if (prt == NULL) {
//加鎖，多線程訪問
MutexLockerEx x(_m, Mutex::_no_safepoint_check_flag);
// Confirm that it's really not there...
prt = find_region_table(ind, from_hr);
if (prt == NULL) {
//使用稀疏矩陣存儲
uintptr_t from_hr_bot_card_index =
uintptr_t(from_hr->bottom())
>> CardTableModRefBS::card_shift;
CardIdx_t card_index = from_card - from_hr_bot_card_index;
assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
"Must be in range.");
if (G1HRRSUseSparseTable &&
_sparse_table.add_card(from_hrm_ind, card_index)) {
if (G1RecordHRRSOops) {
HeapRegionRemSet::record(hr(), from);
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print(" Added card " PTR_FORMAT " to region "
"[" PTR_FORMAT "...) for ref " PTR_FORMAT ".\n",
align_size_down(uintptr_t(from),
CardTableModRefBS::card_size),
hr()->bottom(), from);
}
}
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr(" added card to sparse table.");
}
assert(contains_reference_locked(from), "We just added it!");
return;
} else {
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr(" [tid %d] sparse table entry "
"overflow(f: %d, t: %u)",
tid, from_hrm_ind, cur_hrm_ind);
}
}
// 細(xì)粒度卡表滿了，刪除PRT并放入粗粒度卡表
if (_n_fine_entries == _max_fine_entries) {
prt = delete_region_table();
// There is no need to clear the links to the 'all' list here:
// prt will be reused immediately, i.e. remain in the 'all' list.
prt->init(from_hr, false /* clear_links_to_all_list */);
} else {
//稀疏矩陣滿了，需要再分配一個(gè)細(xì)粒度
prt = PerRegionTable::alloc(from_hr);
link_to_all(prt);
}
//把稀疏矩陣的數(shù)據(jù)遷移到細(xì)粒度卡表中，成功后刪除稀疏矩陣
PerRegionTable* first_prt = _fine_grain_regions[ind];
prt->set_collision_list_next(first_prt);
_fine_grain_regions[ind] = prt;
_n_fine_entries++;
if (G1HRRSUseSparseTable) {
// Transfer from sparse to fine-grain.
SparsePRTEntry *sprt_entry = _sparse_table.get_entry(from_hrm_ind);
assert(sprt_entry != NULL, "There should have been an entry");
for (int i = 0; i < SparsePRTEntry::cards_num(); i++) {
CardIdx_t c = sprt_entry->card(i);
if (c != SparsePRTEntry::NullEntry) {
prt->add_card(c);
}
}
// Now we can delete the sparse entry.
bool res = _sparse_table.delete_entry(from_hrm_ind);
assert(res, "It should have been there.");
}
}
assert(prt != NULL && prt->hr() == from_hr, "consequence");
}
//添加引用
prt->add_reference(from);
if (G1RecordHRRSOops) {
HeapRegionRemSet::record(hr(), from);
if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print("Added card " PTR_FORMAT " to region "
"[" PTR_FORMAT "...) for ref " PTR_FORMAT ".\n",
align_size_down(uintptr_t(from),
CardTableModRefBS::card_size),
hr()->bottom(), from);
}
}
assert(contains_reference(from), "We just added it!");
}
Refine線程
Refine線程是G1新引入的并發(fā)線程池，主要有2個(gè)功能：
- 用于處理新生代分區(qū)的抽樣：用來設(shè)置YGC的分區(qū)數(shù)目，以便滿足垃圾回收的預(yù)測停頓時(shí)間，線程池中的最后一個(gè)線程就是抽樣線程。
- 管理RSet：G1會將所有的引用關(guān)系放到隊(duì)列DCQ中，然后使用線程來消費(fèi)隊(duì)列。除了Refine線程外，有些情況GC或Mutator線程也會更新RSet。DCQ通過DCQS（Dirty card queue set）來管理。
這里我們主要看如何管理RSet。DCQS是全局對象，用來存放DCQ。每個(gè)Mutator線程在初始化的時(shí)候都關(guān)聯(lián)DCQS，每個(gè)Mutator有私有的隊(duì)列，當(dāng)私有隊(duì)列滿的時(shí)候，會將存放的引用關(guān)系放入DCQ中。
當(dāng)DCQS滿的時(shí)候，就不繼續(xù)添加了，說明Refine線程處理不過來了。這個(gè)時(shí)候Mutator線程會暫停其他代碼處理，轉(zhuǎn)去更新RSet。
Refine線程工作原理
Refine線程處理RSet關(guān)系，但如果引用關(guān)系變更少，Refine線程就浪費(fèi)了，所以需要?jiǎng)討B(tài)激活和凍結(jié)線程。JVM通過wait和notify機(jī)制來實(shí)現(xiàn)。
設(shè)計(jì)思想是：當(dāng)前一個(gè)Refine線程太忙，激活后一個(gè)。后一個(gè)線程發(fā)現(xiàn)自己太空閑，則凍結(jié)自己。那么第一個(gè)Refine線程怎么激活呢？答案是Java線程（Mutator），因?yàn)镴ava線程會將引用關(guān)系放入DCQ，當(dāng)發(fā)現(xiàn)第一個(gè)Refine線程還沒激活，則發(fā)送notify激活。
我們先看下ConcurrentG1RefineThread線程的run方法
void ConcurrentG1RefineThread::run() {
//初始化線程信息
initialize_in_thread();
wait_for_universe_init();
//最后一個(gè)線程用于處理YHR的數(shù)目
if (_worker_id >= cg1r()->worker_thread_num()) {
run_young_rs_sampling();
terminate();
return;
}
_vtime_start = os::elapsedVTime();
while (!_should_terminate) {
DirtyCardQueueSet& dcqs = JavaThread::dirty_card_queue_set();
// 前一線程通知后一個(gè)線程實(shí)現(xiàn)
wait_for_completed_buffers();
if (_should_terminate) {
break;
}
{
SuspendibleThreadSetJoiner sts;
do {
int curr_buffer_num = (int)dcqs.completed_buffers_num();
// If the number of the buffers falls down into the yellow zone,
// that means that the transition period after the evacuation pause has ended.
if (dcqs.completed_queue_padding() > 0 && curr_buffer_num <= cg1r()->yellow_zone()) {
dcqs.set_completed_queue_padding(0);
}
if (_worker_id > 0 && curr_buffer_num <= _deactivation_threshold) {
// 根據(jù)負(fù)載判斷是否需要停止當(dāng)前的Refine線程
deactivate();
break;
}
// 判斷是否需要通知新的refine線程
if (_next != NULL && !_next->is_active() && curr_buffer_num > _next->_threshold) {
_next->activate();
}
} while (dcqs.apply_closure_to_completed_buffer(_refine_closure, _worker_id + _worker_id_offset, cg1r()->green_zone()));
// We can exit the loop above while being active if there was a yield request.
// 有yield請求時(shí)退出循環(huán)，目的是進(jìn)入安全點(diǎn)
if (is_active()) {
deactivate();
}
}
if (os::supports_vtime()) {
_vtime_accum = (os::elapsedVTime() - _vtime_start);
} else {
_vtime_accum = 0.0;
}
}
terminate();
}
最終處理queue邏輯
bool G1RemSet::refine_card(jbyte* card_ptr, uint worker_i,
bool check_for_refs_into_cset) {
// 卡表指針對應(yīng)的值不是dirty，說明已處理過.
if (*card_ptr != CardTableModRefBS::dirty_card_val()) {
return false;
}
// 找到卡表指針對應(yīng)的分區(qū).
HeapWord* start = _ct_bs->addr_for(card_ptr);
// And find the region containing it.
HeapRegion* r = _g1->heap_region_containing(start);
// 引用者是新生代或在CSet中則不需要更新，因?yàn)橐谜咭惨粧呙? if (r->is_young()) {
return false;
}
if (r->in_collection_set()) {
return false;
}
// 如果在hot card中，則待后續(xù)批量處理
G1HotCardCache* hot_card_cache = _cg1r->hot_card_cache();
if (hot_card_cache->use_cache()) {
card_ptr = hot_card_cache->insert(card_ptr);
if (card_ptr == NULL) {
// There was no eviction. Nothing to do.
return false;
}
start = _ct_bs->addr_for(card_ptr);
r = _g1->heap_region_containing(start);
}
.
HeapWord* end = start + CardTableModRefBS::card_size_in_words;
MemRegion dirtyRegion(start, end);
//定義處理的對象
OopsInHeapRegionClosure* oops_in_heap_closure = NULL;
if (check_for_refs_into_cset) {
oops_in_heap_closure = _cset_rs_update_cl[worker_i];
}
G1UpdateRSOrPushRefOopClosure update_rs_oop_cl(_g1,
_g1->g1_rem_set(),
oops_in_heap_closure,
check_for_refs_into_cset,
worker_i);
update_rs_oop_cl.set_from(r);
G1TriggerClosure trigger_cl;
FilterIntoCSClosure into_cs_cl(NULL, _g1, &trigger_cl);
G1InvokeIfNotTriggeredClosure invoke_cl(&trigger_cl, &into_cs_cl);
G1Mux2Closure mux(&invoke_cl, &update_rs_oop_cl);
FilterOutOfRegionClosure filter_then_update_rs_oop_cl(r,
(check_for_refs_into_cset ?
(OopClosure*)&mux :
(OopClosure*)&update_rs_oop_cl));
// 具體的處理
HeapWord* stop_point =
r->oops_on_card_seq_iterate_careful(dirtyRegion,
&filter_then_update_rs_oop_cl,
filter_young,
card_ptr);
// 如果處理中出現(xiàn)問題，將該引用放入公共的DCQ，等待后續(xù)處理
if (*card_ptr != CardTableModRefBS::dirty_card_val()) {
*card_ptr = CardTableModRefBS::dirty_card_val();
MutexLockerEx x(Shared_DirtyCardQ_lock,
Mutex::_no_safepoint_check_flag);
DirtyCardQueue* sdcq =
JavaThread::dirty_card_queue_set().shared_dirty_card_queue();
sdcq->enqueue(card_ptr);
}
} else {
_conc_refine_cards++;
}
// This gets set to true if the card being refined has
// references that point into the collection set.
bool has_refs_into_cset = trigger_cl.triggered();
// We should only be detecting that the card contains references
// that point into the collection set if the current thread is
// a GC worker thread.
assert(!has_refs_into_cset || SafepointSynchronize::is_at_safepoint(),
"invalid result at non safepoint");
return has_refs_into_cset;
}
以上找到的是512B的內(nèi)存區(qū)域，最終要找到此內(nèi)存區(qū)域的第一個(gè)對象，作為引用者處理。
HeapWord*
HeapRegion::
oops_on_card_seq_iterate_careful(MemRegion mr,
FilterOutOfRegionClosure* cl,
bool filter_young,
jbyte* card_ptr) {
G1CollectedHeap* g1h = G1CollectedHeap::heap();
if (g1h->is_gc_active()) {
mr = mr.intersection(used_region_at_save_marks());
} else {
mr = mr.intersection(used_region());
}
if (mr.is_empty()) return NULL;
if (is_young() && filter_young) {
return NULL;
}
//把卡表改為clean狀態(tài)，表示在處理
if (card_ptr != NULL) {
*card_ptr = CardTableModRefBS::clean_card_val();
OrderAccess::storeload();
}
// Cache the boundaries of the memory region in some const locals
HeapWord* const start = mr.start();
HeapWord* const end = mr.end();
HeapWord* cur = block_start(start);
assert(cur <= start, "Postcondition");
oop obj;
//跳過不在處理區(qū)域的對象
HeapWord* next = cur;
while (next <= start) {
cur = next;
obj = oop(cur);
if (obj->klass_or_null() == NULL) {
// Ran into an unparseable point.
return cur;
}
// Otherwise...
next = cur + block_size(cur);
}
if (!g1h->is_obj_dead(obj)) {
obj->oop_iterate(cl, mr);
}
while (cur < end) {
obj = oop(cur);
if (obj->klass_or_null() == NULL) {
// Ran into an unparseable point.
return cur;
};
// Otherwise:
next = cur + block_size(cur);
if (!g1h->is_obj_dead(obj)) {
//遍歷對象
if (next < end || !obj->is_objArray()) {
obj->oop_iterate(cl);
} else {
obj->oop_iterate(cl, mr);
}
}
cur = next;
}
return NULL;
}
遍歷到的對象會使用G1UpdateRSOrPushRefOopClosure來更新RSet
inline void G1UpdateRSOrPushRefOopClosure::do_oop_nv(T* p) {
oop obj = oopDesc::load_decode_heap_oop(p);
if (obj == NULL) {
return;
}
HeapRegion* to = _g1->heap_region_containing(obj);
//只處理不同分區(qū)的
if (_from == to) {
return;
}
if (_record_refs_into_cset && to->in_collection_set()) {
//Evac會進(jìn)入這里，只需復(fù)制對象到棧中繼續(xù)處理
if (!self_forwarded(obj)) {
//對于成功轉(zhuǎn)移的對象放入G1ParScanThreadState隊(duì)列處理
_push_ref_cl->do_oop(p);
}
} else {
// 更新RSet
to->rem_set()->add_reference(p, _worker_i);
}
}
Refinement Zone
據(jù)資料顯示，RSet在很多情況要浪費(fèi)1%-20%的內(nèi)存空間，是G1調(diào)優(yōu)的重要部分之一。當(dāng)DCQS過慢時(shí)，Mutator線程也會幫忙處理，會影響應(yīng)用處理的性能。通常我們可以在不同的負(fù)載下啟用不同的線程進(jìn)行DCQ處理。這個(gè)工作負(fù)載通過Refinement Zone控制，G1將Queue Set分為四個(gè)區(qū)：白、綠、黃、紅。
白區(qū)[0,green)：GC線程處理
綠[green,yellow): 根據(jù)queue set啟動(dòng)不同數(shù)量的refine
黃[yellow，red)：refine線程全部啟動(dòng)
紅[red,+oo): 除refine啟動(dòng)處理，mutator線程也處理
三個(gè)參數(shù)分別對應(yīng)：G1ConcRefinementGreenZone、G1ConcRefinementYellowZone、G1ConcRefinementRedZone （默認(rèn)為0，G1自動(dòng)推導(dǎo)）
RSet寫屏障
寫屏障：在進(jìn)行特定內(nèi)存值改變時(shí)額外進(jìn)行一些操作，如在G1中將老年代對象的引用改為新生代對象就會觸發(fā)寫屏障：插入額外的代碼，將引用關(guān)系放到DCQ中，等待線程更新到RSet中。
