Ignore machine-check MSRs

[freebsd-src/fkvm-freebsd.git] / usr.sbin / pmcstat / pmcstat_log.c

/*-
 * Copyright (c) 2005-2007, Joseph Koshy
 * Copyright (c) 2007 The FreeBSD Foundation
 * All rights reserved.
 *
 * Portions of this software were developed by A. Joseph Koshy under
 * sponsorship from the FreeBSD Foundation and Google, Inc.
 *
 * 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.
 */

/*
 * Transform a hwpmc(4) log into human readable form, and into
 * gprof(1) compatible profiles.
 */

#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");

#include <sys/param.h>
#include <sys/endian.h>
#include <sys/gmon.h>
#include <sys/imgact_aout.h>
#include <sys/imgact_elf.h>
#include <sys/mman.h>
#include <sys/pmc.h>
#include <sys/queue.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/wait.h>

#include <netinet/in.h>

#include <assert.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <gelf.h>
#include <libgen.h>
#include <limits.h>
#include <netdb.h>
#include <pmc.h>
#include <pmclog.h>
#include <sysexits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "pmcstat.h"

#define min(A,B)                ((A) < (B) ? (A) : (B))
#define max(A,B)                ((A) > (B) ? (A) : (B))

#define PMCSTAT_ALLOCATE                1

/*
 * PUBLIC INTERFACES
 *
 * pmcstat_initialize_logging() initialize this module, called first
 * pmcstat_shutdown_logging()           orderly shutdown, called last
 * pmcstat_open_log()                   open an eventlog for processing
 * pmcstat_process_log()                print/convert an event log
 * pmcstat_close_log()                  finish processing an event log
 *
 * IMPLEMENTATION NOTES
 *
 * We correlate each 'callchain' or 'sample' entry seen in the event
 * log back to an executable object in the system. Executable objects
 * include:
 *      - program executables,
 *      - shared libraries loaded by the runtime loader,
 *      - dlopen()'ed objects loaded by the program,
 *      - the runtime loader itself,
 *      - the kernel and kernel modules.
 *
 * Each process that we know about is treated as a set of regions that
 * map to executable objects.  Processes are described by
 * 'pmcstat_process' structures.  Executable objects are tracked by
 * 'pmcstat_image' structures.  The kernel and kernel modules are
 * common to all processes (they reside at the same virtual addresses
 * for all processes).  Individual processes can have their text
 * segments and shared libraries loaded at process-specific locations.
 *
 * A given executable object can be in use by multiple processes
 * (e.g., libc.so) and loaded at a different address in each.
 * pmcstat_pcmap structures track per-image mappings.
 *
 * The sample log could have samples from multiple PMCs; we
 * generate one 'gmon.out' profile per PMC.
 *
 * IMPLEMENTATION OF GMON OUTPUT
 *
 * Each executable object gets one 'gmon.out' profile, per PMC in
 * use.  Creation of 'gmon.out' profiles is done lazily.  The
 * 'gmon.out' profiles generated for a given sampling PMC are
 * aggregates of all the samples for that particular executable
 * object.
 *
 * IMPLEMENTATION OF SYSTEM-WIDE CALLGRAPH OUTPUT
 *
 * Each active pmcid has its own callgraph structure, described by a
 * 'struct pmcstat_callgraph'.  Given a process id and a list of pc
 * values, we map each pc value to a tuple (image, symbol), where
 * 'image' denotes an executable object and 'symbol' is the closest
 * symbol that precedes the pc value.  Each pc value in the list is
 * also given a 'rank' that reflects its depth in the call stack.
 */

typedef const void *pmcstat_interned_string;

/*
 * 'pmcstat_pmcrecord' is a mapping from PMC ids to human-readable
 * names.
 */

struct pmcstat_pmcrecord {
        LIST_ENTRY(pmcstat_pmcrecord)   pr_next;
        pmc_id_t                        pr_pmcid;
        pmcstat_interned_string pr_pmcname;
};

static LIST_HEAD(,pmcstat_pmcrecord)    pmcstat_pmcs =
        LIST_HEAD_INITIALIZER(&pmcstat_pmcs);


/*
 * struct pmcstat_gmonfile tracks a given 'gmon.out' file.  These
 * files are mmap()'ed in as needed.
 */

struct pmcstat_gmonfile {
        LIST_ENTRY(pmcstat_gmonfile)    pgf_next; /* list of entries */
        int             pgf_overflow;   /* whether a count overflowed */
        pmc_id_t        pgf_pmcid;      /* id of the associated pmc */
        size_t          pgf_nbuckets;   /* #buckets in this gmon.out */
        unsigned int    pgf_nsamples;   /* #samples in this gmon.out */
        pmcstat_interned_string pgf_name;       /* pathname of gmon.out file */
        size_t          pgf_ndatabytes; /* number of bytes mapped */
        void            *pgf_gmondata;  /* pointer to mmap'ed data */
        FILE            *pgf_file;      /* used when writing gmon arcs */
};

/*
 * A 'pmcstat_image' structure describes an executable program on
 * disk.  'pi_execpath' is a cookie representing the pathname of
 * the executable.  'pi_start' and 'pi_end' are the least and greatest
 * virtual addresses for the text segments in the executable.
 * 'pi_gmonlist' contains a linked list of gmon.out files associated
 * with this image.
 */

enum pmcstat_image_type {
        PMCSTAT_IMAGE_UNKNOWN = 0,      /* never looked at the image */
        PMCSTAT_IMAGE_INDETERMINABLE,   /* can't tell what the image is */
        PMCSTAT_IMAGE_ELF32,            /* ELF 32 bit object */
        PMCSTAT_IMAGE_ELF64,            /* ELF 64 bit object */
        PMCSTAT_IMAGE_AOUT              /* AOUT object */
};

struct pmcstat_image {
        LIST_ENTRY(pmcstat_image) pi_next;      /* hash link */
        TAILQ_ENTRY(pmcstat_image) pi_lru;      /* LRU list */
        pmcstat_interned_string pi_execpath;    /* cookie */
        pmcstat_interned_string pi_samplename;  /* sample path name */
        pmcstat_interned_string pi_fullpath;    /* path to FS object */

        enum pmcstat_image_type pi_type;        /* executable type */

        /*
         * Executables have pi_start and pi_end; these are zero
         * for shared libraries.
         */
        uintfptr_t      pi_start;       /* start address (inclusive) */
        uintfptr_t      pi_end;         /* end address (exclusive) */
        uintfptr_t      pi_entry;       /* entry address */
        uintfptr_t      pi_vaddr;       /* virtual address where loaded */
        int             pi_isdynamic;   /* whether a dynamic object */
        int             pi_iskernelmodule;
        pmcstat_interned_string pi_dynlinkerpath; /* path in .interp */

        /* All symbols associated with this object. */
        struct pmcstat_symbol *pi_symbols;
        size_t          pi_symcount;

        /*
         * An image can be associated with one or more gmon.out files;
         * one per PMC.
         */
        LIST_HEAD(,pmcstat_gmonfile) pi_gmlist;
};

/*
 * All image descriptors are kept in a hash table.
 */
static LIST_HEAD(,pmcstat_image)        pmcstat_image_hash[PMCSTAT_NHASH];

/*
 * A 'pmcstat_pcmap' structure maps a virtual address range to an
 * underlying 'pmcstat_image' descriptor.
 */
struct pmcstat_pcmap {
        TAILQ_ENTRY(pmcstat_pcmap) ppm_next;
        uintfptr_t      ppm_lowpc;
        uintfptr_t      ppm_highpc;
        struct pmcstat_image *ppm_image;
};

/*
 * A 'pmcstat_process' structure models processes.  Each process is
 * associated with a set of pmcstat_pcmap structures that map
 * addresses inside it to executable objects.  This set is implemented
 * as a list, kept sorted in ascending order of mapped addresses.
 *
 * 'pp_pid' holds the pid of the process.  When a process exits, the
 * 'pp_isactive' field is set to zero, but the process structure is
 * not immediately reclaimed because there may still be samples in the
 * log for this process.
 */

struct pmcstat_process {
        LIST_ENTRY(pmcstat_process) pp_next;    /* hash-next */
        pid_t                   pp_pid;         /* associated pid */
        int                     pp_isactive;    /* whether active */
        uintfptr_t              pp_entryaddr;   /* entry address */
        TAILQ_HEAD(,pmcstat_pcmap) pp_map;      /* address range map */
};

/*
 * All process descriptors are kept in a hash table.
 */
static LIST_HEAD(,pmcstat_process) pmcstat_process_hash[PMCSTAT_NHASH];

static struct pmcstat_process *pmcstat_kernproc; /* kernel 'process' */

/*
 * Each function symbol tracked by pmcstat(8).
 */

struct pmcstat_symbol {
        pmcstat_interned_string ps_name;
        uint64_t        ps_start;
        uint64_t        ps_end;
};

/*
 * Each call graph node is tracked by a pmcstat_cgnode struct.
 */

struct pmcstat_cgnode {
        struct pmcstat_image    *pcg_image;
        uintfptr_t              pcg_func;
        uint32_t                pcg_count;
        uint32_t                pcg_nchildren;
        LIST_ENTRY(pmcstat_cgnode) pcg_sibling;
        LIST_HEAD(,pmcstat_cgnode) pcg_children;
};

struct pmcstat_cgnode_hash {
        struct pmcstat_cgnode  *pch_cgnode;
        uint32_t                pch_pmcid;
        LIST_ENTRY(pmcstat_cgnode_hash) pch_next;
};

static int pmcstat_cgnode_hash_count;
static pmcstat_interned_string pmcstat_previous_filename_printed;

/*
 * The toplevel CG nodes (i.e., with rank == 0) are placed in a hash table.
 */

static LIST_HEAD(,pmcstat_cgnode_hash) pmcstat_cgnode_hash[PMCSTAT_NHASH];

/* Misc. statistics */
static struct pmcstat_stats {
        int ps_exec_aout;       /* # a.out executables seen */
        int ps_exec_elf;        /* # elf executables seen */
        int ps_exec_errors;     /* # errors processing executables */
        int ps_exec_indeterminable; /* # unknown executables seen */
        int ps_samples_total;   /* total number of samples processed */
        int ps_samples_skipped; /* #samples filtered out for any reason */
        int ps_samples_unknown_offset;  /* #samples of rank 0 not in a map */
        int ps_samples_indeterminable;  /* #samples in indeterminable images */
        int ps_callchain_dubious_frames;/* #dubious frame pointers seen */
} pmcstat_stats;


/*
 * Prototypes
 */

static void     pmcstat_gmon_create_file(struct pmcstat_gmonfile *_pgf,
    struct pmcstat_image *_image);
static pmcstat_interned_string pmcstat_gmon_create_name(const char *_sd,
    struct pmcstat_image *_img, pmc_id_t _pmcid);
static void     pmcstat_gmon_map_file(struct pmcstat_gmonfile *_pgf);
static void     pmcstat_gmon_unmap_file(struct pmcstat_gmonfile *_pgf);

static void pmcstat_image_determine_type(struct pmcstat_image *_image,
    struct pmcstat_args *_a);
static struct pmcstat_gmonfile *pmcstat_image_find_gmonfile(struct
    pmcstat_image *_i, pmc_id_t _id);
