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         struct pmcpl_ct_arc *arc;
 358
 359         if (ct->pct_flags & PMCPL_PCT_TAG)
 360                 return 0;
 361
 362         ct->pct_flags |= PMCPL_PCT_TAG;
 363
 364         if (x >= PMCPL_CT_MAXCOL) {
 365                 pmcpl_ct_topscreen[x][*y] = NULL;
 366                 return 1;
 367         }
 368         pmcpl_ct_topscreen[x][*y] = ct;
 369
 370         /*
 371          * Check if this is a terminal node.
 372          * We need to check that some samples exist
 373          * for at least one arc for that PMC.
 374          */
 375         terminal = 1;
 376         for (i = 0; i < ct->pct_narc; i++) {
 377                 arc = &ct->pct_arc[i];
 378                 if (PMCPL_CT_SAMPLE(pmcin,
 379                     &arc->pcta_samples) != 0 &&
 380                     PMCPL_CT_SAMPLEP(pmcin,
 381                     &arc->pcta_samples) > pmcstat_threshold &&
 382                     (arc->pcta_child->pct_flags & PMCPL_PCT_TAG) == 0) {
 383                         terminal = 0;
 384                         break;
 385                 }
 386         }
 387
 388         if (ct->pct_narc == 0 || terminal) {
 389                 pmcpl_ct_topscreen[x+1][*y] = NULL;
 390                 if (*y >= PMCPL_CT_MAXLINE)
 391                         return 1;
 392                 *y = *y + 1;
 393                 for (i=0; i < x; i++)
 394                         pmcpl_ct_topscreen[i][*y] =
 395                             pmcpl_ct_topscreen[i][*y - 1];
 396                 return 0;
 397         }
 398
 399         for (i = 0; i < ct->pct_narc; i++) {
 400                 if (PMCPL_CT_SAMPLE(pmcin,
 401                     &ct->pct_arc[i].pcta_samples) == 0)
 402                         continue;
 403                 if (PMCPL_CT_SAMPLEP(pmcin,
 404                     &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) {
 405                         if (pmcpl_ct_node_dumptop(pmcin,
 406                                 ct->pct_arc[i].pcta_child,
 407                                 rsamples, x+1, y))
 408                                 return 1;
 409                 }
 410         }
 411
 412         return 0;
 413 }
 414
 415 /*
 416  * Compare two top line by sum.
 417  */
 418 static int
 419 pmcpl_ct_line_compare(const void *a, const void *b)
 420 {
 421         const struct pmcpl_ct_line *ct1, *ct2;
 422
 423         ct1 = (const struct pmcpl_ct_line *) a;
 424         ct2 = (const struct pmcpl_ct_line *) b;
 425
 426         /* Sort in reverse order */
 427         if (ct1->ln_sum < ct2->ln_sum)
 428                 return (1);
 429         if (ct1->ln_sum > ct2->ln_sum)
 430                 return (-1);
 431         return (0);
 432 }
 433
 434 /*
 435  * Format and display given PMC index.
 436  */
 437
 438 static void
 439 pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
 440 {
 441 #undef  TS
 442 #undef  TSI
 443 #define TS(x, y)        (pmcpl_ct_topscreen[x][y])
 444 #define TSI(x, y)       (pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index])
 445
 446         int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y;
 447         float v;
 448         char ns[30], vs[10], is[20];
 449         struct pmcpl_ct_node *ct;
 450         struct pmcstat_symbol *sym;
 451         const char *space = " ";
 452
 453         /*
 454          * Sort by line cost.
 455          */
 456         for (y = 0; ; y++) {
 457                 ct = TS(1, y);
 458                 if (ct == NULL)
 459                         break;
 460
 461                 pmcpl_ct_topmax[y].ln_sum = 0;
 462                 pmcpl_ct_topmax[y].ln_index = y;
 463                 for (x = 1; TS(x, y) != NULL; x++) {
 464                         pmcpl_ct_topmax[y].ln_sum +=
 465                             PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples);
 466                 }
 467         }
 468         qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]),
 469             pmcpl_ct_line_compare);
 470         pmcpl_ct_topmax[y].ln_index = y;
 471
 472         for (y = 0; y < maxy; y++) {
 473                 ct = TSI(1, y);
 474                 if (ct == NULL)
 475                         break;
 476
 477                 if (y > 0)
 478                         PMCSTAT_PRINTW("\n");
 479
 480                 /* Output sum. */
 481                 v = pmcpl_ct_topmax[y].ln_sum * 100.0 /
 482                     rsamples->sb[pmcin];
 483                 snprintf(vs, sizeof(vs), "%.1f", v);
 484                 v_attrs = PMCSTAT_ATTRPERCENT(v);
 485                 PMCSTAT_ATTRON(v_attrs);
 486                 PMCSTAT_PRINTW("%5.5s ", vs);
 487                 PMCSTAT_ATTROFF(v_attrs);
 488
 489                 width = indentwidth = 5 + 1;
 490
 491                 for (x = 1; (ct = TSI(x, y)) != NULL; x++) {
 492
 493                         vs[0] = '\0'; vs_len = 0;
 494                         is[0] = '\0'; is_len = 0;
 495
 496                         /* Format value. */
 497                         v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples);
 498                         if (v > pmcstat_threshold)
 499                                 vs_len  = snprintf(vs, sizeof(vs),
 500                                     "(%.1f%%)", v);
 501                         v_attrs = PMCSTAT_ATTRPERCENT(v);
 502
 503                         if (pmcstat_skiplink && v <= pmcstat_threshold) {
 504                                 strlcpy(ns, ".", sizeof(ns));
 505                                 ns_len = 1;
 506                         } else {
 507                         sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
 508                         if (sym != NULL) {
 509                                 ns_len = snprintf(ns, sizeof(ns), "%s",
 510                                     pmcstat_string_unintern(sym->ps_name));
 511                         } else
 512                                 ns_len = snprintf(ns, sizeof(ns), "%p",
 513                                     (void *)ct->pct_func);
 514
 515                         /* Format image. */
 516                         if (x == 1 ||
 517                             TSI(x-1, y)->pct_image != ct->pct_image)
 518                                 is_len = snprintf(is, sizeof(is), "@%s",
 519                                     pmcstat_string_unintern(ct->pct_image->pi_name));
 520
 521                         /* Check for line wrap. */
 522                         width += ns_len + is_len + vs_len + 1;
 523                         }
 524                         if (width >= pmcstat_displaywidth) {
 525                                 maxy--;
 526                                 if (y >= maxy)
 527                                         break;
 528                                 PMCSTAT_PRINTW("\n%*s", indentwidth, space);
 529                                 width = indentwidth + ns_len + is_len + vs_len;
 530                         }
 531
 532                         PMCSTAT_ATTRON(v_attrs);
 533                         PMCSTAT_PRINTW("%s%s%s ", ns, is, vs);
 534                         PMCSTAT_ATTROFF(v_attrs);
 535                 }
 536         }
 537 }
 538
 539 /*
 540  * Output top mode snapshot.
 541  */
 542
 543 void
 544 pmcpl_ct_topdisplay(void)
 545 {
 546         int y;
 547         struct pmcpl_ct_sample r, *rsamples;
 548
 549         rsamples = &r;
 550         pmcpl_ct_samples_root(rsamples);
 551
 552         pmcpl_ct_node_cleartag();
 553
 554         PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE");
 555
 556         y = 0;
 557         if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter,
 558             pmcpl_ct_root, rsamples, 0, &y))
 559                 PMCSTAT_PRINTW("...\n");
 560         pmcpl_ct_topscreen[1][y] = NULL;
 561
 562         pmcpl_ct_node_printtop(rsamples,
 563             pmcstat_pmcinfilter, pmcstat_displayheight - 2);
 564
 565         pmcpl_ct_samples_free(rsamples);
 566 }
 567
 568 /*
 569  * Handle top mode keypress.
 570  */
 571
 572 int
 573 pmcpl_ct_topkeypress(int c, WINDOW *w)
 574 {
 575
 576         switch (c) {
 577         case 'f':
 578                 pmcstat_skiplink = !pmcstat_skiplink;
 579                 wprintw(w, "skip empty link %s", pmcstat_skiplink ? "on" : "off");
 580                 break;
 581         }
 582
 583         return 0;
 584 }
 585
 586 /*
 587  * Look for a callgraph node associated with pmc `pmcid' in the global
 588  * hash table that corresponds to the given `pc' value in the process map
 589  * `ppm'.
 590  */
 591
 592 static struct pmcpl_ct_node *
 593 pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent,
 594     struct pmcstat_pcmap *ppm, uintfptr_t pc, int pmcin)
 595 {
 596         struct pmcstat_symbol *sym;
 597         struct pmcstat_image *image;
 598         struct pmcpl_ct_node *ct;
 599         struct pmcpl_ct_node_hash *h;
 600         struct pmcpl_ct_arc *arc;
 601         uintfptr_t loadaddress;
 602         int i;
 603         unsigned int hash;
 604
 605         assert(parent != NULL);
 606
 607         image = ppm->ppm_image;
 608
 609         loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
 610         pc -= loadaddress;      /* Convert to an offset in the image. */
 611
 612         /*
 613          * Try determine the function at this offset.  If we can't
 614          * find a function round leave the `pc' value alone.
 615          */
 616         if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
 617                 pc = sym->ps_start;
 618         else
 619                 pmcstat_stats.ps_samples_unknown_function++;
 620
 621         for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++)
 622                 hash += (pc >> i) & 0xFF;
 623
 624         hash &= PMCSTAT_HASH_MASK;
 625
 626         ct = NULL;
 627         LIST_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
 628                 ct = h->pch_ctnode;
 629
 630                 assert(ct != NULL);
 631
 632                 if (ct->pct_image == image && ct->pct_func == pc) {
 633                         /*
 634                          * Find related arc in parent node and
 635                          * increment the sample count.
 636                          */
 637                         for (i = 0; i < parent->pct_narc; i++) {
 638                                 if (parent->pct_arc[i].pcta_child == ct) {
 639                                         arc = &parent->pct_arc[i];
 640                                         pmcpl_ct_samples_grow(&arc->pcta_samples);
 641                                         arc->pcta_samples.sb[pmcin]++;
 642                                         /* Estimate call count. */
 643                                         pmcpl_ct_samples_grow(&arc->pcta_callid);
 644                                         if (pmcpl_ct_callid.sb[pmcin] -
 645                                             arc->pcta_callid.sb[pmcin] > 1)
 646                                                 arc->pcta_call++;
 647                                         arc->pcta_callid.sb[pmcin] =
 648                                             pmcpl_ct_callid.sb[pmcin];
 649                                         return (ct);
 650                                 }
 651                         }
 652
 653                         /*
 654                          * No arc found for us, add ourself to the parent.
 655                          */
 656                         pmcpl_ct_arc_grow(parent->pct_narc,
 657                             &parent->pct_arc_c, &parent->pct_arc);
 658                         arc = &parent->pct_arc[parent->pct_narc];
 659                         pmcpl_ct_samples_grow(&arc->pcta_samples);
 660                         arc->pcta_samples.sb[pmcin] = 1;
 661                         arc->pcta_call = 1;
 662                         pmcpl_ct_samples_grow(&arc->pcta_callid);
 663                         arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
 664                         arc->pcta_child = ct;
 665                         parent->pct_narc++;
 666                         return (ct);
 667                 }
 668         }
 669
 670         /*
 671          * We haven't seen this (pmcid, pc) tuple yet, so allocate a
 672          * new callgraph node and a new hash table entry for it.
 673          */
 674         ct = pmcpl_ct_node_allocate(image, pc);
 675         if ((h = malloc(sizeof(*h))) == NULL)
 676                 err(EX_OSERR, "ERROR: Could not allocate callgraph node");
 677
 678         h->pch_ctnode = ct;
 679         LIST_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
 680
 681         pmcpl_ct_arc_grow(parent->pct_narc,
 682             &parent->pct_arc_c, &parent->pct_arc);
 683         arc = &parent->pct_arc[parent->pct_narc];
 684         pmcpl_ct_samples_grow(&arc->pcta_samples);
 685         arc->pcta_samples.sb[pmcin] = 1;
 686         arc->pcta_call = 1;
 687         pmcpl_ct_samples_grow(&arc->pcta_callid);
 688         arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
 689         arc->pcta_child = ct;
 690         parent->pct_narc++;
 691         return (ct);
 692 }
 693
 694 /*
 695  * Record a callchain.
 696  */
 697
 698 void
 699 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
 700     uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
 701 {
 702         int n, pmcin;
 703         struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX];
 704         struct pmcstat_process *km;
 705         struct pmcpl_ct_node *parent, *child;
 706
 707         (void) cpu;
 708
 709         assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX);
 710
 711         /* Get the PMC index. */
 712         pmcin = pmcr->pr_pmcin;
 713
 714         /*
 715          * Validate mapping for the callchain.
 716          * Go from bottom to first invalid entry.
 717          */
 718         km = pmcstat_kernproc;
 719         for (n = 0; n < (int)nsamples; n++) {
 720                 ppm[n] = pmcstat_process_find_map(usermode ?
 721                     pp : km, cc[n]);
 722                 if (ppm[n] == NULL) {
 723                         /* Detect full frame capture (kernel + user). */
 724                         if (!usermode) {
 725                                 ppm[n] = pmcstat_process_find_map(pp, cc[n]);
 726                                 if (ppm[n] != NULL)
 727                                         km = pp;
 728                         }
 729                 }
 730                 if (ppm[n] == NULL)
 731                         break;
 732         }
 733         if (n-- == 0) {
 734                 pmcstat_stats.ps_callchain_dubious_frames++;
 735                 pmcr->pr_dubious_frames++;
 736                 return;
 737         }
 738
 739         /* Increase the call generation counter. */
 740         pmcpl_ct_samples_grow(&pmcpl_ct_callid);
 741         pmcpl_ct_callid.sb[pmcin]++;
 742
 743         /*
 744          * Iterate remaining addresses.
 745          */
 746         for (parent = pmcpl_ct_root, child = NULL; n >= 0; n--) {
 747                 child = pmcpl_ct_node_hash_lookup_pc(parent, ppm[n], cc[n],
 748                     pmcin);
 749                 if (child == NULL) {
 750                         pmcstat_stats.ps_callchain_dubious_frames++;
 751                         continue;
 752                 }
 753                 parent = child;
 754         }
 755
 756         /*
 757          * Increment the sample count for this PMC.
 758          */
 759         if (child != NULL) {
 760                 pmcpl_ct_samples_grow(&child->pct_samples);
 761                 child->pct_samples.sb[pmcin]++;
 762
 763                 /* Update per instruction sample if required. */
 764                 if (args.pa_ctdumpinstr)
 765                         pmcpl_ct_instr_add(child, pmcin, cc[0] -
 766                             (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
 767                              ppm[0]->ppm_image->pi_start));
 768         }
 769 }
 770
 771 /*
 772  * Print node self cost.
 773  */
 774
 775 static void
 776 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
 777 {
 778         int i, j, line;
 779         uintptr_t addr;
 780         struct pmcstat_symbol *sym;
 781         char sourcefile[PATH_MAX];
 782         char funcname[PATH_MAX];
 783
 784         /*
 785          * Object binary.
 786          */
 787 #ifdef PMCPL_CT_OPTIMIZEFN
 788         if (pmcpl_ct_prevfn != ct->pct_image->pi_fullpath) {
 789 #endif
 790                 pmcpl_ct_prevfn = ct->pct_image->pi_fullpath;
 791                 fprintf(args.pa_graphfile, "ob=%s\n",
 792                     pmcstat_string_unintern(pmcpl_ct_prevfn));
 793 #ifdef PMCPL_CT_OPTIMIZEFN
 794         }
 795 #endif
 796
 797         /*
 798          * Function name.
 799          */
 800         if (pmcstat_image_addr2line(ct->pct_image, ct->pct_func,
 801             sourcefile, sizeof(sourcefile), &line,
 802             funcname, sizeof(funcname))) {
 803                 fprintf(args.pa_graphfile, "fn=%s\n",
 804                     funcname);
 805         } else {
 806                 sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
 807                 if (sym != NULL)
 808                         fprintf(args.pa_graphfile, "fn=%s\n",
 809                             pmcstat_string_unintern(sym->ps_name));
 810                 else
 811                         fprintf(args.pa_graphfile, "fn=%p\n",
 812                             (void *)(ct->pct_image->pi_vaddr + ct->pct_func));
 813         }
 814
 815         /*
 816          * Self cost.
 817          */
 818         if (ct->pct_ninstr > 0) {
 819                 for (i = 0; i < ct->pct_ninstr; i++) {
 820                         addr = ct->pct_image->pi_vaddr +
 821                             ct->pct_instr[i].pctf_func;
 822                         line = 0;
 823                         if (pmcstat_image_addr2line(ct->pct_image, addr,
 824                             sourcefile, sizeof(sourcefile), &line,
 825                             funcname, sizeof(funcname)))
 826                                 fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
 827                         fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
 828                         for (j = 0; j<pmcstat_npmcs; j++)
 829                                 fprintf(args.pa_graphfile, " %u",
 830                                     PMCPL_CT_SAMPLE(j,
 831                                     &ct->pct_instr[i].pctf_samples));
 832                         fprintf(args.pa_graphfile, "\n");
 833                 }
 834         } else {
 835                 addr = ct->pct_image->pi_vaddr + ct->pct_func;
 836                 line = 0;
 837                 if (pmcstat_image_addr2line(ct->pct_image, addr,
 838                     sourcefile, sizeof(sourcefile), &line,
 839                     funcname, sizeof(funcname)))
 840                         fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
 841                 fprintf(args.pa_graphfile, "* *");
 842                 for (i = 0; i<pmcstat_npmcs ; i++)
 843                         fprintf(args.pa_graphfile, " %u",
 844                             PMCPL_CT_SAMPLE(i, &ct->pct_samples));
 845                 fprintf(args.pa_graphfile, "\n");
 846         }
 847 }
 848
 849 /*
 850  * Print node child cost.
 851  */
 852
 853 static void
 854 pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct)
 855 {
 856         int i, j, line;
 857         uintptr_t addr;
 858         struct pmcstat_symbol *sym;
 859         struct pmcpl_ct_node *child;
 860         char sourcefile[PATH_MAX];
 861         char funcname[PATH_MAX];
 862
 863         /*
 864          * Child cost.
 865          * TODO: attach child cost to the real position in the funtion.
 866          * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
 867          */
 868         for (i=0 ; i<ct->pct_narc; i++) {
 869                 child = ct->pct_arc[i].pcta_child;
 870
 871                 /* Object binary. */
 872 #ifdef PMCPL_CT_OPTIMIZEFN
 873                 if (pmcpl_ct_prevfn != child->pct_image->pi_fullpath) {
 874 #endif
 875                         pmcpl_ct_prevfn = child->pct_image->pi_fullpath;
 876                         fprintf(args.pa_graphfile, "cob=%s\n",
 877                             pmcstat_string_unintern(pmcpl_ct_prevfn));
 878 #if PMCPL_CT_OPTIMIZEFN
 879                 }
 880 #endif
 881                 /* Child function name. */
 882                 addr = child->pct_image->pi_vaddr + child->pct_func;
 883                 /* Child function source file. */
 884                 if (pmcstat_image_addr2line(child->pct_image, addr,
 885                     sourcefile, sizeof(sourcefile), &line,
 886                     funcname, sizeof(funcname))) {
 887                         fprintf(args.pa_graphfile, "cfn=%s\n", funcname);
 888                         fprintf(args.pa_graphfile, "cfl=%s\n", sourcefile);
 889                 } else {
 890                         sym = pmcstat_symbol_search(child->pct_image,
 891                             child->pct_func);
 892                         if (sym != NULL)
 893                                 fprintf(args.pa_graphfile, "cfn=%s\n",
 894                                     pmcstat_string_unintern(sym->ps_name));
 895                         else
 896                                 fprintf(args.pa_graphfile, "cfn=%p\n", (void *)addr);
 897                 }
 898
 899                 /* Child function address, line and call count. */
 900                 fprintf(args.pa_graphfile, "calls=%u %p %u\n",
 901                     ct->pct_arc[i].pcta_call, (void *)addr, line);
 902
 903                 if (ct->pct_image != NULL) {
 904                         /* Call address, line, sample. */
 905                         addr = ct->pct_image->pi_vaddr + ct->pct_func;
 906                         line = 0;
 907                         if (pmcstat_image_addr2line(ct->pct_image, addr, sourcefile,
 908                             sizeof(sourcefile), &line,
 909                             funcname, sizeof(funcname)))
 910                                 fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
 911                         else
 912                                 fprintf(args.pa_graphfile, "* *");
 913                 }
 914                 else
 915                         fprintf(args.pa_graphfile, "* *");
 916                 for (j = 0; j<pmcstat_npmcs; j++)
 917                         fprintf(args.pa_graphfile, " %u",
 918                             PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
 919                 fprintf(args.pa_graphfile, "\n");
 920         }
 921 }
 922
 923 /*
 924  * Clean the PMC name for Kcachegrind formula
 925  */
 926
 927 static void
 928 pmcpl_ct_fixup_pmcname(char *s)
 929 {
 930         char *p;
 931
 932         for (p = s; *p; p++)
 933                 if (!isalnum(*p))
 934                         *p = '_';
 935 }
 936
 937 /*
 938  * Print a calltree (KCachegrind) for all PMCs.
 939  */
 940
 941 static void
 942 pmcpl_ct_print(void)
 943 {
 944         int n, i;
 945         struct pmcpl_ct_node_hash *pch;
 946         struct pmcpl_ct_sample rsamples;
 947         char name[40];
 948
 949         pmcpl_ct_samples_root(&rsamples);
 950         pmcpl_ct_prevfn = NULL;
 951
 952         fprintf(args.pa_graphfile,
 953                 "version: 1\n"
 954                 "creator: pmcstat\n"
 955                 "positions: instr line\n"
 956                 "events:");
 957         for (i=0; i<pmcstat_npmcs; i++) {
 958                 snprintf(name, sizeof(name), "%s_%d",
 959                     pmcstat_pmcindex_to_name(i), i);
 960                 pmcpl_ct_fixup_pmcname(name);
 961                 fprintf(args.pa_graphfile, " %s", name);
 962         }
 963         fprintf(args.pa_graphfile, "\nsummary:");
 964         for (i=0; i<pmcstat_npmcs ; i++)
 965                 fprintf(args.pa_graphfile, " %u",
 966                     PMCPL_CT_SAMPLE(i, &rsamples));
 967         fprintf(args.pa_graphfile, "\n\n");
 968
 969         /*
 970          * Fake root node
 971          */
 972         fprintf(args.pa_graphfile, "ob=FreeBSD\n");
 973         fprintf(args.pa_graphfile, "fn=ROOT\n");
 974         fprintf(args.pa_graphfile, "* *");
 975         for (i = 0; i<pmcstat_npmcs ; i++)
 976                 fprintf(args.pa_graphfile, " 0");
 977         fprintf(args.pa_graphfile, "\n");
 978         pmcpl_ct_node_printchild(pmcpl_ct_root);
 979
 980         for (n = 0; n < PMCSTAT_NHASH; n++)
 981                 LIST_FOREACH(pch, &pmcpl_ct_node_hash[n], pch_next) {
 982                         pmcpl_ct_node_printself(pch->pch_ctnode);
 983                         pmcpl_ct_node_printchild(pch->pch_ctnode);
 984         }
 985
 986         pmcpl_ct_samples_free(&rsamples);
 987 }
 988
 989 int
 990 pmcpl_ct_configure(char *opt)
 991 {
 992
 993         if (strncmp(opt, "skiplink=", 9) == 0) {
 994                 pmcstat_skiplink = atoi(opt+9);
 995         } else
 996                 return (0);
 997
 998         return (1);
 999 }
1000
1001 int
1002 pmcpl_ct_init(void)
1003 {
1004         int i;
1005
1006         pmcpl_ct_prevfn = NULL;
1007         pmcpl_ct_root = pmcpl_ct_node_allocate(NULL, 0);
1008
1009         for (i = 0; i < PMCSTAT_NHASH; i++)
1010                 LIST_INIT(&pmcpl_ct_node_hash[i]);
1011
1012         pmcpl_ct_samples_init(&pmcpl_ct_callid);
1013
1014         return (0);
1015 }
1016
1017 void
1018 pmcpl_ct_shutdown(FILE *mf)
1019 {
1020         int i;
1021         struct pmcpl_ct_node_hash *pch, *pchtmp;
1022
1023         (void) mf;
1024
1025         if (args.pa_flags & FLAG_DO_CALLGRAPHS)
1026                 pmcpl_ct_print();
1027
1028         /*
1029          * Free memory.
1030          */
1031
1032         for (i = 0; i < PMCSTAT_NHASH; i++) {
1033                 LIST_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
1034                     pchtmp) {
1035                         pmcpl_ct_node_free(pch->pch_ctnode);
1036                         free(pch);
1037                 }
1038         }
1039
1040         pmcpl_ct_node_free(pmcpl_ct_root);
1041         pmcpl_ct_root = NULL;
1042
1043         pmcpl_ct_samples_free(&pmcpl_ct_callid);
1044 }
1045