Raw File
/*****************************************************************************
 *
 *  msw.cpp:	mark&sweep garbage collector for CMM.
 *
 *  version:    0.0.2 (30 Oct 96)
 *  authors:	Pietro Iglio
 *  email:	cmm@di.unipi.it
 *  address:	Dipartimento di Informatica
 *		Corso Italia 40
 *		I-56125 Pisa, Italy
 *
 *  Copyright (C) 1995 Pietro Iglio
 *
 *  This file is part of the PoSSo Customizable Memory Manager (CMM).
 *
 * 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 agree to license at no charge to all parties under these terms and
 * conditions any derivative works or modified versions of this software.
 *
 * 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 THE COPYRIGHT HOLDERS DISCLAIM ALL
 * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL THE COPYRIGHT HOLDERS
 * 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.
 *
 ****************************************************************************/

/* Following macros can be defined at compile time to get debug info and
 * heap checking:
 *
 *	- NDEBUG
 *	- MSW_CHECK_HEAP: perform automatic heap checking before/after every
 *                        collection and tempHeap destruction.
 *	- MSW_SERIAL_DEBUG
 *	- MSW_TRACE_ONE_PAGE
 *	- MSW_DONT_TAG_FREE_MEM: when NDEBUG is on avoid filling with a tag
 *	                         each empty/released memory object.
 *
 * Other macros that can be defined at compile time:
 *
 *	- MSW_ALLOC_ZERO_OK: enables allocation of 0-sized memory objects.
 *	- MSW_GET_ALLOC_SIZE_STATS: counts blocks requests for each size.
 *	- MSW_SHOW_TIMINGS: after each collection shows the time required
 */

/*---------------------------------------------------------------------------*
 * DEFINITIONS:
 *---------------------------------------------------------------------------
 * FreeChunks:
 *   A chunk is a set of one or more consecutives pages.
 *   A chunk class is the set of chunks of the same size.
 *   Free chunk classes are keeped in a list sorted by size. Each chunk class
 *   is keeped in a list too.
 *   Eg.   size(2) -> size(8) -> size(20)
 *	for size(2):
 *	  chunk1 -> chunk2 -> ...
 *
 *   header->nextPage points to the next chunk is the same class
 *   header->nextChunk points to the next chunk class.
 *
 *---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*

  MSW handles small and large objects differently.  A small object is an
  object whose size is less than 256 bytes.

  MSW gets pages from allocatePages(). Each page is marked as either
  SINGLE, when used for small objects, or GROUPED.

  Each SINGLE page contains only objects of the same exact word size.
  Each page contains a free list linking all free objects within that page.

  During the sweep phase any non marked object is released:
  in the case of a small object, it is added to the free list of the page;
  otherwise the corresponding set of {\em grouped} pages is added to the set of
  available pages.
  Non marked pages can be immediately released without scanning them.

  Each object has a header which contains a bitmask (telling whether the
  object is allocated, free or marked) and a pointer to the next free object in
  the same page.
  the header is before the object, therefore, when cerating a page of fixed
  objects of size S, MSW allocates S+OBJ_ALIGNMENT bytes per object.

  Adding OBJ_ALIGNMENT ensures that the next object is properly aligned.
  [Since a rounding of S is done entering mswAlloc, one could instead add
   PtrSize before rounding S and avoid adding OBJ_ALIGNEMENT. Beppe ]

 *---------------------------------------------------------------------------*/


#include "cmm.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <setjmp.h>

#ifdef unix
#   include <unistd.h>
#endif

/*---------------------------------------------------------------------------*
 * :: Verbosity
 *---------------------------------------------------------------------------*/

#define mswVERBOSE(STMT)	WHEN_VERBOSE(CMM_STATS, STMT)

/*---------------------------------------------------------------------------*
 * :: Debug Stuff
 *---------------------------------------------------------------------------*/

static unsigned long	markedBytes = 0;
static unsigned long	sweptBytes  = 0;

static unsigned 	totFreeFPages = 0;
static unsigned long	totFreeFixedMem = 0;

static unsigned long	allocSerial   = 0;
static unsigned long	freeSerial    = 0;
static unsigned long	collectSerial = 0;

#define gcOut	stderr

#ifdef NDEBUG
#    define mswDEBUG(STMT)
#    define mswTagMemDEBUG(STMT)	
#    define mswSerialDEBUG(STMT)
#    define mswGcDEBUG(STMT)
#    define mswCheckDEBUG(STMT)
#    define mswCondCheckDEBUG(STMT)
#    define mswTracePageDEBUG(page)
#    define mswGetStatsDEBUG(STMT)
#else
     int mswGcDebug = 0;
     int mswCheckDebug = 1;
#    define mswDEBUG(STMT)	STMT

#    if defined(MSW_DONT_TAG_FREE_MEM)
#	define mswTagMemDEBUG(STMT)	
#    else
#	define mswTagMemDEBUG(STMT)	STMT
#    endif

     /* NOTE: `allocSerial', etc. can be confused with a root  */
#    if defined(MSW_SERIAL_DEBUG)
        static unsigned long	allocSerialBreak = 0;
#    	define mswSerialDEBUG(STMT) 	STMT
#    else
#	define mswSerialDEBUG(STMT)
#    endif


#    define mswGcDEBUG(STMT)	if (!mswGcDebug) ; else STMT

#    if defined(MSW_CHECK_HEAP)
#    		define mswCheckDEBUG(STMT)   STMT
#    		define mswCondCheckDEBUG(STMT) if (!mswCheckDebug) ; else STMT
#    else
#		define mswCheckDEBUG(STMT)
#		define mswCondCheckDEBUG(STMT)
#    endif

#    if defined(MSW_TRACE_ONE_PAGE)
                void		mswTraceFPage(Ptr page);
                static Ptr	mswTracedPage = NULL;

#    		define mswTracePageDEBUG(pagePtr) \
                            if (pagePtr) mswTraceFPage(pagePtr)
#    else
#		define mswTracePageDEBUG(pagePtr)
#    endif

#    if defined(MSW_GET_ALLOC_SIZE_STATS)

#	define MAX_TRACED_SIZE			4000
        static unsigned long totAllocatedSizes [MAX_TRACED_SIZE];
        static unsigned long totHugeAllocated = 0;

#	define mswGetStatsDEBUG(size) \
		if ((size) < MAX_TRACED_SIZE) \
	  		totAllocatedSizes[(size)] += 1; \
		else \
                        totHugeAllocated += 1;
#    else
#    	define mswGetStatsDEBUG(size)
#    endif

#endif

/*---------------------------------------------------------------------------*
 *
 * :: Macros
 *
 *---------------------------------------------------------------------------*/


/******************************* Constants *******************************/

#define MaxFixedSize		(bytesPerPage >> 1) - 16

#define PagesRequest		10

#define PtrAlignment		sizeof(Ptr)
#define PtrSize			sizeof(Ptr)

/* FirstObjOffset is the offset of the first allocable obj in a page */
#define FirstObjOffset	       (Word) PTR_ALIGN(sizeof(PageHeaderStruct)+1, \
					        OBJ_ALIGNMENT) -1
#define AllocMask		0x1
#define MarkMask		0x3
#define FreeMask		0x0
#define OpaqueMask		0xaa
#define TransparentMask		0xbb

/* Page type: values for the page map */

#define PAGE_Free		0x0
#define PAGE_Fixed		0x1
#define PAGE_Mixed		0x2
#define PAGE_Next		0x3
#define PAGE_Other		0x4

/* Page space: values for the page space */
#define SPACE_Permanent		0
#define SPACE_Temporary		1

#define MSW_TRANSPARENT_OBJ	0
#define MSW_OPAQUE_OBJ		1

#define PageMapInitialSize	bytesPerPage * 4

#define MSW_HEAP_PAGES_INC	800

/* When using debug options a memory object is filled with EMPTY_MEM_TAG value
 * when is allocated and with RELEASED_MEM_TAG when is released during a
 * collection.
 * If there is an attempt of using a free memory object, it should be easy to
 * understand if the mem obj has been released during a collection.
 */
#define EMPTY_MEM_TAG		0xee
#define RELEASED_MEM_TAG	0xdd

#define PAGE_START(ptr)		(Ptr)((Word)(ptr) & ~(bytesPerPage - 1))

#define PTR_ALIGN(ptr, align)	\
             (Ptr)(((Word)((Ptr)(ptr)-1)+(align)) & ~((align)-1))

#define ROUND_UP(n, b)  (Word) PTR_ALIGN((n),(b))
#define ROUND_DOWN(n, b) (Word) ((Word)(n) & ~((b) -1))

#define IS_INSIDE_HEAP(p)	\
             ((Ptr)(p) < heapEnd && (Ptr)(p) >= heapStart)

#define GET_OBJ_BASE(ptr, header) 				      	\
   (Ptr)((Word)header + header->basePointerv[(Word)(ptr)-(Word)header])

#define PAGE_INFO(p)  pageMap[GCPtoPage(p)]
#define PAGE_SPACE(p) pageSpace[GCPtoPage(p)]

#define NEXT_FREE_OBJ(p)          *(Ptr *)((Ptr)(p) + 1)
#define SET_NEXT_FREE_OBJ(p, obj) *(Ptr *)((Ptr)(p) + 1) = (obj)

#define isAvailFPage(p)  (((PageHeader)(p))->nextPage != NULL)
#define isFullFPage(p)  	 (((PageHeader)(p))->freeList == NULL)
/* Address of last obj that can be allocated in "page" (fixed) */
#define GET_LAST_OBJ_PTR(pg,size) \
              (Ptr)(pg) + bytesPerPage - ((size) + OBJ_ALIGNMENT)

/* pageLink is a vector defined by CMM. Other heaps use it for other purposes.
 * Here it is renamed to pageMap because this name is more appropriate and
 * helps reading the code.
 */
#define pageMap		pageLink

// Max number of pages for a chunk (currently used for debugging only)
#define MAX_CHUNK_PAGES          50000
/*---------------------------------------------------------------------------*
 *
 * :: Type Definitions
 *
 *---------------------------------------------------------------------------*/


/****** PageHeader ******/

typedef struct pageHeaderStruct *	PageHeader;

typedef struct pageHeaderStruct {
	Word 	objSize;	/* Size of objects allocated in this page */
	Ptr *	basePointerv;
	PageHeader nextPage;	/* Next page with some free objects */
	Ptr	freeList;	/* First free obj in this page */
	int	allocatedObjs;
	int	nPages;		/* >0 only for mixed objects */
	char	isMarked;	/* The whole page is marked? */
	char	isOpaque;       /* Only for mixed objs. 1 => don't traverse */

} PageHeaderStruct;


/****** FreePageHeader ******/

typedef struct freePageHeaderStruct *	FreePageHeader;

typedef struct freePageHeaderStruct {
        FreePageHeader	nextChunk;  /* Next page of same chunk size */
	FreePageHeader	nextChunkGroup;
	int		nPages;

} FreePageHeaderStruct;

/****** FPageInfoStruct ******/

struct FPagesInfoStruct {
	Word	firstObjOffset;
	Ptr *	basePointerv;
	int	objectsPerPage;
};

/*---------------------------------------------------------------------------*
 *
 * :: TempHeap Typedef & Globals
 *
 *---------------------------------------------------------------------------*/


#define	MAX_ROOT	30

typedef struct TempHeapInfoStruct *		TempHeapInfo;

struct TempHeapInfoStruct {
	Ptr 		roots[MAX_ROOT];
	int 		nRoots;
	PageHeader	availFPages[MaxFixedSize];

	TempHeapInfo	previous;
};

static TempHeapInfo	tempHeapInfo	= NULL;
static int	mustResetTempHeap = 0;
static int	noCollection = 0;

#define mswDisableCollection()	(noCollection = 1)
#define mswEnableCollection()	(noCollection = 0)
#define mswIsCollectionDisabled() (noCollection)

/*---------------------------------------------------------------------------*
 *
 * :: MarkStack Typedef & Globals
 *
 *---------------------------------------------------------------------------*/

typedef struct MarkStackFrameStruct *      MarkStackFrame;

struct MarkStackFrameStruct {
        MarkStackFrame previous;
        MarkStackFrame next;
};

#define  MarkStackFramePages       8

#define MarkStackPush(OBJ)   \
     { *(Ptr*)markStackTop = (Ptr) (OBJ);         \
	 markStackTop += PtrSize;                \
	   if (markStackTop == markStackHeadroom)  mswExpandMarkStack(); }

#define MarkStackPop(VAR)                              \
     { if (markStackTop == markStackBase) {            \
         theMarkStack = theMarkStack->previous;        \
         markStackHeadroom = (Ptr) theMarkStack + MarkStackFramePages * bytesPerPage;   \
	 markStackTop = markStackHeadroom - PtrSize; \
	 markStackBase = (Ptr) theMarkStack + sizeof(MarkStackFrameStruct); \
     }    \
     else \
         markStackTop -= PtrSize;          \
     VAR = *(GCP *)markStackTop; }

#define MarkStackIsEmpty()  \
     (markStackTop == markStackBase && theMarkStack->previous == NULL)


static MarkStackFrame   theMarkStack;
static Ptr              markStackTop;
static Ptr              markStackHeadroom;
static Ptr              markStackBase;

/*---------------------------------------------------------------------------*
 *
 * :: Global Variables
 *
 *---------------------------------------------------------------------------*/


struct	FPagesInfoStruct	FPagesInfo	[MaxFixedSize];

static  PageHeader	availFPages   [MaxFixedSize];
static  unsigned	totFreePages = 0;

/***** freeChunks  *****/

static  FreePageHeader 	freeChunks = NULL;

static	int	totReleasedPages = 0;


/***** Memory Sections *****/

static  Ptr	stackStart;
static	Ptr	stackEnd;

static	Ptr	dataStart;
static  Ptr	dataEnd;

static  Ptr	heapStart  = (Ptr) -1;
static  Ptr	heapEnd = NULL;

extern  int	end;	/* Compiler defined, end of data segment */


/*---------------------------------------------------------------------------*
 * :: Timings
 *---------------------------------------------------------------------------*/


#if defined(MSW_SHOW_TIMINGS)

#	ifdef sgi  /* System V */
#   		include <sys/types.h>
#   		include <sys/times.h>
#	else
#   		include <sys/time.h>
#   		include <sys/resource.h>
#	endif

#	define mswShowTIME(STMT)	STMT
        static Word  mswGetCpuTime  (void);
        static Word  totMarkTime  = 0;
        static Word  totSweepTime = 0;
#else
#	define mswShowTIME(STMT)	
#endif

/*---------------------------------------------------------------------------*
 *
 * :: Local Prototypes
 *
 *---------------------------------------------------------------------------*/


static PageHeader     mswAllocFPage	       (Word size);
static Ptr  	      mswAllocChunk	       (unsigned long, unsigned);
static Ptr  	      mswAllocPages	       (int nPages, Word size);

static Ptr            mswGetPages	       (int nPages, Word size);
static PageHeader     mswSetupFPage	       (Ptr page, Word size);

static void	      mswFreeChunk	       (PageHeader);

static void	      mswAddToFreeChunksAndMap (Ptr chunk, int nPages);
static void	      mswAddToFreeChunks       (Ptr chunk, int nPages);
static Ptr	      mswGetBestFitChunk       (int nPages);
static void	      mswRemoveFromFreeChunks  (FreePageHeader chunk);

static void	      mswPageMapSetRange       (Ptr, Ptr, unsigned);
static void	      mswPageMapSet	       (Ptr, int, unsigned);
static void	      mswPageSpaceSetRange     (Ptr, Ptr);
static void	      mswPageSpaceSetRangeTo   (Ptr, Ptr, short);
static void	      mswPageSpaceSet	       (Ptr, int);

static void	      mswCheckFreeChunks       (void);

/*---------------------------------------------------------------------------*
 * :: mswSelect
 *
 * -- interface for C
 *
 *---------------------------------------------------------------------------*/

void
mswSelect()
{
  Cmm::heap = Cmm::theMSHeap;
}

/*---------------------------------------------------------------------------*
 * :: mswAlloc
 *---------------------------------------------------------------------------*/


void *
mswAlloc(unsigned long size)
{
        Ptr    	   freeList;
        PageHeader freePage;
	Ptr	   ret;

	mswSerialDEBUG({
 	    if (allocSerial++ == allocSerialBreak)
		allocSerialBreak = allocSerial; /*** PLACE A BREAKP. HERE ***/
	});

	mswTracePageDEBUG(mswTracedPage);

#	if defined(MSW_ALLOC_ZERO_OK)
	    if (size == 0) size = 4;
#	endif

	assert(size);

	size = ROUND_UP(size, PtrSize);

	mswGetStatsDEBUG(size);

	if (size >= MaxFixedSize)
		return mswAllocChunk(size, MSW_TRANSPARENT_OBJ);

	/**** allocate an object from pool(size) ****/

        freePage = availFPages[size];

	assert(freePage != NULL);
	assert(freePage->objSize == size);

	freeList = freePage->freeList;

	freePage->allocatedObjs += 1;
	*freeList = AllocMask;
	*(Byte *)(freeList-1) = TransparentMask;

	// Following assignment is needed because subsequent call to
	// mswAllocFPage might release completely "freePage".
	// This ensures that there is at least one live object.
	ret = freeList + 1;

	freePage->freeList = NEXT_FREE_OBJ(freeList);

	if (freePage->freeList == NULL
	    && (availFPages[size] = freePage->nextPage) == NULL)
	  mswAllocFPage(size);

	assert(freeList);
	assert(freePage->freeList == NULL ||
	       ((Ptr) freePage->freeList > (Ptr) freePage &&
		(Ptr) freePage->freeList < (Ptr) freePage + bytesPerPage));

	mswTracePageDEBUG(mswTracedPage);

	return ret;
}

/*---------------------------------------------------------------------------*
 * :: mswAllocOpaque
 *
 * Allocates an object that is guaranteed to do not contain pointers.
 * Useful only for big chunks, that are not traversed during the collection.
 *
 *---------------------------------------------------------------------------*/

void *
mswAllocOpaque(unsigned long size)
{
	if (size < MaxFixedSize) {
	  Ptr ret = (Ptr)mswAlloc(size);
	  *(Byte *)(ret-2) = OpaqueMask;
	  return ret;
	}
	else
	  return mswAllocChunk(size, MSW_OPAQUE_OBJ);
}

/*---------------------------------------------------------------------------*
 * :: mswAllocFPage
 *
 * Return a pointer to a free fixed list for "size".
 * The code looks obscure because mswAllocPages() can cause a collection
 * that can add pages to availFPages[].
 *---------------------------------------------------------------------------*/

static PageHeader
mswAllocFPage(Word size)
{
	Ptr    page;

	page = mswAllocPages(1, size);

	if (availFPages[size] == NULL) {
		assert(page);
		availFPages[size] = mswSetupFPage(page, size);
	}

	return availFPages[size];
}

/*---------------------------------------------------------------------------*
 * :: mswShouldExpandHeap
 *
 * Called after a GC. Return 1 if the heap should be expanded. Note that an
 * expansion might be request even if we found enough free pages after a GC.
 *---------------------------------------------------------------------------*/

#define GC_MAX_BUSY_MEM		10

static int
mswShouldExpandHeap(void)
{
	int percBusyMem;

	if (markedBytes == 0)
	    return 0;          // We didn't collect

	Word heapSize = ((Word)lastHeapPage - firstHeapPage) * bytesPerPage;

	percBusyMem = (100 * markedBytes) / heapSize;

	markedBytes = 0;

	mswDEBUG(fprintf(stdout, " %d\% busy memory ", percBusyMem););

	if (percBusyMem > GC_MAX_BUSY_MEM) {
	      mswDEBUG(fprintf(stdout, "-> expand heap\n"););
	      return 1;
        }
	else {
	      mswDEBUG(fprintf(stdout, "-> not expand heap\n"););
	      return 0;
	}
}

/*---------------------------------------------------------------------------*
 * :: mswGetPages
 *
 * Return a chunk of "nPages" consecutives pages, getting them from a
 * garbage collection or from the operating system.
 * "size" is 0 if the pages are mixed.
 * Since more than requested pages can be allocated, the remaining chunk is
 * added to freeChunks.
 * NOTE: the pageMap is updated only for extra chunks.
 * NOTE that when mswGetPages is called no chunk of "nPages" size is
 *   currently available.
 * NOTE: a NULL value is returned only if no memory is available.
 *
 *---------------------------------------------------------------------------*/


#define HAS_ENOUGH_PAGES(npages) (lastHeapPage - firstFreePage >= (npages) + 1)

static Ptr	mswExpandHeap(int);

static Ptr
mswGetPages(int nPages, Word size)
{
  Ptr            newPages;

  mswCollect();

  /* Expand anyway if not found enough free pages */
  if (mswShouldExpandHeap()) {
    newPages = mswExpandHeap(MSW_HEAP_PAGES_INC);
    mswAddToFreeChunksAndMap(newPages, MSW_HEAP_PAGES_INC);
  }

  /* Found free objects after collection? */
  if (size != 0 &&
      availFPages[size]) {
    mswDEBUG(fprintf(gcOut, "Found enough objects after gc!\n"));
    return NULL;		/* <------------ */
  }

  /* Try if the request can be satisfied after GC */
  newPages = mswGetBestFitChunk(nPages);
  /* Found a free chunk after collection ? */
  if (newPages) {
    mswDEBUG(fprintf(gcOut, "Found enough pages after gc!\n"));
    return newPages;		/* <----------- */
  }
  mswDEBUG(fprintf(gcOut, "[H]"));

  return mswExpandHeap(nPages);
}

/*---------------------------------------------------------------------------*
 * :: mswExpandHeap
 *---------------------------------------------------------------------------*/

static Ptr
mswExpandHeap(int nPages)
{
	Ptr	newPages;
	int	pagesRequest = nPages;
	int     lastPage = GCPtoPage(heapEnd) - 1;
	Word	bytesRequest;

	newPages = (Ptr) allocatePages(pagesRequest, Cmm::theMSHeap);

	bytesRequest = pagesRequest * bytesPerPage;

	/* Check that allocatePages() returns an aligned address */
	assert(newPages == PAGE_START(newPages));

	pagesRequest = bytesRequest / bytesPerPage;

 	assert(heapStart <= newPages);

	if (heapEnd < newPages) {
	        mswPageMapSetRange(heapEnd, newPages - 1, PAGE_Other);
		mswPageSpaceSetRangeTo(heapEnd,newPages-1, SPACE_Permanent);
	}

	if (heapEnd < newPages + bytesRequest)
	  heapEnd = newPages + bytesRequest;

	mswPageSpaceSet(newPages, nPages);

	return newPages;
}

/*---------------------------------------------------------------------------*
 * :: mswSetupFPages
 *---------------------------------------------------------------------------*/

