| Message ID | 20171114210426.GL14653@tucnak |
|---|---|
| State | New |
| Headers | show |
| Series | Fix use-after-free in the strlen pass (PR tree-optimization/82977) | expand |
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? > > 2017-11-14 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/82977 > * tree-ssa-strlen.c (strlen_optimize_stmt): Pass a reference to a copy > constructed temporary to strlen_to_stridx.put. I've been seeing a couple new tests flip between pass and fail recently. I wonder if this is the ultimate cause. My brain isn't working at the moment (sick and too little sleep), so not going to try and review it right now. jeff
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. Martin
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. Jakub
On 11/14/2017 02:10 PM, Jeff Law 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? >> >> 2017-11-14 Jakub Jelinek <jakub@redhat.com> >> >> PR tree-optimization/82977 >> * tree-ssa-strlen.c (strlen_optimize_stmt): Pass a reference to a copy >> constructed temporary to strlen_to_stridx.put. > I've been seeing a couple new tests flip between pass and fail recently. > I wonder if this is the ultimate cause. I've been noticing it for quite a while, even before the commit, so I suspect something else is going on in addition to this bug. Martin
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++;
On 11/14/2017 02:30 PM, Martin Sebor wrote: > On 11/14/2017 02:10 PM, Jeff Law 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? >>> >>> 2017-11-14 Jakub Jelinek <jakub@redhat.com> >>> >>> PR tree-optimization/82977 >>> * tree-ssa-strlen.c (strlen_optimize_stmt): Pass a reference to a >>> copy >>> constructed temporary to strlen_to_stridx.put. >> I've been seeing a couple new tests flip between pass and fail recently. >> I wonder if this is the ultimate cause. > > I've been noticing it for quite a while, even before the commit, > so I suspect something else is going on in addition to this bug. I'm referring specifically to the Wstringop-truncation tests. They're ping-ponging between PASS/FAIL here with alarming regularity and no sense of rhyme or reason. If I had to guess I'd guess uninit memory, dangling pointer or the like, which is precisely the kind of problem the patch is meant to fix. jeff
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. But when we make our containers behave differently than the STL it makes it much easier for someone to make a mistake such as this one. IMHO this kind of difference in behavior is silly and long term just makes our jobs harder. I'd vote for fixing our containers. jeff
On Tue, Nov 14, 2017 at 04:46:01PM -0700, Martin Sebor wrote: > 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. Well, IMHO then the extra argument should be there only #if CHECKING_P, so that you don't grow or slow down --enable-checking=release, and more importantly, > 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 > + This is the wrong spot to check it. > /* 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++; It should be checked here. if (insert == INSERT) { #if CHECKING_P ... #endif if (m_size * 3 <= m_n_elements * 4) expand (); } because otherwise you'll find the problem only if you are unlucky enough that the hash table is expanded, while checking it this way would ensure that there are no such potential problems. Jakub
On Tue, 14 Nov 2017, Jeff Law wrote: > 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. > But when we make our containers behave differently than the STL it makes > it much easier for someone to make a mistake such as this one. > > IMHO this kind of difference in behavior is silly and long term just > makes our jobs harder. > > I'd vote for fixing our containers. I'd argue that this is simply a programming error and I doubt the libstdc++ variant works by design/specification. So let's go with Jakubs patch. We can do the extra checking as followup. Jakub, your patch is ok. Thanks, Richard.
On 11/15/2017 01:28 AM, Richard Biener wrote: > On Tue, 14 Nov 2017, Jeff Law wrote: > >> 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. >> But when we make our containers behave differently than the STL it makes >> it much easier for someone to make a mistake such as this one. >> >> IMHO this kind of difference in behavior is silly and long term just >> makes our jobs harder. >> >> I'd vote for fixing our containers. > > I'd argue that this is simply a programming error and I doubt the > libstdc++ variant works by design/specification. It's by design. You can find the discussion of this very issue in C++ standard library issue 526: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 Martin
--- gcc/tree-ssa-strlen.c.jj 2017-11-13 09:31:30.000000000 +0100 +++ gcc/tree-ssa-strlen.c 2017-11-14 10:28:30.583110162 +0100 @@ -2968,7 +2968,7 @@ strlen_optimize_stmt (gimple_stmt_iterat tree rhs1 = gimple_assign_rhs1 (stmt); if (stridx_strlenloc *ps = strlen_to_stridx.get (rhs1)) - strlen_to_stridx.put (lhs, *ps); + strlen_to_stridx.put (lhs, stridx_strlenloc (*ps)); } else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) {