[gcc(refs/vendors/ARM/heads/morello)] Update libstdc++ `pool_allocator` for capabilities

[gcc(refs/vendors/ARM/heads/morello)] Update libstdc++ `pool_allocator` for capabilities

[Matthew Malcomson]

https://gcc.gnu.org/g:8db59b80459ed21d889f07d548511e9a9ea6fee7

commit 8db59b80459ed21d889f07d548511e9a9ea6fee7
Author: Matthew Malcomson <matthew.malcomson@arm.com>
Date:   Wed Oct 19 11:52:39 2022 +0100

    Update libstdc++ `pool_allocator` for capabilities
    
    The existing pool_allocator implementation does not work with
    capabilities.  The problem we see is a SIGBUS on an attempt to store a
    capability to an unaligned location.
    
    This problem was due to the mechanism by which a free list is maintained
    in this allocator.  We store a pointer to the "head" of a linked list
    of free allocations in an array indexed by size of allocation.  During
    allocation the existing implementation ensured that the alignment of
    each chunk given out was at least 8 bytes (and that the size of each
    chunk given out was at least 8 bytes).  This meant that the alignment
    and size of each chunk was large enough for a pointer.
    
    With the larger sizes and higher alignment requirements of pointers on
    capability architectures this was no longer enough.  Here we change
    `_S_align` (which is used to both maintain alignment and round up
    allocations) to `__SIZEOF_POINTER__` when that macro exists.  This both
    provides the necessary alignment and size for the larger capabilities.
    
    There is a maximum size of 128 bytes beyond which this allocator falls
    back to `new` and `delete`.  This size is smaller than the size at which
    padding and extra alignment become necessary to ensure that CHERI bounds
    compression do not allow access beyond the current object that we're
    allocating.  Hence in updating this allocator we do not need to concern
    ourselves with such padding and extra alignment.
    
    ----
    In order to bound the pointers returned by this allocator we can simply
    add a call to a builtin function applying the necessary bounds at the
    end of the `allocate` member function.
    This works well apart from one complication due to the free list
    mechanism described above.  During deallocation the original pointer is
    given back to the allocator, and the allocator uses this pointer to
    store a link to the "next" free chunk while updating the "head" of its
    free list for this size to be the given pointer.  If the bounds on this
    pointer are not large enough to span the size of a capability, then we
    can not store a capability in this position (even if the space we had
    carved out for this chunk was padded up to the size of a capability).
    A similar problem arises once an allocation has been provided, reclaimed
    onto a free list, and is then given out again.  Given that allocations
    are made and categorized based on multiples of `_S_align`, if we bound
    the size of an allocation to the number of bytes it needs then it may
    not span the entire allocation hunk that was given out.  Hence after
    this allocation has been reclaimed onto the free list it may be given
    out to another consumer which needs the entirety of the allocation yet
    is not given a pointer with wide enough bounds.
    
    In order to apply the most restrictive bounds possible on the pointers
    given out, we would need to maintain another data structure containing
    wider-bounds capabilities from which to extend the necessary bounds of
    the pointers given to `deallocate`.
    
    Rather than add such extra complexity, here we choose to give out
    pointers with bounds that are always rounded up with `_M_round_up` to
    the same size that we associate allocations in our free list.  This does
    mean that programming errors which read slightly past the end
    allocations are not caught, but it still restricts the permissions given
    to the returned pointer enough so that it can not access any
    neighbouring object.  This is considered a reasonable security tradeoff.
    
    ----
    One extra feature that was considered was that due to the aforementioned
    mechanism by which the free list is maintained, each allocation would
    usually be returned containing a capability that can access the next
    free allocation.
    This indirectly provides more permissions than are necessary to the user
    of this API.  Those extra permissions could theoretically be used to put
    some other memory region on the free list (triggering the allocator to
    write to some memory that it should not).  The only memory a user could
    cause to be accessed would be memory that user already had access to
    (since they would need a valid capability), and it seems relatively
    unlikely to accidentally affect the free list when compared to the
    likelihood of accidentally writing past the end of an allocation.
    Nevertheless it seems reasonable to clear this capability on allocation,
    and we perform that by a simple write to clear the free list link when
    returning a pointer from the free list.
    
    ----
    Of note is that there is nothing in pool_allocator that handles increasing
    the alignment of a pool from the original pointer provided by
    `::operator new` in `_M_allocate_chunk`.  This means that increasing the
    `_S_align` member beyond 16 bytes (which is the allocation alignment of
    `malloc`) would not continue to increase the alignment of the pointers this
    allocator gives out.  Luckily that doesn't matter for us, but it's worth noting
    that we do rely on the alignment of pointers that come back from `::operator
    new`.

