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