williamr@2: /*
williamr@2:  *
williamr@2:  * Copyright (c) 1994
williamr@2:  * Hewlett-Packard Company
williamr@2:  *
williamr@2:  * Copyright (c) 1996,1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Moscow Center for SPARC Technology
williamr@2:  *
williamr@2:  * Copyright (c) 1999 
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@2:  * Permission to use or copy this software for any purpose is hereby granted 
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: 
williamr@2: #ifndef _STLP_PTHREAD_ALLOC_H
williamr@2: #define _STLP_PTHREAD_ALLOC_H
williamr@2: 
williamr@2: // Pthread-specific node allocator.
williamr@2: // This is similar to the default allocator, except that free-list
williamr@2: // information is kept separately for each thread, avoiding locking.
williamr@2: // This should be reasonably fast even in the presence of threads.
williamr@2: // The down side is that storage may not be well-utilized.
williamr@2: // It is not an error to allocate memory in thread A and deallocate
williamr@2: // it in thread B.  But this effectively transfers ownership of the memory,
williamr@2: // so that it can only be reallocated by thread B.  Thus this can effectively
williamr@2: // result in a storage leak if it's done on a regular basis.
williamr@2: // It can also result in frequent sharing of
williamr@2: // cache lines among processors, with potentially serious performance
williamr@2: // consequences.
williamr@2: 
williamr@2: #include <pthread.h>
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_ALLOC_H
williamr@2: #include <stl/_alloc.h>
williamr@2: #endif
williamr@2: 
williamr@2: #ifndef __RESTRICT
williamr@2: #  define __RESTRICT
williamr@2: #endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@2: #define _STLP_DATA_ALIGNMENT 8
williamr@2: 
williamr@2: union _Pthread_alloc_obj {
williamr@2:     union _Pthread_alloc_obj * __free_list_link;
williamr@2:     char __client_data[_STLP_DATA_ALIGNMENT];    /* The client sees this.    */
williamr@2: };
williamr@2: 
williamr@2: // Pthread allocators don't appear to the client to have meaningful
williamr@2: // instances.  We do in fact need to associate some state with each
williamr@2: // thread.  That state is represented by
williamr@2: // _Pthread_alloc_per_thread_state<_Max_size>.
williamr@2: 
williamr@2: template<size_t _Max_size>
williamr@2: struct _Pthread_alloc_per_thread_state {
williamr@2:   typedef _Pthread_alloc_obj __obj;
williamr@2:   enum { _S_NFREELISTS = _Max_size/_STLP_DATA_ALIGNMENT };
williamr@2: 
williamr@2:   // Free list link for list of available per thread structures.
williamr@2:   // When one of these becomes available for reuse due to thread
williamr@2:   // termination, any objects in its free list remain associated
williamr@2:   // with it.  The whole structure may then be used by a newly
williamr@2:   // created thread.
williamr@2:   _Pthread_alloc_per_thread_state() : __next(0)
williamr@2:   {
williamr@2:     memset((void *)__free_list, 0, (size_t)_S_NFREELISTS * sizeof(__obj *));
williamr@2:   }
williamr@2:   // Returns an object of size __n, and possibly adds to size n free list.
williamr@2:   void *_M_refill(size_t __n);
williamr@2:   
williamr@2:   _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS]; 
williamr@2:   _Pthread_alloc_per_thread_state<_Max_size> * __next; 
williamr@2:   // this data member is only to be used by per_thread_allocator, which returns memory to the originating thread.
williamr@2:   _STLP_mutex _M_lock;
williamr@2: 
williamr@2:  };
williamr@2: 
williamr@2: // Pthread-specific allocator.
williamr@2: // The argument specifies the largest object size allocated from per-thread
williamr@2: // free lists.  Larger objects are allocated using malloc_alloc.
williamr@2: // Max_size must be a power of 2.
williamr@2: template < __DFL_NON_TYPE_PARAM(size_t, _Max_size, _MAX_BYTES) >
williamr@2: class _Pthread_alloc {
williamr@2: 
williamr@2: public: // but only for internal use:
williamr@2: 
williamr@2:   typedef _Pthread_alloc_obj __obj;
williamr@2:   typedef _Pthread_alloc_per_thread_state<_Max_size> __state_type;
williamr@2:   typedef char value_type;
williamr@2: 
williamr@2:   // Allocates a chunk for nobjs of size size.  nobjs may be reduced
williamr@2:   // if it is inconvenient to allocate the requested number.
williamr@2:   static char *_S_chunk_alloc(size_t __size, size_t &__nobjs);
williamr@2: 
williamr@2:   enum {_S_ALIGN = _STLP_DATA_ALIGNMENT};
williamr@2: 
williamr@2:   static size_t _S_round_up(size_t __bytes) {
williamr@2:         return (((__bytes) + (int)_S_ALIGN-1) & ~((int)_S_ALIGN - 1));
williamr@2:   }
williamr@2:   static size_t _S_freelist_index(size_t __bytes) {
williamr@2:         return (((__bytes) + (int)_S_ALIGN-1)/(int)_S_ALIGN - 1);
williamr@2:   }
williamr@2: 
williamr@2: private:
williamr@2:   // Chunk allocation state. And other shared state.
williamr@2:   // Protected by _S_chunk_allocator_lock.
williamr@2:   static _STLP_mutex_base _S_chunk_allocator_lock;
williamr@2:   static char *_S_start_free;
williamr@2:   static char *_S_end_free;
williamr@2:   static size_t _S_heap_size;
williamr@2:   static _Pthread_alloc_per_thread_state<_Max_size>* _S_free_per_thread_states;
williamr@2:   static pthread_key_t _S_key;
williamr@2:   static bool _S_key_initialized;
williamr@2:         // Pthread key under which per thread state is stored. 
williamr@2:         // Allocator instances that are currently unclaimed by any thread.
williamr@2:   static void _S_destructor(void *instance);
williamr@2:         // Function to be called on thread exit to reclaim per thread
williamr@2:         // state.
williamr@2:   static _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();
williamr@2: public:
williamr@2:         // Return a recycled or new per thread state.
williamr@2:   static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();
williamr@2: private:
williamr@2:         // ensure that the current thread has an associated
williamr@2:         // per thread state.
williamr@2:   class _M_lock;
williamr@2:   friend class _M_lock;
williamr@2:   class _M_lock {
williamr@2:       public:
williamr@2:         _M_lock () { _S_chunk_allocator_lock._M_acquire_lock(); }
williamr@2:         ~_M_lock () { _S_chunk_allocator_lock._M_release_lock(); }
williamr@2:   };
williamr@2: 
williamr@2: public:
williamr@2: 
williamr@2:   /* n must be > 0      */
williamr@2:   static void * allocate(size_t __n)
williamr@2:   {
williamr@2:     __obj * volatile * __my_free_list;
williamr@2:     __obj * __RESTRICT __result;
williamr@2:     __state_type* __a;
williamr@2: 
williamr@2:     if (__n > _Max_size) {
williamr@2:         return(__malloc_alloc<0>::allocate(__n));
williamr@2:     }
williamr@2: 
williamr@2:     __a = _S_get_per_thread_state();
williamr@2: 
williamr@2:     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
williamr@2:     __result = *__my_free_list;
williamr@2:     if (__result == 0) {
williamr@2:         void *__r = __a -> _M_refill(_S_round_up(__n));
williamr@2:         return __r;
williamr@2:     }
williamr@2:     *__my_free_list = __result -> __free_list_link;
williamr@2:     return (__result);
williamr@2:   };
williamr@2: 
williamr@2:   /* p may not be 0 */
williamr@2:   static void deallocate(void *__p, size_t __n)
williamr@2:   {
williamr@2:     __obj *__q = (__obj *)__p;
williamr@2:     __obj * volatile * __my_free_list;
williamr@2:     __state_type* __a;
williamr@2: 
williamr@2:     if (__n > _Max_size) {
williamr@2:         __malloc_alloc<0>::deallocate(__p, __n);
williamr@2:         return;
williamr@2:     }
williamr@2: 
williamr@2:     __a = _S_get_per_thread_state();
williamr@2:     
williamr@2:     __my_free_list = __a->__free_list + _S_freelist_index(__n);
williamr@2:     __q -> __free_list_link = *__my_free_list;
williamr@2:     *__my_free_list = __q;
williamr@2:   }
williamr@2: 
williamr@2:   // boris : versions for per_thread_allocator
williamr@2:   /* n must be > 0      */
williamr@2:   static void * allocate(size_t __n, __state_type* __a)
williamr@2:   {
williamr@2:     __obj * volatile * __my_free_list;
williamr@2:     __obj * __RESTRICT __result;
williamr@2: 
williamr@2:     if (__n > _Max_size) {
williamr@2:         return(__malloc_alloc<0>::allocate(__n));
williamr@2:     }
williamr@2: 
williamr@2:     // boris : here, we have to lock per thread state, as we may be getting memory from
williamr@2:     // different thread pool.
williamr@2:     _STLP_mutex_lock __lock(__a->_M_lock);
williamr@2: 
williamr@2:     __my_free_list = __a -> __free_list + _S_freelist_index(__n);
williamr@2:     __result = *__my_free_list;
williamr@2:     if (__result == 0) {
williamr@2:         void *__r = __a -> _M_refill(_S_round_up(__n));
williamr@2:         return __r;
williamr@2:     }
williamr@2:     *__my_free_list = __result -> __free_list_link;
williamr@2:     return (__result);
williamr@2:   };
williamr@2: 
williamr@2:   /* p may not be 0 */
williamr@2:   static void deallocate(void *__p, size_t __n, __state_type* __a)
williamr@2:   {
williamr@2:     __obj *__q = (__obj *)__p;
williamr@2:     __obj * volatile * __my_free_list;
williamr@2: 
williamr@2:     if (__n > _Max_size) {
williamr@2:         __malloc_alloc<0>::deallocate(__p, __n);
williamr@2:         return;
williamr@2:     }
williamr@2: 
williamr@2:     // boris : here, we have to lock per thread state, as we may be returning memory from
williamr@2:     // different thread.
williamr@2:     _STLP_mutex_lock __lock(__a->_M_lock);
williamr@2: 
williamr@2:     __my_free_list = __a->__free_list + _S_freelist_index(__n);
williamr@2:     __q -> __free_list_link = *__my_free_list;
williamr@2:     *__my_free_list = __q;
williamr@2:   }
williamr@2: 
williamr@2:   static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);
williamr@2: 
williamr@2: } ;
williamr@2: 
williamr@2: # if defined (_STLP_USE_TEMPLATE_EXPORT)
williamr@2: _STLP_EXPORT_TEMPLATE_CLASS _Pthread_alloc<_MAX_BYTES>;
williamr@2: # endif
williamr@2: 
williamr@2: typedef _Pthread_alloc<_MAX_BYTES> __pthread_alloc;
williamr@2: typedef __pthread_alloc pthread_alloc;
williamr@2: 
williamr@2: template <class _Tp>
williamr@2: class pthread_allocator {
williamr@2:   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
williamr@2: public:
williamr@2:   typedef size_t     size_type;
williamr@2:   typedef ptrdiff_t  difference_type;
williamr@2:   typedef _Tp*       pointer;
williamr@2:   typedef const _Tp* const_pointer;
williamr@2:   typedef _Tp&       reference;
williamr@2:   typedef const _Tp& const_reference;
williamr@2:   typedef _Tp        value_type;
williamr@2: 
williamr@2: #ifdef _STLP_MEMBER_TEMPLATE_CLASSES
williamr@2:   template <class _NewType> struct rebind {
williamr@2:     typedef pthread_allocator<_NewType> other;
williamr@2:   };
williamr@2: #endif
williamr@2: 
williamr@2:   pthread_allocator() _STLP_NOTHROW {}
williamr@2:   pthread_allocator(const pthread_allocator<_Tp>& a) _STLP_NOTHROW {}
williamr@2: 
williamr@2: #if defined (_STLP_MEMBER_TEMPLATES) /* && defined (_STLP_FUNCTION_PARTIAL_ORDER) */
williamr@2:   template <class _OtherType> pthread_allocator(const pthread_allocator<_OtherType>&)
williamr@2: 		_STLP_NOTHROW {}
williamr@2: #endif
williamr@2: 
williamr@2:   ~pthread_allocator() _STLP_NOTHROW {}
williamr@2: 
williamr@2:   pointer address(reference __x) const { return &__x; }
williamr@2:   const_pointer address(const_reference __x) const { return &__x; }
williamr@2: 
williamr@2:   // __n is permitted to be 0.  The C++ standard says nothing about what
williamr@2:   // the return value is when __n == 0.
williamr@2:   _Tp* allocate(size_type __n, const void* = 0) {
williamr@2:     return __n != 0 ? __STATIC_CAST(_Tp*,_S_Alloc::allocate(__n * sizeof(_Tp)))
williamr@2:                     : 0;
williamr@2:   }
williamr@2: 
williamr@2:   // p is not permitted to be a null pointer.
williamr@2:   void deallocate(pointer __p, size_type __n)
williamr@2:     { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }
williamr@2: 
williamr@2:   size_type max_size() const _STLP_NOTHROW 
williamr@2:     { return size_t(-1) / sizeof(_Tp); }
williamr@2: 
williamr@2:   void construct(pointer __p, const _Tp& __val) { _STLP_PLACEMENT_NEW (__p) _Tp(__val); }
williamr@2:   void destroy(pointer _p) { _p->~_Tp(); }
williamr@2: };
williamr@2: 
williamr@2: _STLP_TEMPLATE_NULL
williamr@2: class _STLP_CLASS_DECLSPEC pthread_allocator<void> {
williamr@2: public:
williamr@2:   typedef size_t      size_type;
williamr@2:   typedef ptrdiff_t   difference_type;
williamr@2:   typedef void*       pointer;
williamr@2:   typedef const void* const_pointer;
williamr@2:   typedef void        value_type;
williamr@2: #ifdef _STLP_MEMBER_TEMPLATE_CLASSES
williamr@2:   template <class _NewType> struct rebind {
williamr@2:     typedef pthread_allocator<_NewType> other;
williamr@2:   };
williamr@2: #endif
williamr@2: };
williamr@2: 
williamr@2: template <class _T1, class _T2>
williamr@2: inline bool operator==(const pthread_allocator<_T1>&,
williamr@2:                        const pthread_allocator<_T2>& a2) 
williamr@2: {
williamr@2:   return true;
williamr@2: }
williamr@2: 
williamr@2: #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
williamr@2: template <class _T1, class _T2>
williamr@2: inline bool operator!=(const pthread_allocator<_T1>&,
williamr@2:                        const pthread_allocator<_T2>&)
williamr@2: {
williamr@2:   return false;
williamr@2: }
williamr@2: #endif
williamr@2: 
williamr@2: 
williamr@2: #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
williamr@2: 
williamr@2: # ifdef _STLP_USE_RAW_SGI_ALLOCATORS
williamr@2: template <class _Tp, size_t _Max_size>
williamr@2: struct _Alloc_traits<_Tp, _Pthread_alloc<_Max_size> >
williamr@2: {
williamr@2:   typedef __allocator<_Tp, _Pthread_alloc<_Max_size> > 
williamr@2:           allocator_type;
williamr@2: };
williamr@2: # endif
williamr@2: 
williamr@2: template <class _Tp, class _Atype>
williamr@2: struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >
williamr@2: {
williamr@2:   typedef pthread_allocator<_Tp> allocator_type;
williamr@2: };
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: #if !defined (_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM)
williamr@2: 
williamr@2: template <class _Tp1, class _Tp2>
williamr@2: inline pthread_allocator<_Tp2>&
williamr@2: __stl_alloc_rebind(pthread_allocator<_Tp1>& __x, const _Tp2*) {
williamr@2:   return (pthread_allocator<_Tp2>&)__x;
williamr@2: }
williamr@2: 
williamr@2: template <class _Tp1, class _Tp2>
williamr@2: inline pthread_allocator<_Tp2>
williamr@2: __stl_alloc_create(pthread_allocator<_Tp1>&, const _Tp2*) {
williamr@2:   return pthread_allocator<_Tp2>();
williamr@2: }
williamr@2: 
williamr@2: #endif /* _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM */
williamr@2: 
williamr@2: //
williamr@2: // per_thread_allocator<> : this allocator always return memory to the same thread 
williamr@2: // it was allocated from.
williamr@2: //
williamr@2: 
williamr@2: template <class _Tp>
williamr@2: class per_thread_allocator {
williamr@2:   typedef pthread_alloc _S_Alloc;          // The underlying allocator.
williamr@2:   typedef pthread_alloc::__state_type __state_type;
williamr@2: public:
williamr@2:   typedef size_t     size_type;
williamr@2:   typedef ptrdiff_t  difference_type;
williamr@2:   typedef _Tp*       pointer;
williamr@2:   typedef const _Tp* const_pointer;
williamr@2:   typedef _Tp&       reference;
williamr@2:   typedef const _Tp& const_reference;
williamr@2:   typedef _Tp        value_type;
williamr@2: 
williamr@2: #ifdef _STLP_MEMBER_TEMPLATE_CLASSES
williamr@2:   template <class _NewType> struct rebind {
williamr@2:     typedef per_thread_allocator<_NewType> other;
williamr@2:   };
williamr@2: #endif
williamr@2: 
williamr@2:   per_thread_allocator() _STLP_NOTHROW { 
williamr@2:     _M_state = _S_Alloc::_S_get_per_thread_state();
williamr@2:   }
williamr@2:   per_thread_allocator(const per_thread_allocator<_Tp>& __a) _STLP_NOTHROW : _M_state(__a._M_state){}
williamr@2: 
williamr@2: #if defined (_STLP_MEMBER_TEMPLATES) /* && defined (_STLP_FUNCTION_PARTIAL_ORDER) */
williamr@2:   template <class _OtherType> per_thread_allocator(const per_thread_allocator<_OtherType>& __a)
williamr@2: 		_STLP_NOTHROW : _M_state(__a._M_state) {}
williamr@2: #endif
williamr@2: 
williamr@2:   ~per_thread_allocator() _STLP_NOTHROW {}
williamr@2: 
williamr@2:   pointer address(reference __x) const { return &__x; }
williamr@2:   const_pointer address(const_reference __x) const { return &__x; }
williamr@2: 
williamr@2:   // __n is permitted to be 0.  The C++ standard says nothing about what
williamr@2:   // the return value is when __n == 0.
williamr@2:   _Tp* allocate(size_type __n, const void* = 0) {
williamr@2:     return __n != 0 ? __STATIC_CAST(_Tp*,_S_Alloc::allocate(__n * sizeof(_Tp), _M_state)): 0;
williamr@2:   }
williamr@2: 
williamr@2:   // p is not permitted to be a null pointer.
williamr@2:   void deallocate(pointer __p, size_type __n)
williamr@2:     { _S_Alloc::deallocate(__p, __n * sizeof(_Tp), _M_state); }
williamr@2: 
williamr@2:   size_type max_size() const _STLP_NOTHROW 
williamr@2:     { return size_t(-1) / sizeof(_Tp); }
williamr@2: 
williamr@2:   void construct(pointer __p, const _Tp& __val) { _STLP_PLACEMENT_NEW (__p) _Tp(__val); }
williamr@2:   void destroy(pointer _p) { _p->~_Tp(); }
williamr@2: 
williamr@2:   // state is being kept here
williamr@2:   __state_type* _M_state;
williamr@2: };
williamr@2: 
williamr@2: _STLP_TEMPLATE_NULL
williamr@2: class _STLP_CLASS_DECLSPEC per_thread_allocator<void> {
williamr@2: public:
williamr@2:   typedef size_t      size_type;
williamr@2:   typedef ptrdiff_t   difference_type;
williamr@2:   typedef void*       pointer;
williamr@2:   typedef const void* const_pointer;
williamr@2:   typedef void        value_type;
williamr@2: #ifdef _STLP_MEMBER_TEMPLATE_CLASSES
williamr@2:   template <class _NewType> struct rebind {
williamr@2:     typedef per_thread_allocator<_NewType> other;
williamr@2:   };
williamr@2: #endif
williamr@2: };
williamr@2: 
williamr@2: template <class _T1, class _T2>
williamr@2: inline bool operator==(const per_thread_allocator<_T1>& __a1,
williamr@2:                        const per_thread_allocator<_T2>& __a2) 
williamr@2: {
williamr@2:   return __a1._M_state == __a2._M_state;
williamr@2: }
williamr@2: 
williamr@2: #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
williamr@2: template <class _T1, class _T2>
williamr@2: inline bool operator!=(const per_thread_allocator<_T1>& __a1,
williamr@2:                        const per_thread_allocator<_T2>& __a2)
williamr@2: {
williamr@2:   return __a1._M_state != __a2._M_state;
williamr@2: }
williamr@2: #endif
williamr@2: 
williamr@2: 
williamr@2: #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
williamr@2: 
williamr@2: template <class _Tp, class _Atype>
williamr@2: struct _Alloc_traits<_Tp, per_thread_allocator<_Atype> >
williamr@2: {
williamr@2:   typedef per_thread_allocator<_Tp> allocator_type;
williamr@2: };
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: #if !defined (_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM)
williamr@2: 
williamr@2: template <class _Tp1, class _Tp2>
williamr@2: inline per_thread_allocator<_Tp2>&
williamr@2: __stl_alloc_rebind(per_thread_allocator<_Tp1>& __x, const _Tp2*) {
williamr@2:   return (per_thread_allocator<_Tp2>&)__x;
williamr@2: }
williamr@2: 
williamr@2: template <class _Tp1, class _Tp2>
williamr@2: inline per_thread_allocator<_Tp2>
williamr@2: __stl_alloc_create(per_thread_allocator<_Tp1>&, const _Tp2*) {
williamr@2:   return per_thread_allocator<_Tp2>();
williamr@2: }
williamr@2: 
williamr@2: #endif /* _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM */
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) && !defined (_STLP_LINK_TIME_INSTANTIATION)
williamr@2: #  include <stl/_pthread_alloc.c>
williamr@2: # endif
williamr@2: 
williamr@2: #endif /* _STLP_PTHREAD_ALLOC */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: