libctf: symbol type linking support

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.

14 files changed, 1898 insertions, 272 deletions

diff --git a/include/ChangeLog b/include/ChangeLog
index 5c0f6b9..ad4c8a6 100644
--- a/include/ChangeLog
+++ b/include/ChangeLog
@@ -1,5 +1,15 @@
 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.
+
+2020-11-20  Nick Alcock  <nick.alcock@oracle.com>
+
 	* bfdlink.h (struct elf_sym_strtab): Replace with...
 	(struct elf_internal_sym): ... this.
 	(struct bfd_link_callbacks) <examine_strtab>: Take only a
diff --git a/include/ctf-api.h b/include/ctf-api.h
index 93bd5f3..6dd37b9 100644
--- a/include/ctf-api.h
+++ b/include/ctf-api.h
@@ -361,6 +361,8 @@ extern int ctf_func_type_args (ctf_dict_t *, ctf_id_t, uint32_t, ctf_id_t *);
 
 extern ctf_id_t ctf_lookup_by_name (ctf_dict_t *, const char *);
 extern ctf_id_t ctf_lookup_by_symbol (ctf_dict_t *, unsigned long);
+extern ctf_id_t ctf_symbol_next (ctf_dict_t *, ctf_next_t **,
+				 const char **name, int functions);
 extern ctf_id_t ctf_lookup_variable (ctf_dict_t *, const char *);
 
 extern ctf_id_t ctf_type_resolve (ctf_dict_t *, ctf_id_t);
@@ -468,6 +470,9 @@ extern int ctf_add_member_encoded (ctf_dict_t *, ctf_id_t, const char *,
 
 extern int ctf_add_variable (ctf_dict_t *, const char *, ctf_id_t);
 
+extern int ctf_add_objt_sym (ctf_dict_t *, const char *, ctf_id_t);
+extern int ctf_add_func_sym (ctf_dict_t *, const char *, ctf_id_t);
+
 extern int ctf_set_array (ctf_dict_t *, ctf_id_t, const ctf_arinfo_t *);
 
 extern ctf_dict_t *ctf_create (int *);
diff --git a/include/ctf.h b/include/ctf.h
index d0a21f1..c7a1e43 100644
--- a/include/ctf.h
+++ b/include/ctf.h
@@ -73,18 +73,20 @@ extern "C"
    the data types section.  Each label is accompanied by a type ID i.  A given
    label refers to the group of types whose IDs are in the range [0, i].
 
-   Data object and function records are stored in the same order as they appear
-   in the corresponding symbol table, except that symbols marked SHN_UNDEF are
-   not stored and symbols that have no type data are padded out with zeroes.
-   For each data object, the type ID (a small integer) is recorded.  For each
-   function, the type ID of the return type and argument types is recorded.
+   Data object and function records (collectively, "symtypetabs") are stored in
+   the same order as they appear in the corresponding symbol table, except that
+   symbols marked SHN_UNDEF are not stored and symbols that have no type data
+   are padded out with zeroes.  For each entry in these tables, the type ID (a
+   small integer) is recorded.  (Functions get CTF_K_FUNCTION types, just like
+   data objects that are function pointers.)
 
    For situations in which the order of the symbols in the symtab is not known,
-   a pair of optional indexes follow the data object and function info sections:
-   each of these is an array of strtab indexes, mapped 1:1 to the corresponding
-   data object / function info section, giving each entry in those sections a
-   name so that the linker can correlate them with final symtab entries and
-   reorder them accordingly (dropping the indexes in the process).
+   or most symbols have no type in this dict and most entries would be
+   zero-pads, a pair of optional indexes follow the data object and function
+   info sections: each of these is an array of strtab indexes, mapped 1:1 to the
+   corresponding data object / function info section, giving each entry in those
+   sections a name so that the linker can correlate them with final symtab
+   entries and reorder them accordingly (dropping the indexes in the process).
 
    Variable records (as distinct from data objects) provide a modicum of support
    for non-ELF systems, mapping a variable name to a CTF type ID.  The variable
@@ -92,7 +94,8 @@ extern "C"
    not define how the consumer maps these variable names to addresses or
    anything else, or indeed what these names represent: they might be names
    looked up at runtime via dlsym() or names extracted at runtime by a debugger
-   or anything else the consumer likes.
+   or anything else the consumer likes.  Variable records with identically-
+   named entries in the data object section are removed.
 
    The data types section is a list of variable size records that represent each
    type, in order by their ID.  The types themselves form a directed graph,
@@ -104,9 +107,9 @@ extern "C"
    Strings are recorded as a string table ID (0 or 1) and a byte offset into the
    string table.  String table 0 is the internal CTF string table.  String table
    1 is the external string table, which is the string table associated with the
-   ELF symbol table for this object.  CTF does not record any strings that are
-   already in the symbol table, and the CTF string table does not contain any
-   duplicated strings.
+   ELF dynamic symbol table for this object.  CTF does not record any strings
+   that are already in the symbol table, and the CTF string table does not
+   contain any duplicated strings.
 
    If the CTF data has been merged with another parent CTF object, some outgoing
    edges may refer to type nodes that exist in another CTF object.  The debugger
@@ -199,9 +202,16 @@ typedef struct ctf_header
 #define CTF_VERSION_3 4
 #define CTF_VERSION CTF_VERSION_3 /* Current version.  */
 
+/* All of these flags bar CTF_F_COMPRESS and CTF_F_IDXSORTED are bug-workaround
+   flags and are valid only in format v3: in v2 and below they cannot occur and
+   in v4 and later, they will be recycled for other purposes.  */
+
 #define CTF_F_COMPRESS	0x1		/* Data buffer is compressed by libctf.  */
+#define CTF_F_NEWFUNCINFO 0x2		/* New v3 func info section format.  */
+#define CTF_F_IDXSORTED 0x4		/* Index sections already sorted.  */
 #define CTF_F_DYNSTR 0x8		/* Strings come from .dynstr.  */
-#define CTF_F_MAX (CTF_F_COMPRESS | CTF_F_DYNSTR)
+#define CTF_F_MAX (CTF_F_COMPRESS | CTF_F_NEWFUNCINFO | CTF_F_IDXSORTED	\
+		   | CTF_F_DYNSTR)
 
 typedef struct ctf_lblent
 {
diff --git a/libctf/ChangeLog b/libctf/ChangeLog
index 6670a6a..8f2fb48 100644
--- a/libctf/ChangeLog
+++ b/libctf/ChangeLog
@@ -1,5 +1,117 @@
 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.
+
+2020-11-20  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-link.c (ctf_link_shuffle_syms): Adjust.
 	(ctf_link_add_linker_symbol): New, unimplemented stub.
 	* libctf.ver: Add it.
diff --git a/libctf/ctf-create.c b/libctf/ctf-create.c
index 384e8cf..5fc50a5 100644
--- a/libctf/ctf-create.c
+++ b/libctf/ctf-create.c
@@ -24,6 +24,9 @@
 #include <unistd.h>
 #include <zlib.h>
 
+#include <elf.h>
+#include "elf-bfd.h"
+
 #ifndef EOVERFLOW
 #define EOVERFLOW ERANGE
 #endif
@@ -79,6 +82,7 @@ ctf_create (int *errp)
   ctf_dynhash_t *dthash;
   ctf_dynhash_t *dvhash;
   ctf_dynhash_t *structs = NULL, *unions = NULL, *enums = NULL, *names = NULL;
+  ctf_dynhash_t *objthash = NULL, *funchash = NULL;
   ctf_sect_t cts;
   ctf_dict_t *fp;
 
@@ -107,6 +111,10 @@ ctf_create (int *errp)
 			      NULL, NULL);
   names = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
 			      NULL, NULL);
+  objthash = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
+				 free, NULL);
+  funchash = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
+				 free, NULL);
   if (!structs || !unions || !enums || !names)
     {
       ctf_set_open_errno (errp, EAGAIN);
@@ -125,6 +133,8 @@ ctf_create (int *errp)
   fp->ctf_unions.ctn_writable = unions;
   fp->ctf_enums.ctn_writable = enums;
   fp->ctf_names.ctn_writable = names;
+  fp->ctf_objthash = objthash;
+  fp->ctf_funchash = funchash;
   fp->ctf_dthash = dthash;
   fp->ctf_dvhash = dvhash;
   fp->ctf_dtoldid = 0;
@@ -148,6 +158,8 @@ ctf_create (int *errp)
   ctf_dynhash_destroy (unions);
   ctf_dynhash_destroy (enums);
   ctf_dynhash_destroy (names);
+  ctf_dynhash_destroy (objthash);
+  ctf_dynhash_destroy (funchash);
   ctf_dynhash_destroy (dvhash);
  err_dt:
   ctf_dynhash_destroy (dthash);
@@ -155,6 +167,395 @@ ctf_create (int *errp)
   return NULL;
 }
 
+/* Delete data symbols that have been assigned names from the variable section.
+   Must be called from within ctf_serialize, because that is the only place
+   you can safely delete variables without messing up ctf_rollback.  */
+
+static int
+symtypetab_delete_nonstatic_vars (ctf_dict_t *fp)
+{
+  ctf_dvdef_t *dvd, *nvd;
+  ctf_id_t type;
+
+  for (dvd = ctf_list_next (&fp->ctf_dvdefs); dvd != NULL; dvd = nvd)
+    {
+      nvd = ctf_list_next (dvd);
+
+      if (((type = (ctf_id_t) (uintptr_t)
+	    ctf_dynhash_lookup (fp->ctf_objthash, dvd->dvd_name)) > 0)
+	  && type == dvd->dvd_type)
+	ctf_dvd_delete (fp, dvd);
+    }
+
+  return 0;
+}
+
+/* Determine if a symbol is "skippable" and should never appear in the
+   symtypetab sections.  */
+
+int
+ctf_symtab_skippable (ctf_link_sym_t *sym)
+{
+  /* Never skip symbols whose name is not yet known.  */
+  if (sym->st_nameidx_set)
+    return 0;
+
+  return (sym->st_name == NULL || sym->st_name[0] == 0
+	  || sym->st_shndx == SHN_UNDEF
+	  || strcmp (sym->st_name, "_START_") == 0
+	  || strcmp (sym->st_name, "_END_") == 0
+	  || (sym->st_type == STT_OBJECT && sym->st_shndx == SHN_EXTABS
+	      && sym->st_value == 0));
+}
+
+/* Symtypetab emission flags.  */
+
+#define CTF_SYMTYPETAB_EMIT_FUNCTION 0x1
+#define CTF_SYMTYPETAB_EMIT_PAD 0x2
+#define CTF_SYMTYPETAB_FORCE_INDEXED 0x4
+
+/* Get the number of symbols in a symbol hash, the count of symbols, the maximum
+   seen, the eventual size, without any padding elements, of the func/data and
+   (if generated) index sections, and the size of accumulated padding elements.
+   The linker-reported set of symbols is found in SYMFP.
+
+   Also figure out if any symbols need to be moved to the variable section, and
+   add them (if not already present).  */
+
+_libctf_nonnull_
+static int
+symtypetab_density (ctf_dict_t *fp, ctf_dict_t *symfp, ctf_dynhash_t *symhash,
+		    size_t *count, size_t *max, size_t *unpadsize,
+		    size_t *padsize, size_t *idxsize, int flags)
+{
+  ctf_next_t *i = NULL;
+  const void *name;
+  const void *ctf_sym;
+  ctf_dynhash_t *linker_known = NULL;
+  int err;
+  int beyond_max = 0;
+
+  *count = 0;
+  *max = 0;
+  *unpadsize = 0;
+  *idxsize = 0;
+  *padsize = 0;
+
+  if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+    {
+      /* Make a dynhash citing only symbols reported by the linker of the
+	 appropriate type, then traverse all potential-symbols we know the types
+	 of, removing them from linker_known as we go.  Once this is done, the
+	 only symbols remaining in linker_known are symbols we don't know the
+	 types of: we must emit pads for those symbols that are below the
+	 maximum symbol we will emit (any beyond that are simply skipped).  */
+
+      if ((linker_known = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
+					      NULL, NULL)) == NULL)
+	return (ctf_set_errno (fp, ENOMEM));
+
+      while ((err = ctf_dynhash_cnext (symfp->ctf_dynsyms, &i,
+				       &name, &ctf_sym)) == 0)
+	{
+	  ctf_link_sym_t *sym = (ctf_link_sym_t *) ctf_sym;
+
+	  if (((flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+	       && sym->st_type != STT_FUNC)
+	      || (!(flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+		  && sym->st_type != STT_OBJECT))
+	    continue;
+
+	  if (ctf_symtab_skippable (sym))
+	    continue;
+
+	  /* This should only be true briefly before all the names are
+	     finalized, long before we get this far.  */
+	  if (!ctf_assert (fp, !sym->st_nameidx_set))
+	    return -1;				/* errno is set for us.  */
+
+	  if (ctf_dynhash_cinsert (linker_known, name, ctf_sym) < 0)
+	    {
+	      ctf_dynhash_destroy (linker_known);
+	      return (ctf_set_errno (fp, ENOMEM));
+	    }
+	}
+      if (err != ECTF_NEXT_END)
+	{
+	  ctf_err_warn (fp, 0, err, _("iterating over linker-known symbols during "
+				  "serialization"));
+	  ctf_dynhash_destroy (linker_known);
+	  return (ctf_set_errno (fp, err));
+	}
+    }
+
+  while ((err = ctf_dynhash_cnext (symhash, &i, &name, NULL)) == 0)
+    {
+      ctf_link_sym_t *sym;
+
+      if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+	{
+	  /* Linker did not report symbol in symtab.  Remove it from the
+	     set of known data symbols and continue.  */
+	  if ((sym = ctf_dynhash_lookup (symfp->ctf_dynsyms, name)) == NULL)
+	    {
+	      ctf_dynhash_remove (symhash, name);
+	      continue;
+	    }
+
+	  /* We don't remove skippable symbols from the symhash because we don't
+	     want them to be migrated into variables.  */
+	  if (ctf_symtab_skippable (sym))
+	    continue;
+
+	  if ((flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+	      && sym->st_type != STT_FUNC)
+	    {
+	      ctf_err_warn (fp, 1, 0, _("Symbol %x added to CTF as a function "
+					"but is of type %x\n"),
+			    sym->st_symidx, sym->st_type);
+	      ctf_dynhash_remove (symhash, name);
+	      continue;
+	    }
+	  else if (!(flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+		   && sym->st_type != STT_OBJECT)
+	    {
+	      ctf_err_warn (fp, 1, 0, _("Symbol %x added to CTF as a data "
+					"object but is of type %x\n"),
+			    sym->st_symidx, sym->st_type);
+	      ctf_dynhash_remove (symhash, name);
+	      continue;
+	    }
+
+	  ctf_dynhash_remove (linker_known, name);
+	}
+      *unpadsize += sizeof (uint32_t);
+      (*count)++;
+
+      if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+	{
+	  if (*max < sym->st_symidx)
+	    *max = sym->st_symidx;
+	}
+      else
+	(*max)++;
+    }
+  if (err != ECTF_NEXT_END)
+    {
+      ctf_err_warn (fp, 0, err, _("iterating over CTF symtypetab during "
+				  "serialization"));
+      ctf_dynhash_destroy (linker_known);
+      return (ctf_set_errno (fp, err));
+    }
+
+  if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+    {
+      while ((err = ctf_dynhash_cnext (linker_known, &i, NULL, &ctf_sym)) == 0)
+	{
+	  ctf_link_sym_t *sym = (ctf_link_sym_t *) ctf_sym;
+
+	  if (sym->st_symidx > *max)
+	    beyond_max++;
+	}
+      if (err != ECTF_NEXT_END)
+	{
+	  ctf_err_warn (fp, 0, err, _("iterating over linker-known symbols "
+				      "during CTF serialization"));
+	  ctf_dynhash_destroy (linker_known);
+	  return (ctf_set_errno (fp, err));
+	}
+    }
+
+  *idxsize = *count * sizeof (uint32_t);
+  if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+    *padsize = (ctf_dynhash_elements (linker_known) - beyond_max) * sizeof (uint32_t);
+
+  ctf_dynhash_destroy (linker_known);
+  return 0;
+}
+
+/* Emit an objt or func symtypetab into DP in a particular order defined by an
+   array of ctf_link_sym_t or symbol names passed in.  The index has NIDX
+   elements in it: unindexed output would terminate at symbol OUTMAX and is in
+   any case no larger than SIZE bytes.  Some index elements are expected to be
+   skipped: see symtypetab_density.  The linker-reported set of symbols (if any)
+   is found in SYMFP. */
+static int
+emit_symtypetab (ctf_dict_t *fp, ctf_dict_t *symfp, uint32_t *dp,
+		 ctf_link_sym_t **idx, const char **nameidx, uint32_t nidx,
+		 uint32_t outmax, int size, int flags)
+{
+  uint32_t i;
+  uint32_t *dpp = dp;
+  ctf_dynhash_t *symhash;
+
+  ctf_dprintf ("Emitting table of size %i, outmax %u, %u symtypetab entries, "
+	       "flags %i\n", size, outmax, nidx, flags);
+
+  /* Empty table? Nothing to do.  */
+  if (size == 0)
+    return 0;
+
+  if (flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+    symhash = fp->ctf_funchash;
+  else
+    symhash = fp->ctf_objthash;
+
+  for (i = 0; i < nidx; i++)
+    {
+      const char *sym_name;
+      void *type;
+
+      /* If we have a linker-reported set of symbols, we may be given that set
+	 to work from, or a set of symbol names.  In both cases we want to look
+	 at the corresponding linker-reported symbol (if any).  */
+      if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+	{
+	  ctf_link_sym_t *this_link_sym;
+
+	  if (idx)
+	    this_link_sym = idx[i];
+	  else
+	    this_link_sym = ctf_dynhash_lookup (symfp->ctf_dynsyms, nameidx[i]);
+
+	  /* Unreported symbol number.  No pad, no nothing.  */
+	  if (!this_link_sym)
+	    continue;
+
+	  /* Symbol of the wrong type, or skippable?  This symbol is not in this
+	     table.  */
+	  if (((flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+	       && this_link_sym->st_type != STT_FUNC)
+	      || (!(flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+		  && this_link_sym->st_type != STT_OBJECT))
+	    continue;
+
+	  if (ctf_symtab_skippable (this_link_sym))
+	    continue;
+
+	  sym_name = this_link_sym->st_name;
+
+	  /* Linker reports symbol of a different type to the symbol we actually
+	     added?  Skip the symbol.  No pad, since the symbol doesn't actually
+	     belong in this table at all.  (Warned about in
+	     symtypetab_density.)  */
+	  if ((this_link_sym->st_type == STT_FUNC)
+	      && (ctf_dynhash_lookup (fp->ctf_objthash, sym_name)))
+	    continue;
+
+	  if ((this_link_sym->st_type == STT_OBJECT)
+	      && (ctf_dynhash_lookup (fp->ctf_funchash, sym_name)))
+	    continue;
+	}
+      else
+	sym_name = nameidx[i];
+
+      /* Symbol in index but no type set? Silently skip and (optionally)
+	 pad.  (In force-indexed mode, this is also where we track symbols of
+	 the wrong type for this round of insertion.)  */
+      if ((type = ctf_dynhash_lookup (symhash, sym_name)) == NULL)
+	{
+	  if (flags & CTF_SYMTYPETAB_EMIT_PAD)
+	    *dpp++ = 0;
+	  continue;
+	}
+
+      if (!ctf_assert (fp, (((char *) dpp) - (char *) dp) < size))
+	return -1;				/* errno is set for us.  */
+
+      *dpp++ = (ctf_id_t) (uintptr_t) type;
+
+      /* When emitting unindexed output, all later symbols are pads: stop
+	 early.  */
+      if ((flags & CTF_SYMTYPETAB_EMIT_PAD) && idx[i]->st_symidx == outmax)
+	break;
+    }
+
+  return 0;
+}
+
+/* Emit an objt or func symtypetab index into DP in a paticular order defined by
+   an array of symbol names passed in.  Stop at NIDX.  The linker-reported set
+   of symbols (if any) is found in SYMFP. */
+static int
+emit_symtypetab_index (ctf_dict_t *fp, ctf_dict_t *symfp, uint32_t *dp,
+		       const char **idx, uint32_t nidx, int size, int flags)
+{
+  uint32_t i;
+  uint32_t *dpp = dp;
+  ctf_dynhash_t *symhash;
+
+  ctf_dprintf ("Emitting index of size %i, %u entries reported by linker, "
+	       "flags %i\n", size, nidx, flags);
+
+  /* Empty table? Nothing to do.  */
+  if (size == 0)
+    return 0;
+
+  if (flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+    symhash = fp->ctf_funchash;
+  else
+    symhash = fp->ctf_objthash;
+
+  /* Indexes should always be unpadded.  */
+  if (!ctf_assert (fp, !(flags & CTF_SYMTYPETAB_EMIT_PAD)))
+    return -1;					/* errno is set for us.  */
+
+  for (i = 0; i < nidx; i++)
+    {
+      const char *sym_name;
+      void *type;
+
+      if (!(flags & CTF_SYMTYPETAB_FORCE_INDEXED))
+	{
+	  ctf_link_sym_t *this_link_sym;
+
+	  this_link_sym = ctf_dynhash_lookup (symfp->ctf_dynsyms, idx[i]);
+
+	  /* This is an index: unreported symbols should never appear in it.  */
+	  if (!ctf_assert (fp, this_link_sym != NULL))
+	    return -1;				/* errno is set for us.  */
+
+	  /* Symbol of the wrong type, or skippable?  This symbol is not in this
+	     table.  */
+	  if (((flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+	       && this_link_sym->st_type != STT_FUNC)
+	      || (!(flags & CTF_SYMTYPETAB_EMIT_FUNCTION)
+		  && this_link_sym->st_type != STT_OBJECT))
+	    continue;
+
+	  if (ctf_symtab_skippable (this_link_sym))
+	    continue;
+
+	  sym_name = this_link_sym->st_name;
+
+	  /* Linker reports symbol of a different type to the symbol we actually
+	     added?  Skip the symbol.  */
+	  if ((this_link_sym->st_type == STT_FUNC)
+	      && (ctf_dynhash_lookup (fp->ctf_objthash, sym_name)))
+	    continue;
+
+	  if ((this_link_sym->st_type == STT_OBJECT)
+	      && (ctf_dynhash_lookup (fp->ctf_funchash, sym_name)))
+	    continue;
+	}
+      else
+	sym_name = idx[i];
+
+      /* Symbol in index and reported by linker, but no type set? Silently skip
+	 and (optionally) pad.  (In force-indexed mode, this is also where we
+	 track symbols of the wrong type for this round of insertion.)  */
+      if ((type = ctf_dynhash_lookup (symhash, sym_name)) == NULL)
+	continue;
+
+      ctf_str_add_ref (fp, sym_name, dpp++);
+
+      if (!ctf_assert (fp, (((char *) dpp) - (char *) dp) <= size))
+	return -1;				/* errno is set for us.  */
+    }
+
+  return 0;
+}
+
 static unsigned char *
 ctf_copy_smembers (ctf_dict_t *fp, ctf_dtdef_t *dtd, unsigned char *t)
 {
@@ -275,11 +676,18 @@ ctf_serialize (ctf_dict_t *fp)
   ctf_dvdef_t *dvd;
   ctf_varent_t *dvarents;
   ctf_strs_writable_t strtab;
+  ctf_dict_t *symfp = fp;
 
   unsigned char *t;
   unsigned long i;
-  size_t buf_size, type_size, nvars;
-  unsigned char *buf, *newbuf;
+  int symflags = 0;
+  size_t buf_size, type_size, objt_size, func_size;
+  size_t objt_unpadsize, func_unpadsize, objt_padsize, func_padsize;
+  size_t funcidx_size, objtidx_size;
+  size_t nvars, nfuncs, nobjts, maxobjt, maxfunc;
+  size_t ndynsyms = 0;
+  const char **sym_name_order = NULL;
+  unsigned char *buf = NULL, *newbuf;
   int err;
 
   if (!(fp->ctf_flags & LCTF_RDWR))
@@ -292,13 +700,17 @@ ctf_serialize (ctf_dict_t *fp)
   /* Fill in an initial CTF header.  We will leave the label, object,
      and function sections empty and only output a header, type section,
      and string table.  The type section begins at a 4-byte aligned
-     boundary past the CTF header itself (at relative offset zero).  */
+     boundary past the CTF header itself (at relative offset zero).  The flag
+     indicating a new-style function info section (an array of CTF_K_FUNCTION
+     type IDs in the types section) is flipped on.  */
 
   memset (&hdr, 0, sizeof (hdr));
   hdr.cth_magic = CTF_MAGIC;
   hdr.cth_version = CTF_VERSION;
 
-  hdr.cth_flags = CTF_F_DYNSTR;
+  /* This is a new-format func info section, and the symtab and strtab come out
+     of the dynsym and dynstr these days.  */
+  hdr.cth_flags = (CTF_F_NEWFUNCINFO | CTF_F_DYNSTR);
 
   /* Iterate through the dynamic type definition list and compute the
      size of the CTF type section we will need to generate.  */
@@ -342,6 +754,84 @@ ctf_serialize (ctf_dict_t *fp)
 	}
     }
 
+  /* Symbol table stuff is done only if the linker has told this dict about
+     potential symbols (usually the case for parent dicts only).  The linker
+     will report symbols to the parent dict in a parent/child link, as usual
+     with all linker-related matters.  */
+
+  if (!fp->ctf_dynsyms && fp->ctf_parent && fp->ctf_parent->ctf_dynsyms)
+    symfp = fp->ctf_parent;
+
+  /* No linker-reported symbols at all: ctf_link_shuffle_syms was never called.
+     This must be an unsorted, indexed dict.  Otherwise, this is a sorted
+     dict, and the header flags indicate as much.  */
+  if (!symfp->ctf_dynsyms)
+    symflags = CTF_SYMTYPETAB_FORCE_INDEXED;
+  else
+    hdr.cth_flags |= CTF_F_IDXSORTED;
+
+  /* Work out the sizes of the object and function sections, and work out the
+     number of pad (unassigned) symbols in each, and the overall size of the
+     sections.  */
+
+  if (symtypetab_density (fp, symfp, fp->ctf_objthash, &nobjts, &maxobjt,
+			  &objt_unpadsize, &objt_padsize, &objtidx_size,
+			  symflags) < 0)
+    return -1;					/* errno is set for us.  */
+
+  ctf_dprintf ("Object symtypetab: %i objects, max %i, unpadded size %i, "
+	       "%i bytes of pads, index size %i\n", (int) nobjts, (int) maxobjt,
+	       (int) objt_unpadsize, (int) objt_padsize, (int) objtidx_size);
+
+  if (symtypetab_density (fp, symfp, fp->ctf_funchash, &nfuncs, &maxfunc,
+			  &func_unpadsize, &func_padsize, &funcidx_size,
+			  symflags | CTF_SYMTYPETAB_EMIT_FUNCTION) < 0)
+    return -1;					/* errno is set for us.  */
+
+  ctf_dprintf ("Function symtypetab: %i functions, max %i, unpadded size %i, "
+	       "%i bytes of pads, index size %i\n", (int) nfuncs, (int) maxfunc,
+	       (int) func_unpadsize, (int) func_padsize, (int) funcidx_size);
+
+  /* If the linker has reported any symbols at all, those symbols that the
+     linker has not reported are now removed from the ctf_objthash and
+     ctf_funchash.  Delete entries from the variable section that duplicate
+     newly-added data symbols.  There's no need to migrate new ones in, because
+     linker invocations (even ld -r) can only introduce new symbols, not remove
+     symbols that already exist, and the compiler always emits both a variable
+     and a data symbol simultaneously.  */
+
+  if (symtypetab_delete_nonstatic_vars (fp) < 0)
+    return -1;
+
+  /* It is worth indexing each section if it would save space to do so, due to
+     reducing the number of pads sufficiently.  A pad is the same size as a
+     single index entry: but index sections compress relatively poorly compared
+     to constant pads, so it takes a lot of contiguous padding to equal one
+     index section entry.  It would be nice to be able to *verify* whether we
+     would save space after compression rather than guessing, but this seems
+     difficult, since it would require complete reserialization.  Regardless, if
+     the linker has not reported any symbols (e.g. if this is not a final link
+     but just an ld -r), we must emit things in indexed fashion just as the
+     compiler does.  */
+
+  objt_size = objt_unpadsize;
+  if (!(symflags & CTF_SYMTYPETAB_FORCE_INDEXED)
+      && ((objt_padsize + objt_unpadsize) * CTF_INDEX_PAD_THRESHOLD
+	  > objt_padsize))
+    {
+      objt_size += objt_padsize;
+      objtidx_size = 0;
+    }
+
+  func_size = func_unpadsize;
+  if (!(symflags & CTF_SYMTYPETAB_FORCE_INDEXED)
+      && ((func_padsize + func_unpadsize) * CTF_INDEX_PAD_THRESHOLD
+	  > func_padsize))
+    {
+      func_size += func_padsize;
+      funcidx_size = 0;
+    }
+
   /* Computing the number of entries in the CTF variable section is much
      simpler.  */
 
@@ -352,6 +842,11 @@ ctf_serialize (ctf_dict_t *fp)
      then allocate a new buffer and memcpy the finished header to the start of
      the buffer.  (We will adjust this later with strtab length info.)  */
 
+  hdr.cth_lbloff = hdr.cth_objtoff = 0;
+  hdr.cth_funcoff = hdr.cth_objtoff + objt_size;
+  hdr.cth_objtidxoff = hdr.cth_funcoff + func_size;
+  hdr.cth_funcidxoff = hdr.cth_objtidxoff + objtidx_size;
+  hdr.cth_varoff = hdr.cth_funcidxoff + funcidx_size;
   hdr.cth_typeoff = hdr.cth_varoff + (nvars * sizeof (ctf_varent_t));
   hdr.cth_stroff = hdr.cth_typeoff + type_size;
   hdr.cth_strlen = 0;
@@ -362,7 +857,7 @@ ctf_serialize (ctf_dict_t *fp)
     return (ctf_set_errno (fp, EAGAIN));
 
   memcpy (buf, &hdr, sizeof (ctf_header_t));
-  t = (unsigned char *) buf + sizeof (ctf_header_t) + hdr.cth_varoff;
+  t = (unsigned char *) buf + sizeof (ctf_header_t) + hdr.cth_objtoff;
 
   hdrp = (ctf_header_t *) buf;
   if ((fp->ctf_flags & LCTF_CHILD) && (fp->ctf_parname != NULL))
@@ -370,6 +865,114 @@ ctf_serialize (ctf_dict_t *fp)
   if (fp->ctf_cuname != NULL)
     ctf_str_add_ref (fp, fp->ctf_cuname, &hdrp->cth_cuname);
 
+  /* Sort the linker's symbols into name order if need be: if
+     ctf_link_shuffle_syms has not been called at all, just use all the symbols
+     that were added to this dict, and don't bother sorting them since this is
+     probably an ld -r and will likely just be consumed by ld again, with no
+     ctf_lookup_by_symbol()s ever done on it.  */
+
+  if ((objtidx_size != 0) || (funcidx_size != 0))
+    {
+      ctf_next_t *i = NULL;
+      void *symname;
+      const char **walk;
+      int err;
+
+      if (symfp->ctf_dynsyms)
+	ndynsyms = ctf_dynhash_elements (symfp->ctf_dynsyms);
+      else
+	ndynsyms = ctf_dynhash_elements (symfp->ctf_objthash)
+	  + ctf_dynhash_elements (symfp->ctf_funchash);
+
+      if ((sym_name_order = calloc (ndynsyms, sizeof (const char *))) == NULL)
+	goto oom;
+
+      walk = sym_name_order;
+
+      if (symfp->ctf_dynsyms)
+	{
+	  while ((err = ctf_dynhash_next_sorted (symfp->ctf_dynsyms, &i, &symname,
+						 NULL, ctf_dynhash_sort_by_name,
+						 NULL)) == 0)
+	    *walk++ = (const char *) symname;
+	  if (err != ECTF_NEXT_END)
+	    goto symerr;
+	}
+      else
+	{
+	  while ((err = ctf_dynhash_next (symfp->ctf_objthash, &i, &symname,
+					  NULL)) == 0)
+	    *walk++ = (const char *) symname;
+	  if (err != ECTF_NEXT_END)
+	    goto symerr;
+
+	  while ((err = ctf_dynhash_next (symfp->ctf_funchash, &i, &symname,
+					  NULL)) == 0)
+	    *walk++ = (const char *) symname;
+	  if (err != ECTF_NEXT_END)
+	    goto symerr;
+	}
+    }
+
+  /* Emit the object and function sections, and if necessary their indexes.
+     Emission is done in symtab order if there is no index, and in index
+     (name) order otherwise.  */
+
+  if ((objtidx_size == 0) && symfp->ctf_dynsymidx)
+    {
+      ctf_dprintf ("Emitting unindexed objt symtypetab\n");
+      if (emit_symtypetab (fp, symfp, (uint32_t *) t, symfp->ctf_dynsymidx,
+			   NULL, symfp->ctf_dynsymmax + 1, maxobjt, objt_size,
+			   symflags | CTF_SYMTYPETAB_EMIT_PAD) < 0)
+	goto err;				/* errno is set for us.  */
+    }
+  else
+    {
+      ctf_dprintf ("Emitting indexed objt symtypetab\n");
+      if (emit_symtypetab (fp, symfp, (uint32_t *) t, NULL, sym_name_order,
+			   ndynsyms, maxobjt, objt_size, symflags) < 0)
+	goto err;				/* errno is set for us.  */
+    }
+
+  t += objt_size;
+
+  if ((funcidx_size == 0) && symfp->ctf_dynsymidx)
+    {
+      ctf_dprintf ("Emitting unindexed func symtypetab\n");
+      if (emit_symtypetab (fp, symfp, (uint32_t *) t, symfp->ctf_dynsymidx,
+			   NULL, symfp->ctf_dynsymmax + 1, maxfunc,
+			   func_size, symflags | CTF_SYMTYPETAB_EMIT_FUNCTION
+			   | CTF_SYMTYPETAB_EMIT_PAD) < 0)
+	goto err;				/* errno is set for us.  */
+    }
+  else
+    {
+      ctf_dprintf ("Emitting indexed func symtypetab\n");
+      if (emit_symtypetab (fp, symfp, (uint32_t *) t, NULL, sym_name_order,
+			   ndynsyms, maxfunc, func_size,
+			   symflags | CTF_SYMTYPETAB_EMIT_FUNCTION) < 0)
+	goto err;				/* errno is set for us.  */
+    }
+
+  t += func_size;
+
+  if (objtidx_size > 0)
+    if (emit_symtypetab_index (fp, symfp, (uint32_t *) t, sym_name_order,
+			       ndynsyms, objtidx_size, symflags) < 0)
+      goto err;
+
+  t += objtidx_size;
+
+  if (funcidx_size > 0)
+    if (emit_symtypetab_index (fp, symfp, (uint32_t *) t, sym_name_order,
+			       ndynsyms, funcidx_size,
+			       symflags | CTF_SYMTYPETAB_EMIT_FUNCTION) < 0)
+      goto err;
+
+  t += funcidx_size;
+  free (sym_name_order);
+  sym_name_order = NULL;
+
   /* Work over the variable list, translating everything into ctf_varent_t's and
      prepping the string table.  */
 
@@ -486,10 +1089,7 @@ ctf_serialize (ctf_dict_t *fp)
   ctf_str_purge_refs (fp);
 
   if (strtab.cts_strs == NULL)
-    {
-      free (buf);
-      return (ctf_set_errno (fp, EAGAIN));
-    }
+    goto oom;
 
   /* Now the string table is constructed, we can sort the buffer of
      ctf_varent_t's.  */
@@ -499,9 +1099,8 @@ ctf_serialize (ctf_dict_t *fp)
 
   if ((newbuf = ctf_realloc (fp, buf, buf_size + strtab.cts_len)) == NULL)
     {
-      free (buf);
       free (strtab.cts_strs);
-      return (ctf_set_errno (fp, EAGAIN));
+      goto oom;
     }
   buf = newbuf;
   memcpy (buf + buf_size, strtab.cts_strs, strtab.cts_len);
@@ -537,13 +1136,25 @@ ctf_serialize (ctf_dict_t *fp)
   nfp->ctf_add_processing = fp->ctf_add_processing;
   nfp->ctf_snapshots = fp->ctf_snapshots + 1;
   nfp->ctf_specific = fp->ctf_specific;
+  nfp->ctf_nfuncidx = fp->ctf_nfuncidx;
+  nfp->ctf_nobjtidx = fp->ctf_nobjtidx;
+  nfp->ctf_objthash = fp->ctf_objthash;
+  nfp->ctf_funchash = fp->ctf_funchash;
+  nfp->ctf_dynsyms = fp->ctf_dynsyms;
   nfp->ctf_ptrtab = fp->ctf_ptrtab;
+  nfp->ctf_dynsymidx = fp->ctf_dynsymidx;
+  nfp->ctf_dynsymmax = fp->ctf_dynsymmax;
   nfp->ctf_ptrtab_len = fp->ctf_ptrtab_len;
   nfp->ctf_link_inputs = fp->ctf_link_inputs;
   nfp->ctf_link_outputs = fp->ctf_link_outputs;
   nfp->ctf_errs_warnings = fp->ctf_errs_warnings;
+  nfp->ctf_funcidx_names = fp->ctf_funcidx_names;
+  nfp->ctf_objtidx_names = fp->ctf_objtidx_names;
+  nfp->ctf_funcidx_sxlate = fp->ctf_funcidx_sxlate;
+  nfp->ctf_objtidx_sxlate = fp->ctf_objtidx_sxlate;
   nfp->ctf_str_prov_offset = fp->ctf_str_prov_offset;
   nfp->ctf_syn_ext_strtab = fp->ctf_syn_ext_strtab;
+  nfp->ctf_in_flight_dynsyms = fp->ctf_in_flight_dynsyms;
   nfp->ctf_link_in_cu_mapping = fp->ctf_link_in_cu_mapping;
   nfp->ctf_link_out_cu_mapping = fp->ctf_link_out_cu_mapping;
   nfp->ctf_link_type_mapping = fp->ctf_link_type_mapping;
@@ -574,6 +1185,14 @@ ctf_serialize (ctf_dict_t *fp)
   memset (&fp->ctf_errs_warnings, 0, sizeof (ctf_list_t));
   fp->ctf_add_processing = NULL;
   fp->ctf_ptrtab = NULL;
+  fp->ctf_funcidx_names = NULL;
+  fp->ctf_objtidx_names = NULL;
+  fp->ctf_funcidx_sxlate = NULL;
+  fp->ctf_objtidx_sxlate = NULL;
+  fp->ctf_objthash = NULL;
+  fp->ctf_funchash = NULL;
+  fp->ctf_dynsyms = NULL;
+  fp->ctf_dynsymidx = NULL;
   fp->ctf_link_inputs = NULL;
   fp->ctf_link_outputs = NULL;
   fp->ctf_syn_ext_strtab = NULL;
@@ -587,6 +1206,7 @@ ctf_serialize (ctf_dict_t *fp)
   fp->ctf_dvhash = NULL;
   memset (&fp->ctf_dvdefs, 0, sizeof (ctf_list_t));
   memset (fp->ctf_lookups, 0, sizeof (fp->ctf_lookups));
+  memset (&fp->ctf_in_flight_dynsyms, 0, sizeof (fp->ctf_in_flight_dynsyms));
   memset (&fp->ctf_dedup, 0, sizeof (fp->ctf_dedup));
   fp->ctf_structs.ctn_writable = NULL;
   fp->ctf_unions.ctn_writable = NULL;
@@ -597,10 +1217,22 @@ ctf_serialize (ctf_dict_t *fp)
   memcpy (fp, nfp, sizeof (ctf_dict_t));
   memcpy (nfp, &ofp, sizeof (ctf_dict_t));
 
-  nfp->ctf_refcnt = 1;		/* Force nfp to be freed.  */
+  nfp->ctf_refcnt = 1;				/* Force nfp to be freed.  */
   ctf_dict_close (nfp);
 
   return 0;
+
+symerr:
+  ctf_err_warn (fp, 0, err, _("error serializing symtypetabs"));
+  goto err;
+oom:
+  free (buf);
+  free (sym_name_order);
+  return (ctf_set_errno (fp, EAGAIN));
+err:
+  free (buf);
+  free (sym_name_order);
+  return -1;					/* errno is set for us.  */
 }
 
 ctf_names_t *
@@ -1598,6 +2230,49 @@ ctf_add_variable (ctf_dict_t *fp, const char *name, ctf_id_t ref)
   return 0;
 }
 
+int
+ctf_add_funcobjt_sym (ctf_dict_t *fp, int is_function, const char *name, ctf_id_t id)
+{
+  ctf_dict_t *tmp = fp;
+  char *dupname;
+  ctf_dynhash_t *h = is_function ? fp->ctf_funchash : fp->ctf_objthash;
+
+  if (!(fp->ctf_flags & LCTF_RDWR))
+    return (ctf_set_errno (fp, ECTF_RDONLY));
+
+  if (ctf_dynhash_lookup (fp->ctf_objthash, name) != NULL ||
+      ctf_dynhash_lookup (fp->ctf_funchash, name) != NULL)
+    return (ctf_set_errno (fp, ECTF_DUPLICATE));
+
+  if (ctf_lookup_by_id (&tmp, id) == NULL)
+    return -1;                                  /* errno is set for us.  */
+
+  if (is_function && ctf_type_kind (fp, id) != CTF_K_FUNCTION)
+    return (ctf_set_errno (fp, ECTF_NOTFUNC));
+
+  if ((dupname = strdup (name)) == NULL)
+    return (ctf_set_errno (fp, ENOMEM));
+
+  if (ctf_dynhash_insert (h, dupname, (void *) (uintptr_t) id) < 0)
+    {
+      free (dupname);
+      return (ctf_set_errno (fp, ENOMEM));
+    }
+  return 0;
+}
+
+int
+ctf_add_objt_sym (ctf_dict_t *fp, const char *name, ctf_id_t id)
+{
+  return (ctf_add_funcobjt_sym (fp, 0, name, id));
+}
+
+int
+ctf_add_func_sym (ctf_dict_t *fp, const char *name, ctf_id_t id)
+{
+  return (ctf_add_funcobjt_sym (fp, 1, name, id));
+}
+
 typedef struct ctf_bundle
 {
   ctf_dict_t *ctb_dict;		/* CTF dict handle.  */
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index 582f9de..202fad0 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -476,6 +476,13 @@ ctf_dynhash_next (ctf_dynhash_t *h, ctf_next_t **it, void **key, void **value)
   return ECTF_NEXT_END;
 }
 
+int
+ctf_dynhash_sort_by_name (const ctf_next_hkv_t *one, const ctf_next_hkv_t *two,
+			  void *unused _libctf_unused_)
+{
+  return strcmp ((char *) one->hkv_key, (char *) two->hkv_key);
+}
+
 /* Traverse a sorted dynhash, in _next iterator form.
 
    See ctf_dynhash_next for notes on error returns, etc.
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index 0e09a45..62ea360 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -43,6 +43,15 @@ extern "C"
 {
 #endif
 
+/* Tuning.  */
+
+/* The proportion of symtypetab entries which must be pads before we consider it
+   worthwhile to emit a symtypetab section as an index.  Indexes cost time to
+   look up, but save space all told.  Do not set to 1, since this will cause
+   indexes to be eschewed completely, even in child dicts, at considerable space
+   cost.  */
+#define CTF_INDEX_PAD_THRESHOLD .75
+
 /* Compiler attributes.  */
 
 #if defined (__GNUC__)
@@ -61,6 +70,7 @@ extern "C"
 #define _libctf_unlikely_(x) __builtin_expect ((x), 0)
 #define _libctf_unused_ __attribute__ ((__unused__))
 #define _libctf_malloc_ __attribute__((__malloc__))
+#define _libctf_nonnull_ __attribute__((__nonnull__))
 
 #else
 
@@ -68,6 +78,7 @@ extern "C"
 #define _libctf_unlikely_(x) (x)
 #define _libctf_unused_
 #define _libctf_malloc_
+#define _libctf_nonnull_
 #define __extension__
 
 #endif
@@ -232,6 +243,14 @@ typedef struct ctf_str_atom_ref
   uint32_t *caf_ref;		/* A single ref to this string.  */
 } ctf_str_atom_ref_t;
 
+/* A single linker-provided symbol, during symbol addition, possibly before we
+   have been given external strtab refs.  */
+typedef struct ctf_in_flight_dynsym
+{
+  ctf_list_t cid_list;		/* List forward/back pointers.  */
+  ctf_link_sym_t cid_sym;	/* The linker-known symbol.  */
+} ctf_in_flight_dynsym_t;
+
 /* The structure used as the key in a ctf_link_type_mapping.  The value is a
    type index, not a type ID.  */
 
@@ -380,11 +399,28 @@ struct ctf_dict
   unsigned char *ctf_dynbase;	  /* Freeable CTF file pointer. */
   unsigned char *ctf_buf;	  /* Uncompressed CTF data buffer.  */
   size_t ctf_size;		  /* Size of CTF header + uncompressed data.  */
-  uint32_t *ctf_sxlate;		  /* Translation table for symtab entries.  */
+  uint32_t *ctf_sxlate;		  /* Translation table for unindexed symtypetab
+				     entries.  */
   unsigned long ctf_nsyms;	  /* Number of entries in symtab xlate table.  */
   uint32_t *ctf_txlate;		  /* Translation table for type IDs.  */
   uint32_t *ctf_ptrtab;		  /* Translation table for pointer-to lookups.  */
   size_t ctf_ptrtab_len;	  /* Num types storable in ptrtab currently.  */
+  uint32_t *ctf_funcidx_names;	  /* Name of each function symbol in symtypetab
+				     (if indexed).  */
+  uint32_t *ctf_objtidx_names;	  /* Likewise, for object symbols.  */
+  size_t ctf_nfuncidx;		  /* Number of funcidx entries.  */
+  uint32_t *ctf_funcidx_sxlate;	  /* Offsets into funcinfo for a given funcidx.  */
+  uint32_t *ctf_objtidx_sxlate;	  /* Likewise, for ctf_objtidx.  */
+  size_t ctf_nobjtidx;		  /* Number of objtidx entries.  */
+  ctf_dynhash_t *ctf_objthash;	  /* name -> type ID.  */
+  ctf_dynhash_t *ctf_funchash;	  /* name -> CTF_K_FUNCTION type ID.  */
+
+  /* The next three are linker-derived state found in ctf_link targets only.  */
+
+  ctf_dynhash_t *ctf_dynsyms;	  /* Symbol info from ctf_link_shuffle_syms.  */
+  ctf_link_sym_t **ctf_dynsymidx;  /* Indexes ctf_dynsyms by symidx.  */
+  uint32_t ctf_dynsymmax;	  /* Maximum ctf_dynsym index.  */
+  ctf_list_t ctf_in_flight_dynsyms; /* Dynsyms during accumulation.  */
   struct ctf_varent *ctf_vars;	  /* Sorted variable->type mapping.  */
   unsigned long ctf_nvars;	  /* Number of variables in ctf_vars.  */
   unsigned long ctf_typemax;	  /* Maximum valid type ID number.  */
@@ -494,7 +530,10 @@ struct ctf_next
   /* We can save space on this side of things by noting that a dictionary is
      either dynamic or not, as a whole, and a given iterator can only iterate
      over one kind of thing at once: so we can overlap the DTD and non-DTD
-     members, and the structure, variable and enum members, etc.  */
+     members, and the structure, variable and enum members, etc.
+
+     Some of the _next iterators actually thunk down to another _next iterator
+     themselves, so one of the options in here is a _next iterator!  */
   union
   {
     const ctf_member_t *ctn_mp;
@@ -502,6 +541,7 @@ struct ctf_next
     const ctf_dmdef_t *ctn_dmd;
     const ctf_enum_t *ctn_en;
     const ctf_dvdef_t *ctn_dvd;
+    ctf_next_t *ctn_next;
     ctf_next_hkv_t *ctn_sorted_hkv;
     void **ctn_hash_slot;
   } u;
@@ -542,9 +582,9 @@ struct ctf_next
 #define LCTF_VBYTES(fp, kind, size, vlen) \
   ((fp)->ctf_dictops->ctfo_get_vbytes(fp, kind, size, vlen))
 
-#define LCTF_CHILD	0x0001	/* CTF dict is a child */
-#define LCTF_RDWR	0x0002	/* CTF dict is writable */
-#define LCTF_DIRTY	0x0004	/* CTF dict has been modified */
+#define LCTF_CHILD	0x0001	/* CTF dict is a child.  */
+#define LCTF_RDWR	0x0002	/* CTF dict is writable.  */
+#define LCTF_DIRTY	0x0004	/* CTF dict has been modified.  */
 
 extern ctf_names_t *ctf_name_table (ctf_dict_t *, int);
 extern const ctf_type_t *ctf_lookup_by_id (ctf_dict_t **, ctf_id_t);
@@ -552,6 +592,10 @@ extern ctf_id_t ctf_lookup_by_rawname (ctf_dict_t *, int, const char *);
 extern ctf_id_t ctf_lookup_by_rawhash (ctf_dict_t *, ctf_names_t *, const char *);
 extern void ctf_set_ctl_hashes (ctf_dict_t *);
 
+extern int ctf_symtab_skippable (ctf_link_sym_t *sym);
+extern int ctf_add_funcobjt_sym (ctf_dict_t *, int is_function,
+				 const char *, ctf_id_t);
+
 extern ctf_dict_t *ctf_get_dict (ctf_dict_t *fp, ctf_id_t type);
 
 typedef unsigned int (*ctf_hash_fun) (const void *ptr);
@@ -598,6 +642,9 @@ extern void ctf_dynhash_iter_remove (ctf_dynhash_t *, ctf_hash_iter_remove_f,
 				     void *);
 extern void *ctf_dynhash_iter_find (ctf_dynhash_t *, ctf_hash_iter_find_f,
 				    void *);
+extern int ctf_dynhash_sort_by_name (const ctf_next_hkv_t *,
+				     const ctf_next_hkv_t *,
+				     void * _libctf_unused_);
 extern int ctf_dynhash_next (ctf_dynhash_t *, ctf_next_t **,
 			     void **key, void **value);
 extern int ctf_dynhash_next_sorted (ctf_dynhash_t *, ctf_next_t **,
@@ -721,7 +768,10 @@ extern void ctf_assert_fail_internal (ctf_dict_t *, const char *,
 				      size_t, const char *);
 extern const char *ctf_link_input_name (ctf_dict_t *);
 
-extern Elf64_Sym *ctf_sym_to_elf64 (const Elf32_Sym *src, Elf64_Sym *dst);
+extern ctf_link_sym_t *ctf_elf32_to_link_sym (ctf_dict_t *fp, ctf_link_sym_t *dst,
+					      const Elf32_Sym *src, uint32_t symidx);
+extern ctf_link_sym_t *ctf_elf64_to_link_sym (ctf_dict_t *fp, ctf_link_sym_t *dst,
+					      const Elf64_Sym *src, uint32_t symidx);
 extern const char *ctf_lookup_symbol_name (ctf_dict_t *fp, unsigned long symidx);
 
 /* Variables, all underscore-prepended. */
diff --git a/libctf/ctf-link.c b/libctf/ctf-link.c
index 3f4f2ee..4b86ca9 100644
--- a/libctf/ctf-link.c
+++ b/libctf/ctf-link.c
@@ -51,10 +51,6 @@ ctf_add_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type,
 
   dst_type = LCTF_TYPE_TO_INDEX(dst_fp, dst_type);
 
-  /* This dynhash is a bit tricky: it has a multivalued (structural) key, so we
-     need to use the sized-hash machinery to generate key hashing and equality
-     functions.  */
-
   if (dst_fp->ctf_link_type_mapping == NULL)
     {
       ctf_hash_fun f = ctf_hash_type_key;
@@ -574,7 +570,7 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
   ctf_link_in_member_cb_arg_t *arg = (ctf_link_in_member_cb_arg_t *) arg_;
   ctf_dict_t *per_cu_out_fp;
   ctf_id_t dst_type = 0;
-  ctf_dict_t *check_fp;
+  ctf_dict_t *insert_fp;
   ctf_dvdef_t *dvd;
 
   /* See if this variable is filtered out.  */
@@ -590,18 +586,18 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
      dict, we want to try to add to that first: if it reports a duplicate,
      or if the type is in a child already, add straight to the child.  */
 
-  check_fp = arg->out_fp;
+  insert_fp = arg->out_fp;
 
-  dst_type = ctf_type_mapping (arg->in_fp, type, &check_fp);
+  dst_type = ctf_type_mapping (arg->in_fp, type, &insert_fp);
   if (dst_type != 0)
     {
-      if (check_fp == arg->out_fp)
+      if (insert_fp == arg->out_fp)
 	{
-	  if (check_variable (name, check_fp, dst_type, &dvd))
+	  if (check_variable (name, insert_fp, dst_type, &dvd))
 	    {
 	      /* No variable here: we can add it.  */
-	      if (ctf_add_variable (check_fp, name, dst_type) < 0)
-		return (ctf_set_errno (arg->out_fp, ctf_errno (check_fp)));
+	      if (ctf_add_variable (insert_fp, name, dst_type) < 0)
+		return (ctf_set_errno (arg->out_fp, ctf_errno (insert_fp)));
 	      return 0;
 	    }
 
@@ -628,11 +624,11 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
 					  arg->cu_name)) == NULL)
     return -1;					/* Errno is set for us.  */
 
-  /* If the type was not found, check for it in the child too. */
+  /* If the type was not found, check for it in the child too.  */
   if (dst_type == 0)
     {
-      check_fp = per_cu_out_fp;
-      dst_type = ctf_type_mapping (arg->in_fp, type, &check_fp);
+      insert_fp = per_cu_out_fp;
+      dst_type = ctf_type_mapping (arg->in_fp, type, &insert_fp);
 
       if (dst_type == 0)
 	{
@@ -1153,6 +1149,169 @@ ctf_link_deduplicating_variables (ctf_dict_t *fp, ctf_dict_t **inputs,
   return 0;
 }
 
+/* Check for symbol conflicts during linking.  Three possibilities: already
+   exists, conflicting, or nonexistent.  We don't have a dvd structure we can
+   use as a flag like check_variable does, so we use a tristate return
+   value instead: -1: conflicting; 1: nonexistent: 0: already exists.  */
+
+static int
+check_sym (ctf_dict_t *fp, const char *name, ctf_id_t type, int functions)
+{
+  ctf_dynhash_t *thishash = functions ? fp->ctf_funchash : fp->ctf_objthash;
+  ctf_dynhash_t *thathash = functions ? fp->ctf_objthash : fp->ctf_funchash;
+  void *value;
+
+  /* Wrong type (function when object is wanted, etc).  */
+  if (ctf_dynhash_lookup_kv (thathash, name, NULL, NULL))
+    return -1;
+
+  /* Not present at all yet.  */
+  if (!ctf_dynhash_lookup_kv (thishash, name, NULL, &value))
+    return 1;
+
+  /* Already present.  */
+  if ((ctf_id_t) (uintptr_t) value == type)
+    return 0;
+
+  /* Wrong type.  */
+  return -1;
+}
+
+/* Do a deduplicating link of one symtypetab (function info or data object) in
+   one input dict.  */
+
+static int
+ctf_link_deduplicating_one_symtypetab (ctf_dict_t *fp, ctf_dict_t *input,
+				       int cu_mapped, int functions)
+{
+  ctf_next_t *it = NULL;
+  const char *name;
+  ctf_id_t type;
+  const char *in_file_name;
+
+  if (ctf_cuname (input) != NULL)
+    in_file_name = ctf_cuname (input);
+  else
+    in_file_name = "unnamed-CU";
+
+  while ((type = ctf_symbol_next (input, &it, &name, functions)) != CTF_ERR)
+    {
+      ctf_id_t dst_type;
+      ctf_dict_t *per_cu_out_fp;
+      ctf_dict_t *insert_fp = fp;
+      int sym;
+
+      /* Look in the parent first.  */
+
+      dst_type = ctf_type_mapping (input, type, &insert_fp);
+      if (dst_type != 0)
+	{
+	  if (insert_fp == fp)
+	    {
+	      sym = check_sym (fp, name, dst_type, functions);
+
+	      /* Already present: next symbol.  */
+	      if (sym == 0)
+		continue;
+	      /* Not present: add it.  */
+	      else if (sym > 0)
+		{
+		  if (ctf_add_funcobjt_sym (fp, functions,
+					    name, dst_type) < 0)
+		    return -1; 			/* errno is set for us.  */
+		  continue;
+		}
+	    }
+	}
+
+      /* Can't add to the parent due to a name clash (most unlikely), or because
+	 it references a type only present in the child.  Try adding to the
+	 child, creating if need be.  If we can't do that, skip it.  Don't add
+	 to a child if we're doing a CU-mapped link, since that has only one
+	 output.  */
+      if (cu_mapped)
+	{
+	  ctf_dprintf ("Symbol %s in input file %s depends on a type %lx "
+		       "hidden due to conflicts: skipped.\n", name,
+		       in_file_name, type);
+	  continue;
+	}
+
+      if ((per_cu_out_fp = ctf_create_per_cu (fp, in_file_name,
+					      in_file_name)) == NULL)
+	return -1;				/* errno is set for us.  */
+
+      /* If the type was not found, check for it in the child too.  */
+      if (dst_type == 0)
+	{
+	  insert_fp = per_cu_out_fp;
+	  dst_type = ctf_type_mapping (input, type, &insert_fp);
+
+	  if (dst_type == 0)
+	    {
+	      ctf_err_warn (fp, 1, 0,
+			    _("type %lx for symbol %s in input file %s "
+			      "not found: skipped"), type, name, in_file_name);
+	      continue;
+	    }
+	}
+
+      sym = check_sym (per_cu_out_fp, name, dst_type, functions);
+
+      /* Already present: next symbol.  */
+      if (sym == 0)
+	continue;
+      /* Not present: add it.  */
+      else if (sym > 0)
+	{
+	  if (ctf_add_funcobjt_sym (per_cu_out_fp, functions,
+				    name, dst_type) < 0)
+	    return -1;				/* errno is set for us.  */
+	}
+      else
+	{
+	  /* Perhaps this should be an assertion failure.  */
+	  ctf_err_warn (fp, 0, ECTF_DUPLICATE,
+			_("symbol %s in input file %s found conflicting "
+			  "even when trying in per-CU dict."), name,
+			in_file_name);
+	  return (ctf_set_errno (fp, ECTF_DUPLICATE));
+	}
+    }
+  if (ctf_errno (input) != ECTF_NEXT_END)
+    {
+      ctf_set_errno (fp, ctf_errno (input));
+      ctf_err_warn (fp, 0, ctf_errno (input),
+		    functions ? _("iterating over function symbols") :
+		    _("iterating over data symbols"));
+      return -1;
+    }
+
+  return 0;
+}
+
+/* Do a deduplicating link of the function info and data objects
+   in the inputs.  */
+static int
+ctf_link_deduplicating_syms (ctf_dict_t *fp, ctf_dict_t **inputs,
+			     size_t ninputs, int cu_mapped)
+{
+  size_t i;
+
+  for (i = 0; i < ninputs; i++)
+    {
+      if (ctf_link_deduplicating_one_symtypetab (fp, inputs[i],
+						 cu_mapped, 0) < 0)
+	return -1;				/* errno is set for us.  */
+
+      if (ctf_link_deduplicating_one_symtypetab (fp, inputs[i],
+						 cu_mapped, 1) < 0)
+	return -1;				/* errno is set for us.  */
+    }
+
+  return 0;
+}
+
 /* Do the per-CU part of a deduplicating link.  */
 static int
 ctf_link_deduplicating_per_cu (ctf_dict_t *fp)
@@ -1305,6 +1464,11 @@ ctf_link_deduplicating_per_cu (ctf_dict_t *fp)
 	  goto err_inputs_outputs;
 	}
 
+      /* For now, we omit symbol section linking for CU-mapped links, until it
+	 is clear how to unify the symbol table across such links.  (Perhaps we
+	 should emit an unconditionally indexed symtab, like the compiler
+	 does.)  */
+
       if (ctf_link_deduplicating_close_inputs (fp, in, inputs, ninputs) < 0)
 	{
 	  free (inputs);
@@ -1457,6 +1621,15 @@ ctf_link_deduplicating (ctf_dict_t *fp)
       goto err;
     }
 
+  if (ctf_link_deduplicating_syms (fp, inputs, ninputs, 0) < 0)
+    {
+      ctf_err_warn (fp, 0, 0, _("deduplicating link symbol emission failed for "
+				"%s"), ctf_link_input_name (fp));
+      for (i = 1; i < noutputs; i++)
+	ctf_dict_close (outputs[i]);
+      goto err;
+    }
+
   /* Now close all the inputs, including per-CU intermediates.  */
 
   if (ctf_link_deduplicating_close_inputs (fp, NULL, inputs, ninputs) < 0)
@@ -1591,19 +1764,162 @@ ctf_link_add_strtab (ctf_dict_t *fp, ctf_link_strtab_string_f *add_string,
 	err = iter_arg.err;
     }
 
+  if (err)
+    ctf_set_errno (fp, err);
+
   return -err;
 }
 
-/* Not yet implemented.  */
+/* Inform the ctf-link machinery of a new symbol in the target symbol table
+   (which must be some symtab that is not usually stripped, and which
+   is in agreement with ctf_bfdopen_ctfsect).  May be called either before or
+   after ctf_link_add_strtab.  */
 int
 ctf_link_add_linker_symbol (ctf_dict_t *fp, ctf_link_sym_t *sym)
 {
+  ctf_in_flight_dynsym_t *cid;
+
+  /* Cheat a little: if there is already an ENOMEM error code recorded against
+     this dict, we shouldn't even try to add symbols because there will be no
+     memory to do so: probably we failed to add some previous symbol.  This
+     makes out-of-memory exits 'sticky' across calls to this function, so the
+     caller doesn't need to worry about error conditions.  */
+
+  if (ctf_errno (fp) == ENOMEM)
+    return -ENOMEM;				/* errno is set for us.  */
+
+  if (ctf_symtab_skippable (sym))
+    return 0;
+
+  if (sym->st_type != STT_OBJECT && sym->st_type != STT_FUNC)
+    return 0;
+
+  /* Add the symbol to the in-flight list.  */
+
+  if ((cid = malloc (sizeof (ctf_in_flight_dynsym_t))) == NULL)
+    goto oom;
+
+  cid->cid_sym = *sym;
+  ctf_list_append (&fp->ctf_in_flight_dynsyms, cid);
+
   return 0;
+
+ oom:
+  ctf_dynhash_destroy (fp->ctf_dynsyms);
+  fp->ctf_dynsyms = NULL;
+  ctf_set_errno (fp, ENOMEM);
+  return -ENOMEM;
 }
+
+/* Impose an ordering on symbols.  The ordering takes effect immediately, but
+   since the ordering info does not include type IDs, lookups may return nothing
+   until such IDs are added by calls to ctf_add_*_sym.  Must be called after
+   ctf_link_add_strtab and ctf_link_add_linker_symbol.  */
 int
 ctf_link_shuffle_syms (ctf_dict_t *fp)
 {
+  ctf_in_flight_dynsym_t *did, *nid;
+  ctf_next_t *i = NULL;
+  int err = ENOMEM;
+  void *name_, *sym_;
+
+  if (!fp->ctf_dynsyms)
+    {
+      fp->ctf_dynsyms = ctf_dynhash_create (ctf_hash_string,
+					    ctf_hash_eq_string,
+					    NULL, free);
+      if (!fp->ctf_dynsyms)
+	{
+	  ctf_set_errno (fp, ENOMEM);
+	  return -ENOMEM;
+	}
+    }
+
+  /* Add all the symbols, excluding only those we already know are prohibited
+     from appearing in symtypetabs.  */
+
+  for (did = ctf_list_next (&fp->ctf_in_flight_dynsyms); did != NULL; did = nid)
+    {
+      ctf_link_sym_t *new_sym;
+
+      nid = ctf_list_next (did);
+      ctf_list_delete (&fp->ctf_in_flight_dynsyms, did);
+
+      /* We might get a name or an external strtab offset.  The strtab offset is
+	 guaranteed resolvable at this point, so turn it into a string.  */
+
+      if (did->cid_sym.st_name == NULL)
+	{
+	  uint32_t off = CTF_SET_STID (did->cid_sym.st_nameidx, CTF_STRTAB_1);
+
+	  did->cid_sym.st_name = ctf_strraw (fp, off);
+	  did->cid_sym.st_nameidx_set = 0;
+	  if (!ctf_assert (fp, did->cid_sym.st_name != NULL))
+	    return -ECTF_INTERNAL;		/* errno is set for us.  */
+	}
+
+      /* The symbol might have turned out to be nameless, so we have to recheck
+	 for skippability here.  */
+      if (!ctf_symtab_skippable (&did->cid_sym))
+	{
+	  ctf_dprintf ("symbol name from linker: %s\n", did->cid_sym.st_name);
+
+	  if ((new_sym = malloc (sizeof (ctf_link_sym_t))) == NULL)
+	    goto local_oom;
+
+	  memcpy (new_sym, &did->cid_sym, sizeof (ctf_link_sym_t));
+	  if (ctf_dynhash_cinsert (fp->ctf_dynsyms, new_sym->st_name, new_sym) < 0)
+	    goto local_oom;
+
+	  if (fp->ctf_dynsymmax < new_sym->st_symidx)
+	    fp->ctf_dynsymmax = new_sym->st_symidx;
+	}
+
+      free (did);
+      continue;
+
+    local_oom:
+      free (did);
+      free (new_sym);
+      goto err;
+    }
+
+  /* Construct a mapping from shndx to the symbol info.  */
+  free (fp->ctf_dynsymidx);
+  if ((fp->ctf_dynsymidx = calloc (fp->ctf_dynsymmax + 1,
+				   sizeof (ctf_link_sym_t *))) == NULL)
+    goto err;
+
+  while ((err = ctf_dynhash_next (fp->ctf_dynsyms, &i, &name_, &sym_)) == 0)
+    {
+      const char *name = (const char *) name;
+      ctf_link_sym_t *symp = (ctf_link_sym_t *) sym_;
+
+      if (!ctf_assert (fp, symp->st_symidx <= fp->ctf_dynsymmax))
+	{
+	  ctf_next_destroy (i);
+	  err = ctf_errno (fp);
+	  goto err;
+	}
+      fp->ctf_dynsymidx[symp->st_symidx] = symp;
+    }
+  if (err != ECTF_NEXT_END)
+    {
+      ctf_err_warn (fp, 0, err, _("error iterating over shuffled symbols"));
+      goto err;
+    }
   return 0;
+
+ err:
+  /* Leave the in-flight symbols around: they'll be freed at
+     dict close time regardless.  */
+  ctf_dynhash_destroy (fp->ctf_dynsyms);
+  fp->ctf_dynsyms = NULL;
+  free (fp->ctf_dynsymidx);
+  fp->ctf_dynsymidx = NULL;
+  fp->ctf_dynsymmax = 0;
+  ctf_set_errno (fp, err);
+  return -err;
 }
 
 typedef struct ctf_name_list_accum_cb_arg
diff --git a/libctf/ctf-lookup.c b/libctf/ctf-lookup.c
index 5682bf0..a862b40 100644
--- a/libctf/ctf-lookup.c
+++ b/libctf/ctf-lookup.c
@@ -20,6 +20,7 @@
 #include <ctf-impl.h>
 #include <elf.h>
 #include <string.h>
+#include <assert.h>
 
 /* Compare the given input string and length against a table of known C storage
    qualifier keywords.  We just ignore these in ctf_lookup_by_name, below.  To
@@ -192,21 +193,66 @@ err:
   return CTF_ERR;
 }
 
-typedef struct ctf_lookup_var_key
+/* Return the pointer to the internal CTF type data corresponding to the
+   given type ID.  If the ID is invalid, the function returns NULL.
+   This function is not exported outside of the library.  */
+
+const ctf_type_t *
+ctf_lookup_by_id (ctf_dict_t **fpp, ctf_id_t type)
 {
-  ctf_dict_t *clvk_fp;
-  const char *clvk_name;
-} ctf_lookup_var_key_t;
+  ctf_dict_t *fp = *fpp;	/* Caller passes in starting CTF dict.  */
+  ctf_id_t idx;
+
+  if ((fp = ctf_get_dict (fp, type)) == NULL)
+    {
+      (void) ctf_set_errno (*fpp, ECTF_NOPARENT);
+      return NULL;
+    }
+
+  /* If this dict is writable, check for a dynamic type.  */
+
+  if (fp->ctf_flags & LCTF_RDWR)
+    {
+      ctf_dtdef_t *dtd;
+
+      if ((dtd = ctf_dynamic_type (fp, type)) != NULL)
+	{
+	  *fpp = fp;
+	  return &dtd->dtd_data;
+	}
+      (void) ctf_set_errno (*fpp, ECTF_BADID);
+      return NULL;
+    }
+
+  /* Check for a type in the static portion.  */
+
+  idx = LCTF_TYPE_TO_INDEX (fp, type);
+  if (idx > 0 && (unsigned long) idx <= fp->ctf_typemax)
+    {
+      *fpp = fp;		/* Function returns ending CTF dict.  */
+      return (LCTF_INDEX_TO_TYPEPTR (fp, idx));
+    }
+
+  (void) ctf_set_errno (*fpp, ECTF_BADID);
+  return NULL;
+}
+
+typedef struct ctf_lookup_idx_key
+{
+  ctf_dict_t *clik_fp;
+  const char *clik_name;
+  uint32_t *clik_names;
+} ctf_lookup_idx_key_t;
 
 /* A bsearch function for variable names.  */
 
 static int
-ctf_lookup_var (const void *key_, const void *memb_)
+ctf_lookup_var (const void *key_, const void *lookup_)
 {
-  const ctf_lookup_var_key_t *key = key_;
-  const ctf_varent_t *memb = memb_;
+  const ctf_lookup_idx_key_t *key = key_;
+  const ctf_varent_t *lookup = lookup_;
 
-  return (strcmp (key->clvk_name, ctf_strptr (key->clvk_fp, memb->ctv_name)));
+  return (strcmp (key->clik_name, ctf_strptr (key->clik_fp, lookup->ctv_name)));
 }
 
 /* Given a variable name, return the type of the variable with that name.  */
@@ -215,7 +261,7 @@ ctf_id_t
 ctf_lookup_variable (ctf_dict_t *fp, const char *name)
 {
   ctf_varent_t *ent;
-  ctf_lookup_var_key_t key = { fp, name };
+  ctf_lookup_idx_key_t key = { fp, name, NULL };
 
   /* This array is sorted, so we can bsearch for it.  */
 
@@ -233,189 +279,457 @@ ctf_lookup_variable (ctf_dict_t *fp, const char *name)
   return ent->ctv_type;
 }
 
-/* Given a symbol table index, return the name of that symbol from the secondary
-   string table, or the null string (never NULL).  */
+typedef struct ctf_symidx_sort_arg_cb
+{
+  ctf_dict_t *fp;
+  uint32_t *names;
+} ctf_symidx_sort_arg_cb_t;
+
+static int
+sort_symidx_by_name (const void *one_, const void *two_, void *arg_)
+{
+  const uint32_t *one = one_;
+  const uint32_t *two = two_;
+  ctf_symidx_sort_arg_cb_t *arg = arg_;
+
+  return (strcmp (ctf_strptr (arg->fp, arg->names[*one]),
+		  ctf_strptr (arg->fp, arg->names[*two])));
+}
+
+/* Sort a symbol index section by name.  Takes a 1:1 mapping of names to the
+   corresponding symbol table.  Returns a lexicographically sorted array of idx
+   indexes (and thus, of indexes into the corresponding func info / data object
+   section).  */
+
+static uint32_t *
+ctf_symidx_sort (ctf_dict_t *fp, uint32_t *idx, size_t *nidx,
+			 size_t len)
+{
+  uint32_t *sorted;
+  size_t i;
+
+  if ((sorted = malloc (len)) == NULL)
+    {
+      ctf_set_errno (fp, ENOMEM);
+      return NULL;
+    }
+
+  *nidx = len / sizeof (uint32_t);
+  for (i = 0; i < *nidx; i++)
+    sorted[i] = i;
+
+  if (!(fp->ctf_header->cth_flags & CTF_F_IDXSORTED))
+    {
+      ctf_symidx_sort_arg_cb_t arg = { fp, idx };
+      ctf_dprintf ("Index section unsorted: sorting.");
+      ctf_qsort_r (sorted, *nidx, sizeof (uint32_t), sort_symidx_by_name, &arg);
+      fp->ctf_header->cth_flags |= CTF_F_IDXSORTED;
+    }
+
+  return sorted;
+}
+
+/* Given a symbol index, return the name of that symbol from the table provided
+   by ctf_link_shuffle_syms, or failing that from the secondary string table, or
+   the null string.  */
 const char *
 ctf_lookup_symbol_name (ctf_dict_t *fp, unsigned long symidx)
 {
   const ctf_sect_t *sp = &fp->ctf_symtab;
-  Elf64_Sym sym, *gsp;
+  ctf_link_sym_t sym;
+  int err;
 
-  if (sp->cts_data == NULL)
+  if (fp->ctf_dynsymidx)
     {
-      ctf_set_errno (fp, ECTF_NOSYMTAB);
-      return _CTF_NULLSTR;
+      err = EINVAL;
+      if (symidx > fp->ctf_dynsymmax)
+	goto try_parent;
+
+      ctf_link_sym_t *symp = fp->ctf_dynsymidx[symidx];
+
+      if (!symp)
+	goto try_parent;
+
+      return symp->st_name;
     }
 
+  err = ECTF_NOSYMTAB;
+  if (sp->cts_data == NULL)
+    goto try_parent;
+
   if (symidx >= fp->ctf_nsyms)
+    goto try_parent;
+
+  switch (sp->cts_entsize)
     {
-      ctf_set_errno (fp, EINVAL);
+    case sizeof (Elf64_Sym):
+      {
+	const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
+	ctf_elf64_to_link_sym (fp, &sym, symp, symidx);
+      }
+      break;
+    case sizeof (Elf32_Sym):
+      {
+	const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
+	ctf_elf32_to_link_sym (fp, &sym, symp, symidx);
+      }
+      break;
+    default:
+      ctf_set_errno (fp, ECTF_SYMTAB);
       return _CTF_NULLSTR;
     }
 
-  if (sp->cts_entsize == sizeof (Elf32_Sym))
-    {
-      const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
-      gsp = ctf_sym_to_elf64 (symp, &sym);
-    }
-  else
-      gsp = (Elf64_Sym *) sp->cts_data + symidx;
+  assert (!sym.st_nameidx_set);
 
-  if (gsp->st_name < fp->ctf_str[CTF_STRTAB_1].cts_len)
-    return (const char *) fp->ctf_str[CTF_STRTAB_1].cts_strs + gsp->st_name;
+  return sym.st_name;
 
-  return _CTF_NULLSTR;
+ try_parent:
+  if (fp->ctf_parent)
+    return ctf_lookup_symbol_name (fp->ctf_parent, symidx);
+  else
+    {
+      ctf_set_errno (fp, err);
+      return _CTF_NULLSTR;
+    }
 }
 
-/* Given a symbol table index, return the type of the data object described
-   by the corresponding entry in the symbol table.  */
+/* Iterate over all symbols with types: if FUNC, function symbols, otherwise,
+   data symbols.  The name argument is not optional.  The return order is
+   arbitrary, though is likely to be in symbol index or name order.  You can
+   change the value of 'functions' in the middle of iteration over non-dynamic
+   dicts, but doing so on dynamic dicts will fail.  (This is probably not very
+   useful, but there is no reason to prohibit it.)  */
 
 ctf_id_t
-ctf_lookup_by_symbol (ctf_dict_t *fp, unsigned long symidx)
+ctf_symbol_next (ctf_dict_t *fp, ctf_next_t **it, const char **name,
+		 int functions)
 {
-  const ctf_sect_t *sp = &fp->ctf_symtab;
-  ctf_id_t type;
+  ctf_id_t sym;
+  ctf_next_t *i = *it;
+  int err;
 
-  if (sp->cts_data == NULL)
-    return (ctf_set_errno (fp, ECTF_NOSYMTAB));
+  if (!i)
+    {
+      if ((i = ctf_next_create ()) == NULL)
+	return ctf_set_errno (fp, ENOMEM);
 
-  if (symidx >= fp->ctf_nsyms)
-    return (ctf_set_errno (fp, EINVAL));
+      i->cu.ctn_fp = fp;
+      i->ctn_iter_fun = (void (*) (void)) ctf_symbol_next;
+      i->ctn_n = 0;
+      *it = i;
+    }
+
+  if ((void (*) (void)) ctf_symbol_next != i->ctn_iter_fun)
+    return (ctf_set_errno (fp, ECTF_NEXT_WRONGFUN));
 
-  if (sp->cts_entsize == sizeof (Elf32_Sym))
+  if (fp != i->cu.ctn_fp)
+    return (ctf_set_errno (fp, ECTF_NEXT_WRONGFP));
+
+  /* We intentionally use raw access, not ctf_lookup_by_symbol, to avoid
+     incurring additional sorting cost for unsorted symtypetabs coming from the
+     compiler, to allow ctf_symbol_next to work in the absence of a symtab, and
+     finally because it's easier to work out what the name of each symbol is if
+     we do that.  */
+
+  if (fp->ctf_flags & LCTF_RDWR)
     {
-      const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
-      if (ELF32_ST_TYPE (symp->st_info) != STT_OBJECT)
-	return (ctf_set_errno (fp, ECTF_NOTDATA));
+      ctf_dynhash_t *dynh = functions ? fp->ctf_funchash : fp->ctf_objthash;
+      void *dyn_name = NULL, *dyn_value = NULL;
+
+      if (!dynh)
+	{
+	  ctf_next_destroy (i);
+	  return (ctf_set_errno (fp, ECTF_NEXT_END));
+	}
+
+      err = ctf_dynhash_next (dynh, &i->u.ctn_next, &dyn_name, &dyn_value);
+      /* This covers errors and also end-of-iteration.  */
+      if (err != 0)
+	{
+	  ctf_next_destroy (i);
+	  *it = NULL;
+	  return ctf_set_errno (fp, err);
+	}
+
+      *name = dyn_name;
+      sym = (ctf_id_t) (uintptr_t) dyn_value;
     }
-  else
+  else if ((!functions && fp->ctf_objtidx_names) ||
+	   (functions && fp->ctf_funcidx_names))
     {
-      const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
-      if (ELF64_ST_TYPE (symp->st_info) != STT_OBJECT)
-	return (ctf_set_errno (fp, ECTF_NOTDATA));
+      ctf_header_t *hp = fp->ctf_header;
+      uint32_t *idx = functions ? fp->ctf_funcidx_names : fp->ctf_objtidx_names;
+      uint32_t *tab;
+      size_t len;
+
+      if (functions)
+	{
+	  len = (hp->cth_varoff - hp->cth_funcidxoff) / sizeof (uint32_t);
+	  tab = (uint32_t *) (fp->ctf_buf + hp->cth_funcoff);
+	}
+      else
+	{
+	  len = (hp->cth_funcidxoff - hp->cth_objtidxoff) / sizeof (uint32_t);
+	  tab = (uint32_t *) (fp->ctf_buf + hp->cth_objtoff);
+	}
+
+      do
+	{
+	  if (i->ctn_n >= len)
+	    goto end;
+
+	  *name = ctf_strptr (fp, idx[i->ctn_n]);
+	  sym = tab[i->ctn_n++];
+	} while (sym == -1u || sym == 0);
     }
+  else
+    {
+      /* Skip over pads in ctf_xslate, padding for typeless symbols in the
+	 symtypetab itself, and symbols in the wrong table.  */
+      for (; i->ctn_n < fp->ctf_nsyms; i->ctn_n++)
+	{
+	  ctf_header_t *hp = fp->ctf_header;
 
-  if (fp->ctf_sxlate[symidx] == -1u)
-    return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
+	  if (fp->ctf_sxlate[i->ctn_n] == -1u)
+	    continue;
 
-  type = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
-  if (type == 0)
-    return (ctf_set_errno (fp, ECTF_NOTYPEDAT));
+	  sym = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[i->ctn_n]);
 
-  return type;
+	  if (sym == 0)
+	    continue;
+
+	  if (functions)
+	    {
+	      if (fp->ctf_sxlate[i->ctn_n] >= hp->cth_funcoff
+		  && fp->ctf_sxlate[i->ctn_n] < hp->cth_objtidxoff)
+		break;
+	    }
+	  else
+	    {
+	      if (fp->ctf_sxlate[i->ctn_n] >= hp->cth_objtoff
+		  && fp->ctf_sxlate[i->ctn_n] < hp->cth_funcoff)
+		break;
+	    }
+	}
+
+      if (i->ctn_n >= fp->ctf_nsyms)
+	goto end;
+
+      *name = ctf_lookup_symbol_name (fp, i->ctn_n++);
+    }
+
+  return sym;
+
+ end:
+  ctf_next_destroy (i);
+  *it = NULL;
+  return (ctf_set_errno (fp, ECTF_NEXT_END));
 }
 
-/* Return the native dict of a given type: if called on a child and the
-   type is in the parent, return the parent.  Needed if you plan to access
-   the type directly, without using the API.  */
-ctf_dict_t *
-ctf_get_dict (ctf_dict_t *fp, ctf_id_t type)
+/* A bsearch function for function and object index names.  */
+
+static int
+ctf_lookup_idx_name (const void *key_, const void *idx_)
 {
-    if ((fp->ctf_flags & LCTF_CHILD) && LCTF_TYPE_ISPARENT (fp, type))
-      return fp->ctf_parent;
+  const ctf_lookup_idx_key_t *key = key_;
+  const uint32_t *idx = idx_;
 
-    return fp;
+  return (strcmp (key->clik_name, ctf_strptr (key->clik_fp, key->clik_names[*idx])));
 }
 
-/* Return the pointer to the internal CTF type data corresponding to the
-   given type ID.  If the ID is invalid, the function returns NULL.
-   This function is not exported outside of the library.  */
+/* Given a symbol number, look up that symbol in the function or object
+   index table (which must exist).  Return 0 if not found there (or pad).  */
 
-const ctf_type_t *
-ctf_lookup_by_id (ctf_dict_t **fpp, ctf_id_t type)
+static ctf_id_t
+ctf_try_lookup_indexed (ctf_dict_t *fp, unsigned long symidx, int is_function)
 {
-  ctf_dict_t *fp = *fpp;	/* Caller passes in starting CTF dict.  */
-  ctf_id_t idx;
+  const char *symname = ctf_lookup_symbol_name (fp, symidx);
+  struct ctf_header *hp = fp->ctf_header;
+  uint32_t *symtypetab;
+  uint32_t *names;
+  uint32_t *sxlate;
+  size_t nidx;
 
-  if ((fp = ctf_get_dict (fp, type)) == NULL)
-    {
-      (void) ctf_set_errno (*fpp, ECTF_NOPARENT);
-      return NULL;
-    }
+  ctf_dprintf ("Looking up type of object with symtab idx %lx (%s) in "
+	       "indexed symtypetab\n", symidx, symname);
 
-  /* If this dict is writable, check for a dynamic type.  */
+  if (symname[0] == '\0')
+    return -1;					/* errno is set for us.  */
 
-  if (fp->ctf_flags & LCTF_RDWR)
+  if (is_function)
     {
-      ctf_dtdef_t *dtd;
-
-      if ((dtd = ctf_dynamic_type (fp, type)) != NULL)
+      if (!fp->ctf_funcidx_sxlate)
 	{
-	  *fpp = fp;
-	  return &dtd->dtd_data;
+	  if ((fp->ctf_funcidx_sxlate
+	       = ctf_symidx_sort (fp, (uint32_t *)
+				  (fp->ctf_buf + hp->cth_funcidxoff),
+				  &fp->ctf_nfuncidx,
+				  hp->cth_varoff - hp->cth_funcidxoff))
+	      == NULL)
+	    {
+	      ctf_err_warn (fp, 0, 0, _("cannot sort function symidx"));
+	      return -1;				/* errno is set for us.  */
+	    }
 	}
-      (void) ctf_set_errno (*fpp, ECTF_BADID);
-      return NULL;
+      symtypetab = (uint32_t *) (fp->ctf_buf + hp->cth_funcoff);
+      sxlate = fp->ctf_funcidx_sxlate;
+      names = fp->ctf_funcidx_names;
+      nidx = fp->ctf_nfuncidx;
     }
+  else
+    {
+      if (!fp->ctf_objtidx_sxlate)
+	{
+	  if ((fp->ctf_objtidx_sxlate
+	       = ctf_symidx_sort (fp, (uint32_t *)
+				  (fp->ctf_buf + hp->cth_objtidxoff),
+				  &fp->ctf_nobjtidx,
+				  hp->cth_funcidxoff - hp->cth_objtidxoff))
+	      == NULL)
+	    {
+	      ctf_err_warn (fp, 0, 0, _("cannot sort object symidx"));
+	      return -1;				/* errno is set for us. */
+	    }
+	}
 
-  /* Check for a type in the static portion.  */
+      symtypetab = (uint32_t *) (fp->ctf_buf + hp->cth_objtoff);
+      sxlate = fp->ctf_objtidx_sxlate;
+      names = fp->ctf_objtidx_names;
+      nidx = fp->ctf_nobjtidx;
+    }
 
-  idx = LCTF_TYPE_TO_INDEX (fp, type);
-  if (idx > 0 && (unsigned long) idx <= fp->ctf_typemax)
+  ctf_lookup_idx_key_t key = { fp, symname, names };
+  uint32_t *idx;
+
+  idx = bsearch (&key, sxlate, nidx, sizeof (uint32_t), ctf_lookup_idx_name);
+
+  if (!idx)
     {
-      *fpp = fp;		/* Function returns ending CTF dict.  */
-      return (LCTF_INDEX_TO_TYPEPTR (fp, idx));
+      ctf_dprintf ("%s not found in idx\n", symname);
+      return 0;
     }
 
-  (void) ctf_set_errno (*fpp, ECTF_BADID);
-  return NULL;
+  /* Should be impossible, but be paranoid.  */
+  if ((idx - sxlate) > (ptrdiff_t) nidx)
+    return (ctf_set_errno (fp, ECTF_CORRUPT));
+
+  ctf_dprintf ("Symbol %lx (%s) is of type %x\n", symidx, symname,
+	       symtypetab[*idx]);
+  return symtypetab[*idx];
 }
 
-/* Given a symbol table index, return the info for the function described
-   by the corresponding entry in the symbol table.  */
+/* Given a symbol table index, return the type of the function or data object
+   described by the corresponding entry in the symbol table.  We can only return
+   symbols in read-only dicts and in dicts for which ctf_link_shuffle_syms has
+   been called to assign symbol indexes to symbol names.  */
 
-int
-ctf_func_info (ctf_dict_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
+ctf_id_t
+ctf_lookup_by_symbol (ctf_dict_t *fp, unsigned long symidx)
 {
   const ctf_sect_t *sp = &fp->ctf_symtab;
-  const uint32_t *dp;
-  uint32_t info, kind, n;
+  ctf_id_t type = 0;
+  int err = 0;
+
+  /* Shuffled dynsymidx present?  Use that.  */
+  if (fp->ctf_dynsymidx)
+    {
+      const ctf_link_sym_t *sym;
+
+      ctf_dprintf ("Looking up type of object with symtab idx %lx in "
+		   "writable dict symtypetab\n", symidx);
+
+      /* The dict must be dynamic.  */
+      if (!ctf_assert (fp, fp->ctf_flags & LCTF_RDWR))
+	return CTF_ERR;
+
+      err = EINVAL;
+      if (symidx > fp->ctf_dynsymmax)
+	goto try_parent;
+
+      sym = fp->ctf_dynsymidx[symidx];
+      err = ECTF_NOTYPEDAT;
+      if (!sym || (sym->st_shndx != STT_OBJECT && sym->st_shndx != STT_FUNC))
+	goto try_parent;
+
+      if (!ctf_assert (fp, !sym->st_nameidx_set))
+	return CTF_ERR;
+
+      if (fp->ctf_objthash == NULL
+	  || ((type = (ctf_id_t) (uintptr_t)
+	       ctf_dynhash_lookup (fp->ctf_objthash, sym->st_name)) == 0))
+	{
+	  if (fp->ctf_funchash == NULL
+	      || ((type = (ctf_id_t) (uintptr_t)
+		   ctf_dynhash_lookup (fp->ctf_funchash, sym->st_name)) == 0))
+	    goto try_parent;
+	}
+
+      return type;
+    }
 
+  err = ECTF_NOSYMTAB;
   if (sp->cts_data == NULL)
-    return (ctf_set_errno (fp, ECTF_NOSYMTAB));
+    goto try_parent;
 
+  /* This covers both out-of-range lookups and a dynamic dict which hasn't been
+     shuffled yet.  */
+  err = EINVAL;
   if (symidx >= fp->ctf_nsyms)
-    return (ctf_set_errno (fp, EINVAL));
+    goto try_parent;
 
-  if (sp->cts_entsize == sizeof (Elf32_Sym))
+  if (fp->ctf_objtidx_names)
     {
-      const Elf32_Sym *symp = (Elf32_Sym *) sp->cts_data + symidx;
-      if (ELF32_ST_TYPE (symp->st_info) != STT_FUNC)
-	return (ctf_set_errno (fp, ECTF_NOTFUNC));
+      if ((type = ctf_try_lookup_indexed (fp, symidx, 0)) == CTF_ERR)
+	return CTF_ERR;				/* errno is set for us.  */
     }
-  else
+  if (type == 0 && fp->ctf_funcidx_names)
     {
-      const Elf64_Sym *symp = (Elf64_Sym *) sp->cts_data + symidx;
-      if (ELF64_ST_TYPE (symp->st_info) != STT_FUNC)
-	return (ctf_set_errno (fp, ECTF_NOTFUNC));
+      if ((type = ctf_try_lookup_indexed (fp, symidx, 1)) == CTF_ERR)
+	return CTF_ERR;				/* errno is set for us.  */
     }
+  if (type != 0)
+    return type;
+
+  err = ECTF_NOTYPEDAT;
+  if (fp->ctf_objtidx_names && fp->ctf_funcidx_names)
+    goto try_parent;
+
+  /* Table must be nonindexed.  */
+
+  ctf_dprintf ("Looking up object type %lx in 1:1 dict symtypetab\n", symidx);
 
   if (fp->ctf_sxlate[symidx] == -1u)
-    return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
+    goto try_parent;
+
+  type = *(uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
 
-  dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]);
+  if (type == 0)
+    goto try_parent;
 
-  info = *dp++;
-  kind = LCTF_INFO_KIND (fp, info);
-  n = LCTF_INFO_VLEN (fp, info);
+  return type;
+ try_parent:
+  if (fp->ctf_parent)
+    return ctf_lookup_by_symbol (fp->ctf_parent, symidx);
+  else
+    return (ctf_set_errno (fp, err));
+}
 
-  if (kind == CTF_K_UNKNOWN && n == 0)
-    return (ctf_set_errno (fp, ECTF_NOFUNCDAT));
+/* Given a symbol table index, return the info for the function described
+   by the corresponding entry in the symbol table, which may be a function
+   symbol or may be a data symbol that happens to be a function pointer.  */
 
-  if (kind != CTF_K_FUNCTION)
-    return (ctf_set_errno (fp, ECTF_CORRUPT));
+int
+ctf_func_info (ctf_dict_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
+{
+  ctf_id_t type;
 
-  fip->ctc_return = *dp++;
-  fip->ctc_argc = n;
-  fip->ctc_flags = 0;
+  if ((type = ctf_lookup_by_symbol (fp, symidx)) == CTF_ERR)
+    return -1;					/* errno is set for us.  */
 
-  if (n != 0 && dp[n - 1] == 0)
-    {
-      fip->ctc_flags |= CTF_FUNC_VARARG;
-      fip->ctc_argc--;
-    }
+  if (ctf_type_kind (fp, type) != CTF_K_FUNCTION)
+    return (ctf_set_errno (fp, ECTF_NOTFUNC));
 
-  return 0;
+  return ctf_func_type_info (fp, type, fip);
 }
 
 /* Given a symbol table index, return the arguments for the function described
@@ -423,21 +737,15 @@ ctf_func_info (ctf_dict_t *fp, unsigned long symidx, ctf_funcinfo_t *fip)
 
 int
 ctf_func_args (ctf_dict_t *fp, unsigned long symidx, uint32_t argc,
-	       ctf_id_t * argv)
+	       ctf_id_t *argv)
 {
-  const uint32_t *dp;
-  ctf_funcinfo_t f;
-
-  if (ctf_func_info (fp, symidx, &f) < 0)
-    return -1;			/* errno is set for us.  */
-
-  /* The argument data is two uint32_t's past the translation table
-     offset: one for the function info, and one for the return type. */
+  ctf_id_t type;
 
-  dp = (uint32_t *) ((uintptr_t) fp->ctf_buf + fp->ctf_sxlate[symidx]) + 2;
+  if ((type = ctf_lookup_by_symbol (fp, symidx)) == CTF_ERR)
+    return -1;					/* errno is set for us.  */
 
-  for (argc = MIN (argc, f.ctc_argc); argc != 0; argc--)
-    *argv++ = *dp++;
+  if (ctf_type_kind (fp, type) != CTF_K_FUNCTION)
+    return (ctf_set_errno (fp, ECTF_NOTFUNC));
 
-  return 0;
+  return ctf_func_type_args (fp, type, argc, argv);
 }
diff --git a/libctf/ctf-open.c b/libctf/ctf-open.c
index 456efa6..3281c67 100644
--- a/libctf/ctf-open.c
+++ b/libctf/ctf-open.c
@@ -27,8 +27,6 @@
 #include <bfd.h>
 #include <zlib.h>
 
-#include "elf-bfd.h"
-
 static const ctf_dmodel_t _libctf_models[] = {
   {"ILP32", CTF_MODEL_ILP32, 4, 1, 2, 4, 4},
   {"LP64", CTF_MODEL_LP64, 8, 1, 2, 4, 8},
@@ -220,55 +218,88 @@ static const ctf_dictops_t ctf_dictops[] = {
   {get_kind_v2, get_root_v2, get_vlen_v2, get_ctt_size_v2, get_vbytes_v2},
 };
 
-/* Initialize the symtab translation table by filling each entry with the
-  offset of the CTF type or function data corresponding to each STT_FUNC or
-  STT_OBJECT entry in the symbol table.  */
+/* Initialize the symtab translation table as appropriate for its indexing
+   state.  For unindexed symtypetabs, fill each entry with the offset of the CTF
+   type or function data corresponding to each STT_FUNC or STT_OBJECT entry in
+   the symbol table.  For indexed symtypetabs, do nothing: the needed
+   initialization for indexed lookups may be quite expensive, so it is done only
+   as needed, when lookups happen.  (In particular, the majority of indexed
+   symtypetabs come from the compiler, and all the linker does is iteration over
+   all entries, which doesn't need this initialization.)
+
+   The SP symbol table section may be NULL if there is no symtab.  */
 
 static int
-init_symtab (ctf_dict_t *fp, const ctf_header_t *hp,
-	     const ctf_sect_t *sp, const ctf_sect_t *strp)
+init_symtab (ctf_dict_t *fp, const ctf_header_t *hp, const ctf_sect_t *sp)
 {
-  const unsigned char *symp = sp->cts_data;
+  const unsigned char *symp;
+  int skip_func_info = 0;
+  int i;
   uint32_t *xp = fp->ctf_sxlate;
   uint32_t *xend = xp + fp->ctf_nsyms;
 
   uint32_t objtoff = hp->cth_objtoff;
   uint32_t funcoff = hp->cth_funcoff;
 
-  uint32_t info, vlen;
-  Elf64_Sym sym, *gsp;
-  const char *name;
-
-  /* The CTF data object and function type sections are ordered to match
-     the relative order of the respective symbol types in the symtab.
-     If no type information is available for a symbol table entry, a
-     pad is inserted in the CTF section.  As a further optimization,
-     anonymous or undefined symbols are omitted from the CTF data.  */
-
-  for (; xp < xend; xp++, symp += sp->cts_entsize)
+  /* If the CTF_F_NEWFUNCINFO flag is not set, pretend the func info section
+     is empty: this compiler is too old to emit a function info section we
+     understand.  */
+
+  if (!(hp->cth_flags & CTF_F_NEWFUNCINFO))
+    skip_func_info = 1;
+
+  if (hp->cth_objtidxoff < hp->cth_funcidxoff)
+    fp->ctf_objtidx_names = (uint32_t *) (fp->ctf_buf + hp->cth_objtidxoff);
+  if (hp->cth_funcidxoff < hp->cth_varoff && !skip_func_info)
+    fp->ctf_funcidx_names = (uint32_t *) (fp->ctf_buf + hp->cth_funcidxoff);
+
+  /* Don't bother doing the rest if everything is indexed, or if we don't have a
+     symbol table: we will never use it.  */
+  if ((fp->ctf_objtidx_names && fp->ctf_funcidx_names) || !sp || !sp->cts_data)
+    return 0;
+
+  /* The CTF data object and function type sections are ordered to match the
+     relative order of the respective symbol types in the symtab, unless there
+     is an index section, in which case the order is arbitrary and the index
+     gives the mapping.  If no type information is available for a symbol table
+     entry, a pad is inserted in the CTF section.  As a further optimization,
+     anonymous or undefined symbols are omitted from the CTF data.  If an
+     index is available for function symbols but not object symbols, or vice
+     versa, we populate the xslate table for the unindexed symbols only.  */
+
+  for (i = 0, symp = sp->cts_data; xp < xend; xp++, symp += sp->cts_entsize,
+	 i++)
     {
-      if (sp->cts_entsize == sizeof (Elf32_Sym))
-	gsp = ctf_sym_to_elf64 ((Elf32_Sym *) (uintptr_t) symp, &sym);
-      else
-	gsp = (Elf64_Sym *) (uintptr_t) symp;
+      ctf_link_sym_t sym;
 
-      if (gsp->st_name < strp->cts_size)
-	name = (const char *) strp->cts_data + gsp->st_name;
-      else
-	name = _CTF_NULLSTR;
+      switch (sp->cts_entsize)
+	{
+	case sizeof (Elf64_Sym):
+	  {
+	    const Elf64_Sym *symp64 = (Elf64_Sym *) (uintptr_t) symp;
+	    ctf_elf64_to_link_sym (fp, &sym, symp64, i);
+	  }
+	  break;
+	case sizeof (Elf32_Sym):
+	  {
+	    const Elf32_Sym *symp32 = (Elf32_Sym *) (uintptr_t) symp;
+	    ctf_elf32_to_link_sym (fp, &sym, symp32, i);
+	  }
+	  break;
+	default:
+	  return ECTF_SYMTAB;
+	}
 
-      if (gsp->st_name == 0 || gsp->st_shndx == SHN_UNDEF
-	  || strcmp (name, "_START_") == 0 || strcmp (name, "_END_") == 0)
+      if (ctf_symtab_skippable (&sym))
 	{
 	  *xp = -1u;
 	  continue;
 	}
 
-      switch (ELF64_ST_TYPE (gsp->st_info))
+      switch (sym.st_type)
 	{
 	case STT_OBJECT:
-	  if (objtoff >= hp->cth_funcoff
-	      || (gsp->st_shndx == SHN_EXTABS && gsp->st_value == 0))
+	  if (fp->ctf_objtidx_names || objtoff >= hp->cth_funcoff)
 	    {
 	      *xp = -1u;
 	      break;
@@ -279,25 +310,15 @@ init_symtab (ctf_dict_t *fp, const ctf_header_t *hp,
 	  break;
 
 	case STT_FUNC:
-	  if (funcoff >= hp->cth_objtidxoff)
+	  if (fp->ctf_funcidx_names || funcoff >= hp->cth_objtidxoff
+	      || skip_func_info)
 	    {
 	      *xp = -1u;
 	      break;
 	    }
 
 	  *xp = funcoff;
-
-	  info = *(uint32_t *) ((uintptr_t) fp->ctf_buf + funcoff);
-	  vlen = LCTF_INFO_VLEN (fp, info);
-
-	  /* If we encounter a zero pad at the end, just skip it.  Otherwise
-	     skip over the function and its return type (+2) and the argument
-	     list (vlen).
-	   */
-	  if (LCTF_INFO_KIND (fp, info) == CTF_K_UNKNOWN && vlen == 0)
-	    funcoff += sizeof (uint32_t);	/* Skip pad.  */
-	  else
-	    funcoff += sizeof (uint32_t) * (vlen + 2);
+	  funcoff += sizeof (uint32_t);
 	  break;
 
 	default:
@@ -1012,9 +1033,7 @@ flip_lbls (void *start, size_t len)
 }
 
 /* Flip the endianness of the data-object or function sections or their indexes,
-   all arrays of uint32_t.  (The function section has more internal structure,
-   but that structure is an array of uint32_t, so can be treated as one big
-   array for byte-swapping.)  */
+   all arrays of uint32_t.  */
 
 static void
 flip_objts (void *start, size_t len)
@@ -1379,8 +1398,9 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
 	 info.  We do not support dynamically upgrading such entries (none
 	 should exist in any case, since dwarf2ctf does not create them).  */
 
-      ctf_err_warn (NULL, 0, 0, _("ctf_bufopen: CTF version %d symsect not "
-				  "supported"), pp->ctp_version);
+      ctf_err_warn (NULL, 0, ECTF_NOTSUP, _("ctf_bufopen: CTF version %d "
+					    "symsect not supported"),
+		    pp->ctp_version);
       return (ctf_set_open_errno (errp, ECTF_NOTSUP));
     }
 
@@ -1388,7 +1408,12 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
     hdrsz = sizeof (ctf_header_v2_t);
 
   if (_libctf_unlikely_ (pp->ctp_flags > CTF_F_MAX))
-    return (ctf_set_open_errno (errp, ECTF_FLAGS));
+    {
+      ctf_err_warn (NULL, 0, ECTF_FLAGS, _("ctf_bufopen: invalid header "
+					   "flags: %x"),
+		    (unsigned int) pp->ctp_flags);
+      return (ctf_set_open_errno (errp, ECTF_FLAGS));
+    }
 
   if (ctfsect->cts_size < hdrsz)
     return (ctf_set_open_errno (errp, ECTF_NOCTFBUF));
@@ -1423,7 +1448,10 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
       || hp->cth_funcoff > fp->ctf_size || hp->cth_objtidxoff > fp->ctf_size
       || hp->cth_funcidxoff > fp->ctf_size || hp->cth_typeoff > fp->ctf_size
       || hp->cth_stroff > fp->ctf_size)
-    return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    {
+      ctf_err_warn (NULL, 0, ECTF_CORRUPT, _("header offset exceeds CTF size"));
+      return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    }
 
   if (hp->cth_lbloff > hp->cth_objtoff
       || hp->cth_objtoff > hp->cth_funcoff
@@ -1432,13 +1460,46 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
       || hp->cth_objtidxoff > hp->cth_funcidxoff
       || hp->cth_funcidxoff > hp->cth_varoff
       || hp->cth_varoff > hp->cth_typeoff || hp->cth_typeoff > hp->cth_stroff)
-    return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    {
+      ctf_err_warn (NULL, 0, ECTF_CORRUPT, _("overlapping CTF sections"));
+      return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    }
 
   if ((hp->cth_lbloff & 3) || (hp->cth_objtoff & 2)
       || (hp->cth_funcoff & 2) || (hp->cth_objtidxoff & 2)
       || (hp->cth_funcidxoff & 2) || (hp->cth_varoff & 3)
       || (hp->cth_typeoff & 3))
-    return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    {
+      ctf_err_warn (NULL, 0, ECTF_CORRUPT,
+		    _("CTF sections not properly aligned"));
+      return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    }
+
+  /* This invariant will be lifted in v4, but for now it is true.  */
+
+  if ((hp->cth_funcidxoff - hp->cth_objtidxoff != 0) &&
+      (hp->cth_funcidxoff - hp->cth_objtidxoff
+       != hp->cth_funcoff - hp->cth_objtoff))
+    {
+      ctf_err_warn (NULL, 0, ECTF_CORRUPT,
+		    _("Object index section exists is neither empty nor the "
+		      "same length as the object section: %u versus %u "
+		      "bytes"), hp->cth_funcoff - hp->cth_objtoff,
+		    hp->cth_funcidxoff - hp->cth_objtidxoff);
+      return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    }
+
+  if ((hp->cth_varoff - hp->cth_funcidxoff != 0) &&
+      (hp->cth_varoff - hp->cth_funcidxoff
+       != hp->cth_objtidxoff - hp->cth_funcoff))
+    {
+      ctf_err_warn (NULL, 0, ECTF_CORRUPT,
+		    _("Function index section exists is neither empty nor the "
+		      "same length as the function section: %u versus %u "
+		      "bytes"), hp->cth_objtidxoff - hp->cth_funcoff,
+		    hp->cth_varoff - hp->cth_funcidxoff);
+      return (ctf_set_open_errno (errp, ECTF_CORRUPT));
+    }
 
   /* Once everything is determined to be valid, attempt to decompress the CTF
      data buffer if it is compressed, or copy it into new storage if it is not
@@ -1586,10 +1647,12 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
   if ((err = init_types (fp, hp)) != 0)
     goto bad;
 
-  /* If we have a symbol table section, allocate and initialize
-     the symtab translation table, pointed to by ctf_sxlate.  This table may be
-     too large for the actual size of the object and function info sections: if
-     so, ctf_nsyms will be adjusted and the excess will never be used.  */
+  /* Allocate and initialize the symtab translation table, pointed to by
+     ctf_sxlate, and the corresponding index sections.  This table may be too
+     large for the actual size of the object and function info sections: if so,
+     ctf_nsyms will be adjusted and the excess will never be used.  It's
+     possible to do indexed symbol lookups even without a symbol table, so check
+     even in that case.  */
 
   if (symsect != NULL)
     {
@@ -1601,11 +1664,11 @@ ctf_bufopen_internal (const ctf_sect_t *ctfsect, const ctf_sect_t *symsect,
 	  err = ENOMEM;
 	  goto bad;
 	}
-
-      if ((err = init_symtab (fp, hp, symsect, strsect)) != 0)
-	goto bad;
     }
 
+  if ((err = init_symtab (fp, hp, symsect)) != 0)
+    goto bad;
+
   ctf_set_ctl_hashes (fp);
 
   if (symsect != NULL)
@@ -1649,6 +1712,7 @@ ctf_dict_close (ctf_dict_t *fp)
 {
   ctf_dtdef_t *dtd, *ntd;
   ctf_dvdef_t *dvd, *nvd;
+  ctf_in_flight_dynsym_t *did, *nid;
   ctf_err_warning_t *err, *nerr;
 
   if (fp == NULL)
@@ -1701,6 +1765,20 @@ ctf_dict_close (ctf_dict_t *fp)
       ctf_dvd_delete (fp, dvd);
     }
   ctf_dynhash_destroy (fp->ctf_dvhash);
+
+  free (fp->ctf_funcidx_sxlate);
+  free (fp->ctf_objtidx_sxlate);
+  ctf_dynhash_destroy (fp->ctf_objthash);
+  ctf_dynhash_destroy (fp->ctf_funchash);
+  free (fp->ctf_dynsymidx);
+  ctf_dynhash_destroy (fp->ctf_dynsyms);
+  for (did = ctf_list_next (&fp->ctf_in_flight_dynsyms); did != NULL; did = nid)
+    {
+      nid = ctf_list_next (did);
+      ctf_list_delete (&fp->ctf_in_flight_dynsyms, did);
+      free (did);
+    }
+
   ctf_str_free_atoms (fp);
   free (fp->ctf_tmp_typeslice);
 
diff --git a/libctf/ctf-string.c b/libctf/ctf-string.c
index 701cc86..ed65b51 100644
--- a/libctf/ctf-string.c
+++ b/libctf/ctf-string.c
@@ -259,6 +259,28 @@ ctf_str_add_external (ctf_dict_t *fp, const char *str, uint32_t offset)
     return 0;
 
   atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
+
+  if (!fp->ctf_syn_ext_strtab)
+    fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
+						 ctf_hash_eq_integer,
+						 NULL, NULL);
+  if (!fp->ctf_syn_ext_strtab)
+    {
+      ctf_set_errno (fp, ENOMEM);
+      return 0;
+    }
+
+  if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
+			  (void *) (uintptr_t)
+			  atom->csa_external_offset,
+			  (void *) atom->csa_str) < 0)
+    {
+      /* No need to bother freeing the syn_ext_strtab: it will get freed at
+	 ctf_str_write_strtab time if unreferenced.  */
+      ctf_set_errno (fp, ENOMEM);
+      return 0;
+    }
+
   return 1;
 }
 
@@ -285,17 +307,20 @@ ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 }
 
 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
-   snapshot ID.  */
+   snapshot ID.  External atoms are never removed, because they came from the
+   linker string table and are still present even if you roll back type
+   additions.  */
 static int
 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 {
   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 
-  return (atom->csa_snapshot_id > id->snapshot_id);
+  return (atom->csa_snapshot_id > id->snapshot_id)
+    && (atom->csa_external_offset == 0);
 }
 
-/* Roll back, deleting all atoms created after a particular ID.  */
+/* Roll back, deleting all (internal) atoms created after a particular ID.  */
 void
 ctf_str_rollback (ctf_dict_t *fp, ctf_snapshot_id_t id)
 {
@@ -455,32 +480,15 @@ ctf_str_write_strtab (ctf_dict_t *fp)
   if ((strtab.cts_strs = malloc (strtab.cts_len)) == NULL)
     goto oom_sorttab;
 
-  if (!fp->ctf_syn_ext_strtab)
-    fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
-						 ctf_hash_eq_integer,
-						 NULL, NULL);
-  if (!fp->ctf_syn_ext_strtab)
-    goto oom_strtab;
-
   /* Update all refs: also update the strtab appropriately.  */
   for (i = 0; i < s.strtab_count; i++)
     {
       if (sorttab[i]->csa_external_offset)
 	{
-	  /* External strtab entry: populate the synthetic external strtab.
-
-	     This is safe because you cannot ctf_rollback to before the point
-	     when a ctf_update is done, and the strtab is written at ctf_update
-	     time.  So any atoms we reference here are sure to stick around
-	     until ctf_dict_close.  */
+	  /* External strtab entry.  */
 
 	  any_external = 1;
 	  ctf_str_update_refs (sorttab[i], sorttab[i]->csa_external_offset);
-	  if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
-				  (void *) (uintptr_t)
-				  sorttab[i]->csa_external_offset,
-				  (void *) sorttab[i]->csa_str) < 0)
-	    goto oom_strtab;
 	  sorttab[i]->csa_offset = sorttab[i]->csa_external_offset;
 	}
       else
