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 == NULL || 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 == NULL || 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; 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; 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 = NULL; 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 == NULL || (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 != NULL && 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 == NULL) { 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