tools/perf/util/hist.c

   1 #include "hist.h"
   2 #include "session.h"
   3 #include "sort.h"
   4 #include <math.h>
   5
   6 struct callchain_param  callchain_param = {
   7         .mode   = CHAIN_GRAPH_REL,
   8         .min_percent = 0.5
   9 };
  10
  11 /*
  12  * histogram, sorted on item, collects counts
  13  */
  14
  15 struct hist_entry *__perf_session__add_hist_entry(struct rb_root *hists,
  16                                                   struct addr_location *al,
  17                                                   struct symbol *sym_parent,
  18                                                   u64 count, bool *hit)
  19 {
  20         struct rb_node **p = &hists->rb_node;
  21         struct rb_node *parent = NULL;
  22         struct hist_entry *he;
  23         struct hist_entry entry = {
  24                 .thread = al->thread,
  25                 .ms = {
  26                         .map    = al->map,
  27                         .sym    = al->sym,
  28                 },
  29                 .ip     = al->addr,
  30                 .level  = al->level,
  31                 .count  = count,
  32                 .parent = sym_parent,
  33         };
  34         int cmp;
  35
  36         while (*p != NULL) {
  37                 parent = *p;
  38                 he = rb_entry(parent, struct hist_entry, rb_node);
  39
  40                 cmp = hist_entry__cmp(&entry, he);
  41
  42                 if (!cmp) {
  43                         *hit = true;
  44                         return he;
  45                 }
  46
  47                 if (cmp < 0)
  48                         p = &(*p)->rb_left;
  49                 else
  50                         p = &(*p)->rb_right;
  51         }
  52
  53         he = malloc(sizeof(*he) + (symbol_conf.use_callchain ?
  54                                     sizeof(struct callchain_node) : 0));
  55         if (!he)
  56                 return NULL;
  57         *he = entry;
  58         rb_link_node(&he->rb_node, parent, p);
  59         rb_insert_color(&he->rb_node, hists);
  60         *hit = false;
  61         return he;
  62 }
  63
  64 int64_t
  65 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
  66 {
  67         struct sort_entry *se;
  68         int64_t cmp = 0;
  69
  70         list_for_each_entry(se, &hist_entry__sort_list, list) {
  71                 cmp = se->se_cmp(left, right);
  72                 if (cmp)
  73                         break;
  74         }
  75
  76         return cmp;
  77 }
  78
  79 int64_t
  80 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
  81 {
  82         struct sort_entry *se;
  83         int64_t cmp = 0;
  84
  85         list_for_each_entry(se, &hist_entry__sort_list, list) {
  86                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
  87
  88                 f = se->se_collapse ?: se->se_cmp;
  89
  90                 cmp = f(left, right);
  91                 if (cmp)
  92                         break;
  93         }
  94
  95         return cmp;
  96 }
  97
  98 void hist_entry__free(struct hist_entry *he)
  99 {
 100         free(he);
 101 }
 102
 103 /*
 104  * collapse the histogram
 105  */
 106
 107 static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
 108 {
 109         struct rb_node **p = &root->rb_node;
 110         struct rb_node *parent = NULL;
 111         struct hist_entry *iter;
 112         int64_t cmp;
 113
 114         while (*p != NULL) {
 115                 parent = *p;
 116                 iter = rb_entry(parent, struct hist_entry, rb_node);
 117
 118                 cmp = hist_entry__collapse(iter, he);
 119
 120                 if (!cmp) {
 121                         iter->count += he->count;
 122                         hist_entry__free(he);
 123                         return;
 124                 }
 125
 126                 if (cmp < 0)
 127                         p = &(*p)->rb_left;
 128                 else
 129                         p = &(*p)->rb_right;
 130         }
 131
 132         rb_link_node(&he->rb_node, parent, p);
 133         rb_insert_color(&he->rb_node, root);
 134 }
 135
 136 void perf_session__collapse_resort(struct rb_root *hists)
 137 {
 138         struct rb_root tmp;
 139         struct rb_node *next;
 140         struct hist_entry *n;
 141
 142         if (!sort__need_collapse)
 143                 return;
 144
 145         tmp = RB_ROOT;
 146         next = rb_first(hists);
 147
 148         while (next) {
 149                 n = rb_entry(next, struct hist_entry, rb_node);
 150                 next = rb_next(&n->rb_node);
 151
 152                 rb_erase(&n->rb_node, hists);
 153                 collapse__insert_entry(&tmp, n);
 154         }
 155
 156         *hists = tmp;
 157 }
 158
 159 /*
 160  * reverse the map, sort on count.
 161  */
 162
 163 static void perf_session__insert_output_hist_entry(struct rb_root *root,
 164                                                    struct hist_entry *he,
 165                                                    u64 min_callchain_hits)
 166 {
 167         struct rb_node **p = &root->rb_node;
 168         struct rb_node *parent = NULL;
 169         struct hist_entry *iter;
 170
 171         if (symbol_conf.use_callchain)
 172                 callchain_param.sort(&he->sorted_chain, he->callchain,
 173                                       min_callchain_hits, &callchain_param);
 174
 175         while (*p != NULL) {
 176                 parent = *p;
 177                 iter = rb_entry(parent, struct hist_entry, rb_node);
 178
 179                 if (he->count > iter->count)
 180                         p = &(*p)->rb_left;
 181                 else
 182                         p = &(*p)->rb_right;
 183         }
 184
 185         rb_link_node(&he->rb_node, parent, p);
 186         rb_insert_color(&he->rb_node, root);
 187 }
 188
 189 u64 perf_session__output_resort(struct rb_root *hists, u64 total_samples)
 190 {
 191         struct rb_root tmp;
 192         struct rb_node *next;
 193         struct hist_entry *n;
 194         u64 min_callchain_hits;
 195         u64 nr_hists = 0;
 196
 197         min_callchain_hits =
 198                 total_samples * (callchain_param.min_percent / 100);
 199
 200         tmp = RB_ROOT;
 201         next = rb_first(hists);
 202
 203         while (next) {
 204                 n = rb_entry(next, struct hist_entry, rb_node);
 205                 next = rb_next(&n->rb_node);
 206
 207                 rb_erase(&n->rb_node, hists);
 208                 perf_session__insert_output_hist_entry(&tmp, n,
 209                                                        min_callchain_hits);
 210                 ++nr_hists;
 211         }
 212
 213         *hists = tmp;
 214         return nr_hists;
 215 }
 216
 217 static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin)
 218 {
 219         int i;
 220         int ret = fprintf(fp, "            ");
 221
 222         for (i = 0; i < left_margin; i++)
 223                 ret += fprintf(fp, " ");
 224
 225         return ret;
 226 }
 227
 228 static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask,
 229                                           int left_margin)
 230 {
 231         int i;
 232         size_t ret = callchain__fprintf_left_margin(fp, left_margin);
 233
 234         for (i = 0; i < depth; i++)
 235                 if (depth_mask & (1 << i))
 236                         ret += fprintf(fp, "|          ");
 237                 else
 238                         ret += fprintf(fp, "           ");
 239
 240         ret += fprintf(fp, "\n");
 241
 242         return ret;
 243 }
 244
 245 static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain,
 246                                      int depth, int depth_mask, int count,
 247                                      u64 total_samples, int hits,
 248                                      int left_margin)
 249 {
 250         int i;
 251         size_t ret = 0;
 252
 253         ret += callchain__fprintf_left_margin(fp, left_margin);
 254         for (i = 0; i < depth; i++) {
 255                 if (depth_mask & (1 << i))
 256                         ret += fprintf(fp, "|");
 257                 else
 258                         ret += fprintf(fp, " ");
 259                 if (!count && i == depth - 1) {
 260                         double percent;
 261
 262                         percent = hits * 100.0 / total_samples;
 263                         ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent);
 264                 } else
 265                         ret += fprintf(fp, "%s", "          ");
 266         }
 267         if (chain->ms.sym)
 268                 ret += fprintf(fp, "%s\n", chain->ms.sym->name);
 269         else
 270                 ret += fprintf(fp, "%p\n", (void *)(long)chain->ip);
 271
 272         return ret;
 273 }
 274
 275 static struct symbol *rem_sq_bracket;
 276 static struct callchain_list rem_hits;
 277
 278 static void init_rem_hits(void)
 279 {
 280         rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6);
 281         if (!rem_sq_bracket) {
 282                 fprintf(stderr, "Not enough memory to display remaining hits\n");
 283                 return;
 284         }
 285
 286         strcpy(rem_sq_bracket->name, "[...]");
 287         rem_hits.ms.sym = rem_sq_bracket;
 288 }
 289
 290 static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
 291                                          u64 total_samples, int depth,
 292                                          int depth_mask, int left_margin)
 293 {
 294         struct rb_node *node, *next;
 295         struct callchain_node *child;
 296         struct callchain_list *chain;
 297         int new_depth_mask = depth_mask;
 298         u64 new_total;
 299         u64 remaining;
 300         size_t ret = 0;
 301         int i;
 302
 303         if (callchain_param.mode == CHAIN_GRAPH_REL)
 304                 new_total = self->children_hit;
 305         else
 306                 new_total = total_samples;
 307
 308         remaining = new_total;
 309
 310         node = rb_first(&self->rb_root);
 311         while (node) {
 312                 u64 cumul;
 313
 314                 child = rb_entry(node, struct callchain_node, rb_node);
 315                 cumul = cumul_hits(child);
 316                 remaining -= cumul;
 317
 318                 /*
 319                  * The depth mask manages the output of pipes that show
 320                  * the depth. We don't want to keep the pipes of the current
 321                  * level for the last child of this depth.
 322                  * Except if we have remaining filtered hits. They will
 323                  * supersede the last child
 324                  */
 325                 next = rb_next(node);
 326                 if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining))
 327                         new_depth_mask &= ~(1 << (depth - 1));
 328
 329                 /*
 330                  * But we keep the older depth mask for the line separator
 331                  * to keep the level link until we reach the last child
 332                  */
 333                 ret += ipchain__fprintf_graph_line(fp, depth, depth_mask,
 334                                                    left_margin);
 335                 i = 0;
 336                 list_for_each_entry(chain, &child->val, list) {
 337                         ret += ipchain__fprintf_graph(fp, chain, depth,
 338                                                       new_depth_mask, i++,
 339                                                       new_total,
 340                                                       cumul,
 341                                                       left_margin);
 342                 }
 343                 ret += __callchain__fprintf_graph(fp, child, new_total,
 344                                                   depth + 1,
 345                                                   new_depth_mask | (1 << depth),
 346                                                   left_margin);
 347                 node = next;
 348         }
 349
 350         if (callchain_param.mode == CHAIN_GRAPH_REL &&
 351                 remaining && remaining != new_total) {
 352
 353                 if (!rem_sq_bracket)
 354                         return ret;
 355
 356                 new_depth_mask &= ~(1 << (depth - 1));
 357
 358                 ret += ipchain__fprintf_graph(fp, &rem_hits, depth,
 359                                               new_depth_mask, 0, new_total,
 360                                               remaining, left_margin);
 361         }
 362
 363         return ret;
 364 }
 365
 366 static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
 367                                        u64 total_samples, int left_margin)
 368 {
 369         struct callchain_list *chain;
 370         bool printed = false;
 371         int i = 0;
 372         int ret = 0;
 373
 374         list_for_each_entry(chain, &self->val, list) {
 375                 if (!i++ && sort__first_dimension == SORT_SYM)
 376                         continue;
 377
 378                 if (!printed) {
 379                         ret += callchain__fprintf_left_margin(fp, left_margin);
 380                         ret += fprintf(fp, "|\n");
 381                         ret += callchain__fprintf_left_margin(fp, left_margin);
 382                         ret += fprintf(fp, "---");
 383
 384                         left_margin += 3;
 385                         printed = true;
 386                 } else
 387                         ret += callchain__fprintf_left_margin(fp, left_margin);
 388
 389                 if (chain->ms.sym)
 390                         ret += fprintf(fp, " %s\n", chain->ms.sym->name);
 391                 else
 392                         ret += fprintf(fp, " %p\n", (void *)(long)chain->ip);
 393         }
 394
 395         ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin);
 396
 397         return ret;
 398 }
 399
 400 static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self,
 401                                       u64 total_samples)
 402 {
 403         struct callchain_list *chain;
 404         size_t ret = 0;
 405
 406         if (!self)
 407                 return 0;
 408
 409         ret += callchain__fprintf_flat(fp, self->parent, total_samples);
 410
 411
 412         list_for_each_entry(chain, &self->val, list) {
 413                 if (chain->ip >= PERF_CONTEXT_MAX)
 414                         continue;
 415                 if (chain->ms.sym)
 416                         ret += fprintf(fp, "                %s\n", chain->ms.sym->name);
 417                 else
 418                         ret += fprintf(fp, "                %p\n",
 419                                         (void *)(long)chain->ip);
 420         }
 421
 422         return ret;
 423 }
 424
 425 static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self,
 426                                             u64 total_samples, int left_margin)
 427 {
 428         struct rb_node *rb_node;
 429         struct callchain_node *chain;
 430         size_t ret = 0;
 431
 432         rb_node = rb_first(&self->sorted_chain);
 433         while (rb_node) {
 434                 double percent;
 435
 436                 chain = rb_entry(rb_node, struct callchain_node, rb_node);
 437                 percent = chain->hit * 100.0 / total_samples;
 438                 switch (callchain_param.mode) {
 439                 case CHAIN_FLAT:
 440                         ret += percent_color_fprintf(fp, "           %6.2f%%\n",
 441                                                      percent);
 442                         ret += callchain__fprintf_flat(fp, chain, total_samples);
 443                         break;
 444                 case CHAIN_GRAPH_ABS: /* Falldown */
 445                 case CHAIN_GRAPH_REL:
 446                         ret += callchain__fprintf_graph(fp, chain, total_samples,
 447                                                         left_margin);
 448                 case CHAIN_NONE:
 449                 default:
 450                         break;
 451                 }
 452                 ret += fprintf(fp, "\n");
 453                 rb_node = rb_next(rb_node);
 454         }
 455
 456         return ret;
 457 }
 458
 459 int hist_entry__snprintf(struct hist_entry *self,
 460                            char *s, size_t size,
 461                            struct perf_session *pair_session,
 462                            bool show_displacement,
 463                            long displacement, bool color,
 464                            u64 session_total)
 465 {
 466         struct sort_entry *se;
 467         u64 count, total;
 468         const char *sep = symbol_conf.field_sep;
 469         int ret;
 470
 471         if (symbol_conf.exclude_other && !self->parent)
 472                 return 0;
 473
 474         if (pair_session) {
 475                 count = self->pair ? self->pair->count : 0;
 476                 total = pair_session->events_stats.total;
 477         } else {
 478                 count = self->count;
 479                 total = session_total;
 480         }
 481
 482         if (total) {
 483                 if (color)
 484                         ret = percent_color_snprintf(s, size,
 485                                                      sep ? "%.2f" : "   %6.2f%%",
 486                                                      (count * 100.0) / total);
 487                 else
 488                         ret = snprintf(s, size, sep ? "%.2f" : "   %6.2f%%",
 489                                        (count * 100.0) / total);
 490         } else
 491                 ret = snprintf(s, size, sep ? "%lld" : "%12lld ", count);
 492
 493         if (symbol_conf.show_nr_samples) {
 494                 if (sep)
 495                         ret += snprintf(s + ret, size - ret, "%c%lld", *sep, count);
 496                 else
 497                         ret += snprintf(s + ret, size - ret, "%11lld", count);
 498         }
 499
 500         if (pair_session) {
 501                 char bf[32];
 502                 double old_percent = 0, new_percent = 0, diff;
 503
 504                 if (total > 0)
 505                         old_percent = (count * 100.0) / total;
 506                 if (session_total > 0)
 507                         new_percent = (self->count * 100.0) / session_total;
 508
 509                 diff = new_percent - old_percent;
 510
 511                 if (fabs(diff) >= 0.01)
 512                         snprintf(bf, sizeof(bf), "%+4.2F%%", diff);
 513                 else
 514                         snprintf(bf, sizeof(bf), " ");
 515
 516                 if (sep)
 517                         ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
 518                 else
 519                         ret += snprintf(s + ret, size - ret, "%11.11s", bf);
 520
 521                 if (show_displacement) {
 522                         if (displacement)
 523                                 snprintf(bf, sizeof(bf), "%+4ld", displacement);
 524                         else
 525                                 snprintf(bf, sizeof(bf), " ");
 526
 527                         if (sep)
 528                                 ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
 529                         else
 530                                 ret += snprintf(s + ret, size - ret, "%6.6s", bf);
 531                 }
 532         }
 533
 534         list_for_each_entry(se, &hist_entry__sort_list, list) {
 535                 if (se->elide)
 536                         continue;
 537
 538                 ret += snprintf(s + ret, size - ret, "%s", sep ?: "  ");
 539                 ret += se->se_snprintf(self, s + ret, size - ret,
 540                                        se->se_width ? *se->se_width : 0);
 541         }
 542
 543         return ret;
 544 }
 545
 546 int hist_entry__fprintf(struct hist_entry *self,
 547                         struct perf_session *pair_session,
 548                         bool show_displacement,
 549                         long displacement, FILE *fp,
 550                         u64 session_total)
 551 {
 552         char bf[512];
 553         hist_entry__snprintf(self, bf, sizeof(bf), pair_session,
 554                              show_displacement, displacement,
 555                              true, session_total);
 556         return fprintf(fp, "%s\n", bf);
 557 }
 558
 559 static size_t hist_entry__fprintf_callchain(struct hist_entry *self, FILE *fp,
 560                                             u64 session_total)
 561 {
 562         int left_margin = 0;
 563
 564         if (sort__first_dimension == SORT_COMM) {
 565                 struct sort_entry *se = list_first_entry(&hist_entry__sort_list,
 566                                                          typeof(*se), list);
 567                 left_margin = se->se_width ? *se->se_width : 0;
 568                 left_margin -= thread__comm_len(self->thread);
 569         }
 570
 571         return hist_entry_callchain__fprintf(fp, self, session_total,
 572                                              left_margin);
 573 }
 574
 575 size_t perf_session__fprintf_hists(struct rb_root *hists,
 576                                    struct perf_session *pair,
 577                                    bool show_displacement, FILE *fp,
 578                                    u64 session_total)
 579 {
 580         struct sort_entry *se;
 581         struct rb_node *nd;
 582         size_t ret = 0;
 583         unsigned long position = 1;
 584         long displacement = 0;
 585         unsigned int width;
 586         const char *sep = symbol_conf.field_sep;
 587         char *col_width = symbol_conf.col_width_list_str;
 588
 589         init_rem_hits();
 590
 591         fprintf(fp, "# %s", pair ? "Baseline" : "Overhead");
 592
 593         if (symbol_conf.show_nr_samples) {
 594                 if (sep)
 595                         fprintf(fp, "%cSamples", *sep);
 596                 else
 597                         fputs("  Samples  ", fp);
 598         }
 599
 600         if (pair) {
 601                 if (sep)
 602                         ret += fprintf(fp, "%cDelta", *sep);
 603                 else
 604                         ret += fprintf(fp, "  Delta    ");
 605
 606                 if (show_displacement) {
 607                         if (sep)
 608                                 ret += fprintf(fp, "%cDisplacement", *sep);
 609                         else
 610                                 ret += fprintf(fp, " Displ");
 611                 }
 612         }
 613
 614         list_for_each_entry(se, &hist_entry__sort_list, list) {
 615                 if (se->elide)
 616                         continue;
 617                 if (sep) {
 618                         fprintf(fp, "%c%s", *sep, se->se_header);
 619                         continue;
 620                 }
 621                 width = strlen(se->se_header);
 622                 if (se->se_width) {
 623                         if (symbol_conf.col_width_list_str) {
 624                                 if (col_width) {
 625                                         *se->se_width = atoi(col_width);
 626                                         col_width = strchr(col_width, ',');
 627                                         if (col_width)
 628                                                 ++col_width;
 629                                 }
 630                         }
 631                         width = *se->se_width = max(*se->se_width, width);
 632                 }
 633                 fprintf(fp, "  %*s", width, se->se_header);
 634         }
 635         fprintf(fp, "\n");
 636
 637         if (sep)
 638                 goto print_entries;
 639
 640         fprintf(fp, "# ........");
 641         if (symbol_conf.show_nr_samples)
 642                 fprintf(fp, " ..........");
 643         if (pair) {
 644                 fprintf(fp, " ..........");
 645                 if (show_displacement)
 646                         fprintf(fp, " .....");
 647         }
 648         list_for_each_entry(se, &hist_entry__sort_list, list) {
 649                 unsigned int i;
 650
 651                 if (se->elide)
 652                         continue;
 653
 654                 fprintf(fp, "  ");
 655                 if (se->se_width)
 656                         width = *se->se_width;
 657                 else
 658                         width = strlen(se->se_header);
 659                 for (i = 0; i < width; i++)
 660                         fprintf(fp, ".");
 661         }
 662
 663         fprintf(fp, "\n#\n");
 664
 665 print_entries:
 666         for (nd = rb_first(hists); nd; nd = rb_next(nd)) {
 667                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 668
 669                 if (show_displacement) {
 670                         if (h->pair != NULL)
 671                                 displacement = ((long)h->pair->position -
 672                                                 (long)position);
 673                         else
 674                                 displacement = 0;
 675                         ++position;
 676                 }
 677                 ret += hist_entry__fprintf(h, pair, show_displacement,
 678                                            displacement, fp, session_total);
 679
 680                 if (symbol_conf.use_callchain)
 681                         ret += hist_entry__fprintf_callchain(h, fp, session_total);
 682
 683                 if (h->ms.map == NULL && verbose > 1) {
 684                         __map_groups__fprintf_maps(&h->thread->mg,
 685                                                    MAP__FUNCTION, verbose, fp);
 686                         fprintf(fp, "%.10s end\n", graph_dotted_line);
 687                 }
 688         }
 689
 690         free(rem_sq_bracket);
 691
 692         return ret;
 693 }