Custom allocator problems

Does anyone know if the requirements have changed for writing custom allocators with C++ 0x11?

A custom allocator (that uses a fixed array as its memory pool) that I have been using successfully for some time, now throws an exception!

It runs fine under VS2008 but bombs out with VS2010.

While I don't think the requirements have been changed, there is now an allocator_traits which you are supposed to use, rather than calling the allocator directly. How this affects existing code though... I'm not sure.

Theory says that changes to C++11 shouldn't break existing C++ code...

It appears to get upset whilst traversing a linked list, where it comes across an unititialised pointer.

Code:

---

        // MEMBER FUNCTIONS FOR _Container_base12
inline void _Container_base12::_Orphan_all()
    {    // orphan all iterators
 #if _ITERATOR_DEBUG_LEVEL == 2
    if (_Myproxy != 0)
        {    // proxy allocated, drain it
        _Lockit _Lock(_LOCK_DEBUG);

        for (_Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;
            *_Pnext != 0; *_Pnext = (*_Pnext)->_Mynextiter)
            (*_Pnext)->_Myproxy = 0;
        _Myproxy->_Myfirstiter = 0; <<<< Here
        }
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
    }

---

In this case, the allocator has been applied to a std::vector. The exception occurs when calling 'reserve'.

Code:

---

vector<int, ArrayAllocator<int, 10>> test;

int main()
{
    test.reserve(2);
}

---

I'll give allocator_traits a look.

I don't seem to be able to get to the bottom of this yet.

Here's a demo that compiles correctly with both VS2008 & VS2010, but exceptions under VS2010.

The allocator shown is a simplified version which only works with items that have a trivial destructor.

All of the tests should print 'true'.

Code:

---

#include <vector>
#include <iostream>

using namespace std;

template <typename T, const size_t MAX_SIZE>
class ArrayAllocator
{
public:
    typedef T                value_type;
    typedef value_type*      pointer;
    typedef const value_type* const_pointer;
    typedef value_type&      reference;
    typedef const value_type& const_reference;
    typedef size_t            size_type;
    typedef std::ptrdiff_t    difference_type;

    //*********************************************************************
    template <typename U>
    struct rebind
    {
        typedef ArrayAllocator<U, MAX_SIZE> other;
    };

    //*********************************************************************
    ArrayAllocator()
    {
    }

    //*********************************************************************
    ArrayAllocator(const ArrayAllocator &rhs)
    {
        std::copy(rhs.buffer, rhs.buffer + MAX_SIZE, buffer);
    }

    //*********************************************************************
    template <typename U>
    ArrayAllocator(const ArrayAllocator<U, MAX_SIZE> &rhs)
    {
    }

    //*********************************************************************
    pointer address(reference x) const
    {
        return (&x);
    }

    //*********************************************************************
    const_pointer address(const_reference x) const
    {
        return (x);
    }

    //*********************************************************************
    pointer allocate(size_type    n,
                    const_pointer cp = 0)
    {
        // Too big?
        if (n > MAX_SIZE)
        {
            throw std::bad_alloc();
        }

        // Return the beginning of the buffer.
        return buffer;
    }

    //*********************************************************************
    void deallocate(pointer  p,
                    size_type n)
    {
    }

    //*********************************************************************
    size_type max_size() const
    {
        return (MAX_SIZE);
    }

    //*********************************************************************
    void construct(pointer          p,
                  const value_type &x)
    {
        *p = x;
    }

    //*********************************************************************
    void destroy(pointer p)
    {
        p->~value_type();
    }

private:

    // Disabled operator.
    void operator =(const ArrayAllocator &);

    // The allocation pool.
    T buffer[MAX_SIZE];
};

//*********************************************************************
template <typename T, const size_t MAX_SIZE>
inline bool operator ==(const ArrayAllocator<T, MAX_SIZE> &,
                        const ArrayAllocator<T, MAX_SIZE> &)
{
    return (false);
}

//*********************************************************************
template <typename T, const size_t MAX_SIZE>
inline bool operator !=(const ArrayAllocator<T, MAX_SIZE> &,
                        const ArrayAllocator<T, MAX_SIZE> &)
{
    return (true);
}

//*********************************************************************
int main()
{
    const size_t MAX_SIZE = 10;

    std::vector<int, ArrayAllocator<int, MAX_SIZE>> test;

    cout << std::boolalpha << (test.size()    == 0)        << "\n";
    cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
    cout << std::boolalpha << (test.capacity() == 0)        << "\n";

    test.push_back(1); // Exception here for VS2010.
    test.push_back(2);

    cout << std::boolalpha << (test[0] == 1) << "\n";
    cout << std::boolalpha << (test[1] == 2) << "\n";

    cout << std::boolalpha << (test.size()    == 2)        << "\n";
    cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
    cout << std::boolalpha << (test.capacity() == 2)        << "\n";

    test.reserve(5);

    cout << std::boolalpha << (test.size()    == 2)        << "\n";
    cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
    cout << std::boolalpha << (test.capacity() == 5)        << "\n";
}

---

the allocator requirements ( both in c++11 and c++2003 ) basically imply that the allocator instance cannot "contain" the memory used for allocation, because given two instances a,b of the same (or rebinded) allocator type, a==b implies that b can deallocate what a has previously allocated and vice versa. Hence, your allocator will break whenever the container uses (legally) more then one "rebind" of your passed allocator type.

Indeed, in the vs2010 vector ctor code there is

Code:

---

{        // construct allocator from _Al
                typename _Alloc::template rebind<_Container_proxy>::other
                        _Alproxy(_Alval);
                this->_Myproxy = _Alproxy.allocate(1);
                _Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
                this->_Myproxy->_Mycont = this;

                _Myfirst = 0;
                _Mylast = 0;
                _Myend = 0;
        }

---

as you can see, your allocator is returning a pointer to a memory region to be destroyed at scope exit, hence the error. This doesn't happen in vs2008 just by chance, because only one allocator instance is used throughout the container lifetime ( allocator<T> for std::vector, allocator<T>::rebind<Node<T>>::other for std::list etc... )
Stack based allocators should use an external stack space instead, a so called "memory arena" ...

Quote:

---

Originally Posted by superbonzo

, a==b implies that b can deallocate what a has previously allocated and vice versa.

---

I understand what you're saying, but I understood that the purpose of the == and != operators was to inform the container code whether allocators were equivalent or not, and so take appropriate action. a==b in the case of this allocator would be false.

I'm programming in a real-time embedded environment and the purpose of the array allocators was to allow use of STL containers in a more deterministic manner.

Oh well, time to roll up the sleeves and refactor. :sick:

Quote:

---

Originally Posted by JohnW@Wessex

I understand what you're saying, but I understood that the purpose of the == and != operators was to inform the container code whether allocators were equivalent or not, and so take appropriate action. a==b in the case of this allocator would be false.

---

this would work if allocators were not required to be copy-constructible. Copy constructibility semantically implies that copies compare equal, hence the STL code above is legitimate ( although an _ASSERT( _Alproxy == _Alval ) would have been appropriate in this case ).

Quote:

---

Originally Posted by superbonzo

this would work if allocators were not required to be copy-constructible. Copy constructibility semantically implies that copies compare equal

---

PITA! What with these allocator restrictions, the requirement that predicates do not have state and non-guaranteed iteration order for some algorithms, I'm increasingly finding myself reverse engineering parts of the STL to work around around STL's 'flexibility' of implementation.

I've read all of the reasons it was designed this way, but in practice these restrictions have tended to make the code I want to write more complex (and sometimes less efficient).

Quote:

---

Originally Posted by JohnW@Wessex

PITA! What with these allocator restrictions...

---

well, I think you're asking too much here, as you're trying to enforce a memory layout ( = all allocations must fit into an array of objects of the same type ) and not just a memory allocation scheme. This is impossible unless severe restrictions are applyed to containers implementations ...

alternatively, did you take a look at boost memory pool ?

BTW, one scenario I found myself in is of having a container that most of the times has a small bounded memory requirement and predictable memory access; like, say, a vector v for which v.size()<=10 99/100 of times. Now, I would have liked an allocator working on the stack in such "normal" circumstances and reverting to the heap otherwise ( or throwing, or logging etc... ) in such a way to exploit that statistical advantage while retaining the std::vector interface and flexibility. Oversimplifying, something like:

Code:

---

#include <memory>
#include <list>

template < std::size_t N = 0, class FallbackAlloc = std::allocator<void> >
class lazy_buffer;

template <>
class lazy_buffer<0,std::allocator<void>>
{
public:
        lazy_buffer() {}

