1 /*
2 * Copyright (C) 2020 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/ancestor.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 AncestorSliceTable::~AncestorSliceTable() = default;
32 AncestorStackProfileCallsiteTable::~AncestorStackProfileCallsiteTable() =
33 default;
34 AncestorSliceByStackTable::~AncestorSliceByStackTable() = default;
35
36 } // namespace tables
37
38 namespace {
39
GetConstraintColumnIndex(Ancestor::Type type)40 uint32_t GetConstraintColumnIndex(Ancestor::Type type) {
41 switch (type) {
42 case Ancestor::Type::kSlice:
43 return tables::AncestorSliceTable::ColumnIndex::start_id;
44 case Ancestor::Type::kStackProfileCallsite:
45 return tables::AncestorStackProfileCallsiteTable::ColumnIndex::start_id;
46 case Ancestor::Type::kSliceByStack:
47 return tables::AncestorSliceByStackTable::ColumnIndex::start_stack_id;
48 }
49 PERFETTO_FATAL("For GCC");
50 }
51
52 template <typename T>
GetAncestors(const T & table,typename T::Id starting_id,std::vector<typename T::RowNumber> & row_numbers_accumulator)53 base::Status GetAncestors(
54 const T& table,
55 typename T::Id starting_id,
56 std::vector<typename T::RowNumber>& row_numbers_accumulator) {
57 auto start_ref = table.FindById(starting_id);
58 if (!start_ref) {
59 return base::ErrStatus("no row with id %" PRIu32 "",
60 static_cast<uint32_t>(starting_id.value));
61 }
62
63 // It's important we insert directly into |row_numbers_accumulator| and not
64 // overwrite it because we expect the existing elements in
65 // |row_numbers_accumulator| to be preserved.
66 auto maybe_parent_id = start_ref->parent_id();
67 while (maybe_parent_id) {
68 auto ref = *table.FindById(*maybe_parent_id);
69 row_numbers_accumulator.emplace_back(ref.ToRowNumber());
70 // Update the loop variable by looking up the next parent_id.
71 maybe_parent_id = ref.parent_id();
72 }
73 return base::OkStatus();
74 }
75
76 template <typename ChildTable, typename ConstraintType, typename ParentTable>
ExtendWithStartId(ConstraintType constraint_value,const ParentTable & table,std::vector<typename ParentTable::RowNumber> parent_rows)77 std::unique_ptr<Table> ExtendWithStartId(
78 ConstraintType constraint_value,
79 const ParentTable& table,
80 std::vector<typename ParentTable::RowNumber> parent_rows) {
81 ColumnStorage<ConstraintType> start_ids;
82 for (uint32_t i = 0; i < parent_rows.size(); ++i)
83 start_ids.Append(constraint_value);
84 return ChildTable::SelectAndExtendParent(table, std::move(parent_rows),
85 std::move(start_ids));
86 }
87
88 template <typename ChildTable, typename ParentTable>
BuildAncestorsTable(typename ParentTable::Id id,const ParentTable & table,std::unique_ptr<Table> & table_return)89 base::Status BuildAncestorsTable(typename ParentTable::Id id,
90 const ParentTable& table,
91 std::unique_ptr<Table>& table_return) {
92 // Build up all the parents row ids.
93 std::vector<typename ParentTable::RowNumber> ancestors;
94 RETURN_IF_ERROR(GetAncestors(table, id, ancestors));
95 table_return =
96 ExtendWithStartId<ChildTable>(id.value, table, std::move(ancestors));
97 return base::OkStatus();
98 }
99
100 } // namespace
101
Ancestor(Type type,const TraceStorage * storage)102 Ancestor::Ancestor(Type type, const TraceStorage* storage)
103 : type_(type), storage_(storage) {}
104
ValidateConstraints(const QueryConstraints & qc)105 base::Status Ancestor::ValidateConstraints(const QueryConstraints& qc) {
106 const auto& cs = qc.constraints();
107
108 int column = static_cast<int>(GetConstraintColumnIndex(type_));
109 auto id_fn = [column](const QueryConstraints::Constraint& c) {
110 return c.column == column && sqlite_utils::IsOpEq(c.op);
111 };
112 bool has_id_cs = std::find_if(cs.begin(), cs.end(), id_fn) != cs.end();
113 return has_id_cs ? base::OkStatus()
114 : base::ErrStatus("Failed to find required constraints");
115 }
116
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &,const BitVector &,std::unique_ptr<Table> & table_return)117 base::Status Ancestor::ComputeTable(const std::vector<Constraint>& cs,
118 const std::vector<Order>&,
119 const BitVector&,
120 std::unique_ptr<Table>& table_return) {
121 uint32_t column = GetConstraintColumnIndex(type_);
122 auto constraint_it =
123 std::find_if(cs.begin(), cs.end(), [column](const Constraint& c) {
124 return c.col_idx == column && c.op == FilterOp::kEq;
125 });
126 if (constraint_it == cs.end()) {
127 return base::ErrStatus("no start id specified.");
128 }
129 if (constraint_it->value.type == SqlValue::Type::kNull) {
130 // Nothing matches a null id so return an empty table.
131 switch (type_) {
132 case Type::kSlice:
133 table_return = tables::AncestorSliceTable::SelectAndExtendParent(
134 storage_->slice_table(), {}, {});
135 break;
136 case Type::kStackProfileCallsite:
137 table_return =
138 tables::AncestorStackProfileCallsiteTable::SelectAndExtendParent(
139 storage_->stack_profile_callsite_table(), {}, {});
140 break;
141 case Type::kSliceByStack:
142 table_return = tables::AncestorSliceByStackTable::SelectAndExtendParent(
143 storage_->slice_table(), {}, {});
144 break;
145 }
146 return base::OkStatus();
147 }
148 if (constraint_it->value.type != SqlValue::Type::kLong) {
149 return base::ErrStatus("start id should be an integer.");
150 }
151
152 int64_t start_id = constraint_it->value.AsLong();
153 uint32_t start_id_uint = static_cast<uint32_t>(start_id);
154 switch (type_) {
155 case Type::kSlice:
156 return BuildAncestorsTable<tables::AncestorSliceTable>(
157 SliceId(start_id_uint), storage_->slice_table(), table_return);
158
159 case Type::kStackProfileCallsite:
160 return BuildAncestorsTable<tables::AncestorStackProfileCallsiteTable>(
161 CallsiteId(start_id_uint), storage_->stack_profile_callsite_table(),
162 table_return);
163
164 case Type::kSliceByStack: {
165 // Find the all slice ids that have the stack id and find all the
166 // ancestors of the slice ids.
167 const auto& slice_table = storage_->slice_table();
168 auto it =
169 slice_table.FilterToIterator({slice_table.stack_id().eq(start_id)});
170 std::vector<tables::SliceTable::RowNumber> ancestors;
171 for (; it; ++it) {
172 RETURN_IF_ERROR(GetAncestors(slice_table, it.id(), ancestors));
173 }
174 // Sort to keep the slices in timestamp order.
175 std::sort(ancestors.begin(), ancestors.end());
176 table_return = ExtendWithStartId<tables::AncestorSliceByStackTable>(
177 start_id, slice_table, std::move(ancestors));
178 return base::OkStatus();
179 }
180 }
181 PERFETTO_FATAL("For GCC");
182 }
183
CreateSchema()184 Table::Schema Ancestor::CreateSchema() {
185 switch (type_) {
186 case Type::kSlice:
187 return tables::AncestorSliceTable::ComputeStaticSchema();
188 case Type::kStackProfileCallsite:
189 return tables::AncestorStackProfileCallsiteTable::ComputeStaticSchema();
190 case Type::kSliceByStack:
191 return tables::AncestorSliceByStackTable::ComputeStaticSchema();
192 }
193 PERFETTO_FATAL("For GCC");
194 }
195
TableName()196 std::string Ancestor::TableName() {
197 switch (type_) {
198 case Type::kSlice:
199 return tables::AncestorSliceTable::Name();
200 case Type::kStackProfileCallsite:
201 return tables::AncestorStackProfileCallsiteTable::Name();
202 case Type::kSliceByStack:
203 return tables::AncestorSliceByStackTable::Name();
204 }
205 PERFETTO_FATAL("For GCC");
206 }
207
EstimateRowCount()208 uint32_t Ancestor::EstimateRowCount() {
209 return 1;
210 }
211
212 // static
213 std::optional<std::vector<tables::SliceTable::RowNumber>>
GetAncestorSlices(const tables::SliceTable & slices,SliceId slice_id)214 Ancestor::GetAncestorSlices(const tables::SliceTable& slices,
215 SliceId slice_id) {
216 std::vector<tables::SliceTable::RowNumber> ret;
217 auto status = GetAncestors(slices, slice_id, ret);
218 if (!status.ok())
219 return std::nullopt;
220 return std::move(ret); // -Wreturn-std-move-in-c++11
221 }
222
223 } // namespace trace_processor
224 } // namespace perfetto
225