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_STACK_PROFILE_TRACKER_H_
18 #define SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_STACK_PROFILE_TRACKER_H_
19 
20 #include <deque>
21 #include <unordered_map>
22 
23 #include "perfetto/ext/base/optional.h"
24 
25 #include "protos/perfetto/trace/profiling/profile_common.pbzero.h"
26 #include "protos/perfetto/trace/profiling/profile_packet.pbzero.h"
27 #include "src/trace_processor/storage/trace_storage.h"
28 #include "src/trace_processor/tables/profiler_tables.h"
29 
30 template <>
31 struct std::hash<std::pair<uint32_t, int64_t>> {
32   using argument_type = std::pair<uint32_t, int64_t>;
33   using result_type = size_t;
34 
35   result_type operator()(const argument_type& p) const {
36     return std::hash<uint32_t>{}(p.first) ^ std::hash<int64_t>{}(p.second);
37   }
38 };
39 
40 template <>
41 struct std::hash<std::pair<uint32_t, perfetto::trace_processor::CallsiteId>> {
42   using argument_type =
43       std::pair<uint32_t, perfetto::trace_processor::CallsiteId>;
44   using result_type = size_t;
45 
46   result_type operator()(const argument_type& p) const {
47     return std::hash<uint32_t>{}(p.first) ^
48            std::hash<uint32_t>{}(p.second.value);
49   }
50 };
51 
52 template <>
53 struct std::hash<std::pair<uint32_t, perfetto::trace_processor::MappingId>> {
54   using argument_type =
55       std::pair<uint32_t, perfetto::trace_processor::MappingId>;
56   using result_type = size_t;
57 
58   result_type operator()(const argument_type& p) const {
59     return std::hash<uint32_t>{}(p.first) ^
60            std::hash<uint32_t>{}(p.second.value);
61   }
62 };
63 
64 template <>
65 struct std::hash<std::pair<uint32_t, perfetto::trace_processor::FrameId>> {
66   using argument_type = std::pair<uint32_t, perfetto::trace_processor::FrameId>;
67   using result_type = size_t;
68 
69   result_type operator()(const argument_type& p) const {
70     return std::hash<uint32_t>{}(p.first) ^
71            std::hash<uint32_t>{}(p.second.value);
72   }
73 };
74 
75 template <>
76 struct std::hash<std::vector<uint64_t>> {
77   using argument_type = std::vector<uint64_t>;
78   using result_type = size_t;
79 
80   result_type operator()(const argument_type& p) const {
81     size_t h = 0u;
82     for (auto v : p)
83       h = h ^ std::hash<uint64_t>{}(v);
84     return h;
85   }
86 };
87 
88 namespace perfetto {
89 namespace trace_processor {
90 
91 struct NameInPackage {
92   StringId name;
93   StringId package;
94 
95   bool operator<(const NameInPackage& b) const {
96     return std::tie(name, package) < std::tie(b.name, b.package);
97   }
98 };
99 
100 class TraceProcessorContext;
101 
102 class GlobalStackProfileTracker {
103  public:
104   std::vector<MappingId> FindMappingRow(StringId name,
105                                         StringId build_id) const {
106     auto it = stack_profile_mapping_index_.find(std::make_pair(name, build_id));
107     if (it == stack_profile_mapping_index_.end())
108       return {};
109     return it->second;
110   }
111 
112   void InsertMappingId(StringId name, StringId build_id, MappingId row) {
113     auto pair = std::make_pair(name, build_id);
114     stack_profile_mapping_index_[pair].emplace_back(row);
115   }
116 
117   std::vector<FrameId> FindFrameIds(MappingId mapping_row,
118                                     uint64_t rel_pc) const {
119     auto it =
120         stack_profile_frame_index_.find(std::make_pair(mapping_row, rel_pc));
121     if (it == stack_profile_frame_index_.end())
122       return {};
123     return it->second;
124   }
125 
126   void InsertFrameRow(MappingId mapping_row, uint64_t rel_pc, FrameId row) {
127     auto pair = std::make_pair(mapping_row, rel_pc);
128     stack_profile_frame_index_[pair].emplace_back(row);
129   }
130 
131   const std::vector<tables::StackProfileFrameTable::Id>* JavaFramesForName(
132       NameInPackage name) {
133     auto it = java_frames_for_name_.find(name);
134     if (it == java_frames_for_name_.end())
135       return nullptr;
136     return &it->second;
137   }
138 
139   void InsertJavaFrameForName(NameInPackage name,
140                               tables::StackProfileFrameTable::Id id) {
141     java_frames_for_name_[name].push_back(id);
142   }
143 
144  private:
145   using MappingKey = std::pair<StringId /* name */, StringId /* build id */>;
146   std::map<MappingKey, std::vector<MappingId>> stack_profile_mapping_index_;
147 
148   using FrameKey = std::pair<MappingId, uint64_t /* rel_pc */>;
149   std::map<FrameKey, std::vector<FrameId>> stack_profile_frame_index_;
150 
151   std::map<NameInPackage, std::vector<tables::StackProfileFrameTable::Id>>
152       java_frames_for_name_;
153 };
154 
155 // TODO(lalitm): Overhaul this class to make row vs id consistent and use
156 // base::Optional instead of int64_t.
157 class SequenceStackProfileTracker {
158  public:
159   using SourceStringId = uint64_t;
160 
161   enum class InternedStringType {
162     kMappingPath,
163     kBuildId,
164     kFunctionName,
165   };
166 
167   struct SourceMapping {
168     SourceStringId build_id = 0;
169     uint64_t exact_offset = 0;
170     uint64_t start_offset = 0;
171     uint64_t start = 0;
172     uint64_t end = 0;
173     uint64_t load_bias = 0;
174     std::vector<SourceStringId> name_ids;
175   };
176   using SourceMappingId = uint64_t;
177 
178   struct SourceFrame {
179     SourceStringId name_id = 0;
180     SourceMappingId mapping_id = 0;
181     uint64_t rel_pc = 0;
182   };
183   using SourceFrameId = uint64_t;
184 
185   using SourceCallstack = std::vector<SourceFrameId>;
186   using SourceCallstackId = uint64_t;
187 
188   struct SourceAllocation {
189     uint64_t pid = 0;
190     // This is int64_t, because we get this from the TraceSorter which also
191     // converts this for us.
192     int64_t timestamp = 0;
193     SourceCallstackId callstack_id = 0;
194     uint64_t self_allocated = 0;
195     uint64_t self_freed = 0;
196     uint64_t alloc_count = 0;
197     uint64_t free_count = 0;
198   };
199 
200   class InternLookup {
201    public:
202     virtual ~InternLookup();
203 
204     virtual base::Optional<base::StringView> GetString(
205         SourceStringId,
206         InternedStringType) const = 0;
207     virtual base::Optional<SourceMapping> GetMapping(SourceMappingId) const = 0;
208     virtual base::Optional<SourceFrame> GetFrame(SourceFrameId) const = 0;
209     virtual base::Optional<SourceCallstack> GetCallstack(
210         SourceCallstackId) const = 0;
211   };
212 
213   explicit SequenceStackProfileTracker(TraceProcessorContext* context);
214   ~SequenceStackProfileTracker();
215 
216   void AddString(SourceStringId, base::StringView);
217   base::Optional<MappingId> AddMapping(
218       SourceMappingId,
219       const SourceMapping&,
220       const InternLookup* intern_lookup = nullptr);
221   base::Optional<FrameId> AddFrame(SourceFrameId,
222                                    const SourceFrame&,
223                                    const InternLookup* intern_lookup = nullptr);
224   base::Optional<CallsiteId> AddCallstack(
225       SourceCallstackId,
226       const SourceCallstack&,
227       const InternLookup* intern_lookup = nullptr);
228 
229   FrameId GetDatabaseFrameIdForTesting(SourceFrameId);
230 
231   // Gets the row number of string / mapping / frame / callstack previously
232   // added through AddString / AddMapping/ AddFrame / AddCallstack.
233   //
234   // If it is not found, look up the string / mapping / frame / callstack in
235   // the global InternedData state, and if found, add to the database, if not
236   // already added before.
237   //
238   // This is to support both ProfilePackets that contain the interned data
239   // (for Android Q) and where the interned data is kept globally in
240   // InternedData (for versions newer than Q).
241   base::Optional<StringId> FindAndInternString(
242       SourceStringId,
243       const InternLookup* intern_lookup,
244       InternedStringType type);
245   base::Optional<std::string> FindOrInsertString(
246       SourceStringId,
247       const InternLookup* intern_lookup,
248       InternedStringType type);
249   base::Optional<MappingId> FindOrInsertMapping(
250       SourceMappingId,
251       const InternLookup* intern_lookup);
252   base::Optional<FrameId> FindOrInsertFrame(SourceFrameId,
253                                             const InternLookup* intern_lookup);
254 
255   base::Optional<CallsiteId> FindOrInsertCallstack(
256       SourceCallstackId,
257       const InternLookup* intern_lookup);
258 
259   // Clear indices when they're no longer needed.
260   void ClearIndices();
261 
262  private:
263   StringId GetEmptyStringId();
264 
265   std::unordered_map<SourceStringId, std::string> string_map_;
266 
267   // Mapping from ID of mapping / frame / callstack in original trace and the
268   // index in the respective table it was inserted into.
269   std::unordered_map<SourceMappingId, MappingId> mapping_ids_;
270   std::unordered_map<SourceFrameId, FrameId> frame_ids_;
271   std::unordered_map<SourceCallstackId, CallsiteId> callstack_ids_;
272 
273   // TODO(oysteine): Share these indices between the StackProfileTrackers,
274   // since they're not sequence-specific.
275   //
276   // Mapping from content of database row to the index of the raw.
277   std::unordered_map<tables::StackProfileMappingTable::Row, MappingId>
278       mapping_idx_;
279   std::unordered_map<tables::StackProfileFrameTable::Row, FrameId> frame_idx_;
280   std::unordered_map<tables::StackProfileCallsiteTable::Row, CallsiteId>
281       callsite_idx_;
282 
283   TraceProcessorContext* const context_;
284   StringId empty_;
285 };
286 
287 }  // namespace trace_processor
288 }  // namespace perfetto
289 
290 #endif  // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_STACK_PROFILE_TRACKER_H_
291