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