C++ Memory Pools — How Exhaustion Crashed a Trading Engine

// TheCodeForge — Fixed-size pool allocator
#include <cstddef>
#include <cassert>
#include <new>

namespace io::thecodeforge {

class FixedPool {
    struct Slot {
        union {
            Slot* next;  // free list pointer
            char data[1]; // placeholder, actual size at runtime
        };
    };

    Slot* pool_start_;
    Slot* free_head_;
    size_t slot_size_;
    size_t slot_count_;

public:
    FixedPool(size_t slot_size, size_t slot_count)
        : slot_size_(slot_size), slot_count_(slot_count) {
        if (slot_size < sizeof(Slot*))
            slot_size_ = sizeof(Slot*); // ensure we can store free ptr

        pool_start_ = static_cast<Slot*>(::operator new(slot_size_ * slot_count_));
        free_head_ = pool_start_;
        for (size_t i = 0; i < slot_count_ - 1; ++i) {
            Slot* current = reinterpret_cast<Slot*>(
                reinterpret_cast<char*>(pool_start_) + i * slot_size_);
            current->next = reinterpret_cast<Slot*>(
                reinterpret_cast<char*>(pool_start_) + (i + 1) * slot_size_);
        }
        // last slot points to null
        Slot* last = reinterpret_cast<Slot*>(
            reinterpret_cast<char*>(pool_start_) + (slot_count_ - 1) * slot_size_);
        last->next = nullptr;
    }

    void* allocate() {
        if (!free_head_) throw std::bad_alloc();
        Slot* slot = free_head_;
        free_head_ = slot->next;
        return slot;
    }

    void deallocate(void* ptr) {
        Slot* slot = static_cast<Slot*>(ptr);
        slot->next = free_head_;
        free_head_ = slot;
    }

    ~FixedPool() {
        ::operator delete(pool_start_);
    }
};

} // namespace

// TheCodeForge — Slab allocator with fixed size classes
#include <array>
#include <cstddef>
#include <new>
#include <algorithm>

namespace io::thecodeforge {

template <size_t... Sizes>
class SlabAllocator {
    static constexpr std::array<size_t, sizeof...(Sizes)> kSizes = {Sizes...};

    struct Slab {
        size_t slot_size;
        FixedPool* pool;
        Slab(size_t sz) : slot_size(sz), pool(nullptr) {}

        void ensure_pool(size_t count) {
            if (!pool)
                pool = new FixedPool(slot_size, count);
        }
    };

    Slab slabs_[sizeof...(Sizes)];  // one per size class
    size_t slab_count_ = sizeof...(Sizes);

public:
    SlabAllocator(size_t slots_per_slab = 256) {
        size_t idx = 0;
        ((slabs_[idx++] = Slab(Sizes)), ...);  // C++17 fold expression
    }

    void* allocate(size_t bytes) {
        for (auto& slab : slabs_) {
            if (bytes <= slab.slot_size) {
                slab.ensure_pool(256);
                return slab.pool->allocate();
            }
        }
        // no matching slab — fallback to malloc
        return ::operator new(bytes);
    }

    void deallocate(void* ptr, size_t bytes) {
        for (auto& slab : slabs_) {
            if (bytes <= slab.slot_size) {
                slab.pool->deallocate(ptr);
                return;
            }
        }
        ::operator delete(ptr);
    }
};

using SmallObjectAllocator = SlabAllocator<8, 16, 32, 64, 128, 256, 512, 1024>;

} // namespace

// TheCodeForge — Lock-free fixed-size pool
#include <atomic>
#include <cstddef>
#include <new>

namespace io::thecodeforge {

class LockFreePool {
    struct Slot {
        std::atomic<Slot*> next;
    };

