test1:
  The most basic test.  Start with a 16 page heap.  Allocate 8 1-page
objects.  Get rid of 4 of the reference to these objects.  Allocate
another object.  The four garbage objects should be collected.  Should
be at 5 pages allocated when done.

---------------------------------------------------------------------------
test2:
  First test of objects with pointers to other objects.  allocate 4
1-page objects.  Make one of these garbage.  Allocate 3 more 1-page
objects, putting pointers to these in the 3 objects we have pointers
to.  Allocate 2 more to cause a collection.  After collection, the
objects which weren't root objects should have been copied to new
locations.  Should be 8 pages allocated when done.

---------------------------------------------------------------------------
test3:
  Once again, start with a 16-page heap.  This time, allocate 8
1/2-page objects.  Make half of these garbage, in such a way that one
page is completely freed and 2 pages are half garbage.  Next,
allocate four more half-page objects, and make the four remaining
objects point to these.  This will put us up to a total of 12
half-page objects.  16 will cause a collection.  Allocate 2 more, and
put pointers to these in the last 4 objects we allocated.  We look at the
heap to make sure it is in a state consistent with what I've
described.  Finally, we allocate 2 more half-page objects to cause a
collection.  Print the addresses and make sure the result is
isomorphic to the result before.  Expect 6.5 pages allocated at end.

---------------------------------------------------------------------------
test4:
  This is the first test of objects with more than one pointer in them
(using the "direct,", or "bit-mapped" representation of where the
pointers are.)  Use a 16 page heap, allocate some, null some, print,
allocate to cause a collection, print again, and make sure the after
is isomorphic to the before.  Expect 6.5 pages allocated at end.

---------------------------------------------------------------------------
test5:
  First test of multi-page objects.  Use a 16 page heap.  Allocate 2
2-page objects, and make one of them garbage.  Allocate 2 more, and
put pointers to them in the remaining object from the first
allocation.  At this point, half the pages are allocated.  Look at the
heap, allocate again to cause a collection, and look at the heap.
Expect 6 pages allocated at end.

---------------------------------------------------------------------------
test6:
  First test of mixed size objects, including objects that span page
boundaries.  Look at "original allocation" results and make sure that
they look like

Page:    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
object:  |0|1 |2|3 |4|5 |6|7 |

Then we null objects 1, 3, 4, 6, and 7.  Pages 2 and 4 should become
garbage later.

Next we allocate some more, 2 half-page and 2 3/4 page objects, and
put some pointers back and forth between the existing objects,
including pointers from non-root to root objects, and a pointer into
an object interior.  Look at the state of the system.

Allocate again to cause a collection, and make sure the result is
isomorphic to the original.  Expect 6.5 pages allocated at end.

---------------------------------------------------------------------------
test7:
  This program is supposed to test use of the "free_list".
The free list is created when the current allocation page has space
left, but an allocation request comes in for a chunk that requires
multiple pages, and the next page is not free.  In that case, we
search for a block of contiguous pages big enough to satisfy the
current request, and abandon the current allocation page.  If the
current page contains a non-trivial amount of space (where triviality
is defined as less than 5% of a page), then the rest of the page is
pushed on the front of the free list.

Note that the free list must be abandoned at the beginning of garbage
collection, since some of the pages the free blocks reside on may be
freed.  (Alternatively, I could do scan-stacks first, and then retain
only those blocks on promoted pages.)

To test the free list, I first have to set up an instance where it
will be used.  I will use a 16 page heap.  Initially I use 1 page
objects.  I allocate 8 of these, using pages 0 through 7.  Make pages
1, 3, 5, and 7 garbage.  The next allocation will cause a collection.
0, 2, 4, 6 and 8 should be retained.  Allocate 3 more times, and then
destroy the references to pages 8, 9, 10, and 11.  The next allocation
should get page 12, and cause a collection.  3 more pages should be
free which should take us to page 15.  Get rid of the references to
12, 13, 14, and 15.  The next allocation requests a near-page (>95%)
object.  This causes a collection, after which we should have 0, 1, 2,
4, and 6 in the current space, with 1 as the current allocation page.
Another near-page allocation should get us page 3, and put the last bit of
page 1 on the free list.  Another near-page allocation should be
on page 5, and put the last bit of page 3 on the free list.  Another
near-page object will be put on page 7.  At this point, we print out
the heap, and verify that there are three blocks on the free list.
Allocate a 5% page object, make sure we got the expected address (end
of page 5), and print out the heap to verify that there are now 2
blocks on the free list.  Now we test the interaction of the free-list
and GC.  Put the address of the last object we got in a pointer in
the near-page object in page 1, and get rid of the reference to it on
the stack.  This should cause it to be copied.  Also, put a pointer to
the near-page object on page 7 in the page 1 object.  Now get rid of
stack references to all objects except the one on page 1.  Now
allocate a 1/4 page object.  This should not fit on the free list, so
it should cause a collection.  During collection, only the block on
page 1 should be used, and the small page 5 object should be copied
there.  Page 8 should get the page 7 object, and the 1/4 page object
should fill up the end of 8 and the beginning of 9.  The free list
should be null.

---------------------------------------------------------------------------
Test8: Unsure refs found late.

In GC, unions can cause "unsure refs".  If an object containing an
unsure ref is found during GC, the page it "points" to (since it may not
be a pointer) must be promoted instead of copied.

Let a foo be a half-page object containing a sure reference and an
unsure reference.  Allocate 8 of these, make 4 garbage (0, 1, 6, 7).
Allocate 4 more; make objects 0.2 and 0.3 have sure pointers to
1.0 and 1.1.  Make 0.4 have a sure ref to 1.2, and 0.5 an *unsure* ref
to 1.3.  Allocate three more; make 1.0 and 1.1 have sure refs to 2.0 and
2.1, and make 1.2 and 1.3 both have unsure refs to 2.3.  Finally
allocate another to start a collection.

During collection, pages 0, 1 and 2 should be promoted because they were
pointed at by roots, and pages 5 and 7 should be promoted because they
were the targets of unsure refs.  Pages 8 and 9 should be taken up by
new allocation, containing objects 1.0, 1.1, 2.0, and 2.1, and possibly
2.2.  (The order in which the references in 1.4 and 1.5 are found should
influence the GC.  If the unsure ref is found first, object 2.2 will not
be copied, because page 5 will already be promoted when the
reference to 2.2 is encounterd.  Otherwise it will be copied.  Try both
ways to make sure this is true.  It prompts.)



