1. Garbage collector

$Log: flx_gc.pak,v $ Revision 1.6 2006/08/04 05:46:07 skaller Lazy variables. Revision 1.5 2006/07/31 12:45:17 skaller Add _gc_type t type qualifier which tells that t is an allocable type and requires a shape. Add magic substitution encoding @?n which refers to the shape of the n'th type argument. Fixed faulty declaration of C++ array new operator used for allocation of a gc scannable array. Provided type Varray::varray[t] for variable length array, this is only a first cut: it's actually an immobile bounded length array with size variable up to the bound. Revision 1.4 2006/07/17 16:42:40 skaller Start with config and small binding for mmap. Revision 1.3 2006/06/25 16:34:02 rfistman added PRE_LINK_FLAGS hack to get /link flag in VS toolchain to precede all link directives. Diddling with LDFLAGS didn't work because there are currently two ways to pass library args as names (flx_pthread) via "libs" or as system dependent linker switches (/DEFAULTLIB:libflx_pthread, -lflx_pthread) via LDFLAGS. flx_gc now inserted by code generator into all .resh files. I don't know if this is the best way to do it, but adding "requires flx_gc" to the libflx package only ensures that it be linked against libflx and not users of lib flx. I don't see how any of this could have actually worked for you guys from a fresh build. flx_gc.fpc had flx as Name: instead of flx_gc making build order wrong added dependency on flx_gc, libflx_gc to flx package. added flx_gc to pkg_requires and libflx_gc to lib_requires in flx_pthread so it would like /link once again come before all other link arguments. this unbreaks the building of DLLs with the VS toolchain. changed maker so that it doesn't pass libraries via the linker flags but rather via the libs arg. this was breaking both encapsulation and the VS build. changed '# ranlib' to '@rem ranlib' for VS build. # isn't a dos comment. added libflx_gc to bin/flx script. this script is hardcoded and doesn't use the packages! why is is different to the build used in the test phase? Revision 1.2 2006/06/24 06:10:30 skaller Fix build macro for gc library. Revision 1.1 2006/06/22 13:35:25 skaller Rename the gc to be a first class standalone package.

The Felix garbage collector consists of two components: the collector abstraction, and a concrete collector.

The abstraction consists of an abstract class collector_t, which models the collector, an abstract class allocator_t, which models an allocator, and two concrete classes: shape_t, which defines a type shape descriptor, and frame_t, which describes an allocated memory block, called a frame.

The frame_t data is stored at the beginning of every block the collector manages, this is called the header part. The rest of the block is for client data, and is called the client part. The collector manages frames in terms of pointers to the whole block, which are also pointers to the header. The client only sees a pointer to the client part.

The header contains links to other frames, so the collector can navigate the set of blocks, and a pointer to a shape object, which describes where in the client part pointers reside, so that the collector can chase down all the reachable blocks.

The collector mechanism provides resources for a simple mark and sweep collector, reference counting, and manual deletion. It also provides for user written finalisers, in particular C++ class destructors.

Note that the collector is a 'world stop' synchronous collector. Collection only occurs when you call the collect() method of the collector object.

Note the Felix allocator abstraction is not compatible with the C++ allocator concept; instead, it is a simple wrapper around the malloc/free interface. It is provided primarily to allow instrumentation of allocations, although it is possible to supply a user written allocator.

Start python section to spkgs/flx_gc.py[1 /1 ]
     1: #line 99 "./lpsrc/flx_gc.pak"
     2: cpp_cpps = ['rtl/flx_gc','rtl/flx_collector']
     3: provides_lib = "libflx_gc"
     4: pkg_requires = []
     5: lib_requires = []
     6: iscr_source = ['lpsrc/flx_gc.pak']
     7: build_macro = "FLX_GC"
     8: weaver_directory = 'doc/rtl/flx_gc/'
     9: 
End python section to spkgs/flx_gc.py[1]
Start data section to config/flx_gc.fpc[1 /1 ]
     1: Name: flx_gc
     2: Description: Felix default garbage collector
     3: Version: $Id: flx_gc.pak,v 1.6 2006/08/04 05:46:07 skaller Exp $
     4: provides_dlib: -lflx_gc_dynamic
     5: provides_slib: -lflx_gc_static
End data section to config/flx_gc.fpc[1]
Start cpp section to rtl/flx_gc_config.hpp[1 /1 ]
     1: #line 122 "./lpsrc/flx_gc.pak"
     2: #ifndef __FLX_GC_CONFIG_GUARD__
     3: #define __FLX_GC_CONFIG_GUARD__
     4: #include "flx_rtl_config.hpp"
     5: #ifdef BUILD_FLX_GC
     6: #define GC_EXTERN FLX_EXPORT
     7: #else
     8: #define GC_EXTERN FLX_IMPORT
     9: #endif
    10: #endif
    11: 
