I've found a little task to create a block memory pool allocator. This allocator is required to allocate memory in single fixed-sized blocks from the pool in static memory. Sizes of block and pool are fixed at compile-time, but should be tweakable during the build. This allocator should work on various embedded multithreaded platforms (RTOS). It also should contain several tests.
This is the solution I've come up with, I'd really love to hear some feedback.
#include <array>
#include <bitset>
#include <cassert>
#include <condition_variable>
#include <cstddef>
#include <mutex>
#include <stdexcept>
namespace block_allocator {
namespace detail {
enum class ExhaustedBehaviour {
throw_exception = 0, // If the pool is exhausted (empty) throw the std::bad_alloc{}
wait_for_release // If the pool is exhausted wait for other thread to release an object
};
}
template <std::size_t block_size = 8, std::size_t blocks = 32, detail::ExhaustedBehaviour behaviour = detail::ExhaustedBehaviour::throw_exception>
class Pool final {
public:
using pointer = void *;
// Thread-safe static singleton initialization ([stmt.dcl])
// Singleton prevents the static initialization order fiasco
static auto& get_instance() {
static Pool<block_size, blocks> pool;
return pool;
}
// Thread-safe (not interrupt-safe!) allocator
[[nodiscard]] pointer allocate() {
auto lock = std::unique_lock(mutex);
if constexpr (behaviour == detail::ExhaustedBehaviour::wait_for_release) {
if (occupation_flags.all())
condition_variable.wait(lock);
}
// Find index of the vacant chunk to be returned
auto vacant = FindVacant();
occupation_flags[vacant] = 1;
return &internal_pool[vacant];
}
// Thread-safe deallocation and pool inclusion check
void deallocate(pointer pointer) {
auto lock = std::unique_lock(mutex);
auto delta = GetPoolIndex(pointer);
// Memory doesn't belong to the pool.
// In any other code I would've thrown an exception, but deallocations often occur in destructors.
if (delta >= blocks)
return;
const bool is_exhausted = occupation_flags.all();
occupation_flags[delta] = 0;
if constexpr (behaviour == detail::ExhaustedBehaviour::wait_for_release) {
if (is_exhausted)
condition_variable.notify_one();
}
}
private:
// Type alias for an array of block_size bytes
using Block = std::array<std::byte, block_size>;
// Singleton helper
Pool() = default;
// Linear memory-efficient search time.
// For big PoolSizes one could prefer a linked list for a O(1) search time on account of dynamic memory allocation.
auto FindVacant() {
for (std::size_t i = 0; i < blocks; ++i)
if (occupation_flags[i] == 0)
return i;
if constexpr (behaviour == detail::ExhaustedBehaviour::throw_exception)
throw std::bad_alloc{};
else
throw std::runtime_error("Unexpected end of pool (check the correct usage of the is_exhausted flag)");
}
// O(1) chunk offset calculation
auto GetPoolIndex(pointer pointer) {
auto delta = static_cast<std::size_t>(reinterpret_cast<Block*>(pointer) -
reinterpret_cast<Block*>(&internal_pool[0]));
return delta;
}
// Uninitialized storage for block_size * blocks bytes
// Note the lack of alignment requirements. This may become a problem on ARM-alike architectures with placement new
std::array<Block, blocks> internal_pool;
// Occupation flags. Every bit represents the corresponding internal_pool element. 0 stands for vacant, 1 — occupied
std::bitset<blocks> occupation_flags;
// Condition variable for notifying other threads when the detail::ExhaustedBehaviour::wait_for_release is selected
static inline std::condition_variable condition_variable;
std::mutex mutex;
};
template <std::size_t block_size = 8, std::size_t blocks = 32>
class PoolTest {
public:
// Should be GTest, simplified for the sake of density
static bool test() {
auto dst = test_double_deallocation();
dst &= test_block_size();
dst &= test_exhaust();
dst &= test_threads();
return dst;
}
private:
// Simple (incomplete) RAII for internal test use.
// One should also delete the copy constructor and copy assignment operator
template <typename T, typename pool>
class AutoDeallocator {
public:
AutoDeallocator() {
pointer = reinterpret_cast<T*>(pool::get_instance().allocate());
}
~AutoDeallocator() {
pool::get_instance().deallocate(pointer);
}
operator T*() const {
return pointer;
}
private:
T* pointer = nullptr;
};
using current_pool = Pool <block_size, blocks>;
using pool_wrapper = AutoDeallocator<std::byte, current_pool>;
// Test the accidental double deallocation
static bool test_double_deallocation() {
try {
auto& pool = current_pool::get_instance();
auto ptr = pool.allocate();
pool.deallocate(ptr);
pool.deallocate(ptr);
}
catch (...) {
return false;
}
return true;
}
// Verify the block size via the pointer arithmetic
static bool test_block_size() {
auto first = pool_wrapper();
auto second = pool_wrapper();
auto delta = second - first;
return delta == block_size;
}
// Request all the blocks and catch the std::bad_alloc exception when requesting the extra one
static bool test_exhaust() {
std::array<pool_wrapper, blocks> arr{};
try {
pool_wrapper exhaust;
}
catch (std::bad_alloc&) {
return true;
}
catch(...) {
return false;
}
return false;
}
static bool test_threads() {
auto func = [](std::exception_ptr& e) {
try {
auto allocated = pool_wrapper();
}
catch(...) {
e = std::current_exception();
}
};
std::array<std::thread, blocks> array_of_threads;
std::array<std::exception_ptr, blocks> array_of_exceptions;
for(std::size_t i = 0; i < array_of_threads.size(); ++i) {
array_of_threads[i] = std::thread([&]() {
func(array_of_exceptions[i]);
});
}
std::for_each(array_of_threads.begin(), array_of_threads.end(), [](auto¤t_thread) { current_thread.join(); });
return std::all_of(array_of_exceptions.begin(), array_of_exceptions.end(), [](auto& val) {return val == nullptr; });
}
};
}
static bool pool_test = block_allocator::PoolTest<9, 4>::test();
int main() {
assert(pool_test);
return 0;
}
