1 /*
2 * Copyright (C) 2021 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/perfetto_sql/intrinsics/table_functions/descendant.h"
18
19 #include <algorithm>
20 #include <cinttypes>
21 #include <cstdint>
22 #include <memory>
23 #include <optional>
24 #include <string>
25 #include <utility>
26 #include <vector>
27
28 #include "perfetto/base/logging.h"
29 #include "perfetto/base/status.h"
30 #include "perfetto/ext/base/status_or.h"
31 #include "perfetto/trace_processor/basic_types.h"
32 #include "src/trace_processor/db/column/types.h"
33 #include "src/trace_processor/db/column_storage.h"
34 #include "src/trace_processor/db/table.h"
35 #include "src/trace_processor/db/typed_column.h"
36 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/tables_py.h"
37 #include "src/trace_processor/storage/trace_storage.h"
38 #include "src/trace_processor/tables/slice_tables_py.h"
39 #include "src/trace_processor/types/trace_processor_context.h"
40 #include "src/trace_processor/util/status_macros.h"
41
42 namespace perfetto::trace_processor {
43 namespace tables {
44
45 DescendantSliceTable::~DescendantSliceTable() = default;
46 DescendantSliceByStackTable::~DescendantSliceByStackTable() = default;
47
48 } // namespace tables
49
50 namespace {
51
52 template <typename ChildTable, typename ParentTable, typename ConstraintType>
ExtendWithStartId(ConstraintType constraint_id,const ParentTable & table,std::vector<typename ParentTable::RowNumber> parent_rows)53 std::unique_ptr<Table> ExtendWithStartId(
54 ConstraintType constraint_id,
55 const ParentTable& table,
56 std::vector<typename ParentTable::RowNumber> parent_rows) {
57 ColumnStorage<ConstraintType> start_ids;
58 for (uint32_t i = 0; i < parent_rows.size(); ++i)
59 start_ids.Append(constraint_id);
60 return ChildTable::SelectAndExtendParent(table, std::move(parent_rows),
61 std::move(start_ids));
62 }
63
GetDescendants(const tables::SliceTable & slices,SliceId starting_id,std::vector<tables::SliceTable::RowNumber> & row_numbers_accumulator)64 base::Status GetDescendants(
65 const tables::SliceTable& slices,
66 SliceId starting_id,
67 std::vector<tables::SliceTable::RowNumber>& row_numbers_accumulator) {
68 auto start_ref = slices.FindById(starting_id);
69 // The query gave an invalid ID that doesn't exist in the slice table.
70 if (!start_ref) {
71 return base::ErrStatus("no row with id %" PRIu32 "",
72 static_cast<uint32_t>(starting_id.value));
73 }
74
75 // As an optimization, for any finished slices, we only need to consider
76 // slices which started before the end of this slice (because slices on a
77 // track are always perfectly stacked).
78 // For unfinshed slices (i.e. -1 dur), we need to consider until the end of
79 // the trace so we cannot add any similar constraint.
80 Query q;
81 if (start_ref->dur() >= 0) {
82 q.constraints.emplace_back(
83 slices.ts().le(start_ref->ts() + start_ref->dur()));
84 }
85
86 // All nested descendents must be on the same track, with a ts greater than
87 // |start_ref.ts| and whose depth is larger than |start_ref|'s.
88 q.constraints.emplace_back(slices.ts().ge(start_ref->ts()));
89 q.constraints.emplace_back(slices.track_id().eq(start_ref->track_id().value));
90 q.constraints.emplace_back(slices.depth().gt(start_ref->depth()));
91
92 // It's important we insert directly into |row_numbers_accumulator| and not
93 // overwrite it because we expect the existing elements in
94 // |row_numbers_accumulator| to be preserved.
95
96 for (auto it = slices.FilterToIterator(q); it; ++it) {
97 row_numbers_accumulator.emplace_back(it.row_number());
98 }
99 return base::OkStatus();
100 }
101
102 } // namespace
103
Descendant(Type type,const TraceStorage * storage)104 Descendant::Descendant(Type type, const TraceStorage* storage)
105 : type_(type), storage_(storage) {}
106
ComputeTable(const std::vector<SqlValue> & arguments)107 base::StatusOr<std::unique_ptr<Table>> Descendant::ComputeTable(
108 const std::vector<SqlValue>& arguments) {
109 PERFETTO_CHECK(arguments.size() == 1);
110
111 const auto& slices = storage_->slice_table();
112 if (arguments[0].type == SqlValue::Type::kNull) {
113 // Nothing matches a null id so return an empty table.
114 switch (type_) {
115 case Type::kSlice:
116 return tables::DescendantSliceTable::SelectAndExtendParent(
117 storage_->slice_table(), {}, {});
118 case Type::kSliceByStack:
119 return tables::DescendantSliceByStackTable::SelectAndExtendParent(
120 storage_->slice_table(), {}, {});
121 }
122 PERFETTO_FATAL("For GCC");
123 }
124 if (arguments[0].type != SqlValue::Type::kLong) {
125 return base::ErrStatus("start id should be an integer.");
126 }
127
128 int64_t start_id = arguments[0].AsLong();
129 std::vector<tables::SliceTable::RowNumber> descendants;
130 switch (type_) {
131 case Type::kSlice: {
132 // Build up all the children row ids.
133 uint32_t start_id_uint = static_cast<uint32_t>(start_id);
134 RETURN_IF_ERROR(GetDescendants(
135 slices, tables::SliceTable::Id(start_id_uint), descendants));
136 return ExtendWithStartId<tables::DescendantSliceTable>(
137 start_id_uint, slices, std::move(descendants));
138 }
139 case Type::kSliceByStack: {
140 Query q;
141 q.constraints = {slices.stack_id().eq(start_id)};
142 for (auto it = slices.FilterToIterator(q); it; ++it) {
143 RETURN_IF_ERROR(GetDescendants(slices, it.id(), descendants));
144 }
145 return ExtendWithStartId<tables::DescendantSliceByStackTable>(
146 start_id, slices, std::move(descendants));
147 }
148 }
149 PERFETTO_FATAL("For GCC");
150 }
151
CreateSchema()152 Table::Schema Descendant::CreateSchema() {
153 switch (type_) {
154 case Type::kSlice:
155 return tables::DescendantSliceTable::ComputeStaticSchema();
156 case Type::kSliceByStack:
157 return tables::DescendantSliceByStackTable::ComputeStaticSchema();
158 }
159 PERFETTO_FATAL("For GCC");
160 }
161
TableName()162 std::string Descendant::TableName() {
163 switch (type_) {
164 case Type::kSlice:
165 return tables::DescendantSliceTable::Name();
166 case Type::kSliceByStack:
167 return tables::DescendantSliceByStackTable::Name();
168 }
169 PERFETTO_FATAL("For GCC");
170 }
171
EstimateRowCount()172 uint32_t Descendant::EstimateRowCount() {
173 return 1;
174 }
175
176 // static
177 std::optional<std::vector<tables::SliceTable::RowNumber>>
GetDescendantSlices(const tables::SliceTable & slices,SliceId slice_id)178 Descendant::GetDescendantSlices(const tables::SliceTable& slices,
179 SliceId slice_id) {
180 std::vector<tables::SliceTable::RowNumber> ret;
181 auto status = GetDescendants(slices, slice_id, ret);
182 if (!status.ok())
183 return std::nullopt;
184 return std::move(ret);
185 }
186
187 } // namespace perfetto::trace_processor
188