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
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
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
129 tdesc_idhash(int nbuckets, void *data)
130 {
131 	tdesc_t *tdp = data;
132 
133 	return (tdp->t_id % nbuckets);
134 }
135 
136 int
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
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
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 #ifdef illumos
177 /*ARGSUSED1*/
178 static int
179 tdesc_print(void *data, void *private __unused)
180 {
181 	tdesc_t *tdp = data;
182 
183 	printf("%7d %s\n", tdp->t_id, tdesc_name(tdp));
184 
185 	return (1);
186 }
187 #endif
188 
189 static void
190 free_intr(tdesc_t *tdp)
191 {
192 	free(tdp->t_intr);
193 }
194 
195 static void
196 free_ardef(tdesc_t *tdp)
197 {
198 	free(tdp->t_ardef);
199 }
200 
201 static void
202 free_mlist(tdesc_t *tdp)
203 {
204 	mlist_t *ml = tdp->t_members;
205 	mlist_t *oml;
206 
207 	while (ml) {
208 		oml = ml;
209 		ml = ml->ml_next;
210 
211 		if (oml->ml_name)
212 			free(oml->ml_name);
213 		free(oml);
214 	}
215 }
216 
217 static void
218 free_elist(tdesc_t *tdp)
219 {
220 	elist_t *el = tdp->t_emem;
221 	elist_t *oel;
222 
223 	while (el) {
224 		oel = el;
225 		el = el->el_next;
226 
227 		if (oel->el_name)
228 			free(oel->el_name);
229 		free(oel);
230 	}
231 }
232 
233 static void (*free_cbs[])(tdesc_t *) = {
234 	NULL,
235 	free_intr,
236 	NULL,
237 	free_ardef,
238 	NULL,
239 	free_mlist,
240 	free_mlist,
241 	free_elist,
242 	NULL,
243 	NULL,
244 	NULL,
245 	NULL,
246 	NULL,
247 	NULL
248 };
249 
250 /*ARGSUSED1*/
251 static void
252 tdesc_free_cb(void *arg, void *private __unused)
253 {
254 	tdesc_t *tdp = arg;
255 	if (tdp->t_name)
256 		free(tdp->t_name);
257 	if (free_cbs[tdp->t_type])
258 		free_cbs[tdp->t_type](tdp);
259 	free(tdp);
260 
261 	return;
262 }
263 
264 void
265 tdesc_free(tdesc_t *tdp)
266 {
267 	tdesc_free_cb(tdp, NULL);
268 }
269 
270 static int
271 tdata_label_cmp(void *arg1, void *arg2)
272 {
273 	labelent_t *le1 = arg1;
274 	labelent_t *le2 = arg2;
275 	return (le1->le_idx - le2->le_idx);
276 }
277 
278 void
279 tdata_label_add(tdata_t *td, const char *label, int idx)
280 {
281 	labelent_t *le = xmalloc(sizeof (*le));
282 
283 	le->le_name = xstrdup(label);
284 	le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx);
285 
286 	slist_add(&td->td_labels, le, tdata_label_cmp);
287 }
288 
289 static int
290 tdata_label_top_cb(void *data, void *arg)
291 {
292 	labelent_t *le = data;
293 	labelent_t **topp = arg;
294 
295 	*topp = le;
296 
297 	return (1);
298 }
299 
300 labelent_t *
301 tdata_label_top(tdata_t *td)
302 {
303 	labelent_t *top = NULL;
304 
305 	(void) list_iter(td->td_labels, tdata_label_top_cb, &top);
306 
307 	return (top);
308 }
309 
310 static int
311 tdata_label_find_cb(void *arg1, void *arg2)
312 {
313 	labelent_t *le = arg1;
314 	labelent_t *tmpl = arg2;
315 	return (streq(le->le_name, tmpl->le_name));
316 }
317 
318 int
319 tdata_label_find(tdata_t *td, char *label)
320 {
321 	labelent_t let;
322 	labelent_t *ret;
323 
324 	if (streq(label, "BASE")) {
325 		ret = (labelent_t *)list_first(td->td_labels);
326 		return (ret ? ret->le_idx : -1);
327 	}
328 
329 	let.le_name = label;
330 
331 	if (!(ret = (labelent_t *)list_find(td->td_labels, &let,
332 	    tdata_label_find_cb)))
333 		return (-1);
334 
335 	return (ret->le_idx);
336 }
337 
338 static int
339 tdata_label_newmax_cb(void *data, void *arg)
340 {
341 	labelent_t *le = data;
342 	int *newmaxp = arg;
343 
344 	if (le->le_idx > *newmaxp) {
345 		le->le_idx = *newmaxp;
346 		return (1);
347 	}
348 
349 	return (0);
350 }
351 
352 void
353 tdata_label_newmax(tdata_t *td, int newmax)
354 {
355 	(void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax);
356 }
357 
358 /*ARGSUSED1*/
359 static void
360 tdata_label_free_cb(void *arg, void *private __unused)
361 {
362 	labelent_t *le = arg;
363 	if (le->le_name)
364 		free(le->le_name);
365 	free(le);
366 }
367 
368 void
369 tdata_label_free(tdata_t *td)
370 {
371 	list_free(td->td_labels, tdata_label_free_cb, NULL);
372 	td->td_labels = NULL;
373 }
374 
375 tdata_t *
376 tdata_new(void)
377 {
378 	tdata_t *new = xcalloc(sizeof (tdata_t));
379 
380 	new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
381 	    tdesc_layoutcmp);
382 	new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash,
383 	    tdesc_idcmp);
384 	/*
385 	 * This is also traversed as a list, but amortized O(1)
386 	 * lookup massively impacts part of the merge phase, so
387 	 * we store the iidescs as a hash.
388 	 */
389 	new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL);
390 	new->td_nextid = 1;
391 	new->td_curvgen = 1;
392 
393 	pthread_mutex_init(&new->td_mergelock, NULL);
394 
395 	return (new);
396 }
397 
398 void
399 tdata_free(tdata_t *td)
400 {
401 	hash_free(td->td_iihash, iidesc_free, NULL);
402 	hash_free(td->td_layouthash, tdesc_free_cb, NULL);
403 	hash_free(td->td_idhash, NULL, NULL);
404 	list_free(td->td_fwdlist, NULL, NULL);
405 
406 	tdata_label_free(td);
407 
408 	free(td->td_parlabel);
409 	free(td->td_parname);
410 
411 	pthread_mutex_destroy(&td->td_mergelock);
412 
413 	free(td);
414 }
415 
416 /*ARGSUSED1*/
417 static int
418 build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
419 {
420 	tdata_t *td = private;
421 
422 	hash_add(td->td_idhash, ctdp);
423 	hash_add(td->td_layouthash, ctdp);
424 
425 	return (1);
426 }
427 
428 static tdtrav_cb_f build_hashes_cbs[] = {
429 	NULL,
430 	build_hashes,	/* intrinsic */
431 	build_hashes,	/* pointer */
432 	build_hashes,	/* array */
433 	build_hashes,	/* function */
434 	build_hashes,	/* struct */
435 	build_hashes,	/* union */
436 	build_hashes,	/* enum */
437 	build_hashes,	/* forward */
438 	build_hashes,	/* typedef */
439 	tdtrav_assert,	/* typedef_unres */
440 	build_hashes,	/* volatile */
441 	build_hashes,	/* const */
442 	build_hashes	/* restrict */
443 };
444 
445 static void
446 tdata_build_hashes_common(tdata_t *td, hash_t *hash)
447 {
448 	(void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL,
449 	    build_hashes_cbs, td);
450 }
451 
452 void
453 tdata_build_hashes(tdata_t *td)
454 {
455 	tdata_build_hashes_common(td, td->td_iihash);
456 }
457 
458 /* Merge td2 into td1.  td2 is destroyed by the merge */
459 void
460 tdata_merge(tdata_t *td1, tdata_t *td2)
461 {
462 	td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark);
463 	td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen);
464 	td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid);
465 
466 	hash_merge(td1->td_iihash, td2->td_iihash);
467 
468 	/* Add td2's type tree to the hashes */
469 	tdata_build_hashes_common(td1, td2->td_iihash);
470 
471 	list_concat(&td1->td_fwdlist, td2->td_fwdlist);
472 	td2->td_fwdlist = NULL;
473 
474 	slist_merge(&td1->td_labels, td2->td_labels,
475 	    tdata_label_cmp);
476 	td2->td_labels = NULL;
477 
478 	/* free the td2 hashes (data is now part of td1) */
479 
480 	hash_free(td2->td_layouthash, NULL, NULL);
481 	td2->td_layouthash = NULL;
482 
483 	hash_free(td2->td_iihash, NULL, NULL);
484 	td2->td_iihash = NULL;
485 
486 	tdata_free(td2);
487 }
488