[libc++] Implement P0401R6 (allocate_at_least)

[var-const]

libcxx/include/__memory/allocate_at_least.h

59

Nit: can it be just return {__alloc.allocate(__n), __n}; like above? I think braced-list initialization should be supported in old language modes.

65

Nit: remove one extra blank line (there currently are two blank lines next to each other).

libcxx/include/__memory/allocator.h

16

Nit: I think it would be easier to just follow "include-what-you-use". It's not obvious that allocate_at_least.h should guarantee to include <cstddef>.

113

Hmm, if I'm reading this correctly, this is exactly equivalent to the old behavior -- even though we implement an interface that would allow an allocator to overallocate, the actual standard allocators never overallocate. Does this require a TODO? Or is this feature only for user-provided allocators?

libcxx/include/string

3293

Question: this is to account for the terminating null, right? Would it be cleaner to remove the subtraction here and the + 1 addition below, instead of having to adjust the value twice?

libcxx/include/vector

2346

Is this line equivalent to this->__cap() = __n; (where __n = __external_cap_to_internal(__n);)? In other words, does __allocation.count require the external->internal adjustment or not?

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp

2

I think there also needs to be a test for std::allocator<T>::allocate_at_least. This test essentially checks that std::allocate_at_least is correctly forwarded to the allocator's allocate_at_least.

22

Nit: make it a struct and avoid the public: label?

31

Nit: since these helpers are always instantiated with int, they probably don't need to be templates at all.

48

Nit: decltype(auto).

[philnik]

libcxx/include/__memory/allocator.h

113

I don't think there is anything preventing an implementation from over-allocating, but I don't know of a standard C API for over-allocating. We can of course special-case this for malloc implementations that have an API for over-allocating.

libcxx/include/string

3293

Feel free to review D119628! But maybe you should wait until I land D110598.

libcxx/include/vector

2346

AFAICT the number of size_types is stored, so no, this doesn't require translation. The allocator returns the number of allocated objects, so the same number that is saved internally.

[var-const]

libcxx/include/__memory/allocator.h

113

Maybe I'm misreading the paper (I wasn't aware of it before seeing this patch), but it seemed like the whole purpose of allocate_at_least is to avoid wasting capacity in case an allocator overallocates. I'm not clear, however, if this only applies to user-provided allocators, or if it's meant specifically for std::allocator, but given the wording changes for std::allocator, I presume the latter.

I don't know if the underlying allocator machinery we're currently using is overallocating and if there's a way to query the actual allocated size. However, I think that:

• if our underlying allocations never overallocate, we should add a comment to that effect to std::allocator<T>::allocate_at_least;
• otherwise, we should add a TODO.

In short, if I'm reading the paper correctly, it's meant to bring a behavioral change, whereas with the current implementation in this patch, the behavior will be exactly equivalent. Once again, I might well be missing or misreading something -- please point it out if I do.

libcxx/include/string

3293

Interesting, thanks for the link. I didn't realize there's a much bigger discussion hidden here.

[philnik]

• Address comments

libcxx/include/__memory/allocator.h

113

I think you are right that the implementation is allowed to return more memory than was requested. The problem is that we have no way to tell if the underlying allocator ever over-allocates. We don't have an API that can tell us that. There is no C-version of allocate_at_least. The only way to support this currently is through extensions. But I don't think we should add a TODO there. This TODO would never be removed, and what's the point of a TODO then? We also don't have a // TODO: optimize sort.

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp

31

I think you have to be able to rebind an allocator, so making this a non-template class would make this technically not an allocator.

[var-const]

libcxx/include/__memory/allocator.h

113

I feel that we would have to use compiler-internal functions, so it's okay that there is no C-version. I wouldn't call it an extension, though -- some library functionality can only be implemented using magical compiler intrinsics.

Regarding the TODO, I think the full intention of the paper won't be realized until this is implemented, so the TODO is necessary. The optimize sort case is different -- there is always room for optional optimization, but in this case I feel this is almost a mandatory optimization. To continue with the sort analogy, if we had a sort implementation that had a O(N^2) worst-case complexity, a TODO would be in order.

Having said that, I don't know if the actual low-level allocation functions we use support or ever plan to support over-allocating. @ldionne what are your thoughts on this?

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp

2

Thanks for expanding the test! What I meant is that since we're adding two new functions to the API (std::allocate_at_least and std::allocator<T>::allocate_at_least), we should have separate test for both of them -- i.e., we can't rely on std::allocate_at_least tests to test std::allocator<T>::allocate_at_least. I know that, at least in the current state, std::allocator<T>::allocate_at_least is equivalent to std::allocator<T>::allocate and there isn't much to test, but I still feel that at least a rudimentary test needs to be added. But please check with @ldionne -- perhaps what I'm suggesting is overkill.

