[Patch] Fix __len overflows (take 2)

[Paolo Carlini <pcarlini at suse dot de>]

Hi,

the below tries to incorporate to my best Nathan's comments: first,
we check that max_size() will not be exceeded, then, in case __len
overflows, we allocate exactly max_size(). The underlying logic is
that max_size() is the real point of reference wrt the max possible
size of a vector and is supposed to reflect what the system can
really achieve.

I'm finishing testing on x86 and x86_64 and would like to commit
the patch tomorrow if it's fine with everyone...

Paolo.

//////////
2004-10-20  Paolo Carlini  <pcarlini@suse.de>
	    Dhruv Matani  <dhruvbird@gmx.net>
	    Nathan Myers  <ncm@cantrip.org>

	* include/bits/vector.tcc (_M_insert_aux, _M_fill_insert,
	_M_range_insert): Check at the outset that we are not trying
	to exceed max_size, then deal properly with __len overflows.
	* testsuite/23_containers/vector/modifiers/insert/1.cc: New.

diff -urN libstdc++-v3-orig/include/bits/vector.tcc libstdc++-v3/include/bits/vector.tcc
--- libstdc++-v3-orig/include/bits/vector.tcc	2004-07-28 18:37:17.000000000 +0200
+++ libstdc++-v3/include/bits/vector.tcc	2004-10-19 21:57:59.000000000 +0200
@@ -262,7 +262,16 @@
       else
 	{
 	  const size_type __old_size = size();
-	  const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
+	  if (__old_size == this->max_size())
+	    __throw_length_error(__N("vector::_M_insert_aux"));
+
+	  // When sizeof(value_type) == 1 and __old_size > size_type(-1)/2
+	  // __len overflows: if we don't notice and _M_allocate doesn't
+	  // throw we crash badly later.
+	  size_type __len = __old_size != 0 ? 2 * __old_size : 1;	  
+	  if (__len < __old_size)
+	    __len = this->max_size();
+
 	  iterator __new_start(this->_M_allocate(__len));
 	  iterator __new_finish(__new_start);
 	  try
@@ -279,7 +288,7 @@
 					    iterator(this->_M_impl._M_finish),
 					    __new_finish,
 					    this->get_allocator());
-          }
+	    }
 	  catch(...)
 	    {
 	      std::_Destroy(__new_start, __new_finish, this->get_allocator());
@@ -337,7 +346,16 @@
 	  else
 	    {
 	      const size_type __old_size = size();
-	      const size_type __len = __old_size + std::max(__old_size, __n);
+	      if (this->max_size() - __old_size < __n)
+		__throw_length_error(__N("vector::_M_fill_insert"));
+	      
+	      // See _M_insert_aux above (+ in this case, __len can overflow
+	      // in many other situations, not just for sizeof(value_type) == 1
+	      // and __old_size > size_type(-1)/2).
+	      size_type __len = __old_size + std::max(__old_size, __n);
+	      if (__len < __old_size)
+		__len = this->max_size();
+
 	      iterator __new_start(this->_M_allocate(__len));
 	      iterator __new_finish(__new_start);
 	      try
@@ -389,7 +407,7 @@
     template<typename _ForwardIterator>
       void
       vector<_Tp, _Alloc>::
-      _M_range_insert(iterator __position,_ForwardIterator __first,
+      _M_range_insert(iterator __position, _ForwardIterator __first,
 		      _ForwardIterator __last, forward_iterator_tag)
       {
 	if (__first != __last)
@@ -429,7 +447,14 @@
 	    else
 	      {
 		const size_type __old_size = size();
-		const size_type __len = __old_size + std::max(__old_size, __n);
+		if (this->max_size() - __old_size < __n)
+		  __throw_length_error(__N("vector::_M_range_insert"));	
+
+		// See _M_fill_insert above.
+		size_type __len = __old_size + std::max(__old_size, __n);
+		if (__len < __old_size)
+		  __len = this->max_size();
+
 		iterator __new_start(this->_M_allocate(__len));
 		iterator __new_finish(__new_start);
 		try
diff -urN libstdc++-v3-orig/testsuite/23_containers/vector/modifiers/insert/1.cc libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/1.cc
--- libstdc++-v3-orig/testsuite/23_containers/vector/modifiers/insert/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/1.cc	2004-10-19 22:44:42.000000000 +0200
@@ -0,0 +1,58 @@
+// Copyright (C) 2004 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <vector>
+#include <stdexcept>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  using namespace std;
+
+  vector<int> iv;
+
+  try
+    {
+      iv.insert(iv.end(), iv.max_size() + 1, 1);
+    }
+  catch(std::length_error&)
+    {
+      VERIFY( true );
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}