End cpp section to rtl/flx_gc_config.hpp[1]
Start cpp section to rtl/flx_gc.hpp[1 /15 ] Next Last
     1: #line 134 "./lpsrc/flx_gc.pak"
     2: #ifndef FLX_GC
     3: #define FLX_GC
     4: 
     5: #include <cstdlib>
     6: #include "flx_gc_config.hpp"
     7: 
     8: // we use an STL set to hold the collection of roots
     9: #include <set>
    10: 
    11: namespace flx {
    12: namespace gc {
    13: namespace generic {
    14: // Here are the types we refer to:
    15: 
    16: struct GC_EXTERN frame_t;      // the type of all collectable objects
    17: struct GC_EXTERN gc_shape_t;   // the shape of collectable objects
    18: struct GC_EXTERN collector_t;  // the collector itself
    19: struct GC_EXTERN allocator_t;  // the collector itself
    20: 
    21: enum gc_shape_flags_t {
    22:   gc_flags_default    = 0,            //< collectable and mobile
    23:   gc_flags_immobile   = 1,            //< cannot be moved
    24:   gc_flags_persistent = 2             //< cannot be deallocated
    25: };
    26: 
    27: /// Describes runtime object shape.
    28: struct GC_EXTERN gc_shape_t
    29: {
    30:   gc_shape_t *next_shape;         ///< pointer to next shape in list or NULL
    31:   char const *cname;              ///< C++ typename
    32:   std::size_t count;              ///< array element count
    33:   std::size_t amt;                ///< bytes allocated
    34:   void (*finaliser)(collector_t*, void*);  ///< finalisation function
    35:   std::size_t n_offsets;          ///< number of offsets
    36:   std::size_t *offsets;           ///< actual offsets
    37:   gc_shape_flags_t flags;         ///< flags
    38:   // convenience constructor
    39:   gc_shape_t(
    40:     gc_shape_t *ns,
    41:     char const *cn,
    42:     std::size_t count_a,
    43:     std::size_t amt_a,
    44:     void (*finaliser_a)(collector_t*, void*),
    45:     std::size_t n_offsets_a,
    46:     std::size_t *offsets_a
    47:   );
    48:   gc_shape_t(
    49:     gc_shape_t *ns,
    50:     char const *cn,
    51:     std::size_t count_a,
    52:     std::size_t amt_a,
    53:     void (*finaliser_a)(collector_t*, void*),
    54:     std::size_t n_offsets_a,
    55:     std::size_t *offsets_a,
    56:     gc_shape_flags_t flags_a
    57:   );
    58: };
End cpp section to rtl/flx_gc.hpp[1]
The following template is provided as a standard wrapper for C++ class destructors. The term
  std_finaliser<T>
denotes a function pointer to the wrapper for the destructor of class T, which can be used as a finaliser in the shape descriptor of a T. The client is cautioned than the order of finalisation may not be what is expected. Finalisers should be provided for all C++ objects managed by the Felix collector and not refering to Felix objects, but which contain pointers to other objects that need to be deleted when the main object is destroyed; for example a string class managing an array of char requires its destructor be invoked to delete the managed array, and so a finaliser wrapping the destructor must be provided.

C data types may, of course, also require destruction, and Felix therefore can provide programmers with the convenience of C++ destructors, even for C data types.

Start cpp section to rtl/flx_gc.hpp[2 /15 ] Next Prev First Last
    59: #line 215 "./lpsrc/flx_gc.pak"
    60: template<class T>
    61: void std_finaliser(collector_t*, void *t)
    62: {
    63:   static_cast<T*>(t) -> ~T();
    64: }
    65: 
End cpp section to rtl/flx_gc.hpp[2]
Here is the allocator abstraction.
Start cpp section to rtl/flx_gc.hpp[3 /15 ] Next Prev First Last
    66: #line 224 "./lpsrc/flx_gc.pak"
    67: 
    68: /// Allocator abstraction.
    69: 
    70: struct allocator_t {
    71:   bool debug;
    72:   allocator_t():debug(false){}
    73:   virtual void *allocate(std::size_t)=0;
    74:   virtual void deallocate(void *)=0;
    75:   virtual void *reallocate(void *, std::size_t)=0;
    76:   virtual ~allocator_t(){};
    77:   void set_debug(bool d){debug=d;}
    78: };
    79: 
End cpp section to rtl/flx_gc.hpp[3]
And here is the collector abstraction.
Start cpp section to rtl/flx_gc.hpp[4 /15 ] Next Prev First Last
    80: #line 240 "./lpsrc/flx_gc.pak"
    81: 
    82: /// Collector abstraction.
    83: struct GC_EXTERN collector_t
    84: {
    85:   bool debug;
    86:   void set_debug(bool d){debug=d;}
    87:   collector_t();
    88:   virtual ~collector_t(){}
    89: 
End cpp section to rtl/flx_gc.hpp[4]
These routines just provide statistics.
Start cpp section to rtl/flx_gc.hpp[5 /15 ] Next Prev First Last
    90: #line 252 "./lpsrc/flx_gc.pak"
    91:   unsigned long get_allocation_count()const {
    92:     return v_get_allocation_count();
    93:   }
    94: 
    95:   unsigned long get_root_count()const {
    96:     return v_get_root_count();
    97:   }
    98: 
    99:   unsigned long get_allocation_amt()const {
   100:     return v_get_allocation_amt();
   101:   }
   102: 
End cpp section to rtl/flx_gc.hpp[5]
Hooks for the supplied allocator, which operate in terms of shape objects rather than raw memory amounts.
Start cpp section to rtl/flx_gc.hpp[6 /15 ] Next Prev First Last
   103: #line 268 "./lpsrc/flx_gc.pak"
   104:   void *allocate(gc_shape_t *shape, unsigned long x) {
   105:     return v_allocate(shape,x);
   106:   }
   107: 
   108:   void deallocate(frame_t *fp) {
   109:     v_deallocate(fp);
   110:   }
   111: 
End cpp section to rtl/flx_gc.hpp[6]
The mark and sweep collector algorithm.
Start cpp section to rtl/flx_gc.hpp[7 /15 ] Next Prev First Last
   112: #line 279 "./lpsrc/flx_gc.pak"
   113:   unsigned long collect() {
   114:     return v_collect();
   115:   }
   116: 
End cpp section to rtl/flx_gc.hpp[7]
Routines to add and remove roots.
Start cpp section to rtl/flx_gc.hpp[8 /15 ] Next Prev First Last
   117: #line 286 "./lpsrc/flx_gc.pak"
   118:   void add_root(void *memory) {
   119:     v_add_root(memory);
   120:   }
   121: 
   122:   void remove_root(void *memory) {
   123:     v_remove_root(memory);
   124:   }
   125: 
End cpp section to rtl/flx_gc.hpp[8]
Routine to optimise store by compaction. Optional, does nothing if not implemented. The closed flag should be set to true if a collection has just been done, and, no foreign pointers are expected anywhere, otherwise it should be set to false. Setting it to true enables a check that every pointer found is live (points to an known object) or NULL. This may not be the case if there is any garbage, which may contain the address on the machine stack that used to point to a live frame (but the frame is now gone).
Start cpp section to rtl/flx_gc.hpp[9 /15 ] Next Prev First Last
   126: #line 308 "./lpsrc/flx_gc.pak"
   127:   void compact(bool closed) {
   128:     v_compact(closed);
   129:   }
   130: 
End cpp section to rtl/flx_gc.hpp[9]
Integrity check for the data structure being managed.
Start cpp section to rtl/flx_gc.hpp[10 /15 ] Next Prev First Last
   131: #line 315 "./lpsrc/flx_gc.pak"
   132:   void check() {
   133:     v_check();
   134:   }
   135: 
   136: private:
   137:   virtual unsigned long v_get_allocation_count()const=0;
   138:   virtual unsigned long v_get_root_count()const=0;
   139:   virtual unsigned long v_get_allocation_amt()const=0;
   140:   virtual void *v_allocate(gc_shape_t *shape, unsigned long)=0;
   141:   virtual void v_deallocate(frame_t *fp)=0;
   142:   virtual unsigned long v_collect()=0;
   143:   virtual void v_add_root(void *memory)=0;
   144:   virtual void v_remove_root(void *memory)=0;
   145:   virtual void v_compact(bool closed)=0;
   146:   virtual void v_check()=0;
   147: 
End cpp section to rtl/flx_gc.hpp[10]
It doesn't make any sense to copy collector objects about.
Start cpp section to rtl/flx_gc.hpp[11 /15 ] Next Prev First Last
   148: #line 335 "./lpsrc/flx_gc.pak"
   149:   void operator=(collector_t const&);
   150:   collector_t(collector_t const&);
   151: };
   152: 
   153: 
End cpp section to rtl/flx_gc.hpp[11]
The destroy function unconditionally deletes an object, so it must only be used when there are no managed pointers to the object. Other pointers might exist, and that is normally OK provided they're not dereferenced.
Start cpp section to rtl/flx_gc.hpp[12 /15 ] Next Prev First Last
   154: #line 347 "./lpsrc/flx_gc.pak"
   155: void GC_EXTERN destroy(void *b);
   156: 
End cpp section to rtl/flx_gc.hpp[12]
The following routines are provided to help safely manage pointers. The can be used to initialise, assign and destroy, and delete pointer variables, where delete implies both NULLing out the variable and also deleting the object pointed to.

Each untyped routine has a corresponding template to provide a type safe interface.

Start cpp section to rtl/flx_gc.hpp[13 /15 ] Next Prev First Last
   157: #line 361 "./lpsrc/flx_gc.pak"
   158: void GC_EXTERN _init_ptr(void **a, void *b);
   159: void GC_EXTERN _set_ptr(void **a, void *b);
   160: void GC_EXTERN _release_ptr(void **a);
   161: void GC_EXTERN _destroy_ptr(void **a);
   162: 
   163: template<class T>
   164: void init_ptr(T **a, T *b)
   165: {
   166:   _init_ptr
   167:   (
   168:     reinterpret_cast<void**>(a),
   169:     reinterpret_cast<void*>(b)
   170:   );
   171: }
   172: 
   173: template<class T>
   174: void set_ptr(T **a, T *b)
   175: {
   176:   _set_ptr
   177:   (
   178:     reinterpret_cast<void**>(a),
   179:     reinterpret_cast<void*>(b)
   180:   );
   181: }
   182: 
   183: template<class T>
   184: void release_ptr(T **a)
   185: {
   186:   _release_ptr
   187:   (
   188:     reinterpret_cast<void**>(a)
   189:   );
   190: }
   191: 
   192: template<class T>
   193: void destroy_ptr(T **a)
   194: {
   195:   _destroy_ptr
   196:   (
   197:     reinterpret_cast<void**>(a)
   198:   );
   199: }
   200: 
End cpp section to rtl/flx_gc.hpp[13]
These two routines are used to reset the type of object an memory block hold, and reset the length of an array, respectively.
Start cpp section to rtl/flx_gc.hpp[14 /15 ] Next Prev First Last
   201: #line 410 "./lpsrc/flx_gc.pak"
   202: GC_EXTERN void reset_shape(void *memory, gc_shape_t &);
   203: GC_EXTERN void reset_count(void *memory, unsigned long);
   204: GC_EXTERN unsigned long get_count(void *memory);
   205: 
   206: }}} // end namespaces
   207: 
