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
24 namespace perfetto {
25 namespace trace_processor {
26 namespace {
GetConstraintColumnIndex(AncestorGenerator::Ancestor type,TraceProcessorContext * context)27 uint32_t GetConstraintColumnIndex(AncestorGenerator::Ancestor type,
28 TraceProcessorContext* context) {
29 switch (type) {
30 case AncestorGenerator::Ancestor::kSlice:
31 return context->storage->slice_table().GetColumnCount();
32 case AncestorGenerator::Ancestor::kStackProfileCallsite:
33 return context->storage->stack_profile_callsite_table().GetColumnCount();
34 }
35 return 0;
36 }
37
38 template <typename T>
BuildAncestorsRowMap(const T & table,typename T::Id starting_id)39 base::Optional<RowMap> BuildAncestorsRowMap(const T& table,
40 typename T::Id starting_id) {
41 auto start_row = table.id().IndexOf(starting_id);
42
43 if (!start_row) {
44 // TODO(lalitm): Ideally this should result in an error, or be filtered out
45 // during ValidateConstraints so we can just dereference |start_row|
46 // directly. However ValidateConstraints doesn't know the value we're
47 // filtering for so can't ensure it exists. For now we return a nullptr
48 // which will cause the query to surface an error with the message "SQL
49 // error: constraint failed".
50 return base::nullopt;
51 }
52
53 std::vector<uint32_t> parent_rows;
54 auto maybe_parent_id = table.parent_id()[*start_row];
55 while (maybe_parent_id) {
56 uint32_t parent_row = table.id().IndexOf(*maybe_parent_id).value();
57 parent_rows.push_back(parent_row);
58 // Update the loop variable by looking up the next parent_id.
59 maybe_parent_id = table.parent_id()[parent_row];
60 }
61 return RowMap(std::move(parent_rows));
62 }
63
64 template <typename T>
BuildAncestorsTable(const T & table,typename T::Id starting_id)65 std::unique_ptr<Table> BuildAncestorsTable(const T& table,
66 typename T::Id starting_id) {
67 // Build up all the parents row ids.
68 auto ancestors = BuildAncestorsRowMap(table, starting_id);
69 if (!ancestors) {
70 return nullptr;
71 }
72 // Add a new column that includes the constraint.
73 std::unique_ptr<NullableVector<uint32_t>> child_ids(
74 new NullableVector<uint32_t>());
75 for (uint32_t i = 0; i < ancestors->size(); ++i)
76 child_ids->Append(starting_id.value);
77 return std::unique_ptr<Table>(
78 new Table(table.Apply(std::move(*ancestors))
79 .ExtendWithColumn("start_id", std::move(child_ids),
80 TypedColumn<uint32_t>::default_flags() |
81 TypedColumn<uint32_t>::kHidden)));
82 }
83 } // namespace
84
AncestorGenerator(Ancestor type,TraceProcessorContext * context)85 AncestorGenerator::AncestorGenerator(Ancestor type,
86 TraceProcessorContext* context)
87 : type_(type), context_(context) {}
88
ValidateConstraints(const QueryConstraints & qc)89 util::Status AncestorGenerator::ValidateConstraints(
90 const QueryConstraints& qc) {
91 const auto& cs = qc.constraints();
92
93 int column = static_cast<int>(GetConstraintColumnIndex(type_, context_));
94 auto id_fn = [column](const QueryConstraints::Constraint& c) {
95 return c.column == column && c.op == SQLITE_INDEX_CONSTRAINT_EQ;
96 };
97 bool has_id_cs = std::find_if(cs.begin(), cs.end(), id_fn) != cs.end();
98 return has_id_cs ? util::OkStatus()
99 : util::ErrStatus("Failed to find required constraints");
100 }
101
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &)102 std::unique_ptr<Table> AncestorGenerator::ComputeTable(
103 const std::vector<Constraint>& cs,
104 const std::vector<Order>&) {
105 uint32_t column = GetConstraintColumnIndex(type_, context_);
106 auto it = std::find_if(cs.begin(), cs.end(), [column](const Constraint& c) {
107 return c.col_idx == column && c.op == FilterOp::kEq;
108 });
109 PERFETTO_DCHECK(it != cs.end());
110
111 auto start_id = static_cast<uint32_t>(it->value.AsLong());
112 switch (type_) {
113 case Ancestor::kSlice:
114 return BuildAncestorsTable(context_->storage->slice_table(),
115 SliceId(start_id));
116 case Ancestor::kStackProfileCallsite:
117 return BuildAncestorsTable(
118 context_->storage->stack_profile_callsite_table(),
119 CallsiteId(start_id));
120 }
121 return nullptr;
122 }
123
CreateSchema()124 Table::Schema AncestorGenerator::CreateSchema() {
125 Table::Schema final_schema;
126 switch (type_) {
127 case Ancestor::kSlice:
128 final_schema = tables::SliceTable::Schema();
129 break;
130 case Ancestor::kStackProfileCallsite:
131 final_schema = tables::StackProfileCallsiteTable::Schema();
132 break;
133 }
134 final_schema.columns.push_back(Table::Schema::Column{
135 "start_id", SqlValue::Type::kLong, /* is_id = */ false,
136 /* is_sorted = */ false, /* is_hidden = */ true});
137 return final_schema;
138 }
139
TableName()140 std::string AncestorGenerator::TableName() {
141 switch (type_) {
142 case Ancestor::kSlice:
143 return "ancestor_slice";
144 case Ancestor::kStackProfileCallsite:
145 return "experimental_ancestor_stack_profile_callsite";
146 }
147 return "ancestor_unknown";
148 }
149
EstimateRowCount()150 uint32_t AncestorGenerator::EstimateRowCount() {
151 return 1;
152 }
153
154 // static
GetAncestorSlices(const tables::SliceTable & slices,SliceId slice_id)155 base::Optional<RowMap> AncestorGenerator::GetAncestorSlices(
156 const tables::SliceTable& slices,
157 SliceId slice_id) {
158 return BuildAncestorsRowMap(slices, slice_id);
159 }
160
161 } // namespace trace_processor
162 } // namespace perfetto
163