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