xref: /aosp_15_r20/external/perfetto/src/trace_processor/importers/proto/heap_graph_tracker.h (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc)
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