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