# Fixed-size memory allocator

I've been trying to implement a simple Boost PMR allocator that has a fixed amount of memory. My first implementation (which can be found here) had undefined behavior and did not handle memory alignment.

I've been doing a lot of reading around these topics and while I'm still unclear about some of it, I believe the code posted below is closer to a real solution.

It would be very helpful if someone could review the code below for the following:

• undefined behavior
• proper handling of memory alignment
• obvious performance enhancements

Also, is it possible to calculate how many bytes are needed to align a buffer? See TODO comment in allocate_block(). What I have there now is the following, but it feels wrong.

const auto max_space_needed = sizeof(header) + sizeof(void*) + _bytes + _alignment;


For the most part, the implementation appears to work, but I want to make sure I've covered as many things as possible since this will be included in the next release of the software I work on.

#ifndef IRODS_FIXED_BUFFER_RESOURCE_HPP
#define IRODS_FIXED_BUFFER_RESOURCE_HPP

/// \file

#include <boost/container/pmr/memory_resource.hpp>

#include <fmt/format.h>

#include <cassert>
#include <cstddef>
#include <memory>
#include <ostream>
#include <stdexcept>
#include <tuple>
#include <type_traits>

/// A namespace containing components meant to be used with Boost.Container's PMR library.
namespace irods::experimental::pmr
{
/// A \p fixed_buffer_resource is a special purpose memory resource class template that
/// allocates memory from the buffer given on construction. It allows applications to
/// enforce a cap on the amount of memory available to components.
///
/// This class implements a first-fit scheme and is NOT thread-safe.
///
/// \tparam ByteRep The memory representation for the underlying buffer. Must be \p char
///                 or \p std::byte.
///
/// \since 4.2.11
template <typename ByteRep>
class fixed_buffer_resource
: public boost::container::pmr::memory_resource
{
public:
static_assert(std::is_same_v<ByteRep, char> ||
std::is_same_v<ByteRep, unsigned char> ||
std::is_same_v<ByteRep, std::uint8_t> ||
std::is_same_v<ByteRep, std::byte>);

/// Constructs a \p fixed_buffer_resource using the given buffer as the allocation
/// source.
///
/// \param[in] _buffer      The buffer that will be used for allocations.
/// \param[in] _buffer_size The size of the buffer in bytes.
///
/// \throws std::invalid_argument If any of the incoming constructor arguments do not
///                               satisfy construction requirements.
///
/// \since 4.2.11
fixed_buffer_resource(ByteRep* _buffer, std::int64_t _buffer_size)
: boost::container::pmr::memory_resource{}
, buffer_{_buffer}
, buffer_size_(_buffer_size)
, allocated_{}
{
if (!_buffer || _buffer_size <= 0) {
const auto* msg_fmt = "fixed_buffer_resource: invalid constructor arguments "
"[buffer={}, size={}].";
const auto msg = fmt::format(msg_fmt, fmt::ptr(_buffer), _buffer_size);
throw std::invalid_argument{msg_fmt};
}

std::size_t space_left = buffer_size_;

// Make sure the buffer is aligned for the header type.
throw std::runtime_error{"fixed_buffer_resource: internal memory alignment error. "};
}

} // fixed_buffer_resource

fixed_buffer_resource(const fixed_buffer_resource&) = delete;
auto operator=(const fixed_buffer_resource&) -> fixed_buffer_resource& = delete;

~fixed_buffer_resource() = default;

/// Returns the number of bytes used by the client.
///
/// The value returned does not include memory used for tracking allocations.
///
/// \return An unsigned integral type.
///
/// \since 4.2.11
auto allocated() const noexcept -> std::size_t
{
return allocated_;
} // allocated

/// Returns the number of bytes used for tracking allocations.
///
/// \return An unsigned integral type.
///
/// \since 4.2.11
auto allocation_overhead() const noexcept -> std::size_t
{
return 0;

/// Writes the state of the allocation table to the output stream.
///
/// \since 4.2.11
auto print(std::ostream& _os) const -> void
{
std::size_t i = 0;

for (auto* h = headers_; h; h = h->next) {
_os << fmt::format("{:>3}. Header Info [{}]: {{previous={:14}, next={:14}, used={:>5}, data={:14}, data_size={}}}\n",
i,
fmt::ptr(h),
fmt::ptr(h->prev),
fmt::ptr(h->next),
h->used,
h->size);
++i;
}
} // print

protected:
auto do_allocate(std::size_t _bytes, std::size_t _alignment) -> void* override
{
for (auto* h = headers_; h; h = h->next) {
if (auto* p = allocate_block(_bytes, _alignment, h); p) {
return p;
}
}

} // do_allocate

auto do_deallocate(void* _p, std::size_t _bytes, std::size_t _alignment) -> void override
{
void* data = *(static_cast<void**>(_p) - 1);

assert(h != nullptr);
assert(h->size == _bytes);

h->used = false;

coalesce_with_next_unused_block(h);
coalesce_with_next_unused_block(h->prev);

allocated_ -= _bytes;
} // do_deallocate

auto do_is_equal(const boost::container::pmr::memory_resource& _other) const noexcept -> bool override
{
return this == &_other;
} // do_is_equal

private:
// Header associated with an allocation within the underlying memory buffer.
// All data segments will be preceded by a header.
//
// Memory Layout:
//
//     +------------------------------------------------------------------+
//     +------------------+-----------------------------------------------+
//                        | padding | unaligned pointer | aligned pointer |
//                        +-----------------------------------------------+
//
{
std::size_t size;   // Size of the memory block (excluding all management info).
bool used;          // Indicates whether the memory is in use.

{

auto aligned_alloc(std::size_t _bytes, std::size_t _alignment, header* _h)
-> std::tuple<void*, std::size_t>
{
// The unused memory is located right after the header.
auto space_left = _h->size - sizeof(void*);

// Reserve space for the potentially unaligned pointer.
void* aligned_data = static_cast<ByteRep*>(data) + sizeof(void*);

if (!std::align(_alignment, _bytes, aligned_data, space_left)) {
return {nullptr, 0};
}

// Store the address of the original allocation directly before the
// aligned memory.
new (static_cast<ByteRep*>(aligned_data) - sizeof(void*)) void*{data};

return {aligned_data, space_left};
} // aligned_alloc

auto allocate_block(std::size_t _bytes, std::size_t _alignment, header* _h) -> void*
{
if (_h->used) {
return nullptr;
}

// Return the block if it matches the requested number of bytes.
if (_bytes == _h->size) {
if (auto* aligned_data = std::get<void*>(aligned_alloc(_bytes, _alignment, _h)); aligned_data) {
_h->used = true;
allocated_ += _bytes;
return aligned_data;
}
}

// TODO Is it possible to compute the amount of memory needed to satisfy
// the allocation and alignment requirements? I'm not sure if this line
// is correct.
const auto max_space_needed = sizeof(header) + sizeof(void*) + _bytes + _alignment;

// Split the data segment managed by this header if it is large enough
// to satisfy the allocation request and management information.
if (max_space_needed < _h->size) {
auto [aligned_data, space_left] = aligned_alloc(_bytes, _alignment, _h);

if (!aligned_data) {
return nullptr;
}

void* aligned_header_storage = static_cast<ByteRep*>(aligned_data) + _bytes;

return nullptr;
}

// Construct a new header after the memory managed by "_h".
// The new header manages unused memory.

// Update the allocation table links for the header just after the
}

_h->size = _bytes;
_h->used = true;

allocated_ += _bytes;

return aligned_data;
}

return nullptr;
} // allocate_block

{
if (!_h || _h->used) {
return;
}

// Coalesce the memory blocks if they are not in use by the client.
// This means that "_h" will absorb the header at "_h->next".
// TODO This does not consider the header's size.
// How should I handle this?

}
}
} // coalesce_with_next_unused_block

void* buffer_;
std::size_t buffer_size_;
std::size_t allocated_;
}; // fixed_buffer_resource
} // namespace irods::experimental::pmr

#endif // IRODS_FIXED_BUFFER_RESOURCE_HPP


• You're using Boost.PMR instead of std::pmr, with C++17? Nov 23, 2021 at 14:52
• Yes. The project I work on is tied to Clang 6.0.1 and Boost 1.67.
– Kory
Nov 23, 2021 at 15:03
• But pmr is available for the std collections in C++17; just because Boost is also in use doesn't mean you have to use Boost.Container. Nov 23, 2021 at 15:06
• Right. However, I don't think the version of Clang we use has support for std::pmr. I believe I checked for that before, but I'll check again.
– Kory
Nov 23, 2021 at 15:08
• Yeah, Clang 6 does not appear to have support for pmr. It has some headers, but the implementation is not complete. Also, I forgot to mention we are using libc++.
– Kory
Nov 23, 2021 at 15:38

Use inline initializers on your members rather than constants in the only constructor. You can write the members as:

    void* buffer_ = nullptr;
std::size_t buffer_size_;
std::size_t allocated_ = 0;


And then your constructor needs only:

 : buffer_size_(_buffer_size)


I notice that the parameter is uint64_t while the member uses size_t.

• The parameter type and member type are different on purpose. This is for situations where a negative value is passed to the constructor. We want to be able to detect those cases.
– Kory
Nov 28, 2021 at 2:20
    static_assert(std::is_same_v<ByteRep, char> ||
std::is_same_v<ByteRep, unsigned char> ||
std::is_same_v<ByteRep, std::uint8_t> ||
std::is_same_v<ByteRep, std::byte>);


Why those four particular types, but not signed char? Perhaps what we really care about is

   static_assert(sizeof (ByteRep) == 1);


            const auto* msg_fmt = "fixed_buffer_resource: invalid constructor arguments "
"[buffer={}, size={}].";
const auto msg = fmt::format(msg_fmt, fmt::ptr(_buffer), _buffer_size);
throw std::invalid_argument{msg_fmt};


Why do we discard msg, and populate the exception using the format string?

The handling of alignment is quite tricky. I don't see any obvious issues. The non-obvious issues need to be exercised using a good test suite; it's a shame you didn't include your tests in the review request.

• Thanks for your reply. The msg/msg_fmt is a typo due to experimenting with online editors (godbolt, etc). I have a very basic unit test which can be found here. What things should I test for other than allocation/deallocation? Is signed char different from char? Wouldn't it be possible for someone to pass an empty class as ByteRep if I only checked for a size of 1?
– Kory
Nov 23, 2021 at 12:53
• re signed char etc.: For casting to/from raw memory, the language only treats (plain) char , unsigned char, and std::byte as special. However, I think he avoids UB by using placement new for the header instead of just pointing into the buffer and calling it a header, even though it has no constructor or destructor. Nov 23, 2021 at 15:10
• @JDługosz, I guess that means that std::uint8_t should be removed from the list of acceptable types, then, rather than adding signed char. Nov 23, 2021 at 15:55

There is a bug in allocate_block().

                auto [aligned_data, space_left] = aligned_alloc(_bytes, _alignment, _h);

if (!aligned_data) {
return nullptr;
}

void* aligned_header_storage = static_cast<ByteRep*>(aligned_data) + _bytes;


• space_left is not updated to reflect the allocation of _bytes bytes. This means the call to std::align() for aligned_header_storage is incorrect.
• space_left needs to be checked to make sure there is enough space left in the buffer to hold an additional header.