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
126 typedef struct equiv_data equiv_data_t;
127 typedef 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 */
134 typedef struct tdesc_ops {
135 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;
139 extern 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 */
145 struct 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
179 static void
180 add_mapping(alist_t *ta, tid_t srcid, tid_t tgtid)
181 {
182 debug(3, "Adding mapping %u => %u\n", srcid, tgtid);
183
184 assert(!alist_find(ta, (void *)srcid, NULL));
185 assert(srcid != 0 && tgtid != 0);
186
187 alist_add(ta, (void *)srcid, (void *)tgtid);
188 }
189
190 static tid_t
191 get_mapping(alist_t *ta, int srcid)
192 {
193 long ltgtid;
194
195 if (alist_find(ta, (void *)srcid, (void **)<gtid))
196 return ((int)ltgtid);
197 else
198 return (0);
199 }
200
201 /*
202 * Determining equivalence of tdesc_t subgraphs
203 */
204
205 struct 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
215 static int equiv_node(tdesc_t *, tdesc_t *, equiv_data_t *);
216
217 /*ARGSUSED2*/
218 static int
219 equiv_intrinsic(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
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
240 static int
241 equiv_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
246 static int
247 equiv_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 < 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
267 static int
268 equiv_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
282 static int
283 equiv_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*/
315 static int
316 equiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
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*/
337 static int
338 equiv_assert(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
339 {
340 /* foul, evil, and very bad - this is a "shouldn't happen" */
341 assert(1 == 0);
342
343 return (0);
344 }
345
346 static int
347 fwd_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 }
353
354 static int
355 equiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed)
356 {
357 int (*equiv)();
358 int mapping;
359
360 if (ctdp->t_emark > ed->ed_clear_mark ||
361 mtdp->t_emark > ed->ed_clear_mark)
362 return (ctdp->t_emark == mtdp->t_emark);
363
364 /*
365 * In normal (non-self-uniquify) mode, we don't want to do equivalency
366 * checking on a subgraph that has already been checked. If a mapping
367 * has already been established for a given child node, we can simply
368 * compare the mapping for the child node with the ID of the parent
369 * node. If we are in self-uniquify mode, then we're comparing two
370 * subgraphs within the child graph, and thus need to ignore any
371 * type mappings that have been created, as they are only valid into the
372 * parent.
373 */
374 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 &&
375 mapping == mtdp->t_id && !ed->ed_selfuniquify)
376 return (1);
377
378 if (!streq(ctdp->t_name, mtdp->t_name))
379 return (0);
380
381 if (ctdp->t_type != mtdp->t_type) {
382 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD)
383 return (fwd_equiv(ctdp, mtdp));
384 else
385 return (0);
386 }
387
388 ctdp->t_emark = ed->ed_cur_mark;
389 mtdp->t_emark = ed->ed_cur_mark;
390 ed->ed_cur_mark++;
391
392 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL)
393 return (equiv(ctdp, mtdp, ed));
394
395 return (1);
396 }
397
398 /*
399 * We perform an equivalency check on two subgraphs by traversing through them
400 * in lockstep. If a given node is equivalent in both the parent and the child,
401 * we mark it in both subgraphs, using the t_emark field, with a monotonically
402 * increasing number. If, in the course of the traversal, we reach a node that
403 * we have visited and numbered during this equivalency check, we have a cycle.
404 * If the previously-visited nodes don't have the same emark, then the edges
405 * that brought us to these nodes are not equivalent, and so the check ends.
406 * If the emarks are the same, the edges are equivalent. We then backtrack and
407 * continue the traversal. If we have exhausted all edges in the subgraph, and
408 * have not found any inequivalent nodes, then the subgraphs are equivalent.
409 */
410 static int
411 equiv_cb(void *bucket, void *arg)
412 {
413 equiv_data_t *ed = arg;
414 tdesc_t *mtdp = bucket;
415 tdesc_t *ctdp = ed->ed_node;
416
417 ed->ed_clear_mark = ed->ed_cur_mark + 1;
418 ed->ed_cur_mark = ed->ed_clear_mark + 1;
419
420 if (equiv_node(ctdp, mtdp, ed)) {
421 debug(3, "equiv_node matched %d %d\n", ctdp->t_id, mtdp->t_id);
422 ed->ed_tgt = mtdp;
423 /* matched. stop looking */
424 return (-1);
425 }
426
427 return (0);
428 }
429
430 /*ARGSUSED1*/
431 static int
432 map_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp, void *private)
433 {
434 merge_cb_data_t *mcd = private;
435
436 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0)
437 return (0);
438
439 return (1);
440 }
441
442 /*ARGSUSED1*/
443 static int
444 map_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp, void *private)
445 {
446 merge_cb_data_t *mcd = private;
447 equiv_data_t ed;
448
449 ed.ed_ta = mcd->md_ta;
450 ed.ed_clear_mark = mcd->md_parent->td_curemark;
451 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
452 ed.ed_node = ctdp;
453 ed.ed_selfuniquify = 0;
454
455 debug(3, "map_td_tree_post on %d %s\n", ctdp->t_id, tdesc_name(ctdp));
456
457 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp,
458 equiv_cb, &ed) < 0) {
459 /* We found an equivalent node */
460 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) {
461 int id = mcd->md_tgt->td_nextid++;
462
463 debug(3, "Creating new defn type %d\n", id);
464 add_mapping(mcd->md_ta, ctdp->t_id, id);
465 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt,
466 (void *)(ulong_t)id);
467 hash_add(mcd->md_tdtba, ctdp);
468 } else
469 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id);
470
471 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash,
472 equiv_cb, &ed) < 0) {
473 /*
474 * We didn't find an equivalent node by looking through the
475 * layout hash, but we somehow found it by performing an
476 * exhaustive search through the entire graph. This usually
477 * means that the "name" hash function is broken.
478 */
479 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id,
480 tdesc_name(ctdp), ed.ed_tgt->t_id);
481 } else {
482 int id = mcd->md_tgt->td_nextid++;
483
484 debug(3, "Creating new type %d\n", id);
485 add_mapping(mcd->md_ta, ctdp->t_id, id);
486 hash_add(mcd->md_tdtba, ctdp);
487 }
488
489 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
490
491 return (1);
492 }
493
494 /*ARGSUSED1*/
495 static int
496 map_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp, void *private)
497 {
498 merge_cb_data_t *mcd = private;
499 equiv_data_t ed;
500
501 ed.ed_ta = mcd->md_ta;
502 ed.ed_clear_mark = mcd->md_parent->td_curemark;
503 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
504 ed.ed_node = ctdp;
505 ed.ed_selfuniquify = 1;
506 ed.ed_tgt = NULL;
507
508 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) {
509 debug(3, "Self check found %d in %d\n", ctdp->t_id,
510 ed.ed_tgt->t_id);
511 add_mapping(mcd->md_ta, ctdp->t_id,
512 get_mapping(mcd->md_ta, ed.ed_tgt->t_id));
513 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba,
514 equiv_cb, &ed) < 0) {
515 /*
516 * We didn't find an equivalent node using the quick way (going
517 * through the hash normally), but we did find it by iterating
518 * through the entire hash. This usually means that the hash
519 * function is broken.
520 */
521 aborterr("Self-unique second pass for %d (%s) == %d\n",
522 ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id);
523 } else {
524 int id = mcd->md_tgt->td_nextid++;
525
526 debug(3, "Creating new type %d\n", id);
527 add_mapping(mcd->md_ta, ctdp->t_id, id);
528 hash_add(mcd->md_tdtba, ctdp);
529 }
530
531 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
532
533 return (1);
534 }
535
536 static tdtrav_cb_f map_pre[] = {
537 NULL,
538 map_td_tree_pre, /* intrinsic */
539 map_td_tree_pre, /* pointer */
540 map_td_tree_pre, /* array */
541 map_td_tree_pre, /* function */
542 map_td_tree_pre, /* struct */
543 map_td_tree_pre, /* union */
544 map_td_tree_pre, /* enum */
545 map_td_tree_pre, /* forward */
546 map_td_tree_pre, /* typedef */
547 tdtrav_assert, /* typedef_unres */
548 map_td_tree_pre, /* volatile */
549 map_td_tree_pre, /* const */
550 map_td_tree_pre /* restrict */
551 };
552
553 static tdtrav_cb_f map_post[] = {
554 NULL,
555 map_td_tree_post, /* intrinsic */
556 map_td_tree_post, /* pointer */
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, /* enum */
562 map_td_tree_post, /* forward */
563 map_td_tree_post, /* typedef */
564 tdtrav_assert, /* typedef_unres */
565 map_td_tree_post, /* volatile */
566 map_td_tree_post, /* const */
567 map_td_tree_post /* restrict */
568 };
569
570 static tdtrav_cb_f map_self_post[] = {
571 NULL,
572 map_td_tree_self_post, /* intrinsic */
573 map_td_tree_self_post, /* pointer */
574 map_td_tree_self_post, /* array */
575 map_td_tree_self_post, /* function */
576 map_td_tree_self_post, /* struct */
577 map_td_tree_self_post, /* union */
578 map_td_tree_self_post, /* enum */
579 map_td_tree_self_post, /* forward */
580 map_td_tree_self_post, /* typedef */
581 tdtrav_assert, /* typedef_unres */
582 map_td_tree_self_post, /* volatile */
583 map_td_tree_self_post, /* const */
584 map_td_tree_self_post /* restrict */
585 };
586
587 /*
588 * Determining equivalence of iidesc_t nodes
589 */
590
591 typedef struct iifind_data {
592 iidesc_t *iif_template;
593 alist_t *iif_ta;
594 int iif_newidx;
595 int iif_refmerge;
596 } iifind_data_t;
597
598 /*
599 * Check to see if this iidesc_t (node) - the current one on the list we're
600 * iterating through - matches the target one (iif->iif_template). Return -1
601 * if it matches, to stop the iteration.
602 */
603 static int
604 iidesc_match(void *data, void *arg)
605 {
606 iidesc_t *node = data;
607 iifind_data_t *iif = arg;
608 int i;
609
610 if (node->ii_type != iif->iif_template->ii_type ||
611 !streq(node->ii_name, iif->iif_template->ii_name) ||
612 node->ii_dtype->t_id != iif->iif_newidx)
613 return (0);
614
615 if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) &&
616 !streq(node->ii_owner, iif->iif_template->ii_owner))
617 return (0);
618
619 if (node->ii_nargs != iif->iif_template->ii_nargs)
620 return (0);
621
622 for (i = 0; i < node->ii_nargs; i++) {
623 if (get_mapping(iif->iif_ta,
624 iif->iif_template->ii_args[i]->t_id) !=
625 node->ii_args[i]->t_id)
626 return (0);
627 }
628
629 if (iif->iif_refmerge) {
630 switch (iif->iif_template->ii_type) {
631 case II_GFUN:
632 case II_SFUN:
633 case II_GVAR:
634 case II_SVAR:
635 debug(3, "suppressing duping of %d %s from %s\n",
636 iif->iif_template->ii_type,
637 iif->iif_template->ii_name,
638 (iif->iif_template->ii_owner ?
639 iif->iif_template->ii_owner : "NULL"));
640 return (0);
641 case II_NOT:
642 case II_PSYM:
643 case II_SOU:
644 case II_TYPE:
645 break;
646 }
647 }
648
649 return (-1);
650 }
651
652 static int
653 merge_type_cb(void *data, void *arg)
654 {
655 iidesc_t *sii = data;
656 merge_cb_data_t *mcd = arg;
657 iifind_data_t iif;
658 tdtrav_cb_f *post;
659
660 post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post);
661
662 /* Map the tdesc nodes */
663 (void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post,
664 mcd);
665
666 /* Map the iidesc nodes */
667 iif.iif_template = sii;
668 iif.iif_ta = mcd->md_ta;
669 iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id);
670 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
671
672 if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match,
673 &iif) == 1)
674 /* successfully mapped */
675 return (1);
676
677 debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"),
678 sii->ii_type);
679
680 list_add(mcd->md_iitba, sii);
681
682 return (0);
683 }
684
685 static int
686 remap_node(tdesc_t **tgtp, tdesc_t *oldtgt, int selftid, tdesc_t *newself,
687 merge_cb_data_t *mcd)
688 {
689 tdesc_t *tgt = NULL;
690 tdesc_t template;
691 int oldid = oldtgt->t_id;
692
693 if (oldid == selftid) {
694 *tgtp = newself;
695 return (1);
696 }
697
698 if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0)
699 aborterr("failed to get mapping for tid %d\n", oldid);
700
701 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template,
702 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) ||
703 !hash_find(mcd->md_tgt->td_idhash, (void *)&template,
704 (void *)&tgt))) {
705 debug(3, "Remap couldn't find %d (from %d)\n", template.t_id,
706 oldid);
707 *tgtp = oldtgt;
708 list_add(mcd->md_tdtbr, tgtp);
709 return (0);
710 }
711
712 *tgtp = tgt;
713 return (1);
714 }
715
716 static tdesc_t *
717 conjure_template(tdesc_t *old, int newselfid)
718 {
719 tdesc_t *new = xcalloc(sizeof (tdesc_t));
720
721 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL;
722 new->t_type = old->t_type;
723 new->t_size = old->t_size;
724 new->t_id = newselfid;
725 new->t_flags = old->t_flags;
726
727 return (new);
728 }
729
730 /*ARGSUSED2*/
731 static tdesc_t *
732 conjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
733 {
734 tdesc_t *new = conjure_template(old, newselfid);
735
736 new->t_intr = xmalloc(sizeof (intr_t));
737 bcopy(old->t_intr, new->t_intr, sizeof (intr_t));
738
739 return (new);
740 }
741
742 static tdesc_t *
743 conjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
744 {
745 tdesc_t *new = conjure_template(old, newselfid);
746
747 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd);
748
749 return (new);
750 }
751
752 static tdesc_t *
753 conjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
754 {
755 tdesc_t *new = conjure_template(old, newselfid);
756 fndef_t *nfn = xmalloc(sizeof (fndef_t));
757 fndef_t *ofn = old->t_fndef;
758 int i;
759
760 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd);
761
762 nfn->fn_nargs = ofn->fn_nargs;
763 nfn->fn_vargs = ofn->fn_vargs;
764
765 if (nfn->fn_nargs > 0)
766 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs);
767
768 for (i = 0; i < ofn->fn_nargs; i++) {
769 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id,
770 new, mcd);
771 }
772
773 new->t_fndef = nfn;
774
775 return (new);
776 }
777
778 static tdesc_t *
779 conjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
780 {
781 tdesc_t *new = conjure_template(old, newselfid);
782 ardef_t *nar = xmalloc(sizeof (ardef_t));
783 ardef_t *oar = old->t_ardef;
784
785 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new,
786 mcd);
787 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new,
788 mcd);
789
790 nar->ad_nelems = oar->ad_nelems;
791
792 new->t_ardef = nar;
793
794 return (new);
795 }
796
797 static tdesc_t *
798 conjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
799 {
800 tdesc_t *new = conjure_template(old, newselfid);
801 mlist_t *omem, **nmemp;
802
803 for (omem = old->t_members, nmemp = &new->t_members;
804 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) {
805 *nmemp = xmalloc(sizeof (mlist_t));
806 (*nmemp)->ml_offset = omem->ml_offset;
807 (*nmemp)->ml_size = omem->ml_size;
808 (*nmemp)->ml_name = xstrdup(omem->ml_name);
809 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type,
810 old->t_id, new, mcd);
811 }
812 *nmemp = NULL;
813
814 return (new);
815 }
816
817 /*ARGSUSED2*/
818 static tdesc_t *
819 conjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
820 {
821 tdesc_t *new = conjure_template(old, newselfid);
822 elist_t *oel, **nelp;
823
824 for (oel = old->t_emem, nelp = &new->t_emem;
825 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) {
826 *nelp = xmalloc(sizeof (elist_t));
827 (*nelp)->el_name = xstrdup(oel->el_name);
828 (*nelp)->el_number = oel->el_number;
829 }
830 *nelp = NULL;
831
832 return (new);
833 }
834
835 /*ARGSUSED2*/
836 static tdesc_t *
837 conjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
838 {
839 tdesc_t *new = conjure_template(old, newselfid);
840
841 list_add(&mcd->md_tgt->td_fwdlist, new);
842
843 return (new);
844 }
845
846 /*ARGSUSED*/
847 static tdesc_t *
848 conjure_assert(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
849 {
850 assert(1 == 0);
851 return (NULL);
852 }
853
854 static iidesc_t *
855 conjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd)
856 {
857 iidesc_t *new = iidesc_dup(old);
858 int i;
859
860 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd);
861 for (i = 0; i < new->ii_nargs; i++) {
862 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL,
863 mcd);
864 }
865
866 return (new);
867 }
868
869 static int
870 fwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private)
871 {
872 alist_t *map = private;
873 tdesc_t *defn;
874
875 if (!alist_find(map, (void *)fwd, (void **)&defn))
876 return (0);
877
878 debug(3, "Redirecting an edge to %s\n", tdesc_name(defn));
879
880 *fwdp = defn;
881
882 return (1);
883 }
884
885 static tdtrav_cb_f fwd_redir_cbs[] = {
886 NULL,
887 NULL, /* intrinsic */
888 NULL, /* pointer */
889 NULL, /* array */
890 NULL, /* function */
891 NULL, /* struct */
892 NULL, /* union */
893 NULL, /* enum */
894 fwd_redir, /* forward */
895 NULL, /* typedef */
896 tdtrav_assert, /* typedef_unres */
897 NULL, /* volatile */
898 NULL, /* const */
899 NULL /* restrict */
900 };
901
902 typedef struct redir_mstr_data {
903 tdata_t *rmd_tgt;
904 alist_t *rmd_map;
905 } redir_mstr_data_t;
906
907 static int
908 redir_mstr_fwd_cb(void *name, void *value, void *arg)
909 {
910 tdesc_t *fwd = name;
911 int defnid = (int)value;
912 redir_mstr_data_t *rmd = arg;
913 tdesc_t template;
914 tdesc_t *defn;
915
916 template.t_id = defnid;
917
918 if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template,
919 (void *)&defn)) {
920 aborterr("Couldn't unforward %d (%s)\n", defnid,
921 tdesc_name(defn));
922 }
923
924 debug(3, "Forward map: resolved %d to %s\n", defnid, tdesc_name(defn));
925
926 alist_add(rmd->rmd_map, (void *)fwd, (void *)defn);
927
928 return (1);
929 }
930
931 static void
932 redir_mstr_fwds(merge_cb_data_t *mcd)
933 {
934 redir_mstr_data_t rmd;
935 alist_t *map = alist_new(NULL, NULL);
936
937 rmd.rmd_tgt = mcd->md_tgt;
938 rmd.rmd_map = map;
939
940 if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) {
941 (void) iitraverse_hash(mcd->md_tgt->td_iihash,
942 &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map);
943 }
944
945 alist_free(map);
946 }
947
948 static int
949 add_iitba_cb(void *data, void *private)
950 {
951 merge_cb_data_t *mcd = private;
952 iidesc_t *tba = data;
953 iidesc_t *new;
954 iifind_data_t iif;
955 int newidx;
956
957 newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id);
958 assert(newidx != -1);
959
960 (void) list_remove(mcd->md_iitba, data, NULL, NULL);
961
962 iif.iif_template = tba;
963 iif.iif_ta = mcd->md_ta;
964 iif.iif_newidx = newidx;
965 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
966
967 if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match,
968 &iif) == 1) {
969 debug(3, "iidesc_t %s already exists\n",
970 (tba->ii_name ? tba->ii_name : "(anon)"));
971 return (1);
972 }
973
974 new = conjure_iidesc(tba, mcd);
975 hash_add(mcd->md_tgt->td_iihash, new);
976
977 return (1);
978 }
979
980 static int
981 add_tdesc(tdesc_t *oldtdp, int newid, merge_cb_data_t *mcd)
982 {
983 tdesc_t *newtdp;
984 tdesc_t template;
985
986 template.t_id = newid;
987 assert(hash_find(mcd->md_parent->td_idhash,
988 (void *)&template, NULL) == 0);
989
990 debug(3, "trying to conjure %d %s (%d) as %d\n",
991 oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id, newid);
992
993 if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid,
994 mcd)) == NULL)
995 /* couldn't map everything */
996 return (0);
997
998 debug(3, "succeeded\n");
999
1000 hash_add(mcd->md_tgt->td_idhash, newtdp);
1001 hash_add(mcd->md_tgt->td_layouthash, newtdp);
1002
1003 return (1);
1004 }
1005
1006 static int
1007 add_tdtba_cb(void *data, void *arg)
1008 {
1009 tdesc_t *tdp = data;
1010 merge_cb_data_t *mcd = arg;
1011 int newid;
1012 int rc;
1013
1014 newid = get_mapping(mcd->md_ta, tdp->t_id);
1015 assert(newid != -1);
1016
1017 if ((rc = add_tdesc(tdp, newid, mcd)))
1018 hash_remove(mcd->md_tdtba, (void *)tdp);
1019
1020 return (rc);
1021 }
1022
1023 static int
1024 add_tdtbr_cb(void *data, void *arg)
1025 {
1026 tdesc_t **tdpp = data;
1027 merge_cb_data_t *mcd = arg;
1028
1029 debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id);
1030
1031 if (!remap_node(tdpp, *tdpp, -1, NULL, mcd))
1032 return (0);
1033
1034 (void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL);
1035 return (1);
1036 }
1037
1038 static void
1039 merge_types(hash_t *src, merge_cb_data_t *mcd)
1040 {
1041 list_t *iitba = NULL;
1042 list_t *tdtbr = NULL;
1043 int iirc, tdrc;
1044
1045 mcd->md_iitba = &iitba;
1046 mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
1047 tdesc_layoutcmp);
1048 mcd->md_tdtbr = &tdtbr;
1049
1050 (void) hash_iter(src, merge_type_cb, mcd);
1051
1052 tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, (void *)mcd);
1053 debug(3, "add_tdtba_cb added %d items\n", tdrc);
1054
1055 iirc = list_iter(*mcd->md_iitba, add_iitba_cb, (void *)mcd);
1056 debug(3, "add_iitba_cb added %d items\n", iirc);
1057
1058 assert(list_count(*mcd->md_iitba) == 0 &&
1059 hash_count(mcd->md_tdtba) == 0);
1060
1061 tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, (void *)mcd);
1062 debug(3, "add_tdtbr_cb added %d items\n", tdrc);
1063
1064 if (list_count(*mcd->md_tdtbr) != 0)
1065 aborterr("Couldn't remap all nodes\n");
1066
1067 /*
1068 * We now have an alist of master forwards and the ids of the new master
1069 * definitions for those forwards in mcd->md_fdida. By this point,
1070 * we're guaranteed that all of the master definitions referenced in
1071 * fdida have been added to the master tree. We now traverse through
1072 * the master tree, redirecting all edges inbound to forwards that have
1073 * definitions to those definitions.
1074 */
1075 if (mcd->md_parent == mcd->md_tgt) {
1076 redir_mstr_fwds(mcd);
1077 }
1078 }
1079
1080 void
1081 merge_into_master(tdata_t *cur, tdata_t *mstr, tdata_t *tgt, int selfuniquify)
1082 {
1083 merge_cb_data_t mcd;
1084
1085 cur->td_ref++;
1086 mstr->td_ref++;
1087 if (tgt)
1088 tgt->td_ref++;
1089
1090 assert(cur->td_ref == 1 && mstr->td_ref == 1 &&
1091 (tgt == NULL || tgt->td_ref == 1));
1092
1093 mcd.md_parent = mstr;
1094 mcd.md_tgt = (tgt ? tgt : mstr);
1095 mcd.md_ta = alist_new(NULL, NULL);
1096 mcd.md_fdida = alist_new(NULL, NULL);
1097 mcd.md_flags = 0;
1098
1099 if (selfuniquify)
1100 mcd.md_flags |= MCD_F_SELFUNIQUIFY;
1101 if (tgt)
1102 mcd.md_flags |= MCD_F_REFMERGE;
1103
1104 mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen);
1105 mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark);
1106
1107 merge_types(cur->td_iihash, &mcd);
1108
1109 if (debug_level >= 3) {
1110 debug(3, "Type association stats\n");
1111 alist_stats(mcd.md_ta, 0);
1112 debug(3, "Layout hash stats\n");
1113 hash_stats(mcd.md_tgt->td_layouthash, 1);
1114 }
1115
1116 alist_free(mcd.md_fdida);
1117 alist_free(mcd.md_ta);
1118
1119 cur->td_ref--;
1120 mstr->td_ref--;
1121 if (tgt)
1122 tgt->td_ref--;
1123 }
1124
1125 tdesc_ops_t tdesc_ops[] = {
1126 { "ERROR! BAD tdesc TYPE", NULL, NULL },
1127 { "intrinsic", equiv_intrinsic, conjure_intrinsic },
1128 { "pointer", equiv_plain, conjure_plain },
1129 { "array", equiv_array, conjure_array },
1130 { "function", equiv_function, conjure_function },
1131 { "struct", equiv_su, conjure_su },
1132 { "union", equiv_su, conjure_su },
1133 { "enum", equiv_enum, conjure_enum },
1134 { "forward", NULL, conjure_forward },
1135 { "typedef", equiv_plain, conjure_plain },
1136 { "typedef_unres", equiv_assert, conjure_assert },
1137 { "volatile", equiv_plain, conjure_plain },
1138 { "const", equiv_plain, conjure_plain },
1139 { "restrict", equiv_plain, conjure_plain }
1140 };