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

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

[Alexandre Oliva]

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?


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>

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

[Richard Biener]

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>