Back to index

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