https://github.com/Unipisa/CMM
Raw File
Tip revision: 0e186db83a043dcfe9c666dd4c90f9e8d1b9234e authored by Giuseppe Attardi on 27 October 1994, 11:26:20 UTC
1.1 -
Tip revision: 0e186db
cmm.C
/* This module implements the POSSO Customisable Memory Management (CMM)
   CMM provides garbage collected storage for C++ programs.

   The technique is described in:

   G. Attardi and T. Flagella ``A customisable memory management
   framework'', Proceedings of USENIX C++ Conference 1994, Cambridge,
   Massachusetts, April 1994.

   The implementation is derived from the code of the "mostly-copying" garbage
   collection algorithm, by Joel Bartlett, of DEC.

*/

/* 
   Copyright (C) 1993 Giuseppe Attardi and Tito Flagella.

   This file is part of the POSSO Customizable Memory Manager (CMM).

   CMM is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   See file 'Copyright' for full details.

*/

/*
 *              Copyright 1990 Digital Equipment Corporation
 *                         All Rights Reserved
 *
 * Permission to use, copy, and modify this software and its documentation is
 * hereby granted only under the following terms and conditions.  Both the
 * above copyright notice and this permission notice must appear in all copies
 * of the software, derivative works or modified versions, and any portions
 * thereof, and both notices must appear in supporting documentation.
 *
 * Users of this software agree to the terms and conditions set forth herein,
 * and hereby grant back to Digital a non-exclusive, unrestricted, royalty-free
 * right and license under any changes, enhancements or extensions made to the
 * core functions of the software, including but not limited to those affording
 * compatibility with other hardware or software environments, but excluding
 * applications which incorporate this software.  Users further agree to use
 * their best efforts to return to Digital any such changes, enhancements or
 * extensions that they make and inform Digital of noteworthy uses of this
 * software.  Correspondence should be provided to Digital at:
 * 
 *                       Director of Licensing
 *                       Western Research Laboratory
 *                       Digital Equipment Corporation
 *                       250 University Avenue
 *                       Palo Alto, California  94301  
 * 
 * This software may be distributed (but not offered for sale or transferred
 * for compensation) to third parties, provided such third parties agree to
 * abide by the terms and conditions of this notice.  
 * 
 * THE SOFTWARE IS PROVIDED "AS IS" AND DIGITAL EQUIPMENT CORP. DISCLAIMS ALL
 * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL DIGITAL EQUIPMENT
 * CORPORATION BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 * SOFTWARE.
 */

#include "machine.H"
#include "cmm.H"
#include <setjmp.h>

/* Version tag */

char*  CmmVersion = "CMM 1.3";

extern "C"  void* sbrk(int);

       /**************************************
	* Garbage Collected Heap Definitions *
	**************************************/

/*
 * The heap consists of a discontiguous set of pages of memory, where each
 * page is BYTESxPAGE long.  N.B.  the page size for garbage collection is
 * independent of the processor's virtual memory page size.
 */

static int  totalPages,		/* # of pages in the heap		*/
	    heapSpanPages,	/* # of pages that span the heap	*/
	    freePages,		/* # of pages not yet allocated		*/
	    freeWords = 0,	/* # words left on the current page	*/
	    *freep,		/* Ptr to the first free word on the current
				   page */
	    freePage,		/* First possible free page		*/
	    *pageLink,		/* Page link for each page		*/
	    queue_head,		/* Head of list of stable set of pages	*/
	    queue_tail;     	/* Tail of list of stable set of pages	*/

int	    firstHeapPage,	/* Page # of first heap page		*/
	    lastHeapPage,	/* Page # of last heap page		*/
	    *ObjectMap;		/* Bitmap of objects			*/
#if !HEADER_SIZE
int	    *LiveMap;		/* Bitmap of live objects		*/
#endif


short *pageSpace;		/* Space number for each page		*/
static short *pageGroup;	/* Size of group of pages		*/

int	    current_space;	/* Current space number			*/
int	    next_space;		/* Next space number			*/

CmmHeap    **pageHeap;		/* Heap to which each page belongs	*/

#ifndef DELETE_TABLES
static int tablePages,		/* # of pages used by tables	*/
firstTablePage;			/* index of first page used by table	*/
#endif

/*
 * Groups of pages used for objects spanning multiple pages, are dealt
 * as follows:
 *
 * The first page p0 in a group contains the number n of pages in the group,
 * each of the following pages contains the offset from the first page:
 * 	pageGroup[p0] = n
 * 	pageGroup[p0+1] = -1
 * 	pageGroup[p0+n-1] = 1-n
 * Given a page p, we can compute the first page by p+pageGroup[p] if
 * pageGroup[p] < 0, otherwise p.
 */   

/*
 Tito:
   A new algorithm for garbage collection is used when MARKING is defined.
   The new algorithm is:
   1) Look at the roots to promote a set of pages whose objects cannot
      be moved. Any reachable object is marked as a reached object setting
      its bit into the "LiveMap" bitmap to 1.
   2) Scan the promoted pages, traversing all the objects marked as reached.
   Traverse applies the scavenge to any pointer internal to the traversed
   objects. scavenge does:
    - if the pointer is outside the heap do nothing;
    - if the pointer is to an object in another heap traverse that object.
    - if the object has already been reached, then if the object is in 
      a promoted page return, else set the pointer to the forward position.
    - if the object has not yet been reached, then if the object is in 
      a promoted page, mark it and apply traverse to it, else copy the object,
      set the old header to the forward position, and set the forward bit of
      the new object to 0.

   Note that any page allocated to copy reachable objects is added to the
   promoted set. For this reason you don't need to apply traverse to
   moved objects. They will be traversed as they are reachable objects in
   promoted pages.

   3) Reset the mark bit for any object in the promoted pages.
 */


       /**********************************
        * Exported Interface Definitions *
	**********************************/

#ifdef CMM_VERBOSE
int CmmVerbosity = 1;		/* controls amount of printout */
#endif

/*
 * An instance of the type gcheap is created to configure the size of the
 * initial heap, the expansion increment, the maximum size of the heap,
 * the allocation percentage to force a total collection, the allocation
 * percentage to force heap expansion, and garbage collection options.
 */

/* Default heap configuration */

const int  GCMINBYTES = 131072,		/* # of bytes of initial heap	*/
	   GCMAXBYTES = 2147483647,	/* # of bytes of the final heap */
	   GCINCBYTES = 1048576,	/* # of bytes of each increment	*/
	   GCFULLGCTHRESHOLD = 35,	/* % allocated to force total
					   collection		       	*/
	   GCINCPERCENT = 25,		/* % allocated to force expansion */
	   GCFLAGS = 0;			/* option flags			*/

/* Actual heap configuration */

static int  gcminbytes = GCMINBYTES,	/* # of bytes of initial heap	*/
	    gcmaxbytes = GCMAXBYTES,	/* # of bytes of the final heap */
	    gcincbytes = GCINCBYTES,	/* # of bytes of each increment */
	    gcFullGcThreshold = GCFULLGCTHRESHOLD,/* % allocated to force
					    total collection		*/
	    gcincpercent = GCINCPERCENT,/* % allocated to force expansion */
	    gcflags = GCFLAGS;		/* option flags			*/
static bool gcdefaults = true,		/* default setting in force	*/
	    gcheapcreated = false;	/* boolean indicating heap created */

gcheap::gcheap(int minheapbytes,
		int maxheapbytes,
		int incheapbytes,
		int FullGcThreshold,
		int incpercent,
		int flags)  {
	if  (!gcheapcreated  &&  minheapbytes > 0  &&
	     (gcdefaults || maxheapbytes >= gcmaxbytes))  {
	   gcdefaults = false;
	   gcminbytes = minheapbytes;
	   gcmaxbytes = maxheapbytes;
	   gcincbytes = incheapbytes;
	   gcFullGcThreshold = FullGcThreshold;
	   gcincpercent = incpercent;
	   gcminbytes = MAX(gcminbytes, 4*BYTESxPAGE);
	   gcmaxbytes = MAX(gcmaxbytes, gcminbytes);
	   if  (gcFullGcThreshold < 0  ||  gcFullGcThreshold > 50)
	      gcFullGcThreshold = GCFULLGCTHRESHOLD;
	   if  (gcincpercent < 0  ||  gcincpercent > 50)
	      gcincpercent = GCINCPERCENT;
	}
	if  (gcheapcreated  &&  minheapbytes > 0  &&
	     (gcdefaults || maxheapbytes >= gcmaxbytes))  {
	   gcdefaults = false;
	   if  (getenv("GCMAXBYTES") == NULL)  gcmaxbytes = maxheapbytes;
	   if  (getenv("GCINCBYTES") == NULL)  gcincbytes = incheapbytes;
	   if  (getenv("GCFULLGCTHRESHOLD") == NULL)
	     gcFullGcThreshold = FullGcThreshold;
	   if  (getenv("GCINCPERCENT") == NULL)  gcincpercent = incpercent;
	   gcminbytes = MAX(gcminbytes, 4*BYTESxPAGE);
	   gcmaxbytes = MAX(gcmaxbytes, gcminbytes);
	   if  (gcFullGcThreshold < 0  ||  gcFullGcThreshold > 50)
	      gcFullGcThreshold = GCFULLGCTHRESHOLD;
	   if  (gcincpercent < 0  ||  gcincpercent > 50)
	      gcincpercent = GCINCPERCENT;
	}
	gcflags = gcflags | flags;
}

/*
 * Freespace objects have a tag of 0.
 * Pad objects for double alignment have a tag of 1.
 * GcObjects have a tag of 2.
 * The header for a one-word double alignment pad is kept in doublepad.
 */

#if HEADER_SIZE
static int  freespace_tag = MAKE_TAG(0);
#ifdef DOUBLE_ALIGN
static int  doublepad = MAKE_HEADER(1, MAKE_TAG(1));
#endif
#endif

#ifdef DOUBLE_ALIGN
#define ONEPAGEOBJ_WORDS (WORDSxPAGE-HEADER_SIZE)
#else
#define ONEPAGEOBJ_WORDS WORDSxPAGE
#endif


/***********************************************************************
  Roots
 ***********************************************************************/

/*
 * The following structure contains the additional roots registered with
 * the garbage collector.  It is allocated from the non-garbage collected
 * heap.
 */

static int  roots_count = 0;
static int  roots_size = 0;
#define	    ROOTS_INC 10
static int  freed_entries = 0;

static struct  roots_struct  {
  unsigned*  addr;	/* Address of the roots */
  int  bytes;		/* Number of bytes in the roots */ 
}  *roots;


/*----------------------------------------------------------------------
 * gcroots --
 *
 * Additional roots are "registered" with the garbage collector by the
 * following procedure.
 *______________________________________________________________________*/

void  gcroots(void* addr, int bytes)
{
  if (freed_entries) {
    for  (int i = 0; i < roots_count; i++) {
      if (roots[i].addr == 0) {
	roots[i].addr = (unsigned*)addr;
	roots[i].bytes = bytes;
	freed_entries--;
      }
    }
  }
  
  if  (roots_count == roots_size)   {
    roots_struct  *np;
    roots_size += ROOTS_INC;
    np = new roots_struct[roots_size];
    for  (int i = 0; i < roots_count; i++)  np[i] = roots[i];
    delete  roots;
    roots = np;
  }
  roots[roots_count].addr = (unsigned*)addr;
  roots[roots_count].bytes = bytes;
  roots_count++;
}

void  gcunroots(void* addr)
{
  int i;
  for  (i = 0; i < roots_count; i++) 
    if (roots[i].addr == addr) {
      roots[i].addr = 0;
      freed_entries++;
      break;
    }
  assert(i < roots_count);
}

	/****************************
	 * Mostly Copying Collector *
	 ****************************/

/*----------------------------------------------------------------------
 * environment_value --
 *
 * Get heap configuration information from the environment.
 *
 * Results: true if the value is provided, value in value.
 *______________________________________________________________________*/

static int  environment_value(char* name, int& value)
{
	 char* valuestring = getenv(name);

	 if (valuestring != NULL)  {
	    value = atoi(valuestring);
	    return  1;
	 }
	 return  0;
}

#if !HEADER_SIZE
/*
 * Go forward until next object, return the size in words.
 */
int GcObject::words()
{

  register int length = 1;
  register int index = WORD_INDEX(this+1);
  int shift = BIT_INDEX(this+1);
  register unsigned int bits = (unsigned int)ObjectMap[index] >> shift;
  register int inner = BITSxWORD - shift;
  int nextPage = GCP_to_PAGE(this);
  nextPage += pageGroup[nextPage];
  int max = ((int)PAGE_to_GCP(nextPage) - (int)this) / (BITSxWORD * BYTESxWORD);

  do {
    do {
      if (bits & 1) return length;
      bits = bits >> 1;
      length++;
    } while (--inner);
    bits = (unsigned int)ObjectMap[++index];
    inner = BITSxWORD;
  } while (max--);
  /* we fall out here when this is last object on page */
  return (GcObject *)PAGE_to_GCP(nextPage) - this;
}

/* Version using ffs.
   Counts the number of consecutive 1's in ObjectMap, which encode
   half the number of words of the object.
   We assume that object are an even number of words.
int words()
{
  int length = 0, bits,
  index = WORD_INDEX(this),
  shift = BIT_INDEX(this);

  while (true) {
    bits = (unsigned int)ObjectMap[index] >> shift;
    inc = ffs(~bits) - 1;
    if (inc < 0) inc = BITSxWORD;
    if (inc == (BITSxWORD - shift)) break;
    length += inc;
    index++;
    shift = 0;
  }
  return 2*length;
}

A setObjectMap which goes with this is:

setObjectMap(GCP p, int size)
{
  int index = WORD_INDEX(p),
  shift = BIT_INDEX(p);
  size = size / 2;
  while (true) {
    count = size % (BITSxWORD - shift);
    ObjectMap[index] |= (1 << count) - 1;
    size -= count;
    if (size == 0) break;
    index++;
    shift = 0;
  }
}
*/
#endif

/***********************************************************************
  Initialization
 ***********************************************************************/

#if !HEADER_SIZE
/*
 * An object of this class is used to fill free portion of page.
 */
class GcFreeObject: public GcObject {
  void traverse() {}
  int words() { return WORDSxPAGE; }
};

static GcFreeObject *aGcFreeObject;

#ifdef DOUBLE_ALIGN_OPTIMIZE
/*
 * An object of this class is used for padding.
 */
class GcPadObject: public GcObject {
  void traverse() {}
  int words() { return 1; }
};

static GcPadObject *aGcPadObject;
#endif
#endif

DefaultHeap *CmmHeap::theDefaultHeap = NULL;
CmmHeap *CmmHeap::heap = NULL;

// used during initialization of objects:
static GcObject *aGcObject;
static GcVarObject *aGcVarObject;

static unsigned  stackBottom;	// The base of the stack
static unsigned *globalHeapStart; // start of global heap

CmmInitEarly() {
  int i;
  if  (stackBottom == 0) {

#define STACKBOTTOM_ALIGNMENT_M1 0xffffff
#ifdef STACK_GROWS_DOWNWARD
    stackBottom = ((unsigned)&i + STACKBOTTOM_ALIGNMENT_M1)
      & ~STACKBOTTOM_ALIGNMENT_M1;
#else
    stackBottom = (unsigned)&i & ~STACKBOTTOM_ALIGNMENT_M1;
#endif

    /* Determine start of system heap				*/
    globalHeapStart = (unsigned *)sbrk(0);
  }
}

// #define CMM_DEBUG
#ifdef CMM_DEBUG
#include "utils.C"
#endif

/*----------------------------------------------------------------------
 * CmmInit --
 *
 * The heap is allocated and the appropriate data structures are initialized
 * by the following function.  It is called the first time any storage is
 * allocated from the heap.
 *______________________________________________________________________*/

static void  CmmInit()
{
  char  *heap;
  int  i;
  
  /* Log actual heap parameters if from environment or logging */
  if  ((environment_value("GCMINBYTES", gcminbytes) |
	environment_value("GCMAXBYTES", gcmaxbytes) |
	environment_value("GCINCBYTES", gcincbytes) |
	environment_value("GCFULLGCTHRESHOLD", gcFullGcThreshold) |
	environment_value("GCINCPERCENT", gcincpercent) |
	environment_value("GCFLAGS", gcflags))  ||
       gcflags & GCSTATS)  {
    fprintf(stderr,
	    "***** gcalloc  gcheap(%d, %d, %d, %d, %d, %d)\n",
	    gcminbytes, gcmaxbytes, gcincbytes, gcFullGcThreshold,
	    gcincpercent, gcflags);
  }
  
  /* Allocate heap and side tables.  Exit on allocation failure. */
#ifdef DELETE_TABLES
  heapSpanPages = totalPages = gcminbytes/BYTESxPAGE;
  if  ((heap = new char[totalPages*BYTESxPAGE + BYTESxPAGE - 1]) == NULL ||
       (pageSpace = new short[heapSpanPages]) == NULL  ||
       (pageLink = new int[heapSpanPages]) == NULL  ||
       (pageGroup = new short[heapSpanPages]) == NULL  ||
       (pageHeap = new CmmHeap*[heapSpanPages]) == NULL  ||
       (ObjectMap = new int[heapSpanPages*WORDSxPAGE/BITSxWORD]) == NULL
#if !HEADER_SIZE
       || (LiveMap = new int[heapSpanPages*WORDSxPAGE/BITSxWORD]) == NULL
#endif
       ) {
    fprintf(stderr, 
	    "\n****** gcalloc  Unable to allocate %d byte heap\n",
	    gcminbytes);
    abort();
  }
  if ((unsigned)heap & (BYTESxPAGE - 1))
    heap = heap + (BYTESxPAGE - ((unsigned)heap & (BYTESxPAGE - 1)));
  firstHeapPage = GCP_to_PAGE(heap);
  lastHeapPage = firstHeapPage + heapSpanPages - 1;
  freePages = totalPages;

#else

  heapSpanPages = totalPages = (gcminbytes + BYTESxPAGE - 1)/BYTESxPAGE;
  tablePages = (totalPages*sizeof(int)*2 /* pageLink, pageHeap */
		+ totalPages*sizeof(short)*2 /* pageSpace, pageGroup */
		+ totalPages*WORDSxPAGE/BITSxWORD*sizeof(int) /* ObjectMap */
#if !HEADER_SIZE
		+ totalPages*WORDSxPAGE/BITSxWORD*sizeof(int) /* LiveMap */
#endif
		+ BYTESxPAGE - 1) / BYTESxPAGE;
  /* Allocate one block for both the heap and the tables.
   * The tables will be recycled into pages at the next collection.
   */
  if  ((heap = new char[(totalPages + tablePages)*BYTESxPAGE + BYTESxPAGE - 1])
       == NULL) {
    fprintf(stderr, 
	    "\n****** CMM  Unable to allocate %d byte heap\n", gcminbytes);
    abort();
  }
  heap = heap + BYTESxPAGE - 1;
  heap -= (int)heap % BYTESxPAGE;
  firstHeapPage = GCP_to_PAGE(heap);
  lastHeapPage = firstHeapPage + heapSpanPages - 1;
  firstTablePage = lastHeapPage + 1;
  freePages = totalPages;

  pageSpace = (short *)PAGE_to_GCP(firstTablePage);
  pageGroup = &pageSpace[totalPages];
  pageLink = (int *)&pageGroup[totalPages];
  pageHeap = (CmmHeap **)&pageLink[totalPages];
  ObjectMap = (int *)&pageHeap[totalPages];
#if !HEADER_SIZE
  LiveMap = (int *)&ObjectMap[totalPages*WORDSxPAGE/BITSxWORD];
#endif

#endif DELETE_TABLES

  /* The following definitions are safe because these vectors are accessed
     only through an address within a page. Instead of using
     pageSpace[addr - firstHeapPage]
     space is displaced by firstHeapPage so that we can use:
     pageSpace[addr]
     */

  pageSpace = pageSpace - firstHeapPage;
  pageLink = pageLink - firstHeapPage;
  pageGroup  = pageGroup  - firstHeapPage;
  pageHeap  = pageHeap  - firstHeapPage;
  ObjectMap = ObjectMap - WORD_INDEX(firstHeapPage*BYTESxPAGE);
#if !HEADER_SIZE
  LiveMap = LiveMap - WORD_INDEX(firstHeapPage*BYTESxPAGE);
#endif

  /* Initialize tables */
  for (i = firstHeapPage ; i <= lastHeapPage ; i++) {
    pageHeap[i] = NOHEAP;
//    pageSpace[i] = UNALLOCATEDSPACE;
  }
  current_space = 3;		// leave 1 as UNALLOCATEDSPACE
  next_space = 3;
  freePage = firstHeapPage;
  queue_head = 0;
  gcheapcreated = true;

  CmmHeap::theDefaultHeap->usedPages = 0;
  CmmHeap::theDefaultHeap->reservedPages = 0;
  CmmHeap::theDefaultHeap->stablePages = 0;
  CmmHeap::theDefaultHeap->firstUnusedPage =
    CmmHeap::theDefaultHeap->firstReservedPage =
      CmmHeap::theDefaultHeap->lastReservedPage = firstHeapPage;

#if !HEADER_SIZE
  aGcFreeObject = ::new GcFreeObject;
#ifdef DOUBLE_ALIGN_OPTIMIZE
  aGcPadObject = ::new GcPadObject;
#endif
#endif

  // The following initializations are needed by the GcObject::new 
  // operator. For this reason they don't use new, but ::new.
  aGcObject = ::new GcObject;
  aGcVarObject = ::new GcVarObject;
}

/*----------------------------------------------------------------------
 * shouldExpandHeap --
 *
 * Once the heap has been allocated, it is automatically expanded after garbage
 * collection until the maximum size is reached.  If space cannot be allocated
 * to expand the heap, then the heap will be left it's current size and no
 * further expansions will be attempted.
 *
 * Results: true when the heap should be expanded.
 *______________________________________________________________________*/

static int  shouldExpandHeap()
{
  return  (HEAPPERCENT(CmmHeap::theDefaultHeap->stablePages) >= gcincpercent
	   && totalPages < gcmaxbytes/BYTESxPAGE  &&  gcincbytes != 0);
}

static void  (*save_new_handler)();

static void  dummy_new_handler() { set_new_handler(save_new_handler); }

static  expandfailed = 0;

/*----------------------------------------------------------------------
 * expandHeap --
 *
 * Expands the heap by gcincbytes.
 *
 * Results: number of first new page allocated, 0 on failure
 *______________________________________________________________________*/

static int  expandHeap()
{
  int  inc_totalPages = gcincbytes/BYTESxPAGE,
  new_firstHeapPage = firstHeapPage,
  inc_firstHeapPage,
  new_lastHeapPage = lastHeapPage,
  inc_lastHeapPage,
  new_totalPages,
  *new_pageLink = NULL,
  *new_ObjectMap = NULL,
#if !HEADER_SIZE
  *new_LiveMap = NULL,
#endif
  i;

  short *new_pageSpace = NULL;
  short *new_pageGroup = NULL;
  CmmHeap **new_pageHeap = NULL;

#ifndef DELETE_TABLES
  char  *new_tables;
  int   new_tablePages;
#endif

  char*  inc_heap;

  /* Check for previous expansion failure */
  if  (expandfailed)  return  0;

  /* Allocate additional heap and determine page span */
  save_new_handler = set_new_handler(dummy_new_handler);
#ifdef DELETE_TABLES
  inc_heap = new char[inc_totalPages*BYTESxPAGE + BYTESxPAGE - 1];
  if  (inc_heap == NULL)  goto fail;
  if ((unsigned)inc_heap & (BYTESxPAGE - 1))
    inc_heap = inc_heap +
      (BYTESxPAGE - ((unsigned)inc_heap & (BYTESxPAGE - 1)));
  inc_firstHeapPage = GCP_to_PAGE(inc_heap);
  inc_lastHeapPage = inc_firstHeapPage + inc_totalPages - 1;
  if  (inc_firstHeapPage < firstHeapPage)
    new_firstHeapPage = inc_firstHeapPage;
  if  (inc_lastHeapPage > lastHeapPage)
    new_lastHeapPage = inc_lastHeapPage;
  new_totalPages = totalPages + inc_totalPages;
  heapSpanPages = new_lastHeapPage - new_firstHeapPage + 1;
  
  /* Allocate contiguous space for each side table, recover gracefully
     from allocation failure.  */
  if  ((new_pageSpace = new short[heapSpanPages]) == NULL  ||
       (new_pageLink = new int[heapSpanPages]) == NULL  ||
       (new_pageGroup = new short[heapSpanPages]) == NULL  ||
       (new_pageHeap = new CmmHeap*[heapSpanPages]) == NULL  ||
       (new_ObjectMap = new int[heapSpanPages*WORDSxPAGE/BITSxWORD]) == NULL
#if !HEADER_SIZE
       ||  (new_LiveMap = new int[heapSpanPages*WORDSxPAGE/BITSxWORD]) == NULL
#endif
       ) {
  fail:	   set_new_handler(save_new_handler);
    if  (inc_heap)  delete inc_heap;
    if  (new_pageSpace)  delete new_pageSpace;
    if  (new_pageLink)  delete new_pageLink;
    if  (new_pageGroup)  delete new_pageGroup;
    if  (new_pageHeap)  delete new_pageHeap;
    if  (new_ObjectMap)  delete new_ObjectMap;
#if !HEADER_SIZE
    if  (new_LiveMap)  delete new_LiveMap;
#endif
    expandfailed = 1;
    WHEN_FLAGS (GCSTATS,
		fprintf(stderr,
			"\n***** gcalloc  Heap expansion failed\n"));
    return  0;
  }
  set_new_handler(save_new_handler);
  new_pageSpace = new_pageSpace - new_firstHeapPage;
  new_pageLink = new_pageLink - new_firstHeapPage;
  new_pageGroup = new_pageGroup - new_firstHeapPage;
  new_pageHeap = new_pageHeap - new_firstHeapPage;
  new_ObjectMap = new_ObjectMap - WORD_INDEX(new_firstHeapPage*BYTESxPAGE);
#if !HEADER_SIZE
  new_LiveMap = new_LiveMap - WORD_INDEX(new_firstHeapPage*BYTESxPAGE);
#endif

  /* Initialize gaps in between blocks of pages */
  for (i = inc_lastHeapPage + 1 ; i <= firstHeapPage ; i++)
    new_pageHeap[i] = UNCOLLECTEDHEAP;
  for (i = lastHeapPage + 1 ; i < inc_firstHeapPage ; i++)
    new_pageHeap[i] = UNCOLLECTEDHEAP;

#else				// !DELETE_PAGES

  inc_heap = new char[inc_totalPages*BYTESxPAGE + BYTESxPAGE - 1];
  if (inc_heap == NULL) goto fail;
  inc_heap = inc_heap + BYTESxPAGE - 1;
  inc_heap -= (int)inc_heap % BYTESxPAGE;
  inc_firstHeapPage = GCP_to_PAGE(inc_heap);
  inc_lastHeapPage = inc_firstHeapPage + inc_totalPages - 1;
  new_firstHeapPage = MIN(firstHeapPage,
			  MIN(firstTablePage, inc_firstHeapPage));
  new_lastHeapPage = MAX(lastHeapPage,
			 MAX(firstTablePage + tablePages - 1,
			     inc_lastHeapPage));
  new_totalPages = totalPages + tablePages + inc_totalPages;
  heapSpanPages = new_lastHeapPage - new_firstHeapPage + 1;

  new_tablePages = (heapSpanPages*sizeof(int)*2 /* pageLink, pageHeap */
		    + heapSpanPages*sizeof(short)*2 /* pageSpace, pageGroup */
		    + heapSpanPages*WORDSxPAGE/BITSxWORD*sizeof(int) /* ObjectMap */
#if !HEADER_SIZE
		    + heapSpanPages*WORDSxPAGE/BITSxWORD*sizeof(int) /* LiveMap */
#endif
		    + BYTESxPAGE - 1) / BYTESxPAGE;
  if ((new_tables = new char[new_tablePages*BYTESxPAGE + BYTESxPAGE - 1])
      == NULL) {
  fail: set_new_handler(save_new_handler);
    if  (inc_heap)  delete inc_heap;
    expandfailed = 1;
    WHEN_FLAGS (GCSTATS,
		fprintf(stderr, "\n***** CMM  Heap expansion failed\n"));
    return  0;
  }
  set_new_handler(save_new_handler);
  new_pageSpace = (short *)new_tables;
  new_pageGroup = &new_pageSpace[heapSpanPages];
  new_pageLink = (int *)&new_pageGroup[heapSpanPages];
  new_pageHeap = (CmmHeap **)&new_pageLink[heapSpanPages];
  new_ObjectMap = (int *)&new_pageHeap[heapSpanPages];
#if !HEADER_SIZE
  new_LiveMap = (int *)&new_ObjectMap[heapSpanPages*WORDSxPAGE/BITSxWORD];
#endif

  new_pageSpace = new_pageSpace - new_firstHeapPage;
  new_pageLink = new_pageLink - new_firstHeapPage;
  new_pageGroup = new_pageGroup - new_firstHeapPage;
  new_pageHeap = new_pageHeap - new_firstHeapPage;
  new_ObjectMap = new_ObjectMap - WORD_INDEX(new_firstHeapPage*BYTESxPAGE);
#if !HEADER_SIZE
  new_LiveMap = new_LiveMap - WORD_INDEX(new_firstHeapPage*BYTESxPAGE);
#endif

  /* Recycle old tables */
  int lastTablePage = firstTablePage + tablePages - 1;
  for (i = firstTablePage; i <= lastTablePage; i++)
    new_pageHeap[i] = NOHEAP;
  /* Fill gaps */
  int gapStart = MIN(lastTablePage, inc_lastHeapPage);
  int gap1Start = MIN(lastHeapPage, gapStart);

  int gapEnd = MAX(firstTablePage, inc_firstHeapPage);
  int gap2End = MAX(firstHeapPage, gapEnd);

  int gap1End = (gapEnd == gap2End) ?
    MAX(firstHeapPage, MIN(firstTablePage, inc_firstHeapPage)) : gapEnd;
  int gap2Start = (gapStart == gap1Start) ?
    MIN(lastHeapPage, MAX(lastTablePage, inc_lastHeapPage)) : gapStart;
  for (i = gap1Start + 1; i < gap1End; i++)
    new_pageHeap[i] = UNCOLLECTEDHEAP;
  for (i = gap2Start + 1; i < gap2End; i++)
    new_pageHeap[i] = UNCOLLECTEDHEAP;
#endif DELETE_TABLES

  /* Initialize new side tables */
  for (i = inc_firstHeapPage ; i <= inc_lastHeapPage ; i++)
    new_pageHeap[i] = NOHEAP;
  for (i = firstHeapPage ; i <= lastHeapPage ; i++) {
    new_pageSpace[i] = pageSpace[i];
    new_pageHeap[i] = pageHeap[i];
    new_pageLink[i] = pageLink[i];
    new_pageGroup[i] = pageGroup[i];
  }
  for  (i = WORD_INDEX(firstHeapPage*BYTESxPAGE);
	i < WORD_INDEX((lastHeapPage + 1)*BYTESxPAGE); i++) {
    new_ObjectMap[i] = ObjectMap[i];
#if !HEADER_SIZE
    // necessary if expandHeap() is called during collection
    new_LiveMap[i] = LiveMap[i];
#endif
  }

#ifdef DELETE_TABLES
  delete (pageSpace + firstHeapPage);
  delete (pageLink + firstHeapPage);
  delete (pageGroup + firstHeapPage);
  delete (pageHeap + firstHeapPage);
  delete (ObjectMap + WORD_INDEX(firstHeapPage*BYTESxPAGE));
#if !HEADER_SIZE
  delete (LiveMap + WORD_INDEX(firstHeapPage*BYTESxPAGE));
#endif
#endif
  pageSpace = new_pageSpace;
  pageLink = new_pageLink;
  pageGroup = new_pageGroup;
  pageHeap = new_pageHeap;
  ObjectMap = new_ObjectMap;
#if !HEADER_SIZE
  LiveMap = new_LiveMap;
#endif
  firstHeapPage = new_firstHeapPage;
  lastHeapPage = new_lastHeapPage;
  totalPages = new_totalPages;
#ifdef DELETE_TABLES
  freePages += inc_totalPages;
#else
  freePages += inc_totalPages + tablePages;
  tablePages = new_tablePages;
  firstTablePage = GCP_to_PAGE(new_tables);
#endif
  freePage = inc_firstHeapPage;
#ifdef CMM_DEBUG
  showHeapPages();
#else
#ifdef CMM_VERBOSE
  printf("Heap pages: %d\n", totalPages);
#endif
#endif
  WHEN_FLAGS (GCSTATS,
	      fprintf(stderr,
		      "\n***** gcalloc  Heap expanded to %d bytes\n",
		      totalPages*BYTESxPAGE));
  return  inc_firstHeapPage;
}

