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