[PATCH 15/19] libctf: map from old to corresponding newly-added types in ctf_add_type

[Nick Alcock <nick dot alcock at oracle dot com>]

This lets you call ctf_type_mapping (dest_fp, src_fp, src_type_id)
and get told what type ID the corresponding type has in the target
ctf_file_t.  This works even if it was added by a recursive call, and
because it is stored in the target ctf_file_t it works even if we
had to add one type to multiple ctf_file_t's as part of conflicting
type handling.

We only empty out this mapping at ctf_file_close time, because it is
perfectly valid to call ctf_link repeatedly, or to call it after calling
ctf_file_write: we have to keep tracking these types until the types
themselves are thrown away.

libctf/
	* ctf-impl.h (ctf_file_t): New field ctf_link_type_mapping.
	(struct ctf_link_type_mapping_key): New.
	(ctf_hash_type_mapping_key): Likewise.
	(ctf_hash_eq_type_mapping_key): Likewise.
	(ctf_add_type_mapping): Likewise.
	(ctf_type_mapping): Likewise.
	* ctf-open.c (ctf_file_close): Update accordingly.
	* ctf-create.c (ctf_update): Likewise.
	(ctf_add_type): Populate the mapping.
	* ctf-hash.c (ctf_hash_type_mapping_key): Hash a type mapping key.
	(ctf_hash_eq_type_mapping_key): Check the key for equality.
	(ctf_dynhash_insert): Fix comment typo.
	* ctf-link.c (ctf_add_type_mapping): New.
	(ctf_type_mapping): Likewise.
---
 libctf/ctf-create.c | 15 ++++++-
 libctf/ctf-hash.c   | 24 ++++++++++-
 libctf/ctf-impl.h   | 19 +++++++++
 libctf/ctf-link.c   | 97 +++++++++++++++++++++++++++++++++++++++++++++
 libctf/ctf-open.c   |  1 +
 5 files changed, 153 insertions(+), 3 deletions(-)

diff --git a/libctf/ctf-create.c b/libctf/ctf-create.c
index e3d5b22f17..1a72128878 100644
--- a/libctf/ctf-create.c
+++ b/libctf/ctf-create.c
@@ -457,6 +457,7 @@ ctf_update (ctf_file_t *fp)
   nfp->ctf_specific = fp->ctf_specific;
   nfp->ctf_link_inputs = fp->ctf_link_inputs;
   nfp->ctf_link_outputs = fp->ctf_link_outputs;
+  nfp->ctf_link_type_mapping = fp->ctf_link_type_mapping;
 
   nfp->ctf_snapshot_lu = fp->ctf_snapshots;
 
@@ -468,6 +469,7 @@ ctf_update (ctf_file_t *fp)
   memset (&fp->ctf_dtdefs, 0, sizeof (ctf_list_t));
   fp->ctf_link_inputs = NULL;
   fp->ctf_link_outputs = NULL;
+  fp->ctf_link_type_mapping = NULL;
 
   fp->ctf_dvhash = NULL;
   memset (&fp->ctf_dvdefs, 0, sizeof (ctf_list_t));
@@ -1540,6 +1542,7 @@ ctf_add_type (ctf_file_t *dst_fp, ctf_file_t *src_fp, ctf_id_t src_type)
   ctf_funcinfo_t ctc;
 
   ctf_hash_t *hp;
+  ctf_id_t orig_src_type = src_type;
 
   if (!(dst_fp->ctf_flags & LCTF_RDWR))
     return (ctf_set_errno (dst_fp, ECTF_RDONLY));
@@ -1623,7 +1626,10 @@ ctf_add_type (ctf_file_t *dst_fp, ctf_file_t *src_fp, ctf_id_t src_type)
 	      if (memcmp (&src_en, &dst_en, sizeof (ctf_encoding_t)) == 0)
 		{
 		  if (kind != CTF_K_SLICE)
-		    return dst_type;
+		    {
+		      ctf_add_type_mapping (src_fp, src_type, dst_fp, dst_type);
+		      return dst_type;
+		    }
 		}
 	      else
 		  {
@@ -1681,7 +1687,10 @@ ctf_add_type (ctf_file_t *dst_fp, ctf_file_t *src_fp, ctf_id_t src_type)
 	      if (match && sroot == droot)
 		{
 		  if (kind != CTF_K_SLICE)
-		    return dtd->dtd_type;
+		    {
+		      ctf_add_type_mapping (src_fp, src_type, dst_fp, dst_type);
+		      return dtd->dtd_type;
+		    }
 		}
 	      else if (!match && sroot && droot)
 		{
@@ -1922,6 +1931,8 @@ ctf_add_type (ctf_file_t *dst_fp, ctf_file_t *src_fp, ctf_id_t src_type)
       return (ctf_set_errno (dst_fp, ECTF_CORRUPT));
     }
 
+  if (dst_type != CTF_ERR)
+    ctf_add_type_mapping (src_fp, orig_src_type, dst_fp, dst_type);
   return dst_type;
 }
 
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index 12bd6ef9b9..624e8084ef 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -82,6 +82,28 @@ ctf_hash_eq_string (const void *a, const void *b)
   return !strcmp((const char *) hep_a->key, (const char *) hep_b->key);
 }
 
+/* Hash a type_mapping_key.  */
+unsigned int
+ctf_hash_type_mapping_key (const void *ptr)
+{
+  ctf_helem_t *hep = (ctf_helem_t *) ptr;
+  ctf_link_type_mapping_key_t *k = (ctf_link_type_mapping_key_t *) hep->key;
+
+  return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx);
+}
+
+int
+ctf_hash_eq_type_mapping_key (const void *a, const void *b)
+{
+  ctf_helem_t *hep_a = (ctf_helem_t *) a;
+  ctf_helem_t *hep_b = (ctf_helem_t *) b;
+  ctf_link_type_mapping_key_t *key_a = (ctf_link_type_mapping_key_t *) hep_a->key;
+  ctf_link_type_mapping_key_t *key_b = (ctf_link_type_mapping_key_t *) hep_b->key;
+
+  return (key_a->cltm_fp == key_b->cltm_fp)
+    && (key_a->cltm_idx == key_b->cltm_idx);
+}
+
 /* The dynhash, used for hashes whose size is not known at creation time. */
 
 /* Free a single ctf_helem.  */
@@ -164,7 +186,7 @@ ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
     return errno;
 
   /* We need to keep the key_free and value_free around in each item because the
-     del function has no visiblity into the hash as a whole, only into the
+     del function has no visibility into the hash as a whole, only into the
      individual items.  */
 
   slot->key_free = hp->key_free;
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index 088e31c851..0b72866b30 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -204,6 +204,17 @@ typedef struct ctf_str_atom_ref
   uint32_t *caf_ref;		/* A single ref to this string.  */
 } ctf_str_atom_ref_t;
 
+/* The structure used as the key in a ctf_link_type_mapping, which lets the
+   linker machinery determine which type IDs on the input side of a link map to
+   which types on the output side.  (The value is a ctf_id_t: another
+   index, not a type.)  */
+
+typedef struct ctf_link_type_mapping_key
+{
+  ctf_file_t *cltm_fp;
+  ctf_id_t cltm_idx;
+} ctf_link_type_mapping_key_t;
+
 /* The ctf_file is the structure used to represent a CTF container to library
    clients, who see it only as an opaque pointer.  Modifications can therefore
    be made freely to this structure without regard to client versioning.  The
@@ -268,6 +279,7 @@ struct ctf_file
   ctf_archive_t *ctf_archive;	  /* Archive this ctf_file_t came from.  */
   ctf_dynhash_t *ctf_link_inputs; /* Inputs to this link.  */
   ctf_dynhash_t *ctf_link_outputs; /* Additional outputs from this link.  */
+  ctf_dynhash_t *ctf_link_type_mapping; /* Map input types to output types.  */
   char *ctf_tmp_typeslice;	  /* Storage for slicing up type names.  */
   size_t ctf_tmp_typeslicelen;	  /* Size of the typeslice.  */
   void *ctf_specific;		  /* Data for ctf_get/setspecific().  */
@@ -327,10 +339,12 @@ extern const ctf_type_t *ctf_lookup_by_id (ctf_file_t **, ctf_id_t);
 typedef unsigned int (*ctf_hash_fun) (const void *ptr);
 extern unsigned int ctf_hash_integer (const void *ptr);
 extern unsigned int ctf_hash_string (const void *ptr);
+extern unsigned int ctf_hash_type_mapping_key (const void *ptr);
 
 typedef int (*ctf_hash_eq_fun) (const void *, const void *);
 extern int ctf_hash_eq_integer (const void *, const void *);
 extern int ctf_hash_eq_string (const void *, const void *);
+extern int ctf_hash_eq_type_mapping_key (const void *, const void *);
 
 typedef void (*ctf_hash_free_fun) (void *);
 
@@ -370,6 +384,11 @@ extern int ctf_dvd_insert (ctf_file_t *, ctf_dvdef_t *);
 extern void ctf_dvd_delete (ctf_file_t *, ctf_dvdef_t *);
 extern ctf_dvdef_t *ctf_dvd_lookup (const ctf_file_t *, const char *);
 
+extern void ctf_add_type_mapping (ctf_file_t *src_fp, ctf_id_t src_type,
+				  ctf_file_t *dst_fp, ctf_id_t dst_type);
+extern ctf_id_t ctf_type_mapping (ctf_file_t *src_fp, ctf_id_t src_type,
+				  ctf_file_t **dst_fp);
+
 extern void ctf_decl_init (ctf_decl_t *);
 extern void ctf_decl_fini (ctf_decl_t *);
 extern void ctf_decl_push (ctf_decl_t *, ctf_file_t *, ctf_id_t);
diff --git a/libctf/ctf-link.c b/libctf/ctf-link.c
index 8e0f6389a6..1b1a718786 100644
--- a/libctf/ctf-link.c
+++ b/libctf/ctf-link.c
@@ -21,6 +21,103 @@
 #include <string.h>
 
 /* 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 container 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 container 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_file_t *src_fp, ctf_id_t src_type,
+		      ctf_file_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);
+
+  /* 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_mapping_key;
+      ctf_hash_eq_fun e = ctf_hash_eq_type_mapping_key;
+
+      if ((dst_fp->ctf_link_type_mapping = ctf_dynhash_create (f, e, free,
+							       NULL)) == NULL)
+	return;
+    }
+
+  ctf_link_type_mapping_key_t *key;
+  key = calloc (1, sizeof (struct ctf_link_type_mapping_key));
+  if (!key)
+    return;
+
+  key->cltm_fp = src_fp;
+  key->cltm_idx = src_type;
+
+  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_file_t *src_fp, ctf_id_t src_type, ctf_file_t **dst_fp)
+{
+  ctf_link_type_mapping_key_t key;
+  ctf_file_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.cltm_fp = src_fp;
+  key.cltm_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
diff --git a/libctf/ctf-open.c b/libctf/ctf-open.c
index 577681d576..81a068276b 100644
--- a/libctf/ctf-open.c
+++ b/libctf/ctf-open.c
@@ -1601,6 +1601,7 @@ ctf_file_close (ctf_file_t *fp)
 
   ctf_dynhash_destroy (fp->ctf_link_inputs);
   ctf_dynhash_destroy (fp->ctf_link_outputs);
+  ctf_dynhash_destroy (fp->ctf_link_type_mapping);
 
   ctf_free (fp->ctf_sxlate);
   ctf_free (fp->ctf_txlate);
-- 
2.22.0.238.g049a27acdc