[libc++] LWG2070: Use Allocator construction for objects created with allocate_shared

[ldionne]

Summary

This patch updates allocate_shared to call allocator_traits::construct when creating the object held inside the shared_pointer, and allocator_traits::destroy when destroying it. This resolves the part of P0674R1 that was originally filed as LWG2070.

This change is landed separately from the rest of P0674R1 because it is incredibly tricky from an ABI perspective.

This is the reason why this change is so tricky, as explained in the code:

Prior to C++20 (or if the compiler doesn't support [[no_unique_address]]),
we use an implementation that performs EBO for both the allocator and the
object type stored in the `shared_ptr`. This is the original implementation
that has been used in libc++, and we must be ABI compatible with it.

Starting in C++20, P0674 requires us to use Allocator construction for
initializing the object type. That requirement rules out the use of the
EBO for the object type, since using the EBO implies that the base will be
initialized when the control block is initialized (and hence we can't do it
through Allocator construction). Hence, supporting P0674 requires changing
how we store the object type inside the control block, which we do while
being ABI compatible by using [[no_unique_address]].

To achieve ABI compatibility, this patch implements an ABI-compatible type equivalent to __compressed_pair, but where the data member is stored in a union, and hence available to be initialized via Allocator construction. The tricky part with this emulation is that it needs to be 100% ABI compatible with __compressed_pair, which means also emulating its drawbacks, such as the inability to elide storage for final classes.

Fixes https://llvm.org/PR41900
Supersedes https://llvm.org/D62760

[zoecarver]

libcxx/include/memory

4089

I don't think this works. We need to call allocator_traits<_Tp>::construct which requires us to have a pointer of type _Tp* which is why D62760 has to use __shared_ptr_pointer instead of __shared_ptr_emplace.

allocator_traits<_ControlBlockAllocator>::construct isn't sufficient, see the relevant part of the standard: https://eel.is/c++draft/util.smartptr.shared#create-7.5

[zoecarver]

This is my bad; I should have made this more clear or changed the order of the patches. One of the primary reasons I'm pushing on D62760 is because it adds __shared_ptr_aligned_block and the preliminary logic to use it. This is necessary to support array types in make_shared and allocate_shared, and I thought it would be easier if there was a separate patch to implement __shared_ptr_aligned_block.

That being said, make_shared and allocate_shared will have different overloads for array types, so if we can get away with using __shared_ptr_emplace in the non-array overloads, we should 100% try to do that to simplify the implementation (as is done in this patch).

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/util.smartptr.shared.create/allocate_shared_construct.pass.cpp

28

In either patch, it would probably be a good idea to move these into MyAllocator so we can make sure that the correct specialization is setting them.

[ldionne]

Update with a new approach entirely.

[ldionne]

Reupload as patch application failed

[ldionne]

Another approach, which Zoe thought about just now and told me on Slack, would be to implement the storage like this instead (untested, I just wrote this up):

struct _Storage {
    _LIBCPP_HIDE_FROM_ABI explicit _Storage(_Alloc&& __a) {
        ::new ((void*)__get_alloc()) _Alloc(_VSTD::move(__a));
    }
    _LIBCPP_HIDE_FROM_ABI ~_Storage() {
        __get_alloc()->~_Alloc();
    }
    _Alloc* __get_alloc() _NOEXCEPT { /* compute offset */ }
    _Tp* __get_elem() _NOEXCEPT { /* compute offset */ }
    char alignas(__compressed_pair<_Alloc, _Tp>) __blob_[sizeof(__compressed_pair<_Alloc, _Tp>)];
};

I think we'd be able to compute the offsets with a bit of help from the __compressed_pair, and then I'm pretty sure it would be valid to placement-new into the blob as we like. I'll explore this approach too to see what it gives - the benefit would be not needing [[no_unique_address]] and potentially simpler code.

[zoecarver]

Let me start by saying that I haven't spent a lot of time looking at it but I really like this implementation.

---

In D91201#2453425, @ldionne wrote:

Another approach, which Zoe thought about just now and told me on Slack, would be to implement the storage like this instead (untested, I just wrote this up):

struct _Storage {
    _LIBCPP_HIDE_FROM_ABI explicit _Storage(_Alloc&& __a) {
        ::new ((void*)__get_alloc()) _Alloc(_VSTD::move(__a));
    }
    _LIBCPP_HIDE_FROM_ABI ~_Storage() {
        __get_alloc()->~_Alloc();
    }
    _Alloc* __get_alloc() _NOEXCEPT { /* compute offset */ }
    _Tp* __get_elem() _NOEXCEPT { /* compute offset */ }
    char alignas(__compressed_pair<_Alloc, _Tp>) __blob_[sizeof(__compressed_pair<_Alloc, _Tp>)];
};

I think we'd be able to compute the offsets with a bit of help from the __compressed_pair, and then I'm pretty sure it would be valid to placement-new into the blob as we like. I'll explore this approach too to see what it gives - the benefit would be not needing [[no_unique_address]] and potentially simpler code.

If the approach I'm talking about is simpler in this patch, it might not be simpler in absolute terms. If we're going to implement _Storage anyway as a more general thing, I think this implementation makes a lot of sense.

I think the code snippet I quoted is kind of missing my point. Using aligned storage, or a union, or anything similar is a bit irrelevant to what I was trying to say. I was highlighting a good way to do the "compute offset" part. The fundamental problem that this patch is trying to solve is that we need a pointer to the second element of __data_ in __shared_ptr_emplace, and we need that pointer before __shared_ptr_emplace is initialized. One way to do that (which you implement in this patch) is to make the second member a union and take its address. Another solution (what I was proposing) is we could simply static cast a pointer to __data_ to the correct __compressed_pair_elem type. Because __compressed_pair inherits from both of its elements, this should Just Work™. The latter solution would require no changes to the layout of __shared_ptr_emplace (and depending on how you look at it, that might be positive).

libcxx/include/memory

3336

This reminds me that we should support/test move-only allocator types.

3359

Do we really need __tmp allocators everywhere?

3364

IMHO we should make _Storage a more general utility.

Also can you please static assert that the alignment and size is the same as an equivilant __compressed_pair.

3368

This class is a work of art :)

