cddl/contrib/opensolaris/tools/ctf/cvt/tdata.c

   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 }