Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-07 Thread Pedro Alves
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@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.

-- 
Pedro Alves


[patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
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  ppluzhni...@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.



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 

Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
On Tue, Sep 6, 2011 at 9:28 AM, Paul Pluzhnikov ppluzhni...@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.

-- 
Paul Pluzhnikov


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Diego Novillo
On Tue, Sep 6, 2011 at 12:28, Paul Pluzhnikov ppluzhni...@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  ppluzhni...@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.


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Diego Novillo
On Tue, Sep 6, 2011 at 12:54, Paul Pluzhnikov ppluzhni...@google.com wrote:
 On Tue, Sep 6, 2011 at 9:44 AM, Diego Novillo dnovi...@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



Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
On Tue, Sep 6, 2011 at 10:46 AM, Diego Novillo dnovi...@google.com wrote:
 On Tue, Sep 6, 2011 at 12:54, Paul Pluzhnikov ppluzhni...@google.com wrote:
 On Tue, Sep 6, 2011 at 9:44 AM, Diego Novillo dnovi...@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,
-- 
Paul Pluzhnikov


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Jonathan Wakely
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.


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Jonathan Wakely
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.


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
On Tue, Sep 6, 2011 at 12:44 PM, Jonathan Wakely jwakely@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,
-- 
Paul Pluzhnikov


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Christopher Jefferson

On 6 Sep 2011, at 21:19, Paul Pluzhnikov wrote:

 On Tue, Sep 6, 2011 at 12:44 PM, Jonathan Wakely jwakely@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


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
On Tue, Sep 6, 2011 at 1:33 PM, Jonathan Wakely jwakely@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,
-- 
Paul Pluzhnikov


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Jonathan Wakely
On 6 September 2011 21:52, Paul Pluzhnikov wrote:
 On Tue, Sep 6, 2011 at 1:33 PM, Jonathan Wakely jwakely@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.


Re: [patch][google/integration] Add lightweight checks to vector::begin et. al. (issue4973065)

2011-09-06 Thread Paul Pluzhnikov
On Tue, Sep 6, 2011 at 2:51 PM, Jonathan Wakely jwakely@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,
-- 
Paul Pluzhnikov