xref: /freebsd/usr.sbin/pmcstat/pmcpl_calltree.c (revision de138ec703c3f7d8ed73ba94068d571b2ee7a87c)
1 /*-
2  * Copyright (c) 2009, Fabien Thomas
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  */
26 
27 /*
28  * Process hwpmc(4) samples as calltree.
29  *
30  * Output file format compatible with Kcachegrind (kdesdk).
31  * Handle top mode with a sorted tree display.
32  */
33 
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
36 
37 #include <sys/param.h>
38 #include <sys/endian.h>
39 #include <sys/queue.h>
40 
41 #include <assert.h>
42 #include <curses.h>
43 #include <ctype.h>
44 #include <err.h>
45 #include <errno.h>
46 #include <fcntl.h>
47 #include <pmc.h>
48 #include <pmclog.h>
49 #include <stdint.h>
50 #include <stdio.h>
51 #include <stdlib.h>
52 #include <string.h>
53 #include <unistd.h>
54 #include <sysexits.h>
55 
56 #include "pmcstat.h"
57 #include "pmcstat_log.h"
58 #include "pmcstat_top.h"
59 #include "pmcpl_calltree.h"
60 
61 #define PMCPL_CT_GROWSIZE	4
62 
63 static pmcstat_interned_string pmcpl_ct_prevfn;
64 
65 static int pmcstat_skiplink = 0;
66 
67 struct pmcpl_ct_node;
68 
69 /* Get the sample value for PMC a. */
70 #define PMCPL_CT_SAMPLE(a, b) \
71 	((a) < (b)->npmcs ? (b)->sb[a] : 0)
72 
73 /* Get the sample value in percent related to rsamples. */
74 #define PMCPL_CT_SAMPLEP(a, b) \
75 	(PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a])
76 
77 struct pmcpl_ct_sample {
78 	int		npmcs;		/* Max pmc index available. */
79 	unsigned	*sb;		/* Sample buffer for 0..npmcs. */
80 };
81 
82 struct pmcpl_ct_arc {
83 	struct pmcpl_ct_sample	pcta_samples;
84 	struct pmcpl_ct_sample	pcta_callid;
85 	unsigned		pcta_call;
86 	struct pmcpl_ct_node	*pcta_child;
87 };
88 
89 struct pmcpl_ct_instr {
90 	uintfptr_t		pctf_func;
91 	struct pmcpl_ct_sample	pctf_samples;
92 };
93 
94 /*
95  * Each calltree node is tracked by a pmcpl_ct_node struct.
96  */
97 struct pmcpl_ct_node {
98 #define PMCPL_PCT_TAG	0x00000001	/* Loop detection. */
99 	uint32_t		pct_flags;
100 	struct pmcstat_image	*pct_image;
101 	uintfptr_t		pct_func;
102 	struct pmcpl_ct_sample	pct_samples;
103 
104 	int			pct_narc;
105 	int			pct_arc_c;
106 	struct pmcpl_ct_arc 	*pct_arc;
107 
108 	/* TODO: optimize for large number of items. */
109 	int			pct_ninstr;
110 	int			pct_instr_c;
111 	struct pmcpl_ct_instr	*pct_instr;
112 };
113 
114 struct pmcpl_ct_node_hash {
115 	struct pmcpl_ct_node  *pch_ctnode;
116 	LIST_ENTRY(pmcpl_ct_node_hash) pch_next;
117 };
118 
119 struct pmcpl_ct_sample pmcpl_ct_callid;
120 
121 #define PMCPL_CT_MAXCOL		PMC_CALLCHAIN_DEPTH_MAX
122 #define PMCPL_CT_MAXLINE	1024	/* TODO: dynamic. */
123 
124 struct pmcpl_ct_line {
125 	unsigned	ln_sum;
126 	unsigned	ln_index;
127 };
128 
129 struct pmcpl_ct_line	pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1];
130 struct pmcpl_ct_node	*pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1];
131 
132 /*
133  * All nodes indexed by function/image name are placed in a hash table.
134  */
135 static LIST_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH];
136 
137 /*
138  * Root node for the graph.
139  */
140 static struct pmcpl_ct_node *pmcpl_ct_root;
141 
142 /*
143  * Prototypes
144  */
145 
146 /*
147  * Initialize a samples.
148  */
149 
150 static void
151 pmcpl_ct_samples_init(struct pmcpl_ct_sample *samples)
152 {
153 
154 	samples->npmcs = 0;
155 	samples->sb = NULL;
156 }
157 
158 /*
159  * Free a samples.
160  */
161 
162 static void
163 pmcpl_ct_samples_free(struct pmcpl_ct_sample *samples)
164 {
165 
166 	samples->npmcs = 0;
167 	free(samples->sb);
168 	samples->sb = NULL;
169 }
170 
171 /*
172  * Grow a sample block to store pmcstat_npmcs PMCs.
173  */
174 
175 static void
176 pmcpl_ct_samples_grow(struct pmcpl_ct_sample *samples)
177 {
178 	int npmcs;
179 
180 	/* Enough storage. */
181 	if (pmcstat_npmcs <= samples->npmcs)
182                 return;
183 
184 	npmcs = samples->npmcs +
185 	    max(pmcstat_npmcs - samples->npmcs, PMCPL_CT_GROWSIZE);
186 	samples->sb = realloc(samples->sb, npmcs * sizeof(unsigned));
187 	if (samples->sb == NULL)
188 		errx(EX_SOFTWARE, "ERROR: out of memory");
189 	bzero((char *)samples->sb + samples->npmcs * sizeof(unsigned),
190 	    (npmcs - samples->npmcs) * sizeof(unsigned));
191 	samples->npmcs = npmcs;
192 }
193 
194 /*
195  * Compute the sum of all root arcs.
196  */
197 
198 static void
199 pmcpl_ct_samples_root(struct pmcpl_ct_sample *samples)
200 {
201 	int i, pmcin;
202 
203 	pmcpl_ct_samples_init(samples);
204 	pmcpl_ct_samples_grow(samples);
205 
206 	for (i = 0; i < pmcpl_ct_root->pct_narc; i++)
207 		for (pmcin = 0; pmcin < pmcstat_npmcs; pmcin++)
208 			samples->sb[pmcin] += PMCPL_CT_SAMPLE(pmcin,
209 			    &pmcpl_ct_root->pct_arc[i].pcta_samples);
210 }
211 
212 /*
213  * Grow the arc table.
214  */
215 
216 static void
217 pmcpl_ct_arc_grow(int cursize, int *maxsize, struct pmcpl_ct_arc **items)
218 {
219 	int nmaxsize;
220 
221 	if (cursize < *maxsize)
222 		return;
223 
224 	nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
225 	*items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_arc));
226 	if (*items == NULL)
227 		errx(EX_SOFTWARE, "ERROR: out of memory");
228 	bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_arc),
229 	    (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_arc));
230 	*maxsize = nmaxsize;
231 }
232 
233 /*
234  * Grow the instr table.
235  */
236 
237 static void
238 pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items)
239 {
240 	int nmaxsize;
241 
242 	if (cursize < *maxsize)
243 		return;
244 
245 	nmaxsize = *maxsize + max(cursize + 1 - *maxsize, PMCPL_CT_GROWSIZE);
246 	*items = realloc(*items, nmaxsize * sizeof(struct pmcpl_ct_instr));
247 	if (*items == NULL)
248 		errx(EX_SOFTWARE, "ERROR: out of memory");
249 	bzero((char *)*items + *maxsize * sizeof(struct pmcpl_ct_instr),
250 	    (nmaxsize - *maxsize) * sizeof(struct pmcpl_ct_instr));
251 	*maxsize = nmaxsize;
252 }
253 
254 /*
255  * Add a new instruction sample to given node.
256  */
257 
258 static void
259 pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
260 {
261 	int i;
262 	struct pmcpl_ct_instr *in;
263 
264 	for (i = 0; i<ct->pct_ninstr; i++) {
265 		if (ct->pct_instr[i].pctf_func == pc) {
266 			in = &ct->pct_instr[i];
267 			pmcpl_ct_samples_grow(&in->pctf_samples);
268 			in->pctf_samples.sb[pmcin]++;
269 			return;
270 		}
271 	}
272 
273 	pmcpl_ct_instr_grow(ct->pct_ninstr, &ct->pct_instr_c, &ct->pct_instr);
274 	in = &ct->pct_instr[ct->pct_ninstr];
275 	in->pctf_func = pc;
276 	pmcpl_ct_samples_init(&in->pctf_samples);
277 	pmcpl_ct_samples_grow(&in->pctf_samples);
278 	in->pctf_samples.sb[pmcin] = 1;
279 	ct->pct_ninstr++;
280 }
281 
282 /*
283  * Allocate a new node.
284  */
285 
286 static struct pmcpl_ct_node *
287 pmcpl_ct_node_allocate(struct pmcstat_image *image, uintfptr_t pc)
288 {
289 	struct pmcpl_ct_node *ct;
290 
291 	if ((ct = malloc(sizeof(*ct))) == NULL)
292 		err(EX_OSERR, "ERROR: Cannot allocate callgraph node");
293 
294 	ct->pct_flags	= 0;
295 	ct->pct_image 	= image;
296 	ct->pct_func	= pc;
297 
298 	pmcpl_ct_samples_init(&ct->pct_samples);
299 
300 	ct->pct_narc	= 0;
301 	ct->pct_arc_c	= 0;
302 	ct->pct_arc	= NULL;
303 
304 	ct->pct_ninstr	= 0;
305 	ct->pct_instr_c	= 0;
306 	ct->pct_instr	= NULL;
307 
308 	return (ct);
309 }
310 
311 /*
312  * Free a node.
313  */
314 
315 static void
316 pmcpl_ct_node_free(struct pmcpl_ct_node *ct)
317 {
318 	int i;
319 
320 	for (i = 0; i < ct->pct_narc; i++) {
321 		pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_samples);
322 		pmcpl_ct_samples_free(&ct->pct_arc[i].pcta_callid);
323 	}
324 
325 	pmcpl_ct_samples_free(&ct->pct_samples);
326 	free(ct->pct_arc);
327 	free(ct->pct_instr);
328 	free(ct);
329 }
330 
331 /*
332  * Clear the graph tag on each node.
333  */
334 static void
335 pmcpl_ct_node_cleartag(void)
336 {
337 	int i;
338 	struct pmcpl_ct_node_hash *pch;
339 
340 	for (i = 0; i < PMCSTAT_NHASH; i++)
341 		LIST_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
342 			pch->pch_ctnode->pct_flags &= ~PMCPL_PCT_TAG;
343 
344 	pmcpl_ct_root->pct_flags &= ~PMCPL_PCT_TAG;
345 }
346 
347 /*
348  * Print the callchain line by line with maximum cost at top.
349  */
350 
351 static int
352 pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
353     struct pmcpl_ct_sample *rsamples, int x, int *y)
354 {
355 	int i, terminal;
356 	struct pmcpl_ct_arc *arc;
357 
358 	if (ct->pct_flags & PMCPL_PCT_TAG)
359 		return 0;
360 
361 	ct->pct_flags |= PMCPL_PCT_TAG;
362 
363 	if (x >= PMCPL_CT_MAXCOL) {
364 		pmcpl_ct_topscreen[x][*y] = NULL;
365 		return 1;
366 	}
367 	pmcpl_ct_topscreen[x][*y] = ct;
368 
369 	/*
370 	 * Check if this is a terminal node.
371 	 * We need to check that some samples exist
372 	 * for at least one arc for that PMC.
373 	 */
374 	terminal = 1;
375 	for (i = 0; i < ct->pct_narc; i++) {
376 		arc = &ct->pct_arc[i];
377 		if (PMCPL_CT_SAMPLE(pmcin,
378 		    &arc->pcta_samples) != 0 &&
379 		    PMCPL_CT_SAMPLEP(pmcin,
380 		    &arc->pcta_samples) > pmcstat_threshold &&
381 		    (arc->pcta_child->pct_flags & PMCPL_PCT_TAG) == 0) {
382 			terminal = 0;
383 			break;
384 		}
385 	}
386 
387 	if (ct->pct_narc == 0 || terminal) {
388 		pmcpl_ct_topscreen[x+1][*y] = NULL;
389 		if (*y >= PMCPL_CT_MAXLINE)
390 			return 1;
391 		*y = *y + 1;
392 		for (i=0; i < x; i++)
393 			pmcpl_ct_topscreen[i][*y] =
394 			    pmcpl_ct_topscreen[i][*y - 1];
395 		return 0;
396 	}
397 
398 	for (i = 0; i < ct->pct_narc; i++) {
399 		if (PMCPL_CT_SAMPLE(pmcin,
400 		    &ct->pct_arc[i].pcta_samples) == 0)
401 			continue;
402 		if (PMCPL_CT_SAMPLEP(pmcin,
403 		    &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) {
404 			if (pmcpl_ct_node_dumptop(pmcin,
405 			        ct->pct_arc[i].pcta_child,
406 			        rsamples, x+1, y))
407 				return 1;
408 		}
409 	}
410 
411 	return 0;
412 }
413 
414 /*
415  * Compare two top line by sum.
416  */
417 static int
418 pmcpl_ct_line_compare(const void *a, const void *b)
419 {
420 	const struct pmcpl_ct_line *ct1, *ct2;
421 
422 	ct1 = (const struct pmcpl_ct_line *) a;
423 	ct2 = (const struct pmcpl_ct_line *) b;
424 
425 	/* Sort in reverse order */
426 	if (ct1->ln_sum < ct2->ln_sum)
427 		return (1);
428 	if (ct1->ln_sum > ct2->ln_sum)
429 		return (-1);
430 	return (0);
431 }
432 
433 /*
434  * Format and display given PMC index.
435  */
436 
437 static void
438 pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
439 {
440 #undef	TS
441 #undef	TSI
442 #define	TS(x, y)	(pmcpl_ct_topscreen[x][y])
443 #define	TSI(x, y)	(pmcpl_ct_topscreen[x][pmcpl_ct_topmax[y].ln_index])
444 
445 	int v_attrs, ns_len, vs_len, is_len, width, indentwidth, x, y;
446 	float v;
447 	char ns[30], vs[10], is[20];
448 	struct pmcpl_ct_node *ct;
449 	struct pmcstat_symbol *sym;
450 	const char *space = " ";
451 
452 	/*
453 	 * Sort by line cost.
454 	 */
455 	for (y = 0; ; y++) {
456 		ct = TS(1, y);
457 		if (ct == NULL)
458 			break;
459 
460 		pmcpl_ct_topmax[y].ln_sum = 0;
461 		pmcpl_ct_topmax[y].ln_index = y;
462 		for (x = 1; TS(x, y) != NULL; x++) {
463 			pmcpl_ct_topmax[y].ln_sum +=
464 			    PMCPL_CT_SAMPLE(pmcin, &TS(x, y)->pct_samples);
465 		}
466 	}
467 	qsort(pmcpl_ct_topmax, y, sizeof(pmcpl_ct_topmax[0]),
468 	    pmcpl_ct_line_compare);
469 	pmcpl_ct_topmax[y].ln_index = y;
470 
471 	for (y = 0; y < maxy; y++) {
472 		ct = TSI(1, y);
473 		if (ct == NULL)
474 			break;
475 
476 		if (y > 0)
477 			PMCSTAT_PRINTW("\n");
478 
479 		/* Output sum. */
480 		v = pmcpl_ct_topmax[y].ln_sum * 100.0 /
481 		    rsamples->sb[pmcin];
482 		snprintf(vs, sizeof(vs), "%.1f", v);
483 		v_attrs = PMCSTAT_ATTRPERCENT(v);
484 		PMCSTAT_ATTRON(v_attrs);
485 		PMCSTAT_PRINTW("%5.5s ", vs);
486 		PMCSTAT_ATTROFF(v_attrs);
487 
488 		width = indentwidth = 5 + 1;
489 
490 		for (x = 1; (ct = TSI(x, y)) != NULL; x++) {
491 
492 			vs[0] = '\0'; vs_len = 0;
493 			is[0] = '\0'; is_len = 0;
494 
495 			/* Format value. */
496 			v = PMCPL_CT_SAMPLEP(pmcin, &ct->pct_samples);
497 			if (v > pmcstat_threshold)
498 				vs_len  = snprintf(vs, sizeof(vs),
499 				    "(%.1f%%)", v);
500 			v_attrs = PMCSTAT_ATTRPERCENT(v);
501 
502 			if (pmcstat_skiplink && v <= pmcstat_threshold) {
503 				strlcpy(ns, ".", sizeof(ns));
504 				ns_len = 1;
505 			} else {
506 			sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
507 			if (sym != NULL) {
508 				ns_len = snprintf(ns, sizeof(ns), "%s",
509 				    pmcstat_string_unintern(sym->ps_name));
510 			} else
511 				ns_len = snprintf(ns, sizeof(ns), "%p",
512 				    (void *)ct->pct_func);
513 
514 			/* Format image. */
515 			if (x == 1 ||
516 			    TSI(x-1, y)->pct_image != ct->pct_image)
517 				is_len = snprintf(is, sizeof(is), "@%s",
518 				    pmcstat_string_unintern(ct->pct_image->pi_name));
519 
520 			/* Check for line wrap. */
521 			width += ns_len + is_len + vs_len + 1;
522 			}
523 			if (width >= pmcstat_displaywidth) {
524 				maxy--;
525 				if (y >= maxy)
526 					break;
527 				PMCSTAT_PRINTW("\n%*s", indentwidth, space);
528 				width = indentwidth + ns_len + is_len + vs_len;
529 			}
530 
531 			PMCSTAT_ATTRON(v_attrs);
532 			PMCSTAT_PRINTW("%s%s%s ", ns, is, vs);
533 			PMCSTAT_ATTROFF(v_attrs);
534 		}
535 	}
536 }
537 
538 /*
539  * Output top mode snapshot.
540  */
541 
542 void
543 pmcpl_ct_topdisplay(void)
544 {
545 	int y;
546 	struct pmcpl_ct_sample r, *rsamples;
547 
548 	rsamples = &r;
549 	pmcpl_ct_samples_root(rsamples);
550 
551 	pmcpl_ct_node_cleartag();
552 
553 	PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE");
554 
555 	y = 0;
556 	if (pmcpl_ct_node_dumptop(pmcstat_pmcinfilter,
557 	    pmcpl_ct_root, rsamples, 0, &y))
558 		PMCSTAT_PRINTW("...\n");
559 	pmcpl_ct_topscreen[1][y] = NULL;
560 
561 	pmcpl_ct_node_printtop(rsamples,
562 	    pmcstat_pmcinfilter, pmcstat_displayheight - 2);
563 
564 	pmcpl_ct_samples_free(rsamples);
565 }
566 
567 /*
568  * Handle top mode keypress.
569  */
570 
571 int
572 pmcpl_ct_topkeypress(int c, WINDOW *w)
573 {
574 
575 	switch (c) {
576 	case 'f':
577 		pmcstat_skiplink = !pmcstat_skiplink;
578 		wprintw(w, "skip empty link %s", pmcstat_skiplink ? "on" : "off");
579 		break;
580 	}
581 
582 	return 0;
583 }
584 
585 /*
586  * Look for a callgraph node associated with pmc `pmcid' in the global
587  * hash table that corresponds to the given `pc' value in the process map
588  * `ppm'.
589  */
590 
591 static struct pmcpl_ct_node *
592 pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent,
593     struct pmcstat_pcmap *ppm, uintfptr_t pc, int pmcin)
594 {
595 	struct pmcstat_symbol *sym;
596 	struct pmcstat_image *image;
597 	struct pmcpl_ct_node *ct;
598 	struct pmcpl_ct_node_hash *h;
599 	struct pmcpl_ct_arc *arc;
600 	uintfptr_t loadaddress;
601 	int i;
602 	unsigned int hash;
603 
604 	assert(parent != NULL);
605 
606 	image = ppm->ppm_image;
607 
608 	loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
609 	pc -= loadaddress;	/* Convert to an offset in the image. */
610 
611 	/*
612 	 * Try determine the function at this offset.  If we can't
613 	 * find a function round leave the `pc' value alone.
614 	 */
615 	if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
616 		pc = sym->ps_start;
617 	else
618 		pmcstat_stats.ps_samples_unknown_function++;
619 
620 	for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++)
621 		hash += (pc >> i) & 0xFF;
622 
623 	hash &= PMCSTAT_HASH_MASK;
624 
625 	ct = NULL;
626 	LIST_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
627 		ct = h->pch_ctnode;
628 
629 		assert(ct != NULL);
630 
631 		if (ct->pct_image == image && ct->pct_func == pc) {
632 			/*
633 			 * Find related arc in parent node and
634 			 * increment the sample count.
635 			 */
636 			for (i = 0; i < parent->pct_narc; i++) {
637 				if (parent->pct_arc[i].pcta_child == ct) {
638 					arc = &parent->pct_arc[i];
639 					pmcpl_ct_samples_grow(&arc->pcta_samples);
640 					arc->pcta_samples.sb[pmcin]++;
641 					/* Estimate call count. */
642 					pmcpl_ct_samples_grow(&arc->pcta_callid);
643 					if (pmcpl_ct_callid.sb[pmcin] -
644 					    arc->pcta_callid.sb[pmcin] > 1)
645 						arc->pcta_call++;
646 					arc->pcta_callid.sb[pmcin] =
647 					    pmcpl_ct_callid.sb[pmcin];
648 					return (ct);
649 				}
650 			}
651 
652 			/*
653 			 * No arc found for us, add ourself to the parent.
654 			 */
655 			pmcpl_ct_arc_grow(parent->pct_narc,
656 			    &parent->pct_arc_c, &parent->pct_arc);
657 			arc = &parent->pct_arc[parent->pct_narc];
658 			pmcpl_ct_samples_grow(&arc->pcta_samples);
659 			arc->pcta_samples.sb[pmcin] = 1;
660 			arc->pcta_call = 1;
661 			pmcpl_ct_samples_grow(&arc->pcta_callid);
662 			arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
663 			arc->pcta_child = ct;
664 			parent->pct_narc++;
665 			return (ct);
666 		}
667 	}
668 
669 	/*
670 	 * We haven't seen this (pmcid, pc) tuple yet, so allocate a
671 	 * new callgraph node and a new hash table entry for it.
672 	 */
673 	ct = pmcpl_ct_node_allocate(image, pc);
674 	if ((h = malloc(sizeof(*h))) == NULL)
675 		err(EX_OSERR, "ERROR: Could not allocate callgraph node");
676 
677 	h->pch_ctnode = ct;
678 	LIST_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
679 
680 	pmcpl_ct_arc_grow(parent->pct_narc,
681 	    &parent->pct_arc_c, &parent->pct_arc);
682 	arc = &parent->pct_arc[parent->pct_narc];
683 	pmcpl_ct_samples_grow(&arc->pcta_samples);
684 	arc->pcta_samples.sb[pmcin] = 1;
685 	arc->pcta_call = 1;
686 	pmcpl_ct_samples_grow(&arc->pcta_callid);
687 	arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
688 	arc->pcta_child = ct;
689 	parent->pct_narc++;
690 	return (ct);
691 }
692 
693 /*
694  * Record a callchain.
695  */
696 
697 void
698 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
699     uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
700 {
701 	int n, pmcin;
702 	struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX];
703 	struct pmcstat_process *km;
704 	struct pmcpl_ct_node *parent, *child;
705 
706 	(void) cpu;
707 
708 	assert(nsamples>0 && nsamples<=PMC_CALLCHAIN_DEPTH_MAX);
709 
710 	/* Get the PMC index. */
711 	pmcin = pmcr->pr_pmcin;
712 
713 	/*
714 	 * Validate mapping for the callchain.
715 	 * Go from bottom to first invalid entry.
716 	 */
717 	km = pmcstat_kernproc;
718 	for (n = 0; n < (int)nsamples; n++) {
719 		ppm[n] = pmcstat_process_find_map(usermode ?
720 		    pp : km, cc[n]);
721 		if (ppm[n] == NULL) {
722 			/* Detect full frame capture (kernel + user). */
723 			if (!usermode) {
724 				ppm[n] = pmcstat_process_find_map(pp, cc[n]);
725 				if (ppm[n] != NULL)
726 					km = pp;
727 			}
728 		}
729 		if (ppm[n] == NULL)
730 			break;
731 	}
732 	if (n-- == 0) {
733 		pmcstat_stats.ps_callchain_dubious_frames++;
734 		pmcr->pr_dubious_frames++;
735 		return;
736 	}
737 
738 	/* Increase the call generation counter. */
739 	pmcpl_ct_samples_grow(&pmcpl_ct_callid);
740 	pmcpl_ct_callid.sb[pmcin]++;
741 
742 	/*
743 	 * Iterate remaining addresses.
744 	 */
745 	for (parent = pmcpl_ct_root, child = NULL; n >= 0; n--) {
746 		child = pmcpl_ct_node_hash_lookup_pc(parent, ppm[n], cc[n],
747 		    pmcin);
748 		if (child == NULL) {
749 			pmcstat_stats.ps_callchain_dubious_frames++;
750 			continue;
751 		}
752 		parent = child;
753 	}
754 
755 	/*
756 	 * Increment the sample count for this PMC.
757 	 */
758 	if (child != NULL) {
759 		pmcpl_ct_samples_grow(&child->pct_samples);
760 		child->pct_samples.sb[pmcin]++;
761 
762 		/* Update per instruction sample if required. */
763 		if (args.pa_ctdumpinstr)
764 			pmcpl_ct_instr_add(child, pmcin, cc[0] -
765 			    (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
766 			     ppm[0]->ppm_image->pi_start));
767 	}
768 }
769 
770 /*
771  * Print node self cost.
772  */
773 
774 static void
775 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
776 {
777 	int i, j, line;
778 	uintptr_t addr;
779 	struct pmcstat_symbol *sym;
780 	char sourcefile[PATH_MAX];
781 	char funcname[PATH_MAX];
782 
783 	/*
784 	 * Object binary.
785 	 */
786 #ifdef PMCPL_CT_OPTIMIZEFN
787 	if (pmcpl_ct_prevfn != ct->pct_image->pi_fullpath) {
788 #endif
789 		pmcpl_ct_prevfn = ct->pct_image->pi_fullpath;
790 		fprintf(args.pa_graphfile, "ob=%s\n",
791 		    pmcstat_string_unintern(pmcpl_ct_prevfn));
792 #ifdef PMCPL_CT_OPTIMIZEFN
793 	}
794 #endif
795 
796 	/*
797 	 * Function name.
798 	 */
799 	if (pmcstat_image_addr2line(ct->pct_image, ct->pct_func,
800 	    sourcefile, sizeof(sourcefile), &line,
801 	    funcname, sizeof(funcname))) {
802 		fprintf(args.pa_graphfile, "fn=%s\n",
803 		    funcname);
804 	} else {
805 		sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
806 		if (sym != NULL)
807 			fprintf(args.pa_graphfile, "fn=%s\n",
808 			    pmcstat_string_unintern(sym->ps_name));
809 		else
810 			fprintf(args.pa_graphfile, "fn=%p\n",
811 			    (void *)(ct->pct_image->pi_vaddr + ct->pct_func));
812 	}
813 
814 	/*
815 	 * Self cost.
816 	 */
817 	if (ct->pct_ninstr > 0) {
818 		for (i = 0; i < ct->pct_ninstr; i++) {
819 			addr = ct->pct_image->pi_vaddr +
820 			    ct->pct_instr[i].pctf_func;
821 			line = 0;
822 			if (pmcstat_image_addr2line(ct->pct_image, addr,
823 			    sourcefile, sizeof(sourcefile), &line,
824 			    funcname, sizeof(funcname)))
825 				fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
826 			fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
827 			for (j = 0; j<pmcstat_npmcs; j++)
828 				fprintf(args.pa_graphfile, " %u",
829 				    PMCPL_CT_SAMPLE(j,
830 				    &ct->pct_instr[i].pctf_samples));
831 			fprintf(args.pa_graphfile, "\n");
832 		}
833 	} else {
834 		addr = ct->pct_image->pi_vaddr + ct->pct_func;
835 		line = 0;
836 		if (pmcstat_image_addr2line(ct->pct_image, addr,
837 		    sourcefile, sizeof(sourcefile), &line,
838 		    funcname, sizeof(funcname)))
839 			fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
840 		fprintf(args.pa_graphfile, "* *");
841 		for (i = 0; i<pmcstat_npmcs ; i++)
842 			fprintf(args.pa_graphfile, " %u",
843 			    PMCPL_CT_SAMPLE(i, &ct->pct_samples));
844 		fprintf(args.pa_graphfile, "\n");
845 	}
846 }
847 
848 /*
849  * Print node child cost.
850  */
851 
852 static void
853 pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct)
854 {
855 	int i, j, line;
856 	uintptr_t addr;
857 	struct pmcstat_symbol *sym;
858 	struct pmcpl_ct_node *child;
859 	char sourcefile[PATH_MAX];
860 	char funcname[PATH_MAX];
861 
862 	/*
863 	 * Child cost.
864 	 * TODO: attach child cost to the real position in the funtion.
865 	 * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
866 	 */
867 	for (i=0 ; i<ct->pct_narc; i++) {
868 		child = ct->pct_arc[i].pcta_child;
869 
870 		/* Object binary. */
871 #ifdef PMCPL_CT_OPTIMIZEFN
872 		if (pmcpl_ct_prevfn != child->pct_image->pi_fullpath) {
873 #endif
874 			pmcpl_ct_prevfn = child->pct_image->pi_fullpath;
875 			fprintf(args.pa_graphfile, "cob=%s\n",
876 			    pmcstat_string_unintern(pmcpl_ct_prevfn));
877 #if PMCPL_CT_OPTIMIZEFN
878 		}
879 #endif
880 		/* Child function name. */
881 		addr = child->pct_image->pi_vaddr + child->pct_func;
882 		/* Child function source file. */
883 		if (pmcstat_image_addr2line(child->pct_image, addr,
884 		    sourcefile, sizeof(sourcefile), &line,
885 		    funcname, sizeof(funcname))) {
886 			fprintf(args.pa_graphfile, "cfn=%s\n", funcname);
887 			fprintf(args.pa_graphfile, "cfl=%s\n", sourcefile);
888 		} else {
889 			sym = pmcstat_symbol_search(child->pct_image,
890 			    child->pct_func);
891 			if (sym != NULL)
892 				fprintf(args.pa_graphfile, "cfn=%s\n",
893 				    pmcstat_string_unintern(sym->ps_name));
894 			else
895 				fprintf(args.pa_graphfile, "cfn=%p\n", (void *)addr);
896 		}
897 
898 		/* Child function address, line and call count. */
899 		fprintf(args.pa_graphfile, "calls=%u %p %u\n",
900 		    ct->pct_arc[i].pcta_call, (void *)addr, line);
901 
902 		if (ct->pct_image != NULL) {
903 			/* Call address, line, sample. */
904 			addr = ct->pct_image->pi_vaddr + ct->pct_func;
905 			line = 0;
906 			if (pmcstat_image_addr2line(ct->pct_image, addr, sourcefile,
907 			    sizeof(sourcefile), &line,
908 			    funcname, sizeof(funcname)))
909 				fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
910 			else
911 				fprintf(args.pa_graphfile, "* *");
912 		}
913 		else
914 			fprintf(args.pa_graphfile, "* *");
915 		for (j = 0; j<pmcstat_npmcs; j++)
916 			fprintf(args.pa_graphfile, " %u",
917 			    PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
918 		fprintf(args.pa_graphfile, "\n");
919 	}
920 }
921 
922 /*
923  * Clean the PMC name for Kcachegrind formula
924  */
925 
926 static void
927 pmcpl_ct_fixup_pmcname(char *s)
928 {
929 	char *p;
930 
931 	for (p = s; *p; p++)
932 		if (!isalnum(*p))
933 			*p = '_';
934 }
935 
936 /*
937  * Print a calltree (KCachegrind) for all PMCs.
938  */
939 
940 static void
941 pmcpl_ct_print(void)
942 {
943 	int n, i;
944 	struct pmcpl_ct_node_hash *pch;
945 	struct pmcpl_ct_sample rsamples;
946 	char name[40];
947 
948 	pmcpl_ct_samples_root(&rsamples);
949 	pmcpl_ct_prevfn = NULL;
950 
951 	fprintf(args.pa_graphfile,
952 		"version: 1\n"
953 		"creator: pmcstat\n"
954 		"positions: instr line\n"
955 		"events:");
956 	for (i=0; i<pmcstat_npmcs; i++) {
957 		snprintf(name, sizeof(name), "%s_%d",
958 		    pmcstat_pmcindex_to_name(i), i);
959 		pmcpl_ct_fixup_pmcname(name);
960 		fprintf(args.pa_graphfile, " %s", name);
961 	}
962 	fprintf(args.pa_graphfile, "\nsummary:");
963 	for (i=0; i<pmcstat_npmcs ; i++)
964 		fprintf(args.pa_graphfile, " %u",
965 		    PMCPL_CT_SAMPLE(i, &rsamples));
966 	fprintf(args.pa_graphfile, "\n\n");
967 
968 	/*
969 	 * Fake root node
970 	 */
971 	fprintf(args.pa_graphfile, "ob=FreeBSD\n");
972 	fprintf(args.pa_graphfile, "fn=ROOT\n");
973 	fprintf(args.pa_graphfile, "* *");
974 	for (i = 0; i<pmcstat_npmcs ; i++)
975 		fprintf(args.pa_graphfile, " 0");
976 	fprintf(args.pa_graphfile, "\n");
977 	pmcpl_ct_node_printchild(pmcpl_ct_root);
978 
979 	for (n = 0; n < PMCSTAT_NHASH; n++)
980 		LIST_FOREACH(pch, &pmcpl_ct_node_hash[n], pch_next) {
981 			pmcpl_ct_node_printself(pch->pch_ctnode);
982 			pmcpl_ct_node_printchild(pch->pch_ctnode);
983 	}
984 
985 	pmcpl_ct_samples_free(&rsamples);
986 }
987 
988 int
989 pmcpl_ct_configure(char *opt)
990 {
991 
992 	if (strncmp(opt, "skiplink=", 9) == 0) {
993 		pmcstat_skiplink = atoi(opt+9);
994 	} else
995 		return (0);
996 
997 	return (1);
998 }
999 
1000 int
1001 pmcpl_ct_init(void)
1002 {
1003 	int i;
1004 
1005 	pmcpl_ct_prevfn = NULL;
1006 	pmcpl_ct_root = pmcpl_ct_node_allocate(NULL, 0);
1007 
1008 	for (i = 0; i < PMCSTAT_NHASH; i++)
1009 		LIST_INIT(&pmcpl_ct_node_hash[i]);
1010 
1011 	pmcpl_ct_samples_init(&pmcpl_ct_callid);
1012 
1013 	return (0);
1014 }
1015 
1016 void
1017 pmcpl_ct_shutdown(FILE *mf)
1018 {
1019 	int i;
1020 	struct pmcpl_ct_node_hash *pch, *pchtmp;
1021 
1022 	(void) mf;
1023 
1024 	if (args.pa_flags & FLAG_DO_CALLGRAPHS)
1025 		pmcpl_ct_print();
1026 
1027 	/*
1028 	 * Free memory.
1029 	 */
1030 
1031 	for (i = 0; i < PMCSTAT_NHASH; i++) {
1032 		LIST_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
1033 		    pchtmp) {
1034 			pmcpl_ct_node_free(pch->pch_ctnode);
1035 			free(pch);
1036 		}
1037 	}
1038 
1039 	pmcpl_ct_node_free(pmcpl_ct_root);
1040 	pmcpl_ct_root = NULL;
1041 
1042 	pmcpl_ct_samples_free(&pmcpl_ct_callid);
1043 }
1044 
1045