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

   1 /*
   2  * Copyright (c) 1996
   3  * Silicon Graphics Computer Systems, Inc.
   4  *
   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.
  12  */
  13
  14 #ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H
  15 #define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1
  16
  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
  28 // consequences.
  29
  30 #include <bits/std_cerrno.h>
  31 #include <bits/stl_config.h>
  32 #include <bits/stl_alloc.h>
  33 #ifndef __RESTRICT
  34 #  define __RESTRICT
  35 #endif
  36
  37 #ifndef __STL_NO_BAD_ALLOC
  38 #  include <bits/std_new.h>
  39 #endif
  40
  41 __STL_BEGIN_NAMESPACE
  42
  43 #define __STL_DATA_ALIGNMENT 8
  44
  45 union _Pthread_alloc_obj {
  46     union _Pthread_alloc_obj * __free_list_link;
  47     char __client_data[__STL_DATA_ALIGNMENT];    /* The client sees this.    */
  48 };
  49
  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>.
  54
  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
  65         // created thread.
  66   _Pthread_alloc_per_thread_state() : __next(0)
  67   {
  68     memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
  69   }
  70   // Returns an object of size __n, and possibly adds to size n free list.
  71   void *_M_refill(size_t __n);
  72 };
  73
  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 {
  80
  81 public: // but only for internal use:
  82
  83   typedef _Pthread_alloc_obj __obj;
  84
  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);
  88
  89   enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
  90
  91   static size_t _S_round_up(size_t __bytes) {
  92     return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
  93   }
  94   static size_t _S_freelist_index(size_t __bytes) {
  95     return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
  96   }
  97
  98 private:
  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
 112         // state.
 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
 117         // per thread state.
 118   class _M_lock;
 119   friend class _M_lock;
 120   class _M_lock {
 121       public:
 122         _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
 123         ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
 124   };
 125
 126 public:
 127
 128   /* n must be > 0      */
 129   static void * allocate(size_t __n)
 130   {
 131     __obj * volatile * __my_free_list;
 132     __obj * __RESTRICT __result;
 133     _Pthread_alloc_per_thread_state<_Max_size>* __a;
 134
 135     if (__n > _Max_size) {
 136         return(malloc_alloc::allocate(__n));
 137     }
 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();
 142     }
 143     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
 144     __result = *__my_free_list;
 145     if (__result == 0) {
 146         void *__r = __a -> _M_refill(_S_round_up(__n));
 147         return __r;
 148     }
 149     *__my_free_list = __result -> __free_list_link;
 150     return (__result);
 151   };
 152
 153   /* p may not be 0 */
 154   static void deallocate(void *__p, size_t __n)
 155   {
 156     __obj *__q = (__obj *)__p;
 157     __obj * volatile * __my_free_list;
 158     _Pthread_alloc_per_thread_state<_Max_size>* __a;
 159
 160     if (__n > _Max_size) {
 161         malloc_alloc::deallocate(__p, __n);
 162         return;
 163     }
 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();
 168     }
 169     __my_free_list = __a->__free_list + _S_freelist_index(__n);
 170     __q -> __free_list_link = *__my_free_list;
 171     *__my_free_list = __q;
 172   }
 173
 174   static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
 175
 176 } ;
 177
 178 typedef _Pthread_alloc_template<> pthread_alloc;
 179
 180
 181 template <size_t _Max_size>
 182 void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
 183 {
 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;
 189 }
 190
 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()
 194 {
 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;
 200         return __result;
 201     } else {
 202         return new _Pthread_alloc_per_thread_state<_Max_size>;
 203     }
 204 }
 205
 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()
 209 {
 210     /*REFERENCED*/
 211     _M_lock __lock_instance;    // Need to acquire lock here.
 212     int __ret_code;
 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
 217         }
 218         _S_key_initialized = true;
 219     }
 220     __result = _S_new_per_thread_state();
 221     __ret_code = pthread_setspecific(_S_key, __result);
 222     if (__ret_code) {
 223       if (__ret_code == ENOMEM) {
 224         __THROW_BAD_ALLOC;
 225       } else {
 226         // EINVAL
 227         abort();
 228       }
 229     }
 230     return __result;
 231 }
 232
 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)
 239 {
 240   {
 241     char * __result;
 242     size_t __total_bytes;
 243     size_t __bytes_left;
 244     /*REFERENCED*/
 245     _M_lock __lock_instance;         // Acquire lock for this routine
 246
 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;
 252         return(__result);
 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;
 258         return(__result);
 259     } else {
 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);
 269
 270             ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
 271             *__my_free_list = (__obj *)_S_start_free;
 272         }
 273 #       ifdef _SGI_SOURCE
 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.
 278           {
 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);
 284             }
 285           }
 286 #       else  /* !SGI_SOURCE */
 287           _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
 288 #       endif
 289         _S_heap_size += __bytes_to_get;
 290         _S_end_free = _S_start_free + __bytes_to_get;
 291     }
 292   }
 293   // lock is released here
 294   return(_S_chunk_alloc(__size, __nobjs));
 295 }
 296
 297
 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)
 304 {
 305     int __nobjs = 128;
 306     char * __chunk =
 307         _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
 308     __obj * volatile * __my_free_list;
 309     __obj * __result;
 310     __obj * __current_obj, * __next_obj;
 311     int __i;
 312
 313     if (1 == __nobjs)  {
 314         return(__chunk);
 315     }
 316     __my_free_list = __free_list
 317                  + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
 318
 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;
 327             break;
 328         } else {
 329             __current_obj -> __free_list_link = __next_obj;
 330         }
 331       }
 332     return(__result);
 333 }
 334
 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)
 338 {
 339     void * __result;
 340     size_t __copy_sz;
 341
 342     if (__old_sz > _Max_size
 343         && __new_sz > _Max_size) {
 344         return(realloc(__p, __new_sz));
 345     }
 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);
 351     return(__result);
 352 }
 353
 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;
 357
 358 template <size_t _Max_size>
 359 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
 360
 361 template <size_t _Max_size>
 362 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
 363
 364 template <size_t _Max_size>
 365 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
 366 = PTHREAD_MUTEX_INITIALIZER;
 367
 368 template <size_t _Max_size>
 369 char *_Pthread_alloc_template<_Max_size>
 370 ::_S_start_free = 0;
 371
 372 template <size_t _Max_size>
 373 char *_Pthread_alloc_template<_Max_size>
 374 ::_S_end_free = 0;
 375
 376 template <size_t _Max_size>
 377 size_t _Pthread_alloc_template<_Max_size>
 378 ::_S_heap_size = 0;
 379
 380 #ifdef __STL_USE_STD_ALLOCATORS
 381
 382 template <class _Tp>
 383 class pthread_allocator {
 384   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
 385 public:
 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;
 393
 394   template <class _NewType> struct rebind {
 395     typedef pthread_allocator<_NewType> other;
 396   };
 397
 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>&)
 402                 __STL_NOTHROW {}
 403   ~pthread_allocator() __STL_NOTHROW {}
 404
 405   pointer address(reference __x) const { return &__x; }
 406   const_pointer address(const_reference __x) const { return &__x; }
 407
 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)))
 412                     : 0;
 413   }
 414
 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)); }
 418
 419   size_type max_size() const __STL_NOTHROW
 420     { return size_t(-1) / sizeof(_Tp); }
 421
 422   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
 423   void destroy(pointer _p) { _p->~_Tp(); }
 424 };
 425
 426 template<>
 427 class pthread_allocator<void> {
 428 public:
 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;
 434
 435   template <class _NewType> struct rebind {
 436     typedef pthread_allocator<_NewType> other;
 437   };
 438 };
 439
 440 template <size_t _Max_size>
 441 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
 442                        const _Pthread_alloc_template<_Max_size>&)
 443 {
 444   return true;
 445 }
 446
 447 template <class _T1, class _T2>
 448 inline bool operator==(const pthread_allocator<_T1>&,
 449                        const pthread_allocator<_T2>& a2)
 450 {
 451   return true;
 452 }
 453
 454 template <class _T1, class _T2>
 455 inline bool operator!=(const pthread_allocator<_T1>&,
 456                        const pthread_allocator<_T2>&)
 457 {
 458   return false;
 459 }
 460
 461 template <class _Tp, size_t _Max_size>
 462 struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
 463 {
 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> >
 467           allocator_type;
 468 };
 469
 470 template <class _Tp, class _Atype, size_t _Max>
 471 struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
 472 {
 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;
 476 };
 477
 478 template <class _Tp, class _Atype>
 479 struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
 480 {
 481   static const bool _S_instanceless = true;
 482   typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
 483   typedef pthread_allocator<_Tp> allocator_type;
 484 };
 485
 486
 487 #endif /* __STL_USE_STD_ALLOCATORS */
 488
 489 __STL_END_NAMESPACE
 490
 491 #endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */
 492
 493 // Local Variables:
 494 // mode:C++
 495 // End: