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_COUNTER_MIPMAP_OPERATOR_H_
18 #define SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_OPERATORS_COUNTER_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 counter-like tracks.
32 //
33 // In the context of trace data, mipmap really means aggregating the counter
34 // values in a given time period into the {min, max, last} value for that
35 // period, allowing UIs to efficiently display the contents of a counter track
36 // when very zoomed out.
37 //
38 // Specifically, we are computing the query:
39 // ```
40 //   select
41 //     last_value(ts),
42 //     min(value),
43 //     max(value),
44 //     last_value(value)
45 //   from $input in
46 //   where in.ts_end >= $window_start and in.ts <= $window_end
47 //   group by ts / $window_resolution
48 //   order by ts
49 // ```
50 // but in O(logn) time by using a segment-tree like data structure (see
51 // ImplicitSegmentForest).
52 //
53 // [1] https://en.wikipedia.org/wiki/Mipmap
54 struct CounterMipmapOperator : sqlite::Module<CounterMipmapOperator> {
55   struct Counter {
56     float min;
57     float max;
58   };
59   struct Agg {
operatorCounterMipmapOperator::Agg60     Counter operator()(const Counter& a, const Counter& b) {
61       Counter res;
62       res.min = b.min < a.min ? b.min : a.min;
63       res.max = b.max > a.max ? b.max : a.max;
64       return res;
65     }
66   };
67   struct State {
68     ImplicitSegmentForest<Counter, Agg> forest;
69     std::vector<int64_t> timestamps;
70   };
71   struct Context {
ContextCounterMipmapOperator::Context72     explicit Context(PerfettoSqlEngine* _engine) : engine(_engine) {}
73     PerfettoSqlEngine* engine;
74     sqlite::ModuleStateManager<CounterMipmapOperator> manager;
75   };
76   struct Vtab : sqlite::Module<CounterMipmapOperator>::Vtab {
77     sqlite::ModuleStateManager<CounterMipmapOperator>::PerVtabState* state;
78   };
79   struct Cursor : sqlite::Module<CounterMipmapOperator>::Cursor {
80     struct Result {
81       Counter min_max_counter;
82       Counter last_counter;
83       int64_t last_ts;
84     };
85     std::vector<Result> counters;
86     uint32_t index;
87   };
88 
89   static constexpr auto kType = kCreateOnly;
90   static constexpr bool kSupportsWrites = false;
91   static constexpr bool kDoesOverloadFunctions = false;
92 
93   static int Create(sqlite3*,
94                     void*,
95                     int,
96                     const char* const*,
97                     sqlite3_vtab**,
98                     char**);
99   static int Destroy(sqlite3_vtab*);
100 
101   static int Connect(sqlite3*,
102                      void*,
103                      int,
104                      const char* const*,
105                      sqlite3_vtab**,
106                      char**);
107   static int Disconnect(sqlite3_vtab*);
108 
109   static int BestIndex(sqlite3_vtab*, sqlite3_index_info*);
110 
111   static int Open(sqlite3_vtab*, sqlite3_vtab_cursor**);
112   static int Close(sqlite3_vtab_cursor*);
113 
114   static int Filter(sqlite3_vtab_cursor*,
115                     int,
116                     const char*,
117                     int,
118                     sqlite3_value**);
119   static int Next(sqlite3_vtab_cursor*);
120   static int Eof(sqlite3_vtab_cursor*);
121   static int Column(sqlite3_vtab_cursor*, sqlite3_context*, int);
122   static int Rowid(sqlite3_vtab_cursor*, sqlite_int64*);
123 
124   // This needs to happen at the end as it depends on the functions
125   // defined above.
126   static constexpr sqlite3_module kModule = CreateModule();
127 };
128 
129 }  // namespace perfetto::trace_processor
130 
131 #endif  // SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_OPERATORS_COUNTER_MIPMAP_OPERATOR_H_
132