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 2006 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26#pragma ident "%Z%%M% %I% %E% SMI" 27 28/* 29 * This file contains routines that merge one tdata_t tree, called the child, 30 * into another, called the parent. Note that these names are used mainly for 31 * convenience and to represent the direction of the merge. They are not meant 32 * to imply any relationship between the tdata_t graphs prior to the merge. 33 * 34 * tdata_t structures contain two main elements - a hash of iidesc_t nodes, and 35 * a directed graph of tdesc_t nodes, pointed to by the iidesc_t nodes. Simply 36 * put, we merge the tdesc_t graphs, followed by the iidesc_t nodes, and then we 37 * clean up loose ends. 38 * 39 * The algorithm is as follows: 40 * 41 * 1. Mapping iidesc_t nodes 42 * 43 * For each child iidesc_t node, we first try to map its tdesc_t subgraph 44 * against the tdesc_t graph in the parent. For each node in the child subgraph 45 * that exists in the parent, a mapping between the two (between their type IDs) 46 * is established. For the child nodes that cannot be mapped onto existing 47 * parent nodes, a mapping is established between the child node ID and a 48 * newly-allocated ID that the node will use when it is re-created in the 49 * parent. These unmappable nodes are added to the md_tdtba (tdesc_t To Be 50 * Added) hash, which tracks nodes that need to be created in the parent. 51 * 52 * If all of the nodes in the subgraph for an iidesc_t in the child can be 53 * mapped to existing nodes in the parent, then we can try to map the child 54 * iidesc_t onto an iidesc_t in the parent. If we cannot find an equivalent 55 * iidesc_t, or if we were not able to completely map the tdesc_t subgraph(s), 56 * then we add this iidesc_t to the md_iitba (iidesc_t To Be Added) list. This 57 * list tracks iidesc_t nodes that are to be created in the parent. 58 * 59 * While visiting the tdesc_t nodes, we may discover a forward declaration (a 60 * FORWARD tdesc_t) in the parent that is resolved in the child. That is, there 61 * may be a structure or union definition in the child with the same name as the 62 * forward declaration in the parent. If we find such a node, we record an 63 * association in the md_fdida (Forward => Definition ID Association) list 64 * between the parent ID of the forward declaration and the ID that the 65 * definition will use when re-created in the parent. 66 * 67 * 2. Creating new tdesc_t nodes (the md_tdtba hash) 68 * 69 * We have now attempted to map all tdesc_t nodes from the child into the 70 * parent, and have, in md_tdtba, a hash of all tdesc_t nodes that need to be 71 * created (or, as we so wittily call it, conjured) in the parent. We iterate 72 * through this hash, creating the indicated tdesc_t nodes. For a given tdesc_t 73 * node, conjuring requires two steps - the copying of the common tdesc_t data 74 * (name, type, etc) from the child node, and the creation of links from the 75 * newly-created node to the parent equivalents of other tdesc_t nodes pointed 76 * to by node being conjured. Note that in some cases, the targets of these 77 * links will be on the md_tdtba hash themselves, and may not have been created 78 * yet. As such, we can't establish the links from these new nodes into the 79 * parent graph. We therefore conjure them with links to nodes in the *child* 80 * graph, and add pointers to the links to be created to the md_tdtbr (tdesc_t 81 * To Be Remapped) hash. For example, a POINTER tdesc_t that could not be 82 * resolved would have its &tdesc_t->t_tdesc added to md_tdtbr. 83 * 84 * 3. Creating new iidesc_t nodes (the md_iitba list) 85 * 86 * When we have completed step 2, all tdesc_t nodes have been created (or 87 * already existed) in the parent. Some of them may have incorrect links (the 88 * members of the md_tdtbr list), but they've all been created. As such, we can 89 * create all of the iidesc_t nodes, as we can attach the tdesc_t subgraph 90 * pointers correctly. We create each node, and attach the pointers to the 91 * appropriate parts of the parent tdesc_t graph. 92 * 93 * 4. Resolving newly-created tdesc_t node links (the md_tdtbr list) 94 * 95 * As in step 3, we rely on the fact that all of the tdesc_t nodes have been 96 * created. Each entry in the md_tdtbr list is a pointer to where a link into 97 * the parent will be established. As saved in the md_tdtbr list, these 98 * pointers point into the child tdesc_t subgraph. We can thus get the target 99 * type ID from the child, look at the ID mapping to determine the desired link 100 * target, and redirect the link accordingly. 101 * 102 * 5. Parent => child forward declaration resolution 103 * 104 * If entries were made in the md_fdida list in step 1, we have forward 105 * declarations in the parent that need to be resolved to their definitions 106 * re-created in step 2 from the child. Using the md_fdida list, we can locate 107 * the definition for the forward declaration, and we can redirect all inbound 108 * edges to the forward declaration node to the actual definition. 109 * 110 * A pox on the house of anyone who changes the algorithm without updating 111 * this comment. 112 */ 113 114#if HAVE_NBTOOL_CONFIG_H 115# include "nbtool_config.h" 116#endif 117 118#include <stdio.h> 119#include <strings.h> 120#include <assert.h> 121#include <pthread.h> 122 123#include "ctf_headers.h" 124#include "ctftools.h" 125#include "list.h" 126#include "alist.h" 127#include "memory.h" 128#include "traverse.h" 129 130typedef struct equiv_data equiv_data_t; 131typedef struct merge_cb_data merge_cb_data_t; 132 133/* 134 * There are two traversals in this file, for equivalency and for tdesc_t 135 * re-creation, that do not fit into the tdtraverse() framework. We have our 136 * own traversal mechanism and ops vector here for those two cases. 137 */ 138typedef struct tdesc_ops { 139 const char *name; 140 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *); 141 tdesc_t *(*conjure)(tdesc_t *, int, merge_cb_data_t *); 142} tdesc_ops_t; 143extern tdesc_ops_t tdesc_ops[]; 144 145/* 146 * The workhorse structure of tdata_t merging. Holds all lists of nodes to be 147 * processed during various phases of the merge algorithm. 148 */ 149struct merge_cb_data { 150 tdata_t *md_parent; 151 tdata_t *md_tgt; 152 alist_t *md_ta; /* Type Association */ 153 alist_t *md_fdida; /* Forward -> Definition ID Association */ 154 list_t **md_iitba; /* iidesc_t nodes To Be Added to the parent */ 155 hash_t *md_tdtba; /* tdesc_t nodes To Be Added to the parent */ 156 list_t **md_tdtbr; /* tdesc_t nodes To Be Remapped */ 157 int md_flags; 158}; /* merge_cb_data_t */ 159 160/* 161 * When we first create a tdata_t from stabs data, we will have duplicate nodes. 162 * Normal merges, however, assume that the child tdata_t is already self-unique, 163 * and for speed reasons do not attempt to self-uniquify. If this flag is set, 164 * the merge algorithm will self-uniquify by avoiding the insertion of 165 * duplicates in the md_tdtdba list. 166 */ 167#define MCD_F_SELFUNIQUIFY 0x1 168 169/* 170 * When we merge the CTF data for the modules, we don't want it to contain any 171 * data that can be found in the reference module (usually genunix). If this 172 * flag is set, we're doing a merge between the fully merged tdata_t for this 173 * module and the tdata_t for the reference module, with the data unique to this 174 * module ending up in a third tdata_t. It is this third tdata_t that will end 175 * up in the .SUNW_ctf section for the module. 176 */ 177#define MCD_F_REFMERGE 0x2 178 179/* 180 * Mapping of child type IDs to parent type IDs 181 */ 182 183static void 184add_mapping(alist_t *ta, tid_t srcid, tid_t tgtid) 185{ 186 debug(3, "Adding mapping %u <%x> => %u <%x>\n", srcid, srcid, tgtid, tgtid); 187 188 assert(!alist_find(ta, (void *)(uintptr_t)srcid, NULL)); 189 assert(srcid != 0 && tgtid != 0); 190 191 alist_add(ta, (void *)(uintptr_t)srcid, (void *)(uintptr_t)tgtid); 192} 193 194static tid_t 195get_mapping(alist_t *ta, int srcid) 196{ 197 void *ltgtid; 198 199 if (alist_find(ta, (void *)(uintptr_t)srcid, (void **)<gtid)) 200 return ((uintptr_t)ltgtid); 201 else 202 return (0); 203} 204 205/* 206 * Determining equivalence of tdesc_t subgraphs 207 */ 208 209struct equiv_data { 210 alist_t *ed_ta; 211 tdesc_t *ed_node; 212 tdesc_t *ed_tgt; 213 214 int ed_clear_mark; 215 int ed_cur_mark; 216 int ed_selfuniquify; 217}; /* equiv_data_t */ 218 219static int equiv_node(tdesc_t *, tdesc_t *, equiv_data_t *); 220 221/*ARGSUSED2*/ 222static int 223equiv_intrinsic(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused) 224{ 225 intr_t *si = stdp->t_intr; 226 intr_t *ti = ttdp->t_intr; 227 228 if (si->intr_type != ti->intr_type || 229 si->intr_signed != ti->intr_signed || 230 si->intr_offset != ti->intr_offset || 231 si->intr_nbits != ti->intr_nbits) 232 return (0); 233 234 if (si->intr_type == INTR_INT && 235 si->intr_iformat != ti->intr_iformat) 236 return (0); 237 else if (si->intr_type == INTR_REAL && 238 si->intr_fformat != ti->intr_fformat) 239 return (0); 240 241 return (1); 242} 243 244static int 245equiv_plain(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 246{ 247 return (equiv_node(stdp->t_tdesc, ttdp->t_tdesc, ed)); 248} 249 250static int 251equiv_function(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 252{ 253 fndef_t *fn1 = stdp->t_fndef, *fn2 = ttdp->t_fndef; 254 int i; 255 256 if (fn1->fn_nargs != fn2->fn_nargs || 257 fn1->fn_vargs != fn2->fn_vargs) 258 return (0); 259 260 if (!equiv_node(fn1->fn_ret, fn2->fn_ret, ed)) 261 return (0); 262 263 for (i = 0; i < (int) fn1->fn_nargs; i++) { 264 if (!equiv_node(fn1->fn_args[i], fn2->fn_args[i], ed)) 265 return (0); 266 } 267 268 return (1); 269} 270 271static int 272equiv_array(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 273{ 274 ardef_t *ar1 = stdp->t_ardef, *ar2 = ttdp->t_ardef; 275 276 if (!equiv_node(ar1->ad_contents, ar2->ad_contents, ed) || 277 !equiv_node(ar1->ad_idxtype, ar2->ad_idxtype, ed)) 278 return (0); 279 280 if (ar1->ad_nelems != ar2->ad_nelems) 281 return (0); 282 283 return (1); 284} 285 286static int 287equiv_su(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 288{ 289 mlist_t *ml1 = stdp->t_members, *ml2 = ttdp->t_members; 290 mlist_t *olm1 = NULL; 291 292 while (ml1 && ml2) { 293 if (ml1->ml_offset != ml2->ml_offset || 294 strcmp(ml1->ml_name, ml2->ml_name) != 0) 295 return (0); 296 297 /* 298 * Don't do the recursive equivalency checking more than 299 * we have to. 300 */ 301 if (olm1 == NULL || olm1->ml_type->t_id != ml1->ml_type->t_id) { 302 if (ml1->ml_size != ml2->ml_size || 303 !equiv_node(ml1->ml_type, ml2->ml_type, ed)) 304 return (0); 305 } 306 307 olm1 = ml1; 308 ml1 = ml1->ml_next; 309 ml2 = ml2->ml_next; 310 } 311 312 if (ml1 || ml2) 313 return (0); 314 315 return (1); 316} 317 318/*ARGSUSED2*/ 319static int 320equiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused) 321{ 322 elist_t *el1 = stdp->t_emem; 323 elist_t *el2 = ttdp->t_emem; 324 325 while (el1 && el2) { 326 if (el1->el_number != el2->el_number || 327 strcmp(el1->el_name, el2->el_name) != 0) 328 return (0); 329 330 el1 = el1->el_next; 331 el2 = el2->el_next; 332 } 333 334 if (el1 || el2) 335 return (0); 336 337 return (1); 338} 339 340/*ARGSUSED*/ 341static int 342equiv_assert(tdesc_t *stdp __unused, tdesc_t *ttdp __unused, equiv_data_t *ed __unused) 343{ 344 /* foul, evil, and very bad - this is a "shouldn't happen" */ 345 assert(1 == 0); 346 347 return (0); 348} 349 350static int 351fwd_equiv(tdesc_t *ctdp, tdesc_t *mtdp) 352{ 353 tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp); 354 355 return (defn->t_type == STRUCT || defn->t_type == UNION); 356} 357 358static int 359equiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed) 360{ 361 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *); 362 int mapping; 363 364 if (ctdp->t_emark > ed->ed_clear_mark || 365 mtdp->t_emark > ed->ed_clear_mark) 366 return (ctdp->t_emark == mtdp->t_emark); 367 368 /* 369 * In normal (non-self-uniquify) mode, we don't want to do equivalency 370 * checking on a subgraph that has already been checked. If a mapping 371 * has already been established for a given child node, we can simply 372 * compare the mapping for the child node with the ID of the parent 373 * node. If we are in self-uniquify mode, then we're comparing two 374 * subgraphs within the child graph, and thus need to ignore any 375 * type mappings that have been created, as they are only valid into the 376 * parent. 377 */ 378 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 && 379 mapping == mtdp->t_id && !ed->ed_selfuniquify) 380 return (1); 381 382 if (!streq(ctdp->t_name, mtdp->t_name)) 383 return (0); 384 385 if (ctdp->t_type != mtdp->t_type) { 386 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD) 387 return (fwd_equiv(ctdp, mtdp)); 388 else 389 return (0); 390 } 391 392 ctdp->t_emark = ed->ed_cur_mark; 393 mtdp->t_emark = ed->ed_cur_mark; 394 ed->ed_cur_mark++; 395 396 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL) 397 return (equiv(ctdp, mtdp, ed)); 398 399 return (1); 400} 401 402/* 403 * We perform an equivalency check on two subgraphs by traversing through them 404 * in lockstep. If a given node is equivalent in both the parent and the child, 405 * we mark it in both subgraphs, using the t_emark field, with a monotonically 406 * increasing number. If, in the course of the traversal, we reach a node that 407 * we have visited and numbered during this equivalency check, we have a cycle. 408 * If the previously-visited nodes don't have the same emark, then the edges 409 * that brought us to these nodes are not equivalent, and so the check ends. 410 * If the emarks are the same, the edges are equivalent. We then backtrack and 411 * continue the traversal. If we have exhausted all edges in the subgraph, and 412 * have not found any inequivalent nodes, then the subgraphs are equivalent. 413 */ 414static int 415equiv_cb(void *bucket, void *arg) 416{ 417 equiv_data_t *ed = arg; 418 tdesc_t *mtdp = bucket; 419 tdesc_t *ctdp = ed->ed_node; 420 421 ed->ed_clear_mark = ed->ed_cur_mark + 1; 422 ed->ed_cur_mark = ed->ed_clear_mark + 1; 423 424 if (equiv_node(ctdp, mtdp, ed)) { 425 debug(3, "equiv_node matched %d <%x> %d <%x>\n", 426 ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id); 427 ed->ed_tgt = mtdp; 428 /* matched. stop looking */ 429 return (-1); 430 } 431 432 return (0); 433} 434 435/*ARGSUSED1*/ 436static int 437map_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 438{ 439 merge_cb_data_t *mcd = private; 440 441 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0) 442 return (0); 443 444 return (1); 445} 446 447/*ARGSUSED1*/ 448static int 449map_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 450{ 451 merge_cb_data_t *mcd = private; 452 equiv_data_t ed; 453 454 ed.ed_ta = mcd->md_ta; 455 ed.ed_clear_mark = mcd->md_parent->td_curemark; 456 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 457 ed.ed_node = ctdp; 458 ed.ed_selfuniquify = 0; 459 460 debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp)); 461 462 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp, 463 equiv_cb, &ed) < 0) { 464 /* We found an equivalent node */ 465 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) { 466 int id = mcd->md_tgt->td_nextid++; 467 468 debug(3, "Creating new defn type %d <%x>\n", id, id); 469 add_mapping(mcd->md_ta, ctdp->t_id, id); 470 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt, 471 (void *)(ulong_t)id); 472 hash_add(mcd->md_tdtba, ctdp); 473 } else 474 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id); 475 476 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash, 477 equiv_cb, &ed) < 0) { 478 /* 479 * We didn't find an equivalent node by looking through the 480 * layout hash, but we somehow found it by performing an 481 * exhaustive search through the entire graph. This usually 482 * means that the "name" hash function is broken. 483 */ 484 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id, 485 tdesc_name(ctdp), ed.ed_tgt->t_id); 486 } else { 487 int id = mcd->md_tgt->td_nextid++; 488 489 debug(3, "Creating new type %d <%x>\n", id, id); 490 add_mapping(mcd->md_ta, ctdp->t_id, id); 491 hash_add(mcd->md_tdtba, ctdp); 492 } 493 494 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 495 496 return (1); 497} 498 499/*ARGSUSED1*/ 500static int 501map_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 502{ 503 merge_cb_data_t *mcd = private; 504 equiv_data_t ed; 505 506 ed.ed_ta = mcd->md_ta; 507 ed.ed_clear_mark = mcd->md_parent->td_curemark; 508 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 509 ed.ed_node = ctdp; 510 ed.ed_selfuniquify = 1; 511 ed.ed_tgt = NULL; 512 513 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) { 514 debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id, 515 ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id); 516 add_mapping(mcd->md_ta, ctdp->t_id, 517 get_mapping(mcd->md_ta, ed.ed_tgt->t_id)); 518 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba, 519 equiv_cb, &ed) < 0) { 520 /* 521 * We didn't find an equivalent node using the quick way (going 522 * through the hash normally), but we did find it by iterating 523 * through the entire hash. This usually means that the hash 524 * function is broken. 525 */ 526 aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n", 527 ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id, 528 ed.ed_tgt->t_id); 529 } else { 530 int id = mcd->md_tgt->td_nextid++; 531 532 debug(3, "Creating new type %d <%x>\n", id, id); 533 add_mapping(mcd->md_ta, ctdp->t_id, id); 534 hash_add(mcd->md_tdtba, ctdp); 535 } 536 537 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 538 539 return (1); 540} 541 542static tdtrav_cb_f map_pre[] = { 543 NULL, 544 map_td_tree_pre, /* intrinsic */ 545 map_td_tree_pre, /* pointer */ 546 map_td_tree_pre, /* array */ 547 map_td_tree_pre, /* function */ 548 map_td_tree_pre, /* struct */ 549 map_td_tree_pre, /* union */ 550 map_td_tree_pre, /* enum */ 551 map_td_tree_pre, /* forward */ 552 map_td_tree_pre, /* typedef */ 553 tdtrav_assert, /* typedef_unres */ 554 map_td_tree_pre, /* volatile */ 555 map_td_tree_pre, /* const */ 556 map_td_tree_pre /* restrict */ 557}; 558 559static tdtrav_cb_f map_post[] = { 560 NULL, 561 map_td_tree_post, /* intrinsic */ 562 map_td_tree_post, /* pointer */ 563 map_td_tree_post, /* array */ 564 map_td_tree_post, /* function */ 565 map_td_tree_post, /* struct */ 566 map_td_tree_post, /* union */ 567 map_td_tree_post, /* enum */ 568 map_td_tree_post, /* forward */ 569 map_td_tree_post, /* typedef */ 570 tdtrav_assert, /* typedef_unres */ 571 map_td_tree_post, /* volatile */ 572 map_td_tree_post, /* const */ 573 map_td_tree_post /* restrict */ 574}; 575 576static tdtrav_cb_f map_self_post[] = { 577 NULL, 578 map_td_tree_self_post, /* intrinsic */ 579 map_td_tree_self_post, /* pointer */ 580 map_td_tree_self_post, /* array */ 581 map_td_tree_self_post, /* function */ 582 map_td_tree_self_post, /* struct */ 583 map_td_tree_self_post, /* union */ 584 map_td_tree_self_post, /* enum */ 585 map_td_tree_self_post, /* forward */ 586 map_td_tree_self_post, /* typedef */ 587 tdtrav_assert, /* typedef_unres */ 588 map_td_tree_self_post, /* volatile */ 589 map_td_tree_self_post, /* const */ 590 map_td_tree_self_post /* restrict */ 591}; 592 593/* 594 * Determining equivalence of iidesc_t nodes 595 */ 596 597typedef struct iifind_data { 598 iidesc_t *iif_template; 599 alist_t *iif_ta; 600 int iif_newidx; 601 int iif_refmerge; 602} iifind_data_t; 603 604/* 605 * Check to see if this iidesc_t (node) - the current one on the list we're 606 * iterating through - matches the target one (iif->iif_template). Return -1 607 * if it matches, to stop the iteration. 608 */ 609static int 610iidesc_match(void *data, void *arg) 611{ 612 iidesc_t *node = data; 613 iifind_data_t *iif = arg; 614 int i; 615 616 if (node->ii_type != iif->iif_template->ii_type || 617 !streq(node->ii_name, iif->iif_template->ii_name) || 618 node->ii_dtype->t_id != iif->iif_newidx) 619 return (0); 620 621 if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) && 622 !streq(node->ii_owner, iif->iif_template->ii_owner)) 623 return (0); 624 625 if (node->ii_nargs != iif->iif_template->ii_nargs) 626 return (0); 627 628 for (i = 0; i < node->ii_nargs; i++) { 629 if (get_mapping(iif->iif_ta, 630 iif->iif_template->ii_args[i]->t_id) != 631 node->ii_args[i]->t_id) 632 return (0); 633 } 634 635 if (iif->iif_refmerge) { 636 switch (iif->iif_template->ii_type) { 637 case II_GFUN: 638 case II_SFUN: 639 case II_GVAR: 640 case II_SVAR: 641 debug(3, "suppressing duping of %d %s from %s\n", 642 iif->iif_template->ii_type, 643 iif->iif_template->ii_name, 644 (iif->iif_template->ii_owner ? 645 iif->iif_template->ii_owner : "NULL")); 646 return (0); 647 case II_NOT: 648 case II_PSYM: 649 case II_SOU: 650 case II_TYPE: 651 break; 652 } 653 } 654 655 return (-1); 656} 657 658static int 659merge_type_cb(void *data, void *arg) 660{ 661 iidesc_t *sii = data; 662 merge_cb_data_t *mcd = arg; 663 iifind_data_t iif; 664 tdtrav_cb_f *post; 665 666 post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post); 667 668 /* Map the tdesc nodes */ 669 (void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post, 670 mcd); 671 672 /* Map the iidesc nodes */ 673 iif.iif_template = sii; 674 iif.iif_ta = mcd->md_ta; 675 iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id); 676 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); 677 678 if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match, 679 &iif) == 1) 680 /* successfully mapped */ 681 return (1); 682 683 debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"), 684 sii->ii_type); 685 686 list_add(mcd->md_iitba, sii); 687 688 return (0); 689} 690 691static int 692remap_node(tdesc_t **tgtp, tdesc_t *oldtgt, int selftid, tdesc_t *newself, 693 merge_cb_data_t *mcd) 694{ 695 tdesc_t *tgt = NULL; 696 tdesc_t template; 697 int oldid = oldtgt->t_id; 698 699 if (oldid == selftid) { 700 *tgtp = newself; 701 return (1); 702 } 703 704 if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0) 705 aborterr("failed to get mapping for tid %d <%x>\n", oldid, oldid); 706 707 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template, 708 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) || 709 !hash_find(mcd->md_tgt->td_idhash, (void *)&template, 710 (void *)&tgt))) { 711 debug(3, "Remap couldn't find %d <%x> (from %d <%x>)\n", template.t_id, 712 template.t_id, oldid, oldid); 713 *tgtp = oldtgt; 714 list_add(mcd->md_tdtbr, tgtp); 715 return (0); 716 } 717 718 *tgtp = tgt; 719 return (1); 720} 721 722static tdesc_t * 723conjure_template(tdesc_t *old, int newselfid) 724{ 725 tdesc_t *new = xcalloc(sizeof (tdesc_t)); 726 727 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL; 728 new->t_type = old->t_type; 729 new->t_size = old->t_size; 730 new->t_id = newselfid; 731 new->t_flags = old->t_flags; 732 733 return (new); 734} 735 736/*ARGSUSED2*/ 737static tdesc_t * 738conjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 739{ 740 tdesc_t *new = conjure_template(old, newselfid); 741 742 new->t_intr = xmalloc(sizeof (intr_t)); 743 bcopy(old->t_intr, new->t_intr, sizeof (intr_t)); 744 745 return (new); 746} 747 748static tdesc_t * 749conjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 750{ 751 tdesc_t *new = conjure_template(old, newselfid); 752 753 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd); 754 755 return (new); 756} 757 758static tdesc_t * 759conjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 760{ 761 tdesc_t *new = conjure_template(old, newselfid); 762 fndef_t *nfn = xmalloc(sizeof (fndef_t)); 763 fndef_t *ofn = old->t_fndef; 764 int i; 765 766 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd); 767 768 nfn->fn_nargs = ofn->fn_nargs; 769 nfn->fn_vargs = ofn->fn_vargs; 770 771 if (nfn->fn_nargs > 0) 772 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs); 773 774 for (i = 0; i < (int) ofn->fn_nargs; i++) { 775 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id, 776 new, mcd); 777 } 778 779 new->t_fndef = nfn; 780 781 return (new); 782} 783 784static tdesc_t * 785conjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 786{ 787 tdesc_t *new = conjure_template(old, newselfid); 788 ardef_t *nar = xmalloc(sizeof (ardef_t)); 789 ardef_t *oar = old->t_ardef; 790 791 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new, 792 mcd); 793 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new, 794 mcd); 795 796 nar->ad_nelems = oar->ad_nelems; 797 798 new->t_ardef = nar; 799 800 return (new); 801} 802 803static tdesc_t * 804conjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 805{ 806 tdesc_t *new = conjure_template(old, newselfid); 807 mlist_t *omem, **nmemp; 808 809 for (omem = old->t_members, nmemp = &new->t_members; 810 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) { 811 *nmemp = xmalloc(sizeof (mlist_t)); 812 (*nmemp)->ml_offset = omem->ml_offset; 813 (*nmemp)->ml_size = omem->ml_size; 814 (*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name"); 815 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type, 816 old->t_id, new, mcd); 817 } 818 *nmemp = NULL; 819 820 return (new); 821} 822 823/*ARGSUSED2*/ 824static tdesc_t * 825conjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 826{ 827 tdesc_t *new = conjure_template(old, newselfid); 828 elist_t *oel, **nelp; 829 830 for (oel = old->t_emem, nelp = &new->t_emem; 831 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) { 832 *nelp = xmalloc(sizeof (elist_t)); 833 (*nelp)->el_name = xstrdup(oel->el_name); 834 (*nelp)->el_number = oel->el_number; 835 } 836 *nelp = NULL; 837 838 return (new); 839} 840 841/*ARGSUSED2*/ 842static tdesc_t * 843conjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 844{ 845 tdesc_t *new = conjure_template(old, newselfid); 846 847 list_add(&mcd->md_tgt->td_fwdlist, new); 848 849 return (new); 850} 851 852/*ARGSUSED*/ 853static tdesc_t * 854conjure_assert(tdesc_t *old __unused, int newselfid __unused, merge_cb_data_t *mcd __unused) 855{ 856 assert(1 == 0); 857 return (NULL); 858} 859 860static iidesc_t * 861conjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd) 862{ 863 iidesc_t *new = iidesc_dup(old); 864 int i; 865 866 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd); 867 for (i = 0; i < new->ii_nargs; i++) { 868 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL, 869 mcd); 870 } 871 872 return (new); 873} 874 875static int 876fwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private) 877{ 878 alist_t *map = private; 879 void *defn; 880 881 if (!alist_find(map, (void *)fwd, (void **)&defn)) 882 return (0); 883 884 debug(3, "Redirecting an edge to %s\n", tdesc_name(defn)); 885 886 *fwdp = defn; 887 888 return (1); 889} 890 891static tdtrav_cb_f fwd_redir_cbs[] = { 892 NULL, 893 NULL, /* intrinsic */ 894 NULL, /* pointer */ 895 NULL, /* array */ 896 NULL, /* function */ 897 NULL, /* struct */ 898 NULL, /* union */ 899 NULL, /* enum */ 900 fwd_redir, /* forward */ 901 NULL, /* typedef */ 902 tdtrav_assert, /* typedef_unres */ 903 NULL, /* volatile */ 904 NULL, /* const */ 905 NULL /* restrict */ 906}; 907 908typedef struct redir_mstr_data { 909 tdata_t *rmd_tgt; 910 alist_t *rmd_map; 911} redir_mstr_data_t; 912 913static int 914redir_mstr_fwd_cb(void *name, void *value, void *arg) 915{ 916 tdesc_t *fwd = name; 917 int defnid = (uintptr_t)value; 918 redir_mstr_data_t *rmd = arg; 919 tdesc_t template; 920 tdesc_t *defn; 921 922 template.t_id = defnid; 923 924 if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template, 925 (void *)&defn)) { 926 aborterr("Couldn't unforward %d (%s)\n", defnid, 927 tdesc_name(defn)); 928 } 929 930 debug(3, "Forward map: resolved %d to %s\n", defnid, tdesc_name(defn)); 931 932 alist_add(rmd->rmd_map, (void *)fwd, (void *)defn); 933 934 return (1); 935} 936 937static void 938redir_mstr_fwds(merge_cb_data_t *mcd) 939{ 940 redir_mstr_data_t rmd; 941 alist_t *map = alist_new(NULL, NULL); 942 943 rmd.rmd_tgt = mcd->md_tgt; 944 rmd.rmd_map = map; 945 946 if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) { 947 (void) iitraverse_hash(mcd->md_tgt->td_iihash, 948 &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map); 949 } 950 951 alist_free(map); 952} 953 954static int 955add_iitba_cb(void *data, void *private) 956{ 957 merge_cb_data_t *mcd = private; 958 iidesc_t *tba = data; 959 iidesc_t *new; 960 iifind_data_t iif; 961 int newidx; 962 963 newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id); 964 assert(newidx != -1); 965 966 (void) list_remove(mcd->md_iitba, data, NULL, NULL); 967 968 iif.iif_template = tba; 969 iif.iif_ta = mcd->md_ta; 970 iif.iif_newidx = newidx; 971 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); 972 973 if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match, 974 &iif) == 1) { 975 debug(3, "iidesc_t %s already exists\n", 976 (tba->ii_name ? tba->ii_name : "(anon)")); 977 return (1); 978 } 979 980 new = conjure_iidesc(tba, mcd); 981 hash_add(mcd->md_tgt->td_iihash, new); 982 983 return (1); 984} 985 986static int 987add_tdesc(tdesc_t *oldtdp, int newid, merge_cb_data_t *mcd) 988{ 989 tdesc_t *newtdp; 990 tdesc_t template; 991 992 template.t_id = newid; 993 assert(hash_find(mcd->md_parent->td_idhash, 994 (void *)&template, NULL) == 0); 995 996 debug(3, "trying to conjure %d %s (%d, <%x>) as %d, <%x>\n", 997 oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id, 998 oldtdp->t_id, newid, newid); 999 1000 if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid, 1001 mcd)) == NULL) 1002 /* couldn't map everything */ 1003 return (0); 1004 1005 debug(3, "succeeded\n"); 1006 1007 hash_add(mcd->md_tgt->td_idhash, newtdp); 1008 hash_add(mcd->md_tgt->td_layouthash, newtdp); 1009 1010 return (1); 1011} 1012 1013static int 1014add_tdtba_cb(void *data, void *arg) 1015{ 1016 tdesc_t *tdp = data; 1017 merge_cb_data_t *mcd = arg; 1018 int newid; 1019 int rc; 1020 1021 newid = get_mapping(mcd->md_ta, tdp->t_id); 1022 assert(newid != -1); 1023 1024 if ((rc = add_tdesc(tdp, newid, mcd))) 1025 hash_remove(mcd->md_tdtba, (void *)tdp); 1026 1027 return (rc); 1028} 1029 1030static int 1031add_tdtbr_cb(void *data, void *arg) 1032{ 1033 tdesc_t **tdpp = data; 1034 merge_cb_data_t *mcd = arg; 1035 1036 debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id); 1037 1038 if (!remap_node(tdpp, *tdpp, -1, NULL, mcd)) 1039 return (0); 1040 1041 (void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL); 1042 return (1); 1043} 1044 1045static void 1046merge_types(hash_t *src, merge_cb_data_t *mcd) 1047{ 1048 list_t *iitba = NULL; 1049 list_t *tdtbr = NULL; 1050 int iirc, tdrc; 1051 1052 mcd->md_iitba = &iitba; 1053 mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, 1054 tdesc_layoutcmp); 1055 mcd->md_tdtbr = &tdtbr; 1056 1057 (void) hash_iter(src, merge_type_cb, mcd); 1058 1059 tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, mcd); 1060 debug(3, "add_tdtba_cb added %d items\n", tdrc); 1061 1062 iirc = list_iter(*mcd->md_iitba, add_iitba_cb, mcd); 1063 debug(3, "add_iitba_cb added %d items\n", iirc); 1064 1065 assert(list_count(*mcd->md_iitba) == 0 && 1066 hash_count(mcd->md_tdtba) == 0); 1067 1068 tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, mcd); 1069 debug(3, "add_tdtbr_cb added %d items\n", tdrc); 1070 1071 if (list_count(*mcd->md_tdtbr) != 0) 1072 aborterr("Couldn't remap all nodes\n"); 1073 1074 /* 1075 * We now have an alist of master forwards and the ids of the new master 1076 * definitions for those forwards in mcd->md_fdida. By this point, 1077 * we're guaranteed that all of the master definitions referenced in 1078 * fdida have been added to the master tree. We now traverse through 1079 * the master tree, redirecting all edges inbound to forwards that have 1080 * definitions to those definitions. 1081 */ 1082 if (mcd->md_parent == mcd->md_tgt) { 1083 redir_mstr_fwds(mcd); 1084 } 1085} 1086 1087void 1088merge_into_master(tdata_t *cur, tdata_t *mstr, tdata_t *tgt, int selfuniquify) 1089{ 1090 merge_cb_data_t mcd; 1091 1092 cur->td_ref++; 1093 mstr->td_ref++; 1094 if (tgt) 1095 tgt->td_ref++; 1096 1097 assert(cur->td_ref == 1 && mstr->td_ref == 1 && 1098 (tgt == NULL || tgt->td_ref == 1)); 1099 1100 mcd.md_parent = mstr; 1101 mcd.md_tgt = (tgt ? tgt : mstr); 1102 mcd.md_ta = alist_new(NULL, NULL); 1103 mcd.md_fdida = alist_new(NULL, NULL); 1104 mcd.md_flags = 0; 1105 1106 if (selfuniquify) 1107 mcd.md_flags |= MCD_F_SELFUNIQUIFY; 1108 if (tgt) 1109 mcd.md_flags |= MCD_F_REFMERGE; 1110 1111 mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen); 1112 mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark); 1113 1114 merge_types(cur->td_iihash, &mcd); 1115 1116 if (debug_level >= 3) { 1117 debug(3, "Type association stats\n"); 1118 alist_stats(mcd.md_ta, 0); 1119 debug(3, "Layout hash stats\n"); 1120 hash_stats(mcd.md_tgt->td_layouthash, 1); 1121 } 1122 1123 alist_free(mcd.md_fdida); 1124 alist_free(mcd.md_ta); 1125 1126 cur->td_ref--; 1127 mstr->td_ref--; 1128 if (tgt) 1129 tgt->td_ref--; 1130} 1131 1132tdesc_ops_t tdesc_ops[] = { 1133 { "ERROR! BAD tdesc TYPE", NULL, NULL }, 1134 { "intrinsic", equiv_intrinsic, conjure_intrinsic }, 1135 { "pointer", equiv_plain, conjure_plain }, 1136 { "array", equiv_array, conjure_array }, 1137 { "function", equiv_function, conjure_function }, 1138 { "struct", equiv_su, conjure_su }, 1139 { "union", equiv_su, conjure_su }, 1140 { "enum", equiv_enum, conjure_enum }, 1141 { "forward", NULL, conjure_forward }, 1142 { "typedef", equiv_plain, conjure_plain }, 1143 { "typedef_unres", equiv_assert, conjure_assert }, 1144 { "volatile", equiv_plain, conjure_plain }, 1145 { "const", equiv_plain, conjure_plain }, 1146 { "restrict", equiv_plain, conjure_plain } 1147}; 1148