libstdc++-v3/include/bits/pthread_allocimpl.h

   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
  73 namespace std
  74 {
  75
  76 #define __STL_DATA_ALIGNMENT 8
  77
  78 union _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
  88 template<size_t _Max_size>
  89 struct _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.
 111 template <size_t _Max_size = 128>
 112 class _Pthread_alloc_template {
 113
 114 public: // 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
 131 private:
 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
 159 public:
 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
 211 typedef _Pthread_alloc_template<> pthread_alloc;
 212
 213
 214 template <size_t _Max_size>
 215 void _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
 224 template <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
 239 template <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.                             */
 269 template <size_t _Max_size>
 270 char *_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.                                         */
 334 template <size_t _Max_size>
 335 void *_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
 368 template <size_t _Max_size>
 369 void *_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
 387 template <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
 391 template <size_t _Max_size>
 392 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
 393
 394 template <size_t _Max_size>
 395 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
 396
 397 template <size_t _Max_size>
 398 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
 399 = PTHREAD_MUTEX_INITIALIZER;
 400
 401 template <size_t _Max_size>
 402 char *_Pthread_alloc_template<_Max_size>
 403 ::_S_start_free = 0;
 404
 405 template <size_t _Max_size>
 406 char *_Pthread_alloc_template<_Max_size>
 407 ::_S_end_free = 0;
 408
 409 template <size_t _Max_size>
 410 size_t _Pthread_alloc_template<_Max_size>
 411 ::_S_heap_size = 0;
 412
 413
 414 template <class _Tp>
 415 class pthread_allocator {
 416   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
 417 public:
 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
 458 template<>
 459 class pthread_allocator<void> {
 460 public:
 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
 472 template <size_t _Max_size>
 473 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
 474                        const _Pthread_alloc_template<_Max_size>&)
 475 {
 476   return true;
 477 }
 478
 479 template <class _T1, class _T2>
 480 inline bool operator==(const pthread_allocator<_T1>&,
 481                        const pthread_allocator<_T2>& a2)
 482 {
 483   return true;
 484 }
 485
 486 template <class _T1, class _T2>
 487 inline bool operator!=(const pthread_allocator<_T1>&,
 488                        const pthread_allocator<_T2>&)
 489 {
 490   return false;
 491 }
 492
 493 template <class _Tp, size_t _Max_size>
 494 struct _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
 502 template <class _Tp, class _Atype, size_t _Max>
 503 struct _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
 510 template <class _Tp, class _Atype>
 511 struct _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: