2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2012, Fabien Thomas
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * Process hwpmc(4) samples as calltree.
32 * Output file format compatible with Kcachegrind (kdesdk).
33 * Handle top mode with a sorted tree display.
36 #include <sys/cdefs.h>
37 __FBSDID("$FreeBSD$");
39 #include <sys/param.h>
40 #include <sys/endian.h>
41 #include <sys/queue.h>
59 #include "pmcstat_log.h"
60 #include "pmcstat_top.h"
61 #include "pmcpl_calltree.h"
63 #define min(A,B) ((A) < (B) ? (A) : (B))
64 #define max(A,B) ((A) > (B) ? (A) : (B))
66 #define PMCPL_CT_GROWSIZE 4
68 static int pmcstat_skiplink = 0;
72 /* Get the sample value for PMC a. */
73 #define PMCPL_CT_SAMPLE(a, b) \
74 ((a) < (b)->npmcs ? (b)->sb[a] : 0)
76 /* Get the sample value in percent related to rsamples. */
77 #define PMCPL_CT_SAMPLEP(a, b) \
78 (PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a])
80 struct pmcpl_ct_sample {
81 int npmcs; /* Max pmc index available. */
82 unsigned *sb; /* Sample buffer for 0..npmcs. */
86 struct pmcpl_ct_sample pcta_samples;
87 struct pmcpl_ct_sample pcta_callid;
89 struct pmcpl_ct_node *pcta_child;
92 struct pmcpl_ct_instr {
94 struct pmcpl_ct_sample pctf_samples;
98 * Each calltree node is tracked by a pmcpl_ct_node struct.
100 struct pmcpl_ct_node {
101 struct pmcstat_image *pct_image;
104 struct pmcstat_symbol *pct_sym;
105 pmcstat_interned_string pct_ifl;
106 pmcstat_interned_string pct_ifn;
108 struct pmcpl_ct_sample pct_samples;
112 struct pmcpl_ct_arc *pct_arc;
114 /* TODO: optimize for large number of items. */
117 struct pmcpl_ct_instr *pct_instr;
119 #define PMCPL_PCT_ADDR 0
120 #define PMCPL_PCT_NAME 1
122 #define PMCPL_PCT_WHITE 0
123 #define PMCPL_PCT_GREY 1
124 #define PMCPL_PCT_BLACK 2
128 struct pmcpl_ct_node_hash {
129 struct pmcpl_ct_node *pch_ctnode;
130 STAILQ_ENTRY(pmcpl_ct_node_hash) pch_next;
133 static struct pmcpl_ct_sample pmcpl_ct_callid;
135 #define PMCPL_CT_MAXCOL PMC_CALLCHAIN_DEPTH_MAX
136 #define PMCPL_CT_MAXLINE 1024 /* TODO: dynamic. */
138 struct pmcpl_ct_line {
143 static struct pmcpl_ct_line pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1];
144 static struct pmcpl_ct_node
145 *pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1];
148 * All nodes indexed by function/image name are placed in a hash table.
150 static STAILQ_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH];
153 * Root node for the graph.
155 static struct pmcpl_ct_node *pmcpl_ct_root;
162 * Initialize a samples.
166 pmcpl_ct_samples_init(struct pmcpl_ct_sample *samples)
178 pmcpl_ct_samples_free(struct pmcpl_ct_sample *samples)
187 * Grow a sample block to store pmcstat_npmcs PMCs.
191 pmcpl_ct_samples_grow(struct pmcpl_ct_sample *samples)
195 /* Enough storage. */
196 if (pmcstat_npmcs <= samples->npmcs)
199 npmcs = samples->npmcs +
200 max(pmcstat_npmcs - samples->npmcs, PMCPL_CT_GROWSIZE);
201 samples->sb = reallocarray(samples->sb, npmcs, sizeof(unsigned));
202 if (samples->sb == NULL)
203 errx(EX_SOFTWARE, "ERROR: out of memory");
204 bzero((char *)samples->sb + samples->npmcs * sizeof(unsigned),
205 (npmcs - samples->npmcs) * sizeof(unsigned));
206 samples->npmcs = npmcs;
210 * Compute the sum of all root arcs.
214 pmcpl_ct_samples_root(struct pmcpl_ct_sample *samples)
218 pmcpl_ct_samples_init(samples);
219 pmcpl_ct_samples_grow(samples);
221 for (i = 0; i < pmcpl_ct_root->pct_narc; i++)
222 for (pmcin = 0; pmcin < pmcstat_npmcs; pmcin++)
223 samples->sb[pmcin] += PMCPL_CT_SAMPLE(pmcin,
224 &pmcpl_ct_root->pct_arc[i].pcta_samples);
228 * Grow the arc table.
232 pmcpl_ct_arc_grow(int cursize, int *maxsize, struct pmcpl_ct_arc **items)
234 unsigned int nmaxsize;
236 if (cursize < *maxsize)
239 nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
240 *items = reallocarray(*items, nmaxsize, sizeof(struct pmcpl_ct_arc));
242 errx(EX_SOFTWARE, "ERROR: out of memory");
243 bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_arc),
244 (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_arc));
249 * Grow the instr table.
253 pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items)
255 unsigned int nmaxsize;
257 if (cursize < *maxsize)
260 nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
261 *items = reallocarray(*items, nmaxsize, sizeof(struct pmcpl_ct_instr));
263 errx(EX_SOFTWARE, "ERROR: out of memory");
264 bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_instr),
265 (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_instr));
270 * Add a new instruction sample to given node.
274 pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin,
275 uintfptr_t pc, unsigned v)
278 struct pmcpl_ct_instr *in;
280 for (i = 0; i<ct->pct_ninstr; i++) {
281 if (ct->pct_instr[i].pctf_func == pc) {
282 in = &ct->pct_instr[i];
283 pmcpl_ct_samples_grow(&in->pctf_samples);
284 in->pctf_samples.sb[pmcin] += v;
289 pmcpl_ct_instr_grow(ct->pct_ninstr, &ct->pct_instr_c, &ct->pct_instr);
290 in = &ct->pct_instr[ct->pct_ninstr];
292 pmcpl_ct_samples_init(&in->pctf_samples);
293 pmcpl_ct_samples_grow(&in->pctf_samples);
294 in->pctf_samples.sb[pmcin] = v;
299 * Allocate a new node.
302 static struct pmcpl_ct_node *
303 pmcpl_ct_node_allocate(void)
305 struct pmcpl_ct_node *ct;
307 if ((ct = malloc(sizeof(*ct))) == NULL)
308 err(EX_OSERR, "ERROR: Cannot allocate callgraph node");
310 pmcpl_ct_samples_init(&ct->pct_samples);
313 ct->pct_image = NULL;
322 ct->pct_instr = NULL;
324 ct->pct_color = PMCPL_PCT_WHITE;
334 pmcpl_ct_node_free(struct pmcpl_ct_node *ct)
338 for (i = 0; i < ct->pct_narc; i++) {
339 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_samples);
340 pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_callid);
343 pmcpl_ct_samples_free(&ct->pct_samples);
350 * Clear the graph tag on each node.
353 pmcpl_ct_node_cleartag(void)
356 struct pmcpl_ct_node_hash *pch;
358 for (i = 0; i < PMCSTAT_NHASH; i++)
359 STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
360 pch->pch_ctnode->pct_color = PMCPL_PCT_WHITE;
362 pmcpl_ct_root->pct_color = PMCPL_PCT_WHITE;
366 * Print the callchain line by line with maximum cost at top.
370 pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
371 struct pmcpl_ct_sample *rsamples, int x, int *y)
374 struct pmcpl_ct_arc *arc;
376 if (ct->pct_color == PMCPL_PCT_GREY)
379 if (x >= PMCPL_CT_MAXCOL) {
380 pmcpl_ct_topscreen[x][*y] = NULL;
383 pmcpl_ct_topscreen[x][*y] = ct;
386 * Check if this is a terminal node.
387 * We need to check that some samples exist
388 * for at least one arc for that PMC.
391 for (i = 0; i < ct->pct_narc; i++) {
392 arc = &ct->pct_arc[i];
393 if (arc->pcta_child->pct_color != PMCPL_PCT_GREY &&
394 PMCPL_CT_SAMPLE(pmcin,
395 &arc->pcta_samples) != 0 &&
396 PMCPL_CT_SAMPLEP(pmcin,
397 &arc->pcta_samples) > pmcstat_threshold) {
403 if (ct->pct_narc == 0 || terminal) {
404 pmcpl_ct_topscreen[x+1][*y] = NULL;
405 if (*y >= PMCPL_CT_MAXLINE)
408 for (i=0; i < x; i++)
409 pmcpl_ct_topscreen[i][*y] =
410 pmcpl_ct_topscreen[i][*y - 1];
414 ct->pct_color = PMCPL_PCT_GREY;
415 for (i = 0; i < ct->pct_narc; i++) {
416 if (PMCPL_CT_SAMPLE(pmcin,
417 &ct->pct_arc[i].pcta_samples) == 0)
419 if (PMCPL_CT_SAMPLEP(pmcin,
420 &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) {
421 if (pmcpl_ct_node_dumptop(pmcin,
422 ct->pct_arc[i].pcta_child,
424 ct->pct_color = PMCPL_PCT_BLACK;
429 ct->pct_color = PMCPL_PCT_BLACK;
435 * Compare two top line by sum.
438 pmcpl_ct_line_compare(const void *a, const void *b)
440 const struct pmcpl_ct_line *ct1, *ct2;
442 ct1 = (const struct pmcpl_ct_line *) a;
443 ct2 = (const struct pmcpl_ct_line *) b;
445 /* Sort in reverse order */
446 if (ct1->ln_sum < ct2->ln_sum)
448 if (ct1->ln_sum > ct2->ln_sum)
454 * Format and display given PMC index.
458 pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
462 #define TS(x, y) (pmcpl_ct_topscreen[x][y])
463 #define TSI(x, y) (pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index])
465 int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y;
467 char ns[30], vs[10], is[20];
468 struct pmcpl_ct_node *ct;
469 const char *space = " ";
479 pmcpl_ct_topmax[y].ln_sum = 0;
480 pmcpl_ct_topmax[y].ln_index = y;
481 for (x = 1; TS(x, y) != NULL; x++) {
482 pmcpl_ct_topmax[y].ln_sum +=
483 PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples);
486 qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]),
487 pmcpl_ct_line_compare);
488 pmcpl_ct_topmax[y].ln_index = y;
490 for (y = 0; y < maxy; y++) {
496 PMCSTAT_PRINTW("\n");
499 v = pmcpl_ct_topmax[y].ln_sum * 100.0 /
501 snprintf(vs, sizeof(vs), "%.1f", v);
502 v_attrs = PMCSTAT_ATTRPERCENT(v);
503 PMCSTAT_ATTRON(v_attrs);
504 PMCSTAT_PRINTW("%5.5s ", vs);
505 PMCSTAT_ATTROFF(v_attrs);
507 width = indentwidth = 5 + 1;
509 for (x = 1; (ct = TSI(x, y)) != NULL; x++) {
511 vs[0] = '\0'; vs_len = 0;
512 is[0] = '\0'; is_len = 0;
515 v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples);
516 if (v > pmcstat_threshold)
517 vs_len = snprintf(vs, sizeof(vs),
519 v_attrs = PMCSTAT_ATTRPERCENT(v);
521 if (pmcstat_skiplink && v <= pmcstat_threshold) {
522 strlcpy(ns, ".", sizeof(ns));
525 if (ct->pct_sym != NULL) {
526 ns_len = snprintf(ns, sizeof(ns), "%s",
527 pmcstat_string_unintern(ct->pct_sym->ps_name));
529 ns_len = snprintf(ns, sizeof(ns), "%p",
530 (void *)ct->pct_func);
534 TSI(x-1, y)->pct_image != ct->pct_image)
535 is_len = snprintf(is, sizeof(is), "@%s",
536 pmcstat_string_unintern(ct->pct_image->pi_name));
538 /* Check for line wrap. */
539 width += ns_len + is_len + vs_len + 1;
541 if (width >= pmcstat_displaywidth) {
545 PMCSTAT_PRINTW("\n%*s", indentwidth, space);
546 width = indentwidth + ns_len + is_len + vs_len;
549 PMCSTAT_ATTRON(v_attrs);
550 PMCSTAT_PRINTW("%s%s%s ", ns, is, vs);
551 PMCSTAT_ATTROFF(v_attrs);
557 * Output top mode snapshot.
561 pmcpl_ct_topdisplay(void)
564 struct pmcpl_ct_sample r, *rsamples;
567 pmcpl_ct_samples_root(rsamples);
568 pmcpl_ct_node_cleartag();
570 PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE");
573 if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter,
574 pmcpl_ct_root, rsamples, 0, &y))
575 PMCSTAT_PRINTW("...\n");
576 pmcpl_ct_topscreen[1][y] = NULL;
578 pmcpl_ct_node_printtop(rsamples,
579 pmcstat_pmcinfilter, pmcstat_displayheight - 2);
581 pmcpl_ct_samples_free(rsamples);
585 * Handle top mode keypress.
589 pmcpl_ct_topkeypress(int c, void *arg)
597 pmcstat_skiplink = !pmcstat_skiplink;
598 wprintw(w, "skip empty link %s",
599 pmcstat_skiplink ? "on" : "off");
607 * Look for a callgraph node associated with pmc `pmcid' in the global
608 * hash table that corresponds to the given `pc' value in the process map
613 pmcpl_ct_node_update(struct pmcpl_ct_node *parent,
614 struct pmcpl_ct_node *child, int pmcin, unsigned v, int cd)
616 struct pmcpl_ct_arc *arc;
619 assert(parent != NULL);
622 * Find related arc in parent node and
623 * increment the sample count.
625 for (i = 0; i < parent->pct_narc; i++) {
626 if (parent->pct_arc[i].pcta_child == child) {
627 arc = &parent->pct_arc[i];
628 pmcpl_ct_samples_grow(&arc->pcta_samples);
629 arc->pcta_samples.sb[pmcin] += v;
630 /* Estimate call count. */
632 pmcpl_ct_samples_grow(&arc->pcta_callid);
633 if (pmcpl_ct_callid.sb[pmcin] -
634 arc->pcta_callid.sb[pmcin] > 1)
636 arc->pcta_callid.sb[pmcin] =
637 pmcpl_ct_callid.sb[pmcin];
644 * No arc found for us, add ourself to the parent.
646 pmcpl_ct_arc_grow(parent->pct_narc,
647 &parent->pct_arc_c, &parent->pct_arc);
648 arc = &parent->pct_arc[parent->pct_narc];
649 pmcpl_ct_samples_grow(&arc->pcta_samples);
650 arc->pcta_samples.sb[pmcin] = v;
653 pmcpl_ct_samples_grow(&arc->pcta_callid);
654 arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
656 arc->pcta_child = child;
661 * Lookup by image/pc.
664 static struct pmcpl_ct_node *
665 pmcpl_ct_node_hash_lookup(struct pmcstat_image *image, uintfptr_t pc,
666 struct pmcstat_symbol *sym, char *fl, char *fn)
670 struct pmcpl_ct_node *ct;
671 struct pmcpl_ct_node_hash *h;
672 pmcstat_interned_string ifl, ifn;
675 ifl = pmcstat_string_intern(fl);
676 ifn = pmcstat_string_intern(fn);
682 for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++)
683 hash += (pc >> i) & 0xFF;
685 hash &= PMCSTAT_HASH_MASK;
687 STAILQ_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
692 if (ct->pct_image == image && ct->pct_func == pc) {
695 if (ct->pct_type == PMCPL_PCT_NAME &&
696 ct->pct_ifl == ifl && ct->pct_ifn == ifn)
702 * We haven't seen this (pmcid, pc) tuple yet, so allocate a
703 * new callgraph node and a new hash table entry for it.
705 ct = pmcpl_ct_node_allocate();
706 if ((h = malloc(sizeof(*h))) == NULL)
707 err(EX_OSERR, "ERROR: Could not allocate callgraph node");
710 ct->pct_type = PMCPL_PCT_NAME;
714 ct->pct_type = PMCPL_PCT_ADDR;
715 ct->pct_image = image;
720 STAILQ_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
725 * Record a callchain.
729 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
730 uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
733 uintfptr_t pc, loadaddress;
734 struct pmcstat_image *image;
735 struct pmcstat_symbol *sym;
736 struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX];
737 struct pmcstat_process *km;
738 struct pmcpl_ct_node *ct;
739 struct pmcpl_ct_node *ctl[PMC_CALLCHAIN_DEPTH_MAX+1];
743 assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX);
745 /* Get the PMC index. */
746 pmcin = pmcr->pr_pmcin;
749 * Validate mapping for the callchain.
750 * Go from bottom to first invalid entry.
752 km = pmcstat_kernproc;
753 for (n = 0; n < (int)nsamples; n++) {
754 ppm[n] = pmcstat_process_find_map(usermode ?
756 if (ppm[n] == NULL) {
757 /* Detect full frame capture (kernel + user). */
759 ppm[n] = pmcstat_process_find_map(pp, cc[n]);
768 pmcstat_stats.ps_callchain_dubious_frames++;
769 pmcr->pr_dubious_frames++;
773 /* Increase the call generation counter. */
774 pmcpl_ct_samples_grow(&pmcpl_ct_callid);
775 pmcpl_ct_callid.sb[pmcin]++;
780 ctl[0] = pmcpl_ct_root;
781 for (i = 1; n >= 0; n--) {
782 image = ppm[n]->ppm_image;
783 loadaddress = ppm[n]->ppm_lowpc +
784 image->pi_vaddr - image->pi_start;
785 /* Convert to an offset in the image. */
786 pc = cc[n] - loadaddress;
788 * Try determine the function at this offset. If we can't
789 * find a function round leave the `pc' value alone.
791 if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
794 pmcstat_stats.ps_samples_unknown_function++;
796 ct = pmcpl_ct_node_hash_lookup(image, pc, sym, NULL, NULL);
798 pmcstat_stats.ps_callchain_dubious_frames++;
803 /* No valid node found. */
809 for (i = 1; i < n; i++)
810 pmcpl_ct_node_update(ctl[i-1], ctl[i], pmcin, 1, 1);
813 * Increment the sample count for this PMC.
815 pmcpl_ct_samples_grow(&ctl[n-1]->pct_samples);
816 ctl[n-1]->pct_samples.sb[pmcin]++;
818 /* Update per instruction sample if required. */
819 if (args.pa_ctdumpinstr)
820 pmcpl_ct_instr_add(ctl[n-1], pmcin, cc[0] -
821 (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
822 ppm[0]->ppm_image->pi_start), 1);
826 * Print node child cost.
830 pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct, uintfptr_t paddr,
835 struct pmcpl_ct_node *child;
836 char sourcefile[PATH_MAX];
837 char funcname[PATH_MAX];
841 * TODO: attach child cost to the real position in the function.
842 * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
844 for (i=0 ; i<ct->pct_narc; i++) {
845 child = ct->pct_arc[i].pcta_child;
847 fprintf(args.pa_graphfile, "cob=%s\n",
848 pmcstat_string_unintern(child->pct_image->pi_fullpath));
849 /* Child function name. */
850 addr = child->pct_image->pi_vaddr + child->pct_func;
852 /* Child function source file. */
853 if (child->pct_type == PMCPL_PCT_NAME) {
854 fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n",
855 pmcstat_string_unintern(child->pct_ifl),
856 pmcstat_string_unintern(child->pct_ifn));
857 } else if (pmcstat_image_addr2line(child->pct_image, addr,
858 sourcefile, sizeof(sourcefile), &line,
859 funcname, sizeof(funcname))) {
860 fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n",
861 sourcefile, funcname);
863 if (child->pct_sym != NULL)
864 fprintf(args.pa_graphfile,
866 pmcstat_string_unintern(
867 child->pct_sym->ps_name));
869 fprintf(args.pa_graphfile,
870 "cfi=???\ncfn=%p\n", (void *)addr);
873 /* Child function address, line and call count. */
874 fprintf(args.pa_graphfile, "calls=%u %p %u\n",
875 ct->pct_arc[i].pcta_call, (void *)addr, line);
878 * Call address, line, sample.
879 * TODO: Associate call address to the right location.
881 fprintf(args.pa_graphfile, "%p %u", (void *)paddr, pline);
882 for (j = 0; j<pmcstat_npmcs; j++)
883 fprintf(args.pa_graphfile, " %u",
884 PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
885 fprintf(args.pa_graphfile, "\n");
890 * Print node self cost.
894 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
896 int i, j, fline, line;
897 uintfptr_t faddr, addr;
898 char sourcefile[PATH_MAX];
899 char funcname[PATH_MAX];
904 fprintf(args.pa_graphfile, "ob=%s\n",
905 pmcstat_string_unintern(ct->pct_image->pi_fullpath));
910 faddr = ct->pct_image->pi_vaddr + ct->pct_func;
912 if (ct->pct_type == PMCPL_PCT_NAME) {
913 fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n",
914 pmcstat_string_unintern(ct->pct_ifl),
915 pmcstat_string_unintern(ct->pct_ifn));
916 } else if (pmcstat_image_addr2line(ct->pct_image, faddr,
917 sourcefile, sizeof(sourcefile), &fline,
918 funcname, sizeof(funcname))) {
919 fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n",
920 sourcefile, funcname);
922 if (ct->pct_sym != NULL)
923 fprintf(args.pa_graphfile, "fl=???\nfn=%s\n",
924 pmcstat_string_unintern(ct->pct_sym->ps_name));
926 fprintf(args.pa_graphfile, "fl=???\nfn=%p\n",
927 (void *)(ct->pct_image->pi_vaddr + ct->pct_func));
933 if (ct->pct_ninstr > 0) {
937 for (i = 0; i < ct->pct_ninstr; i++) {
938 addr = ct->pct_image->pi_vaddr +
939 ct->pct_instr[i].pctf_func;
941 pmcstat_image_addr2line(ct->pct_image, addr,
942 sourcefile, sizeof(sourcefile), &line,
943 funcname, sizeof(funcname));
944 fprintf(args.pa_graphfile, "%p %u",
946 for (j = 0; j<pmcstat_npmcs; j++)
947 fprintf(args.pa_graphfile, " %u",
949 &ct->pct_instr[i].pctf_samples));
950 fprintf(args.pa_graphfile, "\n");
953 /* Global cost function cost. */
954 fprintf(args.pa_graphfile, "%p %u", (void *)faddr, fline);
955 for (i = 0; i<pmcstat_npmcs ; i++)
956 fprintf(args.pa_graphfile, " %u",
957 PMCPL_CT_SAMPLE(i, &ct->pct_samples));
958 fprintf(args.pa_graphfile, "\n");
961 pmcpl_ct_node_printchild(ct, faddr, fline);
965 pmcpl_ct_printnode(struct pmcpl_ct_node *ct)
969 if (ct == pmcpl_ct_root) {
970 fprintf(args.pa_graphfile, "fn=root\n");
971 fprintf(args.pa_graphfile, "0x0 1");
972 for (i = 0; i<pmcstat_npmcs ; i++)
973 fprintf(args.pa_graphfile, " 0");
974 fprintf(args.pa_graphfile, "\n");
975 pmcpl_ct_node_printchild(ct, 0, 0);
977 pmcpl_ct_node_printself(ct);
981 * Breadth first traversal.
985 pmcpl_ct_bfs(struct pmcpl_ct_node *ct)
988 struct pmcpl_ct_node_hash *pch, *pchc;
989 struct pmcpl_ct_node *child;
990 STAILQ_HEAD(,pmcpl_ct_node_hash) q;
993 if ((pch = malloc(sizeof(*pch))) == NULL)
994 err(EX_OSERR, "ERROR: Cannot allocate queue");
995 pch->pch_ctnode = ct;
996 STAILQ_INSERT_TAIL(&q, pch, pch_next);
997 ct->pct_color = PMCPL_PCT_BLACK;
999 while (!STAILQ_EMPTY(&q)) {
1000 pch = STAILQ_FIRST(&q);
1001 STAILQ_REMOVE_HEAD(&q, pch_next);
1002 pmcpl_ct_printnode(pch->pch_ctnode);
1003 for (i = 0; i<pch->pch_ctnode->pct_narc; i++) {
1004 child = pch->pch_ctnode->pct_arc[i].pcta_child;
1005 if (child->pct_color == PMCPL_PCT_WHITE) {
1006 child->pct_color = PMCPL_PCT_BLACK;
1007 if ((pchc = malloc(sizeof(*pchc))) == NULL)
1009 "ERROR: Cannot allocate queue");
1010 pchc->pch_ctnode = child;
1011 STAILQ_INSERT_TAIL(&q, pchc, pch_next);
1019 * Detect and fix inlined location.
1023 _pmcpl_ct_expand_inline(struct pmcpl_ct_node *ct)
1026 unsigned fline, line, v;
1027 uintfptr_t faddr, addr, pc;
1028 char sourcefile[PATH_MAX];
1029 char ffuncname[PATH_MAX], funcname[PATH_MAX];
1030 char buffer[PATH_MAX];
1031 struct pmcpl_ct_node *child;
1034 * Resolve parent and compare to each instr location.
1036 faddr = ct->pct_image->pi_vaddr + ct->pct_func;
1038 if (!pmcstat_image_addr2line(ct->pct_image, faddr,
1039 sourcefile, sizeof(sourcefile), &fline,
1040 ffuncname, sizeof(ffuncname)))
1043 for (i = 0; i < ct->pct_ninstr; i++) {
1044 addr = ct->pct_image->pi_vaddr +
1045 ct->pct_instr[i].pctf_func;
1047 if (!pmcstat_image_addr2line(ct->pct_image, addr,
1048 sourcefile, sizeof(sourcefile), &line,
1049 funcname, sizeof(funcname)))
1052 if (strcmp(funcname, ffuncname) == 0)
1056 * - Lookup/create inline node by function name.
1057 * - Move instr PMCs to the inline node.
1059 * The lookup create a specific node per image/pc.
1061 if (args.pa_verbosity >= 2)
1062 fprintf(args.pa_printfile,
1063 "WARNING: inlined function at %p %s in %s\n",
1064 (void *)addr, funcname, ffuncname);
1066 snprintf(buffer, sizeof(buffer), "%s@%s",
1067 funcname, ffuncname);
1068 child = pmcpl_ct_node_hash_lookup(ct->pct_image,
1069 ct->pct_func, ct->pct_sym, sourcefile, buffer);
1070 assert(child != NULL);
1071 pc = ct->pct_instr[i].pctf_func;
1072 for (j = 0; j<pmcstat_npmcs; j++) {
1073 v = PMCPL_CT_SAMPLE(j,
1074 &ct->pct_instr[i].pctf_samples);
1077 pmcpl_ct_instr_add(child, j, pc, v);
1078 pmcpl_ct_node_update(ct, child, j, v, 0);
1079 if (j < ct->pct_samples.npmcs)
1080 ct->pct_samples.sb[j] -=
1081 ct->pct_instr[i].pctf_samples.sb[j];
1082 ct->pct_instr[i].pctf_samples.sb[j] = 0;
1088 pmcpl_ct_expand_inline(void)
1091 struct pmcpl_ct_node_hash *pch;
1093 if (!args.pa_ctdumpinstr)
1096 for (i = 0; i < PMCSTAT_NHASH; i++)
1097 STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
1098 if (pch->pch_ctnode->pct_type == PMCPL_PCT_ADDR)
1099 _pmcpl_ct_expand_inline(pch->pch_ctnode);
1103 * Clean the PMC name for Kcachegrind formula
1107 pmcpl_ct_fixup_pmcname(char *s)
1111 for (p = s; *p; p++)
1117 * Print a calltree (KCachegrind) for all PMCs.
1121 pmcpl_ct_print(void)
1125 struct pmcpl_ct_sample rsamples;
1127 pmcpl_ct_samples_root(&rsamples);
1128 pmcpl_ct_expand_inline();
1130 fprintf(args.pa_graphfile,
1132 "creator: pmcstat\n"
1133 "positions: instr line\n"
1135 for (i=0; i<pmcstat_npmcs; i++) {
1136 snprintf(name, sizeof(name), "%s_%d",
1137 pmcstat_pmcindex_to_name(i), i);
1138 pmcpl_ct_fixup_pmcname(name);
1139 fprintf(args.pa_graphfile, " %s", name);
1141 fprintf(args.pa_graphfile, "\nsummary:");
1142 for (i=0; i<pmcstat_npmcs ; i++)
1143 fprintf(args.pa_graphfile, " %u",
1144 PMCPL_CT_SAMPLE(i, &rsamples));
1145 fprintf(args.pa_graphfile, "\n");
1146 pmcpl_ct_bfs(pmcpl_ct_root);
1147 pmcpl_ct_samples_free(&rsamples);
1151 pmcpl_ct_configure(char *opt)
1154 if (strncmp(opt, "skiplink=", 9) == 0) {
1155 pmcstat_skiplink = atoi(opt+9);
1167 pmcpl_ct_root = pmcpl_ct_node_allocate();
1169 for (i = 0; i < PMCSTAT_NHASH; i++)
1170 STAILQ_INIT(&pmcpl_ct_node_hash[i]);
1172 pmcpl_ct_samples_init(&pmcpl_ct_callid);
1178 pmcpl_ct_shutdown(FILE *mf)
1181 struct pmcpl_ct_node_hash *pch, *pchtmp;
1185 if (args.pa_flags & FLAG_DO_CALLGRAPHS)
1192 for (i = 0; i < PMCSTAT_NHASH; i++) {
1193 STAILQ_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
1195 pmcpl_ct_node_free(pch->pch_ctnode);
1200 pmcpl_ct_node_free(pmcpl_ct_root);
1201 pmcpl_ct_root = NULL;
1203 pmcpl_ct_samples_free(&pmcpl_ct_callid);