Fix htab lookup bug in reregister_specialization (issue5190046)

Fix htab lookup bug in reregister_specialization (issue5190046)

[Diego Novillo]

I found this bug while debugging a failure in pph images with template
classes.  When writing the decl_specializations table, the writer
calls htab_elements() to output the length of the table.  It then
traverses the table with htab_traverse_noresize() to emit all the
entries.

The reader uses that value to know how many entries it needs to read.
However, the table was out of sync wrt empty entries because
reregister_specialization does a lookup using INSERT instead of
NO_INSERT, so it was leaving a bunch of empty entries in it (thanks
Jakub for helping me diagnose this).

Since empty entries are never traversed by htab_traverse, they were
never written out and the reader was trying to read more entries than
there really were.

Jason, I don't think this is affecting any bugs in trunk, but it looks
worth fixing.  OK for trunk?


Diego.


	* pt.c (reregister_specialization): Call htab_find_slot with
	NO_INSERT.

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 04e7767..2366dc9 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -1648,8 +1648,8 @@ reregister_specialization (tree spec, tree tinfo, tree new_spec)
   elt.args = TI_ARGS (tinfo);
   elt.spec = NULL_TREE;
 
-  slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
-  if (*slot)
+  slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, NO_INSERT);
+  if (slot && *slot)
     {
       gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
       gcc_assert (new_spec != NULL_TREE);

--
This patch is available for review at http://codereview.appspot.com/5190046

Re: Fix htab lookup bug in reregister_specialization (issue5190046)

[Jakub Jelinek]

On Wed, Oct 05, 2011 at 03:49:38PM -0400, Diego Novillo wrote:
> Jason, I don't think this is affecting any bugs in trunk, but it looks
> worth fixing.  OK for trunk?

Well, it can cause problems.  Consider 3 entries in the hash table
with the same hash. (1) inserted first, then (2), then (3), then (2)
gets htab_remove_elt (decl_specializations has deletions on it too),
so (2) in the hash table is overwritten with HTAB_DELETED_ENTRY.
Next reregister_specialization is called with the same hash.
It will find the slot (where (2) used to be stored), overwrites
the HTAB_DELETED_ENTRY with HTAB_EMPTY_ENTRY (aka NULL) and return
that slot, but as reregister_specialization doesn't store anything there,
afterwards htab_find won't be able to find (3).

BTW, register_specialization has the same problems.  If slot != NULL and fn
== NULL, it can still return without storing non-NULL into *slot
(when optimize_specialization_lookup_p (tmpl) returns non-zero).
You can do else if (slot != NULL && fn == NULL) htab_clear_slot (decl_specializations, slot);

And, IMHO slot should be void **, otherwise there is aliasing violation.

> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -1648,8 +1648,8 @@ reregister_specialization (tree spec, tree tinfo, tree new_spec)
>    elt.args = TI_ARGS (tinfo);
>    elt.spec = NULL_TREE;
>  
> -  slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
> -  if (*slot)
> +  slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, NO_INSERT);
> +  if (slot && *slot)
>      {
>        gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
>        gcc_assert (new_spec != NULL_TREE);

If you never insert, it should be htab_find only (with spec_entry * instead
of spec_entry ** variable).

	Jakub

Re: Fix htab lookup bug in reregister_specialization (issue5190046)

[Jason Merrill]

On 10/05/2011 04:05 PM, Jakub Jelinek wrote:
> BTW, register_specialization has the same problems.  If slot != NULL and fn
> == NULL, it can still return without storing non-NULL into *slot
> (when optimize_specialization_lookup_p (tmpl) returns non-zero).
> You can do else if (slot != NULL&&  fn == NULL) htab_clear_slot (decl_specializations, slot);

I don't think there's a problem in that function; if fn == NULL, then we 
store spec in its place.

> If you never insert, it should be htab_find only (with spec_entry * instead
> of spec_entry ** variable).

Makes sense.

Jason

Re: Fix htab lookup bug in reregister_specialization (issue5190046)

[Jakub Jelinek]

On Wed, Oct 05, 2011 at 05:03:45PM -0400, Jason Merrill wrote:
> On 10/05/2011 04:05 PM, Jakub Jelinek wrote:
> >BTW, register_specialization has the same problems.  If slot != NULL and fn
> >== NULL, it can still return without storing non-NULL into *slot
> >(when optimize_specialization_lookup_p (tmpl) returns non-zero).
> >You can do else if (slot != NULL&&  fn == NULL) htab_clear_slot (decl_specializations, slot);
> 
> I don't think there's a problem in that function; if fn == NULL,
> then we store spec in its place.

If optimize_specialization_lookup_p (tmpl) doesn't change return value in
between the two calls, then you are right.  But perhaps in that case
you could avoid the second call and use slot != NULL instead.

	Jakub

Re: Fix htab lookup bug in reregister_specialization (issue5190046)

[Jason Merrill]

On 10/05/2011 05:15 PM, Jakub Jelinek wrote:
> If optimize_specialization_lookup_p (tmpl) doesn't change return value in
> between the two calls, then you are right.  But perhaps in that case
> you could avoid the second call and use slot != NULL instead.

That makes sense too.

Jason

[PATCH] Fix htab lookup bug in reregister_specialization (issue5190046, take 2)

[Jakub Jelinek]

On Wed, Oct 05, 2011 at 09:44:34PM -0400, Jason Merrill wrote:
> On 10/05/2011 05:15 PM, Jakub Jelinek wrote:
> >If optimize_specialization_lookup_p (tmpl) doesn't change return value in
> >between the two calls, then you are right.  But perhaps in that case
> >you could avoid the second call and use slot != NULL instead.
> 
> That makes sense too.

Here is a modified patch then, bootstrapped/regtested on x86_64-linux
and i686-linux, ok for trunk?  Would just the reregister_specialization
change be ok for 4.6 too?

2011-10-07  Jakub Jelinek  <jakub@redhat.com>
	    Diego Novillo  <dnovillo@google.com>

	* pt.c (reregister_specialization): Use htab_find instead of
	htab_find_slot with INSERT.
	(maybe_process_partial_specialization, lookup_template_class_1): Change
	slot variable type to void ** to avoid aliasing problems.
	(register_specialization): Likewise.  Use slot != NULL instead of
	more expensive !optimize_specialization_lookup_p (tmpl) test.

--- gcc/cp/pt.c.jj	2011-10-03 14:27:49.000000000 +0200
+++ gcc/cp/pt.c	2011-10-07 09:14:12.000000000 +0200
@@ -892,7 +892,8 @@ maybe_process_partial_specialization (tr
 		     instantiation.  Reassign it to the new member
 		     specialization template.  */
 		  spec_entry elt;
-		  spec_entry **slot;
+		  spec_entry *entry;
+		  void **slot;
 
 		  elt.tmpl = most_general_template (tmpl);
 		  elt.args = CLASSTYPE_TI_ARGS (inst);
@@ -903,10 +904,10 @@ maybe_process_partial_specialization (tr
 		  elt.tmpl = tmpl;
 		  elt.args = INNERMOST_TEMPLATE_ARGS (elt.args);
 
-		  slot = (spec_entry **)
-		    htab_find_slot (type_specializations, &elt, INSERT);
-		  *slot = ggc_alloc_spec_entry ();
-		  **slot = elt;
+		  slot = htab_find_slot (type_specializations, &elt, INSERT);
+		  entry = ggc_alloc_spec_entry ();
+		  *entry = elt;
+		  *slot = entry;
 		}
 	      else if (COMPLETE_OR_OPEN_TYPE_P (inst))
 		/* But if we've had an implicit instantiation, that's a
@@ -1294,7 +1295,7 @@ register_specialization (tree spec, tree
 			 hashval_t hash)
 {
   tree fn;
-  spec_entry **slot = NULL;
+  void **slot = NULL;
   spec_entry elt;
 
   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL && DECL_P (spec));
@@ -1327,10 +1328,10 @@ register_specialization (tree spec, tree
       if (hash == 0)
 	hash = hash_specialization (&elt);
 
-      slot = (spec_entry **)
+      slot =
 	htab_find_slot_with_hash (decl_specializations, &elt, hash, INSERT);
       if (*slot)
-	fn = (*slot)->spec;
+	fn = ((spec_entry *) *slot)->spec;
       else
 	fn = NULL_TREE;
     }
@@ -1423,11 +1424,12 @@ register_specialization (tree spec, tree
       && !check_specialization_namespace (tmpl))
     DECL_CONTEXT (spec) = DECL_CONTEXT (tmpl);
 
-  if (!optimize_specialization_lookup_p (tmpl))
+  if (slot != NULL /* !optimize_specialization_lookup_p (tmpl) */)
     {
+      spec_entry *entry = ggc_alloc_spec_entry ();
       gcc_assert (tmpl && args && spec);
-      *slot = ggc_alloc_spec_entry ();
-      **slot = elt;
+      *entry = elt;
+      *slot = entry;
       if (TREE_CODE (spec) == FUNCTION_DECL && DECL_NAMESPACE_SCOPE_P (spec)
 	  && PRIMARY_TEMPLATE_P (tmpl)
 	  && DECL_SAVED_TREE (DECL_TEMPLATE_RESULT (tmpl)) == NULL_TREE)
@@ -1639,19 +1641,19 @@ iterative_hash_template_arg (tree arg, h
 bool
 reregister_specialization (tree spec, tree tinfo, tree new_spec)
 {
-  spec_entry **slot;
+  spec_entry *entry;
   spec_entry elt;
 
   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
   elt.args = TI_ARGS (tinfo);
   elt.spec = NULL_TREE;
 
-  slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
-  if (*slot)
+  entry = (spec_entry *) htab_find (decl_specializations, &elt);
+  if (entry != NULL)
     {
-      gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
+      gcc_assert (entry->spec == spec || entry->spec == new_spec);
       gcc_assert (new_spec != NULL_TREE);
-      (*slot)->spec = new_spec;
+      entry->spec = new_spec;
       return 1;
     }
 
@@ -7042,7 +7044,7 @@ lookup_template_class_1 (tree d1, tree a
 {
   tree templ = NULL_TREE, parmlist;
   tree t;
-  spec_entry **slot;
+  void **slot;
   spec_entry *entry;
   spec_entry elt;
   hashval_t hash;
@@ -7480,10 +7482,11 @@ lookup_template_class_1 (tree d1, tree a
       SET_TYPE_TEMPLATE_INFO (t, build_template_info (found, arglist));
 
       elt.spec = t;
-      slot = (spec_entry **) htab_find_slot_with_hash (type_specializations,
-						       &elt, hash, INSERT);
-      *slot = ggc_alloc_spec_entry ();
-      **slot = elt;
+      slot = htab_find_slot_with_hash (type_specializations,
+				       &elt, hash, INSERT);
+      entry = ggc_alloc_spec_entry ();
+      *entry = elt;
+      *slot = entry;
 
       /* Note this use of the partial instantiation so we can check it
 	 later in maybe_process_partial_specialization.  */


	Jakub

Re: [PATCH] Fix htab lookup bug in reregister_specialization (issue5190046, take 2)

[Jason Merrill]

On 10/07/2011 12:14 PM, Jakub Jelinek wrote:
> Here is a modified patch then, bootstrapped/regtested on x86_64-linux
> and i686-linux, ok for trunk?  Would just the reregister_specialization
> change be ok for 4.6 too?

Yes and yes.

Jason