static PageHeader
mswSetupFPage(Ptr page, Word size)
{
	PageHeader header = (PageHeader) page;
	Ptr        firstObj, lastObj, p;
	Word       size1 = size + OBJ_ALIGNMENT;

	assert(FPagesInfo[size].basePointerv);

	header->objSize       = size;
	header->basePointerv  = FPagesInfo[size].basePointerv;
	header->allocatedObjs = 0;
	header->nextPage      = NULL;
	header->nPages	      = 1;
	header->isMarked      = 0;

	firstObj = page + FPagesInfo[size].firstObjOffset;
	lastObj  = GET_LAST_OBJ_PTR(page, size);

	header->freeList      = firstObj;

	for (p = firstObj; p <= lastObj; p += size1) {
	  *p = 0;		/* mark and alloc info */
	  SET_NEXT_FREE_OBJ(p, p + size1); /* Next free list item */
	  mswTagMemDEBUG({
	    Ptr pd;
	    for (pd = p + 1 + sizeof(Ptr); pd < p + 1 + size; pd++)
	      *pd = EMPTY_MEM_TAG;
	  });
	}

	SET_NEXT_FREE_OBJ(p - size1, NULL);   /* Last item has no tail */

	pageMap[GCPtoPage(p)] = PAGE_Fixed;

	return header;
}

/*---------------------------------------------------------------------------*
 * :: mswRemoveAvailFPage
 *
 * NOTE: here a page is always removed because the caller will always free
 * the page.
 *---------------------------------------------------------------------------*/

static void
mswRemoveAvailFPage(PageHeader header)
{
	PageHeader page = availFPages[header->objSize];

	if (page == header) {
		availFPages[header->objSize] = header->nextPage;
		return;  /* <--------- */
	}
	/* Note: page can be NULL if in tempHeapInfo->availFPages[] */
	while (page != NULL) {
		if (page->nextPage == header) break;
		page = page->nextPage;
	}

	/* NOTE: we put following test here and not at the beginning of the
	 * function because this situation can happen only when there is a
	 * collection with a tempHeap active, so this is a very rare event.
	 */
	if (page == NULL) {
		/* Remove page from tempHeapInfo->availFPages */
		assert(tempHeapInfo);
		assert(pageSpace[GCPtoPage(header)] == SPACE_Permanent);
		page = tempHeapInfo->availFPages[header->objSize];

		if (page == header) {
			tempHeapInfo->availFPages[header->objSize] =
			    header->nextPage;
			return;  /* <--------- */
		}

		do {
			if (page->nextPage == header) break;
			page = page->nextPage;
		} while (page != NULL);
	}

	assert(page);
	page->nextPage = header->nextPage;
}

/*---------------------------------------------------------------------------*
 * :: mswFree
 *---------------------------------------------------------------------------*/

void
mswFree(void * p)
{
	PageHeader   header = (PageHeader) PAGE_START(p);
	Word         size   = header->objSize;

	mswSerialDEBUG(freeSerial += 1;);

	/* NOp when tempHeap active.
	 * !! Move first 2 assignments after this if
	 */
	if (tempHeapInfo) return;

	if (header->objSize >= MaxFixedSize) {
	        mswFreeChunk(header);
		return;				/* <-------- */
	}

	mswTracePageDEBUG(mswTracedPage);

	assert(p == GET_OBJ_BASE(p, header) + 1);
	assert((Ptr)header != p);
	assert(IS_INSIDE_HEAP(p));
	assert(header->allocatedObjs);
	header->allocatedObjs -= 1;

	/* !! Should call mswFreePage(header) if == 0; but this requires
	 * objs allocated in page-based sublists, otherwise it is not possible
	 * to remove free objs from their lists.
	 */

	if (isFullFPage(header)) {
		/* Add to the list of fixed pages having at least a free
	         * object.
		 */
		header->nextPage = availFPages[size];
	        availFPages[size] = header;
	}

	if (header->allocatedObjs == 0 &&
	    isAvailFPage(header)) {
		/* Release this page completely */
		mswRemoveAvailFPage(header);
		mswFreeChunk(header);
	}
	else {
		/* Simply add the released obj to the local freeList */
		*(Ptr *)p = header->freeList;
		p = (Ptr)p-1;
		header->freeList = (Ptr) p;
		*(Ptr)p = 0;   /* Remove allocation mark */
	}

	/* totFreeFixedMem += size; */

	mswTagMemDEBUG({
		Ptr pd;
		for (pd = (Ptr)p +1+sizeof(Ptr); pd < (Ptr)p +1+size; pd++)
		       *pd = RELEASED_MEM_TAG;
	});
}

/*---------------------------------------------------------------------------*
 * :: mswGetObjSize
 *
 * Given a pointer to an allocated object, return the size of the object.
 * Remember that, for instance, if you allocate a 20 bytes object, 24 bytes
 * are allocated.
 *---------------------------------------------------------------------------*/

unsigned long
mswGetObjSize(void * ptr)
{
	int 	   pageInfo = PAGE_INFO(ptr);
	PageHeader page     = (PageHeader) PAGE_START(ptr);

	assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed);

	return page->objSize;
}
/*---------------------------------------------------------------------------*
 * :: mswGetRealObjSize
 *
 * Given a pointer to an allocated object, return the real size of the object,
 * i.e. the amount of memory allocated for the object. The difference with
 * mswGetObjSize() is only for mixed pages.
 *
 *---------------------------------------------------------------------------*/

static unsigned long
mswGetRealObjSize(void * ptr)
{
	int 	   pageInfo = PAGE_INFO(ptr);
	PageHeader page     = (PageHeader) PAGE_START(ptr);

	assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed);

	if (pageInfo == PAGE_Fixed)
		return page->objSize;
	else
		return (page->nPages * bytesPerPage) - FirstObjOffset -1;
}

/*---------------------------------------------------------------------------*
 * :: mswRealloc
 *
 * Re-allocate a previously allocated block
 *
 *---------------------------------------------------------------------------*/

void *
mswRealloc(void * p, unsigned long size)
{
	unsigned long realSize = mswGetRealObjSize(p);
	Ptr	      newPtr;
	PageHeader    page;

	if (realSize >= size) {
		/* Size of mixed objects must be updated because during
		 * the mark phase we traverse only header->objSize bytes.
		 */
		if (PAGE_INFO(p) == PAGE_Mixed) {
			page = (PageHeader) PAGE_START(p);
			page->objSize = size;
		      }
		return p;	/* <---------- */
	}
	else {
		newPtr = (Ptr)mswAlloc(size);
		/* If obj is opaque, then keep it opaque */
		if (size < MaxFixedSize)
			*(newPtr-2) = *((Ptr)p-2);
		else {
		  PageHeader newHead = (PageHeader) ROUND_DOWN(newPtr,
							       bytesPerPage);
		  PageHeader oldHead = (PageHeader) ROUND_DOWN(p,
							       bytesPerPage);
		  newHead->isOpaque = oldHead->isOpaque;
		}
		memcpy(newPtr, p, realSize);
		mswFree(p);
		return newPtr;
	}
}

/*---------------------------------------------------------------------------*
 * :: mswCalloc(n, size)
 *
 * Allocates "n" elements of size "size", all initialized to 0.
 *
 *---------------------------------------------------------------------------*/

void *
mswCalloc(unsigned long n, unsigned long size)
{
	void * mem = mswAlloc(n * size);

	return memset(mem, 0, n * size);
}

/*---------------------------------------------------------------------------*
 *
 * :: PageMap
 *
 *---------------------------------------------------------------------------*/

/* Mark pages in ["from".."to"] with "type".
 * NOTE: "to" is included in range.
 */
static void
mswPageMapSetRange(Ptr from, Ptr to, unsigned type)
{
	Word l;
	Word h;
	register Word k;

	l = GCPtoPage(from);
	h = GCPtoPage(to);

	for (k = l; k <= h; k++)
	  pageMap[k] = type;
}

/* Mark "nPages" pages starting from "pageStart" with "type" */
static void
mswPageMapSet(Ptr pageStart, int nPages, unsigned type)
{
	int	index = GCPtoPage(pageStart);

	while (nPages--)
	  pageMap[index++] = type;
}
/*---------------------------------------------------------------------------*
 *
 * :: PageSpace
 *
 *---------------------------------------------------------------------------*/

static void
mswPageSpaceSetRange(Ptr from, Ptr to)
{
	Word l;
	Word h;
	short type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent);
	register Word k;

	l = GCPtoPage(from);
	h = GCPtoPage(to);

	for (k = l; k <= h; k++)
	  pageSpace[k] = type;
}

static void
mswPageSpaceSetRangeTo(Ptr from, Ptr to, short type)
{
	Word l;
	Word h;
	register Word k;

	assert(type == SPACE_Permanent || type == SPACE_Temporary);

	l = GCPtoPage(from);
	h = GCPtoPage(to);

	for (k = l; k <= h; k++)
	  pageSpace[k] = type;
}

static void
mswPageSpaceSet(Ptr pageStart, int nPages)
{
	int	index = GCPtoPage(pageStart);
	short	type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent);

	while (nPages--)
	  pageSpace[index++] = type;
}

static void
mswPageSpaceSetTo(Ptr pageStart, int nPages, short type)
{
	int	index = GCPtoPage(pageStart);

	assert(type == SPACE_Permanent || type == SPACE_Temporary);

	while (nPages--)
	  pageSpace[index++] = type;
}

/*---------------------------------------------------------------------------*
 *
 * :: Free Chunks Management
 *
 *---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*
 * :: mswAddToFreeChunks
 *
 * Add "chunk" to the list of free chunks. "nPages" is the chunk size.
 * NOTE: does not update pageMap[], to optimize cases in which it is already
 * 	updated. See mswAddToFreeChunksAndMap().
 *
 *---------------------------------------------------------------------------*/

static void
mswAddToFreeChunks(Ptr ptr, int nPages)
{
	FreePageHeader	chunks = freeChunks;
	FreePageHeader *pPrev  = &freeChunks;
	FreePageHeader  chunk  = (FreePageHeader) ptr;

	chunk->nPages = nPages;
	totFreePages += nPages;

	mswTagMemDEBUG({
		Ptr	p;
		Ptr     end = ptr + (nPages * bytesPerPage);
		for (p = ptr + sizeof(FreePageHeaderStruct) + 1;
		     p < end; p++)
		         *p = RELEASED_MEM_TAG;
	});

	if (!chunks) {
		chunk->nextChunk      = NULL;
		chunk->nextChunkGroup = NULL;
		freeChunks = chunk;
		return;				/* <---- */
	}

	while (chunks) {
		if (chunks->nPages == nPages) {
			*pPrev = chunk;
			chunk->nextChunk      = chunks;
			chunk->nextChunkGroup = chunks->nextChunkGroup;
			return;			/* <---- */
		}
		else if (chunks->nPages > nPages) {
			*pPrev = chunk;
			chunk->nextChunk      = NULL;
			chunk->nextChunkGroup = chunks;
			return;			/* <---- */
		}
		pPrev = &(chunks->nextChunkGroup);
		chunks = chunks->nextChunkGroup;
	}
	/* This point is reached if this is the maximum chunk.
	 * Add the chunk to the tail of the list.
	 */
	*pPrev = chunk;
	chunk->nextChunk      = NULL;
	chunk->nextChunkGroup = NULL;
}

/*---------------------------------------------------------------------------*
 * :: mswAddToFreeChunksAndMap
 *
 * As mswAddToFreeChunks(), but the pageMap[] is updated.
 *
 *---------------------------------------------------------------------------*/

