| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
The newer update-copyright.py fixes file encoding too, removing cr/lf
on binutils/bfdtest2.c and ld/testsuite/ld-cygwin/exe-export.exp, and
embedded cr in binutils/testsuite/binutils-all/ar.exp string match.
|
|
The result of running etc/update-copyright.py --this-year, fixing all
the files whose mode is changed by the script, plus a build with
--enable-maintainer-mode --enable-cgen-maint=yes, then checking
out */po/*.pot which we don't update frequently.
The copy of cgen was with commit d1dd5fcc38ead reverted as that commit
breaks building of bfp opcodes files.
|
|
* ctf-impl.h (ctf_dynset_eq_string): Don't declare.
* ctf-hash.c (ctf_dynset_eq_string): Delete function.
* ctf-dedup.c (make_set_element): Use htab_eq_string.
(ctf_dedup_atoms_init, ADD_CITER, ctf_dedup_init): Likewise.
(ctf_dedup_conflictify_unshared): Likewise.
(ctf_dedup_walk_output_mapping): Likewise.
|
|
The preceding change revealed a new bug: the string table is sorted for
better compression, so repeated serialization with type (or member)
additions in the middle can move strings around. But every
serialization flushes the set of refs (the memory locations that are
automatically updated with a final string offset when the strtab is
updated), so if we are not to have string offsets go stale, we must do
all ref additions within the serialization code (which walks the
complete set of types and symbols anyway). Unfortunately, we were adding
one ref in another place: the type name in the dynamic type definitions,
which has a ref added to it by ctf_add_generic.
So adding a type, serializing (via, say, one of the ctf_write
functions), adding another type with a name that sorts earlier, and
serializing again will corrupt the name of the first type because it no
longer had a ref pointing to its dtd entry's name when its string offset
was shifted later in the strtab to mae way for the other type.
To ensure that we don't miss strings, we also maintain a set of *pending
refs* that will be added later (during serialization), and remove
entries from that set when the ref is finally added. We always use
ctf_str_add_pending outside ctf-serialize.c, ensure that ctf_serialize
adds all strtab offsets as refs (even those in the dtds) on every
serialization, and mandate that no refs are live on entry to
ctf_serialize and that all pending refs are gone before strtab
finalization. (Of necessity ctf_serialize has to traverse all strtab
offsets in the dtds in order to serialize them, so adding them as refs
at the same time is easy.)
(Note that we still can't erase unused atoms when we roll back, though
we can erase unused refs: members and enums are still not removed by
rollbacks and might reference strings added after the snapshot.)
libctf/ChangeLog
2021-03-18 Nick Alcock <nick.alcock@oracle.com>
* ctf-hash.c (ctf_dynset_elements): New.
* ctf-impl.h (ctf_dynset_elements): Declare it.
(ctf_str_add_pending): Likewise.
(ctf_dict_t) <ctf_str_pending_ref>: New, set of refs that must be
added during serialization.
* ctf-string.c (ctf_str_create_atoms): Initialize it.
(CTF_STR_ADD_REF): New flag.
(CTF_STR_MAKE_PROVISIONAL): Likewise.
(CTF_STR_PENDING_REF): Likewise.
(ctf_str_add_ref_internal): Take a flags word rather than int
params. Populate, and clear out, ctf_str_pending_ref.
(ctf_str_add): Adjust accordingly.
(ctf_str_add_external): Likewise.
(ctf_str_add_pending): New.
(ctf_str_remove_ref): Also remove the potential ref if it is a
pending ref.
* ctf-serialize.c (ctf_serialize): Prohibit addition of strings
with ctf_str_add_ref before serialization. Ensure that the
ctf_str_pending_ref set is empty before strtab finalization.
(ctf_emit_type_sect): Add a ref to the ctt_name.
* ctf-create.c (ctf_add_generic): Add the ctt_name as a pending
ref.
* testsuite/libctf-writable/reserialize-strtab-corruption.*: New test.
|
|
|
|
This adds facilities to write out the function info and data object
sections, which efficiently map from entries in the symbol table to
types. The write-side code is entirely new: the read-side code was
merely significantly changed and support for indexed tables added
(pointed to by the no-longer-unused cth_objtidxoff and cth_funcidxoff
header fields).
With this in place, you can use ctf_lookup_by_symbol to look up the
types of symbols of function and object type (and, as before, you can
use ctf_lookup_variable to look up types of file-scope variables not
present in the symbol table, as long as you know their name: but
variables that are also data objects are now found in the data object
section instead.)
(Compatible) file format change:
The CTF spec has always said that the function info section looks much
like the CTF_K_FUNCTIONs in the type section: an info word (including an
argument count) followed by a return type and N argument types. This
format is suboptimal: it means function symbols cannot be deduplicated
and it causes a lot of ugly code duplication in libctf. But
conveniently the compiler has never emitted this! Because it has always
emitted a rather different format that libctf has never accepted, we can
be sure that there are no instances of this function info section in the
wild, and can freely change its format without compatibility concerns or
a file format version bump. (And since it has never been emitted in any
code that generated any older file format version, either, we need keep
no code to read the format as specified at all!)
So the function info section is now specified as an array of uint32_t,
exactly like the object data section: each entry is a type ID in the
type section which must be of kind CTF_K_FUNCTION, the prototype of
this function.
This allows function types to be deduplicated and also correctly encodes
the fact that all functions declared in C really are types available to
the program: so they should be stored in the type section like all other
types. (In format v4, we will be able to represent the types of static
functions as well, but that really does require a file format change.)
We introduce a new header flag, CTF_F_NEWFUNCINFO, which is set if the
new function info format is in use. A sufficiently new compiler will
always set this flag. New libctf will always set this flag: old libctf
will refuse to open any CTF dicts that have this flag set. If the flag
is not set on a dict being read in, new libctf will disregard the
function info section. Format v4 will remove this flag (or, rather, the
flag has no meaning there and the bit position may be recycled for some
other purpose).
New API:
Symbol addition:
ctf_add_func_sym: Add a symbol with a given name and type. The
type must be of kind CTF_K_FUNCTION (a function
pointer). Internally this adds a name -> type
mapping to the ctf_funchash in the ctf_dict.
ctf_add_objt_sym: Add a symbol with a given name and type. The type
kind can be anything, including function pointers.
This adds to ctf_objthash.
These both treat symbols as name -> type mappings: the linker associates
symbol names with symbol indexes via the ctf_link_shuffle_syms callback,
which sets up the ctf_dynsyms/ctf_dynsymidx/ctf_dynsymmax fields in the
ctf_dict. Repeated relinks can add more symbols.
Variables that are also exposed as symbols are removed from the variable
section at serialization time.
CTF symbol type sections which have enough pads, defined by
CTF_INDEX_PAD_THRESHOLD (whether because they are in dicts with symbols
where most types are unknown, or in archive where most types are defined
in some child or parent dict, not in this specific dict) are sorted by
name rather than symidx and accompanied by an index which associates
each symbol type entry with a name: the existing ctf_lookup_by_symbol
will map symbol indexes to symbol names and look the names up in the
index automatically. (This is currently ELF-symbol-table-dependent, but
there is almost nothing specific to ELF in here and we can add support
for other symbol table formats easily).
The compiler also uses index sections to communicate the contents of
object file symbol tables without relying on any specific ordering of
symbols: it doesn't need to sort them, and libctf will detect an
unsorted index section via the absence of the new CTF_F_IDXSORTED header
flag, and sort it if needed.
Iteration:
ctf_symbol_next: Iterator which returns the types and names of symbols
one by one, either for function or data symbols.
This does not require any sorting: the ctf_link machinery uses it to
pull in all the compiler-provided symbols cheaply, but it is not
restricted to that use.
(Compatible) changes in API:
ctf_lookup_by_symbol: can now be called for object and function
symbols: never returns ECTF_NOTDATA (which is
now not thrown by anything, but is kept for
compatibility and because it is a plausible
error that we might start throwing again at some
later date).
Internally we also have changes to the ctf-string functionality so that
"external" strings (those where we track a string -> offset mapping, but
only write out an offset) can be consulted via the usual means
(ctf_strptr) before the strtab is written out. This is important
because ctf_link_add_linker_symbol can now be handed symbols named via
strtab offsets, and ctf_link_shuffle_syms must figure out their actual
names by looking in the external symtab we have just been fed by the
ctf_link_add_strtab callback, long before that strtab is written out.
include/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ctf-api.h (ctf_symbol_next): New.
(ctf_add_objt_sym): Likewise.
(ctf_add_func_sym): Likewise.
* ctf.h: Document new function info section format.
(CTF_F_NEWFUNCINFO): New.
(CTF_F_IDXSORTED): New.
(CTF_F_MAX): Adjust accordingly.
libctf/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ctf-impl.h (CTF_INDEX_PAD_THRESHOLD): New.
(_libctf_nonnull_): Likewise.
(ctf_in_flight_dynsym_t): New.
(ctf_dict_t) <ctf_funcidx_names>: Likewise.
<ctf_objtidx_names>: Likewise.
<ctf_nfuncidx>: Likewise.
<ctf_nobjtidx>: Likewise.
<ctf_funcidx_sxlate>: Likewise.
<ctf_objtidx_sxlate>: Likewise.
<ctf_objthash>: Likewise.
<ctf_funchash>: Likewise.
<ctf_dynsyms>: Likewise.
<ctf_dynsymidx>: Likewise.
<ctf_dynsymmax>: Likewise.
<ctf_in_flight_dynsym>: Likewise.
(struct ctf_next) <u.ctn_next>: Likewise.
(ctf_symtab_skippable): New prototype.
(ctf_add_funcobjt_sym): Likewise.
(ctf_dynhash_sort_by_name): Likewise.
(ctf_sym_to_elf64): Rename to...
(ctf_elf32_to_link_sym): ... this, and...
(ctf_elf64_to_link_sym): ... this.
* ctf-open.c (init_symtab): Check for lack of CTF_F_NEWFUNCINFO
flag, and presence of index sections. Refactor out
ctf_symtab_skippable and ctf_elf*_to_link_sym, and use them. Use
ctf_link_sym_t, not Elf64_Sym. Skip initializing objt or func
sxlate sections if corresponding index section is present. Adjust
for new func info section format.
(ctf_bufopen_internal): Add ctf_err_warn to corrupt-file error
handling. Report incorrect-length index sections. Always do an
init_symtab, even if there is no symtab section (there may be index
sections still).
(flip_objts): Adjust comment: func and objt sections are actually
identical in structure now, no need to caveat.
(ctf_dict_close): Free newly-added data structures.
* ctf-create.c (ctf_create): Initialize them.
(ctf_symtab_skippable): New, refactored out of
init_symtab, with st_nameidx_set check added.
(ctf_add_funcobjt_sym): New, add a function or object symbol to the
ctf_objthash or ctf_funchash, by name.
(ctf_add_objt_sym): Call it.
(ctf_add_func_sym): Likewise.
(symtypetab_delete_nonstatic_vars): New, delete vars also present as
data objects.
(CTF_SYMTYPETAB_EMIT_FUNCTION): New flag to symtypetab emitters:
this is a function emission, not a data object emission.
(CTF_SYMTYPETAB_EMIT_PAD): New flag to symtypetab emitters: emit
pads for symbols with no type (only set for unindexed sections).
(CTF_SYMTYPETAB_FORCE_INDEXED): New flag to symtypetab emitters:
always emit indexed.
(symtypetab_density): New, figure out section sizes.
(emit_symtypetab): New, emit a symtypetab.
(emit_symtypetab_index): New, emit a symtypetab index.
(ctf_serialize): Call them, emitting suitably sorted symtypetab
sections and indexes. Set suitable header flags. Copy over new
fields.
* ctf-hash.c (ctf_dynhash_sort_by_name): New, used to impose an
order on symtypetab index sections.
* ctf-link.c (ctf_add_type_mapping): Delete erroneous comment
relating to code that was never committed.
(ctf_link_one_variable): Improve variable name.
(check_sym): New, symtypetab analogue of check_variable.
(ctf_link_deduplicating_one_symtypetab): New.
(ctf_link_deduplicating_syms): Likewise.
(ctf_link_deduplicating): Call them.
(ctf_link_deduplicating_per_cu): Note that we don't call them in
this case (yet).
(ctf_link_add_strtab): Set the error on the fp correctly.
(ctf_link_add_linker_symbol): New (no longer a do-nothing stub), add
a linker symbol to the in-flight list.
(ctf_link_shuffle_syms): New (no longer a do-nothing stub), turn the
in-flight list into a mapping we can use, now its names are
resolvable in the external strtab.
* ctf-string.c (ctf_str_rollback_atom): Don't roll back atoms with
external strtab offsets.
(ctf_str_rollback): Adjust comment.
(ctf_str_write_strtab): Migrate ctf_syn_ext_strtab population from
writeout time...
(ctf_str_add_external): ... to string addition time.
* ctf-lookup.c (ctf_lookup_var_key_t): Rename to...
(ctf_lookup_idx_key_t): ... this, now we use it for syms too.
<clik_names>: New member, a name table.
(ctf_lookup_var): Adjust accordingly.
(ctf_lookup_variable): Likewise.
(ctf_lookup_by_id): Shuffle further up in the file.
(ctf_symidx_sort_arg_cb): New, callback for...
(sort_symidx_by_name): ... this new function to sort a symidx
found to be unsorted (likely originating from the compiler).
(ctf_symidx_sort): New, sort a symidx.
(ctf_lookup_symbol_name): Support dynamic symbols with indexes
provided by the linker. Use ctf_link_sym_t, not Elf64_Sym.
Check the parent if a child lookup fails.
(ctf_lookup_by_symbol): Likewise. Work for function symbols too.
(ctf_symbol_next): New, iterate over symbols with types (without
sorting).
(ctf_lookup_idx_name): New, bsearch for symbol names in indexes.
(ctf_try_lookup_indexed): New, attempt an indexed lookup.
(ctf_func_info): Reimplement in terms of ctf_lookup_by_symbol.
(ctf_func_args): Likewise.
(ctf_get_dict): Move...
* ctf-types.c (ctf_get_dict): ... here.
* ctf-util.c (ctf_sym_to_elf64): Re-express as...
(ctf_elf64_to_link_sym): ... this. Add new st_symidx field, and
st_nameidx_set (always 0, so st_nameidx can be ignored). Look in
the ELF strtab for names.
(ctf_elf32_to_link_sym): Likewise, for Elf32_Sym.
(ctf_next_destroy): Destroy ctf_next_t.u.ctn_next if need be.
* libctf.ver: Add ctf_symbol_next, ctf_add_objt_sym and
ctf_add_func_sym.
|
|
The naming of the ctf_file_t type in libctf is a historical curiosity.
Back in the Solaris days, CTF dictionaries were originally generated as
a separate file and then (sometimes) merged into objects: hence the
datatype was named ctf_file_t, and known as a "CTF file". Nowadays, raw
CTF is essentially never written to a file on its own, and the datatype
changed name to a "CTF dictionary" years ago. So the term "CTF file"
refers to something that is never a file! This is at best confusing.
The type has also historically been known as a 'CTF container", which is
even more confusing now that we have CTF archives which are *also* a
sort of container (they contain CTF dictionaries), but which are never
referred to as containers in the source code.
So fix this by completing the renaming, renaming ctf_file_t to
ctf_dict_t throughout, and renaming those few functions that refer to
CTF files by name (keeping compatibility aliases) to refer to dicts
instead. Old users who still refer to ctf_file_t will see (harmless)
pointer-compatibility warnings at compile time, but the ABI is unchanged
(since C doesn't mangle names, and ctf_file_t was always an opaque type)
and things will still compile fine as long as -Werror is not specified.
All references to CTF containers and CTF files in the source code are
fixed to refer to CTF dicts instead.
Further (smaller) renamings of annoyingly-named functions to come, as
part of the process of souping up queries across whole archives at once
(needed for the function info and data object sections).
binutils/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* objdump.c (dump_ctf_errs): Rename ctf_file_t to ctf_dict_t.
(dump_ctf_archive_member): Likewise.
(dump_ctf): Likewise. Use ctf_dict_close, not ctf_file_close.
* readelf.c (dump_ctf_errs): Rename ctf_file_t to ctf_dict_t.
(dump_ctf_archive_member): Likewise.
(dump_section_as_ctf): Likewise. Use ctf_dict_close, not
ctf_file_close.
gdb/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ctfread.c: Change uses of ctf_file_t to ctf_dict_t.
(ctf_fp_info::~ctf_fp_info): Call ctf_dict_close, not ctf_file_close.
include/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ctf-api.h (ctf_file_t): Rename to...
(ctf_dict_t): ... this. Keep ctf_file_t around for compatibility.
(struct ctf_file): Likewise rename to...
(struct ctf_dict): ... this.
(ctf_file_close): Rename to...
(ctf_dict_close): ... this, keeping compatibility function.
(ctf_parent_file): Rename to...
(ctf_parent_dict): ... this, keeping compatibility function.
All callers adjusted.
* ctf.h: Rename references to ctf_file_t to ctf_dict_t.
(struct ctf_archive) <ctfa_nfiles>: Rename to...
<ctfa_ndicts>: ... this.
ld/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ldlang.c (ctf_output): This is a ctf_dict_t now.
(lang_ctf_errs_warnings): Rename ctf_file_t to ctf_dict_t.
(ldlang_open_ctf): Adjust comment.
(lang_merge_ctf): Use ctf_dict_close, not ctf_file_close.
* ldelfgen.h (ldelf_examine_strtab_for_ctf): Rename ctf_file_t to
ctf_dict_t. Change opaque declaration accordingly.
* ldelfgen.c (ldelf_examine_strtab_for_ctf): Adjust.
* ldemul.h (examine_strtab_for_ctf): Likewise.
(ldemul_examine_strtab_for_ctf): Likewise.
* ldeuml.c (ldemul_examine_strtab_for_ctf): Likewise.
libctf/ChangeLog
2020-11-20 Nick Alcock <nick.alcock@oracle.com>
* ctf-impl.h: Rename ctf_file_t to ctf_dict_t: all declarations
adjusted.
(ctf_fileops): Rename to...
(ctf_dictops): ... this.
(ctf_dedup_t) <cd_id_to_file_t>: Rename to...
<cd_id_to_dict_t>: ... this.
(ctf_file_t): Fix outdated comment.
<ctf_fileops>: Rename to...
<ctf_dictops>: ... this.
(struct ctf_archive_internal) <ctfi_file>: Rename to...
<ctfi_dict>: ... this.
* ctf-archive.c: Rename ctf_file_t to ctf_dict_t.
Rename ctf_archive.ctfa_nfiles to ctfa_ndicts.
Rename ctf_file_close to ctf_dict_close. All users adjusted.
* ctf-create.c: Likewise. Refer to CTF dicts, not CTF containers.
(ctf_bundle_t) <ctb_file>: Rename to...
<ctb_dict): ... this.
* ctf-decl.c: Rename ctf_file_t to ctf_dict_t.
* ctf-dedup.c: Likewise. Rename ctf_file_close to
ctf_dict_close. Refer to CTF dicts, not CTF containers.
* ctf-dump.c: Likewise.
* ctf-error.c: Likewise.
* ctf-hash.c: Likewise.
* ctf-inlines.h: Likewise.
* ctf-labels.c: Likewise.
* ctf-link.c: Likewise.
* ctf-lookup.c: Likewise.
* ctf-open-bfd.c: Likewise.
* ctf-string.c: Likewise.
* ctf-subr.c: Likewise.
* ctf-types.c: Likewise.
* ctf-util.c: Likewise.
* ctf-open.c: Likewise.
(ctf_file_close): Rename to...
(ctf_dict_close): ...this.
(ctf_file_close): New trivial wrapper around ctf_dict_close, for
compatibility.
(ctf_parent_file): Rename to...
(ctf_parent_dict): ... this.
(ctf_parent_file): New trivial wrapper around ctf_parent_dict, for
compatibility.
* libctf.ver: Add ctf_dict_close and ctf_parent_dict.
|
|
Systems like mingw64 have pointers that can only be represented by 'long
long'. Consistently cast integers stored in pointers through uintptr_t
to cater for this.
libctf/
* ctf-create.c (ctf_dtd_insert): Add uintptr_t casts.
(ctf_dtd_delete): Likewise.
(ctf_dtd_lookup): Likewise.
(ctf_rollback): Likewise.
* ctf-hash.c (ctf_hash_lookup_type): Likewise.
* ctf-types.c (ctf_lookup_by_rawhash): Likewise.
|
|
This adds the core deduplicator that the ctf_link machinery calls
(possibly repeatedly) to link the CTF sections: it takes an array
of input ctf_file_t's and another array that indicates which entries in
the input array are parents of which other entries, and returns an array
of outputs. The first output is always the ctf_file_t on which
ctf_link/ctf_dedup/etc was called: the other outputs are child dicts
that have the first output as their parent.
include/
* ctf-api.h (CTF_LINK_SHARE_DUPLICATED): No longer unimplemented.
libctf/
* ctf-impl.h (ctf_type_id_key): New, the key in the
cd_id_to_file_t.
(ctf_dedup): New, core deduplicator state.
(ctf_file_t) <ctf_dedup>: New.
<ctf_dedup_atoms>: New.
<ctf_dedup_atoms_alloc>: New.
(ctf_hash_type_id_key): New prototype.
(ctf_hash_eq_type_id_key): Likewise.
(ctf_dedup_atoms_init): Likewise.
* ctf-hash.c (ctf_hash_eq_type_id_key): New.
(ctf_dedup_atoms_init): Likewise.
* ctf-create.c (ctf_serialize): Adjusted.
(ctf_add_encoded): No longer static.
(ctf_add_reftype): Likewise.
* ctf-open.c (ctf_file_close): Destroy the
ctf_dedup_atoms_alloc.
* ctf-dedup.c: New file.
* ctf-decls.h [!HAVE_DECL_STPCPY]: Add prototype.
* configure.ac: Check for stpcpy.
* Makefile.am: Add it.
* Makefile.in: Regenerate.
* config.h.in: Regenerate.
* configure: Regenerate.
|
|
The name was just annoyingly long and I kept misspelling it.
It's also a bad name: it's not a mapping the type might be *used* in a
type mapping, but it is itself a representation of a type (a ctf_file_t
/ ctf_id_t pair), not of a mapping at all.
libctf/
* ctf-impl.h (ctf_link_type_mapping_key): Rename to...
(ctf_link_type_key): ... this, adjusting member prefixes to
match.
(ctf_hash_type_mapping_key): Rename to...
(ctf_hash_type_key): ... this.
(ctf_hash_eq_type_mapping_key): Rename to...
(ctf_hash_eq_type_key): ... this.
* ctf-hash.c (ctf_hash_type_mapping_key): Rename to...
(ctf_hash_type_key): ... this, and adjust for member name
changes.
(ctf_hash_eq_type_mapping_key): Rename to...
(ctf_hash_eq_type_key): ... this, and adjust for member name
changes.
* ctf-link.c (ctf_add_type_mapping): Adjust. Note the lack of
need for out-of-memory checking in this code.
(ctf_type_mapping): Adjust.
|
|
This lets you iterate over dynhashes and dynsets using the _next API.
dynhashes can be iterated over in sorted order, which works by
populating an array of key/value pairs using ctf_dynhash_next itself,
then sorting it with qsort.
Convenience inline functions named ctf_dyn{hash,set}_cnext are also
provided that take (-> return) const keys and values.
libctf/
* ctf-impl.h (ctf_next_hkv_t): New, kv-pairs passed to
sorting functions.
(ctf_next_t) <u.ctn_sorted_hkv>: New, sorted kv-pairs for
ctf_dynhash_next_sorted.
<cu.ctn_h>: New, pointer to the dynhash under iteration.
<cu.ctn_s>: New, pointer to the dynset under iteration.
(ctf_hash_sort_f): Sorting function passed to...
(ctf_dynhash_next_sorted): ... this new function.
(ctf_dynhash_next): New.
(ctf_dynset_next): New.
* ctf-inlines.h (ctf_dynhash_cnext_sorted): New.
(ctf_dynhash_cnext): New.
(ctf_dynset_cnext): New.
* ctf-hash.c (ctf_dynhash_next_sorted): New.
(ctf_dynhash_next): New.
(ctf_dynset_next): New.
* ctf-util.c (ctf_next_destroy): Free the u.ctn_sorted_hkv if
needed.
(ctf_next_copy): Alloc-and-copy the u.ctn_sorted_hkv if needed.
|
|
There are many places in the deduplicator which use hashtables as tiny
sets: keys with no value (and usually, but not always, no freeing
function) often with only one or a few members. For each of these, even
after the last change to not store the freeing functions, we are storing
a little malloced block for each item just to track the key/value pair,
and a little malloced block for the hash table itself just to track the
freeing function because we can't use libiberty hashtab's freeing
function because we are using that to free the little malloced per-item
block.
If we only have a key, we don't need any of that: we can ditch the
per-malloced block because we don't have a value, and we can ditch the
per-hashtab structure because we don't need to independently track the
freeing functions since libiberty hashtab is doing it for us. That
means we don't need an owner field in the (now nonexistent) item block
either.
Roughly speaking, this datatype saves about 25% in time and 20% in peak
memory usage for normal links, even fairly big ones. So this might seem
redundant, but it's really worth it.
Instead of a _lookup function, a dynset has two distinct functions:
ctf_dynset_exists, which returns true or false and an optional pointer
to the set member, and ctf_dynhash_lookup_any, which is used if all
members of the set are expected to be equivalent and we just want *any*
member and we don't care which one.
There is no iterator in this set of functions, not because we don't
iterate over dynset members -- we do, a lot -- but because the iterator
here is a member of an entirely new family of much more convenient
iteration functions, introduced in the next commit.
libctf/
* ctf-hash.c (ctf_dynset_eq_string): New.
(ctf_dynset_create): New.
(DYNSET_EMPTY_ENTRY_REPLACEMENT): New.
(DYNSET_DELETED_ENTRY_REPLACEMENT): New.
(key_to_internal): New.
(internal_to_key): New.
(ctf_dynset_insert): New.
(ctf_dynset_remove): New.
(ctf_dynset_destroy): New.
(ctf_dynset_lookup): New.
(ctf_dynset_exists): New.
(ctf_dynset_lookup_any): New.
(ctf_hash_insert_type): Coding style.
(ctf_hash_define_type): Likewise.
* ctf-impl.h (ctf_dynset_t): New.
(ctf_dynset_eq_string): New.
(ctf_dynset_create): New.
(ctf_dynset_insert): New.
(ctf_dynset_remove): New.
(ctf_dynset_destroy): New.
(ctf_dynset_lookup): New.
(ctf_dynset_exists): New.
(ctf_dynset_lookup_any): New.
* ctf-inlines.h (ctf_dynset_cinsert): New.
|
|
The libctf dynhash hashtab abstraction supports per-hashtab arbitrary
key/item freeing functions -- but it also has a constant slot type that
holds both key and value requested by the user, so it needs to use its
own freeing function to free that -- and it has nowhere to store the
freeing functions the caller requested.
So it copies them into every hash item, bloating every slot, even though
all items in a given hash table must have the same key and value freeing
functions.
So point back to the owner using a back-pointer, but don't even spend
space in the item or the hashtab allocating those freeing functions
unless necessary: if none are needed, we can simply arrange to not pass
in ctf_dynhash_item_free as a del_f to hashtab_create_alloc, and none of
those fields will ever be accessed.
The only downside is that this makes the code sensitive to the order of
fields in the ctf_helem_t and ctf_hashtab_t: but the deduplicator
allocates so many hash tables that doing this alone cuts memory usage
during deduplication by about 10%. (libiberty hashtab itself has a lot
of per-hashtab bloat: in the future we might trim that down, or make a
trimmer version.)
libctf/
* ctf-hash.c (ctf_helem_t) <key_free>: Remove.
<value_free>: Likewise.
<owner>: New.
(ctf_dynhash_item_free): Indirect through the owner.
(ctf_dynhash_create): Only pass in ctf_dynhash_item_free and
allocate space for the key_free and value_free fields fields
if necessary.
(ctf_hashtab_insert): Likewise. Fix OOM errno value.
(ctf_dynhash_insert): Only access ctf_hashtab's key_free and
value_free if they will exist. Set the slot's owner, but only
if it exists.
(ctf_dynhash_remove): Adjust.
|
|
Right now, if you insert a key/value pair into a dynhash, the old slot's
key is freed and the new one always assigned. This seemed sane to me
when I wrote it, but I got it wrong time and time again. It's much
less confusing to free the key passed in: if a key-freeing function
was passed, you are asserting that the dynhash owns the key in any
case, so if you pass in a key it is always buggy to assume it sticks
around. Freeing the old key means that you can't even safely look up a
key from out of a dynhash and hold on to it, because some other matching
key might force it to be freed at any time.
In the new model, you can always get a key out of a dynhash with
ctf_dynhash_lookup_kv and hang on to it until the kv-pair is actually
deleted from the dynhash. In the old model the pointer to the key might
be freed at any time if a matching key was inserted.
libctf/
* ctf-hash.c (ctf_hashtab_insert): Free the key passed in if
there is a key-freeing function and the key already exists.
|
|
Future commits will use these.
ctf_dynhash_elements: count elements in a dynhash
ctf_dynhash_lookup_kv: look up and return pointers to the original key
and value in a dynhash (the only way of getting
a reference to the original key)
ctf_dynhash_iter_find: iterate until an item is found, then return its
key
ctf_dynhash_cinsert: insert a const key / value into a dynhash (a thim
wrapper in a new header dedicated to inline
functions).
As with the rest of ctf_dynhash, this is not public API. No impact
on existing callers is expected.
libctf/
* ctf-inlines.h: New file.
* ctf-impl.h: Include it.
(ctf_hash_iter_find_f): New typedef.
(ctf_dynhash_elements): New.
(ctf_dynhash_lookup_kv): New.
(ctf_dynhash_iter_find): New.
* ctf-hash.c (ctf_dynhash_lookup_kv): New.
(ctf_traverse_find_cb_arg_t): New.
(ctf_hashtab_traverse_find): New.
(ctf_dynhash_iter_find): New.
(ctf_dynhash_elements): New.
|
|
|
|
When a ctf_dynhash_insert() finds a slot already existing, it should
call the key and value free functions on the existing key and value and
move the passed-in key into place, so that the lifetime rules for hash
keys are always the same no matter whether the key existed or not but
neither are the keys or values leaked.
New in v3.
v5: fix tabdamage.
libctf/
* ctf-hash.c (ctf_hashtab_insert): Pass in the key and value
freeing functions: if set, free the key and value if the slot
already exists. Always reassign the key.
(ctf_dynhash_insert): Adjust call appropriately.
(ctf_hash_insert_type): Likewise.
|
|
This lets you call ctf_type_mapping (dest_fp, src_fp, src_type_id)
and get told what type ID the corresponding type has in the target
ctf_file_t. This works even if it was added by a recursive call, and
because it is stored in the target ctf_file_t it works even if we
had to add one type to multiple ctf_file_t's as part of conflicting
type handling.
We empty out this mapping after every archive is linked: because it maps
input to output fps, and we only visit each input fp once, its contents
are rendered entirely useless every time the source fp changes.
v3: add several missing mapping additions. Add ctf_dynhash_empty, and
empty after every input archive.
v5: fix tabdamage.
libctf/
* ctf-impl.h (ctf_file_t): New field ctf_link_type_mapping.
(struct ctf_link_type_mapping_key): New.
(ctf_hash_type_mapping_key): Likewise.
(ctf_hash_eq_type_mapping_key): Likewise.
(ctf_add_type_mapping): Likewise.
(ctf_type_mapping): Likewise.
(ctf_dynhash_empty): Likewise.
* ctf-open.c (ctf_file_close): Update accordingly.
* ctf-create.c (ctf_update): Likewise.
(ctf_add_type): Populate the mapping.
* ctf-hash.c (ctf_hash_type_mapping_key): Hash a type mapping key.
(ctf_hash_eq_type_mapping_key): Check the key for equality.
(ctf_dynhash_insert): Fix comment typo.
(ctf_dynhash_empty): New.
* ctf-link.c (ctf_add_type_mapping): New.
(ctf_type_mapping): Likewise.
(empty_link_type_mapping): New.
(ctf_link_one_input_archive): Call it.
|
|
The CTF file format has always supported "external strtabs", which
internally are strtab offsets with their MSB on: such refs
get their strings from the strtab passed in at CTF file open time:
this is usually intended to be the ELF strtab, and that's what this
implementation is meant to support, though in theory the external
strtab could come from anywhere.
This commit adds support for these external strings in the ctf-string.c
strtab tracking layer. It's quite easy: we just add a field csa_offset
to the atoms table that tracks all strings: this field tracks the offset
of the string in the ELF strtab (with its MSB already on, courtesy of a
new macro CTF_SET_STID), and adds a new function that sets the
csa_offset to the specified offset (plus MSB). Then we just need to
avoid writing out strings to the internal strtab if they have csa_offset
set, and note that the internal strtab is shorter than it might
otherwise be.
(We could in theory save a little more time here by eschewing sorting
such strings, since we never actually write the strings out anywhere,
but that would mean storing them separately and it's just not worth the
complexity cost until profiling shows it's worth doing.)
We also have to go through a bit of extra effort at variable-sorting
time. This was previously using direct references to the internal
strtab: it couldn't use ctf_strptr or ctf_strraw because the new strtab
is not yet ready to put in its usual field (in a ctf_file_t that hasn't
even been allocated yet at this stage): but now we're using the external
strtab, this will no longer do because it'll be looking things up in the
wrong strtab, with disastrous results. Instead, pass the new internal
strtab in to a new ctf_strraw_explicit function which is just like
ctf_strraw except you can specify a ne winternal strtab to use.
But even now that it is using a new internal strtab, this is not quite
enough: it can't look up strings in the external strtab because ld
hasn't written it out yet, and when it does will write it straight to
disk. Instead, when we write the internal strtab, note all the offset
-> string mappings that we have noted belong in the *external* strtab to
a new "synthetic external strtab" dynhash, ctf_syn_ext_strtab, and look
in there at ctf_strraw time if it is set. This uses minimal extra
memory (because only strings in the external strtab that we actually use
are stored, and even those come straight out of the atoms table), but
let both variable sorting and name interning when ctf_bufopen is next
called work fine. (This also means that we don't need to filter out
spurious ECTF_STRTAB warnings from ctf_bufopen but can pass them back to
the caller, once we wrap ctf_bufopen so that we have a new internal
variant of ctf_bufopen etc that we can pass the synthetic external
strtab to. That error has been filtered out since the days of Solaris
libctf, which didn't try to handle the problem of getting external
strtabs right at construction time at all.)
v3: add the synthetic strtab and all associated machinery.
v5: fix tabdamage.
include/
* ctf.h (CTF_SET_STID): New.
libctf/
* ctf-impl.h (ctf_str_atom_t) <csa_offset>: New field.
(ctf_file_t) <ctf_syn_ext_strtab>: Likewise.
(ctf_str_add_ref): Name the last arg.
(ctf_str_add_external) New.
(ctf_str_add_strraw_explicit): Likewise.
(ctf_simple_open_internal): Likewise.
(ctf_bufopen_internal): Likewise.
* ctf-string.c (ctf_strraw_explicit): Split from...
(ctf_strraw): ... here, with new support for ctf_syn_ext_strtab.
(ctf_str_add_ref_internal): Return the atom, not the
string.
(ctf_str_add): Adjust accordingly.
(ctf_str_add_ref): Likewise. Move up in the file.
(ctf_str_add_external): New: update the csa_offset.
(ctf_str_count_strtab): Only account for strings with no csa_offset
in the internal strtab length.
(ctf_str_write_strtab): If the csa_offset is set, update the
string's refs without writing the string out, and update the
ctf_syn_ext_strtab. Make OOM handling less ugly.
* ctf-create.c (struct ctf_sort_var_arg_cb): New.
(ctf_update): Handle failure to populate the strtab. Pass in the
new ctf_sort_var arg. Adjust for ctf_syn_ext_strtab addition.
Call ctf_simple_open_internal, not ctf_simple_open.
(ctf_sort_var): Call ctf_strraw_explicit rather than looking up
strings by hand.
* ctf-hash.c (ctf_hash_insert_type): Likewise (but using
ctf_strraw). Adjust to diagnose ECTF_STRTAB nonetheless.
* ctf-open.c (init_types): No longer filter out ECTF_STRTAB.
(ctf_file_close): Destroy the ctf_syn_ext_strtab.
(ctf_simple_open): Rename to, and reimplement as a wrapper around...
(ctf_simple_open_internal): ... this new function, which calls
ctf_bufopen_internal.
(ctf_bufopen): Rename to, and reimplement as a wrapper around...
(ctf_bufopen_internal): ... this new function, which sets
ctf_syn_ext_strtab.
|
|
There are two, ctf_dynhash_iter and ctf_dynhash_iter_remove: the latter
lets you return a nonzero value to remove the element being iterated
over.
Used in the next commit.
libctf/
* ctf-impl.h (ctf_hash_iter_f): New.
(ctf_dynhash_iter): New declaration.
(ctf_dynhash_iter_remove): New declaration.
* ctf-hash.c (ctf_dynhash_iter): Define.
(ctf_dynhash_iter_remove): Likewise.
(ctf_hashtab_traverse): New.
(ctf_hashtab_traverse_remove): Likewise.
(struct ctf_traverse_cb_arg): Likewise.
(struct ctf_traverse_remove_cb_arg): Likewise.
|
|
We must call htab_remove_elt with an element (in this case, a mocked-up
one with only the key populated, since no reasonable hash function will
need the other fields), not with the key alone.
libctf/
* ctf-hash.c (ctf_dynhash_remove): Call with a mocked-up element.
|
|
libctf maintains two distinct hash ADTs, one (ctf_dynhash) for wrapping
dynamically-generated unknown-sized hashes during CTF file construction,
one (ctf_hash) for wrapping unchanging hashes whose size is known at
creation time for reading CTF files that were previously created.
In the binutils implementation, these are both fairly thin wrappers
around libiberty hashtab.
Unusually, this code is not kept synchronized with libdtrace-ctf,
due to its dependence on libiberty hashtab.
libctf/
* ctf-hash.c: New file.
* ctf-impl.h: New declarations.
|
