OSDN Git Service

f377d4071c728b8d919161492b7f6038e90b3344
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / mt_allocator.h
1 // MT-optimized allocator -*- C++ -*-
2
3 // Copyright (C) 2003, 2004 Free Software Foundation, Inc.
4 //
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)
9 // any later version.
10
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.
15
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,
19 // USA.
20
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.
29
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.
33  */
34
35 #ifndef _MT_ALLOCATOR_H
36 #define _MT_ALLOCATOR_H 1
37
38 #include <new>
39 #include <cstdlib>
40 #include <bits/functexcept.h>
41 #include <bits/gthr.h>
42 #include <bits/atomicity.h>
43
44 namespace __gnu_cxx
45 {
46   /**
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
51    *  "global").
52    *
53    *  Further details:
54    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html
55    */
56   typedef void (*__destroy_handler)(void*);
57   typedef void (*__create_handler)(void);
58
59   struct __pool_base
60   {
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;
64
65     // Variables used to configure the behavior of the allocator,
66     // assigned and explained in detail below.
67     struct _Tune
68     {
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 };
76
77       // Alignment needed.
78       // NB: In any case must be >= sizeof(_Block_record), that
79       // is 4 on 32 bit machines and 8 on 64 bit machines.
80       size_t    _M_align;
81       
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.
85       size_t    _M_max_bytes; 
86       
87       // Size in bytes of the smallest bin.
88       // NB: Must be a power of 2 and >= _M_align.
89       size_t    _M_min_bin;
90       
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
96       size_t    _M_chunk_size;
97       
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
103       // 65534)
104       size_t    _M_max_threads;
105       
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;
113       
114       // Set to true forces all allocations to use new().
115       bool      _M_force_new; 
116       
117       explicit
118       _Tune()
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)
123       { }
124
125       explicit
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)
131       { }
132       
133       bool
134       is_default() const
135       {
136         bool __ret = true;
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;
143         return __ret;
144       }
145     };
146     
147     struct _Block_address
148     {
149       void*                     _M_initial;
150       _Block_address*           _M_next;
151     };
152     
153     const _Tune&
154     _M_get_options() const
155     { return _M_options; }
156
157     void
158     _M_set_options(_Tune __t)
159     { 
160       if (!_M_init)
161         _M_options = __t;
162     }
163
164     bool
165     _M_check_threshold(size_t __bytes)
166     { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }
167
168     size_t
169     _M_get_binmap(size_t __bytes)
170     { return _M_binmap[__bytes]; }
171
172     explicit __pool_base() 
173     : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { }
174
175   protected:
176     // Configuration options.
177     _Tune                       _M_options;
178     
179     _Binmap_type*               _M_binmap;
180
181     // We need to create the initial lists and set up some variables
182     // before we can answer to the first request for memory.
183     bool                        _M_init;
184   };
185
186   // Data describing the underlying memory pool, parameterized on
187   // threading support.
188   template<bool _Thread>
189     class __pool;
190
191   template<>
192     class __pool<true>;
193
194   template<>
195     class __pool<false>;
196
197
198 #ifdef __GTHREADS
199   // Specialization for thread enabled, via gthreads.h.
200   template<>
201     class __pool<true> : public __pool_base
202     {
203     public:
204       // Each requesting thread is assigned an id ranging from 1 to
205       // _S_max_threads. Thread id 0 is used as a global memory pool.
206       // In order to get constant performance on the thread assignment
207       // routine, we keep a list of free ids. When a thread first
208       // requests memory we remove the first record in this list and
209       // stores the address in a __gthread_key. When initializing the
210       // __gthread_key we specify a destructor. When this destructor
211       // (i.e. the thread dies) is called, we return the thread id to
212       // the front of this list.
213       struct _Thread_record
214       {
215         // Points to next free thread id record. NULL if last record in list.
216         _Thread_record* volatile        _M_next;
217         
218         // Thread id ranging from 1 to _S_max_threads.
219         size_t                          _M_id;
220       };
221       
222       union _Block_record
223       {
224         // Points to the block_record of the next free block.
225         _Block_record* volatile         _M_next;
226         
227         // The thread id of the thread which has requested this block.
228         size_t                          _M_thread_id;
229       };
230       
231       struct _Bin_record
232       {
233         // An "array" of pointers to the first free block for each
234         // thread id. Memory to this "array" is allocated in
235         // _S_initialize() for _S_max_threads + global pool 0.
236         _Block_record** volatile        _M_first;
237         
238         // A list of the initial addresses of all allocated blocks.
239         _Block_address*                 _M_address;
240
241         // An "array" of counters used to keep track of the amount of
242         // blocks that are on the freelist/used for each thread id.
243         // Memory to these "arrays" is allocated in _S_initialize() for
244         // _S_max_threads + global pool 0.
245         size_t* volatile                _M_free;
246         size_t* volatile                _M_used;
247         
248         // Each bin has its own mutex which is used to ensure data
249         // integrity while changing "ownership" on a block.  The mutex
250         // is initialized in _S_initialize().
251         __gthread_mutex_t*              _M_mutex;
252       };
253       
254       void
255       _M_initialize(__destroy_handler __d);
256
257       void
258       _M_initialize_once(__create_handler __c)
259       {
260         // Although the test in __gthread_once() would suffice, we
261         // wrap test of the once condition in our own unlocked
262         // check. This saves one function call to pthread_once()
263         // (which itself only tests for the once value unlocked anyway
264         // and immediately returns if set)
265         if (__builtin_expect(_M_init == false, false))
266           {
267             if (__gthread_active_p())
268               __gthread_once(&_M_once, __c);
269             if (!_M_init)
270               __c();
271           }
272       }
273
274       char* 
275       _M_reserve_block(size_t __bytes, const size_t __thread_id);
276     
277       void
278       _M_reclaim_block(char* __p, size_t __bytes);
279     
280       const _Bin_record&
281       _M_get_bin(size_t __which)
282       { return _M_bin[__which]; }
283       
284       void
285       _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block, 
286                          size_t __thread_id)
287       {
288         if (__gthread_active_p())
289           {
290             __block->_M_thread_id = __thread_id;
291             --__bin._M_free[__thread_id];
292             ++__bin._M_used[__thread_id];
293           }
294       }
295
296       void 
297       _M_destroy_thread_key(void* __freelist_pos);
298
299       size_t 
300       _M_get_thread_id();
301
302       explicit __pool() 
303       : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL) 
304       {
305         // On some platforms, __gthread_once_t is an aggregate.
306         __gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
307         _M_once = __tmp;
308       }
309
310       ~__pool();
311
312     private:
313       // An "array" of bin_records each of which represents a specific
314       // power of 2 size. Memory to this "array" is allocated in
315       // _M_initialize().
316       _Bin_record* volatile     _M_bin;
317
318       // Actual value calculated in _M_initialize().
319       size_t                    _M_bin_size;
320
321       __gthread_once_t          _M_once;
322       
323       _Thread_record*           _M_thread_freelist;
324       void*                     _M_thread_freelist_initial;
325     };
326 #endif
327
328   // Specialization for single thread.
329   template<>
330     class __pool<false> : public __pool_base
331     {
332     public:
333       union _Block_record
334       {
335         // Points to the block_record of the next free block.
336         _Block_record* volatile         _M_next;
337       };
338
339       struct _Bin_record
340       {
341         // An "array" of pointers to the first free block.
342         _Block_record** volatile        _M_first;
343
344         // A list of the initial addresses of all allocated blocks.
345         _Block_address*                 _M_address;
346       };
347       
348       void
349       _M_initialize_once()
350       {
351         if (__builtin_expect(_M_init == false, false))
352           _M_initialize();
353       }
354
355       char* 
356       _M_reserve_block(size_t __bytes, const size_t __thread_id);
357     
358       void
359       _M_reclaim_block(char* __p, size_t __bytes);
360     
361       size_t 
362       _M_get_thread_id() { return 0; }
363       
364       const _Bin_record&
365       _M_get_bin(size_t __which)
366       { return _M_bin[__which]; }
367       
368       void
369       _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
370       { }
371
372       explicit __pool() 
373       : _M_bin(NULL), _M_bin_size(1) { }
374
375       ~__pool();
376
377     private:
378       // An "array" of bin_records each of which represents a specific
379       // power of 2 size. Memory to this "array" is allocated in
380       // _M_initialize().
381       _Bin_record* volatile     _M_bin;
382       
383       // Actual value calculated in _M_initialize().
384       size_t                    _M_bin_size;     
385
386       void
387       _M_initialize();
388   };
389
390   template<bool _Thread>
391     struct __common_pool_policy 
392     {
393       typedef __pool<_Thread> __pool_type;
394
395       template<typename _Tp1, bool _Thread1 = _Thread>
396         struct _M_rebind;
397
398       template<typename _Tp1>
399         struct _M_rebind<_Tp1, true>
400         { typedef __common_pool_policy<true> other; };
401
402       template<typename _Tp1>
403         struct _M_rebind<_Tp1, false>
404         { typedef __common_pool_policy<false> other; };
405
406       static __pool_type&
407       _S_get_pool()
408       { 
409         static __pool_type _S_pool;
410         return _S_pool;
411       }
412
413       static void
414       _S_initialize_once() 
415       { 
416         static bool __init;
417         if (__builtin_expect(__init == false, false))
418           {
419             _S_get_pool()._M_initialize_once(); 
420             __init = true;
421           }
422       }
423     };
424
425   template<>
426     struct __common_pool_policy<true>;
427
428 #ifdef __GTHREADS
429   template<>
430     struct __common_pool_policy<true>
431     {
432       typedef __pool<true> __pool_type;
433
434       template<typename _Tp1, bool _Thread1 = true>
435         struct _M_rebind;
436
437       template<typename _Tp1>
438         struct _M_rebind<_Tp1, true>
439         { typedef __common_pool_policy<true> other; };
440
441       template<typename _Tp1>
442         struct _M_rebind<_Tp1, false>
443         { typedef __common_pool_policy<false> other; };
444
445       static __pool_type&
446       _S_get_pool()
447       { 
448         static __pool_type _S_pool;
449         return _S_pool;
450       }
451
452       static void
453       _S_destroy_thread_key(void* __freelist_pos)
454       { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
455       
456       static void
457       _S_initialize() 
458       { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
459
460       static void
461       _S_initialize_once() 
462       { 
463         static bool __init;
464         if (__builtin_expect(__init == false, false))
465           {
466             _S_get_pool()._M_initialize_once(_S_initialize); 
467             __init = true;
468           }
469       }
470    };
471 #endif
472
473
474   template<typename _Tp, bool _Thread>
475     struct __per_type_pool_policy
476     {
477       typedef __pool<_Thread> __pool_type;
478
479       template<typename _Tp1, bool _Thread1 = _Thread>
480         struct _M_rebind;
481
482       template<typename _Tp1>
483         struct _M_rebind<_Tp1, false>
484         { typedef __per_type_pool_policy<_Tp1, false> other; };
485
486       template<typename _Tp1>
487         struct _M_rebind<_Tp1, true>
488         { typedef __per_type_pool_policy<_Tp1, true> other; };
489
490       // Avoid static initialization ordering issues.
491       static __pool_type&
492       _S_get_pool() 
493       { 
494         static __pool_type _S_pool;
495         return _S_pool;
496       }
497
498       static void
499       _S_initialize_once() 
500       { 
501         static bool __init;
502         if (__builtin_expect(__init == false, false))
503           {
504             _S_get_pool()._M_initialize_once(); 
505             __init = true;
506           }
507       }
508     };
509
510   template<typename _Tp>
511     struct __per_type_pool_policy<_Tp, true>;
512
513 #ifdef __GTHREADS
514   template<typename _Tp>
515     struct __per_type_pool_policy<_Tp, true>
516     {
517       typedef __pool<true> __pool_type;
518
519       template<typename _Tp1, bool _Thread1 = true>
520         struct _M_rebind;
521
522       template<typename _Tp1>
523         struct _M_rebind<_Tp1, false>
524         { typedef __per_type_pool_policy<_Tp1, false> other; };
525
526       template<typename _Tp1>
527         struct _M_rebind<_Tp1, true>
528         { typedef __per_type_pool_policy<_Tp1, true> other; };
529
530       // Avoid static initialization ordering issues.
531       static __pool_type&
532       _S_get_pool( ) 
533       { 
534         static __pool_type _S_pool;
535         return _S_pool;
536       }
537
538       static void
539       _S_destroy_thread_key(void* __freelist_pos)
540       { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
541       
542       static void
543       _S_initialize() 
544       { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
545
546       static void
547       _S_initialize_once() 
548       { 
549         static bool __init;
550         if (__builtin_expect(__init == false, false))
551           {
552             _S_get_pool()._M_initialize_once(_S_initialize); 
553             __init = true;
554           }
555       }
556     };
557 #endif
558
559   template<typename _Tp>
560     class __mt_alloc_base 
561     {
562     public:
563       typedef size_t                    size_type;
564       typedef ptrdiff_t                 difference_type;
565       typedef _Tp*                      pointer;
566       typedef const _Tp*                const_pointer;
567       typedef _Tp&                      reference;
568       typedef const _Tp&                const_reference;
569       typedef _Tp                       value_type;
570
571       pointer
572       address(reference __x) const
573       { return &__x; }
574
575       const_pointer
576       address(const_reference __x) const
577       { return &__x; }
578
579       size_type
580       max_size() const throw() 
581       { return size_t(-1) / sizeof(_Tp); }
582
583       // _GLIBCXX_RESOLVE_LIB_DEFECTS
584       // 402. wrong new expression in [some_] allocator::construct
585       void 
586       construct(pointer __p, const _Tp& __val) 
587       { ::new(__p) _Tp(__val); }
588
589       void 
590       destroy(pointer __p) { __p->~_Tp(); }
591     };
592
593 #ifdef __GTHREADS
594 #define __default_policy __common_pool_policy<true>
595 #else
596 #define __default_policy __common_pool_policy<false>
597 #endif
598
599   template<typename _Tp, typename _Poolp = __default_policy>
600     class __mt_alloc : public __mt_alloc_base<_Tp>, _Poolp
601     {
602     public:
603       typedef size_t                    size_type;
604       typedef ptrdiff_t                 difference_type;
605       typedef _Tp*                      pointer;
606       typedef const _Tp*                const_pointer;
607       typedef _Tp&                      reference;
608       typedef const _Tp&                const_reference;
609       typedef _Tp                       value_type;
610       typedef _Poolp                    __policy_type;
611       typedef typename _Poolp::__pool_type       __pool_type;
612
613       template<typename _Tp1, typename _Poolp1 = _Poolp>
614         struct rebind
615         { 
616           typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
617           typedef __mt_alloc<_Tp1, pol_type> other;
618         };
619
620       // Create pool instance so that order of construction will be
621       // pool_type first, then allocator. This is necessary for
622       // correct global and static object construction/destruction.
623       __mt_alloc() throw() 
624       { __policy_type::_S_get_pool(); }
625
626       __mt_alloc(const __mt_alloc&) throw() 
627       { __policy_type::_S_get_pool(); }
628
629       template<typename _Tp1, typename _Poolp1>
630         __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>& obj) throw()  
631         { __policy_type::_S_get_pool(); }
632
633       ~__mt_alloc() throw() { }
634
635       pointer
636       allocate(size_type __n, const void* = 0);
637
638       void
639       deallocate(pointer __p, size_type __n);
640
641       const __pool_base::_Tune
642       _M_get_options()
643       { 
644         // Return a copy, not a reference, for external consumption.
645         return __pool_base::_Tune(this->_S_get_pool()._M_get_options()); 
646       }
647       
648       void
649       _M_set_options(__pool_base::_Tune __t)
650       { this->_S_get_pool()._M_set_options(__t); }
651     };
652
653   template<typename _Tp, typename _Poolp>
654     typename __mt_alloc<_Tp, _Poolp>::pointer
655     __mt_alloc<_Tp, _Poolp>::
656     allocate(size_type __n, const void*)
657     {
658       this->_S_initialize_once();
659
660       // Requests larger than _M_max_bytes are handled by new/delete
661       // directly.
662       __pool_type& __pool = this->_S_get_pool();
663       const size_t __bytes = __n * sizeof(_Tp);
664       if (__pool._M_check_threshold(__bytes))
665         {
666           void* __ret = ::operator new(__bytes);
667           return static_cast<_Tp*>(__ret);
668         }
669
670       // Round up to power of 2 and figure out which bin to use.
671       const size_t __which = __pool._M_get_binmap(__bytes);
672       const size_t __thread_id = __pool._M_get_thread_id();
673       
674       // Find out if we have blocks on our freelist.  If so, go ahead
675       // and use them directly without having to lock anything.
676       char* __c;
677       typedef typename __pool_type::_Bin_record _Bin_record;
678       const _Bin_record& __bin = __pool._M_get_bin(__which);
679       if (__bin._M_first[__thread_id])
680         {
681           // Already reserved.
682           typedef typename __pool_type::_Block_record _Block_record;
683           _Block_record* __block = __bin._M_first[__thread_id];
684           __bin._M_first[__thread_id] = __bin._M_first[__thread_id]->_M_next;
685           
686           __pool._M_adjust_freelist(__bin, __block, __thread_id);
687           const __pool_base::_Tune& __options = __pool._M_get_options();
688           __c = reinterpret_cast<char*>(__block) + __options._M_align;
689         }
690       else
691         {
692           // Null, reserve.
693           __c = __pool._M_reserve_block(__bytes, __thread_id);
694         }
695       return static_cast<_Tp*>(static_cast<void*>(__c));
696     }
697   
698   template<typename _Tp, typename _Poolp>
699     void
700     __mt_alloc<_Tp, _Poolp>::
701     deallocate(pointer __p, size_type __n)
702     {
703       // Requests larger than _M_max_bytes are handled by operators
704       // new/delete directly.
705       __pool_type& __pool = this->_S_get_pool();
706       const size_t __bytes = __n * sizeof(_Tp);
707       if (__pool._M_check_threshold(__bytes))
708         ::operator delete(__p);
709       else
710         __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes);
711     }
712   
713   template<typename _Tp, typename _Poolp>
714     inline bool
715     operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
716     { return true; }
717   
718   template<typename _Tp, typename _Poolp>
719     inline bool
720     operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
721     { return false; }
722
723 #undef __default_policy
724 } // namespace __gnu_cxx
725
726 #endif