static void
mswAddToFreeChunksAndMap(Ptr chunk, int nPages)
{
	mswAddToFreeChunks(chunk, nPages);
	mswPageMapSet(chunk, nPages, PAGE_Free);

	mswTagMemDEBUG({
		Ptr p = (Ptr)chunk + FirstObjOffset + 1;

		for (;p < (Ptr)chunk + nPages * bytesPerPage; p++)
		      *p = EMPTY_MEM_TAG;
	});
}

/*---------------------------------------------------------------------------*
 * :: mswBreakAndAllocChunk
 *
 * "chunk" is the block to be allocated.
 *
 *---------------------------------------------------------------------------*/

static Ptr
mswBreakAndAllocChunk(FreePageHeader chunk, FreePageHeader * pPrev, int nPages)
{
	int 	       nExtraPages;
	FreePageHeader extraChunk;

	/* Remove the chunk from the chunk list */
	if (chunk->nextChunk == NULL)
		*pPrev = chunk->nextChunkGroup;
	else {
	        *pPrev = chunk->nextChunk;
		chunk->nextChunk->nextChunkGroup = chunk->nextChunkGroup;
	}
	totFreePages -= chunk->nPages;
	if (chunk->nPages > nPages) {
		nExtraPages = chunk->nPages - nPages;
		extraChunk = (FreePageHeader)((Ptr)chunk +
					      nPages * bytesPerPage);
		mswAddToFreeChunks((Ptr)extraChunk, nExtraPages);
	}
	/* If we are in the copying phase (tempHeap ended by not destroyed)
	 * we must promote temporary pages.
	 */
	if (mustResetTempHeap)
		mswPageSpaceSet((Ptr) chunk, nPages);

	return (Ptr) chunk;
}

/*---------------------------------------------------------------------------*
 * :: mswGetBestFitChunk
 *
 * Walks through the list of free chunks finding the one that best satisfies
 * the request, returning NULL if cannot find a so big chunk.
 * If the chunk is found, it is removed from the free list. Spare pages are
 * reinserted in the free list.
 *
 *---------------------------------------------------------------------------*/

static Ptr
mswGetBestFitChunk(int nPages)
{
       FreePageHeader chunks = freeChunks;
       FreePageHeader *pPrev  = &freeChunks;

       while (chunks) {
	     if (chunks->nPages >= nPages)
	           return mswBreakAndAllocChunk(chunks, pPrev, nPages);
	     pPrev = &(chunks->nextChunkGroup);
	     chunks = chunks->nextChunkGroup;
       }
       return NULL;
}

/*---------------------------------------------------------------------------*
 * :: mswRemoveFromFreeChunks
 *---------------------------------------------------------------------------*/

static void
mswRemoveFromFreeChunks(FreePageHeader chunk)
{
       FreePageHeader chunks = freeChunks;
       FreePageHeader *pPrev  = &freeChunks;
       int	       nPages = chunk->nPages;

       totFreePages -= nPages;

       while (chunks) {
	     if (chunks->nPages == nPages) break;
	     pPrev = &(chunks->nextChunkGroup);
	     chunks = chunks->nextChunkGroup;
       }

       if (chunks == chunk) {
	       if (chunk->nextChunk) {
	       	    *pPrev = chunk->nextChunk;
		    chunk->nextChunk->nextChunkGroup = chunk->nextChunkGroup;
	       }
	       else
	       	    *pPrev = chunk->nextChunkGroup;
	       return;
       }

       do {
	       assert(chunks);
	       pPrev = &(chunks->nextChunk);
	       chunks = chunks->nextChunk;
       } while (chunks != chunk);

       assert(chunks);
       *pPrev = chunk->nextChunk;
}
/*---------------------------------------------------------------------------*
 * :: mswMergeChunkWithNeighbors
 *
 * Given a chunk that is going to be released, look at its neighbors and merge
 * it into a bigger chunk if possible.
 * Return the pointer to the new chunk and "pNPages" is updated to the new
 * size
 *
 *---------------------------------------------------------------------------*/

static Ptr
mswMergeChunkWithNeighbors(Ptr chunk, int* pNPages)
{
	int nPages    = *pNPages;
	Page baseIndex = GCPtoPage(chunk);
	Page limitIndex= GCPtoPage(heapEnd);
	Page index     = baseIndex;
	Ptr newChunk  = chunk;
	FreePageHeader followChunk;

	while (index > firstHeapPage) {
		if (pageMap[index-1] != PAGE_Free)
			break;

		nPages++;
		index--;
	}

	/* "index" is the index of the first page of the previous free chunk.*/
	if (index != baseIndex) {
		newChunk = (Ptr)pageToGCP(index);
		mswRemoveFromFreeChunks((FreePageHeader)newChunk);
	}

	index = baseIndex + *pNPages;

	/* A free chunk follows the current chunk? */
	if (index < limitIndex &&
	    pageMap[index] == PAGE_Free) {
		followChunk = (FreePageHeader) pageToGCP(index);
		nPages += followChunk->nPages;
		mswRemoveFromFreeChunks(followChunk);
	}

	*pNPages = nPages;
	return newChunk;
}

/*---------------------------------------------------------------------------*
 * :: mswAllocChunk
 *
 * Alloc a chunk of "size" bytes. A chunk is allocated only if it is bigger
 * than maximum fixed object.
 *---------------------------------------------------------------------------*/

static Ptr
mswAllocChunk(unsigned long size, unsigned type)
{
	int	nPages = (FirstObjOffset + size + bytesPerPage)
	                    / bytesPerPage;
	int     index;
	Ptr	p;

	p = mswAllocPages(nPages, 0);

	((PageHeader)p)->objSize      = size;
	((PageHeader)p)->basePointerv = NULL;
	((PageHeader)p)->nPages	      = nPages;
	((PageHeader)p)->allocatedObjs= 1;
	((PageHeader)p)->isMarked     = 0;
	((PageHeader)p)->isOpaque     = (type == MSW_OPAQUE_OBJ);

	/* Mark pages in pageMap */
	index = GCPtoPage(p);
	pageMap[index] = PAGE_Mixed;

	while (--nPages)
	  pageMap[++index] = PAGE_Next;

	return p + FirstObjOffset + 1;
}

/*---------------------------------------------------------------------------*
 * :: mswAllocPages(nPages, size)
 *
 * Alloc "nPages" consecutive pages from freeChunks; if no available chunk
 * can satisfy the request, mswGetPages() is called.
 * "size" is 0 if the page is for mixed objects, else the size of fixed
 * objects. This value is passed to mswGetPages() to decide if
 * we have enough room after a collection.
 *
 *---------------------------------------------------------------------------*/

static Ptr
mswAllocPages(int nPages, Word size)
{
	Ptr page = mswGetBestFitChunk(nPages);

	if (page == NULL)
		page = mswGetPages(nPages, size);

	if (tempHeapInfo && page) {
		int pg = GCPtoPage(page);
		int lastPg = pg + nPages;
		do
			pageSpace[pg++] = SPACE_Temporary;
		while (pg != lastPg);
	}

	return page;
}

/*---------------------------------------------------------------------------*
 * :: mswQuickFreeChunk
 *
 * Free a chunk of "totReleasedPages" preceding "p".
 * Used during sweep phase. A global variable is used because of efficiency
 * required.
 * Details: When a fixed page or a group of mixed pages is released during
 * sweep phase we avoid an expensive call to mswFreeChunk(), but we count the
 * number of consecutive pages (totReleasedPages) and as soon as we find a
 * page that is not released we call mswQuickFreeChunk() to release the
 * whole chunk of consecutive pages.
 *---------------------------------------------------------------------------*/

static void
mswQuickFreeChunk(Ptr p)
{
	assert(totReleasedPages != 0);

	p = p - (totReleasedPages * bytesPerPage);
	mswPageMapSet(p, totReleasedPages, PAGE_Free);
	if (tempHeapInfo)
	    mswPageSpaceSetTo(p, totReleasedPages, SPACE_Permanent);

	p = mswMergeChunkWithNeighbors(p, &totReleasedPages);

	/* Add to freeChunks */
	mswAddToFreeChunks(p, totReleasedPages);
	totReleasedPages = 0;
}
/*---------------------------------------------------------------------------*
 * :: mswFreeChunk
 *
 * Implementation Note: the page map is marked before the chunk is merged.
 * This because if the chunk will be merged, its neighbor(s) are already
 * marked with PAGE_Free.
 *---------------------------------------------------------------------------*/

static void
mswFreeChunk(PageHeader header)
{
	int 	nPages = header->nPages;

	assert(nPages > 0 && nPages < MAX_CHUNK_PAGES);

	mswPageMapSet((Ptr)header, nPages, PAGE_Free);
	assert(tempHeapInfo == NULL);
//	if (tempHeapInfo)
//	    mswPageSpaceSetTo((Ptr)header, nPages, SPACE_Permanent);

	header = (PageHeader) mswMergeChunkWithNeighbors((Ptr)header, &nPages);

	/* Add to freeChunks */
	mswAddToFreeChunks((Ptr) header, nPages);
}

/*---------------------------------------------------------------------------*
 *
 * :: Mark and Sweep
 *
 *---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*
 * :: mswMark
 *---------------------------------------------------------------------------*/

static void		mswMarkFromTo(GCP from, GCP to);
static void		mswExpandMarkStack(void);
extern char **		environ;

static void
mswMark(void)
{
	jmp_buf regs;
	int	dummy = 0;
	static  void * mmenv = NULL;

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

	if (!mmenv)
#		if defined(STACKBOTTOM)
	                 mmenv = (void *)((char *)STACKBOTTOM-1);
#		else
	                 mmenv = environ;
#		endif

	stackStart = (Ptr) mmenv;
	stackEnd = (Ptr) &dummy;

	if (stackStart > stackEnd) {
		Ptr tmp = stackStart;
		stackStart = stackEnd;
		stackEnd  = tmp;
	}

	mswVERBOSE(markedBytes = 0;);

	mswMarkFromTo((GCP)stackStart, (GCP)stackEnd);
	mswGcDEBUG(fprintf(gcOut, " (%lu marked from stack)", markedBytes););
	CmmExamineStaticAreas(mswMarkFromTo);
}

unsigned maxDepth = 0;
unsigned currDepth = 0;

#ifdef MSW_RECURSIVE_MARK

static void
mswMarkFromTo(GCP from, GCP to)
{
	GCP			pt;
	Ptr			p;
	Ptr			bp;
	static PageHeader	header;

	assert(from < to);

	for (pt = from; pt < to; pt++) {
	  p = *(Ptr *)pt;
	  if (! IS_INSIDE_HEAP(p)) continue;

	  switch (PAGE_INFO(p)) {

	  case PAGE_Fixed:

	    header = (PageHeader) PAGE_START(p);

	    bp = GET_OBJ_BASE(p, header);

	    /* Consider only allocated objs not marked. */
	    if (*bp != AllocMask) continue;

	    /* Mark this object */
	    *bp = MarkMask;
	    mswVERBOSE(markedBytes += header->objSize;);

	    /* Mark this page */
	    header->isMarked = 1;

	    /* If opaque, don't traverse it */
	    assert(*(bp-1) == OpaqueMask ||
		   *(bp-1) == TransparentMask);

	    if (*(Byte *)(bp-1) == OpaqueMask)
	      continue;

	    mswMarkFromTo((GCP)(bp+1),
			  (GCP)(bp + header->objSize +1));
	    break;

	  case PAGE_Mixed:
	    p = (Ptr) ROUND_DOWN(p, bytesPerPage);
	  LAB_PageMixed:
	    /* Here `p' must point to the top of the page */

	    if (((PageHeader)p)->isMarked) continue;

	    header = (PageHeader) p;
	    /* Mark the whole page */
	    header->isMarked = 1;
	    mswVERBOSE(markedBytes += header->nPages * bytesPerPage;);

	    /* If opaque, don't traverse it */
	    if (((PageHeader)p)->isOpaque) continue;
			
	    p += FirstObjOffset + 1;

	    mswMarkFromTo((GCP)p, (GCP)(p + header->objSize));
	    break;

	  case PAGE_Next:
	    int index = GCPtoPage(p) - 1;
	    while (pageMap[index] != PAGE_Mixed) {
	      index -= 1;
	      assert(index > 0);
	    }
	    p = (Ptr)pageToGCP(index);
	    goto LAB_PageMixed;
	  }
	}
}
#elif MSW_BREAD_FIRST

