https://github.com/Unipisa/CMM
Tip revision: cfa29670480cf0d5f09f5e3055e530dec3e6ff65 authored by Giuseppe Attardi on 24 November 1996, 18:13:45 UTC
1.7 -
1.7 -
Tip revision: cfa2967
msw.cc
/*****************************************************************************
*
* msw.cc: memory manager with mark&sweep garbage collection.
*
* 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.
*
*---------------------------------------------------------------------------*/
#include "cmm.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <setjmp.h>
#ifndef __WIN32__
# 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_LONG_Free 0L
#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 0xdd
#define RELEASED_MEM_TAG 0xee
#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
/*---------------------------------------------------------------------------*
*
* :: 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);
/*---------------------------------------------------------------------------*
* :: 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;
*(freeList-1) = TransparentMask;
// Next assignment is needed because subsequent call to
// mswAllocFPage might release completely "freePage". This way we
// ensure that there is at least an object alive.
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.
* Usefull only for big chunks, that are not traversed during the collection.
*
*---------------------------------------------------------------------------*/
void *
mswAllocOpaque(unsigned long size)
{
if (size < MaxFixedSize) {
Ptr ret = (Ptr)mswAlloc(size);
*(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;
mswDEBUG(fprintf(gcOut, "Automatic gc call...\n"););
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,
"Not found enough pages after gc! Expanding heap\n"));
return mswExpandHeap(nPages);
}
/*---------------------------------------------------------------------------*
* :: mswExpandHeap
*---------------------------------------------------------------------------*/
static Ptr
mswExpandHeap(int nPages)
{
Ptr newPages;
int pagesRequest = nPages;
int extraPages;
int lowestFreePage;
int lastPage = GCPtoPage(heapEnd) - 1;
Ptr extraChunk;
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);
if (pagesRequest != nPages) {
Ptr chunk = (Ptr)pageToGCP(lowestFreePage);
mswRemoveFromFreeChunks((FreePageHeader)chunk);
newPages = chunk;
}
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;
Ptr tmp;
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;
(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 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)
{
Ptr mem = (Ptr) 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 iif 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;
int baseIndex = GCPtoPage(chunk);
int limitIndex= GCPtoPage(heapEnd);
int index = baseIndex;
Ptr newChunk = chunk;
FreePageHeader followChunk;
while (index > firstHeapPage) {
if (pageMap[index-1] != PAGE_Free)
break;
nPages += 1;
index -= 1;
}
/* "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 ? 1 : 0);
/* 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;
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*) (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 (*(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 (*(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 (*(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;
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)
{
Word time1, time2, time3;
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({
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;
Word averageFreeMem;
if (heapSize < Cmm::gcThreshold)
mswDEBUG(fprintf(gcOut,
"heap size < gc threshold: skipping GC\n"));
else {
mswDEBUG(fprintf(gcOut, "-> GC request ACCEPTED.\n"););
mswCollectNow();
}
}
/*---------------------------------------------------------------------------*
*
* :: mswInit()
*
*---------------------------------------------------------------------------*/
void
mswInit()
{
extern void CmmInit(void);
int i, j, k;
Word firstObjOff, bp = 0;
Word lastObjOff;
Word size1, counter;
static int initialized = 0;
if (initialized) return; // <---------------
initialized = 1;
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 = (Word) PTR_ALIGN(sizeof(PageHeaderStruct)+1,
OBJ_ALIGNMENT) -1;
FPagesInfo[i].firstObjOffset = firstObjOff;
FPagesInfo[i].basePointerv = (Ptr *)
malloc(sizeof(Ptr) * bytesPerPage);
for (j = 0; 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 (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;
}
CmmInit();
heapStart = (Ptr)pageToGCP(firstHeapPage);
heapEnd = heapStart;
for (i = PtrSize; i < MaxFixedSize; i += PtrSize)
availFPages[i] = mswAllocFPage(i);
{
char * c = (char *) mswAlloc(4); /* initialize allocator if not */
mswFree(c);
}
/* 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(int 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(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)
{
int 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,
"+++++ (. = 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;
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(*(p-1) == TransparentMask || *(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 start of the object!\n");
return;
}
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 = 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 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 */
