<deque>: For allocators where allocator_traits<T>::pointer is an object, destructors aren't always called

[nicolasjinchereau]

When using a custom allocator that defines allocator_traits<T>::pointer as a class or struct, std::deque constructs more instances of that pointer object than it destroys. So if pointer has non-trivial constructors or destructors, some destructors will not be called.

> cl repro.cpp /std:c++latest

#include <type_traits>
#include <cstdio>
#include <cstdlib>
#include <compare>
#include <iterator>
#include <deque>

int numPtrs = 0;

template<class T>
class FancyPointer
{
    T* p{};

    template<class U>
    friend class FancyPointer;

    template<class U> requires std::is_convertible_v<U*, T*>
    FancyPointer(U* p)
        : FancyPointer()
    {
        this->p = p;
    }
    
    template<class U>
    friend class FancyAllocator;
public:
    
    using value_type = T;
    using pointer = FancyPointer<T>;
    using difference_type = ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;

    template<class U = T> requires (!std::is_void_v<U>)
    using reference = U&;

    FancyPointer() {
        ++numPtrs;
    }

    ~FancyPointer() {
        --numPtrs;
    }

    FancyPointer(const FancyPointer& fp)
        : FancyPointer()
    {
        p = fp.p;
    }

    FancyPointer(FancyPointer&& fp)
        : FancyPointer()
    {
        p = fp.p;
        fp.p = nullptr;
    }

    template<class U> requires std::is_convertible_v<U*, T*>
    FancyPointer(const FancyPointer<U>& fp)
        : FancyPointer()
    {
        p = fp.p;
    }

    FancyPointer(std::nullptr_t)
        : FancyPointer()
    {
        p = nullptr;
    }

    FancyPointer& operator=(const FancyPointer& fp) {
        p = fp.p;
        return *this;
    }

    template<class U> requires std::is_convertible_v<U*, T*>
    FancyPointer& operator=(const FancyPointer<U>& fp) {
        p = fp.p;
        return *this;
    }
    
    FancyPointer& operator=(FancyPointer&& fp) {
        p = fp.p;
        fp.p = nullptr;
        return *this;
    }

    FancyPointer& operator=(std::nullptr_t) {
        reset();
        return *this;
    }

    T* get() const {
        return p;
    }

    void reset() {
        p = nullptr;
    }

    explicit operator bool() const {
        return p != nullptr;
    }

    T* operator->() const {
        return p;
    }

    template<class U = T> requires (!std::is_void_v<U>)
    U& operator*() const {
        return *p;
    }

    template<class U = T> requires (!std::is_void_v<U>)
    U& operator[](ptrdiff_t index) const {
        return p[index];
    }

    FancyPointer& operator++() {
        ++p;
        return *this;
    }

    FancyPointer operator++(int) {
        auto tmp = *this;
        ++p;
        return tmp;
    }

    FancyPointer& operator--() {
        --p;
        return *this;
    }

    FancyPointer operator--(int) {
        auto tmp = *this;
        --p;
        return tmp;
    }

    FancyPointer& operator+=(ptrdiff_t off) {
        p += off;
        return *this;
    }

    FancyPointer& operator-=(ptrdiff_t off) {
        p -= off;
        return *this;
    }

    FancyPointer operator+(ptrdiff_t off) const {
        return { p + off };
    }

    FancyPointer operator-(ptrdiff_t off) const {
        return { p - off };
    }

    ptrdiff_t operator-(const FancyPointer& fp) const {
        return { p - fp.p };
    }

    template<class U> requires (!std::is_void_v<U> && std::is_same_v<U, T>)
    static FancyPointer<U> pointer_to(U& u) {
        return { &u };
    }

    template<class T2>
    bool operator==(const FancyPointer<T2>& right) const {
        return get() == right.get();
    }

    bool operator==(std::nullptr_t) const {
        return get() == nullptr;
    }

    template<class T2>
    std::strong_ordering operator<=>(const FancyPointer<T2>& right) {
        return get() <=> right.get();
    }

    std::strong_ordering operator<=>(std::nullptr_t) {
        return get() <=> nullptr;
    }
};

template <class T>
class FancyAllocator
{
public:
    using value_type = T;
    using pointer = FancyPointer<T>;
    using const_pointer = FancyPointer<const T>;
    using difference_type = ptrdiff_t;
    using size_type = std::size_t;

    template <class U>
    struct rebind {
        using other = FancyAllocator<U>;
    };

    FancyAllocator() {}
    ~FancyAllocator() {}

    template<class U>
    FancyAllocator(const FancyAllocator<U>& that) {}

    pointer allocate(size_type n) {
        void* p = ::operator new(n * sizeof(T), std::align_val_t(alignof(T)));
        return pointer{ static_cast<T*>(p) };
    }

    void deallocate(pointer fp, size_type n) {
        ::operator delete(fp.p, std::align_val_t(alignof(T)));
    }

    FancyAllocator select_on_container_copy_construction() const {
        return *this;
    }