[ldionne]

LGTM but I'd like to see the updated tests. Thanks!

libcxx/include/__memory/allocate_at_least.h

47

I don't think this comment is necessary -- IMO it creates confusion where there should be none. Someone looking at this code and going "Hmm, I don't think those identifiers are valid" would easily convince themselves that the world is broken if we can't write that pre-C++23.

libcxx/include/__memory/allocator.h

113

My understanding of the paper's intent is that we add this interface so that user-defined allocators can take advantage of it, *and* system allocators too when possible. However, I agree with @philnik that the C library simply doesn't give us a standard way to take advantage of this at the moment, so I think our implementation is optimal (with one caveat, see below). Because of this, I feel that we *are* implementing the paper faithfully, and there is nothing left to do, so I wouldn't leave any comment. I hope this makes sense.

Caveat: On systems that support it, we could perhaps use malloc_usable_size (https://man7.org/linux/man-pages/man3/malloc_usable_size.3.html) to query how much memory malloc gave us in reality. Doing that in std::allocator is going to create interesting challenges, though, since we use operator new from std::allocator, not std::malloc directly. If it's even possible to do it, I think it will mandate being done in a separate patch as it will certainly be somewhat involved.

In my opinion, where P0401r6 perhaps didn't go far enough is by not adding some sort of operator new where you get a size feedback (oh wait, this is https://wg21.link/p0901r5)! If we had that, then we could use that from std::allocator instead. And from the dylib (where we'd implement that novel operator new), we'd be in a position to call malloc and use malloc_usable_size() on the returned pointer (whenever that's supported).

So I guess I can summarize my opinion by saying that std::allocator is basically a veneer on top of operator new, and so any optimization needs to be made in operator new itself, not in std::allocator.

libcxx/include/memory

101–109

I think we need some // since C++20s?

libcxx/include/string

1862

After we ship this, I would like us to revisit the patch where you modified __recommend's return value (I can't find it ATM). See if it makes that patch any easier.

libcxx/include/vector

683

685

_LIBCPP_HIDE_FROM_ABI?

2337

2340

_LIBCPP_HIDE_FROM_ABI

libcxx/test/libcxx/diagnostics/detail.headers/memory/allocate_at_least.module.verify.cpp

1

Please rebase onto main.

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp

2

I agree -- we definitely need to treat std::allocate_at_least and std::allocator<T>::allocate_at_least as if they were different things, since they are different functions in the API. This test seems to be fine for std::allocate_at_least, but I'd like a separate test for std::allocator::allocate_at_least. You probably want to take some inspiration from libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp & friends for that one (e.g. testing overaligned types, etc.)

14

Can you also add a simple test like

using AllocationResult = std::allocation_result<int*>;

Just to check the box of testing specifically for that type's existence.

[philnik]

• Address comments

[ldionne]

LGTM with added tests for allocator::allocate_at_least.

libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate_at_least.pass.cpp

59 ↗

(On Diff #421171)

I think perhaps you copy-pasted from libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp a bit too eagerly :-). We also need to test:

• The return type of allocator::allocate_at_least
• That the size member is >= to ptr

[var-const]

LGTM (once the remaining comment is addressed). Thanks!

[philnik]

• Address comments

libcxx/docs/FeatureTestMacroTable.rst

.. table:: Current Status
     ``__cpp_lib_type_identity``                       ``201806L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_unwrap_ref``                          ``201811L``
     ------------------------------------------------- -----------------
     **C++ 2b**
     -------------------------------------------------------------------
     ``__cpp_lib_adaptor_iterator_pair_constructor``   ``202106L``
     ------------------------------------------------- -----------------
-    ``__cpp_lib_allocate_at_least``                   *unimplemented*
+    ``__cpp_lib_allocate_at_least``                   ``202106L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_associative_heterogeneous_erasure``   *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_bind_back``                           *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_byteswap``                            ``202110L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_constexpr_cmath``                     *unimplemented*

