xref: /titanic_41/usr/src/tools/ctf/cvt/merge.c (revision c168da277d64ace98b478c694fd808f783ce7d2e)
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
add_mapping(alist_t * ta,tid_t srcid,tid_t tgtid)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
get_mapping(alist_t * ta,int srcid)191 get_mapping(alist_t *ta, int srcid)
192 {
193 	long ltgtid;
194 
195 	if (alist_find(ta, (void *)srcid, (void **)&ltgtid))
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
equiv_intrinsic(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_plain(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_function(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_array(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_su(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_enum(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
equiv_assert(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)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
fwd_equiv(tdesc_t * ctdp,tdesc_t * mtdp)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
equiv_node(tdesc_t * ctdp,tdesc_t * mtdp,equiv_data_t * ed)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
equiv_cb(void * bucket,void * arg)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
map_td_tree_pre(tdesc_t * ctdp,tdesc_t ** ctdpp,void * private)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
map_td_tree_post(tdesc_t * ctdp,tdesc_t ** ctdpp,void * private)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
map_td_tree_self_post(tdesc_t * ctdp,tdesc_t ** ctdpp,void * private)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
iidesc_match(void * data,void * arg)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
merge_type_cb(void * data,void * arg)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
remap_node(tdesc_t ** tgtp,tdesc_t * oldtgt,int selftid,tdesc_t * newself,merge_cb_data_t * mcd)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 *
conjure_template(tdesc_t * old,int newselfid)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 *
conjure_intrinsic(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_plain(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_function(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_array(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_su(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_enum(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_forward(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_assert(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)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 *
conjure_iidesc(iidesc_t * old,merge_cb_data_t * mcd)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
fwd_redir(tdesc_t * fwd,tdesc_t ** fwdp,void * private)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
redir_mstr_fwd_cb(void * name,void * value,void * arg)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
redir_mstr_fwds(merge_cb_data_t * mcd)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
add_iitba_cb(void * data,void * private)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
add_tdesc(tdesc_t * oldtdp,int newid,merge_cb_data_t * mcd)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
add_tdtba_cb(void * data,void * arg)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
add_tdtbr_cb(void * data,void * arg)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
merge_types(hash_t * src,merge_cb_data_t * mcd)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
merge_into_master(tdata_t * cur,tdata_t * mstr,tdata_t * tgt,int selfuniquify)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 };
1141