RFR: 8210708: Use single mark bitmap in G1 [v3]

Wed Jun 1 10:56:39 UTC 2022

> Hi all,
> 
>   can I have reviews for this change that removes one of the mark bitmaps in G1 to save memory?
> 
> Previously G1 used two mark bitmaps, one that has been in use for current liveness determination ("prev bitmap"), one that is currently being built ("next bitmap"); these two then were swapped during the remark pause.
> 
> G1 needed the current liveness information to determine whether an object (and the corresponding klass) below the respective top-at-mark-start is live, i.e. could be read from.
> The mechanism is described in detail in the "Garbage-First Garbage Collection Paper" by Detlefs et al ([doi](https://doi.org/10.1145%2F1029873.1029879)).
> 
> This mechanism has several drawbacks:
> 
> *  you need twice the space than actually necessary as we will see; this space is significant as a bitmap adds ~1.5% of Java heap size to the G1 native memory usage
> *   during scanning the cards you need to rely a lot on walking the bitmaps (below tams) which is extra work, and actually most of the time it is the case that the tams is at the end of the region
> 
> The alternative presented here is to reformat the holes between objects with filler objects; this is a traditional sweep over the heap which has originally been considered fairly expensive. However since JDK 11 G1 already does that sweep anyway when rebuilding remembered sets, and during this investigation it has been shown that reformatting the holes is "for free".
> 
> That reformatting not only includes actually stuffing filler objects into these holes, but also updating the BOT concurrently.
> 
> This concurrency has some drawback: after class unloading (in the remark pause) and before the Cleanup pause (which indicates the end of the concurrent rebuilding of the remsets and scrubbing the regions phase) using the BOT needs some care:
> 
> *    during GC actually there is no issue: the BOT is at least stable in that it can not change while accessing it; the BOT may still point to dead objects, but these can be found using the bitmap.
> *    during concurrent refinement we can still use the BOT, because any mix of old BOT and new BOT eventually leads to some object start, i.e. an object before a given address. However that object may have been overwritten on the heap by filler object data, in a way that the heap is not parsable at the moment. So we must completely rely on the bitmap finding a valid object start from that (preliminary) object start. This observation is the difference to the previous [PR#8884](https://github.com/openjdk/jdk/pull/8884) and exploited in this change. This removes a few 100 LOC of changes :) 
> 
> Above I mentioned that there is a distinction between objects that can be parsed directly and objects for which we need to use the bitmap. For this reason the code introduces a per-region new marker called `parsable_bottom` (typically called `pb` in the code, similar to tams) that indicates from which address within the region the heap is parsable.
> 
> Let me describe the relation of tams and pb during the various phases in gc:
> 
> Young-only gcs (and initial state):
> `pb = tams = tars = bottom`; card scanning always uses the BOT/direct scanning of the heap
> 
> 
> bottom  top
> |       |  
> v       v
> +---------------------+
> |                     |
> +---------------------|
> ^
> |
> tams, pb, tars
> 
> During Concurrent Mark Start until Remark: `tams = top, pb = bottom`; concurrent marking runs; we can still use BOT/direct scanning of the heap for refinement and gc card scan.
> Marking not only marks objects from bottom to tams, but also sets a flag in the back scan skip table on a fairly coarse basis.
> 
> bottom    top
> |         |  
> v         v
> +---------------------+
> |                     |
> +---------------------|
> ^         ^
> |         |
> pb        tams
> 
> From Remark -> Cleanup: `pb = tams; tams = bottom; tars = top;` Remark unloaded classes, so we set `pb` to `tams`; in the region at addresses < `tams` we might encounter unparsable objects. This means that during this time, refinement can not use the BOT to find valid objects spanning into the card it wants to scan as described above. Use the bitmap for that.
> 
> Rebuild the remembered sets from `bottom` to `tars`, and scrub the heap from `bottom` to `pb`.
> 
> Note that the change sets `pb` incrementally (and concurrently) back to bottom as a region finishes scrubbing to decrease the size of the area we need to use the bitmap to help as a BOT replacement.
> Scrubbing means: put filler objects in holes of dead objects, and update the BOT according to these filler objects.
> 
> bottom        top
> |             |  
> v             v
> +---------------------+
> |                     |
> +---------------------|
> ^         ^   ^
> |         |   |
> tams      pb  (tars)
> 
> As soon as scrubbing finishes on a per-region basis: Set `pb` to `bottom` - the whole region is now parsable again. At Cleanup, all regions are scrubbed.
> 
> Evacuation failure handling: evacuation failure handling has been modified to accomodate this:
> 
> *   evac failure expects that the bitmap is clear for regions to (intermittently) mark live objects there. This still applies - the young collection needs to clear old gen regions, but only after the Cleanup pause (G1 can only have mixed gcs after cleanup) because only at that point marks may still be left from the marking on the bitmap of old regions. The young gc just clears those (and only those) at the beginning of gc. It also clears the bitmaps of old gen regions in the remove self-forwards phase.
> *    evac failure of young regions is handled as before: after evacuation failure the region is left as old gen region with marks below tams in the concurrent start pause, otherwise the bitmap is cleared.
> 
> Thanks go to @kstefanj for the initial prototype, @walulyai for taking over for a bit. I'll add both as contributors/authors.
> 
> Testing: tier1-5 (multiple times), tier 6-8 (running, but the previous version in PR#8884 completed this one fine)
> 
> Thanks,
>   Thomas

Thomas Schatzl has updated the pull request incrementally with one additional commit since the last revision:

  ayang review2; more cleanup of unnecessary changes, asserts

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/8957/files
  - new: https://git.openjdk.java.net/jdk/pull/8957/files/331fb52c..d3a7a96f

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=8957&range=02
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=8957&range=01-02

  Stats: 44 lines in 4 files changed: 1 ins; 11 del; 32 mod
  Patch: https://git.openjdk.java.net/jdk/pull/8957.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/8957/head:pull/8957

PR: https://git.openjdk.java.net/jdk/pull/8957