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", pmcstat_skiplink ? "on" : "off");
 579                 break;
 580         }
 581
 582         return 0;
 583 }
 584
 585 /*
 586  * Look for a callgraph node associated with pmc `pmcid' in the global
 587  * hash table that corresponds to the given `pc' value in the process map
 588  * `ppm'.
 589  */
 590
 591 static struct pmcpl_ct_node *
 592 pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent,
 593     struct pmcstat_pcmap *ppm, uintfptr_t pc, int pmcin)
 594 {
 595         struct pmcstat_symbol *sym;
 596         struct pmcstat_image *image;
 597         struct pmcpl_ct_node *ct;
 598         struct pmcpl_ct_node_hash *h;
 599         struct pmcpl_ct_arc *arc;
 600         uintfptr_t loadaddress;
 601         int i;
 602         unsigned int hash;
 603
 604         assert(parent != NULL);
 605
 606         image = ppm->ppm_image;
 607
 608         loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
 609         pc -= loadaddress;      /* Convert to an offset in the image. */
 610
 611         /*
 612          * Try determine the function at this offset.  If we can't
 613          * find a function round leave the `pc' value alone.
 614          */
 615         if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
 616                 pc = sym->ps_start;
 617         else
 618                 pmcstat_stats.ps_samples_unknown_function++;
 619
 620         for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++)
 621                 hash += (pc >> i) & 0xFF;
 622
 623         hash &= PMCSTAT_HASH_MASK;
 624
 625         ct = NULL;
 626         LIST_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
 627                 ct = h->pch_ctnode;
 628
 629                 assert(ct != NULL);
 630
 631                 if (ct->pct_image == image && ct->pct_func == pc) {
 632                         /*
 633                          * Find related arc in parent node and
 634                          * increment the sample count.
 635                          */
 636                         for (i = 0; i < parent->pct_narc; i++) {
 637                                 if (parent->pct_arc[i].pcta_child == ct) {
 638                                         arc = &parent->pct_arc[i];
 639                                         pmcpl_ct_samples_grow(&arc->pcta_samples);
 640                                         arc->pcta_samples.sb[pmcin]++;
 641                                         /* Estimate call count. */
 642                                         pmcpl_ct_samples_grow(&arc->pcta_callid);
 643                                         if (pmcpl_ct_callid.sb[pmcin] -
 644                                             arc->pcta_callid.sb[pmcin] > 1)
 645                                                 arc->pcta_call++;
 646                                         arc->pcta_callid.sb[pmcin] =
 647                                             pmcpl_ct_callid.sb[pmcin];
 648                                         return (ct);
 649                                 }
 650                         }
 651
 652                         /*
 653                          * No arc found for us, add ourself to the parent.
 654                          */
 655                         pmcpl_ct_arc_grow(parent->pct_narc,
 656                             &parent->pct_arc_c, &parent->pct_arc);
 657                         arc = &parent->pct_arc[parent->pct_narc];
 658                         pmcpl_ct_samples_grow(&arc->pcta_samples);
 659                         arc->pcta_samples.sb[pmcin] = 1;
 660                         arc->pcta_call = 1;
 661                         pmcpl_ct_samples_grow(&arc->pcta_callid);
 662                         arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
 663                         arc->pcta_child = ct;
 664                         parent->pct_narc++;
 665                         return (ct);
 666                 }
 667         }
 668
 669         /*
 670          * We haven't seen this (pmcid, pc) tuple yet, so allocate a
 671          * new callgraph node and a new hash table entry for it.
 672          */
 673         ct = pmcpl_ct_node_allocate(image, pc);
 674         if ((h = malloc(sizeof(*h))) == NULL)
 675                 err(EX_OSERR, "ERROR: Could not allocate callgraph node");
 676
 677         h->pch_ctnode = ct;
 678         LIST_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
 679
 680         pmcpl_ct_arc_grow(parent->pct_narc,
 681             &parent->pct_arc_c, &parent->pct_arc);
 682         arc = &parent->pct_arc[parent->pct_narc];
 683         pmcpl_ct_samples_grow(&arc->pcta_samples);
 684         arc->pcta_samples.sb[pmcin] = 1;
 685         arc->pcta_call = 1;
 686         pmcpl_ct_samples_grow(&arc->pcta_callid);
 687         arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
 688         arc->pcta_child = ct;
 689         parent->pct_narc++;
 690         return (ct);
 691 }
 692
 693 /*
 694  * Record a callchain.
 695  */
 696
 697 void
 698 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
 699     uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
 700 {
 701         int n, pmcin;
 702         struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX];
 703         struct pmcstat_process *km;
 704         struct pmcpl_ct_node *parent, *child;
 705
 706         (void) cpu;
 707
 708         assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX);
 709
 710         /* Get the PMC index. */
 711         pmcin = pmcr->pr_pmcin;
 712
 713         /*
 714          * Validate mapping for the callchain.
 715          * Go from bottom to first invalid entry.
 716          */
 717         km = pmcstat_kernproc;
 718         for (n = 0; n < (int)nsamples; n++) {
 719                 ppm[n] = pmcstat_process_find_map(usermode ?
 720                     pp : km, cc[n]);
 721                 if (ppm[n] == NULL) {
 722                         /* Detect full frame capture (kernel + user). */
 723                         if (!usermode) {
 724                                 ppm[n] = pmcstat_process_find_map(pp, cc[n]);
 725                                 if (ppm[n] != NULL)
 726                                         km = pp;
 727                         }
 728                 }
 729                 if (ppm[n] == NULL)
 730                         break;
 731         }
 732         if (n-- == 0) {
 733                 pmcstat_stats.ps_callchain_dubious_frames++;
 734                 pmcr->pr_dubious_frames++;
 735                 return;
 736         }
 737
 738         /* Increase the call generation counter. */
 739         pmcpl_ct_samples_grow(&pmcpl_ct_callid);
 740         pmcpl_ct_callid.sb[pmcin]++;
 741
 742         /*
 743          * Iterate remaining addresses.
 744          */
 745         for (parent = pmcpl_ct_root, child = NULL; n >= 0; n--) {
 746                 child = pmcpl_ct_node_hash_lookup_pc(parent, ppm[n], cc[n],
 747                     pmcin);
 748                 if (child == NULL) {
 749                         pmcstat_stats.ps_callchain_dubious_frames++;
 750                         continue;
 751                 }
 752                 parent = child;
 753         }
 754
 755         /*
 756          * Increment the sample count for this PMC.
 757          */
 758         if (child != NULL) {
 759                 pmcpl_ct_samples_grow(&child->pct_samples);
 760                 child->pct_samples.sb[pmcin]++;
 761
 762                 /* Update per instruction sample if required. */
 763                 if (args.pa_ctdumpinstr)
 764                         pmcpl_ct_instr_add(child, pmcin, cc[0] -
 765                             (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
 766                              ppm[0]->ppm_image->pi_start));
 767         }
 768 }
 769
 770 /*
 771  * Print node self cost.
 772  */
 773
 774 static void
 775 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
 776 {
 777         int i, j, line;
 778         uintptr_t addr;
 779         struct pmcstat_symbol *sym;
 780         char sourcefile[PATH_MAX];
 781         char funcname[PATH_MAX];
 782
 783         /*
 784          * Object binary.
 785          */
 786 #ifdef PMCPL_CT_OPTIMIZEFN
 787         if (pmcpl_ct_prevfn != ct->pct_image->pi_fullpath) {
 788 #endif
 789                 pmcpl_ct_prevfn = ct->pct_image->pi_fullpath;
 790                 fprintf(args.pa_graphfile, "ob=%s\n",
 791                     pmcstat_string_unintern(pmcpl_ct_prevfn));
 792 #ifdef PMCPL_CT_OPTIMIZEFN
 793         }
 794 #endif
 795
 796         /*
 797          * Function name.
 798          */
 799         if (pmcstat_image_addr2line(ct->pct_image, ct->pct_func,
 800             sourcefile, sizeof(sourcefile), &line,
 801             funcname, sizeof(funcname))) {
 802                 fprintf(args.pa_graphfile, "fn=%s\n",
 803                     funcname);
 804         } else {
 805                 sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
 806                 if (sym != NULL)
 807                         fprintf(args.pa_graphfile, "fn=%s\n",
 808                             pmcstat_string_unintern(sym->ps_name));
 809                 else
 810                         fprintf(args.pa_graphfile, "fn=%p\n",
 811                             (void *)(ct->pct_image->pi_vaddr + ct->pct_func));
 812         }
 813
 814         /*
 815          * Self cost.
 816          */
 817         if (ct->pct_ninstr > 0) {
 818                 for (i = 0; i < ct->pct_ninstr; i++) {
 819                         addr = ct->pct_image->pi_vaddr +
 820                             ct->pct_instr[i].pctf_func;
 821                         line = 0;
 822                         if (pmcstat_image_addr2line(ct->pct_image, addr,
 823                             sourcefile, sizeof(sourcefile), &line,
 824                             funcname, sizeof(funcname)))
 825                                 fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
 826                         fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
 827                         for (j = 0; j<pmcstat_npmcs; j++)
 828                                 fprintf(args.pa_graphfile, " %u",
 829                                     PMCPL_CT_SAMPLE(j,
 830                                     &ct->pct_instr[i].pctf_samples));
 831                         fprintf(args.pa_graphfile, "\n");
 832                 }
 833         } else {
 834                 addr = ct->pct_image->pi_vaddr + ct->pct_func;
 835                 line = 0;
 836                 if (pmcstat_image_addr2line(ct->pct_image, addr,
 837                     sourcefile, sizeof(sourcefile), &line,
 838                     funcname, sizeof(funcname)))
 839                         fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
 840                 fprintf(args.pa_graphfile, "* *");
 841                 for (i = 0; i<pmcstat_npmcs ; i++)
 842                         fprintf(args.pa_graphfile, " %u",
 843                             PMCPL_CT_SAMPLE(i, &ct->pct_samples));
 844                 fprintf(args.pa_graphfile, "\n");
 845         }
 846 }
 847
 848 /*
 849  * Print node child cost.
 850  */
 851
 852 static void
 853 pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct)
 854 {
 855         int i, j, line;
 856         uintptr_t addr;
 857         struct pmcstat_symbol *sym;
 858         struct pmcpl_ct_node *child;
 859         char sourcefile[PATH_MAX];
 860         char funcname[PATH_MAX];
 861
 862         /*
 863          * Child cost.
 864          * TODO: attach child cost to the real position in the funtion.
 865          * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
 866          */
 867         for (i=0 ; i<ct->pct_narc; i++) {
 868                 child = ct->pct_arc[i].pcta_child;
 869
 870                 /* Object binary. */
 871 #ifdef PMCPL_CT_OPTIMIZEFN
 872                 if (pmcpl_ct_prevfn != child->pct_image->pi_fullpath) {
 873 #endif
 874                         pmcpl_ct_prevfn = child->pct_image->pi_fullpath;
 875                         fprintf(args.pa_graphfile, "cob=%s\n",
 876                             pmcstat_string_unintern(pmcpl_ct_prevfn));
 877 #if PMCPL_CT_OPTIMIZEFN
 878                 }
 879 #endif
 880                 /* Child function name. */
 881                 addr = child->pct_image->pi_vaddr + child->pct_func;
 882                 /* Child function source file. */
 883                 if (pmcstat_image_addr2line(child->pct_image, addr,
 884                     sourcefile, sizeof(sourcefile), &line,
 885                     funcname, sizeof(funcname))) {
 886                         fprintf(args.pa_graphfile, "cfn=%s\n", funcname);
 887                         fprintf(args.pa_graphfile, "cfl=%s\n", sourcefile);
 888                 } else {
 889                         sym = pmcstat_symbol_search(child->pct_image,
 890                             child->pct_func);
 891                         if (sym != NULL)
 892                                 fprintf(args.pa_graphfile, "cfn=%s\n",
 893                                     pmcstat_string_unintern(sym->ps_name));
 894                         else
 895                                 fprintf(args.pa_graphfile, "cfn=%p\n", (void *)addr);
 896                 }
 897
 898                 /* Child function address, line and call count. */
 899                 fprintf(args.pa_graphfile, "calls=%u %p %u\n",
 900                     ct->pct_arc[i].pcta_call, (void *)addr, line);
 901
 902                 if (ct->pct_image != NULL) {
 903                         /* Call address, line, sample. */
 904                         addr = ct->pct_image->pi_vaddr + ct->pct_func;
 905                         line = 0;
 906                         if (pmcstat_image_addr2line(ct->pct_image, addr, sourcefile,
 907                             sizeof(sourcefile), &line,
 908                             funcname, sizeof(funcname)))
 909                                 fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
 910                         else
 911                                 fprintf(args.pa_graphfile, "* *");
 912                 }
 913                 else
 914                         fprintf(args.pa_graphfile, "* *");
 915                 for (j = 0; j<pmcstat_npmcs; j++)
 916                         fprintf(args.pa_graphfile, " %u",
 917                             PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
 918                 fprintf(args.pa_graphfile, "\n");
 919         }
 920 }
 921
 922 /*
 923  * Clean the PMC name for Kcachegrind formula
 924  */
 925
 926 static void
 927 pmcpl_ct_fixup_pmcname(char *s)
 928 {
 929         char *p;
 930
 931         for (p = s; *p; p++)
 932                 if (!isalnum(*p))
 933                         *p = '_';
 934 }
 935
 936 /*
 937  * Print a calltree (KCachegrind) for all PMCs.
 938  */
 939
 940 static void
 941 pmcpl_ct_print(void)
 942 {
 943         int n, i;
 944         struct pmcpl_ct_node_hash *pch;
 945         struct pmcpl_ct_sample rsamples;
 946         char name[40];
 947
 948         pmcpl_ct_samples_root(&rsamples);
 949         pmcpl_ct_prevfn = NULL;
 950
 951         fprintf(args.pa_graphfile,
 952                 "version: 1\n"
 953                 "creator: pmcstat\n"
 954                 "positions: instr line\n"
 955                 "events:");
 956         for (i=0; i<pmcstat_npmcs; i++) {
 957                 snprintf(name, sizeof(name), "%s_%d",
 958                     pmcstat_pmcindex_to_name(i), i);
 959                 pmcpl_ct_fixup_pmcname(name);
 960                 fprintf(args.pa_graphfile, " %s", name);
 961         }
 962         fprintf(args.pa_graphfile, "\nsummary:");
 963         for (i=0; i<pmcstat_npmcs ; i++)
 964                 fprintf(args.pa_graphfile, " %u",
 965                     PMCPL_CT_SAMPLE(i, &rsamples));
 966         fprintf(args.pa_graphfile, "\n\n");
 967
 968         /*
 969          * Fake root node
 970          */
 971         fprintf(args.pa_graphfile, "ob=FreeBSD\n");
 972         fprintf(args.pa_graphfile, "fn=ROOT\n");
 973         fprintf(args.pa_graphfile, "* *");
 974         for (i = 0; i<pmcstat_npmcs ; i++)
 975                 fprintf(args.pa_graphfile, " 0");
 976         fprintf(args.pa_graphfile, "\n");
 977         pmcpl_ct_node_printchild(pmcpl_ct_root);
 978
 979         for (n = 0; n < PMCSTAT_NHASH; n++)
 980                 LIST_FOREACH(pch, &pmcpl_ct_node_hash[n], pch_next) {
 981                         pmcpl_ct_node_printself(pch->pch_ctnode);
 982                         pmcpl_ct_node_printchild(pch->pch_ctnode);
 983         }
 984
 985         pmcpl_ct_samples_free(&rsamples);
 986 }
 987
 988 int
 989 pmcpl_ct_configure(char *opt)
 990 {
 991
 992         if (strncmp(opt, "skiplink=", 9) == 0) {
 993                 pmcstat_skiplink = atoi(opt+9);
 994         } else
 995                 return (0);
 996
 997         return (1);
 998 }
 999
1000 int
1001 pmcpl_ct_init(void)
1002 {
1003         int i;
1004
1005         pmcpl_ct_prevfn = NULL;
1006         pmcpl_ct_root = pmcpl_ct_node_allocate(NULL, 0);
1007
1008         for (i = 0; i < PMCSTAT_NHASH; i++)
1009                 LIST_INIT(&pmcpl_ct_node_hash[i]);
1010
1011         pmcpl_ct_samples_init(&pmcpl_ct_callid);
1012
1013         return (0);
1014 }
1015
1016 void
1017 pmcpl_ct_shutdown(FILE *mf)
1018 {
1019         int i;
1020         struct pmcpl_ct_node_hash *pch, *pchtmp;
1021
1022         (void) mf;
1023
1024         if (args.pa_flags & FLAG_DO_CALLGRAPHS)
1025                 pmcpl_ct_print();
1026
1027         /*
1028          * Free memory.
1029          */
1030
1031         for (i = 0; i < PMCSTAT_NHASH; i++) {
1032                 LIST_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
1033                     pchtmp) {
1034                         pmcpl_ct_node_free(pch->pch_ctnode);
1035                         free(pch);
1036                 }
1037         }
1038
1039         pmcpl_ct_node_free(pmcpl_ct_root);
1040         pmcpl_ct_root = NULL;
1041
1042         pmcpl_ct_samples_free(&pmcpl_ct_callid);
1043 }
1044