/*----------------------------------------------------------------------
 * empty_stableset --
 *
 * Moves the stable set back into the current_space.
 * A total collection is performed by calling this before calling
 * collect().  When generational collection is not desired, this is called
 * after collection to empty the stable set.
 *______________________________________________________________________*/

static void  empty_stableset()
{
  CmmHeap::theDefaultHeap->stablePages = 0;
  while  (queue_head)  {
    int i = queue_head;
    int pages = pageGroup[i];
    while (pages--)
      pageSpace[i++] = current_space;
    queue_head = pageLink[queue_head];
  }
}

/*----------------------------------------------------------------------
 * queue --
 *
 * Adds a page to the stable set page queue.
 *______________________________________________________________________*/

static void  queue(int page)
{
  if  (queue_head != 0)
    pageLink[queue_tail] = page;
  else 
    queue_head = page;
  pageLink[page] = 0;
  queue_tail = page;
}

/*----------------------------------------------------------------------
 * promote_page --
 *
 * Pages that have might have references in the stack or the registers are
 * promoted to the stable set.
 *
 * Note that objects that get allocated in a CONTINUED page (after a large
 * object) will never move.
 *______________________________________________________________________*/

static void  promote_page(GCP cp)
{
  int page = GCP_to_PAGE(cp);
  
  // Don't promote pages belonging to other heaps.
  
  if  (page >= firstHeapPage  &&  page <= lastHeapPage
       && pageHeap[page] == CmmHeap::theDefaultHeap
       && pageSpace[page] == current_space) {
    
#ifdef MARKING
    MARK(basePointer(cp));
    // given the basePointer we could avoid computing pagecount
#endif
    
    int pages = pageGroup[page];
    if (pages < 0) { page += pages; pages = pageGroup[page]; }

    WHEN_FLAGS (GCDEBUGLOG,
		fprintf(stderr, "promoted 0x%x\n", PAGE_to_GCP(page)));
    queue(page);
    CmmHeap::theDefaultHeap->usedPages += pages; // in next_space
    CmmHeap::theDefaultHeap->stablePages += pages;
    while (pages--)
      pageSpace[page++] = next_space;
  }
}

/*----------------------------------------------------------------------
 * basePointer --
 *
 * Results: pointer to the beginning of the containing object
 *______________________________________________________________________*/ 

GcObject *basePointer(GCP fp)
{
  fp = (GCP) ((int)fp & ~(BYTESxWORD-1));
/*
  while (! IS_OBJECT(fp))
    fp--;
  return (GcObject *)fp;  
*/
  register int index = WORD_INDEX(fp);
  register int inner = BIT_INDEX(fp);
  register int mask = 1 << inner;
  register unsigned int bits = (unsigned int)ObjectMap[index];

  do {
    do {
      if (bits & mask) return (GcObject *)fp;
      mask = mask >> 1;
      fp--;
    } while (inner--);
    bits = (unsigned int)ObjectMap[--index];
    inner = BITSxWORD-1;
    mask = 1 << BITSxWORD-1;
  } while (true);
}

/*----------------------------------------------------------------------
 * CmmHeap::scavenge --
 *
 * Replaces pointer to (within) object with pointer to scavenged object
 *
 * Results: none
 *
 * Side effects: freep, freeWords, usedPages
 *______________________________________________________________________*/

void DefaultHeap::scavenge(GcObject **ptr) {

  if (inside((GCP)*ptr)) {

    GcObject *p = basePointer((GCP)*ptr);

    if (inside((GCP)p))
      *ptr = (GcObject *)((int)CmmMove((GCP)p) + (int)*ptr - (int)p);
#ifdef MARKING
    else
      // Here you can decide to traverse or not objects in other heaps.
      // If not, simply return. Here we traverse.
      visit(p);
#endif
    }
}

/*----------------------------------------------------------------------
 * CmmMove --
 *
 * Copies object from current_space to next_space
 *
 * Results: pointer to header of copied object
 *
 * Side effects: freep, freeWords, usedPages
 *______________________________________________________________________*/

GCP CmmMove(GCP cp)
{
  int  page = GCP_to_PAGE(cp);	/* Page number */
  GCP  np;			/* Pointer to the new object */
#if HEADER_SIZE
  int  header;			/* Object header */
#endif

  /* Verify that the object is a valid pointer and decrement ptr cnt */
  WHEN_FLAGS (GCTSTOBJ, verify_object(cp, 1));

  if  (STABLE(page))
#ifdef MARKING
    {
      if (MARKED(cp))
	return(cp);
      else {
	MARK(cp);
	if (HEADER_TAG(*(cp - HEADER_SIZE)) > 1)
	  ((GcObject *)cp)->traverse();
	return(cp);
      }
    }
#else
  return(cp);
#endif
  /* If cell is already forwarded, return forwarding pointer */
#if HEADER_SIZE
  header = cp[-HEADER_SIZE];
  if  (FORWARDED(header)) {
    WHEN_FLAGS (GCTSTOBJ, {
      verify_object((GCP)header, 0);
      verify_header((GCP)header);
    });
    return ((GCP)header);
  }
#else
  if  (FORWARDED(cp))
    return ((GCP)*cp);
#endif

  /* Move the object */
  WHEN_FLAGS (GCTSTOBJ, verify_header(cp));

  /* Forward or promote object */
#if HEADER_SIZE
  register int  words = HEADER_WORDS(header);
#else
  register int  words = ((GcObject *)cp)->words();
#endif
  if  (words >= freeWords)  {
    /* Promote objects >= a page to stable set */
    /* This is to avoid expandHeap(). See note about collect().
     * We could perform copying during a full GC by reserving in advance
     * a block of pages for objects >= 1 page
     */
    if  (words >= ONEPAGEOBJ_WORDS)  {
      promote_page(cp);
      /* tito: you don't need to traverse it now.
       * Object will be traversed, when the promoted page will be swept.
       */
      return(cp);
    }
    /* Discard any partial page and allocate a new one */
    // We must ensure that this does not invoke expandHeap()
    CmmHeap::theDefaultHeap->reserve_pages(1);
    WHEN_FLAGS (GCDEBUGLOG, fprintf(stderr, "queued   0x%x\n", freep));
    queue(GCP_to_PAGE(freep));
    CmmHeap::theDefaultHeap->stablePages += 1;
  }
  /* Forward object, leave forwarding pointer in old object header */
#if HEADER_SIZE
  *freep++ = header;
#else
  GCP ocp = cp;
#endif
  np = freep;
  SET_OBJECTMAP(np);
  freeWords = freeWords - words;
#if HEADER_SIZE
  cp[-HEADER_SIZE] = (int)np;	// lowest bit 0 means forwarded
  words -= HEADER_SIZE;
  while  (words--)  *freep++ = *cp++;
#ifdef DOUBLE_ALIGN
  if  ((freeWords & 1) == 0  &&  freeWords)  {
    *freep++ = doublepad;
    freeWords = freeWords - 1;
  }
#endif
#else
  MARK(cp); // Necessary to recognise as forwarded */
  while  (words--)  *freep++ = *cp++;
  *ocp = (int)np;
#endif
#ifdef MARKING
  MARK(np);
  /* tito: no need to traverse it now.
     Object will be traversed, when the promoted page will be swept.
     */
#endif
  return(np);
}

