Compute "LeakShare" instead of retained size?

[pyricau]

This is inspired by the BLeak paper from @jvilk

We currently report retained size, which is computed on dominators. Retained size only considers objects uniquely owned by dominators.

The "leaktrace" is the shortest path from GC Roots to a known leaking object, and there can be multiple paths from roots (and even from a single root) to the leaking instance as well as what it retains, so the retained size is often much smaller than what would be reclaimed if the leak was fixed.

In LeakCanary, we've somewhat worked around that by showing the retained size for each node in the path. The leak cause is typically one of the refs along the path, so if that leak is also a unique ref to the rest of the subgraph then the retained size associated with it should be correct.

However there are cases where this isn't true, e.g. when a leak is caused by forgetting to deregister from a store and that store holds references from two different places. In that case, we only see the shortest path but there's another longer path pointing to the same instance so retained size won't be accurate.

LeakShare distributes the size of retained objects equally amongst leak roots. Quote from the paper:

LeakShare first marks all of the items in the heap that are reachable from non-leaks via a breadth-first traversal that stops at leak roots. These nodes are ignored by subsequent traversals. Then, LeakShare performs a breadth-first traversal from each leak root that increments a counter on all reachable nodes. Once this process is complete, every node has a counter containing the number of leak roots that can reach it. Finally, the algorithm calculates the LeakShare of each leak root by adding up the size of each reachable node divided by its counter, which splits the “credit” for the node among all leak roots that can reach it.

One tricky bit here is that LeakCanary finds all the leaks and computes retained size in a single BFS. By design, navigating the graph requires IO reads, so avoiding additional BFS would be nice.

BLeak creates a clear set of distincts leak roots, whereas LeakCanary returns a set of paths to leaking objects where the "leak root" could be anywhere in a sub path of its path from GC Root. When we look at nodes on the path, we probably want a number that says "if this ref was cleared, here's how much we'd reclaim".

Thinking about this more, it seems like LeakShare is mostly interesting if we have several identified leaks with distinct paths. LeakCanary takes a shortcut and assumes only the shortest path matters, and once that leak is fixed any other leak will surface.

So... I'm not sure exactly if LeakShare would be useful, nor if we could have an efficient implementation.

Related DominatorTree in LeakCanary: https://github.com/square/leakcanary/blob/main/shark/src/main/java/shark/internal/DominatorTree.kt#L42