JVM G1 源码分析（三）- Remembered Sets
1. 简介
记录集Remembered Sets简称RSet，用于记录对象在不同分区之间的引用关系，目的是为了加速垃圾回收的速度，主要是加速标记阶段。
本文将详细介绍RSet的结构。
通常的，有两种记录引用关系的方式，PointOut和PointIn。
如果obj1.field1=obj2，如果是PointOut方式，则在obj1所在region的RSet记录obj2的位置；如果是PointIn方式，则在obj2所在region记录obj1的位置。G1采用的是PointIn方式。
一共有五种分区间的引用关系：
- 分区内引用
- 新生代分区Y1引用新生代分区Y2
- 新生代分区Y1引用老年代分区O1
- 老年代分区O1引用新生代分区Y1
- 老年代分区O1引用老年代分区O2
YGC时，GC root主要是两类：栈空间和老年代分区到新生代分区的引用关系。
Mixed GC时，由于仅回收部分老年代分区，老年代分区之间的引用关系也将被使用。
因此，我们仅需要记录两种引用关系：老年代分区引用新生代分区，老年代分区之间的引用。
2. RSet
由于PointIn模式的缺点，一个对象可能被引用的次数不固定，为了节约空间，G1采用了三级数据结构来存储：
- 稀疏表：通过哈希表来存储，key是region index，value是card数组
- 细粒度PerRegionTable：当稀疏表指定region的card数量超过阈值时，则在细粒度PRT中创建一个对应的PerRegionTable对象，其包含一个C heap位图，每一位对应一个card
- 粗粒度位图：当细粒度PRT size超过阈值时，则退化为分区位图，每一位表示对应分区有引用到当前分区
每个HeapRegion都包含了一个HeapRegionRemSet，每个HeapRegionRemSet都包含了一个OtherRegionsTable，引用数据就保存在这个OtherRegionsTable中。
我们通过添加引用来了解RSet的结构。
添加引用的入口在heapRegionRemSet.cpp中
void OtherRegionsTable::add_reference(OopOrNarrowOopStar from, uint tid) {// Note that this may be a continued H region.HeapRegion* from_hr = _g1h->heap_region_containing(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)) {assert(contains_reference(from), "We just found " PTR_FORMAT " in the Coarse table", p2i(from));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) {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) {CardIdx_t card_index = card_within_region(from, from_hr);if (_sparse_table.add_card(from_hrm_ind, card_index)) {assert(contains_reference_locked(from), "We just added " PTR_FORMAT " to the Sparse table", p2i(from));return;}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);// The assignment into _fine_grain_regions allows the prt to// start being used concurrently. In addition to// collision_list_next which must be visible (else concurrent// parsing of the list, if any, may fail to see other entries),// the content of the prt must be visible (else for instance// some mark bits may not yet seem cleared or a 'later' update// performed by a concurrent thread could be undone when the// zeroing becomes visible). This requires store ordering.OrderAccess::release_store(&_fine_grain_regions[ind], prt);_n_fine_entries++;// 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 < sprt_entry->num_valid_cards(); i++) {CardIdx_t c = sprt_entry->card(i);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);assert(contains_reference(from), "We just added " PTR_FORMAT " to the PRT (%d)", p2i(from), prt->contains_reference(from));
}
- 大对象可能跨region，因此需要找到该对象的头部region
- 判断region index是否在粗粒度位图中，如是，则直接返回
- 在细粒度PRT中查找region index对应的记录，如有，则返回
- 在稀疏表中添加该region index和card，如果返回成功或found，则返回
- 如果_sparse_table.add_card返回overflow，则表示稀疏表对应region记录已超过阈值，则在细粒度PRT中添加region index和card
稀疏表主要逻辑在sparsePRT.hpp中
class SparsePRTEntry: public CHeapObj {
private:// The type of a card entry.typedef uint16_t card_elem_t;static const size_t card_array_alignment = sizeof(int) / sizeof(card_elem_t);RegionIdx_t _region_ind;int _next_index;int _next_null;card_elem_t _cards[card_array_alignment];
}bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {SparsePRTEntry* e = entry_for_region_ind_create(region_ind);assert(e != NULL && e->r_ind() == region_ind,"Postcondition of call above.");SparsePRTEntry::AddCardResult res = e->add_card(card_index);if (res == SparsePRTEntry::added) _occupied_cards++;assert(e->num_valid_cards() > 0, "Postcondition");return res != SparsePRTEntry::overflow;
}SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {for (int i = 0; i < num_valid_cards(); i++) {if (card(i) == card_index) {return found;}}if (num_valid_cards() < cards_num() - 1) {_cards[_next_null] = (card_elem_t)card_index;_next_null++;return added;}// Otherwise, we're full.return overflow;
}
往稀疏表中添加引用的逻辑主要在两个add_card方法中：
- 根据region index从哈希表中找到SparsePRTEntry
- 在_cards中遍历，如果card已经记录，则返回found；
- 如果小于阈值，则添加card到_cards数组
- 如果大于等于阈值，则返回overflow
细粒度PRT主要逻辑在heapRegionRemSet.cpp的PerRegionTable类中
class PerRegionTable: public CHeapObj {friend class OtherRegionsTable;friend class HeapRegionRemSetIterator;HeapRegion* _hr;CHeapBitMap _bm;jint _occupied;PerRegionTable* _next;PerRegionTable* _prev;PerRegionTable * _collision_list_next;static PerRegionTable* volatile _free_list;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++;}}}
}
- _bm是个C heap位图，每一位对应region中的一个card
- 添加引用时，先根据card在_bm中找到对应bit位置，然后将该bit置为1
- _occupied引用数量加1，如果是并行操作则使用原子指令加1
粗粒度位图的逻辑简单很多，主要是在OtherRegionsTable中定义了一个CHeapBitMap
class OtherRegionsTable {CHeapBitMap _coarse_map;
}
3. 总结
在串行和并行GC中，GC通过整堆扫描，来确定对象是否处于可达路径中。
然而G1为了避免整堆扫描，为每个分区记录了一个RSet，记录引用分区内对象的card索引。这样标记时，仅仅需要扫描对应分区的对应card中的对象是否可达即可，极大的提升了GC效率。
4. 引用
jdk12源代码[https://hg.openjdk.java.net/jdk/jdk12]
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！