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 #ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H
  44 #define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1
  45
  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
  57 // consequences.
  58
  59 #include <bits/c++config.h>
  60 #include <bits/std_cerrno.h>
  61 #include <bits/stl_alloc.h>
  62 #ifndef __RESTRICT
  63 #  define __RESTRICT
  64 #endif
  65
  66 #include <new>
  67
  68 namespace std
  69 {
  70
  71 #define __STL_DATA_ALIGNMENT 8
  72
  73 union _Pthread_alloc_obj {
  74     union _Pthread_alloc_obj * __free_list_link;
  75     char __client_data[__STL_DATA_ALIGNMENT];    /* The client sees this.    */
  76 };
  77
  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>.
  82
  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
  93         // created thread.
  94   _Pthread_alloc_per_thread_state() : __next(0)
  95   {
  96     memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
  97   }
  98   // Returns an object of size __n, and possibly adds to size n free list.
  99   void *_M_refill(size_t __n);
 100 };
 101
 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 {
 108
 109 public: // but only for internal use:
 110
 111   typedef _Pthread_alloc_obj __obj;
 112
 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);
 116
 117   enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
 118
 119   static size_t _S_round_up(size_t __bytes) {
 120     return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
 121   }
 122   static size_t _S_freelist_index(size_t __bytes) {
 123     return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
 124   }
 125
 126 private:
 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
 140         // state.
 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
 145         // per thread state.
 146   class _M_lock;
 147   friend class _M_lock;
 148   class _M_lock {
 149       public:
 150         _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
 151         ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
 152   };
 153
 154 public:
 155
 156   /* n must be > 0      */
 157   static void * allocate(size_t __n)
 158   {
 159     __obj * volatile * __my_free_list;
 160     __obj * __RESTRICT __result;
 161     _Pthread_alloc_per_thread_state<_Max_size>* __a;
 162
 163     if (__n > _Max_size) {
 164         return(malloc_alloc::allocate(__n));
 165     }
 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();
 170     }
 171     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
 172     __result = *__my_free_list;
 173     if (__result == 0) {
 174         void *__r = __a -> _M_refill(_S_round_up(__n));
 175         return __r;
 176     }
 177     *__my_free_list = __result -> __free_list_link;
 178     return (__result);
 179   };
 180
 181   /* p may not be 0 */
 182   static void deallocate(void *__p, size_t __n)
 183   {
 184     __obj *__q = (__obj *)__p;
 185     __obj * volatile * __my_free_list;
 186     _Pthread_alloc_per_thread_state<_Max_size>* __a;
 187
 188     if (__n > _Max_size) {
 189         malloc_alloc::deallocate(__p, __n);
 190         return;
 191     }
 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();
 196     }
 197     __my_free_list = __a->__free_list + _S_freelist_index(__n);
 198     __q -> __free_list_link = *__my_free_list;
 199     *__my_free_list = __q;
 200   }
 201
 202   static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
 203
 204 } ;
 205
 206 typedef _Pthread_alloc_template<> pthread_alloc;
 207
 208
 209 template <size_t _Max_size>
 210 void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
 211 {
 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;
 217 }
 218
 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()
 222 {
 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;
 228         return __result;
 229     } else {
 230         return new _Pthread_alloc_per_thread_state<_Max_size>;
 231     }
 232 }
 233
 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()
 237 {
 238     /*REFERENCED*/
 239     _M_lock __lock_instance;    // Need to acquire lock here.
 240     int __ret_code;
 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
 245         }
 246         _S_key_initialized = true;
 247     }
 248     __result = _S_new_per_thread_state();
 249     __ret_code = pthread_setspecific(_S_key, __result);
 250     if (__ret_code) {
 251       if (__ret_code == ENOMEM) {
 252         std::__throw_bad_alloc();
 253       } else {
 254         // EINVAL
 255         abort();
 256       }
 257     }
 258     return __result;
 259 }
 260
 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)
 267 {
 268   {
 269     char * __result;
 270     size_t __total_bytes;
 271     size_t __bytes_left;
 272     /*REFERENCED*/
 273     _M_lock __lock_instance;         // Acquire lock for this routine
 274
 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;
 280         return(__result);
 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;
 286         return(__result);
 287     } else {
 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);
 297
 298             ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
 299             *__my_free_list = (__obj *)_S_start_free;
 300         }
 301 #       ifdef _SGI_SOURCE
 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.
 306           {
 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);
 312             }
 313           }
 314 #       else  /* !SGI_SOURCE */
 315           _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
 316 #       endif
 317         _S_heap_size += __bytes_to_get;
 318         _S_end_free = _S_start_free + __bytes_to_get;
 319     }
 320   }
 321   // lock is released here
 322   return(_S_chunk_alloc(__size, __nobjs));
 323 }
 324
 325
 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)
 332 {
 333     int __nobjs = 128;
 334     char * __chunk =
 335         _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
 336     __obj * volatile * __my_free_list;
 337     __obj * __result;
 338     __obj * __current_obj, * __next_obj;
 339     int __i;
 340
 341     if (1 == __nobjs)  {
 342         return(__chunk);
 343     }
 344     __my_free_list = __free_list
 345                  + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
 346
 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;
 355             break;
 356         } else {
 357             __current_obj -> __free_list_link = __next_obj;
 358         }
 359       }
 360     return(__result);
 361 }
 362
 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)
 366 {
 367     void * __result;
 368     size_t __copy_sz;
 369
 370     if (__old_sz > _Max_size
 371         && __new_sz > _Max_size) {
 372         return(realloc(__p, __new_sz));
 373     }
 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);
 379     return(__result);
 380 }
 381
 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;
 385
 386 template <size_t _Max_size>
 387 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
 388
 389 template <size_t _Max_size>
 390 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
 391
 392 template <size_t _Max_size>
 393 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
 394 = PTHREAD_MUTEX_INITIALIZER;
 395
 396 template <size_t _Max_size>
 397 char *_Pthread_alloc_template<_Max_size>
 398 ::_S_start_free = 0;
 399
 400 template <size_t _Max_size>
 401 char *_Pthread_alloc_template<_Max_size>
 402 ::_S_end_free = 0;
 403
 404 template <size_t _Max_size>
 405 size_t _Pthread_alloc_template<_Max_size>
 406 ::_S_heap_size = 0;
 407
 408
 409 template <class _Tp>
 410 class pthread_allocator {
 411   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
 412 public:
 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;
 420
 421   template <class _NewType> struct rebind {
 422     typedef pthread_allocator<_NewType> other;
 423   };
 424
 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>&)
 429                 __STL_NOTHROW {}
 430   ~pthread_allocator() __STL_NOTHROW {}
 431
 432   pointer address(reference __x) const { return &__x; }
 433   const_pointer address(const_reference __x) const { return &__x; }
 434
 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)))
 439                     : 0;
 440   }
 441
 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)); }
 445
 446   size_type max_size() const __STL_NOTHROW
 447     { return size_t(-1) / sizeof(_Tp); }
 448
 449   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
 450   void destroy(pointer _p) { _p->~_Tp(); }
 451 };
 452
 453 template<>
 454 class pthread_allocator<void> {
 455 public:
 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;
 461
 462   template <class _NewType> struct rebind {
 463     typedef pthread_allocator<_NewType> other;
 464   };
 465 };
 466
 467 template <size_t _Max_size>
 468 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
 469                        const _Pthread_alloc_template<_Max_size>&)
 470 {
 471   return true;
 472 }
 473
 474 template <class _T1, class _T2>
 475 inline bool operator==(const pthread_allocator<_T1>&,
 476                        const pthread_allocator<_T2>& a2)
 477 {
 478   return true;
 479 }
 480
 481 template <class _T1, class _T2>
 482 inline bool operator!=(const pthread_allocator<_T1>&,
 483                        const pthread_allocator<_T2>&)
 484 {
 485   return false;
 486 }
 487
 488 template <class _Tp, size_t _Max_size>
 489 struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
 490 {
 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> >
 494           allocator_type;
 495 };
 496
 497 template <class _Tp, class _Atype, size_t _Max>
 498 struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
 499 {
 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;
 503 };
 504
 505 template <class _Tp, class _Atype>
 506 struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
 507 {
 508   static const bool _S_instanceless = true;
 509   typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
 510   typedef pthread_allocator<_Tp> allocator_type;
 511 };
 512
 513
 514 } // namespace std
 515
 516 #endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */
 517
 518 // Local Variables:
 519 // mode:C++
 520 // End: