[00/13] check hash table counts

[Alexandre Oliva <oliva@adacore.com>]

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>