static struct pmcstat_image *pmcstat_image_from_path(pmcstat_interned_string
    _path, int _iskernelmodule);
static void pmcstat_image_get_aout_params(struct pmcstat_image *_image,
    struct pmcstat_args *_a);
static void pmcstat_image_get_elf_params(struct pmcstat_image *_image,
    struct pmcstat_args *_a);
static void     pmcstat_image_increment_bucket(struct pmcstat_pcmap *_pcm,
    uintfptr_t _pc, pmc_id_t _pmcid, struct pmcstat_args *_a);
static void     pmcstat_image_link(struct pmcstat_process *_pp,
    struct pmcstat_image *_i, uintfptr_t _lpc);

static void     pmcstat_pmcid_add(pmc_id_t _pmcid,
    pmcstat_interned_string _name, struct pmcstat_args *_a);
static const char *pmcstat_pmcid_to_name(pmc_id_t _pmcid);

static void     pmcstat_process_aout_exec(struct pmcstat_process *_pp,
    struct pmcstat_image *_image, uintfptr_t _entryaddr,
    struct pmcstat_args *_a);
static void     pmcstat_process_elf_exec(struct pmcstat_process *_pp,
    struct pmcstat_image *_image, uintfptr_t _entryaddr,
    struct pmcstat_args *_a);
static void     pmcstat_process_exec(struct pmcstat_process *_pp,
    pmcstat_interned_string _path, uintfptr_t _entryaddr,
    struct pmcstat_args *_ao);
static struct pmcstat_process *pmcstat_process_lookup(pid_t _pid,
    int _allocate);
static struct pmcstat_pcmap *pmcstat_process_find_map(
    struct pmcstat_process *_p, uintfptr_t _pc);

static int      pmcstat_string_compute_hash(const char *_string);
static void pmcstat_string_initialize(void);
static pmcstat_interned_string pmcstat_string_intern(const char *_s);
static pmcstat_interned_string pmcstat_string_lookup(const char *_s);
static int      pmcstat_string_lookup_hash(pmcstat_interned_string _is);
static void pmcstat_string_shutdown(void);
static const char *pmcstat_string_unintern(pmcstat_interned_string _is);


/*
 * A simple implementation of interned strings.  Each interned string
 * is assigned a unique address, so that subsequent string compares
 * can be done by a simple pointer comparision instead of using
 * strcmp().  This speeds up hash table lookups and saves memory if
 * duplicate strings are the norm.
 */
struct pmcstat_string {
        LIST_ENTRY(pmcstat_string)      ps_next;        /* hash link */
        int             ps_len;
        int             ps_hash;
        char            *ps_string;
};

static LIST_HEAD(,pmcstat_string)       pmcstat_string_hash[PMCSTAT_NHASH];

/*
 * Compute a 'hash' value for a string.
 */

static int
pmcstat_string_compute_hash(const char *s)
{
        int hash;

        for (hash = 0; *s; s++)
                hash ^= *s;

        return (hash & PMCSTAT_HASH_MASK);
}

/*
 * Intern a copy of string 's', and return a pointer to the
 * interned structure.
 */

static pmcstat_interned_string
pmcstat_string_intern(const char *s)
{
        struct pmcstat_string *ps;
        const struct pmcstat_string *cps;
        int hash, len;

        if ((cps = pmcstat_string_lookup(s)) != NULL)
                return (cps);

        hash = pmcstat_string_compute_hash(s);
        len  = strlen(s);

        if ((ps = malloc(sizeof(*ps))) == NULL)
                err(EX_OSERR, "ERROR: Could not intern string");
        ps->ps_len = len;
        ps->ps_hash = hash;
        ps->ps_string = strdup(s);
        LIST_INSERT_HEAD(&pmcstat_string_hash[hash], ps, ps_next);
        return ((pmcstat_interned_string) ps);
}

static const char *
pmcstat_string_unintern(pmcstat_interned_string str)
{
        const char *s;

        s = ((const struct pmcstat_string *) str)->ps_string;
        return (s);
}

static pmcstat_interned_string
pmcstat_string_lookup(const char *s)
{
        struct pmcstat_string *ps;
        int hash, len;

        hash = pmcstat_string_compute_hash(s);
        len = strlen(s);

        LIST_FOREACH(ps, &pmcstat_string_hash[hash], ps_next)
            if (ps->ps_len == len && ps->ps_hash == hash &&
                strcmp(ps->ps_string, s) == 0)
                    return (ps);
        return (NULL);
}

static int
pmcstat_string_lookup_hash(pmcstat_interned_string s)
{
        const struct pmcstat_string *ps;

        ps = (const struct pmcstat_string *) s;
        return (ps->ps_hash);
}

/*
 * Initialize the string interning facility.
 */

static void
pmcstat_string_initialize(void)
{
        int i;

        for (i = 0; i < PMCSTAT_NHASH; i++)
                LIST_INIT(&pmcstat_string_hash[i]);
}

/*
 * Destroy the string table, free'ing up space.
 */

static void
pmcstat_string_shutdown(void)
{
        int i;
        struct pmcstat_string *ps, *pstmp;

        for (i = 0; i < PMCSTAT_NHASH; i++)
                LIST_FOREACH_SAFE(ps, &pmcstat_string_hash[i], ps_next,
                    pstmp) {
                        LIST_REMOVE(ps, ps_next);
                        free(ps->ps_string);
                        free(ps);
                }
}

/*
 * Create a gmon.out file and size it.
 */

static void
pmcstat_gmon_create_file(struct pmcstat_gmonfile *pgf,
    struct pmcstat_image *image)
{
        int fd;
        size_t count;
        struct gmonhdr gm;
        const char *pathname;
        char buffer[DEFAULT_BUFFER_SIZE];

        pathname = pmcstat_string_unintern(pgf->pgf_name);
        if ((fd = open(pathname, O_RDWR|O_NOFOLLOW|O_CREAT,
                 S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH)) < 0)
                err(EX_OSERR, "ERROR: Cannot open \"%s\"", pathname);

        gm.lpc = image->pi_start;
        gm.hpc = image->pi_end;
        gm.ncnt = (pgf->pgf_nbuckets * sizeof(HISTCOUNTER)) +
            sizeof(struct gmonhdr);
        gm.version = GMONVERSION;
        gm.profrate = 0;                /* use ticks */
        gm.histcounter_type = 0;        /* compatibility with moncontrol() */
        gm.spare[0] = gm.spare[1] = 0;

        /* Write out the gmon header */
        if (write(fd, &gm, sizeof(gm)) < 0)
                goto error;

        /* Zero fill the samples[] array */
        (void) memset(buffer, 0, sizeof(buffer));

        count = pgf->pgf_ndatabytes - sizeof(struct gmonhdr);
        while (count > sizeof(buffer)) {
                if (write(fd, &buffer, sizeof(buffer)) < 0)
                        goto error;
                count -= sizeof(buffer);
        }

        if (write(fd, &buffer, count) < 0)
                goto error;

        (void) close(fd);

        return;

 error:
        err(EX_OSERR, "ERROR: Cannot write \"%s\"", pathname);
}

/*
 * Determine the full pathname of a gmon.out file for a given
 * (image,pmcid) combination.  Return the interned string.
 */

pmcstat_interned_string
pmcstat_gmon_create_name(const char *samplesdir, struct pmcstat_image *image,
    pmc_id_t pmcid)
{
        const char *pmcname;
        char fullpath[PATH_MAX];

        pmcname = pmcstat_pmcid_to_name(pmcid);

        (void) snprintf(fullpath, sizeof(fullpath),
            "%s/%s/%s", samplesdir, pmcname,
            pmcstat_string_unintern(image->pi_samplename));

        return (pmcstat_string_intern(fullpath));
}


/*
 * Mmap in a gmon.out file for processing.
 */

static void
pmcstat_gmon_map_file(struct pmcstat_gmonfile *pgf)
{
        int fd;
        const char *pathname;

        pathname = pmcstat_string_unintern(pgf->pgf_name);

        /* the gmon.out file must already exist */
        if ((fd = open(pathname, O_RDWR | O_NOFOLLOW, 0)) < 0)
                err(EX_OSERR, "ERROR: cannot open \"%s\"", pathname);

        pgf->pgf_gmondata = mmap(NULL, pgf->pgf_ndatabytes,
            PROT_READ|PROT_WRITE, MAP_NOSYNC|MAP_SHARED, fd, 0);

        if (pgf->pgf_gmondata == MAP_FAILED)
                err(EX_OSERR, "ERROR: cannot map \"%s\"", pathname);

        (void) close(fd);
}

/*
 * Unmap a gmon.out file after sync'ing its data to disk.
 */

static void
pmcstat_gmon_unmap_file(struct pmcstat_gmonfile *pgf)
{
        (void) msync(pgf->pgf_gmondata, pgf->pgf_ndatabytes,
            MS_SYNC);
        (void) munmap(pgf->pgf_gmondata, pgf->pgf_ndatabytes);
        pgf->pgf_gmondata = NULL;
}

static void
pmcstat_gmon_append_arc(struct pmcstat_image *image, pmc_id_t pmcid,
    uintptr_t rawfrom, uintptr_t rawto, uint32_t count)
{
        struct rawarc arc;      /* from <sys/gmon.h> */
        const char *pathname;
        struct pmcstat_gmonfile *pgf;

        if ((pgf = pmcstat_image_find_gmonfile(image, pmcid)) == NULL)
                return;

        if (pgf->pgf_file == NULL) {
                pathname = pmcstat_string_unintern(pgf->pgf_name);
                if ((pgf->pgf_file = fopen(pathname, "a")) == NULL)
                        return;
        }

        arc.raw_frompc = rawfrom + image->pi_vaddr;
        arc.raw_selfpc = rawto + image->pi_vaddr;
        arc.raw_count = count;

        (void) fwrite(&arc, sizeof(arc), 1, pgf->pgf_file);

}

static struct pmcstat_gmonfile *
pmcstat_image_find_gmonfile(struct pmcstat_image *image, pmc_id_t pmcid)
{
        struct pmcstat_gmonfile *pgf;
        LIST_FOREACH(pgf, &image->pi_gmlist, pgf_next)
            if (pgf->pgf_pmcid == pmcid)
                    return (pgf);
        return (NULL);
}


/*
 * Determine whether a given executable image is an A.OUT object, and
 * if so, fill in its parameters from the text file.
 * Sets image->pi_type.
 */

static void
pmcstat_image_get_aout_params(struct pmcstat_image *image,
    struct pmcstat_args *a)
{
        int fd;
        ssize_t nbytes;
        struct exec ex;
        const char *path;
        char buffer[PATH_MAX];

        path = pmcstat_string_unintern(image->pi_execpath);
        assert(path != NULL);

        if (image->pi_iskernelmodule)
                errx(EX_SOFTWARE, "ERROR: a.out kernel modules are "
                    "unsupported \"%s\"", path);

        (void) snprintf(buffer, sizeof(buffer), "%s%s",
            a->pa_fsroot, path);

        if ((fd = open(buffer, O_RDONLY, 0)) < 0 ||
            (nbytes = read(fd, &ex, sizeof(ex))) < 0) {
                warn("WARNING: Cannot determine type of \"%s\"", path);
                image->pi_type = PMCSTAT_IMAGE_INDETERMINABLE;
                if (fd != -1)
                        (void) close(fd);
                return;
        }

        (void) close(fd);

        if ((unsigned) nbytes != sizeof(ex) ||
            N_BADMAG(ex))
                return;

        image->pi_type = PMCSTAT_IMAGE_AOUT;

        /* TODO: the rest of a.out processing */

        return;
}

/*
 * Helper function.
 */

static int
pmcstat_symbol_compare(const void *a, const void *b)
{
        const struct pmcstat_symbol *sym1, *sym2;

        sym1 = (const struct pmcstat_symbol *) a;
        sym2 = (const struct pmcstat_symbol *) b;

        if (sym1->ps_end <= sym2->ps_start)
                return (-1);
        if (sym1->ps_start >= sym2->ps_end)
                return (1);
        return (0);
}

/*
 * Map an address to a symbol in an image.
 */

static struct pmcstat_symbol *
pmcstat_symbol_search(struct pmcstat_image *image, uintfptr_t addr)
{
        struct pmcstat_symbol sym;

        if (image->pi_symbols == NULL)
                return (NULL);

        sym.ps_name  = NULL;
        sym.ps_start = addr;
        sym.ps_end   = addr + 1;

        return (bsearch((void *) &sym, image->pi_symbols,
                    image->pi_symcount, sizeof(struct pmcstat_symbol),
                    pmcstat_symbol_compare));
}

/*
 * Add the list of symbols in the given section to the list associated
 * with the object.
 */
static void
pmcstat_image_add_symbols(struct pmcstat_image *image, Elf *e,
    Elf_Scn *scn, GElf_Shdr *sh)
{
        int firsttime;
        size_t n, newsyms, nshsyms, nfuncsyms;
        struct pmcstat_symbol *symptr;
        char *fnname;
        GElf_Sym sym;
        Elf_Data *data;

        if ((data = elf_getdata(scn, NULL)) == NULL)
                return;

        /*
         * Determine the number of functions named in this
         * section.
         */

        nshsyms = sh->sh_size / sh->sh_entsize;
        for (n = nfuncsyms = 0; n < nshsyms; n++) {
                if (gelf_getsym(data, (int) n, &sym) != &sym)
                        return;
                if (GELF_ST_TYPE(sym.st_info) == STT_FUNC)
                        nfuncsyms++;
        }

        if (nfuncsyms == 0)
                return;

        /*
         * Allocate space for the new entries.
         */
        firsttime = image->pi_symbols == NULL;
        symptr = realloc(image->pi_symbols,
            sizeof(*symptr) * (image->pi_symcount + nfuncsyms));
        if (symptr == image->pi_symbols) /* realloc() failed. */
                return;
        image->pi_symbols = symptr;

        /*
         * Append new symbols to the end of the current table.
         */
        symptr += image->pi_symcount;

        for (n = newsyms = 0; n < nshsyms; n++) {
                if (gelf_getsym(data, (int) n, &sym) != &sym)
                        return;
                if (GELF_ST_TYPE(sym.st_info) != STT_FUNC)
                        continue;

                if (!firsttime && pmcstat_symbol_search(image, sym.st_value))
                        continue; /* We've seen this symbol already. */

                if ((fnname = elf_strptr(e, sh->sh_link, sym.st_name))
                    == NULL)
                        continue;

                symptr->ps_name  = pmcstat_string_intern(fnname);
                symptr->ps_start = sym.st_value - image->pi_vaddr;
                symptr->ps_end   = symptr->ps_start + sym.st_size;
                symptr++;

                newsyms++;
        }

        image->pi_symcount += newsyms;

        assert(newsyms <= nfuncsyms);

        /*
         * Return space to the system if there were duplicates.
         */
        if (newsyms < nfuncsyms)
                image->pi_symbols = realloc(image->pi_symbols,
                    sizeof(*symptr) * image->pi_symcount);

        /*
         * Keep the list of symbols sorted.
         */
        qsort(image->pi_symbols, image->pi_symcount, sizeof(*symptr),
            pmcstat_symbol_compare);

        /*
         * Deal with function symbols that have a size of 'zero' by
         * making them extend to the next higher address.  These
         * symbols are usually defined in assembly code.
         */
        for (symptr = image->pi_symbols;
             symptr < image->pi_symbols + (image->pi_symcount - 1);
             symptr++)
                if (symptr->ps_start == symptr->ps_end)
                        symptr->ps_end = (symptr+1)->ps_start;
}

/*
 * Examine an ELF file to determine the size of its text segment.
 * Sets image->pi_type if anything conclusive can be determined about
 * this image.
 */

static void
pmcstat_image_get_elf_params(struct pmcstat_image *image,
    struct pmcstat_args *a)
{
        int fd;
        size_t i, nph, nsh;
        const char *path, *elfbase;
        uintfptr_t minva, maxva;
        Elf *e;
        Elf_Scn *scn;
        GElf_Ehdr eh;
        GElf_Phdr ph;
        GElf_Shdr sh;
        enum pmcstat_image_type image_type;
        char buffer[PATH_MAX];

        assert(image->pi_type == PMCSTAT_IMAGE_UNKNOWN);

        image->pi_start = minva = ~(uintfptr_t) 0;
        image->pi_end = maxva = (uintfptr_t) 0;
        image->pi_type = image_type = PMCSTAT_IMAGE_INDETERMINABLE;
        image->pi_isdynamic = 0;
        image->pi_dynlinkerpath = NULL;
        image->pi_vaddr = 0;

        path = pmcstat_string_unintern(image->pi_execpath);
        assert(path != NULL);

        /*
         * Look for kernel modules under FSROOT/KERNELPATH/NAME,
         * and user mode executable objects under FSROOT/PATHNAME.
         */
        if (image->pi_iskernelmodule)
                (void) snprintf(buffer, sizeof(buffer), "%s%s/%s",
                    a->pa_fsroot, a->pa_kernel, path);
        else
                (void) snprintf(buffer, sizeof(buffer), "%s%s",
                    a->pa_fsroot, path);

        e = NULL;
        if ((fd = open(buffer, O_RDONLY, 0)) < 0 ||
            (e = elf_begin(fd, ELF_C_READ, NULL)) == NULL ||
            (elf_kind(e) != ELF_K_ELF)) {
                warnx("WARNING: Cannot determine the type of \"%s\".",
                    buffer);
                goto done;
        }

        if (gelf_getehdr(e, &eh) != &eh) {
                warnx("WARNING: Cannot retrieve the ELF Header for "
                    "\"%s\": %s.", buffer, elf_errmsg(-1));
                goto done;
        }

        if (eh.e_type != ET_EXEC && eh.e_type != ET_DYN &&
            !(image->pi_iskernelmodule && eh.e_type == ET_REL)) {
                warnx("WARNING: \"%s\" is of an unsupported ELF type.",
                    buffer);
                goto done;
        }

        image_type = eh.e_ident[EI_CLASS] == ELFCLASS32 ?
            PMCSTAT_IMAGE_ELF32 : PMCSTAT_IMAGE_ELF64;

        /*
         * Determine the virtual address where an executable would be
         * loaded.  Additionally, for dynamically linked executables,
         * save the pathname to the runtime linker.
         */
        if (eh.e_type == ET_EXEC) {
                if (elf_getphnum(e, &nph) == 0) {
                        warnx("WARNING: Could not determine the number of "
                            "program headers in \"%s\": %s.", buffer,
                            elf_errmsg(-1));
                        goto done;
                }
                for (i = 0; i < eh.e_phnum; i++) {
                        if (gelf_getphdr(e, i, &ph) != &ph) {
                                warnx("WARNING: Retrieval of PHDR entry #%ju "
                                    "in \"%s\" failed: %s.", (uintmax_t) i,
                                    buffer, elf_errmsg(-1));
                                goto done;
                        }
                        switch (ph.p_type) {
                        case PT_DYNAMIC:
                                image->pi_isdynamic = 1;
                                break;
                        case PT_INTERP:
                                if ((elfbase = elf_rawfile(e, NULL)) == NULL) {
                                        warnx("WARNING: Cannot retrieve the "
                                            "interpreter for \"%s\": %s.",
                                            buffer, elf_errmsg(-1));
                                        goto done;
                                }
                                image->pi_dynlinkerpath =
                                    pmcstat_string_intern(elfbase +
                                        ph.p_offset);
                                break;
                        case PT_LOAD:
                                if (ph.p_offset == 0)
                                        image->pi_vaddr = ph.p_vaddr;
                                break;
                        }
                }
        }

        /*
         * Get the min and max VA associated with this ELF object.
         */
        if (elf_getshnum(e, &nsh) == 0) {
                warnx("WARNING: Could not determine the number of sections "
                    "for \"%s\": %s.", buffer, elf_errmsg(-1));
                goto done;
        }

        for (i = 0; i < nsh; i++) {
                if ((scn = elf_getscn(e, i)) == NULL ||
                    gelf_getshdr(scn, &sh) != &sh) {
                        warnx("WARNING: Could not retrieve section header "
                            "#%ju in \"%s\": %s.", (uintmax_t) i, buffer,
                            elf_errmsg(-1));
                        goto done;
                }
                if (sh.sh_flags & SHF_EXECINSTR) {
                        minva = min(minva, sh.sh_addr);
                        maxva = max(maxva, sh.sh_addr + sh.sh_size);
                }
                if (sh.sh_type == SHT_SYMTAB || sh.sh_type == SHT_DYNSYM)
                        pmcstat_image_add_symbols(image, e, scn, &sh);
        }

        image->pi_start = minva;
        image->pi_end   = maxva;
        image->pi_type  = image_type;
        image->pi_fullpath = pmcstat_string_intern(buffer);

 done:
        (void) elf_end(e);
        if (fd >= 0)
                (void) close(fd);
        return;
}

/*
 * Given an image descriptor, determine whether it is an ELF, or AOUT.
 * If no handler claims the image, set its type to 'INDETERMINABLE'.
 */

static void
pmcstat_image_determine_type(struct pmcstat_image *image,
    struct pmcstat_args *a)
{
        assert(image->pi_type == PMCSTAT_IMAGE_UNKNOWN);

        /* Try each kind of handler in turn */
        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                pmcstat_image_get_elf_params(image, a);
        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                pmcstat_image_get_aout_params(image, a);

        /*
         * Otherwise, remember that we tried to determine
         * the object's type and had failed.
         */
        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                image->pi_type = PMCSTAT_IMAGE_INDETERMINABLE;
}

/*
 * Locate an image descriptor given an interned path, adding a fresh
 * descriptor to the cache if necessary.  This function also finds a
 * suitable name for this image's sample file.
 *
 * We defer filling in the file format specific parts of the image
 * structure till the time we actually see a sample that would fall
 * into this image.
 */

