[binutils-gdb] libctf, string: split the movable refs out of the ref list

[binutils-gdb] libctf, string: split the movable refs out of the ref list

[Nick Alcock]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=b404bf7270f9afada6d089624ab5e9b39fcf344c

commit b404bf7270f9afada6d089624ab5e9b39fcf344c
Author: Nick Alcock <nick.alcock@oracle.com>
Date:   Fri Jul 12 12:44:02 2024 +0100

    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.

Diff:
---
 libctf/ctf-impl.h   |  7 +++----
 libctf/ctf-string.c | 60 +++++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 47 insertions(+), 20 deletions(-)

diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index cd93a187aca..b17a2d8699d 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 2d96e45617c..4e1fd620ff1 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)