https://gcc.gnu.org/g:d456728667ddace4cf34ac7a5e63cb67de4c6257
commit r15-7905-gd456728667ddace4cf34ac7a5e63cb67de4c6257
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Thu Mar 6 10:53:38 2025 +0000
libstdc++: Simplify __memcpyable_iterators concept
My P3349R1 paper clarifies that we should be able to lower contiguous
iterators to pointers, without worrying about side effects of individual
increment or dereference operations.
We do need to advance the iterators, and we need to use std::to_address
on the result of advancing them. This ensures that iterators with error
detection get a chance to diagnose bugs. If we don't use std::to_address
on the advanced iterator, it would be possible for a memcpy on the
pointers to overflow a buffer. By performing the += or -= operations and
also using std::to_address, we give the iterator a chance to abort,
throw, or call a violation handler before the buffer overflow happens.
The new tests only check the std::copy* algorithms, because std::move
and std::move_backward use the same implementation details.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (__nothrow_contiguous_iterator):
Remove.
(__memcpyable_iterators): Simplify.
(__copy_move_a2, __copy_n_a, __copy_move_backward_a2): Call
std::to_address on the iterators after advancing them.
* testsuite/25_algorithms/copy/contiguous.cc: New test.
* testsuite/25_algorithms/copy_backward/contiguous.cc: New test.
* testsuite/25_algorithms/copy_n/contiguous.cc: New test.
Reviewed-by: Tomasz Kamiński <tkami...@redhat.com>
Diff:
---
libstdc++-v3/include/bits/stl_algobase.h | 39 ++++------
.../testsuite/25_algorithms/copy/contiguous.cc | 87 +++++++++++++++++++++
.../25_algorithms/copy_backward/contiguous.cc | 88 ++++++++++++++++++++++
.../testsuite/25_algorithms/copy_n/contiguous.cc | 87 +++++++++++++++++++++
4 files changed, 276 insertions(+), 25 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algobase.h
b/libstdc++-v3/include/bits/stl_algobase.h
index fc7cc89736a8..119dbe9a0936 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -359,27 +359,13 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
#endif // HOSTED
#if __cpp_lib_concepts
- // N.B. this is not the same as nothrow-forward-iterator, which doesn't
- // require noexcept operations, it just says it's undefined if they throw.
- // Here we require them to be actually noexcept.
- template<typename _Iter>
- concept __nothrow_contiguous_iterator
- = contiguous_iterator<_Iter> && requires (_Iter __i) {
- // If this operation can throw then the iterator could cause
- // the algorithm to exit early via an exception, in which case
- // we can't use memcpy.
- { *__i } noexcept;
- };
-
template<typename _OutIter, typename _InIter, typename _Sent = _InIter>
concept __memcpyable_iterators
- = __nothrow_contiguous_iterator<_OutIter>
- && __nothrow_contiguous_iterator<_InIter>
+ = contiguous_iterator<_OutIter> && contiguous_iterator<_InIter>
&& sized_sentinel_for<_Sent, _InIter>
- && requires (_OutIter __o, _InIter __i, _Sent __s) {
+ && requires (_OutIter __o, _InIter __i) {
requires !!__memcpyable<decltype(std::to_address(__o)),
decltype(std::to_address(__i))>::__value;
- { __i != __s } noexcept;
};
#endif
@@ -457,9 +443,10 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
void* __dest = std::to_address(__result);
const void* __src = std::to_address(__first);
size_t __nbytes = __n * sizeof(iter_value_t<_InIter>);
- // Advance the iterators first, in case doing so throws.
- __result += __n;
- __first += __n;
+ // Advance the iterators and convert to pointers first.
+ // This gives the iterators a chance to do bounds checking.
+ (void) std::to_address(__result += __n);
+ (void) std::to_address(__first += __n);
__builtin_memmove(__dest, __src, __nbytes);
}
else if (__n == 1)
@@ -579,9 +566,10 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
void* __dest = std::to_address(__result);
const void* __src = std::to_address(__first);
size_t __nbytes = __n * sizeof(iter_value_t<_InputIterator>);
- // Advance the iterators first, in case doing so throws.
- __result += __n;
- __first += __n;
+ // Advance the iterators and convert to pointers first.
+ // This gives the iterators a chance to do bounds checking.
+ (void) std::to_address(__result += __n);
+ (void) std::to_address(__first += __n);
__builtin_memmove(__dest, __src, __nbytes);
}
else if (__n == 1)
@@ -727,9 +715,10 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
if (auto __n = __last - __first; __n > 1) [[likely]]
{
const void* __src = std::to_address(__first);
- // Advance the iterators first, in case doing so throws.
- __result -= __n;
- __first += __n;
+ // Advance the iterators and convert to pointers first.
+ // This gives the iterators a chance to do bounds checking.
+ (void) std::to_address(__result -= __n);
+ (void) std::to_address(__first += __n);
void* __dest = std::to_address(__result);
size_t __nbytes = __n * sizeof(iter_value_t<_BI1>);
__builtin_memmove(__dest, __src, __nbytes);
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/contiguous.cc
b/libstdc++-v3/testsuite/25_algorithms/copy/contiguous.cc
new file mode 100644
index 000000000000..0fdce08ece8b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/contiguous.cc
@@ -0,0 +1,87 @@
+// { dg-do run { target c++20 } }
+
+#include <algorithm>
+#include <iterator>
+#include <cstdlib>
+#include <testsuite_hooks.h>
+
+const int valid_size = 3;
+const int out_of_bound = valid_size + 1;
+// data is larger than valid_size so that `data + out_of_bound` does
+// not have undefined behaviour, but data[valid_size] is not allowed
+// to be accessed by Iter.
+int data[valid_size + 1]{ 1, 2, 3, -999 };
+
+struct Iter
+{
+ using iterator_category = std::contiguous_iterator_tag;
+ using value_type = int;
+ using different_type = int;
+ using reference = int&;
+ using pointer = int*;
+
+ static inline bool advance_error = false;
+ static inline bool address_error = false;
+
+ int index{};
+
+ int& operator*() const
+ { std::abort(); } // Should not happen if reads/writes are done on pointers.
+
+ int* operator->() const
+ {
+ if (index < 0 || index > valid_size)
+ {
+ address_error = true;
+ return data + valid_size;
+ }
+ return data + index;
+ }
+
+ int& operator[](int n) const { return *(*this + n); }
+
+ Iter& operator++() { return *this += 1; }
+ Iter& operator--() { return *this -= 1; }
+ Iter operator++(int) { return Iter{index++}; }
+ Iter operator--(int) { return Iter{index--}; }
+
+ bool operator==(const Iter&) const = default;
+ auto operator<=>(const Iter&) const = default;
+
+ Iter& operator+=(int n)
+ {
+ index += n;
+ if (index < 0 || index > valid_size)
+ advance_error = true;
+ return *this;
+ }
+ Iter& operator-=(int n) { return *this += -n; }
+
+ friend Iter operator+(Iter i, int n) { return i += n; }
+ friend Iter operator+(int n, Iter i) { return i + n; }
+ friend Iter operator-(Iter i, int n) { return i + -n; }
+ friend int operator-(Iter i, Iter j) { return i.index - j.index; }
+};
+
+static_assert( std::contiguous_iterator<Iter> );
+
+int main()
+{
+ // P3349R1 allows std::copy to lower contiguous iterators to pointers,
+ // but it must still advance the contiguous iterator and use std::to_address
+ // to get a pointer for both ends of the range.
+ // This test verifies that Iter::operator-> is called for an out-of-range
+ // iterator, so that a hardened iterator with error-checking is able to
+ // detect the error.
+
+ int i[out_of_bound];
+ // Attempt to read from an out-of-bound Iter:
+ std::copy(Iter{0}, Iter{out_of_bound}, i);
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+ Iter::advance_error = Iter::address_error = false;
+ // Attempt to write to an out-of-bound Iter:
+ std::copy(std::begin(i), std::end(i), Iter{0});
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/contiguous.cc
b/libstdc++-v3/testsuite/25_algorithms/copy_backward/contiguous.cc
new file mode 100644
index 000000000000..b8cfa2ea5fdf
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/contiguous.cc
@@ -0,0 +1,88 @@
+// { dg-do run { target c++20 } }
+
+#include <algorithm>
+#include <iterator>
+#include <cstdlib>
+#include <testsuite_hooks.h>
+
+const int valid_size = 3;
+const int out_of_bound = valid_size + 1;
+// array is larger than valid_size so that `data + out_of_bound` and `data - 1`
+// do not have undefined behaviour, but data[valid_size] and data[-1] are
+// not allowed to be accessed by Iter.
+int array[1 + valid_size + 1]{ -999, 1, 2, 3, -999 };
+int* data = array + 1;
+
+struct Iter
+{
+ using iterator_category = std::contiguous_iterator_tag;
+ using value_type = int;
+ using different_type = int;
+ using reference = int&;
+ using pointer = int*;
+
+ static inline bool advance_error = false;
+ static inline bool address_error = false;
+
+ int index{};
+
+ int& operator*() const
+ { std::abort(); } // Should not happen if reads/writes are done on pointers.
+
+ int* operator->() const
+ {
+ if (index < 0 || index > valid_size)
+ {
+ address_error = true;
+ return data;
+ }
+ return data + index;
+ }
+
+ int& operator[](int n) const { return *(*this + n); }
+
+ Iter& operator++() { return *this += 1; }
+ Iter& operator--() { return *this -= 1; }
+ Iter operator++(int) { return Iter{index++}; }
+ Iter operator--(int) { return Iter{index--}; }
+
+ bool operator==(const Iter&) const = default;
+ auto operator<=>(const Iter&) const = default;
+
+ Iter& operator+=(int n)
+ {
+ index += n;
+ if (index < 0 || index > valid_size)
+ advance_error = true;
+ return *this;
+ }
+ Iter& operator-=(int n) { return *this += -n; }
+
+ friend Iter operator+(Iter i, int n) { return i += n; }
+ friend Iter operator+(int n, Iter i) { return i + n; }
+ friend Iter operator-(Iter i, int n) { return i + -n; }
+ friend int operator-(Iter i, Iter j) { return i.index - j.index; }
+};
+
+static_assert( std::contiguous_iterator<Iter> );
+
+int main()
+{
+ // P3349R1 allows std::copy_backward to lower contiguous iterators to
pointers
+ // but it must still advance the contiguous iterator and use std::to_address
+ // to get a pointer for both ends of the range.
+ // This test verifies that Iter::operator-> is called for an out-of-range
+ // iterator, so that a hardened iterator with error-checking is able to
+ // detect the error.
+
+ int i[out_of_bound];
+ // Attempt to read from an out-of-bound Iter:
+ std::copy_backward(Iter{0}, Iter{out_of_bound}, i + out_of_bound);
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+ Iter::advance_error = Iter::address_error = false;
+ // Attempt to write to an out-of-bound Iter with index -1:
+ std::copy_backward(std::begin(i), std::end(i), Iter{valid_size});
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_n/contiguous.cc
b/libstdc++-v3/testsuite/25_algorithms/copy_n/contiguous.cc
new file mode 100644
index 000000000000..b5f00f5d1bc1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_n/contiguous.cc
@@ -0,0 +1,87 @@
+// { dg-do run { target c++20 } }
+
+#include <algorithm>
+#include <iterator>
+#include <cstdlib>
+#include <testsuite_hooks.h>
+
+const int valid_size = 3;
+const int out_of_bound = valid_size + 1;
+// data is larger than valid_size so that `data + out_of_bound` does
+// not have undefined behaviour, but data[valid_size] is not allowed
+// to be accessed by Iter.
+int data[valid_size + 1]{ 1, 2, 3, -999 };
+
+struct Iter
+{
+ using iterator_category = std::contiguous_iterator_tag;
+ using value_type = int;
+ using different_type = int;
+ using reference = int&;
+ using pointer = int*;
+
+ static inline bool advance_error = false;
+ static inline bool address_error = false;
+
+ int index{};
+
+ int& operator*() const
+ { std::abort(); } // Should not happen if reads/writes are done on pointers.
+
+ int* operator->() const
+ {
+ if (index < 0 || index > valid_size)
+ {
+ address_error = true;
+ return data + valid_size;
+ }
+ return data + index;
+ }
+
+ int& operator[](int n) const { return *(*this + n); }
+
+ Iter& operator++() { return *this += 1; }
+ Iter& operator--() { return *this -= 1; }
+ Iter operator++(int) { return Iter{index++}; }
+ Iter operator--(int) { return Iter{index--}; }
+
+ bool operator==(const Iter&) const = default;
+ auto operator<=>(const Iter&) const = default;
+
+ Iter& operator+=(int n)
+ {
+ index += n;
+ if (index < 0 || index > valid_size)
+ advance_error = true;
+ return *this;
+ }
+ Iter& operator-=(int n) { return *this += -n; }
+
+ friend Iter operator+(Iter i, int n) { return i += n; }
+ friend Iter operator+(int n, Iter i) { return i + n; }
+ friend Iter operator-(Iter i, int n) { return i + -n; }
+ friend int operator-(Iter i, Iter j) { return i.index - j.index; }
+};
+
+static_assert( std::contiguous_iterator<Iter> );
+
+int main()
+{
+ // P3349R1 allows std::copy_n to lower contiguous iterators to pointers,
+ // but it must still advance the contiguous iterator and use std::to_address
+ // to get a pointer for both ends of the range.
+ // This test verifies that Iter::operator-> is called for an out-of-range
+ // iterator, so that a hardened iterator with error-checking is able to
+ // detect the error.
+
+ int i[out_of_bound];
+ // Attempt to read from an out-of-bound Iter:
+ std::copy_n(Iter{0}, out_of_bound, i);
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+ Iter::advance_error = Iter::address_error = false;
+ // Attempt to write to an out-of-bound Iter:
+ std::copy_n(std::begin(i), out_of_bound, Iter{0});
+ VERIFY( Iter::advance_error );
+ VERIFY( Iter::address_error );
+}