static struct pmcstat_image *
pmcstat_image_from_path(pmcstat_interned_string internedpath,
    int iskernelmodule)
{
        int count, hash, nlen;
        struct pmcstat_image *pi;
        char *sn;
        char name[NAME_MAX];

        hash = pmcstat_string_lookup_hash(internedpath);

        /* First, look for an existing entry. */
        LIST_FOREACH(pi, &pmcstat_image_hash[hash], pi_next)
            if (pi->pi_execpath == internedpath &&
                  pi->pi_iskernelmodule == iskernelmodule)
                    return (pi);

        /*
         * Allocate a new entry and place it at the head of the hash
         * and LRU lists.
         */
        pi = malloc(sizeof(*pi));
        if (pi == NULL)
                return (NULL);

        pi->pi_type = PMCSTAT_IMAGE_UNKNOWN;
        pi->pi_execpath = internedpath;
        pi->pi_start = ~0;
        pi->pi_end = 0;
        pi->pi_entry = 0;
        pi->pi_vaddr = 0;
        pi->pi_isdynamic = 0;
        pi->pi_iskernelmodule = iskernelmodule;
        pi->pi_dynlinkerpath = NULL;
        pi->pi_symbols = NULL;
        pi->pi_symcount = 0;

        /*
         * Look for a suitable name for the sample files associated
         * with this image: if `basename(path)`+".gmon" is available,
         * we use that, otherwise we try iterating through
         * `basename(path)`+ "~" + NNN + ".gmon" till we get a free
         * entry.
         */
        if ((sn = basename(pmcstat_string_unintern(internedpath))) == NULL)
                err(EX_OSERR, "ERROR: Cannot process \"%s\"",
                    pmcstat_string_unintern(internedpath));

        nlen = strlen(sn);
        nlen = min(nlen, (int) (sizeof(name) - sizeof(".gmon")));

        snprintf(name, sizeof(name), "%.*s.gmon", nlen, sn);

        /* try use the unabridged name first */
        if (pmcstat_string_lookup(name) == NULL)
                pi->pi_samplename = pmcstat_string_intern(name);
        else {
                /*
                 * Otherwise use a prefix from the original name and
                 * upto 3 digits.
                 */
                nlen = strlen(sn);
                nlen = min(nlen, (int) (sizeof(name)-sizeof("~NNN.gmon")));
                count = 0;
                do {
                        if (++count > 999)
                                errx(EX_CANTCREAT, "ERROR: cannot create a "
                                    "gmon file for \"%s\"", name);
                        snprintf(name, sizeof(name), "%.*s~%3.3d.gmon",
                            nlen, sn, count);
                        if (pmcstat_string_lookup(name) == NULL) {
                                pi->pi_samplename =
                                    pmcstat_string_intern(name);
                                count = 0;
                        }
                } while (count > 0);
        }


        LIST_INIT(&pi->pi_gmlist);

        LIST_INSERT_HEAD(&pmcstat_image_hash[hash], pi, pi_next);

        return (pi);
}

/*
 * Increment the bucket in the gmon.out file corresponding to 'pmcid'
 * and 'pc'.
 */

static void
pmcstat_image_increment_bucket(struct pmcstat_pcmap *map, uintfptr_t pc,
    pmc_id_t pmcid, struct pmcstat_args *a)
{
        struct pmcstat_image *image;
        struct pmcstat_gmonfile *pgf;
        uintfptr_t bucket;
        HISTCOUNTER *hc;

        assert(pc >= map->ppm_lowpc && pc < map->ppm_highpc);

        image = map->ppm_image;

        /*
         * If this is the first time we are seeing a sample for
         * this executable image, try determine its parameters.
         */
        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                pmcstat_image_determine_type(image, a);

        assert(image->pi_type != PMCSTAT_IMAGE_UNKNOWN);

        /* Ignore samples in images that we know nothing about. */
        if (image->pi_type == PMCSTAT_IMAGE_INDETERMINABLE) {
                pmcstat_stats.ps_samples_indeterminable++;
                return;
        }

        /*
         * Find the gmon file corresponding to 'pmcid', creating it if
         * needed.
         */
        pgf = pmcstat_image_find_gmonfile(image, pmcid);
        if (pgf == NULL) {
                if ((pgf = calloc(1, sizeof(*pgf))) == NULL)
                        err(EX_OSERR, "ERROR:");

                pgf->pgf_gmondata = NULL;       /* mark as unmapped */
                pgf->pgf_name = pmcstat_gmon_create_name(a->pa_samplesdir,
                    image, pmcid);
                pgf->pgf_pmcid = pmcid;
                assert(image->pi_end > image->pi_start);
                pgf->pgf_nbuckets = (image->pi_end - image->pi_start) /
                    FUNCTION_ALIGNMENT; /* see <machine/profile.h> */
                pgf->pgf_ndatabytes = sizeof(struct gmonhdr) +
                    pgf->pgf_nbuckets * sizeof(HISTCOUNTER);
                pgf->pgf_nsamples = 0;
                pgf->pgf_file = NULL;

                pmcstat_gmon_create_file(pgf, image);

                LIST_INSERT_HEAD(&image->pi_gmlist, pgf, pgf_next);
        }

        /*
         * Map the gmon file in if needed.  It may have been mapped
         * out under memory pressure.
         */
        if (pgf->pgf_gmondata == NULL)
                pmcstat_gmon_map_file(pgf);

        assert(pgf->pgf_gmondata != NULL);

        /*
         *
         */

        bucket = (pc - map->ppm_lowpc) / FUNCTION_ALIGNMENT;

        assert(bucket < pgf->pgf_nbuckets);

        hc = (HISTCOUNTER *) ((uintptr_t) pgf->pgf_gmondata +
            sizeof(struct gmonhdr));

        /* saturating add */
        if (hc[bucket] < 0xFFFFU)  /* XXX tie this to sizeof(HISTCOUNTER) */
                hc[bucket]++;
        else /* mark that an overflow occurred */
                pgf->pgf_overflow = 1;

        pgf->pgf_nsamples++;
}

/*
 * Record the fact that PC values from 'start' to 'end' come from
 * image 'image'.
 */

static void
pmcstat_image_link(struct pmcstat_process *pp, struct pmcstat_image *image,
    uintfptr_t start)
{
        struct pmcstat_pcmap *pcm, *pcmnew;
        uintfptr_t offset;

        assert(image->pi_type != PMCSTAT_IMAGE_UNKNOWN &&
            image->pi_type != PMCSTAT_IMAGE_INDETERMINABLE);

        if ((pcmnew = malloc(sizeof(*pcmnew))) == NULL)
                err(EX_OSERR, "ERROR: Cannot create a map entry");

        /*
         * Adjust the map entry to only cover the text portion
         * of the object.
         */

        offset = start - image->pi_vaddr;
        pcmnew->ppm_lowpc  = image->pi_start + offset;
        pcmnew->ppm_highpc = image->pi_end + offset;
        pcmnew->ppm_image  = image;

        assert(pcmnew->ppm_lowpc < pcmnew->ppm_highpc);

        /* Overlapped mmap()'s are assumed to never occur. */
        TAILQ_FOREACH(pcm, &pp->pp_map, ppm_next)
            if (pcm->ppm_lowpc >= pcmnew->ppm_highpc)
                    break;

        if (pcm == NULL)
                TAILQ_INSERT_TAIL(&pp->pp_map, pcmnew, ppm_next);
        else
                TAILQ_INSERT_BEFORE(pcm, pcmnew, ppm_next);
}

/*
 * Unmap images in the range [start..end) associated with process
 * 'pp'.
 */

static void
pmcstat_image_unmap(struct pmcstat_process *pp, uintfptr_t start,
    uintfptr_t end)
{
        struct pmcstat_pcmap *pcm, *pcmtmp, *pcmnew;

        assert(pp != NULL);
        assert(start < end);

        /*
         * Cases:
         * - we could have the range completely in the middle of an
         *   existing pcmap; in this case we have to split the pcmap
         *   structure into two (i.e., generate a 'hole').
         * - we could have the range covering multiple pcmaps; these
         *   will have to be removed.
         * - we could have either 'start' or 'end' falling in the
         *   middle of a pcmap; in this case shorten the entry.
         */
        TAILQ_FOREACH_SAFE(pcm, &pp->pp_map, ppm_next, pcmtmp) {
                assert(pcm->ppm_lowpc < pcm->ppm_highpc);
                if (pcm->ppm_highpc <= start)
                        continue;
                if (pcm->ppm_lowpc >= end)
                        return;
                if (pcm->ppm_lowpc >= start && pcm->ppm_highpc <= end) {
                        /*
                         * The current pcmap is completely inside the
                         * unmapped range: remove it entirely.
                         */
                        TAILQ_REMOVE(&pp->pp_map, pcm, ppm_next);
                        free(pcm);
                } else if (pcm->ppm_lowpc < start && pcm->ppm_highpc > end) {
                        /*
                         * Split this pcmap into two; curtail the
                         * current map to end at [start-1], and start
                         * the new one at [end].
                         */
                        if ((pcmnew = malloc(sizeof(*pcmnew))) == NULL)
                                err(EX_OSERR, "ERROR: Cannot split a map "
                                    "entry");

                        pcmnew->ppm_image = pcm->ppm_image;

                        pcmnew->ppm_lowpc = end;
                        pcmnew->ppm_highpc = pcm->ppm_highpc;

                        pcm->ppm_highpc = start;

                        TAILQ_INSERT_AFTER(&pp->pp_map, pcm, pcmnew, ppm_next);

                        return;
                } else if (pcm->ppm_lowpc < start && pcm->ppm_highpc <= end)
                        pcm->ppm_highpc = start;
                else if (pcm->ppm_lowpc >= start && pcm->ppm_highpc > end)
                        pcm->ppm_lowpc = end;
                else
                        assert(0);
        }
}

/*
 * Add a {pmcid,name} mapping.
 */

static void
pmcstat_pmcid_add(pmc_id_t pmcid, pmcstat_interned_string ps,
    struct pmcstat_args *a)
{
        struct pmcstat_pmcrecord *pr;
        struct stat st;
        char fullpath[PATH_MAX];

        /* Replace an existing name for the PMC. */
        LIST_FOREACH(pr, &pmcstat_pmcs, pr_next)
            if (pr->pr_pmcid == pmcid) {
                    pr->pr_pmcname = ps;
                    return;
            }

        /*
         * Otherwise, allocate a new descriptor and create the
         * appropriate directory to hold gmon.out files.
         */
        if ((pr = malloc(sizeof(*pr))) == NULL)
                err(EX_OSERR, "ERROR: Cannot allocate pmc record");

        pr->pr_pmcid = pmcid;
        pr->pr_pmcname = ps;
        LIST_INSERT_HEAD(&pmcstat_pmcs, pr, pr_next);

        (void) snprintf(fullpath, sizeof(fullpath), "%s/%s", a->pa_samplesdir,
            pmcstat_string_unintern(ps));

        /* If the path name exists, it should be a directory */
        if (stat(fullpath, &st) == 0 && S_ISDIR(st.st_mode))
                return;

        if (mkdir(fullpath, S_IRWXU|S_IRGRP|S_IXGRP|S_IROTH|S_IXOTH) < 0)
                err(EX_OSERR, "ERROR: Cannot create directory \"%s\"",
                    fullpath);
}

/*
 * Given a pmcid in use, find its human-readable name.
 */

