1 /*
2  * Copyright (C) 2024 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_PERFETTO_SQL_INTRINSICS_OPERATORS_SLICE_MIPMAP_OPERATOR_H_
18 #define SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_OPERATORS_SLICE_MIPMAP_OPERATOR_H_
19 
20 #include <sqlite3.h>
21 #include <cstdint>
22 #include <vector>
23 
24 #include "src/trace_processor/containers/implicit_segment_forest.h"
25 #include "src/trace_processor/perfetto_sql/engine/perfetto_sql_engine.h"
26 #include "src/trace_processor/sqlite/bindings/sqlite_module.h"
27 #include "src/trace_processor/sqlite/module_lifecycle_manager.h"
28 
29 namespace perfetto::trace_processor {
30 
31 // Operator for building "mipmaps"  [1] over the slices in the trace.
32 //
33 // In this context mipmap really means aggregating the slices in a given
34 // time period by max(dur) for that period, allowing UIs to efficiently display
35 // the contents of slice tracks when very zoomed out.
36 //
37 // Specifically, we are computing the query:
38 // ```
39 //   select
40 //     depth,
41 //     max(dur) as dur,
42 //     id,
43 //     ts
44 //   from $input in
45 //   where in.ts_end >= $window_start and in.ts <= $window_end
46 //   group by depth, ts / $window_resolution
47 //   order by ts
48 // ```
49 // but in O(logn) time by using a segment-tree like data structure (see
50 // ImplicitSegmentForest).
51 //
52 // [1] https://en.wikipedia.org/wiki/Mipmap
53 struct SliceMipmapOperator : sqlite::Module<SliceMipmapOperator> {
54   struct Slice {
55     int64_t dur;
56     uint32_t id;
57     uint32_t idx;
58   };
59   struct Agg {
operatorSliceMipmapOperator::Agg60     Slice operator()(const Slice& a, const Slice& b) {
61       return a.dur < b.dur ? b : a;
62     }
63   };
64   struct PerDepth {
65     ImplicitSegmentForest<Slice, Agg> forest;
66     std::vector<int64_t> timestamps;
67   };
68   struct State {
69     std::vector<PerDepth> by_depth;
70   };
71   struct Context {
ContextSliceMipmapOperator::Context72     explicit Context(PerfettoSqlEngine* _engine) : engine(_engine) {}
73     PerfettoSqlEngine* engine;
74     sqlite::ModuleStateManager<SliceMipmapOperator> manager;
75   };
76   struct Vtab : sqlite::Module<SliceMipmapOperator>::Vtab {
77     sqlite::ModuleStateManager<SliceMipmapOperator>::PerVtabState* state;
78   };
79   struct Cursor : sqlite::Module<SliceMipmapOperator>::Cursor {
80     struct Result {
81       int64_t timestamp;
82       int64_t dur;
83       uint32_t id;
84       uint32_t depth;
85     };
86     std::vector<Result> results;
87     uint32_t index = 0;
88   };
89 
90   static constexpr auto kType = kCreateOnly;
91   static constexpr bool kSupportsWrites = false;
92   static constexpr bool kDoesOverloadFunctions = false;
93 
94   static int Create(sqlite3*,
95                     void*,
96                     int,
97                     const char* const*,
98                     sqlite3_vtab**,
99                     char**);
100   static int Destroy(sqlite3_vtab*);
101 
102   static int Connect(sqlite3*,
103                      void*,
104                      int,
105                      const char* const*,
106                      sqlite3_vtab**,
107                      char**);
108   static int Disconnect(sqlite3_vtab*);
109 
110   static int BestIndex(sqlite3_vtab*, sqlite3_index_info*);
111 
112   static int Open(sqlite3_vtab*, sqlite3_vtab_cursor**);
113   static int Close(sqlite3_vtab_cursor*);
114 
115   static int Filter(sqlite3_vtab_cursor*,
116                     int,
117                     const char*,
118                     int,
119                     sqlite3_value**);
120   static int Next(sqlite3_vtab_cursor*);
121   static int Eof(sqlite3_vtab_cursor*);
122   static int Column(sqlite3_vtab_cursor*, sqlite3_context*, int);
123   static int Rowid(sqlite3_vtab_cursor*, sqlite_int64*);
124 
125   // This needs to happen at the end as it depends on the functions
126   // defined above.
127   static constexpr sqlite3_module kModule = CreateModule();
128 };
129 
130 }  // namespace perfetto::trace_processor
131 
132 #endif  // SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_OPERATORS_SLICE_MIPMAP_OPERATOR_H_
133