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