static const char *
pmcstat_pmcid_to_name(pmc_id_t pmcid)
{
        struct pmcstat_pmcrecord *pr;
        char fullpath[PATH_MAX];

        LIST_FOREACH(pr, &pmcstat_pmcs, pr_next)
            if (pr->pr_pmcid == pmcid)
                    return (pmcstat_string_unintern(pr->pr_pmcname));

        /* create a default name and add this entry */
        if ((pr = malloc(sizeof(*pr))) == NULL)
                err(EX_OSERR, "ERROR: ");
        pr->pr_pmcid = pmcid;

        (void) snprintf(fullpath, sizeof(fullpath), "%X", (unsigned int) pmcid);
        pr->pr_pmcname = pmcstat_string_intern(fullpath);

        LIST_INSERT_HEAD(&pmcstat_pmcs, pr, pr_next);

        return (pmcstat_string_unintern(pr->pr_pmcname));
}

/*
 * Associate an AOUT image with a process.
 */

static void
pmcstat_process_aout_exec(struct pmcstat_process *pp,
    struct pmcstat_image *image, uintfptr_t entryaddr,
    struct pmcstat_args *a)
{
        (void) pp;
        (void) image;
        (void) entryaddr;
        (void) a;
        /* TODO Implement a.out handling */
}

/*
 * Associate an ELF image with a process.
 */

static void
pmcstat_process_elf_exec(struct pmcstat_process *pp,
    struct pmcstat_image *image, uintfptr_t entryaddr,
    struct pmcstat_args *a)
{
        uintmax_t libstart;
        struct pmcstat_image *rtldimage;

        assert(image->pi_type == PMCSTAT_IMAGE_ELF32 ||
            image->pi_type == PMCSTAT_IMAGE_ELF64);

        /* Create a map entry for the base executable. */
        pmcstat_image_link(pp, image, image->pi_vaddr);

        /*
         * For dynamically linked executables we need to determine
         * where the dynamic linker was mapped to for this process,
         * Subsequent executable objects that are mapped in by the
         * dynamic linker will be tracked by log events of type
         * PMCLOG_TYPE_MAP_IN.
         */

        if (image->pi_isdynamic) {

                /*
                 * The runtime loader gets loaded just after the maximum
                 * possible heap address.  Like so:
                 *
                 * [  TEXT DATA BSS HEAP -->*RTLD  SHLIBS   <--STACK]
                 * ^                                                ^
                 * 0                               VM_MAXUSER_ADDRESS

                 *
                 * The exact address where the loader gets mapped in
                 * will vary according to the size of the executable
                 * and the limits on the size of the process'es data
                 * segment at the time of exec().  The entry address
                 * recorded at process exec time corresponds to the
                 * 'start' address inside the dynamic linker.  From
                 * this we can figure out the address where the
                 * runtime loader's file object had been mapped to.
                 */
                rtldimage = pmcstat_image_from_path(image->pi_dynlinkerpath,
                    0);
                if (rtldimage == NULL) {
                        warnx("WARNING: Cannot find image for \"%s\".",
                            pmcstat_string_unintern(image->pi_dynlinkerpath));
                        pmcstat_stats.ps_exec_errors++;
                        return;
                }

                if (rtldimage->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                        pmcstat_image_get_elf_params(rtldimage, a);

                if (rtldimage->pi_type != PMCSTAT_IMAGE_ELF32 &&
                    rtldimage->pi_type != PMCSTAT_IMAGE_ELF64) {
                        warnx("WARNING: rtld not an ELF object \"%s\".",
                            pmcstat_string_unintern(image->pi_dynlinkerpath));
                        return;
                }

                libstart = entryaddr - rtldimage->pi_entry;
                pmcstat_image_link(pp, rtldimage, libstart);
        }
}

/*
 * Find the process descriptor corresponding to a PID.  If 'allocate'
 * is zero, we return a NULL if a pid descriptor could not be found or
 * a process descriptor process.  If 'allocate' is non-zero, then we
 * will attempt to allocate a fresh process descriptor.  Zombie
 * process descriptors are only removed if a fresh allocation for the
 * same PID is requested.
 */

static struct pmcstat_process *
pmcstat_process_lookup(pid_t pid, int allocate)
{
        uint32_t hash;
        struct pmcstat_pcmap *ppm, *ppmtmp;
        struct pmcstat_process *pp, *pptmp;

        hash = (uint32_t) pid & PMCSTAT_HASH_MASK;      /* simplicity wins */

        LIST_FOREACH_SAFE(pp, &pmcstat_process_hash[hash], pp_next, pptmp)
            if (pp->pp_pid == pid) {
                    /* Found a descriptor, check and process zombies */
                    if (allocate && pp->pp_isactive == 0) {
                            /* remove maps */
                            TAILQ_FOREACH_SAFE(ppm, &pp->pp_map, ppm_next,
                                ppmtmp) {
                                    TAILQ_REMOVE(&pp->pp_map, ppm, ppm_next);
                                    free(ppm);
                            }
                            /* remove process entry */
                            LIST_REMOVE(pp, pp_next);
                            free(pp);
                            break;
                    }
                    return (pp);
            }

        if (!allocate)
                return (NULL);

        if ((pp = malloc(sizeof(*pp))) == NULL)
                err(EX_OSERR, "ERROR: Cannot allocate pid descriptor");

        pp->pp_pid = pid;
        pp->pp_isactive = 1;

        TAILQ_INIT(&pp->pp_map);

        LIST_INSERT_HEAD(&pmcstat_process_hash[hash], pp, pp_next);
        return (pp);
}

/*
 * Associate an image and a process.
 */

static void
pmcstat_process_exec(struct pmcstat_process *pp,
    pmcstat_interned_string path, uintfptr_t entryaddr,
    struct pmcstat_args *a)
{
        struct pmcstat_image *image;

        if ((image = pmcstat_image_from_path(path, 0)) == NULL) {
                pmcstat_stats.ps_exec_errors++;
                return;
        }

        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                pmcstat_image_determine_type(image, a);

        assert(image->pi_type != PMCSTAT_IMAGE_UNKNOWN);

        switch (image->pi_type) {
        case PMCSTAT_IMAGE_ELF32:
        case PMCSTAT_IMAGE_ELF64:
                pmcstat_stats.ps_exec_elf++;
                pmcstat_process_elf_exec(pp, image, entryaddr, a);
                break;

        case PMCSTAT_IMAGE_AOUT:
                pmcstat_stats.ps_exec_aout++;
                pmcstat_process_aout_exec(pp, image, entryaddr, a);
                break;

        case PMCSTAT_IMAGE_INDETERMINABLE:
                pmcstat_stats.ps_exec_indeterminable++;
                break;

        default:
                err(EX_SOFTWARE, "ERROR: Unsupported executable type for "
                    "\"%s\"", pmcstat_string_unintern(path));
        }
}


/*
 * Find the map entry associated with process 'p' at PC value 'pc'.
 */

static struct pmcstat_pcmap *
pmcstat_process_find_map(struct pmcstat_process *p, uintfptr_t pc)
{
        struct pmcstat_pcmap *ppm;

        TAILQ_FOREACH(ppm, &p->pp_map, ppm_next) {
                if (pc >= ppm->ppm_lowpc && pc < ppm->ppm_highpc)
                        return (ppm);
                if (pc < ppm->ppm_lowpc)
                        return (NULL);
        }

        return (NULL);
}

static struct pmcstat_cgnode *
pmcstat_cgnode_allocate(struct pmcstat_image *image, uintfptr_t pc)
{
        struct pmcstat_cgnode *cg;

        if ((cg = malloc(sizeof(*cg))) == NULL)
                err(EX_OSERR, "ERROR: Cannot allocate callgraph node");

        cg->pcg_image = image;
        cg->pcg_func = pc;

        cg->pcg_count = 0;
        cg->pcg_nchildren = 0;
        LIST_INIT(&cg->pcg_children);

        return (cg);
}

/*
 * Free a node and its children.
 */
static void
pmcstat_cgnode_free(struct pmcstat_cgnode *cg)
{
        struct pmcstat_cgnode *cgc, *cgtmp;

        LIST_FOREACH_SAFE(cgc, &cg->pcg_children, pcg_sibling, cgtmp)
                pmcstat_cgnode_free(cgc);
        free(cg);
}

/*
 * Look for a callgraph node associated with pmc `pmcid' in the global
 * hash table that corresponds to the given `pc' value in the process
 * `pp'.
 */
static struct pmcstat_cgnode *
pmcstat_cgnode_hash_lookup_pc(struct pmcstat_process *pp, uint32_t pmcid,
    uintfptr_t pc, int usermode)
{
        struct pmcstat_pcmap *ppm;
        struct pmcstat_symbol *sym;
        struct pmcstat_image *image;
        struct pmcstat_cgnode *cg;
        struct pmcstat_cgnode_hash *h;
        uintfptr_t loadaddress;
        unsigned int i, hash;

        ppm = pmcstat_process_find_map(usermode ? pp : pmcstat_kernproc, pc);
        if (ppm == NULL)
                return (NULL);

        image = ppm->ppm_image;

        loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
        pc -= loadaddress;      /* Convert to an offset in the image. */

        /*
         * 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;

        for (hash = i = 0; i < sizeof(uintfptr_t); i++)
                hash += (pc >> i) & 0xFF;

        hash &= PMCSTAT_HASH_MASK;

        cg = NULL;
        LIST_FOREACH(h, &pmcstat_cgnode_hash[hash], pch_next)
        {
                if (h->pch_pmcid != pmcid)
                        continue;

                cg = h->pch_cgnode;

                assert(cg != NULL);

                if (cg->pcg_image == image && cg->pcg_func == pc)
                        return (cg);
        }

        /*
         * We haven't seen this (pmcid, pc) tuple yet, so allocate a
         * new callgraph node and a new hash table entry for it.
         */
        cg = pmcstat_cgnode_allocate(image, pc);
        if ((h = malloc(sizeof(*h))) == NULL)
                err(EX_OSERR, "ERROR: Could not allocate callgraph node");

        h->pch_pmcid = pmcid;
        h->pch_cgnode = cg;
        LIST_INSERT_HEAD(&pmcstat_cgnode_hash[hash], h, pch_next);

        pmcstat_cgnode_hash_count++;

        return (cg);
}

/*
 * Compare two callgraph nodes for sorting.
 */
static int
pmcstat_cgnode_compare(const void *a, const void *b)
{
        const struct pmcstat_cgnode *const *pcg1, *const *pcg2, *cg1, *cg2;

        pcg1 = (const struct pmcstat_cgnode *const *) a;
        cg1 = *pcg1;
        pcg2 = (const struct pmcstat_cgnode *const *) b;
        cg2 = *pcg2;

        /* Sort in reverse order */
        if (cg1->pcg_count < cg2->pcg_count)
                return (1);
        if (cg1->pcg_count > cg2->pcg_count)
                return (-1);
        return (0);
}

/*
 * Find (allocating if a needed) a callgraph node in the given
 * parent with the same (image, pcoffset) pair.
 */

static struct pmcstat_cgnode *
pmcstat_cgnode_find(struct pmcstat_cgnode *parent, struct pmcstat_image *image,
    uintfptr_t pcoffset)
{
        struct pmcstat_cgnode *child;

        LIST_FOREACH(child, &parent->pcg_children, pcg_sibling) {
                if (child->pcg_image == image &&
                    child->pcg_func == pcoffset)
                        return (child);
        }

        /*
         * Allocate a new structure.
         */

        child = pmcstat_cgnode_allocate(image, pcoffset);

        /*
         * Link it into the parent.
         */
        LIST_INSERT_HEAD(&parent->pcg_children, child, pcg_sibling);
        parent->pcg_nchildren++;

        return (child);
}

/*
 * Print one callgraph node.  The output format is:
 *
 * indentation %(parent's samples) #nsamples function@object
 */
static void
pmcstat_cgnode_print(struct pmcstat_args *a, struct pmcstat_cgnode *cg,
    int depth, uint32_t total)
{
        uint32_t n;
        const char *space;
        struct pmcstat_symbol *sym;
        struct pmcstat_cgnode **sortbuffer, **cgn, *pcg;

        space = " ";

        if (depth > 0)
                (void) fprintf(a->pa_graphfile, "%*s", depth, space);

        if (cg->pcg_count == total)
                (void) fprintf(a->pa_graphfile, "100.0%% ");
        else
                (void) fprintf(a->pa_graphfile, "%05.2f%% ",
                    100.0 * cg->pcg_count / total);

        n = fprintf(a->pa_graphfile, " [%u] ", cg->pcg_count);

        /* #samples is a 12 character wide field. */
        if (n < 12)
                (void) fprintf(a->pa_graphfile, "%*s", 12 - n, space);

        if (depth > 0)
                (void) fprintf(a->pa_graphfile, "%*s", depth, space);

        sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func);
        if (sym)
                (void) fprintf(a->pa_graphfile, "%s",
                    pmcstat_string_unintern(sym->ps_name));
        else
                (void) fprintf(a->pa_graphfile, "%p",
                    (void *) (cg->pcg_image->pi_vaddr + cg->pcg_func));

