usr.sbin/pmcstat/pmcpl_calltree.c

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