End cpp section to rtl/flx_gc.hpp[14]
The following two routines are used to provide C++ type safe heap allocation. There are no corresponding delete routines, please use the destroy function.

Note these routines are now placed in the global namespace to accomodate Metrowerks compiler on Mac OS.

Start cpp section to rtl/flx_gc.hpp[15 /15 ] Prev First
   208: #line 426 "./lpsrc/flx_gc.pak"
   209: /// Allocate collectable object
   210: GC_EXTERN void *operator new
   211: (
   212:   std::size_t,
   213:   flx::gc::generic::collector_t &,
   214:   flx::gc::generic::gc_shape_t &
   215: );
   216: 
   217: /// Allocate collectable array
   218: GC_EXTERN void *operator new []
   219: (
   220:   std::size_t,
   221:   flx::gc::generic::collector_t &,
   222:   flx::gc::generic::gc_shape_t &,
   223:   unsigned long
   224: );
   225: 
   226: #endif
   227: 
End cpp section to rtl/flx_gc.hpp[15]
Start cpp section to rtl/flx_gc_private.hpp[1 /1 ]
     1: #line 447 "./lpsrc/flx_gc.pak"
     2: // THIS IS A HACK .. required by generic pointer
     3: // manipulators -- but really should be private to the Felix
     4: // default collector implementation
     5: 
     6: namespace flx {
     7: namespace gc {
     8: namespace generic { // SHOULD BE NAMESPACE collector
     9: 
    10: /// Heap Frame header
    11: struct frame_t
    12: {
    13:   gc_shape_t *shape;      // the shape of each object
    14:   unsigned long n_objects; // how many objects (for arrays)
    15:   frame_t *next;          // the next and previous objects
    16:   frame_t *prev;          // in the collectors list
    17:   collector_t *collector; // the managing collector
    18:   bool garbage;           // the garbage flag
    19:   bool finalised;         // whether the object is finalised
    20: };
    21: 
    22: }}} // end namespaces
    23: 
    24: // ----------------------------------------------------
    25: 
    26: #define _ROUNDUP(i,n) ((i + n - 1) / n * n)
    27: #define _ALIGN(i) _ROUNDUP(i,FLX_MAX_ALIGN)
    28: 
    29: #define FRAMESIZE int(_ALIGN(sizeof(flx::gc::generic::frame_t)))
    30: #define FRAME_TO_CLIENT(p) \
    31:   ((void*)((unsigned char*)(void*)p + FRAMESIZE))
    32: #define CLIENT_TO_FRAME(p) \
    33:   ((frame_t*)(void*)((unsigned char*)p - FRAMESIZE))
    34: 
    35: 
End cpp section to rtl/flx_gc_private.hpp[1]
Start cpp section to rtl/flx_gc.cpp[1 /1 ]
     1: #line 483 "./lpsrc/flx_gc.pak"
     2: 
     3: #include "flx_gc.hpp"
     4: #include <cstdio>
     5: #include <cassert>
     6: #include "flx_gc_private.hpp"
     7: 
     8: namespace flx {
     9: namespace gc {
    10: namespace generic {
    11: 
    12: // create a shape object given an array of offsets
    13: gc_shape_t::gc_shape_t
    14: (
    15:   gc_shape_t *ns,
    16:   char const *cn,
    17:   std::size_t count_a,
    18:   std::size_t amt_a,
    19:   void (*finaliser_a)(collector_t*, void*),
    20:   std::size_t n_offsets_a,
    21:   std::size_t *offsets_a,
    22:   gc_shape_flags_t flags_a
    23: )
    24:   :
    25:   next_shape(ns),
    26:   cname(cn),
    27:   count(count_a),
    28:   amt(amt_a),
    29:   finaliser(finaliser_a),
    30:   n_offsets(n_offsets_a),
    31:   offsets(offsets_a),
    32:   flags(flags_a)
    33: {}
    34: 
    35: // with flags defaulted
    36: gc_shape_t::gc_shape_t
    37: (
    38:   gc_shape_t *ns,
    39:   char const *cn,
    40:   std::size_t count_a,
    41:   std::size_t amt_a,
    42:   void (*finaliser_a)(collector_t*, void*),
    43:   std::size_t n_offsets_a,
    44:   std::size_t *offsets_a
    45: )
    46:   :
    47:   next_shape(ns),
    48:   cname(cn),
    49:   count(count_a),
    50:   amt(amt_a),
    51:   finaliser(finaliser_a),
    52:   n_offsets(n_offsets_a),
    53:   offsets(offsets_a),
    54:   flags(gc_flags_default)
    55: {}
    56: 
    57: void destroy(void *p)
    58: {
    59:   if(p)
    60:   {
    61:     frame_t *fp = CLIENT_TO_FRAME(p);
    62:     if(!fp->finalised)
    63:       fp->collector->deallocate(fp);
    64:    }
    65: }
    66: 
    67: // b may be 0
    68: void _init_ptr(void **a, void *b)
    69: {
    70:   *a = b;
    71: }
    72: 
    73: // *a or b may be 0
    74: void _set_ptr(void **a, void *b)
    75: {
    76:   *a = b;
    77: }
    78: 
    79: // *a may be 0
    80: void _release_ptr(void **a)
    81: {
    82:   *a = 0;
    83: }
    84: 
    85: void _destroy_ptr(void **a)
    86: {
    87:   void *b = *a; // save the pointer value
    88:   *a=0;         // null out the variable
    89:   destroy(b);
    90: }
    91: 
    92: void reset_shape(void *memory, gc_shape_t &shape)
    93: {
    94:   assert(memory);
    95:   CLIENT_TO_FRAME(memory)->shape = &shape;
    96: }
    97: 
    98: void reset_count(void *memory, unsigned long n)
    99: {
   100:   assert(memory);
   101:   CLIENT_TO_FRAME(memory)->n_objects = n;
   102: }
   103: 
   104: unsigned long get_count(void *memory)
   105: {
   106:   assert(memory);
   107:   return CLIENT_TO_FRAME(memory)->n_objects;
   108: }
   109: 
   110: collector_t::collector_t() : debug(false) {}
   111: 
   112: 
   113: }}} // end namespaces
   114: 
   115: // in global namespace now ..
   116: void *operator new(
   117:   std::size_t amt,
   118:   flx::gc::generic::collector_t &collector,
   119:   flx::gc::generic::gc_shape_t &shape
   120: )
   121: {
   122:   if (amt != shape.amt)
   123:   {
   124:     fprintf(stderr,"Shape size error: allocator size = %ld\n",amt);
   125:     fprintf(stderr,"Shape %s size = %ld\n",shape.cname,shape.amt);
   126:     abort();
   127:   }
   128:   return collector.allocate(&shape,1);
   129: }
   130: 
   131: // array form
   132: void *operator new [] (
   133:   std::size_t amt,
   134:   flx::gc::generic::collector_t &collector,
   135:   flx::gc::generic::gc_shape_t &shape,
   136:   unsigned long count
   137: )
   138: {
   139:   assert (amt == shape.amt * count);
   140:   return collector.allocate(&shape,count);
   141: }
   142: 
   143: 
