Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : #ifndef MCRL2_UTILITIES_MEMORY_POOL_H_
      11             : #define MCRL2_UTILITIES_MEMORY_POOL_H_
      12             : 
      13             : #include "mcrl2/utilities/detail/free_list.h"
      14             : #include "mcrl2/utilities/noncopyable.h"
      15             : #include "mcrl2/utilities/mutex.h"
      16             : 
      17             : #include <array>
      18             : #include <cstdint>
      19             : #include <forward_list>
      20             : #include <type_traits>
      21             : #include <mutex>
      22             : 
      23             : namespace mcrl2
      24             : {
      25             : namespace utilities
      26             : {
      27             : 
      28             : /// \brief The memory pool allocates elements of size T from blocks.
      29             : /// \details When ThreadSafe is true then the thread-safe guarantees will be satisfied.
      30             : template <class T, 
      31             :           std::size_t ElementsPerBlock = 1024, 
      32             :           bool ThreadSafe = false>
      33             : class memory_pool : private mcrl2::utilities::noncopyable
      34             : {
      35             : public:
      36        1623 :   memory_pool() = default;
      37             : 
      38             :   /// \brief Triggers the (possibly non-trivial) destructor of all elements stored
      39             :   ///        in the pool.
      40         193 :   ~memory_pool()
      41             :   {
      42         193 :     m_freelist.destructive_mark();
      43             : 
      44             :     /// For all actual elements stored in the pool trigger the destructor.
      45         193 :     bool first_block = true;
      46         385 :     for (auto& block : m_blocks)
      47             :     {
      48         192 :       if (first_block)
      49             :       {
      50             :         // This is the first block, for that one only m_current_index elements were inserted.
      51        1770 :         for (std::size_t index = 0; index < m_current_index; ++index)
      52             :         {
      53        1578 :           auto& slot = block[index];
      54        1578 :           if (!slot.is_marked())
      55             :           {
      56           0 :             reinterpret_cast<T*>(&slot)->~T();
      57             :           }
      58             :         }
      59         192 :         first_block = false;
      60             :       }
      61             :       else
      62             :       {
      63           0 :         for (auto& slot : block)
      64             :         {
      65           0 :           if (!slot.is_marked())
      66             :           {
      67           0 :             reinterpret_cast<T*>(&slot)->~T();
      68             :           }
      69             :         }
      70             :       }
      71             :     }
      72             : 
      73         193 :     assert(m_freelist.empty());
      74         193 :   }
      75             : 
      76             :   /// \brief Reuses memory from block and allocates a new block when
      77             :   ///        no slots are free.
      78             :   /// \returns A pointer to a block of memory that can store an object of type T.
      79          30 :   /// \threadsafe
      80     1172312 :   T* allocate()
      81             :   {
      82          30 :     // Only allow one thread to allocate at the time.
      83     1172312 :     m_block_mutex.lock();
      84          30 : 
      85     1172312 :     if (!m_freelist.empty())
      86           0 :     {
      87       62720 :       T& element = m_freelist.pop_front();
      88       62720 :       m_block_mutex.unlock();
      89       62720 :       return &element;
      90             :     }
      91          30 : 
      92     1109592 :     if (m_current_index >= ElementsPerBlock)
      93             :     {
      94           1 :       // The whole buffer was used so allocate a new one.
      95        2265 :       m_blocks.emplace_front();
      96        2265 :       ++m_number_of_blocks;
      97        2264 :       m_current_index = 0;
      98             :     }
      99             : 
     100          30 :     // The object was last written as this slot is not part of the freelist.
     101     1109592 :     T& slot = (m_blocks.front()[m_current_index++]).element();
     102          30 : 
     103     1109622 :     assert(contains(&slot));
     104     1109622 :     m_block_mutex.unlock();
     105     1109592 :     return &slot;
     106             :   }
     107             : 
     108           0 :   /// \brief Free the memory used by the given pointer that has been allocated by this pool.
     109      240725 :   void deallocate(T* pointer)
     110           0 :   {    
     111      240725 :     m_block_mutex.lock();
     112           0 : 
     113      240725 :     assert(contains(pointer));
     114      240725 :     m_freelist.push_front(reinterpret_cast<Slot&>(*pointer));
     115           0 : 
     116      240725 :     m_block_mutex.unlock();
     117      240725 :   }
     118             : 
     119             :   /// \brief Frees blocks that are no longer storing elements of T.
     120           0 :   /// \returns The number of blocks that have been removed.
     121        9139 :   std::size_t consolidate()
     122           0 :   {
     123        9139 :     m_block_mutex.lock();
     124           0 : 
     125        9139 :     m_freelist.destructive_mark();
     126        9139 :     std::size_t old_number_of_blocks = m_number_of_blocks;
     127             : 
     128           0 :     // Keep track of the last block to be able to erase the current block.
     129        9139 :     auto block_before_it = m_blocks.before_begin();
     130       11763 :     for (auto it = m_blocks.begin(); it != m_blocks.end();)
     131           0 :     {
     132        2624 :       Block& block = *it;
     133             : 
     134           0 :       // Keep track of the head of the freelist.
     135        2624 :       FreelistIt old_freelist_head = m_freelist.begin();
     136             : 
     137           0 :       // Indicate that current block only contains slots in the freelist.
     138        2624 :       bool block_only_freelist = true;
     139     2494048 :       for (Slot& slot : block)
     140           0 :       {
     141     2491424 :         if (slot.is_marked())
     142           0 :         {
     143      351901 :           m_freelist.push_front(slot);
     144             :         }
     145             :         else
     146             :         {
     147           0 :           // There is one slot that was not part of the freelist.
     148     2139523 :           block_only_freelist = false;
     149             :         }
     150             :       }
     151             : 
     152           0 :       // Erase blocks that only have elements in the freelist.
     153        2624 :       if (block_only_freelist)
     154             :       {
     155           0 :         // Remove the slots in the freelist that point into this block.
     156         208 :         m_freelist.erase_after(m_freelist.before_begin(), old_freelist_head);
     157             : 
     158           0 :         // The current block only has elements in the freelist, so erase it.
     159         208 :         it = m_blocks.erase_after(block_before_it);
     160         208 :         --m_number_of_blocks;
     161             :       }
     162             :       else
     163           0 :       {
     164        2416 :         block_before_it = it;
     165        2416 :         ++it;
     166             :       }
     167             :     }
     168           0 : 
     169        9139 :     m_block_mutex.unlock();
     170        9139 :     return old_number_of_blocks - m_number_of_blocks;
     171             :   }
     172             : 
     173             :   /// \returns True when thi memory pool has space for at least one more element without allocating
     174             :   ///          new memory.
     175             :   bool has_free_slots() const noexcept
     176             :   {
     177             :     // The freelist is not full, i.e. points to some slot or the index has not yet reached the end.
     178             :     return m_current_index < ElementsPerBlock || m_freelist.empty();
     179             :   }
     180             : 
     181             :   /// \returns The total number of elements that could be stored in this memory pool.
     182             :   std::size_t capacity() const noexcept
     183             :   {
     184             :     return m_number_of_blocks * ElementsPerBlock;
     185             :   }
     186             : 
     187             :   // Move constructor and assignment are possible.
     188             :   memory_pool(memory_pool&& other) = default;
     189             :   memory_pool& operator=(memory_pool&& other) = default;
     190             : 
     191             : private:
     192             :   using Freelist = typename detail::free_list<T>;
     193             :   using FreelistIt = typename Freelist::iterator;
     194             :   using Slot = typename Freelist::slot;
     195             : 
     196             :   /// \brief An array that stores ElementsPerBlock number of objects of type T.
     197             :   using Block = std::array<Slot, ElementsPerBlock>;
     198             : 
     199             :   /// \brief The last slot in the first block that has never been returned by allocate.
     200             :   using SizeType = typename std::conditional<ThreadSafe, std::atomic<std::size_t>, std::size_t>::type;
     201             :   SizeType m_current_index = ElementsPerBlock;
     202             : 
     203             :   /// \brief Equal to the size of the blocks array to prevent iterating over the block list.
     204             :   SizeType m_number_of_blocks = 0;
     205             : 
     206             :   /// \brief The list of blocks allocated by this pool.
     207             :   std::forward_list<Block> m_blocks;
     208             : 
     209             :   /// \brief Ensures that the block list is only modified by a single thread.
     210             :   mcrl2::utilities::mutex m_block_mutex = {};
     211             : 
     212             :   /// \brief Indicates the head of the freelist.
     213             :   Freelist m_freelist;
     214             : 
     215         164 :   /// \returns Check whether the pointer is contained in this memory pool.
     216     1350183 :   bool contains(T* p)
     217         164 :   {
     218     1350183 :     assert(p != nullptr);
     219         164 : 
     220     1350347 :     std::uintptr_t pointer = reinterpret_cast<std::uintptr_t>(p);
     221     6995547 :     for (auto& block : m_blocks)
     222         164 :     {
     223     6995711 :       std::uintptr_t firstSlot = reinterpret_cast<std::uintptr_t>(block.data());
     224     6995547 :       if (firstSlot <= pointer && pointer < firstSlot + sizeof(Slot) * ElementsPerBlock)
     225         164 :       {
     226     1350347 :         assert((pointer - firstSlot) % sizeof(Slot) == 0);
     227     1350183 :         return true;
     228             :       }
     229             :     }
     230           0 : 
     231           0 :     return false;
     232             :   }
     233             : 
     234             : };
     235             : 
     236             : } // namespace utilities
     237             : } // namespace mcrl2
     238             : 
     239             : #endif // MCRL2_UTILITIES_MEMORY_POOL_H_