libctf: replace 'pending refs' abstraction

A few years ago we introduced a 'pending refs' abstraction to fix one
problem: serializing a dict, then changing it would tend to corrupt the dict
because the strtab sort we do on strtab writeout (to improve compression
efficiency) would modify the offset of any strings that sorted
lexicographically earlier in the strtab: so we added a new restriction that
all strings are added only at serialization time, and maintained a set of
'pending' refs that were added earlier, whose offsets we could update (like
other refs) at writeout time.

This was in hindsight seriously problematic for maintenance (because
serialization has to traverse all strings in all datatypes in the entire
dict), and has become impossible to sustain now that we can read in existing
dicts, modify them, and reserialize them again.  We really don't want to
have to dig through the entire dict we jut read in just in order to dig out
all its strtab offsets, then *change* it, just for the sake of a sort that
adds a frankly trivial amount of compression efficiency.

Sorting *is* still worthwhile -- but it sacrifices very little to only sort
newly-added portions of the strtab, reusing older portions as necessary.
As a first stage in this, discard the whole "pending refs" abstraction and
replace it with "movable" refs, which are exactly like all other refs
(addresses containing the strtab offset of some string, which are updated
wiht the final strtab offset on serialization) except that we track them in
a reverse dict so that we can move the refs around (which we do whenever we
realloc() a buffer containing a bunch of structure members or something when
we add members to the structure).

libctf/

	* ctf-create.c (ctf_add_enumerator): Call ctf_str_move_refs; add
        a movable ref.
	(ctf_add_member_offset): Likewise.
	* ctf-util.c (ctf_realloc): Delete.
	* ctf-serialize.c (ctf_serialize): No longer use it.  Adjust to
	new fields.
	* ctf-string.c (ctf_str_purge_atom_refs): Purge movable refs.
	(ctf_str_free_atom): Free freeable atoms' strings.
	(ctf_str_create_atoms): Create the movable refs dynhash if needed.
	(ctf_str_free_atoms): Destroy it.
	(CTF_STR_MOVABLE): Switch (back) from ints to flags (see previous
	reversion).  Add new flag.
	(aref_create):  New, populate movable refs if need be.
	(ctf_str_add_ref_internal): Switch back to flags, update refs
	directly for nonprovisional strings (with already-known fixed offsets);
	create refs via aref_create.  Allocate strings only if not within an
	mmapped strtab.
	(ctf_str_add_movable_ref): New.
	(ctf_str_add): Adjust to CTF_STR_* reintroduction.
	(ctf_str_add_external): LIkewise.
	(ctf_str_move_refs): New, move refs via ctf_str_movable_refs
	backpointer.
	(ctf_str_purge_refs): Drop ctf_str_num_refs.
	(ctf_str_update_refs): Fix indentation.
	* ctf-impl.h (struct ctf_str_atom_movable): New.
	(struct ctf_dict.ctf_str_num_refs): Drop.
	(struct ctf_dict.ctf_str_movable_refs): New.
	(ctf_str_add_movable_ref): Declare.
	(ctf_str_move_refs): Likewise.
	(ctf_realloc): Drop.

1 files changed, 18 insertions, 3 deletions

diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index c16ef18..f461131 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -207,13 +207,17 @@ typedef struct ctf_err_warning
    removed from this table on ctf_close(), but on every ctf_serialize(), all
    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
 {
-  const char *csa_str;		/* Backpointer to string (hash key).  */
+  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.  */
   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. */
 } ctf_str_atom_t;
 
 /* The refs of a single string in the atoms table.  */
@@ -224,6 +228,15 @@ typedef struct ctf_str_atom_ref
   uint32_t *caf_ref;		/* A single ref to this string.  */
 } ctf_str_atom_ref_t;
 
+  /* Like a ctf_str_atom_ref_t, but specific to movable refs.  */
+
+typedef struct ctf_str_atom_ref_movable
+{
+  ctf_list_t caf_list;		/* List forward/back pointers.  */
+  uint32_t *caf_ref;		/* A single ref to this string.  */
+  ctf_dynhash_t *caf_movable_refs; /* Backpointer to ctf_str_movable_refs for this dict. */  
+} ctf_str_atom_ref_movable_t;
+
 /* A single linker-provided symbol, during symbol addition, possibly before we
    have been given external strtab refs.  */
 typedef struct ctf_in_flight_dynsym
@@ -384,7 +397,7 @@ struct ctf_dict
   ctf_lookup_t ctf_lookups[5];	    /* Pointers to nametabs for name lookup.  */
   ctf_strs_t ctf_str[2];	    /* Array of string table base and bounds.  */
   ctf_dynhash_t *ctf_str_atoms;	  /* Hash table of ctf_str_atoms_t.  */
-  uint64_t ctf_str_num_refs;	  /* Number of refs to cts_str_atoms.  */
+  ctf_dynhash_t *ctf_str_movable_refs; /* Hash table of void * -> ctf_str_atom_ref_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. */
@@ -725,6 +738,9 @@ extern int ctf_str_create_atoms (ctf_dict_t *);
 extern void ctf_str_free_atoms (ctf_dict_t *);
 extern uint32_t ctf_str_add (ctf_dict_t *, const char *);
 extern uint32_t ctf_str_add_ref (ctf_dict_t *, const char *, uint32_t *ref);
+extern uint32_t ctf_str_add_movable_ref (ctf_dict_t *, const char *,
+					 uint32_t *ref);
+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);
@@ -758,7 +774,6 @@ extern void *ctf_mmap (size_t length, size_t offset, int fd);
 extern void ctf_munmap (void *, size_t);
 extern ssize_t ctf_pread (int fd, void *buf, ssize_t count, off_t offset);
 
-extern void *ctf_realloc (ctf_dict_t *, void *, size_t);
 extern char *ctf_str_append (char *, const char *);
 extern char *ctf_str_append_noerr (char *, const char *);