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 tables::AncestorSliceTable::SelectAndExtendParent(
116 storage_->slice_table(), {}, {});
117 case Type::kStackProfileCallsite:
118 return tables::AncestorStackProfileCallsiteTable::SelectAndExtendParent(
119 storage_->stack_profile_callsite_table(), {}, {});
120 case Type::kSliceByStack:
121 return tables::AncestorSliceByStackTable::SelectAndExtendParent(
122 storage_->slice_table(), {}, {});
123 }
124 return base::OkStatus();
125 }
126 if (arguments[0].type != SqlValue::Type::kLong) {
127 return base::ErrStatus("start id should be an integer.");
128 }
129
130 int64_t start_id = arguments[0].AsLong();
131 uint32_t start_id_uint = static_cast<uint32_t>(start_id);
132 switch (type_) {
133 case Type::kSlice:
134 return BuildAncestorsTable<tables::AncestorSliceTable>(
135 SliceId(start_id_uint), storage_->slice_table());
136
137 case Type::kStackProfileCallsite:
138 return BuildAncestorsTable<tables::AncestorStackProfileCallsiteTable>(
139 CallsiteId(start_id_uint), storage_->stack_profile_callsite_table());
140
141 case Type::kSliceByStack: {
142 // Find the all slice ids that have the stack id and find all the
143 // ancestors of the slice ids.
144 const auto& slice_table = storage_->slice_table();
145 Query q;
146 q.constraints = {slice_table.stack_id().eq(start_id)};
147 auto it = slice_table.FilterToIterator(q);
148 std::vector<tables::SliceTable::RowNumber> ancestors;
149 for (; it; ++it) {
150 RETURN_IF_ERROR(GetAncestors(slice_table, it.id(), ancestors));
151 }
152 // Sort to keep the slices in timestamp order.
153 std::sort(ancestors.begin(), ancestors.end());
154 return ExtendWithStartId<tables::AncestorSliceByStackTable>(
155 start_id, slice_table, std::move(ancestors));
156 }
157 }
158 PERFETTO_FATAL("For GCC");
159 }
160
CreateSchema()161 Table::Schema Ancestor::CreateSchema() {
162 switch (type_) {
163 case Type::kSlice:
164 return tables::AncestorSliceTable::ComputeStaticSchema();
165 case Type::kStackProfileCallsite:
166 return tables::AncestorStackProfileCallsiteTable::ComputeStaticSchema();
167 case Type::kSliceByStack:
168 return tables::AncestorSliceByStackTable::ComputeStaticSchema();
169 }
170 PERFETTO_FATAL("For GCC");
171 }
172
TableName()173 std::string Ancestor::TableName() {
174 switch (type_) {
175 case Type::kSlice:
176 return tables::AncestorSliceTable::Name();
177 case Type::kStackProfileCallsite:
178 return tables::AncestorStackProfileCallsiteTable::Name();
179 case Type::kSliceByStack:
180 return tables::AncestorSliceByStackTable::Name();
181 }
182 PERFETTO_FATAL("For GCC");
183 }
184
EstimateRowCount()185 uint32_t Ancestor::EstimateRowCount() {
186 return 1;
187 }
188
189 // static
190 std::optional<std::vector<tables::SliceTable::RowNumber>>
GetAncestorSlices(const tables::SliceTable & slices,SliceId slice_id)191 Ancestor::GetAncestorSlices(const tables::SliceTable& slices,
192 SliceId slice_id) {
193 std::vector<tables::SliceTable::RowNumber> ret;
194 auto status = GetAncestors(slices, slice_id, ret);
195 if (!status.ok())
196 return std::nullopt;
197 return std::move(ret); // -Wreturn-std-move-in-c++11
198 }
199
200 } // namespace perfetto::trace_processor
201