1 /*
2 * Copyright (C) 2024 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/range_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
36 namespace {
37
AddOffsetToTokenIndex(std::vector<Token> & tokens,uint32_t offset)38 void AddOffsetToTokenIndex(std::vector<Token>& tokens, uint32_t offset) {
39 for (auto& token : tokens) {
40 token.index += offset;
41 }
42 }
43
44 } // namespace
45
Flatten(uint32_t * start,const uint32_t * end,uint32_t stride)46 void RangeOverlay::Flatten(uint32_t* start,
47 const uint32_t* end,
48 uint32_t stride) {
49 for (uint32_t* it = start; it < end; it += stride) {
50 *it += range_->start;
51 }
52 }
53
ChainImpl(std::unique_ptr<DataLayerChain> inner,const Range * range)54 RangeOverlay::ChainImpl::ChainImpl(std::unique_ptr<DataLayerChain> inner,
55 const Range* range)
56 : inner_(std::move(inner)), range_(range) {
57 PERFETTO_CHECK(range->end <= inner_->size());
58 }
59
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const60 SingleSearchResult RangeOverlay::ChainImpl::SingleSearch(FilterOp op,
61 SqlValue sql_val,
62 uint32_t i) const {
63 PERFETTO_DCHECK(i < range_->size());
64 return inner_->SingleSearch(op, sql_val, i + range_->start);
65 }
66
ValidateSearchConstraints(FilterOp op,SqlValue sql_val) const67 SearchValidationResult RangeOverlay::ChainImpl::ValidateSearchConstraints(
68 FilterOp op,
69 SqlValue sql_val) const {
70 if (sql_val.is_null() && op != FilterOp::kIsNotNull &&
71 op != FilterOp::kIsNull) {
72 return SearchValidationResult::kNoData;
73 }
74 return inner_->ValidateSearchConstraints(op, sql_val);
75 }
76
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const77 RangeOrBitVector RangeOverlay::ChainImpl::SearchValidated(
78 FilterOp op,
79 SqlValue sql_val,
80 Range search_range) const {
81 PERFETTO_DCHECK(search_range.size() <= range_->size());
82 PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::Search");
83
84 Range inner_search_range(search_range.start + range_->start,
85 search_range.end + range_->start);
86 auto inner_res = inner_->SearchValidated(op, sql_val, inner_search_range);
87 if (inner_res.IsRange()) {
88 Range inner_res_range = std::move(inner_res).TakeIfRange();
89 if (inner_res_range.empty()) {
90 return RangeOrBitVector(Range());
91 }
92 return RangeOrBitVector(Range(inner_res_range.start - range_->start,
93 inner_res_range.end - range_->start));
94 }
95
96 BitVector inner_res_bv = std::move(inner_res).TakeIfBitVector();
97 if (range_->start == 0 && inner_res_bv.size() == range_->end) {
98 return RangeOrBitVector{std::move(inner_res_bv)};
99 }
100
101 PERFETTO_DCHECK(inner_res_bv.size() == inner_search_range.end);
102 PERFETTO_DCHECK(inner_res_bv.CountSetBits(inner_search_range.start) == 0);
103
104 BitVector::Builder builder(search_range.end, search_range.start);
105 uint32_t cur_val = search_range.start;
106 uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
107 for (uint32_t i = 0; i < front_elements; ++i, ++cur_val) {
108 builder.Append(inner_res_bv.IsSet(cur_val + range_->start));
109 }
110
111 // Fast path: we compare as many groups of 64 elements as we can.
112 // This should be very easy for the compiler to auto-vectorize.
113 uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
114 for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
115 uint64_t word = 0;
116 // This part should be optimised by SIMD and is expected to be fast.
117 for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k, ++cur_val) {
118 bool comp_result = inner_res_bv.IsSet(cur_val + range_->start);
119 word |= static_cast<uint64_t>(comp_result) << k;
120 }
121 builder.AppendWord(word);
122 }
123
124 // Slow path: we compare <64 elements and append to fill the Builder.
125 uint32_t back_elements = builder.BitsUntilFull();
126 for (uint32_t i = 0; i < back_elements; ++i, ++cur_val) {
127 builder.Append(inner_res_bv.IsSet(cur_val + range_->start));
128 }
129 return RangeOrBitVector(std::move(builder).Build());
130 }
131
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const132 void RangeOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
133 SqlValue sql_val,
134 Indices& indices) const {
135 PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::IndexSearch");
136 AddOffsetToTokenIndex(indices.tokens, range_->start);
137 inner_->IndexSearchValidated(op, sql_val, indices);
138 }
139
StableSort(Token * start,Token * end,SortDirection direction) const140 void RangeOverlay::ChainImpl::StableSort(Token* start,
141 Token* end,
142 SortDirection direction) const {
143 for (Token* it = start; it != end; ++it) {
144 it->index += range_->start;
145 }
146 inner_->StableSort(start, end, direction);
147 }
148
Distinct(Indices & indices) const149 void RangeOverlay::ChainImpl::Distinct(Indices& indices) const {
150 PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::Distinct");
151 AddOffsetToTokenIndex(indices.tokens, range_->start);
152 inner_->Distinct(indices);
153 }
154
MaxElement(Indices & indices) const155 std::optional<Token> RangeOverlay::ChainImpl::MaxElement(
156 Indices& indices) const {
157 PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::MaxElement");
158 AddOffsetToTokenIndex(indices.tokens, range_->start);
159 return inner_->MaxElement(indices);
160 }
161
MinElement(Indices & indices) const162 std::optional<Token> RangeOverlay::ChainImpl::MinElement(
163 Indices& indices) const {
164 PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::MinElement");
165 AddOffsetToTokenIndex(indices.tokens, range_->start);
166 return inner_->MinElement(indices);
167 }
168
Get_AvoidUsingBecauseSlow(uint32_t index) const169 SqlValue RangeOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
170 uint32_t index) const {
171 return inner_->Get_AvoidUsingBecauseSlow(index + range_->start);
172 }
173
174 } // namespace perfetto::trace_processor::column
175