diff options
Diffstat (limited to 'private/ntos/rtl/heap.c')
| -rw-r--r-- | private/ntos/rtl/heap.c | 2772 |
1 files changed, 2772 insertions, 0 deletions
diff --git a/private/ntos/rtl/heap.c b/private/ntos/rtl/heap.c new file mode 100644 index 000000000..041a2a87c --- /dev/null +++ b/private/ntos/rtl/heap.c @@ -0,0 +1,2772 @@ +/*++ + +Copyright (c) 1989 Microsoft Corporation + +Module Name: + + heap.c + +Abstract: + + This module implements a heap allocator. + +Author: + + Steve Wood (stevewo) 20-Sep-1989 (Adapted from URTL\alloc.c) + +Revision History: + +--*/ + +#include "ntrtlp.h" +#include "heap.h" +#include "heappriv.h" + +#if defined(NTOS_KERNEL_RUNTIME) +#if defined(ALLOC_PRAGMA) +PHEAP_UNCOMMMTTED_RANGE +RtlpCreateUnCommittedRange( + IN PHEAP_SEGMENT Segment + ); + +VOID +RtlpDestroyUnCommittedRange( + IN PHEAP_SEGMENT Segment, + IN PHEAP_UNCOMMMTTED_RANGE UnCommittedRange + ); + +VOID +RtlpInsertUnCommittedPages( + IN PHEAP_SEGMENT Segment, + IN ULONG Address, + IN ULONG Size + ); + +NTSTATUS +RtlpDestroyHeapSegment( + IN PHEAP_SEGMENT Segment + ); + +PHEAP_FREE_ENTRY +RtlpExtendHeap( + IN PHEAP Heap, + IN ULONG AllocationSize + ); + + +#pragma alloc_text(PAGE, RtlpCreateUnCommittedRange) +#pragma alloc_text(PAGE, RtlpDestroyUnCommittedRange) +#pragma alloc_text(PAGE, RtlpInsertUnCommittedPages) +#pragma alloc_text(PAGE, RtlpFindAndCommitPages) +#pragma alloc_text(PAGE, RtlpInitializeHeapSegment) +#pragma alloc_text(PAGE, RtlpDestroyHeapSegment) +#pragma alloc_text(PAGE, RtlCreateHeap) +#pragma alloc_text(PAGE, RtlDestroyHeap) +#pragma alloc_text(PAGE, RtlpExtendHeap) +#pragma alloc_text(PAGE, RtlpCoalesceFreeBlocks) +#pragma alloc_text(PAGE, RtlpDeCommitFreeBlock) +#pragma alloc_text(PAGE, RtlpInsertFreeBlock) +#pragma alloc_text(PAGE, RtlAllocateHeap) +#pragma alloc_text(PAGE, RtlFreeHeap) +#pragma alloc_text(PAGE, RtlpGetSizeOfBigBlock) +#pragma alloc_text(PAGE, RtlpCheckBusyBlockTail) +#pragma alloc_text(PAGE, RtlZeroHeap) +#endif + +#else + +PVOID +RtlDebugCreateHeap( + IN ULONG Flags, + IN PVOID HeapBase OPTIONAL, + IN ULONG ReserveSize OPTIONAL, + IN ULONG CommitSize OPTIONAL, + IN PVOID Lock OPTIONAL, + IN PRTL_HEAP_PARAMETERS Parameters OPTIONAL + ); + +BOOLEAN +RtlDebugDestroyHeap( + IN PVOID HeapHandle + ); + +PVOID +RtlDebugAllocateHeap( + IN PVOID HeapHandle, + IN ULONG Flags, + IN ULONG Size + ); + +BOOLEAN +RtlDebugFreeHeap( + IN PVOID HeapHandle, + IN ULONG Flags, + IN PVOID BaseAddress + ); + +NTSTATUS +RtlDebugZeroHeap( + IN PVOID HeapHandle, + IN ULONG Flags + ); + +PVOID +RtlAllocateHeapSlowly( + IN PVOID HeapHandle, + IN ULONG Flags, + IN ULONG Size + ); + +BOOLEAN +RtlFreeHeapSlowly( + IN PVOID HeapHandle, + IN ULONG Flags, + IN PVOID BaseAddress + ); + +#endif // NTOS_KERNEL_RUNTIME + +// +// If any of these flags are set, the fast allocator punts +// to the slow do-everything allocator. +// +#define HEAP_SLOW_FLAGS (HEAP_DEBUG_FLAGS | \ + HEAP_SETTABLE_USER_FLAGS | \ + HEAP_NEED_EXTRA_FLAGS | \ + HEAP_CREATE_ALIGN_16 | \ + HEAP_FREE_CHECKING_ENABLED | \ + HEAP_TAIL_CHECKING_ENABLED) + +UCHAR CheckHeapFillPattern[ CHECK_HEAP_TAIL_SIZE ] = { + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL, + CHECK_HEAP_TAIL_FILL +}; + +PHEAP_UNCOMMMTTED_RANGE +RtlpCreateUnCommittedRange( + IN PHEAP_SEGMENT Segment + ) +{ + NTSTATUS Status; + PVOID FirstEntry, LastEntry; + PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp; + ULONG ReserveSize, CommitSize; + PHEAP_UCR_SEGMENT UCRSegment; + + RTL_PAGED_CODE(); + + pp = &Segment->Heap->UnusedUnCommittedRanges; + if (*pp == NULL) { + UCRSegment = Segment->Heap->UCRSegments; + if (UCRSegment == NULL || + UCRSegment->CommittedSize == UCRSegment->ReservedSize + ) { + ReserveSize = 0x10000; + UCRSegment = NULL; + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + &UCRSegment, + 0, + &ReserveSize, + MEM_RESERVE, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + return NULL; + } + + CommitSize = 0x1000; + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + &UCRSegment, + 0, + &CommitSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + ZwFreeVirtualMemory( NtCurrentProcess(), + &UCRSegment, + &ReserveSize, + MEM_RELEASE + ); + return NULL; + } + + UCRSegment->Next = Segment->Heap->UCRSegments; + Segment->Heap->UCRSegments = UCRSegment; + UCRSegment->ReservedSize = ReserveSize; + UCRSegment->CommittedSize = CommitSize; + FirstEntry = (PCHAR)(UCRSegment + 1); + } + else { + CommitSize = 0x1000; + FirstEntry = (PCHAR)UCRSegment + UCRSegment->CommittedSize; + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + &FirstEntry, + 0, + &CommitSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + return NULL; + } + + UCRSegment->CommittedSize += CommitSize; + } + + LastEntry = (PCHAR)UCRSegment + UCRSegment->CommittedSize; + UnCommittedRange = (PHEAP_UNCOMMMTTED_RANGE)FirstEntry; + pp = &Segment->Heap->UnusedUnCommittedRanges; + while ((PCHAR)UnCommittedRange < (PCHAR)LastEntry) { + *pp = UnCommittedRange; + pp = &UnCommittedRange->Next; + UnCommittedRange += 1; + } + *pp = NULL; + pp = &Segment->Heap->UnusedUnCommittedRanges; + } + + UnCommittedRange = *pp; + *pp = UnCommittedRange->Next; + return UnCommittedRange; +} + + +VOID +RtlpDestroyUnCommittedRange( + IN PHEAP_SEGMENT Segment, + IN PHEAP_UNCOMMMTTED_RANGE UnCommittedRange + ) +{ + RTL_PAGED_CODE(); + + UnCommittedRange->Next = Segment->Heap->UnusedUnCommittedRanges; + Segment->Heap->UnusedUnCommittedRanges = UnCommittedRange; + UnCommittedRange->Address = 0; + UnCommittedRange->Size = 0; + return; +} + +VOID +RtlpInsertUnCommittedPages( + IN PHEAP_SEGMENT Segment, + IN ULONG Address, + IN ULONG Size + ) +{ + PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp; + + RTL_PAGED_CODE(); + + pp = &Segment->UnCommittedRanges; + while (UnCommittedRange = *pp) { + if (UnCommittedRange->Address > Address) { + if (Address + Size == UnCommittedRange->Address) { + UnCommittedRange->Address = Address; + UnCommittedRange->Size += Size; + if (UnCommittedRange->Size > Segment->LargestUnCommittedRange) { + Segment->LargestUnCommittedRange = UnCommittedRange->Size; + } + + return; + } + + break; + } + else + if ((UnCommittedRange->Address + UnCommittedRange->Size) == Address) { + Address = UnCommittedRange->Address; + Size += UnCommittedRange->Size; + + *pp = UnCommittedRange->Next; + RtlpDestroyUnCommittedRange( Segment, UnCommittedRange ); + Segment->NumberOfUnCommittedRanges -= 1; + + if (Size > Segment->LargestUnCommittedRange) { + Segment->LargestUnCommittedRange = Size; + } + } + else { + pp = &UnCommittedRange->Next; + } + } + + UnCommittedRange = RtlpCreateUnCommittedRange( Segment ); + if (UnCommittedRange == NULL) { + HeapDebugPrint(( "Abandoning uncommitted range (%x for %x)\n", Address, Size )); + HeapDebugBreak( NULL ); + return; + } + + UnCommittedRange->Address = Address; + UnCommittedRange->Size = Size; + UnCommittedRange->Next = *pp; + *pp = UnCommittedRange; + Segment->NumberOfUnCommittedRanges += 1; + if (Size >= Segment->LargestUnCommittedRange) { + Segment->LargestUnCommittedRange = Size; + } + + return; +} + + + +PHEAP_FREE_ENTRY +RtlpFindAndCommitPages( + IN PHEAP Heap, + IN PHEAP_SEGMENT Segment, + IN OUT PULONG Size, + IN PVOID AddressWanted OPTIONAL + ) +{ + NTSTATUS Status; + PHEAP_ENTRY FirstEntry, LastEntry, PreviousLastEntry; + PHEAP_UNCOMMMTTED_RANGE PreviousUnCommittedRange, UnCommittedRange, *pp; + ULONG Address; + + RTL_PAGED_CODE(); + + PreviousUnCommittedRange = NULL; + pp = &Segment->UnCommittedRanges; + while (UnCommittedRange = *pp) { + if (UnCommittedRange->Size >= *Size && + (!ARGUMENT_PRESENT( AddressWanted ) || UnCommittedRange->Address == (ULONG)AddressWanted ) + ) { + Address = UnCommittedRange->Address; + if (Heap->CommitRoutine != NULL) { + Status = (Heap->CommitRoutine)( Heap, + (PVOID *)&Address, + Size + ); + } + else { + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&Address, + 0, + Size, + MEM_COMMIT, + PAGE_READWRITE + ); + } + if (!NT_SUCCESS( Status )) { + return NULL; + } + + HeapInternalTrace( Segment->Heap, (Segment->Heap->TraceBuffer, HEAP_TRACE_COMMIT_MEMORY, 2, Address, *Size) ); + + Segment->NumberOfUnCommittedPages -= *Size / PAGE_SIZE; + if (Segment->LargestUnCommittedRange == UnCommittedRange->Size) { + Segment->LargestUnCommittedRange = 0; + } + + FirstEntry = (PHEAP_ENTRY)Address; + + if (PreviousUnCommittedRange == NULL) { + LastEntry = Segment->FirstEntry; + } + else { + LastEntry = (PHEAP_ENTRY)(PreviousUnCommittedRange->Address + + PreviousUnCommittedRange->Size); + } + while (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) { + PreviousLastEntry = LastEntry; + LastEntry += LastEntry->Size; + if ((PCHAR)LastEntry >= (PCHAR)Segment->LastValidEntry || LastEntry->Size==0) { + HeapDebugPrint(( "Heap missing last entry in committed range near %x\n", + PreviousLastEntry + )); + HeapDebugBreak( PreviousLastEntry ); + return NULL; + } + } + + + LastEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY; + UnCommittedRange->Address += *Size; + UnCommittedRange->Size -= *Size; + + HeapInternalTrace( Segment->Heap, (Segment->Heap->TraceBuffer, HEAP_TRACE_COMMIT_INSERT, 3, LastEntry, UnCommittedRange->Address, UnCommittedRange->Size) ); + + if (UnCommittedRange->Size == 0) { + if (UnCommittedRange->Address == (ULONG)Segment->LastValidEntry) { + FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY; + } + else { + FirstEntry->Flags = 0; + } + + *pp = UnCommittedRange->Next; + RtlpDestroyUnCommittedRange( Segment, UnCommittedRange ); + Segment->NumberOfUnCommittedRanges -= 1; + } + else { + FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY; + } + FirstEntry->SegmentIndex = LastEntry->SegmentIndex; + FirstEntry->Size = (USHORT)(*Size >> HEAP_GRANULARITY_SHIFT); + FirstEntry->PreviousSize = LastEntry->Size; + + HeapInternalTrace( Segment->Heap, (Segment->Heap->TraceBuffer, HEAP_TRACE_COMMIT_NEW_ENTRY, 3, FirstEntry, *(PULONG)FirstEntry, *((PULONG)FirstEntry+1)) ); + + if (!(FirstEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) { + (FirstEntry + FirstEntry->Size)->PreviousSize = FirstEntry->Size; + } + if (Segment->LargestUnCommittedRange == 0) { + UnCommittedRange = Segment->UnCommittedRanges; + while (UnCommittedRange != NULL) { + if (UnCommittedRange->Size >= Segment->LargestUnCommittedRange) { + Segment->LargestUnCommittedRange = UnCommittedRange->Size; + } + UnCommittedRange = UnCommittedRange->Next; + } + } + + return (PHEAP_FREE_ENTRY)FirstEntry; + } + else { + PreviousUnCommittedRange = UnCommittedRange; + pp = &UnCommittedRange->Next; + } + } + + return NULL; +} + + +BOOLEAN +RtlpInitializeHeapSegment( + IN PHEAP Heap, + IN PHEAP_SEGMENT Segment, + IN UCHAR SegmentIndex, + IN ULONG Flags, + IN PVOID BaseAddress, + IN PVOID UnCommittedAddress, + IN PVOID CommitLimitAddress + ) +{ + NTSTATUS Status; + PHEAP_ENTRY FirstEntry; + USHORT PreviousSize, Size; + ULONG NumberOfPages; + ULONG NumberOfCommittedPages; + ULONG NumberOfUnCommittedPages; + ULONG CommitSize; + + RTL_PAGED_CODE(); + + NumberOfPages = ((ULONG)CommitLimitAddress - (ULONG)BaseAddress) / PAGE_SIZE; + FirstEntry = (PHEAP_ENTRY)ROUND_UP_TO_POWER2( Segment + 1, + HEAP_GRANULARITY + ); + + if ((PVOID)Heap == BaseAddress) { + PreviousSize = Heap->Entry.Size; + } + else { + PreviousSize = 0; + } + + Size = (USHORT)(((ULONG)FirstEntry - (ULONG)Segment) >> HEAP_GRANULARITY_SHIFT); + + if ((PCHAR)(FirstEntry + 1) >= (PCHAR)UnCommittedAddress) { + if ((PCHAR)(FirstEntry + 1) >= (PCHAR)CommitLimitAddress) { + return FALSE; + } + + CommitSize = (PCHAR)(FirstEntry + 1) - (PCHAR)UnCommittedAddress; + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&UnCommittedAddress, + 0, + &CommitSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + return FALSE; + } + + UnCommittedAddress = (PVOID)((PCHAR)UnCommittedAddress + CommitSize); + } + + NumberOfUnCommittedPages = ((ULONG)CommitLimitAddress - (ULONG)UnCommittedAddress) / PAGE_SIZE; + NumberOfCommittedPages = NumberOfPages - NumberOfUnCommittedPages; + + Segment->Entry.PreviousSize = PreviousSize; + Segment->Entry.Size = Size; + Segment->Entry.Flags = HEAP_ENTRY_BUSY; + Segment->Entry.SegmentIndex = SegmentIndex; +#if i386 && !NTOS_KERNEL_RUNTIME + if (NtGlobalFlag & FLG_USER_STACK_TRACE_DB) { + Segment->AllocatorBackTraceIndex = (USHORT)RtlLogStackBackTrace(); + } +#endif // i386 && !NTOS_KERNEL_RUNTIME + Segment->Signature = HEAP_SEGMENT_SIGNATURE; + Segment->Flags = Flags; + Segment->Heap = Heap; + Segment->BaseAddress = BaseAddress; + Segment->FirstEntry = FirstEntry; + Segment->LastValidEntry = (PHEAP_ENTRY)((PCHAR)BaseAddress + (NumberOfPages * PAGE_SIZE)); + Segment->NumberOfPages = NumberOfPages; + Segment->NumberOfUnCommittedPages = NumberOfUnCommittedPages; + + if (NumberOfUnCommittedPages) { + RtlpInsertUnCommittedPages( Segment, + (ULONG)UnCommittedAddress, + NumberOfUnCommittedPages * PAGE_SIZE + ); + } + + Heap->Segments[ SegmentIndex ] = Segment; + + PreviousSize = Segment->Entry.Size; + FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY; + FirstEntry->PreviousSize = PreviousSize; + FirstEntry->SegmentIndex = SegmentIndex; + + RtlpInsertFreeBlock( Heap, + (PHEAP_FREE_ENTRY)FirstEntry, + (PHEAP_ENTRY)UnCommittedAddress - FirstEntry + ); + return TRUE; +} + + +NTSTATUS +RtlpDestroyHeapSegment( + IN PHEAP_SEGMENT Segment + ) +{ + PVOID BaseAddress; + ULONG BytesToFree; + + RTL_PAGED_CODE(); + + if (!(Segment->Flags & HEAP_SEGMENT_USER_ALLOCATED)) { + BaseAddress = Segment->BaseAddress; + BytesToFree = 0; + return ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&BaseAddress, + &BytesToFree, + MEM_RELEASE + ); + } + else { + return STATUS_SUCCESS; + } +} + + +PVOID +RtlCreateHeap( + IN ULONG Flags, + IN PVOID HeapBase OPTIONAL, + IN ULONG ReserveSize OPTIONAL, + IN ULONG CommitSize OPTIONAL, + IN PVOID Lock OPTIONAL, + IN PRTL_HEAP_PARAMETERS Parameters OPTIONAL + ) + +/*++ + +Routine Description: + + This routine initializes a heap. + +Arguments: + + Flags - Specifies optional attributes of the heap. + + Valid Flags Values: + + HEAP_NO_SERIALIZE - if set, then allocations and deallocations on + this heap are NOT synchronized by these routines. + + HEAP_GROWABLE - if set, then the heap is a "sparse" heap where + memory is committed only as necessary instead of + being preallocated. + + HeapBase - if not NULL, this specifies the base address for memory + to use as the heap. If NULL, memory is allocated by these routines. + + ReserveSize - if not zero, this specifies the amount of virtual address + space to reserve for the heap. + + CommitSize - if not zero, this specifies the amount of virtual address + space to commit for the heap. Must be less than ReserveSize. If + zero, then defaults to one page. + + Lock - if not NULL, this parameter points to the resource lock to + use. Only valid if HEAP_NO_SERIALIZE is NOT set. + + Parameters - optional heap parameters. + +Return Value: + + PVOID - a pointer to be used in accessing the created heap. + +--*/ + +{ + NTSTATUS Status; + PHEAP Heap = NULL; + PHEAP_SEGMENT Segment = NULL; + PLIST_ENTRY FreeListHead; + ULONG SizeOfHeapHeader; + ULONG SegmentFlags; + PVOID CommittedBase; + PVOID UnCommittedBase; + MEMORY_BASIC_INFORMATION MemoryInformation; + ULONG n; + ULONG InitialCountOfUnusedUnCommittedRanges; + ULONG MaximumHeapBlockSize; + PVOID NextHeapHeaderAddress; + PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp; + RTL_HEAP_PARAMETERS TempParameters; +#ifndef NTOS_KERNEL_RUNTIME + PPEB Peb; +#else + extern ULONG MmHeapSegmentReserve; + extern ULONG MmHeapSegmentCommit; + extern ULONG MmHeapDeCommitTotalFreeThreshold; + extern ULONG MmHeapDeCommitFreeBlockThreshold; +#endif // NTOS_KERNEL_RUNTIME + + RTL_PAGED_CODE(); + +#ifdef DEBUG_PAGE_HEAP + if ( RtlpDebugPageHeap && ( HeapBase == NULL ) && ( Lock == NULL )) { + return RtlpDebugPageHeapCreate( Flags, HeapBase, ReserveSize, CommitSize, Lock, Parameters ); + } + else { + Flags &= ~( HEAP_PROTECTION_ENABLED | HEAP_BREAK_WHEN_OUT_OF_VM | HEAP_NO_ALIGNMENT ); + } +#endif + + if (!(Flags & HEAP_SKIP_VALIDATION_CHECKS)) { + if (Flags & ~HEAP_CREATE_VALID_MASK) { + HeapDebugPrint(( "Invalid flags (%08x) specified to RtlCreateHeap\n", Flags )); + HeapDebugBreak( NULL ); + Flags &= HEAP_CREATE_VALID_MASK; + } + } + + MaximumHeapBlockSize = HEAP_MAXIMUM_BLOCK_SIZE << HEAP_GRANULARITY_SHIFT; + + Status = STATUS_SUCCESS; + RtlZeroMemory( &TempParameters, sizeof( TempParameters ) ); + if (ARGUMENT_PRESENT( Parameters )) { + try { + if (Parameters->Length == sizeof( *Parameters )) { + RtlMoveMemory( &TempParameters, Parameters, sizeof( *Parameters ) ); + } + } + except( EXCEPTION_EXECUTE_HANDLER ) { + Status = GetExceptionCode(); + } + + if (!NT_SUCCESS( Status )) { + return NULL; + } + } + Parameters = &TempParameters; + + if (NtGlobalFlag & FLG_HEAP_ENABLE_TAIL_CHECK) { + Flags |= HEAP_TAIL_CHECKING_ENABLED; + } + + if (NtGlobalFlag & FLG_HEAP_ENABLE_FREE_CHECK) { + Flags |= HEAP_FREE_CHECKING_ENABLED; + } + + if (NtGlobalFlag & FLG_HEAP_DISABLE_COALESCING) { + Flags |= HEAP_DISABLE_COALESCE_ON_FREE; + } + +#ifndef NTOS_KERNEL_RUNTIME + Peb = NtCurrentPeb(); + + if (NtGlobalFlag & FLG_HEAP_VALIDATE_PARAMETERS) { + Flags |= HEAP_VALIDATE_PARAMETERS_ENABLED; + } + + if (NtGlobalFlag & FLG_HEAP_VALIDATE_ALL) { + Flags |= HEAP_VALIDATE_ALL_ENABLED; + } + + if (NtGlobalFlag & FLG_HEAP_ENABLE_CALL_TRACING) { + Flags |= HEAP_CREATE_ENABLE_TRACING; + } + if (Parameters->SegmentReserve == 0) { + Parameters->SegmentReserve = Peb->HeapSegmentReserve; + } + + if (Parameters->SegmentCommit == 0) { + Parameters->SegmentCommit = Peb->HeapSegmentCommit; + } + + if (Parameters->DeCommitFreeBlockThreshold == 0) { + Parameters->DeCommitFreeBlockThreshold = Peb->HeapDeCommitFreeBlockThreshold; + } + + if (Parameters->DeCommitTotalFreeThreshold == 0) { + Parameters->DeCommitTotalFreeThreshold = Peb->HeapDeCommitTotalFreeThreshold; + } +#else + if (Parameters->SegmentReserve == 0) { + Parameters->SegmentReserve = MmHeapSegmentReserve; + } + + if (Parameters->SegmentCommit == 0) { + Parameters->SegmentCommit = MmHeapSegmentCommit; + } + + if (Parameters->DeCommitFreeBlockThreshold == 0) { + Parameters->DeCommitFreeBlockThreshold = MmHeapDeCommitFreeBlockThreshold; + } + + if (Parameters->DeCommitTotalFreeThreshold == 0) { + Parameters->DeCommitTotalFreeThreshold = MmHeapDeCommitTotalFreeThreshold; + } +#endif // NTOS_KERNEL_RUNTIME + + if (Parameters->MaximumAllocationSize == 0) { + Parameters->MaximumAllocationSize = ((ULONG)MM_HIGHEST_USER_ADDRESS - + (ULONG)MM_LOWEST_USER_ADDRESS - + PAGE_SIZE + ); + } + + if (Parameters->VirtualMemoryThreshold == 0 || + Parameters->VirtualMemoryThreshold > MaximumHeapBlockSize + ) { + Parameters->VirtualMemoryThreshold = MaximumHeapBlockSize; + } + + if (!ARGUMENT_PRESENT( CommitSize )) { + CommitSize = PAGE_SIZE; + + if (!ARGUMENT_PRESENT( ReserveSize )) { + ReserveSize = 64 * CommitSize; + } + } + else + if (!ARGUMENT_PRESENT( ReserveSize )) { + ReserveSize = ROUND_UP_TO_POWER2( CommitSize, 64 * 1024 ); + } + +#ifndef NTOS_KERNEL_RUNTIME + if (DEBUG_HEAP( Flags )) { + return RtlDebugCreateHeap( Flags, + HeapBase, + ReserveSize, + CommitSize, + Lock, + Parameters + ); + } +#endif // NTOS_KERNEL_RUNTIME + + SizeOfHeapHeader = sizeof( HEAP ); + if (!(Flags & HEAP_NO_SERIALIZE)) { + if (ARGUMENT_PRESENT( Lock )) { + Flags |= HEAP_LOCK_USER_ALLOCATED; + } + else { + SizeOfHeapHeader += sizeof( HEAP_LOCK ); + Lock = (PHEAP_LOCK)-1; + } + } + else + if (ARGUMENT_PRESENT( Lock )) { + return NULL; + } + + // + // See if caller allocate the space for the heap. + // + + if (ARGUMENT_PRESENT( HeapBase )) { + if (Parameters->CommitRoutine != NULL) { + if (Parameters->InitialCommit == 0 || + Parameters->InitialReserve == 0 || + Parameters->InitialCommit > Parameters->InitialReserve || + Flags & HEAP_GROWABLE + ) { + return NULL; + } + CommittedBase = HeapBase; + UnCommittedBase = (PCHAR)CommittedBase + Parameters->InitialCommit; + ReserveSize = Parameters->InitialReserve; + RtlZeroMemory( CommittedBase, PAGE_SIZE ); + } + else { + Status = ZwQueryVirtualMemory( NtCurrentProcess(), + HeapBase, + MemoryBasicInformation, + &MemoryInformation, + sizeof( MemoryInformation ), + NULL + ); + if (!NT_SUCCESS( Status )) { + return NULL; + } + + if (MemoryInformation.BaseAddress != HeapBase) { + return NULL; + } + + if (MemoryInformation.State == MEM_FREE) { + return NULL; + } + + CommittedBase = MemoryInformation.BaseAddress; + if (MemoryInformation.State == MEM_COMMIT) { + RtlZeroMemory( CommittedBase, PAGE_SIZE ); + CommitSize = MemoryInformation.RegionSize; + UnCommittedBase = (PCHAR)CommittedBase + CommitSize; + Status = ZwQueryVirtualMemory( NtCurrentProcess(), + UnCommittedBase, + MemoryBasicInformation, + &MemoryInformation, + sizeof( MemoryInformation ), + NULL + ); + ReserveSize = CommitSize; + if (NT_SUCCESS( Status ) && + MemoryInformation.State == MEM_RESERVE + ) { + ReserveSize += MemoryInformation.RegionSize; + } + } + else { + CommitSize = PAGE_SIZE; + UnCommittedBase = CommittedBase; + } + } + + SegmentFlags = HEAP_SEGMENT_USER_ALLOCATED; + Heap = (PHEAP)HeapBase; + } + else { + if (Parameters->CommitRoutine != NULL) { + return NULL; + } + + // + // Reserve the amount of virtual address space requested. + // + + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&Heap, + 0, + &ReserveSize, + MEM_RESERVE, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + return NULL; + } + + SegmentFlags = 0; + + if (!ARGUMENT_PRESENT( CommitSize )) { + CommitSize = PAGE_SIZE; + } + + CommittedBase = Heap; + UnCommittedBase = Heap; + } + + if (CommittedBase == UnCommittedBase) { + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&CommittedBase, + 0, + &CommitSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (!NT_SUCCESS( Status )) { + if (!ARGUMENT_PRESENT(HeapBase)) { + // + // Return the reserved virtual address space. + // + ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&Heap, + &ReserveSize, + MEM_RELEASE ); + } + return NULL; + } + + UnCommittedBase = (PVOID)((PCHAR)UnCommittedBase + CommitSize); + } + + NextHeapHeaderAddress = Heap + 1; + UnCommittedRange = (PHEAP_UNCOMMMTTED_RANGE)ROUND_UP_TO_POWER2( NextHeapHeaderAddress, + sizeof( QUAD ) + ); + InitialCountOfUnusedUnCommittedRanges = 8; + SizeOfHeapHeader += InitialCountOfUnusedUnCommittedRanges * sizeof( *UnCommittedRange ); + pp = &Heap->UnusedUnCommittedRanges; + while (InitialCountOfUnusedUnCommittedRanges--) { + *pp = UnCommittedRange; + pp = &UnCommittedRange->Next; + UnCommittedRange += 1; + } + NextHeapHeaderAddress = UnCommittedRange; + *pp = NULL; + + if (IS_HEAP_TAGGING_ENABLED()) { + Heap->PseudoTagEntries = (PHEAP_PSEUDO_TAG_ENTRY)ROUND_UP_TO_POWER2( NextHeapHeaderAddress, + sizeof( QUAD ) + ); + SizeOfHeapHeader += HEAP_NUMBER_OF_PSEUDO_TAG * sizeof( HEAP_PSEUDO_TAG_ENTRY ); + NextHeapHeaderAddress = Heap->PseudoTagEntries + HEAP_NUMBER_OF_PSEUDO_TAG; + } + + SizeOfHeapHeader = ROUND_UP_TO_POWER2( SizeOfHeapHeader, + HEAP_GRANULARITY + ); + + Heap->Entry.Size = (USHORT)(SizeOfHeapHeader >> HEAP_GRANULARITY_SHIFT); + Heap->Entry.Flags = HEAP_ENTRY_BUSY; + + Heap->Signature = HEAP_SIGNATURE; + Heap->Flags = Flags; + Heap->ForceFlags = (Flags & (HEAP_NO_SERIALIZE | + HEAP_GENERATE_EXCEPTIONS | + HEAP_ZERO_MEMORY | + HEAP_REALLOC_IN_PLACE_ONLY | + HEAP_VALIDATE_PARAMETERS_ENABLED | + HEAP_VALIDATE_ALL_ENABLED | + HEAP_CREATE_ENABLE_TRACING | + HEAP_TAIL_CHECKING_ENABLED | + HEAP_CREATE_ALIGN_16 | + HEAP_FREE_CHECKING_ENABLED + ) + ); + Heap->EventLogMask = (0x00010000) << ((Flags & HEAP_CLASS_MASK) >> 12); + + Heap->FreeListsInUseTerminate = 0xFFFF; + Heap->HeaderValidateLength = (USHORT)((ULONG)NextHeapHeaderAddress - (ULONG)Heap); + Heap->HeaderValidateCopy = NULL; + + FreeListHead = &Heap->FreeLists[ 0 ]; + n = HEAP_MAXIMUM_FREELISTS; + while (n--) { + InitializeListHead( FreeListHead ); + FreeListHead++; + } + InitializeListHead( &Heap->VirtualAllocdBlocks ); + + // + // Initialize the cricital section that controls access to + // the free list. + // + + if (Lock == (PHEAP_LOCK)-1) { + Lock = (PHEAP_LOCK)NextHeapHeaderAddress; + Status = RtlInitializeLockRoutine( Lock ); + if (!NT_SUCCESS( Status )) { + return NULL; + } + + NextHeapHeaderAddress = (PHEAP_LOCK)Lock + 1; + } + Heap->LockVariable = Lock; + + if (!RtlpInitializeHeapSegment( Heap, + (PHEAP_SEGMENT) + ((PCHAR)Heap + SizeOfHeapHeader), + 0, + SegmentFlags, + CommittedBase, + UnCommittedBase, + (PCHAR)CommittedBase + ReserveSize + ) + ) { + return NULL; + } + + Heap->ProcessHeapsListIndex = 0; + Heap->SegmentReserve = Parameters->SegmentReserve; + Heap->SegmentCommit = Parameters->SegmentCommit; + Heap->DeCommitFreeBlockThreshold = Parameters->DeCommitFreeBlockThreshold >> HEAP_GRANULARITY_SHIFT; + Heap->DeCommitTotalFreeThreshold = Parameters->DeCommitTotalFreeThreshold >> HEAP_GRANULARITY_SHIFT; + Heap->MaximumAllocationSize = Parameters->MaximumAllocationSize; + Heap->VirtualMemoryThreshold = ROUND_UP_TO_POWER2( Parameters->VirtualMemoryThreshold, + HEAP_GRANULARITY + ) >> HEAP_GRANULARITY_SHIFT; + if (Flags & HEAP_CREATE_ALIGN_16) { + Heap->AlignRound = 15 + sizeof( HEAP_ENTRY ); + Heap->AlignMask = (ULONG)~15; + } + else { + Heap->AlignRound = 7 + sizeof( HEAP_ENTRY ); + Heap->AlignMask = (ULONG)~7; + } + + if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) { + Heap->AlignRound += CHECK_HEAP_TAIL_SIZE; + + } + Heap->CommitRoutine = Parameters->CommitRoutine; + +#if !defined(NTOS_KERNEL_RUNTIME) + RtlpAddHeapToProcessList( Heap ); +#endif // !defined(NTOS_KERNEL_RUNTIME) + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpCreateHeapEventId, + Heap->EventLogMask, + Flags, + Heap, + ReserveSize, + CommitSize + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + + return (PVOID)Heap; +} // RtlCreateHeap + + +PVOID +RtlDestroyHeap( + IN PVOID HeapHandle + ) +{ + PHEAP Heap = (PHEAP)HeapHandle; + PHEAP_SEGMENT Segment; + PHEAP_UCR_SEGMENT UCRSegments; + PLIST_ENTRY Head, Next; + PVOID BaseAddress; + ULONG RegionSize; + UCHAR SegmentIndex; + + // + // Validate that HeapAddress points to a HEAP structure. + // + + RTL_PAGED_CODE(); + + IF_DEBUG_PAGE_HEAP_THEN_RETURN( + HeapHandle, + RtlpDebugPageHeapDestroy( HeapHandle ) + ); + + if (Heap == NULL) { + return NULL; + } + +#ifndef NTOS_KERNEL_RUNTIME + if (DEBUG_HEAP( Heap->Flags )) { + if (!RtlDebugDestroyHeap( HeapHandle )) { + return HeapHandle; + } + } + + if (HeapHandle == NtCurrentPeb()->ProcessHeap) { + return HeapHandle; + } +#endif // NTOS_KERNEL_RUNTIME + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpDestroyHeapEventId, + Heap->EventLogMask, + Heap + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + + Head = &Heap->VirtualAllocdBlocks; + Next = Head->Flink; + while (Head != Next) { + BaseAddress = CONTAINING_RECORD( Next, HEAP_VIRTUAL_ALLOC_ENTRY, Entry ); + Next = Next->Flink; + RegionSize = 0; + ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&BaseAddress, + &RegionSize, + MEM_RELEASE + ); + } + +#if !defined(NTOS_KERNEL_RUNTIME) + RtlpDestroyTags( Heap ); + RtlpRemoveHeapFromProcessList( Heap ); +#endif // !defined(NTOS_KERNEL_RUNTIME) + + // + // If the heap is serialized, delete the critical section created + // by RtlCreateHeap. + // + + if (!(Heap->Flags & HEAP_NO_SERIALIZE)) { + if (!(Heap->Flags & HEAP_LOCK_USER_ALLOCATED)) { + (VOID)RtlDeleteLockRoutine( Heap->LockVariable ); + } + + Heap->LockVariable = NULL; + } + + UCRSegments = Heap->UCRSegments; + Heap->UCRSegments = NULL; + while (UCRSegments) { + BaseAddress = UCRSegments; + UCRSegments = UCRSegments->Next; + RegionSize = 0; + ZwFreeVirtualMemory( NtCurrentProcess(), + &BaseAddress, + &RegionSize, + MEM_RELEASE + ); + } + + SegmentIndex = HEAP_MAXIMUM_SEGMENTS; + while (SegmentIndex--) { + Segment = Heap->Segments[ SegmentIndex ]; + if (Segment) { + RtlpDestroyHeapSegment( Segment ); + } + } + + return NULL; +} // RtlDestroyHeap + + +PHEAP_FREE_ENTRY +RtlpExtendHeap( + IN PHEAP Heap, + IN ULONG AllocationSize + ) +{ + NTSTATUS Status; + PHEAP_SEGMENT Segment; + PHEAP_FREE_ENTRY FreeBlock; + UCHAR SegmentIndex, EmptySegmentIndex; + ULONG NumberOfPages; + ULONG CommitSize; + ULONG ReserveSize; + ULONG FreeSize; + + RTL_PAGED_CODE(); + + NumberOfPages = ((AllocationSize + PAGE_SIZE - 1) / PAGE_SIZE); + FreeSize = NumberOfPages * PAGE_SIZE; + + HeapInternalTrace( Heap, (Heap->TraceBuffer, HEAP_TRACE_EXTEND_HEAP, 3, AllocationSize, NumberOfPages, FreeSize) ); + + EmptySegmentIndex = HEAP_MAXIMUM_SEGMENTS; + for (SegmentIndex=0; SegmentIndex<HEAP_MAXIMUM_SEGMENTS; SegmentIndex++) { + Segment = Heap->Segments[ SegmentIndex ]; + if (Segment && + NumberOfPages <= Segment->NumberOfUnCommittedPages && + FreeSize <= Segment->LargestUnCommittedRange + ) { + FreeBlock = RtlpFindAndCommitPages( Heap, + Segment, + &FreeSize, + NULL + ); + if (FreeBlock != NULL) { + FreeSize = FreeSize >> HEAP_GRANULARITY_SHIFT; + FreeBlock = RtlpCoalesceFreeBlocks( Heap, FreeBlock, &FreeSize, FALSE ); + RtlpInsertFreeBlock( Heap, FreeBlock, FreeSize ); + return FreeBlock; + } + } + else + if (Segment == NULL && EmptySegmentIndex == HEAP_MAXIMUM_SEGMENTS) { + EmptySegmentIndex = SegmentIndex; + } + } + + if (EmptySegmentIndex != HEAP_MAXIMUM_SEGMENTS && + Heap->Flags & HEAP_GROWABLE + ) { + Segment = NULL; + if ((AllocationSize + PAGE_SIZE) > Heap->SegmentReserve) { + ReserveSize = AllocationSize + PAGE_SIZE; + } + else { + ReserveSize = Heap->SegmentReserve; + } + + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&Segment, + 0, + &ReserveSize, + MEM_RESERVE, + PAGE_READWRITE + ); + if (NT_SUCCESS( Status )) { + Heap->SegmentReserve += ReserveSize; + if ((AllocationSize + PAGE_SIZE) > Heap->SegmentCommit) { + CommitSize = AllocationSize + PAGE_SIZE; + } + else { + CommitSize = Heap->SegmentCommit; + } + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&Segment, + 0, + &CommitSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (NT_SUCCESS( Status ) && + !RtlpInitializeHeapSegment( Heap, + Segment, + EmptySegmentIndex, + 0, + Segment, + (PCHAR)Segment + CommitSize, + (PCHAR)Segment + ReserveSize + ) + ) { + Status = STATUS_NO_MEMORY; + } + + if (NT_SUCCESS(Status)) { + return (PHEAP_FREE_ENTRY)Segment->FirstEntry; + } + + ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&Segment, + &ReserveSize, + MEM_RELEASE + ); + } + } + +#if !defined(NTOS_KERNEL_RUNTIME) + if (Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE) { + FreeBlock = RtlpCoalesceHeap( Heap ); + if ((FreeBlock != NULL) && (FreeBlock->Size >= AllocationSize)) { + return(FreeBlock); + } + } +#endif + return NULL; +} + + +PHEAP_FREE_ENTRY +RtlpCoalesceFreeBlocks( + IN PHEAP Heap, + IN PHEAP_FREE_ENTRY FreeBlock, + IN OUT PULONG FreeSize, + IN BOOLEAN RemoveFromFreeList + ) +{ + PHEAP_FREE_ENTRY FreeBlock1, NextFreeBlock; + + RTL_PAGED_CODE(); + + FreeBlock1 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock - FreeBlock->PreviousSize); + if (FreeBlock1 != FreeBlock && + !(FreeBlock1->Flags & HEAP_ENTRY_BUSY) && + (*FreeSize + FreeBlock1->Size) <= HEAP_MAXIMUM_BLOCK_SIZE + ) { + HEAPASSERT(FreeBlock->PreviousSize == FreeBlock1->Size); + HeapInternalTrace( Heap, (Heap->TraceBuffer, HEAP_TRACE_COALESCE_FREE_BLOCKS, + 7, + FreeBlock1, *(PULONG)FreeBlock1, *((PULONG)FreeBlock1+1), + FreeBlock, *(PULONG)FreeBlock, *((PULONG)FreeBlock+1), + *FreeSize + FreeBlock1->Size + ) + ); + + if (RemoveFromFreeList) { + RtlpRemoveFreeBlock( Heap, FreeBlock ); + Heap->TotalFreeSize -= FreeBlock->Size; + RemoveFromFreeList = FALSE; + } + + RtlpRemoveFreeBlock( Heap, FreeBlock1 ); + FreeBlock1->Flags = FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY; + FreeBlock = FreeBlock1; + *FreeSize += FreeBlock1->Size; + Heap->TotalFreeSize -= FreeBlock1->Size; + FreeBlock->Size = (USHORT)*FreeSize; + if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + ((PHEAP_ENTRY)FreeBlock + *FreeSize)->PreviousSize = (USHORT)*FreeSize; + } + } + + if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + NextFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + *FreeSize); + if (!(NextFreeBlock->Flags & HEAP_ENTRY_BUSY) && + (*FreeSize + NextFreeBlock->Size) <= HEAP_MAXIMUM_BLOCK_SIZE + ) { + HEAPASSERT(*FreeSize == NextFreeBlock->PreviousSize); + HeapInternalTrace( Heap, (Heap->TraceBuffer, HEAP_TRACE_COALESCE_FREE_BLOCKS, + 7, + FreeBlock, *(PULONG)FreeBlock, *((PULONG)FreeBlock+1), + NextFreeBlock, *(PULONG)NextFreeBlock, *((PULONG)NextFreeBlock+1), + *FreeSize + NextFreeBlock->Size + ) + ); + if (RemoveFromFreeList) { + RtlpRemoveFreeBlock( Heap, FreeBlock ); + Heap->TotalFreeSize -= FreeBlock->Size; + RemoveFromFreeList = FALSE; + } + + FreeBlock->Flags = NextFreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY; + RtlpRemoveFreeBlock( Heap, NextFreeBlock ); + *FreeSize += NextFreeBlock->Size; + Heap->TotalFreeSize -= NextFreeBlock->Size; + FreeBlock->Size = (USHORT)*FreeSize; + if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + ((PHEAP_ENTRY)FreeBlock + *FreeSize)->PreviousSize = (USHORT)*FreeSize; + } + } + } + + return FreeBlock; +} + + +VOID +RtlpDeCommitFreeBlock( + IN PHEAP Heap, + IN PHEAP_FREE_ENTRY FreeBlock, + IN ULONG FreeSize + ) +{ + NTSTATUS Status; + ULONG DeCommitAddress, DeCommitSize; + USHORT LeadingFreeSize, TrailingFreeSize; + PHEAP_SEGMENT Segment; + PHEAP_FREE_ENTRY LeadingFreeBlock, TrailingFreeBlock; + PHEAP_ENTRY LeadingBusyBlock, TrailingBusyBlock; + + RTL_PAGED_CODE(); + + if (Heap->CommitRoutine != NULL) { + RtlpInsertFreeBlock( Heap, FreeBlock, FreeSize ); + return; + } + + Segment = Heap->Segments[ FreeBlock->SegmentIndex ]; + + LeadingBusyBlock = NULL; + LeadingFreeBlock = FreeBlock; + DeCommitAddress = ROUND_UP_TO_POWER2( LeadingFreeBlock, PAGE_SIZE ); + LeadingFreeSize = (USHORT)((PHEAP_ENTRY)DeCommitAddress - (PHEAP_ENTRY)LeadingFreeBlock); + if (LeadingFreeSize == 1) { + DeCommitAddress += PAGE_SIZE; + LeadingFreeSize += PAGE_SIZE >> HEAP_GRANULARITY_SHIFT; + } + else + if (LeadingFreeBlock->PreviousSize != 0) { + if (DeCommitAddress == (ULONG)LeadingFreeBlock) { + LeadingBusyBlock = (PHEAP_ENTRY)LeadingFreeBlock - LeadingFreeBlock->PreviousSize; + } + } + + TrailingBusyBlock = NULL; + TrailingFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + FreeSize); + DeCommitSize = ROUND_DOWN_TO_POWER2( (ULONG)TrailingFreeBlock, PAGE_SIZE ); + TrailingFreeSize = (PHEAP_ENTRY)TrailingFreeBlock - (PHEAP_ENTRY)DeCommitSize; + if (TrailingFreeSize == (sizeof( HEAP_ENTRY ) >> HEAP_GRANULARITY_SHIFT)) { + DeCommitSize -= PAGE_SIZE; + TrailingFreeSize += PAGE_SIZE >> HEAP_GRANULARITY_SHIFT; + } + else + if (TrailingFreeSize == 0 && !(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + TrailingBusyBlock = (PHEAP_ENTRY)TrailingFreeBlock; + } + + TrailingFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)TrailingFreeBlock - TrailingFreeSize); + if (DeCommitSize > DeCommitAddress) { + DeCommitSize -= DeCommitAddress; + } + else { + DeCommitSize = 0; + } + + if (DeCommitSize != 0) { + Status = ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&DeCommitAddress, + &DeCommitSize, + MEM_DECOMMIT + ); + if (NT_SUCCESS( Status )) { + RtlpInsertUnCommittedPages( Segment, + DeCommitAddress, + DeCommitSize + ); + Segment->NumberOfUnCommittedPages += DeCommitSize / PAGE_SIZE; + + if (LeadingFreeSize != 0) { + LeadingFreeBlock->Flags = HEAP_ENTRY_LAST_ENTRY; + LeadingFreeBlock->Size = LeadingFreeSize; + Heap->TotalFreeSize += LeadingFreeSize; + RtlpInsertFreeBlockDirect( Heap, LeadingFreeBlock, LeadingFreeSize ); + } + else + if (LeadingBusyBlock != NULL) { + LeadingBusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY; + } + + if (TrailingFreeSize != 0) { + TrailingFreeBlock->PreviousSize = 0; + TrailingFreeBlock->SegmentIndex = Segment->Entry.SegmentIndex; + TrailingFreeBlock->Flags = 0; + TrailingFreeBlock->Size = TrailingFreeSize; + ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)TrailingFreeBlock + TrailingFreeSize))->PreviousSize = (USHORT)TrailingFreeSize; + RtlpInsertFreeBlockDirect( Heap, TrailingFreeBlock, TrailingFreeSize ); + Heap->TotalFreeSize += TrailingFreeSize; + } + else + if (TrailingBusyBlock != NULL) { + TrailingBusyBlock->PreviousSize = 0; + } + } + else { + RtlpInsertFreeBlock( Heap, LeadingFreeBlock, FreeSize ); + } + } + else { + RtlpInsertFreeBlock( Heap, LeadingFreeBlock, FreeSize ); + } + + return; +} + + +VOID +RtlpInsertFreeBlock( + IN PHEAP Heap, + IN PHEAP_FREE_ENTRY FreeBlock, + IN ULONG FreeSize + ) +{ + USHORT PreviousSize, Size; + UCHAR Flags; + UCHAR SegmentIndex; + PHEAP_SEGMENT Segment; + + RTL_PAGED_CODE(); + + PreviousSize = FreeBlock->PreviousSize; + SegmentIndex = FreeBlock->SegmentIndex; + Segment = Heap->Segments[ SegmentIndex ]; + Flags = FreeBlock->Flags; + Heap->TotalFreeSize += FreeSize; + + while (FreeSize != 0) { + if (FreeSize > (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) { + Size = HEAP_MAXIMUM_BLOCK_SIZE; + if (FreeSize == (ULONG)HEAP_MAXIMUM_BLOCK_SIZE + 1) { + Size -= 16; + } + + FreeBlock->Flags = 0; + } + else { + Size = (USHORT)FreeSize; + FreeBlock->Flags = Flags; + } + + FreeBlock->PreviousSize = PreviousSize; + FreeBlock->SegmentIndex = SegmentIndex; + FreeBlock->Size = Size; + RtlpInsertFreeBlockDirect( Heap, FreeBlock, Size ); + PreviousSize = Size; + FreeSize -= Size; + FreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + Size); + if ((PHEAP_ENTRY)FreeBlock >= Segment->LastValidEntry) { + return; + } + } + + if (!(Flags & HEAP_ENTRY_LAST_ENTRY)) { + FreeBlock->PreviousSize = PreviousSize; + } + return; +} + + +#define RtlFindFirstSetRightMember(Set) \ + (((Set) & 0xFFFF) ? \ + (((Set) & 0xFF) ? \ + RtlpBitsClearLow[(Set) & 0xFF] : \ + RtlpBitsClearLow[((Set) >> 8) & 0xFF] + 8) : \ + ((((Set) >> 16) & 0xFF) ? \ + RtlpBitsClearLow[ ((Set) >> 16) & 0xFF] + 16 : \ + RtlpBitsClearLow[ (Set) >> 24] + 24) \ + ) + +PVOID +RtlAllocateHeap( + IN PVOID HeapHandle, + IN ULONG Flags, + IN ULONG Size + ) +{ + PHEAP Heap = (PHEAP)HeapHandle; + PULONG FreeListsInUse; + ULONG FreeListsInUseUlong; + ULONG AllocationSize; + ULONG FreeSize, AllocationIndex; + PLIST_ENTRY FreeListHead, Next; + PHEAP_ENTRY BusyBlock; + PHEAP_FREE_ENTRY FreeBlock, SplitBlock, SplitBlock2; + ULONG InUseIndex; + UCHAR FreeFlags; + NTSTATUS Status; + EXCEPTION_RECORD ExceptionRecord; + PVOID ReturnValue; + + RTL_PAGED_CODE(); + + Flags |= Heap->ForceFlags; + + // + // Check for special features that force us to call the slow, do-everything + // version. + // + + if (( ! ( Flags & HEAP_SLOW_FLAGS )) && ( Size < 0x80000000 )) { + + // + // Round the requested size up to the allocation granularity. Note + // that if the request is for 0 bytes, we still allocate memory, because + // we add in an extra 1 byte to protect ourselves from idiots. + // + + AllocationSize = ((Size ? Size : 1) + 7 + sizeof( HEAP_ENTRY )) & (ULONG)~7; + AllocationIndex = AllocationSize >> HEAP_GRANULARITY_SHIFT; + + if (!(Flags & HEAP_NO_SERIALIZE)) { + + // + // Lock the free list. + // + RtlAcquireLockRoutine( Heap->LockVariable ); + } + + if (AllocationIndex < HEAP_MAXIMUM_FREELISTS) { + FreeListHead = &Heap->FreeLists[ AllocationIndex ]; + if ( !IsListEmpty( FreeListHead )) { + FreeBlock = CONTAINING_RECORD( FreeListHead->Blink, + HEAP_FREE_ENTRY, + FreeList ); + FreeFlags = FreeBlock->Flags; + RtlpFastRemoveDedicatedFreeBlock( Heap, FreeBlock ); + Heap->TotalFreeSize -= AllocationIndex; + BusyBlock = (PHEAP_ENTRY)FreeBlock; + BusyBlock->Flags = HEAP_ENTRY_BUSY | (FreeFlags & HEAP_ENTRY_LAST_ENTRY); + BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size); + BusyBlock->SmallTagIndex = 0; + } else { + + // + // Scan the free list in use vector to find the smallest + // available free block large enough for our allocations. + // + + // + // Compute the index of the ULONG where the scan should begin + // + InUseIndex = AllocationIndex >> 5; + FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex]; + + // + // Mask off the bits in the first ULONG that represent allocations + // smaller than we need. + // + FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << (AllocationIndex & 0x1f)) - 1); + + // + // Begin unrolled loop to scan bit vector. + // + switch (InUseIndex) { + case 0: + if (FreeListsInUseUlong) { + FreeListHead = &Heap->FreeLists[0]; + break; + } + FreeListsInUseUlong = *FreeListsInUse++; + + // deliberate fallthrough to next ULONG + + case 1: + if (FreeListsInUseUlong) { + FreeListHead = &Heap->FreeLists[32]; + break; + } + FreeListsInUseUlong = *FreeListsInUse++; + + // deliberate fallthrough to next ULONG + + case 2: + if (FreeListsInUseUlong) { + FreeListHead = &Heap->FreeLists[64]; + break; + } + FreeListsInUseUlong = *FreeListsInUse++; + + // deliberate fallthrough to next ULONG + + case 3: + if (FreeListsInUseUlong) { + FreeListHead = &Heap->FreeLists[96]; + break; + } + + // deliberate fallthrough to non dedicated list + + default: + + // + // No suitable entry on the free list was found. + // + goto LookInNonDedicatedList; + } + + // + // A free list has been found with a large enough allocation. FreeListHead + // contains the base of the vector it was found in. FreeListsInUseUlong + // contains the vector. + // + FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong ); + + FreeBlock = CONTAINING_RECORD( FreeListHead->Blink, + HEAP_FREE_ENTRY, + FreeList ); + RtlpFastRemoveDedicatedFreeBlock( Heap, FreeBlock ); +SplitFreeBlock: + FreeFlags = FreeBlock->Flags; + Heap->TotalFreeSize -= FreeBlock->Size; + + BusyBlock = (PHEAP_ENTRY)FreeBlock; + BusyBlock->Flags = HEAP_ENTRY_BUSY; + FreeSize = BusyBlock->Size - AllocationIndex; + BusyBlock->Size = (USHORT)AllocationIndex; + BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size); + BusyBlock->SmallTagIndex = 0; + + if (FreeSize != 0) { + if (FreeSize == 1) { + BusyBlock->Size += 1; + BusyBlock->UnusedBytes += sizeof( HEAP_ENTRY ); + } else { + SplitBlock = (PHEAP_FREE_ENTRY)(BusyBlock + AllocationIndex); + SplitBlock->Flags = FreeFlags; + SplitBlock->PreviousSize = (USHORT)AllocationIndex; + SplitBlock->SegmentIndex = BusyBlock->SegmentIndex; + SplitBlock->Size = (USHORT)FreeSize; + if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) { + RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize); + Heap->TotalFreeSize += FreeSize; + } else { + SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize); + if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) { + SplitBlock2->PreviousSize = (USHORT)FreeSize; + RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + } else { + SplitBlock->Flags = SplitBlock2->Flags; + RtlpFastRemoveFreeBlock( Heap, SplitBlock2 ); + Heap->TotalFreeSize -= SplitBlock2->Size; + FreeSize += SplitBlock2->Size; + if (FreeSize <= HEAP_MAXIMUM_BLOCK_SIZE) { + SplitBlock->Size = (USHORT)FreeSize; + if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize; + } + RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + } else { + RtlpInsertFreeBlock( Heap, SplitBlock, FreeSize ); + } + } + } + FreeFlags = 0; + } + } + if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) { + BusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY; + } + } + + if (!(Flags & HEAP_NO_SERIALIZE)) { + // + // Unlock the free list. + // + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + // + // Return the address of the user portion of the allocated block. + // This is the byte following the header. + // + ReturnValue = BusyBlock + 1; + + if (Flags & HEAP_ZERO_MEMORY) { + RtlZeroMemory( ReturnValue, Size ); + } + + return(ReturnValue); + } else if (AllocationIndex <= Heap->VirtualMemoryThreshold) { + +LookInNonDedicatedList: + FreeListHead = &Heap->FreeLists[0]; + Next = FreeListHead->Flink; + while (FreeListHead != Next) { + FreeBlock = CONTAINING_RECORD( Next, HEAP_FREE_ENTRY, FreeList ); + if (FreeBlock->Size >= AllocationIndex) { + RtlpFastRemoveNonDedicatedFreeBlock( Heap, FreeBlock ); + goto SplitFreeBlock; + } + Next = Next->Flink; + } + + FreeBlock = RtlpExtendHeap( Heap, AllocationSize ); + if (FreeBlock != NULL) { + RtlpFastRemoveNonDedicatedFreeBlock( Heap, FreeBlock ); + goto SplitFreeBlock; + } + Status = STATUS_NO_MEMORY; + + } else if (Heap->Flags & HEAP_GROWABLE) { + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + VirtualAllocBlock = NULL; + AllocationSize += FIELD_OFFSET( HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&VirtualAllocBlock, + 0, + &AllocationSize, + MEM_COMMIT, + PAGE_READWRITE ); + if (NT_SUCCESS(Status)) { + // + // Just committed, already zero. + // + VirtualAllocBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size); + VirtualAllocBlock->BusyBlock.Flags = HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT | HEAP_ENTRY_BUSY; + VirtualAllocBlock->CommitSize = AllocationSize; + VirtualAllocBlock->ReserveSize = AllocationSize; + InsertTailList( &Heap->VirtualAllocdBlocks, (PLIST_ENTRY)VirtualAllocBlock ); + + if (!(Flags & HEAP_NO_SERIALIZE)) { + // + // Unlock the free list. + // + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + // + // Return the address of the user portion of the allocated block. + // This is the byte following the header. + // + return (PHEAP_ENTRY)(VirtualAllocBlock + 1); + } + } else { + Status = STATUS_BUFFER_TOO_SMALL; + } + + // + // This is the error return. + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + // + // Unlock the free list. + // + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + if (Flags & HEAP_GENERATE_EXCEPTIONS) { + // + // Construct an exception record. + // + ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; + ExceptionRecord.ExceptionRecord = (PEXCEPTION_RECORD)NULL; + ExceptionRecord.NumberParameters = 1; + ExceptionRecord.ExceptionFlags = 0; + ExceptionRecord.ExceptionInformation[ 0 ] = AllocationSize; + RtlRaiseException( &ExceptionRecord ); + } + + SET_LAST_STATUS(Status); + return(NULL); + } else { + return(RtlAllocateHeapSlowly(HeapHandle, Flags, Size)); + } +} + +PVOID +RtlAllocateHeapSlowly( + IN PVOID HeapHandle, + IN ULONG Flags, + IN ULONG Size + ) +{ + PHEAP Heap = (PHEAP)HeapHandle; + BOOLEAN LockAcquired; + PVOID ReturnValue=NULL; + PULONG FreeListsInUse; + ULONG FreeListsInUseUlong; + ULONG AllocationSize; + ULONG FreeSize, AllocationIndex; + UCHAR EntryFlags, FreeFlags; + PLIST_ENTRY FreeListHead, Next; + PHEAP_ENTRY BusyBlock; + PHEAP_FREE_ENTRY FreeBlock, SplitBlock, SplitBlock2; + PHEAP_ENTRY_EXTRA ExtraStuff; + NTSTATUS Status; + EXCEPTION_RECORD ExceptionRecord; + ULONG ZeroSize = 0; + + RTL_PAGED_CODE(); + + // + // Note that Flags has already been OR'd with Heap->ForceFlags. + // + +#ifndef NTOS_KERNEL_RUNTIME + if (DEBUG_HEAP( Flags )) { + return RtlDebugAllocateHeap( HeapHandle, Flags, Size ); + } +#endif // NTOS_KERNEL_RUNTIME + + if (Size > 0x7fffffff) { + SET_LAST_STATUS( STATUS_NO_MEMORY ); + return NULL; + } + + AllocationSize = ((Size ? Size : 1) + Heap->AlignRound) & Heap->AlignMask; + EntryFlags = (UCHAR)(HEAP_ENTRY_BUSY | ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4)); + if (Flags & HEAP_NEED_EXTRA_FLAGS || Heap->PseudoTagEntries != NULL) { + EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT; + AllocationSize += sizeof( HEAP_ENTRY_EXTRA ); + } + AllocationIndex = AllocationSize >> HEAP_GRANULARITY_SHIFT; + + // + // Lock the free list. + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlAcquireLockRoutine( Heap->LockVariable ); + LockAcquired = TRUE; + } + else { + LockAcquired = FALSE; + } + + + try { + if (AllocationIndex < HEAP_MAXIMUM_FREELISTS) { + FreeListHead = &Heap->FreeLists[ AllocationIndex ]; + if ( !IsListEmpty( FreeListHead )) { + FreeBlock = CONTAINING_RECORD( FreeListHead->Flink, + HEAP_FREE_ENTRY, + FreeList + ); + FreeFlags = FreeBlock->Flags; + RtlpRemoveFreeBlock( Heap, FreeBlock ); + Heap->TotalFreeSize -= AllocationIndex; + BusyBlock = (PHEAP_ENTRY)FreeBlock; + BusyBlock->Flags = EntryFlags | (FreeFlags & HEAP_ENTRY_LAST_ENTRY); + BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size); + } + else { + if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 1) / 4) { + FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 0 ]; + FreeListsInUseUlong = *FreeListsInUse++ >> (AllocationIndex & 0x1F); + if (FreeListsInUseUlong) { + FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 2) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 3) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + goto LookInNonDedicatedList; + } + } + } + } + } + else + if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 2) / 4) { + FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 1 ]; + FreeListsInUseUlong = *FreeListsInUse++ >> (AllocationIndex & 0x1F); + if (FreeListsInUseUlong) { + FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 2) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + goto LookInNonDedicatedList; + } + } + } + } + else + if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 3) / 4) { + FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 2 ]; + FreeListsInUseUlong = *FreeListsInUse++ >> (AllocationIndex & 0x1F); + if (FreeListsInUseUlong) { + FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + FreeListsInUseUlong = *FreeListsInUse++; + if (FreeListsInUseUlong) { + FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) - + (AllocationIndex & 0x1F) + + RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + goto LookInNonDedicatedList; + } + } + } + else { + FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 3 ]; + FreeListsInUseUlong = *FreeListsInUse++ >> (AllocationIndex & 0x1F); + if (FreeListsInUseUlong) { + FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong ); + } + else { + goto LookInNonDedicatedList; + } + } + + FreeBlock = CONTAINING_RECORD( FreeListHead->Flink, + HEAP_FREE_ENTRY, + FreeList + ); +SplitFreeBlock: + FreeFlags = FreeBlock->Flags; + RtlpRemoveFreeBlock( Heap, FreeBlock ); + Heap->TotalFreeSize -= FreeBlock->Size; + + BusyBlock = (PHEAP_ENTRY)FreeBlock; + BusyBlock->Flags = EntryFlags; + FreeSize = BusyBlock->Size - AllocationIndex; + BusyBlock->Size = (USHORT)AllocationIndex; + BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size); + if (FreeSize != 0) { + if (FreeSize == 1) { + BusyBlock->Size += 1; + BusyBlock->UnusedBytes += sizeof( HEAP_ENTRY ); + } + else { + SplitBlock = (PHEAP_FREE_ENTRY)(BusyBlock + AllocationIndex); + SplitBlock->Flags = FreeFlags; + SplitBlock->PreviousSize = (USHORT)AllocationIndex; + SplitBlock->SegmentIndex = BusyBlock->SegmentIndex; + SplitBlock->Size = (USHORT)FreeSize; + if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) { + RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + } + else { + SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize); + if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) { + SplitBlock2->PreviousSize = (USHORT)FreeSize; + RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + } + else { + SplitBlock->Flags = SplitBlock2->Flags; + RtlpRemoveFreeBlock( Heap, SplitBlock2 ); + Heap->TotalFreeSize -= SplitBlock2->Size; + FreeSize += SplitBlock2->Size; + if (FreeSize <= HEAP_MAXIMUM_BLOCK_SIZE) { + SplitBlock->Size = (USHORT)FreeSize; + if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize; + } + RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + } + else { + RtlpInsertFreeBlock( Heap, SplitBlock, FreeSize ); + } + } + } + + FreeFlags = 0; + } + } + + if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) { + BusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY; + } + } + + ReturnValue = BusyBlock + 1; + if (Flags & HEAP_ZERO_MEMORY) { + ZeroSize = Size; + } + else + if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) { + RtlFillMemoryUlong( (PCHAR)(BusyBlock + 1), Size & ~0x3, ALLOC_HEAP_FILL ); + } + + if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) { + RtlFillMemory( (PCHAR)ReturnValue + Size, + CHECK_HEAP_TAIL_SIZE, + CHECK_HEAP_TAIL_FILL + ); + + BusyBlock->Flags |= HEAP_ENTRY_FILL_PATTERN; + } + + BusyBlock->SmallTagIndex = 0; + if (BusyBlock->Flags & HEAP_ENTRY_EXTRA_PRESENT) { + ExtraStuff = RtlpGetExtraStuffPointer( BusyBlock ); + ExtraStuff->ZeroInit = 0; +#ifndef NTOS_KERNEL_RUNTIME + if (IS_HEAP_TAGGING_ENABLED()) { + ExtraStuff->TagIndex = RtlpUpdateTagEntry( Heap, + (USHORT)((Flags & HEAP_TAG_MASK) >> HEAP_TAG_SHIFT), + 0, + BusyBlock->Size, + AllocationAction + ); + } + } + else + if (IS_HEAP_TAGGING_ENABLED()) { + BusyBlock->SmallTagIndex = (UCHAR)RtlpUpdateTagEntry( Heap, + (USHORT)((Flags & HEAP_SMALL_TAG_MASK) >> HEAP_TAG_SHIFT), + 0, + BusyBlock->Size, + AllocationAction + ); +#endif // NTOS_KERNEL_RUNTIME + } + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpAllocHeapEventId, + Heap->EventLogMask, + Heap, + Flags, + Size, + ReturnValue + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + + // + // Return the address of the user portion of the allocated block. + // This is the byte following the header. + // + + leave; + } + else + if (AllocationIndex <= Heap->VirtualMemoryThreshold) { +LookInNonDedicatedList: + FreeListHead = &Heap->FreeLists[ 0 ]; + Next = FreeListHead->Flink; + while (FreeListHead != Next) { + FreeBlock = CONTAINING_RECORD( Next, HEAP_FREE_ENTRY, FreeList ); + if (FreeBlock->Size >= AllocationIndex) { + goto SplitFreeBlock; + } + else { + Next = Next->Flink; + } + } + + FreeBlock = RtlpExtendHeap( Heap, AllocationSize ); + if (FreeBlock != NULL) { + goto SplitFreeBlock; + } + + Status = STATUS_NO_MEMORY; + } + else + if (Heap->Flags & HEAP_GROWABLE) { + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + VirtualAllocBlock = NULL; + AllocationSize += FIELD_OFFSET( HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + Status = ZwAllocateVirtualMemory( NtCurrentProcess(), + (PVOID *)&VirtualAllocBlock, + 0, + &AllocationSize, + MEM_COMMIT, + PAGE_READWRITE + ); + if (NT_SUCCESS( Status )) { + // + // Just committed, already zero. + // + VirtualAllocBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size); + VirtualAllocBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT; + VirtualAllocBlock->CommitSize = AllocationSize; + VirtualAllocBlock->ReserveSize = AllocationSize; +#ifndef NTOS_KERNEL_RUNTIME + if (IS_HEAP_TAGGING_ENABLED()) { + VirtualAllocBlock->ExtraStuff.TagIndex = + RtlpUpdateTagEntry( Heap, + (USHORT)((Flags & HEAP_SMALL_TAG_MASK) >> HEAP_TAG_SHIFT), + 0, + VirtualAllocBlock->CommitSize >> HEAP_GRANULARITY_SHIFT, + VirtualAllocationAction + ); + } +#endif // NTOS_KERNEL_RUNTIME + InsertTailList( &Heap->VirtualAllocdBlocks, (PLIST_ENTRY)VirtualAllocBlock ); + + // + // Return the address of the user portion of the allocated block. + // This is the byte following the header. + // + + ReturnValue = (PHEAP_ENTRY)(VirtualAllocBlock + 1); + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpAllocHeapEventId, + Heap->EventLogMask, + Heap, + Flags, + Size, + ReturnValue + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + + leave; + } + } + else { + Status = STATUS_BUFFER_TOO_SMALL; + } + + SET_LAST_STATUS( Status ); + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpAllocHeapEventId, + Heap->EventLogMask, + Heap, + Flags, + Size, + NULL + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + + // + // Release the free list lock if held + // + + if (LockAcquired) { + LockAcquired = FALSE; + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + if (Flags & HEAP_GENERATE_EXCEPTIONS) { + // + // Construct an exception record. + // + + ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; + ExceptionRecord.ExceptionRecord = (PEXCEPTION_RECORD)NULL; + ExceptionRecord.NumberParameters = 1; + ExceptionRecord.ExceptionFlags = 0; + ExceptionRecord.ExceptionInformation[ 0 ] = AllocationSize; + RtlRaiseException( &ExceptionRecord ); + } + } + except( GetExceptionCode() == STATUS_NO_MEMORY ? EXCEPTION_CONTINUE_SEARCH : + EXCEPTION_EXECUTE_HANDLER + ) { + SET_LAST_STATUS( GetExceptionCode() ); + } + + // + // Release the free list lock if held + // + + if (LockAcquired) { + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + if ( ZeroSize ) { + RtlZeroMemory( ReturnValue, ZeroSize ); + } + + return ReturnValue; +} + + +BOOLEAN +RtlFreeHeap( + IN PVOID HeapHandle, + IN ULONG Flags, + IN PVOID BaseAddress + ) +{ + NTSTATUS Status; + PHEAP Heap = (PHEAP)HeapHandle; + PHEAP_ENTRY BusyBlock; + PHEAP_ENTRY_EXTRA ExtraStuff; + ULONG FreeSize; + + RTL_PAGED_CODE(); + + if ( BaseAddress != NULL ) { + + Flags |= Heap->ForceFlags; + + if ( ! ( Flags & HEAP_SLOW_FLAGS )) { + + BusyBlock = (PHEAP_ENTRY)BaseAddress - 1; + + // + // Protect ourselves from idiots by refusing to free blocks + // that do not have the busy bit set. + // + // Also refuse to free blocks that are not eight-byte aligned. + // The specific idiot in this case is Office95, which likes + // to free a random pointer when you start Word95 from a desktop + // shortcut. + // + // As further insurance against idiots, check the segment index + // to make sure it is less than HEAP_MAXIMUM_SEGMENTS (16). This + // should fix all the dorks who have ASCII or Unicode where the + // heap header is supposed to be. + // + + if ((BusyBlock->Flags & HEAP_ENTRY_BUSY) && + (((ULONG)BaseAddress & 0x7) == 0) && + (BusyBlock->SegmentIndex < HEAP_MAXIMUM_SEGMENTS)) { + + // + // Lock the heap + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlAcquireLockRoutine( Heap->LockVariable ); + } + + if (!(BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)) { + FreeSize = BusyBlock->Size; +#ifdef NTOS_KERNEL_RUNTIME + BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap, + (PHEAP_FREE_ENTRY)BusyBlock, + &FreeSize, + FALSE ); +#else + if (!(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)) { + BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap, + (PHEAP_FREE_ENTRY)BusyBlock, + &FreeSize, + FALSE ); + } +#endif + // + // Check for a small allocation that can go on a freelist + // first, these should never trigger a decommit. + // + HEAPASSERT(HEAP_MAXIMUM_FREELISTS < Heap->DeCommitFreeBlockThreshold); + if (FreeSize < HEAP_MAXIMUM_FREELISTS) { + RtlpFastInsertDedicatedFreeBlockDirect( Heap, + (PHEAP_FREE_ENTRY)BusyBlock, + (USHORT)FreeSize ); + Heap->TotalFreeSize += FreeSize; + if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize); + } + } else if ((FreeSize < Heap->DeCommitFreeBlockThreshold) || + ((Heap->TotalFreeSize + FreeSize) < Heap->DeCommitTotalFreeThreshold)) { + if (FreeSize <= (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) { + RtlpFastInsertNonDedicatedFreeBlockDirect( Heap, + (PHEAP_FREE_ENTRY)BusyBlock, + (USHORT)FreeSize ); + if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize); + } + Heap->TotalFreeSize += FreeSize; + } else { + RtlpInsertFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize ); + } + + } else { + RtlpDeCommitFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize ); + } + + // + // Unlock the heap + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlReleaseLockRoutine( Heap->LockVariable ); + } + } else { + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + RemoveEntryList( &VirtualAllocBlock->Entry ); + + // + // Release lock here as there is no reason to hold it across + // the system call. + // + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + FreeSize = 0; + Status = ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&VirtualAllocBlock, + &FreeSize, + MEM_RELEASE + ); + if (!NT_SUCCESS( Status )) { + SET_LAST_STATUS( Status ); + return(FALSE); + } + } + + return(TRUE); + + } else { + + // + // Not a busy block, fail the call. + // + + SET_LAST_STATUS( STATUS_INVALID_PARAMETER ); + return(FALSE); + } + + } else { + + // + // Call the do-everything allocator. + // + + return(RtlFreeHeapSlowly(HeapHandle, Flags, BaseAddress)); + } + + } else { + + // + // BaseAddress is NULL, just return success + // + + return(TRUE); + } + +} // RtlFreeHeap + + +BOOLEAN +RtlFreeHeapSlowly( + IN PVOID HeapHandle, + IN ULONG Flags, + IN PVOID BaseAddress + ) +{ + NTSTATUS Status; + PHEAP Heap = (PHEAP)HeapHandle; + PHEAP_ENTRY BusyBlock; + PHEAP_ENTRY_EXTRA ExtraStuff; + ULONG FreeSize; + BOOLEAN Result, LockAcquired; +#ifndef NTOS_KERNEL_RUNTIME + USHORT TagIndex; +#endif // NTOS_KERNEL_RUNTIME + + RTL_PAGED_CODE(); + + // + // Note that Flags has already been OR'd with Heap->ForceFlags. + // + +#ifndef NTOS_KERNEL_RUNTIME + if (DEBUG_HEAP( Flags )) { + return RtlDebugFreeHeap( HeapHandle, Flags, BaseAddress ); + } +#endif // NTOS_KERNEL_RUNTIME + + Result = FALSE; + + // + // Lock the heap + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlAcquireLockRoutine( Heap->LockVariable ); + LockAcquired = TRUE; + } + else { + LockAcquired = FALSE; + } + + try { + + BusyBlock = (PHEAP_ENTRY)BaseAddress - 1; + + if ((BusyBlock->Flags & HEAP_ENTRY_BUSY) && + (((ULONG)BaseAddress & 0x7) == 0) && + (BusyBlock->SegmentIndex < HEAP_MAXIMUM_SEGMENTS)) { + + if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) { + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + RemoveEntryList( &VirtualAllocBlock->Entry ); + +#ifndef NTOS_KERNEL_RUNTIME + if (IS_HEAP_TAGGING_ENABLED()) { + RtlpUpdateTagEntry( Heap, + VirtualAllocBlock->ExtraStuff.TagIndex, + VirtualAllocBlock->CommitSize >> HEAP_GRANULARITY_SHIFT, + 0, + VirtualFreeAction + ); + } +#endif // NTOS_KERNEL_RUNTIME + + FreeSize = 0; + Status = ZwFreeVirtualMemory( NtCurrentProcess(), + (PVOID *)&VirtualAllocBlock, + &FreeSize, + MEM_RELEASE + ); + if (NT_SUCCESS( Status )) { + Result = TRUE; + } + else { + SET_LAST_STATUS( Status ); + } + } + else { +#ifndef NTOS_KERNEL_RUNTIME + if (IS_HEAP_TAGGING_ENABLED()) { + if (BusyBlock->Flags & HEAP_ENTRY_EXTRA_PRESENT) { + ExtraStuff = (PHEAP_ENTRY_EXTRA)(BusyBlock + BusyBlock->Size - 1); + TagIndex = RtlpUpdateTagEntry( Heap, + ExtraStuff->TagIndex, + BusyBlock->Size, + 0, + FreeAction + ); + } + else { + TagIndex = RtlpUpdateTagEntry( Heap, + BusyBlock->SmallTagIndex, + BusyBlock->Size, + 0, + FreeAction + ); + } + } + else { + TagIndex = 0; + } +#endif // NTOS_KERNEL_RUNTIME + + FreeSize = BusyBlock->Size; +#ifndef NTOS_KERNEL_RUNTIME + if (!(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)) { +#endif // NTOS_KERNEL_RUNTIME + BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap, (PHEAP_FREE_ENTRY)BusyBlock, &FreeSize, FALSE ); +#ifndef NTOS_KERNEL_RUNTIME + } +#endif // NTOS_KERNEL_RUNTIME + + if (FreeSize < Heap->DeCommitFreeBlockThreshold || + (Heap->TotalFreeSize + FreeSize) < Heap->DeCommitTotalFreeThreshold + ) { + if (FreeSize <= (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) { + RtlpInsertFreeBlockDirect( Heap, (PHEAP_FREE_ENTRY)BusyBlock, (USHORT)FreeSize ); + if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) { + HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize); + } + Heap->TotalFreeSize += FreeSize; + } + else { + RtlpInsertFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize ); + } + +#ifndef NTOS_KERNEL_RUNTIME + if (TagIndex != 0) { + PHEAP_FREE_ENTRY_EXTRA FreeExtra; + + BusyBlock->Flags |= HEAP_ENTRY_EXTRA_PRESENT; + FreeExtra = (PHEAP_FREE_ENTRY_EXTRA)(BusyBlock + BusyBlock->Size) - 1; + FreeExtra->TagIndex = TagIndex; + FreeExtra->FreeBackTraceIndex = 0; +#if i386 + if (NtGlobalFlag & FLG_USER_STACK_TRACE_DB) { + FreeExtra->FreeBackTraceIndex = (USHORT)RtlLogStackBackTrace(); + } +#endif // i386 + } +#endif // NTOS_KERNEL_RUNTIME + } + else { + RtlpDeCommitFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize ); + } + + Result = TRUE; + } + } + else { + + // + // Not a busy block, fail the call. + // + + SET_LAST_STATUS( STATUS_INVALID_PARAMETER ); + } + +#if ENABLE_HEAP_EVENT_LOGGING + if (RtlAreLogging( Heap->EventLogMask )) { + RtlLogEvent( RtlpFreeHeapEventId, + Heap->EventLogMask, + Heap, + Flags, + BaseAddress, + Result + ); + } +#endif // ENABLE_HEAP_EVENT_LOGGING + } + except( EXCEPTION_EXECUTE_HANDLER ) { + SET_LAST_STATUS( GetExceptionCode() ); + Result = FALSE; + } + // + // Unlock the heap + // + + if (LockAcquired) { + RtlReleaseLockRoutine( Heap->LockVariable ); + } + + return Result; +} // RtlFreeHeap + + + +PHEAP_ENTRY_EXTRA +RtlpGetExtraStuffPointer( + PHEAP_ENTRY BusyBlock + ) +{ + ULONG AllocationIndex; + + if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) { + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + return &VirtualAllocBlock->ExtraStuff; + } + else { + AllocationIndex = BusyBlock->Size; + return (PHEAP_ENTRY_EXTRA)(BusyBlock + AllocationIndex - 1); + } +} + + +ULONG +RtlpGetSizeOfBigBlock( + IN PHEAP_ENTRY BusyBlock + ) +{ + PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; + + RTL_PAGED_CODE(); + + VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock ); + return VirtualAllocBlock->CommitSize - BusyBlock->Size; +} + + +BOOLEAN +RtlpCheckBusyBlockTail( + IN PHEAP_ENTRY BusyBlock + ) +{ + PCHAR Tail; + ULONG Size, cbEqual; + + RTL_PAGED_CODE(); + + if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) { + Size = RtlpGetSizeOfBigBlock( BusyBlock ); + } + else { + Size = (BusyBlock->Size << HEAP_GRANULARITY_SHIFT) - BusyBlock->UnusedBytes; + } + + Tail = (PCHAR)(BusyBlock + 1) + Size; + cbEqual = RtlCompareMemory( Tail, + CheckHeapFillPattern, + CHECK_HEAP_TAIL_SIZE + ); + if (cbEqual != CHECK_HEAP_TAIL_SIZE) { + HeapDebugPrint(( "Heap block at %lx modified at %lx past requested size of %lx\n", + BusyBlock, + Tail + cbEqual, + Size + )); + HeapDebugBreak( BusyBlock ); + return FALSE; + } + else { + return TRUE; + } +} + + +NTSTATUS +RtlZeroHeap( + IN PVOID HeapHandle, + IN ULONG Flags + ) +{ + PHEAP Heap = (PHEAP)HeapHandle; + NTSTATUS Status; + BOOLEAN LockAcquired; + PHEAP_SEGMENT Segment; + ULONG SegmentIndex; + PHEAP_ENTRY CurrentBlock; + PHEAP_FREE_ENTRY FreeBlock; + ULONG Size; + PHEAP_UNCOMMMTTED_RANGE UnCommittedRange; + + RTL_PAGED_CODE(); + + Flags |= Heap->ForceFlags; + +#ifndef NTOS_KERNEL_RUNTIME + if (DEBUG_HEAP( Flags )) { + return RtlDebugZeroHeap( HeapHandle, Flags ); + } +#endif // NTOS_KERNEL_RUNTIME + + Status = STATUS_SUCCESS; + + // + // Lock the heap + // + + if (!(Flags & HEAP_NO_SERIALIZE)) { + RtlAcquireLockRoutine( Heap->LockVariable ); + LockAcquired = TRUE; + } + else { + LockAcquired = FALSE; + } + + try { try { + for (SegmentIndex=0; SegmentIndex<HEAP_MAXIMUM_SEGMENTS; SegmentIndex++) { + Segment = Heap->Segments[ SegmentIndex ]; + if (!Segment) { + continue; + } + + UnCommittedRange = Segment->UnCommittedRanges; + CurrentBlock = Segment->FirstEntry; + while (CurrentBlock < Segment->LastValidEntry) { + Size = CurrentBlock->Size << HEAP_GRANULARITY_SHIFT; + if (!(CurrentBlock->Flags & HEAP_ENTRY_BUSY)) { + FreeBlock = (PHEAP_FREE_ENTRY)CurrentBlock; + if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED && + CurrentBlock->Flags & HEAP_ENTRY_FILL_PATTERN + ) { + RtlFillMemoryUlong( FreeBlock + 1, + Size - sizeof( *FreeBlock ), + FREE_HEAP_FILL + ); + } + else { + RtlFillMemoryUlong( FreeBlock + 1, + Size - sizeof( *FreeBlock ), + 0 + ); + } + } + + if (CurrentBlock->Flags & HEAP_ENTRY_LAST_ENTRY) { + CurrentBlock += CurrentBlock->Size; + if (UnCommittedRange == NULL) { + CurrentBlock = Segment->LastValidEntry; + } + else { + CurrentBlock = (PHEAP_ENTRY) + ((PCHAR)UnCommittedRange->Address + UnCommittedRange->Size); + UnCommittedRange = UnCommittedRange->Next; + } + } + else { + CurrentBlock += CurrentBlock->Size; + } + } + } + } + except( EXCEPTION_EXECUTE_HANDLER ) { + Status = GetExceptionCode(); + } + } finally { + // + // Unlock the heap + // + + if (LockAcquired) { + RtlReleaseLockRoutine( Heap->LockVariable ); + } + } + + return Status; +} |