[gcc(refs/vendors/ARM/heads/morello)] Update mt_allocator for CHERI

[gcc(refs/vendors/ARM/heads/morello)] Update mt_allocator for CHERI

[Matthew Malcomson]

https://gcc.gnu.org/g:7c3edbbe0452d99192b97c88fdd65fb321e85e76

commit 7c3edbbe0452d99192b97c88fdd65fb321e85e76
Author: Matthew Malcomson <matthew.malcomson@arm.com>
Date:   Wed Oct 19 11:57:44 2022 +0100

    Update mt_allocator for CHERI
    
    The implementation basics this allocator are as follows:
      - There are N "bins" for each power-of-two size.  N is determined
        based on the maximum size beyond which we do use `new` directly.
      - Each bin contains a linked list of "chunks" that have been
        allocated.  This list is only used at cleanup-time so that we can
        call `delete` on each one.
      - Each bin then contains a linked-list of "records" that represent
        available allocations of the correct size.
      - When there are no available "records" we generate some more by
        obtaining an `_M_chunk_size` block from `new` and splitting it up
        into `(_M_chunk_size - address metadata) / sizeof(record)` records.
    
    ----
    The existing errors that we see in our testsuite were all to do with
    misalignment of capabilities in our allocations.  This was happening
    when we were attempting to store our linked-list pointers in misaligned
    locations.  There is an `_M_align` configuration member which determines
    the alignment required for a record.  This must also be `>=
    sizeof(_Block_record)` since the alignment also corresponds to the size
    left for each record metadata.
    
    The existing alignment was 8.  We update it to use the larger of 8 and
    `__SIZEOF_POINTER__` where possible given that the size of a
    `_Block_record` is a pointer.  This avoids all alignment problems that
    we see in the testcase.
    
    Considering if extra padding and alignment is necessary for large
    allocations, we see that the maximum allocation size before falling back
    to `new` is configurable.  However, as the comments describe this has a
    maximum of 32768.  It happens that the alignment requirement to allow
    CHERI to precisely bound an allocation of 32768 bytes is 16, which is
    the same alignment requirement we already have in order to store
    capabilities in the metadata.  Hence we do not have to worry about
    padding and alignment for CHERI bounds.
    
    ----
    Given that the metadata recorded in these allocations contains a pointer
    that would give the user more permissions (especially around permissions
    to access other objects) than are necessary, we zero out this metadata
    area before returning it to the user.  This information does not need to
    be maintained over the period that the user has access to it.
    
    ----
    Restricting the bounds of returned allocations is more tricky.  The act
    of applying bounds is relatively simple -- we have to call the
    appropriate bounding function everywhere that a "record" is made.  The
    problem occurs during deallocation when the allocation given out must be
    reclaimed by adding metadata to the space.  In mt_alloc the metadata is
    stored just before the allocation returned to the user.  This stands in
    contrast to the pool_allocator which stores metadata at the start of the
    allocation.  This means that a basic implementation of narrowing bounds
    would need to include 16 bytes before the allocation returned as well as
    the total allocation returned.
    
    On top of this, since this allocator is a power-of-two allocator (as
    opposed to a multiple-of-alignment sized allocator like pool_allocator)
    the space at the end of an allocation that would need to be accessible
    in order for any reclaimed allocations to have bounds spanning the
    entire range they need may be quite large.  E.g. an allocation of 8193
    bytes would be satisfied from the free list of blocks of 16384 (2^14)
    bytes.  Without any mechanism to widen the bounds of a deallocated
    pointer we would have to give the user a capability with bounds spanning
    the entire 16384 bytes.
    
    This implies that the trade-off in forgoing tight bounds in order to not
    change the implementation of this allocator is much more dramatic than
    the corresponding trade-off in pool_allocator.  However the decision is
    still in much the same vein -- tight-bounds requires some extra data
    structure to maintain extra permissions for use in increasing bounds of
    pointers that are being deallocated, while lax bounds miss more
    out-of-bounds accesses but still do not provide access to any other
    objects that the user did not have access to before (only provides
    access to padding at the end of an allocation).
    
    Based on the fact that this allocator keeps a record of allocations that
    it has made, these allocations could be used to widen the bounds of any
    block returned to the allocator by the user.  However this would require
    either a new data structure to look these things up (e.g. hash table) or
    a linked-list traverse on the existing data structure.
    
    Given this particular allocator does not seem to be used in many places
    (a debian code search for `__mt_alloc` only found few packages outside
    of compilers), we have decided to forego adjusting this particular
    allocator to have the tightest bounds available.

Diff:
---
 libstdc++-v3/include/ext/mt_allocator.h            |  9 ++++--
 libstdc++-v3/src/c++98/mt_allocator.cc             | 15 +++++++++-
 .../ext/mt_allocator/check_read_end_of_bounds.cc   | 30 +++++++++++++++++++
 .../ext/mt_allocator/check_read_out_of_bounds.cc   | 35 ++++++++++++++++++++++
 .../ext/mt_allocator/check_reallocate_and_read.cc  | 33 ++++++++++++++++++++
 5 files changed, 118 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/include/ext/mt_allocator.h b/libstdc++-v3/include/ext/mt_allocator.h
