KiokuGraph

Posted on Aug 8

Dominator trees explained, without the graph theory

#java #dotnet #jvm #memory

Open any heap analyser and you meet the word "dominator" in the first thirty seconds, usually with
no explanation. It sounds like theory. It is the single most practical idea in memory analysis, and
it takes about three minutes to understand properly.

The problem it solves

A heap is a graph: objects pointing at objects, with cycles, shared references and no tidy hierarchy.

You want to answer one question: if I fix this, how much memory do I get back?

That question is hard to answer from the graph directly. An object can be referenced from five
places. Dropping one reference frees nothing, because the other four still hold it. Counting the
bytes "under" an object by walking its references double-counts everything shared, and in a real
heap almost everything is shared.

So a naive answer overstates wildly. You need to know what an object holds exclusively.

The definition, in one sentence

X dominates Y if every path from the GC roots to Y passes through X.

That is it. "Every path" is the load-bearing part.

GC roots are where reachability begins - stack locals of live threads, static fields, JNI
references. An object survives collection because some path leads to it from a root. If every
such path goes through X, then removing X removes the last way to reach Y, and Y becomes garbage.

So dominance means: X is single-handedly keeping Y alive.

A worked example

        [GC root]
            |
            v
          Cache
         /     \
        v       v
    Session   Session
        \      /
         v    v
        UserRecord

Cache dominates both Session objects. Every path from the root reaches them through Cache.
Cache also dominates UserRecord. There are two paths to it, but both pass through Cache, so it still qualifies.
Neither Session dominates UserRecord. Remove the left one and the right still reaches it.

The consequence is the useful bit. Drop Cache and all four objects below become collectable. Drop
one Session and nothing is freed - UserRecord survives via the other, and the Session
itself is only reclaimed if nothing else points at it.

This is why "which object has the most references?" is the wrong question and "which object
dominates the most bytes?" is the right one.

Retained size

The retained size of X is the total bytes of X plus everything X dominates. Equivalently: the
memory that becomes free if X becomes unreachable.

Contrast with shallow size, the bytes of the object itself - for a HashMap, about 48 bytes,
regardless of whether it holds three entries or three million.

That gap is what makes leaks findable:

Object	Shallow	Retained
`HashMap`	48 B	4.7 GB
`byte[]` (one of 27,000)	8 KB	8 KB
`String` (one of 1.2 M)	40 B	40 B

A histogram sorted by instance count puts String at the top and tells you nothing - a million
strings is what a healthy application looks like. Sorted by retained size, that 48-byte HashMap
appears first, and it is the outage.

The tree

Compute the dominator relationship for every object and you get a tree, because dominance has a
convenient property: each object has exactly one immediate dominator, the closest object that
dominates it. Link each to its immediate dominator and the messy graph becomes a tree.

The tree has two properties that make it worth the computation:

No double-counting. Every object appears exactly once. Retained sizes down the tree sum correctly, so the numbers can be trusted and compared.
Sorting by retained size ranks your problems. The top of the tree is, in order, the things whose removal frees the most memory. That is a work queue.

Note what the tree is not: it is not the reference graph. A dominator tree edge does not mean "X
has a field pointing at Y". It means "X is the last thing standing between Y and the collector".

How to read it during an incident

Sort by retained size, descending. Look at the top ten and no further at first.
Ignore the framework. The first entries are often a classloader, a thread pool or a connection pool. Those legitimately dominate a lot. You are looking for something yours.
Look for a small object with an enormous retained size. A static field, a cache, a listener list. That asymmetry is the signature of a leak.
Expand one level, not ten. The children tell you what is being retained - sessions? byte arrays? - which usually names the bug immediately.
Then ask why it is still reachable. The path from the GC root to that object is the code path that has to change.

Steps 1-4 usually take a couple of minutes. Step 5 is the actual debugging.

Why it is computed, not estimated

Dominance is a defined relation over a directed graph, not a heuristic. Two analysers over the same
dump produce the same dominator tree, or one of them is wrong. There is no tuning parameter and
nothing to interpret.

That matters when you are about to tell a room that the leak is in the session cache. "The analyser
thinks it might be here" invites argument. "Removing this frees 4.7 GB, and here is the reference
chain keeping it alive" ends the discussion.

The short version

Dominates = every path from a GC root passes through it = it is single-handedly keeping the object alive.
Retained size = what you get back if it goes away. Shallow size = the object alone.
Sort by retained size. Instance counts find noise; retained size finds leaks.
A small object with a huge retained size is the classic leak signature.
It is mathematics, not inference - which is why the number is arguable only if it is wrong.

KiokuGraph computes the dominator tree for JVM and .NET heaps and opens on
it sorted by retained size, so steps 1-4 above are the first screen. Free for a single dump.

DEV Community