[ldionne]

Add static_assert

libcxx/include/memory

3359

We need this one because we destroy the original one when we call ~Storage(), and then we need to deallocate this using the allocator. So I really don't see a way to get around this.

3364

IMHO we should make _Storage a more general utility.

I think I agree, but I'd like to do that in a separate patch. Making it generic will add complexity, like the ability to skip initialization of either member, etc. I'd like to keep this change small because of the trickiness.

Also can you please static assert that the alignment and size is the same as an equivilant __compressed_pair.

Done.

3368

I'm not sure whether I want to say thank you or run away and hide :-). I guess the problem we're trying to solve is pretty terrible, but the solution isn't too bad.

[ldionne]

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/util.smartptr.shared.create/allocate_shared_construct.pass.cpp

28

I don't think we can, because the allocator is going to be rebound to allocate an unknown object (ie the shared pointer control block).

[zoecarver]

libcxx/include/memory

3373

The above comment got me thinking... why can't this be a default destructor?

[ldionne]

libcxx/include/memory

3373

Frankly, I was getting an error about the compiler being unable to generate a destructor because the type in the union is non trivial, and this stopped the error.

I imagine the compiler is saying: you have a union with a non-trivial destructor so I want you to write your cleanup explicitly if you need some. But I could be wrong.

[zoecarver]

This LGTM. Not only to fix the LWG issue, but this is a great cleanup to this part of the codebase. So, thanks Louis.

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/libcxx.control_block_layout.pass.cpp

38 ↗

