pthread_alloc
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:10k
源码类别:

STL

开发平台:

Visual C++

  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. #ifndef __SGI_STL_PTHREAD_ALLOC
  14. #define __SGI_STL_PTHREAD_ALLOC
  15. // Pthread-specific node allocator.
  16. // This is similar to the default allocator, except that free-list
  17. // information is kept separately for each thread, avoiding locking.
  18. // This should be reasonably fast even in the presence of threads.
  19. // The down side is that storage may not be well-utilized.
  20. // It is not an error to allocate memory in thread A and deallocate
  21. // it n thread B.  But this effectively transfers ownership of the memory,
  22. // so that it can only be reallocated by thread B.  Thus this can effectively
  23. // result in a storage leak if it's done on a regular basis.
  24. // It can also result in frequent sharing of
  25. // cache lines among processors, with potentially serious performance
  26. // consequences.
  27. #include <stl_config.h>
  28. #include <stl_alloc.h>
  29. #ifndef __RESTRICT
  30. #  define __RESTRICT
  31. #endif
  32. __STL_BEGIN_NAMESPACE
  33. // Note that this class has nonstatic members.  We instantiate it once
  34. // per thread.
  35. template <bool dummy>
  36. class __pthread_alloc_template {
  37. private:
  38.   enum {ALIGN = 8};
  39.   enum {MAX_BYTES = 128};  // power of 2
  40.   enum {NFREELISTS = MAX_BYTES/ALIGN};
  41.   union obj {
  42.         union obj * free_list_link;
  43.         char client_data[ALIGN];    /* The client sees this.        */
  44.   };
  45.   // Per instance state
  46.   obj* volatile free_list[NFREELISTS]; 
  47.   __pthread_alloc_template<dummy>* next;  // Free list link
  48.   static size_t ROUND_UP(size_t bytes) {
  49. return (((bytes) + ALIGN-1) & ~(ALIGN - 1));
  50.   }
  51.   static size_t FREELIST_INDEX(size_t bytes) {
  52. return (((bytes) + ALIGN-1)/ALIGN - 1);
  53.   }
  54.   // Returns an object of size n, and optionally adds to size n free list.
  55.   void *refill(size_t n);
  56.   // Allocates a chunk for nobjs of size "size".  nobjs may be reduced
  57.   // if it is inconvenient to allocate the requested number.
  58.   static char *chunk_alloc(size_t size, int &nobjs);
  59.   // Chunk allocation state. And other shared state.
  60.   // Protected by chunk_allocator_lock.
  61.   static pthread_mutex_t chunk_allocator_lock;
  62.   static char *start_free;
  63.   static char *end_free;
  64.   static size_t heap_size;
  65.   static __pthread_alloc_template<dummy>* free_allocators;
  66.   static pthread_key_t key;
  67.   static bool key_initialized;
  68. // Pthread key under which allocator is stored. 
  69. // Allocator instances that are currently unclaimed by any thread.
  70.   static void destructor(void *instance);
  71. // Function to be called on thread exit to reclaim allocator
  72. // instance.
  73.   static __pthread_alloc_template<dummy> *new_allocator();
  74. // Return a recycled or new allocator instance.
  75.   static __pthread_alloc_template<dummy> *get_allocator_instance();
  76. // ensure that the current thread has an associated
  77. // allocator instance.
  78.   class lock {
  79.       public:
  80. lock () { pthread_mutex_lock(&chunk_allocator_lock); }
  81. ~lock () { pthread_mutex_unlock(&chunk_allocator_lock); }
  82.   };
  83.   friend class lock;
  84. public:
  85.   __pthread_alloc_template() : next(0)
  86.   {
  87.     memset((void *)free_list, 0, NFREELISTS * sizeof(obj *));
  88.   }
  89.   /* n must be > 0 */
  90.   static void * allocate(size_t n)
  91.   {
  92.     obj * volatile * my_free_list;
  93.     obj * __RESTRICT result;
  94.     __pthread_alloc_template<dummy>* a;
  95.     if (n > MAX_BYTES) {
  96. return(malloc(n));
  97.     }
  98.     if (!key_initialized ||
  99.         !(a = (__pthread_alloc_template<dummy>*)
  100. pthread_getspecific(key))) {
  101. a = get_allocator_instance();
  102.     }
  103.     my_free_list = a -> free_list + FREELIST_INDEX(n);
  104.     result = *my_free_list;
  105.     if (result == 0) {
  106.      void *r = a -> refill(ROUND_UP(n));
  107. return r;
  108.     }
  109.     *my_free_list = result -> free_list_link;
  110.     return (result);
  111.   };
  112.   /* p may not be 0 */
  113.   static void deallocate(void *p, size_t n)
  114.   {
  115.     obj *q = (obj *)p;
  116.     obj * volatile * my_free_list;
  117.     __pthread_alloc_template<dummy>* a;
  118.     if (n > MAX_BYTES) {
  119. free(p);
  120. return;
  121.     }
  122.     if (!key_initialized ||
  123.         !(a = (__pthread_alloc_template<dummy>*)
  124. pthread_getspecific(key))) {
  125. a = get_allocator_instance();
  126.     }
  127.     my_free_list = a->free_list + FREELIST_INDEX(n);
  128.     q -> free_list_link = *my_free_list;
  129.     *my_free_list = q;
  130.   }
  131.   static void * reallocate(void *p, size_t old_sz, size_t new_sz);
  132. } ;
  133. typedef __pthread_alloc_template<false> pthread_alloc;
  134. template <bool dummy>
  135. void __pthread_alloc_template<dummy>::destructor(void * instance)
  136. {
  137.     __pthread_alloc_template<dummy>* a =
  138. (__pthread_alloc_template<dummy>*)instance;
  139.     a -> next = free_allocators;
  140.     free_allocators = a;
  141. }
  142. template <bool dummy>
  143. __pthread_alloc_template<dummy>*
  144. __pthread_alloc_template<dummy>::new_allocator()
  145. {
  146.     if (0 != free_allocators) {
  147. __pthread_alloc_template<dummy>* result = free_allocators;
  148. free_allocators = free_allocators -> next;
  149. return result;
  150.     } else {
  151. return new __pthread_alloc_template<dummy>;
  152.     }
  153. }
  154. template <bool dummy>
  155. __pthread_alloc_template<dummy>*
  156. __pthread_alloc_template<dummy>::get_allocator_instance()
  157. {
  158.     __pthread_alloc_template<dummy>* result;
  159.     if (!key_initialized) {
  160.      /*REFERENCED*/
  161. lock lock_instance;
  162. if (!key_initialized) {
  163.     if (pthread_key_create(&key, destructor)) {
  164. abort();  // failed
  165.     }
  166.     key_initialized = true;
  167. }
  168.     }
  169.     result = new_allocator();
  170.     if (pthread_setspecific(key, result)) abort();
  171.     return result;
  172. }
  173. /* We allocate memory in large chunks in order to avoid fragmenting */
  174. /* the malloc heap too much. */
  175. /* We assume that size is properly aligned. */
  176. template <bool dummy>
  177. char *__pthread_alloc_template<dummy>
  178. ::chunk_alloc(size_t size, int &nobjs)
  179. {
  180.   {
  181.     char * result;
  182.     size_t total_bytes;
  183.     size_t bytes_left;
  184.     /*REFERENCED*/
  185.     lock lock_instance; // Acquire lock for this routine
  186.     total_bytes = size * nobjs;
  187.     bytes_left = end_free - start_free;
  188.     if (bytes_left >= total_bytes) {
  189. result = start_free;
  190. start_free += total_bytes;
  191. return(result);
  192.     } else if (bytes_left >= size) {
  193. nobjs = bytes_left/size;
  194. total_bytes = size * nobjs;
  195. result = start_free;
  196. start_free += total_bytes;
  197. return(result);
  198.     } else {
  199. size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
  200. // Try to make use of the left-over piece.
  201. if (bytes_left > 0) {
  202.     __pthread_alloc_template<dummy>* a = 
  203. (__pthread_alloc_template<dummy>*)pthread_getspecific(key);
  204.     obj * volatile * my_free_list =
  205. a->free_list + FREELIST_INDEX(bytes_left);
  206.             ((obj *)start_free) -> free_list_link = *my_free_list;
  207.             *my_free_list = (obj *)start_free;
  208. }
  209. # ifdef _SGI_SOURCE
  210.   // Try to get memory that's aligned on something like a
  211.   // cache line boundary, so as to avoid parceling out
  212.   // parts of the same line to different threads and thus
  213.   // possibly different processors.
  214.   {
  215.     const int cache_line_size = 128;  // probable upper bound
  216.     bytes_to_get &= ~(cache_line_size-1);
  217.     start_free = (char *)memalign(cache_line_size, bytes_to_get); 
  218.     if (0 == start_free) {
  219.       start_free = (char *)malloc_alloc::allocate(bytes_to_get);
  220.     }
  221.   }
  222. # else  /* !SGI_SOURCE */
  223.   start_free = (char *)malloc_alloc::allocate(bytes_to_get);
  224. #       endif
  225. heap_size += bytes_to_get;
  226. end_free = start_free + bytes_to_get;
  227.     }
  228.   }
  229.   // lock is released here
  230.   return(chunk_alloc(size, nobjs));
  231. }
  232. /* Returns an object of size n, and optionally adds to size n free list.*/
  233. /* We assume that n is properly aligned. */
  234. /* We hold the allocation lock. */
  235. template <bool dummy>
  236. void *__pthread_alloc_template<dummy>
  237. ::refill(size_t n)
  238. {
  239.     int nobjs = 128;
  240.     char * chunk = chunk_alloc(n, nobjs);
  241.     obj * volatile * my_free_list;
  242.     obj * result;
  243.     obj * current_obj, * next_obj;
  244.     int i;
  245.     if (1 == nobjs)  {
  246. return(chunk);
  247.     }
  248.     my_free_list = free_list + FREELIST_INDEX(n);
  249.     /* Build free list in chunk */
  250.       result = (obj *)chunk;
  251.       *my_free_list = next_obj = (obj *)(chunk + n);
  252.       for (i = 1; ; i++) {
  253. current_obj = next_obj;
  254. next_obj = (obj *)((char *)next_obj + n);
  255. if (nobjs - 1 == i) {
  256.     current_obj -> free_list_link = 0;
  257.     break;
  258. } else {
  259.     current_obj -> free_list_link = next_obj;
  260. }
  261.       }
  262.     return(result);
  263. }
  264. template <bool dummy>
  265. void *__pthread_alloc_template<dummy>
  266. ::reallocate(void *p, size_t old_sz, size_t new_sz)
  267. {
  268.     void * result;
  269.     size_t copy_sz;
  270.     if (old_sz > MAX_BYTES && new_sz > MAX_BYTES) {
  271. return(realloc(p, new_sz));
  272.     }
  273.     if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
  274.     result = allocate(new_sz);
  275.     copy_sz = new_sz > old_sz? old_sz : new_sz;
  276.     memcpy(result, p, copy_sz);
  277.     deallocate(p, old_sz);
  278.     return(result);
  279. }
  280. template <bool dummy>
  281. __pthread_alloc_template<dummy> *
  282. __pthread_alloc_template<dummy>::free_allocators = 0;
  283. template <bool dummy>
  284. pthread_key_t __pthread_alloc_template<dummy>::key;
  285. template <bool dummy>
  286. bool __pthread_alloc_template<dummy>::key_initialized = false;
  287. template <bool dummy>
  288. pthread_mutex_t __pthread_alloc_template<dummy>::chunk_allocator_lock
  289. = PTHREAD_MUTEX_INITIALIZER;
  290. template <bool dummy>
  291. char *__pthread_alloc_template<dummy>
  292. ::start_free = 0;
  293. template <bool dummy>
  294. char *__pthread_alloc_template<dummy>
  295. ::end_free = 0;
  296. template <bool dummy>
  297. size_t __pthread_alloc_template<dummy>
  298. ::heap_size = 0;
  299. __STL_END_NAMESPACE
  300. #endif /* __SGI_STL_PTHREAD_ALLOC */
  301. // Local Variables:
  302. // mode:C++
  303. // End: