boost/interprocess/mem_algo/detail/simple_seq_fit_impl.hpp
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2005-2009. 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/pointer_to_other.hpp> #include <boost/interprocess/interprocess_fwd.hpp> #include <boost/interprocess/containers/allocation_type.hpp> #include <boost/interprocess/containers/container/detail/multiallocation_chain.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 <boost/assert.hpp> #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 boost::container::containers_detail:: basic_multiallocation_chain<VoidPointer> multiallocation_chain; private: class block_ctrl; typedef typename boost:: 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::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_chain allocate_many(std::size_t elem_bytes, std::size_t num_elements) { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- return algo_impl_t::allocate_many(this, elem_bytes, num_elements); } //!Multiple element allocation, different size multiallocation_chain allocate_many(const std::size_t *elem_sizes, std::size_t n_elements, std::size_t sizeof_element) { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- return algo_impl_t::allocate_many(this, elem_sizes, n_elements, sizeof_element); } //!Multiple element deallocation void deallocate_many(multiallocation_chain chain); /// @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 (boost::interprocess::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 (boost::interprocess::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(boost::interprocess::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(boost::interprocess::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(boost::interprocess::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! // BOOST_ASSERT(m_header.m_allocated == 0); // BOOST_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; last = block; block = detail::get_pointer(block->m_next); } char *last_free_end_address = reinterpret_cast<char*>(last) + last->m_size*Alignment; if(last_free_end_address != (reinterpret_cast<char*>(this) + priv_block_end_offset())){ //there is an allocated block in the end of this block //so no shrinking is possible return; } //Check if have only 1 big free block void *unique_block = 0; if(!m_header.m_allocated){ BOOST_ASSERT(prev == root); std::size_t ignore; unique_block = priv_allocate(boost::interprocess::allocate_new, 0, 0, ignore).first; if(!unique_block) return; last = detail::get_pointer(m_header.m_root.m_next); BOOST_ASSERT(last_free_end_address == (reinterpret_cast<char*>(last) + last->m_size*Alignment)); } std::size_t last_units = last->m_size; std::size_t received_size; void *addr = priv_check_and_allocate(last_units, prev, last, received_size); (void)addr; BOOST_ASSERT(addr); BOOST_ASSERT(received_size == last_units*Alignment - AllocatedCtrlBytes); //Shrink it m_header.m_size /= Alignment; m_header.m_size -= last->m_size; m_header.m_size *= Alignment; m_header.m_allocated -= last->m_size*Alignment; if(unique_block) priv_deallocate(unique_block); } template<class MutexFamily, class VoidPointer> inline void simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_mark_new_allocated_block(block_ctrl *new_block) { new_block->m_next = 0; } template<class MutexFamily, class VoidPointer> inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl * simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_get_block(const void *ptr) { return const_cast<block_ctrl*>(reinterpret_cast<const block_ctrl*> (reinterpret_cast<const char*>(ptr) - AllocatedCtrlBytes)); } template<class MutexFamily, class VoidPointer> inline void *simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_get_user_buffer(const typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *block) { return const_cast<char*>(reinterpret_cast<const char*>(block) + AllocatedCtrlBytes); } template<class MutexFamily, class VoidPointer> inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_add_segment(void *addr, std::size_t size) { algo_impl_t::assert_alignment(addr); //Check size BOOST_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(priv_get_user_buffer(new_block)); } 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_free_memory() const { return m_header.m_size - m_header.m_allocated - algo_impl_t::multiple_of_units(sizeof(*this) + m_header.m_extra_hdr_bytes); } 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),Alignment) + detail::get_rounded_size(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>::zero_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 do{ //Just clear user the memory part reserved for the user std::memset( priv_get_user_buffer(block) , 0 , block->get_user_bytes()); block = detail::get_pointer(block->m_next); } while(block != &m_header.m_root); } template<class MutexFamily, class VoidPointer> inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>:: check_sanity() { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- block_ctrl *block = detail::get_pointer(m_header.m_root.m_next); std::size_t free_memory = 0; //Iterate through all blocks obtaining their size while(block != &m_header.m_root){ algo_impl_t::assert_alignment(block); if(!algo_impl_t::check_alignment(block)) return false; //Free blocks's next must be always valid block_ctrl *next = detail::get_pointer(block->m_next); if(!next){ return false; } free_memory += block->m_size*Alignment; block = next; } //Check allocated bytes are less than size if(m_header.m_allocated > m_header.m_size){ return false; } //Check free bytes are less than size if(free_memory > m_header.m_size){ return false; } return true; } template<class MutexFamily, class VoidPointer> inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>:: allocate(std::size_t nbytes) { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- std::size_t ignore; return priv_allocate(boost::interprocess::allocate_new, nbytes, nbytes, ignore).first; } template<class MutexFamily, class VoidPointer> inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>:: allocate_aligned(std::size_t nbytes, std::size_t alignment) { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- return algo_impl_t:: allocate_aligned(this, nbytes, alignment); } template<class MutexFamily, class VoidPointer> template<class T> inline std::pair<T*, bool> simple_seq_fit_impl<MutexFamily, VoidPointer>:: allocation_command (boost::interprocess::allocation_type command, std::size_t limit_size, std::size_t preferred_size,std::size_t &received_size, T *reuse_ptr) { std::pair<void*, bool> ret = priv_allocation_command (command, limit_size, preferred_size, received_size, static_cast<void*>(reuse_ptr), sizeof(T)); BOOST_ASSERT(0 == ((std::size_t)ret.first % detail::alignment_of<T>::value)); return std::pair<T *, bool>(static_cast<T*>(ret.first), ret.second); } template<class MutexFamily, class VoidPointer> inline std::pair<void*, bool> simple_seq_fit_impl<MutexFamily, VoidPointer>:: raw_allocation_command (boost::interprocess::allocation_type command, std::size_t limit_objects, std::size_t preferred_objects,std::size_t &received_objects, void *reuse_ptr, std::size_t sizeof_object) { if(!sizeof_object) return std::pair<void *, bool>(static_cast<void*>(0), false); if(command & boost::interprocess::try_shrink_in_place){ bool success = algo_impl_t::try_shrink ( this, reuse_ptr, limit_objects*sizeof_object , preferred_objects*sizeof_object, received_objects); received_objects /= sizeof_object; return std::pair<void *, bool> ((success ? reuse_ptr : 0), true); } return priv_allocation_command (command, limit_objects, preferred_objects, received_objects, reuse_ptr, sizeof_object); } template<class MutexFamily, class VoidPointer> inline std::pair<void*, bool> simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_allocation_command (boost::interprocess::allocation_type command, std::size_t limit_size, std::size_t preferred_size, std::size_t &received_size, void *reuse_ptr, std::size_t sizeof_object) { command &= ~boost::interprocess::expand_bwd; if(!command) return std::pair<void *, bool>(static_cast<void*>(0), false); std::pair<void*, bool> ret; std::size_t max_count = m_header.m_size/sizeof_object; if(limit_size > max_count || preferred_size > max_count){ ret.first = 0; return ret; } std::size_t l_size = limit_size*sizeof_object; std::size_t p_size = preferred_size*sizeof_object; std::size_t r_size; { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- ret = priv_allocate(command, l_size, p_size, r_size, reuse_ptr); } received_size = r_size/sizeof_object; return ret; } template<class MutexFamily, class VoidPointer> inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>:: size(const void *ptr) const { //We need no synchronization since this block is not going //to be modified //Obtain the real size of the block const block_ctrl *block = static_cast<const block_ctrl*>(priv_get_block(ptr)); return block->get_user_bytes(); } template<class MutexFamily, class VoidPointer> void* simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_expand_both_sides(boost::interprocess::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) { typedef std::pair<block_ctrl *, block_ctrl *> prev_block_t; block_ctrl *reuse = priv_get_block(reuse_ptr); received_size = 0; if(this->size(reuse_ptr) > min_size){ received_size = this->size(reuse_ptr); return reuse_ptr; } if(command & boost::interprocess::expand_fwd){ if(priv_expand(reuse_ptr, min_size, preferred_size, received_size)) return reuse_ptr; } else{ received_size = this->size(reuse_ptr); } if(command & boost::interprocess::expand_bwd){ std::size_t extra_forward = !received_size ? 0 : received_size + BlockCtrlBytes; prev_block_t prev_pair = priv_prev_block_if_free(reuse); block_ctrl *prev = prev_pair.second; if(!prev){ return 0; } std::size_t needs_backwards = detail::get_rounded_size(preferred_size - extra_forward, Alignment); if(!only_preferred_backwards){ max_value(detail::get_rounded_size(min_size - extra_forward, Alignment) ,min_value(prev->get_user_bytes(), needs_backwards)); } //Check if previous block has enough size if((prev->get_user_bytes()) >= needs_backwards){ //Now take all next space. This will succeed if(!priv_expand(reuse_ptr, received_size, received_size, received_size)){ BOOST_ASSERT(0); } //We need a minimum size to split the previous one if((prev->get_user_bytes() - needs_backwards) > 2*BlockCtrlBytes){ block_ctrl *new_block = reinterpret_cast<block_ctrl*> (reinterpret_cast<char*>(reuse) - needs_backwards - BlockCtrlBytes); new_block->m_next = 0; new_block->m_size = BlockCtrlUnits + (needs_backwards + extra_forward)/Alignment; prev->m_size = (prev->get_total_bytes() - needs_backwards)/Alignment - BlockCtrlUnits; received_size = needs_backwards + extra_forward; m_header.m_allocated += needs_backwards + BlockCtrlBytes; return priv_get_user_buffer(new_block); } else{ //Just merge the whole previous block block_ctrl *prev_2_block = prev_pair.first; //Update received size and allocation received_size = extra_forward + prev->get_user_bytes(); m_header.m_allocated += prev->get_total_bytes(); //Now unlink it from previous block prev_2_block->m_next = prev->m_next; prev->m_size = reuse->m_size + prev->m_size; prev->m_next = 0; priv_get_user_buffer(prev); } } } return 0; } template<class MutexFamily, class VoidPointer> inline void simple_seq_fit_impl<MutexFamily, VoidPointer>:: deallocate_many(typename simple_seq_fit_impl<MutexFamily, VoidPointer>::multiallocation_chain chain) { //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- while(!chain.empty()){ void *addr = chain.front(); chain.pop_front(); this->priv_deallocate(addr); } } template<class MutexFamily, class VoidPointer> inline std::size_t simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_get_total_units(std::size_t userbytes) { std::size_t s = detail::get_rounded_size(userbytes, Alignment)/Alignment; if(!s) ++s; return BlockCtrlUnits + s; } template<class MutexFamily, class VoidPointer> std::pair<void *, bool> simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_allocate(boost::interprocess::allocation_type command ,std::size_t limit_size ,std::size_t preferred_size ,std::size_t &received_size ,void *reuse_ptr) { if(command & boost::interprocess::shrink_in_place){ bool success = algo_impl_t::shrink(this, reuse_ptr, limit_size, preferred_size, received_size); return std::pair<void *, bool> ((success ? reuse_ptr : 0), true); } typedef std::pair<void *, bool> return_type; received_size = 0; if(limit_size > preferred_size) return return_type(static_cast<void*>(0), false); //Number of units to request (including block_ctrl header) std::size_t nunits = detail::get_rounded_size(preferred_size, Alignment)/Alignment + BlockCtrlUnits; //Get the root and the first memory block block_ctrl *prev = &m_header.m_root; block_ctrl *block = detail::get_pointer(prev->m_next); block_ctrl *root = &m_header.m_root; block_ctrl *biggest_block = 0; block_ctrl *prev_biggest_block = 0; std::size_t biggest_size = 0; //Expand in place //reuse_ptr, limit_size, preferred_size, received_size // if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){ void *ret = priv_expand_both_sides (command, limit_size, preferred_size, received_size, reuse_ptr, true); if(ret){ algo_impl_t::assert_alignment(ret); return return_type(ret, true); } } if(command & boost::interprocess::allocate_new){ received_size = 0; while(block != root){ //Update biggest block pointers if(block->m_size > biggest_size){ prev_biggest_block = prev; biggest_size = block->m_size; biggest_block = block; } algo_impl_t::assert_alignment(block); void *addr = this->priv_check_and_allocate(nunits, prev, block, received_size); if(addr){ algo_impl_t::assert_alignment(addr); return return_type(addr, false); } //Bad luck, let's check next block prev = block; block = detail::get_pointer(block->m_next); } //Bad luck finding preferred_size, now if we have any biggest_block //try with this block if(biggest_block){ std::size_t limit_units = detail::get_rounded_size(limit_size, Alignment)/Alignment + BlockCtrlUnits; if(biggest_block->m_size < limit_units) return return_type(static_cast<void*>(0), false); received_size = biggest_block->m_size*Alignment - BlockCtrlUnits; void *ret = this->priv_check_and_allocate (biggest_block->m_size, prev_biggest_block, biggest_block, received_size); BOOST_ASSERT(ret != 0); algo_impl_t::assert_alignment(ret); return return_type(ret, false); } } //Now try to expand both sides with min size if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){ return_type ret (priv_expand_both_sides (command, limit_size, preferred_size, received_size, reuse_ptr, false), true); algo_impl_t::assert_alignment(ret.first); return ret; } return return_type(static_cast<void*>(0), false); } template<class MutexFamily, class VoidPointer> inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_is_allocated_block (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *block) { return block->m_next == 0; } template<class MutexFamily, class VoidPointer> inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl * simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_next_block_if_free (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *ptr) { //Take the address where the next block should go block_ctrl *next_block = reinterpret_cast<block_ctrl*> (reinterpret_cast<char*>(ptr) + ptr->m_size*Alignment); //Check if the adjacent block is in the managed segment char *this_char_ptr = reinterpret_cast<char*>(this); char *next_char_ptr = reinterpret_cast<char*>(next_block); std::size_t distance = (next_char_ptr - this_char_ptr)/Alignment; if(distance >= (m_header.m_size/Alignment)){ //"next_block" does not exist so we can't expand "block" return 0; } if(!next_block->m_next) return 0; return next_block; } template<class MutexFamily, class VoidPointer> inline std::pair<typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl * ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *> simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_prev_block_if_free (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *ptr) { typedef std::pair<block_ctrl *, block_ctrl *> prev_pair_t; //Take the address where the previous block should go block_ctrl *root = &m_header.m_root; block_ctrl *prev_2_block = root; block_ctrl *prev_block = detail::get_pointer(root->m_next); while((reinterpret_cast<char*>(prev_block) + prev_block->m_size*Alignment) != reinterpret_cast<char*>(ptr) && prev_block != root){ prev_2_block = prev_block; prev_block = detail::get_pointer(prev_block->m_next); } if(prev_block == root || !prev_block->m_next) return prev_pair_t(static_cast<block_ctrl*>(0), static_cast<block_ctrl*>(0)); //Check if the previous block is in the managed segment char *this_char_ptr = reinterpret_cast<char*>(this); char *prev_char_ptr = reinterpret_cast<char*>(prev_block); std::size_t distance = (prev_char_ptr - this_char_ptr)/Alignment; if(distance >= (m_header.m_size/Alignment)){ //"previous_block" does not exist so we can't expand "block" return prev_pair_t(static_cast<block_ctrl*>(0), static_cast<block_ctrl*>(0)); } return prev_pair_t(prev_2_block, prev_block); } template<class MutexFamily, class VoidPointer> inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>:: priv_expand (void *ptr ,std::size_t min_size ,std::size_t preferred_size ,std::size_t &received_size) { //Obtain the real size of the block block_ctrl *block = reinterpret_cast<block_ctrl*>(priv_get_block(ptr)); std::size_t old_block_size = block->m_size; //All used blocks' next is marked with 0 so check it BOOST_ASSERT(block->m_next == 0); //Put this to a safe value received_size = old_block_size*Alignment - BlockCtrlBytes; //Now translate it to Alignment units min_size = detail::get_rounded_size(min_size, Alignment)/Alignment; preferred_size = detail::get_rounded_size(preferred_size, Alignment)/Alignment; //Some parameter checks if(min_size > preferred_size) return false; std::size_t data_size = old_block_size - BlockCtrlUnits; if(data_size >= min_size) return true; block_ctrl *next_block = priv_next_block_if_free(block); if(!next_block){ return false; } //Is "block" + "next_block" big enough? std::size_t merged_size = old_block_size + next_block->m_size; //Now we can expand this block further than before received_size = merged_size*Alignment - BlockCtrlBytes; if(merged_size < (min_size + BlockCtrlUnits)){ return false; } //We can fill expand. Merge both blocks, block->m_next = next_block->m_next; block->m_size = merged_size; //Find the previous free block of next_block block_ctrl *prev = &m_header.m_root; while(detail::get_pointer(prev->m_next) != next_block){ prev = detail::get_pointer(prev->m_next); } //Now insert merged block in the free list //This allows reusing allocation logic in this function m_header.m_allocated -= old_block_size*Alignment; prev->m_next = block; //Now use check and allocate to do the allocation logic preferred_size += BlockCtrlUnits; std::size_t nunits = preferred_size < merged_size ? preferred_size : merged_size; //This must success since nunits is less than merged_size! if(!this->priv_check_and_allocate (nunits, prev, block, received_size)){ //Something very ugly is happening here. This is a bug //or there is memory corruption BOOST_ASSERT(0); return false; } return true; } template<class MutexFamily, class VoidPointer> inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_check_and_allocate (std::size_t nunits ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl* prev ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl* block ,std::size_t &received_size) { std::size_t upper_nunits = nunits + BlockCtrlUnits; bool found = false; if (block->m_size > upper_nunits){ //This block is bigger than needed, split it in //two blocks, the first's size will be "units" //the second's size will be "block->m_size-units" std::size_t total_size = block->m_size; block->m_size = nunits; block_ctrl *new_block = reinterpret_cast<block_ctrl*> (reinterpret_cast<char*>(block) + Alignment*nunits); new_block->m_size = total_size - nunits; new_block->m_next = block->m_next; prev->m_next = new_block; found = true; } else if (block->m_size >= nunits){ //This block has exactly the right size with an extra //unusable extra bytes. prev->m_next = block->m_next; found = true; } if(found){ //We need block_ctrl for deallocation stuff, so //return memory user can overwrite m_header.m_allocated += block->m_size*Alignment; received_size = block->get_user_bytes(); //Mark the block as allocated block->m_next = 0; //Check alignment algo_impl_t::assert_alignment(block); return priv_get_user_buffer(block); } return 0; } template<class MutexFamily, class VoidPointer> void simple_seq_fit_impl<MutexFamily, VoidPointer>::deallocate(void* addr) { if(!addr) return; //----------------------- boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header); //----------------------- return this->priv_deallocate(addr); } template<class MutexFamily, class VoidPointer> void simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_deallocate(void* addr) { if(!addr) return; //Let's get free block list. List is always sorted //by memory address to allow block merging. //Pointer next always points to the first //(lower address) block block_ctrl * prev = &m_header.m_root; block_ctrl * pos = detail::get_pointer(m_header.m_root.m_next); block_ctrl * block = reinterpret_cast<block_ctrl*>(priv_get_block(addr)); //All used blocks' next is marked with 0 so check it BOOST_ASSERT(block->m_next == 0); //Check if alignment and block size are right algo_impl_t::assert_alignment(addr); std::size_t total_size = Alignment*block->m_size; BOOST_ASSERT(m_header.m_allocated >= total_size); //Update used memory count m_header.m_allocated -= total_size; //Let's find the previous and the next block of the block to deallocate //This ordering comparison must be done with original pointers //types since their mapping to raw pointers can be different //in each process while((detail::get_pointer(pos) != &m_header.m_root) && (block > pos)){ prev = pos; pos = detail::get_pointer(pos->m_next); } //Try to combine with upper block char *block_char_ptr = reinterpret_cast<char*>(detail::get_pointer(block)); if ((block_char_ptr + Alignment*block->m_size) == reinterpret_cast<char*>(detail::get_pointer(pos))){ block->m_size += pos->m_size; block->m_next = pos->m_next; } else{ block->m_next = pos; } //Try to combine with lower block if ((reinterpret_cast<char*>(detail::get_pointer(prev)) + Alignment*prev->m_size) == block_char_ptr){ prev->m_size += block->m_size; prev->m_next = block->m_next; } else{ prev->m_next = block; } } } //namespace detail { } //namespace interprocess { } //namespace boost { #include <boost/interprocess/detail/config_end.hpp> #endif //#ifndef BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP