10
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your effort to write such a detailed comment. Your coding style preferences are no doubt awesome. Please note that my Alloc is private. I have a publicAllocate function. It deduces alignment value (4, 8, 16) from the size parameter. I think it's good enough in practice. If you need to allocate anything cache-line or page aligned then this allocator is not for you. As for smaller alignments, allocators on 64-bit systems normally have minimum alignment of 16 or 8 bytes. And nobody cares. My allocator sometimes picks 4 bytes. It is already better than many people ever wanted. \$\endgroup\$ – Aleksey Demakov Aug 25 '18 at 23:30
  • 1
    \$\begingroup\$ On deducing alignment from size and/or assuming 16-byte alignment is good enough for anyone: posix_memalign was motivated by cases (such as SSE) where the default isn't good enough. In C++ you might get the best of both worlds by calling chunk.allocate<T>(n) and implementing that in terms of alloc(sizeof(T)*n, alignof(T)). \$\endgroup\$ – Quuxplusone Aug 26 '18 at 19:48
  • \$\begingroup\$ AFAIK 16-byte alignment should be enough for SSE. So my code should be able to handle such cases well. Thanks for reminding about alignof(), somehow I overlooked it. But I would use it only for smaller allocation sizes, while for larger (>= 16) sizes I would still use minimum 16-byte alignment exactly because compiler might emit SSE-instructions e.g. to copy large trivially-copyable objects. \$\endgroup\$ – Aleksey Demakov Aug 30 '18 at 5:36
-3
\$\begingroup\$

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(???)
};
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't think that part was code to be reviewed, it seems more like pseudo-code to illustrate the concept... Though you are right about being invalid in C++. \$\endgroup\$ – glampert Mar 30 '15 at 18:38
  • 2
    \$\begingroup\$ My question explicitly states that this is a C sample. Then the name of the struct is "C_Arena", try to guess why. And did not you notice some 150+ lines of C++ code that follow this C snippet? Any comments on those? Also why did you replace struct Header header with Header* header? It was not meant to be a pointer originally. I should also remind you that std::vector internally allocates memory on the free store. Therefore your code adds an extra level of indirection as compared to my code. This defeats its purpose. Anyway, thank you for the first answer to my question. \$\endgroup\$ – Aleksey Demakov Mar 30 '15 at 19:07
  • \$\begingroup\$ @AlekseyDemakov: I saw little point in reviewing the rest of the code with such a fundamental flaw at the beginning. Fix that and I will take a look at the rest of the code. Yep I did not know what to do with the head I was just guessing at that point. \$\endgroup\$ – Martin York Mar 30 '15 at 19:28
  • \$\begingroup\$ zero-sized array isn't valid in C either. Flexible array member is a C99 feature though. \$\endgroup\$ – Deduplicator Mar 31 '15 at 1:17
  • \$\begingroup\$ Can you just propose to make array[1] and finish the discussion? \$\endgroup\$ – Nick Sep 11 '16 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.