stk_memory_blockpool.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_BLOCKPOOL_H_
#define STK_MEMORY_BLOCKPOOL_H_
 
#include "stk_memory_allocator.h"
#include "sync/stk_sync_cv.h"

 
namespace stk {
namespace memory {

class BlockMemoryPool : public ITraceable
{
public:
    static const size_t CAPACITY_MAX = 0xFFFEU;

    explicit BlockMemoryPool(size_t capacity, size_t raw_block_size, uint8_t *storage,
                             size_t storage_size, const char *name = nullptr);

#if STK_MEMORY_PLACEMENT_NEW
    explicit BlockMemoryPool(size_t capacity, size_t raw_block_size, const char *name = nullptr);
#endif

    STK_VIRT_DTOR ~BlockMemoryPool();

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

    void *TimedAlloc(Timeout timeout_ticks = WAIT_INFINITE);

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

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

    void *Alloc();

    template <typename T> T *AllocT();

    void *TryAlloc();

    template <typename T> T *TryAllocT();

    bool Free(void *ptr);

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

    size_t GetCapacity() const { return m_capacity; }

    size_t GetBlockSize() const { return m_block_size; }

    size_t GetUsedCount() const { return m_used_count; }

    size_t GetFreeCount() const { return (m_capacity - m_used_count); }

    bool IsFull() const { return (GetFreeCount() == 0U); }

    bool IsEmpty() const { return (m_used_count == 0U); }
 
private:
    STK_NONCOPYABLE_CLASS(BlockMemoryPool);

    struct MemoryBlock
    {
        MemoryBlock *next; 
    };

    static const size_t BLOCK_ALIGN = static_cast<size_t>(sizeof(MemoryBlock));

    void BuildFreeList();

    void *PopFreeList();
 
