/***************************************************************************** * * msw.cc: memory manager with mark&sweep garbage collection. * * version: 0.0.1 (27 Aug 95) * authors: Pietro Iglio * email: cmm@di.unipi.it, iglio@posso.dm.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: * * - MSW_DEBUG * - MSW_CHECK_HEAP: perform automatic heap checking before/after every * collection and tempHeap destruction. * - MSW_SERIAL_DEBUG * - MSW_TRACE_ONE_PAGE * - MSW_DONT_CLEAN_FREE_MEM: when MSW_DEBUG is on avoid clearing every * empty/released memory object with a special * tag. * * 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 "machine.h" #include "cmm.h" #include "msw.h" #include #include #include #include #include /****************************************************************************** * :: Debug Stuff *****************************************************************************/ unsigned long markedBytes = 0; unsigned long sweptBytes = 0; unsigned totFreeFPages = 0; unsigned long totFreeFixedMem = 0; unsigned long allocSerial = 0; unsigned long freeSerial = 0; unsigned long collectSerial = 0; FILE * gcOut = stderr; #ifdef NDEBUG int mswDebug = 0; # define mswDEBUG(STMT) # define mswCleanMemDEBUG(STMT) # define mswSerialDEBUG(STMT) # define mswGcDEBUG(STMT) # define mswCheckDEBUG(STMT) # define mswCondCheckDEBUG(STMT) # define mswTracePageDEBUG(page) # define mswGetStatsDEBUG(STMT) #else int mswDebug = 1; int mswGcDebug = 0; int mswCheckDebug = 1; # define mswDEBUG(STMT) STMT # if defined(MSW_DONT_CLEAN_MEM) # define mswCleanMemDEBUG(STMT) # else # define mswCleanMemDEBUG(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 #if defined(__i386) extern int etext; # define DATASTART ((((unsigned long)(&etext)) + 0xfff) & ~0xfff) # define STACKBOTTOM ((Ptr)0xc0000000) #endif #if defined(__mips) || defined(__sparc) || defined(__alpha) #define ObjAlignment 8 #endif /****************************************************************************** * * :: Macros * *****************************************************************************/ /******************************* Constants *******************************/ #define MaxFixedSize (bytesPerPage >> 1) - 16 #define PageMask (~(Word)(bytesPerPage - 1)) #define PagesRequest 10 #if !defined(ObjAlignment) # define ObjAlignment 4 #endif #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, \ ObjAlignment) -1 #define AllocMask 0x1 #define MarkMask 0x3 #define FreeMask 0x0 /* 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 /* 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_FROM_PTR(ptr) (Ptr)((Word)(ptr) & PageMask) #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) < heapEndPtr && (Ptr)(p) >= heapStartPtr) #define GET_OBJ_BASE(ptr, header) \ (Ptr)((Word)header + header->basePointerv[(Word)(ptr)-(Word)header]) #define INDEX_FROM_PTR(p) \ (Word)(((unsigned long) p) / bytesPerPage) #define PAGE_FROM_INDEX(i) ((Ptr)((i) * bytesPerPage)) #define PAGE_INFO_FROM_PTR(p) pageMap[INDEX_FROM_PTR(p)] #define PAGE_SPACE_FROM_PTR(p) pageSpace[INDEX_FROM_PTR(p)] /* How many pages needed for "bytes" bytes. */ #define BYTES_TO_PAGES(bytes) 1 + ((bytes) / bytesPerPage) #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) + ObjAlignment) /* 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 * *****************************************************************************/ typedef unsigned char Byte; typedef unsigned long Word; typedef Byte * Ptr; /****** 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; }; TempHeapInfo tempHeapInfo = NULL; int mustResetTempHeap = 0; int noCollection = 0; #define mswDisableCollection() (noCollection = 1) #define mswEnableCollection() (noCollection = 0) #define mswIsCollectionDisabled() (noCollection) /****************************************************************************** * * :: Global Variables * *****************************************************************************/ struct FPagesInfoStruct FPagesInfo [MaxFixedSize]; static PageHeader availFPages [MaxFixedSize]; static unsigned totFreePages = 0; /***** GC "Automatic" or "On Demand" *****/ static unsigned mswGcType = 0; /***** freeChunks *****/ static FreePageHeader freeChunks = NULL; static int totReleasedPages = 0; /***** Memory Sections *****/ static Ptr stackStartPtr; static Ptr stackEndPtr; static Ptr dataStartPtr; static Ptr dataEndPtr; static Ptr heapStartPtr = (Ptr) -1; static Ptr heapEndPtr = NULL; extern int end; /* Compiler defined, end of data segment */ /****************************************************************************** * :: Timings *****************************************************************************/ #if defined(MSW_SHOW_TIMINGS) # ifdef sgi /* System V */ # include # include # else # include # include # 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 mswReservePages (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); /****************************************************************************** * * :: Function Definitions * *****************************************************************************/ /****************************************************************************** * :: 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; // 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) if ((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) return mswAlloc(size); 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 *****************************************************************************/ #define FIXED_MEM_WEIGHT 1 #define GC_FREE_FACTOR 10 /* 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. */ static int mswShouldExpandHeap(void) { Word heapSize = ((Word)lastHeapPage - firstHeapPage) * bytesPerPage; Word averageFreeMem = (totFreePages * bytesPerPage); mswDEBUG(fprintf(stdout, "mswShouldExpandHeap: " "heapSize:%lu, freeMem:%lu ->", heapSize, averageFreeMem);); if (averageFreeMem * GC_FREE_FACTOR < heapSize) { mswDEBUG(fprintf(stdout, " expand heap\n");); return 1; } else { mswDEBUG(fprintf(stdout, " NOT expand heap\n");); return 0; } } /****************************************************************************** * :: mswReservePages *****************************************************************************/ #define HAS_ENOUGH_PAGES(npages) (lastHeapPage - firstFreePage >= (npages) + 1) static Ptr mswExpandHeap (int pagesRequest); /* 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 mswReservePages is called no chunk of "nPages" size is * currently available. * NOTE: a NULL value is returned only if no memory is available. */ static Ptr mswReservePages(int nPages, Word size) { Ptr newPages; int pagesRequest; // = PagesRequest; // if (pagesRequest < nPages) pagesRequest = nPages; if (mswGcType == MSW_Automatic && ! HAS_ENOUGH_PAGES(pagesRequest)) { mswDEBUG(fprintf(gcOut, "Automatic gc call...\n");); mswCollect(); /* Expand anyway if not found enough free pages */ if (mswShouldExpandHeap()) { newPages = mswExpandHeap(pagesRequest); mswAddToFreeChunksAndMap(newPages, pagesRequest); } /* 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(pagesRequest); } /****************************************************************************** * :: mswExpandHeap *****************************************************************************/ static Ptr mswExpandHeap(int nPages) { Ptr newPages; int pagesRequest = nPages; int extraPages; int lowestFreePage; int lastPage = INDEX_FROM_PTR(heapEndPtr) - 1; Ptr extraChunk; Word bytesRequest; if (pageMap[lastPage] == PAGE_Free && lastPage > firstHeapPage) { lowestFreePage = lastPage - 1; while (pageMap[lowestFreePage] == PAGE_Free) lowestFreePage -= 1; lowestFreePage += 1; pagesRequest -= (lastPage - lowestFreePage); } newPages = (Ptr) allocatePages(pagesRequest, Cmm::theMSHeap); bytesRequest = pagesRequest * bytesPerPage; /* Check that allocatePages() returns an aligned address */ assert(newPages == PAGE_FROM_PTR(newPages)); pagesRequest = bytesRequest / bytesPerPage; assert(heapStartPtr <= newPages); if (heapEndPtr != newPages) { mswPageMapSetRange(heapEndPtr, newPages - 1, PAGE_Other); mswPageSpaceSetRangeTo(heapEndPtr,newPages-1, SPACE_Permanent); } if (heapEndPtr < newPages + bytesRequest) heapEndPtr = newPages + bytesRequest; mswPageSpaceSet(newPages, nPages); if (pagesRequest != nPages) { Ptr chunk = PAGE_FROM_INDEX(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 + ObjAlignment; 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 */ mswCleanMemDEBUG({ 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[INDEX_FROM_PTR(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[INDEX_FROM_PTR(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_FROM_PTR(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((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; */ mswCleanMemDEBUG({ 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_FROM_PTR(ptr); PageHeader page = (PageHeader) PAGE_FROM_PTR(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_FROM_PTR(ptr); PageHeader page = (PageHeader) PAGE_FROM_PTR(ptr); assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed); if (pageInfo == PAGE_Fixed) return page->objSize; else return (page->nPages * bytesPerPage) - FirstObjOffset -1; } /****************************************************************************** * :: mswResize *****************************************************************************/ /* 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_FROM_PTR(p) == PAGE_Mixed) page = (PageHeader) PAGE_FROM_PTR(p); page->objSize = size; return p; /* <---------- */ } else { newPtr = (Ptr) mswAlloc(size); page = (PageHeader) PAGE_FROM_PTR(p); memcpy(newPtr, p, realSize); mswFree(p); return newPtr; } } /****************************************************************************** * :: mswCalloc *****************************************************************************/ /* 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 = INDEX_FROM_PTR(from); h = INDEX_FROM_PTR(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 = INDEX_FROM_PTR(pageStart); while (nPages--) { pageMap[index] = type; index += 1; } } /****************************************************************************** * * :: PageSpace * *****************************************************************************/ static void mswPageSpaceSetRange(Ptr from, Ptr to) { Word l; Word h; short type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent); register Word k; l = INDEX_FROM_PTR(from); h = INDEX_FROM_PTR(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 = INDEX_FROM_PTR(from); h = INDEX_FROM_PTR(to); for (k = l; k <= h; k++) pageSpace[k] = type; } static void mswPageSpaceSet(Ptr pageStart, int nPages) { int index = INDEX_FROM_PTR(pageStart); short type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent); while (nPages--) { pageSpace[index] = type; index += 1; } } static void mswPageSpaceSetTo(Ptr pageStart, int nPages, short type) { int index = INDEX_FROM_PTR(pageStart); assert(type == SPACE_Permanent || type == SPACE_Temporary); while (nPages--) { pageSpace[index] = type; index += 1; } } /****************************************************************************** * * :: 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; mswCleanMemDEBUG({ Ptr p; Ptr endPtr = ptr + (nPages * bytesPerPage); for (p = ptr + sizeof(struct freePageHeaderStruct) + 1; p < endPtr; 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); mswCleanMemDEBUG({ 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 there are in the coping 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 = INDEX_FROM_PTR(chunk); int limitIndex= INDEX_FROM_PTR(heapEndPtr); 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 = PAGE_FROM_INDEX(index); mswRemoveFromFreeChunks((FreePageHeader)newChunk); } index = baseIndex + *pNPages; /* A free chunk follows the current chunk? */ if (index < limitIndex && pageMap[index] == PAGE_Free) { followChunk = (FreePageHeader) PAGE_FROM_INDEX(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 = INDEX_FROM_PTR(p); pageMap[index] = PAGE_Mixed; while (--nPages) pageMap[++index] = PAGE_Next; return p + FirstObjOffset + 1; } /* Alloc "nPages" consecutive pages from freeChunks; if no available chunk * can satisfy the request, mswReservePages() is called. * "size" is 0 if the page is for mixed objects, else the size of fixed * objects. This value is passed to mswReservepages() 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 = mswReservePages(nPages, size); if (tempHeapInfo && page) { int pg = INDEX_FROM_PTR(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 jmp_buf regs; static void mswMarkFromTo (Ptr from, Ptr to); extern char ** environ; static void mswMark(void) { int dummy = 0; int i; static void * mmenv = NULL; /* ensure flushing of register caches */ if (_setjmp(regs) == 0) _longjmp(regs, 1); if (!mmenv) # if defined(STACKBOTTOM) mmenv = STACKBOTTOM-1; # else mmenv = environ; # endif stackStartPtr = (Ptr) mmenv; stackEndPtr = (Ptr) &dummy; if (stackStartPtr > stackEndPtr) { Ptr tmp = stackStartPtr; stackStartPtr = stackEndPtr; stackEndPtr = tmp; } mswDEBUG({ markedBytes = 0; }); mswMarkFromTo(stackStartPtr, stackEndPtr); mswGcDEBUG({fprintf(gcOut, " (%lu marked from stack)", markedBytes); }); mswMarkFromTo(dataStartPtr, dataEndPtr); } static void mswMarkFromTo(Ptr from, Ptr to) { long * pt; Ptr p; Ptr bp; static PageHeader header; static unsigned pageInfo; assert(from < to); for (pt = (long*) from; pt < (long*) to; pt++) { p = *(Ptr *)pt; if (! IS_INSIDE_HEAP(p)) continue; pageInfo = PAGE_INFO_FROM_PTR(p); if (pageInfo == PAGE_Fixed) { header = (PageHeader) PAGE_FROM_PTR(p); bp = GET_OBJ_BASE(p, header); /* Is really pointing to a fixed obj? */ if ((Ptr) header == bp) continue; /* Consider only allocated objs not marked. */ if (*bp != AllocMask) continue; /* Mark this object */ *bp = MarkMask; mswDEBUG({ markedBytes += header->objSize; }); /* Mark this page */ header->isMarked = 1; mswMarkFromTo(bp+1, bp + header->objSize +1); } else if (pageInfo == 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; mswDEBUG({ markedBytes += header->nPages * bytesPerPage; }); /* If opaque, don't traverse it */ if (((PageHeader)p)->isOpaque) continue; p += FirstObjOffset + 1; mswMarkFromTo(p, p + header->objSize); } else if (pageInfo == PAGE_Next) { int index = INDEX_FROM_PTR(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = PAGE_FROM_INDEX(index); goto LAB_PageMixed; } } } /****************************************************************************** * :: mswSweep functions *****************************************************************************/ static void mswSweepFPage(Ptr page) { Word size = ((PageHeader)page)->objSize; Ptr p; Word size1 = size + ObjAlignment; 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; mswDEBUG(totFreeFPages += 1;); mswDEBUG({ 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; mswCleanMemDEBUG({ Ptr pd; for (pd = p + 1 + sizeof(Ptr); pd < p + 1 + size; pd++) *pd = EMPTY_MEM_TAG; }); fixedFreeList = p; released += 1; mswDEBUG(totFreeFixedMem += size;); } /* totFreeFixedMem += (size * released); */ if (wasFull && released != 0) { if (tempHeapInfo && PAGE_SPACE_FROM_PTR(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; }); mswDEBUG({ if (((PageHeader)page)->allocatedObjs == 0) totFreeFPages += 1; }); } /****************************************************************************** * :: mswSweep *****************************************************************************/ static void mswSweep() { Ptr page; unsigned pageInfo; PageHeader header; int i; totReleasedPages = 0; for (page = heapStartPtr; page < heapEndPtr; page += bytesPerPage) { pageInfo = PAGE_INFO_FROM_PTR(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 { mswDEBUG(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; mswDEBUG({ markedBytes = 0; sweptBytes = 0; totFreeFPages = 0; }); mswShowTIME({ time1 = mswGetCpuTime(); }) mswMark(); /********* Mark Phase *********/ mswDEBUG({ fprintf(stdout, "."); fflush(stdout); }); 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(stdout, "#%lu: ", collectSerial); }); mswCondCheckDEBUG(mswCheckHeap(0);); mswDEBUG({ fprintf(stdout, "[Garbage collection.."); fflush(stdout); }); mswMarkAndSweep(); mswDEBUG({ fprintf(stdout, "done.]\n"); }); mswDEBUG({ fprintf(stdout, "Marked %lu bytes\n", markedBytes); fprintf(stdout, "Swept %lu bytes\n", sweptBytes); fprintf(stdout, "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(stdout, "heap size < gc threshold: skipping GC\n")); return; /* <---------- */ } #ifdef xxx averageFreeMem = (totFreePages * bytesPerPage) /* + totFreeFixedMem / FIXED_MEM_WEIGHT */ ; mswDEBUG(fprintf(stdout, "heapSize:%lu, averageFreeMem:%lu ", heapSize, averageFreeMem)); if (averageFreeMem * GC_FREE_FACTOR > heapSize) { mswDEBUG(fprintf(stdout, "-> GC request REJECTED.\n");); return; /* <-------- */ } #endif mswDEBUG(fprintf(stdout, "-> GC request ACCEPTED.\n");); mswCollectNow(); } /****************************************************************************** * * :: MarkAndSweepInit() * *****************************************************************************/ void mswInit(unsigned gcType) { 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; if (gcType & MSW_Automatic) mswGcType = MSW_Automatic; if (gcType & MSW_OnDemand) { assert(mswGcType == 0); mswGcType = MSW_OnDemand; } assert(mswGcType != 0); freeChunks = NULL; dataStartPtr = (Ptr) DATASTART; dataEndPtr = (Ptr) &end; stackStartPtr = (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, ObjAlignment) -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 + ObjAlignment; 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) { bp = (Word) j; counter = size1 - 1; /* Faith fake pointers: a pointer will not be * traced if is pointing to an object header. */ for (k = j - ObjAlignment + 1; k <= j; k++) FPagesInfo[i].basePointerv[k] = NULL; continue; } else counter -= 1; 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(); heapStartPtr = PAGE_FROM_INDEX(firstHeapPage); heapEndPtr = heapStartPtr; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) availFPages[i] = mswAllocFPage(i); { char * c = (char *) mswAlloc(4); /* initialize allocator if not */ mswFree(c); } } /****************************************************************************** * * MarkAndSweep::scanRoots * *****************************************************************************/ static void scanFPageRoots(PageHeader); static void scanMixedPageRoots(PageHeader); void MarkAndSweep::scanRoots(int page) { unsigned pageInfo = PAGE_INFO_FROM_PTR(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) scanFPageRoots((PageHeader)PAGE_FROM_INDEX(page)); else if (pageInfo == PAGE_Mixed) scanMixedPageRoots((PageHeader)PAGE_FROM_INDEX(page)); } static void scanFPageRoots(PageHeader header) { int size = header->objSize; Word size1 = size + ObjAlignment; 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); } } static void scanMixedPageRoots(PageHeader header) { long* ptr; long* endPtr; if (header->isOpaque) return; // <---- endPtr = (long*) FirstObjOffset + 1 + header->objSize; for (ptr = (long*) FirstObjOffset + 1; ptr < endPtr; ptr++) promotePage(ptr); } /****************************************************************************** * * :: TempHeap * *****************************************************************************/ /****************************************************************************** * :: mswRegisterRoot *****************************************************************************/ void mswRegisterRoot(void * p) { if (tempHeapInfo->nRoots == MAX_ROOT) { fprintf(stderr, "Too many roots...\n"); exit(-1); } tempHeapInfo->roots[tempHeapInfo->nRoots++] = (Ptr) p; } /****************************************************************************** * :: mswTempHeapFreePages *****************************************************************************/ /* Releases every page --EXCEPT ones marked PAGE_Other-- from * tempHeapInfo->firstPage up to heapEndPtr. 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(PAGE_FROM_INDEX(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(PAGE_FROM_INDEX(page)); } /****************************************************************************** * :: mswTempHeapStart *****************************************************************************/ /* Freezes availFPages[] and resets it, such that everything is * allocated into the new space. */ void mswTempHeapStart() { 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(); } /****************************************************************************** * :: mswTempHeapEnd *****************************************************************************/ void mswTempHeapEnd() { 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); } } void mswTempHeapFree() { mswTempHeapFreePages(); mustResetTempHeap = 0; mswEnableCollection(); mswCondCheckDEBUG(mswCheckHeap(0)); } /****************************************************************************** * * :: 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"); if (mswDebug) fprintf(gcOut, "+++ Debug version +++\n"); fprintf(gcOut, "Alignment = %d\n", ObjAlignment); fprintf(gcOut, "Max heap size = %lu Kbytes\n", (unsigned long) (heapEndPtr - heapStartPtr) / 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 = INDEX_FROM_PTR(heapStartPtr); int top = INDEX_FROM_PTR(heapEndPtr); 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 = INDEX_FROM_PTR(heapStartPtr); int top = INDEX_FROM_PTR(heapEndPtr); 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"); } /* 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(struct PageHeaderStruct)) / (size + ObjAlignment); } /* Calculates fragmentation for each fixed size. */ void mswShowFragmentation() { double realUse; double totRealUse = 0.0; int totAnalized = 0; int i, totObjs, totPages, minPages; PageHeader pages; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { pages = availFPages[i]; /* Show only significant data */ if (pages == NULL || pages->nextPage == NULL) { 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)\n", totObjs, totPages, minPages); } if (totAnalized) fprintf(gcOut, "\nTot: fixed pages used at %2.4g%%.\n", totRealUse / (double) totAnalized); else fprintf(gcOut, "No fragmentation for fixed objs.\n"); } /****************************************************************************** * :: Heap Checking Functions *****************************************************************************/ /* 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; } /* 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); } } /* 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_FROM_PTR(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(struct PageHeaderStruct)); assert(freeList < (Ptr)page + bytesPerPage); /* Check that obj is marked Free */ assert(*((Ptr)freeList) == FreeMask); start = (Ptr)freeList + 1 + sizeof(Ptr); mswCleanMemDEBUG({ 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_FROM_PTR(page) == SPACE_Temporary); else assert(PAGE_SPACE_FROM_PTR(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 + ObjAlignment; 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 == AllocMask || *p == FreeMask); if (*p == AllocMask) allocatedObjs += 1; } assert(allocatedObjs == header->allocatedObjs); } static void mswCheckMixedPage(PageHeader header) { int nPages = header->nPages; int index = INDEX_FROM_PTR(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 = heapStartPtr; page < heapEndPtr; page += bytesPerPage) { pageInfo = PAGE_INFO_FROM_PTR(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(heapStartPtr < heapEndPtr); for (page = heapStartPtr; page < heapEndPtr; page+= bytesPerPage) { pageInfo = PAGE_INFO_FROM_PTR(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_FROM_PTR(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 = INDEX_FROM_PTR(l1); nPages = nGroupPages; while (nPages--) assert(pageMap[i++] == PAGE_Free); mswCleanMemDEBUG({ for (p = (Ptr)l1+sizeof(struct 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) { # if !defined(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"); mswCheckPageMap(); if (verbose) fprintf(gcOut, "- checking free fixed objects...\n"); mswCheckFreeFixedObjs(); if (verbose) fprintf(gcOut, "- checking fixed and mixed pages...\n"); 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_FROM_PTR(p); switch (PAGE_INFO_FROM_PTR(p)) { case PAGE_Fixed: if (pageSpace[INDEX_FROM_PTR(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer is pointing inside a%s fixed page.\n", temporary); fprintf(gcOut, "Page: %lx (index: %d, offset: %d)\n", page, INDEX_FROM_PTR(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 is pointing before the start of the object!\n"); return; } break; case PAGE_Next: { int index; if (pageSpace[INDEX_FROM_PTR(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 = INDEX_FROM_PTR(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = PAGE_FROM_INDEX(index); goto LAB_PageMixed; } case PAGE_Mixed: if (pageSpace[INDEX_FROM_PTR(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer is pointing inside a%s mixed page\n", temporary); LAB_PageMixed: page = (PageHeader) PAGE_FROM_PTR(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 is pointing before the first object offset!\n"); return; } return; case PAGE_Free: if (pageSpace[INDEX_FROM_PTR(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer is pointing to a chunk of released%s memory.\n", temporary); return; case PAGE_Other: fprintf(gcOut, "This pointer is pointing 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 pageFromPtr(Ptr p) { return PAGE_FROM_PTR(p); } Ptr objBase(Ptr p, PageHeader header) { return GET_OBJ_BASE(p, header); } int isInsideHeap(Ptr p) { return IS_INSIDE_HEAP(p); } int indexFromPtr(Ptr p) { return INDEX_FROM_PTR(p); } Ptr pageFromIndex(int index) { return PAGE_FROM_INDEX(index); } int pageSpaceFromPtr(Ptr p) { int space = PAGE_SPACE_FROM_PTR(p); if (space == SPACE_Temporary) printf("(temporary)\n"); else printf("(permanent)\n"); return space; } int pageInfoFromPtr(Ptr p) { int info = PAGE_INFO_FROM_PTR(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; } int bytesToPages(unsigned long bytes) { return BYTES_TO_PAGES(bytes); } 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_FROM_PTR(page) == PAGE_Fixed) mswCheckFPage(page); } #endif /* MSW_TRACE_ONE_PAGE */ void mswCheckAllocatedObj(void * ptr) { Ptr obj = (Ptr) ptr; int pageInfo = PAGE_INFO_FROM_PTR(obj); PageHeader header = (PageHeader) PAGE_FROM_PTR(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 */