1 /*
2 * Copyright (C) 2023 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 #include "src/trace_processor/db/column/data_layer.h"
18
19 #include <algorithm>
20 #include <cstdint>
21 #include <iterator>
22 #include <memory>
23 #include <utility>
24 #include <vector>
25
26 #include "perfetto/base/logging.h"
27 #include "perfetto/trace_processor/basic_types.h"
28 #include "src/trace_processor/containers/bit_vector.h"
29 #include "src/trace_processor/containers/string_pool.h"
30 #include "src/trace_processor/db/column/arrangement_overlay.h"
31 #include "src/trace_processor/db/column/dense_null_overlay.h"
32 #include "src/trace_processor/db/column/dummy_storage.h"
33 #include "src/trace_processor/db/column/id_storage.h"
34 #include "src/trace_processor/db/column/null_overlay.h"
35 #include "src/trace_processor/db/column/numeric_storage.h"
36 #include "src/trace_processor/db/column/range_overlay.h"
37 #include "src/trace_processor/db/column/selector_overlay.h"
38 #include "src/trace_processor/db/column/set_id_storage.h"
39 #include "src/trace_processor/db/column/string_storage.h"
40 #include "src/trace_processor/db/column/types.h"
41 #include "src/trace_processor/db/compare.h"
42
43 namespace perfetto::trace_processor::column {
44
45 DataLayer::~DataLayer() = default;
46 DataLayerChain::~DataLayerChain() = default;
47
48 // All the below code exists as machinery to allow dead-code-elimination
49 // and linker symbol stripping to work for trace processor built into Chrome. It
50 // is ugly and hacky but is the only way we could come up with to actually meet
51 // both performance constraints and saving binary size in Chrome.
52 //
53 // TODO(b/325583551): investigate whether we can improve this at some point,
54 // potentially removing this if Chrome no longer relies on trace processor for
55 // JSON export.
56
MakeChain()57 std::unique_ptr<DataLayerChain> DataLayer::MakeChain() {
58 switch (impl_) {
59 case Impl::kDummy:
60 return static_cast<DummyStorage*>(this)->MakeChain();
61 case Impl::kId:
62 return static_cast<IdStorage*>(this)->MakeChain();
63 case Impl::kNumericDouble:
64 return static_cast<NumericStorage<double>*>(this)->MakeChain();
65 case Impl::kNumericUint32:
66 return static_cast<NumericStorage<uint32_t>*>(this)->MakeChain();
67 case Impl::kNumericInt32:
68 return static_cast<NumericStorage<int32_t>*>(this)->MakeChain();
69 case Impl::kNumericInt64:
70 return static_cast<NumericStorage<int64_t>*>(this)->MakeChain();
71 case Impl::kSetId:
72 return static_cast<SetIdStorage*>(this)->MakeChain();
73 case Impl::kString:
74 return static_cast<StringStorage*>(this)->MakeChain();
75 case Impl::kArrangement:
76 case Impl::kDenseNull:
77 case Impl::kNull:
78 case Impl::kRange:
79 case Impl::kSelector:
80 PERFETTO_FATAL(
81 "Unexpected call to MakeChain(). MakeChain(DataLayerChain) should be "
82 "called instead");
83 }
84 PERFETTO_FATAL("For GCC");
85 }
86
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs args)87 std::unique_ptr<DataLayerChain> DataLayer::MakeChain(
88 std::unique_ptr<DataLayerChain> inner,
89 ChainCreationArgs args) {
90 switch (impl_) {
91 case Impl::kArrangement:
92 return static_cast<ArrangementOverlay*>(this)->MakeChain(std::move(inner),
93 args);
94 case Impl::kDenseNull:
95 return static_cast<DenseNullOverlay*>(this)->MakeChain(std::move(inner),
96 args);
97 case Impl::kNull:
98 return static_cast<NullOverlay*>(this)->MakeChain(std::move(inner), args);
99 case Impl::kRange:
100 return static_cast<RangeOverlay*>(this)->MakeChain(std::move(inner),
101 args);
102 case Impl::kSelector:
103 return static_cast<SelectorOverlay*>(this)->MakeChain(std::move(inner),
104 args);
105 case Impl::kDummy:
106 case Impl::kId:
107 case Impl::kNumericDouble:
108 case Impl::kNumericUint32:
109 case Impl::kNumericInt32:
110 case Impl::kNumericInt64:
111 case Impl::kSetId:
112 case Impl::kString:
113 PERFETTO_FATAL(
114 "Unexpected call to MakeChain(DataLayerChain). MakeChain() should be "
115 "called instead");
116 }
117 PERFETTO_FATAL("For GCC");
118 }
119
OrderedIndexSearchValidated(FilterOp op,SqlValue value,const OrderedIndices & indices) const120 Range DataLayerChain::OrderedIndexSearchValidated(
121 FilterOp op,
122 SqlValue value,
123 const OrderedIndices& indices) const {
124 auto lb = [&]() {
125 return static_cast<uint32_t>(std::distance(
126 indices.data,
127 std::lower_bound(indices.data, indices.data + indices.size, value,
128 [this](uint32_t idx, const SqlValue& v) {
129 return compare::SqlValueComparator(
130 Get_AvoidUsingBecauseSlow(idx), v);
131 })));
132 };
133 auto ub = [&]() {
134 return static_cast<uint32_t>(std::distance(
135 indices.data,
136 std::upper_bound(indices.data, indices.data + indices.size, value,
137 [this](const SqlValue& v, uint32_t idx) {
138 return compare::SqlValueComparator(
139 v, Get_AvoidUsingBecauseSlow(idx));
140 })));
141 };
142 switch (op) {
143 case FilterOp::kEq:
144 return {lb(), ub()};
145 case FilterOp::kLe:
146 return {0, ub()};
147 case FilterOp::kLt:
148 return {0, lb()};
149 case FilterOp::kGe:
150 return {lb(), indices.size};
151 case FilterOp::kGt:
152 return {ub(), indices.size};
153 case FilterOp::kIsNull:
154 PERFETTO_CHECK(value.is_null());
155 return {0, ub()};
156 case FilterOp::kIsNotNull:
157 PERFETTO_CHECK(value.is_null());
158 return {ub(), indices.size};
159 case FilterOp::kNe:
160 case FilterOp::kGlob:
161 case FilterOp::kRegex:
162 PERFETTO_FATAL("Wrong filtering operation");
163 }
164 PERFETTO_FATAL("For GCC");
165 }
166
ArrangementOverlay(const std::vector<uint32_t> * arrangement,DataLayerChain::Indices::State arrangement_state)167 ArrangementOverlay::ArrangementOverlay(
168 const std::vector<uint32_t>* arrangement,
169 DataLayerChain::Indices::State arrangement_state)
170 : DataLayer(Impl::kArrangement),
171 arrangement_(arrangement),
172 arrangement_state_(arrangement_state) {}
173 ArrangementOverlay::~ArrangementOverlay() = default;
174
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs args)175 std::unique_ptr<DataLayerChain> ArrangementOverlay::MakeChain(
176 std::unique_ptr<DataLayerChain> inner,
177 ChainCreationArgs args) {
178 return std::make_unique<ChainImpl>(std::move(inner), arrangement_,
179 arrangement_state_,
180 args.does_layer_order_chain_contents);
181 }
182
DenseNullOverlay(const BitVector * non_null)183 DenseNullOverlay::DenseNullOverlay(const BitVector* non_null)
184 : DataLayer(Impl::kDenseNull), non_null_(non_null) {}
185 DenseNullOverlay::~DenseNullOverlay() = default;
186
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs)187 std::unique_ptr<DataLayerChain> DenseNullOverlay::MakeChain(
188 std::unique_ptr<DataLayerChain> inner,
189 ChainCreationArgs) {
190 return std::make_unique<ChainImpl>(std::move(inner), non_null_);
191 }
192
MakeChain()193 std::unique_ptr<DataLayerChain> DummyStorage::MakeChain() {
194 return std::make_unique<ChainImpl>();
195 }
196
IdStorage()197 IdStorage::IdStorage() : DataLayer(Impl::kId) {}
198 IdStorage::~IdStorage() = default;
199
MakeChain()200 std::unique_ptr<DataLayerChain> IdStorage::MakeChain() {
201 return std::make_unique<ChainImpl>();
202 }
203
NullOverlay(const BitVector * non_null)204 NullOverlay::NullOverlay(const BitVector* non_null)
205 : DataLayer(Impl::kNull), non_null_(non_null) {}
206 NullOverlay::~NullOverlay() = default;
207
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs)208 std::unique_ptr<DataLayerChain> NullOverlay::MakeChain(
209 std::unique_ptr<DataLayerChain> inner,
210 ChainCreationArgs) {
211 return std::make_unique<ChainImpl>(std::move(inner), non_null_);
212 }
213
NumericStorageBase(ColumnType type,bool is_sorted,Impl impl)214 NumericStorageBase::NumericStorageBase(ColumnType type,
215 bool is_sorted,
216 Impl impl)
217 : DataLayer(impl), storage_type_(type), is_sorted_(is_sorted) {}
218
219 NumericStorageBase::~NumericStorageBase() = default;
220
221 template <typename T>
MakeChain()222 std::unique_ptr<DataLayerChain> NumericStorage<T>::MakeChain() {
223 return std::make_unique<ChainImpl>(vector_, storage_type_, is_sorted_);
224 }
225
226 template <typename T>
NumericStorage(const std::vector<T> * vec,ColumnType type,bool is_sorted)227 NumericStorage<T>::NumericStorage(const std::vector<T>* vec,
228 ColumnType type,
229 bool is_sorted)
230 : NumericStorageBase(type, is_sorted, GetImpl()), vector_(vec) {}
231
232 // Define explicit instantiation of the necessary templates here to reduce
233 // binary size bloat.
234 template class NumericStorage<double>;
235 template class NumericStorage<uint32_t>;
236 template class NumericStorage<int32_t>;
237 template class NumericStorage<int64_t>;
238
RangeOverlay(const Range * range)239 RangeOverlay::RangeOverlay(const Range* range)
240 : DataLayer(Impl::kRange), range_(range) {}
241 RangeOverlay::~RangeOverlay() = default;
242
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs)243 std::unique_ptr<DataLayerChain> RangeOverlay::MakeChain(
244 std::unique_ptr<DataLayerChain> inner,
245 ChainCreationArgs) {
246 return std::make_unique<ChainImpl>(std::move(inner), range_);
247 }
248
SelectorOverlay(const BitVector * selector)249 SelectorOverlay::SelectorOverlay(const BitVector* selector)
250 : DataLayer(Impl::kSelector), selector_(selector) {}
251 SelectorOverlay::~SelectorOverlay() = default;
252
MakeChain(std::unique_ptr<DataLayerChain> inner,ChainCreationArgs)253 std::unique_ptr<DataLayerChain> SelectorOverlay::MakeChain(
254 std::unique_ptr<DataLayerChain> inner,
255 ChainCreationArgs) {
256 return std::make_unique<ChainImpl>(std::move(inner), selector_);
257 }
258
SetIdStorage(const std::vector<uint32_t> * values)259 SetIdStorage::SetIdStorage(const std::vector<uint32_t>* values)
260 : DataLayer(Impl::kSetId), values_(values) {}
261 SetIdStorage::~SetIdStorage() = default;
262
MakeChain()263 std::unique_ptr<DataLayerChain> SetIdStorage::MakeChain() {
264 return std::make_unique<ChainImpl>(values_);
265 }
266
StringStorage(StringPool * string_pool,const std::vector<StringPool::Id> * data,bool is_sorted)267 StringStorage::StringStorage(StringPool* string_pool,
268 const std::vector<StringPool::Id>* data,
269 bool is_sorted)
270 : DataLayer(Impl::kString),
271 data_(data),
272 string_pool_(string_pool),
273 is_sorted_(is_sorted) {}
274 StringStorage::~StringStorage() = default;
275
MakeChain()276 std::unique_ptr<DataLayerChain> StringStorage::MakeChain() {
277 return std::make_unique<ChainImpl>(string_pool_, data_, is_sorted_);
278 }
279
280 } // namespace perfetto::trace_processor::column
281