/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * Postmortem type identification
 * ------------------------------
 *
 * When debugging kernel memory corruption problems, one often determines that
 * the corrupted buffer has been erroneously written to by a user of an
 * adjacent buffer -- determining the specifics of the adjacent buffer can
 * therefore offer insight into the cause of the corruption.  To determine the
 * type of an arbitrary memory buffer, however, one has historically been
 * forced to use dcmds ::kgrep and ::whatis in alternating succession; when an
 * object of known type is finally reached, types can be back-propagated to
 * determine the type of the unknown object.
 *
 * This process is labor-intensive and error-prone.  Using CTF data and a
 * collection of heuristics, we would like to both automate this process and
 * improve on it.
 *
 * We start by constructing the pointer graph.  Each node in the graph is
 * a memory object (either a static object from module data, or a dynamically
 * allocated memory object); the node's outgoing edges represent pointers from
 * the object to other memory objects in the system.
 *
 * Once the graph is constructed, we start at nodes of known type, and use the
 * type information to determine the type of each pointer represented by an
 * outgoing edge.  Determining the pointer type allows us to determine the
 * type of the edge's destination node, and therefore to iteratively continue
 * the process of type identification.  This process works as long as all
 * pointed-to objects are exactly the size of their inferred types.
 *
 * Unfortunately, pointed-to objects are often _not_ the size of the pointed-to
 * type.  This is largely due to three phenomena:
 *
 * (a)	C makes no distinction between a pointer to a single object and a
 *	pointer to some number of objects of like type.
 *
 * (b)	C performs no bounds checking on array indexing, allowing declarations
 *	of structures that are implicitly followed by arrays of the type of the
 *	structure's last member.  These declarations most often look like:
 *
 *	    typedef struct foo {
 *	            int       foo_bar;
 *	            int       foo_baz;
 *	            mumble_t  foo_mumble[1];
 *	    } foo_t;
 *
 *	When a foo_t is allocated, the size of n - 1 mumble_t's is added to the
 *	size of a foo_t to derive the size of the allocation; this allows for
 *	the n trailing mumble_t's to be referenced from the allocated foo_t
 *	using C's convenient array syntax -- without requiring an additional
 *	memory dereference.  ISO C99 calls the last member in such a structure
 *	the "flexible array member" (FAM); we adhere to this terminology.
 *
 * (c)	It is not uncommon for structures to embed smaller structures, and
 *	to pass pointers to these smaller structures to routines that track
 *	the structures only by the smaller type.  This can be thought of as
 *	a sort of crude-but-efficient polymorphism; see e.g., struct seg and
 *	its embedded avl_node_t.  It is less common (but by no means unheard
 *	of) for the smaller structures to be used as place holders in data
 *	structures consisting of the larger structure.  That is, instead of an
 *	instance of the larger structure being pointed to by the smaller
 *	structure pointer, an instance of the smaller structure is pointed to
 *	the larger structure pointer; see e.g., struct buf and struct hbuf or
 *	struct seg_pcache and struct seg_phash.  This construct is particularly
 *	important to identify when the smaller structures are in a contiguous
 *	array (as they are in each of the two examples provided):  by examining
 *	only the data structure of larger structures, one would erroneously
 *	assume that the array of the smaller structure is actually an array of
 *	the larger structure.
 *
 * Taken together, these three phenomena imply that if we have a pointer to
 * an object that is larger than the pointed-to type, we don't know if the
 * object is an array of objects of the pointed-to type, the pointed-to type
 * followed by an array of that type's last member, or some other larger type
 * that we haven't yet discovered.
 *
 * Differentiating these three situations is the focus of many of the
 * type graph heuristics.  Type graph processing is performed in an initial
 * pass, four type-determining passes, and a final, post-pass:
 *
 * Initial: Graph construction
 *
 * The initial pass constructs the nodes from the kmem caches and module data,
 * and constructs the edges by propagating out from module data.  Nodes that
 * are in module data or known kmem caches (see tg_cachetab[], below) are
 * marked with their known type.  This pass takes the longest amount of
 * wall-clock time, for it frequently induces I/O to read the postmortem image
 * into memory from permanent storage.
 *
 * pass1: Conservative propagation
 *
 * In pass1, we propagate types out from the known nodes, adding types to
 * nodes' tgn_typelists as they are inferred.  Nodes are marked as they are
 * processed to guarantee halting.  We proceed as conservatively as possible
 * in this pass; if we discover that a node is larger than twice its inferred
 * type (that is, we've run into one of the three phenomena described above),
 * we add the inferred type to the node's tgn_typelist, but we don't descend.
 *
 * pass2: Array determination
 *
 * In pass2, we visit those nodes through which we refused to descend in pass1.
 * If we find one (and only one) structural interpretation for the object, we
 * have determined that -- to the best of our knowledge -- we are not seeing
 * phenomenon (c).  To further differentiate (a) from (b), we check if the
 * structure ends with an array of size one; if it does, we assume that it has
 * a flexible array member.  Otherwise, we perform an additional check:  we
 * calculate the size of the object modulo the size of the inferred type and
 * subtract it from the size of the object.  If this value is less than or
 * equal to the size of the next-smaller kmem cache, we know that it's not an
 * array of the inferred type -- if it were an array of the inferred type, it
 * would have been instead allocated out of the next-smaller cache.
 *
 * In either case (FAM or no FAM), we iterate through each element of the
 * hypothesised array, checking that each pointer member points to either NULL
 * or valid memory.  If pointer members do not satisfy these criteria, it is
 * assumed that we have not satisfactorily determined that the given object is
 * an array of the inferred type, and we abort processing of the node.  Note
 * that uninitialized pointers can potentially prevent an otherwise valid
 * array from being interpreted as such.  Because array misinterpretation
 * can induce substantial cascading type misinterpretation, it is preferred to
 * be conservative and accurate in such cases -- even if it means a lower type
 * recognition rate.
 *
 * pass3: Type coalescence
 *
 * pass3 coalesces type possibilities by preferring structural possibilities
 * over non-structural ones.  For example, if an object is either of type
 * "char" (pointed to by a caddr_t) or type "struct frotz", the possibilities
 * will be coalesced into just "struct frotz."
 *
 * pass4: Non-array type inference
 *
 * pass4 is the least conservative:  it is assumed that phenomenon (c) has been
 * completely ferreted out by prior passes.  All unknown types are visited, and
 * incoming edges are checked.  If there is only one possible structural
 * inference for the unknown type, the node is inferred to be of that type, and
 * the type is propagated.  This pass picks up those nodes that are larger than
 * their inferred type, but for which the inferred type is likely accurate.
 * (struct dcentry, with its FAM of characters, is an example type that is
 * frequently determined by this pass.)
 *
 * Post-pass: Greatest unknown reach
 *
 * If recognition rate is low (or, from a more practical perspective, if the
 * object of interest is not automatically identified), it can be useful
 * to know which node is the greatest impediment to further recognition.
 * If the user can -- by hook or by crook -- determine the true type of this
 * node (and set it with ::istype), much more type identification should be
 * possible.  To facilitate this, we therefore define the _reach_ of a node to
 * be the number of unknown nodes that could potentially be identified were the
 * node's type better known.  We determine the reach by performing a
 * depth-first pass through the graph.  The node of greatest reach (along with
 * the reach itself) are reported upon completion of the post-pass.
 */

#include <mdb/mdb_param.h>
#include <mdb/mdb_modapi.h>
#include <mdb/mdb_ctf.h>
#include <sys/sysmacros.h>
#include <sys/kmem_impl.h>
#include <sys/vmem_impl.h>
#include <sys/modctl.h>
#include <sys/kobj.h>
#include <stdio.h>
#include "kmem.h"

struct tg_node;

typedef struct tg_edge {
	struct tg_node	*tge_src;	/* source node */
	struct tg_node	*tge_dest;	/* destination node */
	uintptr_t	tge_srcoffs;	/* offset in source node */
	uintptr_t	tge_destoffs;	/* offset in destination node */
	struct tg_edge	*tge_nextin;	/* next incoming edge */
	struct tg_edge	*tge_nextout;	/* next outgoing edge */
	int		tge_marked;	/* mark */
} tg_edge_t;

typedef struct tg_type {
	mdb_ctf_id_t	tgt_type;	/* CTF type */
	mdb_ctf_id_t	tgt_utype;	/* unresolved CTF type */
	mdb_ctf_id_t	tgt_rtype;	/* referring type */
	size_t		tgt_roffs;	/* referring offset */
	const char	*tgt_rmember;	/* referring member */
	tg_edge_t	*tgt_redge;	/* referring edge */
	struct tg_type	*tgt_next;	/* next type */
	int		tgt_flags;	/* flags */
} tg_type_t;

#define	TG_TYPE_ARRAY		0x0001
#define	TG_TYPE_NOTARRAY	0x0002
#define	TG_TYPE_HASFAM		0x0004

typedef struct tg_node {
	uintptr_t	tgn_base;	/* address base of object */
	uintptr_t	tgn_limit;	/* address limit of object */
	tg_edge_t	*tgn_incoming;	/* incoming edges */
	tg_edge_t	*tgn_outgoing;	/* outgoing edges */
	tg_type_t	*tgn_typelist;	/* conjectured typelist */
	tg_type_t	*tgn_fraglist;	/* type fragment list */
	char		tgn_marked;	/* marked */
	char		tgn_postmarked;	/* marked in postpass */
	int		tgn_smaller;	/* size of next-smaller cache */
	int		tgn_reach;	/* number of reachable unknown nodes */
	mdb_ctf_id_t	tgn_type;	/* known type */
} tg_node_t;

#define	TG_NODE_SIZE(n)		((n)->tgn_limit - (n)->tgn_base)

typedef struct tg_stats {
	size_t	tgs_buffers;
	size_t	tgs_nodes;
	size_t	tgs_unmarked;
	size_t	tgs_known;
	size_t	tgs_typed;
	size_t	tgs_conflicts;
	size_t	tgs_frag;
	size_t	tgs_candidates;
} tg_stats_t;

typedef struct tg_typeoffs {
	mdb_ctf_id_t		tgto_type;	/* found type */
	ulong_t			tgto_offs;	/* offset of interest */
	const char		**tgto_memberp;	/* referring member name */
	tg_edge_t		*tgto_edge;	/* outbound edge */
} tg_typeoffs_t;

typedef struct tg_buildstate {
	uintptr_t		tgbs_addr;	/* address of region */
	uintptr_t		*tgbs_buf;	/* in-core copy of region */
	size_t			tgbs_ndx;	/* current pointer index */
	size_t			tgbs_nptrs;	/* number of pointers */
	tg_node_t		*tgbs_src;	/* corresponding node */
	struct tg_buildstate	*tgbs_next;	/* next stacked or free */
} tg_buildstate_t;

typedef struct tg_poststate {
	tg_node_t		*tgps_node;	/* current node */
	tg_edge_t		*tgps_edge;	/* current edge */
	size_t			tgps_total;	/* current total */
	struct tg_poststate	*tgps_next;	/* next stacked or free */
} tg_poststate_t;

typedef struct tg_todo {
	tg_node_t		*tgtd_node;	/* node to process */
	uintptr_t		tgtd_offs;	/* offset within node */
	mdb_ctf_id_t		tgtd_type;	/* conjectured type */
	struct tg_todo		*tgtd_next;	/* next todo */
} tg_todo_t;

typedef struct tg_nodedata {
	tg_node_t		*tgd_next;	/* next node to fill in */
	size_t			tgd_size;	/* size of this node */
} tg_nodedata_t;

/*
 * Some caches can be pretty arduous to identify (or are rife with conflicts).
 * To assist type identification, specific caches are identified with the
 * types of their contents.  Each cache need _not_ be listed here; in general,
 * a cache should only be added to the tg_cachetab[] if the identification rate
 * for the cache is less than 95%Every .  (The identification rate for a
 * specific cache can be quickly determined by specifying the cache to
 * ::typegraph.)
 */
struct {
	char *tgc_name;
	char *tgc_type;
} tg_cachetab[] = {
	{ "streams_mblk",	"mblk_t" },
	{ "seg_cache",		"struct seg" },
	{ "segvn_cache",	"struct segvn_data" },
	{ "anon_cache",		"struct anon" },
	{ "ufs_inode_cache",	"inode_t" },
	{ "hme_cache",		"struct hment" },
	{ "queue_cache",	"queinfo_t" },
	{ "sock_cache",		"struct sonode" },
	{ "ire_cache",		"ire_t" },
	{ NULL,			NULL }
};

/*
 * Some types are only known by their opaque handles.  While this is a good way
 * to keep interface clients from eating the Forbidden Fruit, it can make type
 * identification difficult -- which can be especially important for big
 * structures like dev_info_t.  To assist type identification, we keep a table
 * to translate from opaque handles to their underlying structures.  A
 * translation should only be added to the tg_typetab[] if the lack of
 * translation is preventing substantial type identification.  (This can be
 * determined by using the "typeunknown" walker on a dump with bufctl auditing
 * enabled, and using "::whatis -b" to determine the types of unknown buffers;
 * if many of these unknown types are structures behind an opaque handle, a
 * new entry in tg_typetab[] is likely warranted.)
 */
struct {
	char		*tgt_type_name;		/* filled in statically */
	char		*tgt_actual_name;	/* filled in statically */
	mdb_ctf_id_t	tgt_type;		/* determined dynamically */
	mdb_ctf_id_t	tgt_actual_type;	/* determined dynamically */
} tg_typetab[] = {
	{ "dev_info_t",		"struct dev_info" },
	{ "ddi_dma_handle_t",	"ddi_dma_impl_t *" },
	{ NULL,			NULL }
};

static enum {
	TG_PASS1 = 1,
	TG_PASS2,
	TG_PASS3,
	TG_PASS4
} tg_pass;

static size_t tg_nnodes;	/* number of nodes */
static size_t tg_nanchored;	/* number of anchored nodes */
static tg_node_t *tg_node;	/* array of nodes */
static tg_node_t **tg_sorted;	/* sorted array of pointers into tg_node */
static size_t tg_nsorted;	/* number of pointers in tg_sorted */
static int *tg_sizes;		/* copy of kmem_alloc_sizes[] array */
static int tg_nsizes;		/* number of sizes in tg_sizes */
static hrtime_t tg_start;	/* start time */
static int tg_improved;		/* flag indicating that we have improved */
static int tg_built;		/* flag indicating that type graph is built */
static uint_t tg_verbose;	/* flag to increase verbosity */

static mdb_ctf_id_t typegraph_type_offset(mdb_ctf_id_t, size_t,
    tg_edge_t *, const char **);

static void
typegraph_typetab_init(void)
{
	int i;

	for (i = 0; tg_typetab[i].tgt_type_name != NULL; i++) {
		if (mdb_ctf_lookup_by_name(tg_typetab[i].tgt_type_name,
		    &tg_typetab[i].tgt_type) == -1) {
			mdb_warn("can't find type '%s'\n",
			    tg_typetab[i].tgt_type_name);
			mdb_ctf_type_invalidate(&tg_typetab[i].tgt_type);
			continue;
		}

		if (mdb_ctf_lookup_by_name(tg_typetab[i].tgt_actual_name,
		    &tg_typetab[i].tgt_actual_type) == -1) {
			mdb_warn("can't find type '%s'\n",
			    tg_typetab[i].tgt_actual_name);
			mdb_ctf_type_invalidate(&tg_typetab[i].tgt_actual_type);
		}
	}
}

/*
 * A wrapper around mdb_ctf_type_resolve() that first checks the type
 * translation table.
 */
static mdb_ctf_id_t
typegraph_resolve(mdb_ctf_id_t type)
{
	int i;
	mdb_ctf_id_t ret;

	/*
	 * This could be _much_ more efficient...
	 */
	for (i = 0; tg_typetab[i].tgt_type_name != NULL; i++) {
		if (mdb_ctf_type_cmp(type, tg_typetab[i].tgt_type) == 0) {
			type = tg_typetab[i].tgt_actual_type;
			break;
		}
	}

	(void) mdb_ctf_type_resolve(type, &ret);
	return (ret);
}

/*
 * A wrapper around mdb_ctf_type_name() that deals with anonymous structures.
 * Anonymous structures are those that have no name associated with them.
 * Nearly always, these structures are referred to by a typedef (e.g.
 * "typedef struct { int bar } foo_t"); we expect the unresolved type to
 * be passed as utype.
 */
static char *
typegraph_type_name(mdb_ctf_id_t type, mdb_ctf_id_t utype)
{
	static char buf[MDB_SYM_NAMLEN];

	if (mdb_ctf_type_name(type, buf, sizeof (buf)) == NULL) {
		(void) strcpy(buf, "<unknown>");
	} else {
		/*
		 * Perhaps a CTF interface would be preferable to this kludgey
		 * strcmp()?  Perhaps.
		 */
		if (strcmp(buf, "struct ") == 0)
			(void) mdb_ctf_type_name(utype, buf, sizeof (buf));
	}

	return (buf);
}

/*
 * A wrapper around mdb_ctf_type_size() that accurately accounts for arrays.
 */
static ssize_t
typegraph_size(mdb_ctf_id_t type)
{
	mdb_ctf_arinfo_t arr;
	ssize_t size;

	if (!mdb_ctf_type_valid(type))
		return (-1);

	if (mdb_ctf_type_kind(type) != CTF_K_ARRAY)
		return (mdb_ctf_type_size(type));

	if (mdb_ctf_array_info(type, &arr) == -1)
		return (-1);

	type = typegraph_resolve(arr.mta_contents);

	if (!mdb_ctf_type_valid(type))
		return (-1);

	if ((size = mdb_ctf_type_size(type)) == -1)
		return (-1);

	return (size * arr.mta_nelems);
}

/*
 * The mdb_ctf_member_iter() callback for typegraph_type_offset().
 */
static int
typegraph_offiter(const char *name, mdb_ctf_id_t type,
    ulong_t off, tg_typeoffs_t *toffs)
{
	int kind;
	ssize_t size;
	mdb_ctf_arinfo_t arr;

	off /= NBBY;

	if (off > toffs->tgto_offs) {
		/*
		 * We went past it; return failure.
		 */
		return (1);
	}

	if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
		return (0);

	if ((size = mdb_ctf_type_size(type)) == -1)
		return (0);

	if (off < toffs->tgto_offs &&
	    size != 0 && off + size <= toffs->tgto_offs) {
		/*
		 * Haven't reached it yet; continue looking.
		 */
		return (0);
	}

	/*
	 * If the base type is not a structure, an array or a union, and
	 * the offset equals the desired offset, we have our type.
	 */
	if ((kind = mdb_ctf_type_kind(type)) != CTF_K_STRUCT &&
	    kind != CTF_K_UNION && kind != CTF_K_ARRAY) {
		if (off == toffs->tgto_offs)
			toffs->tgto_type = type;

		if (toffs->tgto_memberp != NULL)
			*(toffs->tgto_memberp) = name;

		return (1);
	}

	/*
	 * If the type is an array, see if we fall within the bounds.
	 */
	if (kind == CTF_K_ARRAY) {
		if (mdb_ctf_array_info(type, &arr) == -1)
			return (0);

		type = typegraph_resolve(arr.mta_contents);

		if (!mdb_ctf_type_valid(type))
			return (0);

		size = mdb_ctf_type_size(type) * arr.mta_nelems;

		if (off < toffs->tgto_offs && off + size <= toffs->tgto_offs) {
			/*
			 * Nope, haven't found it yet; continue looking.
			 */
			return (0);
		}
	}

	toffs->tgto_type = typegraph_type_offset(type,
	    toffs->tgto_offs - off, toffs->tgto_edge, toffs->tgto_memberp);

	return (1);
}

/*
 * The mdb_ctf_member_iter() callback for typegraph_type_offset() when the type
 * is found to be of kind CTF_K_UNION.  With unions, we attempt to do better
 * than just completely punting:  if all but one of the members is impossible
 * (due to, say, size constraints on the destination node), we can propagate
 * the valid member.
 */
static int
typegraph_union(const char *name, mdb_ctf_id_t type, ulong_t off,
    tg_typeoffs_t *toffs)
{
	const char *member = name;
	tg_edge_t *e = toffs->tgto_edge;
	mdb_ctf_id_t rtype;
	size_t rsize;
	int kind;

	if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
		return (0);

	kind = mdb_ctf_type_kind(type);

	if (kind == CTF_K_STRUCT || kind != CTF_K_UNION ||
	    kind != CTF_K_ARRAY) {
		type = typegraph_type_offset(type,
		    toffs->tgto_offs - off, e, &member);
	}

	if (!mdb_ctf_type_valid(type))
		return (0);

	if (mdb_ctf_type_kind(type) != CTF_K_POINTER)
		return (0);

	/*
	 * Now figure out what exactly we're pointing to.
	 */
	if (mdb_ctf_type_reference(type, &rtype) == -1)
		return (0);

	if (!mdb_ctf_type_valid(rtype = typegraph_resolve(rtype)))
		return (0);

	rsize = mdb_ctf_type_size(rtype);

	/*
	 * Compare this size to the size of the thing we're pointing to --
	 * if it's larger than the node that we're pointing to, we know that
	 * the alleged pointer type must be an invalid interpretation of the
	 * union.
	 */
	if (rsize > TG_NODE_SIZE(e->tge_dest) - e->tge_destoffs) {
		/*
		 * We're in luck -- it's not possibly this pointer.
		 */
		return (0);
	}

	/*
	 * This looks like it could be legit.  If the type hasn't been
	 * specified, we could be in business.
	 */
	if (mdb_ctf_type_valid(toffs->tgto_type)) {
		/*
		 * There are two potentially valid interpretations for this
		 * union.  Invalidate the type.
		 */
		mdb_ctf_type_invalidate(&toffs->tgto_type);
		return (1);
	}

	toffs->tgto_type = type;

	if (toffs->tgto_memberp != NULL)
		*(toffs->tgto_memberp) = member;

	return (0);
}

/*ARGSUSED*/
static int
typegraph_lastmember(const char *name,
    mdb_ctf_id_t type, ulong_t off, void *last)
{
	*((mdb_ctf_id_t *)last) = type;

	return (0);
}

/*
 * To determine if a structure is has a flexible array member, we iterate over
 * the members; if the structure has more than one member, and the last member
 * is an array of size 1, we're going to assume that this structure has a
 * flexible array member.  Yes, this heuristic is a little sloppy -- but cut me
 * some slack:  why the hell else would you have an array of size 1?  (Don't
 * answer that.)
 */
static int
typegraph_hasfam(mdb_ctf_id_t type, mdb_ctf_id_t *atype)
{
	mdb_ctf_arinfo_t arr;
	mdb_ctf_id_t last;
	int kind;

	if (!mdb_ctf_type_valid(type))
		return (0);

	if ((kind = mdb_ctf_type_kind(type)) != CTF_K_STRUCT)
		return (0);

	mdb_ctf_type_invalidate(&last);
	mdb_ctf_member_iter(type, typegraph_lastmember, &last);

	if (!mdb_ctf_type_valid(last))
		return (0);

	if ((kind = mdb_ctf_type_kind(last)) == CTF_K_STRUCT)
		return (typegraph_hasfam(last, atype));

	if (kind != CTF_K_ARRAY)
		return (0);

	if (typegraph_size(last) == typegraph_size(type)) {
		/*
		 * This structure has only one member; even if that member is
		 * an array of size 1, we'll assume that there is something
		 * stranger going on than a run-of-the-mill FAM (e.g., a
		 * kmutex_t).
		 */
		return (0);
	}

	if (mdb_ctf_array_info(last, &arr) == -1)
		return (0);

	if (arr.mta_nelems != 1)
		return (0);

	if (atype != NULL)
		*atype = typegraph_resolve(arr.mta_contents);

	return (1);
}

/*
 * This routine takes a type and offset, and returns the type at the specified
 * offset.  It additionally takes an optional edge to help bust unions, and
 * an optional address of a character pointer to set to the name of the member
 * found at the specified offset.
 */
static mdb_ctf_id_t
typegraph_type_offset(mdb_ctf_id_t type, size_t offset, tg_edge_t *e,
    const char **member)
{
	mdb_ctf_arinfo_t arr;
	uint_t kind;
	mdb_ctf_id_t last;
	ssize_t size;
	ssize_t lsize;
	tg_typeoffs_t toffs;
	mdb_ctf_id_t inval;

	mdb_ctf_type_invalidate(&inval);

	if (member != NULL)
		*member = NULL;

	/*
	 * Resolve type to its base type.
	 */
	type = typegraph_resolve(type);
	kind = mdb_ctf_type_kind(type);

	switch (kind) {
	case CTF_K_ARRAY:
		/*
		 * If this is an array, we need to figure out what it's an
		 * array _of_.  We must then figure out the size of the array
		 * structure, and then determine our offset within that type.
		 * From there, we can recurse.
		 */
		if (mdb_ctf_array_info(type, &arr) == -1)
			return (inval);

		type = typegraph_resolve(arr.mta_contents);

		if (!mdb_ctf_type_valid(type))
			return (inval);

		/*
		 * If the type is not a structure/union, then check that the
		 * offset doesn't point to the middle of the base type and
		 * return it.
		 */
		kind = mdb_ctf_type_kind(type);
		size = mdb_ctf_type_size(type);

		if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) {
			if (offset % size) {
				/*
				 * The offset is pointing to the middle of a
				 * type; return failure.
				 */
				return (inval);
			}

			return (type);
		}

		return (typegraph_type_offset(type, offset % size, e, member));

	case CTF_K_STRUCT:
		/*
		 * If the offset is larger than the size, we need to figure
		 * out what exactly we're looking at.  There are several
		 * possibilities:
		 *
		 * (a)	A structure that has this type as its first member.
		 *
		 * (b)	An array of structures of this type.
		 *
		 * (c)	A structure has a flexible array member.
		 *
		 * The differentiation between (a) and (b) has hopefully
		 * happened before entering this function.  To differentiate
		 * between (b) and (c), we call typegraph_hasfam().
		 */
		size = mdb_ctf_type_size(type);

		if (offset >= size) {
			if (typegraph_hasfam(type, &last)) {
				/*
				 * We have a live one.  Take the size, subtract
				 * the size of the last element, and recurse.
				 */
				if (!mdb_ctf_type_valid(last))
					return (inval);

				lsize = mdb_ctf_type_size(last);

				return (typegraph_type_offset(last,
				    offset - size - lsize, e, member));
			}

			offset %= size;
		}

		toffs.tgto_offs = offset;
		toffs.tgto_memberp = member;
		toffs.tgto_edge = e;
		mdb_ctf_type_invalidate(&toffs.tgto_type);

		mdb_ctf_member_iter(type,
		    (mdb_ctf_member_f *)typegraph_offiter, &toffs);

		return (toffs.tgto_type);

	case CTF_K_POINTER:
		if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
			return (inval);

		size = mdb_ctf_type_size(type);

		if (offset % size) {
			/*
			 * The offset is pointing to the middle of a type;
			 * return failure.
			 */
			return (inval);
		}

		return (type);

	case CTF_K_UNION:
		if (e == NULL) {
			/*
			 * We've been given no outbound edge -- we have no way
			 * of figuring out what the hell this union is.
			 */
			return (inval);
		}

		toffs.tgto_offs = offset;
		toffs.tgto_memberp = member;
		toffs.tgto_edge = e;
		mdb_ctf_type_invalidate(&toffs.tgto_type);

		/*
		 * Try to bust the union...
		 */
		if (mdb_ctf_member_iter(type,
		    (mdb_ctf_member_f *)typegraph_union, &toffs) != 0) {
			/*
			 * There was at least one valid pointer in there.
			 * Return "void *".
			 */
			(void) mdb_ctf_lookup_by_name("void *", &type);

			return (type);
		}

		return (toffs.tgto_type);

	default:
		/*
		 * If the offset is anything other than zero, no dice.
		 */
		if (offset != 0)
			return (inval);

		return (type);
	}
}

