I have implemented a C++11 compatible linear or arena allocator. The code follows.
linear_allocator.hpp:
#pragma once
#include <cstddef>
#include <cassert>
#include <new>
#include "aligned_mallocations.hpp"
template <typename T>
class LinearAllocator
{
public:
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
//using propagate_on_container_copy_assignment = std::true_type;
//using propagate_on_container_move_assignment = std::true_type;
//using propagate_on_container_swap = std::true_type;
LinearAllocator(std::size_t count = 64)
: m_memUsed(0),
m_memStartAddress(nullptr)
{
allocate(count);
}
~LinearAllocator()
{
clear();
}
template <class U>
LinearAllocator(const LinearAllocator<U>&) noexcept
{}
/// \brief allocates memory equal to # count objects of type T
pointer allocate(std::size_t count)
{
if (count > std::size_t(-1) / sizeof(T))
{
throw std::bad_alloc{};
}
if (m_memStartAddress != nullptr)
{
alignedFree(m_memStartAddress);
}
m_memUsed = count * sizeof(T);
m_memStartAddress = static_cast<pointer>(alignedMalloc(m_memUsed, alignof(T)));
return m_memStartAddress;
}
/// \brief deallocates previously allocated memory
/// \brief Linear/arena allocators do not support free() operations. Use clear() instead.
void deallocate([[maybe_unused]] pointer p, [[maybe_unused]] std::size_t count) noexcept
{
//assert(false);
clear();
}
/// \brief simply resets memory
void clear()
{
if (m_memStartAddress != nullptr)
{
alignedFree(m_memStartAddress);
m_memStartAddress = nullptr;
}
this->m_memUsed = 0;
}
/// \brief GETTERS
pointer getStartAddress() const
{
return this->m_memStartAddress;
}
std::size_t getUsedMemory() const
{
return this->m_memUsed;
}
private:
std::size_t m_memUsed;
pointer m_memStartAddress;
};
template <class T, class U>
bool operator==(const LinearAllocator<T> &, const LinearAllocator<U> &)
{
return true;
}
template <class T, class U>
bool operator!=(const LinearAllocator<T> &, const LinearAllocator<U> &)
{
return false;
}
Don't worry about alignedMalloc and alignedFree. They are correct.
This is my test program (linear_allocator.cpp):
#include "linear_allocator.hpp"
#include <vector>
#include <deque>
#include <iostream>
#include <string>
#include <typeinfo>
int main()
{
[[maybe_unused]]
LinearAllocator<int> a{1024};
std::cout << a.getStartAddress() << '\n';
std::cout << a.getUsedMemory() << '\n';
std::vector<std::string, LinearAllocator<std::string>> v;
v.reserve(100);
std::cout << "Vector capacity = " << v.capacity() << '\n';
//std::cout << v.get_allocator().getStartAddress() << '\n';
//std::cout << v.get_allocator().getUsedMemory() << '\n';
v.push_back("Hello");
v.push_back("w/e");
v.push_back("whatever");
v.push_back("there is ist sofi j");
v.push_back("wisdom");
v.push_back("fear");
v.push_back("there's more than meets the eye");
for (const auto &s : v)
{
std::cout << s << '\n';
}
std::cout << typeid(v.get_allocator()).name() << '\n';
std::deque<int, LinearAllocator<int>> dq;
dq.push_back(23);
dq.push_back(90);
dq.push_back(38794);
dq.push_back(7);
dq.push_back(0);
dq.push_back(2);
dq.push_back(13);
dq.push_back(24323);
dq.push_back(0);
dq.push_back(1234);
for (const auto &i : dq)
{
std::cout << i << '\n';
}
std::cout << typeid(dq.get_allocator()).name() << '\n';
}
Compiling with g++ -std=c++17 -O2 -march=native -Wall linear_allocator.cpp -o linear_allocator.gpp.exe and running linear_allocator.gpp.exe gives output:
0x4328b8
4096
Vector capacity = 100
Hello
w/e
whatever
there is ist sofi j
wisdom
fear
there's more than meets the eye
15LinearAllocatorINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEE
As you can see deque's output isn't there at all. If I uncomment these 2 lines:
//std::cout << v.get_allocator().getStartAddress() << '\n';
//std::cout << v.get_allocator().getUsedMemory() << '\n';
vector's output will also not be displayed.
Compilation with MSVS cl gives the following output:
000000B47A1CAF88
4096
which is even worse.
There must be something I am missing as there appears to be UB, but I am unable to pinpoint where that is. My allocator design was based on C++11 + guidelines. I wonder what am I doing wrong.
While an allocator takes care of providing and releasing memory for storing container's data, it still does so only on container's request. That is, the actual management of the provided storage (in particular, its lifetime) is still on the container's side. Imagine what happens when a vector performs a relocation of its elements:
A new chunk of memory, greater by a given factor than the current (old) one, is requested.
The elements stored in the "old" chunk are copied/moved to the new chunk.
Only then, the "old" memory chunk can be released.
In your implementation, there can be only one memory chunk active at a time -- the old memory chunk is released before a new one is allocated (specifically, this happens when a container only requests a new chunk of memory, where the elements could be relocated to). You invoke UB already when the vector tries to relocate elements from the previous storage, because the memory where they lived has already been invalidated.
Additionally, by not providing a copy-constructor for your allocator type, the compiler-provided implementation performs a shallow copy (i.e., it copies the pointer, not the data stored under that address), which is then released in the destructor. That is, the call:
v.get_allocator()
will make a shallow copy of the allocator, creating a prvalue of your allocator type, and release the stored pointer as soon as the temporary object ends its lifetime (i.e., at the end of full statement including the cout call), leading to a double call to alignedFree on the same pointer.