1185 lines
30 KiB
C
1185 lines
30 KiB
C
#include "precomp.h"
|
|
#pragma hdrstop
|
|
|
|
|
|
// SEGMENT_HEADER is the header that resides at the beginning of every
|
|
// segment of memory managed by this package. For non-growable heaps,
|
|
// there is only one segment for the entire heap. For growable heaps,
|
|
// segments are created as needed whenever there is not enough free space
|
|
// to satisfy an allocation request.
|
|
|
|
typedef struct _SEGMENT_HEADER {
|
|
struct _SEGMENT_HEADER *Next;
|
|
ULONG Size;
|
|
ULONG Spare[ 2 ]; // Make sizeof match granularity
|
|
} SEGMENT_HEADER, *PSEGMENT_HEADER;
|
|
|
|
|
|
// FREE_HEADER is the header that resides at the beginning of every
|
|
// free block of memory managed by this package. All free blocks are
|
|
// linked together on a free list rooted in the heap header. The segment
|
|
// field of a free header prevents free blocks in different segments from
|
|
// being coalesced.
|
|
|
|
typedef struct _FREE_HEADER {
|
|
struct _FREE_HEADER *Next;
|
|
ULONG Size;
|
|
struct _SEGMENT_HEADER *Segment;
|
|
ULONG Spare;
|
|
} FREE_HEADER, *PFREE_HEADER;
|
|
|
|
|
|
// BUSY_HEADER is the header that resides at the beginning of allocated
|
|
// block of memory managed by this package. When the block is
|
|
// allocated, the Busy structure is valid. The address that the user
|
|
// sees actually points to the byte following the header. When the
|
|
// block is on the free list, the Free structure is valid.
|
|
|
|
typedef struct _BUSY_HEADER {
|
|
struct _SEGMENT_HEADER *Segment;
|
|
ULONG Size;
|
|
HANDLE HandleValue;
|
|
ULONG Spare;
|
|
} BUSY_HEADER, *PBUSY_HEADER;
|
|
|
|
|
|
// Flags are stored in the low order two bits of the first word of the
|
|
// header. This is possible, since all blocks are aligned on 16 byte
|
|
// boundaries. To make walking the free list fast, the flag value for
|
|
// a free block is zero, so we can use the Next pointer without modification.
|
|
|
|
#define FLAGS_FREE 0x00000000
|
|
#define FLAGS_BUSY 0x00000001
|
|
#define FLAGS_MASK 0x00000003
|
|
|
|
|
|
// All allocations are made as a multiple of ALLOCATION_GRANULARITY.
|
|
// The size requested is rounded up to a multiple of the allocation
|
|
// granularity. The size of an allocation header is then added and
|
|
// that is the amount of memory that is actually allocated.
|
|
|
|
#define ALLOCATION_GRANULARITY 16 // bytes
|
|
|
|
|
|
// HEAP_HEADER is the header for a heap. All access to the heap is
|
|
// synchronized by the Lock field.
|
|
|
|
typedef struct _HEAP_HEADER {
|
|
|
|
// Heap routines use Length to determine if the heap is valid.
|
|
|
|
ULONG Length;
|
|
|
|
|
|
// If the ZeroExtraMemory field is true, then the heap allocation
|
|
// logic will zero initialize any extra space at the end of an allocated
|
|
// block, due to rounding up to the ALIGNMENT_GRANULARITY amount.
|
|
|
|
BOOLEAN ZeroExtraMemory;
|
|
|
|
|
|
// The address of the first valid address at the begining of the
|
|
// heap. Used for validating pointers passed to AlFreeHeap
|
|
|
|
PVOID ValidAddress;
|
|
|
|
|
|
// The address of the first address of memory beyond the end of the heap
|
|
|
|
PVOID EndAddress;
|
|
|
|
|
|
// FreeList is the header for the heap free list.
|
|
|
|
ULONG Spare; // Make free list align on granularity
|
|
FREE_HEADER FreeList;
|
|
} HEAP_HEADER, *PHEAP_HEADER;
|
|
|
|
|
|
|
|
// The heap is constructed out of a memory descriptor
|
|
// block that is below the descriptor for the loaded program. This block
|
|
// also accomodates the loaded program stack. It is essential therefore
|
|
// to estimate the stack space requirement for your arc program. (16 pages
|
|
// should be enough.) The StackPages and HeapPages are 4K each.
|
|
|
|
|
|
#define HEAP_ZERO_EXTRA_MEMORY 0x00000008
|
|
|
|
// Define memory allocation descriptor listhead and heap storage variables.
|
|
|
|
|
|
ULONG AlHeapFree;
|
|
ULONG AlHeapLimit;
|
|
|
|
PVOID HeapHandle;
|
|
|
|
|
|
PVOID
|
|
AlRtCreateHeap(
|
|
IN ULONG Flags,
|
|
IN PVOID HeapBase,
|
|
IN ULONG Size
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine initializes a heap.
|
|
|
|
Arguments:
|
|
|
|
Flags - Specifies optional attributes of the heap.
|
|
|
|
Valid Flags Values:
|
|
HEAP_ZERO_EXTRA_MEMORY. to make sure that extra memory passed
|
|
in is zeroed out.
|
|
|
|
HeapBase - if not NULL, this specifies the base address for memory
|
|
to use as the heap. If NULL, memory is allocated by these routines.
|
|
|
|
Size - Size of the block of memory passed in to be used as a heap
|
|
|
|
Return Value:
|
|
|
|
PVOID - a pointer to be used in accessing the created heap.
|
|
|
|
--*/
|
|
|
|
{
|
|
PHEAP_HEADER Heap = NULL;
|
|
PFREE_HEADER FreeBlock;
|
|
|
|
|
|
Heap = (PHEAP_HEADER)HeapBase;
|
|
Heap->Length = sizeof( HEAP_HEADER );
|
|
Heap->ZeroExtraMemory = (BOOLEAN)((Flags & HEAP_ZERO_EXTRA_MEMORY) ? TRUE : FALSE);
|
|
Heap->ValidAddress = (PCH)Heap + ((sizeof(*Heap) + (ALLOCATION_GRANULARITY-1)) & ~(ALLOCATION_GRANULARITY-1));
|
|
Heap->EndAddress = (PCH)Heap + Size;
|
|
|
|
|
|
// Initialize the free list to be a single block that starts immediately
|
|
// after the heap header.
|
|
|
|
|
|
FreeBlock = (PFREE_HEADER)Heap->ValidAddress;
|
|
FreeBlock->Next = NULL;
|
|
FreeBlock->Size = (ULONG)Heap->EndAddress -
|
|
(ULONG)FreeBlock;
|
|
FreeBlock->Segment = NULL;
|
|
|
|
Heap->FreeList.Next = FreeBlock;
|
|
Heap->FreeList.Size = 0;
|
|
Heap->FreeList.Segment = NULL;
|
|
|
|
return( (PVOID)Heap );
|
|
} // AlRtCreateHeap
|
|
|
|
|
|
|
|
#if DBG
|
|
|
|
BOOLEAN
|
|
DumpHeapSegment(
|
|
BOOLEAN DumpHeap,
|
|
PHEAP_HEADER Heap,
|
|
PVOID FirstValidBlock,
|
|
PVOID FirstInvalidBlock,
|
|
PULONG CountOfFreeBlocks
|
|
)
|
|
{
|
|
PVOID CurrentBlock = FirstValidBlock;
|
|
PFREE_HEADER FreeBlock;
|
|
PBUSY_HEADER BusyBlock;
|
|
|
|
while (CurrentBlock < FirstInvalidBlock) {
|
|
BusyBlock = CurrentBlock;
|
|
FreeBlock = CurrentBlock;
|
|
if (((ULONG)BusyBlock->Segment & FLAGS_MASK) == FLAGS_BUSY) {
|
|
if (DumpHeap) {
|
|
AlPrint( " %08lx: BUSY Flags=%lx Size: %lx Segment: %lx\n",
|
|
BusyBlock,
|
|
(ULONG)BusyBlock->Segment & FLAGS_MASK,
|
|
BusyBlock->Size,
|
|
(ULONG)BusyBlock->Segment & ~FLAGS_MASK
|
|
);
|
|
}
|
|
|
|
CurrentBlock = (PCH)CurrentBlock + BusyBlock->Size;
|
|
}
|
|
else
|
|
if (((ULONG)FreeBlock->Next & FLAGS_MASK) == FLAGS_FREE) {
|
|
*CountOfFreeBlocks += 1;
|
|
if (DumpHeap) {
|
|
AlPrint( " %08lx: FREE Next=%lx Size: %lx Segment: %lx\n",
|
|
FreeBlock,
|
|
FreeBlock->Next,
|
|
FreeBlock->Size,
|
|
FreeBlock->Segment
|
|
);
|
|
}
|
|
|
|
CurrentBlock = (PCH)CurrentBlock + FreeBlock->Size;
|
|
}
|
|
else {
|
|
if (DumpHeap) {
|
|
AlPrint( "*** Invalid heap block at %lx\n", CurrentBlock );
|
|
}
|
|
|
|
return( FALSE );
|
|
}
|
|
|
|
}
|
|
|
|
if (CurrentBlock != FirstInvalidBlock) {
|
|
if (DumpHeap) {
|
|
AlPrint( "*** Heap segment ends at %lx instead of %lx\n",
|
|
CurrentBlock, FirstInvalidBlock
|
|
);
|
|
}
|
|
|
|
return( FALSE );
|
|
}
|
|
|
|
return( TRUE );
|
|
}
|
|
|
|
|
|
BOOLEAN
|
|
AlRtValidateHeap(
|
|
IN PVOID HeapHandle,
|
|
IN BOOLEAN DumpHeap
|
|
)
|
|
{
|
|
PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle;
|
|
PFREE_HEADER FreeBlock;
|
|
BOOLEAN HeapValid = TRUE;
|
|
ULONG LengthOfFreeList;
|
|
ULONG CountOfFreeBlocks;
|
|
|
|
|
|
// Validate that HeapAddress points to a HEAP_HEADER structure.
|
|
|
|
|
|
if (Heap->Length != sizeof( HEAP_HEADER )) {
|
|
if (DumpHeap) {
|
|
AlPrint( "AlRtHEAP: Invalid heap header- %lx\n", Heap );
|
|
}
|
|
|
|
HeapValid = FALSE;
|
|
goto exit;
|
|
}
|
|
|
|
|
|
if (DumpHeap) {
|
|
AlPrint( "Heap at %lx, Length=%lx\n", Heap, Heap->Length );
|
|
AlPrint( " FreeList: Head=%lx\n", Heap->FreeList.Next );
|
|
AlPrint( " Heap: End Address = %lx\n",Heap->EndAddress);
|
|
}
|
|
|
|
|
|
if (Heap->FreeList.Size != 0) {
|
|
if (DumpHeap) {
|
|
AlPrint( "*** head of free list is invalid (size)\n" );
|
|
}
|
|
|
|
HeapValid = FALSE;
|
|
goto exit;
|
|
}
|
|
|
|
LengthOfFreeList = 0;
|
|
FreeBlock = Heap->FreeList.Next;
|
|
while (FreeBlock) {
|
|
if (DumpHeap) {
|
|
AlPrint( " %08lx: Next=%lx Size: %lx Segment: %lx\n",
|
|
FreeBlock,
|
|
FreeBlock->Next,
|
|
FreeBlock->Size,
|
|
FreeBlock->Segment
|
|
);
|
|
}
|
|
|
|
if (((ULONG)FreeBlock->Next & FLAGS_MASK) != FLAGS_FREE) {
|
|
if (DumpHeap) {
|
|
AlPrint( "*** free list element is not a valid free block\n" );
|
|
}
|
|
|
|
HeapValid = FALSE;
|
|
goto exit;
|
|
}
|
|
|
|
LengthOfFreeList += 1;
|
|
FreeBlock = FreeBlock->Next;
|
|
}
|
|
|
|
CountOfFreeBlocks = 0;
|
|
if (DumpHeap) {
|
|
AlPrint( " Heap Blocks starting at %lx:\n", Heap->ValidAddress );
|
|
}
|
|
|
|
HeapValid = DumpHeapSegment( DumpHeap,
|
|
Heap,
|
|
Heap->ValidAddress,
|
|
Heap->EndAddress,
|
|
&CountOfFreeBlocks
|
|
);
|
|
if (!HeapValid) {
|
|
goto exit;
|
|
}
|
|
|
|
if (LengthOfFreeList != CountOfFreeBlocks) {
|
|
if (DumpHeap) {
|
|
AlPrint( "*** Number of free blocks in arena (%ld) does not match number in the free list (%ld)\n",
|
|
CountOfFreeBlocks,
|
|
LengthOfFreeList
|
|
);
|
|
}
|
|
|
|
HeapValid = FALSE;
|
|
goto exit;
|
|
}
|
|
|
|
exit:
|
|
return( HeapValid );
|
|
|
|
} // AlRtValidateHeap
|
|
|
|
|
|
#else
|
|
|
|
BOOLEAN
|
|
AlRtValidateHeap(
|
|
IN PVOID HeapHandle,
|
|
IN BOOLEAN DumpHeap
|
|
)
|
|
{
|
|
return( TRUE );
|
|
}
|
|
|
|
#endif
|
|
|
|
|
|
|
|
PVOID
|
|
AlRtAllocateHeap(
|
|
IN PVOID HeapHandle,
|
|
IN ULONG Size
|
|
)
|
|
{
|
|
PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle;
|
|
ULONG allocationSize;
|
|
// PSEGMENT_HEADER Segment;
|
|
PFREE_HEADER FreeBlock;
|
|
PFREE_HEADER PreviousFreeBlock;
|
|
PFREE_HEADER NewFreeBlock;
|
|
PBUSY_HEADER BusyBlock;
|
|
|
|
|
|
|
|
// Validate that HeapAddress points to a HEAP_HEADER structure.
|
|
|
|
|
|
if (Heap->Length != sizeof( HEAP_HEADER )) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap );
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
// Additional check, see if the heap is valid, call the heap validation
|
|
// code, requesting it to not dump stuff.
|
|
|
|
if(!AlRtValidateHeap( HeapHandle, FALSE)) {
|
|
|
|
#if DBG
|
|
AlPrint("Heap validation failed\n");
|
|
#endif
|
|
return ( NULL );
|
|
}
|
|
|
|
|
|
|
|
// Round the requested size up to the allocation granularity. Note
|
|
// that if the request is for 0 bytes, we still allocate memory.
|
|
|
|
|
|
allocationSize = ((Size ? Size : ALLOCATION_GRANULARITY) +
|
|
sizeof( BUSY_HEADER ) +
|
|
ALLOCATION_GRANULARITY -
|
|
1
|
|
) & ~(ALLOCATION_GRANULARITY - 1);
|
|
if (allocationSize < Size) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap size - %lx\n", Size );
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
// Point to the free list header.
|
|
|
|
|
|
FreeBlock = &Heap->FreeList;
|
|
#if DBG
|
|
if (FreeBlock->Size != 0) {
|
|
AlPrint( "ALHEAP: Heap free list HEAD hosed at %lx\n", FreeBlock );
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( NULL );
|
|
}
|
|
#endif // DBG
|
|
|
|
|
|
// Continuous loop. We'll break out of the loop when we've found
|
|
// (or created) some free memory.
|
|
|
|
|
|
while (TRUE) {
|
|
|
|
// Have we reached the end of the free list?
|
|
|
|
|
|
if (FreeBlock->Next == NULL)
|
|
return( NULL );
|
|
else {
|
|
|
|
// Point to the next free block, saving a pointer to the
|
|
// previous one.
|
|
|
|
|
|
PreviousFreeBlock = FreeBlock;
|
|
FreeBlock = PreviousFreeBlock->Next;
|
|
}
|
|
|
|
#if DBG
|
|
if (FreeBlock->Size == 0) {
|
|
AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n",
|
|
FreeBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
return( NULL );
|
|
}
|
|
#endif // DBG
|
|
|
|
|
|
// We haven't exhausted the free list yet. If this block is
|
|
// large enough for what we need, break out of the while loop.
|
|
|
|
|
|
if (FreeBlock->Size >= allocationSize) {
|
|
break;
|
|
}
|
|
|
|
} // while ( TRUE )
|
|
|
|
|
|
// We have found a free block that is large enough to hold what the
|
|
// user requested. If it's exactly the right size, simply point the
|
|
// previous free block to the successor of this free block. If it's
|
|
// larger than what we want, we allocate from the front of the block,
|
|
// leaving the trailing part free. Exactly the right size is fuzzy,
|
|
// as if we decide to split we need at least enough extra space for
|
|
// a free header plus some space to statisfy an allocation.
|
|
|
|
|
|
if ((FreeBlock->Size - allocationSize) < (2 * sizeof( FREE_HEADER ))) {
|
|
|
|
// If the amount of extra space is less than twice the size of
|
|
// a free header, just give the caller all the space, as the
|
|
// extra amount is too small to waste a free block on.
|
|
|
|
|
|
allocationSize = FreeBlock->Size;
|
|
|
|
|
|
// Exactly the right size. Point previous free block to the
|
|
// next free block.
|
|
|
|
|
|
PreviousFreeBlock->Next = FreeBlock->Next;
|
|
|
|
}
|
|
else {
|
|
|
|
|
|
// More memory than we need. Make the trailing part of the block
|
|
// into a free block. Point the previous block to the new block
|
|
// and the new block to the next block.
|
|
|
|
|
|
NewFreeBlock = (PFREE_HEADER)((PCH)FreeBlock + allocationSize);
|
|
PreviousFreeBlock->Next = NewFreeBlock;
|
|
NewFreeBlock->Next = FreeBlock->Next;
|
|
NewFreeBlock->Size = FreeBlock->Size - allocationSize;
|
|
NewFreeBlock->Segment = FreeBlock->Segment;
|
|
}
|
|
|
|
|
|
// Set up the header for the allocated block.
|
|
|
|
|
|
BusyBlock = (PBUSY_HEADER)FreeBlock;
|
|
BusyBlock->Segment = (PSEGMENT_HEADER)((ULONG)FreeBlock->Segment |
|
|
FLAGS_BUSY
|
|
);
|
|
BusyBlock->Size = allocationSize;
|
|
BusyBlock->HandleValue = NULL;
|
|
|
|
if (Heap->ZeroExtraMemory) {
|
|
ULONG extraSize;
|
|
|
|
extraSize = allocationSize - Size - sizeof( BUSY_HEADER );
|
|
memset( (PCHAR)BusyBlock + (allocationSize - extraSize),
|
|
0,
|
|
extraSize
|
|
);
|
|
}
|
|
|
|
#if DBG
|
|
BusyBlock->Spare = 0;
|
|
#endif
|
|
|
|
|
|
// Return the address of the user portion of the allocated block.
|
|
// This is the byte following the header.
|
|
|
|
|
|
return( (PVOID)(BusyBlock + 1) );
|
|
} // AlRtAllocateHeap
|
|
|
|
|
|
PVOID
|
|
AlRtFreeHeap(
|
|
IN PVOID HeapHandle,
|
|
IN PVOID BaseAddress
|
|
)
|
|
{
|
|
PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle;
|
|
PFREE_HEADER FreeBlock;
|
|
PFREE_HEADER PreviousFreeBlock;
|
|
PFREE_HEADER SecondPrevFreeBlock;
|
|
PBUSY_HEADER BusyBlock;
|
|
PSEGMENT_HEADER BusySegment;
|
|
ULONG BusyFlags;
|
|
ULONG BusySize;
|
|
|
|
if (BaseAddress == NULL) {
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
// Validate that HeapAddress points to a HEAP_HEADER structure.
|
|
|
|
|
|
if (Heap->Length != sizeof( HEAP_HEADER )) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap );
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( BaseAddress );
|
|
}
|
|
|
|
|
|
// Additional check, see if the heap is valid, call the heap validation
|
|
// code, requesting it to not dump stuff.
|
|
|
|
if(!AlRtValidateHeap( HeapHandle, FALSE)) {
|
|
|
|
#if DBG
|
|
AlPrint("Heap validation failed\n");
|
|
#endif
|
|
return ( BaseAddress );
|
|
}
|
|
|
|
|
|
|
|
// Get the 'real' address of the allocation unit. (That is, the
|
|
// address of the allocation header.) Make sure the address lies
|
|
// within the bounds of the valid portion of the heap.
|
|
|
|
|
|
BusyBlock = (PBUSY_HEADER)BaseAddress - 1;
|
|
BusyFlags = (ULONG)BusyBlock->Segment & FLAGS_MASK;
|
|
BusySegment = (PSEGMENT_HEADER)((ULONG)BusyBlock->Segment & ~FLAGS_MASK);
|
|
BusySize = BusyBlock->Size;
|
|
|
|
if (BusyFlags != FLAGS_BUSY
|
|
#if DBG
|
|
|| (BusySegment == NULL &&
|
|
((PCHAR)BusyBlock < (PCHAR)Heap->ValidAddress ||
|
|
(PCHAR)BusyBlock >= (PCHAR)Heap->EndAddress
|
|
)
|
|
) ||
|
|
(BusySegment != NULL &&
|
|
(BusyBlock < (PBUSY_HEADER)(BusySegment+1) ||
|
|
BusyBlock >= (PBUSY_HEADER)((ULONG)BusySegment + BusySegment->Size)
|
|
)
|
|
) ||
|
|
(BusySize < ALLOCATION_GRANULARITY
|
|
) ||
|
|
(BusySize & (ALLOCATION_GRANULARITY-1) != 0
|
|
)
|
|
#endif // DBG
|
|
) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid Address specified to AlRtFreeHeap( %lx, %lx )\n",
|
|
Heap,
|
|
BaseAddress
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( BaseAddress );
|
|
}
|
|
|
|
|
|
|
|
// Free blocks are stored in the free list in ascending order by
|
|
// base address. As we search the free list to find the place for
|
|
// this block, we remember the previous two free blocks that we
|
|
// passed through. These are used during combining of adjacent
|
|
// free blocks.
|
|
|
|
|
|
SecondPrevFreeBlock = NULL;
|
|
PreviousFreeBlock = &Heap->FreeList;
|
|
#if DBG
|
|
if (PreviousFreeBlock->Size != 0) {
|
|
AlPrint( "ALHEAP: Heap free list HEAD hosed at %lx\n",
|
|
PreviousFreeBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( BaseAddress );
|
|
}
|
|
#endif // DBG
|
|
|
|
|
|
// Continuous loop. We'll break out of the loop when we've found
|
|
// the first block of free memory whose address is larger than the
|
|
// address of the block being freed. (Or the end of the free list.)
|
|
|
|
|
|
while (TRUE) {
|
|
|
|
|
|
// Get the address of the next free block. If we've exhausted
|
|
// the free list, break out of the loop -- the block we're
|
|
// freeing goes at the end of the list.
|
|
|
|
|
|
FreeBlock = PreviousFreeBlock->Next;
|
|
|
|
if (FreeBlock == NULL) {
|
|
break;
|
|
}
|
|
|
|
#if DBG
|
|
if (FreeBlock->Size == 0) {
|
|
AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n",
|
|
FreeBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( BaseAddress );
|
|
}
|
|
#endif // DBG
|
|
|
|
|
|
// If the address of the current block is higher than the
|
|
// address of the block we're freeing, break out of the loop.
|
|
// The freed block goes immediately before the current block.
|
|
|
|
|
|
if (FreeBlock > (PFREE_HEADER)BusyBlock) {
|
|
break;
|
|
}
|
|
|
|
|
|
// We haven't found the spot yet. Remember the last two blocks.
|
|
|
|
|
|
SecondPrevFreeBlock = PreviousFreeBlock;
|
|
PreviousFreeBlock = FreeBlock;
|
|
|
|
} // while ( TRUE )
|
|
|
|
|
|
|
|
// We've found the place for the block we're freeing. If the previous
|
|
// block is adjacent to this one, merge the two by summing their sizes,
|
|
// adjusting the address of the block being freed, and making the second
|
|
// previous block the first previous block. (Note that the previous
|
|
// block may actually be the listhead. In this case, the if condition
|
|
// will never be true, because the Size of the listhead is 0.)
|
|
|
|
|
|
if (((PCH)PreviousFreeBlock + PreviousFreeBlock->Size) == (PCH)BusyBlock &&
|
|
PreviousFreeBlock->Segment == BusySegment
|
|
) {
|
|
BusySize += PreviousFreeBlock->Size;
|
|
BusyBlock = (PBUSY_HEADER)PreviousFreeBlock;
|
|
PreviousFreeBlock = SecondPrevFreeBlock;
|
|
#if DBG
|
|
}
|
|
else
|
|
if ((PreviousFreeBlock != &Heap->FreeList) &&
|
|
((PCH)PreviousFreeBlock + PreviousFreeBlock->Size) > (PCH)BusyBlock
|
|
) {
|
|
AlPrint( "ALHEAP: Heap free list overlaps freed block at %lx\n",
|
|
BusyBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( BaseAddress );
|
|
#endif // DBG
|
|
}
|
|
|
|
|
|
// If the block being freed is adjacent to the current block, merge
|
|
// the two by summing their sizes and making the next block the
|
|
// current block. (Note that the current block may not exist, in
|
|
// which case FreeBlock == NULL, and the if condition will not be
|
|
// true.)
|
|
//*** There is an assumption here that we'll never EVER use the
|
|
//*** very highest part of the address space for user mode allocatable
|
|
//*** memory!
|
|
|
|
|
|
if (((PCH)BusyBlock + BusySize) == (PCH)FreeBlock &&
|
|
FreeBlock->Segment == BusySegment
|
|
) {
|
|
BusySize += FreeBlock->Size;
|
|
FreeBlock = FreeBlock->Next;
|
|
#if DBG
|
|
if (FreeBlock != NULL) {
|
|
if (FreeBlock->Size == 0) {
|
|
AlPrint( "ALHEAP: Heap free list ENTRY hosed at %lx\n",
|
|
FreeBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( BaseAddress );
|
|
}
|
|
}
|
|
}
|
|
else
|
|
if ((FreeBlock != NULL) &&
|
|
((PCH)BusyBlock + BusySize) > (PCH)FreeBlock
|
|
) {
|
|
AlPrint( "ALHEAP: Freed block overlaps heap free list at %lx\n",
|
|
BusyBlock
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
|
|
return( BaseAddress );
|
|
#endif // DBG
|
|
}
|
|
|
|
|
|
// Done merging. Update the free list and the free block header.
|
|
//*** May want to reclaim (i.e., release) pages sometime. That is,
|
|
//*** if we find ourselves with oodles of contiguous pages on the
|
|
//*** free list, we could delete them from our address space. On
|
|
//*** the other hand, it probably doesn't cost very much to keep
|
|
//*** them around, and if the process needed that much memory once,
|
|
//*** it's likely to need it again.
|
|
|
|
|
|
PreviousFreeBlock->Next = (PFREE_HEADER)BusyBlock;
|
|
((PFREE_HEADER)BusyBlock)->Next = FreeBlock;
|
|
((PFREE_HEADER)BusyBlock)->Size = BusySize;
|
|
((PFREE_HEADER)BusyBlock)->Segment = BusySegment;
|
|
|
|
|
|
// Release the free list lock and return to the caller.
|
|
|
|
|
|
|
|
return( NULL );
|
|
} // AlRtFreeHeap
|
|
|
|
|
|
|
|
PVOID
|
|
AlRtReAllocateHeap(
|
|
IN PVOID HeapHandle,
|
|
IN PVOID BaseAddress,
|
|
IN ULONG Size
|
|
)
|
|
{
|
|
PHEAP_HEADER Heap = (PHEAP_HEADER)HeapHandle;
|
|
PVOID NewBaseAddress;
|
|
ULONG allocationSize;
|
|
PBUSY_HEADER BusyBlock;
|
|
PBUSY_HEADER ExtraBusyBlock;
|
|
PSEGMENT_HEADER BusySegment;
|
|
ULONG BusyFlags;
|
|
ULONG BusySize;
|
|
LONG DeltaSize;
|
|
|
|
|
|
// Validate that HeapAddress points to a HEAP_HEADER structure.
|
|
|
|
|
|
if (Heap->Length != sizeof( HEAP_HEADER )) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap header- %lx\n", Heap );
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
// Additional check, see if the heap is valid, call the heap validation
|
|
// code, requesting it to not dump stuff.
|
|
|
|
if(!AlRtValidateHeap( HeapHandle, FALSE)) {
|
|
|
|
#if DBG
|
|
AlPrint("Heap validation failed\n");
|
|
#endif
|
|
return ( NULL );
|
|
}
|
|
|
|
|
|
|
|
// Round the requested size up to the allocation granularity. Note
|
|
// that if the request is for 0 bytes, we still allocate memory.
|
|
|
|
|
|
allocationSize = ((Size ? Size : ALLOCATION_GRANULARITY) +
|
|
sizeof( BUSY_HEADER ) +
|
|
ALLOCATION_GRANULARITY -
|
|
1
|
|
) & ~(ALLOCATION_GRANULARITY - 1);
|
|
|
|
if (allocationSize < Size) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap size - %lx\n", Size );
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
if (BaseAddress == NULL) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid heap address - %lx\n", BaseAddress );
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
// Get the 'real' address of the allocation unit. (That is, the
|
|
// address of the allocation header.) Make sure the address lies
|
|
// within the bounds of the valid portion of the heap.
|
|
|
|
|
|
BusyBlock = (PBUSY_HEADER)BaseAddress - 1;
|
|
BusySize = BusyBlock->Size;
|
|
BusySegment = (PSEGMENT_HEADER)((ULONG)BusyBlock->Segment & ~FLAGS_MASK);
|
|
BusyFlags = (ULONG)BusyBlock->Segment & FLAGS_MASK;
|
|
|
|
if (BusyFlags != FLAGS_BUSY
|
|
#if DBG
|
|
|| (BusySegment == NULL &&
|
|
((PCHAR)BusyBlock < (PCHAR)Heap->ValidAddress ||
|
|
(PCHAR)BusyBlock >= (PCHAR)Heap->EndAddress
|
|
)
|
|
) ||
|
|
(BusySegment != NULL &&
|
|
(BusyBlock < (PBUSY_HEADER)(BusySegment+1) ||
|
|
BusyBlock >= (PBUSY_HEADER)((ULONG)BusySegment + BusySegment->Size)
|
|
)
|
|
) ||
|
|
(BusySize < ALLOCATION_GRANULARITY
|
|
) ||
|
|
(BusySize & (ALLOCATION_GRANULARITY-1) != 0
|
|
)
|
|
#endif // DBG
|
|
) {
|
|
#if DBG
|
|
AlPrint( "ALHEAP: Invalid Address specified to AlRtFreeHeap( %lx, %lx )\n",
|
|
Heap,
|
|
BaseAddress
|
|
);
|
|
// RtlpBreakPointHeap();
|
|
#endif // DBG
|
|
return( NULL );
|
|
}
|
|
|
|
|
|
|
|
// See if new size less than or equal to the current size.
|
|
|
|
|
|
DeltaSize = (LONG)(BusySize - allocationSize);
|
|
if (DeltaSize >= 0) {
|
|
|
|
// Then shrinking block. If amount of shrinkage is less than
|
|
// the size of a free block, then nothing to do.
|
|
|
|
|
|
if (DeltaSize < sizeof( FREE_HEADER )) {
|
|
if (Heap->ZeroExtraMemory) {
|
|
memset( (PCHAR)BusyBlock + (allocationSize - DeltaSize),0,
|
|
DeltaSize
|
|
);
|
|
}
|
|
|
|
return( BaseAddress );
|
|
}
|
|
|
|
|
|
// Otherwise, shrink size of this block to new size, and make extra
|
|
// space at end look like another busy block and call AlRtFreeHeap
|
|
// to free it.
|
|
|
|
|
|
BusyBlock->Size = allocationSize;
|
|
ExtraBusyBlock = (PBUSY_HEADER)((PCH)BusyBlock + allocationSize);
|
|
ExtraBusyBlock->Segment = BusyBlock->Segment;
|
|
ExtraBusyBlock->Size = (ULONG)(DeltaSize);
|
|
#if DBG
|
|
ExtraBusyBlock->Spare = 0;
|
|
#endif
|
|
|
|
AlRtFreeHeap( HeapHandle, (PVOID)(ExtraBusyBlock+1) );
|
|
|
|
if (Heap->ZeroExtraMemory) {
|
|
ULONG extraSize;
|
|
|
|
extraSize = allocationSize - Size - sizeof( BUSY_HEADER );
|
|
memset( (PCHAR)BusyBlock + (allocationSize - extraSize),0,
|
|
extraSize
|
|
);
|
|
}
|
|
|
|
return( BaseAddress );
|
|
}
|
|
|
|
|
|
// Otherwise growing block, so allocate a new block with the bigger
|
|
// size, copy the contents of the old block to the new block and then
|
|
// free the old block. Return the address of the new block.
|
|
|
|
|
|
NewBaseAddress = AlRtAllocateHeap( HeapHandle, Size );
|
|
if (NewBaseAddress != NULL) {
|
|
#if DBG
|
|
ExtraBusyBlock = (PBUSY_HEADER)NewBaseAddress - 1;
|
|
ExtraBusyBlock->Spare = 0;
|
|
#endif
|
|
memmove( NewBaseAddress,
|
|
BaseAddress,
|
|
BusySize - sizeof( BUSY_HEADER )
|
|
);
|
|
|
|
AlRtFreeHeap( HeapHandle, BaseAddress );
|
|
}
|
|
|
|
return( NewBaseAddress );
|
|
}
|
|
|
|
|
|
|
|
|
|
ARC_STATUS
|
|
AlMemoryInitialize (
|
|
ULONG StackPages,
|
|
ULONG HeapPages
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine allocates stack space for the OS loader, initializes
|
|
heap storage, and initializes the memory allocation list.
|
|
|
|
Arguments:
|
|
|
|
None.
|
|
|
|
Return Value:
|
|
|
|
ESUCCESS is returned if the initialization is successful. Otherwise,
|
|
ENOMEM is returned.
|
|
|
|
--*/
|
|
|
|
{
|
|
|
|
PMEMORY_DESCRIPTOR FreeDescriptor;
|
|
PMEMORY_DESCRIPTOR ProgramDescriptor;
|
|
|
|
|
|
// Find the memory descriptor that describes the allocation for the OS
|
|
// loader itself.
|
|
|
|
|
|
ProgramDescriptor = NULL;
|
|
while ((ProgramDescriptor = ArcGetMemoryDescriptor(ProgramDescriptor)) != NULL) {
|
|
if (ProgramDescriptor->MemoryType == MemoryLoadedProgram) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
// If a loaded program memory descriptor was found, then it must be
|
|
// for the OS loader since that is the only program that can be loaded.
|
|
// If a loaded program memory descriptor was not found, then firmware
|
|
// is not functioning properly and an unsuccessful status is returned.
|
|
|
|
|
|
if (ProgramDescriptor == NULL) {
|
|
return ENOMEM;
|
|
}
|
|
|
|
|
|
// Find the free memory descriptor that is just below the loaded
|
|
// program in memory. There should be several megabytes of free
|
|
// memory just preceeding the OS loader.
|
|
|
|
|
|
FreeDescriptor = NULL;
|
|
while ((FreeDescriptor = ArcGetMemoryDescriptor(FreeDescriptor)) != NULL) {
|
|
if ((FreeDescriptor->MemoryType == MemoryFree) &&
|
|
(FreeDescriptor->PageCount >= (StackPages+HeapPages))) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
// If a free memory descriptor was not found that describes the free
|
|
// memory just below the OS loader, then firmware is not functioning
|
|
// properly and an unsuccessful status is returned.
|
|
|
|
|
|
if (FreeDescriptor == NULL) {
|
|
return ENOMEM;
|
|
}
|
|
|
|
|
|
// Check to determine if enough free memory is available for the OS
|
|
// loader stack and the heap area. If enough memory is not available,
|
|
// then return an unsuccessful status.
|
|
|
|
|
|
if (FreeDescriptor->PageCount < (StackPages + HeapPages)) {
|
|
return ENOMEM;
|
|
}
|
|
|
|
|
|
// Compute the address of the loader heap, initialize the heap
|
|
// allocation variables, and zero the heap memory.
|
|
|
|
|
|
AlHeapFree = KSEG0_BASE | ((ProgramDescriptor->BasePage -
|
|
(StackPages + HeapPages)) << PAGE_SHIFT);
|
|
|
|
AlHeapLimit = AlHeapFree + (HeapPages << PAGE_SHIFT);
|
|
|
|
memset((PVOID)AlHeapFree, 0,HeapPages << PAGE_SHIFT);
|
|
|
|
|
|
|
|
// Changed to new heap allocater
|
|
|
|
|
|
if ((HeapHandle = AlRtCreateHeap
|
|
(
|
|
HEAP_ZERO_EXTRA_MEMORY,
|
|
(PVOID)AlHeapFree,
|
|
HeapPages << PAGE_SHIFT
|
|
))
|
|
== NULL)
|
|
return ENOMEM;
|
|
else
|
|
return ESUCCESS;
|
|
|
|
}
|
|
|
|
|
|
|
|
// AlAllocateHeap.
|
|
|
|
// Heap space allocator. Size is in bytes required.
|
|
|
|
PVOID
|
|
AlAllocateHeap (
|
|
IN ULONG Size
|
|
)
|
|
{
|
|
return (AlRtAllocateHeap
|
|
(
|
|
HeapHandle,
|
|
Size
|
|
));
|
|
|
|
}
|
|
|
|
|
|
|
|
// 3. AlDeallocateHeap
|
|
|
|
// Heap Deallocation needs to be defined and implemented.
|
|
|
|
|
|
|
|
PVOID
|
|
AlDeallocateHeap (
|
|
IN PVOID HeapAddress
|
|
)
|
|
{
|
|
return (AlRtFreeHeap
|
|
(
|
|
HeapHandle,
|
|
HeapAddress
|
|
));
|
|
}
|
|
|
|
|
|
|
|
// 4. AlReallocateHeap
|
|
|
|
|
|
|
|
|
|
PVOID
|
|
AlReallocateHeap (
|
|
IN PVOID HeapAddress,
|
|
IN ULONG NewSize
|
|
)
|
|
{
|
|
return (AlRtReAllocateHeap
|
|
(
|
|
HeapHandle,
|
|
HeapAddress,
|
|
NewSize
|
|
));
|
|
}
|
|
|
|
|
|
// 5. AlValidateHeap
|
|
|
|
// Heap validation
|
|
|
|
|
|
|
|
BOOLEAN
|
|
AlValidateHeap(
|
|
IN BOOLEAN DumpHeap
|
|
)
|
|
{
|
|
return (AlRtValidateHeap
|
|
(
|
|
HeapHandle,
|
|
DumpHeap
|
|
));
|
|
}
|
|
|