1 /*- 2 * Copyright (c) 2005-2007, Joseph Koshy 3 * Copyright (c) 2007 The FreeBSD Foundation 4 * All rights reserved. 5 * 6 * Portions of this software were developed by A. Joseph Koshy under 7 * sponsorship from the FreeBSD Foundation and Google, Inc. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31 /* 32 * Transform a hwpmc(4) log into human readable form, and into 33 * gprof(1) compatible profiles. 34 */ 35 36 #include <sys/cdefs.h> 37 __FBSDID("$FreeBSD$"); 38 39 #include <sys/param.h> 40 #include <sys/endian.h> 41 #include <sys/gmon.h> 42 #include <sys/imgact_aout.h> 43 #include <sys/imgact_elf.h> 44 #include <sys/mman.h> 45 #include <sys/pmc.h> 46 #include <sys/queue.h> 47 #include <sys/socket.h> 48 #include <sys/stat.h> 49 #include <sys/wait.h> 50 51 #include <netinet/in.h> 52 53 #include <assert.h> 54 #include <curses.h> 55 #include <err.h> 56 #include <errno.h> 57 #include <fcntl.h> 58 #include <gelf.h> 59 #include <libgen.h> 60 #include <limits.h> 61 #include <netdb.h> 62 #include <pmc.h> 63 #include <pmclog.h> 64 #include <sysexits.h> 65 #include <stdint.h> 66 #include <stdio.h> 67 #include <stdlib.h> 68 #include <string.h> 69 #include <unistd.h> 70 71 #include "pmcstat.h" 72 #include "pmcstat_log.h" 73 #include "pmcstat_top.h" 74 #include "pmcpl_callgraph.h" 75 76 /* Get the sample value in percent related to nsamples. */ 77 #define PMCPL_CG_COUNTP(a) \ 78 ((a)->pcg_count * 100.0 / nsamples) 79 80 /* 81 * The toplevel CG nodes (i.e., with rank == 0) are placed in a hash table. 82 */ 83 84 struct pmcstat_cgnode_hash_list pmcstat_cgnode_hash[PMCSTAT_NHASH]; 85 int pmcstat_cgnode_hash_count; 86 87 static pmcstat_interned_string pmcstat_previous_filename_printed; 88 89 static struct pmcstat_cgnode * 90 pmcstat_cgnode_allocate(struct pmcstat_image *image, uintfptr_t pc) 91 { 92 struct pmcstat_cgnode *cg; 93 94 if ((cg = malloc(sizeof(*cg))) == NULL) 95 err(EX_OSERR, "ERROR: Cannot allocate callgraph node"); 96 97 cg->pcg_image = image; 98 cg->pcg_func = pc; 99 100 cg->pcg_count = 0; 101 cg->pcg_nchildren = 0; 102 LIST_INIT(&cg->pcg_children); 103 104 return (cg); 105 } 106 107 /* 108 * Free a node and its children. 109 */ 110 static void 111 pmcstat_cgnode_free(struct pmcstat_cgnode *cg) 112 { 113 struct pmcstat_cgnode *cgc, *cgtmp; 114 115 LIST_FOREACH_SAFE(cgc, &cg->pcg_children, pcg_sibling, cgtmp) 116 pmcstat_cgnode_free(cgc); 117 free(cg); 118 } 119 120 /* 121 * Look for a callgraph node associated with pmc `pmcid' in the global 122 * hash table that corresponds to the given `pc' value in the process 123 * `pp'. 124 */ 125 static struct pmcstat_cgnode * 126 pmcstat_cgnode_hash_lookup_pc(struct pmcstat_process *pp, pmc_id_t pmcid, 127 uintfptr_t pc, int usermode) 128 { 129 struct pmcstat_pcmap *ppm; 130 struct pmcstat_symbol *sym; 131 struct pmcstat_image *image; 132 struct pmcstat_cgnode *cg; 133 struct pmcstat_cgnode_hash *h; 134 uintfptr_t loadaddress; 135 unsigned int i, hash; 136 137 ppm = pmcstat_process_find_map(usermode ? pp : pmcstat_kernproc, pc); 138 if (ppm == NULL) 139 return (NULL); 140 141 image = ppm->ppm_image; 142 143 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start; 144 pc -= loadaddress; /* Convert to an offset in the image. */ 145 146 /* 147 * Try determine the function at this offset. If we can't 148 * find a function round leave the `pc' value alone. 149 */ 150 if ((sym = pmcstat_symbol_search(image, pc)) != NULL) 151 pc = sym->ps_start; 152 153 for (hash = i = 0; i < sizeof(uintfptr_t); i++) 154 hash += (pc >> i) & 0xFF; 155 156 hash &= PMCSTAT_HASH_MASK; 157 158 cg = NULL; 159 LIST_FOREACH(h, &pmcstat_cgnode_hash[hash], pch_next) 160 { 161 if (h->pch_pmcid != pmcid) 162 continue; 163 164 cg = h->pch_cgnode; 165 166 assert(cg != NULL); 167 168 if (cg->pcg_image == image && cg->pcg_func == pc) 169 return (cg); 170 } 171 172 /* 173 * We haven't seen this (pmcid, pc) tuple yet, so allocate a 174 * new callgraph node and a new hash table entry for it. 175 */ 176 cg = pmcstat_cgnode_allocate(image, pc); 177 if ((h = malloc(sizeof(*h))) == NULL) 178 err(EX_OSERR, "ERROR: Could not allocate callgraph node"); 179 180 h->pch_pmcid = pmcid; 181 h->pch_cgnode = cg; 182 LIST_INSERT_HEAD(&pmcstat_cgnode_hash[hash], h, pch_next); 183 184 pmcstat_cgnode_hash_count++; 185 186 return (cg); 187 } 188 189 /* 190 * Compare two callgraph nodes for sorting. 191 */ 192 static int 193 pmcstat_cgnode_compare(const void *a, const void *b) 194 { 195 const struct pmcstat_cgnode *const *pcg1, *const *pcg2, *cg1, *cg2; 196 197 pcg1 = (const struct pmcstat_cgnode *const *) a; 198 cg1 = *pcg1; 199 pcg2 = (const struct pmcstat_cgnode *const *) b; 200 cg2 = *pcg2; 201 202 /* Sort in reverse order */ 203 if (cg1->pcg_count < cg2->pcg_count) 204 return (1); 205 if (cg1->pcg_count > cg2->pcg_count) 206 return (-1); 207 return (0); 208 } 209 210 /* 211 * Find (allocating if a needed) a callgraph node in the given 212 * parent with the same (image, pcoffset) pair. 213 */ 214 215 static struct pmcstat_cgnode * 216 pmcstat_cgnode_find(struct pmcstat_cgnode *parent, struct pmcstat_image *image, 217 uintfptr_t pcoffset) 218 { 219 struct pmcstat_cgnode *child; 220 221 LIST_FOREACH(child, &parent->pcg_children, pcg_sibling) { 222 if (child->pcg_image == image && 223 child->pcg_func == pcoffset) 224 return (child); 225 } 226 227 /* 228 * Allocate a new structure. 229 */ 230 231 child = pmcstat_cgnode_allocate(image, pcoffset); 232 233 /* 234 * Link it into the parent. 235 */ 236 LIST_INSERT_HEAD(&parent->pcg_children, child, pcg_sibling); 237 parent->pcg_nchildren++; 238 239 return (child); 240 } 241 242 /* 243 * Print one callgraph node. The output format is: 244 * 245 * indentation %(parent's samples) #nsamples function@object 246 */ 247 static void 248 pmcstat_cgnode_print(struct pmcstat_cgnode *cg, int depth, uint32_t total) 249 { 250 uint32_t n; 251 const char *space; 252 struct pmcstat_symbol *sym; 253 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg; 254 255 space = " "; 256 257 if (depth > 0) 258 (void) fprintf(args.pa_graphfile, "%*s", depth, space); 259 260 if (cg->pcg_count == total) 261 (void) fprintf(args.pa_graphfile, "100.0%% "); 262 else 263 (void) fprintf(args.pa_graphfile, "%05.2f%% ", 264 100.0 * cg->pcg_count / total); 265 266 n = fprintf(args.pa_graphfile, " [%u] ", cg->pcg_count); 267 268 /* #samples is a 12 character wide field. */ 269 if (n < 12) 270 (void) fprintf(args.pa_graphfile, "%*s", 12 - n, space); 271 272 if (depth > 0) 273 (void) fprintf(args.pa_graphfile, "%*s", depth, space); 274 275 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func); 276 if (sym) 277 (void) fprintf(args.pa_graphfile, "%s", 278 pmcstat_string_unintern(sym->ps_name)); 279 else 280 (void) fprintf(args.pa_graphfile, "%p", 281 (void *) (cg->pcg_image->pi_vaddr + cg->pcg_func)); 282 283 if (pmcstat_previous_filename_printed != 284 cg->pcg_image->pi_fullpath) { 285 pmcstat_previous_filename_printed = cg->pcg_image->pi_fullpath; 286 (void) fprintf(args.pa_graphfile, " @ %s\n", 287 pmcstat_string_unintern( 288 pmcstat_previous_filename_printed)); 289 } else 290 (void) fprintf(args.pa_graphfile, "\n"); 291 292 if (cg->pcg_nchildren == 0) 293 return; 294 295 if ((sortbuffer = (struct pmcstat_cgnode **) 296 malloc(sizeof(struct pmcstat_cgnode *) * 297 cg->pcg_nchildren)) == NULL) 298 err(EX_OSERR, "ERROR: Cannot print callgraph"); 299 cgn = sortbuffer; 300 301 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling) 302 *cgn++ = pcg; 303 304 assert(cgn - sortbuffer == (int) cg->pcg_nchildren); 305 306 qsort(sortbuffer, cg->pcg_nchildren, sizeof(struct pmcstat_cgnode *), 307 pmcstat_cgnode_compare); 308 309 for (cgn = sortbuffer, n = 0; n < cg->pcg_nchildren; n++, cgn++) 310 pmcstat_cgnode_print(*cgn, depth+1, cg->pcg_count); 311 312 free(sortbuffer); 313 } 314 315 /* 316 * Record a callchain. 317 */ 318 319 void 320 pmcpl_cg_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr, 321 uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu) 322 { 323 uintfptr_t pc, loadaddress; 324 uint32_t n; 325 struct pmcstat_image *image; 326 struct pmcstat_pcmap *ppm; 327 struct pmcstat_symbol *sym; 328 struct pmcstat_cgnode *parent, *child; 329 struct pmcstat_process *km; 330 pmc_id_t pmcid; 331 332 (void) cpu; 333 334 /* 335 * Find the callgraph node recorded in the global hash table 336 * for this (pmcid, pc). 337 */ 338 339 pc = cc[0]; 340 pmcid = pmcr->pr_pmcid; 341 parent = pmcstat_cgnode_hash_lookup_pc(pp, pmcid, pc, usermode); 342 if (parent == NULL) { 343 pmcstat_stats.ps_callchain_dubious_frames++; 344 return; 345 } 346 347 parent->pcg_count++; 348 349 /* 350 * For each return address in the call chain record, subject 351 * to the maximum depth desired. 352 * - Find the image associated with the sample. Stop if there 353 * there is no valid image at that address. 354 * - Find the function that overlaps the return address. 355 * - If found: use the start address of the function. 356 * If not found (say an object's symbol table is not present or 357 * is incomplete), round down to th gprof bucket granularity. 358 * - Convert return virtual address to an offset in the image. 359 * - Look for a child with the same {offset,image} tuple, 360 * inserting one if needed. 361 * - Increment the count of occurrences of the child. 362 */ 363 km = pmcstat_kernproc; 364 365 for (n = 1; n < (uint32_t) args.pa_graphdepth && n < nsamples; n++, 366 parent = child) { 367 pc = cc[n]; 368 369 ppm = pmcstat_process_find_map(usermode ? pp : km, pc); 370 if (ppm == NULL) { 371 /* Detect full frame capture (kernel + user). */ 372 if (!usermode) { 373 ppm = pmcstat_process_find_map(pp, pc); 374 if (ppm != NULL) 375 km = pp; 376 } 377 } 378 if (ppm == NULL) 379 return; 380 381 image = ppm->ppm_image; 382 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - 383 image->pi_start; 384 pc -= loadaddress; 385 386 if ((sym = pmcstat_symbol_search(image, pc)) != NULL) 387 pc = sym->ps_start; 388 389 child = pmcstat_cgnode_find(parent, image, pc); 390 child->pcg_count++; 391 } 392 } 393 394 /* 395 * Printing a callgraph for a PMC. 396 */ 397 static void 398 pmcstat_callgraph_print_for_pmcid(struct pmcstat_pmcrecord *pmcr) 399 { 400 int n, nentries; 401 uint32_t nsamples; 402 pmc_id_t pmcid; 403 struct pmcstat_cgnode **sortbuffer, **cgn; 404 struct pmcstat_cgnode_hash *pch; 405 406 /* 407 * We pull out all callgraph nodes in the top-level hash table 408 * with a matching PMC id. We then sort these based on the 409 * frequency of occurrence. Each callgraph node is then 410 * printed. 411 */ 412 413 nsamples = 0; 414 pmcid = pmcr->pr_pmcid; 415 if ((sortbuffer = (struct pmcstat_cgnode **) 416 malloc(sizeof(struct pmcstat_cgnode *) * 417 pmcstat_cgnode_hash_count)) == NULL) 418 err(EX_OSERR, "ERROR: Cannot sort callgraph"); 419 cgn = sortbuffer; 420 421 for (n = 0; n < PMCSTAT_NHASH; n++) 422 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next) 423 if (pch->pch_pmcid == pmcid) { 424 nsamples += pch->pch_cgnode->pcg_count; 425 *cgn++ = pch->pch_cgnode; 426 } 427 428 nentries = cgn - sortbuffer; 429 assert(nentries <= pmcstat_cgnode_hash_count); 430 431 if (nentries == 0) { 432 free(sortbuffer); 433 return; 434 } 435 436 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *), 437 pmcstat_cgnode_compare); 438 439 (void) fprintf(args.pa_graphfile, 440 "@ %s [%u samples]\n\n", 441 pmcstat_string_unintern(pmcr->pr_pmcname), 442 nsamples); 443 444 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) { 445 pmcstat_previous_filename_printed = NULL; 446 pmcstat_cgnode_print(*cgn, 0, nsamples); 447 (void) fprintf(args.pa_graphfile, "\n"); 448 } 449 450 free(sortbuffer); 451 } 452 453 /* 454 * Print out callgraphs. 455 */ 456 457 static void 458 pmcstat_callgraph_print(void) 459 { 460 struct pmcstat_pmcrecord *pmcr; 461 462 LIST_FOREACH(pmcr, &pmcstat_pmcs, pr_next) 463 pmcstat_callgraph_print_for_pmcid(pmcr); 464 } 465 466 static void 467 pmcstat_cgnode_topprint(struct pmcstat_cgnode *cg, 468 int depth, uint32_t nsamples) 469 { 470 int v_attrs, vs_len, ns_len, width, len, n, nchildren; 471 float v; 472 char ns[30], vs[10]; 473 struct pmcstat_symbol *sym; 474 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg; 475 476 (void) depth; 477 478 /* Format value. */ 479 v = PMCPL_CG_COUNTP(cg); 480 snprintf(vs, sizeof(vs), "%.1f", v); 481 v_attrs = PMCSTAT_ATTRPERCENT(v); 482 483 /* Format name. */ 484 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func); 485 if (sym != NULL) { 486 snprintf(ns, sizeof(ns), "%s", 487 pmcstat_string_unintern(sym->ps_name)); 488 } else 489 snprintf(ns, sizeof(ns), "%p", 490 (void *)cg->pcg_func); 491 492 PMCSTAT_ATTRON(v_attrs); 493 PMCSTAT_PRINTW("%5.5s", vs); 494 PMCSTAT_ATTROFF(v_attrs); 495 PMCSTAT_PRINTW(" %-10.10s %-20.20s", 496 pmcstat_string_unintern(cg->pcg_image->pi_name), 497 ns); 498 499 nchildren = cg->pcg_nchildren; 500 if (nchildren == 0) { 501 PMCSTAT_PRINTW("\n"); 502 return; 503 } 504 505 width = pmcstat_displaywidth - 40; 506 507 if ((sortbuffer = (struct pmcstat_cgnode **) 508 malloc(sizeof(struct pmcstat_cgnode *) * 509 nchildren)) == NULL) 510 err(EX_OSERR, "ERROR: Cannot print callgraph"); 511 cgn = sortbuffer; 512 513 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling) 514 *cgn++ = pcg; 515 516 assert(cgn - sortbuffer == (int)nchildren); 517 518 qsort(sortbuffer, nchildren, sizeof(struct pmcstat_cgnode *), 519 pmcstat_cgnode_compare); 520 521 /* Count how many callers. */ 522 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) { 523 pcg = *cgn; 524 525 v = PMCPL_CG_COUNTP(pcg); 526 if (v < pmcstat_threshold) 527 break; 528 } 529 nchildren = n; 530 531 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) { 532 pcg = *cgn; 533 534 /* Format value. */ 535 if (nchildren > 1) { 536 v = PMCPL_CG_COUNTP(pcg); 537 vs_len = snprintf(vs, sizeof(vs), ":%.1f", v); 538 v_attrs = PMCSTAT_ATTRPERCENT(v); 539 } else 540 vs_len = 0; 541 542 /* Format name. */ 543 sym = pmcstat_symbol_search(pcg->pcg_image, pcg->pcg_func); 544 if (sym != NULL) { 545 ns_len = snprintf(ns, sizeof(ns), "%s", 546 pmcstat_string_unintern(sym->ps_name)); 547 } else 548 ns_len = snprintf(ns, sizeof(ns), "%p", 549 (void *)pcg->pcg_func); 550 551 len = ns_len + vs_len + 1; 552 if (width - len < 0) { 553 PMCSTAT_PRINTW("..."); 554 break; 555 } 556 width -= len; 557 558 PMCSTAT_PRINTW(" %s", ns); 559 if (nchildren > 1) { 560 PMCSTAT_ATTRON(v_attrs); 561 PMCSTAT_PRINTW("%s", vs); 562 PMCSTAT_ATTROFF(v_attrs); 563 } 564 } 565 PMCSTAT_PRINTW("\n"); 566 free(sortbuffer); 567 } 568 569 /* 570 * Top mode display. 571 */ 572 573 void 574 pmcpl_cg_topdisplay(void) 575 { 576 int n, nentries; 577 uint32_t nsamples; 578 struct pmcstat_cgnode **sortbuffer, **cgn; 579 struct pmcstat_cgnode_hash *pch; 580 struct pmcstat_pmcrecord *pmcr; 581 582 pmcr = pmcstat_pmcindex_to_pmcr(pmcstat_pmcinfilter); 583 584 /* 585 * We pull out all callgraph nodes in the top-level hash table 586 * with a matching PMC index. We then sort these based on the 587 * frequency of occurrence. Each callgraph node is then 588 * printed. 589 */ 590 591 nsamples = 0; 592 593 if ((sortbuffer = (struct pmcstat_cgnode **) 594 malloc(sizeof(struct pmcstat_cgnode *) * 595 pmcstat_cgnode_hash_count)) == NULL) 596 err(EX_OSERR, "ERROR: Cannot sort callgraph"); 597 cgn = sortbuffer; 598 599 for (n = 0; n < PMCSTAT_NHASH; n++) 600 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next) 601 if (pmcr == NULL || pch->pch_pmcid == pmcr->pr_pmcid) { 602 nsamples += pch->pch_cgnode->pcg_count; 603 *cgn++ = pch->pch_cgnode; 604 } 605 606 nentries = cgn - sortbuffer; 607 assert(nentries <= pmcstat_cgnode_hash_count); 608 609 if (nentries == 0) { 610 free(sortbuffer); 611 return; 612 } 613 614 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *), 615 pmcstat_cgnode_compare); 616 617 PMCSTAT_PRINTW("%5.5s %-10.10s %-20.20s %s\n", 618 "%SAMP", "IMAGE", "FUNCTION", "CALLERS"); 619 620 nentries = min(pmcstat_displayheight - 2, nentries); 621 622 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) { 623 if (PMCPL_CG_COUNTP(*cgn) < pmcstat_threshold) 624 break; 625 pmcstat_cgnode_topprint(*cgn, 0, nsamples); 626 } 627 628 free(sortbuffer); 629 } 630 631 /* 632 * Handle top mode keypress. 633 */ 634 635 int 636 pmcpl_cg_topkeypress(int c, WINDOW *w) 637 { 638 639 (void) c; (void) w; 640 641 return 0; 642 } 643 644 int 645 pmcpl_cg_init(void) 646 { 647 int i; 648 649 pmcstat_cgnode_hash_count = 0; 650 pmcstat_previous_filename_printed = NULL; 651 652 for (i = 0; i < PMCSTAT_NHASH; i++) { 653 LIST_INIT(&pmcstat_cgnode_hash[i]); 654 } 655 656 return (0); 657 } 658 659 void 660 pmcpl_cg_shutdown(FILE *mf) 661 { 662 int i; 663 struct pmcstat_cgnode_hash *pch, *pchtmp; 664 665 (void) mf; 666 667 if (args.pa_flags & FLAG_DO_CALLGRAPHS) 668 pmcstat_callgraph_print(); 669 670 /* 671 * Free memory. 672 */ 673 for (i = 0; i < PMCSTAT_NHASH; i++) { 674 LIST_FOREACH_SAFE(pch, &pmcstat_cgnode_hash[i], pch_next, 675 pchtmp) { 676 pmcstat_cgnode_free(pch->pch_cgnode); 677 LIST_REMOVE(pch, pch_next); 678 free(pch); 679 } 680 } 681 } 682 683