1 // MT-optimized allocator -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 /** @file ext/mt_allocator.h
31 * This file is a GNU extension to the Standard C++ Library.
34 #ifndef _MT_ALLOCATOR_H
35 #define _MT_ALLOCATOR_H 1
39 #include <bits/functexcept.h>
40 #include <ext/atomicity.h>
41 #include <bits/stl_move.h>
43 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx
)
48 typedef void (*__destroy_handler
)(void*);
50 /// Base class for pool object.
53 // Using short int as type for the binmap implies we are never
54 // caching blocks larger than 32768 with this allocator.
55 typedef unsigned short int _Binmap_type
;
57 // Variables used to configure the behavior of the allocator,
58 // assigned and explained in detail below.
61 // Compile time constants for the default _Tune values.
62 enum { _S_align
= 8 };
63 enum { _S_max_bytes
= 128 };
64 enum { _S_min_bin
= 8 };
65 enum { _S_chunk_size
= 4096 - 4 * sizeof(void*) };
66 enum { _S_max_threads
= 4096 };
67 enum { _S_freelist_headroom
= 10 };
70 // NB: In any case must be >= sizeof(_Block_record), that
71 // is 4 on 32 bit machines and 8 on 64 bit machines.
74 // Allocation requests (after round-up to power of 2) below
75 // this value will be handled by the allocator. A raw new/
76 // call will be used for requests larger than this value.
77 // NB: Must be much smaller than _M_chunk_size and in any
81 // Size in bytes of the smallest bin.
82 // NB: Must be a power of 2 and >= _M_align (and of course
83 // much smaller than _M_max_bytes).
86 // In order to avoid fragmenting and minimize the number of
87 // new() calls we always request new memory using this
88 // value. Based on previous discussions on the libstdc++
89 // mailing list we have chosen the value below.
90 // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
91 // NB: At least one order of magnitude > _M_max_bytes.
94 // The maximum number of supported threads. For
95 // single-threaded operation, use one. Maximum values will
96 // vary depending on details of the underlying system. (For
97 // instance, Linux 2.4.18 reports 4070 in
98 // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
100 size_t _M_max_threads
;
102 // Each time a deallocation occurs in a threaded application
103 // we make sure that there are no more than
104 // _M_freelist_headroom % of used memory on the freelist. If
105 // the number of additional records is more than
106 // _M_freelist_headroom % of the freelist, we move these
107 // records back to the global pool.
108 size_t _M_freelist_headroom
;
110 // Set to true forces all allocations to use new().
115 : _M_align(_S_align
), _M_max_bytes(_S_max_bytes
), _M_min_bin(_S_min_bin
),
116 _M_chunk_size(_S_chunk_size
), _M_max_threads(_S_max_threads
),
117 _M_freelist_headroom(_S_freelist_headroom
),
118 _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
122 _Tune(size_t __align
, size_t __maxb
, size_t __minbin
, size_t __chunk
,
123 size_t __maxthreads
, size_t __headroom
, bool __force
)
124 : _M_align(__align
), _M_max_bytes(__maxb
), _M_min_bin(__minbin
),
125 _M_chunk_size(__chunk
), _M_max_threads(__maxthreads
),
126 _M_freelist_headroom(__headroom
), _M_force_new(__force
)
130 struct _Block_address
133 _Block_address
* _M_next
;
137 _M_get_options() const
138 { return _M_options
; }
141 _M_set_options(_Tune __t
)
148 _M_check_threshold(size_t __bytes
)
149 { return __bytes
> _M_options
._M_max_bytes
|| _M_options
._M_force_new
; }
152 _M_get_binmap(size_t __bytes
)
153 { return _M_binmap
[__bytes
]; }
157 { return _M_options
._M_align
; }
161 : _M_options(_Tune()), _M_binmap(NULL
), _M_init(false) { }
164 __pool_base(const _Tune
& __options
)
165 : _M_options(__options
), _M_binmap(NULL
), _M_init(false) { }
169 __pool_base(const __pool_base
&);
172 operator=(const __pool_base
&);
175 // Configuration options.
178 _Binmap_type
* _M_binmap
;
180 // Configuration of the pool object via _M_options can happen
181 // after construction but before initialization. After
182 // initialization is complete, this variable is set to true.
188 * @brief Data describing the underlying memory pool, parameterized on
191 template<bool _Thread
>
194 /// Specialization for single thread.
196 class __pool
<false> : public __pool_base
201 // Points to the block_record of the next free block.
202 _Block_record
* _M_next
;
207 // An "array" of pointers to the first free block.
208 _Block_record
** _M_first
;
210 // A list of the initial addresses of all allocated blocks.
211 _Block_address
* _M_address
;
217 if (__builtin_expect(_M_init
== false, false))
222 _M_destroy() throw();
225 _M_reserve_block(size_t __bytes
, const size_t __thread_id
);
228 _M_reclaim_block(char* __p
, size_t __bytes
);
231 _M_get_thread_id() { return 0; }
234 _M_get_bin(size_t __which
)
235 { return _M_bin
[__which
]; }
238 _M_adjust_freelist(const _Bin_record
&, _Block_record
*, size_t)
242 : _M_bin(NULL
), _M_bin_size(1) { }
244 explicit __pool(const __pool_base::_Tune
& __tune
)
245 : __pool_base(__tune
), _M_bin(NULL
), _M_bin_size(1) { }
248 // An "array" of bin_records each of which represents a specific
249 // power of 2 size. Memory to this "array" is allocated in
253 // Actual value calculated in _M_initialize().
261 /// Specialization for thread enabled, via gthreads.h.
263 class __pool
<true> : public __pool_base
266 // Each requesting thread is assigned an id ranging from 1 to
267 // _S_max_threads. Thread id 0 is used as a global memory pool.
268 // In order to get constant performance on the thread assignment
269 // routine, we keep a list of free ids. When a thread first
270 // requests memory we remove the first record in this list and
271 // stores the address in a __gthread_key. When initializing the
272 // __gthread_key we specify a destructor. When this destructor
273 // (i.e. the thread dies) is called, we return the thread id to
274 // the front of this list.
275 struct _Thread_record
277 // Points to next free thread id record. NULL if last record in list.
278 _Thread_record
* _M_next
;
280 // Thread id ranging from 1 to _S_max_threads.
286 // Points to the block_record of the next free block.
287 _Block_record
* _M_next
;
289 // The thread id of the thread which has requested this block.
295 // An "array" of pointers to the first free block for each
296 // thread id. Memory to this "array" is allocated in
297 // _S_initialize() for _S_max_threads + global pool 0.
298 _Block_record
** _M_first
;
300 // A list of the initial addresses of all allocated blocks.
301 _Block_address
* _M_address
;
303 // An "array" of counters used to keep track of the amount of
304 // blocks that are on the freelist/used for each thread id.
305 // - Note that the second part of the allocated _M_used "array"
306 // actually hosts (atomic) counters of reclaimed blocks: in
307 // _M_reserve_block and in _M_reclaim_block those numbers are
308 // subtracted from the first ones to obtain the actual size
309 // of the "working set" of the given thread.
310 // - Memory to these "arrays" is allocated in _S_initialize()
311 // for _S_max_threads + global pool 0.
315 // Each bin has its own mutex which is used to ensure data
316 // integrity while changing "ownership" on a block. The mutex
317 // is initialized in _S_initialize().
318 __gthread_mutex_t
* _M_mutex
;
321 // XXX GLIBCXX_ABI Deprecated
323 _M_initialize(__destroy_handler
);
328 if (__builtin_expect(_M_init
== false, false))
333 _M_destroy() throw();
336 _M_reserve_block(size_t __bytes
, const size_t __thread_id
);
339 _M_reclaim_block(char* __p
, size_t __bytes
);
342 _M_get_bin(size_t __which
)
343 { return _M_bin
[__which
]; }
346 _M_adjust_freelist(const _Bin_record
& __bin
, _Block_record
* __block
,
349 if (__gthread_active_p())
351 __block
->_M_thread_id
= __thread_id
;
352 --__bin
._M_free
[__thread_id
];
353 ++__bin
._M_used
[__thread_id
];
357 // XXX GLIBCXX_ABI Deprecated
359 _M_destroy_thread_key(void*);
365 : _M_bin(NULL
), _M_bin_size(1), _M_thread_freelist(NULL
)
368 explicit __pool(const __pool_base::_Tune
& __tune
)
369 : __pool_base(__tune
), _M_bin(NULL
), _M_bin_size(1),
370 _M_thread_freelist(NULL
)
374 // An "array" of bin_records each of which represents a specific
375 // power of 2 size. Memory to this "array" is allocated in
379 // Actual value calculated in _M_initialize().
382 _Thread_record
* _M_thread_freelist
;
383 void* _M_thread_freelist_initial
;
390 template<template <bool> class _PoolTp
, bool _Thread
>
393 typedef _PoolTp
<_Thread
> pool_type
;
398 static pool_type _S_pool
;
403 template<template <bool> class _PoolTp
, bool _Thread
>
404 struct __common_pool_base
;
406 template<template <bool> class _PoolTp
>
407 struct __common_pool_base
<_PoolTp
, false>
408 : public __common_pool
<_PoolTp
, false>
410 using __common_pool
<_PoolTp
, false>::_S_get_pool
;
416 if (__builtin_expect(__init
== false, false))
418 _S_get_pool()._M_initialize_once();
425 template<template <bool> class _PoolTp
>
426 struct __common_pool_base
<_PoolTp
, true>
427 : public __common_pool
<_PoolTp
, true>
429 using __common_pool
<_PoolTp
, true>::_S_get_pool
;
433 { _S_get_pool()._M_initialize_once(); }
439 if (__builtin_expect(__init
== false, false))
441 if (__gthread_active_p())
443 // On some platforms, __gthread_once_t is an aggregate.
444 static __gthread_once_t __once
= __GTHREAD_ONCE_INIT
;
445 __gthread_once(&__once
, _S_initialize
);
448 // Double check initialization. May be necessary on some
449 // systems for proper construction when not compiling with
451 _S_get_pool()._M_initialize_once();
458 /// Policy for shared __pool objects.
459 template<template <bool> class _PoolTp
, bool _Thread
>
460 struct __common_pool_policy
: public __common_pool_base
<_PoolTp
, _Thread
>
462 template<typename _Tp1
, template <bool> class _PoolTp1
= _PoolTp
,
463 bool _Thread1
= _Thread
>
465 { typedef __common_pool_policy
<_PoolTp1
, _Thread1
> other
; };
467 using __common_pool_base
<_PoolTp
, _Thread
>::_S_get_pool
;
468 using __common_pool_base
<_PoolTp
, _Thread
>::_S_initialize_once
;
472 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
473 struct __per_type_pool
475 typedef _Tp value_type
;
476 typedef _PoolTp
<_Thread
> pool_type
;
481 // Sane defaults for the _PoolTp.
482 typedef typename
pool_type::_Block_record _Block_record
;
483 const static size_t __a
= (__alignof__(_Tp
) >= sizeof(_Block_record
)
484 ? __alignof__(_Tp
) : sizeof(_Block_record
));
486 typedef typename
__pool_base::_Tune _Tune
;
487 static _Tune
_S_tune(__a
, sizeof(_Tp
) * 64,
488 sizeof(_Tp
) * 2 >= __a
? sizeof(_Tp
) * 2 : __a
,
489 sizeof(_Tp
) * size_t(_Tune::_S_chunk_size
),
490 _Tune::_S_max_threads
,
491 _Tune::_S_freelist_headroom
,
492 std::getenv("GLIBCXX_FORCE_NEW") ? true : false);
493 static pool_type
_S_pool(_S_tune
);
498 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
499 struct __per_type_pool_base
;
501 template<typename _Tp
, template <bool> class _PoolTp
>
502 struct __per_type_pool_base
<_Tp
, _PoolTp
, false>
503 : public __per_type_pool
<_Tp
, _PoolTp
, false>
505 using __per_type_pool
<_Tp
, _PoolTp
, false>::_S_get_pool
;
511 if (__builtin_expect(__init
== false, false))
513 _S_get_pool()._M_initialize_once();
520 template<typename _Tp
, template <bool> class _PoolTp
>
521 struct __per_type_pool_base
<_Tp
, _PoolTp
, true>
522 : public __per_type_pool
<_Tp
, _PoolTp
, true>
524 using __per_type_pool
<_Tp
, _PoolTp
, true>::_S_get_pool
;
528 { _S_get_pool()._M_initialize_once(); }
534 if (__builtin_expect(__init
== false, false))
536 if (__gthread_active_p())
538 // On some platforms, __gthread_once_t is an aggregate.
539 static __gthread_once_t __once
= __GTHREAD_ONCE_INIT
;
540 __gthread_once(&__once
, _S_initialize
);
543 // Double check initialization. May be necessary on some
544 // systems for proper construction when not compiling with
546 _S_get_pool()._M_initialize_once();
553 /// Policy for individual __pool objects.
554 template<typename _Tp
, template <bool> class _PoolTp
, bool _Thread
>
555 struct __per_type_pool_policy
556 : public __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>
558 template<typename _Tp1
, template <bool> class _PoolTp1
= _PoolTp
,
559 bool _Thread1
= _Thread
>
561 { typedef __per_type_pool_policy
<_Tp1
, _PoolTp1
, _Thread1
> other
; };
563 using __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>::_S_get_pool
;
564 using __per_type_pool_base
<_Tp
, _PoolTp
, _Thread
>::_S_initialize_once
;
568 /// Base class for _Tp dependent member functions.
569 template<typename _Tp
>
570 class __mt_alloc_base
573 typedef size_t size_type
;
574 typedef ptrdiff_t difference_type
;
575 typedef _Tp
* pointer
;
576 typedef const _Tp
* const_pointer
;
577 typedef _Tp
& reference
;
578 typedef const _Tp
& const_reference
;
579 typedef _Tp value_type
;
582 address(reference __x
) const
586 address(const_reference __x
) const
590 max_size() const throw()
591 { return size_t(-1) / sizeof(_Tp
); }
593 // _GLIBCXX_RESOLVE_LIB_DEFECTS
594 // 402. wrong new expression in [some_] allocator::construct
596 construct(pointer __p
, const _Tp
& __val
)
597 { ::new((void *)__p
) _Tp(__val
); }
599 #ifdef __GXX_EXPERIMENTAL_CXX0X__
600 template<typename
... _Args
>
602 construct(pointer __p
, _Args
&&... __args
)
603 { ::new((void *)__p
) _Tp(std::forward
<_Args
>(__args
)...); }
607 destroy(pointer __p
) { __p
->~_Tp(); }
611 #define __thread_default true
613 #define __thread_default false
617 * @brief This is a fixed size (power of 2) allocator which - when
618 * compiled with thread support - will maintain one freelist per
619 * size per thread plus a "global" one. Steps are taken to limit
620 * the per thread freelist sizes (by returning excess back to
621 * the "global" list).
624 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch32.html
626 template<typename _Tp
,
627 typename _Poolp
= __common_pool_policy
<__pool
, __thread_default
> >
628 class __mt_alloc
: public __mt_alloc_base
<_Tp
>
631 typedef size_t size_type
;
632 typedef ptrdiff_t difference_type
;
633 typedef _Tp
* pointer
;
634 typedef const _Tp
* const_pointer
;
635 typedef _Tp
& reference
;
636 typedef const _Tp
& const_reference
;
637 typedef _Tp value_type
;
638 typedef _Poolp __policy_type
;
639 typedef typename
_Poolp::pool_type __pool_type
;
641 template<typename _Tp1
, typename _Poolp1
= _Poolp
>
644 typedef typename
_Poolp1::template _M_rebind
<_Tp1
>::other pol_type
;
645 typedef __mt_alloc
<_Tp1
, pol_type
> other
;
648 __mt_alloc() throw() { }
650 __mt_alloc(const __mt_alloc
&) throw() { }
652 template<typename _Tp1
, typename _Poolp1
>
653 __mt_alloc(const __mt_alloc
<_Tp1
, _Poolp1
>&) throw() { }
655 ~__mt_alloc() throw() { }
658 allocate(size_type __n
, const void* = 0);
661 deallocate(pointer __p
, size_type __n
);
663 const __pool_base::_Tune
666 // Return a copy, not a reference, for external consumption.
667 return __policy_type::_S_get_pool()._M_get_options();
671 _M_set_options(__pool_base::_Tune __t
)
672 { __policy_type::_S_get_pool()._M_set_options(__t
); }
675 template<typename _Tp
, typename _Poolp
>
676 typename __mt_alloc
<_Tp
, _Poolp
>::pointer
677 __mt_alloc
<_Tp
, _Poolp
>::
678 allocate(size_type __n
, const void*)
680 if (__builtin_expect(__n
> this->max_size(), false))
681 std::__throw_bad_alloc();
683 __policy_type::_S_initialize_once();
685 // Requests larger than _M_max_bytes are handled by operator
686 // new/delete directly.
687 __pool_type
& __pool
= __policy_type::_S_get_pool();
688 const size_t __bytes
= __n
* sizeof(_Tp
);
689 if (__pool
._M_check_threshold(__bytes
))
691 void* __ret
= ::operator new(__bytes
);
692 return static_cast<_Tp
*>(__ret
);
695 // Round up to power of 2 and figure out which bin to use.
696 const size_t __which
= __pool
._M_get_binmap(__bytes
);
697 const size_t __thread_id
= __pool
._M_get_thread_id();
699 // Find out if we have blocks on our freelist. If so, go ahead
700 // and use them directly without having to lock anything.
702 typedef typename
__pool_type::_Bin_record _Bin_record
;
703 const _Bin_record
& __bin
= __pool
._M_get_bin(__which
);
704 if (__bin
._M_first
[__thread_id
])
707 typedef typename
__pool_type::_Block_record _Block_record
;
708 _Block_record
* __block
= __bin
._M_first
[__thread_id
];
709 __bin
._M_first
[__thread_id
] = __block
->_M_next
;
711 __pool
._M_adjust_freelist(__bin
, __block
, __thread_id
);
712 __c
= reinterpret_cast<char*>(__block
) + __pool
._M_get_align();
717 __c
= __pool
._M_reserve_block(__bytes
, __thread_id
);
719 return static_cast<_Tp
*>(static_cast<void*>(__c
));
722 template<typename _Tp
, typename _Poolp
>
724 __mt_alloc
<_Tp
, _Poolp
>::
725 deallocate(pointer __p
, size_type __n
)
727 if (__builtin_expect(__p
!= 0, true))
729 // Requests larger than _M_max_bytes are handled by
730 // operators new/delete directly.
731 __pool_type
& __pool
= __policy_type::_S_get_pool();
732 const size_t __bytes
= __n
* sizeof(_Tp
);
733 if (__pool
._M_check_threshold(__bytes
))
734 ::operator delete(__p
);
736 __pool
._M_reclaim_block(reinterpret_cast<char*>(__p
), __bytes
);
740 template<typename _Tp
, typename _Poolp
>
742 operator==(const __mt_alloc
<_Tp
, _Poolp
>&, const __mt_alloc
<_Tp
, _Poolp
>&)
745 template<typename _Tp
, typename _Poolp
>
747 operator!=(const __mt_alloc
<_Tp
, _Poolp
>&, const __mt_alloc
<_Tp
, _Poolp
>&)
750 #undef __thread_default
752 _GLIBCXX_END_NAMESPACE