[00/13] check hash table counts

  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(+)
  

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
> 
>