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 #if defined(sun) 178 /*ARGSUSED1*/ 179 static int 180 tdesc_print(void *data, void *private __unused) 181 { 182 tdesc_t *tdp = data; 183 184 printf("%7d %s\n", tdp->t_id, tdesc_name(tdp)); 185 186 return (1); 187 } 188 #endif 189 190 static void 191 free_intr(tdesc_t *tdp) 192 { 193 free(tdp->t_intr); 194 } 195 196 static void 197 free_ardef(tdesc_t *tdp) 198 { 199 free(tdp->t_ardef); 200 } 201 202 static void 203 free_mlist(tdesc_t *tdp) 204 { 205 mlist_t *ml = tdp->t_members; 206 mlist_t *oml; 207 208 while (ml) { 209 oml = ml; 210 ml = ml->ml_next; 211 212 if (oml->ml_name) 213 free(oml->ml_name); 214 free(oml); 215 } 216 } 217 218 static void 219 free_elist(tdesc_t *tdp) 220 { 221 elist_t *el = tdp->t_emem; 222 elist_t *oel; 223 224 while (el) { 225 oel = el; 226 el = el->el_next; 227 228 if (oel->el_name) 229 free(oel->el_name); 230 free(oel); 231 } 232 } 233 234 static void (*free_cbs[])(tdesc_t *) = { 235 NULL, 236 free_intr, 237 NULL, 238 free_ardef, 239 NULL, 240 free_mlist, 241 free_mlist, 242 free_elist, 243 NULL, 244 NULL, 245 NULL, 246 NULL, 247 NULL, 248 NULL 249 }; 250 251 /*ARGSUSED1*/ 252 static void 253 tdesc_free_cb(void *arg, void *private __unused) 254 { 255 tdesc_t *tdp = arg; 256 if (tdp->t_name) 257 free(tdp->t_name); 258 if (free_cbs[tdp->t_type]) 259 free_cbs[tdp->t_type](tdp); 260 free(tdp); 261 262 return; 263 } 264 265 void 266 tdesc_free(tdesc_t *tdp) 267 { 268 tdesc_free_cb(tdp, NULL); 269 } 270 271 static int 272 tdata_label_cmp(void *arg1, void *arg2) 273 { 274 labelent_t *le1 = arg1; 275 labelent_t *le2 = arg2; 276 return (le1->le_idx - le2->le_idx); 277 } 278 279 void 280 tdata_label_add(tdata_t *td, const char *label, int idx) 281 { 282 labelent_t *le = xmalloc(sizeof (*le)); 283 284 le->le_name = xstrdup(label); 285 le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx); 286 287 slist_add(&td->td_labels, le, tdata_label_cmp); 288 } 289 290 static int 291 tdata_label_top_cb(void *data, void *arg) 292 { 293 labelent_t *le = data; 294 labelent_t **topp = arg; 295 296 *topp = le; 297 298 return (1); 299 } 300 301 labelent_t * 302 tdata_label_top(tdata_t *td) 303 { 304 labelent_t *top = NULL; 305 306 (void) list_iter(td->td_labels, tdata_label_top_cb, &top); 307 308 return (top); 309 } 310 311 static int 312 tdata_label_find_cb(void *arg1, void *arg2) 313 { 314 labelent_t *le = arg1; 315 labelent_t *tmpl = arg2; 316 return (streq(le->le_name, tmpl->le_name)); 317 } 318 319 int 320 tdata_label_find(tdata_t *td, char *label) 321 { 322 labelent_t let; 323 labelent_t *ret; 324 325 if (streq(label, "BASE")) { 326 ret = (labelent_t *)list_first(td->td_labels); 327 return (ret ? ret->le_idx : -1); 328 } 329 330 let.le_name = label; 331 332 if (!(ret = (labelent_t *)list_find(td->td_labels, &let, 333 tdata_label_find_cb))) 334 return (-1); 335 336 return (ret->le_idx); 337 } 338 339 static int 340 tdata_label_newmax_cb(void *data, void *arg) 341 { 342 labelent_t *le = data; 343 int *newmaxp = arg; 344 345 if (le->le_idx > *newmaxp) { 346 le->le_idx = *newmaxp; 347 return (1); 348 } 349 350 return (0); 351 } 352 353 void 354 tdata_label_newmax(tdata_t *td, int newmax) 355 { 356 (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax); 357 } 358 359 /*ARGSUSED1*/ 360 static void 361 tdata_label_free_cb(void *arg, void *private __unused) 362 { 363 labelent_t *le = arg; 364 if (le->le_name) 365 free(le->le_name); 366 free(le); 367 } 368 369 void 370 tdata_label_free(tdata_t *td) 371 { 372 list_free(td->td_labels, tdata_label_free_cb, NULL); 373 td->td_labels = NULL; 374 } 375 376 tdata_t * 377 tdata_new(void) 378 { 379 tdata_t *new = xcalloc(sizeof (tdata_t)); 380 381 new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, 382 tdesc_layoutcmp); 383 new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash, 384 tdesc_idcmp); 385 /* 386 * This is also traversed as a list, but amortized O(1) 387 * lookup massively impacts part of the merge phase, so 388 * we store the iidescs as a hash. 389 */ 390 new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL); 391 new->td_nextid = 1; 392 new->td_curvgen = 1; 393 394 pthread_mutex_init(&new->td_mergelock, NULL); 395 396 return (new); 397 } 398 399 void 400 tdata_free(tdata_t *td) 401 { 402 hash_free(td->td_iihash, iidesc_free, NULL); 403 hash_free(td->td_layouthash, tdesc_free_cb, NULL); 404 hash_free(td->td_idhash, NULL, NULL); 405 list_free(td->td_fwdlist, NULL, NULL); 406 407 tdata_label_free(td); 408 409 free(td->td_parlabel); 410 free(td->td_parname); 411 412 pthread_mutex_destroy(&td->td_mergelock); 413 414 free(td); 415 } 416 417 /*ARGSUSED1*/ 418 static int 419 build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 420 { 421 tdata_t *td = private; 422 423 hash_add(td->td_idhash, ctdp); 424 hash_add(td->td_layouthash, ctdp); 425 426 return (1); 427 } 428 429 static tdtrav_cb_f build_hashes_cbs[] = { 430 NULL, 431 build_hashes, /* intrinsic */ 432 build_hashes, /* pointer */ 433 build_hashes, /* array */ 434 build_hashes, /* function */ 435 build_hashes, /* struct */ 436 build_hashes, /* union */ 437 build_hashes, /* enum */ 438 build_hashes, /* forward */ 439 build_hashes, /* typedef */ 440 tdtrav_assert, /* typedef_unres */ 441 build_hashes, /* volatile */ 442 build_hashes, /* const */ 443 build_hashes /* restrict */ 444 }; 445 446 static void 447 tdata_build_hashes_common(tdata_t *td, hash_t *hash) 448 { 449 (void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL, 450 build_hashes_cbs, td); 451 } 452 453 void 454 tdata_build_hashes(tdata_t *td) 455 { 456 tdata_build_hashes_common(td, td->td_iihash); 457 } 458 459 /* Merge td2 into td1. td2 is destroyed by the merge */ 460 void 461 tdata_merge(tdata_t *td1, tdata_t *td2) 462 { 463 td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark); 464 td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen); 465 td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid); 466 467 hash_merge(td1->td_iihash, td2->td_iihash); 468 469 /* Add td2's type tree to the hashes */ 470 tdata_build_hashes_common(td1, td2->td_iihash); 471 472 list_concat(&td1->td_fwdlist, td2->td_fwdlist); 473 td2->td_fwdlist = NULL; 474 475 slist_merge(&td1->td_labels, td2->td_labels, 476 tdata_label_cmp); 477 td2->td_labels = NULL; 478 479 /* free the td2 hashes (data is now part of td1) */ 480 481 hash_free(td2->td_layouthash, NULL, NULL); 482 td2->td_layouthash = NULL; 483 484 hash_free(td2->td_iihash, NULL, NULL); 485 td2->td_iihash = NULL; 486 487 tdata_free(td2); 488 } 489