static void
mswMarkFromTo(GCP from, GCP to)
{
  GCP			pt;
  Ptr			p;
  Ptr			bp;
  static PageHeader	header;

  assert(from < to);

 Mark_Loop:

  for (pt = from; pt < to; pt++) {
    p = *(Ptr *)pt;
    if (! IS_INSIDE_HEAP(p)) continue;

    switch(PAGE_INFO(p)) {

    PAGE_Fixed:
      header = (PageHeader) PAGE_START(p);

      bp = GET_OBJ_BASE(p, header);

      /* Consider only allocated objs not marked. */
      if (*bp != AllocMask) continue;
		
      /* Mark this object */
      *bp = MarkMask;
      markedBytes += header->objSize;
		
      /* Mark this page */
      header->isMarked = 1;
		
      /* If opaque, don't traverse it */
      assert(*(bp-1) == OpaqueMask ||
	     *(bp-1) == TransparentMask);
		
      if (*(Byte *)(bp-1) == OpaqueMask)
	continue;
		
      MarkStackPush((GCP)(bp+1));

    PAGE_Mixed:
      p = (Ptr) ROUND_DOWN(p, bytesPerPage);
    LAB_PageMixed:
      /* Here `p' must point to the top of the page */

      if (((PageHeader)p)->isMarked) continue;

      header = (PageHeader) p;
      /* Mark the whole page */
      header->isMarked = 1;
      markedBytes += header->nPages * bytesPerPage;

      /* If opaque, don't traverse it */
      if (((PageHeader)p)->isOpaque) continue;
			
      p += FirstObjOffset + 1;
		
      MarkStackPush((GCP)(bp+1));

    PAGE_Next:
      int index = GCPtoPage(p) - 1;
      while (pageMap[index] != PAGE_Mixed) {
	index -= 1;
	assert(index > 0);
      }
      p = (Ptr)pageToGCP(index);
      goto LAB_PageMixed;
    }
    assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other);
		
    if (MarkStackIsEmpty())
      return;			// <<-------------

    MarkStackPop(from);
    assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other);
    assert(IS_INSIDE_HEAP(from));
    to = from + PageHeader(PAGE_START(from))->objSize;
    goto Mark_Loop;
  }
}

#else				// DEPTH-FIRST

static void
mswMarkFromTo(GCP from, GCP to)
{
  GCP			pt;
  Ptr			p;
  Ptr			bp;
  static PageHeader	header;

  assert(from < to);

 Mark_Loop:

  for (pt = from; pt < to; pt++) {
    p = *(Ptr *)pt;
    if (! IS_INSIDE_HEAP(p)) continue;

    switch (PAGE_INFO(p)) {

    case PAGE_Fixed:
      header = (PageHeader) PAGE_START(p);
      bp = GET_OBJ_BASE(p, header);

      /* Consider only allocated objs not marked. */
      if (*bp != AllocMask) continue;

      /* Mark this object */
      *bp = MarkMask;
      markedBytes += header->objSize;

      /* Mark this page */
      header->isMarked = 1;

      /* If opaque, don't traverse it */
      assert(*(bp-1) == OpaqueMask ||
	     *(bp-1) == TransparentMask);

      if (*(Byte *)(bp-1) == OpaqueMask)
	continue;

      MarkStackPush(pt+1);
      MarkStackPush(to);

      from = (GCP)(bp+1);
      to = (GCP)(bp + header->objSize +1);
      goto Mark_Loop;

    case PAGE_Mixed:
      p = (Ptr) ROUND_DOWN(p, bytesPerPage);
    LAB_PageMixed:
      /* Here `p' must point to the top of the page */

      if (((PageHeader)p)->isMarked) continue;

      header = (PageHeader) p;
      /* Mark the whole page */
      header->isMarked = 1;
      markedBytes += header->nPages * bytesPerPage;

      /* If opaque, don't traverse it */
      if (((PageHeader)p)->isOpaque) continue;

      p += FirstObjOffset + 1;

      MarkStackPush(pt+1);
      MarkStackPush(to);

      from = (GCP) p;
      to = (GCP) (p + header->objSize);
      goto Mark_Loop;

    case PAGE_Next:
      {
	int index = GCPtoPage(p) - 1;
	while (pageMap[index] != PAGE_Mixed) {
	  index -= 1;
	  assert(index > 0);
	}
	p = (Ptr)pageToGCP(index);
	goto LAB_PageMixed;
      }
    }
  }
  assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other);

  if (MarkStackIsEmpty())
    return;			// <<-------------

  MarkStackPop(to);
  MarkStackPop(from);

  assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other);
  goto Mark_Loop;
}

#endif				/* MSW_RECURSIVE_MARK */


/*---------------------------------------------------------------------------*
 * :: mswExpandMarkStack()
 *---------------------------------------------------------------------------*/

static void
mswExpandMarkStack()
{
  MarkStackFrame newFrame;

  if (theMarkStack->next == NULL) {
    newFrame = (MarkStackFrame) mswGetPages(MarkStackFramePages, 0);
    theMarkStack->next = newFrame;
    newFrame->previous = theMarkStack;
    newFrame->next = NULL;
    mswPageMapSet((Ptr) newFrame, MarkStackFramePages, PAGE_Other);
  }
  else
    newFrame = theMarkStack->next;

  theMarkStack = newFrame;

  markStackTop = (Ptr) theMarkStack + sizeof(MarkStackFrameStruct);
  markStackHeadroom = (Ptr) theMarkStack + MarkStackFramePages  * bytesPerPage;
  markStackBase = markStackTop;
}

/*---------------------------------------------------------------------------*
 * :: mswSweep functions
 *---------------------------------------------------------------------------*/

static void
mswSweepFPage(Ptr page)
{
  Word	size = ((PageHeader)page)->objSize;
  Ptr	p;
  Word	size1 = size + OBJ_ALIGNMENT;
  int	released = 0;
  Ptr	lo = page + FPagesInfo[size].firstObjOffset;
  Ptr	hi = GET_LAST_OBJ_PTR(page, size);
  Ptr	fixedFreeList = ((PageHeader)page)->freeList;
  int	wasFull = (fixedFreeList == NULL);

	
  if (((PageHeader)page)->isMarked == 0) {
    if (!isFullFPage(page))
      /* A full page cannot be available */
      mswRemoveAvailFPage((PageHeader)page);
    totReleasedPages += 1;
    mswVERBOSE(totFreeFPages += 1;);
    mswVERBOSE(sweptBytes += bytesPerPage;);
    return;			/* <-------- */
  }
  else
    ((PageHeader)page)->isMarked = 0;

  for (p = lo; p <= hi; p += size1) {
    if (*p == (MarkMask | AllocMask)) {
      *p = AllocMask;
      continue;
    }
    /* Found a free obj */
    if (*p == FreeMask) {
      mswDEBUG(totFreeFixedMem += size;);
      continue;
    }
	
    assert(*p == AllocMask);
    *p = FreeMask;
    *(Ptr *)(p+1) = fixedFreeList;
    mswTagMemDEBUG({
      Ptr pd;
      for (pd = p + 1 + sizeof(Ptr);
	   pd < p + 1 + size; pd++)
	*pd = EMPTY_MEM_TAG;
    });
	
    fixedFreeList = p;
    released += 1;
    mswDEBUG(totFreeFixedMem += size;);
  }

  if (wasFull && released != 0) {
    if (tempHeapInfo &&
	PAGE_SPACE(page) == SPACE_Permanent) {
      ((PageHeader)page)->nextPage =
	tempHeapInfo->availFPages[size];
      tempHeapInfo->availFPages[size] = (PageHeader)page;
    }
    else {
      ((PageHeader)page)->nextPage = availFPages[size];
      availFPages[size] = (PageHeader)page;
    }
  }
  ((PageHeader)page)->freeList = fixedFreeList;
  ((PageHeader)page)->allocatedObjs -= released;

  if (((PageHeader)page)->allocatedObjs == 0 &&
      (isAvailFPage(page))) {
    mswRemoveAvailFPage((PageHeader)page);
    totReleasedPages += 1;
  }
  else if (totReleasedPages)
    mswQuickFreeChunk(page);

  assert(((PageHeader)page)->allocatedObjs >= 0);
  mswDEBUG({ sweptBytes += released * size;
	       if (((PageHeader)page)->allocatedObjs == 0)
		 totFreeFPages += 1;
	     });
}

/*---------------------------------------------------------------------------*
 * :: mswSweep
 *---------------------------------------------------------------------------*/

static void
mswSweep()
{
  Ptr		page;
  unsigned	pageInfo;
  PageHeader	header;
  int		i;

  totReleasedPages = 0;

  for (page = heapStart; page < heapEnd; page += bytesPerPage) {
    pageInfo = PAGE_INFO(page);
    if (pageInfo == PAGE_Fixed)
      mswSweepFPage(page);
    else if (pageInfo == PAGE_Mixed) {
      header = (PageHeader)page;
      /* Sweep mixed page */
      if (header->isMarked) {
		header->isMarked = 0;
		if (totReleasedPages)
		  mswQuickFreeChunk(page);
      }
      else {
	mswVERBOSE(sweptBytes += header->nPages * bytesPerPage;);
	totReleasedPages += header->nPages;
      }
      page += (header->nPages - 1) * bytesPerPage;
    }
    else {
      assert(pageInfo == PAGE_Free ||
	     pageInfo == PAGE_Other);
      if (totReleasedPages)
	mswQuickFreeChunk(page);
    }
  }
  if (totReleasedPages)
    mswQuickFreeChunk(page);

  /* Arrange availFPages[] so that there is no empty list */
  for (i = PtrSize; i < MaxFixedSize; i += PtrSize)
    if (availFPages[i] == NULL)
      availFPages[i] = mswAllocFPage(i);
}


/*---------------------------------------------------------------------------*
 * :: mswMarkAndSweep
 *---------------------------------------------------------------------------*/

static void
mswMarkAndSweep(void)
{
  mswDEBUG(Word	time1);
  mswDEBUG(Word	time2);

  mswVERBOSE({
    markedBytes = 0;
    sweptBytes = 0;
    totFreeFPages = 0;
  });

  mswShowTIME({ time1 = mswGetCpuTime(); });
	
  mswMark();			/********* Mark Phase *********/

  mswDEBUG({
    fprintf(gcOut, ".");
    fflush(gcOut);
  });

  mswShowTIME({
    time2 = mswGetCpuTime();
    totMarkTime += (time2 - time1);
    fprintf(gcOut, "[Mark: %lu msec.]", time2 - time1);
  });

  mswSweep();			/********* Sweep Phase *********/

  mswShowTIME({
    Word time3 = mswGetCpuTime() - time2;
    totSweepTime += time3;
    fprintf(gcOut, "[Sweep: %lu msec.]", time3);
  });
}

/*---------------------------------------------------------------------------*
 * :: mswCollectNow
 *
 * Unconditional GC.
 *
 *---------------------------------------------------------------------------*/

void
mswCollectNow()
{
  if (mswIsCollectionDisabled()) return;
  mswDEBUG({ totFreeFixedMem = 0;
	     collectSerial += 1;
	     fprintf(gcOut, "#%lu: ", collectSerial);
	   });
  mswDisableCollection();
  mswCondCheckDEBUG(mswCheckHeap(0););

  mswDEBUG({
    fprintf(gcOut, "[Garbage collection..");
    fflush(gcOut);
  });
  mswMarkAndSweep();
  mswEnableCollection();
  mswDEBUG(fprintf(gcOut, "done.]\n"););

  mswVERBOSE({
    fprintf(gcOut, "Marked %lu bytes, Reclaimed %lu bytes\n",
	    markedBytes, sweptBytes);
    fprintf(gcOut, "Tot. %u free pages (%u tot.) (%u from fixed)\n",
	    totFreePages,
	    (unsigned)(lastHeapPage - firstHeapPage),
	    totFreeFPages);
  });
  mswCondCheckDEBUG(mswCheckHeap(0););
}

/*---------------------------------------------------------------------------*
 * :: mswCollect
 *
 * Conditional GC. Collect only if (heapSize > gcThreshold) and there is not
 * enough free memory.
 *---------------------------------------------------------------------------*/

void
mswCollect()
{
  Word heapSize = (lastHeapPage - firstHeapPage) * bytesPerPage;

  if (heapSize < (Word)Cmm::gcThreshold)
    ; // mswDEBUG(fprintf(gcOut, "heap size < gc threshold: skipping GC\n"));
  else {
    mswDEBUG(fprintf(gcOut, "Calling GC...\n"););
    mswCollectNow();
  }
}

/*---------------------------------------------------------------------------*
 *
 * :: MarkAndSweep()
 *
 *---------------------------------------------------------------------------*/

MarkAndSweep::MarkAndSweep()
{
	int 	i, j, k;
	Word	firstObjOff, bp = 0;
	Word	lastObjOff;
	Word    size1, counter;

	Cmm::theMSHeap = this;	// needed for allocatePages()

	freeChunks = NULL;

	stackStart = (Ptr) &i;

	/* This loop fills FPagesInfo[] vector, that is a vector
	 * containing information about each fixed size.
	 * This information will be shared among all the fixed pages for the
	 * same size.
	 */
	for (i = PtrSize; i < MaxFixedSize; i += PtrSize) {
	  firstObjOff = FirstObjOffset;
	  FPagesInfo[i].firstObjOffset = firstObjOff;
	  FPagesInfo[i].basePointerv = (Ptr *)
	    malloc(sizeof(Ptr) * bytesPerPage);

	  for (j = 0; (Word)j < firstObjOff; j++)
	    FPagesInfo[i].basePointerv[j] = 0;

	  size1 = i + OBJ_ALIGNMENT;
	  counter = 0;

	  /* Compute the basePointer[] vector for size `i'.
	   * basePointer[] can be used to access, given the page
	   * offset of a pointer, to the base of the object.
	   * NOTE that the base of an object is the word containing
	   * the alloc/mark info, not the real start of the object,
	   * that will be one word after.
	   */
	  for (j = firstObjOff;
	       j < (int)(GET_LAST_OBJ_PTR(NULL, i) + size1);
	       j++) {

	    if (counter == 0) {
	      if ((Word)j > bytesPerPage - size1) /* PATCH BEGIN */
		bp = 0;
	      else
		bp = (Word) j;            /* PATCH END */

	      counter = size1 - 1;

	      /* Faith fake pointers: a pointer will not be
	       * traced if is pointing to an object header.
	       */
	      for (k = j - OBJ_ALIGNMENT + 1; k <= j; k++)
		FPagesInfo[i].basePointerv[k] = NULL;
	      continue;
	    }
	    else	
	      counter--;

	    FPagesInfo[i].basePointerv[j] = (Ptr) bp;
	  }
	  for (k = j; j < bytesPerPage; j++)
	    FPagesInfo[i].basePointerv[k] = NULL;

	  lastObjOff= bytesPerPage - size1 - firstObjOff;
	  FPagesInfo[i].objectsPerPage =
	    (lastObjOff - firstObjOff) / size1;
	}

	CmmHeap::init();
	heapStart = (Ptr)pageToGCP(firstHeapPage);
	heapEnd   = heapStart;

	for (i = PtrSize; i < MaxFixedSize; i += PtrSize)
	  availFPages[i] = mswAllocFPage(i);

	/* Initialize MarkStack */

	theMarkStack = (MarkStackFrame) mswGetPages(MarkStackFramePages, 0);
	theMarkStack->previous = NULL;
	theMarkStack->next = NULL;
	markStackBase = (Ptr)theMarkStack +sizeof(struct MarkStackFrameStruct);
	markStackHeadroom = (Ptr)theMarkStack +
	    MarkStackFramePages * bytesPerPage;
	markStackTop = markStackBase;

	mswPageMapSet((Ptr) theMarkStack, MarkStackFramePages, PAGE_Other);
}

/*---------------------------------------------------------------------------*
 *
 * -- MarkAndSweep::scanRoots(int page)
 *
 * Promotes pages referred by any allocated object inside "page".
 * (Should be) Used by DefaultHeap to identify pointers from MarkAndSweep
 *
 *---------------------------------------------------------------------------*/

static void	scanFPageRoots(PageHeader);
static void	scanMixedPageRoots(PageHeader);

void
MarkAndSweep::scanRoots(Page page)
{
	unsigned pageInfo = PAGE_INFO(page);
	PageHeader header = (PageHeader)pageToGCP(page);

	// Note: here we ignore PAGE_Next because those pages are
	// traversed when the PAGE_Mixed (i.e. the header) is reached.

	if (pageInfo == PAGE_Fixed) {
	  int 	size = header->objSize;
	  Word	size1 = size + OBJ_ALIGNMENT;
	  Ptr	obj;
	  long*	ptr;
	  Ptr	lo = (Ptr)header + FPagesInfo[size].firstObjOffset;
	  Ptr	hi = GET_LAST_OBJ_PTR(header, size);
	
	  for (obj = lo; obj <= hi; obj += size1) {
	    if (*obj != AllocMask)
	      continue;		// <----

	    for (ptr = (long*) obj + 1 + sizeof(Ptr);
		 ptr < (long*) obj + 1 + size; ptr++)
	      promotePage((GCP)ptr);
	  }
	} else if (pageInfo == PAGE_Mixed) {
	  long*	ptr;
	  long* end;
	
	  if (header->isOpaque) return; // <----
	
	  end = (long*) FirstObjOffset + 1 + header->objSize;
	
	  for (ptr = (long*) FirstObjOffset + 1; ptr < end; ptr++)
	    promotePage((GCP)ptr);
	}
}

/*---------------------------------------------------------------------------*
 * :: mswRegisterRoot
 *---------------------------------------------------------------------------*/

void
mswRegisterRoot(void * p)
{
	if (tempHeapInfo->nRoots == MAX_ROOT) {
	  fprintf(stderr, "Too many roots...\n");
	  exit(-1);
	}
	tempHeapInfo->roots[tempHeapInfo->nRoots++] = (Ptr) p;
}

/*---------------------------------------------------------------------------*
 *
 * :: TempHeap
 *
 *---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*
 * :: mswTempHeapFreePages
 *
 * Releases every page --EXCEPT ones marked PAGE_Other-- from
 * tempHeapInfo->firstPage up to heapEnd. Uses mswQuickFreeChunk().
 * When this function is called:
 * 	- every PAGE_Other and PAGE_Free must be SPACE_Permanent
 *	- every allocated page can be either SPACE_Permanent or SPACE_Temporary
 *
 *---------------------------------------------------------------------------*/

static void
mswTempHeapFreePages(void)
{
	Page	page;
	totReleasedPages = 0;

	/* NOTE: the following loop is ugly because optimized */

	for (page = firstHeapPage; page < lastHeapPage; page++) {
	  if (pageSpace[page] == SPACE_Permanent) {
	    if (totReleasedPages)
	      mswQuickFreeChunk((Ptr)pageToGCP(page));
	    page += 1;
	    while (page < lastHeapPage &&
		   pageSpace[page] == SPACE_Permanent)
	      page += 1;
	    if (page != lastHeapPage) {
	      totReleasedPages += 1;
	      pageSpace[page] = SPACE_Permanent;
	    }
	  }
	  else {
	    totReleasedPages += 1;
	    pageSpace[page] = SPACE_Permanent;
	  }
	}
	if (totReleasedPages)
	  mswQuickFreeChunk((Ptr)pageToGCP(page));
}

/*---------------------------------------------------------------------------*
 * :: mswTempHeapStart
 *
 * Freezes availFPages[] and resets it, such that everything is
 * allocated into the new space.
 *---------------------------------------------------------------------------*/

void
mswTempHeapStart()
{
#ifndef MSW_NO_TEMPHEAP
	int	i;
	TempHeapInfo prev = tempHeapInfo;

	tempHeapInfo =
	  (TempHeapInfo) mswAlloc(sizeof(struct TempHeapInfoStruct));

	tempHeapInfo->previous = prev;
	tempHeapInfo->nRoots = 0;

	mswDisableCollection();

	for (i = PtrSize; i < MaxFixedSize; i += PtrSize) {
	  tempHeapInfo->availFPages[i] = availFPages[i];
	  availFPages[i] = NULL;
	  availFPages[i] = mswAllocFPage(i);
	}
	mswEnableCollection();
#endif // ! MSW_NO_TEMPHEAP
}

/*---------------------------------------------------------------------------*
 * :: mswTempHeapEnd
 *---------------------------------------------------------------------------*/

void
mswTempHeapEnd()
{
#ifndef MSW_NO_TEMPHEAP
	TempHeapInfo	tmp;
	int		i;

	assert(tempHeapInfo);
	mswCondCheckDEBUG(mswCheckHeap(0));

	mswDisableCollection();
	for (i = PtrSize; i < MaxFixedSize; i += PtrSize)
	  availFPages[i] = tempHeapInfo->availFPages[i];

	tmp = tempHeapInfo;
	tempHeapInfo = tempHeapInfo->previous;
	mswFree(tmp);
	mustResetTempHeap = 1;

	for (i = PtrSize; i < MaxFixedSize; i += PtrSize) {
	  if (availFPages[i] == NULL)
	    availFPages[i] = mswAllocFPage(i);
	}
#endif // ! MSW_NO_TEMPHEAP
}

void
mswTempHeapFree()
{
#ifndef MSW_NO_TEMPHEAP
	mswTempHeapFreePages();
	mustResetTempHeap = 0;
	mswEnableCollection();
	mswCondCheckDEBUG(mswCheckHeap(0));
#endif
}

/*---------------------------------------------------------------------------*
 *
 * :: Timings
 *
 *---------------------------------------------------------------------------*/

#ifdef MSW_SHOW_TIMINGS

static Word
mswGetCpuTime(void)
{
#   ifdef sgi			/* System V */
	struct tms timebuf;
	Word r;

	times(&timebuf);
	r = timebuf.tms_utime * 100;
	return r/6;
#   else
	struct rusage rusage;
	getrusage (RUSAGE_SELF, &rusage);
	return (rusage.ru_utime.tv_sec*1000 + rusage.ru_utime.tv_usec/1000
		+ rusage.ru_stime.tv_sec*1000 + rusage.ru_stime.tv_usec/1000);
#   endif
}

