1 // POSIX thread-related memory allocation -*- C++ -*-
3 // Copyright (C) 2001 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.
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
43 #ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H
44 #define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1
46 // Pthread-specific node allocator.
47 // This is similar to the default allocator, except that free-list
48 // information is kept separately for each thread, avoiding locking.
49 // This should be reasonably fast even in the presence of threads.
50 // The down side is that storage may not be well-utilized.
51 // It is not an error to allocate memory in thread A and deallocate
52 // it in thread B. But this effectively transfers ownership of the memory,
53 // so that it can only be reallocated by thread B. Thus this can effectively
54 // result in a storage leak if it's done on a regular basis.
55 // It can also result in frequent sharing of
56 // cache lines among processors, with potentially serious performance
59 #include <bits/c++config.h>
60 #include <bits/std_cerrno.h>
61 #include <bits/stl_alloc.h>
71 #define __STL_DATA_ALIGNMENT 8
73 union _Pthread_alloc_obj {
74 union _Pthread_alloc_obj * __free_list_link;
75 char __client_data[__STL_DATA_ALIGNMENT]; /* The client sees this. */
78 // Pthread allocators don't appear to the client to have meaningful
79 // instances. We do in fact need to associate some state with each
80 // thread. That state is represented by
81 // _Pthread_alloc_per_thread_state<_Max_size>.
83 template<size_t _Max_size>
84 struct _Pthread_alloc_per_thread_state {
85 typedef _Pthread_alloc_obj __obj;
86 enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT };
87 _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS];
88 _Pthread_alloc_per_thread_state<_Max_size> * __next;
89 // Free list link for list of available per thread structures.
90 // When one of these becomes available for reuse due to thread
91 // termination, any objects in its free list remain associated
92 // with it. The whole structure may then be used by a newly
94 _Pthread_alloc_per_thread_state() : __next(0)
96 memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
98 // Returns an object of size __n, and possibly adds to size n free list.
99 void *_M_refill(size_t __n);
102 // Pthread-specific allocator.
103 // The argument specifies the largest object size allocated from per-thread
104 // free lists. Larger objects are allocated using malloc_alloc.
105 // Max_size must be a power of 2.
106 template <size_t _Max_size = 128>
107 class _Pthread_alloc_template {
109 public: // but only for internal use:
111 typedef _Pthread_alloc_obj __obj;
113 // Allocates a chunk for nobjs of size size. nobjs may be reduced
114 // if it is inconvenient to allocate the requested number.
115 static char *_S_chunk_alloc(size_t __size, int &__nobjs);
117 enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
119 static size_t _S_round_up(size_t __bytes) {
120 return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
122 static size_t _S_freelist_index(size_t __bytes) {
123 return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
127 // Chunk allocation state. And other shared state.
128 // Protected by _S_chunk_allocator_lock.
129 static pthread_mutex_t _S_chunk_allocator_lock;
130 static char *_S_start_free;
131 static char *_S_end_free;
132 static size_t _S_heap_size;
133 static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states;
134 static pthread_key_t _S_key;
135 static bool _S_key_initialized;
136 // Pthread key under which per thread state is stored.
137 // Allocator instances that are currently unclaimed by any thread.
138 static void _S_destructor(void *instance);
139 // Function to be called on thread exit to reclaim per thread
141 static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();
142 // Return a recycled or new per thread state.
143 static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();
144 // ensure that the current thread has an associated
147 friend class _M_lock;
150 _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
151 ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
157 static void * allocate(size_t __n)
159 __obj * volatile * __my_free_list;
160 __obj * __RESTRICT __result;
161 _Pthread_alloc_per_thread_state<_Max_size>* __a;
163 if (__n > _Max_size) {
164 return(malloc_alloc::allocate(__n));
166 if (!_S_key_initialized ||
167 !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*)
168 pthread_getspecific(_S_key))) {
169 __a = _S_get_per_thread_state();
171 __my_free_list = __a -> __free_list + _S_freelist_index(__n);
172 __result = *__my_free_list;
174 void *__r = __a -> _M_refill(_S_round_up(__n));
177 *__my_free_list = __result -> __free_list_link;
182 static void deallocate(void *__p, size_t __n)
184 __obj *__q = (__obj *)__p;
185 __obj * volatile * __my_free_list;
186 _Pthread_alloc_per_thread_state<_Max_size>* __a;
188 if (__n > _Max_size) {
189 malloc_alloc::deallocate(__p, __n);
192 if (!_S_key_initialized ||
193 !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *)
194 pthread_getspecific(_S_key))) {
195 __a = _S_get_per_thread_state();
197 __my_free_list = __a->__free_list + _S_freelist_index(__n);
198 __q -> __free_list_link = *__my_free_list;
199 *__my_free_list = __q;
202 static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
206 typedef _Pthread_alloc_template<> pthread_alloc;
209 template <size_t _Max_size>
210 void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
212 _M_lock __lock_instance; // Need to acquire lock here.
213 _Pthread_alloc_per_thread_state<_Max_size>* __s =
214 (_Pthread_alloc_per_thread_state<_Max_size> *)__instance;
215 __s -> __next = _S_free_per_thread_states;
216 _S_free_per_thread_states = __s;
219 template <size_t _Max_size>
220 _Pthread_alloc_per_thread_state<_Max_size> *
221 _Pthread_alloc_template<_Max_size>::_S_new_per_thread_state()
223 /* lock already held here. */
224 if (0 != _S_free_per_thread_states) {
225 _Pthread_alloc_per_thread_state<_Max_size> *__result =
226 _S_free_per_thread_states;
227 _S_free_per_thread_states = _S_free_per_thread_states -> __next;
230 return new _Pthread_alloc_per_thread_state<_Max_size>;
234 template <size_t _Max_size>
235 _Pthread_alloc_per_thread_state<_Max_size> *
236 _Pthread_alloc_template<_Max_size>::_S_get_per_thread_state()
239 _M_lock __lock_instance; // Need to acquire lock here.
241 _Pthread_alloc_per_thread_state<_Max_size> * __result;
242 if (!_S_key_initialized) {
243 if (pthread_key_create(&_S_key, _S_destructor)) {
244 std::__throw_bad_alloc(); // defined in funcexcept.h
246 _S_key_initialized = true;
248 __result = _S_new_per_thread_state();
249 __ret_code = pthread_setspecific(_S_key, __result);
251 if (__ret_code == ENOMEM) {
252 std::__throw_bad_alloc();
261 /* We allocate memory in large chunks in order to avoid fragmenting */
262 /* the malloc heap too much. */
263 /* We assume that size is properly aligned. */
264 template <size_t _Max_size>
265 char *_Pthread_alloc_template<_Max_size>
266 ::_S_chunk_alloc(size_t __size, int &__nobjs)
270 size_t __total_bytes;
273 _M_lock __lock_instance; // Acquire lock for this routine
275 __total_bytes = __size * __nobjs;
276 __bytes_left = _S_end_free - _S_start_free;
277 if (__bytes_left >= __total_bytes) {
278 __result = _S_start_free;
279 _S_start_free += __total_bytes;
281 } else if (__bytes_left >= __size) {
282 __nobjs = __bytes_left/__size;
283 __total_bytes = __size * __nobjs;
284 __result = _S_start_free;
285 _S_start_free += __total_bytes;
288 size_t __bytes_to_get =
289 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
290 // Try to make use of the left-over piece.
291 if (__bytes_left > 0) {
292 _Pthread_alloc_per_thread_state<_Max_size>* __a =
293 (_Pthread_alloc_per_thread_state<_Max_size>*)
294 pthread_getspecific(_S_key);
295 __obj * volatile * __my_free_list =
296 __a->__free_list + _S_freelist_index(__bytes_left);
298 ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
299 *__my_free_list = (__obj *)_S_start_free;
302 // Try to get memory that's aligned on something like a
303 // cache line boundary, so as to avoid parceling out
304 // parts of the same line to different threads and thus
305 // possibly different processors.
307 const int __cache_line_size = 128; // probable upper bound
308 __bytes_to_get &= ~(__cache_line_size-1);
309 _S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get);
310 if (0 == _S_start_free) {
311 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
314 # else /* !SGI_SOURCE */
315 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
317 _S_heap_size += __bytes_to_get;
318 _S_end_free = _S_start_free + __bytes_to_get;
321 // lock is released here
322 return(_S_chunk_alloc(__size, __nobjs));
326 /* Returns an object of size n, and optionally adds to size n free list.*/
327 /* We assume that n is properly aligned. */
328 /* We hold the allocation lock. */
329 template <size_t _Max_size>
330 void *_Pthread_alloc_per_thread_state<_Max_size>
331 ::_M_refill(size_t __n)
335 _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
336 __obj * volatile * __my_free_list;
338 __obj * __current_obj, * __next_obj;
344 __my_free_list = __free_list
345 + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
347 /* Build free list in chunk */
348 __result = (__obj *)__chunk;
349 *__my_free_list = __next_obj = (__obj *)(__chunk + __n);
350 for (__i = 1; ; __i++) {
351 __current_obj = __next_obj;
352 __next_obj = (__obj *)((char *)__next_obj + __n);
353 if (__nobjs - 1 == __i) {
354 __current_obj -> __free_list_link = 0;
357 __current_obj -> __free_list_link = __next_obj;
363 template <size_t _Max_size>
364 void *_Pthread_alloc_template<_Max_size>
365 ::reallocate(void *__p, size_t __old_sz, size_t __new_sz)
370 if (__old_sz > _Max_size
371 && __new_sz > _Max_size) {
372 return(realloc(__p, __new_sz));
374 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
375 __result = allocate(__new_sz);
376 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
377 memcpy(__result, __p, __copy_sz);
378 deallocate(__p, __old_sz);
382 template <size_t _Max_size>
383 _Pthread_alloc_per_thread_state<_Max_size> *
384 _Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0;
386 template <size_t _Max_size>
387 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
389 template <size_t _Max_size>
390 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
392 template <size_t _Max_size>
393 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
394 = PTHREAD_MUTEX_INITIALIZER;
396 template <size_t _Max_size>
397 char *_Pthread_alloc_template<_Max_size>
400 template <size_t _Max_size>
401 char *_Pthread_alloc_template<_Max_size>
404 template <size_t _Max_size>
405 size_t _Pthread_alloc_template<_Max_size>
410 class pthread_allocator {
411 typedef pthread_alloc _S_Alloc; // The underlying allocator.
413 typedef size_t size_type;
414 typedef ptrdiff_t difference_type;
415 typedef _Tp* pointer;
416 typedef const _Tp* const_pointer;
417 typedef _Tp& reference;
418 typedef const _Tp& const_reference;
419 typedef _Tp value_type;
421 template <class _NewType> struct rebind {
422 typedef pthread_allocator<_NewType> other;
425 pthread_allocator() __STL_NOTHROW {}
426 pthread_allocator(const pthread_allocator& a) __STL_NOTHROW {}
427 template <class _OtherType>
428 pthread_allocator(const pthread_allocator<_OtherType>&)
430 ~pthread_allocator() __STL_NOTHROW {}
432 pointer address(reference __x) const { return &__x; }
433 const_pointer address(const_reference __x) const { return &__x; }
435 // __n is permitted to be 0. The C++ standard says nothing about what
436 // the return value is when __n == 0.
437 _Tp* allocate(size_type __n, const void* = 0) {
438 return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp)))
442 // p is not permitted to be a null pointer.
443 void deallocate(pointer __p, size_type __n)
444 { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }
446 size_type max_size() const __STL_NOTHROW
447 { return size_t(-1) / sizeof(_Tp); }
449 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
450 void destroy(pointer _p) { _p->~_Tp(); }
454 class pthread_allocator<void> {
456 typedef size_t size_type;
457 typedef ptrdiff_t difference_type;
458 typedef void* pointer;
459 typedef const void* const_pointer;
460 typedef void value_type;
462 template <class _NewType> struct rebind {
463 typedef pthread_allocator<_NewType> other;
467 template <size_t _Max_size>
468 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
469 const _Pthread_alloc_template<_Max_size>&)
474 template <class _T1, class _T2>
475 inline bool operator==(const pthread_allocator<_T1>&,
476 const pthread_allocator<_T2>& a2)
481 template <class _T1, class _T2>
482 inline bool operator!=(const pthread_allocator<_T1>&,
483 const pthread_allocator<_T2>&)
488 template <class _Tp, size_t _Max_size>
489 struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
491 static const bool _S_instanceless = true;
492 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type;
493 typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> >
497 template <class _Tp, class _Atype, size_t _Max>
498 struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
500 static const bool _S_instanceless = true;
501 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type;
502 typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type;
505 template <class _Tp, class _Atype>
506 struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
508 static const bool _S_instanceless = true;
509 typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
510 typedef pthread_allocator<_Tp> allocator_type;
516 #endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */