1 /* Symbol, variable and name lookup.
2 Copyright (C) 2019-2020 Free Software Foundation, Inc.
4 This file is part of libctf.
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
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.
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/>. */
25 /* Compare the given input string and length against a table of known C storage
26 qualifier keywords. We just ignore these in ctf_lookup_by_name, below. To
27 do this quickly, we use a pre-computed Perfect Hash Function similar to the
28 technique originally described in the classic paper:
30 R.J. Cichelli, "Minimal Perfect Hash Functions Made Simple",
31 Communications of the ACM, Volume 23, Issue 1, January 1980, pp. 17-19.
33 For an input string S of length N, we use hash H = S[N - 1] + N - 105, which
34 for the current set of qualifiers yields a unique H in the range [0 .. 20].
35 The hash can be modified when the keyword set changes as necessary. We also
36 store the length of each keyword and check it prior to the final strcmp().
38 TODO: just use gperf. */
41 isqualifier (const char *s
, size_t len
)
43 static const struct qual
48 {"static", 6}, {"", 0}, {"", 0}, {"", 0},
49 {"volatile", 8}, {"", 0}, {"", 0}, {"", 0}, {"", 0},
50 {"", 0}, {"auto", 4}, {"extern", 6}, {"", 0}, {"", 0},
51 {"", 0}, {"", 0}, {"const", 5}, {"register", 8},
52 {"", 0}, {"restrict", 8}, {"_Restrict", 9}
55 int h
= s
[len
- 1] + (int) len
- 105;
56 const struct qual
*qp
= &qhash
[h
];
58 return (h
>= 0 && (size_t) h
< sizeof (qhash
) / sizeof (qhash
[0])
59 && (size_t) len
== qp
->q_len
&&
60 strncmp (qp
->q_name
, s
, qp
->q_len
) == 0);
63 /* Attempt to convert the given C type name into the corresponding CTF type ID.
64 It is not possible to do complete and proper conversion of type names
65 without implementing a more full-fledged parser, which is necessary to
66 handle things like types that are function pointers to functions that
67 have arguments that are function pointers, and fun stuff like that.
68 Instead, this function implements a very simple conversion algorithm that
69 finds the things that we actually care about: structs, unions, enums,
70 integers, floats, typedefs, and pointers to any of these named types. */
73 ctf_lookup_by_name (ctf_dict_t
*fp
, const char *name
)
75 static const char delimiters
[] = " \t\n\r\v\f*";
77 const ctf_lookup_t
*lp
;
78 const char *p
, *q
, *end
;
80 ctf_id_t ntype
, ptype
;
83 return (ctf_set_errno (fp
, EINVAL
));
85 for (p
= name
, end
= name
+ strlen (name
); *p
!= '\0'; p
= q
)
87 while (isspace ((int) *p
))
88 p
++; /* Skip leading whitespace. */
93 if ((q
= strpbrk (p
+ 1, delimiters
)) == NULL
)
94 q
= end
; /* Compare until end. */
98 /* Find a pointer to type by looking in fp->ctf_ptrtab.
99 If we can't find a pointer to the given type, see if
100 we can compute a pointer to the type resulting from
101 resolving the type down to its base type and use
102 that instead. This helps with cases where the CTF
103 data includes "struct foo *" but not "foo_t *" and
104 the user tries to access "foo_t *" in the debugger.
106 TODO need to handle parent dicts too. */
108 ntype
= fp
->ctf_ptrtab
[LCTF_TYPE_TO_INDEX (fp
, type
)];
111 ntype
= ctf_type_resolve_unsliced (fp
, type
);
114 fp
->ctf_ptrtab
[LCTF_TYPE_TO_INDEX (fp
, ntype
)]) == 0)
116 (void) ctf_set_errno (fp
, ECTF_NOTYPE
);
121 type
= LCTF_INDEX_TO_TYPE (fp
, ntype
, (fp
->ctf_flags
& LCTF_CHILD
));
127 if (isqualifier (p
, (size_t) (q
- p
)))
128 continue; /* Skip qualifier keyword. */
130 for (lp
= fp
->ctf_lookups
; lp
->ctl_prefix
!= NULL
; lp
++)
132 /* TODO: This is not MT-safe. */
133 if ((lp
->ctl_prefix
[0] == '\0' ||
134 strncmp (p
, lp
->ctl_prefix
, (size_t) (q
- p
)) == 0) &&
135 (size_t) (q
- p
) >= lp
->ctl_len
)
137 for (p
+= lp
->ctl_len
; isspace ((int) *p
); p
++)
138 continue; /* Skip prefix and next whitespace. */
140 if ((q
= strchr (p
, '*')) == NULL
)
141 q
= end
; /* Compare until end. */
143 while (isspace ((int) q
[-1]))
144 q
--; /* Exclude trailing whitespace. */
146 /* Expand and/or allocate storage for a slice of the name, then
149 if (fp
->ctf_tmp_typeslicelen
>= (size_t) (q
- p
) + 1)
151 memcpy (fp
->ctf_tmp_typeslice
, p
, (size_t) (q
- p
));
152 fp
->ctf_tmp_typeslice
[(size_t) (q
- p
)] = '\0';
156 free (fp
->ctf_tmp_typeslice
);
157 fp
->ctf_tmp_typeslice
= xstrndup (p
, (size_t) (q
- p
));
158 if (fp
->ctf_tmp_typeslice
== NULL
)
160 (void) ctf_set_errno (fp
, ENOMEM
);
165 if ((type
= ctf_lookup_by_rawhash (fp
, lp
->ctl_hash
,
166 fp
->ctf_tmp_typeslice
)) == 0)
168 (void) ctf_set_errno (fp
, ECTF_NOTYPE
);
176 if (lp
->ctl_prefix
== NULL
)
178 (void) ctf_set_errno (fp
, ECTF_NOTYPE
);
183 if (*p
!= '\0' || type
== 0)
184 return (ctf_set_errno (fp
, ECTF_SYNTAX
));
189 if (fp
->ctf_parent
!= NULL
190 && (ptype
= ctf_lookup_by_name (fp
->ctf_parent
, name
)) != CTF_ERR
)
196 /* Return the pointer to the internal CTF type data corresponding to the
197 given type ID. If the ID is invalid, the function returns NULL.
198 This function is not exported outside of the library. */
201 ctf_lookup_by_id (ctf_dict_t
**fpp
, ctf_id_t type
)
203 ctf_dict_t
*fp
= *fpp
; /* Caller passes in starting CTF dict. */
206 if ((fp
= ctf_get_dict (fp
, type
)) == NULL
)
208 (void) ctf_set_errno (*fpp
, ECTF_NOPARENT
);
212 /* If this dict is writable, check for a dynamic type. */
214 if (fp
->ctf_flags
& LCTF_RDWR
)
218 if ((dtd
= ctf_dynamic_type (fp
, type
)) != NULL
)
221 return &dtd
->dtd_data
;
223 (void) ctf_set_errno (*fpp
, ECTF_BADID
);
227 /* Check for a type in the static portion. */
229 idx
= LCTF_TYPE_TO_INDEX (fp
, type
);
230 if (idx
> 0 && (unsigned long) idx
<= fp
->ctf_typemax
)
232 *fpp
= fp
; /* Function returns ending CTF dict. */
233 return (LCTF_INDEX_TO_TYPEPTR (fp
, idx
));
236 (void) ctf_set_errno (*fpp
, ECTF_BADID
);
240 typedef struct ctf_lookup_idx_key
243 const char *clik_name
;
244 uint32_t *clik_names
;
245 } ctf_lookup_idx_key_t
;
247 /* A bsearch function for variable names. */
250 ctf_lookup_var (const void *key_
, const void *lookup_
)
252 const ctf_lookup_idx_key_t
*key
= key_
;
253 const ctf_varent_t
*lookup
= lookup_
;
255 return (strcmp (key
->clik_name
, ctf_strptr (key
->clik_fp
, lookup
->ctv_name
)));
258 /* Given a variable name, return the type of the variable with that name. */
261 ctf_lookup_variable (ctf_dict_t
*fp
, const char *name
)
264 ctf_lookup_idx_key_t key
= { fp
, name
, NULL
};
266 /* This array is sorted, so we can bsearch for it. */
268 ent
= bsearch (&key
, fp
->ctf_vars
, fp
->ctf_nvars
, sizeof (ctf_varent_t
),
273 if (fp
->ctf_parent
!= NULL
)
274 return ctf_lookup_variable (fp
->ctf_parent
, name
);
276 return (ctf_set_errno (fp
, ECTF_NOTYPEDAT
));
279 return ent
->ctv_type
;
282 typedef struct ctf_symidx_sort_arg_cb
286 } ctf_symidx_sort_arg_cb_t
;
289 sort_symidx_by_name (const void *one_
, const void *two_
, void *arg_
)
291 const uint32_t *one
= one_
;
292 const uint32_t *two
= two_
;
293 ctf_symidx_sort_arg_cb_t
*arg
= arg_
;
295 return (strcmp (ctf_strptr (arg
->fp
, arg
->names
[*one
]),
296 ctf_strptr (arg
->fp
, arg
->names
[*two
])));
299 /* Sort a symbol index section by name. Takes a 1:1 mapping of names to the
300 corresponding symbol table. Returns a lexicographically sorted array of idx
301 indexes (and thus, of indexes into the corresponding func info / data object
305 ctf_symidx_sort (ctf_dict_t
*fp
, uint32_t *idx
, size_t *nidx
,
311 if ((sorted
= malloc (len
)) == NULL
)
313 ctf_set_errno (fp
, ENOMEM
);
317 *nidx
= len
/ sizeof (uint32_t);
318 for (i
= 0; i
< *nidx
; i
++)
321 if (!(fp
->ctf_header
->cth_flags
& CTF_F_IDXSORTED
))
323 ctf_symidx_sort_arg_cb_t arg
= { fp
, idx
};
324 ctf_dprintf ("Index section unsorted: sorting.");
325 ctf_qsort_r (sorted
, *nidx
, sizeof (uint32_t), sort_symidx_by_name
, &arg
);
326 fp
->ctf_header
->cth_flags
|= CTF_F_IDXSORTED
;
332 /* Given a symbol index, return the name of that symbol from the table provided
333 by ctf_link_shuffle_syms, or failing that from the secondary string table, or
336 ctf_lookup_symbol_name (ctf_dict_t
*fp
, unsigned long symidx
)
338 const ctf_sect_t
*sp
= &fp
->ctf_symtab
;
342 if (fp
->ctf_dynsymidx
)
345 if (symidx
> fp
->ctf_dynsymmax
)
348 ctf_link_sym_t
*symp
= fp
->ctf_dynsymidx
[symidx
];
353 return symp
->st_name
;
357 if (sp
->cts_data
== NULL
)
360 if (symidx
>= fp
->ctf_nsyms
)
363 switch (sp
->cts_entsize
)
365 case sizeof (Elf64_Sym
):
367 const Elf64_Sym
*symp
= (Elf64_Sym
*) sp
->cts_data
+ symidx
;
368 ctf_elf64_to_link_sym (fp
, &sym
, symp
, symidx
);
371 case sizeof (Elf32_Sym
):
373 const Elf32_Sym
*symp
= (Elf32_Sym
*) sp
->cts_data
+ symidx
;
374 ctf_elf32_to_link_sym (fp
, &sym
, symp
, symidx
);
378 ctf_set_errno (fp
, ECTF_SYMTAB
);
382 assert (!sym
.st_nameidx_set
);
388 return ctf_lookup_symbol_name (fp
->ctf_parent
, symidx
);
391 ctf_set_errno (fp
, err
);
396 /* Iterate over all symbols with types: if FUNC, function symbols, otherwise,
397 data symbols. The name argument is not optional. The return order is
398 arbitrary, though is likely to be in symbol index or name order. You can
399 change the value of 'functions' in the middle of iteration over non-dynamic
400 dicts, but doing so on dynamic dicts will fail. (This is probably not very
401 useful, but there is no reason to prohibit it.) */
404 ctf_symbol_next (ctf_dict_t
*fp
, ctf_next_t
**it
, const char **name
,
413 if ((i
= ctf_next_create ()) == NULL
)
414 return ctf_set_errno (fp
, ENOMEM
);
417 i
->ctn_iter_fun
= (void (*) (void)) ctf_symbol_next
;
422 if ((void (*) (void)) ctf_symbol_next
!= i
->ctn_iter_fun
)
423 return (ctf_set_errno (fp
, ECTF_NEXT_WRONGFUN
));
425 if (fp
!= i
->cu
.ctn_fp
)
426 return (ctf_set_errno (fp
, ECTF_NEXT_WRONGFP
));
428 /* We intentionally use raw access, not ctf_lookup_by_symbol, to avoid
429 incurring additional sorting cost for unsorted symtypetabs coming from the
430 compiler, to allow ctf_symbol_next to work in the absence of a symtab, and
431 finally because it's easier to work out what the name of each symbol is if
434 if (fp
->ctf_flags
& LCTF_RDWR
)
436 ctf_dynhash_t
*dynh
= functions
? fp
->ctf_funchash
: fp
->ctf_objthash
;
437 void *dyn_name
= NULL
, *dyn_value
= NULL
;
441 ctf_next_destroy (i
);
442 return (ctf_set_errno (fp
, ECTF_NEXT_END
));
445 err
= ctf_dynhash_next (dynh
, &i
->u
.ctn_next
, &dyn_name
, &dyn_value
);
446 /* This covers errors and also end-of-iteration. */
449 ctf_next_destroy (i
);
451 return ctf_set_errno (fp
, err
);
455 sym
= (ctf_id_t
) (uintptr_t) dyn_value
;
457 else if ((!functions
&& fp
->ctf_objtidx_names
) ||
458 (functions
&& fp
->ctf_funcidx_names
))
460 ctf_header_t
*hp
= fp
->ctf_header
;
461 uint32_t *idx
= functions
? fp
->ctf_funcidx_names
: fp
->ctf_objtidx_names
;
467 len
= (hp
->cth_varoff
- hp
->cth_funcidxoff
) / sizeof (uint32_t);
468 tab
= (uint32_t *) (fp
->ctf_buf
+ hp
->cth_funcoff
);
472 len
= (hp
->cth_funcidxoff
- hp
->cth_objtidxoff
) / sizeof (uint32_t);
473 tab
= (uint32_t *) (fp
->ctf_buf
+ hp
->cth_objtoff
);
481 *name
= ctf_strptr (fp
, idx
[i
->ctn_n
]);
482 sym
= tab
[i
->ctn_n
++];
483 } while (sym
== -1u || sym
== 0);
487 /* Skip over pads in ctf_xslate, padding for typeless symbols in the
488 symtypetab itself, and symbols in the wrong table. */
489 for (; i
->ctn_n
< fp
->ctf_nsyms
; i
->ctn_n
++)
491 ctf_header_t
*hp
= fp
->ctf_header
;
493 if (fp
->ctf_sxlate
[i
->ctn_n
] == -1u)
496 sym
= *(uint32_t *) ((uintptr_t) fp
->ctf_buf
+ fp
->ctf_sxlate
[i
->ctn_n
]);
503 if (fp
->ctf_sxlate
[i
->ctn_n
] >= hp
->cth_funcoff
504 && fp
->ctf_sxlate
[i
->ctn_n
] < hp
->cth_objtidxoff
)
509 if (fp
->ctf_sxlate
[i
->ctn_n
] >= hp
->cth_objtoff
510 && fp
->ctf_sxlate
[i
->ctn_n
] < hp
->cth_funcoff
)
515 if (i
->ctn_n
>= fp
->ctf_nsyms
)
518 *name
= ctf_lookup_symbol_name (fp
, i
->ctn_n
++);
524 ctf_next_destroy (i
);
526 return (ctf_set_errno (fp
, ECTF_NEXT_END
));
529 /* A bsearch function for function and object index names. */
532 ctf_lookup_idx_name (const void *key_
, const void *idx_
)
534 const ctf_lookup_idx_key_t
*key
= key_
;
535 const uint32_t *idx
= idx_
;
537 return (strcmp (key
->clik_name
, ctf_strptr (key
->clik_fp
, key
->clik_names
[*idx
])));
540 /* Given a symbol number, look up that symbol in the function or object
541 index table (which must exist). Return 0 if not found there (or pad). */
544 ctf_try_lookup_indexed (ctf_dict_t
*fp
, unsigned long symidx
, int is_function
)
546 const char *symname
= ctf_lookup_symbol_name (fp
, symidx
);
547 struct ctf_header
*hp
= fp
->ctf_header
;
548 uint32_t *symtypetab
;
553 ctf_dprintf ("Looking up type of object with symtab idx %lx (%s) in "
554 "indexed symtypetab\n", symidx
, symname
);
556 if (symname
[0] == '\0')
557 return -1; /* errno is set for us. */
561 if (!fp
->ctf_funcidx_sxlate
)
563 if ((fp
->ctf_funcidx_sxlate
564 = ctf_symidx_sort (fp
, (uint32_t *)
565 (fp
->ctf_buf
+ hp
->cth_funcidxoff
),
567 hp
->cth_varoff
- hp
->cth_funcidxoff
))
570 ctf_err_warn (fp
, 0, 0, _("cannot sort function symidx"));
571 return -1; /* errno is set for us. */
574 symtypetab
= (uint32_t *) (fp
->ctf_buf
+ hp
->cth_funcoff
);
575 sxlate
= fp
->ctf_funcidx_sxlate
;
576 names
= fp
->ctf_funcidx_names
;
577 nidx
= fp
->ctf_nfuncidx
;
581 if (!fp
->ctf_objtidx_sxlate
)
583 if ((fp
->ctf_objtidx_sxlate
584 = ctf_symidx_sort (fp
, (uint32_t *)
585 (fp
->ctf_buf
+ hp
->cth_objtidxoff
),
587 hp
->cth_funcidxoff
- hp
->cth_objtidxoff
))
590 ctf_err_warn (fp
, 0, 0, _("cannot sort object symidx"));
591 return -1; /* errno is set for us. */
595 symtypetab
= (uint32_t *) (fp
->ctf_buf
+ hp
->cth_objtoff
);
596 sxlate
= fp
->ctf_objtidx_sxlate
;
597 names
= fp
->ctf_objtidx_names
;
598 nidx
= fp
->ctf_nobjtidx
;
601 ctf_lookup_idx_key_t key
= { fp
, symname
, names
};
604 idx
= bsearch (&key
, sxlate
, nidx
, sizeof (uint32_t), ctf_lookup_idx_name
);
608 ctf_dprintf ("%s not found in idx\n", symname
);
612 /* Should be impossible, but be paranoid. */
613 if ((idx
- sxlate
) > (ptrdiff_t) nidx
)
614 return (ctf_set_errno (fp
, ECTF_CORRUPT
));
616 ctf_dprintf ("Symbol %lx (%s) is of type %x\n", symidx
, symname
,
618 return symtypetab
[*idx
];
621 /* Given a symbol table index, return the type of the function or data object
622 described by the corresponding entry in the symbol table. We can only return
623 symbols in read-only dicts and in dicts for which ctf_link_shuffle_syms has
624 been called to assign symbol indexes to symbol names. */
627 ctf_lookup_by_symbol (ctf_dict_t
*fp
, unsigned long symidx
)
629 const ctf_sect_t
*sp
= &fp
->ctf_symtab
;
633 /* Shuffled dynsymidx present? Use that. */
634 if (fp
->ctf_dynsymidx
)
636 const ctf_link_sym_t
*sym
;
638 ctf_dprintf ("Looking up type of object with symtab idx %lx in "
639 "writable dict symtypetab\n", symidx
);
641 /* The dict must be dynamic. */
642 if (!ctf_assert (fp
, fp
->ctf_flags
& LCTF_RDWR
))
646 if (symidx
> fp
->ctf_dynsymmax
)
649 sym
= fp
->ctf_dynsymidx
[symidx
];
650 err
= ECTF_NOTYPEDAT
;
651 if (!sym
|| (sym
->st_shndx
!= STT_OBJECT
&& sym
->st_shndx
!= STT_FUNC
))
654 if (!ctf_assert (fp
, !sym
->st_nameidx_set
))
657 if (fp
->ctf_objthash
== NULL
658 || ((type
= (ctf_id_t
) (uintptr_t)
659 ctf_dynhash_lookup (fp
->ctf_objthash
, sym
->st_name
)) == 0))
661 if (fp
->ctf_funchash
== NULL
662 || ((type
= (ctf_id_t
) (uintptr_t)
663 ctf_dynhash_lookup (fp
->ctf_funchash
, sym
->st_name
)) == 0))
671 if (sp
->cts_data
== NULL
)
674 /* This covers both out-of-range lookups and a dynamic dict which hasn't been
677 if (symidx
>= fp
->ctf_nsyms
)
680 if (fp
->ctf_objtidx_names
)
682 if ((type
= ctf_try_lookup_indexed (fp
, symidx
, 0)) == CTF_ERR
)
683 return CTF_ERR
; /* errno is set for us. */
685 if (type
== 0 && fp
->ctf_funcidx_names
)
687 if ((type
= ctf_try_lookup_indexed (fp
, symidx
, 1)) == CTF_ERR
)
688 return CTF_ERR
; /* errno is set for us. */
693 err
= ECTF_NOTYPEDAT
;
694 if (fp
->ctf_objtidx_names
&& fp
->ctf_funcidx_names
)
697 /* Table must be nonindexed. */
699 ctf_dprintf ("Looking up object type %lx in 1:1 dict symtypetab\n", symidx
);
701 if (fp
->ctf_sxlate
[symidx
] == -1u)
704 type
= *(uint32_t *) ((uintptr_t) fp
->ctf_buf
+ fp
->ctf_sxlate
[symidx
]);
712 return ctf_lookup_by_symbol (fp
->ctf_parent
, symidx
);
714 return (ctf_set_errno (fp
, err
));
717 /* Given a symbol table index, return the info for the function described
718 by the corresponding entry in the symbol table, which may be a function
719 symbol or may be a data symbol that happens to be a function pointer. */
722 ctf_func_info (ctf_dict_t
*fp
, unsigned long symidx
, ctf_funcinfo_t
*fip
)
726 if ((type
= ctf_lookup_by_symbol (fp
, symidx
)) == CTF_ERR
)
727 return -1; /* errno is set for us. */
729 if (ctf_type_kind (fp
, type
) != CTF_K_FUNCTION
)
730 return (ctf_set_errno (fp
, ECTF_NOTFUNC
));
732 return ctf_func_type_info (fp
, type
, fip
);
735 /* Given a symbol table index, return the arguments for the function described
736 by the corresponding entry in the symbol table. */
739 ctf_func_args (ctf_dict_t
*fp
, unsigned long symidx
, uint32_t argc
,
744 if ((type
= ctf_lookup_by_symbol (fp
, symidx
)) == CTF_ERR
)
745 return -1; /* errno is set for us. */
747 if (ctf_type_kind (fp
, type
) != CTF_K_FUNCTION
)
748 return (ctf_set_errno (fp
, ECTF_NOTFUNC
));
750 return ctf_func_type_args (fp
, type
, argc
, argv
);