Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2019 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Eric Seckler | c165b87 | 2019-11-04 14:26:25 +0000 | [diff] [blame] | 17 | #ifndef SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ |
| 18 | #define SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 19 | |
| 20 | #include <inttypes.h> |
| 21 | #include <map> |
| 22 | #include <set> |
| 23 | #include <vector> |
| 24 | |
| 25 | // Implements two algorithms that walk a HeapGraph. |
| 26 | // a) Traverse all references from roots and mark the nodes as reachable. |
| 27 | // b) For each node, calculate two numbers: |
| 28 | // 1. retained: The number of bytes that are directly and indirectly |
| 29 | // referenced by the node. |
| 30 | // 2. uniquely retained: The number of bytes that are only retained through |
| 31 | // this object. If this object were destroyed, this many bytes would be |
| 32 | // freed up. |
| 33 | // |
| 34 | // The algorithm for b) is a modified Tarjan's algorithm. We use Tarjan's |
| 35 | // algorithm to find connected components. This is such that we break cycles |
| 36 | // that can exist in the retention graphs. All nodes within the cycle get |
| 37 | // assigned the same component. Then, most of the graph algorithm operates on |
| 38 | // these components. |
| 39 | // |
| 40 | // For instance, the below graph, which for simplicity does not contain any |
| 41 | // loops. |
| 42 | // Apart from nodes retaining / uniquely retaining themselves: |
| 43 | // a retains nothing |
| 44 | // a uniquely retains nothing |
| 45 | // |
| 46 | // b retains a |
| 47 | // b uniquely retains nothing |
| 48 | // |
| 49 | // c retains a |
| 50 | // c uniquely retains nothing |
| 51 | // |
| 52 | // d retains a, b, c |
| 53 | // d uniquely retains a, b, c |
| 54 | // |
| 55 | // a | |
| 56 | // ^^ | |
| 57 | // / \ | |
| 58 | // b c | |
| 59 | // ^ ^ | |
| 60 | // \ / | |
| 61 | // d | |
| 62 | // |
Florian Mayer | bd42039 | 2019-11-05 20:00:58 +0000 | [diff] [blame] | 63 | // The basic idea of the algorithm is to keep track of the number of unvisited |
| 64 | // nodes that retain the node. Nodes that have multiple parents get double |
| 65 | // counted; this is so we can always reduce the number of unvisited nodes by |
| 66 | // the number of edges from a node that retain a node. |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 67 | // |
Florian Mayer | bd42039 | 2019-11-05 20:00:58 +0000 | [diff] [blame] | 68 | // In the same graph: |
| 69 | // visiting a: 2 unvisited nodes retain a {b, c} |
| 70 | // visiting b: 2 unvisited nodes retain a {d, c} |
| 71 | // visiting c: 2 unvisited nodes retain a {d, d} |
| 72 | // visiting d: 0 unvisited nodes retain a |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 73 | // |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 74 | // |
| 75 | // A more complete example |
| 76 | // |
| 77 | // a | |
| 78 | // ^^ | |
| 79 | // / \ | |
| 80 | // b c | |
| 81 | // ^ ^ | |
| 82 | // \ / \ | |
| 83 | // d e | |
| 84 | // ^ ^ | |
| 85 | // \ / | |
| 86 | // f | |
| 87 | // |
Florian Mayer | bd42039 | 2019-11-05 20:00:58 +0000 | [diff] [blame] | 88 | // visiting a: 2 unvisited nodes retain a ({b, c}) |
| 89 | // visiting b: 2 unvisited nodes retain a ({d, c}) |
| 90 | // visiting c: 3 unvisited nodes retain a ({d, d, e}) |
| 91 | // visiting d: 2 unvisited nodes retain a ({f, e}) |
| 92 | // visiting e: 2 unvisited nodes retain a ({f, f}) |
| 93 | // visiting f: 0 unvisited nodes retain a |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 94 | |
| 95 | namespace perfetto { |
| 96 | namespace trace_processor { |
| 97 | |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 98 | class HeapGraphWalker { |
| 99 | public: |
| 100 | class Delegate { |
| 101 | public: |
| 102 | virtual ~Delegate(); |
| 103 | virtual void MarkReachable(int64_t row) = 0; |
| 104 | virtual void SetRetained(int64_t row, |
| 105 | int64_t retained, |
| 106 | int64_t unique_retained) = 0; |
| 107 | }; |
| 108 | |
| 109 | HeapGraphWalker(Delegate* delegate) : delegate_(delegate) {} |
| 110 | |
| 111 | void AddEdge(int64_t owner_row, int64_t owned_row); |
| 112 | void AddNode(int64_t row, uint64_t size); |
| 113 | |
| 114 | // Mark a a node as root. This marks all the nodes reachable from it as |
| 115 | // reachable. |
| 116 | void MarkRoot(int64_t row); |
| 117 | // Calculate the retained and unique retained size for each node. This |
| 118 | // includes nodes not reachable from roots. |
| 119 | void CalculateRetained(); |
| 120 | |
| 121 | private: |
| 122 | struct Node { |
Florian Mayer | fc830b8 | 2019-11-15 13:45:51 +0000 | [diff] [blame] | 123 | std::vector<Node*> children; |
| 124 | std::vector<Node*> parents; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 125 | uint64_t self_size = 0; |
| 126 | uint64_t retained_size = 0; |
| 127 | |
| 128 | int64_t row = 0; |
| 129 | uint64_t node_index = 0; |
| 130 | uint64_t lowlink = 0; |
| 131 | int64_t component = -1; |
Florian Mayer | bd42039 | 2019-11-05 20:00:58 +0000 | [diff] [blame] | 132 | |
| 133 | bool reachable = false; |
| 134 | bool on_stack = false; |
Florian Mayer | 3506367 | 2019-11-11 13:52:47 +0000 | [diff] [blame] | 135 | bool root = false; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 136 | }; |
| 137 | |
| 138 | struct Component { |
Florian Mayer | 3506367 | 2019-11-11 13:52:47 +0000 | [diff] [blame] | 139 | uint64_t self_size = 0; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 140 | uint64_t unique_retained_size = 0; |
Florian Mayer | 3506367 | 2019-11-11 13:52:47 +0000 | [diff] [blame] | 141 | uint64_t unique_retained_root_size = 0; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 142 | size_t incoming_edges = 0; |
| 143 | size_t orig_incoming_edges = 0; |
Florian Mayer | bd42039 | 2019-11-05 20:00:58 +0000 | [diff] [blame] | 144 | size_t pending_nodes = 0; |
| 145 | std::set<int64_t> children_components; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 146 | uint64_t lowlink = 0; |
Florian Mayer | 3506367 | 2019-11-11 13:52:47 +0000 | [diff] [blame] | 147 | |
| 148 | bool root = false; |
Florian Mayer | 04a93f2 | 2019-11-04 11:49:52 +0000 | [diff] [blame] | 149 | }; |
| 150 | |
| 151 | Node& GetNode(int64_t id) { return nodes_[static_cast<size_t>(id)]; } |
| 152 | |
| 153 | void FindSCC(Node*); |
| 154 | void FoundSCC(Node*); |
| 155 | int64_t RetainedSize(const Component&); |
| 156 | |
| 157 | // Make node and all transitive children as reachable. |
| 158 | void ReachableNode(Node*); |
| 159 | |
| 160 | std::vector<Component> components_; |
| 161 | std::vector<Node*> node_stack_; |
| 162 | uint64_t next_node_index_ = 1; |
| 163 | std::vector<Node> nodes_; |
| 164 | |
| 165 | Delegate* delegate_; |
| 166 | }; |
| 167 | |
| 168 | } // namespace trace_processor |
| 169 | } // namespace perfetto |
| 170 | |
Eric Seckler | c165b87 | 2019-11-04 14:26:25 +0000 | [diff] [blame] | 171 | #endif // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ |