libctf: actually deduplicate the strtab

This commit finally implements strtab deduplication, putting together all
the pieces assembled in the earlier commits.

The magic is entirely localized to ctf_link_write, which preserializes all
the dicts (parent first), and calls ctf_dedup_strings on the parent.

(The error paths get tweaked a bit too.)

Calling ctf_dedup_strings has implications elsewhere: the lifetime rules for
the inputs versus outputs change a bit now that the child output dicts
contain references to the parent dict's atoms table.  We also pre-purge
movable refs from all the deduplicated strings before freeing any of this
because movable refs contain backreferences into the dict they came from,
which means the parent contains references to all the children!  Purging
the refs first makes those references go away so we can free the children
without creating any wild pointers, even temporarily.

There's a new testcase that identifies a regression whereby offset 0 (the
null string) and index 0 (in children now often the parent dict name,
".ctf") got mixed up, leading to anonymous structs and unions getting the
not entirely C-valid name ".ctf" instead.

May other testcases get adjusted to no longer depend on the precise layout
of the strtab.

TODO: add new tests to verify that strings are actually being deduplicated.

libctf/
	* ctf-link.c (ctf_link_write): Deduplicate strings.
	* ctf-open.c (ctf_dict_close): Free refs, then the link outputs,
        then the out cu_mapping, then the inputs, in that order.
        * ctf-string.c (ctf_str_purge_refs): Not static any more.
	* ctf-impl.h: Declare it.

ld/
	* testsuite/ld-ctf/conflicting-cycle-2.A-1.d: Don't depend on
        strtab contents.
	* testsuite/ld-ctf/conflicting-cycle-2.A-2.d: Likewise.
	* testsuite/ld-ctf/conflicting-cycle-2.parent.d: Likewise.
	* testsuite/ld-ctf/conflicting-cycle-3.C-1.d: Likewise.
	* testsuite/ld-ctf/conflicting-cycle-3.C-2.d: Likewise.
	* testsuite/ld-ctf/anonymous-conflicts*: New test.

12 files changed, 101 insertions, 15 deletions