libcxx/docs/Status/Cxx2bPapers.csv

 "Paper #","Group","Paper Name","Meeting","Status","First released version"
 "`P0881R7 <https://wg21.link/P0881R7>`__","LWG","A Proposal to add stacktrace library","Autumn 2020","",""
 "`P0943R6 <https://wg21.link/P0943R6>`__","LWG","Support C atomics in C++","Autumn 2020","",""
 "`P1048R1 <https://wg21.link/P1048R1>`__","LWG","A proposal for a type trait to detect scoped enumerations","Autumn 2020","|Complete|","12.0"
 "`P1679R3 <https://wg21.link/P1679R3>`__","LWG","string contains function","Autumn 2020","|Complete|","12.0"
 "","","","","",""
 "`P1682R3 <https://wg21.link/P1682R3>`__","LWG","std::to_underlying for enumerations","February 2021","|Complete|","13.0"
 "`P2017R1 <https://wg21.link/P2017R1>`__","LWG","Conditionally borrowed ranges","February 2021","",""
 "`P2160R1 <https://wg21.link/P2160R1>`__","LWG","Locks lock lockables","February 2021","",""
 "`P2162R2 <https://wg21.link/P2162R2>`__","LWG","Inheriting from std::variant","February 2021","|Complete|","13.0"
 "`P2212R2 <https://wg21.link/P2212R2>`__","LWG","Relax Requirements for time_point::clock","February 2021","",""
 "`P2259R1 <https://wg21.link/P2259R1>`__","LWG","Repairing input range adaptors and counted_iterator","February 2021","",""
 "","","","","",""
-"`P0401R6 <https://wg21.link/P0401R6>`__","LWG","Providing size feedback in the Allocator interface","June 2021","",""
+"`P0401R6 <https://wg21.link/P0401R6>`__","LWG","Providing size feedback in the Allocator interface","June 2021","|Complete|","15.0"
 "`P0448R4 <https://wg21.link/P0448R4>`__","LWG","A strstream replacement using span<charT> as buffer","June 2021","",""
 "`P1132R8 <https://wg21.link/P1132R8>`__","LWG","out_ptr - a scalable output pointer abstraction","June 2021","",""
 "`P1328R1 <https://wg21.link/P1328R1>`__","LWG","Making std::type_info::operator== constexpr","June 2021","",""
 "`P1425R4 <https://wg21.link/P1425R4>`__","LWG","Iterators pair constructors for stack and queue","June 2021","|Complete|","14.0"
 "`P1518R2 <https://wg21.link/P1518R2>`__","LWG","Stop overconstraining allocators in container deduction guides","June 2021","|Complete|","13.0"
 "`P1659R3 <https://wg21.link/P1659R3>`__","LWG","starts_with and ends_with","June 2021","",""
 "`P1951R1 <https://wg21.link/P1951R1>`__","LWG","Default Arguments for pair Forwarding Constructor","June 2021","|Complete|","14.0"
 "`P1989R2 <https://wg21.link/P1989R2>`__","LWG","Range constructor for std::string_view","June 2021","|Complete|","14.0"

libcxx/include/CMakeLists.txt

set(files
   __iterator/size.h
   __iterator/sortable.h
   __iterator/unreachable_sentinel.h
   __iterator/wrap_iter.h
   __libcpp_version
   __locale
   __mbstate_t.h
   __memory/addressof.h
+  __memory/allocate_at_least.h
   __memory/allocation_guard.h
   __memory/allocator.h
   __memory/allocator_arg_t.h
   __memory/allocator_traits.h
   __memory/auto_ptr.h
   __memory/compressed_pair.h
   __memory/concepts.h
   __memory/construct_at.h

libcxx/include/__memory/allocate_at_least.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___MEMORY_ALLOCATE_AT_LEAST_H
+#define _LIBCPP___MEMORY_ALLOCATE_AT_LEAST_H
+
+#include <__config>
+#include <__memory/allocator_traits.h>
+#include <cstddef>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 20
+template <class _Pointer>
+struct allocation_result {
+  _Pointer ptr;
+  size_t count;
+};
+
+template <class _Alloc>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr
+allocation_result<typename allocator_traits<_Alloc>::pointer> allocate_at_least(_Alloc& __alloc, size_t __n) {
+  if constexpr (requires { __alloc.allocate_at_least(__n); }) {
+    return __alloc.allocate_at_least(__n);
+  } else {
+    return {__alloc.allocate(__n), __n};
+  }
+}
+
+template <class _Alloc>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr
+auto __allocate_at_least(_Alloc& __alloc, size_t __n) {
+  return std::allocate_at_least(__alloc, __n);
+}
+#else
+template <class _Pointer>
+struct __allocation_result {
+  // both count and ptr are already allowed because of `std::count()` and `std::from_chars_result` respectively
+  _Pointer ptr;
+  size_t count;
+};
+
+template <class _Alloc>
+_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI
+__allocation_result<typename allocator_traits<_Alloc>::pointer> __allocate_at_least(_Alloc& __alloc, size_t __n) {
+  return {__alloc.allocate(__n), __n};
+}
+
+#endif // _LIBCPP_STD_VER > 20
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___MEMORY_ALLOCATE_AT_LEAST_H

libcxx/include/__memory/allocator.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___MEMORY_ALLOCATOR_H
 #define _LIBCPP___MEMORY_ALLOCATOR_H
 
 #include <__config>
+#include <__memory/allocate_at_least.h>
 #include <__memory/allocator_traits.h>
 #include <__utility/forward.h>
 #include <cstddef>
 #include <new>
 #include <stdexcept>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
_Tp* allocate(size_t __n) {
             __throw_bad_array_new_length();
         if (__libcpp_is_constant_evaluated()) {
             return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
         } else {
             return static_cast<_Tp*>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));
         }
     }
 
