From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2049) id 2544A3858D39; Wed, 19 Oct 2022 11:01:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2544A3858D39 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666177287; bh=+wL2/vssQP4/Co9HA2eDVCZNGrVmPYY052096dOLaJY=; h=From:To:Subject:Date:From; b=vlZbG05ZkOC2cGBfAVxSPt3kGTvUaTenuF2l4gV/pRJYjJmPEMkoygtVGd8UyguAC N8licdYmkiRAxSMsZ19Dmcx61QDhpoZKAwGSRPc4dVQxrIxkrvJvRGv9kGrdojKPb6 zFMtSCMzzQOneI25LCyKKqM1HcF9zLPvzmvBp0do= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Matthew Malcomson To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc(refs/vendors/ARM/heads/morello)] Update mt_allocator for CHERI X-Act-Checkin: gcc X-Git-Author: Matthew Malcomson X-Git-Refname: refs/vendors/ARM/heads/morello X-Git-Oldrev: 8db59b80459ed21d889f07d548511e9a9ea6fee7 X-Git-Newrev: 7c3edbbe0452d99192b97c88fdd65fb321e85e76 Message-Id: <20221019110127.2544A3858D39@sourceware.org> Date: Wed, 19 Oct 2022 11:01:27 +0000 (GMT) List-Id: https://gcc.gnu.org/g:7c3edbbe0452d99192b97c88fdd65fb321e85e76 commit 7c3edbbe0452d99192b97c88fdd65fb321e85e76 Author: Matthew Malcomson 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(__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 +#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(__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(__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(__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 +// . + +// 20.4.1.1 allocator members + +#include +#include +#include + +int main() +{ + // Uses new, but delete only sometimes. + typedef __gnu_cxx::__mt_alloc allocator_type; + __gnu_test::check_read_end_of_bounds(); + 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 +// . + +// 20.4.1.1 allocator members + +#include +#include +#include + +int main() +{ + typedef __gnu_cxx::__mt_alloc 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(); + 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 +// . + +// 20.4.1.1 allocator members + +#include +#include +#include + +int main() +{ + typedef __gnu_cxx::__mt_alloc 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(); + asm volatile ("" : "=r" (x) : "r" (x) : ); + return 0; +}