multi_simple_seq_fit_impl.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 972 行 · 第 1/3 页

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2007. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/interprocess for documentation.
//
//////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP
#define BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP

#if (defined _MSC_VER) && (_MSC_VER >= 1200)
#  pragma once
#endif

#include <boost/interprocess/detail/config_begin.hpp>
#include <boost/interprocess/detail/workaround.hpp>

#include <boost/interprocess/interprocess_fwd.hpp>
#include <boost/interprocess/allocators/allocation_type.hpp>
#include <boost/interprocess/offset_ptr.hpp>
#include <boost/interprocess/sync/interprocess_mutex.hpp>
#include <boost/interprocess/exceptions.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/multi_segment_services.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/type_with_alignment.hpp>
#include <boost/interprocess/sync/scoped_lock.hpp>
#include <algorithm>
#include <utility>
#include <cstring>

#include <assert.h>
#include <new>

/*!\file
   Describes sequential fit algorithm used to allocate objects in shared memory.
   This class is intended as a base class for single segment and multi-segment
   implementations.
*/

namespace boost {

namespace interprocess {

namespace detail {

/*!This class implements the simple sequential fit algorithm with a simply
   linked list of free buffers.
   This class is intended as a base class for single segment and multi-segment
   implementations.*/
template<class MutexFamily, class VoidPointer>
class simple_seq_fit_impl
{
   //Non-copyable
   simple_seq_fit_impl();
   simple_seq_fit_impl(const simple_seq_fit_impl &);
   simple_seq_fit_impl &operator=(const simple_seq_fit_impl &);

   public:
   /*!Shared interprocess_mutex family used for the rest of the Interprocess framework*/
   typedef MutexFamily        mutex_family;
   /*!Pointer type to be used with the rest of the Interprocess framework*/
   typedef VoidPointer        void_pointer;

   private:
   struct block_ctrl;
   typedef typename detail::
      pointer_to_other<void_pointer, block_ctrl>::type block_ctrl_ptr;

   /*!Block control structure*/
   struct block_ctrl
   {
      /*!Offset pointer to the next block.*/
      block_ctrl_ptr m_next;
      /*!This block's memory size (including block_ctrl 
         header) in BasicSize units*/
      std::size_t    m_size;
   
      std::size_t get_user_bytes() const
      {  return this->m_size*Alignment - BlockCtrlBytes; }

      std::size_t get_total_bytes() const
      {  return this->m_size*Alignment; }

      static block_ctrl *get_block_from_addr(void *addr)
      {
         return reinterpret_cast<block_ctrl*>
            (reinterpret_cast<char*>(addr) - BlockCtrlBytes);
      }

      void *get_addr() const
      {
         return reinterpret_cast<block_ctrl*>
            (reinterpret_cast<const char*>(this) + BlockCtrlBytes);
      }

   };

   /*!Shared interprocess_mutex to protect memory allocate/deallocate*/
   typedef typename MutexFamily::mutex_type        interprocess_mutex;

   /*!This struct includes needed data and derives from
      interprocess_mutex to allow EBO when using null interprocess_mutex*/
   struct header_t : public interprocess_mutex
   {
      /*!Pointer to the first free block*/
      block_ctrl        m_root;
      /*!Allocated bytes for internal checking*/
      std::size_t       m_allocated;
      /*!The size of the memory segment*/
      std::size_t       m_size;
   }  m_header;

   public:
   /*!Constructor. "size" is the total size of the managed memory segment, 
      "extra_hdr_bytes" indicates the extra bytes beginning in the sizeof(simple_seq_fit_impl)
      offset that the allocator should not use at all.*/
   simple_seq_fit_impl           (std::size_t size, std::size_t extra_hdr_bytes);
   /*!Destructor.*/
   ~simple_seq_fit_impl();
   /*!Obtains the minimum size needed by the algorithm*/
   static std::size_t get_min_size (std::size_t extra_hdr_bytes);

   //Functions for single segment management

   /*!Allocates bytes, returns 0 if there is not more memory*/
   void* allocate             (std::size_t nbytes);

   /*!Deallocates previously allocated bytes*/
   void   deallocate          (void *addr);

   /*!Returns the size of the memory segment*/
   std::size_t get_size()  const;

   /*!Increases managed memory in extra_size bytes more*/
   void grow(std::size_t extra_size);

   /*!Returns true if all allocated memory has been deallocated*/
   bool all_memory_deallocated();

   /*!Makes an internal sanity check and returns true if success*/
   bool check_sanity();

   //!Initializes to zero all the memory that's not in use.
   //!This function is normally used for security reasons.
   void clear_free_memory();

   std::pair<void *, bool>
      allocation_command  (allocation_type command,   std::size_t limit_size,
                           std::size_t preferred_size,std::size_t &received_size, 
                           void *reuse_ptr = 0, std::size_t backwards_multiple = 1);

   /*!Returns the size of the buffer previously allocated pointed by ptr*/
   std::size_t size(void *ptr) const;

   /*!Allocates aligned bytes, returns 0 if there is not more memory.
      Alignment must be power of 2*/
   void* allocate_aligned     (std::size_t nbytes, std::size_t alignment);

   /*!Allocates bytes, if there is no more memory, it executes functor
      f(std::size_t) to allocate a new segment to manage. The functor returns 
      std::pair<void*, std::size_t> indicating the base address and size of 
      the new segment. If the new segment can't be allocated, allocate
      it will return 0.*/
   void* multi_allocate(std::size_t nbytes);

