introduction
In this post, I will delv into more specific details and examples of GC in the JVM. First, I'll explain the main concepts of GC and then examine how various garbage collectors operate.
Main Concepts
Root Node Enumeration
This process involves earching for reference chains starting from the GC root set.
- Examples of GC roots include global refereces and variables in the excecution context.
- To maintain consistency, this task is performed on a snapshot of the program state.
Ordinary Object Pointer Map
An OopMap stores information about references in the object's stack and registers once loading is complete. It includes details about which instructions modify references or OopMap data. Creating an OopMap for every instruction would be highly inefficent. Instead, OopMaps are only created for safe points, which are specific points in the code where the program may run for an extended time, such as during method calls, loops, or exception handling.
There are two methods for reaching safe points:
- Preemptive Suspension: User threads are interrupted and repeatedly checked until they reach a safe point.
- Voluntary Suspension: Threads poll a flag during execution and voluntarily pause at the next safe point.
A polling mechanism can use a single assembly instruction. For example, preventing memory access triggers a memory protection trap, which throws an exception handled by an exception handler to temporarily suspend the thead.
Safe Region
A safe region is a state or area where:
- No references to objects are made.
- No references to objects are modified.
When a thread is in a state like wating or ready, it cannot respond to interrupts. This is why the concept of a safe region is necessary. threads in a safe region do not need to be considered during GC.
Before a thread exits the safe region, it mus:
- Ensure that root node enumeration has been completed
- Check if any GC steps are still running that require the thread to pause.
Once thease checks are done, the thread can either resume execution or remain in a waiting state as needed.
Memory Set and Card Table
The goal of these techniques is to reduce the scope of root scans, which can be expensive when scanning references across generations.
Instead of scanning all references between generations, memory sets record only cross-generational references, allowing the GC to efficiently identify live objects.
A common appraoch to optimize this process is by reducing precision mapping records to memory blocks rather than individual objects.
- Dividing memroy into indexed blocks and implementing a byte array to track references allows the use of simple division operations to calculate indices.
Write Barrier
If an object in another generation references a block in a differenct generation, the refernce is marked in the card table either before or after the reference occurs. While this increases the cost of updating references, it is still lower than scanning the entire generation.
False sharing can occur when physically different varibales are stored in the same cache line. Since the card table manages regions of 512 bytes(the size of card), false sharing can have a significant impact within the range of cache line size multiplied by the card size.
Tricolor Marking Algorithm
The Garbage Collector can search the object graph after root node enumeration.
- White: Unreachable object
- Black: Object that doesn't reference any white object
- Gray: Reachable but the objects it references have not been checked yet
- Mark a gray object as black and mark all objects it references as gray
- Repeate until there are no gray objects left
- White objects are released
It is more critical to mistakenly consider a live object as dead than to consider a dead object as live. This situation can occur when a user thread adds a reference form a black object to a white object and simultaneously removes a reference form a gray object to a white object. Preventing just one of these two scenarios is sufficient to avoid this critical problem.
Incremental Update
- If a black object adds a reference to a white object, the change is recorded
- After the concurrent scan is complete, the recorded black objects are scanned again
- The white objects are marked as gray
Snapshot at the Beginning
- If a reference form a gray object to a white object is removed, the change is recorded
- After the concurrent scan is complete, the recorded gray objects (and their references) are scanned again
- The white objects are marked as gray
How Garbage Collectors Operate
G1
Shenandoah
ZGC
