PointerArena.h

Go to the documentation of this file.

/*
 * This file is a part of the Biology project by eons LLC.
 * Biology (aka Develop Biology) is a framework for approaching software
 * development from a natural sciences perspective.
 *
 * Copyright (C) 2026 Séon O'Shannon & eons LLC
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include "bio/common/thread/ThreadSafe.h"
#include <cstddef>
#include <stdint.h>
#include <new>
#include <cstdio>
#include <cstdlib>
//@formatter:off
#if BIO_CPP_VERSION >= 11
    #include <utility>
#endif
//@formatter:on
 
namespace bio {
 
typedef uint32_t Index;
 
template < typename TYPE, bool MEMCPY_SAFE >
class Arrangement;
 
namespace pointer_arena {
 
typedef uint32_t Handle;
 
static const Handle NullHandle = 0;
static const Handle AddressMask = 0x3fffffffu;
static const Handle GenerationMask = 0xc0000000u;
static const uint32_t GenerationShift = 30u;
static const uint32_t GenerationModulo = 3u;
static const uint16_t ForeignGeneration = 3u;
static const ::std::size_t WordShift = 3;
static const ::std::size_t WordSize = (1u << WordShift);
static const uint32_t NullPageFreeSlot = 0xffffffffu;
static const uint16_t AllocationFlagFree = 0x0001u;
static const uint16_t AllocationFlagSpan = 0x0004u;
static const uint16_t PageFlagSmall = 0x0001u;
 
struct MemoryAllocation
{
    uint32_t mOffsetWords;
    uint32_t mCapacityWords;
    uint32_t mRequestedBytes;
    uint16_t mGeneration;
    uint16_t mFlags;
 
    MemoryAllocation();
    MemoryAllocation(
        uint32_t offsetWords,
        uint32_t capacityWords,
        uint32_t requestedBytes,
        uint16_t generation,
        uint16_t flags);
};
 
inline bool operator==(
    const MemoryAllocation& lhs,
    const MemoryAllocation& rhs)
{
    return
        lhs.mOffsetWords == rhs.mOffsetWords &&
        lhs.mCapacityWords == rhs.mCapacityWords &&
        lhs.mRequestedBytes == rhs.mRequestedBytes &&
        lhs.mGeneration == rhs.mGeneration &&
        lhs.mFlags == rhs.mFlags;
}
 
struct MemoryPage
{
    uint32_t mOffsetWords;
    uint32_t mPageBytes;
    uint16_t mSlotBytes;
    uint16_t mFlags;
    uint32_t mFirstFreeWordOffset;
    uint32_t mFreeSlots;
    uint32_t mTotalSlots;
    uint32_t mNextFreshSlot;
    unsigned char* mSlotStates;
 
    MemoryPage();
    MemoryPage(
        uint32_t offsetWords,
        uint32_t pageBytes,
        uint16_t slotBytes,
        uint16_t flags,
        uint32_t firstFreeWordOffset,
        uint32_t freeSlots,
        uint32_t totalSlots,
        uint32_t nextFreshSlot,
        unsigned char* slotStates);
};
 
inline bool operator==(
    const MemoryPage& lhs,
    const MemoryPage& rhs)
{
    return
        lhs.mOffsetWords == rhs.mOffsetWords &&
        lhs.mPageBytes == rhs.mPageBytes &&
        lhs.mSlotBytes == rhs.mSlotBytes &&
        lhs.mFlags == rhs.mFlags &&
        lhs.mFirstFreeWordOffset == rhs.mFirstFreeWordOffset &&
        lhs.mFreeSlots == rhs.mFreeSlots &&
        lhs.mTotalSlots == rhs.mTotalSlots &&
        lhs.mNextFreshSlot == rhs.mNextFreshSlot &&
        lhs.mSlotStates == rhs.mSlotStates;
}
 
class PointerArena :
    public ThreadSafe
{
    friend void DeleteObjectStorage(
        void* raw,
        ::std::size_t bytes);
    friend void FreeBytes(
        void* raw,
        ::std::size_t bytes);
 
public:
    static PointerArena& Instance();
 
    PointerArena();
    ~PointerArena();
 
    void* AllocateBytes(
        ::std::size_t bytes,
        ::std::size_t align);
    void* ReallocateBytes(
        void* raw,
        ::std::size_t oldBytes,
        ::std::size_t newBytes,
        ::std::size_t align);
    void FreeBytes(
        void* raw,
        ::std::size_t bytes);
 
    Handle HandleFor(const void* raw);
    Handle ArenaHandleFor(const void* raw) const;
    const void* Resolve(Handle handle) const;
 
    bool Owns(const void* raw) const;
    bool IsArenaHandle(Handle handle) const;
    bool IsForeignHandle(Handle handle) const;
 
    const void* GetBase() const;
    ::std::size_t GetCapacityBytes() const;
    ::std::size_t GetBytesHandedOut() const;
    ::std::size_t GetForeignCount() const;
    ::std::size_t GetAllocationRecordCount() const;
    ::std::size_t GetSmallAllocationCount() const;
    ::std::size_t GetPageRecordCount() const;
 
private:
    unsigned char* mBase;
    ::std::size_t mCapacityBytes;
    ::std::size_t mNextByte;
    bool mReservedWithMmap;
    // Stable (never-moving) per-word generation table for the checked-compact deref:
    // one byte per arena word, MAP_NORESERVE-reserved once alongside mBase. Read
    // lock-free by ResolveFast so racey multi-thread derefs only ever touch
    // never-moving memory (never the growable mPages/mAllocations, which the deref no
    // longer reads). Set on alloc, bumped under the arena lock on free.
    unsigned char* mSlotGenTable;
    ::std::size_t mSlotGenTableBytes;
    bool mSlotGenTableMmap;
    Arrangement< const void*, true >* mForeign;
    Arrangement< MemoryAllocation, true >* mAllocations;
    Arrangement< MemoryPage, true >* mPages;
    Index* mSmallPageLookup;
    ::std::size_t mSmallPageLookupCount;
    ::std::size_t mSmallAllocationCount;
    struct FreeBlock
    {
        unsigned char* mRaw;
        ::std::size_t mBytes;
        uint16_t mGeneration;
    };
    struct ForeignCacheEntry
    {
        const void* mRaw;
        Handle mHandle;
    };
    // Persistent per-address foreign dedup entry (C3). Bounds mForeign to the number of
    // UNIQUE foreign addresses: a re-import of an address that was evicted from the small
    // direct-mapped mForeignCache is resolved to its existing handle here instead of
    // appending a duplicate permanent mForeign entry.
    struct ForeignMapEntry
    {
        const void* mRaw;
        Handle mHandle;
    };
    struct SmallPageCacheEntry
    {
        uint16_t mSlotBytes;
        Index mPageIndex;
    };
    // Initial (and growth-base) capacity of the free-block store. The store is now a
    // growable heap array (mFreeBlocks / mFreeBlockCapacity) so a freed span is NEVER
    // dropped when full (C4).
    static const ::std::size_t FreeBlockInitialCapacity = 4096;
    static const ::std::size_t ForeignCacheCapacity = 4096;
    static const ::std::size_t ForeignCacheProbeCount = 8;
    static const ::std::size_t SmallPageCacheCapacity = 64;
    static const ::std::size_t SmallPageDirectCacheCapacity = 513;
    // Growable free-block store: pointer + capacity, doubled under the arena lock when
    // full (C4). ONLY accessed under the arena lock, so growing/moving it is safe.
    FreeBlock* mFreeBlocks;
    ForeignCacheEntry mForeignCache[ForeignCacheCapacity];
    SmallPageCacheEntry mSmallPageCache[SmallPageCacheCapacity];
    Index mSmallPageDirectCache[SmallPageDirectCacheCapacity];
    // Persistent open-addressing dedup map (raw address -> foreign handle) for C3.
    // malloc-backed, arena-lock-only, never read by the deref path.
    ForeignMapEntry* mForeignMap;
    ::std::size_t mForeignMapCapacity;
    ::std::size_t mForeignMapCount;
    ::std::size_t mFreeBlockCount;
    ::std::size_t mFreeBlockCapacity;
    ::std::size_t mForeignCacheVictim;
    ::std::size_t mSmallPageCacheVictim;
 
    void EnsureReserved();
    void* TakeFreeBlock(
        ::std::size_t bytes,
        ::std::size_t align,
        ::std::size_t* capacityBytes,
        uint16_t* generation);
    void* AllocateSmallBytes(
        ::std::size_t bytes,
        ::std::size_t align);
    void* AllocateSpanBytes(
        ::std::size_t bytes,
        ::std::size_t align);
    Index CreateSmallPage(
        ::std::size_t slotBytes,
        ::std::size_t align);
    Index FindSmallPage(
        ::std::size_t slotBytes) const;
    Index FindCachedSmallPage(
        ::std::size_t slotBytes) const;
    void RecordSmallPageCache(
        ::std::size_t slotBytes,
        Index pageIndex);
    bool EnsureSmallPageLookup();
    void RecordSmallPageLookup(
        Index pageIndex,
        ::std::size_t offsetBytes,
        ::std::size_t pageBytes);
    Index LookupSmallPageForRaw(
        const void* raw) const;
    Index FindPageForRaw(
        const void* raw) const;
    Index AddAllocation(
        ::std::size_t offsetBytes,
        ::std::size_t capacityBytes,
        ::std::size_t requestedBytes,
        uint16_t flags,
        uint16_t generation);
    Index FindAllocationByOffset(
        ::std::size_t offsetBytes) const;
    Index FindAllocationContainingOffset(
        ::std::size_t offsetBytes) const;
    bool RetireAllocation(
        ::std::size_t offsetBytes,
        MemoryAllocation* retiredAllocation = NULL);
    void RecordFreeBlock(
        void* raw,
        ::std::size_t bytes,
        uint16_t generation);
    bool CacheSmallBytes(
        void* raw,
        ::std::size_t bytes);
    const void* ResolveArena(Handle handle) const;
    Handle AddForeign(const void* raw);
    ::std::size_t ForeignCacheIndex(const void* raw) const;
    Handle FindRecentForeign(const void* raw) const;
    void RecordRecentForeign(
        const void* raw,
        Handle handle);
    // Persistent foreign dedup map (C3): consulted by AddForeign before appending so a
    // re-imported address returns its existing handle instead of a duplicate entry.
    Handle FindForeignInMap(const void* raw) const;
    void InsertForeignInMap(
        const void* raw,
        Handle handle);
    const void* ResolveForeign(Handle handle) const;
 
    PointerArena(const PointerArena&);
    PointerArena& operator=(const PointerArena&);
};
 
void* Allocate(
    ::std::size_t bytes,
    ::std::size_t align);
void* Reallocate(
    void* raw,
    ::std::size_t oldBytes,
    ::std::size_t newBytes,
    ::std::size_t align);
void DeleteObjectStorage(void* raw);
void DeleteObjectStorage(
    void* raw,
    ::std::size_t bytes);
void FreeBytes(void* raw);
void FreeBytes(
    void* raw,
    ::std::size_t bytes);
bool UseSystemContainerStorage();
void PushSystemContainerStorage();
void PopSystemContainerStorage();
 
Handle HandleFor(const void* raw);
const void* Resolve(Handle handle);
 
bool Owns(const void* raw);
bool IsArenaHandle(Handle handle);
bool IsForeignHandle(Handle handle);
const void* ArenaBase();
::std::size_t ArenaBytesHandedOut();
::std::size_t ForeignHandleCount();
::std::size_t ArenaAllocationRecordCount();
::std::size_t ArenaSmallAllocationCount();
::std::size_t ArenaPageRecordCount();
 
//@formatter:off
#if BIO_COMPACT_POINTER_STORAGE
extern const unsigned char* gPointerArenaBase;
#endif
 
inline Handle MakeHandle(
    uint32_t wordOffset,
    uint16_t generation)
{
    const Handle offsetField = static_cast< Handle >(wordOffset + 1u);
    if (!offsetField || offsetField > AddressMask)
    {
        return NullHandle;
    }
    return
        (static_cast< Handle >(generation % GenerationModulo) << GenerationShift) |
        offsetField;
}
 
inline uint32_t HandleOffsetField(Handle handle)
{
    return handle & AddressMask;
}
 
inline uint16_t HandleGeneration(Handle handle)
{
    return static_cast< uint16_t >((handle & GenerationMask) >> GenerationShift);
}
 
inline bool IsForeignHandleValue(Handle handle)
{
    return handle && HandleGeneration(handle) == ForeignGeneration;
}
 
inline uint32_t HandleWordOffset(Handle handle)
{
    const uint32_t offsetField = HandleOffsetField(handle);
    if (!offsetField)
    {
        return 0;
    }
    return offsetField - 1u;
}
 
#if BIO_ARENA_CHECKED
// Stable per-word generation table, reserved once alongside gPointerArenaBase (see
// PointerArena.cpp EnsureReserved). It NEVER moves, so ResolveFast reads it lock-free
// and racey multi-thread derefs never touch the growable mPages/mAllocations.
extern unsigned char* gSlotGenTable;
 
// Loud failure for a dereference of a stale/dangling arena handle in a checked
// build (C1): the handle outlived its slot's free/reuse and the arena liveness +
// generation check rejected it, so resolving raw would hand back reused memory.
// Abort instead of silently corrupting. NOT NDEBUG-gated (the check is opt-in, so
// when on it always fires). Returns to keep ResolveFast's return type well-formed.
inline const void* OnStaleHandle(Handle handle, const char* file, int line)
{
    ::std::fprintf(stderr,
        "BIO_ARENA_CHECKED: dereference of a stale/dangling arena handle 0x%08lx at %s:%d\n",
        static_cast< unsigned long >(handle), file, line);
    ::std::abort();
    return NULL;
}
#endif
 
#if BIO_COMPACT_POINTER_STORAGE
inline const void* ResolveFast(Handle handle)
{
    if (!handle)
    {
        return NULL;
    }
    if (IsForeignHandleValue(handle))
    {
        return Resolve(handle);
    }
    //@formatter:off
    #if BIO_ARENA_CHECKED
    // Checked path (C1 + C2): validate the (mod-3) generation via the STABLE per-word
    // generation table. That table and gPointerArenaBase never move, so this deref
    // reads ONLY never-moving memory -- it is safe under lock-free racey reads from
    // many threads while other threads allocate (which grow mPages/mAllocations, no
    // longer touched here). A generation mismatch means the handle outlived its slot's
    // free/reuse -> abort rather than resolve to reused memory.
    {
        const uint32_t offsetField = HandleOffsetField(handle);
        if (!offsetField || !gPointerArenaBase || !gSlotGenTable)
        {
            return NULL;
        }
        const ::std::size_t wordOffset = static_cast< ::std::size_t >(offsetField - 1u);
        if (gSlotGenTable[wordOffset] != HandleGeneration(handle))
        {
            return OnStaleHandle(handle, __FILE__, __LINE__);
        }
        return gPointerArenaBase + (wordOffset << WordShift);
    }
    #else
    const uint32_t offsetField = HandleOffsetField(handle);
    if (!offsetField || !gPointerArenaBase)
    {
        return NULL;
    }
    return gPointerArenaBase + (static_cast< ::std::size_t >(offsetField - 1u) << WordShift);
    #endif
    //@formatter:on
}
#endif
//@formatter:on
 
template < typename T >
inline ::std::size_t AlignmentOf()
{
    //@formatter:off
    #if defined(__GNUC__) || defined(__clang__)
    return __alignof__(T);
    #else
    return sizeof(void*);
    #endif
    //@formatter:on
}
 
template < typename T >
inline T* New()
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T();
}
 
template < typename T >
inline T* NewCopy(const T& value)
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T(value);
}
 
//@formatter:off
#if BIO_CPP_VERSION >= 11
template < typename T, typename... Args >
inline T* NewWith(Args&&... args)
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T(::std::forward< Args >(args)...);
}
#else
template < typename T, typename A1 >
inline T* NewWith(const A1& a1)
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T(a1);
}
 
template < typename T, typename A1, typename A2 >
inline T* NewWith(const A1& a1, A2& a2)
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T(a1, a2);
}
 
template < typename T, typename A1, typename A2 >
inline T* NewWith(const A1& a1, const A2& a2)
{
    void* storage = Allocate(sizeof(T), AlignmentOf< T >());
    return new (storage) T(a1, a2);
}
#endif
//@formatter:on
 
template < typename T >
inline void Delete(T* raw)
{
    if (!raw)
    {
        return;
    }
    raw->~T();
    DeleteObjectStorage(raw, sizeof(T));
}
 
template < typename T >
class Object
{
public:
    Object()
        :
        mObject(New< T >())
    {
    }
 
    explicit Object(const T& value)
        :
        mObject(NewCopy< T >(value))
    {
    }
 
    //@formatter:off
    #if BIO_CPP_VERSION >= 11
    template < typename... Args >
    explicit Object(Args&&... args)
        :
        mObject(NewWith< T >(::std::forward< Args >(args)...))
    {
    }
    #else
    template < typename A1 >
    explicit Object(const A1& a1)
        :
        mObject(NewWith< T >(a1))
    {
    }
 
    template < typename A1, typename A2 >
    Object(const A1& a1, A2& a2)
        :
        mObject(NewWith< T >(a1, a2))
    {
    }
 
    template < typename A1, typename A2 >
    Object(const A1& a1, const A2& a2)
        :
        mObject(NewWith< T >(a1, a2))
    {
    }
    #endif
    //@formatter:on
 
    ~Object()
    {
        if (mObject)
        {
            mObject->~T();
            mObject = NULL;
        }
    }
 
    T* Get()
    {
        return mObject;
    }
 
    const T* Get() const
    {
        return mObject;
    }
 
private:
    T* mObject;
 
    Object(const Object&);
    Object& operator=(const Object&);
};
 
} //pointer_arena namespace
} //bio namespace
 
//@formatter:off
#if BIO_COMPACT_POINTER_STORAGE
    #define BIO_POINTER_ARENA_ALLOCATED(TYPE) \
        static void* operator new(::std::size_t bytes) \
        { \
            void* storage = ::bio::pointer_arena::Allocate( \
                bytes, \
                ::bio::pointer_arena::AlignmentOf< TYPE >()); \
            if (!storage) \
            { \
                throw ::std::bad_alloc(); \
            } \
            return storage; \
        } \
        static void* operator new(::std::size_t, void* raw) \
        { \
            return raw; \
        } \
        static void operator delete(void* raw) \
        { \
            ::bio::pointer_arena::DeleteObjectStorage(raw); \
        } \
        static void operator delete(void*, void*) \
        { \
        }
#else
    #define BIO_POINTER_ARENA_ALLOCATED(TYPE)
#endif
//@formatter:on