C++ custom memory allocator

Question

I'm working on a C++ custom memory allocator, that would be kind of a replacement for the C flexible array syntax, you know, the stuff like that:

struct C_Arena
{
  struct Header header;
  size_t size;
  size_t used;
  char* data[];
};
...
struct C_Arena *arena = malloc(1000);
arena->size = 1000 - sizeof(struct C_flexible_array_struct));
arena->used = 0;
struct Header *header = &arena->header;
...

I want to have this in C++ like this:

auto arena = Chunk<Header>(new char[1000], 1000);
Header *header = arena.Get<Header>();
...

I'm not an expert C++ programmer. I had to learn a lot while I've been working on this problem. I probably made some mistakes. In particular I didn't think ahead about exception safety of my code. I'd like to get an advice on how to amend this problem. And any other suggestions on improving my code are welcome.

Please note that this is a low level allocator. Its interface is not compatible with libc++ requirements. I am going to add a libc++-compatible wrapper for this one as a separate class.

So far I have the following:

// Round down to a power of two multiple.
constexpr std::size_t Align(std::size_t n, std::size_t a) {
  return n & ~(a - 1);
}

// Round up to a power of two multiple.
constexpr std::size_t AlignUp(std::size_t n, std::size_t a) {
  return Align(n + a - 1, a);
}

namespace memory {
namespace detail {

// Calculate a data item alignment according to its size.
constexpr std::size_t Align(std::size_t size, std::size_t offset) {
  return size < 0x08 ? ::AlignUp(offset, 0x04)
                     : size < 0x10 ? ::AlignUp(offset, 0x08)
                                   : ::AlignUp(offset, 0x10);
}

// Services for placement of a given type instance within a memory chunk
// at the specified offset.
template <typename T, std::size_t S> class EntryLayout {
public:
  using Type = T;
  using Pointer = T *;

  static constexpr std::size_t Size = sizeof(Type);
  static constexpr std::size_t Offset = Align(Size, S);
  static constexpr std::size_t EndOffset = Offset + Size;

  static Pointer Instance(char *ptr) {
    return reinterpret_cast<Pointer>(RawData(ptr));
  }

  template <typename... Args>
  static Pointer Construct(char *ptr, Args &&... args) {
    return new (RawData(ptr)) Type(std::forward<Args>(args)...);
  }

  static void Destruct(char *ptr) { Instance(ptr)->~Type(); }

private:
  static char *RawData(char *ptr) { return ptr + Offset; }
};

// Services for placement of a number of types within a memory
// chunk at the specified offset.
template <std::size_t S, typename... Tail> class ChunkLayout {
public:
  static constexpr std::size_t StartOffset = S;
  static constexpr std::size_t EndOffset = S;

  template <typename... Args> static void Construct(char *, Args...) {}

  static void Destruct(char *) {}
};

// Recursive template specialization of the above.
template <std::size_t S, typename Head, typename... Tail>
class ChunkLayout<S, Head, Tail...>
    : public ChunkLayout<EntryLayout<Head, S>::EndOffset, Tail...> {
public:
  using EntryType = Head;
  using HeadLayout = EntryLayout<Head, S>;
  using TailLayout = ChunkLayout<HeadLayout::EndOffset, Tail...>;

  static constexpr std::size_t StartOffset = S;
  static constexpr std::size_t EndOffset = TailLayout::EndOffset;

  static typename HeadLayout::Pointer Instance(char *ptr) {
    return HeadLayout::Instance(ptr);
  }

  template <typename... Args> void Construct(char *ptr, Args... args) {
    HeadLayout::Construct(ptr, args...);
    TailLayout::Construct(ptr, args...);
  }

  void Destruct(char *ptr) {
    TailLayout::Destruct(ptr);
    HeadLayout::Destruct(ptr);
  }
};

} // namespace detail

// Control of memory chunk free and used space.
class ChunkSpace {
public:
  ChunkSpace(std::size_t size) noexcept : free_{size}, used_(0) {}

  std::size_t Used() const { return used_; }
  std::size_t Free() const { return free_; }
  std::size_t Size() const { return free_ + used_; }

  bool Alloc(std::size_t size) {
    if (size > free_)
      return false;
    free_ -= size;
    used_ += size;
    return true;
  }

  void Reset(std::size_t size = 0) {
    assert(size <= used_);
    free_ = free_ + used_ - size;
    used_ = size;
  }

private:
  std::size_t free_;
  std::size_t used_;
};

template <typename... EntryType>
class Chunk : public detail::ChunkLayout<0, ChunkSpace, EntryType...> {
  using Layout = detail::ChunkLayout<0, ChunkSpace, EntryType...>;

public:
  Chunk(char *data, std::size_t size) : data_{data} {
    assert(size > Layout::EndOffset);

    // Construct ChunkSpace instance to bootstrap allocation.
    Layout::HeadLayout::Construct(data_, size);
    // Allocate space required for all the chunk data.
    Alloc(Layout::EndOffset);
    // Construct the rest of the chunk data.
    Layout::TailLayout::Construct(data_);
  }

  ~Chunk() {
    Layout::Destruct(data_);
  }

  template <typename T>
  T* Get() {
    return decltype(Upcast<T>(this))::Instance(data_);
  }

  template <typename T>
  const T* Get() const {
    return decltype(Upcast<T>(this))::Instance(data_);
  }

  std::size_t Used() const { return Get<ChunkSpace>()->Used(); }
  std::size_t Free() const { return Get<ChunkSpace>()->Free(); }
  std::size_t Size() const { return Get<ChunkSpace>()->Size(); }

  void *Allocate(std::size_t size) {
    std::size_t offset = Used();
    std::size_t aligned_offset = detail::Align(size, offset);
    std::size_t offset_padding = aligned_offset - offset;
    if (!Alloc(size + offset_padding))
      return nullptr;
    return data_ + aligned_offset;
  }

private:
  bool Alloc(std::size_t size) {
    return Get<ChunkSpace>()->Alloc(size);
  }

  // Some C++ magic to upcast to the base class that contains layout info
  // for a given entry type.
  template <typename Head, std::size_t S, typename... Tail>
  static typename detail::ChunkLayout<S, Head, Tail...>::HeadLayout
  Upcast(const detail::ChunkLayout<S, Head, Tail...> *);

  char *data_;
};

} // namespace memory

To make clear how this code is going to be used, here is a more elaborated example:

#include "chunk.h"
#include "iostream"

struct A {
  int value = 0xa;
};

struct B {
  int value = 0xb;
};

int main() {
  char buffer[1024];

  // Create a memory chunk with 2 embedded structs.
  memory::Chunk<A, B> chunk(buffer, sizeof buffer);

  // Get and use the embedded structs.
  A *a = chunk.Get<A>();
  B *b = chunk.Get<B>();
  std::cout << std::hex;
  std::cout << "a: " << a->value << " b: " << b->value << std::endl;
  std::cout << std::dec;

  // Allocate a memory block within the chunk.
  void *p = chunk.Allocate(200);
  // Do whatever you like with the block.
  memset(p, 0, 200);
  // ...

  return 0;
}

Answer 1

Some random observations:

Your code is a bit harder to follow than it needs to be, because of your Consistent Use Of Capital Letters Without A Specific Purpose.

static constexpr std::size_t Size = sizeof(Type);
static constexpr std::size_t Offset = Align(Size, S);

Here we've got Capitals indicating a static member constant; a member typedef; an extern function; and a template non-type parameter. As a reader, I expect lowercase to be the default, and Capital Letters to indicate something specifically salient. In some codebases they mean "class names"; in others they mean "global constants"; but here they seem to mean nothing more than "I capitalize all my identifiers." This slows down the reader.

---

It seems like you're mixing two (maybe three) concerns here. First, you're writing a memory resource (a.k.a. allocator) that manages handing out chunks of memory from a buffer. Second, you've decided that the same buffer should also hold basically a std::tuple<EntryType...> as its first block.

Third, your initial example (but not your complete final example) suggests that maybe you want the memory resource to take ownership of its buffer and free it when it's done with it?

auto arena = Chunk<Header>(new char[1000], 1000);
Header *header = arena.Get<Header>();

If arena didn't take ownership of the buffer, this would be a memory leak, right? (But in your final example, you use a stack-local buffer, so it's not a problem.)

I recommend splitting your code into one piece that does nothing but the handing-out-memory-blocks business, and a separate piece that reimplements std::tuple. (Or, you know, just use std::tuple.) So then your Chunk<ElementType...> would look something like this:

template<class... Ts>
class Chunk {
    using Tuple = std::tuple<Ts...>;

    MemoryResource mr_;
    Tuple *tuple_;
public:
    explicit Chunk(char *buffer, size_t size) : mr_(buffer, size) {
        void *p = mr_.allocate(sizeof(Tuple));
        tuple_ = ::new (p) Tuple;
    }
    void *allocate(size_t bytes) { return mr_.allocate(bytes); }
    template<class T> auto& get() { return std::get<T>(tuple_); }
};

---

I notice that you provide both T* Get() and const T* Get() const. First of all, why T* and not T&? Second, have you considered whether the correct signature might be just a single overload T* Get() const? Your Chunk structure could arguably be viewed as a handle referring to the buffer; fetching a mutable reference to the T object stored in the buffer can be done without modifying the Chunk structure itself. Food for thought, maybe.

---

You wrote template<typename... EntryType> where I would write template<class... EntryTypes> — I use plural names for parameter packs, and recommend everyone else do so too. (And as for class over typename — it's just shorter.)

---

One more thing about your Get function: consider that you are allowed to have a std::tuple<A,A,A>, but you are not allowed to have a Chunk<A,A,A> with your current implementation. Functions that fetch a member out of a parameter-pack should almost invariably take an integer index, not a type, as their template parameter. Of course std::get for tuple and variant supports both syntaxes; you could, too.

---

I mistrust your Alloc function because it takes a size but fails to ask the caller what alignment they want. If I want space to store an int, I can call Alloc(4), but if the pointer I get back is 1-byte-aligned, that doesn't help me. As a general rule, allocation functions should always take both size and alignment parameters.

Answer 2

This is not valid C++.

struct C_Arena
{
  struct Header header;
  size_t size;
  size_t used;
  char* data[];
};
...
struct C_Arena *arena = malloc(1000);
arena->size = 1000 - sizeof(struct C_flexible_array_struct));
arena->used = 0;
struct Header *header = &arena->header;

Zero sized arrays is a C trick but not valid in C++. You can use a vector (or an array here). Then use the constructor to initialize all the members. This means your code will change a bit as the buffer is not local to the Arena object.

struct C_Arena
{
  size_t  size;
  size_t  used;
  std::vector<char> data;
  Header* header;

  C_Arena(std::size_t arenaSize = 1000)
     : size(arenaSize - sizeof(struct C_flexible_array_struct))
     , used(0)
     , data(arenaSize)
     , header(???)
};