7
\$\begingroup\$

This is a fairly straightforward object allocator/factory, which sets up a stack of freed nodes as a linked list in the unused part of the storage. I would appreciate any and all feedback you may have.

A few things of note:

  • This is not intended to be a std::allocator drop-in replacement.
  • I'm kind of iffy on the ALLOC_T template parameter. It feels like it could be become annoying to use, but I need to add a trait type to manage entry_t otherwise (because of the default template parameter value). I'm definitely up for suggestions on that front.
  • My code does not currently actively use the move constructor/assignment beyond unit tests, and I'm on the fence about them. They subjectively feel like a potential minefield if misused, but potentially usefull during initialization. I'd like opinions on that.
  • I am mildly worried about strict aliasing violations since I'm being kinda cute with the entry_t union, recycling unused objects to maintain the free list. I'm pretty sure everything is fine, but I'd like a sanity check on that specific front.
  • If this code is bug-free, there should be no usage of the public interface of this class that could cause any of the asserts to fire.
  • Allocating and freeing is currently a hard O(1) and I like it this way.
  • I didn't bother with noexcept, should I have?

Here's the code:

#include <cassert>
#include <utility>
#include <vector>

template<typename T, template<typename> typename ALLOC_T=std::allocator>
class Arena {
public:
  using allocator_t = ALLOC_T<T>;
  using storage_t = std::aligned_storage<sizeof(T), alignof(T)>;
  union entry_t {
    storage_t storage;
    size_t next_free;
  };

  Arena(std::size_t count, const allocator_t& alloc=allocator_t())
    : storage_(count, alloc) {}

  Arena(Arena const&) = delete;
  Arena& operator=(Arena const&) = delete;

  Arena(Arena&& rhs)
    : storage_(std::move(rhs.storage_)),
      alloc_count_(rhs.alloc_count_),
      free_stack_top_(rhs.free_stack_top_) {
    rhs.alloc_count_ = 0;
    rhs.free_stack_top_ = npos;
  }

  Arena& operator=(Arena&& rhs) {
    storage_ = std::move(rhs.storage_);
    alloc_count_ = rhs.alloc_count_;
    free_stack_top_ = rhs.free_stack_top_;

    rhs.alloc_count_ = 0;
    rhs.free_stack_top_ = npos;
  }

  template<typename... ARGS>
  T* create(ARGS&&... args) {
    // Find the slot we will allocate from.
    entry_t* selected_entry = nullptr;
    if (free_stack_top_ != npos) {
      // If the free list is not empty, pick from it.
      assert(free_stack_top_ < storage_.size());
      selected_entry = &storage_[free_stack_top_];

      // Update the free list
      free_stack_top_ = selected_entry->next_free;
      assert(free_stack_top_ < storage_.size() || free_stack_top_ == npos);
    }
    else {
      // Pick from the end of the currently allocated block, which is currently contiguous.
      if (alloc_count_ == storage_.size()) {
        throw std::bad_alloc();
      }

      assert(alloc_count_ < storage_.size());
      selected_entry = &storage_[alloc_count_];
    }

    try {
      selected_entry->storage = storage_t();
      T* result = new(&selected_entry->storage) T(std::forward<ARGS>(args)...);
      ++alloc_count_;
      return result;
    }
    catch(...) {
      // If T's constructor throws, cancel the allocation
      selected_entry->next_free = free_stack_top_;
      free_stack_top_ = getId_(selected_entry);
      throw;
    }
  }

  void destroy(T* what) {
    what->~T();

    auto as_storage = reinterpret_cast<storage_t*>(what);
    auto as_entry = reinterpret_cast<entry_t*>(as_storage);
    auto index = getId_(as_entry);

    // Insert the freed node on the free stack
    storage_[index].next_free = free_stack_top_;
    free_stack_top_ = index;
    --alloc_count_;
  }

  size_t capacity() const {
    return storage_.size();
  }

  bool full() const {
    return alloc_count_ == capacity();
  }

private:

  // returns the index of a given storage entry.
  size_t getId_(entry_t* storage_entry) {
    assert(storage_entry >= &storage_.front() && storage_entry <= &storage_.back());
    return storage_entry - &storage_[0];
  }

  static const size_t npos = -1;

  std::vector<entry_t, allocator_t> storage_;
  size_t alloc_count_ = 0;
  size_t free_stack_top_ = npos;
};

Example usage:

#include <iostream>

struct test {
  int i_;

  test(int i) : i_(i) {
    std::cout << i << " created at: " << this << std::endl;
   }

  ~test() {
    std::cout << i_ << " destroyed" << std::endl;
  }

};

