dynamic_memory.hpp

00001 /*
00002  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #ifndef UAVCAN_DYNAMIC_MEMORY_HPP_INCLUDED
00006 #define UAVCAN_DYNAMIC_MEMORY_HPP_INCLUDED
00007 
00008 #include <cassert>
00009 #include <cstdlib>
00010 #include <cstring>
00011 #include <uavcan/std.hpp>
00012 #include <uavcan/util/templates.hpp>
00013 #include <uavcan/util/placement_new.hpp>
00014 #include <uavcan/build_config.hpp>
00015 
00016 namespace uavcan
00017 {
00018 /**
00019  * This interface is used by other library components that need dynamic memory.
00020  */
00021 class UAVCAN_EXPORT IPoolAllocator
00022 {
00023 public:
00024     virtual ~IPoolAllocator() { }
00025 
00026     virtual void* allocate(std::size_t size) = 0;
00027     virtual void deallocate(const void* ptr) = 0;
00028 
00029     /**
00030      * Returns the maximum number of blocks this allocator can allocate.
00031      */
00032     virtual uint16_t getBlockCapacity() const = 0;
00033 };
00034 
00035 /**
00036  * Classic implementation of a pool allocator (Meyers).
00037  *
00038  * The allocator can be made thread-safe (optional) by means of providing a RAII-lock type via the second template
00039  * argument. The allocator uses the lock only to access the shared state, therefore critical sections are only a few
00040  * cycles long, which implies that it should be acceptable to use hardware IRQ disabling instead of a mutex for
00041  * performance reasons. For example, an IRQ-based RAII-lock type can be implemented as follows:
00042  *     struct RaiiSynchronizer
00043  *     {
00044  *         RaiiSynchronizer()  { __disable_irq(); }
00045  *         ~RaiiSynchronizer() { __enable_irq(); }
00046  *     };
00047  */
00048 template <std::size_t PoolSize,
00049           uint8_t BlockSize,
00050           typename RaiiSynchronizer = char>
00051 class UAVCAN_EXPORT PoolAllocator : public IPoolAllocator,
00052                                     Noncopyable
00053 {
00054     union Node
00055     {
00056         uint8_t data[BlockSize];
00057         Node* next;
00058     };
00059 
00060     Node* free_list_;
00061     union
00062     {
00063          uint8_t bytes[PoolSize];
00064          long double _aligner1;
00065          long long _aligner2;
00066          Node _aligner3;
00067     } pool_;
00068 
00069     uint16_t used_;
00070     uint16_t max_used_;
00071 
00072 public:
00073     static const uint16_t NumBlocks = PoolSize / BlockSize;
00074 
00075     PoolAllocator();
00076 
00077     virtual void* allocate(std::size_t size);
00078     virtual void deallocate(const void* ptr);
00079 
00080     virtual uint16_t getBlockCapacity() const { return NumBlocks; }
00081 
00082     /**
00083      * Return the number of blocks that are currently allocated/unallocated.
00084      */
00085     uint16_t getNumUsedBlocks() const
00086     {
00087         RaiiSynchronizer lock;
00088         (void)lock;
00089         return used_;
00090     }
00091     uint16_t getNumFreeBlocks() const
00092     {
00093         RaiiSynchronizer lock;
00094         (void)lock;
00095         return static_cast<uint16_t>(NumBlocks - used_);
00096     }
00097 
00098     /**
00099      * Returns the maximum number of blocks that were ever allocated at the same time.
00100      */
00101     uint16_t getPeakNumUsedBlocks() const
00102     {
00103         RaiiSynchronizer lock;
00104         (void)lock;
00105         return max_used_;
00106     }
00107 };
00108 
00109 /**
00110  * Limits the maximum number of blocks that can be allocated in a given allocator.
00111  */
00112 class LimitedPoolAllocator : public IPoolAllocator
00113 {
00114     IPoolAllocator& allocator_;
00115     const uint16_t max_blocks_;
00116     uint16_t used_blocks_;
00117 
00118 public:
00119     LimitedPoolAllocator(IPoolAllocator& allocator, std::size_t max_blocks)
00120         : allocator_(allocator)
00121         , max_blocks_(static_cast<uint16_t>(min<std::size_t>(max_blocks, 0xFFFFU)))
00122         , used_blocks_(0)
00123     {
00124         UAVCAN_ASSERT(max_blocks_ > 0);
00125     }
00126 
00127     virtual void* allocate(std::size_t size);
00128     virtual void deallocate(const void* ptr);
00129 
00130     virtual uint16_t getBlockCapacity() const;
00131 };
00132 
00133 // ----------------------------------------------------------------------------
00134 
00135 /*
00136  * PoolAllocator<>
00137  */
00138 template <std::size_t PoolSize, uint8_t BlockSize, typename RaiiSynchronizer>
00139 const uint16_t PoolAllocator<PoolSize, BlockSize, RaiiSynchronizer>::NumBlocks;
00140 
00141 template <std::size_t PoolSize, uint8_t BlockSize, typename RaiiSynchronizer>
00142 PoolAllocator<PoolSize, BlockSize, RaiiSynchronizer>::PoolAllocator() :
00143     free_list_(reinterpret_cast<Node*>(pool_.bytes)),
00144     used_(0),
00145     max_used_(0)
00146 {
00147     // The limit is imposed by the width of the pool usage tracking variables.
00148     StaticAssert<((PoolSize / BlockSize) <= 0xFFFFU)>::check();
00149 
00150     (void)std::memset(pool_.bytes, 0, PoolSize);
00151     for (unsigned i = 0; (i + 1) < (NumBlocks - 1 + 1); i++) // -Werror=type-limits
00152     {
00153         // coverity[dead_error_line : FALSE]
00154         free_list_[i].next = free_list_ + i + 1;
00155     }
00156     free_list_[NumBlocks - 1].next = UAVCAN_NULLPTR;
00157 }
00158 
00159 template <std::size_t PoolSize, uint8_t BlockSize, typename RaiiSynchronizer>
00160 void* PoolAllocator<PoolSize, BlockSize, RaiiSynchronizer>::allocate(std::size_t size)
00161 {
00162     if (free_list_ == UAVCAN_NULLPTR || size > BlockSize)
00163     {
00164         return UAVCAN_NULLPTR;
00165     }
00166 
00167     RaiiSynchronizer lock;
00168     (void)lock;
00169 
00170     void* pmem = free_list_;
00171     free_list_ = free_list_->next;
00172 
00173     // Statistics
00174     UAVCAN_ASSERT(used_ < NumBlocks);
00175     used_++;
00176     if (used_ > max_used_)
00177     {
00178         max_used_ = used_;
00179     }
00180 
00181     return pmem;
00182 }
00183 
00184 template <std::size_t PoolSize, uint8_t BlockSize, typename RaiiSynchronizer>
00185 void PoolAllocator<PoolSize, BlockSize, RaiiSynchronizer>::deallocate(const void* ptr)
00186 {
00187     if (ptr == UAVCAN_NULLPTR)
00188     {
00189         return;
00190     }
00191 
00192     RaiiSynchronizer lock;
00193     (void)lock;
00194 
00195     Node* p = static_cast<Node*>(const_cast<void*>(ptr));
00196     p->next = free_list_;
00197     free_list_ = p;
00198 
00199     // Statistics
00200     UAVCAN_ASSERT(used_ > 0);
00201     used_--;
00202 }
00203 
00204 }
00205 
00206 #endif // UAVCAN_DYNAMIC_MEMORY_HPP_INCLUDED