/*----------------------------------------------------------------------
 * DefaultHeap::collect --
 *
 * Garbage collection for the DefaultHeap. It is typically
 * called when half the pages in the heap have been allocated.
 * It may also be directly called.
 * 
 * WARNING: (freePages + reserveedPages - usedPages) must be > usedPages when
 * collect() is called to avoid the invocation of expandHeap() in the
 * middle of collection.
 *______________________________________________________________________*/

void DefaultHeap::collect()
{
  int  page;			/* Page number while walking page list */
  GCP  cp,			/* Pointers to move constituent objects */
  nextcp;	
//  static doFullGC = false;
    
  /* Check for heap not yet allocated */
  if  (!gcheapcreated)  {
    CmmInit();
    return;
  }
#ifdef CMM_DEBUG
  printf(">"); showHeapPages();
#endif
  
  /* Log entry to the collector */
  WHEN_FLAGS (GCSTATS, {
    fprintf(stderr, "***** gcalloc  Collecting - %d%% allocated  ->  ",
	    HEAPPERCENT(usedPages));
    newline_if_logging();
  });
  
  /* Allocate rest of the current page */
  if (freeWords != 0)  {
#if HEADER_SIZE
    *freep = MAKE_HEADER(freeWords, freespace_tag);
#else
    *freep = *(GCP)aGcFreeObject;
    SET_OBJECTMAP(freep);
#endif
    freeWords = 0;
  }
  
//  if (freePages + reservedPages < 2 * usedPages)
//    expandHeap();

  //  if (doFullGC) empty_stableset();

  /* Advance space.
   * Pages allocated by CmmMove() herein will belong to the stable set.
   * At the end of collect() we go back to normal.
   * Therefore objects moved once by the collector will not be moved again
   * until a full collection is enabled by empty_stableset().
   */

  next_space = current_space + 1;
  usedPages = stablePages;	// start counting in next_space

#if !HEADER_SIZE
  /* Clear the LiveMap bitmap */
  bzero((char*)&LiveMap[WORD_INDEX(firstHeapPage * BYTESxPAGE)],
	heapSpanPages * (BYTESxPAGE / BITSxWORD));
#endif
  /* Examine stack, registers, static area and possibly the non-garbage
     collected heap for possible pointers */
  WHEN_FLAGS (GCROOTLOG, fprintf(stderr, "stack roots:\n"));
  {
    jmp_buf regs;
    unsigned *fp;		/* Pointer for checking the stack */
#ifdef STACK_GROWS_DOWNWARD
    register unsigned *lim = (unsigned *)regs;
#else
    register unsigned *lim = (unsigned *)regs + sizeof(regs);
#endif
    extern int end;

    /* ensure flushing of register caches */
    if (_setjmp(regs) == 0) _longjmp(regs, 1);

#ifdef STACK_GROWS_DOWNWARD
    for (fp = lim; fp < (unsigned *)stackBottom; fp++) {
      WHEN_FLAGS (GCROOTLOG, log_root(fp));
      promote_page((GCP)*fp);
    }
#else
    for (fp = lim; fp > (unsigned *)stackBottom; fp--) {
      WHEN_FLAGS (GCROOTLOG, log_root(fp));
      promote_page((GCP)*fp);
    }
#endif
    
    WHEN_FLAGS (GCROOTLOG,
		fprintf(stderr, "static and register roots:\n"));
    for  (fp = DATASTART ; fp < (unsigned *)&end ; fp++)  {
      if (fp == (unsigned *)&freep) continue;
      // Maybe: *fp == freep or better
      // (*fp >= freep && *fp < PAGE_to_GCP(GCP_to_PAGE(freep) + 1))
      WHEN_FLAGS (GCROOTLOG, log_root(fp));
      promote_page((GCP)*fp);
    }
    for  (int i = 0; i < roots_count; i++)  {
      fp = roots[i].addr;
      for  (int j = roots[i].bytes; j > 0; j = j - BYTESxWORD)
	promote_page((GCP)*fp++);
    }
    if  (gcflags & GCHEAPROOTS)  {
      WHEN_FLAGS (GCHEAPLOG,
		  fprintf(stderr, "Uncollected heap roots:\n"));
      unsigned *globalHeapEnd = (unsigned *)sbrk(0);
      fp = globalHeapStart;
      while  (fp < globalHeapEnd)  {
	if  (!inside((GCP)fp))  {
	  WHEN_FLAGS (GCHEAPLOG, log_root(fp));
	  if  (gcflags & GCHEAPROOTS)
	    promote_page((GCP)*fp);
	  fp++;
	}
	else
	  fp = fp + WORDSxPAGE;	// skip page
      }
    }
  }
  WHEN_FLAGS (GCSTATS, {
    fprintf(stderr, "%d%% locked  ", HEAPPERCENT(usedPages));
    newline_if_logging();
  });
  
  /* Sweep across stable pages and move their constituent items.	 */
  page = queue_head;
  while  (page)  {
    cp = PAGE_to_GCP(page);
    WHEN_FLAGS (GCDEBUGLOG, fprintf(stderr, "sweeping 0x%x\n", cp));
    GCP nextPage = PAGE_to_GCP(page + 1);
    bool inCurrentPage = (page == GCP_to_PAGE(freep));
    nextcp = inCurrentPage ? freep : nextPage;
    /* current page may get filled while we sweep it */
    while (cp < nextcp ||
	   inCurrentPage && cp < (nextcp = (cp <= freep && freep < nextPage) ?
				  freep : nextPage)) {
      WHEN_FLAGS (GCTSTOBJ, verify_header(cp + HEADER_SIZE));
#if HEADER_SIZE
      if ((HEADER_TAG(*cp) > 1)
#ifdef MARKING
	  || MARKED(cp + HEADER_SIZE)
#endif
	  )
	((GcObject *)(cp + HEADER_SIZE))->traverse();
      cp = cp + HEADER_WORDS(*cp);
#else
      ((GcObject *)cp)->traverse();
      cp = cp + ((GcObject *)cp)->words();
#endif
    }
    page = pageLink[page];
  }
  
  /* Finished, all retained pages are now part of the stable set */
  current_space = current_space + 2;
  next_space = current_space;
  WHEN_FLAGS (GCSTATS,
	      fprintf(stderr, "%d%% stable.\n", HEAPPERCENT(stablePages)));
  
  /* Check for total collection and heap expansion.  */
  if  (gcFullGcThreshold)  {
    /* Performing generational collection */
    /*    if (doFullGC) {
	  doFullGC = false;
	  if  (shouldExpandHeap())  expandHeap();
	  }
	  else */
    if  (HEAPPERCENT(usedPages) >= gcFullGcThreshold)  {
      /* Perform a total collection and then expand the heap */
      //      doFullGC = true;
      empty_stableset();
      int  save_gcFullGcThreshold = gcFullGcThreshold;
      gcFullGcThreshold = 100;
      cp = NULL;		// or collect will promote it again
      collect();
      if  (shouldExpandHeap())  expandHeap();
      gcFullGcThreshold = save_gcFullGcThreshold;
    }
  }
  else  {
    /* Not performing generational collection */
    if  (shouldExpandHeap())  expandHeap();
    empty_stableset();
  }
#ifdef CMM_DEBUG
  printf("<"); showHeapPages();
#endif
}

/*----------------------------------------------------------------------
 * next_page --
 *
 * Results: index of next page (wrapped at the end)
 *______________________________________________________________________*/

static inline int  next_page(int page)
{
  return  (page == lastHeapPage) ? firstHeapPage : page + 1;
}

/*----------------------------------------------------------------------
 * allocate_page --
 *
 * Page allocator.
 * Allocates a number of additional pages to the indicated heap.
 *
 * Results: address of first page
 *
 * Side effects: freePage
 *______________________________________________________________________*/

GCP  allocate_page(int pages, CmmHeap *heap)
{
  int  free,		/* # contiguous free pages */
  firstPage,	/* Page # of first free page */
  allPages; /* # of pages in the heap */
  GCP  firstByte;	/* address of first free page */
  
  allPages = heapSpanPages;
  free = 0;
  firstPage = freePage;
  while  (allPages--)  {
    if  (pageHeap[freePage] == NOHEAP)  {
      if  (++free == pages)  goto FOUND;
    } else
      free = 0;
    freePage = next_page(freePage);
    if  (freePage == firstHeapPage)  free = 0;
    if (free == 0) firstPage = freePage;
  }
  /* Failed to allocate space, try expanding the heap.  Assure
     that minimum increment size is at least the size of this object.
     */
  if  (!gcheapcreated)  CmmInit(); /* initialize heap, if not done yet */
  gcincbytes = MAX(gcincbytes, pages*BYTESxPAGE);
  if  ((firstPage = expandHeap()) == 0)  {
    /* Can't do it */
    fprintf(stderr,
	    "\n***** allocate_page  Unable to allocate %d pages\n", pages);
    abort();
  }
 FOUND:
  // Ok, I found all needed contiguous pages.
  freePages -= pages;
  firstByte = PAGE_to_GCP(firstPage);
  int i = 1;
  while (pages--) {
    pageHeap[firstPage+pages] = heap;
#if !HEADER_SIZE
    // Fake groups so that words() works also outside the DefaultHeap;
    pageGroup[firstPage+pages] = i++;
#endif
  }
  return firstByte;
}

/*----------------------------------------------------------------------
 * DefaultHeap::reserve_pages --
 *
 * When alloc() is unable to allocate storage, it calls this routine to
 * allocate one or more pages.  If space is not available then the garbage
 * collector is called and/or the heap is expanded.
 *
 * Results: address of first page
 *
 * Side effects: freePage, freep, freeWords, usedPages
 *______________________________________________________________________*/

GCP  DefaultHeap::reserve_pages(int pages)
{
  int firstPage;		/* Page # of first free page	*/
  int i;
  
  /* Garbage collect if not enough pages will be left for collection.	*/
  if  (current_space == next_space && /* not within CmmMove()  		*/
       usedPages - stablePages + pages >
       freePages + reservedPages - usedPages - pages)  {
    // freep is seen by the collector: it should not consider it as a root.
    collect();
  }
  /* Discard any remaining portion of current page */
  if  (freeWords != 0)  {
#if HEADER_SIZE
    *freep = MAKE_HEADER(freeWords, freespace_tag);
#else
    *freep = *(GCP)aGcFreeObject;
    SET_OBJECTMAP(freep);
#endif
    freeWords = 0;
  }
  if (reservedPages - usedPages > reservedPages / 16) {
    // not worth looking for the last few ones dispersed through the heap
    int free = 0; /* # contiguous free pages	*/
    int allPages = lastReservedPage - firstReservedPage;
    firstPage = firstUnusedPage;
    while  (allPages--)  {
      if  (pageHeap[firstUnusedPage] == this &&
	   // in previous generation
	   pageSpace[firstUnusedPage] != current_space  &&
	   UNSTABLE(firstUnusedPage))  { // but not in stable set
	if  (++free == pages) {
	  freep = PAGE_to_GCP(firstPage);
	  goto FOUND;
	}
      } else {
	free = 0;
	firstPage = firstUnusedPage+1;
      }
      if (firstUnusedPage == lastReservedPage) {
	firstUnusedPage = firstPage = firstReservedPage;
	free = 0;
      } else
	firstUnusedPage++;
    }
  }
  {
    int reserved = MAX(8, pages); // get a bunch of them
    freep = allocate_page(reserved, this);
    firstUnusedPage = firstPage = GCP_to_PAGE(freep);
    i = firstPage + reserved - 1;
    lastReservedPage = MAX(lastReservedPage, i);
    reservedPages += reserved;
    for (i = pages; i < reserved; i++)
      pageSpace[firstPage + i] = UNALLOCATEDSPACE;
  }
 FOUND:
  // I found all needed contiguous pages.
  bzero((char*)freep, pages*BYTESxPAGE);
#if HEADER_SIZE && defined(DOUBLE_ALIGN)
  *freep++ = doublepad;
  freeWords = pages*WORDSxPAGE - 1;
#else
  freeWords = pages*WORDSxPAGE;
#endif
  usedPages += pages;
  bzero((char*)&ObjectMap[WORD_INDEX(firstPage*BYTESxPAGE)],
	pages*(BYTESxPAGE/BITSxWORD));
  pageSpace[firstPage] = next_space;
  pageGroup[firstPage] = pages;
  i = -1;
  while (--pages)  {
    pageSpace[++firstPage] = next_space;
    pageGroup[firstPage] = i--;
  }
  return freep;
}

/*----------------------------------------------------------------------
 * DefaultHeap::alloc --
 *
 * Storage is allocated by the following function.
 * It is up to the specific constructor procedure to assure that all
 * pointer slots are correctly initialized.
 *
 * Results: pointer to the object
 *
 * Side effects: freep, freeWords
 *______________________________________________________________________*/

GCP DefaultHeap::alloc(int size)
{
  GCP  object;		/* Pointer to the object */
  
  size = BYTEStoWORDS(size); // add size of header
  
  /* Try to allocate from current page */
  if  (size <= freeWords)  {
#if HEADER_SIZE
    object = freep;
    freeWords = freeWords - size;
    freep = freep + size;
#ifdef DOUBLE_ALIGN
    if  ((freeWords & 1) == 0  &&  freeWords)  {
      *freep++ = doublepad;
      freeWords = freeWords - 1;
    }
#endif
    return(object);
#else				// !HEADER_SIZE
#ifdef DOUBLE_ALIGN_OPTIMIZE
    if (size < 16 || ((int)freep & 7) == 0) {
#endif
      object = freep;
      freeWords = freeWords - size;
      freep = freep + size;
      return(object);
#ifdef DOUBLE_ALIGN_OPTIMIZE
    } else if (size <= freeWords - 1) {
      SET_OBJECTMAP(freep);
      *freep++ = *(GCP)aGcPadObject;
      object = freep;
      freeWords = freeWords - size - 1;
      freep = freep + size;
      return(object);
    }
#endif
#endif
  }
  /* Object fits in one page with left over free space*/
  if  (size < ONEPAGEOBJ_WORDS)  {
    reserve_pages(1);
    object = freep;
    freeWords = freeWords - size;
    freep = freep + size;
#if HEADER_SIZE && defined(DOUBLE_ALIGN)
    if  ((freeWords & 1) == 0  &&  freeWords)  {
      *freep++ = doublepad;
      freeWords = freeWords - 1;
    }
#endif
    return(object);
  }
  
  /* Object >= 1 page in size.
   * It is allocated at the beginning of next page.
   */
#if HEADER_SIZE
  if  (size > MAX_HEADER_WORDS)  {
    fprintf(stderr,
	    "\n***** gcalloc  Unable to allocate objects larger than %d bytes\n",
	    MAX_HEADER_WORDS * BYTESxWORD - BYTESxWORD);
    abort();
  }
#endif
#if HEADER_SIZE && defined(DOUBLE_ALIGN)
  reserve_pages((size + WORDSxPAGE) / WORDSxPAGE);
#else
  reserve_pages((size + WORDSxPAGE - 1) / WORDSxPAGE);
#endif
  
  object = freep;
  /* No object is allocated in final page after object > 1 page */
  if  (freeWords != 0)  {
#if HEADER_SIZE
    *freep = MAKE_HEADER(freeWords, freespace_tag);
#else
    *freep = *(GCP)aGcFreeObject;
    SET_OBJECTMAP(freep);
#endif
    freeWords = 0;
  }
  freep = NULL;
  return(object);
}

