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 #include "protos/perfetto/trace_processor/serialization.pbzero.h"
34
35 namespace perfetto::trace_processor::column {
36 namespace {
37
38 constexpr uint32_t kIndexOfNthSetRatio = 32;
39
40 } // namespace
41
ChainImpl(std::unique_ptr<DataLayerChain> inner,const BitVector * selector)42 SelectorOverlay::ChainImpl::ChainImpl(std::unique_ptr<DataLayerChain> inner,
43 const BitVector* selector)
44 : inner_(std::move(inner)), selector_(selector) {}
45
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const46 SingleSearchResult SelectorOverlay::ChainImpl::SingleSearch(FilterOp op,
47 SqlValue sql_val,
48 uint32_t i) const {
49 return inner_->SingleSearch(op, sql_val, selector_->IndexOfNthSet(i));
50 }
51
ValidateSearchConstraints(FilterOp op,SqlValue sql_val) const52 SearchValidationResult SelectorOverlay::ChainImpl::ValidateSearchConstraints(
53 FilterOp op,
54 SqlValue sql_val) const {
55 return inner_->ValidateSearchConstraints(op, sql_val);
56 }
57
SearchValidated(FilterOp op,SqlValue sql_val,Range in) const58 RangeOrBitVector SelectorOverlay::ChainImpl::SearchValidated(FilterOp op,
59 SqlValue sql_val,
60 Range in) const {
61 PERFETTO_TP_TRACE(metatrace::Category::DB,
62 "SelectorOverlay::ChainImpl::Search");
63
64 // Figure out the bounds of the OrderedIndices in the underlying storage and
65 // search it.
66 uint32_t start_idx = selector_->IndexOfNthSet(in.start);
67 uint32_t end_idx = selector_->IndexOfNthSet(in.end - 1) + 1;
68
69 auto storage_result =
70 inner_->SearchValidated(op, sql_val, Range(start_idx, end_idx));
71 if (storage_result.IsRange()) {
72 Range storage_range = std::move(storage_result).TakeIfRange();
73 if (storage_range.empty()) {
74 return RangeOrBitVector(Range());
75 }
76 uint32_t out_start = selector_->CountSetBits(storage_range.start);
77 uint32_t out_end = selector_->CountSetBits(storage_range.end);
78 return RangeOrBitVector(Range(out_start, out_end));
79 }
80
81 BitVector storage_bitvector = std::move(storage_result).TakeIfBitVector();
82 PERFETTO_DCHECK(storage_bitvector.size() <= selector_->size());
83 storage_bitvector.SelectBits(*selector_);
84 if (storage_bitvector.size() == 0) {
85 return RangeOrBitVector(std::move(storage_bitvector));
86 }
87 PERFETTO_DCHECK(storage_bitvector.size() == in.end);
88 return RangeOrBitVector(std::move(storage_bitvector));
89 }
90
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const91 void SelectorOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
92 SqlValue sql_val,
93 Indices& indices) const {
94 PERFETTO_TP_TRACE(metatrace::Category::DB,
95 "SelectorOverlay::ChainImpl::IndexSearch");
96 TranslateToInnerIndices(indices);
97 return inner_->IndexSearchValidated(op, sql_val, indices);
98 }
99
StableSort(SortToken * start,SortToken * end,SortDirection direction) const100 void SelectorOverlay::ChainImpl::StableSort(SortToken* start,
101 SortToken* end,
102 SortDirection direction) const {
103 PERFETTO_TP_TRACE(metatrace::Category::DB,
104 "SelectorOverlay::ChainImpl::StableSort");
105 for (SortToken* it = start; it != end; ++it) {
106 it->index = selector_->IndexOfNthSet(it->index);
107 }
108 inner_->StableSort(start, end, direction);
109 }
110
Distinct(Indices & indices) const111 void SelectorOverlay::ChainImpl::Distinct(Indices& indices) const {
112 PERFETTO_TP_TRACE(metatrace::Category::DB,
113 "SelectorOverlay::ChainImpl::Distinct");
114 TranslateToInnerIndices(indices);
115 return inner_->Distinct(indices);
116 }
117
MaxElement(Indices & indices) const118 std::optional<Token> SelectorOverlay::ChainImpl::MaxElement(
119 Indices& indices) const {
120 PERFETTO_TP_TRACE(metatrace::Category::DB,
121 "SelectorOverlay::ChainImpl::MaxElement");
122 TranslateToInnerIndices(indices);
123 return inner_->MaxElement(indices);
124 }
125
MinElement(Indices & indices) const126 std::optional<Token> SelectorOverlay::ChainImpl::MinElement(
127 Indices& indices) const {
128 PERFETTO_TP_TRACE(metatrace::Category::DB,
129 "SelectorOverlay::ChainImpl::MinElement");
130 TranslateToInnerIndices(indices);
131 return inner_->MinElement(indices);
132 }
133
Get_AvoidUsingBecauseSlow(uint32_t index) const134 SqlValue SelectorOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
135 uint32_t index) const {
136 return inner_->Get_AvoidUsingBecauseSlow(selector_->IndexOfNthSet(index));
137 }
138
Serialize(StorageProto * storage) const139 void SelectorOverlay::ChainImpl::Serialize(StorageProto* storage) const {
140 auto* selector_overlay = storage->set_selector_overlay();
141 inner_->Serialize(selector_overlay->set_storage());
142 selector_->Serialize(selector_overlay->set_bit_vector());
143 }
144
TranslateToInnerIndices(Indices & indices) const145 void SelectorOverlay::ChainImpl::TranslateToInnerIndices(
146 Indices& indices) const {
147 if (selector_->size() == selector_->CountSetBits()) {
148 return;
149 }
150
151 if (indices.tokens.size() < selector_->size() / kIndexOfNthSetRatio) {
152 for (auto& token : indices.tokens) {
153 token.index = selector_->IndexOfNthSet(token.index);
154 }
155 return;
156 }
157
158 // TODO(mayzner): once we have a reverse index for IndexOfNthSet in
159 // BitVector, this should no longer be necessary.
160 std::vector<uint32_t> lookup = selector_->GetSetBitIndices();
161 for (auto& token : indices.tokens) {
162 token.index = lookup[token.index];
163 }
164 }
165
166 } // namespace perfetto::trace_processor::column
167