[00/13] check hash table counts

[00/13] check hash table counts

[Alexandre Oliva]

While looking into another issue that corrupted hash tables, I added
code to check consistency of element counts, and hit numerous issues
that were concerning, of three kinds: insertion of entries that seem
empty, dangling insertions, and lookups during insertions.

These problems may all have the effect of replacing a deleted entry
with one that seems empty, which may disconnect double-hashing chains
involving that entry, and thus cause entries to go missing.

This patch, opening the patch series, only adds code to detect these
problems to the hash table verifier method.  I'm not sure it makes
sense to put it in, but I post it for the record.  Fixes and cheaper
detectors for some of these errors are going to be posted separately.

The number of bugs it revealed tells me that leaving callers in charge
of completing insertions is too error prone.  I found this
verification code a bit too expensive to enable in general.  We could
add check entry count cheaply at expand time and catch some of these
at very low cost, which would likely catch at least some of the
errors, but perhaps a safer interface could avoid them entirely.
WDYT?


I'm going to post a collection of 13 patches a as a followup to this
one, fixing various problems it has detected, or adding code to catch
some of these problems sooner.


for  gcc/ChangeLog

	* hash-table.h (verify): Check elements and deleted counts.
---
 gcc/hash-table.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 53507daae26c3..7dbeea05373a2 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -1035,6 +1035,23 @@ hash_table<Descriptor, Lazy, Allocator>
 	  && Descriptor::equal (*entry, comparable))
 	hashtab_chk_error ();
     }
+
+  if (m_size < 2048)
+    {
+      size_t elmts = m_n_elements, dels = m_n_deleted;
+      for (size_t i = 0; i < m_size; i++)
+	{
+	  value_type *entry = &m_entries[i];
+	  if (!is_empty (*entry))
+	    {
+	      elmts--;
+	      if (is_deleted (*entry))
+		dels--;
+	    }
+	}
+      if (elmts || dels)
+	hashtab_chk_error ();
+    }
 }
 
 /* This function deletes an element with the given COMPARABLE value


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[01/13] scoped tables: insert before further lookups

[Alexandre Oliva]

Avoid hash table lookups between requesting an insert and storing the
inserted value in avail_exprs_stack.  Lookups before the insert is
completed could fail to find double-hashed elements.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* tree-ssa-scopedtables.cc
	(avail_exprs_stack::lookup_avail_expr): Finish hash table
	insertion before further lookups.
---
 gcc/tree-ssa-scopedtables.cc |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/gcc/tree-ssa-scopedtables.cc b/gcc/tree-ssa-scopedtables.cc
index 6d203ef89ecef..3e6e129e7d5d3 100644
--- a/gcc/tree-ssa-scopedtables.cc
+++ b/gcc/tree-ssa-scopedtables.cc
@@ -259,11 +259,6 @@ avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
     }
   else if (*slot == NULL)
     {
-      /* If we did not find the expression in the hash table, we may still
-	 be able to produce a result for some expressions.  */
-      tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
-								  element);
-
       /* We have, in effect, allocated *SLOT for ELEMENT at this point.
 	 We must initialize *SLOT to a real entry, even if we found a
 	 way to prove ELEMENT was a constant after not finding ELEMENT
@@ -277,6 +272,11 @@ avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
       class expr_hash_elt *element2 = new expr_hash_elt (element);
       *slot = element2;
 
+      /* If we did not find the expression in the hash table, we may still
+	 be able to produce a result for some expressions.  */
+      tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
+								  element);
+
       record_expr (element2, NULL, '2');
       return retval;
     }

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[02/13] varpool: do not add NULL vnodes to referenced

[Alexandre Oliva]

Avoid adding NULL vnodes to referenced tables.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* varpool.c (symbol_table::remove_unreferenced_decls): Do not
	add NULL vnodes to referenced table.
---
 gcc/varpool.cc |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/gcc/varpool.cc b/gcc/varpool.cc
index bfd17f1250cc0..ccbd6e50f4b01 100644
--- a/gcc/varpool.cc
+++ b/gcc/varpool.cc
@@ -680,10 +680,12 @@ symbol_table::remove_unreferenced_decls (void)
 	    enqueue_node (vnode, &first);
 	  else
 	    {
-	      referenced.add (vnode);
+	      if (vnode)
+		referenced.add (vnode);
 	      while (vnode && vnode->alias && vnode->definition)
 		{
 		  vnode = vnode->get_alias_target ();
+		  gcc_checking_assert (vnode);
 	          referenced.add (vnode);
 		}
 	    }

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[03/13] tree-inline decl_map: skip mapping NULL to itself

[Alexandre Oliva]

Mapping a NULL key is no use, skip it.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* tree-inline.cc (insert_decl_map): Skip mapping a NULL decl
	as value to itself.
---
 gcc/tree-inline.cc |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/tree-inline.cc b/gcc/tree-inline.cc
index c6c86af6c4ea9..bfea1cc11822e 100644
--- a/gcc/tree-inline.cc
+++ b/gcc/tree-inline.cc
@@ -148,7 +148,7 @@ insert_decl_map (copy_body_data *id, tree key, tree value)
 
   /* Always insert an identity map as well.  If we see this same new
      node again, we won't want to duplicate it a second time.  */
-  if (key != value)
+  if (key != value && value)
     id->decl_map->put (value, value);
 }
 

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[04/13] [C++] constraint: insert norm entry once

[Alexandre Oliva]

Use NO_INSERT to test whether inserting should be attempted.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/cp/ChangeLog

	* constraint.cc (normalize_concept_check): Use NO_INSERT for
	pre-insertion check.
---
 gcc/cp/constraint.cc |    8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index 37eae03afdb73..f28f96ada463e 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -777,14 +777,16 @@ normalize_concept_check (tree check, tree args, norm_info info)
   norm_entry entry = {tmpl, targs, NULL_TREE};
   norm_entry **slot = nullptr;
   hashval_t hash = 0;
+  bool insert = false;
   if (!info.generate_diagnostics ())
     {
       /* Cache the normal form of the substituted concept-id (when not
 	 diagnosing).  */
       hash = norm_hasher::hash (&entry);
-      slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT);
-      if (*slot)
+      slot = norm_cache->find_slot_with_hash (&entry, hash, NO_INSERT);
+      if (slot)
 	return (*slot)->norm;
+      insert = true;
     }
 
   /* The concept may have been ill-formed.  */
@@ -794,7 +796,7 @@ normalize_concept_check (tree check, tree args, norm_info info)
 
   info.update_context (check, args);
   tree norm = normalize_expression (def, targs, info);
-  if (slot)
+  if (insert)
     {
       /* Recompute SLOT since norm_cache may have been expanded during
 	 the recursive call.  */

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[05/13] ssa-loop-niter: skip caching of null operands

[Alexandre Oliva]

When a TREE_OPERAND is NULL, do not cache it.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* tree-ssa-loop-niter.cc (expand_simple_operands): Refrain
	from caching NULL TREE_OPERANDs.
---
 gcc/tree-ssa-loop-niter.cc |    2 ++
 1 file changed, 2 insertions(+)

diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index fece876099c16..17645648326e8 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -2325,6 +2325,8 @@ expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache)
       for (i = 0; i < n; i++)
 	{
 	  e = TREE_OPERAND (expr, i);
+	  if (!e)
+	    continue;
 	  /* SCEV analysis feeds us with a proper expression
 	     graph matching the SSA graph.  Avoid turning it
 	     into a tree here, thus handle tree sharing

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[06/13] tree-inline decl_map: skip mapping result's NULL default def

[Alexandre Oliva]

If a result doesn't have a default def, don't attempt to remap it.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* tree-inline.cc (declare_return_variable): Don't remap NULL
	default def of result.
---
 gcc/tree-inline.cc |    9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-inline.cc b/gcc/tree-inline.cc
index bfea1cc11822e..4556256dc32b1 100644
--- a/gcc/tree-inline.cc
+++ b/gcc/tree-inline.cc
@@ -3851,10 +3851,11 @@ declare_return_variable (copy_body_data *id, tree return_slot, tree modify_dest,
 	 it's default_def SSA_NAME.  */
       if (gimple_in_ssa_p (id->src_cfun)
 	  && is_gimple_reg (result))
-	{
-	  temp = make_ssa_name (temp);
-	  insert_decl_map (id, ssa_default_def (id->src_cfun, result), temp);
-	}
+	if (tree default_def = ssa_default_def (id->src_cfun, result))
+	  {
+	    temp = make_ssa_name (temp);
+	    insert_decl_map (id, default_def, temp);
+	  }
       insert_init_stmt (id, entry_bb, gimple_build_assign (temp, var));
     }
   else

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[07/13] postreload-gcse: no insert on mere lookup

[Alexandre Oliva]

lookup_expr_in_table is not used for insertions, but it mistakenly
used INSERT rather than NO_INSERT.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* postreload-gcse.cc (lookup_expr_in_table): Use NO_INSERT.
---
 gcc/postreload-gcse.cc |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/postreload-gcse.cc b/gcc/postreload-gcse.cc
index 1c795b43ca36b..2818f54dedd29 100644
--- a/gcc/postreload-gcse.cc
+++ b/gcc/postreload-gcse.cc
@@ -447,7 +447,7 @@ lookup_expr_in_table (rtx pat)
   tmp_expr->hash = hash;
   tmp_expr->avail_occr = NULL;
 
-  slot = expr_table->find_slot_with_hash (tmp_expr, hash, INSERT);
+  slot = expr_table->find_slot_with_hash (tmp_expr, hash, NO_INSERT);
   obstack_free (&expr_obstack, tmp_expr);
 
   if (!slot)

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[08/13] tm: complete tm_restart insertion

[Alexandre Oliva]

Insertion of a tm_restart_node in tm_restart failed to record the
newly-allocated node in the hash table.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* trans-mem.cc (split_bb_make_tm_edge): Record new node in
	tm_restart.
---
 gcc/trans-mem.cc |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/trans-mem.cc b/gcc/trans-mem.cc
index 131dce05476ac..cbd1b891266fd 100644
--- a/gcc/trans-mem.cc
+++ b/gcc/trans-mem.cc
@@ -3215,7 +3215,7 @@ split_bb_make_tm_edge (gimple *stmt, basic_block dest_bb,
   struct tm_restart_node *n = *slot;
   if (n == NULL)
     {
-      n = ggc_alloc<tm_restart_node> ();
+      *slot = n = ggc_alloc<tm_restart_node> ();
       *n = dummy;
     }
   else

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[09/13] [C++] constexpr: request insert iff depth is ok

[Alexandre Oliva]

cxx_eval_call_expression requests an INSERT even in cases when it
would later decide not to insert.  This could break double-hashing
chains.  Arrange for it to use NO_INSERT when the insertion would not
be completed.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/cp/ChangeLog

	* constexpr.cc (cxx_eval_call_expression): Do not request an
	INSERT that would not be completed.
---
 gcc/cp/constexpr.cc |    8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/gcc/cp/constexpr.cc b/gcc/cp/constexpr.cc
index d99c49bdbe282..6d20ffa2cdeb6 100644
--- a/gcc/cp/constexpr.cc
+++ b/gcc/cp/constexpr.cc
@@ -3000,13 +3000,15 @@ cxx_eval_call_expression (const constexpr_ctx *ctx, tree t,
 
       /* If we have seen this call before, we are done.  */
       maybe_initialize_constexpr_call_table ();
+      bool insert = depth_ok < constexpr_cache_depth;
       constexpr_call **slot
-	= constexpr_call_table->find_slot (&new_call, INSERT);
-      entry = *slot;
+	= constexpr_call_table->find_slot (&new_call,
+					   insert ? INSERT : NO_INSERT);
+      entry = slot ? *slot : NULL;
       if (entry == NULL)
 	{
 	  /* Only cache up to constexpr_cache_depth to limit memory use.  */
-	  if (depth_ok < constexpr_cache_depth)
+	  if (insert)
 	    {
 	      /* We need to keep a pointer to the entry, not just the slot, as
 		 the slot can move during evaluation of the body.  */

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[10/13] lto: drop dummy partition mapping

[Alexandre Oliva]

When adding a catch-all partition, we map NULL to it.  That mapping is
ineffective and unnecessary.  Drop it.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/lto/ChangeLog

	* lto-partition.cc (lto_1_to_1_map): Drop NULL partition
	mapping.
---
 gcc/lto/lto-partition.cc |    1 -
 1 file changed, 1 deletion(-)

diff --git a/gcc/lto/lto-partition.cc b/gcc/lto/lto-partition.cc
index ebb9c3abe128c..654d67f272e92 100644
--- a/gcc/lto/lto-partition.cc
+++ b/gcc/lto/lto-partition.cc
@@ -333,7 +333,6 @@ lto_1_to_1_map (void)
       else
 	{
 	  partition = new_partition ("");
-	  pmap.put (NULL, partition);
 	  npartitions++;
 	}
 

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[11/13] ada: don't map NULL decl to locus

[Alexandre Oliva]

When decl is NULL, don't record its mapping in the
decl_to_instance_map.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ada/ChangeLog

	* gcc-interface/trans.cc (Sloc_to_locus): Don't map NULL decl.
---
 gcc/ada/gcc-interface/trans.cc |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/ada/gcc-interface/trans.cc b/gcc/ada/gcc-interface/trans.cc
index 59332f93614a9..6579ad11cc284 100644
--- a/gcc/ada/gcc-interface/trans.cc
+++ b/gcc/ada/gcc-interface/trans.cc
@@ -10564,7 +10564,7 @@ Sloc_to_locus (Source_Ptr Sloc, location_t *locus, bool clear_column,
   *locus
     = linemap_position_for_line_and_column (line_table, map, line, column);
 
-  if (file_map && file_map[file - 1].Instance)
+  if (decl && file_map && file_map[file - 1].Instance)
     decl_to_instance_map->put (decl, file_map[file - 1].Instance);
 
   return true;

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[12/13] hash set: reject attempts to add empty values

[Alexandre Oliva]

Check, after adding a key to a hash set, that the entry does not look
empty.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* hash-set.h (add): Check that the inserted entry does not
	look empty.
---
 gcc/hash-set.h |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/gcc/hash-set.h b/gcc/hash-set.h
index 76fa7f394561e..a98121a060eed 100644
--- a/gcc/hash-set.h
+++ b/gcc/hash-set.h
@@ -58,7 +58,11 @@ public:
       Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
       bool existed = !Traits::is_empty (*e);
       if (!existed)
-	new (e) Key (k);
+	{
+	  new (e) Key (k);
+	  // Catch attempts to insert e.g. a NULL pointer.
+	  gcc_checking_assert (!Traits::is_empty (*e));
+	}
 
       return existed;
     }

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[13/13] hash-map: reject empty-looking insertions

[Alexandre Oliva]

Check, after inserting entries, that they don't look empty.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* hash-map.h (put, get_or_insert): Check that entry does not
	look empty after insertion.
---
 gcc/hash-map.h |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/gcc/hash-map.h b/gcc/hash-map.h
index 457967f4bf1ae..63fa21cf37c5b 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -169,11 +169,12 @@ public:
     {
       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 						   INSERT);
-      bool ins = hash_entry::is_empty (*e);
+      bool ins = Traits::is_empty (*e);
       if (ins)
 	{
 	  e->m_key = k;
 	  new ((void *) &e->m_value) Value (v);
+	  gcc_checking_assert (!Traits::is_empty (*e));
 	}
       else
 	e->m_value = v;
@@ -203,6 +204,7 @@ public:
 	{
 	  e->m_key = k;
 	  new ((void *)&e->m_value) Value ();
+	  gcc_checking_assert (!Traits::is_empty (*e));
 	}
 
       if (existed != NULL)

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [01/13] scoped tables: insert before further lookups

[Jeff Law]

On 12/26/22 21:17, Alexandre Oliva via Gcc-patches wrote:
> 
> Avoid hash table lookups between requesting an insert and storing the
> inserted value in avail_exprs_stack.  Lookups before the insert is
> completed could fail to find double-hashed elements.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* tree-ssa-scopedtables.cc
> 	(avail_exprs_stack::lookup_avail_expr): Finish hash table
> 	insertion before further lookups.
Thanks.  OK.
Jeff

Re: [07/13] postreload-gcse: no insert on mere lookup

[Jeff Law]

On 12/26/22 21:24, Alexandre Oliva via Gcc-patches wrote:
> 
> lookup_expr_in_table is not used for insertions, but it mistakenly
> used INSERT rather than NO_INSERT.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* postreload-gcse.cc (lookup_expr_in_table): Use NO_INSERT.
OK
jeff

Re: [02/13] varpool: do not add NULL vnodes to referenced

[Jeff Law]

On 12/26/22 21:18, Alexandre Oliva via Gcc-patches wrote:
> 
> Avoid adding NULL vnodes to referenced tables.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* varpool.c (symbol_table::remove_unreferenced_decls): Do not
> 	add NULL vnodes to referenced table.
OK
jeff

Re: [03/13] tree-inline decl_map: skip mapping NULL to itself

[Jeff Law]

On 12/26/22 21:19, Alexandre Oliva via Gcc-patches wrote:
> 
> Mapping a NULL key is no use, skip it.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* tree-inline.cc (insert_decl_map): Skip mapping a NULL decl
> 	as value to itself.
OK
jeff

Re: [05/13] ssa-loop-niter: skip caching of null operands

[Jeff Law]

On 12/26/22 21:22, Alexandre Oliva via Gcc-patches wrote:
> 
> When a TREE_OPERAND is NULL, do not cache it.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* tree-ssa-loop-niter.cc (expand_simple_operands): Refrain
> 	from caching NULL TREE_OPERANDs.
I must admit some curiosity about the NULL operand though.  Do you 
recall what kind of node had a NULL operand and whether or not that was 
a valid state or not?

I just want to make sure this isn't just papering over a deeper issue.

jeff

Re: [06/13] tree-inline decl_map: skip mapping result's NULL default def

[Jeff Law]

On 12/26/22 21:23, Alexandre Oliva via Gcc-patches wrote:
> 
> If a result doesn't have a default def, don't attempt to remap it.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* tree-inline.cc (declare_return_variable): Don't remap NULL
> 	default def of result.
OK
jeff

Re: [08/13] tm: complete tm_restart insertion

[Jeff Law]

On 12/26/22 21:28, Alexandre Oliva via Gcc-patches wrote:
> 
> Insertion of a tm_restart_node in tm_restart failed to record the
> newly-allocated node in the hash table.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* trans-mem.cc (split_bb_make_tm_edge): Record new node in
> 	tm_restart.
OK
jeff

Re: [12/13] hash set: reject attempts to add empty values

[Jeff Law]

On 12/26/22 21:38, Alexandre Oliva via Gcc-patches wrote:
> 
> Check, after adding a key to a hash set, that the entry does not look
> empty.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* hash-set.h (add): Check that the inserted entry does not
> 	look empty.
OK once prereqs are installed.
jeff

Re: [13/13] hash-map: reject empty-looking insertions

[Jeff Law]

On 12/26/22 21:39, Alexandre Oliva via Gcc-patches wrote:
> 
> Check, after inserting entries, that they don't look empty.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* hash-map.h (put, get_or_insert): Check that entry does not
> 	look empty after insertion.
OK once prereqs are installed.
jeff

Re: [11/13] ada: don't map NULL decl to locus

[Jeff Law]

On 12/26/22 21:38, Alexandre Oliva via Gcc-patches wrote:
> 
> When decl is NULL, don't record its mapping in the
> decl_to_instance_map.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ada/ChangeLog
> 
> 	* gcc-interface/trans.cc (Sloc_to_locus): Don't map NULL decl.
OK assuming that a NULL "decl" is valid -- you're in a much better 
position than me to assess validity of a NULL "decl" here.

jeff

Re: [10/13] lto: drop dummy partition mapping

[Jeff Law]

On 12/26/22 21:35, Alexandre Oliva via Gcc-patches wrote:
> 
> When adding a catch-all partition, we map NULL to it.  That mapping is
> ineffective and unnecessary.  Drop it.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/lto/ChangeLog
> 
> 	* lto-partition.cc (lto_1_to_1_map): Drop NULL partition
> 	mapping.
OK
jeff

Re: [04/13] [C++] constraint: insert norm entry once

[Jeff Law]

On 12/26/22 21:21, Alexandre Oliva via Gcc-patches wrote:
> 
> Use NO_INSERT to test whether inserting should be attempted.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/cp/ChangeLog
> 
> 	* constraint.cc (normalize_concept_check): Use NO_INSERT for
> 	pre-insertion check.
OK
jeff

Re: [09/13] [C++] constexpr: request insert iff depth is ok

[Jeff Law]

On 12/26/22 21:30, Alexandre Oliva via Gcc-patches wrote:
> 
> cxx_eval_call_expression requests an INSERT even in cases when it
> would later decide not to insert.  This could break double-hashing
> chains.  Arrange for it to use NO_INSERT when the insertion would not
> be completed.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/cp/ChangeLog
> 
> 	* constexpr.cc (cxx_eval_call_expression): Do not request an
> 	INSERT that would not be completed.
OK.
Jeff

Re: [11/13] ada: don't map NULL decl to locus

[Arnaud Charlet]

>> When decl is NULL, don't record its mapping in the
>> decl_to_instance_map.
>> Regstrapped on x86_64-linux-gnu.  Ok to install?
>> for  gcc/ada/ChangeLog
>>    * gcc-interface/trans.cc (Sloc_to_locus): Don't map NULL decl.
> OK assuming that a NULL "decl" is valid -- you're in a much better position than me to assess validity of a NULL "decl" here.

I confirm that this is OK and expected.

Arno

Re: [13/13] hash-map: reject empty-looking insertions

[David Malcolm]

On Tue, 2022-12-27 at 01:39 -0300, Alexandre Oliva via Gcc-patches
wrote:
> 
> Check, after inserting entries, that they don't look empty.

Thanks for working on this - I often get this stuff wrong.

Would it make sense to also add assertions that such entries aren't
Traits::is_deleted?  (both for hash_map and hash_set)

Dave

> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
>         * hash-map.h (put, get_or_insert): Check that entry does not
>         look empty after insertion.
> ---
>  gcc/hash-map.h |    4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
> 
> diff --git a/gcc/hash-map.h b/gcc/hash-map.h
> index 457967f4bf1ae..63fa21cf37c5b 100644
> --- a/gcc/hash-map.h
> +++ b/gcc/hash-map.h
> @@ -169,11 +169,12 @@ public:
>      {
>        hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash
> (k),
>                                                    INSERT);
> -      bool ins = hash_entry::is_empty (*e);
> +      bool ins = Traits::is_empty (*e);
>        if (ins)
>         {
>           e->m_key = k;
>           new ((void *) &e->m_value) Value (v);
> +         gcc_checking_assert (!Traits::is_empty (*e));
>         }
>        else
>         e->m_value = v;
> @@ -203,6 +204,7 @@ public:
>         {
>           e->m_key = k;
>           new ((void *)&e->m_value) Value ();
> +         gcc_checking_assert (!Traits::is_empty (*e));
>         }
>  
>        if (existed != NULL)
> 

Re: [05/13] ssa-loop-niter: skip caching of null operands

[Alexandre Oliva]

Hello, Jeff,

On Dec 27, 2022, Jeff Law <jeffreyalaw@gmail.com> wrote:

>> * tree-ssa-loop-niter.cc (expand_simple_operands): Refrain
>> from caching NULL TREE_OPERANDs.

> I must admit some curiosity about the NULL operand though.  Do you
> recall what kind of node had a NULL operand and whether or not that
> was a valid state or not?

I'm pretty sure the case I hit was a CALL_EXPR.


Thanks for the reviews!

Happy GNU Year!

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [00/13] check hash table counts

[Martin Liška]

On 12/27/22 05:07, Alexandre Oliva via Gcc-patches wrote:
> 
> While looking into another issue that corrupted hash tables, I added
> code to check consistency of element counts, and hit numerous issues
> that were concerning, of three kinds: insertion of entries that seem
> empty, dangling insertions, and lookups during insertions.
> 
> These problems may all have the effect of replacing a deleted entry
> with one that seems empty, which may disconnect double-hashing chains
> involving that entry, and thus cause entries to go missing.
> 
> This patch, opening the patch series, only adds code to detect these
> problems to the hash table verifier method.  I'm not sure it makes
> sense to put it in, but I post it for the record.  Fixes and cheaper
> detectors for some of these errors are going to be posted separately.
> 
> The number of bugs it revealed tells me that leaving callers in charge
> of completing insertions is too error prone.  I found this
> verification code a bit too expensive to enable in general.

Hello.

I really like the verification code you added. It's quite similar to what
I added to hash-table.h:

void
hash_table<Descriptor, Lazy, Allocator>
::verify (const compare_type &comparable, hashval_t hash)

where the check is also expensive, but I guard it with a param value:

hash-table-verification-limit
The number of elements for which hash table verification is done for each searched element.

You can utilize the parameter or come up with your own.

Cheers,
Martin

>  We could
> add check entry count cheaply at expand time and catch some of these
> at very low cost, which would likely catch at least some of the
> errors, but perhaps a safer interface could avoid them entirely.
> WDYT?
> 
> 
> I'm going to post a collection of 13 patches a as a followup to this
> one, fixing various problems it has detected, or adding code to catch
> some of these problems sooner.
> 
> 
> for  gcc/ChangeLog
> 
> 	* hash-table.h (verify): Check elements and deleted counts.
> ---
>  gcc/hash-table.h |   17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
> 
> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index 53507daae26c3..7dbeea05373a2 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -1035,6 +1035,23 @@ hash_table<Descriptor, Lazy, Allocator>
>  	  && Descriptor::equal (*entry, comparable))
>  	hashtab_chk_error ();
>      }
> +
> +  if (m_size < 2048)
> +    {
> +      size_t elmts = m_n_elements, dels = m_n_deleted;
> +      for (size_t i = 0; i < m_size; i++)
> +	{
> +	  value_type *entry = &m_entries[i];
> +	  if (!is_empty (*entry))
> +	    {
> +	      elmts--;
> +	      if (is_deleted (*entry))
> +		dels--;
> +	    }
> +	}
> +      if (elmts || dels)
> +	hashtab_chk_error ();
> +    }
>  }
>  
>  /* This function deletes an element with the given COMPARABLE value
> 
> 

[14/17] parloops: don't request insert that won't be completed

[Alexandre Oliva]

In take_address_of, we may refrain from completing a decl_address
INSERT if gsi is NULL, so dnn't even ask for an INSERT in this case.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* tree-parloops.cc (take_address_of): Skip INSERT if !gsi.
---
 gcc/tree-parloops.cc |    7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/gcc/tree-parloops.cc b/gcc/tree-parloops.cc
index e680d97dd0497..b829ba7b873b6 100644
--- a/gcc/tree-parloops.cc
+++ b/gcc/tree-parloops.cc
@@ -1221,8 +1221,11 @@ take_address_of (tree obj, tree type, edge entry,
   uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
   int_tree_map elt;
   elt.uid = uid;
-  int_tree_map *slot = decl_address->find_slot (elt, INSERT);
-  if (!slot->to)
+  int_tree_map *slot = decl_address->find_slot (elt,
+						gsi == NULL
+						? NO_INSERT
+						: INSERT);
+  if (!slot || !slot->to)
     {
       if (gsi == NULL)
 	return NULL;


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[15/17] prevent hash set/map insertion of deleted entries

[Alexandre Oliva]

On Dec 27, 2022, David Malcolm <dmalcolm@redhat.com> wrote:

> Would it make sense to also add assertions that such entries aren't
> Traits::is_deleted?  (both for hash_map and hash_set)

Yeah, I guess so.  I've come up with something for hash-table proper
too, coming up in 17/17.


Just like the recently-added checks for empty entries, add checks for
deleted entries as well.  This didn't catch any problems, but it might
prevent future accidents.  Suggested by David Malcolm.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* hash-map.h (put, get_or_insert): Check that added entry
	doesn't look deleted either.
	& hash-set.h (add): Likewise.
---
 gcc/hash-map.h |    8 +++++---
 gcc/hash-set.h |    3 ++-
 2 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map.h b/gcc/hash-map.h
index 63fa21cf37c5b..e6ca9cf5e6429 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -173,8 +173,9 @@ public:
       if (ins)
 	{
 	  e->m_key = k;
-	  new ((void *) &e->m_value) Value (v);
-	  gcc_checking_assert (!Traits::is_empty (*e));
+	  new ((void *)&e->m_value) Value (v);
+	  gcc_checking_assert (!Traits::is_empty (*e)
+			       && !Traits::is_deleted (*e));
 	}
       else
 	e->m_value = v;
@@ -204,7 +205,8 @@ public:
 	{
 	  e->m_key = k;
 	  new ((void *)&e->m_value) Value ();
-	  gcc_checking_assert (!Traits::is_empty (*e));
+	  gcc_checking_assert (!Traits::is_empty (*e)
+			       && !Traits::is_deleted (*e));
 	}
 
       if (existed != NULL)
diff --git a/gcc/hash-set.h b/gcc/hash-set.h
index a98121a060eed..08e1851d5118d 100644
--- a/gcc/hash-set.h
+++ b/gcc/hash-set.h
@@ -61,7 +61,8 @@ public:
 	{
 	  new (e) Key (k);
 	  // Catch attempts to insert e.g. a NULL pointer.
-	  gcc_checking_assert (!Traits::is_empty (*e));
+	  gcc_checking_assert (!Traits::is_empty (*e)
+			       && !Traits::is_deleted (*e));
 	}
 
       return existed;


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[16/17] check hash table counts at expand

[Alexandre Oliva]

On Dec 28, 2022, Martin Liška <mliska@suse.cz> wrote:

> I really like the verification code you added. It's quite similar to what
> I added to hash-table.h:

*nod*

Prompted by your encouragement, I've combined the element count
verification code with the verify() loop, and also added it to expand,
where it can be done cheaply.


Add cheap verification of element and deleted entry counts during
expand and hash verify.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* hash-table.h (expand): Check elements and deleted counts.
	(verify): Likewise.
---
 gcc/hash-table.h |   35 ++++++++++++++++++++++++++++-------
 1 file changed, 28 insertions(+), 7 deletions(-)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 53507daae26c3..f4bda6102323e 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -805,19 +805,28 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
     hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
 						    * osize);
 
+  size_t n_deleted = m_n_deleted;
+
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
+  size_t n_elements = m_n_elements;
+
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
-      if (!is_empty (x) && !is_deleted (x))
+      if (is_empty (x))
+	;
+      else if (is_deleted (x))
+	n_deleted--;
+      else
         {
+	  n_elements--;
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
 	  /* After the resources of 'x' have been moved to a new object at 'q',
@@ -829,6 +838,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
     }
   while (p < olimit);
 
+  gcc_checking_assert (!n_elements && !n_deleted);
+
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
@@ -1018,8 +1029,9 @@ hash_table<Descriptor, Lazy, Allocator>
   return &m_entries[index];
 }
 
-/* Verify that all existing elements in th hash table which are
-   equal to COMPARABLE have an equal HASH value provided as argument.  */
+/* Verify that all existing elements in the hash table which are
+   equal to COMPARABLE have an equal HASH value provided as argument.
+   Also check that the hash table element counts are correct.  */
 
 template<typename Descriptor, bool Lazy,
 	 template<typename Type> class Allocator>
@@ -1027,14 +1039,23 @@ void
 hash_table<Descriptor, Lazy, Allocator>
 ::verify (const compare_type &comparable, hashval_t hash)
 {
+  size_t n_elements = m_n_elements;
+  size_t n_deleted = m_n_deleted;
   for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
     {
       value_type *entry = &m_entries[i];
-      if (!is_empty (*entry) && !is_deleted (*entry)
-	  && hash != Descriptor::hash (*entry)
-	  && Descriptor::equal (*entry, comparable))
-	hashtab_chk_error ();
+      if (!is_empty (*entry))
+	{
+	  n_elements--;
+	  if (is_deleted (*entry))
+	    n_deleted--;
+	  else if (hash != Descriptor::hash (*entry)
+		   && Descriptor::equal (*entry, comparable))
+	    hashtab_chk_error ();
+	}
     }
+  if (hash_table_sanitize_eq_limit >= m_size)
+    gcc_checking_assert (!n_elements && !n_deleted);
 }
 
 /* This function deletes an element with the given COMPARABLE value


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

[17/17] check hash table insertions

[Alexandre Oliva]

On Dec 27, 2022, Alexandre Oliva <oliva@adacore.com> wrote:

> The number of bugs it revealed tells me that leaving callers in charge
> of completing insertions is too error prone.  I found this
> verification code a bit too expensive to enable in general.

Here's a relatively cheap, checking-only test to catch dangling inserts.


I've noticed a number of potential problems in hash tables, of three
kinds: insertion of entries that seem empty, dangling insertions, and
lookups during insertions.

These problems may all have the effect of replacing a deleted entry
with one that seems empty, which may disconnect double-hashing chains
involving that entry, and thus cause entries to go missing.

This patch detects such problems by recording a pending insertion and
checking that it's completed before other potentially-conflicting
operations.  The additional field is only introduced when checking is
enabled.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChnageLog

	* hash-table.h (check_complete_insertion, check_insert_slot):
	New hash_table methods.
	(m_inserting_slot): New hash_table field.
	(begin, hash_table ctors, ~hash_table): Check previous insert.
	(expand, empty_slow, clear_slot, find_with_hash): Likewise.
	(remote_elt_with_hash, traverse_noresize): Likewise.
	(gt_pch_nx): Likewise.
	(find_slot_with_hash): Likewise.  Record requested insert.
---
 gcc/hash-table.h |   63 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 60 insertions(+), 3 deletions(-)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index f4bda6102323e..33753d04b7bdb 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -495,6 +495,7 @@ public:
     {
       if (Lazy && m_entries == NULL)
 	return iterator ();
+      check_complete_insertion ();
       iterator iter (m_entries, m_entries + m_size);
       iter.slide ();
       return iter;
@@ -551,8 +552,39 @@ private:
     Descriptor::mark_empty (v);
   }
 
+public:
+  void check_complete_insertion () const
+  {
+#if CHECKING_P
+    if (!m_inserting_slot)
+      return;
+
+    gcc_checking_assert (m_inserting_slot >= &m_entries[0]
+			 && m_inserting_slot < &m_entries[m_size]);
+
+    if (!is_empty (*m_inserting_slot))
+      m_inserting_slot = NULL;
+    else
+      gcc_unreachable ();
+#endif
+  }
+
+private:
+  value_type *check_insert_slot (value_type *ret)
+  {
+#if CHECKING_P
+    gcc_checking_assert (is_empty (*ret));
+    m_inserting_slot = ret;
+#endif
+    return ret;
+  }
+
+#if CHECKING_P
+  mutable value_type *m_inserting_slot;
+#endif
+
   /* Table itself.  */
-  typename Descriptor::value_type *m_entries;
+  value_type *m_entries;
 
   size_t m_size;
 
@@ -607,6 +639,9 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
 						     ATTRIBUTE_UNUSED,
 						     mem_alloc_origin origin
 						     MEM_STAT_DECL) :
