1 /* 2 * Copyright (C) 2020 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 INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_ 18 #define INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_ 19 20 #include <sys/types.h> 21 22 #include <map> 23 #include <memory> 24 #include <set> 25 #include <string> 26 27 #include "perfetto/base/proc_utils.h" 28 #include "perfetto/ext/trace_processor/importers/memory_tracker/graph.h" 29 #include "perfetto/ext/trace_processor/importers/memory_tracker/raw_process_memory_node.h" 30 31 namespace perfetto { 32 namespace trace_processor { 33 34 class PERFETTO_EXPORT GraphProcessor { 35 public: 36 // This map does not own the pointers inside. 37 using RawMemoryNodeMap = 38 std::map<base::PlatformProcessId, std::unique_ptr<RawProcessMemoryNode>>; 39 40 static std::unique_ptr<GlobalNodeGraph> CreateMemoryGraph( 41 const RawMemoryNodeMap& process_nodes); 42 43 static void RemoveWeakNodesFromGraph(GlobalNodeGraph* global_graph); 44 45 static void AddOverheadsAndPropagateEntries(GlobalNodeGraph* global_graph); 46 47 static void CalculateSizesForGraph(GlobalNodeGraph* global_graph); 48 49 static std::map<base::PlatformProcessId, uint64_t> 50 ComputeSharedFootprintFromGraph(const GlobalNodeGraph& global_graph); 51 52 private: 53 friend class GraphProcessorTest; 54 55 static void CollectAllocatorNodes(const RawProcessMemoryNode& source, 56 GlobalNodeGraph* global_graph, 57 GlobalNodeGraph::Process* process_graph); 58 59 static void AddEdges(const RawProcessMemoryNode& source, 60 GlobalNodeGraph* global_graph); 61 62 static void MarkImplicitWeakParentsRecursively(GlobalNodeGraph::Node* node); 63 64 static void MarkWeakOwnersAndChildrenRecursively( 65 GlobalNodeGraph::Node* node, 66 std::set<const GlobalNodeGraph::Node*>* nodes); 67 68 static void RemoveWeakNodesRecursively(GlobalNodeGraph::Node* parent); 69 70 static void AssignTracingOverhead(const std::string& allocator, 71 GlobalNodeGraph* global_graph, 72 GlobalNodeGraph::Process* process); 73 74 static GlobalNodeGraph::Node::Entry AggregateNumericWithNameForNode( 75 GlobalNodeGraph::Node* node, 76 const std::string& name); 77 78 static void AggregateNumericsRecursively(GlobalNodeGraph::Node* node); 79 80 static void PropagateNumericsAndDiagnosticsRecursively( 81 GlobalNodeGraph::Node* node); 82 83 static base::Optional<uint64_t> AggregateSizeForDescendantNode( 84 GlobalNodeGraph::Node* root, 85 GlobalNodeGraph::Node* descendant); 86 87 static void CalculateSizeForNode(GlobalNodeGraph::Node* node); 88 89 /** 90 * Calculate not-owned and not-owning sub-sizes of a memory allocator node 91 * from its children's (sub-)sizes. 92 * 93 * Not-owned sub-size refers to the aggregated memory of all children which 94 * is not owned by other MADs. Conversely, not-owning sub-size is the 95 * aggregated memory of all children which do not own another MAD. The 96 * diagram below illustrates these two concepts: 97 * 98 * ROOT 1 ROOT 2 99 * size: 4 size: 5 100 * not-owned sub-size: 4 not-owned sub-size: 1 (!) 101 * not-owning sub-size: 0 (!) not-owning sub-size: 5 102 * 103 * ^ ^ 104 * | | 105 * 106 * PARENT 1 ===== owns =====> PARENT 2 107 * size: 4 size: 5 108 * not-owned sub-size: 4 not-owned sub-size: 5 109 * not-owning sub-size: 4 not-owning sub-size: 5 110 * 111 * ^ ^ 112 * | | 113 * 114 * CHILD 1 CHILD 2 115 * size [given]: 4 size [given]: 5 116 * not-owned sub-size: 4 not-owned sub-size: 5 117 * not-owning sub-size: 4 not-owning sub-size: 5 118 * 119 * This method assumes that (1) the size of the node, its children, and its 120 * owners [see calculateSizes()] and (2) the not-owned and not-owning 121 * sub-sizes of both the children and owners of the node have already been 122 * calculated [depth-first post-order traversal]. 123 */ 124 static void CalculateNodeSubSizes(GlobalNodeGraph::Node* node); 125 126 /** 127 * Calculate owned and owning coefficients of a memory allocator node and 128 * its owners. 129 * 130 * The owning coefficient refers to the proportion of a node's not-owning 131 * sub-size which is attributed to the node (only relevant to owning MADs). 132 * Conversely, the owned coefficient is the proportion of a node's 133 * not-owned sub-size, which is attributed to it (only relevant to owned 134 * MADs). 135 * 136 * The not-owned size of the owned node is split among its owners in the 137 * order of the ownership importance as demonstrated by the following 138 * example: 139 * 140 * memory allocator nodes 141 * OWNED OWNER1 OWNER2 OWNER3 OWNER4 142 * not-owned sub-size [given] 10 - - - - 143 * not-owning sub-size [given] - 6 7 5 8 144 * importance [given] - 2 2 1 0 145 * attributed not-owned sub-size 2 - - - - 146 * attributed not-owning sub-size - 3 4 0 1 147 * owned coefficient 2/10 - - - - 148 * owning coefficient - 3/6 4/7 0/5 1/8 149 * 150 * Explanation: Firstly, 6 bytes are split equally among OWNER1 and OWNER2 151 * (highest importance). OWNER2 owns one more byte, so its attributed 152 * not-owning sub-size is 6/2 + 1 = 4 bytes. OWNER3 is attributed no size 153 * because it is smaller than the owners with higher priority. However, 154 * OWNER4 is larger, so it's attributed the difference 8 - 7 = 1 byte. 155 * Finally, 2 bytes remain unattributed and are hence kept in the OWNED 156 * node as attributed not-owned sub-size. The coefficients are then 157 * directly calculated as fractions of the sub-sizes and corresponding 158 * attributed sub-sizes. 159 * 160 * Note that we always assume that all ownerships of a node overlap (e.g. 161 * OWNER3 is subsumed by both OWNER1 and OWNER2). Hence, the table could 162 * be alternatively represented as follows: 163 * 164 * owned memory range 165 * 0 1 2 3 4 5 6 7 8 9 10 166 * Priority 2 | OWNER1 + OWNER2 (split) | OWNER2 | 167 * Priority 1 | (already attributed) | 168 * Priority 0 | - - - (already attributed) - - - | OWNER4 | 169 * Remainder | - - - - - (already attributed) - - - - - - | OWNED | 170 * 171 * This method assumes that (1) the size of the node [see calculateSizes()] 172 * and (2) the not-owned size of the node and not-owning sub-sizes of its 173 * owners [see the first step of calculateEffectiveSizes()] have already 174 * been calculated. Note that the method doesn't make any assumptions about 175 * the order in which nodes are visited. 176 */ 177 static void CalculateNodeOwnershipCoefficient(GlobalNodeGraph::Node* node); 178 179 /** 180 * Calculate cumulative owned and owning coefficients of a memory allocator 181 * node from its (non-cumulative) owned and owning coefficients and the 182 * cumulative coefficients of its parent and/or owned node. 183 * 184 * The cumulative coefficients represent the total effect of all 185 * (non-strict) ancestor ownerships on a memory allocator node. The 186 * cumulative owned coefficient of a MAD can be calculated simply as: 187 * 188 * cumulativeOwnedC(M) = ownedC(M) * cumulativeOwnedC(parent(M)) 189 * 190 * This reflects the assumption that if a parent of a child MAD is 191 * (partially) owned, then the parent's owner also indirectly owns (a part 192 * of) the child MAD. 193 * 194 * The cumulative owning coefficient of a MAD depends on whether the MAD 195 * owns another node: 196 * 197 * [if M doesn't own another MAD] 198 * / cumulativeOwningC(parent(M)) 199 * cumulativeOwningC(M) = 200 * \ [if M owns another MAD] 201 * owningC(M) * cumulativeOwningC(owned(M)) 202 * 203 * The reasoning behind the first case is similar to the one for cumulative 204 * owned coefficient above. The only difference is that we don't need to 205 * include the node's (non-cumulative) owning coefficient because it is 206 * implicitly 1. 207 * 208 * The formula for the second case is derived as follows: Since the MAD 209 * owns another node, its memory is not included in its parent's not-owning 210 * sub-size and hence shouldn't be affected by the parent's corresponding 211 * cumulative coefficient. Instead, the MAD indirectly owns everything 212 * owned by its owned node (and so it should be affected by the 213 * corresponding coefficient). 214 * 215 * Note that undefined coefficients (and coefficients of non-existent 216 * nodes) are implicitly assumed to be 1. 217 * 218 * This method assumes that (1) the size of the node [see calculateSizes()], 219 * (2) the (non-cumulative) owned and owning coefficients of the node [see 220 * the second step of calculateEffectiveSizes()], and (3) the cumulative 221 * coefficients of the node's parent and owned MADs (if present) 222 * [depth-first pre-order traversal] have already been calculated. 223 */ 224 static void CalculateNodeCumulativeOwnershipCoefficient( 225 GlobalNodeGraph::Node* node); 226 227 /** 228 * Calculate the effective size of a memory allocator node. 229 * 230 * In order to simplify the (already complex) calculation, we use the fact 231 * that effective size is cumulative (unlike regular size), i.e. the 232 * effective size of a non-leaf node is equal to the sum of effective sizes 233 * of its children. The effective size of a leaf MAD is calculated as: 234 * 235 * effectiveSize(M) = size(M) * cumulativeOwningC(M) * cumulativeOwnedC(M) 236 * 237 * This method assumes that (1) the size of the node and its children [see 238 * calculateSizes()] and (2) the cumulative owning and owned coefficients 239 * of the node (if it's a leaf node) [see the third step of 240 * calculateEffectiveSizes()] or the effective sizes of its children (if 241 * it's a non-leaf node) [depth-first post-order traversal] have already 242 * been calculated. 243 */ 244 static void CalculateNodeEffectiveSize(GlobalNodeGraph::Node* node); 245 }; 246 247 } // namespace trace_processor 248 } // namespace perfetto 249 250 #endif // INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_ 251