tp: add some macros and tables for operating on heap graphs
This prepares for the addition of flamegraphs on top of heap graphs
using SQL queries.
Change-Id: Ie579e767eea21bfa5881b2c45519bc3387512813
diff --git a/Android.bp b/Android.bp
index a16b10c..7ebf1fb 100644
--- a/Android.bp
+++ b/Android.bp
@@ -13122,8 +13122,12 @@
"src/trace_processor/perfetto_sql/stdlib/android/io.sql",
"src/trace_processor/perfetto_sql/stdlib/android/job_scheduler.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/dmabuf.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/class_tree.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_class_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/excluded_refs.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/raw_dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/process.sql",
"src/trace_processor/perfetto_sql/stdlib/android/monitor_contention.sql",
"src/trace_processor/perfetto_sql/stdlib/android/network_packets.sql",
diff --git a/BUILD b/BUILD
index 2423b1e..55b6ec0 100644
--- a/BUILD
+++ b/BUILD
@@ -2534,8 +2534,12 @@
perfetto_filegroup(
name = "src_trace_processor_perfetto_sql_stdlib_android_memory_heap_graph_heap_graph",
srcs = [
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/class_tree.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_class_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/excluded_refs.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/raw_dominator_tree.sql",
],
)
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/BUILD.gn
index 51eb1a4..c368232 100644
--- a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/BUILD.gn
@@ -16,7 +16,11 @@
perfetto_sql_source_set("heap_graph") {
sources = [
+ "class_tree.sql",
+ "dominator_class_tree.sql",
"dominator_tree.sql",
"excluded_refs.sql",
+ "helpers.sql",
+ "raw_dominator_tree.sql",
]
}
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/class_tree.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/class_tree.sql
new file mode 100644
index 0000000..6616af5
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/class_tree.sql
@@ -0,0 +1,50 @@
+--
+-- Copyright 2024 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.
+
+INCLUDE PERFETTO MODULE android.memory.heap_graph.excluded_refs;
+INCLUDE PERFETTO MODULE android.memory.heap_graph.helpers;
+INCLUDE PERFETTO MODULE graphs.search;
+
+-- Converts the heap graph into a tree by performing a BFS on the graph from
+-- the roots. This basically ends up with all paths being the shortest path
+-- from the root to the node (with lower ids being picked in the case of ties).
+CREATE PERFETTO TABLE _heap_graph_object_min_depth_tree AS
+SELECT node_id AS id, parent_node_id AS parent_id
+FROM graph_reachable_bfs!(
+ (
+ SELECT owner_id AS source_node_id, owned_id AS dest_node_id
+ FROM heap_graph_reference ref
+ WHERE ref.id NOT IN _excluded_refs AND ref.owned_id IS NOT NULL
+ ORDER BY ref.owned_id
+ ),
+ (
+ SELECT id AS node_id
+ FROM heap_graph_object
+ WHERE root_type IS NOT NULL
+ )
+)
+ORDER BY id;
+
+CREATE PERFETTO TABLE _heap_graph_path_hashes as
+SELECT *
+FROM _heap_graph_type_path_hash!(_heap_graph_object_min_depth_tree);
+
+CREATE PERFETTO TABLE _heap_graph_path_hashes_aggregated as
+SELECT *
+FROM _heap_graph_path_hash_aggregate!(_heap_graph_path_hashes);
+
+CREATE PERFETTO TABLE _heap_graph_class_tree AS
+SELECT *
+FROM _heap_graph_path_hashes_to_class_tree!(_heap_graph_path_hashes_aggregated);
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_class_tree.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_class_tree.sql
new file mode 100644
index 0000000..f0d9eea
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_class_tree.sql
@@ -0,0 +1,34 @@
+--
+-- Copyright 2024 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.
+
+INCLUDE PERFETTO MODULE android.memory.heap_graph.helpers;
+INCLUDE PERFETTO MODULE android.memory.heap_graph.raw_dominator_tree;
+
+CREATE PERFETTO TABLE _heap_graph_dominator_path_hashes as
+SELECT *
+FROM _heap_graph_type_path_hash!((
+ SELECT id, idom_id AS parent_id
+ FROM _raw_heap_graph_dominator_tree
+));
+
+CREATE PERFETTO TABLE _heap_graph_dominator_path_hashes_aggregated as
+SELECT *
+FROM _heap_graph_path_hash_aggregate!(_heap_graph_dominator_path_hashes);
+
+CREATE PERFETTO TABLE _heap_graph_dominator_class_tree AS
+SELECT *
+FROM _heap_graph_path_hashes_to_class_tree!(
+ _heap_graph_dominator_path_hashes_aggregated
+);
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql
index 00e4d41..6c12783 100644
--- a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/dominator_tree.sql
@@ -13,47 +13,8 @@
-- See the License for the specific language governing permissions and
-- limitations under the License.
-INCLUDE PERFETTO MODULE android.memory.heap_graph.excluded_refs;
-INCLUDE PERFETTO MODULE graphs.dominator_tree;
INCLUDE PERFETTO MODULE graphs.scan;
-
--- The assigned id of the "super root".
--- Since a Java heap graph is a "forest" structure, we need to add a imaginary
--- "super root" node which connects all the roots of the forest into a single
--- connected component, so that the dominator tree algorithm can be performed.
-CREATE PERFETTO FUNCTION _heap_graph_super_root_fn()
--- The assigned id of the "super root".
-RETURNS INT AS
-SELECT id + 1
-FROM heap_graph_object
-ORDER BY id DESC
-LIMIT 1;
-
-CREATE PERFETTO VIEW _dominator_compatible_heap_graph AS
-SELECT
- ref.owner_id AS source_node_id,
- ref.owned_id AS dest_node_id
-FROM heap_graph_reference ref
-JOIN heap_graph_object source_node ON ref.owner_id = source_node.id
-WHERE source_node.reachable
- AND ref.id NOT IN _excluded_refs
- AND ref.owned_id IS NOT NULL
-UNION ALL
-SELECT
- (SELECT _heap_graph_super_root_fn()) as source_node_id,
- id AS dest_node_id
-FROM heap_graph_object
-WHERE root_type IS NOT NULL;
-
-CREATE PERFETTO TABLE _raw_heap_graph_dominator_tree AS
-SELECT node_id AS id, dominator_node_id as idom_id
-FROM graph_dominator_tree!(
- _dominator_compatible_heap_graph,
- (SELECT _heap_graph_super_root_fn())
-)
--- Excluding the imaginary root.
-WHERE dominator_node_id IS NOT NULL
-ORDER BY id;
+INCLUDE PERFETTO MODULE android.memory.heap_graph.raw_dominator_tree;
CREATE PERFETTO TABLE _heap_graph_dominator_tree_bottom_up_scan AS
SELECT *
@@ -61,7 +22,7 @@
(
SELECT id AS source_node_id, idom_id AS dest_node_id
FROM _raw_heap_graph_dominator_tree
- WHERE idom_id != _heap_graph_super_root_fn()
+ WHERE idom_id IS NOT NULL
),
(
SELECT
@@ -102,12 +63,12 @@
(
SELECT idom_id AS source_node_id, id AS dest_node_id
FROM _raw_heap_graph_dominator_tree
- WHERE idom_id != _heap_graph_super_root_fn()
+ WHERE idom_id IS NOT NULL
),
(
SELECT id, 1 AS depth
FROM _raw_heap_graph_dominator_tree
- WHERE idom_id = _heap_graph_super_root_fn()
+ WHERE idom_id IS NULL
),
(depth),
(SELECT t.id, t.depth + 1 AS depth FROM $table t)
@@ -139,7 +100,7 @@
) AS
SELECT
r.id,
- IIF(r.idom_id = _heap_graph_super_root_fn(), NULL, r.idom_id) AS idom_id,
+ r.idom_id AS idom_id,
d.subtree_count AS dominated_obj_count,
d.subtree_size_bytes AS dominated_size_bytes,
d.subtree_native_size_bytes AS dominated_native_size_bytes,
@@ -147,5 +108,5 @@
FROM _raw_heap_graph_dominator_tree r
JOIN _heap_graph_dominator_tree_bottom_up_scan d USING(id)
JOIN _heap_graph_dominator_tree_top_down_scan t USING (id)
-WHERE r.id != _heap_graph_super_root_fn()
+WHERE r.id IS NOT NULL
ORDER BY id;
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql
new file mode 100644
index 0000000..ba6a7b1
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql
@@ -0,0 +1,146 @@
+--
+-- Copyright 2024 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.
+
+INCLUDE PERFETTO MODULE graphs.scan;
+
+-- Given a table containing a "tree-ified" heap graph object table (i.e.
+-- by using a dominator tree or shortest path algorithm), computes a hash of
+-- the path from the root to each node in the graph based on class names.
+--
+-- This allows an SQL aggregation of all nodes which have the same hash to
+-- build a "class-tree" instead of the object tree.
+CREATE PERFETTO MACRO _heap_graph_type_path_hash(tab TableOrSubquery)
+RETURNS TableOrSubquery
+AS (
+ SELECT id, path_hash, parent_path_hash
+ FROM _graph_scan!(
+ (
+ SELECT parent_id AS source_node_id, id AS dest_node_id
+ FROM $tab
+ WHERE parent_id IS NOT NULL
+ ),
+ (
+ SELECT
+ t.id,
+ o.type_id as parent_type_id,
+ HASH(
+ o.upid,
+ o.graph_sample_ts,
+ o.type_id,
+ IFNULL(o.root_type, '')
+ ) AS path_hash,
+ 0 AS parent_path_hash
+ FROM $tab t
+ JOIN heap_graph_object o USING (id)
+ WHERE t.parent_id IS NULL
+ ),
+ (parent_type_id, path_hash, parent_path_hash),
+ (
+ SELECT
+ t.id,
+ o.type_id as parent_type_id,
+ IIF(
+ o.type_id = t.parent_type_id,
+ t.path_hash,
+ HASH(t.path_hash, o.type_id)
+ ) AS path_hash,
+ IIF(
+ o.type_id = t.parent_type_id,
+ t.parent_path_hash,
+ t.path_hash
+ ) AS parent_path_hash
+ FROM $table t
+ JOIN heap_graph_object o USING (id)
+ )
+ )
+ ORDER BY id
+);
+
+-- Given a table containing heap graph tree-table with path hashes computed
+-- (see _heap_graph_type_path_hash macro), aggregates together all nodes
+-- with the same hash and also splits out "native size" as a separate node under
+-- the nodes which contain the native size.
+CREATE PERFETTO MACRO _heap_graph_path_hash_aggregate(tab TableOrSubquery)
+RETURNS TableOrSubquery
+AS (
+ with x AS (
+ SELECT
+ o.graph_sample_ts,
+ o.upid,
+ path_hash,
+ parent_path_hash,
+ COALESCE(
+ c.deobfuscated_name || ' [' || o.root_type || ']',
+ c.name || ' [' || o.root_type || ']',
+ c.deobfuscated_name,
+ c.name
+ ) AS name,
+ COUNT() AS self_count,
+ SUM(o.self_size) AS self_size,
+ SUM(o.native_size > 0) AS self_native_count,
+ SUM(o.native_size) AS self_native_size
+ FROM $tab
+ JOIN heap_graph_object o USING (id)
+ JOIN heap_graph_class c ON o.type_id = c.id
+ GROUP BY path_hash
+ )
+ SELECT
+ graph_sample_ts,
+ upid,
+ HASH(path_hash, 'native', '') AS path_hash,
+ path_hash AS parent_path_hash,
+ '[native] ' || x.name AS name,
+ SUM(x.self_native_count) AS self_count,
+ SUM(x.self_native_size) AS self_size
+ FROM x
+ WHERE x.self_native_size > 0
+ GROUP BY path_hash
+ UNION ALL
+ SELECT
+ graph_sample_ts,
+ upid,
+ path_hash,
+ parent_path_hash,
+ name,
+ self_count,
+ self_size
+ FROM x
+ ORDER BY path_hash
+);
+
+-- Given a table containing heap graph tree-table aggregated by path hashes
+-- (see _heap_graph_path_hash_aggregate) computes the "class tree" by converting
+-- the path hashes to ids.
+--
+-- Note that |tab| *must* be a Perfetto (e.g. not a subquery) for this macro
+-- to work.
+CREATE PERFETTO MACRO _heap_graph_path_hashes_to_class_tree(tab TableOrSubquery)
+RETURNS TableOrSubquery
+AS (
+ SELECT
+ graph_sample_ts,
+ upid,
+ _auto_id AS id,
+ (
+ SELECT p._auto_id
+ FROM $tab p
+ WHERE c.parent_path_hash = p.path_hash
+ ) AS parent_id,
+ name,
+ self_count,
+ self_size
+ FROM $tab c
+ ORDER BY id
+);
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/raw_dominator_tree.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/raw_dominator_tree.sql
new file mode 100644
index 0000000..b6d41fb
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/raw_dominator_tree.sql
@@ -0,0 +1,61 @@
+--
+-- Copyright 2024 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.
+
+INCLUDE PERFETTO MODULE android.memory.heap_graph.excluded_refs;
+INCLUDE PERFETTO MODULE graphs.dominator_tree;
+
+-- The assigned id of the "super root".
+-- Since a Java heap graph is a "forest" structure, we need to add a imaginary
+-- "super root" node which connects all the roots of the forest into a single
+-- connected component, so that the dominator tree algorithm can be performed.
+CREATE PERFETTO FUNCTION _heap_graph_super_root_fn()
+-- The assigned id of the "super root".
+RETURNS INT AS
+SELECT id + 1
+FROM heap_graph_object
+ORDER BY id DESC
+LIMIT 1;
+
+CREATE PERFETTO VIEW _dominator_compatible_heap_graph AS
+SELECT
+ ref.owner_id AS source_node_id,
+ ref.owned_id AS dest_node_id
+FROM heap_graph_reference ref
+JOIN heap_graph_object source_node ON ref.owner_id = source_node.id
+WHERE source_node.reachable
+ AND ref.id NOT IN _excluded_refs
+ AND ref.owned_id IS NOT NULL
+UNION ALL
+SELECT
+ (SELECT _heap_graph_super_root_fn()) as source_node_id,
+ id AS dest_node_id
+FROM heap_graph_object
+WHERE root_type IS NOT NULL;
+
+CREATE PERFETTO TABLE _raw_heap_graph_dominator_tree AS
+SELECT
+ node_id AS id,
+ iif(
+ dominator_node_id = _heap_graph_super_root_fn(),
+ null,
+ dominator_node_id
+ ) as idom_id
+FROM graph_dominator_tree!(
+ _dominator_compatible_heap_graph,
+ (SELECT _heap_graph_super_root_fn())
+)
+-- Excluding the imaginary root.
+WHERE dominator_node_id IS NOT NULL
+ORDER BY id;
