The new gc_block allocation scheme optimizes virtual memory and
cache behavior.

Previously, each page of the heap had a header, struct gc_block.
The conservative GC tested whether a pointer pointed into the heap by
searching a simple hash table called gc_object_hash.  The new
allocation scheme allows faster conservative object marking by
eliminating gc_object_hash, and reduces cache conflict misses and
paging by placing struct gc_blocks in an array.

Since gc_blocks are not part of the pages they describe further memory
optimizations are possible:  Free pages anywhere in the heap can be
marked as low priority with madvise.  And, free pages can be made
unreadable, as is done when compiled with -DDEBUG.  Madvise is not
currently used, since it seems to have a negligible effect.  

Rather than searching a hash table to find a gc_block structure,
markObject simply needs to subtract the heap base from a pointer, and
use the difference in pages to index the gc_block array.

There are some complications:  The java heap is not really an array of
pages:  Pages allocated by malloc and gc_system_alloc may be interleaved.
There are three ways to deal with this:
1. Allocate the entire heap up front, which needlessly ties up
   resources.
2. Allocate some address space, then fill in the heap and gc_block
   array as needed (using mmap).  On systems which support the
   MAP_NORESERVE flag, mmap can allocate address space without
   allocating backing store.  But, on other systems a strange trick
   would be required:  Call mmap(0) to find out where mmap wants to
   place memory, add an arbitrary constant, and start the heap there.
   This trick is less than reliable.  And, neither approach works on
   systems that don't have mmap.
3. Allocate the full gc_block array up front.  Compensate for holes in
   the heap address range, but be prepared to realloc the gc_block
   array if neeeded.

I have taken the third approach.  Kaffe initially allocates an array
of max-heap-pages * 1.25 gc_block structures using malloc.  If this
array turns out to be too small (because quite a few memory
allocation requests are bypassing gc_malloc), the array is
realloc'ed to a better guess at its maximum size.  Pointers to
gc_blocks (both inside gc_blocks and in variables such as
gc_prim_freelist) are relocated.  

This adds a wrinkle to any work on a concurrent GC:  There can be no
gc_block *'s on any stack when the array is realloced (inside
gc_heap_malloc).

Jason Baker <jbaker@cs.utah.edu>
Jan  6, 1999