#endif				/* MSW_SHOW_TIMINGS */

/*---------------------------------------------------------------------------*
 * :: mswShowInfo
 *---------------------------------------------------------------------------*/

void
mswShowInfo(void)
{
	fprintf(gcOut,
		"-------------------- MSW Collector ------------------\n\n");
	mswDEBUG(fprintf(gcOut, "+++ Debug version +++\n"););
	fprintf(gcOut, "Alignment = %d\n", OBJ_ALIGNMENT);
	fprintf(gcOut, "Max heap size = %lu Kbytes\n",
		(unsigned long) (heapEnd - heapStart) / 1024);
	fprintf(gcOut, "Page size = %lu\n", bytesPerPage);

	mswShowTIME({
	  fprintf(gcOut, "Tot. Mark Time = %lu msec.\n", totMarkTime);
	  fprintf(gcOut, "Tot. Sweep Time = %lu msec.\n", totSweepTime);
	});
}


/*---------------------------------------------------------------------------*
 *
 * :: Debug
 *
 *---------------------------------------------------------------------------*/

#ifndef NDEBUG

void
mswShowMem(void)
{
	int base = GCPtoPage(heapStart);
	int top  = GCPtoPage(heapEnd);
	int i;
	int j = 0;
	char c;
	const int pagesPerLine = 72;

	fprintf(gcOut,
		"+++++ (. = Free, # = Fixed, B/b = BigObj, O = Other) ++++");

	for (i = base; i < top; i++) {
	  if (j == 0) {
	    fprintf(gcOut, "\n%05d: ", i);
	    j = pagesPerLine;
	  }
	  j -= 1;

	  switch (pageMap[i]) {
	  case PAGE_Free: c = '.'; break;
			case PAGE_Fixed: c = '#'; break;
			case PAGE_Mixed: c = 'B'; break;
			case PAGE_Next: c = 'b'; break;
			case PAGE_Other: c = 'O'; break;
			default:
			  assert(-1);
			}
	  fputc(c, gcOut);
	}
	fprintf(gcOut, "\n");
}

void
mswShowTempMem(void)
{
	int base = GCPtoPage(heapStart);
	int top  = GCPtoPage(heapEnd);
	int i;
	int j = 0;
	char c;
	const int pagesPerLine = 72;

	fprintf(gcOut,
		"+++++ (T = Temporary, - = Permanent) ++++");

	for (i = base; i < top; i++) {
	  if (j == 0) {
	    fprintf(gcOut, "\n%05d: ", i);
	    j = pagesPerLine;
	  }
	  j -= 1;

	  if (pageSpace[i] == SPACE_Temporary)
	    c = 'T';
	  else
	    c = '_';

	  fputc(c, gcOut);
	}
	fprintf(gcOut, "\n");
}

void
mswShowFreeChunks(void)
{
	FreePageHeader	l = freeChunks;
	FreePageHeader	l1;

	fprintf(gcOut, "+++ Free chunks: \n");
	while (l) {
	  fprintf(gcOut, "> %d pages chunks: ", l->nPages);
	  l1 = l;
	  while (l1) {
	    fprintf(gcOut, "[%x]", (unsigned) l1);
	    l1 = l1->nextChunk;
	  }
	  fprintf(gcOut, "\n");
	  l = l->nextChunkGroup;
	}
	fprintf(gcOut, "--- free chunks end\n");
}

/*---------------------------------------------------------------------------*
 * ::maxObjsInOnePage
 *
 * Used by mswShowFragmentation(). Returns the max number of fixed objs of
 * size "size" that can fit in one page.
 *
 *---------------------------------------------------------------------------*/

static int
maxObjsInOnePage(int size)
{
	return (bytesPerPage - sizeof(PageHeaderStruct))
	  / (size + OBJ_ALIGNMENT);
}

/*---------------------------------------------------------------------------*
 * ::mswShowFragmentation
 *
 * Calculates fragmentation for each fixed size.
 *---------------------------------------------------------------------------*/

void
mswShowFragmentation()
{
	double 	realUse;
	double 	totRealUse = 0.0;
	int	totAnalized = 0;
	int 	i, totObjs, totPages, minPages;
	int     wastedPages = 0;
	PageHeader pages;

	for (i = PtrSize; i < MaxFixedSize; i += PtrSize) {
	  pages = availFPages[i];

	  /* Show only significant data */
	  if (pages == NULL ||
	      pages->nextPage == NULL) {
	    if (pages && pages->allocatedObjs == 0)
	      wastedPages += 1;
	    totRealUse += 100.0;
	    totAnalized += 1;
	    continue;			/* <------------- */
	  }
	
	  totObjs = 0;
	  totPages = 0;

	  while (pages) {
	    totObjs += pages->allocatedObjs;
	    totPages += 1;
	    pages = pages->nextPage;
	  }
	  minPages = 1 + (totObjs / maxObjsInOnePage(i));
	  realUse = (100.0 * (double) minPages) / (double) totPages;
	  totRealUse +=  realUse;
	  totAnalized += 1;
	  fprintf(gcOut, "Pages[%d] used at %2.4g%% ", i, realUse);
	  fprintf(gcOut, "(%d objs in %d pages, %d min pages, -> %d pg wasted)\n",
		  totObjs, totPages, minPages, totPages - minPages);
	  wastedPages += (totPages - minPages);
	}
	if (totAnalized)
	  fprintf(gcOut, "\nTot: fixed pages used at %2.4g%%. Tot. %d/%d wasted pages.\n",
		  totRealUse / (double) totAnalized, wastedPages,
		  lastHeapPage - firstHeapPage);
	else
	  fprintf(gcOut, "No fragmentation for fixed objs.\n");
}

/*---------------------------------------------------------------------------*
 * :: Heap Checking Functions
 *---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*
 * ::mswIsInAvailFPages
 *
 * Returns 0 if "page" is not in "pages", else 1.
 *
 *---------------------------------------------------------------------------*/

static int
mswIsInAvailFPages(PageHeader page, PageHeader pages)
{
	while (pages) {
	  if (pages == page) return 1;
	  pages = pages->nextPage;
	}
	return 0;
}

/*---------------------------------------------------------------------------*
 * ::mswCheckPageIsFixed
 *
 * Check that "page" looks like a fixed page.
 *
 *---------------------------------------------------------------------------*/

static void
mswCheckPageIsFixed(Ptr page)
{
	PageHeader header = (PageHeader) page;
	PageHeader pg;
	Word	 size  = header->objSize;

	assert(size > 0 && size < MaxFixedSize);
	assert(size == ROUND_UP(size, PtrAlignment));
	assert(header->basePointerv);
	assert(header->allocatedObjs <= bytesPerPage / (size+1));
	assert(header->freeList == NULL ||
	       (header->freeList > (Ptr) header &&
		header->freeList < (Ptr) header + bytesPerPage));

	if (header->freeList) {
	  /* If there is at least a free object, check that this page
	   * is among availables pages.
	   */
	  pg = availFPages[size];
	  if (mswIsInAvailFPages(header, pg) == 0) {
	    if (tempHeapInfo == NULL) {
	      assert("found a fixed page not full but not"
		     "in availFPages[]" == NULL);
	    }
	    pg = tempHeapInfo->availFPages[size];
	    if (mswIsInAvailFPages(header, pg) == 0) {
	      assert("found a fixed page not full but not"
		     "in availFPages[]" == NULL);
	    }
	  }
	}
	else {
	  /* No free objects => check that this page
	   * is NOT among availables pages.
	   */
	  pg = availFPages[size];
	  while (pg) {
	    if (pg == header) break;
	    pg = pg->nextPage;
	  }
	  assert(pg == NULL);
	}
}

/*---------------------------------------------------------------------------*
 * ::mswCheckFreeFixedList
 *
 * Trace the "freeList" for objs of size "size" checking that every obj
 * is not marked, not allocated, that it is filled with EMPTY_MEM_TAG or
 * RELEASED_MEM_TAG and that the corresponding page is PAGE_Free of PAGE_Fixed.
 *---------------------------------------------------------------------------*/

static void
mswCheckFreeFixedList(PageHeader page, int size)
{
	Ptr 	p;
	Ptr	start;
	Ptr	freeList = page->freeList;
	int	pageInfo = PAGE_INFO(page);

	if (freeList == NULL) return;

	assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Free);

	while (freeList) {
	  /* Check that every obj is inside page boundaries */
	  assert(freeList > (Ptr)page + sizeof(PageHeaderStruct));
	  assert(freeList < (Ptr)page + bytesPerPage);
	  /* Check that obj is marked Free */
	  assert(*((Ptr)freeList) == FreeMask);

	  start = (Ptr)freeList + 1 + sizeof(Ptr);

	  mswTagMemDEBUG({
	    for (p = start; p < freeList + 1 + size; p++)
	      assert(*p == EMPTY_MEM_TAG ||
		     *p == RELEASED_MEM_TAG);
	  });
	
	  freeList = NEXT_FREE_OBJ(freeList);
	}
}

static void
mswCheckFreeFixedObjs(void)
{
	int	i;
	PageHeader page;

	for (i = PtrSize; i < MaxFixedSize; i += PtrSize) {
	  page = availFPages[i];
	  while (page) {
	    if (tempHeapInfo)
	      assert(PAGE_SPACE(page) == SPACE_Temporary);
	    else
	      assert(PAGE_SPACE(page) == SPACE_Permanent);
	    assert(page->objSize == i);
	    assert(page->isMarked == 0);
	    assert(page->freeList);
	    mswCheckFreeFixedList(page, i);
	    page = page->nextPage;
	  }
	}
}

static void
mswCheckFPage(Ptr page)
{
	PageHeader header = (PageHeader) page;
	Ptr	 p;
	int	 size  = header->objSize;
	int 	 size1 = size + OBJ_ALIGNMENT;
	Ptr	 hi = GET_LAST_OBJ_PTR(page, size);
	int	 firstObjOff;
	int	 allocatedObjs = 0;

	mswCheckPageIsFixed(page);
	firstObjOff = FPagesInfo[size].firstObjOffset;

	for (p = page + firstObjOff; p <= hi; p += size1) {
	  assert(*(Byte *)(p-1) == TransparentMask
		 || *(Byte *)(p-1) == OpaqueMask);
	  assert(*p == AllocMask || *p == FreeMask);
	  if (*p == AllocMask)
	    allocatedObjs += 1;
	}
	assert(allocatedObjs == header->allocatedObjs);
}

static void
mswCheckMixedPage(PageHeader header)
{
	int	nPages = header->nPages;
	int	index = GCPtoPage(header);
	int	i;

	for (i = index + 1; i < index + nPages; i++)
	  assert(pageMap[i] == PAGE_Next);

	assert(header->basePointerv == NULL);
	assert(header->allocatedObjs == 1);
	assert(header->nPages == (FirstObjOffset + header->objSize
				  + bytesPerPage) / bytesPerPage);
}

static void
mswCheckFixedAndMixedPages(void)
{
	Ptr page;
	int pageInfo;

	for (page = heapStart; page < heapEnd; page += bytesPerPage) {
	  pageInfo = PAGE_INFO(page);
	  if (pageInfo == PAGE_Fixed)
	    mswCheckFPage(page);
	  else if (pageInfo == PAGE_Mixed) {
	    mswCheckMixedPage((PageHeader)page);
	    page += (((PageHeader)page)->nPages -1) * bytesPerPage;
	  }
	  else
	    assert(pageInfo == PAGE_Other || pageInfo == PAGE_Free);
	}
}

