libctf: add a deduplicator-specific type mapping table

When CTF linking is done, the linker has to track the association
between types in the inputs and types in the outputs.  The deduplicator
does this via the cd_output_emission_hashes, which maps from hashes of
types (valid in both the input and output) to the IDs of types in the
specific dict in which the cd_emission_hashes is held.  However, the
nondeduplicating linker and ctf_add_type used a different mechanism, a
dedicated hashtab stored in the ctf_link_type_mapping, populated via
ctf_add_type_mapping and queried via the ctf_type_mapping function.  To
allow the same functions to be used for variable and symbol population
in both the deduplicating and nondeduplicating linker, the deduplicator
carefully transferred all its input->output mappings into this hashtab
before returning.

This is *expensive*. The number of entries in this hashtab scales as the
number of input types, and unlike the hashing machinery the type mapping
machinery (the only other thing which scales that way) has not been much
optimized.

Now the nondeduplicating linker is gone, we can throw this out, move
the existing type mapping machinery to ctf-create.c and dedicate it to
ctf_add_type alone, and add a new function ctf_dedup_type_mapping which
uses the deduplicator's built-in knowledge of type mappings directly,
without requiring an expensive repopulation phase.

This speeds up a test link of nouveau.ko (a good worst-case candidate
with a lot of types in each of a lot of input files) from 9.11s to 7.15s
in my testing, a speedup of over 20%.

libctf/ChangeLog
2021-03-02  Nick Alcock  <nick.alcock@oracle.com>

	* ctf-impl.h (ctf_dict_t) <ctf_link_type_mapping>: No longer used
	by the nondeduplicating linker.
	(ctf_add_type_mapping): Removed, now static.
	(ctf_type_mapping): Likewise.
	(ctf_dedup_type_mapping): New.
	(ctf_dedup_t) <cd_input_nums>: New.
	* ctf-dedup.c (ctf_dedup_init): Populate it.
	(ctf_dedup_fini): Free it again.  Emphasise that this has to be
	the last thing called.
	(ctf_dedup): Populate it.
	(ctf_dedup_populate_type_mapping): Removed.
	(ctf_dedup_populate_type_mappings): Likewise.
	(ctf_dedup_emit): No longer call it.  No longer call
	ctf_dedup_fini either.
	(ctf_dedup_type_mapping): New.
	* ctf-link.c (ctf_unnamed_cuname): New.
	(ctf_create_per_cu): Arguments must be non-null now.
	(ctf_in_member_cb_arg): Removed.
	(ctf_link): No longer populate it.  No longer discard the
	mapping table.
	(ctf_link_deduplicating_one_symtypetab): Use
	ctf_dedup_type_mapping, not ctf_type_mapping.  Use
	ctf_unnamed_cuname.
	(ctf_link_one_variable): Likewise.  Pass in args individually: no
	longer a ctf_variable_iter callback.
	(empty_link_type_mapping): Removed.
	(ctf_link_deduplicating_variables): Use ctf_variable_next, not
	ctf_variable_iter.  No longer pack arguments to
	ctf_link_one_variable into a struct.
	(ctf_link_deduplicating_per_cu): Call ctf_dedup_fini once
	all link phases are done.
	(ctf_link_deduplicating): Likewise.
	(ctf_link_intern_extern_string): Improve comment.
	(ctf_add_type_mapping): Migrate...
	(ctf_type_mapping): ... these functions...
	* ctf-create.c (ctf_add_type_mapping): ... here...
	(ctf_type_mapping): ... and make static, for the sole use of
	ctf_add_type.

5 files changed, 344 insertions, 328 deletions

diff --git a/libctf/ChangeLog b/libctf/ChangeLog
index e0d3f7b..9706919 100644
--- a/libctf/ChangeLog
+++ b/libctf/ChangeLog
@@ -1,5 +1,46 @@
 2021-03-02  Nick Alcock  <nick.alcock@oracle.com>
 
+	* ctf-impl.h (ctf_dict_t) <ctf_link_type_mapping>: No longer used
+	by the nondeduplicating linker.
+	(ctf_add_type_mapping): Removed, now static.
+	(ctf_type_mapping): Likewise.
+	(ctf_dedup_type_mapping): New.
+	(ctf_dedup_t) <cd_input_nums>: New.
+	* ctf-dedup.c (ctf_dedup_init): Populate it.
+	(ctf_dedup_fini): Free it again.  Emphasise that this has to be
+	the last thing called.
+	(ctf_dedup): Populate it.
+	(ctf_dedup_populate_type_mapping): Removed.
+	(ctf_dedup_populate_type_mappings): Likewise.
+	(ctf_dedup_emit): No longer call it.  No longer call
+	ctf_dedup_fini either.
+	(ctf_dedup_type_mapping): New.
+	* ctf-link.c (ctf_unnamed_cuname): New.
+	(ctf_create_per_cu): Arguments must be non-null now.
+	(ctf_in_member_cb_arg): Removed.
+	(ctf_link): No longer populate it.  No longer discard the
+	mapping table.
+	(ctf_link_deduplicating_one_symtypetab): Use
+	ctf_dedup_type_mapping, not ctf_type_mapping.  Use
+	ctf_unnamed_cuname.
+	(ctf_link_one_variable): Likewise.  Pass in args individually: no
+	longer a ctf_variable_iter callback.
+	(empty_link_type_mapping): Removed.
+	(ctf_link_deduplicating_variables): Use ctf_variable_next, not
+	ctf_variable_iter.  No longer pack arguments to
+	ctf_link_one_variable into a struct.
+	(ctf_link_deduplicating_per_cu): Call ctf_dedup_fini once
+	all link phases are done.
+	(ctf_link_deduplicating): Likewise.
+	(ctf_link_intern_extern_string): Improve comment.
+	(ctf_add_type_mapping): Migrate...
+	(ctf_type_mapping): ... these functions...
+	* ctf-create.c (ctf_add_type_mapping): ... here...
+	(ctf_type_mapping): ... and make static, for the sole use of
+	ctf_add_type.
+
+2021-03-02  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-link.c (ctf_link_one_variable): Remove reference to
 	"unconflicted link mode".
 
