lib-src/gc/bgc.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 <AD/gc/gcconfig.h>  // system configuration
  32 #include <AD/gc/bgc.h>       // Bartlett's garbage collector
  33 #include <AD/gc/gcobject.h>  // garbage collectable objects
  34 #include <AD/gc/gcheaps.h>   // the heap manager
  35 #include <AD/gc/gcmacros.h>  // useful macros
  36 #include <AD/gc/weakptr.h>   // weak pointers
  37 #include <AD/gc/gctimer.h>
  38
  39 //////////////////////////////////////////////////////////////////////////////
  40 //  Some identifying information.
  41 //////////////////////////////////////////////////////////////////////////////
  42 // #define DEBUG_GC  // no debugging for production use
  43 #define SANITY_CHECK // inexpensive checking (left in place for your assurance)
  44 #define ALGORITHM "Mostly copying with blacklisting"
  45 #define VERSION   "0.5 (Feb 11th, 1995)"
  46
  47 #ifdef DEBUG_GC
  48 #   define SANITY_CHECK
  49 #endif
  50
  51 //////////////////////////////////////////////////////////////////////////////
  52 //  Import some types
  53 //////////////////////////////////////////////////////////////////////////////
  54 typedef HM::GCPageId   GCPageId;
  55 typedef HM::PageStatus PageStatus;
  56
  57 //////////////////////////////////////////////////////////////////////////////
  58 //  Method that returns a name for this class
  59 //////////////////////////////////////////////////////////////////////////////
  60 const char * BGC::my_name() const { return "BGC"; }
  61
  62 //////////////////////////////////////////////////////////////////////////////
  63 //  Constructor.
  64 //////////////////////////////////////////////////////////////////////////////
  65 BGC::BGC()
  66 {
  67    // Perform initialization steps:
  68    heap_pointer                   = 0;
  69    heap_limit                     = 0;
  70    gc_limit                       = 0;
  71    phase                          = mutation_phase;
  72    heap_used                      = 0;
  73    heap_size                      = 0;
  74    initial_heap_size              = 128 * 1024;
  75    min_heap_growth                = 512 * 1024;
  76    should_collect                 = false;
  77
  78    stat.algorithm                 = ALGORITHM;
  79    stat.version                   = VERSION;
  80    reset_statistics(stat);
  81 }
  82
  83 //////////////////////////////////////////////////////////////////////////////
  84 //  Destructor
  85 //////////////////////////////////////////////////////////////////////////////
  86 BGC::~BGC()
  87 {
  88    clear();
  89 }
  90
  91 //////////////////////////////////////////////////////////////////////////////
  92 //  Method that releases all the memory within the collector.
  93 //  The collector is now in a clean slate (though the statistics are
  94 //  not reset).  Use with caution!
  95 //////////////////////////////////////////////////////////////////////////////
  96 void BGC::clear()
  97 {
  98    heap_pointer = 0;
  99    heap_limit   = 0;
 100    gc_limit     = 0;
 101    heap_used    = 0;
 102    heap_size    = 0;
 103    HM::release_all_pages(this);
 104 }
 105
 106 //////////////////////////////////////////////////////////////////////////////
 107 // Method that compute the minimal amount of heap expansion
 108 // that should be done.
 109 //////////////////////////////////////////////////////////////////////////////
 110 size_t BGC::min_growth()
 111 {
 112    return heap_size == 0 ? initial_heap_size : min_heap_growth;
 113 }
 114
 115 //////////////////////////////////////////////////////////////////////////////
 116 //  Method to allocate a new object of a given size
 117 //////////////////////////////////////////////////////////////////////////////
 118 void * BGC::m_alloc(size_t n)
 119 {  // round up the size
 120    size_t bytes = GC_ROUNDUP_SIZE(n + sizeof(GCHeader));
 121
 122    // if we have enough space in current fragment, then use it.
 123    if (heap_pointer + bytes > gc_limit) {
 124       // No more space left, we'll try to get some more from the
 125       // the heap manager and/or garbage collect.
 126
 127       //
 128       // Try garbage collection first if the gc_ratio is reached.
 129       //
 130       if (should_collect) collect();
 131
 132       //
 133       // Now try to expand the heap if there is still a need to.
 134       //
 135       if (heap_pointer + bytes > gc_limit) grow_heap (bytes);
 136    }
 137
 138    // Get new storage for object.
 139    // Stamp the starting address into the bitmap.
 140
 141    GCObject * new_obj = GC_OBJ_OBJECT_ADDR(heap_pointer);
 142    GC_OBJ_SET_HEADER(new_obj, bytes);
 143    heap_pointer += bytes;
 144    HM::object_map.mark(new_obj);
 145    return new_obj;
 146 }
 147
 148 //////////////////////////////////////////////////////////////////////////////
 149 //  Method to deallocate an object manually.
 150 //  Note: this method tries to catch errors involving deallocation.
 151 //////////////////////////////////////////////////////////////////////////////
 152 void BGC::free(void * obj)
 153 {
 154    // Ignores all requests that do not lie on our heap space
 155    if (! GC_IS_A_POINTER(obj)) return;
 156    if (HM::is_mapped(obj)     &&
 157        HM::page_gc(obj) == id &&
 158        HM::get_object_map().is_marked(obj)) {
 159       // Just unmark the object.  The space is not really
 160       // reclaimed at this point; instead it will be reclaimed
 161       // at the next collection.
 162       HM::object_map.unmark(obj);
 163    } else {
 164
 165       // Hold on, Pedro!  The object doesn't seem to exist!
 166       cerr << "[ GC" << id
 167            << ": application tries to free non-existent object at "
 168            << (void*)obj << " ]\n" << flush;
 169    }
 170 }
 171
 172 //////////////////////////////////////////////////////////////////////////////
 173 //  Method for expanding the heap.
 174 //  We try to expand the heap only if the number of bytes requested
 175 //  is not immediately available.
 176 //////////////////////////////////////////////////////////////////////////////
 177 void BGC::grow_heap (size_t bytes)
 178 {
 179    size_t old_total = heap_size + HM::bytes_free();
 180    size_t wanted    = bytes + sizeof(GCHeader);
 181    size_t growth;
 182    Byte * storage =
 183      (Byte*)HM::allocate_pages
 184               ( this, wanted,
 185                 (heap_size == 0 ? initial_heap_size : min_heap_growth),
 186                 growth,
 187                 phase == copying_phase ? HM::newly_allocated :
 188                                          HM::from_space
 189               );
 190
 191    if (storage == 0) {
 192       // Growth failed!
 193       cerr << "[ GC" << id << ": Out of memory!  Can't allocate "
 194            << bytes << " bytes from system. ]\n" << flush;
 195       exit (1);
 196    }
 197
 198    heap_pointer = storage + GC_ALIGNMENT - sizeof(GCHeader);
 199    heap_limit   = storage + growth;
 200    heap_start   = heap_pointer;
 201    heap_size   += heap_limit - heap_pointer;
 202    heap_used    = heap_size - (heap_limit - heap_pointer);
 203    size_t new_total = heap_size + HM::bytes_free();
 204    gc_limit     = storage + new_total * gc_ratio / 100 - heap_used;
 205    should_collect = gc_limit <= heap_limit;
 206    if (gc_limit > heap_limit) gc_limit = heap_limit;
 207    if (heap_pointer + wanted > gc_limit) gc_limit = heap_limit;
 208    if (new_total > old_total) {
 209       stat.number_of_heap_expansions++;
 210       heap_growth_message(heap_size, growth);
 211    }
 212 }
 213
 214 //////////////////////////////////////////////////////////////////////////////
 215 //  Method for tracing an object pointer.
 216 //  Tracing moves object currently in the heap into the to-space.
 217 //////////////////////////////////////////////////////////////////////////////
 218 GCObject * BGC::trace (GCObject * ptr)
 219 {
 220 #ifdef GC_HAS_CROSS_HEAP_POINTERS
 221    // make sure it is a pointer first.
 222    // Since Prop uses small unmapped addresses to represent
 223    // unit functors it is a good idea to check first if we allow
 224    // cross heap pointer lest these things get mistaken for the real thing.
 225    if (! GC_IS_A_POINTER(ptr)) return ptr;
 226 #endif
 227
 228    // Objects not within the current collector heap are skipped.
 229    if (! IS_WITHIN_BOUNDS(ptr) || ! IS_USED_ADDR(ptr,id)) {
 230 #ifdef GC_HAS_CROSS_HEAP_POINTERS
 231       // We'll grow the traversed map incrementally
 232 #ifdef DEBUG_GC
 233       assert(HM::traversed_map.is_within_bounds(ptr));
 234 #endif
 235       if (! HM::traversed_map.is_marked(ptr)) {
 236          HM::traversed_map.mark(ptr);
 237          ptr->trace(this);
 238       }
 239 #endif
 240       return ptr;
 241    }
 242
 243    // Get starting address of object.
 244    void * obj_ptr = HM::object_map.starting_addr(ptr);
 245
 246    // If it is a new object then just return, since it must already
 247    // have been properly traced.
 248    if (IS_NEW_ADDR(obj_ptr)) return ptr;
 249
 250 #ifdef DEBUG_GC
 251    if (ptr != obj_ptr)
 252       cerr << "[ Warning: pointer is at " << (void*)ptr << " but object is "
 253            << (void*)obj_ptr << " ]\n" << flush;
 254 #endif
 255
 256    // Get header of object
 257    GCHeader header = GC_OBJ_HEADER(obj_ptr);
 258
 259    // If it is a forwarded object then set the forwarding address;
 260    // then exit.
 261    if (GC_OBJ_IS_FORWARDED(header)) {
 262       return (GCObject*)((Byte*)GC_OBJ_FORWARD_ADDR(header) +
 263                     ((Byte*)ptr - (Byte*)obj_ptr));
 264    }
 265
 266    // If the object is marked live then it cannot be moved, so just return
 267    if (HM::live_map.is_marked(obj_ptr)) return ptr;
 268
 269    // Okay, seems like we'll have to copy this object.
 270    size_t size = GC_OBJ_HEADER_LEN(header);
 271    if (heap_pointer + size > heap_limit) {
 272       bytes_copied += heap_pointer - heap_start;
 273       grow_heap (size);
 274       enqueue_pages_to_scan(heap_pointer, heap_limit);
 275    }
 276
 277    // Mark new object
 278    GCObject * new_obj = GC_OBJ_OBJECT_ADDR(heap_pointer);
 279    HM::object_map.mark(new_obj);
 280
 281    // Copy object
 282    int * src  = (int*)GC_OBJ_HEADER_ADDR(obj_ptr);
 283    int * dest = (int*)heap_pointer;
 284    size /= sizeof(int);
 285    while (size-- > 0) { *dest++ = *src++; }
 286    heap_pointer = (Byte*)dest;
 287
 288    // Leave a forwarding address in the header of the old object.
 289    GC_OBJ_SET_FORWARD(obj_ptr, new_obj);
 290
 291    // Update pointer
 292    return (GCObject*)((Byte*)new_obj + ((Byte*)ptr - (Byte*)obj_ptr));
 293 }
 294
 295 //////////////////////////////////////////////////////////////////////////////
 296 //  Method for starting the garbage collection
 297 //////////////////////////////////////////////////////////////////////////////
 298 void BGC::collect(int level)
 299 {  // if we are already performing collection don't start
 300    // it up again until it is finished.
 301    if (phase == mutation_phase && heap_size > 0) do_collect (level);
 302 }
 303
 304 //////////////////////////////////////////////////////////////////////////////
 305 //  Method for doing the actual garbage collection
 306 //////////////////////////////////////////////////////////////////////////////
 307 void BGC::do_collect(int /* level */)
 308 {
 309    ///////////////////////////////////////////////////////////////////////////
 310    // This will hold all the registers
 311    ///////////////////////////////////////////////////////////////////////////
 312    jmp_buf reg_roots;
 313
 314    ///////////////////////////////////////////////////////////////////////////
 315    // Flush registers into the jmp_buf, which'll become part of the
 316    // stack to scan.
 317    ///////////////////////////////////////////////////////////////////////////
 318    flush_registers();
 319    // if (_setjmp(reg_roots) == 0) _longjmp(reg_roots,1);
 320    if (setjmp(reg_roots) == 0) longjmp(reg_roots,1);
 321
 322    ///////////////////////////////////////////////////////////////////////////
 323    // Setup various limits for scanning
 324    ///////////////////////////////////////////////////////////////////////////
 325    if (is_downward_stack) {
 326       stack_top    = (void**)((Byte*)reg_roots);
 327    } else {
 328       stack_top    = (void**)((Byte*)reg_roots + sizeof(reg_roots));
 329    }
 330
 331    ///////////////////////////////////////////////////////////////////////////
 332    // Move the heap pointer to the next page for the to-space.
 333    // Compute the amount of heap used.
 334    // Mark the new area as newly allocated.
 335    ///////////////////////////////////////////////////////////////////////////
 336    heap_pointer = (Byte*)GC_ROUNDUP_PAGE_ADDR(heap_pointer)
 337                            + GC_ALIGNMENT - sizeof(GCHeader);
 338    heap_used    = heap_size - (heap_limit - heap_pointer)
 339                      + (GC_ALIGNMENT - sizeof(GCHeader));
 340    heap_start   = heap_pointer;
 341    HM::mark_space(heap_pointer, heap_limit, HM::newly_allocated);
 342    gc_limit     = heap_limit;
 343
 344    ///////////////////////////////////////////////////////////////////////////
 345    // Setup various statistics.
 346    ///////////////////////////////////////////////////////////////////////////
 347    bytes_copied     = 0;
 348    stat.number_of_collections++;
 349
 350    ///////////////////////////////////////////////////////////////////////////
 351    // Set up the timer
 352    ///////////////////////////////////////////////////////////////////////////
 353 #ifdef GC_USE_TIMER
 354    GCTimer user_time_at_start;
 355    GCTimer system_time_at_start;
 356    user_time_at_start.get_user_time();
 357    system_time_at_start.get_system_time();
 358 #endif
 359
 360    ///////////////////////////////////////////////////////////////////////////
 361    // Print the annoying garbage collection message
 362    ///////////////////////////////////////////////////////////////////////////
 363    start_collection_message();
 364
 365    ///////////////////////////////////////////////////////////////////////////
 366    // Setup the new scanning queue if necessary.
 367    // The 4 below is just some slack;
 368    ///////////////////////////////////////////////////////////////////////////
 369    size_t max_pages = 2 * heap_used / GC_PAGE_SIZE + 4;
 370    clear_scan_queue();
 371    grow_scan_queue(max_pages);
 372
 373    ///////////////////////////////////////////////////////////////////////////
 374    // Locate and mark all the roots in different areas of the memory
 375    ///////////////////////////////////////////////////////////////////////////
 376    phase = marking_phase;
 377    scan_stack_area  ();   // scan the stack area
 378    scan_static_area ();   // scan the static area
 379    get_heap_top();        // locate the start of the heap.
 380    scan_heap_area   ();   // scan the heap area
 381    scan_user_roots  ();   // scan the user supplied roots
 382
 383    ///////////////////////////////////////////////////////////////////////////
 384    // Now scan all promoted pages and copy all promoted objects.
 385    ///////////////////////////////////////////////////////////////////////////
 386    phase = copying_phase;
 387    copy_promoted_pages ();    // now move objects around.
 388    bytes_copied += heap_pointer - heap_start;
 389
 390    ///////////////////////////////////////////////////////////////////////////
 391    // Free all unpromoted pages
 392    ///////////////////////////////////////////////////////////////////////////
 393    HM::discard_from_space(this, heap_size, pages_removed);
 394
 395    ///////////////////////////////////////////////////////////////////////////
 396    // Recompute statistics and adjust gc limit.
 397    ///////////////////////////////////////////////////////////////////////////
 398    heap_used  = heap_size - (heap_limit - heap_pointer);
 399    size_t new_total = heap_size + HM::bytes_free();
 400    gc_limit = heap_pointer + new_total * gc_ratio / 100L - heap_used;
 401    should_collect = gc_limit <= heap_limit;
 402    if (gc_limit > heap_limit) gc_limit = heap_limit;
 403
 404    ///////////////////////////////////////////////////////////////////////////
 405    // Compute the time used for collection.
 406    ///////////////////////////////////////////////////////////////////////////
 407 #ifdef GC_USE_TIMER
 408    GCTimer user_time_at_end;
 409    GCTimer system_time_at_end;
 410    user_time_at_end.get_user_time();
 411    system_time_at_end.get_system_time();
 412    stat.gc_user_time         = user_time_at_end - user_time_at_start;
 413    stat.gc_system_time       = system_time_at_end - system_time_at_start;
 414    stat.total_gc_user_time   += stat.gc_user_time;
 415    stat.total_gc_system_time += stat.gc_system_time;
 416 #endif
 417
 418    ///////////////////////////////////////////////////////////////////////////
 419    // Now clean up properly
 420    ///////////////////////////////////////////////////////////////////////////
 421    phase = mutation_phase;
 422 #ifdef GC_HAS_CROSS_HEAP_POINTERS
 423    HM::traversed_map.clear();
 424 #endif
 425    memset(reg_roots, 0, sizeof(reg_roots));
 426
 427    ///////////////////////////////////////////////////////////////////////////
 428    //  Print the equally annoying end of collection message.
 429    ///////////////////////////////////////////////////////////////////////////
 430    end_collection_message();
 431 }
 432
 433 //////////////////////////////////////////////////////////////////////////////
 434 //  Method for scanning a consecutive block of memory for roots.
 435 //////////////////////////////////////////////////////////////////////////////
 436 inline void BGC::scan_for_roots (void ** start, void ** stop)
 437 {
 438    // Scan consecutively.
 439    // Caution: addresses between start and stop (not including stop)
 440    // must be mapped by the OS.
 441    for (void ** P = (void**)GC_TRUNC_ADDR(start); P < stop; P++) {
 442       void * ptr = *P;
 443
 444       // Try to interpret each cell as a pointer and see if it
 445       // falls within any pages of this collectable heap.
 446       if (! IS_WITHIN_BOUNDS(ptr)) continue;
 447       if (! IS_USED_ADDR(ptr, id)) continue;
 448
 449       // If so, locate the starting address (the pointer may be
 450       // an interior pointer) and trace the object.
 451       Byte * obj = (Byte*)HM::object_map.starting_addr(ptr);
 452       if (obj == 0) continue;
 453       if (! IS_USED_ADDR(obj, id)) continue;
 454
 455       // Get the header of the object.
 456       GCHeader header = GC_OBJ_HEADER(obj);
 457
 458       //  Now check whether the pointer actually lies within the
 459       //  boundary of the object.
 460       Byte * limit = obj + GC_OBJ_HEADER_LEN(header) - sizeof(GCHeader);
 461
 462       if ((Byte*)ptr >= limit) continue;  // Nope.
 463
 464       // Finally, we've found a object.  Promote the page(s) in which
 465       // it resides and mark the object as live.
 466 #ifdef DEBUG_GC
 467       cerr << "[ Promoting object *"
 468            << (void*)P << " = "
 469            << (void*)ptr << ", "
 470            << (void*)obj << " ... "
 471            << (void*)limit << " ]\n" << flush;
 472
 473       if (! IS_PROMOTED_ADDR(obj) && ! IS_FROM_SPACE_ADDR(obj)) {
 474          cerr << "[ Shit! Object is not at from space, header = "
 475               << (void*)header << " status = " << (int)SPACE_TYPE(obj)
 476               << " ]\n" << flush;
 477       }
 478 #endif
 479
 480       if (HM::live_map.is_marked(obj)) continue;
 481       objects_promoted++;
 482       HM::live_map.mark(obj);      // mark it as live
 483
 484       GCPageId p = GC_PAGE_ID(GC_OBJ_HEADER_ADDR(obj));
 485       GCPageId q = GC_PAGE_ID(limit-1);
 486
 487       //
 488       // Now make all pages straddled by object as promote.  Be extremely
 489       // careful in promote all pages.   Make sure boundary conditions
 490       // are taken care of.
 491       for ( ;p <= q; p++) {
 492          if (! IS_PROMOTED_PAGE(p)) {
 493             PROMOTE_PAGE(p);
 494             enqueue_pages_to_scan(GC_PAGE_ADDR(p), GC_PAGE_ADDR(p+1));
 495             pages_promoted++;
 496
 497 #ifdef DEBUG_GC
 498             cerr << "[ New promoted page "
 499                  << (void*)GC_PAGE_ADDR(p)
 500                  << " ... "
 501                  << (void*)GC_PAGE_ADDR(p+1)
 502                  << " gc = " << (int)PAGE_GC(p)
 503                  << " space = " << (int)PAGE_SPACE_TYPE(p)
 504                  << " ]\n" << flush;
 505 #endif
 506          }
 507       }
 508    }
 509 }
 510
 511 //////////////////////////////////////////////////////////////////////////////
 512 //  Method for scanning the stack area
 513 //////////////////////////////////////////////////////////////////////////////
 514 void BGC::scan_stack_area()
 515 {
 516    if (is_downward_stack) {
 517       // stack grows to lower addresses
 518       scanning_message("registers and stack", stack_top, stack_bottom);
 519       scan_for_roots (stack_top,  stack_bottom);
 520    } else {
 521       scanning_message("registers and stack", stack_bottom, stack_top);
 522       scan_for_roots (stack_bottom, stack_top);
 523    }
 524 }
 525
 526 //////////////////////////////////////////////////////////////////////////////
 527 //  Method for scanning the static area.
 528 //  We'll have to take into account of all the static data used
 529 //  by the heap manager.
 530 //////////////////////////////////////////////////////////////////////////////
 531 void BGC::scan_static_area()
 532 {
 533    scanning_message("static data area", data_bottom, data_top);
 534    size_t n;
 535    const HM::AddrRange * blacklisted = HM::blacklisted_data(n);
 536    size_t i = 0;
 537    void ** start = data_bottom;
 538    void ** stop  = data_top;
 539    for (start = data_bottom; start < data_top; start = stop) {
 540       while (i < n) {
 541          if (start > (void**)blacklisted[i].stop)
 542          { i++; }
 543          else if (start >= (void**)blacklisted[i].start)
 544          { start = (void**)blacklisted[i].stop; i++; }
 545          else break;
 546       }
 547       if (i < n) stop = (void**)blacklisted[i].start;
 548       else       stop = data_top;
 549       if (start < stop)
 550          scan_for_roots (start, stop);
 551    }
 552 }
 553
 554 //////////////////////////////////////////////////////////////////////////////
 555 //  Method for scanning the heap area
 556 //////////////////////////////////////////////////////////////////////////////
 557 void BGC::scan_heap_area()
 558 {
 559    scanning_message("non-collectable heap", heap_bottom, heap_top);
 560
 561    // Scan consecutively.
 562    // Caution: addresses between start and stop (not including stop)
 563    // must be mapped by the OS.
 564
 565    //
 566    // Scan all pages in the user heap that are NOT owned by this heap.
 567    // We'll do it one page at a time for now.
 568    //
 569    void ** P, ** page_limit;
 570    for (P = heap_bottom; P < heap_top; P = page_limit) {
 571       page_limit = (void**)GC_TRUNC_PAGE_ADDR((Byte*)P + GC_PAGE_SIZE);
 572       if (page_limit > heap_top) page_limit = heap_top;
 573
 574       // Check to make sure that the address is not been currently
 575       // used by us or allocated but not used.
 576       GCPageId page_id = GC_PAGE_ID(P);
 577
 578       if (IS_WITHIN_TRACKED_LIMITS(P)) {
 579          switch (PAGE_SPACE_TYPE(page_id)) {
 580             // not allocated page will be scanned
 581             case HM::not_allocated:     break;
 582
 583             // blacklisted pages will be skipped
 584             case HM::blacklisted:       continue;
 585
 586             // This page has been allocated... check some more....
 587             case HM::from_space:
 588             {  GC_ID the_id = PAGE_GC(page_id);
 589                // unused pages will be skipped.
 590                if (the_id == 0)  continue;
 591
 592                // pages within this heap will be skipped.
 593                if (the_id == id) continue;
 594
 595                // allocated pages on other heaps will be scanned.
 596             }  break;
 597
 598             // case HM::to_space:          continue;
 599             // case HM::newly_allocated:   continue;
 600
 601             // promoted pages and newly allocated pages will be skipped.
 602             default:                               continue;
 603          }
 604       }
 605
 606       // The rest of the stuff are scanned
 607       scan_for_roots(P, page_limit);
 608    }
 609 }
 610
 611 //////////////////////////////////////////////////////////////////////////////
 612 //  Method to perform finalization after all promoted
 613 //  objects have been moved.  Objects that hasn't been moved and
 614 //  is not promoted must be garbage and can be safely finalized.
 615 //////////////////////////////////////////////////////////////////////////////
 616 void BGC::do_finalization()
 617 {
 618    if (! should_finalize) return;
 619
 620    //
 621    // Invoke finalization methods of dying objects.
 622    //
 623    foreach_page_owned_by_collector(page_id, this) {
 624       switch (PAGE_SPACE_TYPE(page_id)) {
 625          case GCHeapManager::from_space:
 626          case GCHeapManager::to_space:
 627          {  Byte * page_addr  = (Byte*)GC_PAGE_ADDR(page_id);
 628             Byte * page_limit = page_addr + GC_PAGE_SIZE;
 629             while (page_addr < page_limit) {
 630                if (GCHeapManager::object_map.is_marked(page_addr)) {
 631                   GCHeader header = GC_OBJ_HEADER(page_addr);
 632                   if (GC_OBJ_IS_FORWARDED(header)) {
 633                      // Object has been moved; get its length from the
 634                      // forwarded object.
 635                      page_addr +=
 636                         GC_OBJ_HEADER_LEN(
 637                            GC_OBJ_HEADER(
 638                               GC_OBJ_FORWARD_ADDR(header)));
 639                   } else {
 640                      // Object hasn't been forwarded.
 641                      // Finalize all unpromoted objects.
 642                      if (! GCHeapManager::live_map.is_marked(page_addr)) {
 643                         ((GCObject*)page_addr)->~GCObject();
 644                      }
 645                      page_addr += GC_OBJ_HEADER_LEN(header);
 646                   }
 647                } else {
 648                   page_addr += GC_ALIGNMENT;
 649                }
 650             }
 651          }
 652       }
 653    }
 654 }
 655
 656 //////////////////////////////////////////////////////////////////////////////
 657 //  Method to scan pages within the scan queue and copy.
 658 //////////////////////////////////////////////////////////////////////////////
 659 void BGC::copy_promoted_pages ()
 660 {
 661    size_t i;
 662    phase = copying_phase;
 663
 664
 665    // Set up the pages to scan
 666    enqueue_pages_to_scan(heap_pointer, heap_limit);
 667
 668 #ifdef SANITY_CHECK
 669    size_t objects_traced = 0;
 670 #endif
 671
 672    // Scan all promoted pages first.
 673    for (i = 0; i < pages_promoted; i++) {
 674       Byte * page_addr  = (Byte*)GC_PAGE_ADDR(scan_queue[i]);
 675       Byte * page_limit = page_addr + GC_PAGE_SIZE;
 676       while (page_addr < page_limit) {
 677          if (HM::object_map.is_marked(page_addr)) {
 678             if (HM::live_map.is_marked(page_addr)) {
 679                ((GCObject*)page_addr)->trace(this);
 680 #ifdef SANITY_CHECK
 681                 objects_traced++;
 682 #endif
 683                page_addr += GC_OBJ_HEADER_LEN(GC_OBJ_HEADER(page_addr));
 684             } else {
 685                GCHeader header = GC_OBJ_HEADER(page_addr);
 686                if (GC_OBJ_IS_FORWARDED(header)) {
 687                   page_addr +=
 688                      GC_OBJ_HEADER_LEN(
 689                         GC_OBJ_HEADER(
 690                            GC_OBJ_FORWARD_ADDR(header)));
 691                } else {
 692                   page_addr += GC_OBJ_HEADER_LEN(header);
 693                }
 694             }
 695          } else {
 696             page_addr += GC_ALIGNMENT;
 697          }
 698       }
 699    }
 700
 701 #ifdef SANITY_CHECK
 702          if (objects_traced != objects_promoted) {
 703             cerr << "[ Bug: number of objects promoted = " << objects_promoted
 704                  << " while the number of objects traced = " << objects_traced
 705                  << " ]\n" << flush;
 706          }
 707 #endif
 708
 709    // Now scan all other pages on the queue.
 710    // Since these are new objects they are guaranteed to packed together.
 711    // We'll use faster code that avoids searching thru the bitmap bit by bit.
 712    for (  ; i < number_of_pages_to_scan; i++) {
 713       Byte * page_addr  =
 714          (Byte*)GC_PAGE_ADDR(scan_queue[i]) + GC_ALIGNMENT;
 715       Byte * page_limit = (Byte*)GC_PAGE_ADDR(scan_limit_queue[i]);
 716       while (page_addr < page_limit) {
 717          if (! HM::object_map.is_marked(page_addr)) break;
 718          ((GCObject*)page_addr)->trace(this);
 719          page_addr += GC_OBJ_HEADER_LEN(GC_OBJ_HEADER(page_addr));
 720       }
 721    }
 722
 723    //
 724    // Scavenge the table of weak pointers.
 725    //
 726    do_weak_pointer_collection();
 727
 728    // All objects have now been properly moved to a new space.
 729    // Perform proper finalization at this point.
 730    do_finalization();
 731
 732    // Finally, clear the affected part of the live map in the promoted
 733    // pages.  All object currently marked as allocated but not alive will
 734    // be reset.  All live bit will also be cleared in the same process.
 735    for (i = 0; i < pages_promoted; i++) {
 736       GCPageId page = scan_queue[i];
 737       Byte * page_addr  = (Byte*)GC_PAGE_ADDR(page);
 738       Byte * page_limit = page_addr + GC_PAGE_SIZE;
 739
 740       // copy the live map into the object map.
 741       HM::object_map.copy(page_addr,page_limit,HM::live_map);
 742       // clear the live map.
 743       HM::live_map.clear(page_addr, page_limit);
 744    }
 745 }
 746
 747 //////////////////////////////////////////////////////////////////////////////
 748 //  Accounting method.
 749 //////////////////////////////////////////////////////////////////////////////
 750 BGC::Statistics BGC::statistics ()
 751 {
 752    stat.bytes_used    = heap_size - (heap_limit - heap_pointer);
 753    stat.bytes_managed = heap_size;
 754    stat.bytes_free    = heap_limit - heap_pointer;
 755    return stat;
 756 }
 757
 758 //////////////////////////////////////////////////////////////////////////////
 759 //  Method for printing a heap growth message
 760 //////////////////////////////////////////////////////////////////////////////
 761 void BGC::heap_growth_message(size_t/*heap_size_now*/, size_t /*growth*/) const
 762 {
 763    if ((verbosity_level & gc_notify_heap_expansion) && console) {
 764       size_t total   = heap_size + HM::bytes_free();
 765       size_t percent = heap_used * 100 / total;
 766       (*console) << "[ GC" << id << ": increasing heap... "
 767                  << heap_used << '/' << total
 768                  << " (" << percent << "%) ]\n" << flush;
 769    }
 770 }
 771
 772 //////////////////////////////////////////////////////////////////////////////
 773 //  Method for printing a start collection message
 774 //////////////////////////////////////////////////////////////////////////////
 775 void BGC::start_collection_message() const
 776 {
 777    if (is_verbose() && console) {
 778       size_t total   = heap_size + HM::bytes_free();
 779       size_t percent = heap_used * 100 / total;
 780       (*console) << "[ GC" << id << ": collecting... "
 781                  << heap_used << '/' << total
 782                  << " (" << percent << "%) ]\n" << flush;
 783    }
 784 }
 785
 786 //////////////////////////////////////////////////////////////////////////////
 787 //  Method for printing a end collection message
 788 //////////////////////////////////////////////////////////////////////////////
 789 void BGC::end_collection_message() const
 790 {
 791    if (is_verbose() && console) {
 792       size_t total   = heap_size + HM::bytes_free();
 793       size_t percent = heap_used * 100 / total;
 794       (*console) << "[ GC" << id << ": done... "
 795                  << heap_used << '/' << total << " ("
 796                  << percent << "%)";
 797       if (verbosity_level & gc_notify_heap_info)
 798       {  (*console)
 799                  << "("
 800                  << (pages_promoted * GC_PAGE_SIZE) << " promoted, "
 801                  << bytes_copied << " moved, "
 802                  << (long)(GC_PAGE_SIZE * pages_removed - bytes_copied)
 803                  << " freed)";
 804       }
 805       (*console) << " ]\n" << flush;
 806 #ifdef GC_USE_TIMER
 807       if (verbosity_level & gc_print_collection_time) {
 808          (*console) << "[ GC" << id << ": user time: "
 809                     << stat.gc_user_time
 810                     << " system time: "
 811                     << stat.gc_system_time
 812                     << " ]\n"
 813                     << flush;
 814       }
 815 #endif
 816     }
 817 }
 818
 819 //////////////////////////////////////////////////////////////////////////////
 820 //  Create an instance of BGC and make that the default collector.
 821 //  The users are free to create others if necessary.
 822 //////////////////////////////////////////////////////////////////////////////
 823 BGC bgc;
 824 GC * GC::default_gc = &bgc;
 825
 826 GC_Initializer::GC_Initializer()
 827 {  GC::set_default_gc(bgc); }