        if (pmcstat_previous_filename_printed !=
            cg->pcg_image->pi_fullpath) {
                pmcstat_previous_filename_printed = cg->pcg_image->pi_fullpath;
                (void) fprintf(a->pa_graphfile, " @ %s\n",
                    pmcstat_string_unintern(
                    pmcstat_previous_filename_printed));
        } else
                (void) fprintf(a->pa_graphfile, "\n");

        if (cg->pcg_nchildren == 0)
                return;

        if ((sortbuffer = (struct pmcstat_cgnode **)
                malloc(sizeof(struct pmcstat_cgnode *) *
                    cg->pcg_nchildren)) == NULL)
                err(EX_OSERR, "ERROR: Cannot print callgraph");
        cgn = sortbuffer;

        LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling)
            *cgn++ = pcg;

        assert(cgn - sortbuffer == (int) cg->pcg_nchildren);

        qsort(sortbuffer, cg->pcg_nchildren, sizeof(struct pmcstat_cgnode *),
            pmcstat_cgnode_compare);

        for (cgn = sortbuffer, n = 0; n < cg->pcg_nchildren; n++, cgn++)
                pmcstat_cgnode_print(a, *cgn, depth+1, cg->pcg_count);

        free(sortbuffer);
}

/*
 * Record a callchain.
 */

static void
pmcstat_record_callchain(struct pmcstat_process *pp, uint32_t pmcid,
    uint32_t nsamples, uintfptr_t *cc, int usermode, struct pmcstat_args *a)
{
        uintfptr_t pc, loadaddress;
        uint32_t n;
        struct pmcstat_image *image;
        struct pmcstat_pcmap *ppm;
        struct pmcstat_symbol *sym;
        struct pmcstat_cgnode *parent, *child;

        /*
         * Find the callgraph node recorded in the global hash table
         * for this (pmcid, pc).
         */

        pc = cc[0];
        parent = pmcstat_cgnode_hash_lookup_pc(pp, pmcid, pc, usermode);
        if (parent == NULL) {
                pmcstat_stats.ps_callchain_dubious_frames++;
                return;
        }

        parent->pcg_count++;

        /*
         * For each return address in the call chain record, subject
         * to the maximum depth desired.
         * - Find the image associated with the sample.  Stop if there
         *   there is no valid image at that address.
         * - Find the function that overlaps the return address.
         * - If found: use the start address of the function.
         *   If not found (say an object's symbol table is not present or
         *   is incomplete), round down to th gprof bucket granularity.
         * - Convert return virtual address to an offset in the image.
         * - Look for a child with the same {offset,image} tuple,
         *   inserting one if needed.
         * - Increment the count of occurrences of the child.
         */

        for (n = 1; n < (uint32_t) a->pa_graphdepth && n < nsamples; n++,
            parent = child) {
                pc = cc[n];

                ppm = pmcstat_process_find_map(usermode ? pp :
                    pmcstat_kernproc, pc);
                if (ppm == NULL)
                        return;

                image = ppm->ppm_image;
                loadaddress = ppm->ppm_lowpc + image->pi_vaddr -
                    image->pi_start;
                pc -= loadaddress;

                if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
                        pc = sym->ps_start;

                child = pmcstat_cgnode_find(parent, image, pc);
                child->pcg_count++;
        }
}

/*
 * Printing a callgraph for a PMC.
 */
static void
pmcstat_callgraph_print_for_pmcid(struct pmcstat_args *a,
    struct pmcstat_pmcrecord *pmcr)
{
        int n, nentries;
        uint32_t nsamples, pmcid;
        struct pmcstat_cgnode **sortbuffer, **cgn;
        struct pmcstat_cgnode_hash *pch;

        /*
         * We pull out all callgraph nodes in the top-level hash table
         * with a matching PMC id.  We then sort these based on the
         * frequency of occurrence.  Each callgraph node is then
         * printed.
         */

        nsamples = 0;
        pmcid = pmcr->pr_pmcid;
        if ((sortbuffer = (struct pmcstat_cgnode **)
            malloc(sizeof(struct pmcstat_cgnode *) *
            pmcstat_cgnode_hash_count)) == NULL)
                err(EX_OSERR, "ERROR: Cannot sort callgraph");
        cgn = sortbuffer;

        memset(sortbuffer, 0xFF, pmcstat_cgnode_hash_count *
            sizeof(struct pmcstat_cgnode **));

        for (n = 0; n < PMCSTAT_NHASH; n++)
                LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next)
                    if (pch->pch_pmcid == pmcid) {
                            nsamples += pch->pch_cgnode->pcg_count;
                            *cgn++ = pch->pch_cgnode;
                    }

        nentries = cgn - sortbuffer;
        assert(nentries <= pmcstat_cgnode_hash_count);

        if (nentries == 0)
                return;

        qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *),
            pmcstat_cgnode_compare);

        (void) fprintf(a->pa_graphfile,
            "@ %s [%u samples]\n\n",
            pmcstat_string_unintern(pmcr->pr_pmcname),
            nsamples);

        for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) {
                pmcstat_previous_filename_printed = NULL;
                pmcstat_cgnode_print(a, *cgn, 0, nsamples);
                (void) fprintf(a->pa_graphfile, "\n");
        }

        free(sortbuffer);
}

/*
 * Print out callgraphs.
 */

static void
pmcstat_callgraph_print(struct pmcstat_args *a)
{
        struct pmcstat_pmcrecord *pmcr;

        LIST_FOREACH(pmcr, &pmcstat_pmcs, pr_next)
            pmcstat_callgraph_print_for_pmcid(a, pmcr);
}

static void
pmcstat_cgnode_do_gmon_arcs(struct pmcstat_cgnode *cg, pmc_id_t pmcid)
{
        struct pmcstat_cgnode *cgc;

        /*
         * Look for child nodes that belong to the same image.
         */

        LIST_FOREACH(cgc, &cg->pcg_children, pcg_sibling) {
                if (cgc->pcg_image == cg->pcg_image)
                        pmcstat_gmon_append_arc(cg->pcg_image, pmcid,
                            cgc->pcg_func, cg->pcg_func, cgc->pcg_count);
                if (cgc->pcg_nchildren > 0)
                        pmcstat_cgnode_do_gmon_arcs(cgc, pmcid);
        }
}

static void
pmcstat_callgraph_do_gmon_arcs_for_pmcid(pmc_id_t pmcid)
{
        int n;
        struct pmcstat_cgnode_hash *pch;

        for (n = 0; n < PMCSTAT_NHASH; n++)
                LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next)
                        if (pch->pch_pmcid == pmcid &&
                            pch->pch_cgnode->pcg_nchildren > 1)
                                pmcstat_cgnode_do_gmon_arcs(pch->pch_cgnode,
                                    pmcid);
}


static void
pmcstat_callgraph_do_gmon_arcs(void)
{
        struct pmcstat_pmcrecord *pmcr;

        LIST_FOREACH(pmcr, &pmcstat_pmcs, pr_next)
                pmcstat_callgraph_do_gmon_arcs_for_pmcid(pmcr->pr_pmcid);
}

/*
 * Convert a hwpmc(4) log to profile information.  A system-wide
 * callgraph is generated if FLAG_DO_CALLGRAPHS is set.  gmon.out
 * files usable by gprof(1) are created if FLAG_DO_GPROF is set.
 */
