C++ imitation of glibc malloc(), free()

Question

I wrote a C++ simulator that performs algorithms for glibc malloc() and free().

The core logic is basically the same, with the following differences:

• chunk alignment unit is sizeof(Chunk) (32 in a typical 64bit machine), whereas in glibc it is 2 * sizeof(size_t) (16 in a typical 64bit machine). glibc uses an equilibristic hack for that (frequent casting between size_t and Chunk*). I think I can simulate that as well, but writing this was already too tired...

• when an arena runs out of memory, glibc requests another arena via sysmalloc(). My simulator uses std::vector<unsigned char> as arena, and all the allocated pointers are on that vector, so expanding arena will invalidate all allocated pointers. I don't know a simple way to mitigate this.

Code:

#include <algorithm>
#include <bit>
#include <cassert>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <ranges>
#include <stdexcept>
#include <unordered_map>
#include <random>
#include <vector>


// sizeof(Chunk) == 32 in typical 64bit machines,
// but the 'foot' of the current chunk is actually
// represented as the prev_size of the (unallocated) next chunk
// foot - head it is at least and aligned as sizeof(Chunk)
// sizeof(Chunk) should be a power of 2

// chunks are look like this:
//
// chunk->     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             |             Size of previous chunk, if unallocated (U clear)  |
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             |             Size of chunk, in bytes                     |0|U|I|
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             | Forward pointer to next chunk in list (only used if free)     |
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             | Back pointer to previous chunk in list (only used if free)    |
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             |             Unused space (multiple of sizeof(Chunk) bytes)    |
// nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//     `foot:' |             Size of chunk, in bytes (written by prev chunk)   |
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//             |             Size of next chunk, in bytes                |0|U|I|
//             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

struct Chunk {
    std::size_t prev_size_ = 0;
    // invariant: size_ > 0
    // invariant: rightmost three (or two) bits of size_ are flags (CHUNK_IN_USE,
    // CHUNK_UNSORTED)
    std::size_t size_ = 0;
    // pointers to prev/next within bins, only used for free chunks.
    // nothing to do with prev/next chunks within the global arena, beware!
    Chunk* next_ = nullptr;
    Chunk* prev_ = nullptr;
};

static_assert(sizeof(std::size_t) == 8 || sizeof(std::size_t) == 4);
constexpr std::size_t CHUNK_IN_USE = 0x1;
constexpr std::size_t CHUNK_UNSORTED = 0x2;
constexpr std::size_t CHUNK_FLAG_MASK = 0x7;
constexpr std::size_t CHUNK_FLAG_UNMASK =
        (sizeof(std::size_t) == 8) ? 0xFFFFFFFFFFFFFFF8 : 0xFFFFFFF8;

struct GetSize {
    std::size_t operator()(Chunk* iter) const noexcept {
        assert(iter);
        return iter->size_;
    }
};

class AllocManager {
private:
    static constexpr std::size_t chunk_alignment_ = sizeof(Chunk);
    static_assert(std::has_single_bit(chunk_alignment_));
    static constexpr std::size_t align_multiplier = (sizeof(std::size_t) == 8) ? 1UL : 2UL;
    static constexpr std::size_t bin_shift_ = (sizeof(std::size_t) == 8) ? 5UL : 4UL;
    static constexpr std::size_t num_fast_bins_ = 8UL * align_multiplier;
    static constexpr std::size_t num_small_bins_ = 56UL * align_multiplier;

    static constexpr std::size_t min_fast_size_ = chunk_alignment_;
    static constexpr std::size_t min_small_size_ = chunk_alignment_ * num_fast_bins_;
    static constexpr std::size_t min_large_size_ =
            chunk_alignment_ * (num_small_bins_ + num_fast_bins_);

    std::size_t curr_pool_size_ = 0;

    // bins that store chunks of 32, 64, 96, ..., 224 bytes respectively
    // (or 16, 32, ..., 112)
    // LIFO singly linked list, NOT merged when freed
    std::vector <Chunk*> fast_bins_;

    // bins that store chunks of 256, 288, ..., 2016 bytes respectively
    // (or 128, 144, ..., 1008)
    // FIFO doubly linked list, chunks are merged with adjacent chunks when freed
    // if adjacent
    std::vector <Chunk*> small_bins_;

    // a *single* bin that store chunks of 2048+ bytes (or 1024+)
    // maintain the sorted order w.r.t. chunk size in *increasing* order
    // chunks are merged with adjacent chunks when freed if adjacent
    std::vector <Chunk*> large_bin_;

    // a bin for freed chunks and remainder chunks
    // when an allocation request fails to search chunk in other bins,
    // this bin is searched
    Chunk* unsorted_bin_ = nullptr;

    Chunk* top_chunk_ = nullptr;

    // store *all* chunks
    std::vector <unsigned char> all_chunks_;

public:
    AllocManager(std::size_t init_pool_size)
            : curr_pool_size_{init_pool_size}, fast_bins_(num_fast_bins_, nullptr),
              small_bins_(num_small_bins_, nullptr), all_chunks_(init_pool_size) {
        assert(init_pool_size % chunk_alignment_ == 0);
        top_chunk_ = first_chunk();
        set_size(top_chunk_, init_pool_size);
    }

private:
    [[nodiscard]] bool is_begin(const Chunk* chunk) const noexcept {
        assert(chunk);
        assert(reinterpret_cast<const unsigned char*>(chunk) >=
               all_chunks_.data());
        return reinterpret_cast<const unsigned char*>(chunk) == all_chunks_.data();
    }

    Chunk* first_chunk() noexcept {
        return reinterpret_cast<Chunk*>(all_chunks_.data());
    }

    const Chunk* first_chunk() const noexcept {
        return reinterpret_cast<const Chunk*>(all_chunks_.data());
    }

    // don't need is_last, as top_chunk_ is always the last chunk

    std::size_t* get_foot(Chunk* chunk) noexcept {
        assert(chunk && chunk != top_chunk_);
        return reinterpret_cast<std::size_t*>(reinterpret_cast<unsigned char*>(chunk) +
                                              realsize(chunk));
    }

    const std::size_t* get_foot(const Chunk* chunk) const noexcept {
        assert(chunk && chunk != top_chunk_);
        return reinterpret_cast<const std::size_t*>(
                reinterpret_cast<const unsigned char*>(chunk) + realsize(chunk));
    }

    [[nodiscard]] std::size_t get_flags(const Chunk* chunk) const noexcept {
        assert(chunk);
        return chunk->size_ & CHUNK_FLAG_MASK;
    }

    void set_flags(Chunk* chunk, std::size_t flags) {
        assert(chunk && chunk != top_chunk_);
        chunk->size_ &= CHUNK_FLAG_UNMASK;
        chunk->size_ |= flags;
        // add the foot
        std::size_t* foot = get_foot(chunk);
        *foot &= CHUNK_FLAG_UNMASK;
        *foot |= flags;
    }

    // erase flags and make a nonzero mulitple of chunk_alignment_
    std::size_t realsize(std::size_t sz) const noexcept {
        assert(sz >= chunk_alignment_);
        return (sz >> bin_shift_) << bin_shift_;
    }

    std::size_t realsize(const Chunk* chunk) const noexcept {
        assert(chunk && chunk->size_ >= chunk_alignment_);
        return realsize(chunk->size_);
    }

    void set_size(Chunk* chunk, std::size_t sz) {
        assert(chunk);
        chunk->size_ = sz;
        // add the foot
        if (chunk != top_chunk_) {
            std::size_t* foot = get_foot(chunk);
            *foot = sz;
        }
    }

    std::size_t verify_size(const Chunk* chunk) const noexcept {
        assert(chunk && chunk->size_ >= chunk_alignment_);
        // check the foot
        assert(chunk == top_chunk_ || *get_foot(chunk) == chunk->size_);
        return chunk->size_;
    }

    Chunk* prev_chunk(Chunk* chunk) noexcept {
        if (!chunk || is_begin(chunk)) {
            return nullptr;
        }
        return reinterpret_cast<Chunk*>(reinterpret_cast<unsigned char*>(chunk) -
                                        realsize(chunk->prev_size_));
    }

    const Chunk* prev_chunk(const Chunk* chunk) const noexcept {
        if (!chunk || is_begin(chunk)) {
            return nullptr;
        }
        return reinterpret_cast<const Chunk*>(
                reinterpret_cast<const unsigned char*>(chunk) -
                realsize(chunk->prev_size_));
    }

    Chunk* next_chunk(Chunk* chunk) noexcept {
        if (!chunk || chunk == top_chunk_) {
            return nullptr;
        }
        return reinterpret_cast<Chunk*>(reinterpret_cast<unsigned char*>(chunk) +
                                        realsize(chunk));
    }

    const Chunk* next_chunk(const Chunk* chunk) const noexcept {
        if (!chunk || chunk == top_chunk_) {
            return nullptr;
        }
        return reinterpret_cast<const Chunk*>(
                reinterpret_cast<const unsigned char*>(chunk) + realsize(chunk));
    }

    bool verify_fastbins() const {
        assert(fast_bins_.size() == num_fast_bins_);
        for (std::size_t i = 0; i < num_fast_bins_; ++i) {
            auto chunk = fast_bins_[i];
            while (chunk) {
                assert(realsize(verify_size(chunk)) == fast_size(i));
                assert(get_flags(chunk) == CHUNK_IN_USE);
                chunk = chunk->next_;
            }
        }
        return true;
    }

    bool verify_smallbins() const {
        assert(small_bins_.size() == num_small_bins_);
        for (std::size_t i = 0; i < num_small_bins_; ++i) {
            auto chunk = small_bins_[i];
            while (chunk) {
                assert(verify_size(chunk) == small_size(i));
                assert(chunk->prev_ && chunk->next_ && chunk->prev_->next_ == chunk &&
                       chunk->next_->prev_ == chunk);
                if (chunk == chunk->next_) {
                    assert(chunk == chunk->prev_);
                    break;
                }
                chunk = chunk->next_;
                if (chunk == small_bins_[i]) {
                    break;
                }
            }
        }
        return true;
    }

    bool verify_largebin() const {
        assert(std::ranges::is_sorted(large_bin_, std::ranges::less{}, GetSize{}));
        assert(std::ranges::all_of(large_bin_, [this](const auto& chunk) {
            return chunk && get_flags(chunk) == 0 &&
                   verify_size(chunk) >= min_large_size_ &&
                   (chunk->size_ % chunk_alignment_) == 0;
        }));
        return true;
    }

    bool verify_unsorted() const {
        auto chunk = unsorted_bin_;
        while (chunk) {
            assert(verify_size(chunk) >= chunk_alignment_ &&
                   (realsize(chunk) % chunk_alignment_) == 0);
            assert(get_flags(chunk) == CHUNK_UNSORTED);
            assert(chunk->prev_ && chunk->next_ && chunk->prev_->next_ == chunk &&
                   chunk->next_->prev_ == chunk);
            if (chunk == chunk->next_) {
                assert(chunk == chunk->prev_);
                break;
            }
            chunk = chunk->next_;
            if (chunk == unsorted_bin_) {
                break;
            }
        }
        return true;
    }

    bool verify() const {
        assert(!all_chunks_.empty() && all_chunks_.size() == curr_pool_size_);
        const Chunk* chunk = first_chunk();
        while (chunk) {
            assert(chunk->size_ >= chunk_alignment_ &&
                   (realsize(chunk) % chunk_alignment_) == 0);
            auto next = next_chunk(chunk);
            if (!next) {
                assert(chunk == top_chunk_ && get_flags(chunk) == 0);
                assert(reinterpret_cast<const unsigned char*>(chunk) + chunk->size_ ==
                       all_chunks_.data() + all_chunks_.size());
            }
            chunk = next;
        }
        assert(verify_fastbins());
        assert(verify_smallbins());
        assert(verify_largebin());
        assert(verify_unsorted());
        return true;
    }

    [[nodiscard]] std::size_t fast_index(std::size_t num_bytes) const noexcept {
        return (num_bytes >> bin_shift_);
    }

    [[nodiscard]] std::size_t fast_size(std::size_t idx) const noexcept {
        return (idx << bin_shift_);
    }

    [[nodiscard]] std::size_t small_index(std::size_t num_bytes) const noexcept {
        assert(num_bytes >= min_small_size_);
        return ((num_bytes - min_small_size_) >> bin_shift_);
    }

    [[nodiscard]] std::size_t small_size(std::size_t idx) const noexcept {
        return (idx << bin_shift_) + min_small_size_;
    }

    // where to insert in the large bin
    [[nodiscard]] auto large_iter(std::size_t num_bytes) const noexcept {
        return std::ranges::lower_bound(large_bin_, num_bytes, std::ranges::less{},
                                        GetSize{});
    }

    void unlink_from_bin(Chunk* chunk, Chunk*& bin) {
        assert(chunk && chunk->prev_ && chunk->next_ && bin);
        if (chunk == chunk->prev_) {
            // make bin empty
            assert(chunk == chunk->next_);
            bin = nullptr;
        } else {
            if (chunk == bin) {
                bin = chunk->next_;
            }
            chunk->next_->prev_ = chunk->prev_;
            chunk->prev_->next_ = chunk->next_;
        }
        chunk->prev_ = nullptr;
        chunk->next_ = nullptr;
    }

    void push_front_to_bin(Chunk* chunk, Chunk*& bin) {
        push_back_to_bin(chunk, bin);
        bin = chunk;
    }

    void push_back_to_bin(Chunk* chunk, Chunk*& bin) {
        assert(chunk);
        if (!bin) {
            bin = chunk;
            chunk->prev_ = chunk;
            chunk->next_ = chunk;
        } else {
            chunk->next_ = bin;
            chunk->prev_ = bin->prev_;
            bin->prev_->next_ = chunk;
            bin->prev_ = chunk;
        }
    }

    Chunk* pop_back_from_bin(Chunk*& bin) {
        auto chunk = bin;
        if (chunk) {
            assert(chunk->prev_ && chunk->next_);
            chunk = chunk->prev_;
            unlink_from_bin(chunk, bin);
        }
        return chunk;
    }

    Chunk* pop_front_from_bin(Chunk*& bin) {
        auto chunk = bin;
        if (chunk) {
            assert(chunk->prev_ && chunk->next_);
            unlink_from_bin(chunk, bin);
        }
        return chunk;
    }

    Chunk* pop_fastbin(Chunk*& bin) {
        auto chunk = bin;
        if (chunk) {
            bin = bin->next_;
            chunk->next_ = nullptr;
            assert(!chunk->prev_);
        }
        return chunk;
    }

    void push_fastbin(Chunk* chunk, Chunk*& bin) {
        assert(chunk && !chunk->prev_);
        chunk->next_ = bin;
        bin = chunk;

        // we mark CHUNK_IN_USE for fastbin chunks
        // so that they won't be consolidated.
        set_flags(chunk, CHUNK_IN_USE);
    }

    Chunk* try_alloc_fastbin(std::size_t num_bytes) {
        std::size_t fast_bin_index = fast_index(num_bytes);
        assert(fast_bin_index < num_fast_bins_);
        auto chunk = pop_fastbin(fast_bins_[fast_bin_index]);
        assert(!chunk || get_flags(chunk) == CHUNK_IN_USE);
        return chunk;
    }

    Chunk* try_alloc_smallbin(std::size_t num_bytes) {
        assert(num_bytes >= min_small_size_);
        std::size_t small_bin_index = small_index(num_bytes);
        assert(small_bin_index < num_small_bins_);
        auto chunk = pop_front_from_bin(small_bins_[small_bin_index]);
        if (chunk) {
            set_flags(chunk, CHUNK_IN_USE);
        }
        return chunk;
    }

    void unlink_chunk(Chunk* chunk) {
        assert(chunk);
        assert(!(get_flags(chunk) & CHUNK_IN_USE));
        auto num_bytes = chunk->size_;
        if (get_flags(chunk) & CHUNK_UNSORTED) {
            assert(unsorted_bin_);
            set_flags(chunk, 0);
            unlink_from_bin(chunk, unsorted_bin_);
        } else if (num_bytes < min_small_size_) {
            // fastbin chunks should never be consolidated by adjacent chunks,
            // they should be retrieved only upon malloc requests
            assert(false);
        } else if (num_bytes < min_large_size_) {
            std::size_t small_bin_index = small_index(num_bytes);
            assert(small_bin_index < num_small_bins_ && small_bins_[small_bin_index]);
            unlink_from_bin(chunk, small_bins_[small_bin_index]);
        } else if (chunk != top_chunk_) {
            auto where = large_iter(num_bytes);
            assert(where != large_bin_.end() && (*where)->size_ == num_bytes);
            while (*where != chunk) {
                ++where;
            }
            assert(where != large_bin_.end() && *where == chunk);
            large_bin_.erase(where);
        } else {
            assert(chunk == top_chunk_);
        }
    }

    void consolidate_chunk(Chunk* chunk) {
        assert(chunk);
        auto size = chunk->size_;
        auto next = next_chunk(chunk);
        while (!is_begin(chunk) && !(chunk->prev_size_ & CHUNK_IN_USE)) {
            auto prev = prev_chunk(chunk);
            assert(prev->size_);
            unlink_chunk(prev);
            assert(get_flags(prev) == 0);
            size += prev->size_;
            chunk = prev;
        }
        bool next_was_top = false;
        while (next && !(next->size_ & CHUNK_IN_USE)) {
            assert(next->size_);
            unlink_chunk(next);
            assert(get_flags(next) == 0);
            size += next->size_;
            next_was_top = (next == top_chunk_);
            next = next_chunk(next);
        }
        if (!next_was_top) {
            set_size(chunk, size);
            push_front_to_bin(chunk, unsorted_bin_);
            set_flags(chunk, CHUNK_UNSORTED);
        } else {
            top_chunk_ = chunk;
            set_size(chunk, size);
        }
    }

    void consolidate_fastbin() {
        for (std::size_t i = 0; i < num_fast_bins_; ++i) {
            while (fast_bins_[i]) {
                auto chunk = pop_fastbin(fast_bins_[i]);
                set_flags(chunk, 0);
                consolidate_chunk(chunk);
            }
        }
    }

    void place_in_bins(Chunk* chunk) {
        assert(chunk && get_flags(chunk) == 0);
        auto num_bytes = chunk->size_;
        if (num_bytes < min_small_size_) {
            push_fastbin(chunk, fast_bins_[fast_index(num_bytes)]);
        } else if (num_bytes < min_large_size_) {
            push_back_to_bin(chunk, small_bins_[small_index(num_bytes)]);
        } else {
            large_bin_.insert(large_iter(num_bytes), chunk);
        }
    }

    Chunk* split_chunk_after(Chunk* chunk, std::size_t offset) {
        assert(chunk && (chunk != top_chunk_) && offset >= chunk_alignment_ &&
               (offset % chunk_alignment_) == 0 &&
               realsize(chunk) >= offset + sizeof(Chunk) &&
               (realsize(chunk) - offset) % chunk_alignment_ == 0);

        auto split_size = realsize(chunk) - offset;

        // set new size of the current (left) chunk and erase flags
        set_size(chunk, offset);

        Chunk* split_chunk = reinterpret_cast<Chunk*>(
                reinterpret_cast<unsigned char*>(chunk) + offset);
        assert(split_chunk->prev_size_ == offset);
        split_chunk->prev_ = nullptr;
        split_chunk->next_ = nullptr;
        set_size(split_chunk, split_size);
        assert(split_chunk == next_chunk(chunk));
        assert(verify_size(split_chunk) == split_size);
        return split_chunk;
    }

    Chunk* try_alloc_unsorted(std::size_t num_bytes) {
        while (unsorted_bin_) {
            auto chunk = pop_front_from_bin(unsorted_bin_);
            assert(chunk && get_flags(chunk) == CHUNK_UNSORTED);
            set_flags(chunk, 0);

            // for small requests, if this is the last unsorted,
            // then split and take if possible
            if (!unsorted_bin_ && num_bytes < min_large_size_ &&
                chunk->size_ >= num_bytes + chunk_alignment_) {
                auto remainder = split_chunk_after(chunk, num_bytes);
                set_flags(chunk, CHUNK_IN_USE);
                set_flags(remainder, CHUNK_UNSORTED);
                push_front_to_bin(remainder, unsorted_bin_);
                return chunk;
            }

            // use this if exact fit
            if (chunk->size_ == num_bytes) {
                set_flags(chunk, CHUNK_IN_USE);
                return chunk;
            }

            place_in_bins(chunk);
        }
        return nullptr;
    }

    Chunk* try_alloc_largebin(std::size_t num_bytes) {
        assert(num_bytes >= min_large_size_ && (num_bytes % chunk_alignment_) == 0);
        auto where = large_iter(num_bytes);

        if (where == large_bin_.end()) {
            // no large bin chunk is available
            return nullptr;
        } else {
            // best fit
            auto chunk = *where;
            assert(get_flags(chunk) == 0);
            assert(chunk->size_ >= num_bytes);
            large_bin_.erase(where);
            if (chunk->size_ == num_bytes) {
                // use if exact fit
                set_flags(chunk, CHUNK_IN_USE);
                return chunk;
            } else if (chunk->size_ >= num_bytes + chunk_alignment_) {
                assert((chunk->size_ - num_bytes) % chunk_alignment_ == 0);
                // split to take remainder
                auto remainder = split_chunk_after(chunk, num_bytes);
                set_flags(chunk, CHUNK_IN_USE);
                place_in_bins(remainder);
                return chunk;
            }
        }
    }

    Chunk* alloc_top(std::size_t num_bytes) {
        assert(num_bytes >= chunk_alignment_ &&
               (num_bytes % chunk_alignment_) == 0);
        assert(get_flags(top_chunk_) == 0);
        if (top_chunk_->size_ < num_bytes + chunk_alignment_) {
            // TODO: how to deal with this?
            throw std::runtime_error("memory pool is not enough");
        }

        assert((top_chunk_->size_ % chunk_alignment_ == 0) &&
               top_chunk_->size_ >= num_bytes + chunk_alignment_ &&
               (top_chunk_->size_ - num_bytes) % chunk_alignment_ == 0);

        auto chunk = top_chunk_;

        auto split_size = top_chunk_->size_ - num_bytes;
        // set new size of the current (left) chunk and erase flags
        top_chunk_->size_ = num_bytes;
        Chunk* split_chunk = reinterpret_cast<Chunk*>(
                reinterpret_cast<unsigned char*>(top_chunk_) + num_bytes);
        assert(split_chunk);
        std::size_t* foot = reinterpret_cast<std::size_t*>(split_chunk);
        *foot = num_bytes;
        assert(split_chunk->prev_size_ == num_bytes);
        split_chunk->prev_ = nullptr;
        split_chunk->next_ = nullptr;
        split_chunk->size_ = split_size;
        top_chunk_ = split_chunk;
        assert(split_chunk == next_chunk(chunk));
        assert(split_chunk == top_chunk_);
        set_flags(chunk, CHUNK_IN_USE);
        return chunk;
    }

    std::size_t request_to_sz(std::size_t num_bytes) {
        return ((num_bytes / chunk_alignment_) * chunk_alignment_) +
               ((num_bytes % chunk_alignment_) ? chunk_alignment_ : 0);
    }

public:
    void* alloc_chunk(std::size_t num_bytes) {
        num_bytes = request_to_sz(num_bytes);
        assert(num_bytes >= min_fast_size_ && num_bytes % chunk_alignment_ == 0);
        if (num_bytes < min_small_size_) {
            auto res = try_alloc_fastbin(num_bytes);
            if (res) {
                assert(res->size_ == (num_bytes | CHUNK_IN_USE));
                assert(verify());
                return reinterpret_cast<void*>(res);
            }
        } else if (num_bytes < min_large_size_) {
            auto res = try_alloc_smallbin(num_bytes);
            if (res) {
                assert(res->size_ == (num_bytes | CHUNK_IN_USE));
                assert(verify());
                return reinterpret_cast<void*>(res);
            }
        } else {
            consolidate_fastbin();
            assert(verify());
        }
        {
            auto res = try_alloc_unsorted(num_bytes);
            if (res) {
                assert(res->size_ == (num_bytes | CHUNK_IN_USE));
                assert(verify());
                return reinterpret_cast<void*>(res);
            }
        }
        auto res = alloc_top(num_bytes);
        assert(res && res->size_ == (num_bytes | CHUNK_IN_USE));
        assert(verify());
        return reinterpret_cast<void*>(res);
    }

    void dealloc_chunk(void* ptr) {
        assert(ptr);
        Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
        assert(get_flags(chunk) == CHUNK_IN_USE);
        set_flags(chunk, 0);
        assert(chunk != top_chunk_);
        if (next_chunk(chunk) != top_chunk_ && chunk->size_ < min_small_size_) {
            push_fastbin(chunk, fast_bins_[fast_index(chunk->size_)]);
        } else {
            consolidate_chunk(chunk);
        }
        assert(verify());
    }
};


int main() {
    AllocManager simulator(1UL << 24UL);

    std::mt19937 gen(std::random_device{}());
    // will be multiplied by alignment
    std::gamma_distribution <> chunk_size_dist(2, 2);
    constexpr std::size_t chunk_align = 8UL;
    constexpr int num = 200'000;

    std::bernoulli_distribution to_alloc_or_dealloc(0.65);
    std::bernoulli_distribution large_or_small(0.05);
    std::unordered_map <void*, std::size_t> allocated;
    std::unordered_map <void*, std::size_t> allocated_std;

    float my_alloc_duration = 0.0f;
    float std_alloc_duration = 0.0f;

    for (int i = 0; i < num; ++i) {
        if (to_alloc_or_dealloc(gen)) {
            auto sz = (1 + static_cast<std::size_t>(chunk_size_dist(gen))) * chunk_align;
            if (large_or_small(gen)) {
                sz += 1024;
            }
            auto start = std::chrono::steady_clock::now();
            auto cnk = simulator.alloc_chunk(sz);
            auto end = std::chrono::steady_clock::now();
            my_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                    end - start).count();
            allocated[cnk] = sz;
            start = std::chrono::steady_clock::now();
            void* ptr = std::malloc(sz);
            end = std::chrono::steady_clock::now();
            std_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                    end - start).count();
            allocated_std[ptr] = sz;
        } else {
            if (!allocated.empty()) {
                auto[cnk, sz] = *allocated.begin();
                auto start = std::chrono::steady_clock::now();
                simulator.dealloc_chunk(cnk);
                auto end = std::chrono::steady_clock::now();
                my_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                        end - start).count();
                allocated.erase(allocated.begin());
                assert(!allocated_std.empty());
                auto[ptr, sz2] = *allocated_std.begin();
                start = std::chrono::steady_clock::now();
                std::free(ptr);
                end = std::chrono::steady_clock::now();
                std_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                        end - start).count();
                allocated_std.erase(allocated_std.begin());
            }
        }
    }
    std::cout << "AllocManager elapsed " << my_alloc_duration / 1000.0f << "ms\n";
    std::cout << "std::malloc std::free elapsed " << std_alloc_duration / 1000.0f << "ms\n";
}

Result in my machine: (gcc 11.2 -O3)

frozenca::AllocManager elapsed 12.2252ms
std::malloc std::free elapsed 26.1129ms

Answer 1

General Observations

You did a lot of work and it is a very interesting question. You know more about the most recent versions (C++17 and C++20) of C++ than I do.

You do need to do learn more about object oriented design, the AllocManager manager class is too complex (does too much), quite possibly you could have an abstract bins class that each bin could inherit from, an example of this might be an abstract verify function that works differently for each bin. The Chunk struct might also be a class, you could move some of the code from the AllocManager class into the Chunk struct as well.

The organization of this code review is to go from general comments to specific issues. At the end of the answer the code has been reorganized into multiple files, which is a beginning to how I would have written the program.

Solid Programming

SOLID is 5 object oriented design principles. SOLID is a mnemonic acronym for five design principles intended to make software designs more understandable, flexible and maintainable. This will help you design your objects and classes better.

1. The Single Responsibility Principle - A class should only have a single responsibility, that is, only changes to one part of the software's specification should be able to affect the specification of the class.
2. The Open–closed Principle - states software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification.
3. The Liskov Substitution Principle - Objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.
4. The Interface segregation principle - states that no client should be forced to depend on methods it does not use.
5. The Dependency Inversion Principle - is a specific form of decoupling software modules. When following this principle, the conventional dependency relationships established from high-level, policy-setting modules to low-level, dependency modules are reversed, thus rendering high-level modules independent of the low-level module implementation details.

At a minimum this code violates the Single Responsibility Principle and may violate the Interface segregation principle.

Program Organization

Rather than putting all of the code into a single file the program should be organized with header files and source code files. The header files define the interfaces that the code will use, the source files contain most of the executable code. This allows faster build times for performing maintenance. It also allows the code to be modular and reusable.

In C++ classes are generally defined in header files, some very simple functions or methods can also be coded in the header file, but generally the executable code is in C++ source files so that bug fixing is limited to the specific area where a problem exists. This also makes adding features easier. This is different then coding in C# or Java.

Not all of the functions and methods a class uses need to be declared in in the class if the code is organized this way, if you look at the alternate AllocManager.cpp you will see that some of the functions are static functions declared in the file. This provides even more protection than private or protected variables and methods since static variables can't be accessed outside the program module.

Object Organization

A convention in all object oriented programming is that the public interfaces are all declared at the top of the class, this allows the users of the class to quickly find the interfaces they need without examining all of the code. Mixing up the public and private declarations can definitely cause confusion to the programmers that need to interface with the class.

Issues

Use the assert Macro Only in Debug Mode

The code depends on the assert macro very heavily, you need to be aware that if you compile this for production (optimized with no debug mode set) that all of the assert statements will be null. Any errors you want the code to generate in production/release mode need to use if statements and properly report the errors. Here are 2 references cplusplus.com and cppreference.com.

