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.
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.
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]
22 * Copyright 2010 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
27 * Routines for manipulating tdesc and tdata structures
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.
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.
55 tdesc_layouthash(int nbuckets, void *node)
64 switch (tdp->t_type) {
70 name = tdp->t_tdesc->t_name;
73 h = tdp->t_fndef->fn_nargs +
74 tdp->t_fndef->fn_vargs;
75 name = tdp->t_fndef->fn_ret->t_name;
78 h = tdp->t_ardef->ad_nelems;
79 name = tdp->t_ardef->ad_contents->t_name;
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.
89 if (tdp->t_members != NULL)
90 name = tdp->t_members->ml_name;
93 /* Use the first element in the hash value */
94 name = tdp->t_emem->el_name;
98 * Intrinsics, forwards, and typedefs all have
101 warning("Unexpected unnamed %d tdesc (ID %d)\n",
102 tdp->t_type, tdp->t_id);
107 return (hash_name(nbuckets, name));
109 return (h % nbuckets);
113 tdesc_layoutcmp(void *arg1, void *arg2)
115 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
117 if (tdp1->t_name == NULL) {
118 if (tdp2->t_name == NULL)
122 } else if (tdp2->t_name == NULL)
125 return (strcmp(tdp1->t_name, tdp2->t_name));
129 tdesc_idhash(int nbuckets, void *data)
133 return (tdp->t_id % nbuckets);
137 tdesc_idcmp(void *arg1, void *arg2)
139 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
141 if (tdp1->t_id == tdp2->t_id)
144 return (tdp1->t_id > tdp2->t_id ? 1 : -1);
148 tdesc_namehash(int nbuckets, void *data)
154 if (tdp->t_name == NULL)
157 for (h = 0, c = tdp->t_name; *c; c++) {
159 if ((g = (h & 0xf0000000)) != 0) {
165 return (h % nbuckets);
169 tdesc_namecmp(void *arg1, void *arg2)
171 tdesc_t *tdp1 = arg1, *tdp2 = arg2;
173 return (!streq(tdp1->t_name, tdp2->t_name));
179 tdesc_print(void *data, void *private __unused)
183 printf("%7d %s\n", tdp->t_id, tdesc_name(tdp));
190 free_intr(tdesc_t *tdp)
196 free_ardef(tdesc_t *tdp)
202 free_mlist(tdesc_t *tdp)
204 mlist_t *ml = tdp->t_members;
218 free_elist(tdesc_t *tdp)
220 elist_t *el = tdp->t_emem;
233 static void (*free_cbs[])(tdesc_t *) = {
252 tdesc_free_cb(void *arg, void *private __unused)
257 if (free_cbs[tdp->t_type])
258 free_cbs[tdp->t_type](tdp);
265 tdesc_free(tdesc_t *tdp)
267 tdesc_free_cb(tdp, NULL);
271 tdata_label_cmp(void *arg1, void *arg2)
273 labelent_t *le1 = arg1;
274 labelent_t *le2 = arg2;
275 return (le1->le_idx - le2->le_idx);
279 tdata_label_add(tdata_t *td, const char *label, int idx)
281 labelent_t *le = xmalloc(sizeof (*le));
283 le->le_name = xstrdup(label);
284 le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx);
286 slist_add(&td->td_labels, le, tdata_label_cmp);
290 tdata_label_top_cb(void *data, void *arg)
292 labelent_t *le = data;
293 labelent_t **topp = arg;
301 tdata_label_top(tdata_t *td)
303 labelent_t *top = NULL;
305 (void) list_iter(td->td_labels, tdata_label_top_cb, &top);
311 tdata_label_find_cb(void *arg1, void *arg2)
313 labelent_t *le = arg1;
314 labelent_t *tmpl = arg2;
315 return (streq(le->le_name, tmpl->le_name));
319 tdata_label_find(tdata_t *td, char *label)
324 if (streq(label, "BASE")) {
325 ret = (labelent_t *)list_first(td->td_labels);
326 return (ret ? ret->le_idx : -1);
331 if (!(ret = (labelent_t *)list_find(td->td_labels, &let,
332 tdata_label_find_cb)))
335 return (ret->le_idx);
339 tdata_label_newmax_cb(void *data, void *arg)
341 labelent_t *le = data;
344 if (le->le_idx > *newmaxp) {
345 le->le_idx = *newmaxp;
353 tdata_label_newmax(tdata_t *td, int newmax)
355 (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax);
360 tdata_label_free_cb(void *arg, void *private __unused)
362 labelent_t *le = arg;
369 tdata_label_free(tdata_t *td)
371 list_free(td->td_labels, tdata_label_free_cb, NULL);
372 td->td_labels = NULL;
378 tdata_t *new = xcalloc(sizeof (tdata_t));
380 new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash,
382 new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash,
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.
389 new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL);
393 pthread_mutex_init(&new->td_mergelock, NULL);
399 tdata_free(tdata_t *td)
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);
406 tdata_label_free(td);
408 free(td->td_parlabel);
409 free(td->td_parname);
411 pthread_mutex_destroy(&td->td_mergelock);
418 build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private)
420 tdata_t *td = private;
422 hash_add(td->td_idhash, ctdp);
423 hash_add(td->td_layouthash, ctdp);
428 static tdtrav_cb_f build_hashes_cbs[] = {
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 */
446 tdata_build_hashes_common(tdata_t *td, hash_t *hash)
448 (void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL,
449 build_hashes_cbs, td);
453 tdata_build_hashes(tdata_t *td)
455 tdata_build_hashes_common(td, td->td_iihash);
458 /* Merge td2 into td1. td2 is destroyed by the merge */
460 tdata_merge(tdata_t *td1, tdata_t *td2)
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);
466 hash_merge(td1->td_iihash, td2->td_iihash);
468 /* Add td2's type tree to the hashes */
469 tdata_build_hashes_common(td1, td2->td_iihash);
471 list_concat(&td1->td_fwdlist, td2->td_fwdlist);
472 td2->td_fwdlist = NULL;
474 slist_merge(&td1->td_labels, td2->td_labels,
476 td2->td_labels = NULL;
478 /* free the td2 hashes (data is now part of td1) */
480 hash_free(td2->td_layouthash, NULL, NULL);
481 td2->td_layouthash = NULL;
483 hash_free(td2->td_iihash, NULL, NULL);
484 td2->td_iihash = NULL;