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