diff --git a/libctf/ctf-create.c b/libctf/ctf-create.c
index c01ab7a..d417922 100644
--- a/libctf/ctf-create.c
+++ b/libctf/ctf-create.c
@@ -2471,6 +2471,101 @@ membadd (const char *name, ctf_id_t type, unsigned long offset, void *arg)
   return 0;
 }
 
+/* Record the correspondence between a source and ctf_add_type()-added
+   destination type: both types are translated into parent type IDs if need be,
+   so they relate to the actual dictionary they are in.  Outside controlled
+   circumstances (like linking) it is probably not useful to do more than
+   compare these pointers, since there is nothing stopping the user closing the
+   source dict whenever they want to.
+
+   Our OOM handling here is just to not do anything, because this is called deep
+   enough in the call stack that doing anything useful is painfully difficult:
+   the worst consequence if we do OOM is a bit of type duplication anyway.  */
+
+static void
+ctf_add_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type,
+		      ctf_dict_t *dst_fp, ctf_id_t dst_type)
+{
+  if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
+    src_fp = src_fp->ctf_parent;
+
+  src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
+
+  if (LCTF_TYPE_ISPARENT (dst_fp, dst_type) && dst_fp->ctf_parent)
+    dst_fp = dst_fp->ctf_parent;
+
+  dst_type = LCTF_TYPE_TO_INDEX(dst_fp, dst_type);
+
+  if (dst_fp->ctf_link_type_mapping == NULL)
+    {
+      ctf_hash_fun f = ctf_hash_type_key;
+      ctf_hash_eq_fun e = ctf_hash_eq_type_key;
+
+      if ((dst_fp->ctf_link_type_mapping = ctf_dynhash_create (f, e, free,
+							       NULL)) == NULL)
+	return;
+    }
+
+  ctf_link_type_key_t *key;
+  key = calloc (1, sizeof (struct ctf_link_type_key));
+  if (!key)
+    return;
+
+  key->cltk_fp = src_fp;
+  key->cltk_idx = src_type;
+
+  /* No OOM checking needed, because if this doesn't work the worst we'll do is
+     add a few more duplicate types (which will probably run out of memory
+     anyway).  */
+  ctf_dynhash_insert (dst_fp->ctf_link_type_mapping, key,
+		      (void *) (uintptr_t) dst_type);
+}
+
+/* Look up a type mapping: return 0 if none.  The DST_FP is modified to point to
+   the parent if need be.  The ID returned is from the dst_fp's perspective.  */
+static ctf_id_t
+ctf_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type, ctf_dict_t **dst_fp)
+{
+  ctf_link_type_key_t key;
+  ctf_dict_t *target_fp = *dst_fp;
+  ctf_id_t dst_type = 0;
+
+  if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
+    src_fp = src_fp->ctf_parent;
+
+  src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
+  key.cltk_fp = src_fp;
+  key.cltk_idx = src_type;
+
+  if (target_fp->ctf_link_type_mapping)
+    dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
+					       &key);
+
+  if (dst_type != 0)
+    {
+      dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
+				     target_fp->ctf_parent != NULL);
+      *dst_fp = target_fp;
+      return dst_type;
+    }
+
+  if (target_fp->ctf_parent)
+    target_fp = target_fp->ctf_parent;
+  else
+    return 0;
+
+  if (target_fp->ctf_link_type_mapping)
+    dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
+					       &key);
+
+  if (dst_type)
+    dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
+				   target_fp->ctf_parent != NULL);
+
+  *dst_fp = target_fp;
+  return dst_type;
+}
+
 /* The ctf_add_type routine is used to copy a type from a source CTF dictionary
    to a dynamic destination dictionary.  This routine operates recursively by
    following the source type's links and embedded member types.  If the
diff --git a/libctf/ctf-dedup.c b/libctf/ctf-dedup.c
index 001c248..50da4ac 100644
--- a/libctf/ctf-dedup.c
+++ b/libctf/ctf-dedup.c
@@ -1642,6 +1642,12 @@ ctf_dedup_init (ctf_dict_t *fp)
     goto oom;
 #endif
 
+  if ((d->cd_input_nums
+       = ctf_dynhash_create (ctf_hash_integer,
+			     ctf_hash_eq_integer,
+			     NULL, NULL)) == NULL)
+    goto oom;
+
   if ((d->cd_emission_struct_members
        = ctf_dynhash_create (ctf_hash_integer,
 			     ctf_hash_eq_integer,
@@ -1661,6 +1667,8 @@ ctf_dedup_init (ctf_dict_t *fp)
   return ctf_set_errno (fp, ENOMEM);
 }
 
+/* No ctf_dedup calls are allowed after this call other than starting a new
+   deduplication via ctf_dedup (not even ctf_dedup_type_mapping lookups).  */
 void
 ctf_dedup_fini (ctf_dict_t *fp, ctf_dict_t **outputs, uint32_t noutputs)
 {
@@ -1682,6 +1690,7 @@ ctf_dedup_fini (ctf_dict_t *fp, ctf_dict_t **outputs, uint32_t noutputs)
 #ifdef ENABLE_LIBCTF_HASH_DEBUGGING
   ctf_dynhash_destroy (d->cd_output_mapping_guard);
 #endif
+  ctf_dynhash_destroy (d->cd_input_nums);
   ctf_dynhash_destroy (d->cd_emission_struct_members);
   ctf_dynset_destroy (d->cd_conflicting_types);
 
@@ -1876,12 +1885,22 @@ ctf_dedup (ctf_dict_t *output, ctf_dict_t **inputs, uint32_t ninputs,
   size_t i;
   ctf_next_t *it = NULL;
 
-  for (i = 0; i < ninputs; i++)
-    ctf_dprintf ("Input %i: %s\n", (int) i, ctf_link_input_name (inputs[i]));
-
   if (ctf_dedup_init (output) < 0)
     return -1; 					/* errno is set for us.  */
 
+  for (i = 0; i < ninputs; i++)
+    {
+      ctf_dprintf ("Input %i: %s\n", (int) i, ctf_link_input_name (inputs[i]));
+      if (ctf_dynhash_insert (d->cd_input_nums, inputs[i],
+			      (void *) (uintptr_t) i) < 0)
+	{
+	  ctf_set_errno (output, errno);
+	  ctf_err_warn (output, 0, errno, _("ctf_dedup: cannot initialize: %s\n"),
+			ctf_errmsg (errno));
+	  goto err;
+	}
+    }
+
   /* Some flags do not apply when CU-mapping: this is not a duplicated link,
      because there is only one output and we really don't want to end up marking
      all nonconflicting but appears-only-once types as conflicting (which in the
@@ -1937,6 +1956,10 @@ ctf_dedup (ctf_dict_t *output, ctf_dict_t **inputs, uint32_t ninputs,
 	return -1;				/* errno is set for us.  */
     }
   return 0;
+
+ err:
+  ctf_dedup_fini (output, NULL, 0);
+  return -1;
 }
 
 static int
