/******************************** -*- C -*- ****************************
 *
 *	Object Table maintenance module.
 *
 *	$Revision: 1.7.5$
 *	$Date: 2000/05/28 16:56:52$
 *	$Author: pb$
 *
 ***********************************************************************/

/***********************************************************************
 *
 * Copyright 1988-92, 1994-95, 1999, 2000 Free Software Foundation, Inc.
 * Written by Steve Byrne.
 *
 * This file is part of GNU Smalltalk.
 *
 * GNU Smalltalk is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2, or (at your option) any later 
 * version.
 * 
 * GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  
 *
 ***********************************************************************/


#include <stdio.h>
#include "gst.h"
#include "alloc.h"
#include "oop.h"
#include "dict.h"
#include "save.h"
#include "comp.h"
#include "callin.h"
#include "lex.h"
#include "lib.h"
#include "str.h"
#include "sym.h"
#include "sysdep.h"
#if STDC_HEADERS
#include <stdlib.h>
#include <string.h>
#endif /* STDC_HEADERS */

/* Size of the object semi spaces, in bytes */
#define	K		1024

/* you can increase this value if you need more space, and it won't hurt
 * performance *if* your machine has enough physical memory (otherwise, you
 * thrash the pager) */
#define INIT_MEM_SPACE_SIZE		(1 * K * K) 
#define NEW_GENERATION_SIZE		(128 * K) 


#define INIT_NUM_INCUBATOR_OOPS   50 		/* SWAG */
#define INCUBATOR_CHUNK_SIZE	  20 		/* SWAG */


/* Define this flag to turn on debugging code for OOP table management */
/* #define OOP_DEBUGGING */

/* Define this flag to force a GC on every object allocation. */
/* #define GC_TORTURE */


#define alignSize(size) \
 ( ((size) + sizeof(OOP) - 1) & ~(sizeof(OOP) - 1) )

/* Turn on the mark bit in OBJ */
#define markObject(obj) \
  (voidPtr)(((long)(obj)) | 1)

#define unmarkObject(obj) \
  (voidPtr)(((long)(obj)) & ~1)

#define isMarked(obj) \
  isObjMarked((obj)->objClass)

#define isObjMarked(obj) \
  ((long)(obj) & 1)




/* These are the real OOPS for nil, true, and false */
OOP			nilOOP, trueOOP, falseOOP;

/* The OOP table.  This contains a pointer to the object, and some flag
   bits indicating whether the object is read-only, reachable and/or pooled.
   Some of the bits indicate the difference between the allocated length
   (stored in the object itself), and the real length, because variable
   byte objects may not be an even multiple of sizeof(voidPtr). */
struct OOPStruct	*oopTable = nil, *allOopsTable;
OOP                     firstFreeOOP, lastUsedOOP;

int			numFreeOOPs, oopTableSize;

mst_Boolean		gcState = true, gcMessage = true;
static mst_Boolean	gcFlipping = false;

#ifdef GC_TORTURE
unsigned long		gcWaitFlipCount = 0, allocCounter = 0;
unsigned long		doTortureCounter = 0;
mst_Boolean		doGCTorture = false;
#endif


/* If there is this much space used after a gcFlip, we need to grow the
 * object heap by spaceGrowRate % next time we gcFlip, so that the storage
 * gets copied into the new, larger area.
 */
int			growThresholdPercent = 80;

/* Grow the object heap by this percentage when the amount of space used
 * exceeds growThresholdPercent.
 */
int			spaceGrowRate = 30;

/* This vector holds the storage for all the Character objects in the system.
   Since all character objects are unique, we pre-allocate space for 256 of
   them, and treat them as special built-ins when doing garbage collection.*/
CharObject		charObjectTable[NUM_CHAR_OBJECTS];

/* This is "nil" object in the system.  That is, the single instance of the
   UndefinedObject class, which is called "nil". */
struct NilObjectStruct	nilObject;

/* These represent the two boolean objects in the system, true and false.
   This is the object storage for those two objects. 
   false == &booleanObjects[0], true == &booleanObjects[1] */
struct BooleanObjectStruct booleanObjects[2];

/* This contains the maximum size of the heap.  It is checked at every
 * allocObj; if the space is too small, it is  brought up to spec before
 * being used
 */
unsigned long	maxSpaceSize;

/* This variable represents information about the memory space.  memSpace
   holds the required information: basically the pointer to the base and
   top of the space, and the pointers into it for allocation and copying.
*/
struct memorySpaceStruct memSpace;

/* These variables hold onto the object incubator's state */
OOP 			*incOOPBasePtr, *incOOPPtr, *incOOPEndPtr;



/* static mst_Object	moveObject(); */
static mst_Boolean	growMemory();
static void		initSpace(), displayObject(), allocOOPTable(),
			displayOOP();
			
static inline void	markOOPs(), sweepOOPs(), /* markGlobalOOPs(), */
			markIncubatorOOPs(), markFinalizableOOPReferences(),
			checkObjectsAfterSweep(),
			checkWeakRefs(), sweepPooledContexts();

static unsigned long	prepareForSweep();


/*
 *	void initOOPTable(size)
 *
 * Description
 *
 *	Initialize the OOP table.  Initially, all the OOPs are on the OOP free
 *	list so that's just how we initialize them.  We do as much
 *	initialization as we can, but we're called before classses are
 *	defined, so things that have definite classes must wait until
 *	the classes are defined.
 *
 * Input
 *
 *	size of the table to be created
 */
void
initOOPTable(size)
     long	size;
{
  int i;

  allocOOPTable(size);

  nilOOP->flags		= F_READONLY | F_REACHABLE;
  nilOOP->object	= (mst_Object)&nilObject;
  nilObject.objSize	= ROUNDED_WORDS(sizeof(struct NilObjectStruct));

  trueOOP->flags 		= F_READONLY | F_REACHABLE;
  trueOOP->object		= (mst_Object)&booleanObjects[0];
  falseOOP->flags 		= F_READONLY | F_REACHABLE;
  falseOOP->object		= (mst_Object)&booleanObjects[1];
  booleanObjects[0].objSize	= ROUNDED_WORDS(sizeof(struct BooleanObjectStruct));
  booleanObjects[1].objSize	= ROUNDED_WORDS(sizeof(struct BooleanObjectStruct));
  booleanObjects[0].booleanValue= trueOOP;
  booleanObjects[1].booleanValue= falseOOP;

  for (i = 0; i < NUM_CHAR_OBJECTS; i++) {
    charObjectTable[i].objSize = ROUNDED_WORDS(sizeof(charObjectTable[i]));
    charObjectTable[i].charVal = (char) i;
    oopTable[i + CHAR_OBJECT_BASE].object = (mst_Object)&charObjectTable[i];
    oopTable[i + CHAR_OBJECT_BASE].flags = F_READONLY | F_REACHABLE;
  }
}


void
allocOOPTable(size)
     long	size;
{
  register long i;
  long		bytes;

  oopTableSize  = size;
  bytes		= (size - FIRST_OOP_INDEX) * sizeof(struct OOPStruct);
  allOopsTable  = (struct OOPStruct *)xmalloc(bytes);

  oopTable	= &allOopsTable[-FIRST_OOP_INDEX];
  nilOOP	= &oopTable[nilOOPIndex];
  trueOOP	= &oopTable[trueOOPIndex];
  falseOOP	= &oopTable[falseOOPIndex];

  firstFreeOOP  	= &oopTable[size - 1];
  lastUsedOOP   	= oopTable;
  numFreeOOPs		= size;
  firstFreeOOP->object	= NULL;
  firstFreeOOP->flags	= F_FREE;
  
  i = size - 1;
  while(firstFreeOOP != &oopTable[0]) {
    firstFreeOOP = &oopTable[--i];
    firstFreeOOP->object = (mst_Object) &oopTable[i + 1];
    firstFreeOOP->flags = F_FREE;
  }
}

void
reallocOOPTable(newSize)
     long	newSize;
{
  long			bytes;
  struct OOPStruct 	*newOopTable, *oldOopTable;
  int			numFixed;
  mst_Object		object;
  OOP			oop;

  bytes		= (newSize - FIRST_OOP_INDEX) * sizeof(struct OOPStruct);
  oldOopTable	= allOopsTable;
  allOopsTable	= (struct OOPStruct *)xrealloc(allOopsTable, bytes);
  newOopTable	= allOopsTable;

  if (newOopTable != oldOopTable) {
    for (oop = newOopTable; oop < &oopTable[oopTableSize]; oop++) {
      if (oopValid(oop)) {
        object = oopToObj(oop);
        numFixed = numOOPs(object);
        allOopsTable = oldOopTable;
        fixupObject(object, numFixed);
        allOopsTable = newOopTable;
        restoreObject(object, numFixed);
      }
    }
  }

  lastUsedOOP   += (newOopTable - oldOopTable);
  oopTable	+= (newOopTable - oldOopTable);
  nilOOP	+= (newOopTable - oldOopTable);
  trueOOP	+= (newOopTable - oldOopTable);
  falseOOP	+= (newOopTable - oldOopTable);

  firstFreeOOP  	= &oopTable[newSize - 1];
  
  /* mark the new OOPs as available */
  for (oop = &oopTable[oopTableSize]; oop < &oopTable[newSize]; oop++) {
    oop->flags = F_FREE;
  }

  oopTableSize = newSize;
  refreshOOPFreeList();
}

/*
 *	void initBuiltinObjectsClasses()
 *
 * Description
 *
 *	Initialize the builtin objects after the respective classes
 *	have been created.
 *
 */
void
initBuiltinObjectsClasses()
{
  int		i;

  nilObject.objClass	= undefinedObjectClass;
  booleanObjects[0].objClass	= trueClass;
  booleanObjects[1].objClass	= falseClass;

  for (i = 0; i < NUM_CHAR_OBJECTS; i++) {
    charObjectTable[i].objClass = charClass;
  }
}

/*
 *	void fixupMetaclassObjects()
 *
 * Description
 *
 *	Called after the fundamental class hierarchy has been defined, this
 *	function goes through and fixes up all the objects in the oop table
 *	that don't have a objClass (objClass == nilOOP).  It's a
 *	chicken-and-egg problem: the metaclassClass doesn't yet exist when the
 *	hierarchy is put together, so after it's created, we have to go back
 *	and fix all the metaclasses that we created.
 *
 */
void
fixupMetaclassObjects()
{
  OOP		oop;
  mst_Object	object;

  for (oop = oopTable; oop <= lastUsedOOP; oop++) {
    object = oopToObj(oop);
    if (!(oop->flags & F_FREE) && isNil(object->objClass)) {
      object->objClass = metaclassClass;
    }
  }
}


/*
 *	OOP findAnInstance(classOOP)
 *
 * Description
 *
 *	Finds and returns an instance of the class CLASSOOP.  Returns "nil" if
 *	there are no instances present.
 *
 * Inputs
 *
 *	classOOP: 
 *		OOP for a class for which to find an instance
 *
 * Outputs
 *
 *	The first instance of the given class in the OOP table.
 */
OOP
findAnInstance(classOOP)
     OOP	classOOP;
{
  register OOP	oop;

  for (oop = oopTable; oop <= lastUsedOOP; oop++) {
    if (!(oop->flags & F_FREE) && (oopClass(oop) == classOOP)) {
      return (oop);
    }
  }

  return (nilOOP);
}


void
swapObjects(oop1, oop2)
     OOP	oop1, oop2;
{
  struct OOPStruct tempOOP;

  tempOOP = *oop2;		/* note structure assignment going on here */
  *oop2 = *oop1;
  *oop1 = tempOOP;
}

OOP
charOOPAt(c)
     Byte	c;
{
  return (&oopTable[c + CHAR_OBJECT_BASE]);
}

Byte
charOOPValue(charOOP)
     OOP	charOOP;
{
  return (charOOP - &oopTable[CHAR_OBJECT_BASE]);
}

/*
 *	mst_Boolean oopIndexValid(index)
 *
 * Description
 *
 *	Checks to see if index represents a valid OOP.
 *
 * Inputs
 *
 *	index : a long index into the OOP table, apparently 1 based due to
 *		being called from Smalltalk via a primitive.
 *
 * Outputs
 *
 *	True if the index represents a valid OOP table element, false
 *	otherwise.
 */
mst_Boolean
oopIndexValid(index)
     long	index;
{
  return (index >= FIRST_OOP_INDEX && index <= oopTableSize);
}


void
printObject(oop)
     OOP	oop;
{
  if (isInt(oop)) {
    printf("%ld", toInt(oop));
  } else if (isNil(oop)) {
    printf("nil");
  } else if (oop == trueOOP) {
    printf("true");
  } else if (oop == falseOOP) {
    printf("false");
  } else if (oopClass(oop) == charClass) {
    printf("$%c", charOOPValue(oop));
  } else if (oopClass(oop) == floatClass) {
    printf("%#g", floatOOPValue(oop));
  } else if (oopClass(oop) == symbolClass) {
    printf("#"); printSymbol(oop);
  } else if (oopClass(oop) == stringClass) {
    /* ### have to quote embedded quote chars */
    printf("'");
    printString(oop);
    printf("'");
  } else {
    printOOPConstructor(oop);
  }
  fflush(stdout);
}

void 
classifyAddr(addr)
     void	*addr;
{
  if (isOOPAddr(addr)) {
    displayOOP(addr);
  } else if (isObjAddr(addr)) {
    displayObject(addr);
  } else if isInt(addr) {
    printf("Smalltalk SmallInteger %ld\n", toInt(addr));
  } else {
    printf("Address %p is not a Smalltalk entity\n", addr);
  }
  fflush(stdout);
}

void
displayOOP(oop)
     OOP	oop;
{
  mst_Boolean	isBuiltin;
  
  if (!isOOPAddr(oop)) {
    printf("Parameter %p does not appear to be an OOP!\n", oop);
    return;
  }

  isBuiltin = (oop < oopTable);

  if (!isBuiltin) {
    printf ("OOP %p [%ld]\n", oop, (unsigned long) (oop - oopTable));
  }

  if (oop->flags & F_FREE) {
    printf("Free ");
  }

  if (oop->flags & F_REACHABLE) {
    printf("Reachable ");
  }

  printf("   Empty bytes = %ld\n", (oop->flags & EMPTY_BYTES));
  if (!(oop->flags & F_FREE)) {
    printObject(oop);
  }
  printf("\n");
}


void 
displayObject(obj)
     mst_Object	obj;
{
  if (!isObjAddr(obj)) {
    printf("Parameter %p does not appear to be an object!\n", obj);
    return;
  }
    
  printf("Object at %p, ", obj);
  printf("Size %ld\n", numOOPs(obj));
  printf("Class ");
  printObject(obj->objClass);
  printf("\n");
}


/*
 *	Object allocObj(size)
 *
 * Description
 *
 *	Allocate and return space for an object of SIZE bytes.  This basically
 *	means moving the allocation pointer for the current space up by SIZE
 *	bytes, and, if there isn't enough space left, flipping the garbage
 *	collector after memory is compacted.  The space is merely allocated;
 *      it is not initialized.
 *
 * Inputs
 *
 *	size  : size in bytes of the object to allocate.  This will be rounded
 *		by this routine up to a suitable boundary, typically to a 4
 *		byte boundary.
 *
 * Outputs
 *
 *	Address of the newly allocated object.
 */
mst_Object
allocObj(size)
     unsigned long	size;
{
  register char	*newAllocPtr, *oldAllocPtr;

#ifdef GC_TORTURE
  if (gcState && doGCTorture) {
    minorGCFlip();
  }
#endif  

  size = alignSize(size);

  /* We don't want to have allocPtr pointing to the wrong thing during GC, so
   * we use a local var to hold its new value
   */
  newAllocPtr = memSpace.allocPtr + size;
  if (newAllocPtr >= memSpace.maxPtr) {
    if (!gcFlipping) {
      /* not enough room currently, try to make some more */
      int percent;
      percent = (memSpace.newAllocPtr - memSpace.space)
        * 100 / memSpace.totalSize;

      if (percent >= growThresholdPercent) {
        gcFlip();
      } else {
        minorGCFlip();
      }

      newAllocPtr = memSpace.allocPtr + size;
    }
    if (newAllocPtr >= memSpace.maxPtr) {
      /* uh oh, still too big -- we need to grow memory */
      unsigned long spaceInUse;
      unsigned long spaceNeeded;

      spaceInUse = memSpace.allocPtr - memSpace.space;
      
      /* we need what we already are using, plus some breathing room */
      spaceNeeded = size + spaceInUse;
      spaceNeeded += spaceNeeded * spaceGrowRate / 100;
      if (!growMemoryTo(spaceNeeded)) {
	/* !!! do something more reasonable in the future */
	errorf("Cannot recover, exiting...");
	exit(1);
      }
      newAllocPtr = memSpace.allocPtr + size;
    }
  }

  oldAllocPtr = memSpace.allocPtr;
  memSpace.allocPtr = newAllocPtr;
  return ((mst_Object)oldAllocPtr);
}



/*
 *	mst_Boolean gcOff()
 *
 * Description
 *
 *	Turns off the garbage collector.  Returns the previous on/off state.
 *
 * Outputs
 *
 *	Previous state of the garbage collector (on or off).
 */
mst_Boolean
gcOff()
{
  mst_Boolean	oldGCState;

  oldGCState = gcState;
  gcState = false;
  return (oldGCState);
}

/*
 *	void gcOn()
 *
 * Description
 *
 *	Turns on the garbage collector.
 *
 */
mst_Boolean
gcOn()
{
  mst_Boolean	oldGCState;

  oldGCState = gcState;
  gcState = true;
  return (oldGCState);
}

/*
 *	void setGCState(state)
 *
 * Description
 *
 *	Set the garbage collector flag to the specified state (either on or
 *	off).
 *
 * Inputs
 *
 *	state : mst_Boolean, true => gc on.
 *
 */
mst_Boolean
setGCState(state)
     mst_Boolean	state;
{
  if(state) {
    return(gcOn());
  } else {
    return(gcOff());
  }
}



/*
 *	void initMem()
 *
 * Description
 *
 *	Initialize the memory allocator.  The memory space is allocated, and
 *	the various garbage collection flags are set to their initial values.
 *
 */
void
initMem()
{
  maxSpaceSize = INIT_MEM_SPACE_SIZE;
  initSpace(&memSpace);

  gcOff();
  incInitRegistry();
}


mst_Object
curSpaceAddr()
{
  return ((mst_Object)memSpace.space);
}

void
setSpaceInfo(size)
     long	size;
{
  memSpace.newAllocPtr = memSpace.allocPtr = memSpace.space + size;
}


/*
 *	mst_Boolean growTo(spaceSize)
 *
 * Description
 *
 *	Grows the allocated memory to the given size in bytes, if it's not
 *	there already.  In the future, the gc should give some indication that
 *	it was not able to acquire the required number of bytes, and this
 *	function will return false, causing the system primitive to fail.
 *
 * Inputs
 *
 *	spaceSize: 
 *		Size in bytes to grow the spaces to.
 *
 * Outputs
 *
 *	True if the operation was successful, False if the memory could not be
 *	allocated (this is not currently implemented).
 */
mst_Boolean
growTo(spaceSize)
     unsigned long spaceSize;
{
  if (spaceSize > maxSpaceSize) {
    maxSpaceSize = spaceSize;
    gcFlip();
  }
  
  return true;
}


/*
 *	mst_Boolean growMemoryTo(spaceSize)
 *
 * Description
 *
 *	Grows the memory segment to sapceSize.  Shoudl be called after the
 *	sweep has occurred so that things are contiguous.  Ensures that the OOP
 *	table pointers are fixed up to point to the new objects.
 *
 * Inputs
 *
 *	spaceSize: 
 *		The size of memory to grow to.  If it's not larger than the
 *		current allocation, nothing happens.
 *
 * Outputs
 *
 *	True if the operation succeeded, false of the memory could not be
 *	grown. 
 */
mst_Boolean
growMemoryTo(spaceSize)
     unsigned long spaceSize;
{
  if (spaceSize > maxSpaceSize) {
    maxSpaceSize = spaceSize;
    return growMemory();
  }
  
  return true;
}
  


/*
 *	static mst_Boolean growMemory()
 *
 * Description
 *
 *	Grows the memory segment to maxSpaceSize.  Should be called after the
 *	sweep has occurred so that things are contiguous.  Ensures that the OOP
 *	table pointers (the live ones) are fixed up to point to the new
 *	objects. 
 *
 */
mst_Boolean
growMemory()
{
  unsigned long spaceDelta;
  char		*oldSpacePtr;
  OOP		oop;

  fixupObjectPointers();
  oldSpacePtr = memSpace.space;
  memSpace.space = (char *)xrealloc(memSpace.space, maxSpaceSize + NEW_GENERATION_SIZE);
  if (!memSpace.space) {
    printf("\n\n[Memory allocation failure]\nCan't allocate enough memory to continue.\n");
    /* try to recover */
    maxSpaceSize = memSpace.totalSize;
    memSpace.space = oldSpacePtr;
    return (false);
  }
  spaceDelta = memSpace.space - oldSpacePtr;
  memSpace.totalSize = maxSpaceSize;
  memSpace.allocPtr += spaceDelta;
  memSpace.newAllocPtr += spaceDelta;
  memSpace.maxPtr = memSpace.space + memSpace.totalSize;
#ifdef GROW_DEBUG
  printf("old = %8x, new = %8x, delta = %8x\n", oldSpacePtr, memSpace.space, spaceDelta);
#endif

  if (oopTable) {
    /* Fix up the OOP table pointers to objects */
    for (oop = oopTable; oop <= lastUsedOOP; oop++) {
      if (!(oop->flags & (F_FREE | F_POOLED))) {
#ifdef GROW_DEBUG
        voidPtr obj;
        printf("old = %8x, ", obj = (voidPtr) oop->object);
#endif
	oop->object = (mst_Object)(((char *)oop->object) + spaceDelta);
#ifdef GROW_DEBUG
	printf("new = %x, delta = %x\n", oop->object, ((voidPtr)oop->object) - obj);
#endif
      }
    }
  }
  restoreObjectPointers();

  return true;
}



