3 * Silicon Graphics Computer Systems, Inc.
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation. Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose. It is provided "as is" without express or implied warranty.
14 #ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H
15 #define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1
17 // Pthread-specific node allocator.
18 // This is similar to the default allocator, except that free-list
19 // information is kept separately for each thread, avoiding locking.
20 // This should be reasonably fast even in the presence of threads.
21 // The down side is that storage may not be well-utilized.
22 // It is not an error to allocate memory in thread A and deallocate
23 // it in thread B. But this effectively transfers ownership of the memory,
24 // so that it can only be reallocated by thread B. Thus this can effectively
25 // result in a storage leak if it's done on a regular basis.
26 // It can also result in frequent sharing of
27 // cache lines among processors, with potentially serious performance
30 #include <bits/c++config.h>
31 #include <bits/std_cerrno.h>
32 #include <bits/stl_alloc.h>
37 #ifndef __STL_NO_BAD_ALLOC
43 #define __STL_DATA_ALIGNMENT 8
45 union _Pthread_alloc_obj {
46 union _Pthread_alloc_obj * __free_list_link;
47 char __client_data[__STL_DATA_ALIGNMENT]; /* The client sees this. */
50 // Pthread allocators don't appear to the client to have meaningful
51 // instances. We do in fact need to associate some state with each
52 // thread. That state is represented by
53 // _Pthread_alloc_per_thread_state<_Max_size>.
55 template<size_t _Max_size>
56 struct _Pthread_alloc_per_thread_state {
57 typedef _Pthread_alloc_obj __obj;
58 enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT };
59 _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS];
60 _Pthread_alloc_per_thread_state<_Max_size> * __next;
61 // Free list link for list of available per thread structures.
62 // When one of these becomes available for reuse due to thread
63 // termination, any objects in its free list remain associated
64 // with it. The whole structure may then be used by a newly
66 _Pthread_alloc_per_thread_state() : __next(0)
68 memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
70 // Returns an object of size __n, and possibly adds to size n free list.
71 void *_M_refill(size_t __n);
74 // Pthread-specific allocator.
75 // The argument specifies the largest object size allocated from per-thread
76 // free lists. Larger objects are allocated using malloc_alloc.
77 // Max_size must be a power of 2.
78 template <size_t _Max_size = 128>
79 class _Pthread_alloc_template {
81 public: // but only for internal use:
83 typedef _Pthread_alloc_obj __obj;
85 // Allocates a chunk for nobjs of size size. nobjs may be reduced
86 // if it is inconvenient to allocate the requested number.
87 static char *_S_chunk_alloc(size_t __size, int &__nobjs);
89 enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
91 static size_t _S_round_up(size_t __bytes) {
92 return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
94 static size_t _S_freelist_index(size_t __bytes) {
95 return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
99 // Chunk allocation state. And other shared state.
100 // Protected by _S_chunk_allocator_lock.
101 static pthread_mutex_t _S_chunk_allocator_lock;
102 static char *_S_start_free;
103 static char *_S_end_free;
104 static size_t _S_heap_size;
105 static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states;
106 static pthread_key_t _S_key;
107 static bool _S_key_initialized;
108 // Pthread key under which per thread state is stored.
109 // Allocator instances that are currently unclaimed by any thread.
110 static void _S_destructor(void *instance);
111 // Function to be called on thread exit to reclaim per thread
113 static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();
114 // Return a recycled or new per thread state.
115 static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();
116 // ensure that the current thread has an associated
119 friend class _M_lock;
122 _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
123 ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
129 static void * allocate(size_t __n)
131 __obj * volatile * __my_free_list;
132 __obj * __RESTRICT __result;
133 _Pthread_alloc_per_thread_state<_Max_size>* __a;
135 if (__n > _Max_size) {
136 return(malloc_alloc::allocate(__n));
138 if (!_S_key_initialized ||
139 !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*)
140 pthread_getspecific(_S_key))) {
141 __a = _S_get_per_thread_state();
143 __my_free_list = __a -> __free_list + _S_freelist_index(__n);
144 __result = *__my_free_list;
146 void *__r = __a -> _M_refill(_S_round_up(__n));
149 *__my_free_list = __result -> __free_list_link;
154 static void deallocate(void *__p, size_t __n)
156 __obj *__q = (__obj *)__p;
157 __obj * volatile * __my_free_list;
158 _Pthread_alloc_per_thread_state<_Max_size>* __a;
160 if (__n > _Max_size) {
161 malloc_alloc::deallocate(__p, __n);
164 if (!_S_key_initialized ||
165 !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *)
166 pthread_getspecific(_S_key))) {
167 __a = _S_get_per_thread_state();
169 __my_free_list = __a->__free_list + _S_freelist_index(__n);
170 __q -> __free_list_link = *__my_free_list;
171 *__my_free_list = __q;
174 static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
178 typedef _Pthread_alloc_template<> pthread_alloc;
181 template <size_t _Max_size>
182 void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
184 _M_lock __lock_instance; // Need to acquire lock here.
185 _Pthread_alloc_per_thread_state<_Max_size>* __s =
186 (_Pthread_alloc_per_thread_state<_Max_size> *)__instance;
187 __s -> __next = _S_free_per_thread_states;
188 _S_free_per_thread_states = __s;
191 template <size_t _Max_size>
192 _Pthread_alloc_per_thread_state<_Max_size> *
193 _Pthread_alloc_template<_Max_size>::_S_new_per_thread_state()
195 /* lock already held here. */
196 if (0 != _S_free_per_thread_states) {
197 _Pthread_alloc_per_thread_state<_Max_size> *__result =
198 _S_free_per_thread_states;
199 _S_free_per_thread_states = _S_free_per_thread_states -> __next;
202 return new _Pthread_alloc_per_thread_state<_Max_size>;
206 template <size_t _Max_size>
207 _Pthread_alloc_per_thread_state<_Max_size> *
208 _Pthread_alloc_template<_Max_size>::_S_get_per_thread_state()
211 _M_lock __lock_instance; // Need to acquire lock here.
213 _Pthread_alloc_per_thread_state<_Max_size> * __result;
214 if (!_S_key_initialized) {
215 if (pthread_key_create(&_S_key, _S_destructor)) {
216 __THROW_BAD_ALLOC; // defined in stl_alloc.h
218 _S_key_initialized = true;
220 __result = _S_new_per_thread_state();
221 __ret_code = pthread_setspecific(_S_key, __result);
223 if (__ret_code == ENOMEM) {
233 /* We allocate memory in large chunks in order to avoid fragmenting */
234 /* the malloc heap too much. */
235 /* We assume that size is properly aligned. */
236 template <size_t _Max_size>
237 char *_Pthread_alloc_template<_Max_size>
238 ::_S_chunk_alloc(size_t __size, int &__nobjs)
242 size_t __total_bytes;
245 _M_lock __lock_instance; // Acquire lock for this routine
247 __total_bytes = __size * __nobjs;
248 __bytes_left = _S_end_free - _S_start_free;
249 if (__bytes_left >= __total_bytes) {
250 __result = _S_start_free;
251 _S_start_free += __total_bytes;
253 } else if (__bytes_left >= __size) {
254 __nobjs = __bytes_left/__size;
255 __total_bytes = __size * __nobjs;
256 __result = _S_start_free;
257 _S_start_free += __total_bytes;
260 size_t __bytes_to_get =
261 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
262 // Try to make use of the left-over piece.
263 if (__bytes_left > 0) {
264 _Pthread_alloc_per_thread_state<_Max_size>* __a =
265 (_Pthread_alloc_per_thread_state<_Max_size>*)
266 pthread_getspecific(_S_key);
267 __obj * volatile * __my_free_list =
268 __a->__free_list + _S_freelist_index(__bytes_left);
270 ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
271 *__my_free_list = (__obj *)_S_start_free;
274 // Try to get memory that's aligned on something like a
275 // cache line boundary, so as to avoid parceling out
276 // parts of the same line to different threads and thus
277 // possibly different processors.
279 const int __cache_line_size = 128; // probable upper bound
280 __bytes_to_get &= ~(__cache_line_size-1);
281 _S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get);
282 if (0 == _S_start_free) {
283 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
286 # else /* !SGI_SOURCE */
287 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
289 _S_heap_size += __bytes_to_get;
290 _S_end_free = _S_start_free + __bytes_to_get;
293 // lock is released here
294 return(_S_chunk_alloc(__size, __nobjs));
298 /* Returns an object of size n, and optionally adds to size n free list.*/
299 /* We assume that n is properly aligned. */
300 /* We hold the allocation lock. */
301 template <size_t _Max_size>
302 void *_Pthread_alloc_per_thread_state<_Max_size>
303 ::_M_refill(size_t __n)
307 _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
308 __obj * volatile * __my_free_list;
310 __obj * __current_obj, * __next_obj;
316 __my_free_list = __free_list
317 + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
319 /* Build free list in chunk */
320 __result = (__obj *)__chunk;
321 *__my_free_list = __next_obj = (__obj *)(__chunk + __n);
322 for (__i = 1; ; __i++) {
323 __current_obj = __next_obj;
324 __next_obj = (__obj *)((char *)__next_obj + __n);
325 if (__nobjs - 1 == __i) {
326 __current_obj -> __free_list_link = 0;
329 __current_obj -> __free_list_link = __next_obj;
335 template <size_t _Max_size>
336 void *_Pthread_alloc_template<_Max_size>
337 ::reallocate(void *__p, size_t __old_sz, size_t __new_sz)
342 if (__old_sz > _Max_size
343 && __new_sz > _Max_size) {
344 return(realloc(__p, __new_sz));
346 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
347 __result = allocate(__new_sz);
348 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
349 memcpy(__result, __p, __copy_sz);
350 deallocate(__p, __old_sz);
354 template <size_t _Max_size>
355 _Pthread_alloc_per_thread_state<_Max_size> *
356 _Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0;
358 template <size_t _Max_size>
359 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
361 template <size_t _Max_size>
362 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
364 template <size_t _Max_size>
365 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
366 = PTHREAD_MUTEX_INITIALIZER;
368 template <size_t _Max_size>
369 char *_Pthread_alloc_template<_Max_size>
372 template <size_t _Max_size>
373 char *_Pthread_alloc_template<_Max_size>
376 template <size_t _Max_size>
377 size_t _Pthread_alloc_template<_Max_size>
380 #ifdef __STL_USE_STD_ALLOCATORS
383 class pthread_allocator {
384 typedef pthread_alloc _S_Alloc; // The underlying allocator.
386 typedef size_t size_type;
387 typedef ptrdiff_t difference_type;
388 typedef _Tp* pointer;
389 typedef const _Tp* const_pointer;
390 typedef _Tp& reference;
391 typedef const _Tp& const_reference;
392 typedef _Tp value_type;
394 template <class _NewType> struct rebind {
395 typedef pthread_allocator<_NewType> other;
398 pthread_allocator() __STL_NOTHROW {}
399 pthread_allocator(const pthread_allocator& a) __STL_NOTHROW {}
400 template <class _OtherType>
401 pthread_allocator(const pthread_allocator<_OtherType>&)
403 ~pthread_allocator() __STL_NOTHROW {}
405 pointer address(reference __x) const { return &__x; }
406 const_pointer address(const_reference __x) const { return &__x; }
408 // __n is permitted to be 0. The C++ standard says nothing about what
409 // the return value is when __n == 0.
410 _Tp* allocate(size_type __n, const void* = 0) {
411 return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp)))
415 // p is not permitted to be a null pointer.
416 void deallocate(pointer __p, size_type __n)
417 { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }
419 size_type max_size() const __STL_NOTHROW
420 { return size_t(-1) / sizeof(_Tp); }
422 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
423 void destroy(pointer _p) { _p->~_Tp(); }
427 class pthread_allocator<void> {
429 typedef size_t size_type;
430 typedef ptrdiff_t difference_type;
431 typedef void* pointer;
432 typedef const void* const_pointer;
433 typedef void value_type;
435 template <class _NewType> struct rebind {
436 typedef pthread_allocator<_NewType> other;
440 template <size_t _Max_size>
441 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
442 const _Pthread_alloc_template<_Max_size>&)
447 template <class _T1, class _T2>
448 inline bool operator==(const pthread_allocator<_T1>&,
449 const pthread_allocator<_T2>& a2)
454 template <class _T1, class _T2>
455 inline bool operator!=(const pthread_allocator<_T1>&,
456 const pthread_allocator<_T2>&)
461 template <class _Tp, size_t _Max_size>
462 struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
464 static const bool _S_instanceless = true;
465 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type;
466 typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> >
470 template <class _Tp, class _Atype, size_t _Max>
471 struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
473 static const bool _S_instanceless = true;
474 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type;
475 typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type;
478 template <class _Tp, class _Atype>
479 struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
481 static const bool _S_instanceless = true;
482 typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
483 typedef pthread_allocator<_Tp> allocator_type;
487 #endif /* __STL_USE_STD_ALLOCATORS */
491 #endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */