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 18-- Given a table containing a "tree-ified" heap graph object table (i.e. 19-- by using a dominator tree or shortest path algorithm), computes a hash of 20-- the path from the root to each node in the graph based on class names. 21-- 22-- This allows an SQL aggregation of all nodes which have the same hash to 23-- build a "class-tree" instead of the object tree. 24CREATE PERFETTO MACRO _heap_graph_type_path_hash( 25 tab TableOrSubquery 26) 27RETURNS TableOrSubquery AS 28( 29 SELECT 30 id, 31 path_hash, 32 parent_path_hash 33 FROM _graph_scan!( 34 ( 35 SELECT parent_id AS source_node_id, id AS dest_node_id 36 FROM $tab 37 WHERE parent_id IS NOT NULL 38 ), 39 ( 40 SELECT 41 t.id, 42 o.type_id as parent_type_id, 43 HASH( 44 o.upid, 45 o.graph_sample_ts, 46 o.type_id, 47 IFNULL(o.root_type, ''), 48 IFNULL(o.heap_type, '') 49 ) AS path_hash, 50 0 AS parent_path_hash 51 FROM $tab t 52 JOIN heap_graph_object o USING (id) 53 WHERE t.parent_id IS NULL 54 ), 55 (parent_type_id, path_hash, parent_path_hash), 56 ( 57 SELECT 58 t.id, 59 o.type_id as parent_type_id, 60 IIF( 61 o.type_id = t.parent_type_id, 62 t.path_hash, 63 HASH(t.path_hash, o.type_id, IFNULL(o.heap_type, "")) 64 ) AS path_hash, 65 IIF( 66 o.type_id = t.parent_type_id, 67 t.parent_path_hash, 68 t.path_hash 69 ) AS parent_path_hash 70 FROM $table t 71 JOIN heap_graph_object o USING (id) 72 ) 73 ) 74 ORDER BY 75 id 76); 77 78-- Given a table containing heap graph tree-table with path hashes computed 79-- (see _heap_graph_type_path_hash macro), aggregates together all nodes 80-- with the same hash and also splits out "native size" as a separate node under 81-- the nodes which contain the native size. 82CREATE PERFETTO MACRO _heap_graph_path_hash_aggregate( 83 tab TableOrSubquery 84) 85RETURNS TableOrSubquery AS 86( 87 WITH 88 x AS ( 89 SELECT 90 o.graph_sample_ts, 91 o.upid, 92 path_hash, 93 parent_path_hash, 94 coalesce(c.deobfuscated_name, c.name) AS name, 95 o.root_type, 96 o.heap_type, 97 count() AS self_count, 98 sum(o.self_size) AS self_size, 99 sum(o.native_size > 0) AS self_native_count, 100 sum(o.native_size) AS self_native_size 101 FROM $tab 102 JOIN heap_graph_object AS o 103 USING (id) 104 JOIN heap_graph_class AS c 105 ON o.type_id = c.id 106 GROUP BY 107 path_hash 108 ) 109 SELECT 110 graph_sample_ts, 111 upid, 112 hash(path_hash, 'native', '') AS path_hash, 113 path_hash AS parent_path_hash, 114 '[native] ' || x.name AS name, 115 root_type, 116 'native' AS heap_type, 117 sum(x.self_native_count) AS self_count, 118 sum(x.self_native_size) AS self_size 119 FROM x 120 WHERE 121 x.self_native_size > 0 122 GROUP BY 123 path_hash 124 UNION ALL 125 SELECT 126 graph_sample_ts, 127 upid, 128 path_hash, 129 parent_path_hash, 130 name, 131 root_type, 132 heap_type, 133 self_count, 134 self_size 135 FROM x 136 ORDER BY 137 path_hash 138); 139 140-- Given a table containing heap graph tree-table aggregated by path hashes 141-- (see _heap_graph_path_hash_aggregate) computes the "class tree" by converting 142-- the path hashes to ids. 143-- 144-- Note that |tab| *must* be a Perfetto (e.g. not a subquery) for this macro 145-- to work. 146CREATE PERFETTO MACRO _heap_graph_path_hashes_to_class_tree( 147 tab TableOrSubquery 148) 149RETURNS TableOrSubquery AS 150( 151 SELECT 152 graph_sample_ts, 153 upid, 154 _auto_id AS id, 155 ( 156 SELECT 157 p._auto_id 158 FROM $tab AS p 159 WHERE 160 c.parent_path_hash = p.path_hash 161 ) AS parent_id, 162 name, 163 root_type, 164 heap_type, 165 self_count, 166 self_size, 167 path_hash AS path_hash_stable 168 FROM $tab AS c 169 ORDER BY 170 id 171); 172