Back to index

lightning-sunbird  0.9+nobinonly
gc_alloc.h
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved.
00003  *
00004  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00005  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00006  *
00007  * Permission is hereby granted to use or copy this program
00008  * for any purpose,  provided the above notices are retained on all copies.
00009  * Permission to modify the code and to distribute modified code is granted,
00010  * provided the above notices are retained, and a notice that the code was
00011  * modified is included with the above copyright notice.
00012  */
00013 
00014 //
00015 // This is a C++ header file that is intended to replace the SGI STL
00016 // alloc.h.
00017 //
00018 // This assumes the collector has been compiled with -DATOMIC_UNCOLLECTABLE
00019 // and -DALL_INTERIOR_POINTERS.  We also recommend
00020 // -DREDIRECT_MALLOC=GC_uncollectable_malloc.
00021 //
00022 // Some of this could be faster in the explicit deallocation case.  In particular,
00023 // we spend too much time clearing objects on the free lists.  That could be avoided.
00024 //
00025 // This uses template classes with static members, and hence does not work
00026 // with g++ 2.7.2 and earlier.
00027 //
00028 
00029 #include "gc.h"
00030 
00031 #ifndef GC_ALLOC_H
00032 
00033 #define GC_ALLOC_H
00034 #define __ALLOC_H    // Prevent inclusion of the default version.  Ugly.
00035 #define __SGI_STL_ALLOC_H
00036 #define __SGI_STL_INTERNAL_ALLOC_H
00037 
00038 #ifndef __ALLOC
00039 #   define __ALLOC alloc
00040 #endif
00041 
00042 #include <stddef.h>
00043 #include <string.h>
00044 
00045 // The following is just replicated from the conventional SGI alloc.h:
00046 
00047 template<class T, class alloc>
00048 class simple_alloc {
00049 
00050 public:
00051     static T *allocate(size_t n)
00052                 { return 0 == n? 0 : (T*) alloc::allocate(n * sizeof (T)); }
00053     static T *allocate(void)
00054                 { return (T*) alloc::allocate(sizeof (T)); }
00055     static void deallocate(T *p, size_t n)
00056                 { if (0 != n) alloc::deallocate(p, n * sizeof (T)); }
00057     static void deallocate(T *p)
00058                 { alloc::deallocate(p, sizeof (T)); }
00059 };
00060 
00061 #include "gc.h"
00062 
00063 // The following need to match collector data structures.
00064 // We can't include gc_priv.h, since that pulls in way too much stuff.
00065 // This should eventually be factored out into another include file.
00066 
00067 extern "C" {
00068     extern void ** const GC_objfreelist_ptr;
00069     extern void ** const GC_aobjfreelist_ptr;
00070     extern void ** const GC_uobjfreelist_ptr;
00071     extern void ** const GC_auobjfreelist_ptr;
00072 
00073     extern void GC_incr_words_allocd(size_t words);
00074     extern void GC_incr_mem_freed(size_t words);
00075 
00076     extern char * GC_generic_malloc_words_small(size_t word, int kind);
00077 }
00078 
00079 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
00080 // AUNCOLLECTABLE in gc_priv.h.
00081 
00082 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
00083        GC_AUNCOLLECTABLE = 3 };
00084 
00085 enum { GC_max_fast_bytes = 255 };
00086 
00087 enum { GC_bytes_per_word = sizeof(char *) };
00088 
00089 enum { GC_byte_alignment = 8 };
00090 
00091 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
00092 
00093 inline void * &GC_obj_link(void * p)
00094 {   return *(void **)p;  }
00095 
00096 // Compute a number of words >= n+1 bytes.
00097 // The +1 allows for pointers one past the end.
00098 inline size_t GC_round_up(size_t n)
00099 {
00100     return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
00101 }
00102 
00103 // The same but don't allow for extra byte.
00104 inline size_t GC_round_up_uncollectable(size_t n)
00105 {
00106     return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
00107 }
00108 
00109 template <int dummy>
00110 class GC_aux_template {
00111 public:
00112   // File local count of allocated words.  Occasionally this is
00113   // added into the global count.  A separate count is necessary since the
00114   // real one must be updated with a procedure call.
00115   static size_t GC_words_recently_allocd;
00116 
00117   // Same for uncollectable mmory.  Not yet reflected in either
00118   // GC_words_recently_allocd or GC_non_gc_bytes.
00119   static size_t GC_uncollectable_words_recently_allocd;
00120 
00121   // Similar counter for explicitly deallocated memory.
00122   static size_t GC_mem_recently_freed;
00123 
00124   // Again for uncollectable memory.
00125   static size_t GC_uncollectable_mem_recently_freed;
00126 
00127   static void * GC_out_of_line_malloc(size_t nwords, int kind);
00128 };
00129 
00130 template <int dummy>
00131 size_t GC_aux_template<dummy>::GC_words_recently_allocd = 0;
00132 
00133 template <int dummy>
00134 size_t GC_aux_template<dummy>::GC_uncollectable_words_recently_allocd = 0;
00135 
00136 template <int dummy>
00137 size_t GC_aux_template<dummy>::GC_mem_recently_freed = 0;
00138 
00139 template <int dummy>
00140 size_t GC_aux_template<dummy>::GC_uncollectable_mem_recently_freed = 0;
00141 
00142 template <int dummy>
00143 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
00144 {
00145     GC_words_recently_allocd += GC_uncollectable_words_recently_allocd;
00146     GC_non_gc_bytes +=
00147                 GC_bytes_per_word * GC_uncollectable_words_recently_allocd;
00148     GC_uncollectable_words_recently_allocd = 0;
00149 
00150     GC_mem_recently_freed += GC_uncollectable_mem_recently_freed;
00151     GC_non_gc_bytes -= 
00152                 GC_bytes_per_word * GC_uncollectable_mem_recently_freed;
00153     GC_uncollectable_mem_recently_freed = 0;
00154 
00155     GC_incr_words_allocd(GC_words_recently_allocd);
00156     GC_words_recently_allocd = 0;
00157 
00158     GC_incr_mem_freed(GC_mem_recently_freed);
00159     GC_mem_recently_freed = 0;
00160 
00161     return GC_generic_malloc_words_small(nwords, kind);
00162 }
00163 
00164 typedef GC_aux_template<0> GC_aux;
00165 
00166 // A fast, single-threaded, garbage-collected allocator
00167 // We assume the first word will be immediately overwritten.
00168 // In this version, deallocation is not a noop, and explicit
00169 // deallocation is likely to help performance.
00170 template <int dummy>
00171 class single_client_gc_alloc_template {
00172     public:
00173        static void * allocate(size_t n)
00174         {
00175            size_t nwords = GC_round_up(n);
00176            void ** flh;
00177            void * op;
00178 
00179            if (n > GC_max_fast_bytes) return GC_malloc(n);
00180            flh = GC_objfreelist_ptr + nwords;
00181            if (0 == (op = *flh)) {
00182               return GC_aux::GC_out_of_line_malloc(nwords, GC_NORMAL);
00183            }
00184            *flh = GC_obj_link(op);
00185            GC_aux::GC_words_recently_allocd += nwords;
00186            return op;
00187         }
00188        static void * ptr_free_allocate(size_t n)
00189         {
00190            size_t nwords = GC_round_up(n);
00191            void ** flh;
00192            void * op;
00193 
00194            if (n > GC_max_fast_bytes) return GC_malloc_atomic(n);
00195            flh = GC_aobjfreelist_ptr + nwords;
00196            if (0 == (op = *flh)) {
00197               return GC_aux::GC_out_of_line_malloc(nwords, GC_PTRFREE);
00198            }
00199            *flh = GC_obj_link(op);
00200            GC_aux::GC_words_recently_allocd += nwords;
00201            return op;
00202         }
00203        static void deallocate(void *p, size_t n)
00204        {
00205             size_t nwords = GC_round_up(n);
00206             void ** flh;
00207           
00208            if (n > GC_max_fast_bytes)  {
00209               GC_free(p);
00210            } else {
00211                flh = GC_objfreelist_ptr + nwords;
00212                GC_obj_link(p) = *flh;
00213               memset((char *)p + GC_bytes_per_word, 0,
00214                      GC_bytes_per_word * (nwords - 1));
00215                *flh = p;
00216                GC_aux::GC_mem_recently_freed += nwords;
00217            }
00218        }
00219        static void ptr_free_deallocate(void *p, size_t n)
00220        {
00221             size_t nwords = GC_round_up(n);
00222             void ** flh;
00223           
00224            if (n > GC_max_fast_bytes) {
00225               GC_free(p);
00226            } else {
00227               flh = GC_aobjfreelist_ptr + nwords;
00228               GC_obj_link(p) = *flh;
00229               *flh = p;
00230               GC_aux::GC_mem_recently_freed += nwords;
00231            }
00232        }
00233 };
00234 
00235 typedef single_client_gc_alloc_template<0> single_client_gc_alloc;
00236 
00237 // Once more, for uncollectable objects.
00238 template <int dummy>
00239 class single_client_alloc_template {
00240     public:
00241        static void * allocate(size_t n)
00242         {
00243            size_t nwords = GC_round_up_uncollectable(n);
00244            void ** flh;
00245            void * op;
00246 
00247            if (n > GC_max_fast_bytes) return GC_malloc_uncollectable(n);
00248            flh = GC_uobjfreelist_ptr + nwords;
00249            if (0 == (op = *flh)) {
00250               return GC_aux::GC_out_of_line_malloc(nwords, GC_UNCOLLECTABLE);
00251            }
00252            *flh = GC_obj_link(op);
00253            GC_aux::GC_uncollectable_words_recently_allocd += nwords;
00254            return op;
00255         }
00256        static void * ptr_free_allocate(size_t n)
00257         {
00258            size_t nwords = GC_round_up_uncollectable(n);
00259            void ** flh;
00260            void * op;
00261 
00262            if (n > GC_max_fast_bytes) return GC_malloc_atomic_uncollectable(n);
00263            flh = GC_auobjfreelist_ptr + nwords;
00264            if (0 == (op = *flh)) {
00265               return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
00266            }
00267            *flh = GC_obj_link(op);
00268            GC_aux::GC_uncollectable_words_recently_allocd += nwords;
00269            return op;
00270         }
00271        static void deallocate(void *p, size_t n)
00272        {
00273             size_t nwords = GC_round_up_uncollectable(n);
00274             void ** flh;
00275           
00276            if (n > GC_max_fast_bytes)  {
00277               GC_free(p);
00278            } else {
00279                flh = GC_uobjfreelist_ptr + nwords;
00280                GC_obj_link(p) = *flh;
00281                *flh = p;
00282                GC_aux::GC_uncollectable_mem_recently_freed += nwords;
00283            }
00284        }
00285        static void ptr_free_deallocate(void *p, size_t n)
00286        {
00287             size_t nwords = GC_round_up_uncollectable(n);
00288             void ** flh;
00289           
00290            if (n > GC_max_fast_bytes) {
00291               GC_free(p);
00292            } else {
00293               flh = GC_auobjfreelist_ptr + nwords;
00294               GC_obj_link(p) = *flh;
00295               *flh = p;
00296               GC_aux::GC_uncollectable_mem_recently_freed += nwords;
00297            }
00298        }
00299 };
00300 
00301 typedef single_client_alloc_template<0> single_client_alloc;
00302 
00303 template < int dummy >
00304 class gc_alloc_template {
00305     public:
00306        static void * allocate(size_t n) { return GC_malloc(n); }
00307        static void * ptr_free_allocate(size_t n)
00308               { return GC_malloc_atomic(n); }
00309        static void deallocate(void *, size_t) { }
00310        static void ptr_free_deallocate(void *, size_t) { }
00311 };
00312 
00313 typedef gc_alloc_template < 0 > gc_alloc;
00314 
00315 template < int dummy >
00316 class alloc_template {
00317     public:
00318        static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
00319        static void * ptr_free_allocate(size_t n)
00320               { return GC_malloc_atomic_uncollectable(n); }
00321        static void deallocate(void *p, size_t) { GC_free(p); }
00322        static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
00323 };
00324 
00325 typedef alloc_template < 0 > alloc;
00326 
00327 #ifdef _SGI_SOURCE
00328 
00329 // We want to specialize simple_alloc so that it does the right thing
00330 // for all pointerfree types.  At the moment there is no portable way to
00331 // even approximate that.  The following approximation should work for
00332 // SGI compilers, and perhaps some others.
00333 
00334 # define __GC_SPECIALIZE(T,alloc) \
00335 class simple_alloc<T, alloc> { \
00336 public: \
00337     static T *allocate(size_t n) \
00338        { return 0 == n? 0 : \
00339                       (T*) alloc::ptr_free_allocate(n * sizeof (T)); } \
00340     static T *allocate(void) \
00341        { return (T*) alloc::ptr_free_allocate(sizeof (T)); } \
00342     static void deallocate(T *p, size_t n) \
00343        { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
00344     static void deallocate(T *p) \
00345        { alloc::ptr_free_deallocate(p, sizeof (T)); } \
00346 };
00347 
00348 __GC_SPECIALIZE(char, gc_alloc)
00349 __GC_SPECIALIZE(int, gc_alloc)
00350 __GC_SPECIALIZE(unsigned, gc_alloc)
00351 __GC_SPECIALIZE(float, gc_alloc)
00352 __GC_SPECIALIZE(double, gc_alloc)
00353 
00354 __GC_SPECIALIZE(char, alloc)
00355 __GC_SPECIALIZE(int, alloc)
00356 __GC_SPECIALIZE(unsigned, alloc)
00357 __GC_SPECIALIZE(float, alloc)
00358 __GC_SPECIALIZE(double, alloc)
00359 
00360 __GC_SPECIALIZE(char, single_client_gc_alloc)
00361 __GC_SPECIALIZE(int, single_client_gc_alloc)
00362 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
00363 __GC_SPECIALIZE(float, single_client_gc_alloc)
00364 __GC_SPECIALIZE(double, single_client_gc_alloc)
00365 
00366 __GC_SPECIALIZE(char, single_client_alloc)
00367 __GC_SPECIALIZE(int, single_client_alloc)
00368 __GC_SPECIALIZE(unsigned, single_client_alloc)
00369 __GC_SPECIALIZE(float, single_client_alloc)
00370 __GC_SPECIALIZE(double, single_client_alloc)
00371 
00372 #ifdef __STL_USE_STD_ALLOCATORS
00373 
00374 ???copy stuff from stl_alloc.h or remove it to a different file ???
00375 
00376 #endif /* __STL_USE_STD_ALLOCATORS */
00377 
00378 #endif /* _SGI_SOURCE */
00379 
00380 #endif /* GC_ALLOC_H */