lib-src/gc/weakptr.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-1997
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <string.h>
  26 #include <AD/gc/weakptr.h>    // weak pointers
  27 #include <AD/gc/gcheaps.h>    // heap manager
  28 #include <AD/gc/gcmacros.h>   // useful macros
  29
  30 //////////////////////////////////////////////////////////////////////////////
  31 //  Import some types
  32 //////////////////////////////////////////////////////////////////////////////
  33 typedef WeakPointerManager::WP_Index     WP_Index;
  34 typedef WeakPointerManager::WP_TimeStamp WP_TimeStamp;
  35 typedef WeakPointerManager::WP_Entry     WP_Entry;
  36
  37 //////////////////////////////////////////////////////////////////////////////
  38 //  Static data.
  39 //
  40 //  The dummy entry is needed to make sure that when we dereference
  41 //  an empty weak pointer before we have any entries in the weak pointer table
  42 //  we don't dereference the null pointer.
  43 //////////////////////////////////////////////////////////////////////////////
  44 static WP_Entry dummy_entry[1];
  45 WP_Entry *   WeakPointerManager::wp_table          = dummy_entry;
  46 WP_Entry *   WeakPointerManager::wp_next_free      = 0;
  47 void     *   WeakPointerManager::wp_table_core     = 0;
  48 size_t       WeakPointerManager::wp_table_size     = 0;
  49 size_t       WeakPointerManager::wp_table_capacity = 0;
  50 WP_TimeStamp WeakPointerManager::wp_timestamp      = 0;
  51
  52 //////////////////////////////////////////////////////////////////////////////
  53 //  Constructor and destructor
  54 //////////////////////////////////////////////////////////////////////////////
  55 WeakPointerManager:: WeakPointerManager() {}
  56 WeakPointerManager::~WeakPointerManager() {}
  57
  58 //////////////////////////////////////////////////////////////////////////////
  59 //  Method to add a new pointer into the weakpointer table.
  60 //  We have a BIG problem: since objects can be moved around by the
  61 //  collectors we can't really hash their addresses.   So in the meantime
  62 //  we won't bother with hashing at all.
  63 //
  64 //  In the current setup the table is just an array.  Unused entries are
  65 //  linked together in a freelist.  Assignment of weakpointer can be
  66 //  accomplished in O(1) amortized time(and unfortunately O(1) space.)
  67 //////////////////////////////////////////////////////////////////////////////
  68 WP_Index WeakPointerManager::add_pointer(GCObject * obj, WP_TimeStamp& ts)
  69 {
  70    if (obj == 0) { ts = 0; return 0; }
  71
  72    for (;;) {
  73       if (wp_next_free) {
  74          WP_Index i = wp_next_free - wp_table;
  75          wp_next_free->object    = obj;
  76          wp_next_free->timestamp = ts = ++wp_timestamp;
  77          wp_next_free = wp_next_free->next;
  78          wp_table_size++;
  79          return i;
  80       } else {
  81          if (wp_table_capacity == wp_table_size)
  82          {  GC::garbage_collect();
  83             if (wp_table_capacity == wp_table_size)
  84                grow_wp_table();
  85          } else {
  86             WP_Index i = wp_table_size;
  87             wp_table[i].object    = obj;
  88             wp_table[i].timestamp = ts = ++wp_timestamp;
  89             wp_table_size++;
  90             return i;
  91          }
  92       }
  93    }
  94 }
  95
  96 //////////////////////////////////////////////////////////////////////////////
  97 //  Method to expand the wp_table when necessary.
  98 //  The wp_table *must* be blacklisted so that the entries are not
  99 //  mistaken for ``strong'' pointers by the collectors.
 100 //////////////////////////////////////////////////////////////////////////////
 101 void WeakPointerManager::grow_wp_table()
 102 {  if (wp_table_capacity == wp_table_size) {
 103
 104       // Compute the new size, round it up to page boundaries
 105       size_t new_size = GC_ROUNDUP_PAGE_SIZE(wp_table_size *3 / 2 + 1024);
 106
 107       // Allocate a new table.
 108       void *     new_wp_table_core;
 109       WP_Entry * new_wp_table =
 110          (WP_Entry*)HM::allocate_pages_on_boundaries
 111             (new_size * sizeof(WP_Entry), new_wp_table_core);
 112       WP_Entry * new_limit   = new_wp_table + new_size;
 113
 114       // Blacklist the new table and unblacklist the old one.
 115       HM::blacklist_system_heap (wp_table, wp_table + wp_table_capacity, false);
 116       HM::grow_page_table       (new_wp_table, new_limit);
 117       HM::blacklist_system_heap (new_wp_table, new_limit, true);
 118
 119       // Copy the old table into the new
 120       memcpy (new_wp_table, wp_table, wp_table_capacity * sizeof(WP_Entry));
 121
 122       // Delete the old table
 123       HM::deallocate_pages_on_boundaries
 124          (wp_table_core, wp_table_capacity * sizeof(WP_Entry));
 125
 126       // Update various static data
 127       wp_table          = new_wp_table;
 128       wp_table_capacity = new_size;
 129       wp_table_core     = new_wp_table_core;
 130    }
 131 }
 132
 133 //////////////////////////////////////////////////////////////////////////////
 134 //  Method to scavenge and update the wp_table during finalization.
 135 //  Only entries owned by the collector 'gc' will be touched.
 136 //  Weakpointer entries to dying objects will be reclaimed.
 137 //////////////////////////////////////////////////////////////////////////////
 138 void WeakPointerManager::scavenge_wp_table(GC * gc)
 139 {  register GC::GC_ID id = gc->gc_id();
 140    for (register WP_Entry * p = wp_table, * q = wp_table + wp_table_capacity;
 141         p < q; p++) {
 142       register GCObject * obj = p->object;
 143       if (HM::is_mapped(obj) && HM::page_gc(obj) == id) {
 144          switch (HM::page_status(obj)) {
 145             case HM::to_space:
 146             case HM::from_space:
 147             {  // See if object has been moved.
 148                if (HM::get_object_map().is_marked(obj)) {
 149                   if (HM::get_live_map().is_marked(obj)) {
 150                      // Object has been promoted.  Preserve it.
 151                      break;
 152                   } else {
 153                      // Object has either been moved or is dying
 154                      register GCHeader header = GC_OBJ_HEADER(obj);
 155                      if (GC_OBJ_IS_FORWARDED(header)) {
 156                         // Object has been moved
 157                         // Update and forward the address.
 158                         p->object = GC_OBJ_FORWARD_ADDR(header);
 159                         break;
 160                      }
 161                   }
 162                }
 163             }  // falls thru
 164             case HM::blacklisted:
 165             case HM::not_allocated:
 166             {  // Now delete the object.
 167                // The freed entry is recycled back into the free list.
 168                p->object = 0;
 169                p->timestamp = 0;
 170                wp_table_size--;
 171                p->next = wp_next_free;
 172                wp_next_free = p;
 173             }  break;
 174             case HM::newly_allocated:
 175                // skip
 176                break;
 177          }
 178       }
 179    }
 180 }