Leakcanary: Compute retained size

[pyricau]

See http://www.cs.au.dk/~gerth/advising/thesis/henrik-knakkegaard-christensen.pdf

[pyricau]

Thoughts:

• Do it as we go through the shortest path. This will extend the path finding as we do need to go through all instances reachable from gc roots, but there's no need to do a separate path.
• As we go through, build a map of dominators (object id -> object id of dominator)
• Since we only care about total retained sized for leaking instances, each object will either be dominated by a leaking instance or "no dominator".
• Every new object discovered is dominated by its parent dominator (or its parent if the parent is a leaking instance), which will be a leaking instance or "no dominator"
• Every object rediscovered will be dominated by the closest common dominator (between the prior dominator and the objects parent dominator)
• If an object is a leaking instance, it may have another leaking instance as its dominator, or "no dominator"
• For every discovered object we also need to compute the shallow retained size.
• In the end for each leaking instance we find all objects that points to it as their dominator and sum their shallow size.
• If any of those dominated objects is a leaking instance, we also must add all of their summed retained size to the dominator retained size. Kind of an open question here, does it make sense to keep leaking instances which have another leaking instance on their path?
• We need a pluggable part for additional retained size (e.g. bitmaps)
• We only need to compute the shallow size for instances which are dominated by a leaking instance. It probably makes sense to keep two different structures: 1) the set of "no dominators" object ids (set of long) and 2) a map of (object id) -> (dominator object id, shallow retained size)
• Some objects will never make it into leak nodes (e.g. primitive arrays) but still need to count as part of retained size
• We need to keep going after we've found all leaking instances.
• We need to go through excluded "won't fix" leaks, but not weak refs.