1 // MT-optimized allocator -*- C++ -*-
3 // Copyright (C) 2003 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
41 #include <bits/functexcept.h>
42 #include <bits/gthr.h>
43 #include <bits/atomicity.h>
48 * This is a fixed size (power of 2) allocator which - when
49 * compiled with thread support - will maintain one freelist per
50 * size per thread plus a "global" one. Steps are taken to limit
51 * the per thread freelist sizes (by returning excess back to
56 * vector<int, __gnu_cxx::__mt_alloc<int> > v1;
58 * typedef __gnu_cxx::__mt_alloc<char> > string_allocator;
59 * std::basic_string<char, std::char_traits<char>, string_allocator> s1;
62 template<typename _Tp
>
66 typedef size_t size_type
;
67 typedef ptrdiff_t difference_type
;
69 typedef const _Tp
* const_pointer
;
70 typedef _Tp
& reference
;
71 typedef const _Tp
& const_reference
;
72 typedef _Tp value_type
;
74 template<typename _Tp1
>
76 { typedef __mt_alloc
<_Tp1
> other
; };
83 __mt_alloc(const __mt_alloc
&) throw()
88 template<typename _Tp1
>
89 __mt_alloc(const __mt_alloc
<_Tp1
>&) throw()
94 ~__mt_alloc() throw() { }
97 address(reference __x
) const { return &__x
; }
100 address(const_reference __x
) const { return &__x
; }
103 max_size() const throw()
104 { return size_t(-1) / sizeof(_Tp
); }
106 // _GLIBCXX_RESOLVE_LIB_DEFECTS
107 // 402. wrong new expression in [some_] allocator::construct
109 construct(pointer __p
, const _Tp
& __val
)
110 { ::new(__p
) _Tp(__val
); }
113 destroy(pointer __p
) { __p
->~_Tp(); }
117 * We need to create the initial lists and set up some variables
118 * before we can answer to the first request for memory.
119 * The initialization of these variables is done at file scope
120 * below class declaration.
123 static __gthread_once_t _S_once_mt
;
125 static bool _S_initialized
;
128 * Using short int as type for the binmap implies we are never caching
129 * blocks larger than 65535 with this allocator
131 typedef unsigned short int binmap_type
;
132 static binmap_type
* _S_binmap
;
134 static void _S_init();
137 * Variables used to "tune" the behavior of the allocator, assigned
138 * and explained in detail below.
140 static size_t _S_max_bytes
;
141 static size_t _S_chunk_size
;
142 static size_t _S_max_threads
;
143 static size_t _S_no_of_bins
;
144 static size_t _S_freelist_headroom
;
147 * Each requesting thread is assigned an id ranging from 1 to
148 * _S_max_threads. Thread id 0 is used as a global memory pool.
149 * In order to get constant performance on the thread assignment
150 * routine, we keep a list of free ids. When a thread first requests
151 * memory we remove the first record in this list and stores the address
152 * in a __gthread_key. When initializing the __gthread_key
153 * we specify a destructor. When this destructor (i.e. the thread dies)
154 * is called, we return the thread id to the back of this list.
160 * Points to next free thread id record. NULL if last record in list.
165 * Thread id ranging from 1 to _S_max_threads.
170 static thread_record
* _S_thread_freelist_first
;
171 static thread_record
* _S_thread_freelist_last
;
172 static __gthread_mutex_t _S_thread_freelist_mutex
;
173 static void _S_thread_key_destr(void* freelist_pos
);
174 static __gthread_key_t _S_thread_key
;
175 static size_t _S_get_thread_id();
181 * Points to the next block_record for its thread_id.
186 * The thread id of the thread which has requested this block.
187 * All blocks are initially "owned" by global pool thread id 0.
195 * An "array" of pointers to the first/last free block for each
196 * thread id. Memory to these "arrays" is allocated in _S_init()
197 * for _S_max_threads + global pool 0.
199 block_record
** first
;
203 * An "array" of counters used to keep track of the amount of blocks
204 * that are on the freelist/used for each thread id.
205 * Memory to these "arrays" is allocated in _S_init()
206 * for _S_max_threads + global pool 0.
212 * Each bin has its own mutex which is used to ensure data integrity
213 * while changing "ownership" on a block.
214 * The mutex is initialized in _S_init().
217 __gthread_mutex_t
* mutex
;
222 * An "array" of bin_records each of which represents a specific
223 * power of 2 size. Memory to this "array" is allocated in _S_init().
225 static bin_record
* _S_bin
;
229 allocate(size_t __n
, std::allocator
<void>::const_pointer __h
= 0)
232 * Requests larger than _S_max_bytes are handled by
233 * new/delete directly
235 if (__n
> _S_max_bytes
)
237 void* __ret
= malloc(__n
* sizeof(_Tp
));
240 return static_cast<_Tp
*>(__ret
);
244 * Although the test in __gthread_once() would suffice, we
245 * wrap test of the once condition in our own unlocked
246 * check. This saves one function call to pthread_once()
247 * (which itself only tests for the once value unlocked anyway
248 * and immediately returns if set)
253 if (__gthread_active_p())
254 __gthread_once(&_S_once_mt
, _S_init
);
264 * Round up to power of 2 and figure out which bin to use
266 size_t bin
= _S_binmap
[__n
];
269 size_t thread_id
= _S_get_thread_id();
271 size_t thread_id
= 0;
277 * Find out if we have blocks on our freelist.
278 * If so, go ahead and use them directly without
279 * having to lock anything.
281 if (_S_bin
[bin
].first
[thread_id
] == NULL
)
284 * Are we using threads?
285 * - Yes, lock and check if there are free blocks on the global
286 * list (and if not add new ones), get the first one
288 * - No, all operations are made directly to global pool 0
289 * no need to lock or change ownership but check for free
290 * blocks on global list (and if not add new ones) and
294 if (__gthread_active_p())
296 __gthread_mutex_lock(_S_bin
[bin
].mutex
);
298 if (_S_bin
[bin
].first
[0] == NULL
)
300 _S_bin
[bin
].first
[0] =
301 (block_record
*)malloc(_S_chunk_size
);
303 if (!_S_bin
[bin
].first
[0])
305 __gthread_mutex_unlock(_S_bin
[bin
].mutex
);
309 size_t bin_t
= 1 << bin
;
311 _S_chunk_size
/(bin_t
+ sizeof(block_record
));
313 _S_bin
[bin
].free
[0] = block_count
;
316 block
= _S_bin
[bin
].first
[0];
318 while (block_count
> 0)
320 block
->next
= (block_record
*)((char*)block
+
321 (bin_t
+ sizeof(block_record
)));
327 _S_bin
[bin
].last
[0] = block
;
330 block
= _S_bin
[bin
].first
[0];
333 * Remove from list and count down the available counter on
336 _S_bin
[bin
].first
[0] = _S_bin
[bin
].first
[0]->next
;
337 _S_bin
[bin
].free
[0]--;
339 __gthread_mutex_unlock(_S_bin
[bin
].mutex
);
342 * Now that we have removed the block from the global
343 * freelist we can change owner and update the used
344 * counter for this thread without locking.
346 block
->thread_id
= thread_id
;
347 _S_bin
[bin
].used
[thread_id
]++;
352 _S_bin
[bin
].first
[0] = (block_record
*)malloc(_S_chunk_size
);
354 if (!_S_bin
[bin
].first
[0])
357 size_t bin_t
= 1 << bin
;
359 _S_chunk_size
/ (bin_t
+ sizeof(block_record
));
361 _S_bin
[bin
].free
[0] = block_count
;
364 block
= _S_bin
[bin
].first
[0];
366 while (block_count
> 0)
368 block
->next
= (block_record
*)((char*)block
+
369 (bin_t
+ sizeof(block_record
)));
375 _S_bin
[bin
].last
[0] = block
;
377 block
= _S_bin
[bin
].first
[0];
380 * Remove from list and count down the available counter on
381 * global pool 0 and increase it's used counter.
383 _S_bin
[bin
].first
[0] = _S_bin
[bin
].first
[0]->next
;
384 _S_bin
[bin
].free
[0]--;
385 _S_bin
[bin
].used
[0]++;
391 * "Default" operation - we have blocks on our own freelist
392 * grab the first record and update the counters.
394 block
= _S_bin
[bin
].first
[thread_id
];
396 _S_bin
[bin
].first
[thread_id
] = _S_bin
[bin
].first
[thread_id
]->next
;
397 _S_bin
[bin
].free
[thread_id
]--;
398 _S_bin
[bin
].used
[thread_id
]++;
401 return static_cast<_Tp
*>(static_cast<void*>((char*)block
+ sizeof(block_record
)));
405 deallocate(pointer __p
, size_type __n
)
408 * Requests larger than _S_max_bytes are handled by
409 * malloc/free directly
411 if (__n
> _S_max_bytes
)
418 * Round up to power of 2 and figure out which bin to use
420 size_t bin
= _S_binmap
[__n
];
423 size_t thread_id
= _S_get_thread_id();
425 size_t thread_id
= 0;
428 block_record
* block
= (block_record
*)((char*)__p
429 - sizeof(block_record
));
432 * This block will always be at the back of a list and thus
433 * we set its next pointer to NULL.
438 if (__gthread_active_p())
441 * Calculate the number of records to remove from our freelist
443 int remove
= _S_bin
[bin
].free
[thread_id
] -
444 (_S_bin
[bin
].used
[thread_id
] / _S_freelist_headroom
);
447 * The calculation above will almost always tell us to
448 * remove one or two records at a time, but this creates
449 * too much contention when locking and therefore we
450 * wait until the number of records is "high enough".
452 if (remove
> (int)(100 * (_S_no_of_bins
- bin
)) &&
453 remove
> (int)(_S_bin
[bin
].free
[thread_id
] /
454 _S_freelist_headroom
))
456 __gthread_mutex_lock(_S_bin
[bin
].mutex
);
460 if (_S_bin
[bin
].first
[0] == NULL
)
461 _S_bin
[bin
].first
[0] = _S_bin
[bin
].first
[thread_id
];
463 _S_bin
[bin
].last
[0]->next
= _S_bin
[bin
].first
[thread_id
];
465 _S_bin
[bin
].last
[0] = _S_bin
[bin
].first
[thread_id
];
467 _S_bin
[bin
].first
[thread_id
] =
468 _S_bin
[bin
].first
[thread_id
]->next
;
470 _S_bin
[bin
].free
[0]++;
471 _S_bin
[bin
].free
[thread_id
]--;
476 _S_bin
[bin
].last
[0]->next
= NULL
;
478 __gthread_mutex_unlock(_S_bin
[bin
].mutex
);
482 * Did we allocate this block?
483 * - Yes, return it to our freelist
484 * - No, return it to global pool
486 if (thread_id
== block
->thread_id
)
488 if (_S_bin
[bin
].first
[thread_id
] == NULL
)
489 _S_bin
[bin
].first
[thread_id
] = block
;
491 _S_bin
[bin
].last
[thread_id
]->next
= block
;
493 _S_bin
[bin
].last
[thread_id
] = block
;
495 _S_bin
[bin
].free
[thread_id
]++;
496 _S_bin
[bin
].used
[thread_id
]--;
500 __gthread_mutex_lock(_S_bin
[bin
].mutex
);
502 if (_S_bin
[bin
].first
[0] == NULL
)
503 _S_bin
[bin
].first
[0] = block
;
505 _S_bin
[bin
].last
[0]->next
= block
;
507 _S_bin
[bin
].last
[0] = block
;
509 _S_bin
[bin
].free
[0]++;
510 _S_bin
[bin
].used
[block
->thread_id
]--;
512 __gthread_mutex_unlock(_S_bin
[bin
].mutex
);
519 * Single threaded application - return to global pool
521 if (_S_bin
[bin
].first
[0] == NULL
)
522 _S_bin
[bin
].first
[0] = block
;
524 _S_bin
[bin
].last
[0]->next
= block
;
526 _S_bin
[bin
].last
[0] = block
;
528 _S_bin
[bin
].free
[0]++;
529 _S_bin
[bin
].used
[0]--;
534 template<typename _Tp
>
540 * Calculate the number of bins required based on _S_max_bytes,
541 * _S_no_of_bins is initialized to 1 below.
545 while (_S_max_bytes
> bin_t
)
553 * Setup the bin map for quick lookup of the relevant bin
555 _S_binmap
= (binmap_type
*)
556 malloc ((_S_max_bytes
+ 1) * sizeof(binmap_type
));
561 binmap_type
* bp_t
= _S_binmap
;
562 binmap_type bin_max_t
= 1;
563 binmap_type bin_t
= 0;
564 for (binmap_type ct
= 0; ct
<= _S_max_bytes
; ct
++)
575 * If __gthread_active_p() create and initialize the list of
576 * free thread ids. Single threaded applications use thread id 0
577 * directly and have no need for this.
580 if (__gthread_active_p())
582 _S_thread_freelist_first
=
583 (thread_record
*)malloc(sizeof(thread_record
) * _S_max_threads
);
585 if (!_S_thread_freelist_first
)
589 * NOTE! The first assignable thread id is 1 since the global
593 for (i
= 1; i
< _S_max_threads
; i
++)
595 _S_thread_freelist_first
[i
- 1].next
=
596 &_S_thread_freelist_first
[i
];
598 _S_thread_freelist_first
[i
- 1].id
= i
;
602 * Set last record and pointer to this
604 _S_thread_freelist_first
[i
- 1].next
= NULL
;
605 _S_thread_freelist_first
[i
- 1].id
= i
;
606 _S_thread_freelist_last
= &_S_thread_freelist_first
[i
- 1];
609 * Initialize per thread key to hold pointer to
610 * _S_thread_freelist NOTE! Here's an ugly workaround - if
611 * _S_thread_key_destr is not explicitly called at least
612 * once it won't be linked into the application. This is the
613 * behavior of template methods and __gthread_key_create()
614 * takes only a pointer to the function and does not cause
615 * the compiler to create an instance.
617 _S_thread_key_destr(NULL
);
618 __gthread_key_create(&_S_thread_key
, _S_thread_key_destr
);
623 * Initialize _S_bin and its members
625 _S_bin
= (bin_record
*)malloc(sizeof(bin_record
) * _S_no_of_bins
);
630 for (size_t bin
= 0; bin
< _S_no_of_bins
; bin
++)
632 std::size_t __n
= _S_max_threads
+ 1;
634 _S_bin
[bin
].first
= (block_record
**)
635 malloc(sizeof(block_record
*) * __n
);
637 if (!_S_bin
[bin
].first
)
640 _S_bin
[bin
].last
= (block_record
**)
641 malloc(sizeof(block_record
*) * __n
);
643 if (!_S_bin
[bin
].last
)
646 _S_bin
[bin
].free
= (size_t*) malloc(sizeof(size_t) * __n
);
648 if (!_S_bin
[bin
].free
)
651 _S_bin
[bin
].used
= (size_t*) malloc(sizeof(size_t) * __n
);
653 if (!_S_bin
[bin
].used
)
657 _S_bin
[bin
].mutex
=(__gthread_mutex_t
*) malloc(sizeof(__gthread_mutex_t
));
659 #ifdef __GTHREAD_MUTEX_INIT
661 // Do not copy a POSIX/gthr mutex once in use.
662 __gthread_mutex_t __tmp
= __GTHREAD_MUTEX_INIT
;
663 *_S_bin
[bin
].mutex
= __tmp
;
666 { __GTHREAD_MUTEX_INIT_FUNCTION (_S_bin
[bin
].mutex
); }
670 for (size_t thread
= 0; thread
<= _S_max_threads
; thread
++)
672 _S_bin
[bin
].first
[thread
] = NULL
;
673 _S_bin
[bin
].last
[thread
] = NULL
;
674 _S_bin
[bin
].free
[thread
] = 0;
675 _S_bin
[bin
].used
[thread
] = 0;
679 _S_initialized
= true;
683 template<typename _Tp
>
686 _S_thread_key_destr(void* freelist_pos
)
689 * If the thread - when it dies - still has records on its
690 * freelist we return them to the global pool here.
692 for (size_t bin
= 0; bin
< _S_no_of_bins
; bin
++)
694 block_record
* block
=
695 _S_bin
[bin
].first
[((thread_record
*)freelist_pos
)->id
];
699 __gthread_mutex_lock(_S_bin
[bin
].mutex
);
700 while (block
!= NULL
)
702 if (_S_bin
[bin
].first
[0] == NULL
)
703 _S_bin
[bin
].first
[0] = block
;
705 _S_bin
[bin
].last
[0]->next
= block
;
707 _S_bin
[bin
].last
[0] = block
;
709 _S_bin
[bin
].free
[0]++;
712 _S_bin
[bin
].last
[0]->next
= NULL
;
713 __gthread_mutex_unlock(_S_bin
[bin
].mutex
);
718 * Return this thread id record to thread_freelist
720 __gthread_mutex_lock(&_S_thread_freelist_mutex
);
721 _S_thread_freelist_last
->next
= (thread_record
*)freelist_pos
;
722 _S_thread_freelist_last
= (thread_record
*)freelist_pos
;
723 _S_thread_freelist_last
->next
= NULL
;
724 __gthread_mutex_unlock(&_S_thread_freelist_mutex
);
727 template<typename _Tp
>
733 * If we have thread support and it's active we check the thread
734 * key value and return it's id or if it's not set we take the
735 * first record from _S_thread_freelist and sets the key and
738 if (__gthread_active_p())
740 thread_record
* freelist_pos
;
743 (thread_record
*)__gthread_getspecific(_S_thread_key
)) == NULL
)
746 * Since _S_max_threads must be larger than the
747 * theoretical max number of threads of the OS the list
748 * can never be empty.
750 __gthread_mutex_lock(&_S_thread_freelist_mutex
);
751 freelist_pos
= _S_thread_freelist_first
;
752 _S_thread_freelist_first
= _S_thread_freelist_first
->next
;
753 __gthread_mutex_unlock(&_S_thread_freelist_mutex
);
755 __gthread_setspecific(_S_thread_key
, (void*)freelist_pos
);
758 * Since thread_ids may/will be reused (espcially in
759 * producer/consumer applications) we make sure that the
760 * list pointers and free counter is reset BUT as the
761 * "old" thread may still be owner of some memory (which
762 * is referred to by other threads and thus not freed)
763 * we don't reset the used counter.
765 for (size_t bin
= 0; bin
< _S_no_of_bins
; bin
++)
767 _S_bin
[bin
].first
[freelist_pos
->id
] = NULL
;
768 _S_bin
[bin
].last
[freelist_pos
->id
] = NULL
;
769 _S_bin
[bin
].free
[freelist_pos
->id
] = 0;
773 return freelist_pos
->id
;
777 * Otherwise (no thread support or inactive) all requests are
778 * served from the global pool 0.
783 template<typename _Tp
> __gthread_once_t
784 __mt_alloc
<_Tp
>::_S_once_mt
= __GTHREAD_ONCE_INIT
;
787 template<typename _Tp
> bool
788 __mt_alloc
<_Tp
>::_S_initialized
= false;
790 template<typename _Tp
> typename __mt_alloc
<_Tp
>::binmap_type
*
791 __mt_alloc
<_Tp
>::_S_binmap
= NULL
;
794 * Allocation requests (after round-up to power of 2) below this
795 * value will be handled by the allocator. A raw malloc/free() call
796 * will be used for requests larger than this value.
798 template<typename _Tp
> size_t
799 __mt_alloc
<_Tp
>::_S_max_bytes
= 128;
802 * In order to avoid fragmenting and minimize the number of malloc()
803 * calls we always request new memory using this value. Based on
804 * previous discussions on the libstdc++ mailing list we have
805 * choosen the value below. See
806 * http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
808 template<typename _Tp
> size_t
809 __mt_alloc
<_Tp
>::_S_chunk_size
= 4096 - 4 * sizeof(void*);
812 * The maximum number of supported threads. Our Linux 2.4.18 reports
813 * 4070 in /proc/sys/kernel/threads-max
815 template<typename _Tp
> size_t
816 __mt_alloc
<_Tp
>::_S_max_threads
= 4096;
819 * Actual value calculated in _S_init()
821 template<typename _Tp
> size_t
822 __mt_alloc
<_Tp
>::_S_no_of_bins
= 1;
825 * Each time a deallocation occurs in a threaded application we make
826 * sure that there are no more than _S_freelist_headroom % of used
827 * memory on the freelist. If the number of additional records is
828 * more than _S_freelist_headroom % of the freelist, we move these
829 * records back to the global pool.
831 template<typename _Tp
> size_t
832 __mt_alloc
<_Tp
>::_S_freelist_headroom
= 10;
835 * Actual initialization in _S_init()
838 template<typename _Tp
> typename __mt_alloc
<_Tp
>::thread_record
*
839 __mt_alloc
<_Tp
>::_S_thread_freelist_first
= NULL
;
841 template<typename _Tp
> typename __mt_alloc
<_Tp
>::thread_record
*
842 __mt_alloc
<_Tp
>::_S_thread_freelist_last
= NULL
;
844 template<typename _Tp
> __gthread_mutex_t
845 __mt_alloc
<_Tp
>::_S_thread_freelist_mutex
= __GTHREAD_MUTEX_INIT
;
848 * Actual initialization in _S_init()
850 template<typename _Tp
> __gthread_key_t
851 __mt_alloc
<_Tp
>::_S_thread_key
;
854 template<typename _Tp
> typename __mt_alloc
<_Tp
>::bin_record
*
855 __mt_alloc
<_Tp
>::_S_bin
= NULL
;
856 } // namespace __gnu_cxx