GC roots, reachability, and why GC is graph traversal

You finish processing an order, but its customer data is still on the heap. Does that mean garbage collection missed it? To answer that, we need to follow the references that still lead to the data.

In Lesson 3, we zoomed into one object and separated its own storage from the objects its fields reference. Now zoom back out. Each object is a node, and each reference is a directed connection to another node. Together, they form an object graph.

References turn the heap into a graph

The final picture from Lesson 3 gives us our starting point. Follow the reference inside User to B, then from B to C. Each object occupies its own memory; the arrows describe how the objects are connected.

For the rest of this lesson, give those nodes application names:

class Order {
    Customer customer;
}

class Customer {
    Address address;
}

An Order can reference a Customer, which can reference an Address. The collector’s fundamental question is whether there is still a path to those objects from the running program. An object’s age can influence how a collector manages it, but age alone does not decide whether it is garbage.

An object becomes eligible for reclamation when it is no longer reachable from the GC root set.

We’ll use ordinary strong references throughout these pictures. Special reference processing, including weak references and finalization, adds rules that belong in a later lesson. Eligible does not mean reclaimed immediately: the collector must discover and reclaim the object in an appropriate collection.

Where traversal begins

The chain Order → Customer → Address does not tell us whether Order itself is reachable. We need an entry point into that chain. A GC root is a reference starting point the JVM knows to consider when discovering live objects.

For example, a live reference to Order in an executing method can keep the whole chain reachable. Address does not need a direct root reference: the path through Order and Customer is enough.

A root is not a special kind of Java object with a “root” header. We draw the root-set starting reference separately to distinguish the entry point from the ordinary object graph. Heap analyzers sometimes label the first object reached as a GC root; that reporting convention does not change the underlying reachability question.

Root sources connect the runtime to the heap

References can come from several parts of the running JVM. The left-hand labels in this picture identify sources; the object boxes are the things they keep reachable.

Live references in thread stack frames and registers connect executing methods to objects. Static state can also keep objects reachable through a live class and its runtime relationships. Static fields are not an unconditional promise of immortality: class-loader reachability and class unloading matter. Nor does the diagram imply static fields physically live outside the heap.

Native code can hold JNI local and strong global references, and the JVM maintains references in internal VM structures. JNI weak global references have different retention semantics and are outside our strong-reference model. The exact root categories and scanning machinery depend on the JVM and collector.

Follow one root from running code

Let’s make the thread case concrete. main starts a platform thread named t1, then waits for it to finish:

public static void main(String[] args)
        throws InterruptedException {
    Thread t1 = new Thread(
        RootExample::processOrder,
        "t1"
    );

    t1.start();
    t1.join();
}

static void processOrder() {
    Order order = loadOrder();
    chargeCustomer(order);
}

Imagine the collector examines the process while chargeCustomer(order) is still using the order. The running state includes both threads, but the important entry path to this object graph comes from t1:

Read the path from the root reference downward:

t1 stack slot or register
    └── order
          └──► Order
                  └──► Customer
                           └──► Address

main created t1, but that does not make the main thread the root of Order. The collector does not have to begin with main and walk through one Java-reference chain to every other thread. It builds a root set from all relevant runtime sources. In this snapshot, t1’s live order reference is one of those starting points. main may separately have a live t1 reference in its own frame, but that is a different root path to the Thread object.

If processOrder returns and no other strong path reaches the order, the t1 frame and its local reference disappear. The Order → Customer → Address graph can then become eligible for collection. Starting a thread does not permanently root every object it ever created.

While order is live, the collector still needs to find the reference whether it is held in a stack slot or a register. That reference keeps Order, Customer, Address, and everything strongly reachable from them alive. Source-level scope alone does not guarantee liveness until the closing brace: optimized code can stop needing a reference earlier.

The JVM cannot treat every machine word as an object reference. A frame may contain references, integers, saved execution state, and other values. HotSpot uses knowledge of the execution point and frame layout to identify the reference locations precisely.

For interpreted methods, HotSpot uses interpreter-frame information and reference maps for the bytecode position. For JIT-compiled methods, metadata associated with the compiled code describes where references can be found at relevant machine-code locations. Think of an OopMap as a map saying “this stack slot and this register contain object references.” It describes locations, not a list of every object reachable from them.

This is the connection to retain for later: the collector needs a correct root set, so the execution engine must help it interpret thread state. We’ll return to compiled frames, OopMaps, and safepoints when that cooperation becomes the main topic. The code and snapshot above illustrate the relationship; they do not promise the exact machine location of order in every compiled execution.

Reachability is transitive

Start at the reference at the top of the first panel. It reaches A; A reaches B; B reaches C. All three are reachable even though only A has a direct root reference.

Now remove the only root reference to A. B and C still have incoming references, and their fields have not changed. But those references originate inside a disconnected graph. Without another path from any root, all three become eligible for collection together.

Setting one variable to null is therefore not a universal instruction to collect an object. It removes one reference. Another local, a collection, or another root path may still reach that object.

Cycles do not keep themselves alive

Suppose A references B and B references A. Both have incoming references, but neither has a path from the root set. Follow the arrows around the cycle: they never connect it back to the running program.

A tracing collector can reclaim both objects. This is where tracing differs from simple reference counting: counting incoming references alone would miss that the entire cycle is disconnected. Ordinary cyclic Java structures do not inherently cause memory leaks. A root path into that cycle would keep it alive; the cycle itself does not.

Marking is graph traversal

Imagine a heap where the root reaches A, and A reaches B and C. Elsewhere, D reaches E, with no connection from the roots. The three stages below show discovery rather than elapsed time.

Conceptually, the collector starts with root references and puts newly discovered objects on a worklist. It takes an object from that list, examines its outgoing references, and records newly discovered targets. It continues until no pending objects remain.

Remembering which objects have already been discovered avoids repeatedly following the same cycle. In this example A, B, and C are marked; D and E remain unmarked. Marking identifies the live graph. Reclaiming or moving memory is a subsequent part of the collector’s strategy, and a mark need not mean modifying the object’s header.

This is a simplified whole-heap traversal over a stable graph. Real collectors can collect selected regions or generations, and concurrent collectors must account for references changing during collection. We will add those mechanisms later; they do not turn object age or incoming-reference counts into substitutes for reachability.

A Java heap leak usually contains reachable objects

Return to the customer data that survived processing. Suppose the application keeps an ever-growing cache:

static Map<String, Object> cache =
    new HashMap<>();

Assume its class remains live, and the application continually inserts new keys and values without eviction. The static reference reaches the map, which reaches its entries and their values. Follow that path in the picture.

The application no longer needs some values, but it still holds paths to them. The collector cannot infer the application’s intention. It correctly preserves reachable objects, so repeated collections cannot repair an unbounded retention policy.

This is the usual shape of a Java heap-retention leak: unwanted reachability rather than a failed collector. Native-memory and resource leaks need their own diagnosis. Even on the heap, a single large snapshot does not prove a leak; a deliberately sized cache can be legitimate. The important question is whether the retained data and its lifetime match the application’s needs.

Paths to GC roots explain survival

A heap histogram tells you which classes occupy memory. To understand why one Customer survives, inspect its incoming references and work back toward a root. A heap analyzer calls this a path to GC roots.

Here, Customer is an entry value, the entry is reachable through the map’s table, and the map is held by the live cache. Removing the entry can break this path. It only makes Customer collectible if no other strong root path remains. A request still in flight or a second cache might provide another one.

Heap tools can filter paths by reference strength. Keep those settings in mind: a weak-reference path does not establish the same retention as the strong paths shown here. Finding one path explains survival; finding and removing one path does not prove that all paths are gone.

From reachable size to retained size

Lesson 3 separated an object’s shallow size from the objects it references. Retained size asks a different question: how much memory would become eligible for collection if this object were removed from the reachable graph?

In the first panel, all paths to B and C pass through A. A therefore dominates B and C. Its retained set includes itself and those objects, and its retained size is the sum of their shallow sizes. A small object can consequently retain a large graph.

In the second panel, a root reaches B without passing through A. Removing A leaves B reachable, and B still reaches C. Neither B nor C belongs to A’s retained set in that graph. Merely adding up everything reachable from A would overstate what A alone retains.

This is the intuition behind a dominator tree: it organizes objects by which objects every root path must pass through. Its edges describe domination, not necessarily direct Java field references. We do not need the construction algorithm yet; we need the alternate-path check before interpreting a large retained-size number.

Check your reasoning

Use the marking picture again: a root reaches A, A reaches B and C, and a disconnected D references E. Now add a reference from E back to D.

Keep the graph model

We can now connect object layout to lifetime. Layout tells us what a node occupies; references connect the nodes; root-set starting references let the collector discover the live graph. This also gives us a practical debugging question: which root path keeps this unwanted object alive?

The next Lesson 5: mark-sweep, mark-compact, and copying moves from deciding what is live to deciding how to reclaim and organize memory. Fragmentation and allocation speed will help explain why those strategies differ.