+#if _LIBCPP_STD_VER > 20
+    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr
+    allocation_result<_Tp*> allocate_at_least(size_t __n) {
+        return {allocate(__n), __n};
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
     void deallocate(_Tp* __p, size_t __n) _NOEXCEPT {
         if (__libcpp_is_constant_evaluated()) {
             ::operator delete(__p);
         } else {
             _VSTD::__libcpp_deallocate((void*)__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
         }
     }
const _Tp* allocate(size_t __n) {
             __throw_bad_array_new_length();
         if (__libcpp_is_constant_evaluated()) {
             return static_cast<const _Tp*>(::operator new(__n * sizeof(_Tp)));
         } else {
             return static_cast<const _Tp*>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));
         }
     }
 
+#if _LIBCPP_STD_VER > 20
+    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr
+    allocation_result<const _Tp*> allocate_at_least(size_t __n) {
+        return {allocate(__n), __n};
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
     void deallocate(const _Tp* __p, size_t __n) {
         if (__libcpp_is_constant_evaluated()) {
             ::operator delete(const_cast<_Tp*>(__p));
         } else {
             _VSTD::__libcpp_deallocate((void*) const_cast<_Tp *>(__p), __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
         }
     }

libcxx/include/__split_buffer

 {
     __end_ = __new_last;
 }
 
 template <class _Tp, class _Allocator>
 __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
     : __end_cap_(nullptr, __a)
 {
-    __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr;
+    if (__cap == 0) {
+        __first_ = nullptr;
+    } else {
+        auto __allocation = std::__allocate_at_least(__alloc(), __cap);
+        __first_ = __allocation.ptr;
+        __cap = __allocation.count;
+    }
     __begin_ = __end_ = __first_ + __start;
     __end_cap() = __first_ + __cap;
 }
 
 template <class _Tp, class _Allocator>
 inline
 __split_buffer<_Tp, _Allocator>::__split_buffer()
     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
if (__a == __c.__alloc())
         __end_cap() = __c.__end_cap();
         __c.__first_ = nullptr;
         __c.__begin_ = nullptr;
         __c.__end_ = nullptr;
         __c.__end_cap() = nullptr;
     }
     else
     {
-        size_type __cap = __c.size();
-        __first_ = __alloc_traits::allocate(__alloc(), __cap);
+        auto __allocation = std::__allocate_at_least(__alloc(), __c.size());
+        __first_ = __allocation.ptr;
         __begin_ = __end_ = __first_;
-        __end_cap() = __first_ + __cap;
+        __end_cap() = __first_ + __allocation.count;
         typedef move_iterator<iterator> _Ip;
         __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
     }
 }
 
 template <class _Tp, class _Allocator>
 __split_buffer<_Tp, _Allocator>&
 __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)

libcxx/include/memory

struct allocator_traits
 
     template <class T>
     static void destroy(allocator_type& a, T* p); // constexpr in C++20
 
     static size_type max_size(const allocator_type& a); // noexcept in C++14, constexpr in C++20
     static allocator_type select_on_container_copy_construction(const allocator_type& a); // constexpr in C++20
 };
 
+template<class Pointer>
+struct allocation_result {
+    Pointer ptr;
+    size_t count;
+};
+
+template<class Allocator>
+[[nodiscard]] constexpr allocation_result<typename allocator_traits<Allocator>::pointer>
+    allocate_at_least(Allocator& a, size_t n);
+
 template <>
 class allocator<void> // removed in C++20
 {
 public:
     typedef void*                                 pointer;
     typedef const void*                           const_pointer;
     typedef void                                  value_type;
 

 void* align(size_t alignment, size_t size, void*& ptr, size_t& space);
 
 }  // std
 
 */
 
 #include <__config>
 #include <__memory/addressof.h>
+#include <__memory/allocate_at_least.h>
 #include <__memory/allocation_guard.h>
 #include <__memory/allocator.h>
 #include <__memory/allocator_arg_t.h>
 #include <__memory/allocator_traits.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/concepts.h>
 #include <__memory/construct_at.h>
 #include <__memory/pointer_traits.h>

libcxx/include/module.modulemap

module map {
     export *
   }
   module memory {
     header "memory"
     export *
 
     module __memory {
       module addressof                       { private header "__memory/addressof.h" }
+      module allocate_at_least               { private header "__memory/allocate_at_least.h" }
       module allocation_guard                { private header "__memory/allocation_guard.h" }
       module allocator                       { private header "__memory/allocator.h" }
       module allocator_arg_t                 { private header "__memory/allocator_arg_t.h" }
       module allocator_traits                { private header "__memory/allocator_traits.h" }
       module auto_ptr                        { private header "__memory/auto_ptr.h" }
       module compressed_pair                 { private header "__memory/compressed_pair.h" }
       module concepts                        { private header "__memory/concepts.h" }
       module construct_at                    { private header "__memory/construct_at.h" }

libcxx/include/string

 #include <__algorithm/min.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_if.h>
 #include <__assert>
 #include <__config>
 #include <__debug>
 #include <__ios/fpos.h>
 #include <__iterator/wrap_iter.h>
+#include <__memory/allocate_at_least.h>
 #include <__utility/auto_cast.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <compare>
 #include <cstdio>  // EOF
 #include <cstdlib>
 #include <cstring>
 #include <initializer_list>
void __copy_assign_alloc(const basic_string& __str, true_type)
                 if (!__str.__is_long())
                 {
                     __clear_and_shrink();
                     __alloc() = __str.__alloc();
                 }
                 else
                 {
                     allocator_type __a = __str.__alloc();
-                    pointer __p = __alloc_traits::allocate(__a, __str.__get_long_cap());
+                    auto __allocation = std::__allocate_at_least(__a, __str.__get_long_cap());
                     __clear_and_shrink();
                     __alloc() = _VSTD::move(__a);
-                    __set_long_pointer(__p);
-                    __set_long_cap(__str.__get_long_cap());
+                    __set_long_pointer(__allocation.ptr);
+                    __set_long_cap(__allocation.count);
                     __set_long_size(__str.size());
                 }
             }
         }
 
     _LIBCPP_INLINE_VISIBILITY
     void __copy_assign_alloc(const basic_string&, false_type) _NOEXCEPT
         {}
void basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s,
     pointer __p;
     if (__fits_in_sso(__reserve))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
-        size_type __cap = __recommend(__reserve);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__reserve) + 1);
+        __p = __allocation.ptr;
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__allocation.count);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
 {
     if (__sz > max_size())
         __throw_length_error();
     pointer __p;
     if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
-        size_type __cap = __recommend(__sz);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
+        __p = __allocation.ptr;
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__allocation.count);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 template <class>
void basic_string<_CharT, _Traits, _Allocator>::__init_copy_ctor_external(
     const value_type* __s, size_type __sz) {
   pointer __p;
   if (__fits_in_sso(__sz)) {
     __p = __get_short_pointer();
     __set_short_size(__sz);
   } else {
     if (__sz > max_size())
       __throw_length_error();
-    size_t __cap = __recommend(__sz);
-    __p = __alloc_traits::allocate(__alloc(), __cap + 1);
+    auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
+    __p = __allocation.ptr;
     __set_long_pointer(__p);
-    __set_long_cap(__cap + 1);
+    __set_long_cap(__allocation.count);
     __set_long_size(__sz);
   }
   traits_type::copy(_VSTD::__to_address(__p), __s, __sz + 1);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
     pointer __p;
     if (__fits_in_sso(__n))
     {
         __set_short_size(__n);
         __p = __get_short_pointer();
     }
     else
     {
-        size_type __cap = __recommend(__n);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__n) + 1);
+        __p = __allocation.ptr;
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__allocation.count);
         __set_long_size(__n);
     }
     traits_type::assign(_VSTD::__to_address(__p), __n, __c);
     traits_type::assign(__p[__n], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
     pointer __p;
     if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
-        size_type __cap = __recommend(__sz);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        auto __allocation = std::__allocate_at_least(__alloc(), __recommend(__sz) + 1);
+        __p = __allocation.ptr;
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__allocation.count);
         __set_long_size(__sz);
     }
 
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try
     {
 #endif  // _LIBCPP_NO_EXCEPTIONS
     for (; __first != __last; ++__first, (void) ++__p)

 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap - 1)
         __throw_length_error();
     pointer __old_p = __get_pointer();
     size_type __cap = __old_cap < __ms / 2 - __alignment ?
                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                           __ms - 1;
-    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
+    auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
+    pointer __p = __allocation.ptr;
     __invalidate_all_iterators();
     if (__n_copy != 0)
         traits_type::copy(_VSTD::__to_address(__p),
                           _VSTD::__to_address(__old_p), __n_copy);
     if (__n_add != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy, __p_new_stuff, __n_add);
     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
     if (__sec_cp_sz != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy + __n_add,
                           _VSTD::__to_address(__old_p) + __n_copy + __n_del, __sec_cp_sz);
     if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
-    __set_long_cap(__cap+1);
+    __set_long_cap(__allocation.count);
     __old_sz = __n_copy + __n_add + __sec_cp_sz;
     __set_long_size(__old_sz);
     traits_type::assign(__p[__old_sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                                      size_type __n_copy,  size_type __n_del,     size_type __n_add)
 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap)
         __throw_length_error();
     pointer __old_p = __get_pointer();
     size_type __cap = __old_cap < __ms / 2 - __alignment ?
                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                           __ms - 1;
-    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
+    auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
+    pointer __p = __allocation.ptr;
     __invalidate_all_iterators();
     if (__n_copy != 0)
         traits_type::copy(_VSTD::__to_address(__p),
                           _VSTD::__to_address(__old_p), __n_copy);
     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
     if (__sec_cp_sz != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy + __n_add,
                           _VSTD::__to_address(__old_p) + __n_copy + __n_del,
                           __sec_cp_sz);
     if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
