tests/test_gc11.pcc

   1 //////////////////////////////////////////////////////////////////////////////
   2 //  Program to test garbage collection with pointer sharing.
   3 //////////////////////////////////////////////////////////////////////////////
   4
   5 #include <iostream.h>
   6 #include <stdlib.h>
   7 #include <assert.h>
   8 #include <unistd.h>
   9 #include <AD/gc/gcheaps.h>
  10 #include <AD/gc/markswp.h>
  11
  12 #define NODES (256 * 1024)
  13 #define TRIALS 10
  14 #define SHARING
  15
  16 MarkSweepGC marksweep_gc;
  17
  18 //////////////////////////////////////////////////////////////////////////////
  19 //  Datatype TREE is just a simple binary tree (actually a dag in our case).
  20 //////////////////////////////////////////////////////////////////////////////
  21 datatype TREE :: collectable = empty | node (TREE, int, TREE);
  22 instantiate datatype TREE;
  23
  24 //////////////////////////////////////////////////////////////////////////////
  25 //  Compute the sum of all nodes of a tree
  26 //////////////////////////////////////////////////////////////////////////////
  27 int sum (TREE t)
  28 {  match (t) {
  29       case empty:        return 0;
  30       case node(x,i,y):  return sum(x) + i + sum(y);
  31    }
  32 }
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //  Count the number of pointer sharings.
  36 //////////////////////////////////////////////////////////////////////////////
  37 int sharing (TREE t)
  38 {  match (t) {
  39       case empty:        return 0;
  40       case node(x,i,y):  return sharing(x) + sharing(y)
  41                                  + ((x != empty && x == y) ? 1 : 0);
  42    }
  43 }
  44
  45 //////////////////////////////////////////////////////////////////////////////
  46 //  Compute the size of a tree
  47 //////////////////////////////////////////////////////////////////////////////
  48 int size (TREE t)
  49 {  match (t) {
  50       case empty:        return 0;
  51       case node(x,i,y):  return size(x) + 1 + size(y);
  52    }
  53 }
  54
  55 //////////////////////////////////////////////////////////////////////////////
  56 //  Check a tree for correctness.
  57 //////////////////////////////////////////////////////////////////////////////
  58 void check (TREE t)
  59 {  match (t) {
  60       case empty:        return;
  61       case node(x,i,y):
  62          assert (HM::is_mapped(t) &&
  63                  HM::page_gc(t) == GC::get_default_gc().gc_id());
  64          assert (HM::get_object_map().is_marked(t));
  65          check(x); check(y);
  66    }
  67 }
  68
  69 //////////////////////////////////////////////////////////////////////////////
  70 //  Routine to make a random tree of a certain size.
  71 //////////////////////////////////////////////////////////////////////////////
  72 TREE make_tree(int n)
  73 {  if (n == 0) return empty;
  74    int split = rand() % n;
  75    int data  = rand() % n;
  76 #ifdef SHARING
  77    if ((n % 2 == 1) && (rand() % 2 == 1)) {
  78       TREE t = make_tree(n/2);
  79       return node(t, data, t);
  80    }
  81 #endif
  82    return node(make_tree(split), data, make_tree(n - split - 1));
  83 }
  84
  85 void testing()
  86 {
  87    for (int trial = 1; trial <= TRIALS; trial++) {
  88        cout << "Trial number " << trial << '\n' << flush;
  89        TREE tree1    = make_tree(NODES);
  90        int  size1    = size(tree1);
  91        int  sum1     = sum(tree1);
  92        int  sharing1 = sharing (tree1);
  93        check(tree1);
  94
  95        cout << "Size = " << size1 << " check sum = " << sum1
  96             << " pointer sharing = " << sharing1 << '\n' << flush;
  97
  98        make_tree(NODES);              // this just generates a lot of garbage
  99
 100        // Now traverse the tree check things.
 101        assert(size(tree1)     == NODES);
 102        assert(sum(tree1)      == sum1);
 103        assert(sharing(tree1)  == sharing1);
 104        check(tree1);
 105        cout << "Trial number " << trial << " has passed\n";
 106    }
 107 }
 108
 109 int main()
 110 {
 111    GC::set_default_gc(marksweep_gc);
 112    cout <<
 113      "This test generate random dags and try to see if garbage collection\n"
 114      "works on preserving pointer sharing correctly.  I'll do this "
 115       << TRIALS << " times.\n";
 116    srand(getpid());
 117    testing();
 118    // force an explicit garbage collection
 119    cout << "Finished.  Now I'm forcing another garbage collection to clean\n"
 120            "things up.  There should be very little garbage left at the end.\n";
 121    GC::garbage_collect();
 122    return 0;
 123 }