All Paths in a Function Should Return a Value

When I compile, I use the -Wall flag to report all warnings. I found this warning message: warning C4715: 'AllocManager::try_alloc_largebin': not all control paths return a value. This indicates that the function may return unknown values in some cases, one way to ensure the function returns a value is to only return a value at the end of the function, declare a variable of the proper type and initialize it to a default value, then set the variable in the code where you currently have the return statements. The following function generates a warning message in my compiler:

Chunk* try_alloc_largebin(std::size_t num_bytes) {
    assert(num_bytes >= min_large_size_ && (num_bytes % chunk_alignment_) == 0);
    auto where = large_iter(num_bytes);

    if (where == large_bin_.end()) {
        // no large bin chunk is available
        return nullptr;
    }
    else {
        // best fit
        auto chunk = *where;
        assert(get_flags(chunk) == 0);
        assert(chunk->size_ >= num_bytes);
        large_bin_.erase(where);
        if (chunk->size_ == num_bytes) {
            // use if exact fit
            set_flags(chunk, CHUNK_IN_USE);
            return chunk;
        }
        else if (chunk->size_ >= num_bytes + chunk_alignment_) {
            assert((chunk->size_ - num_bytes) % chunk_alignment_ == 0);
            // split to take remainder
            auto remainder = split_chunk_after(chunk, num_bytes);
            set_flags(chunk, CHUNK_IN_USE);
            place_in_bins(remainder);
            return chunk;
        }
    }
}

Reorganized Code

Chunk.h

#ifndef CHUNK_H

struct Chunk {
    std::size_t prev_size_ = 0;
    // invariant: size_ > 0
    // invariant: rightmost three (or two) bits of size_ are flags (CHUNK_IN_USE,
    // CHUNK_UNSORTED)
    std::size_t size_ = 0;
    // pointers to prev/next within bins, only used for free chunks.
    // nothing to do with prev/next chunks within the global arena, beware!
    Chunk* next_ = nullptr;
    Chunk* prev_ = nullptr;
};

static_assert(sizeof(std::size_t) == 8 || sizeof(std::size_t) == 4);
constexpr std::size_t CHUNK_IN_USE = 0x1;
constexpr std::size_t CHUNK_UNSORTED = 0x2;
constexpr std::size_t CHUNK_FLAG_MASK = 0x7;
constexpr std::size_t CHUNK_FLAG_UNMASK =
(sizeof(std::size_t) == 8) ? 0xFFFFFFFFFFFFFFF8 : 0xFFFFFFF8;

#endif // !CHUNK_H

AllocManager.h

#ifndef ALLOCMANAGER_H
#include <vector>
#include "chunk.h"

class AllocManager
{
public:
    AllocManager(std::size_t init_pool_size);
    void* alloc_chunk(std::size_t num_bytes);
    void dealloc_chunk(void* ptr);

private:
    [[nodiscard]] bool is_begin(const Chunk* chunk) const noexcept;

    Chunk* first_chunk() noexcept {
        return reinterpret_cast<Chunk*>(all_chunks_.data());
    }

    const Chunk* first_chunk() const noexcept {
        return reinterpret_cast<const Chunk*>(all_chunks_.data());
    }

    // don't need is_last, as top_chunk_ is always the last chunk
    std::size_t* get_foot(Chunk* chunk) noexcept;
    const std::size_t* get_foot(const Chunk* chunk) const noexcept;

    [[nodiscard]] std::size_t get_flags(const Chunk* chunk) const noexcept;

    void set_flags(Chunk* chunk, std::size_t flags);

    // erase flags and make a nonzero mulitple of chunk_alignment_
    std::size_t realsize(std::size_t sz) const noexcept;
    std::size_t realsize(const Chunk* chunk) const noexcept;

    void set_size(Chunk* chunk, std::size_t sz);
    std::size_t verify_size(const Chunk* chunk) const noexcept;

    Chunk* prev_chunk(Chunk* chunk) noexcept;

    const Chunk* prev_chunk(const Chunk* chunk) const noexcept;

    Chunk* next_chunk(Chunk* chunk) noexcept;

    const Chunk* next_chunk(const Chunk* chunk) const noexcept;

    bool verify_fastbins() const;
    bool verify_smallbins() const;
    bool verify_largebin() const;
    bool verify_unsorted() const;
    bool verify() const;

    // where to insert in the large bin
    [[nodiscard]] auto large_iter(std::size_t num_bytes) const noexcept;

    void push_fastbin(Chunk* chunk, Chunk*& bin);

    Chunk* try_alloc_fastbin(std::size_t num_bytes);
    Chunk* try_alloc_smallbin(std::size_t num_bytes);

    void unlink_chunk(Chunk* chunk);

    void consolidate_chunk(Chunk* chunk);
    void consolidate_fastbin();

    void place_in_bins(Chunk* chunk);

    Chunk* split_chunk_after(Chunk* chunk, std::size_t offset);

    Chunk* try_alloc_unsorted(std::size_t num_bytes);

    Chunk* try_alloc_largebin(std::size_t num_bytes);

    Chunk* alloc_top(std::size_t num_bytes);


    std::size_t curr_pool_size_ = 0;

    // bins that store chunks of 32, 64, 96, ..., 224 bytes respectively
    // (or 16, 32, ..., 112)
    // LIFO singly linked list, NOT merged when freed
    std::vector <Chunk*> fast_bins_;

    // bins that store chunks of 256, 288, ..., 2016 bytes respectively
    // (or 128, 144, ..., 1008)
    // FIFO doubly linked list, chunks are merged with adjacent chunks when freed
    // if adjacent
    std::vector <Chunk*> small_bins_;

    // a *single* bin that store chunks of 2048+ bytes (or 1024+)
    // maintain the sorted order w.r.t. chunk size in *increasing* order
    // chunks are merged with adjacent chunks when freed if adjacent
    std::vector <Chunk*> large_bin_;

    // a bin for freed chunks and remainder chunks
    // when an allocation request fails to search chunk in other bins,
    // this bin is searched
    Chunk* unsorted_bin_ = nullptr;

    Chunk* top_chunk_ = nullptr;

    // store *all* chunks
    std::vector <unsigned char> all_chunks_;
};

#endif !ALLOCMANAGER_H

AllocManager.cpp

#include <algorithm>
#include <bit>
#include <cassert>
#include <ranges>
#include <stdexcept>
#include "AllocManager.h"

static constexpr std::size_t chunk_alignment_ = sizeof(Chunk);
static_assert(std::has_single_bit(chunk_alignment_));
static constexpr std::size_t align_multiplier = (sizeof(std::size_t) == 8) ? 1UL : 2UL;
static constexpr std::size_t bin_shift_ = (sizeof(std::size_t) == 8) ? 5UL : 4UL;
static constexpr std::size_t num_fast_bins_ = 8UL * align_multiplier;
static constexpr std::size_t num_small_bins_ = 56UL * align_multiplier;

static constexpr std::size_t min_fast_size_ = chunk_alignment_;
static constexpr std::size_t min_small_size_ = chunk_alignment_ * num_fast_bins_;
static constexpr std::size_t min_large_size_ =
chunk_alignment_ * (num_small_bins_ + num_fast_bins_);

static std::size_t request_to_sz(std::size_t num_bytes) {
    return ((num_bytes / chunk_alignment_) * chunk_alignment_) +
        ((num_bytes % chunk_alignment_) ? chunk_alignment_ : 0);
}

static [[nodiscard]] std::size_t fast_index(std::size_t num_bytes) noexcept {
    return (num_bytes >> bin_shift_);
}

static [[nodiscard]] std::size_t fast_size(std::size_t idx) noexcept {
    return (idx << bin_shift_);
}

static [[nodiscard]] std::size_t small_index(std::size_t num_bytes) noexcept;

static [[nodiscard]] std::size_t small_size(std::size_t idx) noexcept {
    return (idx << bin_shift_) + min_small_size_;
}

static [[nodiscard]] std::size_t small_index(std::size_t num_bytes) noexcept {
    assert(num_bytes >= min_small_size_);
    return ((num_bytes - min_small_size_) >> bin_shift_);
}

static void unlink_from_bin(Chunk* chunk, Chunk*& bin) {
    assert(chunk && chunk->prev_ && chunk->next_ && bin);
    if (chunk == chunk->prev_) {
        // make bin empty
        assert(chunk == chunk->next_);
        bin = nullptr;
    }
    else {
        if (chunk == bin) {
            bin = chunk->next_;
        }
        chunk->next_->prev_ = chunk->prev_;
        chunk->prev_->next_ = chunk->next_;
    }
    chunk->prev_ = nullptr;
    chunk->next_ = nullptr;
}

static void push_back_to_bin(Chunk* chunk, Chunk*& bin) {
    assert(chunk);
    if (!bin) {
        bin = chunk;
        chunk->prev_ = chunk;
        chunk->next_ = chunk;
    }
    else {
        chunk->next_ = bin;
        chunk->prev_ = bin->prev_;
        bin->prev_->next_ = chunk;
        bin->prev_ = chunk;
    }
}

static void push_front_to_bin(Chunk* chunk, Chunk*& bin) {
    push_back_to_bin(chunk, bin);
    bin = chunk;
}

static Chunk* pop_back_from_bin(Chunk*& bin) {
    auto chunk = bin;
    if (chunk) {
        assert(chunk->prev_ && chunk->next_);
        chunk = chunk->prev_;
        unlink_from_bin(chunk, bin);
    }
    return chunk;
}

static Chunk* pop_front_from_bin(Chunk*& bin) {
    auto chunk = bin;
    if (chunk) {
        assert(chunk->prev_ && chunk->next_);
        unlink_from_bin(chunk, bin);
    }
    return chunk;
}

static Chunk* pop_fastbin(Chunk*& bin) {
    auto chunk = bin;
    if (chunk) {
        bin = bin->next_;
        chunk->next_ = nullptr;
        assert(!chunk->prev_);
    }
    return chunk;
}

struct GetSize {
    std::size_t operator()(Chunk* iter) const noexcept {
        assert(iter);
        return iter->size_;
    }
};

AllocManager::AllocManager(std::size_t init_pool_size)
    : curr_pool_size_{ init_pool_size }, fast_bins_(num_fast_bins_, nullptr),
    small_bins_(num_small_bins_, nullptr), all_chunks_(init_pool_size) {
    assert(init_pool_size% chunk_alignment_ == 0);
    top_chunk_ = first_chunk();
    set_size(top_chunk_, init_pool_size);
}

void* AllocManager::alloc_chunk(std::size_t num_bytes) {
    num_bytes = request_to_sz(num_bytes);
    assert(num_bytes >= min_fast_size_ && num_bytes % chunk_alignment_ == 0);
    if (num_bytes < min_small_size_) {
        auto res = try_alloc_fastbin(num_bytes);
        if (res) {
            assert(res->size_ == (num_bytes | CHUNK_IN_USE));
            assert(verify());
            return reinterpret_cast<void*>(res);
        }
    }
    else if (num_bytes < min_large_size_) {
        auto res = try_alloc_smallbin(num_bytes);
        if (res) {
            assert(res->size_ == (num_bytes | CHUNK_IN_USE));
            assert(verify());
            return reinterpret_cast<void*>(res);
        }
    }
    else {
        consolidate_fastbin();
        assert(verify());
    }
    {
        auto res = try_alloc_unsorted(num_bytes);
        if (res) {
            assert(res->size_ == (num_bytes | CHUNK_IN_USE));
            assert(verify());
            return reinterpret_cast<void*>(res);
        }
    }
    auto res = alloc_top(num_bytes);
    assert(res && res->size_ == (num_bytes | CHUNK_IN_USE));
    assert(verify());
    return reinterpret_cast<void*>(res);
}

void AllocManager::dealloc_chunk(void* ptr) {
    assert(ptr);
    Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
    assert(get_flags(chunk) == CHUNK_IN_USE);
    set_flags(chunk, 0);
    assert(chunk != top_chunk_);
    if (next_chunk(chunk) != top_chunk_ && chunk->size_ < min_small_size_) {
        push_fastbin(chunk, fast_bins_[fast_index(chunk->size_)]);
    }
    else {
        consolidate_chunk(chunk);
    }
    assert(verify());
}

void AllocManager::set_flags(Chunk* chunk, std::size_t flags) {
    assert(chunk && chunk != top_chunk_);
    chunk->size_ &= CHUNK_FLAG_UNMASK;
    chunk->size_ |= flags;
    // add the foot
    std::size_t* foot = get_foot(chunk);
    *foot &= CHUNK_FLAG_UNMASK;
    *foot |= flags;
}

[[nodiscard]] bool AllocManager::is_begin(const Chunk* chunk) const noexcept {
    assert(chunk);
    assert(reinterpret_cast<const unsigned char*>(chunk) >=
        all_chunks_.data());
    return reinterpret_cast<const unsigned char*>(chunk) == all_chunks_.data();
}

std::size_t* AllocManager::get_foot(Chunk* chunk) noexcept {
    assert(chunk && chunk != top_chunk_);
    return reinterpret_cast<std::size_t*>(reinterpret_cast<unsigned char*>(chunk) +
        realsize(chunk));
}

const std::size_t* AllocManager::get_foot(const Chunk* chunk) const noexcept {
    assert(chunk && chunk != top_chunk_);
    return reinterpret_cast<const std::size_t*>(
        reinterpret_cast<const unsigned char*>(chunk) + realsize(chunk));
}

[[nodiscard]] std::size_t AllocManager::get_flags(const Chunk* chunk) const noexcept {
    assert(chunk);
    return chunk->size_ & CHUNK_FLAG_MASK;
}

std::size_t AllocManager::realsize(std::size_t sz) const noexcept {
    assert(sz >= chunk_alignment_);
    return (sz >> bin_shift_) << bin_shift_;
}

std::size_t AllocManager::realsize(const Chunk* chunk) const noexcept {
    assert(chunk && chunk->size_ >= chunk_alignment_);
    return realsize(chunk->size_);
}

void AllocManager::set_size(Chunk* chunk, std::size_t sz) {
    assert(chunk);
    chunk->size_ = sz;
    // add the foot
    if (chunk != top_chunk_) {
        std::size_t* foot = get_foot(chunk);
        *foot = sz;
    }
}

std::size_t AllocManager::verify_size(const Chunk* chunk) const noexcept {
    assert(chunk && chunk->size_ >= chunk_alignment_);
    // check the foot
    assert(chunk == top_chunk_ || *get_foot(chunk) == chunk->size_);
    return chunk->size_;
}

Chunk* AllocManager::prev_chunk(Chunk* chunk) noexcept {
    if (!chunk || is_begin(chunk)) {
        return nullptr;
    }
    return reinterpret_cast<Chunk*>(reinterpret_cast<unsigned char*>(chunk) -
        realsize(chunk->prev_size_));
}

const Chunk* AllocManager::prev_chunk(const Chunk* chunk) const noexcept {
    if (!chunk || is_begin(chunk)) {
        return nullptr;
    }
    return reinterpret_cast<const Chunk*>(
        reinterpret_cast<const unsigned char*>(chunk) -
        realsize(chunk->prev_size_));
}

Chunk* AllocManager::next_chunk(Chunk* chunk) noexcept {
    if (!chunk || chunk == top_chunk_) {
        return nullptr;
    }
    return reinterpret_cast<Chunk*>(reinterpret_cast<unsigned char*>(chunk) +
        realsize(chunk));
}

const Chunk* AllocManager::next_chunk(const Chunk* chunk) const noexcept {
    if (!chunk || chunk == top_chunk_) {
        return nullptr;
    }
    return reinterpret_cast<const Chunk*>(
        reinterpret_cast<const unsigned char*>(chunk) + realsize(chunk));
}

bool AllocManager::verify_fastbins() const {
    assert(fast_bins_.size() == num_fast_bins_);
    for (std::size_t i = 0; i < num_fast_bins_; ++i) {
        auto chunk = fast_bins_[i];
        while (chunk) {
            assert(realsize(verify_size(chunk)) == fast_size(i));
            assert(get_flags(chunk) == CHUNK_IN_USE);
            chunk = chunk->next_;
        }
    }
    return true;
}

bool AllocManager::verify_smallbins() const {
    assert(small_bins_.size() == num_small_bins_);
    for (std::size_t i = 0; i < num_small_bins_; ++i) {
        auto chunk = small_bins_[i];
        while (chunk) {
            assert(verify_size(chunk) == small_size(i));
            assert(chunk->prev_ && chunk->next_ && chunk->prev_->next_ == chunk &&
                chunk->next_->prev_ == chunk);
            if (chunk == chunk->next_) {
                assert(chunk == chunk->prev_);
                break;
            }
            chunk = chunk->next_;
            if (chunk == small_bins_[i]) {
                break;
            }
        }
    }
    return true;
}

bool AllocManager::verify_largebin() const {
    assert(std::ranges::is_sorted(large_bin_, std::ranges::less{}, GetSize{}));
    assert(std::ranges::all_of(large_bin_, [this](const auto& chunk) {
        return chunk && get_flags(chunk) == 0 &&
            verify_size(chunk) >= min_large_size_ &&
            (chunk->size_ % chunk_alignment_) == 0;
        }));
    return true;
}

bool AllocManager::verify_unsorted() const {
    auto chunk = unsorted_bin_;
    while (chunk) {
        assert(verify_size(chunk) >= chunk_alignment_ &&
            (realsize(chunk) % chunk_alignment_) == 0);
        assert(get_flags(chunk) == CHUNK_UNSORTED);
        assert(chunk->prev_ && chunk->next_ && chunk->prev_->next_ == chunk &&
            chunk->next_->prev_ == chunk);
        if (chunk == chunk->next_) {
            assert(chunk == chunk->prev_);
            break;
        }
        chunk = chunk->next_;
        if (chunk == unsorted_bin_) {
            break;
        }
    }
    return true;
}

bool AllocManager::verify() const {
    assert(!all_chunks_.empty() && all_chunks_.size() == curr_pool_size_);
    const Chunk* chunk = first_chunk();
    while (chunk) {
        assert(chunk->size_ >= chunk_alignment_ &&
            (realsize(chunk) % chunk_alignment_) == 0);
        auto next = next_chunk(chunk);
        if (!next) {
            assert(chunk == top_chunk_ && get_flags(chunk) == 0);
            assert(reinterpret_cast<const unsigned char*>(chunk) + chunk->size_ ==
                all_chunks_.data() + all_chunks_.size());
        }
        chunk = next;
    }
    assert(verify_fastbins());
    assert(verify_smallbins());
    assert(verify_largebin());
    assert(verify_unsorted());
    return true;
}

[[nodiscard]] auto AllocManager::large_iter(std::size_t num_bytes) const noexcept {
    return std::ranges::lower_bound(large_bin_, num_bytes, std::ranges::less{},
        GetSize{});
}

void AllocManager::push_fastbin(Chunk* chunk, Chunk*& bin) {
    assert(chunk && !chunk->prev_);
    chunk->next_ = bin;
    bin = chunk;

    // we mark CHUNK_IN_USE for fastbin chunks
    // so that they won't be consolidated.
    set_flags(chunk, CHUNK_IN_USE);
}

Chunk* AllocManager::try_alloc_fastbin(std::size_t num_bytes) {
    std::size_t fast_bin_index = fast_index(num_bytes);
    assert(fast_bin_index < num_fast_bins_);
    auto chunk = pop_fastbin(fast_bins_[fast_bin_index]);
    assert(!chunk || get_flags(chunk) == CHUNK_IN_USE);
    return chunk;
}

Chunk* AllocManager::try_alloc_smallbin(std::size_t num_bytes) {
    assert(num_bytes >= min_small_size_);
    std::size_t small_bin_index = small_index(num_bytes);
    assert(small_bin_index < num_small_bins_);
    auto chunk = pop_front_from_bin(small_bins_[small_bin_index]);
    if (chunk) {
        set_flags(chunk, CHUNK_IN_USE);
    }
    return chunk;
}

void AllocManager::unlink_chunk(Chunk* chunk) {
    assert(chunk);
    assert(!(get_flags(chunk) & CHUNK_IN_USE));
    auto num_bytes = chunk->size_;
    if (get_flags(chunk) & CHUNK_UNSORTED) {
        assert(unsorted_bin_);
        set_flags(chunk, 0);
        unlink_from_bin(chunk, unsorted_bin_);
    }
    else if (num_bytes < min_small_size_) {
        // fastbin chunks should never be consolidated by adjacent chunks,
        // they should be retrieved only upon malloc requests
        assert(false);
    }
    else if (num_bytes < min_large_size_) {
        std::size_t small_bin_index = small_index(num_bytes);
        assert(small_bin_index < num_small_bins_&& small_bins_[small_bin_index]);
        unlink_from_bin(chunk, small_bins_[small_bin_index]);
    }
    else if (chunk != top_chunk_) {
        auto where = large_iter(num_bytes);
        assert(where != large_bin_.end() && (*where)->size_ == num_bytes);
        while (*where != chunk) {
            ++where;
        }
        assert(where != large_bin_.end() && *where == chunk);
        large_bin_.erase(where);
    }
    else {
        assert(chunk == top_chunk_);
    }
}

void AllocManager::consolidate_chunk(Chunk* chunk) {
    assert(chunk);
    auto size = chunk->size_;
    auto next = next_chunk(chunk);
    while (!is_begin(chunk) && !(chunk->prev_size_ & CHUNK_IN_USE)) {
        auto prev = prev_chunk(chunk);
        assert(prev->size_);
        unlink_chunk(prev);
        assert(get_flags(prev) == 0);
        size += prev->size_;
        chunk = prev;
    }
    bool next_was_top = false;
    while (next && !(next->size_ & CHUNK_IN_USE)) {
        assert(next->size_);
        unlink_chunk(next);
        assert(get_flags(next) == 0);
        size += next->size_;
        next_was_top = (next == top_chunk_);
        next = next_chunk(next);
    }
    if (!next_was_top) {
        set_size(chunk, size);
        push_front_to_bin(chunk, unsorted_bin_);
        set_flags(chunk, CHUNK_UNSORTED);
    }
    else {
        top_chunk_ = chunk;
        set_size(chunk, size);
    }
}

void AllocManager::consolidate_fastbin() {
    for (std::size_t i = 0; i < num_fast_bins_; ++i) {
        while (fast_bins_[i]) {
            auto chunk = pop_fastbin(fast_bins_[i]);
            set_flags(chunk, 0);
            consolidate_chunk(chunk);
        }
    }
}

