1178481Sjb/* 2178481Sjb * CDDL HEADER START 3178481Sjb * 4178481Sjb * The contents of this file are subject to the terms of the 5178481Sjb * Common Development and Distribution License (the "License"). 6178481Sjb * You may not use this file except in compliance with the License. 7178481Sjb * 8178481Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9178481Sjb * or http://www.opensolaris.org/os/licensing. 10178481Sjb * See the License for the specific language governing permissions 11178481Sjb * and limitations under the License. 12178481Sjb * 13178481Sjb * When distributing Covered Code, include this CDDL HEADER in each 14178481Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15178481Sjb * If applicable, add the following below this CDDL HEADER, with the 16178481Sjb * fields enclosed by brackets "[]" replaced with your own identifying 17178481Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 18178481Sjb * 19178481Sjb * CDDL HEADER END 20178481Sjb */ 21178481Sjb/* 22210767Srpaulo * Copyright 2010 Sun Microsystems, Inc. All rights reserved. 23178481Sjb * Use is subject to license terms. 24178481Sjb */ 25178481Sjb 26178481Sjb/* 27178481Sjb * Routines for manipulating tdesc and tdata structures 28178481Sjb */ 29178481Sjb 30178481Sjb#include <stdio.h> 31178481Sjb#include <stdlib.h> 32178481Sjb#include <strings.h> 33178481Sjb#include <pthread.h> 34178481Sjb 35178481Sjb#include "ctftools.h" 36178481Sjb#include "memory.h" 37178481Sjb#include "traverse.h" 38178481Sjb 39178481Sjb/* 40178481Sjb * The layout hash is used during the equivalency checking. We have a node in 41178481Sjb * the child graph that may be equivalent to a node in the parent graph. To 42178481Sjb * find the corresponding node (if any) in the parent, we need a quick way to 43178481Sjb * get to all nodes in the parent that look like the node in the child. Since a 44178481Sjb * large number of nodes don't have names, we need to incorporate the layout of 45178481Sjb * the node into the hash. If we don't, we'll end up with the vast majority of 46178481Sjb * nodes in bucket zero, with one or two nodes in each of the remaining buckets. 47178481Sjb * 48178481Sjb * There are a couple of constraints, both of which concern forward 49178481Sjb * declarations. Recall that a forward declaration tdesc is equivalent to a 50178481Sjb * tdesc that actually defines the structure or union. As such, we cannot 51178481Sjb * incorporate anything into the hash for a named struct or union node that 52178481Sjb * couldn't be found by looking at the forward, and vice versa. 53178481Sjb */ 54178481Sjbint 55178481Sjbtdesc_layouthash(int nbuckets, void *node) 56178481Sjb{ 57178481Sjb tdesc_t *tdp = node; 58178481Sjb char *name = NULL; 59178481Sjb ulong_t h = 0; 60178481Sjb 61178481Sjb if (tdp->t_name) 62178481Sjb name = tdp->t_name; 63178481Sjb else { 64178481Sjb switch (tdp->t_type) { 65178481Sjb case POINTER: 66178481Sjb case TYPEDEF: 67178481Sjb case VOLATILE: 68178481Sjb case CONST: 69178481Sjb case RESTRICT: 70178481Sjb name = tdp->t_tdesc->t_name; 71178481Sjb break; 72178481Sjb case FUNCTION: 73178481Sjb h = tdp->t_fndef->fn_nargs + 74178481Sjb tdp->t_fndef->fn_vargs; 75178481Sjb name = tdp->t_fndef->fn_ret->t_name; 76178481Sjb break; 77178481Sjb case ARRAY: 78178481Sjb h = tdp->t_ardef->ad_nelems; 79178481Sjb name = tdp->t_ardef->ad_contents->t_name; 80178481Sjb break; 81178481Sjb case STRUCT: 82178481Sjb case UNION: 83178481Sjb /* 84178481Sjb * Unnamed structures, which cannot have forward 85178481Sjb * declarations pointing to them. We can therefore 86178481Sjb * incorporate the name of the first member into 87210767Srpaulo * the hash value, assuming there are any. 88178481Sjb */ 89210767Srpaulo if (tdp->t_members != NULL) 90210767Srpaulo name = tdp->t_members->ml_name; 91178481Sjb break; 92178481Sjb case ENUM: 93178481Sjb /* Use the first element in the hash value */ 94178481Sjb name = tdp->t_emem->el_name; 95178481Sjb break; 96178481Sjb default: 97178481Sjb /* 98178481Sjb * Intrinsics, forwards, and typedefs all have 99178481Sjb * names. 100178481Sjb */ 101178481Sjb warning("Unexpected unnamed %d tdesc (ID %d)\n", 102178481Sjb tdp->t_type, tdp->t_id); 103178481Sjb } 104178481Sjb } 105178481Sjb 106178481Sjb if (name) 107178481Sjb return (hash_name(nbuckets, name)); 108178481Sjb 109178481Sjb return (h % nbuckets); 110178481Sjb} 111178481Sjb 112178481Sjbint 113178481Sjbtdesc_layoutcmp(void *arg1, void *arg2) 114178481Sjb{ 115178481Sjb tdesc_t *tdp1 = arg1, *tdp2 = arg2; 116178481Sjb 117178481Sjb if (tdp1->t_name == NULL) { 118178481Sjb if (tdp2->t_name == NULL) 119178481Sjb return (0); 120178481Sjb else 121178481Sjb return (-1); 122178481Sjb } else if (tdp2->t_name == NULL) 123178481Sjb return (1); 124178481Sjb else 125178481Sjb return (strcmp(tdp1->t_name, tdp2->t_name)); 126178481Sjb} 127178481Sjb 128178481Sjbint 129178481Sjbtdesc_idhash(int nbuckets, void *data) 130178481Sjb{ 131178481Sjb tdesc_t *tdp = data; 132178481Sjb 133178481Sjb return (tdp->t_id % nbuckets); 134178481Sjb} 135178481Sjb 136178481Sjbint 137178481Sjbtdesc_idcmp(void *arg1, void *arg2) 138178481Sjb{ 139178481Sjb tdesc_t *tdp1 = arg1, *tdp2 = arg2; 140178481Sjb 141178481Sjb if (tdp1->t_id == tdp2->t_id) 142178481Sjb return (0); 143178481Sjb else 144178481Sjb return (tdp1->t_id > tdp2->t_id ? 1 : -1); 145178481Sjb} 146178481Sjb 147178481Sjbint 148178481Sjbtdesc_namehash(int nbuckets, void *data) 149178481Sjb{ 150178481Sjb tdesc_t *tdp = data; 151178481Sjb ulong_t h, g; 152178481Sjb char *c; 153178481Sjb 154178481Sjb if (tdp->t_name == NULL) 155178481Sjb return (0); 156178481Sjb 157178481Sjb for (h = 0, c = tdp->t_name; *c; c++) { 158178481Sjb h = (h << 4) + *c; 159178481Sjb if ((g = (h & 0xf0000000)) != 0) { 160178481Sjb h ^= (g >> 24); 161178481Sjb h ^= g; 162178481Sjb } 163178481Sjb } 164178481Sjb 165178481Sjb return (h % nbuckets); 166178481Sjb} 167178481Sjb 168178481Sjbint 169178481Sjbtdesc_namecmp(void *arg1, void *arg2) 170178481Sjb{ 171178481Sjb tdesc_t *tdp1 = arg1, *tdp2 = arg2; 172178481Sjb 173178481Sjb return (!streq(tdp1->t_name, tdp2->t_name)); 174178481Sjb} 175178481Sjb 176178546Sjb#if defined(sun) 177178481Sjb/*ARGSUSED1*/ 178178546Sjbstatic int 179178546Sjbtdesc_print(void *data, void *private __unused) 180178481Sjb{ 181178481Sjb tdesc_t *tdp = data; 182178481Sjb 183178481Sjb printf("%7d %s\n", tdp->t_id, tdesc_name(tdp)); 184178481Sjb 185178481Sjb return (1); 186178481Sjb} 187178546Sjb#endif 188178481Sjb 189178481Sjbstatic void 190178481Sjbfree_intr(tdesc_t *tdp) 191178481Sjb{ 192178481Sjb free(tdp->t_intr); 193178481Sjb} 194178481Sjb 195178481Sjbstatic void 196178481Sjbfree_ardef(tdesc_t *tdp) 197178481Sjb{ 198178481Sjb free(tdp->t_ardef); 199178481Sjb} 200178481Sjb 201178481Sjbstatic void 202178481Sjbfree_mlist(tdesc_t *tdp) 203178481Sjb{ 204178481Sjb mlist_t *ml = tdp->t_members; 205178481Sjb mlist_t *oml; 206178481Sjb 207178481Sjb while (ml) { 208178481Sjb oml = ml; 209178481Sjb ml = ml->ml_next; 210178481Sjb 211178481Sjb if (oml->ml_name) 212178481Sjb free(oml->ml_name); 213178481Sjb free(oml); 214178481Sjb } 215178481Sjb} 216178481Sjb 217178481Sjbstatic void 218178481Sjbfree_elist(tdesc_t *tdp) 219178481Sjb{ 220178481Sjb elist_t *el = tdp->t_emem; 221178481Sjb elist_t *oel; 222178481Sjb 223178481Sjb while (el) { 224178481Sjb oel = el; 225178481Sjb el = el->el_next; 226178481Sjb 227178481Sjb if (oel->el_name) 228178481Sjb free(oel->el_name); 229178481Sjb free(oel); 230178481Sjb } 231178481Sjb} 232178481Sjb 233178481Sjbstatic void (*free_cbs[])(tdesc_t *) = { 234178481Sjb NULL, 235178481Sjb free_intr, 236178481Sjb NULL, 237178481Sjb free_ardef, 238178481Sjb NULL, 239178481Sjb free_mlist, 240178481Sjb free_mlist, 241178481Sjb free_elist, 242178481Sjb NULL, 243178481Sjb NULL, 244178481Sjb NULL, 245178481Sjb NULL, 246178481Sjb NULL, 247178481Sjb NULL 248178481Sjb}; 249178481Sjb 250178481Sjb/*ARGSUSED1*/ 251178546Sjbstatic void 252178546Sjbtdesc_free_cb(void *arg, void *private __unused) 253178481Sjb{ 254178546Sjb tdesc_t *tdp = arg; 255178481Sjb if (tdp->t_name) 256178481Sjb free(tdp->t_name); 257178481Sjb if (free_cbs[tdp->t_type]) 258178481Sjb free_cbs[tdp->t_type](tdp); 259178481Sjb free(tdp); 260178481Sjb 261178546Sjb return; 262178481Sjb} 263178481Sjb 264178481Sjbvoid 265178481Sjbtdesc_free(tdesc_t *tdp) 266178481Sjb{ 267178546Sjb tdesc_free_cb(tdp, NULL); 268178481Sjb} 269178481Sjb 270178481Sjbstatic int 271178546Sjbtdata_label_cmp(void *arg1, void *arg2) 272178481Sjb{ 273178546Sjb labelent_t *le1 = arg1; 274178546Sjb labelent_t *le2 = arg2; 275178481Sjb return (le1->le_idx - le2->le_idx); 276178481Sjb} 277178481Sjb 278178481Sjbvoid 279178546Sjbtdata_label_add(tdata_t *td, const char *label, int idx) 280178481Sjb{ 281178481Sjb labelent_t *le = xmalloc(sizeof (*le)); 282178481Sjb 283178481Sjb le->le_name = xstrdup(label); 284178481Sjb le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx); 285178481Sjb 286178546Sjb slist_add(&td->td_labels, le, tdata_label_cmp); 287178481Sjb} 288178481Sjb 289178481Sjbstatic int 290178481Sjbtdata_label_top_cb(void *data, void *arg) 291178481Sjb{ 292178481Sjb labelent_t *le = data; 293178481Sjb labelent_t **topp = arg; 294178481Sjb 295178481Sjb *topp = le; 296178481Sjb 297178481Sjb return (1); 298178481Sjb} 299178481Sjb 300178481Sjblabelent_t * 301178481Sjbtdata_label_top(tdata_t *td) 302178481Sjb{ 303178481Sjb labelent_t *top = NULL; 304178481Sjb 305178481Sjb (void) list_iter(td->td_labels, tdata_label_top_cb, &top); 306178481Sjb 307178481Sjb return (top); 308178481Sjb} 309178481Sjb 310178481Sjbstatic int 311178546Sjbtdata_label_find_cb(void *arg1, void *arg2) 312178481Sjb{ 313178546Sjb labelent_t *le = arg1; 314178546Sjb labelent_t *tmpl = arg2; 315178481Sjb return (streq(le->le_name, tmpl->le_name)); 316178481Sjb} 317178481Sjb 318178481Sjbint 319178481Sjbtdata_label_find(tdata_t *td, char *label) 320178481Sjb{ 321178481Sjb labelent_t let; 322178481Sjb labelent_t *ret; 323178481Sjb 324178481Sjb if (streq(label, "BASE")) { 325178481Sjb ret = (labelent_t *)list_first(td->td_labels); 326178481Sjb return (ret ? ret->le_idx : -1); 327178481Sjb } 328178481Sjb 329178481Sjb let.le_name = label; 330178481Sjb 331178481Sjb if (!(ret = (labelent_t *)list_find(td->td_labels, &let, 332178546Sjb tdata_label_find_cb))) 333178481Sjb return (-1); 334178481Sjb 335178481Sjb return (ret->le_idx); 336178481Sjb} 337178481Sjb 338178481Sjbstatic int 339178481Sjbtdata_label_newmax_cb(void *data, void *arg) 340178481Sjb{ 341178481Sjb labelent_t *le = data; 342178481Sjb int *newmaxp = arg; 343178481Sjb 344178481Sjb if (le->le_idx > *newmaxp) { 345178481Sjb le->le_idx = *newmaxp; 346178481Sjb return (1); 347178481Sjb } 348178481Sjb 349178481Sjb return (0); 350178481Sjb} 351178481Sjb 352178481Sjbvoid 353178481Sjbtdata_label_newmax(tdata_t *td, int newmax) 354178481Sjb{ 355178481Sjb (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax); 356178481Sjb} 357178481Sjb 358178481Sjb/*ARGSUSED1*/ 359178481Sjbstatic void 360178546Sjbtdata_label_free_cb(void *arg, void *private __unused) 361178481Sjb{ 362178546Sjb labelent_t *le = arg; 363178481Sjb if (le->le_name) 364178481Sjb free(le->le_name); 365178481Sjb free(le); 366178481Sjb} 367178481Sjb 368178481Sjbvoid 369178481Sjbtdata_label_free(tdata_t *td) 370178481Sjb{ 371178546Sjb list_free(td->td_labels, tdata_label_free_cb, NULL); 372178481Sjb td->td_labels = NULL; 373178481Sjb} 374178481Sjb 375178481Sjbtdata_t * 376178481Sjbtdata_new(void) 377178481Sjb{ 378178481Sjb tdata_t *new = xcalloc(sizeof (tdata_t)); 379178481Sjb 380178481Sjb new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, 381178481Sjb tdesc_layoutcmp); 382178481Sjb new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash, 383178481Sjb tdesc_idcmp); 384178481Sjb /* 385178481Sjb * This is also traversed as a list, but amortized O(1) 386178481Sjb * lookup massively impacts part of the merge phase, so 387178481Sjb * we store the iidescs as a hash. 388178481Sjb */ 389178481Sjb new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL); 390178481Sjb new->td_nextid = 1; 391178481Sjb new->td_curvgen = 1; 392178481Sjb 393178481Sjb pthread_mutex_init(&new->td_mergelock, NULL); 394178481Sjb 395178481Sjb return (new); 396178481Sjb} 397178481Sjb 398178481Sjbvoid 399178481Sjbtdata_free(tdata_t *td) 400178481Sjb{ 401178546Sjb hash_free(td->td_iihash, iidesc_free, NULL); 402178546Sjb hash_free(td->td_layouthash, tdesc_free_cb, NULL); 403178481Sjb hash_free(td->td_idhash, NULL, NULL); 404178481Sjb list_free(td->td_fwdlist, NULL, NULL); 405178481Sjb 406178481Sjb tdata_label_free(td); 407178481Sjb 408178481Sjb free(td->td_parlabel); 409178481Sjb free(td->td_parname); 410178481Sjb 411178481Sjb pthread_mutex_destroy(&td->td_mergelock); 412178481Sjb 413178481Sjb free(td); 414178481Sjb} 415178481Sjb 416178481Sjb/*ARGSUSED1*/ 417178481Sjbstatic int 418178546Sjbbuild_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 419178481Sjb{ 420178481Sjb tdata_t *td = private; 421178481Sjb 422178481Sjb hash_add(td->td_idhash, ctdp); 423178481Sjb hash_add(td->td_layouthash, ctdp); 424178481Sjb 425178481Sjb return (1); 426178481Sjb} 427178481Sjb 428178481Sjbstatic tdtrav_cb_f build_hashes_cbs[] = { 429178481Sjb NULL, 430178481Sjb build_hashes, /* intrinsic */ 431178481Sjb build_hashes, /* pointer */ 432178481Sjb build_hashes, /* array */ 433178481Sjb build_hashes, /* function */ 434178481Sjb build_hashes, /* struct */ 435178481Sjb build_hashes, /* union */ 436178481Sjb build_hashes, /* enum */ 437178481Sjb build_hashes, /* forward */ 438178481Sjb build_hashes, /* typedef */ 439178481Sjb tdtrav_assert, /* typedef_unres */ 440178481Sjb build_hashes, /* volatile */ 441178481Sjb build_hashes, /* const */ 442178481Sjb build_hashes /* restrict */ 443178481Sjb}; 444178481Sjb 445178481Sjbstatic void 446178481Sjbtdata_build_hashes_common(tdata_t *td, hash_t *hash) 447178481Sjb{ 448178481Sjb (void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL, 449178481Sjb build_hashes_cbs, td); 450178481Sjb} 451178481Sjb 452178481Sjbvoid 453178481Sjbtdata_build_hashes(tdata_t *td) 454178481Sjb{ 455178481Sjb tdata_build_hashes_common(td, td->td_iihash); 456178481Sjb} 457178481Sjb 458178481Sjb/* Merge td2 into td1. td2 is destroyed by the merge */ 459178481Sjbvoid 460178481Sjbtdata_merge(tdata_t *td1, tdata_t *td2) 461178481Sjb{ 462178481Sjb td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark); 463178481Sjb td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen); 464178481Sjb td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid); 465178481Sjb 466178481Sjb hash_merge(td1->td_iihash, td2->td_iihash); 467178481Sjb 468178481Sjb /* Add td2's type tree to the hashes */ 469178481Sjb tdata_build_hashes_common(td1, td2->td_iihash); 470178481Sjb 471178481Sjb list_concat(&td1->td_fwdlist, td2->td_fwdlist); 472178481Sjb td2->td_fwdlist = NULL; 473178481Sjb 474178481Sjb slist_merge(&td1->td_labels, td2->td_labels, 475178546Sjb tdata_label_cmp); 476178481Sjb td2->td_labels = NULL; 477178481Sjb 478178481Sjb /* free the td2 hashes (data is now part of td1) */ 479178481Sjb 480178481Sjb hash_free(td2->td_layouthash, NULL, NULL); 481178481Sjb td2->td_layouthash = NULL; 482178481Sjb 483178481Sjb hash_free(td2->td_iihash, NULL, NULL); 484178481Sjb td2->td_iihash = NULL; 485178481Sjb 486178481Sjb tdata_free(td2); 487178481Sjb} 488