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

[Richard Biener <richard.guenther@gmail.com>]

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>