RFR: 8305896: Alternative full GC forwarding [v16]

Tue May 2 15:28:37 UTC 2023

On Tue, 2 May 2023 13:00:29 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:
> 
>   Address @shipilev's review

Hi Roman,

Small general concern, the last-last-ditch-GC fallback table may be impractical cost-wise. How large is that expected to grow? You pay 24+x (~48 on glibc with internal overhead) bytes per forwarded oop.

Very easy first-step mitigation: Let the table house the first n (1000-10000) nodes as an inline member array. Allocate nodes from there, only allocate spilloffs from C-heap. Allocation would be a lot faster and cheaper memory wise, and its just some lines of code.

Cheers, Thomas

src/hotspot/share/gc/shared/slidingForwarding.cpp line 35:

> 33: 
> 34: // We cannot use 0, because that may already be a valid base address in zero-based heaps.
> 35: // 0x1 is safe because heap base addresses must be aligned by much larger alginemnt

typo

src/hotspot/share/gc/shared/slidingForwarding.cpp line 44:

> 42:     _region_size_words_shift(log2i_exact(region_size_words)),
> 43:   _bases_table(nullptr),
> 44:   _fallback_table(nullptr) {

Assert for sane values for region_size? At least >= word size?

src/hotspot/share/gc/shared/slidingForwarding.cpp line 81:

> 79:   _bases_table = nullptr;
> 80: 
> 81:   if (_fallback_table != nullptr) {

null check not needed

src/hotspot/share/gc/shared/slidingForwarding.cpp line 137:

> 135: void FallbackTable::forward_to(HeapWord* from, HeapWord* to) {
> 136:   size_t idx = home_index(from);
> 137:   if (_table[idx]._from != nullptr) {

Here you need to do a contains check, right? Because, as you wrote in your answer to Aleksey, forwardings can be rewritten: https://github.com/openjdk/jdk/pull/13582/files#r1180126262

src/hotspot/share/gc/shared/slidingForwarding.hpp line 121:

> 119:   size_t           _region_size_words;
> 120:   size_t           _region_size_words_shift;
> 121:   HeapWord**       _bases_table;

Small nit. For clarity, I would prefer if we had a real structure here, e.g.:

struct region_forwarding { HeapWord* dest; HeapWord* alt_dest; };
region_forwarding* _table;

src/hotspot/share/gc/shared/slidingForwarding.hpp line 168:

> 166:   FallbackTableEntry _table[TABLE_SIZE];
> 167: 
> 168:   static size_t home_index(HeapWord* from);

Nitpicking, but I'd prefer an int or unsigned as return val here.

src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 56:

> 54:     // Primary is free
> 55:     _bases_table[base_idx] = to_region_base;
> 56:   } else if (region_contains(_bases_table[base_idx], to)) {

Stupid question, could this not just be `else if ( _bases_table[base_idx] == to_region_base)` ? Same below?

src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 87:

> 85: 
> 86: HeapWord* SlidingForwarding::decode_forwarding(HeapWord* from, uintptr_t encoded) const {
> 87:   assert((encoded & markWord::marked_value) == markWord::marked_value, "must be marked as forwarded");

Assert for !FALLBACK too?

src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 95:

> 93:   size_t base_idx = from_idx + alt_region;
> 94: 
> 95:   HeapWord* decoded = _bases_table[base_idx] + offset;

Maybe assert that table slot != UNUSED_BASE first

src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 115:

> 113:   uintptr_t encoded = encode_forwarding(from_hw, to_hw);
> 114:   markWord new_header = markWord((from_header.value() & ~MARK_LOWER_HALF_MASK) | encoded);
> 115:   from->set_mark(new_header);

What happens if the header is displaced into an OM? Should we not update the displaced header instead?

src/hotspot/share/gc/shared/slidingForwarding.inline.hpp line 125:

> 123:   assert(_bases_table != nullptr, "call begin() before asking for forwarding");
> 124: 
> 125:   markWord header = from->mark();

Could this header be displaced?

test/hotspot/gtest/gc/shared/test_slidingForwarding.cpp line 40:

> 38:   return ((uintptr_t(1) << 2) /* fallback */ | 3 /* forwarded */);
> 39: }
> 40: 

Could you add a test that forwarding works for displaced Oop+OM ?

-------------

Changes requested by stuefe (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/13582#pullrequestreview-1405661292
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182596471
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182631488
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182633369
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182691084
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182612217
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182688315
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182622823
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182636381
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182640645
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182644415
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182647104
PR Review Comment: https://git.openjdk.org/jdk/pull/13582#discussion_r1182706683