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