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