Understand JVM GC: G1 Regions, Remembered Sets, SATB Barriers

Topic Overview

G1 Garbage Collector

G1 (Garbage-First) divides the heap into equal-sized regions and collects the ones with the most garbage first. It targets predictable pause times on large heaps, unlike single-heap stop-the-world collectors.

Regions, Remembered Sets, SATB

Key mechanisms:

• Regions: typically 1-32 MiB; eden, survivor, and old data can live in different regions over time
• Remembered sets: per-region logs of cross-region references so GC need not scan the entire heap
• SATB barriers: snapshot-at-the-beginning logging keeps concurrent marking sound while mutators run

Young collections evacuate live objects from eden regions; mixed collections fold in old regions with high reclaim potential.

For example, a 8 GiB heap split into 2048 regions lets G1 target a 200 ms pause by collecting just 20 regions worth of garbage.

Design Notes

Pause time goals are hints, not guarantees. Under allocation pressure G1 may still collect more regions than planned; pair `-XX:MaxGCPauseMillis` with GC logs to see real behavior.

For This Exercise

This exercise asks you to document G1's region model, remembered sets, and SATB write barriers. You will explain how G1 bounds pause time compared to whole-heap collectors.

You will use the same mental model here when reading production interpreter source later in the track. Sketch one concrete input on paper, predict the outcome, then confirm with code. That discipline catches logic errors early and makes debugging far faster when you extend the implementation in follow-on tasks.

Your Task

Simulate the G1 garbage collector on a tiny heap:

• regions (eden, survivor, old, humongous);
• the post-write barrier that maintains per-region remembered sets;
• young collections that evacuate live objects, using RSets as extra roots;
• concurrent marking with the SATB pre-write barrier;
• mixed collections that pick the old regions with the most garbage first.

Heap

16 regions (r0-r15) of 8 units each. Objects have a size in units, two reference fields (0 and 1, initially null), an age, and a root flag.

• Allocation: objects of at most 4 units go into the current eden region. When it lacks room, the lowest-numbered free region becomes the new current eden. If 4 eden regions already exist, first print eden full: young GC and run a young GC labelled young GC (allocation failure).
• Humongous: objects over 4 units take the lowest run of contiguous free regions (humongous, then humongous-cont, with the last one holding the remainder). They never move.

Barriers (on ref A.F B)

• SATB: while marking, if the field's old value is non-null, print SATB: enqueue OLD and remember it.
• Post-write: if B is non-null, A and B are in different regions, A's region is not young (eden/survivor), and B's RSet doesn't have it yet, print RSet[rB] += rA and add A's region to the RSet of B's region.

Young GC (collects all eden and survivor regions)

1. Eager reclaim: a humongous object that is not a root and not referenced by any live object's field is freed: eager reclaim: humongous NAME (rX-rY).
2. Live young objects: those reachable from the roots, or from the fields of every object (live or not) in an old/humongous region listed in some young region's RSet, following only young objects.
3. Evacuation: dead young objects are dropped. Survivors, in creation order, get age + 1 and are copied to a survivor region if the age is below 2, or to an old region otherwise. Copies bump-allocate into the current destination region of that type, and take the lowest free region when it is full.
4. The collected regions become free. All RSets are rebuilt from the live objects' fields, and the next allocation starts a new eden region.

The summary is LABEL: N live copied (S to survivor, P to old), D dead, F region(s) freed.

Marking

• mark start: clears all marks and prints concurrent mark started.

• mark end: marks everything reachable from the current roots, from every SATB-enqueued object, and from every object allocated during the cycle. Then it prints concurrent mark finished: and rN old: L/U units live for each old region.

• mixed-gc (needs a finished marking, else mixed-gc: needs a completed marking cycle) collects:

  • the young regions;
  • up to 2 old regions whose live share is below 65%, lowest live share first, each printed as collection set += rN (L/U live).

  Old objects in the collection set survive if they are marked, and move to old regions. The summary is labelled mixed GC.

Other commands

• regions lists the non-free regions: rN TYPE USED/8: names (- if empty, nothing for humongous-cont), then rset {rA rB} if the RSet is non-empty, then K free regions.
• root NAME / unroot NAME.

Errors:

• alloc: NAME SIZE (1-32 units)
• alloc X: name in use
• alloc X: out of memory…
• root: no object X / unroot: no object X
• ref: OBJ.FIELD (0-1) TARGET|null
• ref: no object X
• mark: start|end, mark: already marking, mark: not marking
• unknown command X

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A young GC must not trace through old objects. Old→young references are found only through the remembered sets. That is what makes young pauses independent of the old generation's size.
2. Marking must treat everything the SATB barrier saved as live, even if it is garbage by the end (floating garbage).

Hidden tests cover SATB keeping an overwritten object alive through a mixed GC, the choice of the mixed collection set, eden-full allocation failure, name reuse after collection, and every command error.