@@ -3003,100 +3026,6 @@ ctf_dedup_emit_struct_members (ctf_dict_t *output, ctf_dict_t **inputs,
   return ctf_set_errno (output, err);
 }
 
-/* Populate the type mapping used by the types in one FP (which must be an input
-   dict containing a non-null cd_output resulting from a ctf_dedup_emit_type
-   walk).  */
-static int
-ctf_dedup_populate_type_mapping (ctf_dict_t *shared, ctf_dict_t *fp,
-				 ctf_dict_t **inputs)
-{
-  ctf_dedup_t *d = &shared->ctf_dedup;
-  ctf_dict_t *output = fp->ctf_dedup.cd_output;
-  const void *k, *v;
-  ctf_next_t *i = NULL;
-  int err;
-
-  /* The shared dict (the output) stores its types in the fp itself, not in a
-     separate cd_output dict.  */
-  if (shared == fp)
-    output = fp;
-
-  /* There may be no types to emit at all, or all the types in this TU may be
-     shared.  */
-  if (!output || !output->ctf_dedup.cd_output_emission_hashes)
-    return 0;
-
-  while ((err = ctf_dynhash_cnext (output->ctf_dedup.cd_output_emission_hashes,
-				  &i, &k, &v)) == 0)
-    {
-      const char *hval = (const char *) k;
-      ctf_id_t id_out = (ctf_id_t) (uintptr_t) v;
-      ctf_next_t *j = NULL;
-      ctf_dynset_t *type_ids;
-      const void *id;
-
-      type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hval);
-      if (!ctf_assert (shared, type_ids))
-	return -1;
-#ifdef ENABLE_LIBCTF_HASH_DEBUGGING
-      ctf_dprintf ("Traversing emission hash: hval %s\n", hval);
-#endif
-
-      while ((err = ctf_dynset_cnext (type_ids, &j, &id)) == 0)
-	{
-	  ctf_dict_t *input = inputs[CTF_DEDUP_GID_TO_INPUT (id)];
-	  ctf_id_t id_in = CTF_DEDUP_GID_TO_TYPE (id);
-
-#ifdef ENABLE_LIBCTF_HASH_DEBUGGING
-	  ctf_dprintf ("Adding mapping from %i/%lx to %lx\n",
-		       CTF_DEDUP_GID_TO_INPUT (id), id_in, id_out);
-#endif
-	  ctf_add_type_mapping (input, id_in, output, id_out);
-	}
-      if (err != ECTF_NEXT_END)
-	{
-	  ctf_next_destroy (i);
-	  goto err;
-	}
-    }
-  if (err != ECTF_NEXT_END)
-    goto err;
-
-  return 0;
-
- err:
-  ctf_err_warn (shared, 0, err, _("iteration error populating the type mapping"));
-  return ctf_set_errno (shared, err);
-}
-
-/* Populate the type mapping machinery used by the rest of the linker,
-   by ctf_add_type, etc.  */
-static int
-ctf_dedup_populate_type_mappings (ctf_dict_t *output, ctf_dict_t **inputs,
-				  uint32_t ninputs)
-{
-  size_t i;
-
-  if (ctf_dedup_populate_type_mapping (output, output, inputs) < 0)
-    {
-      ctf_err_warn (output, 0, 0, _("cannot populate type mappings for shared "
-				    "CTF dict"));
-      return -1;				/* errno is set for us.  */
-    }
-
-  for (i = 0; i < ninputs; i++)
-    {
-      if (ctf_dedup_populate_type_mapping (output, inputs[i], inputs) < 0)
-	{
-	  ctf_err_warn (output, 0, ctf_errno (inputs[i]),
-			_("cannot populate type mappings for per-CU CTF dict"));
-	  return ctf_set_errno (output, ctf_errno (inputs[i]));
-	}
-    }
-
-  return 0;
-}
-
 /* Emit deduplicated types into the outputs.  The shared type repository is
    OUTPUT, on which the ctf_dedup function must have already been called.  The
    PARENTS array contains the INPUTS index of the parent dict for every child
@@ -3127,9 +3056,6 @@ ctf_dedup_emit (ctf_dict_t *output, ctf_dict_t **inputs, uint32_t ninputs,
   if (ctf_dedup_emit_struct_members (output, inputs, ninputs, parents) < 0)
     return NULL;				/* errno is set for us.  */
 
-  if (ctf_dedup_populate_type_mappings (output, inputs, ninputs) < 0)
-    return NULL;				/* errno is set for us.  */
-
   for (i = 0; i < ninputs; i++)
     {
       if (inputs[i]->ctf_dedup.cd_output)
@@ -3163,6 +3089,76 @@ ctf_dedup_emit (ctf_dict_t *output, ctf_dict_t **inputs, uint32_t ninputs,
 	}
     }
 
-  ctf_dedup_fini (output, outputs, num_outputs);
   return outputs;
 }
+
+/* Determine what type SRC_FP / SRC_TYPE was emitted as in the FP, which
+   must be the shared dict or have it as a parent: return 0 if none.  The SRC_FP
+   must be a past input to ctf_dedup.  */
+
+ctf_id_t
+ctf_dedup_type_mapping (ctf_dict_t *fp, ctf_dict_t *src_fp, ctf_id_t src_type)
+{
+  ctf_dict_t *output = NULL;
+  ctf_dedup_t *d;
+  int input_num;
+  void *num_ptr;
+  void *type_ptr;
+  int found;
+  const char *hval;
+
+  /* It is an error (an internal error in the caller, in ctf-link.c) to call
+     this with an FP that is not a per-CU output or shared output dict, or with
+     a SRC_FP that was not passed to ctf_dedup as an input; it is an internal
+     error in ctf-dedup for the type passed not to have been hashed, though if
+     the src_fp is a child dict and the type is not a child type, it will have
+     been hashed under the GID corresponding to the parent.  */
+
+  if (fp->ctf_dedup.cd_type_hashes != NULL)
+    output = fp;
+  else if (fp->ctf_parent && fp->ctf_parent->ctf_dedup.cd_type_hashes != NULL)
+    output = fp->ctf_parent;
+  else
+    {
+      ctf_set_errno (fp, ECTF_INTERNAL);
+      ctf_err_warn (fp, 0, ECTF_INTERNAL,
+		    _("dict %p passed to ctf_dedup_type_mapping is not a "
+		      "deduplicated output"), (void *) fp);
+      return CTF_ERR;
+    }
+
+  if (src_fp->ctf_parent && ctf_type_isparent (src_fp, src_type))
+    src_fp = src_fp->ctf_parent;
+
+  d = &output->ctf_dedup;
+
+  found = ctf_dynhash_lookup_kv (d->cd_input_nums, src_fp, NULL, &num_ptr);
+  if (!ctf_assert (output, found != 0))
+    return CTF_ERR;				/* errno is set for us.  */
+  input_num = (uintptr_t) num_ptr;
+
+  hval = ctf_dynhash_lookup (d->cd_type_hashes,
+			     CTF_DEDUP_GID (output, input_num, src_type));
+
+  if (!ctf_assert (output, hval != NULL))
+    return CTF_ERR;				/* errno is set for us.  */
+
+  /* The emission hashes may be unset if this dict was created after
+     deduplication to house variables or other things that would conflict if
+     stored in the shared dict.  */
+  if (fp->ctf_dedup.cd_output_emission_hashes)
+    if (ctf_dynhash_lookup_kv (fp->ctf_dedup.cd_output_emission_hashes, hval,
+			       NULL, &type_ptr))
+      return (ctf_id_t) (uintptr_t) type_ptr;
+
+  if (fp->ctf_parent)
+    {
+      ctf_dict_t *pfp = fp->ctf_parent;
+      if (pfp->ctf_dedup.cd_output_emission_hashes)
+	if (ctf_dynhash_lookup_kv (pfp->ctf_dedup.cd_output_emission_hashes,
+				   hval, NULL, &type_ptr))
+	  return (ctf_id_t) (uintptr_t) type_ptr;
+    }
+
+  return 0;
+}
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index a6e1da5..78a41ff 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -347,6 +347,11 @@ typedef struct ctf_dedup
   /* A set (a hash) of hash values of conflicting types.  */
   ctf_dynset_t *cd_conflicting_types;
 
+  /* A hash mapping fp *'s of inputs to their input_nums.  Used only by
+     functions outside the core ctf_dedup / ctf_dedup_emit machinery which do
+     not take an inputs array.  */
+  ctf_dynhash_t *cd_input_nums;
+
   /* Maps type hashes to ctf_id_t's in this dictionary.  Populated only at
      emission time, in the dictionary where emission is taking place.  */
   ctf_dynhash_t *cd_output_emission_hashes;
@@ -455,9 +460,8 @@ struct ctf_dict
   ctf_dynhash_t *ctf_link_inputs; /* Inputs to this link.  */
   ctf_dynhash_t *ctf_link_outputs; /* Additional outputs from this link.  */
 
-  /* Map input types to output types: populated in each output dict.
-     Key is a ctf_link_type_key_t: value is a type ID.  Used by
-     nondeduplicating links and ad-hoc ctf_add_type calls only.  */
+  /* Map input types to output types for ctf_add_type.  Key is a
+     ctf_link_type_key_t: value is a type ID.  */
   ctf_dynhash_t *ctf_link_type_mapping;
 
   /* Map input CU names to output CTF dict names: populated in the top-level
@@ -703,11 +707,6 @@ extern ctf_id_t ctf_add_encoded (ctf_dict_t *, uint32_t, const char *,
 extern ctf_id_t ctf_add_reftype (ctf_dict_t *, uint32_t, ctf_id_t,
 				 uint32_t kind);
 
-extern void ctf_add_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type,
-				  ctf_dict_t *dst_fp, ctf_id_t dst_type);
-extern ctf_id_t ctf_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type,
-				  ctf_dict_t **dst_fp);
-
 extern int ctf_dedup_atoms_init (ctf_dict_t *);
 extern int ctf_dedup (ctf_dict_t *, ctf_dict_t **, uint32_t ninputs,
 		      uint32_t *parents, int cu_mapped);
@@ -715,6 +714,8 @@ extern void ctf_dedup_fini (ctf_dict_t *, ctf_dict_t **, uint32_t);
 extern ctf_dict_t **ctf_dedup_emit (ctf_dict_t *, ctf_dict_t **,
 				    uint32_t ninputs, uint32_t *parents,
 				    uint32_t *noutputs, int cu_mapped);
+extern ctf_id_t ctf_dedup_type_mapping (ctf_dict_t *fp, ctf_dict_t *src_fp,
+					ctf_id_t src_type);
 
 extern void ctf_decl_init (ctf_decl_t *);
 extern void ctf_decl_fini (ctf_decl_t *);
diff --git a/libctf/ctf-link.c b/libctf/ctf-link.c
index d598b78..c0b0916 100644
--- a/libctf/ctf-link.c
+++ b/libctf/ctf-link.c
@@ -24,118 +24,18 @@
 #pragma weak ctf_open
 #endif
 
-/* Type tracking machinery.  */
-
-/* Record the correspondence between a source and ctf_add_type()-added
-   destination type: both types are translated into parent type IDs if need be,
-   so they relate to the actual dictionary they are in.  Outside controlled
-   circumstances (like linking) it is probably not useful to do more than
-   compare these pointers, since there is nothing stopping the user closing the
-   source dict whenever they want to.
-
-   Our OOM handling here is just to not do anything, because this is called deep
-   enough in the call stack that doing anything useful is painfully difficult:
-   the worst consequence if we do OOM is a bit of type duplication anyway.  */
-
-void
-ctf_add_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type,
-		      ctf_dict_t *dst_fp, ctf_id_t dst_type)
-{
-  if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
-    src_fp = src_fp->ctf_parent;
-
-  src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
-
-  if (LCTF_TYPE_ISPARENT (dst_fp, dst_type) && dst_fp->ctf_parent)
-    dst_fp = dst_fp->ctf_parent;
-
-  dst_type = LCTF_TYPE_TO_INDEX(dst_fp, dst_type);
-
-  if (dst_fp->ctf_link_type_mapping == NULL)
-    {
-      ctf_hash_fun f = ctf_hash_type_key;
-      ctf_hash_eq_fun e = ctf_hash_eq_type_key;
-
-      if ((dst_fp->ctf_link_type_mapping = ctf_dynhash_create (f, e, free,
-							       NULL)) == NULL)
-	return;
-    }
-
-  ctf_link_type_key_t *key;
-  key = calloc (1, sizeof (struct ctf_link_type_key));
-  if (!key)
-    return;
-
-  key->cltk_fp = src_fp;
-  key->cltk_idx = src_type;
-
-  /* No OOM checking needed, because if this doesn't work the worst we'll do is
-     add a few more duplicate types (which will probably run out of memory
-     anyway).  */
-  ctf_dynhash_insert (dst_fp->ctf_link_type_mapping, key,
-		      (void *) (uintptr_t) dst_type);
-}
-
-/* Look up a type mapping: return 0 if none.  The DST_FP is modified to point to
-   the parent if need be.  The ID returned is from the dst_fp's perspective.  */
-ctf_id_t
-ctf_type_mapping (ctf_dict_t *src_fp, ctf_id_t src_type, ctf_dict_t **dst_fp)
-{
-  ctf_link_type_key_t key;
-  ctf_dict_t *target_fp = *dst_fp;
-  ctf_id_t dst_type = 0;
-
-  if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
-    src_fp = src_fp->ctf_parent;
-
-  src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
-  key.cltk_fp = src_fp;
-  key.cltk_idx = src_type;
-
-  if (target_fp->ctf_link_type_mapping)
-    dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
-					       &key);
-
-  if (dst_type != 0)
-    {
-      dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
-				     target_fp->ctf_parent != NULL);
-      *dst_fp = target_fp;
-      return dst_type;
-    }
-
-  if (target_fp->ctf_parent)
-    target_fp = target_fp->ctf_parent;
-  else
-    return 0;
-
-  if (target_fp->ctf_link_type_mapping)
-    dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
-					       &key);
-
-  if (dst_type)
-    dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
-				   target_fp->ctf_parent != NULL);
-
-  *dst_fp = target_fp;
-  return dst_type;
-}
-
-/* Linker machinery.
-
-   CTF linking consists of adding CTF archives full of content to be merged into
+/* CTF linking consists of adding CTF archives full of content to be merged into
    this one to the current file (which must be writable) by calling
-   ctf_link_add_ctf().  Once this is done, a call to ctf_link() will merge the
-   type tables together, generating new CTF files as needed, with this one as a
-   parent, to contain types from the inputs which conflict.
-   ctf_link_add_strtab() takes a callback which provides string/offset pairs to
-   be added to the external symbol table and deduplicated from all CTF string
-   tables in the output link; ctf_link_shuffle_syms() takes a callback which
-   provides symtab entries in ascending order, and shuffles the function and
-   data sections to match; and ctf_link_write() emits a CTF file (if there are
-   no conflicts requiring per-compilation-unit sub-CTF files) or CTF archives
-   (otherwise) and returns it, suitable for addition in the .ctf section of the
-   output.  */
+   ctf_link_add_ctf.  Once this is done, a call to ctf_link will merge the type
+   tables together, generating new CTF files as needed, with this one as a
+   parent, to contain types from the inputs which conflict.  ctf_link_add_strtab
+   takes a callback which provides string/offset pairs to be added to the
+   external symbol table and deduplicated from all CTF string tables in the
+   output link; ctf_link_shuffle_syms takes a callback which provides symtab
+   entries in ascending order, and shuffles the function and data sections to
+   match; and ctf_link_write emits a CTF file (if there are no conflicts
+   requiring per-compilation-unit sub-CTF files) or CTF archives (otherwise) and
+   returns it, suitable for addition in the .ctf section of the output.  */
 
 /* Return the name of the compilation unit this CTF dict or its parent applies
    to, or a non-null string otherwise: prefer the parent.  Used in debugging
@@ -151,6 +51,19 @@ ctf_link_input_name (ctf_dict_t *fp)
     return "(unnamed)";
 }
 
+/* Return the cuname of a dict, or the string "unnamed-CU" if none.  */
+
+static const char *
+ctf_unnamed_cuname (ctf_dict_t *fp)
+{
+  const char *cuname = ctf_cuname (fp);
+
+  if (!cuname)
+    cuname = "unnamed-CU";
+
+  return cuname;
+}
+
 /* The linker inputs look like this.  clin_fp is used for short-circuited
    CU-mapped links that can entirely avoid the first link phase in some
    situations in favour of just passing on the contained ctf_dict_t: it is
@@ -279,6 +192,7 @@ ctf_link_add_ctf (ctf_dict_t *fp, ctf_archive_t *ctf, const char *name)
 /* Return a per-CU output CTF dictionary suitable for the given CU, creating and
    interning it if need be.  */
 