+#if CHECKING_P
+  m_inserting_slot (0),
+#endif
   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
   m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
 #if GATHER_STATISTICS
@@ -639,6 +674,9 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
 						     ATTRIBUTE_UNUSED,
 						     mem_alloc_origin origin
 						     MEM_STAT_DECL) :
+#if CHECKING_P
+  m_inserting_slot (0),
+#endif
   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
   m_searches (0), m_collisions (0), m_ggc (ggc),
   m_sanitize_eq_and_hash (sanitize_eq_and_hash)
@@ -646,6 +684,8 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
   , m_gather_mem_stats (gather_mem_stats)
 #endif
 {
+  h.check_complete_insertion ();
+
   size_t size = h.m_size;
 
   if (m_gather_mem_stats)
@@ -675,6 +715,8 @@ template<typename Descriptor, bool Lazy,
 	 template<typename Type> class Allocator>
 hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
 {
+  check_complete_insertion ();
+
   if (!Lazy || m_entries)
     {
       for (size_t i = m_size - 1; i < m_size; i--)
@@ -778,6 +820,8 @@ template<typename Descriptor, bool Lazy,
 void
 hash_table<Descriptor, Lazy, Allocator>::expand ()
 {
+  check_complete_insertion ();
+
   value_type *oentries = m_entries;
   unsigned int oindex = m_size_prime_index;
   size_t osize = size ();
@@ -853,6 +897,8 @@ template<typename Descriptor, bool Lazy,
 void
 hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
 {
+  check_complete_insertion ();
+
   size_t size = m_size;
   size_t nsize = size;
   value_type *entries = m_entries;
@@ -901,6 +947,8 @@ template<typename Descriptor, bool Lazy,
 void
 hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
 {
+  check_complete_insertion ();
+
   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
 		         || is_empty (*slot) || is_deleted (*slot)));
 
@@ -927,6 +975,8 @@ hash_table<Descriptor, Lazy, Allocator>
   if (Lazy && m_entries == NULL)
     m_entries = alloc_entries (size);
 
+  check_complete_insertion ();
+
 #if CHECKING_P
   if (m_sanitize_eq_and_hash)
     verify (comparable, hash);
@@ -976,6 +1026,8 @@ hash_table<Descriptor, Lazy, Allocator>
     }
   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
     expand ();
+  else
+    check_complete_insertion ();
 
 #if CHECKING_P
   if (m_sanitize_eq_and_hash)
@@ -1022,11 +1074,11 @@ hash_table<Descriptor, Lazy, Allocator>
     {
       m_n_deleted--;
       mark_empty (*first_deleted_slot);
-      return first_deleted_slot;
+      return check_insert_slot (first_deleted_slot);
     }
 
   m_n_elements++;
-  return &m_entries[index];
+  return check_insert_slot (&m_entries[index]);
 }
 
 /* Verify that all existing elements in the hash table which are
@@ -1068,6 +1120,8 @@ void
 hash_table<Descriptor, Lazy, Allocator>
 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
 {
+  check_complete_insertion ();
+
   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
   if (slot == NULL)
     return;
@@ -1094,6 +1148,8 @@ hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
   if (Lazy && m_entries == NULL)
     return;
 
+  check_complete_insertion ();
+
   value_type *slot = m_entries;
   value_type *limit = slot + size ();
 
@@ -1210,6 +1266,7 @@ template<typename D>
 static void
 gt_pch_nx (hash_table<D> *h)
 {
+  h->check_complete_insertion ();
   bool success
     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
   gcc_checking_assert (success);


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [17/17] check hash table insertions

[Richard Biener]

> Am 28.12.2022 um 13:51 schrieb Alexandre Oliva via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> On Dec 27, 2022, Alexandre Oliva <oliva@adacore.com> wrote:
> 
>> The number of bugs it revealed tells me that leaving callers in charge
>> of completing insertions is too error prone.  I found this
>> verification code a bit too expensive to enable in general.
> 
> Here's a relatively cheap, checking-only test to catch dangling inserts.
> 
> 
> I've noticed a number of potential problems in hash tables, of three
> kinds: insertion of entries that seem empty, dangling insertions, and
> lookups during insertions.
> 
> These problems may all have the effect of replacing a deleted entry
> with one that seems empty, which may disconnect double-hashing chains
> involving that entry, and thus cause entries to go missing.
> 
> This patch detects such problems by recording a pending insertion and
> checking that it's completed before other potentially-conflicting
> operations.  The additional field is only introduced when checking is
> enabled.

I wonder if on INSERT, pushing a DELETED marker would fix the dangling insert and search during delete problem be whether that would be better from a design point of view? (It of course requires a DELETED representation)

> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChnageLog
> 
>    * hash-table.h (check_complete_insertion, check_insert_slot):
>    New hash_table methods.
>    (m_inserting_slot): New hash_table field.
>    (begin, hash_table ctors, ~hash_table): Check previous insert.
>    (expand, empty_slow, clear_slot, find_with_hash): Likewise.
>    (remote_elt_with_hash, traverse_noresize): Likewise.
>    (gt_pch_nx): Likewise.
>    (find_slot_with_hash): Likewise.  Record requested insert.
> ---
> gcc/hash-table.h |   63 +++++++++++++++++++++++++++++++++++++++++++++++++++---
> 1 file changed, 60 insertions(+), 3 deletions(-)
> 
> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index f4bda6102323e..33753d04b7bdb 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -495,6 +495,7 @@ public:
>     {
>       if (Lazy && m_entries == NULL)
>    return iterator ();
> +      check_complete_insertion ();
>       iterator iter (m_entries, m_entries + m_size);
>       iter.slide ();
>       return iter;
> @@ -551,8 +552,39 @@ private:
>     Descriptor::mark_empty (v);
>   }
> 
> +public:
> +  void check_complete_insertion () const
> +  {
> +#if CHECKING_P
> +    if (!m_inserting_slot)
> +      return;
> +
> +    gcc_checking_assert (m_inserting_slot >= &m_entries[0]
> +             && m_inserting_slot < &m_entries[m_size]);
> +
> +    if (!is_empty (*m_inserting_slot))
> +      m_inserting_slot = NULL;
> +    else
> +      gcc_unreachable ();
> +#endif
> +  }
> +
> +private:
> +  value_type *check_insert_slot (value_type *ret)
> +  {
> +#if CHECKING_P
> +    gcc_checking_assert (is_empty (*ret));
> +    m_inserting_slot = ret;
> +#endif
> +    return ret;
> +  }
> +
> +#if CHECKING_P
> +  mutable value_type *m_inserting_slot;
> +#endif
> +
>   /* Table itself.  */
> -  typename Descriptor::value_type *m_entries;
> +  value_type *m_entries;
> 
>   size_t m_size;
> 
> @@ -607,6 +639,9 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
>                             ATTRIBUTE_UNUSED,
>                             mem_alloc_origin origin
>                             MEM_STAT_DECL) :
> +#if CHECKING_P
> +  m_inserting_slot (0),
> +#endif
>   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
>   m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
> #if GATHER_STATISTICS
> @@ -639,6 +674,9 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
>                             ATTRIBUTE_UNUSED,
>                             mem_alloc_origin origin
>                             MEM_STAT_DECL) :
> +#if CHECKING_P
> +  m_inserting_slot (0),
> +#endif
>   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
>   m_searches (0), m_collisions (0), m_ggc (ggc),
>   m_sanitize_eq_and_hash (sanitize_eq_and_hash)
> @@ -646,6 +684,8 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
>   , m_gather_mem_stats (gather_mem_stats)
> #endif
> {
> +  h.check_complete_insertion ();
> +
>   size_t size = h.m_size;
> 
>   if (m_gather_mem_stats)
> @@ -675,6 +715,8 @@ template<typename Descriptor, bool Lazy,
>     template<typename Type> class Allocator>
> hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
> {
> +  check_complete_insertion ();
> +
>   if (!Lazy || m_entries)
>     {
>       for (size_t i = m_size - 1; i < m_size; i--)
> @@ -778,6 +820,8 @@ template<typename Descriptor, bool Lazy,
> void
> hash_table<Descriptor, Lazy, Allocator>::expand ()
> {
> +  check_complete_insertion ();
> +
>   value_type *oentries = m_entries;
>   unsigned int oindex = m_size_prime_index;
>   size_t osize = size ();
> @@ -853,6 +897,8 @@ template<typename Descriptor, bool Lazy,
> void
> hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
> {
> +  check_complete_insertion ();
> +
>   size_t size = m_size;
>   size_t nsize = size;
>   value_type *entries = m_entries;
> @@ -901,6 +947,8 @@ template<typename Descriptor, bool Lazy,
> void
> hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
> {
> +  check_complete_insertion ();
> +
>   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
>                 || is_empty (*slot) || is_deleted (*slot)));
> 
> @@ -927,6 +975,8 @@ hash_table<Descriptor, Lazy, Allocator>
>   if (Lazy && m_entries == NULL)
>     m_entries = alloc_entries (size);
> 
> +  check_complete_insertion ();
> +
> #if CHECKING_P
>   if (m_sanitize_eq_and_hash)
>     verify (comparable, hash);
> @@ -976,6 +1026,8 @@ hash_table<Descriptor, Lazy, Allocator>
>     }
>   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
>     expand ();
> +  else
> +    check_complete_insertion ();
> 
> #if CHECKING_P
>   if (m_sanitize_eq_and_hash)
> @@ -1022,11 +1074,11 @@ hash_table<Descriptor, Lazy, Allocator>
>     {
>       m_n_deleted--;
>       mark_empty (*first_deleted_slot);
> -      return first_deleted_slot;
> +      return check_insert_slot (first_deleted_slot);
>     }
> 
>   m_n_elements++;
> -  return &m_entries[index];
> +  return check_insert_slot (&m_entries[index]);
> }
> 
> /* Verify that all existing elements in the hash table which are
> @@ -1068,6 +1120,8 @@ void
> hash_table<Descriptor, Lazy, Allocator>
> ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
> {
> +  check_complete_insertion ();
> +
>   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
>   if (slot == NULL)
>     return;
> @@ -1094,6 +1148,8 @@ hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
>   if (Lazy && m_entries == NULL)
>     return;
> 
> +  check_complete_insertion ();
> +
>   value_type *slot = m_entries;
>   value_type *limit = slot + size ();
> 
> @@ -1210,6 +1266,7 @@ template<typename D>
> static void
> gt_pch_nx (hash_table<D> *h)
> {
> +  h->check_complete_insertion ();
>   bool success
>     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
>   gcc_checking_assert (success);
> 
> 
> -- 
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>   Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [17/17] check hash table insertions

[Alexandre Oliva]

On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:

> I wonder if on INSERT, pushing a DELETED marker would fix the dangling
> insert and search during delete problem be whether that would be
> better from a design point of view? (It of course requires a DELETED
> representation)

I'm undecided whether a design that rules out the possibility of not
having DELETED would qualify as unequivocally better.

Unless DELETED takes over the NULL representation, and something else is
used for EMPTY, every INSERT point would have to be adjusted to look for
the non-NULL DELETED representation.  That alone was enough for me to
rule out going down that path.

If we were to change the INSERT callers, it would make sense to
e.g. return a smart pointer that enforced the completion of the
insertion.  But that wouldn't fix lookups during insertion without
requiring a separate DELETED representation.

The one-pending-insertion strategy I implemented was the only one I
could find that addressed all of the pitfalls without significant
overhead.  It caught even one case that the mere element-counting had
failed to catch.

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [14/17] parloops: don't request insert that won't be completed

[Jeff Law]

On 12/28/22 05:30, Alexandre Oliva via Gcc-patches wrote:
> 
> In take_address_of, we may refrain from completing a decl_address
> INSERT if gsi is NULL, so dnn't even ask for an INSERT in this case.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* tree-parloops.cc (take_address_of): Skip INSERT if !gsi.
OK
jeff

Re: [15/17] prevent hash set/map insertion of deleted entries

[Jeff Law]

On 12/28/22 05:32, Alexandre Oliva via Gcc-patches wrote:
> On Dec 27, 2022, David Malcolm <dmalcolm@redhat.com> wrote:
> 
>> Would it make sense to also add assertions that such entries aren't
>> Traits::is_deleted?  (both for hash_map and hash_set)
> 
> Yeah, I guess so.  I've come up with something for hash-table proper
> too, coming up in 17/17.
> 
> 
> Just like the recently-added checks for empty entries, add checks for
> deleted entries as well.  This didn't catch any problems, but it might
> prevent future accidents.  Suggested by David Malcolm.
> 
> Regstrapped on x86_64-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	* hash-map.h (put, get_or_insert): Check that added entry
> 	doesn't look deleted either.
> 	& hash-set.h (add): Likewise.
OK
jeff

Re: [17/17] check hash table insertions

[Richard Biener]

> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva <oliva@adacore.com>:
> 
> On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
> 
>> I wonder if on INSERT, pushing a DELETED marker would fix the dangling
>> insert and search during delete problem be whether that would be
>> better from a design point of view? (It of course requires a DELETED
>> representation)
> 
> I'm undecided whether a design that rules out the possibility of not
> having DELETED would qualify as unequivocally better.
> 
> Unless DELETED takes over the NULL representation, and something else is
> used for EMPTY, every INSERT point would have to be adjusted to look for
> the non-NULL DELETED representation.

Not sure what you mean - I think turning EMPTY (or DELETED) into DELETED at insert time would make the slot occupied for lookups and thus fix lookup during insert.  Of course insert during insert would still fail and possibly return the same slot again.  So the most foolproof design would be a new INSERTING representation.

>  That alone was enough for me to
> rule out going down that path.
> 
> If we were to change the INSERT callers, it would make sense to
> e.g. return a smart pointer that enforced the completion of the
> insertion.  But that wouldn't fix lookups during insertion without
> requiring a separate DELETED representation.
> 
> The one-pending-insertion strategy I implemented was the only one I
> could find that addressed all of the pitfalls without significant
> overhead.  It caught even one case that the mere element-counting had
> failed to catch.

Yes, it’s true that this addresses all issues with just imposing constraints on API use.  But the I wondered how you catched the completion of the insertion?  (I’ll have to
Dig into the patch to see)

Richard 

> 
> -- 
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>   Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [17/17] check hash table insertions

[Alexandre Oliva]

On Dec 29, 2022, Richard Biener <richard.guenther@gmail.com> wrote:

>> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva <oliva@adacore.com>:
>> 
>> On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
>> 
>>> I wonder if on INSERT, pushing a DELETED marker would fix the dangling
>>> insert and search during delete problem be whether that would be
>>> better from a design point of view? (It of course requires a DELETED
>>> representation)
>> 
>> I'm undecided whether a design that rules out the possibility of not
>> having DELETED would qualify as unequivocally better.
>> 
>> Unless DELETED takes over the NULL representation, and something else is
>> used for EMPTY, every INSERT point would have to be adjusted to look for
>> the non-NULL DELETED representation.

> Not sure what you mean

I meant existing code tests that dereferencing the returned slot pointer
yields NULL.  If we were to change the slot value during insert, we'd
have to adjust all callers.

> I think turning EMPTY (or DELETED) into
> DELETED at insert time would make the slot occupied for lookups and
> thus fix lookup during insert.

Yup.

> Of course insert during insert would
> still fail and possibly return the same slot again.

Yeah.

> So the most foolproof design would be a new INSERTING representation.

There's a glitch there: we can't expand with a pending insert.  So we
might need to count inserting nodes separately, or (ideally) be able to
check quickly that insertions have completed.

But then, inserting with a pending insert ought to be caught and
reported, because an insertion invalidates previously-returned slot
pointers, including that of the pending insert.  And that's how I got to
the proposed patch.

>> The one-pending-insertion strategy I implemented was the only one I
>> could find that addressed all of the pitfalls without significant
>> overhead.  It caught even one case that the mere element-counting had
>> failed to catch.

> Yes, it’s true that this addresses all issues with just imposing
> constraints on API use.  But the I wondered how you catched the
> completion of the insertion?  (I’ll have to
> Dig into the patch to see)

Record the slot with the pending insert, and at any subsequent operation
(that could be affected by the pending insert), check and report in case
the insertion was not completed.


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [17/17] check hash table insertions

[Richard Biener]

> Am 30.12.2022 um 09:53 schrieb Alexandre Oliva <oliva@adacore.com>:
> 
> On Dec 29, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
> 
>>>> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva <oliva@adacore.com>:
>>> 
>>> On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
>>> 
>>>> I wonder if on INSERT, pushing a DELETED marker would fix the dangling
>>>> insert and search during delete problem be whether that would be
>>>> better from a design point of view? (It of course requires a DELETED
>>>> representation)
>>> 
>>> I'm undecided whether a design that rules out the possibility of not
>>> having DELETED would qualify as unequivocally better.
>>> 
>>> Unless DELETED takes over the NULL representation, and something else is
>>> used for EMPTY, every INSERT point would have to be adjusted to look for
>>> the non-NULL DELETED representation.
> 
>> Not sure what you mean
> 
> I meant existing code tests that dereferencing the returned slot pointer
> yields NULL.  If we were to change the slot value during insert, we'd
> have to adjust all callers.
> 
>> I think turning EMPTY (or DELETED) into
>> DELETED at insert time would make the slot occupied for lookups and
>> thus fix lookup during insert.
> 
> Yup.
> 
>> Of course insert during insert would
>> still fail and possibly return the same slot again.
> 
> Yeah.
> 
>> So the most foolproof design would be a new INSERTING representation.
> 
> There's a glitch there: we can't expand with a pending insert.  So we
> might need to count inserting nodes separately, or (ideally) be able to
> check quickly that insertions have completed.
> 
> But then, inserting with a pending insert ought to be caught and
> reported, because an insertion invalidates previously-returned slot
> pointers, including that of the pending insert.  And that's how I got to
> the proposed patch.
> 
>>> The one-pending-insertion strategy I implemented was the only one I
>>> could find that addressed all of the pitfalls without significant
>>> overhead.  It caught even one case that the mere element-counting had
>>> failed to catch.
> 
>> Yes, it’s true that this addresses all issues with just imposing
>> constraints on API use.  But the I wondered how you catched the
>> completion of the insertion?  (I’ll have to
>> Dig into the patch to see)
> 
> Record the slot with the pending insert, and at any subsequent operation
> (that could be affected by the pending insert), check and report in case
> the insertion was not completed.

Ah, OK, so the completion is checked at the next conflicting operation.  Yeah, that makes sense I guess.

Thus OK (I think Jeff already approved the patch).

Thanks and happy holidays!

Richard 

> 
> 
> -- 
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>   Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [17/17] check hash table insertions

[Alexandre Oliva]

On Dec 30, 2022, Richard Biener <richard.guenther@gmail.com> wrote:

> Ah, OK, so the completion is checked at the next conflicting
> operation.  Yeah, that makes sense I guess.

*nod*

> Thus OK (I think Jeff already approved the patch).

Thanks, 16/ and 17/ were still pending reviews.
I'm installing 17/ now.

> Thanks and happy holidays!

Happy GNU Year! :-)

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>

Re: [16/17] check hash table counts at expand

[Richard Biener]

On Wed, Dec 28, 2022 at 1:47 PM Alexandre Oliva via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Dec 28, 2022, Martin Liška <mliska@suse.cz> wrote:
>
> > I really like the verification code you added. It's quite similar to what
> > I added to hash-table.h:
>
> *nod*
>
> Prompted by your encouragement, I've combined the element count
> verification code with the verify() loop, and also added it to expand,
> where it can be done cheaply.
>
>
> Add cheap verification of element and deleted entry counts during
> expand and hash verify.
>
> Regstrapped on x86_64-linux-gnu.  Ok to install?

OK.

>
> for  gcc/ChangeLog
>
>         * hash-table.h (expand): Check elements and deleted counts.
>         (verify): Likewise.
> ---
>  gcc/hash-table.h |   35 ++++++++++++++++++++++++++++-------
>  1 file changed, 28 insertions(+), 7 deletions(-)
>
> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index 53507daae26c3..f4bda6102323e 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -805,19 +805,28 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>      hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
>                                                     * osize);
>
> +  size_t n_deleted = m_n_deleted;
> +
>    m_entries = nentries;
>    m_size = nsize;
>    m_size_prime_index = nindex;
>    m_n_elements -= m_n_deleted;
>    m_n_deleted = 0;
>
> +  size_t n_elements = m_n_elements;
> +
>    value_type *p = oentries;
>    do
>      {
>        value_type &x = *p;
>
> -      if (!is_empty (x) && !is_deleted (x))
> +      if (is_empty (x))
> +       ;
> +      else if (is_deleted (x))
> +       n_deleted--;
> +      else
>          {
> +         n_elements--;
>            value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>           new ((void*) q) value_type (std::move (x));
>           /* After the resources of 'x' have been moved to a new object at 'q',
> @@ -829,6 +838,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>      }
>    while (p < olimit);
>
> +  gcc_checking_assert (!n_elements && !n_deleted);
> +
>    if (!m_ggc)
>      Allocator <value_type> ::data_free (oentries);
>    else
> @@ -1018,8 +1029,9 @@ hash_table<Descriptor, Lazy, Allocator>
>    return &m_entries[index];
>  }
>
> -/* Verify that all existing elements in th hash table which are
> -   equal to COMPARABLE have an equal HASH value provided as argument.  */
> +/* Verify that all existing elements in the hash table which are
> +   equal to COMPARABLE have an equal HASH value provided as argument.
> +   Also check that the hash table element counts are correct.  */
>
>  template<typename Descriptor, bool Lazy,
>          template<typename Type> class Allocator>
> @@ -1027,14 +1039,23 @@ void
>  hash_table<Descriptor, Lazy, Allocator>
>  ::verify (const compare_type &comparable, hashval_t hash)
>  {
> +  size_t n_elements = m_n_elements;
> +  size_t n_deleted = m_n_deleted;
>    for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
>      {
>        value_type *entry = &m_entries[i];
> -      if (!is_empty (*entry) && !is_deleted (*entry)
> -         && hash != Descriptor::hash (*entry)
> -         && Descriptor::equal (*entry, comparable))
> -       hashtab_chk_error ();
> +      if (!is_empty (*entry))
> +       {
> +         n_elements--;
> +         if (is_deleted (*entry))
> +           n_deleted--;
> +         else if (hash != Descriptor::hash (*entry)
> +                  && Descriptor::equal (*entry, comparable))
> +           hashtab_chk_error ();
> +       }
>      }
> +  if (hash_table_sanitize_eq_limit >= m_size)
> +    gcc_checking_assert (!n_elements && !n_deleted);
>  }
>
>  /* This function deletes an element with the given COMPARABLE value
>
>
> --
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>    Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>