(On Diff #312624)

Maybe this should be a libcxx test only? I see "libcxx" in the name, but maybe it should be moved to the "libcxx" test directory.

137 ↗

(On Diff #312624)

This test makes me feel really confident that there won't be any ABI issues. Thanks!

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/util.smartptr.shared.create/allocate_shared_construct.pass.cpp

28

Fair enough. Makes sense.

[ldionne]

Use alternative implementation that's much simpler than [[no_unique_address]].

[ldionne]

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/libcxx.control_block_layout.pass.cpp

38 ↗

(On Diff #312624)

It is a libc++ test only, since it has // REQUIRES: libc++. I've actually been thinking about not having separate directories for libcxx specific tests and other tests, since we have lit markup that can handle it.

I believe one of the reasons was to ease the life of MSVC and libstdc++ using our test suite, however they now run using lit and so they do have the features available.

[zoecarver]

libcxx/include/memory

3362

Alternatively, you could make __blob_ a std::aligned_storage.

3366

(This is a new comment, I'm not replying to an old comment, even though that's what it looks like.)

Isn't this UB? __blob_ is uninitialized when you call .first() on it in __get_alloc().

[ldionne]

libcxx/include/memory

3362

I used to love aligned_storage, and then I read http://open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1413r2.pdf. I'm not sure I agree entirely with the paper, but I've been moving away from the type since it seemed like there were efforts to deprecate it. I'm not sure where those efforts ended up, though.

3366

Yes, it is indeed UB (hopefully benign UB). I ran it through ubsan before updating the patch and it didn't complain, so I thought to myself "it's good enough". But you're entirely right, it *is* plain and simple UB.

The issue is that I haven't been able to find a way to implement it without that. Simply, what we want is this:

_Alloc* __get_alloc() _NOEXCEPT {
    std::ptrdiff_t __offset = _CompressedPair::__first_offset(); // how to compute this?
    _Alloc* __alloc = static_cast<_Alloc*>(&__blob_ + __offset);
    return __alloc;
}

I wasn't able to find an implementation that didn't actually require an object to be alive:

_LIBCPP_INLINE_VISIBILITY
static std::ptrdiff_t __first_offset() _NOEXCEPT {
    __compressed_pair __p; // also requires default-constructing, which doesn't work
    _T1 const* __first = _VSTD::addressof(__p.first());
    return static_cast<char const*>(__first) - static_cast<char const*>(&__p);
}

I tried something with offsetof inside __compressed_pair_elem, but I couldn't compute the offset of the second element of the compressed pair. I don't know whether it's impossible or whether I'm just not imaginative enough. If we can't think of something, I can go back to the no_unique_address implementation (it's just a bit more complicated, but it's correct AFAICT).

[zoecarver]

libcxx/include/memory

3366

I actually really liked the no_unique_address implementation. And I think at this point we only support (or should only support) compiler that have implemented no_unique_address all the way back to C++03.

That being said, there is a way to do what you're thinking. We discussed this earlier, but I don't think I did a good job explaining. Basically, here's the idea: __compressed_pair *always* inherits from two __compressed_pair_elems. Always. We can simply static_cast a __compressed_pair pointer to both of it's base classes. That will give you two pointers which you can use to do placement new on both members.

(I think that might still technically be UB, because you never actually construct the object, but it seems like better UB then calling a member on an uninitialized object, which seems fairly dangerous IMHO.)

[zoecarver]

libcxx/include/memory

3366

Here's a pseudo-code example:

_Alloc* __get_alloc() _NOEXCEPT {
    _CompressedPair *__as_pair = reinterpret_cast<_CompressedPair*>(__blob_);
    _CompressedPair::_Base1* __first = static_cast<_CompressedPair::_Base1*>(__as_pair);
    _Alloc *__alloc = reinterpret_cast<_Alloc*>(__first);
    return __alloc;
}

[ldionne]

Remove UB!

libcxx/include/memory

3366

Hmm, that's clever, and actually very simple. Do you agree to go forward with that implementation, then?

Working with you is very humbling :-).

[zoecarver]

This looks great. Thanks for spending so much time iterating on this patch!

libcxx/include/memory

3362

The reason I liked using it in libc++ is that it works in C++03 mode (and alignas / alignof didn't use to). But now that we don't need to use it, I'm on board with moving away.

Thanks for the paper link :)

3366

Yes, I'm happy to go forward with that.

Thanks, you're too kind :)

[ldionne]

CI is passing, I'm going to ship this.

[curdeius]

@ldionne, shouldn't the related bug be updated?
https://llvm.org/PR41900

[ldionne]

In D91201#2487683, @curdeius wrote:

@ldionne, shouldn't the related bug be updated?
https://llvm.org/PR41900

Yes, thanks for the reminder. Done now.

libcxx/include/memory

template <class ..._Args>
             :  __data_(__a, _Tp(_VSTD::forward<_Args>(__args)...)) {}
 #endif
 
 private:
     virtual void __on_zero_shared() _NOEXCEPT;
     virtual void __on_zero_shared_weak() _NOEXCEPT;
 public:
     _LIBCPP_INLINE_VISIBILITY
     _Alloc& __get_alloc() _NOEXCEPT {return __data_.first();}
     _LIBCPP_INLINE_VISIBILITY
     _Tp* __get_elem() _NOEXCEPT {return _VSTD::addressof(__data_.second());}
 };
 
 template <class _Tp, class _Alloc>
 void
 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared() _NOEXCEPT
 {
+#if _LIBCPP_STD_VER > 17
+    typedef typename __allocator_traits_rebind<_Alloc, _Tp>::type _TpAllocator;
+    _TpAllocator __alloc(__get_alloc());
+    allocator_traits<_TpAllocator>::destroy(__alloc, __get_elem());
+#else
     __get_elem()->~_Tp();
+#endif
 }
 
 template <class _Tp, class _Alloc>
 void
 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
 {
     typedef typename __allocator_traits_rebind<_Alloc, __shared_ptr_emplace>::type _Al;
     typedef allocator_traits<_Al> _ATraits;
     typedef pointer_traits<typename _ATraits::pointer> _PTraits;
     _Al __a(__get_alloc());
     __get_alloc().~_Alloc();
     __a.deallocate(_PTraits::pointer_to(*this), 1);
 }
 
 struct __shared_ptr_dummy_rebind_allocator_type;
 template <>
 class _LIBCPP_TEMPLATE_VIS allocator<__shared_ptr_dummy_rebind_allocator_type>
 {
 public:
     template <class _Other>
     struct rebind
     {
         typedef allocator<_Other> other;
     };
 };
 
 template<class _Tp> class _LIBCPP_TEMPLATE_VIS enable_shared_from_this;
 
 template<class _Tp, class _Up>
 struct __compatible_with
make_shared(_Args&& ...__args)
     _A2 __a2;
     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
     ::new(__hold2.get()) _CntrlBlk(__a2, _VSTD::forward<_Args>(__args)...);
 
     _Tp *__ptr = __hold2->__get_elem();
     return shared_ptr<_Tp>::__create_with_control_block(__ptr, __hold2.release());
 }
 
-template<class _Tp, class _Alloc, class ..._Args>
-inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    !is_array<_Tp>::value,
-    shared_ptr<_Tp>
->::type
-allocate_shared(const _Alloc& __a, _Args&& ...__args)
+template<class _Tp, class _Alloc, class ..._Args, class = _EnableIf<!is_array<_Tp>::value> >
+_LIBCPP_INLINE_VISIBILITY
+shared_ptr<_Tp> allocate_shared(const _Alloc& __a, _Args&& ...__args)
 {
-    static_assert( is_constructible<_Tp, _Args...>::value, "Can't construct object in allocate_shared");
+    typedef __shared_ptr_emplace<_Tp, _Alloc> _ControlBlock;
+    typedef typename __allocator_traits_rebind<_Alloc, _ControlBlock>::type _ControlBlockAllocator;
+    typedef __allocator_destructor<_ControlBlockAllocator> _GuardDeleter;
 
-    typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
-    typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
-    typedef __allocator_destructor<_A2> _D2;
+    _ControlBlockAllocator __cb_alloc(__a);
+    unique_ptr<_ControlBlock, _GuardDeleter> __guard(__cb_alloc.allocate(1), _GuardDeleter(__cb_alloc, 1));
 
-    _A2 __a2(__a);
-    unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
-    ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
-        _CntrlBlk(__a, _VSTD::forward<_Args>(__args)...);
+#if _LIBCPP_STD_VER > 17
+    allocator_traits<_ControlBlockAllocator>::construct(__cb_alloc, _VSTD::addressof(*__guard.get()), __a, _VSTD::forward<_Args>(__args)...);
+#else
+    ::new(static_cast<void*>(_VSTD::addressof(*__guard.get()))) _ControlBlock(__a, _VSTD::forward<_Args>(__args)...);
+#endif
 
-    typename shared_ptr<_Tp>::element_type *__p = __hold2->__get_elem();
-    return shared_ptr<_Tp>::__create_with_control_block(__p, _VSTD::addressof(*__hold2.release()));
+    typename shared_ptr<_Tp>::element_type *__p = __guard->__get_elem();
+    return shared_ptr<_Tp>::__create_with_control_block(__p, _VSTD::addressof(*__guard.release()));
 }
 
 template<class _Tp, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
 {
     return __x.get() == __y.get();

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/util.smartptr.shared.create/allocate_shared.pass.cpp

struct Three
     int value;
     Three(int v, int, int) : value(v) {++count;}
     Three(Three const & o) : value(o.value) {++count;}
     ~Three() {--count;}
 };
 
 int Three::count = 0;
 
