2
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\begingroup\$ You're using Boost.PMR instead of std::pmr, with C++17? \$\endgroup\$
    – JDługosz
    Nov 23 at 14:52
  • \$\begingroup\$ Yes. The project I work on is tied to Clang 6.0.1 and Boost 1.67. \$\endgroup\$
    – Kory
    Nov 23 at 15:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – JDługosz
    Nov 23 at 15:06
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kory
    Nov 23 at 15:08
  • \$\begingroup\$ 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++. \$\endgroup\$
    – Kory
    Nov 23 at 15:38
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kory
    2 days ago
1
\$\begingroup\$
    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.

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$
    – Kory
    Nov 23 at 12:53
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – JDługosz
    Nov 23 at 15:10
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 23 at 15:55
1
\$\begingroup\$

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.
New contributor
Kory is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

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.