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 template<typename _Tp>
60 typedef size_t size_type;
61 typedef ptrdiff_t difference_type;
63 typedef const _Tp* const_pointer;
64 typedef _Tp& reference;
65 typedef const _Tp& const_reference;
66 typedef _Tp value_type;
68 template<typename _Tp1>
70 { typedef __mt_alloc<_Tp1> other; };
77 __mt_alloc(const __mt_alloc&) throw()
82 template<typename _Tp1>
83 __mt_alloc(const __mt_alloc<_Tp1>& obj) throw()
88 ~__mt_alloc() throw() { }
91 address(reference __x) const
95 address(const_reference __x) const
99 max_size() const throw()
100 { return size_t(-1) / sizeof(_Tp); }
102 // _GLIBCXX_RESOLVE_LIB_DEFECTS
103 // 402. wrong new expression in [some_] allocator::construct
105 construct(pointer __p, const _Tp& __val)
106 { ::new(__p) _Tp(__val); }
109 destroy(pointer __p) { __p->~_Tp(); }
112 allocate(size_type __n, const void* = 0);
115 deallocate(pointer __p, size_type __n);
117 // Variables used to configure the behavior of the allocator,
118 // assigned and explained in detail below.
121 // Allocation requests (after round-up to power of 2) below
122 // this value will be handled by the allocator. A raw new/
123 // call will be used for requests larger than this value.
126 // Size in bytes of the smallest bin (must be a power of 2).
129 // In order to avoid fragmenting and minimize the number of
130 // new() calls we always request new memory using this
131 // value. Based on previous discussions on the libstdc++
132 // mailing list we have choosen the value below.
133 // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
134 size_t _M_chunk_size;
136 // The maximum number of supported threads. Our Linux 2.4.18
137 // reports 4070 in /proc/sys/kernel/threads-max
138 size_t _M_max_threads;
140 // Each time a deallocation occurs in a threaded application
141 // we make sure that there are no more than
142 // _M_freelist_headroom % of used memory on the freelist. If
143 // the number of additional records is more than
144 // _M_freelist_headroom % of the freelist, we move these
145 // records back to the global pool.
146 size_t _M_freelist_headroom;
148 // Set to true forces all allocations to use new().
153 : _M_max_bytes(128), _M_min_bin(8),
154 _M_chunk_size(4096 - 4 * sizeof(void*)),
155 _M_max_threads(4096), _M_freelist_headroom(10),
156 _M_force_new(getenv("GLIBCXX_FORCE_NEW") ? true : false)
160 _Tune(size_t __maxb, size_t __minbin, size_t __chunk,
161 size_t __maxthreads, size_t __headroom, bool __force)
162 : _M_max_bytes(__maxb), _M_min_bin(__minbin), _M_chunk_size(__chunk),
163 _M_max_threads(__maxthreads), _M_freelist_headroom(__headroom),
164 _M_force_new(__force)
169 // We need to create the initial lists and set up some variables
170 // before we can answer to the first request for memory.
172 static __gthread_once_t _S_once;
179 // Configuration options.
180 static _Tune _S_options;
184 { return _S_options; }
187 _S_set_options(_Tune __t)
193 // Using short int as type for the binmap implies we are never
194 // caching blocks larger than 65535 with this allocator
195 typedef unsigned short int _Binmap_type;
196 static _Binmap_type* _S_binmap;
198 // Each requesting thread is assigned an id ranging from 1 to
199 // _S_max_threads. Thread id 0 is used as a global memory pool.
200 // In order to get constant performance on the thread assignment
201 // routine, we keep a list of free ids. When a thread first
202 // requests memory we remove the first record in this list and
203 // stores the address in a __gthread_key. When initializing the
204 // __gthread_key we specify a destructor. When this destructor
205 // (i.e. the thread dies) is called, we return the thread id to
206 // the front of this list.
208 struct _Thread_record
210 // Points to next free thread id record. NULL if last record in list.
211 _Thread_record* volatile _M_next;
213 // Thread id ranging from 1 to _S_max_threads.
217 static _Thread_record* volatile _S_thread_freelist_first;
218 static __gthread_mutex_t _S_thread_freelist_mutex;
219 static __gthread_key_t _S_thread_key;
222 _S_destroy_thread_key(void* __freelist_pos);
230 // Points to the block_record of the next free block.
231 _Block_record* volatile _M_next;
234 // The thread id of the thread which has requested this block.
241 // An "array" of pointers to the first free block for each
242 // thread id. Memory to this "array" is allocated in _S_initialize()
243 // for _S_max_threads + global pool 0.
244 _Block_record** volatile _M_first;
247 // An "array" of counters used to keep track of the amount of
248 // blocks that are on the freelist/used for each thread id.
249 // Memory to these "arrays" is allocated in _S_initialize() for
250 // _S_max_threads + global pool 0.
251 size_t* volatile _M_free;
252 size_t* volatile _M_used;
254 // Each bin has its own mutex which is used to ensure data
255 // integrity while changing "ownership" on a block. The mutex
256 // is initialized in _S_initialize().
257 __gthread_mutex_t* _M_mutex;
261 // An "array" of bin_records each of which represents a specific
262 // power of 2 size. Memory to this "array" is allocated in
264 static _Bin_record* volatile _S_bin;
266 // Actual value calculated in _S_initialize().
267 static size_t _S_bin_size;
270 template<typename _Tp>
271 typename __mt_alloc<_Tp>::pointer
273 allocate(size_type __n, const void*)
275 // Although the test in __gthread_once() would suffice, we wrap
276 // test of the once condition in our own unlocked check. This
277 // saves one function call to pthread_once() (which itself only
278 // tests for the once value unlocked anyway and immediately
283 if (__gthread_active_p())
284 __gthread_once(&_S_once, _S_initialize);
290 // Requests larger than _M_max_bytes are handled by new/delete
292 const size_t __bytes = __n * sizeof(_Tp);
293 if (__bytes > _S_options._M_max_bytes || _S_options._M_force_new)
295 void* __ret = ::operator new(__bytes);
296 return static_cast<_Tp*>(__ret);
299 // Round up to power of 2 and figure out which bin to use.
300 const size_t __which = _S_binmap[__bytes];
301 const size_t __thread_id = _S_get_thread_id();
303 // Find out if we have blocks on our freelist. If so, go ahead
304 // and use them directly without having to lock anything.
305 const _Bin_record& __bin = _S_bin[__which];
306 _Block_record* __block = NULL;
307 if (__bin._M_first[__thread_id] == NULL)
309 const size_t __bin_size = ((_S_options._M_min_bin << __which)
310 + sizeof(_Block_record));
311 size_t __block_count = _S_options._M_chunk_size / __bin_size;
313 // Are we using threads?
314 // - Yes, check if there are free blocks on the global
315 // list. If so, grab up to __block_count blocks in one
316 // lock and change ownership. If the global list is
317 // empty, we allocate a new chunk and add those blocks
318 // directly to our own freelist (with us as owner).
319 // - No, all operations are made directly to global pool 0
320 // no need to lock or change ownership but check for free
321 // blocks on global list (and if not add new ones) and
322 // get the first one.
324 if (__gthread_active_p())
326 __gthread_mutex_lock(__bin._M_mutex);
327 if (__bin._M_first[0] == NULL)
329 // No need to hold the lock when we are adding a
330 // whole chunk to our own list.
331 __gthread_mutex_unlock(__bin._M_mutex);
333 void* __v = ::operator new(_S_options._M_chunk_size);
334 __bin._M_first[__thread_id] = static_cast<_Block_record*>(__v);
335 __bin._M_free[__thread_id] = __block_count;
338 __block = __bin._M_first[__thread_id];
339 while (__block_count-- > 0)
341 char* __c = reinterpret_cast<char*>(__block) + __bin_size;
342 __block->_M_next = reinterpret_cast<_Block_record*>(__c);
343 __block = __block->_M_next;
345 __block->_M_next = NULL;
349 // Is the number of required blocks greater than or
350 // equal to the number that can be provided by the
352 __bin._M_first[__thread_id] = __bin._M_first[0];
353 if (__block_count >= __bin._M_free[0])
355 __bin._M_free[__thread_id] = __bin._M_free[0];
356 __bin._M_free[0] = 0;
357 __bin._M_first[0] = NULL;
361 __bin._M_free[__thread_id] = __block_count;
362 __bin._M_free[0] -= __block_count;
364 __block = __bin._M_first[0];
365 while (__block_count-- > 0)
366 __block = __block->_M_next;
367 __bin._M_first[0] = __block->_M_next;
368 __block->_M_next = NULL;
370 __gthread_mutex_unlock(__bin._M_mutex);
376 void* __v = ::operator new(_S_options._M_chunk_size);
377 __bin._M_first[0] = static_cast<_Block_record*>(__v);
380 __block = __bin._M_first[0];
381 while (__block_count-- > 0)
383 char* __c = reinterpret_cast<char*>(__block) + __bin_size;
384 __block->_M_next = reinterpret_cast<_Block_record*>(__c);
385 __block = __block->_M_next;
387 __block->_M_next = NULL;
391 __block = __bin._M_first[__thread_id];
392 __bin._M_first[__thread_id] = __bin._M_first[__thread_id]->_M_next;
394 if (__gthread_active_p())
396 __block->_M_thread_id = __thread_id;
397 --__bin._M_free[__thread_id];
398 ++__bin._M_used[__thread_id];
402 char* __c = reinterpret_cast<char*>(__block) + sizeof(_Block_record);
403 return static_cast<_Tp*>(static_cast<void*>(__c));
406 template<typename _Tp>
409 deallocate(pointer __p, size_type __n)
411 // Requests larger than _M_max_bytes are handled by operators
412 // new/delete directly.
413 const size_t __bytes = __n * sizeof(_Tp);
414 if (__bytes > _S_options._M_max_bytes || _S_options._M_force_new)
416 ::operator delete(__p);
420 // Round up to power of 2 and figure out which bin to use.
421 const size_t __which = _S_binmap[__bytes];
422 const _Bin_record& __bin = _S_bin[__which];
424 char* __c = reinterpret_cast<char*>(__p) - sizeof(_Block_record);
425 _Block_record* __block = reinterpret_cast<_Block_record*>(__c);
428 if (__gthread_active_p())
430 // Calculate the number of records to remove from our freelist:
431 // in order to avoid too much contention we wait until the
432 // number of records is "high enough".
433 const size_t __thread_id = _S_get_thread_id();
435 long __remove = ((__bin._M_free[__thread_id]
436 * _S_options._M_freelist_headroom)
437 - __bin._M_used[__thread_id]);
438 if (__remove > static_cast<long>(100 * (_S_bin_size - __which)
439 * _S_options._M_freelist_headroom)
440 && __remove > static_cast<long>(__bin._M_free[__thread_id]))
442 _Block_record* __tmp = __bin._M_first[__thread_id];
443 _Block_record* __first = __tmp;
444 __remove /= _S_options._M_freelist_headroom;
445 const long __removed = __remove;
447 while (__remove-- > 0)
448 __tmp = __tmp->_M_next;
449 __bin._M_first[__thread_id] = __tmp->_M_next;
450 __bin._M_free[__thread_id] -= __removed;
452 __gthread_mutex_lock(__bin._M_mutex);
453 __tmp->_M_next = __bin._M_first[0];
454 __bin._M_first[0] = __first;
455 __bin._M_free[0] += __removed;
456 __gthread_mutex_unlock(__bin._M_mutex);
459 // Return this block to our list and update counters and
460 // owner id as needed.
461 --__bin._M_used[__block->_M_thread_id];
463 __block->_M_next = __bin._M_first[__thread_id];
464 __bin._M_first[__thread_id] = __block;
466 ++__bin._M_free[__thread_id];
471 // Single threaded application - return to global pool.
472 __block->_M_next = __bin._M_first[0];
473 __bin._M_first[0] = __block;
477 template<typename _Tp>
482 if (_S_options._M_force_new)
485 // Calculate the number of bins required based on _M_max_bytes.
486 // _S_bin_size is statically-initialized to one.
487 size_t __bin_size = _S_options._M_min_bin;
488 while (_S_options._M_max_bytes > __bin_size)
494 // Setup the bin map for quick lookup of the relevant bin.
495 const size_t __j = (_S_options._M_max_bytes + 1) * sizeof(_Binmap_type);
496 _S_binmap = static_cast<_Binmap_type*>(::operator new(__j));
498 _Binmap_type* __bp = _S_binmap;
499 _Binmap_type __bin_max = _S_options._M_min_bin;
500 _Binmap_type __bint = 0;
501 for (_Binmap_type __ct = 0; __ct <= _S_options._M_max_bytes; ++__ct)
503 if (__ct > __bin_max)
511 // Initialize _S_bin and its members.
512 void* __v = ::operator new(sizeof(_Bin_record) * _S_bin_size);
513 _S_bin = static_cast<_Bin_record*>(__v);
515 // If __gthread_active_p() create and initialize the list of
516 // free thread ids. Single threaded applications use thread id 0
517 // directly and have no need for this.
519 if (__gthread_active_p())
521 const size_t __k = sizeof(_Thread_record) * _S_options._M_max_threads;
522 __v = ::operator new(__k);
523 _S_thread_freelist_first = static_cast<_Thread_record*>(__v);
525 // NOTE! The first assignable thread id is 1 since the
526 // global pool uses id 0
528 for (__i = 1; __i < _S_options._M_max_threads; ++__i)
530 _Thread_record& __tr = _S_thread_freelist_first[__i - 1];
531 __tr._M_next = &_S_thread_freelist_first[__i];
536 _S_thread_freelist_first[__i - 1]._M_next = NULL;
537 _S_thread_freelist_first[__i - 1]._M_id = __i;
539 // Make sure this is initialized.
540 #ifndef __GTHREAD_MUTEX_INIT
541 __GTHREAD_MUTEX_INIT_FUNCTION(&_S_thread_freelist_mutex);
543 // Initialize per thread key to hold pointer to
544 // _S_thread_freelist.
545 __gthread_key_create(&_S_thread_key, _S_destroy_thread_key);
547 const size_t __max_threads = _S_options._M_max_threads + 1;
548 for (size_t __n = 0; __n < _S_bin_size; ++__n)
550 _Bin_record& __bin = _S_bin[__n];
551 __v = ::operator new(sizeof(_Block_record*) * __max_threads);
552 __bin._M_first = static_cast<_Block_record**>(__v);
554 __v = ::operator new(sizeof(size_t) * __max_threads);
555 __bin._M_free = static_cast<size_t*>(__v);
557 __v = ::operator new(sizeof(size_t) * __max_threads);
558 __bin._M_used = static_cast<size_t*>(__v);
560 __v = ::operator new(sizeof(__gthread_mutex_t));
561 __bin._M_mutex = static_cast<__gthread_mutex_t*>(__v);
563 #ifdef __GTHREAD_MUTEX_INIT
565 // Do not copy a POSIX/gthr mutex once in use.
566 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
567 *__bin._M_mutex = __tmp;
570 { __GTHREAD_MUTEX_INIT_FUNCTION(__bin._M_mutex); }
573 for (size_t __threadn = 0; __threadn < __max_threads;
576 __bin._M_first[__threadn] = NULL;
577 __bin._M_free[__threadn] = 0;
578 __bin._M_used[__threadn] = 0;
584 for (size_t __n = 0; __n < _S_bin_size; ++__n)
586 _Bin_record& __bin = _S_bin[__n];
587 __v = ::operator new(sizeof(_Block_record*));
588 __bin._M_first = static_cast<_Block_record**>(__v);
589 __bin._M_first[0] = NULL;
595 template<typename _Tp>
601 // If we have thread support and it's active we check the thread
602 // key value and return its id or if it's not set we take the
603 // first record from _S_thread_freelist and sets the key and
605 if (__gthread_active_p())
607 _Thread_record* __freelist_pos =
608 static_cast<_Thread_record*>(__gthread_getspecific(_S_thread_key));
609 if (__freelist_pos == NULL)
611 // Since _S_options._M_max_threads must be larger than
612 // the theoretical max number of threads of the OS the
613 // list can never be empty.
614 __gthread_mutex_lock(&_S_thread_freelist_mutex);
615 __freelist_pos = _S_thread_freelist_first;
616 _S_thread_freelist_first = _S_thread_freelist_first->_M_next;
617 __gthread_mutex_unlock(&_S_thread_freelist_mutex);
619 __gthread_setspecific(_S_thread_key,
620 static_cast<void*>(__freelist_pos));
622 return __freelist_pos->_M_id;
625 // Otherwise (no thread support or inactive) all requests are
626 // served from the global pool 0.
631 template<typename _Tp>
634 _S_destroy_thread_key(void* __freelist_pos)
636 // Return this thread id record to front of thread_freelist.
637 __gthread_mutex_lock(&_S_thread_freelist_mutex);
638 _Thread_record* __tr = static_cast<_Thread_record*>(__freelist_pos);
639 __tr->_M_next = _S_thread_freelist_first;
640 _S_thread_freelist_first = __tr;
641 __gthread_mutex_unlock(&_S_thread_freelist_mutex);
645 template<typename _Tp>
647 operator==(const __mt_alloc<_Tp>&, const __mt_alloc<_Tp>&)
650 template<typename _Tp>
652 operator!=(const __mt_alloc<_Tp>&, const __mt_alloc<_Tp>&)
655 template<typename _Tp>
656 bool __mt_alloc<_Tp>::_S_init = false;
658 template<typename _Tp>
659 typename __mt_alloc<_Tp>::_Tune __mt_alloc<_Tp>::_S_options;
661 template<typename _Tp>
662 typename __mt_alloc<_Tp>::_Binmap_type* __mt_alloc<_Tp>::_S_binmap;
664 template<typename _Tp>
665 typename __mt_alloc<_Tp>::_Bin_record* volatile __mt_alloc<_Tp>::_S_bin;
667 template<typename _Tp>
668 size_t __mt_alloc<_Tp>::_S_bin_size = 1;
670 // Actual initialization in _S_initialize().
672 template<typename _Tp>
673 __gthread_once_t __mt_alloc<_Tp>::_S_once = __GTHREAD_ONCE_INIT;
675 template<typename _Tp>
676 typename __mt_alloc<_Tp>::_Thread_record*
677 volatile __mt_alloc<_Tp>::_S_thread_freelist_first = NULL;
679 template<typename _Tp>
680 __gthread_key_t __mt_alloc<_Tp>::_S_thread_key;
682 template<typename _Tp>
684 #ifdef __GTHREAD_MUTEX_INIT
685 __mt_alloc<_Tp>::_S_thread_freelist_mutex = __GTHREAD_MUTEX_INIT;
687 __mt_alloc<_Tp>::_S_thread_freelist_mutex;
690 } // namespace __gnu_cxx