1
2 /*
3 * Copyright (C) 2023 The Android Open Source Project
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "src/trace_processor/db/column/numeric_storage.h"
19
20 #include <algorithm>
21 #include <cmath>
22 #include <cstdint>
23 #include <functional>
24 #include <limits>
25 #include <optional>
26 #include <string>
27 #include <utility>
28 #include <variant>
29 #include <vector>
30
31 #include "perfetto/base/logging.h"
32 #include "perfetto/public/compiler.h"
33 #include "perfetto/trace_processor/basic_types.h"
34 #include "src/trace_processor/containers/bit_vector.h"
35 #include "src/trace_processor/db/column/data_layer.h"
36 #include "src/trace_processor/db/column/types.h"
37 #include "src/trace_processor/db/column/utils.h"
38 #include "src/trace_processor/tp_metatrace.h"
39
40 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
41 #include "protos/perfetto/trace_processor/serialization.pbzero.h"
42
43 namespace perfetto::trace_processor::column {
44 namespace {
45
46 using Indices = DataLayerChain::Indices;
47 using OrderedIndices = DataLayerChain::OrderedIndices;
48
49 using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
50
51 // Using the fact that binary operators in std are operators() of classes, we
52 // can wrap those classes in variants and use them for std::visit in
53 // SerialComparators. This helps prevent excess templating and switches.
54 template <typename T>
55 using FilterOpVariant = std::variant<std::greater<T>,
56 std::greater_equal<T>,
57 std::less<T>,
58 std::less_equal<T>,
59 std::equal_to<T>,
60 std::not_equal_to<T>>;
61
62 // Based on SqlValue and ColumnType, casts SqlValue to proper type. Assumes the
63 // |val| and |type| are correct.
GetNumericTypeVariant(ColumnType type,SqlValue val)64 inline NumericValue GetNumericTypeVariant(ColumnType type, SqlValue val) {
65 switch (type) {
66 case ColumnType::kDouble:
67 return val.AsDouble();
68 case ColumnType::kInt64:
69 return val.AsLong();
70 case ColumnType::kInt32:
71 return static_cast<int32_t>(val.AsLong());
72 case ColumnType::kUint32:
73 return static_cast<uint32_t>(val.AsLong());
74 case ColumnType::kString:
75 case ColumnType::kDummy:
76 case ColumnType::kId:
77 PERFETTO_FATAL("Invalid type");
78 }
79 PERFETTO_FATAL("For GCC");
80 }
81
82 // Fetch std binary comparator class based on FilterOp. Can be used in
83 // std::visit for comparison.
84 template <typename T>
GetFilterOpVariant(FilterOp op)85 inline FilterOpVariant<T> GetFilterOpVariant(FilterOp op) {
86 switch (op) {
87 case FilterOp::kEq:
88 return FilterOpVariant<T>(std::equal_to<T>());
89 case FilterOp::kNe:
90 return FilterOpVariant<T>(std::not_equal_to<T>());
91 case FilterOp::kGe:
92 return FilterOpVariant<T>(std::greater_equal<T>());
93 case FilterOp::kGt:
94 return FilterOpVariant<T>(std::greater<T>());
95 case FilterOp::kLe:
96 return FilterOpVariant<T>(std::less_equal<T>());
97 case FilterOp::kLt:
98 return FilterOpVariant<T>(std::less<T>());
99 case FilterOp::kGlob:
100 case FilterOp::kRegex:
101 case FilterOp::kIsNotNull:
102 case FilterOp::kIsNull:
103 PERFETTO_FATAL("Not a valid operation on numeric type.");
104 }
105 PERFETTO_FATAL("For GCC");
106 }
107
LowerBoundIntrinsic(const void * vector_ptr,NumericValue val,Range search_range)108 uint32_t LowerBoundIntrinsic(const void* vector_ptr,
109 NumericValue val,
110 Range search_range) {
111 return std::visit(
112 [vector_ptr, search_range](auto val_data) {
113 using T = decltype(val_data);
114 const T* typed_start =
115 static_cast<const std::vector<T>*>(vector_ptr)->data();
116 const auto* lower =
117 std::lower_bound(typed_start + search_range.start,
118 typed_start + search_range.end, val_data);
119 return static_cast<uint32_t>(std::distance(typed_start, lower));
120 },
121 val);
122 }
123
UpperBoundIntrinsic(const void * vector_ptr,NumericValue val,Range search_range)124 uint32_t UpperBoundIntrinsic(const void* vector_ptr,
125 NumericValue val,
126 Range search_range) {
127 return std::visit(
128 [vector_ptr, search_range](auto val_data) {
129 using T = decltype(val_data);
130 const T* typed_start =
131 static_cast<const std::vector<T>*>(vector_ptr)->data();
132 const auto* upper =
133 std::upper_bound(typed_start + search_range.start,
134 typed_start + search_range.end, val_data);
135 return static_cast<uint32_t>(std::distance(typed_start, upper));
136 },
137 val);
138 }
139
140 template <typename T>
TypedLinearSearch(T typed_val,const T * start,FilterOp op,BitVector::Builder & builder)141 void TypedLinearSearch(T typed_val,
142 const T* start,
143 FilterOp op,
144 BitVector::Builder& builder) {
145 switch (op) {
146 case FilterOp::kEq:
147 return utils::LinearSearchWithComparator(typed_val, start,
148 std::equal_to<T>(), builder);
149 case FilterOp::kNe:
150 return utils::LinearSearchWithComparator(typed_val, start,
151 std::not_equal_to<T>(), builder);
152 case FilterOp::kLe:
153 return utils::LinearSearchWithComparator(typed_val, start,
154 std::less_equal<T>(), builder);
155 case FilterOp::kLt:
156 return utils::LinearSearchWithComparator(typed_val, start, std::less<T>(),
157 builder);
158 case FilterOp::kGt:
159 return utils::LinearSearchWithComparator(typed_val, start,
160 std::greater<T>(), builder);
161 case FilterOp::kGe:
162 return utils::LinearSearchWithComparator(
163 typed_val, start, std::greater_equal<T>(), builder);
164 case FilterOp::kGlob:
165 case FilterOp::kRegex:
166 case FilterOp::kIsNotNull:
167 case FilterOp::kIsNull:
168 PERFETTO_DFATAL("Illegal argument");
169 }
170 }
171
IntColumnWithDouble(FilterOp op,SqlValue * sql_val)172 SearchValidationResult IntColumnWithDouble(FilterOp op, SqlValue* sql_val) {
173 double double_val = sql_val->AsDouble();
174
175 // Case when |sql_val| can be interpreted as a SqlValue::Double.
176 if (std::equal_to<>()(static_cast<double>(static_cast<int64_t>(double_val)),
177 double_val)) {
178 *sql_val = SqlValue::Long(static_cast<int64_t>(double_val));
179 return SearchValidationResult::kOk;
180 }
181 // Logic for when the value is a real double.
182 switch (op) {
183 case FilterOp::kEq:
184 return SearchValidationResult::kNoData;
185 case FilterOp::kNe:
186 return SearchValidationResult::kAllData;
187
188 case FilterOp::kLe:
189 case FilterOp::kGt:
190 *sql_val = SqlValue::Long(static_cast<int64_t>(std::floor(double_val)));
191 return SearchValidationResult::kOk;
192
193 case FilterOp::kLt:
194 case FilterOp::kGe:
195 *sql_val = SqlValue::Long(static_cast<int64_t>(std::ceil(double_val)));
196 return SearchValidationResult::kOk;
197
198 case FilterOp::kIsNotNull:
199 case FilterOp::kIsNull:
200 case FilterOp::kGlob:
201 case FilterOp::kRegex:
202 PERFETTO_FATAL("Invalid filter operation");
203 }
204 PERFETTO_FATAL("For GCC");
205 }
206
DoubleColumnWithInt(FilterOp op,SqlValue * sql_val)207 SearchValidationResult DoubleColumnWithInt(FilterOp op, SqlValue* sql_val) {
208 int64_t i = sql_val->AsLong();
209 auto i_as_d = static_cast<double>(i);
210
211 // Case when |sql_val| can be interpreted as a SqlValue::Long.
212 if (std::equal_to<int64_t>()(i, static_cast<int64_t>(i_as_d))) {
213 *sql_val = SqlValue::Double(i_as_d);
214 return SearchValidationResult::kOk;
215 }
216
217 // Logic for when the value can't be represented as double.
218 switch (op) {
219 case FilterOp::kEq:
220 return SearchValidationResult::kNoData;
221 case FilterOp::kNe:
222 return SearchValidationResult::kAllData;
223
224 case FilterOp::kLe:
225 case FilterOp::kGt:
226 // The first double value smaller than |i|.
227 *sql_val = SqlValue::Double(std::nextafter(i_as_d, i - 1));
228 return SearchValidationResult::kOk;
229
230 case FilterOp::kLt:
231 case FilterOp::kGe:
232 // The first double value bigger than |i|.
233 *sql_val = SqlValue::Double(std::nextafter(i_as_d, i + 1));
234 return SearchValidationResult::kOk;
235
236 case FilterOp::kIsNotNull:
237 case FilterOp::kIsNull:
238 case FilterOp::kGlob:
239 case FilterOp::kRegex:
240 PERFETTO_FATAL("Invalid filter operation");
241 }
242 PERFETTO_FATAL("For GCC");
243 }
244
245 } // namespace
246
ChainImpl(const void * vector_ptr,ColumnType type,bool is_sorted)247 NumericStorageBase::ChainImpl::ChainImpl(const void* vector_ptr,
248 ColumnType type,
249 bool is_sorted)
250 : vector_ptr_(vector_ptr), storage_type_(type), is_sorted_(is_sorted) {}
251
ValidateSearchConstraints(FilterOp op,SqlValue val) const252 SearchValidationResult NumericStorageBase::ChainImpl::ValidateSearchConstraints(
253 FilterOp op,
254 SqlValue val) const {
255 // NULL checks.
256 if (PERFETTO_UNLIKELY(val.is_null())) {
257 if (op == FilterOp::kIsNotNull) {
258 return SearchValidationResult::kAllData;
259 }
260 if (op == FilterOp::kIsNull) {
261 return SearchValidationResult::kNoData;
262 }
263 PERFETTO_FATAL(
264 "Invalid path. NULL should only be compared with 'IS NULL' and 'IS NOT "
265 "NULL'");
266 }
267
268 // FilterOp checks. Switch so that we get a warning if new FilterOp is not
269 // handled.
270 switch (op) {
271 case FilterOp::kEq:
272 case FilterOp::kNe:
273 case FilterOp::kLt:
274 case FilterOp::kLe:
275 case FilterOp::kGt:
276 case FilterOp::kGe:
277 break;
278 case FilterOp::kIsNull:
279 case FilterOp::kIsNotNull:
280 PERFETTO_FATAL("Invalid constraint");
281 case FilterOp::kGlob:
282 case FilterOp::kRegex:
283 return SearchValidationResult::kNoData;
284 }
285
286 // Type checks.
287 switch (val.type) {
288 case SqlValue::kNull:
289 case SqlValue::kLong:
290 case SqlValue::kDouble:
291 break;
292 case SqlValue::kString:
293 // Any string is always more than any numeric.
294 if (op == FilterOp::kLt || op == FilterOp::kLe) {
295 return SearchValidationResult::kAllData;
296 }
297 return SearchValidationResult::kNoData;
298 case SqlValue::kBytes:
299 return SearchValidationResult::kNoData;
300 }
301
302 // Bounds of the value.
303 enum ExtremeVal { kTooBig, kTooSmall, kOk };
304 ExtremeVal extreme_validator = kOk;
305
306 double num_val = val.type == SqlValue::kLong
307 ? static_cast<double>(val.AsLong())
308 : val.AsDouble();
309
310 switch (storage_type_) {
311 case ColumnType::kDouble:
312 // Any value would make a sensible comparison with a double.
313 case ColumnType::kInt64:
314 // TODO(b/307482437): As long as the type is not double there is nothing
315 // to verify here, as all values are going to be in the int64_t limits.
316 break;
317 case ColumnType::kInt32:
318 if (num_val > std::numeric_limits<int32_t>::max()) {
319 extreme_validator = kTooBig;
320 break;
321 }
322 if (num_val < std::numeric_limits<int32_t>::min()) {
323 extreme_validator = kTooSmall;
324 break;
325 }
326 break;
327 case ColumnType::kUint32:
328 if (num_val > std::numeric_limits<uint32_t>::max()) {
329 extreme_validator = kTooBig;
330 break;
331 }
332 if (num_val < std::numeric_limits<uint32_t>::min()) {
333 extreme_validator = kTooSmall;
334 break;
335 }
336 break;
337 case ColumnType::kString:
338 case ColumnType::kDummy:
339 case ColumnType::kId:
340 break;
341 }
342
343 switch (extreme_validator) {
344 case kOk:
345 return SearchValidationResult::kOk;
346 case kTooBig:
347 if (op == FilterOp::kLt || op == FilterOp::kLe || op == FilterOp::kNe) {
348 return SearchValidationResult::kAllData;
349 }
350 return SearchValidationResult::kNoData;
351 case kTooSmall:
352 if (op == FilterOp::kGt || op == FilterOp::kGe || op == FilterOp::kNe) {
353 return SearchValidationResult::kAllData;
354 }
355 return SearchValidationResult::kNoData;
356 }
357
358 PERFETTO_FATAL("For GCC");
359 }
360
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const361 RangeOrBitVector NumericStorageBase::ChainImpl::SearchValidated(
362 FilterOp op,
363 SqlValue sql_val,
364 Range search_range) const {
365 PERFETTO_DCHECK(search_range.end <= size());
366
367 PERFETTO_TP_TRACE(
368 metatrace::Category::DB, "NumericStorage::ChainImpl::Search",
369 [&search_range, op](metatrace::Record* r) {
370 r->AddArg("Start", std::to_string(search_range.start));
371 r->AddArg("End", std::to_string(search_range.end));
372 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
373 });
374
375 // Mismatched types - value is double and column is int.
376 if (sql_val.type == SqlValue::kDouble &&
377 storage_type_ != ColumnType::kDouble) {
378 auto ret_opt =
379 utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), search_range);
380 if (ret_opt) {
381 return RangeOrBitVector(*ret_opt);
382 }
383 }
384
385 // Mismatched types - column is double and value is int.
386 if (sql_val.type != SqlValue::kDouble &&
387 storage_type_ == ColumnType::kDouble) {
388 auto ret_opt =
389 utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), search_range);
390 if (ret_opt) {
391 return RangeOrBitVector(*ret_opt);
392 }
393 }
394
395 NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
396
397 if (is_sorted_) {
398 if (op != FilterOp::kNe) {
399 return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
400 }
401 // Not equal is a special operation on binary search, as it doesn't define a
402 // range, and rather just `not` range returned with `equal` operation.
403 Range r = BinarySearchIntrinsic(FilterOp::kEq, val, search_range);
404 BitVector bv(r.start, true);
405 bv.Resize(r.end, false);
406 bv.Resize(search_range.end, true);
407 return RangeOrBitVector(std::move(bv));
408 }
409 return RangeOrBitVector(LinearSearchInternal(op, val, search_range));
410 }
411
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const412 void NumericStorageBase::ChainImpl::IndexSearchValidated(
413 FilterOp op,
414 SqlValue sql_val,
415 Indices& indices) const {
416 PERFETTO_TP_TRACE(
417 metatrace::Category::DB, "NumericStorage::ChainImpl::IndexSearch",
418 [&indices, op](metatrace::Record* r) {
419 r->AddArg("Count", std::to_string(indices.tokens.size()));
420 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
421 });
422
423 // Mismatched types - value is double and column is int.
424 if (sql_val.type == SqlValue::kDouble &&
425 storage_type_ != ColumnType::kDouble) {
426 if (utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), indices)) {
427 return;
428 }
429 }
430
431 // Mismatched types - column is double and value is int.
432 if (sql_val.type != SqlValue::kDouble &&
433 storage_type_ == ColumnType::kDouble) {
434 if (utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), indices)) {
435 return;
436 }
437 }
438
439 NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
440 std::visit(
441 [this, &indices, op](auto val) {
442 using T = decltype(val);
443 auto* start = static_cast<const std::vector<T>*>(vector_ptr_)->data();
444 std::visit(
445 [start, &indices, val](auto comparator) {
446 utils::IndexSearchWithComparator(val, start, indices, comparator);
447 },
448 GetFilterOpVariant<T>(op));
449 },
450 val);
451 }
452
LinearSearchInternal(FilterOp op,NumericValue val,Range range) const453 BitVector NumericStorageBase::ChainImpl::LinearSearchInternal(
454 FilterOp op,
455 NumericValue val,
456 Range range) const {
457 BitVector::Builder builder(range.end, range.start);
458 if (const auto* u32 = std::get_if<uint32_t>(&val)) {
459 const auto* start =
460 static_cast<const std::vector<uint32_t>*>(vector_ptr_)->data() +
461 range.start;
462 TypedLinearSearch(*u32, start, op, builder);
463 } else if (const auto* i64 = std::get_if<int64_t>(&val)) {
464 const auto* start =
465 static_cast<const std::vector<int64_t>*>(vector_ptr_)->data() +
466 range.start;
467 TypedLinearSearch(*i64, start, op, builder);
468 } else if (const auto* i32 = std::get_if<int32_t>(&val)) {
469 const auto* start =
470 static_cast<const std::vector<int32_t>*>(vector_ptr_)->data() +
471 range.start;
472 TypedLinearSearch(*i32, start, op, builder);
473 } else if (const auto* db = std::get_if<double>(&val)) {
474 const auto* start =
475 static_cast<const std::vector<double>*>(vector_ptr_)->data() +
476 range.start;
477 TypedLinearSearch(*db, start, op, builder);
478 } else {
479 PERFETTO_DFATAL("Invalid");
480 }
481 return std::move(builder).Build();
482 }
483
BinarySearchIntrinsic(FilterOp op,NumericValue val,Range search_range) const484 Range NumericStorageBase::ChainImpl::BinarySearchIntrinsic(
485 FilterOp op,
486 NumericValue val,
487 Range search_range) const {
488 switch (op) {
489 case FilterOp::kEq:
490 return {LowerBoundIntrinsic(vector_ptr_, val, search_range),
491 UpperBoundIntrinsic(vector_ptr_, val, search_range)};
492 case FilterOp::kLe:
493 return {search_range.start,
494 UpperBoundIntrinsic(vector_ptr_, val, search_range)};
495 case FilterOp::kLt:
496 return {search_range.start,
497 LowerBoundIntrinsic(vector_ptr_, val, search_range)};
498 case FilterOp::kGe:
499 return {LowerBoundIntrinsic(vector_ptr_, val, search_range),
500 search_range.end};
501 case FilterOp::kGt:
502 return {UpperBoundIntrinsic(vector_ptr_, val, search_range),
503 search_range.end};
504 case FilterOp::kNe:
505 case FilterOp::kIsNull:
506 case FilterOp::kIsNotNull:
507 case FilterOp::kGlob:
508 case FilterOp::kRegex:
509 return {};
510 }
511 return {};
512 }
513
Serialize(StorageProto * msg) const514 void NumericStorageBase::ChainImpl::Serialize(StorageProto* msg) const {
515 auto* numeric_storage_msg = msg->set_numeric_storage();
516 numeric_storage_msg->set_is_sorted(is_sorted_);
517 numeric_storage_msg->set_column_type(static_cast<uint32_t>(storage_type_));
518
519 switch (storage_type_) {
520 case ColumnType::kInt64: {
521 const auto* ptr = static_cast<const std::vector<int64_t>*>(vector_ptr_);
522 numeric_storage_msg->set_values(
523 reinterpret_cast<const uint8_t*>(ptr->data()),
524 sizeof(int64_t) * ptr->size());
525 break;
526 }
527 case ColumnType::kInt32: {
528 const auto* ptr = static_cast<const std::vector<int64_t>*>(vector_ptr_);
529 numeric_storage_msg->set_values(
530 reinterpret_cast<const uint8_t*>(ptr->data()),
531 sizeof(int32_t) * ptr->size());
532 break;
533 }
534 case ColumnType::kUint32: {
535 const auto* ptr = static_cast<const std::vector<int64_t>*>(vector_ptr_);
536 numeric_storage_msg->set_values(
537 reinterpret_cast<const uint8_t*>(ptr->data()),
538 sizeof(uint32_t) * ptr->size());
539 break;
540 }
541 case ColumnType::kDouble: {
542 const auto* ptr = static_cast<const std::vector<int64_t>*>(vector_ptr_);
543 numeric_storage_msg->set_values(
544 reinterpret_cast<const uint8_t*>(ptr->data()),
545 sizeof(double_t) * ptr->size());
546 break;
547 }
548 case ColumnType::kDummy:
549 case ColumnType::kId:
550 case ColumnType::kString:
551 PERFETTO_FATAL("Invalid column type for NumericStorage");
552 }
553 }
554
555 } // namespace perfetto::trace_processor::column
556