卡表(CardTable）

由于新生代的垃圾收集通常很频繁，如果老年代对象引用了新生代的对象，那么，需要跟踪从老年代到新生代的所有引用，从而避免每次YGC时扫描整个老年代，减少开销。

HotSpot 使用（Card Marking）技术来解决老年代到新生代的引用问题。使用卡表（Card Table）和写屏障（Write Barrier）来进行标记并加快对GC Roots的扫描。

卡表的就是典型的空间换时间的实现。基于卡表（Card Table）的设计，将堆空间划分为一系列2次幂大小的卡页（Card Page）。卡页（Card Page）大小为512字节，卡表（Card Table）实现为一个简单的字节数组。

假设老年代内存地址从0开始。可以理解为cardTable[0]代表内存地址0-511字节的内存的标记，cardTable[1]代表内存地址512-1023字节的内存的标记。当对一个对象引用进行写操作时（对象引用改变），写屏障逻辑将会标记对象所在的卡页为dirty。这样就标记了跨代引用的内存块。

但是同样也引入了些许进行引用赋值的时候增加了写屏障的消耗，还有针对对象赋值在并发高的场景内，也会由于缓冲行的虚共享导致无效化写入。所以在进行写屏障写入先进行下该卡是否被标记为脏卡。如果已经为脏卡，则进行操作。

CMS在并发标记阶段就使用了卡表来进行跨代引用的遍历处理，在G1中还引入了RememberSet(RSet)在回收过程中，快速的找到活跃对象，同时避免整堆扫描。

RSet

Remembered Set是一种抽象概念，而card table可以说是remembered set的一种实现方式。

Remembered Set是在实现部分垃圾收集（partial GC）时用于记录从非收集部分指向收集部分的指针的集合的抽象数据结构。

分代式GC是一种部分垃圾收集的实现方式。当分两代时，通常把这两代叫做Eden和old；通常能单独收集的只是Eden。此时Remembered set记录的就是从old指向Eden的跨代指针。

Regional collector也是一种部分垃圾收集的实现方式。此时Remembered set就要记录跨region的指针。在每个region有一份。这个RSet记录的是从别的region指向该region的card。RSet记录了其他Region中的对象引用本Region中对象的关系，属于points-into结构（谁引用了我的对象）。而Card Table则是一种points-out（我引用了谁的对象）的结构，每个Card 覆盖一定范围的Heap（一般为512Bytes）。G1的RSet是在Card Table的基础上实现的：每个Region会记录下别的Region有指向自己的指针，并标记这些指针分别在哪些Card的范围内。 这个RSet其实是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index。

举例说下.当Region A的RSet里有一项的key是region B，value里有index为577的Card（577>>>9得到Card1），它的意思就是region B的一个card里有引用指向region A。所以对region A来说，该RSet记录的是points-into的关系；而card table仍然记录了points-out的关系.

我们可以知道 分区中对象的引用无非就是同分区同代引用，要么就是跨分区跨代引用。

同分区新生代不需要RSet，这个点很好理解，新生代到老年代则无需使用RSet记录，应为G1的YoungGC是不涉及到老年代分区的梳理的无需关注，当发生MixedGC，从新生代也可以找到老年代 所以无需记录，发生FullGC也无需记录，应为整个堆都会处理，相反老年代到新生代需要使用RSet记录，记录老年代到新生代是为了YGC的时候，只需要选定young Region的RSet（记录了old->young的跨代引用）作为根集，这样就避免了扫描old Region，老年代到老年代需要RSet记录则是由于发生MixedGC不是全部的老年代的GC而是部分，所以需要记录RSet。

总结：RSet去记录分区引用关系，卡表去记录对应区域内存的对象使用情况

G1使用RSet来使用新的数据结构PRTPre region Table来实现的,参见源码heapRememberSet的PerRegionTable 定义。

class PerRegionTable: public CHeapObj {
friend class OtherRegionsTable;
friend class HeapRegionRemSetIterator;

//分区索引
HeapRegion* _hr;
//卡表位图
BitMap _bm;
//已经使用的容量
jint _occupied;

// next pointer for free/allocated 'all' list
PerRegionTable* _next;

// prev pointer for the allocated 'all' list
PerRegionTable* _prev;

// next pointer in collision list
PerRegionTable * _collision_list_next;

// Global free list of PRTs
static PerRegionTable* _free_list;

每个分区都会有一个RSet，也就是有一个PerRegionTable,一个对象被引用的频率有可能是很平凡也有可能是很少的引用。所以G1设立了针对三种不同的查询策略对应的数据结构

2. 稀疏PRT: 使用Hash表来实现

3. 细粒度PRT:通过PRT指针数组来实现

4. 粗粒度PRT:使用位图_coarse_map来表示，key存放的是分区的起始地址。如果存在，代表这块分区被别的分区引用。

ok 当发生应用更改，如发生下列引用赋值时HR1.Obj1.Field=HR2.Obj2,会触发更新Rset。代码如下参见：heapRememberSet#add_reference

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.
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.
size_t ind = from_hrm_ind & _mod_max_fine_entries_mask;
PerRegionTable* prt = find_region_table(ind, from_hr);
if (prt == NULL) {
// 这里加锁为了在并发情况保证只有一个线程来更新RSet
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);
}
}

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 {
prt = PerRegionTable::alloc(from_hr);
link_to_all(prt);
}

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");
}
// Note that we can't assert "prt->hr() == from_hr", because of the
// possibility of concurrent reuse. But see head comment of
// OtherRegionsTable for why this is OK.
assert(prt != NULL, "Inv");

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!");
}

