merge.c revision 274565
1178481Sjb/*
2178481Sjb * CDDL HEADER START
3178481Sjb *
4178481Sjb * The contents of this file are subject to the terms of the
5178481Sjb * Common Development and Distribution License (the "License").
6178481Sjb * You may not use this file except in compliance with the License.
7178481Sjb *
8178481Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9178481Sjb * or http://www.opensolaris.org/os/licensing.
10178481Sjb * See the License for the specific language governing permissions
11178481Sjb * and limitations under the License.
12178481Sjb *
13178481Sjb * When distributing Covered Code, include this CDDL HEADER in each
14178481Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15178481Sjb * If applicable, add the following below this CDDL HEADER, with the
16178481Sjb * fields enclosed by brackets "[]" replaced with your own identifying
17178481Sjb * information: Portions Copyright [yyyy] [name of copyright owner]
18178481Sjb *
19178481Sjb * CDDL HEADER END
20178481Sjb */
21178481Sjb/*
22178481Sjb * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
23178481Sjb * Use is subject to license terms.
24178481Sjb */
25178481Sjb
26178481Sjb#pragma ident	"%Z%%M%	%I%	%E% SMI"
27178481Sjb
28178481Sjb/*
29178481Sjb * This file contains routines that merge one tdata_t tree, called the child,
30178481Sjb * into another, called the parent.  Note that these names are used mainly for
31178481Sjb * convenience and to represent the direction of the merge.  They are not meant
32178481Sjb * to imply any relationship between the tdata_t graphs prior to the merge.
33178481Sjb *
34178481Sjb * tdata_t structures contain two main elements - a hash of iidesc_t nodes, and
35178481Sjb * a directed graph of tdesc_t nodes, pointed to by the iidesc_t nodes.  Simply
36178481Sjb * put, we merge the tdesc_t graphs, followed by the iidesc_t nodes, and then we
37178481Sjb * clean up loose ends.
38178481Sjb *
39178481Sjb * The algorithm is as follows:
40178481Sjb *
41178481Sjb * 1. Mapping iidesc_t nodes
42178481Sjb *
43178481Sjb * For each child iidesc_t node, we first try to map its tdesc_t subgraph
44178481Sjb * against the tdesc_t graph in the parent.  For each node in the child subgraph
45178481Sjb * that exists in the parent, a mapping between the two (between their type IDs)
46178481Sjb * is established.  For the child nodes that cannot be mapped onto existing
47178481Sjb * parent nodes, a mapping is established between the child node ID and a
48178481Sjb * newly-allocated ID that the node will use when it is re-created in the
49178481Sjb * parent.  These unmappable nodes are added to the md_tdtba (tdesc_t To Be
50178481Sjb * Added) hash, which tracks nodes that need to be created in the parent.
51178481Sjb *
52178481Sjb * If all of the nodes in the subgraph for an iidesc_t in the child can be
53178481Sjb * mapped to existing nodes in the parent, then we can try to map the child
54178481Sjb * iidesc_t onto an iidesc_t in the parent.  If we cannot find an equivalent
55178481Sjb * iidesc_t, or if we were not able to completely map the tdesc_t subgraph(s),
56178481Sjb * then we add this iidesc_t to the md_iitba (iidesc_t To Be Added) list.  This
57178481Sjb * list tracks iidesc_t nodes that are to be created in the parent.
58178481Sjb *
59178481Sjb * While visiting the tdesc_t nodes, we may discover a forward declaration (a
60178481Sjb * FORWARD tdesc_t) in the parent that is resolved in the child.  That is, there
61178481Sjb * may be a structure or union definition in the child with the same name as the
62178481Sjb * forward declaration in the parent.  If we find such a node, we record an
63178481Sjb * association in the md_fdida (Forward => Definition ID Association) list
64178481Sjb * between the parent ID of the forward declaration and the ID that the
65178481Sjb * definition will use when re-created in the parent.
66178481Sjb *
67178481Sjb * 2. Creating new tdesc_t nodes (the md_tdtba hash)
68178481Sjb *
69178481Sjb * We have now attempted to map all tdesc_t nodes from the child into the
70178481Sjb * parent, and have, in md_tdtba, a hash of all tdesc_t nodes that need to be
71178481Sjb * created (or, as we so wittily call it, conjured) in the parent.  We iterate
72178481Sjb * through this hash, creating the indicated tdesc_t nodes.  For a given tdesc_t
73178481Sjb * node, conjuring requires two steps - the copying of the common tdesc_t data
74178481Sjb * (name, type, etc) from the child node, and the creation of links from the
75178481Sjb * newly-created node to the parent equivalents of other tdesc_t nodes pointed
76178481Sjb * to by node being conjured.  Note that in some cases, the targets of these
77178481Sjb * links will be on the md_tdtba hash themselves, and may not have been created
78178481Sjb * yet.  As such, we can't establish the links from these new nodes into the
79178481Sjb * parent graph.  We therefore conjure them with links to nodes in the *child*
80178481Sjb * graph, and add pointers to the links to be created to the md_tdtbr (tdesc_t
81178481Sjb * To Be Remapped) hash.  For example, a POINTER tdesc_t that could not be
82178481Sjb * resolved would have its &tdesc_t->t_tdesc added to md_tdtbr.
83178481Sjb *
84178481Sjb * 3. Creating new iidesc_t nodes (the md_iitba list)
85178481Sjb *
86178481Sjb * When we have completed step 2, all tdesc_t nodes have been created (or
87178481Sjb * already existed) in the parent.  Some of them may have incorrect links (the
88178481Sjb * members of the md_tdtbr list), but they've all been created.  As such, we can
89178481Sjb * create all of the iidesc_t nodes, as we can attach the tdesc_t subgraph
90178481Sjb * pointers correctly.  We create each node, and attach the pointers to the
91178481Sjb * appropriate parts of the parent tdesc_t graph.
92178481Sjb *
93178481Sjb * 4. Resolving newly-created tdesc_t node links (the md_tdtbr list)
94178481Sjb *
95178481Sjb * As in step 3, we rely on the fact that all of the tdesc_t nodes have been
96178481Sjb * created.  Each entry in the md_tdtbr list is a pointer to where a link into
97178481Sjb * the parent will be established.  As saved in the md_tdtbr list, these
98178481Sjb * pointers point into the child tdesc_t subgraph.  We can thus get the target
99178481Sjb * type ID from the child, look at the ID mapping to determine the desired link
100178481Sjb * target, and redirect the link accordingly.
101178481Sjb *
102178481Sjb * 5. Parent => child forward declaration resolution
103178481Sjb *
104178481Sjb * If entries were made in the md_fdida list in step 1, we have forward
105178481Sjb * declarations in the parent that need to be resolved to their definitions
106178481Sjb * re-created in step 2 from the child.  Using the md_fdida list, we can locate
107178481Sjb * the definition for the forward declaration, and we can redirect all inbound
108178481Sjb * edges to the forward declaration node to the actual definition.
109178481Sjb *
110178481Sjb * A pox on the house of anyone who changes the algorithm without updating
111178481Sjb * this comment.
112178481Sjb */
113178481Sjb
114178481Sjb#include <stdio.h>
115178481Sjb#include <strings.h>
116178481Sjb#include <assert.h>
117178481Sjb#include <pthread.h>
118178481Sjb
119178481Sjb#include "ctf_headers.h"
120178481Sjb#include "ctftools.h"
121178481Sjb#include "list.h"
122178481Sjb#include "alist.h"
123178481Sjb#include "memory.h"
124178481Sjb#include "traverse.h"
125178481Sjb
126178481Sjbtypedef struct equiv_data equiv_data_t;
127178481Sjbtypedef struct merge_cb_data merge_cb_data_t;
128178481Sjb
129178481Sjb/*
130178481Sjb * There are two traversals in this file, for equivalency and for tdesc_t
131178481Sjb * re-creation, that do not fit into the tdtraverse() framework.  We have our
132178481Sjb * own traversal mechanism and ops vector here for those two cases.
133178481Sjb */
134178481Sjbtypedef struct tdesc_ops {
135178546Sjb	const char *name;
136178481Sjb	int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *);
137178481Sjb	tdesc_t *(*conjure)(tdesc_t *, int, merge_cb_data_t *);
138178481Sjb} tdesc_ops_t;
139178481Sjbextern tdesc_ops_t tdesc_ops[];
140178481Sjb
141178481Sjb/*
142178481Sjb * The workhorse structure of tdata_t merging.  Holds all lists of nodes to be
143178481Sjb * processed during various phases of the merge algorithm.
144178481Sjb */
145178481Sjbstruct merge_cb_data {
146178481Sjb	tdata_t *md_parent;
147178481Sjb	tdata_t *md_tgt;
148178481Sjb	alist_t *md_ta;		/* Type Association */
149178481Sjb	alist_t *md_fdida;	/* Forward -> Definition ID Association */
150178481Sjb	list_t	**md_iitba;	/* iidesc_t nodes To Be Added to the parent */
151178481Sjb	hash_t	*md_tdtba;	/* tdesc_t nodes To Be Added to the parent */
152178481Sjb	list_t	**md_tdtbr;	/* tdesc_t nodes To Be Remapped */
153178481Sjb	int md_flags;
154178481Sjb}; /* merge_cb_data_t */
155178481Sjb
156178481Sjb/*
157178481Sjb * When we first create a tdata_t from stabs data, we will have duplicate nodes.
158178481Sjb * Normal merges, however, assume that the child tdata_t is already self-unique,
159178481Sjb * and for speed reasons do not attempt to self-uniquify.  If this flag is set,
160178481Sjb * the merge algorithm will self-uniquify by avoiding the insertion of
161178481Sjb * duplicates in the md_tdtdba list.
162178481Sjb */
163178481Sjb#define	MCD_F_SELFUNIQUIFY	0x1
164178481Sjb
165178481Sjb/*
166178481Sjb * When we merge the CTF data for the modules, we don't want it to contain any
167178481Sjb * data that can be found in the reference module (usually genunix).  If this
168178481Sjb * flag is set, we're doing a merge between the fully merged tdata_t for this
169178481Sjb * module and the tdata_t for the reference module, with the data unique to this
170178481Sjb * module ending up in a third tdata_t.  It is this third tdata_t that will end
171178481Sjb * up in the .SUNW_ctf section for the module.
172178481Sjb */
173178481Sjb#define	MCD_F_REFMERGE	0x2
174178481Sjb
175178481Sjb/*
176178481Sjb * Mapping of child type IDs to parent type IDs
177178481Sjb */
178178481Sjb
179178481Sjbstatic void
180178481Sjbadd_mapping(alist_t *ta, tid_t srcid, tid_t tgtid)
181178481Sjb{
182178546Sjb	debug(3, "Adding mapping %u <%x> => %u <%x>\n", srcid, srcid, tgtid, tgtid);
183178481Sjb
184178546Sjb	assert(!alist_find(ta, (void *)(uintptr_t)srcid, NULL));
185178481Sjb	assert(srcid != 0 && tgtid != 0);
186178481Sjb
187178546Sjb	alist_add(ta, (void *)(uintptr_t)srcid, (void *)(uintptr_t)tgtid);
188178481Sjb}
189178481Sjb
190178481Sjbstatic tid_t
191178481Sjbget_mapping(alist_t *ta, int srcid)
192178481Sjb{
193178546Sjb	void *ltgtid;
194178481Sjb
195178546Sjb	if (alist_find(ta, (void *)(uintptr_t)srcid, (void **)&ltgtid))
196178546Sjb		return ((uintptr_t)ltgtid);
197178481Sjb	else
198178481Sjb		return (0);
199178481Sjb}
200178481Sjb
201178481Sjb/*
202178481Sjb * Determining equivalence of tdesc_t subgraphs
203178481Sjb */
204178481Sjb
205178481Sjbstruct equiv_data {
206178481Sjb	alist_t *ed_ta;
207178481Sjb	tdesc_t *ed_node;
208178481Sjb	tdesc_t *ed_tgt;
209178481Sjb
210178481Sjb	int ed_clear_mark;
211178481Sjb	int ed_cur_mark;
212178481Sjb	int ed_selfuniquify;
213178481Sjb}; /* equiv_data_t */
214178481Sjb
215178481Sjbstatic int equiv_node(tdesc_t *, tdesc_t *, equiv_data_t *);
216178481Sjb
217178481Sjb/*ARGSUSED2*/
218178481Sjbstatic int
219178546Sjbequiv_intrinsic(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused)
220178481Sjb{
221178481Sjb	intr_t *si = stdp->t_intr;
222178481Sjb	intr_t *ti = ttdp->t_intr;
223178481Sjb
224178481Sjb	if (si->intr_type != ti->intr_type ||
225178481Sjb	    si->intr_signed != ti->intr_signed ||
226178481Sjb	    si->intr_offset != ti->intr_offset ||
227178481Sjb	    si->intr_nbits != ti->intr_nbits)
228178481Sjb		return (0);
229178481Sjb
230178481Sjb	if (si->intr_type == INTR_INT &&
231178481Sjb	    si->intr_iformat != ti->intr_iformat)
232178481Sjb		return (0);
233178481Sjb	else if (si->intr_type == INTR_REAL &&
234178481Sjb	    si->intr_fformat != ti->intr_fformat)
235178481Sjb		return (0);
236178481Sjb
237178481Sjb	return (1);
238178481Sjb}
239178481Sjb
240178481Sjbstatic int
241178481Sjbequiv_plain(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
242178481Sjb{
243178481Sjb	return (equiv_node(stdp->t_tdesc, ttdp->t_tdesc, ed));
244178481Sjb}
245178481Sjb
246178481Sjbstatic int
247178481Sjbequiv_function(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
248178481Sjb{
249178481Sjb	fndef_t *fn1 = stdp->t_fndef, *fn2 = ttdp->t_fndef;
250178481Sjb	int i;
251178481Sjb
252178481Sjb	if (fn1->fn_nargs != fn2->fn_nargs ||
253178481Sjb	    fn1->fn_vargs != fn2->fn_vargs)
254178481Sjb		return (0);
255178481Sjb
256178481Sjb	if (!equiv_node(fn1->fn_ret, fn2->fn_ret, ed))
257178481Sjb		return (0);
258178481Sjb
259178546Sjb	for (i = 0; i < (int) fn1->fn_nargs; i++) {
260178481Sjb		if (!equiv_node(fn1->fn_args[i], fn2->fn_args[i], ed))
261178481Sjb			return (0);
262178481Sjb	}
263178481Sjb
264178481Sjb	return (1);
265178481Sjb}
266178481Sjb
267178481Sjbstatic int
268178481Sjbequiv_array(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
269178481Sjb{
270178481Sjb	ardef_t *ar1 = stdp->t_ardef, *ar2 = ttdp->t_ardef;
271178481Sjb
272178481Sjb	if (!equiv_node(ar1->ad_contents, ar2->ad_contents, ed) ||
273178481Sjb	    !equiv_node(ar1->ad_idxtype, ar2->ad_idxtype, ed))
274178481Sjb		return (0);
275178481Sjb
276178481Sjb	if (ar1->ad_nelems != ar2->ad_nelems)
277178481Sjb		return (0);
278178481Sjb
279178481Sjb	return (1);
280178481Sjb}
281178481Sjb
282178481Sjbstatic int
283178481Sjbequiv_su(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
284178481Sjb{
285178481Sjb	mlist_t *ml1 = stdp->t_members, *ml2 = ttdp->t_members;
286178481Sjb	mlist_t *olm1 = NULL;
287178481Sjb
288178481Sjb	while (ml1 && ml2) {
289178481Sjb		if (ml1->ml_offset != ml2->ml_offset ||
290274565Smarkj		    strcmp(ml1->ml_name, ml2->ml_name) != 0 ||
291274565Smarkj		    ml1->ml_size != ml2->ml_size ||
292274565Smarkj		    !equiv_node(ml1->ml_type, ml2->ml_type, ed))
293178481Sjb			return (0);
294178481Sjb
295178481Sjb		olm1 = ml1;
296178481Sjb		ml1 = ml1->ml_next;
297178481Sjb		ml2 = ml2->ml_next;
298178481Sjb	}
299178481Sjb
300178481Sjb	if (ml1 || ml2)
301178481Sjb		return (0);
302178481Sjb
303178481Sjb	return (1);
304178481Sjb}
305178481Sjb
306178481Sjb/*ARGSUSED2*/
307178481Sjbstatic int
308178546Sjbequiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused)
309178481Sjb{
310178481Sjb	elist_t *el1 = stdp->t_emem;
311178481Sjb	elist_t *el2 = ttdp->t_emem;
312178481Sjb
313178481Sjb	while (el1 && el2) {
314178481Sjb		if (el1->el_number != el2->el_number ||
315178481Sjb		    strcmp(el1->el_name, el2->el_name) != 0)
316178481Sjb			return (0);
317178481Sjb
318178481Sjb		el1 = el1->el_next;
319178481Sjb		el2 = el2->el_next;
320178481Sjb	}
321178481Sjb
322178481Sjb	if (el1 || el2)
323178481Sjb		return (0);
324178481Sjb
325178481Sjb	return (1);
326178481Sjb}
327178481Sjb
328178481Sjb/*ARGSUSED*/
329178481Sjbstatic int
330178546Sjbequiv_assert(tdesc_t *stdp __unused, tdesc_t *ttdp __unused, equiv_data_t *ed __unused)
331178481Sjb{
332178481Sjb	/* foul, evil, and very bad - this is a "shouldn't happen" */
333178481Sjb	assert(1 == 0);
334178481Sjb
335178481Sjb	return (0);
336178481Sjb}
337178481Sjb
338178481Sjbstatic int
339178481Sjbfwd_equiv(tdesc_t *ctdp, tdesc_t *mtdp)
340178481Sjb{
341178481Sjb	tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp);
342178481Sjb
343178481Sjb	return (defn->t_type == STRUCT || defn->t_type == UNION);
344178481Sjb}
345178481Sjb
346178481Sjbstatic int
347178481Sjbequiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed)
348178481Sjb{
349178546Sjb	int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *);
350178481Sjb	int mapping;
351178481Sjb
352178481Sjb	if (ctdp->t_emark > ed->ed_clear_mark ||
353178481Sjb	    mtdp->t_emark > ed->ed_clear_mark)
354178481Sjb		return (ctdp->t_emark == mtdp->t_emark);
355178481Sjb
356178481Sjb	/*
357178481Sjb	 * In normal (non-self-uniquify) mode, we don't want to do equivalency
358178481Sjb	 * checking on a subgraph that has already been checked.  If a mapping
359178481Sjb	 * has already been established for a given child node, we can simply
360178481Sjb	 * compare the mapping for the child node with the ID of the parent
361178481Sjb	 * node.  If we are in self-uniquify mode, then we're comparing two
362178481Sjb	 * subgraphs within the child graph, and thus need to ignore any
363178481Sjb	 * type mappings that have been created, as they are only valid into the
364178481Sjb	 * parent.
365178481Sjb	 */
366178481Sjb	if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 &&
367178481Sjb	    mapping == mtdp->t_id && !ed->ed_selfuniquify)
368178481Sjb		return (1);
369178481Sjb
370178481Sjb	if (!streq(ctdp->t_name, mtdp->t_name))
371178481Sjb		return (0);
372178481Sjb
373178481Sjb	if (ctdp->t_type != mtdp->t_type) {
374178481Sjb		if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD)
375178481Sjb			return (fwd_equiv(ctdp, mtdp));
376178481Sjb		else
377178481Sjb			return (0);
378178481Sjb	}
379178481Sjb
380178481Sjb	ctdp->t_emark = ed->ed_cur_mark;
381178481Sjb	mtdp->t_emark = ed->ed_cur_mark;
382178481Sjb	ed->ed_cur_mark++;
383178481Sjb
384178481Sjb	if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL)
385178481Sjb		return (equiv(ctdp, mtdp, ed));
386178481Sjb
387178481Sjb	return (1);
388178481Sjb}
389178481Sjb
390178481Sjb/*
391178481Sjb * We perform an equivalency check on two subgraphs by traversing through them
392178481Sjb * in lockstep.  If a given node is equivalent in both the parent and the child,
393178481Sjb * we mark it in both subgraphs, using the t_emark field, with a monotonically
394178481Sjb * increasing number.  If, in the course of the traversal, we reach a node that
395178481Sjb * we have visited and numbered during this equivalency check, we have a cycle.
396178481Sjb * If the previously-visited nodes don't have the same emark, then the edges
397178481Sjb * that brought us to these nodes are not equivalent, and so the check ends.
398178481Sjb * If the emarks are the same, the edges are equivalent.  We then backtrack and
399178481Sjb * continue the traversal.  If we have exhausted all edges in the subgraph, and
400178481Sjb * have not found any inequivalent nodes, then the subgraphs are equivalent.
401178481Sjb */
402178481Sjbstatic int
403178481Sjbequiv_cb(void *bucket, void *arg)
404178481Sjb{
405178481Sjb	equiv_data_t *ed = arg;
406178481Sjb	tdesc_t *mtdp = bucket;
407178481Sjb	tdesc_t *ctdp = ed->ed_node;
408178481Sjb
409178481Sjb	ed->ed_clear_mark = ed->ed_cur_mark + 1;
410178481Sjb	ed->ed_cur_mark = ed->ed_clear_mark + 1;
411178481Sjb
412178481Sjb	if (equiv_node(ctdp, mtdp, ed)) {
413178546Sjb		debug(3, "equiv_node matched %d <%x> %d <%x>\n",
414178546Sjb		    ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id);
415178481Sjb		ed->ed_tgt = mtdp;
416178481Sjb		/* matched.  stop looking */
417178481Sjb		return (-1);
418178481Sjb	}
419178481Sjb
420178481Sjb	return (0);
421178481Sjb}
422178481Sjb
423178481Sjb/*ARGSUSED1*/
424178481Sjbstatic int
425178546Sjbmap_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
426178481Sjb{
427178481Sjb	merge_cb_data_t *mcd = private;
428178481Sjb
429178481Sjb	if (get_mapping(mcd->md_ta, ctdp->t_id) > 0)
430178481Sjb		return (0);
431178481Sjb
432178481Sjb	return (1);
433178481Sjb}
434178481Sjb
435178481Sjb/*ARGSUSED1*/
436178481Sjbstatic int
437178546Sjbmap_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
438178481Sjb{
439178481Sjb	merge_cb_data_t *mcd = private;
440178481Sjb	equiv_data_t ed;
441178481Sjb
442178481Sjb	ed.ed_ta = mcd->md_ta;
443178481Sjb	ed.ed_clear_mark = mcd->md_parent->td_curemark;
444178481Sjb	ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
445178481Sjb	ed.ed_node = ctdp;
446178481Sjb	ed.ed_selfuniquify = 0;
447178481Sjb
448178546Sjb	debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp));
449178481Sjb
450178481Sjb	if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp,
451178481Sjb	    equiv_cb, &ed) < 0) {
452178481Sjb		/* We found an equivalent node */
453178481Sjb		if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) {
454178481Sjb			int id = mcd->md_tgt->td_nextid++;
455178481Sjb
456178546Sjb			debug(3, "Creating new defn type %d <%x>\n", id, id);
457178481Sjb			add_mapping(mcd->md_ta, ctdp->t_id, id);
458178481Sjb			alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt,
459178481Sjb			    (void *)(ulong_t)id);
460178481Sjb			hash_add(mcd->md_tdtba, ctdp);
461178481Sjb		} else
462178481Sjb			add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id);
463178481Sjb
464178481Sjb	} else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash,
465178481Sjb	    equiv_cb, &ed) < 0) {
466178481Sjb		/*
467178481Sjb		 * We didn't find an equivalent node by looking through the
468178481Sjb		 * layout hash, but we somehow found it by performing an
469178481Sjb		 * exhaustive search through the entire graph.  This usually
470178481Sjb		 * means that the "name" hash function is broken.
471178481Sjb		 */
472178481Sjb		aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id,
473178481Sjb		    tdesc_name(ctdp), ed.ed_tgt->t_id);
474178481Sjb	} else {
475178481Sjb		int id = mcd->md_tgt->td_nextid++;
476178481Sjb
477178546Sjb		debug(3, "Creating new type %d <%x>\n", id, id);
478178481Sjb		add_mapping(mcd->md_ta, ctdp->t_id, id);
479178481Sjb		hash_add(mcd->md_tdtba, ctdp);
480178481Sjb	}
481178481Sjb
482178481Sjb	mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
483178481Sjb
484178481Sjb	return (1);
485178481Sjb}
486178481Sjb
487178481Sjb/*ARGSUSED1*/
488178481Sjbstatic int
489178546Sjbmap_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
490178481Sjb{
491178481Sjb	merge_cb_data_t *mcd = private;
492178481Sjb	equiv_data_t ed;
493178481Sjb
494178481Sjb	ed.ed_ta = mcd->md_ta;
495178481Sjb	ed.ed_clear_mark = mcd->md_parent->td_curemark;
496178481Sjb	ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
497178481Sjb	ed.ed_node = ctdp;
498178481Sjb	ed.ed_selfuniquify = 1;
499178481Sjb	ed.ed_tgt = NULL;
500178481Sjb
501178481Sjb	if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) {
502178546Sjb		debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id,
503178546Sjb		    ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id);
504178481Sjb		add_mapping(mcd->md_ta, ctdp->t_id,
505178481Sjb		    get_mapping(mcd->md_ta, ed.ed_tgt->t_id));
506178481Sjb	} else if (debug_level > 1 && hash_iter(mcd->md_tdtba,
507178481Sjb	    equiv_cb, &ed) < 0) {
508178481Sjb		/*
509178481Sjb		 * We didn't find an equivalent node using the quick way (going
510178481Sjb		 * through the hash normally), but we did find it by iterating
511178481Sjb		 * through the entire hash.  This usually means that the hash
512178481Sjb		 * function is broken.
513178481Sjb		 */
514178546Sjb		aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n",
515178546Sjb		    ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id,
516178546Sjb		    ed.ed_tgt->t_id);
517178481Sjb	} else {
518178481Sjb		int id = mcd->md_tgt->td_nextid++;
519178481Sjb
520178546Sjb		debug(3, "Creating new type %d <%x>\n", id, id);
521178481Sjb		add_mapping(mcd->md_ta, ctdp->t_id, id);
522178481Sjb		hash_add(mcd->md_tdtba, ctdp);
523178481Sjb	}
524178481Sjb
525178481Sjb	mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
526178481Sjb
527178481Sjb	return (1);
528178481Sjb}
529178481Sjb
530178481Sjbstatic tdtrav_cb_f map_pre[] = {
531178481Sjb	NULL,
532178481Sjb	map_td_tree_pre,	/* intrinsic */
533178481Sjb	map_td_tree_pre,	/* pointer */
534178481Sjb	map_td_tree_pre,	/* array */
535178481Sjb	map_td_tree_pre,	/* function */
536178481Sjb	map_td_tree_pre,	/* struct */
537178481Sjb	map_td_tree_pre,	/* union */
538178481Sjb	map_td_tree_pre,	/* enum */
539178481Sjb	map_td_tree_pre,	/* forward */
540178481Sjb	map_td_tree_pre,	/* typedef */
541178481Sjb	tdtrav_assert,		/* typedef_unres */
542178481Sjb	map_td_tree_pre,	/* volatile */
543178481Sjb	map_td_tree_pre,	/* const */
544178481Sjb	map_td_tree_pre		/* restrict */
545178481Sjb};
546178481Sjb
547178481Sjbstatic tdtrav_cb_f map_post[] = {
548178481Sjb	NULL,
549178481Sjb	map_td_tree_post,	/* intrinsic */
550178481Sjb	map_td_tree_post,	/* pointer */
551178481Sjb	map_td_tree_post,	/* array */
552178481Sjb	map_td_tree_post,	/* function */
553178481Sjb	map_td_tree_post,	/* struct */
554178481Sjb	map_td_tree_post,	/* union */
555178481Sjb	map_td_tree_post,	/* enum */
556178481Sjb	map_td_tree_post,	/* forward */
557178481Sjb	map_td_tree_post,	/* typedef */
558178481Sjb	tdtrav_assert,		/* typedef_unres */
559178481Sjb	map_td_tree_post,	/* volatile */
560178481Sjb	map_td_tree_post,	/* const */
561178481Sjb	map_td_tree_post	/* restrict */
562178481Sjb};
563178481Sjb
564178481Sjbstatic tdtrav_cb_f map_self_post[] = {
565178481Sjb	NULL,
566178481Sjb	map_td_tree_self_post,	/* intrinsic */
567178481Sjb	map_td_tree_self_post,	/* pointer */
568178481Sjb	map_td_tree_self_post,	/* array */
569178481Sjb	map_td_tree_self_post,	/* function */
570178481Sjb	map_td_tree_self_post,	/* struct */
571178481Sjb	map_td_tree_self_post,	/* union */
572178481Sjb	map_td_tree_self_post,	/* enum */
573178481Sjb	map_td_tree_self_post,	/* forward */
574178481Sjb	map_td_tree_self_post,	/* typedef */
575178481Sjb	tdtrav_assert,		/* typedef_unres */
576178481Sjb	map_td_tree_self_post,	/* volatile */
577178481Sjb	map_td_tree_self_post,	/* const */
578178481Sjb	map_td_tree_self_post	/* restrict */
579178481Sjb};
580178481Sjb
581178481Sjb/*
582178481Sjb * Determining equivalence of iidesc_t nodes
583178481Sjb */
584178481Sjb
585178481Sjbtypedef struct iifind_data {
586178481Sjb	iidesc_t *iif_template;
587178481Sjb	alist_t *iif_ta;
588178481Sjb	int iif_newidx;
589178481Sjb	int iif_refmerge;
590178481Sjb} iifind_data_t;
591178481Sjb
592178481Sjb/*
593178481Sjb * Check to see if this iidesc_t (node) - the current one on the list we're
594178481Sjb * iterating through - matches the target one (iif->iif_template).  Return -1
595178481Sjb * if it matches, to stop the iteration.
596178481Sjb */
597178481Sjbstatic int
598178481Sjbiidesc_match(void *data, void *arg)
599178481Sjb{
600178481Sjb	iidesc_t *node = data;
601178481Sjb	iifind_data_t *iif = arg;
602178481Sjb	int i;
603178481Sjb
604178481Sjb	if (node->ii_type != iif->iif_template->ii_type ||
605178481Sjb	    !streq(node->ii_name, iif->iif_template->ii_name) ||
606178481Sjb	    node->ii_dtype->t_id != iif->iif_newidx)
607178481Sjb		return (0);
608178481Sjb
609178481Sjb	if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) &&
610178481Sjb	    !streq(node->ii_owner, iif->iif_template->ii_owner))
611178481Sjb		return (0);
612178481Sjb
613178481Sjb	if (node->ii_nargs != iif->iif_template->ii_nargs)
614178481Sjb		return (0);
615178481Sjb
616178481Sjb	for (i = 0; i < node->ii_nargs; i++) {
617178481Sjb		if (get_mapping(iif->iif_ta,
618178481Sjb		    iif->iif_template->ii_args[i]->t_id) !=
619178481Sjb		    node->ii_args[i]->t_id)
620178481Sjb			return (0);
621178481Sjb	}
622178481Sjb
623178481Sjb	if (iif->iif_refmerge) {
624178481Sjb		switch (iif->iif_template->ii_type) {
625178481Sjb		case II_GFUN:
626178481Sjb		case II_SFUN:
627178481Sjb		case II_GVAR:
628178481Sjb		case II_SVAR:
629178481Sjb			debug(3, "suppressing duping of %d %s from %s\n",
630178481Sjb			    iif->iif_template->ii_type,
631178481Sjb			    iif->iif_template->ii_name,
632178481Sjb			    (iif->iif_template->ii_owner ?
633178481Sjb			    iif->iif_template->ii_owner : "NULL"));
634178481Sjb			return (0);
635178481Sjb		case II_NOT:
636178481Sjb		case II_PSYM:
637178481Sjb		case II_SOU:
638178481Sjb		case II_TYPE:
639178481Sjb			break;
640178481Sjb		}
641178481Sjb	}
642178481Sjb
643178481Sjb	return (-1);
644178481Sjb}
645178481Sjb
646178481Sjbstatic int
647178481Sjbmerge_type_cb(void *data, void *arg)
648178481Sjb{
649178481Sjb	iidesc_t *sii = data;
650178481Sjb	merge_cb_data_t *mcd = arg;
651178481Sjb	iifind_data_t iif;
652178481Sjb	tdtrav_cb_f *post;
653178481Sjb
654178481Sjb	post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post);
655178481Sjb
656178481Sjb	/* Map the tdesc nodes */
657178481Sjb	(void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post,
658178481Sjb	    mcd);
659178481Sjb
660178481Sjb	/* Map the iidesc nodes */
661178481Sjb	iif.iif_template = sii;
662178481Sjb	iif.iif_ta = mcd->md_ta;
663178481Sjb	iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id);
664178481Sjb	iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
665178481Sjb
666178481Sjb	if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match,
667178481Sjb	    &iif) == 1)
668178481Sjb		/* successfully mapped */
669178481Sjb		return (1);
670178481Sjb
671178481Sjb	debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"),
672178481Sjb	    sii->ii_type);
673178481Sjb
674178481Sjb	list_add(mcd->md_iitba, sii);
675178481Sjb
676178481Sjb	return (0);
677178481Sjb}
678178481Sjb
679178481Sjbstatic int
680178481Sjbremap_node(tdesc_t **tgtp, tdesc_t *oldtgt, int selftid, tdesc_t *newself,
681178481Sjb    merge_cb_data_t *mcd)
682178481Sjb{
683178481Sjb	tdesc_t *tgt = NULL;
684178481Sjb	tdesc_t template;
685178481Sjb	int oldid = oldtgt->t_id;
686178481Sjb
687178481Sjb	if (oldid == selftid) {
688178481Sjb		*tgtp = newself;
689178481Sjb		return (1);
690178481Sjb	}
691178481Sjb
692178481Sjb	if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0)
693178546Sjb		aborterr("failed to get mapping for tid %d <%x>\n", oldid, oldid);
694178481Sjb
695178481Sjb	if (!hash_find(mcd->md_parent->td_idhash, (void *)&template,
696178481Sjb	    (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) ||
697178481Sjb	    !hash_find(mcd->md_tgt->td_idhash, (void *)&template,
698178481Sjb	    (void *)&tgt))) {
699178546Sjb		debug(3, "Remap couldn't find %d <%x> (from %d <%x>)\n", template.t_id,
700178546Sjb		    template.t_id, oldid, oldid);
701178481Sjb		*tgtp = oldtgt;
702178481Sjb		list_add(mcd->md_tdtbr, tgtp);
703178481Sjb		return (0);
704178481Sjb	}
705178481Sjb
706178481Sjb	*tgtp = tgt;
707178481Sjb	return (1);
708178481Sjb}
709178481Sjb
710178481Sjbstatic tdesc_t *
711178481Sjbconjure_template(tdesc_t *old, int newselfid)
712178481Sjb{
713178481Sjb	tdesc_t *new = xcalloc(sizeof (tdesc_t));
714178481Sjb
715178481Sjb	new->t_name = old->t_name ? xstrdup(old->t_name) : NULL;
716178481Sjb	new->t_type = old->t_type;
717178481Sjb	new->t_size = old->t_size;
718178481Sjb	new->t_id = newselfid;
719178481Sjb	new->t_flags = old->t_flags;
720178481Sjb
721178481Sjb	return (new);
722178481Sjb}
723178481Sjb
724178481Sjb/*ARGSUSED2*/
725178481Sjbstatic tdesc_t *
726178546Sjbconjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused)
727178481Sjb{
728178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
729178481Sjb
730178481Sjb	new->t_intr = xmalloc(sizeof (intr_t));
731178481Sjb	bcopy(old->t_intr, new->t_intr, sizeof (intr_t));
732178481Sjb
733178481Sjb	return (new);
734178481Sjb}
735178481Sjb
736178481Sjbstatic tdesc_t *
737178481Sjbconjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
738178481Sjb{
739178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
740178481Sjb
741178481Sjb	(void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd);
742178481Sjb
743178481Sjb	return (new);
744178481Sjb}
745178481Sjb
746178481Sjbstatic tdesc_t *
747178481Sjbconjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
748178481Sjb{
749178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
750178481Sjb	fndef_t *nfn = xmalloc(sizeof (fndef_t));
751178481Sjb	fndef_t *ofn = old->t_fndef;
752178481Sjb	int i;
753178481Sjb
754178481Sjb	(void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd);
755178481Sjb
756178481Sjb	nfn->fn_nargs = ofn->fn_nargs;
757178481Sjb	nfn->fn_vargs = ofn->fn_vargs;
758178481Sjb
759178481Sjb	if (nfn->fn_nargs > 0)
760178481Sjb		nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs);
761178481Sjb
762178546Sjb	for (i = 0; i < (int) ofn->fn_nargs; i++) {
763178481Sjb		(void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id,
764178481Sjb		    new, mcd);
765178481Sjb	}
766178481Sjb
767178481Sjb	new->t_fndef = nfn;
768178481Sjb
769178481Sjb	return (new);
770178481Sjb}
771178481Sjb
772178481Sjbstatic tdesc_t *
773178481Sjbconjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
774178481Sjb{
775178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
776178481Sjb	ardef_t *nar = xmalloc(sizeof (ardef_t));
777178481Sjb	ardef_t *oar = old->t_ardef;
778178481Sjb
779178481Sjb	(void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new,
780178481Sjb	    mcd);
781178481Sjb	(void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new,
782178481Sjb	    mcd);
783178481Sjb
784178481Sjb	nar->ad_nelems = oar->ad_nelems;
785178481Sjb
786178481Sjb	new->t_ardef = nar;
787178481Sjb
788178481Sjb	return (new);
789178481Sjb}
790178481Sjb
791178481Sjbstatic tdesc_t *
792178481Sjbconjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
793178481Sjb{
794178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
795178481Sjb	mlist_t *omem, **nmemp;
796178481Sjb
797178481Sjb	for (omem = old->t_members, nmemp = &new->t_members;
798178481Sjb	    omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) {
799178481Sjb		*nmemp = xmalloc(sizeof (mlist_t));
800178481Sjb		(*nmemp)->ml_offset = omem->ml_offset;
801178481Sjb		(*nmemp)->ml_size = omem->ml_size;
802178546Sjb		(*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name");
803178481Sjb		(void) remap_node(&((*nmemp)->ml_type), omem->ml_type,
804178481Sjb		    old->t_id, new, mcd);
805178481Sjb	}
806178481Sjb	*nmemp = NULL;
807178481Sjb
808178481Sjb	return (new);
809178481Sjb}
810178481Sjb
811178481Sjb/*ARGSUSED2*/
812178481Sjbstatic tdesc_t *
813178546Sjbconjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused)
814178481Sjb{
815178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
816178481Sjb	elist_t *oel, **nelp;
817178481Sjb
818178481Sjb	for (oel = old->t_emem, nelp = &new->t_emem;
819178481Sjb	    oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) {
820178481Sjb		*nelp = xmalloc(sizeof (elist_t));
821178481Sjb		(*nelp)->el_name = xstrdup(oel->el_name);
822178481Sjb		(*nelp)->el_number = oel->el_number;
823178481Sjb	}
824178481Sjb	*nelp = NULL;
825178481Sjb
826178481Sjb	return (new);
827178481Sjb}
828178481Sjb
829178481Sjb/*ARGSUSED2*/
830178481Sjbstatic tdesc_t *
831178481Sjbconjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
832178481Sjb{
833178481Sjb	tdesc_t *new = conjure_template(old, newselfid);
834178481Sjb
835178481Sjb	list_add(&mcd->md_tgt->td_fwdlist, new);
836178481Sjb
837178481Sjb	return (new);
838178481Sjb}
839178481Sjb
840178481Sjb/*ARGSUSED*/
841178481Sjbstatic tdesc_t *
842178546Sjbconjure_assert(tdesc_t *old __unused, int newselfid __unused, merge_cb_data_t *mcd __unused)
843178481Sjb{
844178481Sjb	assert(1 == 0);
845178481Sjb	return (NULL);
846178481Sjb}
847178481Sjb
848178481Sjbstatic iidesc_t *
849178481Sjbconjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd)
850178481Sjb{
851178481Sjb	iidesc_t *new = iidesc_dup(old);
852178481Sjb	int i;
853178481Sjb
854178481Sjb	(void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd);
855178481Sjb	for (i = 0; i < new->ii_nargs; i++) {
856178481Sjb		(void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL,
857178481Sjb		    mcd);
858178481Sjb	}
859178481Sjb
860178481Sjb	return (new);
861178481Sjb}
862178481Sjb
863178481Sjbstatic int
864178481Sjbfwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private)
865178481Sjb{
866178481Sjb	alist_t *map = private;
867178546Sjb	void *defn;
868178481Sjb
869178481Sjb	if (!alist_find(map, (void *)fwd, (void **)&defn))
870178481Sjb		return (0);
871178481Sjb
872178481Sjb	debug(3, "Redirecting an edge to %s\n", tdesc_name(defn));
873178481Sjb
874178481Sjb	*fwdp = defn;
875178481Sjb
876178481Sjb	return (1);
877178481Sjb}
878178481Sjb
879178481Sjbstatic tdtrav_cb_f fwd_redir_cbs[] = {
880178481Sjb	NULL,
881178481Sjb	NULL,			/* intrinsic */
882178481Sjb	NULL,			/* pointer */
883178481Sjb	NULL,			/* array */
884178481Sjb	NULL,			/* function */
885178481Sjb	NULL,			/* struct */
886178481Sjb	NULL,			/* union */
887178481Sjb	NULL,			/* enum */
888178481Sjb	fwd_redir,		/* forward */
889178481Sjb	NULL,			/* typedef */
890178481Sjb	tdtrav_assert,		/* typedef_unres */
891178481Sjb	NULL,			/* volatile */
892178481Sjb	NULL,			/* const */
893178481Sjb	NULL			/* restrict */
894178481Sjb};
895178481Sjb
896178481Sjbtypedef struct redir_mstr_data {
897178481Sjb	tdata_t *rmd_tgt;
898178481Sjb	alist_t *rmd_map;
899178481Sjb} redir_mstr_data_t;
900178481Sjb
901178481Sjbstatic int
902178481Sjbredir_mstr_fwd_cb(void *name, void *value, void *arg)
903178481Sjb{
904178481Sjb	tdesc_t *fwd = name;
905178546Sjb	int defnid = (uintptr_t)value;
906178481Sjb	redir_mstr_data_t *rmd = arg;
907178481Sjb	tdesc_t template;
908178481Sjb	tdesc_t *defn;
909178481Sjb
910178481Sjb	template.t_id = defnid;
911178481Sjb
912178481Sjb	if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template,
913178481Sjb	    (void *)&defn)) {
914178481Sjb		aborterr("Couldn't unforward %d (%s)\n", defnid,
915178481Sjb		    tdesc_name(defn));
916178481Sjb	}
917178481Sjb
918178481Sjb	debug(3, "Forward map: resolved %d to %s\n", defnid, tdesc_name(defn));
919178481Sjb
920178481Sjb	alist_add(rmd->rmd_map, (void *)fwd, (void *)defn);
921178481Sjb
922178481Sjb	return (1);
923178481Sjb}
924178481Sjb
925178481Sjbstatic void
926178481Sjbredir_mstr_fwds(merge_cb_data_t *mcd)
927178481Sjb{
928178481Sjb	redir_mstr_data_t rmd;
929178481Sjb	alist_t *map = alist_new(NULL, NULL);
930178481Sjb
931178481Sjb	rmd.rmd_tgt = mcd->md_tgt;
932178481Sjb	rmd.rmd_map = map;
933178481Sjb
934178481Sjb	if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) {
935178481Sjb		(void) iitraverse_hash(mcd->md_tgt->td_iihash,
936178481Sjb		    &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map);
937178481Sjb	}
938178481Sjb
939178481Sjb	alist_free(map);
940178481Sjb}
941178481Sjb
942178481Sjbstatic int
943178481Sjbadd_iitba_cb(void *data, void *private)
944178481Sjb{
945178481Sjb	merge_cb_data_t *mcd = private;
946178481Sjb	iidesc_t *tba = data;
947178481Sjb	iidesc_t *new;
948178481Sjb	iifind_data_t iif;
949178481Sjb	int newidx;
950178481Sjb
951178481Sjb	newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id);
952178481Sjb	assert(newidx != -1);
953178481Sjb
954178481Sjb	(void) list_remove(mcd->md_iitba, data, NULL, NULL);
955178481Sjb
956178481Sjb	iif.iif_template = tba;
957178481Sjb	iif.iif_ta = mcd->md_ta;
958178481Sjb	iif.iif_newidx = newidx;
959178481Sjb	iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
960178481Sjb
961178481Sjb	if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match,
962178481Sjb	    &iif) == 1) {
963178481Sjb		debug(3, "iidesc_t %s already exists\n",
964178481Sjb		    (tba->ii_name ? tba->ii_name : "(anon)"));
965178481Sjb		return (1);
966178481Sjb	}
967178481Sjb
968178481Sjb	new = conjure_iidesc(tba, mcd);
969178481Sjb	hash_add(mcd->md_tgt->td_iihash, new);
970178481Sjb
971178481Sjb	return (1);
972178481Sjb}
973178481Sjb
974178481Sjbstatic int
975178481Sjbadd_tdesc(tdesc_t *oldtdp, int newid, merge_cb_data_t *mcd)
976178481Sjb{
977178481Sjb	tdesc_t *newtdp;
978178481Sjb	tdesc_t template;
979178481Sjb
980178481Sjb	template.t_id = newid;
981178481Sjb	assert(hash_find(mcd->md_parent->td_idhash,
982178481Sjb	    (void *)&template, NULL) == 0);
983178481Sjb
984178546Sjb	debug(3, "trying to conjure %d %s (%d, <%x>) as %d, <%x>\n",
985178546Sjb	    oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id,
986178546Sjb	    oldtdp->t_id, newid, newid);
987178481Sjb
988178481Sjb	if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid,
989178481Sjb	    mcd)) == NULL)
990178481Sjb		/* couldn't map everything */
991178481Sjb		return (0);
992178481Sjb
993178481Sjb	debug(3, "succeeded\n");
994178481Sjb
995178481Sjb	hash_add(mcd->md_tgt->td_idhash, newtdp);
996178481Sjb	hash_add(mcd->md_tgt->td_layouthash, newtdp);
997178481Sjb
998178481Sjb	return (1);
999178481Sjb}
1000178481Sjb
1001178481Sjbstatic int
1002178481Sjbadd_tdtba_cb(void *data, void *arg)
1003178481Sjb{
1004178481Sjb	tdesc_t *tdp = data;
1005178481Sjb	merge_cb_data_t *mcd = arg;
1006178481Sjb	int newid;
1007178481Sjb	int rc;
1008178481Sjb
1009178481Sjb	newid = get_mapping(mcd->md_ta, tdp->t_id);
1010178481Sjb	assert(newid != -1);
1011178481Sjb
1012178481Sjb	if ((rc = add_tdesc(tdp, newid, mcd)))
1013178481Sjb		hash_remove(mcd->md_tdtba, (void *)tdp);
1014178481Sjb
1015178481Sjb	return (rc);
1016178481Sjb}
1017178481Sjb
1018178481Sjbstatic int
1019178481Sjbadd_tdtbr_cb(void *data, void *arg)
1020178481Sjb{
1021178481Sjb	tdesc_t **tdpp = data;
1022178481Sjb	merge_cb_data_t *mcd = arg;
1023178481Sjb
1024178481Sjb	debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id);
1025178481Sjb
1026178481Sjb	if (!remap_node(tdpp, *tdpp, -1, NULL, mcd))
1027178481Sjb		return (0);
1028178481Sjb
1029178481Sjb	(void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL);
1030178481Sjb	return (1);
1031178481Sjb}
1032178481Sjb
1033178481Sjbstatic void
1034178481Sjbmerge_types(hash_t *src, merge_cb_data_t *mcd)
1035178481Sjb{
1036178481Sjb	list_t *iitba = NULL;
1037178481Sjb	list_t *tdtbr = NULL;
1038178481Sjb	int iirc, tdrc;
1039178481Sjb
1040178481Sjb	mcd->md_iitba = &iitba;
1041178481Sjb	mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
1042178481Sjb	    tdesc_layoutcmp);
1043178481Sjb	mcd->md_tdtbr = &tdtbr;
1044178481Sjb
1045178481Sjb	(void) hash_iter(src, merge_type_cb, mcd);
1046178481Sjb
1047178546Sjb	tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, mcd);
1048178481Sjb	debug(3, "add_tdtba_cb added %d items\n", tdrc);
1049178481Sjb
1050178546Sjb	iirc = list_iter(*mcd->md_iitba, add_iitba_cb, mcd);
1051178481Sjb	debug(3, "add_iitba_cb added %d items\n", iirc);
1052178481Sjb
1053178481Sjb	assert(list_count(*mcd->md_iitba) == 0 &&
1054178481Sjb	    hash_count(mcd->md_tdtba) == 0);
1055178481Sjb
1056178546Sjb	tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, mcd);
1057178481Sjb	debug(3, "add_tdtbr_cb added %d items\n", tdrc);
1058178481Sjb
1059178481Sjb	if (list_count(*mcd->md_tdtbr) != 0)
1060178481Sjb		aborterr("Couldn't remap all nodes\n");
1061178481Sjb
1062178481Sjb	/*
1063178481Sjb	 * We now have an alist of master forwards and the ids of the new master
1064178481Sjb	 * definitions for those forwards in mcd->md_fdida.  By this point,
1065178481Sjb	 * we're guaranteed that all of the master definitions referenced in
1066178481Sjb	 * fdida have been added to the master tree.  We now traverse through
1067178481Sjb	 * the master tree, redirecting all edges inbound to forwards that have
1068178481Sjb	 * definitions to those definitions.
1069178481Sjb	 */
1070178481Sjb	if (mcd->md_parent == mcd->md_tgt) {
1071178481Sjb		redir_mstr_fwds(mcd);
1072178481Sjb	}
1073178481Sjb}
1074178481Sjb
1075178481Sjbvoid
1076178481Sjbmerge_into_master(tdata_t *cur, tdata_t *mstr, tdata_t *tgt, int selfuniquify)
1077178481Sjb{
1078178481Sjb	merge_cb_data_t mcd;
1079178481Sjb
1080178481Sjb	cur->td_ref++;
1081178481Sjb	mstr->td_ref++;
1082178481Sjb	if (tgt)
1083178481Sjb		tgt->td_ref++;
1084178481Sjb
1085178481Sjb	assert(cur->td_ref == 1 && mstr->td_ref == 1 &&
1086178481Sjb	    (tgt == NULL || tgt->td_ref == 1));
1087178481Sjb
1088178481Sjb	mcd.md_parent = mstr;
1089178481Sjb	mcd.md_tgt = (tgt ? tgt : mstr);
1090178481Sjb	mcd.md_ta = alist_new(NULL, NULL);
1091178481Sjb	mcd.md_fdida = alist_new(NULL, NULL);
1092178481Sjb	mcd.md_flags = 0;
1093178481Sjb
1094178481Sjb	if (selfuniquify)
1095178481Sjb		mcd.md_flags |= MCD_F_SELFUNIQUIFY;
1096178481Sjb	if (tgt)
1097178481Sjb		mcd.md_flags |= MCD_F_REFMERGE;
1098178481Sjb
1099178481Sjb	mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen);
1100178481Sjb	mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark);
1101178481Sjb
1102178481Sjb	merge_types(cur->td_iihash, &mcd);
1103178481Sjb
1104178481Sjb	if (debug_level >= 3) {
1105178481Sjb		debug(3, "Type association stats\n");
1106178481Sjb		alist_stats(mcd.md_ta, 0);
1107178481Sjb		debug(3, "Layout hash stats\n");
1108178481Sjb		hash_stats(mcd.md_tgt->td_layouthash, 1);
1109178481Sjb	}
1110178481Sjb
1111178481Sjb	alist_free(mcd.md_fdida);
1112178481Sjb	alist_free(mcd.md_ta);
1113178481Sjb
1114178481Sjb	cur->td_ref--;
1115178481Sjb	mstr->td_ref--;
1116178481Sjb	if (tgt)
1117178481Sjb		tgt->td_ref--;
1118178481Sjb}
1119178481Sjb
1120178481Sjbtdesc_ops_t tdesc_ops[] = {
1121178481Sjb	{ "ERROR! BAD tdesc TYPE", NULL, NULL },
1122178481Sjb	{ "intrinsic",		equiv_intrinsic,	conjure_intrinsic },
1123178481Sjb	{ "pointer", 		equiv_plain,		conjure_plain },
1124178481Sjb	{ "array", 		equiv_array,		conjure_array },
1125178481Sjb	{ "function", 		equiv_function,		conjure_function },
1126178481Sjb	{ "struct",		equiv_su,		conjure_su },
1127178481Sjb	{ "union",		equiv_su,		conjure_su },
1128178481Sjb	{ "enum",		equiv_enum,		conjure_enum },
1129178481Sjb	{ "forward",		NULL,			conjure_forward },
1130178481Sjb	{ "typedef",		equiv_plain,		conjure_plain },
1131178481Sjb	{ "typedef_unres",	equiv_assert,		conjure_assert },
1132178481Sjb	{ "volatile",		equiv_plain,		conjure_plain },
1133178481Sjb	{ "const", 		equiv_plain,		conjure_plain },
1134178481Sjb	{ "restrict",		equiv_plain,		conjure_plain }
1135178481Sjb};
1136