text: /*
   * 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);
  }
  