End cpp section to rtl/flx_gc.cpp[1]
Start cpp section to rtl/flx_collector.hpp[1 /1 ]
     1: #line 626 "./lpsrc/flx_gc.pak"
     2: #ifndef FLX_COLLECTOR
     3: #define FLX_COLLECTOR
     4: #include "flx_gc.hpp"
     5: #include "flx_gc_private.hpp"
     6: #include <map>
     7: 
     8: namespace flx {
     9: namespace gc {
    10: namespace collector {
    11: using namespace generic;
    12: 
    13: struct GC_EXTERN malloc_free;
    14: struct GC_EXTERN flx_collector_t;
    15: 
    16: /// Allocator using malloc and free.
    17: struct GC_EXTERN malloc_free : public virtual allocator_t
    18: {
    19:   void *allocate(std::size_t);
    20:   void *reallocate(void *, std::size_t);
    21:   void deallocate(void *);
    22: };
    23: 
    24: 
    25: /// Naive Mark and Sweep Collector.
    26: struct GC_EXTERN flx_collector_t : public collector_t
    27: {
    28:   flx_collector_t(allocator_t *);
    29:   ~flx_collector_t();
    30: 
    31:   // special to this collector ..?
    32:   void set_min_arena_size(unsigned long);
    33:   bool check_client_pointer(void *);
    34:   bool check_frame_pointer(frame_t *);
    35: 
    36: 
    37: protected:
    38: 
    39:   /// allocator
    40:   void *impl_allocate(gc_shape_t *ptr_map, unsigned long);
    41:   void impl_deallocate(frame_t *frame);
    42: 
    43:   /// collector (returns number of objects collected)
    44:   unsigned long impl_collect();
    45: 
    46:   // add and remove roots
    47:   void impl_add_root(void *memory);
    48:   void impl_remove_root(void *memory);
    49: 
    50:   //
    51:   void check();
    52: 
    53:   // statistics
    54:   unsigned long impl_get_allocation_count()const;
    55:   unsigned long impl_get_root_count()const;
    56:   unsigned long impl_get_allocation_amt()const;
    57: 
    58:   void impl_compact(bool closed);
    59:   void impl_check();
    60: 
    61: private:
    62:   /// allocator
    63:   void *v_allocate(gc_shape_t *ptr_map, unsigned long);
    64:   void v_deallocate(frame_t *frame);
    65: 
    66:   /// collector (returns number of objects collected)
    67:   unsigned long v_collect();
    68: 
    69:   // add and remove roots
    70:   void v_add_root(void *memory);
    71:   void v_remove_root(void *memory);
    72: 
    73:   //
    74:   void v_check();
    75:   // statistics
    76:   unsigned long v_get_allocation_count()const;
    77:   unsigned long v_get_root_count()const;
    78:   unsigned long v_get_allocation_amt()const;
    79: 
    80:   void v_compact(bool closed);
    81: 
    82: private:
    83:   bool collecting;
    84:   unsigned long allocation_count;
    85:   unsigned long root_count;
    86:   unsigned long allocation_amt;
    87: 
    88: 
    89:   void unlink(frame_t *frame);
    90:   void dispose(frame_t *frame);
    91:     // calls post_delete or delete_frame
    92: 
    93:   void post_delete(frame_t *frame);
    94:   void delete_frame(frame_t *frame);
    95:   unsigned long reap();
    96: 
    97:   void mark();
    98:   unsigned long sweep(); // calls scan_object
    99:   void scan_object(frame_t *frame);
   100: 
   101:   frame_t *first;
   102:   frame_t *to_delete;
   103:   typedef std::map<frame_t*,unsigned long, std::less<frame_t*> > rootmap_t;
   104:   rootmap_t roots;
   105:   bool parity;
   106:   allocator_t *allocator;
   107: 
   108:   // if compaction is being used this stuff controls
   109:   // the arena. The arena ptr grows DOWN towards the
   110:   // start of the arena. arena is NULL unless arenas
   111:   // are being used. Once in use, the allocator is
   112:   // not (normally) used for individual objects
   113: 
   114:   void *arena;       // if compaction is being used, lo address
   115:   void *arena_high;  // arena base (high) address
   116:   void *arena_ptr;   // current top of the stack
   117:   unsigned long arena_size; // hi - lo
   118:   unsigned long arena_free; // ptr - lo
   119:   float arena_size_factor;
   120:   unsigned long min_arena_size;
   121: };
   122: 
   123: }}} // end namespaces
   124: #endif
   125: 
