libctf: fix lookups of pointers by name in parent dicts

When you look up a type by name using ctf_lookup_by_name, in most cases
libctf can just strip off any qualifiers and look for the name, but for
pointer types this doesn't work, since the caller will want the pointer
type itself.  But pointer types are nameless, and while they cite the
types they point to, looking up a type by name requires a link going the
*other way*, from the type pointed to to the pointer type that points to
it.

libctf has always built this up at open time: ctf_ptrtab is an array of
type indexes pointing from the index of every type to the index of the
type that points to it.  But because it is built up at open time (and
because it uses type indexes and not type IDs) it is restricted to
working within a single dict and ignoring parent/child
relationships. This is normally invisible, unless you manage to get a
dict with a type in the parent but the only pointer to it in a child.
The ctf_ptrtab will not track this relationship, so lookups of this
pointer type by name will fail.  Since which type is in the parent and
which in the child is largely opaque to the user (which goes where is up
to the deduplicator, and it can and does reshuffle things to save
space), this leads to a very bad user experience, with an
obviously-visible pointer type which ctf_lookup_by_name claims doesn't
exist.

The fix is to have another array, ctf_pptrtab, which is populated in
child dicts: like the parent's ctf_ptrtab, it has one element per type
in the parent, but is all zeroes except for those types which are
pointed to by types in the child: so it maps parent dict indices to
child dict indices.  The array is grown, and new child types scanned,
whenever a lookup happens and new types have been added to the child
since the last time a lookup happened that might need the pptrtab.
(So for non-writable dicts, this only happens once, since new types
cannot be added to non-writable dicts at all.)

Since this introduces new complexity (involving updating only part of
the ctf_pptrtab) which is only seen when a writable dict is in use, we
introduce a new libctf-writable testsuite that contains lookup tests
with no corresponding CTF-containing .c files (which can thus be run
even on platforms with no .ctf-section support in the linker yet), and
add a test to check that creation of pointers in children to types in
parents and a following lookup by name works as expected.  The non-
writable case is tested in a new libctf-regression testsuite which is
used to track now-fixed outright bugs in libctf.

libctf/ChangeLog
2021-01-05  Nick Alcock  <nick.alcock@oracle.com>

	* ctf-impl.h (ctf_dict_t) <ctf_pptrtab>: New.
	<ctf_pptrtab_len>: New.
	<ctf_pptrtab_typemax>: New.
	* ctf-create.c (ctf_serialize): Update accordingly.
	(ctf_add_reftype): Note that we don't need to update pptrtab here,
	despite updating ptrtab.
	* ctf-open.c (ctf_dict_close): Destroy the pptrtab.
	(ctf_import): Likewise.
	(ctf_import_unref): Likewise.
	* ctf-lookup.c (grow_pptrtab): New.
	(refresh_pptrtab): New, update a pptrtab.
	(ctf_lookup_by_name): Turn into a wrapper around (and rename to)...
	(ctf_lookup_by_name_internal): ... this: construct the pptrtab, and
	use it in addition to the parent's ptrtab when parent dicts are
	searched.
	* testsuite/libctf-regression/regression.exp: New testsuite for
	regression tests.
	* testsuite/libctf-regression/pptrtab*: New test.
	* testsuite/libctf-writable/writable.exp: New testsuite for tests of
	writable CTF dicts.
	* testsuite/libctf-writable/pptrtab*: New test.

8 files changed, 258 insertions, 0 deletions

