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 17 #ifndef SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ 18 #define SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ 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 // 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. 67 // 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 73 // 74 // 75 // A more complete example 76 // 77 // a | 78 // ^^ | 79 // / \ | 80 // b c | 81 // ^ ^ | 82 // \ / \ | 83 // d e | 84 // ^ ^ | 85 // \ / | 86 // f | 87 // 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 94 95 namespace perfetto { 96 namespace trace_processor { 97 98 class HeapGraphWalker { 99 public: 100 using ClassNameId = uint32_t; 101 102 struct PathFromRoot { 103 static constexpr size_t kRoot = 0; 104 struct Node { 105 uint32_t depth = 0; 106 // Invariant: parent_id < id of this node. 107 size_t parent_id = 0; 108 uint64_t size = 0; 109 uint64_t count = 0; 110 ClassNameId class_name = 0; 111 std::map<ClassNameId, size_t> children; 112 }; 113 std::vector<Node> nodes{Node{}}; 114 }; 115 116 class Delegate { 117 public: 118 virtual ~Delegate(); 119 virtual void MarkReachable(int64_t row) = 0; 120 virtual void SetRetained(int64_t row, 121 int64_t retained, 122 int64_t unique_retained) = 0; 123 }; 124 HeapGraphWalker(Delegate * delegate)125 HeapGraphWalker(Delegate* delegate) : delegate_(delegate) {} 126 127 void AddEdge(int64_t owner_row, int64_t owned_row); AddNode(int64_t row,uint64_t size)128 void AddNode(int64_t row, uint64_t size) { AddNode(row, size, 0); } 129 void AddNode(int64_t row, uint64_t size, ClassNameId class_name); 130 131 // Mark a a node as root. This marks all the nodes reachable from it as 132 // reachable. 133 void MarkRoot(int64_t row); 134 // Calculate the retained and unique retained size for each node. This 135 // includes nodes not reachable from roots. 136 void CalculateRetained(); 137 138 PathFromRoot FindPathsFromRoot(); 139 140 private: 141 struct Node { 142 std::vector<Node*> children; 143 std::vector<Node*> parents; 144 uint64_t self_size = 0; 145 uint64_t retained_size = 0; 146 147 int64_t row = 0; 148 uint64_t node_index = 0; 149 uint64_t lowlink = 0; 150 int64_t component = -1; 151 152 uint32_t class_name = 0; 153 int32_t distance_to_root = -1; 154 155 bool on_stack = false; 156 bool find_paths_from_root_visited = false; 157 rootNode158 bool root() { return distance_to_root == 0; } reachableNode159 bool reachable() { return distance_to_root >= 0; } 160 }; 161 162 struct Component { 163 uint64_t self_size = 0; 164 uint64_t unique_retained_size = 0; 165 uint64_t unique_retained_root_size = 0; 166 size_t incoming_edges = 0; 167 size_t orig_incoming_edges = 0; 168 size_t pending_nodes = 0; 169 std::set<int64_t> children_components; 170 uint64_t lowlink = 0; 171 172 bool root = false; 173 }; 174 GetNode(int64_t id)175 Node& GetNode(int64_t id) { return nodes_[static_cast<size_t>(id)]; } 176 177 void FindSCC(Node*); 178 void FoundSCC(Node*); 179 int64_t RetainedSize(const Component&); 180 181 void FindPathFromRoot(Node* n, PathFromRoot* path); 182 183 std::vector<Component> components_; 184 std::vector<Node*> node_stack_; 185 uint64_t next_node_index_ = 1; 186 std::vector<Node> nodes_; 187 188 std::vector<Node*> roots_; 189 190 Delegate* delegate_; 191 }; 192 193 } // namespace trace_processor 194 } // namespace perfetto 195 196 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_ 197