End cpp section to rtl/flx_collector.hpp[1]
Start cpp section to rtl/flx_collector.cpp[1 /1 ]
     1: #line 751 "./lpsrc/flx_gc.pak"
     2: #include <cstdlib>
     3: #include <map>
     4: #include <limits.h>
     5: #include <cassert>
     6: #include <cstdio>
     7: #include <cstddef>
     8: #include "flx_rtl_config.hpp"
     9: #include "flx_collector.hpp"
    10: namespace flx {
    11: namespace gc {
    12: namespace collector {
    13: 
    14: static int mcount FLX_UNUSED = 0;
    15: #ifdef HAVE_GNU_X86
    16: register void *sp __asm__("esp");
    17: #else
    18: // this was getting us unused variable warnings
    19: // static void *sp = 0;
    20: #endif
    21: 
    22: void *low_sp = 0;
    23: void *hi_sp = 0;
    24: 
    25: void *malloc_free::allocate(std::size_t amt)
    26: {
    27:   void *p = malloc(amt);
    28:   if(debug)fprintf(stderr,"Malloc %ld bytes, address = %p\n",amt,p);
    29:   //++mcount;
    30:   //void *x = sp;
    31:   //if (low_sp == NULL) low_sp = x,hi_sp = x;
    32:   //else {
    33:   //  if (x < low_sp) low_sp = x;
    34:   //  if (x > hi_sp) hi_sp = x;
    35:   //}
    36:   //if(mcount%100==0)printf("malloc %p, count=%d,stack size = %ld\n",p,mcount,(char*)hi_sp - (char*)low_sp);
    37:   if(p)return p;
    38:   else {
    39:     fprintf(stderr,"Felix: Malloc out of memory, blk=%ld\n",long(amt));
    40:     abort();
    41:   }
    42: }
    43: 
    44: 
    45: void *malloc_free::reallocate(void *p, size_t amt)
    46: {
    47:   void *q = realloc(p,amt);
    48:   if(q) return p;
    49:   else {
    50:     fprintf(stderr,"Felix: Realloc out of memory, blk=%ld\n",long(amt));
    51:     abort();
    52:   }
    53: }
    54: 
    55: void malloc_free::deallocate(void *p)
    56: {
    57:   //printf("free %p\n",p);
    58:   if(debug)fprintf(stderr,"Free %p\n",p);
    59:   free(p);
    60: }
    61: 
    62: void *flx_collector_t::v_allocate(gc_shape_t *ptr_map, unsigned long x) {
    63:   return impl_allocate(ptr_map, x);
    64: }
    65: 
    66: void flx_collector_t::v_deallocate(frame_t *frame) {
    67:   impl_deallocate(frame);
    68: }
    69: 
    70: unsigned long flx_collector_t::v_collect() {
    71:   return impl_collect();
    72: }
    73: 
    74: void flx_collector_t::v_add_root(void *memory) {
    75:   impl_add_root(memory);
    76: }
    77: 
    78: void flx_collector_t::v_remove_root(void *memory) {
    79:   impl_remove_root(memory);
    80: }
    81: 
    82: void flx_collector_t::v_check() {
    83:   impl_check();
    84: }
    85: 
    86: unsigned long flx_collector_t::v_get_allocation_count()const {
    87:   return impl_get_allocation_count();
    88: }
    89: 
    90: unsigned long flx_collector_t::v_get_root_count()const {
    91:   return impl_get_root_count();
    92: }
    93: 
    94: unsigned long flx_collector_t::v_get_allocation_amt()const {
    95:   return impl_get_allocation_amt();
    96: }
    97: 
    98: void flx_collector_t::v_compact(bool closed) {
    99:   impl_compact(closed);
   100: }
   101: 
   102: 
   103: unsigned long flx_collector_t::impl_get_allocation_count()const
   104: {
   105:   return allocation_count;
   106: }
   107: 
   108: unsigned long flx_collector_t::impl_get_root_count()const
   109: {
   110:   return root_count;
   111: }
   112: 
   113: unsigned long flx_collector_t::impl_get_allocation_amt()const
   114: {
   115:   return allocation_amt;
   116: }
   117: 
   118: 
   119: flx_collector_t::flx_collector_t(allocator_t *a) :
   120:   collecting(false),
   121:   allocation_count(0),
   122:   root_count(0),
   123:   allocation_amt(0),
   124:   first(0),
   125:   to_delete(0),
   126:   parity(false),
   127:   allocator(a),
   128:   arena(0),
   129:   arena_high(0),
   130:   arena_ptr(0),
   131:   arena_size(0),
   132:   arena_free(0),
   133:   arena_size_factor(1.6f),
   134:   min_arena_size(1000000) // 1Meg
   135: {}
   136: 
   137: void flx_collector_t::set_min_arena_size(unsigned long x)
   138: {
   139:   min_arena_size = x;
   140: }
   141: 
   142: void * flx_collector_t::impl_allocate(gc_shape_t *shape, unsigned long nobj)
   143: {
   144:   // calculate how much memory to request
   145:   std::size_t amt = nobj * shape->amt * shape->count + FRAMESIZE;
   146: 
   147:   // allocate a block
   148:   frame_t *fp;
   149:   if(!arena || shape->flags & generic::gc_flags_immobile || amt > arena_free)
   150:     fp = (frame_t*)allocator->allocate(amt);
   151:   else
   152:   {
   153:     amt = _ALIGN(amt);
   154:     arena_ptr = (unsigned char*)arena_ptr - amt;
   155:     arena_free -= amt;
   156:     fp = (frame_t*)arena_ptr;
   157:     if(debug)fprintf(stderr, "New arena object at %p, size %ld\n",arena_ptr,amt);
   158:   }
   159:   assert(fp); // Got some memory!
   160: 
   161:   if(debug)fprintf(stderr,"Allocated %p-0x%x= new %s\n", FRAME_TO_CLIENT(fp),FRAMESIZE,shape->cname);
   162:   // initialise the shape, garbage flag, and refcount
   163:   fp->shape = shape;
   164:   fp->garbage = parity;
   165:   fp->finalised = false;
   166:   fp->n_objects = nobj;
   167:   fp->collector = this;
   168: 
   169:   // link the frame into the collectors list
   170:   fp->prev = 0;
   171:   fp->next = first;
   172:   if(first) first->prev = fp;
   173:   first = fp;
   174: 
   175:   // update statistics
   176:   allocation_count++;
   177:   allocation_amt += amt;
   178:   //fprintf(stderr,"ADDING %ld to allocation amt, result %ld\n",long(amt),long(allocation_amt));
   179:   // return client memory pointer
   180:   return FRAME_TO_CLIENT(fp);
   181: }
   182: 
   183: void flx_collector_t::impl_deallocate(frame_t *fp)
   184: {
   185:   unlink(fp);
   186:   dispose(fp);
   187: }
   188: 
   189: void flx_collector_t::unlink(frame_t *fp)
   190: {
   191:   // check we have a pointer to an object
   192:   assert(fp);
   193: 
   194:   // flag the object as finalised, even before
   195:   // actually calling the finaliser, to
   196:   // prevent recursion via destroy
   197:   fp->finalised = true;
   198: 
   199:   // call the finaliser if there is one
   200:   void (*finaliser)(collector_t*, void*) = fp->shape->finaliser;
   201:   if (finaliser)
   202:   {
   203:     void *cp = FRAME_TO_CLIENT(fp);
   204:     (*finaliser)(this,cp);
   205:   }
   206:   // unlink the frame from the collectors list
   207:   if(fp->prev)
   208:     fp->prev->next = fp->next;
   209:   else {
   210:     assert(first==fp);
   211:     first=fp->next;
   212:   }
   213:   if(fp->next)
   214:     fp->next->prev = fp->prev;
   215: }
   216: 
   217: void flx_collector_t::post_delete(frame_t *fp)
   218: {
   219:   assert(collecting);
   220:   // link into list of objects to delete
   221:   // this list uses the prev pointer!
   222:   fp->prev = to_delete;
   223:   to_delete = fp;
   224: }
   225: 
   226: void flx_collector_t::dispose(frame_t *fp)
   227: {
   228:   if(collecting) post_delete(fp);
   229:   else delete_frame(fp);
   230: }
   231: 
   232: void flx_collector_t::delete_frame(frame_t *fp)
   233: {
   234:   // update statistics
   235:   allocation_count--;
   236:   gc_shape_t *shape = fp->shape;
   237:   unsigned long nobj = shape -> count * fp -> n_objects;
   238:   std::size_t size = shape->amt * nobj + FRAMESIZE;
   239:   //fprintf(stderr,"Raw frame %p size %ld\n",fp,long(size));
   240:   // check if pointer is in arena
   241:   if(arena &&
   242:     std::less_equal<void*>()(arena_ptr,fp) && // ptr <= fp < base
   243:     std::less<void*>()(fp,arena_high)
   244:   )
   245:   {
   246:     size = _ALIGN(size); // FRAGILE
   247:     //fprintf(stderr,"In arena!");
   248:   }
   249:   else
   250:   {
   251:     //fprintf(stderr,"Not in arena\n");
   252:     allocator->deallocate(fp);
   253:   }
   254: 
   255:   allocation_amt -= size;
   256:   //fprintf(stderr,"Subtracting %ld result is %ld\n",long(size),long(allocation_amt));
   257:   //fprintf(stderr, "delete frame %p: nalloc=%ld, alloc=%ld, size = %ld\n",
   258:   //  fp, allocation_count, allocation_amt,long(size)
   259:   //);
   260: }
   261: 
   262: unsigned long flx_collector_t::reap ()
   263: {
   264:   unsigned long count = 0;
   265:   while(to_delete)
   266:   {
   267:     frame_t *next = to_delete-> prev;
   268:     delete_frame(to_delete);
   269:     to_delete = next;
   270:     ++count;
   271:   }
   272:   return count;
   273: }
   274: 
   275: 
   276: unsigned long flx_collector_t::sweep()
   277: {
   278:   if(debug)fprintf(stderr,"Collector: Sweep\n");
   279:   collecting=true;
   280:   frame_t *current = first;
   281:   while(current)
   282:   {
   283:     if(current->garbage == parity)
   284:     {
   285:       if(debug)fprintf(stderr,"Garbage %p=%s\n",current,current->shape->cname);
   286:       unlink(current);
   287:       post_delete(current);
   288:     }
   289:     current = current->next;
   290:   }
   291:   parity = !parity;
   292:   collecting = false;
   293:   return reap();
   294: }
   295: 
   296: void flx_collector_t::impl_add_root(void *memory)
   297: {
   298:   if(!memory)
   299:   {
   300:     fprintf(stderr, "GC ERROR: ADD NULL ROOT\n");
   301:     abort();
   302:   }
   303:   frame_t *p =  CLIENT_TO_FRAME(memory);
   304:   rootmap_t::iterator iter = roots.find(p);
   305:   if(iter == roots.end())
   306:   {
   307:     std::pair<frame_t *const, unsigned long> entry(p,1UL);
   308:     roots.insert (entry);
   309:     root_count++;
   310:   }
   311:   else
   312:     ++(*iter).second;
   313: }
   314: 
   315: void flx_collector_t::impl_remove_root(void *memory)
   316: {
   317:   frame_t *p =  CLIENT_TO_FRAME(memory);
   318:   rootmap_t::iterator iter = roots.find(p);
   319:   if(iter == roots.end())
   320:   {
   321:     fprintf(stderr, "GC ERROR: REMOVE ROOT WHICH IS NOT ROOT\n");
   322:     abort();
   323:   }
   324:   if((*iter).second == 1UL)
   325:   {
   326:     roots.erase(iter);
   327:     root_count--;
   328:   }
   329:   else
   330:     --(*iter).second;
   331: }
   332: 
   333: void flx_collector_t::scan_object(frame_t *frame)
   334: {
   335:   if(debug)fprintf(stderr,"Scanning %p\n",frame);
   336:   if(debug)fprintf(stderr,"Scanning [valid] %p=%s\n",frame,frame->shape->cname);
   337:   if(frame->garbage == parity)
   338:   {
   339:     if(debug){
   340:       fprintf(stderr,"Reachable %p\n",frame);
   341:       gc_shape_t * shape = frame->shape;
   342:       fprintf(stderr,"Reachable [valid] %p=%s\n",frame,shape->cname);
   343:       for(unsigned int i=0; i<shape->n_offsets; ++i)
   344:       {
   345:         unsigned long offset = shape->offsets[i];
   346:         unsigned char *p = (unsigned char*)FRAME_TO_CLIENT(frame);
   347:         void *x = *(void**)(p+offset);
   348:         if(x) {
   349:           bool valid = check_client_pointer(x);
   350:           fprintf(stderr," offset: 0x%04lx %p->[%p-0x%x] %s\n",
   351:             offset,p+offset,x,FRAMESIZE,
   352:             valid?"[valid]":"INVALID"
   353:           );
   354:           if(!valid) abort();
   355:         }
   356:         else
   357:           fprintf(stderr," offset: 0x%04lx %p->[%p] NULL\n",
   358:             offset,p+offset,x);
   359:       }
   360:     }
   361:     frame->garbage = !parity; // reachable!
   362:     gc_shape_t *shape = frame->shape;
   363:     unsigned long n_objects = frame->n_objects * shape->count;
   364:     std::size_t obj_size = shape->amt;
   365:     std::size_t n_offsets = shape->n_offsets;
   366:     std::size_t *offsets = shape->offsets;
   367:     unsigned char *p = (unsigned char*)FRAME_TO_CLIENT(frame);
   368: 
   369:     for(unsigned long j=0; j<n_objects; ++j)
   370:     {
   371:       for(unsigned int i=0; i<n_offsets; ++i)
   372:       {
   373:         void **q = (void**)(void*)(p + offsets[i]);
   374:         if(*q)
   375:           scan_object(CLIENT_TO_FRAME(*q));
   376:       }
   377:       p+=obj_size;
   378:     }
   379:   }
   380: }
   381: 
   382: void flx_collector_t::mark()
   383: {
   384:   if(debug)fprintf(stderr,"Collector: Running mark\n");
   385:   assert (root_count == roots.size());
   386: 
   387:   rootmap_t::iterator const end = roots.end();
   388:   for(
   389:     rootmap_t::iterator i = roots.begin();
   390:     i != end;
   391:     ++i
   392:   )
   393:     scan_object((*i).first);
   394: }
   395: 
   396: unsigned long flx_collector_t::impl_collect()
   397: {
   398:   if(debug)fprintf(stderr,"Running collector\n");
   399:   mark();
   400:   unsigned long r = sweep();
   401:   if(debug)impl_check();
   402:   return r;
   403: }
   404: 
   405: static int vpcompare(void const *a, void const *b) {
   406:   void *aa = *(void**)a;
   407:   void *bb = *(void**)b;
   408:   if (std::less<void*>()(aa,bb)) return -1;
   409:   if (std::equal_to<void*>()(aa,bb)) return 0;
   410:   return 1;
   411: }
   412: 
   413: // scan all known objects, and check every pointer
   414: // is either NULL or points to one of them
   415: 
   416: void flx_collector_t::impl_check()
   417: {
   418:   if(debug)fprintf(stderr,"RUNNING HEAP INTEGRITY CHECK\n");
   419:   unsigned long nobj = allocation_count;
   420:   void **ctrl = (void**)malloc(nobj * sizeof(void*));
   421:   unsigned long handled = 0;
   422:   unsigned long allocated = 0;
   423:   frame_t *lfirst = first;
   424:   unsigned long inarena = 0;
   425:   unsigned long outofarena = 0;
   426:   while(lfirst) {
   427:     ctrl[handled++]=lfirst;
   428:     gc_shape_t *shape = lfirst->shape;
   429:     unsigned long n_objects = lfirst->n_objects * shape->count;
   430:     unsigned long size = n_objects * shape->amt + FRAMESIZE;
   431:     if(arena &&
   432:       std::less_equal<void*>()(arena_ptr,lfirst) && // ptr <= fp < base
   433:       std::less<void*>()(lfirst,arena_high)
   434:     )
   435:     {
   436:       size = _ALIGN(size); // FRAGILE
   437:       inarena++;
   438:     }
   439:     else
   440:       outofarena++
   441:     ;
   442:     //fprintf(stderr,"Object %p size %ld type %s\n",lfirst,long(size),shape->cname);
   443:     allocated += size;
   444:     lfirst = lfirst->next;
   445:   }
   446: 
   447:   if(handled != nobj)
   448:   {
   449:     fprintf(stderr,"Wrong number of objects\n");
   450:     abort();
   451:   }
   452: 
   453:   if(allocated != allocation_amt)
   454:   {
   455:     fprintf(stderr,"Wrong allocation amount: recorded as %ld, counted as %ld\n",
   456:       allocation_amt, allocated
   457:     );
   458:     fprintf(stderr, "Objects in arena = %ld, objects out of arena = %ld\n",
   459:       inarena,outofarena
   460:     );
   461:     abort();
   462:   }
   463:   qsort(ctrl,nobj,sizeof(void*),vpcompare);
   464: 
   465:   for(unsigned int i = 0; i<nobj; ++i) {
   466:     frame_t *frame = (frame_t*) ctrl[i];
   467:     gc_shape_t *shape = frame->shape;
   468:     unsigned long n_objects = frame->n_objects * shape->count;
   469: 
   470:     // scan the frame for pointers and adjust them
   471:     unsigned char *client = (unsigned char*)FRAME_TO_CLIENT(frame);
   472:     size_t *offsets = shape -> offsets;
   473:     for(unsigned int nel = 0; nel < n_objects; nel++)
   474:     {
   475:       for(unsigned int k = 0; k<shape->n_offsets; ++k)
   476:       {
   477:         size_t offset = offsets[k];
   478:         void **loc = (void**)(client + offset);
   479:         void *client_ptr = *loc;
   480:         if (client_ptr) // leave NULL alone
   481:         {
   482:           void *address= CLIENT_TO_FRAME(client_ptr);
   483:           void **res = (void**) bsearch(
   484:             &address,
   485:             ctrl,nobj,
   486:             sizeof(void*),
   487:             vpcompare
   488:           );
   489:           if(!res) {
   490:             fprintf(stderr,
   491:               "CHECK: In object frame=%p, type %s, subobject #%d,\n"
   492:               "offset #%d->%ld, at address %p,\n"
   493:               "pointer [frame=%p, client=%p] NOT IN GC LIST\n",
   494:               frame, shape->cname,nel,k,offset,loc,address,client_ptr);
   495:             abort();
   496:           }
   497:         }
   498:       }
   499:       client += shape->amt;
   500:     }
   501:   }
   502: 
   503:   rootmap_t::iterator last = roots.end();
   504:   for(
   505:     rootmap_t::iterator iter = roots.begin();
   506:     iter != last;
   507:     ++iter
   508:   )
   509:   {
   510:     std::pair<frame_t *const, unsigned long> root_record = *iter;
   511:     void **res = (void**) bsearch(
   512:       &root_record.first,
   513:       ctrl,nobj,
   514:       sizeof(void*),
   515:       vpcompare
   516:     );
   517:     if(!res) {
   518:       fprintf(stderr,"CHECK: WOOPS CANNOT FIND ROOT! %p\n",root_record.first);
   519:       abort();
   520:     }
   521:   }
   522:   free(ctrl);
   523: }
   524: 
   525: bool flx_collector_t::check_frame_pointer(frame_t *p)
   526: {
   527:   frame_t *current = first;
   528:   while(current)
   529:   {
   530:     if(current == p) return true;
   531:     current = current->next;
   532:   }
   533:   return false;
   534: }
   535: 
   536: bool flx_collector_t::check_client_pointer(void *p)
   537: {
   538:   return p?check_frame_pointer (CLIENT_TO_FRAME(p)):true;
   539: }
   540: 
   541: flx_collector_t::~flx_collector_t()
   542: {
   543:   //THIS IS VERY DANGEROUS! What if don't want to collect
   544:   //the garbage for efficiency reasons???
   545:   //
   546:   // ELIDED .. already caused a bug!
   547:   //
   548:   //roots.clear();
   549:   //root_count = 0;
   550:   //sweep();
   551: }
   552: 
   553: // ONCE THIS ROUTINE IS CALLED, the allocator
   554: // is never used again for individual objects.
   555: // The compactor puts all the targets in a SINGLE frame
   556: // and so they cannot be deallocated by the allocator.
   557: // Instead, the only way to clean up garbage is by
   558: // compacting again. We have to do this when we run out
   559: // of memory --- but ONLY when we're in compacting mode:
   560: // if we try it out of compacting mode we're screwed,
   561: // because we have to allocate enough memory for a copy
   562: // of ALL the objects (and if just ran out on a single
   563: // operation that is going to be impossible!
   564: 
   565: struct compact_entry_t {
   566:   void *old_frame;
   567:   void *new_frame;
   568: };
   569: 
   570: static int compact_entry_compare
   571: (
   572:   void const *a,
   573:   void const *b
   574: ) {
   575:   void * aa = ((compact_entry_t const*)a) -> old_frame;
   576:   void * bb = ((compact_entry_t const*)b) -> old_frame;
   577:   if (std::less<void*>()(aa,bb)) return -1;
   578:   else if (std::equal_to<void*>()(aa,bb)) return 0;
   579:   else return 1;
   580: }
   581: 
   582: void flx_collector_t::impl_compact(bool closed) {
   583:   //if(arena)
   584:   //fprintf(stderr,"arena size = %ld, free space %d%%\n",
   585:   //  arena_size, int(float(arena_free)/float(arena_size)*100.0f)
   586:   //);
   587: 
   588:   unsigned long nobj = allocation_count;
   589:   unsigned long memreq = allocation_amt;
   590: 
   591:   // temporary hack: if arena has at least 20% free space don't compact
   592:   if(arena && float(arena_free>>8) / float(arena_size>>8) > 0.2) return;
   593:   //fprintf(stderr,"COMPACTING\n");
   594:   compact_entry_t *ctrl = (compact_entry_t*)malloc(nobj * sizeof(compact_entry_t));
   595:   unsigned long handled = 0;
   596: 
   597:   // empty the collectors list of objects into the control array
   598:   // the effect is to simply forget all the objects!
   599: 
   600:   if(debug)fprintf(stderr,"FRAME SIZE = %x\n",FRAMESIZE);
   601:   if(debug)
   602:     fprintf(stderr,"Building array of %ld frames\n",nobj);
   603:   while(first) {
   604:     ctrl[handled++].old_frame=first;
   605:     first = first->next;
   606:   }
   607:   assert(handled == nobj);
   608: 
   609:   if(debug)fprintf(stderr,"Sorting array");
   610:   qsort(ctrl,nobj,sizeof(compact_entry_t),compact_entry_compare);
   611: 
   612:   // make a new arena, make sure it is aligned!
   613:   if(debug)
   614:     fprintf(stderr,"MEMREQ=%ld\n",memreq);
   615:   unsigned long new_arena_size = (unsigned long)(memreq * arena_size_factor) + 256 + nobj * FLX_MAX_ALIGN;
   616:   if(new_arena_size < min_arena_size) new_arena_size = min_arena_size ;
   617:   if(debug)fprintf(stderr,"UNALIGNED MEMORY REQUIREMENT=%ld\n",new_arena_size);
   618:   new_arena_size = _ALIGN(new_arena_size);
   619:   if(debug)fprintf(stderr,"ALIGNED MEMORY REQUIREMENT=%ld\n",new_arena_size);
   620:   if(debug)fprintf(stderr,"Allocating new arena, size=%ld\n",new_arena_size);
   621:   unsigned char *new_arena = (unsigned char*)allocator->allocate(new_arena_size);
   622:   unsigned char *new_arena_ptr = new_arena + new_arena_size;
   623:   unsigned long new_arena_free = new_arena_size;
   624:   unsigned char *new_arena_high = new_arena_ptr;
   625: 
   626:   if(debug)fprintf(stderr,"new arena =%p\n",new_arena);
   627:   if(debug)fprintf(stderr,"arena_ptr =%p\n",new_arena_ptr);
   628: 
   629:   // assign new locations to our objects
   630:   for(unsigned long int j = 0; j<nobj; ++j) {
   631:     unsigned long int i = nobj - j - 1;
   632:     // calculate the object size
   633:     frame_t *frame = (frame_t*) ctrl[i].old_frame;
   634:     gc_shape_t *shape = frame->shape;
   635:     if(shape->flags & gc_flags_immobile)
   636:     {
   637:       // don't move immobile objects
   638:       ctrl[i].new_frame = frame;
   639:       //fprintf(stderr, "Immobile %p type %s\n",frame, shape->cname);
   640:     }
   641:     else
   642:     {
   643:       unsigned long n_objects = frame->n_objects * shape->count;
   644:       unsigned long amt = shape->amt * n_objects + FRAMESIZE;
   645:       if(arena &&
   646:         std::less_equal<void*>()(arena_ptr,frame) && // ptr <= fp < base
   647:         std::less<void*>()(frame,arena_high)
   648:       )
   649:         amt = _ALIGN(amt); // FRAGILE
   650:       allocation_amt -= amt;
   651:       unsigned long new_amt = _ALIGN(amt);
   652:       allocation_amt += new_amt;
   653: 
   654:       // allocate store in arena
   655:       new_arena_ptr = (unsigned char*)new_arena_ptr - new_amt;
   656:       new_arena_free -= new_amt;
   657:       ctrl[i].new_frame = new_arena_ptr;
   658:       //fprintf(stderr,"MOVE OBJECT %p old size %ld new size %ld to %p\n",frame,amt,new_amt,new_arena_ptr);
   659:       if(debug)
   660:         if(amt != new_amt)
   661:           fprintf(stderr,"NONARENA TO ARENA MOVE\n");
   662:     }
   663:   }
   664: 
   665:   // copy the objects and update pointers
   666:   if(debug)fprintf(stderr,"COPYING OBJECTS\n");
   667:   for(unsigned int i = 0; i<nobj; ++i) {
   668:     frame_t *old_frame = (frame_t*) ctrl[i].old_frame;
   669:     frame_t *new_frame = (frame_t*) ctrl[i].new_frame;
   670:     gc_shape_t *shape = old_frame->shape;
   671:     //if(debug)fprintf(stderr,"\nCOPYING OBJECT %s at %p to %p\n",shape->cname,old_frame,new_frame);
   672:     unsigned long n_objects = old_frame->n_objects * shape->count;
   673:     std::size_t obj_size = shape->amt;
   674: 
   675:     // NOTE: NOT ALIGNED!! in case source is not an arena
   676:     unsigned long amt = obj_size * n_objects + FRAMESIZE;
   677:     //if(debug)fprintf(stderr,"Raw size %ld\n",amt);
   678: 
   679:     // copy the frame: we use memmove because
   680:     // we might be doing an in-place compaction
   681:     if (new_frame != old_frame)
   682:       memmove(new_frame,old_frame,amt)
   683:     ;
   684: 
   685:     //if(debug)fprintf(stderr,"Linking into collector list\n");
   686:     // link the frame into the collectors list
   687:     new_frame->prev = 0;
   688:     new_frame->next = first;
   689:     if(first) first->prev = new_frame;
   690:     first = new_frame;
   691: 
   692:     // scan the frame for pointers and adjust them
   693:     unsigned char *client = (unsigned char*)FRAME_TO_CLIENT(new_frame);
   694:     size_t *offsets = shape -> offsets;
   695:     //if(debug)fprintf(stderr,"Client pointer %p\n",client);
   696:     //if(debug)fprintf(stderr,"SCANNING frame %d, %ld objects\n",i,n_objects);
   697:     for(unsigned int nel = 0; nel < n_objects; nel++)
   698:     {
   699:       for(unsigned int k = 0; k<shape->n_offsets; ++k)
   700:       {
   701:         size_t offset = offsets[k];
   702:         //if(debug)fprintf(stderr,"Scanning offset #%d, offset %ld, \n",k,(long)offset);
   703: 
   704:         void **loc = (void**)(client + offset);
   705:         //if(debug)fprintf(stderr,"ADDRESS OF POINTER %p\n",loc);
   706:         void *client_ptr = *loc;
   707:         //if(debug)fprintf(stderr,"VALUE OF CLIENT POINTER %p\n",client_ptr);
   708:         if (client_ptr) // leave NULL alone
   709:         {
   710:           void *address= CLIENT_TO_FRAME(client_ptr);
   711:           //if(debug)fprintf(stderr,"FRAME POINTER %p\n",address);
   712:           //if(debug)fprintf(stderr,"SEARCHING\n");
   713:           compact_entry_t *res = (compact_entry_t*) bsearch(
   714:             &address,
   715:             ctrl,nobj,
   716:             sizeof(compact_entry_t),
   717:             compact_entry_compare
   718:           );
   719:           //if(debug)fprintf(stderr,"SEARCH DONE\n");
   720:           //if(debug)fprintf(stderr,"RESULT ADDRESS=%p\n",res);
   721:           if(closed)
   722:           {
   723:             if(!res) {
   724:               fprintf(stderr, "COMPACTOR: CANNOT FIND ADDRESS %p!!!!!!!\n",address);
   725:               abort();
   726:             }
   727:             //if(debug)fprintf(stderr,"New frame pointer is %p\n",res->new_frame);
   728:             //if(debug)fprintf(stderr,"New client pointer is %p\n",FRAME_TO_CLIENT(res->new_frame));
   729:           }
   730:           // finally adjust the pointer if needed
   731:           if(res)
   732:             *loc = FRAME_TO_CLIENT(res->new_frame);
   733:         }
   734:       }
   735:       client += shape->amt;
   736:     }
   737:   }
   738: 
   739:   //if(debug)fprintf(stderr,"SCANNING COMPLETE\n");
   740:   // discard the old arena now (if there was one)
   741:   if (arena)
   742:   {
   743:     if(debug)fprintf(stderr,"DEALLOCATING OLD ARENA\n");
   744:     allocator->deallocate(arena);
   745:   }
   746:   arena = new_arena;
   747:   arena_size = new_arena_size;
   748:   arena_free = new_arena_free;
   749:   arena_ptr = new_arena_ptr;
   750:   arena_high = new_arena_high;
   751: 
   752:   if(debug)
   753:     fprintf(stderr,"NEW ARENA: LO %p HI %p PTR %p\n",arena, arena_high,arena_ptr);
   754: 
   755:   //if(debug)fprintf(stderr, "FIXING ROOTS\n");
   756:   rootmap_t old_roots = roots;
   757:   roots.clear();
   758: 
   759:   rootmap_t::iterator last = old_roots.end();
   760:   for(
   761:     rootmap_t::iterator iter = old_roots.begin();
   762:     iter != last;
   763:     ++iter
   764:   )
   765:   {
   766:     std::pair<frame_t *const, unsigned long> old_root_record = *iter;
   767:     compact_entry_t *res = (compact_entry_t*) bsearch(
   768:       &old_root_record.first,
   769:       ctrl,nobj,
   770:       sizeof(compact_entry_t),
   771:       compact_entry_compare
   772:     );
   773:     if(!res) {
   774:       fprintf(stderr,"WOOPS CANNOT FIND ROOT! %p\n",old_root_record.first);
   775:       abort();
   776:     }
   777:     std::pair<frame_t *const, unsigned long> new_root_record
   778:     (
   779:       (frame_t*)res->new_frame,
   780:       old_root_record.second
   781:     );
   782:     roots.insert(new_root_record);
   783:   }
   784:   //if(debug)fprintf(stderr,"FIXED UP ROOTS\n");
   785:   free(ctrl);
   786: }
   787: 
   788: }}} // end namespaces
   789: 