diff --git a/libctf/testsuite/libctf-regression/pptrtab-a.c b/libctf/testsuite/libctf-regression/pptrtab-a.c
new file mode 100644
index 0000000..e9f656a
--- /dev/null
+++ b/libctf/testsuite/libctf-regression/pptrtab-a.c
@@ -0,0 +1,3 @@
+typedef long a_t;
+
+a_t *a;
diff --git a/libctf/testsuite/libctf-regression/pptrtab-b.c b/libctf/testsuite/libctf-regression/pptrtab-b.c
new file mode 100644
index 0000000..6142f19
--- /dev/null
+++ b/libctf/testsuite/libctf-regression/pptrtab-b.c
@@ -0,0 +1,4 @@
+typedef long a_t;
+
+a_t b;
+
diff --git a/libctf/testsuite/libctf-regression/pptrtab.c b/libctf/testsuite/libctf-regression/pptrtab.c
new file mode 100644
index 0000000..5d3c2f2
--- /dev/null
+++ b/libctf/testsuite/libctf-regression/pptrtab.c
@@ -0,0 +1,54 @@
+#include <ctf-api.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+int
+main (int argc, char *argv[])
+{
+  ctf_dict_t *fp;
+  ctf_archive_t *ctf;
+  ctf_next_t *i = NULL;
+  ctf_id_t type;
+  const char *arcname;
+  char *type_name;
+  int err;
+
+  if (argc != 2)
+    {
+      fprintf (stderr, "Syntax: %s PROGRAM\n", argv[0]);
+      exit(1);
+    }
+
+  if ((ctf = ctf_open (argv[1], NULL, &err)) == NULL)
+    goto open_err;
+
+  /* Make sure we can look up a_t * by name in all non-parent dicts, even though
+     the a_t * and the type it points to are in distinct dicts.  */
+
+  while ((fp = ctf_archive_next (ctf, &i, &arcname, 1, &err)) != NULL)
+    {
+      if ((type = ctf_lookup_by_name (fp, "a_t *")) == CTF_ERR)
+	goto err;
+
+      if (ctf_type_reference (fp, type) == CTF_ERR)
+	goto err;
+
+      printf ("%s: a_t * points to a type of kind %i\n", arcname,
+	      ctf_type_kind (fp, ctf_type_reference (fp, type)));
+
+      ctf_dict_close (fp);
+    }
+  if (err != ECTF_NEXT_END)
+    goto open_err;
+
+  ctf_close (ctf);
+
+  return 0;
+
+ open_err:
+  fprintf (stderr, "%s: cannot open: %s\n", argv[0], ctf_errmsg (err));
+  return 1;
+ err:
+  fprintf (stderr, "Lookup failed in %s: %s\n", arcname, ctf_errmsg (ctf_errno (fp)));
+  return 1;
+}
diff --git a/libctf/testsuite/libctf-regression/pptrtab.lk b/libctf/testsuite/libctf-regression/pptrtab.lk
new file mode 100644
index 0000000..43aae7d
--- /dev/null
+++ b/libctf/testsuite/libctf-regression/pptrtab.lk
@@ -0,0 +1,4 @@
+# source: pptrtab-a.c
+# source: pptrtab-b.c
+# link_flags: -Wl,--ctf-share-types=share-duplicated
+.*/pptrtab-[ab]\.c: .* points to a type of kind 10
diff --git a/libctf/testsuite/libctf-regression/regression.exp b/libctf/testsuite/libctf-regression/regression.exp
new file mode 100644
index 0000000..51ad257
--- /dev/null
+++ b/libctf/testsuite/libctf-regression/regression.exp
@@ -0,0 +1,43 @@
+# Copyright (C) 2021 Free Software Foundation, Inc.
+#
+# This file is part of the GNU Binutils.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+# MA 02110-1301, USA.
+#
+
+if ![is_elf_format] {
+    unsupported "CTF needs bfd changes to be emitted on non-ELF"
+    return 0
+}
+
+if {[info exists env(LC_ALL)]} {
+    set old_lc_all $env(LC_ALL)
+}
+set env(LC_ALL) "C"
+
+set ctf_test_list [lsort [glob -nocomplain $srcdir/$subdir/*.lk]]
+
+foreach ctf_test $ctf_test_list {
+    verbose [file rootname $ctf_test]
+    verbose running lookup test on $ctf_test
+    run_lookup_test [file rootname $ctf_test]
+}
+
+if {[info exists old_lc_all]} {
+    set env(LC_ALL) $old_lc_all
+} else {
+    unset env(LC_ALL)
+}
diff --git a/libctf/testsuite/libctf-writable/pptrtab.c b/libctf/testsuite/libctf-writable/pptrtab.c
new file mode 100644
index 0000000..68c3563
--- /dev/null
+++ b/libctf/testsuite/libctf-writable/pptrtab.c
@@ -0,0 +1,109 @@
+#include <ctf-api.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+int
+main (int argc, char *argv[])
+{
+  ctf_dict_t *pfp;
+  ctf_dict_t *cfp;
+  ctf_id_t base, base2, ptr, ptr2, type, last_type;
+  ctf_encoding_t encoding = { CTF_INT_SIGNED, 0, sizeof (int) };
+  ctf_encoding_t encoding2 = { CTF_INT_SIGNED, 0, sizeof (long) };
+  char *type_name;
+  int err;
+
+  if ((pfp = ctf_create (&err)) == NULL)
+    goto create_err;
+
+  if ((cfp = ctf_create (&err)) == NULL)
+    goto create_err;
+
+  if (ctf_import (cfp, pfp) < 0)
+    goto create_child;
+
+  /* First, try an int in the parent with a pointer in the child.  Also make
+     another pair of types we will chain to later: these end up before the
+     pptrtab lazy-update watermark.  */
+
+  if ((base = ctf_add_integer (pfp, CTF_ADD_ROOT, "int", &encoding)) == CTF_ERR)
+    goto create_parent;
+
+  if ((base2 = ctf_add_integer (pfp, CTF_ADD_ROOT, "long int", &encoding2)) == CTF_ERR)
+    goto create_parent;
+
+  if ((ptr = ctf_add_pointer (cfp, CTF_ADD_ROOT, base)) == CTF_ERR)
+    goto create_child;
+
+  if ((type = ctf_lookup_by_name (cfp, "int *") ) == CTF_ERR)
+    goto err;
+
+  type_name = ctf_type_aname (cfp, type);
+  printf ("First lookup: %s in the child points to a type of kind %i\n",
+	  type_name, ctf_type_kind (cfp, ctf_type_reference (cfp, type)));
+  free (type_name);
+
+  if (ctf_type_reference (cfp, type) != base)
+    printf ("First lookup ref diff: %lx versus %lx\n", base,
+	    ctf_type_reference (cfp, type));
+  last_type = type;
+
+  /* Add another pointer to the same type in the parent and try a lookup.  */
+
+  if ((ptr = ctf_add_pointer (pfp, CTF_ADD_ROOT, base2)) == CTF_ERR)
+    goto create_parent;
+
+  if ((type = ctf_lookup_by_name (cfp, "long int *") ) == CTF_ERR)
+    goto err;
+
+  type_name = ctf_type_aname (cfp, type);
+  printf ("Second lookup: %s in the child points to a type of kind %i\n",
+	  type_name, ctf_type_kind (cfp, ctf_type_reference (cfp, type)));
+  free (type_name);
+
+  if (ctf_type_reference (cfp, type) != base2)
+    printf ("Second lookup ref diff: %lx versus %lx\n", base2,
+	    ctf_type_reference (cfp, type));
+  if (last_type == type)
+    printf ("Second lookup should not return the same type as the first: %lx\n", type);
+
+  last_type = type;
+
+  /* Add another pointer to the same type in the child and try a lookup.  */
+
+  if ((ptr = ctf_add_pointer (cfp, CTF_ADD_ROOT, base2)) == CTF_ERR)
+    goto create_child;
+
+  if ((type = ctf_lookup_by_name (cfp, "long int *") ) == CTF_ERR)
+    goto err;
+
+  type_name = ctf_type_aname (cfp, type);
+  printf ("Third lookup: %s in the child points to a type of kind %i\n",
+	  type_name, ctf_type_kind (cfp, ctf_type_reference (cfp, type)));
+  free (type_name);
+
+  if (ctf_type_reference (cfp, type) != base2)
+    printf ("Third lookup ref diff: %lx versus %lx\n", base2,
+	    ctf_type_reference (cfp, type));
+
+  if (last_type == type)
+    printf ("Third lookup should not return the same type as the second: %lx\n", type);
+
+  ctf_file_close (cfp);
+  ctf_file_close (pfp);
+
+  return 0;
+
+ create_err:
+  fprintf (stderr, "Creation failed: %s\n", ctf_errmsg (err));
+  return 1;
+ create_parent:
+  fprintf (stderr, "Cannot create type: %s\n", ctf_errmsg (ctf_errno (pfp)));
+  return 1;
+ create_child:
+  fprintf (stderr, "Cannot create type: %s\n", ctf_errmsg (ctf_errno (cfp)));
+  return 1;
+ err:
+  fprintf (stderr, "Lookup failed: %s\n", ctf_errmsg (ctf_errno (cfp)));
+  return 1;
+}
diff --git a/libctf/testsuite/libctf-writable/pptrtab.lk b/libctf/testsuite/libctf-writable/pptrtab.lk
new file mode 100644
index 0000000..56cd8c2
--- /dev/null
+++ b/libctf/testsuite/libctf-writable/pptrtab.lk
@@ -0,0 +1,3 @@
+First lookup: int \* in the child points to a type of kind 1
+Second lookup: long int \* in the child points to a type of kind 1
+Third lookup: long int \* in the child points to a type of kind 1
diff --git a/libctf/testsuite/libctf-writable/writable.exp b/libctf/testsuite/libctf-writable/writable.exp
new file mode 100644
index 0000000..270262f
--- /dev/null
+++ b/libctf/testsuite/libctf-writable/writable.exp
@@ -0,0 +1,38 @@
+# Copyright (C) 2021 Free Software Foundation, Inc.
+#
+# This file is part of the GNU Binutils.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+# MA 02110-1301, USA.
+#
+
+if {[info exists env(LC_ALL)]} {
+    set old_lc_all $env(LC_ALL)
+}
+set env(LC_ALL) "C"
+
+set ctf_test_list [lsort [glob -nocomplain $srcdir/$subdir/*.lk]]
+
+foreach ctf_test $ctf_test_list {
+    verbose [file rootname $ctf_test]
+    verbose running lookup test on $ctf_test
+    run_lookup_test [file rootname $ctf_test]
+}
+
+if {[info exists old_lc_all]} {
+    set env(LC_ALL) $old_lc_all
+} else {
+    unset env(LC_ALL)
+}