diff --git a/ld/testsuite/ld-ctf/anonymous-conflicts-B.c b/ld/testsuite/ld-ctf/anonymous-conflicts-B.c
new file mode 100644
index 0000000..97df8a7
--- /dev/null
+++ b/ld/testsuite/ld-ctf/anonymous-conflicts-B.c
@@ -0,0 +1,10 @@
+struct A
+{
+  union
+  {
+    long a;
+  };
+  int b;
+};
+
+static struct A a __attribute__((used));
diff --git a/ld/testsuite/ld-ctf/anonymous-conflicts.c b/ld/testsuite/ld-ctf/anonymous-conflicts.c
new file mode 100644
index 0000000..b117721
--- /dev/null
+++ b/ld/testsuite/ld-ctf/anonymous-conflicts.c
@@ -0,0 +1,10 @@
+struct A
+{
+  union
+  {
+    int a;
+  };
+  int b;
+};
+
+static struct A a __attribute__((used));
diff --git a/ld/testsuite/ld-ctf/anonymous-conflicts.d b/ld/testsuite/ld-ctf/anonymous-conflicts.d
new file mode 100644
index 0000000..2869a0f
--- /dev/null
+++ b/ld/testsuite/ld-ctf/anonymous-conflicts.d
@@ -0,0 +1,21 @@
+#as:
+#source: anonymous-conflicts.c
+#source: anonymous-conflicts-B.c
+#objdump: --ctf
+#ld: -shared --ctf-variables
+#name: Conflicted anonymous struct/union names
+
+.*: +file format .*
+
+Contents of CTF section .ctf:
+
+  Header:
+    Magic number: 0xdff2
+    Version: 5 \(CTF_VERSION_4\)
+#...
+    0x[0-9a-f]*: \(kind 6\) struct A \(.*
+                \[0x0\] : ID 0x[0-9a-f]*: \(kind 7\) union  \(.*
+#...
+    0x[0-9a-f]*: \(kind 6\) struct A \(.*
+                \[0x0\] : ID 0x[0-9a-f]*: \(kind 7\) union  \(.*
+#...
diff --git a/ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d b/ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d
index 770ef99..fa3c21e 100644
--- a/ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d
+++ b/ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d
@@ -36,5 +36,4 @@ CTF archive member: .*/A.c:
         *\[0x0\] b: ID 0x[0-9a-f]*: \(kind 3\) struct B \* \(size 0x[0-9a-f]*\) \(aligned at 0x[0-9a-f]*\)
 
   Strings:
-    0x0: 
 #...
diff --git a/ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d b/ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d
index d71c5ba..7721080 100644
--- a/ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d
+++ b/ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d
@@ -37,5 +37,4 @@ CTF archive member: .*/A-2.c:
         *\[0x[0-9a-f]*\] wombat: ID 0x[0-9a-f]*: \(kind 1\) int \(format 0x1\) \(size 0x[0-9a-f]*\) \(aligned at 0x[0-9a-f]*\)
 
   Strings:
-    0x0: 
 #...
diff --git a/ld/testsuite/ld-ctf/conflicting-cycle-2.parent.d b/ld/testsuite/ld-ctf/conflicting-cycle-2.parent.d
index f7427e3..14014cb 100644
--- a/ld/testsuite/ld-ctf/conflicting-cycle-2.parent.d
+++ b/ld/testsuite/ld-ctf/conflicting-cycle-2.parent.d
@@ -19,7 +19,7 @@ Contents of CTF section .ctf:
     Version: 5 \(CTF_VERSION_4\)
 #...
     Type section:	.* \(0x94 bytes\)
-    String section:	.* \(0x1d bytes\)
+    String section:	.*
 
   Labels:
 
diff --git a/ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d b/ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d
index 6f42a49..6180df2 100644
--- a/ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d
+++ b/ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d
@@ -35,5 +35,4 @@ CTF archive member: .*/C.c:
         *\[0x0\] a: ID 0x[0-9a-f]*: \(kind 3\) struct A \* \(size 0x[0-9a-f]*\) \(aligned at 0x[0-9a-f]*\)
 
   Strings:
-    0x0: 
 #...
diff --git a/ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d b/ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d
index 55d9db6..a0dac55 100644
--- a/ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d
+++ b/ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d
@@ -36,5 +36,4 @@ CTF archive member: .*/C-2.c:
                 \[0x[0-9a-f]*\] wombat: ID 0x[0-9a-f]*: \(kind 1\) int \(format 0x1\) \(size 0x[0-9a-f]*\) \(aligned at 0x[0-9a-f]*\)
 
   Strings:
-    0x0: 
 #...
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index b15b37c..76eed06 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -769,6 +769,7 @@ extern uint32_t ctf_str_add_movable_ref (ctf_dict_t *, const char *,
 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_purge_refs (ctf_dict_t *fp);
 extern void ctf_str_rollback (ctf_dict_t *, ctf_snapshot_id_t);
 extern const ctf_strs_writable_t *ctf_str_write_strtab (ctf_dict_t *);
 
diff --git a/libctf/ctf-link.c b/libctf/ctf-link.c
index 04403df..b3e416f 100644
--- a/libctf/ctf-link.c
+++ b/libctf/ctf-link.c
@@ -1826,7 +1826,7 @@ typedef struct ctf_name_list_accum_cb_arg
   char **names;
   ctf_dict_t *fp;
   ctf_dict_t **files;
-  size_t i;
+  ssize_t i;
   char **dynames;
   size_t ndynames;
 } ctf_name_list_accum_cb_arg_t;
@@ -1961,11 +1961,12 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
   char *transformed_name = NULL;
   ctf_dict_t **files;
   FILE *f = NULL;
-  size_t i;
+  ssize_t i;
   int err;
   long fsize;
   const char *errloc;
   unsigned char *buf = NULL;
+  uint64_t old_parent_strlen, all_strlens = 0;
 
   memset (&arg, 0, sizeof (ctf_name_list_accum_cb_arg_t));
   arg.fp = fp;
@@ -1983,7 +1984,7 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
 	}
     }
 
-  /* No extra outputs? Just write a simple ctf_dict_t.  */
+  /* No extra outputs?  Just write a simple ctf_dict_t.  */
   if (arg.i == 0)
     {
       unsigned char *ret = ctf_write_mem (fp, size, threshold);
@@ -1992,7 +1993,9 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
     }
 
   /* Writing an archive.  Stick ourselves (the shared repository, parent of all
-     other archives) on the front of it with the default name.  */
+     other archives) on the front of it with the default name.  (Writing the parent
+     dict out first is essential for strings in child dicts shared with the parent
+     to get their proper offsets.)  */
   if ((names = realloc (arg.names, sizeof (char *) * (arg.i + 1))) == NULL)
     {
       errloc = "name reallocation";
@@ -2034,6 +2037,39 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
   memmove (&(arg.files[1]), arg.files, sizeof (ctf_dict_t *) * (arg.i));
   arg.files[0] = fp;
 
+  /* Preserialize everything, doing everything but strtab generation and things that
+     depend on that.  */
+  for (i = 0; i < arg.i + 1; i++)
+    {
+      if (ctf_preserialize (arg.files[i]) < 0)
+	{
+	  errno = ctf_errno (arg.files[i]);
+	  for (i--; i >= 0; i--)
+	    ctf_depreserialize (arg.files[i]);
+	  errloc = "preserialization";
+	  goto err_no;
+	}
+    }
+
+  ctf_dprintf ("Deduplicating strings.\n");
+
+  for (i = 0; i < arg.i; i++)
+    all_strlens += arg.files[i]->ctf_str_prov_offset;
+  old_parent_strlen = arg.files[0]->ctf_str_prov_offset;
+
+  if (ctf_dedup_strings (fp) < 0)
+    {
+      for (i = 0; i < arg.i + 1; i++)
+	ctf_depreserialize (arg.files[i]);
+      errloc = "string deduplication";
+      goto err_str_dedup;
+    }
+
+  ctf_dprintf ("Deduplicated strings: original parent strlen: %zu; "
+	       "original lengths: %zu; final length: %zu.\n",
+	       (size_t) old_parent_strlen, (size_t) all_strlens,
+	       (size_t) arg.files[0]->ctf_str_prov_offset);
+
   if ((f = tmpfile ()) == NULL)
     {
       errloc = "tempfile creation";
@@ -2045,8 +2081,8 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
 			       threshold)) < 0)
     {
       errloc = "archive writing";
-      ctf_set_errno (fp, err);
-      goto err;
+      errno = err;
+      goto err_no;
     }
 
   if (fseek (f, 0, SEEK_END) < 0)
@@ -2105,7 +2141,7 @@ ctf_link_write (ctf_dict_t *fp, size_t *size, size_t threshold)
 
  err_no:
   ctf_set_errno (fp, errno);
-
+ err_str_dedup:
   /* Turn off the is-linking flag on all the dicts in this link, as above.  */
   for (i = 0; i < arg.i; i++)
     {
diff --git a/libctf/ctf-open.c b/libctf/ctf-open.c
index 9e96d1f..32c0338 100644
--- a/libctf/ctf-open.c
+++ b/libctf/ctf-open.c
@@ -2013,6 +2013,20 @@ ctf_dict_close (ctf_dict_t *fp)
       free (did);
     }
 
+  /* The lifetime rules here are delicate.  We must destroy the outputs before
+     the atoms (since in a link the outputs contain references to the parent's
+     atoms), but we must destroy the inputs after that (since many type strings
+     ultimately come from the inputs).  In addition, if there are
+     ctf_link_outputs, the parent dict's atoms table may have movable refs that
+     refer to the outputs: so purge the refs first, including the movable
+     ones.  */
+
+  if (fp->ctf_link_outputs && ctf_dynhash_elements (fp->ctf_link_outputs) > 0)
+    ctf_str_purge_refs (fp);
+
+  ctf_dynhash_destroy (fp->ctf_link_outputs);
+  ctf_dynhash_destroy (fp->ctf_link_out_cu_mapping);
+
   ctf_str_free_atoms (fp);
   free (fp->ctf_tmp_typeslice);
 
@@ -2031,10 +2045,8 @@ ctf_dict_close (ctf_dict_t *fp)
 
   ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
   ctf_dynhash_destroy (fp->ctf_link_inputs);
-  ctf_dynhash_destroy (fp->ctf_link_outputs);
   ctf_dynhash_destroy (fp->ctf_link_type_mapping);
   ctf_dynhash_destroy (fp->ctf_link_in_cu_mapping);
-  ctf_dynhash_destroy (fp->ctf_link_out_cu_mapping);
   ctf_dynhash_destroy (fp->ctf_add_processing);
   ctf_dedup_fini (fp, NULL, 0);
   ctf_dynset_destroy (fp->ctf_dedup_atoms_alloc);
diff --git a/libctf/ctf-string.c b/libctf/ctf-string.c
index 3c5a468..3fab192 100644
--- a/libctf/ctf-string.c
+++ b/libctf/ctf-string.c
@@ -682,7 +682,7 @@ ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 }
 
 /* Remove all the recorded refs from the atoms table.  */
-static void
+void
 ctf_str_purge_refs (ctf_dict_t *fp)
 {
   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);