Line data    Source code

       1             : /*
       2             :  *
       3             :  *
       4             :  * Distributed under the OpenDDS License.
       5             :  * See: http://www.opendds.org/license.html
       6             :  */
       7             : 
       8             : #ifndef OPENDDS_DCPS_MEMORYPOOL_H
       9             : #define OPENDDS_DCPS_MEMORYPOOL_H
      10             : 
      11             : #include "dcps_export.h"
      12             : 
      13             : OPENDDS_BEGIN_VERSIONED_NAMESPACE_DECL
      14             : 
      15             : namespace OpenDDS {
      16             : namespace Test {
      17             :   class MemoryPoolTest;
      18             :   class FreeIndexTest;
      19             : }
      20             : namespace DCPS {
      21             : 
      22             : /// Header of all allocations - found at beginning of allocation inside pool.
      23             : /// Extra room must be added to each allocation for this header.
      24             : class OpenDDS_Dcps_Export AllocHeader {
      25             : public:
      26             :   /** Construct */
      27             :   AllocHeader();
      28             : 
      29             :   /** Get alloc size */
      30       66371 :   unsigned int size() const { return is_free() ? -alloc_size_ : alloc_size_; }
      31             :   /** Get prev alloc size */
      32           0 :   unsigned int prev_size() const { return prev_size_; }
      33             :   /** Is this alloc free */
      34       82036 :   bool is_free() const { return alloc_size_ < 0; }
      35             : 
      36             :   /** Get pointer to start of my buffer */
      37             :   unsigned char* ptr() const;
      38             : 
      39             :   /** Go to next header */
      40             :   AllocHeader* next_adjacent();
      41             : 
      42             :   /** Go to prev header */
      43             :   AllocHeader* prev_adjacent();
      44             : 
      45             :   /** Allocate from this block: change size, and mark as allocated */
      46             :   void allocate(size_t size);
      47             : 
      48             :   /** Set the size value stored in this header */
      49             :   void set_size(size_t size);
      50             :   /** Set the prev size value stored in this header */
      51        1305 :   void set_prev_size(int size) { prev_size_ = size; }
      52             :   /** Mark this block as allocated */
      53         784 :   void set_allocated() { if (alloc_size_ < 0) alloc_size_ = - alloc_size_; }
      54             : 
      55             :   /** Join with the next adjacent block */
      56             :   void join_next();
      57             : 
      58             : protected:
      59             :   /** Sizes are those of buffers, does not include size of headers */
      60             :   int alloc_size_; ///< Size of my buffer, negative if free, positive if alloc
      61             :   int prev_size_;  ///< Size of previous buffer, or 0 if first, never negative
      62             : };
      63             : 
      64             : /// Header of free allocations - found at beginning of allocation inside pool.
      65             : /// This forces a minimum allocation size, so that, when freed, header can
      66             : /// be cast to this type.
      67             : class OpenDDS_Dcps_Export FreeHeader : public AllocHeader {
      68             : public:
      69             :   /** Initialize the first AllocHeader with its size */
      70             :   void init_free_block(unsigned int pool_size);
      71             : 
      72             :   /** Mark as free */
      73             :   void set_free();
      74             : 
      75             :   /** Get next equal or smaller free block in size order */
      76             :   FreeHeader* smaller_free(unsigned char* pool_base) const;
      77             :   /** Get next equal or larger free block in size order */
      78             :   FreeHeader* larger_free(unsigned char* pool_base) const;
      79             : 
      80             :   /** Set the next equal or smaller free block in size order */
      81             :   void set_smaller_free(FreeHeader* next, unsigned char* pool_base);
      82             :   /** Set the next equal or larger free block in size order */
      83             :   void set_larger_free(FreeHeader* prev, unsigned char* pool_base);
      84             : 
      85             : private:
      86             :   size_t offset_smaller_free_; ///< Offset to smaller free block in size order
      87             :   size_t offset_larger_free_;  ///< Offset to larger free block in size order
      88             : };
      89             : 
      90             : /// Node of free index.  Should point to smallest free block of the range
      91             : /// from size (inclusive) to limit (non inclusive).  If multiple free
      92             : /// allocations of the smallest size in range exist, should point to the one
      93             : /// which is the "smallest" (in free list order).
      94             : class FreeIndexNode {
      95             : public:
      96             :   FreeIndexNode();
      97             :   /** Set the free alloc this node points to */
      98        2802 :   void set_ptr(FreeHeader* ptr) { ptr_ = ptr; }
      99             :   /** Set the sizes for this node */
     100             :   void set_sizes(size_t size, size_t limit);
     101             : 
     102             :   /** Does this node contain a given size */
     103         299 :   bool contains(size_t size) { return ((size >= size_) && (size < limit_)); }
     104             : 
     105             :   /** Get this node's free block */
     106       54712 :   FreeHeader* ptr() { return ptr_; }
     107             :   /** Get this node's minimum size */
     108           8 :   unsigned int size() const { return static_cast<unsigned int>(size_); }
     109             : 
     110             : private:
     111             :   size_t size_;       ///< size of buffer
     112             :   size_t limit_;      ///< upper_limit of buffer size (one too large)
     113             :   FreeHeader* ptr_;   ///< points to smallest free alloc of size_ or larger
     114             : };
     115             : 
     116             : /// Index of free nodes in memory pool.
     117             : /// Allows for a faster search of free nodes
     118             : class OpenDDS_Dcps_Export FreeIndex {
     119             :   friend class Test::MemoryPoolTest;
     120             :   friend class Test::FreeIndexTest;
     121             : public:
     122             :   explicit FreeIndex(FreeHeader*& largest_free);
     123             :   /** Initialize index with initial free block */
     124             :   void init(FreeHeader* init_free_block);
     125             : 
     126             :   /** Add free block to index */
     127             :   void add(FreeHeader* free_block);
     128             :   /** Remove free block from index */
     129             :   void remove(FreeHeader* free_block, FreeHeader* next_largest);
     130             : 
     131             :   /** Find smallest free block of size or larger */
     132             :   FreeHeader* find(size_t size, unsigned char* base);
     133             : 
     134             :   /** Calculate index of node corresponding to a size */
     135             :   static unsigned int node_index(size_t size);
     136             : 
     137             : #ifdef VALIDATE_MEMORY_POOL
     138             :   static void validate_index(FreeIndex& index,
     139             :                              unsigned char* base,
     140             :                              bool log = false);
     141             : #endif
     142             : private:
     143             :   enum {
     144             :     min_index_pow = 3,
     145             :     max_index_pow = 12
     146             :   };
     147             :   enum {
     148             :     min_index = 8,    // 2^^3
     149             :     max_index = 4096  // 2^^12
     150             :   };
     151             : 
     152             :   size_t size_;               ///< Number of index nodes
     153             :   FreeHeader*& largest_free_; ///< Memory pool's pointer to largest free block
     154             :   FreeIndexNode nodes_[max_index_pow - min_index_pow + 1];   ///< Index nodes
     155             : };
     156             : 
     157             : // MemoryPool tracks free list, in size order (next meaning largest to smallest)
     158             : // and an index into the list at various sizes, which point to the smallest
     159             : // free allocation of that size or larger (but not larger than the next size).
     160             : // Allocations can be done by checking the index for the needed size, and going
     161             : // to the first free block.
     162             : class OpenDDS_Dcps_Export MemoryPool {
     163             :   friend class Test::MemoryPoolTest;
     164             : public:
     165             :   explicit MemoryPool(unsigned int pool_size, size_t granularity = 8);
     166             :   ~MemoryPool();
     167             : 
     168             :   /** Does the pool include a given pointer */
     169       12017 :   bool includes(void* ptr) const {
     170       12017 :      return (pool_ptr_ <= ptr) && (ptr < pool_ptr_ + pool_size_); }
     171             : 
     172             :   /** Allocate size bytes from the pool **/
     173             :   void* pool_alloc(size_t size);
     174             : 
     175             :   /** Attempt to free an allocation.  Return true if allocation is managed by
     176             :       this pool (and thus was freed).
     177             :    */
     178             :   bool pool_free(void* ptr);
     179             : 
     180             :   /** Low water mark of maximum available bytes for an allocation */
     181             :   size_t lwm_free_bytes() const;
     182             : 
     183             :   /** Calculate aligned size of allocation */
     184         907 :   static size_t align(size_t size, size_t granularity) {
     185         907 :      return (size + granularity - 1) / granularity * granularity; }
     186             : 
     187             :   size_t size () const { return pool_size_; }
     188             : 
     189             : private:
     190             :   const size_t granularity_;     ///< Configured granularity
     191             :   const size_t min_alloc_size_;  ///< Aligned minimum allocation size
     192             :   const size_t pool_size_;       ///< Configured pool size
     193             :   size_t lwm_free_bytes_;        ///< Low water mark of available bytes
     194             :   unsigned char* pool_ptr_;      ///< Pointer to pool
     195             : 
     196             :   FreeHeader* largest_free_;     ///< Pointer to largest free index
     197             :   FreeIndex free_index_;         ///< Index of free nodex
     198             : 
     199             :   enum {
     200             :     min_free_size = sizeof(FreeHeader)
     201             :   };
     202             : 
     203             :   // Helpers
     204             :   void remove_free_alloc(FreeHeader* block_to_alloc);
     205             :   void insert_free_alloc(FreeHeader* block_freed);
     206             :   void join_free_allocs(FreeHeader* block_freed);
     207             :   unsigned char* allocate(FreeHeader* free_block, size_t alloc_size);
     208             : 
     209             :   bool joinable_next(FreeHeader* freed);
     210             :   bool joinable_prev(FreeHeader* freed);
     211             : 
     212             : #ifdef VALIDATE_MEMORY_POOL
     213             :   static void validate_pool(MemoryPool& pool, bool log = false);
     214             : #endif
     215             : };
     216             : 
     217             : }} // end namespaces
     218             : 
     219             : OPENDDS_END_VERSIONED_NAMESPACE_DECL
     220             : 
     221             : #endif // OPENDDS_MEMORY_POOL_H