-    __set_long_cap(__cap+1);
+    __set_long_cap(__allocation.count);
 }
 
 // assign
 
 template <class _CharT, class _Traits, class _Allocator>
 template <bool __is_short>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::__assign_no_alias(
basic_string<_CharT, _Traits, _Allocator>::__shrink_or_extend(size_type __target_capacity)
     {
         __was_long = true;
         __now_long = false;
         __new_data = __get_short_pointer();
         __p = __get_long_pointer();
     }
     else
     {
-        if (__target_capacity > __cap)
-            __new_data = __alloc_traits::allocate(__alloc(), __target_capacity+1);
+        if (__target_capacity > __cap) {
+            auto __allocation = std::__allocate_at_least(__alloc(), __target_capacity + 1);
+            __new_data = __allocation.ptr;
+            __target_capacity = __allocation.count - 1;
+        }
         else
         {
         #ifndef _LIBCPP_NO_EXCEPTIONS
             try
             {
         #endif // _LIBCPP_NO_EXCEPTIONS
-                __new_data = __alloc_traits::allocate(__alloc(), __target_capacity+1);
+                auto __allocation = std::__allocate_at_least(__alloc(), __target_capacity + 1);
+                __new_data = __allocation.ptr;
+                __target_capacity = __allocation.count - 1;
         #ifndef _LIBCPP_NO_EXCEPTIONS
             }
             catch (...)
             {
                 return;
             }
         #else  // _LIBCPP_NO_EXCEPTIONS
             if (__new_data == nullptr)

libcxx/include/vector

 #include <__algorithm/unwrap_iter.h>
 #include <__assert>
 #include <__bit_reference>
 #include <__config>
 #include <__debug>
 #include <__functional/hash.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/wrap_iter.h>
+#include <__memory/allocate_at_least.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <climits>
 #include <compare>
 #include <cstdlib>
 #include <cstring>

 private:
     pointer __begin_ = nullptr;
     pointer __end_ = nullptr;
     __compressed_pair<pointer, allocator_type> __end_cap_ =
         __compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag());
 
     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
     _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
-    void __vallocate(size_type __n);
+
+
+    //  Allocate space for __n objects
+    //  throws length_error if __n > max_size()
+    //  throws (probably bad_alloc) if memory run out
+    //  Precondition:  __begin_ == __end_ == __end_cap() == 0
+    //  Precondition:  __n > 0
+    //  Postcondition:  capacity() == __n
+    //  Postcondition:  size() == 0
+    void __vallocate(size_type __n) {
+        if (__n > max_size())
+            __throw_length_error();
+        auto __allocation = std::__allocate_at_least(__alloc(), __n);
+        __begin_ = __allocation.ptr;
+        __end_ = __allocation.ptr;
+        __end_cap() = __begin_ + __allocation.count;
+        __annotate_new(0);
+    }
+
     void __vdeallocate() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
     void __construct_at_end(size_type __n);
     _LIBCPP_INLINE_VISIBILITY
     void __construct_at_end(size_type __n, const_reference __x);
     template <class _ForwardIterator>
         typename enable_if
         <
vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
     __annotate_new(size());
     __invalidate_all_iterators();
     return __r;
 }
 
-//  Allocate space for __n objects
-//  throws length_error if __n > max_size()
-//  throws (probably bad_alloc) if memory run out
-//  Precondition:  __begin_ == __end_ == __end_cap() == 0
-//  Precondition:  __n > 0
-//  Postcondition:  capacity() == __n
-//  Postcondition:  size() == 0
-template <class _Tp, class _Allocator>
-void
-vector<_Tp, _Allocator>::__vallocate(size_type __n)
-{
-    if (__n > max_size())
-        this->__throw_length_error();
-    this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
-    this->__end_cap() = this->__begin_ + __n;
-    __annotate_new(0);
-}
-
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
 {
     if (this->__begin_ != nullptr)
     {
         clear();
         __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
void __throw_length_error() const {
         _VSTD::__throw_length_error("vector");
     }
 
     _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
     void __throw_out_of_range() const {
         _VSTD::__throw_out_of_range("vector");
     }
 
+    //  Allocate space for __n objects
+    //  throws length_error if __n > max_size()
+    //  throws (probably bad_alloc) if memory run out
+    //  Precondition:  __begin_ == __end_ == __cap() == 0
+    //  Precondition:  __n > 0
+    //  Postcondition:  capacity() == __n
+    //  Postcondition:  size() == 0
     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
-    void __vallocate(size_type __n);
+    void __vallocate(size_type __n) {
+        if (__n > max_size())
+            __throw_length_error();
+        auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n));
+        __begin_ = __allocation.ptr;
+        __size_ = 0;
+        __cap() = __allocation.count;
+    }
+
     void __vdeallocate() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     static size_type __align_it(size_type __new_size) _NOEXCEPT
         {return (__new_size + (__bits_per_word-1)) & ~((size_type)__bits_per_word-1);}
     _LIBCPP_INLINE_VISIBILITY  size_type __recommend(size_type __new_size) const;
     _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
     template <class _ForwardIterator>
         typename enable_if

 
 template <class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 vector<bool, _Allocator>::__invalidate_all_iterators()
 {
 }
 
-//  Allocate space for __n objects
-//  throws length_error if __n > max_size()
-//  throws (probably bad_alloc) if memory run out
-//  Precondition:  __begin_ == __end_ == __cap() == 0
-//  Precondition:  __n > 0
-//  Postcondition:  capacity() == __n
-//  Postcondition:  size() == 0
-template <class _Allocator>
-void
-vector<bool, _Allocator>::__vallocate(size_type __n)
-{
-    if (__n > max_size())
-        this->__throw_length_error();
-    __n = __external_cap_to_internal(__n);
-    this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
-    this->__size_ = 0;
-    this->__cap() = __n;
-}
-
 template <class _Allocator>
 void
 vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
 {
     if (this->__begin_ != nullptr)
     {
         __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
         __invalidate_all_iterators();

libcxx/include/version

 # define __cpp_lib_to_address                           201711L
 # define __cpp_lib_to_array                             201907L
 # define __cpp_lib_type_identity                        201806L
 # define __cpp_lib_unwrap_ref                           201811L
 #endif
 
 #if _LIBCPP_STD_VER > 20
 # define __cpp_lib_adaptor_iterator_pair_constructor    202106L
-// # define __cpp_lib_allocate_at_least                    202106L
+# define __cpp_lib_allocate_at_least                    202106L
 // # define __cpp_lib_associative_heterogeneous_erasure    202110L
 // # define __cpp_lib_bind_back                            202202L
 # define __cpp_lib_byteswap                             202110L
 // # define __cpp_lib_constexpr_cmath                      202202L
 // # define __cpp_lib_constexpr_typeinfo                   202106L
 // # define __cpp_lib_invoke_r                             202106L
 # define __cpp_lib_is_scoped_enum                       202011L
 # define __cpp_lib_monadic_optional                     202110L

libcxx/test/libcxx/diagnostics/detail.headers/memory/allocate_at_least.module.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__memory/allocate_at_least.h'}}
+#include <__memory/allocate_at_least.h>

libcxx/test/std/language.support/support.limits/support.limits.general/memory.version.pass.cpp

 
 # ifndef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should be defined in c++2b"
 # endif
 # if __cpp_lib_addressof_constexpr != 201603L
 #   error "__cpp_lib_addressof_constexpr should have the value 201603L in c++2b"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_allocate_at_least
-#     error "__cpp_lib_allocate_at_least should be defined in c++2b"
-#   endif
-#   if __cpp_lib_allocate_at_least != 202106L
-#     error "__cpp_lib_allocate_at_least should have the value 202106L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_allocate_at_least
-#     error "__cpp_lib_allocate_at_least should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_allocate_at_least
+#   error "__cpp_lib_allocate_at_least should be defined in c++2b"
+# endif
+# if __cpp_lib_allocate_at_least != 202106L
+#   error "__cpp_lib_allocate_at_least should have the value 202106L in c++2b"
+# endif
 
 # ifndef __cpp_lib_allocator_traits_is_always_equal
 #   error "__cpp_lib_allocator_traits_is_always_equal should be defined in c++2b"
 # endif
 # if __cpp_lib_allocator_traits_is_always_equal != 201411L
 #   error "__cpp_lib_allocator_traits_is_always_equal should have the value 201411L in c++2b"
 # endif
 

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp

 
 # ifndef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should be defined in c++2b"
 # endif
 # if __cpp_lib_addressof_constexpr != 201603L
 #   error "__cpp_lib_addressof_constexpr should have the value 201603L in c++2b"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_allocate_at_least
-#     error "__cpp_lib_allocate_at_least should be defined in c++2b"
-#   endif
-#   if __cpp_lib_allocate_at_least != 202106L
-#     error "__cpp_lib_allocate_at_least should have the value 202106L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_allocate_at_least
-#     error "__cpp_lib_allocate_at_least should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_allocate_at_least
+#   error "__cpp_lib_allocate_at_least should be defined in c++2b"
+# endif
+# if __cpp_lib_allocate_at_least != 202106L
+#   error "__cpp_lib_allocate_at_least should have the value 202106L in c++2b"
+# endif
 
 # ifndef __cpp_lib_allocator_traits_is_always_equal
 #   error "__cpp_lib_allocator_traits_is_always_equal should be defined in c++2b"
 # endif
 # if __cpp_lib_allocator_traits_is_always_equal != 201411L
 #   error "__cpp_lib_allocator_traits_is_always_equal should have the value 201411L in c++2b"
 # endif
 

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <memory>
+
+// template<class Allocator>
+// [[nodiscard]] constexpr allocation_result<typename allocator_traits<Allocator>::pointer>
+//   allocate_at_least(Allocator& a, size_t n);
+
+#include <cassert>
+#include <memory>
+
+template <class T>
+struct no_allocate_at_least {
+  using value_type = T;
+  T t;
+
+  constexpr T* allocate(size_t) { return &t; }
+  constexpr void deallocate(T*, size_t) {}
+};
+
+template <class T>
+struct has_allocate_at_least {
+  using value_type = T;
+  T t1;
+  T t2;
+
+  constexpr T* allocate(size_t) { return &t1; }
+  constexpr void deallocate(T*, size_t) {}
+  constexpr std::allocation_result<T*> allocate_at_least(size_t) {
+    return {&t2, 2};
+  }
+};
+
+constexpr bool test() {
+  { // check that std::allocate_at_least forwards to allocator::allocate if no allocate_at_least exists
+    no_allocate_at_least<int> alloc;
+    std::same_as<std::allocation_result<int*>> decltype(auto) ret = std::allocate_at_least(alloc, 1);
+    assert(ret.count == 1);
+    assert(ret.ptr == &alloc.t);
+  }
+
+  { // check that std::allocate_at_least forwards to allocator::allocate_at_least if allocate_at_least exists
+    has_allocate_at_least<int> alloc;
+    std::same_as<std::allocation_result<int*>> decltype(auto) ret = std::allocate_at_least(alloc, 1);
+    assert(ret.count == 2);
+    assert(ret.ptr == &alloc.t2);
+  }
+
+  { // check that std::allocator::allocate_at_least works
+    std::allocator<int> alloc;
+    auto allocation = alloc.allocate_at_least(1);
+    assert(allocation.count >= 1);
+    assert(allocation.ptr != nullptr);
+    alloc.deallocate(allocation.ptr, allocation.count);
+  }
+
+  return true;
+}
+
+int main() {
+  test();
+  static_assert(test());
+}

libcxx/utils/generate_feature_test_macro_components.py

feature_test_macros = [ add_version_header(x) for x in [
   }, {
     "name": "__cpp_lib_addressof_constexpr",
     "values": { "c++17": 201603 },
     "headers": ["memory"],
   }, {
     "name": "__cpp_lib_allocate_at_least",
     "values": { "c++2b": 202106 },
     "headers": ["memory"],
-    "unimplemented": True,
   }, {
     "name": "__cpp_lib_allocator_traits_is_always_equal",
     "values": { "c++17": 201411 },
     "headers": ["deque", "forward_list", "list", "map", "memory", "scoped_allocator", "set", "string", "unordered_map", "unordered_set", "vector"],
   }, {
     "name": "__cpp_lib_any",
     "values": { "c++17": 201606 },
     "headers": ["any"],