Re: [00/13] check hash table counts

["Martin Liška" <mliska@suse.cz>]

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