libctf, link: tie in the deduplicating linker

This fairly intricate commit connects up the CTF linker machinery (which
operates in terms of ctf_archive_t's on ctf_link_inputs ->
ctf_link_outputs) to the deduplicator (which operates in terms of arrays
of ctf_file_t's, all the archives exploded).

The nondeduplicating linker is retained, but is not called unless the
CTF_LINK_NONDEDUP flag is passed in (which ld never does), or the
environment variable LD_NO_CTF_DEDUP is set.  Eventually, once we have
confidence in the much-more-complex deduplicating linker, I hope the
nondeduplicating linker can be removed.

In brief, what this does is traverses each input archive in
ctf_link_inputs, opening every member (if not already open) and tying
child dicts to their parents, shoving them into an array and
constructing a corresponding parents array that tells the deduplicator
which dict is the parent of which child.  We then call ctf_dedup and
ctf_dedup_emit with that array of inputs, taking the outputs that result
and putting them into ctf_link_outputs where the rest of the CTF linker
expects to find them, then linking in the variables just as is done by
the nondeduplicating linker.

It also implements much of the CU-mapping side of things.  The problem
CU-mapping introduces is that if you map many input CUs into one output,
this is saying that you want many translation units to produce at most
one child dict if conflicting types are found in any of them.  This
means you can suddenly have multiple distinct types with the same name
in the same dict, which libctf cannot really represent because it's not
something you can do with C translation units.

The deduplicator machinery already committed does as best it can with
these, hiding types with conflicting names rather than making child
dicts out of them: but we still need to call it.  This is done similarly
to the main link, taking the inputs (one CU output at a time),
deduplicating them, taking the output and making it an input to the
final link.  Two (significant) optimizations are done: we share atoms
tables between all these links and the final link (so e.g. all type hash
values are shared, all decorated type names, etc); and any CU-mapped
links with only one input (and no child dicts) doesn't need to do
anything other than renaming the CU: the CU-mapped link phase can be
skipped for it.  Put together, large CU-mapped links can save 50% of
their memory usage and about as much time (and the memory usage for
CU-mapped links is significant, because all those output CUs have to
have all their types stored in memory all at once).

include/
	* ctf-api.h (CTF_LINK_NONDEDUP): New, turn off the
	deduplicator.
libctf/
	* ctf-impl.h (ctf_list_splice): New.
	* ctf-util.h (ctf_list_splice): Likewise.
	* ctf-link.c (link_sort_inputs_cb_arg_t): Likewise.
	(ctf_link_sort_inputs): Likewise.
	(ctf_link_deduplicating_count_inputs): Likewise.
	(ctf_link_deduplicating_open_inputs): Likewise.
	(ctf_link_deduplicating_close_inputs): Likewise.
	(ctf_link_deduplicating_variables): Likewise.
	(ctf_link_deduplicating_per_cu): Likewise.
	(ctf_link_deduplicating): Likewise.
	(ctf_link): Call it.

2 files changed, 8 insertions, 0 deletions

diff --git a/include/ChangeLog b/include/ChangeLog
index 896f333..e65e85d 100644
--- a/include/ChangeLog
+++ b/include/ChangeLog
@@ -1,5 +1,10 @@
 2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
 
+	* ctf-api.h (CTF_LINK_NONDEDUP): New, turn off the
+	deduplicator.
+
+2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-api.h (CTF_LINK_OMIT_VARIABLES_SECTION): New.
 
 2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
diff --git a/include/ctf-api.h b/include/ctf-api.h
index f034f98..77ea5cd 100644
--- a/include/ctf-api.h
+++ b/include/ctf-api.h
@@ -86,6 +86,9 @@ typedef struct ctf_link_sym
 /* Share only types that are used by multiple inputs.  */
 #define CTF_LINK_SHARE_DUPLICATED 0x1
 
+/* Do a nondeduplicating link.  */
+#define CTF_LINK_NONDEDUP 0x2
+
 /* Create empty outputs for all registered CU mappings even if no types are
    emitted into them.  */
 #define CTF_LINK_EMPTY_CU_MAPPINGS 0x4