home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / bits / pthread_allocimpl.h < prev    next >
Encoding:
C/C++ Source or Header  |  2003-12-15  |  17.3 KB  |  526 lines
  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:
  526.