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