static int
pmcstat_analyze_log(struct pmcstat_args *a)
{
        uint32_t cpu, cpuflags;
        uintfptr_t pc;
        pid_t pid;
        struct pmcstat_image *image;
        struct pmcstat_process *pp, *ppnew;
        struct pmcstat_pcmap *ppm, *ppmtmp;
        struct pmclog_ev ev;
        pmcstat_interned_string image_path;

        assert(a->pa_flags & FLAG_DO_ANALYSIS);

        if (elf_version(EV_CURRENT) == EV_NONE)
                err(EX_UNAVAILABLE, "Elf library intialization failed");

        while (pmclog_read(a->pa_logparser, &ev) == 0) {
                assert(ev.pl_state == PMCLOG_OK);

                switch (ev.pl_type) {
                case PMCLOG_TYPE_INITIALIZE:
                        if ((ev.pl_u.pl_i.pl_version & 0xFF000000) !=
                            PMC_VERSION_MAJOR << 24 && a->pa_verbosity > 0)
                                warnx("WARNING: Log version 0x%x does not "
                                    "match compiled version 0x%x.",
                                    ev.pl_u.pl_i.pl_version,
                                    PMC_VERSION_MAJOR);
                        break;

                case PMCLOG_TYPE_MAP_IN:
                        /*
                         * Introduce an address range mapping for a
                         * userland process or the kernel (pid == -1).
                         *
                         * We always allocate a process descriptor so
                         * that subsequent samples seen for this
                         * address range are mapped to the current
                         * object being mapped in.
                         */
                        pid = ev.pl_u.pl_mi.pl_pid;
                        if (pid == -1)
                                pp = pmcstat_kernproc;
                        else
                                pp = pmcstat_process_lookup(pid,
                                    PMCSTAT_ALLOCATE);

                        assert(pp != NULL);

                        image_path = pmcstat_string_intern(ev.pl_u.pl_mi.
                            pl_pathname);
                        image = pmcstat_image_from_path(image_path, pid == -1);
                        if (image->pi_type == PMCSTAT_IMAGE_UNKNOWN)
                                pmcstat_image_determine_type(image, a);
                        if (image->pi_type != PMCSTAT_IMAGE_INDETERMINABLE)
                                pmcstat_image_link(pp, image,
                                    ev.pl_u.pl_mi.pl_start);
                        break;

                case PMCLOG_TYPE_MAP_OUT:
                        /*
                         * Remove an address map.
                         */
                        pid = ev.pl_u.pl_mo.pl_pid;
                        if (pid == -1)
                                pp = pmcstat_kernproc;
                        else
                                pp = pmcstat_process_lookup(pid, 0);

                        if (pp == NULL) /* unknown process */
                                break;

                        pmcstat_image_unmap(pp, ev.pl_u.pl_mo.pl_start,
                            ev.pl_u.pl_mo.pl_end);
                        break;

                case PMCLOG_TYPE_PCSAMPLE:
                        /*
                         * Note: the `PCSAMPLE' log entry is not
                         * generated by hpwmc(4) after version 2.
                         */

                        /*
                         * We bring in the gmon file for the image
                         * currently associated with the PMC & pid
                         * pair and increment the appropriate entry
                         * bin inside this.
                         */
                        pmcstat_stats.ps_samples_total++;

                        pc = ev.pl_u.pl_s.pl_pc;
                        pp = pmcstat_process_lookup(ev.pl_u.pl_s.pl_pid,
                            PMCSTAT_ALLOCATE);
                        if ((ppm = pmcstat_process_find_map(pp, pc)) == NULL &&
                            (ppm = pmcstat_process_find_map(pmcstat_kernproc,
                                pc)) == NULL) { /* unknown process,offset pair */
                                pmcstat_stats.ps_samples_unknown_offset++;
                                break;
                        }

                        pmcstat_image_increment_bucket(ppm, pc,
                            ev.pl_u.pl_s.pl_pmcid, a);

                        break;

                case PMCLOG_TYPE_CALLCHAIN:
                        pmcstat_stats.ps_samples_total++;

                        cpuflags = ev.pl_u.pl_cc.pl_cpuflags;
                        cpu = PMC_CALLCHAIN_CPUFLAGS_TO_CPU(cpuflags);

                        /* Filter on the CPU id. */
                        if ((a->pa_cpumask & (1 << cpu)) == 0) {
                                pmcstat_stats.ps_samples_skipped++;
                                break;
                        }

                        pp = pmcstat_process_lookup(ev.pl_u.pl_cc.pl_pid,
                            PMCSTAT_ALLOCATE);

                        pmcstat_record_callchain(pp,
                            ev.pl_u.pl_cc.pl_pmcid, ev.pl_u.pl_cc.pl_npc,
                            ev.pl_u.pl_cc.pl_pc,
                            PMC_CALLCHAIN_CPUFLAGS_TO_USERMODE(cpuflags), a);

                        if ((a->pa_flags & FLAG_DO_GPROF) == 0)
                                break;

                        pc = ev.pl_u.pl_cc.pl_pc[0];
                        if ((ppm = pmcstat_process_find_map(pp, pc)) == NULL &&
                            (ppm = pmcstat_process_find_map(pmcstat_kernproc,
                                pc)) == NULL) { /* unknown offset */
                                pmcstat_stats.ps_samples_unknown_offset++;
                                break;
                        }

                        pmcstat_image_increment_bucket(ppm, pc,
                            ev.pl_u.pl_cc.pl_pmcid, a);

                        break;

                case PMCLOG_TYPE_PMCALLOCATE:
                        /*
                         * Record the association pmc id between this
                         * PMC and its name.
                         */
                        pmcstat_pmcid_add(ev.pl_u.pl_a.pl_pmcid,
                            pmcstat_string_intern(ev.pl_u.pl_a.pl_evname), a);
                        break;

                case PMCLOG_TYPE_PROCEXEC:

                        /*
                         * Change the executable image associated with
                         * a process.
                         */
                        pp = pmcstat_process_lookup(ev.pl_u.pl_x.pl_pid,
                            PMCSTAT_ALLOCATE);

                        /* delete the current process map */
                        TAILQ_FOREACH_SAFE(ppm, &pp->pp_map, ppm_next, ppmtmp) {
                                TAILQ_REMOVE(&pp->pp_map, ppm, ppm_next);
                                free(ppm);
                        }

                        /* associate this process  image */
                        image_path = pmcstat_string_intern(
                                ev.pl_u.pl_x.pl_pathname);
                        assert(image_path != NULL);
                        pmcstat_process_exec(pp, image_path,
                            ev.pl_u.pl_x.pl_entryaddr, a);
                        break;

                case PMCLOG_TYPE_PROCEXIT:

                        /*
                         * Due to the way the log is generated, the
                         * last few samples corresponding to a process
                         * may appear in the log after the process
                         * exit event is recorded.  Thus we keep the
                         * process' descriptor and associated data
                         * structures around, but mark the process as
                         * having exited.
                         */
                        pp = pmcstat_process_lookup(ev.pl_u.pl_e.pl_pid, 0);
                        if (pp == NULL)
                                break;
                        pp->pp_isactive = 0;    /* mark as a zombie */
                        break;

                case PMCLOG_TYPE_SYSEXIT:
                        pp = pmcstat_process_lookup(ev.pl_u.pl_se.pl_pid, 0);
                        if (pp == NULL)
                                break;
                        pp->pp_isactive = 0;    /* make a zombie */
                        break;

                case PMCLOG_TYPE_PROCFORK:

                        /*
                         * Allocate a process descriptor for the new
                         * (child) process.
                         */
                        ppnew =
                            pmcstat_process_lookup(ev.pl_u.pl_f.pl_newpid,
                                PMCSTAT_ALLOCATE);

                        /*
                         * If we had been tracking the parent, clone
                         * its address maps.
                         */
                        pp = pmcstat_process_lookup(ev.pl_u.pl_f.pl_oldpid, 0);
                        if (pp == NULL)
                                break;
                        TAILQ_FOREACH(ppm, &pp->pp_map, ppm_next)
                            pmcstat_image_link(ppnew, ppm->ppm_image,
                                ppm->ppm_lowpc);
                        break;

                default:        /* other types of entries are not relevant */
                        break;
                }
        }

        if (ev.pl_state == PMCLOG_EOF)
                return (PMCSTAT_FINISHED);
        else if (ev.pl_state == PMCLOG_REQUIRE_DATA)
                return (PMCSTAT_RUNNING);

        err(EX_DATAERR, "ERROR: event parsing failed (record %jd, "
            "offset 0x%jx)", (uintmax_t) ev.pl_count + 1, ev.pl_offset);
}

/*
 * Print log entries as text.
 */

static int
pmcstat_print_log(struct pmcstat_args *a)
{
        struct pmclog_ev ev;
        uint32_t npc;

        while (pmclog_read(a->pa_logparser, &ev) == 0) {
                assert(ev.pl_state == PMCLOG_OK);
                switch (ev.pl_type) {
                case PMCLOG_TYPE_CALLCHAIN:
                        PMCSTAT_PRINT_ENTRY(a, "callchain",
                            "%d 0x%x %d %d %c", ev.pl_u.pl_cc.pl_pid,
                            ev.pl_u.pl_cc.pl_pmcid,
                            PMC_CALLCHAIN_CPUFLAGS_TO_CPU(ev.pl_u.pl_cc. \
                                pl_cpuflags), ev.pl_u.pl_cc.pl_npc,
                            PMC_CALLCHAIN_CPUFLAGS_TO_USERMODE(ev.pl_u.pl_cc.\
                                pl_cpuflags) ? 'u' : 's');
                        for (npc = 0; npc < ev.pl_u.pl_cc.pl_npc; npc++)
                                PMCSTAT_PRINT_ENTRY(a, "...", "%p",
                                    (void *) ev.pl_u.pl_cc.pl_pc[npc]);
                        break;
                case PMCLOG_TYPE_CLOSELOG:
                        PMCSTAT_PRINT_ENTRY(a,"closelog",);
                        break;
                case PMCLOG_TYPE_DROPNOTIFY:
                        PMCSTAT_PRINT_ENTRY(a,"drop",);
                        break;
                case PMCLOG_TYPE_INITIALIZE:
                        PMCSTAT_PRINT_ENTRY(a,"initlog","0x%x \"%s\"",
                            ev.pl_u.pl_i.pl_version,
                            pmc_name_of_cputype(ev.pl_u.pl_i.pl_arch));
                        if ((ev.pl_u.pl_i.pl_version & 0xFF000000) !=
                            PMC_VERSION_MAJOR << 24 && a->pa_verbosity > 0)
                                warnx("WARNING: Log version 0x%x != expected "
                                    "version 0x%x.", ev.pl_u.pl_i.pl_version,
                                    PMC_VERSION);
                        break;
                case PMCLOG_TYPE_MAP_IN:
                        PMCSTAT_PRINT_ENTRY(a,"map-in","%d %p \"%s\"",
                            ev.pl_u.pl_mi.pl_pid,
                            (void *) ev.pl_u.pl_mi.pl_start,
                            ev.pl_u.pl_mi.pl_pathname);
                        break;
                case PMCLOG_TYPE_MAP_OUT:
                        PMCSTAT_PRINT_ENTRY(a,"map-out","%d %p %p",
                            ev.pl_u.pl_mo.pl_pid,
                            (void *) ev.pl_u.pl_mo.pl_start,
                            (void *) ev.pl_u.pl_mo.pl_end);
                        break;
                case PMCLOG_TYPE_PCSAMPLE:
                        PMCSTAT_PRINT_ENTRY(a,"sample","0x%x %d %p %c",
                            ev.pl_u.pl_s.pl_pmcid,
                            ev.pl_u.pl_s.pl_pid,
                            (void *) ev.pl_u.pl_s.pl_pc,
                            ev.pl_u.pl_s.pl_usermode ? 'u' : 's');
                        break;
                case PMCLOG_TYPE_PMCALLOCATE:
                        PMCSTAT_PRINT_ENTRY(a,"allocate","0x%x \"%s\" 0x%x",
                            ev.pl_u.pl_a.pl_pmcid,
                            ev.pl_u.pl_a.pl_evname,
                            ev.pl_u.pl_a.pl_flags);
                        break;
                case PMCLOG_TYPE_PMCATTACH:
                        PMCSTAT_PRINT_ENTRY(a,"attach","0x%x %d \"%s\"",
                            ev.pl_u.pl_t.pl_pmcid,
                            ev.pl_u.pl_t.pl_pid,
                            ev.pl_u.pl_t.pl_pathname);
                        break;
                case PMCLOG_TYPE_PMCDETACH:
                        PMCSTAT_PRINT_ENTRY(a,"detach","0x%x %d",
                            ev.pl_u.pl_d.pl_pmcid,
                            ev.pl_u.pl_d.pl_pid);
                        break;
                case PMCLOG_TYPE_PROCCSW:
                        PMCSTAT_PRINT_ENTRY(a,"cswval","0x%x %d %jd",
                            ev.pl_u.pl_c.pl_pmcid,
                            ev.pl_u.pl_c.pl_pid,
                            ev.pl_u.pl_c.pl_value);
                        break;
                case PMCLOG_TYPE_PROCEXEC:
                        PMCSTAT_PRINT_ENTRY(a,"exec","0x%x %d %p \"%s\"",
                            ev.pl_u.pl_x.pl_pmcid,
                            ev.pl_u.pl_x.pl_pid,
                            (void *) ev.pl_u.pl_x.pl_entryaddr,
                            ev.pl_u.pl_x.pl_pathname);
                        break;
                case PMCLOG_TYPE_PROCEXIT:
                        PMCSTAT_PRINT_ENTRY(a,"exitval","0x%x %d %jd",
                            ev.pl_u.pl_e.pl_pmcid,
                            ev.pl_u.pl_e.pl_pid,
                            ev.pl_u.pl_e.pl_value);
                        break;
                case PMCLOG_TYPE_PROCFORK:
                        PMCSTAT_PRINT_ENTRY(a,"fork","%d %d",
                            ev.pl_u.pl_f.pl_oldpid,
                            ev.pl_u.pl_f.pl_newpid);
                        break;
                case PMCLOG_TYPE_USERDATA:
                        PMCSTAT_PRINT_ENTRY(a,"userdata","0x%x",
                            ev.pl_u.pl_u.pl_userdata);
                        break;
                case PMCLOG_TYPE_SYSEXIT:
                        PMCSTAT_PRINT_ENTRY(a,"exit","%d",
                            ev.pl_u.pl_se.pl_pid);
                        break;
                default:
                        fprintf(a->pa_printfile, "unknown event (type %d).\n",
                            ev.pl_type);
                }
        }

        if (ev.pl_state == PMCLOG_EOF)
                return (PMCSTAT_FINISHED);
        else if (ev.pl_state ==  PMCLOG_REQUIRE_DATA)
                return (PMCSTAT_RUNNING);

        errx(EX_DATAERR, "ERROR: event parsing failed "
            "(record %jd, offset 0x%jx).",
            (uintmax_t) ev.pl_count + 1, ev.pl_offset);
        /*NOTREACHED*/
}

