1 // MT-optimized allocator -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /** @file ext/mt_allocator.h
27 * This file is a GNU extension to the Standard C++ Library.
30 #ifndef _MT_ALLOCATOR_H
31 #define _MT_ALLOCATOR_H 1
35 #include <bits/functexcept.h>
36 #include <ext/atomicity.h>
37 #include <bits/move.h>
39 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx
)
44 typedef void (*__destroy_handler
)(void*);
46 /// Base class for pool object.
49 // Using short int as type for the binmap implies we are never
50 // caching blocks larger than 32768 with this allocator.
51 typedef unsigned short int _Binmap_type
;
53 // Variables used to configure the behavior of the allocator,
54 // assigned and explained in detail below.
57 // Compile time constants for the default _Tune values.
58 enum { _S_align
= 8 };
59 enum { _S_max_bytes
= 128 };
60 enum { _S_min_bin
= 8 };
61 enum { _S_chunk_size
= 4096 - 4 * sizeof(void*) };
62 enum { _S_max_threads
= 4096 };
63 enum { _S_freelist_headroom
= 10 };
66 // NB: In any case must be >= sizeof(_Block_record), that
67 // is 4 on 32 bit machines and 8 on 64 bit machines.
70 // Allocation requests (after round-up to power of 2) below
71 // this value will be handled by the allocator. A raw new/
72 // call will be used for requests larger than this value.
73 // NB: Must be much smaller than _M_chunk_size and in any
77 // Size in bytes of the smallest bin.
78 // NB: Must be a power of 2 and >= _M_align (and of course
79 // much smaller than _M_max_bytes).
82 // In order to avoid fragmenting and minimize the number of
83 // new() calls we always request new memory using this
84 // value. Based on previous discussions on the libstdc++
85 // mailing list we have chosen the value below.
86 // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
87 // NB: At least one order of magnitude > _M_max_bytes.
90 // The maximum number of supported threads. For
91 // single-threaded operation, use one. Maximum values will
92 // vary depending on details of the underlying system. (For
93 // instance, Linux 2.4.18 reports 4070 in
94 // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
96 size_t _M_max_threads
;
98 // Each time a deallocation occurs in a threaded application
99 // we make sure that there are no more than
100 // _M_freelist_headroom % of used memory on the freelist. If
101 // the number of additional records is more than
102 // _M_freelist_headroom % of the freelist, we move these
103 // records back to the global pool.
104 size_t _M_freelist_headroom
;
106 // Set to true forces all allocations to use new().
111 : _M_align(_S_align
), _M_max_bytes(_S_max_bytes
), _M_min_bin(_S_min_bin
),
112 _M_chunk_size(_S_chunk_size
), _M_max_threads(_S_max_threads
),
113 _M_freelist_headroom(_S_freelist_headroom
),
114 _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
118 _Tune(size_t __align
, size_t __maxb
, size_t __minbin
, size_t __chunk
,
119 size_t __maxthreads
, size_t __headroom
, bool __force
)
120 : _M_align(__align
), _M_max_bytes(__maxb
), _M_min_bin(__minbin
),
121 _M_chunk_size(__chunk
), _M_max_threads(__maxthreads
),
122 _M_freelist_headroom(__headroom
), _M_force_new(__force
)
126 struct _Block_address
129 _Block_address
* _M_next
;
133 _M_get_options() const
134 { return _M_options
; }
137 _M_set_options(_Tune __t
)
144 _M_check_threshold(size_t __bytes
)
145 { return __bytes
> _M_options
._M_max_bytes
|| _M_options
._M_force_new
; }
148 _M_get_binmap(size_t __bytes
)
149 { return _M_binmap
[__bytes
]; }
153 { return _M_options
._M_align
; }
157 : _M_options(_Tune()), _M_binmap(NULL
), _M_init(false) { }
160 __pool_base(const _Tune
& __options
)
161 : _M_options(__options
), _M_binmap(NULL
), _M_init(false) { }
165 __pool_base(const __pool_base
&);
168 operator=(const __pool_base
&);
171 // Configuration options.
174 _Binmap_type
* _M_binmap
;
176 // Configuration of the pool object via _M_options can happen
177 // after construction but before initialization. After
178 // initialization is complete, this variable is set to true.
184 * @brief Data describing the underlying memory pool, parameterized on
187 template<bool _Thread
>
190 /// Specialization for single thread.
192 class __pool
<false> : public __pool_base
197 // Points to the block_record of the next free block.
198 _Block_record
* _M_next
;
203 // An "array" of pointers to the first free block.
204 _Block_record
** _M_first
;
206 // A list of the initial addresses of all allocated blocks.
207 _Block_address
* _M_address
;
213 if (__builtin_expect(_M_init
== false, false))
218 _M_destroy() throw();
221 _M_reserve_block(size_t __bytes
, const size_t __thread_id
);
224 _M_reclaim_block(char* __p
, size_t __bytes
) throw ();
227 _M_get_thread_id() { return 0; }
230 _M_get_bin(size_t __which
)
231 { return _M_bin
[__which
]; }
234 _M_adjust_freelist(const _Bin_record
&, _Block_record
*, size_t)
238 : _M_bin(NULL
), _M_bin_size(1) { }
240 explicit __pool(const __pool_base::_Tune
& __tune
)
241 : __pool_base(__tune
), _M_bin(NULL
), _M_bin_size(1) { }
244 // An "array" of bin_records each of which represents a specific
245 // power of 2 size. Memory to this "array" is allocated in
249 // Actual value calculated in _M_initialize().
257 /// Specialization for thread enabled, via gthreads.h.
259 class __pool
<true> : public __pool_base
262 // Each requesting thread is assigned an id ranging from 1 to
263 // _S_max_threads. Thread id 0 is used as a global memory pool.
264 // In order to get constant performance on the thread assignment
265 // routine, we keep a list of free ids. When a thread first
266 // requests memory we remove the first record in this list and
267 // stores the address in a __gthread_key. When initializing the
268 // __gthread_key we specify a destructor. When this destructor
269 // (i.e. the thread dies) is called, we return the thread id to
270 // the front of this list.
271 struct _Thread_record
273 // Points to next free thread id record. NULL if last record in list.
274 _Thread_record
* _M_next
;
276 // Thread id ranging from 1 to _S_max_threads.
282 // Points to the block_record of the next free block.
283 _Block_record
* _M_next
;
285 // The thread id of the thread which has requested this block.
291 // An "array" of pointers to the first free block for each
292 // thread id. Memory to this "array" is allocated in
293 // _S_initialize() for _S_max_threads + global pool 0.
294 _Block_record
** _M_first
;
296 // A list of the initial addresses of all allocated blocks.
297 _Block_address
* _M_address
;
299 // An "array" of counters used to keep track of the amount of
300 // blocks that are on the freelist/used for each thread id.
301 // - Note that the second part of the allocated _M_used "array"
302 // actually hosts (atomic) counters of reclaimed blocks: in
303 // _M_reserve_block and in _M_reclaim_block those numbers are
304 // subtracted from the first ones to obtain the actual size
305 // of the "working set" of the given thread.
306 // - Memory to these "arrays" is allocated in _S_initialize()
307 // for _S_max_threads + global pool 0.
311 // Each bin has its own mutex which is used to ensure data
312 // integrity while changing "ownership" on a block. The mutex
313 // is initialized in _S_initialize().
314 __gthread_mutex_t
* _M_mutex
;
317 // XXX GLIBCXX_ABI Deprecated
319 _M_initialize(__destroy_handler
);
324 if (__builtin_expect(_M_init
== false, false))
329 _M_destroy() throw();
332 _M_reserve_block(size_t __bytes
, const size_t __thread_id
);
335 _M_reclaim_block(char* __p
, size_t __bytes
) throw ();
338 _M_get_bin(size_t __which
)
339 { return _M_bin
[__which
]; }
342 _M_adjust_freelist(const _Bin_record
& __bin
, _Block_record
* __block
,
345 if (__gthread_active_p())
347 __block
->_M_thread_id
= __thread_id
;
348 --__bin
._M_free
[__thread_id
];
349 ++__bin
._M_used
[__thread_id
];
353 // XXX GLIBCXX_ABI Deprecated
355 _M_destroy_thread_key(void*) throw ();
361 : _M_bin(NULL
), _M_bin_size(1), _M_thread_freelist(NULL
)
364 explicit __pool(const __pool_base::_Tune
& __tune
)
365 : __pool_base(__tune
), _M_bin(NULL
), _M_bin_size(1),
366 _M_thread_freelist(NULL
)
370 // An "array" of bin_records each of which represents a specific
371 // power of 2 size. Memory to this "array" is allocated in
375 // Actual value calculated in _M_initialize().
378 _Thread_record
* _M_thread_freelist
;
379 void* _M_thread_freelist_initial
;
386 template<template <bool> class _PoolTp
, bool _Thread
>
389 typedef _PoolTp
<_Thread
> pool_type
;
394 static pool_type _S_pool
;
399 template<template <bool> class _PoolTp
, bool _Thread
>
400 struct __common_pool_base
;
402 template<template <bool> class _PoolTp
>
403 struct __common_pool_base
<_PoolTp
, false>
404 : public __common_pool
<_PoolTp
, false>
406 using __common_pool
<_PoolTp
, false>::_S_get_pool
;
412 if (__builtin_expect(__init
== false, false))
414 _S_get_pool()._M_initialize_once();
421 template<template <bool> class _PoolTp
>
422 struct __common_pool_base
<_PoolTp
, true>
423 : public __common_pool
<_PoolTp
, true>
425 using __common_pool
<_PoolTp
, true>::_S_get_pool
;
429 { _S_get_pool()._M_initialize_once(); }
435 if (__builtin_expect(__init
== false, false))
437 if (__gthread_active_p())
439 // On some platforms, __gthread_once_t is an aggregate.
440 static __gthread_once_t __once
= __GTHREAD_ONCE_INIT
;
441 __gthread_once(&__once
, _S_initialize
);
444 // Double check initialization. May be necessary on some
445 // systems for proper construction when not compiling with
447 _S_get_pool()._M_initialize_once();
454 /// Policy for shared __pool objects.
455 template<template <bool> class _PoolTp
, bool _Thread
>
456 struct __common_pool_policy
: public __common_pool_base
<_PoolTp
, _Thread
>
458 template<typename _Tp1
, template <bool> class _PoolTp1
= _PoolTp
,
459 bool _Thread1
= _Thread
>
461 { typedef __common_pool_policy
<_PoolTp1
, _Thread1
> other
; };
463 using __common_pool_base
<_PoolTp
, _Thread
>::_S_get_pool
;
464 using __common_pool_base
<_PoolTp
, _Thread
>::_S_initialize_once
;
468 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
469 struct __per_type_pool
471 typedef _Tp value_type
;
472 typedef _PoolTp
<_Thread
> pool_type
;
477 // Sane defaults for the _PoolTp.
478 typedef typename
pool_type::_Block_record _Block_record
;
479 const static size_t __a
= (__alignof__(_Tp
) >= sizeof(_Block_record
)
480 ? __alignof__(_Tp
) : sizeof(_Block_record
));
482 typedef typename
__pool_base::_Tune _Tune
;
483 static _Tune
_S_tune(__a
, sizeof(_Tp
) * 64,
484 sizeof(_Tp
) * 2 >= __a
? sizeof(_Tp
) * 2 : __a
,
485 sizeof(_Tp
) * size_t(_Tune::_S_chunk_size
),
486 _Tune::_S_max_threads
,
487 _Tune::_S_freelist_headroom
,
488 std::getenv("GLIBCXX_FORCE_NEW") ? true : false);
489 static pool_type
_S_pool(_S_tune
);
494 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
495 struct __per_type_pool_base
;
497 template<typename _Tp
, template <bool> class _PoolTp
>
498 struct __per_type_pool_base
<_Tp
, _PoolTp
, false>
499 : public __per_type_pool
<_Tp
, _PoolTp
, false>
501 using __per_type_pool
<_Tp
, _PoolTp
, false>::_S_get_pool
;
507 if (__builtin_expect(__init
== false, false))
509 _S_get_pool()._M_initialize_once();
516 template<typename _Tp
, template <bool> class _PoolTp
>
517 struct __per_type_pool_base
<_Tp
, _PoolTp
, true>
518 : public __per_type_pool
<_Tp
, _PoolTp
, true>
520 using __per_type_pool
<_Tp
, _PoolTp
, true>::_S_get_pool
;
524 { _S_get_pool()._M_initialize_once(); }
530 if (__builtin_expect(__init
== false, false))
532 if (__gthread_active_p())
534 // On some platforms, __gthread_once_t is an aggregate.
535 static __gthread_once_t __once
= __GTHREAD_ONCE_INIT
;
536 __gthread_once(&__once
, _S_initialize
);
539 // Double check initialization. May be necessary on some
540 // systems for proper construction when not compiling with
542 _S_get_pool()._M_initialize_once();
549 /// Policy for individual __pool objects.
550 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
551 struct __per_type_pool_policy
552 : public __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>
554 template<typename _Tp1
, template <bool> class _PoolTp1
= _PoolTp
,
555 bool _Thread1
= _Thread
>
557 { typedef __per_type_pool_policy
<_Tp1
, _PoolTp1
, _Thread1
> other
; };
559 using __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>::_S_get_pool
;
560 using __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>::_S_initialize_once
;
564 /// Base class for _Tp dependent member functions.
565 template<typename _Tp
>
566 class __mt_alloc_base
569 typedef size_t size_type
;
570 typedef ptrdiff_t difference_type
;
571 typedef _Tp
* pointer
;
572 typedef const _Tp
* const_pointer
;
573 typedef _Tp
& reference
;
574 typedef const _Tp
& const_reference
;
575 typedef _Tp value_type
;
578 address(reference __x
) const
582 address(const_reference __x
) const
586 max_size() const throw()
587 { return size_t(-1) / sizeof(_Tp
); }
589 // _GLIBCXX_RESOLVE_LIB_DEFECTS
590 // 402. wrong new expression in [some_] allocator::construct
592 construct(pointer __p
, const _Tp
& __val
)
593 { ::new((void *)__p
) _Tp(__val
); }
595 #ifdef __GXX_EXPERIMENTAL_CXX0X__
596 template<typename
... _Args
>
598 construct(pointer __p
, _Args
&&... __args
)
599 { ::new((void *)__p
) _Tp(std::forward
<_Args
>(__args
)...); }
603 destroy(pointer __p
) { __p
->~_Tp(); }
607 #define __thread_default true
609 #define __thread_default false
613 * @brief This is a fixed size (power of 2) allocator which - when
614 * compiled with thread support - will maintain one freelist per
615 * size per thread plus a @a global one. Steps are taken to limit
616 * the per thread freelist sizes (by returning excess back to
617 * the @a global list).
618 * @ingroup allocators
621 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch32.html
623 template<typename _Tp
,
624 typename _Poolp
= __common_pool_policy
<__pool
, __thread_default
> >
625 class __mt_alloc
: public __mt_alloc_base
<_Tp
>
628 typedef size_t size_type
;
629 typedef ptrdiff_t difference_type
;
630 typedef _Tp
* pointer
;
631 typedef const _Tp
* const_pointer
;
632 typedef _Tp
& reference
;
633 typedef const _Tp
& const_reference
;
634 typedef _Tp value_type
;
635 typedef _Poolp __policy_type
;
636 typedef typename
_Poolp::pool_type __pool_type
;
638 template<typename _Tp1
, typename _Poolp1
= _Poolp
>
641 typedef typename
_Poolp1::template _M_rebind
<_Tp1
>::other pol_type
;
642 typedef __mt_alloc
<_Tp1
, pol_type
> other
;
645 __mt_alloc() throw() { }
647 __mt_alloc(const __mt_alloc
&) throw() { }
649 template<typename _Tp1
, typename _Poolp1
>
650 __mt_alloc(const __mt_alloc
<_Tp1
, _Poolp1
>&) throw() { }
652 ~__mt_alloc() throw() { }
655 allocate(size_type __n
, const void* = 0);
658 deallocate(pointer __p
, size_type __n
);
660 const __pool_base::_Tune
663 // Return a copy, not a reference, for external consumption.
664 return __policy_type::_S_get_pool()._M_get_options();
668 _M_set_options(__pool_base::_Tune __t
)
669 { __policy_type::_S_get_pool()._M_set_options(__t
); }
672 template<typename _Tp
, typename _Poolp
>
673 typename __mt_alloc
<_Tp
, _Poolp
>::pointer
674 __mt_alloc
<_Tp
, _Poolp
>::
675 allocate(size_type __n
, const void*)
677 if (__n
> this->max_size())
678 std::__throw_bad_alloc();
680 __policy_type::_S_initialize_once();
682 // Requests larger than _M_max_bytes are handled by operator
683 // new/delete directly.
684 __pool_type
& __pool
= __policy_type::_S_get_pool();
685 const size_t __bytes
= __n
* sizeof(_Tp
);
686 if (__pool
._M_check_threshold(__bytes
))
688 void* __ret
= ::operator new(__bytes
);
689 return static_cast<_Tp
*>(__ret
);
692 // Round up to power of 2 and figure out which bin to use.
693 const size_t __which
= __pool
._M_get_binmap(__bytes
);
694 const size_t __thread_id
= __pool
._M_get_thread_id();
696 // Find out if we have blocks on our freelist. If so, go ahead
697 // and use them directly without having to lock anything.
699 typedef typename
__pool_type::_Bin_record _Bin_record
;
700 const _Bin_record
& __bin
= __pool
._M_get_bin(__which
);
701 if (__bin
._M_first
[__thread_id
])
704 typedef typename
__pool_type::_Block_record _Block_record
;
705 _Block_record
* __block
= __bin
._M_first
[__thread_id
];
706 __bin
._M_first
[__thread_id
] = __block
->_M_next
;
708 __pool
._M_adjust_freelist(__bin
, __block
, __thread_id
);
709 __c
= reinterpret_cast<char*>(__block
) + __pool
._M_get_align();
714 __c
= __pool
._M_reserve_block(__bytes
, __thread_id
);
716 return static_cast<_Tp
*>(static_cast<void*>(__c
));
719 template<typename _Tp
, typename _Poolp
>
721 __mt_alloc
<_Tp
, _Poolp
>::
722 deallocate(pointer __p
, size_type __n
)
724 if (__builtin_expect(__p
!= 0, true))
726 // Requests larger than _M_max_bytes are handled by
727 // operators new/delete directly.
728 __pool_type
& __pool
= __policy_type::_S_get_pool();
729 const size_t __bytes
= __n
* sizeof(_Tp
);
730 if (__pool
._M_check_threshold(__bytes
))
731 ::operator delete(__p
);
733 __pool
._M_reclaim_block(reinterpret_cast<char*>(__p
), __bytes
);
737 template<typename _Tp
, typename _Poolp
>
739 operator==(const __mt_alloc
<_Tp
, _Poolp
>&, const __mt_alloc
<_Tp
, _Poolp
>&)
742 template<typename _Tp
, typename _Poolp
>
744 operator!=(const __mt_alloc
<_Tp
, _Poolp
>&, const __mt_alloc
<_Tp
, _Poolp
>&)
747 #undef __thread_default
749 _GLIBCXX_END_NAMESPACE