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 <stdint.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53 #include <unistd.h>
  54 #include <sysexits.h>
  55
  56 #include "pmcstat.h"
  57 #include "pmcstat_log.h"
  58 #include "pmcstat_top.h"
  59 #include "pmcpl_calltree.h"
  60
  61 #define PMCPL_CT_GROWSIZE       4
  62
  63 static pmcstat_interned_string pmcpl_ct_prevfn;
  64
  65 static int pmcstat_skiplink = 0;
  66
  67 struct pmcpl_ct_node;
  68
  69 /* Get the sample value for PMC a. */
  70 #define PMCPL_CT_SAMPLE(a, b) \
  71         ((a) < (b)->npmcs ? (b)->sb[a] : 0)
  72
  73 /* Get the sample value in percent related to rsamples. */
  74 #define PMCPL_CT_SAMPLEP(a, b) \
  75         (PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a])
  76
  77 struct pmcpl_ct_sample {
  78         int             npmcs;          /* Max pmc index available. */
  79         unsigned        *sb;            /* Sample buffer for 0..npmcs. */
  80 };
  81
  82 struct pmcpl_ct_arc {
  83         struct pmcpl_ct_sample  pcta_samples;
  84         struct pmcpl_ct_sample  pcta_callid;
  85         unsigned                pcta_call;
  86         struct pmcpl_ct_node    *pcta_child;
  87 };
  88
  89 struct pmcpl_ct_instr {
  90         uintfptr_t              pctf_func;
  91         struct pmcpl_ct_sample  pctf_samples;
  92 };
  93
  94 /*
  95  * Each calltree node is tracked by a pmcpl_ct_node struct.
  96  */
  97 struct pmcpl_ct_node {
  98 #define PMCPL_PCT_TAG   0x00000001      /* Loop detection. */
  99         uint32_t                pct_flags;
 100         struct pmcstat_image    *pct_image;
 101         uintfptr_t              pct_func;
 102         struct pmcpl_ct_sample  pct_samples;
 103
 104         int                     pct_narc;
 105         int                     pct_arc_c;
 106         struct pmcpl_ct_arc     *pct_arc;
 107
 108         /* TODO: optimize for large number of items. */
 109         int                     pct_ninstr;
 110         int                     pct_instr_c;
 111         struct pmcpl_ct_instr   *pct_instr;
 112 };
 113
 114 struct pmcpl_ct_node_hash {
 115         struct pmcpl_ct_node  *pch_ctnode;
 116         LIST_ENTRY(pmcpl_ct_node_hash) pch_next;
 117 };
 118
 119 struct pmcpl_ct_sample pmcpl_ct_callid;
 120
 121 #define PMCPL_CT_MAXCOL         PMC_CALLCHAIN_DEPTH_MAX
 122 #define PMCPL_CT_MAXLINE        1024    /* TODO: dynamic. */
 123
 124 struct pmcpl_ct_line {
 125         unsigned        ln_sum;
 126         unsigned        ln_index;
 127 };
 128
 129 struct pmcpl_ct_line    pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1];
 130 struct pmcpl_ct_node    *pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1];
 131
 132 /*
 133  * All nodes indexed by function/image name are placed in a hash table.
 134  */
 135 static LIST_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH];
 136
 137 /*
 138  * Root node for the graph.
 139  */
 140 static struct pmcpl_ct_node *pmcpl_ct_root;
 141
 142 /*
 143  * Prototypes
 144  */
 145
 146 /*
 147  * Initialize a samples.
 148  */
 149
 150 static void
 151 pmcpl_ct_samples_init(struct pmcpl_ct_sample *samples)
 152 {
 153
 154         samples->npmcs = 0;
 155         samples->sb = NULL;
 156 }
 157
 158 /*
 159  * Free a samples.
 160  */
 161
 162 static void
 163 pmcpl_ct_samples_free(struct pmcpl_ct_sample *samples)
 164 {
 165
 166         samples->npmcs = 0;
 167         free(samples->sb);
 168         samples->sb = NULL;
 169 }
 170
 171 /*
 172  * Grow a sample block to store pmcstat_npmcs PMCs.
 173  */
 174
 175 static void
 176 pmcpl_ct_samples_grow(struct pmcpl_ct_sample *samples)
 177 {
 178         int npmcs;
 179
 180         /* Enough storage. */
 181         if (pmcstat_npmcs <= samples->npmcs)
 182                 return;
 183
 184         npmcs = samples->npmcs +
 185             max(pmcstat_npmcs - samples->npmcs, PMCPL_CT_GROWSIZE);
 186         samples->sb = realloc(samples->sb, npmcs * sizeof(unsigned));
 187         if (samples->sb == NULL)
 188                 errx(EX_SOFTWARE, "ERROR: out of memory");
 189         bzero((char *)samples->sb + samples->npmcs * sizeof(unsigned),
 190             (npmcs - samples->npmcs) * sizeof(unsigned));
 191         samples->npmcs = npmcs;
 192 }
 193
 194 /*
 195  * Compute the sum of all root arcs.
 196  */
 197
 198 static void
 199 pmcpl_ct_samples_root(struct pmcpl_ct_sample *samples)
 200 {
 201         int i, pmcin;
 202
 203         pmcpl_ct_samples_init(samples);
 204         pmcpl_ct_samples_grow(samples);
 205
 206         for (i = 0; i < pmcpl_ct_root->pct_narc; i++)
 207                 for (pmcin = 0; pmcin < pmcstat_npmcs; pmcin++)
 208                         samples->sb[pmcin] += PMCPL_CT_SAMPLE(pmcin,
 209                             &pmcpl_ct_root->pct_arc[i].pcta_samples);
 210 }
 211
 212 /*
 213  * Grow the arc table.
 214  */
 215
 216 static void
 217 pmcpl_ct_arc_grow(int cursize, int *maxsize, struct pmcpl_ct_arc **items)
 218 {
 219         int nmaxsize;
 220
 221         if (cursize < *maxsize)
 222                 return;
 223
 224         nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
 225         *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_arc));
 226         if (*items == NULL)
 227                 errx(EX_SOFTWARE, "ERROR: out of memory");
 228         bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_arc),
 229             (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_arc));
 230         *maxsize = nmaxsize;
 231 }
 232
 233 /*
 234  * Grow the instr table.
 235  */
 236
 237 static void
 238 pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items)
 239 {
 240         int nmaxsize;
 241
 242         if (cursize < *maxsize)
 243                 return;
 244
 245         nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
 246         *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_instr));
 247         if (*items == NULL)
 248                 errx(EX_SOFTWARE, "ERROR: out of memory");
 249         bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_instr),
 250             (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_instr));
 251         *maxsize = nmaxsize;
 252 }
 253
 254 /*
 255  * Add a new instruction sample to given node.
 256  */
 257
 258 static void
 259 pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
 260 {
 261         int i;
 262         struct pmcpl_ct_instr *in;
 263
 264         for (i = 0; i<ct->pct_ninstr; i++) {
 265                 if (ct->pct_instr[i].pctf_func == pc) {
 266                         in = &ct->pct_instr[i];
 267                         pmcpl_ct_samples_grow(&in->pctf_samples);
 268                         in->pctf_samples.sb[pmcin]++;
 269                         return;
 270                 }
 271         }
 272
 273         pmcpl_ct_instr_grow(ct->pct_ninstr, &ct->pct_instr_c, &ct->pct_instr);
 274         in = &ct->pct_instr[ct->pct_ninstr];
 275         in->pctf_func = pc;
 276         pmcpl_ct_samples_init(&in->pctf_samples);
 277         pmcpl_ct_samples_grow(&in->pctf_samples);
 278         in->pctf_samples.sb[pmcin] = 1;
 279         ct->pct_ninstr++;
 280 }
 281
 282 /*
 283  * Allocate a new node.
 284  */
 285
 286 static struct pmcpl_ct_node *
 287 pmcpl_ct_node_allocate(struct pmcstat_image *image, uintfptr_t pc)
 288 {
 289         struct pmcpl_ct_node *ct;
 290
 291         if ((ct = malloc(sizeof(*ct))) == NULL)
 292                 err(EX_OSERR, "ERROR: Cannot allocate callgraph node");
 293
 294         ct->pct_flags   = 0;
 295         ct->pct_image   = image;
 296         ct->pct_func    = pc;
 297
 298         pmcpl_ct_samples_init(&ct->pct_samples);
 299
 300         ct->pct_narc    = 0;
 301         ct->pct_arc_c   = 0;
 302         ct->pct_arc     = NULL;
 303
 304         ct->pct_ninstr  = 0;
 305         ct->pct_instr_c = 0;
 306         ct->pct_instr   = NULL;
 307
 308         return (ct);
 309 }
 310
 311 /*
 312  * Free a node.
 313  */
 314
 315 static void
 316 pmcpl_ct_node_free(struct pmcpl_ct_node *ct)
 317 {
 318         int i;
 319
 320         for (i = 0; i < ct->pct_narc; i++) {
 321                 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_samples);
 322                 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_callid);
 323         }
 324
 325         pmcpl_ct_samples_free(&ct->pct_samples);
 326         free(ct->pct_arc);
 327         free(ct->pct_instr);
 328         free(ct);
 329 }
 330
 331 /*
 332  * Clear the graph tag on each node.
 333  */
 334 static void
 335 pmcpl_ct_node_cleartag(void)
 336 {
 337         int i;
 338         struct pmcpl_ct_node_hash *pch;
 339
 340         for (i = 0; i < PMCSTAT_NHASH; i++)
 341                 LIST_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
 342                         pch->pch_ctnode->pct_flags &= ~PMCPL_PCT_TAG;
 343
 344         pmcpl_ct_root->pct_flags &= ~PMCPL_PCT_TAG;
 345 }
 346
 347 /*
 348  * Print the callchain line by line with maximum cost at top.
 349  */
 350
 351 static int
 352 pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
 353     struct pmcpl_ct_sample *rsamples, int x, int *y)
 354 {
 355         int i, terminal;
 356         struct pmcpl_ct_arc *arc;
 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                 arc = &ct->pct_arc[i];
 377                 if (PMCPL_CT_SAMPLE(pmcin,
 378                     &arc->pcta_samples) != 0 &&
 379                     PMCPL_CT_SAMPLEP(pmcin,
 380                     &arc->pcta_samples) > pmcstat_threshold &&
 381                     (arc->pcta_child->pct_flags & PMCPL_PCT_TAG) == 0) {
 382                         terminal = 0;
 383                         break;
 384                 }
 385         }
 386
 387         if (ct->pct_narc == 0 || terminal) {
 388                 pmcpl_ct_topscreen[x+1][*y] = NULL;
 389                 if (*y >= PMCPL_CT_MAXLINE)
 390                         return 1;
 391                 *y = *y + 1;
 392                 for (i=0; i < x; i++)
 393                         pmcpl_ct_topscreen[i][*y] =
 394                             pmcpl_ct_topscreen[i][*y - 1];
 395                 return 0;
 396         }
 397
 398         for (i = 0; i < ct->pct_narc; i++) {
 399                 if (PMCPL_CT_SAMPLE(pmcin,
 400                     &ct->pct_arc[i].pcta_samples) == 0)
 401                         continue;
 402                 if (PMCPL_CT_SAMPLEP(pmcin,
 403                     &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) {
 404                         if (pmcpl_ct_node_dumptop(pmcin,
 405                                 ct->pct_arc[i].pcta_child,
 406                                 rsamples, x+1, y))
 407                                 return 1;
 408                 }
 409         }
 410
 411         return 0;
 412 }
 413
 414 /*
 415  * Compare two top line by sum.
 416  */
 417 static int
 418 pmcpl_ct_line_compare(const void *a, const void *b)
 419 {
 420         const struct pmcpl_ct_line *ct1, *ct2;
 421
 422         ct1 = (const struct pmcpl_ct_line *) a;
 423         ct2 = (const struct pmcpl_ct_line *) b;
 424
 425         /* Sort in reverse order */
 426         if (ct1->ln_sum < ct2->ln_sum)
 427                 return (1);
 428         if (ct1->ln_sum > ct2->ln_sum)
 429                 return (-1);
 430         return (0);
 431 }
 432
 433 /*
 434  * Format and display given PMC index.
 435  */
 436
 437 static void
 438 pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
 439 {
 440 #undef  TS
 441 #undef  TSI
 442 #define TS(x, y)        (pmcpl_ct_topscreen[x][y])
 443 #define TSI(x, y)       (pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index])
 444
 445         int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y;
 446         float v;
 447         char ns[30], vs[10], is[20];
 448         struct pmcpl_ct_node *ct;
 449         struct pmcstat_symbol *sym;
 450         const char *space = " ";
 451
 452         /*
 453          * Sort by line cost.
 454          */
 455         for (y = 0; ; y++) {
 456                 ct = TS(1, y);
 457                 if (ct == NULL)
 458                         break;
 459
 460                 pmcpl_ct_topmax[y].ln_sum = 0;
 461                 pmcpl_ct_topmax[y].ln_index = y;
 462                 for (x = 1; TS(x, y) != NULL; x++) {
 463                         pmcpl_ct_topmax[y].ln_sum +=
 464                             PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples);
 465                 }
 466         }
 467         qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]),
 468             pmcpl_ct_line_compare);
 469         pmcpl_ct_topmax[y].ln_index = y;
 470
 471         for (y = 0; y < maxy; y++) {
 472                 ct = TSI(1, y);
 473                 if (ct == NULL)
 474                         break;
 475
 476                 if (y > 0)
 477                         PMCSTAT_PRINTW("\n");
 478
 479                 /* Output sum. */
 480                 v = pmcpl_ct_topmax[y].ln_sum * 100.0 /
 481                     rsamples->sb[pmcin];
 482                 snprintf(vs, sizeof(vs), "%.1f", v);
 483                 v_attrs = PMCSTAT_ATTRPERCENT(v);
 484                 PMCSTAT_ATTRON(v_attrs);
 485                 PMCSTAT_PRINTW("%5.5s ", vs);
 486                 PMCSTAT_ATTROFF(v_attrs);
 487
 488                 width = indentwidth = 5 + 1;
 489
 490                 for (x = 1; (ct = TSI(x, y)) != NULL; x++) {
 491
 492                         vs[0] = '\0'; vs_len = 0;
 493                         is[0] = '\0'; is_len = 0;
 494
 495                         /* Format value. */
 496                         v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples);
 497                         if (v > pmcstat_threshold)
 498                                 vs_len  = snprintf(vs, sizeof(vs),
 499                                     "(%.1f%%)", v);
 500                         v_attrs = PMCSTAT_ATTRPERCENT(v);
 501
 502                         if (pmcstat_skiplink && v <= pmcstat_threshold) {
 503                                 strlcpy(ns, ".", sizeof(ns));
 504                                 ns_len = 1;
 505                         } else {
 506                         sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
 507                         if (sym != NULL) {
 508                                 ns_len = snprintf(ns, sizeof(ns), "%s",
 509                                     pmcstat_string_unintern(sym->ps_name));
 510                         } else
 511                                 ns_len = snprintf(ns, sizeof(ns), "%p",
 512                                     (void *)ct->pct_func);
 513
 514                         /* Format image. */
 515                         if (x == 1 ||
 516                             TSI(x-1, y)->pct_image != ct->pct_image)
 517                                 is_len = snprintf(is, sizeof(is), "@%s",
 518                                     pmcstat_string_unintern(ct->pct_image->pi_name));
 519
 520                         /* Check for line wrap. */
 521                         width += ns_len + is_len + vs_len + 1;
 522                         }
 523                         if (width >= pmcstat_displaywidth) {
 524                                 maxy--;
 525                                 if (y >= maxy)
 526                                         break;
 527                                 PMCSTAT_PRINTW("\n%*s", indentwidth, space);
 528                                 width = indentwidth + ns_len + is_len + vs_len;
 529                         }
 530
 531                         PMCSTAT_ATTRON(v_attrs);
 532                         PMCSTAT_PRINTW("%s%s%s ", ns, is, vs);
 533                         PMCSTAT_ATTROFF(v_attrs);
 534                 }
 535         }
 536 }
 537
 538 /*
 539  * Output top mode snapshot.
 540  */
 541
 542 void
 543 pmcpl_ct_topdisplay(void)
 544 {
 545         int y;
 546         struct pmcpl_ct_sample r, *rsamples;
 547
 548         rsamples = &r;
 549         pmcpl_ct_samples_root(rsamples);
 550
 551         pmcpl_ct_node_cleartag();
 552
 553         PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE");
 554
 555         y = 0;
 556         if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter,
 557             pmcpl_ct_root, rsamples, 0, &y))
 558                 PMCSTAT_PRINTW("...\n");
 559         pmcpl_ct_topscreen[1][y] = NULL;
 560
 561         pmcpl_ct_node_printtop(rsamples,
 562             pmcstat_pmcinfilter, pmcstat_displayheight - 2);
 563
 564         pmcpl_ct_samples_free(rsamples);
 565 }
 566
 567 /*
 568  * Handle top mode keypress.
 569  */
 570
 571 int
 572 pmcpl_ct_topkeypress(int c, WINDOW *w)
 573 {
 574
 575         switch (c) {
 576         case 'f':
 577                 pmcstat_skiplink = !pmcstat_skiplink;
 578                 wprintw(w, "skip empty link %s",
 579                     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