1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 // See http://www.boost.org/libs/interprocess for documentation.
9 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP
12 #define BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 #include <boost/interprocess/detail/config_begin.hpp>
23 #include <boost/interprocess/detail/workaround.hpp>
25 #include <boost/intrusive/pointer_traits.hpp>
27 #include <boost/interprocess/interprocess_fwd.hpp>
28 #include <boost/interprocess/containers/allocation_type.hpp>
29 #include <boost/container/detail/multiallocation_chain.hpp>
30 #include <boost/interprocess/offset_ptr.hpp>
31 #include <boost/interprocess/sync/interprocess_mutex.hpp>
32 #include <boost/interprocess/exceptions.hpp>
33 #include <boost/interprocess/detail/utilities.hpp>
34 #include <boost/interprocess/detail/min_max.hpp>
35 #include <boost/interprocess/detail/type_traits.hpp>
36 #include <boost/interprocess/sync/scoped_lock.hpp>
37 #include <boost/intrusive/pointer_traits.hpp>
38 #include <boost/interprocess/mem_algo/detail/mem_algo_common.hpp>
39 #include <boost/move/detail/type_traits.hpp> //make_unsigned, alignment_of
40 #include <boost/intrusive/detail/minimal_pair_header.hpp>
42 #include <boost/assert.hpp>
45 //!Describes sequential fit algorithm used to allocate objects in shared memory.
46 //!This class is intended as a base class for single segment and multi-segment
50 namespace interprocess {
53 //!This class implements the simple sequential fit algorithm with a simply
54 //!linked list of free buffers.
55 //!This class is intended as a base class for single segment and multi-segment
57 template<class MutexFamily, class VoidPointer>
58 class simple_seq_fit_impl
61 simple_seq_fit_impl();
62 simple_seq_fit_impl(const simple_seq_fit_impl &);
63 simple_seq_fit_impl &operator=(const simple_seq_fit_impl &);
65 typedef typename boost::intrusive::
66 pointer_traits<VoidPointer>::template
67 rebind_pointer<char>::type char_ptr;
71 //!Shared interprocess_mutex family used for the rest of the Interprocess framework
72 typedef MutexFamily mutex_family;
73 //!Pointer type to be used with the rest of the Interprocess framework
74 typedef VoidPointer void_pointer;
75 typedef boost::container::container_detail::
76 basic_multiallocation_chain<VoidPointer> multiallocation_chain;
78 typedef typename boost::intrusive::pointer_traits<char_ptr>::difference_type difference_type;
79 typedef typename boost::container::container_detail::make_unsigned<difference_type>::type size_type;
84 friend class block_ctrl;
86 typedef typename boost::intrusive::
87 pointer_traits<VoidPointer>::template
88 rebind_pointer<block_ctrl>::type block_ctrl_ptr;
90 //!Block control structure
94 //!Offset pointer to the next block.
95 block_ctrl_ptr m_next;
96 //!This block's memory size (including block_ctrl
97 //!header) in BasicSize units
100 size_type get_user_bytes() const
101 { return this->m_size*Alignment - BlockCtrlBytes; }
103 size_type get_total_bytes() const
104 { return this->m_size*Alignment; }
107 //!Shared interprocess_mutex to protect memory allocate/deallocate
108 typedef typename MutexFamily::mutex_type interprocess_mutex;
110 //!This struct includes needed data and derives from
111 //!interprocess_mutex to allow EBO when using null interprocess_mutex
112 struct header_t : public interprocess_mutex
114 //!Pointer to the first free block
116 //!Allocated bytes for internal checking
117 size_type m_allocated;
118 //!The size of the memory segment
120 //!The extra size required by the segment
121 size_type m_extra_hdr_bytes;
124 friend class ipcdetail::memory_algorithm_common<simple_seq_fit_impl>;
126 typedef ipcdetail::memory_algorithm_common<simple_seq_fit_impl> algo_impl_t;
129 //!Constructor. "size" is the total size of the managed memory segment,
130 //!"extra_hdr_bytes" indicates the extra bytes beginning in the sizeof(simple_seq_fit_impl)
131 //!offset that the allocator should not use at all.
132 simple_seq_fit_impl (size_type size, size_type extra_hdr_bytes);
135 ~simple_seq_fit_impl();
137 //!Obtains the minimum size needed by the algorithm
138 static size_type get_min_size (size_type extra_hdr_bytes);
140 //Functions for single segment management
142 //!Allocates bytes, returns 0 if there is not more memory
143 void* allocate (size_type nbytes);
145 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED)
147 //!Multiple element allocation, same size
148 void allocate_many(size_type elem_bytes, size_type num_elements, multiallocation_chain &chain)
150 //-----------------------
151 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
152 //-----------------------
153 algo_impl_t::allocate_many(this, elem_bytes, num_elements, chain);
156 //!Multiple element allocation, different size
157 void allocate_many(const size_type *elem_sizes, size_type n_elements, size_type sizeof_element, multiallocation_chain &chain)
159 //-----------------------
160 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
161 //-----------------------
162 algo_impl_t::allocate_many(this, elem_sizes, n_elements, sizeof_element, chain);
165 //!Multiple element deallocation
166 void deallocate_many(multiallocation_chain &chain);
168 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED
170 //!Deallocates previously allocated bytes
171 void deallocate (void *addr);
173 //!Returns the size of the memory segment
174 size_type get_size() const;
176 //!Returns the number of free bytes of the memory segment
177 size_type get_free_memory() const;
179 //!Increases managed memory in extra_size bytes more
180 void grow(size_type extra_size);
182 //!Decreases managed memory as much as possible
183 void shrink_to_fit();
185 //!Returns true if all allocated memory has been deallocated
186 bool all_memory_deallocated();
188 //!Makes an internal sanity check and returns true if success
191 //!Initializes to zero all the memory that's not in use.
192 //!This function is normally used for security reasons.
193 void zero_free_memory();
196 T *allocation_command (boost::interprocess::allocation_type command, size_type limit_size,
197 size_type &prefer_in_recvd_out_size, T *&reuse);
199 void * raw_allocation_command (boost::interprocess::allocation_type command, size_type limit_size,
200 size_type &prefer_in_recvd_out_size, void *&reuse_ptr, size_type sizeof_object = 1);
202 //!Returns the size of the buffer previously allocated pointed by ptr
203 size_type size(const void *ptr) const;
205 //!Allocates aligned bytes, returns 0 if there is not more memory.
206 //!Alignment must be power of 2
207 void* allocate_aligned (size_type nbytes, size_type alignment);
211 //!Obtains the pointer returned to the user from the block control
212 static void *priv_get_user_buffer(const block_ctrl *block);
214 //!Obtains the block control structure of the user buffer
215 static block_ctrl *priv_get_block(const void *ptr);
217 //!Real allocation algorithm with min allocation option
218 void * priv_allocate(boost::interprocess::allocation_type command
220 ,size_type &prefer_in_recvd_out_size, void *&reuse_ptr);
222 void * priv_allocation_command(boost::interprocess::allocation_type command
224 ,size_type &prefer_in_recvd_out_size
226 ,size_type sizeof_object);
228 //!Returns the number of total units that a user buffer
229 //!of "userbytes" bytes really occupies (including header)
230 static size_type priv_get_total_units(size_type userbytes);
232 static size_type priv_first_block_offset(const void *this_ptr, size_type extra_hdr_bytes);
233 size_type priv_block_end_offset() const;
235 //!Returns next block if it's free.
236 //!Returns 0 if next block is not free.
237 block_ctrl *priv_next_block_if_free(block_ctrl *ptr);
239 //!Check if this block is free (not allocated)
240 bool priv_is_allocated_block(block_ctrl *ptr);
242 //!Returns previous block's if it's free.
243 //!Returns 0 if previous block is not free.
244 std::pair<block_ctrl*, block_ctrl*> priv_prev_block_if_free(block_ctrl *ptr);
246 //!Real expand function implementation
247 bool priv_expand(void *ptr, size_type min_size, size_type &prefer_in_recvd_out_size);
249 //!Real expand to both sides implementation
250 void* priv_expand_both_sides(boost::interprocess::allocation_type command
251 ,size_type min_size, size_type &prefer_in_recvd_out_size
253 ,bool only_preferred_backwards);
255 //!Real private aligned allocation function
256 //void* priv_allocate_aligned (size_type nbytes, size_type alignment);
258 //!Checks if block has enough memory and splits/unlinks the block
259 //!returning the address to the users
260 void* priv_check_and_allocate(size_type units
263 ,size_type &received_size);
264 //!Real deallocation algorithm
265 void priv_deallocate(void *addr);
267 //!Makes a new memory portion available for allocation
268 void priv_add_segment(void *addr, size_type size);
270 void priv_mark_new_allocated_block(block_ctrl *block);
273 static const size_type Alignment = ::boost::container::container_detail::alignment_of
274 < ::boost::container::container_detail::max_align_t>::value;
276 static const size_type BlockCtrlBytes = ipcdetail::ct_rounded_size<sizeof(block_ctrl), Alignment>::value;
277 static const size_type BlockCtrlUnits = BlockCtrlBytes/Alignment;
278 static const size_type MinBlockUnits = BlockCtrlUnits;
279 static const size_type MinBlockSize = MinBlockUnits*Alignment;
280 static const size_type AllocatedCtrlBytes = BlockCtrlBytes;
281 static const size_type AllocatedCtrlUnits = BlockCtrlUnits;
282 static const size_type UsableByPreviousChunk = 0;
285 static const size_type PayloadPerAllocation = BlockCtrlBytes;
288 template<class MutexFamily, class VoidPointer>
289 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
290 simple_seq_fit_impl<MutexFamily, VoidPointer>
291 ::priv_first_block_offset(const void *this_ptr, size_type extra_hdr_bytes)
293 //First align "this" pointer
294 size_type uint_this = (std::size_t)this_ptr;
295 size_type uint_aligned_this = uint_this/Alignment*Alignment;
296 size_type this_disalignment = (uint_this - uint_aligned_this);
297 size_type block1_off =
298 ipcdetail::get_rounded_size(sizeof(simple_seq_fit_impl) + extra_hdr_bytes + this_disalignment, Alignment)
300 algo_impl_t::assert_alignment(this_disalignment + block1_off);
304 template<class MutexFamily, class VoidPointer>
305 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
306 simple_seq_fit_impl<MutexFamily, VoidPointer>
307 ::priv_block_end_offset() const
309 //First align "this" pointer
310 size_type uint_this = (std::size_t)this;
311 size_type uint_aligned_this = uint_this/Alignment*Alignment;
312 size_type this_disalignment = (uint_this - uint_aligned_this);
314 ipcdetail::get_truncated_size(m_header.m_size + this_disalignment, Alignment)
316 algo_impl_t::assert_alignment(old_end + this_disalignment);
320 template<class MutexFamily, class VoidPointer>
321 inline simple_seq_fit_impl<MutexFamily, VoidPointer>::
322 simple_seq_fit_impl(size_type segment_size, size_type extra_hdr_bytes)
324 //Initialize sizes and counters
325 m_header.m_allocated = 0;
326 m_header.m_size = segment_size;
327 m_header.m_extra_hdr_bytes = extra_hdr_bytes;
329 //Initialize pointers
330 size_type block1_off = priv_first_block_offset(this, extra_hdr_bytes);
332 m_header.m_root.m_next = reinterpret_cast<block_ctrl*>
333 ((reinterpret_cast<char*>(this) + block1_off));
334 algo_impl_t::assert_alignment(ipcdetail::to_raw_pointer(m_header.m_root.m_next));
335 m_header.m_root.m_next->m_size = (segment_size - block1_off)/Alignment;
336 m_header.m_root.m_next->m_next = &m_header.m_root;
339 template<class MutexFamily, class VoidPointer>
340 inline simple_seq_fit_impl<MutexFamily, VoidPointer>::~simple_seq_fit_impl()
342 //There is a memory leak!
343 // BOOST_ASSERT(m_header.m_allocated == 0);
344 // BOOST_ASSERT(m_header.m_root.m_next->m_next == block_ctrl_ptr(&m_header.m_root));
347 template<class MutexFamily, class VoidPointer>
348 inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::grow(size_type extra_size)
350 //Old highest address block's end offset
351 size_type old_end = this->priv_block_end_offset();
353 //Update managed buffer's size
354 m_header.m_size += extra_size;
356 //We need at least MinBlockSize blocks to create a new block
357 if((m_header.m_size - old_end) < MinBlockSize){
361 //We'll create a new free block with extra_size bytes
363 block_ctrl *new_block = reinterpret_cast<block_ctrl*>
364 (reinterpret_cast<char*>(this) + old_end);
366 algo_impl_t::assert_alignment(new_block);
367 new_block->m_next = 0;
368 new_block->m_size = (m_header.m_size - old_end)/Alignment;
369 m_header.m_allocated += new_block->m_size*Alignment;
370 this->priv_deallocate(priv_get_user_buffer(new_block));
373 template<class MutexFamily, class VoidPointer>
374 void simple_seq_fit_impl<MutexFamily, VoidPointer>::shrink_to_fit()
376 //Get the root and the first memory block
377 block_ctrl *prev = &m_header.m_root;
378 block_ctrl *last = &m_header.m_root;
379 block_ctrl *block = ipcdetail::to_raw_pointer(last->m_next);
380 block_ctrl *root = &m_header.m_root;
383 if(block == root) return;
385 //Iterate through the free block list
386 while(block != root){
389 block = ipcdetail::to_raw_pointer(block->m_next);
392 char *last_free_end_address = reinterpret_cast<char*>(last) + last->m_size*Alignment;
393 if(last_free_end_address != (reinterpret_cast<char*>(this) + priv_block_end_offset())){
394 //there is an allocated block in the end of this block
395 //so no shrinking is possible
399 //Check if have only 1 big free block
400 void *unique_block = 0;
401 if(!m_header.m_allocated){
402 BOOST_ASSERT(prev == root);
403 size_type ignore_recvd = 0;
404 void *ignore_reuse = 0;
405 unique_block = priv_allocate(boost::interprocess::allocate_new, 0, ignore_recvd, ignore_reuse);
408 last = ipcdetail::to_raw_pointer(m_header.m_root.m_next);
409 BOOST_ASSERT(last_free_end_address == (reinterpret_cast<char*>(last) + last->m_size*Alignment));
411 size_type last_units = last->m_size;
413 size_type received_size;
414 void *addr = priv_check_and_allocate(last_units, prev, last, received_size);
417 BOOST_ASSERT(received_size == last_units*Alignment - AllocatedCtrlBytes);
420 m_header.m_size /= Alignment;
421 m_header.m_size -= last->m_size;
422 m_header.m_size *= Alignment;
423 m_header.m_allocated -= last->m_size*Alignment;
426 priv_deallocate(unique_block);
429 template<class MutexFamily, class VoidPointer>
430 inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::
431 priv_mark_new_allocated_block(block_ctrl *new_block)
433 new_block->m_next = 0;
436 template<class MutexFamily, class VoidPointer>
438 typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *
439 simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_get_block(const void *ptr)
441 return const_cast<block_ctrl*>(reinterpret_cast<const block_ctrl*>
442 (reinterpret_cast<const char*>(ptr) - AllocatedCtrlBytes));
445 template<class MutexFamily, class VoidPointer>
447 void *simple_seq_fit_impl<MutexFamily, VoidPointer>::
448 priv_get_user_buffer(const typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *block)
450 return const_cast<char*>(reinterpret_cast<const char*>(block) + AllocatedCtrlBytes);
453 template<class MutexFamily, class VoidPointer>
454 inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_add_segment(void *addr, size_type segment_size)
456 algo_impl_t::assert_alignment(addr);
458 BOOST_ASSERT(!(segment_size < MinBlockSize));
459 if(segment_size < MinBlockSize)
461 //Construct big block using the new segment
462 block_ctrl *new_block = static_cast<block_ctrl *>(addr);
463 new_block->m_size = segment_size/Alignment;
464 new_block->m_next = 0;
465 //Simulate this block was previously allocated
466 m_header.m_allocated += new_block->m_size*Alignment;
467 //Return block and insert it in the free block list
468 this->priv_deallocate(priv_get_user_buffer(new_block));
471 template<class MutexFamily, class VoidPointer>
472 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
473 simple_seq_fit_impl<MutexFamily, VoidPointer>::get_size() const
474 { return m_header.m_size; }
476 template<class MutexFamily, class VoidPointer>
477 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
478 simple_seq_fit_impl<MutexFamily, VoidPointer>::get_free_memory() const
480 return m_header.m_size - m_header.m_allocated -
481 algo_impl_t::multiple_of_units(sizeof(*this) + m_header.m_extra_hdr_bytes);
484 template<class MutexFamily, class VoidPointer>
485 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
486 simple_seq_fit_impl<MutexFamily, VoidPointer>::
487 get_min_size (size_type extra_hdr_bytes)
489 return ipcdetail::get_rounded_size((size_type)sizeof(simple_seq_fit_impl),Alignment) +
490 ipcdetail::get_rounded_size(extra_hdr_bytes,Alignment)
494 template<class MutexFamily, class VoidPointer>
495 inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>::
496 all_memory_deallocated()
498 //-----------------------
499 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
500 //-----------------------
501 return m_header.m_allocated == 0 &&
502 ipcdetail::to_raw_pointer(m_header.m_root.m_next->m_next) == &m_header.m_root;
505 template<class MutexFamily, class VoidPointer>
506 inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::zero_free_memory()
508 //-----------------------
509 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
510 //-----------------------
511 block_ctrl *block = ipcdetail::to_raw_pointer(m_header.m_root.m_next);
513 //Iterate through all free portions
515 //Just clear user the memory part reserved for the user
516 std::memset( priv_get_user_buffer(block)
518 , block->get_user_bytes());
519 block = ipcdetail::to_raw_pointer(block->m_next);
521 while(block != &m_header.m_root);
524 template<class MutexFamily, class VoidPointer>
525 inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>::
528 //-----------------------
529 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
530 //-----------------------
531 block_ctrl *block = ipcdetail::to_raw_pointer(m_header.m_root.m_next);
533 size_type free_memory = 0;
535 //Iterate through all blocks obtaining their size
536 while(block != &m_header.m_root){
537 algo_impl_t::assert_alignment(block);
538 if(!algo_impl_t::check_alignment(block))
540 //Free blocks's next must be always valid
541 block_ctrl *next = ipcdetail::to_raw_pointer(block->m_next);
545 free_memory += block->m_size*Alignment;
549 //Check allocated bytes are less than size
550 if(m_header.m_allocated > m_header.m_size){
554 //Check free bytes are less than size
555 if(free_memory > m_header.m_size){
561 template<class MutexFamily, class VoidPointer>
562 inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>::
563 allocate(size_type nbytes)
565 //-----------------------
566 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
567 //-----------------------
568 size_type ignore_recvd = nbytes;
569 void *ignore_reuse = 0;
570 return priv_allocate(boost::interprocess::allocate_new, nbytes, ignore_recvd, ignore_reuse);
573 template<class MutexFamily, class VoidPointer>
574 inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>::
575 allocate_aligned(size_type nbytes, size_type alignment)
577 //-----------------------
578 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
579 //-----------------------
581 allocate_aligned(this, nbytes, alignment);
584 template<class MutexFamily, class VoidPointer>
586 inline T* simple_seq_fit_impl<MutexFamily, VoidPointer>::
587 allocation_command (boost::interprocess::allocation_type command, size_type limit_size,
588 size_type &prefer_in_recvd_out_size, T *&reuse_ptr)
590 void *raw_reuse = reuse_ptr;
591 void * const ret = priv_allocation_command
592 (command, limit_size, prefer_in_recvd_out_size, raw_reuse, sizeof(T));
593 BOOST_ASSERT(0 == ((std::size_t)ret % ::boost::container::container_detail::alignment_of<T>::value));
594 reuse_ptr = static_cast<T*>(raw_reuse);
595 return static_cast<T*>(ret);
598 template<class MutexFamily, class VoidPointer>
599 inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>::
600 raw_allocation_command (boost::interprocess::allocation_type command, size_type limit_objects,
601 size_type &prefer_in_recvd_out_size, void *&reuse_ptr, size_type sizeof_object)
603 size_type const preferred_objects = prefer_in_recvd_out_size;
605 return reuse_ptr = 0, static_cast<void*>(0);
607 if(command & boost::interprocess::try_shrink_in_place){
608 if(!reuse_ptr) return static_cast<void*>(0);
609 prefer_in_recvd_out_size = preferred_objects*sizeof_object;
610 bool success = algo_impl_t::try_shrink
611 ( this, reuse_ptr, limit_objects*sizeof_object, prefer_in_recvd_out_size);
612 prefer_in_recvd_out_size /= sizeof_object;
613 return success ? reuse_ptr : 0;
616 return priv_allocation_command
617 (command, limit_objects, prefer_in_recvd_out_size, reuse_ptr, sizeof_object);
621 template<class MutexFamily, class VoidPointer>
622 inline void* simple_seq_fit_impl<MutexFamily, VoidPointer>::
623 priv_allocation_command (boost::interprocess::allocation_type command, size_type limit_size,
624 size_type &prefer_in_recvd_out_size, void *&reuse_ptr, size_type sizeof_object)
626 size_type const preferred_size = prefer_in_recvd_out_size;
627 command &= ~boost::interprocess::expand_bwd;
629 return reuse_ptr = 0, static_cast<void*>(0);
632 size_type max_count = m_header.m_size/sizeof_object;
633 if(limit_size > max_count || preferred_size > max_count){
634 return reuse_ptr = 0, static_cast<void*>(0);
636 size_type l_size = limit_size*sizeof_object;
637 size_type r_size = preferred_size*sizeof_object;
640 //-----------------------
641 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
642 //-----------------------
643 ret = priv_allocate(command, l_size, r_size, reuse_ptr);
645 prefer_in_recvd_out_size = r_size/sizeof_object;
649 template<class MutexFamily, class VoidPointer>
650 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
651 simple_seq_fit_impl<MutexFamily, VoidPointer>::size(const void *ptr) const
653 //We need no synchronization since this block is not going
655 //Obtain the real size of the block
656 const block_ctrl *block = static_cast<const block_ctrl*>(priv_get_block(ptr));
657 return block->get_user_bytes();
660 template<class MutexFamily, class VoidPointer>
661 void* simple_seq_fit_impl<MutexFamily, VoidPointer>::
662 priv_expand_both_sides(boost::interprocess::allocation_type command
664 ,size_type &prefer_in_recvd_out_size
666 ,bool only_preferred_backwards)
668 size_type const preferred_size = prefer_in_recvd_out_size;
669 typedef std::pair<block_ctrl *, block_ctrl *> prev_block_t;
670 block_ctrl *reuse = priv_get_block(reuse_ptr);
671 prefer_in_recvd_out_size = 0;
673 if(this->size(reuse_ptr) > min_size){
674 prefer_in_recvd_out_size = this->size(reuse_ptr);
678 if(command & boost::interprocess::expand_fwd){
679 if(priv_expand(reuse_ptr, min_size, prefer_in_recvd_out_size = preferred_size))
683 prefer_in_recvd_out_size = this->size(reuse_ptr);
685 if(command & boost::interprocess::expand_bwd){
686 size_type extra_forward = !prefer_in_recvd_out_size ? 0 : prefer_in_recvd_out_size + BlockCtrlBytes;
687 prev_block_t prev_pair = priv_prev_block_if_free(reuse);
688 block_ctrl *prev = prev_pair.second;
693 size_type needs_backwards =
694 ipcdetail::get_rounded_size(preferred_size - extra_forward, Alignment);
696 if(!only_preferred_backwards){
697 max_value(ipcdetail::get_rounded_size(min_size - extra_forward, Alignment)
698 ,min_value(prev->get_user_bytes(), needs_backwards));
701 //Check if previous block has enough size
702 if((prev->get_user_bytes()) >= needs_backwards){
703 //Now take all next space. This will succeed
704 if(!priv_expand(reuse_ptr, prefer_in_recvd_out_size, prefer_in_recvd_out_size)){
708 //We need a minimum size to split the previous one
709 if((prev->get_user_bytes() - needs_backwards) > 2*BlockCtrlBytes){
710 block_ctrl *new_block = reinterpret_cast<block_ctrl*>
711 (reinterpret_cast<char*>(reuse) - needs_backwards - BlockCtrlBytes);
713 new_block->m_next = 0;
715 BlockCtrlUnits + (needs_backwards + extra_forward)/Alignment;
717 (prev->get_total_bytes() - needs_backwards)/Alignment - BlockCtrlUnits;
718 prefer_in_recvd_out_size = needs_backwards + extra_forward;
719 m_header.m_allocated += needs_backwards + BlockCtrlBytes;
720 return priv_get_user_buffer(new_block);
723 //Just merge the whole previous block
724 block_ctrl *prev_2_block = prev_pair.first;
725 //Update received size and allocation
726 prefer_in_recvd_out_size = extra_forward + prev->get_user_bytes();
727 m_header.m_allocated += prev->get_total_bytes();
728 //Now unlink it from previous block
729 prev_2_block->m_next = prev->m_next;
730 prev->m_size = reuse->m_size + prev->m_size;
732 priv_get_user_buffer(prev);
739 template<class MutexFamily, class VoidPointer>
740 inline void simple_seq_fit_impl<MutexFamily, VoidPointer>::
741 deallocate_many(typename simple_seq_fit_impl<MutexFamily, VoidPointer>::multiallocation_chain &chain)
743 //-----------------------
744 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
745 //-----------------------
746 while(!chain.empty()){
747 this->priv_deallocate(to_raw_pointer(chain.pop_front()));
751 template<class MutexFamily, class VoidPointer>
752 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::size_type
753 simple_seq_fit_impl<MutexFamily, VoidPointer>::
754 priv_get_total_units(size_type userbytes)
756 size_type s = ipcdetail::get_rounded_size(userbytes, Alignment)/Alignment;
758 return BlockCtrlUnits + s;
761 template<class MutexFamily, class VoidPointer>
762 void * simple_seq_fit_impl<MutexFamily, VoidPointer>::
763 priv_allocate(boost::interprocess::allocation_type command
764 ,size_type limit_size, size_type &prefer_in_recvd_out_size, void *&reuse_ptr)
766 size_type const preferred_size = prefer_in_recvd_out_size;
767 if(command & boost::interprocess::shrink_in_place){
768 if(!reuse_ptr) return static_cast<void*>(0);
769 bool success = algo_impl_t::shrink(this, reuse_ptr, limit_size, prefer_in_recvd_out_size);
770 return success ? reuse_ptr : 0;
772 prefer_in_recvd_out_size = 0;
774 if(limit_size > preferred_size){
775 return reuse_ptr = 0, static_cast<void*>(0);
778 //Number of units to request (including block_ctrl header)
779 size_type nunits = ipcdetail::get_rounded_size(preferred_size, Alignment)/Alignment + BlockCtrlUnits;
781 //Get the root and the first memory block
782 block_ctrl *prev = &m_header.m_root;
783 block_ctrl *block = ipcdetail::to_raw_pointer(prev->m_next);
784 block_ctrl *root = &m_header.m_root;
785 block_ctrl *biggest_block = 0;
786 block_ctrl *prev_biggest_block = 0;
787 size_type biggest_size = 0;
790 if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){
791 void *ret = priv_expand_both_sides(command, limit_size, prefer_in_recvd_out_size = preferred_size, reuse_ptr, true);
793 algo_impl_t::assert_alignment(ret);
798 if(command & boost::interprocess::allocate_new){
799 prefer_in_recvd_out_size = 0;
800 while(block != root){
801 //Update biggest block pointers
802 if(block->m_size > biggest_size){
803 prev_biggest_block = prev;
804 biggest_size = block->m_size;
805 biggest_block = block;
807 algo_impl_t::assert_alignment(block);
808 void *addr = this->priv_check_and_allocate(nunits, prev, block, prefer_in_recvd_out_size);
810 algo_impl_t::assert_alignment(addr);
811 return reuse_ptr = 0, addr;
813 //Bad luck, let's check next block
815 block = ipcdetail::to_raw_pointer(block->m_next);
818 //Bad luck finding preferred_size, now if we have any biggest_block
819 //try with this block
821 size_type limit_units = ipcdetail::get_rounded_size(limit_size, Alignment)/Alignment + BlockCtrlUnits;
822 if(biggest_block->m_size < limit_units){
823 return reuse_ptr = 0, static_cast<void*>(0);
825 void *ret = this->priv_check_and_allocate
826 (biggest_block->m_size, prev_biggest_block, biggest_block, prefer_in_recvd_out_size = biggest_block->m_size*Alignment - BlockCtrlUnits);
827 BOOST_ASSERT(ret != 0);
828 algo_impl_t::assert_alignment(ret);
829 return reuse_ptr = 0, ret;
832 //Now try to expand both sides with min size
833 if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){
834 void *ret = priv_expand_both_sides (command, limit_size, prefer_in_recvd_out_size = preferred_size, reuse_ptr, false);
835 algo_impl_t::assert_alignment(ret);
838 return reuse_ptr = 0, static_cast<void*>(0);
841 template<class MutexFamily, class VoidPointer> inline
842 bool simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_is_allocated_block
843 (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *block)
844 { return block->m_next == 0; }
846 template<class MutexFamily, class VoidPointer>
847 inline typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *
848 simple_seq_fit_impl<MutexFamily, VoidPointer>::
849 priv_next_block_if_free
850 (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *ptr)
852 //Take the address where the next block should go
853 block_ctrl *next_block = reinterpret_cast<block_ctrl*>
854 (reinterpret_cast<char*>(ptr) + ptr->m_size*Alignment);
856 //Check if the adjacent block is in the managed segment
857 char *this_char_ptr = reinterpret_cast<char*>(this);
858 char *next_char_ptr = reinterpret_cast<char*>(next_block);
859 size_type distance = (size_type)(next_char_ptr - this_char_ptr)/Alignment;
861 if(distance >= (m_header.m_size/Alignment)){
862 //"next_block" does not exist so we can't expand "block"
866 if(!next_block->m_next)
872 template<class MutexFamily, class VoidPointer>
874 std::pair<typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *
875 ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *>
876 simple_seq_fit_impl<MutexFamily, VoidPointer>::
877 priv_prev_block_if_free
878 (typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl *ptr)
880 typedef std::pair<block_ctrl *, block_ctrl *> prev_pair_t;
881 //Take the address where the previous block should go
882 block_ctrl *root = &m_header.m_root;
883 block_ctrl *prev_2_block = root;
884 block_ctrl *prev_block = ipcdetail::to_raw_pointer(root->m_next);
886 while((reinterpret_cast<char*>(prev_block) + prev_block->m_size*Alignment)
887 != reinterpret_cast<char*>(ptr)
888 && prev_block != root){
889 prev_2_block = prev_block;
890 prev_block = ipcdetail::to_raw_pointer(prev_block->m_next);
893 if(prev_block == root || !prev_block->m_next)
894 return prev_pair_t(static_cast<block_ctrl*>(0), static_cast<block_ctrl*>(0));
896 //Check if the previous block is in the managed segment
897 char *this_char_ptr = reinterpret_cast<char*>(this);
898 char *prev_char_ptr = reinterpret_cast<char*>(prev_block);
899 size_type distance = (size_type)(prev_char_ptr - this_char_ptr)/Alignment;
901 if(distance >= (m_header.m_size/Alignment)){
902 //"previous_block" does not exist so we can't expand "block"
903 return prev_pair_t(static_cast<block_ctrl*>(0), static_cast<block_ctrl*>(0));
905 return prev_pair_t(prev_2_block, prev_block);
909 template<class MutexFamily, class VoidPointer>
910 inline bool simple_seq_fit_impl<MutexFamily, VoidPointer>::
911 priv_expand (void *ptr, size_type min_size, size_type &received_size)
913 size_type preferred_size = received_size;
914 //Obtain the real size of the block
915 block_ctrl *block = reinterpret_cast<block_ctrl*>(priv_get_block(ptr));
916 size_type old_block_size = block->m_size;
918 //All used blocks' next is marked with 0 so check it
919 BOOST_ASSERT(block->m_next == 0);
921 //Put this to a safe value
922 received_size = old_block_size*Alignment - BlockCtrlBytes;
924 //Now translate it to Alignment units
925 min_size = ipcdetail::get_rounded_size(min_size, Alignment)/Alignment;
926 preferred_size = ipcdetail::get_rounded_size(preferred_size, Alignment)/Alignment;
928 //Some parameter checks
929 if(min_size > preferred_size)
932 size_type data_size = old_block_size - BlockCtrlUnits;
934 if(data_size >= min_size)
937 block_ctrl *next_block = priv_next_block_if_free(block);
942 //Is "block" + "next_block" big enough?
943 size_type merged_size = old_block_size + next_block->m_size;
945 //Now we can expand this block further than before
946 received_size = merged_size*Alignment - BlockCtrlBytes;
948 if(merged_size < (min_size + BlockCtrlUnits)){
952 //We can fill expand. Merge both blocks,
953 block->m_next = next_block->m_next;
954 block->m_size = merged_size;
956 //Find the previous free block of next_block
957 block_ctrl *prev = &m_header.m_root;
958 while(ipcdetail::to_raw_pointer(prev->m_next) != next_block){
959 prev = ipcdetail::to_raw_pointer(prev->m_next);
962 //Now insert merged block in the free list
963 //This allows reusing allocation logic in this function
964 m_header.m_allocated -= old_block_size*Alignment;
965 prev->m_next = block;
967 //Now use check and allocate to do the allocation logic
968 preferred_size += BlockCtrlUnits;
969 size_type nunits = preferred_size < merged_size ? preferred_size : merged_size;
971 //This must success since nunits is less than merged_size!
972 if(!this->priv_check_and_allocate (nunits, prev, block, received_size)){
973 //Something very ugly is happening here. This is a bug
974 //or there is memory corruption
981 template<class MutexFamily, class VoidPointer> inline
982 void* simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_check_and_allocate
984 ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl* prev
985 ,typename simple_seq_fit_impl<MutexFamily, VoidPointer>::block_ctrl* block
986 ,size_type &received_size)
988 size_type upper_nunits = nunits + BlockCtrlUnits;
991 if (block->m_size > upper_nunits){
992 //This block is bigger than needed, split it in
993 //two blocks, the first's size will be "units"
994 //the second's size will be "block->m_size-units"
995 size_type total_size = block->m_size;
996 block->m_size = nunits;
998 block_ctrl *new_block = reinterpret_cast<block_ctrl*>
999 (reinterpret_cast<char*>(block) + Alignment*nunits);
1000 new_block->m_size = total_size - nunits;
1001 new_block->m_next = block->m_next;
1002 prev->m_next = new_block;
1005 else if (block->m_size >= nunits){
1006 //This block has exactly the right size with an extra
1007 //unusable extra bytes.
1008 prev->m_next = block->m_next;
1013 //We need block_ctrl for deallocation stuff, so
1014 //return memory user can overwrite
1015 m_header.m_allocated += block->m_size*Alignment;
1016 received_size = block->get_user_bytes();
1017 //Mark the block as allocated
1020 algo_impl_t::assert_alignment(block);
1021 return priv_get_user_buffer(block);
1026 template<class MutexFamily, class VoidPointer>
1027 void simple_seq_fit_impl<MutexFamily, VoidPointer>::deallocate(void* addr)
1030 //-----------------------
1031 boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
1032 //-----------------------
1033 return this->priv_deallocate(addr);
1036 template<class MutexFamily, class VoidPointer>
1037 void simple_seq_fit_impl<MutexFamily, VoidPointer>::priv_deallocate(void* addr)
1041 //Let's get free block list. List is always sorted
1042 //by memory address to allow block merging.
1043 //Pointer next always points to the first
1044 //(lower address) block
1045 block_ctrl * prev = &m_header.m_root;
1046 block_ctrl * pos = ipcdetail::to_raw_pointer(m_header.m_root.m_next);
1047 block_ctrl * block = reinterpret_cast<block_ctrl*>(priv_get_block(addr));
1049 //All used blocks' next is marked with 0 so check it
1050 BOOST_ASSERT(block->m_next == 0);
1052 //Check if alignment and block size are right
1053 algo_impl_t::assert_alignment(addr);
1055 size_type total_size = Alignment*block->m_size;
1056 BOOST_ASSERT(m_header.m_allocated >= total_size);
1058 //Update used memory count
1059 m_header.m_allocated -= total_size;
1061 //Let's find the previous and the next block of the block to deallocate
1062 //This ordering comparison must be done with original pointers
1063 //types since their mapping to raw pointers can be different
1065 while((ipcdetail::to_raw_pointer(pos) != &m_header.m_root) && (block > pos)){
1067 pos = ipcdetail::to_raw_pointer(pos->m_next);
1070 //Try to combine with upper block
1071 char *block_char_ptr = reinterpret_cast<char*>(ipcdetail::to_raw_pointer(block));
1073 if ((block_char_ptr + Alignment*block->m_size) ==
1074 reinterpret_cast<char*>(ipcdetail::to_raw_pointer(pos))){
1075 block->m_size += pos->m_size;
1076 block->m_next = pos->m_next;
1079 block->m_next = pos;
1082 //Try to combine with lower block
1083 if ((reinterpret_cast<char*>(ipcdetail::to_raw_pointer(prev))
1084 + Alignment*prev->m_size) ==
1088 prev->m_size += block->m_size;
1089 prev->m_next = block->m_next;
1092 prev->m_next = block;
1096 } //namespace ipcdetail {
1098 } //namespace interprocess {
1100 } //namespace boost {
1102 #include <boost/interprocess/detail/config_end.hpp>
1104 #endif //#ifndef BOOST_INTERPROCESS_MEM_ALGO_DETAIL_SIMPLE_SEQ_FIT_IMPL_HPP