/*
 * This routine takes an address and a type, and determines if the memory
 * pointed to by the specified address could be of the specified type.
 * This could become significantly more sophisticated, but for now it's pretty
 * simple:  this is _not_ of the specified type if it's a pointer, and either:
 *
 *  (a)	The alignment is not correct given the type that is pointed to.
 *
 *  (b)	The memory pointed to is invalid.  Note that structures that have
 *	uninitialized pointers may cause us to erroneously fail -- but these
 *	structures are a bug anyway (uninitialized pointers can confuse many
 *	analysis tools, including ::findleaks).
 */
static int
typegraph_couldbe(uintptr_t addr, mdb_ctf_id_t type)
{
	int rkind;
	mdb_ctf_id_t rtype;
	uintptr_t val, throwaway;
	size_t rsize;
	char buf[MDB_SYM_NAMLEN];

	if (mdb_ctf_type_kind(type) != CTF_K_POINTER)
		return (1);

	if (mdb_ctf_type_reference(type, &rtype) == -1)
		return (1);

	if (!mdb_ctf_type_valid(rtype = typegraph_resolve(rtype)))
		return (1);

	if (mdb_vread(&val, sizeof (val), addr) == -1) {
		/*
		 * This is definitely unexpected.  We should not be getting
		 * back an error on a node that was successfully read in.
		 * Lacking something better to do, we'll print an error
		 * and return.
		 */
		mdb_warn("failed to evaluate pointer type at address %p", addr);
		return (1);
	}

	rkind = mdb_ctf_type_kind(rtype);

	if (rkind == CTF_K_STRUCT || rkind == CTF_K_UNION) {
		/*
		 * If it's a pointer to a structure or union, it must be
		 * aligned to sizeof (uintptr_t).
		 */
		if (val & (sizeof (uintptr_t) - 1)) {
			if (tg_verbose) {
				mdb_printf("typegraph: pass %d: rejecting "
				    "*%p (%p) as %s: misaligned pointer\n",
				    tg_pass, addr, val,
				    mdb_ctf_type_name(type, buf, sizeof (buf)));
			}

			return (0);
		}
	}

	rsize = mdb_ctf_type_size(rtype);

	if (val == 0 || rsize == 0)
		return (1);

	/*
	 * For our speculative read, we're going to clamp the referenced size
	 * at the size of a pointer.
	 */
	if (rsize > sizeof (uintptr_t))
		rsize = sizeof (uintptr_t);

	if (mdb_vread(&throwaway, rsize, val) == -1) {
		if (tg_verbose) {
			mdb_printf("typegraph: pass %d: rejecting *%p (%p) as"
			    " %s: bad pointer\n", tg_pass, addr, val,
			    mdb_ctf_type_name(type, buf, sizeof (buf)));
		}
		return (0);
	}

	return (1);
}

static int
typegraph_nodecmp(const void *l, const void *r)
{
	tg_node_t *lhs = *(tg_node_t **)l;
	tg_node_t *rhs = *(tg_node_t **)r;

	if (lhs->tgn_base < rhs->tgn_base)
		return (-1);
	if (lhs->tgn_base > rhs->tgn_base)
		return (1);

	return (0);
}

static tg_node_t *
typegraph_search(uintptr_t addr)
{
	ssize_t left = 0, right = tg_nnodes - 1, guess;

	while (right >= left) {
		guess = (right + left) >> 1;

		if (addr < tg_sorted[guess]->tgn_base) {
			right = guess - 1;
			continue;
		}

		if (addr >= tg_sorted[guess]->tgn_limit) {
			left = guess + 1;
			continue;
		}

		return (tg_sorted[guess]);
	}

	return (NULL);
}

static int
typegraph_interested(const kmem_cache_t *c)
{
	vmem_t vmem;

	if (mdb_vread(&vmem, sizeof (vmem), (uintptr_t)c->cache_arena) == -1) {
		mdb_warn("cannot read arena %p for cache '%s'",
		    (uintptr_t)c->cache_arena, c->cache_name);
		return (0);
	}

	/*
	 * If this cache isn't allocating from the kmem_default or the
	 * kmem_firewall vmem arena, we're not interested.
	 */
	if (strcmp(vmem.vm_name, "kmem_default") != 0 &&
	    strcmp(vmem.vm_name, "kmem_firewall") != 0)
		return (0);

	return (1);
}

static int
typegraph_estimate(uintptr_t addr, const kmem_cache_t *c, size_t *est)
{
	if (!typegraph_interested(c))
		return (WALK_NEXT);

	*est += kmem_estimate_allocated(addr, c);

	return (WALK_NEXT);
}

static int
typegraph_estimate_modctl(uintptr_t addr, const struct modctl *m, size_t *est)
{
	struct module mod;

	if (m->mod_mp == NULL)
		return (WALK_NEXT);

	if (mdb_vread(&mod, sizeof (mod), (uintptr_t)m->mod_mp) == -1) {
		mdb_warn("couldn't read modctl %p's module", addr);
		return (WALK_NEXT);
	}

	(*est) += mod.nsyms;

	return (WALK_NEXT);
}

/*ARGSUSED*/
static int
typegraph_estimate_vmem(uintptr_t addr, const vmem_t *vmem, size_t *est)
{
	if (strcmp(vmem->vm_name, "kmem_oversize") != 0)
		return (WALK_NEXT);

	*est += (size_t)(vmem->vm_kstat.vk_alloc.value.ui64 -
	    vmem->vm_kstat.vk_free.value.ui64);

	return (WALK_NEXT);
}

/*ARGSUSED*/
static int
typegraph_buf(uintptr_t addr, void *ignored, tg_nodedata_t *tgd)
{
	tg_node_t *node = tgd->tgd_next++;
	uintptr_t limit = addr + tgd->tgd_size;

	node->tgn_base = addr;
	node->tgn_limit = limit;

	return (WALK_NEXT);
}

/*ARGSUSED*/
static int
typegraph_kmem(uintptr_t addr, const kmem_cache_t *c, tg_node_t **tgp)
{
	tg_node_t *node = *tgp;
	tg_nodedata_t tgd;
	mdb_ctf_id_t type;
	int i, smaller;

	mdb_ctf_type_invalidate(&type);

	if (!typegraph_interested(c))
		return (WALK_NEXT);

	tgd.tgd_size = c->cache_bufsize;
	tgd.tgd_next = *tgp;

	if (mdb_pwalk("kmem", (mdb_walk_cb_t)typegraph_buf, &tgd, addr) == -1) {
		mdb_warn("can't walk kmem for cache %p (%s)", addr,
		    c->cache_name);
		return (WALK_DONE);
	}

	*tgp = tgd.tgd_next;

	for (i = 0; tg_cachetab[i].tgc_name != NULL; i++) {
		if (strcmp(tg_cachetab[i].tgc_name, c->cache_name) != 0)
			continue;

		if (mdb_ctf_lookup_by_name(tg_cachetab[i].tgc_type,
		    &type) == -1) {
			mdb_warn("could not find type '%s', allegedly type "
			    "for cache %s", tg_cachetab[i].tgc_type,
			    c->cache_name);
			break;
		}

		break;
	}

	/*
	 * If this is a named cache (i.e., not from a kmem_alloc_[n] cache),
	 * the nextsize is 0.
	 */
	if (strncmp(c->cache_name, "kmem_alloc_", strlen("kmem_alloc_")) == 0) {
		GElf_Sym sym;
		GElf_Sym sym2;

		if (tg_sizes == NULL) {
			size_t nsizes = 0;
			size_t nsizes_reg = 0;
			size_t nsizes_big = 0;

			if (mdb_lookup_by_name("kmem_alloc_sizes",
			    &sym) == -1) {
				mdb_warn("failed to find 'kmem_alloc_sizes'");
				return (WALK_ERR);
			}
			nsizes_reg = sym.st_size / sizeof (int);

			if (mdb_lookup_by_name("kmem_big_alloc_sizes",
			    &sym2) != -1) {
				nsizes_big = sym2.st_size / sizeof (int);
			}

			nsizes = nsizes_reg + nsizes_big;

			tg_sizes = mdb_zalloc(nsizes * sizeof (int), UM_SLEEP);
			tg_nsizes = nsizes;

			if (mdb_vread(tg_sizes, sym.st_size,
			    (uintptr_t)sym.st_value) == -1) {
				mdb_warn("failed to read kmem_alloc_sizes");
				return (WALK_ERR);
			}
			if (nsizes_big > 0 &&
			    mdb_vread(&tg_sizes[nsizes_reg], sym2.st_size,
			    (uintptr_t)sym2.st_value) == -1) {
				mdb_warn("failed to read kmem_big_alloc_sizes");
				return (WALK_ERR);
			}
		}

		/*
		 * Yes, this is a linear search -- but we're talking about
		 * a pretty small array (38 elements as of this writing), and
		 * only executed a handful of times (for each sized kmem
		 * cache).
		 */
		for (i = 0; i < tg_nsizes; i++) {
			if (tg_sizes[i] == c->cache_bufsize)
				break;
		}

		if (i == tg_nsizes) {
			/*
			 * Something is wrong -- this appears to be a sized
			 * kmem cache, but we can't find its size in the
			 * kmem_alloc_sizes array.  Emit a warning and return
			 * failure.
			 */
			mdb_warn("couldn't find buffer size for %s (%d)"
			    " in kmem_alloc_sizes array\n", c->cache_name,
			    c->cache_bufsize);

			return (WALK_ERR);
		}

		if (i == 0) {
			smaller = 1;
		} else {
			smaller = tg_sizes[i - 1];
		}
	} else {
		smaller = 0;
	}

	for (; node < *tgp; node++) {
		node->tgn_type = type;
		node->tgn_smaller = smaller;
	}

	*tgp = tgd.tgd_next;

	return (WALK_NEXT);
}

/*ARGSUSED*/
static int
typegraph_seg(uintptr_t addr, const vmem_seg_t *seg, tg_node_t **tgp)
{
	tg_nodedata_t tgd;

	tgd.tgd_next = *tgp;
	tgd.tgd_size = seg->vs_end - seg->vs_start;

	typegraph_buf(seg->vs_start, NULL, &tgd);

	*tgp = tgd.tgd_next;
	return (WALK_NEXT);
}

static int
typegraph_vmem(uintptr_t addr, const vmem_t *vmem, tg_node_t **tgp)
{
	if (strcmp(vmem->vm_name, "kmem_oversize") != 0)
		return (WALK_NEXT);

	if (mdb_pwalk("vmem_alloc",
	    (mdb_walk_cb_t)typegraph_seg, tgp, addr) == -1)
		mdb_warn("can't walk vmem for arena %p", addr);

	return (WALK_NEXT);
}

static void
typegraph_build_anchored(uintptr_t addr, size_t size, mdb_ctf_id_t type)
{
	uintptr_t *buf;
	tg_buildstate_t *state = NULL, *new_state, *free = NULL;
	tg_node_t *node, *src;
	tg_edge_t *edge;
	size_t nptrs, ndx;
	uintptr_t min = tg_sorted[0]->tgn_base;
	uintptr_t max = tg_sorted[tg_nnodes - 1]->tgn_limit;
	ssize_t rval;
	int mask = sizeof (uintptr_t) - 1;

	if (addr == 0 || size < sizeof (uintptr_t))
		return;

	/*
	 * Add an anchored node.
	 */
	src = &tg_node[tg_nnodes + tg_nanchored++];
	src->tgn_base = addr;
	src->tgn_limit = addr + size;
	src->tgn_type = type;

push:
	/*
	 * If our address isn't pointer-aligned, we need to align it and
	 * whack the size appropriately.
	 */
	if (addr & mask) {
		if ((mask + 1) - (addr & mask) >= size)
			goto out;

		size -= (mask + 1) - (addr & mask);
		addr += (mask + 1) - (addr & mask);
	}

	nptrs = size / sizeof (uintptr_t);
	buf = mdb_alloc(size, UM_SLEEP);
	ndx = 0;

	if ((rval = mdb_vread(buf, size, addr)) != size) {
		mdb_warn("couldn't read ptr at %p (size %ld); rval is %d",
		    addr, size, rval);
		goto out;
	}
pop:
	for (; ndx < nptrs; ndx++) {
		uintptr_t ptr = buf[ndx];

		if (ptr < min || ptr >= max)
			continue;

		if ((node = typegraph_search(ptr)) == NULL)
			continue;

		/*
		 * We need to record an edge to us.
		 */
		edge = mdb_zalloc(sizeof (tg_edge_t), UM_SLEEP);

		edge->tge_src = src;
		edge->tge_dest = node;
		edge->tge_nextout = src->tgn_outgoing;
		src->tgn_outgoing = edge;

		edge->tge_srcoffs += ndx * sizeof (uintptr_t);
		edge->tge_destoffs = ptr - node->tgn_base;
		edge->tge_nextin = node->tgn_incoming;
		node->tgn_incoming = edge;

		/*
		 * If this node is marked, we don't need to descend.
		 */
		if (node->tgn_marked)
			continue;

		/*
		 * We need to descend.  To minimize the resource consumption
		 * of type graph construction, we avoid recursing.
		 */
		node->tgn_marked = 1;

		if (free != NULL) {
			new_state = free;
			free = free->tgbs_next;
		} else {
			new_state =
			    mdb_zalloc(sizeof (tg_buildstate_t), UM_SLEEP);
		}

		new_state->tgbs_src = src;
		src = node;

		new_state->tgbs_addr = addr;
		addr = node->tgn_base;
		size = node->tgn_limit - addr;

		new_state->tgbs_next = state;
		new_state->tgbs_buf = buf;
		new_state->tgbs_ndx = ndx + 1;
		new_state->tgbs_nptrs = nptrs;
		state = new_state;
		goto push;
	}

	/*
	 * If we're here, then we have completed this region.  We need to
	 * free our buffer, and update our "resident" counter accordingly.
	 */
	mdb_free(buf, size);

out:
	/*
	 * If we have pushed state, we need to pop it.
	 */
	if (state != NULL) {
		buf = state->tgbs_buf;
		ndx = state->tgbs_ndx;
		src = state->tgbs_src;
		nptrs = state->tgbs_nptrs;
		addr = state->tgbs_addr;

		size = nptrs * sizeof (uintptr_t);

		new_state = state->tgbs_next;
		state->tgbs_next = free;
		free = state;
		state = new_state;

		goto pop;
	}

	while (free != NULL) {
		state = free;
		free = free->tgbs_next;
		mdb_free(state, sizeof (tg_buildstate_t));
	}
}

static void
typegraph_build(uintptr_t addr, size_t size)
{
	uintptr_t limit = addr + size;
	char name[MDB_SYM_NAMLEN];
	GElf_Sym sym;
	mdb_ctf_id_t type;

	do {
		if (mdb_lookup_by_addr(addr, MDB_SYM_EXACT, name,
		    sizeof (name), &sym) == -1) {
			addr++;
			continue;
		}

		if (sym.st_size == 0) {
			addr++;
			continue;
		}

		if (strcmp(name, "kstat_initial") == 0) {
			/*
			 * Yes, this is a kludge.  "kstat_initial" ends up
			 * backing the kstat vmem arena -- so we don't want
			 * to include it as an anchor node.
			 */
			addr += sym.st_size;
			continue;
		}

		/*
		 * We have the symbol; now get its type.
		 */
		if (mdb_ctf_lookup_by_addr(addr, &type) == -1) {
			addr += sym.st_size;
			continue;
		}

		if (!mdb_ctf_type_valid(type)) {
			addr += sym.st_size;
			continue;
		}

		if (!mdb_ctf_type_valid(type = typegraph_resolve(type))) {
			addr += sym.st_size;
			continue;
		}

		typegraph_build_anchored(addr, (size_t)sym.st_size, type);
		addr += sym.st_size;
	} while (addr < limit);
}

/*ARGSUSED*/
static int
typegraph_thread(uintptr_t addr, const kthread_t *t, mdb_ctf_id_t *type)
{
	/*
	 * If this thread isn't already a node, add it as an anchor.  And
	 * regardless, set its type to be the specified type.
	 */
	tg_node_t *node;

	if ((node = typegraph_search(addr)) == NULL) {
		typegraph_build_anchored(addr, mdb_ctf_type_size(*type), *type);
	} else {
		node->tgn_type = *type;
	}

	return (WALK_NEXT);
}

/*ARGSUSED*/
static int
typegraph_kstat(uintptr_t addr, const vmem_seg_t *seg, mdb_ctf_id_t *type)
{
	size_t size = mdb_ctf_type_size(*type);

	typegraph_build_anchored(seg->vs_start, size, *type);

	return (WALK_NEXT);
}

static void
typegraph_node_addtype(tg_node_t *node, tg_edge_t *edge, mdb_ctf_id_t rtype,
    const char *rmember, size_t roffs, mdb_ctf_id_t utype, mdb_ctf_id_t type)
{
	tg_type_t *tp;
	tg_type_t **list;

	if (edge->tge_destoffs == 0) {
		list = &node->tgn_typelist;
	} else {
		list = &node->tgn_fraglist;
	}

	/*
	 * First, search for this type in the type list.
	 */
	for (tp = *list; tp != NULL; tp = tp->tgt_next) {
		if (mdb_ctf_type_cmp(tp->tgt_type, type) == 0)
			return;
	}

	tp = mdb_zalloc(sizeof (tg_type_t), UM_SLEEP);
	tp->tgt_next = *list;
	tp->tgt_type = type;
	tp->tgt_rtype = rtype;
	tp->tgt_utype = utype;
	tp->tgt_redge = edge;
	tp->tgt_roffs = roffs;
	tp->tgt_rmember = rmember;
	*list = tp;

	tg_improved = 1;
}

static void
typegraph_stats_node(tg_node_t *node, tg_stats_t *stats)
{
	tg_edge_t *e;

	stats->tgs_nodes++;

	if (!node->tgn_marked)
		stats->tgs_unmarked++;

	if (mdb_ctf_type_valid(node->tgn_type)) {
		stats->tgs_known++;
		return;
	}

	if (node->tgn_typelist != NULL) {
		stats->tgs_typed++;

		if (node->tgn_typelist->tgt_next)
			stats->tgs_conflicts++;

		return;
	}

	if (node->tgn_fraglist != NULL) {
		stats->tgs_frag++;
		return;
	}

	/*
	 * This node is not typed -- but check if any of its outgoing edges
	 * were successfully typed; such nodes represent candidates for
	 * an exhaustive type search.
	 */
	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
		if (e->tge_dest->tgn_typelist) {
			stats->tgs_candidates++;
			break;
		}
	}
}

/*ARGSUSED*/
static int
typegraph_stats_buffer(uintptr_t addr, void *ignored, tg_stats_t *stats)
{
	tg_node_t *node;

	stats->tgs_buffers++;

	if ((node = typegraph_search(addr)) == NULL) {
		return (WALK_NEXT);
	}

	typegraph_stats_node(node, stats);

	return (WALK_NEXT);
}

/*ARGSUSED*/
void
typegraph_stat_print(char *name, size_t stat)
{
	mdb_printf("typegraph: ");

	if (name == NULL) {
		mdb_printf("\n");
		return;
	}

	mdb_printf("%30s => %ld\n", name, stat);
}

static void
typegraph_stat_str(char *name, char *str)
{
	mdb_printf("typegraph: %30s => %s\n", name, str);
}

static void
typegraph_stat_perc(char *name, size_t stat, size_t total)
{
	int perc = (stat * 100) / total;
	int tenths = ((stat * 1000) / total) % 10;

	mdb_printf("typegraph: %30s => %-13ld (%2d.%1d%%)\n", name, stat,
	    perc, tenths);
}

static void
typegraph_stat_time(int last)
{
	static hrtime_t ts;
	hrtime_t pass;

	if (ts == 0) {
		pass = (ts = gethrtime()) - tg_start;
	} else {
		hrtime_t now = gethrtime();

		pass = now - ts;
		ts = now;
	}

	mdb_printf("typegraph: %30s => %lld seconds\n",
	    "time elapsed, this pass", pass / NANOSEC);
	mdb_printf("typegraph: %30s => %lld seconds\n",
	    "time elapsed, total", (ts - tg_start) / NANOSEC);
	mdb_printf("typegraph:\n");

	if (last)
		ts = 0;
}

static void
typegraph_stats(void)
{
	size_t i, n;
	tg_stats_t stats;

	bzero(&stats, sizeof (stats));

	for (i = 0; i < tg_nnodes - tg_nanchored; i++)
		typegraph_stats_node(&tg_node[i], &stats);

	n = stats.tgs_nodes;

	typegraph_stat_print("pass", tg_pass);
	typegraph_stat_print("nodes", n);
	typegraph_stat_perc("unmarked", stats.tgs_unmarked, n);
	typegraph_stat_perc("known", stats.tgs_known, n);
	typegraph_stat_perc("conjectured", stats.tgs_typed, n);
	typegraph_stat_perc("conjectured fragments", stats.tgs_frag, n);
	typegraph_stat_perc("known or conjectured",
	    stats.tgs_known + stats.tgs_typed + stats.tgs_frag, n);
	typegraph_stat_print("conflicts", stats.tgs_conflicts);
	typegraph_stat_print("candidates", stats.tgs_candidates);
	typegraph_stat_time(0);
}

/*
 * This is called both in pass1 and in subsequent passes (to propagate new type
 * inferences).
 */
static void
typegraph_pass1_node(tg_node_t *node, mdb_ctf_id_t type)
{
	tg_todo_t *first = NULL, *last = NULL, *free = NULL, *this = NULL;
	tg_todo_t *todo;
	tg_edge_t *e;
	uintptr_t offs = 0;
	size_t size;
	const char *member;

	if (!mdb_ctf_type_valid(type))
		return;
again:
	/*
	 * For each of the nodes corresponding to our outgoing edges,
	 * determine their type.
	 */
	size = typegraph_size(type);

	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
		mdb_ctf_id_t ntype, rtype;
		size_t nsize;
		int kind;

		/*
		 * If we're being called in pass1, we're very conservative:
		 *
		 * (a)	If the outgoing edge is beyond the size of the type
		 *	(and the current node is not the root), we refuse to
		 *	descend.  This situation isn't actually hopeless -- we
		 *	could be looking at array of the projected type -- but
		 *	we'll allow a later phase to pass in that node and its
		 *	conjectured type as the root.
		 *
		 * (b)	If the outgoing edge has a destination offset of
		 *	something other than 0, we'll descend, but we won't
		 *	add the type to the type list of the destination node.
		 *	This allows us to gather information that can later be
		 *	used to perform a more constrained search.
		 */
		if (tg_pass == TG_PASS1 && e->tge_srcoffs - offs > size)
			continue;

		if (offs >= typegraph_size(type))
			continue;

		if (e->tge_srcoffs < offs)
			continue;

		if (e->tge_marked)
			continue;

		ntype = typegraph_type_offset(type,
		    e->tge_srcoffs - offs, e, &member);

		if (!mdb_ctf_type_valid(ntype))
			continue;

		if ((kind = mdb_ctf_type_kind(ntype)) != CTF_K_POINTER)
			continue;

		if (mdb_ctf_type_reference(ntype, &rtype) == -1)
			continue;

		if (!mdb_ctf_type_valid(ntype = typegraph_resolve(rtype)))
			continue;

		kind = mdb_ctf_type_kind(ntype);
		nsize = mdb_ctf_type_size(ntype);

		if (nsize > TG_NODE_SIZE(e->tge_dest) - e->tge_destoffs)
			continue;

		typegraph_node_addtype(e->tge_dest, e, type,
		    member, e->tge_srcoffs - offs, rtype, ntype);

		if (e->tge_dest->tgn_marked)
			continue;

		/*
		 * If our destination offset is 0 and the type that we marked
		 * it with is useful, mark the node that we're
		 * going to visit.  And regardless, mark the edge.
		 */
		if (e->tge_destoffs == 0 && kind == CTF_K_STRUCT)
			e->tge_dest->tgn_marked = 1;

		e->tge_marked = 1;

		/*
		 * If this isn't a structure, it's pointless to descend.
		 */
		if (kind != CTF_K_STRUCT)
			continue;

		if (nsize <= TG_NODE_SIZE(e->tge_dest) / 2) {
			tg_node_t *dest = e->tge_dest;

			/*
			 * If the conjectured type is less than half of the
			 * size of the object, we might be dealing with a
			 * polymorphic type.  It's dangerous to descend in
			 * this case -- if our conjectured type is larger than
			 * the actual type, we will mispropagate.  (See the
			 * description for phenomenon (c) in the block comment
			 * for how this condition can arise.)  We therefore
			 * only descend if we are in pass4 and there is only
			 * one inference for this node.
			 */
			if (tg_pass < TG_PASS4)
				continue;

			if (dest->tgn_typelist == NULL ||
			    dest->tgn_typelist->tgt_next != NULL) {
				/*
				 * There is either no inference for this node,
				 * or more than one -- in either case, chicken
				 * out.
				 */
				continue;
			}
		}

		if (free != NULL) {
			todo = free;
			free = free->tgtd_next;
		} else {
			todo = mdb_alloc(sizeof (tg_todo_t), UM_SLEEP);
		}

		todo->tgtd_node = e->tge_dest;
		todo->tgtd_type = ntype;
		todo->tgtd_offs = e->tge_destoffs;
		todo->tgtd_next = NULL;

		if (last == NULL) {
			first = last = todo;
		} else {
			last->tgtd_next = todo;
			last = todo;
		}
	}

	/*
	 * If this was from a to-do list, it needs to be freed.
	 */
	if (this != NULL) {
		this->tgtd_next = free;
		free = this;
	}

	/*
	 * Now peel something off of the to-do list.
	 */
	if (first != NULL) {
		this = first;
		first = first->tgtd_next;
		if (first == NULL)
			last = NULL;

		node = this->tgtd_node;
		offs = this->tgtd_offs;
		type = this->tgtd_type;
		goto again;
	}

	/*
	 * Nothing more to do -- free the to-do list.
	 */
	while (free != NULL) {
		this = free->tgtd_next;
		mdb_free(free, sizeof (tg_todo_t));
		free = this;
	}
}

static void
typegraph_pass1(void)
{
	int i;

	tg_pass = TG_PASS1;
	for (i = 0; i < tg_nnodes; i++)
		typegraph_pass1_node(&tg_node[i], tg_node[i].tgn_type);
}

static void
typegraph_pass2_node(tg_node_t *node)
{
	mdb_ctf_id_t type, ntype;
	size_t tsize, nsize, rem, offs, limit;
	uintptr_t base, addr;
	int fam, kind;
	tg_type_t *tp, *found = NULL;

	if (mdb_ctf_type_valid(node->tgn_type))
		return;

	for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
		if ((kind = mdb_ctf_type_kind(tp->tgt_type)) == CTF_K_UNION) {
			/*
			 * Fucking unions...
			 */
			found = NULL;
			break;
		}

		if (kind == CTF_K_POINTER || kind == CTF_K_STRUCT) {
			if (found != NULL) {
				/*
				 * There's more than one interpretation for
				 * this structure; for now, we punt.
				 */
				found = NULL;
				break;
			}
			found = tp;
		}
	}

	if (found == NULL ||
	    (found->tgt_flags & (TG_TYPE_ARRAY | TG_TYPE_NOTARRAY)))
		return;

	fam = typegraph_hasfam(type = found->tgt_type, &ntype);

	if (fam) {
		/*
		 * If this structure has a flexible array member, and the
		 * FAM type isn't a struct or pointer, we're going to treat
		 * it as if it did not have a FAM.
		 */
		kind = mdb_ctf_type_kind(ntype);

		if (kind != CTF_K_POINTER && kind != CTF_K_STRUCT)
			fam = 0;
	}

	tsize = typegraph_size(type);
	nsize = TG_NODE_SIZE(node);

	if (!fam) {
		/*
		 * If this doesn't have a flexible array member, and our
		 * preferred type is greater than half the size of the node, we
		 * won't try to treat it as an array.
		 */
		if (tsize > nsize / 2)
			return;

		if ((rem = (nsize % tsize)) != 0) {
			/*
			 * If the next-smaller cache size is zero, we were
			 * expecting the type size to evenly divide the node
			 * size -- we must not have the right type.
			 */
			if (node->tgn_smaller == 0)
				return;

			if (nsize - rem <= node->tgn_smaller) {
				/*
				 * If this were really an array of this type,
				 * we would have allocated it out of a smaller
				 * cache -- it's either not an array (e.g.,
				 * it's a bigger, unknown structure) or it's an
				 * array of some other type.  In either case,
				 * we punt.
				 */
				return;
			}
		}
	}

	/*
	 * So far, this looks like it might be an array.
	 */
	if (node->tgn_smaller != 0) {
		limit = node->tgn_smaller;
	} else {
		limit = TG_NODE_SIZE(node);
	}

	base = node->tgn_base;

	if (fam) {
		found->tgt_flags |= TG_TYPE_HASFAM;

		for (offs = 0; offs < limit; ) {
			ntype = typegraph_type_offset(type, offs, NULL, NULL);

			if (!mdb_ctf_type_valid(ntype)) {
				offs++;
				continue;
			}

			if (!typegraph_couldbe(base + offs, ntype)) {
				found->tgt_flags |= TG_TYPE_NOTARRAY;
				return;
			}

			offs += mdb_ctf_type_size(ntype);
		}
	} else {
		for (offs = 0; offs < tsize; ) {
			ntype = typegraph_type_offset(type, offs, NULL, NULL);

			if (!mdb_ctf_type_valid(ntype)) {
				offs++;
				continue;
			}

			for (addr = base + offs; addr < base + limit;
			    addr += tsize) {
				if (typegraph_couldbe(addr, ntype))
					continue;

				found->tgt_flags |= TG_TYPE_NOTARRAY;
				return;
			}

			offs += mdb_ctf_type_size(ntype);
			continue;
		}
	}

	/*
	 * Now mark this type as an array, and reattempt pass1 from this node.
	 */
	found->tgt_flags |= TG_TYPE_ARRAY;
	typegraph_pass1_node(node, type);
}

static void
typegraph_pass2(void)
{
	int i;

	tg_pass = TG_PASS2;
	do {
		tg_improved = 0;

		for (i = 0; i < tg_nnodes; i++)
			typegraph_pass2_node(&tg_node[i]);
	} while (tg_improved);
}

static void
typegraph_pass3(void)
{
	tg_node_t *node;
	tg_type_t *tp;
	size_t i;
	uintptr_t loffs;

	tg_pass = TG_PASS3;
	loffs = offsetof(tg_node_t, tgn_typelist);

again:
	/*
	 * In this pass, we're going to coalesce types.  We're looking for
	 * nodes where one possible type is a structure, and another is
	 * either a CTF_K_INTEGER variant (e.g. "char", "void") or a
	 * CTF_K_FORWARD (an opaque forward definition).
	 *
	 * N.B.  It might appear to be beneficial to coalesce types when
	 * the possibilities include two structures, and one is contained
	 * within the other (e.g., "door_node" contains a "vnode" as its
	 * first member; "vnode" could be smooshed, leaving just "door_node").
	 * This optimization is overly aggressive, however:  there are too
	 * many places where we pull stunts with structures such that they're
	 * actually polymorphic (e.g., "nc_cache" and "ncache").  Performing
	 * this optimization would run the risk of false propagation --
	 * which we want to avoid if at all possible.
	 */
	for (i = 0; i < tg_nnodes; i++) {
		tg_type_t **list;

		list = (tg_type_t **)((uintptr_t)(node = &tg_node[i]) + loffs);

		if (mdb_ctf_type_valid(node->tgn_type))
			continue;

		if (*list == NULL)
			continue;

		/*
		 * First, scan for type CTF_K_STRUCT.  If we find it, eliminate
		 * everything that's a CTF_K_INTEGER or CTF_K_FORWARD.
		 */
		for (tp = *list; tp != NULL; tp = tp->tgt_next) {
			if (mdb_ctf_type_kind(tp->tgt_type) == CTF_K_STRUCT)
				break;
		}

		if (tp != NULL) {
			tg_type_t *prev = NULL, *next;

			for (tp = *list; tp != NULL; tp = next) {
				int kind = mdb_ctf_type_kind(tp->tgt_type);

				next = tp->tgt_next;

				if (kind == CTF_K_INTEGER ||
				    kind == CTF_K_FORWARD) {
					if (prev == NULL) {
						*list = next;
					} else {
						prev->tgt_next = next;
					}

					mdb_free(tp, sizeof (tg_type_t));
				} else {
					prev = tp;
				}
			}
		}
	}

	if (loffs == offsetof(tg_node_t, tgn_typelist)) {
		loffs = offsetof(tg_node_t, tgn_fraglist);
		goto again;
	}
}

static void
typegraph_pass4_node(tg_node_t *node)
{
	tg_edge_t *e;
	mdb_ctf_id_t type, ntype;
	tg_node_t *src = NULL;
	int kind;

	if (mdb_ctf_type_valid(node->tgn_type))
		return;

	if (node->tgn_typelist != NULL)
		return;

	mdb_ctf_type_invalidate(&type);

	/*
	 * Now we want to iterate over all incoming edges.  If we can find an
	 * incoming edge pointing to offset 0 from a node of known or
	 * conjectured type, check the types of the referring node.
	 */
	for (e = node->tgn_incoming; e != NULL; e = e->tge_nextin) {
		tg_node_t *n = e->tge_src;

		if (e->tge_destoffs != 0)
			continue;

		if (!mdb_ctf_type_valid(ntype = n->tgn_type)) {
			if (n->tgn_typelist != NULL &&
			    n->tgn_typelist->tgt_next == NULL) {
				ntype = n->tgn_typelist->tgt_type;
			}

			if (!mdb_ctf_type_valid(ntype))
				continue;
		}

		kind = mdb_ctf_type_kind(ntype);

		if (kind != CTF_K_STRUCT && kind != CTF_K_POINTER)
			continue;

		if (src != NULL && mdb_ctf_type_cmp(type, ntype) != 0) {
			/*
			 * We have two valid, potentially conflicting
			 * interpretations for this node -- chicken out.
			 */
			src = NULL;
			break;
		}

		src = n;
		type = ntype;
	}

	if (src != NULL)
		typegraph_pass1_node(src, type);
}

static void
typegraph_pass4(void)
{
	size_t i, conjectured[2], gen = 0;

	conjectured[1] = tg_nnodes;

	tg_pass = TG_PASS4;
	do {
		conjectured[gen] = 0;

		for (i = 0; i < tg_nnodes; i++) {
			if (tg_node[i].tgn_typelist != NULL)
				conjectured[gen]++;
			typegraph_pass4_node(&tg_node[i]);
		}

		/*
		 * Perform another pass3 to coalesce any new conflicts.
		 */
		typegraph_pass3();
		tg_pass = TG_PASS4;
		gen ^= 1;
	} while (conjectured[gen ^ 1] < conjectured[gen]);
}

static void
typegraph_postpass_node(tg_node_t *node)
{
	size_t total = 0;
	tg_edge_t *e, *edge = node->tgn_outgoing;
	tg_poststate_t *free = NULL, *stack = NULL, *state;
	tg_node_t *dest;

	if (node->tgn_postmarked)
		return;

push:
	node->tgn_postmarked = 1;
	node->tgn_reach = 0;

pop:
	for (e = edge; e != NULL; e = e->tge_nextout) {
		dest = e->tge_dest;

		if (dest->tgn_postmarked)
			continue;

		/*
		 * Add a new element and descend.
		 */
		if (free == NULL) {
			state = mdb_alloc(sizeof (tg_poststate_t), UM_SLEEP);
		} else {
			state = free;
			free = free->tgps_next;
		}

		state->tgps_node = node;
		state->tgps_edge = e;
		state->tgps_total = total;
		state->tgps_next = stack;
		stack = state;

		node = dest;
		edge = dest->tgn_outgoing;
		goto push;
	}

	if (!mdb_ctf_type_valid(node->tgn_type) &&
	    node->tgn_typelist == NULL && node->tgn_fraglist == NULL) {
		/*
		 * We are an unknown node; our count must reflect this.
		 */
		node->tgn_reach++;
	}

	/*
	 * Now we need to check for state to pop.
	 */
	if ((state = stack) != NULL) {
		edge = state->tgps_edge;
		node = state->tgps_node;
		total = state->tgps_total;
		dest = edge->tge_dest;

		stack = state->tgps_next;
		state->tgps_next = free;
		free = state;

		if (!mdb_ctf_type_valid(dest->tgn_type) &&
		    dest->tgn_typelist == NULL && dest->tgn_fraglist == NULL) {
			/*
			 * We only sum our child's reach into our own if
			 * that child is of unknown type.  This prevents long
			 * chains of non-increasing reach.
			 */
			node->tgn_reach += dest->tgn_reach;
		}

		edge = edge->tge_nextout;
		goto pop;
	}

	/*
	 * We need to free our freelist.
	 */
	while (free != NULL) {
		state = free;
		free = free->tgps_next;
		mdb_free(state, sizeof (tg_poststate_t));
	}
}

static void
typegraph_postpass(void)
{
	int i, max = 0;
	tg_node_t *node, *maxnode = NULL;
	char c[256];

	for (i = 0; i < tg_nnodes; i++)
		tg_node[i].tgn_postmarked = 0;

	/*
	 * From those nodes with unknown type and no outgoing edges, we want
	 * to eminate towards the root.
	 */
	for (i = tg_nnodes - tg_nanchored; i < tg_nnodes; i++) {
		node = &tg_node[i];

		typegraph_postpass_node(node);
	}

	for (i = 0; i < tg_nnodes - tg_nanchored; i++) {
		node = &tg_node[i];

		if (mdb_ctf_type_valid(node->tgn_type))
			continue;

		if (node->tgn_reach < max)
			continue;

		maxnode = node;
		max = node->tgn_reach;
	}

	typegraph_stat_str("pass", "post");

	if (maxnode != NULL) {
		mdb_snprintf(c, sizeof (c), "%p",
		    maxnode->tgn_base, maxnode->tgn_reach);
	} else {
		strcpy(c, "-");
	}

	typegraph_stat_print("nodes", tg_nnodes - tg_nanchored);
	typegraph_stat_str("greatest unknown node reach", c);
	typegraph_stat_perc("reachable unknown nodes",
	    max, tg_nnodes - tg_nanchored);
	typegraph_stat_time(1);
}

static void
typegraph_allpass(int first)
{
	size_t i;
	tg_edge_t *e;

	if (!first)
		tg_start = gethrtime();

	for (i = 0; i < tg_nnodes; i++) {
		tg_node[i].tgn_marked = 0;
		tg_node[i].tgn_postmarked = 0;

		for (e = tg_node[i].tgn_incoming; e != NULL; e = e->tge_nextin)
			e->tge_marked = 0;
	}

	typegraph_pass1();
	typegraph_stats();
	typegraph_pass2();
	typegraph_stats();
	typegraph_pass3();
	typegraph_stats();
	typegraph_pass4();
	typegraph_stats();
	typegraph_postpass();
}

/*ARGSUSED*/
static int
typegraph_modctl(uintptr_t addr, const struct modctl *m, int *ignored)
{
	struct module mod;
	tg_node_t *node;
	mdb_ctf_id_t type;

	if (m->mod_mp == NULL)
		return (WALK_NEXT);

	if (mdb_vread(&mod, sizeof (mod), (uintptr_t)m->mod_mp) == -1) {
		mdb_warn("couldn't read modctl %p's module", addr);
		return (WALK_NEXT);
	}

	/*
	 * As long as we're here, we're going to mark the address pointed
	 * to by mod_mp as a "struct module" (mod_mp is defined to be a
	 * void *).  Yes, this is a horrible kludge -- but it's not like
	 * this code isn't already depending on the fact that mod_mp is
	 * actually a pointer to "struct module" (see the mdb_vread(), above).
	 * Without this, we can't identify any of the objects allocated by
	 * krtld.
	 */
	if ((node = typegraph_search((uintptr_t)m->mod_mp)) != NULL) {
		if (mdb_ctf_lookup_by_name("struct module", &type) != -1)
			node->tgn_type = type;
	}

	typegraph_build((uintptr_t)mod.data, mod.data_size);
	typegraph_build((uintptr_t)mod.bss, mod.bss_size);

	return (WALK_NEXT);
}

static void
typegraph_sort(void)
{
	size_t i;

	if (tg_sorted)
		mdb_free(tg_sorted, tg_nsorted * sizeof (tg_node_t *));

	tg_nsorted = tg_nnodes;
	tg_sorted = mdb_alloc(tg_nsorted * sizeof (tg_node_t *), UM_SLEEP);

	for (i = 0; i < tg_nsorted; i++)
		tg_sorted[i] = &tg_node[i];

	qsort(tg_sorted, tg_nsorted, sizeof (tg_node_t *), typegraph_nodecmp);
}

static void
typegraph_known_node(uintptr_t addr, const char *typename)
{
	tg_node_t *node;
	mdb_ctf_id_t type;

	if ((node = typegraph_search(addr)) == NULL) {
		mdb_warn("couldn't find node corresponding to "
		    "%s at %p\n", typename, addr);
		return;
	}

	if (mdb_ctf_lookup_by_name(typename, &type) == -1) {
		mdb_warn("couldn't find type for '%s'", typename);
		return;
	}

	node->tgn_type = type;
}

/*
 * There are a few important nodes that are impossible to figure out without
 * some carnal knowledge.
 */
static void
typegraph_known_nodes(void)
{
	uintptr_t segkp;

	if (mdb_readvar(&segkp, "segkp") == -1) {
		mdb_warn("couldn't read 'segkp'");
	} else {
		struct seg seg;

		if (mdb_vread(&seg, sizeof (seg), segkp) == -1) {
			mdb_warn("couldn't read seg at %p", segkp);
		} else {
			typegraph_known_node((uintptr_t)seg.s_data,
			    "struct segkp_segdata");
		}
	}
}

/*ARGSUSED*/
int
typegraph(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	size_t est = 0;
	tg_node_t *tgp;
	kmem_cache_t c;
	tg_stats_t stats;
	mdb_ctf_id_t type;
	int wasbuilt = tg_built;
	uintptr_t kstat_arena;
	uint_t perc;
	int i;

	if (!mdb_prop_postmortem) {
		mdb_warn("typegraph: can only be run on a system "
		    "dump; see dumpadm(1M)\n");
		return (DCMD_ERR);
	}

	tg_verbose = 0;

	if (mdb_getopts(argc, argv,
	    'v', MDB_OPT_SETBITS, TRUE, &tg_verbose, NULL) != argc)
		return (DCMD_USAGE);

	if (tg_built)
		goto trace;

	tg_start = gethrtime();
	typegraph_stat_str("pass", "initial");
	typegraph_typetab_init();

	/*
	 * First, we need an estimate on the number of buffers.
	 */
	if (mdb_walk("kmem_cache",
	    (mdb_walk_cb_t)typegraph_estimate, &est) == -1) {
		mdb_warn("couldn't walk 'kmem_cache'");
		return (DCMD_ERR);
	}

	if (mdb_walk("modctl",
	    (mdb_walk_cb_t)typegraph_estimate_modctl, &est) == -1) {
		mdb_warn("couldn't walk 'modctl'");
		return (DCMD_ERR);
	}

	if (mdb_walk("vmem",
	    (mdb_walk_cb_t)typegraph_estimate_vmem, &est) == -1) {
		mdb_warn("couldn't walk 'vmem'");
		return (DCMD_ERR);
	}

	typegraph_stat_print("maximum nodes", est);

	tgp = tg_node = mdb_zalloc(sizeof (tg_node_t) * est, UM_SLEEP);
	for (i = 0; i < est; i++)
		mdb_ctf_type_invalidate(&tg_node[i].tgn_type);

	if (mdb_walk("vmem", (mdb_walk_cb_t)typegraph_vmem, &tgp) == -1) {
		mdb_warn("couldn't walk 'vmem'");
		return (DCMD_ERR);
	}

	if (mdb_walk("kmem_cache", (mdb_walk_cb_t)typegraph_kmem, &tgp) == -1) {
		mdb_warn("couldn't walk 'kmem_cache'");
		return (DCMD_ERR);
	}

	tg_nnodes = tgp - tg_node;

	typegraph_stat_print("actual nodes", tg_nnodes);

	typegraph_sort();

	if (mdb_ctf_lookup_by_name("kthread_t", &type) == -1) {
		mdb_warn("couldn't find 'kthread_t'");
		return (DCMD_ERR);
	}

	if (mdb_walk("thread", (mdb_walk_cb_t)typegraph_thread, &type) == -1) {
		mdb_warn("couldn't walk 'thread'");
		return (DCMD_ERR);
	}

	if (mdb_ctf_lookup_by_name("ekstat_t", &type) == -1) {
		mdb_warn("couldn't find 'ekstat_t'");
		return (DCMD_ERR);
	}

	if (mdb_readvar(&kstat_arena, "kstat_arena") == -1) {
		mdb_warn("couldn't read 'kstat_arena'");
		return (DCMD_ERR);
	}

	if (mdb_pwalk("vmem_alloc", (mdb_walk_cb_t)typegraph_kstat,
	    &type, kstat_arena) == -1) {
		mdb_warn("couldn't walk kstat vmem arena");
		return (DCMD_ERR);
	}

	if (mdb_walk("modctl", (mdb_walk_cb_t)typegraph_modctl, NULL) == -1) {
		mdb_warn("couldn't walk 'modctl'");
		return (DCMD_ERR);
	}

	typegraph_stat_print("anchored nodes", tg_nanchored);
	tg_nnodes += tg_nanchored;
	typegraph_sort();
	typegraph_known_nodes();
	typegraph_stat_time(0);
	tg_built = 1;

trace:
	if (!wasbuilt || !(flags & DCMD_ADDRSPEC)) {
		typegraph_allpass(!wasbuilt);
		return (DCMD_OK);
	}

	bzero(&stats, sizeof (stats));

	/*
	 * If we've been given an address, it's a kmem cache.
	 */
	if (mdb_vread(&c, sizeof (c), addr) == -1) {
		mdb_warn("couldn't read kmem_cache at %p", addr);
		return (DCMD_ERR);
	}

	if (mdb_pwalk("kmem",
	    (mdb_walk_cb_t)typegraph_stats_buffer, &stats, addr) == -1) {
		mdb_warn("can't walk kmem for cache %p", addr);
		return (DCMD_ERR);
	}

	if (DCMD_HDRSPEC(flags))
		mdb_printf("%-25s %7s %7s %7s %7s %7s %7s %5s\n", "NAME",
		    "BUFS", "NODES", "UNMRK", "KNOWN",
		    "INFER", "FRAG", "HIT%");

	if (stats.tgs_nodes) {
		perc = ((stats.tgs_known + stats.tgs_typed +
		    stats.tgs_frag) * 1000) / stats.tgs_nodes;
	} else {
		perc = 0;
	}

	mdb_printf("%-25s %7ld %7ld %7ld %7ld %7ld %7ld %3d.%1d\n",
	    c.cache_name, stats.tgs_buffers, stats.tgs_nodes,
	    stats.tgs_unmarked, stats.tgs_known, stats.tgs_typed,
	    stats.tgs_frag, perc / 10, perc % 10);

	return (DCMD_OK);
}

int
typegraph_built(void)
{
	if (!tg_built) {
		mdb_warn("type graph not yet built; run ::typegraph.\n");
		return (0);
	}

	return (1);
}

