diff options
Diffstat (limited to 'usr.sbin/pmcstat/pmcpl_calltree.c')
| -rw-r--r-- | usr.sbin/pmcstat/pmcpl_calltree.c | 1197 |
1 files changed, 1197 insertions, 0 deletions
diff --git a/usr.sbin/pmcstat/pmcpl_calltree.c b/usr.sbin/pmcstat/pmcpl_calltree.c new file mode 100644 index 0000000..3d0127d --- /dev/null +++ b/usr.sbin/pmcstat/pmcpl_calltree.c @@ -0,0 +1,1197 @@ +/*- + * Copyright (c) 2012, Fabien Thomas + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* + * Process hwpmc(4) samples as calltree. + * + * Output file format compatible with Kcachegrind (kdesdk). + * Handle top mode with a sorted tree display. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/param.h> +#include <sys/endian.h> +#include <sys/queue.h> + +#include <assert.h> +#include <curses.h> +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <fcntl.h> +#include <pmc.h> +#include <pmclog.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <sysexits.h> + +#include "pmcstat.h" +#include "pmcstat_log.h" +#include "pmcstat_top.h" +#include "pmcpl_calltree.h" + +#define PMCPL_CT_GROWSIZE 4 + +static int pmcstat_skiplink = 0; + +struct pmcpl_ct_node; + +/* Get the sample value for PMC a. */ +#define PMCPL_CT_SAMPLE(a, b) \ + ((a) < (b)->npmcs ? (b)->sb[a] : 0) + +/* Get the sample value in percent related to rsamples. */ +#define PMCPL_CT_SAMPLEP(a, b) \ + (PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a]) + +struct pmcpl_ct_sample { + int npmcs; /* Max pmc index available. */ + unsigned *sb; /* Sample buffer for 0..npmcs. */ +}; + +struct pmcpl_ct_arc { + struct pmcpl_ct_sample pcta_samples; + struct pmcpl_ct_sample pcta_callid; + unsigned pcta_call; + struct pmcpl_ct_node *pcta_child; +}; + +struct pmcpl_ct_instr { + uintfptr_t pctf_func; + struct pmcpl_ct_sample pctf_samples; +}; + +/* + * Each calltree node is tracked by a pmcpl_ct_node struct. + */ +struct pmcpl_ct_node { + struct pmcstat_image *pct_image; + uintfptr_t pct_func; + + struct pmcstat_symbol *pct_sym; + pmcstat_interned_string pct_ifl; + pmcstat_interned_string pct_ifn; + + struct pmcpl_ct_sample pct_samples; + + int pct_narc; + int pct_arc_c; + struct pmcpl_ct_arc *pct_arc; + + /* TODO: optimize for large number of items. */ + int pct_ninstr; + int pct_instr_c; + struct pmcpl_ct_instr *pct_instr; + +#define PMCPL_PCT_ADDR 0 +#define PMCPL_PCT_NAME 1 + char pct_type; +#define PMCPL_PCT_WHITE 0 +#define PMCPL_PCT_GREY 1 +#define PMCPL_PCT_BLACK 2 + char pct_color; +}; + +struct pmcpl_ct_node_hash { + struct pmcpl_ct_node *pch_ctnode; + STAILQ_ENTRY(pmcpl_ct_node_hash) pch_next; +}; + +static struct pmcpl_ct_sample pmcpl_ct_callid; + +#define PMCPL_CT_MAXCOL PMC_CALLCHAIN_DEPTH_MAX +#define PMCPL_CT_MAXLINE 1024 /* TODO: dynamic. */ + +struct pmcpl_ct_line { + unsigned ln_sum; + unsigned ln_index; +}; + +static struct pmcpl_ct_line pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1]; +static struct pmcpl_ct_node + *pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1]; + +/* + * All nodes indexed by function/image name are placed in a hash table. + */ +static STAILQ_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH]; + +/* + * Root node for the graph. + */ +static struct pmcpl_ct_node *pmcpl_ct_root; + +/* + * Prototypes + */ + +/* + * Initialize a samples. + */ + +static void +pmcpl_ct_samples_init(struct pmcpl_ct_sample *samples) +{ + + samples->npmcs = 0; + samples->sb = NULL; +} + +/* + * Free a samples. + */ + +static void +pmcpl_ct_samples_free(struct pmcpl_ct_sample *samples) +{ + + samples->npmcs = 0; + free(samples->sb); + samples->sb = NULL; +} + +/* + * Grow a sample block to store pmcstat_npmcs PMCs. + */ + +static void +pmcpl_ct_samples_grow(struct pmcpl_ct_sample *samples) +{ + int npmcs; + + /* Enough storage. */ + if (pmcstat_npmcs <= samples->npmcs) + return; + + npmcs = samples->npmcs + + max(pmcstat_npmcs - samples->npmcs, PMCPL_CT_GROWSIZE); + samples->sb = realloc(samples->sb, npmcs * sizeof(unsigned)); + if (samples->sb == NULL) + errx(EX_SOFTWARE, "ERROR: out of memory"); + bzero((char *)samples->sb + samples->npmcs * sizeof(unsigned), + (npmcs - samples->npmcs) * sizeof(unsigned)); + samples->npmcs = npmcs; +} + +/* + * Compute the sum of all root arcs. + */ + +static void +pmcpl_ct_samples_root(struct pmcpl_ct_sample *samples) +{ + int i, pmcin; + + pmcpl_ct_samples_init(samples); + pmcpl_ct_samples_grow(samples); + + for (i = 0; i < pmcpl_ct_root->pct_narc; i++) + for (pmcin = 0; pmcin < pmcstat_npmcs; pmcin++) + samples->sb[pmcin] += PMCPL_CT_SAMPLE(pmcin, + &pmcpl_ct_root->pct_arc[i].pcta_samples); +} + +/* + * Grow the arc table. + */ + +static void +pmcpl_ct_arc_grow(int cursize, int *maxsize, struct pmcpl_ct_arc **items) +{ + int nmaxsize; + + if (cursize < *maxsize) + return; + + nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE); + *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_arc)); + if (*items == NULL) + errx(EX_SOFTWARE, "ERROR: out of memory"); + bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_arc), + (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_arc)); + *maxsize = nmaxsize; +} + +/* + * Grow the instr table. + */ + +static void +pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items) +{ + int nmaxsize; + + if (cursize < *maxsize) + return; + + nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE); + *items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_instr)); + if (*items == NULL) + errx(EX_SOFTWARE, "ERROR: out of memory"); + bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_instr), + (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_instr)); + *maxsize = nmaxsize; +} + +/* + * Add a new instruction sample to given node. + */ + +static void +pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, + uintfptr_t pc, unsigned v) +{ + int i; + struct pmcpl_ct_instr *in; + + for (i = 0; i<ct->pct_ninstr; i++) { + if (ct->pct_instr[i].pctf_func == pc) { + in = &ct->pct_instr[i]; + pmcpl_ct_samples_grow(&in->pctf_samples); + in->pctf_samples.sb[pmcin] += v; + return; + } + } + + pmcpl_ct_instr_grow(ct->pct_ninstr, &ct->pct_instr_c, &ct->pct_instr); + in = &ct->pct_instr[ct->pct_ninstr]; + in->pctf_func = pc; + pmcpl_ct_samples_init(&in->pctf_samples); + pmcpl_ct_samples_grow(&in->pctf_samples); + in->pctf_samples.sb[pmcin] = v; + ct->pct_ninstr++; +} + +/* + * Allocate a new node. + */ + +static struct pmcpl_ct_node * +pmcpl_ct_node_allocate(void) +{ + struct pmcpl_ct_node *ct; + + if ((ct = malloc(sizeof(*ct))) == NULL) + err(EX_OSERR, "ERROR: Cannot allocate callgraph node"); + + pmcpl_ct_samples_init(&ct->pct_samples); + + ct->pct_sym = NULL; + ct->pct_image = NULL; + ct->pct_func = 0; + + ct->pct_narc = 0; + ct->pct_arc_c = 0; + ct->pct_arc = NULL; + + ct->pct_ninstr = 0; + ct->pct_instr_c = 0; + ct->pct_instr = NULL; + + ct->pct_color = PMCPL_PCT_WHITE; + + return (ct); +} + +/* + * Free a node. + */ + +static void +pmcpl_ct_node_free(struct pmcpl_ct_node *ct) +{ + int i; + + for (i = 0; i < ct->pct_narc; i++) { + pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_samples); + pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_callid); + } + + pmcpl_ct_samples_free(&ct->pct_samples); + free(ct->pct_arc); + free(ct->pct_instr); + free(ct); +} + +/* + * Clear the graph tag on each node. + */ +static void +pmcpl_ct_node_cleartag(void) +{ + int i; + struct pmcpl_ct_node_hash *pch; + + for (i = 0; i < PMCSTAT_NHASH; i++) + STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next) + pch->pch_ctnode->pct_color = PMCPL_PCT_WHITE; + + pmcpl_ct_root->pct_color = PMCPL_PCT_WHITE; +} + +/* + * Print the callchain line by line with maximum cost at top. + */ + +static int +pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct, + struct pmcpl_ct_sample *rsamples, int x, int *y) +{ + int i, terminal; + struct pmcpl_ct_arc *arc; + + if (ct->pct_color == PMCPL_PCT_GREY) + return 0; + + if (x >= PMCPL_CT_MAXCOL) { + pmcpl_ct_topscreen[x][*y] = NULL; + return 1; + } + pmcpl_ct_topscreen[x][*y] = ct; + + /* + * Check if this is a terminal node. + * We need to check that some samples exist + * for at least one arc for that PMC. + */ + terminal = 1; + for (i = 0; i < ct->pct_narc; i++) { + arc = &ct->pct_arc[i]; + if (arc->pcta_child->pct_color != PMCPL_PCT_GREY && + PMCPL_CT_SAMPLE(pmcin, + &arc->pcta_samples) != 0 && + PMCPL_CT_SAMPLEP(pmcin, + &arc->pcta_samples) > pmcstat_threshold) { + terminal = 0; + break; + } + } + + if (ct->pct_narc == 0 || terminal) { + pmcpl_ct_topscreen[x+1][*y] = NULL; + if (*y >= PMCPL_CT_MAXLINE) + return 1; + *y = *y + 1; + for (i=0; i < x; i++) + pmcpl_ct_topscreen[i][*y] = + pmcpl_ct_topscreen[i][*y - 1]; + return 0; + } + + ct->pct_color = PMCPL_PCT_GREY; + for (i = 0; i < ct->pct_narc; i++) { + if (PMCPL_CT_SAMPLE(pmcin, + &ct->pct_arc[i].pcta_samples) == 0) + continue; + if (PMCPL_CT_SAMPLEP(pmcin, + &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) { + if (pmcpl_ct_node_dumptop(pmcin, + ct->pct_arc[i].pcta_child, + rsamples, x+1, y)) { + ct->pct_color = PMCPL_PCT_BLACK; + return 1; + } + } + } + ct->pct_color = PMCPL_PCT_BLACK; + + return 0; +} + +/* + * Compare two top line by sum. + */ +static int +pmcpl_ct_line_compare(const void *a, const void *b) +{ + const struct pmcpl_ct_line *ct1, *ct2; + + ct1 = (const struct pmcpl_ct_line *) a; + ct2 = (const struct pmcpl_ct_line *) b; + + /* Sort in reverse order */ + if (ct1->ln_sum < ct2->ln_sum) + return (1); + if (ct1->ln_sum > ct2->ln_sum) + return (-1); + return (0); +} + +/* + * Format and display given PMC index. + */ + +static void +pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy) +{ +#undef TS +#undef TSI +#define TS(x, y) (pmcpl_ct_topscreen[x][y]) +#define TSI(x, y) (pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index]) + + int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y; + float v; + char ns[30], vs[10], is[20]; + struct pmcpl_ct_node *ct; + const char *space = " "; + + /* + * Sort by line cost. + */ + for (y = 0; ; y++) { + ct = TS(1, y); + if (ct == NULL) + break; + + pmcpl_ct_topmax[y].ln_sum = 0; + pmcpl_ct_topmax[y].ln_index = y; + for (x = 1; TS(x, y) != NULL; x++) { + pmcpl_ct_topmax[y].ln_sum += + PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples); + } + } + qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]), + pmcpl_ct_line_compare); + pmcpl_ct_topmax[y].ln_index = y; + + for (y = 0; y < maxy; y++) { + ct = TSI(1, y); + if (ct == NULL) + break; + + if (y > 0) + PMCSTAT_PRINTW("\n"); + + /* Output sum. */ + v = pmcpl_ct_topmax[y].ln_sum * 100.0 / + rsamples->sb[pmcin]; + snprintf(vs, sizeof(vs), "%.1f", v); + v_attrs = PMCSTAT_ATTRPERCENT(v); + PMCSTAT_ATTRON(v_attrs); + PMCSTAT_PRINTW("%5.5s ", vs); + PMCSTAT_ATTROFF(v_attrs); + + width = indentwidth = 5 + 1; + + for (x = 1; (ct = TSI(x, y)) != NULL; x++) { + + vs[0] = '\0'; vs_len = 0; + is[0] = '\0'; is_len = 0; + + /* Format value. */ + v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples); + if (v > pmcstat_threshold) + vs_len = snprintf(vs, sizeof(vs), + "(%.1f%%)", v); + v_attrs = PMCSTAT_ATTRPERCENT(v); + + if (pmcstat_skiplink && v <= pmcstat_threshold) { + strlcpy(ns, ".", sizeof(ns)); + ns_len = 1; + } else { + if (ct->pct_sym != NULL) { + ns_len = snprintf(ns, sizeof(ns), "%s", + pmcstat_string_unintern(ct->pct_sym->ps_name)); + } else + ns_len = snprintf(ns, sizeof(ns), "%p", + (void *)ct->pct_func); + + /* Format image. */ + if (x == 1 || + TSI(x-1, y)->pct_image != ct->pct_image) + is_len = snprintf(is, sizeof(is), "@%s", + pmcstat_string_unintern(ct->pct_image->pi_name)); + + /* Check for line wrap. */ + width += ns_len + is_len + vs_len + 1; + } + if (width >= pmcstat_displaywidth) { + maxy--; + if (y >= maxy) + break; + PMCSTAT_PRINTW("\n%*s", indentwidth, space); + width = indentwidth + ns_len + is_len + vs_len; + } + + PMCSTAT_ATTRON(v_attrs); + PMCSTAT_PRINTW("%s%s%s ", ns, is, vs); + PMCSTAT_ATTROFF(v_attrs); + } + } +} + +/* + * Output top mode snapshot. + */ + +void +pmcpl_ct_topdisplay(void) +{ + int y; + struct pmcpl_ct_sample r, *rsamples; + + rsamples = &r; + pmcpl_ct_samples_root(rsamples); + pmcpl_ct_node_cleartag(); + + PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE"); + + y = 0; + if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter, + pmcpl_ct_root, rsamples, 0, &y)) + PMCSTAT_PRINTW("...\n"); + pmcpl_ct_topscreen[1][y] = NULL; + + pmcpl_ct_node_printtop(rsamples, + pmcstat_pmcinfilter, pmcstat_displayheight - 2); + + pmcpl_ct_samples_free(rsamples); +} + +/* + * Handle top mode keypress. + */ + +int +pmcpl_ct_topkeypress(int c, WINDOW *w) +{ + + switch (c) { + case 'f': + pmcstat_skiplink = !pmcstat_skiplink; + wprintw(w, "skip empty link %s", + pmcstat_skiplink ? "on" : "off"); + break; + } + + return 0; +} + +/* + * Look for a callgraph node associated with pmc `pmcid' in the global + * hash table that corresponds to the given `pc' value in the process map + * `ppm'. + */ + +static void +pmcpl_ct_node_update(struct pmcpl_ct_node *parent, + struct pmcpl_ct_node *child, int pmcin, unsigned v, int cd) +{ + struct pmcpl_ct_arc *arc; + int i; + + assert(parent != NULL); + + /* + * Find related arc in parent node and + * increment the sample count. + */ + for (i = 0; i < parent->pct_narc; i++) { + if (parent->pct_arc[i].pcta_child == child) { + arc = &parent->pct_arc[i]; + pmcpl_ct_samples_grow(&arc->pcta_samples); + arc->pcta_samples.sb[pmcin] += v; + /* Estimate call count. */ + if (cd) { + pmcpl_ct_samples_grow(&arc->pcta_callid); + if (pmcpl_ct_callid.sb[pmcin] - + arc->pcta_callid.sb[pmcin] > 1) + arc->pcta_call++; + arc->pcta_callid.sb[pmcin] = + pmcpl_ct_callid.sb[pmcin]; + } + return; + } + } + + /* + * No arc found for us, add ourself to the parent. + */ + pmcpl_ct_arc_grow(parent->pct_narc, + &parent->pct_arc_c, &parent->pct_arc); + arc = &parent->pct_arc[parent->pct_narc]; + pmcpl_ct_samples_grow(&arc->pcta_samples); + arc->pcta_samples.sb[pmcin] = v; + arc->pcta_call = 1; + if (cd) { + pmcpl_ct_samples_grow(&arc->pcta_callid); + arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin]; + } + arc->pcta_child = child; + parent->pct_narc++; +} + +/* + * Lookup by image/pc. + */ + +static struct pmcpl_ct_node * +pmcpl_ct_node_hash_lookup(struct pmcstat_image *image, uintfptr_t pc, + struct pmcstat_symbol *sym, char *fl, char *fn) +{ + int i; + unsigned int hash; + struct pmcpl_ct_node *ct; + struct pmcpl_ct_node_hash *h; + pmcstat_interned_string ifl, ifn; + + if (fn != NULL) { + ifl = pmcstat_string_intern(fl); + ifn = pmcstat_string_intern(fn); + } else { + ifl = 0; + ifn = 0; + } + + for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++) + hash += (pc >> i) & 0xFF; + + hash &= PMCSTAT_HASH_MASK; + + STAILQ_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) { + ct = h->pch_ctnode; + + assert(ct != NULL); + + if (ct->pct_image == image && ct->pct_func == pc) { + if (fn == NULL) + return (ct); + if (ct->pct_type == PMCPL_PCT_NAME && + ct->pct_ifl == ifl && ct->pct_ifn == ifn) + return (ct); + } + } + + /* + * We haven't seen this (pmcid, pc) tuple yet, so allocate a + * new callgraph node and a new hash table entry for it. + */ + ct = pmcpl_ct_node_allocate(); + if ((h = malloc(sizeof(*h))) == NULL) + err(EX_OSERR, "ERROR: Could not allocate callgraph node"); + + if (fn != NULL) { + ct->pct_type = PMCPL_PCT_NAME; + ct->pct_ifl = ifl; + ct->pct_ifn = ifn; + } else + ct->pct_type = PMCPL_PCT_ADDR; + ct->pct_image = image; + ct->pct_func = pc; + ct->pct_sym = sym; + + h->pch_ctnode = ct; + STAILQ_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next); + return (ct); +} + +/* + * Record a callchain. + */ + +void +pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr, + uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu) +{ + int i, n, pmcin; + uintfptr_t pc, loadaddress; + struct pmcstat_image *image; + struct pmcstat_symbol *sym; + struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX]; + struct pmcstat_process *km; + struct pmcpl_ct_node *ct; + struct pmcpl_ct_node *ctl[PMC_CALLCHAIN_DEPTH_MAX+1]; + + (void) cpu; + + assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX); + + /* Get the PMC index. */ + pmcin = pmcr->pr_pmcin; + + /* + * Validate mapping for the callchain. + * Go from bottom to first invalid entry. + */ + km = pmcstat_kernproc; + for (n = 0; n < (int)nsamples; n++) { + ppm[n] = pmcstat_process_find_map(usermode ? + pp : km, cc[n]); + if (ppm[n] == NULL) { + /* Detect full frame capture (kernel + user). */ + if (!usermode) { + ppm[n] = pmcstat_process_find_map(pp, cc[n]); + if (ppm[n] != NULL) + km = pp; + } + } + if (ppm[n] == NULL) + break; + } + if (n-- == 0) { + pmcstat_stats.ps_callchain_dubious_frames++; + pmcr->pr_dubious_frames++; + return; + } + + /* Increase the call generation counter. */ + pmcpl_ct_samples_grow(&pmcpl_ct_callid); + pmcpl_ct_callid.sb[pmcin]++; + + /* + * Build node list. + */ + ctl[0] = pmcpl_ct_root; + for (i = 1; n >= 0; n--) { + image = ppm[n]->ppm_image; + loadaddress = ppm[n]->ppm_lowpc + + image->pi_vaddr - image->pi_start; + /* Convert to an offset in the image. */ + pc = cc[n] - loadaddress; + /* + * Try determine the function at this offset. If we can't + * find a function round leave the `pc' value alone. + */ + if ((sym = pmcstat_symbol_search(image, pc)) != NULL) + pc = sym->ps_start; + else + pmcstat_stats.ps_samples_unknown_function++; + + ct = pmcpl_ct_node_hash_lookup(image, pc, sym, NULL, NULL); + if (ct == NULL) { + pmcstat_stats.ps_callchain_dubious_frames++; + continue; + } + ctl[i++] = ct; + } + /* No valid node found. */ + if (i == 1) + return; + n = i; + + ct = ctl[0]; + for (i = 1; i < n; i++) + pmcpl_ct_node_update(ctl[i-1], ctl[i], pmcin, 1, 1); + + /* + * Increment the sample count for this PMC. + */ + pmcpl_ct_samples_grow(&ctl[n-1]->pct_samples); + ctl[n-1]->pct_samples.sb[pmcin]++; + + /* Update per instruction sample if required. */ + if (args.pa_ctdumpinstr) + pmcpl_ct_instr_add(ctl[n-1], pmcin, cc[0] - + (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr - + ppm[0]->ppm_image->pi_start), 1); +} + +/* + * Print node child cost. + */ + +static void +pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct, uintfptr_t paddr, + int pline) +{ + int i, j, line; + uintfptr_t addr; + struct pmcpl_ct_node *child; + char sourcefile[PATH_MAX]; + char funcname[PATH_MAX]; + + /* + * Child cost. + * TODO: attach child cost to the real position in the funtion. + * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost> + */ + for (i=0 ; i<ct->pct_narc; i++) { + child = ct->pct_arc[i].pcta_child; + /* Object binary. */ + fprintf(args.pa_graphfile, "cob=%s\n", + pmcstat_string_unintern(child->pct_image->pi_fullpath)); + /* Child function name. */ + addr = child->pct_image->pi_vaddr + child->pct_func; + line = 0; + /* Child function source file. */ + if (child->pct_type == PMCPL_PCT_NAME) { + fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n", + pmcstat_string_unintern(child->pct_ifl), + pmcstat_string_unintern(child->pct_ifn)); + } else if (pmcstat_image_addr2line(child->pct_image, addr, + sourcefile, sizeof(sourcefile), &line, + funcname, sizeof(funcname))) { + fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n", + sourcefile, funcname); + } else { + if (child->pct_sym != NULL) + fprintf(args.pa_graphfile, + "cfi=???\ncfn=%s\n", + pmcstat_string_unintern( + child->pct_sym->ps_name)); + else + fprintf(args.pa_graphfile, + "cfi=???\ncfn=%p\n", (void *)addr); + } + + /* Child function address, line and call count. */ + fprintf(args.pa_graphfile, "calls=%u %p %u\n", + ct->pct_arc[i].pcta_call, (void *)addr, line); + + /* + * Call address, line, sample. + * TODO: Associate call address to the right location. + */ + fprintf(args.pa_graphfile, "%p %u", (void *)paddr, pline); + for (j = 0; j<pmcstat_npmcs; j++) + fprintf(args.pa_graphfile, " %u", + PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples)); + fprintf(args.pa_graphfile, "\n"); + } +} + +/* + * Print node self cost. + */ + +static void +pmcpl_ct_node_printself(struct pmcpl_ct_node *ct) +{ + int i, j, fline, line; + uintfptr_t faddr, addr; + char sourcefile[PATH_MAX]; + char funcname[PATH_MAX]; + + /* + * Object binary. + */ + fprintf(args.pa_graphfile, "ob=%s\n", + pmcstat_string_unintern(ct->pct_image->pi_fullpath)); + + /* + * Function name. + */ + faddr = ct->pct_image->pi_vaddr + ct->pct_func; + fline = 0; + if (ct->pct_type == PMCPL_PCT_NAME) { + fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n", + pmcstat_string_unintern(ct->pct_ifl), + pmcstat_string_unintern(ct->pct_ifn)); + } else if (pmcstat_image_addr2line(ct->pct_image, faddr, + sourcefile, sizeof(sourcefile), &fline, + funcname, sizeof(funcname))) { + fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n", + sourcefile, funcname); + } else { + if (ct->pct_sym != NULL) + fprintf(args.pa_graphfile, "fl=???\nfn=%s\n", + pmcstat_string_unintern(ct->pct_sym->ps_name)); + else + fprintf(args.pa_graphfile, "fl=???\nfn=%p\n", + (void *)(ct->pct_image->pi_vaddr + ct->pct_func)); + } + + /* + * Self cost. + */ + if (ct->pct_ninstr > 0) { + /* + * Per location cost. + */ + for (i = 0; i < ct->pct_ninstr; i++) { + addr = ct->pct_image->pi_vaddr + + ct->pct_instr[i].pctf_func; + line = 0; + pmcstat_image_addr2line(ct->pct_image, addr, + sourcefile, sizeof(sourcefile), &line, + funcname, sizeof(funcname)); + fprintf(args.pa_graphfile, "%p %u", + (void *)addr, line); + for (j = 0; j<pmcstat_npmcs; j++) + fprintf(args.pa_graphfile, " %u", + PMCPL_CT_SAMPLE(j, + &ct->pct_instr[i].pctf_samples)); + fprintf(args.pa_graphfile, "\n"); + } + } else { + /* Global cost function cost. */ + fprintf(args.pa_graphfile, "%p %u", (void *)faddr, fline); + for (i = 0; i<pmcstat_npmcs ; i++) + fprintf(args.pa_graphfile, " %u", + PMCPL_CT_SAMPLE(i, &ct->pct_samples)); + fprintf(args.pa_graphfile, "\n"); + } + + pmcpl_ct_node_printchild(ct, faddr, fline); +} + +static void +pmcpl_ct_printnode(struct pmcpl_ct_node *ct) +{ + int i; + + if (ct == pmcpl_ct_root) { + fprintf(args.pa_graphfile, "fn=root\n"); + fprintf(args.pa_graphfile, "0x0 1"); + for (i = 0; i<pmcstat_npmcs ; i++) + fprintf(args.pa_graphfile, " 0"); + fprintf(args.pa_graphfile, "\n"); + pmcpl_ct_node_printchild(ct, 0, 0); + } else + pmcpl_ct_node_printself(ct); +} + +/* + * Breadth first traversal. + */ + +static void +pmcpl_ct_bfs(struct pmcpl_ct_node *ct) +{ + int i; + struct pmcpl_ct_node_hash *pch, *pchc; + struct pmcpl_ct_node *child; + STAILQ_HEAD(,pmcpl_ct_node_hash) q; + + STAILQ_INIT(&q); + if ((pch = malloc(sizeof(*pch))) == NULL) + err(EX_OSERR, "ERROR: Cannot allocate queue"); + pch->pch_ctnode = ct; + STAILQ_INSERT_TAIL(&q, pch, pch_next); + ct->pct_color = PMCPL_PCT_BLACK; + + while (!STAILQ_EMPTY(&q)) { + pch = STAILQ_FIRST(&q); + STAILQ_REMOVE_HEAD(&q, pch_next); + pmcpl_ct_printnode(pch->pch_ctnode); + for (i = 0; i<pch->pch_ctnode->pct_narc; i++) { + child = pch->pch_ctnode->pct_arc[i].pcta_child; + if (child->pct_color == PMCPL_PCT_WHITE) { + child->pct_color = PMCPL_PCT_BLACK; + if ((pchc = malloc(sizeof(*pchc))) == NULL) + err(EX_OSERR, + "ERROR: Cannot allocate queue"); + pchc->pch_ctnode = child; + STAILQ_INSERT_TAIL(&q, pchc, pch_next); + } + } + free(pch); + } +} + +/* + * Detect and fix inlined location. + */ + +static void +_pmcpl_ct_expand_inline(struct pmcpl_ct_node *ct) +{ + int i, j; + unsigned fline, line, v; + uintfptr_t faddr, addr, pc; + char sourcefile[PATH_MAX]; + char ffuncname[PATH_MAX], funcname[PATH_MAX]; + char buffer[PATH_MAX]; + struct pmcpl_ct_node *child; + + /* + * Resolve parent and compare to each instr location. + */ + faddr = ct->pct_image->pi_vaddr + ct->pct_func; + fline = 0; + if (!pmcstat_image_addr2line(ct->pct_image, faddr, + sourcefile, sizeof(sourcefile), &fline, + ffuncname, sizeof(ffuncname))) + return; + + for (i = 0; i < ct->pct_ninstr; i++) { + addr = ct->pct_image->pi_vaddr + + ct->pct_instr[i].pctf_func; + line = 0; + if (!pmcstat_image_addr2line(ct->pct_image, addr, + sourcefile, sizeof(sourcefile), &line, + funcname, sizeof(funcname))) + continue; + + if (strcmp(funcname, ffuncname) == 0) + continue; + + /* + * - Lookup/create inline node by function name. + * - Move instr PMCs to the inline node. + * - Link nodes. + * The lookup create a specific node per image/pc. + */ + if (args.pa_verbosity >= 2) + fprintf(args.pa_printfile, + "WARNING: inlined function at %p %s in %s\n", + (void *)addr, funcname, ffuncname); + + snprintf(buffer, sizeof(buffer), "%s@%s", + funcname, ffuncname); + child = pmcpl_ct_node_hash_lookup(ct->pct_image, + ct->pct_func, ct->pct_sym, sourcefile, buffer); + assert(child != NULL); + pc = ct->pct_instr[i].pctf_func; + for (j = 0; j<pmcstat_npmcs; j++) { + v = PMCPL_CT_SAMPLE(j, + &ct->pct_instr[i].pctf_samples); + if (v == 0) + continue; + pmcpl_ct_instr_add(child, j, pc, v); + pmcpl_ct_node_update(ct, child, j, v, 0); + if (j < ct->pct_samples.npmcs) + ct->pct_samples.sb[j] -= + ct->pct_instr[i].pctf_samples.sb[j]; + ct->pct_instr[i].pctf_samples.sb[j] = 0; + } + } +} + +static void +pmcpl_ct_expand_inline(void) +{ + int i; + struct pmcpl_ct_node_hash *pch; + + if (!args.pa_ctdumpinstr) + return; + + for (i = 0; i < PMCSTAT_NHASH; i++) + STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next) + if (pch->pch_ctnode->pct_type == PMCPL_PCT_ADDR) + _pmcpl_ct_expand_inline(pch->pch_ctnode); +} + +/* + * Clean the PMC name for Kcachegrind formula + */ + +static void +pmcpl_ct_fixup_pmcname(char *s) +{ + char *p; + + for (p = s; *p; p++) + if (!isalnum(*p)) + *p = '_'; +} + +/* + * Print a calltree (KCachegrind) for all PMCs. + */ + +static void +pmcpl_ct_print(void) +{ + int i; + char name[40]; + struct pmcpl_ct_sample rsamples; + + pmcpl_ct_samples_root(&rsamples); + pmcpl_ct_expand_inline(); + + fprintf(args.pa_graphfile, + "version: 1\n" + "creator: pmcstat\n" + "positions: instr line\n" + "events:"); + for (i=0; i<pmcstat_npmcs; i++) { + snprintf(name, sizeof(name), "%s_%d", + pmcstat_pmcindex_to_name(i), i); + pmcpl_ct_fixup_pmcname(name); + fprintf(args.pa_graphfile, " %s", name); + } + fprintf(args.pa_graphfile, "\nsummary:"); + for (i=0; i<pmcstat_npmcs ; i++) + fprintf(args.pa_graphfile, " %u", + PMCPL_CT_SAMPLE(i, &rsamples)); + fprintf(args.pa_graphfile, "\n"); + pmcpl_ct_bfs(pmcpl_ct_root); + pmcpl_ct_samples_free(&rsamples); +} + +int +pmcpl_ct_configure(char *opt) +{ + + if (strncmp(opt, "skiplink=", 9) == 0) { + pmcstat_skiplink = atoi(opt+9); + } else + return (0); + + return (1); +} + +int +pmcpl_ct_init(void) +{ + int i; + + pmcpl_ct_root = pmcpl_ct_node_allocate(); + + for (i = 0; i < PMCSTAT_NHASH; i++) + STAILQ_INIT(&pmcpl_ct_node_hash[i]); + + pmcpl_ct_samples_init(&pmcpl_ct_callid); + + return (0); +} + +void +pmcpl_ct_shutdown(FILE *mf) +{ + int i; + struct pmcpl_ct_node_hash *pch, *pchtmp; + + (void) mf; + + if (args.pa_flags & FLAG_DO_CALLGRAPHS) + pmcpl_ct_print(); + + /* + * Free memory. + */ + + for (i = 0; i < PMCSTAT_NHASH; i++) { + STAILQ_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next, + pchtmp) { + pmcpl_ct_node_free(pch->pch_ctnode); + free(pch); + } + } + + pmcpl_ct_node_free(pmcpl_ct_root); + pmcpl_ct_root = NULL; + + pmcpl_ct_samples_free(&pmcpl_ct_callid); +} + |
