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 291 while (ml1 && ml2) { 292 if (ml1->ml_offset != ml2->ml_offset || 293 strcmp(ml1->ml_name, ml2->ml_name) != 0 || 294 ml1->ml_size != ml2->ml_size || 295 !equiv_node(ml1->ml_type, ml2->ml_type, ed)) 296 return (0); 297 298 ml1 = ml1->ml_next; 299 ml2 = ml2->ml_next; 300 } 301 302 if (ml1 || ml2) 303 return (0); 304 305 return (1); 306} 307 308/*ARGSUSED2*/ 309static int 310equiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused) 311{ 312 elist_t *el1 = stdp->t_emem; 313 elist_t *el2 = ttdp->t_emem; 314 315 while (el1 && el2) { 316 if (el1->el_number != el2->el_number || 317 strcmp(el1->el_name, el2->el_name) != 0) 318 return (0); 319 320 el1 = el1->el_next; 321 el2 = el2->el_next; 322 } 323 324 if (el1 || el2) 325 return (0); 326 327 return (1); 328} 329 330/*ARGSUSED*/ 331static int 332equiv_assert(tdesc_t *stdp __unused, tdesc_t *ttdp __unused, equiv_data_t *ed __unused) 333{ 334 /* foul, evil, and very bad - this is a "shouldn't happen" */ 335 assert(1 == 0); 336 337 return (0); 338} 339 340static int 341fwd_equiv(tdesc_t *ctdp, tdesc_t *mtdp) 342{ 343 tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp); 344 345 return (defn->t_type == STRUCT || defn->t_type == UNION || 346 defn->t_type == ENUM); 347} 348 349static int 350equiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed) 351{ 352 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *); 353 int mapping; 354 355 if (ctdp->t_emark > ed->ed_clear_mark && 356 mtdp->t_emark > ed->ed_clear_mark) 357 return (ctdp->t_emark == mtdp->t_emark); 358 359 /* 360 * In normal (non-self-uniquify) mode, we don't want to do equivalency 361 * checking on a subgraph that has already been checked. If a mapping 362 * has already been established for a given child node, we can simply 363 * compare the mapping for the child node with the ID of the parent 364 * node. If we are in self-uniquify mode, then we're comparing two 365 * subgraphs within the child graph, and thus need to ignore any 366 * type mappings that have been created, as they are only valid into the 367 * parent. 368 */ 369 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 && 370 mapping == mtdp->t_id && !ed->ed_selfuniquify) 371 return (1); 372 373 if (!streq(ctdp->t_name, mtdp->t_name)) 374 return (0); 375 376 if (ctdp->t_type != mtdp->t_type) { 377 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD) 378 return (fwd_equiv(ctdp, mtdp)); 379 else 380 return (0); 381 } 382 383 ctdp->t_emark = ed->ed_cur_mark; 384 mtdp->t_emark = ed->ed_cur_mark; 385 ed->ed_cur_mark++; 386 387 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL) 388 return (equiv(ctdp, mtdp, ed)); 389 390 return (1); 391} 392 393/* 394 * We perform an equivalency check on two subgraphs by traversing through them 395 * in lockstep. If a given node is equivalent in both the parent and the child, 396 * we mark it in both subgraphs, using the t_emark field, with a monotonically 397 * increasing number. If, in the course of the traversal, we reach a node that 398 * we have visited and numbered during this equivalency check, we have a cycle. 399 * If the previously-visited nodes don't have the same emark, then the edges 400 * that brought us to these nodes are not equivalent, and so the check ends. 401 * If the emarks are the same, the edges are equivalent. We then backtrack and 402 * continue the traversal. If we have exhausted all edges in the subgraph, and 403 * have not found any inequivalent nodes, then the subgraphs are equivalent. 404 */ 405static int 406equiv_cb(void *bucket, void *arg) 407{ 408 equiv_data_t *ed = arg; 409 tdesc_t *mtdp = bucket; 410 tdesc_t *ctdp = ed->ed_node; 411 412 ed->ed_clear_mark = ed->ed_cur_mark + 1; 413 ed->ed_cur_mark = ed->ed_clear_mark + 1; 414 415 if (equiv_node(ctdp, mtdp, ed)) { 416 debug(3, "equiv_node matched %d <%x> %d <%x>\n", 417 ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id); 418 ed->ed_tgt = mtdp; 419 /* matched. stop looking */ 420 return (-1); 421 } 422 423 return (0); 424} 425 426/*ARGSUSED1*/ 427static int 428map_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 429{ 430 merge_cb_data_t *mcd = private; 431 432 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0) 433 return (0); 434 435 return (1); 436} 437 438/*ARGSUSED1*/ 439static int 440map_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 441{ 442 merge_cb_data_t *mcd = private; 443 equiv_data_t ed; 444 445 ed.ed_ta = mcd->md_ta; 446 ed.ed_clear_mark = mcd->md_parent->td_curemark; 447 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 448 ed.ed_node = ctdp; 449 ed.ed_selfuniquify = 0; 450 451 debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp)); 452 453 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp, 454 equiv_cb, &ed) < 0) { 455 /* We found an equivalent node */ 456 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) { 457 int id = mcd->md_tgt->td_nextid++; 458 459 debug(3, "Creating new defn type %d <%x>\n", id, id); 460 add_mapping(mcd->md_ta, ctdp->t_id, id); 461 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt, 462 (void *)(ulong_t)id); 463 hash_add(mcd->md_tdtba, ctdp); 464 } else 465 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id); 466 467 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash, 468 equiv_cb, &ed) < 0) { 469 /* 470 * We didn't find an equivalent node by looking through the 471 * layout hash, but we somehow found it by performing an 472 * exhaustive search through the entire graph. This usually 473 * means that the "name" hash function is broken. 474 */ 475 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id, 476 tdesc_name(ctdp), ed.ed_tgt->t_id); 477 } else { 478 int id = mcd->md_tgt->td_nextid++; 479 480 debug(3, "Creating new type %d <%x>\n", id, id); 481 add_mapping(mcd->md_ta, ctdp->t_id, id); 482 hash_add(mcd->md_tdtba, ctdp); 483 } 484 485 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 486 487 return (1); 488} 489 490/*ARGSUSED1*/ 491static int 492map_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 493{ 494 merge_cb_data_t *mcd = private; 495 equiv_data_t ed; 496 497 ed.ed_ta = mcd->md_ta; 498 ed.ed_clear_mark = mcd->md_parent->td_curemark; 499 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 500 ed.ed_node = ctdp; 501 ed.ed_selfuniquify = 1; 502 ed.ed_tgt = NULL; 503 504 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) { 505 debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id, 506 ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id); 507 add_mapping(mcd->md_ta, ctdp->t_id, 508 get_mapping(mcd->md_ta, ed.ed_tgt->t_id)); 509 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba, 510 equiv_cb, &ed) < 0) { 511 /* 512 * We didn't find an equivalent node using the quick way (going 513 * through the hash normally), but we did find it by iterating 514 * through the entire hash. This usually means that the hash 515 * function is broken. 516 */ 517 aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n", 518 ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id, 519 ed.ed_tgt->t_id); 520 } else { 521 int id = mcd->md_tgt->td_nextid++; 522 523 debug(3, "Creating new type %d <%x>\n", id, id); 524 add_mapping(mcd->md_ta, ctdp->t_id, id); 525 hash_add(mcd->md_tdtba, ctdp); 526 } 527 528 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 529 530 return (1); 531} 532 533static tdtrav_cb_f map_pre[] = { 534 NULL, 535 map_td_tree_pre, /* intrinsic */ 536 map_td_tree_pre, /* pointer */ 537 map_td_tree_pre, /* reference */ 538 map_td_tree_pre, /* array */ 539 map_td_tree_pre, /* function */ 540 map_td_tree_pre, /* struct */ 541 map_td_tree_pre, /* union */ 542 map_td_tree_pre, /* class */ 543 map_td_tree_pre, /* enum */ 544 map_td_tree_pre, /* forward */ 545 map_td_tree_pre, /* typedef */ 546 tdtrav_assert, /* typedef_unres */ 547 map_td_tree_pre, /* volatile */ 548 map_td_tree_pre, /* const */ 549 map_td_tree_pre /* restrict */ 550}; 551 552static tdtrav_cb_f map_post[] = { 553 NULL, 554 map_td_tree_post, /* intrinsic */ 555 map_td_tree_post, /* pointer */ 556 map_td_tree_post, /* reference */ 557 map_td_tree_post, /* array */ 558 map_td_tree_post, /* function */ 559 map_td_tree_post, /* struct */ 560 map_td_tree_post, /* union */ 561 map_td_tree_post, /* class */ 562 map_td_tree_post, /* enum */ 563 map_td_tree_post, /* forward */ 564 map_td_tree_post, /* typedef */ 565 tdtrav_assert, /* typedef_unres */ 566 map_td_tree_post, /* volatile */ 567 map_td_tree_post, /* const */ 568 map_td_tree_post /* restrict */ 569}; 570 571static tdtrav_cb_f map_self_post[] = { 572 NULL, 573 map_td_tree_self_post, /* intrinsic */ 574 map_td_tree_self_post, /* pointer */ 575 map_td_tree_self_post, /* reference */ 576 map_td_tree_self_post, /* array */ 577 map_td_tree_self_post, /* function */ 578 map_td_tree_self_post, /* struct */ 579 map_td_tree_self_post, /* union */ 580 map_td_tree_self_post, /* class */ 581 map_td_tree_self_post, /* enum */ 582 map_td_tree_self_post, /* forward */ 583 map_td_tree_self_post, /* typedef */ 584 tdtrav_assert, /* typedef_unres */ 585 map_td_tree_self_post, /* volatile */ 586 map_td_tree_self_post, /* const */ 587 map_td_tree_self_post /* restrict */ 588}; 589 590/* 591 * Determining equivalence of iidesc_t nodes 592 */ 593 594typedef struct iifind_data { 595 iidesc_t *iif_template; 596 alist_t *iif_ta; 597 int iif_newidx; 598 int iif_refmerge; 599} iifind_data_t; 600 601/* 602 * Check to see if this iidesc_t (node) - the current one on the list we're 603 * iterating through - matches the target one (iif->iif_template). Return -1 604 * if it matches, to stop the iteration. 605 */ 606static int 607iidesc_match(void *data, void *arg) 608{ 609 iidesc_t *node = data; 610 iifind_data_t *iif = arg; 611 int i; 612 613 if (node->ii_type != iif->iif_template->ii_type || 614 !streq(node->ii_name, iif->iif_template->ii_name) || 615 node->ii_dtype->t_id != iif->iif_newidx) 616 return (0); 617 618 if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) && 619 !streq(node->ii_owner, iif->iif_template->ii_owner)) 620 return (0); 621 622 if (node->ii_nargs != iif->iif_template->ii_nargs) 623 return (0); 624 625 for (i = 0; i < node->ii_nargs; i++) { 626 if (get_mapping(iif->iif_ta, 627 iif->iif_template->ii_args[i]->t_id) != 628 node->ii_args[i]->t_id) 629 return (0); 630 } 631 632 if (iif->iif_refmerge) { 633 switch (iif->iif_template->ii_type) { 634 case II_GFUN: 635 case II_SFUN: 636 case II_GVAR: 637 case II_SVAR: 638 debug(3, "suppressing duping of %d %s from %s\n", 639 iif->iif_template->ii_type, 640 iif->iif_template->ii_name, 641 (iif->iif_template->ii_owner ? 642 iif->iif_template->ii_owner : "NULL")); 643 return (0); 644 case II_NOT: 645 case II_PSYM: 646 case II_SOU: 647 case II_TYPE: 648 break; 649 } 650 } 651 652 return (-1); 653} 654 655static int 656merge_type_cb(void *data, void *arg) 657{ 658 iidesc_t *sii = data; 659 merge_cb_data_t *mcd = arg; 660 iifind_data_t iif; 661 tdtrav_cb_f *post; 662 663 post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post); 664 665 /* Map the tdesc nodes */ 666 (void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post, 667 mcd); 668 669 /* Map the iidesc nodes */ 670 iif.iif_template = sii; 671 iif.iif_ta = mcd->md_ta; 672 iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id); 673 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); 674 675 if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match, 676 &iif) == 1) 677 /* successfully mapped */ 678 return (1); 679 680 debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"), 681 sii->ii_type); 682 683 list_add(mcd->md_iitba, sii); 684 685 return (0); 686} 687 688static int 689remap_node(tdesc_t **tgtp, tdesc_t *oldtgt, int selftid, tdesc_t *newself, 690 merge_cb_data_t *mcd) 691{ 692 tdesc_t *tgt = NULL; 693 tdesc_t template; 694 int oldid = oldtgt->t_id; 695 696 if (oldid == selftid) { 697 *tgtp = newself; 698 return (1); 699 } 700 701 if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0) 702 aborterr("failed to get mapping for tid %d (%s) <%x>\n", oldid, 703 oldtgt->t_name, oldid); 704 705 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template, 706 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) || 707 !hash_find(mcd->md_tgt->td_idhash, (void *)&template, 708 (void *)&tgt))) { 709 debug(3, "Remap couldn't find %d <%x> (from %d <%x>)\n", template.t_id, 710 template.t_id, oldid, oldid); 711 *tgtp = oldtgt; 712 list_add(mcd->md_tdtbr, tgtp); 713 return (0); 714 } 715 716 *tgtp = tgt; 717 return (1); 718} 719 720static tdesc_t * 721conjure_template(tdesc_t *old, int newselfid) 722{ 723 tdesc_t *new = xcalloc(sizeof (tdesc_t)); 724 725 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL; 726 new->t_type = old->t_type; 727 new->t_size = old->t_size; 728 new->t_id = newselfid; 729 new->t_flags = old->t_flags; 730 731 return (new); 732} 733 734/*ARGSUSED2*/ 735static tdesc_t * 736conjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 737{ 738 tdesc_t *new = conjure_template(old, newselfid); 739 740 new->t_intr = xmalloc(sizeof (intr_t)); 741 bcopy(old->t_intr, new->t_intr, sizeof (intr_t)); 742 743 return (new); 744} 745 746static tdesc_t * 747conjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 748{ 749 tdesc_t *new = conjure_template(old, newselfid); 750 751 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd); 752 753 return (new); 754} 755 756static tdesc_t * 757conjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 758{ 759 tdesc_t *new = conjure_template(old, newselfid); 760 fndef_t *nfn = xmalloc(sizeof (fndef_t)); 761 fndef_t *ofn = old->t_fndef; 762 int i; 763 764 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd); 765 766 nfn->fn_nargs = ofn->fn_nargs; 767 nfn->fn_vargs = ofn->fn_vargs; 768 769 if (nfn->fn_nargs > 0) 770 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs); 771 772 for (i = 0; i < (int) ofn->fn_nargs; i++) { 773 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id, 774 new, mcd); 775 } 776 777 new->t_fndef = nfn; 778 779 return (new); 780} 781 782static tdesc_t * 783conjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 784{ 785 tdesc_t *new = conjure_template(old, newselfid); 786 ardef_t *nar = xmalloc(sizeof (ardef_t)); 787 ardef_t *oar = old->t_ardef; 788 789 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new, 790 mcd); 791 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new, 792 mcd); 793 794 nar->ad_nelems = oar->ad_nelems; 795 796 new->t_ardef = nar; 797 798 return (new); 799} 800 801static tdesc_t * 802conjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 803{ 804 tdesc_t *new = conjure_template(old, newselfid); 805 mlist_t *omem, **nmemp; 806 807 for (omem = old->t_members, nmemp = &new->t_members; 808 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) { 809 *nmemp = xmalloc(sizeof (mlist_t)); 810 (*nmemp)->ml_offset = omem->ml_offset; 811 (*nmemp)->ml_size = omem->ml_size; 812 (*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name"); 813 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type, 814 old->t_id, new, mcd); 815 } 816 *nmemp = NULL; 817 818 return (new); 819} 820 821/*ARGSUSED2*/ 822static tdesc_t * 823conjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 824{ 825 tdesc_t *new = conjure_template(old, newselfid); 826 elist_t *oel, **nelp; 827 828 for (oel = old->t_emem, nelp = &new->t_emem; 829 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) { 830 *nelp = xmalloc(sizeof (elist_t)); 831 (*nelp)->el_name = xstrdup(oel->el_name); 832 (*nelp)->el_number = oel->el_number; 833 } 834 *nelp = NULL; 835 836 return (new); 837} 838 839/*ARGSUSED2*/ 840static tdesc_t * 841conjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 842{ 843 tdesc_t *new = conjure_template(old, newselfid); 844 845 list_add(&mcd->md_tgt->td_fwdlist, new); 846 847 return (new); 848} 849 850/*ARGSUSED*/ 851static tdesc_t * 852conjure_assert(tdesc_t *old __unused, int newselfid __unused, merge_cb_data_t *mcd __unused) 853{ 854 assert(1 == 0); 855 return (NULL); 856} 857 858static iidesc_t * 859conjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd) 860{ 861 iidesc_t *new = iidesc_dup(old); 862 int i; 863 864 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd); 865 for (i = 0; i < new->ii_nargs; i++) { 866 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL, 867 mcd); 868 } 869 870 return (new); 871} 872 873static int 874fwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private) 875{ 876 alist_t *map = private; 877 void *defn; 878 879 if (!alist_find(map, (void *)fwd, (void **)&defn)) 880 return (0); 881 882 debug(3, "Redirecting an edge to %s\n", tdesc_name(defn)); 883 884 *fwdp = defn; 885 886 return (1); 887} 888 889static tdtrav_cb_f fwd_redir_cbs[] = { 890 NULL, 891 NULL, /* intrinsic */ 892 NULL, /* pointer */ 893 NULL, /* reference */ 894 NULL, /* array */ 895 NULL, /* function */ 896 NULL, /* struct */ 897 NULL, /* union */ 898 NULL, /* class */ 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 { "reference", equiv_plain, conjure_plain }, 1137 { "array", equiv_array, conjure_array }, 1138 { "function", equiv_function, conjure_function }, 1139 { "struct", equiv_su, conjure_su }, 1140 { "union", equiv_su, conjure_su }, 1141 { "class", equiv_su, conjure_su }, 1142 { "enum", equiv_enum, conjure_enum }, 1143 { "forward", NULL, conjure_forward }, 1144 { "typedef", equiv_plain, conjure_plain }, 1145 { "typedef_unres", equiv_assert, conjure_assert }, 1146 { "volatile", equiv_plain, conjure_plain }, 1147 { "const", equiv_plain, conjure_plain }, 1148 { "restrict", equiv_plain, conjure_plain } 1149}; 1150