| Message ID | 20110906162854.5C60B190B10@elbrus2.mtv.corp.google.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Sep 6, 2011 at 9:28 AM, Paul Pluzhnikov <ppluzhnikov@google.com> wrote: > This patch adds a lightweight self-consistency check to many vector > operations. Google issue 5246356. Sorry, forgot to mention: tested by doing bootstrap and make check on Linux/x86_64.
On Tue, Sep 6, 2011 at 12:28, Paul Pluzhnikov <ppluzhnikov@google.com> wrote: > Greetings, > > This patch adds a lightweight self-consistency check to many vector > operations. Google issue 5246356. > > Ok for google/integration branch? > > Thanks, > -- > > > 2011-09-06 Paul Pluzhnikov <ppluzhnikov@google.com> > > * include/bits/stl_vector.h (__is_valid): New function. > (begin, end, size, capacity, swap, clear): Call it. > * include/bits/vector.tcc (operator=): Likewise. OK. Any reason not to send this (or a variant) to mainline? Diego.
On Tue, Sep 6, 2011 at 9:44 AM, Diego Novillo <dnovillo@google.com> wrote:
> OK. Any reason not to send this (or a variant) to mainline?
AFAIU, mainline is not interested -- there is already a debug mode (enabled
by _GLIBCXX_DEBUG), which catches many of the same bugs (and more), and
introduction of "parallel" debug modes is undesirable.
Unfortunately, _GLIBCXX_DEBUG makes no performance guarantees (making some
normally constant-time operations O(N), etc.) and so we can't just turn
it on in Google.
Thanks,
On Tue, Sep 6, 2011 at 12:54, Paul Pluzhnikov <ppluzhnikov@google.com> wrote: > On Tue, Sep 6, 2011 at 9:44 AM, Diego Novillo <dnovillo@google.com> wrote: > >> OK. Any reason not to send this (or a variant) to mainline? > > AFAIU, mainline is not interested -- there is already a debug mode (enabled > by _GLIBCXX_DEBUG), which catches many of the same bugs (and more), and > introduction of "parallel" debug modes is undesirable. > > Unfortunately, _GLIBCXX_DEBUG makes no performance guarantees (making some > normally constant-time operations O(N), etc.) and so we can't just turn > it on in Google. Right. That's why I thought of a variant. Maybe we want to have levels of checking, or a _GLBICXX_DEBUG_FAST. But this is something to discuss with libstdc++ (CC'd). Diego. > > Thanks, > -- > Paul Pluzhnikov >
On Tue, Sep 6, 2011 at 10:46 AM, Diego Novillo <dnovillo@google.com> wrote: > On Tue, Sep 6, 2011 at 12:54, Paul Pluzhnikov <ppluzhnikov@google.com> wrote: >> On Tue, Sep 6, 2011 at 9:44 AM, Diego Novillo <dnovillo@google.com> wrote: >> >>> OK. Any reason not to send this (or a variant) to mainline? >> >> AFAIU, mainline is not interested -- there is already a debug mode (enabled >> by _GLIBCXX_DEBUG), which catches many of the same bugs (and more), and >> introduction of "parallel" debug modes is undesirable. >> >> Unfortunately, _GLIBCXX_DEBUG makes no performance guarantees (making some >> normally constant-time operations O(N), etc.) and so we can't just turn >> it on in Google. > > Right. That's why I thought of a variant. Maybe we want to have > levels of checking, or a _GLBICXX_DEBUG_FAST. Which would introduce a "parallel" debug mode ... which has been rejected in the past. > But this is something to discuss with libstdc++ (CC'd). Sure. If the "parallel" debug mode is more tenable now, I am all for it. To give some context, in a large code base (> 1e6 lines of C++ code), the checks added in this patch found 20 bugs. Most (though not all) of these bugs could also have been found with Valgrind and (probably) with _GLIBCXX_DEBUG, but the runtime cost of running such heavy-weight checks over the entire code base is prohibitive. Thanks,
On 6 September 2011 19:01, Paul Pluzhnikov wrote: > >> But this is something to discuss with libstdc++ (CC'd). > > Sure. If the "parallel" debug mode is more tenable now, I am all for it. I don't think anything has changed. I'm not excited by the idea of another debug mode, especially not this patch, which would never get into mainline. It is always valid to call vector::begin(), it's 'noexcept' so the patch will cause immediate calls to std::terminate, so why throw instead of just aborting? Why is __valid not named consistently with the v3 naming style? What's a dangling vector anyway? One that has been moved from? > To give some context, in a large code base (> 1e6 lines of C++ code), > the checks added in this patch found 20 bugs. > > Most (though not all) of these bugs could also have been found with Valgrind > and (probably) with _GLIBCXX_DEBUG, but the runtime cost of running such > heavy-weight checks over the entire code base is prohibitive. You can do: #ifdef MY_DEBUG_FLAG #include <debug/vector> namespace v = __gnu_debug; #else #include <vector> namespace v = std; # Then use v::vector in specific places to only enable the checks in some places.
On 6 September 2011 20:23, Jonathan Wakely wrote: > > What's a dangling vector anyway? One that has been moved from? Apparently not, since a moved-from vector would pass __valid() (as indeed it should) So I'm quite curious what bugs this catches. The existing debug mode catches some fairly subtle cases of user error such as comparing iterators from different containers, or dereferencing past-the-end iterators. This patch seems to catch user errors related to ... what? Heap corruption? Using a vector after its destructor runs? Those are pretty serious, un-subtle errors and not specific to vector, so why add code to vector (code which isn't 100% reliable if it only catches corruption after the memory is reused and new data written to it) to detect more general problems that can happen to any type? The fact the patch did catch real bugs doesn't mean it's a good idea, as you say, those bugs probably could have been caught in other ways.
On Tue, Sep 6, 2011 at 12:44 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: > On 6 September 2011 20:23, Jonathan Wakely wrote: >> >> What's a dangling vector anyway? One that has been moved from? > > Apparently not, since a moved-from vector would pass __valid() (as > indeed it should) > > So I'm quite curious what bugs this catches. The garden variety "use after free": vector<> *v = new vector<>; ... delete v; ... for (it = v->begin(); it != v->end(); ++it) // Oops! > The existing debug mode > catches some fairly subtle cases of user error such as comparing > iterators from different containers, or dereferencing past-the-end > iterators. This patch seems to catch user errors related to ... what? > Heap corruption? Using a vector after its destructor runs? Those > are pretty serious, un-subtle errors and not specific to vector, so > why add code to vector (code which isn't 100% reliable if it only > catches corruption after the memory is reused and new data written to > it) It is 100% percent reliable for us, due to use of a debugging allocator which scribbles on all free()d memory. But yes, that's one more reason why this patch is not really good for upstream. > to detect more general problems that can happen to any type? We can't (easily) catch the general problem. This patch allows us to easily catch this particular instance of it. > The fact the patch did catch real bugs doesn't mean it's a good idea, > as you say, those bugs probably could have been caught in other ways. Sure -- we have other ways to catch the these bugs. They are not very practical at the moment due to their runtime overhead. As for your other suggestion: enabling _GLIBCXX_DEBUG just for vector, that didn't occur to me and is something I'd like to explore. Thanks,
On 6 Sep 2011, at 21:19, Paul Pluzhnikov wrote: > On Tue, Sep 6, 2011 at 12:44 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: >> On 6 September 2011 20:23, Jonathan Wakely wrote: >>> >>> What's a dangling vector anyway? One that has been moved from? >> >> Apparently not, since a moved-from vector would pass __valid() (as >> indeed it should) >> >> So I'm quite curious what bugs this catches. > > The garden variety "use after free": > > vector<> *v = new vector<>; > ... > delete v; > ... > > for (it = v->begin(); it != v->end(); ++it) // Oops! > >> The existing debug mode >> catches some fairly subtle cases of user error such as comparing >> iterators from different containers, or dereferencing past-the-end >> iterators. This patch seems to catch user errors related to ... what? >> Heap corruption? Using a vector after its destructor runs? Those >> are pretty serious, un-subtle errors and not specific to vector, so >> why add code to vector (code which isn't 100% reliable if it only >> catches corruption after the memory is reused and new data written to >> it) > > It is 100% percent reliable for us, due to use of a debugging allocator > which scribbles on all free()d memory. > > But yes, that's one more reason why this patch is not really good for > upstream. > >> to detect more general problems that can happen to any type? > > We can't (easily) catch the general problem. This patch allows us to easily > catch this particular instance of it. > >> The fact the patch did catch real bugs doesn't mean it's a good idea, >> as you say, those bugs probably could have been caught in other ways. > > Sure -- we have other ways to catch the these bugs. They are not very > practical at the moment due to their runtime overhead. > > As for your other suggestion: enabling _GLIBCXX_DEBUG just for vector, > that didn't occur to me and is something I'd like to explore. It might be interesting to profile your app under _GLIBCXX_DEBUG, and see where the high costs are. I previously found that stable_sort had a stupidly high cost, and it turned out with some tweaking we could get just as much protection with a lower cost. Chris
On 6 September 2011 21:19, Paul Pluzhnikov wrote: > On Tue, Sep 6, 2011 at 12:44 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: >> On 6 September 2011 20:23, Jonathan Wakely wrote: >>> >>> What's a dangling vector anyway? One that has been moved from? >> >> Apparently not, since a moved-from vector would pass __valid() (as >> indeed it should) >> >> So I'm quite curious what bugs this catches. > > The garden variety "use after free": > > vector<> *v = new vector<>; > ... > delete v; > ... > > for (it = v->begin(); it != v->end(); ++it) // Oops! Eurgh, the occurrence of "delete" in anything except a destructor is a code smell that should have led someone to find those bugs anyway! Obviously the code above is a trivial example, but it's unforgivable to write that - patching vector to catch it is definitely solving the wrong problem in the wrong place! >> The existing debug mode >> catches some fairly subtle cases of user error such as comparing >> iterators from different containers, or dereferencing past-the-end >> iterators. This patch seems to catch user errors related to ... what? >> Heap corruption? Using a vector after its destructor runs? Those >> are pretty serious, un-subtle errors and not specific to vector, so >> why add code to vector (code which isn't 100% reliable if it only >> catches corruption after the memory is reused and new data written to >> it) > > It is 100% percent reliable for us, due to use of a debugging allocator > which scribbles on all free()d memory. Aha. > But yes, that's one more reason why this patch is not really good for > upstream. > >> to detect more general problems that can happen to any type? > > We can't (easily) catch the general problem. This patch allows us to easily > catch this particular instance of it. Sure, but so does adding "assert(this);" at the top of every member function to check you don't call through a null pointer, but that doesn't make it a good idea :-) I'm not 100% against a lighter weight debug mode, but it would have to offer some pretty convincing benefits and I don't see this patch being widely useful enough to warrant a separate mode. Especially as the existing debug mode is *much* faster than it used to be for some workloads. >> The fact the patch did catch real bugs doesn't mean it's a good idea, >> as you say, those bugs probably could have been caught in other ways. > > Sure -- we have other ways to catch the these bugs. They are not very > practical at the moment due to their runtime overhead. > > As for your other suggestion: enabling _GLIBCXX_DEBUG just for vector, > that didn't occur to me and is something I'd like to explore. It's something I do quite often, so that specific types can be switched to use debug mode during some builds, or for some unit tests, without having to turn on the extra checks for every use of vector (or other std containers) in the entire app. Also, if your code uses a typedef like: typedef v::vector<Data> vector_type; and you consistently use that typedef (rather than referring to std::vector<Data> directly) then it can be relatively painless to turn debug mode on and off for specific pieces of code. Even the unconventional-looking "v::vector" (or "my_debug_switch_123::vector") only gets mentioned in one place.
On Tue, Sep 6, 2011 at 1:33 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: >> for (it = v->begin(); it != v->end(); ++it) // Oops! > > Eurgh, the occurrence of "delete" in anything except a destructor is a > code smell that should have led someone to find those bugs anyway! > Obviously the code above is a trivial example, but it's unforgivable > to write that I can assure you that the actual code that exhibited these bugs was much subtler than that, and the bugs were not immediately obvious. Sometimes they were not immediately obvious even after running Valgrind on the buggy code and getting allocation/deletion/access stack traces with source corrdinates. >> We can't (easily) catch the general problem. This patch allows us to easily >> catch this particular instance of it. > > Sure, but so does adding "assert(this);" at the top of every member Sorry, no. Adding "assert(this);" does not catch any new bugs (at least not on Linux) -- the code would have immediately crashed on zero-page dereference anyway. Thanks,
On 6 September 2011 21:52, Paul Pluzhnikov wrote: > On Tue, Sep 6, 2011 at 1:33 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: > >>> for (it = v->begin(); it != v->end(); ++it) // Oops! >> >> Eurgh, the occurrence of "delete" in anything except a destructor is a >> code smell that should have led someone to find those bugs anyway! >> Obviously the code above is a trivial example, but it's unforgivable >> to write that > > I can assure you that the actual code that exhibited these bugs was much > subtler than that, and the bugs were not immediately obvious. > > Sometimes they were not immediately obvious even after running Valgrind > on the buggy code and getting allocation/deletion/access stack traces with > source corrdinates. > >>> We can't (easily) catch the general problem. This patch allows us to easily >>> catch this particular instance of it. >> >> Sure, but so does adding "assert(this);" at the top of every member > > Sorry, no. Adding "assert(this);" does not catch any new bugs (at least > not on Linux) -- the code would have immediately crashed on zero-page > dereference anyway. I don't mean for vector::begin and the other functions in that patch, I mean in general for member functions of any type. There are plenty of functions that wouldn't crash when called through a null pointer. But even std:vector has member functions like that, such as max_size. Anyway, I think we've concluded the patch is not suitable for general use, as it has limited value without a debugging allocator that makes pages dirty after free.
On Tue, Sep 6, 2011 at 2:51 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: > I don't mean for vector::begin and the other functions in that patch, > I mean in general for member functions of any type. There are plenty > of functions that wouldn't crash when called through a null pointer. > But even std:vector has member functions like that, such as max_size. Right. (We might tweak the compiler to automagically insert that assert in non-omitimized builds ;-) > Anyway, I think we've concluded the patch is not suitable for general > use, as it has limited value without a debugging allocator that makes > pages dirty after free. Agreed. I'll rename __is_valid to _M_is_valid to match the rest of the file, and submit to google/integration only. Thanks for your comments,
On 6 September 2011 22:58, Paul Pluzhnikov wrote: > On Tue, Sep 6, 2011 at 2:51 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: > >> I don't mean for vector::begin and the other functions in that patch, >> I mean in general for member functions of any type. There are plenty >> of functions that wouldn't crash when called through a null pointer. >> But even std:vector has member functions like that, such as max_size. > > Right. (We might tweak the compiler to automagically insert that assert > in non-omitimized builds ;-) Heh :-) Have you considered a compiler option to make 'delete v' zero out the pointer, so that any following use of it gives an immediate segfault? That would be conforming (the value of delete's operand is unspecified after the operation), but would only help if the same pointer is used, rather than another object with the same value. I don't know of any compiler that does that, but have wondered if it would be useful for debugging some cases.
On Tuesday 06 September 2011 23:09:17, Jonathan Wakely wrote: > On 6 September 2011 22:58, Paul Pluzhnikov wrote: > > On Tue, Sep 6, 2011 at 2:51 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote: > > > >> I don't mean for vector::begin and the other functions in that patch, > >> I mean in general for member functions of any type. There are plenty > >> of functions that wouldn't crash when called through a null pointer. > >> But even std:vector has member functions like that, such as max_size. > > > > Right. (We might tweak the compiler to automagically insert that assert > > in non-omitimized builds ;-) > > Heh :-) > > Have you considered a compiler option to make 'delete v' zero out the > pointer, so that any following use of it gives an immediate segfault? > That would be conforming (the value of delete's operand is unspecified > after the operation), but would only help if the same pointer is used, > rather than another object with the same value. I don't know of any > compiler that does that, but have wondered if it would be useful for > debugging some cases. Zeroing out would hide bugs; there's lots of code that does delete ptr; ... ... ... if (ptr) { ptr->... } You'd not see the bug that way. Making 'delete v' clobber the pointer with 0xdeadbeef or ~0 instead would be better.
On Wed, Sep 7, 2011 at 2:34 AM, Pedro Alves <pedro@codesourcery.com> wrote: > Zeroing out would hide bugs; there's lots of code that does > > delete ptr; > ... > if (ptr) > { > ptr->... > } > > You'd not see the bug that way. Making 'delete v' clobber the pointer > with 0xdeadbeef or ~0 instead would be better. Right. In practice, I don't believe I've ever seen this bug in such a "pure" form though. What I often see is ptr = new Foo; DoSomethingInAnotherThread(ptr); ... delete ptr; // Oops. Didn't wait for another thread to finish } Or ptr = new Foo; DoSomethingThatDeletes(ptr); ptr->x++; // Oops. Use after free AFAICT, neither of these would be helped by delete stomping on the pointer.
Index: include/bits/stl_vector.h =================================================================== --- include/bits/stl_vector.h (revision 178493) +++ include/bits/stl_vector.h (working copy) @@ -234,6 +234,16 @@ using _Base::_M_impl; using _Base::_M_get_Tp_allocator; + bool __is_valid() const + { + return (this->_M_impl._M_end_of_storage == 0 + && this->_M_impl._M_start == 0 + && this->_M_impl._M_finish == 0) + || (this->_M_impl._M_start <= this->_M_impl._M_finish + && this->_M_impl._M_finish <= this->_M_impl._M_end_of_storage + && this->_M_impl._M_start < this->_M_impl._M_end_of_storage); + } + public: // [23.2.4.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) @@ -531,7 +541,13 @@ */ iterator begin() _GLIBCXX_NOEXCEPT - { return iterator(this->_M_impl._M_start); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("begin() on corrupt (dangling?) vector"); +#endif + return iterator(this->_M_impl._M_start); + } /** * Returns a read-only (constant) iterator that points to the @@ -540,7 +556,13 @@ */ const_iterator begin() const _GLIBCXX_NOEXCEPT - { return const_iterator(this->_M_impl._M_start); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("begin() on corrupt (dangling?) vector"); +#endif + return const_iterator(this->_M_impl._M_start); + } /** * Returns a read/write iterator that points one past the last @@ -549,7 +571,13 @@ */ iterator end() _GLIBCXX_NOEXCEPT - { return iterator(this->_M_impl._M_finish); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("end() on corrupt (dangling?) vector"); +#endif + return iterator(this->_M_impl._M_finish); + } /** * Returns a read-only (constant) iterator that points one past @@ -558,7 +586,13 @@ */ const_iterator end() const _GLIBCXX_NOEXCEPT - { return const_iterator(this->_M_impl._M_finish); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("end() on corrupt (dangling?) vector"); +#endif + return const_iterator(this->_M_impl._M_finish); + } /** * Returns a read/write reverse iterator that points to the @@ -638,7 +672,13 @@ /** Returns the number of elements in the %vector. */ size_type size() const _GLIBCXX_NOEXCEPT - { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("size() on corrupt (dangling?) vector"); +#endif + return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); + } /** Returns the size() of the largest possible %vector. */ size_type @@ -718,7 +758,12 @@ */ size_type capacity() const _GLIBCXX_NOEXCEPT - { return size_type(this->_M_impl._M_end_of_storage + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("capacity() on corrupt (dangling?) vector"); +#endif + return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); } /** @@ -1112,6 +1157,10 @@ noexcept(_Alloc_traits::_S_nothrow_swap()) #endif { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid() || !__x.__is_valid()) + __throw_logic_error("swap() on corrupt (dangling?) vector"); +#endif this->_M_impl._M_swap_data(__x._M_impl); _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); @@ -1125,7 +1174,13 @@ */ void clear() _GLIBCXX_NOEXCEPT - { _M_erase_at_end(this->_M_impl._M_start); } + { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid()) + __throw_logic_error("clear() on corrupt (dangling?) vector"); +#endif + _M_erase_at_end(this->_M_impl._M_start); + } protected: /** Index: include/bits/vector.tcc =================================================================== --- include/bits/vector.tcc (revision 178493) +++ include/bits/vector.tcc (working copy) @@ -158,6 +158,10 @@ vector<_Tp, _Alloc>:: operator=(const vector<_Tp, _Alloc>& __x) { +#if __google_stl_debug_dangling_vector + if (!this->__is_valid() || !__x.__is_valid()) + __throw_logic_error("operator=() on corrupt (dangling?) vector"); +#endif if (&__x != this) { #ifdef __GXX_EXPERIMENTAL_CXX0X__