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