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