C++ heap allocator using an explicit free list

Question

Description

I've written a heap allocator in C++ using an explicit free list for organization. I've also written a series of unit tests and a microbenchmark using Catch2. At time of writing I've tested it with gcc and clang on Linux and MSVC and clang on Windows.

The intended use case for this code is personal projects falling under the umbrella of real time simulations. The "problem" I'm solving is the same as why anyone writes an allocator, I'd imagine - consistent dynamic memory performance and insights into memory usage.

Request

I'd like feedback on a few thing in particular:

Design - I want to leverage C++20 well and write code that's reasonably readable and maintainable. By reasonably I mean something like the legal notion, e.g., "a reasonable developer." Opinions backed by experience are always welcome, too.

Performance - Writing portable, reusable code is more important than raw performance, but I don't want the design to needlessly hamper performance. Relatedly, I don't want to write code that hampers the compiler's ability to do its job with optimizations.

Unit tests - Ensuring "complete testing coverage" is a tough exercise, even for a small project like this. Did I forget any edge cases? Are my tests overwhelmingly redundant?

Benchmarking - I don't expect my code to outperform stdlib, but would you call the benchmark I wrote fair/useful/thorough? What other patterns would you test if this was your allocator? Or am I just mistaken and writing a bare-bones allocator like this should always yield better than stdlib performance?

Project Code

If you'd prefer to browse yourself, the full repository at time of writing is here.

The BlockHeader struct is really just something to cast a chunk of memory into.

#ifndef BRASSTACKS_MEMORY_BLOCKHEADER_HPP
#define BRASSTACKS_MEMORY_BLOCKHEADER_HPP

#include <cstddef>
#include <cstdint>

namespace btx::memory {

struct alignas(16) BlockHeader final {
public:
    // Convenience functions for common casting and pointer math
    [[nodiscard]] static inline BlockHeader * header(void *address) {
        return reinterpret_cast<BlockHeader *>(
            reinterpret_cast<uint8_t *>(address) - sizeof(BlockHeader)
        );
    }

    [[nodiscard]] static inline void * payload(BlockHeader *header) {
        return reinterpret_cast<uint8_t *>(header) + sizeof(BlockHeader);
    }

    // No constructors because BlockHeader is intended to be used as a means by
    // which to interpret existing memory via casts.
    BlockHeader() = delete;
    ~BlockHeader() = delete;

    BlockHeader(BlockHeader &&) = delete;
    BlockHeader(BlockHeader const &) = delete;

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

    std::size_t size = 0; // The size stored here refers to the space available
                          // for user allocation. Said another way, it's the
                          // size of the whole block, minus sizeof(BlockHeader).

    BlockHeader *next = nullptr;
    BlockHeader *prev = nullptr;
};

} // namespace btx::memory

#endif // BRASSTACKS_MEMORY_BLOCKHEADER_HPP

The Heap is the main actor.

#ifndef BRASSTACKS_MEMORY_HEAP_HPP
#define BRASSTACKS_MEMORY_HEAP_HPP

#include "brasstacks/memory/BlockHeader.hpp"

#include <cstddef>
#include <cstdint>

namespace btx::memory {

struct BlockHeader;

class Heap final {
public:
    [[nodiscard]] void * alloc(std::size_t const req_bytes);
    void free(void *address);

    [[nodiscard]] std::size_t total_size()     const { return _total_size;     }
    [[nodiscard]] std::size_t current_used()   const { return _current_used;   }
    [[nodiscard]] std::size_t current_allocs() const { return _current_allocs; }
    [[nodiscard]] std::size_t peak_used()      const { return _peak_used;      }
    [[nodiscard]] std::size_t peak_allocs()    const { return _peak_allocs;    }

    [[nodiscard]] uint8_t     const * raw_heap()  const { return _raw_heap; }
    [[nodiscard]] BlockHeader const * free_head() const { return _free_head; }

    [[nodiscard]] float calc_fragmentation() const;

    Heap() = delete;
    ~Heap();

    explicit Heap(std::size_t const req_bytes);

    Heap(Heap &&other) = delete;
    Heap(Heap const &) = delete;

    Heap & operator=(Heap &&other) = delete;
    Heap & operator=(Heap const &) = delete;

private:
    uint8_t     *_raw_heap;
    BlockHeader *_free_head;

    std::size_t _total_size;
    std::size_t _current_used;
    std::size_t _current_allocs;
    std::size_t _peak_used;
    std::size_t _peak_allocs;

    static std::size_t constexpr _min_alloc_bytes = sizeof(BlockHeader);

    void _split_free_block(BlockHeader *header, std::size_t const bytes);
    void _use_whole_free_block(BlockHeader *header);
    void _coalesce(BlockHeader *header);
};

} // namespace btx::memory

#endif // BRASSTACKS_MEMORY_HEAP_HPP

Consequently, Heap.cpp is the bulk of the code.

#include "brasstacks/memory/Heap.hpp"

#include <cassert>
#include <cstdlib>

namespace btx::memory {

// =============================================================================
float Heap::calc_fragmentation() const {
    std::size_t total_free = 0;
    std::size_t largest_free_block_size = 0;
    BlockHeader *current_header = _free_head;

    while(current_header != nullptr) {
        if(current_header->size > largest_free_block_size) {
            largest_free_block_size = current_header->size;
        }
        total_free += current_header->size;
        current_header = current_header->next;
    }

    if(total_free == 0) {
        return 0.0f;
    }

    return 1.0f - (
        static_cast<float>(largest_free_block_size)
        / static_cast<float>(total_free)
    );
}

// =============================================================================
void * Heap::alloc(std::size_t const req_bytes) {
    if(req_bytes <= 0) {
        assert(false && "Cannot allocate zero or fewer bytes");
        return nullptr;
    }

    std::size_t bytes = req_bytes;

    if(bytes < _min_alloc_bytes) {
        bytes = _min_alloc_bytes;
    }

    int32_t constexpr ALIGN = sizeof(void *);
    bytes = (bytes + ALIGN - 1) & -ALIGN;

    // Find a free block with sufficient space available
    auto *current_header = _free_head;
    while(current_header != nullptr) {
        std::size_t const size_of_new_block = bytes + sizeof(BlockHeader);
        // The most likely case that'll fit is the block we've found is bigger
        // than what we've asked for, so we need to split it. This implies
        // the creation of a new header for the new allocation as well
        if(current_header->size >= size_of_new_block) {
            // If splitting the block would result in less than 32 bytes of
            // free space, just use the whole thing
            if(current_header->size - size_of_new_block < _min_alloc_bytes) {
                _use_whole_free_block(current_header);
            }
            else {
                _split_free_block(current_header, bytes);
            }
            break;
        }

        // Much less likely, but still possible, is finding a block that fits
        // the request exactly, in which case we just need to fix the pointers
        if(current_header->size == bytes) {
            _use_whole_free_block(current_header);
            break;
        }

        // Carry on looking for a suitable block
        current_header = current_header->next;
    }

    // We couldn't find a block of sufficient size, so the allocation has
    // failed and the user will need to handle it how they see fit
    if(current_header == nullptr) {
        assert(false && "Failed to allocate block");
        return nullptr;
    }

    // Update the heap's metrics
    _current_used += current_header->size;
    _current_allocs += 1;

    if(_current_used > _peak_used) {
        _peak_used = _current_used;
    }

    if(_current_allocs > _peak_allocs) {
        _peak_allocs = _current_allocs;
    }

    // And hand the bytes requested back to the user
    return BlockHeader::payload(current_header);
}

// =============================================================================
void Heap::free(void *address) {
    if(address == nullptr) {
        assert(false && "Attempting to free memory twice");
        return;
    }

    // Grab the associated header from the user's pointer
    BlockHeader *header_to_free = BlockHeader::header(address);

    // Update heap stats
    _current_used -= header_to_free->size;
    _current_allocs -= 1;

    // If the free list is empty, then this block will serve as the new head
    if(_free_head == nullptr) {
        _free_head = header_to_free;
    }
    else if(header_to_free < _free_head) {
        // If the newly freed block has a earlier memory address than the free
        // list's current head, the freed block becomes the new head
        header_to_free->next = _free_head;
        header_to_free->prev = nullptr;
        _free_head->prev = header_to_free;

        _free_head = header_to_free;
    }
    else {
        // Otherwise the newly freed block will land somewhere after the head.
        // Walk the list to find a block to insert the newly free block after,
        // and break if current_block is the last free block in the list.
        auto *current_header = _free_head;
        while(header_to_free < current_header) {
            if(current_header->next == nullptr) {
                break;
            }

            current_header = current_header->next;
        }

        // Fix the list pointers
        header_to_free->next = current_header->next;
        header_to_free->prev = current_header;

        if(header_to_free->next != nullptr) {
            header_to_free->next->prev = header_to_free;
        }

        if(header_to_free->prev != nullptr) {
            header_to_free->prev->next = header_to_free;
        }
    }

    _coalesce(header_to_free);

    address = nullptr;
}

// =============================================================================
Heap::Heap(std::size_t const req_bytes) :
    _raw_heap       { nullptr },
    _current_used   { sizeof(BlockHeader) },
    _current_allocs { 0 },
    _peak_used      { sizeof(BlockHeader) },
    _peak_allocs    { 0 }
{
    if(req_bytes <= 0) {
        assert(false && "Cannot allocate zero sized heap");
        return;
    }

    // So long as BlockHeader's size is a power of two, this rounding to a
    // multiple math is safe
    int32_t constexpr ALIGN = sizeof(BlockHeader) * 2;
    std::size_t const bytes = (req_bytes + ALIGN - 1) & -ALIGN;

    _total_size = bytes;

    _raw_heap = reinterpret_cast<uint8_t *>(::malloc(_total_size));

    assert(_raw_heap != nullptr && "Heap allocation failed");

    _free_head = reinterpret_cast<BlockHeader *>(_raw_heap);

    _free_head->size = bytes - sizeof(BlockHeader);
    _free_head->next = nullptr;
    _free_head->prev = nullptr;
}

Heap::~Heap() {
    ::free(_raw_heap);
}

// =============================================================================
void Heap::_split_free_block(BlockHeader *header, std::size_t const bytes) {
    // Reinterpret the space just beyond what's requested as a new free block
    auto *new_free_header = reinterpret_cast<BlockHeader *>(
        reinterpret_cast<uint8_t *>(header)
        + sizeof(BlockHeader)
        + bytes
    );

    // The heap's used size increases for each header, whether free or used
    _current_used += sizeof(BlockHeader);

    // The new block's size is set to what's left of the original block
    new_free_header->size = header->size - sizeof(BlockHeader) - bytes;

    // And the allocation we'll return is shrunk proportionately
    header->size -= new_free_header->size + sizeof(BlockHeader);

    // Fix up the linked list, removing the allocation from the free list
    new_free_header->next = header->next;
    new_free_header->prev = header->prev;

    header->next = nullptr;
    header->prev = nullptr;

    if(new_free_header->next != nullptr) {
        new_free_header->next->prev = new_free_header;
    }

    if(new_free_header->prev != nullptr) {
        new_free_header->prev->next = new_free_header;
    }

    // Finally, adjust _free_head if need be
    if(header == _free_head) {
        _free_head = new_free_header;
    }
}

// =============================================================================
void Heap::_use_whole_free_block(BlockHeader *header) {
    if(header->next != nullptr) {
        header->next->prev = header->prev;
    }

    if(header->prev != nullptr) {
        header->prev->next = header->next;
    }

    if(header == _free_head) {
        _free_head = _free_head->next;
    }

    header->next = nullptr;
    header->prev = nullptr;
}

// =============================================================================
void Heap::_coalesce(BlockHeader *header) {
    if(header->next != nullptr) {
        // If the current block's payload plus its own size is the same
        // location as header->next, that means the blocks are contiguous and
        // can be merged
        auto *next_header_from_offset = reinterpret_cast<BlockHeader *>(
            reinterpret_cast<uint8_t *>(BlockHeader::payload(header))
            + header->size
        );

        if(next_header_from_offset == header->next) {
            // Grow the size of the current block by absorbing the next
            auto *next_header = header->next;
            header->size += sizeof(BlockHeader) + next_header->size;

            // Fix the pointers
            header->next = next_header->next;

            if(header->next != nullptr) {
                header->next->prev = header;
            }

            next_header->next = nullptr;
            next_header->prev = nullptr;

            // Since two blocks merged, there's one less header being used
            _current_used -= sizeof(BlockHeader);
        }
    }

    if(header->prev != nullptr) {
        // This is the same strategy as above, but measuring forward from
        // header->prev
        auto *prev_header_from_offset = reinterpret_cast<BlockHeader *>(
            reinterpret_cast<uint8_t *>(BlockHeader::payload(header->prev))
            + header->prev->size
        );

        if(prev_header_from_offset == header) {
            // Grow the size of the current block by absorbing the next
            auto *prev_header = header->prev;
            prev_header->size += sizeof(BlockHeader) + header->size;

            // Fix the pointers
            prev_header->next = header->next;

            if(header->next != nullptr) {
                header->next->prev = header->prev;
            }

            header->next = nullptr;
            header->prev = nullptr;

            // Since two blocks merged, there's one less header being used
            _current_used -= sizeof(BlockHeader);
        }
    }
}

} // namespace btx::memory

Unit Tests and Benchmark

As for the Catch2 code, the source files share brief header

#ifndef TEST_HELPERS_HPP
#define TEST_HELPERS_HPP

#include <catch2/catch_test_macros.hpp>
#include <catch2/matchers/catch_matchers_floating_point.hpp>
#include <catch2/benchmark/catch_benchmark.hpp>

float constexpr epsilon = 1.0e-6f;

#endif // TEST_HELPERS_HPP

This is the benchmark I wrote:

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

#include <random>
#include <functional>
#include <vector>
#include <numeric>

using namespace btx::memory;

constexpr std::size_t alloc_count = 1000;
constexpr std::size_t min_alloc_size = 1 << 4;
constexpr std::size_t max_alloc_size = 1 << 8;

TEST_CASE("Benchmarking") {
    // The first thing we need is a good ol' RNG on which to base our ranges
    std::random_device dev;
    std::default_random_engine rng(dev());

    // Next, a vector of random allocation sizes
    std::vector<std::size_t> alloc_sizes;
    alloc_sizes.resize(alloc_count);

    auto alloc_size_rng = std::bind(
        std::uniform_int_distribution<std::size_t>(min_alloc_size,
                                                   max_alloc_size),
        rng
    );

    for(auto &alloc_size : alloc_sizes) {
        alloc_size = alloc_size_rng();
    }

    // The benchmarks below will allocate 500 randomly sized blocks, then free
    // those 500 blocks in a random order, and repeat for the second 500 blocks.
    // In service of that, I'll make two vectors of indices (first half: 0-499,
    // second half 499-999) and shuffle them
    std::vector<std::size_t> free_order_first_half(alloc_count/2);
    std::iota(
        free_order_first_half.begin(),
        free_order_first_half.end(),
        0
    );
    std::shuffle(
        free_order_first_half.begin(),
        free_order_first_half.end(),
        rng
    );

    std::vector<std::size_t> free_order_second_half(alloc_count/2);
    std::iota(
        free_order_second_half.begin(),
        free_order_second_half.end(),
        alloc_count/2
    );
    std::shuffle(
        free_order_second_half.begin(),
        free_order_second_half.end(),
        rng
    );

    // Finally, a vector of pointers to store the allocations
    std::vector<void *> allocs(alloc_count);
    std::fill(allocs.begin(), allocs.end(), nullptr);

    // Test plain malloc() and free()
    BENCHMARK("libstdc malloc and free benchmark") {
        return [&] {
            std::size_t alloc = 0;

            // Allocate the first half
            do {
                allocs[alloc] = ::malloc(alloc_sizes[alloc]);

                // Zero the memory
                ::memset(allocs[alloc], 0, alloc_sizes[alloc]);

                // Write some "useful" information
                auto *new_block = static_cast<std::size_t *>(allocs[alloc]);
                *new_block = alloc_sizes[alloc];

                ++alloc;
            } while(alloc < alloc_count/2);

            // Free the first half in random order
            for(auto const index : free_order_first_half) {
                ::free(allocs[index]);
            }

            // Allocate the second half
            do {
                allocs[alloc] = ::malloc(alloc_sizes[alloc]);

                // Same nonosense as above
                ::memset(allocs[alloc], 0, alloc_sizes[alloc]);
                auto *new_block = static_cast<std::size_t *>(allocs[alloc]);
                *new_block = alloc_sizes[alloc];

                ++alloc;
            } while(alloc < alloc_count);

            // Free the second half in random order
            for(auto const index : free_order_second_half) {
                ::free(allocs[index]);
            }
        };
    };

    // Create a heap that's guaranteed to be able to hold all of our random
    // allocations
    auto heap_size_rng = std::bind(
        std::uniform_int_distribution<std::size_t>(
            max_alloc_size * alloc_count + 32u,
            max_alloc_size * alloc_count * 2
        ),
        rng
    );

    Heap heap(heap_size_rng());

    // And test its performance
    BENCHMARK("btx::memory alloc and free benchmark") {
        return [&] {
            std::size_t alloc = 0;

            // Allocate the first half
            do {
                allocs[alloc] = heap.alloc(alloc_sizes[alloc]);

                // Zero the memory
                ::memset(allocs[alloc], 0, alloc_sizes[alloc]);

                // Write some "useful" information
                auto *new_block = static_cast<std::size_t *>(allocs[alloc]);
                *new_block = alloc_sizes[alloc];

                ++alloc;
            } while(alloc < alloc_count/2);

            // Free the first half in random order
            for(auto const index : free_order_first_half) {
                heap.free(allocs[index]);
            }

            // Allocate the second half
            do {
                allocs[alloc] = heap.alloc(alloc_sizes[alloc]);

                // Same nonosense as above
                ::memset(allocs[alloc], 0, alloc_sizes[alloc]);
                auto *new_block = static_cast<std::size_t *>(allocs[alloc]);
                *new_block = alloc_sizes[alloc];

                ++alloc;
            } while(alloc < alloc_count);

            // Free the second half in random order
            for(auto const index : free_order_second_half) {
                heap.free(allocs[index]);
            }
        };
    };
}

Testing basic Heap functions.

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

using namespace btx::memory;
using namespace Catch::Matchers;

TEST_CASE("Heap creation and initial state metrics") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    // First check the heap's internal metrics
    REQUIRE(heap.current_used() == sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Next check the heap's structure
    auto const *raw_heap = heap.raw_heap();
    auto const *free_header = reinterpret_cast<BlockHeader const *>(raw_heap);

    REQUIRE(free_header->size == heap_size - sizeof(BlockHeader));
    REQUIRE(free_header->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
}

Testing just one block.

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

using namespace btx::memory;
using namespace Catch::Matchers;

TEST_CASE("Allocate and free a single block") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    // Allocate one block
    std::size_t const size_a = 64;
    void *alloc_a = heap.alloc(size_a);

    // Check the heap's internal metrics
    REQUIRE(heap.total_size() == heap_size);
    REQUIRE(heap.current_used() == size_a + 2 * sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Check that the BlockHeader helper functions produce interchangable
    // addresses, and that header_a->next is nullptr
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));
    REQUIRE(header_a->next == nullptr);

    // The header for our sole allocation is at the very beginning of the heap
    auto const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);

    // The free block header is now at +96 bytes
    auto const *free_header = reinterpret_cast<BlockHeader const *>(
        raw_heap + sizeof(BlockHeader) + header_a->size
    );

    // And the free block is 384 bytes in size
    REQUIRE(free_header->size ==
        heap_size - (header_a->size + 2 * sizeof(BlockHeader))
    );

    // free_header->next should point nowhere
    REQUIRE(free_header->next == nullptr);

    // Now free the block
    heap.free(alloc_a);

    // The heap's internal metrics should be back to their initial state
    REQUIRE(heap.total_size() == 512);
    REQUIRE(heap.current_used() == sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == size_a + 2 * sizeof(BlockHeader));
    REQUIRE(heap.peak_allocs() == 1);
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));
}

TEST_CASE("Allocate and free a single block, filling the heap") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    // Allocate one block
    std::size_t const size_a = heap_size - sizeof(BlockHeader);
    void *alloc_a = heap.alloc(size_a);

    // Check the heap's internal metrics
    REQUIRE(heap.total_size() == heap_size);
    REQUIRE(heap.current_used() == size_a + sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Check that the BlockHeader helper functions produce interchangable
    // addresses, and that header_a->next is nullptr
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));
    REQUIRE(header_a->next == nullptr);

    // The header for our sole allocation is at the very beginning of the heap
    auto const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);

    // Now free the block
    heap.free(alloc_a);

    // The heap's internal metrics should be back to their initial state
    REQUIRE(heap.total_size() == 512);
    REQUIRE(heap.current_used() == sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == size_a + sizeof(BlockHeader));
    REQUIRE(heap.peak_allocs() == 1);
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));
}

Testing two blocks.

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

using namespace btx::memory;
using namespace Catch::Matchers;

TEST_CASE("Allocate and free two blocks, free a->b") {
    std::size_t const heap_size = 256;
    Heap heap(heap_size);

    // Allocate two blocks
    std::size_t const size_a = 64;
    std::size_t const size_b = 96;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);

    // Check the heap's internal metrics
    REQUIRE(heap.current_used() == 256);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());

    // Check that the BlockHeader helper functions produce interchangable
    // addresses
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));

    BlockHeader *header_b = BlockHeader::header(alloc_b);
    // alloc_b will have absorbed the zero-byte free block below it, meaning
    // alloc_b is 32 bytes larger than the requested size
    REQUIRE(header_b->size == 128);
    REQUIRE(alloc_b == BlockHeader::payload(header_b));

    // Both headers' pointers should be null
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(heap.free_head() == nullptr);

    // The first header is at the very beginning of the heap
    uint8_t const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);

    // The second header is at +96 bytes
    REQUIRE(reinterpret_cast<uint8_t *>(header_b) ==
        raw_heap + sizeof(BlockHeader) + size_a
    );

    // Since the free header was absorbed, it should be null
    REQUIRE(heap.free_head() == nullptr);

    // Now free the first block
    heap.free(alloc_a);

    // Check the heap stats
    REQUIRE(heap.current_used() == 192);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 256);
    REQUIRE(heap.peak_allocs() == 2);

    // Given that header_a is now free, it should be the new head of the free
    // list. Its size is unchanged and its pointers are null because it's the
    // only member of the list
    REQUIRE(heap.free_head() == header_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_a->prev == nullptr);

    // Free the second block
    heap.free(alloc_b);

    // Check the heap stats
    REQUIRE(heap.current_used() == sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 256);
    REQUIRE(heap.peak_allocs() == 2);

    // Given that the second block was between the first and free blocks, the
    // entire heap should now be back to a single free block
    REQUIRE(header_a->size == heap_size - sizeof(BlockHeader));
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
}

TEST_CASE("Allocate and free two blocks, free b->a") {
    std::size_t const heap_size = 256;
    Heap heap(heap_size);

    // Allocate two blocks
    std::size_t const size_a = 64;
    std::size_t const size_b = 96;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);

    // Check the heap's internal metrics
    REQUIRE(heap.current_used() == 3 * sizeof(BlockHeader) + size_a + size_b);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());

    // Check that the BlockHeader helper functions produce interchangable
    // addresses
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));

    BlockHeader *header_b = BlockHeader::header(alloc_b);
    REQUIRE(header_b->size == 128);
    REQUIRE(alloc_b == BlockHeader::payload(header_b));

    // Both headers' next pointer should be null
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_b->next == nullptr);

    // The first header is at the very beginning of the heap
    uint8_t const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);

    // The second header is at +96 bytes
    REQUIRE(reinterpret_cast<uint8_t *>(header_b) ==
        raw_heap
        + sizeof(BlockHeader)
        + size_a
    );

    // Since the free header was absorbed, it should be null
    REQUIRE(heap.free_head() == nullptr);

    // Now free the second block
    heap.free(alloc_b);

    // Check the heap stats
    REQUIRE(heap.current_used() == size_a + 2 * sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 3 * sizeof(BlockHeader) + size_a + size_b);
    REQUIRE(heap.peak_allocs() == 2);

    // At this point, the free list is just header_b plus the 32 bytes it
    // absorbed when we coalesced the zero-byte block previosuly called
    // free_header
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->size == size_b + sizeof(BlockHeader));
    REQUIRE(header_a->size == size_a);

    // Free the first block
    heap.free(alloc_a);

    // Check the heap stats
    REQUIRE(heap.current_used() == sizeof(BlockHeader));
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 3 * sizeof(BlockHeader) + size_a + size_b);
    REQUIRE(heap.peak_allocs() == 2);

    // The entire heap should now be back to a single free block
    REQUIRE(header_a->size == heap_size - sizeof(BlockHeader));
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
}

Testing three blocks.

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

using namespace btx::memory;
using namespace Catch::Matchers;

TEST_CASE("Allocate and free three blocks, free a->b->c") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    // Check the heap's internal metrics
    REQUIRE(heap.current_used() == 416);
    REQUIRE(heap.current_allocs() == 3);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());

    // Check that the BlockHeader helper functions produce interchangable
    // addresses
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));

    BlockHeader *header_b = BlockHeader::header(alloc_b);
    REQUIRE(header_b->size == size_b);
    REQUIRE(alloc_b == BlockHeader::payload(header_b));

    BlockHeader *header_c = BlockHeader::header(alloc_c);
    REQUIRE(header_c->size == size_c);
    REQUIRE(alloc_c == BlockHeader::payload(header_c));

    // Check the physical locations in memory
    auto const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);
    REQUIRE(reinterpret_cast<uint8_t *>(header_b) == raw_heap + 96);
    REQUIRE(reinterpret_cast<uint8_t *>(header_c) == raw_heap + 224);

    // And the free block is 96 bytes in size, given a 32 byte BlockHeader
    auto const *free_header = heap.free_head();
    REQUIRE(free_header->size == 96);

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_a);

    // The internal metrics will largely be the same, except with size_a fewer
    // used bytes and one fewer allocs
    REQUIRE(heap.current_used() == 352);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Given 64+96=160 bytes total free, fragmentation is ~0.4
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.4f, epsilon));

    // header_a has become the "true" free_header, which means the next pointer
    // directs us to the free chunk at the end of the heap
    REQUIRE(header_a->next == free_header);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_a);

    // header_a, while now free, has the same size as it did before
    REQUIRE(header_a->size == 64);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_b);

    // This time, the used bytes count drops by size_b and the size of a
    // BlockHeader, since a and b should be merged now
    REQUIRE(heap.current_used() == 224);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Given 192+96=288 bytes total free, fragmentation is ~0.33
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs((1.0f/3.0f), epsilon));

    // header_a->next still  points to the free block at the end of the heap
    // since it just absorbed alloc_b
    REQUIRE(header_a->next == free_header);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_a);

    // But the size has grown by size_b and sizeof(BlockHeader)
    REQUIRE(header_a->size == 192);

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_c);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Everything is free, so fragmentation should be at zero
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // There's no more free block at the end of the heap, so header_a->next
    // points nowhere
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

TEST_CASE("Allocate and free three blocks, free a->c->b") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    BlockHeader *header_a = BlockHeader::header(alloc_a);
    BlockHeader *header_b = BlockHeader::header(alloc_b);
    BlockHeader *header_c = BlockHeader::header(alloc_c);

    auto const *free_header = heap.free_head();

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_a);

    // The internal metrics will largely be the same, except with size_a fewer
    // used bytes and one fewer allocs
    REQUIRE(heap.current_used() == 352);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Given 64+96=160 bytes total free, fragmentation is ~0.4
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.4f, epsilon));

    // header_a has become the "true" free_header, which means the next pointer
    // directs us to the free chunk at the end of the heap
    REQUIRE(header_a->next == free_header);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_a);

    // header_a, while now free, has the same size as it did before
    REQUIRE(header_a->size == 64);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_c);

    // header_c and free_header have merged
    REQUIRE(heap.current_used() == 192);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // header_a is still the top of the free list, but now it points to b
    REQUIRE(header_a->next == header_c);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == header_a);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // 64+256=320 bytes total free, fragmentation is ~0.2
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.2f, epsilon));

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_b);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // No fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // There's no more free block at the end of the heap, so header_a->next
    // points nowhere
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

TEST_CASE("Allocate and free three blocks, free b->a->c") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    BlockHeader *header_a = BlockHeader::header(alloc_a);
    BlockHeader *header_b = BlockHeader::header(alloc_b);
    BlockHeader *header_c = BlockHeader::header(alloc_c);

    auto const *free_header = heap.free_head();

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_b);

    // The 96 bytes of alloc_b will have been subtracted from the total used
    REQUIRE(heap.current_used() == 320);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // alloc_b is now free and is 96 bytes, so we're at ~0.5 fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.5f, epsilon));

    // With header_b now technically a free header, its next pointer will
    // lead to the original free_header
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == free_header);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_b);

    // Both header_b and free_header will have the same sizes as before
    REQUIRE(header_b->size == 96);
    REQUIRE(free_header->size == 96);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_a);

    // Now we've got a and b merged, plus the straggler free block at the end
    REQUIRE(heap.current_used() == 224);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // a and b taken together gives us 192 bytes, so ~0.3 fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs((1.0f/3.0f), epsilon));

    // header_a->next now jumps to the original free_header
    REQUIRE(header_a->next == free_header);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_a);

    // header_a->size has grown to encompass both a and b, but free_header
    // stays the same
    REQUIRE(header_a->size == 192);
    REQUIRE(free_header->size == 96);

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_c);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // And 0 fragmentation when it's all said and done
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // There's no more free block at the end of the heap, so header_a->next
    // points nowhere
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

TEST_CASE("Allocate and free three blocks, free b->c->a") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    BlockHeader *header_a = BlockHeader::header(alloc_a);
    BlockHeader *header_b = BlockHeader::header(alloc_b);
    BlockHeader *header_c = BlockHeader::header(alloc_c);

    auto const *free_header = heap.free_head();

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_b);

    // The 96 bytes of alloc_b will have been subtracted from the total used
    REQUIRE(heap.current_used() == 320);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // alloc_b is now free and is 96 bytes, so we're at ~0.5 fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.5f, epsilon));

    // With header_b now technically the free header, its next pointer will
    // lead to the original free_header
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == free_header);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_b);

    // Both header_b and free_header will have the same sizes as before
    REQUIRE(header_b->size == 96);
    REQUIRE(free_header->size == 96);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_c);

    // Now we've just got a and b, with all the free space after b coallesced
    REQUIRE(heap.current_used() == 128);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // b and c will have merged with the original free block, so there's no
    // fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // All the free space is coallesced, so header_b is the whole free list
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // header_b->size has grown to encompass c and the original free_header
    REQUIRE(header_b->size == 384);

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_a);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // And again, no fragmentation when everything's free
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Everything's free
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

TEST_CASE("Allocate and free three blocks, free c->a->b") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    BlockHeader *header_a = BlockHeader::header(alloc_a);
    BlockHeader *header_b = BlockHeader::header(alloc_b);
    BlockHeader *header_c = BlockHeader::header(alloc_c);

    auto const *free_header = heap.free_head();

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_c);

    // The free block at the end of the heap and alloc_c will have merged
    REQUIRE(heap.current_used() == 256);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Given the free blocks are coallesced, fragmentation is 0
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Since the original free block and alloc_c have merged, and header_c
    // is the new free header, the pointers are cleared out
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // The header_c/the free header's size has grown
    REQUIRE(header_c->size == 256);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_a);

    // header_a is the new free header, so we've only reclaimed 64 bytes
    REQUIRE(heap.current_used() == 192);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // The free list pointers skip over alloc_b
    REQUIRE(header_a->next == header_c);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == header_a);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // 64+256=320, and 256/320 = 0.8, so we've got ~20% fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.2f, epsilon));

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_b);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // And again, no fragmentation when everything's free
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // There's no more free block at the end of the heap, so header_a->next
    // points nowhere
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

TEST_CASE("Allocate and free three blocks, free c->b->a") {
    std::size_t const heap_size = 512;
    Heap heap(heap_size);

    std::size_t const size_a = 64;
    std::size_t const size_b = 96;
    std::size_t const size_c = 128;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);

    BlockHeader *header_a = BlockHeader::header(alloc_a);
    BlockHeader *header_b = BlockHeader::header(alloc_b);
    BlockHeader *header_c = BlockHeader::header(alloc_c);

    auto const *free_header = heap.free_head();

    //--------------------------------------------------------------------------
    // Free the first block
    heap.free(alloc_c);

    // The free block at the end of the heap and alloc_c will have merged
    REQUIRE(heap.current_used() == 256);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Given the free blocks are coallesced, fragmentation is 0
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Since the original free block and alloc_c have merged, and header_c
    // is the new free header, the pointers are cleared out
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // The header_c/the free header's size has grown
    REQUIRE(header_c->size == 256);

    //--------------------------------------------------------------------------
    // Free the second block
    heap.free(alloc_b);

    // Again, the used bytes count decreases by sizeof(BlockHeader) and alloc_b
    // due to the coallescing of free space
    REQUIRE(heap.current_used() == 128);
    REQUIRE(heap.current_allocs() == 1);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // Still zero fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // Now header_b is the "new" free_header
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // header_c, serving as the "new" free_header, will have grown in size
    REQUIRE(header_b->size == 384);

    //--------------------------------------------------------------------------
    // Free the third block
    heap.free(alloc_a);

    // Finally, everything's free so only the 32 bytes of the heap's header are
    // used
    REQUIRE(heap.current_used() == 32);
    REQUIRE(heap.current_allocs() == 0);
    REQUIRE(heap.peak_used() == 416);
    REQUIRE(heap.peak_allocs() == 3);

    // And certainly zero fragmentation with everything free
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.0f, epsilon));

    // There's no more free block at the end of the heap, so header_a->next
    // points nowhere
    REQUIRE(header_a->next == nullptr);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // And the size of header_a should be the whole available heap
    REQUIRE(header_a->size == 480);
}

And testing four blocks.

#include "brasstacks/memory/BlockHeader.hpp"
#include "brasstacks/memory/Heap.hpp"

#include "test_helpers.hpp"

using namespace btx::memory;
using namespace Catch::Matchers;

TEST_CASE("Allocate four blocks, free a and c, then allocate a block that's "
          "less than c, testing fragmentation")
{
    std::size_t const heap_size = 1280;
    Heap heap(heap_size);

    std::size_t const size_a = 96;
    std::size_t const size_b = 128;
    std::size_t const size_c = 256;
    std::size_t const size_d = 512;

    void *alloc_a = heap.alloc(size_a);
    void *alloc_b = heap.alloc(size_b);
    void *alloc_c = heap.alloc(size_c);
    void *alloc_d = heap.alloc(size_d);

    // Check the heap's internal metrics
    REQUIRE(heap.current_used() == 1152);
    REQUIRE(heap.current_allocs() == 4);
    REQUIRE(heap.peak_used() == heap.current_used());
    REQUIRE(heap.peak_allocs() == heap.current_allocs());

    // Check that the BlockHeader helper functions produce interchangable
    // addresses
    BlockHeader *header_a = BlockHeader::header(alloc_a);
    REQUIRE(header_a->size == size_a);
    REQUIRE(alloc_a == BlockHeader::payload(header_a));

    BlockHeader *header_b = BlockHeader::header(alloc_b);
    REQUIRE(header_b->size == size_b);
    REQUIRE(alloc_b == BlockHeader::payload(header_b));

    BlockHeader *header_c = BlockHeader::header(alloc_c);
    REQUIRE(header_c->size == size_c);
    REQUIRE(alloc_c == BlockHeader::payload(header_c));

    BlockHeader *header_d = BlockHeader::header(alloc_d);
    REQUIRE(header_d->size == size_d);
    REQUIRE(alloc_d == BlockHeader::payload(header_d));

    // And the free block is 32 bytes in size, given a 32 byte BlockHeader
    BlockHeader const *free_header = heap.free_head();
    REQUIRE(free_header->size == 128);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == nullptr);

    // Check the physical locations in memory
    uint8_t const *raw_heap = heap.raw_heap();
    REQUIRE(reinterpret_cast<uint8_t *>(header_a) == raw_heap);
    REQUIRE(reinterpret_cast<uint8_t *>(header_b) == raw_heap + 128);
    REQUIRE(reinterpret_cast<uint8_t *>(header_c) == raw_heap + 288);
    REQUIRE(reinterpret_cast<uint8_t *>(header_d) == raw_heap + 576);
    REQUIRE(reinterpret_cast<uint8_t const *>(free_header) == raw_heap + 1120);

    //--------------------------------------------------------------------------
    // Free alloc_a
    heap.free(alloc_a);

    // The internal metrics will largely be the same, except with size_a fewer
    // used bytes and one fewer allocs
    REQUIRE(heap.current_used() == 1056);
    REQUIRE(heap.current_allocs() == 3);
    REQUIRE(heap.peak_used() == 1152);
    REQUIRE(heap.peak_allocs() == 4);

    // 96+128=224 bytes free, so that's ~0.43 fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.42857143f, epsilon));

    // header_a, while now free, has the same size as it did before
    REQUIRE(header_a->size == 96);

    // As does free_header
    REQUIRE(free_header->size == 128);

    // header_a has become the "true" free_header, which means the next pointer
    // directs us to the free chunk at the end of the heap
    REQUIRE(header_a->next == free_header);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == nullptr);
    REQUIRE(header_c->prev == nullptr);
    REQUIRE(header_d->next == nullptr);
    REQUIRE(header_d->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_a);

    //--------------------------------------------------------------------------
    // Free alloc_c
    heap.free(alloc_c);

    // The internal metrics will largely be the same, except with size_a fewer
    // used bytes and one fewer allocs
    REQUIRE(heap.current_used() == 800);
    REQUIRE(heap.current_allocs() == 2);
    REQUIRE(heap.peak_used() == 1152);
    REQUIRE(heap.peak_allocs() == 4);

    // 96+256+128=480 bytes free, so that's ~0.467 fragmentation
    REQUIRE_THAT(heap.calc_fragmentation(), WithinAbs(0.46666667f, epsilon));

    // alloc_c was before the free block at the end, so header_a->next now
    // points to alloc_c
    REQUIRE(header_a->next == header_c);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_c->next == free_header);
    REQUIRE(header_c->prev == header_a);
    REQUIRE(header_d->next == nullptr);
    REQUIRE(header_d->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == header_c);

    //--------------------------------------------------------------------------
    // Allocate a smaller chunk where alloc_d used to be, but larger than
    // alloc_a
    std::size_t const size_e = 128;
    void *alloc_e = heap.alloc(size_e);
    BlockHeader *header_e = BlockHeader::header(alloc_e);
    REQUIRE(alloc_e == BlockHeader::payload(header_e));
    REQUIRE(header_e->size == size_e);

    // The newest allocation, f, will live where d once was.
    REQUIRE(alloc_e == alloc_c);
    REQUIRE(header_e == header_c);

    auto *free_half_of_c =  reinterpret_cast<BlockHeader *>(
        reinterpret_cast<uint8_t *>(header_e)
        + sizeof(BlockHeader)
        + size_e
    );

    // Now we can test the pointer layout
    REQUIRE(header_a->next == free_half_of_c);
    REQUIRE(header_a->prev == nullptr);
    REQUIRE(header_b->next == nullptr);
    REQUIRE(header_b->prev == nullptr);
    REQUIRE(header_e->next == nullptr);
    REQUIRE(header_e->prev == nullptr);
    REQUIRE(free_half_of_c->next == free_header);
    REQUIRE(free_half_of_c->prev == header_a);
    REQUIRE(header_d->next == nullptr);
    REQUIRE(header_d->prev == nullptr);
    REQUIRE(free_header->next == nullptr);
    REQUIRE(free_header->prev == free_half_of_c);

    // And the size of the new free half of C
    REQUIRE(free_half_of_c->size == 96);
}

