Fixed-size memory allocator

Question

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_{}
 , headers_{}
 {
 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.
 if (!std::align(alignof(header), sizeof(header), buffer_, space_left)) {
 throw std::runtime_error{"fixed_buffer_resource: internal memory alignment error. "};
 }
 headers_ = new (buffer_) header;
 headers_->size = space_left - sizeof(header);
 headers_->prev = nullptr;
 headers_->next = nullptr;
 headers_->used = false;
 } // 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;
 } // allocation_overhead
 /// 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,
 fmt::ptr(address_of_data_segment(h)),
 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;
 }
 }
 throw std::bad_alloc{};
 } // do_allocate
 auto do_deallocate(void* _p, std::size_t _bytes, std::size_t _alignment) -> void override
 {
 void* data = *(static_cast<void**>(_p) - 1);
 auto* h = reinterpret_cast<header*>(static_cast<ByteRep*>(data) - sizeof(header));
 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 | header | data segment |
 // +------------------+-----------------------------------------------+
 // | padding | unaligned pointer | aligned pointer |
 // +-----------------------------------------------+
 //
 struct header
 {
 std::size_t size; // Size of the memory block (excluding all management info).
 header* prev; // Pointer to the previous header block.
 header* next; // Pointer to the next header block.
 bool used; // Indicates whether the memory is in use.
 }; // struct header
 auto address_of_data_segment(header* _h) const noexcept -> ByteRep*
 {
 return reinterpret_cast<ByteRep*>(_h) + sizeof(header);
 } // address_of_data_segment
 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.
 void* data = address_of_data_segment(_h);
 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;
 if (!std::align(alignof(header), sizeof(header), aligned_header_storage, space_left)) {
 return nullptr;
 }
 // Construct a new header after the memory managed by "_h".
 // The new header manages unused memory.
 auto* new_header = new (aligned_header_storage) header;
 new_header->size = space_left - _bytes - sizeof(header);
 new_header->prev = _h;
 new_header->next = _h->next;
 new_header->used = false;
 // Update the allocation table links for the header just after the
 // newly added header.
 if (auto* next_header = _h->next; next_header) {
 next_header->prev = new_header;
 }
 // Adjust the current header's size and mark it as used.
 _h->size = _bytes;
 _h->next = new_header;
 _h->used = true;
 allocated_ += _bytes;
 return aligned_data;
 }
 return nullptr;
 } // allocate_block
 auto coalesce_with_next_unused_block(header* _h) -> void
 {
 if (!_h || _h->used) {
 return;
 }
 auto* header_to_remove = _h->next;
 // Coalesce the memory blocks if they are not in use by the client.
 // This means that "_h" will absorb the header at "_h->next".
 if (header_to_remove && !header_to_remove->used) {
 // TODO This does not consider the header's size.
 // How should I handle this?
 _h->size += header_to_remove->size;
 _h->next = header_to_remove->next;
 // Make sure the links between the headers are updated appropriately.
 // (i.e. "_h" and "header_to_remove->next" need their links updated).
 if (auto* new_next_header = header_to_remove->next; new_next_header) {
 new_next_header->prev = _h;
 }
 }
 } // coalesce_with_next_unused_block
 void* buffer_;
 std::size_t buffer_size_;
 std::size_t allocated_;
 header* headers_;
 }; // fixed_buffer_resource
} // namespace irods::experimental::pmr
#endif // IRODS_FIXED_BUFFER_RESOURCE_HPP

• JDługosz: You're using Boost.PMR instead of std::pmr, with C++17?
• Kory: Yes. The project I work on is tied to Clang 6.0.1 and Boost 1.67.
• JDługosz: 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.
• Kory: 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: 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++.

Answer 1

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;
 header* headers_ = nullptr;

And then your constructor needs only:

 : buffer_size_(_buffer_size)

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

• Kory: 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.

Answer 2

 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.

• Kory: 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?
• JDługosz: 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.
• Toby Speight: @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.

Answer 3

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;
 if (!std::align(alignof(header), sizeof(header), aligned_header_storage, space_left)) {
 return nullptr;
 }
 // Construct a new header after the memory managed by "_h".
 // The new header manages unused memory.
 auto* new_header = new (aligned_header_storage) header;

• 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.