usr.sbin/pmcstat/pmcpl_callgraph.c

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