Back to index

lightning-sunbird  0.9+nobinonly
new_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 revision of gc_alloc.h for SGI STL versions > 3.0
00016 // Unlike earlier versions, it supplements the standard "alloc.h"
00017 // instead of replacing it.
00018 //
00019 // This is sloppy about variable names used in header files.
00020 // It also doesn't yet understand the new header file names or
00021 // namespaces.
00022 //
00023 // This assumes the collector has been compiled with -DATOMIC_UNCOLLECTABLE
00024 // and -DALL_INTERIOR_POINTERS.  We also recommend
00025 // -DREDIRECT_MALLOC=GC_uncollectable_malloc.
00026 //
00027 // Some of this could be faster in the explicit deallocation case.
00028 // In particular, we spend too much time clearing objects on the
00029 // free lists.  That could be avoided.
00030 //
00031 // This uses template classes with static members, and hence does not work
00032 // with g++ 2.7.2 and earlier.
00033 //
00034 // Unlike its predecessor, this one simply defines
00035 //     gc_alloc
00036 //     single_client_gc_alloc
00037 //     traceable_alloc
00038 //     single_client_traceable_alloc
00039 //
00040 // It does not redefine alloc.  Nor does it change the default allocator,
00041 // though the user may wish to do so.  (The argument against changing
00042 // the default allocator is that it may introduce subtle link compatibility
00043 // problems.  The argument for changing it is that the usual default
00044 // allocator is usually a very bad choice for a garbage collected environment.)
00045 //
00046 
00047 #ifndef GC_ALLOC_H
00048 
00049 #include "gc.h"
00050 #include <alloc.h>
00051 
00052 #define GC_ALLOC_H
00053 
00054 #include <stddef.h>
00055 #include <string.h>
00056 
00057 // The following need to match collector data structures.
00058 // We can't include gc_priv.h, since that pulls in way too much stuff.
00059 // This should eventually be factored out into another include file.
00060 
00061 extern "C" {
00062     extern void ** const GC_objfreelist_ptr;
00063     extern void ** const GC_aobjfreelist_ptr;
00064     extern void ** const GC_uobjfreelist_ptr;
00065     extern void ** const GC_auobjfreelist_ptr;
00066 
00067     extern void GC_incr_words_allocd(size_t words);
00068     extern void GC_incr_mem_freed(size_t words);
00069 
00070     extern char * GC_generic_malloc_words_small(size_t word, int kind);
00071 }
00072 
00073 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
00074 // AUNCOLLECTABLE in gc_priv.h.
00075 
00076 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
00077        GC_AUNCOLLECTABLE = 3 };
00078 
00079 enum { GC_max_fast_bytes = 255 };
00080 
00081 enum { GC_bytes_per_word = sizeof(char *) };
00082 
00083 enum { GC_byte_alignment = 8 };
00084 
00085 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
00086 
00087 inline void * &GC_obj_link(void * p)
00088 {   return *(void **)p;  }
00089 
00090 // Compute a number of words >= n+1 bytes.
00091 // The +1 allows for pointers one past the end.
00092 inline size_t GC_round_up(size_t n)
00093 {
00094     return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
00095 }
00096 
00097 // The same but don't allow for extra byte.
00098 inline size_t GC_round_up_uncollectable(size_t n)
00099 {
00100     return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
00101 }
00102 
00103 template <int dummy>
00104 class GC_aux_template {
00105 public:
00106   // File local count of allocated words.  Occasionally this is
00107   // added into the global count.  A separate count is necessary since the
00108   // real one must be updated with a procedure call.
00109   static size_t GC_words_recently_allocd;
00110 
00111   // Same for uncollectable mmory.  Not yet reflected in either
00112   // GC_words_recently_allocd or GC_non_gc_bytes.
00113   static size_t GC_uncollectable_words_recently_allocd;
00114 
00115   // Similar counter for explicitly deallocated memory.
00116   static size_t GC_mem_recently_freed;
00117 
00118   // Again for uncollectable memory.
00119   static size_t GC_uncollectable_mem_recently_freed;
00120 
00121   static void * GC_out_of_line_malloc(size_t nwords, int kind);
00122 };
00123 
00124 template <int dummy>
00125 size_t GC_aux_template<dummy>::GC_words_recently_allocd = 0;
00126 
00127 template <int dummy>
00128 size_t GC_aux_template<dummy>::GC_uncollectable_words_recently_allocd = 0;
00129 
00130 template <int dummy>
00131 size_t GC_aux_template<dummy>::GC_mem_recently_freed = 0;
00132 
00133 template <int dummy>
00134 size_t GC_aux_template<dummy>::GC_uncollectable_mem_recently_freed = 0;
00135 
00136 template <int dummy>
00137 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
00138 {
00139     GC_words_recently_allocd += GC_uncollectable_words_recently_allocd;
00140     GC_non_gc_bytes +=
00141                 GC_bytes_per_word * GC_uncollectable_words_recently_allocd;
00142     GC_uncollectable_words_recently_allocd = 0;
00143 
00144     GC_mem_recently_freed += GC_uncollectable_mem_recently_freed;
00145     GC_non_gc_bytes -= 
00146                 GC_bytes_per_word * GC_uncollectable_mem_recently_freed;
00147     GC_uncollectable_mem_recently_freed = 0;
00148 
00149     GC_incr_words_allocd(GC_words_recently_allocd);
00150     GC_words_recently_allocd = 0;
00151 
00152     GC_incr_mem_freed(GC_mem_recently_freed);
00153     GC_mem_recently_freed = 0;
00154 
00155     return GC_generic_malloc_words_small(nwords, kind);
00156 }
00157 
00158 typedef GC_aux_template<0> GC_aux;
00159 
00160 // A fast, single-threaded, garbage-collected allocator
00161 // We assume the first word will be immediately overwritten.
00162 // In this version, deallocation is not a noop, and explicit
00163 // deallocation is likely to help performance.
00164 template <int dummy>
00165 class single_client_gc_alloc_template {
00166     public:
00167        static void * allocate(size_t n)
00168         {
00169            size_t nwords = GC_round_up(n);
00170            void ** flh;
00171            void * op;
00172 
00173            if (n > GC_max_fast_bytes) return GC_malloc(n);
00174            flh = GC_objfreelist_ptr + nwords;
00175            if (0 == (op = *flh)) {
00176               return GC_aux::GC_out_of_line_malloc(nwords, GC_NORMAL);
00177            }
00178            *flh = GC_obj_link(op);
00179            GC_aux::GC_words_recently_allocd += nwords;
00180            return op;
00181         }
00182        static void * ptr_free_allocate(size_t n)
00183         {
00184            size_t nwords = GC_round_up(n);
00185            void ** flh;
00186            void * op;
00187 
00188            if (n > GC_max_fast_bytes) return GC_malloc_atomic(n);
00189            flh = GC_aobjfreelist_ptr + nwords;
00190            if (0 == (op = *flh)) {
00191               return GC_aux::GC_out_of_line_malloc(nwords, GC_PTRFREE);
00192            }
00193            *flh = GC_obj_link(op);
00194            GC_aux::GC_words_recently_allocd += nwords;
00195            return op;
00196         }
00197        static void deallocate(void *p, size_t n)
00198        {
00199             size_t nwords = GC_round_up(n);
00200             void ** flh;
00201           
00202            if (n > GC_max_fast_bytes)  {
00203               GC_free(p);
00204            } else {
00205                flh = GC_objfreelist_ptr + nwords;
00206                GC_obj_link(p) = *flh;
00207               memset((char *)p + GC_bytes_per_word, 0,
00208                      GC_bytes_per_word * (nwords - 1));
00209                *flh = p;
00210                GC_aux::GC_mem_recently_freed += nwords;
00211            }
00212        }
00213        static void ptr_free_deallocate(void *p, size_t n)
00214        {
00215             size_t nwords = GC_round_up(n);
00216             void ** flh;
00217           
00218            if (n > GC_max_fast_bytes) {
00219               GC_free(p);
00220            } else {
00221               flh = GC_aobjfreelist_ptr + nwords;
00222               GC_obj_link(p) = *flh;
00223               *flh = p;
00224               GC_aux::GC_mem_recently_freed += nwords;
00225            }
00226        }
00227 };
00228 
00229 typedef single_client_gc_alloc_template<0> single_client_gc_alloc;
00230 
00231 // Once more, for uncollectable objects.
00232 template <int dummy>
00233 class single_client_traceable_alloc_template {
00234     public:
00235        static void * allocate(size_t n)
00236         {
00237            size_t nwords = GC_round_up_uncollectable(n);
00238            void ** flh;
00239            void * op;
00240 
00241            if (n > GC_max_fast_bytes) return GC_malloc_uncollectable(n);
00242            flh = GC_uobjfreelist_ptr + nwords;
00243            if (0 == (op = *flh)) {
00244               return GC_aux::GC_out_of_line_malloc(nwords, GC_UNCOLLECTABLE);
00245            }
00246            *flh = GC_obj_link(op);
00247            GC_aux::GC_uncollectable_words_recently_allocd += nwords;
00248            return op;
00249         }
00250        static void * ptr_free_allocate(size_t n)
00251         {
00252            size_t nwords = GC_round_up_uncollectable(n);
00253            void ** flh;
00254            void * op;
00255 
00256            if (n > GC_max_fast_bytes) return GC_malloc_atomic_uncollectable(n);
00257            flh = GC_auobjfreelist_ptr + nwords;
00258            if (0 == (op = *flh)) {
00259               return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
00260            }
00261            *flh = GC_obj_link(op);
00262            GC_aux::GC_uncollectable_words_recently_allocd += nwords;
00263            return op;
00264         }
00265        static void deallocate(void *p, size_t n)
00266        {
00267             size_t nwords = GC_round_up_uncollectable(n);
00268             void ** flh;
00269           
00270            if (n > GC_max_fast_bytes)  {
00271               GC_free(p);
00272            } else {
00273                flh = GC_uobjfreelist_ptr + nwords;
00274                GC_obj_link(p) = *flh;
00275                *flh = p;
00276                GC_aux::GC_uncollectable_mem_recently_freed += nwords;
00277            }
00278        }
00279        static void ptr_free_deallocate(void *p, size_t n)
00280        {
00281             size_t nwords = GC_round_up_uncollectable(n);
00282             void ** flh;
00283           
00284            if (n > GC_max_fast_bytes) {
00285               GC_free(p);
00286            } else {
00287               flh = GC_auobjfreelist_ptr + nwords;
00288               GC_obj_link(p) = *flh;
00289               *flh = p;
00290               GC_aux::GC_uncollectable_mem_recently_freed += nwords;
00291            }
00292        }
00293 };
00294 
00295 typedef single_client_traceable_alloc_template<0> single_client_traceable_alloc;
00296 
00297 template < int dummy >
00298 class gc_alloc_template {
00299     public:
00300        static void * allocate(size_t n) { return GC_malloc(n); }
00301        static void * ptr_free_allocate(size_t n)
00302               { return GC_malloc_atomic(n); }
00303        static void deallocate(void *, size_t) { }
00304        static void ptr_free_deallocate(void *, size_t) { }
00305 };
00306 
00307 typedef gc_alloc_template < 0 > gc_alloc;
00308 
00309 template < int dummy >
00310 class traceable_alloc_template {
00311     public:
00312        static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
00313        static void * ptr_free_allocate(size_t n)
00314               { return GC_malloc_atomic_uncollectable(n); }
00315        static void deallocate(void *p, size_t) { GC_free(p); }
00316        static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
00317 };
00318 
00319 typedef traceable_alloc_template < 0 > traceable_alloc;
00320 
00321 #ifdef _SGI_SOURCE
00322 
00323 // We want to specialize simple_alloc so that it does the right thing
00324 // for all pointerfree types.  At the moment there is no portable way to
00325 // even approximate that.  The following approximation should work for
00326 // SGI compilers, and perhaps some others.
00327 
00328 # define __GC_SPECIALIZE(T,alloc) \
00329 class simple_alloc<T, alloc> { \
00330 public: \
00331     static T *allocate(size_t n) \
00332        { return 0 == n? 0 : \
00333                       (T*) alloc::ptr_free_allocate(n * sizeof (T)); } \
00334     static T *allocate(void) \
00335        { return (T*) alloc::ptr_free_allocate(sizeof (T)); } \
00336     static void deallocate(T *p, size_t n) \
00337        { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
00338     static void deallocate(T *p) \
00339        { alloc::ptr_free_deallocate(p, sizeof (T)); } \
00340 };
00341 
00342 __GC_SPECIALIZE(char, gc_alloc)
00343 __GC_SPECIALIZE(int, gc_alloc)
00344 __GC_SPECIALIZE(unsigned, gc_alloc)
00345 __GC_SPECIALIZE(float, gc_alloc)
00346 __GC_SPECIALIZE(double, gc_alloc)
00347 
00348 __GC_SPECIALIZE(char, traceable_alloc)
00349 __GC_SPECIALIZE(int, traceable_alloc)
00350 __GC_SPECIALIZE(unsigned, traceable_alloc)
00351 __GC_SPECIALIZE(float, traceable_alloc)
00352 __GC_SPECIALIZE(double, traceable_alloc)
00353 
00354 __GC_SPECIALIZE(char, single_client_gc_alloc)
00355 __GC_SPECIALIZE(int, single_client_gc_alloc)
00356 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
00357 __GC_SPECIALIZE(float, single_client_gc_alloc)
00358 __GC_SPECIALIZE(double, single_client_gc_alloc)
00359 
00360 __GC_SPECIALIZE(char, single_client_traceable_alloc)
00361 __GC_SPECIALIZE(int, single_client_traceable_alloc)
00362 __GC_SPECIALIZE(unsigned, single_client_traceable_alloc)
00363 __GC_SPECIALIZE(float, single_client_traceable_alloc)
00364 __GC_SPECIALIZE(double, single_client_traceable_alloc)
00365 
00366 #ifdef __STL_USE_STD_ALLOCATORS
00367 
00368 __STL_BEGIN_NAMESPACE
00369 
00370 template <class _T>
00371 struct _Alloc_traits<_T, gc_alloc >
00372 {
00373   static const bool _S_instanceless = true;
00374   typedef simple_alloc<_T, gc_alloc > _Alloc_type;
00375   typedef __allocator<_T, gc_alloc > allocator_type;
00376 };
00377 
00378 inline bool operator==(const gc_alloc&,
00379                        const gc_alloc&)
00380 {
00381   return true;
00382 }
00383 
00384 inline bool operator!=(const gc_alloc&,
00385                        const gc_alloc&)
00386 {
00387   return false;
00388 }
00389 
00390 template <class _T>
00391 struct _Alloc_traits<_T, single_client_gc_alloc >
00392 {
00393   static const bool _S_instanceless = true;
00394   typedef simple_alloc<_T, single_client_gc_alloc > _Alloc_type;
00395   typedef __allocator<_T, single_client_gc_alloc > allocator_type;
00396 };
00397 
00398 inline bool operator==(const single_client_gc_alloc&,
00399                        const single_client_gc_alloc&)
00400 {
00401   return true;
00402 }
00403 
00404 inline bool operator!=(const single_client_gc_alloc&,
00405                        const single_client_gc_alloc&)
00406 {
00407   return false;
00408 }
00409 
00410 template <class _T>
00411 struct _Alloc_traits<_T, traceable_alloc >
00412 {
00413   static const bool _S_instanceless = true;
00414   typedef simple_alloc<_T, traceable_alloc > _Alloc_type;
00415   typedef __allocator<_T, traceable_alloc > allocator_type;
00416 };
00417 
00418 inline bool operator==(const traceable_alloc&,
00419                        const traceable_alloc&)
00420 {
00421   return true;
00422 }
00423 
00424 inline bool operator!=(const traceable_alloc&,
00425                        const traceable_alloc&)
00426 {
00427   return false;
00428 }
00429 
00430 template <class _T>
00431 struct _Alloc_traits<_T, single_client_traceable_alloc >
00432 {
00433   static const bool _S_instanceless = true;
00434   typedef simple_alloc<_T, single_client_traceable_alloc > _Alloc_type;
00435   typedef __allocator<_T, single_client_traceable_alloc > allocator_type;
00436 };
00437 
00438 inline bool operator==(const single_client_traceable_alloc&,
00439                        const single_client_traceable_alloc&)
00440 {
00441   return true;
00442 }
00443 
00444 inline bool operator!=(const single_client_traceable_alloc&,
00445                        const single_client_traceable_alloc&)
00446 {
00447   return false;
00448 }
00449 
00450 __STL_END_NAMESPACE
00451 
00452 #endif /* __STL_USE_STD_ALLOCATORS */
00453 
00454 #endif /* _SGI_SOURCE */
00455 
00456 #endif /* GC_ALLOC_H */