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