/*
 * Public Interfaces.
 */

/*
 * Close a logfile, after first flushing all in-module queued data.
 */

int
pmcstat_close_log(struct pmcstat_args *a)
{
        if (pmc_flush_logfile() < 0 ||
            pmc_configure_logfile(-1) < 0)
                err(EX_OSERR, "ERROR: logging failed");
        a->pa_flags &= ~(FLAG_HAS_OUTPUT_LOGFILE | FLAG_HAS_PIPE);
        return (a->pa_flags & FLAG_HAS_PIPE ? PMCSTAT_EXITING :
            PMCSTAT_FINISHED);
}



/*
 * Open a log file, for reading or writing.
 *
 * The function returns the fd of a successfully opened log or -1 in
 * case of failure.
 */

int
pmcstat_open_log(const char *path, int mode)
{
        int error, fd;
        size_t hlen;
        const char *p, *errstr;
        struct addrinfo hints, *res, *res0;
        char hostname[MAXHOSTNAMELEN];

        errstr = NULL;
        fd = -1;

        /*
         * If 'path' is "-" then open one of stdin or stdout depending
         * on the value of 'mode'.
         *
         * If 'path' contains a ':' and does not start with a '/' or '.',
         * and is being opened for writing, treat it as a "host:port"
         * specification and open a network socket.
         *
         * Otherwise, treat 'path' as a file name and open that.
         */
        if (path[0] == '-' && path[1] == '\0')
                fd = (mode == PMCSTAT_OPEN_FOR_READ) ? 0 : 1;
        else if (mode == PMCSTAT_OPEN_FOR_WRITE && path[0] != '/' &&
            path[0] != '.' && strchr(path, ':') != NULL) {

                p = strrchr(path, ':');
                hlen = p - path;
                if (p == path || hlen >= sizeof(hostname)) {
                        errstr = strerror(EINVAL);
                        goto done;
                }

                assert(hlen < sizeof(hostname));
                (void) strncpy(hostname, path, hlen);
                hostname[hlen] = '\0';

                (void) memset(&hints, 0, sizeof(hints));
                hints.ai_family = AF_UNSPEC;
                hints.ai_socktype = SOCK_STREAM;
                if ((error = getaddrinfo(hostname, p+1, &hints, &res0)) != 0) {
                        errstr = gai_strerror(error);
                        goto done;
                }

                fd = -1;
                for (res = res0; res; res = res->ai_next) {
                        if ((fd = socket(res->ai_family, res->ai_socktype,
                            res->ai_protocol)) < 0) {
                                errstr = strerror(errno);
                                continue;
                        }
                        if (connect(fd, res->ai_addr, res->ai_addrlen) < 0) {
                                errstr = strerror(errno);
                                (void) close(fd);
                                fd = -1;
                                continue;
                        }
                        errstr = NULL;
                        break;
                }
                freeaddrinfo(res0);

        } else if ((fd = open(path, mode == PMCSTAT_OPEN_FOR_READ ?
                    O_RDONLY : (O_WRONLY|O_CREAT|O_TRUNC),
                    S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH)) < 0)
                        errstr = strerror(errno);

  done:
        if (errstr)
                errx(EX_OSERR, "ERROR: Cannot open \"%s\" for %s: %s.", path,
                    (mode == PMCSTAT_OPEN_FOR_READ ? "reading" : "writing"),
                    errstr);

        return (fd);
}

/*
 * Process a log file in offline analysis mode.
 */

int
pmcstat_process_log(struct pmcstat_args *a)
{

        /*
         * If analysis has not been asked for, just print the log to
         * the current output file.
         */
        if (a->pa_flags & FLAG_DO_PRINT)
                return (pmcstat_print_log(a));
        else
                return (pmcstat_analyze_log(a));
}

/*
 * Initialize module.
 */

void
pmcstat_initialize_logging(struct pmcstat_args *a)
{
        int i;

        (void) a;

        /* use a convenient format for 'ldd' output */
        if (setenv("LD_TRACE_LOADED_OBJECTS_FMT1","%o \"%p\" %x\n",1) != 0)
                err(EX_OSERR, "ERROR: Cannot setenv");

        /* Initialize hash tables */
        pmcstat_string_initialize();
        for (i = 0; i < PMCSTAT_NHASH; i++) {
                LIST_INIT(&pmcstat_image_hash[i]);
                LIST_INIT(&pmcstat_process_hash[i]);
        }

        /*
         * Create a fake 'process' entry for the kernel with pid -1.
         * hwpmc(4) will subsequently inform us about where the kernel
         * and any loaded kernel modules are mapped.
         */
        if ((pmcstat_kernproc = pmcstat_process_lookup((pid_t) -1,
                 PMCSTAT_ALLOCATE)) == NULL)
                err(EX_OSERR, "ERROR: Cannot initialize logging");
}

/*
 * Shutdown module.
 */

void
pmcstat_shutdown_logging(struct pmcstat_args *a)
{
        int i;
        FILE *mf;
        struct pmcstat_gmonfile *pgf, *pgftmp;
        struct pmcstat_image *pi, *pitmp;
        struct pmcstat_process *pp, *pptmp;
        struct pmcstat_cgnode_hash *pch, *pchtmp;

        /* determine where to send the map file */
        mf = NULL;
        if (a->pa_mapfilename != NULL)
                mf = (strcmp(a->pa_mapfilename, "-") == 0) ?
                    a->pa_printfile : fopen(a->pa_mapfilename, "w");

        if (mf == NULL && a->pa_flags & FLAG_DO_GPROF &&
            a->pa_verbosity >= 2)
                mf = a->pa_printfile;

        if (mf)
                (void) fprintf(mf, "MAP:\n");


        if (a->pa_flags & FLAG_DO_CALLGRAPHS)
                pmcstat_callgraph_print(a);

        /*
         * Sync back all gprof flat profile data.
         */
        for (i = 0; i < PMCSTAT_NHASH; i++) {
                LIST_FOREACH(pi, &pmcstat_image_hash[i], pi_next) {
                        if (mf)
                                (void) fprintf(mf, " \"%s\" => \"%s\"",
                                    pmcstat_string_unintern(pi->pi_execpath),
                                    pmcstat_string_unintern(
                                    pi->pi_samplename));

                        /* flush gmon.out data to disk */
                        LIST_FOREACH(pgf, &pi->pi_gmlist, pgf_next) {
                                pmcstat_gmon_unmap_file(pgf);
                                if (mf)
                                        (void) fprintf(mf, " %s/%d",
                                            pmcstat_pmcid_to_name(
                                            pgf->pgf_pmcid),
                                            pgf->pgf_nsamples);
                                if (pgf->pgf_overflow && a->pa_verbosity >= 1)
                                        warnx("WARNING: profile \"%s\" "
                                            "overflowed.",
                                            pmcstat_string_unintern(
                                                pgf->pgf_name));
                        }

                        if (mf)
                                (void) fprintf(mf, "\n");
                }
        }

        /*
         * Compute arcs and add these to the gprof files.
         */
        if (a->pa_flags & FLAG_DO_GPROF && a->pa_graphdepth > 1)
                pmcstat_callgraph_do_gmon_arcs();

        /*
         * Free memory.
         */
        for (i = 0; i < PMCSTAT_NHASH; i++) {
                LIST_FOREACH_SAFE(pch, &pmcstat_cgnode_hash[i], pch_next,
                    pchtmp) {
                        pmcstat_cgnode_free(pch->pch_cgnode);
                        free(pch);
                }
        }

        for (i = 0; i < PMCSTAT_NHASH; i++) {
                LIST_FOREACH_SAFE(pi, &pmcstat_image_hash[i], pi_next, pitmp)
                {
                        LIST_FOREACH_SAFE(pgf, &pi->pi_gmlist, pgf_next,
                            pgftmp) {
                                if (pgf->pgf_file)
                                        (void) fclose(pgf->pgf_file);
                                LIST_REMOVE(pgf, pgf_next);
                                free(pgf);
                        }
                        if (pi->pi_symbols)
                                free(pi->pi_symbols);

                        LIST_REMOVE(pi, pi_next);
                        free(pi);
                }

                LIST_FOREACH_SAFE(pp, &pmcstat_process_hash[i], pp_next,
                    pptmp) {
                        LIST_REMOVE(pp, pp_next);
                        free(pp);
                }
        }

        pmcstat_string_shutdown();

        /*
         * Print errors unless -q was specified.  Print all statistics
         * if verbosity > 1.
         */
#define PRINT(N,V,A) do {                                               \
                if (pmcstat_stats.ps_##V || (A)->pa_verbosity >= 2)     \
                        (void) fprintf((A)->pa_printfile, " %-40s %d\n",\
                            N, pmcstat_stats.ps_##V);                   \
        } while (0)

        if (a->pa_verbosity >= 1 && a->pa_flags & FLAG_DO_GPROF) {
                (void) fprintf(a->pa_printfile, "CONVERSION STATISTICS:\n");
                PRINT("#exec/a.out", exec_aout, a);
                PRINT("#exec/elf", exec_elf, a);
                PRINT("#exec/unknown", exec_indeterminable, a);
                PRINT("#exec handling errors", exec_errors, a);
                PRINT("#samples/total", samples_total, a);
                PRINT("#samples/unclaimed", samples_unknown_offset, a);
                PRINT("#samples/unknown-object", samples_indeterminable, a);
                PRINT("#callchain/dubious-frames", callchain_dubious_frames,
                    a);
        }

        if (mf)
                (void) fclose(mf);
}