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/connected_flow_generator.h"
18
19 #include <memory>
20 #include <queue>
21 #include <set>
22
23 #include "src/trace_processor/dynamic/ancestor_generator.h"
24 #include "src/trace_processor/dynamic/descendant_slice_generator.h"
25 #include "src/trace_processor/importers/common/flow_tracker.h"
26 #include "src/trace_processor/types/trace_processor_context.h"
27
28 namespace perfetto {
29 namespace trace_processor {
30
ConnectedFlowGenerator(Mode mode,TraceProcessorContext * context)31 ConnectedFlowGenerator::ConnectedFlowGenerator(Mode mode,
32 TraceProcessorContext* context)
33 : mode_(mode), context_(context) {}
34
35 ConnectedFlowGenerator::~ConnectedFlowGenerator() = default;
36
ValidateConstraints(const QueryConstraints & qc)37 util::Status ConnectedFlowGenerator::ValidateConstraints(
38 const QueryConstraints& qc) {
39 const auto& cs = qc.constraints();
40
41 auto flow_id_fn = [this](const QueryConstraints::Constraint& c) {
42 return c.column == static_cast<int>(
43 context_->storage->flow_table().GetColumnCount()) &&
44 c.op == SQLITE_INDEX_CONSTRAINT_EQ;
45 };
46 bool has_flow_id_cs =
47 std::find_if(cs.begin(), cs.end(), flow_id_fn) != cs.end();
48
49 return has_flow_id_cs
50 ? util::OkStatus()
51 : util::ErrStatus("Failed to find required constraints");
52 }
53
54 namespace {
55
56 enum FlowVisitMode : uint8_t {
57 VISIT_INCOMING = 1 << 0,
58 VISIT_OUTGOING = 1 << 1,
59 VISIT_INCOMING_AND_OUTGOING = VISIT_INCOMING | VISIT_OUTGOING,
60 };
61
62 enum RelativesVisitMode : uint8_t {
63 VISIT_NO_RELATIVES = 0,
64 VISIT_ANCESTORS = 1 << 0,
65 VISIT_DESCENDANTS = 1 << 1,
66 VISIT_ALL_RELATIVES = VISIT_ANCESTORS | VISIT_DESCENDANTS,
67 };
68
69 // Searches through the slice table recursively to find connected flows.
70 // Usage:
71 // BFS bfs = BFS(context);
72 // bfs
73 // // Add list of slices to start with.
74 // .Start(start_id).Start(start_id2)
75 // // Additionally include relatives of |another_id| in search space.
76 // .GoToRelatives(another_id, VISIT_ANCESTORS)
77 // // Visit all connected slices to the above slices.
78 // .VisitAll(VISIT_INCOMING, VISIT_NO_RELATIVES);
79 //
80 // bfs.TakeResultingFlows();
81 class BFS {
82 public:
BFS(TraceProcessorContext * context)83 BFS(TraceProcessorContext* context) : context_(context) {}
84
TakeResultingFlows()85 RowMap TakeResultingFlows() && { return RowMap(std::move(flow_rows_)); }
86
87 // Includes a starting slice ID to search.
Start(SliceId start_id)88 BFS& Start(SliceId start_id) {
89 slices_to_visit_.push({start_id, VisitType::START});
90 known_slices_.insert(start_id);
91 return *this;
92 }
93
94 // Visits all slices that can be reached from the given starting slices.
VisitAll(FlowVisitMode visit_flow,RelativesVisitMode visit_relatives)95 void VisitAll(FlowVisitMode visit_flow, RelativesVisitMode visit_relatives) {
96 while (!slices_to_visit_.empty()) {
97 SliceId slice_id = slices_to_visit_.front().first;
98 VisitType visit_type = slices_to_visit_.front().second;
99 slices_to_visit_.pop();
100
101 // If the given slice is being visited due to being ancestor or descendant
102 // of a previous one, do not compute ancestors or descendants again as the
103 // result is going to be the same.
104 if (visit_type != VisitType::VIA_RELATIVE) {
105 GoToRelatives(slice_id, visit_relatives);
106 }
107
108 // If the slice was visited by a flow, do not try to go back.
109 if ((visit_flow & VISIT_INCOMING) &&
110 visit_type != VisitType::VIA_OUTGOING_FLOW) {
111 GoByFlow(slice_id, FlowDirection::INCOMING);
112 }
113 if ((visit_flow & VISIT_OUTGOING) &&
114 visit_type != VisitType::VIA_INCOMING_FLOW) {
115 GoByFlow(slice_id, FlowDirection::OUTGOING);
116 }
117 }
118 }
119
120 // Includes the relatives of |slice_id| to the list of slices to visit.
GoToRelatives(SliceId slice_id,RelativesVisitMode visit_relatives)121 BFS& GoToRelatives(SliceId slice_id, RelativesVisitMode visit_relatives) {
122 if (visit_relatives & VISIT_ANCESTORS) {
123 base::Optional<RowMap> ancestors = AncestorGenerator::GetAncestorSlices(
124 context_->storage->slice_table(), slice_id);
125 if (ancestors)
126 GoToRelativesImpl(ancestors->IterateRows());
127 }
128 if (visit_relatives & VISIT_DESCENDANTS) {
129 base::Optional<RowMap> descendants =
130 DescendantSliceGenerator::GetDescendantSlices(
131 context_->storage->slice_table(), slice_id);
132 GoToRelativesImpl(descendants->IterateRows());
133 }
134 return *this;
135 }
136
137 private:
138 enum class FlowDirection {
139 INCOMING,
140 OUTGOING,
141 };
142
143 enum class VisitType {
144 START,
145 VIA_INCOMING_FLOW,
146 VIA_OUTGOING_FLOW,
147 VIA_RELATIVE,
148 };
149
GoByFlow(SliceId slice_id,FlowDirection flow_direction)150 void GoByFlow(SliceId slice_id, FlowDirection flow_direction) {
151 PERFETTO_DCHECK(known_slices_.count(slice_id) != 0);
152
153 const auto& flow = context_->storage->flow_table();
154
155 const TypedColumn<SliceId>& start_col =
156 (flow_direction == FlowDirection::OUTGOING ? flow.slice_out()
157 : flow.slice_in());
158 const TypedColumn<SliceId>& end_col =
159 (flow_direction == FlowDirection::OUTGOING ? flow.slice_in()
160 : flow.slice_out());
161
162 auto rows = flow.FilterToRowMap({start_col.eq(slice_id.value)});
163
164 for (auto row_it = rows.IterateRows(); row_it; row_it.Next()) {
165 flow_rows_.push_back(row_it.row());
166 SliceId next_slice_id = end_col[row_it.row()];
167 if (known_slices_.count(next_slice_id) != 0) {
168 continue;
169 }
170
171 known_slices_.insert(next_slice_id);
172 slices_to_visit_.push(
173 {next_slice_id, flow_direction == FlowDirection::INCOMING
174 ? VisitType::VIA_INCOMING_FLOW
175 : VisitType::VIA_OUTGOING_FLOW});
176 }
177 }
178
GoToRelativesImpl(RowMap::Iterator it)179 void GoToRelativesImpl(RowMap::Iterator it) {
180 const auto& slice = context_->storage->slice_table();
181 for (; it; it.Next()) {
182 auto relative_slice_id = slice.id()[it.row()];
183 if (known_slices_.count(relative_slice_id))
184 continue;
185 known_slices_.insert(relative_slice_id);
186 slices_to_visit_.push({relative_slice_id, VisitType::VIA_RELATIVE});
187 }
188 }
189
190 std::queue<std::pair<SliceId, VisitType>> slices_to_visit_;
191 std::set<SliceId> known_slices_;
192 std::vector<uint32_t> flow_rows_;
193
194 TraceProcessorContext* context_;
195 };
196
197 } // namespace
198
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &)199 std::unique_ptr<Table> ConnectedFlowGenerator::ComputeTable(
200 const std::vector<Constraint>& cs,
201 const std::vector<Order>&) {
202 const auto& flow = context_->storage->flow_table();
203 const auto& slice = context_->storage->slice_table();
204
205 auto it = std::find_if(cs.begin(), cs.end(), [&flow](const Constraint& c) {
206 return c.col_idx == flow.GetColumnCount() && c.op == FilterOp::kEq;
207 });
208
209 PERFETTO_DCHECK(it != cs.end());
210
211 SliceId start_id{static_cast<uint32_t>(it->value.AsLong())};
212
213 if (!slice.id().IndexOf(start_id)) {
214 PERFETTO_ELOG("Given slice id is invalid (ConnectedFlowGenerator)");
215 return nullptr;
216 }
217
218 BFS bfs(context_);
219
220 switch (mode_) {
221 case Mode::kDirectlyConnectedFlow:
222 bfs.Start(start_id).VisitAll(VISIT_INCOMING_AND_OUTGOING,
223 VISIT_NO_RELATIVES);
224 break;
225 case Mode::kFollowingFlow:
226 bfs.Start(start_id).VisitAll(VISIT_OUTGOING, VISIT_DESCENDANTS);
227 break;
228 case Mode::kPrecedingFlow:
229 bfs.Start(start_id).VisitAll(VISIT_INCOMING, VISIT_ANCESTORS);
230 break;
231 }
232
233 RowMap result_rows = std::move(bfs).TakeResultingFlows();
234
235 // Aditional column for start_id
236 std::unique_ptr<NullableVector<uint32_t>> start_ids(
237 new NullableVector<uint32_t>());
238
239 for (size_t i = 0; i < result_rows.size(); i++) {
240 start_ids->Append(start_id.value);
241 }
242
243 return std::unique_ptr<Table>(
244 new Table(flow.Apply(RowMap(std::move(result_rows)))
245 .ExtendWithColumn("start_id", std::move(start_ids),
246 TypedColumn<uint32_t>::default_flags() |
247 TypedColumn<uint32_t>::kHidden)));
248 }
249
CreateSchema()250 Table::Schema ConnectedFlowGenerator::CreateSchema() {
251 auto schema = tables::FlowTable::Schema();
252 schema.columns.push_back(Table::Schema::Column{
253 "start_id", SqlValue::Type::kLong, /* is_id = */ false,
254 /* is_sorted = */ false, /* is_hidden = */ true});
255 return schema;
256 }
257
TableName()258 std::string ConnectedFlowGenerator::TableName() {
259 switch (mode_) {
260 case Mode::kDirectlyConnectedFlow:
261 return "directly_connected_flow";
262 case Mode::kFollowingFlow:
263 return "following_flow";
264 case Mode::kPrecedingFlow:
265 return "preceding_flow";
266 }
267 PERFETTO_FATAL("Unexpected ConnectedFlowType");
268 }
269
EstimateRowCount()270 uint32_t ConnectedFlowGenerator::EstimateRowCount() {
271 return 1;
272 }
273 } // namespace trace_processor
274 } // namespace perfetto
275