<lambda>null1 @file:Suppress("INVISIBLE_REFERENCE", "INVISIBLE_MEMBER", "CANNOT_OVERRIDE_INVISIBLE_MEMBER")
2 package shark.internal
3
4 import shark.ValueHolder
5 import shark.internal.ObjectDominators.DominatorNode
6 import shark.internal.hppc.LongLongScatterMap
7 import shark.internal.hppc.LongLongScatterMap.ForEachCallback
8 import shark.internal.hppc.LongScatterSet
9
10 internal class DominatorTree(expectedElements: Int = 4) {
11
12 /**
13 * Map of objects to their dominator.
14 *
15 * If an object is dominated by more than one GC root then its dominator is set to
16 * [ValueHolder.NULL_REFERENCE].
17 */
18 private val dominated = LongLongScatterMap(expectedElements)
19
20 /**
21 * Records that [objectId] is a root.
22 */
23 fun updateDominatedAsRoot(objectId: Long): Boolean {
24 return updateDominated(objectId, ValueHolder.NULL_REFERENCE)
25 }
26
27 /**
28 * Records that [objectId] can be reached through [parentObjectId], updating the dominator for
29 * [objectId] to be either [parentObjectId] if [objectId] has no known dominator and otherwise to
30 * the Lowest Common Dominator between [parentObjectId] and the previously determined dominator
31 * for [objectId].
32 *
33 * [parentObjectId] should already have been added via [updateDominatedAsRoot]. Failing to do
34 * that will throw [IllegalStateException] on future calls.
35 *
36 * This implementation is optimized with the assumption that the graph is visited as a breadth
37 * first search, so when objectId already has a known dominator then its dominator path is
38 * shorter than the dominator path of [parentObjectId].
39 *
40 * @return true if [objectId] already had a known dominator, false otherwise.
41 */
42 fun updateDominated(
43 objectId: Long,
44 parentObjectId: Long
45 ): Boolean {
46 val dominatedSlot = dominated.getSlot(objectId)
47
48 val hasDominator = dominatedSlot != -1
49
50 if (!hasDominator || parentObjectId == ValueHolder.NULL_REFERENCE) {
51 dominated[objectId] = parentObjectId
52 } else {
53 val currentDominator = dominated.getSlotValue(dominatedSlot)
54 if (currentDominator != ValueHolder.NULL_REFERENCE) {
55 // We're looking for the Lowest Common Dominator between currentDominator and
56 // parentObjectId. We know that currentDominator likely has a shorter dominator path than
57 // parentObjectId since we're exploring the graph with a breadth first search. So we build
58 // a temporary hash set for the dominator path of currentDominator (since it's smaller)
59 // and then go through the dominator path of parentObjectId checking if any id exists
60 // in that hash set.
61 // Once we find either a common dominator or none, we update the map accordingly
62 val currentDominators = LongScatterSet()
63 var dominator = currentDominator
64 while (dominator != ValueHolder.NULL_REFERENCE) {
65 currentDominators.add(dominator)
66 val nextDominatorSlot = dominated.getSlot(dominator)
67 if (nextDominatorSlot == -1) {
68 throw IllegalStateException(
69 "Did not find dominator for $dominator when going through the dominator chain for $currentDominator: $currentDominators"
70 )
71 } else {
72 dominator = dominated.getSlotValue(nextDominatorSlot)
73 }
74 }
75 dominator = parentObjectId
76 while (dominator != ValueHolder.NULL_REFERENCE) {
77 if (dominator in currentDominators) {
78 break
79 }
80 val nextDominatorSlot = dominated.getSlot(dominator)
81 if (nextDominatorSlot == -1) {
82 throw IllegalStateException(
83 "Did not find dominator for $dominator when going through the dominator chain for $parentObjectId"
84 )
85 } else {
86 dominator = dominated.getSlotValue(nextDominatorSlot)
87 }
88 }
89 dominated[objectId] = dominator
90 }
91 }
92 return hasDominator
93 }
94
95 private class MutableDominatorNode {
96 var shallowSize = 0
97 var retainedSize = 0
98 var retainedCount = 0
99 val dominated = mutableListOf<Long>()
100 }
101
102 fun buildFullDominatorTree(computeSize: (Long) -> Int): Map<Long, DominatorNode> {
103 val dominators = mutableMapOf<Long, MutableDominatorNode>()
104 dominated.forEach(ForEachCallback {key, value ->
105 // create entry for dominated
106 dominators.getOrPut(key) {
107 MutableDominatorNode()
108 }
109 // If dominator is null ref then we still have an entry for that, to collect all dominator
110 // roots.
111 dominators.getOrPut(value) {
112 MutableDominatorNode()
113 }.dominated += key
114 })
115
116 val allReachableObjectIds = dominators.keys.toSet() - ValueHolder.NULL_REFERENCE
117
118 val retainedSizes = computeRetainedSizes(allReachableObjectIds) { objectId ->
119 val shallowSize = computeSize(objectId)
120 dominators.getValue(objectId).shallowSize = shallowSize
121 shallowSize
122 }
123
124 dominators.forEach { (objectId, node) ->
125 if (objectId != ValueHolder.NULL_REFERENCE) {
126 val (retainedSize, retainedCount) = retainedSizes.getValue(objectId)
127 node.retainedSize = retainedSize
128 node.retainedCount = retainedCount
129 }
130 }
131
132 val rootDominator = dominators.getValue(ValueHolder.NULL_REFERENCE)
133 rootDominator.retainedSize = rootDominator.dominated.map { dominators[it]!!.retainedSize }.sum()
134 rootDominator.retainedCount =
135 rootDominator.dominated.map { dominators[it]!!.retainedCount }.sum()
136
137 // Sort children with largest retained first
138 dominators.values.forEach { node ->
139 node.dominated.sortBy { -dominators.getValue(it).retainedSize }
140 }
141
142 return dominators.mapValues { (_, node) ->
143 DominatorNode(
144 node.shallowSize, node.retainedSize, node.retainedCount, node.dominated
145 )
146 }
147 }
148
149 /**
150 * Computes the size retained by [retainedObjectIds] using the dominator tree built using
151 * [updateDominatedAsRoot]. The shallow size of each object is provided by [computeSize].
152 * @return a map of object id to retained size.
153 */
154 fun computeRetainedSizes(
155 retainedObjectIds: Set<Long>,
156 computeSize: (Long) -> Int
157 ): Map<Long, Pair<Int, Int>> {
158 val nodeRetainedSizes = mutableMapOf<Long, Pair<Int, Int>>()
159 retainedObjectIds.forEach { objectId ->
160 nodeRetainedSizes[objectId] = 0 to 0
161 }
162
163 dominated.forEach(object : ForEachCallback {
164 override fun onEntry(
165 key: Long,
166 value: Long
167 ) {
168 // lazy computing of instance size
169 var instanceSize = -1
170
171 // If the entry is a node, add its size to nodeRetainedSizes
172 nodeRetainedSizes[key]?.let { (currentRetainedSize, currentRetainedCount) ->
173 instanceSize = computeSize(key)
174 nodeRetainedSizes[key] = currentRetainedSize + instanceSize to currentRetainedCount + 1
175 }
176
177 if (value != ValueHolder.NULL_REFERENCE) {
178 var dominator = value
179 val dominatedByNextNode = mutableListOf(key)
180 while (dominator != ValueHolder.NULL_REFERENCE) {
181 // If dominator is a node
182 if (nodeRetainedSizes.containsKey(dominator)) {
183 // Update dominator for all objects in the dominator path so far to directly point
184 // to it. We're compressing the dominator path to make this iteration faster and
185 // faster as we go through each entry.
186 dominatedByNextNode.forEach { objectId ->
187 dominated[objectId] = dominator
188 }
189 if (instanceSize == -1) {
190 instanceSize = computeSize(key)
191 }
192 // Update retained size for that node
193 val (currentRetainedSize, currentRetainedCount) = nodeRetainedSizes.getValue(
194 dominator
195 )
196 nodeRetainedSizes[dominator] =
197 (currentRetainedSize + instanceSize) to currentRetainedCount + 1
198 dominatedByNextNode.clear()
199 } else {
200 dominatedByNextNode += dominator
201 }
202 dominator = dominated[dominator]
203 }
204 // Update all dominator for all objects found in the dominator path after the last node
205 dominatedByNextNode.forEach { objectId ->
206 dominated[objectId] = ValueHolder.NULL_REFERENCE
207 }
208 }
209 }
210 })
211 dominated.release()
212
213 return nodeRetainedSizes
214 }
215 }
216