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