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 <optional> 22 #include <set> 23 #include <utility> 24 #include <vector> 25 26 #include "perfetto/base/flat_set.h" 27 #include "perfetto/ext/base/string_view.h" 28 29 #include "protos/perfetto/trace/profiling/heap_graph.pbzero.h" 30 #include "src/trace_processor/storage/trace_storage.h" 31 #include "src/trace_processor/tables/profiler_tables_py.h" 32 #include "src/trace_processor/types/trace_processor_context.h" 33 34 namespace perfetto { 35 namespace trace_processor { 36 37 class TraceProcessorContext; 38 39 struct NormalizedType { 40 base::StringView name; 41 bool is_static_class; 42 size_t number_of_arrays; 43 }; 44 45 struct PathFromRoot { 46 static constexpr size_t kRoot = 0; 47 struct Node { 48 uint32_t depth = 0; 49 // Invariant: parent_id < id of this node. 50 size_t parent_id = 0; 51 int64_t size = 0; 52 int64_t count = 0; 53 StringId class_name_id = {}; 54 std::map<StringId, size_t> children; 55 }; 56 std::vector<Node> nodes{Node{}}; 57 std::set<tables::HeapGraphObjectTable::Id> visited; 58 }; 59 60 std::optional<base::StringView> GetStaticClassTypeName(base::StringView type); 61 size_t NumberOfArrays(base::StringView type); 62 NormalizedType GetNormalizedType(base::StringView type); 63 base::StringView NormalizeTypeName(base::StringView type); 64 std::string DenormalizeTypeName(NormalizedType normalized, 65 base::StringView deobfuscated_type_name); 66 67 class HeapGraphTracker : public Destructible { 68 public: 69 struct SourceObject { 70 // All ids in this are in the trace iid space, not in the trace processor 71 // id space. 72 uint64_t object_id = 0; 73 uint64_t self_size = 0; 74 uint64_t type_id = 0; 75 protos::pbzero::HeapGraphObject::HeapType heap_type = 76 protos::pbzero::HeapGraphObject::HEAP_TYPE_UNKNOWN; 77 78 std::vector<uint64_t> field_name_ids; 79 std::vector<uint64_t> referred_objects; 80 81 // If this object is an instance of `libcore.util.NativeAllocationRegistry`, 82 // this is the value of its `size` field. 83 std::optional<int64_t> native_allocation_registry_size; 84 }; 85 86 struct SourceRoot { 87 protos::pbzero::HeapGraphRoot::Type root_type; 88 std::vector<uint64_t> object_ids; 89 }; 90 91 explicit HeapGraphTracker(TraceStorage* storage); 92 GetOrCreate(TraceProcessorContext * context)93 static HeapGraphTracker* GetOrCreate(TraceProcessorContext* context) { 94 if (!context->heap_graph_tracker) { 95 context->heap_graph_tracker.reset( 96 new HeapGraphTracker(context->storage.get())); 97 } 98 return static_cast<HeapGraphTracker*>(context->heap_graph_tracker.get()); 99 } 100 101 void AddRoot(uint32_t seq_id, UniquePid upid, int64_t ts, SourceRoot root); 102 void AddObject(uint32_t seq_id, UniquePid upid, int64_t ts, SourceObject obj); 103 void AddInternedType(uint32_t seq_id, 104 uint64_t intern_id, 105 StringId strid, 106 std::optional<uint64_t> location_id, 107 uint64_t object_size, 108 std::vector<uint64_t> field_name_ids, 109 uint64_t superclass_id, 110 uint64_t classloader_id, 111 bool no_fields, 112 protos::pbzero::HeapGraphType::Kind kind); 113 void AddInternedFieldName(uint32_t seq_id, 114 uint64_t intern_id, 115 base::StringView str); 116 void AddInternedLocationName(uint32_t seq_id, 117 uint64_t intern_id, 118 StringId str); 119 void FinalizeProfile(uint32_t seq); 120 void FinalizeAllProfiles(); 121 void SetPacketIndex(uint32_t seq_id, uint64_t index); 122 123 ~HeapGraphTracker() override; 124 RowsForType(std::optional<StringId> package_name,StringId type_name)125 const std::vector<tables::HeapGraphClassTable::RowNumber>* RowsForType( 126 std::optional<StringId> package_name, 127 StringId type_name) const { 128 auto it = class_to_rows_.find(std::make_pair(package_name, type_name)); 129 if (it == class_to_rows_.end()) 130 return nullptr; 131 return &it->second; 132 } 133 RowsForField(StringId field_name)134 const std::vector<tables::HeapGraphReferenceTable::RowNumber>* RowsForField( 135 StringId field_name) const { 136 return field_to_rows_.Find(field_name); 137 } 138 139 std::unique_ptr<tables::ExperimentalFlamegraphTable> BuildFlamegraph( 140 const int64_t current_ts, 141 const UniquePid current_upid); 142 GetLastObjectId(uint32_t seq_id)143 uint64_t GetLastObjectId(uint32_t seq_id) { 144 return GetOrCreateSequence(seq_id).last_object_id; 145 } 146 GetLastObjectHeapType(uint32_t seq_id)147 perfetto::protos::pbzero::HeapGraphObject::HeapType GetLastObjectHeapType( 148 uint32_t seq_id) { 149 return GetOrCreateSequence(seq_id).last_heap_type; 150 } 151 152 private: 153 struct InternedField { 154 StringId name; 155 StringId type_name; 156 }; 157 struct InternedType { 158 StringId name; 159 std::optional<uint64_t> location_id; 160 uint64_t object_size; 161 std::vector<uint64_t> field_name_ids; 162 uint64_t superclass_id; 163 bool no_fields; 164 uint64_t classloader_id; 165 protos::pbzero::HeapGraphType::Kind kind; 166 }; 167 struct SequenceState { 168 UniquePid current_upid = 0; 169 int64_t current_ts = 0; 170 uint64_t last_object_id = 0; 171 protos::pbzero::HeapGraphObject::HeapType last_heap_type = 172 protos::pbzero::HeapGraphObject::HEAP_TYPE_UNKNOWN; 173 std::vector<SourceRoot> current_roots; 174 175 // Note: the below maps are a mix of std::map and base::FlatHashMap because 176 // of the incremental evolution of this code (i.e. when the code was written 177 // FlatHashMap did not exist and pieces were migrated as they were found to 178 // be performance problems). 179 // 180 // In the future, likely all of these should be base::FlatHashMap. This 181 // was not done when the first use of base::FlatHashMap happened because 182 // there are some subtle cases where base::FlatHashMap *regresses* perf and 183 // there was not time for investigation. 184 185 std::map<uint64_t, InternedType> interned_types; 186 std::map<uint64_t, StringId> interned_location_names; 187 base::FlatHashMap<uint64_t, tables::HeapGraphObjectTable::RowNumber> 188 object_id_to_db_row; 189 base::FlatHashMap<uint64_t, tables::HeapGraphClassTable::RowNumber> 190 type_id_to_db_row; 191 std::map<uint64_t, std::vector<tables::HeapGraphReferenceTable::RowNumber>> 192 references_for_field_name_id; 193 base::FlatHashMap<uint64_t, InternedField> interned_fields; 194 std::map<tables::HeapGraphClassTable::Id, 195 std::vector<tables::HeapGraphObjectTable::RowNumber>> 196 deferred_reference_objects_for_type_; 197 std::optional<uint64_t> prev_index; 198 // For most objects, we need not store the size in the object's message 199 // itself, because all instances of the type have the same type. In this 200 // case, we defer setting self_size in the table until we process the class 201 // message in FinalizeProfile. 202 std::map<tables::HeapGraphClassTable::Id, 203 std::vector<tables::HeapGraphObjectTable::RowNumber>> 204 deferred_size_objects_for_type_; 205 // Contains the value of the "size" field for each 206 // "libcore.util.NativeAllocationRegistry" object. 207 std::map<tables::HeapGraphObjectTable::Id, int64_t> nar_size_by_obj_id; 208 bool truncated = false; 209 }; 210 211 SequenceState& GetOrCreateSequence(uint32_t seq_id); 212 tables::HeapGraphObjectTable::RowReference GetOrInsertObject( 213 SequenceState* sequence_state, 214 uint64_t object_id); 215 tables::HeapGraphClassTable::RowReference GetOrInsertType( 216 SequenceState* sequence_state, 217 uint64_t type_id); 218 bool SetPidAndTimestamp(SequenceState* seq, UniquePid upid, int64_t ts); 219 void PopulateSuperClasses(const SequenceState& seq); 220 InternedType* GetSuperClass(SequenceState* sequence_state, 221 const InternedType* current_type); 222 bool IsTruncated(UniquePid upid, int64_t ts); 223 StringId InternRootTypeString(protos::pbzero::HeapGraphRoot::Type); 224 StringId InternTypeKindString(protos::pbzero::HeapGraphType::Kind); 225 226 // Returns the object pointed to by `field` in `obj`. 227 std::optional<tables::HeapGraphObjectTable::Id> GetReferenceByFieldName( 228 tables::HeapGraphObjectTable::Id obj, 229 StringId field); 230 231 // Populates HeapGraphObject::native_size by walking the graph for 232 // `seq`. 233 // 234 // This should be called only once (it is not idempotent) per seq, after the 235 // all the other tables have been fully populated. 236 void PopulateNativeSize(const SequenceState& seq); 237 238 void GetChildren(tables::HeapGraphObjectTable::RowReference, 239 std::vector<tables::HeapGraphObjectTable::Id>&); 240 void MarkRoot(tables::HeapGraphObjectTable::RowReference, StringId type); 241 size_t RankRoot(StringId type); 242 void UpdateShortestPaths(tables::HeapGraphObjectTable::RowReference row_ref); 243 void FindPathFromRoot(tables::HeapGraphObjectTable::RowReference, 244 PathFromRoot* path); 245 246 TraceStorage* const storage_; 247 std::map<uint32_t, SequenceState> sequence_state_; 248 249 std::map<std::pair<std::optional<StringId>, StringId>, 250 std::vector<tables::HeapGraphClassTable::RowNumber>> 251 class_to_rows_; 252 base::FlatHashMap<StringId, 253 std::vector<tables::HeapGraphReferenceTable::RowNumber>> 254 field_to_rows_; 255 256 std::map<std::pair<std::optional<StringId>, StringId>, StringId> 257 deobfuscation_mapping_; 258 std::map<std::pair<UniquePid, int64_t>, 259 std::set<tables::HeapGraphObjectTable::RowNumber>> 260 roots_; 261 std::set<std::pair<UniquePid, int64_t>> truncated_graphs_; 262 263 StringId cleaner_thunk_str_id_; 264 StringId referent_str_id_; 265 StringId cleaner_thunk_this0_str_id_; 266 StringId native_size_str_id_; 267 StringId cleaner_next_str_id_; 268 269 std::array<StringId, 15> root_type_string_ids_ = {}; 270 static_assert(protos::pbzero::HeapGraphRoot_Type_MIN == 0); 271 static_assert(protos::pbzero::HeapGraphRoot_Type_MAX + 1 == 272 std::tuple_size<decltype(root_type_string_ids_)>{}); 273 274 std::array<StringId, 12> type_kind_string_ids_ = {}; 275 static_assert(protos::pbzero::HeapGraphType_Kind_MIN == 0); 276 static_assert(protos::pbzero::HeapGraphType_Kind_MAX + 1 == 277 std::tuple_size<decltype(type_kind_string_ids_)>{}); 278 }; 279 280 } // namespace trace_processor 281 } // namespace perfetto 282 283 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_TRACKER_H_ 284