tools/perf/util/hist.c

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