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/id_storage.h"
18
19 #include <algorithm>
20 #include <cstdint>
21 #include <functional>
22 #include <iterator>
23 #include <limits>
24 #include <optional>
25 #include <string>
26 #include <unordered_set>
27 #include <utility>
28
29 #include "perfetto/base/logging.h"
30 #include "perfetto/public/compiler.h"
31 #include "perfetto/trace_processor/basic_types.h"
32 #include "src/trace_processor/containers/bit_vector.h"
33 #include "src/trace_processor/db/column/data_layer.h"
34 #include "src/trace_processor/db/column/types.h"
35 #include "src/trace_processor/db/column/utils.h"
36 #include "src/trace_processor/tp_metatrace.h"
37
38 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
39 #include "protos/perfetto/trace_processor/serialization.pbzero.h"
40
41 namespace perfetto::trace_processor::column {
42 namespace {
43
44 template <typename Comparator>
IndexSearchWithComparator(uint32_t val,DataLayerChain::Indices & indices)45 void IndexSearchWithComparator(uint32_t val, DataLayerChain::Indices& indices) {
46 indices.tokens.erase(
47 std::remove_if(
48 indices.tokens.begin(), indices.tokens.end(),
49 [val](const Token& idx) { return !Comparator()(idx.index, val); }),
50 indices.tokens.end());
51 }
52
53 } // namespace
54
ValidateSearchConstraints(FilterOp op,SqlValue val) const55 SearchValidationResult IdStorage::ChainImpl::ValidateSearchConstraints(
56 FilterOp op,
57 SqlValue val) const {
58 // NULL checks.
59 if (PERFETTO_UNLIKELY(val.is_null())) {
60 if (op == FilterOp::kIsNotNull) {
61 return SearchValidationResult::kAllData;
62 }
63 if (op == FilterOp::kIsNull) {
64 return SearchValidationResult::kNoData;
65 }
66 PERFETTO_DFATAL(
67 "Invalid filter operation. NULL should only be compared with 'IS NULL' "
68 "and 'IS NOT NULL'");
69 return SearchValidationResult::kNoData;
70 }
71
72 // FilterOp checks. Switch so that we get a warning if new FilterOp is not
73 // handled.
74 switch (op) {
75 case FilterOp::kEq:
76 case FilterOp::kNe:
77 case FilterOp::kLt:
78 case FilterOp::kLe:
79 case FilterOp::kGt:
80 case FilterOp::kGe:
81 break;
82 case FilterOp::kIsNull:
83 case FilterOp::kIsNotNull:
84 PERFETTO_FATAL("Invalid constraint");
85 case FilterOp::kGlob:
86 case FilterOp::kRegex:
87 return SearchValidationResult::kNoData;
88 }
89
90 // Type checks.
91 switch (val.type) {
92 case SqlValue::kNull:
93 case SqlValue::kLong:
94 case SqlValue::kDouble:
95 break;
96 case SqlValue::kString:
97 // Any string is always more than any numeric.
98 if (op == FilterOp::kLt || op == FilterOp::kLe) {
99 return SearchValidationResult::kAllData;
100 }
101 return SearchValidationResult::kNoData;
102 case SqlValue::kBytes:
103 return SearchValidationResult::kNoData;
104 }
105
106 // Bounds of the value.
107 double num_val = val.type == SqlValue::kLong
108 ? static_cast<double>(val.AsLong())
109 : val.AsDouble();
110
111 if (PERFETTO_UNLIKELY(num_val > std::numeric_limits<uint32_t>::max())) {
112 if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
113 return SearchValidationResult::kAllData;
114 }
115 return SearchValidationResult::kNoData;
116 }
117 if (PERFETTO_UNLIKELY(num_val < std::numeric_limits<uint32_t>::min())) {
118 if (op == FilterOp::kGe || op == FilterOp::kGt || op == FilterOp::kNe) {
119 return SearchValidationResult::kAllData;
120 }
121 return SearchValidationResult::kNoData;
122 }
123
124 return SearchValidationResult::kOk;
125 }
126
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t index) const127 SingleSearchResult IdStorage::ChainImpl::SingleSearch(FilterOp op,
128 SqlValue sql_val,
129 uint32_t index) const {
130 if (sql_val.type != SqlValue::kLong ||
131 sql_val.long_value > std::numeric_limits<uint32_t>::max() ||
132 sql_val.long_value < std::numeric_limits<uint32_t>::min()) {
133 // Because of the large amount of code needing for handling comparisions
134 // with doubles or out of range values, just defer to the full search.
135 return SingleSearchResult::kNeedsFullSearch;
136 }
137 auto val = static_cast<uint32_t>(sql_val.long_value);
138 switch (op) {
139 case FilterOp::kEq:
140 return index == val ? SingleSearchResult::kMatch
141 : SingleSearchResult::kNoMatch;
142 case FilterOp::kNe:
143 return index != val ? SingleSearchResult::kMatch
144 : SingleSearchResult::kNoMatch;
145 case FilterOp::kGe:
146 return index >= val ? SingleSearchResult::kMatch
147 : SingleSearchResult::kNoMatch;
148 case FilterOp::kGt:
149 return index > val ? SingleSearchResult::kMatch
150 : SingleSearchResult::kNoMatch;
151 case FilterOp::kLe:
152 return index <= val ? SingleSearchResult::kMatch
153 : SingleSearchResult::kNoMatch;
154 case FilterOp::kLt:
155 return index < val ? SingleSearchResult::kMatch
156 : SingleSearchResult::kNoMatch;
157 case FilterOp::kIsNotNull:
158 return SingleSearchResult::kMatch;
159 case FilterOp::kIsNull:
160 case FilterOp::kGlob:
161 case FilterOp::kRegex:
162 return SingleSearchResult::kNoMatch;
163 }
164 PERFETTO_FATAL("For GCC");
165 }
166
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const167 RangeOrBitVector IdStorage::ChainImpl::SearchValidated(
168 FilterOp op,
169 SqlValue sql_val,
170 Range search_range) const {
171 PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::ChainImpl::Search",
172 [&search_range, op](metatrace::Record* r) {
173 r->AddArg("Start", std::to_string(search_range.start));
174 r->AddArg("End", std::to_string(search_range.end));
175 r->AddArg("Op",
176 std::to_string(static_cast<uint32_t>(op)));
177 });
178
179 // It's a valid filter operation if |sql_val| is a double, although it
180 // requires special logic.
181 if (sql_val.type == SqlValue::kDouble) {
182 switch (utils::CompareIntColumnWithDouble(op, &sql_val)) {
183 case SearchValidationResult::kOk:
184 break;
185 case SearchValidationResult::kAllData:
186 return RangeOrBitVector(Range(0, search_range.end));
187 case SearchValidationResult::kNoData:
188 return RangeOrBitVector(Range());
189 }
190 }
191
192 auto val = static_cast<uint32_t>(sql_val.AsLong());
193 if (op == FilterOp::kNe) {
194 BitVector ret(search_range.start, false);
195 ret.Resize(search_range.end, true);
196 ret.Clear(val);
197 return RangeOrBitVector(std::move(ret));
198 }
199 return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
200 }
201
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const202 void IdStorage::ChainImpl::IndexSearchValidated(FilterOp op,
203 SqlValue sql_val,
204 Indices& indices) const {
205 PERFETTO_TP_TRACE(
206 metatrace::Category::DB, "IdStorage::ChainImpl::IndexSearch",
207 [&indices, op](metatrace::Record* r) {
208 r->AddArg("Count", std::to_string(indices.tokens.size()));
209 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
210 });
211
212 // It's a valid filter operation if |sql_val| is a double, although it
213 // requires special logic.
214 if (sql_val.type == SqlValue::kDouble) {
215 switch (utils::CompareIntColumnWithDouble(op, &sql_val)) {
216 case SearchValidationResult::kAllData:
217 return;
218 case SearchValidationResult::kNoData:
219 indices.tokens.clear();
220 return;
221 case SearchValidationResult::kOk:
222 break;
223 }
224 }
225
226 auto val = static_cast<uint32_t>(sql_val.AsLong());
227 switch (op) {
228 case FilterOp::kEq:
229 return IndexSearchWithComparator<std::equal_to<>>(val, indices);
230 case FilterOp::kNe:
231 return IndexSearchWithComparator<std::not_equal_to<>>(val, indices);
232 case FilterOp::kLe:
233 return IndexSearchWithComparator<std::less_equal<>>(val, indices);
234 case FilterOp::kLt:
235 return IndexSearchWithComparator<std::less<>>(val, indices);
236 case FilterOp::kGt:
237 return IndexSearchWithComparator<std::greater<>>(val, indices);
238 case FilterOp::kGe:
239 return IndexSearchWithComparator<std::greater_equal<>>(val, indices);
240 case FilterOp::kIsNotNull:
241 case FilterOp::kIsNull:
242 case FilterOp::kGlob:
243 case FilterOp::kRegex:
244 PERFETTO_FATAL("Invalid filter operation");
245 }
246 PERFETTO_FATAL("FilterOp not matched");
247 }
248
BinarySearchIntrinsic(FilterOp op,Id val,Range range)249 Range IdStorage::ChainImpl::BinarySearchIntrinsic(FilterOp op,
250 Id val,
251 Range range) {
252 switch (op) {
253 case FilterOp::kEq:
254 return {val, val + (range.start <= val && val < range.end)};
255 case FilterOp::kLe:
256 return {range.start, std::clamp(val + 1, range.start, range.end)};
257 case FilterOp::kLt:
258 return {range.start, std::clamp(val, range.start, range.end)};
259 case FilterOp::kGe:
260 return {std::clamp(val, range.start, range.end), range.end};
261 case FilterOp::kGt:
262 return {std::clamp(val + 1, range.start, range.end), range.end};
263 case FilterOp::kIsNotNull:
264 case FilterOp::kNe:
265 case FilterOp::kIsNull:
266 case FilterOp::kGlob:
267 case FilterOp::kRegex:
268 PERFETTO_FATAL("Invalid filter operation");
269 }
270 PERFETTO_FATAL("FilterOp not matched");
271 }
272
StableSort(SortToken * start,SortToken * end,SortDirection direction) const273 void IdStorage::ChainImpl::StableSort(SortToken* start,
274 SortToken* end,
275 SortDirection direction) const {
276 PERFETTO_TP_TRACE(metatrace::Category::DB,
277 "IdStorage::ChainImpl::StableSort");
278 switch (direction) {
279 case SortDirection::kAscending:
280 std::stable_sort(start, end, [](const SortToken& a, const SortToken& b) {
281 return a.index < b.index;
282 });
283 return;
284 case SortDirection::kDescending:
285 std::stable_sort(start, end, [](const SortToken& a, const SortToken& b) {
286 return a.index > b.index;
287 });
288 return;
289 }
290 PERFETTO_FATAL("For GCC");
291 }
292
Distinct(Indices & indices) const293 void IdStorage::ChainImpl::Distinct(Indices& indices) const {
294 PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::ChainImpl::Distinct");
295 std::unordered_set<uint32_t> s;
296 indices.tokens.erase(
297 std::remove_if(
298 indices.tokens.begin(), indices.tokens.end(),
299 [&s](const Token& idx) { return !s.insert(idx.index).second; }),
300 indices.tokens.end());
301 }
302
MaxElement(Indices & indices) const303 std::optional<Token> IdStorage::ChainImpl::MaxElement(Indices& indices) const {
304 PERFETTO_TP_TRACE(metatrace::Category::DB,
305 "IdStorage::ChainImpl::MaxElement");
306 auto tok = std::max_element(
307 indices.tokens.begin(), indices.tokens.end(),
308 [](const Token& a, const Token& b) { return a.index < b.index; });
309 return (tok == indices.tokens.end()) ? std::nullopt
310 : std::make_optional(*tok);
311 }
312
MinElement(Indices & indices) const313 std::optional<Token> IdStorage::ChainImpl::MinElement(Indices& indices) const {
314 PERFETTO_TP_TRACE(metatrace::Category::DB,
315 "IdStorage::ChainImpl::MinElement");
316 auto tok = std::min_element(
317 indices.tokens.begin(), indices.tokens.end(),
318 [](const Token& a, const Token& b) { return a.index > b.index; });
319 if (tok == indices.tokens.end()) {
320 return std::nullopt;
321 }
322 return *tok;
323 }
324
Get_AvoidUsingBecauseSlow(uint32_t index) const325 SqlValue IdStorage::ChainImpl::Get_AvoidUsingBecauseSlow(uint32_t index) const {
326 return SqlValue::Long(index);
327 }
328
Serialize(StorageProto * storage) const329 void IdStorage::ChainImpl::Serialize(StorageProto* storage) const {
330 storage->set_id_storage();
331 }
332
333 } // namespace perfetto::trace_processor::column
334