OpenSolaris Launch

1 files changed, 481 insertions, 0 deletions

diff --git a/usr/src/tools/ctf/cvt/tdata.c b/usr/src/tools/ctf/cvt/tdata.c
new file mode 100644
index 0000000000..fd37d1e142
--- /dev/null
+++ b/usr/src/tools/ctf/cvt/tdata.c
@@ -0,0 +1,481 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+/*
+ * Routines for manipulating tdesc and tdata structures
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <pthread.h>
+
+#include "ctftools.h"
+#include "memory.h"
+#include "traverse.h"
+
+/*
+ * The layout hash is used during the equivalency checking.  We have a node in
+ * the child graph that may be equivalent to a node in the parent graph.  To
+ * find the corresponding node (if any) in the parent, we need a quick way to
+ * get to all nodes in the parent that look like the node in the child.  Since a
+ * large number of nodes don't have names, we need to incorporate the layout of
+ * the node into the hash.  If we don't, we'll end up with the vast majority of
+ * nodes in bucket zero, with one or two nodes in each of the remaining buckets.
+ *
+ * There are a couple of constraints, both of which concern forward
+ * declarations.  Recall that a forward declaration tdesc is equivalent to a
+ * tdesc that actually defines the structure or union.  As such, we cannot
+ * incorporate anything into the hash for a named struct or union node that
+ * couldn't be found by looking at the forward, and vice versa.
+ */
+int
+tdesc_layouthash(int nbuckets, void *node)
+{
+	tdesc_t *tdp = node;
+	char *name = NULL;
+	ulong_t h = 0;
+
+	if (tdp->t_name)
+		name = tdp->t_name;
+	else {
+		switch (tdp->t_type) {
+		case POINTER:
+		case TYPEDEF:
+		case VOLATILE:
+		case CONST:
+		case RESTRICT:
+			name = tdp->t_tdesc->t_name;
+			break;
+		case FUNCTION:
+			h = tdp->t_fndef->fn_nargs +
+			    tdp->t_fndef->fn_vargs;
+			name = tdp->t_fndef->fn_ret->t_name;
+			break;
+		case ARRAY:
+			h = tdp->t_ardef->ad_nelems;
+			name = tdp->t_ardef->ad_contents->t_name;
+			break;
+		case STRUCT:
+		case UNION:
+			/*
+			 * Unnamed structures, which cannot have forward
+			 * declarations pointing to them.  We can therefore
+			 * incorporate the name of the first member into
+			 * the hash value.
+			 */
+			name = tdp->t_members->ml_name;
+			break;
+		case ENUM:
+			/* Use the first element in the hash value */
+			name = tdp->t_emem->el_name;
+			break;
+		default:
+			/*
+			 * Intrinsics, forwards, and typedefs all have
+			 * names.
+			 */
+			warning("Unexpected unnamed %d tdesc (ID %d)\n",
+			    tdp->t_type, tdp->t_id);
+		}
+	}
+
+	if (name)
+		return (hash_name(nbuckets, name));
+
+	return (h % nbuckets);
+}
+
+int
+tdesc_layoutcmp(void *arg1, void *arg2)
+{
+	tdesc_t *tdp1 = arg1, *tdp2 = arg2;
+
+	if (tdp1->t_name == NULL) {
+		if (tdp2->t_name == NULL)
+			return (0);
+		else
+			return (-1);
+	} else if (tdp2->t_name == NULL)
+		return (1);
+	else
+		return (strcmp(tdp1->t_name, tdp2->t_name));
+}
+
+int
+tdesc_idhash(int nbuckets, void *data)
+{
+	tdesc_t *tdp = data;
+
+	return (tdp->t_id % nbuckets);
+}
+
+int
+tdesc_idcmp(void *arg1, void *arg2)
+{
+	tdesc_t *tdp1 = arg1, *tdp2 = arg2;
+
+	if (tdp1->t_id == tdp2->t_id)
+		return (0);
+	else
+		return (tdp1->t_id > tdp2->t_id ? 1 : -1);
+}
+
+int
+tdesc_namehash(int nbuckets, void *data)
+{
+	tdesc_t *tdp = data;
+	ulong_t h, g;
+	char *c;
+
+	if (tdp->t_name == NULL)
+		return (0);
+
+	for (h = 0, c = tdp->t_name; *c; c++) {
+		h = (h << 4) + *c;
+		if ((g = (h & 0xf0000000)) != 0) {
+			h ^= (g >> 24);
+			h ^= g;
+		}
+	}
+
+	return (h % nbuckets);
+}
+
+int
+tdesc_namecmp(void *arg1, void *arg2)
+{
+	tdesc_t *tdp1 = arg1, *tdp2 = arg2;
+
+	return (!streq(tdp1->t_name, tdp2->t_name));
+}
+
+/*ARGSUSED1*/
+int
+tdesc_print(void *data, void *private)
+{
+	tdesc_t *tdp = data;
+
+	printf("%7d %s\n", tdp->t_id, (tdp->t_name ? tdp->t_name : "(anon)"));
+
+	return (1);
+}
+
+static void
+free_intr(tdesc_t *tdp)
+{
+	free(tdp->t_intr);
+}
+
+static void
+free_ardef(tdesc_t *tdp)
+{
+	free(tdp->t_ardef);
+}
+
+static void
+free_mlist(tdesc_t *tdp)
+{
+	mlist_t *ml = tdp->t_members;
+	mlist_t *oml;
+
+	while (ml) {
+		oml = ml;
+		ml = ml->ml_next;
+
+		if (oml->ml_name)
+			free(oml->ml_name);
+		free(oml);
+	}
+}
+
+static void
+free_elist(tdesc_t *tdp)
+{
+	elist_t *el = tdp->t_emem;
+	elist_t *oel;
+
+	while (el) {
+		oel = el;
+		el = el->el_next;
+
+		if (oel->el_name)
+			free(oel->el_name);
+		free(oel);
+	}
+}
+
+static void (*free_cbs[])(tdesc_t *) = {
+	NULL,
+	free_intr,
+	NULL,
+	free_ardef,
+	NULL,
+	free_mlist,
+	free_mlist,
+	free_elist,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL,
+	NULL
+};
+
+/*ARGSUSED1*/
+static int
+tdesc_free_cb(tdesc_t *tdp, void *private)
+{
+	if (tdp->t_name)
+		free(tdp->t_name);
+	if (free_cbs[tdp->t_type])
+		free_cbs[tdp->t_type](tdp);
+	free(tdp);
+
+	return (1);
+}
+
+void
+tdesc_free(tdesc_t *tdp)
+{
+	(void) tdesc_free_cb(tdp, NULL);
+}
+
+static int
+tdata_label_cmp(labelent_t *le1, labelent_t *le2)
+{
+	return (le1->le_idx - le2->le_idx);
+}
+
+void
+tdata_label_add(tdata_t *td, char *label, int idx)
+{
+	labelent_t *le = xmalloc(sizeof (*le));
+
+	le->le_name = xstrdup(label);
+	le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx);
+
+	slist_add(&td->td_labels, le, (int (*)())tdata_label_cmp);
+}
+
+static int
+tdata_label_top_cb(void *data, void *arg)
+{
+	labelent_t *le = data;
+	labelent_t **topp = arg;
+
+	*topp = le;
+
+	return (1);
+}
+
+labelent_t *
+tdata_label_top(tdata_t *td)
+{
+	labelent_t *top = NULL;
+
+	(void) list_iter(td->td_labels, tdata_label_top_cb, &top);
+
+	return (top);
+}
+
+static int
+tdata_label_find_cb(labelent_t *le, labelent_t *tmpl)
+{
+	return (streq(le->le_name, tmpl->le_name));
+}
+
+int
+tdata_label_find(tdata_t *td, char *label)
+{
+	labelent_t let;
+	labelent_t *ret;
+
+	if (streq(label, "BASE")) {
+		ret = (labelent_t *)list_first(td->td_labels);
+		return (ret ? ret->le_idx : -1);
+	}
+
+	let.le_name = label;
+
+	if (!(ret = (labelent_t *)list_find(td->td_labels, &let,
+	    (int (*)())tdata_label_find_cb)))
+		return (-1);
+
+	return (ret->le_idx);
+}
+
+static int
+tdata_label_newmax_cb(void *data, void *arg)
+{
+	labelent_t *le = data;
+	int *newmaxp = arg;
+
+	if (le->le_idx > *newmaxp) {
+		le->le_idx = *newmaxp;
+		return (1);
+	}
+
+	return (0);
+}
+
+void
+tdata_label_newmax(tdata_t *td, int newmax)
+{
+	(void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax);
+}
+
+/*ARGSUSED1*/
+static void
+tdata_label_free_cb(labelent_t *le, void *private)
+{
+	if (le->le_name)
+		free(le->le_name);
+	free(le);
+}
+
+void
+tdata_label_free(tdata_t *td)
+{
+	list_free(td->td_labels, (void (*)())tdata_label_free_cb, NULL);
+	td->td_labels = NULL;
+}
+
+tdata_t *
+tdata_new(void)
+{
+	tdata_t *new = xcalloc(sizeof (tdata_t));
+
+	new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
+	    tdesc_layoutcmp);
+	new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash,
+	    tdesc_idcmp);
+	/*
+	 * This is also traversed as a list, but amortized O(1)
+	 * lookup massively impacts part of the merge phase, so
+	 * we store the iidescs as a hash.
+	 */
+	new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL);
+	new->td_nextid = 1;
+	new->td_curvgen = 1;
+
+	pthread_mutex_init(&new->td_mergelock, NULL);
+
+	return (new);
+}
+
+void
+tdata_free(tdata_t *td)
+{
+	hash_free(td->td_iihash, (void (*)())iidesc_free, NULL);
+	hash_free(td->td_layouthash, (void (*)())tdesc_free_cb, NULL);
+	hash_free(td->td_idhash, NULL, NULL);
+	list_free(td->td_fwdlist, NULL, NULL);
+
+	tdata_label_free(td);
+
+	free(td->td_parlabel);
+	free(td->td_parname);
+
+	pthread_mutex_destroy(&td->td_mergelock);
+
+	free(td);
+}
+
+/*ARGSUSED1*/
+static int
+build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp, void *private)
+{
+	tdata_t *td = private;
+
+	hash_add(td->td_idhash, ctdp);
+	hash_add(td->td_layouthash, ctdp);
+
+	return (1);
+}
+
+static tdtrav_cb_f build_hashes_cbs[] = {
+	NULL,
+	build_hashes,	/* intrinsic */
+	build_hashes,	/* pointer */
+	build_hashes,	/* array */
+	build_hashes,	/* function */
+	build_hashes,	/* struct */
+	build_hashes,	/* union */
+	build_hashes,	/* enum */
+	build_hashes,	/* forward */
+	build_hashes,	/* typedef */
+	tdtrav_assert,	/* typedef_unres */
+	build_hashes,	/* volatile */
+	build_hashes,	/* const */
+	build_hashes	/* restrict */
+};
+
+static void
+tdata_build_hashes_common(tdata_t *td, hash_t *hash)
+{
+	(void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL,
+	    build_hashes_cbs, td);
+}
+
+void
+tdata_build_hashes(tdata_t *td)
+{
+	tdata_build_hashes_common(td, td->td_iihash);
+}
+
+/* Merge td2 into td1.  td2 is destroyed by the merge */
+void
+tdata_merge(tdata_t *td1, tdata_t *td2)
+{
+	td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark);
+	td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen);
+	td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid);
+
+	hash_merge(td1->td_iihash, td2->td_iihash);
+
+	/* Add td2's type tree to the hashes */
+	tdata_build_hashes_common(td1, td2->td_iihash);
+
+	list_concat(&td1->td_fwdlist, td2->td_fwdlist);
+	td2->td_fwdlist = NULL;
+
+	slist_merge(&td1->td_labels, td2->td_labels,
+	    (int (*)())tdata_label_cmp);
+	td2->td_labels = NULL;
+
+	/* free the td2 hashes (data is now part of td1) */
+
+	hash_free(td2->td_layouthash, NULL, NULL);
+	td2->td_layouthash = NULL;
+
+	hash_free(td2->td_iihash, NULL, NULL);
+	td2->td_iihash = NULL;
+
+	tdata_free(td2);
+}