tp: add flamechart operator for sampled stack rendering To render sampled call stacks as a flame chart over time, the UI needs the maximal-run decomposition of a stream of (ts, leaf callsite) samples: for each stack depth, the time ranges over which the same frame was continuously present. Computing this in SQL needs unbounded recursive expansion and doing it in JS means shipping every sample to the UI, so implement it as a C++ operator mirroring the flamegraph split: a pure sweep in flamechart.cc and a SQLite aggregate (__intrinsic_flamechart) wrapping it. The sweep is a single streaming pass over ts-ordered points: points whose stack shares a prefix with the previous one extend the open segments at those depths; only divergent depths close and open segments. Leaf ids resolve through the id -> row index persisted on Tree, and output rows stream straight into a dataframe. Expose the operator to SQL as _stack_sample_flamechart_runs! in the std.stack_sample.flamechart stdlib module, alongside sampling eligibility; mapping classification lives in std.stack_sample.mapping.
diff --git a/Android.bp b/Android.bp index bc9d489..408686d 100644 --- a/Android.bp +++ b/Android.bp
@@ -3185,6 +3185,8 @@ ":perfetto_src_trace_processor_plugins_experimental_flamegraph_experimental_flamegraph", ":perfetto_src_trace_processor_plugins_experimental_flat_slice_experimental_flat_slice", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", + ":perfetto_src_trace_processor_plugins_flamechart_flamechart", + ":perfetto_src_trace_processor_plugins_flamechart_intrinsics", ":perfetto_src_trace_processor_plugins_flamegraph_flamegraph", ":perfetto_src_trace_processor_plugins_flamegraph_intrinsics", ":perfetto_src_trace_processor_plugins_graph_scan_graph_scan", @@ -19370,6 +19372,15 @@ ], } +// GN: //src/trace_processor/perfetto_sql/stdlib/std/stack_sample:stack_sample +filegroup { + name: "perfetto_src_trace_processor_perfetto_sql_stdlib_std_stack_sample_stack_sample", + srcs: [ + "src/trace_processor/perfetto_sql/stdlib/std/stack_sample/flamechart.sql", + "src/trace_processor/perfetto_sql/stdlib/std/stack_sample/mapping.sql", + ], +} + // GN: //src/trace_processor/perfetto_sql/stdlib/std/thread:thread filegroup { name: "perfetto_src_trace_processor_perfetto_sql_stdlib_std_thread_thread", @@ -19417,6 +19428,7 @@ ":perfetto_src_trace_processor_perfetto_sql_stdlib_stacks_stacks", ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_gpu_gpu", ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_metasql_metasql", + ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_stack_sample_stack_sample", ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_thread_thread", ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_traceinfo_traceinfo", ":perfetto_src_trace_processor_perfetto_sql_stdlib_std_trees_trees", @@ -20237,6 +20249,30 @@ ], } +// GN: //src/trace_processor/plugins/flamechart:flamechart +filegroup { + name: "perfetto_src_trace_processor_plugins_flamechart_flamechart", + srcs: [ + "src/trace_processor/plugins/flamechart/flamechart.cc", + ], +} + +// GN: //src/trace_processor/plugins/flamechart:intrinsics +filegroup { + name: "perfetto_src_trace_processor_plugins_flamechart_intrinsics", + srcs: [ + "src/trace_processor/plugins/flamechart/flamechart_function.cc", + ], +} + +// GN: //src/trace_processor/plugins/flamechart:unittests +filegroup { + name: "perfetto_src_trace_processor_plugins_flamechart_unittests", + srcs: [ + "src/trace_processor/plugins/flamechart/flamechart_unittest.cc", + ], +} + // GN: //src/trace_processor/plugins/flamegraph:flamegraph filegroup { name: "perfetto_src_trace_processor_plugins_flamegraph_flamegraph", @@ -21433,6 +21469,8 @@ ":perfetto_src_trace_processor_plugins_experimental_flamegraph_experimental_flamegraph", ":perfetto_src_trace_processor_plugins_experimental_flat_slice_experimental_flat_slice", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", + ":perfetto_src_trace_processor_plugins_flamechart_flamechart", + ":perfetto_src_trace_processor_plugins_flamechart_intrinsics", ":perfetto_src_trace_processor_plugins_flamegraph_flamegraph", ":perfetto_src_trace_processor_plugins_flamegraph_intrinsics", ":perfetto_src_trace_processor_plugins_graph_scan_graph_scan", @@ -24433,6 +24471,9 @@ ":perfetto_src_trace_processor_plugins_experimental_flat_slice_unittests", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_unittests", + ":perfetto_src_trace_processor_plugins_flamechart_flamechart", + ":perfetto_src_trace_processor_plugins_flamechart_intrinsics", + ":perfetto_src_trace_processor_plugins_flamechart_unittests", ":perfetto_src_trace_processor_plugins_flamegraph_flamegraph", ":perfetto_src_trace_processor_plugins_flamegraph_intrinsics", ":perfetto_src_trace_processor_plugins_flamegraph_unittests", @@ -25565,6 +25606,8 @@ ":perfetto_src_trace_processor_plugins_experimental_flamegraph_experimental_flamegraph", ":perfetto_src_trace_processor_plugins_experimental_flat_slice_experimental_flat_slice", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", + ":perfetto_src_trace_processor_plugins_flamechart_flamechart", + ":perfetto_src_trace_processor_plugins_flamechart_intrinsics", ":perfetto_src_trace_processor_plugins_flamegraph_flamegraph", ":perfetto_src_trace_processor_plugins_flamegraph_intrinsics", ":perfetto_src_trace_processor_plugins_graph_scan_graph_scan", @@ -26275,6 +26318,8 @@ ":perfetto_src_trace_processor_plugins_experimental_flamegraph_experimental_flamegraph", ":perfetto_src_trace_processor_plugins_experimental_flat_slice_experimental_flat_slice", ":perfetto_src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", + ":perfetto_src_trace_processor_plugins_flamechart_flamechart", + ":perfetto_src_trace_processor_plugins_flamechart_intrinsics", ":perfetto_src_trace_processor_plugins_flamegraph_flamegraph", ":perfetto_src_trace_processor_plugins_flamegraph_intrinsics", ":perfetto_src_trace_processor_plugins_graph_scan_graph_scan",
diff --git a/BUILD b/BUILD index 43be48b..be3064f 100644 --- a/BUILD +++ b/BUILD
@@ -509,6 +509,8 @@ ":src_trace_processor_plugins_experimental_flat_slice_tables", ":src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", ":src_trace_processor_plugins_experimental_slice_layout_tables", + ":src_trace_processor_plugins_flamechart_flamechart", + ":src_trace_processor_plugins_flamechart_intrinsics", ":src_trace_processor_plugins_flamegraph_flamegraph", ":src_trace_processor_plugins_flamegraph_intrinsics", ":src_trace_processor_plugins_graph_scan_graph_scan", @@ -826,6 +828,8 @@ ":src_trace_processor_plugins_experimental_flat_slice_tables", ":src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", ":src_trace_processor_plugins_experimental_slice_layout_tables", + ":src_trace_processor_plugins_flamechart_flamechart", + ":src_trace_processor_plugins_flamechart_intrinsics", ":src_trace_processor_plugins_flamegraph_flamegraph", ":src_trace_processor_plugins_flamegraph_intrinsics", ":src_trace_processor_plugins_graph_scan_graph_scan", @@ -4272,6 +4276,15 @@ ], ) +# GN target: //src/trace_processor/perfetto_sql/stdlib/std/stack_sample:stack_sample +perfetto_filegroup( + name = "src_trace_processor_perfetto_sql_stdlib_std_stack_sample_stack_sample", + srcs = [ + "src/trace_processor/perfetto_sql/stdlib/std/stack_sample/flamechart.sql", + "src/trace_processor/perfetto_sql/stdlib/std/stack_sample/mapping.sql", + ], +) + # GN target: //src/trace_processor/perfetto_sql/stdlib/std/thread:thread perfetto_filegroup( name = "src_trace_processor_perfetto_sql_stdlib_std_thread_thread", @@ -4403,6 +4416,7 @@ ":src_trace_processor_perfetto_sql_stdlib_stacks_stacks", ":src_trace_processor_perfetto_sql_stdlib_std_gpu_gpu", ":src_trace_processor_perfetto_sql_stdlib_std_metasql_metasql", + ":src_trace_processor_perfetto_sql_stdlib_std_stack_sample_stack_sample", ":src_trace_processor_perfetto_sql_stdlib_std_thread_thread", ":src_trace_processor_perfetto_sql_stdlib_std_traceinfo_traceinfo", ":src_trace_processor_perfetto_sql_stdlib_std_trees_trees", @@ -4846,6 +4860,24 @@ ], ) +# GN target: //src/trace_processor/plugins/flamechart:flamechart +perfetto_filegroup( + name = "src_trace_processor_plugins_flamechart_flamechart", + srcs = [ + "src/trace_processor/plugins/flamechart/flamechart.cc", + "src/trace_processor/plugins/flamechart/flamechart.h", + ], +) + +# GN target: //src/trace_processor/plugins/flamechart:intrinsics +perfetto_filegroup( + name = "src_trace_processor_plugins_flamechart_intrinsics", + srcs = [ + "src/trace_processor/plugins/flamechart/flamechart_function.cc", + "src/trace_processor/plugins/flamechart/flamechart_function.h", + ], +) + # GN target: //src/trace_processor/plugins/flamegraph:flamegraph perfetto_filegroup( name = "src_trace_processor_plugins_flamegraph_flamegraph", @@ -11744,6 +11776,8 @@ ":src_trace_processor_plugins_experimental_flat_slice_tables", ":src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", ":src_trace_processor_plugins_experimental_slice_layout_tables", + ":src_trace_processor_plugins_flamechart_flamechart", + ":src_trace_processor_plugins_flamechart_intrinsics", ":src_trace_processor_plugins_flamegraph_flamegraph", ":src_trace_processor_plugins_flamegraph_intrinsics", ":src_trace_processor_plugins_graph_scan_graph_scan", @@ -12092,6 +12126,8 @@ ":src_trace_processor_plugins_experimental_flat_slice_tables", ":src_trace_processor_plugins_experimental_slice_layout_experimental_slice_layout", ":src_trace_processor_plugins_experimental_slice_layout_tables", + ":src_trace_processor_plugins_flamechart_flamechart", + ":src_trace_processor_plugins_flamechart_intrinsics", ":src_trace_processor_plugins_flamegraph_flamegraph", ":src_trace_processor_plugins_flamegraph_intrinsics", ":src_trace_processor_plugins_graph_scan_graph_scan",
diff --git a/src/trace_processor/BUILD.gn b/src/trace_processor/BUILD.gn index 09c1de1..2d8d980 100644 --- a/src/trace_processor/BUILD.gn +++ b/src/trace_processor/BUILD.gn
@@ -248,6 +248,7 @@ "plugins/experimental_flamegraph", "plugins/experimental_flat_slice", "plugins/experimental_slice_layout", + "plugins/flamechart:intrinsics", "plugins/flamegraph:intrinsics", "plugins/graph_scan", "plugins/graph_traversal", @@ -482,6 +483,7 @@ "plugins/descendant:unittests", "plugins/experimental_flat_slice:unittests", "plugins/experimental_slice_layout:unittests", + "plugins/flamechart:unittests", "plugins/flamegraph:unittests", "plugins/span_join_operator:unittests", "plugins/strace:unittests",
diff --git a/src/trace_processor/perfetto_sql/stdlib/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/BUILD.gn index 7322787..a98958e 100644 --- a/src/trace_processor/perfetto_sql/stdlib/BUILD.gn +++ b/src/trace_processor/perfetto_sql/stdlib/BUILD.gn
@@ -37,6 +37,7 @@ "stacks", "std/gpu", "std/metasql", + "std/stack_sample", "std/thread", "std/traceinfo", "std/trees",
diff --git a/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/BUILD.gn new file mode 100644 index 0000000..23f3c57 --- /dev/null +++ b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/BUILD.gn
@@ -0,0 +1,22 @@ +# Copyright (C) 2026 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. + +import("../../../../../../gn/perfetto_sql.gni") + +perfetto_sql_source_set("stack_sample") { + sources = [ + "flamechart.sql", + "mapping.sql", + ] +}
diff --git a/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/flamechart.sql b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/flamechart.sql new file mode 100644 index 0000000..301e845 --- /dev/null +++ b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/flamechart.sql
@@ -0,0 +1,81 @@ +-- +-- Copyright 2026 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 +-- +-- https://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. + +-- Whether a sampling timebase supports reconstructing callstack runs over time. +-- Clock, cycle, and instruction sampling qualify. Other event counters and +-- unknown timebases do not. This describes eligibility, not duration accuracy: +-- boundaries are inferred from samples rather than recorded function exits. +CREATE PERFETTO FUNCTION _stack_sample_flamechart_supported( + -- The structured stack_sample_session.timebase_unit, not a counter name. + timebase_unit STRING +) +-- True for supported sampling timebases; false for unknown or other units. +RETURNS BOOL +AS +SELECT coalesce($timebase_unit IN ('ns', 'cycles', 'instructions'), false); + +-- sqlformat file off + +-- Computes the flame-chart rectangle set ("runs") for a stack tree and a +-- series of sample points. Zero-duration runs from stack transitions at equal +-- timestamps are omitted. +-- +-- For each stack depth, a run spans the time range over which the same frame +-- was continuously present at that depth: consecutive points sharing a stack +-- prefix extend the shared runs, only divergent depths open new ones. Runs +-- still open after the last point have duration -1 (incomplete). Consumers +-- can extend these runs to the end of the trace. +-- +-- Example usage: +-- ``` +-- SELECT ts, dur, depth, id, sample_count +-- FROM _stack_sample_flamechart_runs!( +-- _tree_from_table!( +-- (SELECT id, parent_id, name FROM stacks), +-- (name) +-- ), +-- (SELECT ts, callsite_id AS leaf_id FROM samples ORDER BY ts) +-- ); +-- ``` +CREATE PERFETTO MACRO _stack_sample_flamechart_runs( + -- A TREE pointer from _tree_from_table! encoding the stack structure. + tree Expr, + -- A table/view/subquery of sample points with columns 'ts' and 'leaf_id'. + -- Rows must be ordered by ts. 'leaf_id' references the tree's id column + -- and names the innermost (leaf) frame of the sample's stack; points with + -- a null or unresolvable leaf_id are skipped. + points TableOrSubquery +) +-- Returns the runs: ts, dur, depth (0 = outermost frame), id (the id of the +-- frame's node in the tree's source table) and sample_count (number of +-- points in the run). +RETURNS TableOrSubquery +AS ( + SELECT + c0 AS ts, + c1 AS dur, + c2 AS depth, + c3 AS id, + c4 AS sample_count + FROM __intrinsic_table_ptr( + (SELECT __intrinsic_flamechart($tree, p.ts, p.leaf_id) FROM $points AS p) + ) + WHERE + __intrinsic_table_ptr_bind(c0, 'ts') + AND __intrinsic_table_ptr_bind(c1, 'dur') + AND __intrinsic_table_ptr_bind(c2, 'depth') + AND __intrinsic_table_ptr_bind(c3, 'id') + AND __intrinsic_table_ptr_bind(c4, 'sample_count') +);
diff --git a/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/mapping.sql b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/mapping.sql new file mode 100644 index 0000000..7bdcecb --- /dev/null +++ b/src/trace_processor/perfetto_sql/stdlib/std/stack_sample/mapping.sql
@@ -0,0 +1,86 @@ +-- +-- Copyright 2026 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 +-- +-- https://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. + +-- Best-effort code origin from a mapping path. Mapping metadata does not +-- distinguish executable ELF files from shared objects, so conventional library +-- suffixes identify libraries; other ordinary filenames are treated as binaries. +-- Symbol availability and process display names do not affect this classification. +CREATE PERFETTO FUNCTION _stack_sample_mapping_category( + -- Mapping path, including any " (deleted)" suffix. + mapping_name STRING +) +-- 0: binary, 1: library, 2: kernel, 3: unknown or anonymous. +RETURNS LONG +AS +WITH + normalized AS ( + SELECT + replace( + CASE + WHEN $mapping_name GLOB '* (deleted)' THEN substr( + $mapping_name, + 1, + length($mapping_name) - 10 + ) + ELSE $mapping_name + END, + char(92), + '/' + ) AS path + ), + names AS ( + SELECT + path, + str_split(path, '/', length(path) - length(replace(path, '/', ''))) AS name + FROM normalized + ) +SELECT + CASE + WHEN path IS NULL + OR path = '' THEN 3 + WHEN path GLOB '[[]kernel*' + OR path = '/kernel' + OR path GLOB '/kernel/*' + OR name GLOB 'vmlinux*' + OR name GLOB 'vmlinuz*' + OR name GLOB '*.ko' + OR name GLOB '*.ko.xz' + OR name GLOB '*.ko.gz' + OR name GLOB '*.ko.zst' THEN 2 + WHEN name = '' + OR path GLOB '[[]*' + OR path IN ('unknown', '[unknown]') + OR path GLOB 'linux-vdso*' + OR path GLOB 'memfd:*' + OR path GLOB '/memfd:*' + OR path GLOB 'anon_inode:*' THEN 3 + WHEN lower(name) GLOB '*.so' + OR lower(name) GLOB '*.so.*' + OR lower(name) GLOB '*.dylib' + OR lower(name) GLOB '*.dll' + OR lower(name) GLOB '*.dex' + OR lower(name) GLOB '*.odex' + OR lower(name) GLOB '*.oat' + OR lower(name) GLOB '*.art' + OR lower(name) GLOB '*.jar' + OR lower(name) GLOB '*.apk' THEN 1 + ELSE 0 + END +FROM names; + +-- Classify once per mapping, shared by sample instants and callstack frames. +CREATE PERFETTO TABLE _stack_sample_mapping_classification AS +SELECT id, name, _stack_sample_mapping_category(name) AS category +FROM stack_profile_mapping;
diff --git a/src/trace_processor/plugins/flamechart/BUILD.gn b/src/trace_processor/plugins/flamechart/BUILD.gn new file mode 100644 index 0000000..b2da3ec --- /dev/null +++ b/src/trace_processor/plugins/flamechart/BUILD.gn
@@ -0,0 +1,78 @@ +# Copyright (C) 2026 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. + +import("../../../../gn/perfetto.gni") +import("../../../../gn/test.gni") + +assert(enable_perfetto_trace_processor_sqlite) + +# The flamechart computation, free of any SQLite dependency. +source_set("flamechart") { + sources = [ + "flamechart.cc", + "flamechart.h", + ] + deps = [ + "../../../../gn:default_deps", + "../../../../include/perfetto/ext/base", + "../../../base", + "../../containers", + "../../core/common", + "../../core/dataframe", + "../../core/tree", + "../../core/util", + ] +} + +perfetto_unittest_source_set("unittests") { + testonly = true + sources = [ "flamechart_unittest.cc" ] + deps = [ + ":flamechart", + "../../../../gn:default_deps", + "../../../../gn:gtest_and_gmock", + "../../../base", + "../../../base:test_support", + "../../containers", + "../../core/common", + "../../core/dataframe", + "../../core/dataframe:unittests", + "../../core/tree", + "../../core/util", + ] +} + +# The SQL intrinsic exposing the computation to PerfettoSQL. +source_set("intrinsics") { + sources = [ + "flamechart_function.cc", + "flamechart_function.h", + ] + deps = [ + ":flamechart", + "../../../../gn:default_deps", + "../../../../gn:sqlite", + "../../../base", + "../../containers", + "../../core/common", + "../../core/dataframe", + "../../core/plugin", + "../../core/tree", + "../../core/util", + "../../perfetto_sql/engine", + "../../sqlite", + "../../storage", + "../../types", + ] +}
diff --git a/src/trace_processor/plugins/flamechart/flamechart.cc b/src/trace_processor/plugins/flamechart/flamechart.cc new file mode 100644 index 0000000..bf88916 --- /dev/null +++ b/src/trace_processor/plugins/flamechart/flamechart.cc
@@ -0,0 +1,140 @@ +/* + * Copyright (C) 2026 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/plugins/flamechart/flamechart.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <vector> + +#include "perfetto/base/logging.h" +#include "perfetto/base/status.h" +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/dataframe/adhoc_dataframe_builder.h" +#include "src/trace_processor/core/dataframe/dataframe.h" +#include "src/trace_processor/core/tree/tree.h" +#include "src/trace_processor/core/util/span.h" + +namespace perfetto::trace_processor::flamechart { +namespace { + +// One open (unclosed) segment per stack depth during the sweep. +struct OpenSegment { + // Tree row index of the frame at this depth. + uint32_t row; + // Timestamp at which the segment opened. + int64_t start; + // Number of points accumulated in this segment so far. + int64_t count; +}; + +} // namespace + +base::StatusOr<dataframe::Dataframe> Build(const core::Tree& tree, + core::Span<const int64_t> ts, + core::Span<const int64_t> leaf_id, + StringPool* pool) { + PERFETTO_CHECK(ts.size() == leaf_id.size()); + + // Output ids are the tree's original node ids so consumers can join the + // runs back against the table the tree was built from. Trees without an + // Int64 id column (built by hand) fall back to row indices, matching how + // their leaf ids resolve. + const int64_t* original_ids = + !tree.columns.empty() && tree.columns[0].type.Is<core::Int64>() + ? tree.columns[0].unchecked_data<int64_t>() + : nullptr; + + // Segments are streamed straight into the output dataframe: memory stays + // O(open segments) plus the output. + dataframe::AdhocDataframeBuilder builder( + {"ts", "dur", "depth", "id", "sample_count"}, pool, + dataframe::AdhocDataframeBuilder::Options{ + {}, dataframe::NullabilityType::kDenseNull, /*emit_auto_id=*/false}); + const auto emit = [&](const OpenSegment& seg, size_t depth, int64_t dur) { + // Equal-timestamp stack transitions can close a frame immediately. + if (dur == 0) { + return; + } + builder.PushNonNull(0, seg.start); + builder.PushNonNull(1, dur); + builder.PushNonNull(2, static_cast<int64_t>(depth)); + builder.PushNonNull(3, original_ids ? original_ids[seg.row] + : static_cast<int64_t>(seg.row)); + builder.PushNonNull(4, seg.count); + }; + + std::vector<OpenSegment> open; + // Stack path of the current point, innermost frame first. + std::vector<uint32_t> path; + + int64_t last_ts = 0; + for (size_t i = 0; i < ts.size(); ++i) { + if (i > 0 && ts[i] < last_ts) { + return base::ErrStatus("flamechart: ts must be non-decreasing"); + } + last_ts = ts[i]; + + // Unresolvable leaves (e.g. a sample with no stack) are skipped; open + // segments are kept as-is, without increasing their sample counts. + const uint32_t leaf_row = tree.FindRow(leaf_id[i]); + if (leaf_row == core::Tree::kNullParent) { + continue; + } + + path.clear(); + for (uint32_t r = leaf_row; r != core::Tree::kNullParent; + r = tree.parent[r]) { + path.push_back(r); + } + + const size_t old_depth = open.size(); + const size_t new_depth = path.size(); + + // Length of the common prefix counting from the root (outermost frame): + // segments at these depths continue, everything deeper diverges. + size_t common = 0; + const size_t max_cmp = std::min(old_depth, new_depth); + while (common < max_cmp && + open[common].row == path[new_depth - 1 - common]) { + ++common; + } + + // Close the divergent tail (deepest first for a stable output order). + for (size_t d = old_depth; d > common; --d) { + emit(open[d - 1], d - 1, ts[i] - open[d - 1].start); + } + open.resize(common); + // Open new segments for the divergent tail of the new stack. + for (size_t d = common; d < new_depth; ++d) { + open.push_back(OpenSegment{path[new_depth - 1 - d], ts[i], /*count=*/0}); + } + // Every depth of the point's stack gains one sample. + for (size_t d = 0; d < new_depth; ++d) { + ++open[d].count; + } + } + + // No later observation closes these frames: emit them as incomplete. + for (size_t d = 0; d < open.size(); ++d) { + emit(open[d], d, -1); + } + + return std::move(builder).Build(); +} + +} // namespace perfetto::trace_processor::flamechart
diff --git a/src/trace_processor/plugins/flamechart/flamechart.h b/src/trace_processor/plugins/flamechart/flamechart.h new file mode 100644 index 0000000..1a26293 --- /dev/null +++ b/src/trace_processor/plugins/flamechart/flamechart.h
@@ -0,0 +1,71 @@ +/* + * Copyright (C) 2026 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_PLUGINS_FLAMECHART_FLAMECHART_H_ +#define SRC_TRACE_PROCESSOR_PLUGINS_FLAMECHART_FLAMECHART_H_ + +#include <cstdint> + +#include "perfetto/ext/base/status_or.h" +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/dataframe/dataframe.h" +#include "src/trace_processor/core/tree/tree.h" +#include "src/trace_processor/core/util/span.h" + +namespace perfetto::trace_processor::flamechart { + +// Computes the flame-chart rectangle set from a stack tree and a series of +// sample points. +// +// The tree encodes the stack structure: `tree.parent` links each node to its +// caller (row indices, kNullParent for roots, parents before children). Each +// point is a (ts[i], leaf_id[i]) pair: a sample timestamp and the tree node +// of the innermost (leaf) frame at that time. |ts| must be non-decreasing and +// the two spans must have equal size. Leaf ids are original node ids (e.g. a +// callsite id), resolved through the id -> row index persisted on the tree by +// core::BuildTree; for trees without an id column the ids are row indices. +// Unresolvable leaves are skipped: open segments are kept as-is and the gap +// does not contribute to sample counts. +// +// The returned dataframe has five columns, in this order: +// 0: ts - segment start timestamp +// 1: dur - segment duration, or -1 if still open at the last point +// 2: depth - stack depth (0 = outermost/root frame) +// 3: id - original node id of the segment's frame (the tree's id +// column), so runs join directly against the tree's source table; row +// index for trees without an id column +// 4: sample_count - number of points in the segment +// +// The output is the maximal-run (prefix-merge) decomposition: for each depth, +// a segment spans the time range over which the same frame was continuously +// present at that depth. Consecutive points sharing a stack prefix extend the +// shared segments; only divergent depths open new segments. This keeps the +// output far below (points x depth): the leaf depth yields about one segment +// per run while shallow depths yield only a handful. Segments still open +// after the last point have duration -1 (incomplete). Zero-duration segments +// from stack transitions at equal timestamps are omitted. +// +// The sweep is a single pass over the points. Each point walks its stack and +// updates counts at every depth, so time is O(sum of sample stack depths). +// Memory is O(maximum stack depth) plus the emitted output. +base::StatusOr<dataframe::Dataframe> Build(const core::Tree& tree, + core::Span<const int64_t> ts, + core::Span<const int64_t> leaf_id, + StringPool* pool); + +} // namespace perfetto::trace_processor::flamechart + +#endif // SRC_TRACE_PROCESSOR_PLUGINS_FLAMECHART_FLAMECHART_H_
diff --git a/src/trace_processor/plugins/flamechart/flamechart_function.cc b/src/trace_processor/plugins/flamechart/flamechart_function.cc new file mode 100644 index 0000000..17e7e8f --- /dev/null +++ b/src/trace_processor/plugins/flamechart/flamechart_function.cc
@@ -0,0 +1,161 @@ +/* + * Copyright (C) 2026 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/plugins/flamechart/flamechart_function.h" + +#include <cstdint> +#include <memory> +#include <vector> + +#include "perfetto/base/compiler.h" +#include "perfetto/base/logging.h" +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/dataframe/dataframe.h" +#include "src/trace_processor/core/plugin/plugin.h" +#include "src/trace_processor/core/tree/tree.h" +#include "src/trace_processor/core/util/span.h" +#include "src/trace_processor/perfetto_sql/engine/perfetto_sql_connection.h" +#include "src/trace_processor/plugins/flamechart/flamechart.h" +#include "src/trace_processor/sqlite/bindings/sqlite_aggregate_function.h" +#include "src/trace_processor/sqlite/bindings/sqlite_result.h" +#include "src/trace_processor/sqlite/bindings/sqlite_type.h" +#include "src/trace_processor/sqlite/bindings/sqlite_value.h" +#include "src/trace_processor/sqlite/sqlite_utils.h" +#include "src/trace_processor/storage/trace_storage.h" +#include "src/trace_processor/types/trace_processor_context.h" + +namespace perfetto::trace_processor { +namespace { + +constexpr char kTreePointerType[] = "TREE"; +constexpr char kTablePointerType[] = "TABLE"; + +// Aggregate computing the flame-chart runs for a stack tree and a series of +// sample points. +// +// Args, per aggregated row: +// 0: TREE pointer - the stack tree, from __intrinsic_tree_from_table. Must +// be the same tree for every row. +// 1: ts - sample timestamp (integer). Must be non-decreasing in +// aggregation order. +// 2: leaf_id - tree node id of the innermost (leaf) frame (integer). +// +// Rows with a null ts or leaf_id are skipped. Returns a +// `dataframe::Dataframe*` tagged "TABLE" with columns (ts, dur, depth, id, +// sample_count), consumed via `__intrinsic_table_ptr`; `id` is the frame's +// node id in the tree's source table. +struct FlamechartAgg : public sqlite::AggregateFunction<FlamechartAgg> { + static constexpr char kName[] = "__intrinsic_flamechart"; + static constexpr int kArgCount = 3; + using UserData = StringPool; + + struct AggCtx : sqlite::AggregateContext<AggCtx> { + const core::Tree* tree = nullptr; + bool failed = false; + std::vector<int64_t> ts; + std::vector<int64_t> leaf_id; + }; + + static void Step(sqlite3_context* ctx, int argc, sqlite3_value** argv) { + PERFETTO_DCHECK(argc == kArgCount); + auto& agg = AggCtx::GetOrCreateContextForStep(ctx); + const auto* tree = + sqlite::value::Pointer<core::Tree>(argv[0], kTreePointerType); + if (!tree) { + agg.failed = true; + return sqlite::result::Error( + ctx, "flamechart: first argument must be a TREE pointer"); + } + if (agg.tree && agg.tree != tree) { + agg.failed = true; + return sqlite::result::Error( + ctx, "flamechart: tree must be the same for every row"); + } + agg.tree = tree; + const auto ts_type = sqlite::value::Type(argv[1]); + const auto leaf_type = sqlite::value::Type(argv[2]); + if (ts_type == sqlite::Type::kNull || leaf_type == sqlite::Type::kNull) { + return; + } + if (ts_type != sqlite::Type::kInteger || + leaf_type != sqlite::Type::kInteger) { + agg.failed = true; + return sqlite::result::Error( + ctx, "flamechart: ts and leaf_id must be integers"); + } + agg.ts.push_back(sqlite::value::Int64(argv[1])); + agg.leaf_id.push_back(sqlite::value::Int64(argv[2])); + } + + static void Final(sqlite3_context* ctx) { + StringPool* pool = GetUserData(ctx); + auto raw_agg = AggCtx::GetContextOrNullForFinal(ctx); + // SQLite finalizes aggregates even after Step reports an error. Preserve + // that error and release the context without dereferencing an invalid tree. + if (raw_agg && raw_agg.get()->failed) { + return; + } + // Zero rows: build over nothing, producing an empty runs table with the + // correct schema. + const core::Tree empty_tree; + const core::Tree& tree = raw_agg ? *raw_agg.get()->tree : empty_tree; + const core::Span<const int64_t> ts = raw_agg + ? core::MakeSpan(raw_agg.get()->ts) + : core::Span<const int64_t>(); + const core::Span<const int64_t> leaf_id = + raw_agg ? core::MakeSpan(raw_agg.get()->leaf_id) + : core::Span<const int64_t>(); + SQLITE_ASSIGN_OR_RETURN(ctx, auto runs, + flamechart::Build(tree, ts, leaf_id, pool)); + return sqlite::result::UniquePointer( + ctx, std::make_unique<dataframe::Dataframe>(std::move(runs)), + kTablePointerType); + } +}; + +} // namespace + +namespace flamechart { +namespace { + +class FlamechartPlugin : public Plugin<FlamechartPlugin> { + public: + ~FlamechartPlugin() override; + + void RegisterAggregateFunctions( + PerfettoSqlConnection*, + std::vector<AggregateFunctionRegistration>& out) override { + StringPool* pool = trace_context_->storage->mutable_string_pool(); + out.push_back(MakeAggregateRegistration<FlamechartAgg>(pool)); + } +}; + +FlamechartPlugin::~FlamechartPlugin() = default; + +} // namespace + +void RegisterPlugin() { + static PluginRegistration registration( + []() -> std::unique_ptr<PluginBase> { + return std::make_unique<FlamechartPlugin>(); + }, + FlamechartPlugin::kPluginId, FlamechartPlugin::kDepIds.data(), + FlamechartPlugin::kDepIds.size()); + base::ignore_result(registration); +} + +} // namespace flamechart +} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/plugins/flamechart/flamechart_function.h b/src/trace_processor/plugins/flamechart/flamechart_function.h new file mode 100644 index 0000000..9e2af37 --- /dev/null +++ b/src/trace_processor/plugins/flamechart/flamechart_function.h
@@ -0,0 +1,29 @@ +/* + * Copyright (C) 2026 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_PLUGINS_FLAMECHART_FLAMECHART_FUNCTION_H_ +#define SRC_TRACE_PROCESSOR_PLUGINS_FLAMECHART_FLAMECHART_FUNCTION_H_ + +namespace perfetto::trace_processor::flamechart { + +// Registers the Flamechart plugin with the global plugin set. Idempotent; +// only the first call has an effect. Must run before the first GetPluginSet() +// call (i.e. before constructing TraceProcessorImpl). +void RegisterPlugin(); + +} // namespace perfetto::trace_processor::flamechart + +#endif // SRC_TRACE_PROCESSOR_PLUGINS_FLAMECHART_FLAMECHART_FUNCTION_H_
diff --git a/src/trace_processor/plugins/flamechart/flamechart_unittest.cc b/src/trace_processor/plugins/flamechart/flamechart_unittest.cc new file mode 100644 index 0000000..7b3beb8 --- /dev/null +++ b/src/trace_processor/plugins/flamechart/flamechart_unittest.cc
@@ -0,0 +1,314 @@ +/* + * Copyright (C) 2026 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/plugins/flamechart/flamechart.h" + +#include <algorithm> +#include <cstdint> +#include <memory> +#include <optional> +#include <ostream> +#include <utility> +#include <variant> +#include <vector> + +#include "perfetto/base/logging.h" +#include "src/base/test/status_matchers.h" +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/dataframe/dataframe.h" +#include "src/trace_processor/core/dataframe/dataframe_test_utils.h" +#include "src/trace_processor/core/tree/tree.h" +#include "src/trace_processor/core/util/slab.h" +#include "src/trace_processor/core/util/span.h" +#include "test/gtest_and_gmock.h" + +namespace perfetto::trace_processor::flamechart { +namespace { + +struct Node { + // Parent row index; nullopt for a root. + std::optional<uint32_t> parent; + // Optional original id; defaults to the row index (identity). + std::optional<int64_t> id; +}; + +core::Tree MakeTree(const std::vector<Node>& nodes) { + core::Tree tree; + tree.row_count = static_cast<uint32_t>(nodes.size()); + tree.parent = core::Slab<uint32_t>::Alloc(nodes.size()); + bool identity = true; + for (uint32_t i = 0; i < nodes.size(); ++i) { + tree.parent[i] = nodes[i].parent.value_or(core::Tree::kNullParent); + identity = identity && nodes[i].id.value_or(i) == i; + } + if (!identity) { + // Mirror BuildTree's tree shape: an Int64 id column plus a populated + // index over it. + tree.names = {"id"}; + auto id_col = core::Tree::Column::Create<int64_t>( + static_cast<uint32_t>(nodes.size())); + tree.id_index.identity_ids = false; + tree.id_index.hash.emplace(); + for (uint32_t i = 0; i < nodes.size(); ++i) { + const int64_t id = nodes[i].id.value_or(i); + id_col.unchecked_data<int64_t>()[i] = id; + tree.id_index.hash->Insert(id, i); + } + tree.columns.push_back(std::move(id_col)); + } + return tree; +} + +struct Row { + int64_t ts; + int64_t dur; + int64_t depth; + int64_t id; + int64_t count; + + bool operator==(const Row& o) const { + return ts == o.ts && dur == o.dur && depth == o.depth && id == o.id && + count == o.count; + } +}; + +std::ostream& operator<<(std::ostream& os, const Row& r) { + return os << "Row{" << r.ts << ", " << r.dur << ", " << r.depth << ", " + << r.id << ", " << r.count << "}"; +} + +int64_t AsInt64(const dataframe::ValueVerifier::ValueVariant& v) { + if (const auto* u32 = std::get_if<uint32_t>(&v)) { + return *u32; + } + if (const auto* i32 = std::get_if<int32_t>(&v)) { + return *i32; + } + if (const auto* i64 = std::get_if<int64_t>(&v)) { + return *i64; + } + PERFETTO_FATAL("Unexpected cell type"); +} + +std::vector<Row> ReadRuns(dataframe::Dataframe& df) { + PERFETTO_CHECK(df.column_names().size() == 5); + std::vector<dataframe::FilterSpec> filters; + auto plan = df.PlanQuery(filters, {}, {}, {}, 0b11111); + PERFETTO_CHECK(plan.ok()); + auto cursor = + std::make_unique<dataframe::Cursor<dataframe::TestRowFetcher>>(); + df.PrepareCursor(std::move(*plan), *cursor); + dataframe::TestRowFetcher fetcher; + cursor->Execute(fetcher); + + std::vector<Row> rows; + for (; !cursor->Eof(); cursor->Next()) { + dataframe::ValueVerifier verifier; + verifier.Fetch(&*cursor, 5); + rows.push_back(Row{AsInt64(verifier.values[0]), AsInt64(verifier.values[1]), + AsInt64(verifier.values[2]), AsInt64(verifier.values[3]), + AsInt64(verifier.values[4])}); + } + // Emission order is deterministic but not sorted (mid-sweep closes are + // deepest-first, final closes root-first); sort for stable expectations. + std::sort(rows.begin(), rows.end(), [](const Row& a, const Row& b) { + if (a.depth != b.depth) + return a.depth < b.depth; + if (a.ts != b.ts) + return a.ts < b.ts; + return a.id < b.id; + }); + return rows; +} + +class FlamechartRunsTest : public ::testing::Test { + protected: + base::StatusOr<dataframe::Dataframe> Build( + const core::Tree& tree, + const std::vector<int64_t>& ts, + const std::vector<int64_t>& leaf_id) { + return flamechart::Build(tree, core::MakeSpan(ts), core::MakeSpan(leaf_id), + &pool_); + } + + StringPool pool_; +}; + +// A single run: all points share the full stack, so each depth yields exactly +// one incomplete segment. +TEST_F(FlamechartRunsTest, SingleRunMergesAllPointsPerDepth) { + // Row 0 = A (root), 1 = B, 2 = C (leaf). + core::Tree tree = MakeTree({{std::nullopt, {}}, {{0}, {}}, {{1}, {}}}); + + auto result = Build(tree, {10, 20, 30}, {2, 2, 2}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 3u); + EXPECT_EQ(rows[0], (Row{10, -1, 0, 0, 3})); + EXPECT_EQ(rows[1], (Row{10, -1, 1, 1, 3})); + EXPECT_EQ(rows[2], (Row{10, -1, 2, 2, 3})); +} + +// Two runs that share a prefix: the shared depths merge into single segments +// while the divergent leaf depth opens a new segment per run. +TEST_F(FlamechartRunsTest, SharedPrefixMergesAcrossRuns) { + // 0 = A (root), 1 = B, 2 = C, 3 = D (sibling of C under B). + core::Tree tree = + MakeTree({{std::nullopt, {}}, {{0}, {}}, {{1}, {}}, {{1}, {}}}); + + auto result = Build(tree, {10, 20, 30, 40}, {2, 2, 3, 3}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 4u); + // Shared depths (A, B) span the whole range; the leaf depth has one segment + // per run: C for [10, 30), D remains incomplete from 30 onward. + EXPECT_EQ(rows[0], (Row{10, -1, 0, 0, 4})); + EXPECT_EQ(rows[1], (Row{10, -1, 1, 1, 4})); + EXPECT_EQ(rows[2], (Row{10, 20, 2, 2, 2})); + EXPECT_EQ(rows[3], (Row{30, -1, 2, 3, 2})); +} + +// Two disjoint stacks (different roots): no prefix is shared, every depth +// opens a fresh segment on the leaf change. +TEST_F(FlamechartRunsTest, DisjointStacksOpenFreshSegments) { + // 0 = A -> 1 = B -> 2 = C; 3 = D -> 4 = E. + core::Tree tree = MakeTree({{std::nullopt, {}}, + {{0}, {}}, + {{1}, {}}, + {std::nullopt, {}}, + {{3}, {}}}); + + auto result = Build(tree, {10, 20}, {2, 4}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 5u); + EXPECT_EQ(rows[0], (Row{10, 10, 0, 0, 1})); + EXPECT_EQ(rows[1], (Row{20, -1, 0, 3, 1})); + EXPECT_EQ(rows[2], (Row{10, 10, 1, 1, 1})); + EXPECT_EQ(rows[3], (Row{20, -1, 1, 4, 1})); + EXPECT_EQ(rows[4], (Row{10, 10, 2, 2, 1})); +} + +// Depth changes: the new stack extends the shared prefix and adds deeper +// levels, closing the levels that no longer exist. +TEST_F(FlamechartRunsTest, DepthChangeClosesAndOpensTail) { + // 0 = A (root) -> 1 = B; 0 = A -> 2 = C -> 3 = D. + core::Tree tree = + MakeTree({{std::nullopt, {}}, {{0}, {}}, {{0}, {}}, {{2}, {}}}); + + auto result = Build(tree, {10, 20}, {1, 3}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 4u); + EXPECT_EQ(rows[0], (Row{10, -1, 0, 0, 2})); + EXPECT_EQ(rows[1], (Row{10, 10, 1, 1, 1})); + EXPECT_EQ(rows[2], (Row{20, -1, 1, 2, 1})); + EXPECT_EQ(rows[3], (Row{20, -1, 2, 3, 1})); +} + +// Leaf ids are looked up through the tree's id -> row index, and output runs +// carry the original ids back out. +TEST_F(FlamechartRunsTest, LooksUpOriginalIds) { + // Row 0 = A (id 100), 1 = B (id 101), 2 = C (id 102). + core::Tree tree = MakeTree({{std::nullopt, 100}, {{0}, 101}, {{1}, 102}}); + + // Points reference the original ids rather than row indices. + auto result = Build(tree, {10, 20}, {102, 102}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 3u); + EXPECT_EQ(rows[0], (Row{10, -1, 0, 100, 2})); + EXPECT_EQ(rows[1], (Row{10, -1, 1, 101, 2})); + EXPECT_EQ(rows[2], (Row{10, -1, 2, 102, 2})); +} + +// Points whose leaf cannot be resolved are skipped without breaking open +// segments. +TEST_F(FlamechartRunsTest, SkipsUnresolvableLeaves) { + core::Tree tree = MakeTree({{std::nullopt, {}}, {{0}, {}}, {{1}, {}}}); + + // Second point references a leaf id that does not exist (no id column, and + // row index 42 is out of range). + auto result = Build(tree, {10, 15, 20}, {2, 42, 2}); + ASSERT_TRUE(result.ok()) << result.status().message(); + const auto rows = ReadRuns(*result); + ASSERT_EQ(rows.size(), 3u); + EXPECT_EQ(rows[0], (Row{10, -1, 0, 0, 2})); + EXPECT_EQ(rows[1], (Row{10, -1, 1, 1, 2})); + EXPECT_EQ(rows[2], (Row{10, -1, 2, 2, 2})); +} + +TEST_F(FlamechartRunsTest, SingleSampleIsIncompleteAtEveryDepth) { + core::Tree tree = MakeTree({{std::nullopt, {}}, {{0}, {}}}); + auto result = Build(tree, {10}, {1}); + ASSERT_TRUE(result.ok()) << result.status().message(); + EXPECT_EQ(ReadRuns(*result), + (std::vector<Row>{{10, -1, 0, 0, 1}, {10, -1, 1, 1, 1}})); +} + +TEST_F(FlamechartRunsTest, EqualTimestampsOmitZeroDurationFrames) { + core::Tree tree = MakeTree({{std::nullopt, {}}, {{0}, {}}, {{0}, {}}}); + auto result = Build(tree, {10, 10}, {1, 2}); + ASSERT_TRUE(result.ok()) << result.status().message(); + EXPECT_EQ(ReadRuns(*result), + (std::vector<Row>{{10, -1, 0, 0, 2}, {10, -1, 1, 2, 1}})); +} + +TEST_F(FlamechartRunsTest, EqualTimestampsOmitTransientStackAtEveryDepth) { + core::Tree tree = MakeTree({{std::nullopt, {}}, + {{0}, {}}, + {std::nullopt, {}}, + {{2}, {}}, + {std::nullopt, {}}, + {{4}, {}}}); + auto result = Build(tree, {10, 20, 20, 30}, {1, 3, 5, 1}); + ASSERT_TRUE(result.ok()) << result.status().message(); + EXPECT_EQ(ReadRuns(*result), (std::vector<Row>{{10, 10, 0, 0, 1}, + {20, 10, 0, 4, 1}, + {30, -1, 0, 0, 1}, + {10, 10, 1, 1, 1}, + {20, 10, 1, 5, 1}, + {30, -1, 1, 1, 1}})); +} + +TEST_F(FlamechartRunsTest, TrailingUnresolvableSampleLeavesFramesIncomplete) { + core::Tree tree = MakeTree({{std::nullopt, {}}, {{0}, {}}}); + auto result = Build(tree, {10, 20}, {1, 42}); + ASSERT_TRUE(result.ok()) << result.status().message(); + EXPECT_EQ(ReadRuns(*result), + (std::vector<Row>{{10, -1, 0, 0, 1}, {10, -1, 1, 1, 1}})); +} + +// No points produces an empty table with the correct schema. +TEST_F(FlamechartRunsTest, EmptyPointsProduceEmptyOutput) { + core::Tree tree = MakeTree({{std::nullopt, {}}}); + + auto result = Build(tree, {}, {}); + ASSERT_TRUE(result.ok()) << result.status().message(); + EXPECT_EQ(result->row_count(), 0u); + EXPECT_EQ(result->column_names().size(), 5u); +} + +// Out-of-order timestamps are rejected. +TEST_F(FlamechartRunsTest, RejectsUnsortedTs) { + core::Tree tree = MakeTree({{std::nullopt, {}}}); + + auto result = Build(tree, {20, 10}, {0, 0}); + EXPECT_FALSE(result.ok()); +} + +} // namespace +} // namespace perfetto::trace_processor::flamechart
diff --git a/src/trace_processor/trace_processor_impl.cc b/src/trace_processor/trace_processor_impl.cc index 35ee797..766a4d5 100644 --- a/src/trace_processor/trace_processor_impl.cc +++ b/src/trace_processor/trace_processor_impl.cc
@@ -113,6 +113,7 @@ #include "src/trace_processor/plugins/experimental_flamegraph/experimental_flamegraph.h" #include "src/trace_processor/plugins/experimental_flat_slice/experimental_flat_slice.h" #include "src/trace_processor/plugins/experimental_slice_layout/experimental_slice_layout.h" +#include "src/trace_processor/plugins/flamechart/flamechart_function.h" #include "src/trace_processor/plugins/flamegraph/flamegraph_function.h" #include "src/trace_processor/plugins/graph_scan/graph_scan.h" #include "src/trace_processor/plugins/graph_traversal/graph_traversal.h" @@ -365,6 +366,7 @@ experimental_flamegraph::RegisterPlugin(); experimental_flat_slice::RegisterPlugin(); experimental_slice_layout::RegisterPlugin(); + flamechart::RegisterPlugin(); flamegraph::RegisterPlugin(); graph_scan::RegisterPlugin(); graph_traversal::RegisterPlugin();
diff --git a/test/trace_processor/diff_tests/include_index.py b/test/trace_processor/diff_tests/include_index.py index 3ffb076..5c39ee9 100644 --- a/test/trace_processor/diff_tests/include_index.py +++ b/test/trace_processor/diff_tests/include_index.py
@@ -184,6 +184,7 @@ from diff_tests.stdlib.tests import StdlibSmoke from diff_tests.stdlib.timestamps.tests import Timestamps from diff_tests.stdlib.traced.stats import TracedStats +from diff_tests.stdlib.stack_sample.flamechart_tests import FlamechartRuns from diff_tests.stdlib.trees.table_conversion_tests import TreeRoundtrip from diff_tests.stdlib.viz.tests import Viz from diff_tests.stdlib.wattson.tests import WattsonStdlib @@ -339,6 +340,7 @@ GraphScanTests, TreeRoundtrip, ExportTests, + FlamechartRuns, Frames, GraphSearchTests, GraphPartitionTests,
diff --git a/test/trace_processor/diff_tests/stdlib/stack_sample/flamechart_tests.py b/test/trace_processor/diff_tests/stdlib/stack_sample/flamechart_tests.py new file mode 100644 index 0000000..6d7ce8b --- /dev/null +++ b/test/trace_processor/diff_tests/stdlib/stack_sample/flamechart_tests.py
@@ -0,0 +1,191 @@ +#!/usr/bin/env python3 +# Copyright (C) 2026 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. + +from python.generators.diff_tests.testing import DataPath +from python.generators.diff_tests.testing import Csv +from python.generators.diff_tests.testing import DiffTestBlueprint +from python.generators.diff_tests.testing import ExpectedError +from python.generators.diff_tests.testing import TestSuite + + +class FlamechartRuns(TestSuite): + + def test_shared_prefix_merges(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.trees.table_conversion; + INCLUDE PERFETTO MODULE std.stack_sample.flamechart; + + CREATE PERFETTO TABLE stacks AS + SELECT 100 AS id, NULL AS parent_id, 'A' AS name + UNION ALL SELECT 101, 100, 'B' + UNION ALL SELECT 102, 101, 'C' + UNION ALL SELECT 103, 101, 'D'; + + CREATE PERFETTO TABLE points AS + SELECT 10 AS ts, 102 AS leaf_id + UNION ALL SELECT 20, 102 + UNION ALL SELECT 30, 103 + UNION ALL SELECT 40, 103; + + SELECT ts, dur, depth, id, sample_count + FROM _stack_sample_flamechart_runs!( + _tree_from_table!((SELECT * FROM stacks), (name)), + (SELECT ts, leaf_id FROM points ORDER BY ts) + ) + ORDER BY depth, ts; + """, + out=Csv(""" + "ts","dur","depth","id","sample_count" + 10,-1,0,100,4 + 10,-1,1,101,4 + 10,20,2,102,2 + 30,-1,2,103,2 + """)) + + def test_null_and_unresolvable_leaves_skipped(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.trees.table_conversion; + INCLUDE PERFETTO MODULE std.stack_sample.flamechart; + + CREATE PERFETTO TABLE stacks AS + SELECT 100 AS id, NULL AS parent_id, 'A' AS name + UNION ALL SELECT 101, 100, 'B'; + + CREATE PERFETTO TABLE points AS + SELECT 10 AS ts, 101 AS leaf_id + UNION ALL SELECT 15, NULL + UNION ALL SELECT 18, 999 + UNION ALL SELECT 20, 101; + + SELECT ts, dur, depth, id, sample_count + FROM _stack_sample_flamechart_runs!( + _tree_from_table!((SELECT * FROM stacks), (name)), + (SELECT ts, leaf_id FROM points ORDER BY ts) + ) + ORDER BY depth, ts; + """, + out=Csv(""" + "ts","dur","depth","id","sample_count" + 10,-1,0,100,2 + 10,-1,1,101,2 + """)) + + def test_empty_points(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.trees.table_conversion; + INCLUDE PERFETTO MODULE std.stack_sample.flamechart; + + CREATE PERFETTO TABLE stacks AS + SELECT 100 AS id, NULL AS parent_id, 'A' AS name; + + SELECT count(*) AS cnt + FROM _stack_sample_flamechart_runs!( + _tree_from_table!((SELECT * FROM stacks), (name)), + (SELECT 0 AS ts, 0 AS leaf_id WHERE FALSE) + ); + """, + out=Csv(""" + "cnt" + 0 + """)) + + def test_supported_sampling_timebases(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.stack_sample.flamechart; + WITH units(unit) AS ( + VALUES ('ns'), ('cycles'), ('instructions'), ('count'), + ('cache-misses'), ('custom-clock'), (''), (NULL) + ) + SELECT unit, _stack_sample_flamechart_supported(unit) AS supported + FROM units; + """, + out=Csv(''' + "unit","supported" + "ns",1 + "cycles",1 + "instructions",1 + "count",0 + "cache-misses",0 + "custom-clock",0 + "",0 + "[NULL]",0 + ''')) + + def test_mapping_categories(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.stack_sample.mapping; + WITH mappings(name) AS ( + VALUES ('/out/trace_processor_shell'), ('trace_processor_shell'), + ('/out/trace_processor_shell (deleted)'), + ('/lib/libc.so.6'), ('/lib/libc.so (deleted)'), + ('/lib/libSystem.dylib'), ('C:' || char(92) || 'System32' || char(92) || 'KERNEL32.DLL'), + ('/app/base.apk'), ('/dir.so.name/trace_processor_shell'), + ('[kernel.kallsyms]'), ('/kernel'), ('/boot/vmlinux'), + ('/lib/modules/driver.ko.xz'), ('[vdso]'), ('[anon:jit]'), + ('/memfd:jit-cache (deleted)'), ('unknown'), (''), (NULL) + ) + SELECT name, _stack_sample_mapping_category(name) AS category + FROM mappings; + """, + out=Csv(r''' + "name","category" + "/out/trace_processor_shell",0 + "trace_processor_shell",0 + "/out/trace_processor_shell (deleted)",0 + "/lib/libc.so.6",1 + "/lib/libc.so (deleted)",1 + "/lib/libSystem.dylib",1 + "C:\System32\KERNEL32.DLL",1 + "/app/base.apk",1 + "/dir.so.name/trace_processor_shell",0 + "[kernel.kallsyms]",2 + "/kernel",2 + "/boot/vmlinux",2 + "/lib/modules/driver.ko.xz",2 + "[vdso]",3 + "[anon:jit]",3 + "/memfd:jit-cache (deleted)",3 + "unknown",3 + "",3 + "[NULL]",3 + ''')) + + def test_invalid_tree_reports_error_without_crashing(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query='SELECT __intrinsic_flamechart(NULL, 10, 0);', + out=ExpectedError('flamechart: first argument must be a TREE pointer')) + + def test_invalid_sample_type_reports_error(self): + return DiffTestBlueprint( + trace=DataPath('counters.json'), + query=""" + INCLUDE PERFETTO MODULE std.trees.table_conversion; + SELECT __intrinsic_flamechart( + _tree_from_table!((SELECT 0 AS id, NULL AS parent_id, 'A' AS name), (name)), + 'invalid', 0 + ); + """, + out=ExpectedError('flamechart: ts and leaf_id must be integers'))