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/dynamic/ancestor_generator.h"
18
19 #include <memory>
20 #include <set>
21
22 #include "src/trace_processor/types/trace_processor_context.h"
23 #include "src/trace_processor/util/status_macros.h"
24
25 namespace perfetto {
26 namespace trace_processor {
27 namespace {
GetConstraintColumnIndex(AncestorGenerator::Ancestor type,TraceProcessorContext * context)28 uint32_t GetConstraintColumnIndex(AncestorGenerator::Ancestor type,
29 TraceProcessorContext* context) {
30 switch (type) {
31 case AncestorGenerator::Ancestor::kSlice:
32 return context->storage->slice_table().GetColumnCount();
33 case AncestorGenerator::Ancestor::kStackProfileCallsite:
34 return context->storage->stack_profile_callsite_table().GetColumnCount();
35 case AncestorGenerator::Ancestor::kSliceByStack:
36 return context->storage->slice_table().GetColumnCount();
37 }
38 return 0;
39 }
40
41 template <typename T>
ExtendTableWithStartId(const T & table,int64_t constraint_value)42 Table ExtendTableWithStartId(const T& table, int64_t constraint_value) {
43 // Add a new column that includes the constraint.
44 std::unique_ptr<NullableVector<int64_t>> child_ids(
45 new NullableVector<int64_t>());
46 for (uint32_t i = 0; i < table.row_count(); ++i)
47 child_ids->Append(constraint_value);
48 return table.ExtendWithColumn(
49 "start_id", std::move(child_ids),
50 TypedColumn<uint32_t>::default_flags() | TypedColumn<uint32_t>::kHidden);
51 }
52
53 template <typename T>
BuildAncestorsRowMap(const T & table,typename T::Id starting_id,RowMap & rowmap_return)54 base::Status BuildAncestorsRowMap(const T& table,
55 typename T::Id starting_id,
56 RowMap& rowmap_return) {
57 auto start_row = table.id().IndexOf(starting_id);
58 if (!start_row) {
59 return base::ErrStatus("no row with id %" PRIu32 "",
60 static_cast<uint32_t>(starting_id.value));
61 }
62
63 std::vector<uint32_t> parent_rows;
64 auto maybe_parent_id = table.parent_id()[*start_row];
65 while (maybe_parent_id) {
66 uint32_t parent_row = table.id().IndexOf(*maybe_parent_id).value();
67 parent_rows.push_back(parent_row);
68 // Update the loop variable by looking up the next parent_id.
69 maybe_parent_id = table.parent_id()[parent_row];
70 }
71 rowmap_return = RowMap{parent_rows};
72 return base::OkStatus();
73 }
74
75 // Constraint_value is used to construct the hidden column "start_id"
76 // needed by SQL.
77 // Starting_id refers to the id that is used to generate the ancestors.
78 template <typename T>
BuildAncestorsTable(int64_t constraint_value,const T & table,typename T::Id starting_id,std::unique_ptr<Table> & table_return)79 base::Status BuildAncestorsTable(int64_t constraint_value,
80 const T& table,
81 typename T::Id starting_id,
82 std::unique_ptr<Table>& table_return) {
83 // Build up all the parents row ids.
84 RowMap ancestors;
85 RETURN_IF_ERROR(BuildAncestorsRowMap(table, starting_id, ancestors));
86
87 table_return.reset(new Table(ExtendTableWithStartId(
88 table.Apply(std::move(ancestors)), constraint_value)));
89 return base::OkStatus();
90 }
91 } // namespace
92
AncestorGenerator(Ancestor type,TraceProcessorContext * context)93 AncestorGenerator::AncestorGenerator(Ancestor type,
94 TraceProcessorContext* context)
95 : type_(type), context_(context) {}
96
ValidateConstraints(const QueryConstraints & qc)97 base::Status AncestorGenerator::ValidateConstraints(
98 const QueryConstraints& qc) {
99 const auto& cs = qc.constraints();
100
101 int column = static_cast<int>(GetConstraintColumnIndex(type_, context_));
102 auto id_fn = [column](const QueryConstraints::Constraint& c) {
103 return c.column == column && c.op == SQLITE_INDEX_CONSTRAINT_EQ;
104 };
105 bool has_id_cs = std::find_if(cs.begin(), cs.end(), id_fn) != cs.end();
106 return has_id_cs ? base::OkStatus()
107 : base::ErrStatus("Failed to find required constraints");
108 }
109
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &,const BitVector &,std::unique_ptr<Table> & table_return)110 base::Status AncestorGenerator::ComputeTable(
111 const std::vector<Constraint>& cs,
112 const std::vector<Order>&,
113 const BitVector&,
114 std::unique_ptr<Table>& table_return) {
115 uint32_t column = GetConstraintColumnIndex(type_, context_);
116 auto constraint_it =
117 std::find_if(cs.begin(), cs.end(), [column](const Constraint& c) {
118 return c.col_idx == column && c.op == FilterOp::kEq;
119 });
120 PERFETTO_DCHECK(constraint_it != cs.end());
121 if (constraint_it == cs.end() ||
122 constraint_it->value.type != SqlValue::Type::kLong) {
123 return base::ErrStatus("invalid start_id");
124 }
125 auto start_id = constraint_it->value.AsLong();
126
127 switch (type_) {
128 case Ancestor::kSlice: {
129 RETURN_IF_ERROR(BuildAncestorsTable(
130 /* constraint_id = */ start_id, context_->storage->slice_table(),
131 /* starting_id = */ SliceId(static_cast<uint32_t>(start_id)),
132 table_return));
133 return base::OkStatus();
134 }
135
136 case Ancestor::kStackProfileCallsite: {
137 RETURN_IF_ERROR(BuildAncestorsTable(
138 /* constraint_id = */ start_id,
139 context_->storage->stack_profile_callsite_table(),
140 /* starting_id = */ CallsiteId(static_cast<uint32_t>(start_id)),
141 table_return));
142 return base::OkStatus();
143 }
144
145 case Ancestor::kSliceByStack: {
146 // Find the all slice ids that have the stack id and find all the
147 // ancestors of the slice ids.
148 const auto& slice_table = context_->storage->slice_table();
149
150 auto result = RowMap();
151 auto slice_ids =
152 slice_table.FilterToRowMap({slice_table.stack_id().eq(start_id)});
153
154 for (auto id_it = slice_ids.IterateRows(); id_it; id_it.Next()) {
155 auto slice_id = slice_table.id()[id_it.index()];
156
157 auto ancestors = GetAncestorSlices(slice_table, slice_id);
158 for (auto row_it = ancestors->IterateRows(); row_it; row_it.Next()) {
159 result.Insert(row_it.index());
160 }
161 }
162
163 table_return.reset(new Table(ExtendTableWithStartId(
164 slice_table.Apply(std::move(result)), start_id)));
165 return base::OkStatus();
166 }
167 }
168 return base::ErrStatus("unknown AncestorGenerator type");
169 }
170
CreateSchema()171 Table::Schema AncestorGenerator::CreateSchema() {
172 Table::Schema final_schema;
173 switch (type_) {
174 case Ancestor::kSlice:
175 final_schema = tables::SliceTable::Schema();
176 break;
177 case Ancestor::kStackProfileCallsite:
178 final_schema = tables::StackProfileCallsiteTable::Schema();
179 break;
180 case Ancestor::kSliceByStack:
181 final_schema = tables::SliceTable::Schema();
182 break;
183 }
184 final_schema.columns.push_back(Table::Schema::Column{
185 "start_id", SqlValue::Type::kLong, /* is_id = */ false,
186 /* is_sorted = */ false, /* is_hidden = */ true});
187 return final_schema;
188 }
189
TableName()190 std::string AncestorGenerator::TableName() {
191 switch (type_) {
192 case Ancestor::kSlice:
193 return "ancestor_slice";
194 case Ancestor::kStackProfileCallsite:
195 return "experimental_ancestor_stack_profile_callsite";
196 case Ancestor::kSliceByStack:
197 return "ancestor_slice_by_stack";
198 }
199 return "ancestor_unknown";
200 }
201
EstimateRowCount()202 uint32_t AncestorGenerator::EstimateRowCount() {
203 return 1;
204 }
205
206 // static
GetAncestorSlices(const tables::SliceTable & slices,SliceId slice_id)207 base::Optional<RowMap> AncestorGenerator::GetAncestorSlices(
208 const tables::SliceTable& slices,
209 SliceId slice_id) {
210 RowMap ret;
211 auto status = BuildAncestorsRowMap(slices, slice_id, ret);
212 if (!status.ok())
213 return base::nullopt;
214 return std::move(ret); // -Wreturn-std-move-in-c++11
215 }
216
217 } // namespace trace_processor
218 } // namespace perfetto
219