Answer 1

You are overthinking alignment

malloc() and new will return a pointer that is already suitably aligned for any built-in type, including pointers and std::size_t. So you don't have to worry about properly aligning it to store the first BlockHeader. This also means you can get rid of the alignas for BlockHeader (it is meaningless anyway, since you are not using new to allocate it).

You also didn't actually handle alignment at all in the constructor; you just adjust the amount of bytes you reserve, but if malloc() would return something not aligned to ALIGN, the reinterpret_cast<BlockHeader*>(_raw_heap) would be very wrong.

Use new and placement-new

malloc() is a C function, if you want to write proper C++ code you should use new. To allocate memory for the heap you can just do:

_raw_heap = new uint8_t[_total_size];

You could even make _raw_heap a std::unique_ptr<uint8_t[]> so you don't have to worry about delete.

When creating an instance of a BlockHeader, use placement-new. This ensures the constructor will be called, and more importantly, will ensure the compiler and/or static-analysis tools can see that there is a valid live BlockHeader object:

_free_head = new (_raw_heap) BlockHeader;

Of course you should then also ensure you don't delete the constructor of BlockHeader.

Simplify casts

You can avoid some unnecessary casts by doing pointer arithmetic on BlockHeader* instead of uint8_t*:

[[nodiscard]] static inline BlockHeader * header(void *address) {
    return static_cast<BlockHeader *>(address) - 1;
}

[[nodiscard]] static inline void * payload(BlockHeader *header) {
    return header + 1; // implicit conversion to void* is perfecly fine
}

You can move the declaration of BlockHeader into Heap

BlockHeader is only used as an implementation detail of Heap. It therefore doesn't need to be in the global namespace. You can nest structs in C++, so I would write this in Heap.hpp:

class Heap final {
    struct BlockHeader; // forward declaration
    …
};

And the actual definition can be in Heap.cpp:

struct Heap::BlockHeader {
    [[nodiscard]] static BlockHeader *header(void *address) {
        return static_cast<BlockHeader *>(address) - 1;
    }

    [[nodiscard]] static void *payload(BlockHeader *header) {
        return header + 1; // implicit conversion to void* is perfecly fine
    }
    
    std::size_t size{};
    BlockHeader *next{};
    BlockHeader *prev{};
};

Use of assert()

You should only use assert() to catch bugs in the program. However, some errors are not caused by bugs. For example, malloc() might return nullptr because there is not enough memory. If you compiled your code with -DNDEBUG (which many build systems automatically add in release builds), then your assert() calls are not doing anything anymore. Your program will then crash due to a NULL-pointer dereference. It's better to throw an exception, or if you don't want to use exceptions, write an error to std::cerr and call std::abort().

About the unit tests

Opinions about testing varies a lot. However, I would avoid being overly specific in your test cases. For example, in the test for allocating and freeing a single block, you not only test that functionality, you also test if the BlockHeader contains the expected values. The problem is then that if you ever change the implementation of BlockHeader, your test is no longer valid.

Of course, there is value in testing that the internal datastructures are consistent. However, at the very least I would put that into a separate test.

What I am missing is more rigorous testing of the things that should be visible to the user. For example, that alloc_a != nullptr, and that if you make multiple allocations, that they don't overlap. I would also write to the allocated memory: this checks that the pointer is to a valid memory region, and that no header blocks are being overwritten.

Answer 2

Overview

Must say that when reading complex code, the first thing I want to read is the constructor and destructor. Personally I always put these first in a source file. Without understanding these the other functions are hard.

