[16/17] check hash table counts at expand
Checks
Commit Message
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?
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(-)
Comments
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>
@@ -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