@@ -510,9 +518,6 @@ ctf_str_write_strtab (ctf_dict_t *fp)
   fp->ctf_str_prov_offset = strtab.cts_len + 1;
   return strtab;
 
- oom_strtab:
-  free (strtab.cts_strs);
-  strtab.cts_strs = NULL;
  oom_sorttab:
   free (sorttab);
  oom:
diff --git a/libctf/ctf-types.c b/libctf/ctf-types.c
index 60d1bef..dd8ee4f 100644
--- a/libctf/ctf-types.c
+++ b/libctf/ctf-types.c
@@ -642,6 +642,18 @@ ctf_type_resolve_unsliced (ctf_dict_t *fp, ctf_id_t type)
   return type;
 }
 
+/* Return the native dict of a given type: if called on a child and the
+   type is in the parent, return the parent.  Needed if you plan to access
+   the type directly, without using the API.  */
+ctf_dict_t *
+ctf_get_dict (ctf_dict_t *fp, ctf_id_t type)
+{
+    if ((fp->ctf_flags & LCTF_CHILD) && LCTF_TYPE_ISPARENT (fp, type))
+      return fp->ctf_parent;
+
+    return fp;
+}
+
 /* Look up a name in the given name table, in the appropriate hash given the
    kind of the identifier.  The name is a raw, undecorated identifier.  */
 
diff --git a/libctf/ctf-util.c b/libctf/ctf-util.c
index c29f460..0a15b86 100644
--- a/libctf/ctf-util.c
+++ b/libctf/ctf-util.c
@@ -108,17 +108,48 @@ ctf_list_splice (ctf_list_t *lp, ctf_list_t *append)
   append->l_prev = NULL;
 }
 
-/* Convert a 32-bit ELF symbol into Elf64 and return a pointer to it.  */
+/* Convert a 32-bit ELF symbol to a ctf_link_sym_t.  */
 
-Elf64_Sym *
-ctf_sym_to_elf64 (const Elf32_Sym *src, Elf64_Sym *dst)
+ctf_link_sym_t *
+ctf_elf32_to_link_sym (ctf_dict_t *fp, ctf_link_sym_t *dst, const Elf32_Sym *src,
+		       uint32_t symidx)
 {
-  dst->st_name = src->st_name;
+  /* The name must be in the external string table.  */
+  if (src->st_name < fp->ctf_str[CTF_STRTAB_1].cts_len)
+    dst->st_name = (const char *) fp->ctf_str[CTF_STRTAB_1].cts_strs + src->st_name;
+  else
+    dst->st_name = _CTF_NULLSTR;
+  dst->st_nameidx_set = 0;
+  dst->st_symidx = symidx;
+  dst->st_shndx = src->st_shndx;
+  dst->st_type = ELF32_ST_TYPE (src->st_info);
   dst->st_value = src->st_value;
-  dst->st_size = src->st_size;
-  dst->st_info = src->st_info;
-  dst->st_other = src->st_other;
+
+  return dst;
+}
+
+/* Convert a 64-bit ELF symbol to a ctf_link_sym_t.  */
+
+ctf_link_sym_t *
+ctf_elf64_to_link_sym (ctf_dict_t *fp, ctf_link_sym_t *dst, const Elf64_Sym *src,
+		       uint32_t symidx)
+{
+  /* The name must be in the external string table.  */
+  if (src->st_name < fp->ctf_str[CTF_STRTAB_1].cts_len)
+    dst->st_name = (const char *) fp->ctf_str[CTF_STRTAB_1].cts_strs + src->st_name;
+  else
+    dst->st_name = _CTF_NULLSTR;
+  dst->st_nameidx_set = 0;
+  dst->st_symidx = symidx;
   dst->st_shndx = src->st_shndx;
+  dst->st_type = ELF32_ST_TYPE (src->st_info);
+
+  /* We only care if the value is zero, so avoid nonzeroes turning into
+     zeroes.  */
+  if (_libctf_unlikely_ (src->st_value != 0 && ((uint32_t) src->st_value == 0)))
+    dst->st_value = 1;
+  else
+    dst->st_value = (uint32_t) src->st_value;
 
   return dst;
 }
@@ -212,6 +243,9 @@ ctf_next_destroy (ctf_next_t *i)
 
   if (i->ctn_iter_fun == (void (*) (void)) ctf_dynhash_next_sorted)
     free (i->u.ctn_sorted_hkv);
+  if (i->ctn_iter_fun == (void (*) (void)) ctf_symbol_next
+      && i->cu.ctn_fp->ctf_flags & LCTF_RDWR)
+    ctf_next_destroy (i->u.ctn_next);
   free (i);
 }
 
diff --git a/libctf/libctf.ver b/libctf/libctf.ver
index 317913e..7369d63 100644
--- a/libctf/libctf.ver
+++ b/libctf/libctf.ver
@@ -182,5 +182,9 @@ LIBCTF_1.1 {
 	ctf_dict_close;
 	ctf_parent_dict;
 
+	ctf_symbol_next;
+	ctf_add_objt_sym;
+	ctf_add_func_sym;
+
 	ctf_link_add_linker_symbol;
 } LIBCTF_1.0;