   private:
   /*!Real allocation algorithm with min allocation option*/
   std::pair<void *, bool> priv_allocate(allocation_type command
                                        ,std::size_t min_size
                                        ,std::size_t preferred_size
                                        ,std::size_t &received_size
                                        ,void *reuse_ptr = 0);
   /*!Returns next block if it's free.
      Returns 0 if next block is not free.*/
   block_ctrl *priv_next_block_if_free(block_ctrl *ptr);

   /*!Returns previous block's if it's free.
      Returns 0 if previous block is not free.*/
   std::pair<block_ctrl*, block_ctrl*>priv_prev_block_if_free(block_ctrl *ptr);

   /*!Real expand function implementation*/
   bool priv_expand(void *ptr
                   ,std::size_t min_size, std::size_t preferred_size
                   ,std::size_t &received_size);

   /*!Real expand to both sides implementation*/
   void* priv_expand_both_sides(allocation_type command
                               ,std::size_t min_size
                               ,std::size_t preferred_size
                               ,std::size_t &received_size
                               ,void *reuse_ptr
                               ,bool only_preferred_backwards);

   /*!Real shrink function implementation*/
   bool priv_shrink(void *ptr
                   ,std::size_t max_size, std::size_t preferred_size
                   ,std::size_t &received_size);

   //!Real private aligned allocation function
   void* priv_allocate_aligned     (std::size_t nbytes, std::size_t alignment);

   /*!Checks if block has enough memory and splits/unlinks the block
      returning the address to the users*/
   void* priv_check_and_allocate(std::size_t units
                                ,block_ctrl* prev
                                ,block_ctrl* block
                                ,std::size_t &received_size);
   /*!Real deallocation algorithm*/
   void priv_deallocate(void *addr);

   /*!Makes a new memory portion available for allocation*/
   void priv_add_segment(void *addr, std::size_t size);

   enum { Alignment      = boost::alignment_of<boost::detail::max_align>::value  };
   enum { BlockCtrlBytes = detail::ct_rounded_size<sizeof(block_ctrl), Alignment>::value  };
   enum { BlockCtrlSize  = BlockCtrlBytes/Alignment   };
   enum { MinBlockSize   = BlockCtrlSize + Alignment  };

   public:
   enum {   PayloadPerAllocation = BlockCtrlBytes  };
};

template<class MutexFamily, class VoidPointer>
inline simple_seq_fit_impl<MutexFamily, VoidPointer>::
   simple_seq_fit_impl(std::size_t size, std::size_t extra_hdr_bytes)
{
   //Initialize sizes and counters
   m_header.m_allocated = 0;
   m_header.m_size      = size;

   //Initialize pointers
   std::size_t block1_off  = detail::get_rounded_size(sizeof(*this)+extra_hdr_bytes, Alignment);
   m_header.m_root.m_next  = reinterpret_cast<block_ctrl*>
                              (reinterpret_cast<char*>(this) + block1_off);
   m_header.m_root.m_next->m_size  = (size - block1_off)/Alignment;
   m_header.m_root.m_next->m_next  = &m_header.m_root;
}

template<class MutexFamily, class VoidPointer>
inline simple_seq_fit_impl<MutexFamily, VoidPointer>::~simple_seq_fit_impl()
{
   //There is a memory leak!
//   assert(m_header.m_allocated == 0);
//   assert(m_header.m_root.m_next->m_next == block_ctrl_ptr(&m_header.m_root));
}

template<class MutexFamily, class VoidPointer>
inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::grow(std::size_t extra_size)
{  
   //Old highest address block's end offset
   std::size_t old_end = m_header.m_size/Alignment*Alignment;

   //Update managed buffer's size
   m_header.m_size += extra_size;

   //We need at least MinBlockSize blocks to create a new block
   if((m_header.m_size - old_end) < MinBlockSize){
      return;
   }

   //We'll create a new free block with extra_size bytes
   block_ctrl *new_block = reinterpret_cast<block_ctrl*>
                              (reinterpret_cast<char*>(this) + old_end);

   new_block->m_next = 0;
   new_block->m_size = (m_header.m_size - old_end)/Alignment;
   m_header.m_allocated += new_block->m_size*Alignment;
   this->priv_deallocate(reinterpret_cast<char*>(new_block) + BlockCtrlBytes);
}

template<class MutexFamily, class VoidPointer>
inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_add_segment(void *addr, std::size_t size)
{  
   //Check size
   assert(!(size < MinBlockSize));
   if(size < MinBlockSize)
      return;
   //Construct big block using the new segment
   block_ctrl *new_block   = static_cast<block_ctrl *>(addr);
   new_block->m_size       = size/Alignment;
   new_block->m_next       = 0;
   //Simulate this block was previously allocated
   m_header.m_allocated   += new_block->m_size*Alignment; 
   //Return block and insert it in the free block list
   this->priv_deallocate(reinterpret_cast<char*>(new_block) + BlockCtrlBytes);
}

template<class MutexFamily, class VoidPointer>
inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>::get_size()  const
   {  return m_header.m_size;  }

template<class MutexFamily, class VoidPointer>
inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>::
   get_min_size (std::size_t extra_hdr_bytes)
{
   return detail::get_rounded_size(sizeof(simple_seq_fit_impl)+extra_hdr_bytes
                                  ,Alignment)
          + MinBlockSize;
}

template<class MutexFamily, class VoidPointer>
inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>::
    all_memory_deallocated()
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   return m_header.m_allocated == 0 &&
          detail::get_pointer(m_header.m_root.m_next->m_next) == &m_header.m_root;
}

template<class MutexFamily, class VoidPointer>
inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::clear_free_memory()
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   block_ctrl *block = detail::get_pointer(m_header.m_root.m_next);

   //Iterate through all free portions