/*
 *	void gcFlip()
 *
 * Description
 *
 *	Mark & sweep the objects.  Starting from the root set, recursively mark
 *	objects as reachable, then compact memory, thus eliminating objects
 *	that are not reachable (sweeping them).  Then, check if the space has
 *      to be grown and, if so, readjust the collector's parameters.
 *
 */
void
gcFlip()
{
  int	lastPercent;

#ifdef PROFBLOCK
  ps.numMajorGCs++;
#endif

  if (gcMessage && !regressionTesting) {
    /* print the first part of this message before we finish scanning 
     * oop table for live ones, so that the delay caused by this scanning
     * is apparent.
     * note the use of stderr for the printed message.  The idea here was
     * that generated output could be treated as Smalltalk code, HTML or
     * whatever else you want without harm.
     */
    fflush(stdout);
    fprintf(stderr, "\"Major GC flip... ");
    fflush(stderr);
  }

  gcFlipping = true;
  fixupObjectPointers();
  markOOPs();
  sweepOOPs(memSpace.space);
  restoreObjectPointers();
  gcFlipping = false;

  /* At this point, storage in memory is compacted and contiguous, so we can
   * examine how much memory we have left, and decide if we need to increase
   * memory some more.
   */
  lastPercent = (memSpace.allocPtr - memSpace.space) * 100
    / memSpace.totalSize; 
  
  if (lastPercent > growThresholdPercent) {
    /* with bad grow rates, can undergrow.  Takes care of it */
    maxSpaceSize += maxSpaceSize / 100 * spaceGrowRate;
    maxSpaceSize &= ~(sizeof(long)-1);		/* round to word boundary */
    if (maxSpaceSize > memSpace.totalSize) {
      growMemory();
    }
    maxSpaceSize = memSpace.totalSize;
  }

  if (gcMessage && !regressionTesting) {
    fprintf(stderr, "done, used space = %i%%\"\n", lastPercent);
    fflush(stderr);
  }

  checkObjectsAfterSweep();
}

/*
 *	void minorGCFlip()
 *
 * Description
 *
 *	Mark & sweep the new objects.  Starting from the root set, recursively
 *	mark objects as reachable, then include the actually reachable ones to
 *	the old generation.
 *
 */
void
minorGCFlip()
{
  int lastPercent;

#ifdef PROFBLOCK
  ps.numMinorGCs++;
#endif

  if (gcMessage && !regressionTesting) {
    /* print the first part of this message before we finish scanning 
     * oop table for live ones, so that the delay caused by this scanning
     * is apparent.
     * note the use of stderr for the printed message.  The idea here was
     * that generated output could be treated as Smalltalk code, HTML or
     * whatever else you want without harm.
     */
    fflush(stdout);
    fprintf(stderr, "\"Minor GC flip...");
    fflush(stderr);
  }

  gcFlipping = true;
  fixupObjectPointers();
  markOOPs();
  sweepOOPs(memSpace.newAllocPtr);
  restoreObjectPointers();
  gcFlipping = false;

  lastPercent = (memSpace.allocPtr - memSpace.space) * 100
    / memSpace.totalSize;

  if (gcMessage && !regressionTesting) {
    fprintf(stderr, " done, used space = %i%%\"\n", lastPercent);
    fflush(stderr);
  }

  checkObjectsAfterSweep();
}


/*
 *	static void checkObjectsAfterSweep()
 *
 * Description
 *
 *	Performs special checks on weak and finalizable objects.
 *	When one of the objects pointed to by a weak object have no
 *	other references, the slot of the weak object is replaced by
 *	a nil.
 *	When a finalizable object has no references outside weak objects,
 *	prepareForSweep() marks it in a buffer.  This routine (which
 *	is executed after the sweep) calls back the finalize method.
 *
 */
void
checkObjectsAfterSweep()
{
  register OOP	*pOOP;
  register long	size;

  /* Make a local copy of the buffer */
  size = bufferSize();
  pOOP = alloca(size);
  copyBuffer(pOOP);
  size /= SIZEOF_CHAR_P;

  while (size--) {
    msgSend(*pOOP++, finalizeSymbol, nil);
  }
}

void
checkWeakRefs(oop)
     register OOP oop;
{
  mst_Object		object;
  register OOP		*field;
  register int		numFields;
  
  object = oopToObj(oop);
  for (field = object->data, numFields = numOOPs(object); numFields;
       field++, numFields--) {
    if (isInt(*field)) {
      continue;
    }
    if (*field <= oop) {
      /* Not yet scanned */
      if (!isOOPMarked(*field)) {
	*field = nilOOP;
      }
    } else {
      /* Already scanned */
      if (isOOPFree(*field)) {
	*field = nilOOP;
      }
    }
  }
}

void markOOPs()
{
  markAnOOPInternal(smalltalkDictionary, nil, nil);
  markProcessorRegisters();
  markRegisteredOOPs();
  markIncubatorOOPs();
  markCompileContext();
  markFinalizableOOPReferences();

#ifdef DEBUG_FREED /* Mon Jul  3 00:38:46 1995 */
/**/  {
/**/    OOP oop; int i;
/**/    for (i = 0, oop = oopTable;  oop < &oopTable[oldOopTableIndex]; oop++, i++) {
/**/      if (!(oop->flags & F_REACHABLE)) {
/**/	printf("[%4d]: "); fflush(stdout);
/**/	printObject(oop);
/**/	printf("\n");
/**/	fflush(stdout);
/**/      }
/**/    }
/**/  }
#endif /* DEBUG_FREED Mon Jul  3 00:38:46 1995 */
}

#define tailMarkOOP(newOOP) { \
  oop = (newOOP); \
  continue;		/* tail recurse!!! */ \
}

#define tailMarkOOPRange(firstOOP, oopAtEnd) { \
  curOOP = (OOP *)(firstOOP); \
  atEndOOP = (OOP *)(oopAtEnd); \
  oop = nil; \
  continue; \
}

/*
 *	static void markAnOOPInternal(oop, curOOP, atEndOOP)
 *
 * Description
 *
 *	The transitive marker.  This function works in two ways:
 *	a) when oop is nil, it walks the list of pointers to OOPs
 *	starting at curOOP (included) and finishing at atEndOOP
 *	(excluded).  Each object in the list is then marked.
 *	b) when oop is not nil, it tail recurses telling itself to
 *	mark the pointers referred to by the object pointed to by oop.
 *	Note that a single function does both these jobs to allow a
 *	fast, tail-recursive implementation of single-object marking.
 *
 *	It is called a transitive marker because the recursive approach
 *	is an algorithmic representation of the transitive property: if
 *	A (in the root set) refers to B, and B refers to C, then A indi-
 *	rectly refers to C and C is to be considered reachable.
 *	This function does not mark weak objects, for obvious reasons.
 *
 * Input
 *	see above
 */
void
markAnOOPInternal(oop, curOOP, atEndOOP)
     register OOP	oop;
     register OOP	*curOOP;
     OOP		*atEndOOP;
{
  for (;;) {
    if (!oop) {						/* in the loop! */
#ifndef OPTIMIZE
      mst_Object obj = (mst_Object) (curOOP - 1);	/* for debugging */
#endif
    iterationLoop:
      /* in a loop, do next iteration */
      oop = *curOOP;
      curOOP++;
      if (isOOP(oop)) {
#ifndef OPTIMIZE
	if (!isOOPAddr(oop)) {
	  printf("Error! Invalid OOP %p was found inside %p!\n", oop, obj);
	  debug();
        } else
#endif
        if (!isOOPMarked(oop)) {
	  if (curOOP < atEndOOP) {
	    markAnOOPInternal(oop, nil, nil);
	    goto iterationLoop;
	  } else {
	    /* On the last object in the set, reuse the current invocation.
	     * oop is valid, so we go to the single-object case */
	    continue;
	  }
        }
      }
      /* We reach this point if the object isn't to be marked.  The code above
         contains a continue to tail recurse, so we cannot put the loop in a
         do...while and a goto is necessary here.  Speed is a requirement, so
         I'm doing it. */
      if (curOOP < atEndOOP) {
        goto iterationLoop;
      }
    } else {		/* just starting with this oop */
      OOP		objClass;
      mst_Object	object;
      unsigned long	size;

#ifndef OPTIMIZE
      if (isOOPFree(oop)) {
        printf("Error! Free OOP %p is being marked!\n", oop);
        debug();
        break;
      }
      if (!isPooled(oop) && !isObjAddr(oopToObj(oop))) {
        printf("Error! OOP at %p points to invalid object data at %p!\n", oop, oop->object);
        debug();
        break;
      }
#endif
      /* see if the object has pointers, set up to copy them if so. */
      oop->flags |= F_REACHABLE;
      object = oopToObj(oop);
      objClass = object->objClass;
      if (oop->flags & F_CONTEXT) {
        MethodContext	ctx;
        long		methodSP;
        ctx = (MethodContext) object;
        methodSP = toInt(ctx->spOffset);
	/* printf("setting up for loop on context %x, sp = %d\n", ctx, methodSP); */
        tailMarkOOPRange(&ctx->objClass, ctx->contextStack + methodSP + 1);

      } else if (oop->flags & F_WEAK) {
        if (!isOOPMarked(objClass)) {
 	  tailMarkOOP(objClass);
 	}

      } else {
        size = numOOPs(object);
 	if (size) {
 	  tailMarkOOPRange(&object->objClass, object->data + size);
 	} else if (!isOOPMarked(objClass)) {
 	  tailMarkOOP(objClass);
 	}
      }
    }
    /* This point is reached if and only if nothing has to be marked anymore in
       the current iteration. So exit. */
    break;
  } /* for(;;) */
}

/*
 *	void refreshOOPFreeList()
 *
 * Description
 *
 *	Iterate through the OOP table.  Rebuild the free OOP list.
 *
 */
void
refreshOOPFreeList()
{
  register OOP  newFirstFree, oop;

  /* The free list will be reconstructed */
  newFirstFree = NULL;
  numFreeOOPs = oopTableSize;

  /* Proceed backwards so that the first free OOPs are at the head of the
     free list.  This minimizes the amount of space used by the OOP table in
     a saved image. */

  for (oop = &oopTable[oopTableSize - 1]; oop >= oopTable; oop--) {
    if (oop->flags & F_FREE) {
      oop->object  = (mst_Object) newFirstFree;
      newFirstFree = oop;
    } else {
      lastUsedOOP = oop;
      numFreeOOPs--;
      break;
    }
  }
  while(--oop >= oopTable) {
    if (oop->flags & F_FREE) {
      oop->object  = (mst_Object) newFirstFree;
      newFirstFree = oop;
    } else {
      numFreeOOPs--;
    }
  }
  firstFreeOOP = newFirstFree;
}

