[PATCH] Fix incorrect assertion when deallocating big block

[PATCH] Fix incorrect assertion when deallocating big block

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 954 bytes --]

Since a big_block rounds up the size to a multiple of big_block::min it
is wrong to assert that the supplied number of bytes equals the
big_block's size(). Add big_block::alloc_size(size_t) to calculate the
allocated size consistently, and add comments to the code.

	* src/c++17/memory_resource.cc (big_block): Improve comments.
	(big_block::all_ones): Remove.
	(big_block::big_block(size_t, size_t)): Use alloc_size.
	(big_block::size()): Add comment, replace all_ones with equivalent
	expression.
	(big_block::align()): Shift value of correct type.
	(big_block::alloc_size(size_t)): New function to round up size.
	(__pool_resource::allocate(size_t, size_t)): Add comment.
	(__pool_resource::deallocate(void*, size_t, size_t)): Likewise. Fix
	incorrect assertion by using big_block::alloc_size(size_t).
	* testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Add
	more tests for unpooled allocations.

Tested x86_64-linux, committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 8451 bytes --]

commit 8f54af8a6ab6dae9f9736afd9790691a57d57428
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 13 21:01:57 2018 +0000

    Fix incorrect assertion when deallocating big block
    
    Since a big_block rounds up the size to a multiple of big_block::min it
    is wrong to assert that the supplied number of bytes equals the
    big_block's size(). Add big_block::alloc_size(size_t) to calculate the
    allocated size consistently, and add comments to the code.
    
            * src/c++17/memory_resource.cc (big_block): Improve comments.
            (big_block::all_ones): Remove.
            (big_block::big_block(size_t, size_t)): Use alloc_size.
            (big_block::size()): Add comment, replace all_ones with equivalent
            expression.
            (big_block::align()): Shift value of correct type.
            (big_block::alloc_size(size_t)): New function to round up size.
            (__pool_resource::allocate(size_t, size_t)): Add comment.
            (__pool_resource::deallocate(void*, size_t, size_t)): Likewise. Fix
            incorrect assertion by using big_block::alloc_size(size_t).
            * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Add
            more tests for unpooled allocations.

diff --git a/libstdc++-v3/src/c++17/memory_resource.cc b/libstdc++-v3/src/c++17/memory_resource.cc
index fdbbc914f2e..719cb9f1d29 100644
--- a/libstdc++-v3/src/c++17/memory_resource.cc
+++ b/libstdc++-v3/src/c++17/memory_resource.cc
@@ -537,22 +537,22 @@ namespace pmr
   // An oversized allocation that doesn't fit in a pool.
   struct big_block
   {
+    // Alignment must be a power-of-two so we only need to use enough bits
+    // to store the power, not the actual value:
     static constexpr unsigned _S_alignbits
-      = std::__log2p1((unsigned)numeric_limits<size_t>::digits) - 1;
+      = std::__log2p1((unsigned)numeric_limits<size_t>::digits - 1);
+    // Use the remaining bits to store the size:
     static constexpr unsigned _S_sizebits
       = numeric_limits<size_t>::digits - _S_alignbits;
     // The maximum value that can be stored in _S_size
-    static constexpr size_t all_ones = (1ull << _S_sizebits) - 1u;
-    // The minimum size of a big block
+    static constexpr size_t all_ones = size_t(-1) >> _S_alignbits;
+    // The minimum size of a big block (smaller sizes will be rounded up).
     static constexpr size_t min = 1u << _S_alignbits;
 
     big_block(size_t bytes, size_t alignment)
-    : _M_size((bytes + min - 1u) >> _S_alignbits),
+    : _M_size(alloc_size(bytes) >> _S_alignbits),
       _M_align_exp(std::__log2p1(alignment) - 1u)
-    {
-      if (__builtin_expect(std::__countl_one(bytes) == _S_sizebits, false))
-	_M_size = all_ones;
-    }
+    { }
 
     void* pointer = nullptr;
     size_t _M_size : numeric_limits<size_t>::digits - _S_alignbits;
@@ -560,13 +560,26 @@ namespace pmr
 
     size_t size() const noexcept
     {
-      if (__builtin_expect(_M_size == all_ones, false))
+      // If all bits are set in _M_size it means the maximum possible size:
+      if (__builtin_expect(_M_size == (size_t(-1) >> _S_alignbits), false))
 	return (size_t)-1;
       else
 	return _M_size << _S_alignbits;
     }
 
-    size_t align() const noexcept { return 1ul << _M_align_exp; }
+    size_t align() const noexcept { return size_t(1) << _M_align_exp; }
+
+    // Calculate size to be allocated instead of requested number of bytes.
+    // The requested value will be rounded up to a multiple of big_block::min,
+    // so the low _S_alignbits bits are all zero and don't need to be stored.
+    static constexpr size_t alloc_size(size_t bytes) noexcept
+    {
+      const size_t s = bytes + min - 1u;
+      if (__builtin_expect(s < bytes, false))
+	return size_t(-1); // addition wrapped past zero, return max value
+      else
+	return s & ~(min - 1u);
+    }
 
     friend bool operator<(void* p, const big_block& b) noexcept
     { return less<void*>{}(p, b.pointer); }
@@ -915,6 +928,7 @@ namespace pmr
   {
     auto& b = _M_unpooled.emplace_back(bytes, alignment);
     __try {
+      // N.B. need to allocate b.size(), which might be larger than bytes.
       void* p = resource()->allocate(b.size(), alignment);
       b.pointer = p;
       if (_M_unpooled.size() > 1)
@@ -932,8 +946,7 @@ namespace pmr
   }
 
   void
-  __pool_resource::deallocate(void* p, size_t bytes [[maybe_unused]],
-			      size_t alignment [[maybe_unused]])
+  __pool_resource::deallocate(void* p, size_t bytes, size_t alignment)
   {
     const auto it
       = std::lower_bound(_M_unpooled.begin(), _M_unpooled.end(), p);
@@ -941,9 +954,10 @@ namespace pmr
     if (it != _M_unpooled.end() && it->pointer == p) // [[likely]]
       {
 	const auto b = *it;
-	__glibcxx_assert(b.size() == bytes);
+	__glibcxx_assert(b.size() == b.alloc_size(bytes));
 	__glibcxx_assert(b.align() == alignment);
 	_M_unpooled.erase(it);
+	// N.B. need to deallocate b.size(), which might be larger than bytes.
 	resource()->deallocate(p, b.size(), b.align());
       }
   }
diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
index ce9be2f6c49..749655b63c7 100644
--- a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
+++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
@@ -128,7 +128,8 @@ test03()
 void
 test04()
 {
-  std::pmr::unsynchronized_pool_resource r({256, 256});
+  __gnu_test::memory_resource test_mr;
+  std::pmr::unsynchronized_pool_resource r({256, 256}, &test_mr);
   // Check alignment
   void* p1 = r.allocate(2, 64);
   VERIFY( (std::uintptr_t)p1 % 64 == 0 );
@@ -145,6 +146,95 @@ test04()
   r.deallocate(p4, 2 * largest_pool, 1024);
 }
 
+void
+test05()
+{
+  __gnu_test::memory_resource test_mr;
+  std::pmr::pool_options opts{};
+  opts.max_blocks_per_chunk = 1;
+  opts.largest_required_pool_block = 1;
+  std::pmr::unsynchronized_pool_resource r(opts, &test_mr);
+  opts = r.options();
+  // Test unpooled allocations
+  void** p = new void*[opts.largest_required_pool_block];
+  for (unsigned a : {64, 128, 256, 512})
+  {
+    for (unsigned i = 0; i < opts.largest_required_pool_block; ++i)
+      p[i] = r.allocate(i, a);
+    for (unsigned i = 0; i < opts.largest_required_pool_block; ++i)
+      r.deallocate(p[i], i, a);
+  }
+  delete[] p;
+}
+
+void
+test06()
+{
+  struct custom_mr : std::pmr::memory_resource
+  {
+    size_t expected_size = 0;
+    size_t expected_alignment = 0;
+
+    struct bad_size { };
+    struct bad_alignment { };
+
+    void* do_allocate(std::size_t b, std::size_t a)
+    {
+      if (expected_size != 0)
+      {
+	if (b < expected_size)
+	  throw bad_size();
+	else if (a != expected_alignment)
+	  throw bad_alignment();
+	// Else just throw, don't try to allocate:
+	throw std::bad_alloc();
+      }
+
+      return std::pmr::new_delete_resource()->allocate(b, a);
+    }
+
+    void do_deallocate(void* p, std::size_t b, std::size_t a)
+    { std::pmr::new_delete_resource()->deallocate(p, b, a); }
+
+    bool do_is_equal(const memory_resource& r) const noexcept
+    { return false; }
+  };
+
+  custom_mr c;
+  std::pmr::unsynchronized_pool_resource r({1, 1}, &c);
+  std::pmr::pool_options opts = r.options();
+  const std::size_t largest_pool = opts.largest_required_pool_block;
+  const std::size_t large_alignment = 1024;
+  // Ensure allocations won't fit in pools:
+  VERIFY( largest_pool < large_alignment );
+
+  // Ensure the vector of large allocations has some capacity
+  // and won't need to reallocate:
+  r.deallocate(r.allocate(largest_pool + 1, 1), largest_pool + 1, 1);
+
+  // Try allocating various very large sizes and ensure the size requested
+  // from the upstream allocator is at least as large as needed.
+  for (int i = 1; i < 64; ++i)
+  {
+    for (auto b : { -1, 0, 1, 3 })
+    {
+      std::size_t bytes = std::size_t(1) << i;
+      bytes += b;
+      c.expected_size = bytes;
+      c.expected_alignment = large_alignment;
+      try {
+	(void) r.allocate(bytes, large_alignment);
+      } catch (const std::bad_alloc&) {
+	// expect to catch bad_alloc
+      } catch (custom_mr::bad_size) {
+	VERIFY(false);
+      } catch (custom_mr::bad_alignment) {
+	VERIFY(false);
+      }
+    }
+  }
+}
+
 int
 main()
 {
@@ -152,4 +242,6 @@ main()
   test02();
   test03();
   test04();
+  test05();
+  test06();
 }

Re: [PATCH] Fix incorrect assertion when deallocating big block

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 431 bytes --]

>@@ -932,8 +946,7 @@ namespace pmr
>   }
>
>   void
>-  __pool_resource::deallocate(void* p, size_t bytes [[maybe_unused]],
>-			      size_t alignment [[maybe_unused]])
>+  __pool_resource::deallocate(void* p, size_t bytes, size_t alignment)
>   {
>     const auto it
>       = std::lower_bound(_M_unpooled.begin(), _M_unpooled.end(), p);

This part of the change wasn't meant to be committed. Restored with
the attached patch.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 908 bytes --]

