tools/perf/util/hist.c

   1 #include "util.h"
   2 #include "build-id.h"
   3 #include "hist.h"
   4 #include "session.h"
   5 #include "sort.h"
   6 #include <math.h>
   7
   8 struct callchain_param  callchain_param = {
   9         .mode   = CHAIN_GRAPH_REL,
  10         .min_percent = 0.5
  11 };
  12
  13 static void hist_entry__add_cpumode_period(struct hist_entry *self,
  14                                            unsigned int cpumode, u64 period)
  15 {
  16         switch (cpumode) {
  17         case PERF_RECORD_MISC_KERNEL:
  18                 self->period_sys += period;
  19                 break;
  20         case PERF_RECORD_MISC_USER:
  21                 self->period_us += period;
  22                 break;
  23         case PERF_RECORD_MISC_GUEST_KERNEL:
  24                 self->period_guest_sys += period;
  25                 break;
  26         case PERF_RECORD_MISC_GUEST_USER:
  27                 self->period_guest_us += period;
  28                 break;
  29         default:
  30                 break;
  31         }
  32 }
  33
  34 /*
  35  * histogram, sorted on item, collects periods
  36  */
  37
  38 static struct hist_entry *hist_entry__new(struct hist_entry *template)
  39 {
  40         size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_node) : 0;
  41         struct hist_entry *self = malloc(sizeof(*self) + callchain_size);
  42
  43         if (self != NULL) {
  44                 *self = *template;
  45                 self->nr_events = 1;
  46                 if (symbol_conf.use_callchain)
  47                         callchain_init(self->callchain);
  48         }
  49
  50         return self;
  51 }
  52
  53 static void hists__inc_nr_entries(struct hists *self, struct hist_entry *entry)
  54 {
  55         if (entry->ms.sym && self->max_sym_namelen < entry->ms.sym->namelen)
  56                 self->max_sym_namelen = entry->ms.sym->namelen;
  57         ++self->nr_entries;
  58 }
  59
  60 struct hist_entry *__hists__add_entry(struct hists *self,
  61                                       struct addr_location *al,
  62                                       struct symbol *sym_parent, u64 period)
  63 {
  64         struct rb_node **p = &self->entries.rb_node;
  65         struct rb_node *parent = NULL;
  66         struct hist_entry *he;
  67         struct hist_entry entry = {
  68                 .thread = al->thread,
  69                 .ms = {
  70                         .map    = al->map,
  71                         .sym    = al->sym,
  72                 },
  73                 .cpu    = al->cpu,
  74                 .ip     = al->addr,
  75                 .level  = al->level,
  76                 .period = period,
  77                 .parent = sym_parent,
  78         };
  79         int cmp;
  80
  81         while (*p != NULL) {
  82                 parent = *p;
  83                 he = rb_entry(parent, struct hist_entry, rb_node);
  84
  85                 cmp = hist_entry__cmp(&entry, he);
  86
  87                 if (!cmp) {
  88                         he->period += period;
  89                         ++he->nr_events;
  90                         goto out;
  91                 }
  92
  93                 if (cmp < 0)
  94                         p = &(*p)->rb_left;
  95                 else
  96                         p = &(*p)->rb_right;
  97         }
  98
  99         he = hist_entry__new(&entry);
 100         if (!he)
 101                 return NULL;
 102         rb_link_node(&he->rb_node, parent, p);
 103         rb_insert_color(&he->rb_node, &self->entries);
 104         hists__inc_nr_entries(self, he);
 105 out:
 106         hist_entry__add_cpumode_period(he, al->cpumode, period);
 107         return he;
 108 }
 109
 110 int64_t
 111 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
 112 {
 113         struct sort_entry *se;
 114         int64_t cmp = 0;
 115
 116         list_for_each_entry(se, &hist_entry__sort_list, list) {
 117                 cmp = se->se_cmp(left, right);
 118                 if (cmp)
 119                         break;
 120         }
 121
 122         return cmp;
 123 }
 124
 125 int64_t
 126 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
 127 {
 128         struct sort_entry *se;
 129         int64_t cmp = 0;
 130
 131         list_for_each_entry(se, &hist_entry__sort_list, list) {
 132                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
 133
 134                 f = se->se_collapse ?: se->se_cmp;
 135
 136                 cmp = f(left, right);
 137                 if (cmp)
 138                         break;
 139         }
 140
 141         return cmp;
 142 }
 143
 144 void hist_entry__free(struct hist_entry *he)
 145 {
 146         free(he);
 147 }
 148
 149 /*
 150  * collapse the histogram
 151  */
 152
 153 static bool collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
 154 {
 155         struct rb_node **p = &root->rb_node;
 156         struct rb_node *parent = NULL;
 157         struct hist_entry *iter;
 158         int64_t cmp;
 159
 160         while (*p != NULL) {
 161                 parent = *p;
 162                 iter = rb_entry(parent, struct hist_entry, rb_node);
 163
 164                 cmp = hist_entry__collapse(iter, he);
 165
 166                 if (!cmp) {
 167                         iter->period += he->period;
 168                         hist_entry__free(he);
 169                         return false;
 170                 }
 171
 172                 if (cmp < 0)
 173                         p = &(*p)->rb_left;
 174                 else
 175                         p = &(*p)->rb_right;
 176         }
 177
 178         rb_link_node(&he->rb_node, parent, p);
 179         rb_insert_color(&he->rb_node, root);
 180         return true;
 181 }
 182
 183 void hists__collapse_resort(struct hists *self)
 184 {
 185         struct rb_root tmp;
 186         struct rb_node *next;
 187         struct hist_entry *n;
 188
 189         if (!sort__need_collapse)
 190                 return;
 191
 192         tmp = RB_ROOT;
 193         next = rb_first(&self->entries);
 194         self->nr_entries = 0;
 195         self->max_sym_namelen = 0;
 196
 197         while (next) {
 198                 n = rb_entry(next, struct hist_entry, rb_node);
 199                 next = rb_next(&n->rb_node);
 200
 201                 rb_erase(&n->rb_node, &self->entries);
 202                 if (collapse__insert_entry(&tmp, n))
 203                         hists__inc_nr_entries(self, n);
 204         }
 205
 206         self->entries = tmp;
 207 }
 208
 209 /*
 210  * reverse the map, sort on period.
 211  */
 212
 213 static void __hists__insert_output_entry(struct rb_root *entries,
 214                                          struct hist_entry *he,
 215                                          u64 min_callchain_hits)
 216 {
 217         struct rb_node **p = &entries->rb_node;
 218         struct rb_node *parent = NULL;
 219         struct hist_entry *iter;
 220
 221         if (symbol_conf.use_callchain)
 222                 callchain_param.sort(&he->sorted_chain, he->callchain,
 223                                       min_callchain_hits, &callchain_param);
 224
 225         while (*p != NULL) {
 226                 parent = *p;
 227                 iter = rb_entry(parent, struct hist_entry, rb_node);
 228
 229                 if (he->period > iter->period)
 230                         p = &(*p)->rb_left;
 231                 else
 232                         p = &(*p)->rb_right;
 233         }
 234
 235         rb_link_node(&he->rb_node, parent, p);
 236         rb_insert_color(&he->rb_node, entries);
 237 }
 238
 239 void hists__output_resort(struct hists *self)
 240 {
 241         struct rb_root tmp;
 242         struct rb_node *next;
 243         struct hist_entry *n;
 244         u64 min_callchain_hits;
 245
 246         min_callchain_hits = self->stats.total_period * (callchain_param.min_percent / 100);
 247
 248         tmp = RB_ROOT;
 249         next = rb_first(&self->entries);
 250
 251         self->nr_entries = 0;
 252         self->max_sym_namelen = 0;
 253
 254         while (next) {
 255                 n = rb_entry(next, struct hist_entry, rb_node);
 256                 next = rb_next(&n->rb_node);
 257
 258                 rb_erase(&n->rb_node, &self->entries);
 259                 __hists__insert_output_entry(&tmp, n, min_callchain_hits);
 260                 hists__inc_nr_entries(self, n);
 261         }
 262
 263         self->entries = tmp;
 264 }
 265
 266 static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin)
 267 {
 268         int i;
 269         int ret = fprintf(fp, "            ");
 270
 271         for (i = 0; i < left_margin; i++)
 272                 ret += fprintf(fp, " ");
 273
 274         return ret;
 275 }
 276
 277 static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask,
 278                                           int left_margin)
 279 {
 280         int i;
 281         size_t ret = callchain__fprintf_left_margin(fp, left_margin);
 282
 283         for (i = 0; i < depth; i++)
 284                 if (depth_mask & (1 << i))
 285                         ret += fprintf(fp, "|          ");
 286                 else
 287                         ret += fprintf(fp, "           ");
 288
 289         ret += fprintf(fp, "\n");
 290
 291         return ret;
 292 }
 293
 294 static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain,
 295                                      int depth, int depth_mask, int period,
 296                                      u64 total_samples, int hits,
 297                                      int left_margin)
 298 {
 299         int i;
 300         size_t ret = 0;
 301
 302         ret += callchain__fprintf_left_margin(fp, left_margin);
 303         for (i = 0; i < depth; i++) {
 304                 if (depth_mask & (1 << i))
 305                         ret += fprintf(fp, "|");
 306                 else
 307                         ret += fprintf(fp, " ");
 308                 if (!period && i == depth - 1) {
 309                         double percent;
 310
 311                         percent = hits * 100.0 / total_samples;
 312                         ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent);
 313                 } else
 314                         ret += fprintf(fp, "%s", "          ");
 315         }
 316         if (chain->ms.sym)
 317                 ret += fprintf(fp, "%s\n", chain->ms.sym->name);
 318         else
 319                 ret += fprintf(fp, "%p\n", (void *)(long)chain->ip);
 320
 321         return ret;
 322 }
 323
 324 static struct symbol *rem_sq_bracket;
 325 static struct callchain_list rem_hits;
 326
 327 static void init_rem_hits(void)
 328 {
 329         rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6);
 330         if (!rem_sq_bracket) {
 331                 fprintf(stderr, "Not enough memory to display remaining hits\n");
 332                 return;
 333         }
 334
 335         strcpy(rem_sq_bracket->name, "[...]");
 336         rem_hits.ms.sym = rem_sq_bracket;
 337 }
 338
 339 static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
 340                                          u64 total_samples, int depth,
 341                                          int depth_mask, int left_margin)
 342 {
 343         struct rb_node *node, *next;
 344         struct callchain_node *child;
 345         struct callchain_list *chain;
 346         int new_depth_mask = depth_mask;
 347         u64 new_total;
 348         u64 remaining;
 349         size_t ret = 0;
 350         int i;
 351         uint entries_printed = 0;
 352
 353         if (callchain_param.mode == CHAIN_GRAPH_REL)
 354                 new_total = self->children_hit;
 355         else
 356                 new_total = total_samples;
 357
 358         remaining = new_total;
 359
 360         node = rb_first(&self->rb_root);
 361         while (node) {
 362                 u64 cumul;
 363
 364                 child = rb_entry(node, struct callchain_node, rb_node);
 365                 cumul = cumul_hits(child);
 366                 remaining -= cumul;
 367
 368                 /*
 369                  * The depth mask manages the output of pipes that show
 370                  * the depth. We don't want to keep the pipes of the current
 371                  * level for the last child of this depth.
 372                  * Except if we have remaining filtered hits. They will
 373                  * supersede the last child
 374                  */
 375                 next = rb_next(node);
 376                 if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining))
 377                         new_depth_mask &= ~(1 << (depth - 1));
 378
 379                 /*
 380                  * But we keep the older depth mask for the line separator
 381                  * to keep the level link until we reach the last child
 382                  */
 383                 ret += ipchain__fprintf_graph_line(fp, depth, depth_mask,
 384                                                    left_margin);
 385                 i = 0;
 386                 list_for_each_entry(chain, &child->val, list) {
 387                         ret += ipchain__fprintf_graph(fp, chain, depth,
 388                                                       new_depth_mask, i++,
 389                                                       new_total,
 390                                                       cumul,
 391                                                       left_margin);
 392                 }
 393                 ret += __callchain__fprintf_graph(fp, child, new_total,
 394                                                   depth + 1,
 395                                                   new_depth_mask | (1 << depth),
 396                                                   left_margin);
 397                 node = next;
 398                 if (++entries_printed == callchain_param.print_limit)
 399                         break;
 400         }
 401
 402         if (callchain_param.mode == CHAIN_GRAPH_REL &&
 403                 remaining && remaining != new_total) {
 404
 405                 if (!rem_sq_bracket)
 406                         return ret;
 407
 408                 new_depth_mask &= ~(1 << (depth - 1));
 409
 410                 ret += ipchain__fprintf_graph(fp, &rem_hits, depth,
 411                                               new_depth_mask, 0, new_total,
 412                                               remaining, left_margin);
 413         }
 414
 415         return ret;
 416 }
 417
 418 static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
 419                                        u64 total_samples, int left_margin)
 420 {
 421         struct callchain_list *chain;
 422         bool printed = false;
 423         int i = 0;
 424         int ret = 0;
 425         u32 entries_printed = 0;
 426
 427         list_for_each_entry(chain, &self->val, list) {
 428                 if (!i++ && sort__first_dimension == SORT_SYM)
 429                         continue;
 430
 431                 if (!printed) {
 432                         ret += callchain__fprintf_left_margin(fp, left_margin);
 433                         ret += fprintf(fp, "|\n");
 434                         ret += callchain__fprintf_left_margin(fp, left_margin);
 435                         ret += fprintf(fp, "---");
 436
 437                         left_margin += 3;
 438                         printed = true;
 439                 } else
 440                         ret += callchain__fprintf_left_margin(fp, left_margin);
 441
 442                 if (chain->ms.sym)
 443                         ret += fprintf(fp, " %s\n", chain->ms.sym->name);
 444                 else
 445                         ret += fprintf(fp, " %p\n", (void *)(long)chain->ip);
 446
 447                 if (++entries_printed == callchain_param.print_limit)
 448                         break;
 449         }
 450
 451         ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin);
 452
 453         return ret;
 454 }
 455
 456 static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self,
 457                                       u64 total_samples)
 458 {
 459         struct callchain_list *chain;
 460         size_t ret = 0;
 461
 462         if (!self)
 463                 return 0;
 464
 465         ret += callchain__fprintf_flat(fp, self->parent, total_samples);
 466
 467
 468         list_for_each_entry(chain, &self->val, list) {
 469                 if (chain->ip >= PERF_CONTEXT_MAX)
 470                         continue;
 471                 if (chain->ms.sym)
 472                         ret += fprintf(fp, "                %s\n", chain->ms.sym->name);
 473                 else
 474                         ret += fprintf(fp, "                %p\n",
 475                                         (void *)(long)chain->ip);
 476         }
 477
 478         return ret;
 479 }
 480
 481 static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self,
 482                                             u64 total_samples, int left_margin)
 483 {
 484         struct rb_node *rb_node;
 485         struct callchain_node *chain;
 486         size_t ret = 0;
 487         u32 entries_printed = 0;
 488
 489         rb_node = rb_first(&self->sorted_chain);
 490         while (rb_node) {
 491                 double percent;
 492
 493                 chain = rb_entry(rb_node, struct callchain_node, rb_node);
 494                 percent = chain->hit * 100.0 / total_samples;
 495                 switch (callchain_param.mode) {
 496                 case CHAIN_FLAT:
 497                         ret += percent_color_fprintf(fp, "           %6.2f%%\n",
 498                                                      percent);
 499                         ret += callchain__fprintf_flat(fp, chain, total_samples);
 500                         break;
 501                 case CHAIN_GRAPH_ABS: /* Falldown */
 502                 case CHAIN_GRAPH_REL:
 503                         ret += callchain__fprintf_graph(fp, chain, total_samples,
 504                                                         left_margin);
 505                 case CHAIN_NONE:
 506                 default:
 507                         break;
 508                 }
 509                 ret += fprintf(fp, "\n");
 510                 if (++entries_printed == callchain_param.print_limit)
 511                         break;
 512                 rb_node = rb_next(rb_node);
 513         }
 514
 515         return ret;
 516 }
 517
 518 int hist_entry__snprintf(struct hist_entry *self, char *s, size_t size,
 519                          struct hists *pair_hists, bool show_displacement,
 520                          long displacement, bool color, u64 session_total)
 521 {
 522         struct sort_entry *se;
 523         u64 period, total, period_sys, period_us, period_guest_sys, period_guest_us;
 524         const char *sep = symbol_conf.field_sep;
 525         int ret;
 526
 527         if (symbol_conf.exclude_other && !self->parent)
 528                 return 0;
 529
 530         if (pair_hists) {
 531                 period = self->pair ? self->pair->period : 0;
 532                 total = pair_hists->stats.total_period;
 533                 period_sys = self->pair ? self->pair->period_sys : 0;
 534                 period_us = self->pair ? self->pair->period_us : 0;
 535                 period_guest_sys = self->pair ? self->pair->period_guest_sys : 0;
 536                 period_guest_us = self->pair ? self->pair->period_guest_us : 0;
 537         } else {
 538                 period = self->period;
 539                 total = session_total;
 540                 period_sys = self->period_sys;
 541                 period_us = self->period_us;
 542                 period_guest_sys = self->period_guest_sys;
 543                 period_guest_us = self->period_guest_us;
 544         }
 545
 546         if (total) {
 547                 if (color)
 548                         ret = percent_color_snprintf(s, size,
 549                                                      sep ? "%.2f" : "   %6.2f%%",
 550                                                      (period * 100.0) / total);
 551                 else
 552                         ret = snprintf(s, size, sep ? "%.2f" : "   %6.2f%%",
 553                                        (period * 100.0) / total);
 554                 if (symbol_conf.show_cpu_utilization) {
 555                         ret += percent_color_snprintf(s + ret, size - ret,
 556                                         sep ? "%.2f" : "   %6.2f%%",
 557                                         (period_sys * 100.0) / total);
 558                         ret += percent_color_snprintf(s + ret, size - ret,
 559                                         sep ? "%.2f" : "   %6.2f%%",
 560                                         (period_us * 100.0) / total);
 561                         if (perf_guest) {
 562                                 ret += percent_color_snprintf(s + ret,
 563                                                 size - ret,
 564                                                 sep ? "%.2f" : "   %6.2f%%",
 565                                                 (period_guest_sys * 100.0) /
 566                                                                 total);
 567                                 ret += percent_color_snprintf(s + ret,
 568                                                 size - ret,
 569                                                 sep ? "%.2f" : "   %6.2f%%",
 570                                                 (period_guest_us * 100.0) /
 571                                                                 total);
 572                         }
 573                 }
 574         } else
 575                 ret = snprintf(s, size, sep ? "%lld" : "%12lld ", period);
 576
 577         if (symbol_conf.show_nr_samples) {
 578                 if (sep)
 579                         ret += snprintf(s + ret, size - ret, "%c%lld", *sep, period);
 580                 else
 581                         ret += snprintf(s + ret, size - ret, "%11lld", period);
 582         }
 583
 584         if (pair_hists) {
 585                 char bf[32];
 586                 double old_percent = 0, new_percent = 0, diff;
 587
 588                 if (total > 0)
 589                         old_percent = (period * 100.0) / total;
 590                 if (session_total > 0)
 591                         new_percent = (self->period * 100.0) / session_total;
 592
 593                 diff = new_percent - old_percent;
 594
 595                 if (fabs(diff) >= 0.01)
 596                         snprintf(bf, sizeof(bf), "%+4.2F%%", diff);
 597                 else
 598                         snprintf(bf, sizeof(bf), " ");
 599
 600                 if (sep)
 601                         ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
 602                 else
 603                         ret += snprintf(s + ret, size - ret, "%11.11s", bf);
 604
 605                 if (show_displacement) {
 606                         if (displacement)
 607                                 snprintf(bf, sizeof(bf), "%+4ld", displacement);
 608                         else
 609                                 snprintf(bf, sizeof(bf), " ");
 610
 611                         if (sep)
 612                                 ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
 613                         else
 614                                 ret += snprintf(s + ret, size - ret, "%6.6s", bf);
 615                 }
 616         }
 617
 618         list_for_each_entry(se, &hist_entry__sort_list, list) {
 619                 if (se->elide)
 620                         continue;
 621
 622                 ret += snprintf(s + ret, size - ret, "%s", sep ?: "  ");
 623                 ret += se->se_snprintf(self, s + ret, size - ret,
 624                                        se->se_width ? *se->se_width : 0);
 625         }
 626
 627         return ret;
 628 }
 629
 630 int hist_entry__fprintf(struct hist_entry *self, struct hists *pair_hists,
 631                         bool show_displacement, long displacement, FILE *fp,
 632                         u64 session_total)
 633 {
 634         char bf[512];
 635         hist_entry__snprintf(self, bf, sizeof(bf), pair_hists,
 636                              show_displacement, displacement,
 637                              true, session_total);
 638         return fprintf(fp, "%s\n", bf);
 639 }
 640
 641 static size_t hist_entry__fprintf_callchain(struct hist_entry *self, FILE *fp,
 642                                             u64 session_total)
 643 {
 644         int left_margin = 0;
 645
 646         if (sort__first_dimension == SORT_COMM) {
 647                 struct sort_entry *se = list_first_entry(&hist_entry__sort_list,
 648                                                          typeof(*se), list);
 649                 left_margin = se->se_width ? *se->se_width : 0;
 650                 left_margin -= thread__comm_len(self->thread);
 651         }
 652
 653         return hist_entry_callchain__fprintf(fp, self, session_total,
 654                                              left_margin);
 655 }
 656
 657 size_t hists__fprintf(struct hists *self, struct hists *pair,
 658                       bool show_displacement, FILE *fp)
 659 {
 660         struct sort_entry *se;
 661         struct rb_node *nd;
 662         size_t ret = 0;
 663         unsigned long position = 1;
 664         long displacement = 0;
 665         unsigned int width;
 666         const char *sep = symbol_conf.field_sep;
 667         const char *col_width = symbol_conf.col_width_list_str;
 668
 669         init_rem_hits();
 670
 671         fprintf(fp, "# %s", pair ? "Baseline" : "Overhead");
 672
 673         if (symbol_conf.show_nr_samples) {
 674                 if (sep)
 675                         fprintf(fp, "%cSamples", *sep);
 676                 else
 677                         fputs("  Samples  ", fp);
 678         }
 679
 680         if (symbol_conf.show_cpu_utilization) {
 681                 if (sep) {
 682                         ret += fprintf(fp, "%csys", *sep);
 683                         ret += fprintf(fp, "%cus", *sep);
 684                         if (perf_guest) {
 685                                 ret += fprintf(fp, "%cguest sys", *sep);
 686                                 ret += fprintf(fp, "%cguest us", *sep);
 687                         }
 688                 } else {
 689                         ret += fprintf(fp, "  sys  ");
 690                         ret += fprintf(fp, "  us  ");
 691                         if (perf_guest) {
 692                                 ret += fprintf(fp, "  guest sys  ");
 693                                 ret += fprintf(fp, "  guest us  ");
 694                         }
 695                 }
 696         }
 697
 698         if (pair) {
 699                 if (sep)
 700                         ret += fprintf(fp, "%cDelta", *sep);
 701                 else
 702                         ret += fprintf(fp, "  Delta    ");
 703
 704                 if (show_displacement) {
 705                         if (sep)
 706                                 ret += fprintf(fp, "%cDisplacement", *sep);
 707                         else
 708                                 ret += fprintf(fp, " Displ");
 709                 }
 710         }
 711
 712         list_for_each_entry(se, &hist_entry__sort_list, list) {
 713                 if (se->elide)
 714                         continue;
 715                 if (sep) {
 716                         fprintf(fp, "%c%s", *sep, se->se_header);
 717                         continue;
 718                 }
 719                 width = strlen(se->se_header);
 720                 if (se->se_width) {
 721                         if (symbol_conf.col_width_list_str) {
 722                                 if (col_width) {
 723                                         *se->se_width = atoi(col_width);
 724                                         col_width = strchr(col_width, ',');
 725                                         if (col_width)
 726                                                 ++col_width;
 727                                 }
 728                         }
 729                         width = *se->se_width = max(*se->se_width, width);
 730                 }
 731                 fprintf(fp, "  %*s", width, se->se_header);
 732         }
 733         fprintf(fp, "\n");
 734
 735         if (sep)
 736                 goto print_entries;
 737
 738         fprintf(fp, "# ........");
 739         if (symbol_conf.show_nr_samples)
 740                 fprintf(fp, " ..........");
 741         if (pair) {
 742                 fprintf(fp, " ..........");
 743                 if (show_displacement)
 744                         fprintf(fp, " .....");
 745         }
 746         list_for_each_entry(se, &hist_entry__sort_list, list) {
 747                 unsigned int i;
 748
 749                 if (se->elide)
 750                         continue;
 751
 752                 fprintf(fp, "  ");
 753                 if (se->se_width)
 754                         width = *se->se_width;
 755                 else
 756                         width = strlen(se->se_header);
 757                 for (i = 0; i < width; i++)
 758                         fprintf(fp, ".");
 759         }
 760
 761         fprintf(fp, "\n#\n");
 762
 763 print_entries:
 764         for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
 765                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 766
 767                 if (show_displacement) {
 768                         if (h->pair != NULL)
 769                                 displacement = ((long)h->pair->position -
 770                                                 (long)position);
 771                         else
 772                                 displacement = 0;
 773                         ++position;
 774                 }
 775                 ret += hist_entry__fprintf(h, pair, show_displacement,
 776                                            displacement, fp, self->stats.total_period);
 777
 778                 if (symbol_conf.use_callchain)
 779                         ret += hist_entry__fprintf_callchain(h, fp, self->stats.total_period);
 780
 781                 if (h->ms.map == NULL && verbose > 1) {
 782                         __map_groups__fprintf_maps(&h->thread->mg,
 783                                                    MAP__FUNCTION, verbose, fp);
 784                         fprintf(fp, "%.10s end\n", graph_dotted_line);
 785                 }
 786         }
 787
 788         free(rem_sq_bracket);
 789
 790         return ret;
 791 }
 792
 793 enum hist_filter {
 794         HIST_FILTER__DSO,
 795         HIST_FILTER__THREAD,
 796 };
 797
 798 void hists__filter_by_dso(struct hists *self, const struct dso *dso)
 799 {
 800         struct rb_node *nd;
 801
 802         self->nr_entries = self->stats.total_period = 0;
 803         self->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
 804         self->max_sym_namelen = 0;
 805
 806         for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
 807                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 808
 809                 if (symbol_conf.exclude_other && !h->parent)
 810                         continue;
 811
 812                 if (dso != NULL && (h->ms.map == NULL || h->ms.map->dso != dso)) {
 813                         h->filtered |= (1 << HIST_FILTER__DSO);
 814                         continue;
 815                 }
 816
 817                 h->filtered &= ~(1 << HIST_FILTER__DSO);
 818                 if (!h->filtered) {
 819                         ++self->nr_entries;
 820                         self->stats.total_period += h->period;
 821                         self->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events;
 822                         if (h->ms.sym &&
 823                             self->max_sym_namelen < h->ms.sym->namelen)
 824                                 self->max_sym_namelen = h->ms.sym->namelen;
 825                 }
 826         }
 827 }
 828
 829 void hists__filter_by_thread(struct hists *self, const struct thread *thread)
 830 {
 831         struct rb_node *nd;
 832
 833         self->nr_entries = self->stats.total_period = 0;
 834         self->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
 835         self->max_sym_namelen = 0;
 836
 837         for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
 838                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 839
 840                 if (thread != NULL && h->thread != thread) {
 841                         h->filtered |= (1 << HIST_FILTER__THREAD);
 842                         continue;
 843                 }
 844                 h->filtered &= ~(1 << HIST_FILTER__THREAD);
 845                 if (!h->filtered) {
 846                         ++self->nr_entries;
 847                         self->stats.total_period += h->period;
 848                         self->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events;
 849                         if (h->ms.sym &&
 850                             self->max_sym_namelen < h->ms.sym->namelen)
 851                                 self->max_sym_namelen = h->ms.sym->namelen;
 852                 }
 853         }
 854 }
 855
 856 static int symbol__alloc_hist(struct symbol *self)
 857 {
 858         struct sym_priv *priv = symbol__priv(self);
 859         const int size = (sizeof(*priv->hist) +
 860                           (self->end - self->start) * sizeof(u64));
 861
 862         priv->hist = zalloc(size);
 863         return priv->hist == NULL ? -1 : 0;
 864 }
 865
 866 int hist_entry__inc_addr_samples(struct hist_entry *self, u64 ip)
 867 {
 868         unsigned int sym_size, offset;
 869         struct symbol *sym = self->ms.sym;
 870         struct sym_priv *priv;
 871         struct sym_hist *h;
 872
 873         if (!sym || !self->ms.map)
 874                 return 0;
 875
 876         priv = symbol__priv(sym);
 877         if (priv->hist == NULL && symbol__alloc_hist(sym) < 0)
 878                 return -ENOMEM;
 879
 880         sym_size = sym->end - sym->start;
 881         offset = ip - sym->start;
 882
 883         pr_debug3("%s: ip=%#Lx\n", __func__, self->ms.map->unmap_ip(self->ms.map, ip));
 884
 885         if (offset >= sym_size)
 886                 return 0;
 887
 888         h = priv->hist;
 889         h->sum++;
 890         h->ip[offset]++;
 891
 892         pr_debug3("%#Lx %s: period++ [ip: %#Lx, %#Lx] => %Ld\n", self->ms.sym->start,
 893                   self->ms.sym->name, ip, ip - self->ms.sym->start, h->ip[offset]);
 894         return 0;
 895 }
 896
 897 static struct objdump_line *objdump_line__new(s64 offset, char *line)
 898 {
 899         struct objdump_line *self = malloc(sizeof(*self));
 900
 901         if (self != NULL) {
 902                 self->offset = offset;
 903                 self->line = line;
 904         }
 905
 906         return self;
 907 }
 908
 909 void objdump_line__free(struct objdump_line *self)
 910 {
 911         free(self->line);
 912         free(self);
 913 }
 914
 915 static void objdump__add_line(struct list_head *head, struct objdump_line *line)
 916 {
 917         list_add_tail(&line->node, head);
 918 }
 919
 920 struct objdump_line *objdump__get_next_ip_line(struct list_head *head,
 921                                                struct objdump_line *pos)
 922 {
 923         list_for_each_entry_continue(pos, head, node)
 924                 if (pos->offset >= 0)
 925                         return pos;
 926
 927         return NULL;
 928 }
 929
 930 static int hist_entry__parse_objdump_line(struct hist_entry *self, FILE *file,
 931                                           struct list_head *head)
 932 {
 933         struct symbol *sym = self->ms.sym;
 934         struct objdump_line *objdump_line;
 935         char *line = NULL, *tmp, *tmp2, *c;
 936         size_t line_len;
 937         s64 line_ip, offset = -1;
 938
 939         if (getline(&line, &line_len, file) < 0)
 940                 return -1;
 941
 942         if (!line)
 943                 return -1;
 944
 945         while (line_len != 0 && isspace(line[line_len - 1]))
 946                 line[--line_len] = '\0';
 947
 948         c = strchr(line, '\n');
 949         if (c)
 950                 *c = 0;
 951
 952         line_ip = -1;
 953
 954         /*
 955          * Strip leading spaces:
 956          */
 957         tmp = line;
 958         while (*tmp) {
 959                 if (*tmp != ' ')
 960                         break;
 961                 tmp++;
 962         }
 963
 964         if (*tmp) {
 965                 /*
 966                  * Parse hexa addresses followed by ':'
 967                  */
 968                 line_ip = strtoull(tmp, &tmp2, 16);
 969                 if (*tmp2 != ':' || tmp == tmp2)
 970                         line_ip = -1;
 971         }
 972
 973         if (line_ip != -1) {
 974                 u64 start = map__rip_2objdump(self->ms.map, sym->start);
 975                 offset = line_ip - start;
 976         }
 977
 978         objdump_line = objdump_line__new(offset, line);
 979         if (objdump_line == NULL) {
 980                 free(line);
 981                 return -1;
 982         }
 983         objdump__add_line(head, objdump_line);
 984
 985         return 0;
 986 }
 987
 988 int hist_entry__annotate(struct hist_entry *self, struct list_head *head)
 989 {
 990         struct symbol *sym = self->ms.sym;
 991         struct map *map = self->ms.map;
 992         struct dso *dso = map->dso;
 993         char *filename = dso__build_id_filename(dso, NULL, 0);
 994         bool free_filename = true;
 995         char command[PATH_MAX * 2];
 996         FILE *file;
 997         int err = 0;
 998         u64 len;
 999
1000         if (filename == NULL) {
1001                 if (dso->has_build_id) {
1002                         pr_err("Can't annotate %s: not enough memory\n",
1003                                sym->name);
1004                         return -ENOMEM;
1005                 }
1006                 goto fallback;
1007         } else if (readlink(filename, command, sizeof(command)) < 0 ||
1008                    strstr(command, "[kernel.kallsyms]") ||
1009                    access(filename, R_OK)) {
1010                 free(filename);
1011 fallback:
1012                 /*
1013                  * If we don't have build-ids or the build-id file isn't in the
1014                  * cache, or is just a kallsyms file, well, lets hope that this
1015                  * DSO is the same as when 'perf record' ran.
1016                  */
1017                 filename = dso->long_name;
1018                 free_filename = false;
1019         }
1020
1021         if (dso->origin == DSO__ORIG_KERNEL) {
1022                 if (dso->annotate_warned)
1023                         goto out_free_filename;
1024                 err = -ENOENT;
1025                 dso->annotate_warned = 1;
1026                 pr_err("Can't annotate %s: No vmlinux file was found in the "
1027                        "path\n", sym->name);
1028                 goto out_free_filename;
1029         }
1030
1031         pr_debug("%s: filename=%s, sym=%s, start=%#Lx, end=%#Lx\n", __func__,
1032                  filename, sym->name, map->unmap_ip(map, sym->start),
1033                  map->unmap_ip(map, sym->end));
1034
1035         len = sym->end - sym->start;
1036
1037         pr_debug("annotating [%p] %30s : [%p] %30s\n",
1038                  dso, dso->long_name, sym, sym->name);
1039
1040         snprintf(command, sizeof(command),
1041                  "objdump --start-address=0x%016Lx --stop-address=0x%016Lx -dS -C %s|grep -v %s|expand",
1042                  map__rip_2objdump(map, sym->start),
1043                  map__rip_2objdump(map, sym->end),
1044                  filename, filename);
1045
1046         pr_debug("Executing: %s\n", command);
1047
1048         file = popen(command, "r");
1049         if (!file)
1050                 goto out_free_filename;
1051
1052         while (!feof(file))
1053                 if (hist_entry__parse_objdump_line(self, file, head) < 0)
1054                         break;
1055
1056         pclose(file);
1057 out_free_filename:
1058         if (free_filename)
1059                 free(filename);
1060         return err;
1061 }
1062
1063 void hists__inc_nr_events(struct hists *self, u32 type)
1064 {
1065         ++self->stats.nr_events[0];
1066         ++self->stats.nr_events[type];
1067 }
1068
1069 size_t hists__fprintf_nr_events(struct hists *self, FILE *fp)
1070 {
1071         int i;
1072         size_t ret = 0;
1073
1074         for (i = 0; i < PERF_RECORD_HEADER_MAX; ++i) {
1075                 if (!event__name[i])
1076                         continue;
1077                 ret += fprintf(fp, "%10s events: %10d\n",
1078                                event__name[i], self->stats.nr_events[i]);
1079         }
1080
1081         return ret;
1082 }