    Slot* pool_start_;
    std::atomic<Slot*> free_head_;
    size_t slot_size_;
    size_t slot_count_;

public:
    LockFreePool(size_t slot_size, size_t slot_count)
        : slot_size_(slot_size), slot_count_(slot_count) {
        if (slot_size < sizeof(std::atomic<Slot*>))
            slot_size_ = sizeof(std::atomic<Slot*>);

        pool_start_ = reinterpret_cast<Slot*>(::operator new(slot_size_ * slot_count_));
        for (size_t i = 0; i < slot_count_; ++i) {
            Slot* s = reinterpret_cast<Slot*>(
                reinterpret_cast<char*>(pool_start_) + i * slot_size_);
            s->next.store(i + 1 < slot_count_ ?
                reinterpret_cast<Slot*>(reinterpret_cast<char*>(pool_start_) + (i + 1) * slot_size_) : nullptr,
                std::memory_order_relaxed);
        }
        free_head_.store(pool_start_, std::memory_order_relaxed);
    }

    void* allocate() {
        Slot* old_head = free_head_.load(std::memory_order_acquire);
        Slot* new_head;
        do {
            if (!old_head) return nullptr;  // pool exhausted
            new_head = old_head->next.load(std::memory_order_relaxed);
        } while (!free_head_.compare_exchange_weak(old_head, new_head,
                                                    std::memory_order_acq_rel,
                                                    std::memory_order_acquire));
        return old_head;
    }

    void deallocate(void* ptr) {
        Slot* slot = static_cast<Slot*>(ptr);
        Slot* old_head = free_head_.load(std::memory_order_acquire);
        do {
            slot->next.store(old_head, std::memory_order_relaxed);
        } while (!free_head_.compare_exchange_weak(old_head, slot,
                                                    std::memory_order_acq_rel,
                                                    std::memory_order_acquire));
    }

    ~LockFreePool() {
        ::operator delete(pool_start_);
    }
};

} // namespace

// TheCodeForge — STL-compatible pool allocator
#include <memory>
#include <cstddef>
#include "io/thecodeforge/fixed_pool.h"

namespace io::thecodeforge {

template <typename T>
class PoolAllocator {
public:
    using value_type = T;

    PoolAllocator(FixedPool& pool) noexcept : pool_(&pool) {}

    template <typename U>
    PoolAllocator(const PoolAllocator<U>& other) noexcept
        : pool_(other.pool_) {}

    T* allocate(std::size_t n) {
        if (n != 1) throw std::bad_alloc();  // pool is single-slot only
        return static_cast<T*>(pool_->allocate());
    }

    void deallocate(T* p, std::size_t n) noexcept {
        if (n == 1) pool_->deallocate(p);
    }

    template <typename U>
    struct rebind {
        using other = PoolAllocator<U>;
    };

    // equality: must share the same pool
    friend bool operator==(const PoolAllocator& a, const PoolAllocator& b) {
        return a.pool_ == b.pool_;
    }
    friend bool operator!=(const PoolAllocator& a, const PoolAllocator& b) {
        return a.pool_ != b.pool_;
    }

private:
    FixedPool* pool_;
    // allow cross-type copy
    template <typename U> friend class PoolAllocator;
};

} // namespace

// TheCodeForge — demonstrating pool pitfalls
#include <iostream>
#include <memory>
#include <vector>

struct Particle { int x, y, vx, vy; };  // 16 bytes

// Suppose pool is sized for 1000 particles at 64 bytes each
struct LargePool {
    char data[64 * 1000];
    size_t next = 0;

    void* alloc() {
        if (next >= 1000) return nullptr;
        return data + (next++ * 64);
    }
    // ... no free() - pool never releases memory
};

int main() {
    LargePool pool;
    std::vector<Particle*> vec;
    // worst-case: each particle uses only 16 bytes but pool wastes 48
    for (int i = 0; i < 1000; ++i)
        vec.push_back(static_cast<Particle*>(pool.alloc()));
    std::cout << "Wasted space: " << (64-16)*1000 << " bytes\n";
    // pool memory never freed until program exit
    return 0;
}