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 16-- Computes the "reachable" set of nodes in a directed graph from a given 17-- starting node by performing a depth-first search on the graph. The returned 18-- nodes are structured as a tree with parent-child relationships corresponding 19-- to the order in which nodes were encountered by the DFS. 20-- 21-- While this macro can be used directly by end users (hence being public), 22-- it is primarily intended as a lower-level building block upon which higher 23-- level functions/macros in the standard library can be built. 24-- 25-- Example usage on traces containing heap graphs: 26-- ``` 27-- -- Compute the reachable nodes from the first heap root. 28-- SELECT * 29-- FROM graph_reachable_dfs!( 30-- ( 31-- SELECT 32-- owner_id AS source_node_id, 33-- owned_id as dest_node_id 34-- FROM heap_graph_reference 35-- WHERE owned_id IS NOT NULL 36-- ), 37-- (SELECT id FROM heap_graph_object WHERE root_type IS NOT NULL LIMIT 1) 38-- ); 39-- ``` 40CREATE PERFETTO MACRO graph_reachable_dfs( 41 -- A table/view/subquery corresponding to a directed graph on which the 42 -- reachability search should be performed. This table must have the columns 43 -- "source_node_id" and "dest_node_id" corresponding to the two nodes on 44 -- either end of the edges in the graph. 45 -- 46 -- Note: the columns must contain uint32 similar to ids in trace processor 47 -- tables (i.e. the values should be relatively dense and close to zero). The 48 -- implementation makes assumptions on this for performance reasons and, if 49 -- this criteria is not, can lead to enormous amounts of memory being 50 -- allocated. 51 graph_table TableOrSubquery, 52 -- The start node to |graph_table| which will be the root of the reachability 53 -- tree. 54 start_node_id Expr 55) 56-- The returned table has the schema (node_id UINT32, parent_node_id UINT32). 57-- |node_id| is the id of the node from the input graph and |parent_node_id| 58-- is the id of the node which was the first encountered predecessor in a DFS 59-- search of the graph. 60RETURNS TableOrSubquery AS 61( 62 -- Rename the generic columns of __intrinsic_table_ptr to the actual columns. 63 SELECT c0 AS node_id, c1 AS parent_node_id 64 FROM __intrinsic_table_ptr(( 65 -- Aggregate function to perform a DFS on the nodes on the input graph. 66 SELECT __intrinsic_dfs(g.source_node_id, g.dest_node_id, $start_node_id) 67 FROM $graph_table g 68 )) 69 -- Bind the dynamic columns in the |__intrinsic_table_ptr| to the columns of 70 -- the DFS table. 71 WHERE __intrinsic_table_ptr_bind(c0, 'node_id') 72 AND __intrinsic_table_ptr_bind(c1, 'parent_node_id') 73); 74 75-- Computes the next sibling node in a directed graph. The next node under a parent node 76-- is determined by on the |sort_key|, which should be unique for every node under a parent. 77-- The order of the next sibling is undefined if the |sort_key| is not unique. 78-- 79-- Example usage: 80-- ``` 81-- -- Compute the next sibling: 82-- SELECT * 83-- FROM graph_next_sibling!( 84-- ( 85-- SELECT 86-- id AS node_id, 87-- parent_id AS node_parent_id, 88-- ts AS sort_key 89-- FROM slice 90-- ) 91-- ); 92-- ``` 93CREATE PERFETTO MACRO graph_next_sibling( 94 -- A table/view/subquery corresponding to a directed graph for which to find the next sibling. 95 -- This table must have the columns "node_id", "node_parent_id" and "sort_key". 96 graph_table TableOrSubquery 97) 98-- The returned table has the schema (node_id UINT32, next_node_id UINT32). 99-- |node_id| is the id of the node from the input graph and |next_node_id| 100-- is the id of the node which is its next sibling. 101RETURNS TableOrSubquery AS 102( 103 SELECT node_id, lead(node_id) OVER (PARTITION BY node_parent_id ORDER BY sort_key) AS next_node_id 104 FROM $graph_table 105); 106 107-- Computes the "reachable" set of nodes in a directed graph from a set of 108-- starting (root) nodes by performing a depth-first search from each root node on the graph. 109-- The search is bounded by the sum of edge weights on the path and the root node specifies the 110-- max weight (inclusive) allowed before stopping the search. 111-- The returned nodes are structured as a tree with parent-child relationships corresponding 112-- to the order in which nodes were encountered by the DFS. Each row also has the root node from 113-- which where the edge was encountered. 114-- 115-- While this macro can be used directly by end users (hence being public), 116-- it is primarily intended as a lower-level building block upon which higher 117-- level functions/macros in the standard library can be built. 118-- 119-- Example usage on traces with sched info: 120-- ``` 121-- -- Compute the reachable nodes from a sched wakeup chain 122-- INCLUDE PERFETTO MODULE sched.thread_executing_spans; 123-- 124-- SELECT * 125-- FROM 126-- graph_reachable_dfs_bounded 127-- !( 128-- ( 129-- SELECT 130-- id AS source_node_id, 131-- COALESCE(parent_id, id) AS dest_node_id, 132-- id - COALESCE(parent_id, id) AS edge_weight 133-- FROM _wakeup_chain 134-- ), 135-- ( 136-- SELECT 137-- id AS root_node_id, 138-- id - COALESCE(prev_id, id) AS root_target_weight 139-- FROM _wakeup_chain 140-- )); 141-- ``` 142CREATE PERFETTO MACRO graph_reachable_weight_bounded_dfs( 143 -- A table/view/subquery corresponding to a directed graph on which the 144 -- reachability search should be performed. This table must have the columns 145 -- "source_node_id" and "dest_node_id" corresponding to the two nodes on 146 -- either end of the edges in the graph and an "edge_weight" corresponding to the 147 -- weight of the edge between the node. 148 -- 149 -- Note: the columns must contain uint32 similar to ids in trace processor 150 -- tables (i.e. the values should be relatively dense and close to zero). The 151 -- implementation makes assumptions on this for performance reasons and, if 152 -- this criteria is not, can lead to enormous amounts of memory being 153 -- allocated. 154 graph_table TableOrSubquery, 155 -- A table/view/subquery corresponding to start nodes to |graph_table| which will be the 156 -- roots of the reachability trees. This table must have the columns 157 -- "root_node_id" and "root_target_weight" corresponding to the starting node id and the max 158 -- weight allowed on the tree. 159 -- 160 -- Note: the columns must contain uint32 similar to ids in trace processor 161 -- tables (i.e. the values should be relatively dense and close to zero). The 162 -- implementation makes assumptions on this for performance reasons and, if 163 -- this criteria is not, can lead to enormous amounts of memory being 164 -- allocated. 165 root_table TableOrSubquery, 166 -- Whether the target_weight is a floor weight or ceiling weight. 167 -- If it's floor, the search stops right after we exceed the target weight, and we 168 -- include the node that pushed just passed the target. If ceiling, the search stops 169 -- right before the target weight and the node that would have pushed us passed the 170 -- target is not included. 171 is_target_weight_floor Expr 172 173) 174-- The returned table has the schema (root_node_id, node_id UINT32, parent_node_id UINT32). 175-- |root_node_id| is the id of the starting node under which this edge was encountered. 176-- |node_id| is the id of the node from the input graph and |parent_node_id| 177-- is the id of the node which was the first encountered predecessor in a DFS 178-- search of the graph. 179RETURNS TableOrSubquery AS 180( 181 WITH __temp_graph_table AS (SELECT * FROM $graph_table), 182 __temp_root_table AS (SELECT * FROM $root_table) 183 SELECT dt.root_node_id, dt.node_id, dt.parent_node_id 184 FROM __intrinsic_dfs_weight_bounded( 185 (SELECT RepeatedField(source_node_id) FROM __temp_graph_table), 186 (SELECT RepeatedField(dest_node_id) FROM __temp_graph_table), 187 (SELECT RepeatedField(edge_weight) FROM __temp_graph_table), 188 (SELECT RepeatedField(root_node_id) FROM __temp_root_table), 189 (SELECT RepeatedField(root_target_weight) FROM __temp_root_table), 190 $is_target_weight_floor 191 ) dt 192); 193