/*
 *	static unsigned long prepareForSweep(bottom)  [was: reverseOOPPointers]
 *
 * Description
 *
 *	Iterate through the OOP table.  On marked OOPs, store
 *	the pointer to the object's class into the OOP and the OOP pointer
 *	where the object class usually is.  This allows the sweep phase to
 *	change the OOPs as it moves objects in memory.  Also mark specially
 *	objects to be finalized.
 *
 * Inputs
 *
 *	bottom: The base address over which we can start to reverse pointers
 *
 * Outputs
 *
 *	The number of bytes to be allocated for reachable pooled objects.
 */
unsigned long
prepareForSweep(bottom)
     voidPtr bottom;
{
  register OOP  	newFirstFree, oop;
  register mst_Object	object;
  register unsigned long pooledSize;

  /* The free list will be reconstructed, but the unused OOPs are unchanged */
  newFirstFree = firstFreeOOP;
  numFreeOOPs = oopTableSize;
  pooledSize = 0;

  resetBuffer();

  /* Proceed backwards so that the first free OOPs are at the head of the
     free list.  This minimizes the amount of space used by the OOP table in
     a saved image. */

  for (oop = lastUsedOOP; oop >= oopTable; oop--) {
    if (oop->flags & F_WEAK) {
      checkWeakRefs(oop);
    }

    if (oop->flags & (F_FINALIZE | F_REACHABLE)) {
      if (oop->flags & F_POOLED) {
        /* Reachable pooled object.  Get it to the heap. */
        pooledSize += size2Bytes(oopToObj(oop)->objSize);

      } else if (((voidPtr) oop->object) >= bottom) {
        /* Object reachable after mark phase.  Reverse the pointer */
        object = oopToObj(oop);
        oop->object = (mst_Object)object->objClass;
        object->objClass = markObject(oop);
      }

      if (!(oop->flags & F_REACHABLE)) {
        /* Object is *going* to be finalized, but it was not yet.  We found a
         * weak reference to it, so we mark it so that finalization will occur
         * soon after the end of the sweep pass.  In the meanwhile, we let it
         * survive and decide the object's fate at the next GC pass */
        oop->flags ^= F_FINALIZE;
        addBufPointer(oop);
      }
      oop->flags &= ~F_REACHABLE;
      numFreeOOPs--;

    } else if (!(oop->flags & F_FREE)) {
      /* Object not marked and not already freed.  Add to OOP free list */
      oop->flags   = F_FREE;
      oop->object  = (mst_Object) newFirstFree;
      newFirstFree = oop;
      if (oop == lastUsedOOP) {
        lastUsedOOP--;
      }
    }
  }
  firstFreeOOP = newFirstFree;

  return (pooledSize);
}

/*
 *	static void sweepPooledContexts(dest)
 *
 * Description
 *
 *	Iterate through the OOP table.  Copy pooled, marked objects
 *	to the main heap space (starting at address dest), free the
 *	others.
 *
 */
void
sweepPooledContexts(dest)
     register char *dest;
{
  register OOP		 oop;
  register unsigned long size;

  for (oop = lastUsedOOP; oop >= oopTable; oop--) {
    if (oop->flags & F_POOLED) {
      size = size2Bytes(oopToObj(oop)->objSize);
      memcpy(dest, oop->object, size);
      oop->object = (mst_Object) dest;
      oop->flags &= ~(F_POOLED | F_REACHABLE);
      dest += size;
    }
  }
  emptyContextPool();
}

/* #define SWEEP_DEBUG */
static inline void
sweepOOPs(bottom)
     char *bottom;
{
  register char		*from, *fromStart, *to;
  unsigned long		chunkSize, pooledSize;
  register mst_Object	object;
  OOP			curClass, oop;

  pooledSize = prepareForSweep(bottom);

  /* Algorithm:
     initialize:
     * Start at beginning of allocated space.
     * Skip over the initial contiguous range of marked object, unmarking
       as you go.

     loop:
     * skip over the contiguous range of unmarked objects, leaving "to"
       where it is and advancing "from".
     * if "to" passes the end of allocated storage, we are done.
     * set "fromStart" to "from", and skip over the next contiguous range of
       marked objects, advancing "from".
     * copy the range ["fromStart".."from") to "to".  advance "to" to right
       after the newly copied area.
   */
       
  from = to = bottom;

  while (to < memSpace.allocPtr) {
    object = (mst_Object)to;
    if (!isMarked(object)) {
      /* found the end of the contiguous range */
      break;
    }
    /* unmark this dude */
    oop = unmarkObject(object->objClass);
    curClass = (OOP)oop->object;
    oop->object = object;
    object->objClass = curClass;

    to += size2Bytes(object->objSize);
  }

#ifdef SWEEP_DEBUG
   printf("skipped %d bytes of contig alloc %x space %x max %x\n",
	 to - memSpace.space, memSpace.allocPtr, memSpace.space,
	 memSpace.maxPtr);
#endif /* SWEEP_DEBUG */

  /* we've skipped over the marked initial set of objects, for which
   * no move is necessary.  Now begin the main execution loop
   */

  from = to;
  while (from < memSpace.allocPtr) {
    fromStart = from;		/* debugging only */
    while (from < memSpace.allocPtr) {
      object = (mst_Object)from;
      if (isMarked(object)) {
	/* found a non-free chunk */
	break;
      }

      /* skip over the free memory */
      from += size2Bytes(object->objSize);
    }

#ifdef SWEEP_DEBUG
     printf("skipped free range %x .. %x %d bytes\n", fromStart, from, from - fromStart);
#endif /* SWEEP_DEBUG */

    if (from >= memSpace.allocPtr) {
#ifdef SWEEP_DEBUG
       printf("hit end of memory\n");
#endif /* SWEEP_DEBUG */
      break;			/* we've hit the end of active memory */
    }

    fromStart = from;
    /* span the next in-use contiguous chunk of objects */
    while (from < memSpace.allocPtr) {
      object = (mst_Object)from;
      if (!isMarked(object)) {
	/* found a free chunk */
	break;
      }

      /* unmark this dude & tell the oop where the object *will be*  */
      oop = unmarkObject(object->objClass);
      curClass = (OOP)oop->object;
      oop->object = (mst_Object)(to + ((char *)object - fromStart));
      object->objClass = curClass;

      /* skip over the object */
      from += size2Bytes(object->objSize);
    }


    /* copy the bytes down */
    chunkSize = from - fromStart;
#ifdef SWEEP_DEBUG
     printf("copying range %x .. %x to %x, %d bytes\n",
	   fromStart, from, to, chunkSize);
#endif /* SWEEP_DEBUG */

    memcpy(to, fromStart, chunkSize);
    to += chunkSize;
  }

  memSpace.allocPtr = to;
  
  object = allocObj(pooledSize);
  sweepPooledContexts((char *) object);
  memSpace.newAllocPtr = memSpace.allocPtr;
}

void
markFinalizableOOPReferences()
{
  register OOP  oop;

  for (oop = oopTable; oop <= lastUsedOOP; oop++) {
    /* A finalizable object will always survive this GC flip, even if it is
       not reachable.  We mark the objects that they refer to, so they survive
       too, keeping the finalizable object marked as unreachable. */

    if ((oop->flags & (F_FINALIZE | F_REACHABLE)) == F_FINALIZE) {
      markAnOOPInternal(oop, nil, nil);
      oop->flags ^= F_REACHABLE;
    }
  }
}

#ifdef not_needed
/**/void
/**/markGlobalOOPs()
/**/{
/**/  OOP		**oopPtr, oop;
/**/
/**/  /* first mark them as reachable to work on the global objects */
/**/  /* one at a time and have more locality of reference */
/**/  for (oopPtr = globalOOPs; *oopPtr; oopPtr++) {
/**/    oop = **oopPtr;
/**/    oop->flags |= F_REACHABLE;
/**/  }
/**/  /* then do the real marking */
/**/  for (oopPtr = globalOOPs; *oopPtr; oopPtr++) {
/**/    markAnOOPInternal(**oopPtr, nil, nil);
/**/  }
/**/}
#endif

/*
 *	static void initSpace(space)
 *
 * Description
 *
 *	Initializes the allocation and copying pointers for space SPACE.
 *
 * Inputs
 *
 *	space : Pointer to the struct memorySpaceStruct to be initialized.
 *
 */
void
initSpace(space)
     struct memorySpaceStruct *space;
{
  space->space = (char *)xmalloc(maxSpaceSize + NEW_GENERATION_SIZE);
  space->totalSize = maxSpaceSize;
  space->allocPtr = space->space;
  space->newAllocPtr = space->space;
  space->maxPtr = space->space + space->totalSize;
}




#ifdef GC_TORTURE

/*
 *	void startGCTorture()
 *
 * Description
 *
 *	User level debugging routine to verify correct operation in a range of
 *	code.  Invoking this function ensures that the GC torturing is on.
 *	Calls to this function and stopGCTorture nest, so only the outermost
 *	call really has an effect.
 *
 *	GC torturing means that the garbage collector is run on every
 *	allocation.  This means that objects which are not reachable from the
 *	root set will be immediately freed.
 *
 */
void
startGCTorture()
{
  doGCTorture = true;
  doTortureCounter++;
}


/*
 *	void stopGCTorture()
 *
 * Description
 *
 *	User level debugging routine associated with startGCTorture.  Turns off
 *	the GC torturing if it's the outermost (in an invocation-stacking
 *	order) one, otherwise, just decrements the torture count.
 *
 */
void
stopGCTorture()
{
  if (doTortureCounter > 0) {
    if (--doTortureCounter == 0) { /* on the transition to 0... */
      doGCTorture = false;
    }
  }
}

#endif



/***********************************************************************
 *
 * Incubator support routines
 *
 ***********************************************************************/

void
incInitRegistry()
{
  incOOPBasePtr = (OOP*)xmalloc(INIT_NUM_INCUBATOR_OOPS * sizeof(OOP *));
  incOOPPtr = incOOPBasePtr;
  incOOPEndPtr = incOOPBasePtr + INIT_NUM_INCUBATOR_OOPS;
}

void
incGrowRegistry()
{
  OOP*		oldBase;
  unsigned long oldPtrOffset;
  unsigned long oldRegistrySize, newRegistrySize;

  oldBase = incOOPBasePtr;
  oldPtrOffset = incOOPPtr - incOOPBasePtr;
  oldRegistrySize = incOOPEndPtr - incOOPBasePtr;

  newRegistrySize = oldRegistrySize + INCUBATOR_CHUNK_SIZE;

  incOOPBasePtr = (OOP *)xrealloc(incOOPBasePtr, newRegistrySize * sizeof(OOP *));
  incOOPPtr = incOOPBasePtr + oldPtrOffset;
  incOOPEndPtr = incOOPBasePtr + newRegistrySize;
}

void
markIncubatorOOPs()
{
  markOOPRange(incOOPBasePtr, incOOPPtr);
}
