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(FILE *fp, struct hist_entry *self,
 458                                   struct perf_session *session)
 459 {
 460         struct sort_entry *se;
 461         size_t ret;
 462
 463         if (symbol_conf.exclude_other && !self->parent)
 464                 return 0;
 465
 466         if (session->events_stats.total)
 467                 ret = percent_color_fprintf(fp,
 468                                             symbol_conf.field_sep ? "%.2f" : "   %6.2f%%",
 469                                         (self->count * 100.0) / session->events_stats.total);
 470         else
 471                 ret = fprintf(fp, symbol_conf.field_sep ? "%lld" : "%12lld ", self->count);
 472
 473         if (symbol_conf.show_nr_samples) {
 474                 if (symbol_conf.field_sep)
 475                         fprintf(fp, "%c%lld", *symbol_conf.field_sep, self->count);
 476                 else
 477                         fprintf(fp, "%11lld", self->count);
 478         }
 479
 480         list_for_each_entry(se, &hist_entry__sort_list, list) {
 481                 if (se->elide)
 482                         continue;
 483
 484                 fprintf(fp, "%s", symbol_conf.field_sep ?: "  ");
 485                 ret += se->print(fp, self, se->width ? *se->width : 0);
 486         }
 487
 488         ret += fprintf(fp, "\n");
 489
 490         if (symbol_conf.use_callchain) {
 491                 int left_margin = 0;
 492
 493                 if (sort__first_dimension == SORT_COMM) {
 494                         se = list_first_entry(&hist_entry__sort_list, typeof(*se),
 495                                                 list);
 496                         left_margin = se->width ? *se->width : 0;
 497                         left_margin -= thread__comm_len(self->thread);
 498                 }
 499
 500                 hist_entry_callchain__fprintf(fp, self, session->events_stats.total,
 501                                               left_margin);
 502         }
 503
 504         return ret;
 505 }
 506
 507 size_t perf_session__fprintf_hists(struct perf_session *self, FILE *fp)
 508 {
 509         struct hist_entry *pos;
 510         struct sort_entry *se;
 511         struct rb_node *nd;
 512         size_t ret = 0;
 513         unsigned int width;
 514         char *col_width = symbol_conf.col_width_list_str;
 515
 516         init_rem_hits();
 517
 518         fprintf(fp, "# Overhead");
 519         if (symbol_conf.show_nr_samples) {
 520                 if (symbol_conf.field_sep)
 521                         fprintf(fp, "%cSamples", *symbol_conf.field_sep);
 522                 else
 523                         fputs("  Samples  ", fp);
 524         }
 525         list_for_each_entry(se, &hist_entry__sort_list, list) {
 526                 if (se->elide)
 527                         continue;
 528                 if (symbol_conf.field_sep) {
 529                         fprintf(fp, "%c%s", *symbol_conf.field_sep, se->header);
 530                         continue;
 531                 }
 532                 width = strlen(se->header);
 533                 if (se->width) {
 534                         if (symbol_conf.col_width_list_str) {
 535                                 if (col_width) {
 536                                         *se->width = atoi(col_width);
 537                                         col_width = strchr(col_width, ',');
 538                                         if (col_width)
 539                                                 ++col_width;
 540                                 }
 541                         }
 542                         width = *se->width = max(*se->width, width);
 543                 }
 544                 fprintf(fp, "  %*s", width, se->header);
 545         }
 546         fprintf(fp, "\n");
 547
 548         if (symbol_conf.field_sep)
 549                 goto print_entries;
 550
 551         fprintf(fp, "# ........");
 552         if (symbol_conf.show_nr_samples)
 553                 fprintf(fp, " ..........");
 554         list_for_each_entry(se, &hist_entry__sort_list, list) {
 555                 unsigned int i;
 556
 557                 if (se->elide)
 558                         continue;
 559
 560                 fprintf(fp, "  ");
 561                 if (se->width)
 562                         width = *se->width;
 563                 else
 564                         width = strlen(se->header);
 565                 for (i = 0; i < width; i++)
 566                         fprintf(fp, ".");
 567         }
 568         fprintf(fp, "\n");
 569
 570         fprintf(fp, "#\n");
 571
 572 print_entries:
 573         for (nd = rb_first(&self->hists); nd; nd = rb_next(nd)) {
 574                 pos = rb_entry(nd, struct hist_entry, rb_node);
 575                 ret += hist_entry__fprintf(fp, pos, self);
 576         }
 577
 578         free(rem_sq_bracket);
 579
 580         return ret;
 581 }