commit 90d835c3a0e3fd73b9287ad3b636e13319f38973
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 13 23:01:44 2018 +0000

    Fix unused parameter warnings introduced in earlier patch
    
            * src/c++17/memory_resource.cc (_Pool::deallocate): Restore
            attributes to parameters that are only used in assertions.

diff --git a/libstdc++-v3/src/c++17/memory_resource.cc b/libstdc++-v3/src/c++17/memory_resource.cc
index b553606f552..cb91e5147ce 100644
--- a/libstdc++-v3/src/c++17/memory_resource.cc
+++ b/libstdc++-v3/src/c++17/memory_resource.cc
@@ -940,7 +940,8 @@ namespace pmr
   }
 
   void
-  __pool_resource::deallocate(void* p, size_t bytes, size_t alignment)
+  __pool_resource::deallocate(void* p, size_t bytes [[maybe_unused]],
+			      size_t alignment [[maybe_unused]])
   {
     const auto it
       = std::lower_bound(_M_unpooled.begin(), _M_unpooled.end(), p);

Re: [PATCH] Fix incorrect assertion when deallocating big block

[Christophe Lyon]

On Tue, 13 Nov 2018 at 23:58, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> Since a big_block rounds up the size to a multiple of big_block::min it
> is wrong to assert that the supplied number of bytes equals the
> big_block's size(). Add big_block::alloc_size(size_t) to calculate the
> allocated size consistently, and add comments to the code.
>
>         * src/c++17/memory_resource.cc (big_block): Improve comments.
>         (big_block::all_ones): Remove.
>         (big_block::big_block(size_t, size_t)): Use alloc_size.
>         (big_block::size()): Add comment, replace all_ones with equivalent
>         expression.
>         (big_block::align()): Shift value of correct type.
>         (big_block::alloc_size(size_t)): New function to round up size.
>         (__pool_resource::allocate(size_t, size_t)): Add comment.
>         (__pool_resource::deallocate(void*, size_t, size_t)): Likewise. Fix
>         incorrect assertion by using big_block::alloc_size(size_t).
>         * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Add
>         more tests for unpooled allocations.
>

Hi Jonathan,

I've noticed that the updated test fails on arm*:
FAIL: 20_util/unsynchronized_pool_resource/allocate.cc execution test

the log says:
/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc:232:
void test06(): Assertion 'false' failed.

The same happens on aarch64-elf with -mabi=ilp32

Christophe

> Tested x86_64-linux, committed to trunk.
>

Re: [PATCH] Fix incorrect assertion when deallocating big block

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1558 bytes --]

On 14/11/18 10:31 +0100, Christophe Lyon wrote:
>On Tue, 13 Nov 2018 at 23:58, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> Since a big_block rounds up the size to a multiple of big_block::min it
>> is wrong to assert that the supplied number of bytes equals the
>> big_block's size(). Add big_block::alloc_size(size_t) to calculate the
>> allocated size consistently, and add comments to the code.
>>
>>         * src/c++17/memory_resource.cc (big_block): Improve comments.
>>         (big_block::all_ones): Remove.
>>         (big_block::big_block(size_t, size_t)): Use alloc_size.
>>         (big_block::size()): Add comment, replace all_ones with equivalent
>>         expression.
>>         (big_block::align()): Shift value of correct type.
>>         (big_block::alloc_size(size_t)): New function to round up size.
>>         (__pool_resource::allocate(size_t, size_t)): Add comment.
>>         (__pool_resource::deallocate(void*, size_t, size_t)): Likewise. Fix
>>         incorrect assertion by using big_block::alloc_size(size_t).
>>         * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Add
>>         more tests for unpooled allocations.
>>
>
>Hi Jonathan,
>
>I've noticed that the updated test fails on arm*:
>FAIL: 20_util/unsynchronized_pool_resource/allocate.cc execution test
>
>the log says:
>/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc:232:
>void test06(): Assertion 'false' failed.
>
>The same happens on aarch64-elf with -mabi=ilp32

Should be fixed by this patch, committed to trunk.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 3764 bytes --]

commit b9aea25cc625b0ee3322d8185c2fc9354a800ebb
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Nov 14 20:23:58 2018 +0000

    Fix test that does undefined shifts greater than width of size_t
    
            * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Fix
            test for 32-bit targets. Test additional allocation sizes.

diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
index 749655b63c7..0325a4358b6 100644
--- a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
+++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc
@@ -170,7 +170,7 @@ test05()
 void
 test06()
 {
-  struct custom_mr : std::pmr::memory_resource
+  struct checking_mr : std::pmr::memory_resource
   {
     size_t expected_size = 0;
     size_t expected_alignment = 0;
@@ -178,29 +178,30 @@ test06()
     struct bad_size { };
     struct bad_alignment { };
 
-    void* do_allocate(std::size_t b, std::size_t a)
+    void* do_allocate(std::size_t bytes, std::size_t align)
     {
-      if (expected_size != 0)
-      {
-	if (b < expected_size)
-	  throw bad_size();
-	else if (a != expected_alignment)
-	  throw bad_alignment();
-	// Else just throw, don't try to allocate:
-	throw std::bad_alloc();
-      }
+      // Internal data structures in unsynchronized_pool_resource need to
+      // allocate memory, so handle those normally:
+      if (align <= alignof(std::max_align_t))
+	return std::pmr::new_delete_resource()->allocate(bytes, align);
 
-      return std::pmr::new_delete_resource()->allocate(b, a);
+      // This is a large, unpooled allocation. Check the arguments:
+      if (bytes < expected_size)
+	throw bad_size();
+      else if (align != expected_alignment)
+	throw bad_alignment();
+      // Else just throw, don't really try to allocate:
+      throw std::bad_alloc();
     }
 
-    void do_deallocate(void* p, std::size_t b, std::size_t a)
-    { std::pmr::new_delete_resource()->deallocate(p, b, a); }
+    void do_deallocate(void* p, std::size_t bytes, std::size_t align)
+    { std::pmr::new_delete_resource()->deallocate(p, bytes, align); }
 
     bool do_is_equal(const memory_resource& r) const noexcept
     { return false; }
   };
 
-  custom_mr c;
+  checking_mr c;
   std::pmr::unsynchronized_pool_resource r({1, 1}, &c);
   std::pmr::pool_options opts = r.options();
   const std::size_t largest_pool = opts.largest_required_pool_block;
@@ -214,23 +215,26 @@ test06()
 
   // Try allocating various very large sizes and ensure the size requested
   // from the upstream allocator is at least as large as needed.
-  for (int i = 1; i < 64; ++i)
+  for (int i = 0; i < std::numeric_limits<std::size_t>::digits; ++i)
   {
-    for (auto b : { -1, 0, 1, 3 })
+    for (auto b : { -63, -5, -1, 0, 1, 3, std::numeric_limits<int>::max() })
     {
       std::size_t bytes = std::size_t(1) << i;
-      bytes += b;
+      bytes += b; // For negative b this can wrap to a large positive value.
       c.expected_size = bytes;
       c.expected_alignment = large_alignment;
+      bool caught_bad_alloc = false;
       try {
 	(void) r.allocate(bytes, large_alignment);
       } catch (const std::bad_alloc&) {
 	// expect to catch bad_alloc
-      } catch (custom_mr::bad_size) {
-	VERIFY(false);
-      } catch (custom_mr::bad_alignment) {
-	VERIFY(false);
+	caught_bad_alloc = true;
+      } catch (checking_mr::bad_size) {
+	VERIFY( ! "allocation from upstream resource had expected size" );
+      } catch (checking_mr::bad_alignment) {
+	VERIFY( ! "allocation from upstream resource had expected alignment" );
       }
+      VERIFY( caught_bad_alloc );
     }
   }
 }

Re: [PATCH] Fix incorrect assertion when deallocating big block

[Jonathan Wakely]

On 14/11/18 20:26 +0000, Jonathan Wakely wrote:
>On 14/11/18 10:31 +0100, Christophe Lyon wrote:
>>On Tue, 13 Nov 2018 at 23:58, Jonathan Wakely <jwakely@redhat.com> wrote:
>>>
>>>Since a big_block rounds up the size to a multiple of big_block::min it
>>>is wrong to assert that the supplied number of bytes equals the
>>>big_block's size(). Add big_block::alloc_size(size_t) to calculate the
>>>allocated size consistently, and add comments to the code.
>>>
>>>        * src/c++17/memory_resource.cc (big_block): Improve comments.
>>>        (big_block::all_ones): Remove.
>>>        (big_block::big_block(size_t, size_t)): Use alloc_size.
>>>        (big_block::size()): Add comment, replace all_ones with equivalent
>>>        expression.
>>>        (big_block::align()): Shift value of correct type.
>>>        (big_block::alloc_size(size_t)): New function to round up size.
>>>        (__pool_resource::allocate(size_t, size_t)): Add comment.
>>>        (__pool_resource::deallocate(void*, size_t, size_t)): Likewise. Fix
>>>        incorrect assertion by using big_block::alloc_size(size_t).
>>>        * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: Add
>>>        more tests for unpooled allocations.
>>>
>>
>>Hi Jonathan,
>>
>>I've noticed that the updated test fails on arm*:
>>FAIL: 20_util/unsynchronized_pool_resource/allocate.cc execution test
>>
>>the log says:
>>/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc:232:
>>void test06(): Assertion 'false' failed.
>>
>>The same happens on aarch64-elf with -mabi=ilp32
>
>Should be fixed by this patch, committed to trunk.

I forgot to actually commit this. *Now* it's committed to trunk
(r266163).