End cpp section to rtl/flx_collector.cpp[1]
Start cpp section to rtl/flx_ts_collector.hpp[1 /1 ]
     1: #line 1540 "./lpsrc/flx_gc.pak"
     2: #ifndef FLX_TS_COLLECTOR
     3: #define FLX_TS_COLLECTOR
     4: #include "flx_collector.hpp"
     5: #include "pthread_mutex.hpp"
     6: 
     7: namespace flx {
     8: namespace gc {
     9: namespace collector {
    10: 
    11: /// Naive thread safe Mark and Sweep Collector.
    12: struct PTHREAD_EXTERN flx_ts_collector_t :
    13:   public flx::gc::collector::flx_collector_t
    14: {
    15:   flx_ts_collector_t(allocator_t *);
    16:   ~flx_ts_collector_t();
    17: 
    18: private:
    19:   /// allocator
    20:   void *v_allocate(gc_shape_t *ptr_map, unsigned long);
    21:   void v_deallocate(frame_t *frame);
    22: 
    23:   /// collector (returns number of objects collected)
    24:   unsigned long v_collect();
    25: 
    26:   // add and remove roots
    27:   void v_add_root(void *memory);
    28:   void v_remove_root(void *memory);
    29: 
    30:   //
    31:   void v_check();
    32:   // statistics
    33:   unsigned long v_get_allocation_count()const;
    34:   unsigned long v_get_root_count()const;
    35:   unsigned long v_get_allocation_amt()const;
    36: 
    37:   void v_compact(bool closed);
    38: 
    39: private:
    40:   mutable flx::pthread::flx_mutex_t mut;
    41: };
    42: 
    43: }}} // end namespaces
    44: #endif
    45: 