+#if TEST_STD_VER < 20
+template<class T>
+struct AllocNoConstruct : std::allocator<T>
+{
+    AllocNoConstruct() = default;
+
+    template <class T1>
+    AllocNoConstruct(AllocNoConstruct<T1>) {}
+
+    template <class T1>
+    struct rebind {
+        typedef AllocNoConstruct<T1> other;
+    };
+
+    void construct(void*) { assert(false); }
+};
+#endif // TEST_STD_VER < 20
+
 template <class Alloc>
 void test()
 {
     int const bad = -1;
     {
     std::shared_ptr<Zero> p = std::allocate_shared<Zero>(Alloc());
     assert(Zero::count == 1);
     }
int main(int, char**)
     char c = 'f';
     std::shared_ptr<A> p = std::allocate_shared<A>(bare_allocator<void>(), i, c);
     assert(A::count == 1);
     assert(p->get_int() == 68);
     assert(p->get_char() == 'f');
     }
     assert(A::count == 0);
 
+    // Test that we don't call construct before C++20.
+#if TEST_STD_VER < 20
+    {
+    (void)std::allocate_shared<int>(AllocNoConstruct<int>());
+    }
+#endif // TEST_STD_VER < 20
+
   return 0;
 }

libcxx/test/std/utilities/memory/util.smartptr/util.smartptr.shared/util.smartptr.shared.create/allocate_shared_construct.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
+
+// <memory>
+
+// shared_ptr
+
+// template<class T, class A, class... Args>
+//    shared_ptr<T> allocate_shared(const A& a, Args&&... args);
+
+// This patch tests that allocator_traits::construct is used in allocate_shared
+// as requested in C++20.
+
+#include "test_macros.h"
+
+#include <memory>
+#include <cassert>
+
+static bool construct_called = false;
+static bool destroy_called = false;
+static unsigned allocator_id = 0;
+
+template <class T>
+struct MyAllocator {
+public:
+  typedef T value_type;
+  typedef T* pointer;
+
+  unsigned id = 0;
+
+  MyAllocator() = default;
+  MyAllocator(int id) : id(id) {}
+
+  template <class U>
+  MyAllocator(MyAllocator<U> const& other) : id(other.id){};
+
+  pointer allocate(std::ptrdiff_t n) {
+    return pointer(static_cast<T*>(::operator new(n * sizeof(T))));
+  }
+
+  void deallocate(pointer p, std::ptrdiff_t) { return ::operator delete(p); }
+
+  template <typename ...Args>
+  void construct(T* p, Args&& ...args) {
+    construct_called = true;
+    destroy_called = false;
+    allocator_id = id;
+    ::new (p) T(std::forward<Args>(args)...);
+  }
+
+  void destroy(T* p) {
+    construct_called = false;
+    destroy_called = true;
+    allocator_id = id;
+    p->~T();
+  }
+};
+
+#if !defined(_LIBCPP_VERSION)
+struct Private;
+
+class Factory {
+public:
+  static std::shared_ptr<Private> allocate();
+};
+
+template <class T>
+struct FactoryAllocator;
+
+struct Private {
+  int id;
+
+private:
+  friend FactoryAllocator<Private>;
+  Private(int id) : id(id) {}
+  ~Private() {}
+};
+
+template <class T>
+struct FactoryAllocator : std::allocator<T> {
+  FactoryAllocator() = default;
+
+  template <class T1>
+  FactoryAllocator(FactoryAllocator<T1>) {}
+
+  template <class T1>
+  struct rebind {
+    typedef FactoryAllocator<T1> other;
+  };
+
+  void construct(void* p, int id) { ::new (p) Private(id); }
+  void destroy(Private* p) { p->~Private(); }
+};
+
+std::shared_ptr<Private> Factory::allocate() {
+  FactoryAllocator<Private> factory_alloc;
+  return std::allocate_shared<Private>(factory_alloc, 42);
+}
+#endif // !libc++
+
+struct mchar {
+  char c;
+};
+
+struct Foo {
+  int val;
+
+  Foo(int val) : val(val) {}
+
+  Foo(Foo a, Foo b) : val(a.val + b.val) {}
+};
+
+struct Bar {
+  std::max_align_t y;
+};
+
+void test_aligned(void* p, size_t align) {
+  assert(reinterpret_cast<uintptr_t>(p) % align == 0);
+}
+
+int main(int, char**) {
+  {
+    std::shared_ptr<int> p = std::allocate_shared<int>(MyAllocator<int>());
+    assert(construct_called);
+  }
+  assert(destroy_called);
+  {
+    std::shared_ptr<Foo> p =
+        std::allocate_shared<Foo>(MyAllocator<Foo>(), Foo(42), Foo(100));
+    assert(construct_called);
+    assert(p->val == 142);
+  }
+  assert(destroy_called);
+  { // Make sure allocator is copied.
+    std::shared_ptr<int> p = std::allocate_shared<int>(MyAllocator<int>(3));
+    assert(allocator_id == 3);
+
+    allocator_id = 0;
+  }
+  assert(allocator_id == 3);
+
+  {
+    std::shared_ptr<int> p = std::allocate_shared<int>(MyAllocator<int>(), 42);
+    assert(construct_called);
+    assert(*p == 42);
+  }
+  assert(destroy_called);
+
+  { // Make sure allocator is properly re-bound.
+    std::shared_ptr<int> p =
+        std::allocate_shared<int>(MyAllocator<mchar>(), 42);
+    assert(construct_called);
+    assert(*p == 42);
+  }
+  assert(destroy_called);
+
+  // TODO:
+  // Libc++ doesn't support this yet because we inherit from Private transitively
+  // when trying to do EBO. Test this once we move to using [[no_unique_address]].
+#if !defined(_LIBCPP_VERSION)
+  {
+    // Make sure that we call the correct allocator::construct. Private has a private constructor
+    // so the construct method must be called on its friend Factory's allocator
+    // (Factory::Allocator).
+    std::shared_ptr<Private> p = Factory().allocate();
+    assert(p->id == 42);
+  }
+#endif
+
+  {
+    std::shared_ptr<Bar> p;
+    test_aligned(p.get(), alignof(Bar));
+  }
+
+  return 0;
+}