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