int
whattype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	tg_node_t *node;
	tg_edge_t *e;
	char buf[MDB_SYM_NAMLEN];
	tg_type_t *tp;
	int verbose = 0;

	if (mdb_getopts(argc, argv,
	    'v', MDB_OPT_SETBITS, TRUE, &verbose, NULL) != argc)
		return (DCMD_USAGE);

	if (!(flags & DCMD_ADDRSPEC))
		return (DCMD_USAGE);

	if (!typegraph_built())
		return (DCMD_ABORT);

	if ((node = typegraph_search(addr)) == NULL) {
		mdb_warn("%p does not correspond to a node.\n", addr);
		return (DCMD_OK);
	}

	if (!verbose) {
		mdb_printf("%p is %p+%p, ", addr, node->tgn_base,
		    addr - node->tgn_base);

		if (mdb_ctf_type_valid(node->tgn_type)) {
			mdb_printf("%s\n", mdb_ctf_type_name(node->tgn_type,
			    buf, sizeof (buf)));
			return (DCMD_OK);
		}

		if ((tp = node->tgn_typelist) == NULL) {
			if ((tp = node->tgn_fraglist) == NULL) {
				mdb_printf("unknown type\n");
				return (DCMD_OK);
			}
		}

		if (tp->tgt_next == NULL && mdb_ctf_type_valid(tp->tgt_type)) {
			int kind = mdb_ctf_type_kind(tp->tgt_type);
			size_t offs = tp->tgt_redge->tge_destoffs;

			mdb_printf("possibly %s%s ",
			    tp->tgt_flags & TG_TYPE_ARRAY ? "array of " : "",
			    typegraph_type_name(tp->tgt_type, tp->tgt_utype));

			if (kind != CTF_K_STRUCT && kind != CTF_K_UNION &&
			    mdb_ctf_type_valid(tp->tgt_rtype) &&
			    tp->tgt_rmember != NULL) {
				mdb_printf("(%s.%s) ",
				    mdb_ctf_type_name(tp->tgt_rtype, buf,
				    sizeof (buf)), tp->tgt_rmember);
			}

			if (offs != 0)
				mdb_printf("at %p", node->tgn_base + offs);

			mdb_printf("\n");
			return (DCMD_OK);
		}

		mdb_printf("possibly one of the following:\n");

		for (; tp != NULL; tp = tp->tgt_next) {
			size_t offs = tp->tgt_redge->tge_destoffs;

			mdb_printf("  %s%s ",
			    tp->tgt_flags & TG_TYPE_ARRAY ? "array of " : "",
			    typegraph_type_name(tp->tgt_type, tp->tgt_utype));

			if (offs != 0)
				mdb_printf("at %p ", node->tgn_base + offs);

			mdb_printf("(from %p+%p, type %s)\n",
			    tp->tgt_redge->tge_src->tgn_base,
			    tp->tgt_redge->tge_srcoffs,
			    mdb_ctf_type_name(tp->tgt_rtype,
			    buf, sizeof (buf)) != NULL ? buf : "<unknown>");
		}

		mdb_printf("\n");

		return (DCMD_OK);
	}

	mdb_printf("%-?s %-?s %-29s %5s %5s %s\n", "BASE", "LIMIT", "TYPE",
	    "SIZE", "REACH", "MRK");
	mdb_printf("%-?p %-?p %-29s %5d %5d %s\n",
	    node->tgn_base, node->tgn_limit,
	    mdb_ctf_type_name(node->tgn_type,
	    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
	    typegraph_size(node->tgn_type), node->tgn_reach,
	    node->tgn_marked ? "yes" : "no");

	mdb_printf("\n");
	mdb_printf("  %-20s %?s %8s %-20s %s\n",
	    "INFERENCE", "FROM", "SRCOFFS", "REFTYPE", "REFMEMBER");

	for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
		mdb_printf("  %-20s %?p %8p %-20s %s\n",
		    typegraph_type_name(tp->tgt_type, tp->tgt_utype),
		    tp->tgt_redge->tge_src->tgn_base,
		    tp->tgt_redge->tge_srcoffs,
		    mdb_ctf_type_name(tp->tgt_rtype,
		    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
		    tp->tgt_rmember != NULL ? tp->tgt_rmember : "-");
	}

	mdb_printf("\n");
	mdb_printf("  %-20s %?s %8s %-20s %s\n",
	    "FRAGMENT", "FROM", "SRCOFFS", "REFTYPE", "REFMEMBER");

	for (tp = node->tgn_fraglist; tp != NULL; tp = tp->tgt_next) {
		mdb_printf("  %-20s %?p %8p %-20s %s\n",
		    typegraph_type_name(tp->tgt_type, tp->tgt_utype),
		    tp->tgt_redge->tge_src->tgn_base,
		    tp->tgt_redge->tge_srcoffs,
		    mdb_ctf_type_name(tp->tgt_rtype,
		    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
		    tp->tgt_rmember != NULL ? tp->tgt_rmember : "-");
	}

	mdb_printf("\n");

	mdb_printf("  %?s %8s %8s %6s %6s %5s\n", "FROM", "SRCOFFS", "DESTOFFS",
	    "MARKED", "STATUS", "REACH");

	for (e = node->tgn_incoming; e != NULL; e = e->tge_nextin) {
		tg_node_t *n = e->tge_src;

		mdb_printf("  %?p %8p %8p %6s %6s %ld\n",
		    n->tgn_base, e->tge_srcoffs, e->tge_destoffs,
		    e->tge_marked ? "yes" : "no",
		    mdb_ctf_type_valid(n->tgn_type) ? "known" :
		    n->tgn_typelist != NULL ? "inferd" :
		    n->tgn_fraglist != NULL ? "frgmnt" : "unknwn",
		    n->tgn_reach);
	}

	mdb_printf("\n  %?s %8s %8s %6s %6s %5s\n", "TO", "SRCOFFS", "DESTOFFS",
	    "MARKED", "STATUS", "REACH");

	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
		tg_node_t *n = e->tge_dest;

		mdb_printf("  %?p %8p %8p %6s %6s %ld\n",
		    n->tgn_base, e->tge_srcoffs, e->tge_destoffs,
		    e->tge_marked ? "yes" : "no",
		    mdb_ctf_type_valid(n->tgn_type) ? "known" :
		    n->tgn_typelist != NULL ? "inferd" :
		    n->tgn_fraglist != NULL ? "frgmnt" : "unknwn",
		    n->tgn_reach);
	}

	mdb_printf("\n");

	return (DCMD_OK);
}

int
istype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	tg_node_t *node;
	mdb_ctf_id_t type;

	if (!(flags & DCMD_ADDRSPEC) || argc != 1 ||
	    argv[0].a_type != MDB_TYPE_STRING)
		return (DCMD_USAGE);

	if (!typegraph_built())
		return (DCMD_ABORT);

	/*
	 * Determine the node corresponding to the passed address.
	 */
	if ((node = typegraph_search(addr)) == NULL) {
		mdb_warn("%p not found\n", addr);
		return (DCMD_ERR);
	}

	/*
	 * Now look up the specified type.
	 */
	if (mdb_ctf_lookup_by_name(argv[0].a_un.a_str, &type) == -1) {
		mdb_warn("could not find type %s", argv[0].a_un.a_str);
		return (DCMD_ERR);
	}

	node->tgn_type = type;
	typegraph_allpass(0);

	return (DCMD_OK);
}

/*ARGSUSED*/
int
notype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	tg_node_t *node;

	if (!(flags & DCMD_ADDRSPEC) || argc != 0)
		return (DCMD_USAGE);

	if (!typegraph_built())
		return (DCMD_ABORT);

	if ((node = typegraph_search(addr)) == NULL) {
		mdb_warn("%p not found\n", addr);
		return (DCMD_ERR);
	}

	mdb_ctf_type_invalidate(&node->tgn_type);
	typegraph_allpass(0);

	return (DCMD_OK);
}

int
typegraph_walk_init(mdb_walk_state_t *wsp)
{
	wsp->walk_data = (void *)0;
	return (WALK_NEXT);
}

int
typeconflict_walk_step(mdb_walk_state_t *wsp)
{
	size_t ndx;
	tg_node_t *node;

	for (ndx = (size_t)wsp->walk_data; ndx < tg_nnodes; ndx++) {
		node = &tg_node[ndx];

		if (mdb_ctf_type_valid(node->tgn_type))
			continue;

		if (node->tgn_typelist == NULL)
			continue;

		if (node->tgn_typelist->tgt_next == NULL)
			continue;

		break;
	}

	if (ndx == tg_nnodes)
		return (WALK_DONE);

	wsp->walk_data = (void *)++ndx;
	return (wsp->walk_callback(node->tgn_base, NULL, wsp->walk_cbdata));
}

int
typeunknown_walk_step(mdb_walk_state_t *wsp)
{
	size_t ndx;
	tg_node_t *node;

	for (ndx = (size_t)wsp->walk_data; ndx < tg_nnodes; ndx++) {
		node = &tg_node[ndx];

		if (mdb_ctf_type_valid(node->tgn_type))
			continue;

		if (node->tgn_typelist != NULL)
			continue;

		if (node->tgn_fraglist != NULL)
			continue;

		break;
	}

	if (ndx == tg_nnodes)
		return (WALK_DONE);

	wsp->walk_data = (void *)++ndx;
	return (wsp->walk_callback(node->tgn_base, NULL, wsp->walk_cbdata));
}

#define	FINDLOCKS_DEPTH		32

typedef struct foundlock {
	uintptr_t	fnd_addr;
	uintptr_t	fnd_owner;
	const char	*fnd_member[FINDLOCKS_DEPTH];
	mdb_ctf_id_t	fnd_parent;
	tg_node_t	*fnd_node;
} foundlock_t;

typedef struct findlocks {
	uintptr_t	fl_addr;
	uintptr_t	fl_thread;
	size_t		fl_ndx;
	size_t		fl_nlocks;
	foundlock_t	*fl_locks;
	mdb_ctf_id_t	fl_parent;
	tg_node_t	*fl_node;
	const char	*fl_member[FINDLOCKS_DEPTH - 1];
	int		fl_depth;
} findlocks_t;

/*ARGSUSED*/
static int
findlocks_owner(uintptr_t addr, const void *data, void *owner)
{
	*((uintptr_t *)owner) = addr;

	return (WALK_NEXT);
}

static int
findlocks_findmutex(const char *name, mdb_ctf_id_t type, ulong_t offs,
    findlocks_t *fl)
{
	static int called = 0;
	static mdb_ctf_id_t mutex;
	static mdb_ctf_id_t thread;
	mdb_ctf_id_t parent = fl->fl_parent;
	uintptr_t addr = fl->fl_addr;
	int kind, depth = fl->fl_depth, i;
	foundlock_t *found;

	offs /= NBBY;

	if (!called) {
		if (mdb_ctf_lookup_by_name("kmutex_t", &mutex) == -1) {
			mdb_warn("can't find 'kmutex_t' type");
			return (1);
		}

		if (!mdb_ctf_type_valid(mutex = typegraph_resolve(mutex))) {
			mdb_warn("can't resolve 'kmutex_t' type");
			return (1);
		}

		if (mdb_ctf_lookup_by_name("kthread_t", &thread) == -1) {
			mdb_warn("can't find 'kthread_t' type");
			return (1);
		}

		if (!mdb_ctf_type_valid(thread = typegraph_resolve(thread))) {
			mdb_warn("can't resolve 'kthread_t' type");
			return (1);
		}

		called = 1;
	}

	if (!mdb_ctf_type_valid(type))
		return (0);

	type = typegraph_resolve(type);
	kind = mdb_ctf_type_kind(type);

	if (!mdb_ctf_type_valid(type))
		return (0);

	if (kind == CTF_K_ARRAY) {
		mdb_ctf_arinfo_t arr;
		ssize_t size;

		if (mdb_ctf_array_info(type, &arr) == -1)
			return (0);

		type = typegraph_resolve(arr.mta_contents);

		if (!mdb_ctf_type_valid(type))
			return (0);

		/*
		 * Small optimization:  don't bother running through the array
		 * if we know that we can't process the type.
		 */
		kind = mdb_ctf_type_kind(type);
		size = mdb_ctf_type_size(type);

		if (kind == CTF_K_POINTER || kind == CTF_K_INTEGER)
			return (0);

		for (i = 0; i < arr.mta_nelems; i++) {
			fl->fl_addr = addr + offs + (i * size);
			findlocks_findmutex(name, type, 0, fl);
		}

		fl->fl_addr = addr;

		return (0);
	}

	if (kind != CTF_K_STRUCT)
		return (0);

	if (mdb_ctf_type_cmp(type, mutex) == 0) {
		mdb_ctf_id_t ttype;
		uintptr_t owner = 0;
		tg_node_t *node;

		if (mdb_pwalk("mutex_owner",
		    findlocks_owner, &owner, addr + offs) == -1) {
			return (0);
		}

		/*
		 * Check to see if the owner is a thread.
		 */
		if (owner == 0 || (node = typegraph_search(owner)) == NULL)
			return (0);

		if (!mdb_ctf_type_valid(node->tgn_type))
			return (0);

		ttype = typegraph_resolve(node->tgn_type);

		if (!mdb_ctf_type_valid(ttype))
			return (0);

		if (mdb_ctf_type_cmp(ttype, thread) != 0)
			return (0);

		if (fl->fl_thread != 0 && owner != fl->fl_thread)
			return (0);

		if (fl->fl_ndx >= fl->fl_nlocks) {
			size_t nlocks, osize, size;
			foundlock_t *locks;

			if ((nlocks = (fl->fl_nlocks << 1)) == 0)
				nlocks = 1;

			osize = fl->fl_nlocks * sizeof (foundlock_t);
			size = nlocks * sizeof (foundlock_t);

			locks = mdb_zalloc(size, UM_SLEEP);

			if (fl->fl_locks) {
				bcopy(fl->fl_locks, locks, osize);
				mdb_free(fl->fl_locks, osize);
			}

			fl->fl_locks = locks;
			fl->fl_nlocks = nlocks;
		}

		found = &fl->fl_locks[fl->fl_ndx++];
		found->fnd_addr = (uintptr_t)addr + offs;
		found->fnd_owner = owner;

		for (i = 0; i < fl->fl_depth; i++)
			found->fnd_member[i] = fl->fl_member[i];

		found->fnd_member[i] = name;
		found->fnd_parent = fl->fl_parent;
		found->fnd_node = fl->fl_node;

		return (0);
	}

	fl->fl_addr = (uintptr_t)addr + offs;

	if (name == NULL) {
		fl->fl_parent = type;
	} else if (depth < FINDLOCKS_DEPTH - 1) {
		fl->fl_member[depth] = name;
		fl->fl_depth++;
	}

	mdb_ctf_member_iter(type, (mdb_ctf_member_f *)findlocks_findmutex, fl);

	fl->fl_addr = addr;
	fl->fl_parent = parent;
	fl->fl_depth = depth;

	return (0);
}

