libctf/ctf-lookup.c

   1 /* Symbol, variable and name lookup.
   2    Copyright (C) 2019-2020 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
  24 /* Compare the given input string and length against a table of known C storage
  25    qualifier keywords.  We just ignore these in ctf_lookup_by_name, below.  To
  26    do this quickly, we use a pre-computed Perfect Hash Function similar to the
  27    technique originally described in the classic paper:
  28
  29    R.J. Cichelli, "Minimal Perfect Hash Functions Made Simple",
  30    Communications of the ACM, Volume 23, Issue 1, January 1980, pp. 17-19.
  31
  32    For an input string S of length N, we use hash H = S[N - 1] + N - 105, which
  33    for the current set of qualifiers yields a unique H in the range [0 .. 20].
  34    The hash can be modified when the keyword set changes as necessary.  We also
  35    store the length of each keyword and check it prior to the final strcmp().
  36
  37    TODO: just use gperf.  */
  38
  39 static int
  40 isqualifier (const char *s, size_t len)
  41 {
  42   static const struct qual
  43   {
  44     const char *q_name;
  45     size_t q_len;
  46   } qhash[] = {
  47     {"static", 6}, {"", 0}, {"", 0}, {"", 0},
  48     {"volatile", 8}, {"", 0}, {"", 0}, {"", 0}, {"", 0},
  49     {"", 0}, {"auto", 4}, {"extern", 6}, {"", 0}, {"", 0},
  50     {"", 0}, {"", 0}, {"const", 5}, {"register", 8},
  51     {"", 0}, {"restrict", 8}, {"_Restrict", 9}
  52   };
  53
  54   int h = s[len - 1] + (int) len - 105;
  55   const struct qual *qp = &qhash[h];
  56
  57   return (h >= 0 && (size_t) h < sizeof (qhash) / sizeof (qhash[0])
  58           && (size_t) len == qp->q_len &&
  59           strncmp (qp->q_name, s, qp->q_len) == 0);
  60 }
  61
  62 /* Attempt to convert the given C type name into the corresponding CTF type ID.
  63    It is not possible to do complete and proper conversion of type names
  64    without implementing a more full-fledged parser, which is necessary to
  65    handle things like types that are function pointers to functions that
  66    have arguments that are function pointers, and fun stuff like that.
  67    Instead, this function implements a very simple conversion algorithm that
  68    finds the things that we actually care about: structs, unions, enums,
  69    integers, floats, typedefs, and pointers to any of these named types.  */
  70
  71 ctf_id_t
  72 ctf_lookup_by_name (ctf_file_t *fp, const char *name)
  73 {
  74   static const char delimiters[] = " \t\n\r\v\f*";
  75
  76   const ctf_lookup_t *lp;
  77   const char *p, *q, *end;
  78   ctf_id_t type = 0;
  79   ctf_id_t ntype, ptype;
  80
  81   if (name == NULL)
  82     return (ctf_set_errno (fp, EINVAL));
  83
  84   for (p = name, end = name + strlen (name); *p != '\0'; p = q)
  85     {
  86       while (isspace ((int) *p))
  87         p++;                    /* Skip leading whitespace.  */
  88
  89       if (p == end)
  90         break;
  91
  92       if ((q = strpbrk (p + 1, delimiters)) == NULL)
  93         q = end;                /* Compare until end.  */
  94
  95       if (*p == '*')
  96         {
  97           /* Find a pointer to type by looking in fp->ctf_ptrtab.
  98              If we can't find a pointer to the given type, see if
  99              we can compute a pointer to the type resulting from
 100              resolving the type down to its base type and use
 101              that instead.  This helps with cases where the CTF
 102              data includes "struct foo *" but not "foo_t *" and
 103              the user tries to access "foo_t *" in the debugger.
 104
 105              TODO need to handle parent containers too.  */
 106
 107           ntype = fp->ctf_ptrtab[LCTF_TYPE_TO_INDEX (fp, type)];
 108           if (ntype == 0)
 109             {
 110               ntype = ctf_type_resolve_unsliced (fp, type);
 111               if (ntype == CTF_ERR
 112                   || (ntype =
 113                       fp->ctf_ptrtab[LCTF_TYPE_TO_INDEX (fp, ntype)]) == 0)
 114                 {
 115                   (void) ctf_set_errno (fp, ECTF_NOTYPE);
 116                   goto err;
 117                 }
 118             }
 119
 120           type = LCTF_INDEX_TO_TYPE (fp, ntype, (fp->ctf_flags & LCTF_CHILD));
 121
 122           q = p + 1;
 123           continue;
 124         }
 125
 126       if (isqualifier (p, (size_t) (q - p)))
 127         continue;               /* Skip qualifier keyword.  */
 128
 129       for (lp = fp->ctf_lookups; lp->ctl_prefix != NULL; lp++)
 130         {
 131           /* TODO: This is not MT-safe.  */
 132           if ((lp->ctl_prefix[0] == '\0' ||
 133                strncmp (p, lp->ctl_prefix, (size_t) (q - p)) == 0) &&
 134               (size_t) (q - p) >= lp->ctl_len)
 135             {
 136               for (p += lp->ctl_len; isspace ((int) *p); p++)
 137                 continue;       /* Skip prefix and next whitespace.  */
 138
 139               if ((q = strchr (p, '*')) == NULL)
 140                 q = end;        /* Compare until end.  */
 141
 142               while (isspace ((int) q[-1]))
 143                 q--;            /* Exclude trailing whitespace.  */
 144
 145               /* Expand and/or allocate storage for a slice of the name, then
 146                  copy it in.  */
 147
 148               if (fp->ctf_tmp_typeslicelen >= (size_t) (q - p) + 1)
 149                 {
 150                   memcpy (fp->ctf_tmp_typeslice, p, (size_t) (q - p));
 151                   fp->ctf_tmp_typeslice[(size_t) (q - p)] = '\0';
 152                 }
 153               else
 154                 {
 155                   free (fp->ctf_tmp_typeslice);
 156                   fp->ctf_tmp_typeslice = xstrndup (p, (size_t) (q - p));
 157                   if (fp->ctf_tmp_typeslice == NULL)
 158                     {
 159                       (void) ctf_set_errno (fp, ENOMEM);
 160                       return CTF_ERR;
 161                     }
 162                 }
 163
 164               if ((type = ctf_lookup_by_rawhash (fp, lp->ctl_hash,
 165                                                  fp->ctf_tmp_typeslice)) == 0)
 166                 {
 167                   (void) ctf_set_errno (fp, ECTF_NOTYPE);
 168                   goto err;
 169                 }
 170
 171               break;
 172             }
 173         }
 174
 175       if (lp->ctl_prefix == NULL)
 176         {
 177           (void) ctf_set_errno (fp, ECTF_NOTYPE);
 178           goto err;
 179         }
 180     }
 181
 182   if (*p != '\0' || type == 0)
 183     return (ctf_set_errno (fp, ECTF_SYNTAX));
 184
 185   return type;
 186
 187 err:
 188   if (fp->ctf_parent != NULL
 189       && (ptype = ctf_lookup_by_name (fp->ctf_parent, name)) != CTF_ERR)
 190     return ptype;
 191
 192   return CTF_ERR;
 193 }
 194
 195 typedef struct ctf_lookup_var_key
 196 {
 197   ctf_file_t *clvk_fp;
 198   const char *clvk_name;
 199 } ctf_lookup_var_key_t;
 200
 201 /* A bsearch function for variable names.  */
 202
 203 static int
 204 ctf_lookup_var (const void *key_, const void *memb_)
 205 {
 206   const ctf_lookup_var_key_t *key = key_;
 207   const ctf_varent_t *memb = memb_;
 208
 209   return (strcmp (key->clvk_name, ctf_strptr (key->clvk_fp, memb->ctv_name)));
 210 }
 211
 212 /* Given a variable name, return the type of the variable with that name.  */
 213
 214 ctf_id_t
 215 ctf_lookup_variable (ctf_file_t *fp, const char *name)
 216 {
 217   ctf_varent_t *ent;
 218   ctf_lookup_var_key_t key = { fp, name };
 219
 220   /* This array is sorted, so we can bsearch for it.  */
 221
 222   ent = bsearch (&key, fp->ctf_vars, fp->ctf_nvars, sizeof (ctf_varent_t),
 223                  ctf_lookup_var);
 224
 225   if (ent == NULL)
 226     {
 227       if (fp->ctf_parent != NULL)
 228         return ctf_lookup_variable (fp->ctf_parent, name);
 229
 230       return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
 231     }
 232
 233   return ent->ctv_type;
 234 }
 235
 236 /* Given a symbol table index, return the name of that symbol from the secondary
 237    string table, or the null string (never NULL).  */
 238 const char *
 239 ctf_lookup_symbol_name (ctf_file_t *fp, unsigned long symidx)
 240 {
 241   const ctf_sect_t *sp = &fp->ctf_symtab;
 242   Elf64_Sym sym, *gsp;
 243
 244   if (sp->cts_data == NULL)
 245     {
 246       ctf_set_errno (fp, ECTF_NOSYMTAB);
 247       return _CTF_NULLSTR;
 248     }
 249
 250   if (symidx >= fp->ctf_nsyms)
 251     {
 252       ctf_set_errno (fp, EINVAL);
 253       return _CTF_NULLSTR;
 254     }
 255
 256   if (sp->cts_entsize == sizeof (Elf32_Sym))
 257     {
 258       const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
 259       gsp = ctf_sym_to_elf64 (symp, &sym);
 260     }
 261   else
 262       gsp = (Elf64_Sym *) sp->cts_data + symidx;
 263
 264   if (gsp->st_name < fp->ctf_str[CTF_STRTAB_1].cts_len)
 265     return (const char *) fp->ctf_str[CTF_STRTAB_1].cts_strs + gsp->st_name;
 266
 267   return _CTF_NULLSTR;
 268 }
 269
 270 /* Given a symbol table index, return the type of the data object described
 271    by the corresponding entry in the symbol table.  */
 272
 273 ctf_id_t
 274 ctf_lookup_by_symbol (ctf_file_t *fp, unsigned long symidx)
 275 {
 276   const ctf_sect_t *sp = &fp->ctf_symtab;
 277   ctf_id_t type;
 278
 279   if (sp->cts_data == NULL)
 280     return (ctf_set_errno (fp, ECTF_NOSYMTAB));
 281
 282   if (symidx >= fp->ctf_nsyms)
 283     return (ctf_set_errno (fp, EINVAL));
 284
 285   if (sp->cts_entsize == sizeof (Elf32_Sym))
 286     {
 287       const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
 288       if (ELF32_ST_TYPE (symp->st_info) != STT_OBJECT)
 289         return (ctf_set_errno (fp, ECTF_NOTDATA));
 290     }
 291   else
 292     {
 293       const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
 294       if (ELF64_ST_TYPE (symp->st_info) != STT_OBJECT)
 295         return (ctf_set_errno (fp, ECTF_NOTDATA));
 296     }
 297
 298   if (fp->ctf_sxlate[symidx] == -1u)
 299     return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
 300
 301   type = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
 302   if (type == 0)
 303     return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
 304
 305   return type;
 306 }
 307
 308 /* Return the native dict of a given type: if called on a child and the
 309    type is in the parent, return the parent.  Needed if you plan to access
 310    the type directly, without using the API.  */
 311 ctf_file_t *
 312 ctf_get_dict (ctf_file_t *fp, ctf_id_t type)
 313 {
 314     if ((fp->ctf_flags & LCTF_CHILD) && LCTF_TYPE_ISPARENT (fp, type))
 315       return fp->ctf_parent;
 316
 317     return fp;
 318 }
 319
 320 /* Return the pointer to the internal CTF type data corresponding to the
 321    given type ID.  If the ID is invalid, the function returns NULL.
 322    This function is not exported outside of the library.  */
 323
 324 const ctf_type_t *
 325 ctf_lookup_by_id (ctf_file_t **fpp, ctf_id_t type)
 326 {
 327   ctf_file_t *fp = *fpp;        /* Caller passes in starting CTF dict.  */
 328   ctf_id_t idx;
 329
 330   if ((fp = ctf_get_dict (fp, type)) == NULL)
 331     {
 332       (void) ctf_set_errno (*fpp, ECTF_NOPARENT);
 333       return NULL;
 334     }
 335
 336   /* If this dict is writable, check for a dynamic type.  */
 337
 338   if (fp->ctf_flags & LCTF_RDWR)
 339     {
 340       ctf_dtdef_t *dtd;
 341
 342       if ((dtd = ctf_dynamic_type (fp, type)) != NULL)
 343         {
 344           *fpp = fp;
 345           return &dtd->dtd_data;
 346         }
 347       (void) ctf_set_errno (*fpp, ECTF_BADID);
 348       return NULL;
 349     }
 350
 351   /* Check for a type in the static portion.  */
 352
 353   idx = LCTF_TYPE_TO_INDEX (fp, type);
 354   if (idx > 0 && (unsigned long) idx <= fp->ctf_typemax)
 355     {
 356       *fpp = fp;                /* Function returns ending CTF container.  */
 357       return (LCTF_INDEX_TO_TYPEPTR (fp, idx));
 358     }
 359
 360   (void) ctf_set_errno (*fpp, ECTF_BADID);
 361   return NULL;
 362 }
 363
 364 /* Given a symbol table index, return the info for the function described
 365    by the corresponding entry in the symbol table.  */
 366
 367 int
 368 ctf_func_info (ctf_file_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
 369 {
 370   const ctf_sect_t *sp = &fp->ctf_symtab;
 371   const uint32_t *dp;
 372   uint32_t info, kind, n;
 373
 374   if (sp->cts_data == NULL)
 375     return (ctf_set_errno (fp, ECTF_NOSYMTAB));
 376
 377   if (symidx >= fp->ctf_nsyms)
 378     return (ctf_set_errno (fp, EINVAL));
 379
 380   if (sp->cts_entsize == sizeof (Elf32_Sym))
 381     {
 382       const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
 383       if (ELF32_ST_TYPE (symp->st_info) != STT_FUNC)
 384         return (ctf_set_errno (fp, ECTF_NOTFUNC));
 385     }
 386   else
 387     {
 388       const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
 389       if (ELF64_ST_TYPE (symp->st_info) != STT_FUNC)
 390         return (ctf_set_errno (fp, ECTF_NOTFUNC));
 391     }
 392
 393   if (fp->ctf_sxlate[symidx] == -1u)
 394     return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
 395
 396   dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
 397
 398   info = *dp++;
 399   kind = LCTF_INFO_KIND (fp, info);
 400   n = LCTF_INFO_VLEN (fp, info);
 401
 402   if (kind == CTF_K_UNKNOWN && n == 0)
 403     return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
 404
 405   if (kind != CTF_K_FUNCTION)
 406     return (ctf_set_errno (fp, ECTF_CORRUPT));
 407
 408   fip->ctc_return = *dp++;
 409   fip->ctc_argc = n;
 410   fip->ctc_flags = 0;
 411
 412   if (n != 0 && dp[n - 1] == 0)
 413     {
 414       fip->ctc_flags |= CTF_FUNC_VARARG;
 415       fip->ctc_argc--;
 416     }
 417
 418   return 0;
 419 }
 420
 421 /* Given a symbol table index, return the arguments for the function described
 422    by the corresponding entry in the symbol table.  */
 423
 424 int
 425 ctf_func_args (ctf_file_t * fp, unsigned long symidx, uint32_t argc,
 426                ctf_id_t * argv)
 427 {
 428   const uint32_t *dp;
 429   ctf_funcinfo_t f;
 430
 431   if (ctf_func_info (fp, symidx, &f) < 0)
 432     return -1;                  /* errno is set for us.  */
 433
 434   /* The argument data is two uint32_t's past the translation table
 435      offset: one for the function info, and one for the return type. */
 436
 437   dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]) + 2;
 438
 439   for (argc = MIN (argc, f.ctc_argc); argc != 0; argc--)
 440     *argv++ = *dp++;
 441
 442   return 0;
 443 }