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/perfetto_sql/intrinsics/table_functions/ancestor.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_storage.h"
33 #include "src/trace_processor/db/table.h"
34 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/tables_py.h"
35 #include "src/trace_processor/storage/trace_storage.h"
36 #include "src/trace_processor/tables/slice_tables_py.h"
37 #include "src/trace_processor/types/trace_processor_context.h"
38 #include "src/trace_processor/util/status_macros.h"
39
40 namespace perfetto::trace_processor {
41 namespace tables {
42
43 AncestorSliceTable::~AncestorSliceTable() = default;
44 AncestorStackProfileCallsiteTable::~AncestorStackProfileCallsiteTable() =
45 default;
46 AncestorSliceByStackTable::~AncestorSliceByStackTable() = default;
47
48 } // namespace tables
49
50 namespace {
51
52 template <typename T>
GetAncestors(const T & table,typename T::Id starting_id,std::vector<typename T::RowNumber> & row_numbers_accumulator)53 base::Status GetAncestors(
54 const T& table,
55 typename T::Id starting_id,
56 std::vector<typename T::RowNumber>& row_numbers_accumulator) {
57 auto start_ref = table.FindById(starting_id);
58 if (!start_ref) {
59 return base::ErrStatus("no row with id %" PRIu32 "",
60 static_cast<uint32_t>(starting_id.value));
61 }
62
63 // It's important we insert directly into |row_numbers_accumulator| and not
64 // overwrite it because we expect the existing elements in
65 // |row_numbers_accumulator| to be preserved.
66 auto maybe_parent_id = start_ref->parent_id();
67 while (maybe_parent_id) {
68 auto ref = *table.FindById(*maybe_parent_id);
69 row_numbers_accumulator.emplace_back(ref.ToRowNumber());
70 // Update the loop variable by looking up the next parent_id.
71 maybe_parent_id = ref.parent_id();
72 }
73 // We traverse the tree in reverse id order. To ensure we meet the
74 // requirements of the extension vectors being sorted, ensure that we reverse
75 // the row numbers to be in id order.
76 std::reverse(row_numbers_accumulator.begin(), row_numbers_accumulator.end());
77 return base::OkStatus();
78 }
79
80 template <typename ChildTable, typename ConstraintType, typename ParentTable>
ExtendWithStartId(ConstraintType constraint_value,const ParentTable & table,std::vector<typename ParentTable::RowNumber> parent_rows)81 std::unique_ptr<Table> ExtendWithStartId(
82 ConstraintType constraint_value,
83 const ParentTable& table,
84 std::vector<typename ParentTable::RowNumber> parent_rows) {
85 ColumnStorage<ConstraintType> start_ids;
86 for (uint32_t i = 0; i < parent_rows.size(); ++i)
87 start_ids.Append(constraint_value);
88 return ChildTable::SelectAndExtendParent(table, std::move(parent_rows),
89 std::move(start_ids));
90 }
91
92 template <typename ChildTable, typename ParentTable>
BuildAncestorsTable(typename ParentTable::Id id,const ParentTable & table)93 base::StatusOr<std::unique_ptr<Table>> BuildAncestorsTable(
94 typename ParentTable::Id id,
95 const ParentTable& table) {
96 // Build up all the parents row ids.
97 std::vector<typename ParentTable::RowNumber> ancestors;
98 RETURN_IF_ERROR(GetAncestors(table, id, ancestors));
99 return ExtendWithStartId<ChildTable>(id.value, table, std::move(ancestors));
100 }
101
102 } // namespace
103
Ancestor(Type type,const TraceStorage * storage)104 Ancestor::Ancestor(Type type, const TraceStorage* storage)
105 : type_(type), storage_(storage) {}
106
ComputeTable(const std::vector<SqlValue> & arguments)107 base::StatusOr<std::unique_ptr<Table>> Ancestor::ComputeTable(
108 const std::vector<SqlValue>& arguments) {
109 PERFETTO_CHECK(arguments.size() == 1);
110
111 if (arguments[0].is_null()) {
112 // Nothing matches a null id so return an empty table.
113 switch (type_) {
114 case Type::kSlice:
115 return std::unique_ptr<Table>(
116 tables::AncestorSliceTable::SelectAndExtendParent(
117 storage_->slice_table(), {}, {}));
118 case Type::kStackProfileCallsite:
119 return std::unique_ptr<Table>(
120 tables::AncestorStackProfileCallsiteTable::SelectAndExtendParent(
121 storage_->stack_profile_callsite_table(), {}, {}));
122 case Type::kSliceByStack:
123 return std::unique_ptr<Table>(
124 tables::AncestorSliceByStackTable::SelectAndExtendParent(
125 storage_->slice_table(), {}, {}));
126 }
127 return base::OkStatus();
128 }
129 if (arguments[0].type != SqlValue::Type::kLong) {
130 return base::ErrStatus("start id should be an integer.");
131 }
132
133 int64_t start_id = arguments[0].AsLong();
134 uint32_t start_id_uint = static_cast<uint32_t>(start_id);
135 switch (type_) {
136 case Type::kSlice:
137 return BuildAncestorsTable<tables::AncestorSliceTable>(
138 SliceId(start_id_uint), storage_->slice_table());
139
140 case Type::kStackProfileCallsite:
141 return BuildAncestorsTable<tables::AncestorStackProfileCallsiteTable>(
142 CallsiteId(start_id_uint), storage_->stack_profile_callsite_table());
143
144 case Type::kSliceByStack: {
145 // Find the all slice ids that have the stack id and find all the
146 // ancestors of the slice ids.
147 const auto& slice_table = storage_->slice_table();
148 Query q;
149 q.constraints = {slice_table.stack_id().eq(start_id)};
150 auto it = slice_table.FilterToIterator(q);
151 std::vector<tables::SliceTable::RowNumber> ancestors;
152 for (; it; ++it) {
153 RETURN_IF_ERROR(GetAncestors(slice_table, it.id(), ancestors));
154 }
155 // Sort to keep the slices in timestamp order.
156 std::sort(ancestors.begin(), ancestors.end());
157 return ExtendWithStartId<tables::AncestorSliceByStackTable>(
158 start_id, slice_table, std::move(ancestors));
159 }
160 }
161 PERFETTO_FATAL("For GCC");
162 }
163
CreateSchema()164 Table::Schema Ancestor::CreateSchema() {
165 switch (type_) {
166 case Type::kSlice:
167 return tables::AncestorSliceTable::ComputeStaticSchema();
168 case Type::kStackProfileCallsite:
169 return tables::AncestorStackProfileCallsiteTable::ComputeStaticSchema();
170 case Type::kSliceByStack:
171 return tables::AncestorSliceByStackTable::ComputeStaticSchema();
172 }
173 PERFETTO_FATAL("For GCC");
174 }
175
TableName()176 std::string Ancestor::TableName() {
177 switch (type_) {
178 case Type::kSlice:
179 return tables::AncestorSliceTable::Name();
180 case Type::kStackProfileCallsite:
181 return tables::AncestorStackProfileCallsiteTable::Name();
182 case Type::kSliceByStack:
183 return tables::AncestorSliceByStackTable::Name();
184 }
185 PERFETTO_FATAL("For GCC");
186 }
187
EstimateRowCount()188 uint32_t Ancestor::EstimateRowCount() {
189 return 1;
190 }
191
192 // static
193 std::optional<std::vector<tables::SliceTable::RowNumber>>
GetAncestorSlices(const tables::SliceTable & slices,SliceId slice_id)194 Ancestor::GetAncestorSlices(const tables::SliceTable& slices,
195 SliceId slice_id) {
196 std::vector<tables::SliceTable::RowNumber> ret;
197 auto status = GetAncestors(slices, slice_id, ret);
198 if (!status.ok())
199 return std::nullopt;
200 return std::move(ret); // -Wreturn-std-move-in-c++11
201 }
202
203 } // namespace perfetto::trace_processor
204