1// POSIX thread-related memory allocation -*- C++ -*- 2 3// Copyright (C) 2001 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/* 31 * Copyright (c) 1996 32 * Silicon Graphics Computer Systems, Inc. 33 * 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. 41 */ 42 43/** @file pthread_allocimpl.h 44 * This is an internal header file, included by other library headers. 45 * You should not attempt to use it directly. 46 */ 47 48#ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H 49#define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1 50 51// Pthread-specific node allocator. 52// This is similar to the default allocator, except that free-list 53// information is kept separately for each thread, avoiding locking. 54// This should be reasonably fast even in the presence of threads. 55// The down side is that storage may not be well-utilized. 56// It is not an error to allocate memory in thread A and deallocate 57// it in thread B. But this effectively transfers ownership of the memory, 58// so that it can only be reallocated by thread B. Thus this can effectively 59// result in a storage leak if it's done on a regular basis. 60// It can also result in frequent sharing of 61// cache lines among processors, with potentially serious performance 62// consequences. 63 64#include <bits/c++config.h> 65#include <cerrno> 66#include <bits/stl_alloc.h> 67#ifndef __RESTRICT 68# define __RESTRICT 69#endif 70 71#include <new> 72 73namespace std 74{ 75 76#define __STL_DATA_ALIGNMENT 8 77 78union _Pthread_alloc_obj { 79 union _Pthread_alloc_obj * __free_list_link; 80 char __client_data[__STL_DATA_ALIGNMENT]; /* The client sees this. */ 81}; 82 83// Pthread allocators don't appear to the client to have meaningful 84// instances. We do in fact need to associate some state with each 85// thread. That state is represented by 86// _Pthread_alloc_per_thread_state<_Max_size>. 87 88template<size_t _Max_size> 89struct _Pthread_alloc_per_thread_state { 90 typedef _Pthread_alloc_obj __obj; 91 enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT }; 92 _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS]; 93 _Pthread_alloc_per_thread_state<_Max_size> * __next; 94 // Free list link for list of available per thread structures. 95 // When one of these becomes available for reuse due to thread 96 // termination, any objects in its free list remain associated 97 // with it. The whole structure may then be used by a newly 98 // created thread. 99 _Pthread_alloc_per_thread_state() : __next(0) 100 { 101 memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *)); 102 } 103 // Returns an object of size __n, and possibly adds to size n free list. 104 void *_M_refill(size_t __n); 105}; 106 107// Pthread-specific allocator. 108// The argument specifies the largest object size allocated from per-thread 109// free lists. Larger objects are allocated using malloc_alloc. 110// Max_size must be a power of 2. 111template <size_t _Max_size = 128> 112class _Pthread_alloc_template { 113 114public: // but only for internal use: 115 116 typedef _Pthread_alloc_obj __obj; 117 118 // Allocates a chunk for nobjs of size size. nobjs may be reduced 119 // if it is inconvenient to allocate the requested number. 120 static char *_S_chunk_alloc(size_t __size, int &__nobjs); 121 122 enum {_S_ALIGN = __STL_DATA_ALIGNMENT}; 123 124 static size_t _S_round_up(size_t __bytes) { 125 return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1)); 126 } 127 static size_t _S_freelist_index(size_t __bytes) { 128 return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1); 129 } 130 131private: 132 // Chunk allocation state. And other shared state. 133 // Protected by _S_chunk_allocator_lock. 134 static pthread_mutex_t _S_chunk_allocator_lock; 135 static char *_S_start_free; 136 static char *_S_end_free; 137 static size_t _S_heap_size; 138 static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states; 139 static pthread_key_t _S_key; 140 static bool _S_key_initialized; 141 // Pthread key under which per thread state is stored. 142 // Allocator instances that are currently unclaimed by any thread. 143 static void _S_destructor(void *instance); 144 // Function to be called on thread exit to reclaim per thread 145 // state. 146 static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state(); 147 // Return a recycled or new per thread state. 148 static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state(); 149 // ensure that the current thread has an associated 150 // per thread state. 151 class _M_lock; 152 friend class _M_lock; 153 class _M_lock { 154 public: 155 _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); } 156 ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); } 157 }; 158 159public: 160 161 /* n must be > 0 */ 162 static void * allocate(size_t __n) 163 { 164 __obj * volatile * __my_free_list; 165 __obj * __RESTRICT __result; 166 _Pthread_alloc_per_thread_state<_Max_size>* __a; 167 168 if (__n > _Max_size) { 169 return(malloc_alloc::allocate(__n)); 170 } 171 if (!_S_key_initialized || 172 !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*) 173 pthread_getspecific(_S_key))) { 174 __a = _S_get_per_thread_state(); 175 } 176 __my_free_list = __a -> __free_list + _S_freelist_index(__n); 177 __result = *__my_free_list; 178 if (__result == 0) { 179 void *__r = __a -> _M_refill(_S_round_up(__n)); 180 return __r; 181 } 182 *__my_free_list = __result -> __free_list_link; 183 return (__result); 184 }; 185 186 /* p may not be 0 */ 187 static void deallocate(void *__p, size_t __n) 188 { 189 __obj *__q = (__obj *)__p; 190 __obj * volatile * __my_free_list; 191 _Pthread_alloc_per_thread_state<_Max_size>* __a; 192 193 if (__n > _Max_size) { 194 malloc_alloc::deallocate(__p, __n); 195 return; 196 } 197 if (!_S_key_initialized || 198 !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *) 199 pthread_getspecific(_S_key))) { 200 __a = _S_get_per_thread_state(); 201 } 202 __my_free_list = __a->__free_list + _S_freelist_index(__n); 203 __q -> __free_list_link = *__my_free_list; 204 *__my_free_list = __q; 205 } 206 207 static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz); 208 209} ; 210 211typedef _Pthread_alloc_template<> pthread_alloc; 212 213 214template <size_t _Max_size> 215void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance) 216{ 217 _M_lock __lock_instance; // Need to acquire lock here. 218 _Pthread_alloc_per_thread_state<_Max_size>* __s = 219 (_Pthread_alloc_per_thread_state<_Max_size> *)__instance; 220 __s -> __next = _S_free_per_thread_states; 221 _S_free_per_thread_states = __s; 222} 223 224template <size_t _Max_size> 225_Pthread_alloc_per_thread_state<_Max_size> * 226_Pthread_alloc_template<_Max_size>::_S_new_per_thread_state() 227{ 228 /* lock already held here. */ 229 if (0 != _S_free_per_thread_states) { 230 _Pthread_alloc_per_thread_state<_Max_size> *__result = 231 _S_free_per_thread_states; 232 _S_free_per_thread_states = _S_free_per_thread_states -> __next; 233 return __result; 234 } else { 235 return new _Pthread_alloc_per_thread_state<_Max_size>; 236 } 237} 238 239template <size_t _Max_size> 240_Pthread_alloc_per_thread_state<_Max_size> * 241_Pthread_alloc_template<_Max_size>::_S_get_per_thread_state() 242{ 243 /*REFERENCED*/ 244 _M_lock __lock_instance; // Need to acquire lock here. 245 int __ret_code; 246 _Pthread_alloc_per_thread_state<_Max_size> * __result; 247 if (!_S_key_initialized) { 248 if (pthread_key_create(&_S_key, _S_destructor)) { 249 std::__throw_bad_alloc(); // defined in funcexcept.h 250 } 251 _S_key_initialized = true; 252 } 253 __result = _S_new_per_thread_state(); 254 __ret_code = pthread_setspecific(_S_key, __result); 255 if (__ret_code) { 256 if (__ret_code == ENOMEM) { 257 std::__throw_bad_alloc(); 258 } else { 259 // EINVAL 260 abort(); 261 } 262 } 263 return __result; 264} 265 266/* We allocate memory in large chunks in order to avoid fragmenting */ 267/* the malloc heap too much. */ 268/* We assume that size is properly aligned. */ 269template <size_t _Max_size> 270char *_Pthread_alloc_template<_Max_size> 271::_S_chunk_alloc(size_t __size, int &__nobjs) 272{ 273 { 274 char * __result; 275 size_t __total_bytes; 276 size_t __bytes_left; 277 /*REFERENCED*/ 278 _M_lock __lock_instance; // Acquire lock for this routine 279 280 __total_bytes = __size * __nobjs; 281 __bytes_left = _S_end_free - _S_start_free; 282 if (__bytes_left >= __total_bytes) { 283 __result = _S_start_free; 284 _S_start_free += __total_bytes; 285 return(__result); 286 } else if (__bytes_left >= __size) { 287 __nobjs = __bytes_left/__size; 288 __total_bytes = __size * __nobjs; 289 __result = _S_start_free; 290 _S_start_free += __total_bytes; 291 return(__result); 292 } else { 293 size_t __bytes_to_get = 294 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); 295 // Try to make use of the left-over piece. 296 if (__bytes_left > 0) { 297 _Pthread_alloc_per_thread_state<_Max_size>* __a = 298 (_Pthread_alloc_per_thread_state<_Max_size>*) 299 pthread_getspecific(_S_key); 300 __obj * volatile * __my_free_list = 301 __a->__free_list + _S_freelist_index(__bytes_left); 302 303 ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list; 304 *__my_free_list = (__obj *)_S_start_free; 305 } 306# ifdef _SGI_SOURCE 307 // Try to get memory that's aligned on something like a 308 // cache line boundary, so as to avoid parceling out 309 // parts of the same line to different threads and thus 310 // possibly different processors. 311 { 312 const int __cache_line_size = 128; // probable upper bound 313 __bytes_to_get &= ~(__cache_line_size-1); 314 _S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get); 315 if (0 == _S_start_free) { 316 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get); 317 } 318 } 319# else /* !SGI_SOURCE */ 320 _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get); 321# endif 322 _S_heap_size += __bytes_to_get; 323 _S_end_free = _S_start_free + __bytes_to_get; 324 } 325 } 326 // lock is released here 327 return(_S_chunk_alloc(__size, __nobjs)); 328} 329 330 331/* Returns an object of size n, and optionally adds to size n free list.*/ 332/* We assume that n is properly aligned. */ 333/* We hold the allocation lock. */ 334template <size_t _Max_size> 335void *_Pthread_alloc_per_thread_state<_Max_size> 336::_M_refill(size_t __n) 337{ 338 int __nobjs = 128; 339 char * __chunk = 340 _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs); 341 __obj * volatile * __my_free_list; 342 __obj * __result; 343 __obj * __current_obj, * __next_obj; 344 int __i; 345 346 if (1 == __nobjs) { 347 return(__chunk); 348 } 349 __my_free_list = __free_list 350 + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n); 351 352 /* Build free list in chunk */ 353 __result = (__obj *)__chunk; 354 *__my_free_list = __next_obj = (__obj *)(__chunk + __n); 355 for (__i = 1; ; __i++) { 356 __current_obj = __next_obj; 357 __next_obj = (__obj *)((char *)__next_obj + __n); 358 if (__nobjs - 1 == __i) { 359 __current_obj -> __free_list_link = 0; 360 break; 361 } else { 362 __current_obj -> __free_list_link = __next_obj; 363 } 364 } 365 return(__result); 366} 367 368template <size_t _Max_size> 369void *_Pthread_alloc_template<_Max_size> 370::reallocate(void *__p, size_t __old_sz, size_t __new_sz) 371{ 372 void * __result; 373 size_t __copy_sz; 374 375 if (__old_sz > _Max_size 376 && __new_sz > _Max_size) { 377 return(realloc(__p, __new_sz)); 378 } 379 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p); 380 __result = allocate(__new_sz); 381 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz; 382 memcpy(__result, __p, __copy_sz); 383 deallocate(__p, __old_sz); 384 return(__result); 385} 386 387template <size_t _Max_size> 388_Pthread_alloc_per_thread_state<_Max_size> * 389_Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0; 390 391template <size_t _Max_size> 392pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key; 393 394template <size_t _Max_size> 395bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false; 396 397template <size_t _Max_size> 398pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock 399= PTHREAD_MUTEX_INITIALIZER; 400 401template <size_t _Max_size> 402char *_Pthread_alloc_template<_Max_size> 403::_S_start_free = 0; 404 405template <size_t _Max_size> 406char *_Pthread_alloc_template<_Max_size> 407::_S_end_free = 0; 408 409template <size_t _Max_size> 410size_t _Pthread_alloc_template<_Max_size> 411::_S_heap_size = 0; 412 413 414template <class _Tp> 415class pthread_allocator { 416 typedef pthread_alloc _S_Alloc; // The underlying allocator. 417public: 418 typedef size_t size_type; 419 typedef ptrdiff_t difference_type; 420 typedef _Tp* pointer; 421 typedef const _Tp* const_pointer; 422 typedef _Tp& reference; 423 typedef const _Tp& const_reference; 424 typedef _Tp value_type; 425 426 template <class _NewType> struct rebind { 427 typedef pthread_allocator<_NewType> other; 428 }; 429 430 pthread_allocator() throw() {} 431 pthread_allocator(const pthread_allocator& a) throw() {} 432 template <class _OtherType> 433 pthread_allocator(const pthread_allocator<_OtherType>&) 434 throw() {} 435 ~pthread_allocator() throw() {} 436 437 pointer address(reference __x) const { return &__x; } 438 const_pointer address(const_reference __x) const { return &__x; } 439 440 // __n is permitted to be 0. The C++ standard says nothing about what 441 // the return value is when __n == 0. 442 _Tp* allocate(size_type __n, const void* = 0) { 443 return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp))) 444 : 0; 445 } 446 447 // p is not permitted to be a null pointer. 448 void deallocate(pointer __p, size_type __n) 449 { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); } 450 451 size_type max_size() const throw() 452 { return size_t(-1) / sizeof(_Tp); } 453 454 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } 455 void destroy(pointer _p) { _p->~_Tp(); } 456}; 457 458template<> 459class pthread_allocator<void> { 460public: 461 typedef size_t size_type; 462 typedef ptrdiff_t difference_type; 463 typedef void* pointer; 464 typedef const void* const_pointer; 465 typedef void value_type; 466 467 template <class _NewType> struct rebind { 468 typedef pthread_allocator<_NewType> other; 469 }; 470}; 471 472template <size_t _Max_size> 473inline bool operator==(const _Pthread_alloc_template<_Max_size>&, 474 const _Pthread_alloc_template<_Max_size>&) 475{ 476 return true; 477} 478 479template <class _T1, class _T2> 480inline bool operator==(const pthread_allocator<_T1>&, 481 const pthread_allocator<_T2>& a2) 482{ 483 return true; 484} 485 486template <class _T1, class _T2> 487inline bool operator!=(const pthread_allocator<_T1>&, 488 const pthread_allocator<_T2>&) 489{ 490 return false; 491} 492 493template <class _Tp, size_t _Max_size> 494struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> > 495{ 496 static const bool _S_instanceless = true; 497 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type; 498 typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> > 499 allocator_type; 500}; 501 502template <class _Tp, class _Atype, size_t _Max> 503struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > > 504{ 505 static const bool _S_instanceless = true; 506 typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type; 507 typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type; 508}; 509 510template <class _Tp, class _Atype> 511struct _Alloc_traits<_Tp, pthread_allocator<_Atype> > 512{ 513 static const bool _S_instanceless = true; 514 typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type; 515 typedef pthread_allocator<_Tp> allocator_type; 516}; 517 518 519} // namespace std 520 521#endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */ 522 523// Local Variables: 524// mode:C++ 525// End: 526