libctf/ctf-lookup.c

   1 /* Symbol, variable and name lookup.
   2    Copyright (C) 2019-2021 Free Software Foundation, Inc.
   3
   4    This file is part of libctf.
   5
   6    libctf is free software; you can redistribute it and/or modify it under
   7    the terms of the GNU General Public License as published by the Free
   8    Software Foundation; either version 3, or (at your option) any later
   9    version.
  10
  11    This program is distributed in the hope that it will be useful, but
  12    WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14    See the GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; see the file COPYING.  If not see
  18    <http://www.gnu.org/licenses/>.  */
  19
  20 #include <ctf-impl.h>
  21 #include <elf.h>
  22 #include <string.h>
  23 #include <assert.h>
  24
  25 /* Grow the pptrtab so that it is at least NEW_LEN long.  */
  26 static int
  27 grow_pptrtab (ctf_dict_t *fp, size_t new_len)
  28 {
  29   uint32_t *new_pptrtab;
  30
  31   if ((new_pptrtab = realloc (fp->ctf_pptrtab, sizeof (uint32_t)
  32                               * new_len)) == NULL)
  33     return (ctf_set_errno (fp, ENOMEM));
  34
  35   fp->ctf_pptrtab = new_pptrtab;
  36
  37   memset (fp->ctf_pptrtab + fp->ctf_pptrtab_len, 0,
  38           sizeof (uint32_t) * (new_len - fp->ctf_pptrtab_len));
  39
  40   fp->ctf_pptrtab_len = new_len;
  41   return 0;
  42 }
  43
  44 /* Update entries in the pptrtab that relate to types newly added in the
  45    child.  */
  46 static int
  47 refresh_pptrtab (ctf_dict_t *fp, ctf_dict_t *pfp)
  48 {
  49   uint32_t i;
  50   for (i = fp->ctf_pptrtab_typemax; i <= fp->ctf_typemax; i++)
  51     {
  52       ctf_id_t type = LCTF_INDEX_TO_TYPE (fp, i, 1);
  53       ctf_id_t reffed_type;
  54
  55       if (ctf_type_kind (fp, type) != CTF_K_POINTER)
  56         continue;
  57
  58       reffed_type = ctf_type_reference (fp, type);
  59
  60       if (LCTF_TYPE_ISPARENT (fp, reffed_type))
  61         {
  62           uint32_t idx = LCTF_TYPE_TO_INDEX (fp, reffed_type);
  63
  64           /* Guard against references to invalid types.  No need to consider
  65              the CTF dict corrupt in this case: this pointer just can't be a
  66              pointer to any type we know about.  */
  67           if (idx <= pfp->ctf_typemax)
  68             {
  69               if (idx >= fp->ctf_pptrtab_len
  70                   && grow_pptrtab (fp, pfp->ctf_ptrtab_len) < 0)
  71                 return -1;                      /* errno is set for us.  */
  72
  73               fp->ctf_pptrtab[idx] = i;
  74             }
  75         }
  76     }
  77
  78   fp->ctf_pptrtab_typemax = fp->ctf_typemax;
  79
  80   return 0;
  81 }
  82
  83 /* Compare the given input string and length against a table of known C storage
  84    qualifier keywords.  We just ignore these in ctf_lookup_by_name, below.  To
  85    do this quickly, we use a pre-computed Perfect Hash Function similar to the
  86    technique originally described in the classic paper:
  87
  88    R.J. Cichelli, "Minimal Perfect Hash Functions Made Simple",
  89    Communications of the ACM, Volume 23, Issue 1, January 1980, pp. 17-19.
  90
  91    For an input string S of length N, we use hash H = S[N - 1] + N - 105, which
  92    for the current set of qualifiers yields a unique H in the range [0 .. 20].
  93    The hash can be modified when the keyword set changes as necessary.  We also
  94    store the length of each keyword and check it prior to the final strcmp().
  95
  96    TODO: just use gperf.  */
  97
  98 static int
  99 isqualifier (const char *s, size_t len)
 100 {
 101   static const struct qual
 102   {
 103     const char *q_name;
 104     size_t q_len;
 105   } qhash[] = {
 106     {"static", 6}, {"", 0}, {"", 0}, {"", 0},
 107     {"volatile", 8}, {"", 0}, {"", 0}, {"", 0}, {"", 0},
 108     {"", 0}, {"auto", 4}, {"extern", 6}, {"", 0}, {"", 0},
 109     {"", 0}, {"", 0}, {"const", 5}, {"register", 8},
 110     {"", 0}, {"restrict", 8}, {"_Restrict", 9}
 111   };
 112
 113   int h = s[len - 1] + (int) len - 105;
 114   const struct qual *qp = &qhash[h];
 115
 116   return (h >= 0 && (size_t) h < sizeof (qhash) / sizeof (qhash[0])
 117           && (size_t) len == qp->q_len &&
 118           strncmp (qp->q_name, s, qp->q_len) == 0);
 119 }
 120
 121 /* Attempt to convert the given C type name into the corresponding CTF type ID.
 122    It is not possible to do complete and proper conversion of type names
 123    without implementing a more full-fledged parser, which is necessary to
 124    handle things like types that are function pointers to functions that
 125    have arguments that are function pointers, and fun stuff like that.
 126    Instead, this function implements a very simple conversion algorithm that
 127    finds the things that we actually care about: structs, unions, enums,
 128    integers, floats, typedefs, and pointers to any of these named types.  */
 129
 130 static ctf_id_t
 131 ctf_lookup_by_name_internal (ctf_dict_t *fp, ctf_dict_t *child,
 132                              const char *name)
 133 {
 134   static const char delimiters[] = " \t\n\r\v\f*";
 135
 136   const ctf_lookup_t *lp;
 137   const char *p, *q, *end;
 138   ctf_id_t type = 0;
 139   ctf_id_t ntype, ptype;
 140
 141   if (name == NULL)
 142     return (ctf_set_errno (fp, EINVAL));
 143
 144   for (p = name, end = name + strlen (name); *p != '\0'; p = q)
 145     {
 146       while (isspace ((int) *p))
 147         p++;                    /* Skip leading whitespace.  */
 148
 149       if (p == end)
 150         break;
 151
 152       if ((q = strpbrk (p + 1, delimiters)) == NULL)
 153         q = end;                /* Compare until end.  */
 154
 155       if (*p == '*')
 156         {
 157           /* Find a pointer to type by looking in child->ctf_pptrtab (if child
 158              is set) and fp->ctf_ptrtab.  If we can't find a pointer to the
 159              given type, see if we can compute a pointer to the type resulting
 160              from resolving the type down to its base type and use that instead.
 161              This helps with cases where the CTF data includes "struct foo *"
 162              but not "foo_t *" and the user tries to access "foo_t *" in the
 163              debugger.
 164
 165              There is extra complexity here because uninitialized elements in
 166              the pptrtab and ptrtab are set to zero, but zero (as the type ID
 167              meaning the unimplemented type) is a valid return type from
 168              ctf_lookup_by_name.  (Pointers to types are never of type 0, so
 169              this is unambiguous, just fiddly to deal with.)  */
 170
 171           uint32_t idx = LCTF_TYPE_TO_INDEX (fp, type);
 172           int in_child = 0;
 173
 174           ntype = CTF_ERR;
 175           if (child && idx <= child->ctf_pptrtab_len)
 176             {
 177               ntype = child->ctf_pptrtab[idx];
 178               if (ntype)
 179                 in_child = 1;
 180               else
 181                 ntype = CTF_ERR;
 182             }
 183
 184           if (ntype == CTF_ERR)
 185             {
 186               ntype = fp->ctf_ptrtab[idx];
 187               if (ntype == 0)
 188                 ntype = CTF_ERR;
 189             }
 190
 191           /* Try resolving to its base type and check again.  */
 192           if (ntype == CTF_ERR)
 193             {
 194               if (child)
 195                 ntype = ctf_type_resolve_unsliced (child, type);
 196               else
 197                 ntype = ctf_type_resolve_unsliced (fp, type);
 198
 199               if (ntype == CTF_ERR)
 200                 goto notype;
 201
 202               idx = LCTF_TYPE_TO_INDEX (fp, ntype);
 203
 204               ntype = CTF_ERR;
 205               if (child && idx <= child->ctf_pptrtab_len)
 206                 {
 207                   ntype = child->ctf_pptrtab[idx];
 208                   if (ntype)
 209                     in_child = 1;
 210                   else
 211                     ntype = CTF_ERR;
 212                 }
 213
 214               if (ntype == CTF_ERR)
 215                 {
 216                   ntype = fp->ctf_ptrtab[idx];
 217                   if (ntype == 0)
 218                     ntype = CTF_ERR;
 219                 }
 220               if (ntype == CTF_ERR)
 221                 goto notype;
 222             }
 223
 224           type = LCTF_INDEX_TO_TYPE (fp, ntype, (fp->ctf_flags & LCTF_CHILD)
 225                                      || in_child);
 226
 227           /* We are looking up a type in the parent, but the pointed-to type is
 228              in the child.  Switch to looking in the child: if we need to go
 229              back into the parent, we can recurse again.  */
 230           if (in_child)
 231             {
 232               fp = child;
 233               child = NULL;
 234             }
 235
 236           q = p + 1;
 237           continue;
 238         }
 239
 240       if (isqualifier (p, (size_t) (q - p)))
 241         continue;               /* Skip qualifier keyword.  */
 242
 243       for (lp = fp->ctf_lookups; lp->ctl_prefix != NULL; lp++)
 244         {
 245           /* TODO: This is not MT-safe.  */
 246           if ((lp->ctl_prefix[0] == '\0' ||
 247                strncmp (p, lp->ctl_prefix, (size_t) (q - p)) == 0) &&
 248               (size_t) (q - p) >= lp->ctl_len)
 249             {
 250               for (p += lp->ctl_len; isspace ((int) *p); p++)
 251                 continue;       /* Skip prefix and next whitespace.  */
 252
 253               if ((q = strchr (p, '*')) == NULL)
 254                 q = end;        /* Compare until end.  */
 255
 256               while (isspace ((int) q[-1]))
 257                 q--;            /* Exclude trailing whitespace.  */
 258
 259               /* Expand and/or allocate storage for a slice of the name, then
 260                  copy it in.  */
 261
 262               if (fp->ctf_tmp_typeslicelen >= (size_t) (q - p) + 1)
 263                 {
 264                   memcpy (fp->ctf_tmp_typeslice, p, (size_t) (q - p));
 265                   fp->ctf_tmp_typeslice[(size_t) (q - p)] = '\0';
 266                 }
 267               else
 268                 {
 269                   free (fp->ctf_tmp_typeslice);
 270                   fp->ctf_tmp_typeslice = xstrndup (p, (size_t) (q - p));
 271                   if (fp->ctf_tmp_typeslice == NULL)
 272                     {
 273                       ctf_set_errno (fp, ENOMEM);
 274                       return CTF_ERR;
 275                     }
 276                 }
 277
 278               if ((type = ctf_lookup_by_rawhash (fp, lp->ctl_hash,
 279                                                  fp->ctf_tmp_typeslice)) == 0)
 280                 goto notype;
 281
 282               break;
 283             }
 284         }
 285
 286       if (lp->ctl_prefix == NULL)
 287         goto notype;
 288     }
 289
 290   if (*p != '\0' || type == 0)
 291     return (ctf_set_errno (fp, ECTF_SYNTAX));
 292
 293   return type;
 294
 295  notype:
 296   ctf_set_errno (fp, ECTF_NOTYPE);
 297   if (fp->ctf_parent != NULL)
 298     {
 299       /* Need to look up in the parent, from the child's perspective.
 300          Make sure the pptrtab is up to date.  */
 301
 302       if (fp->ctf_pptrtab_typemax < fp->ctf_typemax)
 303         {
 304           if (refresh_pptrtab (fp, fp->ctf_parent) < 0)
 305             return -1;                  /* errno is set for us.  */
 306         }
 307
 308       if ((ptype = ctf_lookup_by_name_internal (fp->ctf_parent, fp,
 309                                                 name)) != CTF_ERR)
 310         return ptype;
 311       return (ctf_set_errno (fp, ctf_errno (fp->ctf_parent)));
 312     }
 313
 314   return CTF_ERR;
 315 }
 316
 317 ctf_id_t
 318 ctf_lookup_by_name (ctf_dict_t *fp, const char *name)
 319 {
 320   return ctf_lookup_by_name_internal (fp, NULL, name);
 321 }
 322
 323 /* Return the pointer to the internal CTF type data corresponding to the
 324    given type ID.  If the ID is invalid, the function returns NULL.
 325    This function is not exported outside of the library.  */
 326
 327 const ctf_type_t *
 328 ctf_lookup_by_id (ctf_dict_t **fpp, ctf_id_t type)
 329 {
 330   ctf_dict_t *fp = *fpp;        /* Caller passes in starting CTF dict.  */
 331   ctf_id_t idx;
 332
 333   if ((fp = ctf_get_dict (fp, type)) == NULL)
 334     {
 335       (void) ctf_set_errno (*fpp, ECTF_NOPARENT);
 336       return NULL;
 337     }
 338
 339   /* If this dict is writable, check for a dynamic type.  */
 340
 341   if (fp->ctf_flags & LCTF_RDWR)
 342     {
 343       ctf_dtdef_t *dtd;
 344
 345       if ((dtd = ctf_dynamic_type (fp, type)) != NULL)
 346         {
 347           *fpp = fp;
 348           return &dtd->dtd_data;
 349         }
 350       (void) ctf_set_errno (*fpp, ECTF_BADID);
 351       return NULL;
 352     }
 353
 354   /* Check for a type in the static portion.  */
 355
 356   idx = LCTF_TYPE_TO_INDEX (fp, type);
 357   if (idx > 0 && (unsigned long) idx <= fp->ctf_typemax)
 358     {
 359       *fpp = fp;                /* Function returns ending CTF dict.  */
 360       return (LCTF_INDEX_TO_TYPEPTR (fp, idx));
 361     }
 362
 363   (void) ctf_set_errno (*fpp, ECTF_BADID);
 364   return NULL;
 365 }
 366
 367 typedef struct ctf_lookup_idx_key
 368 {
 369   ctf_dict_t *clik_fp;
 370   const char *clik_name;
 371   uint32_t *clik_names;
 372 } ctf_lookup_idx_key_t;
 373
 374 /* A bsearch function for variable names.  */
 375
 376 static int
 377 ctf_lookup_var (const void *key_, const void *lookup_)
 378 {
 379   const ctf_lookup_idx_key_t *key = key_;
 380   const ctf_varent_t *lookup = lookup_;
 381
 382   return (strcmp (key->clik_name, ctf_strptr (key->clik_fp, lookup->ctv_name)));
 383 }
 384
 385 /* Given a variable name, return the type of the variable with that name.  */
 386
 387 ctf_id_t
 388 ctf_lookup_variable (ctf_dict_t *fp, const char *name)
 389 {
 390   ctf_varent_t *ent;
 391   ctf_lookup_idx_key_t key = { fp, name, NULL };
 392
 393   /* This array is sorted, so we can bsearch for it.  */
 394
 395   ent = bsearch (&key, fp->ctf_vars, fp->ctf_nvars, sizeof (ctf_varent_t),
 396                  ctf_lookup_var);
 397
 398   if (ent == NULL)
 399     {
 400       if (fp->ctf_parent != NULL)
 401         return ctf_lookup_variable (fp->ctf_parent, name);
 402
 403       return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
 404     }
 405
 406   return ent->ctv_type;
 407 }
 408
 409 typedef struct ctf_symidx_sort_arg_cb
 410 {
 411   ctf_dict_t *fp;
 412   uint32_t *names;
 413 } ctf_symidx_sort_arg_cb_t;
 414
 415 static int
 416 sort_symidx_by_name (const void *one_, const void *two_, void *arg_)
 417 {
 418   const uint32_t *one = one_;
 419   const uint32_t *two = two_;
 420   ctf_symidx_sort_arg_cb_t *arg = arg_;
 421
 422   return (strcmp (ctf_strptr (arg->fp, arg->names[*one]),
 423                   ctf_strptr (arg->fp, arg->names[*two])));
 424 }
 425
 426 /* Sort a symbol index section by name.  Takes a 1:1 mapping of names to the
 427    corresponding symbol table.  Returns a lexicographically sorted array of idx
 428    indexes (and thus, of indexes into the corresponding func info / data object
 429    section).  */
 430
 431 static uint32_t *
 432 ctf_symidx_sort (ctf_dict_t *fp, uint32_t *idx, size_t *nidx,
 433                          size_t len)
 434 {
 435   uint32_t *sorted;
 436   size_t i;
 437
 438   if ((sorted = malloc (len)) == NULL)
 439     {
 440       ctf_set_errno (fp, ENOMEM);
 441       return NULL;
 442     }
 443
 444   *nidx = len / sizeof (uint32_t);
 445   for (i = 0; i < *nidx; i++)
 446     sorted[i] = i;
 447
 448   if (!(fp->ctf_header->cth_flags & CTF_F_IDXSORTED))
 449     {
 450       ctf_symidx_sort_arg_cb_t arg = { fp, idx };
 451       ctf_dprintf ("Index section unsorted: sorting.");
 452       ctf_qsort_r (sorted, *nidx, sizeof (uint32_t), sort_symidx_by_name, &arg);
 453       fp->ctf_header->cth_flags |= CTF_F_IDXSORTED;
 454     }
 455
 456   return sorted;
 457 }
 458
 459 /* Given a symbol index, return the name of that symbol from the table provided
 460    by ctf_link_shuffle_syms, or failing that from the secondary string table, or
 461    the null string.  */
 462 static const char *
 463 ctf_lookup_symbol_name (ctf_dict_t *fp, unsigned long symidx)
 464 {
 465   const ctf_sect_t *sp = &fp->ctf_symtab;
 466   ctf_link_sym_t sym;
 467   int err;
 468
 469   if (fp->ctf_dynsymidx)
 470     {
 471       err = EINVAL;
 472       if (symidx > fp->ctf_dynsymmax)
 473         goto try_parent;
 474
 475       ctf_link_sym_t *symp = fp->ctf_dynsymidx[symidx];
 476
 477       if (!symp)
 478         goto try_parent;
 479
 480       return symp->st_name;
 481     }
 482
 483   err = ECTF_NOSYMTAB;
 484   if (sp->cts_data == NULL)
 485     goto try_parent;
 486
 487   if (symidx >= fp->ctf_nsyms)
 488     goto try_parent;
 489
 490   switch (sp->cts_entsize)
 491     {
 492     case sizeof (Elf64_Sym):
 493       {
 494         const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
 495         ctf_elf64_to_link_sym (fp, &sym, symp, symidx);
 496       }
 497       break;
 498     case sizeof (Elf32_Sym):
 499       {
 500         const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
 501         ctf_elf32_to_link_sym (fp, &sym, symp, symidx);
 502       }
 503       break;
 504     default:
 505       ctf_set_errno (fp, ECTF_SYMTAB);
 506       return _CTF_NULLSTR;
 507     }
 508
 509   assert (!sym.st_nameidx_set);
 510
 511   return sym.st_name;
 512
 513  try_parent:
 514   if (fp->ctf_parent)
 515     {
 516       const char *ret;
 517       ret = ctf_lookup_symbol_name (fp->ctf_parent, symidx);
 518       if (ret == NULL)
 519         ctf_set_errno (fp, ctf_errno (fp->ctf_parent));
 520       return ret;
 521     }
 522   else
 523     {
 524       ctf_set_errno (fp, err);
 525       return _CTF_NULLSTR;
 526     }
 527 }
 528
 529 /* Given a symbol name, return the index of that symbol, or -1 on error or if
 530    not found.  */
 531 static unsigned long
 532 ctf_lookup_symbol_idx (ctf_dict_t *fp, const char *symname)
 533 {
 534   const ctf_sect_t *sp = &fp->ctf_symtab;
 535   ctf_link_sym_t sym;
 536   void *known_idx;
 537   int err;
 538   ctf_dict_t *cache = fp;
 539
 540   if (fp->ctf_dynsyms)
 541     {
 542       err = EINVAL;
 543
 544       ctf_link_sym_t *symp;
 545
 546       if ((symp = ctf_dynhash_lookup (fp->ctf_dynsyms, symname)) == NULL)
 547         goto try_parent;
 548
 549       return symp->st_symidx;
 550     }
 551
 552   err = ECTF_NOSYMTAB;
 553   if (sp->cts_data == NULL)
 554     goto try_parent;
 555
 556   /* First, try a hash lookup to see if we have already spotted this symbol
 557      during a past iteration: create the hash first if need be.  The lifespan
 558      of the strings is equal to the lifespan of the cts_data, so we don't
 559      need to strdup them.  If this dict was opened as part of an archive,
 560      and this archive has designed a crossdict_cache to cache results that
 561      are the same across all dicts in an archive, use it.  */
 562
 563   if (fp->ctf_archive && fp->ctf_archive->ctfi_crossdict_cache)
 564     cache = fp->ctf_archive->ctfi_crossdict_cache;
 565
 566   if (!cache->ctf_symhash)
 567     if ((cache->ctf_symhash = ctf_dynhash_create (ctf_hash_string,
 568                                                   ctf_hash_eq_string,
 569                                                   NULL, NULL)) == NULL)
 570       goto oom;
 571
 572   if (ctf_dynhash_lookup_kv (cache->ctf_symhash, symname, NULL, &known_idx))
 573     return (unsigned long) (uintptr_t) known_idx;
 574
 575   /* Hash lookup unsuccessful: linear search, populating the hashtab for later
 576      lookups as we go.  */
 577
 578   for (; cache->ctf_symhash_latest < sp->cts_size / sp->cts_entsize;
 579        cache->ctf_symhash_latest++)
 580     {
 581       switch (sp->cts_entsize)
 582         {
 583         case sizeof (Elf64_Sym):
 584           {
 585             Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data;
 586             ctf_elf64_to_link_sym (fp, &sym, &symp[cache->ctf_symhash_latest],
 587                                    cache->ctf_symhash_latest);
 588             if (!ctf_dynhash_lookup_kv (cache->ctf_symhash, sym.st_name,
 589                                         NULL, NULL))
 590               if (ctf_dynhash_cinsert (cache->ctf_symhash, sym.st_name,
 591                                        (const void *) (uintptr_t)
 592                                        cache->ctf_symhash_latest) < 0)
 593                 goto oom;
 594             if (strcmp (sym.st_name, symname) == 0)
 595               return cache->ctf_symhash_latest++;
 596           }
 597           break;
 598         case sizeof (Elf32_Sym):
 599           {
 600             Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data;
 601             ctf_elf32_to_link_sym (fp, &sym, &symp[cache->ctf_symhash_latest],
 602                                    cache->ctf_symhash_latest);
 603             if (!ctf_dynhash_lookup_kv (cache->ctf_symhash, sym.st_name,
 604                                         NULL, NULL))
 605               if (ctf_dynhash_cinsert (cache->ctf_symhash, sym.st_name,
 606                                        (const void *) (uintptr_t)
 607                                        cache->ctf_symhash_latest) < 0)
 608                 goto oom;
 609             if (strcmp (sym.st_name, symname) == 0)
 610               return cache->ctf_symhash_latest++;
 611           }
 612           break;
 613         default:
 614           ctf_set_errno (fp, ECTF_SYMTAB);
 615           return (unsigned long) -1;
 616         }
 617     }
 618
 619   /* Searched everything, still not found.  */
 620
 621   return (unsigned long) -1;
 622
 623  try_parent:
 624   if (fp->ctf_parent)
 625     return ctf_lookup_symbol_idx (fp->ctf_parent, symname);
 626   else
 627     {
 628       ctf_set_errno (fp, err);
 629       return (unsigned long) -1;
 630     }
 631 oom:
 632   ctf_set_errno (fp, ENOMEM);
 633   ctf_err_warn (fp, 0, ENOMEM, _("cannot allocate memory for symbol "
 634                                  "lookup hashtab"));
 635   return (unsigned long) -1;
 636
 637 }
 638
 639 /* Iterate over all symbols with types: if FUNC, function symbols, otherwise,
 640    data symbols.  The name argument is not optional.  The return order is
 641    arbitrary, though is likely to be in symbol index or name order.  You can
 642    change the value of 'functions' in the middle of iteration over non-dynamic
 643    dicts, but doing so on dynamic dicts will fail.  (This is probably not very
 644    useful, but there is no reason to prohibit it.)  */
 645
 646 ctf_id_t
 647 ctf_symbol_next (ctf_dict_t *fp, ctf_next_t **it, const char **name,
 648                  int functions)
 649 {
 650   ctf_id_t sym;
 651   ctf_next_t *i = *it;
 652   int err;
 653
 654   if (!i)
 655     {
 656       if ((i = ctf_next_create ()) == NULL)
 657         return ctf_set_errno (fp, ENOMEM);
 658
 659       i->cu.ctn_fp = fp;
 660       i->ctn_iter_fun = (void (*) (void)) ctf_symbol_next;
 661       i->ctn_n = 0;
 662       *it = i;
 663     }
 664
 665   if ((void (*) (void)) ctf_symbol_next != i->ctn_iter_fun)
 666     return (ctf_set_errno (fp, ECTF_NEXT_WRONGFUN));
 667
 668   if (fp != i->cu.ctn_fp)
 669     return (ctf_set_errno (fp, ECTF_NEXT_WRONGFP));
 670
 671   /* We intentionally use raw access, not ctf_lookup_by_symbol, to avoid
 672      incurring additional sorting cost for unsorted symtypetabs coming from the
 673      compiler, to allow ctf_symbol_next to work in the absence of a symtab, and
 674      finally because it's easier to work out what the name of each symbol is if
 675      we do that.  */
 676
 677   if (fp->ctf_flags & LCTF_RDWR)
 678     {
 679       ctf_dynhash_t *dynh = functions ? fp->ctf_funchash : fp->ctf_objthash;
 680       void *dyn_name = NULL, *dyn_value = NULL;
 681
 682       if (!dynh)
 683         {
 684           ctf_next_destroy (i);
 685           return (ctf_set_errno (fp, ECTF_NEXT_END));
 686         }
 687
 688       err = ctf_dynhash_next (dynh, &i->ctn_next, &dyn_name, &dyn_value);
 689       /* This covers errors and also end-of-iteration.  */
 690       if (err != 0)
 691         {
 692           ctf_next_destroy (i);
 693           *it = NULL;
 694           return ctf_set_errno (fp, err);
 695         }
 696
 697       *name = dyn_name;
 698       sym = (ctf_id_t) (uintptr_t) dyn_value;
 699     }
 700   else if ((!functions && fp->ctf_objtidx_names) ||
 701            (functions && fp->ctf_funcidx_names))
 702     {
 703       ctf_header_t *hp = fp->ctf_header;
 704       uint32_t *idx = functions ? fp->ctf_funcidx_names : fp->ctf_objtidx_names;
 705       uint32_t *tab;
 706       size_t len;
 707
 708       if (functions)
 709         {
 710           len = (hp->cth_varoff - hp->cth_funcidxoff) / sizeof (uint32_t);
 711           tab = (uint32_t *) (fp->ctf_buf + hp->cth_funcoff);
 712         }
 713       else
 714         {
 715           len = (hp->cth_funcidxoff - hp->cth_objtidxoff) / sizeof (uint32_t);
 716           tab = (uint32_t *) (fp->ctf_buf + hp->cth_objtoff);
 717         }
 718
 719       do
 720         {
 721           if (i->ctn_n >= len)
 722             goto end;
 723
 724           *name = ctf_strptr (fp, idx[i->ctn_n]);
 725           sym = tab[i->ctn_n++];
 726         }
 727       while (sym == -1u || sym == 0);
 728     }
 729   else
 730     {
 731       /* Skip over pads in ctf_xslate, padding for typeless symbols in the
 732          symtypetab itself, and symbols in the wrong table.  */
 733       for (; i->ctn_n < fp->ctf_nsyms; i->ctn_n++)
 734         {
 735           ctf_header_t *hp = fp->ctf_header;
 736
 737           if (fp->ctf_sxlate[i->ctn_n] == -1u)
 738             continue;
 739
 740           sym = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[i->ctn_n]);
 741
 742           if (sym == 0)
 743             continue;
 744
 745           if (functions)
 746             {
 747               if (fp->ctf_sxlate[i->ctn_n] >= hp->cth_funcoff
 748                   && fp->ctf_sxlate[i->ctn_n] < hp->cth_objtidxoff)
 749                 break;
 750             }
 751           else
 752             {
 753               if (fp->ctf_sxlate[i->ctn_n] >= hp->cth_objtoff
 754                   && fp->ctf_sxlate[i->ctn_n] < hp->cth_funcoff)
 755                 break;
 756             }
 757         }
 758
 759       if (i->ctn_n >= fp->ctf_nsyms)
 760         goto end;
 761
 762       *name = ctf_lookup_symbol_name (fp, i->ctn_n++);
 763     }
 764
 765   return sym;
 766
 767  end:
 768   ctf_next_destroy (i);
 769   *it = NULL;
 770   return (ctf_set_errno (fp, ECTF_NEXT_END));
 771 }
 772
 773 /* A bsearch function for function and object index names.  */
 774
 775 static int
 776 ctf_lookup_idx_name (const void *key_, const void *idx_)
 777 {
 778   const ctf_lookup_idx_key_t *key = key_;
 779   const uint32_t *idx = idx_;
 780
 781   return (strcmp (key->clik_name, ctf_strptr (key->clik_fp, key->clik_names[*idx])));
 782 }
 783
 784 /* Given a symbol name or (failing that) number, look up that symbol in the
 785    function or object index table (which must exist).  Return 0 if not found
 786    there (or pad).  */
 787
 788 static ctf_id_t
 789 ctf_try_lookup_indexed (ctf_dict_t *fp, unsigned long symidx,
 790                         const char *symname, int is_function)
 791 {
 792   struct ctf_header *hp = fp->ctf_header;
 793   uint32_t *symtypetab;
 794   uint32_t *names;
 795   uint32_t *sxlate;
 796   size_t nidx;
 797
 798   if (symname == NULL)
 799     symname = ctf_lookup_symbol_name (fp, symidx);
 800
 801   ctf_dprintf ("Looking up type of object with symtab idx %lx or name %s in "
 802                "indexed symtypetab\n", symidx, symname);
 803
 804   if (symname[0] == '\0')
 805     return -1;                                  /* errno is set for us.  */
 806
 807   if (is_function)
 808     {
 809       if (!fp->ctf_funcidx_sxlate)
 810         {
 811           if ((fp->ctf_funcidx_sxlate
 812                = ctf_symidx_sort (fp, (uint32_t *)
 813                                   (fp->ctf_buf + hp->cth_funcidxoff),
 814                                   &fp->ctf_nfuncidx,
 815                                   hp->cth_varoff - hp->cth_funcidxoff))
 816               == NULL)
 817             {
 818               ctf_err_warn (fp, 0, 0, _("cannot sort function symidx"));
 819               return -1;                                /* errno is set for us.  */
 820             }
 821         }
 822       symtypetab = (uint32_t *) (fp->ctf_buf + hp->cth_funcoff);
 823       sxlate = fp->ctf_funcidx_sxlate;
 824       names = fp->ctf_funcidx_names;
 825       nidx = fp->ctf_nfuncidx;
 826     }
 827   else
 828     {
 829       if (!fp->ctf_objtidx_sxlate)
 830         {
 831           if ((fp->ctf_objtidx_sxlate
 832                = ctf_symidx_sort (fp, (uint32_t *)
 833                                   (fp->ctf_buf + hp->cth_objtidxoff),
 834                                   &fp->ctf_nobjtidx,
 835                                   hp->cth_funcidxoff - hp->cth_objtidxoff))
 836               == NULL)
 837             {
 838               ctf_err_warn (fp, 0, 0, _("cannot sort object symidx"));
 839               return -1;                                /* errno is set for us. */
 840             }
 841         }
 842
 843       symtypetab = (uint32_t *) (fp->ctf_buf + hp->cth_objtoff);
 844       sxlate = fp->ctf_objtidx_sxlate;
 845       names = fp->ctf_objtidx_names;
 846       nidx = fp->ctf_nobjtidx;
 847     }
 848
 849   ctf_lookup_idx_key_t key = { fp, symname, names };
 850   uint32_t *idx;
 851
 852   idx = bsearch (&key, sxlate, nidx, sizeof (uint32_t), ctf_lookup_idx_name);
 853
 854   if (!idx)
 855     {
 856       ctf_dprintf ("%s not found in idx\n", symname);
 857       return 0;
 858     }
 859
 860   /* Should be impossible, but be paranoid.  */
 861   if ((idx - sxlate) > (ptrdiff_t) nidx)
 862     return (ctf_set_errno (fp, ECTF_CORRUPT));
 863
 864   ctf_dprintf ("Symbol %lx (%s) is of type %x\n", symidx, symname,
 865                symtypetab[*idx]);
 866   return symtypetab[*idx];
 867 }
 868
 869 /* Given a symbol name or (if NULL) symbol index, return the type of the
 870    function or data object described by the corresponding entry in the symbol
 871    table.  We can only return symbols in read-only dicts and in dicts for which
 872    ctf_link_shuffle_syms has been called to assign symbol indexes to symbol
 873    names.  */
 874
 875 static ctf_id_t
 876 ctf_lookup_by_sym_or_name (ctf_dict_t *fp, unsigned long symidx,
 877                            const char *symname)
 878 {
 879   const ctf_sect_t *sp = &fp->ctf_symtab;
 880   ctf_id_t type = 0;
 881   int err = 0;
 882
 883   /* Shuffled dynsymidx present?  Use that.  */
 884   if (fp->ctf_dynsymidx)
 885     {
 886       const ctf_link_sym_t *sym;
 887
 888       if (symname)
 889         ctf_dprintf ("Looking up type of object with symname %s in "
 890                      "writable dict symtypetab\n", symname);
 891       else
 892         ctf_dprintf ("Looking up type of object with symtab idx %lx in "
 893                      "writable dict symtypetab\n", symidx);
 894
 895       /* The dict must be dynamic.  */
 896       if (!ctf_assert (fp, fp->ctf_flags & LCTF_RDWR))
 897         return CTF_ERR;
 898
 899       /* No name? Need to look it up.  */
 900       if (!symname)
 901         {
 902           err = EINVAL;
 903           if (symidx > fp->ctf_dynsymmax)
 904             goto try_parent;
 905
 906           sym = fp->ctf_dynsymidx[symidx];
 907           err = ECTF_NOTYPEDAT;
 908           if (!sym || (sym->st_shndx != STT_OBJECT && sym->st_shndx != STT_FUNC))
 909             goto try_parent;
 910
 911           if (!ctf_assert (fp, !sym->st_nameidx_set))
 912             return CTF_ERR;
 913           symname = sym->st_name;
 914      }
 915
 916       if (fp->ctf_objthash == NULL
 917           || ((type = (ctf_id_t) (uintptr_t)
 918                ctf_dynhash_lookup (fp->ctf_objthash, symname)) == 0))
 919         {
 920           if (fp->ctf_funchash == NULL
 921               || ((type = (ctf_id_t) (uintptr_t)
 922                    ctf_dynhash_lookup (fp->ctf_funchash, symname)) == 0))
 923             goto try_parent;
 924         }
 925
 926       return type;
 927     }
 928
 929   /* Lookup by name in a dynamic dict: just do it directly.  */
 930   if (symname && fp->ctf_flags & LCTF_RDWR)
 931     {
 932       if (fp->ctf_objthash == NULL
 933           || ((type = (ctf_id_t) (uintptr_t)
 934                ctf_dynhash_lookup (fp->ctf_objthash, symname)) == 0))
 935         {
 936           if (fp->ctf_funchash == NULL
 937               || ((type = (ctf_id_t) (uintptr_t)
 938                    ctf_dynhash_lookup (fp->ctf_funchash, symname)) == 0))
 939             goto try_parent;
 940         }
 941       return type;
 942     }
 943
 944   err = ECTF_NOSYMTAB;
 945   if (sp->cts_data == NULL)
 946     goto try_parent;
 947
 948   /* This covers both out-of-range lookups and a dynamic dict which hasn't been
 949      shuffled yet.  */
 950   err = EINVAL;
 951   if (symname == NULL && symidx >= fp->ctf_nsyms)
 952     goto try_parent;
 953
 954   if (fp->ctf_objtidx_names)
 955     {
 956       if ((type = ctf_try_lookup_indexed (fp, symidx, symname, 0)) == CTF_ERR)
 957         return CTF_ERR;                         /* errno is set for us.  */
 958     }
 959   if (type == 0 && fp->ctf_funcidx_names)
 960     {
 961       if ((type = ctf_try_lookup_indexed (fp, symidx, symname, 1)) == CTF_ERR)
 962         return CTF_ERR;                         /* errno is set for us.  */
 963     }
 964   if (type != 0)
 965     return type;
 966
 967   err = ECTF_NOTYPEDAT;
 968   if (fp->ctf_objtidx_names && fp->ctf_funcidx_names)
 969     goto try_parent;
 970
 971   /* Table must be nonindexed.  */
 972
 973   ctf_dprintf ("Looking up object type %lx in 1:1 dict symtypetab\n", symidx);
 974
 975   if (symname != NULL)
 976     if ((symidx = ctf_lookup_symbol_idx (fp, symname)) == (unsigned long) -1)
 977       goto try_parent;
 978
 979   if (fp->ctf_sxlate[symidx] == -1u)
 980     goto try_parent;
 981
 982   type = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
 983
 984   if (type == 0)
 985     goto try_parent;
 986
 987   return type;
 988  try_parent:
 989   if (fp->ctf_parent)
 990     {
 991       ctf_id_t ret = ctf_lookup_by_sym_or_name (fp->ctf_parent, symidx,
 992                                                 symname);
 993       if (ret == CTF_ERR)
 994         ctf_set_errno (fp, ctf_errno (fp->ctf_parent));
 995       return ret;
 996     }
 997   else
 998     return (ctf_set_errno (fp, err));
 999 }
1000
1001 /* Given a symbol table index, return the type of the function or data object
1002    described by the corresponding entry in the symbol table.  */
1003 ctf_id_t
1004 ctf_lookup_by_symbol (ctf_dict_t *fp, unsigned long symidx)
1005 {
1006   return ctf_lookup_by_sym_or_name (fp, symidx, NULL);
1007 }
1008
1009 /* Given a symbol name, return the type of the function or data object described
1010    by the corresponding entry in the symbol table.  */
1011 ctf_id_t
1012 ctf_lookup_by_symbol_name (ctf_dict_t *fp, const char *symname)
1013 {
1014   return ctf_lookup_by_sym_or_name (fp, 0, symname);
1015 }
1016
1017 /* Given a symbol table index, return the info for the function described
1018    by the corresponding entry in the symbol table, which may be a function
1019    symbol or may be a data symbol that happens to be a function pointer.  */
1020
1021 int
1022 ctf_func_info (ctf_dict_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
1023 {
1024   ctf_id_t type;
1025
1026   if ((type = ctf_lookup_by_symbol (fp, symidx)) == CTF_ERR)
1027     return -1;                                  /* errno is set for us.  */
1028
1029   if (ctf_type_kind (fp, type) != CTF_K_FUNCTION)
1030     return (ctf_set_errno (fp, ECTF_NOTFUNC));
1031
1032   return ctf_func_type_info (fp, type, fip);
1033 }
1034
1035 /* Given a symbol table index, return the arguments for the function described
1036    by the corresponding entry in the symbol table.  */
1037
1038 int
1039 ctf_func_args (ctf_dict_t *fp, unsigned long symidx, uint32_t argc,
1040                ctf_id_t *argv)
1041 {
1042   ctf_id_t type;
1043
1044   if ((type = ctf_lookup_by_symbol (fp, symidx)) == CTF_ERR)
1045     return -1;                                  /* errno is set for us.  */
1046
1047   if (ctf_type_kind (fp, type) != CTF_K_FUNCTION)
1048     return (ctf_set_errno (fp, ECTF_NOTFUNC));
1049
1050   return ctf_func_type_args (fp, type, argc, argv);
1051 }