        virtual void* allocate( std::size_t n ) = 0;
        virtual void  deallocate( void* p, std::size_t n ) = 0;

private:
        lazy_buffer( const lazy_buffer& ); // deleted
        lazy_buffer& operator=( const lazy_buffer& ); // deleted
};

template < std::size_t N, class FallbackAlloc >
class lazy_buffer:
        public lazy_buffer<>
{
public:
        lazy_buffer(): current_( buffer_ ) {}
        lazy_buffer( const FallbackAlloc& fallback ): current_( buffer_ ), fallback_( fallback ) {}

        void* allocate( std::size_t n )
        {
                void* result;

                if( current_ + n <= buffer_ + N )
                {
                        result = current_;
                        current_ += n;
                }
                else
                        result = fallback_.allocate( n );
               
                return result;
        }

        void  deallocate( void* p, std::size_t n )
        {
                if( p < buffer_ || p >= buffer_ + N )
                {
                        fallback_.deallocate( reinterpret_cast<char*>( p ), n );
                }
        }

private:
        char  buffer_[N];
        char* current_;
        typename FallbackAlloc::template rebind<char>::other        fallback_;
};


template < class T >
class lazy_allocator
{
public:
        typedef T                value_type;
    typedef value_type*      pointer;
    typedef const value_type* const_pointer;
    typedef value_type&      reference;
    typedef const value_type& const_reference;
    typedef size_t            size_type;
    typedef std::ptrdiff_t    difference_type;

    template <typename U>
    struct rebind { typedef lazy_allocator<U> other; };

    lazy_allocator( lazy_buffer<>& rhs ): buffer_( &rhs ) {}

        template <class V>
        lazy_allocator( const lazy_allocator<V>& rhs ): buffer_( rhs.get_buffer() ) {}

    pointer                        address(reference x) const { return &x; }
        const_pointer        address(const_reference x) const { return &x; }

        size_type max_size() const { return std::numeric_limits<std::size_t>::max() / sizeof( T ); }

    pointer allocate( size_type n, const_pointer hint = 0 ) { return reinterpret_cast<pointer>( buffer_->allocate( n * sizeof( T ) ) ); }
    void        deallocate( pointer p, size_type n ) { return buffer_->deallocate( p, n * sizeof( T ) ); }

    void construct( pointer p, const value_type &v ) { new( reinterpret_cast<void*>( p ) ) value_type( v ); }
    void destroy( pointer p ) { p->~value_type(); }

        lazy_buffer<>* get_buffer() const { return buffer_; }

private:
        lazy_buffer<>* buffer_;
};

int main()
{
        static const std::size_t expected_size = 2; // "mean" number of elements
        static const std::size_t reserved_size = 3 * expected_size / 2; // optimal number of reserved elements to minimize probability of buffer exhaustion
        static const std::size_t reserved_memory_size = 3 * reserved_size * sizeof(int); // estimate of the actual memory per element consumption

        lazy_buffer<reserved_memory_size>  abuffer;
        std::list<int,lazy_allocator<int>> alist( abuffer );

        alist.push_back(0);
        alist.push_back(1);

        // ... ^ no heap allocations in vc2010
}

---

PS1: not tested, just a copy&past exercise :)
PS2: clearly, the code above ignores memory alignment and pointer representation issues, thus is wrong, in general. Moreover, it could be interesting to add further customization, like abstracting allocations relative to the "expected" memory access pattern ...
PS3: implementing this would be much more easier in c++11 thanks to allocator_traits ( no need to define allocator members with obvious definition ) and std::align(); unfortunately, vc2010 supports none of them :(

Thanks, I'll give that a look.
What I want is something like that, but with no fallback.

I've spent all morning trying to come up with a bounded size allocator that doesn't blow up with VS2010 or leak memory, with no luck yet. I was about ready to throw in the towel. :sick:

Thanks for the help, but I've run out of time to try and get something working :(

I'm beginning to think that the allocator implementation that I am after may be impossible with STL containers. Or at least, far more difficult than I'm prepared to spend time on.

I could probably have written and debugged an array based linked list class in the time I've wasted on this!

Quote:

---

Originally Posted by JohnW@Wessex

Here's a demo that compiles correctly with both VS2008 & VS2010, but exceptions under VS2010.

---

I didn't test it, but wouldn't the solution be to take the buffer out of the allocator? Something like

Code:

---

int main()
{
    const size_t MAX_SIZE = 1024; // bytes
    char buffer[MAX_SIZE];

    std::vector<int, ArrayAllocator<int, MAX_SIZE>> test(
        ArrayAllocator<int, MAX_SIZE>(buffer));
//...
}

---

where the buffer is passed to the allocator's constructor.

I think I've tried some variations of that, given superbonzo's comments , but I'll give it a second look.

Whenever I've put together an allocator that returns the same address as previously (which in theory should be perfectly valid for a vector of objects with trivial destructors, as I don't actually have to allocate more memory and move any data, just let it use more of the original array), VS2010 exceptions.

