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