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 2010 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26 /* 27 * Routines for manipulating tdesc and tdata structures 28 */ 29 30 #if HAVE_NBTOOL_CONFIG_H 31 # include "nbtool_config.h" 32 #endif 33 34 #include <stdio.h> 35 #include <stdlib.h> 36 #include <strings.h> 37 #include <pthread.h> 38 39 #include "ctftools.h" 40 #include "memory.h" 41 #include "traverse.h" 42 43 /* 44 * The layout hash is used during the equivalency checking. We have a node in 45 * the child graph that may be equivalent to a node in the parent graph. To 46 * find the corresponding node (if any) in the parent, we need a quick way to 47 * get to all nodes in the parent that look like the node in the child. Since a 48 * large number of nodes don't have names, we need to incorporate the layout of 49 * the node into the hash. If we don't, we'll end up with the vast majority of 50 * nodes in bucket zero, with one or two nodes in each of the remaining buckets. 51 * 52 * There are a couple of constraints, both of which concern forward 53 * declarations. Recall that a forward declaration tdesc is equivalent to a 54 * tdesc that actually defines the structure or union. As such, we cannot 55 * incorporate anything into the hash for a named struct or union node that 56 * couldn't be found by looking at the forward, and vice versa. 57 */ 58 int 59 tdesc_layouthash(int nbuckets, void *node) 60 { 61 tdesc_t *tdp = node; 62 char *name = NULL; 63 ulong_t h = 0; 64 65 if (tdp->t_name) 66 name = tdp->t_name; 67 else { 68 switch (tdp->t_type) { 69 case POINTER: 70 case TYPEDEF: 71 case VOLATILE: 72 case CONST: 73 case RESTRICT: 74 name = tdp->t_tdesc->t_name; 75 break; 76 case FUNCTION: 77 h = tdp->t_fndef->fn_nargs + 78 tdp->t_fndef->fn_vargs; 79 name = tdp->t_fndef->fn_ret->t_name; 80 break; 81 case ARRAY: 82 h = tdp->t_ardef->ad_nelems; 83 name = tdp->t_ardef->ad_contents->t_name; 84 break; 85 case STRUCT: 86 case UNION: 87 /* 88 * Unnamed structures, which cannot have forward 89 * declarations pointing to them. We can therefore 90 * incorporate the name of the first member into 91 * the hash value, assuming there are any. 92 */ 93 if (tdp->t_members != NULL) 94 name = tdp->t_members->ml_name; 95 break; 96 case ENUM: 97 /* Use the first element in the hash value */ 98 name = tdp->t_emem->el_name; 99 break; 100 default: 101 /* 102 * Intrinsics, forwards, and typedefs all have 103 * names. 104 */ 105 warning("Unexpected unnamed %d tdesc (ID %d)\n", 106 tdp->t_type, tdp->t_id); 107 } 108 } 109 110 if (name) 111 return (hash_name(nbuckets, name)); 112 113 return (h % nbuckets); 114 } 115 116 int 117 tdesc_layoutcmp(void *arg1, void *arg2) 118 { 119 tdesc_t *tdp1 = arg1, *tdp2 = arg2; 120 121 if (tdp1->t_name == NULL) { 122 if (tdp2->t_name == NULL) 123 return (0); 124 else 125 return (-1); 126 } else if (tdp2->t_name == NULL) 127 return (1); 128 else 129 return (strcmp(tdp1->t_name, tdp2->t_name)); 130 } 131 132 int 133 tdesc_idhash(int nbuckets, void *data) 134 { 135 tdesc_t *tdp = data; 136 137 return (tdp->t_id % nbuckets); 138 } 139 140 int 141 tdesc_idcmp(void *arg1, void *arg2) 142 { 143 tdesc_t *tdp1 = arg1, *tdp2 = arg2; 144 145 if (tdp1->t_id == tdp2->t_id) 146 return (0); 147 else 148 return (tdp1->t_id > tdp2->t_id ? 1 : -1); 149 } 150 151 int 152 tdesc_namehash(int nbuckets, void *data) 153 { 154 tdesc_t *tdp = data; 155 ulong_t h, g; 156 char *c; 157 158 if (tdp->t_name == NULL) 159 return (0); 160 161 for (h = 0, c = tdp->t_name; *c; c++) { 162 h = (h << 4) + *c; 163 if ((g = (h & 0xf0000000)) != 0) { 164 h ^= (g >> 24); 165 h ^= g; 166 } 167 } 168 169 return (h % nbuckets); 170 } 171 172 int 173 tdesc_namecmp(void *arg1, void *arg2) 174 { 175 tdesc_t *tdp1 = arg1, *tdp2 = arg2; 176 177 return (!streq(tdp1->t_name, tdp2->t_name)); 178 } 179 180 #if defined(sun) 181 /*ARGSUSED1*/ 182 static int 183 tdesc_print(void *data, void *private __unused) 184 { 185 tdesc_t *tdp = data; 186 187 printf("%7d %s\n", tdp->t_id, tdesc_name(tdp)); 188 189 return (1); 190 } 191 #endif 192 193 static void 194 free_intr(tdesc_t *tdp) 195 { 196 free(tdp->t_intr); 197 } 198 199 static void 200 free_ardef(tdesc_t *tdp) 201 { 202 free(tdp->t_ardef); 203 } 204 205 static void 206 free_mlist(tdesc_t *tdp) 207 { 208 mlist_t *ml = tdp->t_members; 209 mlist_t *oml; 210 211 while (ml) { 212 oml = ml; 213 ml = ml->ml_next; 214 215 if (oml->ml_name) 216 free(oml->ml_name); 217 free(oml); 218 } 219 } 220 221 static void 222 free_elist(tdesc_t *tdp) 223 { 224 elist_t *el = tdp->t_emem; 225 elist_t *oel; 226 227 while (el) { 228 oel = el; 229 el = el->el_next; 230 231 if (oel->el_name) 232 free(oel->el_name); 233 free(oel); 234 } 235 } 236 237 static void (*free_cbs[])(tdesc_t *) = { 238 NULL, 239 free_intr, 240 NULL, 241 free_ardef, 242 NULL, 243 free_mlist, 244 free_mlist, 245 free_elist, 246 NULL, 247 NULL, 248 NULL, 249 NULL, 250 NULL, 251 NULL 252 }; 253 254 /*ARGSUSED1*/ 255 static void 256 tdesc_free_cb(void *arg, void *private __unused) 257 { 258 tdesc_t *tdp = arg; 259 if (tdp->t_name) 260 free(tdp->t_name); 261 if (free_cbs[tdp->t_type]) 262 free_cbs[tdp->t_type](tdp); 263 free(tdp); 264 265 return; 266 } 267 268 void 269 tdesc_free(tdesc_t *tdp) 270 { 271 tdesc_free_cb(tdp, NULL); 272 } 273 274 static int 275 tdata_label_cmp(void *arg1, void *arg2) 276 { 277 labelent_t *le1 = arg1; 278 labelent_t *le2 = arg2; 279 return (le1->le_idx - le2->le_idx); 280 } 281 282 void 283 tdata_label_add(tdata_t *td, const char *label, int idx) 284 { 285 labelent_t *le = xmalloc(sizeof (*le)); 286 287 le->le_name = xstrdup(label); 288 le->le_idx = (idx == -1 ? td->td_nextid - 1 : idx); 289 290 slist_add(&td->td_labels, le, tdata_label_cmp); 291 } 292 293 static int 294 tdata_label_top_cb(void *data, void *arg) 295 { 296 labelent_t *le = data; 297 labelent_t **topp = arg; 298 299 *topp = le; 300 301 return (1); 302 } 303 304 labelent_t * 305 tdata_label_top(tdata_t *td) 306 { 307 labelent_t *top = NULL; 308 309 (void) list_iter(td->td_labels, tdata_label_top_cb, &top); 310 311 return (top); 312 } 313 314 static int 315 tdata_label_find_cb(void *arg1, void *arg2) 316 { 317 labelent_t *le = arg1; 318 labelent_t *tmpl = arg2; 319 return (streq(le->le_name, tmpl->le_name)); 320 } 321 322 int 323 tdata_label_find(tdata_t *td, char *label) 324 { 325 labelent_t let; 326 labelent_t *ret; 327 328 if (streq(label, "BASE")) { 329 ret = (labelent_t *)list_first(td->td_labels); 330 return (ret ? ret->le_idx : -1); 331 } 332 333 let.le_name = label; 334 335 if (!(ret = (labelent_t *)list_find(td->td_labels, &let, 336 tdata_label_find_cb))) 337 return (-1); 338 339 return (ret->le_idx); 340 } 341 342 static int 343 tdata_label_newmax_cb(void *data, void *arg) 344 { 345 labelent_t *le = data; 346 int *newmaxp = arg; 347 348 if (le->le_idx > *newmaxp) { 349 le->le_idx = *newmaxp; 350 return (1); 351 } 352 353 return (0); 354 } 355 356 void 357 tdata_label_newmax(tdata_t *td, int newmax) 358 { 359 (void) list_iter(td->td_labels, tdata_label_newmax_cb, &newmax); 360 } 361 362 /*ARGSUSED1*/ 363 static void 364 tdata_label_free_cb(void *arg, void *private __unused) 365 { 366 labelent_t *le = arg; 367 if (le->le_name) 368 free(le->le_name); 369 free(le); 370 } 371 372 void 373 tdata_label_free(tdata_t *td) 374 { 375 list_free(td->td_labels, tdata_label_free_cb, NULL); 376 td->td_labels = NULL; 377 } 378 379 tdata_t * 380 tdata_new(void) 381 { 382 tdata_t *new = xcalloc(sizeof (tdata_t)); 383 384 new->td_layouthash = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, 385 tdesc_layoutcmp); 386 new->td_idhash = hash_new(TDATA_ID_HASH_SIZE, tdesc_idhash, 387 tdesc_idcmp); 388 /* 389 * This is also traversed as a list, but amortized O(1) 390 * lookup massively impacts part of the merge phase, so 391 * we store the iidescs as a hash. 392 */ 393 new->td_iihash = hash_new(IIDESC_HASH_SIZE, iidesc_hash, NULL); 394 new->td_nextid = 1; 395 new->td_curvgen = 1; 396 397 pthread_mutex_init(&new->td_mergelock, NULL); 398 399 return (new); 400 } 401 402 void 403 tdata_free(tdata_t *td) 404 { 405 hash_free(td->td_iihash, iidesc_free, NULL); 406 hash_free(td->td_layouthash, tdesc_free_cb, NULL); 407 hash_free(td->td_idhash, NULL, NULL); 408 list_free(td->td_fwdlist, NULL, NULL); 409 410 tdata_label_free(td); 411 412 free(td->td_parlabel); 413 free(td->td_parname); 414 415 pthread_mutex_destroy(&td->td_mergelock); 416 417 free(td); 418 } 419 420 /*ARGSUSED1*/ 421 static int 422 build_hashes(tdesc_t *ctdp, tdesc_t **ctdpp __unused, void *private) 423 { 424 tdata_t *td = private; 425 426 hash_add(td->td_idhash, ctdp); 427 hash_add(td->td_layouthash, ctdp); 428 429 return (1); 430 } 431 432 static tdtrav_cb_f build_hashes_cbs[] = { 433 NULL, 434 build_hashes, /* intrinsic */ 435 build_hashes, /* pointer */ 436 build_hashes, /* array */ 437 build_hashes, /* function */ 438 build_hashes, /* struct */ 439 build_hashes, /* union */ 440 build_hashes, /* enum */ 441 build_hashes, /* forward */ 442 build_hashes, /* typedef */ 443 tdtrav_assert, /* typedef_unres */ 444 build_hashes, /* volatile */ 445 build_hashes, /* const */ 446 build_hashes /* restrict */ 447 }; 448 449 static void 450 tdata_build_hashes_common(tdata_t *td, hash_t *hash) 451 { 452 (void) iitraverse_hash(hash, &td->td_curvgen, NULL, NULL, 453 build_hashes_cbs, td); 454 } 455 456 void 457 tdata_build_hashes(tdata_t *td) 458 { 459 tdata_build_hashes_common(td, td->td_iihash); 460 } 461 462 /* Merge td2 into td1. td2 is destroyed by the merge */ 463 void 464 tdata_merge(tdata_t *td1, tdata_t *td2) 465 { 466 td1->td_curemark = MAX(td1->td_curemark, td2->td_curemark); 467 td1->td_curvgen = MAX(td1->td_curvgen, td2->td_curvgen); 468 td1->td_nextid = MAX(td1->td_nextid, td2->td_nextid); 469 470 hash_merge(td1->td_iihash, td2->td_iihash); 471 472 /* Add td2's type tree to the hashes */ 473 tdata_build_hashes_common(td1, td2->td_iihash); 474 475 list_concat(&td1->td_fwdlist, td2->td_fwdlist); 476 td2->td_fwdlist = NULL; 477 478 slist_merge(&td1->td_labels, td2->td_labels, 479 tdata_label_cmp); 480 td2->td_labels = NULL; 481 482 /* free the td2 hashes (data is now part of td1) */ 483 484 hash_free(td2->td_layouthash, NULL, NULL); 485 td2->td_layouthash = NULL; 486 487 hash_free(td2->td_iihash, NULL, NULL); 488 td2->td_iihash = NULL; 489 490 tdata_free(td2); 491 } 492