Understanding GC: Roots, Reachability, and Mark-and-Sweep

The Problem: Unreferenced Objects

Let's begin by visualizing the problem that garbage collection solves. In previous lessons, we established that the JVM divides its memory into different areas. For this discussion, the most important are the JVM stack and the heap. Each thread has its own stack, which stores frames for each method call. These frames hold primitive local variables and references to objects. The objects themselves live on the shared heap.

When a method finishes executing, its stack frame is popped, and all the references within it vanish. But what about the objects on the heap that those references were pointing to? They become "orphaned" or "unreferenced." Without garbage collection, this memory would be lost forever, leading to a memory leak.

The following video provides an excellent and detailed walkthrough of this exact scenario. It visualizes how method calls build up the stack and how objects are created on the heap. Pay close attention to what happens when the method stack frames are unwound.

As the video illustrates, once all references to an object are gone, it becomes inaccessible to the running program. This inaccessible object is "garbage," and its memory can be safely reclaimed. The central question for the JVM is: how can it reliably identify all such garbage objects?

Object Reachability and GC Roots

The JVM's approach is elegant. Instead of hunting for garbage, it does the opposite: it identifies everything that is still alive. An object is considered "alive" or reachable if the application can access it through a chain of references starting from a special set of entry points. These foundational entry points are known as Garbage Collection Roots (GC Roots).

If an object is not reachable from any GC Root, it is considered garbage. This approach neatly sidesteps a major problem found in simpler memory management schemes like reference counting. In reference counting, two objects can point to each other in a cycle, keeping each other's reference count above zero even if the program has lost all access to them. A reachability analysis correctly identifies such cycles as garbage.

So, what exactly constitutes a GC Root in the HotSpot JVM?

As you've just read, the main GC Roots are:

• Local variables and method parameters: These are stored on the thread stacks. Since they are part of the application's active execution, any object they reference is alive.
• Active threads: The thread objects themselves are considered live.
• Static fields: Static variables belong to a class, not an instance, and exist for the lifetime of the class. They serve as global-like roots.
• JNI References: References created from native code (Java Native Interface). The JVM must assume these are live, as it cannot analyze the native code's behavior.

The core idea is to build a graph of all live objects by starting at these roots and following every reference.

The Mark-and-Sweep Algorithm

The most fundamental algorithm for performing this reachability analysis is called mark-and-sweep. As its name suggests, it operates in two distinct phases.

Let's break down these two phases in more detail.

1. The Mark Phase

In this phase, the garbage collector identifies all live objects.

1. It begins by identifying all the GC Roots.
2. It then "walks" the object graph, starting from these roots. For each object it encounters, it follows all the reference fields within that object to other objects.
3. Every unique object visited during this traversal is marked as being alive. A common way to implement this is by flipping a bit in the object's header—recall the "mark word" we discussed in a previous lesson.

The following animation provides a great visual of this process.

To manage this traversal without getting lost in cycles, garbage collection algorithms often use a conceptual model called the tricolor abstraction. It helps to reason about the state of the object graph during the marking process.

In summary, the tricolor abstraction works as follows:

• White: Initially, all objects are white. This is the set of objects presumed to be garbage.
• Gray: When the GC first discovers an object, it colors it gray. This means the object is reachable, but the GC hasn't yet scanned its fields for further references. The set of gray objects is essentially the "worklist" for the collector.
• Black: Once the GC has scanned all references within a gray object, it colors that object black. This means the object and all objects directly reachable from it have been marked.

The mark phase is complete when there are no gray objects left. At this point, any object that is still white is unreachable and confirmed to be garbage.

2. The Sweep Phase

Once the mark phase is finished, the collector moves to the sweep phase. This phase is more straightforward. The collector scans the entire heap from start to finish. For each object it finds:

• If the object is marked (i.e., it was colored black), it is a live object. The GC un-marks it (resets the bit) in preparation for the next GC cycle and leaves it alone.
• If the object is not marked (i.e., it remained white), it is garbage. The collector reclaims the memory it occupies, making that space available for future allocations.

The following video gives a concise summary of the entire mark-and-sweep process.

A crucial aspect of this process, mentioned in the resources, is that classic mark-and-sweep requires the application to be paused. This is known as a Stop-The-World (STW) pause. The application threads are frozen so that they cannot change the object graph while the collector is trying to traverse it. This pause is a primary source of latency in Java applications, and much of the innovation in garbage collection has focused on minimizing its duration and impact.

Conclusion

In this lesson, you've learned the fundamental principles of garbage collection in Java. We've moved from the problem of orphaned objects on the heap to a robust, graph-based solution for automatically managing memory.

Key Takeaways:

• Garbage Collection is the process of automatically reclaiming memory used by objects that are no longer accessible by the application.
• Object Reachability is the criterion for determining if an object is "alive." An object is reachable if it can be accessed through a chain of references starting from a GC Root.
• GC Roots are the starting points for the reachability analysis and include local variables, active threads, and static fields.
• Mark-and-Sweep is a foundational GC algorithm with two phases:
  1. Mark: Traverse the object graph from the GC Roots to mark all live objects.
  2. Sweep: Scan the heap and reclaim the memory of all unmarked (unreachable) objects.
• This process typically involves a "Stop-The-World" pause, where application threads are halted to ensure the integrity of the object graph during collection.

While mark-and-sweep is a complete and correct algorithm, it's not the most efficient. In our next lesson, we will explore generational garbage collection, a powerful optimization based on the observation that most objects have very short lifecycles. This "weak generational hypothesis" allows the JVM to focus its collection efforts far more effectively, significantly improving application performance.