1. Garbage collector

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