An experimental bodge that returned the last address+1 at every call kept it happy. (though of course it wasn't a solution)

I even tried alternating between two arrays to no avail.

It seems to expect that all allocations will be at new and unique addresses.

Quote:

---

Originally Posted by JohnW@Wessex

Whenever I've put together an allocator that returns the same address as previously (which in theory should be perfectly valid for a vector of objects with trivial destructors, as I don't actually have to allocate more memory and move any data, just let it use more of the original array), VS2010 exceptions.

---

It's not valid in general. Take the situation where you create two vectors using the same allocator (i.e. the same instance of your allocator class, thus using the same buffer). They would be writing to each other's memory.

With what you describe here, it seems that you are trying to change the behavior (or at least the implementation) of vector through the allocator. I think you'd be better of writing your own container class(es).

Quote:

---

Originally Posted by D_Drmmr

It's not valid in general. Take the situation where you create two vectors using the same allocator (i.e. the same instance of your allocator class, thus using the same buffer). They would be writing to each other's memory.

---

The idea was that different vectors wouldn't use the same allocator instance. The allocators would also be marked as 'non-equivalent' via the overloaded == and != allocator operators.

Quote:

---

Originally Posted by D_Drmmr

I think you'd be better of writing your own container class(es).

---

I'm beginning to think the same. I'm just not looking forward to the implementations of set & map!

Quote:

---

Originally Posted by JohnW@Wessex

The idea was that different vectors wouldn't use the same allocator instance.

---

I understand, but the vector implementation cannot assume that. It seems very reasonable to me that when an implementation asks for two allocations without deallocating in between that it requires to receive non-overlapping memory ranges from the allocator.

I think what really bugs me is that, as my allocators used to work OK under VS2008, it must be possible to produce an STL container that is compatible with allocators that contain their own storage.

BTW My original allocators worked with raw byte storage, aligned to the type, rather than an array of actual objects that my simplified example used.

Quote:

---

Originally Posted by JohnW@Wessex

I think what really bugs me is that, as my allocators used to work OK under VS2008, it must be possible to produce an STL container that is compatible with allocators that contain their own storage.

---

actually, the issue in c++03 was even worse because implementations were allowed to always consider equal allocator instances of the same type ( copy constructed or not ). So, even an allocator storing a pointer to an external arena was at least non portable in c++03.

anyway, an easy workaround to adapt your existing code to work with vs2010 is to make the allocator fallback to the heap when constructed from an allocator of different type (eg. the template copy constructor). Given that auxillary allocators are used for debugging purpose only ( at least in std::vector and std::list, I'm not sure for set/map ) you should recover the expected stack-only allocation behavior on release builds.

Clearly, this solution is not portable ...

Quote:

---

Originally Posted by superbonzo

anyway, an easy workaround to adapt your existing code to work with vs2010 is to make the allocator fallback to the heap when constructed from an allocator of different type

---

Unfortunately, that goes against my design requirements. Although the code is compiled and run on Windows for simulation purposes, the final application runs on a DSP platform with a lot less resources.

The object was to create an efficient allocator that could be used for STL containers on a memory restricted, time critical platform. The fixed storage overhead needed to be defined and placed in specified memory regions at compile time.

This would be especially useful when using std::list and other such containers where the storage cannot normally be reserved upfront.

You guys have me kind of lost, so I might be saying something stupid. The problem only occurs when objects from one container are swapped to another container that uses a different allocator, right?

Rather than re-code entire containers, isn't it possible to explicitly compare the allocators outside of the containers, and swap by value if the allocators are different?

Maybe stl containers don't explicitly support this, but that doesn't mean you can't add the support yourself explicitly via a new traits?