Correctly reusing storage of a union member and casting the involved pointers (object pool)

Question

I'm trying to write a C++20 standard conforming object pool that relies on the new wording around the object model that eliminates some undefined behaviour. The comments show the paragraph of the standard draft that I used for my reasoning (https://timsong-cpp.github.io/cppwp/n4861).

On creation the pool allocates storage for a fixed number of objects and manages a freelist inside the unused storage. For now I assume that the type T has no const or reference non-static members.

#include <iostream>
#include <stdexcept>
#include <type_traits>

template <typename T>
class ObjectPool {
public:
    using value_type = T;

    ObjectPool(std::ptrdiff_t capacity) :
        m_capacity(capacity),
        m_nodes(
            // Cast the result pointer back to Node* (https://timsong-cpp.github.io/cppwp/n4861/expr.static.cast#13)
            static_cast<Node*>(
                /*
                Implicitly creates (https://timsong-cpp.github.io/cppwp/n4861/basic.memobj#intro.object-10 and https://timsong-cpp.github.io/cppwp/n4861/basic.memobj#intro.object-13):
                    * the Node[capacity] array
                    * the Node union objects
                    * the Node* member subobjects

                Returns a pointer to the array casted to void* (https://timsong-cpp.github.io/cppwp/n4861/basic.memobj#intro.object-11)
                */
                operator new(capacity * sizeof(Node))
            )
        )
    {
        /*
        The implicit creations happen because it makes the following code defined behaviour.
        Otherwise it would be UB because:
            * Pointer arithmetic without them pointing to elements of an Node[capacity] array (https://timsong-cpp.github.io/cppwp/n4861/expr.add#4)
            * Accessing Node objects through 'pointer to object' pointers outside their lifetime (https://timsong-cpp.github.io/cppwp/n4861/basic.life#6.2).
            * Accessing the Node* subobjects through 'pointer to object' pointers outside their lifetime.
        */

        // Add all nodes to the freelist.
        Node* next = nullptr;
        for (std::ptrdiff_t i = m_capacity - 1; i >= 0; --i) {
            m_nodes[i].next = next;
            next = &m_nodes[i];
        }
        m_root = next;
    }

    ~ObjectPool()
    {
        /*
        Release the allocated storage.
        This ends the lifetime of all objects (array, Node, Node*, T) (https://timsong-cpp.github.io/cppwp/n4861/basic.life#1.5).
        */
        operator delete(m_nodes);
    }

    template <typename... Args>
    T* create(Args&&... args)
    {
        // freelist is empty
        if (!m_root) throw std::bad_alloc();

        Node* new_root = m_root->next;

        /*
        Activate the 'storage' member (https://timsong-cpp.github.io/cppwp/n4861/class.union#7).
        Is this strictly necessary?
        */
        new(&m_root->storage) Storage;

        /*
        Create a T object in the storage of the std::aligned_storage object (https://timsong-cpp.github.io/cppwp/n4861/basic.memobj#intro.object-1).

        This ends the lifetime of the std::aligned_storage object (https://timsong-cpp.github.io/cppwp/n4861/basic.life#1.5)?
        Because std::aligned_storage is most likley implemented with a unsigned char[N] array (https://timsong-cpp.github.io/cppwp/n4861/meta.trans.other#1),
        it 'provides storage' (https://timsong-cpp.github.io/cppwp/n4861/intro.object#3)
        for the T object and so the T object is 'nested within' (https://timsong-cpp.github.io/cppwp/n4861/intro.object#4.2) the std::aligned_storage
        which does not end its lifetime.
        This means without knowing the implementation of std::aligned_storage I don't know if the lifetime has ended or not?

        The union object is still in it's lifetime? The T object is 'nested within' the union object because it is
        'nested within' the member subobject 'storage' because that 'provides storage' (https://timsong-cpp.github.io/cppwp/n4861/intro.object#4.3).

        The union has no active members (https://timsong-cpp.github.io/cppwp/n4861/class.union#2).
        */
        T* obj = new(&m_root->storage) T{std::forward<Args>(args)...};

        m_root = new_root;
        return obj;
    }

    void destroy(T* obj)
    {
        /* Destroy the T object, ending it's lifetime (https://timsong-cpp.github.io/cppwp/n4861/basic.life#5). */
        obj->~T();

        /* if std::aligned_storage is in its lifetime.

        T represents the first byte of storage and is usable in limited ways (https://timsong-cpp.github.io/cppwp/n4861/basic.life#6).
        The storage pointer points to the std::aligned_storage object (https://timsong-cpp.github.io/cppwp/n4861/expr.reinterpret.cast#7 and https://timsong-cpp.github.io/cppwp/n4861/expr.static.cast#13).

        I'm not sure is std::launder() is necessary here because we did not create a new object.

        Storage* storage = reinterpret_cast<Node*>(storage);
        */

        /* if std::aligned_storage is not in its lifetime.

        Create a std::aligned_storage object in the storage of the former T object (https://timsong-cpp.github.io/cppwp/n4861/basic.memobj#intro.object-1).

        This activates the 'storage' member of the corresponding union (https://timsong-cpp.github.io/cppwp/n4861/class.union#2).
        */
        Storage* storage = new(obj) Storage;

        /*
        Get a pointer to the union from a pointer to a member (https://timsong-cpp.github.io/cppwp/n4861/basic.compound#4.2).
        */
        Node* node = reinterpret_cast<Node*>(storage);

        /*
        Activate the 'next' member creating the corresponding subobject (https://timsong-cpp.github.io/cppwp/n4861/class.union#6),
        the lifetime of the 'storage' subobject ends.
        */
        node->next = m_root;
        m_root = node;
    }