End cpp section to rtl/flx_ts_collector.hpp[1]
Start cpp section to rtl/flx_ts_collector.cpp[1 /1 ]
     1: #line 1585 "./lpsrc/flx_gc.pak"
     2: #include "flx_rtl_config.hpp"
     3: #include "flx_ts_collector.hpp"
     4: 
     5: namespace flx {
     6: namespace gc {
     7: namespace collector {
     8: 
     9: flx_ts_collector_t::flx_ts_collector_t(allocator_t *a) :
    10:   flx_collector_t(a)
    11: {}
    12: 
    13: flx_ts_collector_t::~flx_ts_collector_t(){}
    14: 
    15: void *flx_ts_collector_t::v_allocate(gc_shape_t *ptr_map, unsigned long x) {
    16:   flx::pthread::flx_mutex_locker_t l(mut);
    17:   return impl_allocate(ptr_map,x);
    18: }
    19: 
    20: void flx_ts_collector_t::v_deallocate(frame_t *frame) {
    21:   flx::pthread::flx_mutex_locker_t l(mut);
    22:   impl_deallocate(frame);
    23: }
    24: 
    25: unsigned long flx_ts_collector_t::v_collect() {
    26:   flx::pthread::flx_mutex_locker_t l(mut);
    27:   return impl_collect();
    28: }
    29: 
    30: void flx_ts_collector_t::v_add_root(void *memory) {
    31:   flx::pthread::flx_mutex_locker_t l(mut);
    32:   impl_add_root(memory);
    33: }
    34: 
    35: void flx_ts_collector_t::v_remove_root(void *memory) {
    36:   flx::pthread::flx_mutex_locker_t l(mut);
    37:   impl_remove_root(memory);
    38: }
    39: 
    40: void flx_ts_collector_t::v_check() {
    41:   flx::pthread::flx_mutex_locker_t l(mut);
    42:   impl_check();
    43: }
    44: 
    45: unsigned long flx_ts_collector_t::v_get_allocation_count()const {
    46:   flx::pthread::flx_mutex_locker_t l(mut);
    47:   return impl_get_allocation_count();
    48: }
    49: 
    50: unsigned long flx_ts_collector_t::v_get_root_count()const {
    51:   flx::pthread::flx_mutex_locker_t l(mut);
    52:   return impl_get_root_count();
    53: }
    54: 
    55: unsigned long flx_ts_collector_t::v_get_allocation_amt()const {
    56:   flx::pthread::flx_mutex_locker_t l(mut);
    57:   return impl_get_allocation_amt();
    58: }
    59: 
    60: void flx_ts_collector_t::v_compact(bool closed) {
    61:   flx::pthread::flx_mutex_locker_t l(mut);
    62:   impl_compact(closed);
    63: }
    64: 
    65: 
    66: }}} // end namespaces
    67: 
    68: 
End cpp section to rtl/flx_ts_collector.cpp[1]