1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*
27  * Postmortem type identification
28  * ------------------------------
29  *
30  * When debugging kernel memory corruption problems, one often determines that
31  * the corrupted buffer has been erroneously written to by a user of an
32  * adjacent buffer -- determining the specifics of the adjacent buffer can
33  * therefore offer insight into the cause of the corruption.  To determine the
34  * type of an arbitrary memory buffer, however, one has historically been
35  * forced to use dcmds ::kgrep and ::whatis in alternating succession; when an
36  * object of known type is finally reached, types can be back-propagated to
37  * determine the type of the unknown object.
38  *
39  * This process is labor-intensive and error-prone.  Using CTF data and a
40  * collection of heuristics, we would like to both automate this process and
41  * improve on it.
42  *
43  * We start by constructing the pointer graph.  Each node in the graph is
44  * a memory object (either a static object from module data, or a dynamically
45  * allocated memory object); the node's outgoing edges represent pointers from
46  * the object to other memory objects in the system.
47  *
48  * Once the graph is constructed, we start at nodes of known type, and use the
49  * type information to determine the type of each pointer represented by an
50  * outgoing edge.  Determining the pointer type allows us to determine the
51  * type of the edge's destination node, and therefore to iteratively continue
52  * the process of type identification.  This process works as long as all
53  * pointed-to objects are exactly the size of their inferred types.
54  *
55  * Unfortunately, pointed-to objects are often _not_ the size of the pointed-to
56  * type.  This is largely due to three phenomena:
57  *
58  * (a)	C makes no distinction between a pointer to a single object and a
59  *	pointer to some number of objects of like type.
60  *
61  * (b)	C performs no bounds checking on array indexing, allowing declarations
62  *	of structures that are implicitly followed by arrays of the type of the
63  *	structure's last member.  These declarations most often look like:
64  *
65  *	    typedef struct foo {
66  *	            int       foo_bar;
67  *	            int       foo_baz;
68  *	            mumble_t  foo_mumble[1];
69  *	    } foo_t;
70  *
71  *	When a foo_t is allocated, the size of n - 1 mumble_t's is added to the
72  *	size of a foo_t to derive the size of the allocation; this allows for
73  *	the n trailing mumble_t's to be referenced from the allocated foo_t
74  *	using C's convenient array syntax -- without requiring an additional
75  *	memory dereference.  ISO C99 calls the last member in such a structure
76  *	the "flexible array member" (FAM); we adhere to this terminology.
77  *
78  * (c)	It is not uncommon for structures to embed smaller structures, and
79  *	to pass pointers to these smaller structures to routines that track
80  *	the structures only by the smaller type.  This can be thought of as
81  *	a sort of crude-but-efficient polymorphism; see e.g., struct seg and
82  *	its embedded avl_node_t.  It is less common (but by no means unheard
83  *	of) for the smaller structures to be used as place holders in data
84  *	structures consisting of the larger structure.  That is, instead of an
85  *	instance of the larger structure being pointed to by the smaller
86  *	structure pointer, an instance of the smaller structure is pointed to
87  *	the larger structure pointer; see e.g., struct buf and struct hbuf or
88  *	struct seg_pcache and struct seg_phash.  This construct is particularly
89  *	important to identify when the smaller structures are in a contiguous
90  *	array (as they are in each of the two examples provided):  by examining
91  *	only the data structure of larger structures, one would erroneously
92  *	assume that the array of the smaller structure is actually an array of
93  *	the larger structure.
94  *
95  * Taken together, these three phenomena imply that if we have a pointer to
96  * an object that is larger than the pointed-to type, we don't know if the
97  * object is an array of objects of the pointed-to type, the pointed-to type
98  * followed by an array of that type's last member, or some other larger type
99  * that we haven't yet discovered.
100  *
101  * Differentiating these three situations is the focus of many of the
102  * type graph heuristics.  Type graph processing is performed in an initial
103  * pass, four type-determining passes, and a final, post-pass:
104  *
105  * Initial: Graph construction
106  *
107  * The initial pass constructs the nodes from the kmem caches and module data,
108  * and constructs the edges by propagating out from module data.  Nodes that
109  * are in module data or known kmem caches (see tg_cachetab[], below) are
110  * marked with their known type.  This pass takes the longest amount of
111  * wall-clock time, for it frequently induces I/O to read the postmortem image
112  * into memory from permanent storage.
113  *
114  * pass1: Conservative propagation
115  *
116  * In pass1, we propagate types out from the known nodes, adding types to
117  * nodes' tgn_typelists as they are inferred.  Nodes are marked as they are
118  * processed to guarantee halting.  We proceed as conservatively as possible
119  * in this pass; if we discover that a node is larger than twice its inferred
120  * type (that is, we've run into one of the three phenomena described above),
121  * we add the inferred type to the node's tgn_typelist, but we don't descend.
122  *
123  * pass2: Array determination
124  *
125  * In pass2, we visit those nodes through which we refused to descend in pass1.
126  * If we find one (and only one) structural interpretation for the object, we
127  * have determined that -- to the best of our knowledge -- we are not seeing
128  * phenomenon (c).  To further differentiate (a) from (b), we check if the
129  * structure ends with an array of size one; if it does, we assume that it has
130  * a flexible array member.  Otherwise, we perform an additional check:  we
131  * calculate the size of the object modulo the size of the inferred type and
132  * subtract it from the size of the object.  If this value is less than or
133  * equal to the size of the next-smaller kmem cache, we know that it's not an
134  * array of the inferred type -- if it were an array of the inferred type, it
135  * would have been instead allocated out of the next-smaller cache.
136  *
137  * In either case (FAM or no FAM), we iterate through each element of the
138  * hypothesised array, checking that each pointer member points to either NULL
139  * or valid memory.  If pointer members do not satisfy these criteria, it is
140  * assumed that we have not satisfactorily determined that the given object is
141  * an array of the inferred type, and we abort processing of the node.  Note
142  * that uninitialized pointers can potentially prevent an otherwise valid
143  * array from being interpreted as such.  Because array misinterpretation
144  * can induce substantial cascading type misinterpretation, it is preferred to
145  * be conservative and accurate in such cases -- even if it means a lower type
146  * recognition rate.
147  *
148  * pass3: Type coalescence
149  *
150  * pass3 coalesces type possibilities by preferring structural possibilities
151  * over non-structural ones.  For example, if an object is either of type
152  * "char" (pointed to by a caddr_t) or type "struct frotz", the possibilities
153  * will be coalesced into just "struct frotz."
154  *
155  * pass4: Non-array type inference
156  *
157  * pass4 is the least conservative:  it is assumed that phenomenon (c) has been
158  * completely ferreted out by prior passes.  All unknown types are visited, and
159  * incoming edges are checked.  If there is only one possible structural
160  * inference for the unknown type, the node is inferred to be of that type, and
161  * the type is propagated.  This pass picks up those nodes that are larger than
162  * their inferred type, but for which the inferred type is likely accurate.
163  * (struct dcentry, with its FAM of characters, is an example type that is
164  * frequently determined by this pass.)
165  *
166  * Post-pass: Greatest unknown reach
167  *
168  * If recognition rate is low (or, from a more practical perspective, if the
169  * object of interest is not automatically identified), it can be useful
170  * to know which node is the greatest impediment to further recognition.
171  * If the user can -- by hook or by crook -- determine the true type of this
172  * node (and set it with ::istype), much more type identification should be
173  * possible.  To facilitate this, we therefore define the _reach_ of a node to
174  * be the number of unknown nodes that could potentially be identified were the
175  * node's type better known.  We determine the reach by performing a
176  * depth-first pass through the graph.  The node of greatest reach (along with
177  * the reach itself) are reported upon completion of the post-pass.
178  */
179 
180 #include <mdb/mdb_param.h>
181 #include <mdb/mdb_modapi.h>
182 #include <mdb/mdb_ctf.h>
183 #include <sys/sysmacros.h>
184 #include <sys/kmem_impl.h>
185 #include <sys/vmem_impl.h>
186 #include <sys/modctl.h>
187 #include <sys/kobj.h>
188 #include <stdio.h>
189 #include "kmem.h"
190 
191 struct tg_node;
192 
193 typedef struct tg_edge {
194 	struct tg_node	*tge_src;	/* source node */
195 	struct tg_node	*tge_dest;	/* destination node */
196 	uintptr_t	tge_srcoffs;	/* offset in source node */
197 	uintptr_t	tge_destoffs;	/* offset in destination node */
198 	struct tg_edge	*tge_nextin;	/* next incoming edge */
199 	struct tg_edge	*tge_nextout;	/* next outgoing edge */
200 	int		tge_marked;	/* mark */
201 } tg_edge_t;
202 
203 typedef struct tg_type {
204 	mdb_ctf_id_t	tgt_type;	/* CTF type */
205 	mdb_ctf_id_t	tgt_utype;	/* unresolved CTF type */
206 	mdb_ctf_id_t	tgt_rtype;	/* referring type */
207 	size_t		tgt_roffs;	/* referring offset */
208 	const char	*tgt_rmember;	/* referring member */
209 	tg_edge_t	*tgt_redge;	/* referring edge */
210 	struct tg_type	*tgt_next;	/* next type */
211 	int		tgt_flags;	/* flags */
212 } tg_type_t;
213 
214 #define	TG_TYPE_ARRAY		0x0001
215 #define	TG_TYPE_NOTARRAY	0x0002
216 #define	TG_TYPE_HASFAM		0x0004
217 
218 typedef struct tg_node {
219 	uintptr_t	tgn_base;	/* address base of object */
220 	uintptr_t	tgn_limit;	/* address limit of object */
221 	tg_edge_t	*tgn_incoming;	/* incoming edges */
222 	tg_edge_t	*tgn_outgoing;	/* outgoing edges */
223 	tg_type_t	*tgn_typelist;	/* conjectured typelist */
224 	tg_type_t	*tgn_fraglist;	/* type fragment list */
225 	char		tgn_marked;	/* marked */
226 	char		tgn_postmarked;	/* marked in postpass */
227 	int		tgn_smaller;	/* size of next-smaller cache */
228 	int		tgn_reach;	/* number of reachable unknown nodes */
229 	mdb_ctf_id_t	tgn_type;	/* known type */
230 } tg_node_t;
231 
232 #define	TG_NODE_SIZE(n)		((n)->tgn_limit - (n)->tgn_base)
233 
234 typedef struct tg_stats {
235 	size_t	tgs_buffers;
236 	size_t	tgs_nodes;
237 	size_t	tgs_unmarked;
238 	size_t	tgs_known;
239 	size_t	tgs_typed;
240 	size_t	tgs_conflicts;
241 	size_t	tgs_frag;
242 	size_t	tgs_candidates;
243 } tg_stats_t;
244 
245 typedef struct tg_typeoffs {
246 	mdb_ctf_id_t		tgto_type;	/* found type */
247 	ulong_t			tgto_offs;	/* offset of interest */
248 	const char		**tgto_memberp;	/* referring member name */
249 	tg_edge_t		*tgto_edge;	/* outbound edge */
250 } tg_typeoffs_t;
251 
252 typedef struct tg_buildstate {
253 	uintptr_t		tgbs_addr;	/* address of region */
254 	uintptr_t		*tgbs_buf;	/* in-core copy of region */
255 	size_t			tgbs_ndx;	/* current pointer index */
256 	size_t			tgbs_nptrs;	/* number of pointers */
257 	tg_node_t		*tgbs_src;	/* corresponding node */
258 	struct tg_buildstate	*tgbs_next;	/* next stacked or free */
259 } tg_buildstate_t;
260 
261 typedef struct tg_poststate {
262 	tg_node_t		*tgps_node;	/* current node */
263 	tg_edge_t		*tgps_edge;	/* current edge */
264 	size_t			tgps_total;	/* current total */
265 	struct tg_poststate	*tgps_next;	/* next stacked or free */
266 } tg_poststate_t;
267 
268 typedef struct tg_todo {
269 	tg_node_t		*tgtd_node;	/* node to process */
270 	uintptr_t		tgtd_offs;	/* offset within node */
271 	mdb_ctf_id_t		tgtd_type;	/* conjectured type */
272 	struct tg_todo		*tgtd_next;	/* next todo */
273 } tg_todo_t;
274 
275 typedef struct tg_nodedata {
276 	tg_node_t		*tgd_next;	/* next node to fill in */
277 	size_t			tgd_size;	/* size of this node */
278 } tg_nodedata_t;
279 
280 /*
281  * Some caches can be pretty arduous to identify (or are rife with conflicts).
282  * To assist type identification, specific caches are identified with the
283  * types of their contents.  Each cache need _not_ be listed here; in general,
284  * a cache should only be added to the tg_cachetab[] if the identification rate
285  * for the cache is less than 95%Every .  (The identification rate for a
286  * specific cache can be quickly determined by specifying the cache to
287  * ::typegraph.)
288  */
289 struct {
290 	char *tgc_name;
291 	char *tgc_type;
292 } tg_cachetab[] = {
293 	{ "streams_mblk",	"mblk_t" },
294 	{ "seg_cache",		"struct seg" },
295 	{ "segvn_cache",	"struct segvn_data" },
296 	{ "anon_cache",		"struct anon" },
297 	{ "ufs_inode_cache",	"inode_t" },
298 	{ "hme_cache",		"struct hment" },
299 	{ "queue_cache",	"queinfo_t" },
300 	{ "sock_cache",		"struct sonode" },
301 	{ "ire_cache",		"ire_t" },
302 	{ NULL,			NULL }
303 };
304 
305 /*
306  * Some types are only known by their opaque handles.  While this is a good way
307  * to keep interface clients from eating the Forbidden Fruit, it can make type
308  * identification difficult -- which can be especially important for big
309  * structures like dev_info_t.  To assist type identification, we keep a table
310  * to translate from opaque handles to their underlying structures.  A
311  * translation should only be added to the tg_typetab[] if the lack of
312  * translation is preventing substantial type identification.  (This can be
313  * determined by using the "typeunknown" walker on a dump with bufctl auditing
314  * enabled, and using "::whatis -b" to determine the types of unknown buffers;
315  * if many of these unknown types are structures behind an opaque handle, a
316  * new entry in tg_typetab[] is likely warranted.)
317  */
318 struct {
319 	char		*tgt_type_name;		/* filled in statically */
320 	char		*tgt_actual_name;	/* filled in statically */
321 	mdb_ctf_id_t	tgt_type;		/* determined dynamically */
322 	mdb_ctf_id_t	tgt_actual_type;	/* determined dynamically */
323 } tg_typetab[] = {
324 	{ "dev_info_t",		"struct dev_info" },
325 	{ "ddi_dma_handle_t",	"ddi_dma_impl_t *" },
326 	{ NULL,			NULL }
327 };
328 
329 static enum {
330 	TG_PASS1 = 1,
331 	TG_PASS2,
332 	TG_PASS3,
333 	TG_PASS4
334 } tg_pass;
335 
336 static size_t tg_nnodes;	/* number of nodes */
337 static size_t tg_nanchored;	/* number of anchored nodes */
338 static tg_node_t *tg_node;	/* array of nodes */
339 static tg_node_t **tg_sorted;	/* sorted array of pointers into tg_node */
340 static size_t tg_nsorted;	/* number of pointers in tg_sorted */
341 static int *tg_sizes;		/* copy of kmem_alloc_sizes[] array */
342 static int tg_nsizes;		/* number of sizes in tg_sizes */
343 static hrtime_t tg_start;	/* start time */
344 static int tg_improved;		/* flag indicating that we have improved */
345 static int tg_built;		/* flag indicating that type graph is built */
346 static uint_t tg_verbose;	/* flag to increase verbosity */
347 
348 static mdb_ctf_id_t typegraph_type_offset(mdb_ctf_id_t, size_t,
349     tg_edge_t *, const char **);
350 
351 static void
352 typegraph_typetab_init(void)
353 {
354 	int i;
355 
356 	for (i = 0; tg_typetab[i].tgt_type_name != NULL; i++) {
357 		if (mdb_ctf_lookup_by_name(tg_typetab[i].tgt_type_name,
358 		    &tg_typetab[i].tgt_type) == -1) {
359 			mdb_warn("can't find type '%s'\n",
360 			    tg_typetab[i].tgt_type_name);
361 			mdb_ctf_type_invalidate(&tg_typetab[i].tgt_type);
362 			continue;
363 		}
364 
365 		if (mdb_ctf_lookup_by_name(tg_typetab[i].tgt_actual_name,
366 		    &tg_typetab[i].tgt_actual_type) == -1) {
367 			mdb_warn("can't find type '%s'\n",
368 			    tg_typetab[i].tgt_actual_name);
369 			mdb_ctf_type_invalidate(&tg_typetab[i].tgt_actual_type);
370 		}
371 	}
372 }
373 
374 /*
375  * A wrapper around mdb_ctf_type_resolve() that first checks the type
376  * translation table.
377  */
378 static mdb_ctf_id_t
379 typegraph_resolve(mdb_ctf_id_t type)
380 {
381 	int i;
382 	mdb_ctf_id_t ret;
383 
384 	/*
385 	 * This could be _much_ more efficient...
386 	 */
387 	for (i = 0; tg_typetab[i].tgt_type_name != NULL; i++) {
388 		if (mdb_ctf_type_cmp(type, tg_typetab[i].tgt_type) == 0) {
389 			type = tg_typetab[i].tgt_actual_type;
390 			break;
391 		}
392 	}
393 
394 	(void) mdb_ctf_type_resolve(type, &ret);
395 	return (ret);
396 }
397 
398 /*
399  * A wrapper around mdb_ctf_type_name() that deals with anonymous structures.
400  * Anonymous structures are those that have no name associated with them.
401  * Nearly always, these structures are referred to by a typedef (e.g.
402  * "typedef struct { int bar } foo_t"); we expect the unresolved type to
403  * be passed as utype.
404  */
405 static char *
406 typegraph_type_name(mdb_ctf_id_t type, mdb_ctf_id_t utype)
407 {
408 	static char buf[MDB_SYM_NAMLEN];
409 
410 	if (mdb_ctf_type_name(type, buf, sizeof (buf)) == NULL) {
411 		(void) strcpy(buf, "<unknown>");
412 	} else {
413 		/*
414 		 * Perhaps a CTF interface would be preferable to this kludgey
415 		 * strcmp()?  Perhaps.
416 		 */
417 		if (strcmp(buf, "struct ") == 0)
418 			(void) mdb_ctf_type_name(utype, buf, sizeof (buf));
419 	}
420 
421 	return (buf);
422 }
423 
424 /*
425  * A wrapper around mdb_ctf_type_size() that accurately accounts for arrays.
426  */
427 static ssize_t
428 typegraph_size(mdb_ctf_id_t type)
429 {
430 	mdb_ctf_arinfo_t arr;
431 	ssize_t size;
432 
433 	if (!mdb_ctf_type_valid(type))
434 		return (-1);
435 
436 	if (mdb_ctf_type_kind(type) != CTF_K_ARRAY)
437 		return (mdb_ctf_type_size(type));
438 
439 	if (mdb_ctf_array_info(type, &arr) == -1)
440 		return (-1);
441 
442 	type = typegraph_resolve(arr.mta_contents);
443 
444 	if (!mdb_ctf_type_valid(type))
445 		return (-1);
446 
447 	if ((size = mdb_ctf_type_size(type)) == -1)
448 		return (-1);
449 
450 	return (size * arr.mta_nelems);
451 }
452 
453 /*
454  * The mdb_ctf_member_iter() callback for typegraph_type_offset().
455  */
456 static int
457 typegraph_offiter(const char *name, mdb_ctf_id_t type,
458     ulong_t off, tg_typeoffs_t *toffs)
459 {
460 	int kind;
461 	ssize_t size;
462 	mdb_ctf_arinfo_t arr;
463 
464 	off /= NBBY;
465 
466 	if (off > toffs->tgto_offs) {
467 		/*
468 		 * We went past it; return failure.
469 		 */
470 		return (1);
471 	}
472 
473 	if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
474 		return (0);
475 
476 	if ((size = mdb_ctf_type_size(type)) == -1)
477 		return (0);
478 
479 	if (off < toffs->tgto_offs &&
480 	    size != 0 && off + size <= toffs->tgto_offs) {
481 		/*
482 		 * Haven't reached it yet; continue looking.
483 		 */
484 		return (0);
485 	}
486 
487 	/*
488 	 * If the base type is not a structure, an array or a union, and
489 	 * the offset equals the desired offset, we have our type.
490 	 */
491 	if ((kind = mdb_ctf_type_kind(type)) != CTF_K_STRUCT &&
492 	    kind != CTF_K_UNION && kind != CTF_K_ARRAY) {
493 		if (off == toffs->tgto_offs)
494 			toffs->tgto_type = type;
495 
496 		if (toffs->tgto_memberp != NULL)
497 			*(toffs->tgto_memberp) = name;
498 
499 		return (1);
500 	}
501 
502 	/*
503 	 * If the type is an array, see if we fall within the bounds.
504 	 */
505 	if (kind == CTF_K_ARRAY) {
506 		if (mdb_ctf_array_info(type, &arr) == -1)
507 			return (0);
508 
509 		type = typegraph_resolve(arr.mta_contents);
510 
511 		if (!mdb_ctf_type_valid(type))
512 			return (0);
513 
514 		size = mdb_ctf_type_size(type) * arr.mta_nelems;
515 
516 		if (off < toffs->tgto_offs && off + size <= toffs->tgto_offs) {
517 			/*
518 			 * Nope, haven't found it yet; continue looking.
519 			 */
520 			return (0);
521 		}
522 	}
523 
524 	toffs->tgto_type = typegraph_type_offset(type,
525 	    toffs->tgto_offs - off, toffs->tgto_edge, toffs->tgto_memberp);
526 
527 	return (1);
528 }
529 
530 /*
531  * The mdb_ctf_member_iter() callback for typegraph_type_offset() when the type
532  * is found to be of kind CTF_K_UNION.  With unions, we attempt to do better
533  * than just completely punting:  if all but one of the members is impossible
534  * (due to, say, size constraints on the destination node), we can propagate
535  * the valid member.
536  */
537 static int
538 typegraph_union(const char *name, mdb_ctf_id_t type, ulong_t off,
539     tg_typeoffs_t *toffs)
540 {
541 	const char *member = name;
542 	tg_edge_t *e = toffs->tgto_edge;
543 	mdb_ctf_id_t rtype;
544 	size_t rsize;
545 	int kind;
546 
547 	if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
548 		return (0);
549 
550 	kind = mdb_ctf_type_kind(type);
551 
552 	if (kind == CTF_K_STRUCT || kind != CTF_K_UNION ||
553 	    kind != CTF_K_ARRAY) {
554 		type = typegraph_type_offset(type,
555 		    toffs->tgto_offs - off, e, &member);
556 	}
557 
558 	if (!mdb_ctf_type_valid(type))
559 		return (0);
560 
561 	if (mdb_ctf_type_kind(type) != CTF_K_POINTER)
562 		return (0);
563 
564 	/*
565 	 * Now figure out what exactly we're pointing to.
566 	 */
567 	if (mdb_ctf_type_reference(type, &rtype) == -1)
568 		return (0);
569 
570 	if (!mdb_ctf_type_valid(rtype = typegraph_resolve(rtype)))
571 		return (0);
572 
573 	rsize = mdb_ctf_type_size(rtype);
574 
575 	/*
576 	 * Compare this size to the size of the thing we're pointing to --
577 	 * if it's larger than the node that we're pointing to, we know that
578 	 * the alleged pointer type must be an invalid interpretation of the
579 	 * union.
580 	 */
581 	if (rsize > TG_NODE_SIZE(e->tge_dest) - e->tge_destoffs) {
582 		/*
583 		 * We're in luck -- it's not possibly this pointer.
584 		 */
585 		return (0);
586 	}
587 
588 	/*
589 	 * This looks like it could be legit.  If the type hasn't been
590 	 * specified, we could be in business.
591 	 */
592 	if (mdb_ctf_type_valid(toffs->tgto_type)) {
593 		/*
594 		 * There are two potentially valid interpretations for this
595 		 * union.  Invalidate the type.
596 		 */
597 		mdb_ctf_type_invalidate(&toffs->tgto_type);
598 		return (1);
599 	}
600 
601 	toffs->tgto_type = type;
602 
603 	if (toffs->tgto_memberp != NULL)
604 		*(toffs->tgto_memberp) = member;
605 
606 	return (0);
607 }
608 
609 /*ARGSUSED*/
610 static int
611 typegraph_lastmember(const char *name,
612     mdb_ctf_id_t type, ulong_t off, void *last)
613 {
614 	*((mdb_ctf_id_t *)last) = type;
615 
616 	return (0);
617 }
618 
619 /*
620  * To determine if a structure is has a flexible array member, we iterate over
621  * the members; if the structure has more than one member, and the last member
622  * is an array of size 1, we're going to assume that this structure has a
623  * flexible array member.  Yes, this heuristic is a little sloppy -- but cut me
624  * some slack:  why the hell else would you have an array of size 1?  (Don't
625  * answer that.)
626  */
627 static int
628 typegraph_hasfam(mdb_ctf_id_t type, mdb_ctf_id_t *atype)
629 {
630 	mdb_ctf_arinfo_t arr;
631 	mdb_ctf_id_t last;
632 	int kind;
633 
634 	if (!mdb_ctf_type_valid(type))
635 		return (0);
636 
637 	if ((kind = mdb_ctf_type_kind(type)) != CTF_K_STRUCT)
638 		return (0);
639 
640 	mdb_ctf_type_invalidate(&last);
641 	mdb_ctf_member_iter(type, typegraph_lastmember, &last);
642 
643 	if (!mdb_ctf_type_valid(last))
644 		return (0);
645 
646 	if ((kind = mdb_ctf_type_kind(last)) == CTF_K_STRUCT)
647 		return (typegraph_hasfam(last, atype));
648 
649 	if (kind != CTF_K_ARRAY)
650 		return (0);
651 
652 	if (typegraph_size(last) == typegraph_size(type)) {
653 		/*
654 		 * This structure has only one member; even if that member is
655 		 * an array of size 1, we'll assume that there is something
656 		 * stranger going on than a run-of-the-mill FAM (e.g., a
657 		 * kmutex_t).
658 		 */
659 		return (0);
660 	}
661 
662 	if (mdb_ctf_array_info(last, &arr) == -1)
663 		return (0);
664 
665 	if (arr.mta_nelems != 1)
666 		return (0);
667 
668 	if (atype != NULL)
669 		*atype = typegraph_resolve(arr.mta_contents);
670 
671 	return (1);
672 }
673 
674 /*
675  * This routine takes a type and offset, and returns the type at the specified
676  * offset.  It additionally takes an optional edge to help bust unions, and
677  * an optional address of a character pointer to set to the name of the member
678  * found at the specified offset.
679  */
680 static mdb_ctf_id_t
681 typegraph_type_offset(mdb_ctf_id_t type, size_t offset, tg_edge_t *e,
682     const char **member)
683 {
684 	mdb_ctf_arinfo_t arr;
685 	uint_t kind;
686 	mdb_ctf_id_t last;
687 	ssize_t size;
688 	ssize_t lsize;
689 	tg_typeoffs_t toffs;
690 	mdb_ctf_id_t inval;
691 
692 	mdb_ctf_type_invalidate(&inval);
693 
694 	if (member != NULL)
695 		*member = NULL;
696 
697 	/*
698 	 * Resolve type to its base type.
699 	 */
700 	type = typegraph_resolve(type);
701 	kind = mdb_ctf_type_kind(type);
702 
703 	switch (kind) {
704 	case CTF_K_ARRAY:
705 		/*
706 		 * If this is an array, we need to figure out what it's an
707 		 * array _of_.  We must then figure out the size of the array
708 		 * structure, and then determine our offset within that type.
709 		 * From there, we can recurse.
710 		 */
711 		if (mdb_ctf_array_info(type, &arr) == -1)
712 			return (inval);
713 
714 		type = typegraph_resolve(arr.mta_contents);
715 
716 		if (!mdb_ctf_type_valid(type))
717 			return (inval);
718 
719 		/*
720 		 * If the type is not a structure/union, then check that the
721 		 * offset doesn't point to the middle of the base type and
722 		 * return it.
723 		 */
724 		kind = mdb_ctf_type_kind(type);
725 		size = mdb_ctf_type_size(type);
726 
727 		if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) {
728 			if (offset % size) {
729 				/*
730 				 * The offset is pointing to the middle of a
731 				 * type; return failure.
732 				 */
733 				return (inval);
734 			}
735 
736 			return (type);
737 		}
738 
739 		return (typegraph_type_offset(type, offset % size, e, member));
740 
741 	case CTF_K_STRUCT:
742 		/*
743 		 * If the offset is larger than the size, we need to figure
744 		 * out what exactly we're looking at.  There are several
745 		 * possibilities:
746 		 *
747 		 * (a)	A structure that has this type as its first member.
748 		 *
749 		 * (b)	An array of structures of this type.
750 		 *
751 		 * (c)	A structure has a flexible array member.
752 		 *
753 		 * The differentiation between (a) and (b) has hopefully
754 		 * happened before entering this function.  To differentiate
755 		 * between (b) and (c), we call typegraph_hasfam().
756 		 */
757 		size = mdb_ctf_type_size(type);
758 
759 		if (offset >= size) {
760 			if (typegraph_hasfam(type, &last)) {
761 				/*
762 				 * We have a live one.  Take the size, subtract
763 				 * the size of the last element, and recurse.
764 				 */
765 				if (!mdb_ctf_type_valid(last))
766 					return (inval);
767 
768 				lsize = mdb_ctf_type_size(last);
769 
770 				return (typegraph_type_offset(last,
771 				    offset - size - lsize, e, member));
772 			}
773 
774 			offset %= size;
775 		}
776 
777 		toffs.tgto_offs = offset;
778 		toffs.tgto_memberp = member;
779 		toffs.tgto_edge = e;
780 		mdb_ctf_type_invalidate(&toffs.tgto_type);
781 
782 		mdb_ctf_member_iter(type,
783 		    (mdb_ctf_member_f *)typegraph_offiter, &toffs);
784 
785 		return (toffs.tgto_type);
786 
787 	case CTF_K_POINTER:
788 		if (!mdb_ctf_type_valid(type = typegraph_resolve(type)))
789 			return (inval);
790 
791 		size = mdb_ctf_type_size(type);
792 
793 		if (offset % size) {
794 			/*
795 			 * The offset is pointing to the middle of a type;
796 			 * return failure.
797 			 */
798 			return (inval);
799 		}
800 
801 		return (type);
802 
803 	case CTF_K_UNION:
804 		if (e == NULL) {
805 			/*
806 			 * We've been given no outbound edge -- we have no way
807 			 * of figuring out what the hell this union is.
808 			 */
809 			return (inval);
810 		}
811 
812 		toffs.tgto_offs = offset;
813 		toffs.tgto_memberp = member;
814 		toffs.tgto_edge = e;
815 		mdb_ctf_type_invalidate(&toffs.tgto_type);
816 
817 		/*
818 		 * Try to bust the union...
819 		 */
820 		if (mdb_ctf_member_iter(type,
821 		    (mdb_ctf_member_f *)typegraph_union, &toffs) != 0) {
822 			/*
823 			 * There was at least one valid pointer in there.
824 			 * Return "void *".
825 			 */
826 			(void) mdb_ctf_lookup_by_name("void *", &type);
827 
828 			return (type);
829 		}
830 
831 		return (toffs.tgto_type);
832 
833 	default:
834 		/*
835 		 * If the offset is anything other than zero, no dice.
836 		 */
837 		if (offset != 0)
838 			return (inval);
839 
840 		return (type);
841 	}
842 }
843 
844 /*
845  * This routine takes an address and a type, and determines if the memory
846  * pointed to by the specified address could be of the specified type.
847  * This could become significantly more sophisticated, but for now it's pretty
848  * simple:  this is _not_ of the specified type if it's a pointer, and either:
849  *
850  *  (a)	The alignment is not correct given the type that is pointed to.
851  *
852  *  (b)	The memory pointed to is invalid.  Note that structures that have
853  *	uninitialized pointers may cause us to erroneously fail -- but these
854  *	structures are a bug anyway (uninitialized pointers can confuse many
855  *	analysis tools, including ::findleaks).
856  */
857 static int
858 typegraph_couldbe(uintptr_t addr, mdb_ctf_id_t type)
859 {
860 	int rkind;
861 	mdb_ctf_id_t rtype;
862 	uintptr_t val, throwaway;
863 	size_t rsize;
864 	char buf[MDB_SYM_NAMLEN];
865 
866 	if (mdb_ctf_type_kind(type) != CTF_K_POINTER)
867 		return (1);
868 
869 	if (mdb_ctf_type_reference(type, &rtype) == -1)
870 		return (1);
871 
872 	if (!mdb_ctf_type_valid(rtype = typegraph_resolve(rtype)))
873 		return (1);
874 
875 	if (mdb_vread(&val, sizeof (val), addr) == -1) {
876 		/*
877 		 * This is definitely unexpected.  We should not be getting
878 		 * back an error on a node that was successfully read in.
879 		 * Lacking something better to do, we'll print an error
880 		 * and return.
881 		 */
882 		mdb_warn("failed to evaluate pointer type at address %p", addr);
883 		return (1);
884 	}
885 
886 	rkind = mdb_ctf_type_kind(rtype);
887 
888 	if (rkind == CTF_K_STRUCT || rkind == CTF_K_UNION) {
889 		/*
890 		 * If it's a pointer to a structure or union, it must be
891 		 * aligned to sizeof (uintptr_t).
892 		 */
893 		if (val & (sizeof (uintptr_t) - 1)) {
894 			if (tg_verbose) {
895 				mdb_printf("typegraph: pass %d: rejecting "
896 				    "*%p (%p) as %s: misaligned pointer\n",
897 				    tg_pass, addr, val,
898 				    mdb_ctf_type_name(type, buf, sizeof (buf)));
899 			}
900 
901 			return (0);
902 		}
903 	}
904 
905 	rsize = mdb_ctf_type_size(rtype);
906 
907 	if (val == 0 || rsize == 0)
908 		return (1);
909 
910 	/*
911 	 * For our speculative read, we're going to clamp the referenced size
912 	 * at the size of a pointer.
913 	 */
914 	if (rsize > sizeof (uintptr_t))
915 		rsize = sizeof (uintptr_t);
916 
917 	if (mdb_vread(&throwaway, rsize, val) == -1) {
918 		if (tg_verbose) {
919 			mdb_printf("typegraph: pass %d: rejecting *%p (%p) as"
920 			    " %s: bad pointer\n", tg_pass, addr, val,
921 			    mdb_ctf_type_name(type, buf, sizeof (buf)));
922 		}
923 		return (0);
924 	}
925 
926 	return (1);
927 }
928 
929 static int
930 typegraph_nodecmp(const void *l, const void *r)
931 {
932 	tg_node_t *lhs = *(tg_node_t **)l;
933 	tg_node_t *rhs = *(tg_node_t **)r;
934 
935 	if (lhs->tgn_base < rhs->tgn_base)
936 		return (-1);
937 	if (lhs->tgn_base > rhs->tgn_base)
938 		return (1);
939 
940 	return (0);
941 }
942 
943 static tg_node_t *
944 typegraph_search(uintptr_t addr)
945 {
946 	ssize_t left = 0, right = tg_nnodes - 1, guess;
947 
948 	while (right >= left) {
949 		guess = (right + left) >> 1;
950 
951 		if (addr < tg_sorted[guess]->tgn_base) {
952 			right = guess - 1;
953 			continue;
954 		}
955 
956 		if (addr >= tg_sorted[guess]->tgn_limit) {
957 			left = guess + 1;
958 			continue;
959 		}
960 
961 		return (tg_sorted[guess]);
962 	}
963 
964 	return (NULL);
965 }
966 
967 static int
968 typegraph_interested(const kmem_cache_t *c)
969 {
970 	vmem_t vmem;
971 
972 	if (mdb_vread(&vmem, sizeof (vmem), (uintptr_t)c->cache_arena) == -1) {
973 		mdb_warn("cannot read arena %p for cache '%s'",
974 		    (uintptr_t)c->cache_arena, c->cache_name);
975 		return (0);
976 	}
977 
978 	/*
979 	 * If this cache isn't allocating from the kmem_default or the
980 	 * kmem_firewall vmem arena, we're not interested.
981 	 */
982 	if (strcmp(vmem.vm_name, "kmem_default") != 0 &&
983 	    strcmp(vmem.vm_name, "kmem_firewall") != 0)
984 		return (0);
985 
986 	return (1);
987 }
988 
989 static int
990 typegraph_estimate(uintptr_t addr, const kmem_cache_t *c, size_t *est)
991 {
992 	if (!typegraph_interested(c))
993 		return (WALK_NEXT);
994 
995 	*est += kmem_estimate_allocated(addr, c);
996 
997 	return (WALK_NEXT);
998 }
999 
1000 static int
1001 typegraph_estimate_modctl(uintptr_t addr, const struct modctl *m, size_t *est)
1002 {
1003 	struct module mod;
1004 
1005 	if (m->mod_mp == NULL)
1006 		return (WALK_NEXT);
1007 
1008 	if (mdb_vread(&mod, sizeof (mod), (uintptr_t)m->mod_mp) == -1) {
1009 		mdb_warn("couldn't read modctl %p's module", addr);
1010 		return (WALK_NEXT);
1011 	}
1012 
1013 	(*est) += mod.nsyms;
1014 
1015 	return (WALK_NEXT);
1016 }
1017 
1018 /*ARGSUSED*/
1019 static int
1020 typegraph_estimate_vmem(uintptr_t addr, const vmem_t *vmem, size_t *est)
1021 {
1022 	if (strcmp(vmem->vm_name, "kmem_oversize") != 0)
1023 		return (WALK_NEXT);
1024 
1025 	*est += (size_t)(vmem->vm_kstat.vk_alloc.value.ui64 -
1026 	    vmem->vm_kstat.vk_free.value.ui64);
1027 
1028 	return (WALK_NEXT);
1029 }
1030 
1031 /*ARGSUSED*/
1032 static int
1033 typegraph_buf(uintptr_t addr, void *ignored, tg_nodedata_t *tgd)
1034 {
1035 	tg_node_t *node = tgd->tgd_next++;
1036 	uintptr_t limit = addr + tgd->tgd_size;
1037 
1038 	node->tgn_base = addr;
1039 	node->tgn_limit = limit;
1040 
1041 	return (WALK_NEXT);
1042 }
1043 
1044 /*ARGSUSED*/
1045 static int
1046 typegraph_kmem(uintptr_t addr, const kmem_cache_t *c, tg_node_t **tgp)
1047 {
1048 	tg_node_t *node = *tgp;
1049 	tg_nodedata_t tgd;
1050 	mdb_ctf_id_t type;
1051 	int i, smaller;
1052 
1053 	mdb_ctf_type_invalidate(&type);
1054 
1055 	if (!typegraph_interested(c))
1056 		return (WALK_NEXT);
1057 
1058 	tgd.tgd_size = c->cache_bufsize;
1059 	tgd.tgd_next = *tgp;
1060 
1061 	if (mdb_pwalk("kmem", (mdb_walk_cb_t)typegraph_buf, &tgd, addr) == -1) {
1062 		mdb_warn("can't walk kmem for cache %p (%s)", addr,
1063 		    c->cache_name);
1064 		return (WALK_DONE);
1065 	}
1066 
1067 	*tgp = tgd.tgd_next;
1068 
1069 	for (i = 0; tg_cachetab[i].tgc_name != NULL; i++) {
1070 		if (strcmp(tg_cachetab[i].tgc_name, c->cache_name) != 0)
1071 			continue;
1072 
1073 		if (mdb_ctf_lookup_by_name(tg_cachetab[i].tgc_type,
1074 		    &type) == -1) {
1075 			mdb_warn("could not find type '%s', allegedly type "
1076 			    "for cache %s", tg_cachetab[i].tgc_type,
1077 			    c->cache_name);
1078 			break;
1079 		}
1080 
1081 		break;
1082 	}
1083 
1084 	/*
1085 	 * If this is a named cache (i.e., not from a kmem_alloc_[n] cache),
1086 	 * the nextsize is 0.
1087 	 */
1088 	if (strncmp(c->cache_name, "kmem_alloc_", strlen("kmem_alloc_")) == 0) {
1089 		GElf_Sym sym;
1090 		GElf_Sym sym2;
1091 
1092 		if (tg_sizes == NULL) {
1093 			size_t nsizes = 0;
1094 			size_t nsizes_reg = 0;
1095 			size_t nsizes_big = 0;
1096 
1097 			if (mdb_lookup_by_name("kmem_alloc_sizes",
1098 			    &sym) == -1) {
1099 				mdb_warn("failed to find 'kmem_alloc_sizes'");
1100 				return (WALK_ERR);
1101 			}
1102 			nsizes_reg = sym.st_size / sizeof (int);
1103 
1104 			if (mdb_lookup_by_name("kmem_big_alloc_sizes",
1105 			    &sym2) != -1) {
1106 				nsizes_big = sym2.st_size / sizeof (int);
1107 			}
1108 
1109 			nsizes = nsizes_reg + nsizes_big;
1110 
1111 			tg_sizes = mdb_zalloc(nsizes * sizeof (int), UM_SLEEP);
1112 			tg_nsizes = nsizes;
1113 
1114 			if (mdb_vread(tg_sizes, sym.st_size,
1115 			    (uintptr_t)sym.st_value) == -1) {
1116 				mdb_warn("failed to read kmem_alloc_sizes");
1117 				return (WALK_ERR);
1118 			}
1119 			if (nsizes_big > 0 &&
1120 			    mdb_vread(&tg_sizes[nsizes_reg], sym2.st_size,
1121 			    (uintptr_t)sym2.st_value) == -1) {
1122 				mdb_warn("failed to read kmem_big_alloc_sizes");
1123 				return (WALK_ERR);
1124 			}
1125 		}
1126 
1127 		/*
1128 		 * Yes, this is a linear search -- but we're talking about
1129 		 * a pretty small array (38 elements as of this writing), and
1130 		 * only executed a handful of times (for each sized kmem
1131 		 * cache).
1132 		 */
1133 		for (i = 0; i < tg_nsizes; i++) {
1134 			if (tg_sizes[i] == c->cache_bufsize)
1135 				break;
1136 		}
1137 
1138 		if (i == tg_nsizes) {
1139 			/*
1140 			 * Something is wrong -- this appears to be a sized
1141 			 * kmem cache, but we can't find its size in the
1142 			 * kmem_alloc_sizes array.  Emit a warning and return
1143 			 * failure.
1144 			 */
1145 			mdb_warn("couldn't find buffer size for %s (%d)"
1146 			    " in kmem_alloc_sizes array\n", c->cache_name,
1147 			    c->cache_bufsize);
1148 
1149 			return (WALK_ERR);
1150 		}
1151 
1152 		if (i == 0) {
1153 			smaller = 1;
1154 		} else {
1155 			smaller = tg_sizes[i - 1];
1156 		}
1157 	} else {
1158 		smaller = 0;
1159 	}
1160 
1161 	for (; node < *tgp; node++) {
1162 		node->tgn_type = type;
1163 		node->tgn_smaller = smaller;
1164 	}
1165 
1166 	*tgp = tgd.tgd_next;
1167 
1168 	return (WALK_NEXT);
1169 }
1170 
1171 /*ARGSUSED*/
1172 static int
1173 typegraph_seg(uintptr_t addr, const vmem_seg_t *seg, tg_node_t **tgp)
1174 {
1175 	tg_nodedata_t tgd;
1176 
1177 	tgd.tgd_next = *tgp;
1178 	tgd.tgd_size = seg->vs_end - seg->vs_start;
1179 
1180 	typegraph_buf(seg->vs_start, NULL, &tgd);
1181 
1182 	*tgp = tgd.tgd_next;
1183 	return (WALK_NEXT);
1184 }
1185 
1186 static int
1187 typegraph_vmem(uintptr_t addr, const vmem_t *vmem, tg_node_t **tgp)
1188 {
1189 	if (strcmp(vmem->vm_name, "kmem_oversize") != 0)
1190 		return (WALK_NEXT);
1191 
1192 	if (mdb_pwalk("vmem_alloc",
1193 	    (mdb_walk_cb_t)typegraph_seg, tgp, addr) == -1)
1194 		mdb_warn("can't walk vmem for arena %p", addr);
1195 
1196 	return (WALK_NEXT);
1197 }
1198 
1199 static void
1200 typegraph_build_anchored(uintptr_t addr, size_t size, mdb_ctf_id_t type)
1201 {
1202 	uintptr_t *buf;
1203 	tg_buildstate_t *state = NULL, *new_state, *free = NULL;
1204 	tg_node_t *node, *src;
1205 	tg_edge_t *edge;
1206 	size_t nptrs, ndx;
1207 	uintptr_t min = tg_sorted[0]->tgn_base;
1208 	uintptr_t max = tg_sorted[tg_nnodes - 1]->tgn_limit;
1209 	ssize_t rval;
1210 	int mask = sizeof (uintptr_t) - 1;
1211 
1212 	if (addr == 0 || size < sizeof (uintptr_t))
1213 		return;
1214 
1215 	/*
1216 	 * Add an anchored node.
1217 	 */
1218 	src = &tg_node[tg_nnodes + tg_nanchored++];
1219 	src->tgn_base = addr;
1220 	src->tgn_limit = addr + size;
1221 	src->tgn_type = type;
1222 
1223 push:
1224 	/*
1225 	 * If our address isn't pointer-aligned, we need to align it and
1226 	 * whack the size appropriately.
1227 	 */
1228 	if (addr & mask) {
1229 		if ((mask + 1) - (addr & mask) >= size)
1230 			goto out;
1231 
1232 		size -= (mask + 1) - (addr & mask);
1233 		addr += (mask + 1) - (addr & mask);
1234 	}
1235 
1236 	nptrs = size / sizeof (uintptr_t);
1237 	buf = mdb_alloc(size, UM_SLEEP);
1238 	ndx = 0;
1239 
1240 	if ((rval = mdb_vread(buf, size, addr)) != size) {
1241 		mdb_warn("couldn't read ptr at %p (size %ld); rval is %d",
1242 		    addr, size, rval);
1243 		goto out;
1244 	}
1245 pop:
1246 	for (; ndx < nptrs; ndx++) {
1247 		uintptr_t ptr = buf[ndx];
1248 
1249 		if (ptr < min || ptr >= max)
1250 			continue;
1251 
1252 		if ((node = typegraph_search(ptr)) == NULL)
1253 			continue;
1254 
1255 		/*
1256 		 * We need to record an edge to us.
1257 		 */
1258 		edge = mdb_zalloc(sizeof (tg_edge_t), UM_SLEEP);
1259 
1260 		edge->tge_src = src;
1261 		edge->tge_dest = node;
1262 		edge->tge_nextout = src->tgn_outgoing;
1263 		src->tgn_outgoing = edge;
1264 
1265 		edge->tge_srcoffs += ndx * sizeof (uintptr_t);
1266 		edge->tge_destoffs = ptr - node->tgn_base;
1267 		edge->tge_nextin = node->tgn_incoming;
1268 		node->tgn_incoming = edge;
1269 
1270 		/*
1271 		 * If this node is marked, we don't need to descend.
1272 		 */
1273 		if (node->tgn_marked)
1274 			continue;
1275 
1276 		/*
1277 		 * We need to descend.  To minimize the resource consumption
1278 		 * of type graph construction, we avoid recursing.
1279 		 */
1280 		node->tgn_marked = 1;
1281 
1282 		if (free != NULL) {
1283 			new_state = free;
1284 			free = free->tgbs_next;
1285 		} else {
1286 			new_state =
1287 			    mdb_zalloc(sizeof (tg_buildstate_t), UM_SLEEP);
1288 		}
1289 
1290 		new_state->tgbs_src = src;
1291 		src = node;
1292 
1293 		new_state->tgbs_addr = addr;
1294 		addr = node->tgn_base;
1295 		size = node->tgn_limit - addr;
1296 
1297 		new_state->tgbs_next = state;
1298 		new_state->tgbs_buf = buf;
1299 		new_state->tgbs_ndx = ndx + 1;
1300 		new_state->tgbs_nptrs = nptrs;
1301 		state = new_state;
1302 		goto push;
1303 	}
1304 
1305 	/*
1306 	 * If we're here, then we have completed this region.  We need to
1307 	 * free our buffer, and update our "resident" counter accordingly.
1308 	 */
1309 	mdb_free(buf, size);
1310 
1311 out:
1312 	/*
1313 	 * If we have pushed state, we need to pop it.
1314 	 */
1315 	if (state != NULL) {
1316 		buf = state->tgbs_buf;
1317 		ndx = state->tgbs_ndx;
1318 		src = state->tgbs_src;
1319 		nptrs = state->tgbs_nptrs;
1320 		addr = state->tgbs_addr;
1321 
1322 		size = nptrs * sizeof (uintptr_t);
1323 
1324 		new_state = state->tgbs_next;
1325 		state->tgbs_next = free;
1326 		free = state;
1327 		state = new_state;
1328 
1329 		goto pop;
1330 	}
1331 
1332 	while (free != NULL) {
1333 		state = free;
1334 		free = free->tgbs_next;
1335 		mdb_free(state, sizeof (tg_buildstate_t));
1336 	}
1337 }
1338 
1339 static void
1340 typegraph_build(uintptr_t addr, size_t size)
1341 {
1342 	uintptr_t limit = addr + size;
1343 	char name[MDB_SYM_NAMLEN];
1344 	GElf_Sym sym;
1345 	mdb_ctf_id_t type;
1346 
1347 	do {
1348 		if (mdb_lookup_by_addr(addr, MDB_SYM_EXACT, name,
1349 		    sizeof (name), &sym) == -1) {
1350 			addr++;
1351 			continue;
1352 		}
1353 
1354 		if (sym.st_size == 0) {
1355 			addr++;
1356 			continue;
1357 		}
1358 
1359 		if (strcmp(name, "kstat_initial") == 0) {
1360 			/*
1361 			 * Yes, this is a kludge.  "kstat_initial" ends up
1362 			 * backing the kstat vmem arena -- so we don't want
1363 			 * to include it as an anchor node.
1364 			 */
1365 			addr += sym.st_size;
1366 			continue;
1367 		}
1368 
1369 		/*
1370 		 * We have the symbol; now get its type.
1371 		 */
1372 		if (mdb_ctf_lookup_by_addr(addr, &type) == -1) {
1373 			addr += sym.st_size;
1374 			continue;
1375 		}
1376 
1377 		if (!mdb_ctf_type_valid(type)) {
1378 			addr += sym.st_size;
1379 			continue;
1380 		}
1381 
1382 		if (!mdb_ctf_type_valid(type = typegraph_resolve(type))) {
1383 			addr += sym.st_size;
1384 			continue;
1385 		}
1386 
1387 		typegraph_build_anchored(addr, (size_t)sym.st_size, type);
1388 		addr += sym.st_size;
1389 	} while (addr < limit);
1390 }
1391 
1392 /*ARGSUSED*/
1393 static int
1394 typegraph_thread(uintptr_t addr, const kthread_t *t, mdb_ctf_id_t *type)
1395 {
1396 	/*
1397 	 * If this thread isn't already a node, add it as an anchor.  And
1398 	 * regardless, set its type to be the specified type.
1399 	 */
1400 	tg_node_t *node;
1401 
1402 	if ((node = typegraph_search(addr)) == NULL) {
1403 		typegraph_build_anchored(addr, mdb_ctf_type_size(*type), *type);
1404 	} else {
1405 		node->tgn_type = *type;
1406 	}
1407 
1408 	return (WALK_NEXT);
1409 }
1410 
1411 /*ARGSUSED*/
1412 static int
1413 typegraph_kstat(uintptr_t addr, const vmem_seg_t *seg, mdb_ctf_id_t *type)
1414 {
1415 	size_t size = mdb_ctf_type_size(*type);
1416 
1417 	typegraph_build_anchored(seg->vs_start, size, *type);
1418 
1419 	return (WALK_NEXT);
1420 }
1421 
1422 static void
1423 typegraph_node_addtype(tg_node_t *node, tg_edge_t *edge, mdb_ctf_id_t rtype,
1424     const char *rmember, size_t roffs, mdb_ctf_id_t utype, mdb_ctf_id_t type)
1425 {
1426 	tg_type_t *tp;
1427 	tg_type_t **list;
1428 
1429 	if (edge->tge_destoffs == 0) {
1430 		list = &node->tgn_typelist;
1431 	} else {
1432 		list = &node->tgn_fraglist;
1433 	}
1434 
1435 	/*
1436 	 * First, search for this type in the type list.
1437 	 */
1438 	for (tp = *list; tp != NULL; tp = tp->tgt_next) {
1439 		if (mdb_ctf_type_cmp(tp->tgt_type, type) == 0)
1440 			return;
1441 	}
1442 
1443 	tp = mdb_zalloc(sizeof (tg_type_t), UM_SLEEP);
1444 	tp->tgt_next = *list;
1445 	tp->tgt_type = type;
1446 	tp->tgt_rtype = rtype;
1447 	tp->tgt_utype = utype;
1448 	tp->tgt_redge = edge;
1449 	tp->tgt_roffs = roffs;
1450 	tp->tgt_rmember = rmember;
1451 	*list = tp;
1452 
1453 	tg_improved = 1;
1454 }
1455 
1456 static void
1457 typegraph_stats_node(tg_node_t *node, tg_stats_t *stats)
1458 {
1459 	tg_edge_t *e;
1460 
1461 	stats->tgs_nodes++;
1462 
1463 	if (!node->tgn_marked)
1464 		stats->tgs_unmarked++;
1465 
1466 	if (mdb_ctf_type_valid(node->tgn_type)) {
1467 		stats->tgs_known++;
1468 		return;
1469 	}
1470 
1471 	if (node->tgn_typelist != NULL) {
1472 		stats->tgs_typed++;
1473 
1474 		if (node->tgn_typelist->tgt_next)
1475 			stats->tgs_conflicts++;
1476 
1477 		return;
1478 	}
1479 
1480 	if (node->tgn_fraglist != NULL) {
1481 		stats->tgs_frag++;
1482 		return;
1483 	}
1484 
1485 	/*
1486 	 * This node is not typed -- but check if any of its outgoing edges
1487 	 * were successfully typed; such nodes represent candidates for
1488 	 * an exhaustive type search.
1489 	 */
1490 	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
1491 		if (e->tge_dest->tgn_typelist) {
1492 			stats->tgs_candidates++;
1493 			break;
1494 		}
1495 	}
1496 }
1497 
1498 /*ARGSUSED*/
1499 static int
1500 typegraph_stats_buffer(uintptr_t addr, void *ignored, tg_stats_t *stats)
1501 {
1502 	tg_node_t *node;
1503 
1504 	stats->tgs_buffers++;
1505 
1506 	if ((node = typegraph_search(addr)) == NULL) {
1507 		return (WALK_NEXT);
1508 	}
1509 
1510 	typegraph_stats_node(node, stats);
1511 
1512 	return (WALK_NEXT);
1513 }
1514 
1515 /*ARGSUSED*/
1516 void
1517 typegraph_stat_print(char *name, size_t stat)
1518 {
1519 	mdb_printf("typegraph: ");
1520 
1521 	if (name == NULL) {
1522 		mdb_printf("\n");
1523 		return;
1524 	}
1525 
1526 	mdb_printf("%30s => %ld\n", name, stat);
1527 }
1528 
1529 static void
1530 typegraph_stat_str(char *name, char *str)
1531 {
1532 	mdb_printf("typegraph: %30s => %s\n", name, str);
1533 }
1534 
1535 static void
1536 typegraph_stat_perc(char *name, size_t stat, size_t total)
1537 {
1538 	int perc = (stat * 100) / total;
1539 	int tenths = ((stat * 1000) / total) % 10;
1540 
1541 	mdb_printf("typegraph: %30s => %-13ld (%2d.%1d%%)\n", name, stat,
1542 	    perc, tenths);
1543 }
1544 
1545 static void
1546 typegraph_stat_time(int last)
1547 {
1548 	static hrtime_t ts;
1549 	hrtime_t pass;
1550 
1551 	if (ts == 0) {
1552 		pass = (ts = gethrtime()) - tg_start;
1553 	} else {
1554 		hrtime_t now = gethrtime();
1555 
1556 		pass = now - ts;
1557 		ts = now;
1558 	}
1559 
1560 	mdb_printf("typegraph: %30s => %lld seconds\n",
1561 	    "time elapsed, this pass", pass / NANOSEC);
1562 	mdb_printf("typegraph: %30s => %lld seconds\n",
1563 	    "time elapsed, total", (ts - tg_start) / NANOSEC);
1564 	mdb_printf("typegraph:\n");
1565 
1566 	if (last)
1567 		ts = 0;
1568 }
1569 
1570 static void
1571 typegraph_stats(void)
1572 {
1573 	size_t i, n;
1574 	tg_stats_t stats;
1575 
1576 	bzero(&stats, sizeof (stats));
1577 
1578 	for (i = 0; i < tg_nnodes - tg_nanchored; i++)
1579 		typegraph_stats_node(&tg_node[i], &stats);
1580 
1581 	n = stats.tgs_nodes;
1582 
1583 	typegraph_stat_print("pass", tg_pass);
1584 	typegraph_stat_print("nodes", n);
1585 	typegraph_stat_perc("unmarked", stats.tgs_unmarked, n);
1586 	typegraph_stat_perc("known", stats.tgs_known, n);
1587 	typegraph_stat_perc("conjectured", stats.tgs_typed, n);
1588 	typegraph_stat_perc("conjectured fragments", stats.tgs_frag, n);
1589 	typegraph_stat_perc("known or conjectured",
1590 	    stats.tgs_known + stats.tgs_typed + stats.tgs_frag, n);
1591 	typegraph_stat_print("conflicts", stats.tgs_conflicts);
1592 	typegraph_stat_print("candidates", stats.tgs_candidates);
1593 	typegraph_stat_time(0);
1594 }
1595 
1596 /*
1597  * This is called both in pass1 and in subsequent passes (to propagate new type
1598  * inferences).
1599  */
1600 static void
1601 typegraph_pass1_node(tg_node_t *node, mdb_ctf_id_t type)
1602 {
1603 	tg_todo_t *first = NULL, *last = NULL, *free = NULL, *this = NULL;
1604 	tg_todo_t *todo;
1605 	tg_edge_t *e;
1606 	uintptr_t offs = 0;
1607 	size_t size;
1608 	const char *member;
1609 
1610 	if (!mdb_ctf_type_valid(type))
1611 		return;
1612 again:
1613 	/*
1614 	 * For each of the nodes corresponding to our outgoing edges,
1615 	 * determine their type.
1616 	 */
1617 	size = typegraph_size(type);
1618 
1619 	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
1620 		mdb_ctf_id_t ntype, rtype;
1621 		size_t nsize;
1622 		int kind;
1623 
1624 		/*
1625 		 * If we're being called in pass1, we're very conservative:
1626 		 *
1627 		 * (a)	If the outgoing edge is beyond the size of the type
1628 		 *	(and the current node is not the root), we refuse to
1629 		 *	descend.  This situation isn't actually hopeless -- we
1630 		 *	could be looking at array of the projected type -- but
1631 		 *	we'll allow a later phase to pass in that node and its
1632 		 *	conjectured type as the root.
1633 		 *
1634 		 * (b)	If the outgoing edge has a destination offset of
1635 		 *	something other than 0, we'll descend, but we won't
1636 		 *	add the type to the type list of the destination node.
1637 		 *	This allows us to gather information that can later be
1638 		 *	used to perform a more constrained search.
1639 		 */
1640 		if (tg_pass == TG_PASS1 && e->tge_srcoffs - offs > size)
1641 			continue;
1642 
1643 		if (offs >= typegraph_size(type))
1644 			continue;
1645 
1646 		if (e->tge_srcoffs < offs)
1647 			continue;
1648 
1649 		if (e->tge_marked)
1650 			continue;
1651 
1652 		ntype = typegraph_type_offset(type,
1653 		    e->tge_srcoffs - offs, e, &member);
1654 
1655 		if (!mdb_ctf_type_valid(ntype))
1656 			continue;
1657 
1658 		if ((kind = mdb_ctf_type_kind(ntype)) != CTF_K_POINTER)
1659 			continue;
1660 
1661 		if (mdb_ctf_type_reference(ntype, &rtype) == -1)
1662 			continue;
1663 
1664 		if (!mdb_ctf_type_valid(ntype = typegraph_resolve(rtype)))
1665 			continue;
1666 
1667 		kind = mdb_ctf_type_kind(ntype);
1668 		nsize = mdb_ctf_type_size(ntype);
1669 
1670 		if (nsize > TG_NODE_SIZE(e->tge_dest) - e->tge_destoffs)
1671 			continue;
1672 
1673 		typegraph_node_addtype(e->tge_dest, e, type,
1674 		    member, e->tge_srcoffs - offs, rtype, ntype);
1675 
1676 		if (e->tge_dest->tgn_marked)
1677 			continue;
1678 
1679 		/*
1680 		 * If our destination offset is 0 and the type that we marked
1681 		 * it with is useful, mark the node that we're
1682 		 * going to visit.  And regardless, mark the edge.
1683 		 */
1684 		if (e->tge_destoffs == 0 && kind == CTF_K_STRUCT)
1685 			e->tge_dest->tgn_marked = 1;
1686 
1687 		e->tge_marked = 1;
1688 
1689 		/*
1690 		 * If this isn't a structure, it's pointless to descend.
1691 		 */
1692 		if (kind != CTF_K_STRUCT)
1693 			continue;
1694 
1695 		if (nsize <= TG_NODE_SIZE(e->tge_dest) / 2) {
1696 			tg_node_t *dest = e->tge_dest;
1697 
1698 			/*
1699 			 * If the conjectured type is less than half of the
1700 			 * size of the object, we might be dealing with a
1701 			 * polymorphic type.  It's dangerous to descend in
1702 			 * this case -- if our conjectured type is larger than
1703 			 * the actual type, we will mispropagate.  (See the
1704 			 * description for phenomenon (c) in the block comment
1705 			 * for how this condition can arise.)  We therefore
1706 			 * only descend if we are in pass4 and there is only
1707 			 * one inference for this node.
1708 			 */
1709 			if (tg_pass < TG_PASS4)
1710 				continue;
1711 
1712 			if (dest->tgn_typelist == NULL ||
1713 			    dest->tgn_typelist->tgt_next != NULL) {
1714 				/*
1715 				 * There is either no inference for this node,
1716 				 * or more than one -- in either case, chicken
1717 				 * out.
1718 				 */
1719 				continue;
1720 			}
1721 		}
1722 
1723 		if (free != NULL) {
1724 			todo = free;
1725 			free = free->tgtd_next;
1726 		} else {
1727 			todo = mdb_alloc(sizeof (tg_todo_t), UM_SLEEP);
1728 		}
1729 
1730 		todo->tgtd_node = e->tge_dest;
1731 		todo->tgtd_type = ntype;
1732 		todo->tgtd_offs = e->tge_destoffs;
1733 		todo->tgtd_next = NULL;
1734 
1735 		if (last == NULL) {
1736 			first = last = todo;
1737 		} else {
1738 			last->tgtd_next = todo;
1739 			last = todo;
1740 		}
1741 	}
1742 
1743 	/*
1744 	 * If this was from a to-do list, it needs to be freed.
1745 	 */
1746 	if (this != NULL) {
1747 		this->tgtd_next = free;
1748 		free = this;
1749 	}
1750 
1751 	/*
1752 	 * Now peel something off of the to-do list.
1753 	 */
1754 	if (first != NULL) {
1755 		this = first;
1756 		first = first->tgtd_next;
1757 		if (first == NULL)
1758 			last = NULL;
1759 
1760 		node = this->tgtd_node;
1761 		offs = this->tgtd_offs;
1762 		type = this->tgtd_type;
1763 		goto again;
1764 	}
1765 
1766 	/*
1767 	 * Nothing more to do -- free the to-do list.
1768 	 */
1769 	while (free != NULL) {
1770 		this = free->tgtd_next;
1771 		mdb_free(free, sizeof (tg_todo_t));
1772 		free = this;
1773 	}
1774 }
1775 
1776 static void
1777 typegraph_pass1(void)
1778 {
1779 	int i;
1780 
1781 	tg_pass = TG_PASS1;
1782 	for (i = 0; i < tg_nnodes; i++)
1783 		typegraph_pass1_node(&tg_node[i], tg_node[i].tgn_type);
1784 }
1785 
1786 static void
1787 typegraph_pass2_node(tg_node_t *node)
1788 {
1789 	mdb_ctf_id_t type, ntype;
1790 	size_t tsize, nsize, rem, offs, limit;
1791 	uintptr_t base, addr;
1792 	int fam, kind;
1793 	tg_type_t *tp, *found = NULL;
1794 
1795 	if (mdb_ctf_type_valid(node->tgn_type))
1796 		return;
1797 
1798 	for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
1799 		if ((kind = mdb_ctf_type_kind(tp->tgt_type)) == CTF_K_UNION) {
1800 			/*
1801 			 * Fucking unions...
1802 			 */
1803 			found = NULL;
1804 			break;
1805 		}
1806 
1807 		if (kind == CTF_K_POINTER || kind == CTF_K_STRUCT) {
1808 			if (found != NULL) {
1809 				/*
1810 				 * There's more than one interpretation for
1811 				 * this structure; for now, we punt.
1812 				 */
1813 				found = NULL;
1814 				break;
1815 			}
1816 			found = tp;
1817 		}
1818 	}
1819 
1820 	if (found == NULL ||
1821 	    (found->tgt_flags & (TG_TYPE_ARRAY | TG_TYPE_NOTARRAY)))
1822 		return;
1823 
1824 	fam = typegraph_hasfam(type = found->tgt_type, &ntype);
1825 
1826 	if (fam) {
1827 		/*
1828 		 * If this structure has a flexible array member, and the
1829 		 * FAM type isn't a struct or pointer, we're going to treat
1830 		 * it as if it did not have a FAM.
1831 		 */
1832 		kind = mdb_ctf_type_kind(ntype);
1833 
1834 		if (kind != CTF_K_POINTER && kind != CTF_K_STRUCT)
1835 			fam = 0;
1836 	}
1837 
1838 	tsize = typegraph_size(type);
1839 	nsize = TG_NODE_SIZE(node);
1840 
1841 	if (!fam) {
1842 		/*
1843 		 * If this doesn't have a flexible array member, and our
1844 		 * preferred type is greater than half the size of the node, we
1845 		 * won't try to treat it as an array.
1846 		 */
1847 		if (tsize > nsize / 2)
1848 			return;
1849 
1850 		if ((rem = (nsize % tsize)) != 0) {
1851 			/*
1852 			 * If the next-smaller cache size is zero, we were
1853 			 * expecting the type size to evenly divide the node
1854 			 * size -- we must not have the right type.
1855 			 */
1856 			if (node->tgn_smaller == 0)
1857 				return;
1858 
1859 			if (nsize - rem <= node->tgn_smaller) {
1860 				/*
1861 				 * If this were really an array of this type,
1862 				 * we would have allocated it out of a smaller
1863 				 * cache -- it's either not an array (e.g.,
1864 				 * it's a bigger, unknown structure) or it's an
1865 				 * array of some other type.  In either case,
1866 				 * we punt.
1867 				 */
1868 				return;
1869 			}
1870 		}
1871 	}
1872 
1873 	/*
1874 	 * So far, this looks like it might be an array.
1875 	 */
1876 	if (node->tgn_smaller != 0) {
1877 		limit = node->tgn_smaller;
1878 	} else {
1879 		limit = TG_NODE_SIZE(node);
1880 	}
1881 
1882 	base = node->tgn_base;
1883 
1884 	if (fam) {
1885 		found->tgt_flags |= TG_TYPE_HASFAM;
1886 
1887 		for (offs = 0; offs < limit; ) {
1888 			ntype = typegraph_type_offset(type, offs, NULL, NULL);
1889 
1890 			if (!mdb_ctf_type_valid(ntype)) {
1891 				offs++;
1892 				continue;
1893 			}
1894 
1895 			if (!typegraph_couldbe(base + offs, ntype)) {
1896 				found->tgt_flags |= TG_TYPE_NOTARRAY;
1897 				return;
1898 			}
1899 
1900 			offs += mdb_ctf_type_size(ntype);
1901 		}
1902 	} else {
1903 		for (offs = 0; offs < tsize; ) {
1904 			ntype = typegraph_type_offset(type, offs, NULL, NULL);
1905 
1906 			if (!mdb_ctf_type_valid(ntype)) {
1907 				offs++;
1908 				continue;
1909 			}
1910 
1911 			for (addr = base + offs; addr < base + limit;
1912 			    addr += tsize) {
1913 				if (typegraph_couldbe(addr, ntype))
1914 					continue;
1915 
1916 				found->tgt_flags |= TG_TYPE_NOTARRAY;
1917 				return;
1918 			}
1919 
1920 			offs += mdb_ctf_type_size(ntype);
1921 			continue;
1922 		}
1923 	}
1924 
1925 	/*
1926 	 * Now mark this type as an array, and reattempt pass1 from this node.
1927 	 */
1928 	found->tgt_flags |= TG_TYPE_ARRAY;
1929 	typegraph_pass1_node(node, type);
1930 }
1931 
1932 static void
1933 typegraph_pass2(void)
1934 {
1935 	int i;
1936 
1937 	tg_pass = TG_PASS2;
1938 	do {
1939 		tg_improved = 0;
1940 
1941 		for (i = 0; i < tg_nnodes; i++)
1942 			typegraph_pass2_node(&tg_node[i]);
1943 	} while (tg_improved);
1944 }
1945 
1946 static void
1947 typegraph_pass3(void)
1948 {
1949 	tg_node_t *node;
1950 	tg_type_t *tp;
1951 	size_t i;
1952 	uintptr_t loffs;
1953 
1954 	tg_pass = TG_PASS3;
1955 	loffs = offsetof(tg_node_t, tgn_typelist);
1956 
1957 again:
1958 	/*
1959 	 * In this pass, we're going to coalesce types.  We're looking for
1960 	 * nodes where one possible type is a structure, and another is
1961 	 * either a CTF_K_INTEGER variant (e.g. "char", "void") or a
1962 	 * CTF_K_FORWARD (an opaque forward definition).
1963 	 *
1964 	 * N.B.  It might appear to be beneficial to coalesce types when
1965 	 * the possibilities include two structures, and one is contained
1966 	 * within the other (e.g., "door_node" contains a "vnode" as its
1967 	 * first member; "vnode" could be smooshed, leaving just "door_node").
1968 	 * This optimization is overly aggressive, however:  there are too
1969 	 * many places where we pull stunts with structures such that they're
1970 	 * actually polymorphic (e.g., "nc_cache" and "ncache").  Performing
1971 	 * this optimization would run the risk of false propagation --
1972 	 * which we want to avoid if at all possible.
1973 	 */
1974 	for (i = 0; i < tg_nnodes; i++) {
1975 		tg_type_t **list;
1976 
1977 		list = (tg_type_t **)((uintptr_t)(node = &tg_node[i]) + loffs);
1978 
1979 		if (mdb_ctf_type_valid(node->tgn_type))
1980 			continue;
1981 
1982 		if (*list == NULL)
1983 			continue;
1984 
1985 		/*
1986 		 * First, scan for type CTF_K_STRUCT.  If we find it, eliminate
1987 		 * everything that's a CTF_K_INTEGER or CTF_K_FORWARD.
1988 		 */
1989 		for (tp = *list; tp != NULL; tp = tp->tgt_next) {
1990 			if (mdb_ctf_type_kind(tp->tgt_type) == CTF_K_STRUCT)
1991 				break;
1992 		}
1993 
1994 		if (tp != NULL) {
1995 			tg_type_t *prev = NULL, *next;
1996 
1997 			for (tp = *list; tp != NULL; tp = next) {
1998 				int kind = mdb_ctf_type_kind(tp->tgt_type);
1999 
2000 				next = tp->tgt_next;
2001 
2002 				if (kind == CTF_K_INTEGER ||
2003 				    kind == CTF_K_FORWARD) {
2004 					if (prev == NULL) {
2005 						*list = next;
2006 					} else {
2007 						prev->tgt_next = next;
2008 					}
2009 
2010 					mdb_free(tp, sizeof (tg_type_t));
2011 				} else {
2012 					prev = tp;
2013 				}
2014 			}
2015 		}
2016 	}
2017 
2018 	if (loffs == offsetof(tg_node_t, tgn_typelist)) {
2019 		loffs = offsetof(tg_node_t, tgn_fraglist);
2020 		goto again;
2021 	}
2022 }
2023 
2024 static void
2025 typegraph_pass4_node(tg_node_t *node)
2026 {
2027 	tg_edge_t *e;
2028 	mdb_ctf_id_t type, ntype;
2029 	tg_node_t *src = NULL;
2030 	int kind;
2031 
2032 	if (mdb_ctf_type_valid(node->tgn_type))
2033 		return;
2034 
2035 	if (node->tgn_typelist != NULL)
2036 		return;
2037 
2038 	mdb_ctf_type_invalidate(&type);
2039 
2040 	/*
2041 	 * Now we want to iterate over all incoming edges.  If we can find an
2042 	 * incoming edge pointing to offset 0 from a node of known or
2043 	 * conjectured type, check the types of the referring node.
2044 	 */
2045 	for (e = node->tgn_incoming; e != NULL; e = e->tge_nextin) {
2046 		tg_node_t *n = e->tge_src;
2047 
2048 		if (e->tge_destoffs != 0)
2049 			continue;
2050 
2051 		if (!mdb_ctf_type_valid(ntype = n->tgn_type)) {
2052 			if (n->tgn_typelist != NULL &&
2053 			    n->tgn_typelist->tgt_next == NULL) {
2054 				ntype = n->tgn_typelist->tgt_type;
2055 			}
2056 
2057 			if (!mdb_ctf_type_valid(ntype))
2058 				continue;
2059 		}
2060 
2061 		kind = mdb_ctf_type_kind(ntype);
2062 
2063 		if (kind != CTF_K_STRUCT && kind != CTF_K_POINTER)
2064 			continue;
2065 
2066 		if (src != NULL && mdb_ctf_type_cmp(type, ntype) != 0) {
2067 			/*
2068 			 * We have two valid, potentially conflicting
2069 			 * interpretations for this node -- chicken out.
2070 			 */
2071 			src = NULL;
2072 			break;
2073 		}
2074 
2075 		src = n;
2076 		type = ntype;
2077 	}
2078 
2079 	if (src != NULL)
2080 		typegraph_pass1_node(src, type);
2081 }
2082 
2083 static void
2084 typegraph_pass4(void)
2085 {
2086 	size_t i, conjectured[2], gen = 0;
2087 
2088 	conjectured[1] = tg_nnodes;
2089 
2090 	tg_pass = TG_PASS4;
2091 	do {
2092 		conjectured[gen] = 0;
2093 
2094 		for (i = 0; i < tg_nnodes; i++) {
2095 			if (tg_node[i].tgn_typelist != NULL)
2096 				conjectured[gen]++;
2097 			typegraph_pass4_node(&tg_node[i]);
2098 		}
2099 
2100 		/*
2101 		 * Perform another pass3 to coalesce any new conflicts.
2102 		 */
2103 		typegraph_pass3();
2104 		tg_pass = TG_PASS4;
2105 		gen ^= 1;
2106 	} while (conjectured[gen ^ 1] < conjectured[gen]);
2107 }
2108 
2109 static void
2110 typegraph_postpass_node(tg_node_t *node)
2111 {
2112 	size_t total = 0;
2113 	tg_edge_t *e, *edge = node->tgn_outgoing;
2114 	tg_poststate_t *free = NULL, *stack = NULL, *state;
2115 	tg_node_t *dest;
2116 
2117 	if (node->tgn_postmarked)
2118 		return;
2119 
2120 push:
2121 	node->tgn_postmarked = 1;
2122 	node->tgn_reach = 0;
2123 
2124 pop:
2125 	for (e = edge; e != NULL; e = e->tge_nextout) {
2126 		dest = e->tge_dest;
2127 
2128 		if (dest->tgn_postmarked)
2129 			continue;
2130 
2131 		/*
2132 		 * Add a new element and descend.
2133 		 */
2134 		if (free == NULL) {
2135 			state = mdb_alloc(sizeof (tg_poststate_t), UM_SLEEP);
2136 		} else {
2137 			state = free;
2138 			free = free->tgps_next;
2139 		}
2140 
2141 		state->tgps_node = node;
2142 		state->tgps_edge = e;
2143 		state->tgps_total = total;
2144 		state->tgps_next = stack;
2145 		stack = state;
2146 
2147 		node = dest;
2148 		edge = dest->tgn_outgoing;
2149 		goto push;
2150 	}
2151 
2152 	if (!mdb_ctf_type_valid(node->tgn_type) &&
2153 	    node->tgn_typelist == NULL && node->tgn_fraglist == NULL) {
2154 		/*
2155 		 * We are an unknown node; our count must reflect this.
2156 		 */
2157 		node->tgn_reach++;
2158 	}
2159 
2160 	/*
2161 	 * Now we need to check for state to pop.
2162 	 */
2163 	if ((state = stack) != NULL) {
2164 		edge = state->tgps_edge;
2165 		node = state->tgps_node;
2166 		total = state->tgps_total;
2167 		dest = edge->tge_dest;
2168 
2169 		stack = state->tgps_next;
2170 		state->tgps_next = free;
2171 		free = state;
2172 
2173 		if (!mdb_ctf_type_valid(dest->tgn_type) &&
2174 		    dest->tgn_typelist == NULL && dest->tgn_fraglist == NULL) {
2175 			/*
2176 			 * We only sum our child's reach into our own if
2177 			 * that child is of unknown type.  This prevents long
2178 			 * chains of non-increasing reach.
2179 			 */
2180 			node->tgn_reach += dest->tgn_reach;
2181 		}
2182 
2183 		edge = edge->tge_nextout;
2184 		goto pop;
2185 	}
2186 
2187 	/*
2188 	 * We need to free our freelist.
2189 	 */
2190 	while (free != NULL) {
2191 		state = free;
2192 		free = free->tgps_next;
2193 		mdb_free(state, sizeof (tg_poststate_t));
2194 	}
2195 }
2196 
2197 static void
2198 typegraph_postpass(void)
2199 {
2200 	int i, max = 0;
2201 	tg_node_t *node, *maxnode = NULL;
2202 	char c[256];
2203 
2204 	for (i = 0; i < tg_nnodes; i++)
2205 		tg_node[i].tgn_postmarked = 0;
2206 
2207 	/*
2208 	 * From those nodes with unknown type and no outgoing edges, we want
2209 	 * to eminate towards the root.
2210 	 */
2211 	for (i = tg_nnodes - tg_nanchored; i < tg_nnodes; i++) {
2212 		node = &tg_node[i];
2213 
2214 		typegraph_postpass_node(node);
2215 	}
2216 
2217 	for (i = 0; i < tg_nnodes - tg_nanchored; i++) {
2218 		node = &tg_node[i];
2219 
2220 		if (mdb_ctf_type_valid(node->tgn_type))
2221 			continue;
2222 
2223 		if (node->tgn_reach < max)
2224 			continue;
2225 
2226 		maxnode = node;
2227 		max = node->tgn_reach;
2228 	}
2229 
2230 	typegraph_stat_str("pass", "post");
2231 
2232 	if (maxnode != NULL) {
2233 		mdb_snprintf(c, sizeof (c), "%p",
2234 		    maxnode->tgn_base, maxnode->tgn_reach);
2235 	} else {
2236 		strcpy(c, "-");
2237 	}
2238 
2239 	typegraph_stat_print("nodes", tg_nnodes - tg_nanchored);
2240 	typegraph_stat_str("greatest unknown node reach", c);
2241 	typegraph_stat_perc("reachable unknown nodes",
2242 	    max, tg_nnodes - tg_nanchored);
2243 	typegraph_stat_time(1);
2244 }
2245 
2246 static void
2247 typegraph_allpass(int first)
2248 {
2249 	size_t i;
2250 	tg_edge_t *e;
2251 
2252 	if (!first)
2253 		tg_start = gethrtime();
2254 
2255 	for (i = 0; i < tg_nnodes; i++) {
2256 		tg_node[i].tgn_marked = 0;
2257 		tg_node[i].tgn_postmarked = 0;
2258 
2259 		for (e = tg_node[i].tgn_incoming; e != NULL; e = e->tge_nextin)
2260 			e->tge_marked = 0;
2261 	}
2262 
2263 	typegraph_pass1();
2264 	typegraph_stats();
2265 	typegraph_pass2();
2266 	typegraph_stats();
2267 	typegraph_pass3();
2268 	typegraph_stats();
2269 	typegraph_pass4();
2270 	typegraph_stats();
2271 	typegraph_postpass();
2272 }
2273 
2274 /*ARGSUSED*/
2275 static int
2276 typegraph_modctl(uintptr_t addr, const struct modctl *m, int *ignored)
2277 {
2278 	struct module mod;
2279 	tg_node_t *node;
2280 	mdb_ctf_id_t type;
2281 
2282 	if (m->mod_mp == NULL)
2283 		return (WALK_NEXT);
2284 
2285 	if (mdb_vread(&mod, sizeof (mod), (uintptr_t)m->mod_mp) == -1) {
2286 		mdb_warn("couldn't read modctl %p's module", addr);
2287 		return (WALK_NEXT);
2288 	}
2289 
2290 	/*
2291 	 * As long as we're here, we're going to mark the address pointed
2292 	 * to by mod_mp as a "struct module" (mod_mp is defined to be a
2293 	 * void *).  Yes, this is a horrible kludge -- but it's not like
2294 	 * this code isn't already depending on the fact that mod_mp is
2295 	 * actually a pointer to "struct module" (see the mdb_vread(), above).
2296 	 * Without this, we can't identify any of the objects allocated by
2297 	 * krtld.
2298 	 */
2299 	if ((node = typegraph_search((uintptr_t)m->mod_mp)) != NULL) {
2300 		if (mdb_ctf_lookup_by_name("struct module", &type) != -1)
2301 			node->tgn_type = type;
2302 	}
2303 
2304 	typegraph_build((uintptr_t)mod.data, mod.data_size);
2305 	typegraph_build((uintptr_t)mod.bss, mod.bss_size);
2306 
2307 	return (WALK_NEXT);
2308 }
2309 
2310 static void
2311 typegraph_sort(void)
2312 {
2313 	size_t i;
2314 
2315 	if (tg_sorted)
2316 		mdb_free(tg_sorted, tg_nsorted * sizeof (tg_node_t *));
2317 
2318 	tg_nsorted = tg_nnodes;
2319 	tg_sorted = mdb_alloc(tg_nsorted * sizeof (tg_node_t *), UM_SLEEP);
2320 
2321 	for (i = 0; i < tg_nsorted; i++)
2322 		tg_sorted[i] = &tg_node[i];
2323 
2324 	qsort(tg_sorted, tg_nsorted, sizeof (tg_node_t *), typegraph_nodecmp);
2325 }
2326 
2327 static void
2328 typegraph_known_node(uintptr_t addr, const char *typename)
2329 {
2330 	tg_node_t *node;
2331 	mdb_ctf_id_t type;
2332 
2333 	if ((node = typegraph_search(addr)) == NULL) {
2334 		mdb_warn("couldn't find node corresponding to "
2335 		    "%s at %p\n", typename, addr);
2336 		return;
2337 	}
2338 
2339 	if (mdb_ctf_lookup_by_name(typename, &type) == -1) {
2340 		mdb_warn("couldn't find type for '%s'", typename);
2341 		return;
2342 	}
2343 
2344 	node->tgn_type = type;
2345 }
2346 
2347 /*
2348  * There are a few important nodes that are impossible to figure out without
2349  * some carnal knowledge.
2350  */
2351 static void
2352 typegraph_known_nodes(void)
2353 {
2354 	uintptr_t segkp;
2355 
2356 	if (mdb_readvar(&segkp, "segkp") == -1) {
2357 		mdb_warn("couldn't read 'segkp'");
2358 	} else {
2359 		struct seg seg;
2360 
2361 		if (mdb_vread(&seg, sizeof (seg), segkp) == -1) {
2362 			mdb_warn("couldn't read seg at %p", segkp);
2363 		} else {
2364 			typegraph_known_node((uintptr_t)seg.s_data,
2365 			    "struct segkp_segdata");
2366 		}
2367 	}
2368 }
2369 
2370 /*ARGSUSED*/
2371 int
2372 typegraph(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
2373 {
2374 	size_t est = 0;
2375 	tg_node_t *tgp;
2376 	kmem_cache_t c;
2377 	tg_stats_t stats;
2378 	mdb_ctf_id_t type;
2379 	int wasbuilt = tg_built;
2380 	uintptr_t kstat_arena;
2381 	uint_t perc;
2382 	int i;
2383 
2384 	if (!mdb_prop_postmortem) {
2385 		mdb_warn("typegraph: can only be run on a system "
2386 		    "dump; see dumpadm(1M)\n");
2387 		return (DCMD_ERR);
2388 	}
2389 
2390 	tg_verbose = 0;
2391 
2392 	if (mdb_getopts(argc, argv,
2393 	    'v', MDB_OPT_SETBITS, TRUE, &tg_verbose, NULL) != argc)
2394 		return (DCMD_USAGE);
2395 
2396 	if (tg_built)
2397 		goto trace;
2398 
2399 	tg_start = gethrtime();
2400 	typegraph_stat_str("pass", "initial");
2401 	typegraph_typetab_init();
2402 
2403 	/*
2404 	 * First, we need an estimate on the number of buffers.
2405 	 */
2406 	if (mdb_walk("kmem_cache",
2407 	    (mdb_walk_cb_t)typegraph_estimate, &est) == -1) {
2408 		mdb_warn("couldn't walk 'kmem_cache'");
2409 		return (DCMD_ERR);
2410 	}
2411 
2412 	if (mdb_walk("modctl",
2413 	    (mdb_walk_cb_t)typegraph_estimate_modctl, &est) == -1) {
2414 		mdb_warn("couldn't walk 'modctl'");
2415 		return (DCMD_ERR);
2416 	}
2417 
2418 	if (mdb_walk("vmem",
2419 	    (mdb_walk_cb_t)typegraph_estimate_vmem, &est) == -1) {
2420 		mdb_warn("couldn't walk 'vmem'");
2421 		return (DCMD_ERR);
2422 	}
2423 
2424 	typegraph_stat_print("maximum nodes", est);
2425 
2426 	tgp = tg_node = mdb_zalloc(sizeof (tg_node_t) * est, UM_SLEEP);
2427 	for (i = 0; i < est; i++)
2428 		mdb_ctf_type_invalidate(&tg_node[i].tgn_type);
2429 
2430 	if (mdb_walk("vmem", (mdb_walk_cb_t)typegraph_vmem, &tgp) == -1) {
2431 		mdb_warn("couldn't walk 'vmem'");
2432 		return (DCMD_ERR);
2433 	}
2434 
2435 	if (mdb_walk("kmem_cache", (mdb_walk_cb_t)typegraph_kmem, &tgp) == -1) {
2436 		mdb_warn("couldn't walk 'kmem_cache'");
2437 		return (DCMD_ERR);
2438 	}
2439 
2440 	tg_nnodes = tgp - tg_node;
2441 
2442 	typegraph_stat_print("actual nodes", tg_nnodes);
2443 
2444 	typegraph_sort();
2445 
2446 	if (mdb_ctf_lookup_by_name("kthread_t", &type) == -1) {
2447 		mdb_warn("couldn't find 'kthread_t'");
2448 		return (DCMD_ERR);
2449 	}
2450 
2451 	if (mdb_walk("thread", (mdb_walk_cb_t)typegraph_thread, &type) == -1) {
2452 		mdb_warn("couldn't walk 'thread'");
2453 		return (DCMD_ERR);
2454 	}
2455 
2456 	if (mdb_ctf_lookup_by_name("ekstat_t", &type) == -1) {
2457 		mdb_warn("couldn't find 'ekstat_t'");
2458 		return (DCMD_ERR);
2459 	}
2460 
2461 	if (mdb_readvar(&kstat_arena, "kstat_arena") == -1) {
2462 		mdb_warn("couldn't read 'kstat_arena'");
2463 		return (DCMD_ERR);
2464 	}
2465 
2466 	if (mdb_pwalk("vmem_alloc", (mdb_walk_cb_t)typegraph_kstat,
2467 	    &type, kstat_arena) == -1) {
2468 		mdb_warn("couldn't walk kstat vmem arena");
2469 		return (DCMD_ERR);
2470 	}
2471 
2472 	if (mdb_walk("modctl", (mdb_walk_cb_t)typegraph_modctl, NULL) == -1) {
2473 		mdb_warn("couldn't walk 'modctl'");
2474 		return (DCMD_ERR);
2475 	}
2476 
2477 	typegraph_stat_print("anchored nodes", tg_nanchored);
2478 	tg_nnodes += tg_nanchored;
2479 	typegraph_sort();
2480 	typegraph_known_nodes();
2481 	typegraph_stat_time(0);
2482 	tg_built = 1;
2483 
2484 trace:
2485 	if (!wasbuilt || !(flags & DCMD_ADDRSPEC)) {
2486 		typegraph_allpass(!wasbuilt);
2487 		return (DCMD_OK);
2488 	}
2489 
2490 	bzero(&stats, sizeof (stats));
2491 
2492 	/*
2493 	 * If we've been given an address, it's a kmem cache.
2494 	 */
2495 	if (mdb_vread(&c, sizeof (c), addr) == -1) {
2496 		mdb_warn("couldn't read kmem_cache at %p", addr);
2497 		return (DCMD_ERR);
2498 	}
2499 
2500 	if (mdb_pwalk("kmem",
2501 	    (mdb_walk_cb_t)typegraph_stats_buffer, &stats, addr) == -1) {
2502 		mdb_warn("can't walk kmem for cache %p", addr);
2503 		return (DCMD_ERR);
2504 	}
2505 
2506 	if (DCMD_HDRSPEC(flags))
2507 		mdb_printf("%-25s %7s %7s %7s %7s %7s %7s %5s\n", "NAME",
2508 		    "BUFS", "NODES", "UNMRK", "KNOWN",
2509 		    "INFER", "FRAG", "HIT%");
2510 
2511 	if (stats.tgs_nodes) {
2512 		perc = ((stats.tgs_known + stats.tgs_typed +
2513 		    stats.tgs_frag) * 1000) / stats.tgs_nodes;
2514 	} else {
2515 		perc = 0;
2516 	}
2517 
2518 	mdb_printf("%-25s %7ld %7ld %7ld %7ld %7ld %7ld %3d.%1d\n",
2519 	    c.cache_name, stats.tgs_buffers, stats.tgs_nodes,
2520 	    stats.tgs_unmarked, stats.tgs_known, stats.tgs_typed,
2521 	    stats.tgs_frag, perc / 10, perc % 10);
2522 
2523 	return (DCMD_OK);
2524 }
2525 
2526 int
2527 typegraph_built(void)
2528 {
2529 	if (!tg_built) {
2530 		mdb_warn("type graph not yet built; run ::typegraph.\n");
2531 		return (0);
2532 	}
2533 
2534 	return (1);
2535 }
2536 
2537 int
2538 whattype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
2539 {
2540 	tg_node_t *node;
2541 	tg_edge_t *e;
2542 	char buf[MDB_SYM_NAMLEN];
2543 	tg_type_t *tp;
2544 	int verbose = 0;
2545 
2546 	if (mdb_getopts(argc, argv,
2547 	    'v', MDB_OPT_SETBITS, TRUE, &verbose, NULL) != argc)
2548 		return (DCMD_USAGE);
2549 
2550 	if (!(flags & DCMD_ADDRSPEC))
2551 		return (DCMD_USAGE);
2552 
2553 	if (!typegraph_built())
2554 		return (DCMD_ABORT);
2555 
2556 	if ((node = typegraph_search(addr)) == NULL) {
2557 		mdb_warn("%p does not correspond to a node.\n", addr);
2558 		return (DCMD_OK);
2559 	}
2560 
2561 	if (!verbose) {
2562 		mdb_printf("%p is %p+%p, ", addr, node->tgn_base,
2563 		    addr - node->tgn_base);
2564 
2565 		if (mdb_ctf_type_valid(node->tgn_type)) {
2566 			mdb_printf("%s\n", mdb_ctf_type_name(node->tgn_type,
2567 			    buf, sizeof (buf)));
2568 			return (DCMD_OK);
2569 		}
2570 
2571 		if ((tp = node->tgn_typelist) == NULL) {
2572 			if ((tp = node->tgn_fraglist) == NULL) {
2573 				mdb_printf("unknown type\n");
2574 				return (DCMD_OK);
2575 			}
2576 		}
2577 
2578 		if (tp->tgt_next == NULL && mdb_ctf_type_valid(tp->tgt_type)) {
2579 			int kind = mdb_ctf_type_kind(tp->tgt_type);
2580 			size_t offs = tp->tgt_redge->tge_destoffs;
2581 
2582 			mdb_printf("possibly %s%s ",
2583 			    tp->tgt_flags & TG_TYPE_ARRAY ? "array of " : "",
2584 			    typegraph_type_name(tp->tgt_type, tp->tgt_utype));
2585 
2586 			if (kind != CTF_K_STRUCT && kind != CTF_K_UNION &&
2587 			    mdb_ctf_type_valid(tp->tgt_rtype) &&
2588 			    tp->tgt_rmember != NULL) {
2589 				mdb_printf("(%s.%s) ",
2590 				    mdb_ctf_type_name(tp->tgt_rtype, buf,
2591 				    sizeof (buf)), tp->tgt_rmember);
2592 			}
2593 
2594 			if (offs != 0)
2595 				mdb_printf("at %p", node->tgn_base + offs);
2596 
2597 			mdb_printf("\n");
2598 			return (DCMD_OK);
2599 		}
2600 
2601 		mdb_printf("possibly one of the following:\n");
2602 
2603 		for (; tp != NULL; tp = tp->tgt_next) {
2604 			size_t offs = tp->tgt_redge->tge_destoffs;
2605 
2606 			mdb_printf("  %s%s ",
2607 			    tp->tgt_flags & TG_TYPE_ARRAY ? "array of " : "",
2608 			    typegraph_type_name(tp->tgt_type, tp->tgt_utype));
2609 
2610 			if (offs != 0)
2611 				mdb_printf("at %p ", node->tgn_base + offs);
2612 
2613 			mdb_printf("(from %p+%p, type %s)\n",
2614 			    tp->tgt_redge->tge_src->tgn_base,
2615 			    tp->tgt_redge->tge_srcoffs,
2616 			    mdb_ctf_type_name(tp->tgt_rtype,
2617 			    buf, sizeof (buf)) != NULL ? buf : "<unknown>");
2618 		}
2619 
2620 		mdb_printf("\n");
2621 
2622 		return (DCMD_OK);
2623 	}
2624 
2625 	mdb_printf("%-?s %-?s %-29s %5s %5s %s\n", "BASE", "LIMIT", "TYPE",
2626 	    "SIZE", "REACH", "MRK");
2627 	mdb_printf("%-?p %-?p %-29s %5d %5d %s\n",
2628 	    node->tgn_base, node->tgn_limit,
2629 	    mdb_ctf_type_name(node->tgn_type,
2630 	    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
2631 	    typegraph_size(node->tgn_type), node->tgn_reach,
2632 	    node->tgn_marked ? "yes" : "no");
2633 
2634 	mdb_printf("\n");
2635 	mdb_printf("  %-20s %?s %8s %-20s %s\n",
2636 	    "INFERENCE", "FROM", "SRCOFFS", "REFTYPE", "REFMEMBER");
2637 
2638 	for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
2639 		mdb_printf("  %-20s %?p %8p %-20s %s\n",
2640 		    typegraph_type_name(tp->tgt_type, tp->tgt_utype),
2641 		    tp->tgt_redge->tge_src->tgn_base,
2642 		    tp->tgt_redge->tge_srcoffs,
2643 		    mdb_ctf_type_name(tp->tgt_rtype,
2644 		    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
2645 		    tp->tgt_rmember != NULL ? tp->tgt_rmember : "-");
2646 	}
2647 
2648 	mdb_printf("\n");
2649 	mdb_printf("  %-20s %?s %8s %-20s %s\n",
2650 	    "FRAGMENT", "FROM", "SRCOFFS", "REFTYPE", "REFMEMBER");
2651 
2652 	for (tp = node->tgn_fraglist; tp != NULL; tp = tp->tgt_next) {
2653 		mdb_printf("  %-20s %?p %8p %-20s %s\n",
2654 		    typegraph_type_name(tp->tgt_type, tp->tgt_utype),
2655 		    tp->tgt_redge->tge_src->tgn_base,
2656 		    tp->tgt_redge->tge_srcoffs,
2657 		    mdb_ctf_type_name(tp->tgt_rtype,
2658 		    buf, sizeof (buf)) != NULL ? buf : "<unknown>",
2659 		    tp->tgt_rmember != NULL ? tp->tgt_rmember : "-");
2660 	}
2661 
2662 	mdb_printf("\n");
2663 
2664 	mdb_printf("  %?s %8s %8s %6s %6s %5s\n", "FROM", "SRCOFFS", "DESTOFFS",
2665 	    "MARKED", "STATUS", "REACH");
2666 
2667 	for (e = node->tgn_incoming; e != NULL; e = e->tge_nextin) {
2668 		tg_node_t *n = e->tge_src;
2669 
2670 		mdb_printf("  %?p %8p %8p %6s %6s %ld\n",
2671 		    n->tgn_base, e->tge_srcoffs, e->tge_destoffs,
2672 		    e->tge_marked ? "yes" : "no",
2673 		    mdb_ctf_type_valid(n->tgn_type) ? "known" :
2674 		    n->tgn_typelist != NULL ? "inferd" :
2675 		    n->tgn_fraglist != NULL ? "frgmnt" : "unknwn",
2676 		    n->tgn_reach);
2677 	}
2678 
2679 	mdb_printf("\n  %?s %8s %8s %6s %6s %5s\n", "TO", "SRCOFFS", "DESTOFFS",
2680 	    "MARKED", "STATUS", "REACH");
2681 
2682 	for (e = node->tgn_outgoing; e != NULL; e = e->tge_nextout) {
2683 		tg_node_t *n = e->tge_dest;
2684 
2685 		mdb_printf("  %?p %8p %8p %6s %6s %ld\n",
2686 		    n->tgn_base, e->tge_srcoffs, e->tge_destoffs,
2687 		    e->tge_marked ? "yes" : "no",
2688 		    mdb_ctf_type_valid(n->tgn_type) ? "known" :
2689 		    n->tgn_typelist != NULL ? "inferd" :
2690 		    n->tgn_fraglist != NULL ? "frgmnt" : "unknwn",
2691 		    n->tgn_reach);
2692 	}
2693 
2694 	mdb_printf("\n");
2695 
2696 	return (DCMD_OK);
2697 }
2698 
2699 int
2700 istype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
2701 {
2702 	tg_node_t *node;
2703 	mdb_ctf_id_t type;
2704 
2705 	if (!(flags & DCMD_ADDRSPEC) || argc != 1 ||
2706 	    argv[0].a_type != MDB_TYPE_STRING)
2707 		return (DCMD_USAGE);
2708 
2709 	if (!typegraph_built())
2710 		return (DCMD_ABORT);
2711 
2712 	/*
2713 	 * Determine the node corresponding to the passed address.
2714 	 */
2715 	if ((node = typegraph_search(addr)) == NULL) {
2716 		mdb_warn("%p not found\n", addr);
2717 		return (DCMD_ERR);
2718 	}
2719 
2720 	/*
2721 	 * Now look up the specified type.
2722 	 */
2723 	if (mdb_ctf_lookup_by_name(argv[0].a_un.a_str, &type) == -1) {
2724 		mdb_warn("could not find type %s", argv[0].a_un.a_str);
2725 		return (DCMD_ERR);
2726 	}
2727 
2728 	node->tgn_type = type;
2729 	typegraph_allpass(0);
2730 
2731 	return (DCMD_OK);
2732 }
2733 
2734 /*ARGSUSED*/
2735 int
2736 notype(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
2737 {
2738 	tg_node_t *node;
2739 
2740 	if (!(flags & DCMD_ADDRSPEC) || argc != 0)
2741 		return (DCMD_USAGE);
2742 
2743 	if (!typegraph_built())
2744 		return (DCMD_ABORT);
2745 
2746 	if ((node = typegraph_search(addr)) == NULL) {
2747 		mdb_warn("%p not found\n", addr);
2748 		return (DCMD_ERR);
2749 	}
2750 
2751 	mdb_ctf_type_invalidate(&node->tgn_type);
2752 	typegraph_allpass(0);
2753 
2754 	return (DCMD_OK);
2755 }
2756 
2757 int
2758 typegraph_walk_init(mdb_walk_state_t *wsp)
2759 {
2760 	wsp->walk_data = (void *)0;
2761 	return (WALK_NEXT);
2762 }
2763 
2764 int
2765 typeconflict_walk_step(mdb_walk_state_t *wsp)
2766 {
2767 	size_t ndx;
2768 	tg_node_t *node = NULL;
2769 
2770 	for (ndx = (size_t)wsp->walk_data; ndx < tg_nnodes; ndx++) {
2771 		node = &tg_node[ndx];
2772 
2773 		if (mdb_ctf_type_valid(node->tgn_type))
2774 			continue;
2775 
2776 		if (node->tgn_typelist == NULL)
2777 			continue;
2778 
2779 		if (node->tgn_typelist->tgt_next == NULL)
2780 			continue;
2781 
2782 		break;
2783 	}
2784 
2785 	if (ndx == tg_nnodes)
2786 		return (WALK_DONE);
2787 
2788 	wsp->walk_data = (void *)++ndx;
2789 	return (wsp->walk_callback(node->tgn_base, NULL, wsp->walk_cbdata));
2790 }
2791 
2792 int
2793 typeunknown_walk_step(mdb_walk_state_t *wsp)
2794 {
2795 	size_t ndx;
2796 	tg_node_t *node = NULL;
2797 
2798 	for (ndx = (size_t)wsp->walk_data; ndx < tg_nnodes; ndx++) {
2799 		node = &tg_node[ndx];
2800 
2801 		if (mdb_ctf_type_valid(node->tgn_type))
2802 			continue;
2803 
2804 		if (node->tgn_typelist != NULL)
2805 			continue;
2806 
2807 		if (node->tgn_fraglist != NULL)
2808 			continue;
2809 
2810 		break;
2811 	}
2812 
2813 	if (ndx == tg_nnodes)
2814 		return (WALK_DONE);
2815 
2816 	wsp->walk_data = (void *)++ndx;
2817 	return (wsp->walk_callback(node->tgn_base, NULL, wsp->walk_cbdata));
2818 }
2819 
2820 #define	FINDLOCKS_DEPTH		32
2821 
2822 typedef struct foundlock {
2823 	uintptr_t	fnd_addr;
2824 	uintptr_t	fnd_owner;
2825 	const char	*fnd_member[FINDLOCKS_DEPTH];
2826 	mdb_ctf_id_t	fnd_parent;
2827 	tg_node_t	*fnd_node;
2828 } foundlock_t;
2829 
2830 typedef struct findlocks {
2831 	uintptr_t	fl_addr;
2832 	uintptr_t	fl_thread;
2833 	size_t		fl_ndx;
2834 	size_t		fl_nlocks;
2835 	foundlock_t	*fl_locks;
2836 	mdb_ctf_id_t	fl_parent;
2837 	tg_node_t	*fl_node;
2838 	const char	*fl_member[FINDLOCKS_DEPTH - 1];
2839 	int		fl_depth;
2840 } findlocks_t;
2841 
2842 /*ARGSUSED*/
2843 static int
2844 findlocks_owner(uintptr_t addr, const void *data, void *owner)
2845 {
2846 	*((uintptr_t *)owner) = addr;
2847 
2848 	return (WALK_NEXT);
2849 }
2850 
2851 static int
2852 findlocks_findmutex(const char *name, mdb_ctf_id_t type, ulong_t offs,
2853     findlocks_t *fl)
2854 {
2855 	static int called = 0;
2856 	static mdb_ctf_id_t mutex;
2857 	static mdb_ctf_id_t thread;
2858 	mdb_ctf_id_t parent = fl->fl_parent;
2859 	uintptr_t addr = fl->fl_addr;
2860 	int kind, depth = fl->fl_depth, i;
2861 	foundlock_t *found;
2862 
2863 	offs /= NBBY;
2864 
2865 	if (!called) {
2866 		if (mdb_ctf_lookup_by_name("kmutex_t", &mutex) == -1) {
2867 			mdb_warn("can't find 'kmutex_t' type");
2868 			return (1);
2869 		}
2870 
2871 		if (!mdb_ctf_type_valid(mutex = typegraph_resolve(mutex))) {
2872 			mdb_warn("can't resolve 'kmutex_t' type");
2873 			return (1);
2874 		}
2875 
2876 		if (mdb_ctf_lookup_by_name("kthread_t", &thread) == -1) {
2877 			mdb_warn("can't find 'kthread_t' type");
2878 			return (1);
2879 		}
2880 
2881 		if (!mdb_ctf_type_valid(thread = typegraph_resolve(thread))) {
2882 			mdb_warn("can't resolve 'kthread_t' type");
2883 			return (1);
2884 		}
2885 
2886 		called = 1;
2887 	}
2888 
2889 	if (!mdb_ctf_type_valid(type))
2890 		return (0);
2891 
2892 	type = typegraph_resolve(type);
2893 	kind = mdb_ctf_type_kind(type);
2894 
2895 	if (!mdb_ctf_type_valid(type))
2896 		return (0);
2897 
2898 	if (kind == CTF_K_ARRAY) {
2899 		mdb_ctf_arinfo_t arr;
2900 		ssize_t size;
2901 
2902 		if (mdb_ctf_array_info(type, &arr) == -1)
2903 			return (0);
2904 
2905 		type = typegraph_resolve(arr.mta_contents);
2906 
2907 		if (!mdb_ctf_type_valid(type))
2908 			return (0);
2909 
2910 		/*
2911 		 * Small optimization:  don't bother running through the array
2912 		 * if we know that we can't process the type.
2913 		 */
2914 		kind = mdb_ctf_type_kind(type);
2915 		size = mdb_ctf_type_size(type);
2916 
2917 		if (kind == CTF_K_POINTER || kind == CTF_K_INTEGER)
2918 			return (0);
2919 
2920 		for (i = 0; i < arr.mta_nelems; i++) {
2921 			fl->fl_addr = addr + offs + (i * size);
2922 			findlocks_findmutex(name, type, 0, fl);
2923 		}
2924 
2925 		fl->fl_addr = addr;
2926 
2927 		return (0);
2928 	}
2929 
2930 	if (kind != CTF_K_STRUCT)
2931 		return (0);
2932 
2933 	if (mdb_ctf_type_cmp(type, mutex) == 0) {
2934 		mdb_ctf_id_t ttype;
2935 		uintptr_t owner = 0;
2936 		tg_node_t *node;
2937 
2938 		if (mdb_pwalk("mutex_owner",
2939 		    findlocks_owner, &owner, addr + offs) == -1) {
2940 			return (0);
2941 		}
2942 
2943 		/*
2944 		 * Check to see if the owner is a thread.
2945 		 */
2946 		if (owner == 0 || (node = typegraph_search(owner)) == NULL)
2947 			return (0);
2948 
2949 		if (!mdb_ctf_type_valid(node->tgn_type))
2950 			return (0);
2951 
2952 		ttype = typegraph_resolve(node->tgn_type);
2953 
2954 		if (!mdb_ctf_type_valid(ttype))
2955 			return (0);
2956 
2957 		if (mdb_ctf_type_cmp(ttype, thread) != 0)
2958 			return (0);
2959 
2960 		if (fl->fl_thread != 0 && owner != fl->fl_thread)
2961 			return (0);
2962 
2963 		if (fl->fl_ndx >= fl->fl_nlocks) {
2964 			size_t nlocks, osize, size;
2965 			foundlock_t *locks;
2966 
2967 			if ((nlocks = (fl->fl_nlocks << 1)) == 0)
2968 				nlocks = 1;
2969 
2970 			osize = fl->fl_nlocks * sizeof (foundlock_t);
2971 			size = nlocks * sizeof (foundlock_t);
2972 
2973 			locks = mdb_zalloc(size, UM_SLEEP);
2974 
2975 			if (fl->fl_locks) {
2976 				bcopy(fl->fl_locks, locks, osize);
2977 				mdb_free(fl->fl_locks, osize);
2978 			}
2979 
2980 			fl->fl_locks = locks;
2981 			fl->fl_nlocks = nlocks;
2982 		}
2983 
2984 		found = &fl->fl_locks[fl->fl_ndx++];
2985 		found->fnd_addr = (uintptr_t)addr + offs;
2986 		found->fnd_owner = owner;
2987 
2988 		for (i = 0; i < fl->fl_depth; i++)
2989 			found->fnd_member[i] = fl->fl_member[i];
2990 
2991 		found->fnd_member[i] = name;
2992 		found->fnd_parent = fl->fl_parent;
2993 		found->fnd_node = fl->fl_node;
2994 
2995 		return (0);
2996 	}
2997 
2998 	fl->fl_addr = (uintptr_t)addr + offs;
2999 
3000 	if (name == NULL) {
3001 		fl->fl_parent = type;
3002 	} else if (depth < FINDLOCKS_DEPTH - 1) {
3003 		fl->fl_member[depth] = name;
3004 		fl->fl_depth++;
3005 	}
3006 
3007 	mdb_ctf_member_iter(type, (mdb_ctf_member_f *)findlocks_findmutex, fl);
3008 
3009 	fl->fl_addr = addr;
3010 	fl->fl_parent = parent;
3011 	fl->fl_depth = depth;
3012 
3013 	return (0);
3014 }
3015 
3016 static void
3017 findlocks_node(tg_node_t *node, findlocks_t *fl)
3018 {
3019 	mdb_ctf_id_t type = node->tgn_type, ntype;
3020 	int kind;
3021 	tg_type_t *tp, *found = NULL;
3022 
3023 	if (!mdb_ctf_type_valid(type)) {
3024 		mdb_ctf_type_invalidate(&type);
3025 
3026 		for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
3027 			kind = mdb_ctf_type_kind(ntype = tp->tgt_type);
3028 
3029 			if (kind == CTF_K_UNION) {
3030 				/*
3031 				 * Insert disparaging comment about unions here.
3032 				 */
3033 				return;
3034 			}
3035 
3036 			if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
3037 				continue;
3038 
3039 			if (found != NULL) {
3040 				/*
3041 				 * There are multiple interpretations for this
3042 				 * node; we have to punt.
3043 				 */
3044 				return;
3045 			}
3046 
3047 			found = tp;
3048 		}
3049 	}
3050 
3051 	if (found != NULL)
3052 		type = found->tgt_type;
3053 
3054 	fl->fl_parent = type;
3055 	fl->fl_node = node;
3056 
3057 	/*
3058 	 * We have our type.  Now iterate for locks.  Note that we don't yet
3059 	 * deal with locks in flexible array members.
3060 	 */
3061 	if (found != NULL && (found->tgt_flags & TG_TYPE_ARRAY) &&
3062 	    !(found->tgt_flags & TG_TYPE_HASFAM)) {
3063 		uintptr_t base, limit = node->tgn_limit;
3064 		size_t size = mdb_ctf_type_size(found->tgt_type);
3065 
3066 		for (base = node->tgn_base; base < limit; base += size) {
3067 			fl->fl_addr = base;
3068 			findlocks_findmutex(NULL, type, 0, fl);
3069 		}
3070 	} else {
3071 		fl->fl_addr = node->tgn_base;
3072 		findlocks_findmutex(NULL, type, 0, fl);
3073 	}
3074 
3075 	if (mdb_ctf_type_valid(type))
3076 		return;
3077 
3078 	for (tp = node->tgn_fraglist; tp != NULL; tp = tp->tgt_next) {
3079 		kind = mdb_ctf_type_kind(ntype = tp->tgt_type);
3080 
3081 		if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
3082 			continue;
3083 
3084 		fl->fl_addr = node->tgn_base + tp->tgt_redge->tge_destoffs;
3085 		fl->fl_parent = ntype;
3086 		findlocks_findmutex(NULL, ntype, 0, fl);
3087 	}
3088 }
3089 
3090 /*ARGSUSED*/
3091 int
3092 findlocks(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
3093 {
3094 	size_t i, j;
3095 	findlocks_t fl;
3096 
3097 	if (argc != 0)
3098 		return (DCMD_USAGE);
3099 
3100 	if (!typegraph_built())
3101 		return (DCMD_ABORT);
3102 
3103 	if (!(flags & DCMD_ADDRSPEC))
3104 		addr = 0;
3105 
3106 	bzero(&fl, sizeof (fl));
3107 	fl.fl_thread = addr;
3108 
3109 	for (i = 0; i < tg_nnodes; i++) {
3110 		findlocks_node(&tg_node[i], &fl);
3111 	}
3112 
3113 	for (i = 0; i < fl.fl_ndx; i++) {
3114 		foundlock_t *found = &fl.fl_locks[i];
3115 		char buf[MDB_SYM_NAMLEN];
3116 
3117 		if (found->fnd_member[0] != NULL) {
3118 			mdb_printf("%p (%s",
3119 			    found->fnd_addr,
3120 			    mdb_ctf_type_name(found->fnd_parent, buf,
3121 			    sizeof (buf)));
3122 
3123 			for (j = 0; found->fnd_member[j] != NULL; j++)
3124 				mdb_printf(".%s", found->fnd_member[j]);
3125 
3126 			mdb_printf(") is owned by %p\n", found->fnd_owner);
3127 		} else {
3128 			if (found->fnd_node->tgn_incoming == NULL) {
3129 				mdb_printf("%p (%a) is owned by %p\n",
3130 				    found->fnd_addr, found->fnd_addr,
3131 				    found->fnd_owner);
3132 			} else {
3133 				mdb_printf("%p is owned by %p\n",
3134 				    found->fnd_addr, found->fnd_owner);
3135 			}
3136 		}
3137 	}
3138 
3139 	mdb_printf("findlocks: nota bene: %slocks may be held",
3140 	    fl.fl_nlocks ? "other " : "");
3141 
3142 	if (addr == 0) {
3143 		mdb_printf("\n");
3144 	} else {
3145 		mdb_printf(" by %p\n", addr);
3146 	}
3147 
3148 	if (fl.fl_nlocks)
3149 		mdb_free(fl.fl_locks, fl.fl_nlocks * sizeof (foundlock_t));
3150 
3151 	return (DCMD_OK);
3152 }
3153 
3154 /*
3155  * ::findfalse:  Using type knowledge to detect potential false sharing
3156  *
3157  * In caching SMP systems, memory is kept coherent through bus-based snooping
3158  * protocols.  Under these protocols, only a single cache may have a given line
3159  * of memory in a dirty state.  If a different cache wishes to write to the
3160  * dirty line, the new cache must first read-to-own the dirty line from the
3161  * owning cache.  The size of the line used for coherence (the coherence
3162  * granularity) has an immediate ramification for parallel software:  because
3163  * only one cache may own a line at a given time, one wishes to avoid a
3164  * situation where two or more small, disjoint data structures are both
3165  * (a) contained within a single line and (b) accessed in parallel on disjoint
3166  * CPUs.  This situation -- so-called "false sharing" -- can induce suboptimal
3167  * scalability in otherwise scalable software.
3168  *
3169  * Historically, one has been able to find false sharing only with some
3170  * combination of keen intuition and good luck.  And where false sharing has
3171  * been discovered, it has almost always been after having induced suboptimal
3172  * scaling; one has historically not been able to detect false sharing before
3173  * the fact.
3174  *
3175  * Building on the mechanism for postmortem type information, however, we
3176  * can -- from a system crash dump -- detect the the potentially most egregious
3177  * cases of false sharing.  Specifically, after having run through the type
3178  * identification passes described above, we can iterate over all nodes,
3179  * looking for nodes that satisfy the following criteria:
3180  *
3181  *  (a)	The node is an array.  That is, the node was either determined to
3182  *	be of type CTF_K_ARRAY, or the node was inferred to be an array in
3183  *	pass2 of type identification (described above).
3184  *
3185  *  (b)	Each element of the array is a structure that is smaller than the
3186  *	coherence granularity.
3187  *
3188  *  (c)	The total size of the array is greater than the coherence granularity.
3189  *
3190  *  (d)	Each element of the array is a structure that contains within it a
3191  *	synchronization primitive (mutex, readers/writer lock, condition
3192  *	variable or semaphore).  We use the presence of a synchronization
3193  *	primitive as a crude indicator that the disjoint elements of the
3194  *	array are accessed in parallel.
3195  *
3196  * Any node satisfying these criteria is identified as an object that could
3197  * potentially suffer from false sharing, and the node's address, symbolic
3198  * name (if any), type, type size and total size are provided as output.
3199  *
3200  * While there are some instances of false sharing that do not meet the
3201  * above criteria (e.g., if the synchronization for each element is handled
3202  * in a separate structure, or if the elements are only manipulated with
3203  * atomic memory operations), these criteria yield many examples of false
3204  * sharing without swamping the user with false positives.
3205  */
3206 #define	FINDFALSE_COHERENCE_SIZE	64
3207 
3208 /*ARGSUSED*/
3209 static int
3210 findfalse_findsync(const char *name, mdb_ctf_id_t type, ulong_t offs,
3211     void *ignored)
3212 {
3213 	int i, kind;
3214 	static int called = 0;
3215 	static struct {
3216 		char *name;
3217 		mdb_ctf_id_t type;
3218 	} sync[] = {
3219 		{ "kmutex_t" },
3220 		{ "krwlock_t" },
3221 		{ "kcondvar_t" },
3222 		{ "ksema_t" },
3223 		{ NULL }
3224 	};
3225 
3226 	if (!called) {
3227 		char *name;
3228 
3229 		called = 1;
3230 
3231 		for (i = 0; (name = sync[i].name) != NULL; i++) {
3232 			if (mdb_ctf_lookup_by_name(name, &sync[i].type) == -1) {
3233 				mdb_warn("can't find '%s' type", name);
3234 				return (0);
3235 			}
3236 
3237 			sync[i].type = typegraph_resolve(sync[i].type);
3238 
3239 			if (!mdb_ctf_type_valid(sync[i].type)) {
3240 				mdb_warn("can't resolve '%s' type", name);
3241 				return (0);
3242 			}
3243 		}
3244 	}
3245 
3246 	/*
3247 	 * See if this type is any of the synchronization primitives.
3248 	 */
3249 	if (!mdb_ctf_type_valid(type))
3250 		return (0);
3251 
3252 	type = typegraph_resolve(type);
3253 
3254 	for (i = 0; sync[i].name != NULL; i++) {
3255 		if (mdb_ctf_type_cmp(type, sync[i].type) == 0) {
3256 			/*
3257 			 * We have a winner!
3258 			 */
3259 			return (1);
3260 		}
3261 	}
3262 
3263 	if ((kind = mdb_ctf_type_kind(type)) == CTF_K_ARRAY) {
3264 		mdb_ctf_arinfo_t arr;
3265 
3266 		if (mdb_ctf_array_info(type, &arr) == -1)
3267 			return (0);
3268 
3269 		type = typegraph_resolve(arr.mta_contents);
3270 
3271 		return (findfalse_findsync(name, type, 0, NULL));
3272 	}
3273 
3274 	if (kind != CTF_K_STRUCT)
3275 		return (0);
3276 
3277 	if (mdb_ctf_member_iter(type,
3278 	    (mdb_ctf_member_f *)findfalse_findsync, NULL) != 0)
3279 		return (1);
3280 
3281 	return (0);
3282 }
3283 
3284 static void
3285 findfalse_node(tg_node_t *node)
3286 {
3287 	mdb_ctf_id_t type = node->tgn_type;
3288 	tg_type_t *tp, *found = NULL;
3289 	ssize_t size;
3290 	int kind;
3291 	char buf[MDB_SYM_NAMLEN + 1];
3292 	GElf_Sym sym;
3293 
3294 	if (!mdb_ctf_type_valid(type)) {
3295 		mdb_ctf_type_invalidate(&type);
3296 
3297 		for (tp = node->tgn_typelist; tp != NULL; tp = tp->tgt_next) {
3298 			kind = mdb_ctf_type_kind(tp->tgt_type);
3299 
3300 			if (kind == CTF_K_UNION) {
3301 				/*
3302 				 * Once again, the unions impede progress...
3303 				 */
3304 				return;
3305 			}
3306 
3307 			if (kind != CTF_K_STRUCT && kind != CTF_K_ARRAY)
3308 				continue;
3309 
3310 			if (found != NULL) {
3311 				/*
3312 				 * There are multiple interpretations for this
3313 				 * node; we have to punt.
3314 				 */
3315 				return;
3316 			}
3317 
3318 			found = tp;
3319 		}
3320 	}
3321 
3322 	if (found != NULL)
3323 		type = found->tgt_type;
3324 
3325 	if (!mdb_ctf_type_valid(type))
3326 		return;
3327 
3328 	kind = mdb_ctf_type_kind(type);
3329 
3330 	/*
3331 	 * If this isn't an array (or treated as one), it can't induce false
3332 	 * sharing.  (Or at least, we can't detect it.)
3333 	 */
3334 	if (found != NULL) {
3335 		if (!(found->tgt_flags & TG_TYPE_ARRAY))
3336 			return;
3337 
3338 		if (found->tgt_flags & TG_TYPE_HASFAM)
3339 			return;
3340 	} else {
3341 		if (kind != CTF_K_ARRAY)
3342 			return;
3343 	}
3344 
3345 	if (kind == CTF_K_ARRAY) {
3346 		mdb_ctf_arinfo_t arr;
3347 
3348 		if (mdb_ctf_array_info(type, &arr) == -1)
3349 			return;
3350 
3351 		type = typegraph_resolve(arr.mta_contents);
3352 
3353 		if (!mdb_ctf_type_valid(type))
3354 			return;
3355 
3356 	}
3357 
3358 	size = mdb_ctf_type_size(type);
3359 
3360 	/*
3361 	 * If the size is greater than or equal to the cache line size, it's
3362 	 * not false sharing.  (Or at least, the false sharing is benign.)
3363 	 */
3364 	if (size >= FINDFALSE_COHERENCE_SIZE)
3365 		return;
3366 
3367 	if (TG_NODE_SIZE(node) <= FINDFALSE_COHERENCE_SIZE)
3368 		return;
3369 
3370 	/*
3371 	 * This looks like it could be a falsely shared structure.  If this
3372 	 * type contains a mutex, rwlock, semaphore or condition variable,
3373 	 * we're going to report it.
3374 	 */
3375 	if (!findfalse_findsync(NULL, type, 0, NULL))
3376 		return;
3377 
3378 	mdb_printf("%?p ", node->tgn_base);
3379 
3380 	if (mdb_lookup_by_addr(node->tgn_base, MDB_SYM_EXACT, buf,
3381 	    sizeof (buf), &sym) != -1) {
3382 		mdb_printf("%-28s ", buf);
3383 	} else {
3384 		mdb_printf("%-28s ", "-");
3385 	}
3386 
3387 	mdb_printf("%-22s %2d %7ld\n",
3388 	    mdb_ctf_type_name(type, buf, sizeof (buf)), size,
3389 	    TG_NODE_SIZE(node));
3390 }
3391 
3392 /*ARGSUSED*/
3393 int
3394 findfalse(uintptr_t addr, uint_t flags, int argc, const mdb_arg_t *argv)
3395 {
3396 	ssize_t i;
3397 
3398 	if (argc != 0 || (flags & DCMD_ADDRSPEC))
3399 		return (DCMD_USAGE);
3400 
3401 	if (!typegraph_built())
3402 		return (DCMD_ABORT);
3403 
3404 	mdb_printf("%?s %-28s %-22s %2s %7s\n", "ADDR", "SYMBOL", "TYPE",
3405 	    "SZ", "TOTSIZE");
3406 
3407 	/*
3408 	 * We go from the back of the bus and move forward to report false
3409 	 * sharing in named symbols before reporting false sharing in dynamic
3410 	 * structures.
3411 	 */
3412 	for (i = tg_nnodes - 1; i >= 0; i--)
3413 		findfalse_node(&tg_node[i]);
3414 
3415 	return (DCMD_OK);
3416 }
3417