static void
findlocks_node(tg_node_t *node, findlocks_t *fl)
{
	mdb_ctf_id_t type = node->tgn_type, ntype;
	int kind;
	tg_type_t *tp, *found = NULL;

	if (!mdb_ctf_type_valid(type)) {
		mdb_ctf_type_invalidate(&type);

		for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
			kind = mdb_ctf_type_kind(ntype = tp->tgt_type);

			if (kind == CTF_K_UNION) {
				/*
				 * Insert disparaging comment about unions here.
				 */
				return;
			}

			if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
				continue;

			if (found != NULL) {
				/*
				 * There are multiple interpretations for this
				 * node; we have to punt.
				 */
				return;
			}

			found = tp;
		}
	}

	if (found != NULL)
		type = found->tgt_type;

	fl->fl_parent = type;
	fl->fl_node = node;

	/*
	 * We have our type.  Now iterate for locks.  Note that we don't yet
	 * deal with locks in flexible array members.
	 */
	if (found != NULL && (found->tgt_flags & TG_TYPE_ARRAY) &&
	    !(found->tgt_flags & TG_TYPE_HASFAM)) {
		uintptr_t base, limit = node->tgn_limit;
		size_t size = mdb_ctf_type_size(found->tgt_type);

		for (base = node->tgn_base; base < limit; base += size) {
			fl->fl_addr = base;
			findlocks_findmutex(NULL, type, 0, fl);
		}
	} else {
		fl->fl_addr = node->tgn_base;
		findlocks_findmutex(NULL, type, 0, fl);
	}

	if (mdb_ctf_type_valid(type))
		return;

	for (tp = node->tgn_fraglist; tp != NULL; tp = tp->tgt_next) {
		kind = mdb_ctf_type_kind(ntype = tp->tgt_type);

		if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
			continue;

		fl->fl_addr = node->tgn_base + tp->tgt_redge->tge_destoffs;
		fl->fl_parent = ntype;
		findlocks_findmutex(NULL, ntype, 0, fl);
	}
}

/*ARGSUSED*/
int
findlocks(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	size_t i, j;
	findlocks_t fl;

	if (argc != 0)
		return (DCMD_USAGE);

	if (!typegraph_built())
		return (DCMD_ABORT);

	if (!(flags & DCMD_ADDRSPEC))
		addr = 0;

	bzero(&fl, sizeof (fl));
	fl.fl_thread = addr;

	for (i = 0; i < tg_nnodes; i++) {
		findlocks_node(&tg_node[i], &fl);
	}

	for (i = 0; i < fl.fl_ndx; i++) {
		foundlock_t *found = &fl.fl_locks[i];
		char buf[MDB_SYM_NAMLEN];

		if (found->fnd_member[0] != NULL) {
			mdb_printf("%p (%s",
			    found->fnd_addr,
			    mdb_ctf_type_name(found->fnd_parent, buf,
			    sizeof (buf)));

			for (j = 0; found->fnd_member[j] != NULL; j++)
				mdb_printf(".%s", found->fnd_member[j]);

			mdb_printf(") is owned by %p\n", found->fnd_owner);
		} else {
			if (found->fnd_node->tgn_incoming == NULL) {
				mdb_printf("%p (%a) is owned by %p\n",
				    found->fnd_addr, found->fnd_addr,
				    found->fnd_owner);
			} else {
				mdb_printf("%p is owned by %p\n",
				    found->fnd_addr, found->fnd_owner);
			}
		}
	}

	mdb_printf("findlocks: nota bene: %slocks may be held",
	    fl.fl_nlocks ? "other " : "");

	if (addr == 0) {
		mdb_printf("\n");
	} else {
		mdb_printf(" by %p\n", addr);
	}

	if (fl.fl_nlocks)
		mdb_free(fl.fl_locks, fl.fl_nlocks * sizeof (foundlock_t));

	return (DCMD_OK);
}

/*
 * ::findfalse:  Using type knowledge to detect potential false sharing
 *
 * In caching SMP systems, memory is kept coherent through bus-based snooping
 * protocols.  Under these protocols, only a single cache may have a given line
 * of memory in a dirty state.  If a different cache wishes to write to the
 * dirty line, the new cache must first read-to-own the dirty line from the
 * owning cache.  The size of the line used for coherence (the coherence
 * granularity) has an immediate ramification for parallel software:  because
 * only one cache may own a line at a given time, one wishes to avoid a
 * situation where two or more small, disjoint data structures are both
 * (a) contained within a single line and (b) accessed in parallel on disjoint
 * CPUs.  This situation -- so-called "false sharing" -- can induce suboptimal
 * scalability in otherwise scalable software.
 *
 * Historically, one has been able to find false sharing only with some
 * combination of keen intuition and good luck.  And where false sharing has
 * been discovered, it has almost always been after having induced suboptimal
 * scaling; one has historically not been able to detect false sharing before
 * the fact.
 *
 * Building on the mechanism for postmortem type information, however, we
 * can -- from a system crash dump -- detect the the potentially most egregious
 * cases of false sharing.  Specifically, after having run through the type
 * identification passes described above, we can iterate over all nodes,
 * looking for nodes that satisfy the following criteria:
 *
 *  (a)	The node is an array.  That is, the node was either determined to
 *	be of type CTF_K_ARRAY, or the node was inferred to be an array in
 *	pass2 of type identification (described above).
 *
 *  (b)	Each element of the array is a structure that is smaller than the
 *	coherence granularity.
 *
 *  (c)	The total size of the array is greater than the coherence granularity.
 *
 *  (d)	Each element of the array is a structure that contains within it a
 *	synchronization primitive (mutex, readers/writer lock, condition
 *	variable or semaphore).  We use the presence of a synchronization
 *	primitive as a crude indicator that the disjoint elements of the
 *	array are accessed in parallel.
 *
 * Any node satisfying these criteria is identified as an object that could
 * potentially suffer from false sharing, and the node's address, symbolic
 * name (if any), type, type size and total size are provided as output.
 *
 * While there are some instances of false sharing that do not meet the
 * above criteria (e.g., if the synchronization for each element is handled
 * in a separate structure, or if the elements are only manipulated with
 * atomic memory operations), these criteria yield many examples of false
 * sharing without swamping the user with false positives.
 */
#define	FINDFALSE_COHERENCE_SIZE	64

/*ARGSUSED*/
static int
findfalse_findsync(const char *name, mdb_ctf_id_t type, ulong_t offs,
    void *ignored)
{
	int i, kind;
	static int called = 0;
	static struct {
		char *name;
		mdb_ctf_id_t type;
	} sync[] = {
		{ "kmutex_t" },
		{ "krwlock_t" },
		{ "kcondvar_t" },
		{ "ksema_t" },
		{ NULL }
	};

	if (!called) {
		char *name;

		called = 1;

		for (i = 0; (name = sync[i].name) != NULL; i++) {
			if (mdb_ctf_lookup_by_name(name, &sync[i].type) == -1) {
				mdb_warn("can't find '%s' type", name);
				return (0);
			}

			sync[i].type = typegraph_resolve(sync[i].type);

			if (!mdb_ctf_type_valid(sync[i].type)) {
				mdb_warn("can't resolve '%s' type", name);
				return (0);
			}
		}
	}

	/*
	 * See if this type is any of the synchronization primitives.
	 */
	if (!mdb_ctf_type_valid(type))
		return (0);

	type = typegraph_resolve(type);

	for (i = 0; sync[i].name != NULL; i++) {
		if (mdb_ctf_type_cmp(type, sync[i].type) == 0) {
			/*
			 * We have a winner!
			 */
			return (1);
		}
	}

	if ((kind = mdb_ctf_type_kind(type)) == CTF_K_ARRAY) {
		mdb_ctf_arinfo_t arr;

		if (mdb_ctf_array_info(type, &arr) == -1)
			return (0);

		type = typegraph_resolve(arr.mta_contents);

		return (findfalse_findsync(name, type, 0, NULL));
	}

	if (kind != CTF_K_STRUCT)
		return (0);

	if (mdb_ctf_member_iter(type,
	    (mdb_ctf_member_f *)findfalse_findsync, NULL) != 0)
		return (1);

	return (0);
}

static void
findfalse_node(tg_node_t *node)
{
	mdb_ctf_id_t type = node->tgn_type;
	tg_type_t *tp, *found = NULL;
	ssize_t size;
	int kind;
	char buf[MDB_SYM_NAMLEN + 1];
	GElf_Sym sym;

	if (!mdb_ctf_type_valid(type)) {
		mdb_ctf_type_invalidate(&type);

		for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
			kind = mdb_ctf_type_kind(tp->tgt_type);

			if (kind == CTF_K_UNION) {
				/*
				 * Once again, the unions impede progress...
				 */
				return;
			}

			if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
				continue;

			if (found != NULL) {
				/*
				 * There are multiple interpretations for this
				 * node; we have to punt.
				 */
				return;
			}

			found = tp;
		}
	}

	if (found != NULL)
		type = found->tgt_type;

	if (!mdb_ctf_type_valid(type))
		return;

	kind = mdb_ctf_type_kind(type);

	/*
	 * If this isn't an array (or treated as one), it can't induce false
	 * sharing.  (Or at least, we can't detect it.)
	 */
	if (found != NULL) {
		if (!(found->tgt_flags & TG_TYPE_ARRAY))
			return;

		if (found->tgt_flags & TG_TYPE_HASFAM)
			return;
	} else {
		if (kind != CTF_K_ARRAY)
			return;
	}

	if (kind == CTF_K_ARRAY) {
		mdb_ctf_arinfo_t arr;

		if (mdb_ctf_array_info(type, &arr) == -1)
			return;

		type = typegraph_resolve(arr.mta_contents);

		if (!mdb_ctf_type_valid(type))
			return;

	}

	size = mdb_ctf_type_size(type);

	/*
	 * If the size is greater than or equal to the cache line size, it's
	 * not false sharing.  (Or at least, the false sharing is benign.)
	 */
	if (size >= FINDFALSE_COHERENCE_SIZE)
		return;

	if (TG_NODE_SIZE(node) <= FINDFALSE_COHERENCE_SIZE)
		return;

	/*
	 * This looks like it could be a falsely shared structure.  If this
	 * type contains a mutex, rwlock, semaphore or condition variable,
	 * we're going to report it.
	 */
	if (!findfalse_findsync(NULL, type, 0, NULL))
		return;

	mdb_printf("%?p ", node->tgn_base);

	if (mdb_lookup_by_addr(node->tgn_base, MDB_SYM_EXACT, buf,
	    sizeof (buf), &sym) != -1) {
		mdb_printf("%-28s ", buf);
	} else {
		mdb_printf("%-28s ", "-");
	}

	mdb_printf("%-22s %2d %7ld\n",
	    mdb_ctf_type_name(type, buf, sizeof (buf)), size,
	    TG_NODE_SIZE(node));
}

/*ARGSUSED*/
int
findfalse(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
{
	ssize_t i;

	if (argc != 0 || (flags & DCMD_ADDRSPEC))
		return (DCMD_USAGE);

	if (!typegraph_built())
		return (DCMD_ABORT);

	mdb_printf("%?s %-28s %-22s %2s %7s\n", "ADDR", "SYMBOL", "TYPE",
	    "SZ", "TOTSIZE");

	/*
	 * We go from the back of the bus and move forward to report false
	 * sharing in named symbols before reporting false sharing in dynamic
	 * structures.
	 */
	for (i = tg_nnodes - 1; i >= 0; i--)
		findfalse_node(&tg_node[i]);

	return (DCMD_OK);
}