xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/column/set_id_storage.cc (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc) 
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/set_id_storage.h"
18 
19 #include <algorithm>
20 #include <cstdint>
21 #include <functional>
22 #include <memory>
23 #include <optional>
24 #include <string>
25 #include <unordered_set>
26 #include <utility>
27 #include <vector>
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 
40 namespace perfetto::trace_processor::column {
41 namespace {
42 
43 using SetId = SetIdStorage::SetId;
44 
UpperBoundIntrinsic(const SetId * data,SetId val,Range range)45 uint32_t UpperBoundIntrinsic(const SetId* data, SetId val, Range range) {
46   for (uint32_t i = std::max(range.start, val); i < range.end; i++) {
47     if (data[i] > val) {
48       return i;
49     }
50   }
51   return range.end;
52 }
53 
LowerBoundIntrinsic(const SetId * data,SetId id,Range range)54 uint32_t LowerBoundIntrinsic(const SetId* data, SetId id, Range range) {
55   if (data[range.start] == id) {
56     return range.start;
57   }
58   if (range.Contains(id) && data[id] == id) {
59     return id;
60   }
61   // If none of the above are true, than |id| is not present in data, so we need
62   // to look for the first value higher than |id|.
63   return UpperBoundIntrinsic(data, id, range);
64 }
65 
66 }  // namespace
67 
GetStoragePtr()68 SetIdStorage::StoragePtr SetIdStorage::GetStoragePtr() {
69   return values_->data();
70 }
71 
ChainImpl(const std::vector<uint32_t> * values)72 SetIdStorage::ChainImpl::ChainImpl(const std::vector<uint32_t>* values)
73     : values_(values) {}
74 
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const75 SingleSearchResult SetIdStorage::ChainImpl::SingleSearch(FilterOp op,
76                                                          SqlValue sql_val,
77                                                          uint32_t i) const {
78   return utils::SingleSearchNumeric(op, (*values_)[i], sql_val);
79 }
80 
ValidateSearchConstraints(FilterOp op,SqlValue val) const81 SearchValidationResult SetIdStorage::ChainImpl::ValidateSearchConstraints(
82     FilterOp op,
83     SqlValue val) const {
84   // NULL checks.
85   if (PERFETTO_UNLIKELY(val.is_null())) {
86     if (op == FilterOp::kIsNotNull) {
87       return SearchValidationResult::kAllData;
88     }
89     return SearchValidationResult::kNoData;
90   }
91 
92   // FilterOp checks. Switch so that we get a warning if new FilterOp is not
93   // handled.
94   switch (op) {
95     case FilterOp::kEq:
96     case FilterOp::kNe:
97     case FilterOp::kLt:
98     case FilterOp::kLe:
99     case FilterOp::kGt:
100     case FilterOp::kGe:
101       break;
102     case FilterOp::kIsNull:
103     case FilterOp::kIsNotNull:
104       PERFETTO_FATAL("Invalid constraints.");
105     case FilterOp::kGlob:
106     case FilterOp::kRegex:
107       return SearchValidationResult::kNoData;
108   }
109 
110   if (PERFETTO_UNLIKELY(values_->empty())) {
111     return SearchValidationResult::kNoData;
112   }
113 
114   // Type checks.
115   switch (val.type) {
116     case SqlValue::kNull:
117     case SqlValue::kLong:
118     case SqlValue::kDouble:
119       break;
120     case SqlValue::kString:
121       // Any string is always more than any numeric.
122       if (op == FilterOp::kLt || op == FilterOp::kLe) {
123         return SearchValidationResult::kAllData;
124       }
125       return SearchValidationResult::kNoData;
126     case SqlValue::kBytes:
127       return SearchValidationResult::kNoData;
128   }
129 
130   // Bounds of the value.
131   double num_val = val.type == SqlValue::kLong
132                        ? static_cast<double>(val.AsLong())
133                        : val.AsDouble();
134 
135   // As values are sorted, we can cover special cases for when |num_val| is
136   // bigger than the last value and smaller than the first one.
137   if (PERFETTO_UNLIKELY(num_val > values_->back())) {
138     if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
139       return SearchValidationResult::kAllData;
140     }
141     return SearchValidationResult::kNoData;
142   }
143   if (PERFETTO_UNLIKELY(num_val < values_->front())) {
144     if (op == FilterOp::kGe || op == FilterOp::kGt || op == FilterOp::kNe) {
145       return SearchValidationResult::kAllData;
146     }
147     return SearchValidationResult::kNoData;
148   }
149 
150   return SearchValidationResult::kOk;
151 }
152 
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const153 RangeOrBitVector SetIdStorage::ChainImpl::SearchValidated(
154     FilterOp op,
155     SqlValue sql_val,
156     Range search_range) const {
157   PERFETTO_DCHECK(search_range.end <= size());
158 
159   PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::ChainImpl::Search",
160                     [&search_range, op](metatrace::Record* r) {
161                       r->AddArg("Start", std::to_string(search_range.start));
162                       r->AddArg("End", std::to_string(search_range.end));
163                       r->AddArg("Op",
164                                 std::to_string(static_cast<uint32_t>(op)));
165                     });
166 
167   // It's a valid filter operation if |sql_val| is a double, although it
168   // requires special logic.
169   if (sql_val.type == SqlValue::kDouble) {
170     switch (utils::CompareIntColumnWithDouble(op, &sql_val)) {
171       case SearchValidationResult::kOk:
172         break;
173       case SearchValidationResult::kAllData:
174         return RangeOrBitVector(Range(0, search_range.end));
175       case SearchValidationResult::kNoData:
176         return RangeOrBitVector(Range());
177     }
178   }
179 
180   auto val = static_cast<uint32_t>(sql_val.AsLong());
181   if (op == FilterOp::kNe) {
182     // Not equal is a special operation on binary search, as it doesn't define a
183     // range, and rather just `not` range returned with `equal` operation.
184     Range eq_range = BinarySearchIntrinsic(FilterOp::kEq, val, search_range);
185     BitVector bv(search_range.start, false);
186     bv.Resize(eq_range.start, true);
187     bv.Resize(eq_range.end, false);
188     bv.Resize(search_range.end, true);
189     return RangeOrBitVector(std::move(bv));
190   }
191   return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
192 }
193 
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const194 void SetIdStorage::ChainImpl::IndexSearchValidated(FilterOp op,
195                                                    SqlValue sql_val,
196                                                    Indices& indices) const {
197   PERFETTO_TP_TRACE(
198       metatrace::Category::DB, "SetIdStorage::ChainImpl::IndexSearch",
199       [&indices, op](metatrace::Record* r) {
200         r->AddArg("Count", std::to_string(indices.tokens.size()));
201         r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
202       });
203 
204   // It's a valid filter operation if |sql_val| is a double, although it
205   // requires special logic.
206   if (sql_val.type == SqlValue::kDouble) {
207     if (utils::CanReturnEarly(utils::CompareIntColumnWithDouble(op, &sql_val),
208                               indices)) {
209       return;
210     }
211   }
212 
213   // TODO(mayzner): Instead of utils::IndexSearchWithComparator, use the
214   // property of SetId data - that for each index i, data[i] <= i.
215   auto val = static_cast<uint32_t>(sql_val.AsLong());
216   switch (op) {
217     case FilterOp::kEq:
218       utils::IndexSearchWithComparator(val, values_->data(), indices,
219                                        std::equal_to<>());
220       break;
221     case FilterOp::kNe:
222       utils::IndexSearchWithComparator(val, values_->data(), indices,
223                                        std::not_equal_to<>());
224       break;
225     case FilterOp::kLe:
226       utils::IndexSearchWithComparator(val, values_->data(), indices,
227                                        std::less_equal<>());
228       break;
229     case FilterOp::kLt:
230       utils::IndexSearchWithComparator(val, values_->data(), indices,
231                                        std::less<>());
232       break;
233     case FilterOp::kGt:
234       utils::IndexSearchWithComparator(val, values_->data(), indices,
235                                        std::greater<>());
236       break;
237     case FilterOp::kGe:
238       utils::IndexSearchWithComparator(val, values_->data(), indices,
239                                        std::greater_equal<>());
240       break;
241     case FilterOp::kIsNotNull:
242     case FilterOp::kIsNull:
243     case FilterOp::kGlob:
244     case FilterOp::kRegex:
245       PERFETTO_FATAL("Illegal argument");
246   }
247 }
248 
BinarySearchIntrinsic(FilterOp op,SetId val,Range range) const249 Range SetIdStorage::ChainImpl::BinarySearchIntrinsic(FilterOp op,
250                                                      SetId val,
251                                                      Range range) const {
252   switch (op) {
253     case FilterOp::kEq: {
254       if ((*values_)[val] != val) {
255         return {};
256       }
257       uint32_t start = std::max(val, range.start);
258       uint32_t end = UpperBoundIntrinsic(values_->data(), val, range);
259       return {std::min(start, end), end};
260     }
261     case FilterOp::kLe: {
262       return {range.start, UpperBoundIntrinsic(values_->data(), val, range)};
263     }
264     case FilterOp::kLt:
265       return {range.start, LowerBoundIntrinsic(values_->data(), val, range)};
266     case FilterOp::kGe:
267       return {LowerBoundIntrinsic(values_->data(), val, range), range.end};
268     case FilterOp::kGt:
269       return {UpperBoundIntrinsic(values_->data(), val, range), range.end};
270     case FilterOp::kIsNotNull:
271       return range;
272     case FilterOp::kNe:
273       PERFETTO_FATAL("Shouldn't be called");
274     case FilterOp::kIsNull:
275     case FilterOp::kGlob:
276     case FilterOp::kRegex:
277       return {};
278   }
279   return {};
280 }
281 
StableSort(Token * start,Token * end,SortDirection direction) const282 void SetIdStorage::ChainImpl::StableSort(Token* start,
283                                          Token* end,
284                                          SortDirection direction) const {
285   PERFETTO_TP_TRACE(metatrace::Category::DB,
286                     "SetIdStorage::ChainImpl::StableSort");
287   switch (direction) {
288     case SortDirection::kAscending:
289       std::stable_sort(start, end, [this](const Token& a, const Token& b) {
290         return (*values_)[a.index] < (*values_)[b.index];
291       });
292       break;
293     case SortDirection::kDescending:
294       std::stable_sort(start, end, [this](const Token& a, const Token& b) {
295         return (*values_)[a.index] > (*values_)[b.index];
296       });
297       break;
298   }
299 }
300 
Distinct(Indices & indices) const301 void SetIdStorage::ChainImpl::Distinct(Indices& indices) const {
302   PERFETTO_TP_TRACE(metatrace::Category::DB,
303                     "SetIdStorage::ChainImpl::Distinct");
304   std::unordered_set<uint32_t> s;
305   indices.tokens.erase(
306       std::remove_if(indices.tokens.begin(), indices.tokens.end(),
307                      [&s, this](const Token& idx) {
308                        return !s.insert((*values_)[idx.index]).second;
309                      }),
310       indices.tokens.end());
311 }
312 
MaxElement(Indices & indices) const313 std::optional<Token> SetIdStorage::ChainImpl::MaxElement(
314     Indices& indices) const {
315   PERFETTO_TP_TRACE(metatrace::Category::DB,
316                     "SetIdStorage::ChainImpl::MaxElement");
317 
318   auto tok =
319       std::max_element(indices.tokens.begin(), indices.tokens.end(),
320                        [this](const Token& t1, const Token& t2) {
321                          return (*values_)[t1.index] < (*values_)[t2.index];
322                        });
323 
324   if (tok == indices.tokens.end()) {
325     return std::nullopt;
326   }
327   return *tok;
328 }
329 
MinElement(Indices & indices) const330 std::optional<Token> SetIdStorage::ChainImpl::MinElement(
331     Indices& indices) const {
332   PERFETTO_TP_TRACE(metatrace::Category::DB,
333                     "SetIdStorage::ChainImpl::MinElement");
334   auto tok =
335       std::min_element(indices.tokens.begin(), indices.tokens.end(),
336                        [this](const Token& t1, const Token& t2) {
337                          return (*values_)[t1.index] < (*values_)[t2.index];
338                        });
339   if (tok == indices.tokens.end()) {
340     return std::nullopt;
341   }
342 
343   return *tok;
344 }
345 
Get_AvoidUsingBecauseSlow(uint32_t index) const346 SqlValue SetIdStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
347     uint32_t index) const {
348   return SqlValue::Long((*values_)[index]);
349 }
350 
351 }  // namespace perfetto::trace_processor::column
352