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