merge.c revision 305106
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#include <stdio.h> 115#include <strings.h> 116#include <assert.h> 117#include <pthread.h> 118 119#include "ctf_headers.h" 120#include "ctftools.h" 121#include "list.h" 122#include "alist.h" 123#include "memory.h" 124#include "traverse.h" 125 126typedef struct equiv_data equiv_data_t; 127typedef struct merge_cb_data merge_cb_data_t; 128 129/* 130 * There are two traversals in this file, for equivalency and for tdesc_t 131 * re-creation, that do not fit into the tdtraverse() framework. We have our 132 * own traversal mechanism and ops vector here for those two cases. 133 */ 134typedef struct tdesc_ops { 135 const char *name; 136 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *); 137 tdesc_t *(*conjure)(tdesc_t *, int, merge_cb_data_t *); 138} tdesc_ops_t; 139extern tdesc_ops_t tdesc_ops[]; 140 141/* 142 * The workhorse structure of tdata_t merging. Holds all lists of nodes to be 143 * processed during various phases of the merge algorithm. 144 */ 145struct merge_cb_data { 146 tdata_t *md_parent; 147 tdata_t *md_tgt; 148 alist_t *md_ta; /* Type Association */ 149 alist_t *md_fdida; /* Forward -> Definition ID Association */ 150 list_t **md_iitba; /* iidesc_t nodes To Be Added to the parent */ 151 hash_t *md_tdtba; /* tdesc_t nodes To Be Added to the parent */ 152 list_t **md_tdtbr; /* tdesc_t nodes To Be Remapped */ 153 int md_flags; 154}; /* merge_cb_data_t */ 155 156/* 157 * When we first create a tdata_t from stabs data, we will have duplicate nodes. 158 * Normal merges, however, assume that the child tdata_t is already self-unique, 159 * and for speed reasons do not attempt to self-uniquify. If this flag is set, 160 * the merge algorithm will self-uniquify by avoiding the insertion of 161 * duplicates in the md_tdtdba list. 162 */ 163#define MCD_F_SELFUNIQUIFY 0x1 164 165/* 166 * When we merge the CTF data for the modules, we don't want it to contain any 167 * data that can be found in the reference module (usually genunix). If this 168 * flag is set, we're doing a merge between the fully merged tdata_t for this 169 * module and the tdata_t for the reference module, with the data unique to this 170 * module ending up in a third tdata_t. It is this third tdata_t that will end 171 * up in the .SUNW_ctf section for the module. 172 */ 173#define MCD_F_REFMERGE 0x2 174 175/* 176 * Mapping of child type IDs to parent type IDs 177 */ 178 179static void 180add_mapping(alist_t *ta, tid_t srcid, tid_t tgtid) 181{ 182 debug(3, "Adding mapping %u <%x> => %u <%x>\n", srcid, srcid, tgtid, tgtid); 183 184 assert(!alist_find(ta, (void *)(uintptr_t)srcid, NULL)); 185 assert(srcid != 0 && tgtid != 0); 186 187 alist_add(ta, (void *)(uintptr_t)srcid, (void *)(uintptr_t)tgtid); 188} 189 190static tid_t 191get_mapping(alist_t *ta, int srcid) 192{ 193 void *ltgtid; 194 195 if (alist_find(ta, (void *)(uintptr_t)srcid, (void **)<gtid)) 196 return ((uintptr_t)ltgtid); 197 else 198 return (0); 199} 200 201/* 202 * Determining equivalence of tdesc_t subgraphs 203 */ 204 205struct equiv_data { 206 alist_t *ed_ta; 207 tdesc_t *ed_node; 208 tdesc_t *ed_tgt; 209 210 int ed_clear_mark; 211 int ed_cur_mark; 212 int ed_selfuniquify; 213}; /* equiv_data_t */ 214 215static int equiv_node(tdesc_t *, tdesc_t *, equiv_data_t *); 216 217/*ARGSUSED2*/ 218static int 219equiv_intrinsic(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused) 220{ 221 intr_t *si = stdp->t_intr; 222 intr_t *ti = ttdp->t_intr; 223 224 if (si->intr_type != ti->intr_type || 225 si->intr_signed != ti->intr_signed || 226 si->intr_offset != ti->intr_offset || 227 si->intr_nbits != ti->intr_nbits) 228 return (0); 229 230 if (si->intr_type == INTR_INT && 231 si->intr_iformat != ti->intr_iformat) 232 return (0); 233 else if (si->intr_type == INTR_REAL && 234 si->intr_fformat != ti->intr_fformat) 235 return (0); 236 237 return (1); 238} 239 240static int 241equiv_plain(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 242{ 243 return (equiv_node(stdp->t_tdesc, ttdp->t_tdesc, ed)); 244} 245 246static int 247equiv_function(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 248{ 249 fndef_t *fn1 = stdp->t_fndef, *fn2 = ttdp->t_fndef; 250 int i; 251 252 if (fn1->fn_nargs != fn2->fn_nargs || 253 fn1->fn_vargs != fn2->fn_vargs) 254 return (0); 255 256 if (!equiv_node(fn1->fn_ret, fn2->fn_ret, ed)) 257 return (0); 258 259 for (i = 0; i < (int) fn1->fn_nargs; i++) { 260 if (!equiv_node(fn1->fn_args[i], fn2->fn_args[i], ed)) 261 return (0); 262 } 263 264 return (1); 265} 266 267static int 268equiv_array(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 269{ 270 ardef_t *ar1 = stdp->t_ardef, *ar2 = ttdp->t_ardef; 271 272 if (!equiv_node(ar1->ad_contents, ar2->ad_contents, ed) || 273 !equiv_node(ar1->ad_idxtype, ar2->ad_idxtype, ed)) 274 return (0); 275 276 if (ar1->ad_nelems != ar2->ad_nelems) 277 return (0); 278 279 return (1); 280} 281 282static int 283equiv_su(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed) 284{ 285 mlist_t *ml1 = stdp->t_members, *ml2 = ttdp->t_members; 286 mlist_t *olm1 = NULL; 287 288 while (ml1 && ml2) { 289 if (ml1->ml_offset != ml2->ml_offset || 290 strcmp(ml1->ml_name, ml2->ml_name) != 0) 291 return (0); 292 293 /* 294 * Don't do the recursive equivalency checking more than 295 * we have to. 296 */ 297 if (olm1 == NULL || olm1->ml_type->t_id != ml1->ml_type->t_id) { 298 if (ml1->ml_size != ml2->ml_size || 299 !equiv_node(ml1->ml_type, ml2->ml_type, ed)) 300 return (0); 301 } 302 303 olm1 = ml1; 304 ml1 = ml1->ml_next; 305 ml2 = ml2->ml_next; 306 } 307 308 if (ml1 || ml2) 309 return (0); 310 311 return (1); 312} 313 314/*ARGSUSED2*/ 315static int 316equiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused) 317{ 318 elist_t *el1 = stdp->t_emem; 319 elist_t *el2 = ttdp->t_emem; 320 321 while (el1 && el2) { 322 if (el1->el_number != el2->el_number || 323 strcmp(el1->el_name, el2->el_name) != 0) 324 return (0); 325 326 el1 = el1->el_next; 327 el2 = el2->el_next; 328 } 329 330 if (el1 || el2) 331 return (0); 332 333 return (1); 334} 335 336/*ARGSUSED*/ 337static int 338equiv_assert(tdesc_t *stdp __unused, tdesc_t *ttdp __unused, equiv_data_t *ed __unused) 339{ 340 /* foul, evil, and very bad - this is a "shouldn't happen" */ 341 assert(1 == 0); 342 343 return (0); 344} 345 346static int 347fwd_equiv(tdesc_t *ctdp, tdesc_t *mtdp) 348{ 349 tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp); 350 351 return (defn->t_type == STRUCT || defn->t_type == UNION || 352 defn->t_type == ENUM); 353} 354 355static int 356equiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed) 357{ 358 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *); 359 int mapping; 360 361 if (ctdp->t_emark > ed->ed_clear_mark && 362 mtdp->t_emark > ed->ed_clear_mark) 363 return (ctdp->t_emark == mtdp->t_emark); 364 365 /* 366 * In normal (non-self-uniquify) mode, we don't want to do equivalency 367 * checking on a subgraph that has already been checked. If a mapping 368 * has already been established for a given child node, we can simply 369 * compare the mapping for the child node with the ID of the parent 370 * node. If we are in self-uniquify mode, then we're comparing two 371 * subgraphs within the child graph, and thus need to ignore any 372 * type mappings that have been created, as they are only valid into the 373 * parent. 374 */ 375 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 && 376 mapping == mtdp->t_id && !ed->ed_selfuniquify) 377 return (1); 378 379 if (!streq(ctdp->t_name, mtdp->t_name)) 380 return (0); 381 382 if (ctdp->t_type != mtdp->t_type) { 383 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD) 384 return (fwd_equiv(ctdp, mtdp)); 385 else 386 return (0); 387 } 388 389 ctdp->t_emark = ed->ed_cur_mark; 390 mtdp->t_emark = ed->ed_cur_mark; 391 ed->ed_cur_mark++; 392 393 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL) 394 return (equiv(ctdp, mtdp, ed)); 395 396 return (1); 397} 398 399/* 400 * We perform an equivalency check on two subgraphs by traversing through them 401 * in lockstep. If a given node is equivalent in both the parent and the child, 402 * we mark it in both subgraphs, using the t_emark field, with a monotonically 403 * increasing number. If, in the course of the traversal, we reach a node that 404 * we have visited and numbered during this equivalency check, we have a cycle. 405 * If the previously-visited nodes don't have the same emark, then the edges 406 * that brought us to these nodes are not equivalent, and so the check ends. 407 * If the emarks are the same, the edges are equivalent. We then backtrack and 408 * continue the traversal. If we have exhausted all edges in the subgraph, and 409 * have not found any inequivalent nodes, then the subgraphs are equivalent. 410 */ 411static int 412equiv_cb(void *bucket, void *arg) 413{ 414 equiv_data_t *ed = arg; 415 tdesc_t *mtdp = bucket; 416 tdesc_t *ctdp = ed->ed_node; 417 418 ed->ed_clear_mark = ed->ed_cur_mark + 1; 419 ed->ed_cur_mark = ed->ed_clear_mark + 1; 420 421 if (equiv_node(ctdp, mtdp, ed)) { 422 debug(3, "equiv_node matched %d <%x> %d <%x>\n", 423 ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id); 424 ed->ed_tgt = mtdp; 425 /* matched. stop looking */ 426 return (-1); 427 } 428 429 return (0); 430} 431 432/*ARGSUSED1*/ 433static int 434map_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 435{ 436 merge_cb_data_t *mcd = private; 437 438 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0) 439 return (0); 440 441 return (1); 442} 443 444/*ARGSUSED1*/ 445static int 446map_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 447{ 448 merge_cb_data_t *mcd = private; 449 equiv_data_t ed; 450 451 ed.ed_ta = mcd->md_ta; 452 ed.ed_clear_mark = mcd->md_parent->td_curemark; 453 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 454 ed.ed_node = ctdp; 455 ed.ed_selfuniquify = 0; 456 457 debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp)); 458 459 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp, 460 equiv_cb, &ed) < 0) { 461 /* We found an equivalent node */ 462 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) { 463 int id = mcd->md_tgt->td_nextid++; 464 465 debug(3, "Creating new defn type %d <%x>\n", id, id); 466 add_mapping(mcd->md_ta, ctdp->t_id, id); 467 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt, 468 (void *)(ulong_t)id); 469 hash_add(mcd->md_tdtba, ctdp); 470 } else 471 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id); 472 473 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash, 474 equiv_cb, &ed) < 0) { 475 /* 476 * We didn't find an equivalent node by looking through the 477 * layout hash, but we somehow found it by performing an 478 * exhaustive search through the entire graph. This usually 479 * means that the "name" hash function is broken. 480 */ 481 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id, 482 tdesc_name(ctdp), ed.ed_tgt->t_id); 483 } else { 484 int id = mcd->md_tgt->td_nextid++; 485 486 debug(3, "Creating new type %d <%x>\n", id, id); 487 add_mapping(mcd->md_ta, ctdp->t_id, id); 488 hash_add(mcd->md_tdtba, ctdp); 489 } 490 491 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 492 493 return (1); 494} 495 496/*ARGSUSED1*/ 497static int 498map_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 499{ 500 merge_cb_data_t *mcd = private; 501 equiv_data_t ed; 502 503 ed.ed_ta = mcd->md_ta; 504 ed.ed_clear_mark = mcd->md_parent->td_curemark; 505 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; 506 ed.ed_node = ctdp; 507 ed.ed_selfuniquify = 1; 508 ed.ed_tgt = NULL; 509 510 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) { 511 debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id, 512 ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id); 513 add_mapping(mcd->md_ta, ctdp->t_id, 514 get_mapping(mcd->md_ta, ed.ed_tgt->t_id)); 515 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba, 516 equiv_cb, &ed) < 0) { 517 /* 518 * We didn't find an equivalent node using the quick way (going 519 * through the hash normally), but we did find it by iterating 520 * through the entire hash. This usually means that the hash 521 * function is broken. 522 */ 523 aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n", 524 ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id, 525 ed.ed_tgt->t_id); 526 } else { 527 int id = mcd->md_tgt->td_nextid++; 528 529 debug(3, "Creating new type %d <%x>\n", id, id); 530 add_mapping(mcd->md_ta, ctdp->t_id, id); 531 hash_add(mcd->md_tdtba, ctdp); 532 } 533 534 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; 535 536 return (1); 537} 538 539static tdtrav_cb_f map_pre[] = { 540 NULL, 541 map_td_tree_pre, /* intrinsic */ 542 map_td_tree_pre, /* pointer */ 543 map_td_tree_pre, /* array */ 544 map_td_tree_pre, /* function */ 545 map_td_tree_pre, /* struct */ 546 map_td_tree_pre, /* union */ 547 map_td_tree_pre, /* enum */ 548 map_td_tree_pre, /* forward */ 549 map_td_tree_pre, /* typedef */ 550 tdtrav_assert, /* typedef_unres */ 551 map_td_tree_pre, /* volatile */ 552 map_td_tree_pre, /* const */ 553 map_td_tree_pre /* restrict */ 554}; 555 556static tdtrav_cb_f map_post[] = { 557 NULL, 558 map_td_tree_post, /* intrinsic */ 559 map_td_tree_post, /* pointer */ 560 map_td_tree_post, /* array */ 561 map_td_tree_post, /* function */ 562 map_td_tree_post, /* struct */ 563 map_td_tree_post, /* union */ 564 map_td_tree_post, /* enum */ 565 map_td_tree_post, /* forward */ 566 map_td_tree_post, /* typedef */ 567 tdtrav_assert, /* typedef_unres */ 568 map_td_tree_post, /* volatile */ 569 map_td_tree_post, /* const */ 570 map_td_tree_post /* restrict */ 571}; 572 573static tdtrav_cb_f map_self_post[] = { 574 NULL, 575 map_td_tree_self_post, /* intrinsic */ 576 map_td_tree_self_post, /* pointer */ 577 map_td_tree_self_post, /* array */ 578 map_td_tree_self_post, /* function */ 579 map_td_tree_self_post, /* struct */ 580 map_td_tree_self_post, /* union */ 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 <%x>\n", oldid, oldid); 703 704 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template, 705 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) || 706 !hash_find(mcd->md_tgt->td_idhash, (void *)&template, 707 (void *)&tgt))) { 708 debug(3, "Remap couldn't find %d <%x> (from %d <%x>)\n", template.t_id, 709 template.t_id, oldid, oldid); 710 *tgtp = oldtgt; 711 list_add(mcd->md_tdtbr, tgtp); 712 return (0); 713 } 714 715 *tgtp = tgt; 716 return (1); 717} 718 719static tdesc_t * 720conjure_template(tdesc_t *old, int newselfid) 721{ 722 tdesc_t *new = xcalloc(sizeof (tdesc_t)); 723 724 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL; 725 new->t_type = old->t_type; 726 new->t_size = old->t_size; 727 new->t_id = newselfid; 728 new->t_flags = old->t_flags; 729 730 return (new); 731} 732 733/*ARGSUSED2*/ 734static tdesc_t * 735conjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 736{ 737 tdesc_t *new = conjure_template(old, newselfid); 738 739 new->t_intr = xmalloc(sizeof (intr_t)); 740 bcopy(old->t_intr, new->t_intr, sizeof (intr_t)); 741 742 return (new); 743} 744 745static tdesc_t * 746conjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 747{ 748 tdesc_t *new = conjure_template(old, newselfid); 749 750 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd); 751 752 return (new); 753} 754 755static tdesc_t * 756conjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 757{ 758 tdesc_t *new = conjure_template(old, newselfid); 759 fndef_t *nfn = xmalloc(sizeof (fndef_t)); 760 fndef_t *ofn = old->t_fndef; 761 int i; 762 763 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd); 764 765 nfn->fn_nargs = ofn->fn_nargs; 766 nfn->fn_vargs = ofn->fn_vargs; 767 768 if (nfn->fn_nargs > 0) 769 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs); 770 771 for (i = 0; i < (int) ofn->fn_nargs; i++) { 772 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id, 773 new, mcd); 774 } 775 776 new->t_fndef = nfn; 777 778 return (new); 779} 780 781static tdesc_t * 782conjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 783{ 784 tdesc_t *new = conjure_template(old, newselfid); 785 ardef_t *nar = xmalloc(sizeof (ardef_t)); 786 ardef_t *oar = old->t_ardef; 787 788 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new, 789 mcd); 790 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new, 791 mcd); 792 793 nar->ad_nelems = oar->ad_nelems; 794 795 new->t_ardef = nar; 796 797 return (new); 798} 799 800static tdesc_t * 801conjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 802{ 803 tdesc_t *new = conjure_template(old, newselfid); 804 mlist_t *omem, **nmemp; 805 806 for (omem = old->t_members, nmemp = &new->t_members; 807 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) { 808 *nmemp = xmalloc(sizeof (mlist_t)); 809 (*nmemp)->ml_offset = omem->ml_offset; 810 (*nmemp)->ml_size = omem->ml_size; 811 (*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name"); 812 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type, 813 old->t_id, new, mcd); 814 } 815 *nmemp = NULL; 816 817 return (new); 818} 819 820/*ARGSUSED2*/ 821static tdesc_t * 822conjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused) 823{ 824 tdesc_t *new = conjure_template(old, newselfid); 825 elist_t *oel, **nelp; 826 827 for (oel = old->t_emem, nelp = &new->t_emem; 828 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) { 829 *nelp = xmalloc(sizeof (elist_t)); 830 (*nelp)->el_name = xstrdup(oel->el_name); 831 (*nelp)->el_number = oel->el_number; 832 } 833 *nelp = NULL; 834 835 return (new); 836} 837 838/*ARGSUSED2*/ 839static tdesc_t * 840conjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd) 841{ 842 tdesc_t *new = conjure_template(old, newselfid); 843 844 list_add(&mcd->md_tgt->td_fwdlist, new); 845 846 return (new); 847} 848 849/*ARGSUSED*/ 850static tdesc_t * 851conjure_assert(tdesc_t *old __unused, int newselfid __unused, merge_cb_data_t *mcd __unused) 852{ 853 assert(1 == 0); 854 return (NULL); 855} 856 857static iidesc_t * 858conjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd) 859{ 860 iidesc_t *new = iidesc_dup(old); 861 int i; 862 863 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd); 864 for (i = 0; i < new->ii_nargs; i++) { 865 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL, 866 mcd); 867 } 868 869 return (new); 870} 871 872static int 873fwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private) 874{ 875 alist_t *map = private; 876 void *defn; 877 878 if (!alist_find(map, (void *)fwd, (void **)&defn)) 879 return (0); 880 881 debug(3, "Redirecting an edge to %s\n", tdesc_name(defn)); 882 883 *fwdp = defn; 884 885 return (1); 886} 887 888static tdtrav_cb_f fwd_redir_cbs[] = { 889 NULL, 890 NULL, /* intrinsic */ 891 NULL, /* pointer */ 892 NULL, /* array */ 893 NULL, /* function */ 894 NULL, /* struct */ 895 NULL, /* union */ 896 NULL, /* enum */ 897 fwd_redir, /* forward */ 898 NULL, /* typedef */ 899 tdtrav_assert, /* typedef_unres */ 900 NULL, /* volatile */ 901 NULL, /* const */ 902 NULL /* restrict */ 903}; 904 905typedef struct redir_mstr_data { 906 tdata_t *rmd_tgt; 907 alist_t *rmd_map; 908} redir_mstr_data_t; 909 910static int 911redir_mstr_fwd_cb(void *name, void *value, void *arg) 912{ 913 tdesc_t *fwd = name; 914 int defnid = (uintptr_t)value; 915 redir_mstr_data_t *rmd = arg; 916 tdesc_t template; 917 tdesc_t *defn; 918 919 template.t_id = defnid; 920 921 if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template, 922 (void *)&defn)) { 923 aborterr("Couldn't unforward %d (%s)\n", defnid, 924 tdesc_name(defn)); 925 } 926 927 debug(3, "Forward map: resolved %d to %s\n", defnid, tdesc_name(defn)); 928 929 alist_add(rmd->rmd_map, (void *)fwd, (void *)defn); 930 931 return (1); 932} 933 934static void 935redir_mstr_fwds(merge_cb_data_t *mcd) 936{ 937 redir_mstr_data_t rmd; 938 alist_t *map = alist_new(NULL, NULL); 939 940 rmd.rmd_tgt = mcd->md_tgt; 941 rmd.rmd_map = map; 942 943 if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) { 944 (void) iitraverse_hash(mcd->md_tgt->td_iihash, 945 &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map); 946 } 947 948 alist_free(map); 949} 950 951static int 952add_iitba_cb(void *data, void *private) 953{ 954 merge_cb_data_t *mcd = private; 955 iidesc_t *tba = data; 956 iidesc_t *new; 957 iifind_data_t iif; 958 int newidx; 959 960 newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id); 961 assert(newidx != -1); 962 963 (void) list_remove(mcd->md_iitba, data, NULL, NULL); 964 965 iif.iif_template = tba; 966 iif.iif_ta = mcd->md_ta; 967 iif.iif_newidx = newidx; 968 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); 969 970 if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match, 971 &iif) == 1) { 972 debug(3, "iidesc_t %s already exists\n", 973 (tba->ii_name ? tba->ii_name : "(anon)")); 974 return (1); 975 } 976 977 new = conjure_iidesc(tba, mcd); 978 hash_add(mcd->md_tgt->td_iihash, new); 979 980 return (1); 981} 982 983static int 984add_tdesc(tdesc_t *oldtdp, int newid, merge_cb_data_t *mcd) 985{ 986 tdesc_t *newtdp; 987 tdesc_t template; 988 989 template.t_id = newid; 990 assert(hash_find(mcd->md_parent->td_idhash, 991 (void *)&template, NULL) == 0); 992 993 debug(3, "trying to conjure %d %s (%d, <%x>) as %d, <%x>\n", 994 oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id, 995 oldtdp->t_id, newid, newid); 996 997 if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid, 998 mcd)) == NULL) 999 /* couldn't map everything */ 1000 return (0); 1001 1002 debug(3, "succeeded\n"); 1003 1004 hash_add(mcd->md_tgt->td_idhash, newtdp); 1005 hash_add(mcd->md_tgt->td_layouthash, newtdp); 1006 1007 return (1); 1008} 1009 1010static int 1011add_tdtba_cb(void *data, void *arg) 1012{ 1013 tdesc_t *tdp = data; 1014 merge_cb_data_t *mcd = arg; 1015 int newid; 1016 int rc; 1017 1018 newid = get_mapping(mcd->md_ta, tdp->t_id); 1019 assert(newid != -1); 1020 1021 if ((rc = add_tdesc(tdp, newid, mcd))) 1022 hash_remove(mcd->md_tdtba, (void *)tdp); 1023 1024 return (rc); 1025} 1026 1027static int 1028add_tdtbr_cb(void *data, void *arg) 1029{ 1030 tdesc_t **tdpp = data; 1031 merge_cb_data_t *mcd = arg; 1032 1033 debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id); 1034 1035 if (!remap_node(tdpp, *tdpp, -1, NULL, mcd)) 1036 return (0); 1037 1038 (void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL); 1039 return (1); 1040} 1041 1042static void 1043merge_types(hash_t *src, merge_cb_data_t *mcd) 1044{ 1045 list_t *iitba = NULL; 1046 list_t *tdtbr = NULL; 1047 int iirc, tdrc; 1048 1049 mcd->md_iitba = &iitba; 1050 mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, 1051 tdesc_layoutcmp); 1052 mcd->md_tdtbr = &tdtbr; 1053 1054 (void) hash_iter(src, merge_type_cb, mcd); 1055 1056 tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, mcd); 1057 debug(3, "add_tdtba_cb added %d items\n", tdrc); 1058 1059 iirc = list_iter(*mcd->md_iitba, add_iitba_cb, mcd); 1060 debug(3, "add_iitba_cb added %d items\n", iirc); 1061 1062 assert(list_count(*mcd->md_iitba) == 0 && 1063 hash_count(mcd->md_tdtba) == 0); 1064 1065 tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, mcd); 1066 debug(3, "add_tdtbr_cb added %d items\n", tdrc); 1067 1068 if (list_count(*mcd->md_tdtbr) != 0) 1069 aborterr("Couldn't remap all nodes\n"); 1070 1071 /* 1072 * We now have an alist of master forwards and the ids of the new master 1073 * definitions for those forwards in mcd->md_fdida. By this point, 1074 * we're guaranteed that all of the master definitions referenced in 1075 * fdida have been added to the master tree. We now traverse through 1076 * the master tree, redirecting all edges inbound to forwards that have 1077 * definitions to those definitions. 1078 */ 1079 if (mcd->md_parent == mcd->md_tgt) { 1080 redir_mstr_fwds(mcd); 1081 } 1082} 1083 1084void 1085merge_into_master(tdata_t *cur, tdata_t *mstr, tdata_t *tgt, int selfuniquify) 1086{ 1087 merge_cb_data_t mcd; 1088 1089 cur->td_ref++; 1090 mstr->td_ref++; 1091 if (tgt) 1092 tgt->td_ref++; 1093 1094 assert(cur->td_ref == 1 && mstr->td_ref == 1 && 1095 (tgt == NULL || tgt->td_ref == 1)); 1096 1097 mcd.md_parent = mstr; 1098 mcd.md_tgt = (tgt ? tgt : mstr); 1099 mcd.md_ta = alist_new(NULL, NULL); 1100 mcd.md_fdida = alist_new(NULL, NULL); 1101 mcd.md_flags = 0; 1102 1103 if (selfuniquify) 1104 mcd.md_flags |= MCD_F_SELFUNIQUIFY; 1105 if (tgt) 1106 mcd.md_flags |= MCD_F_REFMERGE; 1107 1108 mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen); 1109 mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark); 1110 1111 merge_types(cur->td_iihash, &mcd); 1112 1113 if (debug_level >= 3) { 1114 debug(3, "Type association stats\n"); 1115 alist_stats(mcd.md_ta, 0); 1116 debug(3, "Layout hash stats\n"); 1117 hash_stats(mcd.md_tgt->td_layouthash, 1); 1118 } 1119 1120 alist_free(mcd.md_fdida); 1121 alist_free(mcd.md_ta); 1122 1123 cur->td_ref--; 1124 mstr->td_ref--; 1125 if (tgt) 1126 tgt->td_ref--; 1127} 1128 1129tdesc_ops_t tdesc_ops[] = { 1130 { "ERROR! BAD tdesc TYPE", NULL, NULL }, 1131 { "intrinsic", equiv_intrinsic, conjure_intrinsic }, 1132 { "pointer", equiv_plain, conjure_plain }, 1133 { "array", equiv_array, conjure_array }, 1134 { "function", equiv_function, conjure_function }, 1135 { "struct", equiv_su, conjure_su }, 1136 { "union", equiv_su, conjure_su }, 1137 { "enum", equiv_enum, conjure_enum }, 1138 { "forward", NULL, conjure_forward }, 1139 { "typedef", equiv_plain, conjure_plain }, 1140 { "typedef_unres", equiv_assert, conjure_assert }, 1141 { "volatile", equiv_plain, conjure_plain }, 1142 { "const", equiv_plain, conjure_plain }, 1143 { "restrict", equiv_plain, conjure_plain } 1144}; 1145