int main() {
  simpleobj::Arena<test> arena(12);

  int i = 0;
  auto a = arena.create(i++);
  auto b = arena.create(i++);
  auto c = arena.create(i++);
  auto d = arena.create(i++);

  arena.destroy(b);
  arena.destroy(c);

  auto e = arena.create(i++);
  arena.destroy(a);
  auto f = arena.create(i++);
  auto g = arena.create(i++);

  try {
    for (int i = 0; i < 100; ++i) {
      arena.create(i++);
    }
  }
  catch (std::exception& e) {
    std::cout << e.what() << std::endl;
  }

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ This is not only a memory allocator, but also a factory. Though, it leans more on the factory side. \$\endgroup\$ – Incomputable Sep 6 '17 at 8:34
  • \$\begingroup\$ @Incomputable Correct. The problem it adresses within my codebase is fundamentally a memory/cache management issue, which is why I had both conflated in my mind. \$\endgroup\$ – Frank Sep 6 '17 at 14:24
  • \$\begingroup\$ I believe making layered allocator would have a lot of benefits with affordable overhead. I'll write up an answer. \$\endgroup\$ – Incomputable Sep 6 '17 at 14:25
2
\$\begingroup\$

Looks pretty good, and compiles cleanly under g++-7 -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++. I can't answer all of the questions, but I'll review what I can:

  • I don't see a good reason for storage_t or entry_t to be public types.
  • I share your concern that casting a T* to obtain the corresponding entry_t can't be guaranteed - but I can't see a good O(1) replacement right now. Perhaps using std::aligned_union instead of std::aligned_storage+entry_t is the right way to go?
  • The assert in getId_() is (pedantically) unsafe if called with an entry that's not contained in storage_, because the comparison operators for pointers are defined only if they point into the same object. And misuse of the public interface could get us there, by asking us to destroy a T* that was not allocated by this.
  • The interface provides a full() test, but no empty(). The latter would be useful - perhaps at the end of a program if I want to ensure I released everything I allocated.
  • It's a shame you didn't provide a selection of tests, or a small application to exercise the interface (some of us like to run the code we're reviewing, to confirm the "feel" of it).
\$\endgroup\$
3
\$\begingroup\$

Bug: wrong allocation size

I added a few extra int fields to the test class to make it 20 bytes large, and then ran your program. This is the output I saw:

0 created at: 0x1f8dc20
1 created at: 0x1f8dc28
2 created at: 0x1f8dc30
3 created at: 0x1f8dc38

As you can see, each element is only 8 bytes apart instead of 20. In fact, when I filled in the int fields with values, the program quickly died on an assertion failure because I was overwriting the next_free fields of neighboring entries.

Possible fix

I changed this line:

  using storage_t = std::aligned_storage<sizeof(T), alignof(T)>;

to this:

  using storage_t = typename std::aligned_storage<sizeof(T), alignof(T)>::type;

and got the following better output (with 24 byte allocations):

0 created at: 0x20e8c20
1 created at: 0x20e8c38
2 created at: 0x20e8c50
3 created at: 0x20e8c68

I'm not a C++ expert. I just looked at the examples from here and here to figure out the above change.

\$\endgroup\$
1
\$\begingroup\$

What is described below is inspired by this talk from Andrei Alexandrescu.

Current architecture

  • Violation of one responsibility principle. It tries to both manage memory and allocate objects. Not good.

  • C style interface.

    Raw pointers are present for 20-30 years, I believe. It should be enough for them to shine and sunset, so let them die, at least in ownership context.

  • Restricts on allocator type.

    template<typename> typename ALLOC_T=std::allocator
    

    Behaves unlike what std::vector does. In my opinion, it would be great to provide users all of the power that vector has, and let them shoot in their foot if they wish.

  • Does not use new std::pmr features.

    Interoperability with newer features might be a boon in case the code base will keep moving forward. The namespace provides some useful stuff.

Proposed architecture

Layer the allocator:

  1. Lower level: deals with bytes exclusively. Has no idea what types are. May be uses supplied allocator.

  2. User-facing level: accepts lower level allocator as template parameter, as well as type it will be allocating.

Thus, it will be easier to move from one implementation to another. As code currently stands, it is extremely hard to decouple them. Also, as you probably have noted, the control flow is very hard and leaves lots of openings for forgotten/not considered edge cases.

Lower level

I believe the best interface would be

//template on something if needed
struct memory_allocator_base
{
    struct memory_slab
    {
        void* memblock;
        std::size_t size_in_bytes;
    }

    //I'd prefer no move or copy, since it doesn't know what stays above

    virtual memory_slab allocate(std::size_t size_in_bytes) = 0;
    virtual void deallocate(memory_slab memslab) = 0;

    //utility functions depending on situation and need
}

User-facing level

template <typename MemoryAllocator, typename T>
struct object_allocator_base
{
    std::unique_ptr<T, /*lambda deleter*/> allocate();
    //no need for deallocate, since it gives RAII style semantics!
}

Then, somewhere deep in the implementation:

//define deleter object

std::unique_ptr<T, deleter> allocate()
{ 
    auto slab = memory_allocator.allocate(sizeof(T), alignof(T));
    try 
    {
        allocate the object into slab.memblock;
    }
    catch () {}

    return {slab.memblock, deleter{slab}}; //don't forget the reinterpret_cast
}

deleter will just call original memory allocator with the slab it remembered during creation.

Problems

The main problem I've noticed already is the inability to return the smart pointer without knowing deleter in advance. Probably the deleter will be part of the base, so that it would be defined already.

Might have very high engineering costs. This is mostly unexplored world from what I see, but probably will put an end to memory leaks once and for all ...

\$\endgroup\$
  • \$\begingroup\$ I strongly disagree with the user-facing level forcing a unique_ptr. Ownership semantics have no business being handled by the factory, and is entirely dependant on the code that will actually own the instance. \$\endgroup\$ – Frank Sep 6 '17 at 16:26
  • \$\begingroup\$ I'm familiar with the presentation. But fair enough with regards to the unique_ptr interface. I'm currently playing around with your layered allocator approach, but managing the alignment of the pre-allocated blocks in memory_allocator_base is proving very akward. I'll get back to you once I've sorted it out. \$\endgroup\$ – Frank Sep 6 '17 at 16:45
  • \$\begingroup\$ Here's what I've landed on: gist.github.com/FrancoisChabot/174bfd8916ed4fbb5181e502ca80373d Wether BlockAllocator is reusable in other contexts is what will determine if it's better or not, as Arena is just a dumb wrapper around placement new and delete at this point. Frankly feels like overengineering to me. \$\endgroup\$ – Frank Sep 6 '17 at 17:05
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Incomputable Sep 6 '17 at 17:06

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.