    uint8_t                 *m_storage;        
    MemoryBlock             *m_free_list;      
    sync::ConditionVariable  m_cv;             
    size_t                   m_block_size;     
    size_t                   m_capacity;       
    size_t                   m_used_count;     
    bool                     m_storage_owned;  
};
 
// ---------------------------------------------------------------------------
// Constructors / Destructor
// ---------------------------------------------------------------------------
 
inline BlockMemoryPool::BlockMemoryPool(size_t capacity, size_t raw_block_size, uint8_t *storage,
                                        size_t storage_size, const char *name)
: m_storage(storage),
  m_free_list(nullptr),
  m_block_size(AlignBlockSize(raw_block_size)),
  m_capacity(capacity),
  m_used_count(0U),
  m_storage_owned(false)
{
    STK_ASSERT(capacity > 0U);
    STK_ASSERT(capacity <= CAPACITY_MAX);
    STK_ASSERT(raw_block_size > 0U);
    STK_ASSERT(storage != nullptr);
 
    // API contract: caller-supplied buffer must be large enough
    STK_ASSERT(storage_size >= (capacity * m_block_size));
 
    // in Release builds we ensure capacity which fits storage size, in Debug build the assertion above will be hit
    if ((capacity * m_block_size) > storage_size)
    {
        m_capacity = storage_size / m_block_size;
    }
 
#if STK_SYNC_DEBUG_NAMES
    SetTraceName(name);
#else
    STK_UNUSED(name);
#endif
 
    BuildFreeList();
}
 
#if STK_MEMORY_PLACEMENT_NEW
inline BlockMemoryPool::BlockMemoryPool(size_t capacity, size_t raw_block_size, const char *name)
: m_storage(MemoryAllocator::AllocateArrayT<uint8_t>(capacity * AlignBlockSize(raw_block_size))),
  m_free_list(nullptr),
  m_block_size(AlignBlockSize(raw_block_size)),
  m_capacity(capacity),
  m_used_count(0U),
  m_storage_owned(true)
{
    STK_ASSERT(capacity > 0U);
    STK_ASSERT(capacity <= CAPACITY_MAX);
    STK_ASSERT(raw_block_size > 0U);
 
#if STK_SYNC_DEBUG_NAMES
    SetTraceName(name);
#else
    STK_UNUSED(name);
#endif
 
    if (m_storage != nullptr)
    {
        BuildFreeList();
    }
    // else: m_free_list remains nullptr; caller must check IsStorageValid()
}
#endif
 
inline BlockMemoryPool::~BlockMemoryPool()
{
    // ConditionVariable destructor asserts the wait list is empty
#if STK_MEMORY_PLACEMENT_NEW
    if (m_storage_owned)
    {
        MemoryAllocator::FreeArrayT(m_storage, (m_capacity * m_block_size));
        m_storage = nullptr;
    }
#endif
}
 
// ---------------------------------------------------------------------------
// Alloc / TimedAlloc / TryAlloc
// ---------------------------------------------------------------------------
 
inline EWaitResult BlockMemoryPool::TimedAllocEx(void **block, 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 if (hw::IsInsideISR() && (timeout_ticks != NO_WAIT))
    {
        STK_ASSERT(false); // API contract: ISR callers must pass NO_WAIT / use TryAlloc()
        *block = nullptr;
    }
    else
    {
        sync::ScopedCriticalSection cs_;
 
        const bool timed_wait = (timeout_ticks != WAIT_INFINITE) && (timeout_ticks != NO_WAIT);
 
        // capture an absolute deadline once, before entering the wait loop; a different
        // allocator (TryAlloc() from another task or an ISR) can steal the just-freed
        // block between NotifyOne_CS() and this task re-acquiring the critical section
        // (Mesa-style wakeup, not a direct handoff - see Free()'s note), 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);
 
        *block = nullptr;
        result = WAIT_RESULT_SIGNAL; // fast path: a block is already available
 
        while (m_free_list == nullptr)
        {
            Timeout remaining = timeout_ticks;
            if (timed_wait)
            {
                const Ticks left = (deadline - GetTicks());
                remaining = ((left > 0) ? static_cast<Timeout>(left) : NO_WAIT);
            }
 
            // 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)
            {
                break; // timeout, cancellation or kernel failure: report as is
            }
        }
 
        // timeout raced with a Free(): the lock was re-acquired and a block is available,
        // so honor it instead of reporting a failure (cancellation is never overridden)
        if ((result == WAIT_RESULT_TIMEOUT) && (m_free_list != nullptr))
        {
            result = WAIT_RESULT_SIGNAL;
        }
 
        // only allocate a block if the wait ended in a signal (or none was needed)
        if (result == WAIT_RESULT_SIGNAL)
        {
            *block = PopFreeList();
        }
    }
 
    return result;
}
 
inline void *BlockMemoryPool::TimedAlloc(Timeout timeout_ticks)
{
    void *block = nullptr;
 
    if (TimedAllocEx(&block, timeout_ticks) != WAIT_RESULT_SIGNAL)
    {
        block = nullptr;
    }
 
    return block;
}
 
template <typename T>
inline T *BlockMemoryPool::TimedAllocT(Timeout timeout_ticks)
{
    STK_ASSERT(sizeof(T) <= m_block_size); // API contract: block size should larger or equal to object's size
 
    return static_cast<T *>(TimedAlloc(timeout_ticks));
}
 
inline void *BlockMemoryPool::Alloc()
{
    return TimedAlloc(WAIT_INFINITE);
}
 
template <typename T>
inline T *BlockMemoryPool::AllocT()
{
    return TimedAllocT<T>(WAIT_INFINITE);
}
 
inline void *BlockMemoryPool::TryAlloc()
{
    return TimedAlloc(NO_WAIT);
}
 
template <typename T>
inline T *BlockMemoryPool::TryAllocT()
{
    return TimedAllocT<T>(NO_WAIT);
}
 
// ---------------------------------------------------------------------------
// Free
// ---------------------------------------------------------------------------
 
inline bool BlockMemoryPool::Free(void *ptr)
{
    bool success = false;
 
    if (ptr != nullptr)
    {
        // bounds check: ptr must be in range [m_storage, m_storage + capacity * block_size)
        const Word pt = hw::PtrToWord(ptr);
        const Word lo = hw::PtrToWord(m_storage);
        const Word hi = lo + (m_capacity * m_block_size);
 
        if ((pt < lo) || (pt >= hi))
        {
            STK_ASSERT(false); // API contract: ptr does not belong to this pool
        }
        // alignment check: ptr must be at the start of a block boundary
        else if ((static_cast<size_t>(pt - lo) % m_block_size) != 0U)
        {
            STK_ASSERT(false); // API contract: ptr is misaligned (not a block start)
        }
        else
        {
            const sync::ScopedCriticalSection cs_;
 
            if (m_used_count == 0U)
            {
                STK_ASSERT(false); // pool is already fully free - definite double-free
            }
            else
            {
            #if defined(_DEBUG) || defined(DEBUG)
                bool is_double_free = false;
 
                // O(n) double-free detection: walk the free-list and check if ptr is already on it,
                // only active in debug builds - compiles away completely in release
                for (const MemoryBlock *node = m_free_list; (node != nullptr); node = node->next)
                {
                    if (node == reinterpret_cast<const MemoryBlock *>(ptr))
                    {
                        STK_ASSERT(false); // double-free: ptr is already on the free-list
                        is_double_free = true;
                        break;
                    }
                }
 
                if (!is_double_free)
            #endif
                {
                    // push block onto free-list head (O(1))
                    auto *const blk = reinterpret_cast<MemoryBlock *>(ptr);
                    blk->next       = m_free_list;
                    m_free_list     = blk;
                    m_used_count    = (m_used_count - 1U);
 
                    // wake one blocked allocator - true scheduler wait, no spin-yield
                    m_cv.NotifyOne_CS();
                    
                    success = true;
                }
            }
        }
    }
 
    return success;
}
 
// ---------------------------------------------------------------------------
// Private helpers
// ---------------------------------------------------------------------------
 
inline void BlockMemoryPool::BuildFreeList()
{
    STK_ASSERT((hw::PtrToWord(m_storage) % BLOCK_ALIGN) == 0U);
 
    m_free_list  = nullptr;
    m_used_count = 0U;
 
    // Link blocks in reverse order so m_free_list ends up pointing at block_0
    // (lowest address), giving ascending allocation order.
    for (size_t i = m_capacity; i-- > 0U; )
    {
        MemoryBlock *const blk = hw::WordToPtr<MemoryBlock>(hw::PtrToWord(m_storage) + (i * m_block_size));
 
        blk->next   = m_free_list;
        m_free_list = blk;
    }
}
 
inline void *BlockMemoryPool::PopFreeList()
{
    STK_ASSERT(m_used_count < m_capacity);
 
    MemoryBlock *const blk = m_free_list;
 
    m_free_list  = blk->next;
    m_used_count = (m_used_count + 1U);
 
    return blk;
}
 
} // namespace memory
} // namespace stk
 
#endif /* STK_MEMORY_BLOCKPOOL_H_ */