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 2010 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 /*
27 * Routines for manipulating tdesc and tdata structures
28 */
29
30 #if HAVE_NBTOOL_CONFIG_H
31 # include "nbtool_config.h"
32 #endif
33
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <strings.h>
37 #include <pthread.h>
38
39 #include "ctftools.h"
40 #include "memory.h"
41 #include "traverse.h"
42
43 /*
44 * The layout hash is used during the equivalency checking. We have a node in
45 * the child graph that may be equivalent to a node in the parent graph. To
46 * find the corresponding node (if any) in the parent, we need a quick way to
47 * get to all nodes in the parent that look like the node in the child. Since a
48 * large number of nodes don't have names, we need to incorporate the layout of
49 * the node into the hash. If we don't, we'll end up with the vast majority of
50 * nodes in bucket zero, with one or two nodes in each of the remaining buckets.
51 *
52 * There are a couple of constraints, both of which concern forward
53 * declarations. Recall that a forward declaration tdesc is equivalent to a
54 * tdesc that actually defines the structure or union. As such, we cannot
55 * incorporate anything into the hash for a named struct or union node that
56 * couldn't be found by looking at the forward, and vice versa.
57 */
58 int
tdesc_layouthash(int nbuckets,void * node)59 tdesc_layouthash(int nbuckets, void *node)
60 {
61 tdesc_t *tdp = node;
62 char *name = NULL;
63 ulong_t h = 0;
64
65 if (tdp->t_name)
66 name = tdp->t_name;
67 else {
68 switch (tdp->t_type) {
69 case POINTER:
70 case TYPEDEF:
71 case VOLATILE:
72 case CONST:
73 case RESTRICT:
74 name = tdp->t_tdesc->t_name;
75 break;
76 case FUNCTION:
77 h = tdp->t_fndef->fn_nargs +
78 tdp->t_fndef->fn_vargs;
79 name = tdp->t_fndef->fn_ret->t_name;
80 break;
81 case ARRAY:
82 h = tdp->t_ardef->ad_nelems;
83 name = tdp->t_ardef->ad_contents->t_name;
84 break;
85 case STRUCT:
86 case UNION:
87 /*
88 * Unnamed structures, which cannot have forward
89 * declarations pointing to them. We can therefore
90 * incorporate the name of the first member into
91 * the hash value, assuming there are any.
92 */
93 if (tdp->t_members != NULL)
94 name = tdp->t_members->ml_name;
95 break;
96 case ENUM:
97 /* Use the first element in the hash value */
98 name = tdp->t_emem->el_name;
99 break;
100 default:
101 /*
102 * Intrinsics, forwards, and typedefs all have
103 * names.
104 */
105 warning("Unexpected unnamed %d tdesc (ID %d)\n",
106 tdp->t_type, tdp->t_id);
107 }
108 }
109
110 if (name)
111 return (hash_name(nbuckets, name));
112
113 return (h % nbuckets);
114 }
115
116 int
tdesc_layoutcmp(void * arg1,void * arg2)117 tdesc_layoutcmp(void *arg1, void *arg2)
118 {
119 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
120
121 if (tdp1->t_name == NULL) {
122 if (tdp2->t_name == NULL)
123 return (0);
124 else
125 return (-1);
126 } else if (tdp2->t_name == NULL)
127 return (1);
128 else
129 return (strcmp(tdp1->t_name, tdp2->t_name));
130 }
131
132 int
tdesc_idhash(int nbuckets,void * data)133 tdesc_idhash(int nbuckets, void *data)
134 {
135 tdesc_t *tdp = data;
136
137 return (tdp->t_id % nbuckets);
138 }
139
140 int
tdesc_idcmp(void * arg1,void * arg2)141 tdesc_idcmp(void *arg1, void *arg2)
142 {
143 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
144
145 if (tdp1->t_id == tdp2->t_id)
146 return (0);
147 else
148 return (tdp1->t_id > tdp2->t_id ? 1 : -1);
149 }
150
151 int
tdesc_namehash(int nbuckets,void * data)152 tdesc_namehash(int nbuckets, void *data)
153 {
154 tdesc_t *tdp = data;
155 ulong_t h, g;
156 char *c;
157
158 if (tdp->t_name == NULL)
159 return (0);
160
161 for (h = 0, c = tdp->t_name; *c; c++) {
162 h = (h << 4) + *c;
163 if ((g = (h & 0xf0000000)) != 0) {
164 h ^= (g >> 24);
165 h ^= g;
166 }
167 }
168
169 return (h % nbuckets);
170 }
171
172 int
tdesc_namecmp(void * arg1,void * arg2)173 tdesc_namecmp(void *arg1, void *arg2)
174 {
175 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
176
177 return (!streq(tdp1->t_name, tdp2->t_name));
178 }
179
180 #if defined(sun)
181 /*ARGSUSED1*/
182 static int
tdesc_print(void * data,void * private __unused)183 tdesc_print(void *data, void *private __unused)
184 {
185 tdesc_t *tdp = data;
186
187 printf("%7d %s\n", tdp->t_id, tdesc_name(tdp));
188
189 return (1);
190 }
191 #endif
192
193 static void
free_intr(tdesc_t * tdp)194 free_intr(tdesc_t *tdp)
195 {
196 free(tdp->t_intr);
197 }
198
199 static void
free_ardef(tdesc_t * tdp)200 free_ardef(tdesc_t *tdp)
201 {
202 free(tdp->t_ardef);
203 }
204
205 static void
free_mlist(tdesc_t * tdp)206 free_mlist(tdesc_t *tdp)
207 {
208 mlist_t *ml = tdp->t_members;
209 mlist_t *oml;
210
211 while (ml) {
212 oml = ml;
213 ml = ml->ml_next;
214
215 if (oml->ml_name)
216 free(oml->ml_name);
217 free(oml);
218 }
219 }
220
221 static void
free_elist(tdesc_t * tdp)222 free_elist(tdesc_t *tdp)
223 {
224 elist_t *el = tdp->t_emem;
225 elist_t *oel;
226
227 while (el) {
228 oel = el;
229 el = el->el_next;
230
231 if (oel->el_name)
232 free(oel->el_name);
233 free(oel);
234 }
235 }
236
237 static void (*free_cbs[])(tdesc_t *) = {
238 NULL,
239 free_intr, /* intrinsic */
240 NULL, /* pointer */
241 NULL, /* reference */
242 free_ardef, /* array */
243 NULL, /* function */
244 free_mlist, /* struct */
245 free_mlist, /* union */
246 free_mlist, /* class */
247 free_elist, /* enum */
248 NULL, /* forward */
249 NULL, /* typedef */
250 NULL, /* typedef_unres */
251 NULL, /* volatile */
252 NULL, /* const */
253 NULL /* restrict */
254 };
255
256 /*ARGSUSED1*/
257 static void
tdesc_free_cb(void * arg,void * private __unused)258 tdesc_free_cb(void *arg, void *private __unused)
259 {
260 tdesc_t *tdp = arg;
261 if (tdp->t_name)
262 free(tdp->t_name);
263 if (free_cbs[tdp->t_type])
264 free_cbs[tdp->t_type](tdp);
265 free(tdp);
266
267 return;
268 }
269
270 void
tdesc_free(tdesc_t * tdp)271 tdesc_free(tdesc_t *tdp)
272 {
273 tdesc_free_cb(tdp, NULL);
274 }
275
276 static int
tdata_label_cmp(void * arg1,void * arg2)277 tdata_label_cmp(void *arg1, void *arg2)
278 {
279 labelent_t *le1 = arg1;
280 labelent_t *le2 = arg2;
281 return (le1->le_idx - le2->le_idx);
282 }
283
284 void
tdata_label_add(tdata_t * td,const char * label,int idx)285 tdata_label_add(tdata_t *td, const char *label, int idx)
286 {
287 labelent_t *le = xmalloc(sizeof (*le));
288
289 le->le_name = xstrdup(label);
290 le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx);
291
292 slist_add(&td->td_labels, le, tdata_label_cmp);
293 }
294
295 static int
tdata_label_top_cb(void * data,void * arg)296 tdata_label_top_cb(void *data, void *arg)
297 {
298 labelent_t *le = data;
299 labelent_t **topp = arg;
300
301 *topp = le;
302
303 return (1);
304 }
305
306 labelent_t *
tdata_label_top(tdata_t * td)307 tdata_label_top(tdata_t *td)
308 {
309 labelent_t *top = NULL;
310
311 (void) list_iter(td->td_labels, tdata_label_top_cb, &top);
312
313 return (top);
314 }
315
316 static int
tdata_label_find_cb(void * arg1,void * arg2)317 tdata_label_find_cb(void *arg1, void *arg2)
318 {
319 labelent_t *le = arg1;
320 labelent_t *tmpl = arg2;
321 return (streq(le->le_name, tmpl->le_name));
322 }
323
324 int
tdata_label_find(tdata_t * td,char * label)325 tdata_label_find(tdata_t *td, char *label)
326 {
327 labelent_t let;
328 labelent_t *ret;
329
330 if (streq(label, "BASE")) {
331 ret = (labelent_t *)list_first(td->td_labels);
332 return (ret ? ret->le_idx : -1);
333 }
334
335 let.le_name = label;
336
337 if (!(ret = (labelent_t *)list_find(td->td_labels, &let,
338 tdata_label_find_cb)))
339 return (-1);
340
341 return (ret->le_idx);
342 }
343
344 static int
tdata_label_newmax_cb(void * data,void * arg)345 tdata_label_newmax_cb(void *data, void *arg)
346 {
347 labelent_t *le = data;
348 int *newmaxp = arg;
349
350 if (le->le_idx > *newmaxp) {
351 le->le_idx = *newmaxp;
352 return (1);
353 }
354
355 return (0);
356 }
357
358 void
tdata_label_newmax(tdata_t * td,int newmax)359 tdata_label_newmax(tdata_t *td, int newmax)
360 {
361 (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax);
362 }
363
364 /*ARGSUSED1*/
365 static void
tdata_label_free_cb(void * arg,void * private __unused)366 tdata_label_free_cb(void *arg, void *private __unused)
367 {
368 labelent_t *le = arg;
369 if (le->le_name)
370 free(le->le_name);
371 free(le);
372 }
373
374 void
tdata_label_free(tdata_t * td)375 tdata_label_free(tdata_t *td)
376 {
377 list_free(td->td_labels, tdata_label_free_cb, NULL);
378 td->td_labels = NULL;
379 }
380
381 tdata_t *
tdata_new(void)382 tdata_new(void)
383 {
384 tdata_t *new = xcalloc(sizeof (tdata_t));
385
386 new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
387 tdesc_layoutcmp);
388 new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash,
389 tdesc_idcmp);
390 /*
391 * This is also traversed as a list, but amortized O(1)
392 * lookup massively impacts part of the merge phase, so
393 * we store the iidescs as a hash.
394 */
395 new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL);
396 new->td_nextid = 1;
397 new->td_curvgen = 1;
398
399 pthread_mutex_init(&new->td_mergelock, NULL);
400
401 return (new);
402 }
403
404 void
tdata_free(tdata_t * td)405 tdata_free(tdata_t *td)
406 {
407 hash_free(td->td_iihash, iidesc_free, NULL);
408 hash_free(td->td_layouthash, tdesc_free_cb, NULL);
409 hash_free(td->td_idhash, NULL, NULL);
410 list_free(td->td_fwdlist, NULL, NULL);
411
412 tdata_label_free(td);
413
414 free(td->td_parlabel);
415 free(td->td_parname);
416
417 pthread_mutex_destroy(&td->td_mergelock);
418
419 free(td);
420 }
421
422 /*ARGSUSED1*/
423 static int
build_hashes(tdesc_t * ctdp,tdesc_t ** ctdpp __unused,void * private)424 build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
425 {
426 tdata_t *td = private;
427
428 hash_add(td->td_idhash, ctdp);
429 hash_add(td->td_layouthash, ctdp);
430
431 return (1);
432 }
433
434 static tdtrav_cb_f build_hashes_cbs[] = {
435 NULL,
436 build_hashes, /* intrinsic */
437 build_hashes, /* pointer */
438 build_hashes, /* reference */
439 build_hashes, /* array */
440 build_hashes, /* function */
441 build_hashes, /* struct */
442 build_hashes, /* union */
443 build_hashes, /* class */
444 build_hashes, /* enum */
445 build_hashes, /* forward */
446 build_hashes, /* typedef */
447 tdtrav_assert, /* typedef_unres */
448 build_hashes, /* volatile */
449 build_hashes, /* const */
450 build_hashes /* restrict */
451 };
452
453 static void
tdata_build_hashes_common(tdata_t * td,hash_t * hash)454 tdata_build_hashes_common(tdata_t *td, hash_t *hash)
455 {
456 (void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL,
457 build_hashes_cbs, td);
458 }
459
460 void
tdata_build_hashes(tdata_t * td)461 tdata_build_hashes(tdata_t *td)
462 {
463 tdata_build_hashes_common(td, td->td_iihash);
464 }
465
466 /* Merge td2 into td1. td2 is destroyed by the merge */
467 void
tdata_merge(tdata_t * td1,tdata_t * td2)468 tdata_merge(tdata_t *td1, tdata_t *td2)
469 {
470 td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark);
471 td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen);
472 td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid);
473
474 hash_merge(td1->td_iihash, td2->td_iihash);
475
476 /* Add td2's type tree to the hashes */
477 tdata_build_hashes_common(td1, td2->td_iihash);
478
479 list_concat(&td1->td_fwdlist, td2->td_fwdlist);
480 td2->td_fwdlist = NULL;
481
482 slist_merge(&td1->td_labels, td2->td_labels,
483 tdata_label_cmp);
484 td2->td_labels = NULL;
485
486 /* free the td2 hashes (data is now part of td1) */
487
488 hash_free(td2->td_layouthash, NULL, NULL);
489 td2->td_layouthash = NULL;
490
491 hash_free(td2->td_iihash, NULL, NULL);
492 td2->td_iihash = NULL;
493
494 tdata_free(td2);
495 }
496