lib-src/gc/gcverify.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 <AD/gc/gcverify.h>  // verifier
  27 #include <AD/gc/gcheaps.h>   // heap manager
  28 #include <AD/gc/gcbitmap.h>  // bitmap
  29 #include <AD/gc/gcmacros.h>  // useful macros
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //  Import some types
  33 //////////////////////////////////////////////////////////////////////////////
  34 typedef GCVerifier::Statistics Statistics;
  35
  36 //////////////////////////////////////////////////////////////////////////////
  37 //  Constructor and destructor
  38 //////////////////////////////////////////////////////////////////////////////
  39 GCVerifier:: GCVerifier() : ok(true), testing_gc(0), traversed(0) {}
  40 GCVerifier::~GCVerifier() { delete traversed; }
  41
  42 //////////////////////////////////////////////////////////////////////////////
  43 //  Name of this class
  44 //////////////////////////////////////////////////////////////////////////////
  45 const char * GCVerifier::my_name() const { return "GCVerifier"; }
  46
  47 //////////////////////////////////////////////////////////////////////////////
  48 //  Method for verifying that a pointer is to a valid object.
  49 //////////////////////////////////////////////////////////////////////////////
  50 Bool GCVerifier::is_valid_pointer(GCObject * obj, GC * gc)
  51 {
  52    if (! IS_WITHIN_BOUNDS(obj)) return false;
  53    if (! IS_USED(obj,gc->gc_id())) return false;
  54    if (! HM::object_map.is_marked(obj)) return false;
  55    return true;
  56 }
  57
  58 //////////////////////////////////////////////////////////////////////////////
  59 //  Method for verifying that a pointer is a valid interior pointer to
  60 //  an object.
  61 //////////////////////////////////////////////////////////////////////////////
  62 Bool GCVerifier::is_valid_interior_pointer(GCObject * obj, GC * gc)
  63 {
  64    if (! IS_WITHIN_BOUNDS(obj)) return false;
  65    if (! IS_USED(obj,gc->gc_id())) return false;
  66    void * obj_ptr = HM::object_map.starting_addr(obj);
  67    if (obj_ptr == 0) return false;
  68    if (! IS_USED(obj_ptr,gc->gc_id())) return false;
  69    GCHeader header = GC_OBJ_HEADER(obj_ptr);
  70    if (GC_OBJ_IS_FORWARDED(header)) return false;
  71    size_t   size  = GC_OBJ_HEADER_LEN(header);
  72    Byte *   limit =
  73       (Byte*)obj_ptr + size - GC_ALIGNMENT + sizeof(GCHeader);
  74    if ((Byte*)obj >= limit) return false;
  75    return true;
  76 }
  77
  78 //////////////////////////////////////////////////////////////////////////////
  79 //  Method for verifying an allocated structure on the heap.
  80 //////////////////////////////////////////////////////////////////////////////
  81 Bool GCVerifier::is_valid_structure (GCObject * obj, GC * gc)
  82 {
  83    if (! is_valid_interior_pointer(obj, gc)) return false;
  84    traversed = new GCBitMap; // allocate a bitmap
  85    testing_gc = gc;          // set the default gc
  86    nodes = 0;                // reset the number of nodes traced
  87    ok = true;                // everything is ok for now
  88    obj->trace(gc);           // trace object
  89    delete traversed;         // delete the bitmap
  90    return ok;                // return result
  91 }
  92
  93 //////////////////////////////////////////////////////////////////////////////
  94 //  Method for tracing an object and verifying its correctness.
  95 //////////////////////////////////////////////////////////////////////////////
  96 GCObject * GCVerifier::trace (GCObject * obj)
  97 {
  98    if (! GC_IS_A_POINTER(obj)) return obj;
  99
 100    register void * obj_ptr = 0;
 101
 102    ///////////////////////////////////////////////////////////////////////////
 103    //  Check only objects lying within the same heap.
 104    ///////////////////////////////////////////////////////////////////////////
 105    if (IS_WITHIN_BOUNDS(obj)            &&
 106        IS_USED(obj,testing_gc->gc_id()) &&
 107        (obj_ptr = HM::object_map.starting_addr(obj)) != 0 &&
 108        IS_USED(obj_ptr,testing_gc->gc_id())) {
 109       ////////////////////////////////////////////////////////////////////////
 110       //  Check to see if object is a valid interior pointer to object.
 111       ////////////////////////////////////////////////////////////////////////
 112       GCHeader header = GC_OBJ_HEADER(obj_ptr);
 113       size_t   size  = GC_OBJ_HEADER_LEN(header);
 114       Byte *   limit =
 115          (Byte*)obj_ptr + size - GC_ALIGNMENT + sizeof(GCHeader);
 116       if ((Byte*)obj >= limit) {
 117          // Not a valid object pointer.
 118          if (verbosity_level & gc_print_debugging_info) {
 119             cerr << "[ WARNING: object pointer "
 120                  << (void*)obj << " is invalid ]\n";
 121          }
 122          ok = false; return obj;
 123       }
 124    }
 125
 126    ///////////////////////////////////////////////////////////////////////////
 127    // Trace subobject, but make sure that we don't visit the same node twice.
 128    ///////////////////////////////////////////////////////////////////////////
 129    if (! traversed->is_within_bounds(obj_ptr))
 130       traversed->grow(obj_ptr, (Byte*)obj_ptr + GC_PAGE_SIZE);
 131    if (traversed->is_marked(obj_ptr)) return obj;
 132    traversed->mark(obj_ptr);
 133    nodes++;
 134    obj->trace(this);
 135    return obj;
 136 }
 137
 138 //////////////////////////////////////////////////////////////////////////////
 139 //  Dummied methods
 140 //////////////////////////////////////////////////////////////////////////////
 141 void     * GCVerifier::m_alloc(size_t)
 142    {error("m_alloc is unimplemented"); return 0;}
 143 void       GCVerifier::free(void *)      {error("free is unimplemented");}
 144 void       GCVerifier::collect(int)      {error("collect is unimplemented");}
 145 void       GCVerifier::grow_heap(size_t) {error("grow_heap is unimplemented");}
 146 Statistics GCVerifier::statistics()
 147    { Statistics s; reset_statistics(s);
 148      error("statistics is unimplemented"); return s;
 149    }
 150