<lambda>null1 @file:Suppress("INVISIBLE_REFERENCE", "INVISIBLE_MEMBER")
2
3 package shark.internal
4
5 import java.util.ArrayDeque
6 import java.util.Deque
7 import shark.HeapGraph
8 import shark.HeapObject
9 import shark.OnAnalysisProgressListener
10 import shark.OnAnalysisProgressListener.Step.FINDING_DOMINATORS
11 import shark.OnAnalysisProgressListener.Step.FINDING_PATHS_TO_RETAINED_OBJECTS
12 import shark.ReferenceMatcher
13 import shark.ValueHolder
14 import shark.internal.PathFinder.VisitTracker.Dominated
15 import shark.internal.PathFinder.VisitTracker.Visited
16 import shark.internal.ReferencePathNode.ChildNode
17 import shark.internal.ReferencePathNode.RootNode
18 import shark.internal.ReferencePathNode.RootNode.LibraryLeakRootNode
19 import shark.internal.ReferencePathNode.RootNode.NormalRootNode
20 import shark.internal.hppc.LongScatterSet
21
22 /**
23 * Not thread safe.
24 *
25 * Finds the shortest path from leaking references to a gc root, first ignoring references
26 * identified as "to visit last" and then visiting them as needed if no path is
27 * found.
28 */
29 internal class PathFinder(
30 private val graph: HeapGraph,
31 private val listener: OnAnalysisProgressListener,
32 private val objectReferenceReader: ReferenceReader<HeapObject>,
33 referenceMatchers: List<ReferenceMatcher>
34 ) {
35
36 class PathFindingResults(
37 val pathsToLeakingObjects: List<ReferencePathNode>,
38 val dominatorTree: DominatorTree?
39 )
40
41 sealed class VisitTracker {
42
43 abstract fun visited(
44 objectId: Long,
45 parentObjectId: Long
46 ): Boolean
47
48 class Dominated(expectedElements: Int) : VisitTracker() {
49 /**
50 * Tracks visited objecs and their dominator.
51 * If an object is not in [dominatorTree] then it hasn't been enqueued yet.
52 * If an object is in [dominatorTree] but not in [State.toVisitSet] nor [State.toVisitLastSet]
53 * then it has already been dequeued.
54 *
55 * If an object is dominated by more than one GC root then its dominator is set to
56 * [ValueHolder.NULL_REFERENCE].
57 */
58 val dominatorTree = DominatorTree(expectedElements)
59 override fun visited(
60 objectId: Long,
61 parentObjectId: Long
62 ): Boolean {
63 return dominatorTree.updateDominated(objectId, parentObjectId)
64 }
65 }
66
67 class Visited(expectedElements: Int) : VisitTracker() {
68 /**
69 * Set of visited objects.
70 */
71 private val visitedSet = LongScatterSet(expectedElements)
72 override fun visited(
73 objectId: Long,
74 parentObjectId: Long
75 ): Boolean {
76 return !visitedSet.add(objectId)
77 }
78 }
79 }
80
81 private class State(
82 val leakingObjectIds: LongScatterSet,
83 val computeRetainedHeapSize: Boolean,
84 estimatedVisitedObjects: Int
85 ) {
86
87 /** Set of objects to visit */
88 val toVisitQueue: Deque<ReferencePathNode> = ArrayDeque()
89
90 /**
91 * Objects to visit when [toVisitQueue] is empty.
92 */
93 val toVisitLastQueue: Deque<ReferencePathNode> = ArrayDeque()
94
95 /**
96 * Enables fast checking of whether a node is already in the queue.
97 */
98 val toVisitSet = LongScatterSet()
99 val toVisitLastSet = LongScatterSet()
100
101 val queuesNotEmpty: Boolean
102 get() = toVisitQueue.isNotEmpty() || toVisitLastQueue.isNotEmpty()
103
104 val visitTracker = if (computeRetainedHeapSize) {
105 Dominated(estimatedVisitedObjects)
106 } else {
107 Visited(estimatedVisitedObjects)
108 }
109
110 /**
111 * A marker for when we're done exploring the graph of higher priority references and start
112 * visiting the lower priority references, at which point we won't add any reference to
113 * the high priority queue anymore.
114 */
115 var visitingLast = false
116 }
117
118 private val gcRootProvider = GcRootProvider(graph, referenceMatchers)
119
120 fun findPathsFromGcRoots(
121 leakingObjectIds: Set<Long>,
122 computeRetainedHeapSize: Boolean
123 ): PathFindingResults {
124 listener.onAnalysisProgress(FINDING_PATHS_TO_RETAINED_OBJECTS)
125 // Estimate of how many objects we'll visit. This is a conservative estimate, we should always
126 // visit more than that but this limits the number of early array growths.
127 val estimatedVisitedObjects = (graph.instanceCount / 2).coerceAtLeast(4)
128
129 val state = State(
130 leakingObjectIds = leakingObjectIds.toLongScatterSet(),
131 computeRetainedHeapSize = computeRetainedHeapSize,
132 estimatedVisitedObjects = estimatedVisitedObjects
133 )
134
135 return state.findPathsFromGcRoots()
136 }
137
138 private fun Set<Long>.toLongScatterSet(): LongScatterSet {
139 val longScatterSet = LongScatterSet()
140 longScatterSet.ensureCapacity(size)
141 forEach { longScatterSet.add(it) }
142 return longScatterSet
143 }
144
145 private fun State.findPathsFromGcRoots(): PathFindingResults {
146 enqueueGcRoots()
147
148 val shortestPathsToLeakingObjects = mutableListOf<ReferencePathNode>()
149 visitingQueue@ while (queuesNotEmpty) {
150 val node = poll()
151 if (leakingObjectIds.contains(node.objectId)) {
152 shortestPathsToLeakingObjects.add(node)
153 // Found all refs, stop searching (unless computing retained size)
154 if (shortestPathsToLeakingObjects.size == leakingObjectIds.size()) {
155 if (computeRetainedHeapSize) {
156 listener.onAnalysisProgress(FINDING_DOMINATORS)
157 } else {
158 break@visitingQueue
159 }
160 }
161 }
162
163 val heapObject = graph.findObjectById(node.objectId)
164 objectReferenceReader.read(heapObject).forEach { reference ->
165 val newNode = ChildNode(
166 objectId = reference.valueObjectId,
167 parent = node,
168 lazyDetailsResolver = reference.lazyDetailsResolver
169 )
170 enqueue(newNode, isLowPriority = reference.isLowPriority)
171 }
172 }
173 return PathFindingResults(
174 shortestPathsToLeakingObjects,
175 if (visitTracker is Dominated) visitTracker.dominatorTree else null
176 )
177 }
178
179 private fun State.poll(): ReferencePathNode {
180 return if (!visitingLast && !toVisitQueue.isEmpty()) {
181 val removedNode = toVisitQueue.poll()
182 toVisitSet.remove(removedNode.objectId)
183 removedNode
184 } else {
185 visitingLast = true
186 val removedNode = toVisitLastQueue.poll()
187 toVisitLastSet.remove(removedNode.objectId)
188 removedNode
189 }
190 }
191
192 private fun State.enqueueGcRoots() {
193 gcRootProvider.provideGcRoots().forEach { gcRootReference ->
194 enqueue(
195 gcRootReference.matchedLibraryLeak?.let { matchedLibraryLeak ->
196 LibraryLeakRootNode(
197 gcRootReference.gcRoot,
198 matchedLibraryLeak
199 )
200 } ?: NormalRootNode(
201 gcRootReference.gcRoot
202 ),
203 isLowPriority = gcRootReference.isLowPriority
204 )
205 }
206 }
207
208 @Suppress("ReturnCount")
209 private fun State.enqueue(
210 node: ReferencePathNode,
211 isLowPriority: Boolean
212 ) {
213 if (node.objectId == ValueHolder.NULL_REFERENCE) {
214 return
215 }
216
217 val parentObjectId = when (node) {
218 is RootNode -> ValueHolder.NULL_REFERENCE
219 is ChildNode -> node.parent.objectId
220 }
221
222 // Note: when computing dominators, this has a side effects of updating
223 // the dominator for node.objectId.
224 val alreadyEnqueued = visitTracker.visited(node.objectId, parentObjectId)
225
226 val visitLast = visitingLast || isLowPriority
227
228 when {
229 alreadyEnqueued -> {
230 val bumpPriority =
231 !visitLast &&
232 node.objectId !in toVisitSet &&
233 // This could be false if node had already been visited.
234 node.objectId in toVisitLastSet
235
236 if (bumpPriority) {
237 // Move from "visit last" to "visit first" queue.
238 toVisitQueue.add(node)
239 toVisitSet.add(node.objectId)
240 val nodeToRemove = toVisitLastQueue.first { it.objectId == node.objectId }
241 toVisitLastQueue.remove(nodeToRemove)
242 toVisitLastSet.remove(node.objectId)
243 }
244 }
245 visitLast -> {
246 toVisitLastQueue.add(node)
247 toVisitLastSet.add(node.objectId)
248 }
249 else -> {
250 toVisitQueue.add(node)
251 toVisitSet.add(node.objectId)
252 }
253 }
254 }
255 }
256
257