tools/perf/util/thread-stack.c

   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 "thread.h"
  19 #include "event.h"
  20 #include "machine.h"
  21 #include "util.h"
  22 #include "debug.h"
  23 #include "symbol.h"
  24 #include "comm.h"
  25 #include "call-path.h"
  26 #include "thread-stack.h"
  27
  28 #define STACK_GROWTH 2048
  29
  30 /**
  31  * struct thread_stack_entry - thread stack entry.
  32  * @ret_addr: return address
  33  * @timestamp: timestamp (if known)
  34  * @ref: external reference (e.g. db_id of sample)
  35  * @branch_count: the branch count when the entry was created
  36  * @cp: call path
  37  * @no_call: a 'call' was not seen
  38  */
  39 struct thread_stack_entry {
  40         u64 ret_addr;
  41         u64 timestamp;
  42         u64 ref;
  43         u64 branch_count;
  44         struct call_path *cp;
  45         bool no_call;
  46 };
  47
  48 /**
  49  * struct thread_stack - thread stack constructed from 'call' and 'return'
  50  *                       branch samples.
  51  * @stack: array that holds the stack
  52  * @cnt: number of entries in the stack
  53  * @sz: current maximum stack size
  54  * @trace_nr: current trace number
  55  * @branch_count: running branch count
  56  * @kernel_start: kernel start address
  57  * @last_time: last timestamp
  58  * @crp: call/return processor
  59  * @comm: current comm
  60  */
  61 struct thread_stack {
  62         struct thread_stack_entry *stack;
  63         size_t cnt;
  64         size_t sz;
  65         u64 trace_nr;
  66         u64 branch_count;
  67         u64 kernel_start;
  68         u64 last_time;
  69         struct call_return_processor *crp;
  70         struct comm *comm;
  71 };
  72
  73 static int thread_stack__grow(struct thread_stack *ts)
  74 {
  75         struct thread_stack_entry *new_stack;
  76         size_t sz, new_sz;
  77
  78         new_sz = ts->sz + STACK_GROWTH;
  79         sz = new_sz * sizeof(struct thread_stack_entry);
  80
  81         new_stack = realloc(ts->stack, sz);
  82         if (!new_stack)
  83                 return -ENOMEM;
  84
  85         ts->stack = new_stack;
  86         ts->sz = new_sz;
  87
  88         return 0;
  89 }
  90
  91 static struct thread_stack *thread_stack__new(struct thread *thread,
  92                                               struct call_return_processor *crp)
  93 {
  94         struct thread_stack *ts;
  95
  96         ts = zalloc(sizeof(struct thread_stack));
  97         if (!ts)
  98                 return NULL;
  99
 100         if (thread_stack__grow(ts)) {
 101                 free(ts);
 102                 return NULL;
 103         }
 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 ts;
 112 }
 113
 114 static int thread_stack__push(struct thread_stack *ts, u64 ret_addr)
 115 {
 116         int err = 0;
 117
 118         if (ts->cnt == ts->sz) {
 119                 err = thread_stack__grow(ts);
 120                 if (err) {
 121                         pr_warning("Out of memory: discarding thread stack\n");
 122                         ts->cnt = 0;
 123                 }
 124         }
 125
 126         ts->stack[ts->cnt++].ret_addr = ret_addr;
 127
 128         return err;
 129 }
 130
 131 static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr)
 132 {
 133         size_t i;
 134
 135         /*
 136          * In some cases there may be functions which are not seen to return.
 137          * For example when setjmp / longjmp has been used.  Or the perf context
 138          * switch in the kernel which doesn't stop and start tracing in exactly
 139          * the same code path.  When that happens the return address will be
 140          * further down the stack.  If the return address is not found at all,
 141          * we assume the opposite (i.e. this is a return for a call that wasn't
 142          * seen for some reason) and leave the stack alone.
 143          */
 144         for (i = ts->cnt; i; ) {
 145                 if (ts->stack[--i].ret_addr == ret_addr) {
 146                         ts->cnt = i;
 147                         return;
 148                 }
 149         }
 150 }
 151
 152 static bool thread_stack__in_kernel(struct thread_stack *ts)
 153 {
 154         if (!ts->cnt)
 155                 return false;
 156
 157         return ts->stack[ts->cnt - 1].cp->in_kernel;
 158 }
 159
 160 static int thread_stack__call_return(struct thread *thread,
 161                                      struct thread_stack *ts, size_t idx,
 162                                      u64 timestamp, u64 ref, bool no_return)
 163 {
 164         struct call_return_processor *crp = ts->crp;
 165         struct thread_stack_entry *tse;
 166         struct call_return cr = {
 167                 .thread = thread,
 168                 .comm = ts->comm,
 169                 .db_id = 0,
 170         };
 171
 172         tse = &ts->stack[idx];
 173         cr.cp = tse->cp;
 174         cr.call_time = tse->timestamp;
 175         cr.return_time = timestamp;
 176         cr.branch_count = ts->branch_count - tse->branch_count;
 177         cr.call_ref = tse->ref;
 178         cr.return_ref = ref;
 179         if (tse->no_call)
 180                 cr.flags |= CALL_RETURN_NO_CALL;
 181         if (no_return)
 182                 cr.flags |= CALL_RETURN_NO_RETURN;
 183
 184         return crp->process(&cr, crp->data);
 185 }
 186
 187 static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts)
 188 {
 189         struct call_return_processor *crp = ts->crp;
 190         int err;
 191
 192         if (!crp) {
 193                 ts->cnt = 0;
 194                 return 0;
 195         }
 196
 197         while (ts->cnt) {
 198                 err = thread_stack__call_return(thread, ts, --ts->cnt,
 199                                                 ts->last_time, 0, true);
 200                 if (err) {
 201                         pr_err("Error flushing thread stack!\n");
 202                         ts->cnt = 0;
 203                         return err;
 204                 }
 205         }
 206
 207         return 0;
 208 }
 209
 210 int thread_stack__flush(struct thread *thread)
 211 {
 212         if (thread->ts)
 213                 return __thread_stack__flush(thread, thread->ts);
 214
 215         return 0;
 216 }
 217
 218 int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip,
 219                         u64 to_ip, u16 insn_len, u64 trace_nr)
 220 {
 221         if (!thread)
 222                 return -EINVAL;
 223
 224         if (!thread->ts) {
 225                 thread->ts = thread_stack__new(thread, NULL);
 226                 if (!thread->ts) {
 227                         pr_warning("Out of memory: no thread stack\n");
 228                         return -ENOMEM;
 229                 }
 230                 thread->ts->trace_nr = trace_nr;
 231         }
 232
 233         /*
 234          * When the trace is discontinuous, the trace_nr changes.  In that case
 235          * the stack might be completely invalid.  Better to report nothing than
 236          * to report something misleading, so flush the stack.
 237          */
 238         if (trace_nr != thread->ts->trace_nr) {
 239                 if (thread->ts->trace_nr)
 240                         __thread_stack__flush(thread, thread->ts);
 241                 thread->ts->trace_nr = trace_nr;
 242         }
 243
 244         /* Stop here if thread_stack__process() is in use */
 245         if (thread->ts->crp)
 246                 return 0;
 247
 248         if (flags & PERF_IP_FLAG_CALL) {
 249                 u64 ret_addr;
 250
 251                 if (!to_ip)
 252                         return 0;
 253                 ret_addr = from_ip + insn_len;
 254                 if (ret_addr == to_ip)
 255                         return 0; /* Zero-length calls are excluded */
 256                 return thread_stack__push(thread->ts, ret_addr);
 257         } else if (flags & PERF_IP_FLAG_RETURN) {
 258                 if (!from_ip)
 259                         return 0;
 260                 thread_stack__pop(thread->ts, to_ip);
 261         }
 262
 263         return 0;
 264 }
 265
 266 void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr)
 267 {
 268         if (!thread || !thread->ts)
 269                 return;
 270
 271         if (trace_nr != thread->ts->trace_nr) {
 272                 if (thread->ts->trace_nr)
 273                         __thread_stack__flush(thread, thread->ts);
 274                 thread->ts->trace_nr = trace_nr;
 275         }
 276 }
 277
 278 void thread_stack__free(struct thread *thread)
 279 {
 280         if (thread->ts) {
 281                 __thread_stack__flush(thread, thread->ts);
 282                 zfree(&thread->ts->stack);
 283                 zfree(&thread->ts);
 284         }
 285 }
 286
 287 void thread_stack__sample(struct thread *thread, struct ip_callchain *chain,
 288                           size_t sz, u64 ip)
 289 {
 290         size_t i;
 291
 292         if (!thread || !thread->ts)
 293                 chain->nr = 1;
 294         else
 295                 chain->nr = min(sz, thread->ts->cnt + 1);
 296
 297         chain->ips[0] = ip;
 298
 299         for (i = 1; i < chain->nr; i++)
 300                 chain->ips[i] = thread->ts->stack[thread->ts->cnt - i].ret_addr;
 301 }
 302
 303 struct call_return_processor *
 304 call_return_processor__new(int (*process)(struct call_return *cr, void *data),
 305                            void *data)
 306 {
 307         struct call_return_processor *crp;
 308
 309         crp = zalloc(sizeof(struct call_return_processor));
 310         if (!crp)
 311                 return NULL;
 312         crp->cpr = call_path_root__new();
 313         if (!crp->cpr)
 314                 goto out_free;
 315         crp->process = process;
 316         crp->data = data;
 317         return crp;
 318
 319 out_free:
 320         free(crp);
 321         return NULL;
 322 }
 323
 324 void call_return_processor__free(struct call_return_processor *crp)
 325 {
 326         if (crp) {
 327                 call_path_root__free(crp->cpr);
 328                 free(crp);
 329         }
 330 }
 331
 332 static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr,
 333                                  u64 timestamp, u64 ref, struct call_path *cp,
 334                                  bool no_call)
 335 {
 336         struct thread_stack_entry *tse;
 337         int err;
 338
 339         if (ts->cnt == ts->sz) {
 340                 err = thread_stack__grow(ts);
 341                 if (err)
 342                         return err;
 343         }
 344
 345         tse = &ts->stack[ts->cnt++];
 346         tse->ret_addr = ret_addr;
 347         tse->timestamp = timestamp;
 348         tse->ref = ref;
 349         tse->branch_count = ts->branch_count;
 350         tse->cp = cp;
 351         tse->no_call = no_call;
 352
 353         return 0;
 354 }
 355
 356 static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts,
 357                                 u64 ret_addr, u64 timestamp, u64 ref,
 358                                 struct symbol *sym)
 359 {
 360         int err;
 361
 362         if (!ts->cnt)
 363                 return 1;
 364
 365         if (ts->cnt == 1) {
 366                 struct thread_stack_entry *tse = &ts->stack[0];
 367
 368                 if (tse->cp->sym == sym)
 369                         return thread_stack__call_return(thread, ts, --ts->cnt,
 370                                                          timestamp, ref, false);
 371         }
 372
 373         if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) {
 374                 return thread_stack__call_return(thread, ts, --ts->cnt,
 375                                                  timestamp, ref, false);
 376         } else {
 377                 size_t i = ts->cnt - 1;
 378
 379                 while (i--) {
 380                         if (ts->stack[i].ret_addr != ret_addr)
 381                                 continue;
 382                         i += 1;
 383                         while (ts->cnt > i) {
 384                                 err = thread_stack__call_return(thread, ts,
 385                                                                 --ts->cnt,
 386                                                                 timestamp, ref,
 387                                                                 true);
 388                                 if (err)
 389                                         return err;
 390                         }
 391                         return thread_stack__call_return(thread, ts, --ts->cnt,
 392                                                          timestamp, ref, false);
 393                 }
 394         }
 395
 396         return 1;
 397 }
 398
 399 static int thread_stack__bottom(struct thread *thread, struct thread_stack *ts,
 400                                 struct perf_sample *sample,
 401                                 struct addr_location *from_al,
 402                                 struct addr_location *to_al, u64 ref)
 403 {
 404         struct call_path_root *cpr = ts->crp->cpr;
 405         struct call_path *cp;
 406         struct symbol *sym;
 407         u64 ip;
 408
 409         if (sample->ip) {
 410                 ip = sample->ip;
 411                 sym = from_al->sym;
 412         } else if (sample->addr) {
 413                 ip = sample->addr;
 414                 sym = to_al->sym;
 415         } else {
 416                 return 0;
 417         }
 418
 419         cp = call_path__findnew(cpr, &cpr->call_path, sym, ip,
 420                                 ts->kernel_start);
 421         if (!cp)
 422                 return -ENOMEM;
 423
 424         return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp,
 425                                      true);
 426 }
 427
 428 static int thread_stack__no_call_return(struct thread *thread,
 429                                         struct thread_stack *ts,
 430                                         struct perf_sample *sample,
 431                                         struct addr_location *from_al,
 432                                         struct addr_location *to_al, u64 ref)
 433 {
 434         struct call_path_root *cpr = ts->crp->cpr;
 435         struct call_path *cp, *parent;
 436         u64 ks = ts->kernel_start;
 437         int err;
 438
 439         if (sample->ip >= ks && sample->addr < ks) {
 440                 /* Return to userspace, so pop all kernel addresses */
 441                 while (thread_stack__in_kernel(ts)) {
 442                         err = thread_stack__call_return(thread, ts, --ts->cnt,
 443                                                         sample->time, ref,
 444                                                         true);
 445                         if (err)
 446                                 return err;
 447                 }
 448
 449                 /* If the stack is empty, push the userspace address */
 450                 if (!ts->cnt) {
 451                         cp = call_path__findnew(cpr, &cpr->call_path,
 452                                                 to_al->sym, sample->addr,
 453                                                 ts->kernel_start);
 454                         if (!cp)
 455                                 return -ENOMEM;
 456                         return thread_stack__push_cp(ts, 0, sample->time, ref,
 457                                                      cp, true);
 458                 }
 459         } else if (thread_stack__in_kernel(ts) && sample->ip < ks) {
 460                 /* Return to userspace, so pop all kernel addresses */
 461                 while (thread_stack__in_kernel(ts)) {
 462                         err = thread_stack__call_return(thread, ts, --ts->cnt,
 463                                                         sample->time, ref,
 464                                                         true);
 465                         if (err)
 466                                 return err;
 467                 }
 468         }
 469
 470         if (ts->cnt)
 471                 parent = ts->stack[ts->cnt - 1].cp;
 472         else
 473                 parent = &cpr->call_path;
 474
 475         /* This 'return' had no 'call', so push and pop top of stack */
 476         cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip,
 477                                 ts->kernel_start);
 478         if (!cp)
 479                 return -ENOMEM;
 480
 481         err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp,
 482                                     true);
 483         if (err)
 484                 return err;
 485
 486         return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref,
 487                                     to_al->sym);
 488 }
 489
 490 static int thread_stack__trace_begin(struct thread *thread,
 491                                      struct thread_stack *ts, u64 timestamp,
 492                                      u64 ref)
 493 {
 494         struct thread_stack_entry *tse;
 495         int err;
 496
 497         if (!ts->cnt)
 498                 return 0;
 499
 500         /* Pop trace end */
 501         tse = &ts->stack[ts->cnt - 1];
 502         if (tse->cp->sym == NULL && tse->cp->ip == 0) {
 503                 err = thread_stack__call_return(thread, ts, --ts->cnt,
 504                                                 timestamp, ref, false);
 505                 if (err)
 506                         return err;
 507         }
 508
 509         return 0;
 510 }
 511
 512 static int thread_stack__trace_end(struct thread_stack *ts,
 513                                    struct perf_sample *sample, u64 ref)
 514 {
 515         struct call_path_root *cpr = ts->crp->cpr;
 516         struct call_path *cp;
 517         u64 ret_addr;
 518
 519         /* No point having 'trace end' on the bottom of the stack */
 520         if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref))
 521                 return 0;
 522
 523         cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0,
 524                                 ts->kernel_start);
 525         if (!cp)
 526                 return -ENOMEM;
 527
 528         ret_addr = sample->ip + sample->insn_len;
 529
 530         return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp,
 531                                      false);
 532 }
 533
 534 int thread_stack__process(struct thread *thread, struct comm *comm,
 535                           struct perf_sample *sample,
 536                           struct addr_location *from_al,
 537                           struct addr_location *to_al, u64 ref,
 538                           struct call_return_processor *crp)
 539 {
 540         struct thread_stack *ts = thread->ts;
 541         int err = 0;
 542
 543         if (ts) {
 544                 if (!ts->crp) {
 545                         /* Supersede thread_stack__event() */
 546                         thread_stack__free(thread);
 547                         thread->ts = thread_stack__new(thread, crp);
 548                         if (!thread->ts)
 549                                 return -ENOMEM;
 550                         ts = thread->ts;
 551                         ts->comm = comm;
 552                 }
 553         } else {
 554                 thread->ts = thread_stack__new(thread, crp);
 555                 if (!thread->ts)
 556                         return -ENOMEM;
 557                 ts = thread->ts;
 558                 ts->comm = comm;
 559         }
 560
 561         /* Flush stack on exec */
 562         if (ts->comm != comm && thread->pid_ == thread->tid) {
 563                 err = __thread_stack__flush(thread, ts);
 564                 if (err)
 565                         return err;
 566                 ts->comm = comm;
 567         }
 568
 569         /* If the stack is empty, put the current symbol on the stack */
 570         if (!ts->cnt) {
 571                 err = thread_stack__bottom(thread, ts, sample, from_al, to_al,
 572                                            ref);
 573                 if (err)
 574                         return err;
 575         }
 576
 577         ts->branch_count += 1;
 578         ts->last_time = sample->time;
 579
 580         if (sample->flags & PERF_IP_FLAG_CALL) {
 581                 struct call_path_root *cpr = ts->crp->cpr;
 582                 struct call_path *cp;
 583                 u64 ret_addr;
 584
 585                 if (!sample->ip || !sample->addr)
 586                         return 0;
 587
 588                 ret_addr = sample->ip + sample->insn_len;
 589                 if (ret_addr == sample->addr)
 590                         return 0; /* Zero-length calls are excluded */
 591
 592                 cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
 593                                         to_al->sym, sample->addr,
 594                                         ts->kernel_start);
 595                 if (!cp)
 596                         return -ENOMEM;
 597                 err = thread_stack__push_cp(ts, ret_addr, sample->time, ref,
 598                                             cp, false);
 599         } else if (sample->flags & PERF_IP_FLAG_RETURN) {
 600                 if (!sample->ip || !sample->addr)
 601                         return 0;
 602
 603                 err = thread_stack__pop_cp(thread, ts, sample->addr,
 604                                            sample->time, ref, from_al->sym);
 605                 if (err) {
 606                         if (err < 0)
 607                                 return err;
 608                         err = thread_stack__no_call_return(thread, ts, sample,
 609                                                            from_al, to_al, ref);
 610                 }
 611         } else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) {
 612                 err = thread_stack__trace_begin(thread, ts, sample->time, ref);
 613         } else if (sample->flags & PERF_IP_FLAG_TRACE_END) {
 614                 err = thread_stack__trace_end(ts, sample, ref);
 615         }
 616
 617         return err;
 618 }
 619
 620 size_t thread_stack__depth(struct thread *thread)
 621 {
 622         if (!thread->ts)
 623                 return 0;
 624         return thread->ts->cnt;
 625 }