////////////////////////////////////////////////////////////////////////////// | |
// | |
// (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 | |