Message ID | ork01sjlmo.fsf@lxoliva.fsfla.org |
---|---|
State | New |
Headers | show |
Series | None | expand |
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>
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;