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_TRACKER_H_ 18 #define SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_TRACKER_H_ 19 20 #include <map> 21 #include <set> 22 #include <utility> 23 #include <vector> 24 25 #include "perfetto/ext/base/optional.h" 26 #include "perfetto/ext/base/string_view.h" 27 28 #include "protos/perfetto/trace/profiling/heap_graph.pbzero.h" 29 #include "src/trace_processor/storage/trace_storage.h" 30 #include "src/trace_processor/types/trace_processor_context.h" 31 32 namespace perfetto { 33 namespace trace_processor { 34 35 class TraceProcessorContext; 36 37 struct NormalizedType { 38 base::StringView name; 39 bool is_static_class; 40 size_t number_of_arrays; 41 }; 42 43 struct PathFromRoot { 44 static constexpr size_t kRoot = 0; 45 struct Node { 46 uint32_t depth = 0; 47 // Invariant: parent_id < id of this node. 48 size_t parent_id = 0; 49 int64_t size = 0; 50 int64_t count = 0; 51 StringId class_name_id = {}; 52 std::map<StringId, size_t> children; 53 }; 54 std::vector<Node> nodes{Node{}}; 55 std::set<tables::HeapGraphObjectTable::Id> visited; 56 }; 57 58 void MarkRoot(TraceStorage* s, 59 tables::HeapGraphObjectTable::Id id, 60 StringPool::Id type); 61 void FindPathFromRoot(TraceStorage* storage, 62 tables::HeapGraphObjectTable::Id id, 63 PathFromRoot* path); 64 65 base::Optional<base::StringView> GetStaticClassTypeName(base::StringView type); 66 size_t NumberOfArrays(base::StringView type); 67 NormalizedType GetNormalizedType(base::StringView type); 68 base::StringView NormalizeTypeName(base::StringView type); 69 std::string DenormalizeTypeName(NormalizedType normalized, 70 base::StringView deobfuscated_type_name); 71 72 class HeapGraphTracker : public Destructible { 73 public: 74 struct SourceObject { 75 // All ids in this are in the trace iid space, not in the trace processor 76 // id space. 77 uint64_t object_id = 0; 78 uint64_t self_size = 0; 79 uint64_t type_id = 0; 80 81 std::vector<uint64_t> field_name_ids; 82 std::vector<uint64_t> referred_objects; 83 84 // If this object is an instance of `libcore.util.NativeAllocationRegistry`, 85 // this is the value of its `size` field. 86 base::Optional<int64_t> native_allocation_registry_size; 87 }; 88 89 struct SourceRoot { 90 StringPool::Id root_type; 91 std::vector<uint64_t> object_ids; 92 }; 93 94 explicit HeapGraphTracker(TraceProcessorContext* context); 95 GetOrCreate(TraceProcessorContext * context)96 static HeapGraphTracker* GetOrCreate(TraceProcessorContext* context) { 97 if (!context->heap_graph_tracker) { 98 context->heap_graph_tracker.reset(new HeapGraphTracker(context)); 99 } 100 return static_cast<HeapGraphTracker*>(context->heap_graph_tracker.get()); 101 } 102 103 void AddRoot(uint32_t seq_id, UniquePid upid, int64_t ts, SourceRoot root); 104 void AddObject(uint32_t seq_id, UniquePid upid, int64_t ts, SourceObject obj); 105 void AddInternedType(uint32_t seq_id, 106 uint64_t intern_id, 107 StringPool::Id strid, 108 base::Optional<uint64_t> location_id, 109 uint64_t object_size, 110 std::vector<uint64_t> field_name_ids, 111 uint64_t superclass_id, 112 uint64_t classloader_id, 113 bool no_fields, 114 StringPool::Id kind); 115 void AddInternedFieldName(uint32_t seq_id, 116 uint64_t intern_id, 117 base::StringView str); 118 void AddInternedLocationName(uint32_t seq_id, 119 uint64_t intern_id, 120 StringPool::Id str); 121 void FinalizeProfile(uint32_t seq); 122 void FinalizeAllProfiles(); 123 void SetPacketIndex(uint32_t seq_id, uint64_t index); 124 125 ~HeapGraphTracker() override; 126 RowsForType(base::Optional<StringPool::Id> package_name,StringPool::Id type_name)127 const std::vector<tables::HeapGraphClassTable::Id>* RowsForType( 128 base::Optional<StringPool::Id> package_name, 129 StringPool::Id type_name) const { 130 auto it = class_to_rows_.find(std::make_pair(package_name, type_name)); 131 if (it == class_to_rows_.end()) 132 return nullptr; 133 return &it->second; 134 } 135 RowsForField(StringPool::Id field_name)136 const std::vector<int64_t>* RowsForField(StringPool::Id field_name) const { 137 auto it = field_to_rows_.find(field_name); 138 if (it == field_to_rows_.end()) 139 return nullptr; 140 return &it->second; 141 } 142 143 std::unique_ptr<tables::ExperimentalFlamegraphNodesTable> BuildFlamegraph( 144 const int64_t current_ts, 145 const UniquePid current_upid); 146 GetLastObjectId(uint32_t seq_id)147 uint64_t GetLastObjectId(uint32_t seq_id) { 148 return GetOrCreateSequence(seq_id).last_object_id; 149 } 150 151 private: 152 struct InternedField { 153 StringPool::Id name; 154 StringPool::Id type_name; 155 }; 156 struct InternedType { 157 StringPool::Id name; 158 base::Optional<uint64_t> location_id; 159 uint64_t object_size; 160 std::vector<uint64_t> field_name_ids; 161 uint64_t superclass_id; 162 bool no_fields; 163 uint64_t classloader_id; 164 StringPool::Id kind; 165 }; 166 struct SequenceState { 167 UniquePid current_upid = 0; 168 int64_t current_ts = 0; 169 uint64_t last_object_id = 0; 170 std::vector<SourceRoot> current_roots; 171 std::map<uint64_t, InternedType> interned_types; 172 std::map<uint64_t, StringPool::Id> interned_location_names; 173 std::map<uint64_t, tables::HeapGraphObjectTable::Id> object_id_to_db_id; 174 std::map<uint64_t, tables::HeapGraphClassTable::Id> type_id_to_db_id; 175 std::map<uint64_t, std::vector<tables::HeapGraphReferenceTable::Id>> 176 references_for_field_name_id; 177 std::map<uint64_t, InternedField> interned_fields; 178 std::map<tables::HeapGraphClassTable::Id, 179 std::vector<tables::HeapGraphObjectTable::Id>> 180 deferred_reference_objects_for_type_; 181 base::Optional<uint64_t> prev_index; 182 // For most objects, we need not store the size in the object's message 183 // itself, because all instances of the type have the same type. In this 184 // case, we defer setting self_size in the table until we process the class 185 // message in FinalizeProfile. 186 std::map<tables::HeapGraphClassTable::Id, 187 std::vector<tables::HeapGraphObjectTable::Id>> 188 deferred_size_objects_for_type_; 189 // Contains the value of the "size" field for each 190 // "libcore.util.NativeAllocationRegistry" object. 191 std::map<tables::HeapGraphObjectTable::Id, int64_t> nar_size_by_obj_id; 192 bool truncated = false; 193 }; 194 195 SequenceState& GetOrCreateSequence(uint32_t seq_id); 196 tables::HeapGraphObjectTable::Id GetOrInsertObject( 197 SequenceState* sequence_state, 198 uint64_t object_id); 199 tables::HeapGraphClassTable::Id GetOrInsertType(SequenceState* sequence_state, 200 uint64_t type_id); 201 bool SetPidAndTimestamp(SequenceState* seq, UniquePid upid, int64_t ts); 202 void PopulateSuperClasses(const SequenceState& seq); 203 InternedType* GetSuperClass(SequenceState* sequence_state, 204 const InternedType* current_type); 205 bool IsTruncated(UniquePid upid, int64_t ts); 206 207 // Returns the object pointed to by `field` in `obj`. 208 base::Optional<tables::HeapGraphObjectTable::Id> GetReferenceByFieldName( 209 tables::HeapGraphObjectTable::Id obj, 210 StringPool::Id field); 211 212 // Populates HeapGraphObject::native_size by walking the graph for 213 // `seq`. 214 // 215 // This should be called only once (it is not idempotent) per seq, after the 216 // all the other tables have been fully populated. 217 void PopulateNativeSize(const SequenceState& seq); 218 219 TraceProcessorContext* const context_; 220 std::map<uint32_t, SequenceState> sequence_state_; 221 222 std::map<std::pair<base::Optional<StringPool::Id>, StringPool::Id>, 223 std::vector<tables::HeapGraphClassTable::Id>> 224 class_to_rows_; 225 std::map<StringPool::Id, std::vector<int64_t>> field_to_rows_; 226 227 std::map<std::pair<base::Optional<StringPool::Id>, StringPool::Id>, 228 StringPool::Id> 229 deobfuscation_mapping_; 230 std::map<std::pair<UniquePid, int64_t>, 231 std::set<tables::HeapGraphObjectTable::Id>> 232 roots_; 233 std::set<std::pair<UniquePid, int64_t>> truncated_graphs_; 234 235 StringPool::Id cleaner_thunk_str_id_; 236 StringPool::Id referent_str_id_; 237 StringPool::Id cleaner_thunk_this0_str_id_; 238 StringPool::Id native_size_str_id_; 239 StringPool::Id cleaner_next_str_id_; 240 }; 241 242 } // namespace trace_processor 243 } // namespace perfetto 244 245 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_TRACKER_H_ 246