simple_seq_fit_impl.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2008. 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/min_max.hpp>
#include <boost/interprocess/detail/type_traits.hpp>
#include <boost/interprocess/sync/scoped_lock.hpp>
#include <boost/interprocess/mem_algo/detail/mem_algo_common.hpp>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cassert>
#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;

   typedef detail::basic_multiallocation_iterator
      <void_pointer> multiallocation_iterator;
   typedef detail::basic_multiallocation_chain
      <void_pointer> multiallocation_chain;

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

   class block_ctrl;
   friend class block_ctrl;

   //!Block control structure
   class block_ctrl
   {
      public:
      //!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; }
   };

   //!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;
      //!The extra size required by the segment
      std::size_t       m_extra_hdr_bytes;
   }  m_header;

   friend class detail::basic_multiallocation_iterator<void_pointer>;
   friend class detail::memory_algorithm_common<simple_seq_fit_impl>;

   typedef detail::memory_algorithm_common<simple_seq_fit_impl> algo_impl_t;

   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);

   /// @cond

   //!Multiple element allocation, same size
   multiallocation_iterator allocate_many(std::size_t elem_bytes, std::size_t num_elements);

   //!Multiple element allocation, different size
   multiallocation_iterator allocate_many(const std::size_t *elem_sizes, std::size_t n_elements, std::size_t sizeof_element);

   //!Multiple element deallocation
   void deallocate_many(multiallocation_iterator it);

   /// @endcond

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

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

   //!Returns the number of free bytes of the memory segment
   std::size_t get_free_memory()  const;

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

   //!Decreases managed memory as much as possible
   void shrink_to_fit();

   //!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 zero_free_memory();

   template<class T>
   std::pair<T *, bool>
      allocation_command  (allocation_type command,   std::size_t limit_size,
                           std::size_t preferred_size,std::size_t &received_size, 
                           T *reuse_ptr = 0);

   std::pair<void *, bool>
      raw_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 sizeof_object = 1);

   //!Returns the size of the buffer previously allocated pointed by ptr
   std::size_t size(const 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);

   private:

   //!Obtains the pointer returned to the user from the block control
   static void *priv_get_user_buffer(const block_ctrl *block);

   //!Obtains the block control structure of the user buffer
   static block_ctrl *priv_get_block(const void *ptr);

   //!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);

   std::pair<void *, bool> priv_allocation_command(allocation_type command
                                        ,std::size_t min_size
                                        ,std::size_t preferred_size
                                        ,std::size_t &received_size
                                        ,void *reuse_ptr
                                        ,std::size_t sizeof_object);

   //!Returns the number of total units that a user buffer
   //!of "userbytes" bytes really occupies (including header)
   static std::size_t priv_get_total_units(std::size_t userbytes);

   static std::size_t priv_first_block_offset(const void *this_ptr, std::size_t extra_hdr_bytes);
   std::size_t priv_block_end_offset() const;

   //!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);

   //!Check if this block is free (not allocated)
   bool priv_is_allocated_block(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 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);

   void priv_mark_new_allocated_block(block_ctrl *block);

   public:
   static const std::size_t Alignment      = detail::alignment_of<detail::max_align>::value;
   private:
   static const std::size_t BlockCtrlBytes = detail::ct_rounded_size<sizeof(block_ctrl), Alignment>::value;
   static const std::size_t BlockCtrlUnits = BlockCtrlBytes/Alignment;
   static const std::size_t MinBlockUnits  = BlockCtrlUnits;
   static const std::size_t MinBlockSize   = MinBlockUnits*Alignment;
   static const std::size_t AllocatedCtrlBytes = BlockCtrlBytes;
   static const std::size_t AllocatedCtrlUnits = BlockCtrlUnits;
   static const std::size_t UsableByPreviousChunk = 0;

   public:
   static const std::size_t PayloadPerAllocation = BlockCtrlBytes;
};

template<class MutexFamily, class VoidPointer>
inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>
   ::priv_first_block_offset(const void *this_ptr, std::size_t extra_hdr_bytes)
{
   //First align "this" pointer
   std::size_t uint_this         = (std::size_t)this_ptr;
   std::size_t uint_aligned_this = uint_this/Alignment*Alignment;
   std::size_t this_disalignment = (uint_this - uint_aligned_this);
   std::size_t block1_off = 
      detail::get_rounded_size(sizeof(simple_seq_fit_impl) + extra_hdr_bytes + this_disalignment, Alignment)
      - this_disalignment;
   algo_impl_t::assert_alignment(this_disalignment + block1_off);
   return block1_off;
}

template<class MutexFamily, class VoidPointer>
inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>
   ::priv_block_end_offset() const
{
   //First align "this" pointer
   std::size_t uint_this         = (std::size_t)this;
   std::size_t uint_aligned_this = uint_this/Alignment*Alignment;
   std::size_t this_disalignment = (uint_this - uint_aligned_this);
   std::size_t old_end = 
      detail::get_truncated_size(m_header.m_size + this_disalignment, Alignment)
      - this_disalignment;
   algo_impl_t::assert_alignment(old_end + this_disalignment);
   return old_end;
}

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;
   m_header.m_extra_hdr_bytes = extra_hdr_bytes;

   //Initialize pointers
   std::size_t block1_off = priv_first_block_offset(this, extra_hdr_bytes);

   m_header.m_root.m_next  = reinterpret_cast<block_ctrl*>
      ((reinterpret_cast<char*>(this) + block1_off));
   algo_impl_t::assert_alignment(detail::get_pointer(m_header.m_root.m_next));
   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 = this->priv_block_end_offset();

   //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);

   algo_impl_t::assert_alignment(new_block);
   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(priv_get_user_buffer(new_block));
}

template<class MutexFamily, class VoidPointer>
void simple_seq_fit_impl<MutexFamily, VoidPointer>::shrink_to_fit()
{
   //Get the root and the first memory block
   block_ctrl *prev                 = &m_header.m_root;
   block_ctrl *last                 = &m_header.m_root;
   block_ctrl *block                = detail::get_pointer(last->m_next);
   block_ctrl *root                 = &m_header.m_root;

   //No free block?
   if(block == root) return;

   //Iterate through the free block list
   while(block != root){
      prev  = last;