+_libctf_nonnull_((1,2))
 static ctf_dict_t *
 ctf_create_per_cu (ctf_dict_t *fp, const char *cu_name)
 {
@@ -429,21 +343,6 @@ ctf_link_set_memb_name_changer (ctf_dict_t *fp,
   fp->ctf_link_memb_name_changer_arg = arg;
 }
 
-typedef struct ctf_link_in_member_cb_arg
-{
-  /* The shared output dictionary.  */
-  ctf_dict_t *out_fp;
-
-  /* The cuname of the input file, and an fp to each dictionary in that file
-     in turn.  */
-  const char *in_cuname;
-  ctf_dict_t *in_fp;
-
-  /* If true, this is the CU-mapped portion of a deduplicating link: no child
-     dictionaries should be created.  */
-  int cu_mapped;
-} ctf_link_in_member_cb_arg_t;
-
 /* Set a function which is used to filter out unwanted variables from the link.  */
 int
 ctf_link_set_variable_filter (ctf_dict_t *fp, ctf_link_variable_filter_f *filter,
@@ -479,23 +378,22 @@ check_variable (const char *name, ctf_dict_t *fp, ctf_id_t type,
   return 0;				      /* Already exists.  */
 }
 
-/* Link one variable in.  */
+/* Link one variable named NAME of type TYPE found in IN_FP into FP.  */
 
 static int
-ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
+ctf_link_one_variable (ctf_dict_t *fp, ctf_dict_t *in_fp, const char *name,
+		       ctf_id_t type, int cu_mapped)
 {
-  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 *insert_fp;
   ctf_dvdef_t *dvd;
 
   /* See if this variable is filtered out.  */
 
-  if (arg->out_fp->ctf_link_variable_filter)
+  if (fp->ctf_link_variable_filter)
     {
-      void *farg = arg->out_fp->ctf_link_variable_filter_arg;
-      if (arg->out_fp->ctf_link_variable_filter (arg->in_fp, name, type, farg))
+      void *farg = fp->ctf_link_variable_filter_arg;
+      if (fp->ctf_link_variable_filter (in_fp, name, type, farg))
 	return 0;
     }
 
@@ -503,25 +401,25 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
      to that first: if it reports a duplicate, or if the type is in a child
      already, add straight to the child.  */
 
-  insert_fp = arg->out_fp;
+  if ((dst_type = ctf_dedup_type_mapping (fp, in_fp, type)) == CTF_ERR)
+    return -1;					/* errno is set for us.  */
 
-  dst_type = ctf_type_mapping (arg->in_fp, type, &insert_fp);
   if (dst_type != 0)
     {
-      if (insert_fp == arg->out_fp)
-	{
-	  if (check_variable (name, insert_fp, dst_type, &dvd))
-	    {
-	      /* No variable here: we can add it.  */
-	      if (ctf_add_variable (insert_fp, name, dst_type) < 0)
-		return (ctf_set_errno (arg->out_fp, ctf_errno (insert_fp)));
-	      return 0;
-	    }
+      if (!ctf_assert (fp, ctf_type_isparent (fp, dst_type)))
+	return -1;				/* errno is set for us.  */
 
-	  /* Already present?  Nothing to do.  */
-	  if (dvd && dvd->dvd_type == dst_type)
-	    return 0;
+      if (check_variable (name, fp, dst_type, &dvd))
+	{
+	  /* No variable here: we can add it.  */
+	  if (ctf_add_variable (fp, name, dst_type) < 0)
+	    return -1; 				/* errno is set for us.  */
+	  return 0;
 	}
+
+      /* Already present?  Nothing to do.  */
+      if (dvd && dvd->dvd_type == dst_type)
+	return 0;
     }
 
   /* Can't add to the parent due to a name clash, or because it references a
@@ -529,29 +427,29 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
      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 (arg->cu_mapped)
+  if (cu_mapped)
     {
       ctf_dprintf ("Variable %s in input file %s depends on a type %lx hidden "
-		   "due to conflicts: skipped.\n", name, arg->in_cuname,
-		   type);
+		   "due to conflicts: skipped.\n", name,
+		   ctf_unnamed_cuname (in_fp), type);
       return 0;
     }
 
-  if ((per_cu_out_fp = ctf_create_per_cu (arg->out_fp, arg->in_cuname)) == NULL)
-    return -1;					/* Errno is set for us.  */
+  if ((per_cu_out_fp = ctf_create_per_cu (fp, ctf_unnamed_cuname (in_fp))) == 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 (arg->in_fp, type, &insert_fp);
+      if ((dst_type = ctf_dedup_type_mapping (per_cu_out_fp,
+					      in_fp, type)) == CTF_ERR)
+	return -1;				/* errno is set for us.   */
 
       if (dst_type == 0)
 	{
-	  ctf_err_warn (arg->out_fp, 1, 0,
-			_("type %lx for variable %s in input file %s "
-			  "not found: skipped"), type, name,
-			arg->in_cuname);
+	  ctf_err_warn (fp, 1, 0, _("type %lx for variable %s in input file %s "
+				    "not found: skipped"), type, name,
+			ctf_unnamed_cuname (in_fp));
 	  /* Do not terminate the link: just skip the variable.  */
 	  return 0;
 	}
@@ -559,21 +457,10 @@ ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
 
   if (check_variable (name, per_cu_out_fp, dst_type, &dvd))
     if (ctf_add_variable (per_cu_out_fp, name, dst_type) < 0)
-      return (ctf_set_errno (arg->out_fp, ctf_errno (per_cu_out_fp)));
+      return (ctf_set_errno (fp, ctf_errno (per_cu_out_fp)));
   return 0;
 }
 
-/* Dump the unnecessary link type mapping after one input file is processed.  */
-static void
-empty_link_type_mapping (void *key _libctf_unused_, void *value,
-			 void *arg _libctf_unused_)
-{
-  ctf_dict_t *fp = (ctf_dict_t *) value;
-
-  if (fp->ctf_link_type_mapping)
-    ctf_dynhash_empty (fp->ctf_link_type_mapping);
-}
-
 /* Lazily open a CTF archive for linking, if not already open.
 
    Returns the number of files contained within the opened archive (0 for none),
@@ -925,21 +812,24 @@ static int
 ctf_link_deduplicating_variables (ctf_dict_t *fp, ctf_dict_t **inputs,
 				  size_t ninputs, int cu_mapped)
 {
-  ctf_link_in_member_cb_arg_t arg;
   size_t i;
 
-  arg.cu_mapped = cu_mapped;
-  arg.out_fp = fp;
-
   for (i = 0; i < ninputs; i++)
     {
-      arg.in_fp = inputs[i];
-      if (ctf_cuname (inputs[i]) != NULL)
-	arg.in_cuname = ctf_cuname (inputs[i]);
-      else
-	arg.in_cuname = "unnamed-CU";
-      if (ctf_variable_iter (arg.in_fp, ctf_link_one_variable, &arg) < 0)
-	return ctf_set_errno (fp, ctf_errno (arg.in_fp));
+      ctf_next_t *it = NULL;
+      ctf_id_t type;
+      const char *name;
+
+      while ((type = ctf_variable_next (inputs[i], &it, &name)) != CTF_ERR)
+	{
+	  if (ctf_link_one_variable (fp, inputs[i], name, type, cu_mapped) < 0)
+	    {
+	      ctf_next_destroy (it);
+	      return -1;			/* errno is set for us.  */
+	    }
+	}
+      if (ctf_errno (inputs[i]) != ECTF_NEXT_END)
+	return ctf_set_errno (fp, ctf_errno (inputs[i]));
     }
   return 0;
 }
@@ -982,40 +872,35 @@ ctf_link_deduplicating_one_symtypetab (ctf_dict_t *fp, ctf_dict_t *input,
   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 = ctf_dedup_type_mapping (fp, input, type)) == CTF_ERR)
+	return -1;				/* errno is set for us.  */
+
       if (dst_type != 0)
 	{
-	  if (insert_fp == fp)
-	    {
-	      sym = check_sym (fp, name, dst_type, functions);
+	  if (!ctf_assert (fp, ctf_type_isparent (fp, dst_type)))
+	    return -1;				/* errno is set for us.  */
 
-	      /* 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;
-		}
+	  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;
 	    }
 	}
 
@@ -1028,24 +913,26 @@ ctf_link_deduplicating_one_symtypetab (ctf_dict_t *fp, ctf_dict_t *input,
 	{
 	  ctf_dprintf ("Symbol %s in input file %s depends on a type %lx "
 		       "hidden due to conflicts: skipped.\n", name,
-		       in_file_name, type);
+		       ctf_unnamed_cuname (input), type);
 	  continue;
 	}
 
-      if ((per_cu_out_fp = ctf_create_per_cu (fp, in_file_name)) == NULL)
+      if ((per_cu_out_fp = ctf_create_per_cu (fp, ctf_unnamed_cuname (input))) == 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 = ctf_dedup_type_mapping (per_cu_out_fp,
+						  input, type)) == CTF_ERR)
+	    return -1;				/* errno is set for us.  */
 
 	  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);
+			      "not found: skipped"), type, name,
+			    ctf_unnamed_cuname (input));
 	      continue;
 	    }
 	}
