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