    using propagate_on_container_copy_assignment = std::false_type;
    using propagate_on_container_move_assignment = std::true_type;
    using propagate_on_container_swap = std::true_type;
    using is_always_equal = std::true_type;
};

template <class T1, class T2>
inline bool operator==(const FancyAllocator<T1>& a, const FancyAllocator<T2>& b) noexcept {
    return true;
}

template <class T1, class T2>
inline bool operator!=(const FancyAllocator<T1>& a, const FancyAllocator<T2>& b) noexcept {
    return false;
}


int main(int argc, char* argv[])
{
    {
        std::deque<int, FancyAllocator<int>> stuff;
        stuff.push_back(1);
    }

    printf("FancyPointers (should be zero) : %d\n", numPtrs);
    return 0;
}

Results

FancyPointer has a counter in the constructor and destructor to count the number of live instances. After the deque has been destroyed, the counter should be zero, showing that all FancyPointer destructors have run correctly. However, the program outputs '7'. If std::deque in the above program is replaced with std::list or std::vector, the program will output '0' as expected.

STL version
Microsoft Visual Studio Enterprise 2022 (64-bit) - Preview
Version 17.3.0 Preview 1.1

[StephanTLavavej]

I believe that this is clearly a bug - thanks for the report! Over time, we overhauled vector etc. to respect fancy pointers, but we must have missed deque (which does fairly complicated things with its "map" of block pointers).

[MattStephanson]

I don't know how to properly solve it, but to save some debugging effort, I think this is at least one issue: all the block pointers in the map are constructed, even if they're empty, but are only destroyed if they're non-empty. The map size in this example is 8, so the pointer to the one used block gets destroyed and the other 7 don't.

STL/stl/inc/deque

Lines 1486 to 1495 in 17fde2c

	for (size_type _Block = _Mapsize(); 0 < _Block;) { // free storage for a block and destroy pointer
	if (_Map()[--_Block]) { // free block and destroy its pointer
	_Getal().deallocate(_Map()[_Block], _Block_size);
	_Destroy_in_place(_Map()[_Block]);
	}
	}
	if (_Map() != _Mapptr()) {
	_Almap.deallocate(_Map(), _Mapsize()); // free storage for map
	}

[CaseyCarter]

Do we want to fix this by ensuring that all pointers are constructed and destroyed via the allocator, or do we want to really fix it by never constructing nor destroying any pointers via the allocator as the Standard requires?

[MattStephanson]

Do we want to fix this by ensuring that all pointers are constructed and destroyed via the allocator, or do we want to really fix it by never constructing nor destroying any pointers via the allocator as the Standard requires?

The call to _Destroy_in_place isn't going through the allocator anyway. As I understand it, in at least some cases the deque's map must refer to the blocks using the allocator's fancy pointer type, and the issue here is that those fancy pointers aren't being destroyed at all.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting and we believe that it should be safe to fix this to follow the Standardese - we should use construct()/destroy() provided by the allocator (via allocator_traits) only for container elements, never other types. (As @MattStephanson mentioned, we already appear to be doing this correctly - @CaseyCarter thinks he might have led us astray here temporarily. 😹) For the fancy pointers, we should directly construct and destroy them in a balanced manner, regardless of their nullness.

[MattStephanson]

we should use construct()/destroy() provided by the allocator (via allocator_traits) only for container elements, never other types [...] (we already appear to be doing this correctly)

On that part @CaseyCarter is right (edit: right that there's a bug, I mean). I noticed during debugging that the allocator is also used for the map and the container proxy:

STL/stl/inc/deque

Lines 587 to 593 in 17fde2c

	using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
	using _Alty_traits = allocator_traits<_Alty>;
	using _Alpty = _Rebind_alloc_t<_Alloc, typename _Alty_traits::pointer>;
	using _Alpty_traits = allocator_traits<_Alpty>;
	using _Mapptr = typename _Alpty_traits::pointer;
	using _Alproxy_ty = _Rebind_alloc_t<_Alty, _Container_proxy>;
	using _Alproxy_traits = allocator_traits<_Alproxy_ty>;

STL/stl/inc/deque

Lines 1442 to 1455 in 17fde2c

	_Alpty _Almap(_Getal());
	size_type _Newsize = 0 < _Mapsize() ? _Mapsize() : 1;
	while (_Newsize - _Mapsize() < _Count || _Newsize < _Minimum_map_size) {
	// scale _Newsize to 2^N >= _Mapsize() + _Count
	if (max_size() / _Block_size - _Newsize < _Newsize) {
	_Xlen(); // result too long
	}
	_Newsize *= 2;
	}
	_Count = _Newsize - _Mapsize();
	size_type _Myboff = _Myoff() / _Block_size;
	_Mapptr _Newmap = _Almap.allocate(_Mapsize() + _Count);

etc.

[StephanTLavavej]

We need to allocate the map and the proxy with the user-provided allocator (as all persistent allocations must respect this) - it's construct() and destroy() that should be specific to the elements. (Allocators are weird.)

[MattStephanson]

Ah, I was pretty sure I was missing something. Thanks.