Add the descendant_slice table.
This allows you to given a slice find all descendants related to it. This
can be useful for metrics to traverse the stack and gain information
about what is happening in the trace.
Bug: 160148605
Change-Id: I54869e78d02fd18c18acf7808e4d1ba385f6c6ac
diff --git a/Android.bp b/Android.bp
index eb51eaa..4fb115a 100644
--- a/Android.bp
+++ b/Android.bp
@@ -6713,6 +6713,7 @@
name: "perfetto_src_trace_processor_lib",
srcs: [
"src/trace_processor/dynamic/ancestor_slice_generator.cc",
+ "src/trace_processor/dynamic/descendant_slice_generator.cc",
"src/trace_processor/dynamic/describe_slice_generator.cc",
"src/trace_processor/dynamic/experimental_counter_dur_generator.cc",
"src/trace_processor/dynamic/experimental_flamegraph_generator.cc",
diff --git a/BUILD b/BUILD
index 739956d..fbb2a3e 100644
--- a/BUILD
+++ b/BUILD
@@ -938,6 +938,8 @@
srcs = [
"src/trace_processor/dynamic/ancestor_slice_generator.cc",
"src/trace_processor/dynamic/ancestor_slice_generator.h",
+ "src/trace_processor/dynamic/descendant_slice_generator.cc",
+ "src/trace_processor/dynamic/descendant_slice_generator.h",
"src/trace_processor/dynamic/describe_slice_generator.cc",
"src/trace_processor/dynamic/describe_slice_generator.h",
"src/trace_processor/dynamic/experimental_counter_dur_generator.cc",
diff --git a/docs/analysis/trace-processor.md b/docs/analysis/trace-processor.md
index 7fc102b..a6fa6cf 100644
--- a/docs/analysis/trace-processor.md
+++ b/docs/analysis/trace-processor.md
@@ -319,6 +319,35 @@
ancestor_slice(interesting_slices.id) AS ancestor ON ancestor.depth = 0
```
+### Descendant slice
+descendant_slice is a custom operator table that takes a
+[slice table's id column](/docs/analysis/sql-tables#slice) and computes all
+slices on the same track that are nested under that id (i.e. all slices that
+are on the same track at the same time frame with a depth greater than the given
+slice's depth.
+
+The returned format is the same as the
+[slice table](/docs/analysis/sql-tables#slice)
+
+For example, the following finds the number of slices under each slice of
+interest.
+
+```sql
+CREATE VIEW interesting_slices AS
+SELECT id, ts, dur, track_id
+FROM slice WHERE name LIKE "%interesting slice name%";
+
+SELECT
+ *
+ (
+ SELECT
+ COUNT(*) AS total_descendants
+ FROM descendant_slice(interesting_slice.id)
+ )
+FROM interesting_slices
+```
+
+
## Metrics
TIP: To see how to add to add a new metric to trace processor, see the checklist
diff --git a/src/trace_processor/BUILD.gn b/src/trace_processor/BUILD.gn
index 8ebb933..baf811b 100644
--- a/src/trace_processor/BUILD.gn
+++ b/src/trace_processor/BUILD.gn
@@ -280,6 +280,8 @@
sources = [
"dynamic/ancestor_slice_generator.cc",
"dynamic/ancestor_slice_generator.h",
+ "dynamic/descendant_slice_generator.cc",
+ "dynamic/descendant_slice_generator.h",
"dynamic/describe_slice_generator.cc",
"dynamic/describe_slice_generator.h",
"dynamic/experimental_counter_dur_generator.cc",
diff --git a/src/trace_processor/dynamic/descendant_slice_generator.cc b/src/trace_processor/dynamic/descendant_slice_generator.cc
new file mode 100644
index 0000000..3eefcc2
--- /dev/null
+++ b/src/trace_processor/dynamic/descendant_slice_generator.cc
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/dynamic/descendant_slice_generator.h"
+
+#include <memory>
+#include <set>
+
+#include "src/trace_processor/types/trace_processor_context.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+DescendantSliceGenerator::DescendantSliceGenerator(
+ TraceProcessorContext* context)
+ : context_(context) {}
+
+DescendantSliceGenerator::~DescendantSliceGenerator() = default;
+
+util::Status DescendantSliceGenerator::ValidateConstraints(
+ const QueryConstraints& qc) {
+ const auto& cs = qc.constraints();
+
+ auto slice_id_fn = [this](const QueryConstraints::Constraint& c) {
+ return c.column == static_cast<int>(
+ context_->storage->slice_table().GetColumnCount()) &&
+ c.op == SQLITE_INDEX_CONSTRAINT_EQ;
+ };
+ bool has_slice_id_cs =
+ std::find_if(cs.begin(), cs.end(), slice_id_fn) != cs.end();
+
+ return has_slice_id_cs
+ ? util::OkStatus()
+ : util::ErrStatus("Failed to find required constraints");
+}
+
+std::unique_ptr<Table> DescendantSliceGenerator::ComputeTable(
+ const std::vector<Constraint>& cs,
+ const std::vector<Order>&) {
+ using S = tables::SliceTable;
+ const auto& slice = context_->storage->slice_table();
+
+ auto it = std::find_if(cs.begin(), cs.end(), [&slice](const Constraint& c) {
+ return c.col_idx == slice.GetColumnCount() && c.op == FilterOp::kEq;
+ });
+ PERFETTO_DCHECK(it != cs.end());
+
+ uint32_t start_id = static_cast<uint32_t>(it->value.AsLong());
+ auto start_row = slice.id().IndexOf(S::Id(start_id));
+ // The query gave an invalid ID that doesn't exist in the slice table.
+ if (!start_row) {
+ // TODO(lalitm): Ideally this should result in an error, or be filtered out
+ // during ValidateConstraints so we can just dereference |start_row|
+ // directly. However ValidateConstraints doesn't know the value we're
+ // filtering for so can't ensure it exists. For now we return a nullptr
+ // which will cause the query to surface an error with the message "SQL
+ // error: constraint failed".
+ return nullptr;
+ }
+
+ // All nested descendents must be on the same track, with a ts between
+ // |start_id.ts| and |start_id.ts| + |start_id.dur|, and who's depth is larger
+ // then |start_row|'s. So we just use Filter to select all relevant slices.
+ Table reduced_slice = slice.Filter(
+ {slice.ts().ge(slice.ts()[*start_row]),
+ slice.ts().le(slice.ts()[*start_row] + slice.dur()[*start_row]),
+ slice.track_id().eq(slice.track_id()[*start_row].value),
+ slice.depth().gt(slice.depth()[*start_row])});
+
+ // For every row extend it to match the schema, and return it.
+ std::unique_ptr<NullableVector<uint32_t>> start_ids(
+ new NullableVector<uint32_t>());
+ for (size_t i = 0; i < reduced_slice.row_count(); ++i) {
+ start_ids->Append(start_id);
+ }
+ return std::unique_ptr<Table>(
+ new Table(std::move(reduced_slice)
+ .ExtendWithColumn("start_id", std::move(start_ids),
+ TypedColumn<uint32_t>::default_flags() |
+ TypedColumn<uint32_t>::kHidden)));
+}
+
+Table::Schema DescendantSliceGenerator::CreateSchema() {
+ auto schema = tables::SliceTable::Schema();
+ schema.columns.push_back(Table::Schema::Column{
+ "start_id", SqlValue::Type::kLong, /* is_id = */ false,
+ /* is_sorted = */ false, /* is_hidden = */ true});
+ return schema;
+}
+
+std::string DescendantSliceGenerator::TableName() {
+ return "descendant_slice";
+}
+
+uint32_t DescendantSliceGenerator::EstimateRowCount() {
+ return 1;
+}
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/dynamic/descendant_slice_generator.h b/src/trace_processor/dynamic/descendant_slice_generator.h
new file mode 100644
index 0000000..260c200
--- /dev/null
+++ b/src/trace_processor/dynamic/descendant_slice_generator.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_DYNAMIC_DESCENDANT_SLICE_GENERATOR_H_
+#define SRC_TRACE_PROCESSOR_DYNAMIC_DESCENDANT_SLICE_GENERATOR_H_
+
+#include "src/trace_processor/sqlite/db_sqlite_table.h"
+
+#include "src/trace_processor/storage/trace_storage.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+class TraceProcessorContext;
+
+// Dynamic table for implementing the table.
+// See /docs/analysis.md for details about the functionality and usage of this
+// table.
+class DescendantSliceGenerator : public DbSqliteTable::DynamicTableGenerator {
+ public:
+ explicit DescendantSliceGenerator(TraceProcessorContext* context);
+ ~DescendantSliceGenerator() override;
+
+ Table::Schema CreateSchema() override;
+ std::string TableName() override;
+ uint32_t EstimateRowCount() override;
+ util::Status ValidateConstraints(const QueryConstraints&) override;
+ std::unique_ptr<Table> ComputeTable(const std::vector<Constraint>& cs,
+ const std::vector<Order>& ob) override;
+
+ private:
+ TraceProcessorContext* context_ = nullptr;
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_DYNAMIC_DESCENDANT_SLICE_GENERATOR_H_
diff --git a/src/trace_processor/trace_processor_impl.cc b/src/trace_processor/trace_processor_impl.cc
index 736c806..2b8f818 100644
--- a/src/trace_processor/trace_processor_impl.cc
+++ b/src/trace_processor/trace_processor_impl.cc
@@ -24,6 +24,7 @@
#include "perfetto/ext/base/string_splitter.h"
#include "perfetto/ext/base/string_utils.h"
#include "src/trace_processor/dynamic/ancestor_slice_generator.h"
+#include "src/trace_processor/dynamic/descendant_slice_generator.h"
#include "src/trace_processor/dynamic/describe_slice_generator.h"
#include "src/trace_processor/dynamic/experimental_counter_dur_generator.h"
#include "src/trace_processor/dynamic/experimental_flamegraph_generator.h"
@@ -601,6 +602,8 @@
&storage->slice_table())));
RegisterDynamicTable(std::unique_ptr<AncestorSliceGenerator>(
new AncestorSliceGenerator(&context_)));
+ RegisterDynamicTable(std::unique_ptr<DescendantSliceGenerator>(
+ new DescendantSliceGenerator(&context_)));
// New style db-backed tables.
RegisterDbTable(storage->arg_table());
diff --git a/test/trace_processor/descendant_slice.out b/test/trace_processor/descendant_slice.out
new file mode 100644
index 0000000..b5ffa18
--- /dev/null
+++ b/test/trace_processor/descendant_slice.out
@@ -0,0 +1,16 @@
+"currentSliceName","descendantSliceName"
+"event1_on_async_no_relationships","[NULL]"
+"event1_on_t1_no_relationships","[NULL]"
+"event1_on_t2_no_relationships","[NULL]"
+"event2_depth_0_on_t1","event2_depth_1_on_t1"
+"event2_on_async_depth_0","event2_on_async_depth_1"
+"event2_depth_1_on_t1","[NULL]"
+"event2_on_async_depth_1","[NULL]"
+"event2_depth_0_on_t2","event2_first_depth_1_on_t2"
+"event2_depth_0_on_t2","event2_first_depth_2_on_t2"
+"event2_depth_0_on_t2","event2_second_depth_1_on_t2"
+"event2_depth_0_on_t2","event2_second_depth_2_on_t2"
+"event2_first_depth_1_on_t2","event2_first_depth_2_on_t2"
+"event2_first_depth_2_on_t2","[NULL]"
+"event2_second_depth_1_on_t2","event2_second_depth_2_on_t2"
+"event2_second_depth_2_on_t2","[NULL]"
diff --git a/test/trace_processor/descendant_slice.sql b/test/trace_processor/descendant_slice.sql
new file mode 100644
index 0000000..918dd38
--- /dev/null
+++ b/test/trace_processor/descendant_slice.sql
@@ -0,0 +1,3 @@
+SELECT slice.name AS currentSliceName, descendant.name AS descendantSliceName
+FROM slice LEFT JOIN descendant_slice(slice.id) AS descendant
+ORDER BY slice.ts ASC, descendant.ts ASC, slice.name ASC, descendant.name ASC;
diff --git a/test/trace_processor/index b/test/trace_processor/index
index 2d1de52..59ff137 100644
--- a/test/trace_processor/index
+++ b/test/trace_processor/index
@@ -108,6 +108,8 @@
# Ancestor slice table.
relationship_tables.textproto ancestor_slice.sql ancestor_slice.out
+# Descendant slice table.
+relationship_tables.textproto descendant_slice.sql descendant_slice.out
# The below tests check the lower level layers of the trace processor (i.e.
# fitering and printing code).