On 11/14/2017 02:30 PM, Jakub Jelinek wrote:
On Tue, Nov 14, 2017 at 02:24:28PM -0700, Martin Sebor wrote:
On 11/14/2017 02:04 PM, Jakub Jelinek wrote:
Hi!
strlen_to_stridx.get (rhs1) returns an address into the hash_map, and
strlen_to_stridx.put (lhs, *ps); (in order to be efficient) doesn't make a
copy of the argument just in case, first inserts the slot into it which
may cause reallocation, and only afterwards runs the copy ctor to assign
the value into the new slot. So, passing it a reference to something
in the hash_map is wrong. Fixed thusly, bootstrapped/regtested on
x86_64-linux and i686-linux, ok for trunk?
This seems like an unnecessary gotcha that should be possible to
avoid in the hash_map. The corresponding standard containers
require it to work and so it's surprising when it doesn't in GCC.
I've been looking at how this is implemented and it seems to me
that a fix should be doable by having the hash_map check to see if
the underlying table needs to expand and if so, create a temporary
copy of the element before reallocating it.
That would IMHO just slow down and enlarge the hash_map for all users,
even when most of them don't really need it.
While it is reasonable for STL containers to make sure it works, we
aren't using STL containers and can pose additional restrictions.
How about at least detecting the problem then? The attached patch
catches the bug while running the Wstringop-truncation tests and
passes x86_64 bootstrap.
Martin
gcc/ChangeLog:
* gcc/hash-table.h (find_slot_with_hash, expand): Add argument.
(find_slot): Adjust.
* gcc/hash-map.h (put): Adjust.
* gcc/hash-set.h (add): Adjust.
diff --git a/gcc/hash-map.h b/gcc/hash-map.h
index 73f1c54..b8bff72 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -134,7 +134,7 @@ public:
bool put (const Key &k, const Value &v)
{
hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
- INSERT);
+ INSERT, &v);
bool existed = !hash_entry::is_empty (*e);
if (!existed)
e->m_key = k;
diff --git a/gcc/hash-set.h b/gcc/hash-set.h
index d2247d3..475a358 100644
--- a/gcc/hash-set.h
+++ b/gcc/hash-set.h
@@ -44,7 +44,7 @@ public:
bool add (const Key &k)
{
- Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
+ Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT, &k);
bool existed = !Traits::is_empty (*e);
if (!existed)
*e = k;
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 64d3157..fc39ad93 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -411,7 +411,8 @@ public:
value_type *find_slot (const value_type &value, insert_option insert)
{
- return find_slot_with_hash (value, Descriptor::hash (value), insert);
+ return find_slot_with_hash (value, Descriptor::hash (value), insert,
+ &value);
}
/* This function searches for a hash table slot containing an entry
@@ -422,7 +423,8 @@ public:
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
value_type *find_slot_with_hash (const compare_type &comparable,
- hashval_t hash, enum insert_option insert);
+ hashval_t hash, enum insert_option insert,
+ const void *iptr = NULL);
/* This function deletes an element with the given COMPARABLE value
from hash table starting with the given HASH. If there is no
@@ -504,7 +506,7 @@ private:
value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
value_type *find_empty_slot_for_expand (hashval_t);
bool too_empty_p (unsigned int);
- void expand ();
+ void expand (const void* = NULL);
static bool is_deleted (value_type &v)
{
return Descriptor::is_deleted (v);
@@ -706,11 +708,12 @@ hash_table<Descriptor, Allocator>::too_empty_p (unsigned int elts)
of the table after the call will be about 50%. Naturally the hash
table must already exist. Remember also that the place of the
table entries is changed. If memory allocation fails, this function
- will abort. */
+ will abort. If PTR points into the existing table, the function
+ will abort in checking mode. */
template<typename Descriptor, template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>::expand ()
+hash_table<Descriptor, Allocator>::expand (const void *ptr /* = NULL */)
{
value_type *oentries = m_entries;
unsigned int oindex = m_size_prime_index;
@@ -718,6 +721,15 @@ hash_table<Descriptor, Allocator>::expand ()
value_type *olimit = oentries + osize;
size_t elts = elements ();
+#if CHECKING_P
+ /* Verify that the pointer doesn't point into the table to detect
+ insertions of existing elements. */
+ uintptr_t iptr = (uintptr_t)ptr;
+ uintptr_t ibeg = (uintptr_t)oentries;
+ uintptr_t iend = (uintptr_t)olimit;
+ gcc_checking_assert (iptr < ibeg || iend < iptr);
+#endif
+
/* Resize only when table after removal of unused elements is either
too full or too empty. */
unsigned int nindex;
@@ -866,17 +878,22 @@ hash_table<Descriptor, Allocator>
HASH. To delete an entry, call this with insert=NO_INSERT, then
call clear_slot on the slot returned (possibly after doing some
checks). To insert an entry, call this with insert=INSERT, then
- write the value you want into the returned slot. When inserting an
- entry, NULL may be returned if memory allocation fails. */
+ write the value you want into the returned slot. When inserting
+ an entry, NULL may be returned if memory allocation fails.
+ If PTR points into an element already in the table and the table
+ is expanded, the function aborts. This makes it possible to
+ detect insertions of elements that are already in the table and
+ references to which would be invalidated by the reallocation that
+ results from the insertion. */
template<typename Descriptor, template<typename Type> class Allocator>
typename hash_table<Descriptor, Allocator>::value_type *
hash_table<Descriptor, Allocator>
::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
- enum insert_option insert)
+ enum insert_option insert, const void *ptr)
{
if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
- expand ();
+ expand (ptr);
m_searches++;