Diff:
---
 .../morello/restrictions/morello-restrictions.exp  | 11 +--
 gcc/testsuite/lib/target-supports-dg.exp           | 11 +++
 libstdc++-v3/include/ext/pool_allocator.h          | 35 +++++++-
 .../ext/pool_allocator/check_read_end_of_bounds.cc | 30 +++++++
 .../ext/pool_allocator/check_read_out_of_bounds.cc | 36 ++++++++
 .../pool_allocator/check_reallocate_and_read.cc    | 35 ++++++++
 .../testsuite/lib/dg-enable-shouldfail.exp         | 35 ++++++++
 libstdc++-v3/testsuite/lib/libstdc++.exp           |  3 +
 .../testsuite/libstdc++-dg/conformance.exp         |  1 +
 .../testsuite/util/replacement_memory_operators.h  | 96 +++++++++++++++++++++-
 10 files changed, 280 insertions(+), 13 deletions(-)

diff --git a/gcc/testsuite/gcc.target/aarch64/morello/restrictions/morello-restrictions.exp b/gcc/testsuite/gcc.target/aarch64/morello/restrictions/morello-restrictions.exp
index bb5ebb2cc3f..d069327dc0d 100644
--- a/gcc/testsuite/gcc.target/aarch64/morello/restrictions/morello-restrictions.exp
+++ b/gcc/testsuite/gcc.target/aarch64/morello/restrictions/morello-restrictions.exp
@@ -25,22 +25,15 @@ if {![istarget aarch64*-*-*] } then {
 # Load support procs.
 load_lib gcc-dg.exp
 load_lib c-torture.exp
+load_lib target-supports-dg.exp
 
 # Initialize `dg'.
 dg-init
 
-# We define a different proc to be used by the testcases so we can use
-# `dg-shouldfail` without relying on looking for specific flags.  Sometimes we
-# compile purecap by default, sometimes we don't, hence can't use flags.
 if { [check_effective_target_cheri_capability_pure] } {
   set capability_flags ""
-  proc dg-shouldfail-purecap { args } {
-    upvar dg-do-what dg-do-what
-    dg-shouldfail "morello bounds"
-  }
 } else {
   set capability_flags "-mfake-capability"
-  proc dg-shouldfail-purecap { args } { }
 }
 
 torture-init
@@ -51,8 +44,6 @@ set-torture-options "$C_TORTURE_OPTIONS"
 gcc-dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/*.\[cCS\]]] \
     "" "$capability_flags"
 
-# Delete the proc now we don't need it.
-rename dg-shouldfail-purecap ""
 torture-finish
 # All done.
 dg-finish
diff --git a/gcc/testsuite/lib/target-supports-dg.exp b/gcc/testsuite/lib/target-supports-dg.exp
index 4a03eaae9ce..d3c14a0eda9 100644
--- a/gcc/testsuite/lib/target-supports-dg.exp
+++ b/gcc/testsuite/lib/target-supports-dg.exp
@@ -675,3 +675,14 @@ proc dg-require-symver { args } {
 	set dg-do-what [list [lindex ${dg-do-what} 0] "N" "P"]
     }
 }
+
+# If this target is a purecap capability target, then it should fail.
+# We define a different proc to be used by the testcases so we can use
+# `dg-shouldfail` without relying on looking for specific flags.  Sometimes we
+# compile purecap by default, sometimes we don't, hence can't use flags.
+proc dg-shouldfail-purecap { args } {
+    if { [check_effective_target_cheri_capability_pure] } {
+	upvar dg-do-what dg-do-what
+        eval dg-shouldfail $args
+    }
+}
diff --git a/libstdc++-v3/include/ext/pool_allocator.h b/libstdc++-v3/include/ext/pool_allocator.h
index c247c403bec..bca82f7ac44 100644
--- a/libstdc++-v3/include/ext/pool_allocator.h
+++ b/libstdc++-v3/include/ext/pool_allocator.h
@@ -1,6 +1,6 @@
 // Allocators -*- C++ -*-
 
-// Copyright (C) 2001-2020 Free Software Foundation, Inc.
+// Copyright (C) 2001-2022 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
@@ -77,7 +77,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef std::size_t size_t;
     protected:
 
-      enum { _S_align = 8 };
+      // We round up allocations to this size.
+      // The allocation needs to be large enough to fit a pointer since
+      // internally we store pointers in the unused allocations.
+      enum { _S_align = sizeof (void*) > 8 ? sizeof (void*) : 8 };
       enum { _S_max_bytes = 128 };
       enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
       
@@ -255,9 +258,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		{
 		  *__free_list = __result->_M_free_list_link;
 		  __ret = reinterpret_cast<_Tp*>(__result);
+#ifdef __CHERI_PURE_CAPABILITY__
+		  // Since CHERI is about restricting unnecessary permissions,
+		  // it seems reasonable to clear the internal free list link
+		  // before returning.
+		  __result->_M_free_list_link = 0;
+#endif
 		}
 	      if (__ret == 0)
 		std::__throw_bad_alloc();
+#ifdef __CHERI_PURE_CAPABILITY__
+	      // It is unfortunate that we require the bounds of the pointer we
+	      // return to be large enough to access the entire chunk even if
+	      // the allocation that the user asked for is less than that size.
+	      // This is required due to the fact that we do not increase the
+	      // bounds of allocations when reclaiming them in deallocate.
+	      // They simply go back onto the free list to be returned to a
+	      // later allocation.  This later allocation may need the entire
+	      // chunk allocated, and hence the pointer we bound here -- which
+	      // would be given as-is to such a hypothetical later allocation
+	      // -- must have the widest bounds an allocation which may get it
+	      //  would need.
+	      // It is possible to maintain some out-of-band capabilities
+	      // containing the permissions we need to increase the bounds on a
+	      // pointer that we are requesting be deallocated.  However this
+	      // would require we maintain another data structure, and there is
+	      // little security problem allowing a user to access padding
+	      // space just after their allocation (which will not be affecting
+	      // any other allocation).
+	      __ret = __builtin_cheri_bounds_set_exact
+		      (__ret, _M_round_up(__bytes));
+#endif
 	    }
 	}
       return __ret;
diff --git a/libstdc++-v3/testsuite/ext/pool_allocator/check_read_end_of_bounds.cc b/libstdc++-v3/testsuite/ext/pool_allocator/check_read_end_of_bounds.cc
new file mode 100644
index 00000000000..7eef49a1848
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pool_allocator/check_read_end_of_bounds.cc
@@ -0,0 +1,30 @@
+// Copyright (C) 2022 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/>.
+
+// 20.4.1.1 allocator members
+
+#include <cstdlib>
+#include <ext/pool_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  // Uses new, but delete only sometimes.
+  typedef __gnu_cxx::__pool_alloc<unsigned int> allocator_type;
+  __gnu_test::check_read_end_of_bounds<allocator_type, false>();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pool_allocator/check_read_out_of_bounds.cc b/libstdc++-v3/testsuite/ext/pool_allocator/check_read_out_of_bounds.cc
new file mode 100644
index 00000000000..30fa51775ce
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pool_allocator/check_read_out_of_bounds.cc
@@ -0,0 +1,36 @@
+// { dg-shouldfail-purecap "out of bounds" }
+
+// Copyright (C) 2022 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/>.
+
+// 20.4.1.1 allocator members
+
+#include <cstdlib>
+#include <ext/pool_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  typedef __gnu_cxx::__pool_alloc<unsigned int> allocator_type;
+  // Ensure that the test will return `0` if all operations are executed, and
+  // the compiler does not optimise away the reads at higher optimisation
+  // levels.
+  unsigned int x = __gnu_test::check_read_out_of_bounds<allocator_type, false>();
+  asm volatile ("" : "=r" (x) : "r" (x) : );
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pool_allocator/check_reallocate_and_read.cc b/libstdc++-v3/testsuite/ext/pool_allocator/check_reallocate_and_read.cc
new file mode 100644
index 00000000000..713f17d64b7
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pool_allocator/check_reallocate_and_read.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2022 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/>.
+
+// 20.4.1.1 allocator members
+
+#include <cstdlib>
+#include <ext/pool_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  typedef __gnu_cxx::__pool_alloc<unsigned int> allocator_type;
+  // Ensure that the test will return `0` if all operations are executed, and
+  // the compiler does not optimise away the reads at higher optimisation
+  // levels.
+  unsigned int x = __gnu_test::check_reallocate_and_read<allocator_type, true>();
+  asm volatile ("" : "=r" (x) : "r" (x) : );
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/lib/dg-enable-shouldfail.exp b/libstdc++-v3/testsuite/lib/dg-enable-shouldfail.exp
new file mode 100644
index 00000000000..483655b6d68
--- /dev/null
+++ b/libstdc++-v3/testsuite/lib/dg-enable-shouldfail.exp
@@ -0,0 +1,35 @@
+# The below mostly taken from gcc-dg.exp.
+# We want `dg-shouldfail` in libstdc++ tests.  The procedure itself is loaded
+# by a load_lib directive in libstdc++.exp, but it only works via a wrapper
+# around the procedure which runs an executable and sets the pass/fail status.
+#
+# This procedure defines that wrapper.  In order to define the wrapper the
+# original procedure to run the executable needs to have been defined.  This is
+# defined in the board/OS config (or config/default.exp if there is no specific
+# config given).
+# These configuration files are loaded after libstdc++.exp, which means
+# defining the wrapper there can not work.  Hence we define it in a separate
+# file and allow this file to be loaded from those testsuite drivers that need
+# it.
+if { [info procs ${tool}_load] != [list] \
+      && [info procs saved_${tool}_load] == [list] } {
+    rename ${tool}_load saved_${tool}_load
+
+    proc ${tool}_load { program args } {
+	global tool
+	global shouldfail
+
+	set result [eval [list saved_${tool}_load $program] $args]
+	if { $shouldfail != 0 } {
+	    switch [lindex $result 0] {
+		"pass" { set status "fail" }
+		"fail" { set status "pass" }
+		default { set status [lindex $result 0] }
+	    }
+	    set result [list $status [lindex $result 1]]
+	}
+
+	set result [list [lindex $result 0] [lindex $result 1]]
+	return $result
+    }
+}
diff --git a/libstdc++-v3/testsuite/lib/libstdc++.exp b/libstdc++-v3/testsuite/lib/libstdc++.exp
index 78484f7c9af..712ed0e786f 100644
--- a/libstdc++-v3/testsuite/lib/libstdc++.exp
+++ b/libstdc++-v3/testsuite/lib/libstdc++.exp
@@ -442,6 +442,7 @@ if { [info procs saved-dg-test] == [list] } {
 	global additional_prunes
 	global errorInfo
 	global testname_with_flags
+	global shouldfail
 
 	if { [ catch { eval saved-dg-test $args } errmsg ] } {
 	    set saved_info $errorInfo
@@ -450,6 +451,7 @@ if { [info procs saved-dg-test] == [list] } {
 		unset testname_with_flags
 	    }
 	    unset_timeout_vars
+	    set shouldfail 0
 	    error $errmsg $saved_info
 	}
 	set additional_prunes ""
@@ -457,6 +459,7 @@ if { [info procs saved-dg-test] == [list] } {
 	if [info exists testname_with_flags] {
 	    unset testname_with_flags
 	}
+	set shouldfail 0
     }
 }
 
diff --git a/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp b/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp
index 11fdc8d340b..f47fc382b8e 100644
--- a/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp
+++ b/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp
@@ -18,6 +18,7 @@
 
 # libstdc++-v3 testsuite that uses the 'dg.exp' driver.
 
+load_lib dg-enable-shouldfail.exp
 # Initialization.
 dg-init
 
diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
index a90ffd47524..ca17d3f4c05 100644
--- a/libstdc++-v3/testsuite/util/replacement_memory_operators.h
+++ b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
@@ -1,5 +1,5 @@
 //
-// Copyright (C) 2007-2020 Free Software Foundation, Inc.
+// Copyright (C) 2007-2022 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
@@ -89,6 +89,100 @@ namespace __gnu_test
 	throw std::logic_error("counter not decremented");
       return __b;
     }
+
+  template<typename Alloc, bool uses_global_delete>
+    typename Alloc::value_type
+    check_reallocate_and_read(Alloc a = Alloc())
+      {
+	typename Alloc::pointer p, p2;
+	typename Alloc::value_type ret;
+	__gnu_test::counter::exceptions(false);
+#define ALLOC_AND_ADD(NUM_OBJS) \
+	{ \
+	  p = a.allocate((NUM_OBJS)); \
+	  p2 = a.allocate((NUM_OBJS)); \
+	  ret += *(p  + NUM_OBJS - 1); \
+	  ret += *(p2 + NUM_OBJS - 1); \
+	  a.deallocate(p, (NUM_OBJS)); \
+	  a.deallocate(p2, (NUM_OBJS)); \
+	}
+
+	// Allocate and add a few times for an allocation that should use
+	// operator new (i.e. a large allocation).
+	ALLOC_AND_ADD (100);
+	ALLOC_AND_ADD (100);
+	ALLOC_AND_ADD (100);
+
+	// Now allocate and add a few times for an allocation that might use
+	// operator new.
+	ALLOC_AND_ADD (10);
+	ALLOC_AND_ADD (10);
+	ALLOC_AND_ADD (10);
+
+	// Now allocate and add a few times for an allocation that probably
+	// won't use operator new.
+	ALLOC_AND_ADD (1);
+	ALLOC_AND_ADD (1);
+	ALLOC_AND_ADD (1);
+
+	// N.b. we are not trying to check anything about the values and
+	// pointers, just trying to check that the reads are allowed and that
+	// deallocating and reallocating doesn't crash.
+	// We want to ensure that the reads are not optimised out, hence we
+	// return some combination of the reads.
+	// In order to run this test the value_type must be something which has
+	// an operator+ on it.
+	return ret;
+      }
+
+  template<typename Alloc, bool uses_global_delete>
+    typename Alloc::value_type
+    check_read_out_of_bounds(Alloc a = Alloc())
+      {
+	// N.b. we choose the size quite carefully for our tests.
+	// Unfortunately this is based on implementation details.
+	// Our memory allocators which use this test both round up the bounds
+	// of the allocations they return in order to simplify the
+	// implementation details.  Hence in order to produce a working test we
+	// use a number of allocations which result in tight bounds despite
+	// this rounding up.
+	__gnu_test::counter::exceptions(false);
+#if __cplusplus >= 201103L
+	auto p = a.allocate(8);
+	auto val = *(p+8);
+	a.deallocate(p, 8);
+#else
+	typename Alloc::pointer p = a.allocate(8);
+	typename Alloc::value_type val = *(p+8);
+	a.deallocate(p, 8);
+#endif
+	// N.b. we are not trying to check anything about the values and
+	// pointers, just trying to check that the read above is not OK.
+	return val;
+      }
+
+  template<typename Alloc, bool uses_global_delete>
+    typename Alloc::value_type
+    check_read_end_of_bounds(Alloc a = Alloc())
+      {
+	// Allocate a large-ish sized allocation, then reclaim it, then
+	// allocate again.  Often this will result in being given the same
+	// original allocation back.
+	// This is useful to test CHERI bounded pointers to ensure that any
+	// bounds applied do not restrict the access of any future allocations.
+	__gnu_test::counter::exceptions(false);
+	typename Alloc::pointer p;
+	typename Alloc::value_type val;
+	p = a.allocate(9);
+	val = *(p+8);
+	a.deallocate(p, 9);
+	p = a.allocate(10);
+	val += *(p+9);
+	a.deallocate(p, 10);
+	// N.b. we are not trying to check anything about the values and
+	// pointers, just trying to check that the read above is not OK.
+	return val;
+      }
 } // namespace __gnu_test
 
 void* operator new(std::size_t size) THROW(std::bad_alloc)