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