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