[PATCH] PR libstdc++/87784 fix dynamic_bitset::push_back

[Jonathan Wakely]

Previously the _M_Nb member was incremented before calling
_M_unchecked_set which meant that the bit being set was out of bounds.
It either set the wrong bit in an allocated word, or accessed beyond the
end of the allocated memory in the _M_w vector. The fix for the bug is
to update the _M_Nb member after using it as an index.

As an optimisation, when a new block needs to be appended the call to
_M_unchecked_set can be avoided by appending a block with the least
significant bit already set to the desired value.

	PR libstdc++/87784
	* include/tr2/dynamic_bitset (dynamic_bitset::push_back): When there
	are no unused bits in the last block, append a new block with the
	right value so the bit doesn't need to be set. Only increment size
	after setting the new bit, not before.
	* testsuite/tr2/dynamic_bitset/pr87784.cc: New test.

Tested powerpc64le-linux, committed to trunk.

-------------- next part --------------
commit 9c6be7dac22486040e1a724e8f6f83d5c34d0fb4
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Oct 30 12:30:09 2018 +0000

    PR libstdc++/87784 fix dynamic_bitset::push_back
    
    Previously the _M_Nb member was incremented before calling
    _M_unchecked_set which meant that the bit being set was out of bounds.
    It either set the wrong bit in an allocated word, or accessed beyond the
    end of the allocated memory in the _M_w vector. The fix for the bug is
    to update the _M_Nb member after using it as an index.
    
    As an optimisation, when a new block needs to be appended the call to
    _M_unchecked_set can be avoided by appending a block with the least
    significant bit already set to the desired value.
    
            PR libstdc++/87784
            * include/tr2/dynamic_bitset (dynamic_bitset::push_back): When there
            are no unused bits in the last block, append a new block with the
            right value so the bit doesn't need to be set. Only increment size
            after setting the new bit, not before.
            * testsuite/tr2/dynamic_bitset/pr87784.cc: New test.

diff --git a/libstdc++-v3/include/tr2/dynamic_bitset b/libstdc++-v3/include/tr2/dynamic_bitset
index f76c8faf6e3..9e5c8170c81 100644
--- a/libstdc++-v3/include/tr2/dynamic_bitset
+++ b/libstdc++-v3/include/tr2/dynamic_bitset
@@ -727,10 +727,11 @@ namespace tr2
       void
       push_back(bool __bit)
       {
-	if (size_t __offset = this->size() % bits_per_block == 0)
-	  this->_M_do_append_block(block_type(0), this->_M_Nb);
+	if (this->size() % bits_per_block == 0)
+	  this->_M_do_append_block(block_type(__bit), this->_M_Nb);
+	else
+	  this->_M_unchecked_set(this->_M_Nb, __bit);
 	++this->_M_Nb;
-	this->_M_unchecked_set(this->_M_Nb, __bit);
       }
 
       /**
diff --git a/libstdc++-v3/testsuite/tr2/dynamic_bitset/pr87784.cc b/libstdc++-v3/testsuite/tr2/dynamic_bitset/pr87784.cc
new file mode 100644
index 00000000000..52dc3893a31
--- /dev/null
+++ b/libstdc++-v3/testsuite/tr2/dynamic_bitset/pr87784.cc
@@ -0,0 +1,76 @@
+// Copyright (C) 2018 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 3, 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 COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <tr2/dynamic_bitset>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  std::tr2::dynamic_bitset<unsigned> b;
+  VERIFY( b.size() == 0 );
+  VERIFY( b.find_first() == b.size() );
+  b.push_back(0);
+  VERIFY( b.size() == 1 );
+  VERIFY( b.find_first() == b.size() );
+  b.push_back(0);
+  VERIFY( b.size() == 2 );
+  VERIFY( b.find_first() == b.size() );
+
+  b.push_back(1);
+  VERIFY( b.size() == 3 );
+  VERIFY( b.find_first() == b.size() - 1 );
+  b.push_back(1);
+  VERIFY( b.size() == 4 );
+  VERIFY( b.find_first() == b.size() - 2 );
+  b.push_back(0);
+  VERIFY( b.size() == 5 );
+  VERIFY( b.find_first() == b.size() - 3 );
+
+  b.clear();
+  VERIFY( b.size() == 0 );
+  VERIFY( b.find_first() == b.size() );
+  b.push_back(1);
+  VERIFY( b.size() == 1 );
+  VERIFY( b.find_first() == 0 );
+  b.push_back(1);
+  VERIFY( b.size() == 2 );
+  VERIFY( b.find_first() == 0 );
+  b.push_back(1);
+  VERIFY( b.size() == 3 );
+  VERIFY( b.find_first() == 0 );
+
+  b.clear();
+  b.append(2u);
+  VERIFY( b.size() == b.bits_per_block );
+  VERIFY( b.find_first() == 1 );
+  b <<= 1;
+  VERIFY( b.find_first() == 2 );
+  b <<= 3;
+  VERIFY( b.find_first() == 5 );
+  b <<= 6;
+  VERIFY( b.find_first() == 11 );
+  VERIFY( b.size() == b.bits_per_block );
+}
+
+int
+main()
+{
+  test01();
+}