Re: [18/18] hash table: enforce testing is_empty before is_deleted

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

On Thu, Jan 12, 2023 at 10:32 PM Alexandre Oliva via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
> Existing hash_table traits that use the same representation for empty
> and deleted slots reject marking slots as deleted, and to not pass
> is_deleted for slots that pass is_empty.
>
> Nevertheless, nearly everywhere, we only test for is_deleted after
> checking that !is_empty first.  The one exception was the copy
> constructor, that would fail if traits recognized is_empty slots as
> is_deleted, but then refused to mark_deleted.
>
> This asymmetry is neither necessary nor desirable, and there is a
> theoretical risk that traits might not only fail to refuse to
> mark_deleted, but also return is_deleted for is_empty slots.
>
> This patch introduces checks that detect these potentially problematic
> situations, and reorders the tests in the copy constructor so as to
> use the conventional testing order and thus avoid them.
>
> Regstrapped on x86_64-linux-gnu.  Ok to install?

OK.

>
> for  gcc/ChangeLog
>
>         * hash-table.h (is_deleted): Precheck !is_empty.
>         (mark_deleted): Postcheck !is_empty.
>         (copy constructor): Test is_empty before is_deleted.
> ---
>  gcc/hash-table.h |   16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
>
> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index 1d3166504c38e..e37625dc315bf 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -534,6 +534,11 @@ private:
>    void expand ();
>    static bool is_deleted (value_type &v)
>    {
> +    /* Traits are supposed to avoid recognizing elements as both empty
> +       and deleted, but to fail safe in case custom traits fail to do
> +       that, make sure we never test for is_deleted without having
> +       first ruled out is_empty.  */
> +    gcc_checking_assert (!Descriptor::is_empty (v));
>      return Descriptor::is_deleted (v);
>    }
>
> @@ -545,6 +550,11 @@ private:
>    static void mark_deleted (value_type &v)
>    {
>      Descriptor::mark_deleted (v);
> +    /* Traits are supposed to refuse to set elements as deleted if
> +       those would be indistinguishable from empty, but to fail safe
> +       in case custom traits fail to do that, check that the
> +       just-deleted element does not look empty.  */
> +    gcc_checking_assert (!Descriptor::is_empty (v));
>    }
>
>    static void mark_empty (value_type &v)
> @@ -700,9 +710,11 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
>        for (size_t i = 0; i < size; ++i)
>         {
>           value_type &entry = h.m_entries[i];
> -         if (is_deleted (entry))
> +         if (is_empty (entry))
> +           continue;
> +         else if (is_deleted (entry))
>             mark_deleted (nentries[i]);
> -         else if (!is_empty (entry))
> +         else
>             new ((void*) (nentries + i)) value_type (entry);
>         }
>        m_entries = nentries;
>
> --
> 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>