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 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 #if defined(sun)
 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 }