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/selector_overlay.h"
18
19 #include <cstdint>
20 #include <memory>
21 #include <optional>
22 #include <utility>
23 #include <vector>
24
25 #include "perfetto/base/logging.h"
26 #include "perfetto/trace_processor/basic_types.h"
27 #include "src/trace_processor/containers/bit_vector.h"
28 #include "src/trace_processor/db/column/data_layer.h"
29 #include "src/trace_processor/db/column/types.h"
30 #include "src/trace_processor/tp_metatrace.h"
31
32 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
33
34 namespace perfetto::trace_processor::column {
35 namespace {
36
37 constexpr uint32_t kIndexOfNthSetRatio = 32;
38
TranslateToInnerIndices(const BitVector & selector,std::vector<Token> & tokens)39 void TranslateToInnerIndices(const BitVector& selector,
40 std::vector<Token>& tokens) {
41 if (selector.size() == selector.CountSetBits()) {
42 return;
43 }
44 if (tokens.size() < selector.size() / kIndexOfNthSetRatio) {
45 for (auto& token : tokens) {
46 token.index = selector.IndexOfNthSet(token.index);
47 }
48 return;
49 }
50 // TODO(mayzner): once we have a reverse index for IndexOfNthSet in
51 // BitVector, this should no longer be necessary.
52 std::vector<uint32_t> lookup = selector.GetSetBitIndices();
53 for (auto& token : tokens) {
54 token.index = lookup[token.index];
55 }
56 }
57
TranslateToInnerIndices(const BitVector & selector,uint32_t * start,const uint32_t * end,uint32_t stride)58 void TranslateToInnerIndices(const BitVector& selector,
59 uint32_t* start,
60 const uint32_t* end,
61 uint32_t stride) {
62 if (selector.size() == selector.CountSetBits()) {
63 return;
64 }
65 auto size = static_cast<uint32_t>(end - start);
66 if (size < selector.size() / kIndexOfNthSetRatio) {
67 for (uint32_t* it = start; it < end; it += stride) {
68 *it = selector.IndexOfNthSet(*it);
69 }
70 return;
71 }
72 // TODO(mayzner): once we have a reverse index for IndexOfNthSet in
73 // BitVector, this should no longer be necessary.
74 std::vector<uint32_t> lookup = selector.GetSetBitIndices();
75 for (uint32_t* it = start; it < end; it += stride) {
76 *it = lookup[*it];
77 }
78 }
79
80 } // namespace
81
Flatten(uint32_t * start,const uint32_t * end,uint32_t stride)82 void SelectorOverlay::Flatten(uint32_t* start,
83 const uint32_t* end,
84 uint32_t stride) {
85 TranslateToInnerIndices(*selector_, start, end, stride);
86 }
87
ChainImpl(std::unique_ptr<DataLayerChain> inner,const BitVector * selector)88 SelectorOverlay::ChainImpl::ChainImpl(std::unique_ptr<DataLayerChain> inner,
89 const BitVector* selector)
90 : inner_(std::move(inner)), selector_(selector) {}
91
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const92 SingleSearchResult SelectorOverlay::ChainImpl::SingleSearch(FilterOp op,
93 SqlValue sql_val,
94 uint32_t i) const {
95 return inner_->SingleSearch(op, sql_val, selector_->IndexOfNthSet(i));
96 }
97
ValidateSearchConstraints(FilterOp op,SqlValue sql_val) const98 SearchValidationResult SelectorOverlay::ChainImpl::ValidateSearchConstraints(
99 FilterOp op,
100 SqlValue sql_val) const {
101 if (sql_val.is_null() && op != FilterOp::kIsNotNull &&
102 op != FilterOp::kIsNull) {
103 return SearchValidationResult::kNoData;
104 }
105 return inner_->ValidateSearchConstraints(op, sql_val);
106 }
107
SearchValidated(FilterOp op,SqlValue sql_val,Range in) const108 RangeOrBitVector SelectorOverlay::ChainImpl::SearchValidated(FilterOp op,
109 SqlValue sql_val,
110 Range in) const {
111 PERFETTO_TP_TRACE(metatrace::Category::DB,
112 "SelectorOverlay::ChainImpl::Search");
113
114 // Figure out the bounds of the indicess in the underlying storage and
115 // search it.
116 uint32_t start_idx = selector_->IndexOfNthSet(in.start);
117 uint32_t end_idx = selector_->IndexOfNthSet(in.end - 1) + 1;
118
119 auto storage_result =
120 inner_->SearchValidated(op, sql_val, Range(start_idx, end_idx));
121 if (storage_result.IsRange()) {
122 Range storage_range = std::move(storage_result).TakeIfRange();
123 if (storage_range.empty()) {
124 return RangeOrBitVector(Range());
125 }
126 uint32_t out_start = selector_->CountSetBits(storage_range.start);
127 uint32_t out_end = selector_->CountSetBits(storage_range.end);
128 return RangeOrBitVector(Range(out_start, out_end));
129 }
130
131 BitVector storage_bitvector = std::move(storage_result).TakeIfBitVector();
132 PERFETTO_DCHECK(storage_bitvector.size() <= selector_->size());
133 storage_bitvector.SelectBits(*selector_);
134 if (storage_bitvector.size() == 0) {
135 return RangeOrBitVector(std::move(storage_bitvector));
136 }
137 PERFETTO_DCHECK(storage_bitvector.size() == in.end);
138 return RangeOrBitVector(std::move(storage_bitvector));
139 }
140
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const141 void SelectorOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
142 SqlValue sql_val,
143 Indices& indices) const {
144 PERFETTO_TP_TRACE(metatrace::Category::DB,
145 "SelectorOverlay::ChainImpl::IndexSearch");
146 TranslateToInnerIndices(*selector_, indices.tokens);
147 return inner_->IndexSearchValidated(op, sql_val, indices);
148 }
149
StableSort(Token * start,Token * end,SortDirection direction) const150 void SelectorOverlay::ChainImpl::StableSort(Token* start,
151 Token* end,
152 SortDirection direction) const {
153 PERFETTO_TP_TRACE(metatrace::Category::DB,
154 "SelectorOverlay::ChainImpl::StableSort");
155 for (Token* it = start; it != end; ++it) {
156 it->index = selector_->IndexOfNthSet(it->index);
157 }
158 inner_->StableSort(start, end, direction);
159 }
160
Distinct(Indices & indices) const161 void SelectorOverlay::ChainImpl::Distinct(Indices& indices) const {
162 PERFETTO_TP_TRACE(metatrace::Category::DB,
163 "SelectorOverlay::ChainImpl::Distinct");
164 TranslateToInnerIndices(*selector_, indices.tokens);
165 return inner_->Distinct(indices);
166 }
167
MaxElement(Indices & indices) const168 std::optional<Token> SelectorOverlay::ChainImpl::MaxElement(
169 Indices& indices) const {
170 PERFETTO_TP_TRACE(metatrace::Category::DB,
171 "SelectorOverlay::ChainImpl::MaxElement");
172 TranslateToInnerIndices(*selector_, indices.tokens);
173 return inner_->MaxElement(indices);
174 }
175
MinElement(Indices & indices) const176 std::optional<Token> SelectorOverlay::ChainImpl::MinElement(
177 Indices& indices) const {
178 PERFETTO_TP_TRACE(metatrace::Category::DB,
179 "SelectorOverlay::ChainImpl::MinElement");
180 TranslateToInnerIndices(*selector_, indices.tokens);
181 return inner_->MinElement(indices);
182 }
183
Get_AvoidUsingBecauseSlow(uint32_t index) const184 SqlValue SelectorOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
185 uint32_t index) const {
186 return inner_->Get_AvoidUsingBecauseSlow(selector_->IndexOfNthSet(index));
187 }
188
189 } // namespace perfetto::trace_processor::column
190