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 #ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
17 #define SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
18
19 #include <algorithm>
20 #include <cstdint>
21 #include <functional>
22 #include <limits>
23 #include <optional>
24 #include <type_traits>
25 #include <vector>
26
27 #include "perfetto/base/logging.h"
28 #include "perfetto/trace_processor/basic_types.h"
29 #include "src/trace_processor/containers/bit_vector.h"
30 #include "src/trace_processor/db/column/data_layer.h"
31 #include "src/trace_processor/db/column/types.h"
32
33 namespace perfetto::trace_processor::column::utils {
34 namespace internal {
35
36 template <typename T, typename Comparator>
SingleSearchNumeric(T left,const SqlValue & right_v)37 SingleSearchResult SingleSearchNumeric(T left, const SqlValue& right_v) {
38 if constexpr (std::is_same_v<T, double>) {
39 if (right_v.type != SqlValue::kDouble) {
40 // Because of the large amount of code needing for handling comparisons
41 // with integers, just defer to the full search.
42 return SingleSearchResult::kNeedsFullSearch;
43 }
44 return Comparator()(left, right_v.double_value)
45 ? SingleSearchResult::kMatch
46 : SingleSearchResult::kNoMatch;
47 } else if constexpr (std::is_integral_v<T>) {
48 if (right_v.type != SqlValue::kLong ||
49 right_v.long_value > std::numeric_limits<T>::max() ||
50 right_v.long_value < std::numeric_limits<T>::min()) {
51 // Because of the large amount of code needing for handling comparisons
52 // with doubles or out of range values, just defer to the full search.
53 return SingleSearchResult::kNeedsFullSearch;
54 }
55 return Comparator()(left, static_cast<T>(right_v.long_value))
56 ? SingleSearchResult::kMatch
57 : SingleSearchResult::kNoMatch;
58 } else {
59 static_assert(std::is_same_v<T, void>, "Illegal type");
60 }
61 }
62
63 } // namespace internal
64
65 template <typename Comparator, typename ValType, typename DataType>
LinearSearchWithComparator(ValType val,const DataType * data_ptr,Comparator comparator,BitVector::Builder & builder)66 void LinearSearchWithComparator(ValType val,
67 const DataType* data_ptr,
68 Comparator comparator,
69 BitVector::Builder& builder) {
70 // Slow path: we compare <64 elements and append to get us to a word
71 // boundary.
72 const DataType* cur_val = data_ptr;
73 uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
74 for (uint32_t i = 0; i < front_elements; ++i, ++cur_val) {
75 builder.Append(comparator(*cur_val, val));
76 }
77
78 // Fast path: we compare as many groups of 64 elements as we can.
79 // This should be very easy for the compiler to auto-vectorize.
80 uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
81 for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
82 uint64_t word = 0;
83 // This part should be optimised by SIMD and is expected to be fast.
84 for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k, ++cur_val) {
85 bool comp_result = comparator(*cur_val, val);
86 word |= static_cast<uint64_t>(comp_result) << k;
87 }
88 builder.AppendWord(word);
89 }
90
91 // Slow path: we compare <64 elements and append to fill the Builder.
92 uint32_t back_elements = builder.BitsUntilFull();
93 for (uint32_t i = 0; i < back_elements; ++i, ++cur_val) {
94 builder.Append(comparator(*cur_val, val));
95 }
96 }
97
98 template <typename Comparator, typename ValType, typename DataType>
IndexSearchWithComparator(ValType val,const DataType * data_ptr,DataLayerChain::Indices & indices,Comparator comparator)99 void IndexSearchWithComparator(ValType val,
100 const DataType* data_ptr,
101 DataLayerChain::Indices& indices,
102 Comparator comparator) {
103 auto it = std::remove_if(indices.tokens.begin(), indices.tokens.end(),
104 [&comparator, data_ptr, &val](const Token& token) {
105 return !comparator(*(data_ptr + token.index), val);
106 });
107 indices.tokens.erase(it, indices.tokens.end());
108 }
109
110 template <typename T>
SingleSearchNumeric(FilterOp op,T left,const SqlValue & right_v)111 SingleSearchResult SingleSearchNumeric(FilterOp op,
112 T left,
113 const SqlValue& right_v) {
114 switch (op) {
115 case FilterOp::kEq:
116 return internal::SingleSearchNumeric<T, std::equal_to<T>>(left, right_v);
117 case FilterOp::kNe:
118 return internal::SingleSearchNumeric<T, std::not_equal_to<T>>(left,
119 right_v);
120 case FilterOp::kGe:
121 return internal::SingleSearchNumeric<T, std::greater_equal<T>>(left,
122 right_v);
123 case FilterOp::kGt:
124 return internal::SingleSearchNumeric<T, std::greater<T>>(left, right_v);
125 case FilterOp::kLe:
126 return internal::SingleSearchNumeric<T, std::less_equal<T>>(left,
127 right_v);
128 case FilterOp::kLt:
129 return internal::SingleSearchNumeric<T, std::less<T>>(left, right_v);
130 case FilterOp::kIsNotNull:
131 return SingleSearchResult::kMatch;
132 case FilterOp::kGlob:
133 case FilterOp::kRegex:
134 case FilterOp::kIsNull:
135 return SingleSearchResult::kNoMatch;
136 }
137 PERFETTO_FATAL("For GCC");
138 }
139
140 // Used for comparing the integer column ({u|}int{32|64}) with a double value.
141 // If further search is required it would return kOk and change the SqlValue to
142 // a `SqlLong` which would return real results.
143 SearchValidationResult CompareIntColumnWithDouble(FilterOp op,
144 SqlValue* sql_val);
145
146 // If the validation result doesn't require further search, it will return a
147 // Range that can be passed further. Else it returns nullopt.
148 std::optional<Range> CanReturnEarly(SearchValidationResult, Range);
149
150 // If the validation result doesn't require further search, it will return a
151 // Range that can be passed further. Else it returns nullopt.
152 std::optional<Range> CanReturnEarly(SearchValidationResult,
153 uint32_t indices_size);
154
155 // If the validation result doesn't require further search, will modify
156 // |indices| to match and return true. Otherwise returns false.
157 bool CanReturnEarly(SearchValidationResult res,
158 DataLayerChain::Indices& indices);
159
160 std::vector<uint32_t> ExtractPayloadForTesting(std::vector<Token>&);
161
162 std::vector<uint32_t> ToIndexVectorForTests(RangeOrBitVector&);
163
164 std::vector<uint32_t> ExtractPayloadForTesting(const DataLayerChain::Indices&);
165
166 } // namespace perfetto::trace_processor::column::utils
167
168 #endif // SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
169