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 "%Z%%M% %I% %E% 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 */ 56 int 57 tdesc_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 113 int 114 tdesc_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 129 int 130 tdesc_idhash(int nbuckets, void *data) 131 { 132 tdesc_t *tdp = data; 133 134 return (tdp->t_id % nbuckets); 135 } 136 137 int 138 tdesc_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 148 int 149 tdesc_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 169 int 170 tdesc_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*/ 178 int 179 tdesc_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 188 static void 189 free_intr(tdesc_t *tdp) 190 { 191 free(tdp->t_intr); 192 } 193 194 static void 195 free_ardef(tdesc_t *tdp) 196 { 197 free(tdp->t_ardef); 198 } 199 200 static void 201 free_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 216 static void 217 free_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 232 static 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*/ 250 static int 251 tdesc_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 262 void 263 tdesc_free(tdesc_t *tdp) 264 { 265 (void) tdesc_free_cb(tdp, NULL); 266 } 267 268 static int 269 tdata_label_cmp(labelent_t *le1, labelent_t *le2) 270 { 271 return (le1->le_idx - le2->le_idx); 272 } 273 274 void 275 tdata_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 285 static int 286 tdata_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 296 labelent_t * 297 tdata_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 306 static int 307 tdata_label_find_cb(labelent_t *le, labelent_t *tmpl) 308 { 309 return (streq(le->le_name, tmpl->le_name)); 310 } 311 312 int 313 tdata_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 332 static int 333 tdata_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 346 void 347 tdata_label_newmax(tdata_t *td, int newmax) 348 { 349 (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax); 350 } 351 352 /*ARGSUSED1*/ 353 static void 354 tdata_label_free_cb(labelent_t *le, void *private) 355 { 356 if (le->le_name) 357 free(le->le_name); 358 free(le); 359 } 360 361 void 362 tdata_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 368 tdata_t * 369 tdata_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 391 void 392 tdata_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*/ 410 static int 411 build_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 421 static 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 438 static void 439 tdata_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 445 void 446 tdata_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 */ 452 void 453 tdata_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