/*----------------------------------------------------------------------
 * gcobject --
 *
 * Results: 1 if the object is checked by the garbage collector, otherwise 0.
 *______________________________________________________________________*/

int gcobject(void *obj)
{
  extern int end;
  if (obj >= (void *)(&end)  &&
#ifdef STACK_GROWS_DOWNWARD
      obj < (void *)(&obj)
#else
      obj > (void *)(&obj)
#endif
      ) {
    int page = GCP_to_PAGE(obj);
    if (OUTSIDE_HEAP(page))
      return 0;
  }
  return 1;
}

/***********************************************************************
  new
  ***********************************************************************/

/*----------------------------------------------------------------------
 * GcObject::operator new --
 *
 * The creation of a new GC object requires:
 *	- to mark its address in table ObjectMap
 *	- to record its size in the header
 *______________________________________________________________________*/

void* GcObject::operator new(size_t size, CmmHeap *heap)
{
  GCP object = heap->alloc(size) + HEADER_SIZE;
  
  // To avoid problems in GC after new but during constructor
  // for (int i = 0; i < sizeof(GcObject)/sizeof(int); i++)
  //   object[i] = ((GCP)aGcObject)[i];
  //  actually just one element:
  *object = *((GCP)aGcObject);
  
#if HEADER_SIZE
  object[-HEADER_SIZE] = MAKE_HEADER(BYTEStoWORDS(size), MAKE_TAG(2));
#endif
  SET_OBJECTMAP(object);
  return (void *)object;
}

void GcObject::operator delete(void *obj)
{
  (((GcObject *)obj)->heap())->reclaim((GCP)obj);
}

/*----------------------------------------------------------------------
 * GcVarObject::operator new --
 *______________________________________________________________________*/

void* GcVarObject::operator new(size_t size, size_t ExtraSize, CmmHeap *heap)
{
  size += ExtraSize;
  
  GCP object = heap->alloc(size) + HEADER_SIZE;
  
  // To avoid problems in GC after new but during constructor
  // for (int i = 0; i < sizeof(GcVarObject)/sizeof(int); i++)
  //    object[i] = ((GCP)aGcVarObject)[i];
  //  actually just one element:
  *object = *((GCP)aGcVarObject);
  
#if HEADER_SIZE
  object[-HEADER_SIZE] = MAKE_HEADER(BYTEStoWORDS(size), MAKE_TAG(2));
#endif
  SET_OBJECTMAP(object);
  return (void *)object;
}

/***********************************************************************
  Verification
  ***********************************************************************/

/*----------------------------------------------------------------------
 * next_object --
 *
 * A pointer pointing to the header of an object is stepped to the next
 * header.  Forwarded headers are correctly handled.
 *
 * Results: address of immediately consecutive object
 *______________________________________________________________________*/

static GCP  next_object(GCP xp)
{
#if HEADER_SIZE
  if  (FORWARDED(*xp))
    return  xp + HEADER_WORDS(*((int*)(*xp) - HEADER_SIZE));
  else
    return  xp + HEADER_WORDS(*xp);
#else
  return  xp+ ((GcObject *)xp)->words();
#endif
}

/*----------------------------------------------------------------------
 * verify_object --
 *
 * Verifies that a pointer points to an object in the heap.
 * An invalid pointer will be logged and the program will abort.
 *______________________________________________________________________*/

static void  verify_object(GCP cp, int old)
{
  int  page = GCP_to_PAGE(cp);
  GCP  xp = PAGE_to_GCP(page); /* Ptr to start of page */
  int  error = 0;
  
  if  (page < firstHeapPage)  goto fail;
  error = 1;
  if  (page > lastHeapPage)  goto fail;
  error = 2;
  if  (pageSpace[page] == UNALLOCATEDSPACE)  goto fail;
  error = 3;
  if  (old  &&  UNSTABLE(page)  &&  pageSpace[page] != current_space)
    goto fail;
  error = 4;
  if  (old == 0  &&  pageSpace[page] != next_space)  goto fail; 
  error = 5;
  while  (cp > xp + HEADER_SIZE)  xp = next_object(xp);
  if  (cp == xp + HEADER_SIZE)  return;
 fail:
  fprintf(stderr,
	  "\n***** gcalloc  invalid pointer  error: %d  pointer: 0x%x\n",
	  error, cp);
  abort();
}

/*----------------------------------------------------------------------
 * verify_header --
 *
 * Verifies an object's header.
 * An invalid header will be logged and the program will abort.
 *______________________________________________________________________*/

#ifdef DOUBLE_ALIGN
#define HEADER_PAGES(header) ((HEADER_WORDS(header)+WORDSxPAGE)/WORDSxPAGE)
#else
#define HEADER_PAGES(header) ((HEADER_WORDS(header)+WORDSxPAGE-1)/WORDSxPAGE)
#endif

static void  verify_header(GCP cp)
{
#if HEADER_SIZE
  int  size = HEADER_WORDS(cp[-HEADER_SIZE]),
#else
  int  size = ((GcObject *)cp)->words(),
#endif
  page = GCP_to_PAGE(cp),
  error = 0;
  
  if  FORWARDED(cp[-HEADER_SIZE])  goto fail;
  error = 1;
#if HEADER_SIZE
  if  ((unsigned)HEADER_TAG(cp[-HEADER_SIZE]) > 2)  goto fail;
#endif
  if  (size <= ONEPAGEOBJ_WORDS)  {
    error = 2;
    if  (cp - HEADER_SIZE + size > PAGE_to_GCP(page + 1))  goto fail;
  } else  {
    error = 3;
#if HEADER_SIZE
    int  pages = HEADER_PAGES(cp[-HEADER_SIZE]);
#else
    int pages = pageGroup[page];
    if (pages < 0) pages = pageGroup[page+pages];
#endif
    int pagex = page;
    while  (--pages)  {
      pagex++;
      if  (pagex > lastHeapPage  ||
	   pageGroup[pagex] > 0  ||
	   pageSpace[pagex] != pageSpace[page])
	goto fail;
    }
  }
  return;
 fail:	fprintf(stderr,
		"\n***** gcalloc  invalid header  error: %d  object&: 0x%x  header: 0x%x\n",
		error, cp, cp[-HEADER_SIZE]);
  abort();
}

/***********************************************************************
  Logging and Statistics
  ***********************************************************************/

/*----------------------------------------------------------------------
 * log_root --
 *
 * Logs a root to stderr.
 *______________________________________________________________________*/

static void  log_root(unsigned* fp)
{
  int  page = GCP_to_PAGE(fp);
  if  (page < firstHeapPage  ||  page > lastHeapPage  ||
       pageSpace[page] == UNALLOCATEDSPACE  ||
       (UNSTABLE(page)  &&  pageSpace[page] != current_space))
    return;
  int pages = pageGroup[page];
  if (pages < 0) page += pages;
  GCP  p1, p2 = PAGE_to_GCP(page);
  while  (p2 < (GCP)fp)  {
    p1 = p2;
    p2 = next_object(p2);
  }
  fprintf(stderr, "***** DefaultHeap::alloc  root&: 0x%x  object&: 0x%x  %s\n",
	  fp, p1,
#if HEADER_SIZE
	  HEADER_TAG(*p1)
#else
	  *p1
#endif
	  );
}

/* Output a newline to stderr if logging is enabled. */

void  newline_if_logging()
{
  WHEN_FLAGS ((GCDEBUGLOG | GCROOTLOG | GCHEAPLOG),
	      fprintf(stderr, "\n"));
}
back to top