/***************************************************************************** * * msw.cpp: mark&sweep garbage collector for CMM. * * version: 0.0.2 (30 Oct 96) * authors: Pietro Iglio * email: cmm@di.unipi.it * address: Dipartimento di Informatica * Corso Italia 40 * I-56125 Pisa, Italy * * Copyright (C) 1995 Pietro Iglio * * This file is part of the PoSSo Customizable Memory Manager (CMM). * * Permission to use, copy, and modify this software and its documentation is * hereby granted only under the following terms and conditions. Both the * above copyright notice and this permission notice must appear in all copies * of the software, derivative works or modified versions, and any portions * thereof, and both notices must appear in supporting documentation. * * Users of this software agree to the terms and conditions set forth herein, * and agree to license at no charge to all parties under these terms and * conditions any derivative works or modified versions of this software. * * This software may be distributed (but not offered for sale or transferred * for compensation) to third parties, provided such third parties agree to * abide by the terms and conditions of this notice. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE COPYRIGHT HOLDERS DISCLAIM ALL * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE COPYRIGHT HOLDERS * BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * ****************************************************************************/ /* Following macros can be defined at compile time to get debug info and * heap checking: * * - NDEBUG * - MSW_CHECK_HEAP: perform automatic heap checking before/after every * collection and tempHeap destruction. * - MSW_SERIAL_DEBUG * - MSW_TRACE_ONE_PAGE * - MSW_DONT_TAG_FREE_MEM: when NDEBUG is on avoid filling with a tag * each empty/released memory object. * * Other macros that can be defined at compile time: * * - MSW_ALLOC_ZERO_OK: enables allocation of 0-sized memory objects. * - MSW_GET_ALLOC_SIZE_STATS: counts blocks requests for each size. * - MSW_SHOW_TIMINGS: after each collection shows the time required */ /*---------------------------------------------------------------------------* * DEFINITIONS: *--------------------------------------------------------------------------- * FreeChunks: * A chunk is a set of one or more consecutives pages. * A chunk class is the set of chunks of the same size. * Free chunk classes are keeped in a list sorted by size. Each chunk class * is keeped in a list too. * Eg. size(2) -> size(8) -> size(20) * for size(2): * chunk1 -> chunk2 -> ... * * header->nextPage points to the next chunk is the same class * header->nextChunk points to the next chunk class. * *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* MSW handles small and large objects differently. A small object is an object whose size is less than 256 bytes. MSW gets pages from allocatePages(). Each page is marked as either SINGLE, when used for small objects, or GROUPED. Each SINGLE page contains only objects of the same exact word size. Each page contains a free list linking all free objects within that page. During the sweep phase any non marked object is released: in the case of a small object, it is added to the free list of the page; otherwise the corresponding set of {\em grouped} pages is added to the set of available pages. Non marked pages can be immediately released without scanning them. Each object has a header which contains a bitmask (telling whether the object is allocated, free or marked) and a pointer to the next free object in the same page. the header is before the object, therefore, when cerating a page of fixed objects of size S, MSW allocates S+OBJ_ALIGNMENT bytes per object. Adding OBJ_ALIGNMENT ensures that the next object is properly aligned. [Since a rounding of S is done entering mswAlloc, one could instead add PtrSize before rounding S and avoid adding OBJ_ALIGNEMENT. Beppe ] *---------------------------------------------------------------------------*/ #include "cmm.h" #include #include #include #include #ifdef unix # include #endif /*---------------------------------------------------------------------------* * :: Verbosity *---------------------------------------------------------------------------*/ #define mswVERBOSE(STMT) WHEN_VERBOSE(CMM_STATS, STMT) /*---------------------------------------------------------------------------* * :: Debug Stuff *---------------------------------------------------------------------------*/ static unsigned long markedBytes = 0; static unsigned long sweptBytes = 0; static unsigned totFreeFPages = 0; static unsigned long totFreeFixedMem = 0; static unsigned long allocSerial = 0; static unsigned long freeSerial = 0; static unsigned long collectSerial = 0; #define gcOut stderr #ifdef NDEBUG # define mswDEBUG(STMT) # define mswTagMemDEBUG(STMT) # define mswSerialDEBUG(STMT) # define mswGcDEBUG(STMT) # define mswCheckDEBUG(STMT) # define mswCondCheckDEBUG(STMT) # define mswTracePageDEBUG(page) # define mswGetStatsDEBUG(STMT) #else int mswGcDebug = 0; int mswCheckDebug = 1; # define mswDEBUG(STMT) STMT # if defined(MSW_DONT_TAG_FREE_MEM) # define mswTagMemDEBUG(STMT) # else # define mswTagMemDEBUG(STMT) STMT # endif /* NOTE: `allocSerial', etc. can be confused with a root */ # if defined(MSW_SERIAL_DEBUG) static unsigned long allocSerialBreak = 0; # define mswSerialDEBUG(STMT) STMT # else # define mswSerialDEBUG(STMT) # endif # define mswGcDEBUG(STMT) if (!mswGcDebug) ; else STMT # if defined(MSW_CHECK_HEAP) # define mswCheckDEBUG(STMT) STMT # define mswCondCheckDEBUG(STMT) if (!mswCheckDebug) ; else STMT # else # define mswCheckDEBUG(STMT) # define mswCondCheckDEBUG(STMT) # endif # if defined(MSW_TRACE_ONE_PAGE) void mswTraceFPage(Ptr page); static Ptr mswTracedPage = NULL; # define mswTracePageDEBUG(pagePtr) \ if (pagePtr) mswTraceFPage(pagePtr) # else # define mswTracePageDEBUG(pagePtr) # endif # if defined(MSW_GET_ALLOC_SIZE_STATS) # define MAX_TRACED_SIZE 4000 static unsigned long totAllocatedSizes [MAX_TRACED_SIZE]; static unsigned long totHugeAllocated = 0; # define mswGetStatsDEBUG(size) \ if ((size) < MAX_TRACED_SIZE) \ totAllocatedSizes[(size)] += 1; \ else \ totHugeAllocated += 1; # else # define mswGetStatsDEBUG(size) # endif #endif /*---------------------------------------------------------------------------* * * :: Macros * *---------------------------------------------------------------------------*/ /******************************* Constants *******************************/ #define MaxFixedSize (bytesPerPage >> 1) - 16 #define PagesRequest 10 #define PtrAlignment sizeof(Ptr) #define PtrSize sizeof(Ptr) /* FirstObjOffset is the offset of the first allocable obj in a page */ #define FirstObjOffset (Word) PTR_ALIGN(sizeof(PageHeaderStruct)+1, \ OBJ_ALIGNMENT) -1 #define AllocMask 0x1 #define MarkMask 0x3 #define FreeMask 0x0 #define OpaqueMask 0xaa #define TransparentMask 0xbb /* Page type: values for the page map */ #define PAGE_Free 0x0 #define PAGE_Fixed 0x1 #define PAGE_Mixed 0x2 #define PAGE_Next 0x3 #define PAGE_Other 0x4 /* Page space: values for the page space */ #define SPACE_Permanent 0 #define SPACE_Temporary 1 #define MSW_TRANSPARENT_OBJ 0 #define MSW_OPAQUE_OBJ 1 #define PageMapInitialSize bytesPerPage * 4 #define MSW_HEAP_PAGES_INC 800 /* When using debug options a memory object is filled with EMPTY_MEM_TAG value * when is allocated and with RELEASED_MEM_TAG when is released during a * collection. * If there is an attempt of using a free memory object, it should be easy to * understand if the mem obj has been released during a collection. */ #define EMPTY_MEM_TAG 0xee #define RELEASED_MEM_TAG 0xdd #define PAGE_START(ptr) (Ptr)((Word)(ptr) & ~(bytesPerPage - 1)) #define PTR_ALIGN(ptr, align) \ (Ptr)(((Word)((Ptr)(ptr)-1)+(align)) & ~((align)-1)) #define ROUND_UP(n, b) (Word) PTR_ALIGN((n),(b)) #define ROUND_DOWN(n, b) (Word) ((Word)(n) & ~((b) -1)) #define IS_INSIDE_HEAP(p) \ ((Ptr)(p) < heapEnd && (Ptr)(p) >= heapStart) #define GET_OBJ_BASE(ptr, header) \ (Ptr)((Word)header + header->basePointerv[(Word)(ptr)-(Word)header]) #define PAGE_INFO(p) pageMap[GCPtoPage(p)] #define PAGE_SPACE(p) pageSpace[GCPtoPage(p)] #define NEXT_FREE_OBJ(p) *(Ptr *)((Ptr)(p) + 1) #define SET_NEXT_FREE_OBJ(p, obj) *(Ptr *)((Ptr)(p) + 1) = (obj) #define isAvailFPage(p) (((PageHeader)(p))->nextPage != NULL) #define isFullFPage(p) (((PageHeader)(p))->freeList == NULL) /* Address of last obj that can be allocated in "page" (fixed) */ #define GET_LAST_OBJ_PTR(pg,size) \ (Ptr)(pg) + bytesPerPage - ((size) + OBJ_ALIGNMENT) /* pageLink is a vector defined by CMM. Other heaps use it for other purposes. * Here it is renamed to pageMap because this name is more appropriate and * helps reading the code. */ #define pageMap pageLink // Max number of pages for a chunk (currently used for debugging only) #define MAX_CHUNK_PAGES 50000 /*---------------------------------------------------------------------------* * * :: Type Definitions * *---------------------------------------------------------------------------*/ /****** PageHeader ******/ typedef struct pageHeaderStruct * PageHeader; typedef struct pageHeaderStruct { Word objSize; /* Size of objects allocated in this page */ Ptr * basePointerv; PageHeader nextPage; /* Next page with some free objects */ Ptr freeList; /* First free obj in this page */ int allocatedObjs; int nPages; /* >0 only for mixed objects */ char isMarked; /* The whole page is marked? */ char isOpaque; /* Only for mixed objs. 1 => don't traverse */ } PageHeaderStruct; /****** FreePageHeader ******/ typedef struct freePageHeaderStruct * FreePageHeader; typedef struct freePageHeaderStruct { FreePageHeader nextChunk; /* Next page of same chunk size */ FreePageHeader nextChunkGroup; int nPages; } FreePageHeaderStruct; /****** FPageInfoStruct ******/ struct FPagesInfoStruct { Word firstObjOffset; Ptr * basePointerv; int objectsPerPage; }; /*---------------------------------------------------------------------------* * * :: TempHeap Typedef & Globals * *---------------------------------------------------------------------------*/ #define MAX_ROOT 30 typedef struct TempHeapInfoStruct * TempHeapInfo; struct TempHeapInfoStruct { Ptr roots[MAX_ROOT]; int nRoots; PageHeader availFPages[MaxFixedSize]; TempHeapInfo previous; }; static TempHeapInfo tempHeapInfo = NULL; static int mustResetTempHeap = 0; static int noCollection = 0; #define mswDisableCollection() (noCollection = 1) #define mswEnableCollection() (noCollection = 0) #define mswIsCollectionDisabled() (noCollection) /*---------------------------------------------------------------------------* * * :: MarkStack Typedef & Globals * *---------------------------------------------------------------------------*/ typedef struct MarkStackFrameStruct * MarkStackFrame; struct MarkStackFrameStruct { MarkStackFrame previous; MarkStackFrame next; }; #define MarkStackFramePages 8 #define MarkStackPush(OBJ) \ { *(Ptr*)markStackTop = (Ptr) (OBJ); \ markStackTop += PtrSize; \ if (markStackTop == markStackHeadroom) mswExpandMarkStack(); } #define MarkStackPop(VAR) \ { if (markStackTop == markStackBase) { \ theMarkStack = theMarkStack->previous; \ markStackHeadroom = (Ptr) theMarkStack + MarkStackFramePages * bytesPerPage; \ markStackTop = markStackHeadroom - PtrSize; \ markStackBase = (Ptr) theMarkStack + sizeof(MarkStackFrameStruct); \ } \ else \ markStackTop -= PtrSize; \ VAR = *(GCP *)markStackTop; } #define MarkStackIsEmpty() \ (markStackTop == markStackBase && theMarkStack->previous == NULL) static MarkStackFrame theMarkStack; static Ptr markStackTop; static Ptr markStackHeadroom; static Ptr markStackBase; /*---------------------------------------------------------------------------* * * :: Global Variables * *---------------------------------------------------------------------------*/ struct FPagesInfoStruct FPagesInfo [MaxFixedSize]; static PageHeader availFPages [MaxFixedSize]; static unsigned totFreePages = 0; /***** freeChunks *****/ static FreePageHeader freeChunks = NULL; static int totReleasedPages = 0; /***** Memory Sections *****/ static Ptr stackStart; static Ptr stackEnd; static Ptr dataStart; static Ptr dataEnd; static Ptr heapStart = (Ptr) -1; static Ptr heapEnd = NULL; extern int end; /* Compiler defined, end of data segment */ /*---------------------------------------------------------------------------* * :: Timings *---------------------------------------------------------------------------*/ #if defined(MSW_SHOW_TIMINGS) # ifdef sgi /* System V */ # include # 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 mswGetPages (int nPages, Word size); static PageHeader mswSetupFPage (Ptr page, Word size); static void mswFreeChunk (PageHeader); static void mswAddToFreeChunksAndMap (Ptr chunk, int nPages); static void mswAddToFreeChunks (Ptr chunk, int nPages); static Ptr mswGetBestFitChunk (int nPages); static void mswRemoveFromFreeChunks (FreePageHeader chunk); static void mswPageMapSetRange (Ptr, Ptr, unsigned); static void mswPageMapSet (Ptr, int, unsigned); static void mswPageSpaceSetRange (Ptr, Ptr); static void mswPageSpaceSetRangeTo (Ptr, Ptr, short); static void mswPageSpaceSet (Ptr, int); static void mswCheckFreeChunks (void); /*---------------------------------------------------------------------------* * :: mswSelect * * -- interface for C * *---------------------------------------------------------------------------*/ void mswSelect() { Cmm::heap = Cmm::theMSHeap; } /*---------------------------------------------------------------------------* * :: mswAlloc *---------------------------------------------------------------------------*/ void * mswAlloc(unsigned long size) { Ptr freeList; PageHeader freePage; Ptr ret; mswSerialDEBUG({ if (allocSerial++ == allocSerialBreak) allocSerialBreak = allocSerial; /*** PLACE A BREAKP. HERE ***/ }); mswTracePageDEBUG(mswTracedPage); # if defined(MSW_ALLOC_ZERO_OK) if (size == 0) size = 4; # endif assert(size); size = ROUND_UP(size, PtrSize); mswGetStatsDEBUG(size); if (size >= MaxFixedSize) return mswAllocChunk(size, MSW_TRANSPARENT_OBJ); /**** allocate an object from pool(size) ****/ freePage = availFPages[size]; assert(freePage != NULL); assert(freePage->objSize == size); freeList = freePage->freeList; freePage->allocatedObjs += 1; *freeList = AllocMask; *(Byte *)(freeList-1) = TransparentMask; // Following assignment is needed because subsequent call to // mswAllocFPage might release completely "freePage". // This ensures that there is at least one live object. ret = freeList + 1; freePage->freeList = NEXT_FREE_OBJ(freeList); if (freePage->freeList == NULL && (availFPages[size] = freePage->nextPage) == NULL) mswAllocFPage(size); assert(freeList); assert(freePage->freeList == NULL || ((Ptr) freePage->freeList > (Ptr) freePage && (Ptr) freePage->freeList < (Ptr) freePage + bytesPerPage)); mswTracePageDEBUG(mswTracedPage); return ret; } /*---------------------------------------------------------------------------* * :: mswAllocOpaque * * Allocates an object that is guaranteed to do not contain pointers. * Useful only for big chunks, that are not traversed during the collection. * *---------------------------------------------------------------------------*/ void * mswAllocOpaque(unsigned long size) { if (size < MaxFixedSize) { Ptr ret = (Ptr)mswAlloc(size); *(Byte *)(ret-2) = OpaqueMask; return ret; } else return mswAllocChunk(size, MSW_OPAQUE_OBJ); } /*---------------------------------------------------------------------------* * :: mswAllocFPage * * Return a pointer to a free fixed list for "size". * The code looks obscure because mswAllocPages() can cause a collection * that can add pages to availFPages[]. *---------------------------------------------------------------------------*/ static PageHeader mswAllocFPage(Word size) { Ptr page; page = mswAllocPages(1, size); if (availFPages[size] == NULL) { assert(page); availFPages[size] = mswSetupFPage(page, size); } return availFPages[size]; } /*---------------------------------------------------------------------------* * :: mswShouldExpandHeap * * Called after a GC. Return 1 if the heap should be expanded. Note that an * expansion might be request even if we found enough free pages after a GC. *---------------------------------------------------------------------------*/ #define GC_MAX_BUSY_MEM 10 static int mswShouldExpandHeap(void) { int percBusyMem; if (markedBytes == 0) return 0; // We didn't collect Word heapSize = ((Word)lastHeapPage - firstHeapPage) * bytesPerPage; percBusyMem = (100 * markedBytes) / heapSize; markedBytes = 0; mswDEBUG(fprintf(stdout, " %d\% busy memory ", percBusyMem);); if (percBusyMem > GC_MAX_BUSY_MEM) { mswDEBUG(fprintf(stdout, "-> expand heap\n");); return 1; } else { mswDEBUG(fprintf(stdout, "-> not expand heap\n");); return 0; } } /*---------------------------------------------------------------------------* * :: mswGetPages * * Return a chunk of "nPages" consecutives pages, getting them from a * garbage collection or from the operating system. * "size" is 0 if the pages are mixed. * Since more than requested pages can be allocated, the remaining chunk is * added to freeChunks. * NOTE: the pageMap is updated only for extra chunks. * NOTE that when mswGetPages is called no chunk of "nPages" size is * currently available. * NOTE: a NULL value is returned only if no memory is available. * *---------------------------------------------------------------------------*/ #define HAS_ENOUGH_PAGES(npages) (lastHeapPage - firstFreePage >= (npages) + 1) static Ptr mswExpandHeap(int); static Ptr mswGetPages(int nPages, Word size) { Ptr newPages; mswCollect(); /* Expand anyway if not found enough free pages */ if (mswShouldExpandHeap()) { newPages = mswExpandHeap(MSW_HEAP_PAGES_INC); mswAddToFreeChunksAndMap(newPages, MSW_HEAP_PAGES_INC); } /* Found free objects after collection? */ if (size != 0 && availFPages[size]) { mswDEBUG(fprintf(gcOut, "Found enough objects after gc!\n")); return NULL; /* <------------ */ } /* Try if the request can be satisfied after GC */ newPages = mswGetBestFitChunk(nPages); /* Found a free chunk after collection ? */ if (newPages) { mswDEBUG(fprintf(gcOut, "Found enough pages after gc!\n")); return newPages; /* <----------- */ } mswDEBUG(fprintf(gcOut, "[H]")); return mswExpandHeap(nPages); } /*---------------------------------------------------------------------------* * :: mswExpandHeap *---------------------------------------------------------------------------*/ static Ptr mswExpandHeap(int nPages) { Ptr newPages; int pagesRequest = nPages; int lastPage = GCPtoPage(heapEnd) - 1; Word bytesRequest; newPages = (Ptr) allocatePages(pagesRequest, Cmm::theMSHeap); bytesRequest = pagesRequest * bytesPerPage; /* Check that allocatePages() returns an aligned address */ assert(newPages == PAGE_START(newPages)); pagesRequest = bytesRequest / bytesPerPage; assert(heapStart <= newPages); if (heapEnd < newPages) { mswPageMapSetRange(heapEnd, newPages - 1, PAGE_Other); mswPageSpaceSetRangeTo(heapEnd,newPages-1, SPACE_Permanent); } if (heapEnd < newPages + bytesRequest) heapEnd = newPages + bytesRequest; mswPageSpaceSet(newPages, nPages); return newPages; } /*---------------------------------------------------------------------------* * :: mswSetupFPages *---------------------------------------------------------------------------*/ static PageHeader mswSetupFPage(Ptr page, Word size) { PageHeader header = (PageHeader) page; Ptr firstObj, lastObj, p; Word size1 = size + OBJ_ALIGNMENT; assert(FPagesInfo[size].basePointerv); header->objSize = size; header->basePointerv = FPagesInfo[size].basePointerv; header->allocatedObjs = 0; header->nextPage = NULL; header->nPages = 1; header->isMarked = 0; firstObj = page + FPagesInfo[size].firstObjOffset; lastObj = GET_LAST_OBJ_PTR(page, size); header->freeList = firstObj; for (p = firstObj; p <= lastObj; p += size1) { *p = 0; /* mark and alloc info */ SET_NEXT_FREE_OBJ(p, p + size1); /* Next free list item */ mswTagMemDEBUG({ Ptr pd; for (pd = p + 1 + sizeof(Ptr); pd < p + 1 + size; pd++) *pd = EMPTY_MEM_TAG; }); } SET_NEXT_FREE_OBJ(p - size1, NULL); /* Last item has no tail */ pageMap[GCPtoPage(p)] = PAGE_Fixed; return header; } /*---------------------------------------------------------------------------* * :: mswRemoveAvailFPage * * NOTE: here a page is always removed because the caller will always free * the page. *---------------------------------------------------------------------------*/ static void mswRemoveAvailFPage(PageHeader header) { PageHeader page = availFPages[header->objSize]; if (page == header) { availFPages[header->objSize] = header->nextPage; return; /* <--------- */ } /* Note: page can be NULL if in tempHeapInfo->availFPages[] */ while (page != NULL) { if (page->nextPage == header) break; page = page->nextPage; } /* NOTE: we put following test here and not at the beginning of the * function because this situation can happen only when there is a * collection with a tempHeap active, so this is a very rare event. */ if (page == NULL) { /* Remove page from tempHeapInfo->availFPages */ assert(tempHeapInfo); assert(pageSpace[GCPtoPage(header)] == SPACE_Permanent); page = tempHeapInfo->availFPages[header->objSize]; if (page == header) { tempHeapInfo->availFPages[header->objSize] = header->nextPage; return; /* <--------- */ } do { if (page->nextPage == header) break; page = page->nextPage; } while (page != NULL); } assert(page); page->nextPage = header->nextPage; } /*---------------------------------------------------------------------------* * :: mswFree *---------------------------------------------------------------------------*/ void mswFree(void * p) { PageHeader header = (PageHeader) PAGE_START(p); Word size = header->objSize; mswSerialDEBUG(freeSerial += 1;); /* NOp when tempHeap active. * !! Move first 2 assignments after this if */ if (tempHeapInfo) return; if (header->objSize >= MaxFixedSize) { mswFreeChunk(header); return; /* <-------- */ } mswTracePageDEBUG(mswTracedPage); assert(p == GET_OBJ_BASE(p, header) + 1); assert((Ptr)header != p); assert(IS_INSIDE_HEAP(p)); assert(header->allocatedObjs); header->allocatedObjs -= 1; /* !! Should call mswFreePage(header) if == 0; but this requires * objs allocated in page-based sublists, otherwise it is not possible * to remove free objs from their lists. */ if (isFullFPage(header)) { /* Add to the list of fixed pages having at least a free * object. */ header->nextPage = availFPages[size]; availFPages[size] = header; } if (header->allocatedObjs == 0 && isAvailFPage(header)) { /* Release this page completely */ mswRemoveAvailFPage(header); mswFreeChunk(header); } else { /* Simply add the released obj to the local freeList */ *(Ptr *)p = header->freeList; p = (Ptr)p-1; header->freeList = (Ptr) p; *(Ptr)p = 0; /* Remove allocation mark */ } /* totFreeFixedMem += size; */ mswTagMemDEBUG({ Ptr pd; for (pd = (Ptr)p +1+sizeof(Ptr); pd < (Ptr)p +1+size; pd++) *pd = RELEASED_MEM_TAG; }); } /*---------------------------------------------------------------------------* * :: mswGetObjSize * * Given a pointer to an allocated object, return the size of the object. * Remember that, for instance, if you allocate a 20 bytes object, 24 bytes * are allocated. *---------------------------------------------------------------------------*/ unsigned long mswGetObjSize(void * ptr) { int pageInfo = PAGE_INFO(ptr); PageHeader page = (PageHeader) PAGE_START(ptr); assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed); return page->objSize; } /*---------------------------------------------------------------------------* * :: mswGetRealObjSize * * Given a pointer to an allocated object, return the real size of the object, * i.e. the amount of memory allocated for the object. The difference with * mswGetObjSize() is only for mixed pages. * *---------------------------------------------------------------------------*/ static unsigned long mswGetRealObjSize(void * ptr) { int pageInfo = PAGE_INFO(ptr); PageHeader page = (PageHeader) PAGE_START(ptr); assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed); if (pageInfo == PAGE_Fixed) return page->objSize; else return (page->nPages * bytesPerPage) - FirstObjOffset -1; } /*---------------------------------------------------------------------------* * :: mswRealloc * * Re-allocate a previously allocated block * *---------------------------------------------------------------------------*/ void * mswRealloc(void * p, unsigned long size) { unsigned long realSize = mswGetRealObjSize(p); Ptr newPtr; PageHeader page; if (realSize >= size) { /* Size of mixed objects must be updated because during * the mark phase we traverse only header->objSize bytes. */ if (PAGE_INFO(p) == PAGE_Mixed) { page = (PageHeader) PAGE_START(p); page->objSize = size; } return p; /* <---------- */ } else { newPtr = (Ptr)mswAlloc(size); /* If obj is opaque, then keep it opaque */ if (size < MaxFixedSize) *(newPtr-2) = *((Ptr)p-2); else { PageHeader newHead = (PageHeader) ROUND_DOWN(newPtr, bytesPerPage); PageHeader oldHead = (PageHeader) ROUND_DOWN(p, bytesPerPage); newHead->isOpaque = oldHead->isOpaque; } memcpy(newPtr, p, realSize); mswFree(p); return newPtr; } } /*---------------------------------------------------------------------------* * :: mswCalloc(n, size) * * Allocates "n" elements of size "size", all initialized to 0. * *---------------------------------------------------------------------------*/ void * mswCalloc(unsigned long n, unsigned long size) { void * mem = mswAlloc(n * size); return memset(mem, 0, n * size); } /*---------------------------------------------------------------------------* * * :: PageMap * *---------------------------------------------------------------------------*/ /* Mark pages in ["from".."to"] with "type". * NOTE: "to" is included in range. */ static void mswPageMapSetRange(Ptr from, Ptr to, unsigned type) { Word l; Word h; register Word k; l = GCPtoPage(from); h = GCPtoPage(to); for (k = l; k <= h; k++) pageMap[k] = type; } /* Mark "nPages" pages starting from "pageStart" with "type" */ static void mswPageMapSet(Ptr pageStart, int nPages, unsigned type) { int index = GCPtoPage(pageStart); while (nPages--) pageMap[index++] = type; } /*---------------------------------------------------------------------------* * * :: PageSpace * *---------------------------------------------------------------------------*/ static void mswPageSpaceSetRange(Ptr from, Ptr to) { Word l; Word h; short type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent); register Word k; l = GCPtoPage(from); h = GCPtoPage(to); for (k = l; k <= h; k++) pageSpace[k] = type; } static void mswPageSpaceSetRangeTo(Ptr from, Ptr to, short type) { Word l; Word h; register Word k; assert(type == SPACE_Permanent || type == SPACE_Temporary); l = GCPtoPage(from); h = GCPtoPage(to); for (k = l; k <= h; k++) pageSpace[k] = type; } static void mswPageSpaceSet(Ptr pageStart, int nPages) { int index = GCPtoPage(pageStart); short type = (tempHeapInfo ? SPACE_Temporary : SPACE_Permanent); while (nPages--) pageSpace[index++] = type; } static void mswPageSpaceSetTo(Ptr pageStart, int nPages, short type) { int index = GCPtoPage(pageStart); assert(type == SPACE_Permanent || type == SPACE_Temporary); while (nPages--) pageSpace[index++] = type; } /*---------------------------------------------------------------------------* * * :: Free Chunks Management * *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* * :: mswAddToFreeChunks * * Add "chunk" to the list of free chunks. "nPages" is the chunk size. * NOTE: does not update pageMap[], to optimize cases in which it is already * updated. See mswAddToFreeChunksAndMap(). * *---------------------------------------------------------------------------*/ static void mswAddToFreeChunks(Ptr ptr, int nPages) { FreePageHeader chunks = freeChunks; FreePageHeader *pPrev = &freeChunks; FreePageHeader chunk = (FreePageHeader) ptr; chunk->nPages = nPages; totFreePages += nPages; mswTagMemDEBUG({ Ptr p; Ptr end = ptr + (nPages * bytesPerPage); for (p = ptr + sizeof(FreePageHeaderStruct) + 1; p < end; p++) *p = RELEASED_MEM_TAG; }); if (!chunks) { chunk->nextChunk = NULL; chunk->nextChunkGroup = NULL; freeChunks = chunk; return; /* <---- */ } while (chunks) { if (chunks->nPages == nPages) { *pPrev = chunk; chunk->nextChunk = chunks; chunk->nextChunkGroup = chunks->nextChunkGroup; return; /* <---- */ } else if (chunks->nPages > nPages) { *pPrev = chunk; chunk->nextChunk = NULL; chunk->nextChunkGroup = chunks; return; /* <---- */ } pPrev = &(chunks->nextChunkGroup); chunks = chunks->nextChunkGroup; } /* This point is reached if this is the maximum chunk. * Add the chunk to the tail of the list. */ *pPrev = chunk; chunk->nextChunk = NULL; chunk->nextChunkGroup = NULL; } /*---------------------------------------------------------------------------* * :: mswAddToFreeChunksAndMap * * As mswAddToFreeChunks(), but the pageMap[] is updated. * *---------------------------------------------------------------------------*/ static void mswAddToFreeChunksAndMap(Ptr chunk, int nPages) { mswAddToFreeChunks(chunk, nPages); mswPageMapSet(chunk, nPages, PAGE_Free); mswTagMemDEBUG({ Ptr p = (Ptr)chunk + FirstObjOffset + 1; for (;p < (Ptr)chunk + nPages * bytesPerPage; p++) *p = EMPTY_MEM_TAG; }); } /*---------------------------------------------------------------------------* * :: mswBreakAndAllocChunk * * "chunk" is the block to be allocated. * *---------------------------------------------------------------------------*/ static Ptr mswBreakAndAllocChunk(FreePageHeader chunk, FreePageHeader * pPrev, int nPages) { int nExtraPages; FreePageHeader extraChunk; /* Remove the chunk from the chunk list */ if (chunk->nextChunk == NULL) *pPrev = chunk->nextChunkGroup; else { *pPrev = chunk->nextChunk; chunk->nextChunk->nextChunkGroup = chunk->nextChunkGroup; } totFreePages -= chunk->nPages; if (chunk->nPages > nPages) { nExtraPages = chunk->nPages - nPages; extraChunk = (FreePageHeader)((Ptr)chunk + nPages * bytesPerPage); mswAddToFreeChunks((Ptr)extraChunk, nExtraPages); } /* If we are in the copying phase (tempHeap ended by not destroyed) * we must promote temporary pages. */ if (mustResetTempHeap) mswPageSpaceSet((Ptr) chunk, nPages); return (Ptr) chunk; } /*---------------------------------------------------------------------------* * :: mswGetBestFitChunk * * Walks through the list of free chunks finding the one that best satisfies * the request, returning NULL if cannot find a so big chunk. * If the chunk is found, it is removed from the free list. Spare pages are * reinserted in the free list. * *---------------------------------------------------------------------------*/ static Ptr mswGetBestFitChunk(int nPages) { FreePageHeader chunks = freeChunks; FreePageHeader *pPrev = &freeChunks; while (chunks) { if (chunks->nPages >= nPages) return mswBreakAndAllocChunk(chunks, pPrev, nPages); pPrev = &(chunks->nextChunkGroup); chunks = chunks->nextChunkGroup; } return NULL; } /*---------------------------------------------------------------------------* * :: mswRemoveFromFreeChunks *---------------------------------------------------------------------------*/ static void mswRemoveFromFreeChunks(FreePageHeader chunk) { FreePageHeader chunks = freeChunks; FreePageHeader *pPrev = &freeChunks; int nPages = chunk->nPages; totFreePages -= nPages; while (chunks) { if (chunks->nPages == nPages) break; pPrev = &(chunks->nextChunkGroup); chunks = chunks->nextChunkGroup; } if (chunks == chunk) { if (chunk->nextChunk) { *pPrev = chunk->nextChunk; chunk->nextChunk->nextChunkGroup = chunk->nextChunkGroup; } else *pPrev = chunk->nextChunkGroup; return; } do { assert(chunks); pPrev = &(chunks->nextChunk); chunks = chunks->nextChunk; } while (chunks != chunk); assert(chunks); *pPrev = chunk->nextChunk; } /*---------------------------------------------------------------------------* * :: mswMergeChunkWithNeighbors * * Given a chunk that is going to be released, look at its neighbors and merge * it into a bigger chunk if possible. * Return the pointer to the new chunk and "pNPages" is updated to the new * size * *---------------------------------------------------------------------------*/ static Ptr mswMergeChunkWithNeighbors(Ptr chunk, int* pNPages) { int nPages = *pNPages; Page baseIndex = GCPtoPage(chunk); Page limitIndex= GCPtoPage(heapEnd); Page index = baseIndex; Ptr newChunk = chunk; FreePageHeader followChunk; while (index > firstHeapPage) { if (pageMap[index-1] != PAGE_Free) break; nPages++; index--; } /* "index" is the index of the first page of the previous free chunk.*/ if (index != baseIndex) { newChunk = (Ptr)pageToGCP(index); mswRemoveFromFreeChunks((FreePageHeader)newChunk); } index = baseIndex + *pNPages; /* A free chunk follows the current chunk? */ if (index < limitIndex && pageMap[index] == PAGE_Free) { followChunk = (FreePageHeader) pageToGCP(index); nPages += followChunk->nPages; mswRemoveFromFreeChunks(followChunk); } *pNPages = nPages; return newChunk; } /*---------------------------------------------------------------------------* * :: mswAllocChunk * * Alloc a chunk of "size" bytes. A chunk is allocated only if it is bigger * than maximum fixed object. *---------------------------------------------------------------------------*/ static Ptr mswAllocChunk(unsigned long size, unsigned type) { int nPages = (FirstObjOffset + size + bytesPerPage) / bytesPerPage; int index; Ptr p; p = mswAllocPages(nPages, 0); ((PageHeader)p)->objSize = size; ((PageHeader)p)->basePointerv = NULL; ((PageHeader)p)->nPages = nPages; ((PageHeader)p)->allocatedObjs= 1; ((PageHeader)p)->isMarked = 0; ((PageHeader)p)->isOpaque = (type == MSW_OPAQUE_OBJ); /* Mark pages in pageMap */ index = GCPtoPage(p); pageMap[index] = PAGE_Mixed; while (--nPages) pageMap[++index] = PAGE_Next; return p + FirstObjOffset + 1; } /*---------------------------------------------------------------------------* * :: mswAllocPages(nPages, size) * * Alloc "nPages" consecutive pages from freeChunks; if no available chunk * can satisfy the request, mswGetPages() is called. * "size" is 0 if the page is for mixed objects, else the size of fixed * objects. This value is passed to mswGetPages() to decide if * we have enough room after a collection. * *---------------------------------------------------------------------------*/ static Ptr mswAllocPages(int nPages, Word size) { Ptr page = mswGetBestFitChunk(nPages); if (page == NULL) page = mswGetPages(nPages, size); if (tempHeapInfo && page) { int pg = GCPtoPage(page); int lastPg = pg + nPages; do pageSpace[pg++] = SPACE_Temporary; while (pg != lastPg); } return page; } /*---------------------------------------------------------------------------* * :: mswQuickFreeChunk * * Free a chunk of "totReleasedPages" preceding "p". * Used during sweep phase. A global variable is used because of efficiency * required. * Details: When a fixed page or a group of mixed pages is released during * sweep phase we avoid an expensive call to mswFreeChunk(), but we count the * number of consecutive pages (totReleasedPages) and as soon as we find a * page that is not released we call mswQuickFreeChunk() to release the * whole chunk of consecutive pages. *---------------------------------------------------------------------------*/ static void mswQuickFreeChunk(Ptr p) { assert(totReleasedPages != 0); p = p - (totReleasedPages * bytesPerPage); mswPageMapSet(p, totReleasedPages, PAGE_Free); if (tempHeapInfo) mswPageSpaceSetTo(p, totReleasedPages, SPACE_Permanent); p = mswMergeChunkWithNeighbors(p, &totReleasedPages); /* Add to freeChunks */ mswAddToFreeChunks(p, totReleasedPages); totReleasedPages = 0; } /*---------------------------------------------------------------------------* * :: mswFreeChunk * * Implementation Note: the page map is marked before the chunk is merged. * This because if the chunk will be merged, its neighbor(s) are already * marked with PAGE_Free. *---------------------------------------------------------------------------*/ static void mswFreeChunk(PageHeader header) { int nPages = header->nPages; assert(nPages > 0 && nPages < MAX_CHUNK_PAGES); mswPageMapSet((Ptr)header, nPages, PAGE_Free); assert(tempHeapInfo == NULL); // if (tempHeapInfo) // mswPageSpaceSetTo((Ptr)header, nPages, SPACE_Permanent); header = (PageHeader) mswMergeChunkWithNeighbors((Ptr)header, &nPages); /* Add to freeChunks */ mswAddToFreeChunks((Ptr) header, nPages); } /*---------------------------------------------------------------------------* * * :: Mark and Sweep * *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* * :: mswMark *---------------------------------------------------------------------------*/ static void mswMarkFromTo(GCP from, GCP to); static void mswExpandMarkStack(void); extern char ** environ; static void mswMark(void) { jmp_buf regs; int dummy = 0; static void * mmenv = NULL; /* ensure flushing of register caches */ if (_setjmp(regs) == 0) _longjmp(regs, 1); if (!mmenv) # if defined(STACKBOTTOM) mmenv = (void *)((char *)STACKBOTTOM-1); # else mmenv = environ; # endif stackStart = (Ptr) mmenv; stackEnd = (Ptr) &dummy; if (stackStart > stackEnd) { Ptr tmp = stackStart; stackStart = stackEnd; stackEnd = tmp; } mswVERBOSE(markedBytes = 0;); mswMarkFromTo((GCP)stackStart, (GCP)stackEnd); mswGcDEBUG(fprintf(gcOut, " (%lu marked from stack)", markedBytes);); CmmExamineStaticAreas(mswMarkFromTo); } unsigned maxDepth = 0; unsigned currDepth = 0; #ifdef MSW_RECURSIVE_MARK static void mswMarkFromTo(GCP from, GCP to) { GCP pt; Ptr p; Ptr bp; static PageHeader header; assert(from < to); for (pt = from; pt < to; pt++) { p = *(Ptr *)pt; if (! IS_INSIDE_HEAP(p)) continue; switch (PAGE_INFO(p)) { case PAGE_Fixed: header = (PageHeader) PAGE_START(p); bp = GET_OBJ_BASE(p, header); /* Consider only allocated objs not marked. */ if (*bp != AllocMask) continue; /* Mark this object */ *bp = MarkMask; mswVERBOSE(markedBytes += header->objSize;); /* Mark this page */ header->isMarked = 1; /* If opaque, don't traverse it */ assert(*(bp-1) == OpaqueMask || *(bp-1) == TransparentMask); if (*(Byte *)(bp-1) == OpaqueMask) continue; mswMarkFromTo((GCP)(bp+1), (GCP)(bp + header->objSize +1)); break; case PAGE_Mixed: p = (Ptr) ROUND_DOWN(p, bytesPerPage); LAB_PageMixed: /* Here `p' must point to the top of the page */ if (((PageHeader)p)->isMarked) continue; header = (PageHeader) p; /* Mark the whole page */ header->isMarked = 1; mswVERBOSE(markedBytes += header->nPages * bytesPerPage;); /* If opaque, don't traverse it */ if (((PageHeader)p)->isOpaque) continue; p += FirstObjOffset + 1; mswMarkFromTo((GCP)p, (GCP)(p + header->objSize)); break; case PAGE_Next: int index = GCPtoPage(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = (Ptr)pageToGCP(index); goto LAB_PageMixed; } } } #elif MSW_BREAD_FIRST static void mswMarkFromTo(GCP from, GCP to) { GCP pt; Ptr p; Ptr bp; static PageHeader header; assert(from < to); Mark_Loop: for (pt = from; pt < to; pt++) { p = *(Ptr *)pt; if (! IS_INSIDE_HEAP(p)) continue; switch(PAGE_INFO(p)) { PAGE_Fixed: header = (PageHeader) PAGE_START(p); bp = GET_OBJ_BASE(p, header); /* Consider only allocated objs not marked. */ if (*bp != AllocMask) continue; /* Mark this object */ *bp = MarkMask; markedBytes += header->objSize; /* Mark this page */ header->isMarked = 1; /* If opaque, don't traverse it */ assert(*(bp-1) == OpaqueMask || *(bp-1) == TransparentMask); if (*(Byte *)(bp-1) == OpaqueMask) continue; MarkStackPush((GCP)(bp+1)); PAGE_Mixed: p = (Ptr) ROUND_DOWN(p, bytesPerPage); LAB_PageMixed: /* Here `p' must point to the top of the page */ if (((PageHeader)p)->isMarked) continue; header = (PageHeader) p; /* Mark the whole page */ header->isMarked = 1; markedBytes += header->nPages * bytesPerPage; /* If opaque, don't traverse it */ if (((PageHeader)p)->isOpaque) continue; p += FirstObjOffset + 1; MarkStackPush((GCP)(bp+1)); PAGE_Next: int index = GCPtoPage(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = (Ptr)pageToGCP(index); goto LAB_PageMixed; } assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other); if (MarkStackIsEmpty()) return; // <<------------- MarkStackPop(from); assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other); assert(IS_INSIDE_HEAP(from)); to = from + PageHeader(PAGE_START(from))->objSize; goto Mark_Loop; } } #else // DEPTH-FIRST static void mswMarkFromTo(GCP from, GCP to) { GCP pt; Ptr p; Ptr bp; static PageHeader header; assert(from < to); Mark_Loop: for (pt = from; pt < to; pt++) { p = *(Ptr *)pt; if (! IS_INSIDE_HEAP(p)) continue; switch (PAGE_INFO(p)) { case PAGE_Fixed: header = (PageHeader) PAGE_START(p); bp = GET_OBJ_BASE(p, header); /* Consider only allocated objs not marked. */ if (*bp != AllocMask) continue; /* Mark this object */ *bp = MarkMask; markedBytes += header->objSize; /* Mark this page */ header->isMarked = 1; /* If opaque, don't traverse it */ assert(*(bp-1) == OpaqueMask || *(bp-1) == TransparentMask); if (*(Byte *)(bp-1) == OpaqueMask) continue; MarkStackPush(pt+1); MarkStackPush(to); from = (GCP)(bp+1); to = (GCP)(bp + header->objSize +1); goto Mark_Loop; case PAGE_Mixed: p = (Ptr) ROUND_DOWN(p, bytesPerPage); LAB_PageMixed: /* Here `p' must point to the top of the page */ if (((PageHeader)p)->isMarked) continue; header = (PageHeader) p; /* Mark the whole page */ header->isMarked = 1; markedBytes += header->nPages * bytesPerPage; /* If opaque, don't traverse it */ if (((PageHeader)p)->isOpaque) continue; p += FirstObjOffset + 1; MarkStackPush(pt+1); MarkStackPush(to); from = (GCP) p; to = (GCP) (p + header->objSize); goto Mark_Loop; case PAGE_Next: { int index = GCPtoPage(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = (Ptr)pageToGCP(index); goto LAB_PageMixed; } } } assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other); if (MarkStackIsEmpty()) return; // <<------------- MarkStackPop(to); MarkStackPop(from); assert(pageMap[GCPtoPage(markStackTop)] == PAGE_Other); goto Mark_Loop; } #endif /* MSW_RECURSIVE_MARK */ /*---------------------------------------------------------------------------* * :: mswExpandMarkStack() *---------------------------------------------------------------------------*/ static void mswExpandMarkStack() { MarkStackFrame newFrame; if (theMarkStack->next == NULL) { newFrame = (MarkStackFrame) mswGetPages(MarkStackFramePages, 0); theMarkStack->next = newFrame; newFrame->previous = theMarkStack; newFrame->next = NULL; mswPageMapSet((Ptr) newFrame, MarkStackFramePages, PAGE_Other); } else newFrame = theMarkStack->next; theMarkStack = newFrame; markStackTop = (Ptr) theMarkStack + sizeof(MarkStackFrameStruct); markStackHeadroom = (Ptr) theMarkStack + MarkStackFramePages * bytesPerPage; markStackBase = markStackTop; } /*---------------------------------------------------------------------------* * :: mswSweep functions *---------------------------------------------------------------------------*/ static void mswSweepFPage(Ptr page) { Word size = ((PageHeader)page)->objSize; Ptr p; Word size1 = size + OBJ_ALIGNMENT; int released = 0; Ptr lo = page + FPagesInfo[size].firstObjOffset; Ptr hi = GET_LAST_OBJ_PTR(page, size); Ptr fixedFreeList = ((PageHeader)page)->freeList; int wasFull = (fixedFreeList == NULL); if (((PageHeader)page)->isMarked == 0) { if (!isFullFPage(page)) /* A full page cannot be available */ mswRemoveAvailFPage((PageHeader)page); totReleasedPages += 1; mswVERBOSE(totFreeFPages += 1;); mswVERBOSE(sweptBytes += bytesPerPage;); return; /* <-------- */ } else ((PageHeader)page)->isMarked = 0; for (p = lo; p <= hi; p += size1) { if (*p == (MarkMask | AllocMask)) { *p = AllocMask; continue; } /* Found a free obj */ if (*p == FreeMask) { mswDEBUG(totFreeFixedMem += size;); continue; } assert(*p == AllocMask); *p = FreeMask; *(Ptr *)(p+1) = fixedFreeList; mswTagMemDEBUG({ Ptr pd; for (pd = p + 1 + sizeof(Ptr); pd < p + 1 + size; pd++) *pd = EMPTY_MEM_TAG; }); fixedFreeList = p; released += 1; mswDEBUG(totFreeFixedMem += size;); } if (wasFull && released != 0) { if (tempHeapInfo && PAGE_SPACE(page) == SPACE_Permanent) { ((PageHeader)page)->nextPage = tempHeapInfo->availFPages[size]; tempHeapInfo->availFPages[size] = (PageHeader)page; } else { ((PageHeader)page)->nextPage = availFPages[size]; availFPages[size] = (PageHeader)page; } } ((PageHeader)page)->freeList = fixedFreeList; ((PageHeader)page)->allocatedObjs -= released; if (((PageHeader)page)->allocatedObjs == 0 && (isAvailFPage(page))) { mswRemoveAvailFPage((PageHeader)page); totReleasedPages += 1; } else if (totReleasedPages) mswQuickFreeChunk(page); assert(((PageHeader)page)->allocatedObjs >= 0); mswDEBUG({ sweptBytes += released * size; if (((PageHeader)page)->allocatedObjs == 0) totFreeFPages += 1; }); } /*---------------------------------------------------------------------------* * :: mswSweep *---------------------------------------------------------------------------*/ static void mswSweep() { Ptr page; unsigned pageInfo; PageHeader header; int i; totReleasedPages = 0; for (page = heapStart; page < heapEnd; page += bytesPerPage) { pageInfo = PAGE_INFO(page); if (pageInfo == PAGE_Fixed) mswSweepFPage(page); else if (pageInfo == PAGE_Mixed) { header = (PageHeader)page; /* Sweep mixed page */ if (header->isMarked) { header->isMarked = 0; if (totReleasedPages) mswQuickFreeChunk(page); } else { mswVERBOSE(sweptBytes += header->nPages * bytesPerPage;); totReleasedPages += header->nPages; } page += (header->nPages - 1) * bytesPerPage; } else { assert(pageInfo == PAGE_Free || pageInfo == PAGE_Other); if (totReleasedPages) mswQuickFreeChunk(page); } } if (totReleasedPages) mswQuickFreeChunk(page); /* Arrange availFPages[] so that there is no empty list */ for (i = PtrSize; i < MaxFixedSize; i += PtrSize) if (availFPages[i] == NULL) availFPages[i] = mswAllocFPage(i); } /*---------------------------------------------------------------------------* * :: mswMarkAndSweep *---------------------------------------------------------------------------*/ static void mswMarkAndSweep(void) { mswDEBUG(Word time1); mswDEBUG(Word time2); mswVERBOSE({ markedBytes = 0; sweptBytes = 0; totFreeFPages = 0; }); mswShowTIME({ time1 = mswGetCpuTime(); }); mswMark(); /********* Mark Phase *********/ mswDEBUG({ fprintf(gcOut, "."); fflush(gcOut); }); mswShowTIME({ time2 = mswGetCpuTime(); totMarkTime += (time2 - time1); fprintf(gcOut, "[Mark: %lu msec.]", time2 - time1); }); mswSweep(); /********* Sweep Phase *********/ mswShowTIME({ Word time3 = mswGetCpuTime() - time2; totSweepTime += time3; fprintf(gcOut, "[Sweep: %lu msec.]", time3); }); } /*---------------------------------------------------------------------------* * :: mswCollectNow * * Unconditional GC. * *---------------------------------------------------------------------------*/ void mswCollectNow() { if (mswIsCollectionDisabled()) return; mswDEBUG({ totFreeFixedMem = 0; collectSerial += 1; fprintf(gcOut, "#%lu: ", collectSerial); }); mswDisableCollection(); mswCondCheckDEBUG(mswCheckHeap(0);); mswDEBUG({ fprintf(gcOut, "[Garbage collection.."); fflush(gcOut); }); mswMarkAndSweep(); mswEnableCollection(); mswDEBUG(fprintf(gcOut, "done.]\n");); mswVERBOSE({ fprintf(gcOut, "Marked %lu bytes, Reclaimed %lu bytes\n", markedBytes, sweptBytes); fprintf(gcOut, "Tot. %u free pages (%u tot.) (%u from fixed)\n", totFreePages, (unsigned)(lastHeapPage - firstHeapPage), totFreeFPages); }); mswCondCheckDEBUG(mswCheckHeap(0);); } /*---------------------------------------------------------------------------* * :: mswCollect * * Conditional GC. Collect only if (heapSize > gcThreshold) and there is not * enough free memory. *---------------------------------------------------------------------------*/ void mswCollect() { Word heapSize = (lastHeapPage - firstHeapPage) * bytesPerPage; if (heapSize < (Word)Cmm::gcThreshold) ; // mswDEBUG(fprintf(gcOut, "heap size < gc threshold: skipping GC\n")); else { mswDEBUG(fprintf(gcOut, "Calling GC...\n");); mswCollectNow(); } } /*---------------------------------------------------------------------------* * * :: MarkAndSweep() * *---------------------------------------------------------------------------*/ MarkAndSweep::MarkAndSweep() { int i, j, k; Word firstObjOff, bp = 0; Word lastObjOff; Word size1, counter; Cmm::theMSHeap = this; // needed for allocatePages() freeChunks = NULL; stackStart = (Ptr) &i; /* This loop fills FPagesInfo[] vector, that is a vector * containing information about each fixed size. * This information will be shared among all the fixed pages for the * same size. */ for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { firstObjOff = FirstObjOffset; FPagesInfo[i].firstObjOffset = firstObjOff; FPagesInfo[i].basePointerv = (Ptr *) malloc(sizeof(Ptr) * bytesPerPage); for (j = 0; (Word)j < firstObjOff; j++) FPagesInfo[i].basePointerv[j] = 0; size1 = i + OBJ_ALIGNMENT; counter = 0; /* Compute the basePointer[] vector for size `i'. * basePointer[] can be used to access, given the page * offset of a pointer, to the base of the object. * NOTE that the base of an object is the word containing * the alloc/mark info, not the real start of the object, * that will be one word after. */ for (j = firstObjOff; j < (int)(GET_LAST_OBJ_PTR(NULL, i) + size1); j++) { if (counter == 0) { if ((Word)j > bytesPerPage - size1) /* PATCH BEGIN */ bp = 0; else bp = (Word) j; /* PATCH END */ counter = size1 - 1; /* Faith fake pointers: a pointer will not be * traced if is pointing to an object header. */ for (k = j - OBJ_ALIGNMENT + 1; k <= j; k++) FPagesInfo[i].basePointerv[k] = NULL; continue; } else counter--; FPagesInfo[i].basePointerv[j] = (Ptr) bp; } for (k = j; j < bytesPerPage; j++) FPagesInfo[i].basePointerv[k] = NULL; lastObjOff= bytesPerPage - size1 - firstObjOff; FPagesInfo[i].objectsPerPage = (lastObjOff - firstObjOff) / size1; } CmmHeap::init(); heapStart = (Ptr)pageToGCP(firstHeapPage); heapEnd = heapStart; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) availFPages[i] = mswAllocFPage(i); /* Initialize MarkStack */ theMarkStack = (MarkStackFrame) mswGetPages(MarkStackFramePages, 0); theMarkStack->previous = NULL; theMarkStack->next = NULL; markStackBase = (Ptr)theMarkStack +sizeof(struct MarkStackFrameStruct); markStackHeadroom = (Ptr)theMarkStack + MarkStackFramePages * bytesPerPage; markStackTop = markStackBase; mswPageMapSet((Ptr) theMarkStack, MarkStackFramePages, PAGE_Other); } /*---------------------------------------------------------------------------* * * -- MarkAndSweep::scanRoots(int page) * * Promotes pages referred by any allocated object inside "page". * (Should be) Used by DefaultHeap to identify pointers from MarkAndSweep * *---------------------------------------------------------------------------*/ static void scanFPageRoots(PageHeader); static void scanMixedPageRoots(PageHeader); void MarkAndSweep::scanRoots(Page page) { unsigned pageInfo = PAGE_INFO(page); PageHeader header = (PageHeader)pageToGCP(page); // Note: here we ignore PAGE_Next because those pages are // traversed when the PAGE_Mixed (i.e. the header) is reached. if (pageInfo == PAGE_Fixed) { int size = header->objSize; Word size1 = size + OBJ_ALIGNMENT; Ptr obj; long* ptr; Ptr lo = (Ptr)header + FPagesInfo[size].firstObjOffset; Ptr hi = GET_LAST_OBJ_PTR(header, size); for (obj = lo; obj <= hi; obj += size1) { if (*obj != AllocMask) continue; // <---- for (ptr = (long*) obj + 1 + sizeof(Ptr); ptr < (long*) obj + 1 + size; ptr++) promotePage((GCP)ptr); } } else if (pageInfo == PAGE_Mixed) { long* ptr; long* end; if (header->isOpaque) return; // <---- end = (long*) FirstObjOffset + 1 + header->objSize; for (ptr = (long*) FirstObjOffset + 1; ptr < end; ptr++) promotePage((GCP)ptr); } } /*---------------------------------------------------------------------------* * :: mswRegisterRoot *---------------------------------------------------------------------------*/ void mswRegisterRoot(void * p) { if (tempHeapInfo->nRoots == MAX_ROOT) { fprintf(stderr, "Too many roots...\n"); exit(-1); } tempHeapInfo->roots[tempHeapInfo->nRoots++] = (Ptr) p; } /*---------------------------------------------------------------------------* * * :: TempHeap * *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* * :: mswTempHeapFreePages * * Releases every page --EXCEPT ones marked PAGE_Other-- from * tempHeapInfo->firstPage up to heapEnd. Uses mswQuickFreeChunk(). * When this function is called: * - every PAGE_Other and PAGE_Free must be SPACE_Permanent * - every allocated page can be either SPACE_Permanent or SPACE_Temporary * *---------------------------------------------------------------------------*/ static void mswTempHeapFreePages(void) { Page page; totReleasedPages = 0; /* NOTE: the following loop is ugly because optimized */ for (page = firstHeapPage; page < lastHeapPage; page++) { if (pageSpace[page] == SPACE_Permanent) { if (totReleasedPages) mswQuickFreeChunk((Ptr)pageToGCP(page)); page += 1; while (page < lastHeapPage && pageSpace[page] == SPACE_Permanent) page += 1; if (page != lastHeapPage) { totReleasedPages += 1; pageSpace[page] = SPACE_Permanent; } } else { totReleasedPages += 1; pageSpace[page] = SPACE_Permanent; } } if (totReleasedPages) mswQuickFreeChunk((Ptr)pageToGCP(page)); } /*---------------------------------------------------------------------------* * :: mswTempHeapStart * * Freezes availFPages[] and resets it, such that everything is * allocated into the new space. *---------------------------------------------------------------------------*/ void mswTempHeapStart() { #ifndef MSW_NO_TEMPHEAP int i; TempHeapInfo prev = tempHeapInfo; tempHeapInfo = (TempHeapInfo) mswAlloc(sizeof(struct TempHeapInfoStruct)); tempHeapInfo->previous = prev; tempHeapInfo->nRoots = 0; mswDisableCollection(); for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { tempHeapInfo->availFPages[i] = availFPages[i]; availFPages[i] = NULL; availFPages[i] = mswAllocFPage(i); } mswEnableCollection(); #endif // ! MSW_NO_TEMPHEAP } /*---------------------------------------------------------------------------* * :: mswTempHeapEnd *---------------------------------------------------------------------------*/ void mswTempHeapEnd() { #ifndef MSW_NO_TEMPHEAP TempHeapInfo tmp; int i; assert(tempHeapInfo); mswCondCheckDEBUG(mswCheckHeap(0)); mswDisableCollection(); for (i = PtrSize; i < MaxFixedSize; i += PtrSize) availFPages[i] = tempHeapInfo->availFPages[i]; tmp = tempHeapInfo; tempHeapInfo = tempHeapInfo->previous; mswFree(tmp); mustResetTempHeap = 1; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { if (availFPages[i] == NULL) availFPages[i] = mswAllocFPage(i); } #endif // ! MSW_NO_TEMPHEAP } void mswTempHeapFree() { #ifndef MSW_NO_TEMPHEAP mswTempHeapFreePages(); mustResetTempHeap = 0; mswEnableCollection(); mswCondCheckDEBUG(mswCheckHeap(0)); #endif } /*---------------------------------------------------------------------------* * * :: Timings * *---------------------------------------------------------------------------*/ #ifdef MSW_SHOW_TIMINGS static Word mswGetCpuTime(void) { # ifdef sgi /* System V */ struct tms timebuf; Word r; times(&timebuf); r = timebuf.tms_utime * 100; return r/6; # else struct rusage rusage; getrusage (RUSAGE_SELF, &rusage); return (rusage.ru_utime.tv_sec*1000 + rusage.ru_utime.tv_usec/1000 + rusage.ru_stime.tv_sec*1000 + rusage.ru_stime.tv_usec/1000); # endif } #endif /* MSW_SHOW_TIMINGS */ /*---------------------------------------------------------------------------* * :: mswShowInfo *---------------------------------------------------------------------------*/ void mswShowInfo(void) { fprintf(gcOut, "-------------------- MSW Collector ------------------\n\n"); mswDEBUG(fprintf(gcOut, "+++ Debug version +++\n");); fprintf(gcOut, "Alignment = %d\n", OBJ_ALIGNMENT); fprintf(gcOut, "Max heap size = %lu Kbytes\n", (unsigned long) (heapEnd - heapStart) / 1024); fprintf(gcOut, "Page size = %lu\n", bytesPerPage); mswShowTIME({ fprintf(gcOut, "Tot. Mark Time = %lu msec.\n", totMarkTime); fprintf(gcOut, "Tot. Sweep Time = %lu msec.\n", totSweepTime); }); } /*---------------------------------------------------------------------------* * * :: Debug * *---------------------------------------------------------------------------*/ #ifndef NDEBUG void mswShowMem(void) { int base = GCPtoPage(heapStart); int top = GCPtoPage(heapEnd); int i; int j = 0; char c; const int pagesPerLine = 72; fprintf(gcOut, "+++++ (. = Free, # = Fixed, B/b = BigObj, O = Other) ++++"); for (i = base; i < top; i++) { if (j == 0) { fprintf(gcOut, "\n%05d: ", i); j = pagesPerLine; } j -= 1; switch (pageMap[i]) { case PAGE_Free: c = '.'; break; case PAGE_Fixed: c = '#'; break; case PAGE_Mixed: c = 'B'; break; case PAGE_Next: c = 'b'; break; case PAGE_Other: c = 'O'; break; default: assert(-1); } fputc(c, gcOut); } fprintf(gcOut, "\n"); } void mswShowTempMem(void) { int base = GCPtoPage(heapStart); int top = GCPtoPage(heapEnd); int i; int j = 0; char c; const int pagesPerLine = 72; fprintf(gcOut, "+++++ (T = Temporary, - = Permanent) ++++"); for (i = base; i < top; i++) { if (j == 0) { fprintf(gcOut, "\n%05d: ", i); j = pagesPerLine; } j -= 1; if (pageSpace[i] == SPACE_Temporary) c = 'T'; else c = '_'; fputc(c, gcOut); } fprintf(gcOut, "\n"); } void mswShowFreeChunks(void) { FreePageHeader l = freeChunks; FreePageHeader l1; fprintf(gcOut, "+++ Free chunks: \n"); while (l) { fprintf(gcOut, "> %d pages chunks: ", l->nPages); l1 = l; while (l1) { fprintf(gcOut, "[%x]", (unsigned) l1); l1 = l1->nextChunk; } fprintf(gcOut, "\n"); l = l->nextChunkGroup; } fprintf(gcOut, "--- free chunks end\n"); } /*---------------------------------------------------------------------------* * ::maxObjsInOnePage * * Used by mswShowFragmentation(). Returns the max number of fixed objs of * size "size" that can fit in one page. * *---------------------------------------------------------------------------*/ static int maxObjsInOnePage(int size) { return (bytesPerPage - sizeof(PageHeaderStruct)) / (size + OBJ_ALIGNMENT); } /*---------------------------------------------------------------------------* * ::mswShowFragmentation * * Calculates fragmentation for each fixed size. *---------------------------------------------------------------------------*/ void mswShowFragmentation() { double realUse; double totRealUse = 0.0; int totAnalized = 0; int i, totObjs, totPages, minPages; int wastedPages = 0; PageHeader pages; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { pages = availFPages[i]; /* Show only significant data */ if (pages == NULL || pages->nextPage == NULL) { if (pages && pages->allocatedObjs == 0) wastedPages += 1; totRealUse += 100.0; totAnalized += 1; continue; /* <------------- */ } totObjs = 0; totPages = 0; while (pages) { totObjs += pages->allocatedObjs; totPages += 1; pages = pages->nextPage; } minPages = 1 + (totObjs / maxObjsInOnePage(i)); realUse = (100.0 * (double) minPages) / (double) totPages; totRealUse += realUse; totAnalized += 1; fprintf(gcOut, "Pages[%d] used at %2.4g%% ", i, realUse); fprintf(gcOut, "(%d objs in %d pages, %d min pages, -> %d pg wasted)\n", totObjs, totPages, minPages, totPages - minPages); wastedPages += (totPages - minPages); } if (totAnalized) fprintf(gcOut, "\nTot: fixed pages used at %2.4g%%. Tot. %d/%d wasted pages.\n", totRealUse / (double) totAnalized, wastedPages, lastHeapPage - firstHeapPage); else fprintf(gcOut, "No fragmentation for fixed objs.\n"); } /*---------------------------------------------------------------------------* * :: Heap Checking Functions *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* * ::mswIsInAvailFPages * * Returns 0 if "page" is not in "pages", else 1. * *---------------------------------------------------------------------------*/ static int mswIsInAvailFPages(PageHeader page, PageHeader pages) { while (pages) { if (pages == page) return 1; pages = pages->nextPage; } return 0; } /*---------------------------------------------------------------------------* * ::mswCheckPageIsFixed * * Check that "page" looks like a fixed page. * *---------------------------------------------------------------------------*/ static void mswCheckPageIsFixed(Ptr page) { PageHeader header = (PageHeader) page; PageHeader pg; Word size = header->objSize; assert(size > 0 && size < MaxFixedSize); assert(size == ROUND_UP(size, PtrAlignment)); assert(header->basePointerv); assert(header->allocatedObjs <= bytesPerPage / (size+1)); assert(header->freeList == NULL || (header->freeList > (Ptr) header && header->freeList < (Ptr) header + bytesPerPage)); if (header->freeList) { /* If there is at least a free object, check that this page * is among availables pages. */ pg = availFPages[size]; if (mswIsInAvailFPages(header, pg) == 0) { if (tempHeapInfo == NULL) { assert("found a fixed page not full but not" "in availFPages[]" == NULL); } pg = tempHeapInfo->availFPages[size]; if (mswIsInAvailFPages(header, pg) == 0) { assert("found a fixed page not full but not" "in availFPages[]" == NULL); } } } else { /* No free objects => check that this page * is NOT among availables pages. */ pg = availFPages[size]; while (pg) { if (pg == header) break; pg = pg->nextPage; } assert(pg == NULL); } } /*---------------------------------------------------------------------------* * ::mswCheckFreeFixedList * * Trace the "freeList" for objs of size "size" checking that every obj * is not marked, not allocated, that it is filled with EMPTY_MEM_TAG or * RELEASED_MEM_TAG and that the corresponding page is PAGE_Free of PAGE_Fixed. *---------------------------------------------------------------------------*/ static void mswCheckFreeFixedList(PageHeader page, int size) { Ptr p; Ptr start; Ptr freeList = page->freeList; int pageInfo = PAGE_INFO(page); if (freeList == NULL) return; assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Free); while (freeList) { /* Check that every obj is inside page boundaries */ assert(freeList > (Ptr)page + sizeof(PageHeaderStruct)); assert(freeList < (Ptr)page + bytesPerPage); /* Check that obj is marked Free */ assert(*((Ptr)freeList) == FreeMask); start = (Ptr)freeList + 1 + sizeof(Ptr); mswTagMemDEBUG({ for (p = start; p < freeList + 1 + size; p++) assert(*p == EMPTY_MEM_TAG || *p == RELEASED_MEM_TAG); }); freeList = NEXT_FREE_OBJ(freeList); } } static void mswCheckFreeFixedObjs(void) { int i; PageHeader page; for (i = PtrSize; i < MaxFixedSize; i += PtrSize) { page = availFPages[i]; while (page) { if (tempHeapInfo) assert(PAGE_SPACE(page) == SPACE_Temporary); else assert(PAGE_SPACE(page) == SPACE_Permanent); assert(page->objSize == i); assert(page->isMarked == 0); assert(page->freeList); mswCheckFreeFixedList(page, i); page = page->nextPage; } } } static void mswCheckFPage(Ptr page) { PageHeader header = (PageHeader) page; Ptr p; int size = header->objSize; int size1 = size + OBJ_ALIGNMENT; Ptr hi = GET_LAST_OBJ_PTR(page, size); int firstObjOff; int allocatedObjs = 0; mswCheckPageIsFixed(page); firstObjOff = FPagesInfo[size].firstObjOffset; for (p = page + firstObjOff; p <= hi; p += size1) { assert(*(Byte *)(p-1) == TransparentMask || *(Byte *)(p-1) == OpaqueMask); assert(*p == AllocMask || *p == FreeMask); if (*p == AllocMask) allocatedObjs += 1; } assert(allocatedObjs == header->allocatedObjs); } static void mswCheckMixedPage(PageHeader header) { int nPages = header->nPages; int index = GCPtoPage(header); int i; for (i = index + 1; i < index + nPages; i++) assert(pageMap[i] == PAGE_Next); assert(header->basePointerv == NULL); assert(header->allocatedObjs == 1); assert(header->nPages == (FirstObjOffset + header->objSize + bytesPerPage) / bytesPerPage); } static void mswCheckFixedAndMixedPages(void) { Ptr page; int pageInfo; for (page = heapStart; page < heapEnd; page += bytesPerPage) { pageInfo = PAGE_INFO(page); if (pageInfo == PAGE_Fixed) mswCheckFPage(page); else if (pageInfo == PAGE_Mixed) { mswCheckMixedPage((PageHeader)page); page += (((PageHeader)page)->nPages -1) * bytesPerPage; } else assert(pageInfo == PAGE_Other || pageInfo == PAGE_Free); } } static void mswCheckPageIsInFreeChunks(Ptr page) { FreePageHeader l = freeChunks; FreePageHeader l1; while (l) { l1 = l; while (l1) { if ((Ptr) l1 <= page && page < (Ptr)l1 + l1->nPages * bytesPerPage) return; /* <------- */ l1 = l1->nextChunk; } l = l->nextChunkGroup; } assert(l); /* Cause assertion fault */ } static void mswCheckPageMap(void) { Ptr page; int pageInfo; assert(heapStart < heapEnd); for (page = heapStart; page < heapEnd; page+= bytesPerPage) { pageInfo = PAGE_INFO(page); assert(pageInfo == PAGE_Free || pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed || pageInfo == PAGE_Other || pageInfo == PAGE_Next); if (pageInfo == PAGE_Free) { mswCheckPageIsInFreeChunks(page); assert(PAGE_SPACE(page) == SPACE_Permanent); } else if (pageInfo == PAGE_Fixed) mswCheckPageIsFixed(page); } } /* !! TODO: should check that free space contains RELEASED_MEM_TAG or * EMPTY_MEM_TAG */ static void mswCheckFreeChunks() { FreePageHeader l = freeChunks; FreePageHeader l1; int i, nPages, nGroupPages; int numFreePgs = 0; Ptr p; while (l) { assert(IS_INSIDE_HEAP(l)); l1 = l; if (l1) nGroupPages = l1->nPages; while (l1) { assert(IS_INSIDE_HEAP(l1)); /* Check that is a page address */ assert((Word)l1 == ROUND_DOWN(l1, bytesPerPage)); assert(l1->nPages > 0 && l1->nPages < 20000); assert(l1->nPages == nGroupPages); numFreePgs += nGroupPages; /* Check pages are marked with PAGE_Free */ i = GCPtoPage(l1); nPages = nGroupPages; while (nPages--) assert(pageMap[i++] == PAGE_Free); mswTagMemDEBUG({ for (p = (Ptr)l1+sizeof(FreePageHeaderStruct)+1; p < (Ptr)l1 + (l1->nPages * bytesPerPage); p++) assert(*p == RELEASED_MEM_TAG || *p == EMPTY_MEM_TAG); }); l1 = l1->nextChunk; } l = l->nextChunkGroup; } assert(totFreePages == numFreePgs); } #endif /* ! NDEBUG */ void mswCheckHeap(int verbose) { #ifndef NDEBUG if (verbose) fprintf(gcOut, "\n------------- Checking heap corruption ---------------\n"); if (verbose) fprintf(gcOut, "- checking free chunks...\n"); mswCheckFreeChunks(); if (verbose) fprintf(gcOut, "- checking page map...\n"); if (mustResetTempHeap) { if (verbose) { fprintf(gcOut, "mustResetTempHeap = T => skipping test...\n"); } } else mswCheckPageMap(); if (verbose) fprintf(gcOut, "- checking free fixed objects...\n"); mswCheckFreeFixedObjs(); if (verbose) fprintf(gcOut, "- checking fixed and mixed pages...\n"); if (mustResetTempHeap) if (verbose) { fprintf(gcOut, "mustResetTempHeap = T => skipping test...\n"); } else mswCheckFixedAndMixedPages(); if (verbose) fprintf(gcOut, "-------------------- Heap is OK ------------------------\n\n"); #endif } #ifndef NDEBUG /*---------------------------------------------------------------------------* * :: Functions useful during debugging sessions *---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------* * :: getPtrInfo * * Given a pointer, shows some useful information: page to which belong, size * of the pointed object, etc. * To be used when a crash happen to get information about the pointer causing * it. * *---------------------------------------------------------------------------*/ void getPtrInfo(Ptr p) { PageHeader page; Ptr base; char * temporary = ""; fprintf(gcOut, "---- getPtrInfo(%lx): ----\n", p); if (! IS_INSIDE_HEAP(p)) { fprintf(gcOut, "Hum... this pointer is outside MSW heap...\n"); return; } page = (PageHeader) PAGE_START(p); switch (PAGE_INFO(p)) { case PAGE_Fixed: if (pageSpace[GCPtoPage(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer points into a%s fixed page.\n", temporary); fprintf(gcOut, "Page: %lx (index: %d, offset: %d)\n", page, GCPtoPage(p), (Word)p - (Word)page); fprintf(gcOut, "Size of objs in this page: %d\n", page->objSize); fprintf(gcOut, "Objs allocated in this page: %d\n", page->allocatedObjs); if (p - (Ptr) page < FirstObjOffset) { fprintf(gcOut, "Address before first object offset.\n"); return; } base = GET_OBJ_BASE(p, page); fprintf(gcOut, "pointer base: %lx\n", base); if (base == p) { fprintf(gcOut, "WARNING: the pointer points before the beginning of a fixed object!\n"); return; } switch (*base) { case AllocMask: fprintf(gcOut, "STATE: allocated\n"); break; case MarkMask: fprintf(gcOut, "STATE: marked\n"); break; case FreeMask: fprintf(gcOut, "STATE: free\n"); break; default: fprintf(gcOut, "WARNING: STATE is not MarkMask | AllocMask | FreeMask! \n"); break; } switch (*(base-1)) { case OpaqueMask: fprintf(gcOut, "Obj is OPAQUE \n"); break; case TransparentMask: fprintf(gcOut, "Obj is TRANSPARENT \n"); break; default: fprintf(gcOut, "WARNING: not registred as OPAQUE or TRANSPARENT! \n"); break; } break; case PAGE_Next: { int index; if (pageSpace[GCPtoPage(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer is in the middle of a%s mixed object\n", temporary); fprintf(gcOut, "finding the base page...\n"); index = GCPtoPage(p) - 1; while (pageMap[index] != PAGE_Mixed) { index -= 1; assert(index > 0); } p = (Ptr)pageToGCP(index); goto LAB_PageMixed; } case PAGE_Mixed: if (pageSpace[GCPtoPage(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer points into a%s mixed page\n", temporary); LAB_PageMixed: page = (PageHeader) PAGE_START(p); fprintf(gcOut, "Size of the obj in this page: %d\n", page->objSize); fprintf(gcOut, "Number of pages for this obj: %d\n", page->nPages); if (p - (Ptr) page < FirstObjOffset) { fprintf(gcOut, "The pointer points before the first object offset!\n"); return; } return; case PAGE_Free: if (pageSpace[GCPtoPage(p)] == SPACE_Temporary) temporary = " *temporary*"; fprintf(gcOut, "This pointer points to a chunk of released%s memory.\n", temporary); return; case PAGE_Other: fprintf(gcOut, "This pointer points to another heap.\n"); return; default: fprintf(gcOut, "BUG -- getPtrInfo(): unknown page type (probably the page map is corrupted).\n"); } } /*---------------------------------------------------------------------------* * :: Functions boxing some macros -- useful for debugging *---------------------------------------------------------------------------*/ Ptr pageStart(Ptr p) { return PAGE_START(p); } Ptr objBase(Ptr p, PageHeader header) { return GET_OBJ_BASE(p, header); } int isInsideHeap(Ptr p) { return IS_INSIDE_HEAP(p); } int pageIndex(Ptr p) { return GCPtoPage(p); } Ptr pageFromIndex(int index) { return (Ptr)pageToGCP(index); } int pageSpaceFromPtr(Ptr p) { int space = PAGE_SPACE(p); if (space == SPACE_Temporary) printf("(temporary)\n"); else printf("(permanent)\n"); return space; } int pageInfo(Ptr p) { int info = PAGE_INFO(p); char * s; switch (info) { case PAGE_Free: s = "Free"; break; case PAGE_Fixed: s = "Fixed"; break; case PAGE_Mixed: s = "Mixed"; break; case PAGE_Next: s = "Next"; break; case PAGE_Other: s = "Other"; break; } printf("(%s)\n", s); return info; } Word roundUp(Word a, Word b) { return ROUND_UP(a,b); } Word roundDown(Word a, Word b) { return ROUND_DOWN(a,b); } Ptr getLastObjPtr(Ptr p, Word size) { return GET_LAST_OBJ_PTR(p, size); } # ifdef MSW_TRACE_ONE_PAGE /* Add a call to mswTraceFPage(xxx) on the top of mswAlloc(); * When you get the problem with a fixed page, take its address and restart * setting xxx = address of the corrupted page. */ void mswTraceFPage(Ptr page) { if (IS_INSIDE_HEAP(page) && PAGE_INFO(page) == PAGE_Fixed) mswCheckFPage(page); } # endif /* MSW_TRACE_ONE_PAGE */ void mswCheckAllocatedObj(void * ptr) { Ptr obj = (Ptr) ptr; int pageInfo = PAGE_INFO(obj); PageHeader header = (PageHeader) PAGE_START(obj); assert(IS_INSIDE_HEAP(obj)); assert(pageInfo == PAGE_Fixed || pageInfo == PAGE_Mixed); if (pageInfo == PAGE_Fixed) { Ptr bp = GET_OBJ_BASE(obj, header); assert(bp != (Ptr) header); } else assert((Word) obj - (Word)header == FirstObjOffset + 1); } # ifdef MSW_GET_ALLOC_SIZE_STATS void mswShowStats() { int i; for (i = 1; i < MAX_TRACED_SIZE; i++) if (totAllocatedSizes[i]) printf("%lu objs of size = %lu\n",totAllocatedSizes[i], i); printf("%lu objs of size = %lu\n", totHugeAllocated,MAX_TRACED_SIZE); } # endif /* MSW_GET_ALLOC_SIZE_STATS */ #endif /* NDEBUG */