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 graphs.scan; 17 18INCLUDE PERFETTO MODULE android.memory.heap_graph.raw_dominator_tree; 19 20CREATE PERFETTO TABLE _heap_graph_dominator_tree_bottom_up_scan AS 21SELECT 22 * 23FROM _graph_aggregating_scan!( 24 ( 25 SELECT id AS source_node_id, idom_id AS dest_node_id 26 FROM _raw_heap_graph_dominator_tree 27 WHERE idom_id IS NOT NULL 28 ), 29 ( 30 SELECT 31 p.id, 32 1 AS subtree_count, 33 o.self_size AS subtree_size_bytes, 34 o.native_size AS subtree_native_size_bytes 35 FROM _raw_heap_graph_dominator_tree p 36 JOIN heap_graph_object o USING (id) 37 LEFT JOIN _raw_heap_graph_dominator_tree c ON p.id = c.idom_id 38 WHERE c.id IS NULL 39 ), 40 (subtree_count, subtree_size_bytes, subtree_native_size_bytes), 41 ( 42 WITH children_agg AS ( 43 SELECT 44 t.id, 45 SUM(t.subtree_count) AS subtree_count, 46 SUM(t.subtree_size_bytes) AS subtree_size_bytes, 47 SUM(t.subtree_native_size_bytes) AS subtree_native_size_bytes 48 FROM $table t 49 GROUP BY t.id 50 ) 51 SELECT 52 c.id, 53 c.subtree_count + 1 AS subtree_count, 54 c.subtree_size_bytes + self_size AS subtree_size_bytes, 55 c.subtree_native_size_bytes + native_size AS subtree_native_size_bytes 56 FROM children_agg c 57 JOIN heap_graph_object o USING (id) 58 ) 59) 60ORDER BY 61 id; 62 63CREATE PERFETTO TABLE _heap_graph_dominator_tree_top_down_scan AS 64SELECT 65 * 66FROM _graph_scan!( 67 ( 68 SELECT idom_id AS source_node_id, id AS dest_node_id 69 FROM _raw_heap_graph_dominator_tree 70 WHERE idom_id IS NOT NULL 71 ), 72 ( 73 SELECT id, 1 AS depth 74 FROM _raw_heap_graph_dominator_tree 75 WHERE idom_id IS NULL 76 ), 77 (depth), 78 (SELECT t.id, t.depth + 1 AS depth FROM $table t) 79) 80ORDER BY 81 id; 82 83-- All reachable heap graph objects, their immediate dominators and summary of 84-- their dominated sets. 85-- The heap graph dominator tree is calculated by stdlib graphs.dominator_tree. 86-- Each reachable object is a node in the dominator tree, their immediate 87-- dominator is their parent node in the tree, and their dominated set is all 88-- their descendants in the tree. All size information come from the 89-- heap_graph_object prelude table. 90CREATE PERFETTO TABLE heap_graph_dominator_tree ( 91 -- Heap graph object id. 92 id LONG, 93 -- Immediate dominator object id of the object. If the immediate dominator 94 -- is the "super-root" (i.e. the object is a root or is dominated by multiple 95 -- roots) then `idom_id` will be NULL. 96 idom_id LONG, 97 -- Count of all objects dominated by this object, self inclusive. 98 dominated_obj_count LONG, 99 -- Total self_size of all objects dominated by this object, self inclusive. 100 dominated_size_bytes LONG, 101 -- Total native_size of all objects dominated by this object, self inclusive. 102 dominated_native_size_bytes LONG, 103 -- Depth of the object in the dominator tree. Depth of root objects are 1. 104 depth LONG 105) AS 106SELECT 107 r.id, 108 r.idom_id AS idom_id, 109 d.subtree_count AS dominated_obj_count, 110 d.subtree_size_bytes AS dominated_size_bytes, 111 d.subtree_native_size_bytes AS dominated_native_size_bytes, 112 t.depth 113FROM _raw_heap_graph_dominator_tree AS r 114JOIN _heap_graph_dominator_tree_bottom_up_scan AS d 115 USING (id) 116JOIN _heap_graph_dominator_tree_top_down_scan AS t 117 USING (id) 118WHERE 119 r.id IS NOT NULL 120ORDER BY 121 id; 122