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