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 <stdint.h>
#include <stddef.h>
#include <new>
 
#include "stk_common.h"
#include "stk_helper.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);

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

    ~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 = WAIT_INFINITE);

    template <typename T> T *TimedAllocT(Timeout timeout = 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 uint32_t BLOCK_ALIGN = static_cast<uint32_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;       
    uint16_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));
 
#if STK_SYNC_DEBUG_NAMES
    SetTraceName(name);
#else
    STK_UNUSED(name);
#endif
 
    BuildFreeList();
}
 
inline BlockMemoryPool::BlockMemoryPool(size_t capacity, size_t raw_block_size, const char *name)
    : m_storage(new (std::nothrow) 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()
}
 
inline BlockMemoryPool::~BlockMemoryPool()
{
    // ConditionVariable destructor asserts the wait list is empty
    if (m_storage_owned)
    {
        delete[] m_storage;
        m_storage = nullptr;
    }
}
 
// ---------------------------------------------------------------------------
// Alloc / TimedAlloc / TryAlloc
// ---------------------------------------------------------------------------
 
inline void *BlockMemoryPool::TimedAlloc(Timeout timeout)
{
    if (hw::IsInsideISR() && (timeout != NO_WAIT))
    {
        STK_ASSERT(false); // API contract: ISR callers must pass NO_WAIT / use TryAlloc()
        return nullptr;
    }
 
    sync::ScopedCriticalSection cs_;
 
    while (m_free_list == nullptr)
    {
        // Atomically release the critical section, suspend the task, and
        // re-acquire before returning - no CPU cycles wasted while waiting.
        if (!m_cv.Wait(cs_, timeout))
            return nullptr; // timeout expired
    }
 
    return PopFreeList();
}
 
template <typename T>
inline T *BlockMemoryPool::TimedAllocT(Timeout timeout)
{
    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));
}
 
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)
{
    if (ptr == nullptr)
        return false;
 
    // bounds check: ptr must be in range [m_storage, m_storage + capacity * block_size)
    const uint8_t *p8 = static_cast<uint8_t *>(ptr);
    const uint8_t *lo = m_storage;
    const uint8_t *hi = m_storage + (m_capacity * m_block_size);
 
    if ((p8 < lo) || (p8 >= hi))
    {
        STK_ASSERT(false); // API contract: ptr does not belong to this pool
        return false;
    }
 
    // alignment check: ptr must be at the start of a block boundary
    if ((static_cast<size_t>(p8 - lo) % m_block_size) != 0U)
    {
        STK_ASSERT(false); // API contract: ptr is misaligned (not a block start)
        return false;
    }
 
    sync::ScopedCriticalSection cs_;
 
    if (m_used_count == 0U)
    {
        STK_ASSERT(false); // pool is already fully free - definite double-free
        return false;
    }
 
#if defined(_DEBUG) || defined(DEBUG)
    // 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
            return false;
        }
    }
#endif
 
    // push block onto free-list head (O(1))
    auto *blk   = reinterpret_cast<MemoryBlock *>(ptr);
    blk->next   = m_free_list;
    m_free_list = blk;
    m_used_count = static_cast<uint16_t>(m_used_count - 1U);
 
    // wake one blocked allocator - true scheduler wait, no spin-yield
    m_cv.NotifyOne_CS();
 
    return true;
}
 
// ---------------------------------------------------------------------------
// 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 *blk = reinterpret_cast<MemoryBlock *>(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 *blk = m_free_list;
 
    m_free_list  = blk->next;
    m_used_count = static_cast<uint16_t>(m_used_count + 1U);
 
    return blk;
}
 
} // namespace memory
} // namespace stk
 
#endif /* STK_MEMORY_BLOCKPOOL_H_ */