1 /* 2 * thread-stack.c: Synthesize a thread's stack using call / return events 3 * Copyright (c) 2014, Intel Corporation. 4 * 5 * This program is free software; you can redistribute it and/or modify it 6 * under the terms and conditions of the GNU General Public License, 7 * version 2, as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 12 * more details. 13 * 14 */ 15 16 #include <linux/rbtree.h> 17 #include <linux/list.h> 18 #include <errno.h> 19 #include "thread.h" 20 #include "event.h" 21 #include "machine.h" 22 #include "util.h" 23 #include "debug.h" 24 #include "symbol.h" 25 #include "comm.h" 26 #include "call-path.h" 27 #include "thread-stack.h" 28 29 #define STACK_GROWTH 2048 30 31 /** 32 * struct thread_stack_entry - thread stack entry. 33 * @ret_addr: return address 34 * @timestamp: timestamp (if known) 35 * @ref: external reference (e.g. db_id of sample) 36 * @branch_count: the branch count when the entry was created 37 * @cp: call path 38 * @no_call: a 'call' was not seen 39 * @trace_end: a 'call' but trace ended 40 */ 41 struct thread_stack_entry { 42 u64 ret_addr; 43 u64 timestamp; 44 u64 ref; 45 u64 branch_count; 46 struct call_path *cp; 47 bool no_call; 48 bool trace_end; 49 }; 50 51 /** 52 * struct thread_stack - thread stack constructed from 'call' and 'return' 53 * branch samples. 54 * @stack: array that holds the stack 55 * @cnt: number of entries in the stack 56 * @sz: current maximum stack size 57 * @trace_nr: current trace number 58 * @branch_count: running branch count 59 * @kernel_start: kernel start address 60 * @last_time: last timestamp 61 * @crp: call/return processor 62 * @comm: current comm 63 * @arr_sz: size of array if this is the first element of an array 64 */ 65 struct thread_stack { 66 struct thread_stack_entry *stack; 67 size_t cnt; 68 size_t sz; 69 u64 trace_nr; 70 u64 branch_count; 71 u64 kernel_start; 72 u64 last_time; 73 struct call_return_processor *crp; 74 struct comm *comm; 75 unsigned int arr_sz; 76 }; 77 78 static int thread_stack__grow(struct thread_stack *ts) 79 { 80 struct thread_stack_entry *new_stack; 81 size_t sz, new_sz; 82 83 new_sz = ts->sz + STACK_GROWTH; 84 sz = new_sz * sizeof(struct thread_stack_entry); 85 86 new_stack = realloc(ts->stack, sz); 87 if (!new_stack) 88 return -ENOMEM; 89 90 ts->stack = new_stack; 91 ts->sz = new_sz; 92 93 return 0; 94 } 95 96 static int thread_stack__init(struct thread_stack *ts, struct thread *thread, 97 struct call_return_processor *crp) 98 { 99 int err; 100 101 err = thread_stack__grow(ts); 102 if (err) 103 return err; 104 105 if (thread->mg && thread->mg->machine) 106 ts->kernel_start = machine__kernel_start(thread->mg->machine); 107 else 108 ts->kernel_start = 1ULL << 63; 109 ts->crp = crp; 110 111 return 0; 112 } 113 114 static struct thread_stack *thread_stack__new(struct thread *thread, 115 struct call_return_processor *crp) 116 { 117 struct thread_stack *ts = thread->ts, *new_ts; 118 unsigned int old_sz = ts ? ts->arr_sz : 0; 119 unsigned int new_sz = 1; 120 121 if (!ts || new_sz > old_sz) { 122 new_ts = calloc(new_sz, sizeof(*ts)); 123 if (!new_ts) 124 return NULL; 125 if (ts) 126 memcpy(new_ts, ts, old_sz * sizeof(*ts)); 127 new_ts->arr_sz = new_sz; 128 zfree(&thread->ts); 129 thread->ts = new_ts; 130 ts = new_ts; 131 } 132 133 if (!ts->stack && 134 thread_stack__init(ts, thread, crp)) 135 return NULL; 136 137 return ts; 138 } 139 140 static inline struct thread_stack *thread__stack(struct thread *thread) 141 { 142 return thread ? thread->ts : NULL; 143 } 144 145 static int thread_stack__push(struct thread_stack *ts, u64 ret_addr, 146 bool trace_end) 147 { 148 int err = 0; 149 150 if (ts->cnt == ts->sz) { 151 err = thread_stack__grow(ts); 152 if (err) { 153 pr_warning("Out of memory: discarding thread stack\n"); 154 ts->cnt = 0; 155 } 156 } 157 158 ts->stack[ts->cnt].trace_end = trace_end; 159 ts->stack[ts->cnt++].ret_addr = ret_addr; 160 161 return err; 162 } 163 164 static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr) 165 { 166 size_t i; 167 168 /* 169 * In some cases there may be functions which are not seen to return. 170 * For example when setjmp / longjmp has been used. Or the perf context 171 * switch in the kernel which doesn't stop and start tracing in exactly 172 * the same code path. When that happens the return address will be 173 * further down the stack. If the return address is not found at all, 174 * we assume the opposite (i.e. this is a return for a call that wasn't 175 * seen for some reason) and leave the stack alone. 176 */ 177 for (i = ts->cnt; i; ) { 178 if (ts->stack[--i].ret_addr == ret_addr) { 179 ts->cnt = i; 180 return; 181 } 182 } 183 } 184 185 static void thread_stack__pop_trace_end(struct thread_stack *ts) 186 { 187 size_t i; 188 189 for (i = ts->cnt; i; ) { 190 if (ts->stack[--i].trace_end) 191 ts->cnt = i; 192 else 193 return; 194 } 195 } 196 197 static bool thread_stack__in_kernel(struct thread_stack *ts) 198 { 199 if (!ts->cnt) 200 return false; 201 202 return ts->stack[ts->cnt - 1].cp->in_kernel; 203 } 204 205 static int thread_stack__call_return(struct thread *thread, 206 struct thread_stack *ts, size_t idx, 207 u64 timestamp, u64 ref, bool no_return) 208 { 209 struct call_return_processor *crp = ts->crp; 210 struct thread_stack_entry *tse; 211 struct call_return cr = { 212 .thread = thread, 213 .comm = ts->comm, 214 .db_id = 0, 215 }; 216 217 tse = &ts->stack[idx]; 218 cr.cp = tse->cp; 219 cr.call_time = tse->timestamp; 220 cr.return_time = timestamp; 221 cr.branch_count = ts->branch_count - tse->branch_count; 222 cr.call_ref = tse->ref; 223 cr.return_ref = ref; 224 if (tse->no_call) 225 cr.flags |= CALL_RETURN_NO_CALL; 226 if (no_return) 227 cr.flags |= CALL_RETURN_NO_RETURN; 228 229 return crp->process(&cr, crp->data); 230 } 231 232 static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts) 233 { 234 struct call_return_processor *crp = ts->crp; 235 int err; 236 237 if (!crp) { 238 ts->cnt = 0; 239 return 0; 240 } 241 242 while (ts->cnt) { 243 err = thread_stack__call_return(thread, ts, --ts->cnt, 244 ts->last_time, 0, true); 245 if (err) { 246 pr_err("Error flushing thread stack!\n"); 247 ts->cnt = 0; 248 return err; 249 } 250 } 251 252 return 0; 253 } 254 255 int thread_stack__flush(struct thread *thread) 256 { 257 struct thread_stack *ts = thread->ts; 258 unsigned int pos; 259 int err = 0; 260 261 if (ts) { 262 for (pos = 0; pos < ts->arr_sz; pos++) { 263 int ret = __thread_stack__flush(thread, ts + pos); 264 265 if (ret) 266 err = ret; 267 } 268 } 269 270 return err; 271 } 272 273 int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip, 274 u64 to_ip, u16 insn_len, u64 trace_nr) 275 { 276 struct thread_stack *ts = thread__stack(thread); 277 278 if (!thread) 279 return -EINVAL; 280 281 if (!ts) { 282 ts = thread_stack__new(thread, NULL); 283 if (!ts) { 284 pr_warning("Out of memory: no thread stack\n"); 285 return -ENOMEM; 286 } 287 ts->trace_nr = trace_nr; 288 } 289 290 /* 291 * When the trace is discontinuous, the trace_nr changes. In that case 292 * the stack might be completely invalid. Better to report nothing than 293 * to report something misleading, so flush the stack. 294 */ 295 if (trace_nr != ts->trace_nr) { 296 if (ts->trace_nr) 297 __thread_stack__flush(thread, ts); 298 ts->trace_nr = trace_nr; 299 } 300 301 /* Stop here if thread_stack__process() is in use */ 302 if (ts->crp) 303 return 0; 304 305 if (flags & PERF_IP_FLAG_CALL) { 306 u64 ret_addr; 307 308 if (!to_ip) 309 return 0; 310 ret_addr = from_ip + insn_len; 311 if (ret_addr == to_ip) 312 return 0; /* Zero-length calls are excluded */ 313 return thread_stack__push(ts, ret_addr, 314 flags & PERF_IP_FLAG_TRACE_END); 315 } else if (flags & PERF_IP_FLAG_TRACE_BEGIN) { 316 /* 317 * If the caller did not change the trace number (which would 318 * have flushed the stack) then try to make sense of the stack. 319 * Possibly, tracing began after returning to the current 320 * address, so try to pop that. Also, do not expect a call made 321 * when the trace ended, to return, so pop that. 322 */ 323 thread_stack__pop(ts, to_ip); 324 thread_stack__pop_trace_end(ts); 325 } else if ((flags & PERF_IP_FLAG_RETURN) && from_ip) { 326 thread_stack__pop(ts, to_ip); 327 } 328 329 return 0; 330 } 331 332 void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr) 333 { 334 struct thread_stack *ts = thread__stack(thread); 335 336 if (!ts) 337 return; 338 339 if (trace_nr != ts->trace_nr) { 340 if (ts->trace_nr) 341 __thread_stack__flush(thread, ts); 342 ts->trace_nr = trace_nr; 343 } 344 } 345 346 static void __thread_stack__free(struct thread *thread, struct thread_stack *ts) 347 { 348 __thread_stack__flush(thread, ts); 349 zfree(&ts->stack); 350 } 351 352 static void thread_stack__reset(struct thread *thread, struct thread_stack *ts) 353 { 354 unsigned int arr_sz = ts->arr_sz; 355 356 __thread_stack__free(thread, ts); 357 memset(ts, 0, sizeof(*ts)); 358 ts->arr_sz = arr_sz; 359 } 360 361 void thread_stack__free(struct thread *thread) 362 { 363 struct thread_stack *ts = thread->ts; 364 unsigned int pos; 365 366 if (ts) { 367 for (pos = 0; pos < ts->arr_sz; pos++) 368 __thread_stack__free(thread, ts + pos); 369 zfree(&thread->ts); 370 } 371 } 372 373 static inline u64 callchain_context(u64 ip, u64 kernel_start) 374 { 375 return ip < kernel_start ? PERF_CONTEXT_USER : PERF_CONTEXT_KERNEL; 376 } 377 378 void thread_stack__sample(struct thread *thread, struct ip_callchain *chain, 379 size_t sz, u64 ip, u64 kernel_start) 380 { 381 struct thread_stack *ts = thread__stack(thread); 382 u64 context = callchain_context(ip, kernel_start); 383 u64 last_context; 384 size_t i, j; 385 386 if (sz < 2) { 387 chain->nr = 0; 388 return; 389 } 390 391 chain->ips[0] = context; 392 chain->ips[1] = ip; 393 394 if (!ts) { 395 chain->nr = 2; 396 return; 397 } 398 399 last_context = context; 400 401 for (i = 2, j = 1; i < sz && j <= ts->cnt; i++, j++) { 402 ip = ts->stack[ts->cnt - j].ret_addr; 403 context = callchain_context(ip, kernel_start); 404 if (context != last_context) { 405 if (i >= sz - 1) 406 break; 407 chain->ips[i++] = context; 408 last_context = context; 409 } 410 chain->ips[i] = ip; 411 } 412 413 chain->nr = i; 414 } 415 416 struct call_return_processor * 417 call_return_processor__new(int (*process)(struct call_return *cr, void *data), 418 void *data) 419 { 420 struct call_return_processor *crp; 421 422 crp = zalloc(sizeof(struct call_return_processor)); 423 if (!crp) 424 return NULL; 425 crp->cpr = call_path_root__new(); 426 if (!crp->cpr) 427 goto out_free; 428 crp->process = process; 429 crp->data = data; 430 return crp; 431 432 out_free: 433 free(crp); 434 return NULL; 435 } 436 437 void call_return_processor__free(struct call_return_processor *crp) 438 { 439 if (crp) { 440 call_path_root__free(crp->cpr); 441 free(crp); 442 } 443 } 444 445 static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr, 446 u64 timestamp, u64 ref, struct call_path *cp, 447 bool no_call, bool trace_end) 448 { 449 struct thread_stack_entry *tse; 450 int err; 451 452 if (ts->cnt == ts->sz) { 453 err = thread_stack__grow(ts); 454 if (err) 455 return err; 456 } 457 458 tse = &ts->stack[ts->cnt++]; 459 tse->ret_addr = ret_addr; 460 tse->timestamp = timestamp; 461 tse->ref = ref; 462 tse->branch_count = ts->branch_count; 463 tse->cp = cp; 464 tse->no_call = no_call; 465 tse->trace_end = trace_end; 466 467 return 0; 468 } 469 470 static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts, 471 u64 ret_addr, u64 timestamp, u64 ref, 472 struct symbol *sym) 473 { 474 int err; 475 476 if (!ts->cnt) 477 return 1; 478 479 if (ts->cnt == 1) { 480 struct thread_stack_entry *tse = &ts->stack[0]; 481 482 if (tse->cp->sym == sym) 483 return thread_stack__call_return(thread, ts, --ts->cnt, 484 timestamp, ref, false); 485 } 486 487 if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) { 488 return thread_stack__call_return(thread, ts, --ts->cnt, 489 timestamp, ref, false); 490 } else { 491 size_t i = ts->cnt - 1; 492 493 while (i--) { 494 if (ts->stack[i].ret_addr != ret_addr) 495 continue; 496 i += 1; 497 while (ts->cnt > i) { 498 err = thread_stack__call_return(thread, ts, 499 --ts->cnt, 500 timestamp, ref, 501 true); 502 if (err) 503 return err; 504 } 505 return thread_stack__call_return(thread, ts, --ts->cnt, 506 timestamp, ref, false); 507 } 508 } 509 510 return 1; 511 } 512 513 static int thread_stack__bottom(struct thread_stack *ts, 514 struct perf_sample *sample, 515 struct addr_location *from_al, 516 struct addr_location *to_al, u64 ref) 517 { 518 struct call_path_root *cpr = ts->crp->cpr; 519 struct call_path *cp; 520 struct symbol *sym; 521 u64 ip; 522 523 if (sample->ip) { 524 ip = sample->ip; 525 sym = from_al->sym; 526 } else if (sample->addr) { 527 ip = sample->addr; 528 sym = to_al->sym; 529 } else { 530 return 0; 531 } 532 533 cp = call_path__findnew(cpr, &cpr->call_path, sym, ip, 534 ts->kernel_start); 535 if (!cp) 536 return -ENOMEM; 537 538 return thread_stack__push_cp(ts, ip, sample->time, ref, cp, 539 true, false); 540 } 541 542 static int thread_stack__no_call_return(struct thread *thread, 543 struct thread_stack *ts, 544 struct perf_sample *sample, 545 struct addr_location *from_al, 546 struct addr_location *to_al, u64 ref) 547 { 548 struct call_path_root *cpr = ts->crp->cpr; 549 struct call_path *cp, *parent; 550 u64 ks = ts->kernel_start; 551 int err; 552 553 if (sample->ip >= ks && sample->addr < ks) { 554 /* Return to userspace, so pop all kernel addresses */ 555 while (thread_stack__in_kernel(ts)) { 556 err = thread_stack__call_return(thread, ts, --ts->cnt, 557 sample->time, ref, 558 true); 559 if (err) 560 return err; 561 } 562 563 /* If the stack is empty, push the userspace address */ 564 if (!ts->cnt) { 565 cp = call_path__findnew(cpr, &cpr->call_path, 566 to_al->sym, sample->addr, 567 ts->kernel_start); 568 if (!cp) 569 return -ENOMEM; 570 return thread_stack__push_cp(ts, 0, sample->time, ref, 571 cp, true, false); 572 } 573 } else if (thread_stack__in_kernel(ts) && sample->ip < ks) { 574 /* Return to userspace, so pop all kernel addresses */ 575 while (thread_stack__in_kernel(ts)) { 576 err = thread_stack__call_return(thread, ts, --ts->cnt, 577 sample->time, ref, 578 true); 579 if (err) 580 return err; 581 } 582 } 583 584 if (ts->cnt) 585 parent = ts->stack[ts->cnt - 1].cp; 586 else 587 parent = &cpr->call_path; 588 589 /* This 'return' had no 'call', so push and pop top of stack */ 590 cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip, 591 ts->kernel_start); 592 if (!cp) 593 return -ENOMEM; 594 595 err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp, 596 true, false); 597 if (err) 598 return err; 599 600 return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref, 601 to_al->sym); 602 } 603 604 static int thread_stack__trace_begin(struct thread *thread, 605 struct thread_stack *ts, u64 timestamp, 606 u64 ref) 607 { 608 struct thread_stack_entry *tse; 609 int err; 610 611 if (!ts->cnt) 612 return 0; 613 614 /* Pop trace end */ 615 tse = &ts->stack[ts->cnt - 1]; 616 if (tse->trace_end) { 617 err = thread_stack__call_return(thread, ts, --ts->cnt, 618 timestamp, ref, false); 619 if (err) 620 return err; 621 } 622 623 return 0; 624 } 625 626 static int thread_stack__trace_end(struct thread_stack *ts, 627 struct perf_sample *sample, u64 ref) 628 { 629 struct call_path_root *cpr = ts->crp->cpr; 630 struct call_path *cp; 631 u64 ret_addr; 632 633 /* No point having 'trace end' on the bottom of the stack */ 634 if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref)) 635 return 0; 636 637 cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0, 638 ts->kernel_start); 639 if (!cp) 640 return -ENOMEM; 641 642 ret_addr = sample->ip + sample->insn_len; 643 644 return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp, 645 false, true); 646 } 647 648 int thread_stack__process(struct thread *thread, struct comm *comm, 649 struct perf_sample *sample, 650 struct addr_location *from_al, 651 struct addr_location *to_al, u64 ref, 652 struct call_return_processor *crp) 653 { 654 struct thread_stack *ts = thread__stack(thread); 655 int err = 0; 656 657 if (ts && !ts->crp) { 658 /* Supersede thread_stack__event() */ 659 thread_stack__reset(thread, ts); 660 ts = NULL; 661 } 662 663 if (!ts) { 664 ts = thread_stack__new(thread, crp); 665 if (!ts) 666 return -ENOMEM; 667 ts->comm = comm; 668 } 669 670 /* Flush stack on exec */ 671 if (ts->comm != comm && thread->pid_ == thread->tid) { 672 err = __thread_stack__flush(thread, ts); 673 if (err) 674 return err; 675 ts->comm = comm; 676 } 677 678 /* If the stack is empty, put the current symbol on the stack */ 679 if (!ts->cnt) { 680 err = thread_stack__bottom(ts, sample, from_al, to_al, ref); 681 if (err) 682 return err; 683 } 684 685 ts->branch_count += 1; 686 ts->last_time = sample->time; 687 688 if (sample->flags & PERF_IP_FLAG_CALL) { 689 bool trace_end = sample->flags & PERF_IP_FLAG_TRACE_END; 690 struct call_path_root *cpr = ts->crp->cpr; 691 struct call_path *cp; 692 u64 ret_addr; 693 694 if (!sample->ip || !sample->addr) 695 return 0; 696 697 ret_addr = sample->ip + sample->insn_len; 698 if (ret_addr == sample->addr) 699 return 0; /* Zero-length calls are excluded */ 700 701 cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, 702 to_al->sym, sample->addr, 703 ts->kernel_start); 704 if (!cp) 705 return -ENOMEM; 706 err = thread_stack__push_cp(ts, ret_addr, sample->time, ref, 707 cp, false, trace_end); 708 } else if (sample->flags & PERF_IP_FLAG_RETURN) { 709 if (!sample->ip || !sample->addr) 710 return 0; 711 712 err = thread_stack__pop_cp(thread, ts, sample->addr, 713 sample->time, ref, from_al->sym); 714 if (err) { 715 if (err < 0) 716 return err; 717 err = thread_stack__no_call_return(thread, ts, sample, 718 from_al, to_al, ref); 719 } 720 } else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) { 721 err = thread_stack__trace_begin(thread, ts, sample->time, ref); 722 } else if (sample->flags & PERF_IP_FLAG_TRACE_END) { 723 err = thread_stack__trace_end(ts, sample, ref); 724 } 725 726 return err; 727 } 728 729 size_t thread_stack__depth(struct thread *thread) 730 { 731 struct thread_stack *ts = thread__stack(thread); 732 733 if (!ts) 734 return 0; 735 return ts->cnt; 736 } 737