new_gc_alloc.h

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