/*---------------------------------------------------------------------------* Project: OS - Memory Manager File: OSAlloc.c Copyright 1998 - 2006 Nintendo. All rights reserved. These coded instructions, statements, and computer programs contain proprietary information of Nintendo of America Inc. and/or Nintendo Company Ltd., and are protected by Federal copyright law. They may not be disclosed to third parties or copied or duplicated in any form, in whole or in part, without the prior written consent of Nintendo. $Log: OSAlloc.c,v $ Revision 1.3 2006/02/20 05:25:24 hirose Changed location of include headers. Revision 1.2 2006/01/20 01:07:52 hirose (none) Revision 1.1.1.1 2005/12/29 06:53:27 hiratsu Initial import. Revision 1.1.1.1 2005/05/12 02:15:49 yasuh-to Ported from dolphin source tree. 2 2004/01/09 9:24 Shiki Fixed OSDestroyHeap to re-initialize hd->free to NULL to prevent subsequent OSAlloc in non-debug build. 15 1999/11/01 6:16p Tian Added OSVisitAllocated to iterate over all allocated memory 13 1999/06/03 6:37p Shiki Implemented error messages. 12 1999/06/01 3:01p Shiki Revised function description of OSDestroyHeap(). 11 1999/05/26 9:16a Shiki Fixed OSAllocFixed(), etc. 10 1999/05/25 9:55p Shiki Modified OSCheckHeap()to return # of available bytes in free. 9 1999/05/23 6:57p Shiki Fixed OSAllocFixed(). Added sanity check function. 8 1999/05/22 7:59p Shiki Refined less-efficient array references by pointers. 7 1999/05/22 7:30p Shiki Revised doubly-linked list manipulation functions. 6 1999/05/21 8:06p Shiki Fixed spell misses. 5 1999/05/21 7:56p Shiki Revised. 3 1999/05/19 5:12p Shiki Renamed Halt() to OSHalt(). 2 1999/05/11 4:36p Shiki Refreshed include tree. 1 1999/04/30 12:47p Tianli01 4 1999/04/15 2:49p Tianli01 Fixes for PPC (no floats). Changed failure semantics slightly (NULL return on run out of memory). 3 1999/04/13 9:44a Tianli01 Fixed compile warnings 2 1999/03/26 2:10p Tianli01 Removed OSEvent reliance. 1 1999/03/09 11:43a Tianli01 Fixed negated assertions 1 1999/03/04 2:23p Tianli01 Initial check-in to new tree. 1 1998/12/22 10:29a Tianli01 Initial check-in. To be implemented : OSEvent integration, Sanity checking $NoKeywords: $ *---------------------------------------------------------------------------*/ #include #include #include #include "OSAssert.h" #define OFFSET(n, a) (((u32) (n)) & ((a) - 1)) #define TRUNC(n, a) (((u32) (n)) & ~((a) - 1)) #define ROUND(n, a) (((u32) (n) + (a) - 1) & ~((a) - 1)) #define ALIGNMENT 32 // alignment in bytes #define MINOBJSIZE (HEADERSIZE + ALIGNMENT) // smallest object #define HEADERSIZE ROUND(sizeof(Cell), ALIGNMENT) // InRange(): True if a <= targ < b #define InRange(targ, a, b) \ ((u32)(a) <= (u32)(targ) && (u32)(targ) < (u32)(b)) // RangeOverlap(): True if the ranges a and b overlap in any way. #define RangeOverlap(aStart, aEnd, bStart, bEnd) \ ((u32)(bStart) <= (u32)(aStart) && (u32)(aStart) < (u32)(bEnd) || \ (u32)(bStart) < (u32)(aEnd) && (u32)(aEnd) <= (u32)(bEnd)) // RangeSubset(): True if range a is a subset of range b // Assume (aStart < aEnd) and (bStart < bEnd) #define RangeSubset(aStart, aEnd, bStart, bEnd) \ ((u32)(bStart) <= (u32)(aStart) && (u32)(aEnd) <= (u32)(bEnd)) typedef struct Cell Cell; typedef struct HeapDesc HeapDesc; // Cell: header of object which resides HEADERSIZE bytes before payload. // doubly linked list are needed because of non-contiguous heaps struct Cell { Cell* prev; Cell* next; long size; // size of object plus HEADERSIZE #ifdef _DEBUG HeapDesc* hd; // from which the block is allocated // (NULL in free list). long requested; // size of object to have been requested #endif // _DEBUG }; struct HeapDesc { long size; // if -1 then heap is free. Note OSAllocFixed() // could make a heap empty. Cell* free; // pointer to the first free cell Cell* allocated; // pointer to the first used cell #ifdef _DEBUG u32 paddingBytes; u32 headerBytes; u32 payloadBytes; #endif // _DEBUG }; // volatile because some functions use this as hidden macro parameter volatile OSHeapHandle __OSCurrHeap = -1; static HeapDesc* HeapArray; // array of current heap descriptors static int NumHeaps; // number of heaps static void* ArenaStart; // specified by OSInitAlloc() static void* ArenaEnd; // specified by OSInitAlloc() /*---------------------------------------------------------------------------* Name: DLAddFront Description: Inserts /cell/ into the head of the list pointed to by /list/ Arguments: list: pointer to the first cell in the list cell: pointer to a cell to be inserted Returns: a pointer to the new first cell *---------------------------------------------------------------------------*/ static Cell* DLAddFront(Cell* list, Cell* cell) { cell->next = list; cell->prev = NULL; if (list) list->prev = cell; return cell; } /*---------------------------------------------------------------------------* Name: DLLookup Description: Returns /cell/ if /cell/ is found in /list/. Arguments: list: pointer to the first cell in the list cell: pointer to a cell to look for Returns: /cell/ if /cell/ is in /list/. Otherwise, NULL. *---------------------------------------------------------------------------*/ static Cell* DLLookup(Cell* list, Cell* cell) { for (; list; list = list->next) { if (list == cell) return list; } return NULL; } /*---------------------------------------------------------------------------* Name: DLExtract Description: Extracts /target/ from the list pointed to by /list/. If /target/ is at the head of the list, /list/ will be changed to reflect its removal. Arguments: list: pointer to the first cell in the list cell: pointer to a cell to remove Returns: a pointer to the new first cell *---------------------------------------------------------------------------*/ static Cell* DLExtract(Cell* list, Cell* cell) { if (cell->next) cell->next->prev = cell->prev; if (cell->prev == NULL) return cell->next; else { cell->prev->next = cell->next; return list; } } /*---------------------------------------------------------------------------* Name: DLInsert Description: Inserts /cell/ into the list pointed to by /list/ in sorted order by address. Also attempts to coalesce forward and backward blocks if possible. Arguments: list: pointer to the first cell in the list cell: pointer to a cell to be inserted Returns: a pointer to the new first cell *---------------------------------------------------------------------------*/ static Cell* DLInsert(Cell* list, Cell* cell) { Cell* prev; Cell* next; for (next = list, prev = NULL; next; prev = next, next = next->next) { if (cell <= next) break; } cell->next = next; cell->prev = prev; if (next) { next->prev = cell; if ((char*) cell + cell->size == (char*) next) { // Coalesce forward cell->size += next->size; cell->next = next = next->next; if (next) next->prev = cell; } } if (prev) { prev->next = cell; if ((char*) prev + prev->size == (char*) cell) { // Coalesce back prev->size += cell->size; prev->next = next; if (next) next->prev = prev; } return list; } else { return cell; // cell becomes new head of list } } /*---------------------------------------------------------------------------* Name: DLOverlap Description: returns true if the range delimited by /start/ and /end/ overlaps with any element of /list/. Arguments: list: pointer to the first cell in the list start: start of range end: end of range Returns: TRUE if /start/-/end/ overlaps with any element of /list/ *---------------------------------------------------------------------------*/ static BOOL DLOverlap(Cell* list, void* start, void* end) { Cell* cell; for (cell = list; cell; cell = cell->next) { if (RangeOverlap(cell, (char*) cell + cell->size, start, end)) return TRUE; } return FALSE; } /*---------------------------------------------------------------------------* Name: DLSize Description: returns total number of bytes used by every element of /list/. Arguments: list: pointer to the first cell in the list Returns: total number of bytes used by every cell of /list/ *---------------------------------------------------------------------------*/ static long DLSize(Cell* list) { Cell* cell; long size = 0; for (cell = list; cell; cell = cell->next) { size += cell->size; } return size; } /*---------------------------------------------------------------------------* Name: OSAllocFromHeap Description: Allocates /size/ bytes from /heap/. Some additional memory will also be consumed from /heap/. Arguments: heap: handle to a heap that was returned from OSCreateHeap() size: size of object to be allocated Returns: a null pointer or a pointer to the allocated space aligned with ALIGNMENT bytes boundaries *---------------------------------------------------------------------------*/ void* OSAllocFromHeap(OSHeapHandle heap, u32 size) { HeapDesc* hd; Cell* cell; // candidate block Cell* newCell; // ptr to leftover block long leftoverSize; // size of any leftover #ifdef _DEBUG long requested = (long) size; #endif // _DEBUG ASSERTMSG(HeapArray, OS_ERR_ALLOCFROMHEAP_NOHEAP); ASSERTMSG(0 < ((long) size), OS_ERR_ALLOCFROMHEAP_INVSIZE); ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_ALLOCFROMHEAP_INVHEAP); ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_ALLOCFROMHEAP_INVHEAP); hd = &HeapArray[heap]; // Enlarge size to smallest possible cell size size += HEADERSIZE; size = ROUND(size, ALIGNMENT); // Search for block large enough for (cell = hd->free; cell != NULL; cell = cell->next) { if ((long) size <= cell->size) break; } if (cell == NULL) { #ifdef _DEBUG OSReport("OSAllocFromHeap: Warning- failed to allocate %d bytes\n", size); #endif // _DEBUG return NULL; } ASSERTMSG(OFFSET(cell, ALIGNMENT) == 0, OS_ERR_ALLOCFROMHEAP_BROKENHEAP); ASSERTMSG(cell->hd == NULL, OS_ERR_ALLOCFROMHEAP_BROKENHEAP); leftoverSize = cell->size - (long) size; if (leftoverSize < MINOBJSIZE) { // Just extract this cell out since it's too small to split hd->free = DLExtract(hd->free, cell); } else { // cell is large enough to split into two pieces cell->size = (long) size; // Create a new cell newCell = (Cell*) ((char*) cell + size); newCell->size = leftoverSize; #ifdef _DEBUG newCell->hd = NULL; #endif // Leave newCell in free, and take cell away newCell->prev = cell->prev; newCell->next = cell->next; if (newCell->next != NULL) newCell->next->prev = newCell; if (newCell->prev != NULL) newCell->prev->next = newCell; else { ASSERTMSG(hd->free == cell, OS_ERR_ALLOCFROMHEAP_BROKENHEAP); hd->free = newCell; } } // Add to allocated list hd->allocated = DLAddFront(hd->allocated, cell); #ifdef _DEBUG cell->hd = hd; cell->requested = requested; hd->headerBytes += HEADERSIZE; hd->paddingBytes += cell->size - (HEADERSIZE + requested); hd->payloadBytes += requested; #endif // _DEBUG return (void*) ((char*) cell + HEADERSIZE); } /*---------------------------------------------------------------------------* Name: OSAllocFixed Description: Allocates the block of memory specified by /rstart/ and /rend/. Will break up any heap. Will not check for overlap with other fixed blocks. May create a zero-length heap. Arguments: rstart: pointer to starting addr of block rend: pointer to ending addr of block Returns: a null pointer or a pointer to the allocated space aligned with ALIGNMENT bytes boundaries. /rstart/ and /rend/ might be adjusted to the boundaries of really allocated region. *---------------------------------------------------------------------------*/ void* OSAllocFixed(void** rstart, void** rend) { OSHeapHandle i; // heap iterator Cell* cell; // object iterator Cell* newCell; // for creating new objects if necessary HeapDesc* hd; void* start = (void*) TRUNC(*rstart, ALIGNMENT); void* end = (void*) ROUND(*rend, ALIGNMENT); ASSERTMSG(HeapArray, OS_ERR_ALLOCFIXED_NOHEAP); ASSERTMSG(start < end, OS_ERR_ALLOCFIXED_INVRANGE); ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd), OS_ERR_ALLOCFIXED_INVRANGE); // Check overlap with any allocated blocks. for (i = 0; i < NumHeaps; i++) { hd = &HeapArray[i]; if (hd->size < 0) // Is inactive? continue; if (DLOverlap(hd->allocated, start, end)) { #ifdef _DEBUG OSReport("OSAllocFixed: Warning - failed to allocate from %p to %p\n", start, end); #endif // _DEBUG return NULL; } } /* ASSUME : if we get past all this, the fixed request will not overlap with any non-contiguous free memory. Iterate over heaps breaking up appropriate blocks. note that we cannot change the size of the heap by simply subtracting out the overlap area, since the heaps may be non-contiguous. */ for (i = 0; i < NumHeaps; i++) { // for each free obj in heap, find and break overlaps. hd = &HeapArray[i]; if (hd->size < 0) // Is inactive? continue; for (cell = hd->free; cell; cell = cell->next) { void* cellEnd = (char*) cell + cell->size; if ((char*) cellEnd <= (char*) start) continue; if ((char*) end <= (char*) cell) break; // Since free is sorted in order of start addresses if (InRange(cell, (char*) start - HEADERSIZE, end) && InRange((char*) cellEnd, start, (char*) end + MINOBJSIZE)) { if ((char*) cell < (char*) start) start = (void*) cell; if ((char*) end < (char*) cellEnd) end = (void*) cellEnd; // cell is completely overlaped. Just extract this block hd->free = DLExtract(hd->free, cell); // Note cell->next is intact. XXX hd->size -= cell->size; // Update stats continue; } if (InRange(cell, (char*) start - HEADERSIZE, end)) { if ((char*) cell < (char*) start) start = (void*) cell; // Start of object in middle of range. break off top. // Avoid DLExtract() and DLInsert() since we already know // exactly where the block should go ASSERT(MINOBJSIZE <= (char*) cellEnd - (char*) end); newCell = (Cell*) end; newCell->size = (char*) cellEnd - (char*) end; #ifdef _DEBUG newCell->hd = NULL; #endif // _DEBUG newCell->next = cell->next; if (newCell->next) newCell->next->prev = newCell; newCell->prev = cell->prev; if (newCell->prev) newCell->prev->next = newCell; else hd->free = newCell; // new head hd->size -= (char*) end - (char*) cell; break; } if (InRange((char*) cellEnd, start, (char*) end + MINOBJSIZE)) { if ((char*) end < (char*) cellEnd) end = (void*) cellEnd; // Nothing to change except size ASSERT(MINOBJSIZE <= (char*) start - (char*) cell); hd->size -= (char*) cellEnd - (char*) start; cell->size = (char*) start - (char*) cell; continue; } // Create a new cell after end of the fixed block. ASSERT(MINOBJSIZE <= (char*) cellEnd - (char*) end); newCell = (Cell*) end; newCell->size = (char*) cellEnd - (char*) end; #ifdef _DEBUG newCell->hd = NULL; #endif // _DEBUG newCell->next = cell->next; if (newCell->next) newCell->next->prev = newCell; newCell->prev = cell; cell->next = newCell; // cell is before newCell cell->size = (char*) start - (char*) cell; hd->size -= (char*) end - (char*) start; break; } ASSERT(0 <= hd->size); } ASSERT(OFFSET(start, ALIGNMENT) == 0); ASSERT(OFFSET(end, ALIGNMENT) == 0); ASSERT(start < end); *rstart = start; *rend = end; return *rstart; } /*---------------------------------------------------------------------------* Name: OSFreeToHeap Description: Returns obj /ptr/ to /heap/. Arguments: heap: handle to the heap that /ptr/ was allocated from ptr: pointer to object previously returned from OSAlloc() or OSAllocFromHeap(). Returns: None. *---------------------------------------------------------------------------*/ void OSFreeToHeap(OSHeapHandle heap, void* ptr) { HeapDesc* hd; Cell* cell; ASSERTMSG(HeapArray, OS_ERR_FREETOHEAP_NOHEAP); ASSERTMSG(InRange(ptr, (char*) ArenaStart + HEADERSIZE, (char*) ArenaEnd), OS_ERR_FREETOHEAP_INVPTR); ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_FREETOHEAP_INVPTR); ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_FREETOHEAP_INVHEAP); cell = (Cell*) ((char*) ptr - HEADERSIZE); hd = &HeapArray[heap]; ASSERTMSG(cell->hd == hd, OS_ERR_FREETOHEAP_INVPTR); ASSERTMSG(DLLookup(hd->allocated, cell),OS_ERR_FREETOHEAP_INVPTR); #ifdef _DEBUG cell->hd = NULL; hd->headerBytes -= HEADERSIZE; hd->paddingBytes -= cell->size - (HEADERSIZE + cell->requested); hd->payloadBytes -= cell->requested; #endif // _DEBUG // Extract from the allocated list hd->allocated = DLExtract(hd->allocated, cell); // Add in sorted order to free list (coalesced with next and prev) hd->free = DLInsert(hd->free, cell); } /*---------------------------------------------------------------------------* Name: OSSetCurrentHeap Description: Sets __OSCurrHeap to /heap/. All subsequent calls to OSAlloc() will be performed on this heap until another call to OSSetCurrentHeap(). Arguments: heap: handle to a heap that was returned from OSCreateHeap() Returns: previous heap handle. *---------------------------------------------------------------------------*/ OSHeapHandle OSSetCurrentHeap(OSHeapHandle heap) { OSHeapHandle prev; ASSERTMSG(HeapArray, OS_ERR_SETCURRENTHEAP_NOHEAP); ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_SETCURRENTHEAP_INVHEAP); ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_SETCURRENTHEAP_INVHEAP); prev = __OSCurrHeap; __OSCurrHeap = heap; return prev; } /*---------------------------------------------------------------------------* Name: OSInitAlloc Description: Initializes the arena in which all heaps will reside. Reserves some small amount of memory for array of heap descriptors. Arguments: arenaStart: beginning addr of arena arenaEnd: ending addr of arena maxHeaps: Maximum number of active heaps that will be used in lifetime of program Returns: start of real arena, aligned with 32 bytes boundaries, after heap array has been allocated *---------------------------------------------------------------------------*/ void* OSInitAlloc(void* arenaStart, void* arenaEnd, int maxHeaps) { u32 arraySize; OSHeapHandle i; ASSERTMSG(0 < maxHeaps, OS_ERR_INITALLOC_INVNUMHEAPS); ASSERTMSG((char*) arenaStart < (char*) arenaEnd, OS_ERR_INITALLOC_INVRANGE); ASSERTMSG(maxHeaps <= ((char*) arenaEnd - (char*) arenaStart) / sizeof(HeapDesc), OS_ERR_INITALLOC_INSRANGE); // Place HeapArray at head of the arena arraySize = sizeof(HeapDesc) * maxHeaps; HeapArray = arenaStart; NumHeaps = maxHeaps; for (i = 0; i < NumHeaps; i++) { HeapDesc* hd = &HeapArray[i]; hd->size = -1; hd->free = hd->allocated = NULL; #ifdef _DEBUG hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0; #endif // _DEBUG } // Set __OSCurrHeap to an invalid value __OSCurrHeap = -1; // Reset arenaStart to the nearest reasonable location arenaStart = (void*) ((char*) HeapArray + arraySize); arenaStart = (void*) ROUND(arenaStart, ALIGNMENT); ArenaStart = arenaStart; ArenaEnd = (void*) TRUNC(arenaEnd, ALIGNMENT); ASSERTMSG(MINOBJSIZE <= (char*) ArenaEnd - (char*) ArenaStart, OS_ERR_INITALLOC_INSRANGE); return arenaStart; } /*---------------------------------------------------------------------------* Name: OSCreateHeap Description: Reserves area of memory from /start/ to /end/ for use as a heap. Initializes heap descriptor and free list. Will consume one entry in heap array. Arguments: start: starting addr of heap end: ending addr of heap Returns: If the function succeeds, it returns a new handle to heap for use in OSAllocFromHeap(), OSFreeToHeap(), etc. If the function fails, the return value is -1. *---------------------------------------------------------------------------*/ OSHeapHandle OSCreateHeap(void* start, void* end) { OSHeapHandle heap; HeapDesc* hd; Cell* cell; ASSERTMSG(HeapArray, OS_ERR_CREATEHEAP_NOHEAP); ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE); start = (void*) ROUND(start, ALIGNMENT); end = (void*) TRUNC(end, ALIGNMENT); ASSERTMSG(start < end, OS_ERR_CREATEHEAP_INVRANGE); ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd), OS_ERR_CREATEHEAP_INVRANGE); ASSERTMSG(MINOBJSIZE <= (char*) end - (char*) start, OS_ERR_CREATEHEAP_INSRANGE); #ifdef _DEBUG // Check that the range does not overlap with // any other block in this or other heaps. for (heap = 0; heap < NumHeaps; heap++) { if (HeapArray[heap].size < 0) continue; ASSERTMSG(!DLOverlap(HeapArray[heap].free, start, end), OS_ERR_CREATEHEAP_INVRANGE); ASSERTMSG(!DLOverlap(HeapArray[heap].allocated, start, end), OS_ERR_CREATEHEAP_INVRANGE); } #endif // _DEBUG // Search for free descriptor for (heap = 0; heap < NumHeaps; heap++) { hd = &HeapArray[heap]; if (hd->size < 0) { hd->size = (char*) end - (char*) start; cell = (Cell*) start; cell->prev = NULL; cell->next = NULL; cell->size = hd->size; #ifdef _DEBUG cell->hd = NULL; #endif // _DEBUG hd->free = cell; hd->allocated = 0; #ifdef _DEBUG hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0; #endif // _DEBUG return heap; // NOT REACHED HERE } } // Could not find free descriptor #ifdef _DEBUG OSReport("OSCreateHeap: Warning - Failed to find free heap descriptor."); #endif // _DEBUG return -1; } /*---------------------------------------------------------------------------* Name: OSDestroyHeap Description: Frees up the descriptor for the /heap/. Subsequent allocation requests from this heap will fail unless another heap is created with the same handle. Arguments: heap: handle to a live heap, previously created with OSCreateHeap(). Returns: None. *---------------------------------------------------------------------------*/ void OSDestroyHeap(OSHeapHandle heap) { HeapDesc* hd; #ifdef _DEBUG long size; #endif ASSERTMSG(HeapArray, OS_ERR_DESTROYHEAP_NOHEAP); ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_DESTROYHEAP_INVHEAP); ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_DESTROYHEAP_INVHEAP); hd = &HeapArray[heap]; #ifdef _DEBUG // Check whether entire heap is empty size = DLSize(hd->free); if (hd->size != size) { OSReport("OSDestroyHeap(%d): Warning - free list size %d, heap size %d\n", heap, size, hd->size); } #endif // _DEBUG hd->size = -1; hd->free = hd->allocated = NULL; #ifdef _DEBUG hd->paddingBytes = hd->headerBytes = hd->payloadBytes = 0; if (__OSCurrHeap == heap) __OSCurrHeap = -1; #endif // _DEBUG } /*---------------------------------------------------------------------------* Name: OSAddToHeap Description: Adds an arbitrary block of memory to /heap/. Used to free blocks previously allocated with OSAllocFixed(), or to create non-contiguous heaps. Arguments: heap: handle to live heap, previously created with OSCreateHeap(). start: starting addr of block to add to /heap/ end: ending addr of block to add to /heap/ Returns: None. *---------------------------------------------------------------------------*/ void OSAddToHeap(OSHeapHandle heap, void* start, void* end) { HeapDesc* hd; Cell* cell; #ifdef _DEBUG OSHeapHandle i; #endif // _DEBUG ASSERTMSG(HeapArray, OS_ERR_ADDTOHEAP_NOHEAP); ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_ADDTOHEAP_INVHEAP); ASSERTMSG(0 <= HeapArray[heap].size, OS_ERR_ADDTOHEAP_INVHEAP); hd = &HeapArray[heap]; ASSERTMSG(start < end, OS_ERR_ADDTOHEAP_INVRANGE); start = (void*) ROUND(start, ALIGNMENT); end = (void*) TRUNC(end, ALIGNMENT); ASSERTMSG(MINOBJSIZE <= (char*) end - (char*) start, OS_ERR_ADDTOHEAP_INSRANGE); ASSERTMSG(RangeSubset(start, end, ArenaStart, ArenaEnd), OS_ERR_ADDTOHEAP_INVRANGE); #ifdef _DEBUG // Check that the range does not already overlap with // any other block in this or other heaps. for (i = 0; i < NumHeaps; i++) { if (HeapArray[i].size < 0) continue; ASSERTMSG(!DLOverlap(HeapArray[i].free, start, end), OS_ERR_ADDTOHEAP_INVRANGE); ASSERTMSG(!DLOverlap(HeapArray[i].allocated, start, end), OS_ERR_ADDTOHEAP_INVRANGE); } #endif // _DEBUG // Create a new cell cell = (Cell*) start; cell->size = (char*) end - (char*) start; #ifdef _DEBUG cell->hd = NULL; #endif // _DEBUG // Insert new cell in free hd->size += cell->size; hd->free = DLInsert(hd->free, cell); } /*---------------------------------------------------------------------------* Name: OSCheckHeap Description: Checks heap sanity for debugging Arguments: heap: handle to a live heap. Returns: -1 if heap is not consistent. Otherwise, returns number of bytes available in free. *---------------------------------------------------------------------------*/ #define CHECK(exp) \ do \ { \ if (!(exp)) \ { \ OSReport("OSCheckHeap: Failed " #exp " in %d", __LINE__); \ return -1; \ } \ } while (0) long OSCheckHeap(OSHeapHandle heap) { HeapDesc* hd; Cell* cell; long total = 0; long free = 0; CHECK(HeapArray); CHECK(0 <= heap && heap < NumHeaps); hd = &HeapArray[heap]; CHECK(0 <= hd->size); CHECK(hd->allocated == NULL || hd->allocated->prev == NULL); for (cell = hd->allocated; cell; cell = cell->next) { CHECK(InRange(cell, ArenaStart, ArenaEnd)); CHECK(OFFSET(cell, ALIGNMENT) == 0); CHECK(cell->next == NULL || cell->next->prev == cell); CHECK(MINOBJSIZE <= cell->size); CHECK(OFFSET(cell->size, ALIGNMENT) == 0); total += cell->size; CHECK(0 < total && total <= hd->size); #ifdef _DEBUG CHECK(cell->hd == hd); CHECK(HEADERSIZE + cell->requested <= cell->size); #endif // _DEBUG } CHECK(hd->free == NULL || hd->free->prev == NULL); for (cell = hd->free; cell; cell = cell->next) { CHECK(InRange(cell, ArenaStart, ArenaEnd)); CHECK(OFFSET(cell, ALIGNMENT) == 0); CHECK(cell->next == NULL || cell->next->prev == cell); CHECK(MINOBJSIZE <= cell->size); CHECK(OFFSET(cell->size, ALIGNMENT) == 0); CHECK(cell->next == NULL || (char*) cell + cell->size < (char*) cell->next); total += cell->size; free += cell->size - HEADERSIZE; CHECK(0 < total && total <= hd->size); #ifdef _DEBUG CHECK(cell->hd == NULL); #endif // _DEBUG } CHECK(total == hd->size); return free; } /*---------------------------------------------------------------------------* Name: OSReferentSize Description: Returns size of payload Arguments: ptr: pointer to object previously returned from OSAlloc() or OSAllocFromHeap(). Returns: size of payload *---------------------------------------------------------------------------*/ u32 OSReferentSize(void* ptr) { Cell* cell; ASSERTMSG(HeapArray, OS_ERR_REFERENT_NOHEAP); ASSERTMSG(InRange(ptr, (char*) ArenaStart + HEADERSIZE, (char*) ArenaEnd), OS_ERR_REFERENT_INVPTR); ASSERTMSG(OFFSET(ptr, ALIGNMENT) == 0, OS_ERR_REFERENT_INVPTR); cell = (Cell*) ((char*) ptr - HEADERSIZE); ASSERTMSG(cell->hd, OS_ERR_REFERENT_INVPTR); ASSERTMSG(((char*) cell->hd - (char*) HeapArray) % sizeof(HeapDesc) == 0, OS_ERR_REFERENT_INVPTR); ASSERTMSG(HeapArray <= cell->hd && cell->hd < &HeapArray[NumHeaps], OS_ERR_REFERENT_INVPTR); ASSERTMSG(0 <= cell->hd->size, OS_ERR_REFERENT_INVPTR); ASSERTMSG(DLLookup(cell->hd->allocated, cell), OS_ERR_REFERENT_INVPTR); return (u32) (cell->size - HEADERSIZE); } /*---------------------------------------------------------------------------* Name: OSDumpHeap Description: Dumps statistics and elements of a heap Arguments: heap: handle to a heap. Returns: None. *---------------------------------------------------------------------------*/ void OSDumpHeap(OSHeapHandle heap) { HeapDesc* hd; Cell* cell; OSReport("\nOSDumpHeap(%d):\n", heap); ASSERTMSG(HeapArray, OS_ERR_DUMPHEAP_NOHEAP); ASSERTMSG(0 <= heap && heap < NumHeaps, OS_ERR_DUMPHEAP_INVHEAP); hd = &HeapArray[heap]; if (hd->size < 0) { OSReport("--------Inactive\n"); return; } ASSERTMSG(0 <= OSCheckHeap(heap), OS_ERR_DUMPHEAP_BROKENHEAP); #ifdef _DEBUG OSReport("padding %d/(%f%%) header %d/(%f%%) payload %d/(%f%%)\n", hd->paddingBytes, 100.0 * hd->paddingBytes / hd->size, hd->headerBytes, 100.0 * hd->headerBytes / hd->size, hd->payloadBytes, 100.0 * hd->payloadBytes / hd->size ); #endif // _DEBUG OSReport("addr\tsize\t\tend\tprev\tnext\n"); OSReport("--------Allocated\n"); ASSERTMSG(hd->allocated == NULL || hd->allocated->prev == NULL, OS_ERR_DUMPHEAP_BROKENHEAP); for (cell = hd->allocated; cell; cell = cell->next) { OSReport("%x\t%d\t%x\t%x\t%x\n", cell, cell->size, (char*) cell + cell->size, cell->prev, cell->next ); } OSReport("--------Free\n"); for (cell = hd->free; cell; cell = cell->next) { OSReport("%x\t%d\t%x\t%x\t%x\n", cell, cell->size, (char*) cell + cell->size, cell->prev, cell->next ); } } /*---------------------------------------------------------------------------* Name: OSVisitAllocated Description: Visits every element of every allocated block of memory, calling a routine on each one. Arguments: visitor: function to be called on each cell Returns: None. *---------------------------------------------------------------------------*/ void OSVisitAllocated(OSAllocVisitor visitor) { u32 heap; Cell* cell; for (heap = 0; heap < NumHeaps; heap++) { if (HeapArray[heap].size >= 0) { for (cell = HeapArray[heap].allocated; cell; cell = cell->next) { visitor((void*)((u8*)cell + HEADERSIZE), (u32)cell->size); } } } }