test: heap.c Source File

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# heap.c

Go to the documentation of this file.

    00001 /*++
    00002
    00003 Copyright (c) 1989  Microsoft Corporation
    00004
    00005 Module Name:
    00006
    00007     heap.c
    00008
    00009 Abstract:
    00010
    00011     This module implements a heap allocator.
    00012
    00013 Author:
    00014
    00015     Steve Wood (stevewo) 20-Sep-1989 (Adapted from URTL\alloc.c)
    00016
    00017 Revision History:
    00018
    00019 --*/
    00020
    00021 #include "ntrtlp.h"
    00022 #include "heap.h"
    00023 #include "heappriv.h"
    00024
    00025 #ifdef NTHEAP_ENABLED
    00026 #include "heapp.h"
    00027 #endif // NTHEAP_ENABLED
    00028
    00029 ULONG RtlpDisableHeapLookaside = 0;
    00030
    00031 //
    00032 //  If any of these flags are set, the fast allocator punts
    00033 //  to the slow do-everything allocator.
    00034 //
    00035
    00036 #define HEAP_SLOW_FLAGS (HEAP_DEBUG_FLAGS           | \
    00037                          HEAP_SETTABLE_USER_FLAGS   | \
    00038                          HEAP_NEED_EXTRA_FLAGS      | \
    00039                          HEAP_CREATE_ALIGN_16       | \
    00040                          HEAP_FREE_CHECKING_ENABLED | \
    00041                          HEAP_TAIL_CHECKING_ENABLED)
    00042
    00043 UCHAR CheckHeapFillPattern[ CHECK_HEAP_TAIL_SIZE ] = {
    00044     CHECK_HEAP_TAIL_FILL,
    00045     CHECK_HEAP_TAIL_FILL,
    00046     CHECK_HEAP_TAIL_FILL,
    00047     CHECK_HEAP_TAIL_FILL,
    00048     CHECK_HEAP_TAIL_FILL,
    00049     CHECK_HEAP_TAIL_FILL,
    00050     CHECK_HEAP_TAIL_FILL,
    00051 #ifdef _WIN64
    00052     CHECK_HEAP_TAIL_FILL,
    00053     CHECK_HEAP_TAIL_FILL,
    00054     CHECK_HEAP_TAIL_FILL,
    00055     CHECK_HEAP_TAIL_FILL,
    00056     CHECK_HEAP_TAIL_FILL,
    00057     CHECK_HEAP_TAIL_FILL,
    00058     CHECK_HEAP_TAIL_FILL,
    00059     CHECK_HEAP_TAIL_FILL,
    00060 #endif
    00061     CHECK_HEAP_TAIL_FILL
    00062 };
    00063
    00064 //
    00065 //  An extra bitmap manipulation routine
    00066 //
    00067
    00068 #define RtlFindFirstSetRightMember(Set)                     \
    00069     (((Set) & 0xFFFF) ?                                     \
    00070         (((Set) & 0xFF) ?                                   \
    00071             RtlpBitsClearLow[(Set) & 0xFF] :                \
    00072             RtlpBitsClearLow[((Set) >> 8) & 0xFF] + 8) :    \
    00073         ((((Set) >> 16) & 0xFF) ?                           \
    00074             RtlpBitsClearLow[ ((Set) >> 16) & 0xFF] + 16 :  \
    00075             RtlpBitsClearLow[ (Set) >> 24] + 24)            \
    00076     )
    00077
    00078
    00079 //
    00080 //  These are procedure prototypes exported by heapdbg.c
    00081 //
    00082
    00083 #ifndef NTOS_KERNEL_RUNTIME
    00084
    00085 PVOID
    00086 RtlDebugCreateHeap (
    00087     IN ULONG Flags,
    00088     IN PVOID HeapBase OPTIONAL,
    00089     IN SIZE_T ReserveSize OPTIONAL,
    00090     IN SIZE_T CommitSize OPTIONAL,
    00091     IN PVOID Lock OPTIONAL,
    00092     IN PRTL_HEAP_PARAMETERS Parameters OPTIONAL
    00093     );
    00094
    00095 BOOLEAN
    00096 RtlDebugDestroyHeap (
    00097     IN PVOID HeapHandle
    00098     );
    00099
    00100 PVOID
    00101 RtlDebugAllocateHeap (
    00102     IN PVOID HeapHandle,
    00103     IN ULONG Flags,
    00104     IN SIZE_T Size
    00105     );
    00106
    00107 BOOLEAN
    00108 RtlDebugFreeHeap (
    00109     IN PVOID HeapHandle,
    00110     IN ULONG Flags,
    00111     IN PVOID BaseAddress
    00112     );
    00113
    00114 ULONG
    00115 RtlDebugSizeHeap (
    00116     IN PVOID HeapHandle,
    00117     IN ULONG Flags,
    00118     IN PVOID BaseAddress
    00119     );
    00120
    00121 NTSTATUS
    00122 RtlDebugZeroHeap (
    00123     IN PVOID HeapHandle,
    00124     IN ULONG Flags
    00125     );
    00126
    00127 #endif // NTOS_KERNEL_RUNTIME
    00128
    00129
    00130 //
    00131 //  Local procedure prototypes
    00132 //
    00133
    00134 PHEAP_UNCOMMMTTED_RANGE
    00135 RtlpCreateUnCommittedRange (
    00136     IN PHEAP_SEGMENT Segment
    00137     );
    00138
    00139 VOID
    00140 RtlpDestroyUnCommittedRange (
    00141     IN PHEAP_SEGMENT Segment,
    00142     IN PHEAP_UNCOMMMTTED_RANGE UnCommittedRange
    00143     );
    00144
    00145 VOID
    00146 RtlpInsertUnCommittedPages (
    00147     IN PHEAP_SEGMENT Segment,
    00148     IN ULONG_PTR Address,
    00149     IN SIZE_T Size
    00150     );
    00151
    00152 NTSTATUS
    00153 RtlpDestroyHeapSegment (
    00154     IN PHEAP_SEGMENT Segment
    00155     );
    00156
    00157 PHEAP_FREE_ENTRY
    00158 RtlpExtendHeap (
    00159     IN PHEAP Heap,
    00160     IN SIZE_T AllocationSize
    00161     );
    00162
    00163 #ifdef ALLOC_PRAGMA
    00164
    00165 #pragma alloc_text(PAGE, RtlCreateHeap)
    00166 #pragma alloc_text(PAGE, RtlDestroyHeap)
    00167 #pragma alloc_text(PAGE, RtlAllocateHeap)
    00168 #pragma alloc_text(PAGE, RtlFreeHeap)
    00169 #pragma alloc_text(PAGE, RtlSizeHeap)
    00170 #pragma alloc_text(PAGE, RtlZeroHeap)
    00171
    00172 #pragma alloc_text(PAGE, RtlpCreateUnCommittedRange)
    00173 #pragma alloc_text(PAGE, RtlpDestroyUnCommittedRange)
    00174 #pragma alloc_text(PAGE, RtlpInsertUnCommittedPages)
    00175 #pragma alloc_text(PAGE, RtlpDestroyHeapSegment)
    00176 #pragma alloc_text(PAGE, RtlpExtendHeap)
    00177
    00178 #pragma alloc_text(PAGE, RtlpFindAndCommitPages)
    00179 #pragma alloc_text(PAGE, RtlpInitializeHeapSegment)
    00180 #pragma alloc_text(PAGE, RtlpCoalesceFreeBlocks)
    00181 #pragma alloc_text(PAGE, RtlpDeCommitFreeBlock)
    00182 #pragma alloc_text(PAGE, RtlpInsertFreeBlock)
    00183 #pragma alloc_text(PAGE, RtlpGetSizeOfBigBlock)
    00184 #pragma alloc_text(PAGE, RtlpCheckBusyBlockTail)
    00185
    00186 #endif // ALLOC_PRAGMA
    00187
    00188
    00189 PVOID
    00190
    00191 RtlCreateHeap (
    00192     IN ULONG Flags,
    00193     IN PVOID HeapBase OPTIONAL,
    00194     IN SIZE_T ReserveSize OPTIONAL,
    00195     IN SIZE_T CommitSize OPTIONAL,
    00196     IN PVOID Lock OPTIONAL,
    00197     IN PRTL_HEAP_PARAMETERS Parameters OPTIONAL
    00198     )
    00199
    00200 /*++
    00201
    00202 Routine Description:
    00203
    00204     This routine initializes a heap.
    00205
    00206 Arguments:
    00207
    00208     Flags - Specifies optional attributes of the heap.
    00209
    00210         Valid Flags Values:
    00211
    00212         HEAP_NO_SERIALIZE - if set, then allocations and deallocations on
    00213                          this heap are NOT synchronized by these routines.
    00214
    00215         HEAP_GROWABLE - if set, then the heap is a "sparse" heap where
    00216                         memory is committed only as necessary instead of
    00217                         being preallocated.
    00218
    00219     HeapBase - if not NULL, this specifies the base address for memory
    00220         to use as the heap.  If NULL, memory is allocated by these routines.
    00221
    00222     ReserveSize - if not zero, this specifies the amount of virtual address
    00223         space to reserve for the heap.
    00224
    00225     CommitSize - if not zero, this specifies the amount of virtual address
    00226         space to commit for the heap.  Must be less than ReserveSize.  If
    00227         zero, then defaults to one page.
    00228
    00229     Lock - if not NULL, this parameter points to the resource lock to
    00230         use.  Only valid if HEAP_NO_SERIALIZE is NOT set.
    00231
    00232     Parameters - optional heap parameters.
    00233
    00234 Return Value:
    00235
    00236     PVOID - a pointer to be used in accessing the created heap.
    00237
    00238 --*/
    00239
    00240 {
    00241     ULONG_PTR HighestUserAddress;
    00242     NTSTATUS Status;
    00243     PHEAP Heap = NULL;
    00244     PHEAP_SEGMENT Segment = NULL;
    00245     PLIST_ENTRY FreeListHead;
    00246     ULONG SizeOfHeapHeader;
    00247     ULONG SegmentFlags;
    00248     PVOID CommittedBase;
    00249     PVOID UnCommittedBase;
    00250     MEMORY_BASIC_INFORMATION MemoryInformation;
    00251     SYSTEM_BASIC_INFORMATION SystemInformation;
    00252     ULONG n;
    00253     ULONG InitialCountOfUnusedUnCommittedRanges;
    00254     SIZE_T MaximumHeapBlockSize;
    00255     PVOID NextHeapHeaderAddress;
    00256     PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp;
    00257     RTL_HEAP_PARAMETERS TempParameters;
    00258     ULONG NtGlobalFlag = RtlGetNtGlobalFlags();
    00259
    00260 #ifndef NTOS_KERNEL_RUNTIME
    00261
    00262     PPEB Peb;
    00263
    00264 #else // NTOS_KERNEL_RUNTIME
    00265
    00266     extern SIZE_T MmHeapSegmentReserve;
    00267     extern SIZE_T MmHeapSegmentCommit;
    00268     extern SIZE_T MmHeapDeCommitTotalFreeThreshold;
    00269     extern SIZE_T MmHeapDeCommitFreeBlockThreshold;
    00270
    00271 #endif // NTOS_KERNEL_RUNTIME
    00272
    00273     RTL_PAGED_CODE();
    00274
    00275 #ifndef NTOS_KERNEL_RUNTIME
    00276 #ifdef NTHEAP_ENABLED
    00277     {
    00278         if (Flags & NTHEAP_ENABLED_FLAG) {
    00279
    00280             Heap = RtlCreateNtHeap( Flags, NULL );
    00281
    00282             if (Heap != NULL) {
    00283
    00284                 return Heap;
    00285             }
    00286
    00287             Flags &= ~NTHEAP_ENABLED_FLAG;
    00288         }
    00289     }
    00290 #endif // NTHEAP_ENABLED
    00291 #endif // NTOS_KERNEL_RUNTIME
    00292
    00293     //
    00294     //  Check if we should be using the page heap code.  If not then turn
    00295     //  off any of the page heap flags before going on
    00296     //
    00297
    00298 #ifdef DEBUG_PAGE_HEAP
    00299
    00300     if ( RtlpDebugPageHeap && ( HeapBase == NULL ) && ( Lock == NULL )) {
    00301
    00302         PVOID PageHeap;
    00303
    00304         PageHeap = RtlpDebugPageHeapCreate(
    00305
    00306             Flags,
    00307             HeapBase,
    00308             ReserveSize,
    00309             CommitSize,
    00310             Lock,
    00311             Parameters );
    00312
    00313         if (PageHeap != NULL) {
    00314             return PageHeap;
    00315         }
    00316
    00317         //
    00318         // A `-1' value signals a recursive call from page heap
    00319         // manager. We set this to null and continue creating
    00320         // a normal heap. This small hack is required so that we
    00321         // minimize the dependencies between the normal and the page
    00322         // heap manager.
    00323         //
    00324
    00325         if ((SIZE_T)Parameters == (SIZE_T)-1) {
    00326
    00327             Parameters = NULL;
    00328         }
    00329     }
    00330
    00331     Flags &= ~( HEAP_PROTECTION_ENABLED |
    00332         HEAP_BREAK_WHEN_OUT_OF_VM |
    00333         HEAP_NO_ALIGNMENT );
    00334
    00335 #endif // DEBUG_PAGE_HEAP
    00336
    00337     //
    00338     //  If the caller does not want to skip heap validiation checks then we
    00339     //  need to validate the rest of the flags but simply masking out only
    00340     //  those flags that want on a create heap call
    00341     //
    00342
    00343     if (!(Flags & HEAP_SKIP_VALIDATION_CHECKS)) {
    00344
    00345         if (Flags & ~HEAP_CREATE_VALID_MASK) {
    00346
    00347             HeapDebugPrint(( "Invalid flags (%08x) specified to RtlCreateHeap\n", Flags ));
    00348             HeapDebugBreak( NULL );
    00349
    00350             Flags &= HEAP_CREATE_VALID_MASK;
    00351         }
    00352     }
    00353
    00354     //
    00355     //  The maximum heap block size is really 0x7f000 which is 0x80000 minus a
    00356     //  page.  Maximum block size is 0xfe00 and granularity shift is 3.
    00357     //
    00358
    00359     MaximumHeapBlockSize = HEAP_MAXIMUM_BLOCK_SIZE << HEAP_GRANULARITY_SHIFT;
    00360
    00361     //
    00362     //  Assume we're going to be successful until we're shown otherwise
    00363     //
    00364
    00365     Status = STATUS_SUCCESS;
    00366
    00367     //
    00368     //  This part of the routine builds up local variable containing all the
    00369     //  parameters used to initialize the heap.  First thing we do is zero
    00370     //  it out.
    00371     //
    00372
    00373     RtlZeroMemory( &TempParameters, sizeof( TempParameters ) );
    00374
    00375     //
    00376     //  If our caller supplied the optional heap parameters then we'll
    00377     //  make sure the size is good and copy over them over to our
    00378     //  local copy
    00379     //
    00380
    00381     if (ARGUMENT_PRESENT( Parameters )) {
    00382
    00383         try {
    00384
    00385             if (Parameters->Length == sizeof( *Parameters )) {
    00386
    00387                 RtlMoveMemory( &TempParameters, Parameters, sizeof( *Parameters ) );
    00388             }
    00389
    00390         } except( EXCEPTION_EXECUTE_HANDLER ) {
    00391
    00392             Status = GetExceptionCode();
    00393         }
    00394
    00395         if (!NT_SUCCESS( Status )) {
    00396
    00397             return NULL;
    00398         }
    00399     }
    00400
    00401     //
    00402     //  Set the parameter block to the local copy
    00403     //
    00404
    00405     Parameters = &TempParameters;
    00406
    00407     //
    00408     //  If nt global flags tells us to always do tail or free checking
    00409     //  or to disable coalescing then force those bits set in the user
    00410     //  specified flags
    00411     //
    00412
    00413     if (NtGlobalFlag & FLG_HEAP_ENABLE_TAIL_CHECK) {
    00414
    00415         Flags |= HEAP_TAIL_CHECKING_ENABLED;
    00416     }
    00417
    00418     if (NtGlobalFlag & FLG_HEAP_ENABLE_FREE_CHECK) {
    00419
    00420         Flags |= HEAP_FREE_CHECKING_ENABLED;
    00421     }
    00422
    00423     if (NtGlobalFlag & FLG_HEAP_DISABLE_COALESCING) {
    00424
    00425         Flags |= HEAP_DISABLE_COALESCE_ON_FREE;
    00426     }
    00427
    00428 #ifndef NTOS_KERNEL_RUNTIME
    00429
    00430     //
    00431     //  In the non kernel case we also check if we should
    00432     //  validate parameters, validate all, or do stack backtraces
    00433     //
    00434
    00435     Peb = NtCurrentPeb();
    00436
    00437     if (NtGlobalFlag & FLG_HEAP_VALIDATE_PARAMETERS) {
    00438
    00439         Flags |= HEAP_VALIDATE_PARAMETERS_ENABLED;
    00440     }
    00441
    00442     if (NtGlobalFlag & FLG_HEAP_VALIDATE_ALL) {
    00443
    00444         Flags |= HEAP_VALIDATE_ALL_ENABLED;
    00445     }
    00446
    00447     if (NtGlobalFlag & FLG_USER_STACK_TRACE_DB) {
    00448
    00449         Flags |= HEAP_CAPTURE_STACK_BACKTRACES;
    00450     }
    00451
    00452     //
    00453     //  Also in the non kernel case the PEB will have some state
    00454     //  variables that we need to set if the user hasn't specified
    00455     //  otherwise
    00456     //
    00457
    00458     if (Parameters->SegmentReserve == 0) {
    00459
    00460         Parameters->SegmentReserve = Peb->HeapSegmentReserve;
    00461     }
    00462
    00463     if (Parameters->SegmentCommit == 0) {
    00464
    00465         Parameters->SegmentCommit = Peb->HeapSegmentCommit;
    00466     }
    00467
    00468     if (Parameters->DeCommitFreeBlockThreshold == 0) {
    00469
    00470         Parameters->DeCommitFreeBlockThreshold = Peb->HeapDeCommitFreeBlockThreshold;
    00471     }
    00472
    00473     if (Parameters->DeCommitTotalFreeThreshold == 0) {
    00474
    00475         Parameters->DeCommitTotalFreeThreshold = Peb->HeapDeCommitTotalFreeThreshold;
    00476     }
    00477 #else // NTOS_KERNEL_RUNTIME
    00478
    00479     //
    00480     //  In the kernel case Mm has some global variables that we set
    00481     //  into the paramters if the user hasn't specified otherwise
    00482     //
    00483
    00484     if (Parameters->SegmentReserve == 0) {
    00485
    00486         Parameters->SegmentReserve = MmHeapSegmentReserve;
    00487     }
    00488
    00489     if (Parameters->SegmentCommit == 0) {
    00490
    00491         Parameters->SegmentCommit = MmHeapSegmentCommit;
    00492     }
    00493
    00494     if (Parameters->DeCommitFreeBlockThreshold == 0) {
    00495
    00496         Parameters->DeCommitFreeBlockThreshold = MmHeapDeCommitFreeBlockThreshold;
    00497     }
    00498
    00499     if (Parameters->DeCommitTotalFreeThreshold == 0) {
    00500
    00501         Parameters->DeCommitTotalFreeThreshold = MmHeapDeCommitTotalFreeThreshold;
    00502     }
    00503 #endif // NTOS_KERNEL_RUNTIME
    00504
    00505     //
    00506     //  Get the highest user address
    00507     //
    00508
    00509     if (!NT_SUCCESS(ZwQuerySystemInformation(SystemBasicInformation,
    00510                                              &SystemInformation,
    00511                                              sizeof(SystemInformation),
    00512                                              NULL))) {
    00513         return NULL;
    00514     }
    00515     HighestUserAddress = SystemInformation.MaximumUserModeAddress;
    00516
    00517     //
    00518     //  If the user hasn't said what the largest allocation size is then
    00519     //  we should compute it as the difference between the highest and lowest
    00520     //  address less one page
    00521     //
    00522
    00523     if (Parameters->MaximumAllocationSize == 0) {
    00524
    00525         Parameters->MaximumAllocationSize = (HighestUserAddress -
    00526                                              (ULONG_PTR)MM_LOWEST_USER_ADDRESS -
    00527                                              PAGE_SIZE );
    00528     }
    00529
    00530     //
    00531     //  Set the virtual memory threshold to be non zero and not more than the
    00532     //  maximum heap block size of 0x7f000.  If the user specified one that is
    00533     //  too large we automatically and silently drop it down.
    00534     //
    00535
    00536     if ((Parameters->VirtualMemoryThreshold == 0) ||
    00537         (Parameters->VirtualMemoryThreshold > MaximumHeapBlockSize)) {
    00538
    00539         Parameters->VirtualMemoryThreshold = MaximumHeapBlockSize;
    00540     }
    00541
    00542     //
    00543     //  The default commit size is one page and the default reserve size is
    00544     //  64 pages.
    00545     //
    00546     //  **** this doesn't check that commit size if specified is less than
    00547     //  **** reserved size if specified
    00548     //
    00549
    00550     if (!ARGUMENT_PRESENT( CommitSize )) {
    00551
    00552         CommitSize = PAGE_SIZE;
    00553
    00554         if (!ARGUMENT_PRESENT( ReserveSize )) {
    00555
    00556             ReserveSize = 64 * CommitSize;
    00557
    00558         } else {
    00559
    00560             ReserveSize = ROUND_UP_TO_POWER2( ReserveSize, PAGE_SIZE );
    00561         }
    00562
    00563     } else {
    00564
    00565         //
    00566         //  The heap actually uses space that is reserved and commited
    00567         //  to store internal data structures (the LOCK,
    00568         //  the HEAP_PSEUDO_TAG, etc.). These structures can be larger than
    00569         //  4K especially on a 64-bit build. So, make sure the commit
    00570         //  is at least 8K in length which is the minimal page size for
    00571         //  64-bit systems
    00572         //
    00573
    00574         CommitSize = ROUND_UP_TO_POWER2(CommitSize, PAGE_SIZE);
    00575
    00576         if (!ARGUMENT_PRESENT( ReserveSize )) {
    00577
    00578             ReserveSize = ROUND_UP_TO_POWER2( CommitSize, 16 * PAGE_SIZE );
    00579
    00580         } else {
    00581
    00582             ReserveSize = ROUND_UP_TO_POWER2( ReserveSize, PAGE_SIZE );
    00583         }
    00584
    00585     }
    00586
    00587 #ifndef NTOS_KERNEL_RUNTIME
    00588
    00589     //
    00590     //  In the non kernel case check if we are creating a debug heap
    00591     //  the test checks that skip validation checks is false.
    00592     //
    00593
    00594     if (DEBUG_HEAP( Flags )) {
    00595
    00596         return RtlDebugCreateHeap( Flags,
    00597                                    HeapBase,
    00598                                    ReserveSize,
    00599                                    CommitSize,
    00600                                    Lock,
    00601                                    Parameters );
    00602     }
    00603
    00604 #endif // NTOS_KERNEL_RUNTIME
    00605
    00606     //
    00607     //  Compute the size of the heap which will be the
    00608     //  heap struct itself and if we are to seralize with
    00609     //  out own lock then add room for the lock.  If the
    00610     //  user did not supply the lock then set the lock
    00611     //  variable to -1.
    00612     //
    00613
    00614     SizeOfHeapHeader = sizeof( HEAP );
    00615
    00616     if (!(Flags & HEAP_NO_SERIALIZE)) {
    00617
    00618         if (ARGUMENT_PRESENT( Lock )) {
    00619
    00620             Flags |= HEAP_LOCK_USER_ALLOCATED;
    00621
    00622         } else {
    00623
    00624             SizeOfHeapHeader += sizeof( HEAP_LOCK );
    00625             Lock = (PHEAP_LOCK)-1;
    00626         }
    00627
    00628     } else if (ARGUMENT_PRESENT( Lock )) {
    00629
    00630         //
    00631         //  In this error case the call said not to seralize but also fed us
    00632         //  a lock
    00633         //
    00634
    00635         return NULL;
    00636     }
    00637
    00638     //
    00639     //  See if caller allocate the space for the heap.
    00640     //
    00641
    00642     if (ARGUMENT_PRESENT( HeapBase )) {
    00643
    00644         //
    00645         //  The call specified a heap base now check if there is
    00646         //  a caller supplied commit routine
    00647         //
    00648
    00649         if (Parameters->CommitRoutine != NULL) {
    00650
    00651             //
    00652             //  The caller specified a commit routine so he caller
    00653             //  also needs to have given us certain parameters and make
    00654             //  sure the heap is not growable.  Otherwise it is an error
    00655             //
    00656
    00657             if ((Parameters->InitialCommit == 0) ||
    00658                 (Parameters->InitialReserve == 0) ||
    00659                 (Parameters->InitialCommit > Parameters->InitialReserve) ||
    00660                 (Flags & HEAP_GROWABLE)) {
    00661
    00662                 return NULL;
    00663             }
    00664
    00665             //
    00666             //  Set the commited base and the uncommited base to the
    00667             //  proper pointers within the heap.
    00668             //
    00669
    00670             CommittedBase = HeapBase;
    00671             UnCommittedBase = (PCHAR)CommittedBase + Parameters->InitialCommit;
    00672             ReserveSize = Parameters->InitialReserve;
    00673
    00674             //
    00675             //  Zero out a page of the heap where our first part goes
    00676             //
    00677             //  **** what if the size is less than a page
    00678             //
    00679
    00680             RtlZeroMemory( CommittedBase, PAGE_SIZE );
    00681
    00682         } else {
    00683
    00684             //
    00685             //  The user gave us space but not commit routine
    00686             //  So query the base to get its size
    00687             //
    00688
    00689             Status = ZwQueryVirtualMemory( NtCurrentProcess(),
    00690                                            HeapBase,
    00691                                            MemoryBasicInformation,
    00692                                            &MemoryInformation,
    00693                                            sizeof( MemoryInformation ),
    00694                                            NULL );
    00695
    00696             if (!NT_SUCCESS( Status )) {
    00697
    00698                 return NULL;
    00699             }
    00700
    00701             //
    00702             //  Make sure the user gave us a base address for this block
    00703             //  and that the memory is not free
    00704             //
    00705
    00706             if (MemoryInformation.BaseAddress != HeapBase) {
    00707
    00708                 return NULL;
    00709             }
    00710
    00711             if (MemoryInformation.State == MEM_FREE) {
    00712
    00713                 return NULL;
    00714             }
    00715
    00716             //
    00717             //  Set our commit base to the start of the range
    00718             //
    00719
    00720             CommittedBase = MemoryInformation.BaseAddress;
    00721
    00722             //
    00723             //  If the memory is commmitted then
    00724             //  we can zero out a page worth
    00725             //
    00726
    00727             if (MemoryInformation.State == MEM_COMMIT) {
    00728
    00729                 RtlZeroMemory( CommittedBase, PAGE_SIZE );
    00730
    00731                 //
    00732                 //  Set the commit size and uncommited base according
    00733                 //  to the start of the vm
    00734                 //
    00735
    00736                 CommitSize = MemoryInformation.RegionSize;
    00737                 UnCommittedBase = (PCHAR)CommittedBase + CommitSize;
    00738
    00739                 //
    00740                 //  Find out the uncommited base is reserved and if so
    00741                 //  the update the reserve size accordingly.
    00742                 //
    00743
    00744                 Status = ZwQueryVirtualMemory( NtCurrentProcess(),
    00745                                                UnCommittedBase,
    00746                                                MemoryBasicInformation,
    00747                                                &MemoryInformation,
    00748                                                sizeof( MemoryInformation ),
    00749                                                NULL );
    00750
    00751                 ReserveSize = CommitSize;
    00752
    00753                 if ((NT_SUCCESS( Status )) &&
    00754                     (MemoryInformation.State == MEM_RESERVE)) {
    00755
    00756                     ReserveSize += MemoryInformation.RegionSize;
    00757                 }
    00758
    00759             } else {
    00760
    00761                 //
    00762                 //  The memory the user gave us is not committed so dummy
    00763                 //  up these small nummbers
    00764                 //
    00765
    00766                 CommitSize = PAGE_SIZE;
    00767                 UnCommittedBase = CommittedBase;
    00768             }
    00769         }
    00770
    00771         //
    00772         //  This user gave us a base and we've just taken care of the committed
    00773         //  bookkeeping.  So mark this segment as user supplied and set the
    00774         //  heap
    00775         //
    00776
    00777         SegmentFlags = HEAP_SEGMENT_USER_ALLOCATED;
    00778         Heap = (PHEAP)HeapBase;
    00779
    00780     } else {
    00781
    00782         //
    00783         //  The user did not specify a heap base so we have to allocate the
    00784         //  vm here.  First make sure the user did not give us a commit routine
    00785         //
    00786
    00787         if (Parameters->CommitRoutine != NULL) {
    00788
    00789             return NULL;
    00790         }
    00791
    00792         //
    00793         //  Reserve the amount of virtual address space requested.
    00794         //
    00795
    00796         Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    00797                                           (PVOID *)&Heap,
    00798                                           0,
    00799                                           &ReserveSize,
    00800                                           MEM_RESERVE,
    00801                                           PAGE_READWRITE );
    00802
    00803         if (!NT_SUCCESS( Status )) {
    00804
    00805             return NULL;
    00806         }
    00807
    00808         //
    00809         //  Indicate that this segment is not user supplied
    00810         //
    00811
    00812         SegmentFlags = 0;
    00813
    00814         //
    00815         //  Set the default commit size to one page
    00816         //
    00817
    00818         if (!ARGUMENT_PRESENT( CommitSize )) {
    00819
    00820             CommitSize = PAGE_SIZE;
    00821         }
    00822
    00823         //
    00824         //  Set the committed and uncommitted base to be the same the following
    00825         //  code will actually commit the page for us
    00826         //
    00827
    00828         CommittedBase = Heap;
    00829         UnCommittedBase = Heap;
    00830     }
    00831
    00832     //
    00833     //  At this point we have a heap pointer, committed base, uncommitted base,
    00834     //  segment flags, commit size, and reserve size.  If the committed and
    00835     //  uncommited base are the same then we need to commit the amount
    00836     //  specified by the commit size
    00837     //
    00838
    00839     if (CommittedBase == UnCommittedBase) {
    00840
    00841         Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    00842                                           (PVOID *)&CommittedBase,
    00843                                           0,
    00844                                           &CommitSize,
    00845                                           MEM_COMMIT,
    00846                                           PAGE_READWRITE );
    00847
    00848         //
    00849         //  In the non successful case we need to back out any vm reservation
    00850         //  we did earlier
    00851         //
    00852
    00853         if (!NT_SUCCESS( Status )) {
    00854
    00855             if (!ARGUMENT_PRESENT(HeapBase)) {
    00856
    00857                 //
    00858                 //  Return the reserved virtual address space.
    00859                 //
    00860
    00861                 ZwFreeVirtualMemory( NtCurrentProcess(),
    00862                                      (PVOID *)&Heap,
    00863                                      &ReserveSize,
    00864                                      MEM_RELEASE );
    00865
    00866             }
    00867
    00868             return NULL;
    00869         }
    00870
    00871         //
    00872         //  The new uncommitted base is not adjusted above what we just
    00873         //  committed
    00874         //
    00875
    00876         UnCommittedBase = (PVOID)((PCHAR)UnCommittedBase + CommitSize);
    00877     }
    00878
    00879     //
    00880     //  At this point we have memory for the start of the heap committed and
    00881     //  ready to be initialized.  So now we need initialize the heap
    00882     //
    00883
    00884     //
    00885     //  Calculate the end of the heap header and make room for 8 uncommitted
    00886     //  range structures.  Once we have the room for them then chain them
    00887     //  together and null terminate the chain
    00888     //
    00889
    00890     NextHeapHeaderAddress = Heap + 1;
    00891
    00892     UnCommittedRange = (PHEAP_UNCOMMMTTED_RANGE)ROUND_UP_TO_POWER2( NextHeapHeaderAddress,
    00893                                                                     sizeof( QUAD ) );
    00894
    00895     InitialCountOfUnusedUnCommittedRanges = 8;
    00896
    00897     SizeOfHeapHeader += InitialCountOfUnusedUnCommittedRanges * sizeof( *UnCommittedRange );
    00898
    00899     //
    00900     //  **** what a hack Pp is really a pointer to the next field of the
    00901     //  **** uncommmtted range structure.  So we set next by setting through Pp
    00902     //
    00903
    00904     pp = &Heap->UnusedUnCommittedRanges;
    00905
    00906     while (InitialCountOfUnusedUnCommittedRanges--) {
    00907
    00908         *pp = UnCommittedRange;
    00909         pp = &UnCommittedRange->Next;
    00910         UnCommittedRange += 1;
    00911     }
    00912
    00913     NextHeapHeaderAddress = UnCommittedRange;
    00914
    00915     *pp = NULL;
    00916
    00917     //
    00918     //  Check if tagging is enabled in global flags.  This check is always true
    00919     //  in a debug build.
    00920     //
    00921     //  If tagging is enabled then make room for 129 pseudo tag heap entry.
    00922     //  Which is one more than the number of free lists.  Also point the heap
    00923     //  header to this array of pseudo tags entries.
    00924     //
    00925
    00926     if (IS_HEAP_TAGGING_ENABLED()) {
    00927
    00928         Heap->PseudoTagEntries = (PHEAP_PSEUDO_TAG_ENTRY)ROUND_UP_TO_POWER2( NextHeapHeaderAddress,
    00929                                                                              sizeof( QUAD ) );
    00930
    00931         SizeOfHeapHeader += HEAP_NUMBER_OF_PSEUDO_TAG * sizeof( HEAP_PSEUDO_TAG_ENTRY );
    00932
    00933         //
    00934         //  **** this advancement of the next heap address doesn't seem right
    00935         //  **** given that a pseudo heap entry is 12 ulongs in length and not
    00936         //  **** a single byte
    00937
    00938         NextHeapHeaderAddress = Heap->PseudoTagEntries + HEAP_NUMBER_OF_PSEUDO_TAG;
    00939     }
    00940
    00941     //
    00942     //  Round the size of the heap header to the next 8 byte boundary
    00943     //
    00944
    00945     SizeOfHeapHeader = (ULONG) ROUND_UP_TO_POWER2( SizeOfHeapHeader,
    00946                                                    HEAP_GRANULARITY );
    00947
    00948     //
    00949     //  If the sizeof the heap header is larger than the native
    00950     //  page size, you have a problem. Further, if the CommitSize passed
    00951     //  in was smaller than the SizeOfHeapHeader, you may not even make it
    00952     //  this far before death...
    00953     //
    00954     //  HeapDbgPrint() doesn't work for IA64 yet.
    00955     //
    00956     //  HeapDbgPrint(("Size of the heap header is %u bytes, commit was %u bytes\n", SizeOfHeapHeader, (ULONG) CommitSize));
    00957     //
    00958
    00959     //
    00960     //  Fill in the heap header fields
    00961     //
    00962
    00963     Heap->Entry.Size = (USHORT)(SizeOfHeapHeader >> HEAP_GRANULARITY_SHIFT);
    00964     Heap->Entry.Flags = HEAP_ENTRY_BUSY;
    00965
    00966     Heap->Signature = HEAP_SIGNATURE;
    00967     Heap->Flags = Flags;
    00968     Heap->ForceFlags = (Flags & (HEAP_NO_SERIALIZE |
    00969                                  HEAP_GENERATE_EXCEPTIONS |
    00970                                  HEAP_ZERO_MEMORY |
    00971                                  HEAP_REALLOC_IN_PLACE_ONLY |
    00972                                  HEAP_VALIDATE_PARAMETERS_ENABLED |
    00973                                  HEAP_VALIDATE_ALL_ENABLED |
    00974                                  HEAP_TAIL_CHECKING_ENABLED |
    00975                                  HEAP_CREATE_ALIGN_16 |
    00976                                  HEAP_FREE_CHECKING_ENABLED));
    00977
    00978     Heap->FreeListsInUseTerminate = 0xFFFF;
    00979     Heap->HeaderValidateLength = (USHORT)((PCHAR)NextHeapHeaderAddress - (PCHAR)Heap);
    00980     Heap->HeaderValidateCopy = NULL;
    00981
    00982     //
    00983     //  Initialize the free list to be all empty
    00984     //
    00985
    00986     FreeListHead = &Heap->FreeLists[ 0 ];
    00987     n = HEAP_MAXIMUM_FREELISTS;
    00988
    00989     while (n--) {
    00990
    00991         InitializeListHead( FreeListHead );
    00992         FreeListHead++;
    00993     }
    00994
    00995     //
    00996     //  Make it so that there a no big block allocations
    00997     //
    00998
    00999     InitializeListHead( &Heap->VirtualAllocdBlocks );
    01000
    01001     //
    01002     //  Initialize the cricital section that controls access to
    01003     //  the free list.  If the lock variable is -1 then the caller
    01004     //  did not supply a lock so we need to make room for one
    01005     //  and initialize it.
    01006     //
    01007
    01008     if (Lock == (PHEAP_LOCK)-1) {
    01009
    01010         Lock = (PHEAP_LOCK)NextHeapHeaderAddress;
    01011
    01012         Status = RtlInitializeLockRoutine( Lock );
    01013
    01014         if (!NT_SUCCESS( Status )) {
    01015
    01016             return NULL;
    01017         }
    01018
    01019         NextHeapHeaderAddress = (PHEAP_LOCK)Lock + 1;
    01020     }
    01021
    01022     Heap->LockVariable = Lock;
    01023
    01024
    01025     //
    01026     //  Initialize the first segment for the heap
    01027     //
    01028
    01029     if (!RtlpInitializeHeapSegment( Heap,
    01030                                     (PHEAP_SEGMENT)((PCHAR)Heap + SizeOfHeapHeader),
    01031                                     0,
    01032                                     SegmentFlags,
    01033                                     CommittedBase,
    01034                                     UnCommittedBase,
    01035                                     (PCHAR)CommittedBase + ReserveSize )) {
    01036
    01037         return NULL;
    01038     }
    01039
    01040     //
    01041     //  Fill in additional heap entry fields
    01042     //
    01043
    01044     Heap->ProcessHeapsListIndex = 0;
    01045     Heap->SegmentReserve = Parameters->SegmentReserve;
    01046     Heap->SegmentCommit = Parameters->SegmentCommit;
    01047     Heap->DeCommitFreeBlockThreshold = Parameters->DeCommitFreeBlockThreshold >> HEAP_GRANULARITY_SHIFT;
    01048     Heap->DeCommitTotalFreeThreshold = Parameters->DeCommitTotalFreeThreshold >> HEAP_GRANULARITY_SHIFT;
    01049     Heap->MaximumAllocationSize = Parameters->MaximumAllocationSize;
    01050
    01051     Heap->VirtualMemoryThreshold = (ULONG) (ROUND_UP_TO_POWER2( Parameters->VirtualMemoryThreshold,
    01052                                                        HEAP_GRANULARITY ) >> HEAP_GRANULARITY_SHIFT);
    01053
    01054     Heap->CommitRoutine = Parameters->CommitRoutine;
    01055
    01056     //
    01057     //  We either align the heap at 16 or 8 byte boundaries.  The AlignRound
    01058     //  and AlignMask are used to bring allocation sizes up to the next
    01059     //  boundary.  The align round includes the heap header and the optional
    01060     //  check tail size
    01061     //
    01062
    01063     if (Flags & HEAP_CREATE_ALIGN_16) {
    01064
    01065         Heap->AlignRound = 15 + sizeof( HEAP_ENTRY );
    01066         Heap->AlignMask = (ULONG)~15;
    01067
    01068     } else {
    01069
    01070         Heap->AlignRound = HEAP_GRANULARITY - 1 + sizeof( HEAP_ENTRY );
    01071         Heap->AlignMask = (ULONG)~(HEAP_GRANULARITY - 1);
    01072     }
    01073
    01074     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) {
    01075
    01076         Heap->AlignRound += CHECK_HEAP_TAIL_SIZE;
    01077     }
    01078
    01079 #ifndef NTOS_KERNEL_RUNTIME
    01080
    01081     //
    01082     //  In the non kernel case we need to add this heap to the processes heap
    01083     //  list
    01084     //
    01085
    01086     RtlpAddHeapToProcessList( Heap );
    01087
    01088     //
    01089     //  Initialize the heap lookaide lists.  This is only for the user mode
    01090     //  heap and the heap contains a pointer to the lookaside list array.
    01091     //  The array is sized the same as the dedicated free list.  First we
    01092     //  allocate space for the lookaside list and then we initialize each
    01093     //  lookaside list.
    01094     //
    01095     //  But the caller asked for no serialize or asked for non growable
    01096     //  heap then we won't enable the lookaside lists.
    01097     //
    01098
    01099     Heap->Lookaside = NULL;
    01100     Heap->LookasideLockCount = 0;
    01101
    01102     if ((!(Flags & HEAP_NO_SERIALIZE)) &&
    01103         ( (Flags & HEAP_GROWABLE)) &&
    01104         (!(RtlpDisableHeapLookaside))) {
    01105
    01106         ULONG i;
    01107
    01108         Heap->Lookaside = RtlAllocateHeap( Heap,
    01109                                            Flags,
    01110                                            sizeof(HEAP_LOOKASIDE) * HEAP_MAXIMUM_FREELISTS );
    01111
    01112         if (Heap->Lookaside != NULL) {
    01113
    01114             for (i = 0; i < HEAP_MAXIMUM_FREELISTS; i += 1) {
    01115
    01116                 RtlpInitializeHeapLookaside( &(((PHEAP_LOOKASIDE)(Heap->Lookaside))[i]),
    01117                                              32 );
    01118             }
    01119         }
    01120     }
    01121
    01122 #endif // NTOS_KERNEL_RUNTIME
    01123
    01124     //
    01125     //  And return the fully initialized heap to our caller
    01126     //
    01127
    01128     return (PVOID)Heap;
    01129 }
    01130
    01131
    01132 PVOID
    01133 RtlDestroyHeap (
    01134     IN PVOID HeapHandle
    01135     )
    01136
    01137 /*++
    01138
    01139 Routine Description:
    01140
    01141     This routine is the opposite of Rtl Create Heap.  It tears down an
    01142     existing heap structure.
    01143
    01144 Arguments:
    01145
    01146     HeapHandle - Supplies a pointer to the heap being destroyed
    01147
    01148 Return Value:
    01149
    01150     PVOID - Returns null if the heap was destroyed completely and a
    01151         pointer back to the heap if for some reason the heap could
    01152         not be destroyed.
    01153
    01154 --*/
    01155
    01156 {
    01157     PHEAP Heap = (PHEAP)HeapHandle;
    01158     PHEAP_SEGMENT Segment;
    01159     PHEAP_UCR_SEGMENT UCRSegments;
    01160     PLIST_ENTRY Head, Next;
    01161     PVOID BaseAddress;
    01162     SIZE_T RegionSize;
    01163     UCHAR SegmentIndex;
    01164
    01165     //
    01166     //  Validate that HeapAddress points to a HEAP structure.
    01167     //
    01168
    01169     RTL_PAGED_CODE();
    01170
    01171     if (HeapHandle == NULL) {
    01172
    01173         HeapDebugPrint(( "Ignoring RtlDestroyHeap( NULL )\n" ));
    01174
    01175         return NULL;
    01176     }
    01177
    01178 #ifndef NTOS_KERNEL_RUNTIME
    01179 #ifdef NTHEAP_ENABLED
    01180     {
    01181         if (Heap->Flags & NTHEAP_ENABLED_FLAG) {
    01182
    01183             return RtlDestroyNtHeap( HeapHandle );
    01184         }
    01185     }
    01186 #endif // NTHEAP_ENABLED
    01187 #endif // NTOS_KERNEL_RUNTIME
    01188
    01189     //
    01190     //  Check if this is the debug version of heap using page allocation
    01191     //  with guard pages
    01192     //
    01193
    01194     IF_DEBUG_PAGE_HEAP_THEN_RETURN( HeapHandle,
    01195                                     RtlpDebugPageHeapDestroy( HeapHandle ));
    01196
    01197 #ifndef NTOS_KERNEL_RUNTIME
    01198
    01199     //
    01200     //  In the non kernel case check if this is the debug version of heap
    01201     //  and of so then call the debug version to do the teardown
    01202     //
    01203
    01204     if (DEBUG_HEAP( Heap->Flags )) {
    01205
    01206         if (!RtlDebugDestroyHeap( HeapHandle )) {
    01207
    01208             return HeapHandle;
    01209         }
    01210     }
    01211
    01212     //
    01213     //  We are not allowed to destroy the process heap
    01214     //
    01215
    01216     if (HeapHandle == NtCurrentPeb()->ProcessHeap) {
    01217
    01218         return HeapHandle;
    01219     }
    01220
    01221 #endif // NTOS_KERNEL_RUNTIME
    01222
    01223     //
    01224     //  For every big allocation we remove it from the list and free the
    01225     //  vm
    01226     //
    01227
    01228     Head = &Heap->VirtualAllocdBlocks;
    01229     Next = Head->Flink;
    01230
    01231     while (Head != Next) {
    01232
    01233         BaseAddress = CONTAINING_RECORD( Next, HEAP_VIRTUAL_ALLOC_ENTRY, Entry );
    01234
    01235         Next = Next->Flink;
    01236         RegionSize = 0;
    01237
    01238         ZwFreeVirtualMemory( NtCurrentProcess(),
    01239                              (PVOID *)&BaseAddress,
    01240                              &RegionSize,
    01241                              MEM_RELEASE );
    01242     }
    01243
    01244 #ifndef NTOS_KERNEL_RUNTIME
    01245
    01246     //
    01247     //  In the non kernel case we need to destory any heap tags we have setup
    01248     //  and remove this heap from the process heap list
    01249     //
    01250
    01251     RtlpDestroyTags( Heap );
    01252     RtlpRemoveHeapFromProcessList( Heap );
    01253
    01254 #endif // NTOS_KERNEL_RUNTIME
    01255
    01256     //
    01257     //  If the heap is serialized, delete the critical section created
    01258     //  by RtlCreateHeap.
    01259     //
    01260
    01261     if (!(Heap->Flags & HEAP_NO_SERIALIZE)) {
    01262
    01263         if (!(Heap->Flags & HEAP_LOCK_USER_ALLOCATED)) {
    01264
    01265             (VOID)RtlDeleteLockRoutine( Heap->LockVariable );
    01266         }
    01267
    01268         Heap->LockVariable = NULL;
    01269     }
    01270
    01271     //
    01272     //  For every uncommitted segment we free its vm
    01273     //
    01274
    01275     UCRSegments = Heap->UCRSegments;
    01276     Heap->UCRSegments = NULL;
    01277
    01278     while (UCRSegments) {
    01279
    01280         BaseAddress = UCRSegments;
    01281         UCRSegments = UCRSegments->Next;
    01282         RegionSize = 0;
    01283
    01284         ZwFreeVirtualMemory( NtCurrentProcess(),
    01285                              &BaseAddress,
    01286                              &RegionSize,
    01287                              MEM_RELEASE );
    01288     }
    01289
    01290     //
    01291     //  For every segment in the heap we call a worker routine to
    01292     //  destory the segment
    01293     //
    01294
    01295     SegmentIndex = HEAP_MAXIMUM_SEGMENTS;
    01296
    01297     while (SegmentIndex--) {
    01298
    01299         Segment = Heap->Segments[ SegmentIndex ];
    01300
    01301         if (Segment) {
    01302
    01303             RtlpDestroyHeapSegment( Segment );
    01304         }
    01305     }
    01306
    01307     //
    01308     //  And we return to our caller
    01309     //
    01310
    01311     return NULL;
    01312 }
    01313
    01314
    01315 PVOID
    01316 RtlAllocateHeap (
    01317     IN PVOID HeapHandle,
    01318     IN ULONG Flags,
    01319     IN SIZE_T Size
    01320     )
    01321
    01322 /*++
    01323
    01324 Routine Description:
    01325
    01326     This routine allocates a memory of the specified size from the specified
    01327     heap.
    01328
    01329 Arguments:
    01330
    01331     HeapHandle - Supplies a pointer to an initialized heap structure
    01332
    01333     Flags - Specifies the set of flags to use to control the allocation
    01334
    01335     Size - Specifies the size, in bytes, of the allocation
    01336
    01337 Return Value:
    01338
    01339     PVOID - returns a pointer to the newly allocated block
    01340
    01341 --*/
    01342
    01343 {
    01344     PHEAP Heap = (PHEAP)HeapHandle;
    01345     PULONG FreeListsInUse;
    01346     ULONG FreeListsInUseUlong;
    01347     SIZE_T AllocationSize;
    01348     SIZE_T FreeSize, AllocationIndex;
    01349     PLIST_ENTRY FreeListHead, Next;
    01350     PHEAP_ENTRY BusyBlock;
    01351     PHEAP_FREE_ENTRY FreeBlock, SplitBlock, SplitBlock2;
    01352     ULONG InUseIndex;
    01353     UCHAR FreeFlags;
    01354     NTSTATUS Status;
    01355     EXCEPTION_RECORD ExceptionRecord;
    01356     PVOID ReturnValue;
    01357     BOOLEAN LockAcquired = FALSE;
    01358
    01359     RTL_PAGED_CODE();
    01360
    01361
    01362 #ifndef NTOS_KERNEL_RUNTIME
    01363 #ifdef NTHEAP_ENABLED
    01364     {
    01365         if (Heap->Flags & NTHEAP_ENABLED_FLAG) {
    01366
    01367             return RtlAllocateNtHeap( HeapHandle,
    01368                                       Flags,
    01369                                       Size);
    01370         }
    01371     }
    01372 #endif // NTHEAP_ENABLED
    01373 #endif // NTOS_KERNEL_RUNTIME
    01374
    01375
    01376     //
    01377     //  Take the callers flags and add in the flags that we must forcibly set
    01378     //  in the heap
    01379     //
    01380
    01381     Flags |= Heap->ForceFlags;
    01382
    01383     //
    01384     //  Check for special features that force us to call the slow, do-everything
    01385     //  version.  We do everything slow for any of the following flags.
    01386     //
    01387     //    HEAP_SLOW_FLAGS defined as           0x6f030f60
    01388     //
    01389     //      HEAP_DEBUG_FLAGS, defined as       0x69020000 (heappriv.h)
    01390     //
    01391     //        HEAP_VALIDATE_PARAMETERS_ENABLED 0x40000000 (heap.h)
    01392     //
    01393     //        HEAP_VALIDATE_ALL_ENABLED        0x20000000 (heap.h)
    01394     //
    01395     //        HEAP_CAPTURE_STACK_BACKTRACES    0x08000000 (heap.h)
    01396     //
    01397     //        HEAP_CREATE_ENABLE_TRACING       0x00020000 (ntrtl.h winnt obsolete)
    01398     //
    01399     //        HEAP_FLAG_PAGE_ALLOCS            0x01000000 (heappage.h)
    01400     //
    01401     //      HEAP_SETTABLE_USER_FLAGS           0x00000E00 (ntrtl.h)
    01402     //
    01403     //      HEAP_NEED_EXTRA_FLAGS              0x0f000100 (heap.h)
    01404     //
    01405     //      HEAP_CREATE_ALIGN_16               0x00010000 (ntrtl.h winnt obsolete)
    01406     //
    01407     //      HEAP_FREE_CHECKING_ENABLED         0x00000040 (ntrtl.h winnt)
    01408     //
    01409     //      HEAP_TAIL_CHECKING_ENABLED         0x00000020 (ntrtl.h winnt )
    01410     //
    01411     //  We also do everything slow if the size is greater than max long
    01412     //
    01413
    01414     if ((Flags & HEAP_SLOW_FLAGS) || (Size >= 0x80000000)) {
    01415
    01416         return RtlAllocateHeapSlowly( HeapHandle, Flags, Size );
    01417     }
    01418
    01419     //
    01420     //  At this point we know we are doing everything in this routine
    01421     //  and not taking the slow route.
    01422     //
    01423     //  Round the requested size up to the allocation granularity.  Note
    01424     //  that if the request is for 0 bytes, we still allocate memory, because
    01425     //  we add in an extra 1 byte to protect ourselves from idiots.
    01426     //
    01427     //      Allocation size will be either 16, 24, 32, ...
    01428     //      Allocation index will be 2, 3, 4, ...
    01429     //
    01430     //  Note that allocation size 8 is skipped and are indices 0 and 1
    01431     //
    01432
    01433     AllocationSize = ((Size ? Size : 1) + HEAP_GRANULARITY - 1 + sizeof( HEAP_ENTRY ))
    01434         & ~(HEAP_GRANULARITY -1);
    01435     AllocationIndex = AllocationSize >>  HEAP_GRANULARITY_SHIFT;
    01436
    01437     //
    01438     //  If there is a lookaside list and the index is within limits then
    01439     //  try and allocate from the lookaside list.  We'll actually capture
    01440     //  the lookaside pointer from the heap and only use the captured pointer.
    01441     //  This will take care of the condition where a walk or lock heap can
    01442     //  cause us to check for a non null pointer and then have it become null
    01443     //  when we read it again.  If it is non null to start with then even if
    01444     //  the user walks or locks the heap via another thread the pointer to
    01445     //  still valid here so we can still try and do a lookaside list pop.
    01446     //
    01447
    01448 #ifndef NTOS_KERNEL_RUNTIME
    01449
    01450     {
    01451         PHEAP_LOOKASIDE Lookaside = (PHEAP_LOOKASIDE)Heap->Lookaside;
    01452
    01453         if ((Lookaside != NULL) &&
    01454             (Heap->LookasideLockCount == 0) &&
    01455             (AllocationIndex < HEAP_MAXIMUM_FREELISTS)) {
    01456
    01457             //
    01458             //  If the number of operation elapsed operations is 128 times the
    01459             //  lookaside depth then it is time to adjust the depth
    01460             //
    01461
    01462             if ((LONG)(Lookaside[AllocationIndex].TotalAllocates - Lookaside[AllocationIndex].LastTotalAllocates) >=
    01463                       (Lookaside[AllocationIndex].Depth * 128)) {
    01464
    01465                 RtlpAdjustHeapLookasideDepth(&(Lookaside[AllocationIndex]));
    01466             }
    01467
    01468             ReturnValue = RtlpAllocateFromHeapLookaside(&(Lookaside[AllocationIndex]));
    01469
    01470             if (ReturnValue != NULL) {
    01471
    01472                 PHEAP_ENTRY BusyBlock;
    01473
    01474                 BusyBlock = ((PHEAP_ENTRY)ReturnValue) - 1;
    01475                 BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size);
    01476                 BusyBlock->SmallTagIndex = 0;
    01477
    01478                 if (Flags & HEAP_ZERO_MEMORY) {
    01479
    01480                     RtlZeroMemory( ReturnValue, Size );
    01481                 }
    01482
    01483                 return ReturnValue;
    01484             }
    01485         }
    01486     }
    01487
    01488 #endif // NTOS_KERNEL_RUNTIME
    01489
    01490     try {
    01491
    01492         //
    01493         //  Check if we need to serialize our access to the heap
    01494         //
    01495
    01496         if (!(Flags & HEAP_NO_SERIALIZE)) {
    01497
    01498             //
    01499             //  Lock the free list.
    01500             //
    01501
    01502             RtlAcquireLockRoutine( Heap->LockVariable );
    01503
    01504             LockAcquired = TRUE;
    01505         }
    01506
    01507         //
    01508         //  If the allocation index is less than the maximum free list size
    01509         //  then we can use the index to check the free list otherwise we have
    01510         //  to either pull the entry off of the [0] index list or allocate
    01511         //  memory directly for this request.
    01512         //
    01513
    01514         if (AllocationIndex < HEAP_MAXIMUM_FREELISTS) {
    01515
    01516             //
    01517             //  With a size that matches a free list size grab the head
    01518             //  of the list and check if there is an available entry
    01519             //
    01520
    01521             FreeListHead = &Heap->FreeLists[ AllocationIndex ];
    01522
    01523             if ( !IsListEmpty( FreeListHead ))  {
    01524
    01525                 //
    01526                 //  We're in luck the list has an entry so now get the free
    01527                 //  entry,  copy its flags, remove it from the free list
    01528                 //
    01529
    01530                 FreeBlock = CONTAINING_RECORD( FreeListHead->Blink,
    01531                                                HEAP_FREE_ENTRY,
    01532                                                FreeList );
    01533
    01534                 FreeFlags = FreeBlock->Flags;
    01535
    01536                 RtlpFastRemoveDedicatedFreeBlock( Heap, FreeBlock );
    01537
    01538                 //
    01539                 //  Adjust the total number of bytes free in the heap
    01540                 //
    01541
    01542                 Heap->TotalFreeSize -= AllocationIndex;
    01543
    01544                 //
    01545                 //  Mark the block as busy and and set the number of bytes
    01546                 //  unused and tag index.  Also if it is the last entry
    01547                 //  then keep that flag.
    01548                 //
    01549
    01550                 BusyBlock = (PHEAP_ENTRY)FreeBlock;
    01551                 BusyBlock->Flags = HEAP_ENTRY_BUSY | (FreeFlags & HEAP_ENTRY_LAST_ENTRY);
    01552                 BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size);
    01553                 BusyBlock->SmallTagIndex = 0;
    01554
    01555             } else {
    01556
    01557                 //
    01558                 //  The free list that matches our request is empty
    01559                 //
    01560                 //  Scan the free list in use vector to find the smallest
    01561                 //  available free block large enough for our allocations.
    01562                 //
    01563
    01564                 //
    01565                 //  Compute the index of the ULONG where the scan should begin
    01566                 //
    01567
    01568                 InUseIndex = (ULONG) (AllocationIndex >> 5);
    01569                 FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex];
    01570
    01571                 //
    01572                 //  Mask off the bits in the first ULONG that represent allocations
    01573                 //  smaller than we need.
    01574                 //
    01575
    01576                 FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << ((ULONG) AllocationIndex & 0x1f)) - 1);
    01577
    01578                 //
    01579                 //  Begin unrolled loop to scan bit vector.
    01580                 //
    01581
    01582                 switch (InUseIndex) {
    01583
    01584                 case 0:
    01585
    01586                     if (FreeListsInUseUlong) {
    01587
    01588                         FreeListHead = &Heap->FreeLists[0];
    01589                         break;
    01590                     }
    01591
    01592                     FreeListsInUseUlong = *FreeListsInUse++;
    01593
    01594                     //
    01595                     //  deliberate fallthrough to next ULONG
    01596                     //
    01597
    01598                 case 1:
    01599
    01600                     if (FreeListsInUseUlong) {
    01601
    01602                         FreeListHead = &Heap->FreeLists[32];
    01603                         break;
    01604                     }
    01605
    01606                     FreeListsInUseUlong = *FreeListsInUse++;
    01607
    01608                     //
    01609                     //  deliberate fallthrough to next ULONG
    01610                     //
    01611
    01612                 case 2:
    01613
    01614                     if (FreeListsInUseUlong) {
    01615
    01616                         FreeListHead = &Heap->FreeLists[64];
    01617                         break;
    01618                     }
    01619
    01620                     FreeListsInUseUlong = *FreeListsInUse++;
    01621
    01622                     //
    01623                     //  deliberate fallthrough to next ULONG
    01624                     //
    01625
    01626                 case 3:
    01627
    01628                     if (FreeListsInUseUlong) {
    01629
    01630                         FreeListHead = &Heap->FreeLists[96];
    01631                         break;
    01632                     }
    01633
    01634                     //
    01635                     //  deliberate fallthrough to non dedicated list
    01636                     //
    01637
    01638                 default:
    01639
    01640                     //
    01641                     //  No suitable entry on the free list was found.
    01642                     //
    01643
    01644                     goto LookInNonDedicatedList;
    01645                 }
    01646
    01647                 //
    01648                 //  A free list has been found with a large enough allocation.
    01649                 //  FreeListHead contains the base of the vector it was found in.
    01650                 //  FreeListsInUseUlong contains the vector.
    01651                 //
    01652
    01653                 FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong );
    01654
    01655                 //
    01656                 //  Grab the free block and remove it from the free list
    01657                 //
    01658
    01659                 FreeBlock = CONTAINING_RECORD( FreeListHead->Blink,
    01660                                                HEAP_FREE_ENTRY,
    01661                                                FreeList );
    01662
    01663                 RtlpFastRemoveDedicatedFreeBlock( Heap, FreeBlock );
    01664
    01665     SplitFreeBlock:
    01666
    01667                 //
    01668                 //  Save the blocks flags and decrement the amount of
    01669                 //  free space left in the heap
    01670                 //
    01671
    01672                 FreeFlags = FreeBlock->Flags;
    01673                 Heap->TotalFreeSize -= FreeBlock->Size;
    01674
    01675                 //
    01676                 //  Mark the block busy
    01677                 //
    01678
    01679                 BusyBlock = (PHEAP_ENTRY)FreeBlock;
    01680                 BusyBlock->Flags = HEAP_ENTRY_BUSY;
    01681
    01682                 //
    01683                 //  Compute the size (i.e., index) of the amount from this block
    01684                 //  that we don't need and can return to the free list
    01685                 //
    01686
    01687                 FreeSize = BusyBlock->Size - AllocationIndex;
    01688
    01689                 //
    01690                 //  Finish setting up the rest of the new busy block
    01691                 //
    01692
    01693                 BusyBlock->Size = (USHORT)AllocationIndex;
    01694                 BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size);
    01695                 BusyBlock->SmallTagIndex = 0;
    01696
    01697                 //
    01698                 //  Now if the size that we are going to free up is not zero
    01699                 //  then lets get to work and to the split.
    01700                 //
    01701
    01702                 if (FreeSize != 0) {
    01703
    01704                     //
    01705                     //  But first we won't ever bother doing a split that only
    01706                     //  gives us 8 bytes back.  So if free size is one then just
    01707                     //  bump up the size of the new busy block
    01708                     //
    01709
    01710                     if (FreeSize == 1) {
    01711
    01712                         BusyBlock->Size += 1;
    01713                         BusyBlock->UnusedBytes += sizeof( HEAP_ENTRY );
    01714
    01715                     } else {
    01716
    01717                         //
    01718                         //  Get a pointer to where the new free block will be.
    01719                         //  When we split a block the first part goes to the new
    01720                         //  busy block and the second part goes back to the free
    01721                         //  list
    01722                         //
    01723
    01724                         SplitBlock = (PHEAP_FREE_ENTRY)(BusyBlock + AllocationIndex);
    01725
    01726                         //
    01727                         //  Reset the flags that we copied from the original free list
    01728                         //  header, and set it other size fields.
    01729                         //
    01730
    01731                         SplitBlock->Flags = FreeFlags;
    01732                         SplitBlock->PreviousSize = (USHORT)AllocationIndex;
    01733                         SplitBlock->SegmentIndex = BusyBlock->SegmentIndex;
    01734                         SplitBlock->Size = (USHORT)FreeSize;
    01735
    01736                         //
    01737                         //  If nothing else follows this entry then we will insert
    01738                         //  this into the corresponding free list (and update
    01739                         //  Segment->LastEntryInSegment)
    01740                         //
    01741
    01742                         if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) {
    01743
    01744                             RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize);
    01745                             Heap->TotalFreeSize += FreeSize;
    01746
    01747                         } else {
    01748
    01749                             //
    01750                             //  Otherwise we need to check the following block
    01751                             //  and if it is busy then update its previous size
    01752                             //  before inserting our new free block into the
    01753                             //  free list
    01754                             //
    01755
    01756                             SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
    01757
    01758                             if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) {
    01759
    01760                                 SplitBlock2->PreviousSize = (USHORT)FreeSize;
    01761
    01762                                 RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize );
    01763                                 Heap->TotalFreeSize += FreeSize;
    01764
    01765                             } else {
    01766
    01767                                 //
    01768                                 //  The following block is free so we'll merge
    01769                                 //  these to blocks. by first merging the flags
    01770                                 //
    01771
    01772                                 SplitBlock->Flags = SplitBlock2->Flags;
    01773
    01774                                 //
    01775                                 //  Removing the second block from its free list
    01776                                 //
    01777
    01778                                 RtlpFastRemoveFreeBlock( Heap, SplitBlock2 );
    01779
    01780                                 //
    01781                                 //  Updating the free total number of free bytes
    01782                                 //  in the heap and updating the size of the new
    01783                                 //  free block
    01784                                 //
    01785
    01786                                 Heap->TotalFreeSize -= SplitBlock2->Size;
    01787                                 FreeSize += SplitBlock2->Size;
    01788
    01789                                 //
    01790                                 //  If the new free block is still less than the
    01791                                 //  maximum heap block size then we'll simply
    01792                                 //  insert it back in the free list
    01793                                 //
    01794
    01795                                 if (FreeSize <= HEAP_MAXIMUM_BLOCK_SIZE) {
    01796
    01797                                     SplitBlock->Size = (USHORT)FreeSize;
    01798
    01799                                     //
    01800                                     //  Again check if the new following block
    01801                                     //  exists and if so then updsate is previous
    01802                                     //  size
    01803                                     //
    01804
    01805                                     if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    01806
    01807                                         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
    01808                                     }
    01809
    01810                                     //
    01811                                     //  Insert the new free block into the free
    01812                                     //  list and update the free heap size
    01813                                     //
    01814
    01815                                     RtlpFastInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize );
    01816                                     Heap->TotalFreeSize += FreeSize;
    01817
    01818                                 } else {
    01819
    01820                                     //
    01821                                     //  The new free block is pretty large so we
    01822                                     //  need to call a private routine to do the
    01823                                     //  insert
    01824                                     //
    01825
    01826                                     RtlpInsertFreeBlock( Heap, SplitBlock, FreeSize );
    01827                                 }
    01828                             }
    01829                         }
    01830
    01831                         //
    01832                         //  Now that free flags made it back into a free block
    01833                         //  we can zero out what we saved.
    01834                         //
    01835
    01836                         FreeFlags = 0;
    01837
    01838                         //
    01839                         //  If splitblock now last, update LastEntryInSegment
    01840                         //
    01841
    01842                         if (SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY) {
    01843
    01844                             PHEAP_SEGMENT Segment;
    01845
    01846                             Segment = Heap->Segments[SplitBlock->SegmentIndex];
    01847                             Segment->LastEntryInSegment = (PHEAP_ENTRY)SplitBlock;
    01848                         }
    01849                     }
    01850                 }
    01851
    01852                 //
    01853                 //  If there are no following entries then mark the new block as
    01854                 //  such
    01855                 //
    01856
    01857                 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) {
    01858
    01859                     BusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY;
    01860                 }
    01861             }
    01862
    01863             //
    01864             //  Return the address of the user portion of the allocated block.
    01865             //  This is the byte following the header.
    01866             //
    01867
    01868             ReturnValue = BusyBlock + 1;
    01869
    01870             //
    01871             //  **** Release the lock before the zero memory call
    01872             //
    01873
    01874             if (LockAcquired) {
    01875
    01876                 RtlReleaseLockRoutine( Heap->LockVariable );
    01877
    01878                 LockAcquired = FALSE;
    01879             }
    01880
    01881             //
    01882             //  If the flags indicate that we should zero memory then do it now
    01883             //
    01884
    01885             if (Flags & HEAP_ZERO_MEMORY) {
    01886
    01887                 RtlZeroMemory( ReturnValue, Size );
    01888             }
    01889
    01890             //
    01891             //  And return the allocated block to our caller
    01892             //
    01893
    01894             leave;
    01895
    01896         //
    01897         //  Otherwise the allocation request is bigger than the last dedicated
    01898         //  free list size.  Now check if the size is within our threshold.
    01899         //  Meaning that it could be in the [0] free list
    01900         //
    01901
    01902         } else if (AllocationIndex <= Heap->VirtualMemoryThreshold) {
    01903
    01904     LookInNonDedicatedList:
    01905
    01906             //
    01907             //  The following code cycles through the [0] free list until
    01908             //  it finds a block that satisfies the request.  The list
    01909             //  is sorted so the search is can be terminated early on success
    01910             //
    01911
    01912             FreeListHead = &Heap->FreeLists[0];
    01913
    01914             //
    01915             //  Check if the largest block in the list is smaller than the request
    01916             //
    01917
    01918             Next = FreeListHead->Blink;
    01919
    01920             if (FreeListHead != Next) {
    01921
    01922                 FreeBlock = CONTAINING_RECORD( Next, HEAP_FREE_ENTRY, FreeList );
    01923
    01924                 if (FreeBlock->Size >= AllocationIndex) {
    01925
    01926                     //
    01927                     //  Here we are sure there is at least a block here larger than
    01928                     //  the requested size. Start searching from the first block
    01929                     //
    01930
    01931                     Next = FreeListHead->Flink;
    01932
    01933                     while (FreeListHead != Next) {
    01934
    01935                         FreeBlock = CONTAINING_RECORD( Next, HEAP_FREE_ENTRY, FreeList );
    01936
    01937                         if (FreeBlock->Size >= AllocationIndex) {
    01938
    01939                             //
    01940                             //  We've found something that we can use so now remove
    01941                             //  it from the free list and go to where we treat spliting
    01942                             //  a free block.  Note that the block we found here might
    01943                             //  actually be the exact size we need and that is why
    01944                             //  in the split free block case we have to consider having
    01945                             //  nothing free after the split
    01946                             //
    01947
    01948                             RtlpFastRemoveNonDedicatedFreeBlock( Heap, FreeBlock );
    01949
    01950                             goto SplitFreeBlock;
    01951                         }
    01952
    01953                         Next = Next->Flink;
    01954                     }
    01955                 }
    01956             }
    01957
    01958             //
    01959             //  The [0] list is either empty or everything is too small
    01960             //  so now extend the heap which should get us something less
    01961             //  than or equal to the virtual memory threshold
    01962             //
    01963
    01964             FreeBlock = RtlpExtendHeap( Heap, AllocationSize );
    01965
    01966             //
    01967             //  And provided we got something we'll treat it just like the previous
    01968             //  split free block cases
    01969             //
    01970
    01971             if (FreeBlock != NULL) {
    01972
    01973                 RtlpFastRemoveNonDedicatedFreeBlock( Heap, FreeBlock );
    01974
    01975                 goto SplitFreeBlock;
    01976             }
    01977
    01978             //
    01979             //  We weren't able to extend the heap so we must be out of memory
    01980             //
    01981
    01982             Status = STATUS_NO_MEMORY;
    01983
    01984         //
    01985         //  At this point the allocation is way too big for any of the free lists
    01986         //  and we can only satisfy this request if the heap is growable
    01987         //
    01988
    01989         } else if (Heap->Flags & HEAP_GROWABLE) {
    01990
    01991             PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    01992
    01993             VirtualAllocBlock = NULL;
    01994
    01995             //
    01996             //  Compute how much memory we will need for this allocation which
    01997             //  will include the allocation size plus a header, and then go
    01998             //  get the committed memory
    01999             //
    02000
    02001             AllocationSize += FIELD_OFFSET( HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    02002
    02003             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    02004                                               (PVOID *)&VirtualAllocBlock,
    02005                                               0,
    02006                                               &AllocationSize,
    02007                                               MEM_COMMIT,
    02008                                               PAGE_READWRITE );
    02009
    02010             if (NT_SUCCESS(Status)) {
    02011
    02012                 //
    02013                 //  Just committed, already zero.  Fill in the new block
    02014                 //  and insert it in the list of big allocation
    02015                 //
    02016
    02017                 VirtualAllocBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size);
    02018                 VirtualAllocBlock->BusyBlock.Flags = HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT | HEAP_ENTRY_BUSY;
    02019                 VirtualAllocBlock->CommitSize = AllocationSize;
    02020                 VirtualAllocBlock->ReserveSize = AllocationSize;
    02021
    02022                 InsertTailList( &Heap->VirtualAllocdBlocks, (PLIST_ENTRY)VirtualAllocBlock );
    02023
    02024                 //
    02025                 //  Return the address of the user portion of the allocated block.
    02026                 //  This is the byte following the header.
    02027                 //
    02028
    02029                 ReturnValue = (PHEAP_ENTRY)(VirtualAllocBlock + 1);
    02030
    02031                 leave;
    02032             }
    02033
    02034         } else {
    02035
    02036             Status = STATUS_BUFFER_TOO_SMALL;
    02037         }
    02038
    02039         //
    02040         //  This is the error return.
    02041         //
    02042
    02043         if (Flags & HEAP_GENERATE_EXCEPTIONS) {
    02044
    02045             //
    02046             //  Construct an exception record.
    02047             //
    02048
    02049             ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
    02050             ExceptionRecord.ExceptionRecord = (PEXCEPTION_RECORD)NULL;
    02051             ExceptionRecord.NumberParameters = 1;
    02052             ExceptionRecord.ExceptionFlags = 0;
    02053             ExceptionRecord.ExceptionInformation[ 0 ] = AllocationSize;
    02054
    02055             RtlRaiseException( &ExceptionRecord );
    02056         }
    02057
    02058         SET_LAST_STATUS(Status);
    02059
    02060         ReturnValue = NULL;
    02061
    02062     } finally {
    02063
    02064         if (LockAcquired) {
    02065
    02066             RtlReleaseLockRoutine( Heap->LockVariable );
    02067         }
    02068     }
    02069
    02070     return ReturnValue;
    02071 }
    02072
    02073
    02074 PVOID
    02075 RtlAllocateHeapSlowly (
    02076     IN PVOID HeapHandle,
    02077     IN ULONG Flags,
    02078     IN SIZE_T Size
    02079     )
    02080
    02081 /*++
    02082
    02083 Routine Description:
    02084
    02085     This routine does the equivalent of Rtl Allocate Heap but it does it will
    02086     additional heap consistency checking logic and tagging.
    02087
    02088 Arguments:
    02089
    02090     HeapHandle - Supplies a pointer to an initialized heap structure
    02091
    02092     Flags - Specifies the set of flags to use to control the allocation
    02093
    02094     Size - Specifies the size, in bytes, of the allocation
    02095
    02096 Return Value:
    02097
    02098     PVOID - returns a pointer to the newly allocated block
    02099
    02100 --*/
    02101
    02102 {
    02103     PHEAP Heap = (PHEAP)HeapHandle;
    02104     BOOLEAN LockAcquired = FALSE;
    02105     PVOID ReturnValue = NULL;
    02106     PULONG FreeListsInUse;
    02107     ULONG FreeListsInUseUlong;
    02108     SIZE_T AllocationSize;
    02109     SIZE_T FreeSize, AllocationIndex;
    02110     UCHAR EntryFlags, FreeFlags;
    02111     PLIST_ENTRY FreeListHead, Next;
    02112     PHEAP_ENTRY BusyBlock;
    02113     PHEAP_FREE_ENTRY FreeBlock, SplitBlock, SplitBlock2;
    02114     PHEAP_ENTRY_EXTRA ExtraStuff;
    02115     NTSTATUS Status;
    02116     EXCEPTION_RECORD ExceptionRecord;
    02117     SIZE_T ZeroSize = 0;
    02118
    02119     RTL_PAGED_CODE();
    02120
    02121     //
    02122     //  Note that Flags has already been OR'd with Heap->ForceFlags.
    02123     //
    02124
    02125 #ifndef NTOS_KERNEL_RUNTIME
    02126
    02127     //
    02128     //  In the non kernel case check if we should be using the debug version
    02129     //  of heap allocation
    02130     //
    02131
    02132     if (DEBUG_HEAP( Flags )) {
    02133
    02134         return RtlDebugAllocateHeap( HeapHandle, Flags, Size );
    02135     }
    02136
    02137 #endif // NTOS_KERNEL_RUNTIME
    02138
    02139     //
    02140     //  If the size is greater than maxlong then say we can't allocate that
    02141     //  much and return the error to our caller
    02142     //
    02143
    02144     if (Size > 0x7fffffff) {
    02145
    02146         SET_LAST_STATUS( STATUS_NO_MEMORY );
    02147
    02148         return NULL;
    02149     }
    02150
    02151     //
    02152     //  Round up the requested size to the allocation granularity.  Note
    02153     //  that if the request is for zero bytes we will still allocate memory,
    02154     //
    02155     //      Allocation size will be either 16, 24, 32, ...
    02156     //      Allocation index will be 2, 3, 4, ...
    02157     //
    02158
    02159     AllocationSize = ((Size ? Size : 1) + Heap->AlignRound) & Heap->AlignMask;
    02160
    02161     //
    02162     //  Generate the flags needed for this heap entry.  Mark it busy and add
    02163     //  any user settable bits.  Also if the input flag indicates any entry
    02164     //  extra fields and we have a tag to use then make room for the extra
    02165     //  fields in the heap entry
    02166     //
    02167
    02168     EntryFlags = (UCHAR)(HEAP_ENTRY_BUSY | ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4));
    02169
    02170     if ((Flags & HEAP_NEED_EXTRA_FLAGS) || (Heap->PseudoTagEntries != NULL)) {
    02171
    02172         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
    02173         AllocationSize += sizeof( HEAP_ENTRY_EXTRA );
    02174     }
    02175
    02176     AllocationIndex = AllocationSize >> HEAP_GRANULARITY_SHIFT;
    02177
    02178     try {
    02179
    02180         //
    02181         //  Lock the free list.
    02182         //
    02183
    02184         if (!(Flags & HEAP_NO_SERIALIZE)) {
    02185
    02186             RtlAcquireLockRoutine( Heap->LockVariable );
    02187
    02188             LockAcquired = TRUE;
    02189         }
    02190
    02191         //
    02192         //  Do all the actual heap work under the protection of a try-except clause
    02193         //  to protect us from corruption
    02194         //
    02195
    02196         try {
    02197
    02198             //
    02199             //  If the allocation index is less than the maximum free list size
    02200             //  then we can use the index to check the free list otherwise we have
    02201             //  to either pull the entry off of the [0] index list or allocate
    02202             //  memory directly for this request.
    02203             //
    02204
    02205             if (AllocationIndex < HEAP_MAXIMUM_FREELISTS) {
    02206
    02207                 //
    02208                 //  With a size that matches a free list size grab the head
    02209                 //  of the list and check if there is an available entry
    02210                 //
    02211
    02212                 FreeListHead = &Heap->FreeLists[ AllocationIndex ];
    02213
    02214                 if ( !IsListEmpty( FreeListHead ))  {
    02215
    02216                     //
    02217                     //  We're in luck the list has an entry so now get the free
    02218                     //  entry,  copy its flags, remove it from the free list
    02219                     //
    02220
    02221                     FreeBlock = CONTAINING_RECORD( FreeListHead->Flink,
    02222                                                    HEAP_FREE_ENTRY,
    02223                                                    FreeList );
    02224
    02225                     FreeFlags = FreeBlock->Flags;
    02226
    02227                     RtlpRemoveFreeBlock( Heap, FreeBlock );
    02228
    02229                     //
    02230                     //  Adjust the total number of bytes free in the heap
    02231                     //
    02232
    02233                     Heap->TotalFreeSize -= AllocationIndex;
    02234
    02235                     //
    02236                     //  Mark the block as busy and and set the number of bytes
    02237                     //  unused and tag index.  Also if it is the last entry
    02238                     //  then keep that flag.
    02239                     //
    02240
    02241                     BusyBlock = (PHEAP_ENTRY)FreeBlock;
    02242                     BusyBlock->Flags = EntryFlags | (FreeFlags & HEAP_ENTRY_LAST_ENTRY);
    02243                     BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size);
    02244
    02245                 } else {
    02246
    02247                     //
    02248                     //  The free list that matches our request is empty.  We know
    02249                     //  that there are 128 free lists managed by a 4 ulong bitmap.
    02250                     //  The next big if-else-if statement will decide which ulong
    02251                     //  we tackle
    02252                     //
    02253                     //  Check if the requested allocation index within the first
    02254                     //  quarter of the free lists.
    02255                     //
    02256
    02257                     if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 1) / 4) {
    02258
    02259                         //
    02260                         //  Grab a pointer to the corresponding bitmap ulong, and
    02261                         //  then get the bit we're actually interested in to be the
    02262                         //  first bit of the ulong.
    02263                         //
    02264
    02265                         FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 0 ];
    02266                         FreeListsInUseUlong = *FreeListsInUse++ >> ((ULONG) AllocationIndex & 0x1F);
    02267
    02268                         //
    02269                         //  If the remaining bitmap has any bits set then we know
    02270                         //  there is a non empty list that is larger than our
    02271                         //  requested index so find that bit and compute the list
    02272                         //  head of the next non empty list
    02273                         //
    02274
    02275                         if (FreeListsInUseUlong) {
    02276
    02277                             FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02278
    02279                         } else {
    02280
    02281                             //
    02282                             //  The rest of the first ulong is all zeros so we need
    02283                             //  to move to the second ulong
    02284                             //
    02285
    02286                             FreeListsInUseUlong = *FreeListsInUse++;
    02287
    02288                             //
    02289                             //  Check if the second ulong has any bits set and if
    02290                             //  so then compute the list head of the next non empty
    02291                             //  list
    02292                             //
    02293
    02294                             if (FreeListsInUseUlong) {
    02295
    02296                                 FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) -
    02297                                     (AllocationIndex & 0x1F)  +
    02298                                     RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02299
    02300                             } else {
    02301
    02302                                 //
    02303                                 //  Do the same test for the third ulong
    02304                                 //
    02305
    02306                                 FreeListsInUseUlong = *FreeListsInUse++;
    02307
    02308                                 if (FreeListsInUseUlong) {
    02309
    02310                                     FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 2) / 4) -
    02311                                         (AllocationIndex & 0x1F) +
    02312                                         RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02313
    02314                                 } else {
    02315
    02316                                     //
    02317                                     //  Repeat the test for the forth ulong, and if
    02318                                     //  that one is also empty then we need to grab
    02319                                     //  the allocation off of the [0] index list
    02320                                     //
    02321
    02322                                     FreeListsInUseUlong = *FreeListsInUse++;
    02323
    02324                                     if (FreeListsInUseUlong) {
    02325
    02326                                         FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 3) / 4) -
    02327                                             (AllocationIndex & 0x1F)  +
    02328                                             RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02329
    02330                                     } else {
    02331
    02332                                         goto LookInNonDedicatedList;
    02333                                     }
    02334                                 }
    02335                             }
    02336                         }
    02337
    02338                     //
    02339                     //  Otherwise check if the requested allocation index lies
    02340                     //  within the second quarter of the free lists.  We repeat the
    02341                     //  test just like we did above on the second, third, and forth
    02342                     //  bitmap ulongs.
    02343                     //
    02344
    02345                     } else if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 2) / 4) {
    02346
    02347                         FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 1 ];
    02348                         FreeListsInUseUlong = *FreeListsInUse++ >> ((ULONG) AllocationIndex & 0x1F);
    02349
    02350                         if (FreeListsInUseUlong) {
    02351
    02352                             FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02353
    02354                         } else {
    02355
    02356                             FreeListsInUseUlong = *FreeListsInUse++;
    02357
    02358                             if (FreeListsInUseUlong) {
    02359
    02360                                 FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) -
    02361                                     (AllocationIndex & 0x1F)  +
    02362                                     RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02363
    02364                             } else {
    02365
    02366                                 FreeListsInUseUlong = *FreeListsInUse++;
    02367
    02368                                 if (FreeListsInUseUlong) {
    02369
    02370                                     FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 2) / 4) -
    02371                                         (AllocationIndex & 0x1F)  +
    02372                                         RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02373
    02374                                 } else {
    02375
    02376                                     goto LookInNonDedicatedList;
    02377                                 }
    02378                             }
    02379                         }
    02380
    02381                     //
    02382                     //  Otherwise check if the requested allocation index lies
    02383                     //  within the third quarter of the free lists. We repeat the
    02384                     //  test just like we did above on the third and forth bitmap
    02385                     //  ulongs
    02386                     //
    02387
    02388                     } else if (AllocationIndex < (HEAP_MAXIMUM_FREELISTS * 3) / 4) {
    02389
    02390                         FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 2 ];
    02391                         FreeListsInUseUlong = *FreeListsInUse++ >> ((ULONG) AllocationIndex & 0x1F);
    02392
    02393                         if (FreeListsInUseUlong) {
    02394
    02395                             FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02396
    02397                         } else {
    02398
    02399                             FreeListsInUseUlong = *FreeListsInUse++;
    02400
    02401                             if (FreeListsInUseUlong) {
    02402
    02403                                 FreeListHead += ((HEAP_MAXIMUM_FREELISTS * 1) / 4) -
    02404                                     (AllocationIndex & 0x1F)  +
    02405                                     RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02406
    02407                             } else {
    02408
    02409                                 goto LookInNonDedicatedList;
    02410                             }
    02411                         }
    02412
    02413                     //
    02414                     //  Lastly the requested allocation index must lie within the
    02415                     //  last quarter of the free lists.  We repeat the test just
    02416                     //  like we did above on the forth ulong
    02417                     //
    02418
    02419                     } else {
    02420
    02421                         FreeListsInUse = &Heap->u.FreeListsInUseUlong[ 3 ];
    02422                         FreeListsInUseUlong = *FreeListsInUse++ >> ((ULONG) AllocationIndex & 0x1F);
    02423
    02424                         if (FreeListsInUseUlong) {
    02425
    02426                             FreeListHead += RtlFindFirstSetRightMember( FreeListsInUseUlong );
    02427
    02428                         } else {
    02429
    02430                             goto LookInNonDedicatedList;
    02431                         }
    02432                     }
    02433
    02434                     //
    02435                     //  At this point the free list head points to a non empty free
    02436                     //  list that is of greater size than we need.
    02437                     //
    02438
    02439                     FreeBlock = CONTAINING_RECORD( FreeListHead->Flink,
    02440                                                    HEAP_FREE_ENTRY,
    02441                                                    FreeList );
    02442
    02443     SplitFreeBlock:
    02444
    02445                     //
    02446                     //  Remember the flags that go with this block and remove it
    02447                     //  from its list
    02448                     //
    02449
    02450                     FreeFlags = FreeBlock->Flags;
    02451
    02452                     RtlpRemoveFreeBlock( Heap, FreeBlock );
    02453
    02454                     //
    02455                     //  Adjust the amount free in the heap
    02456                     //
    02457
    02458                     Heap->TotalFreeSize -= FreeBlock->Size;
    02459
    02460                     //
    02461                     //  Mark the block busy
    02462                     //
    02463
    02464                     BusyBlock = (PHEAP_ENTRY)FreeBlock;
    02465                     BusyBlock->Flags = EntryFlags;
    02466
    02467                     //
    02468                     //  Compute the size (i.e., index) of the amount from this
    02469                     //  block that we don't need and can return to the free list
    02470                     //
    02471
    02472                     FreeSize = BusyBlock->Size - AllocationIndex;
    02473
    02474                     //
    02475                     //  Finish setting up the rest of the new busy block
    02476                     //
    02477
    02478                     BusyBlock->Size = (USHORT)AllocationIndex;
    02479                     BusyBlock->UnusedBytes = (UCHAR)(AllocationSize - Size);
    02480
    02481                     //
    02482                     //  Now if the size that we are going to free up is not zero
    02483                     //  then lets get to work and to the split.
    02484                     //
    02485
    02486                     if (FreeSize != 0) {
    02487
    02488                         //
    02489                         //  But first we won't ever bother doing a split that only
    02490                         //  gives us 8 bytes back.  So if free size is one then
    02491                         //  just bump up the size of the new busy block
    02492                         //
    02493
    02494                         if (FreeSize == 1) {
    02495
    02496                             BusyBlock->Size += 1;
    02497                             BusyBlock->UnusedBytes += sizeof( HEAP_ENTRY );
    02498
    02499                         } else {
    02500
    02501                             //
    02502                             //  Get a pointer to where the new free block will be.
    02503                             //  When we split a block the first part goes to the
    02504                             //  new busy block and the second part goes back to the
    02505                             //  free list
    02506                             //
    02507
    02508                             SplitBlock = (PHEAP_FREE_ENTRY)(BusyBlock + AllocationIndex);
    02509
    02510                             //
    02511                             //  Reset the flags that we copied from the original
    02512                             //  free list header, and set it other size fields.
    02513                             //
    02514
    02515                             SplitBlock->Flags = FreeFlags;
    02516                             SplitBlock->PreviousSize = (USHORT)AllocationIndex;
    02517                             SplitBlock->SegmentIndex = BusyBlock->SegmentIndex;
    02518                             SplitBlock->Size = (USHORT)FreeSize;
    02519
    02520                             //
    02521                             //  If nothing else follows this entry then we will
    02522                             //  insert this into the corresponding free list
    02523                             //
    02524
    02525                             if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) {
    02526
    02527                                 RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize );
    02528
    02529                                 Heap->TotalFreeSize += FreeSize;
    02530
    02531                             } else {
    02532
    02533                                 //
    02534                                 //  Otherwise we need to check the following block
    02535                                 //  and if it is busy then update its previous size
    02536                                 //  before inserting our new free block into the
    02537                                 //  free list
    02538                                 //
    02539
    02540                                 SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
    02541
    02542                                 if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) {
    02543
    02544                                     SplitBlock2->PreviousSize = (USHORT)FreeSize;
    02545
    02546                                     RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize );
    02547
    02548                                     Heap->TotalFreeSize += FreeSize;
    02549
    02550                                 } else {
    02551
    02552                                     //
    02553                                     //  The following block is free so we'll merge
    02554                                     //  these to blocks. by first merging the flags
    02555                                     //
    02556
    02557                                     SplitBlock->Flags = SplitBlock2->Flags;
    02558
    02559                                     //
    02560                                     //  Removing the second block from its free
    02561                                     //  list
    02562                                     //
    02563
    02564                                     RtlpRemoveFreeBlock( Heap, SplitBlock2 );
    02565
    02566                                     //
    02567                                     //  Updating the free total number of free
    02568                                     //  bytes in the heap and updating the size of
    02569                                     //  the new free block
    02570                                     //
    02571
    02572                                     Heap->TotalFreeSize -= SplitBlock2->Size;
    02573                                     FreeSize += SplitBlock2->Size;
    02574
    02575                                     //
    02576                                     //  If the new free block is still less than
    02577                                     //  the maximum heap block size then we'll
    02578                                     //  simply insert it back in the free list
    02579                                     //
    02580
    02581                                     if (FreeSize <= HEAP_MAXIMUM_BLOCK_SIZE) {
    02582
    02583                                         SplitBlock->Size = (USHORT)FreeSize;
    02584
    02585                                         //
    02586                                         //  Again check if the new following block
    02587                                         //  exists and if so then updsate is
    02588                                         //  previous size
    02589                                         //
    02590
    02591                                         if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    02592
    02593                                             ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
    02594                                         }
    02595
    02596                                         //
    02597                                         //  Insert the new free block into the free
    02598                                         //  list and update the free heap size
    02599                                         //
    02600
    02601                                         RtlpInsertFreeBlockDirect( Heap, SplitBlock, (USHORT)FreeSize );
    02602
    02603                                         Heap->TotalFreeSize += FreeSize;
    02604
    02605                                     } else {
    02606
    02607                                         //
    02608                                         //  The new free block is pretty large so
    02609                                         //  we need to call a private routine to do
    02610                                         //  the insert
    02611                                         //
    02612
    02613                                         RtlpInsertFreeBlock( Heap, SplitBlock, FreeSize );
    02614                                     }
    02615                                 }
    02616                             }
    02617
    02618                             //
    02619                             //  Now that free flags made it back into a free block
    02620                             //  we can zero out what we saved.
    02621                             //
    02622
    02623                             FreeFlags = 0;
    02624
    02625                             //
    02626                             //  If splitblock now last, update LastEntryInSegment
    02627                             //
    02628
    02629                             if (SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY) {
    02630
    02631                                 PHEAP_SEGMENT Segment;
    02632
    02633                                 Segment = Heap->Segments[SplitBlock->SegmentIndex];
    02634                                 Segment->LastEntryInSegment = (PHEAP_ENTRY)SplitBlock;
    02635                             }
    02636
    02637                         }
    02638                     }
    02639
    02640                     //
    02641                     //  If there are no following entries then mark the new block
    02642                     //  as such
    02643                     //
    02644
    02645                     if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) {
    02646
    02647                         BusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY;
    02648                     }
    02649                 }
    02650
    02651                 //
    02652                 //  Return the address of the user portion of the allocated block.
    02653                 //  This is the byte following the header.
    02654                 //
    02655
    02656                 ReturnValue = BusyBlock + 1;
    02657
    02658                 //
    02659                 //  If the flags indicate that we should zero memory then
    02660                 //  remember how much to zero.  We'll do the zeroing later
    02661                 //
    02662
    02663                 if (Flags & HEAP_ZERO_MEMORY) {
    02664
    02665                     ZeroSize = Size;
    02666
    02667                 //
    02668                 //  Otherwise if the flags indicate that we should fill heap then
    02669                 //  it it now.
    02670                 //
    02671
    02672                 } else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) {
    02673
    02674                     RtlFillMemoryUlong( (PCHAR)(BusyBlock + 1), Size & ~0x3, ALLOC_HEAP_FILL );
    02675                 }
    02676
    02677                 //
    02678                 //  If the flags indicate that we should do tail checking then copy
    02679                 //  the fill pattern right after the heap block.
    02680                 //
    02681
    02682                 if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) {
    02683
    02684                     RtlFillMemory( (PCHAR)ReturnValue + Size,
    02685                                    CHECK_HEAP_TAIL_SIZE,
    02686                                    CHECK_HEAP_TAIL_FILL );
    02687
    02688                     BusyBlock->Flags |= HEAP_ENTRY_FILL_PATTERN;
    02689                 }
    02690
    02691                 BusyBlock->SmallTagIndex = 0;
    02692
    02693                 //
    02694                 //  If the flags indicate that there is an extra block persent then
    02695                 //  we'll fill it in
    02696                 //
    02697
    02698                 if (BusyBlock->Flags & HEAP_ENTRY_EXTRA_PRESENT) {
    02699
    02700                     ExtraStuff = RtlpGetExtraStuffPointer( BusyBlock );
    02701
    02702                     RtlZeroMemory( ExtraStuff, sizeof( *ExtraStuff ));
    02703
    02704     #ifndef NTOS_KERNEL_RUNTIME
    02705
    02706                 //
    02707                 //  In the non kernel case the tagging goes in either the extra
    02708                 //  stuff of the busy block small tag index
    02709                 //
    02710
    02711                     if (IS_HEAP_TAGGING_ENABLED()) {
    02712
    02713                         ExtraStuff->TagIndex = RtlpUpdateTagEntry( Heap,
    02714                                                                    (USHORT)((Flags & HEAP_TAG_MASK) >> HEAP_TAG_SHIFT),
    02715                                                                    0,
    02716                                                                    BusyBlock->Size,
    02717                                                                    AllocationAction );
    02718                     }
    02719
    02720                 } else if (IS_HEAP_TAGGING_ENABLED()) {
    02721
    02722                     BusyBlock->SmallTagIndex = (UCHAR)RtlpUpdateTagEntry( Heap,
    02723                                                                           (USHORT)((Flags & HEAP_SMALL_TAG_MASK) >> HEAP_TAG_SHIFT),
    02724                                                                           0,
    02725                                                                           BusyBlock->Size,
    02726                                                                           AllocationAction );
    02727
    02728     #endif // NTOS_KERNEL_RUNTIME
    02729
    02730                 }
    02731
    02732                 //
    02733                 //  Return the address of the user portion of the allocated block.
    02734                 //  This is the byte following the header.
    02735                 //
    02736
    02737                 leave;
    02738
    02739             //
    02740             //  Otherwise the allocation request is bigger than the last dedicated
    02741             //  free list size.  Now check if the size is within our threshold.
    02742             //  Meaning that it could be in the [0] free list
    02743             //
    02744
    02745             } else if (AllocationIndex <= Heap->VirtualMemoryThreshold) {
    02746
    02747     LookInNonDedicatedList:
    02748
    02749                 //
    02750                 //  The following code cycles through the [0] free list until
    02751                 //  it finds a block that satisfies the request.  The list
    02752                 //  is sorted so the search is can be terminated early on success
    02753                 //
    02754
    02755                 FreeListHead = &Heap->FreeLists[ 0 ];
    02756                 Next = FreeListHead->Flink;
    02757
    02758                 while (FreeListHead != Next) {
    02759
    02760                     FreeBlock = CONTAINING_RECORD( Next, HEAP_FREE_ENTRY, FreeList );
    02761
    02762                     if (FreeBlock->Size >= AllocationIndex) {
    02763
    02764                         //
    02765                         //  We've found something that we can use so now go to
    02766                         //  where we treat spliting a free block.  Note that
    02767                         //  the block we found here might actually be the exact
    02768                         //  size we need and that is why in the split free block
    02769                         //  case we have to consider having nothing free after the
    02770                         //  split
    02771                         //
    02772
    02773                         goto SplitFreeBlock;
    02774
    02775                     } else {
    02776
    02777                         Next = Next->Flink;
    02778                     }
    02779                 }
    02780
    02781                 //
    02782                 //  The [0] list is either empty or everything is too small
    02783                 //  so now extend the heap which should get us something less
    02784                 //  than or equal to the virtual memory threshold
    02785                 //
    02786
    02787                 FreeBlock = RtlpExtendHeap( Heap, AllocationSize );
    02788
    02789                 //
    02790                 //  And provided we got something we'll treat it just like the
    02791                 //  previous split free block cases
    02792                 //
    02793
    02794                 if (FreeBlock != NULL) {
    02795
    02796                     goto SplitFreeBlock;
    02797                 }
    02798
    02799                 //
    02800                 //  We weren't able to extend the heap so we must be out of memory
    02801                 //
    02802
    02803                 Status = STATUS_NO_MEMORY;
    02804
    02805             //
    02806             //  At this point the allocation is way too big for any of the free
    02807             //  lists and we can only satisfy this request if the heap is growable
    02808             //
    02809
    02810             } else if (Heap->Flags & HEAP_GROWABLE) {
    02811
    02812                 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    02813
    02814                 VirtualAllocBlock = NULL;
    02815
    02816                 //
    02817                 //  Compute how much memory we will need for this allocation which
    02818                 //  will include the allocation size plus a header, and then go
    02819                 //  get the committed memory
    02820                 //
    02821
    02822                 AllocationSize += FIELD_OFFSET( HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    02823
    02824                 Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    02825                                                   (PVOID *)&VirtualAllocBlock,
    02826                                                   0,
    02827                                                   &AllocationSize,
    02828                                                   MEM_COMMIT,
    02829                                                   PAGE_READWRITE );
    02830
    02831                 if (NT_SUCCESS( Status )) {
    02832
    02833                     //
    02834                     //  Just committed, already zero.  Fill in the new block
    02835                     //  and insert it in the list of big allocation
    02836                     //
    02837
    02838                     VirtualAllocBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size);
    02839                     VirtualAllocBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT;
    02840                     VirtualAllocBlock->CommitSize = AllocationSize;
    02841                     VirtualAllocBlock->ReserveSize = AllocationSize;
    02842
    02843     #ifndef NTOS_KERNEL_RUNTIME
    02844
    02845                     //
    02846                     //  In the non kernel case see if we need to add heap tagging
    02847                     //
    02848
    02849                     if (IS_HEAP_TAGGING_ENABLED()) {
    02850
    02851                         VirtualAllocBlock->ExtraStuff.TagIndex =
    02852                             RtlpUpdateTagEntry( Heap,
    02853                                                 (USHORT)((Flags & HEAP_SMALL_TAG_MASK) >> HEAP_TAG_SHIFT),
    02854                                                 0,
    02855                                                 VirtualAllocBlock->CommitSize >> HEAP_GRANULARITY_SHIFT,
    02856                                                 VirtualAllocationAction );
    02857                     }
    02858
    02859     #endif // NTOS_KERNEL_RUNTIME
    02860
    02861                     InsertTailList( &Heap->VirtualAllocdBlocks, (PLIST_ENTRY)VirtualAllocBlock );
    02862
    02863                     //
    02864                     //  Return the address of the user portion of the allocated
    02865                     //  block.  This is the byte following the header.
    02866                     //
    02867
    02868                     ReturnValue = (PHEAP_ENTRY)(VirtualAllocBlock + 1);
    02869
    02870                     leave;
    02871                 }
    02872
    02873             //
    02874             //  Otherwise we have an error condition
    02875             //
    02876
    02877             } else {
    02878
    02879                 Status = STATUS_BUFFER_TOO_SMALL;
    02880             }
    02881
    02882             SET_LAST_STATUS( Status );
    02883
    02884             if (Flags & HEAP_GENERATE_EXCEPTIONS) {
    02885
    02886                 //
    02887                 //  Construct an exception record.
    02888                 //
    02889
    02890                 ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
    02891                 ExceptionRecord.ExceptionRecord = (PEXCEPTION_RECORD)NULL;
    02892                 ExceptionRecord.NumberParameters = 1;
    02893                 ExceptionRecord.ExceptionFlags = 0;
    02894                 ExceptionRecord.ExceptionInformation[ 0 ] = AllocationSize;
    02895
    02896                 RtlRaiseException( &ExceptionRecord );
    02897             }
    02898
    02899         } except( GetExceptionCode() == STATUS_NO_MEMORY ? EXCEPTION_CONTINUE_SEARCH :
    02900                                                            EXCEPTION_EXECUTE_HANDLER ) {
    02901
    02902             SET_LAST_STATUS( GetExceptionCode() );
    02903         }
    02904
    02905         //
    02906         //  Check if there is anything to zero out
    02907         //
    02908
    02909         if ( ZeroSize ) {
    02910
    02911             RtlZeroMemory( ReturnValue, ZeroSize );
    02912         }
    02913
    02914     } finally {
    02915
    02916         if (LockAcquired) {
    02917
    02918             RtlReleaseLockRoutine( Heap->LockVariable );
    02919         }
    02920     }
    02921
    02922     //
    02923     //  And return to our caller
    02924     //
    02925
    02926     return ReturnValue;
    02927 }
    02928
    02929
    02930 BOOLEAN
    02931 RtlFreeHeap (
    02932     IN PVOID HeapHandle,
    02933     IN ULONG Flags,
    02934     IN PVOID BaseAddress
    02935     )
    02936
    02937 /*++
    02938
    02939 Routine Description:
    02940
    02941     This routine returns a previously allocated block back to its heap
    02942
    02943 Arguments:
    02944
    02945     HeapHandle - Supplies a pointer to the owning heap structure
    02946
    02947     Flags - Specifies the set of flags to use in the deallocation
    02948
    02949     BaseAddress - Supplies a pointer to the block being freed
    02950
    02951 Return Value:
    02952
    02953     BOOLEAN - TRUE if the block was properly freed and FALSE otherwise
    02954
    02955 --*/
    02956
    02957 {
    02958     NTSTATUS Status;
    02959     PHEAP Heap = (PHEAP)HeapHandle;
    02960     PHEAP_ENTRY BusyBlock;
    02961     PHEAP_ENTRY_EXTRA ExtraStuff;
    02962     SIZE_T FreeSize;
    02963     BOOLEAN LockAcquired = FALSE;
    02964     BOOLEAN ReturnValue = TRUE;
    02965
    02966     RTL_PAGED_CODE();
    02967
    02968     //
    02969     //  First check if the address we're given is null and if so then
    02970     //  there is really nothing to do so just return success
    02971     //
    02972
    02973     if (BaseAddress == NULL) {
    02974
    02975         return TRUE;
    02976     }
    02977
    02978 #ifndef NTOS_KERNEL_RUNTIME
    02979 #ifdef NTHEAP_ENABLED
    02980     {
    02981         if (Heap->Flags & NTHEAP_ENABLED_FLAG) {
    02982
    02983             return RtlFreeNtHeap( HeapHandle,
    02984                                   Flags,
    02985                                   BaseAddress);
    02986         }
    02987     }
    02988 #endif // NTHEAP_ENABLED
    02989 #endif // NTOS_KERNEL_RUNTIME
    02990
    02991
    02992     //
    02993     //  Compliment the input flags with those enforced by the heap
    02994     //
    02995
    02996     Flags |= Heap->ForceFlags;
    02997
    02998     //
    02999     //  Now check if we should go the slow route
    03000     //
    03001
    03002     if (Flags & HEAP_SLOW_FLAGS) {
    03003
    03004         return RtlFreeHeapSlowly(HeapHandle, Flags, BaseAddress);
    03005     }
    03006
    03007     //
    03008     //  We can do everything in this routine. So now backup to get
    03009     //  a pointer to the start of the block
    03010     //
    03011
    03012     BusyBlock = (PHEAP_ENTRY)BaseAddress - 1;
    03013
    03014     //
    03015     //  Protect ourselves from idiots by refusing to free blocks
    03016     //  that do not have the busy bit set.
    03017     //
    03018     //  Also refuse to free blocks that are not eight-byte aligned.
    03019     //  The specific idiot in this case is Office95, which likes
    03020     //  to free a random pointer when you start Word95 from a desktop
    03021     //  shortcut.
    03022     //
    03023     //  As further insurance against idiots, check the segment index
    03024     //  to make sure it is less than HEAP_MAXIMUM_SEGMENTS (16). This
    03025     //  should fix all the dorks who have ASCII or Unicode where the
    03026     //  heap header is supposed to be.
    03027     //
    03028
    03029     try {
    03030         if ((!(BusyBlock->Flags & HEAP_ENTRY_BUSY)) ||
    03031             (((ULONG_PTR)BaseAddress & 0x7) != 0) ||
    03032             (BusyBlock->SegmentIndex >= HEAP_MAXIMUM_SEGMENTS)) {
    03033
    03034             //
    03035             //  Not a busy block, or it's not aligned or the segment is
    03036             //  to big, meaning it's corrupt
    03037             //
    03038
    03039             SET_LAST_STATUS( STATUS_INVALID_PARAMETER );
    03040
    03041             return FALSE;
    03042         }
    03043     } except(EXCEPTION_EXECUTE_HANDLER) {
    03044
    03045         SET_LAST_STATUS( STATUS_INVALID_PARAMETER );
    03046         return FALSE;
    03047     }
    03048
    03049     //
    03050     //  If there is a lookaside list and the block is not a big allocation
    03051     //  and the index is for a dedicated list then free the block to the
    03052     //  lookaside list.  We'll actually capture
    03053     //  the lookaside pointer from the heap and only use the captured pointer.
    03054     //  This will take care of the condition where a walk or lock heap can
    03055     //  cause us to check for a non null pointer and then have it become null
    03056     //  when we read it again.  If it is non null to start with then even if
    03057     //  the user walks or locks the heap via another thread the pointer to
    03058     //  still valid here so we can still try and do a lookaside list push
    03059     //
    03060
    03061 #ifndef NTOS_KERNEL_RUNTIME
    03062
    03063     {
    03064         PHEAP_LOOKASIDE Lookaside = (PHEAP_LOOKASIDE)Heap->Lookaside;
    03065
    03066         if ((Lookaside != NULL) &&
    03067             (Heap->LookasideLockCount == 0) &&
    03068             (!(BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)) &&
    03069             ((FreeSize = BusyBlock->Size) < HEAP_MAXIMUM_FREELISTS)) {
    03070
    03071             if (RtlpFreeToHeapLookaside( &Lookaside[FreeSize], BaseAddress)) {
    03072
    03073                 return TRUE;
    03074             }
    03075         }
    03076     }
    03077
    03078 #endif // NTOS_KERNEL_RUNTIME
    03079
    03080     try {
    03081
    03082         //
    03083         //  Check if we need to lock the heap
    03084         //
    03085
    03086         if (!(Flags & HEAP_NO_SERIALIZE)) {
    03087
    03088             RtlAcquireLockRoutine( Heap->LockVariable );
    03089
    03090             LockAcquired = TRUE;
    03091         }
    03092
    03093         //
    03094         //  Check if this is not a virtual block allocation meaning
    03095         //  that we it is part of the heap free list structure and not
    03096         //  one huge allocation that we got from vm
    03097         //
    03098
    03099         if (!(BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)) {
    03100
    03101             //
    03102             //  This block is not a big allocation so we need to
    03103             //  to get its size, and coalesce the blocks note that
    03104             //  the user mode heap does this conditionally on a heap
    03105             //  flag.  The coalesce function returns the newly formed
    03106             //  free block and the new size.
    03107             //
    03108
    03109             FreeSize = BusyBlock->Size;
    03110
    03111     #ifdef NTOS_KERNEL_RUNTIME
    03112
    03113             BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap,
    03114                                                              (PHEAP_FREE_ENTRY)BusyBlock,
    03115                                                              &FreeSize,
    03116                                                              FALSE );
    03117
    03118     #else // NTOS_KERNEL_RUNTIME
    03119
    03120             if (!(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)) {
    03121
    03122                 BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap,
    03123                                                                  (PHEAP_FREE_ENTRY)BusyBlock,
    03124                                                                  &FreeSize,
    03125                                                                  FALSE );
    03126             }
    03127
    03128     #endif // NTOS_KERNEL_RUNTIME
    03129
    03130             //
    03131             //  Check for a small allocation that can go on a freelist
    03132             //  first, these should never trigger a decommit.
    03133             //
    03134
    03135             HEAPASSERT(HEAP_MAXIMUM_FREELISTS < Heap->DeCommitFreeBlockThreshold);
    03136
    03137             //
    03138             //  If the allocation fits on a free list then insert it on
    03139             //  the appropriate free list.  If the block is not the last
    03140             //  entry then make sure that the next block knows our correct
    03141             //  size, and update the heap free space counter.
    03142             //
    03143
    03144             if (FreeSize < HEAP_MAXIMUM_FREELISTS) {
    03145
    03146                 RtlpFastInsertDedicatedFreeBlockDirect( Heap,
    03147                                                         (PHEAP_FREE_ENTRY)BusyBlock,
    03148                                                         (USHORT)FreeSize );
    03149
    03150                 if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    03151
    03152                     HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize);
    03153                 }
    03154
    03155                 Heap->TotalFreeSize += FreeSize;
    03156
    03157             //
    03158             //  Otherwise the block is to big for one of the dedicated free list so
    03159             //  see if the free size is under the decommit threshold by itself
    03160             //  or the total free in the heap is under the decomit threshold then
    03161             //  we'll put this into a free list
    03162             //
    03163
    03164             } else if ((FreeSize < Heap->DeCommitFreeBlockThreshold) ||
    03165                        ((Heap->TotalFreeSize + FreeSize) < Heap->DeCommitTotalFreeThreshold)) {
    03166
    03167                 //
    03168                 //  Check if the block can go into the [0] index free list, and if
    03169                 //  so then do the insert and make sure the following block is
    03170                 //  needed knows our correct size, and update the heaps free space
    03171                 //  counter
    03172                 //
    03173
    03174                 if (FreeSize <= (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) {
    03175
    03176                     RtlpFastInsertNonDedicatedFreeBlockDirect( Heap,
    03177                                                                (PHEAP_FREE_ENTRY)BusyBlock,
    03178                                                                (USHORT)FreeSize );
    03179
    03180                     if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    03181
    03182                         HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize);
    03183                     }
    03184
    03185                     Heap->TotalFreeSize += FreeSize;
    03186
    03187                 } else {
    03188
    03189                     //
    03190                     //  The block is too big to go on a free list in its
    03191                     //  entirety but we don't want to decommit anything so
    03192                     //  simply call a worker routine to hack up the block
    03193                     //  into pieces that will fit on the free lists.
    03194                     //
    03195
    03196                     RtlpInsertFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize );
    03197                 }
    03198
    03199             //
    03200             //  Otherwise the block is to big for any lists and we should decommit
    03201             //  the block
    03202             //
    03203
    03204             } else {
    03205
    03206                 RtlpDeCommitFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize );
    03207             }
    03208
    03209         } else {
    03210
    03211             //
    03212             //  This is a big virtual block allocation.  To free it we only have to
    03213             //  remove it from the heaps list of virtual allocated blocks, unlock
    03214             //  the heap, and return the block to vm
    03215             //
    03216
    03217             PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    03218
    03219             VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    03220
    03221             RemoveEntryList( &VirtualAllocBlock->Entry );
    03222
    03223             //
    03224             //  Release lock here as there is no reason to hold it across
    03225             //  the system call.
    03226             //
    03227
    03228             if (LockAcquired) {
    03229
    03230                 RtlReleaseLockRoutine( Heap->LockVariable );
    03231                 LockAcquired = FALSE;
    03232             }
    03233
    03234             FreeSize = 0;
    03235
    03236             Status = ZwFreeVirtualMemory( NtCurrentProcess(),
    03237                                           (PVOID *)&VirtualAllocBlock,
    03238                                           &FreeSize,
    03239                                           MEM_RELEASE );
    03240
    03241
    03242             //
    03243             //  Check if we had trouble freeing the block back to vm
    03244             //  and return an error if necessary
    03245             //
    03246
    03247             if (!NT_SUCCESS( Status )) {
    03248
    03249                 SET_LAST_STATUS( Status );
    03250
    03251                 ReturnValue = FALSE;
    03252             }
    03253         }
    03254
    03255     } finally {
    03256
    03257         if (LockAcquired) {
    03258
    03259             RtlReleaseLockRoutine( Heap->LockVariable );
    03260         }
    03261     }
    03262
    03263     //
    03264     //  The block was freed successfully so return success to our
    03265     //  caller
    03266     //
    03267
    03268     return ReturnValue;
    03269 }
    03270
    03271
    03272 BOOLEAN
    03273 RtlFreeHeapSlowly (
    03274     IN PVOID HeapHandle,
    03275     IN ULONG Flags,
    03276     IN PVOID BaseAddress
    03277     )
    03278
    03279 /*++
    03280
    03281 Routine Description:
    03282
    03283     This routine returns a previously allocated block back to its heap.
    03284     It is the slower version of Rtl Free Heap and does more checking and
    03285     tagging control.
    03286
    03287 Arguments:
    03288
    03289     HeapHandle - Supplies a pointer to the owning heap structure
    03290
    03291     Flags - Specifies the set of flags to use in the deallocation
    03292
    03293     BaseAddress - Supplies a pointer to the block being freed
    03294
    03295 Return Value:
    03296
    03297     BOOLEAN - TRUE if the block was properly freed and FALSE otherwise
    03298
    03299 --*/
    03300
    03301 {
    03302     NTSTATUS Status;
    03303     PHEAP Heap = (PHEAP)HeapHandle;
    03304     PHEAP_ENTRY BusyBlock;
    03305     PHEAP_ENTRY_EXTRA ExtraStuff;
    03306     SIZE_T FreeSize;
    03307     BOOLEAN Result;
    03308     BOOLEAN LockAcquired = FALSE;
    03309
    03310 #ifndef NTOS_KERNEL_RUNTIME
    03311
    03312     USHORT TagIndex;
    03313
    03314 #endif // NTOS_KERNEL_RUNTIME
    03315
    03316     RTL_PAGED_CODE();
    03317
    03318     //
    03319     //  Note that Flags has already been OR'd with Heap->ForceFlags.
    03320     //
    03321
    03322 #ifndef NTOS_KERNEL_RUNTIME
    03323
    03324     //
    03325     //  In the non kernel case see if we should be calling the debug version to
    03326     //  free the heap
    03327     //
    03328
    03329     if (DEBUG_HEAP( Flags )) {
    03330
    03331         return RtlDebugFreeHeap( HeapHandle, Flags, BaseAddress );
    03332     }
    03333
    03334 #endif // NTOS_KERNEL_RUNTIME
    03335
    03336     //
    03337     //  Until we figure out otherwise we'll assume that this call will fail
    03338     //
    03339
    03340     Result = FALSE;
    03341
    03342     try {
    03343
    03344         //
    03345         //  Lock the heap
    03346         //
    03347
    03348         if (!(Flags & HEAP_NO_SERIALIZE)) {
    03349
    03350             RtlAcquireLockRoutine( Heap->LockVariable );
    03351
    03352             LockAcquired = TRUE;
    03353         }
    03354
    03355         try {
    03356
    03357             //
    03358             //  Backup to get a pointer to the start of the block
    03359             //
    03360
    03361             BusyBlock = (PHEAP_ENTRY)BaseAddress - 1;
    03362
    03363             //
    03364             //  Protect ourselves from idiots by refusing to free blocks
    03365             //  that do not have the busy bit set.
    03366             //
    03367             //  Also refuse to free blocks that are not eight-byte aligned.
    03368             //  The specific idiot in this case is Office95, which likes
    03369             //  to free a random pointer when you start Word95 from a desktop
    03370             //  shortcut.
    03371             //
    03372             //  As further insurance against idiots, check the segment index
    03373             //  to make sure it is less than HEAP_MAXIMUM_SEGMENTS (16). This
    03374             //  should fix all the dorks who have ASCII or Unicode where the
    03375             //  heap header is supposed to be.
    03376             //
    03377             //  Note that this test is just opposite from the test used in
    03378             //  Rtl Free Heap
    03379             //
    03380
    03381             if ((BusyBlock->Flags & HEAP_ENTRY_BUSY) &&
    03382                 (((ULONG_PTR)BaseAddress & 0x7) == 0) &&
    03383                 (BusyBlock->SegmentIndex < HEAP_MAXIMUM_SEGMENTS)) {
    03384
    03385                 //
    03386                 //  Check if this is a virtual block allocation
    03387                 //
    03388
    03389                 if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) {
    03390
    03391                     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    03392
    03393                     //
    03394                     //  This is a big virtual block allocation.  To free it
    03395                     //  we only have to remove it from the heaps list of
    03396                     //  virtual allocated blocks, unlock the heap, and return
    03397                     //  the block to vm
    03398                     //
    03399
    03400                     VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    03401
    03402                     RemoveEntryList( &VirtualAllocBlock->Entry );
    03403
    03404     #ifndef NTOS_KERNEL_RUNTIME
    03405
    03406                     //
    03407                     //  In the non kernel case see if we need to free the tag
    03408                     //
    03409
    03410                     if (IS_HEAP_TAGGING_ENABLED()) {
    03411
    03412                         RtlpUpdateTagEntry( Heap,
    03413                                             VirtualAllocBlock->ExtraStuff.TagIndex,
    03414                                             VirtualAllocBlock->CommitSize >> HEAP_GRANULARITY_SHIFT,
    03415                                             0,
    03416                                             VirtualFreeAction );
    03417                     }
    03418
    03419     #endif // NTOS_KERNEL_RUNTIME
    03420
    03421                     FreeSize = 0;
    03422
    03423                     Status = ZwFreeVirtualMemory( NtCurrentProcess(),
    03424                                                   (PVOID *)&VirtualAllocBlock,
    03425                                                   &FreeSize,
    03426                                                   MEM_RELEASE );
    03427
    03428                     //
    03429                     //  Check if everything worked okay, if we had trouble freeing
    03430                     //  the block back to vm return an error if necessary,
    03431                     //
    03432
    03433                     if (NT_SUCCESS( Status )) {
    03434
    03435                         Result = TRUE;
    03436
    03437                     } else {
    03438
    03439                         SET_LAST_STATUS( Status );
    03440                     }
    03441
    03442                 } else {
    03443
    03444                     //
    03445                     //  This block is not a big allocation so we need to
    03446                     //  to get its size, and coalesce the blocks note that
    03447                     //  the user mode heap does this conditionally on a heap
    03448                     //  flag.  The coalesce function returns the newly formed
    03449                     //  free block and the new size.
    03450                     //
    03451
    03452     #ifndef NTOS_KERNEL_RUNTIME
    03453
    03454                     //
    03455                     //  First in the non kernel case remove any tagging we might
    03456                     //  have been using.  Note that the will either be in
    03457                     //  the heap header, or in the extra block if present
    03458                     //
    03459
    03460                     if (IS_HEAP_TAGGING_ENABLED()) {
    03461
    03462                         if (BusyBlock->Flags & HEAP_ENTRY_EXTRA_PRESENT) {
    03463
    03464                             ExtraStuff = (PHEAP_ENTRY_EXTRA)(BusyBlock + BusyBlock->Size - 1);
    03465
    03466                             TagIndex = RtlpUpdateTagEntry( Heap,
    03467                                                            ExtraStuff->TagIndex,
    03468                                                            BusyBlock->Size,
    03469                                                            0,
    03470                                                            FreeAction );
    03471
    03472                         } else {
    03473
    03474                             TagIndex = RtlpUpdateTagEntry( Heap,
    03475                                                            BusyBlock->SmallTagIndex,
    03476                                                            BusyBlock->Size,
    03477                                                            0,
    03478                                                            FreeAction );
    03479                         }
    03480
    03481                     } else {
    03482
    03483                         TagIndex = 0;
    03484                     }
    03485
    03486     #endif // NTOS_KERNEL_RUNTIME
    03487
    03488                     //
    03489                     //  This is the size of the block we are freeing
    03490                     //
    03491
    03492                     FreeSize = BusyBlock->Size;
    03493
    03494     #ifndef NTOS_KERNEL_RUNTIME
    03495
    03496                     //
    03497                     //  In the non kernel case see if we should coalesce on free
    03498                     //
    03499
    03500                     if (!(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)) {
    03501
    03502     #endif // NTOS_KERNEL_RUNTIME
    03503
    03504                         //
    03505                         //  In kernel case and in the tested user mode case we
    03506                         //  now coalesce free blocks
    03507                         //
    03508
    03509                         BusyBlock = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks( Heap, (PHEAP_FREE_ENTRY)BusyBlock, &FreeSize, FALSE );
    03510
    03511     #ifndef NTOS_KERNEL_RUNTIME
    03512
    03513                     }
    03514
    03515     #endif // NTOS_KERNEL_RUNTIME
    03516
    03517                     //
    03518                     //  If the block should not be decommit then try and put it
    03519                     //  on a free list
    03520                     //
    03521
    03522                     if ((FreeSize < Heap->DeCommitFreeBlockThreshold) ||
    03523                         ((Heap->TotalFreeSize + FreeSize) < Heap->DeCommitTotalFreeThreshold)) {
    03524
    03525                         //
    03526                         //  Check if the block can fit on one of the dedicated free
    03527                         //  lists
    03528                         //
    03529
    03530                         if (FreeSize <= (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) {
    03531
    03532                             //
    03533                             //  It can fit on a dedicated free list so insert it on
    03534                             //
    03535
    03536                             RtlpInsertFreeBlockDirect( Heap, (PHEAP_FREE_ENTRY)BusyBlock, (USHORT)FreeSize );
    03537
    03538                             //
    03539                             //  If there is a following entry then make sure the
    03540                             //  sizes agree
    03541                             //
    03542
    03543                             if (!(BusyBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    03544
    03545                                 HEAPASSERT((BusyBlock + FreeSize)->PreviousSize == (USHORT)FreeSize);
    03546                             }
    03547
    03548                             //
    03549                             //  Update the heap with the amount of free space
    03550                             //  available
    03551                             //
    03552
    03553                             Heap->TotalFreeSize += FreeSize;
    03554
    03555                         } else {
    03556
    03557                             //
    03558                             //  The block goes on the non dedicated free list
    03559                             //
    03560
    03561                             RtlpInsertFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize );
    03562                         }
    03563
    03564     #ifndef NTOS_KERNEL_RUNTIME
    03565
    03566                         //
    03567                         //  In the non kernel case see if the there was tag and if
    03568                         //  so then update the entry to show that it's been freed
    03569                         //
    03570
    03571                         if (TagIndex != 0) {
    03572
    03573                             PHEAP_FREE_ENTRY_EXTRA FreeExtra;
    03574
    03575                             BusyBlock->Flags |= HEAP_ENTRY_EXTRA_PRESENT;
    03576
    03577                             FreeExtra = (PHEAP_FREE_ENTRY_EXTRA)(BusyBlock + BusyBlock->Size) - 1;
    03578
    03579                             FreeExtra->TagIndex = TagIndex;
    03580                             FreeExtra->FreeBackTraceIndex = 0;
    03581
    03582     #if i386
    03583
    03584                             //
    03585                             //  In the x86 case we can also capture the stack
    03586                             //  backtrace
    03587                             //
    03588
    03589                             if (Heap->Flags & HEAP_CAPTURE_STACK_BACKTRACES) {
    03590
    03591                                 FreeExtra->FreeBackTraceIndex = (USHORT)RtlLogStackBackTrace();
    03592                             }
    03593
    03594     #endif // i386
    03595
    03596                         }
    03597
    03598     #endif // NTOS_KERNEL_RUNTIME
    03599
    03600                     } else {
    03601
    03602                         //
    03603                         //  Otherwise the block is big enough to decommit so have a
    03604                         //  worker routine to do the decommit
    03605                         //
    03606
    03607                         RtlpDeCommitFreeBlock( Heap, (PHEAP_FREE_ENTRY)BusyBlock, FreeSize );
    03608                     }
    03609
    03610                     //
    03611                     //  And say the free worked fine
    03612                     //
    03613
    03614                     Result = TRUE;
    03615                 }
    03616
    03617             } else {
    03618
    03619                 //
    03620                 //  Not a busy block, or it's not aligned or the segment is
    03621                 //  to big, meaning it's corrupt
    03622                 //
    03623
    03624                 SET_LAST_STATUS( STATUS_INVALID_PARAMETER );
    03625             }
    03626
    03627         } except( EXCEPTION_EXECUTE_HANDLER ) {
    03628
    03629             SET_LAST_STATUS( GetExceptionCode() );
    03630
    03631             Result = FALSE;
    03632         }
    03633
    03634     } finally {
    03635
    03636         //
    03637         //  Unlock the heap
    03638         //
    03639
    03640         if (LockAcquired) {
    03641
    03642             RtlReleaseLockRoutine( Heap->LockVariable );
    03643         }
    03644     }
    03645
    03646     //
    03647     //  And return to our caller
    03648     //
    03649
    03650     return Result;
    03651 }
    03652
    03653
    03654 SIZE_T
    03655 RtlSizeHeap (
    03656     IN PVOID HeapHandle,
    03657     IN ULONG Flags,
    03658     IN PVOID BaseAddress
    03659     )
    03660
    03661 /*++
    03662
    03663 Routine Description:
    03664
    03665     This routine returns the size, in bytes, of the indicated block
    03666     of heap storage.  The size only includes the number of bytes the
    03667     original caller used to allocate the block and not any unused
    03668     bytes at the end of the block.
    03669
    03670 Arguments:
    03671
    03672     HeapHandle - Supplies a pointer to the heap that owns the block
    03673         being queried
    03674
    03675     Flags - Supplies a set of flags used to allocate the block
    03676
    03677     BaseAddress - Supplies the address of the block being queried
    03678
    03679 Return Value:
    03680
    03681     SIZE_T - returns the size, in bytes, of the queried block, or -1
    03682         if the block is not in use.
    03683
    03684 --*/
    03685
    03686 {
    03687     PHEAP Heap = (PHEAP)HeapHandle;
    03688     PHEAP_ENTRY BusyBlock;
    03689     SIZE_T BusySize;
    03690
    03691     //
    03692     //  Compliment the input flags with those enforced by the heap
    03693     //
    03694
    03695     Flags |= Heap->ForceFlags;
    03696
    03697     //
    03698     //  Check if this is the nonkernel debug version of heap
    03699     //
    03700
    03701 #ifndef NTOS_KERNEL_RUNTIME
    03702
    03703     if (DEBUG_HEAP( Flags )) {
    03704
    03705         return RtlDebugSizeHeap( HeapHandle, Flags, BaseAddress );
    03706     }
    03707
    03708 #endif // NTOS_KERNEL_RUNTIME
    03709
    03710     //
    03711     //  No lock is required since nothing is modified and nothing
    03712     //  outside the busy block is read.  Backup to get a pointer
    03713     //  to the heap entry
    03714     //
    03715
    03716     BusyBlock = (PHEAP_ENTRY)BaseAddress - 1;
    03717
    03718     //
    03719     //  If the block is not in use then the answer is -1 and
    03720     //  we'll set the error status for the user mode thread
    03721     //
    03722
    03723     if (!(BusyBlock->Flags & HEAP_ENTRY_BUSY)) {
    03724
    03725         BusySize = -1;
    03726
    03727         SET_LAST_STATUS( STATUS_INVALID_PARAMETER );
    03728
    03729     //
    03730     //  Otherwise if the block is from our large allocation then
    03731     //  we'll get the result from that routine
    03732     //
    03733
    03734     } else if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) {
    03735
    03736         BusySize = RtlpGetSizeOfBigBlock( BusyBlock );
    03737
    03738     //
    03739     //  Otherwise the block must be one that we can handle so
    03740     //  calculate its block size and then subtract what's not being
    03741     //  used by the caller.
    03742     //
    03743     //  **** this seems to include the heap entry header in its
    03744     //  **** calculation.  Is that what we really want?
    03745     //
    03746
    03747     } else {
    03748
    03749         BusySize = (BusyBlock->Size << HEAP_GRANULARITY_SHIFT) -
    03750                    BusyBlock->UnusedBytes;
    03751     }
    03752
    03753     //
    03754     //  And return to our caller
    03755     //
    03756
    03757     return BusySize;
    03758 }
    03759
    03760
    03761 NTSTATUS
    03762 RtlZeroHeap (
    03763     IN PVOID HeapHandle,
    03764     IN ULONG Flags
    03765     )
    03766
    03767 /*++
    03768
    03769 Routine Description:
    03770
    03771     This routine zero's (or fills) in all the free blocks in a heap.
    03772     It does not touch big allocations.
    03773
    03774 Arguments:
    03775
    03776     HeapHandle - Supplies a pointer to the heap being zeroed
    03777
    03778     Flags - Supplies a set of heap flags to compliment those already
    03779         set in the heap
    03780
    03781 Return Value:
    03782
    03783     NTSTATUS - An appropriate status code
    03784
    03785 --*/
    03786
    03787 {
    03788     PHEAP Heap = (PHEAP)HeapHandle;
    03789     NTSTATUS Status;
    03790     BOOLEAN LockAcquired = FALSE;
    03791     PHEAP_SEGMENT Segment;
    03792     ULONG SegmentIndex;
    03793     PHEAP_ENTRY CurrentBlock;
    03794     PHEAP_FREE_ENTRY FreeBlock;
    03795     SIZE_T Size;
    03796     PHEAP_UNCOMMMTTED_RANGE UnCommittedRange;
    03797
    03798     RTL_PAGED_CODE();
    03799
    03800     //
    03801     //  Compliment the input flags with those enforced by the heap
    03802     //
    03803
    03804     Flags |= Heap->ForceFlags;
    03805
    03806     //
    03807     //  Check if this is the nonkernel debug version of heap
    03808     //
    03809
    03810 #ifndef NTOS_KERNEL_RUNTIME
    03811
    03812     if (DEBUG_HEAP( Flags )) {
    03813
    03814         return RtlDebugZeroHeap( HeapHandle, Flags );
    03815     }
    03816
    03817 #endif // NTOS_KERNEL_RUNTIME
    03818
    03819     //
    03820     //  Unless something happens otherwise we'll assume that we'll
    03821     //  be successful
    03822     //
    03823
    03824     Status = STATUS_SUCCESS;
    03825
    03826     try {
    03827
    03828         //
    03829         //  Lock the heap
    03830         //
    03831
    03832         if (!(Flags & HEAP_NO_SERIALIZE)) {
    03833
    03834             RtlAcquireLockRoutine( Heap->LockVariable );
    03835
    03836             LockAcquired = TRUE;
    03837         }
    03838
    03839         try {
    03840
    03841             //
    03842             //  Zero fill all the free blocks in all the segements
    03843             //
    03844
    03845             for (SegmentIndex=0; SegmentIndex<HEAP_MAXIMUM_SEGMENTS; SegmentIndex++) {
    03846
    03847                 Segment = Heap->Segments[ SegmentIndex ];
    03848
    03849                 if (!Segment) {
    03850
    03851                     continue;
    03852                 }
    03853
    03854                 UnCommittedRange = Segment->UnCommittedRanges;
    03855                 CurrentBlock = Segment->FirstEntry;
    03856
    03857                 //
    03858                 //  With the current segment we'll zoom through the
    03859                 //  blocks until we reach the end
    03860                 //
    03861
    03862                 while (CurrentBlock < Segment->LastValidEntry) {
    03863
    03864                     Size = CurrentBlock->Size << HEAP_GRANULARITY_SHIFT;
    03865
    03866                     //
    03867                     //  If the block is not in use then we'll either zero
    03868                     //  it or fill it.
    03869                     //
    03870
    03871                     if (!(CurrentBlock->Flags & HEAP_ENTRY_BUSY)) {
    03872
    03873                         FreeBlock = (PHEAP_FREE_ENTRY)CurrentBlock;
    03874
    03875                         if ((Heap->Flags & HEAP_FREE_CHECKING_ENABLED) &&
    03876                             (CurrentBlock->Flags & HEAP_ENTRY_FILL_PATTERN)) {
    03877
    03878                             RtlFillMemoryUlong( FreeBlock + 1,
    03879                                                 Size - sizeof( *FreeBlock ),
    03880                                                 FREE_HEAP_FILL );
    03881
    03882                         } else {
    03883
    03884                             RtlFillMemoryUlong( FreeBlock + 1,
    03885                                                 Size - sizeof( *FreeBlock ),
    03886                                                 0 );
    03887                         }
    03888                     }
    03889
    03890                     //
    03891                     //  If the following entry is uncommited then we need to
    03892                     //  skip over it.  This code strongly implies that the
    03893                     //  uncommitted range list is in perfect sync with the
    03894                     //  blocks in the segement
    03895                     //
    03896
    03897                     if (CurrentBlock->Flags & HEAP_ENTRY_LAST_ENTRY) {
    03898
    03899                         CurrentBlock += CurrentBlock->Size;
    03900
    03901                         //
    03902                         //  Check if the we've reached the end of the segment
    03903                         //  and should just break out of the while loop
    03904                         //
    03905                         //
    03906                         //  **** "break;" would probably be more clear here
    03907                         //
    03908
    03909                         if (UnCommittedRange == NULL) {
    03910
    03911                             CurrentBlock = Segment->LastValidEntry;
    03912
    03913                         //
    03914                         //  Otherwise skip over the uncommitted range
    03915                         //
    03916
    03917                         } else {
    03918
    03919                             CurrentBlock = (PHEAP_ENTRY)
    03920                                 ((PCHAR)UnCommittedRange->Address + UnCommittedRange->Size);
    03921
    03922                             UnCommittedRange = UnCommittedRange->Next;
    03923                         }
    03924
    03925                     //
    03926                     //  Otherwise the next block exists so advance to it
    03927                     //
    03928
    03929                     } else {
    03930
    03931                         CurrentBlock += CurrentBlock->Size;
    03932                     }
    03933                 }
    03934             }
    03935
    03936         } except( EXCEPTION_EXECUTE_HANDLER ) {
    03937
    03938             Status = GetExceptionCode();
    03939         }
    03940
    03941     } finally {
    03942
    03943         //
    03944         //  Unlock the heap
    03945         //
    03946
    03947         if (LockAcquired) {
    03948
    03949             RtlReleaseLockRoutine( Heap->LockVariable );
    03950         }
    03951     }
    03952
    03953     return Status;
    03954 }
    03955
    03956
    03957 //
    03958 //  Local Support Routine
    03959 //
    03960
    03961 PHEAP_UNCOMMMTTED_RANGE
    03962 RtlpCreateUnCommittedRange (
    03963     IN PHEAP_SEGMENT Segment
    03964     )
    03965
    03966 /*++
    03967
    03968 Routine Description:
    03969
    03970     This routine add a new uncommitted range structure to the specified heap
    03971     segment.  This routine works by essentially doing a pop of the stack of
    03972     unused uncommitted range structures located off the heap structure.  If
    03973     the stack is empty then we'll create some more before doing the pop.
    03974
    03975 Arguments:
    03976
    03977     Segment - Supplies the heap segment being modified
    03978
    03979 Return Value:
    03980
    03981     PHEAP_UNCOMMITTED_RANGE - returns a pointer to the newly created
    03982         uncommitted range structure
    03983
    03984 --*/
    03985
    03986 {
    03987     NTSTATUS Status;
    03988     PVOID FirstEntry, LastEntry;
    03989     PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp;
    03990     SIZE_T ReserveSize, CommitSize;
    03991     PHEAP_UCR_SEGMENT UCRSegment;
    03992
    03993     RTL_PAGED_CODE();
    03994
    03995     //
    03996     //  Get a pointer to the unused uncommitted range structures for
    03997     //  the specified heap
    03998     //
    03999
    04000     pp = &Segment->Heap->UnusedUnCommittedRanges;
    04001
    04002     //
    04003     //  If the list is null then we need to allocate some more to
    04004     //  put on the list
    04005     //
    04006
    04007     if (*pp == NULL) {
    04008
    04009         //
    04010         //  Get the next uncommitted range segment from the heap
    04011         //
    04012
    04013         UCRSegment = Segment->Heap->UCRSegments;
    04014
    04015         //
    04016         //  If there are no more uncommitted range segments or
    04017         //  the segemtns commited and reserved sizes are equal (meaning
    04018         //  it's all used up) then we need to allocate another uncommitted
    04019         //  range segment
    04020         //
    04021
    04022         if ((UCRSegment == NULL) ||
    04023             (UCRSegment->CommittedSize == UCRSegment->ReservedSize)) {
    04024
    04025             //
    04026             //  We'll reserve 16 pages of memory and commit at this
    04027             //  time one page of it.
    04028             //
    04029
    04030             ReserveSize = PAGE_SIZE * 16;
    04031             UCRSegment = NULL;
    04032
    04033             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    04034                                               &UCRSegment,
    04035                                               0,
    04036                                               &ReserveSize,
    04037                                               MEM_RESERVE,
    04038                                               PAGE_READWRITE );
    04039
    04040             if (!NT_SUCCESS( Status )) {
    04041
    04042                 return NULL;
    04043             }
    04044
    04045             CommitSize = PAGE_SIZE;
    04046
    04047             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    04048                                               &UCRSegment,
    04049                                               0,
    04050                                               &CommitSize,
    04051                                               MEM_COMMIT,
    04052                                               PAGE_READWRITE );
    04053
    04054             if (!NT_SUCCESS( Status )) {
    04055
    04056                 ZwFreeVirtualMemory( NtCurrentProcess(),
    04057                                      &UCRSegment,
    04058                                      &ReserveSize,
    04059                                      MEM_RELEASE );
    04060
    04061                 return NULL;
    04062             }
    04063
    04064             //
    04065             //  Add this new segment to the front of the UCR segments
    04066             //
    04067
    04068             UCRSegment->Next = Segment->Heap->UCRSegments;
    04069             Segment->Heap->UCRSegments = UCRSegment;
    04070
    04071             //
    04072             //  Set the segments commit and reserve size
    04073             //
    04074
    04075             UCRSegment->ReservedSize = ReserveSize;
    04076             UCRSegment->CommittedSize = CommitSize;
    04077
    04078             //
    04079             //  Point to the first free spot in the segment
    04080             //
    04081
    04082             FirstEntry = (PCHAR)(UCRSegment + 1);
    04083
    04084         } else {
    04085
    04086             //
    04087             //  We have an existing UCR segment with available space
    04088             //  So now try and commit another PAGE_SIZE bytes.  When we are done
    04089             //  FirstEntry will point to the newly committed space
    04090             //
    04091
    04092             CommitSize = PAGE_SIZE;
    04093             FirstEntry = (PCHAR)UCRSegment + UCRSegment->CommittedSize;
    04094
    04095             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    04096                                               &FirstEntry,
    04097                                               0,
    04098                                               &CommitSize,
    04099                                               MEM_COMMIT,
    04100                                               PAGE_READWRITE );
    04101
    04102             if (!NT_SUCCESS( Status )) {
    04103
    04104                 return NULL;
    04105             }
    04106
    04107             //
    04108             //  And update the amount committed in the segment
    04109             //
    04110
    04111             UCRSegment->CommittedSize += CommitSize;
    04112         }
    04113
    04114         //
    04115         //  At this point UCR segment exists and First Entry points to the
    04116         //  start of the available committed space.  We'll make Last Entry
    04117         //  point to the end of the committed space
    04118         //
    04119
    04120         LastEntry = (PCHAR)UCRSegment + UCRSegment->CommittedSize;
    04121
    04122         //
    04123         //  Now the task is to push all of this new space unto the
    04124         //  unused uncommitted range list off the heap, then we can
    04125         //  do a regular pop
    04126         //
    04127
    04128         UnCommittedRange = (PHEAP_UNCOMMMTTED_RANGE)FirstEntry;
    04129
    04130         pp = &Segment->Heap->UnusedUnCommittedRanges;
    04131
    04132         while ((PCHAR)UnCommittedRange < (PCHAR)LastEntry) {
    04133
    04134             *pp = UnCommittedRange;
    04135             pp = &UnCommittedRange->Next;
    04136             UnCommittedRange += 1;
    04137         }
    04138
    04139         //
    04140         //  Null terminate the list
    04141         //
    04142
    04143         *pp = NULL;
    04144
    04145         //
    04146         //  And have Pp point the new top of the list
    04147         //
    04148
    04149         pp = &Segment->Heap->UnusedUnCommittedRanges;
    04150     }
    04151
    04152     //
    04153     //  At this point the Pp points to a non empty list of unused uncommitted
    04154     //  range structures.  So we pop the list and return the top to our caller
    04155     //
    04156
    04157     UnCommittedRange = *pp;
    04158     *pp = UnCommittedRange->Next;
    04159
    04160     return UnCommittedRange;
    04161 }
    04162
    04163
    04164 //
    04165 //  Local Support Routine
    04166 //
    04167
    04168 VOID
    04169 RtlpDestroyUnCommittedRange (
    04170     IN PHEAP_SEGMENT Segment,
    04171     IN PHEAP_UNCOMMMTTED_RANGE UnCommittedRange
    04172     )
    04173
    04174 /*++
    04175
    04176 Routine Description:
    04177
    04178     This routine returns an uncommitted range structure back to the unused
    04179     uncommitted range list
    04180
    04181 Arguments:
    04182
    04183     Segment - Supplies any segment in the heap being modified.  Most likely but
    04184         not necessarily the segment containing the uncommitted range structure
    04185
    04186     UnCommittedRange - Supplies a pointer to the uncommitted range structure
    04187         being decommissioned.
    04188
    04189 Return Value:
    04190
    04191     None.
    04192
    04193 --*/
    04194
    04195 {
    04196     RTL_PAGED_CODE();
    04197
    04198     //
    04199     //  This routine simply does a "push" of the uncommitted range structure
    04200     //  onto the heap's stack of unused uncommitted ranges
    04201     //
    04202
    04203     UnCommittedRange->Next = Segment->Heap->UnusedUnCommittedRanges;
    04204     Segment->Heap->UnusedUnCommittedRanges = UnCommittedRange;
    04205
    04206     //
    04207     //  For safety sake we'll also zero out the fields in the decommissioned
    04208     //  structure
    04209     //
    04210
    04211     UnCommittedRange->Address = 0;
    04212     UnCommittedRange->Size = 0;
    04213
    04214     //
    04215     //  And return to our caller
    04216     //
    04217
    04218     return;
    04219 }
    04220
    04221
    04222 //
    04223 //  Local Support Routine
    04224 //
    04225
    04226 VOID
    04227 RtlpInsertUnCommittedPages (
    04228     IN PHEAP_SEGMENT Segment,
    04229     IN ULONG_PTR Address,
    04230     IN SIZE_T Size
    04231     )
    04232
    04233 /*++
    04234
    04235 Routine Description:
    04236
    04237     This routine adds the specified range to the list of uncommitted pages
    04238     in the segment.  When done the information will hang off the segments
    04239     uncommitted ranges list.
    04240
    04241 Arguments:
    04242
    04243     Segment - Supplies a segment whose uncommitted range is being modified
    04244
    04245     Address - Supplies the base (start) address for the uncommitted range
    04246
    04247     Size - Supplies the size, in bytes, of the uncommitted range
    04248
    04249 Return Value:
    04250
    04251     None.
    04252
    04253 --*/
    04254
    04255 {
    04256     PHEAP_UNCOMMMTTED_RANGE UnCommittedRange, *pp;
    04257
    04258     RTL_PAGED_CODE();
    04259
    04260     //
    04261     //  Get a pointer to the front of the segments uncommitted range list
    04262     //  The list is sorted by ascending address
    04263     //
    04264
    04265     pp = &Segment->UnCommittedRanges;
    04266
    04267     //
    04268     //  While we haven't reached the end of the list we'll zoom through
    04269     //  trying to find a fit
    04270     //
    04271
    04272     while (UnCommittedRange = *pp) {
    04273
    04274         //
    04275         //  If address we want is less than what we're pointing at then
    04276         //  we've found where this new entry goes
    04277         //
    04278
    04279         if (UnCommittedRange->Address > Address) {
    04280
    04281             //
    04282             //  If the new block matches right up to the existing block
    04283             //  then we can simply backup the existing block and add
    04284             //  to its size
    04285             //
    04286
    04287             if ((Address + Size) == UnCommittedRange->Address) {
    04288
    04289                 UnCommittedRange->Address = Address;
    04290                 UnCommittedRange->Size += Size;
    04291
    04292                 //
    04293                 //  Check if we need to update our notion of what the
    04294                 //  largest uncommitted range is
    04295                 //
    04296
    04297                 if (UnCommittedRange->Size > Segment->LargestUnCommittedRange) {
    04298
    04299                     Segment->LargestUnCommittedRange = UnCommittedRange->Size;
    04300                 }
    04301
    04302                 //
    04303                 //  And return to our caller
    04304                 //
    04305
    04306                 return;
    04307             }
    04308
    04309             //
    04310             //  Pp is the address of the block right before us, and *Pp is the
    04311             //  address of the block right after us.  So now fall out to where
    04312             //  the insertion takes place.
    04313             //
    04314
    04315             break;
    04316
    04317         //
    04318         //  Otherwise if this existing block stops right where the new block
    04319         //  starts then we get to modify this entry.
    04320         //
    04321
    04322         } else if ((UnCommittedRange->Address + UnCommittedRange->Size) == Address) {
    04323
    04324             //
    04325             //  Remember the starting address and compute the new larger size
    04326             //
    04327
    04328             Address = UnCommittedRange->Address;
    04329             Size += UnCommittedRange->Size;
    04330
    04331             //
    04332             //  Remove this entry from the list and then return it to the
    04333             //  unused uncommitted list
    04334             //
    04335
    04336             *pp = UnCommittedRange->Next;
    04337
    04338             RtlpDestroyUnCommittedRange( Segment, UnCommittedRange );
    04339
    04340             //
    04341             //  Modify the segemnt counters and largest size state.  The next
    04342             //  time through the loop should hit the first case above where
    04343             //  we'll either merge with a list following us or add a new
    04344             //  entry
    04345             //
    04346
    04347             Segment->NumberOfUnCommittedRanges -= 1;
    04348
    04349             if (Size > Segment->LargestUnCommittedRange) {
    04350
    04351                 Segment->LargestUnCommittedRange = Size;
    04352             }
    04353
    04354         //
    04355         //  Otherwise we'll continue search down the list
    04356         //
    04357
    04358         } else {
    04359
    04360             pp = &UnCommittedRange->Next;
    04361         }
    04362     }
    04363
    04364     //
    04365     //  If we reach this point that means we've either fallen off the end of the
    04366     //  list, or the list is empty, or we've located the spot where a new uncommitted
    04367     //  range structure belongs.  So allocate a new uncommitted range structure,
    04368     //  and make sure we got one.
    04369     //
    04370     //  Pp is the address of the block right before us and *Pp is the address of the
    04371     //  block right after us
    04372     //
    04373
    04374     UnCommittedRange = RtlpCreateUnCommittedRange( Segment );
    04375
    04376     if (UnCommittedRange == NULL) {
    04377
    04378         HeapDebugPrint(( "Abandoning uncommitted range (%x for %x)\n", Address, Size ));
    04379         // HeapDebugBreak( NULL );
    04380
    04381         return;
    04382     }
    04383
    04384     //
    04385     //  Fill in the new uncommitted range structure
    04386     //
    04387
    04388     UnCommittedRange->Address = Address;
    04389     UnCommittedRange->Size = Size;
    04390
    04391     //
    04392     //  Insert it in the list for the segment
    04393     //
    04394
    04395     UnCommittedRange->Next = *pp;
    04396     *pp = UnCommittedRange;
    04397
    04398     //
    04399     //  Update the segment counters and notion of the largest uncommitted range
    04400     //
    04401
    04402     Segment->NumberOfUnCommittedRanges += 1;
    04403
    04404     if (Size >= Segment->LargestUnCommittedRange) {
    04405
    04406         Segment->LargestUnCommittedRange = Size;
    04407     }
    04408
    04409     //
    04410     //  And return to our caller
    04411     //
    04412
    04413     return;
    04414 }
    04415
    04416
    04417 //
    04418 //  Declared in heappriv.h
    04419 //
    04420
    04421 PHEAP_FREE_ENTRY
    04422 RtlpFindAndCommitPages (
    04423     IN PHEAP Heap,
    04424     IN PHEAP_SEGMENT Segment,
    04425     IN OUT PSIZE_T Size,
    04426     IN PVOID AddressWanted OPTIONAL
    04427     )
    04428
    04429 /*++
    04430
    04431 Routine Description:
    04432
    04433     This function searches the supplied segment for an uncommitted range that
    04434     satisfies the specified size.  It commits the range and returns a heap entry
    04435     for the range.
    04436
    04437 Arguments:
    04438
    04439     Heap - Supplies the heap being maniuplated
    04440
    04441     Segment - Supplies the segment being searched
    04442
    04443     Size - Supplies the size of what we need to look for, on return it contains
    04444         the size of what we're just found and committed.
    04445
    04446     AddressWanted - Optionally gives an address where we would like the pages
    04447         based.  If supplied the entry must start at this address
    04448
    04449 Return Value:
    04450
    04451     PHEAP_FREE_ENTRY - Returns a pointer to the newly committed range that
    04452         satisfies the given size requirement, or NULL if we could not find
    04453         something large enough and/or based at the address wanted.
    04454
    04455 --*/
    04456
    04457 {
    04458     NTSTATUS Status;
    04459     PHEAP_ENTRY FirstEntry, LastEntry, PreviousLastEntry;
    04460     PHEAP_UNCOMMMTTED_RANGE PreviousUnCommittedRange, UnCommittedRange, *pp;
    04461     ULONG_PTR Address;
    04462     SIZE_T Length;
    04463
    04464     RTL_PAGED_CODE();
    04465
    04466     //
    04467     //  What the outer loop does is cycle through the uncommited ranges
    04468     //  stored in in the specified segment
    04469     //
    04470
    04471     PreviousUnCommittedRange = NULL;
    04472     pp = &Segment->UnCommittedRanges;
    04473
    04474     while (UnCommittedRange = *pp) {
    04475
    04476         //
    04477         //  Check for the best of worlds, where the size of this current
    04478         //  uncommitted range satisfies our size request and either the user
    04479         //  didn't specify an address or the address match
    04480         //
    04481
    04482         if ((UnCommittedRange->Size >= *Size) &&
    04483             (!ARGUMENT_PRESENT( AddressWanted ) || (UnCommittedRange->Address == (ULONG_PTR)AddressWanted ))) {
    04484
    04485             //
    04486             //  Calculate an address
    04487             //
    04488
    04489             Address = UnCommittedRange->Address;
    04490
    04491             //
    04492             //  Commit the memory.  If the heap doesn't have a commit
    04493             //  routine then use the default mm supplied routine.
    04494             //
    04495
    04496             if (Heap->CommitRoutine != NULL) {
    04497
    04498                 Status = (Heap->CommitRoutine)( Heap,
    04499                                                 (PVOID *)&Address,
    04500                                                 Size );
    04501
    04502             } else {
    04503
    04504                 Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    04505                                                   (PVOID *)&Address,
    04506                                                   0,
    04507                                                   Size,
    04508                                                   MEM_COMMIT,
    04509                                                   PAGE_READWRITE );
    04510
    04511             }
    04512
    04513             if (!NT_SUCCESS( Status )) {
    04514
    04515                 return NULL;
    04516             }
    04517
    04518             //
    04519             //  At this point we have some committed memory, with Address and Size
    04520             //  giving us the necessary details
    04521             //
    04522             //  Update the number of uncommitted pages in the segment and if necessary
    04523             //  mark down the largest uncommitted range
    04524             //
    04525
    04526             Segment->NumberOfUnCommittedPages -= (ULONG) (*Size / PAGE_SIZE);
    04527
    04528             if (Segment->LargestUnCommittedRange == UnCommittedRange->Size) {
    04529
    04530                 Segment->LargestUnCommittedRange = 0;
    04531             }
    04532
    04533             //
    04534             //  First entry is the start of the newly committed range
    04535             //
    04536
    04537             FirstEntry = (PHEAP_ENTRY)Address;
    04538
    04539             //
    04540             //  We want last entry to point to the last real entry before
    04541             //  this newly committed spot.  To do this we start by
    04542             //  setting last entry to either the first entry for the
    04543             //  segment or (if we can do better), to right after the last
    04544             //  uncommitted range we examined.  Either way it points to
    04545             //  some committed range
    04546             //
    04547
    04548             if ((Segment->LastEntryInSegment->Flags & HEAP_ENTRY_LAST_ENTRY) &&
    04549                 (ULONG_PTR)(Segment->LastEntryInSegment + Segment->LastEntryInSegment->Size) == UnCommittedRange->Address) {
    04550
    04551                 LastEntry = Segment->LastEntryInSegment;
    04552
    04553             } else {
    04554
    04555                 if (PreviousUnCommittedRange == NULL) {
    04556
    04557                     LastEntry = Segment->FirstEntry;
    04558
    04559                 } else {
    04560
    04561                     LastEntry = (PHEAP_ENTRY)(PreviousUnCommittedRange->Address +
    04562                                               PreviousUnCommittedRange->Size);
    04563                 }
    04564
    04565                 //
    04566                 //  Now we zoom through the entries until we find the one
    04567                 //  marked last
    04568                 //
    04569
    04570                 while (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    04571
    04572                     PreviousLastEntry = LastEntry;
    04573                     LastEntry += LastEntry->Size;
    04574
    04575                     if (((PCHAR)LastEntry >= (PCHAR)Segment->LastValidEntry) || (LastEntry->Size == 0)) {
    04576
    04577                         //
    04578                         //  Check for the situation where the last entry in the
    04579                         //  segment isn't marked as a last entry but does put
    04580                         //  us right where the have a new committed range
    04581                         //
    04582
    04583                         if (LastEntry == (PHEAP_ENTRY)Address) {
    04584
    04585                             LastEntry = PreviousLastEntry;
    04586
    04587                             break;
    04588                         }
    04589
    04590                         HeapDebugPrint(( "Heap missing last entry in committed range near %x\n", PreviousLastEntry ));
    04591                         HeapDebugBreak( PreviousLastEntry );
    04592
    04593                         return NULL;
    04594                     }
    04595                 }
    04596             }
    04597
    04598             //
    04599             //  Turn off the last bit on this entry because what's following
    04600             //  is no longer uncommitted
    04601             //
    04602
    04603             LastEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
    04604
    04605             //
    04606             //  Shrink the uncommited range by the size we've committed
    04607             //
    04608
    04609             UnCommittedRange->Address += *Size;
    04610             UnCommittedRange->Size -= *Size;
    04611
    04612             //
    04613             //  Now if the size is zero then we've committed everything that there
    04614             //  was in the range.  Otherwise make sure the first entry of what
    04615             //  we've just committed knows that an uncommitted range follows.
    04616             //
    04617
    04618             if (UnCommittedRange->Size == 0) {
    04619
    04620                 //
    04621                 //  This uncommitted range is about to vanish.  Base on if the
    04622                 //  range is the last one in the segemnt then we know how to
    04623                 //  mark the committed range as being last or not.
    04624                 //
    04625
    04626                 if (UnCommittedRange->Address == (ULONG_PTR)Segment->LastValidEntry) {
    04627
    04628                     FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
    04629
    04630                     Segment->LastEntryInSegment = FirstEntry;
    04631
    04632                 } else {
    04633
    04634                     FirstEntry->Flags = 0;
    04635
    04636                     Segment->LastEntryInSegment = Segment->FirstEntry;
    04637                 }
    04638
    04639                 //
    04640                 //  Remove this zero sized range from the uncommitted range
    04641                 //  list, and update the segment counters
    04642                 //
    04643
    04644                 *pp = UnCommittedRange->Next;
    04645
    04646                 RtlpDestroyUnCommittedRange( Segment, UnCommittedRange );
    04647
    04648                 Segment->NumberOfUnCommittedRanges -= 1;
    04649
    04650             } else {
    04651
    04652                 //
    04653                 //  Otherwise the range is not empty so we know what we committed
    04654                 //  is immediately followed by an uncommitted range
    04655                 //
    04656
    04657                 FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
    04658
    04659                 Segment->LastEntryInSegment = FirstEntry;
    04660             }
    04661
    04662             //
    04663             //  Update the fields in the first entry, and optional
    04664             //  following entry.
    04665             //
    04666
    04667             FirstEntry->SegmentIndex = LastEntry->SegmentIndex;
    04668             FirstEntry->Size = (USHORT)(*Size >> HEAP_GRANULARITY_SHIFT);
    04669             FirstEntry->PreviousSize = LastEntry->Size;
    04670
    04671             if (!(FirstEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    04672
    04673                 (FirstEntry + FirstEntry->Size)->PreviousSize = FirstEntry->Size;
    04674             }
    04675
    04676             //
    04677             //  Now if we adjusted the largest uncommitted range to zero then
    04678             //  we need to go back and find the largest uncommitted range
    04679             //  To do that we simply zoom down the uncommitted range list
    04680             //  remembering the largest one
    04681             //
    04682
    04683             if (Segment->LargestUnCommittedRange == 0) {
    04684
    04685                 UnCommittedRange = Segment->UnCommittedRanges;
    04686
    04687                 while (UnCommittedRange != NULL) {
    04688
    04689                     if (UnCommittedRange->Size >= Segment->LargestUnCommittedRange) {
    04690
    04691                         Segment->LargestUnCommittedRange = UnCommittedRange->Size;
    04692                     }
    04693
    04694                     UnCommittedRange = UnCommittedRange->Next;
    04695                 }
    04696             }
    04697
    04698             //
    04699             //  And return the heap entry to our caller
    04700             //
    04701
    04702             return (PHEAP_FREE_ENTRY)FirstEntry;
    04703
    04704         } else {
    04705
    04706             //
    04707             //  Otherwise the current uncommited range is too small or
    04708             //  doesn't have the right address so go to the next uncommitted
    04709             //  range entry
    04710             //
    04711
    04712             PreviousUnCommittedRange = UnCommittedRange;
    04713             pp = &UnCommittedRange->Next;
    04714         }
    04715     }
    04716
    04717     //
    04718     //  At this point we did not find an uncommitted range entry that satisfied
    04719     //  our requirements either because of size and/or address.  So return null
    04720     //  to tell the user we didn't find anything.
    04721     //
    04722
    04723     return NULL;
    04724 }
    04725
    04726
    04727 //
    04728 //  Declared in heappriv.h
    04729 //
    04730
    04731 BOOLEAN
    04732 RtlpInitializeHeapSegment (
    04733     IN PHEAP Heap,
    04734     IN PHEAP_SEGMENT Segment,
    04735     IN UCHAR SegmentIndex,
    04736     IN ULONG Flags,
    04737     IN PVOID BaseAddress,
    04738     IN PVOID UnCommittedAddress,
    04739     IN PVOID CommitLimitAddress
    04740     )
    04741
    04742 /*++
    04743
    04744 Routine Description:
    04745
    04746     This routines initializes the internal structures for a heap segment.
    04747     The caller supplies the heap and the memory for the segment being
    04748     initialized
    04749
    04750 Arguments:
    04751
    04752     Heap - Supplies the address of the heap owning this segment
    04753
    04754     Segment - Supplies a pointer to the segment being initialized
    04755
    04756     SegmentIndex - Supplies the segement index within the heap that this
    04757         new segment is being assigned
    04758
    04759     Flags - Supplies flags controlling the initialization of the segment
    04760         Valid flags are:
    04761
    04762             HEAP_SEGMENT_USER_ALLOCATED
    04763
    04764     BaseAddress - Supplies the base address for the segment
    04765
    04766     UnCommittedAddress - Supplies the address where the uncommited range starts
    04767
    04768     CommitLimitAddress - Supplies the top address available to the segment
    04769
    04770 Return Value:
    04771
    04772     BOOLEAN - TRUE if the initialization is successful and FALSE otherwise
    04773
    04774 --*/
    04775
    04776 {
    04777     NTSTATUS Status;
    04778     PHEAP_ENTRY FirstEntry;
    04779     USHORT PreviousSize, Size;
    04780     ULONG NumberOfPages;
    04781     ULONG NumberOfCommittedPages;
    04782     ULONG NumberOfUnCommittedPages;
    04783     SIZE_T CommitSize;
    04784     ULONG NtGlobalFlag = RtlGetNtGlobalFlags();
    04785
    04786     RTL_PAGED_CODE();
    04787
    04788     //
    04789     //  Compute the total number of pages possible in this segment
    04790     //
    04791
    04792     NumberOfPages = (ULONG) (((PCHAR)CommitLimitAddress - (PCHAR)BaseAddress) / PAGE_SIZE);
    04793
    04794     //
    04795     //  First entry points to the first possible segment entry after
    04796     //  the segment header
    04797     //
    04798
    04799     FirstEntry = (PHEAP_ENTRY)ROUND_UP_TO_POWER2( Segment + 1,
    04800                                                   HEAP_GRANULARITY );
    04801
    04802     //
    04803     //  Now if the heap is equal to the base address for the segment which
    04804     //  it the case for the segment zero then the previous size is the
    04805     //  heap header.  Otherwise there isn't a previous entry
    04806     //
    04807
    04808     if ((PVOID)Heap == BaseAddress) {
    04809
    04810         PreviousSize = Heap->Entry.Size;
    04811
    04812     } else {
    04813
    04814         PreviousSize = 0;
    04815     }
    04816
    04817     //
    04818     //  Compute the index size of the segement header
    04819     //
    04820
    04821     Size = (USHORT)(((PCHAR)FirstEntry - (PCHAR)Segment) >> HEAP_GRANULARITY_SHIFT);
    04822
    04823     //
    04824     //  If the first available heap entry is not committed and
    04825     //  it is beyond the heap limit then we cannot initialize
    04826     //
    04827
    04828     if ((PCHAR)(FirstEntry + 1) >= (PCHAR)UnCommittedAddress) {
    04829
    04830         if ((PCHAR)(FirstEntry + 1) >= (PCHAR)CommitLimitAddress) {
    04831
    04832             return FALSE;
    04833         }
    04834
    04835         //
    04836         //  Enough of the segment has not been committed so we
    04837         //  will commit enough now to handle the first entry
    04838         //
    04839
    04840         CommitSize = (PCHAR)(FirstEntry + 1) - (PCHAR)UnCommittedAddress;
    04841
    04842         Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    04843                                           (PVOID *)&UnCommittedAddress,
    04844                                           0,
    04845                                           &CommitSize,
    04846                                           MEM_COMMIT,
    04847                                           PAGE_READWRITE );
    04848
    04849         if (!NT_SUCCESS( Status )) {
    04850
    04851             return FALSE;
    04852         }
    04853
    04854         //
    04855         //  Because we had to commit some memory we need to adjust
    04856         //  the uncommited address
    04857         //
    04858
    04859         UnCommittedAddress = (PVOID)((PCHAR)UnCommittedAddress + CommitSize);
    04860     }
    04861
    04862     //
    04863     //  At this point we know there is enough memory committed to handle the
    04864     //  segment header and one heap entry
    04865     //
    04866     //  Now compute the number of uncommited pages and the number of committed
    04867     //  pages
    04868     //
    04869
    04870     NumberOfUnCommittedPages = (ULONG)(((PCHAR)CommitLimitAddress - (PCHAR)UnCommittedAddress) / PAGE_SIZE);
    04871     NumberOfCommittedPages = NumberOfPages - NumberOfUnCommittedPages;
    04872
    04873     //
    04874     //  Initialize the heap segment heap entry.  We
    04875     //  calculated earlier if there was a previous entry
    04876     //
    04877
    04878     Segment->Entry.PreviousSize = PreviousSize;
    04879     Segment->Entry.Size = Size;
    04880     Segment->Entry.Flags = HEAP_ENTRY_BUSY;
    04881     Segment->Entry.SegmentIndex = SegmentIndex;
    04882
    04883 #if i386 && !NTOS_KERNEL_RUNTIME
    04884
    04885     //
    04886     //  In the non kernel x86 case see if we need to capture the callers stack
    04887     //  backtrace
    04888     //
    04889
    04890     if (NtGlobalFlag & FLG_USER_STACK_TRACE_DB) {
    04891
    04892         Segment->AllocatorBackTraceIndex = (USHORT)RtlLogStackBackTrace();
    04893     }
    04894
    04895 #endif // i386 && !NTOS_KERNEL_RUNTIME
    04896
    04897     //
    04898     //  Now initializes the heap segment
    04899     //
    04900
    04901     Segment->Signature = HEAP_SEGMENT_SIGNATURE;
    04902     Segment->Flags = Flags;
    04903     Segment->Heap = Heap;
    04904     Segment->BaseAddress = BaseAddress;
    04905     Segment->FirstEntry = FirstEntry;
    04906     Segment->LastValidEntry = (PHEAP_ENTRY)((PCHAR)BaseAddress + (NumberOfPages * PAGE_SIZE));
    04907     Segment->NumberOfPages = NumberOfPages;
    04908     Segment->NumberOfUnCommittedPages = NumberOfUnCommittedPages;
    04909
    04910     //
    04911     //  If there are uncommitted pages then we need to insert them
    04912     //  into the uncommitted ranges list
    04913     //
    04914
    04915     if (NumberOfUnCommittedPages) {
    04916
    04917         RtlpInsertUnCommittedPages( Segment,
    04918                                     (ULONG_PTR)UnCommittedAddress,
    04919                                     NumberOfUnCommittedPages * PAGE_SIZE );
    04920     }
    04921
    04922     //
    04923     //  Have the containing heap point to this segment via the specified index
    04924     //
    04925
    04926     Heap->Segments[ SegmentIndex ] = Segment;
    04927
    04928     //
    04929     //  Initialize the first free heap entry after the heap segment header and
    04930     //  put it in the free list.  This first entry will be for whatever is left
    04931     //  of the committed range
    04932     //
    04933
    04934     PreviousSize = Segment->Entry.Size;
    04935     FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
    04936
    04937     Segment->LastEntryInSegment = FirstEntry;
    04938
    04939     FirstEntry->PreviousSize = PreviousSize;
    04940     FirstEntry->SegmentIndex = SegmentIndex;
    04941
    04942     RtlpInsertFreeBlock( Heap,
    04943                          (PHEAP_FREE_ENTRY)FirstEntry,
    04944                          (PHEAP_ENTRY)UnCommittedAddress - FirstEntry);
    04945
    04946     //
    04947     //  And return to our caller
    04948     //
    04949
    04950     return TRUE;
    04951 }
    04952
    04953
    04954 //
    04955 //  Local Support Routine
    04956 //
    04957
    04958 NTSTATUS
    04959 RtlpDestroyHeapSegment (
    04960     IN PHEAP_SEGMENT Segment
    04961     )
    04962
    04963 /*++
    04964
    04965 Routine Description:
    04966
    04967     This routine removes an existing heap segment.  After the call it
    04968     is as if the segment never existed
    04969
    04970 Arguments:
    04971
    04972     Segment - Supplies a pointer to the heap segment being destroyed
    04973
    04974 Return Value:
    04975
    04976     NTSTATUS - An appropriate status value
    04977
    04978 --*/
    04979
    04980 {
    04981     PVOID BaseAddress;
    04982     SIZE_T BytesToFree;
    04983
    04984     RTL_PAGED_CODE();
    04985
    04986     //
    04987     //  We actually only have work to do if the segment is not
    04988     //  user allocated.  If the segement is user allocated then
    04989     //  we'll assume knows how to get rid of the memory
    04990     //
    04991
    04992     if (!(Segment->Flags & HEAP_SEGMENT_USER_ALLOCATED)) {
    04993
    04994         BaseAddress = Segment->BaseAddress;
    04995         BytesToFree = 0;
    04996
    04997         //
    04998         //  Free all the virtual memory for the segment and return
    04999         //  to our caller.
    05000         //
    05001
    05002         return ZwFreeVirtualMemory( NtCurrentProcess(),
    05003                                     (PVOID *)&BaseAddress,
    05004                                     &BytesToFree,
    05005                                     MEM_RELEASE );
    05006
    05007     } else {
    05008
    05009         //
    05010         //  User allocated segments are a noop
    05011         //
    05012
    05013         return STATUS_SUCCESS;
    05014     }
    05015 }
    05016
    05017
    05018
    05019 //
    05020 //  Local Support Routine
    05021 //
    05022
    05023 PHEAP_FREE_ENTRY
    05024 RtlpExtendHeap (
    05025     IN PHEAP Heap,
    05026     IN SIZE_T AllocationSize
    05027     )
    05028
    05029 /*++
    05030
    05031 Routine Description:
    05032
    05033     This routine is used to extend the amount of committed memory in a heap
    05034
    05035 Arguments:
    05036
    05037     Heap - Supplies the heap being modified
    05038
    05039     AllocationSize - Supplies the size, in bytes, that we need to extend the
    05040         heap
    05041
    05042 Return Value:
    05043
    05044     PHEAP_FREE_ENTRY - Returns a pointer to the newly created heap entry
    05045         of the specified size, or NULL if we weren't able to extend the heap
    05046
    05047 --*/
    05048
    05049 {
    05050     NTSTATUS Status;
    05051     PHEAP_SEGMENT Segment;
    05052     PHEAP_FREE_ENTRY FreeBlock;
    05053     UCHAR SegmentIndex, EmptySegmentIndex;
    05054     ULONG NumberOfPages;
    05055     SIZE_T CommitSize;
    05056     SIZE_T ReserveSize;
    05057     SIZE_T FreeSize;
    05058
    05059     RTL_PAGED_CODE();
    05060
    05061     //
    05062     //  Compute the number of pages need to hold this extension
    05063     //  And then compute the real free, still in bytes, based on
    05064     //  the page count
    05065     //
    05066
    05067     NumberOfPages = (ULONG) ((AllocationSize + PAGE_SIZE - 1) / PAGE_SIZE);
    05068     FreeSize = NumberOfPages * PAGE_SIZE;
    05069
    05070     //
    05071     //  For every segment we're either going to look for an existing
    05072     //  heap segment that we can get some pages out of or we will
    05073     //  identify a free heap segment index where we'll try and create a new
    05074     //  segment
    05075     //
    05076
    05077     EmptySegmentIndex = HEAP_MAXIMUM_SEGMENTS;
    05078
    05079     for (SegmentIndex=0; SegmentIndex<HEAP_MAXIMUM_SEGMENTS; SegmentIndex++) {
    05080
    05081         Segment = Heap->Segments[ SegmentIndex ];
    05082
    05083         //
    05084         //  If the segment exists and number of uncommitted pages will
    05085         //  satisfy our reguest and the largest uncommitted range will
    05086         //  also satisfy our request then we'll try and segment
    05087         //
    05088         //  **** note that this second test seems unnecessary given that
    05089         //  **** the largest uncommitted range is also being tested
    05090         //
    05091
    05092         if ((Segment) &&
    05093             (NumberOfPages <= Segment->NumberOfUnCommittedPages) &&
    05094             (FreeSize <= Segment->LargestUnCommittedRange)) {
    05095
    05096             //
    05097             //  Looks like a good segment so try and commit the
    05098             //  amount we need
    05099             //
    05100
    05101             FreeBlock = RtlpFindAndCommitPages( Heap,
    05102                                                 Segment,
    05103                                                 &FreeSize,
    05104                                                 NULL );
    05105
    05106             //
    05107             //  If we were successful the we will coalesce it with adjacent
    05108             //  free blocks and put it in the free list then return the
    05109             //  the free block
    05110             //
    05111
    05112             if (FreeBlock != NULL) {
    05113
    05114                 //
    05115                 //  **** gdk ****
    05116                 //  **** this doesn't seem right given that coalesece should take
    05117                 //  **** byte count and not heap entry count
    05118                 //
    05119
    05120                 FreeSize = FreeSize >> HEAP_GRANULARITY_SHIFT;
    05121
    05122                 FreeBlock = RtlpCoalesceFreeBlocks( Heap, FreeBlock, &FreeSize, FALSE );
    05123
    05124                 RtlpInsertFreeBlock( Heap, FreeBlock, FreeSize );
    05125
    05126                 return FreeBlock;
    05127             }
    05128
    05129         //
    05130         //  Otherwise if the segment index is not in use and we haven't
    05131         //  yet identified a unused segment index then remembeer this
    05132         //  index
    05133         //
    05134
    05135         } else if ((Segment == NULL) &&
    05136                    (EmptySegmentIndex == HEAP_MAXIMUM_SEGMENTS)) {
    05137
    05138             EmptySegmentIndex = SegmentIndex;
    05139         }
    05140     }
    05141
    05142     //
    05143     //  At this point we weren't able to get the memory from an existing
    05144     //  heap segment so now check if we found an unused segment index
    05145     //  and if we're alowed to grow the heap.
    05146     //
    05147
    05148     if ((EmptySegmentIndex != HEAP_MAXIMUM_SEGMENTS) &&
    05149         (Heap->Flags & HEAP_GROWABLE)) {
    05150
    05151         Segment = NULL;
    05152
    05153         //
    05154         //  Calculate a reserve size for the new segment, we might
    05155         //  need to fudge it up if the allocation size we're going for
    05156         //  right now is already beyond the default reserve size
    05157         //
    05158
    05159         if ((AllocationSize + PAGE_SIZE) > Heap->SegmentReserve) {
    05160
    05161             ReserveSize = AllocationSize + PAGE_SIZE;
    05162
    05163         } else {
    05164
    05165             ReserveSize = Heap->SegmentReserve;
    05166         }
    05167
    05168         //
    05169         //  Try and reserve some vm
    05170         //
    05171
    05172         Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    05173                                           (PVOID *)&Segment,
    05174                                           0,
    05175                                           &ReserveSize,
    05176                                           MEM_RESERVE,
    05177                                           PAGE_READWRITE );
    05178
    05179         //
    05180         //  If we get back status no memory then we should trim back the
    05181         //  request to something reasonable and try again.  We'll half
    05182         //  the amount until we it either succeeds or until we reach
    05183         //  the allocation size.  In the latter case we are really
    05184         //  out of memory.
    05185         //
    05186
    05187         while ((!NT_SUCCESS( Status )) && (ReserveSize != (AllocationSize + PAGE_SIZE))) {
    05188
    05189             ReserveSize = ReserveSize / 2;
    05190
    05191             if( ReserveSize < (AllocationSize + PAGE_SIZE) ) {
    05192
    05193                 ReserveSize = (AllocationSize + PAGE_SIZE);
    05194             }
    05195
    05196             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    05197                                               (PVOID *)&Segment,
    05198                                               0,
    05199                                               &ReserveSize,
    05200                                               MEM_RESERVE,
    05201                                               PAGE_READWRITE );
    05202         }
    05203
    05204         if (NT_SUCCESS( Status )) {
    05205
    05206             //
    05207             //  Adjust the heap state information
    05208             //
    05209
    05210             Heap->SegmentReserve += ReserveSize;
    05211
    05212             //
    05213             //  Compute the commit size to be either the default, or if
    05214             //  that's not big enough then make it big enough to handle
    05215             //  this current request
    05216             //
    05217
    05218             if ((AllocationSize + PAGE_SIZE) > Heap->SegmentCommit) {
    05219
    05220                 CommitSize = AllocationSize + PAGE_SIZE;
    05221
    05222             } else {
    05223
    05224                 CommitSize = Heap->SegmentCommit;
    05225             }
    05226
    05227             //
    05228             //  Try and commit the memory
    05229             //
    05230
    05231             Status = ZwAllocateVirtualMemory( NtCurrentProcess(),
    05232                                               (PVOID *)&Segment,
    05233                                               0,
    05234                                               &CommitSize,
    05235                                               MEM_COMMIT,
    05236                                               PAGE_READWRITE );
    05237
    05238             //
    05239             //  If the commit is successful but we were not able to
    05240             //  initialize the heap segment then still make the status
    05241             //  and error value
    05242             //
    05243
    05244             if (NT_SUCCESS( Status ) &&
    05245                 !RtlpInitializeHeapSegment( Heap,
    05246                                             Segment,
    05247                                             EmptySegmentIndex,
    05248                                             0,
    05249                                             Segment,
    05250                                             (PCHAR)Segment + CommitSize,
    05251                                             (PCHAR)Segment + ReserveSize)) {
    05252
    05253                 Status = STATUS_NO_MEMORY;
    05254             }
    05255
    05256             //
    05257             //  If we've been successful so far then we're done and we
    05258             //  can return the first entry in the segment to our caller
    05259             //
    05260
    05261             if (NT_SUCCESS(Status)) {
    05262
    05263                 return (PHEAP_FREE_ENTRY)Segment->FirstEntry;
    05264             }
    05265
    05266             //
    05267             //  Otherwise either the commit or heap segment initialization failed
    05268             //  so we'll release the memory which will also decommit it if necessary
    05269             //
    05270
    05271             ZwFreeVirtualMemory( NtCurrentProcess(),
    05272                                  (PVOID *)&Segment,
    05273                                  &ReserveSize,
    05274                                  MEM_RELEASE );
    05275         }
    05276     }
    05277
    05278 #ifndef NTOS_KERNEL_RUNTIME
    05279
    05280     //
    05281     //  In the non kernel case we disabled coaleseing on free then what we'll
    05282     //  do as a last resort is coalesce the heap and see if a block comes out
    05283     //  that we can use
    05284     //
    05285
    05286     if (Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE) {
    05287
    05288         FreeBlock = RtlpCoalesceHeap( Heap );
    05289
    05290         if ((FreeBlock != NULL) && (FreeBlock->Size >= AllocationSize)) {
    05291
    05292             return FreeBlock;
    05293         }
    05294     }
    05295
    05296 #endif // NTOS_KERNEL_RUNTIME
    05297
    05298     //
    05299     //  Either the heap cannot grow or we out of resources of some type
    05300     //  so we're going to return null
    05301     //
    05302
    05303     return NULL;
    05304 }
    05305
    05306
    05307 //
    05308 //  Declared in heappriv.h
    05309 //
    05310
    05311 PHEAP_FREE_ENTRY
    05312 RtlpCoalesceFreeBlocks (
    05313     IN PHEAP Heap,
    05314     IN PHEAP_FREE_ENTRY FreeBlock,
    05315     IN OUT PSIZE_T FreeSize,
    05316     IN BOOLEAN RemoveFromFreeList
    05317     )
    05318
    05319 /*++
    05320
    05321 Routine Description:
    05322
    05323     This routine coalesces the free block together.
    05324
    05325 Arguments:
    05326
    05327     Heap - Supplies a pointer to the heap being manipulated
    05328
    05329     FreeBlock - Supplies a pointer to the free block that we want coalesced
    05330
    05331     FreeSize - Supplies the size, in bytes, of the free block.  On return it
    05332         contains the size, in bytes, of the of the newly coalesced free block
    05333
    05334     RemoveFromFreeList - Indicates if the input free block is already on a
    05335         free list and needs to be removed to before coalescing
    05336
    05337 Return Value:
    05338
    05339     PHEAP_FREE_ENTRY - returns a pointer to the newly coalesced free block
    05340
    05341 --*/
    05342
    05343 {
    05344     PHEAP_FREE_ENTRY FreeBlock1, NextFreeBlock;
    05345
    05346     RTL_PAGED_CODE();
    05347
    05348     //
    05349     //  Point to the preceding block
    05350     //
    05351
    05352     FreeBlock1 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock - FreeBlock->PreviousSize);
    05353
    05354     //
    05355     //  Check if there is a preceding block, and if it is free, and the two sizes
    05356     //  put together will still fit on a free lists.
    05357     //
    05358
    05359     if ((FreeBlock1 != FreeBlock) &&
    05360         !(FreeBlock1->Flags & HEAP_ENTRY_BUSY) &&
    05361         ((*FreeSize + FreeBlock1->Size) <= HEAP_MAXIMUM_BLOCK_SIZE)) {
    05362
    05363         //
    05364         //  We are going to merge ourselves with the preceding block
    05365         //
    05366
    05367         HEAPASSERT(FreeBlock->PreviousSize == FreeBlock1->Size);
    05368
    05369         //
    05370         //  Check if we need to remove the input block from the free list
    05371         //
    05372
    05373         if (RemoveFromFreeList) {
    05374
    05375             RtlpRemoveFreeBlock( Heap, FreeBlock );
    05376
    05377             Heap->TotalFreeSize -= FreeBlock->Size;
    05378
    05379             //
    05380             //  We're removed so we don't have to do it again
    05381             //
    05382
    05383             RemoveFromFreeList = FALSE;
    05384         }
    05385
    05386         //
    05387         //  Remove the preceding block from its free list
    05388         //
    05389
    05390         RtlpRemoveFreeBlock( Heap, FreeBlock1 );
    05391
    05392         //
    05393         //  Copy over the last entry flag if necessary from what we're freeing
    05394         //  to the preceding block
    05395         //
    05396
    05397         FreeBlock1->Flags = FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY;
    05398
    05399         if( FreeBlock1->Flags & HEAP_ENTRY_LAST_ENTRY ) {
    05400
    05401             PHEAP_SEGMENT Segment;
    05402
    05403             Segment = Heap->Segments[FreeBlock1->SegmentIndex];
    05404             Segment->LastEntryInSegment = (PHEAP_ENTRY)FreeBlock1;
    05405         }
    05406
    05407         //
    05408         //  Point to the preceding block, and adjust the sizes for the
    05409         //  new free block.  It is the total of both blocks.
    05410         //
    05411
    05412         FreeBlock = FreeBlock1;
    05413
    05414         *FreeSize += FreeBlock1->Size;
    05415
    05416         Heap->TotalFreeSize -= FreeBlock1->Size;
    05417
    05418         FreeBlock->Size = (USHORT)*FreeSize;
    05419
    05420         //
    05421         //  Check if we need to update the previous size of the next
    05422         //  entry
    05423         //
    05424
    05425         if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    05426
    05427             ((PHEAP_ENTRY)FreeBlock + *FreeSize)->PreviousSize = (USHORT)*FreeSize;
    05428         }
    05429     }
    05430
    05431     //
    05432     //  Check if there is a following block.
    05433     //
    05434
    05435     if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    05436
    05437         //
    05438         //  There is a following block so now get a pointer to it
    05439         //  and check if it is free and if putting the two blocks together
    05440         //  still fits on a free list
    05441         //
    05442
    05443         NextFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + *FreeSize);
    05444
    05445         if (!(NextFreeBlock->Flags & HEAP_ENTRY_BUSY) &&
    05446             ((*FreeSize + NextFreeBlock->Size) <= HEAP_MAXIMUM_BLOCK_SIZE)) {
    05447
    05448             //
    05449             //  We are going to merge ourselves with the following block
    05450             //
    05451
    05452             HEAPASSERT(*FreeSize == NextFreeBlock->PreviousSize);
    05453
    05454             //
    05455             //  Check if we need to remove the input block from the free list
    05456             //
    05457
    05458             if (RemoveFromFreeList) {
    05459
    05460                 RtlpRemoveFreeBlock( Heap, FreeBlock );
    05461
    05462                 Heap->TotalFreeSize -= FreeBlock->Size;
    05463
    05464                 //
    05465                 //  **** this assignment isn't necessary because there isn't
    05466                 //  **** any more merging after this one
    05467                 //
    05468
    05469                 RemoveFromFreeList = FALSE;
    05470             }
    05471
    05472             //
    05473             //  Copy up the last entry flag if necessary from the following
    05474             //  block to our input block
    05475             //
    05476
    05477             FreeBlock->Flags = NextFreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY;
    05478
    05479             if( FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY ) {
    05480
    05481                 PHEAP_SEGMENT Segment;
    05482
    05483                 Segment = Heap->Segments[FreeBlock->SegmentIndex];
    05484                 Segment->LastEntryInSegment = (PHEAP_ENTRY)FreeBlock;
    05485             }
    05486
    05487             //
    05488             //  Remove the following block from its free list
    05489             //
    05490
    05491             RtlpRemoveFreeBlock( Heap, NextFreeBlock );
    05492
    05493             //
    05494             //  Adjust the size for the newly combined block
    05495             //
    05496
    05497             *FreeSize += NextFreeBlock->Size;
    05498
    05499             Heap->TotalFreeSize -= NextFreeBlock->Size;
    05500
    05501             FreeBlock->Size = (USHORT)*FreeSize;
    05502
    05503             //
    05504             //  Check if we need to update the previous size of the next block
    05505             //
    05506
    05507             if (!(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    05508
    05509                 ((PHEAP_ENTRY)FreeBlock + *FreeSize)->PreviousSize = (USHORT)*FreeSize;
    05510             }
    05511         }
    05512     }
    05513
    05514     //
    05515     //  And return the free block to our caller
    05516     //
    05517
    05518     return FreeBlock;
    05519 }
    05520
    05521
    05522 //
    05523 //  Declared in heappriv.h
    05524 //
    05525
    05526 VOID
    05527 RtlpDeCommitFreeBlock (
    05528     IN PHEAP Heap,
    05529     IN PHEAP_FREE_ENTRY FreeBlock,
    05530     IN SIZE_T FreeSize
    05531     )
    05532
    05533 /*++
    05534
    05535 Routine Description:
    05536
    05537     This routine takes a free block and decommits it.  This is usually called
    05538     because the block is beyond the decommit threshold
    05539
    05540 Arguments:
    05541
    05542     Heap - Supplies a pointer to the heap being manipulated
    05543
    05544     FreeBlock - Supplies a pointer to the block being decommitted
    05545
    05546     FreeSize - Supplies the size, in bytes, of the free block being decommitted
    05547
    05548 Return Value:
    05549
    05550     None.
    05551
    05552 --*/
    05553
    05554 {
    05555     NTSTATUS Status;
    05556     ULONG_PTR DeCommitAddress;
    05557     SIZE_T DeCommitSize;
    05558     USHORT LeadingFreeSize, TrailingFreeSize;
    05559     PHEAP_SEGMENT Segment;
    05560     PHEAP_FREE_ENTRY LeadingFreeBlock, TrailingFreeBlock;
    05561     PHEAP_ENTRY LeadingBusyBlock, TrailingBusyBlock;
    05562     PHEAP_UNCOMMMTTED_RANGE UnCommittedRange;
    05563
    05564     RTL_PAGED_CODE();
    05565
    05566     //
    05567     //  If the heap has a user specified decommit routine then we won't really
    05568     //  decommit anything instead we'll call a worker routine to chop it up
    05569     //  into pieces that will fit on the free lists
    05570     //
    05571
    05572     if (Heap->CommitRoutine != NULL) {
    05573
    05574         RtlpInsertFreeBlock( Heap, FreeBlock, FreeSize );
    05575
    05576         return;
    05577     }
    05578
    05579     //
    05580     //  Get a pointer to the owning segment
    05581     //
    05582
    05583     Segment = Heap->Segments[ FreeBlock->SegmentIndex ];
    05584
    05585     //
    05586     //  The leading busy block identifies the preceding in use block before
    05587     //  what we are trying to decommit.  It is only used if what we are trying
    05588     //  decommit is right on a page boundary and then it is the block right
    05589     //  before us if it exists.
    05590     //
    05591     //  The leading free block is used to identify whatever space is needed
    05592     //  to round up the callers specified address to a page address.  If the
    05593     //  caller already gave us a page aligned address then the free block
    05594     //  address is identical to what the caller supplied.
    05595     //
    05596
    05597     LeadingBusyBlock = NULL;
    05598     LeadingFreeBlock = FreeBlock;
    05599
    05600     //
    05601     //  Make sure the block we are trying to decommit start on the next full
    05602     //  page boundary.  The leading free size is the size of whatever it takes
    05603     //  to round up the free block to the next page specified in units of
    05604     //  heap entries.
    05605     //
    05606
    05607     DeCommitAddress = ROUND_UP_TO_POWER2( LeadingFreeBlock, PAGE_SIZE );
    05608     LeadingFreeSize = (USHORT)((PHEAP_ENTRY)DeCommitAddress - (PHEAP_ENTRY)LeadingFreeBlock);
    05609
    05610     //
    05611     //  If we leading free size only has space for one heap entry then we'll
    05612     //  bump it up to include the next page, because we don't want to leave
    05613     //  anything that small laying around.  Otherwise if we have a preceding
    05614     //  block and the leading free size is zero then identify the preceding
    05615     //  block as the leading busy block
    05616     //
    05617
    05618     if (LeadingFreeSize == 1) {
    05619
    05620         DeCommitAddress += PAGE_SIZE;
    05621         LeadingFreeSize += PAGE_SIZE >> HEAP_GRANULARITY_SHIFT;
    05622
    05623     } else if (LeadingFreeBlock->PreviousSize != 0) {
    05624
    05625         if (DeCommitAddress == (ULONG_PTR)LeadingFreeBlock) {
    05626
    05627             LeadingBusyBlock = (PHEAP_ENTRY)LeadingFreeBlock - LeadingFreeBlock->PreviousSize;
    05628         }
    05629     }
    05630
    05631     //
    05632     //  The trailing busy block identifies the block immediately after the one
    05633     //  we are trying to decommit provided what we are decommitting ends right
    05634     //  on a page boundary otherwise the trailing busy block stays null and
    05635     //  the trailing free block value is used.
    05636     //
    05637     //  **** gdk ****
    05638     //  **** the assignment of tailing free block doesn't seem right because
    05639     //  **** Free size should be in bytes, and not heap entries
    05640     //
    05641
    05642     TrailingBusyBlock = NULL;
    05643     TrailingFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + FreeSize);
    05644
    05645     //
    05646     //  Make sure the block we are trying to decommit ends on a page boundary.
    05647     //
    05648     //  And compute how many heap entries we had to backup to make it land on a
    05649     //  page boundary.
    05650     //
    05651
    05652     DeCommitSize = ROUND_DOWN_TO_POWER2( (ULONG_PTR)TrailingFreeBlock, PAGE_SIZE );
    05653     TrailingFreeSize = (USHORT)((PHEAP_ENTRY)TrailingFreeBlock - (PHEAP_ENTRY)DeCommitSize);
    05654
    05655     //
    05656     //  If the trailing free size is exactly one heap in size then we will
    05657     //  nibble off a bit more from the decommit size because free block of
    05658     //  exactly one heap entry in size are useless.  Otherwise if we actually
    05659     //  ended on a page boundary and there is a block after us then indicate
    05660     //  that we have a trailing busy block
    05661     //
    05662
    05663     if (TrailingFreeSize == (sizeof( HEAP_ENTRY ) >> HEAP_GRANULARITY_SHIFT)) {
    05664
    05665         DeCommitSize -= PAGE_SIZE;
    05666         TrailingFreeSize += PAGE_SIZE >> HEAP_GRANULARITY_SHIFT;
    05667
    05668     } else if ((TrailingFreeSize == 0) && !(FreeBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) {
    05669
    05670         TrailingBusyBlock = (PHEAP_ENTRY)TrailingFreeBlock;
    05671     }
    05672
    05673     //
    05674     //  Now adjust the trailing free block to compensate for the trailing free size
    05675     //  we just computed.
    05676     //
    05677
    05678     TrailingFreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)TrailingFreeBlock - TrailingFreeSize);
    05679
    05680     //
    05681     //  Right now DeCommit size is really a pointer.  If it points at is beyond
    05682     //  the decommit address then make the size really be just the byte count
    05683     //  to decommit.  Otherwise the decommit size is zero.
    05684     //
    05685
    05686     if (DeCommitSize > DeCommitAddress) {
    05687
    05688         DeCommitSize -= DeCommitAddress;
    05689
    05690     } else {
    05691
    05692         DeCommitSize = 0;
    05693     }
    05694
    05695     //
    05696     //  **** this next test is bogus given the if-then-else that just preceded it
    05697     //
    05698     //  Now check if we still have something to decommit
    05699     //
    05700
    05701     if (DeCommitSize != 0) {
    05702
    05703         //
    05704         //  Before freeing the memory to MM we have to be sure we can create
    05705         //  a PHEAP_UNCOMMMTTED_RANGE later. So we do it right now
    05706         //
    05707
    05708         UnCommittedRange = RtlpCreateUnCommittedRange(Segment);
    05709
    05710         if (UnCommittedRange == NULL) {
    05711
    05712             HeapDebugPrint(( "Failing creating uncommitted range (%x for %x)\n", DeCommitAddress, DeCommitSize ));
    05713
    05714             //
    05715             //  We weren't successful in the decommit so now simply
    05716             //  add the leading free block to the free list
    05717             //
    05718
    05719             RtlpInsertFreeBlock( Heap, LeadingFreeBlock, FreeSize );
    05720
    05721             return;
    05722         }
    05723
    05724         //
    05725         //  Decommit the memory
    05726         //
    05727
    05728         Status = ZwFreeVirtualMemory( NtCurrentProcess(),
    05729                                       (PVOID *)&DeCommitAddress,
    05730                                       &DeCommitSize,
    05731                                       MEM_DECOMMIT );
    05732
    05733         //
    05734         //  Push back the UnCommittedRange structure. Now the insert cannot fail
    05735         //
    05736
    05737         RtlpDestroyUnCommittedRange( Segment, UnCommittedRange );
    05738
    05739         if (NT_SUCCESS( Status )) {
    05740
    05741             //
    05742             //  Insert information regarding the pages we just decommitted
    05743             //  to the lsit of uncommited pages in the segment
    05744             //
    05745
    05746             RtlpInsertUnCommittedPages( Segment,
    05747                                         DeCommitAddress,
    05748                                         DeCommitSize );
    05749             //
    05750             //  Adjust the segments count of uncommitted pages
    05751             //
    05752
    05753             Segment->NumberOfUnCommittedPages += (ULONG)(DeCommitSize / PAGE_SIZE);
    05754
    05755             //
    05756             //  If we have a leading free block then mark its proper state
    05757             //  update the heap, and put it on the free list
    05758             //
    05759
    05760             if (LeadingFreeSize != 0) {
    05761
    05762                 LeadingFreeBlock->Flags = HEAP_ENTRY_LAST_ENTRY;
    05763                 LeadingFreeBlock->Size = LeadingFreeSize;
    05764                 Heap->TotalFreeSize += LeadingFreeSize;
    05765
    05766                 Segment->LastEntryInSegment = (PHEAP_ENTRY)LeadingFreeBlock;
    05767
    05768                 RtlpInsertFreeBlockDirect( Heap, LeadingFreeBlock, LeadingFreeSize );
    05769
    05770             //
    05771             //  Otherwise if we actually have a leading busy block then
    05772             //  make sure the busy block knows we're uncommitted
    05773             //
    05774
    05775             } else if (LeadingBusyBlock != NULL) {
    05776
    05777                 LeadingBusyBlock->Flags |= HEAP_ENTRY_LAST_ENTRY;
    05778
    05779                 Segment->LastEntryInSegment = LeadingBusyBlock;
    05780
    05781             } else if ((Segment->LastEntryInSegment >= (PHEAP_ENTRY)DeCommitAddress)
    05782                             &&
    05783                        ((PCHAR)Segment->LastEntryInSegment < ((PCHAR)DeCommitAddress + DeCommitSize))) {
    05784
    05785                      Segment->LastEntryInSegment = Segment->FirstEntry;
    05786             }
    05787
    05788             //
    05789             //  If there is a trailing free block then sets its state,
    05790             //  update the heap, and insert it on a free list
    05791             //
    05792
    05793             if (TrailingFreeSize != 0) {
    05794
    05795                 TrailingFreeBlock->PreviousSize = 0;
    05796                 TrailingFreeBlock->SegmentIndex = Segment->Entry.SegmentIndex;
    05797                 TrailingFreeBlock->Flags = 0;
    05798                 TrailingFreeBlock->Size = TrailingFreeSize;
    05799
    05800                 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)TrailingFreeBlock + TrailingFreeSize))->PreviousSize = (USHORT)TrailingFreeSize;
    05801
    05802                 RtlpInsertFreeBlockDirect( Heap, TrailingFreeBlock, TrailingFreeSize );
    05803
    05804                 Heap->TotalFreeSize += TrailingFreeSize;
    05805
    05806             //
    05807             //  Otherwise if we actually have a succeeding block then
    05808             //  make it know we are uncommitted
    05809             //
    05810
    05811             } else if (TrailingBusyBlock != NULL) {
    05812
    05813                 TrailingBusyBlock->PreviousSize = 0;
    05814             }
    05815
    05816         } else {
    05817
    05818             //
    05819             //  We weren't successful in the decommit so now simply
    05820             //  add the leading free block to the free list
    05821             //
    05822
    05823             RtlpInsertFreeBlock( Heap, LeadingFreeBlock, FreeSize );
    05824         }
    05825
    05826     } else {
    05827
    05828         //
    05829         //  There is nothing left to decommit to take our leading free block
    05830         //  and put it on a free list
    05831         //
    05832
    05833         RtlpInsertFreeBlock( Heap, LeadingFreeBlock, FreeSize );
    05834     }
    05835
    05836     //
    05837     //  And return to our caller
    05838     //
    05839
    05840     return;
    05841 }
    05842
    05843
    05844 //
    05845 //  Declared in heappriv.h
    05846 //
    05847
    05848 VOID
    05849 RtlpInsertFreeBlock (
    05850     IN PHEAP Heap,
    05851     IN PHEAP_FREE_ENTRY FreeBlock,
    05852     IN SIZE_T FreeSize
    05853     )
    05854
    05855 /*++
    05856
    05857 Routine Description:
    05858
    05859     This routines take a piece of committed memory and adds to the
    05860     the appropriate free lists for the heap.  If necessary this
    05861     routine will divide up the free block to sizes that fit
    05862     on the free list
    05863
    05864
    05865 Arguments:
    05866
    05867     Heap - Supplies a pointer to the owning heap
    05868
    05869     FreeBlock - Supplies a pointer to the block being freed
    05870
    05871     FreeSize - Supplies the size, in bytes, of the block being freed
    05872
    05873 Return Value:
    05874
    05875     None.
    05876
    05877 --*/
    05878
    05879 {
    05880     USHORT PreviousSize, Size;
    05881     UCHAR Flags;
    05882     UCHAR SegmentIndex;
    05883     PHEAP_SEGMENT Segment;
    05884
    05885     RTL_PAGED_CODE();
    05886
    05887     //
    05888     //  Get the size of the previous block, the index of the segment
    05889     //  containing this block, and the flags specific to the block
    05890     //
    05891
    05892     PreviousSize = FreeBlock->PreviousSize;
    05893
    05894     SegmentIndex = FreeBlock->SegmentIndex;
    05895     Segment = Heap->Segments[ SegmentIndex ];
    05896
    05897     Flags = FreeBlock->Flags;
    05898
    05899     //
    05900     //  Adjust the total amount free in the heap
    05901     //
    05902
    05903     Heap->TotalFreeSize += FreeSize;
    05904
    05905     //
    05906     //  Now, while there is still something left to add to the free list
    05907     //  we'll process the information
    05908     //
    05909
    05910     while (FreeSize != 0) {
    05911
    05912         //
    05913         //  If the size is too big for our free lists then we'll
    05914         //  chop it down.
    05915         //
    05916
    05917         if (FreeSize > (ULONG)HEAP_MAXIMUM_BLOCK_SIZE) {
    05918
    05919             Size = HEAP_MAXIMUM_BLOCK_SIZE;
    05920
    05921             //
    05922             //  This little adjustment is so that we don't have a remainder
    05923             //  that is too small to be useful on the next iteration
    05924             //  through the loop
    05925             //
    05926
    05927             if (FreeSize == ((ULONG)HEAP_MAXIMUM_BLOCK_SIZE + 1)) {
    05928
    05929                 Size -= 16;
    05930             }
    05931
    05932             //
    05933             //  Guarantee that Last entry does not get set in this
    05934             //  block.
    05935             //
    05936
    05937             FreeBlock->Flags = 0;
    05938
    05939         } else {
    05940
    05941             Size = (USHORT)FreeSize;
    05942
    05943             //
    05944             //  This could propagate the last entry flag
    05945             //
    05946
    05947             FreeBlock->Flags = Flags;
    05948         }
    05949
    05950         //
    05951         //  Update the block sizes and then insert this
    05952         //  block into a free list
    05953         //
    05954
    05955         FreeBlock->PreviousSize = PreviousSize;
    05956         FreeBlock->SegmentIndex = SegmentIndex;
    05957         FreeBlock->Size = Size;
    05958
    05959         RtlpInsertFreeBlockDirect( Heap, FreeBlock, Size );
    05960
    05961         //
    05962         //  Note the size of what we just freed, and then update
    05963         //  our state information for the next time through the
    05964         //  loop
    05965         //
    05966
    05967         PreviousSize = Size;
    05968
    05969         FreeSize -= Size;
    05970         FreeBlock = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeBlock + Size);
    05971
    05972         //
    05973         //  Check if we're done with the free block based on the
    05974         //  segment information, otherwise go back up and check size
    05975         //  Note that is means that we can get called with a very
    05976         //  large size and still work.
    05977         //
    05978
    05979         if ((PHEAP_ENTRY)FreeBlock >= Segment->LastValidEntry) {
    05980
    05981             return;
    05982         }
    05983     }
    05984
    05985     //
    05986     //  If the block we're freeing did not think it was the last entry
    05987     //  then tell the next block our real size.
    05988     //
    05989
    05990     if (!(Flags & HEAP_ENTRY_LAST_ENTRY)) {
    05991
    05992         FreeBlock->PreviousSize = PreviousSize;
    05993     }
    05994
    05995     //
    05996     //  And return to our caller
    05997     //
    05998
    05999     return;
    06000 }
    06001
    06002
    06003 //
    06004 //  Declared in heappriv.h
    06005 //
    06006
    06007 PHEAP_ENTRY_EXTRA
    06008 RtlpGetExtraStuffPointer (
    06009     PHEAP_ENTRY BusyBlock
    06010     )
    06011
    06012 /*++
    06013
    06014 Routine Description:
    06015
    06016     This routine calculates where the extra stuff record will be given
    06017     the busy block and returns a pointer to it.  The caller must have
    06018     already checked that the entry extry field is present
    06019
    06020 Arguments:
    06021
    06022     BusyBlock - Supplies the busy block whose extra stuff we are seeking
    06023
    06024 Return Value:
    06025
    06026     PHEAP_ENTRY_EXTRA - returns a pointer to the extra stuff record.
    06027
    06028 --*/
    06029
    06030 {
    06031     ULONG AllocationIndex;
    06032
    06033     //
    06034     //  On big blocks the extra stuff is automatically part of the
    06035     //  block
    06036     //
    06037
    06038     if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) {
    06039
    06040         PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    06041
    06042         VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    06043
    06044         return &VirtualAllocBlock->ExtraStuff;
    06045
    06046     } else {
    06047
    06048         //
    06049         //  On non big blocks the extra stuff follows immediately after
    06050         //  the allocation itself.
    06051         //
    06052         //  **** What a hack
    06053         //  **** We do some funny math here because the busy block
    06054         //  **** stride is 8 bytes we know we can stride it by its
    06055         //  **** index minus one to get to the end of the allocation
    06056         //
    06057
    06058         AllocationIndex = BusyBlock->Size;
    06059
    06060         return (PHEAP_ENTRY_EXTRA)(BusyBlock + AllocationIndex - 1);
    06061     }
    06062 }
    06063
    06064
    06065 //
    06066 //  Declared in heappriv.h
    06067 //
    06068
    06069 SIZE_T
    06070 RtlpGetSizeOfBigBlock (
    06071     IN PHEAP_ENTRY BusyBlock
    06072     )
    06073
    06074 /*++
    06075
    06076 Routine Description:
    06077
    06078     This routine returns the size, in bytes, of the big allocation block
    06079
    06080 Arguments:
    06081
    06082     BusyBlock - Supplies a pointer to the block being queried
    06083
    06084 Return Value:
    06085
    06086     SIZE_T - Returns the size, in bytes, that was allocated to the big
    06087         block
    06088
    06089 --*/
    06090
    06091 {
    06092     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
    06093
    06094     RTL_PAGED_CODE();
    06095
    06096     //
    06097     //  Get a pointer to the block header itself
    06098     //
    06099
    06100     VirtualAllocBlock = CONTAINING_RECORD( BusyBlock, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock );
    06101
    06102     //
    06103     //  The size allocated to the block is actually the difference between the
    06104     //  commit size stored in the virtual alloc block and the size stored in
    06105     //  in the block.
    06106     //
    06107
    06108     return VirtualAllocBlock->CommitSize - BusyBlock->Size;
    06109 }
    06110
    06111
    06112 //
    06113 //  Declared in heappriv.h
    06114 //
    06115
    06116 BOOLEAN
    06117 RtlpCheckBusyBlockTail (
    06118     IN PHEAP_ENTRY BusyBlock
    06119     )
    06120
    06121 /*++
    06122
    06123 Routine Description:
    06124
    06125     This routine checks to see if the bytes beyond the user specified
    06126     allocation have been modified.  It does this by checking for a tail
    06127     fill pattern
    06128
    06129 Arguments:
    06130
    06131     BusyBlock - Supplies the heap block being queried
    06132
    06133 Return Value:
    06134
    06135     BOOLEAN - TRUE if the tail is still okay and FALSE otherwise
    06136
    06137 --*/
    06138
    06139 {
    06140     PCHAR Tail;
    06141     SIZE_T Size, cbEqual;
    06142
    06143     RTL_PAGED_CODE();
    06144
    06145     //
    06146     //  Compute the user allocated size of the input heap block
    06147     //
    06148
    06149     if (BusyBlock->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) {
    06150
    06151         Size = RtlpGetSizeOfBigBlock( BusyBlock );
    06152
    06153     } else {
    06154
    06155         Size = (BusyBlock->Size << HEAP_GRANULARITY_SHIFT) - BusyBlock->UnusedBytes;
    06156     }
    06157
    06158     //
    06159     //  Compute a pointer to the tail of the input block.  This would
    06160     //  be the space right after the user allocated portion
    06161     //
    06162
    06163     Tail = (PCHAR)(BusyBlock + 1) + Size;
    06164
    06165     //
    06166     //  Check if the tail fill pattern is still there
    06167     //
    06168
    06169     cbEqual = RtlCompareMemory( Tail,
    06170                                 CheckHeapFillPattern,
    06171                                 CHECK_HEAP_TAIL_SIZE );
    06172
    06173     //
    06174     //  If the number we get back isn't equal to the tail size then
    06175     //  someone modified the block beyond its user specified allocation
    06176     //  size
    06177     //
    06178
    06179     if (cbEqual != CHECK_HEAP_TAIL_SIZE) {
    06180
    06181         //
    06182         //  Do some debug printing
    06183         //
    06184
    06185         HeapDebugPrint(( "Heap block at %p modified at %p past requested size of %lx\n",
    06186                          BusyBlock,
    06187                          Tail + cbEqual,
    06188                          Size ));
    06189
    06190         HeapDebugBreak( BusyBlock );
    06191
    06192         //
    06193         //  And tell our caller there was an error
    06194         //
    06195
    06196         return FALSE;
    06197
    06198     } else {
    06199
    06200         //
    06201         //  And return to our caller that the tail is fine
    06202         //
    06203
    06204         return TRUE;
    06205     }
    06206 }