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 17INCLUDE PERFETTO MODULE slices.flat_slices; 18INCLUDE PERFETTO MODULE sched.thread_executing_span; 19 20CREATE PERFETTO TABLE _critical_path_all AS 21SELECT * FROM _thread_executing_span_critical_path_all(); 22 23-- Limited thread_state view that will later be span joined with the |_thread_executing_span_graph|. 24CREATE PERFETTO VIEW _span_thread_state_view 25AS SELECT id AS thread_state_id, ts, dur, utid, state, blocked_function as function, io_wait, cpu FROM thread_state; 26 27-- Limited slice_view that will later be span joined with the |_thread_executing_span_graph|. 28CREATE PERFETTO VIEW _span_slice_view 29AS 30SELECT 31 slice_id, 32 depth AS slice_depth, 33 name AS slice_name, 34 CAST(ts AS INT) AS ts, 35 CAST(dur AS INT) AS dur, 36 utid 37FROM _slice_flattened; 38 39CREATE VIRTUAL TABLE _span_thread_state_slice_view 40USING 41 SPAN_LEFT_JOIN( 42 _span_thread_state_view PARTITIONED utid, 43 _span_slice_view PARTITIONED utid); 44 45-- |_thread_executing_span_graph| span joined with thread_state information. 46CREATE VIRTUAL TABLE _span_critical_path_thread_state_slice_sp 47USING 48 SPAN_JOIN( 49 _critical_path_all PARTITIONED utid, 50 _span_thread_state_slice_view PARTITIONED utid); 51 52-- |_thread_executing_span_graph| + thread_state view joined with critical_path information. 53CREATE PERFETTO TABLE _critical_path_thread_state_slice AS 54WITH span_starts AS ( 55 SELECT 56 span.id, 57 span.utid, 58 span.critical_path_id, 59 span.critical_path_blocked_dur, 60 span.critical_path_blocked_state, 61 span.critical_path_blocked_function, 62 span.critical_path_utid, 63 thread_state_id, 64 MAX(thread_state.ts, span.ts) AS ts, 65 span.ts + span.dur AS span_end_ts, 66 thread_state.ts + thread_state.dur AS thread_state_end_ts, 67 thread_state.state, 68 thread_state.function, 69 thread_state.cpu, 70 thread_state.io_wait, 71 thread_state.slice_id, 72 thread_state.slice_name, 73 thread_state.slice_depth 74 FROM _critical_path_all span 75 JOIN _span_critical_path_thread_state_slice_sp thread_state USING(id) 76 ) 77SELECT 78 id, 79 thread_state_id, 80 ts, 81 MIN(span_end_ts, thread_state_end_ts) - ts AS dur, 82 utid, 83 state, 84 function, 85 cpu, 86 io_wait, 87 slice_id, 88 slice_name, 89 slice_depth, 90 critical_path_id, 91 critical_path_blocked_dur, 92 critical_path_blocked_state, 93 critical_path_blocked_function, 94 critical_path_utid 95FROM span_starts 96WHERE MIN(span_end_ts, thread_state_end_ts) - ts > 0; 97 98-- Flattened slices span joined with their thread_states. This contains the 'self' information 99-- without 'critical_path' (blocking) information. 100CREATE VIRTUAL TABLE _self_sp USING 101 SPAN_LEFT_JOIN(thread_state PARTITIONED utid, _slice_flattened PARTITIONED utid); 102 103-- Limited view of |_self_sp|. 104CREATE PERFETTO VIEW _self_view 105 AS 106 SELECT 107 id AS self_thread_state_id, 108 slice_id AS self_slice_id, 109 ts, 110 dur, 111 utid AS critical_path_utid, 112 state AS self_state, 113 blocked_function AS self_function, 114 cpu AS self_cpu, 115 io_wait AS self_io_wait, 116 name AS self_slice_name, 117 depth AS self_slice_depth 118 FROM _self_sp; 119 120-- Self and critical path span join. This contains the union of the time intervals from the following: 121-- a. Self slice stack + thread_state. 122-- b. Critical path stack + thread_state. 123CREATE VIRTUAL TABLE _self_and_critical_path_sp 124USING 125 SPAN_JOIN( 126 _self_view PARTITIONED critical_path_utid, 127 _critical_path_thread_state_slice PARTITIONED critical_path_utid); 128 129-- Returns a view of |_self_and_critical_path_sp| unpivoted over the following columns: 130-- self thread_state. 131-- self blocked_function (if one exists). 132-- self process_name (enabled with |enable_process_name|). 133-- self thread_name (enabled with |enable_thread_name|). 134-- self slice_stack (enabled with |enable_self_slice|). 135-- critical_path thread_state. 136-- critical_path process_name. 137-- critical_path thread_name. 138-- critical_path slice_stack (enabled with |enable_critical_path_slice|). 139-- running cpu (if one exists). 140-- A 'stack' is the group of resulting unpivoted rows sharing the same timestamp. 141CREATE PERFETTO FUNCTION _critical_path_stack(critical_path_utid INT, ts LONG, dur LONG, enable_process_name INT, enable_thread_name INT, enable_self_slice INT, enable_critical_path_slice INT) 142RETURNS 143 TABLE( 144 id INT, 145 ts LONG, 146 dur LONG, 147 utid INT, 148 stack_depth INT, 149 name STRING, 150 table_name STRING, 151 critical_path_utid INT) AS 152 -- Spans filtered to the query time window and critical_path_utid. 153 -- This is a preliminary step that gets the start and end ts of all the rows 154 -- so that we can chop the ends of each interval correctly if it overlaps with the query time interval. 155 WITH relevant_spans_starts AS ( 156 SELECT 157 self_thread_state_id, 158 self_state, 159 self_slice_id, 160 self_slice_name, 161 self_slice_depth, 162 self_function, 163 self_io_wait, 164 thread_state_id, 165 state, 166 function, 167 io_wait, 168 slice_id, 169 slice_name, 170 slice_depth, 171 cpu, 172 utid, 173 MAX(ts, $ts) AS ts, 174 MIN(ts + dur, $ts + $dur) AS end_ts, 175 critical_path_utid 176 FROM _self_and_critical_path_sp 177 WHERE dur > 0 AND critical_path_utid = $critical_path_utid 178 ), 179 -- This is the final step that gets the |dur| of each span from the start and 180 -- and end ts of the previous step. 181 -- Now we manually unpivot the result with 3 key steps: 1) Self 2) Critical path 3) CPU 182 -- This CTE is heavily used throughout the entire function so materializing it is 183 -- very important. 184 relevant_spans AS MATERIALIZED ( 185 SELECT 186 self_thread_state_id, 187 self_state, 188 self_slice_id, 189 self_slice_name, 190 self_slice_depth, 191 self_function, 192 self_io_wait, 193 thread_state_id, 194 state, 195 function, 196 io_wait, 197 slice_id, 198 slice_name, 199 slice_depth, 200 cpu, 201 utid, 202 ts, 203 end_ts - ts AS dur, 204 critical_path_utid, 205 utid 206 FROM relevant_spans_starts 207 WHERE dur > 0 208 ), 209 -- 1. Builds the 'self' stack of items as an ordered UNION ALL 210 self_stack AS MATERIALIZED ( 211 -- Builds the self thread_state 212 SELECT 213 self_thread_state_id AS id, 214 ts, 215 dur, 216 critical_path_utid AS utid, 217 0 AS stack_depth, 218 'thread_state: ' || self_state AS name, 219 'thread_state' AS table_name, 220 critical_path_utid 221 FROM relevant_spans 222 UNION ALL 223 -- Builds the self kernel blocked_function 224 SELECT 225 self_thread_state_id AS id, 226 ts, 227 dur, 228 critical_path_utid AS utid, 229 1 AS stack_depth, 230 IIF(self_state GLOB 'R*', NULL, 'kernel function: ' || self_function) AS name, 231 'thread_state' AS table_name, 232 critical_path_utid 233 FROM relevant_spans 234 UNION ALL 235 -- Builds the self kernel io_wait 236 SELECT 237 self_thread_state_id AS id, 238 ts, 239 dur, 240 critical_path_utid AS utid, 241 2 AS stack_depth, 242 IIF(self_state GLOB 'R*', NULL, 'io_wait: ' || self_io_wait) AS name, 243 'thread_state' AS table_name, 244 critical_path_utid 245 FROM relevant_spans 246 UNION ALL 247 -- Builds the self process_name 248 SELECT 249 self_thread_state_id AS id, 250 ts, 251 dur, 252 thread.utid, 253 3 AS stack_depth, 254 IIF($enable_process_name, 'process_name: ' || process.name, NULL) AS name, 255 'thread_state' AS table_name, 256 critical_path_utid 257 FROM relevant_spans 258 LEFT JOIN thread 259 ON thread.utid = critical_path_utid 260 LEFT JOIN process 261 USING (upid) 262 -- Builds the self thread_name 263 UNION ALL 264 SELECT 265 self_thread_state_id AS id, 266 ts, 267 dur, 268 thread.utid, 269 4 AS stack_depth, 270 IIF($enable_thread_name, 'thread_name: ' || thread.name, NULL) AS name, 271 'thread_state' AS table_name, 272 critical_path_utid 273 FROM relevant_spans 274 LEFT JOIN thread 275 ON thread.utid = critical_path_utid 276 JOIN process 277 USING (upid) 278 UNION ALL 279 -- Builds the self 'ancestor' slice stack 280 SELECT 281 anc.id, 282 slice.ts, 283 slice.dur, 284 critical_path_utid AS utid, 285 anc.depth + 5 AS stack_depth, 286 IIF($enable_self_slice, anc.name, NULL) AS name, 287 'slice' AS table_name, 288 critical_path_utid 289 FROM relevant_spans slice 290 JOIN ancestor_slice(self_slice_id) anc WHERE anc.dur != -1 291 UNION ALL 292 -- Builds the self 'deepest' ancestor slice stack 293 SELECT 294 self_slice_id AS id, 295 ts, 296 dur, 297 critical_path_utid AS utid, 298 self_slice_depth + 5 AS stack_depth, 299 IIF($enable_self_slice, self_slice_name, NULL) AS name, 300 'slice' AS table_name, 301 critical_path_utid 302 FROM relevant_spans slice 303 -- Ordering by stack depth is important to ensure the items can 304 -- be renedered in the UI as a debug track in the order in which 305 -- the sub-queries were 'unioned'. 306 ORDER BY stack_depth 307 ), 308 -- Prepares for stage 2 in building the entire stack. 309 -- Computes the starting depth for each stack. This is necessary because 310 -- each self slice stack has variable depth and the depth in each stack 311 -- most be contiguous in order to efficiently generate a pprof in the future. 312 critical_path_start_depth AS MATERIALIZED ( 313 SELECT critical_path_utid, ts, MAX(stack_depth) + 1 AS start_depth 314 FROM self_stack 315 GROUP BY critical_path_utid, ts 316 ), 317 critical_path_span AS MATERIALIZED ( 318 SELECT 319 thread_state_id, 320 state, 321 function, 322 io_wait, 323 slice_id, 324 slice_name, 325 slice_depth, 326 spans.ts, 327 spans.dur, 328 spans.critical_path_utid, 329 utid, 330 start_depth 331 FROM relevant_spans spans 332 JOIN critical_path_start_depth 333 ON 334 critical_path_start_depth.critical_path_utid = spans.critical_path_utid 335 AND critical_path_start_depth.ts = spans.ts 336 WHERE critical_path_start_depth.critical_path_utid = $critical_path_utid AND spans.critical_path_utid != spans.utid 337 ), 338 -- 2. Builds the 'critical_path' stack of items as an ordered UNION ALL 339 critical_path_stack AS MATERIALIZED ( 340 -- Builds the critical_path thread_state 341 SELECT 342 thread_state_id AS id, 343 ts, 344 dur, 345 utid, 346 start_depth AS stack_depth, 347 'blocking thread_state: ' || state AS name, 348 'thread_state' AS table_name, 349 critical_path_utid 350 FROM critical_path_span 351 UNION ALL 352 -- Builds the critical_path process_name 353 SELECT 354 thread_state_id AS id, 355 ts, 356 dur, 357 thread.utid, 358 start_depth + 1 AS stack_depth, 359 'blocking process_name: ' || process.name, 360 'thread_state' AS table_name, 361 critical_path_utid 362 FROM critical_path_span 363 JOIN thread USING (utid) 364 LEFT JOIN process USING (upid) 365 UNION ALL 366 -- Builds the critical_path thread_name 367 SELECT 368 thread_state_id AS id, 369 ts, 370 dur, 371 thread.utid, 372 start_depth + 2 AS stack_depth, 373 'blocking thread_name: ' || thread.name, 374 'thread_state' AS table_name, 375 critical_path_utid 376 FROM critical_path_span 377 JOIN thread USING (utid) 378 UNION ALL 379 -- Builds the critical_path kernel blocked_function 380 SELECT 381 thread_state_id AS id, 382 ts, 383 dur, 384 thread.utid, 385 start_depth + 3 AS stack_depth, 386 'blocking kernel_function: ' || function, 387 'thread_state' AS table_name, 388 critical_path_utid 389 FROM critical_path_span 390 JOIN thread USING (utid) 391 UNION ALL 392 -- Builds the critical_path kernel io_wait 393 SELECT 394 thread_state_id AS id, 395 ts, 396 dur, 397 thread.utid, 398 start_depth + 4 AS stack_depth, 399 'blocking io_wait: ' || io_wait, 400 'thread_state' AS table_name, 401 critical_path_utid 402 FROM critical_path_span 403 JOIN thread USING (utid) 404 UNION ALL 405 -- Builds the critical_path 'ancestor' slice stack 406 SELECT 407 anc.id, 408 slice.ts, 409 slice.dur, 410 slice.utid, 411 anc.depth + start_depth + 5 AS stack_depth, 412 IIF($enable_critical_path_slice, anc.name, NULL) AS name, 413 'slice' AS table_name, 414 critical_path_utid 415 FROM critical_path_span slice 416 JOIN ancestor_slice(slice_id) anc WHERE anc.dur != -1 417 UNION ALL 418 -- Builds the critical_path 'deepest' slice 419 SELECT 420 slice_id AS id, 421 ts, 422 dur, 423 utid, 424 slice_depth + start_depth + 5 AS stack_depth, 425 IIF($enable_critical_path_slice, slice_name, NULL) AS name, 426 'slice' AS table_name, 427 critical_path_utid 428 FROM critical_path_span slice 429 -- Ordering is also important as in the 'self' step above. 430 ORDER BY stack_depth 431 ), 432 -- Prepares for stage 3 in building the entire stack. 433 -- Computes the starting depth for each stack using the deepest stack_depth between 434 -- the critical_path stack and self stack. The self stack depth is 435 -- already computed and materialized in |critical_path_start_depth|. 436 cpu_start_depth_raw AS ( 437 SELECT critical_path_utid, ts, MAX(stack_depth) + 1 AS start_depth 438 FROM critical_path_stack 439 GROUP BY critical_path_utid, ts 440 UNION ALL 441 SELECT * FROM critical_path_start_depth 442 ), 443 cpu_start_depth AS ( 444 SELECT critical_path_utid, ts, MAX(start_depth) AS start_depth 445 FROM cpu_start_depth_raw 446 GROUP BY critical_path_utid, ts 447 ), 448 -- 3. Builds the 'CPU' stack for 'Running' states in either the self or critical path stack. 449 cpu_stack AS ( 450 SELECT 451 thread_state_id AS id, 452 spans.ts, 453 spans.dur, 454 utid, 455 start_depth AS stack_depth, 456 'cpu: ' || cpu AS name, 457 'thread_state' AS table_name, 458 spans.critical_path_utid 459 FROM relevant_spans spans 460 JOIN cpu_start_depth 461 ON 462 cpu_start_depth.critical_path_utid = spans.critical_path_utid 463 AND cpu_start_depth.ts = spans.ts 464 WHERE cpu_start_depth.critical_path_utid = $critical_path_utid AND state = 'Running' OR self_state = 'Running' 465 ), 466 merged AS ( 467 SELECT * FROM self_stack 468 UNION ALL 469 SELECT * FROM critical_path_stack 470 UNION ALL 471 SELECT * FROM cpu_stack 472 ) 473SELECT * FROM merged WHERE id IS NOT NULL; 474 475-- Critical path stack of thread_executing_spans with the following entities in the critical path 476-- stacked from top to bottom: self thread_state, self blocked_function, self process_name, 477-- self thread_name, slice stack, critical_path thread_state, critical_path process_name, 478-- critical_path thread_name, critical_path slice_stack, running_cpu. 479CREATE PERFETTO FUNCTION _thread_executing_span_critical_path_stack( 480 -- Thread utid to filter critical paths to. 481 critical_path_utid INT, 482 -- Timestamp of start of time range to filter critical paths to. 483 ts LONG, 484 -- Duration of time range to filter critical paths to. 485 dur LONG) 486RETURNS 487 TABLE( 488 -- Id of the thread_state or slice in the thread_executing_span. 489 id INT, 490 -- Timestamp of slice in the critical path. 491 ts LONG, 492 -- Duration of slice in the critical path. 493 dur LONG, 494 -- Utid of thread that emitted the slice. 495 utid INT, 496 -- Stack depth of the entitity in the debug track. 497 stack_depth INT, 498 -- Name of entity in the critical path (could be a thread_state, kernel blocked_function, process_name, thread_name, slice name or cpu). 499 name STRING, 500 -- Table name of entity in the critical path (could be either slice or thread_state). 501 table_name STRING, 502 -- Utid of the thread the critical path was filtered to. 503 critical_path_utid INT 504) AS 505SELECT * FROM _critical_path_stack($critical_path_utid, $ts, $dur, 1, 1, 1, 1); 506 507-- Returns a pprof aggregation of the stacks in |_critical_path_stack|. 508CREATE PERFETTO FUNCTION _critical_path_graph(graph_title STRING, critical_path_utid INT, ts LONG, dur LONG, enable_process_name INT, enable_thread_name INT, enable_self_slice INT, enable_critical_path_slice INT) 509RETURNS TABLE(pprof BYTES) 510AS 511WITH 512 stack AS MATERIALIZED ( 513 SELECT 514 ts, 515 dur - IFNULL(LEAD(dur) OVER (PARTITION BY critical_path_utid, ts ORDER BY stack_depth), 0) AS dur, 516 name, 517 utid, 518 critical_path_utid, 519 stack_depth 520 FROM 521 _critical_path_stack($critical_path_utid, $ts, $dur, $enable_process_name, $enable_thread_name, $enable_self_slice, $enable_critical_path_slice) 522 ), 523 graph AS ( 524 SELECT CAT_STACKS($graph_title) AS stack 525 ), 526 parent AS ( 527 SELECT 528 cr.ts, 529 cr.dur, 530 cr.name, 531 cr.utid, 532 cr.stack_depth, 533 CAT_STACKS(graph.stack, cr.name) AS stack, 534 cr.critical_path_utid 535 FROM stack cr, graph 536 WHERE stack_depth = 0 537 UNION ALL 538 SELECT 539 child.ts, 540 child.dur, 541 child.name, 542 child.utid, 543 child.stack_depth, 544 CAT_STACKS(stack, child.name) AS stack, 545 child.critical_path_utid 546 FROM stack child 547 JOIN parent 548 ON 549 parent.critical_path_utid = child.critical_path_utid 550 AND parent.ts = child.ts 551 AND child.stack_depth = parent.stack_depth + 1 552 ), 553 stacks AS ( 554 SELECT dur, stack FROM parent 555 ) 556SELECT EXPERIMENTAL_PROFILE(stack, 'duration', 'ns', dur) AS pprof FROM stacks; 557 558-- Returns a pprof aggreagation of the stacks in |_thread_executing_span_critical_path_stack| 559CREATE PERFETTO FUNCTION _thread_executing_span_critical_path_graph( 560 -- Descriptive name for the graph. 561 graph_title STRING, 562 -- Thread utid to filter critical paths to. 563 critical_path_utid INT, 564 -- Timestamp of start of time range to filter critical paths to. 565 ts INT, 566 -- Duration of time range to filter critical paths to. 567 dur INT) 568RETURNS TABLE( 569 -- Pprof of critical path stacks. 570 pprof BYTES 571) 572AS 573SELECT * FROM _critical_path_graph($graph_title, $critical_path_utid, $ts, $dur, 1, 1, 1, 1); 574