void AllocManager::place_in_bins(Chunk* chunk) {
    assert(chunk && get_flags(chunk) == 0);
    auto num_bytes = chunk->size_;
    if (num_bytes < min_small_size_) {
        push_fastbin(chunk, fast_bins_[fast_index(num_bytes)]);
    }
    else if (num_bytes < min_large_size_) {
        push_back_to_bin(chunk, small_bins_[small_index(num_bytes)]);
    }
    else {
        large_bin_.insert(large_iter(num_bytes), chunk);
    }
}

Chunk* AllocManager::split_chunk_after(Chunk* chunk, std::size_t offset) {
    assert(chunk && (chunk != top_chunk_) && offset >= chunk_alignment_ &&
        (offset % chunk_alignment_) == 0 &&
        realsize(chunk) >= offset + sizeof(Chunk) &&
        (realsize(chunk) - offset) % chunk_alignment_ == 0);

    auto split_size = realsize(chunk) - offset;

    // set new size of the current (left) chunk and erase flags
    set_size(chunk, offset);

    Chunk* split_chunk = reinterpret_cast<Chunk*>(
        reinterpret_cast<unsigned char*>(chunk) + offset);
    assert(split_chunk->prev_size_ == offset);
    split_chunk->prev_ = nullptr;
    split_chunk->next_ = nullptr;
    set_size(split_chunk, split_size);
    assert(split_chunk == next_chunk(chunk));
    assert(verify_size(split_chunk) == split_size);
    return split_chunk;
}

Chunk* AllocManager::try_alloc_unsorted(std::size_t num_bytes) {
    while (unsorted_bin_) {
        auto chunk = pop_front_from_bin(unsorted_bin_);
        assert(chunk && get_flags(chunk) == CHUNK_UNSORTED);
        set_flags(chunk, 0);

        // for small requests, if this is the last unsorted,
        // then split and take if possible
        if (!unsorted_bin_ && num_bytes < min_large_size_ &&
            chunk->size_ >= num_bytes + chunk_alignment_) {
            auto remainder = split_chunk_after(chunk, num_bytes);
            set_flags(chunk, CHUNK_IN_USE);
            set_flags(remainder, CHUNK_UNSORTED);
            push_front_to_bin(remainder, unsorted_bin_);
            return chunk;
        }

        // use this if exact fit
        if (chunk->size_ == num_bytes) {
            set_flags(chunk, CHUNK_IN_USE);
            return chunk;
        }

        place_in_bins(chunk);
    }
    return nullptr;
}

Chunk* AllocManager::try_alloc_largebin(std::size_t num_bytes) {
    assert(num_bytes >= min_large_size_ && (num_bytes % chunk_alignment_) == 0);
    auto where = large_iter(num_bytes);

    if (where == large_bin_.end()) {
        // no large bin chunk is available
        return nullptr;
    }
    else {
        // best fit
        auto chunk = *where;
        assert(get_flags(chunk) == 0);
        assert(chunk->size_ >= num_bytes);
        large_bin_.erase(where);
        if (chunk->size_ == num_bytes) {
            // use if exact fit
            set_flags(chunk, CHUNK_IN_USE);
            return chunk;
        }
        else if (chunk->size_ >= num_bytes + chunk_alignment_) {
            assert((chunk->size_ - num_bytes) % chunk_alignment_ == 0);
            // split to take remainder
            auto remainder = split_chunk_after(chunk, num_bytes);
            set_flags(chunk, CHUNK_IN_USE);
            place_in_bins(remainder);
            return chunk;
        }
    }
}

Chunk* AllocManager::alloc_top(std::size_t num_bytes) {
    assert(num_bytes >= chunk_alignment_ &&
        (num_bytes % chunk_alignment_) == 0);
    assert(get_flags(top_chunk_) == 0);
    if (top_chunk_->size_ < num_bytes + chunk_alignment_) {
        // TODO: how to deal with this?
        throw std::runtime_error("memory pool is not enough");
    }

    assert((top_chunk_->size_ % chunk_alignment_ == 0) &&
        top_chunk_->size_ >= num_bytes + chunk_alignment_ &&
        (top_chunk_->size_ - num_bytes) % chunk_alignment_ == 0);

    auto chunk = top_chunk_;

    auto split_size = top_chunk_->size_ - num_bytes;
    // set new size of the current (left) chunk and erase flags
    top_chunk_->size_ = num_bytes;
    Chunk* split_chunk = reinterpret_cast<Chunk*>(
        reinterpret_cast<unsigned char*>(top_chunk_) + num_bytes);
    assert(split_chunk);
    std::size_t* foot = reinterpret_cast<std::size_t*>(split_chunk);
    *foot = num_bytes;
    assert(split_chunk->prev_size_ == num_bytes);
    split_chunk->prev_ = nullptr;
    split_chunk->next_ = nullptr;
    split_chunk->size_ = split_size;
    top_chunk_ = split_chunk;
    assert(split_chunk == next_chunk(chunk));
    assert(split_chunk == top_chunk_);
    set_flags(chunk, CHUNK_IN_USE);
    return chunk;
}

main.cpp

#include <chrono>
#include <cassert>
#include <iostream>
#include <random>
#include <unordered_map>
#include "AllocManager.h"

int main()
{
    AllocManager simulator(1UL << 24UL);

    std::mt19937 gen(std::random_device{}());
    // will be multiplied by alignment
    std::gamma_distribution <> chunk_size_dist(2, 2);
    constexpr std::size_t chunk_align = 8UL;
    constexpr int num = 200'000;

    std::bernoulli_distribution to_alloc_or_dealloc(0.65);
    std::bernoulli_distribution large_or_small(0.05);
    std::unordered_map <void*, std::size_t> allocated;
    std::unordered_map <void*, std::size_t> allocated_std;

    float my_alloc_duration = 0.0f;
    float std_alloc_duration = 0.0f;

    for (int i = 0; i < num; ++i) {
        if (to_alloc_or_dealloc(gen)) {
            auto sz = (1 + static_cast<std::size_t>(chunk_size_dist(gen))) * chunk_align;
            if (large_or_small(gen)) {
                sz += 1024;
            }
            auto start = std::chrono::steady_clock::now();
            auto cnk = simulator.alloc_chunk(sz);
            auto end = std::chrono::steady_clock::now();
            my_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                end - start).count();
            allocated[cnk] = sz;
            start = std::chrono::steady_clock::now();
            void* ptr = std::malloc(sz);
            end = std::chrono::steady_clock::now();
            std_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                end - start).count();
            allocated_std[ptr] = sz;
        }
        else {
            if (!allocated.empty()) {
                auto [cnk, sz] = *allocated.begin();
                auto start = std::chrono::steady_clock::now();
                simulator.dealloc_chunk(cnk);
                auto end = std::chrono::steady_clock::now();
                my_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                    end - start).count();
                allocated.erase(allocated.begin());
                assert(!allocated_std.empty());
                auto [ptr, sz2] = *allocated_std.begin();
                start = std::chrono::steady_clock::now();
                std::free(ptr);
                end = std::chrono::steady_clock::now();
                std_alloc_duration += std::chrono::duration_cast <std::chrono::duration <float, std::micro>>(
                    end - start).count();
                allocated_std.erase(allocated_std.begin());
            }
        }
    }
    std::cout << "AllocManager elapsed " << my_alloc_duration / 1000.0f << "ms\n";
    std::cout << "std::malloc std::free elapsed " << std_alloc_duration / 1000.0f << "ms\n";
}