2 * Copyright (c) 2005-2007, Joseph Koshy
3 * Copyright (c) 2007 The FreeBSD Foundation
6 * Portions of this software were developed by A. Joseph Koshy under
7 * sponsorship from the FreeBSD Foundation and Google, Inc.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * Transform a hwpmc(4) log into human readable form, and into
33 * gprof(1) compatible profiles.
36 #include <sys/cdefs.h>
37 __FBSDID("$FreeBSD$");
39 #include <sys/param.h>
40 #include <sys/endian.h>
42 #include <sys/imgact_aout.h>
43 #include <sys/imgact_elf.h>
46 #include <sys/queue.h>
47 #include <sys/socket.h>
51 #include <netinet/in.h>
72 #include "pmcstat_log.h"
73 #include "pmcstat_top.h"
74 #include "pmcpl_callgraph.h"
76 /* Get the sample value in percent related to nsamples. */
77 #define PMCPL_CG_COUNTP(a) \
78 ((a)->pcg_count * 100.0 / nsamples)
81 * The toplevel CG nodes (i.e., with rank == 0) are placed in a hash table.
84 struct pmcstat_cgnode_hash_list pmcstat_cgnode_hash[PMCSTAT_NHASH];
85 int pmcstat_cgnode_hash_count;
87 static pmcstat_interned_string pmcstat_previous_filename_printed;
89 static struct pmcstat_cgnode *
90 pmcstat_cgnode_allocate(struct pmcstat_image *image, uintfptr_t pc)
92 struct pmcstat_cgnode *cg;
94 if ((cg = malloc(sizeof(*cg))) == NULL)
95 err(EX_OSERR, "ERROR: Cannot allocate callgraph node");
97 cg->pcg_image = image;
101 cg->pcg_nchildren = 0;
102 LIST_INIT(&cg->pcg_children);
108 * Free a node and its children.
111 pmcstat_cgnode_free(struct pmcstat_cgnode *cg)
113 struct pmcstat_cgnode *cgc, *cgtmp;
115 LIST_FOREACH_SAFE(cgc, &cg->pcg_children, pcg_sibling, cgtmp)
116 pmcstat_cgnode_free(cgc);
121 * Look for a callgraph node associated with pmc `pmcid' in the global
122 * hash table that corresponds to the given `pc' value in the process
125 static struct pmcstat_cgnode *
126 pmcstat_cgnode_hash_lookup_pc(struct pmcstat_process *pp, pmc_id_t pmcid,
127 uintfptr_t pc, int usermode)
129 struct pmcstat_pcmap *ppm;
130 struct pmcstat_symbol *sym;
131 struct pmcstat_image *image;
132 struct pmcstat_cgnode *cg;
133 struct pmcstat_cgnode_hash *h;
134 uintfptr_t loadaddress;
135 unsigned int i, hash;
137 ppm = pmcstat_process_find_map(usermode ? pp : pmcstat_kernproc, pc);
141 image = ppm->ppm_image;
143 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
144 pc -= loadaddress; /* Convert to an offset in the image. */
147 * Try determine the function at this offset. If we can't
148 * find a function round leave the `pc' value alone.
150 if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
153 pmcstat_stats.ps_samples_unknown_function++;
155 for (hash = i = 0; i < sizeof(uintfptr_t); i++)
156 hash += (pc >> i) & 0xFF;
158 hash &= PMCSTAT_HASH_MASK;
161 LIST_FOREACH(h, &pmcstat_cgnode_hash[hash], pch_next)
163 if (h->pch_pmcid != pmcid)
170 if (cg->pcg_image == image && cg->pcg_func == pc)
175 * We haven't seen this (pmcid, pc) tuple yet, so allocate a
176 * new callgraph node and a new hash table entry for it.
178 cg = pmcstat_cgnode_allocate(image, pc);
179 if ((h = malloc(sizeof(*h))) == NULL)
180 err(EX_OSERR, "ERROR: Could not allocate callgraph node");
182 h->pch_pmcid = pmcid;
184 LIST_INSERT_HEAD(&pmcstat_cgnode_hash[hash], h, pch_next);
186 pmcstat_cgnode_hash_count++;
192 * Compare two callgraph nodes for sorting.
195 pmcstat_cgnode_compare(const void *a, const void *b)
197 const struct pmcstat_cgnode *const *pcg1, *const *pcg2, *cg1, *cg2;
199 pcg1 = (const struct pmcstat_cgnode *const *) a;
201 pcg2 = (const struct pmcstat_cgnode *const *) b;
204 /* Sort in reverse order */
205 if (cg1->pcg_count < cg2->pcg_count)
207 if (cg1->pcg_count > cg2->pcg_count)
213 * Find (allocating if a needed) a callgraph node in the given
214 * parent with the same (image, pcoffset) pair.
217 static struct pmcstat_cgnode *
218 pmcstat_cgnode_find(struct pmcstat_cgnode *parent, struct pmcstat_image *image,
221 struct pmcstat_cgnode *child;
223 LIST_FOREACH(child, &parent->pcg_children, pcg_sibling) {
224 if (child->pcg_image == image &&
225 child->pcg_func == pcoffset)
230 * Allocate a new structure.
233 child = pmcstat_cgnode_allocate(image, pcoffset);
236 * Link it into the parent.
238 LIST_INSERT_HEAD(&parent->pcg_children, child, pcg_sibling);
239 parent->pcg_nchildren++;
245 * Print one callgraph node. The output format is:
247 * indentation %(parent's samples) #nsamples function@object
250 pmcstat_cgnode_print(struct pmcstat_cgnode *cg, int depth, uint32_t total)
254 struct pmcstat_symbol *sym;
255 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg;
260 (void) fprintf(args.pa_graphfile, "%*s", depth, space);
262 if (cg->pcg_count == total)
263 (void) fprintf(args.pa_graphfile, "100.0%% ");
265 (void) fprintf(args.pa_graphfile, "%05.2f%% ",
266 100.0 * cg->pcg_count / total);
268 n = fprintf(args.pa_graphfile, " [%u] ", cg->pcg_count);
270 /* #samples is a 12 character wide field. */
272 (void) fprintf(args.pa_graphfile, "%*s", 12 - n, space);
275 (void) fprintf(args.pa_graphfile, "%*s", depth, space);
277 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func);
279 (void) fprintf(args.pa_graphfile, "%s",
280 pmcstat_string_unintern(sym->ps_name));
282 (void) fprintf(args.pa_graphfile, "%p",
283 (void *) (cg->pcg_image->pi_vaddr + cg->pcg_func));
285 if (pmcstat_previous_filename_printed !=
286 cg->pcg_image->pi_fullpath) {
287 pmcstat_previous_filename_printed = cg->pcg_image->pi_fullpath;
288 (void) fprintf(args.pa_graphfile, " @ %s\n",
289 pmcstat_string_unintern(
290 pmcstat_previous_filename_printed));
292 (void) fprintf(args.pa_graphfile, "\n");
294 if (cg->pcg_nchildren == 0)
297 if ((sortbuffer = (struct pmcstat_cgnode **)
298 malloc(sizeof(struct pmcstat_cgnode *) *
299 cg->pcg_nchildren)) == NULL)
300 err(EX_OSERR, "ERROR: Cannot print callgraph");
303 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling)
306 assert(cgn - sortbuffer == (int) cg->pcg_nchildren);
308 qsort(sortbuffer, cg->pcg_nchildren, sizeof(struct pmcstat_cgnode *),
309 pmcstat_cgnode_compare);
311 for (cgn = sortbuffer, n = 0; n < cg->pcg_nchildren; n++, cgn++)
312 pmcstat_cgnode_print(*cgn, depth+1, cg->pcg_count);
318 * Record a callchain.
322 pmcpl_cg_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
323 uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
325 uintfptr_t pc, loadaddress;
327 struct pmcstat_image *image;
328 struct pmcstat_pcmap *ppm;
329 struct pmcstat_symbol *sym;
330 struct pmcstat_cgnode *parent, *child;
331 struct pmcstat_process *km;
337 * Find the callgraph node recorded in the global hash table
338 * for this (pmcid, pc).
342 pmcid = pmcr->pr_pmcid;
343 parent = pmcstat_cgnode_hash_lookup_pc(pp, pmcid, pc, usermode);
344 if (parent == NULL) {
345 pmcstat_stats.ps_callchain_dubious_frames++;
346 pmcr->pr_dubious_frames++;
353 * For each return address in the call chain record, subject
354 * to the maximum depth desired.
355 * - Find the image associated with the sample. Stop if there
356 * there is no valid image at that address.
357 * - Find the function that overlaps the return address.
358 * - If found: use the start address of the function.
359 * If not found (say an object's symbol table is not present or
360 * is incomplete), round down to th gprof bucket granularity.
361 * - Convert return virtual address to an offset in the image.
362 * - Look for a child with the same {offset,image} tuple,
363 * inserting one if needed.
364 * - Increment the count of occurrences of the child.
366 km = pmcstat_kernproc;
368 for (n = 1; n < (uint32_t) args.pa_graphdepth && n < nsamples; n++,
372 ppm = pmcstat_process_find_map(usermode ? pp : km, pc);
374 /* Detect full frame capture (kernel + user). */
376 ppm = pmcstat_process_find_map(pp, pc);
384 image = ppm->ppm_image;
385 loadaddress = ppm->ppm_lowpc + image->pi_vaddr -
389 if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
392 child = pmcstat_cgnode_find(parent, image, pc);
398 * Printing a callgraph for a PMC.
401 pmcstat_callgraph_print_for_pmcid(struct pmcstat_pmcrecord *pmcr)
406 struct pmcstat_cgnode **sortbuffer, **cgn;
407 struct pmcstat_cgnode_hash *pch;
410 * We pull out all callgraph nodes in the top-level hash table
411 * with a matching PMC id. We then sort these based on the
412 * frequency of occurrence. Each callgraph node is then
417 pmcid = pmcr->pr_pmcid;
418 if ((sortbuffer = (struct pmcstat_cgnode **)
419 malloc(sizeof(struct pmcstat_cgnode *) *
420 pmcstat_cgnode_hash_count)) == NULL)
421 err(EX_OSERR, "ERROR: Cannot sort callgraph");
424 for (n = 0; n < PMCSTAT_NHASH; n++)
425 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next)
426 if (pch->pch_pmcid == pmcid) {
427 nsamples += pch->pch_cgnode->pcg_count;
428 *cgn++ = pch->pch_cgnode;
431 nentries = cgn - sortbuffer;
432 assert(nentries <= pmcstat_cgnode_hash_count);
439 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *),
440 pmcstat_cgnode_compare);
442 (void) fprintf(args.pa_graphfile,
443 "@ %s [%u samples]\n\n",
444 pmcstat_string_unintern(pmcr->pr_pmcname),
447 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) {
448 pmcstat_previous_filename_printed = NULL;
449 pmcstat_cgnode_print(*cgn, 0, nsamples);
450 (void) fprintf(args.pa_graphfile, "\n");
457 * Print out callgraphs.
461 pmcstat_callgraph_print(void)
463 struct pmcstat_pmcrecord *pmcr;
465 LIST_FOREACH(pmcr, &pmcstat_pmcs, pr_next)
466 pmcstat_callgraph_print_for_pmcid(pmcr);
470 pmcstat_cgnode_topprint(struct pmcstat_cgnode *cg,
471 int depth, uint32_t nsamples)
473 int v_attrs, vs_len, ns_len, width, len, n, nchildren;
476 struct pmcstat_symbol *sym;
477 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg;
482 v = PMCPL_CG_COUNTP(cg);
483 snprintf(vs, sizeof(vs), "%.1f", v);
484 v_attrs = PMCSTAT_ATTRPERCENT(v);
487 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func);
489 snprintf(ns, sizeof(ns), "%s",
490 pmcstat_string_unintern(sym->ps_name));
492 snprintf(ns, sizeof(ns), "%p",
493 (void *)cg->pcg_func);
495 PMCSTAT_ATTRON(v_attrs);
496 PMCSTAT_PRINTW("%5.5s", vs);
497 PMCSTAT_ATTROFF(v_attrs);
498 PMCSTAT_PRINTW(" %-10.10s %-20.20s",
499 pmcstat_string_unintern(cg->pcg_image->pi_name),
502 nchildren = cg->pcg_nchildren;
503 if (nchildren == 0) {
504 PMCSTAT_PRINTW("\n");
508 width = pmcstat_displaywidth - 40;
510 if ((sortbuffer = (struct pmcstat_cgnode **)
511 malloc(sizeof(struct pmcstat_cgnode *) *
513 err(EX_OSERR, "ERROR: Cannot print callgraph");
516 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling)
519 assert(cgn - sortbuffer == (int)nchildren);
521 qsort(sortbuffer, nchildren, sizeof(struct pmcstat_cgnode *),
522 pmcstat_cgnode_compare);
524 /* Count how many callers. */
525 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) {
528 v = PMCPL_CG_COUNTP(pcg);
529 if (v < pmcstat_threshold)
534 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) {
539 v = PMCPL_CG_COUNTP(pcg);
540 vs_len = snprintf(vs, sizeof(vs), ":%.1f", v);
541 v_attrs = PMCSTAT_ATTRPERCENT(v);
546 sym = pmcstat_symbol_search(pcg->pcg_image, pcg->pcg_func);
548 ns_len = snprintf(ns, sizeof(ns), "%s",
549 pmcstat_string_unintern(sym->ps_name));
551 ns_len = snprintf(ns, sizeof(ns), "%p",
552 (void *)pcg->pcg_func);
554 len = ns_len + vs_len + 1;
555 if (width - len < 0) {
556 PMCSTAT_PRINTW(" ...");
561 PMCSTAT_PRINTW(" %s", ns);
563 PMCSTAT_ATTRON(v_attrs);
564 PMCSTAT_PRINTW("%s", vs);
565 PMCSTAT_ATTROFF(v_attrs);
568 PMCSTAT_PRINTW("\n");
577 pmcpl_cg_topdisplay(void)
581 struct pmcstat_cgnode **sortbuffer, **cgn;
582 struct pmcstat_cgnode_hash *pch;
583 struct pmcstat_pmcrecord *pmcr;
585 pmcr = pmcstat_pmcindex_to_pmcr(pmcstat_pmcinfilter);
587 err(EX_SOFTWARE, "ERROR: invalid pmcindex");
590 * We pull out all callgraph nodes in the top-level hash table
591 * with a matching PMC index. We then sort these based on the
592 * frequency of occurrence. Each callgraph node is then
598 if ((sortbuffer = (struct pmcstat_cgnode **)
599 malloc(sizeof(struct pmcstat_cgnode *) *
600 pmcstat_cgnode_hash_count)) == NULL)
601 err(EX_OSERR, "ERROR: Cannot sort callgraph");
604 for (n = 0; n < PMCSTAT_NHASH; n++)
605 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next)
606 if (pmcr == NULL || pch->pch_pmcid == pmcr->pr_pmcid) {
607 nsamples += pch->pch_cgnode->pcg_count;
608 *cgn++ = pch->pch_cgnode;
611 nentries = cgn - sortbuffer;
612 assert(nentries <= pmcstat_cgnode_hash_count);
619 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *),
620 pmcstat_cgnode_compare);
622 PMCSTAT_PRINTW("%5.5s %-10.10s %-20.20s %s\n",
623 "%SAMP", "IMAGE", "FUNCTION", "CALLERS");
625 nentries = min(pmcstat_displayheight - 2, nentries);
627 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) {
628 if (PMCPL_CG_COUNTP(*cgn) < pmcstat_threshold)
630 pmcstat_cgnode_topprint(*cgn, 0, nsamples);
637 * Handle top mode keypress.
641 pmcpl_cg_topkeypress(int c, WINDOW *w)
654 pmcstat_cgnode_hash_count = 0;
655 pmcstat_previous_filename_printed = NULL;
657 for (i = 0; i < PMCSTAT_NHASH; i++) {
658 LIST_INIT(&pmcstat_cgnode_hash[i]);
665 pmcpl_cg_shutdown(FILE *mf)
668 struct pmcstat_cgnode_hash *pch, *pchtmp;
672 if (args.pa_flags & FLAG_DO_CALLGRAPHS)
673 pmcstat_callgraph_print();
678 for (i = 0; i < PMCSTAT_NHASH; i++) {
679 LIST_FOREACH_SAFE(pch, &pmcstat_cgnode_hash[i], pch_next,
681 pmcstat_cgnode_free(pch->pch_cgnode);
682 LIST_REMOVE(pch, pch_next);