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