Merge "tp: add depth column and super root fn to stdlib memory.heap_graph_dominator_tree" into main
diff --git a/src/trace_processor/perfetto_sql/stdlib/memory/heap_graph_dominator_tree.sql b/src/trace_processor/perfetto_sql/stdlib/memory/heap_graph_dominator_tree.sql
index 51217b0..2326aab 100644
--- a/src/trace_processor/perfetto_sql/stdlib/memory/heap_graph_dominator_tree.sql
+++ b/src/trace_processor/perfetto_sql/stdlib/memory/heap_graph_dominator_tree.sql
@@ -17,7 +17,7 @@
-- Excluding following types from the graph as they share objects' ownership
-- with their real (more interesting) owners and will mask their idom to be the
--- imaginary "root".
+-- "super root".
CREATE PERFETTO TABLE _excluded_type_ids AS
WITH RECURSIVE class_visitor(type_id) AS (
SELECT id AS type_id
@@ -33,6 +33,15 @@
)
SELECT * FROM class_visitor;
+-- 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 memory_heap_graph_super_root_fn()
+-- The assigned id of the "super root".
+RETURNS INT AS
+SELECT max(id) + 1 FROM heap_graph_object;
+
CREATE PERFETTO VIEW _dominator_compatible_heap_graph AS
SELECT
ref.owner_id AS source_node_id,
@@ -42,11 +51,8 @@
WHERE source_node.reachable AND source_node.type_id NOT IN _excluded_type_ids
AND ref.owned_id IS NOT NULL
UNION ALL
--- Since a Java heap graph is a "forest" structure, we need to add a imaginary
--- "root" node which connects all the roots of the forest into a single
--- connected component.
SELECT
- (SELECT max(id) + 1 FROM heap_graph_object) as source_node_id,
+ (SELECT memory_heap_graph_super_root_fn()) as source_node_id,
id AS dest_node_id
FROM heap_graph_object
WHERE root_type IS NOT NULL;
@@ -57,7 +63,7 @@
dominator_node_id AS idom_id
FROM graph_dominator_tree!(
_dominator_compatible_heap_graph,
- (SELECT max(id) + 1 FROM heap_graph_object)
+ (SELECT memory_heap_graph_super_root_fn())
)
-- Excluding the imaginary root.
WHERE dominator_node_id IS NOT NULL
@@ -65,6 +71,20 @@
-- TODO(lalitm): support create index for Perfetto tables.
ORDER BY idom_id;
+CREATE PERFETTO TABLE _heap_graph_dominator_tree_depth AS
+WITH RECURSIVE _tree_visitor(id, depth) AS (
+ -- Let the super root have depth 0.
+ SELECT id, 1 AS depth
+ FROM _heap_graph_dominator_tree
+ WHERE idom_id IN (SELECT memory_heap_graph_super_root_fn())
+ UNION ALL
+ SELECT child.id, parent.depth + 1
+ FROM _heap_graph_dominator_tree child
+ JOIN _tree_visitor parent ON child.idom_id = parent.id
+)
+SELECT * FROM _tree_visitor
+ORDER BY id;
+
-- A performance note: we need 3 memoize functions because EXPERIMENTAL_MEMOIZE
-- limits the function to return only 1 int.
-- This means the exact same "memoized dfs pass" on the tree is done 3 times, so
@@ -128,12 +148,16 @@
-- Total self_size of all objects dominated by this object, self inclusive.
dominated_size_bytes INT,
-- Total native_size of all objects dominated by this object, self inclusive.
- dominated_native_size_bytes INT
+ dominated_native_size_bytes INT,
+ -- Depth of the object in the dominator tree. Depth of root objects are 1.
+ depth INT
) AS
SELECT
- id,
- idom_id,
- _subtree_obj_count(id) AS dominated_obj_count,
- _subtree_size_bytes(id) AS dominated_size_bytes,
- _subtree_native_size_bytes(id) AS dominated_native_size_bytes
-FROM _heap_graph_dominator_tree;
+ t.id,
+ t.idom_id,
+ _subtree_obj_count(t.id) AS dominated_obj_count,
+ _subtree_size_bytes(t.id) AS dominated_size_bytes,
+ _subtree_native_size_bytes(t.id) AS dominated_native_size_bytes,
+ d.depth
+FROM _heap_graph_dominator_tree t
+JOIN _heap_graph_dominator_tree_depth d USING(id);
diff --git a/test/trace_processor/diff_tests/stdlib/memory/heap_graph_dominator_tree_tests.py b/test/trace_processor/diff_tests/stdlib/memory/heap_graph_dominator_tree_tests.py
index 0dfa07e..52bb465 100644
--- a/test/trace_processor/diff_tests/stdlib/memory/heap_graph_dominator_tree_tests.py
+++ b/test/trace_processor/diff_tests/stdlib/memory/heap_graph_dominator_tree_tests.py
@@ -32,6 +32,7 @@
node.idom_id,
node.dominated_obj_count,
node.dominated_size_bytes,
+ node.depth,
cls.name AS type_name
FROM memory_heap_graph_dominator_tree node
JOIN heap_graph_object obj USING(id)
@@ -40,29 +41,42 @@
""",
out=Csv("""
"id","idom_id","dominated_obj_count","dominated_size_bytes",\
-"type_name"
- 0,12,1,3,"A"
- 2,12,1,3,"B"
- 4,12,4,12,"C"
- 1,12,2,6,"D"
- 3,12,1,3,"E"
- 5,4,1,3,"F"
- 6,4,2,6,"G"
- 8,12,1,3,"H"
- 9,12,1,3,"I"
- 10,6,1,3,"J"
- 11,12,1,3,"K"
- 7,1,1,3,"L"
- 13,22,6,922,"M"
- 16,22,3,100,"N"
- 14,13,4,904,"O"
- 15,13,1,16,"P"
- 17,16,1,32,"Q"
- 12,25,13,39,"R"
- 22,25,10,1023,"S"
- 18,16,1,64,"T"
- 19,14,1,128,"U"
- 20,14,1,256,"V"
- 21,14,1,512,"W"
- 23,25,1,1024,"java.lang.ref.FinalizerReference"
+"depth","type_name"
+ 0,12,1,3,2,"A"
+ 2,12,1,3,2,"B"
+ 4,12,4,12,2,"C"
+ 1,12,2,6,2,"D"
+ 3,12,1,3,2,"E"
+ 5,4,1,3,3,"F"
+ 6,4,2,6,3,"G"
+ 8,12,1,3,2,"H"
+ 9,12,1,3,2,"I"
+ 10,6,1,3,4,"J"
+ 11,12,1,3,2,"K"
+ 7,1,1,3,3,"L"
+ 13,22,6,922,2,"M"
+ 16,22,3,100,2,"N"
+ 14,13,4,904,3,"O"
+ 15,13,1,16,3,"P"
+ 17,16,1,32,3,"Q"
+ 12,25,13,39,1,"R"
+ 22,25,10,1023,1,"S"
+ 18,16,1,64,3,"T"
+ 19,14,1,128,4,"U"
+ 20,14,1,256,4,"V"
+ 21,14,1,512,4,"W"
+ 23,25,1,1024,1,"java.lang.ref.FinalizerReference"
+ """))
+
+ def test_heap_graph_super_root_fn(self):
+ return DiffTestBlueprint(
+ trace=Path('heap_graph_for_dominator_tree.textproto'),
+ query="""
+ INCLUDE PERFETTO MODULE memory.heap_graph_dominator_tree;
+
+ SELECT memory_heap_graph_super_root_fn();
+ """,
+ out=Csv("""
+ "memory_heap_graph_super_root_fn()"
+ 25
"""))
