How to use STL-compliant allocators for heterogeneous memory allocations

Question

I'm trying to implement a class that's followed in memory by an array of some arbitrary type:

template<class T>
class Buf
{
    size_t n;
    int refs;
    explicit Buf(size_t n) : n(n) { }
    // other declarations are here as appropriate

    // Followed in memory by:
    // T items[n];
};

This would be easy with operator new:

template<class T>
Buf<T> *make_buf(size_t n)
{
    // Assume the caller will take care of constructing the array elements
    return new(operator new(sizeof(Buf<T>) + sizeof(T) * n)) Buf<T>(n);
}

template<class T>
void free_buf(Buf<T> *p)
{
    // Assume the caller has taken care of destroying the array elements
    p->~Buf<T>();
    return operator delete(p);
}

template<class T>
T *get_buf_array(Buf<T> *p)
{
    return reinterpret_cast<T *>(reinterpret_cast<char *>(p) + sizeof(Buf<T>));
}

But now, how do I implement this using some standard-compliant allocator SomeAllocator?

Is it guaranteed that SomeAllocator::rebind<char>::other::allocate will return memory suitably aligned for any type of object? If so, am I otherwise safe to just use an allocator of some char type? If not, do I have any alternatives, or is this task impossible with allocators in general? (In the worst case I suppose I could cast the pointers to uintptr_t and align them manually, but I'm wondering if there's a better way.)

Fiume

You can always ask for a little more memory and then use std::align... – Jac

@KerrekSB: Wow, nice. I didn't know that function exists... – Fiume

@KerrekSB: I guess the question remains though: what's the best approach, and is it necessary to call that function? Should I use an allocator of char, or an allocator of T? etc. – Fiume

It would have to be an allocator for char, since you don't actually have any type that you can allocate for - you just need the raw memory. (It should be std::allocator_traits<Alloc>::rebind_alloc<char>, though, and rebind_traits for the traits... and you need to call allocate through the traits and obtain a native pointer and all that.) – Jac

@KerrekSB: I was thinking more along the lines of using an allocator for Buf<T> and realigning the pointer for T, but I'm not sure if it'd have any advantage or disadvantage. – Fiume

An allocator for Buf<T> allocates in multiples of that type, so I don't think that would be useful. Sure, you could do some size computations, but at the very least you'd still need to align the address of the first array element somehow. – Jac

@KerrekSB: Yeah -- but don't I still have to align the address of the first array element even if I use a char allocator? I'm not seeing any immediate disadvantage (except perhaps a few extra elements allocated), and the advantage seems to be that I'd no longer need to align the pointer to get the address of the Buf<T> itself. – Fiume

You might find it convenient to declare an array of 1 element, or even 0 if you use GCC or another compiler with that non-Standard extension and don't care about portability - then you know that Buf and the element's alignment is taken care of - otherwise you need to get the max of their alignments. For the allocator... you could then rebind<Aligned_Allocator<std::alignment_of<Buf<T>>> where AlignedAllocator is specialised so <1> needs alignment 1 (e.g. contains one int8_t), <2> 2 etc.. – Mab

Answer 1

I was thinking the solution could be by creating a notional early array.

+-----------+
|Buf<T>     |
+-------+---+---+-------+-------+
|T[0]   | T[1]  |T[2]   |  T[3]...
+-------+-------+-------+-------+

With the non-overlapping T[2], T[3], ... being the required array of T.

template<class T>
class Buf
{
    size_t n;
    int refs;
    explicit Buf(size_t n) : n(n) { }
    // other declarations are here as appropriate

    // Followed in memory by:
    // T items[n];
};

The number of ruined elements would be :-

const size_t lead = ( sizeof(Buf<T>) + sizeof(T) - 1) / sizeof(T);

Finally the raw memory of i can be accessed by

(reinterpret_cast<T*>( this ) )[ i + lead ];

Haugen

Answer 2

I'm afraid you're making unwarranted assumptions about what the C++ standard requires. What you're trying to do may not be generically possible.

The default allocator (new or malloc) is required to return a pointer to a block of memory that is suitably aligned for any complete object type with a fundamental alignment requirement. The size must be at least as large as the requested size. Custom allocators have different requirements, depending on what they allocate. An allocator for one type is not guaranteed to return storage suitably aligned for another. Of course, if you are the one implementing a custom allocator, you can make sure it returns what you need.

The compiler is required to satisfy some constraints about memory layout, but it will not guarantee that something is placed in memory immediately after something else. There could be padding bytes insert to meet alignment requirements.

The recent C++ standards provide quite a bit of support for handling alignments. There is probably an answer for you in there somewhere. I suspect that underlying this are some requirements you haven't told us about. Perhaps there is another way to go about it.

Fauces

Answer 3

I think that standard compliant allocator you stl compliant? Since you don't require your allocator to be used with an stl data structure it is not really necessary to meet it's requirements even though you may as well do so as I think it is a neat way of doing it and in which case you may implement you buffer by using an std::vector with your custom stl style allocator as a template parameter. With regards to alignment guarantees of operator new and operator new[] I suggest you have a look at:

Is there any guarantee of alignment of address return by C++'s new operation?.

If your alignment concerns are for primitive types such as doubles etc. you are pretty much covered by std::align as you can see in http://en.cppreference.com/w/cpp/memory/align.

However if you have stranger/larger alignment requirements such as aligning every element to cache lines etc. or T is a type with a size where sizeof(T)mod alignment != 0 you may have problems when allocating arrays of T's. In such cases even if the first element of the array is aligned to meet the requirement it doesn't mean that all the subsequent elements will be aligned as well.

Sphygmoid

Answer 4

Constrain the alignment by rebinding the allocator to a specialization of std::aligned_storage.

typedef std::aligned_storage_t< 1, std::max( alignof (Buf<T>), alignof (T) ) >
        unit_type; // lowest-common-denominator type for aligned allocation

std::size_t unit_count // number of unit_type array elements needed
    = ( sizeof (Buf<T>) + sizeof (T) * n // = actual used storage
           + sizeof (unit_type) - 1 )    //   + alignment padding
      / sizeof (unit_type);              // divided by element size

typedef typename std::allocator_traits< SomeAllocator >::rebind_alloc< unit_type >
        rebound;

rebound a( alloc_parm ); // Retain this somewhere if statefulness is allowed.
ptr = std::allocator_traits< rebound >::allocate( a, unit_count );

(Remember, all allocator access goes through allocator_traits!)

Refuge