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