1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21 /*
22 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #pragma ident "%Z%%M% %I% %E% SMI"
27
28 /*
29 * This file contains routines that merge one tdata_t tree, called the child,
30 * into another, called the parent. Note that these names are used mainly for
31 * convenience and to represent the direction of the merge. They are not meant
32 * to imply any relationship between the tdata_t graphs prior to the merge.
33 *
34 * tdata_t structures contain two main elements - a hash of iidesc_t nodes, and
35 * a directed graph of tdesc_t nodes, pointed to by the iidesc_t nodes. Simply
36 * put, we merge the tdesc_t graphs, followed by the iidesc_t nodes, and then we
37 * clean up loose ends.
38 *
39 * The algorithm is as follows:
40 *
41 * 1. Mapping iidesc_t nodes
42 *
43 * For each child iidesc_t node, we first try to map its tdesc_t subgraph
44 * against the tdesc_t graph in the parent. For each node in the child subgraph
45 * that exists in the parent, a mapping between the two (between their type IDs)
46 * is established. For the child nodes that cannot be mapped onto existing
47 * parent nodes, a mapping is established between the child node ID and a
48 * newly-allocated ID that the node will use when it is re-created in the
49 * parent. These unmappable nodes are added to the md_tdtba (tdesc_t To Be
50 * Added) hash, which tracks nodes that need to be created in the parent.
51 *
52 * If all of the nodes in the subgraph for an iidesc_t in the child can be
53 * mapped to existing nodes in the parent, then we can try to map the child
54 * iidesc_t onto an iidesc_t in the parent. If we cannot find an equivalent
55 * iidesc_t, or if we were not able to completely map the tdesc_t subgraph(s),
56 * then we add this iidesc_t to the md_iitba (iidesc_t To Be Added) list. This
57 * list tracks iidesc_t nodes that are to be created in the parent.
58 *
59 * While visiting the tdesc_t nodes, we may discover a forward declaration (a
60 * FORWARD tdesc_t) in the parent that is resolved in the child. That is, there
61 * may be a structure or union definition in the child with the same name as the
62 * forward declaration in the parent. If we find such a node, we record an
63 * association in the md_fdida (Forward => Definition ID Association) list
64 * between the parent ID of the forward declaration and the ID that the
65 * definition will use when re-created in the parent.
66 *
67 * 2. Creating new tdesc_t nodes (the md_tdtba hash)
68 *
69 * We have now attempted to map all tdesc_t nodes from the child into the
70 * parent, and have, in md_tdtba, a hash of all tdesc_t nodes that need to be
71 * created (or, as we so wittily call it, conjured) in the parent. We iterate
72 * through this hash, creating the indicated tdesc_t nodes. For a given tdesc_t
73 * node, conjuring requires two steps - the copying of the common tdesc_t data
74 * (name, type, etc) from the child node, and the creation of links from the
75 * newly-created node to the parent equivalents of other tdesc_t nodes pointed
76 * to by node being conjured. Note that in some cases, the targets of these
77 * links will be on the md_tdtba hash themselves, and may not have been created
78 * yet. As such, we can't establish the links from these new nodes into the
79 * parent graph. We therefore conjure them with links to nodes in the *child*
80 * graph, and add pointers to the links to be created to the md_tdtbr (tdesc_t
81 * To Be Remapped) hash. For example, a POINTER tdesc_t that could not be
82 * resolved would have its &tdesc_t->t_tdesc added to md_tdtbr.
83 *
84 * 3. Creating new iidesc_t nodes (the md_iitba list)
85 *
86 * When we have completed step 2, all tdesc_t nodes have been created (or
87 * already existed) in the parent. Some of them may have incorrect links (the
88 * members of the md_tdtbr list), but they've all been created. As such, we can
89 * create all of the iidesc_t nodes, as we can attach the tdesc_t subgraph
90 * pointers correctly. We create each node, and attach the pointers to the
91 * appropriate parts of the parent tdesc_t graph.
92 *
93 * 4. Resolving newly-created tdesc_t node links (the md_tdtbr list)
94 *
95 * As in step 3, we rely on the fact that all of the tdesc_t nodes have been
96 * created. Each entry in the md_tdtbr list is a pointer to where a link into
97 * the parent will be established. As saved in the md_tdtbr list, these
98 * pointers point into the child tdesc_t subgraph. We can thus get the target
99 * type ID from the child, look at the ID mapping to determine the desired link
100 * target, and redirect the link accordingly.
101 *
102 * 5. Parent => child forward declaration resolution
103 *
104 * If entries were made in the md_fdida list in step 1, we have forward
105 * declarations in the parent that need to be resolved to their definitions
106 * re-created in step 2 from the child. Using the md_fdida list, we can locate
107 * the definition for the forward declaration, and we can redirect all inbound
108 * edges to the forward declaration node to the actual definition.
109 *
110 * A pox on the house of anyone who changes the algorithm without updating
111 * this comment.
112 */
113
114 #if HAVE_NBTOOL_CONFIG_H
115 # include "nbtool_config.h"
116 #endif
117
118 #include <stdio.h>
119 #include <strings.h>
120 #include <assert.h>
121 #include <pthread.h>
122
123 #include "ctf_headers.h"
124 #include "ctftools.h"
125 #include "list.h"
126 #include "alist.h"
127 #include "memory.h"
128 #include "traverse.h"
129
130 typedef struct equiv_data equiv_data_t;
131 typedef struct merge_cb_data merge_cb_data_t;
132
133 /*
134 * There are two traversals in this file, for equivalency and for tdesc_t
135 * re-creation, that do not fit into the tdtraverse() framework. We have our
136 * own traversal mechanism and ops vector here for those two cases.
137 */
138 typedef struct tdesc_ops {
139 const char *name;
140 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *);
141 tdesc_t *(*conjure)(tdesc_t *, int, merge_cb_data_t *);
142 } tdesc_ops_t;
143 extern tdesc_ops_t tdesc_ops[];
144
145 /*
146 * The workhorse structure of tdata_t merging. Holds all lists of nodes to be
147 * processed during various phases of the merge algorithm.
148 */
149 struct merge_cb_data {
150 tdata_t *md_parent;
151 tdata_t *md_tgt;
152 alist_t *md_ta; /* Type Association */
153 alist_t *md_fdida; /* Forward -> Definition ID Association */
154 list_t **md_iitba; /* iidesc_t nodes To Be Added to the parent */
155 hash_t *md_tdtba; /* tdesc_t nodes To Be Added to the parent */
156 list_t **md_tdtbr; /* tdesc_t nodes To Be Remapped */
157 int md_flags;
158 }; /* merge_cb_data_t */
159
160 /*
161 * When we first create a tdata_t from stabs data, we will have duplicate nodes.
162 * Normal merges, however, assume that the child tdata_t is already self-unique,
163 * and for speed reasons do not attempt to self-uniquify. If this flag is set,
164 * the merge algorithm will self-uniquify by avoiding the insertion of
165 * duplicates in the md_tdtdba list.
166 */
167 #define MCD_F_SELFUNIQUIFY 0x1
168
169 /*
170 * When we merge the CTF data for the modules, we don't want it to contain any
171 * data that can be found in the reference module (usually genunix). If this
172 * flag is set, we're doing a merge between the fully merged tdata_t for this
173 * module and the tdata_t for the reference module, with the data unique to this
174 * module ending up in a third tdata_t. It is this third tdata_t that will end
175 * up in the .SUNW_ctf section for the module.
176 */
177 #define MCD_F_REFMERGE 0x2
178
179 /*
180 * Mapping of child type IDs to parent type IDs
181 */
182
183 static void
add_mapping(alist_t * ta,tid_t srcid,tid_t tgtid)184 add_mapping(alist_t *ta, tid_t srcid, tid_t tgtid)
185 {
186 debug(3, "Adding mapping %u <%x> => %u <%x>\n", srcid, srcid, tgtid, tgtid);
187
188 assert(!alist_find(ta, (void *)(uintptr_t)srcid, NULL));
189 assert(srcid != 0 && tgtid != 0);
190
191 alist_add(ta, (void *)(uintptr_t)srcid, (void *)(uintptr_t)tgtid);
192 }
193
194 static tid_t
get_mapping(alist_t * ta,int srcid)195 get_mapping(alist_t *ta, int srcid)
196 {
197 void *ltgtid;
198
199 if (alist_find(ta, (void *)(uintptr_t)srcid, (void **)<gtid))
200 return ((uintptr_t)ltgtid);
201 else
202 return (0);
203 }
204
205 /*
206 * Determining equivalence of tdesc_t subgraphs
207 */
208
209 struct equiv_data {
210 alist_t *ed_ta;
211 tdesc_t *ed_node;
212 tdesc_t *ed_tgt;
213
214 int ed_clear_mark;
215 int ed_cur_mark;
216 int ed_selfuniquify;
217 }; /* equiv_data_t */
218
219 static int equiv_node(tdesc_t *, tdesc_t *, equiv_data_t *);
220
221 /*ARGSUSED2*/
222 static int
equiv_intrinsic(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed __unused)223 equiv_intrinsic(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused)
224 {
225 intr_t *si = stdp->t_intr;
226 intr_t *ti = ttdp->t_intr;
227
228 if (si->intr_type != ti->intr_type ||
229 si->intr_signed != ti->intr_signed ||
230 si->intr_offset != ti->intr_offset ||
231 si->intr_nbits != ti->intr_nbits)
232 return (0);
233
234 if (si->intr_type == INTR_INT &&
235 si->intr_iformat != ti->intr_iformat)
236 return (0);
237 else if (si->intr_type == INTR_REAL &&
238 si->intr_fformat != ti->intr_fformat)
239 return (0);
240
241 return (1);
242 }
243
244 static int
equiv_plain(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)245 equiv_plain(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
246 {
247 return (equiv_node(stdp->t_tdesc, ttdp->t_tdesc, ed));
248 }
249
250 static int
equiv_function(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)251 equiv_function(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
252 {
253 fndef_t *fn1 = stdp->t_fndef, *fn2 = ttdp->t_fndef;
254 int i;
255
256 if (fn1->fn_nargs != fn2->fn_nargs ||
257 fn1->fn_vargs != fn2->fn_vargs)
258 return (0);
259
260 if (!equiv_node(fn1->fn_ret, fn2->fn_ret, ed))
261 return (0);
262
263 for (i = 0; i < (int) fn1->fn_nargs; i++) {
264 if (!equiv_node(fn1->fn_args[i], fn2->fn_args[i], ed))
265 return (0);
266 }
267
268 return (1);
269 }
270
271 static int
equiv_array(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)272 equiv_array(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
273 {
274 ardef_t *ar1 = stdp->t_ardef, *ar2 = ttdp->t_ardef;
275
276 if (!equiv_node(ar1->ad_contents, ar2->ad_contents, ed) ||
277 !equiv_node(ar1->ad_idxtype, ar2->ad_idxtype, ed))
278 return (0);
279
280 if (ar1->ad_nelems != ar2->ad_nelems)
281 return (0);
282
283 return (1);
284 }
285
286 static int
equiv_su(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed)287 equiv_su(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed)
288 {
289 mlist_t *ml1 = stdp->t_members, *ml2 = ttdp->t_members;
290 mlist_t *olm1 = NULL;
291
292 while (ml1 && ml2) {
293 if (ml1->ml_offset != ml2->ml_offset ||
294 strcmp(ml1->ml_name, ml2->ml_name) != 0)
295 return (0);
296
297 /*
298 * Don't do the recursive equivalency checking more than
299 * we have to.
300 */
301 if (olm1 == NULL || olm1->ml_type->t_id != ml1->ml_type->t_id) {
302 if (ml1->ml_size != ml2->ml_size ||
303 !equiv_node(ml1->ml_type, ml2->ml_type, ed))
304 return (0);
305 }
306
307 olm1 = ml1;
308 ml1 = ml1->ml_next;
309 ml2 = ml2->ml_next;
310 }
311
312 if (ml1 || ml2)
313 return (0);
314
315 return (1);
316 }
317
318 /*ARGSUSED2*/
319 static int
equiv_enum(tdesc_t * stdp,tdesc_t * ttdp,equiv_data_t * ed __unused)320 equiv_enum(tdesc_t *stdp, tdesc_t *ttdp, equiv_data_t *ed __unused)
321 {
322 elist_t *el1 = stdp->t_emem;
323 elist_t *el2 = ttdp->t_emem;
324
325 while (el1 && el2) {
326 if (el1->el_number != el2->el_number ||
327 strcmp(el1->el_name, el2->el_name) != 0)
328 return (0);
329
330 el1 = el1->el_next;
331 el2 = el2->el_next;
332 }
333
334 if (el1 || el2)
335 return (0);
336
337 return (1);
338 }
339
340 /*ARGSUSED*/
341 static int
equiv_assert(tdesc_t * stdp __unused,tdesc_t * ttdp __unused,equiv_data_t * ed __unused)342 equiv_assert(tdesc_t *stdp __unused, tdesc_t *ttdp __unused, equiv_data_t *ed __unused)
343 {
344 /* foul, evil, and very bad - this is a "shouldn't happen" */
345 assert(1 == 0);
346
347 return (0);
348 }
349
350 static int
fwd_equiv(tdesc_t * ctdp,tdesc_t * mtdp)351 fwd_equiv(tdesc_t *ctdp, tdesc_t *mtdp)
352 {
353 tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp);
354
355 return (defn->t_type == STRUCT || defn->t_type == UNION);
356 }
357
358 static int
equiv_node(tdesc_t * ctdp,tdesc_t * mtdp,equiv_data_t * ed)359 equiv_node(tdesc_t *ctdp, tdesc_t *mtdp, equiv_data_t *ed)
360 {
361 int (*equiv)(tdesc_t *, tdesc_t *, equiv_data_t *);
362 int mapping;
363
364 if (ctdp->t_emark > ed->ed_clear_mark &&
365 mtdp->t_emark > ed->ed_clear_mark)
366 return (ctdp->t_emark == mtdp->t_emark);
367
368 /*
369 * In normal (non-self-uniquify) mode, we don't want to do equivalency
370 * checking on a subgraph that has already been checked. If a mapping
371 * has already been established for a given child node, we can simply
372 * compare the mapping for the child node with the ID of the parent
373 * node. If we are in self-uniquify mode, then we're comparing two
374 * subgraphs within the child graph, and thus need to ignore any
375 * type mappings that have been created, as they are only valid into the
376 * parent.
377 */
378 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 &&
379 mapping == mtdp->t_id && !ed->ed_selfuniquify)
380 return (1);
381
382 if (!streq(ctdp->t_name, mtdp->t_name))
383 return (0);
384
385 if (ctdp->t_type != mtdp->t_type) {
386 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD)
387 return (fwd_equiv(ctdp, mtdp));
388 else
389 return (0);
390 }
391
392 ctdp->t_emark = ed->ed_cur_mark;
393 mtdp->t_emark = ed->ed_cur_mark;
394 ed->ed_cur_mark++;
395
396 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL)
397 return (equiv(ctdp, mtdp, ed));
398
399 return (1);
400 }
401
402 /*
403 * We perform an equivalency check on two subgraphs by traversing through them
404 * in lockstep. If a given node is equivalent in both the parent and the child,
405 * we mark it in both subgraphs, using the t_emark field, with a monotonically
406 * increasing number. If, in the course of the traversal, we reach a node that
407 * we have visited and numbered during this equivalency check, we have a cycle.
408 * If the previously-visited nodes don't have the same emark, then the edges
409 * that brought us to these nodes are not equivalent, and so the check ends.
410 * If the emarks are the same, the edges are equivalent. We then backtrack and
411 * continue the traversal. If we have exhausted all edges in the subgraph, and
412 * have not found any inequivalent nodes, then the subgraphs are equivalent.
413 */
414 static int
equiv_cb(void * bucket,void * arg)415 equiv_cb(void *bucket, void *arg)
416 {
417 equiv_data_t *ed = arg;
418 tdesc_t *mtdp = bucket;
419 tdesc_t *ctdp = ed->ed_node;
420
421 ed->ed_clear_mark = ed->ed_cur_mark + 1;
422 ed->ed_cur_mark = ed->ed_clear_mark + 1;
423
424 if (equiv_node(ctdp, mtdp, ed)) {
425 debug(3, "equiv_node matched %d <%x> %d <%x>\n",
426 ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id);
427 ed->ed_tgt = mtdp;
428 /* matched. stop looking */
429 return (-1);
430 }
431
432 return (0);
433 }
434
435 /*ARGSUSED1*/
436 static int
map_td_tree_pre(tdesc_t * ctdp,tdesc_t ** ctdpp __unused,void * private)437 map_td_tree_pre(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
438 {
439 merge_cb_data_t *mcd = private;
440
441 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0)
442 return (0);
443
444 return (1);
445 }
446
447 /*ARGSUSED1*/
448 static int
map_td_tree_post(tdesc_t * ctdp,tdesc_t ** ctdpp __unused,void * private)449 map_td_tree_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
450 {
451 merge_cb_data_t *mcd = private;
452 equiv_data_t ed;
453
454 ed.ed_ta = mcd->md_ta;
455 ed.ed_clear_mark = mcd->md_parent->td_curemark;
456 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
457 ed.ed_node = ctdp;
458 ed.ed_selfuniquify = 0;
459
460 debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp));
461
462 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp,
463 equiv_cb, &ed) < 0) {
464 /* We found an equivalent node */
465 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) {
466 int id = mcd->md_tgt->td_nextid++;
467
468 debug(3, "Creating new defn type %d <%x>\n", id, id);
469 add_mapping(mcd->md_ta, ctdp->t_id, id);
470 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt,
471 (void *)(ulong_t)id);
472 hash_add(mcd->md_tdtba, ctdp);
473 } else
474 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id);
475
476 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash,
477 equiv_cb, &ed) < 0) {
478 /*
479 * We didn't find an equivalent node by looking through the
480 * layout hash, but we somehow found it by performing an
481 * exhaustive search through the entire graph. This usually
482 * means that the "name" hash function is broken.
483 */
484 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id,
485 tdesc_name(ctdp), ed.ed_tgt->t_id);
486 } else {
487 int id = mcd->md_tgt->td_nextid++;
488
489 debug(3, "Creating new type %d <%x>\n", id, id);
490 add_mapping(mcd->md_ta, ctdp->t_id, id);
491 hash_add(mcd->md_tdtba, ctdp);
492 }
493
494 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
495
496 return (1);
497 }
498
499 /*ARGSUSED1*/
500 static int
map_td_tree_self_post(tdesc_t * ctdp,tdesc_t ** ctdpp __unused,void * private)501 map_td_tree_self_post(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
502 {
503 merge_cb_data_t *mcd = private;
504 equiv_data_t ed;
505
506 ed.ed_ta = mcd->md_ta;
507 ed.ed_clear_mark = mcd->md_parent->td_curemark;
508 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1;
509 ed.ed_node = ctdp;
510 ed.ed_selfuniquify = 1;
511 ed.ed_tgt = NULL;
512
513 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) {
514 debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id,
515 ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id);
516 add_mapping(mcd->md_ta, ctdp->t_id,
517 get_mapping(mcd->md_ta, ed.ed_tgt->t_id));
518 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba,
519 equiv_cb, &ed) < 0) {
520 /*
521 * We didn't find an equivalent node using the quick way (going
522 * through the hash normally), but we did find it by iterating
523 * through the entire hash. This usually means that the hash
524 * function is broken.
525 */
526 aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n",
527 ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id,
528 ed.ed_tgt->t_id);
529 } else {
530 int id = mcd->md_tgt->td_nextid++;
531
532 debug(3, "Creating new type %d <%x>\n", id, id);
533 add_mapping(mcd->md_ta, ctdp->t_id, id);
534 hash_add(mcd->md_tdtba, ctdp);
535 }
536
537 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1;
538
539 return (1);
540 }
541
542 static tdtrav_cb_f map_pre[] = {
543 NULL,
544 map_td_tree_pre, /* intrinsic */
545 map_td_tree_pre, /* pointer */
546 map_td_tree_pre, /* reference */
547 map_td_tree_pre, /* array */
548 map_td_tree_pre, /* function */
549 map_td_tree_pre, /* struct */
550 map_td_tree_pre, /* union */
551 map_td_tree_pre, /* class */
552 map_td_tree_pre, /* enum */
553 map_td_tree_pre, /* forward */
554 map_td_tree_pre, /* typedef */
555 tdtrav_assert, /* typedef_unres */
556 map_td_tree_pre, /* volatile */
557 map_td_tree_pre, /* const */
558 map_td_tree_pre /* restrict */
559 };
560
561 static tdtrav_cb_f map_post[] = {
562 NULL,
563 map_td_tree_post, /* intrinsic */
564 map_td_tree_post, /* pointer */
565 map_td_tree_post, /* reference */
566 map_td_tree_post, /* array */
567 map_td_tree_post, /* function */
568 map_td_tree_post, /* struct */
569 map_td_tree_post, /* union */
570 map_td_tree_post, /* class */
571 map_td_tree_post, /* enum */
572 map_td_tree_post, /* forward */
573 map_td_tree_post, /* typedef */
574 tdtrav_assert, /* typedef_unres */
575 map_td_tree_post, /* volatile */
576 map_td_tree_post, /* const */
577 map_td_tree_post /* restrict */
578 };
579
580 static tdtrav_cb_f map_self_post[] = {
581 NULL,
582 map_td_tree_self_post, /* intrinsic */
583 map_td_tree_self_post, /* pointer */
584 map_td_tree_self_post, /* reference */
585 map_td_tree_self_post, /* array */
586 map_td_tree_self_post, /* function */
587 map_td_tree_self_post, /* struct */
588 map_td_tree_self_post, /* union */
589 map_td_tree_self_post, /* class */
590 map_td_tree_self_post, /* enum */
591 map_td_tree_self_post, /* forward */
592 map_td_tree_self_post, /* typedef */
593 tdtrav_assert, /* typedef_unres */
594 map_td_tree_self_post, /* volatile */
595 map_td_tree_self_post, /* const */
596 map_td_tree_self_post /* restrict */
597 };
598
599 /*
600 * Determining equivalence of iidesc_t nodes
601 */
602
603 typedef struct iifind_data {
604 iidesc_t *iif_template;
605 alist_t *iif_ta;
606 int iif_newidx;
607 int iif_refmerge;
608 } iifind_data_t;
609
610 /*
611 * Check to see if this iidesc_t (node) - the current one on the list we're
612 * iterating through - matches the target one (iif->iif_template). Return -1
613 * if it matches, to stop the iteration.
614 */
615 static int
iidesc_match(void * data,void * arg)616 iidesc_match(void *data, void *arg)
617 {
618 iidesc_t *node = data;
619 iifind_data_t *iif = arg;
620 int i;
621
622 if (node->ii_type != iif->iif_template->ii_type ||
623 !streq(node->ii_name, iif->iif_template->ii_name) ||
624 node->ii_dtype->t_id != iif->iif_newidx)
625 return (0);
626
627 if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) &&
628 !streq(node->ii_owner, iif->iif_template->ii_owner))
629 return (0);
630
631 if (node->ii_nargs != iif->iif_template->ii_nargs)
632 return (0);
633
634 for (i = 0; i < node->ii_nargs; i++) {
635 if (get_mapping(iif->iif_ta,
636 iif->iif_template->ii_args[i]->t_id) !=
637 node->ii_args[i]->t_id)
638 return (0);
639 }
640
641 if (iif->iif_refmerge) {
642 switch (iif->iif_template->ii_type) {
643 case II_GFUN:
644 case II_SFUN:
645 case II_GVAR:
646 case II_SVAR:
647 debug(3, "suppressing duping of %d %s from %s\n",
648 iif->iif_template->ii_type,
649 iif->iif_template->ii_name,
650 (iif->iif_template->ii_owner ?
651 iif->iif_template->ii_owner : "NULL"));
652 return (0);
653 case II_NOT:
654 case II_PSYM:
655 case II_SOU:
656 case II_TYPE:
657 break;
658 }
659 }
660
661 return (-1);
662 }
663
664 static int
merge_type_cb(void * data,void * arg)665 merge_type_cb(void *data, void *arg)
666 {
667 iidesc_t *sii = data;
668 merge_cb_data_t *mcd = arg;
669 iifind_data_t iif;
670 tdtrav_cb_f *post;
671
672 post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post);
673
674 /* Map the tdesc nodes */
675 (void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post,
676 mcd);
677
678 /* Map the iidesc nodes */
679 iif.iif_template = sii;
680 iif.iif_ta = mcd->md_ta;
681 iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id);
682 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
683
684 if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match,
685 &iif) == 1)
686 /* successfully mapped */
687 return (1);
688
689 debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"),
690 sii->ii_type);
691
692 list_add(mcd->md_iitba, sii);
693
694 return (0);
695 }
696
697 static int
remap_node(tdesc_t ** tgtp,tdesc_t * oldtgt,int selftid,tdesc_t * newself,merge_cb_data_t * mcd)698 remap_node(tdesc_t **tgtp, tdesc_t *oldtgt, int selftid, tdesc_t *newself,
699 merge_cb_data_t *mcd)
700 {
701 tdesc_t *tgt = NULL;
702 tdesc_t template;
703 int oldid = oldtgt->t_id;
704
705 if (oldid == selftid) {
706 *tgtp = newself;
707 return (1);
708 }
709
710 if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0)
711 aborterr("failed to get mapping for tid %d (%s) <%x>\n", oldid,
712 oldtgt->t_name, oldid);
713
714 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template,
715 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) ||
716 !hash_find(mcd->md_tgt->td_idhash, (void *)&template,
717 (void *)&tgt))) {
718 debug(3, "Remap couldn't find %d <%x> (from %d <%x>)\n", template.t_id,
719 template.t_id, oldid, oldid);
720 *tgtp = oldtgt;
721 list_add(mcd->md_tdtbr, tgtp);
722 return (0);
723 }
724
725 *tgtp = tgt;
726 return (1);
727 }
728
729 static tdesc_t *
conjure_template(tdesc_t * old,int newselfid)730 conjure_template(tdesc_t *old, int newselfid)
731 {
732 tdesc_t *new = xcalloc(sizeof (tdesc_t));
733
734 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL;
735 new->t_type = old->t_type;
736 new->t_size = old->t_size;
737 new->t_id = newselfid;
738 new->t_flags = old->t_flags;
739
740 return (new);
741 }
742
743 /*ARGSUSED2*/
744 static tdesc_t *
conjure_intrinsic(tdesc_t * old,int newselfid,merge_cb_data_t * mcd __unused)745 conjure_intrinsic(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused)
746 {
747 tdesc_t *new = conjure_template(old, newselfid);
748
749 new->t_intr = xmalloc(sizeof (intr_t));
750 bcopy(old->t_intr, new->t_intr, sizeof (intr_t));
751
752 return (new);
753 }
754
755 static tdesc_t *
conjure_plain(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)756 conjure_plain(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
757 {
758 tdesc_t *new = conjure_template(old, newselfid);
759
760 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd);
761
762 return (new);
763 }
764
765 static tdesc_t *
conjure_function(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)766 conjure_function(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
767 {
768 tdesc_t *new = conjure_template(old, newselfid);
769 fndef_t *nfn = xmalloc(sizeof (fndef_t));
770 fndef_t *ofn = old->t_fndef;
771 int i;
772
773 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd);
774
775 nfn->fn_nargs = ofn->fn_nargs;
776 nfn->fn_vargs = ofn->fn_vargs;
777
778 if (nfn->fn_nargs > 0)
779 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs);
780
781 for (i = 0; i < (int) ofn->fn_nargs; i++) {
782 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id,
783 new, mcd);
784 }
785
786 new->t_fndef = nfn;
787
788 return (new);
789 }
790
791 static tdesc_t *
conjure_array(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)792 conjure_array(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
793 {
794 tdesc_t *new = conjure_template(old, newselfid);
795 ardef_t *nar = xmalloc(sizeof (ardef_t));
796 ardef_t *oar = old->t_ardef;
797
798 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new,
799 mcd);
800 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new,
801 mcd);
802
803 nar->ad_nelems = oar->ad_nelems;
804
805 new->t_ardef = nar;
806
807 return (new);
808 }
809
810 static tdesc_t *
conjure_su(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)811 conjure_su(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
812 {
813 tdesc_t *new = conjure_template(old, newselfid);
814 mlist_t *omem, **nmemp;
815
816 for (omem = old->t_members, nmemp = &new->t_members;
817 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) {
818 *nmemp = xmalloc(sizeof (mlist_t));
819 (*nmemp)->ml_offset = omem->ml_offset;
820 (*nmemp)->ml_size = omem->ml_size;
821 (*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name");
822 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type,
823 old->t_id, new, mcd);
824 }
825 *nmemp = NULL;
826
827 return (new);
828 }
829
830 /*ARGSUSED2*/
831 static tdesc_t *
conjure_enum(tdesc_t * old,int newselfid,merge_cb_data_t * mcd __unused)832 conjure_enum(tdesc_t *old, int newselfid, merge_cb_data_t *mcd __unused)
833 {
834 tdesc_t *new = conjure_template(old, newselfid);
835 elist_t *oel, **nelp;
836
837 for (oel = old->t_emem, nelp = &new->t_emem;
838 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) {
839 *nelp = xmalloc(sizeof (elist_t));
840 (*nelp)->el_name = xstrdup(oel->el_name);
841 (*nelp)->el_number = oel->el_number;
842 }
843 *nelp = NULL;
844
845 return (new);
846 }
847
848 /*ARGSUSED2*/
849 static tdesc_t *
conjure_forward(tdesc_t * old,int newselfid,merge_cb_data_t * mcd)850 conjure_forward(tdesc_t *old, int newselfid, merge_cb_data_t *mcd)
851 {
852 tdesc_t *new = conjure_template(old, newselfid);
853
854 list_add(&mcd->md_tgt->td_fwdlist, new);
855
856 return (new);
857 }
858
859 /*ARGSUSED*/
860 static tdesc_t *
conjure_assert(tdesc_t * old __unused,int newselfid __unused,merge_cb_data_t * mcd __unused)861 conjure_assert(tdesc_t *old __unused, int newselfid __unused, merge_cb_data_t *mcd __unused)
862 {
863 assert(1 == 0);
864 return (NULL);
865 }
866
867 static iidesc_t *
conjure_iidesc(iidesc_t * old,merge_cb_data_t * mcd)868 conjure_iidesc(iidesc_t *old, merge_cb_data_t *mcd)
869 {
870 iidesc_t *new = iidesc_dup(old);
871 int i;
872
873 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd);
874 for (i = 0; i < new->ii_nargs; i++) {
875 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL,
876 mcd);
877 }
878
879 return (new);
880 }
881
882 static int
fwd_redir(tdesc_t * fwd,tdesc_t ** fwdp,void * private)883 fwd_redir(tdesc_t *fwd, tdesc_t **fwdp, void *private)
884 {
885 alist_t *map = private;
886 void *defn;
887
888 if (!alist_find(map, (void *)fwd, (void **)&defn))
889 return (0);
890
891 debug(3, "Redirecting an edge to %s\n", tdesc_name(defn));
892
893 *fwdp = defn;
894
895 return (1);
896 }
897
898 static tdtrav_cb_f fwd_redir_cbs[] = {
899 NULL,
900 NULL, /* intrinsic */
901 NULL, /* pointer */
902 NULL, /* reference */
903 NULL, /* array */
904 NULL, /* function */
905 NULL, /* struct */
906 NULL, /* union */
907 NULL, /* class */
908 NULL, /* enum */
909 fwd_redir, /* forward */
910 NULL, /* typedef */
911 tdtrav_assert, /* typedef_unres */
912 NULL, /* volatile */
913 NULL, /* const */
914 NULL /* restrict */
915 };
916
917 typedef struct redir_mstr_data {
918 tdata_t *rmd_tgt;
919 alist_t *rmd_map;
920 } redir_mstr_data_t;
921
922 static int
redir_mstr_fwd_cb(void * name,void * value,void * arg)923 redir_mstr_fwd_cb(void *name, void *value, void *arg)
924 {
925 tdesc_t *fwd = name;
926 int defnid = (uintptr_t)value;
927 redir_mstr_data_t *rmd = arg;
928 tdesc_t template;
929 tdesc_t *defn;
930
931 template.t_id = defnid;
932
933 if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template,
934 (void *)&defn)) {
935 aborterr("Couldn't unforward %d (%s)\n", defnid,
936 tdesc_name(defn));
937 }
938
939 debug(3, "Forward map: resolved %d to %s\n", defnid, tdesc_name(defn));
940
941 alist_add(rmd->rmd_map, (void *)fwd, (void *)defn);
942
943 return (1);
944 }
945
946 static void
redir_mstr_fwds(merge_cb_data_t * mcd)947 redir_mstr_fwds(merge_cb_data_t *mcd)
948 {
949 redir_mstr_data_t rmd;
950 alist_t *map = alist_new(NULL, NULL);
951
952 rmd.rmd_tgt = mcd->md_tgt;
953 rmd.rmd_map = map;
954
955 if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) {
956 (void) iitraverse_hash(mcd->md_tgt->td_iihash,
957 &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map);
958 }
959
960 alist_free(map);
961 }
962
963 static int
add_iitba_cb(void * data,void * private)964 add_iitba_cb(void *data, void *private)
965 {
966 merge_cb_data_t *mcd = private;
967 iidesc_t *tba = data;
968 iidesc_t *new;
969 iifind_data_t iif;
970 int newidx;
971
972 newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id);
973 assert(newidx != -1);
974
975 (void) list_remove(mcd->md_iitba, data, NULL, NULL);
976
977 iif.iif_template = tba;
978 iif.iif_ta = mcd->md_ta;
979 iif.iif_newidx = newidx;
980 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE);
981
982 if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match,
983 &iif) == 1) {
984 debug(3, "iidesc_t %s already exists\n",
985 (tba->ii_name ? tba->ii_name : "(anon)"));
986 return (1);
987 }
988
989 new = conjure_iidesc(tba, mcd);
990 hash_add(mcd->md_tgt->td_iihash, new);
991
992 return (1);
993 }
994
995 static int
add_tdesc(tdesc_t * oldtdp,int newid,merge_cb_data_t * mcd)996 add_tdesc(tdesc_t *oldtdp, int newid, merge_cb_data_t *mcd)
997 {
998 tdesc_t *newtdp;
999 tdesc_t template;
1000
1001 template.t_id = newid;
1002 assert(hash_find(mcd->md_parent->td_idhash,
1003 (void *)&template, NULL) == 0);
1004
1005 debug(3, "trying to conjure %d %s (%d, <%x>) as %d, <%x>\n",
1006 oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id,
1007 oldtdp->t_id, newid, newid);
1008
1009 if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid,
1010 mcd)) == NULL)
1011 /* couldn't map everything */
1012 return (0);
1013
1014 debug(3, "succeeded\n");
1015
1016 hash_add(mcd->md_tgt->td_idhash, newtdp);
1017 hash_add(mcd->md_tgt->td_layouthash, newtdp);
1018
1019 return (1);
1020 }
1021
1022 static int
add_tdtba_cb(void * data,void * arg)1023 add_tdtba_cb(void *data, void *arg)
1024 {
1025 tdesc_t *tdp = data;
1026 merge_cb_data_t *mcd = arg;
1027 int newid;
1028 int rc;
1029
1030 newid = get_mapping(mcd->md_ta, tdp->t_id);
1031 assert(newid != -1);
1032
1033 if ((rc = add_tdesc(tdp, newid, mcd)))
1034 hash_remove(mcd->md_tdtba, (void *)tdp);
1035
1036 return (rc);
1037 }
1038
1039 static int
add_tdtbr_cb(void * data,void * arg)1040 add_tdtbr_cb(void *data, void *arg)
1041 {
1042 tdesc_t **tdpp = data;
1043 merge_cb_data_t *mcd = arg;
1044
1045 debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id);
1046
1047 if (!remap_node(tdpp, *tdpp, -1, NULL, mcd))
1048 return (0);
1049
1050 (void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL);
1051 return (1);
1052 }
1053
1054 static void
merge_types(hash_t * src,merge_cb_data_t * mcd)1055 merge_types(hash_t *src, merge_cb_data_t *mcd)
1056 {
1057 list_t *iitba = NULL;
1058 list_t *tdtbr = NULL;
1059 int iirc, tdrc;
1060
1061 mcd->md_iitba = &iitba;
1062 mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
1063 tdesc_layoutcmp);
1064 mcd->md_tdtbr = &tdtbr;
1065
1066 (void) hash_iter(src, merge_type_cb, mcd);
1067
1068 tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, mcd);
1069 debug(3, "add_tdtba_cb added %d items\n", tdrc);
1070
1071 iirc = list_iter(*mcd->md_iitba, add_iitba_cb, mcd);
1072 debug(3, "add_iitba_cb added %d items\n", iirc);
1073
1074 assert(list_count(*mcd->md_iitba) == 0 &&
1075 hash_count(mcd->md_tdtba) == 0);
1076
1077 tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, mcd);
1078 debug(3, "add_tdtbr_cb added %d items\n", tdrc);
1079
1080 if (list_count(*mcd->md_tdtbr) != 0)
1081 aborterr("Couldn't remap all nodes\n");
1082
1083 /*
1084 * We now have an alist of master forwards and the ids of the new master
1085 * definitions for those forwards in mcd->md_fdida. By this point,
1086 * we're guaranteed that all of the master definitions referenced in
1087 * fdida have been added to the master tree. We now traverse through
1088 * the master tree, redirecting all edges inbound to forwards that have
1089 * definitions to those definitions.
1090 */
1091 if (mcd->md_parent == mcd->md_tgt) {
1092 redir_mstr_fwds(mcd);
1093 }
1094 }
1095
1096 void
merge_into_master(tdata_t * cur,tdata_t * mstr,tdata_t * tgt,int selfuniquify)1097 merge_into_master(tdata_t *cur, tdata_t *mstr, tdata_t *tgt, int selfuniquify)
1098 {
1099 merge_cb_data_t mcd;
1100
1101 cur->td_ref++;
1102 mstr->td_ref++;
1103 if (tgt)
1104 tgt->td_ref++;
1105
1106 assert(cur->td_ref == 1 && mstr->td_ref == 1 &&
1107 (tgt == NULL || tgt->td_ref == 1));
1108
1109 mcd.md_parent = mstr;
1110 mcd.md_tgt = (tgt ? tgt : mstr);
1111 mcd.md_ta = alist_new(NULL, NULL);
1112 mcd.md_fdida = alist_new(NULL, NULL);
1113 mcd.md_flags = 0;
1114
1115 if (selfuniquify)
1116 mcd.md_flags |= MCD_F_SELFUNIQUIFY;
1117 if (tgt)
1118 mcd.md_flags |= MCD_F_REFMERGE;
1119
1120 mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen);
1121 mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark);
1122
1123 merge_types(cur->td_iihash, &mcd);
1124
1125 if (debug_level >= 3) {
1126 debug(3, "Type association stats\n");
1127 alist_stats(mcd.md_ta, 0);
1128 debug(3, "Layout hash stats\n");
1129 hash_stats(mcd.md_tgt->td_layouthash, 1);
1130 }
1131
1132 alist_free(mcd.md_fdida);
1133 alist_free(mcd.md_ta);
1134
1135 cur->td_ref--;
1136 mstr->td_ref--;
1137 if (tgt)
1138 tgt->td_ref--;
1139 }
1140
1141 tdesc_ops_t tdesc_ops[] = {
1142 { "ERROR! BAD tdesc TYPE", NULL, NULL },
1143 { "intrinsic", equiv_intrinsic, conjure_intrinsic },
1144 { "pointer", equiv_plain, conjure_plain },
1145 { "reference", equiv_plain, conjure_plain },
1146 { "array", equiv_array, conjure_array },
1147 { "function", equiv_function, conjure_function },
1148 { "struct", equiv_su, conjure_su },
1149 { "union", equiv_su, conjure_su },
1150 { "class", equiv_su, conjure_su },
1151 { "enum", equiv_enum, conjure_enum },
1152 { "forward", NULL, conjure_forward },
1153 { "typedef", equiv_plain, conjure_plain },
1154 { "typedef_unres", equiv_assert, conjure_assert },
1155 { "volatile", equiv_plain, conjure_plain },
1156 { "const", equiv_plain, conjure_plain },
1157 { "restrict", equiv_plain, conjure_plain }
1158 };
1159