stk_memory_bytepool.h

Go to the documentation of this file.

/*
 * SuperTinyKernel(TM) RTOS: Lightweight High-Performance Deterministic C++ RTOS for Embedded Systems.
 *
 * Source: https://github.com/SuperTinyKernel-RTOS
 *
 * Copyright (c) 2022-2026 Neutron Code Limited <stk@neutroncode.com>. All Rights Reserved.
 * License: MIT License, see LICENSE for a full text.
 */
 
#ifndef STK_MEMORY_BYTEPOOL_H_
#define STK_MEMORY_BYTEPOOL_H_
 
#include "stk_memory_allocator.h"
#include "sync/stk_sync_cv.h"

 
namespace stk {
namespace memory {

class BytePool : public ITraceable
{
public:
    static const size_t HEADER_SIZE = 8U;

    explicit BytePool(uint8_t *storage, size_t storage_size, const char *name = nullptr);

#if STK_MEMORY_PLACEMENT_NEW
    explicit BytePool(size_t storage_size, const char *name = nullptr);
#endif

    STK_VIRT_DTOR ~BytePool();

    static constexpr size_t AlignSize(size_t raw_size)
    {
        return ((raw_size + (BLOCK_ALIGN - 1U)) & ~(BLOCK_ALIGN - 1U));
    }

    static constexpr size_t RequiredSize(size_t payload_size)
    {
        return (AlignSize(payload_size) + HEADER_SIZE);
    }

    EWaitResult TimedAllocEx(void **block, size_t size, Timeout timeout_ticks = WAIT_INFINITE);

    void *TimedAlloc(size_t size, Timeout timeout_ticks = WAIT_INFINITE);

    template <typename T> T *TimedAllocT(Timeout timeout_ticks = WAIT_INFINITE);

    void *Alloc(size_t size);

    template <typename T> T *AllocT();

    void *TryAlloc(size_t size);

    template <typename T> T *TryAllocT();

    bool Free(void *ptr);

    void GetInfo(size_t &available, size_t &largest, size_t &fragments) const;

    bool IsStorageValid() const { return (m_first != nullptr); }

    size_t GetSize() const
    {
        return ((m_first != nullptr) ? static_cast<size_t>(
            reinterpret_cast<const uint8_t *>(m_end) - reinterpret_cast<const uint8_t *>(m_first)) : 0U);
    }

    size_t GetMaxRequest() const
    {
        const size_t size = GetSize();
        return ((size >= MIN_BLOCK_SIZE) ? (size - HEADER_SIZE) : 0U);
    }
 
private:
    STK_NONCOPYABLE_CLASS(BytePool);

    struct alignas(8) BlockHeader
    {
        uint32_t size;  
        uint32_t state; 
    };

    static const size_t BLOCK_ALIGN = 8U;

    static const size_t MIN_BLOCK_SIZE = (HEADER_SIZE + BLOCK_ALIGN);

    static const size_t POOL_SIZE_MAX = static_cast<size_t>(0xFFFFFFF8UL);
 
    static const uint32_t STATE_FREE = 0x46524545UL; 
    static const uint32_t STATE_USED = 0x55534544UL; 
    static const uint32_t STATE_NONE = 0x00000000UL; 

    void Init();

    static BlockHeader *Next(const BlockHeader *h)
    {
        return reinterpret_cast<BlockHeader *>(const_cast<uint8_t *>(reinterpret_cast<const uint8_t *>(h)) + h->size);
    }

    bool IsSane(const BlockHeader *h) const;

    void Coalesce(BlockHeader *h);

    void *FindFree(size_t need);

    bool IsBlockStart(const BlockHeader *h) const;

    static void AccountRun(size_t run, size_t &available, size_t &largest, size_t &fragments);
 
    uint8_t                 *m_storage;        
    BlockHeader             *m_first;          
    BlockHeader             *m_end;            
    sync::ConditionVariable  m_cv;             
    size_t                   m_storage_size;   
    bool                     m_storage_owned;  
};
 
// ---------------------------------------------------------------------------
// Constructors / Destructor
// ---------------------------------------------------------------------------
 
inline BytePool::BytePool(uint8_t *storage, size_t storage_size, const char *name)
: m_storage(storage),
  m_first(nullptr),
  m_end(nullptr),
  m_cv(),
  m_storage_size(storage_size),
  m_storage_owned(false)
{
    STK_ASSERT(storage != nullptr);
    STK_ASSERT(storage_size >= MIN_BLOCK_SIZE);
 
#if STK_SYNC_DEBUG_NAMES
    SetTraceName(name);
#else
    STK_UNUSED(name);
#endif
 
    Init();
}
 
#if STK_MEMORY_PLACEMENT_NEW
inline BytePool::BytePool(size_t storage_size, const char *name)
: m_storage(MemoryAllocator::AllocateArrayT<uint8_t>(storage_size)),
  m_first(nullptr),
  m_end(nullptr),
  m_cv(),
  m_storage_size(storage_size),
  m_storage_owned(true)
{
    STK_ASSERT(storage_size >= MIN_BLOCK_SIZE);
 
#if STK_SYNC_DEBUG_NAMES
    SetTraceName(name);
#else
    STK_UNUSED(name);
#endif
 
    // else: m_first remains nullptr; caller must check IsStorageValid()
    Init();
}
#endif
 
inline BytePool::~BytePool()
{
    // ConditionVariable destructor asserts the wait list is empty
#if STK_MEMORY_PLACEMENT_NEW
    if (m_storage_owned && (m_storage != nullptr))
    {
        MemoryAllocator::FreeArrayT(m_storage, m_storage_size);
        m_storage = nullptr;
    }
#endif
 
    m_first = nullptr;
    m_end   = nullptr;
}
 
// ---------------------------------------------------------------------------
// Alloc / TimedAlloc / TryAlloc
// ---------------------------------------------------------------------------
 
inline EWaitResult BytePool::TimedAllocEx(void **block, size_t size, Timeout timeout_ticks)
{
    EWaitResult result = WAIT_RESULT_FAIL;
 
    STK_ASSERT(block != nullptr); // API contract: output pointer must be valid
 
    if (block == nullptr)
    {
        // result is WAIT_RESULT_FAIL already, so noop
    }
    else
    {
        *block = nullptr;
 
        if (hw::IsInsideISR() && (timeout_ticks != NO_WAIT))
        {
            STK_ASSERT(false); // API contract: ISR callers must pass NO_WAIT / use TryAlloc()
        }
        else if ((size == 0U) || (size > GetMaxRequest()))
        {
            // result is WAIT_RESULT_FAIL: such a request can never succeed, so do not block on it
        }
        else
        {
            sync::ScopedCriticalSection cs_;
 
            // safe from overflow: size <= GetMaxRequest() <= POOL_SIZE_MAX - HEADER_SIZE
            const size_t need = RequiredSize(size);
 
            const bool timed_wait = (timeout_ticks != WAIT_INFINITE) && (timeout_ticks != NO_WAIT);
 
            // capture an absolute deadline once, before entering the wait loop; every Free()
            // wakes all waiters (Mesa-style, not a direct handoff) and a woken task may have
            // to wait again, so re-passing the original timeout_ticks on each retry would
            // silently restart it; kept as 64-bit Ticks (not truncated to Timeout) so it
            // can't wrap on long uptimes
            const Ticks deadline = (timed_wait ? (GetTicks() + static_cast<Ticks>(timeout_ticks)) : 0);
 
            void *ptr = FindFree(need); // fast path: a suitable block is already available
            result = WAIT_RESULT_SIGNAL;
 
            while (ptr == nullptr)
            {
                Timeout remaining = timeout_ticks;
 
                if (timeout_ticks == NO_WAIT)
                {
                    result = WAIT_RESULT_TIMEOUT; // no waiting requested (ISR-safe path)
                    break;
                }
 
                if (timed_wait)
                {
                    const Ticks left = (deadline - GetTicks());
                    if (left <= 0)
                    {
                        result = WAIT_RESULT_TIMEOUT; // budget is spent and a scan was just made
                        break;
                    }
                    remaining = static_cast<Timeout>(left);
                }
 
                // Atomically release the critical section, suspend the task, and
                // re-acquire before returning - no CPU cycles wasted while waiting.
                result = m_cv.WaitEx(cs_, remaining);
                if ((result != WAIT_RESULT_SIGNAL) && (result != WAIT_RESULT_TIMEOUT))
                {
                    break; // cancellation or kernel failure: report as is
                }
 
                // the lock was re-acquired: re-scan regardless of the wake reason, because the memory
                // may have been released at the very moment the timeout expired (honor it instead of
                // failing), or may have been taken by someone else after the wake-up (wait again)
                ptr = FindFree(need);
                if (ptr != nullptr)
                {
                    result = WAIT_RESULT_SIGNAL;
                }
                else if (result == WAIT_RESULT_TIMEOUT)
                {
                    break;
                }
                else
                {
                    // spurious or stolen wake-up: continue waiting within the remaining budget
                }
            }
 
            *block = ptr;
        }
    }
 
    return result;
}
 
inline void *BytePool::TimedAlloc(size_t size, Timeout timeout_ticks)
{
    void *block = nullptr;
 
    if (TimedAllocEx(&block, size, timeout_ticks) != WAIT_RESULT_SIGNAL)
    {
        block = nullptr;
    }
 
    return block;
}
 
template <typename T>
inline T *BytePool::TimedAllocT(Timeout timeout_ticks)
{
    STK_ASSERT(alignof(T) <= BLOCK_ALIGN); // API contract: payload is aligned to BLOCK_ALIGN only
 
    return static_cast<T *>(TimedAlloc(sizeof(T), timeout_ticks));
}
 
inline void *BytePool::Alloc(size_t size)
{
    return TimedAlloc(size, WAIT_INFINITE);
}
 
template <typename T>
inline T *BytePool::AllocT()
{
    return TimedAllocT<T>(WAIT_INFINITE);
}
 
inline void *BytePool::TryAlloc(size_t size)
{
    return TimedAlloc(size, NO_WAIT);
}
 
template <typename T>
inline T *BytePool::TryAllocT()
{
    return TimedAllocT<T>(NO_WAIT);
}
 
// ---------------------------------------------------------------------------
// Free
// ---------------------------------------------------------------------------
 
inline bool BytePool::Free(void *ptr)
{
    bool success = false;
 
    if ((ptr != nullptr) && (m_first != nullptr))
    {
        // bounds check: payload must be in range [m_first + HEADER_SIZE, m_end)
        const Word pt = hw::PtrToWord(ptr);
        const Word lo = hw::PtrToWord(m_first);
        const Word hi = hw::PtrToWord(m_end);
 
        if ((pt < (lo + HEADER_SIZE)) || (pt >= hi))
        {
            STK_ASSERT(false); // API contract: ptr does not belong to this pool
        }
        // alignment check: payloads always start on a BLOCK_ALIGN boundary relative to the area start
        else if ((static_cast<size_t>(pt - lo) % BLOCK_ALIGN) != 0U)
        {
            STK_ASSERT(false); // API contract: ptr is misaligned (not a payload start)
        }
        else
        {
            const sync::ScopedCriticalSection cs_;
 
            BlockHeader *const h = (reinterpret_cast<BlockHeader *>(ptr) - 1);
 
            if (h->state != STATE_USED)
            {
                STK_ASSERT(false); // block is not in use - double-free or foreign pointer
            }
            else
            {
                bool is_block = true;
 
            #if defined(_DEBUG) || defined(DEBUG)
                // O(n) validation that ptr really is the start of a block (and not an address
                // inside some payload which happens to look like a header), only active in
                // debug builds - compiles away completely in release
                is_block = IsBlockStart(h);
                STK_ASSERT(is_block);
            #endif
 
                if (is_block && IsSane(h))
                {
                    h->state = STATE_FREE;
 
                    // merge with the free blocks that follow; the ones that precede are merged by the next scan
                    Coalesce(h);
 
                    // memory became available: waiters have different request sizes, so all of
                    // them must re-evaluate (waking only one could leave a satisfiable request asleep)
                    m_cv.NotifyAll_CS();
 
                    success = true;
                }
            }
        }
    }
 
    return success;
}
 
// ---------------------------------------------------------------------------
// Statistics
// ---------------------------------------------------------------------------
 
inline void BytePool::GetInfo(size_t &available, size_t &largest, size_t &fragments) const
{
    available = 0U;
    largest   = 0U;
    fragments = 0U;
 
    if (m_first != nullptr)
    {
        const sync::ScopedCriticalSection cs_;
 
        size_t run = 0U; // length of the current run of adjacent free blocks
 
        for (const BlockHeader *h = m_first; (h < m_end); h = Next(h))
        {
            if (!IsSane(h))
            {
                STK_ASSERT(false); // pool metadata is corrupted (payload overrun?)
                break;
            }
 
            if (h->state == STATE_FREE)
            {
                run += h->size;
            }
            else
            {
                AccountRun(run, available, largest, fragments);
                run = 0U;
            }
        }
 
        AccountRun(run, available, largest, fragments);
    }
}
 
// ---------------------------------------------------------------------------
// Private helpers
// ---------------------------------------------------------------------------
 
inline void BytePool::Init()
{
    static_assert(sizeof(BlockHeader) == HEADER_SIZE, "BlockHeader must be exactly HEADER_SIZE bytes");
 
    if (m_storage != nullptr)
    {
        // align the area start to BLOCK_ALIGN and trim its size to a multiple of BLOCK_ALIGN
        const size_t addr   = static_cast<size_t>(hw::PtrToWord(m_storage));
        const size_t shift  = (AlignSize(addr) - addr);
        size_t       usable = ((m_storage_size > shift) ? ((m_storage_size - shift) & ~(BLOCK_ALIGN - 1U)) : 0U);
 
        // block sizes are 32-bit: a larger area would be wasted beyond this limit
        if (usable > POOL_SIZE_MAX)
        {
            usable = POOL_SIZE_MAX;
        }
 
        if (usable >= MIN_BLOCK_SIZE)
        {
            m_first = hw::WordToPtr<BlockHeader>(hw::PtrToWord(m_storage) + shift);
            m_end   = hw::WordToPtr<BlockHeader>(hw::PtrToWord(m_first) + usable);
 
            m_first->size  = static_cast<uint32_t>(usable);
            m_first->state = STATE_FREE;
        }
    }
}
 
inline bool BytePool::IsSane(const BlockHeader *h) const
{
    const bool state_ok = ((h->state == STATE_FREE) || (h->state == STATE_USED));
 
    return (state_ok &&
            (h->size >= MIN_BLOCK_SIZE) &&
            ((h->size % BLOCK_ALIGN) == 0U) &&
            (static_cast<size_t>(reinterpret_cast<const uint8_t *>(m_end) - reinterpret_cast<const uint8_t *>(h)) >= h->size));
}
 
inline void BytePool::Coalesce(BlockHeader *h)
{
    for (BlockHeader *n = Next(h); (n < m_end) && (n->state == STATE_FREE) && IsSane(n); n = Next(h))
    {
        h->size += n->size;
 
        // wipe the absorbed header so it can never be mistaken for a live block
        n->state = STATE_NONE;
        n->size  = 0U;
    }
}
 
inline void *BytePool::FindFree(size_t need)
{
    void *result = nullptr;
 
    for (BlockHeader *h = m_first; (h != nullptr) && (h < m_end) && (result == nullptr); h = Next(h))
    {
        if (!IsSane(h))
        {
            STK_ASSERT(false); // pool metadata is corrupted (payload overrun?)
            break;
        }
 
        if (h->state == STATE_FREE)
        {
            Coalesce(h);
 
            if (h->size >= need)
            {
                const size_t rest = (h->size - need);
 
                // split off the tail if it can form a valid block of its own
                if (rest >= MIN_BLOCK_SIZE)
                {
                    BlockHeader *const tail = reinterpret_cast<BlockHeader *>(reinterpret_cast<uint8_t *>(h) + need);
                    tail->size  = static_cast<uint32_t>(rest);
                    tail->state = STATE_FREE;
 
                    h->size = static_cast<uint32_t>(need);
                }
 
                h->state = STATE_USED;
                result   = (h + 1);
            }
        }
    }
 
    return result;
}
 
inline bool BytePool::IsBlockStart(const BlockHeader *h) const
{
    bool found = false;
 
    for (const BlockHeader *b = m_first; (b != nullptr) && (b <= h) && (b < m_end) && IsSane(b); b = Next(b))
    {
        if (b == h)
        {
            found = true;
            break;
        }
    }
 
    return found;
}
 
inline void BytePool::AccountRun(size_t run, size_t &available, size_t &largest, size_t &fragments)
{
    if (run != 0U)
    {
        const size_t payload = (run - HEADER_SIZE);
 
        available += payload;
        ++fragments;
 
        if (payload > largest)
        {
            largest = payload;
        }
    }
}
 
} // namespace memory
} // namespace stk
 
#endif /* STK_MEMORY_BYTEPOOL_H_ */