lib-src/gc/cgc.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are welcomed to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome(read crave for)
  19 // any suggestions and help from the users.
  20 //
  21 // Allen Leung (leunga@cs.nyu.edu)
  22 // 1994-1995
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <iostream.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <setjmp.h>
  29 #include <unistd.h>
  30 #include <assert.h>
  31 #include <signal.h>
  32 #include <sys/types.h>
  33 #include <AD/gc/gcconfig.h>  // system configuration
  34 #include <AD/gc/cgc.h>       // Conservative garbage collector
  35 #include <AD/gc/gcobject.h>  // garbage collectable objects
  36 #include <AD/gc/gcheaps.h>   // the heap manager
  37 #include <AD/gc/gcmacros.h>  // useful macros
  38 #include <AD/gc/weakptr.h>   // weak pointers
  39 #ifdef GC_USE_TIMER
  40 #   include <sys/time.h>
  41 #   include <sys/resource.h>
  42 #   include <AD/gc/gctimer.h>
  43 #endif
  44
  45 //////////////////////////////////////////////////////////////////////////////
  46 //  Some identifying information.
  47 //////////////////////////////////////////////////////////////////////////////
  48 // #define DEBUG_GC  // no debugging for production use
  49 #define SANITY_CHECK // inexpensive checking (left in place for your assurance)
  50 #ifdef DEBUG_GC
  51 #   define SANITY_CHECK
  52 #endif
  53
  54 //////////////////////////////////////////////////////////////////////////////
  55 //  Import some types
  56 //////////////////////////////////////////////////////////////////////////////
  57 typedef HM::GCPageId   GCPageId;
  58 typedef HM::PageStatus PageStatus;
  59
  60 //////////////////////////////////////////////////////////////////////////////
  61 //  Method to locate the bottom of the stack.
  62 //  We'll take care of both upward growing and downward growing stacks.
  63 //////////////////////////////////////////////////////////////////////////////
  64 static void ** compute_stack_bottom(void ** stack_mark1, Bool& downward_stack)
  65 {  void * stack_mark2[1];
  66    size_t stack_alignment = 0x1000000;
  67    if (stack_mark1 < stack_mark2) {
  68       // case a: stack grows upward.
  69       // We'll truncate the address downward.
  70       downward_stack = false;
  71       return (void**)((size_t)stack_mark1 & (stack_alignment-1));
  72    } else {
  73       // case b: stack grows downward.
  74       // We'll round the address upward.
  75       downward_stack = true;
  76       return (void**)(((size_t)stack_mark1 + stack_alignment - 1)
  77                       & ~(stack_alignment-1));
  78    }
  79 }
  80
  81 //////////////////////////////////////////////////////////////////////////////
  82 //  Method to locate the top of the heap
  83 //////////////////////////////////////////////////////////////////////////////
  84 void CGC::get_heap_top()
  85 {  // This heap top is tentative.
  86    // On Linux sometimes this points to addresses that hasn't been
  87    // mapped.
  88    heap_top = (void**)GC_GET_HEAP_TOP;
  89
  90    // Try read from the end of this address.
  91    // If a seg fault occurs, we know it is not the real thing.
  92    // We'll adjust the heap top stuff in that case.
  93    // If we don't have to adjust then this is does nothing.
  94    verify_heap_top();
  95 }
  96
  97 //////////////////////////////////////////////////////////////////////////////
  98 //
  99 //  Method to verify the heap top
 100 //
 101 //////////////////////////////////////////////////////////////////////////////
 102 void CGC::verify_heap_top()
 103 {  void ** try_addr = (void **)((char*)GC_TRUNC_ADDR(heap_top) - GC_ALIGNMENT);
 104    if (is_debugging() && console)
 105    {  (*console) << "[ GC" << id
 106                  << ": checking heap top address " << (void*)try_addr
 107                  << " ]\n" << flush;
 108    }
 109
 110    void * dummy_unused_variable = *try_addr; // may trap here
 111
 112    if (is_debugging() && console)
 113    {  (*console) << "[ GC" << id
 114                  << ": heap top address " << (void*)try_addr
 115                  << " is ok ]\n" << flush;
 116    }
 117 }
 118
 119
 120 //////////////////////////////////////////////////////////////////////////////
 121 //  Method to flush the register windows on the sparc
 122 //////////////////////////////////////////////////////////////////////////////
 123 #if 0
 124 #ifdef sparc
 125    asm ("       .seg \"text\"");
 126    asm ("       .globl _flush_sparc_register_windows");
 127    asm ("_flush_sparc_register_windows:");
 128    asm ("       ta 3");
 129    asm ("       mov %sp, %o0");
 130    asm ("       retl");
 131    asm ("       nop");   // delay slot
 132 extern "C" void * flush_sparc_register_windows();
 133 #endif
 134 #endif
 135 void CGC::flush_registers()
 136 {
 137 #if 0
 138 #ifdef sparc
 139    flush_sparc_register_windows();
 140 #endif
 141 #endif
 142 }
 143
 144 //////////////////////////////////////////////////////////////////////////////
 145 //
 146 //  Get the bottom heap address
 147 //
 148 //////////////////////////////////////////////////////////////////////////////
 149 void * CGC::global_heap_bottom = 0;
 150 void * CGC::get_heap_bottom()
 151 {  if (global_heap_bottom != 0) return global_heap_bottom;
 152    global_heap_bottom = (void*)GC_GET_HEAP_BOTTOM;
 153    void * static_data_end = (void*)GC_DATA_END;
 154    global_heap_bottom =
 155       get_address_limit(global_heap_bottom, static_data_end, -1);
 156    return global_heap_bottom;
 157 }
 158
 159 //////////////////////////////////////////////////////////////////////////////
 160 //
 161 //  Retrieve the limit address
 162 //
 163 //////////////////////////////////////////////////////////////////////////////
 164 static volatile Bool segfault;
 165 static void segfault_handler(int) { segfault = true; }
 166 void * CGC::get_address_limit(void * start, void * limit, int dir)
 167 {  segfault = false;
 168 #ifdef DEBUG_GC
 169    if (console)
 170       (*console) << "[ CGC::get_address_limit(" << start << ", " << limit
 171                  << ")]\n";
 172 #endif
 173    typedef void (*signal_handler)(int);
 174    signal_handler old_handler = signal(SIGSEGV, segfault_handler);
 175    void * addr = start;
 176    void * new_addr;
 177    if (dir > 0)
 178    {  long dummy = 0;
 179       for (addr = start; addr < limit; addr = ((long *)addr) + dir)
 180       {  dummy += *(long *)addr;
 181          if (segfault) break;
 182       }
 183    } else
 184    {  long dummy = 0;
 185       for (addr = start; addr > limit; addr = ((long *)addr) + dir)
 186       {  dummy += *(long *)addr;
 187          if (segfault) break;
 188       }
 189    }
 190    addr = ((long*)addr) - dir;
 191    signal(SIGSEGV, old_handler);
 192 #ifdef DEBUG_GC
 193    if (console)
 194    {  (*console) << "[ CGC::get_address_limit(" << start << ", " << limit
 195                  << ") = " << addr << "]\n";
 196    }
 197 #endif
 198    return addr;
 199 }
 200
 201 //////////////////////////////////////////////////////////////////////////////
 202 //  Constructor.
 203 //////////////////////////////////////////////////////////////////////////////
 204 CGC::CGC()
 205 {
 206    //
 207    // Determine the boundaries of the stack, heap, and static area.
 208    //
 209    void * stack_mark1[1];
 210    stack_bottom    = compute_stack_bottom(stack_mark1, is_downward_stack);
 211    stack_top       = stack_bottom;
 212    data_bottom     = (void**)GC_DATA_START;
 213    data_top        = (void**)GC_DATA_END;
 214    heap_bottom     = (void**)get_heap_bottom();
 215    heap_top        = heap_bottom;
 216
 217    // Set the initial heap size and heap growth.
 218    // Be conservative and let the subclass override them if necessary
 219    initial_heap_size = 128 * 1024;
 220    min_heap_growth   = 256 * 1024;
 221
 222    // Initialize the scanning queue
 223    scan_queue                     = 0;
 224    scan_limit_queue               = 0;
 225    scan_queue_size                = 0;
 226    number_of_pages_to_scan        = 0;
 227
 228    initialization_message();
 229 }
 230
 231 //////////////////////////////////////////////////////////////////////////////
 232 //  Destructor
 233 //////////////////////////////////////////////////////////////////////////////
 234 CGC::~CGC()
 235 {
 236    delete [] scan_queue;
 237    cleanup_message();
 238 }
 239
 240 //////////////////////////////////////////////////////////////////////////////
 241 //  Methods for setting the initial heap size and amount of heap growth
 242 //////////////////////////////////////////////////////////////////////////////
 243 void CGC::set_initial_heap_size (size_t n) { initial_heap_size = n; }
 244 void CGC::set_min_heap_growth   (size_t n) { min_heap_growth = n; }
 245
 246 //////////////////////////////////////////////////////////////////////////////
 247 //  Method that returns the size of an allocated block
 248 //////////////////////////////////////////////////////////////////////////////
 249 size_t CGC::size(const void * obj) const
 250 {  if (HM::is_mapped((void*)obj) &&
 251        HM::get_object_map().is_marked((void*)obj)) {
 252       return GC_OBJ_HEADER_LEN(GC_OBJ_HEADER(obj));
 253    } else {
 254       return 0;
 255    }
 256 }
 257
 258 //////////////////////////////////////////////////////////////////////////////
 259 //  Method for growing the scan queue
 260 //////////////////////////////////////////////////////////////////////////////
 261 void CGC::grow_scan_queue(size_t pages)
 262 {  if (scan_queue_size < pages) {
 263       delete [] scan_queue;
 264       scan_queue       = new size_t [2 * pages];
 265       scan_limit_queue = scan_queue + pages;
 266       scan_queue_size  = pages;
 267    }
 268 }
 269
 270 //////////////////////////////////////////////////////////////////////////////
 271 //  Method for printing an initialization message
 272 //////////////////////////////////////////////////////////////////////////////
 273 void CGC::initialization_message() const
 274 {
 275    if (is_debugging() && console)
 276       (*console) << "[ GC" << id
 277                  << ": initializing (page size = " << GC_PAGE_SIZE
 278                  << ", alignment = " << GC_ALIGNMENT << ") ]\n" << flush;
 279 }
 280
 281 //////////////////////////////////////////////////////////////////////////////
 282 //  Method for printing a cleanup message
 283 //////////////////////////////////////////////////////////////////////////////
 284 void CGC::cleanup_message() const
 285 {
 286    if (is_debugging() && console)
 287       (*console) << "[ GC" << id << ": cleaning up. ]\n" << flush;
 288 }
 289
 290 //////////////////////////////////////////////////////////////////////////////
 291 //  Method for printing a scanning message.
 292 //////////////////////////////////////////////////////////////////////////////
 293 void CGC::scanning_message(const char * area, void * start, void * stop) const
 294 {
 295    if (is_debugging() && console) {
 296       (*console) << "[ GC" << id << ": scanning the " << area
 297                  << " (" << start << " ... " << stop << ") "
 298                  << ((Byte*)stop - (Byte*)start) << " bytes ]\n" << flush;
 299    }
 300 }
 301
 302 //////////////////////////////////////////////////////////////////////////////
 303 //  Method for performing weak pointer collection
 304 //////////////////////////////////////////////////////////////////////////////
 305 void CGC::do_weak_pointer_collection()
 306 {  if (! should_collect_weak_pointers) return;
 307    int size     = WeakPointerManager::size();
 308    int capacity = WeakPointerManager::capacity();
 309    if (size == 0) return;
 310    if ((verbosity_level & gc_notify_weak_pointer_collection) && console) {
 311       (*console) << "[ GC" << id << ": weakpointer collection ("
 312                  << size << "/" << capacity << ") ..." << flush;
 313    }
 314    WeakPointerManager::scavenge_wp_table(this);
 315    int new_size     = WeakPointerManager::size();
 316    int new_capacity = WeakPointerManager::capacity();
 317    if ((verbosity_level & gc_notify_weak_pointer_collection) && console) {
 318       (*console) << " done (" << new_size << "/" << new_capacity
 319                  << ") ]\n" << flush;
 320    }
 321 }