1 // MT-optimized allocator -*- C++ -*-
3 // Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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.
32 * You should only include this header if you are using GCC 3 or later.
35 #ifndef _MT_ALLOCATOR_H
36 #define _MT_ALLOCATOR_H 1
40 #include <bits/functexcept.h>
41 #include <bits/gthr.h>
42 #include <bits/atomicity.h>
47 * This is a fixed size (power of 2) allocator which - when
48 * compiled with thread support - will maintain one freelist per
49 * size per thread plus a "global" one. Steps are taken to limit
50 * the per thread freelist sizes (by returning excess back to
54 * http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html
56 typedef void (*__destroy_handler)(void*);
57 typedef void (*__create_handler)(void);
61 // Using short int as type for the binmap implies we are never
62 // caching blocks larger than 65535 with this allocator.
63 typedef unsigned short int _Binmap_type;
65 // Variables used to configure the behavior of the allocator,
66 // assigned and explained in detail below.
69 // Compile time constants for the default _Tune values.
70 enum { _S_align = 8 };
71 enum { _S_max_bytes = 128 };
72 enum { _S_min_bin = 8 };
73 enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
74 enum { _S_max_threads = 4096 };
75 enum { _S_freelist_headroom = 10 };
78 // NB: In any case must be >= sizeof(_Block_record), that
79 // is 4 on 32 bit machines and 8 on 64 bit machines.
82 // Allocation requests (after round-up to power of 2) below
83 // this value will be handled by the allocator. A raw new/
84 // call will be used for requests larger than this value.
87 // Size in bytes of the smallest bin.
88 // NB: Must be a power of 2 and >= _M_align.
91 // In order to avoid fragmenting and minimize the number of
92 // new() calls we always request new memory using this
93 // value. Based on previous discussions on the libstdc++
94 // mailing list we have choosen the value below.
95 // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
98 // The maximum number of supported threads. For
99 // single-threaded operation, use one. Maximum values will
100 // vary depending on details of the underlying system. (For
101 // instance, Linux 2.4.18 reports 4070 in
102 // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
104 size_t _M_max_threads;
106 // Each time a deallocation occurs in a threaded application
107 // we make sure that there are no more than
108 // _M_freelist_headroom % of used memory on the freelist. If
109 // the number of additional records is more than
110 // _M_freelist_headroom % of the freelist, we move these
111 // records back to the global pool.
112 size_t _M_freelist_headroom;
114 // Set to true forces all allocations to use new().
119 : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
120 _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads),
121 _M_freelist_headroom(_S_freelist_headroom),
122 _M_force_new(getenv("GLIBCXX_FORCE_NEW") ? true : false)
126 _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk,
127 size_t __maxthreads, size_t __headroom, bool __force)
128 : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
129 _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
130 _M_freelist_headroom(__headroom), _M_force_new(__force)
137 __ret &= _M_align == _S_align;
138 __ret &= _M_max_bytes == _S_max_bytes;
139 __ret &= _M_min_bin == _S_min_bin;
140 __ret &= _M_chunk_size == _S_chunk_size;
141 __ret &= _M_max_threads == _S_max_threads;
142 __ret &= _M_freelist_headroom == _S_freelist_headroom;
147 struct _Block_address
150 _Block_address* _M_next;
154 _M_get_options() const
155 { return _M_options; }
158 _M_set_options(_Tune __t)
165 _M_check_threshold(size_t __bytes)
166 { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }
169 _M_get_binmap(size_t __bytes)
170 { return _M_binmap[__bytes]; }
172 explicit __pool_base()
173 : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { }
175 explicit __pool_base(const _Tune& __tune)
176 : _M_options(__tune), _M_binmap(NULL), _M_init(false) { }
179 // Configuration options.
182 _Binmap_type* _M_binmap;
184 // We need to create the initial lists and set up some variables
185 // before we can answer to the first request for memory.
189 // Data describing the underlying memory pool, parameterized on
190 // threading support.
191 template<bool _Thread>
202 // Specialization for thread enabled, via gthreads.h.
204 class __pool<true> : public __pool_base
207 // Each requesting thread is assigned an id ranging from 1 to
208 // _S_max_threads. Thread id 0 is used as a global memory pool.
209 // In order to get constant performance on the thread assignment
210 // routine, we keep a list of free ids. When a thread first
211 // requests memory we remove the first record in this list and
212 // stores the address in a __gthread_key. When initializing the
213 // __gthread_key we specify a destructor. When this destructor
214 // (i.e. the thread dies) is called, we return the thread id to
215 // the front of this list.
216 struct _Thread_record
218 // Points to next free thread id record. NULL if last record in list.
219 _Thread_record* volatile _M_next;
221 // Thread id ranging from 1 to _S_max_threads.
227 // Points to the block_record of the next free block.
228 _Block_record* volatile _M_next;
230 // The thread id of the thread which has requested this block.
236 // An "array" of pointers to the first free block for each
237 // thread id. Memory to this "array" is allocated in
238 // _S_initialize() for _S_max_threads + global pool 0.
239 _Block_record** volatile _M_first;
241 // A list of the initial addresses of all allocated blocks.
242 _Block_address* _M_address;
244 // An "array" of counters used to keep track of the amount of
245 // blocks that are on the freelist/used for each thread id.
246 // Memory to these "arrays" is allocated in _S_initialize() for
247 // _S_max_threads + global pool 0.
248 size_t* volatile _M_free;
249 size_t* volatile _M_used;
251 // Each bin has its own mutex which is used to ensure data
252 // integrity while changing "ownership" on a block. The mutex
253 // is initialized in _S_initialize().
254 __gthread_mutex_t* _M_mutex;
258 _M_initialize(__destroy_handler __d);
261 _M_initialize_once(__create_handler __c)
263 // Although the test in __gthread_once() would suffice, we
264 // wrap test of the once condition in our own unlocked
265 // check. This saves one function call to pthread_once()
266 // (which itself only tests for the once value unlocked anyway
267 // and immediately returns if set)
268 if (__builtin_expect(_M_init == false, false))
270 if (__gthread_active_p())
271 __gthread_once(&_M_once, __c);
278 _M_destroy() throw();
281 _M_reserve_block(size_t __bytes, const size_t __thread_id);
284 _M_reclaim_block(char* __p, size_t __bytes);
287 _M_get_bin(size_t __which)
288 { return _M_bin[__which]; }
291 _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block,
294 if (__gthread_active_p())
296 __block->_M_thread_id = __thread_id;
297 --__bin._M_free[__thread_id];
298 ++__bin._M_used[__thread_id];
303 _M_destroy_thread_key(void* __freelist_pos);
309 : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL)
311 // On some platforms, __gthread_once_t is an aggregate.
312 __gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
316 explicit __pool(const __pool_base::_Tune& __tune)
317 : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1),
318 _M_thread_freelist(NULL)
320 // On some platforms, __gthread_once_t is an aggregate.
321 __gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
328 // An "array" of bin_records each of which represents a specific
329 // power of 2 size. Memory to this "array" is allocated in
331 _Bin_record* volatile _M_bin;
333 // Actual value calculated in _M_initialize().
336 __gthread_once_t _M_once;
338 _Thread_record* _M_thread_freelist;
339 void* _M_thread_freelist_initial;
343 // Specialization for single thread.
345 class __pool<false> : public __pool_base
350 // Points to the block_record of the next free block.
351 _Block_record* volatile _M_next;
356 // An "array" of pointers to the first free block.
357 _Block_record** volatile _M_first;
359 // A list of the initial addresses of all allocated blocks.
360 _Block_address* _M_address;
366 if (__builtin_expect(_M_init == false, false))
371 _M_destroy() throw();
374 _M_reserve_block(size_t __bytes, const size_t __thread_id);
377 _M_reclaim_block(char* __p, size_t __bytes);
380 _M_get_thread_id() { return 0; }
383 _M_get_bin(size_t __which)
384 { return _M_bin[__which]; }
387 _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
391 : _M_bin(NULL), _M_bin_size(1) { }
393 explicit __pool(const __pool_base::_Tune& __tune)
394 : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1) { }
399 // An "array" of bin_records each of which represents a specific
400 // power of 2 size. Memory to this "array" is allocated in
402 _Bin_record* volatile _M_bin;
404 // Actual value calculated in _M_initialize().
411 template<bool _Thread>
412 struct __common_pool_policy
414 typedef __pool<_Thread> __pool_type;
416 template<typename _Tp1, bool _Thread1 = _Thread>
419 template<typename _Tp1>
420 struct _M_rebind<_Tp1, true>
421 { typedef __common_pool_policy<true> other; };
423 template<typename _Tp1>
424 struct _M_rebind<_Tp1, false>
425 { typedef __common_pool_policy<false> other; };
430 static __pool_type _S_pool;
438 if (__builtin_expect(__init == false, false))
440 _S_get_pool()._M_initialize_once();
447 struct __common_pool_policy<true>;
451 struct __common_pool_policy<true>
453 typedef __pool<true> __pool_type;
455 template<typename _Tp1, bool _Thread1 = true>
458 template<typename _Tp1>
459 struct _M_rebind<_Tp1, true>
460 { typedef __common_pool_policy<true> other; };
462 template<typename _Tp1>
463 struct _M_rebind<_Tp1, false>
464 { typedef __common_pool_policy<false> other; };
469 static __pool_type _S_pool;
474 _S_destroy_thread_key(void* __freelist_pos)
475 { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
479 { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
485 if (__builtin_expect(__init == false, false))
487 _S_get_pool()._M_initialize_once(_S_initialize);
495 template<typename _Tp, bool _Thread>
496 struct __per_type_pool_policy
498 typedef __pool<_Thread> __pool_type;
500 template<typename _Tp1, bool _Thread1 = _Thread>
503 template<typename _Tp1>
504 struct _M_rebind<_Tp1, false>
505 { typedef __per_type_pool_policy<_Tp1, false> other; };
507 template<typename _Tp1>
508 struct _M_rebind<_Tp1, true>
509 { typedef __per_type_pool_policy<_Tp1, true> other; };
511 // Avoid static initialization ordering issues.
515 // Sane defaults for the __pool_type.
516 const static size_t __align = __alignof__(_Tp) >= sizeof(typename __pool_type::_Block_record) ? __alignof__(_Tp) : sizeof(typename __pool_type::_Block_record);
517 static __pool_base::_Tune _S_tune(__align, sizeof(_Tp) * 128, (sizeof(_Tp) * 2) >= __align ? sizeof(_Tp) * 2 : __align, __pool_type::_Tune::_S_chunk_size, __pool_type::_Tune::_S_max_threads, __pool_type::_Tune::_S_freelist_headroom, getenv("GLIBCXX_FORCE_NEW") ? true : false);
518 static __pool_type _S_pool(_S_tune);
526 if (__builtin_expect(__init == false, false))
528 _S_get_pool()._M_initialize_once();
534 template<typename _Tp>
535 struct __per_type_pool_policy<_Tp, true>;
538 template<typename _Tp>
539 struct __per_type_pool_policy<_Tp, true>
541 typedef __pool<true> __pool_type;
543 template<typename _Tp1, bool _Thread1 = true>
546 template<typename _Tp1>
547 struct _M_rebind<_Tp1, false>
548 { typedef __per_type_pool_policy<_Tp1, false> other; };
550 template<typename _Tp1>
551 struct _M_rebind<_Tp1, true>
552 { typedef __per_type_pool_policy<_Tp1, true> other; };
554 // Avoid static initialization ordering issues.
558 // Sane defaults for the __pool_type.
559 const static size_t __align = __alignof__(_Tp) >= sizeof(typename __pool_type::_Block_record) ? __alignof__(_Tp) : sizeof(typename __pool_type::_Block_record);
560 static __pool_base::_Tune _S_tune(__align, sizeof(_Tp) * 128, (sizeof(_Tp) * 2) >= __align ? sizeof(_Tp) * 2 : __align, __pool_type::_Tune::_S_chunk_size, __pool_type::_Tune::_S_max_threads, __pool_type::_Tune::_S_freelist_headroom, getenv("GLIBCXX_FORCE_NEW") ? true : false);
561 static __pool_type _S_pool(_S_tune);
566 _S_destroy_thread_key(void* __freelist_pos)
567 { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
571 { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
577 if (__builtin_expect(__init == false, false))
579 _S_get_pool()._M_initialize_once(_S_initialize);
586 template<typename _Tp>
587 class __mt_alloc_base
590 typedef size_t size_type;
591 typedef ptrdiff_t difference_type;
592 typedef _Tp* pointer;
593 typedef const _Tp* const_pointer;
594 typedef _Tp& reference;
595 typedef const _Tp& const_reference;
596 typedef _Tp value_type;
599 address(reference __x) const
603 address(const_reference __x) const
607 max_size() const throw()
608 { return size_t(-1) / sizeof(_Tp); }
610 // _GLIBCXX_RESOLVE_LIB_DEFECTS
611 // 402. wrong new expression in [some_] allocator::construct
613 construct(pointer __p, const _Tp& __val)
614 { ::new(__p) _Tp(__val); }
617 destroy(pointer __p) { __p->~_Tp(); }
621 #define __default_policy __common_pool_policy<true>
623 #define __default_policy __common_pool_policy<false>
626 template<typename _Tp, typename _Poolp = __default_policy>
627 class __mt_alloc : public __mt_alloc_base<_Tp>, _Poolp
630 typedef size_t size_type;
631 typedef ptrdiff_t difference_type;
632 typedef _Tp* pointer;
633 typedef const _Tp* const_pointer;
634 typedef _Tp& reference;
635 typedef const _Tp& const_reference;
636 typedef _Tp value_type;
637 typedef _Poolp __policy_type;
638 typedef typename _Poolp::__pool_type __pool_type;
640 template<typename _Tp1, typename _Poolp1 = _Poolp>
643 typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
644 typedef __mt_alloc<_Tp1, pol_type> other;
648 { __policy_type::_S_get_pool(); }
650 __mt_alloc(const __mt_alloc&) throw()
651 { __policy_type::_S_get_pool(); }
653 template<typename _Tp1, typename _Poolp1>
654 __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>& obj) throw()
655 { __policy_type::_S_get_pool(); }
657 ~__mt_alloc() throw() { }
660 allocate(size_type __n, const void* = 0);
663 deallocate(pointer __p, size_type __n);
665 const __pool_base::_Tune
668 // Return a copy, not a reference, for external consumption.
669 return __pool_base::_Tune(this->_S_get_pool()._M_get_options());
673 _M_set_options(__pool_base::_Tune __t)
674 { this->_S_get_pool()._M_set_options(__t); }
677 template<typename _Tp, typename _Poolp>
678 typename __mt_alloc<_Tp, _Poolp>::pointer
679 __mt_alloc<_Tp, _Poolp>::
680 allocate(size_type __n, const void*)
682 this->_S_initialize_once();
684 // Requests larger than _M_max_bytes are handled by operator
685 // new/delete directly.
686 __pool_type& __pool = this->_S_get_pool();
687 const size_t __bytes = __n * sizeof(_Tp);
688 if (__pool._M_check_threshold(__bytes))
690 void* __ret = ::operator new(__bytes);
691 return static_cast<_Tp*>(__ret);
694 // Round up to power of 2 and figure out which bin to use.
695 const size_t __which = __pool._M_get_binmap(__bytes);
696 const size_t __thread_id = __pool._M_get_thread_id();
698 // Find out if we have blocks on our freelist. If so, go ahead
699 // and use them directly without having to lock anything.
701 typedef typename __pool_type::_Bin_record _Bin_record;
702 const _Bin_record& __bin = __pool._M_get_bin(__which);
703 if (__bin._M_first[__thread_id])
706 typedef typename __pool_type::_Block_record _Block_record;
707 _Block_record* __block = __bin._M_first[__thread_id];
708 __bin._M_first[__thread_id] = __bin._M_first[__thread_id]->_M_next;
710 __pool._M_adjust_freelist(__bin, __block, __thread_id);
711 const __pool_base::_Tune& __options = __pool._M_get_options();
712 __c = reinterpret_cast<char*>(__block) + __options._M_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 // Requests larger than _M_max_bytes are handled by operators
728 // new/delete directly.
729 __pool_type& __pool = this->_S_get_pool();
730 const size_t __bytes = __n * sizeof(_Tp);
731 if (__pool._M_check_threshold(__bytes))
732 ::operator delete(__p);
734 __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 __default_policy
748 } // namespace __gnu_cxx