Withdrawn: 8210708: Use single mark bitmap in G1

[Thomas Schatzl]

On Wed, 25 May 2022 14:40:39 GMT, Thomas Schatzl <tschatzl at openjdk.org> wrote:

> 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 not use the BOT, and must completely rely on the bitmap for object start and liveness information; the BOT functionality can be emulated by scanning the bitmap backwards (until start of the region) for a marked object; if that objects spans into the area we want to scan we have found the first object into the area we want to scan - otherwise we need to scan forward within the area we want to scan.
> Scanning backwards is a somewhat slow process, particularly since we do not know how far back the last previous object actually is: for this reason this change introduces a `Back scan skip table", which is like a very coarse bitmap (64k bytes/"mark" by default - that's 16 bytes per MB of heap, i.e. 0.0015% of the heap - configurable) that aids in scanning back very large areas.
> Testing showed that the need for this back scan skip table is extremely seldom (like ten occurrences in millions of attempts), but if so, these skips are substantial.
> 
> 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 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 as 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), tier1-8 (with a slightly older version that does not contain latest cleanups, will do again)
> 
> Thanks,
>   Thomas

This pull request has been closed without being integrated.

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

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