首先会判断当前分区FromCardCache中是否存在引用了，如果已经存在，则返回无需更新Rset，直接判断粗粒度的PRT中是否存在被引用的分区，如果存在，也直接返回。

反之就是查询稀疏PRT中是否存在被引用分区的卡表索引，如果存在则返回，不存在就添加进去，同时做了溢出判断，当超出最大的细粒度PRT表示的范围，把细粒度的PRT清除，转换分区的其实地址添加到_coarse_map中。，没有超过最大值，就继续申请空间插入。

需要观察RememberSet的在jvm中工作情况。可以打开对应的上面源码中的参数

G1TraceHeapRegionRememberedSet 来观察对应的日志。

PRT添加完毕之后，就是真正的添加引用关系了。prt->add_reference(from);

观察add_reference的实现逻辑，不难看出RSet的存储就是分区的起始地址和位图索引。

void add_reference(OopOrNarrowOopStar from) {
add_reference_work(from, /*parallel*/ true);
}
void add_reference_work(OopOrNarrowOopStar from, bool par) {
// Must make this robust in case "from" is not in "_hr", because of
// concurrency.

if (G1TraceHeapRegionRememberedSet) {
gclog_or_tty->print_cr(" PRT::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));
}

HeapRegion* loc_hr = hr();
// If the test below fails, then this table was reused concurrently
// with this operation. This is OK, since the old table was coarsened,
// and adding a bit to the new table is never incorrect.
// If the table used to belong to a continues humongous region and is
// now reused for the corresponding start humongous region, we need to
// make sure that we detect this. Thus, we call is_in_reserved_raw()
// instead of just is_in_reserved() here.
if (loc_hr->is_in_reserved_raw(from)) {
size_t hw_offset = pointer_delta((HeapWord*)from, loc_hr->bottom());
CardIdx_t from_card = (CardIdx_t)
hw_offset >> (CardTableModRefBS::card_shift - LogHeapWordSize);

assert(0 <= from_card && (size_t)from_card < HeapRegion::CardsPerRegion,
"Must be in range.");
add_card_work(from_card, par);
}
}
void add_card_work(CardIdx_t from_card, bool par) {
if (!_bm.at(from_card)) {
if (par) {
if (_bm.par_at_put(from_card, 1)) {
Atomic::inc(&_occupied);
}
} else {
_bm.at_put(from_card, 1);
_occupied++;
}
}
}

那么G1针对Rset启用了单独的Refine线程来进行管理，使用线程来管理，首先肯定是异步处理，那必然会引入第三个存储介质来提升处理能力。这就是Dirty Card Quene Set (DCQS)。

整体的工作流程如下图所示

JVM在初始化的时候会创建全局的DCQS，每个应用线程初始化的时候都会在本地线程空间内部关联初始化1个Dirty Card Quene,默认容量是256(G1UpdateBufferSize)，可以存放256个引用关系，每个应用线程内部的DCQ是无锁操作，但是在往全局DCQS添加时候需要加锁处理，DCQ只有Refine线程来进行处理，但是当Refine处理不过来的时候。应用线程同样也会帮忙处理，但是这样带来的后果就是，应用线程会挂起。这种情况正对应用来说是个不好的状况。这意味着对象的引用更换太频繁，导致Refine线程工作超负荷运转。或者是Refine线程的个数太少设置不合理，所以在调优RSet的时候，打开G1SummarizeRSetSats参数，关注RSet的处理情况。

源代码参见ptrQueue enqueue_known_active 方法的处理逻辑，这里是Mutator线程处理引用变更之后，把变更推入DCQ，当应用线程的buffer不为空的时候，会去判断是否需要应用线程帮助处理DCQS，需要则会暂停应用线程，否则直接重新分配到当前的DCQ，当满了的时候，加锁全局的DCQS，然后将本线程的buffer推入DCQS，

Mutator线程帮忙处理DCQ,源代码参见dirtyCardQueue#mut_process_buffer

bool DirtyCardQueueSet::mut_process_buffer(void** buf) {
...
..
bool b = false;
if (worker_i != UINT_MAX) {
b = DirtyCardQueue::apply_closure_to_buffer(_mut_process_closure, buf, 0,
_sz, true, worker_i);
...
}


bool DirtyCardQueue::apply_closure_to_buffer(CardTableEntryClosure* cl,
void** buf,
size_t index, size_t sz,
bool consume,
uint worker_i) {
if (cl == NULL) return true;
for (size_t i = index; i < sz; i += oopSize) {
int ind = byte_index_to_index((int)i);
jbyte* card_ptr = (jbyte*)buf[ind];
if (card_ptr != NULL) {
// Set the entry to null, so we don't do it again (via the test
// above) if we reconsider this buffer.
if (consume) buf[ind] = NULL;
if (!cl->do_card_ptr(card_ptr, worker_i)) return false;
}
}
return true;
}

核心就是 DirtyCardQueue::apply_closure_to_buffer,最终调用 g1RemSet中的RefineRecordRefsIntoCSCardTableEntryClosure闭包.可以看到关联到G1RemSet指针。然后去调用refine_card方法。

class RefineRecordRefsIntoCSCardTableEntryClosure: public CardTableEntryClosure {
G1RemSet* _g1rs;
DirtyCardQueue* _into_cset_dcq;
public:
RefineRecordRefsIntoCSCardTableEntryClosure(G1CollectedHeap* g1h,
DirtyCardQueue* into_cset_dcq) :
_g1rs(g1h->g1_rem_set()), _into_cset_dcq(into_cset_dcq)
{}
bool do_card_ptr(jbyte* card_ptr, uint worker_i) {
assert(SafepointSynchronize::is_at_safepoint(), "not during an evacuation pause");
assert(worker_i < (ParallelGCThreads == 0 ? 1 : ParallelGCThreads), "should be a GC worker");
if (_g1rs->refine_card(card_ptr, worker_i, true)) {
_into_cset_dcq->enqueue(card_ptr);
}
return true;
}
};

refine_card方法,篇幅太长，我这里贴一下代码链接g1RemSet#refine_card

主要逻辑如下

• 如果当前对应的这块卡不是脏卡了，就不处理了。

• 获取当前卡表对应的开始地址，获取对应分区的指针，不处理新生代和CollectionSet内的引用

• 处理高频更新的卡表缓冲

• 从开始找一共找512个字节的区域去处理

  • HeapWord* end = start + CardTableModRefBS::card_size_in_words;
    MemRegion dirtyRegion(start, end);

  •  
  • CardTableModRefBS::card_size_in_words参见CardTableModRefBS#SomePublicConstants为512个字节
  •  

• 定义一个G1ParPushHeapRSClosure闭包处理对象，来处理当前对象往后所在的字节区域的标记。观察HeapRegion#oops_on_card_seq_iterate_careful方法，发现定位当前对象所在的内存块时候，需要跳过这个对象之前的内存地址，然后找到之后把这512字节的内存区块标示为被引用，可以想到的在这512字节的内存区块，不全是存活对象，有可能就会存在无任何引用的对象，但是由于被标记为被引用，无法被清除，这些无任何引用对象就是一部分浮动垃圾。

  • HeapWord* HeapRegion::oops_on_card_seq_iterate_careful(MemRegion mr,
    FilterOutOfRegionClosure* cl,
    bool filter_young,
    jbyte* card_ptr) {
    if (filter_young) {
    assert(card_ptr != NULL, "pre-condition");
    } else {
    assert(card_ptr == NULL, "pre-condition");
    }
    G1CollectedHeap* g1h = G1CollectedHeap::heap();
    if (g1h->is_gc_active()) {
    mr = mr.intersection(MemRegion(bottom(), scan_top()));
    } else {
    mr = mr.intersection(used_region());
    }
    if (mr.is_empty()) return NULL;
    if (is_young() && filter_young) {
    return NULL;
    }
    if (card_ptr != NULL) {
    *card_ptr = CardTableModRefBS::clean_card_val();
    OrderAccess::storeload();
    }
    HeapWord* const start = mr.start();
    HeapWord* const end = mr.end();
    HeapWord* cur = block_start(start);
    assert(cur <= start, "Postcondition");
    oop obj;
    HeapWord* next = cur;
    do {
    cur = next;
    obj = oop(cur);
    if (obj->klass_or_null() == NULL) {
    return cur;
    }
    next = cur + block_size(cur);
    } while (next <= start);
    assert(cur <= start, "Loop postcondition");
    assert(obj->klass_or_null() != NULL, "Loop postcondition");
    do {
    obj = oop(cur);
    assert((cur + block_size(cur)) > (HeapWord*)obj, "Loop invariant");
    if (obj->klass_or_null() == NULL) {
    return cur;
    }
    cur = cur + block_size(cur);
    if (!g1h->is_obj_dead(obj)) {
    if (!obj->is_objArray() || (((HeapWord*)obj) >= start && cur <= end)) {
    obj->oop_iterate(cl);
    } else {
    obj->oop_iterate(cl, mr);
    }
    }
    } while (cur < end);
    return NULL;
    }

Refine线程主要关注下源代码concurrentG1RefineThread，直接看run方法这块自旋的处理。

do {
int curr_buffer_num = (int)dcqs.completed_buffers_num();
//如果所有已提交的要处理的任务的数量下降到Remenber Zone黄色区域，

//可以减少Refine线程的数量
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) {
//如果要处理的任务的数量低于我们的阈值，减少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()));

抛出一些列判断来看，核心就是dcqs.apply_closure_to_completed_buffer(_refine_closure, _worker_id + _worker_id_offset, cg1r()->green_zone())

,这就是Refine线程的工作了。我们来看dirtyCardQueue#apply_closure_to_completed_buffer最终也是调用了使用G1RemSet内部的闭包，关联到G1RemSet指针。然后去调用refine_card方法。

同时Refine线程还有一个样本采集线程，用于控制新生代分区的个数。就是Refine中workid序号最大的那个，也就是concurrentG1RefineThread内部ConcurrentG1Refine._threads[_threads-1]代表的线程。工作流程如下，最终关联到G1CollectionPolicy#revise_young_list_target_length_if_necessary来动态设置这个新生代分区的大小。

void ConcurrentG1RefineThread::sample_young_list_rs_lengths() {
SuspendibleThreadSetJoiner sts;
G1CollectedHeap* g1h = G1CollectedHeap::heap();
G1CollectorPolicy* g1p = g1h->g1_policy();
if (g1p->adaptive_young_list_length()) {
int regions_visited = 0;
g1h->young_list()->rs_length_sampling_init();
while (g1h->young_list()->rs_length_sampling_more()) {
g1h->young_list()->rs_length_sampling_next();
++regions_visited;

// we try to yield every time we visit 10 regions
if (regions_visited == 10) {
if (sts.should_yield()) {
sts.yield();
// we just abandon the iteration
break;
}
regions_visited = 0;
}
}

g1p->revise_young_list_target_length_if_necessary();
}
}
//G1CollectionPolicy#revise_young_list_target_length_if_necessary

void G1CollectorPolicy::revise_young_list_target_length_if_necessary() {
guarantee( adaptive_young_list_length(), "should not call this otherwise" );

size_t rs_lengths = _g1->young_list()->sampled_rs_lengths();
if (rs_lengths > _rs_lengths_prediction) {
// add 10% to avoid having to recalculate often
size_t rs_lengths_prediction = rs_lengths * 1100 / 1000;
update_young_list_target_length(rs_lengths_prediction);
}
}

在update_young_list_target_length方法，你就可以看到上文中我们叙述的G1的停顿预测来进行新生代的启发式推断。

ok 回到这个refine线程处理DCQ这上面，和Remember Zone关联的就是apply_closure_to_completed_buffer方法的参数cg1r()->green_zone(),这里呢触发GC之后。默认值就是0 ，默认要处理所有的DCQ，回过去看run方法的代码可以发现在绿区的时候会根据任务的实际情况来调整Refine线程，而当已提交任务个数达到黄区域，则是所有的Refine线程都会区处理，不包括那个样本收集线程，当已提交任务个数达到红区的时候 ，Mutator去发生了引用修改去提交DCQS的时候就会发现忙不过来了，去协助处理。

上面我们看了Mutator帮助Refine线程去做事，虽然提供了这个能力，但是要极力避免这种情况的发生，因为看到了会拖慢Mutator线程。这就涉及到Refine线程的负载了。这里画个图来表示一下RememberSet Zone

• 白区

  由GC线程控制处理DCQ

• 绿区

  Refine线程开始工作

• 黄区(3倍的绿区的大小)

  所有的Refine都开始工作。不包括Refine抽样线程（Refine线程编号最大的那个）

• 红区(6倍的绿区的大小)

  所有的Refine都开始工作。包括Refine抽样线程，同时应用线程也会帮助处理DCQ。

   

相关阅读

G1垃圾回收源码分析(一)

G1垃圾回收源码分析(二)

G1垃圾回收源码分析(三)