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