1-- 2-- Copyright 2024 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-- https://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 16INCLUDE PERFETTO MODULE android.memory.heap_graph.excluded_refs; 17 18INCLUDE PERFETTO MODULE graphs.dominator_tree; 19 20-- The assigned id of the "super root". 21-- Since a Java heap graph is a "forest" structure, we need to add a imaginary 22-- "super root" node which connects all the roots of the forest into a single 23-- connected component, so that the dominator tree algorithm can be performed. 24CREATE PERFETTO FUNCTION _heap_graph_super_root_fn() 25-- The assigned id of the "super root". 26RETURNS LONG AS 27SELECT 28 id + 1 29FROM heap_graph_object 30ORDER BY 31 id DESC 32LIMIT 1; 33 34CREATE PERFETTO TABLE _raw_heap_graph_dominator_tree AS 35SELECT 36 node_id AS id, 37 iif(dominator_node_id = _heap_graph_super_root_fn(), NULL, dominator_node_id) AS idom_id 38FROM graph_dominator_tree!( 39 ( 40 SELECT 41 ref.owner_id AS source_node_id, 42 ref.owned_id AS dest_node_id 43 FROM heap_graph_reference ref 44 JOIN heap_graph_object source_node ON ref.owner_id = source_node.id 45 WHERE source_node.reachable 46 AND ref.id NOT IN _excluded_refs 47 AND ref.owned_id IS NOT NULL 48 UNION ALL 49 SELECT 50 (SELECT _heap_graph_super_root_fn()) as source_node_id, 51 id AS dest_node_id 52 FROM heap_graph_object 53 WHERE root_type IS NOT NULL 54 ), 55 (SELECT _heap_graph_super_root_fn()) 56) 57-- Excluding the imaginary root. 58WHERE 59 dominator_node_id IS NOT NULL 60ORDER BY 61 id; 62