    std::ptrdiff_t capacity() const
    {
        return m_capacity;
    }
private:
    using Storage = typename std::aligned_storage<sizeof(T), alignof(T)>::type;

    union Node {
        Node* next;
        Storage storage;
    };
    std::ptrdiff_t m_capacity;
    Node* m_nodes;
    Node* m_root;
};

struct Block {
    long a;
    std::string b;
};

int main(int, char **)
{
    ObjectPool<Block> pool(10);

    Block* ptrs[10];
    for (int i = 0; i < 10; ++i) {
        ptrs[i] = pool.create(i, std::to_string(i*17));
    }
    std::cout << "Destroying objects\n";
    for (int i = 0; i < 10; ++i) {
        std::cout << ptrs[i]->a << " " << ptrs[i]->b << "\n";
        pool.destroy(ptrs[i]);
    }
    return 0;
}

My biggest problem is to understand what I have to do to transform the T* pointer in the destroy(T*) function into a Node* pointer to a usable Node object so can can add it to the freelist?

What I also don't understand how objects and subobjects work if they use the exact same storage area (union and their members) and I reuse the storage of a member. The subobjects (member) lifetime ends but does the parent object (union) stay in its lifetime despite all of its storage is reused?

Answer 1

The way you're going about this is unnecessarily overdesigned. It can still work, but the specific changes you're talking about with regard to implicit object creation (IOC) are unrelated to your code, for the most part. Or rather, you can do what you're attempting without relying on IOC (and thus write code that functions under C++17).

So let's start from the beginning: your memory allocation.

You allocate a bunch of memory. But your goal is to allocate an array of Nodes. So... just do that. Just invoke new Node[capacity] instead of allocating unformed memory. There's no point in relying on IOC to solve a problem you can trivially solve yourself (and it can be argued that the result is much more readable as to what is going on).

So, after allocating the array, you put a bunch of values into it. You do this by using the next member of the Node union. This works because the first member of a union is always active upon creation (unless you do something special). So all Node objects have the next member active.

Now, let's move on to the creation of T. You want to activate Node::storage. Placement new works in this case, but you'll still need it even with IOC. That is, IOC does not change the rules of unions. A union member can only implicitly be activated by an assignment to the named member. And you're not trying to do that; you're only going to use its address. So you still need the placement-new call to activate the member.

You then use placement-new to create the T itself within storage. And now we get to talk about lifetime.

You cite [basic.life]/1.5 to suggest that once you do this, storage's lifetime ends. This is true, but it's only because you used aligned_storage_t.

Let's pretend that, instead of std::aligned_storage_t, you had used alignas(T) unsigned char[sizeof(T)] for the type of storage. That matters because byte arrays have special behavior.

If storage is so defined, then T is nested within storage. From [intro.object]/4.2, we see:

An object a is nested within another object b if:

...

• b provides storage for a, or

...

And from the previous paragraph, we learn:

If a complete object is created ([expr.new]) in storage associated with another object e of type “array of N unsigned char” or of type “array of N std​::​byte” ([cstddef.syn]), that array provides storage for the created object if:

• the lifetime of e has begun and not ended, and
• the storage for the new object fits entirely within e, and
• there is no smaller array object that satisfies these constraints.

And all of those would be true if you use a byte array, so storage would continue to exist even after creating a T within it.

If this sounds like a good reason to not use std::aligned_storage, that's because it is.

And since all of this is valid C++17, if you switch to an aligned byte array, you don't have to worry; storage will continue to be within its lifetime.

Now we come to deletion. Destroying the T is the first thing you need to do.

So you've got a pointer to the (just destroyed) object, but you need to get a pointer to the Node. That's a problem because... well, you don't have one. I mean, yes, the address of the T is the same address as that of storage, which is pointer-interconvertible with a pointer to the Node. But it's that first step in that process, from pointer-to-T to pointer-to-storage that's the problem; reinterpret_cast can't get you there.

But std::launder can. And you can go straight from the T* to the Node*, because both objects have the same address and the Node is within its lifetime.

Once you have a Node*, you can reactivate the next member of that object. And since you can do it by assignment, there's no need for placement-new. So most of the stuff in that function is unnecessary.

And yet again, this is perfectly valid for C++17. Even the implicit activation of a union member is standard C++17 (with slightly different rules, but the differences don't apply here).

---

So let's look at a valid, C++17 version of your code:

#include <cstddef>
#include <new>


template <typename T>
class ObjectPool {
public:
    using value_type = T;

    ObjectPool(std::ptrdiff_t capacity)
        : capacity_(capacity)
        , nodes_(new Node[capacity])
    {
        // Add all nodes to the freelist.
        Node* next = nullptr;
        for (std::ptrdiff_t i = capacity_ - 1; i >= 0; --i) {
            nodes_[i].next = next;
            next = &nodes_[i];
        }
        root_ = next;
    }

    ~ObjectPool()
    {
        delete[] nodes_;
    }

    template <typename... Args>
    T* create(Args&&... args)
    {
        // freelist is empty
        if (!root_) throw std::bad_alloc();

        auto *allocate = root_;
        root_ = root_->next;

        new(&allocate->storage) decltype(allocate->storage);

        //Note: not exception-safe.
        T* obj = new(&allocate->storage) T(std::forward<Args>(args)...);
        return obj;
    }

    void destroy(T* obj)
    {
        obj->~T();
        
        Node *free = std::launder(reinterpret_cast<Node*>(obj));
        
        free->next = root_;
        root_ = free;
    }

    std::ptrdiff_t capacity() const
    {
        return capacity_;
    }
    
private:
    union Node
    {
        Node* next;
        alignas(T) std::byte storage[sizeof(T)];
    };
    
    std::ptrdiff_t capacity_;
    Node* nodes_;
    Node* root_ = nullptr;
};