1 /*- 2 * Copyright (c) 2009, Fabien Thomas 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 /* 28 * Process hwpmc(4) samples as calltree. 29 * 30 * Output file format compatible with Kcachegrind (kdesdk). 31 * Handle top mode with a sorted tree display. 32 */ 33 34 #include <sys/cdefs.h> 35 __FBSDID("$FreeBSD$"); 36 37 #include <sys/param.h> 38 #include <sys/endian.h> 39 #include <sys/queue.h> 40 41 #include <assert.h> 42 #include <curses.h> 43 #include <ctype.h> 44 #include <err.h> 45 #include <errno.h> 46 #include <fcntl.h> 47 #include <pmc.h> 48 #include <pmclog.h> 49 #include <stdint.h> 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 #include <unistd.h> 54 #include <sysexits.h> 55 56 #include "pmcstat.h" 57 #include "pmcstat_log.h" 58 #include "pmcstat_top.h" 59 #include "pmcpl_calltree.h" 60 61 #define PMCPL_CT_GROWSIZE 4 62 63 static pmcstat_interned_string pmcpl_ct_prevfn; 64 65 static int pmcstat_skiplink = 0; 66 67 struct pmcpl_ct_node; 68 69 /* Get the sample value for PMC a. */ 70 #define PMCPL_CT_SAMPLE(a, b) \ 71 ((a) < (b)->npmcs ? (b)->sb[a] : 0) 72 73 /* Get the sample value in percent related to rsamples. */ 74 #define PMCPL_CT_SAMPLEP(a, b) \ 75 (PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a]) 76 77 struct pmcpl_ct_sample { 78 int npmcs; /* Max pmc index available. */ 79 unsigned *sb; /* Sample buffer for 0..npmcs. */ 80 }; 81 82 struct pmcpl_ct_arc { 83 struct pmcpl_ct_sample pcta_samples; 84 struct pmcpl_ct_sample pcta_callid; 85 unsigned pcta_call; 86 struct pmcpl_ct_node *pcta_child; 87 }; 88 89 struct pmcpl_ct_instr { 90 uintfptr_t pctf_func; 91 struct pmcpl_ct_sample pctf_samples; 92 }; 93 94 /* 95 * Each calltree node is tracked by a pmcpl_ct_node struct. 96 */ 97 struct pmcpl_ct_node { 98 #define PMCPL_PCT_TAG 0x00000001 /* Loop detection. */ 99 uint32_t pct_flags; 100 struct pmcstat_image *pct_image; 101 uintfptr_t pct_func; 102 struct pmcpl_ct_sample pct_samples; 103 104 int pct_narc; 105 int pct_arc_c; 106 struct pmcpl_ct_arc *pct_arc; 107 108 /* TODO: optimize for large number of items. */ 109 int pct_ninstr; 110 int pct_instr_c; 111 struct pmcpl_ct_instr *pct_instr; 112 }; 113 114 struct pmcpl_ct_node_hash { 115 struct pmcpl_ct_node *pch_ctnode; 116 LIST_ENTRY(pmcpl_ct_node_hash) pch_next; 117 }; 118 119 struct pmcpl_ct_sample pmcpl_ct_callid; 120 121 #define PMCPL_CT_MAXCOL PMC_CALLCHAIN_DEPTH_MAX 122 #define PMCPL_CT_MAXLINE 1024 /* TODO: dynamic. */ 123 124 struct pmcpl_ct_line { 125 unsigned ln_sum; 126 unsigned ln_index; 127 }; 128 129 struct pmcpl_ct_line pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1]; 130 struct pmcpl_ct_node *pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1]; 131 132 /* 133 * All nodes indexed by function/image name are placed in a hash table. 134 */ 135 static LIST_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH]; 136 137 /* 138 * Root node for the graph. 139 */ 140 static struct pmcpl_ct_node *pmcpl_ct_root; 141 142 /* 143 * Prototypes 144 */ 145 146 /* 147 * Initialize a samples. 148 */ 149 150 static void 151 pmcpl_ct_samples_init(struct pmcpl_ct_sample *samples) 152 { 153 154 samples->npmcs = 0; 155 samples->sb = NULL; 156 } 157 158 /* 159 * Free a samples. 160 */ 161 162 static void 163 pmcpl_ct_samples_free(struct pmcpl_ct_sample *samples) 164 { 165 166 samples->npmcs = 0; 167 free(samples->sb); 168 samples->sb = NULL; 169 } 170 171 /* 172 * Grow a sample block to store pmcstat_npmcs PMCs. 173 */ 174 175 static void 176 pmcpl_ct_samples_grow(struct pmcpl_ct_sample *samples) 177 { 178 int npmcs; 179 180 /* Enough storage. */ 181 if (pmcstat_npmcs <= samples->npmcs) 182 return; 183 184 npmcs = samples->npmcs + 185 max(pmcstat_npmcs - samples->npmcs, PMCPL_CT_GROWSIZE); 186 samples->sb = realloc(samples->sb, npmcs * sizeof(unsigned)); 187 if (samples->sb == NULL) 188 errx(EX_SOFTWARE, "ERROR: out of memory"); 189 bzero((char *)samples->sb + samples->npmcs * sizeof(unsigned), 190 (npmcs - samples->npmcs) * sizeof(unsigned)); 191 samples->npmcs = npmcs; 192 } 193 194 /* 195 * Compute the sum of all root arcs. 196 */ 197 198 static void 199 pmcpl_ct_samples_root(struct pmcpl_ct_sample *samples) 200 { 201 int i, pmcin; 202 203 pmcpl_ct_samples_init(samples); 204 pmcpl_ct_samples_grow(samples); 205 206 for (i = 0; i < pmcpl_ct_root->pct_narc; i++) 207 for (pmcin = 0; pmcin < pmcstat_npmcs; pmcin++) 208 samples->sb[pmcin] += PMCPL_CT_SAMPLE(pmcin, 209 &pmcpl_ct_root->pct_arc[i].pcta_samples); 210 } 211 212 /* 213 * Grow the arc table. 214 */ 215 216 static void 217 pmcpl_ct_arc_grow(int cursize, int *maxsize, struct pmcpl_ct_arc **items) 218 { 219 int nmaxsize; 220 221 if (cursize < *maxsize) 222 return; 223 224 nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE); 225 *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_arc)); 226 if (*items == NULL) 227 errx(EX_SOFTWARE, "ERROR: out of memory"); 228 bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_arc), 229 (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_arc)); 230 *maxsize = nmaxsize; 231 } 232 233 /* 234 * Grow the instr table. 235 */ 236 237 static void 238 pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items) 239 { 240 int nmaxsize; 241 242 if (cursize < *maxsize) 243 return; 244 245 nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE); 246 *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_instr)); 247 if (*items == NULL) 248 errx(EX_SOFTWARE, "ERROR: out of memory"); 249 bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_instr), 250 (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_instr)); 251 *maxsize = nmaxsize; 252 } 253 254 /* 255 * Add a new instruction sample to given node. 256 */ 257 258 static void 259 pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc) 260 { 261 int i; 262 struct pmcpl_ct_instr *in; 263 264 for (i = 0; i<ct->pct_ninstr; i++) { 265 if (ct->pct_instr[i].pctf_func == pc) { 266 in = &ct->pct_instr[i]; 267 pmcpl_ct_samples_grow(&in->pctf_samples); 268 in->pctf_samples.sb[pmcin]++; 269 return; 270 } 271 } 272 273 pmcpl_ct_instr_grow(ct->pct_ninstr, &ct->pct_instr_c, &ct->pct_instr); 274 in = &ct->pct_instr[ct->pct_ninstr]; 275 in->pctf_func = pc; 276 pmcpl_ct_samples_init(&in->pctf_samples); 277 pmcpl_ct_samples_grow(&in->pctf_samples); 278 in->pctf_samples.sb[pmcin] = 1; 279 ct->pct_ninstr++; 280 } 281 282 /* 283 * Allocate a new node. 284 */ 285 286 static struct pmcpl_ct_node * 287 pmcpl_ct_node_allocate(struct pmcstat_image *image, uintfptr_t pc) 288 { 289 struct pmcpl_ct_node *ct; 290 291 if ((ct = malloc(sizeof(*ct))) == NULL) 292 err(EX_OSERR, "ERROR: Cannot allocate callgraph node"); 293 294 ct->pct_flags = 0; 295 ct->pct_image = image; 296 ct->pct_func = pc; 297 298 pmcpl_ct_samples_init(&ct->pct_samples); 299 300 ct->pct_narc = 0; 301 ct->pct_arc_c = 0; 302 ct->pct_arc = NULL; 303 304 ct->pct_ninstr = 0; 305 ct->pct_instr_c = 0; 306 ct->pct_instr = NULL; 307 308 return (ct); 309 } 310 311 /* 312 * Free a node. 313 */ 314 315 static void 316 pmcpl_ct_node_free(struct pmcpl_ct_node *ct) 317 { 318 int i; 319 320 for (i = 0; i < ct->pct_narc; i++) { 321 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_samples); 322 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_callid); 323 } 324 325 pmcpl_ct_samples_free(&ct->pct_samples); 326 free(ct->pct_arc); 327 free(ct->pct_instr); 328 free(ct); 329 } 330 331 /* 332 * Clear the graph tag on each node. 333 */ 334 static void 335 pmcpl_ct_node_cleartag(void) 336 { 337 int i; 338 struct pmcpl_ct_node_hash *pch; 339 340 for (i = 0; i < PMCSTAT_NHASH; i++) 341 LIST_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next) 342 pch->pch_ctnode->pct_flags &= ~PMCPL_PCT_TAG; 343 344 pmcpl_ct_root->pct_flags &= ~PMCPL_PCT_TAG; 345 } 346 347 /* 348 * Print the callchain line by line with maximum cost at top. 349 */ 350 351 static int 352 pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct, 353 struct pmcpl_ct_sample *rsamples, int x, int *y) 354 { 355 int i, terminal; 356 struct pmcpl_ct_arc *arc; 357 358 if (ct->pct_flags & PMCPL_PCT_TAG) 359 return 0; 360 361 ct->pct_flags |= PMCPL_PCT_TAG; 362 363 if (x >= PMCPL_CT_MAXCOL) { 364 pmcpl_ct_topscreen[x][*y] = NULL; 365 return 1; 366 } 367 pmcpl_ct_topscreen[x][*y] = ct; 368 369 /* 370 * Check if this is a terminal node. 371 * We need to check that some samples exist 372 * for at least one arc for that PMC. 373 */ 374 terminal = 1; 375 for (i = 0; i < ct->pct_narc; i++) { 376 arc = &ct->pct_arc[i]; 377 if (PMCPL_CT_SAMPLE(pmcin, 378 &arc->pcta_samples) != 0 && 379 PMCPL_CT_SAMPLEP(pmcin, 380 &arc->pcta_samples) > pmcstat_threshold && 381 (arc->pcta_child->pct_flags & PMCPL_PCT_TAG) == 0) { 382 terminal = 0; 383 break; 384 } 385 } 386 387 if (ct->pct_narc == 0 || terminal) { 388 pmcpl_ct_topscreen[x+1][*y] = NULL; 389 if (*y >= PMCPL_CT_MAXLINE) 390 return 1; 391 *y = *y + 1; 392 for (i=0; i < x; i++) 393 pmcpl_ct_topscreen[i][*y] = 394 pmcpl_ct_topscreen[i][*y - 1]; 395 return 0; 396 } 397 398 for (i = 0; i < ct->pct_narc; i++) { 399 if (PMCPL_CT_SAMPLE(pmcin, 400 &ct->pct_arc[i].pcta_samples) == 0) 401 continue; 402 if (PMCPL_CT_SAMPLEP(pmcin, 403 &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) { 404 if (pmcpl_ct_node_dumptop(pmcin, 405 ct->pct_arc[i].pcta_child, 406 rsamples, x+1, y)) 407 return 1; 408 } 409 } 410 411 return 0; 412 } 413 414 /* 415 * Compare two top line by sum. 416 */ 417 static int 418 pmcpl_ct_line_compare(const void *a, const void *b) 419 { 420 const struct pmcpl_ct_line *ct1, *ct2; 421 422 ct1 = (const struct pmcpl_ct_line *) a; 423 ct2 = (const struct pmcpl_ct_line *) b; 424 425 /* Sort in reverse order */ 426 if (ct1->ln_sum < ct2->ln_sum) 427 return (1); 428 if (ct1->ln_sum > ct2->ln_sum) 429 return (-1); 430 return (0); 431 } 432 433 /* 434 * Format and display given PMC index. 435 */ 436 437 static void 438 pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy) 439 { 440 #undef TS 441 #undef TSI 442 #define TS(x, y) (pmcpl_ct_topscreen[x][y]) 443 #define TSI(x, y) (pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index]) 444 445 int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y; 446 float v; 447 char ns[30], vs[10], is[20]; 448 struct pmcpl_ct_node *ct; 449 struct pmcstat_symbol *sym; 450 const char *space = " "; 451 452 /* 453 * Sort by line cost. 454 */ 455 for (y = 0; ; y++) { 456 ct = TS(1, y); 457 if (ct == NULL) 458 break; 459 460 pmcpl_ct_topmax[y].ln_sum = 0; 461 pmcpl_ct_topmax[y].ln_index = y; 462 for (x = 1; TS(x, y) != NULL; x++) { 463 pmcpl_ct_topmax[y].ln_sum += 464 PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples); 465 } 466 } 467 qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]), 468 pmcpl_ct_line_compare); 469 pmcpl_ct_topmax[y].ln_index = y; 470 471 for (y = 0; y < maxy; y++) { 472 ct = TSI(1, y); 473 if (ct == NULL) 474 break; 475 476 if (y > 0) 477 PMCSTAT_PRINTW("\n"); 478 479 /* Output sum. */ 480 v = pmcpl_ct_topmax[y].ln_sum * 100.0 / 481 rsamples->sb[pmcin]; 482 snprintf(vs, sizeof(vs), "%.1f", v); 483 v_attrs = PMCSTAT_ATTRPERCENT(v); 484 PMCSTAT_ATTRON(v_attrs); 485 PMCSTAT_PRINTW("%5.5s ", vs); 486 PMCSTAT_ATTROFF(v_attrs); 487 488 width = indentwidth = 5 + 1; 489 490 for (x = 1; (ct = TSI(x, y)) != NULL; x++) { 491 492 vs[0] = '\0'; vs_len = 0; 493 is[0] = '\0'; is_len = 0; 494 495 /* Format value. */ 496 v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples); 497 if (v > pmcstat_threshold) 498 vs_len = snprintf(vs, sizeof(vs), 499 "(%.1f%%)", v); 500 v_attrs = PMCSTAT_ATTRPERCENT(v); 501 502 if (pmcstat_skiplink && v <= pmcstat_threshold) { 503 strlcpy(ns, ".", sizeof(ns)); 504 ns_len = 1; 505 } else { 506 sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func); 507 if (sym != NULL) { 508 ns_len = snprintf(ns, sizeof(ns), "%s", 509 pmcstat_string_unintern(sym->ps_name)); 510 } else 511 ns_len = snprintf(ns, sizeof(ns), "%p", 512 (void *)ct->pct_func); 513 514 /* Format image. */ 515 if (x == 1 || 516 TSI(x-1, y)->pct_image != ct->pct_image) 517 is_len = snprintf(is, sizeof(is), "@%s", 518 pmcstat_string_unintern(ct->pct_image->pi_name)); 519 520 /* Check for line wrap. */ 521 width += ns_len + is_len + vs_len + 1; 522 } 523 if (width >= pmcstat_displaywidth) { 524 maxy--; 525 if (y >= maxy) 526 break; 527 PMCSTAT_PRINTW("\n%*s", indentwidth, space); 528 width = indentwidth + ns_len + is_len + vs_len; 529 } 530 531 PMCSTAT_ATTRON(v_attrs); 532 PMCSTAT_PRINTW("%s%s%s ", ns, is, vs); 533 PMCSTAT_ATTROFF(v_attrs); 534 } 535 } 536 } 537 538 /* 539 * Output top mode snapshot. 540 */ 541 542 void 543 pmcpl_ct_topdisplay(void) 544 { 545 int y; 546 struct pmcpl_ct_sample r, *rsamples; 547 548 rsamples = &r; 549 pmcpl_ct_samples_root(rsamples); 550 551 pmcpl_ct_node_cleartag(); 552 553 PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE"); 554 555 y = 0; 556 if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter, 557 pmcpl_ct_root, rsamples, 0, &y)) 558 PMCSTAT_PRINTW("...\n"); 559 pmcpl_ct_topscreen[1][y] = NULL; 560 561 pmcpl_ct_node_printtop(rsamples, 562 pmcstat_pmcinfilter, pmcstat_displayheight - 2); 563 564 pmcpl_ct_samples_free(rsamples); 565 } 566 567 /* 568 * Handle top mode keypress. 569 */ 570 571 int 572 pmcpl_ct_topkeypress(int c, WINDOW *w) 573 { 574 575 switch (c) { 576 case 'f': 577 pmcstat_skiplink = !pmcstat_skiplink; 578 wprintw(w, "skip empty link %s", 579 pmcstat_skiplink ? "on" : "off"); 580 break; 581 } 582 583 return 0; 584 } 585 586 /* 587 * Look for a callgraph node associated with pmc `pmcid' in the global 588 * hash table that corresponds to the given `pc' value in the process map 589 * `ppm'. 590 */ 591 592 static struct pmcpl_ct_node * 593 pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent, 594 struct pmcstat_pcmap *ppm, uintfptr_t pc, int pmcin) 595 { 596 struct pmcstat_symbol *sym; 597 struct pmcstat_image *image; 598 struct pmcpl_ct_node *ct; 599 struct pmcpl_ct_node_hash *h; 600 struct pmcpl_ct_arc *arc; 601 uintfptr_t loadaddress; 602 int i; 603 unsigned int hash; 604 605 assert(parent != NULL); 606 607 image = ppm->ppm_image; 608 609 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start; 610 pc -= loadaddress; /* Convert to an offset in the image. */ 611 612 /* 613 * Try determine the function at this offset. If we can't 614 * find a function round leave the `pc' value alone. 615 */ 616 if ((sym = pmcstat_symbol_search(image, pc)) != NULL) 617 pc = sym->ps_start; 618 else 619 pmcstat_stats.ps_samples_unknown_function++; 620 621 for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++) 622 hash += (pc >> i) & 0xFF; 623 624 hash &= PMCSTAT_HASH_MASK; 625 626 ct = NULL; 627 LIST_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) { 628 ct = h->pch_ctnode; 629 630 assert(ct != NULL); 631 632 if (ct->pct_image == image && ct->pct_func == pc) { 633 /* 634 * Find related arc in parent node and 635 * increment the sample count. 636 */ 637 for (i = 0; i < parent->pct_narc; i++) { 638 if (parent->pct_arc[i].pcta_child == ct) { 639 arc = &parent->pct_arc[i]; 640 pmcpl_ct_samples_grow(&arc->pcta_samples); 641 arc->pcta_samples.sb[pmcin]++; 642 /* Estimate call count. */ 643 pmcpl_ct_samples_grow(&arc->pcta_callid); 644 if (pmcpl_ct_callid.sb[pmcin] - 645 arc->pcta_callid.sb[pmcin] > 1) 646 arc->pcta_call++; 647 arc->pcta_callid.sb[pmcin] = 648 pmcpl_ct_callid.sb[pmcin]; 649 return (ct); 650 } 651 } 652 653 /* 654 * No arc found for us, add ourself to the parent. 655 */ 656 pmcpl_ct_arc_grow(parent->pct_narc, 657 &parent->pct_arc_c, &parent->pct_arc); 658 arc = &parent->pct_arc[parent->pct_narc]; 659 pmcpl_ct_samples_grow(&arc->pcta_samples); 660 arc->pcta_samples.sb[pmcin] = 1; 661 arc->pcta_call = 1; 662 pmcpl_ct_samples_grow(&arc->pcta_callid); 663 arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin]; 664 arc->pcta_child = ct; 665 parent->pct_narc++; 666 return (ct); 667 } 668 } 669 670 /* 671 * We haven't seen this (pmcid, pc) tuple yet, so allocate a 672 * new callgraph node and a new hash table entry for it. 673 */ 674 ct = pmcpl_ct_node_allocate(image, pc); 675 if ((h = malloc(sizeof(*h))) == NULL) 676 err(EX_OSERR, "ERROR: Could not allocate callgraph node"); 677 678 h->pch_ctnode = ct; 679 LIST_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next); 680 681 pmcpl_ct_arc_grow(parent->pct_narc, 682 &parent->pct_arc_c, &parent->pct_arc); 683 arc = &parent->pct_arc[parent->pct_narc]; 684 pmcpl_ct_samples_grow(&arc->pcta_samples); 685 arc->pcta_samples.sb[pmcin] = 1; 686 arc->pcta_call = 1; 687 pmcpl_ct_samples_grow(&arc->pcta_callid); 688 arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin]; 689 arc->pcta_child = ct; 690 parent->pct_narc++; 691 return (ct); 692 } 693 694 /* 695 * Record a callchain. 696 */ 697 698 void 699 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr, 700 uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu) 701 { 702 int n, pmcin; 703 struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX]; 704 struct pmcstat_process *km; 705 struct pmcpl_ct_node *parent, *child; 706 707 (void) cpu; 708 709 assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX); 710 711 /* Get the PMC index. */ 712 pmcin = pmcr->pr_pmcin; 713 714 /* 715 * Validate mapping for the callchain. 716 * Go from bottom to first invalid entry. 717 */ 718 km = pmcstat_kernproc; 719 for (n = 0; n < (int)nsamples; n++) { 720 ppm[n] = pmcstat_process_find_map(usermode ? 721 pp : km, cc[n]); 722 if (ppm[n] == NULL) { 723 /* Detect full frame capture (kernel + user). */ 724 if (!usermode) { 725 ppm[n] = pmcstat_process_find_map(pp, cc[n]); 726 if (ppm[n] != NULL) 727 km = pp; 728 } 729 } 730 if (ppm[n] == NULL) 731 break; 732 } 733 if (n-- == 0) { 734 pmcstat_stats.ps_callchain_dubious_frames++; 735 pmcr->pr_dubious_frames++; 736 return; 737 } 738 739 /* Increase the call generation counter. */ 740 pmcpl_ct_samples_grow(&pmcpl_ct_callid); 741 pmcpl_ct_callid.sb[pmcin]++; 742 743 /* 744 * Iterate remaining addresses. 745 */ 746 for (parent = pmcpl_ct_root, child = NULL; n >= 0; n--) { 747 child = pmcpl_ct_node_hash_lookup_pc(parent, ppm[n], cc[n], 748 pmcin); 749 if (child == NULL) { 750 pmcstat_stats.ps_callchain_dubious_frames++; 751 continue; 752 } 753 parent = child; 754 } 755 756 /* 757 * Increment the sample count for this PMC. 758 */ 759 if (child != NULL) { 760 pmcpl_ct_samples_grow(&child->pct_samples); 761 child->pct_samples.sb[pmcin]++; 762 763 /* Update per instruction sample if required. */ 764 if (args.pa_ctdumpinstr) 765 pmcpl_ct_instr_add(child, pmcin, cc[0] - 766 (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr - 767 ppm[0]->ppm_image->pi_start)); 768 } 769 } 770 771 /* 772 * Print node self cost. 773 */ 774 775 static void 776 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct) 777 { 778 int i, j, line; 779 uintptr_t addr; 780 struct pmcstat_symbol *sym; 781 char sourcefile[PATH_MAX]; 782 char funcname[PATH_MAX]; 783 784 /* 785 * Object binary. 786 */ 787 #ifdef PMCPL_CT_OPTIMIZEFN 788 if (pmcpl_ct_prevfn != ct->pct_image->pi_fullpath) { 789 #endif 790 pmcpl_ct_prevfn = ct->pct_image->pi_fullpath; 791 fprintf(args.pa_graphfile, "ob=%s\n", 792 pmcstat_string_unintern(pmcpl_ct_prevfn)); 793 #ifdef PMCPL_CT_OPTIMIZEFN 794 } 795 #endif 796 797 /* 798 * Function name. 799 */ 800 if (pmcstat_image_addr2line(ct->pct_image, ct->pct_func, 801 sourcefile, sizeof(sourcefile), &line, 802 funcname, sizeof(funcname))) { 803 fprintf(args.pa_graphfile, "fn=%s\n", 804 funcname); 805 } else { 806 sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func); 807 if (sym != NULL) 808 fprintf(args.pa_graphfile, "fn=%s\n", 809 pmcstat_string_unintern(sym->ps_name)); 810 else 811 fprintf(args.pa_graphfile, "fn=%p\n", 812 (void *)(ct->pct_image->pi_vaddr + ct->pct_func)); 813 } 814 815 /* 816 * Self cost. 817 */ 818 if (ct->pct_ninstr > 0) { 819 for (i = 0; i < ct->pct_ninstr; i++) { 820 addr = ct->pct_image->pi_vaddr + 821 ct->pct_instr[i].pctf_func; 822 line = 0; 823 if (pmcstat_image_addr2line(ct->pct_image, addr, 824 sourcefile, sizeof(sourcefile), &line, 825 funcname, sizeof(funcname))) 826 fprintf(args.pa_graphfile, "fl=%s\n", sourcefile); 827 fprintf(args.pa_graphfile, "%p %u", (void *)addr, line); 828 for (j = 0; j<pmcstat_npmcs; j++) 829 fprintf(args.pa_graphfile, " %u", 830 PMCPL_CT_SAMPLE(j, 831 &ct->pct_instr[i].pctf_samples)); 832 fprintf(args.pa_graphfile, "\n"); 833 } 834 } else { 835 addr = ct->pct_image->pi_vaddr + ct->pct_func; 836 line = 0; 837 if (pmcstat_image_addr2line(ct->pct_image, addr, 838 sourcefile, sizeof(sourcefile), &line, 839 funcname, sizeof(funcname))) 840 fprintf(args.pa_graphfile, "fl=%s\n", sourcefile); 841 fprintf(args.pa_graphfile, "* *"); 842 for (i = 0; i<pmcstat_npmcs ; i++) 843 fprintf(args.pa_graphfile, " %u", 844 PMCPL_CT_SAMPLE(i, &ct->pct_samples)); 845 fprintf(args.pa_graphfile, "\n"); 846 } 847 } 848 849 /* 850 * Print node child cost. 851 */ 852 853 static void 854 pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct) 855 { 856 int i, j, line; 857 uintptr_t addr; 858 struct pmcstat_symbol *sym; 859 struct pmcpl_ct_node *child; 860 char sourcefile[PATH_MAX]; 861 char funcname[PATH_MAX]; 862 863 /* 864 * Child cost. 865 * TODO: attach child cost to the real position in the function. 866 * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost> 867 */ 868 for (i=0 ; i<ct->pct_narc; i++) { 869 child = ct->pct_arc[i].pcta_child; 870 871 /* Object binary. */ 872 #ifdef PMCPL_CT_OPTIMIZEFN 873 if (pmcpl_ct_prevfn != child->pct_image->pi_fullpath) { 874 #endif 875 pmcpl_ct_prevfn = child->pct_image->pi_fullpath; 876 fprintf(args.pa_graphfile, "cob=%s\n", 877 pmcstat_string_unintern(pmcpl_ct_prevfn)); 878 #if PMCPL_CT_OPTIMIZEFN 879 } 880 #endif 881 /* Child function name. */ 882 addr = child->pct_image->pi_vaddr + child->pct_func; 883 /* Child function source file. */ 884 if (pmcstat_image_addr2line(child->pct_image, addr, 885 sourcefile, sizeof(sourcefile), &line, 886 funcname, sizeof(funcname))) { 887 fprintf(args.pa_graphfile, "cfn=%s\n", funcname); 888 fprintf(args.pa_graphfile, "cfl=%s\n", sourcefile); 889 } else { 890 sym = pmcstat_symbol_search(child->pct_image, 891 child->pct_func); 892 if (sym != NULL) 893 fprintf(args.pa_graphfile, "cfn=%s\n", 894 pmcstat_string_unintern(sym->ps_name)); 895 else 896 fprintf(args.pa_graphfile, "cfn=%p\n", (void *)addr); 897 } 898 899 /* Child function address, line and call count. */ 900 fprintf(args.pa_graphfile, "calls=%u %p %u\n", 901 ct->pct_arc[i].pcta_call, (void *)addr, line); 902 903 if (ct->pct_image != NULL) { 904 /* Call address, line, sample. */ 905 addr = ct->pct_image->pi_vaddr + ct->pct_func; 906 line = 0; 907 if (pmcstat_image_addr2line(ct->pct_image, addr, sourcefile, 908 sizeof(sourcefile), &line, 909 funcname, sizeof(funcname))) 910 fprintf(args.pa_graphfile, "%p %u", (void *)addr, line); 911 else 912 fprintf(args.pa_graphfile, "* *"); 913 } 914 else 915 fprintf(args.pa_graphfile, "* *"); 916 for (j = 0; j<pmcstat_npmcs; j++) 917 fprintf(args.pa_graphfile, " %u", 918 PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples)); 919 fprintf(args.pa_graphfile, "\n"); 920 } 921 } 922 923 /* 924 * Clean the PMC name for Kcachegrind formula 925 */ 926 927 static void 928 pmcpl_ct_fixup_pmcname(char *s) 929 { 930 char *p; 931 932 for (p = s; *p; p++) 933 if (!isalnum(*p)) 934 *p = '_'; 935 } 936 937 /* 938 * Print a calltree (KCachegrind) for all PMCs. 939 */ 940 941 static void 942 pmcpl_ct_print(void) 943 { 944 int n, i; 945 struct pmcpl_ct_node_hash *pch; 946 struct pmcpl_ct_sample rsamples; 947 char name[40]; 948 949 pmcpl_ct_samples_root(&rsamples); 950 pmcpl_ct_prevfn = NULL; 951 952 fprintf(args.pa_graphfile, 953 "version: 1\n" 954 "creator: pmcstat\n" 955 "positions: instr line\n" 956 "events:"); 957 for (i=0; i<pmcstat_npmcs; i++) { 958 snprintf(name, sizeof(name), "%s_%d", 959 pmcstat_pmcindex_to_name(i), i); 960 pmcpl_ct_fixup_pmcname(name); 961 fprintf(args.pa_graphfile, " %s", name); 962 } 963 fprintf(args.pa_graphfile, "\nsummary:"); 964 for (i=0; i<pmcstat_npmcs ; i++) 965 fprintf(args.pa_graphfile, " %u", 966 PMCPL_CT_SAMPLE(i, &rsamples)); 967 fprintf(args.pa_graphfile, "\n\n"); 968 969 /* 970 * Fake root node 971 */ 972 fprintf(args.pa_graphfile, "ob=FreeBSD\n"); 973 fprintf(args.pa_graphfile, "fn=ROOT\n"); 974 fprintf(args.pa_graphfile, "* *"); 975 for (i = 0; i<pmcstat_npmcs ; i++) 976 fprintf(args.pa_graphfile, " 0"); 977 fprintf(args.pa_graphfile, "\n"); 978 pmcpl_ct_node_printchild(pmcpl_ct_root); 979 980 for (n = 0; n < PMCSTAT_NHASH; n++) 981 LIST_FOREACH(pch, &pmcpl_ct_node_hash[n], pch_next) { 982 pmcpl_ct_node_printself(pch->pch_ctnode); 983 pmcpl_ct_node_printchild(pch->pch_ctnode); 984 } 985 986 pmcpl_ct_samples_free(&rsamples); 987 } 988 989 int 990 pmcpl_ct_configure(char *opt) 991 { 992 993 if (strncmp(opt, "skiplink=", 9) == 0) { 994 pmcstat_skiplink = atoi(opt+9); 995 } else 996 return (0); 997 998 return (1); 999 } 1000 1001 int 1002 pmcpl_ct_init(void) 1003 { 1004 int i; 1005 1006 pmcpl_ct_prevfn = NULL; 1007 pmcpl_ct_root = pmcpl_ct_node_allocate(NULL, 0); 1008 1009 for (i = 0; i < PMCSTAT_NHASH; i++) 1010 LIST_INIT(&pmcpl_ct_node_hash[i]); 1011 1012 pmcpl_ct_samples_init(&pmcpl_ct_callid); 1013 1014 return (0); 1015 } 1016 1017 void 1018 pmcpl_ct_shutdown(FILE *mf) 1019 { 1020 int i; 1021 struct pmcpl_ct_node_hash *pch, *pchtmp; 1022 1023 (void) mf; 1024 1025 if (args.pa_flags & FLAG_DO_CALLGRAPHS) 1026 pmcpl_ct_print(); 1027 1028 /* 1029 * Free memory. 1030 */ 1031 1032 for (i = 0; i < PMCSTAT_NHASH; i++) { 1033 LIST_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next, 1034 pchtmp) { 1035 pmcpl_ct_node_free(pch->pch_ctnode); 1036 free(pch); 1037 } 1038 } 1039 1040 pmcpl_ct_node_free(pmcpl_ct_root); 1041 pmcpl_ct_root = NULL; 1042 1043 pmcpl_ct_samples_free(&pmcpl_ct_callid); 1044 } 1045 1046