libctf, string: split the movable refs out of the ref list

In commit 149ce5c263616e65 we introduced the concept of "movable" refs,
which are refs that can be moved in batches, to let us maintain valid ref
lists even when adding refs to blocks of memory that can be realloced (which
is any type containing a vlen which can expand, like names contained within
enum or struct members).  Movable refs need a backpointer to the movable
refs dynhash for this dict; since non-movable refs are very common, we tried
to save memory by having a slightly bigger struct for moveable refs with a
backpointer in it, and casting appropriately, indicating which sort of ref
we were dealing with via a flag on the atom.

Unfortunately this doesn't work reliably, because you can perfectly well
have a string ("foo", say) which has both non-movable refs (say, an external
symbol and a variable name) and movable refs (say, a structure member name)
to the same atom.  Indicate which struct we're dealing with with an atom
flag and suddenly you're casting a ctf_str_atom_ref to a
ctf_str_atom_ref_movable (which is bigger) and dereferencing random memory
off the end of it and interpreting it as a backpointer to the movable refs
dynhash.  This is unlikely to work well.

So bite the bullet and split refs into two separate lists, one for movable
refs, one for immovable refs. It means some annoying code duplication, but
there's not very much of it, and it means we can keep the movable refs
hashtab (which in turn means we don't have to do linear searches to find all
relevant refs when moving refs, which in turn means that
structure/union/enum member additions remain amortized O(n) time, not
O(n^2).

Callers can now purge movable and non-movable refs independently of each
other.  We don't use this yet, but a use is coming.

libctf/
	* ctf-impl.h (CTF_STR_ATOM_MOVABLE): Delete.
        (struct ctf_str_atom) [csa_movable_refs]: New.
	(struct ctf_dict): Adjust comment.
	(ctf_str_purge_refs): Add MOVABLE arg.
	* ctf-string.c (ctf_str_purge_movable_atom_refs): Split out of...
        (ctf_str_purge_atom_refs): ... this.
	(ctf_str_free_atom): Call it.
	(ctf_str_purge_one_atom_refs): Likewise.
	(aref_create): Adjust accordingly.
	(ctf_str_move_refs): Likewise.
	(ctf_str_remove_ref): Remove movable refs too, including
	deleting the ref from ctf_str_movable_refs.
	(ctf_str_purge_refs): Add MOVABLE arg.
	(ctf_str_update_refs): Update movable refs.
	(ctf_str_write_strtab): Check, and purge, movable refs.

2 files changed, 47 insertions, 20 deletions

diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index cd93a18..b17a2d8 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -208,13 +208,13 @@ typedef struct ctf_err_warning
    the csa_refs in all entries are purged.  */
 
 #define CTF_STR_ATOM_FREEABLE	0x1
-#define CTF_STR_ATOM_MOVABLE	0x2
 
 typedef struct ctf_str_atom
 {
   char *csa_str;		/* Pointer to string (also used as hash key).  */
   ctf_list_t csa_refs;		/* This string's refs.  */
-  uint32_t csa_offset;		/* Strtab offset, if any.  */
+  ctf_list_t csa_movable_refs;	/* This string's movable refs.  */
+  uint32_t csa_offset;		/* Offset in this strtab, if any.  */
   uint32_t csa_external_offset;	/* External strtab offset, if any.  */
   unsigned long csa_snapshot_id; /* Snapshot ID at time of creation.  */
   int csa_flags;		 /* CTF_STR_ATOM_* flags. */
@@ -393,7 +393,7 @@ struct ctf_dict
   ctf_strs_t ctf_str[2];	    /* Array of string table base and bounds.  */
   ctf_strs_writable_t *ctf_dynstrtab; /* Dynamically allocated string table, if any. */
   ctf_dynhash_t *ctf_str_atoms;	  /* Hash table of ctf_str_atoms_t.  */
-  ctf_dynhash_t *ctf_str_movable_refs; /* Hash table of void * -> ctf_str_atom_ref_t.  */
+  ctf_dynhash_t *ctf_str_movable_refs; /* Hash table of void * -> ctf_str_atom_ref_movable_t.  */
   uint32_t ctf_str_prov_offset;	  /* Latest provisional offset assigned so far.  */
   unsigned char *ctf_base;	  /* CTF file pointer.  */
   unsigned char *ctf_dynbase;	  /* Freeable CTF file pointer. */
@@ -746,7 +746,6 @@ extern int ctf_str_move_refs (ctf_dict_t *fp, void *src, size_t len, void *dest)
 extern int ctf_str_add_external (ctf_dict_t *, const char *, uint32_t offset);
 extern void ctf_str_remove_ref (ctf_dict_t *, const char *, uint32_t *ref);
 extern void ctf_str_rollback (ctf_dict_t *, ctf_snapshot_id_t);
-extern void ctf_str_purge_refs (ctf_dict_t *);
 extern const ctf_strs_writable_t *ctf_str_write_strtab (ctf_dict_t *);
 
 extern struct ctf_archive_internal *
diff --git a/libctf/ctf-string.c b/libctf/ctf-string.c
index 2d96e45..4e1fd62 100644
--- a/libctf/ctf-string.c
+++ b/libctf/ctf-string.c
@@ -109,20 +109,25 @@ static void
 ctf_str_purge_atom_refs (ctf_str_atom_t *atom)
 {
   ctf_str_atom_ref_t *ref, *next;
+  ctf_str_atom_ref_movable_t *movref, *movnext;
 
   for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next)
     {
       next = ctf_list_next (ref);
       ctf_list_delete (&atom->csa_refs, ref);
-      if (atom->csa_flags & CTF_STR_ATOM_MOVABLE)
-	{
-	  ctf_str_atom_ref_movable_t *movref;
-	  movref = (ctf_str_atom_ref_movable_t *) ref;
-	  ctf_dynhash_remove (movref->caf_movable_refs, ref);
-	}
-
       free (ref);
     }
+
+  for (movref = ctf_list_next (&atom->csa_movable_refs);
+       movref != NULL; movref = movnext)
+    {
+      movnext = ctf_list_next (movref);
+      ctf_list_delete (&atom->csa_movable_refs, movref);
+
+      ctf_dynhash_remove (movref->caf_movable_refs, movref);
+
+      free (movref);
+    }
 }
 
 /* Free an atom.  */
@@ -263,9 +268,10 @@ aref_create (ctf_dict_t *fp, ctf_str_atom_t *atom, uint32_t *ref, int flags)
 	  free (aref);
 	  return NULL;
 	}
+      ctf_list_append (&atom->csa_movable_refs, movref);
     }
-
-  ctf_list_append (&atom->csa_refs, aref);
+  else
+    ctf_list_append (&atom->csa_refs, aref);
 
   return aref;
 }
@@ -489,7 +495,7 @@ ctf_str_move_refs (ctf_dict_t *fp, void *src, size_t len, void *dest)
 
   for (p = (uintptr_t) src; p - (uintptr_t) src < len; p++)
     {
-      ctf_str_atom_ref_t *ref;
+      ctf_str_atom_ref_movable_t *ref;
 
       if ((ref = ctf_dynhash_lookup (fp->ctf_str_movable_refs,
 				     (ctf_str_atom_ref_t *) p)) != NULL)
@@ -514,6 +520,7 @@ void
 ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 {
   ctf_str_atom_ref_t *aref, *anext;
+  ctf_str_atom_ref_movable_t *amovref, *amovnext;
   ctf_str_atom_t *atom = NULL;
 
   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
@@ -529,6 +536,18 @@ ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 	  free (aref);
 	}
     }
+
+  for (amovref = ctf_list_next (&atom->csa_movable_refs);
+       amovref != NULL; amovref = amovnext)
+    {
+      amovnext = ctf_list_next (amovref);
+      if (amovref->caf_ref == ref)
+	{
+	  ctf_list_delete (&atom->csa_movable_refs, amovref);
+	  ctf_dynhash_remove (fp->ctf_str_movable_refs, ref);
+	  free (amovref);
+	}
+    }
 }
 
 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
@@ -558,11 +577,12 @@ ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 			     void *arg _libctf_unused_)
 {
   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
+
   ctf_str_purge_atom_refs (atom);
 }
 
 /* Remove all the recorded refs from the atoms table.  */
-void
+static void
 ctf_str_purge_refs (ctf_dict_t *fp)
 {
   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
@@ -573,10 +593,15 @@ static void
 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 {
   ctf_str_atom_ref_t *ref;
+  ctf_str_atom_ref_movable_t *movref;
 
   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
        ref = ctf_list_next (ref))
     *(ref->caf_ref) = value;
+
+  for (movref = ctf_list_next (&refs->csa_movable_refs);
+       movref != NULL; movref = ctf_list_next (movref))
+    *(movref->caf_ref) = value;
 }
 
 /* Sort the strtab.  */
@@ -664,8 +689,9 @@ ctf_str_write_strtab (ctf_dict_t *fp)
       if (!ctf_assert (fp, atom))
 	goto err_strtab;
 
-      if (atom->csa_str[0] == 0 || ctf_list_empty_p (&atom->csa_refs) ||
-	  atom->csa_external_offset)
+      if (atom->csa_str[0] == 0 || atom->csa_external_offset
+	  || (ctf_list_empty_p (&atom->csa_refs)
+	      && ctf_list_empty_p (&atom->csa_movable_refs)))
 	continue;
 
       strtab->cts_len += strlen (atom->csa_str) + 1;
@@ -700,8 +726,9 @@ ctf_str_write_strtab (ctf_dict_t *fp)
       if (!ctf_assert (fp, atom))
 	goto err_sorttab;
 
-      if (atom->csa_str[0] == 0 || ctf_list_empty_p (&atom->csa_refs) ||
-	  atom->csa_external_offset)
+      if (atom->csa_str[0] == 0 || atom->csa_external_offset
+	  || (ctf_list_empty_p (&atom->csa_refs)
+	      && ctf_list_empty_p (&atom->csa_movable_refs)))
 	continue;
 
       sorttab[i++] = atom;
@@ -747,7 +774,8 @@ ctf_str_write_strtab (ctf_dict_t *fp)
       ctf_str_atom_t *atom = (ctf_str_atom_t *) v;
       uint32_t offset;
 
-      if (ctf_list_empty_p (&atom->csa_refs))
+      if (ctf_list_empty_p (&atom->csa_refs) &&
+	  ctf_list_empty_p (&atom->csa_movable_refs))
 	continue;
 
       if (atom->csa_external_offset)