Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables.

["Martin Liška" <mliska@suse.cz>]

[-- Attachment #1: Type: text/plain, Size: 586 bytes --]

On 10/30/18 11:03 AM, Jakub Jelinek wrote:
> On Mon, Oct 29, 2018 at 04:14:21PM +0100, Martin Liška wrote:
>> +hashtab_chk_error ()
>> +{
>> +  fprintf (stderr, "hash table checking failed: "
>> +	   "equal operator returns true for a pair "
>> +	   "of values with a different hash value");
> 
> BTW, either use internal_error here, or at least if using fprintf
> terminate with \n, in your recent mail I saw:
> ...different hash valueduring RTL pass: vartrack
>                     ^^^^^^

Sure, fixed in attached patch.

Martin

> 
>> +  gcc_unreachable ();
>> +}
> 
> 	Jakub
> 


[-- Attachment #2: 0001-Sanitize-equals-and-hash-functions-in-hash-tables.patch --]
[-- Type: text/x-patch, Size: 2429 bytes --]

From 0d9c979c845580a98767b83c099053d36eb49bb9 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 29 Oct 2018 09:38:21 +0100
Subject: [PATCH] Sanitize equals and hash functions in hash-tables.

---
 gcc/hash-table.h | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index bd83345c7b8..694eedfc4be 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -503,6 +503,7 @@ private:
 
   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
   value_type *find_empty_slot_for_expand (hashval_t);
+  void verify (const compare_type &comparable, hashval_t hash);
   bool too_empty_p (unsigned int);
   void expand ();
   static bool is_deleted (value_type &v)
@@ -882,8 +883,12 @@ hash_table<Descriptor, Allocator>
   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
     expand ();
 
-  m_searches++;
+#if ENABLE_EXTRA_CHECKING
+    if (insert == INSERT)
+      verify (comparable, hash);
+#endif
 
+  m_searches++;
   value_type *first_deleted_slot = NULL;
   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
@@ -930,6 +935,39 @@ hash_table<Descriptor, Allocator>
   return &m_entries[index];
 }
 
+#if ENABLE_EXTRA_CHECKING
+
+/* Report a hash table checking error.  */
+
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+static void
+hashtab_chk_error ()
+{
+  fprintf (stderr, "hash table checking failed: "
+	   "equal operator returns true for a pair "
+	   "of values with a different hash value\n");
+  gcc_unreachable ();
+}
+
+/* Verify that all existing elements in th hash table which are
+   equal to COMPARABLE have an equal HASH value provided as argument.  */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator>
+::verify (const compare_type &comparable, hashval_t hash)
+{
+  for (size_t i = 0; i < 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 ();
+    }
+}
+#endif
+
 /* This function deletes an element with the given COMPARABLE value
    from hash table starting with the given HASH.  If there is no
    matching element in the hash table, this function does nothing. */
-- 
2.19.0