Not sure what you have against zero size memory allocations. You can seriously simplify the code by alowing zero sized allocation (as you don't need to check for nullptrs). Zero size object should still return a pointer.

Also not allowing the free of nullptr. I remember the old days where every call to free() had to check if it was NULL, which meant that everybody wrapped their calls to free() in a custom macro. Simplify everybody's life by allowing calls to free() with nullptr to work as expected.

Algorithm

This is an overly simplistic heap storage mechanism. If this is something you want to have in real code and be performant then you need to improve the process of finding an appropriate free block.

Your current technique is going to lead to extensive fragmentation (much more than is needed). It also is going to become more and more expensive as you fragment that memory.

A very simple but still very good technique is to use a chain of chains. So you have a prev/next chain going across where each element is a different size block. Then each of these blocks has an up/down chain which is a chain of all the free blocks of that size. That way you can very quickly find a list of free blocks of the same size that you want, and then simply use the first element in the chain.

I don't particularly find this statement reliable:

  // Much less likely, but still possible, is finding a block that fits
  // the request exactly, in which case we just need to fix the pointers

This is more likely to the opposite (from the papers I read in my youth).

I will note that in C++ it is very common for applications to allocate/free lots of blocks of the same size in quick succession (i.e pick a spot in the application and the chunks being allocated at that point in time tend to be similar). So keeping recently freed blocks unmerged and ready to be re-used was one of the first optimizations done by the standard memory managers (or at least this was true 30 years ago when I studied the subject, it may not be true anymore, but I suspect it is true enough that it is worth the optimization here).

You can definitely simplify your current free() implementation by using a wrapped linked list. This will result in less checking for nullptr and no special casing when freeing the last element. If you search on the Code Review site for "Linked Lists" and look for information on "Sentinels" you will find implementations that will help you improve your current implementation.

Also it looks like you are defragmenting after every call to free(). That is not probably not the best use of CPU resources. Sure you can do defragementaion sweeps once in a while, but you don't need to do it on every call.

CodeReview

Very nice. I don't see many (or any) people trying to align data. But I suppose in this situation that becomes important.

struct alignas(16) BlockHeader final {
    // ^^^^^^^^^^^

My worry is the "Magic Number" 16. Does this happen to be the maximum alignment on your system? I am not sure that will hold true everywhere. There is a specific type for getting the maximum alignment: max_align_t.

But if you do have an alternative reason for using the magic number 16: I don't mind its use, but then you have to explain why you are using it. So this deserves some more comments (In the code don't explain to me in the comments, I am not that important. But the next person reading your code may own an axe).

---

Should these be using reinterpret_cast<>() or the new bit_cast<>()?

    [[nodiscard]] static inline BlockHeader * header(void *address) {
        return reinterpret_cast<BlockHeader *>(
            reinterpret_cast<uint8_t *>(address) - sizeof(BlockHeader)
        );
    }

    [[nodiscard]] static inline void * payload(BlockHeader *header) {
        return reinterpret_cast<uint8_t *>(header) + sizeof(BlockHeader);
    }

Also these functions have some stringent real world requirements. The header() function definitely expects the parameter to be aligned to 16 byte boundry. If this is not true I would terminate the application immediately, as something has then gone horribly wrong.

---

Nice comment.

    std::size_t size = 0; // The size stored here refers to the space available
                          // for user allocation. Said another way, it's the
                          // size of the whole block, minus sizeof(BlockHeader).

---

#include "brasstacks/memory/BlockHeader.hpp"

// SUFF..

namespace btx::memory {

struct BlockHeader;

Is this not why you include the above header file!
You don't need both.

I would remove the local forward declaration. That way you know your declaration is consistent and always in one place.

---

This is unnecessary.

    Heap() = delete;

    explicit Heap(std::size_t const req_bytes);

Any definition of a constructor removes the compiler defined default constructor.

---

Personally. I don't see the need to delete the move operator.

    Heap(Heap &&other) = delete;
    Heap(Heap const &) = delete;

    Heap & operator=(Heap &&other) = delete;
    Heap & operator=(Heap const &) = delete;

I can definitely see use cases where you want to create the heap in one context but save it in another without having to rely on dynamic allocation.

---

Heap::Heap(std::size_t const req_bytes) :


    // So long as BlockHeader's size is a power of two, this rounding to a
    // multiple math is safe
    int32_t constexpr ALIGN = sizeof(BlockHeader) * 2;
    std::size_t const bytes = (req_bytes + ALIGN - 1) & -ALIGN;

You are assuming 2's compliment arithmatic. I know its by far the most common form of negative value representation. But it is not the only one. Also I always worry about not using the same type and having to convince myself there is no funny compiler type conversion between signed and unsigned types that I forgot about.

Why not simply do the binary operation?

    // Assuming BlockHeader's size is a power of 2.
    std::size_t constexpr align = sizeof(BlockHeader) * 2;
    std::size_t constexpr bottomBits = sizeof(BlockHeader) - 1;
    std::size_t constexpr mask = ~bottomBits;
    std::size_t  bytes = (req_bytes + align - 1) & mask;

---

Don't see the need to dip into C here.

    _raw_heap = reinterpret_cast<uint8_t *>(::malloc(_total_size));
    assert(_raw_heap != nullptr && "Heap allocation failed");

Just use new to allocate the raw memory. Then you don't need to worry about issues of mixed storage space (note: it is uncommon, but C and C++ are not required to use the same memory allocation storage). Also makes it easier to make _raw_heap a std::unique_ptr.

    _raw_heap = std::make_unique<uint8_t>(_total_size);

---

void * Heap::alloc(std::size_t const req_bytes) {
    if(req_bytes <= 0) {
        assert(false && "Cannot allocate zero or fewer bytes");
        return nullptr;
    }

I would note that req_bytes can never be negative. Any negative value you passed has already been converted into a very large positive value by the standard integer conversion rules.

---

void * Heap::alloc(std::size_t const req_bytes) {
    // STUFF

Why are you aligning to a different type?

    int32_t constexpr ALIGN = sizeof(void *);
    bytes = (bytes + ALIGN - 1) & -ALIGN;

Don't you want to be consistent with your other alignment? I think this deserves a very explicit comment on why you are using this as the alignment type.

---

void * Heap::alloc(std::size_t const req_bytes) { // STUFF

    while(current_header != nullptr) {
        // This is const across all loops.
        // Pull it outside the while.
        std::size_t const size_of_new_block = bytes + sizeof(BlockHeader);

---

void Heap::free(void *address) {
  
    // Not sure why you are wasting your time doing this.
    address = nullptr;
}

---

This function is very similar to the the tail of the previous function _split_free_block(). Don't repeat code if you don't have to!

void Heap::_use_whole_free_block(BlockHeader *header) {
    if(header->next != nullptr) {
        header->next->prev = header->prev;
    }

    if(header->prev != nullptr) {
        header->prev->next = header->next;
    }

    if(header == _free_head) {
        _free_head = _free_head->next;
    }

    header->next = nullptr;
    header->prev = nullptr;
}

But if there was an error you now have to remember to fix the bug in two places. By correctly re-using code you will only have the bug in one location.