index 0857390e665..36067831e12 100644
--- a/libstdc++-v3/include/ext/mt_allocator.h
+++ b/libstdc++-v3/include/ext/mt_allocator.h
@@ -1,6 +1,6 @@
 // MT-optimized allocator -*- C++ -*-
 
-// Copyright (C) 2003-2020 Free Software Foundation, Inc.
+// Copyright (C) 2003-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
@@ -58,9 +58,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct _Tune
     {
       // Compile time constants for the default _Tune values.
-      enum { _S_align = 8 };
+      enum { _S_align = sizeof (void*) > 8 ? sizeof (void*) : 8 };
+      enum { _S_min_bin = sizeof (void*) > 8 ? sizeof (void*) : 8 };
       enum { _S_max_bytes = 128 };
-      enum { _S_min_bin = 8 };
       enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
       enum { _S_max_threads = 4096 };
       enum { _S_freelist_headroom = 10 };
@@ -729,6 +729,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  __bin._M_first[__thread_id] = __block->_M_next;
 	  
 	  __pool._M_adjust_freelist(__bin, __block, __thread_id);
+#ifdef __CHERI_PURE_CAPABILITY__
+	  __block->_M_next = (_Block_record *)0;
+#endif
 	  __c = reinterpret_cast<char*>(__block) + __pool._M_get_align();
 	}
       else
diff --git a/libstdc++-v3/src/c++98/mt_allocator.cc b/libstdc++-v3/src/c++98/mt_allocator.cc
index 5741d8e73a2..a24c6e12c69 100644
--- a/libstdc++-v3/src/c++98/mt_allocator.cc
+++ b/libstdc++-v3/src/c++98/mt_allocator.cc
@@ -1,6 +1,6 @@
 // Allocator details.
 
-// Copyright (C) 2004-2020 Free Software Foundation, Inc.
+// Copyright (C) 2004-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
@@ -36,6 +36,13 @@
 // uintptr_t.
 #include <stdint.h>
 
+#ifdef __CHERI_PURE_CAPABILITY__
+#define maybe_set_cheri_bounds(p, n) \
+	__builtin_cheri_bounds_set_exact ((p), (n))
+#else
+#define maybe_set_cheri_bounds(p, n) (p)
+#endif
+
 namespace
 {
 #ifdef __GTHREADS
@@ -151,12 +158,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
     char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
     _Block_record* __block = reinterpret_cast<_Block_record*>(__c);
+    __block = maybe_set_cheri_bounds(__block, __bin_size);
     __bin._M_first[__thread_id] = __block;
     while (--__block_count > 0)
       {
 	__c += __bin_size;
 	__block->_M_next = reinterpret_cast<_Block_record*>(__c);
 	__block = __block->_M_next;
+	__block = maybe_set_cheri_bounds(__block, __bin_size);
       }
     __block->_M_next = 0;
 
@@ -396,12 +405,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
 	    __block = reinterpret_cast<_Block_record*>(__c);
 	    __bin._M_free[__thread_id] = __block_count;
+	    __block = maybe_set_cheri_bounds(__block, __bin_size);
 	    __bin._M_first[__thread_id] = __block;
 	    while (--__block_count > 0)
 	      {
 		__c += __bin_size;
 		__block->_M_next = reinterpret_cast<_Block_record*>(__c);
 		__block = __block->_M_next;
+		__block = maybe_set_cheri_bounds(__block, __bin_size);
 	      }
 	    __block->_M_next = 0;
 	  }
@@ -440,12 +451,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
 	__block = reinterpret_cast<_Block_record*>(__c);
+	__block = maybe_set_cheri_bounds(__block, __bin_size);
  	__bin._M_first[0] = __block;
 	while (--__block_count > 0)
 	  {
 	    __c += __bin_size;
 	    __block->_M_next = reinterpret_cast<_Block_record*>(__c);
 	    __block = __block->_M_next;
+	    __block = maybe_set_cheri_bounds(__block, __bin_size);
 	  }
 	__block->_M_next = 0;
       }
diff --git a/libstdc++-v3/testsuite/ext/mt_allocator/check_read_end_of_bounds.cc b/libstdc++-v3/testsuite/ext/mt_allocator/check_read_end_of_bounds.cc
new file mode 100644
index 00000000000..a269dbaa724
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/mt_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/mt_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  // Uses new, but delete only sometimes.
+  typedef __gnu_cxx::__mt_alloc<unsigned int> allocator_type;
+  __gnu_test::check_read_end_of_bounds<allocator_type, false>();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/mt_allocator/check_read_out_of_bounds.cc b/libstdc++-v3/testsuite/ext/mt_allocator/check_read_out_of_bounds.cc
new file mode 100644
index 00000000000..874cae72138
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/mt_allocator/check_read_out_of_bounds.cc
@@ -0,0 +1,35 @@
+// { 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/mt_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  typedef __gnu_cxx::__mt_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/mt_allocator/check_reallocate_and_read.cc b/libstdc++-v3/testsuite/ext/mt_allocator/check_reallocate_and_read.cc
new file mode 100644
index 00000000000..2bddabfdd17
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/mt_allocator/check_reallocate_and_read.cc
@@ -0,0 +1,33 @@
+// 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/mt_allocator.h>
+#include <replacement_memory_operators.h>
+
+int main()
+{
+  typedef __gnu_cxx::__mt_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;
+}