usr.sbin/pmcstat/pmcpl_calltree.c

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