static void
mswCheckPageIsInFreeChunks(Ptr page)
{
	FreePageHeader l = freeChunks;
	FreePageHeader l1;

	while (l) {
	  l1 = l;
	  while (l1) {
	    if ((Ptr) l1 <= page &&
		page < (Ptr)l1 + l1->nPages * bytesPerPage)
	      return;		/* <------- */
	    l1 = l1->nextChunk;
	  }
	  l = l->nextChunkGroup;
	}

	assert(l);			/* Cause assertion fault */
}

static void
mswCheckPageMap(void)
{
	Ptr	page;
	int	pageInfo;

	assert(heapStart < heapEnd);

	for (page = heapStart; page < heapEnd; page+= bytesPerPage) {
	  pageInfo = PAGE_INFO(page);
	  assert(pageInfo == PAGE_Free || pageInfo == PAGE_Fixed ||
		 pageInfo == PAGE_Mixed || pageInfo == PAGE_Other ||
		 pageInfo == PAGE_Next);

	  if (pageInfo == PAGE_Free) {
	    mswCheckPageIsInFreeChunks(page);
	    assert(PAGE_SPACE(page) == SPACE_Permanent);
	  }
	  else if (pageInfo == PAGE_Fixed)
	    mswCheckPageIsFixed(page);
	}
}

/* !! TODO: should check that free space contains RELEASED_MEM_TAG or
 * EMPTY_MEM_TAG
 */
static void
mswCheckFreeChunks()
{
	FreePageHeader	l = freeChunks;
	FreePageHeader	l1;
	int		i, nPages, nGroupPages;
	int		numFreePgs = 0;
	Ptr		p;

	while (l) {
	  assert(IS_INSIDE_HEAP(l));
	  l1 = l;
	  if (l1)
	    nGroupPages = l1->nPages;
	  while (l1) {
	    assert(IS_INSIDE_HEAP(l1));
	    /* Check that is a page address */
	    assert((Word)l1 == ROUND_DOWN(l1, bytesPerPage));
	    assert(l1->nPages > 0 &&
		   l1->nPages < 20000);
	    assert(l1->nPages == nGroupPages);

	    numFreePgs += nGroupPages;
	    /* Check pages are marked with PAGE_Free */
	    i = GCPtoPage(l1);
	    nPages = nGroupPages;
	    while (nPages--)
	      assert(pageMap[i++] == PAGE_Free);
	
	    mswTagMemDEBUG({
	      for (p = (Ptr)l1+sizeof(FreePageHeaderStruct)+1; p < (Ptr)l1 + (l1->nPages * bytesPerPage); p++)
		assert(*p == RELEASED_MEM_TAG ||
		       *p == EMPTY_MEM_TAG);
	    });
	
	    l1 = l1->nextChunk;
	  }
	  l = l->nextChunkGroup;
	}
	assert(totFreePages == numFreePgs);
}

#endif				/* ! NDEBUG */

void
mswCheckHeap(int verbose)
{
#ifndef NDEBUG
	if (verbose)
	  fprintf(gcOut,
		  "\n------------- Checking heap corruption ---------------\n");
	if (verbose) fprintf(gcOut, "- checking free chunks...\n");
	mswCheckFreeChunks();
	if (verbose) fprintf(gcOut, "- checking page map...\n");
	if (mustResetTempHeap) {
	        if (verbose) {
		      fprintf(gcOut,
			      "mustResetTempHeap = T => skipping test...\n");
                }
	}
	else
	        mswCheckPageMap();
	if (verbose) fprintf(gcOut, "- checking free fixed objects...\n");
	mswCheckFreeFixedObjs();
	if (verbose) fprintf(gcOut, "- checking fixed and mixed pages...\n");
	if (mustResetTempHeap)
	        if (verbose) {
		      fprintf(gcOut,
			      "mustResetTempHeap = T => skipping test...\n");
        }
	else
                mswCheckFixedAndMixedPages();
	if (verbose)
	  fprintf(gcOut,
		  "-------------------- Heap is OK ------------------------\n\n");
#endif
}

#ifndef NDEBUG
/*---------------------------------------------------------------------------*
 * :: Functions useful during debugging sessions
 *---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*
 * :: getPtrInfo
 *
 * Given a pointer, shows some useful information: page to which belong, size
 * of the pointed object, etc.
 * To be used when a crash happen to get information about the pointer causing
 * it.
 *
 *---------------------------------------------------------------------------*/

void
getPtrInfo(Ptr p)
{
	PageHeader page;
	Ptr	   base;
	char *	   temporary = "";

	fprintf(gcOut, "---- getPtrInfo(%lx): ----\n", p);

	if (! IS_INSIDE_HEAP(p)) {
	  fprintf(gcOut, "Hum... this pointer is outside MSW heap...\n");
	  return;
	}
	page = (PageHeader) PAGE_START(p);

	switch (PAGE_INFO(p)) {
	case PAGE_Fixed:
	  if (pageSpace[GCPtoPage(p)] == SPACE_Temporary)
	    temporary = " *temporary*";

	  fprintf(gcOut, "This pointer points into a%s fixed page.\n",
		  temporary);
	  fprintf(gcOut, "Page: %lx  (index: %d, offset: %d)\n",
		  page, GCPtoPage(p), (Word)p - (Word)page);
	  fprintf(gcOut, "Size of objs in this page: %d\n",
		  page->objSize);
	  fprintf(gcOut, "Objs allocated in this page: %d\n",
		  page->allocatedObjs);

	  if (p - (Ptr) page < FirstObjOffset) {
	    fprintf(gcOut, "Address before first object offset.\n");
	    return;
	  }
	  base = GET_OBJ_BASE(p, page);
	  fprintf(gcOut, "pointer base: %lx\n", base);
	  if (base == p) {
	    fprintf(gcOut, "WARNING: the pointer points before the beginning of a fixed object!\n");
	    return;
	  }
	  switch (*base) {
	  case AllocMask:
	    fprintf(gcOut, "STATE: allocated\n"); break;
	  case MarkMask:
	    fprintf(gcOut, "STATE: marked\n"); break;
	  case FreeMask:
	    fprintf(gcOut, "STATE: free\n"); break;
	  default:
	    fprintf(gcOut,
		    "WARNING: STATE is not MarkMask | AllocMask | FreeMask! \n");
	    break;
	  }
	  switch (*(base-1)) {
	  case OpaqueMask:
	    fprintf(gcOut, "Obj is OPAQUE \n"); break;
	  case TransparentMask:
	    fprintf(gcOut, "Obj is TRANSPARENT \n"); break;
	  default:
	    fprintf(gcOut,
		    "WARNING: not registred as OPAQUE or TRANSPARENT! \n");
	    break;
	  }
	  break;
	case PAGE_Next: {
	  int index;

	  if (pageSpace[GCPtoPage(p)] == SPACE_Temporary)
	    temporary = " *temporary*";

	  fprintf(gcOut,
		  "This pointer is in the middle of a%s mixed object\n",
		  temporary);
	  fprintf(gcOut, "finding the base page...\n");

	  index = GCPtoPage(p) - 1;
	  while (pageMap[index] != PAGE_Mixed) {
	    index -= 1;
	    assert(index > 0);
	  }
	  p = (Ptr)pageToGCP(index);
	  goto LAB_PageMixed;
	}
	case PAGE_Mixed:

	  if (pageSpace[GCPtoPage(p)] == SPACE_Temporary)
	    temporary = " *temporary*";

	  fprintf(gcOut, "This pointer points into a%s mixed page\n",
		  temporary);
	LAB_PageMixed:
	  page = (PageHeader) PAGE_START(p);

	  fprintf(gcOut, "Size of the obj in this page: %d\n",
		  page->objSize);
	  fprintf(gcOut, "Number of pages for this obj: %d\n",
		  page->nPages);

	  if (p - (Ptr) page < FirstObjOffset) {
	    fprintf(gcOut,
		    "The pointer points before the first object offset!\n");
	    return;
	  }
	  return;

	case PAGE_Free:
	  if (pageSpace[GCPtoPage(p)] == SPACE_Temporary)
	    temporary = " *temporary*";

	  fprintf(gcOut, "This pointer points to a chunk of released%s memory.\n", temporary);
	  return;

	case PAGE_Other:
	  fprintf(gcOut, "This pointer points to another heap.\n");
	  return;

	default:
	  fprintf(gcOut, "BUG -- getPtrInfo(): unknown page type (probably the page map is corrupted).\n");
	}
}

/*---------------------------------------------------------------------------*
 * :: Functions boxing some macros -- useful for debugging
 *---------------------------------------------------------------------------*/

Ptr
pageStart(Ptr p)
{
	return PAGE_START(p);
}

Ptr
objBase(Ptr p, PageHeader header)
{
	return GET_OBJ_BASE(p, header);
}

int
isInsideHeap(Ptr p)
{
	return IS_INSIDE_HEAP(p);
}

int
pageIndex(Ptr p)
{
	return GCPtoPage(p);
}

Ptr
pageFromIndex(int index)
{
	return (Ptr)pageToGCP(index);
}

int
pageSpaceFromPtr(Ptr p)
{
	int space = PAGE_SPACE(p);
	if (space == SPACE_Temporary)
	  printf("(temporary)\n");
	else
	  printf("(permanent)\n");
	return space;
}

int
pageInfo(Ptr p)
{
	int info = PAGE_INFO(p);
	char * s;
	switch (info) {
	case PAGE_Free: s = "Free"; break;
		      case PAGE_Fixed: s = "Fixed"; break;
		      case PAGE_Mixed: s = "Mixed"; break;
		      case PAGE_Next: s = "Next"; break;
		      case PAGE_Other: s = "Other"; break;
		      }
	printf("(%s)\n", s);
	return info;
}

Word
roundUp(Word a, Word b)
{
	return ROUND_UP(a,b);
}

Word
roundDown(Word a, Word b)
{
	return ROUND_DOWN(a,b);
}

Ptr
getLastObjPtr(Ptr p, Word size)
{
	return GET_LAST_OBJ_PTR(p, size);
}

# ifdef MSW_TRACE_ONE_PAGE
/* Add a call to mswTraceFPage(xxx) on the top of mswAlloc();
 * When you get the problem with a fixed page, take its address and restart
 * setting xxx = address of the corrupted page.
 */
void
mswTraceFPage(Ptr page)
{
	if (IS_INSIDE_HEAP(page) &&
	    PAGE_INFO(page) == PAGE_Fixed)
	  mswCheckFPage(page);
}
# endif				/* MSW_TRACE_ONE_PAGE */

void
mswCheckAllocatedObj(void * ptr)
{
	Ptr	   obj = (Ptr) ptr;
	int 	   pageInfo = PAGE_INFO(obj);
	PageHeader header = (PageHeader) PAGE_START(obj);

	assert(IS_INSIDE_HEAP(obj));
	assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed);

	if (pageInfo == PAGE_Fixed) {
	  Ptr bp = GET_OBJ_BASE(obj, header);
	  assert(bp != (Ptr) header);
	}
	else
	  assert((Word) obj - (Word)header  == FirstObjOffset + 1);

}

# ifdef MSW_GET_ALLOC_SIZE_STATS
void
mswShowStats()
{
	int i;
	for (i = 1; i < MAX_TRACED_SIZE; i++)
	  if (totAllocatedSizes[i])
	    printf("%lu objs of size = %lu\n",totAllocatedSizes[i], i);
	printf("%lu objs of size = %lu\n", totHugeAllocated,MAX_TRACED_SIZE);

}
# endif				/* MSW_GET_ALLOC_SIZE_STATS */

#endif				/* NDEBUG */
back to top