Enable sanitization for hash tables.

2019-06-07  Martin Liska  <mliska@suse.cz>

	* cselib.c (cselib_init): Disable hash table
	sanitization.
	* hash-set.h: Pass new default argument to m_table.
	* hash-table.c: Add global variable with hash table
	sanitization limit.
	* hash-table.h (Allocator>::hash_table): Add new argument
	to ctor.
	(hashtab_chk_error): New.
	* params.def (PARAM_HASH_TABLE_VERIFICATION_LIMIT): New.
	* toplev.c (process_options): Set hash_table_sanitize_eq_limit
	from the PARAM_HASH_TABLE_VERIFICATION_LIMIT value.

From-SVN: r272038

1 files changed, 56 insertions, 4 deletions

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 4178616..686a13d 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -295,6 +295,8 @@ struct prime_ent
 
 extern struct prime_ent const prime_tab[];
 
+/* Limit number of comparisons when calling hash_table<>::verify.  */
+extern unsigned int hash_table_sanitize_eq_limit;
 
 /* Functions for computing hash table indexes.  */
 
@@ -371,10 +373,12 @@ class hash_table
 
 public:
   explicit hash_table (size_t, bool ggc = false,
+		       bool sanitize_eq_and_hash = true,
 		       bool gather_mem_stats = GATHER_STATISTICS,
 		       mem_alloc_origin origin = HASH_TABLE_ORIGIN
 		       CXX_MEM_STAT_INFO);
   explicit hash_table (const hash_table &, bool ggc = false,
+		       bool sanitize_eq_and_hash = true,
 		       bool gather_mem_stats = GATHER_STATISTICS,
 		       mem_alloc_origin origin = HASH_TABLE_ORIGIN
 		       CXX_MEM_STAT_INFO);
@@ -516,6 +520,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)
@@ -564,6 +569,9 @@ private:
   /* if m_entries is stored in ggc memory.  */
   bool m_ggc;
 
+  /* True if the table should be sanitized for equal and hash functions.  */
+  bool m_sanitize_eq_and_hash;
+
   /* If we should gather memory statistics for the table.  */
 #if GATHER_STATISTICS
   bool m_gather_mem_stats;
@@ -586,12 +594,13 @@ extern void dump_hash_table_loc_statistics (void);
 template<typename Descriptor, bool Lazy,
 	 template<typename Type> class Allocator>
 hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
+						     bool sanitize_eq_and_hash,
 						     bool gather_mem_stats
 						     ATTRIBUTE_UNUSED,
 						     mem_alloc_origin origin
 						     MEM_STAT_DECL) :
   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
-  m_ggc (ggc)
+  m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
 #if GATHER_STATISTICS
   , m_gather_mem_stats (gather_mem_stats)
 #endif
@@ -617,12 +626,14 @@ template<typename Descriptor, bool Lazy,
 	 template<typename Type> class Allocator>
 hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
 						     bool ggc,
+						     bool sanitize_eq_and_hash,
 						     bool gather_mem_stats
 						     ATTRIBUTE_UNUSED,
 						     mem_alloc_origin origin
 						     MEM_STAT_DECL) :
   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
-  m_searches (0), m_collisions (0), m_ggc (ggc)
+  m_searches (0), m_collisions (0), m_ggc (ggc),
+  m_sanitize_eq_and_hash (sanitize_eq_and_hash)
 #if GATHER_STATISTICS
   , m_gather_mem_stats (gather_mem_stats)
 #endif
@@ -912,7 +923,13 @@ hash_table<Descriptor, Lazy, Allocator>
       entry = &m_entries[index];
       if (is_empty (*entry)
           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
-        return *entry;
+	{
+#if CHECKING_P
+	  if (m_sanitize_eq_and_hash)
+	    verify (comparable, hash);
+#endif
+	  return *entry;
+	}
     }
 }
 
@@ -941,8 +958,12 @@ hash_table<Descriptor, Lazy, Allocator>
   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
     expand ();
 
-  m_searches++;
+#if CHECKING_P
+  if (m_sanitize_eq_and_hash)
+    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);
@@ -989,6 +1010,37 @@ hash_table<Descriptor, Lazy, Allocator>
   return &m_entries[index];
 }
 
+/* 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, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>
+::verify (const compare_type &comparable, hashval_t hash)
+{
+  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 ();
+    }
+}
+
 /* 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. */