@@ -1068,7 +955,7 @@ ctf_link_deduplicating_one_symtypetab (ctf_dict_t *fp, ctf_dict_t *input,
 	  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);
+			ctf_unnamed_cuname (input));
 	  return (ctf_set_errno (fp, ECTF_DUPLICATE));
 	}
     }
@@ -1258,6 +1145,8 @@ ctf_link_deduplicating_per_cu (ctf_dict_t *fp)
 	  goto err_inputs_outputs;
 	}
 
+      ctf_dedup_fini (out, outputs, noutputs);
+
       /* 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
@@ -1420,6 +1309,8 @@ ctf_link_deduplicating (ctf_dict_t *fp)
       goto err_clean_outputs;
     }
 
+  ctf_dedup_fini (fp, outputs, noutputs);
+
   /* Now close all the inputs, including per-CU intermediates.  */
 
   if (ctf_link_deduplicating_close_inputs (fp, NULL, inputs, ninputs) < 0)
@@ -1452,12 +1343,9 @@ ctf_link_deduplicating (ctf_dict_t *fp)
 int
 ctf_link (ctf_dict_t *fp, int flags)
 {
-  ctf_link_in_member_cb_arg_t arg;
   ctf_next_t *i = NULL;
   int err;
 
-  memset (&arg, 0, sizeof (struct ctf_link_in_member_cb_arg));
-  arg.out_fp = fp;
   fp->ctf_link_flags = flags;
 
   if (fp->ctf_link_inputs == NULL)
@@ -1503,11 +1391,6 @@ ctf_link (ctf_dict_t *fp, int flags)
 
   ctf_link_deduplicating (fp);
 
-  /* Discard the now-unnecessary mapping table data from all the outputs.  */
-  if (fp->ctf_link_type_mapping)
-    ctf_dynhash_empty (fp->ctf_link_type_mapping);
-  ctf_dynhash_iter (fp->ctf_link_outputs, empty_link_type_mapping, NULL);
-
   fp->ctf_flags &= ~LCTF_LINKING;
   if ((ctf_errno (fp) != 0) && (ctf_errno (fp) != ECTF_NOCTFDATA))
     return -1;
@@ -1537,8 +1420,8 @@ ctf_link_intern_extern_string (void *key _libctf_unused_, void *value,
 /* Repeatedly call ADD_STRING to acquire strings from the external string table,
    adding them to the atoms table for this CU and all subsidiary CUs.
 
-   If ctf_link() is also called, it must be called first if you want the new CTF
-   files ctf_link() can create to get their strings dedupped against the ELF
+   If ctf_link is also called, it must be called first if you want the new CTF
+   files ctf_link can create to get their strings dedupped against the ELF
    strtab properly.  */
 int
 ctf_link_add_strtab (ctf_dict_t *fp, ctf_link_strtab_string_f *add_string,