RFR: 8305896: Alternative full GC forwarding [v10]
Aleksey Shipilev
shade at openjdk.org
Fri Apr 28 09:35:28 UTC 2023
On Fri, 28 Apr 2023 07:52:53 GMT, Roman Kennke <rkennke at openjdk.org> wrote:
>> Currently, the full-GC modes of Serial, Shenandoah and G1 GCs are forwarding objects by over-writing the object header with the new object location. Unfortunately, for compact object headers ([JDK-8294992](https://bugs.openjdk.org/browse/JDK-8294992)) this would not work, because the crucial class information is also stored in the header, and we could no longer iterate over objects until the headers would be restored. Also, the preserved-headers tables would grow quite large.
>>
>> I propose to use an alternative algorithm for full-GC (sliding-GC) forwarding that uses a special encoding so that the forwarding information fits into the lowest 32 bits of the header.
>>
>> It exploits the insight that, with sliding GCs, objects from one region will only ever be forwarded to one of two possible target regions. For this to work, we need to divide the heap into equal-sized regions. This is already the case for Shenandoah and G1, and can easily be overlaid for Serial GC, by assuming either the whole heap as a single region (if it fits) or by using SpaceAlignment-sized virtual regions.
>>
>> We also build and maintain a table that has N elements, where N is the number of regions. Each entry is two addresses, which are the start-address of the possible target regions for each source region.
>>
>> With this, forwarding information would be encoded like this:
>> - Bits 0 and 1: same as before, we put in '11' to indicate that the object is forwarded.
>> - Bit 2: Used for 'fallback'-forwarding (see below)
>> - Bit 3: Selects the target region 0 or 1. Look up the base address in the table (see above)
>> - Bits 4..31 The number of heap words from the target base address
>>
>> This works well for all sliding GCs in Serial, G1 and Shenandoah. The exception is in G1, there is a special mode called 'serial compaction' which acts as a last-last-ditch effort to squeeze more space out of the heap by re-forwarding the tails of the compaction chains. Unfortunately, this breaks the assumption of the sliding-forwarding-table. When that happens, we initialize a fallback table, which is a simple open hash-table, and set the Bit 2 in the forwarding to indicate that we shall look up the forwardee in the fallback-table.
>>
>> All the table accesses can be done unsynchronized because:
>> - Serial GC is single-threaded anyway
>> - In G1 and Shenandoah, GC worker threads divide up the work such that each worker does disjoint sets of regions.
>> - G1 serial compaction is single-threaded
>>
>> The change introduces a new (experimental) flag -XX:[+|-]UseAltGCForwarding. This flag is not really intended to be used by end-users. Instead, I intend to programatically enable it with compact object headers once they arrive (i.e. -XX:+UseCompactObjectHeaders would turn on -XX:+UseAltGCForwarding), and the flag is also useful for testing purposes. Once compact object headers become the default and only implementation, the flag and old implementation could be removed. Also, [JDK-8305898](https://bugs.openjdk.org/browse/JDK-8305898) would also use the same flag to enable an alternative self-forwarding approach (also in support of compact object headers).
>>
>> The change also adds a utility class GCForwarding which calls the old or new implementation based on the flag. I think it would also be used for the self-forwarding change to be proposed soon (and separately).
>>
>> I also experimented with a different forwarding approach that would use per-region hashtables, but shelved it for now, because performance was significantly worse than the sliding forwarding encoding. It will become useful later when we want to do 32bit compact object headers, because then, the sliding encoding will not be sufficient to hold forwarding pointers in the header.
>>
>> Testing:
>> - [x] hotspot_gc -UseAltGCForwarding
>> - [x] hotspot_gc +UseAltGCForwarding
>> - [x] tier1 -UseAltGCForwarding
>> - [x] tier1 +UseAltGCForwarding
>> - [x] tier2 -UseAltGCForwarding
>> - [x] tier2 +UseAltGCForwarding
>
> Roman Kennke has updated the pull request incrementally with one additional commit since the last revision:
>
> Fix minimal build
I need to dive deeper into how `slidingForwarding.*` is documented and implemented, cursory review comments meanwhile.
src/hotspot/share/gc/g1/g1FullGCPrepareTask.inline.hpp line 35:
> 33: #include "gc/g1/g1FullGCScope.hpp"
> 34: #include "gc/g1/heapRegion.inline.hpp"
> 35: #include "gc/shared/gcForwarding.hpp"
`gcForwarding.inline.hpp`?
src/hotspot/share/gc/shared/gcForwarding.inline.hpp line 48:
> 46: } else
> 47: #endif
> 48: return obj->forwardee();
The usual style for these it to have braces on `else` path, so that you don't accidentally add the statement outside the `else` branch later. Like this:
#ifdef _LP64
if (UseAltGCForwarding) {
...
} else
#endif
{
return obj->forwardee();
}
src/hotspot/share/gc/shared/gcForwarding.inline.hpp line 59:
> 57: } else
> 58: #endif
> 59: obj->forward_to(fwd);
Same as above.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 49:
> 47: _num_regions = 1;
> 48: _region_size_words_shift = log2i_exact(round_up_power_of_2(heap_size_words));
> 49: }
This feels like something that Serial GC code should be doing when initializing the forwarding.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 54:
> 52: SlidingForwarding::~SlidingForwarding() {
> 53: if (_target_base_table != nullptr) {
> 54: FREE_C_HEAP_ARRAY(HeapWord*, _target_base_table);
Want to `nullptr` the pointers here? Not sure how sensible that is in destructors.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 64:
> 62: assert(_target_base_table == nullptr, "Should be uninitialized");
> 63: _target_base_table = NEW_C_HEAP_ARRAY(HeapWord*, _num_regions * NUM_TARGET_REGIONS, mtGC);
> 64: size_t max = _num_regions * NUM_TARGET_REGIONS;
Swap these lines and reuse `max`.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 90:
> 88: HeapWord* SlidingForwarding::fallback_forwardee(HeapWord* from) const {
> 89: if (_fallback_table == nullptr) {
> 90: return nullptr;
Is it an error to ask for `fallback_forwardee` if there is no table initialized? This implies that no fallback forwardings happened, which implies the no fallback mask is set in any object header, so why are we at this path?
src/hotspot/share/gc/shared/slidingForwarding.cpp line 119:
> 117: val *= 0xbf58476d1ce4e5b9ull;
> 118: val ^= val >> 56;
> 119: val *= 0x94d049bb133111ebull;
Is this a piece of SplitMix64? Let's say so in the comment.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 121:
> 119: val *= 0x94d049bb133111ebull;
> 120: val = (val * 11400714819323198485llu) >> (64 - log2i_exact(TABLE_SIZE));
> 121: assert(val < TABLE_SIZE, "must fit in table: val: " UINT64_FORMAT ", table-size: " UINTX_FORMAT ", table-size-bits: %d", val, TABLE_SIZE, log2i_exact(TABLE_SIZE));
Break the line before the arguments.
src/hotspot/share/gc/shared/slidingForwarding.cpp line 133:
> 131: entry->_to = _table[idx]._to;
> 132: _table[idx]._next = entry;
> 133: }
On else branch, we should probably assert that `_table[idx]._next == nullptr`? We don't set it, but it is safer to check.
src/hotspot/share/gc/shared/slidingForwarding.hpp line 111:
> 109: HeapWord** _target_base_table;
> 110:
> 111: FallbackTable* _fallback_table;
Indentation relative to other fields.
src/hotspot/share/gc/shared/slidingForwarding.hpp line 135:
> 133: /*
> 134: * A simple hash-table that acts as fallback for the sliding forwarding.
> 135: * This is used in the case of G1 serial compactio, which violates the
"compaction"
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 37:
> 35: size_t SlidingForwarding::region_index_containing(HeapWord* addr) const {
> 36: assert(addr >= _heap_start, "sanity: addr: " PTR_FORMAT " heap base: " PTR_FORMAT, p2i(addr), p2i(_heap_start));
> 37: size_t index = ((size_t) (addr - _heap_start)) >> _region_size_words_shift;
We have `pointer_delta` for these subtractions. (This would subsume the previous assert too, I think).
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 43:
> 41:
> 42: bool SlidingForwarding::region_contains(HeapWord* region_base, HeapWord* addr) const {
> 43: return uintptr_t(addr - region_base) < (1ull << _region_size_words_shift);
Same, `pointer_delta`
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 46:
> 44: }
> 45:
> 46:
Excess newline.
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 56:
> 54: encode_base = _target_base_table[base_table_idx + region_idx];
> 55: if (encode_base == UNUSED_BASE) {
> 56: encode_base = _heap_start + target_idx * (1ull << _region_size_words_shift);
`(1ull << _region_size_words_shift)` looks like something you want to pre-compute in a separate field.
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 64:
> 62: }
> 63: if (region_idx >= NUM_TARGET_REGIONS) {
> 64: assert(G1GC_ONLY(UseG1GC) NOT_G1GC(false), "Only happens with G1 serial compaction");
I think the "top" GC flags are always available -- they are deliberately defined in shared `gc_globals.hpp`, so you can just `assert(UseG1GC, ...` here?
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 70:
> 68: assert(target >= encode_base, "target must be above encode base, target:" PTR_FORMAT ", encoded_base: " PTR_FORMAT ", target_idx: " SIZE_FORMAT ", heap start: " PTR_FORMAT ", region_idx: " INTPTR_FORMAT,
> 69: p2i(target), p2i(encode_base), target_idx, p2i(_heap_start), region_idx);
> 70: assert(region_contains(encode_base, target), "region must contain target: original: " PTR_FORMAT ", target: " PTR_FORMAT ", encode_base: " PTR_FORMAT ", region_idx: " INTPTR_FORMAT, p2i(original), p2i(target), p2i(encode_base), region_idx);
These are way too long, need to be broken up with line breaks.
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 71:
> 69: p2i(target), p2i(encode_base), target_idx, p2i(_heap_start), region_idx);
> 70: assert(region_contains(encode_base, target), "region must contain target: original: " PTR_FORMAT ", target: " PTR_FORMAT ", encode_base: " PTR_FORMAT ", region_idx: " INTPTR_FORMAT, p2i(original), p2i(target), p2i(encode_base), region_idx);
> 71: uintptr_t encoded = (((uintptr_t)(target - encode_base)) << COMPRESSED_BITS_SHIFT) |
`pointer_delta`?
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 83:
> 81: size_t base_table_idx = orig_idx * 2 + region_idx;
> 82: HeapWord* decoded = _target_base_table[base_table_idx] + (encoded >> COMPRESSED_BITS_SHIFT);
> 83: assert(decoded >= _heap_start, "must be above heap start, encoded: " INTPTR_FORMAT ", region_idx: " SIZE_FORMAT ", base: " PTR_FORMAT, encoded, region_idx, p2i(_target_base_table[base_table_idx]));
Line break after format string.
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 100:
> 98: if ((encoded & FALLBACK_MASK) != 0) {
> 99: fallback_forward_to(from, to);
> 100: return;
No need for this `return`.
src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 108:
> 106: markWord header = original->mark();
> 107: if ((header.value() & FALLBACK_MASK) != 0) {
> 108: HeapWord* from = cast_from_oop<HeapWord*>(original);
Can pull this `from` to the shared path, and reuse below.
src/hotspot/share/gc/shared/space.cpp line 30:
> 28: #include "gc/shared/collectedHeap.inline.hpp"
> 29: #include "gc/shared/genCollectedHeap.hpp"
> 30: #include "gc/shared/gcForwarding.inline.hpp"
Not in alphabetic order :)
test/hotspot/gtest/gc/shared/test_slidingForwarding.cpp line 60:
> 58:
> 59: sf.forward_to(obj1, obj2);
> 60: ASSERT_EQ(obj1->mark().value(), uintptr_t((2 << 4) | 3));
These "magic" `(2 << 4) | 3` values should really be the calls to helper method in the test, I think. Would make the test much easier to maintain if any changes in header format are done.
test/hotspot/gtest/gc/shared/test_slidingForwarding.cpp line 63:
> 61: ASSERT_EQ(sf.forwardee(obj1), obj2);
> 62:
> 63: sf.forward_to(obj1, obj3);
Wait, so this implies the forwardings can be overwritten? I understand this need for the test, but wouldn't that be a lifecycle error for product code? Once forwarding is done, it must be only reset, no?
-------------
PR Review: https://git.openjdk.org/jdk/pull/13582#pullrequestreview-1404392852
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180102170
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180107096
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180107632
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180132214
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180133548
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180132855
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180137812
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180140786
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180141592
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180148194
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180157853
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180149772
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180152420
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180153007
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180153255
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180158933
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180160952
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180162695
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180163068
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180163746
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180164630
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180165500
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180103112
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180120093
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1180126262
More information about the shenandoah-dev
mailing list