1 /*
2 * Copyright (C) 2021 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/prelude/table_functions/descendant.h"
18
19 #include <memory>
20 #include <set>
21
22 #include "src/trace_processor/prelude/table_functions/tables_py.h"
23 #include "src/trace_processor/sqlite/sqlite_utils.h"
24 #include "src/trace_processor/types/trace_processor_context.h"
25 #include "src/trace_processor/util/status_macros.h"
26
27 namespace perfetto {
28 namespace trace_processor {
29 namespace tables {
30
31 DescendantSliceTable::~DescendantSliceTable() = default;
32 DescendantSliceByStackTable::~DescendantSliceByStackTable() = default;
33
34 } // namespace tables
35
36 namespace {
37
38 template <typename ChildTable, typename ParentTable, typename ConstraintType>
ExtendWithStartId(ConstraintType constraint_id,const ParentTable & table,std::vector<typename ParentTable::RowNumber> parent_rows)39 std::unique_ptr<Table> ExtendWithStartId(
40 ConstraintType constraint_id,
41 const ParentTable& table,
42 std::vector<typename ParentTable::RowNumber> parent_rows) {
43 ColumnStorage<ConstraintType> start_ids;
44 for (uint32_t i = 0; i < parent_rows.size(); ++i)
45 start_ids.Append(constraint_id);
46 return ChildTable::SelectAndExtendParent(table, std::move(parent_rows),
47 std::move(start_ids));
48 }
49
GetDescendants(const tables::SliceTable & slices,SliceId starting_id,std::vector<tables::SliceTable::RowNumber> & row_numbers_accumulator)50 base::Status GetDescendants(
51 const tables::SliceTable& slices,
52 SliceId starting_id,
53 std::vector<tables::SliceTable::RowNumber>& row_numbers_accumulator) {
54 auto start_ref = slices.FindById(starting_id);
55 // The query gave an invalid ID that doesn't exist in the slice table.
56 if (!start_ref) {
57 return base::ErrStatus("no row with id %" PRIu32 "",
58 static_cast<uint32_t>(starting_id.value));
59 }
60
61 // As an optimization, for any finished slices, we only need to consider
62 // slices which started before the end of this slice (because slices on a
63 // track are always perfectly stacked).
64 // For unfinshed slices (i.e. -1 dur), we need to consider until the end of
65 // the trace so we cannot add any similar constraint.
66 std::vector<Constraint> cs;
67 if (start_ref->dur() >= 0) {
68 cs.emplace_back(slices.ts().le(start_ref->ts() + start_ref->dur()));
69 }
70
71 // All nested descendents must be on the same track, with a ts greater than
72 // |start_ref.ts| and whose depth is larger than |start_ref|'s.
73 cs.emplace_back(slices.ts().ge(start_ref->ts()));
74 cs.emplace_back(slices.track_id().eq(start_ref->track_id().value));
75 cs.emplace_back(slices.depth().gt(start_ref->depth()));
76
77 // It's important we insert directly into |row_numbers_accumulator| and not
78 // overwrite it because we expect the existing elements in
79 // |row_numbers_accumulator| to be preserved.
80 for (auto it = slices.FilterToIterator(cs); it; ++it) {
81 row_numbers_accumulator.emplace_back(it.row_number());
82 }
83 return base::OkStatus();
84 }
85
GetConstraintColumnIndex(Descendant::Type type)86 uint32_t GetConstraintColumnIndex(Descendant::Type type) {
87 switch (type) {
88 case Descendant::Type::kSlice:
89 return tables::DescendantSliceTable::ColumnIndex::start_id;
90 case Descendant::Type::kSliceByStack:
91 return tables::DescendantSliceByStackTable::ColumnIndex::start_stack_id;
92 }
93 PERFETTO_FATAL("For GCC");
94 }
95
96 } // namespace
97
Descendant(Type type,const TraceStorage * storage)98 Descendant::Descendant(Type type, const TraceStorage* storage)
99 : type_(type), storage_(storage) {}
100
ValidateConstraints(const QueryConstraints & qc)101 base::Status Descendant::ValidateConstraints(const QueryConstraints& qc) {
102 const auto& cs = qc.constraints();
103
104 int column = static_cast<int>(GetConstraintColumnIndex(type_));
105 auto id_fn = [column](const QueryConstraints::Constraint& c) {
106 return c.column == column && sqlite_utils::IsOpEq(c.op);
107 };
108 bool has_id_cs = std::find_if(cs.begin(), cs.end(), id_fn) != cs.end();
109 return has_id_cs ? base::OkStatus()
110 : base::ErrStatus("Failed to find required constraints");
111 }
112
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &,const BitVector &,std::unique_ptr<Table> & table_return)113 base::Status Descendant::ComputeTable(const std::vector<Constraint>& cs,
114 const std::vector<Order>&,
115 const BitVector&,
116 std::unique_ptr<Table>& table_return) {
117 const auto& slices = storage_->slice_table();
118
119 uint32_t column = GetConstraintColumnIndex(type_);
120 auto constraint_it =
121 std::find_if(cs.begin(), cs.end(), [column](const Constraint& c) {
122 return c.col_idx == column && c.op == FilterOp::kEq;
123 });
124 if (constraint_it == cs.end()) {
125 return base::ErrStatus("no start id specified.");
126 }
127 if (constraint_it->value.type == SqlValue::Type::kNull) {
128 // Nothing matches a null id so return an empty table.
129 switch (type_) {
130 case Type::kSlice:
131 table_return = tables::DescendantSliceTable::SelectAndExtendParent(
132 storage_->slice_table(), {}, {});
133 break;
134 case Type::kSliceByStack:
135 table_return =
136 tables::DescendantSliceByStackTable::SelectAndExtendParent(
137 storage_->slice_table(), {}, {});
138 break;
139 }
140 return base::OkStatus();
141 }
142 if (constraint_it->value.type != SqlValue::Type::kLong) {
143 return base::ErrStatus("start id should be an integer.");
144 }
145
146 int64_t start_id = constraint_it->value.AsLong();
147 std::vector<tables::SliceTable::RowNumber> descendants;
148 switch (type_) {
149 case Type::kSlice: {
150 // Build up all the children row ids.
151 uint32_t start_id_uint = static_cast<uint32_t>(start_id);
152 RETURN_IF_ERROR(GetDescendants(
153 slices, tables::SliceTable::Id(start_id_uint), descendants));
154 table_return = ExtendWithStartId<tables::DescendantSliceTable>(
155 start_id_uint, slices, std::move(descendants));
156 break;
157 }
158 case Type::kSliceByStack: {
159 auto sbs_cs = {slices.stack_id().eq(start_id)};
160 for (auto it = slices.FilterToIterator(sbs_cs); it; ++it) {
161 RETURN_IF_ERROR(GetDescendants(slices, it.id(), descendants));
162 }
163 table_return = ExtendWithStartId<tables::DescendantSliceByStackTable>(
164 start_id, slices, std::move(descendants));
165 break;
166 }
167 }
168
169 return base::OkStatus();
170 }
171
CreateSchema()172 Table::Schema Descendant::CreateSchema() {
173 switch (type_) {
174 case Type::kSlice:
175 return tables::DescendantSliceTable::ComputeStaticSchema();
176 case Type::kSliceByStack:
177 return tables::DescendantSliceByStackTable::ComputeStaticSchema();
178 }
179 PERFETTO_FATAL("For GCC");
180 }
181
TableName()182 std::string Descendant::TableName() {
183 switch (type_) {
184 case Type::kSlice:
185 return tables::DescendantSliceTable::Name();
186 case Type::kSliceByStack:
187 return tables::DescendantSliceByStackTable::Name();
188 }
189 PERFETTO_FATAL("For GCC");
190 }
191
EstimateRowCount()192 uint32_t Descendant::EstimateRowCount() {
193 return 1;
194 }
195
196 // static
197 std::optional<std::vector<tables::SliceTable::RowNumber>>
GetDescendantSlices(const tables::SliceTable & slices,SliceId slice_id)198 Descendant::GetDescendantSlices(const tables::SliceTable& slices,
199 SliceId slice_id) {
200 std::vector<tables::SliceTable::RowNumber> ret;
201 auto status = GetDescendants(slices, slice_id, ret);
202 if (!status.ok())
203 return std::nullopt;
204 return std::move(ret);
205 }
206
207 } // namespace trace_processor
208 } // namespace perfetto
209