pthread_allocimpl.h

Go to the documentation of this file.
00001 // POSIX thread-related memory allocation -*- C++ -*-
00002 
00003 // Copyright (C) 2001 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  * Copyright (c) 1996
00032  * Silicon Graphics Computer Systems, Inc.
00033  *
00034  * Permission to use, copy, modify, distribute and sell this software
00035  * and its documentation for any purpose is hereby granted without fee,
00036  * provided that the above copyright notice appear in all copies and
00037  * that both that copyright notice and this permission notice appear
00038  * in supporting documentation.  Silicon Graphics makes no
00039  * representations about the suitability of this software for any
00040  * purpose.  It is provided "as is" without express or implied warranty.
00041  */
00042 
00043 /** @file pthread_allocimpl.h
00044  *  This is an internal header file, included by other library headers.
00045  *  You should not attempt to use it directly.
00046  */
00047 
00048 #ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H
00049 #define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1
00050 
00051 // Pthread-specific node allocator.
00052 // This is similar to the default allocator, except that free-list
00053 // information is kept separately for each thread, avoiding locking.
00054 // This should be reasonably fast even in the presence of threads.
00055 // The down side is that storage may not be well-utilized.
00056 // It is not an error to allocate memory in thread A and deallocate
00057 // it in thread B.  But this effectively transfers ownership of the memory,
00058 // so that it can only be reallocated by thread B.  Thus this can effectively
00059 // result in a storage leak if it's done on a regular basis.
00060 // It can also result in frequent sharing of
00061 // cache lines among processors, with potentially serious performance
00062 // consequences.
00063 
00064 #include <bits/c++config.h>
00065 #include <cerrno>
00066 #include <bits/stl_alloc.h>
00067 #ifndef __RESTRICT
00068 #  define __RESTRICT
00069 #endif
00070 
00071 #include <new>
00072 
00073 namespace std
00074 {
00075 
00076 #define __STL_DATA_ALIGNMENT 8
00077 
00078 union _Pthread_alloc_obj {
00079     union _Pthread_alloc_obj * __free_list_link;
00080     char __client_data[__STL_DATA_ALIGNMENT];    /* The client sees this.    */
00081 };
00082 
00083 // Pthread allocators don't appear to the client to have meaningful
00084 // instances.  We do in fact need to associate some state with each
00085 // thread.  That state is represented by
00086 // _Pthread_alloc_per_thread_state<_Max_size>.
00087 
00088 template<size_t _Max_size>
00089 struct _Pthread_alloc_per_thread_state {
00090   typedef _Pthread_alloc_obj __obj;
00091   enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT };
00092   _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS]; 
00093   _Pthread_alloc_per_thread_state<_Max_size> * __next; 
00094     // Free list link for list of available per thread structures.
00095     // When one of these becomes available for reuse due to thread
00096     // termination, any objects in its free list remain associated
00097     // with it.  The whole structure may then be used by a newly
00098     // created thread.
00099   _Pthread_alloc_per_thread_state() : __next(0)
00100   {
00101     memset((void *)__free_list, 0, (size_t) _S_NFREELISTS * sizeof(__obj *));
00102   }
00103   // Returns an object of size __n, and possibly adds to size n free list.
00104   void *_M_refill(size_t __n);
00105 };
00106 
00107 // Pthread-specific allocator.
00108 // The argument specifies the largest object size allocated from per-thread
00109 // free lists.  Larger objects are allocated using malloc_alloc.
00110 // Max_size must be a power of 2.
00111 template <size_t _Max_size = 128>
00112 class _Pthread_alloc_template {
00113 
00114 public: // but only for internal use:
00115 
00116   typedef _Pthread_alloc_obj __obj;
00117 
00118   // Allocates a chunk for nobjs of size size.  nobjs may be reduced
00119   // if it is inconvenient to allocate the requested number.
00120   static char *_S_chunk_alloc(size_t __size, int &__nobjs);
00121 
00122   enum {_S_ALIGN = __STL_DATA_ALIGNMENT};
00123 
00124   static size_t _S_round_up(size_t __bytes) {
00125     return (((__bytes) + (int) _S_ALIGN-1) & ~((int) _S_ALIGN - 1));
00126   }
00127   static size_t _S_freelist_index(size_t __bytes) {
00128     return (((__bytes) + (int) _S_ALIGN-1)/(int)_S_ALIGN - 1);
00129   }
00130 
00131 private:
00132   // Chunk allocation state. And other shared state.
00133   // Protected by _S_chunk_allocator_lock.
00134   static pthread_mutex_t _S_chunk_allocator_lock;
00135   static char *_S_start_free;
00136   static char *_S_end_free;
00137   static size_t _S_heap_size;
00138   static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states;
00139   static pthread_key_t _S_key;
00140   static bool _S_key_initialized;
00141         // Pthread key under which per thread state is stored. 
00142         // Allocator instances that are currently unclaimed by any thread.
00143   static void _S_destructor(void *instance);
00144         // Function to be called on thread exit to reclaim per thread
00145         // state.
00146   static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();
00147         // Return a recycled or new per thread state.
00148   static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();
00149         // ensure that the current thread has an associated
00150         // per thread state.
00151   class _M_lock;
00152   friend class _M_lock;
00153   class _M_lock {
00154       public:
00155         _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }
00156         ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }
00157   };
00158 
00159 public:
00160 
00161   /* n must be > 0      */
00162   static void * allocate(size_t __n)
00163   {
00164     __obj * volatile * __my_free_list;
00165     __obj * __RESTRICT __result;
00166     _Pthread_alloc_per_thread_state<_Max_size>* __a;
00167 
00168     if (__n > _Max_size) {
00169         return(malloc_alloc::allocate(__n));
00170     }
00171     if (!_S_key_initialized ||
00172         !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*)
00173                                  pthread_getspecific(_S_key))) {
00174         __a = _S_get_per_thread_state();
00175     }
00176     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
00177     __result = *__my_free_list;
00178     if (__result == 0) {
00179         void *__r = __a -> _M_refill(_S_round_up(__n));
00180         return __r;
00181     }
00182     *__my_free_list = __result -> __free_list_link;
00183     return (__result);
00184   };
00185 
00186   /* p may not be 0 */
00187   static void deallocate(void *__p, size_t __n)
00188   {
00189     __obj *__q = (__obj *)__p;
00190     __obj * volatile * __my_free_list;
00191     _Pthread_alloc_per_thread_state<_Max_size>* __a;
00192 
00193     if (__n > _Max_size) {
00194         malloc_alloc::deallocate(__p, __n);
00195         return;
00196     }
00197     if (!_S_key_initialized ||
00198         !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *)
00199                 pthread_getspecific(_S_key))) {
00200         __a = _S_get_per_thread_state();
00201     }
00202     __my_free_list = __a->__free_list + _S_freelist_index(__n);
00203     __q -> __free_list_link = *__my_free_list;
00204     *__my_free_list = __q;
00205   }
00206 
00207   static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
00208 
00209 } ;
00210 
00211 typedef _Pthread_alloc_template<> pthread_alloc;
00212 
00213 
00214 template <size_t _Max_size>
00215 void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)
00216 {
00217     _M_lock __lock_instance;    // Need to acquire lock here.
00218     _Pthread_alloc_per_thread_state<_Max_size>* __s =
00219         (_Pthread_alloc_per_thread_state<_Max_size> *)__instance;
00220     __s -> __next = _S_free_per_thread_states;
00221     _S_free_per_thread_states = __s;
00222 }
00223 
00224 template <size_t _Max_size>
00225 _Pthread_alloc_per_thread_state<_Max_size> *
00226 _Pthread_alloc_template<_Max_size>::_S_new_per_thread_state()
00227 {    
00228     /* lock already held here.  */
00229     if (0 != _S_free_per_thread_states) {
00230         _Pthread_alloc_per_thread_state<_Max_size> *__result =
00231                     _S_free_per_thread_states;
00232         _S_free_per_thread_states = _S_free_per_thread_states -> __next;
00233         return __result;
00234     } else {
00235         return new _Pthread_alloc_per_thread_state<_Max_size>;
00236     }
00237 }
00238 
00239 template <size_t _Max_size>
00240 _Pthread_alloc_per_thread_state<_Max_size> *
00241 _Pthread_alloc_template<_Max_size>::_S_get_per_thread_state()
00242 {
00243     /*REFERENCED*/
00244     _M_lock __lock_instance;    // Need to acquire lock here.
00245     int __ret_code;
00246     _Pthread_alloc_per_thread_state<_Max_size> * __result;
00247     if (!_S_key_initialized) {
00248         if (pthread_key_create(&_S_key, _S_destructor)) {
00249         std::__throw_bad_alloc();  // defined in funcexcept.h
00250         }
00251         _S_key_initialized = true;
00252     }
00253     __result = _S_new_per_thread_state();
00254     __ret_code = pthread_setspecific(_S_key, __result);
00255     if (__ret_code) {
00256       if (__ret_code == ENOMEM) {
00257     std::__throw_bad_alloc();
00258       } else {
00259     // EINVAL
00260     abort();
00261       }
00262     }
00263     return __result;
00264 }
00265 
00266 /* We allocate memory in large chunks in order to avoid fragmenting     */
00267 /* the malloc heap too much.                                            */
00268 /* We assume that size is properly aligned.                             */
00269 template <size_t _Max_size>
00270 char *_Pthread_alloc_template<_Max_size>
00271 ::_S_chunk_alloc(size_t __size, int &__nobjs)
00272 {
00273   {
00274     char * __result;
00275     size_t __total_bytes;
00276     size_t __bytes_left;
00277     /*REFERENCED*/
00278     _M_lock __lock_instance;         // Acquire lock for this routine
00279 
00280     __total_bytes = __size * __nobjs;
00281     __bytes_left = _S_end_free - _S_start_free;
00282     if (__bytes_left >= __total_bytes) {
00283         __result = _S_start_free;
00284         _S_start_free += __total_bytes;
00285         return(__result);
00286     } else if (__bytes_left >= __size) {
00287         __nobjs = __bytes_left/__size;
00288         __total_bytes = __size * __nobjs;
00289         __result = _S_start_free;
00290         _S_start_free += __total_bytes;
00291         return(__result);
00292     } else {
00293         size_t __bytes_to_get =
00294         2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
00295         // Try to make use of the left-over piece.
00296         if (__bytes_left > 0) {
00297             _Pthread_alloc_per_thread_state<_Max_size>* __a = 
00298                 (_Pthread_alloc_per_thread_state<_Max_size>*)
00299             pthread_getspecific(_S_key);
00300             __obj * volatile * __my_free_list =
00301                         __a->__free_list + _S_freelist_index(__bytes_left);
00302 
00303             ((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
00304             *__my_free_list = (__obj *)_S_start_free;
00305         }
00306 #       ifdef _SGI_SOURCE
00307           // Try to get memory that's aligned on something like a
00308           // cache line boundary, so as to avoid parceling out
00309           // parts of the same line to different threads and thus
00310           // possibly different processors.
00311           {
00312             const int __cache_line_size = 128;  // probable upper bound
00313             __bytes_to_get &= ~(__cache_line_size-1);
00314             _S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get); 
00315             if (0 == _S_start_free) {
00316               _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
00317             }
00318           }
00319 #       else  /* !SGI_SOURCE */
00320           _S_start_free = (char *)malloc_alloc::allocate(__bytes_to_get);
00321 #       endif
00322         _S_heap_size += __bytes_to_get;
00323         _S_end_free = _S_start_free + __bytes_to_get;
00324     }
00325   }
00326   // lock is released here
00327   return(_S_chunk_alloc(__size, __nobjs));
00328 }
00329 
00330 
00331 /* Returns an object of size n, and optionally adds to size n free list.*/
00332 /* We assume that n is properly aligned.                                */
00333 /* We hold the allocation lock.                                         */
00334 template <size_t _Max_size>
00335 void *_Pthread_alloc_per_thread_state<_Max_size>
00336 ::_M_refill(size_t __n)
00337 {
00338     int __nobjs = 128;
00339     char * __chunk =
00340     _Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);
00341     __obj * volatile * __my_free_list;
00342     __obj * __result;
00343     __obj * __current_obj, * __next_obj;
00344     int __i;
00345 
00346     if (1 == __nobjs)  {
00347         return(__chunk);
00348     }
00349     __my_free_list = __free_list
00350          + _Pthread_alloc_template<_Max_size>::_S_freelist_index(__n);
00351 
00352     /* Build free list in chunk */
00353       __result = (__obj *)__chunk;
00354       *__my_free_list = __next_obj = (__obj *)(__chunk + __n);
00355       for (__i = 1; ; __i++) {
00356         __current_obj = __next_obj;
00357         __next_obj = (__obj *)((char *)__next_obj + __n);
00358         if (__nobjs - 1 == __i) {
00359             __current_obj -> __free_list_link = 0;
00360             break;
00361         } else {
00362             __current_obj -> __free_list_link = __next_obj;
00363         }
00364       }
00365     return(__result);
00366 }
00367 
00368 template <size_t _Max_size>
00369 void *_Pthread_alloc_template<_Max_size>
00370 ::reallocate(void *__p, size_t __old_sz, size_t __new_sz)
00371 {
00372     void * __result;
00373     size_t __copy_sz;
00374 
00375     if (__old_sz > _Max_size
00376     && __new_sz > _Max_size) {
00377         return(realloc(__p, __new_sz));
00378     }
00379     if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
00380     __result = allocate(__new_sz);
00381     __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
00382     memcpy(__result, __p, __copy_sz);
00383     deallocate(__p, __old_sz);
00384     return(__result);
00385 }
00386 
00387 template <size_t _Max_size>
00388 _Pthread_alloc_per_thread_state<_Max_size> *
00389 _Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0;
00390 
00391 template <size_t _Max_size>
00392 pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;
00393 
00394 template <size_t _Max_size>
00395 bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;
00396 
00397 template <size_t _Max_size>
00398 pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock
00399 = PTHREAD_MUTEX_INITIALIZER;
00400 
00401 template <size_t _Max_size>
00402 char *_Pthread_alloc_template<_Max_size>
00403 ::_S_start_free = 0;
00404 
00405 template <size_t _Max_size>
00406 char *_Pthread_alloc_template<_Max_size>
00407 ::_S_end_free = 0;
00408 
00409 template <size_t _Max_size>
00410 size_t _Pthread_alloc_template<_Max_size>
00411 ::_S_heap_size = 0;
00412 
00413 
00414 template <class _Tp>
00415 class pthread_allocator {
00416   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
00417 public:
00418   typedef size_t     size_type;
00419   typedef ptrdiff_t  difference_type;
00420   typedef _Tp*       pointer;
00421   typedef const _Tp* const_pointer;
00422   typedef _Tp&       reference;
00423   typedef const _Tp& const_reference;
00424   typedef _Tp        value_type;
00425 
00426   template <class _NewType> struct rebind {
00427     typedef pthread_allocator<_NewType> other;
00428   };
00429 
00430   pthread_allocator() throw() {}
00431   pthread_allocator(const pthread_allocator& a) throw() {}
00432   template <class _OtherType>
00433     pthread_allocator(const pthread_allocator<_OtherType>&)
00434         throw() {}
00435   ~pthread_allocator() throw() {}
00436 
00437   pointer address(reference __x) const { return &__x; }
00438   const_pointer address(const_reference __x) const { return &__x; }
00439 
00440   // __n is permitted to be 0.  The C++ standard says nothing about what
00441   // the return value is when __n == 0.
00442   _Tp* allocate(size_type __n, const void* = 0) {
00443     return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp)))
00444                     : 0;
00445   }
00446 
00447   // p is not permitted to be a null pointer.
00448   void deallocate(pointer __p, size_type __n)
00449     { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }
00450 
00451   size_type max_size() const throw() 
00452     { return size_t(-1) / sizeof(_Tp); }
00453 
00454   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
00455   void destroy(pointer _p) { _p->~_Tp(); }
00456 };
00457 
00458 template<>
00459 class pthread_allocator<void> {
00460 public:
00461   typedef size_t      size_type;
00462   typedef ptrdiff_t   difference_type;
00463   typedef void*       pointer;
00464   typedef const void* const_pointer;
00465   typedef void        value_type;
00466 
00467   template <class _NewType> struct rebind {
00468     typedef pthread_allocator<_NewType> other;
00469   };
00470 };
00471 
00472 template <size_t _Max_size>
00473 inline bool operator==(const _Pthread_alloc_template<_Max_size>&,
00474                        const _Pthread_alloc_template<_Max_size>&)
00475 {
00476   return true;
00477 }
00478 
00479 template <class _T1, class _T2>
00480 inline bool operator==(const pthread_allocator<_T1>&,
00481                        const pthread_allocator<_T2>& a2) 
00482 {
00483   return true;
00484 }
00485 
00486 template <class _T1, class _T2>
00487 inline bool operator!=(const pthread_allocator<_T1>&,
00488                        const pthread_allocator<_T2>&)
00489 {
00490   return false;
00491 }
00492 
00493 template <class _Tp, size_t _Max_size>
00494 struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >
00495 {
00496   static const bool _S_instanceless = true;
00497   typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type;
00498   typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> > 
00499           allocator_type;
00500 };
00501 
00502 template <class _Tp, class _Atype, size_t _Max>
00503 struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >
00504 {
00505   static const bool _S_instanceless = true;
00506   typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type;
00507   typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type;
00508 };
00509 
00510 template <class _Tp, class _Atype>
00511 struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
00512 {
00513   static const bool _S_instanceless = true;
00514   typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;
00515   typedef pthread_allocator<_Tp> allocator_type;
00516 };
00517 
00518 
00519 } // namespace std
00520 
00521 #endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */
00522 
00523 // Local Variables:
00524 // mode:C++
00525 // End:

Generated on Thu Feb 10 23:22:56 2005 for libstdc++-v3 Source by  doxygen 1.4.0