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 (*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 (*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 (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 pointer to the internal CTF type data corresponding to the
 309    given type ID.  If the ID is invalid, the function returns NULL.
 310    This function is not exported outside of the library.  */
 311
 312 const ctf_type_t *
 313 ctf_lookup_by_id (ctf_file_t **fpp, ctf_id_t type)
 314 {
 315   ctf_file_t *fp = *fpp;        /* Caller passes in starting CTF container.  */
 316   ctf_id_t idx;
 317
 318   if ((fp->ctf_flags & LCTF_CHILD) && LCTF_TYPE_ISPARENT (fp, type)
 319       && (fp = fp->ctf_parent) == NULL)
 320     {
 321       (void) ctf_set_errno (*fpp, ECTF_NOPARENT);
 322       return NULL;
 323     }
 324
 325   /* If this container is writable, check for a dynamic type.  */
 326
 327   if (fp->ctf_flags & LCTF_RDWR)
 328     {
 329       ctf_dtdef_t *dtd;
 330
 331       if ((dtd = ctf_dynamic_type (fp, type)) != NULL)
 332         {
 333           *fpp = fp;
 334           return &dtd->dtd_data;
 335         }
 336       (void) ctf_set_errno (*fpp, ECTF_BADID);
 337       return NULL;
 338     }
 339
 340   /* Check for a type in the static portion.  */
 341
 342   idx = LCTF_TYPE_TO_INDEX (fp, type);
 343   if (idx > 0 && (unsigned long) idx <= fp->ctf_typemax)
 344     {
 345       *fpp = fp;                /* Function returns ending CTF container.  */
 346       return (LCTF_INDEX_TO_TYPEPTR (fp, idx));
 347     }
 348
 349   (void) ctf_set_errno (*fpp, ECTF_BADID);
 350   return NULL;
 351 }
 352
 353 /* Given a symbol table index, return the info for the function described
 354    by the corresponding entry in the symbol table.  */
 355
 356 int
 357 ctf_func_info (ctf_file_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
 358 {
 359   const ctf_sect_t *sp = &fp->ctf_symtab;
 360   const uint32_t *dp;
 361   uint32_t info, kind, n;
 362
 363   if (sp->cts_data == NULL)
 364     return (ctf_set_errno (fp, ECTF_NOSYMTAB));
 365
 366   if (symidx >= fp->ctf_nsyms)
 367     return (ctf_set_errno (fp, EINVAL));
 368
 369   if (sp->cts_entsize == sizeof (Elf32_Sym))
 370     {
 371       const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
 372       if (ELF32_ST_TYPE (symp->st_info) != STT_FUNC)
 373         return (ctf_set_errno (fp, ECTF_NOTFUNC));
 374     }
 375   else
 376     {
 377       const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
 378       if (ELF64_ST_TYPE (symp->st_info) != STT_FUNC)
 379         return (ctf_set_errno (fp, ECTF_NOTFUNC));
 380     }
 381
 382   if (fp->ctf_sxlate[symidx] == -1u)
 383     return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
 384
 385   dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
 386
 387   info = *dp++;
 388   kind = LCTF_INFO_KIND (fp, info);
 389   n = LCTF_INFO_VLEN (fp, info);
 390
 391   if (kind == CTF_K_UNKNOWN && n == 0)
 392     return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
 393
 394   if (kind != CTF_K_FUNCTION)
 395     return (ctf_set_errno (fp, ECTF_CORRUPT));
 396
 397   fip->ctc_return = *dp++;
 398   fip->ctc_argc = n;
 399   fip->ctc_flags = 0;
 400
 401   if (n != 0 && dp[n - 1] == 0)
 402     {
 403       fip->ctc_flags |= CTF_FUNC_VARARG;
 404       fip->ctc_argc--;
 405     }
 406
 407   return 0;
 408 }
 409
 410 /* Given a symbol table index, return the arguments for the function described
 411    by the corresponding entry in the symbol table.  */
 412
 413 int
 414 ctf_func_args (ctf_file_t * fp, unsigned long symidx, uint32_t argc,
 415                ctf_id_t * argv)
 416 {
 417   const uint32_t *dp;
 418   ctf_funcinfo_t f;
 419
 420   if (ctf_func_info (fp, symidx, &f) < 0)
 421     return -1;                  /* errno is set for us.  */
 422
 423   /* The argument data is two uint32_t's past the translation table
 424      offset: one for the function info, and one for the return type. */
 425
 426   dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]) + 2;
 427
 428   for (argc = MIN (argc, f.ctc_argc); argc != 0; argc--)
 429     *argv++ = *dp++;
 430
 431   return 0;
 432 }