heap_based_pool_allocator.hpp

00001 /*
00002  * Copyright (C) 2015 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #ifndef UAVCAN_HELPERS_HEAP_BASED_POOL_ALLOCATOR_HPP_INCLUDED
00006 #define UAVCAN_HELPERS_HEAP_BASED_POOL_ALLOCATOR_HPP_INCLUDED
00007 
00008 #include <cstdlib>
00009 #include <uavcan/build_config.hpp>
00010 #include <uavcan/debug.hpp>
00011 #include <uavcan/dynamic_memory.hpp>
00012 
00013 namespace uavcan
00014 {
00015 /**
00016  * A special-purpose implementation of a pool allocator that keeps the pool in the heap using malloc()/free().
00017  * The pool grows dynamically, ad-hoc, thus using as little memory as possible.
00018  *
00019  * Allocated blocks will not be freed back automatically, but there are two ways to force their deallocation:
00020  *  - Call @ref shrink() - this method frees all blocks that are unused at the moment.
00021  *  - Destroy the object - the desctructor calls @ref shrink().
00022  *
00023  * The pool can be limited in growth with hard and soft limits.
00024  * The soft limit defines the value that will be reported via @ref IPoolAllocator::getBlockCapacity().
00025  * The hard limit defines the maximum number of blocks that can be allocated from heap.
00026  * Typically, the hard limit should be equal or greater than the soft limit.
00027  *
00028  * The allocator can be made thread-safe (optional) by means of providing a RAII-lock type via the second template
00029  * argument. The allocator uses the lock only to access the shared state, therefore critical sections are only a few
00030  * cycles long, which implies that it should be acceptable to use hardware IRQ disabling instead of a mutex for
00031  * performance reasons. For example, an IRQ-based RAII-lock type can be implemented as follows:
00032  *     struct RaiiSynchronizer
00033  *     {
00034  *         RaiiSynchronizer()  { __disable_irq(); }
00035  *         ~RaiiSynchronizer() { __enable_irq(); }
00036  *     };
00037  */
00038 template <std::size_t BlockSize,
00039           typename RaiiSynchronizer = char>
00040 class UAVCAN_EXPORT HeapBasedPoolAllocator : public IPoolAllocator,
00041                                              Noncopyable
00042 {
00043     union Node
00044     {
00045         Node* next;
00046     private:
00047         uint8_t data[BlockSize];
00048         long double _aligner1;
00049         long long _aligner2;
00050     };
00051 
00052     const uint16_t capacity_soft_limit_;
00053     const uint16_t capacity_hard_limit_;
00054 
00055     uint16_t num_reserved_blocks_;
00056     uint16_t num_allocated_blocks_;
00057 
00058     Node* reserve_;
00059 
00060 public:
00061     /**
00062      * The allocator initializes with empty reserve, so first allocations will be served from heap.
00063      *
00064      * @param block_capacity_soft_limit     Block capacity that will be reported via @ref getBlockCapacity().
00065      *
00066      * @param block_capacity_hard_limit     Real block capacity limit; the number of allocated blocks will never
00067      *                                      exceed this value. Hard limit should be higher than soft limit.
00068      *                                      Default value is two times the soft limit.
00069      */
00070     HeapBasedPoolAllocator(uint16_t block_capacity_soft_limit,
00071                            uint16_t block_capacity_hard_limit = 0) :
00072         capacity_soft_limit_(block_capacity_soft_limit),
00073         capacity_hard_limit_((block_capacity_hard_limit > 0) ? block_capacity_hard_limit :
00074                              static_cast<uint16_t>(min(static_cast<uint32_t>(block_capacity_soft_limit) * 2U,
00075                                                        static_cast<uint32_t>(NumericTraits<uint16_t>::max())))),
00076         num_reserved_blocks_(0),
00077         num_allocated_blocks_(0),
00078         reserve_(UAVCAN_NULLPTR)
00079     { }
00080 
00081     /**
00082      * The destructor de-allocates all blocks that are currently in the reserve.
00083      * BLOCKS THAT ARE CURRENTLY HELD BY THE APPLICATION WILL LEAK.
00084      */
00085     ~HeapBasedPoolAllocator()
00086     {
00087         shrink();
00088 #if UAVCAN_DEBUG
00089         if (num_allocated_blocks_ > 0)
00090         {
00091             UAVCAN_TRACE("HeapBasedPoolAllocator", "%u BLOCKS LEAKED", num_allocated_blocks_);
00092         }
00093 #endif
00094     }
00095 
00096     /**
00097      * Takes a block from the reserve, unless it's empty.
00098      * In the latter case, allocates a new block in the heap.
00099      */
00100     virtual void* allocate(std::size_t size)
00101     {
00102         if (size > BlockSize)
00103         {
00104             return UAVCAN_NULLPTR;
00105         }
00106 
00107         {
00108             RaiiSynchronizer lock;
00109             (void)lock;
00110 
00111             Node* const p = reserve_;
00112 
00113             if (UAVCAN_LIKELY(p != UAVCAN_NULLPTR))
00114             {
00115                 reserve_ = reserve_->next;
00116                 num_allocated_blocks_++;
00117                 return p;
00118             }
00119 
00120             if (num_reserved_blocks_ >= capacity_hard_limit_)   // Hard limit reached, no further allocations
00121             {
00122                 return UAVCAN_NULLPTR;
00123             }
00124         }
00125 
00126         // Unlikely branch
00127         void* const m = std::malloc(sizeof(Node));
00128         if (m != UAVCAN_NULLPTR)
00129         {
00130             RaiiSynchronizer lock;
00131             (void)lock;
00132 
00133             num_reserved_blocks_++;
00134             num_allocated_blocks_++;
00135         }
00136         return m;
00137     }
00138 
00139     /**
00140      * Puts the block back to reserve.
00141      * The block will not be free()d automatically; see @ref shrink().
00142      */
00143     virtual void deallocate(const void* ptr)
00144     {
00145         if (ptr != UAVCAN_NULLPTR)
00146         {
00147             RaiiSynchronizer lock;
00148             (void)lock;
00149 
00150             Node* const node = static_cast<Node*>(const_cast<void*>(ptr));
00151             node->next = reserve_;
00152             reserve_ = node;
00153 
00154             num_allocated_blocks_--;
00155         }
00156     }
00157 
00158     /**
00159      * The soft limit.
00160      */
00161     virtual uint16_t getBlockCapacity() const { return capacity_soft_limit_; }
00162 
00163     /**
00164      * The hard limit.
00165      */
00166     uint16_t getBlockCapacityHardLimit() const { return capacity_hard_limit_; }
00167 
00168     /**
00169      * Frees all blocks that are not in use at the moment.
00170      * Post-condition is getNumAllocatedBlocks() == getNumReservedBlocks().
00171      */
00172     void shrink()
00173     {
00174         Node* p = UAVCAN_NULLPTR;
00175         for (;;)
00176         {
00177             {
00178                 RaiiSynchronizer lock;
00179                 (void)lock;
00180                 // Removing from reserve and updating the counter.
00181                 p = reserve_;
00182                 if (p != UAVCAN_NULLPTR)
00183                 {
00184                     reserve_ = reserve_->next;
00185                     num_reserved_blocks_--;
00186                 }
00187                 else
00188                 {
00189                     break;
00190                 }
00191             }
00192             // Then freeing, having left the critical section.
00193             std::free(p);
00194         }
00195     }
00196 
00197     /**
00198      * Number of blocks that are currently in use by the application.
00199      */
00200     uint16_t getNumAllocatedBlocks() const
00201     {
00202         RaiiSynchronizer lock;
00203         (void)lock;
00204         return num_allocated_blocks_;
00205     }
00206 
00207     /**
00208      * Number of blocks that are acquired from the heap.
00209      */
00210     uint16_t getNumReservedBlocks() const
00211     {
00212         RaiiSynchronizer lock;
00213         (void)lock;
00214         return num_reserved_blocks_;
00215     }
00216 };
00217 
00218 }
00219 
00220 #endif