ReactOS Fundraising Campaign 2012
 
€ 11,198 / € 30,000

Information | Donate

Home | Info | Community | Development | myReactOS | Contact Us

  1. Home
  2. Community
  3. Development
  4. myReactOS
  5. Fundraiser 2012

  1. Main Page
  2. Alphabetical List
  3. Data Structures
  4. Directories
  5. File List
  6. Data Fields
  7. Globals
  8. Related Pages

ReactOS Development > Doxygen

heap.c
Go to the documentation of this file.
00001 /* COPYRIGHT:       See COPYING in the top level directory
00002  * PROJECT:         ReactOS system libraries
00003  * FILE:            lib/rtl/heap.c
00004  * PURPOSE:         RTL Heap backend allocator
00005  * PROGRAMMERS:     Copyright 2010 Aleksey Bragin
00006  */
00007 
00008 /* Useful references:
00009    http://msdn.microsoft.com/en-us/library/ms810466.aspx
00010    http://msdn.microsoft.com/en-us/library/ms810603.aspx
00011    http://www.securitylab.ru/analytics/216376.php
00012    http://binglongx.spaces.live.com/blog/cns!142CBF6D49079DE8!596.entry
00013    http://www.phreedom.org/research/exploits/asn1-bitstring/
00014    http://illmatics.com/Understanding_the_LFH.pdf
00015    http://www.alex-ionescu.com/?p=18
00016 */
00017 
00018 /* INCLUDES *****************************************************************/
00019 
00020 #include <rtl.h>
00021 #include <heap.h>
00022 
00023 #define NDEBUG
00024 #include <debug.h>
00025 
00026 RTL_CRITICAL_SECTION RtlpProcessHeapsListLock;
00027 
00028 /* Bitmaps stuff */
00029 
00030 /* How many least significant bits are clear */
00031 UCHAR RtlpBitsClearLow[] =
00032 {
00033     8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00034     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00035     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00036     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00037     6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00038     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00039     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00040     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00041     7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00042     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00043     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00044     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00045     6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00046     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00047     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
00048     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
00049 };
00050 
00051 UCHAR FORCEINLINE
00052 RtlpFindLeastSetBit(ULONG Bits)
00053 {
00054     if (Bits & 0xFFFF)
00055     {
00056         if (Bits & 0xFF)
00057             return RtlpBitsClearLow[Bits & 0xFF]; /* Lowest byte */
00058         else
00059             return RtlpBitsClearLow[(Bits >> 8) & 0xFF] + 8; /* 2nd byte */
00060     }
00061     else
00062     {
00063         if ((Bits >> 16) & 0xFF)
00064             return RtlpBitsClearLow[(Bits >> 16) & 0xFF] + 16; /* 3rd byte */
00065         else
00066             return RtlpBitsClearLow[(Bits >> 24) & 0xFF] + 24; /* Highest byte */
00067     }
00068 }
00069 
00070 /* Maximum size of a tail-filling pattern used for compare operation */
00071 UCHAR FillPattern[HEAP_ENTRY_SIZE] =
00072 {
00073     HEAP_TAIL_FILL,
00074     HEAP_TAIL_FILL,
00075     HEAP_TAIL_FILL,
00076     HEAP_TAIL_FILL,
00077     HEAP_TAIL_FILL,
00078     HEAP_TAIL_FILL,
00079     HEAP_TAIL_FILL,
00080     HEAP_TAIL_FILL
00081 };
00082 
00083 /* FUNCTIONS *****************************************************************/
00084 
00085 NTSTATUS NTAPI
00086 RtlpInitializeHeap(OUT PHEAP Heap,
00087                    IN ULONG Flags,
00088                    IN PHEAP_LOCK Lock OPTIONAL,
00089                    IN PRTL_HEAP_PARAMETERS Parameters)
00090 {
00091     ULONG NumUCRs = 8;
00092     ULONG Index;
00093     SIZE_T HeaderSize;
00094     NTSTATUS Status;
00095     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
00096 
00097     /* Preconditions */
00098     ASSERT(Heap != NULL);
00099     ASSERT(Parameters != NULL);
00100     ASSERT(!(Flags & HEAP_LOCK_USER_ALLOCATED));
00101     ASSERT(!(Flags & HEAP_NO_SERIALIZE) || (Lock == NULL));  /* HEAP_NO_SERIALIZE => no lock */
00102 
00103     /* Start out with the size of a plain Heap header */
00104     HeaderSize = ROUND_UP(sizeof(HEAP), sizeof(HEAP_ENTRY));
00105 
00106     /* Check if space needs to be added for the Heap Lock */
00107     if (!(Flags & HEAP_NO_SERIALIZE))
00108     {
00109         if (Lock != NULL)
00110             /* The user manages the Heap Lock */
00111             Flags |= HEAP_LOCK_USER_ALLOCATED;
00112         else
00113         if (RtlpGetMode() == UserMode)
00114         {
00115             /* In user mode, the Heap Lock trails the Heap header */
00116             Lock = (PHEAP_LOCK) ((ULONG_PTR) (Heap) + HeaderSize);
00117             HeaderSize += ROUND_UP(sizeof(HEAP_LOCK), sizeof(HEAP_ENTRY));
00118         }
00119     }
00120 
00121     /* Add space for the initial Heap UnCommitted Range Descriptor list */
00122     UcrDescriptor = (PHEAP_UCR_DESCRIPTOR) ((ULONG_PTR) (Heap) + HeaderSize);
00123     HeaderSize += ROUND_UP(NumUCRs * sizeof(HEAP_UCR_DESCRIPTOR), sizeof(HEAP_ENTRY));
00124 
00125     /* Sanity check */
00126     ASSERT(HeaderSize <= PAGE_SIZE);
00127 
00128     /* Initialise the Heap Entry header containing the Heap header */
00129     Heap->Entry.Size = (USHORT)(HeaderSize >> HEAP_ENTRY_SHIFT);
00130     Heap->Entry.Flags = HEAP_ENTRY_BUSY;
00131     Heap->Entry.SmallTagIndex = LOBYTE(Heap->Entry.Size) ^ HIBYTE(Heap->Entry.Size) ^ Heap->Entry.Flags;
00132     Heap->Entry.PreviousSize = 0;
00133     Heap->Entry.SegmentOffset = 0;
00134     Heap->Entry.UnusedBytes = 0;
00135 
00136     /* Initialise the Heap header */
00137     Heap->Signature = HEAP_SIGNATURE;
00138     Heap->Flags = Flags;
00139     Heap->ForceFlags = (Flags & (HEAP_NO_SERIALIZE |
00140                                  HEAP_GENERATE_EXCEPTIONS |
00141                                  HEAP_ZERO_MEMORY |
00142                                  HEAP_REALLOC_IN_PLACE_ONLY |
00143                                  HEAP_VALIDATE_PARAMETERS_ENABLED |
00144                                  HEAP_VALIDATE_ALL_ENABLED |
00145                                  HEAP_TAIL_CHECKING_ENABLED |
00146                                  HEAP_CREATE_ALIGN_16 |
00147                                  HEAP_FREE_CHECKING_ENABLED));
00148 
00149     /* Initialise the Heap parameters */
00150     Heap->VirtualMemoryThreshold = ROUND_UP(Parameters->VirtualMemoryThreshold, sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT;
00151     Heap->SegmentReserve = Parameters->SegmentReserve;
00152     Heap->SegmentCommit = Parameters->SegmentCommit;
00153     Heap->DeCommitFreeBlockThreshold = Parameters->DeCommitFreeBlockThreshold >> HEAP_ENTRY_SHIFT;
00154     Heap->DeCommitTotalFreeThreshold = Parameters->DeCommitTotalFreeThreshold >> HEAP_ENTRY_SHIFT;
00155     Heap->MaximumAllocationSize = Parameters->MaximumAllocationSize;
00156     Heap->CommitRoutine = Parameters->CommitRoutine;
00157 
00158     /* Initialise the Heap validation info */
00159     Heap->HeaderValidateCopy = NULL;
00160     Heap->HeaderValidateLength = (USHORT)HeaderSize;
00161 
00162     /* Initialise the Heap Lock */
00163     if (!(Flags & HEAP_NO_SERIALIZE) && !(Flags & HEAP_LOCK_USER_ALLOCATED))
00164     {
00165         Status = RtlInitializeHeapLock(&Lock);
00166         if (!NT_SUCCESS(Status))
00167             return Status;
00168     }
00169     Heap->LockVariable = Lock;
00170 
00171     /* Initialise the Heap alignment info */
00172     if (Flags & HEAP_CREATE_ALIGN_16)
00173     {
00174         Heap->AlignMask = (ULONG) ~15;
00175         Heap->AlignRound = 15 + sizeof(HEAP_ENTRY);
00176     }
00177     else
00178     {
00179         Heap->AlignMask = (ULONG) ~(sizeof(HEAP_ENTRY) - 1);
00180         Heap->AlignRound = 2 * sizeof(HEAP_ENTRY) - 1;
00181     }
00182 
00183     if (Flags & HEAP_TAIL_CHECKING_ENABLED)
00184         Heap->AlignRound += sizeof(HEAP_ENTRY);
00185 
00186     /* Initialise the Heap Segment list */
00187     for (Index = 0; Index < HEAP_SEGMENTS; ++Index)
00188         Heap->Segments[Index] = NULL;
00189 
00190     /* Initialise the Heap Free Heap Entry lists */
00191     for (Index = 0; Index < HEAP_FREELISTS; ++Index)
00192         InitializeListHead(&Heap->FreeLists[Index]);
00193 
00194     /* Initialise the Heap Virtual Allocated Blocks list */
00195     InitializeListHead(&Heap->VirtualAllocdBlocks);
00196 
00197     /* Initialise the Heap UnCommitted Region lists */
00198     InitializeListHead(&Heap->UCRSegments);
00199     InitializeListHead(&Heap->UCRList);
00200 
00201     /* Register the initial Heap UnCommitted Region Descriptors */
00202     for (Index = 0; Index < NumUCRs; ++Index)
00203         InsertTailList(&Heap->UCRList, &UcrDescriptor[Index].ListEntry);
00204 
00205     return STATUS_SUCCESS;
00206 }
00207 
00208 VOID FORCEINLINE
00209 RtlpSetFreeListsBit(PHEAP Heap,
00210                     PHEAP_FREE_ENTRY FreeEntry)
00211 {
00212     ULONG Index, Bit;
00213 
00214     ASSERT(FreeEntry->Size < HEAP_FREELISTS);
00215 
00216     /* Calculate offset in the free list bitmap */
00217     Index = FreeEntry->Size >> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
00218     Bit = 1 << (FreeEntry->Size & 7);
00219 
00220     /* Assure it's not already set */
00221     ASSERT((Heap->u.FreeListsInUseBytes[Index] & Bit) == 0);
00222 
00223     /* Set it */
00224     Heap->u.FreeListsInUseBytes[Index] |= Bit;
00225 }
00226 
00227 VOID FORCEINLINE
00228 RtlpClearFreeListsBit(PHEAP Heap,
00229                       PHEAP_FREE_ENTRY FreeEntry)
00230 {
00231     ULONG Index, Bit;
00232 
00233     ASSERT(FreeEntry->Size < HEAP_FREELISTS);
00234 
00235     /* Calculate offset in the free list bitmap */
00236     Index = FreeEntry->Size >> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
00237     Bit = 1 << (FreeEntry->Size & 7);
00238 
00239     /* Assure it was set and the corresponding free list is empty */
00240     ASSERT(Heap->u.FreeListsInUseBytes[Index] & Bit);
00241     ASSERT(IsListEmpty(&Heap->FreeLists[FreeEntry->Size]));
00242 
00243     /* Clear it */
00244     Heap->u.FreeListsInUseBytes[Index] ^= Bit;
00245 }
00246 
00247 VOID NTAPI
00248 RtlpInsertFreeBlockHelper(PHEAP Heap,
00249                           PHEAP_FREE_ENTRY FreeEntry,
00250                           SIZE_T BlockSize,
00251                           BOOLEAN NoFill)
00252 {
00253     PLIST_ENTRY FreeListHead, Current;
00254     PHEAP_FREE_ENTRY CurrentEntry;
00255 
00256     ASSERT(FreeEntry->Size == BlockSize);
00257 
00258     /* Fill if it's not denied */
00259     if (!NoFill)
00260     {
00261         FreeEntry->Flags &= ~(HEAP_ENTRY_FILL_PATTERN |
00262                               HEAP_ENTRY_EXTRA_PRESENT |
00263                               HEAP_ENTRY_BUSY);
00264 
00265         if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
00266         {
00267             RtlFillMemoryUlong((PCHAR)(FreeEntry + 1),
00268                                (BlockSize << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry),
00269                                ARENA_FREE_FILLER);
00270 
00271             FreeEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
00272         }
00273     }
00274     else
00275     {
00276         /* Clear out all flags except the last entry one */
00277         FreeEntry->Flags &= HEAP_ENTRY_LAST_ENTRY;
00278     }
00279 
00280     /* Insert it either into dedicated or non-dedicated list */
00281     if (BlockSize < HEAP_FREELISTS)
00282     {
00283         /* Dedicated list */
00284         FreeListHead = &Heap->FreeLists[BlockSize];
00285 
00286         if (IsListEmpty(FreeListHead))
00287         {
00288             RtlpSetFreeListsBit(Heap, FreeEntry);
00289         }
00290     }
00291     else
00292     {
00293         /* Non-dedicated one */
00294         FreeListHead = &Heap->FreeLists[0];
00295         Current = FreeListHead->Flink;
00296 
00297         /* Find a position where to insert it to (the list must be sorted) */
00298         while (FreeListHead != Current)
00299         {
00300             CurrentEntry = CONTAINING_RECORD(Current, HEAP_FREE_ENTRY, FreeList);
00301 
00302             if (BlockSize <= CurrentEntry->Size)
00303                 break;
00304 
00305             Current = Current->Flink;
00306         }
00307 
00308         FreeListHead = Current;
00309     }
00310 
00311     /* Actually insert it into the list */
00312     InsertTailList(FreeListHead, &FreeEntry->FreeList);
00313 }
00314 
00315 VOID NTAPI
00316 RtlpInsertFreeBlock(PHEAP Heap,
00317                     PHEAP_FREE_ENTRY FreeEntry,
00318                     SIZE_T BlockSize)
00319 {
00320     USHORT Size, PreviousSize;
00321     UCHAR SegmentOffset, Flags;
00322     PHEAP_SEGMENT Segment;
00323 
00324     DPRINT("RtlpInsertFreeBlock(%p %p %x)\n", Heap, FreeEntry, BlockSize);
00325 
00326     /* Increase the free size counter */
00327     Heap->TotalFreeSize += BlockSize;
00328 
00329     /* Remember certain values */
00330     Flags = FreeEntry->Flags;
00331     PreviousSize = FreeEntry->PreviousSize;
00332     SegmentOffset = FreeEntry->SegmentOffset;
00333     Segment = Heap->Segments[SegmentOffset];
00334 
00335     /* Process it */
00336     while (BlockSize)
00337     {
00338         /* Check for the max size */
00339         if (BlockSize > HEAP_MAX_BLOCK_SIZE)
00340         {
00341             Size = HEAP_MAX_BLOCK_SIZE;
00342 
00343             /* Special compensation if it goes above limit just by 1 */
00344             if (BlockSize == (HEAP_MAX_BLOCK_SIZE + 1))
00345                 Size -= 16;
00346 
00347             FreeEntry->Flags = 0;
00348         }
00349         else
00350         {
00351             Size = (USHORT)BlockSize;
00352             FreeEntry->Flags = Flags;
00353         }
00354 
00355         /* Change its size and insert it into a free list */
00356         FreeEntry->Size = Size;
00357         FreeEntry->PreviousSize = PreviousSize;
00358         FreeEntry->SegmentOffset = SegmentOffset;
00359 
00360         /* Call a helper to actually insert the block */
00361         RtlpInsertFreeBlockHelper(Heap, FreeEntry, Size, FALSE);
00362 
00363         /* Update sizes */
00364         PreviousSize = Size;
00365         BlockSize -= Size;
00366 
00367         /* Go to the next entry */
00368         FreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size);
00369 
00370         /* Check if that's all */
00371         if ((PHEAP_ENTRY)FreeEntry >= Segment->LastValidEntry) return;
00372     }
00373 
00374     /* Update previous size if needed */
00375     if (!(Flags & HEAP_ENTRY_LAST_ENTRY))
00376         FreeEntry->PreviousSize = PreviousSize;
00377 }
00378 
00379 VOID NTAPI
00380 RtlpRemoveFreeBlock(PHEAP Heap,
00381                     PHEAP_FREE_ENTRY FreeEntry,
00382                     BOOLEAN Dedicated,
00383                     BOOLEAN NoFill)
00384 {
00385     SIZE_T Result, RealSize;
00386 
00387     /* Remove the free block and update the freelists bitmap */
00388     if (RemoveEntryList(&FreeEntry->FreeList) &&
00389         (Dedicated || (!Dedicated && FreeEntry->Size < HEAP_FREELISTS)))
00390     {
00391         RtlpClearFreeListsBit(Heap, FreeEntry);
00392     }
00393 
00394     /* Fill with pattern if necessary */
00395     if (!NoFill &&
00396         (FreeEntry->Flags & HEAP_ENTRY_FILL_PATTERN))
00397     {
00398         RealSize = (FreeEntry->Size << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry);
00399 
00400         /* Deduct extra stuff from block's real size */
00401         if (FreeEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT &&
00402             RealSize > sizeof(HEAP_FREE_ENTRY_EXTRA))
00403         {
00404             RealSize -= sizeof(HEAP_FREE_ENTRY_EXTRA);
00405         }
00406 
00407         /* Check if the free filler is intact */
00408         Result = RtlCompareMemoryUlong((PCHAR)(FreeEntry + 1),
00409                                         RealSize,
00410                                         ARENA_FREE_FILLER);
00411 
00412         if (Result != RealSize)
00413         {
00414             DPRINT1("Free heap block %p modified at %p after it was freed\n",
00415                 FreeEntry,
00416                 (PCHAR)(FreeEntry + 1) + Result);
00417         }
00418     }
00419 }
00420 
00421 SIZE_T NTAPI
00422 RtlpGetSizeOfBigBlock(PHEAP_ENTRY HeapEntry)
00423 {
00424     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
00425 
00426     /* Get pointer to the containing record */
00427     VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
00428 
00429     /* Restore the real size */
00430     return VirtualEntry->CommitSize - HeapEntry->Size;
00431 }
00432 
00433 PHEAP_UCR_DESCRIPTOR NTAPI
00434 RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment)
00435 {
00436     PLIST_ENTRY Entry;
00437     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
00438     PHEAP_UCR_SEGMENT UcrSegment;
00439     PHEAP Heap = Segment->Heap;
00440     SIZE_T ReserveSize = 16 * PAGE_SIZE;
00441     SIZE_T CommitSize = 1 * PAGE_SIZE;
00442     NTSTATUS Status;
00443 
00444     DPRINT("RtlpCreateUnCommittedRange(%p)\n", Segment);
00445 
00446     /* Check if we have unused UCRs */
00447     if (IsListEmpty(&Heap->UCRList))
00448     {
00449         /* Get a pointer to the first UCR segment */
00450         UcrSegment = CONTAINING_RECORD(Heap->UCRSegments.Flink, HEAP_UCR_SEGMENT, ListEntry);
00451 
00452         /* Check the list of UCR segments */
00453         if (IsListEmpty(&Heap->UCRSegments) ||
00454             UcrSegment->ReservedSize == UcrSegment->CommittedSize)
00455         {
00456             /* We need to create a new one. Reserve 16 pages for it */
00457             UcrSegment = NULL;
00458             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
00459                                              (PVOID *)&UcrSegment,
00460                                              0,
00461                                              &ReserveSize,
00462                                              MEM_RESERVE,
00463                                              PAGE_READWRITE);
00464 
00465             if (!NT_SUCCESS(Status)) return NULL;
00466 
00467             /* Commit one page */
00468             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
00469                                              (PVOID *)&UcrSegment,
00470                                              0,
00471                                              &CommitSize,
00472                                              MEM_COMMIT,
00473                                              PAGE_READWRITE);
00474 
00475             if (!NT_SUCCESS(Status))
00476             {
00477                 /* Release reserved memory */
00478                 ZwFreeVirtualMemory(NtCurrentProcess(),
00479                                     (PVOID *)&UcrSegment,
00480                                     &ReserveSize,
00481                                     MEM_RELEASE);
00482                 return NULL;
00483             }
00484 
00485             /* Set it's data */
00486             UcrSegment->ReservedSize = ReserveSize;
00487             UcrSegment->CommittedSize = CommitSize;
00488 
00489             /* Add it to the head of the list */
00490             InsertHeadList(&Heap->UCRSegments, &UcrSegment->ListEntry);
00491 
00492             /* Get a pointer to the first available UCR descriptor */
00493             UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)(UcrSegment + 1);
00494         }
00495         else
00496         {
00497             /* It's possible to use existing UCR segment. Commit one more page */
00498             UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)((PCHAR)UcrSegment + UcrSegment->CommittedSize);
00499             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
00500                                              (PVOID *)&UcrDescriptor,
00501                                              0,
00502                                              &CommitSize,
00503                                              MEM_COMMIT,
00504                                              PAGE_READWRITE);
00505 
00506             if (!NT_SUCCESS(Status)) return NULL;
00507 
00508             /* Update sizes */
00509             UcrSegment->CommittedSize += CommitSize;
00510         }
00511 
00512         /* There is a whole bunch of new UCR descriptors. Put them into the unused list */
00513         while ((PCHAR)(UcrDescriptor + 1) <= (PCHAR)UcrSegment + UcrSegment->CommittedSize)
00514         {
00515             InsertTailList(&Heap->UCRList, &UcrDescriptor->ListEntry);
00516             UcrDescriptor++;
00517         }
00518     }
00519 
00520     /* There are unused UCRs, just get the first one */
00521     Entry = RemoveHeadList(&Heap->UCRList);
00522     UcrDescriptor = CONTAINING_RECORD(Entry, HEAP_UCR_DESCRIPTOR, ListEntry);
00523     return UcrDescriptor;
00524 }
00525 
00526 VOID NTAPI
00527 RtlpDestroyUnCommittedRange(PHEAP_SEGMENT Segment,
00528                             PHEAP_UCR_DESCRIPTOR UcrDescriptor)
00529 {
00530     /* Zero it out */
00531     UcrDescriptor->Address = NULL;
00532     UcrDescriptor->Size = 0;
00533 
00534     /* Put it into the heap's list of unused UCRs */
00535     InsertHeadList(&Segment->Heap->UCRList, &UcrDescriptor->ListEntry);
00536 }
00537 
00538 VOID NTAPI
00539 RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment,
00540                            ULONG_PTR Address,
00541                            SIZE_T Size)
00542 {
00543     PLIST_ENTRY Current;
00544     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
00545 
00546     DPRINT("RtlpInsertUnCommittedPages(%p %p %x)\n", Segment, Address, Size);
00547 
00548     /* Go through the list of UCR descriptors, they are sorted from lowest address
00549        to the highest */
00550     Current = Segment->UCRSegmentList.Flink;
00551     while (Current != &Segment->UCRSegmentList)
00552     {
00553         UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry);
00554 
00555         if ((ULONG_PTR)UcrDescriptor->Address > Address)
00556         {
00557             /* Check for a really lucky case */
00558             if ((Address + Size) == (ULONG_PTR)UcrDescriptor->Address)
00559             {
00560                 /* Exact match */
00561                 UcrDescriptor->Address = (PVOID)Address;
00562                 UcrDescriptor->Size += Size;
00563                 return;
00564             }
00565 
00566             /* We found the block before which the new one should go */
00567             break;
00568         }
00569         else if (((ULONG_PTR)UcrDescriptor->Address + UcrDescriptor->Size) == Address)
00570         {
00571             /* Modify this entry */
00572             Address = (ULONG_PTR)UcrDescriptor->Address;
00573             Size += UcrDescriptor->Size;
00574 
00575             /* Advance to the next descriptor */
00576             Current = Current->Flink;
00577 
00578             /* Remove the current descriptor from the list and destroy it */
00579             RemoveEntryList(&UcrDescriptor->SegmentEntry);
00580             RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
00581 
00582             Segment->NumberOfUnCommittedRanges--;
00583         }
00584         else
00585         {
00586             /* Advance to the next descriptor */
00587             Current = Current->Flink;
00588         }
00589     }
00590 
00591     /* Create a new UCR descriptor */
00592     UcrDescriptor = RtlpCreateUnCommittedRange(Segment);
00593     if (!UcrDescriptor) return;
00594 
00595     UcrDescriptor->Address = (PVOID)Address;
00596     UcrDescriptor->Size = Size;
00597 
00598     /* "Current" is the descriptor before which our one should go */
00599     InsertTailList(Current, &UcrDescriptor->SegmentEntry);
00600 
00601     DPRINT("Added segment UCR with base %p, size 0x%x\n", Address, Size);
00602 
00603     /* Increase counters */
00604     Segment->NumberOfUnCommittedRanges++;
00605 }
00606 
00607 PHEAP_FREE_ENTRY NTAPI
00608 RtlpFindAndCommitPages(PHEAP Heap,
00609                        PHEAP_SEGMENT Segment,
00610                        PSIZE_T Size,
00611                        PVOID AddressRequested)
00612 {
00613     PLIST_ENTRY Current;
00614     ULONG_PTR Address = 0;
00615     PHEAP_UCR_DESCRIPTOR UcrDescriptor, PreviousUcr = NULL;
00616     PHEAP_ENTRY FirstEntry, LastEntry;
00617     NTSTATUS Status;
00618 
00619     DPRINT("RtlpFindAndCommitPages(%p %p %x %p)\n", Heap, Segment, *Size, Address);
00620 
00621     /* Go through UCRs in a segment */
00622     Current = Segment->UCRSegmentList.Flink;
00623     while (Current != &Segment->UCRSegmentList)
00624     {
00625         UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry);
00626 
00627         /* Check if we can use that one right away */
00628         if (UcrDescriptor->Size >= *Size &&
00629             (UcrDescriptor->Address == AddressRequested || !AddressRequested))
00630         {
00631             /* Get the address */
00632             Address = (ULONG_PTR)UcrDescriptor->Address;
00633 
00634             /* Commit it */
00635             if (Heap->CommitRoutine)
00636             {
00637                 Status = Heap->CommitRoutine(Heap, (PVOID *)&Address, Size);
00638             }
00639             else
00640             {
00641                 Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
00642                                                  (PVOID *)&Address,
00643                                                  0,
00644                                                  Size,
00645                                                  MEM_COMMIT,
00646                                                  PAGE_READWRITE);
00647             }
00648 
00649             DPRINT("Committed %d bytes at base %p, UCR size is %d\n", *Size, Address, UcrDescriptor->Size);
00650 
00651             /* Fail in unsuccessful case */
00652             if (!NT_SUCCESS(Status))
00653             {
00654                 DPRINT1("Committing page failed with status 0x%08X\n", Status);
00655                 return NULL;
00656             }
00657 
00658             /* Update tracking numbers */
00659             Segment->NumberOfUnCommittedPages -= (ULONG)(*Size / PAGE_SIZE);
00660 
00661             /* Calculate first and last entries */
00662             FirstEntry = (PHEAP_ENTRY)Address;
00663 
00664             /* Go through the entries to find the last one */
00665             if (PreviousUcr)
00666                 LastEntry = (PHEAP_ENTRY)((ULONG_PTR)PreviousUcr->Address + PreviousUcr->Size);
00667             else
00668                 LastEntry = &Segment->Entry;
00669 
00670             while (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
00671             {
00672                 ASSERT(LastEntry->Size != 0);
00673                 LastEntry += LastEntry->Size;
00674             }
00675             ASSERT((LastEntry + LastEntry->Size) == FirstEntry);
00676 
00677             /* Unmark it as a last entry */
00678             LastEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
00679 
00680             /* Update UCR descriptor */
00681             UcrDescriptor->Address = (PVOID)((ULONG_PTR)UcrDescriptor->Address + *Size);
00682             UcrDescriptor->Size -= *Size;
00683 
00684             DPRINT("Updating UcrDescriptor %p, new Address %p, size %d\n",
00685                 UcrDescriptor, UcrDescriptor->Address, UcrDescriptor->Size);
00686 
00687             /* Set various first entry fields */
00688             FirstEntry->SegmentOffset = LastEntry->SegmentOffset;
00689             FirstEntry->Size = (USHORT)(*Size >> HEAP_ENTRY_SHIFT);
00690             FirstEntry->PreviousSize = LastEntry->Size;
00691 
00692             /* Check if anything left in this UCR */
00693             if (UcrDescriptor->Size == 0)
00694             {
00695                 /* It's fully exhausted */
00696 
00697                 /* Check if this is the end of the segment */
00698                 if(UcrDescriptor->Address == Segment->LastValidEntry)
00699                 {
00700                     FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
00701                 }
00702                 else
00703                 {
00704                     FirstEntry->Flags = 0;
00705                     /* Update field of next entry */
00706                     ASSERT((FirstEntry + FirstEntry->Size)->PreviousSize == 0);
00707                     (FirstEntry + FirstEntry->Size)->PreviousSize = FirstEntry->Size;
00708                 }
00709 
00710                 /* This UCR needs to be removed because it became useless */
00711                 RemoveEntryList(&UcrDescriptor->SegmentEntry);
00712 
00713                 RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
00714                 Segment->NumberOfUnCommittedRanges--;
00715             }
00716             else
00717             {
00718                 FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
00719             }
00720 
00721             /* We're done */
00722             return (PHEAP_FREE_ENTRY)FirstEntry;
00723         }
00724 
00725         /* Advance to the next descriptor */
00726         PreviousUcr = UcrDescriptor;
00727         Current = Current->Flink;
00728     }
00729 
00730     return NULL;
00731 }
00732 
00733 VOID NTAPI
00734 RtlpDeCommitFreeBlock(PHEAP Heap,
00735                       PHEAP_FREE_ENTRY FreeEntry,
00736                       SIZE_T Size)
00737 {
00738     PHEAP_SEGMENT Segment;
00739     PHEAP_ENTRY PrecedingInUseEntry = NULL, NextInUseEntry = NULL;
00740     PHEAP_FREE_ENTRY NextFreeEntry;
00741     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
00742     SIZE_T PrecedingSize, NextSize, DecommitSize;
00743     ULONG_PTR DecommitBase;
00744     NTSTATUS Status;
00745 
00746     DPRINT("Decommitting %p %p %x\n", Heap, FreeEntry, Size);
00747 
00748     /* We can't decommit if there is a commit routine! */
00749     if (Heap->CommitRoutine)
00750     {
00751         /* Just add it back the usual way */
00752         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
00753         return;
00754     }
00755 
00756     /* Get the segment */
00757     Segment = Heap->Segments[FreeEntry->SegmentOffset];
00758 
00759     /* Get the preceding entry */
00760     DecommitBase = ROUND_UP(FreeEntry, PAGE_SIZE);
00761     PrecedingSize = (PHEAP_ENTRY)DecommitBase - (PHEAP_ENTRY)FreeEntry;
00762 
00763     if (PrecedingSize == 1)
00764     {
00765         /* Just 1 heap entry, increase the base/size */
00766         DecommitBase += PAGE_SIZE;
00767         PrecedingSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT;
00768     }
00769     else if (FreeEntry->PreviousSize &&
00770              (DecommitBase == (ULONG_PTR)FreeEntry))
00771     {
00772         PrecedingInUseEntry = (PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize;
00773     }
00774 
00775     /* Get the next entry */
00776     NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size);
00777     DecommitSize = ROUND_DOWN(NextFreeEntry, PAGE_SIZE);
00778     NextSize = (PHEAP_ENTRY)NextFreeEntry - (PHEAP_ENTRY)DecommitSize;
00779 
00780     if (NextSize == 1)
00781     {
00782         /* Just 1 heap entry, increase the size */
00783         DecommitSize -= PAGE_SIZE;
00784         NextSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT;
00785     }
00786     else if (NextSize == 0 &&
00787              !(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
00788     {
00789         NextInUseEntry = (PHEAP_ENTRY)NextFreeEntry;
00790     }
00791 
00792     NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry - NextSize);
00793 
00794     /* Calculate real decommit size */
00795     if (DecommitSize > DecommitBase)
00796     {
00797         DecommitSize -= DecommitBase;
00798     }
00799     else
00800     {
00801         /* Nothing to decommit */
00802         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
00803         return;
00804     }
00805 
00806     /* A decommit is necessary. Create a UCR descriptor */
00807     UcrDescriptor = RtlpCreateUnCommittedRange(Segment);
00808     if (!UcrDescriptor)
00809     {
00810         DPRINT1("HEAP: Failed to create UCR descriptor\n");
00811         RtlpInsertFreeBlock(Heap, FreeEntry, PrecedingSize);
00812         return;
00813     }
00814 
00815     /* Decommit the memory */
00816     Status = ZwFreeVirtualMemory(NtCurrentProcess(),
00817                                  (PVOID *)&DecommitBase,
00818                                  &DecommitSize,
00819                                  MEM_DECOMMIT);
00820 
00821     /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */
00822     RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
00823 
00824     if (!NT_SUCCESS(Status))
00825     {
00826         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
00827         return;
00828     }
00829 
00830     /* Insert uncommitted pages */
00831     RtlpInsertUnCommittedPages(Segment, DecommitBase, DecommitSize);
00832     Segment->NumberOfUnCommittedPages += (ULONG)(DecommitSize / PAGE_SIZE);
00833 
00834     if (PrecedingSize)
00835     {
00836         /* Adjust size of this free entry and insert it */
00837         FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
00838         FreeEntry->Size = (USHORT)PrecedingSize;
00839         Heap->TotalFreeSize += PrecedingSize;
00840 
00841         /* Insert it into the free list */
00842         RtlpInsertFreeBlockHelper(Heap, FreeEntry, PrecedingSize, FALSE);
00843     }
00844     else if (PrecedingInUseEntry)
00845     {
00846         /* Adjust preceding in use entry */
00847         PrecedingInUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY;
00848     }
00849 
00850     /* Now the next one */
00851     if (NextSize)
00852     {
00853         /* Adjust size of this free entry and insert it */
00854         NextFreeEntry->Flags = 0;
00855         NextFreeEntry->PreviousSize = 0;
00856         NextFreeEntry->SegmentOffset = Segment->Entry.SegmentOffset;
00857         NextFreeEntry->Size = (USHORT)NextSize;
00858 
00859         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry + NextSize))->PreviousSize = (USHORT)NextSize;
00860 
00861         Heap->TotalFreeSize += NextSize;
00862         RtlpInsertFreeBlockHelper(Heap, NextFreeEntry, NextSize, FALSE);
00863     }
00864     else if (NextInUseEntry)
00865     {
00866         NextInUseEntry->PreviousSize = 0;
00867     }
00868 }
00869 
00870 NTSTATUS
00871 NTAPI
00872 RtlpInitializeHeapSegment(IN OUT PHEAP Heap,
00873                           OUT PHEAP_SEGMENT Segment,
00874                           IN UCHAR SegmentIndex,
00875                           IN ULONG SegmentFlags,
00876                           IN SIZE_T SegmentReserve,
00877                           IN SIZE_T SegmentCommit)
00878 {
00879     PHEAP_ENTRY HeapEntry;
00880 
00881     /* Preconditions */
00882     ASSERT(Heap != NULL);
00883     ASSERT(Segment != NULL);
00884     ASSERT(SegmentCommit >= PAGE_SIZE);
00885     ASSERT(ROUND_DOWN(SegmentCommit, PAGE_SIZE) == SegmentCommit);
00886     ASSERT(SegmentReserve >= SegmentCommit);
00887     ASSERT(ROUND_DOWN(SegmentReserve, PAGE_SIZE) == SegmentReserve);
00888 
00889     DPRINT("RtlpInitializeHeapSegment(%p %p %x %x %lx %lx)\n", Heap, Segment, SegmentIndex, SegmentFlags, SegmentReserve, SegmentCommit);
00890 
00891     /* Initialise the Heap Entry header if this is not the first Heap Segment */
00892     if ((PHEAP_SEGMENT) (Heap) != Segment)
00893     {
00894         Segment->Entry.Size = ROUND_UP(sizeof(HEAP_SEGMENT), sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT;
00895         Segment->Entry.Flags = HEAP_ENTRY_BUSY;
00896         Segment->Entry.SmallTagIndex = LOBYTE(Segment->Entry.Size) ^ HIBYTE(Segment->Entry.Size) ^ Segment->Entry.Flags;
00897         Segment->Entry.PreviousSize = 0;
00898         Segment->Entry.SegmentOffset = SegmentIndex;
00899         Segment->Entry.UnusedBytes = 0;
00900     }
00901 
00902     /* Sanity check */
00903     ASSERT((Segment->Entry.Size << HEAP_ENTRY_SHIFT) <= PAGE_SIZE);
00904 
00905     /* Initialise the Heap Segment header */
00906     Segment->SegmentSignature = HEAP_SEGMENT_SIGNATURE;
00907     Segment->SegmentFlags = SegmentFlags;
00908     Segment->Heap = Heap;
00909     Heap->Segments[SegmentIndex] = Segment;
00910 
00911     /* Initialise the Heap Segment location information */
00912     Segment->BaseAddress = Segment;
00913     Segment->NumberOfPages = (ULONG)(SegmentReserve >> PAGE_SHIFT);
00914 
00915     /* Initialise the Heap Entries contained within the Heap Segment */
00916     Segment->FirstEntry = &Segment->Entry + Segment->Entry.Size;
00917     Segment->LastValidEntry = (PHEAP_ENTRY)((ULONG_PTR)Segment + SegmentReserve);
00918 
00919     if (((SIZE_T)Segment->Entry.Size << HEAP_ENTRY_SHIFT) < SegmentCommit)
00920     {
00921         HeapEntry = Segment->FirstEntry;
00922 
00923         /* Prepare a Free Heap Entry header */
00924         HeapEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
00925         HeapEntry->PreviousSize = Segment->Entry.Size;
00926         HeapEntry->SegmentOffset = SegmentIndex;
00927 
00928         /* Register the Free Heap Entry */
00929         RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY) HeapEntry, (SegmentCommit >> HEAP_ENTRY_SHIFT) - Segment->Entry.Size);
00930     }
00931 
00932     /* Initialise the Heap Segment UnCommitted Range information */
00933     Segment->NumberOfUnCommittedPages = (ULONG)((SegmentReserve - SegmentCommit) >> PAGE_SHIFT);
00934     Segment->NumberOfUnCommittedRanges = 0;
00935     InitializeListHead(&Segment->UCRSegmentList);
00936 
00937     /* Register the UnCommitted Range of the Heap Segment */
00938     if (Segment->NumberOfUnCommittedPages != 0)
00939         RtlpInsertUnCommittedPages(Segment, (ULONG_PTR) (Segment) + SegmentCommit, SegmentReserve - SegmentCommit);
00940 
00941     return STATUS_SUCCESS;
00942 }
00943 
00944 VOID NTAPI
00945 RtlpDestroyHeapSegment(PHEAP_SEGMENT Segment)
00946 {
00947     NTSTATUS Status;
00948     PVOID BaseAddress;
00949     SIZE_T Size = 0;
00950 
00951     /* Make sure it's not user allocated */
00952     if (Segment->SegmentFlags & HEAP_USER_ALLOCATED) return;
00953 
00954     BaseAddress = Segment->BaseAddress;
00955     DPRINT("Destroying segment %p, BA %p\n", Segment, BaseAddress);
00956 
00957     /* Release virtual memory */
00958     Status = ZwFreeVirtualMemory(NtCurrentProcess(),
00959                                  &BaseAddress,
00960                                  &Size,
00961                                  MEM_RELEASE);
00962 
00963     if (!NT_SUCCESS(Status))
00964     {
00965         DPRINT1("HEAP: Failed to release segment's memory with status 0x%08X\n", Status);
00966     }
00967 }
00968 
00969 /* Usermode only! */
00970 VOID NTAPI
00971 RtlpAddHeapToProcessList(PHEAP Heap)
00972 {
00973     PPEB Peb;
00974 
00975     /* Get PEB */
00976     Peb = RtlGetCurrentPeb();
00977 
00978     /* Acquire the lock */
00979     RtlEnterCriticalSection(&RtlpProcessHeapsListLock);
00980 
00981     //_SEH2_TRY {
00982     /* Check if max number of heaps reached */
00983     if (Peb->NumberOfHeaps == Peb->MaximumNumberOfHeaps)
00984     {
00985         // TODO: Handle this case
00986         ASSERT(FALSE);
00987     }
00988 
00989     /* Add the heap to the process heaps */
00990     Peb->ProcessHeaps[Peb->NumberOfHeaps] = Heap;
00991     Peb->NumberOfHeaps++;
00992     Heap->ProcessHeapsListIndex = (USHORT)Peb->NumberOfHeaps;
00993     // } _SEH2_FINALLY {
00994 
00995     /* Release the lock */
00996     RtlLeaveCriticalSection(&RtlpProcessHeapsListLock);
00997 
00998     // } _SEH2_END
00999 }
01000 
01001 /* Usermode only! */
01002 VOID NTAPI
01003 RtlpRemoveHeapFromProcessList(PHEAP Heap)
01004 {
01005     PPEB Peb;
01006     PHEAP *Current, *Next;
01007     ULONG Count;
01008 
01009     /* Get PEB */
01010     Peb = RtlGetCurrentPeb();
01011 
01012     /* Acquire the lock */
01013     RtlEnterCriticalSection(&RtlpProcessHeapsListLock);
01014 
01015     /* Check if we don't need anything to do */
01016     if ((Heap->ProcessHeapsListIndex == 0) ||
01017         (Heap->ProcessHeapsListIndex > Peb->NumberOfHeaps) ||
01018         (Peb->NumberOfHeaps == 0))
01019     {
01020         /* Release the lock */
01021         RtlLeaveCriticalSection(&RtlpProcessHeapsListLock);
01022 
01023         return;
01024     }
01025 
01026     /* The process actually has more than one heap.
01027        Use classic, lernt from university times algorithm for removing an entry
01028        from a static array */
01029 
01030     Current = (PHEAP *)&Peb->ProcessHeaps[Heap->ProcessHeapsListIndex - 1];
01031     Next = Current + 1;
01032 
01033     /* How many items we need to shift to the left */
01034     Count = Peb->NumberOfHeaps - (Heap->ProcessHeapsListIndex - 1);
01035 
01036     /* Move them all in a loop */
01037     while (--Count)
01038     {
01039         /* Copy it and advance next pointer */
01040         *Current = *Next;
01041 
01042         /* Update its index */
01043         (*Current)->ProcessHeapsListIndex -= 1;
01044 
01045         /* Advance pointers */
01046         Current++;
01047         Next++;
01048     }
01049 
01050     /* Decrease total number of heaps */
01051     Peb->NumberOfHeaps--;
01052 
01053     /* Zero last unused item */
01054     Peb->ProcessHeaps[Peb->NumberOfHeaps] = NULL;
01055     Heap->ProcessHeapsListIndex = 0;
01056 
01057     /* Release the lock */
01058     RtlLeaveCriticalSection(&RtlpProcessHeapsListLock);
01059 }
01060 
01061 PHEAP_FREE_ENTRY NTAPI
01062 RtlpCoalesceHeap(PHEAP Heap)
01063 {
01064     UNIMPLEMENTED;
01065     return NULL;
01066 }
01067 
01068 PHEAP_FREE_ENTRY NTAPI
01069 RtlpCoalesceFreeBlocks (PHEAP Heap,
01070                         PHEAP_FREE_ENTRY FreeEntry,
01071                         PSIZE_T FreeSize,
01072                         BOOLEAN Remove)
01073 {
01074     PHEAP_FREE_ENTRY CurrentEntry, NextEntry;
01075 
01076     /* Get the previous entry */
01077     CurrentEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize);
01078 
01079     /* Check it */
01080     if (CurrentEntry != FreeEntry &&
01081         !(CurrentEntry->Flags & HEAP_ENTRY_BUSY) &&
01082         (*FreeSize + CurrentEntry->Size) <= HEAP_MAX_BLOCK_SIZE)
01083     {
01084         ASSERT(FreeEntry->PreviousSize == CurrentEntry->Size);
01085 
01086         /* Remove it if asked for */
01087         if (Remove)
01088         {
01089             RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
01090             Heap->TotalFreeSize -= FreeEntry->Size;
01091 
01092             /* Remove it only once! */
01093             Remove = FALSE;
01094         }
01095 
01096         /* Remove previous entry too */
01097         RtlpRemoveFreeBlock(Heap, CurrentEntry, FALSE, FALSE);
01098 
01099         /* Copy flags */
01100         CurrentEntry->Flags = FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY;
01101 
01102         /* Advance FreeEntry and update sizes */
01103         FreeEntry = CurrentEntry;
01104         *FreeSize = *FreeSize + CurrentEntry->Size;
01105         Heap->TotalFreeSize -= CurrentEntry->Size;
01106         FreeEntry->Size = (USHORT)(*FreeSize);
01107 
01108         /* Also update previous size if needed */
01109         if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
01110         {
01111             ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize);
01112         }
01113     }
01114 
01115     /* Check the next block if it exists */
01116     if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
01117     {
01118         NextEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + *FreeSize);
01119 
01120         if (!(NextEntry->Flags & HEAP_ENTRY_BUSY) &&
01121             NextEntry->Size + *FreeSize <= HEAP_MAX_BLOCK_SIZE)
01122         {
01123             ASSERT(*FreeSize == NextEntry->PreviousSize);
01124 
01125             /* Remove it if asked for */
01126             if (Remove)
01127             {
01128                 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
01129                 Heap->TotalFreeSize -= FreeEntry->Size;
01130             }
01131 
01132             /* Copy flags */
01133             FreeEntry->Flags = NextEntry->Flags & HEAP_ENTRY_LAST_ENTRY;
01134 
01135             /* Remove next entry now */
01136             RtlpRemoveFreeBlock(Heap, NextEntry, FALSE, FALSE);
01137 
01138             /* Update sizes */
01139             *FreeSize = *FreeSize + NextEntry->Size;
01140             Heap->TotalFreeSize -= NextEntry->Size;
01141             FreeEntry->Size = (USHORT)(*FreeSize);
01142 
01143             /* Also update previous size if needed */
01144             if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
01145             {
01146                 ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize);
01147             }
01148         }
01149     }
01150     return FreeEntry;
01151 }
01152 
01153 PHEAP_FREE_ENTRY NTAPI
01154 RtlpExtendHeap(PHEAP Heap,
01155                SIZE_T Size)
01156 {
01157     ULONG Pages;
01158     UCHAR Index, EmptyIndex;
01159     SIZE_T FreeSize, CommitSize, ReserveSize;
01160     PHEAP_SEGMENT Segment;
01161     PHEAP_FREE_ENTRY FreeEntry;
01162     NTSTATUS Status;
01163 
01164     DPRINT("RtlpExtendHeap(%p %x)\n", Heap, Size);
01165 
01166     /* Calculate amount in pages */
01167     Pages = (ULONG)((Size + PAGE_SIZE - 1) / PAGE_SIZE);
01168     FreeSize = Pages * PAGE_SIZE;
01169     DPRINT("Pages %x, FreeSize %x. Going through segments...\n", Pages, FreeSize);
01170 
01171     /* Find an empty segment */
01172     EmptyIndex = HEAP_SEGMENTS;
01173     for (Index = 0; Index < HEAP_SEGMENTS; Index++)
01174     {
01175         Segment = Heap->Segments[Index];
01176 
01177         if (Segment) DPRINT("Segment[%d] %p with NOUCP %x\n", Index, Segment, Segment->NumberOfUnCommittedPages);
01178 
01179         /* Check if its size suits us */
01180         if (Segment &&
01181             Pages <= Segment->NumberOfUnCommittedPages)
01182         {
01183             DPRINT("This segment is suitable\n");
01184 
01185             /* Commit needed amount */
01186             FreeEntry = RtlpFindAndCommitPages(Heap, Segment, &FreeSize, NULL);
01187 
01188             /* Coalesce it with adjacent entries */
01189             if (FreeEntry)
01190             {
01191                 FreeSize = FreeSize >> HEAP_ENTRY_SHIFT;
01192                 FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE);
01193                 RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize);
01194                 return FreeEntry;
01195             }
01196         }
01197         else if (!Segment &&
01198                  EmptyIndex == HEAP_SEGMENTS)
01199         {
01200             /* Remember the first unused segment index */
01201             EmptyIndex = Index;
01202         }
01203     }
01204 
01205     /* No luck, need to grow the heap */
01206     if ((Heap->Flags & HEAP_GROWABLE) &&
01207         (EmptyIndex != HEAP_SEGMENTS))
01208     {
01209         Segment = NULL;
01210 
01211         /* Reserve the memory */
01212         if ((Size + PAGE_SIZE) <= Heap->SegmentReserve)
01213             ReserveSize = Heap->SegmentReserve;
01214         else
01215             ReserveSize = Size + PAGE_SIZE;
01216 
01217         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
01218                                          (PVOID)&Segment,
01219                                          0,
01220                                          &ReserveSize,
01221                                          MEM_RESERVE,
01222                                          PAGE_READWRITE);
01223 
01224         /* If it failed, retry again with a half division algorithm */
01225         while (!NT_SUCCESS(Status) &&
01226             ReserveSize != Size + PAGE_SIZE)
01227         {
01228             ReserveSize /= 2;
01229 
01230             if (ReserveSize < (Size + PAGE_SIZE))
01231                 ReserveSize = Size + PAGE_SIZE;
01232 
01233             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
01234                                              (PVOID)&Segment,
01235                                              0,
01236                                              &ReserveSize,
01237                                              MEM_RESERVE,
01238                                              PAGE_READWRITE);
01239         }
01240 
01241         /* Proceed only if it's success */
01242         if (NT_SUCCESS(Status))
01243         {
01244             Heap->SegmentReserve += ReserveSize;
01245 
01246             /* Now commit the memory */
01247             if ((Size + PAGE_SIZE) <= Heap->SegmentCommit)
01248                 CommitSize = Heap->SegmentCommit;
01249             else
01250                 CommitSize = Size + PAGE_SIZE;
01251 
01252             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
01253                                              (PVOID)&Segment,
01254                                              0,
01255                                              &CommitSize,
01256                                              MEM_COMMIT,
01257                                              PAGE_READWRITE);
01258 
01259             DPRINT("Committed %d bytes at base %p\n", CommitSize, Segment);
01260 
01261             /* Initialize heap segment if commit was successful */
01262             if (NT_SUCCESS(Status))
01263                 Status = RtlpInitializeHeapSegment(Heap, Segment, EmptyIndex, 0, ReserveSize, CommitSize);
01264 
01265             /* If everything worked - cool */
01266             if (NT_SUCCESS(Status)) return (PHEAP_FREE_ENTRY)Segment->FirstEntry;
01267 
01268             DPRINT1("Committing failed with status 0x%08X\n", Status);
01269 
01270             /* Nope, we failed. Free memory */
01271             ZwFreeVirtualMemory(NtCurrentProcess(),
01272                                 (PVOID)&Segment,
01273                                 &ReserveSize,
01274                                 MEM_RELEASE);
01275         }
01276         else
01277         {
01278             DPRINT1("Reserving failed with status 0x%08X\n", Status);
01279         }
01280     }
01281 
01282     if (RtlpGetMode() == UserMode)
01283     {
01284         /* If coalescing on free is disabled in usermode, then do it here */
01285         if (Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)
01286         {
01287             FreeEntry = RtlpCoalesceHeap(Heap);
01288 
01289             /* If it's a suitable one - return it */
01290             if (FreeEntry &&
01291                 FreeEntry->Size >= Size)
01292             {
01293                 return FreeEntry;
01294             }
01295         }
01296     }
01297 
01298     return NULL;
01299 }
01300 
01301 /***********************************************************************
01302  *           RtlCreateHeap
01303  * RETURNS
01304  * Handle of heap: Success
01305  * NULL: Failure
01306  *
01307  * @implemented
01308  */
01309 HANDLE NTAPI
01310 RtlCreateHeap(ULONG Flags,
01311               PVOID Addr,
01312               SIZE_T TotalSize,
01313               SIZE_T CommitSize,
01314               PVOID Lock,
01315               PRTL_HEAP_PARAMETERS Parameters)
01316 {
01317     PVOID CommittedAddress = NULL, UncommittedAddress = NULL;
01318     PHEAP Heap = NULL;
01319     RTL_HEAP_PARAMETERS SafeParams = {0};
01320     PPEB Peb;
01321     ULONG_PTR MaximumUserModeAddress;
01322     SYSTEM_BASIC_INFORMATION SystemInformation;
01323     MEMORY_BASIC_INFORMATION MemoryInfo;
01324     ULONG NtGlobalFlags = RtlGetNtGlobalFlags();
01325     ULONG HeapSegmentFlags = 0;
01326     NTSTATUS Status;
01327     ULONG MaxBlockSize;
01328 
01329     /* Check for a special heap */
01330     if (RtlpPageHeapEnabled && !Addr && !Lock)
01331     {
01332         Heap = RtlpPageHeapCreate(Flags, Addr, TotalSize, CommitSize, Lock, Parameters);
01333         if (Heap) return Heap;
01334 
01335         /* Reset a special Parameters == -1 hack */
01336         if ((ULONG_PTR)Parameters == (ULONG_PTR)-1)
01337             Parameters = NULL;
01338         else
01339             DPRINT1("Enabling page heap failed\n");
01340     }
01341 
01342     /* Check validation flags */
01343     if (!(Flags & HEAP_SKIP_VALIDATION_CHECKS) && (Flags & ~HEAP_CREATE_VALID_MASK))
01344     {
01345         DPRINT1("Invalid flags 0x%08x, fixing...\n", Flags);
01346         Flags &= HEAP_CREATE_VALID_MASK;
01347     }
01348 
01349     /* TODO: Capture parameters, once we decide to use SEH */
01350     if (!Parameters) Parameters = &SafeParams;
01351 
01352     /* Check global flags */
01353     if (NtGlobalFlags & FLG_HEAP_DISABLE_COALESCING)
01354         Flags |= HEAP_DISABLE_COALESCE_ON_FREE;
01355 
01356     if (NtGlobalFlags & FLG_HEAP_ENABLE_FREE_CHECK)
01357         Flags |= HEAP_FREE_CHECKING_ENABLED;
01358 
01359     if (NtGlobalFlags & FLG_HEAP_ENABLE_TAIL_CHECK)
01360         Flags |= HEAP_TAIL_CHECKING_ENABLED;
01361 
01362     if (RtlpGetMode() == UserMode)
01363     {
01364         /* Also check these flags if in usermode */
01365         if (NtGlobalFlags & FLG_HEAP_VALIDATE_ALL)
01366             Flags |= HEAP_VALIDATE_ALL_ENABLED;
01367 
01368         if (NtGlobalFlags & FLG_HEAP_VALIDATE_PARAMETERS)
01369             Flags |= HEAP_VALIDATE_PARAMETERS_ENABLED;
01370 
01371         if (NtGlobalFlags & FLG_USER_STACK_TRACE_DB)
01372             Flags |= HEAP_CAPTURE_STACK_BACKTRACES;
01373 
01374         /* Get PEB */
01375         Peb = RtlGetCurrentPeb();
01376 
01377         /* Apply defaults for non-set parameters */
01378         if (!Parameters->SegmentCommit) Parameters->SegmentCommit = Peb->HeapSegmentCommit;
01379         if (!Parameters->SegmentReserve) Parameters->SegmentReserve = Peb->HeapSegmentReserve;
01380         if (!Parameters->DeCommitFreeBlockThreshold) Parameters->DeCommitFreeBlockThreshold = Peb->HeapDeCommitFreeBlockThreshold;
01381         if (!Parameters->DeCommitTotalFreeThreshold) Parameters->DeCommitTotalFreeThreshold = Peb->HeapDeCommitTotalFreeThreshold;
01382     }
01383     else
01384     {
01385         /* Apply defaults for non-set parameters */
01386 #if 0
01387         if (!Parameters->SegmentCommit) Parameters->SegmentCommit = MmHeapSegmentCommit;
01388         if (!Parameters->SegmentReserve) Parameters->SegmentReserve = MmHeapSegmentReserve;
01389         if (!Parameters->DeCommitFreeBlockThreshold) Parameters->DeCommitFreeBlockThreshold = MmHeapDeCommitFreeBlockThreshold;
01390         if (!Parameters->DeCommitTotalFreeThreshold) Parameters->DeCommitTotalFreeThreshold = MmHeapDeCommitTotalFreeThreshold;
01391 #endif
01392     }
01393 
01394     // FIXME: Move to memory manager
01395         if (!Parameters->SegmentCommit) Parameters->SegmentCommit = PAGE_SIZE * 2;
01396         if (!Parameters->SegmentReserve) Parameters->SegmentReserve = 1048576;
01397         if (!Parameters->DeCommitFreeBlockThreshold) Parameters->DeCommitFreeBlockThreshold = PAGE_SIZE;
01398         if (!Parameters->DeCommitTotalFreeThreshold) Parameters->DeCommitTotalFreeThreshold = 65536;
01399 
01400     /* Get the max um address */
01401     Status = ZwQuerySystemInformation(SystemBasicInformation,
01402                                       &SystemInformation,
01403                                       sizeof(SystemInformation),
01404                                       NULL);
01405 
01406     if (!NT_SUCCESS(Status))
01407     {
01408         DPRINT1("Getting max usermode address failed with status 0x%08x\n", Status);
01409         return NULL;
01410     }
01411 
01412     MaximumUserModeAddress = SystemInformation.MaximumUserModeAddress;
01413 
01414     /* Calculate max alloc size */
01415     if (!Parameters->MaximumAllocationSize)
01416         Parameters->MaximumAllocationSize = MaximumUserModeAddress - (ULONG_PTR)0x10000 - PAGE_SIZE;
01417 
01418     MaxBlockSize = 0x80000 - PAGE_SIZE;
01419 
01420     if (!Parameters->VirtualMemoryThreshold ||
01421         Parameters->VirtualMemoryThreshold > MaxBlockSize)
01422     {
01423         Parameters->VirtualMemoryThreshold = MaxBlockSize;
01424     }
01425 
01426     /* Check reserve/commit sizes and set default values */
01427     if (!CommitSize)
01428     {
01429         CommitSize = PAGE_SIZE;
01430         if (TotalSize)
01431             TotalSize = ROUND_UP(TotalSize, PAGE_SIZE);
01432         else
01433             TotalSize = 64 * PAGE_SIZE;
01434     }
01435     else
01436     {
01437         /* Round up the commit size to be at least the page size */
01438         CommitSize = ROUND_UP(CommitSize, PAGE_SIZE);
01439 
01440         if (TotalSize)
01441             TotalSize = ROUND_UP(TotalSize, PAGE_SIZE);
01442         else
01443             TotalSize = ROUND_UP(CommitSize, 16 * PAGE_SIZE);
01444     }
01445 
01446     /* Call special heap */
01447     if (RtlpHeapIsSpecial(Flags))
01448         return RtlDebugCreateHeap(Flags, Addr, TotalSize, CommitSize, Lock, Parameters);
01449 
01450     /* Without serialization, a lock makes no sense */
01451     if ((Flags & HEAP_NO_SERIALIZE) && (Lock != NULL))
01452         return NULL;
01453 
01454     /* See if we are already provided with an address for the heap */
01455     if (Addr)
01456     {
01457         if (Parameters->CommitRoutine)
01458         {
01459             /* There is a commit routine, so no problem here, check params */
01460             if ((Flags & HEAP_GROWABLE) ||
01461                 !Parameters->InitialCommit ||
01462                 !Parameters->InitialReserve ||
01463                 (Parameters->InitialCommit > Parameters->InitialReserve))
01464             {
01465                 /* Fail */
01466                 return NULL;
01467             }
01468 
01469             /* Calculate committed and uncommitted addresses */
01470             CommittedAddress = Addr;
01471             UncommittedAddress = (PCHAR)Addr + Parameters->InitialCommit;
01472             TotalSize = Parameters->InitialReserve;
01473 
01474             /* Zero the initial page ourselves */
01475             RtlZeroMemory(CommittedAddress, PAGE_SIZE);
01476         }
01477         else
01478         {
01479             /* Commit routine is absent, so query how much memory caller reserved */
01480             Status = ZwQueryVirtualMemory(NtCurrentProcess(),
01481                                           Addr,
01482                                           MemoryBasicInformation,
01483                                           &MemoryInfo,
01484                                           sizeof(MemoryInfo),
01485                                           NULL);
01486 
01487             if (!NT_SUCCESS(Status))
01488             {
01489                 DPRINT1("Querying amount of user supplied memory failed with status 0x%08X\n", Status);
01490                 return NULL;
01491             }
01492 
01493             /* Validate it */
01494             if (MemoryInfo.BaseAddress != Addr ||
01495                 MemoryInfo.State == MEM_FREE)
01496             {
01497                 return NULL;
01498             }
01499 
01500             /* Validation checks passed, set committed/uncommitted addresses */
01501             CommittedAddress = Addr;
01502 
01503             /* Check if it's committed or not */
01504             if (MemoryInfo.State == MEM_COMMIT)
01505             {
01506                 /* Zero it out because it's already committed */
01507                 RtlZeroMemory(CommittedAddress, PAGE_SIZE);
01508 
01509                 /* Calculate uncommitted address value */
01510                 CommitSize = MemoryInfo.RegionSize;
01511                 TotalSize = CommitSize;
01512                 UncommittedAddress = (PCHAR)Addr + CommitSize;
01513 
01514                 /* Check if uncommitted address is reserved */
01515                 Status = ZwQueryVirtualMemory(NtCurrentProcess(),
01516                                               UncommittedAddress,
01517                                               MemoryBasicInformation,
01518                                               &MemoryInfo,
01519                                               sizeof(MemoryInfo),
01520                                               NULL);
01521 
01522                 if (NT_SUCCESS(Status) &&
01523                     MemoryInfo.State == MEM_RESERVE)
01524                 {
01525                     /* It is, so add it up to the reserve size */
01526                     TotalSize += MemoryInfo.RegionSize;
01527                 }
01528             }
01529             else
01530             {
01531                 /* It's not committed, inform following code that a commit is necessary */
01532                 CommitSize = PAGE_SIZE;
01533                 UncommittedAddress = Addr;
01534             }
01535         }
01536 
01537         /* Mark this as a user-committed mem */
01538         HeapSegmentFlags = HEAP_USER_ALLOCATED;
01539         Heap = (PHEAP)Addr;
01540     }
01541     else
01542     {
01543         /* Check commit routine */
01544         if (Parameters->CommitRoutine) return NULL;
01545 
01546         /* Reserve memory */
01547         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
01548                                          (PVOID *)&Heap,
01549                                          0,
01550                                          &TotalSize,
01551                                          MEM_RESERVE,
01552                                          PAGE_READWRITE);
01553 
01554         if (!NT_SUCCESS(Status))
01555         {
01556             DPRINT1("Failed to reserve memory with status 0x%08x\n", Status);
01557             return NULL;
01558         }
01559 
01560         /* Set base addresses */
01561         CommittedAddress = Heap;
01562         UncommittedAddress = Heap;
01563     }
01564 
01565     /* Check if we need to commit something */
01566     if (CommittedAddress == UncommittedAddress)
01567     {
01568         /* Commit the required size */
01569         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
01570                                          &CommittedAddress,
01571                                          0,
01572                                          &CommitSize,
01573                                          MEM_COMMIT,
01574                                          PAGE_READWRITE);
01575 
01576         DPRINT("Committed %d bytes at base %p\n", CommitSize, CommittedAddress);
01577 
01578         if (!NT_SUCCESS(Status))
01579         {
01580             DPRINT1("Failure, Status 0x%08X\n", Status);
01581 
01582             /* Release memory if it was reserved */
01583             if (!Addr) ZwFreeVirtualMemory(NtCurrentProcess(),
01584                                            (PVOID *)&Heap,
01585                                            &TotalSize,
01586                                            MEM_RELEASE);
01587 
01588             return NULL;
01589         }
01590 
01591         /* Calculate new uncommitted address */
01592         UncommittedAddress = (PCHAR)UncommittedAddress + CommitSize;
01593     }
01594 
01595     /* Initialize the heap */
01596     Status = RtlpInitializeHeap(Heap, Flags, Lock, Parameters);
01597     if (!NT_SUCCESS(Status))
01598     {
01599         DPRINT1("Failed to initialize heap (%x)\n", Status);
01600         return NULL;
01601     }
01602 
01603     /* Initialize heap's first segment */
01604     Status = RtlpInitializeHeapSegment(Heap, (PHEAP_SEGMENT) (Heap), 0, HeapSegmentFlags, TotalSize, CommitSize);
01605     if (!NT_SUCCESS(Status))
01606     {
01607         DPRINT1("Failed to initialize heap segment (%x)\n", Status);
01608         return NULL;
01609     }
01610 
01611     DPRINT("Created heap %p, CommitSize %x, ReserveSize %x\n", Heap, CommitSize, TotalSize);
01612 
01613     /* Add heap to process list in case of usermode heap */
01614     if (RtlpGetMode() == UserMode)
01615     {
01616         RtlpAddHeapToProcessList(Heap);
01617 
01618         // FIXME: What about lookasides?
01619     }
01620 
01621     return Heap;
01622 }
01623 
01624 /***********************************************************************
01625  *           RtlDestroyHeap
01626  * RETURNS
01627  * TRUE: Success
01628  * FALSE: Failure
01629  *
01630  * @implemented
01631  *
01632  * RETURNS
01633  *  Success: A NULL HANDLE, if heap is NULL or it was destroyed
01634  *  Failure: The Heap handle, if heap is the process heap.
01635  */
01636 HANDLE NTAPI
01637 RtlDestroyHeap(HANDLE HeapPtr) /* [in] Handle of heap */
01638 {
01639     PHEAP Heap = (PHEAP)HeapPtr;
01640     PLIST_ENTRY Current;
01641     PHEAP_UCR_SEGMENT UcrSegment;
01642     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
01643     PVOID BaseAddress;
01644     SIZE_T Size;
01645     LONG i;
01646     PHEAP_SEGMENT Segment;
01647 
01648     if (!HeapPtr) return NULL;
01649 
01650     /* Call page heap routine if required */
01651     if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) return RtlpPageHeapDestroy(HeapPtr);
01652 
01653     /* Call special heap */
01654     if (RtlpHeapIsSpecial(Heap->Flags))
01655     {
01656         if (!RtlDebugDestroyHeap(Heap)) return HeapPtr;
01657     }
01658 
01659     /* Check for a process heap */
01660     if (RtlpGetMode() == UserMode &&
01661         HeapPtr == NtCurrentPeb()->ProcessHeap) return HeapPtr;
01662 
01663     /* Free up all big allocations */
01664     Current = Heap->VirtualAllocdBlocks.Flink;
01665     while (Current != &Heap->VirtualAllocdBlocks)
01666     {
01667         VirtualEntry = CONTAINING_RECORD(Current, HEAP_VIRTUAL_ALLOC_ENTRY, Entry);
01668         BaseAddress = (PVOID)VirtualEntry;
01669         Current = Current->Flink;
01670         Size = 0;
01671         ZwFreeVirtualMemory(NtCurrentProcess(),
01672                             &BaseAddress,
01673                             &Size,
01674                             MEM_RELEASE);
01675     }
01676 
01677     /* Delete tags and remove heap from the process heaps list in user mode */
01678     if (RtlpGetMode() == UserMode)
01679     {
01680         // FIXME DestroyTags
01681         RtlpRemoveHeapFromProcessList(Heap);
01682     }
01683 
01684     /* Delete the heap lock */
01685     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
01686     {
01687         /* Delete it if it wasn't user allocated */
01688         if (!(Heap->Flags & HEAP_LOCK_USER_ALLOCATED))
01689             RtlDeleteHeapLock(Heap->LockVariable);
01690 
01691         /* Clear out the lock variable */
01692         Heap->LockVariable = NULL;
01693     }
01694 
01695     /* Free UCR segments if any were created */
01696     Current = Heap->UCRSegments.Flink;
01697     while (Current != &Heap->UCRSegments)
01698     {
01699         UcrSegment = CONTAINING_RECORD(Current, HEAP_UCR_SEGMENT, ListEntry);
01700 
01701         /* Advance to the next descriptor */
01702         Current = Current->Flink;
01703 
01704         BaseAddress = (PVOID)UcrSegment;
01705         Size = 0;
01706 
01707         /* Release that memory */
01708         ZwFreeVirtualMemory(NtCurrentProcess(),
01709                             &BaseAddress,
01710                             &Size,
01711                             MEM_RELEASE);
01712     }
01713 
01714     /* Go through segments and destroy them */
01715     for (i = HEAP_SEGMENTS - 1; i >= 0; i--)
01716     {
01717         Segment = Heap->Segments[i];
01718         if (Segment) RtlpDestroyHeapSegment(Segment);
01719     }
01720 
01721     return NULL;
01722 }
01723 
01724 PHEAP_ENTRY NTAPI
01725 RtlpSplitEntry(PHEAP Heap,
01726                ULONG Flags,
01727                PHEAP_FREE_ENTRY FreeBlock,
01728                SIZE_T AllocationSize,
01729                SIZE_T Index,
01730                SIZE_T Size)
01731 {
01732     PHEAP_FREE_ENTRY SplitBlock, SplitBlock2;
01733     UCHAR FreeFlags, EntryFlags = HEAP_ENTRY_BUSY;
01734     PHEAP_ENTRY InUseEntry;
01735     SIZE_T FreeSize;
01736 
01737     /* Add extra flags in case of settable user value feature is requested,
01738        or there is a tag (small or normal) or there is a request to
01739        capture stack backtraces */
01740     if ((Flags & HEAP_EXTRA_FLAGS_MASK) ||
01741         Heap->PseudoTagEntries)
01742     {
01743         /* Add flag which means that the entry will have extra stuff attached */
01744         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
01745 
01746         /* NB! AllocationSize is already adjusted by RtlAllocateHeap */
01747     }
01748 
01749     /* Add settable user flags, if any */
01750     EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4;
01751 
01752     /* Save flags, update total free size */
01753     FreeFlags = FreeBlock->Flags;
01754     Heap->TotalFreeSize -= FreeBlock->Size;
01755 
01756     /* Make this block an in-use one */
01757     InUseEntry = (PHEAP_ENTRY)FreeBlock;
01758     InUseEntry->Flags = EntryFlags;
01759     InUseEntry->SmallTagIndex = 0;
01760 
01761     /* Calculate the extra amount */
01762     FreeSize = InUseEntry->Size - Index;
01763 
01764     /* Update it's size fields (we don't need their data anymore) */
01765     InUseEntry->Size = (USHORT)Index;
01766     InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
01767 
01768     /* If there is something to split - do the split */
01769     if (FreeSize != 0)
01770     {
01771         /* Don't split if resulting entry can't contain any payload data
01772         (i.e. being just HEAP_ENTRY_SIZE) */
01773         if (FreeSize == 1)
01774         {
01775             /* Increase sizes of the in-use entry */
01776             InUseEntry->Size++;
01777             InUseEntry->UnusedBytes += sizeof(HEAP_ENTRY);
01778         }
01779         else
01780         {
01781             /* Calculate a pointer to the new entry */
01782             SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
01783 
01784             /* Initialize it */
01785             SplitBlock->Flags = FreeFlags;
01786             SplitBlock->SegmentOffset = InUseEntry->SegmentOffset;
01787             SplitBlock->Size = (USHORT)FreeSize;
01788             SplitBlock->PreviousSize = (USHORT)Index;
01789 
01790             /* Check if it's the last entry */
01791             if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
01792             {
01793                 /* Insert it to the free list if it's the last entry */
01794                 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
01795                 Heap->TotalFreeSize += FreeSize;
01796             }
01797             else
01798             {
01799                 /* Not so easy - need to update next's previous size too */
01800                 SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
01801 
01802                 if (SplitBlock2->Flags & HEAP_ENTRY_BUSY)
01803                 {
01804                     SplitBlock2->PreviousSize = (USHORT)FreeSize;
01805                     RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
01806                     Heap->TotalFreeSize += FreeSize;
01807                 }
01808                 else
01809                 {
01810                     /* Even more complex - the next entry is free, so we can merge them into one! */
01811                     SplitBlock->Flags = SplitBlock2->Flags;
01812 
01813                     /* Remove that next entry */
01814                     RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE, FALSE);
01815 
01816                     /* Update sizes */
01817                     FreeSize += SplitBlock2->Size;
01818                     Heap->TotalFreeSize -= SplitBlock2->Size;
01819 
01820                     if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
01821                     {
01822                         /* Insert it back */
01823                         SplitBlock->Size = (USHORT)FreeSize;
01824 
01825                         /* Don't forget to update previous size of the next entry! */
01826                         if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY))
01827                         {
01828                             ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
01829                         }
01830 
01831                         /* Actually insert it */
01832                         RtlpInsertFreeBlockHelper(Heap, SplitBlock, (USHORT)FreeSize, FALSE);
01833 
01834                         /* Update total size */
01835                         Heap->TotalFreeSize += FreeSize;
01836                     }
01837                     else
01838                     {
01839                         /* Resulting block is quite big */
01840                         RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize);
01841                     }
01842                 }
01843             }
01844 
01845             /* Reset flags of the free entry */
01846             FreeFlags = 0;
01847         }
01848     }
01849 
01850     /* Set last entry flag */
01851     if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
01852         InUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY;
01853 
01854     return InUseEntry;
01855 }
01856 
01857 PVOID NTAPI
01858 RtlpAllocateNonDedicated(PHEAP Heap,
01859                          ULONG Flags,
01860                          SIZE_T Size,
01861                          SIZE_T AllocationSize,
01862                          SIZE_T Index,
01863                          BOOLEAN HeapLocked)
01864 {
01865     PLIST_ENTRY FreeListHead, Next;
01866     PHEAP_FREE_ENTRY FreeBlock;
01867     PHEAP_ENTRY InUseEntry;
01868     PHEAP_ENTRY_EXTRA Extra;
01869     EXCEPTION_RECORD ExceptionRecord;
01870 
01871     /* Go through the zero list to find a place where to insert the new entry */
01872     FreeListHead = &Heap->FreeLists[0];
01873 
01874     /* Start from the largest block to reduce time */
01875     Next = FreeListHead->Blink;
01876     if (FreeListHead != Next)
01877     {
01878         FreeBlock = CONTAINING_RECORD(Next, HEAP_FREE_ENTRY, FreeList);
01879 
01880         if (FreeBlock->Size >= Index)
01881         {
01882             /* Our request is smaller than the largest entry in the zero list */
01883 
01884             /* Go through the list to find insertion place */
01885             Next = FreeListHead->Flink;
01886             while (FreeListHead != Next)
01887             {
01888                 FreeBlock = CONTAINING_RECORD(Next, HEAP_FREE_ENTRY, FreeList);
01889 
01890                 if (FreeBlock->Size >= Index)
01891                 {
01892                     /* Found minimally fitting entry. Proceed to either using it as it is
01893                     or splitting it to two entries */
01894                     RemoveEntryList(&FreeBlock->FreeList);
01895 
01896                     /* Split it */
01897                     InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
01898 
01899                     /* Release the lock */
01900                     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
01901 
01902                     /* Zero memory if that was requested */
01903                     if (Flags & HEAP_ZERO_MEMORY)
01904                         RtlZeroMemory(InUseEntry + 1, Size);
01905                     else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
01906                     {
01907                         /* Fill this block with a special pattern */
01908                         RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
01909                     }
01910 
01911                     /* Fill tail of the block with a special pattern too if requested */
01912                     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
01913                     {
01914                         RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
01915                         InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
01916                     }
01917 
01918                     /* Prepare extra if it's present */
01919                     if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
01920                     {
01921                         Extra = RtlpGetExtraStuffPointer(InUseEntry);
01922                         RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
01923 
01924                         // TODO: Tagging
01925                     }
01926 
01927                     /* Return pointer to the */
01928                     return InUseEntry + 1;
01929                 }
01930 
01931                 /* Advance to the next entry */
01932                 Next = Next->Flink;
01933             }
01934         }
01935     }
01936 
01937     /* Extend the heap, 0 list didn't have anything suitable */
01938     FreeBlock = RtlpExtendHeap(Heap, AllocationSize);
01939 
01940     /* Use the new biggest entry we've got */
01941     if (FreeBlock)
01942     {
01943         RemoveEntryList(&FreeBlock->FreeList);
01944 
01945         /* Split it */
01946         InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
01947 
01948         /* Release the lock */
01949         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
01950 
01951         /* Zero memory if that was requested */
01952         if (Flags & HEAP_ZERO_MEMORY)
01953             RtlZeroMemory(InUseEntry + 1, Size);
01954         else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
01955         {
01956             /* Fill this block with a special pattern */
01957             RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
01958         }
01959 
01960         /* Fill tail of the block with a special pattern too if requested */
01961         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
01962         {
01963             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
01964             InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
01965         }
01966 
01967         /* Prepare extra if it's present */
01968         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
01969         {
01970             Extra = RtlpGetExtraStuffPointer(InUseEntry);
01971             RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
01972 
01973             // TODO: Tagging
01974         }
01975 
01976         /* Return pointer to the */
01977         return InUseEntry + 1;
01978     }
01979 
01980     /* Really unfortunate, out of memory condition */
01981     RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
01982 
01983     /* Generate an exception */
01984     if (Flags & HEAP_GENERATE_EXCEPTIONS)
01985     {
01986         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
01987         ExceptionRecord.ExceptionRecord = NULL;
01988         ExceptionRecord.NumberParameters = 1;
01989         ExceptionRecord.ExceptionFlags = 0;
01990         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
01991 
01992         RtlRaiseException(&ExceptionRecord);
01993     }
01994 
01995     /* Release the lock */
01996     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
01997     DPRINT1("HEAP: Allocation failed!\n");
01998     DPRINT1("Flags %x\n", Heap->Flags);
01999     return NULL;
02000 }
02001 
02002 /***********************************************************************
02003  *           HeapAlloc   (KERNEL32.334)
02004  * RETURNS
02005  * Pointer to allocated memory block
02006  * NULL: Failure
02007  * 0x7d030f60--invalid flags in RtlHeapAllocate
02008  * @implemented
02009  */
02010 PVOID NTAPI
02011 RtlAllocateHeap(IN PVOID HeapPtr,
02012                 IN ULONG Flags,
02013                 IN SIZE_T Size)
02014 {
02015     PHEAP Heap = (PHEAP)HeapPtr;
02016     PULONG FreeListsInUse;
02017     ULONG FreeListsInUseUlong;
02018     SIZE_T AllocationSize;
02019     SIZE_T Index, InUseIndex, i;
02020     PLIST_ENTRY FreeListHead;
02021     PHEAP_ENTRY InUseEntry;
02022     PHEAP_FREE_ENTRY FreeBlock;
02023     UCHAR FreeFlags, EntryFlags = HEAP_ENTRY_BUSY;
02024     EXCEPTION_RECORD ExceptionRecord;
02025     BOOLEAN HeapLocked = FALSE;
02026     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualBlock = NULL;
02027     PHEAP_ENTRY_EXTRA Extra;
02028     NTSTATUS Status;
02029 
02030     /* Force flags */
02031     Flags |= Heap->ForceFlags;
02032 
02033     /* Call special heap */
02034     if (RtlpHeapIsSpecial(Flags))
02035         return RtlDebugAllocateHeap(Heap, Flags, Size);
02036 
02037     /* Check for the maximum size */
02038     if (Size >= 0x80000000)
02039     {
02040         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
02041         DPRINT1("HEAP: Allocation failed!\n");
02042         return NULL;
02043     }
02044 
02045     if (Flags & (HEAP_CREATE_ENABLE_TRACING |
02046                  HEAP_CREATE_ALIGN_16))
02047     {
02048         DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags);
02049     }
02050 
02051     //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size);
02052 
02053     /* Calculate allocation size and index */
02054     if (Size)
02055         AllocationSize = Size;
02056     else
02057         AllocationSize = 1;
02058     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
02059 
02060     /* Add extra flags in case of settable user value feature is requested,
02061        or there is a tag (small or normal) or there is a request to
02062        capture stack backtraces */
02063     if ((Flags & HEAP_EXTRA_FLAGS_MASK) ||
02064         Heap->PseudoTagEntries)
02065     {
02066         /* Add flag which means that the entry will have extra stuff attached */
02067         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
02068 
02069         /* Account for extra stuff size */
02070         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
02071     }
02072 
02073     /* Add settable user flags, if any */
02074     EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4;
02075 
02076     Index = AllocationSize >>  HEAP_ENTRY_SHIFT;
02077 
02078     /* Acquire the lock if necessary */
02079     if (!(Flags & HEAP_NO_SERIALIZE))
02080     {
02081         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02082         HeapLocked = TRUE;
02083     }
02084 
02085     /* Depending on the size, the allocation is going to be done from dedicated,
02086        non-dedicated lists or a virtual block of memory */
02087     if (Index < HEAP_FREELISTS)
02088     {
02089         FreeListHead = &Heap->FreeLists[Index];
02090 
02091         if (!IsListEmpty(FreeListHead))
02092         {
02093             /* There is a free entry in this list */
02094             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
02095                                           HEAP_FREE_ENTRY,
02096                                           FreeList);
02097 
02098             /* Save flags and remove the free entry */
02099             FreeFlags = FreeBlock->Flags;
02100             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
02101 
02102             /* Update the total free size of the heap */
02103             Heap->TotalFreeSize -= Index;
02104 
02105             /* Initialize this block */
02106             InUseEntry = (PHEAP_ENTRY)FreeBlock;
02107             InUseEntry->Flags = EntryFlags | (FreeFlags & HEAP_ENTRY_LAST_ENTRY);
02108             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
02109             InUseEntry->SmallTagIndex = 0;
02110         }
02111         else
02112         {
02113             /* Find smallest free block which this request could fit in */
02114             InUseIndex = Index >> 5;
02115             FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex];
02116 
02117             /* This bit magic disables all sizes which are less than the requested allocation size */
02118             FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << ((ULONG)Index & 0x1f)) - 1);
02119 
02120             /* If size is definitily more than our lists - go directly to the non-dedicated one */
02121             if (InUseIndex > 3)
02122                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02123 
02124             /* Go through the list */
02125             for (i = InUseIndex; i < 4; i++)
02126             {
02127                 if (FreeListsInUseUlong)
02128                 {
02129                     FreeListHead = &Heap->FreeLists[i * 32];
02130                     break;
02131                 }
02132 
02133                 if (i < 3) FreeListsInUseUlong = *FreeListsInUse++;
02134             }
02135 
02136             /* Nothing found, search in the non-dedicated list */
02137             if (i == 4)
02138                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02139 
02140             /* That list is found, now calculate exact block  */
02141             FreeListHead += RtlpFindLeastSetBit(FreeListsInUseUlong);
02142 
02143             /* Take this entry and remove it from the list of free blocks */
02144             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
02145                                           HEAP_FREE_ENTRY,
02146                                           FreeList);
02147             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
02148 
02149             /* Split it */
02150             InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
02151         }
02152 
02153         /* Release the lock */
02154         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02155 
02156         /* Zero memory if that was requested */
02157         if (Flags & HEAP_ZERO_MEMORY)
02158             RtlZeroMemory(InUseEntry + 1, Size);
02159         else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02160         {
02161             /* Fill this block with a special pattern */
02162             RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
02163         }
02164 
02165         /* Fill tail of the block with a special pattern too if requested */
02166         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02167         {
02168             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
02169             InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
02170         }
02171 
02172         /* Prepare extra if it's present */
02173         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02174         {
02175             Extra = RtlpGetExtraStuffPointer(InUseEntry);
02176             RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
02177 
02178             // TODO: Tagging
02179         }
02180 
02181         /* User data starts right after the entry's header */
02182         return InUseEntry + 1;
02183     }
02184     else if (Index <= Heap->VirtualMemoryThreshold)
02185     {
02186         /* The block is too large for dedicated lists, but fine for a non-dedicated one */
02187         return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02188     }
02189     else if (Heap->Flags & HEAP_GROWABLE)
02190     {
02191         /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */
02192         AllocationSize += sizeof(HEAP_VIRTUAL_ALLOC_ENTRY) - sizeof(HEAP_ENTRY);
02193 
02194         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
02195                                          (PVOID *)&VirtualBlock,
02196                                          0,
02197                                          &AllocationSize,
02198                                          MEM_COMMIT,
02199                                          PAGE_READWRITE);
02200 
02201         if (!NT_SUCCESS(Status))
02202         {
02203             // Set STATUS!
02204             /* Release the lock */
02205             if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02206             DPRINT1("HEAP: Allocation failed!\n");
02207             return NULL;
02208         }
02209 
02210         /* Initialize the newly allocated block */
02211         VirtualBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size);
02212         VirtualBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT;
02213         VirtualBlock->CommitSize = AllocationSize;
02214         VirtualBlock->ReserveSize = AllocationSize;
02215 
02216         /* Insert it into the list of virtual allocations */
02217         InsertTailList(&Heap->VirtualAllocdBlocks, &VirtualBlock->Entry);
02218 
02219         /* Release the lock */
02220         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02221 
02222         /* Return pointer to user data */
02223         return VirtualBlock + 1;
02224     }
02225 
02226     /* Generate an exception */
02227     if (Flags & HEAP_GENERATE_EXCEPTIONS)
02228     {
02229         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
02230         ExceptionRecord.ExceptionRecord = NULL;
02231         ExceptionRecord.NumberParameters = 1;
02232         ExceptionRecord.ExceptionFlags = 0;
02233         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
02234 
02235         RtlRaiseException(&ExceptionRecord);
02236     }
02237 
02238     RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL);
02239 
02240     /* Release the lock */
02241     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02242     DPRINT1("HEAP: Allocation failed!\n");
02243     return NULL;
02244 }
02245 
02246 
02247 /***********************************************************************
02248  *           HeapFree   (KERNEL32.338)
02249  * RETURNS
02250  * TRUE: Success
02251  * FALSE: Failure
02252  *
02253  * @implemented
02254  */
02255 BOOLEAN NTAPI RtlFreeHeap(
02256    HANDLE HeapPtr, /* [in] Handle of heap */
02257    ULONG Flags,   /* [in] Heap freeing flags */
02258    PVOID Ptr     /* [in] Address of memory to free */
02259 )
02260 {
02261     PHEAP Heap;
02262     PHEAP_ENTRY HeapEntry;
02263     USHORT TagIndex = 0;
02264     SIZE_T BlockSize;
02265     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
02266     BOOLEAN Locked = FALSE;
02267     NTSTATUS Status;
02268 
02269     /* Freeing NULL pointer is a legal operation */
02270     if (!Ptr) return TRUE;
02271 
02272     /* Get pointer to the heap and force flags */
02273     Heap = (PHEAP)HeapPtr;
02274     Flags |= Heap->ForceFlags;
02275 
02276     /* Call special heap */
02277     if (RtlpHeapIsSpecial(Flags))
02278         return RtlDebugFreeHeap(Heap, Flags, Ptr);
02279 
02280     /* Lock if necessary */
02281     if (!(Flags & HEAP_NO_SERIALIZE))
02282     {
02283         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02284         Locked = TRUE;
02285     }
02286 
02287     /* Get pointer to the heap entry */
02288     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
02289 
02290     /* Check this entry, fail if it's invalid */
02291     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY) ||
02292         (((ULONG_PTR)Ptr & 0x7) != 0) ||
02293         (HeapEntry->SegmentOffset >= HEAP_SEGMENTS))
02294     {
02295         /* This is an invalid block */
02296         DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr);
02297         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
02298 
02299         /* Release the heap lock */
02300         if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
02301         return FALSE;
02302     }
02303 
02304     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02305     {
02306         /* Big allocation */
02307         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02308 
02309         /* Remove it from the list */
02310         RemoveEntryList(&VirtualEntry->Entry);
02311 
02312         // TODO: Tagging
02313 
02314         BlockSize = 0;
02315         Status = ZwFreeVirtualMemory(NtCurrentProcess(),
02316                                      (PVOID *)&VirtualEntry,
02317                                      &BlockSize,
02318                                      MEM_RELEASE);
02319 
02320         if (!NT_SUCCESS(Status))
02321         {
02322             DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n",
02323                 Status, Heap, Ptr, VirtualEntry);
02324             RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status);
02325         }
02326     }
02327     else
02328     {
02329         /* Normal allocation */
02330         BlockSize = HeapEntry->Size;
02331 
02332         // TODO: Tagging
02333 
02334         /* Coalesce in kernel mode, and in usermode if it's not disabled */
02335         if (RtlpGetMode() == KernelMode ||
02336             (RtlpGetMode() == UserMode && !(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)))
02337         {
02338             HeapEntry = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks(Heap,
02339                                                            (PHEAP_FREE_ENTRY)HeapEntry,
02340                                                            &BlockSize,
02341                                                            FALSE);
02342         }
02343 
02344         /* If there is no need to decommit the block - put it into a free list */
02345         if (BlockSize < Heap->DeCommitFreeBlockThreshold ||
02346             (Heap->TotalFreeSize + BlockSize < Heap->DeCommitTotalFreeThreshold))
02347         {
02348             /* Check if it needs to go to a 0 list */
02349             if (BlockSize > HEAP_MAX_BLOCK_SIZE)
02350             {
02351                 /* General-purpose 0 list */
02352                 RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
02353             }
02354             else
02355             {
02356                 /* Usual free list */
02357                 RtlpInsertFreeBlockHelper(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize, FALSE);
02358 
02359                 /* Assert sizes are consistent */
02360                 if (!(HeapEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
02361                 {
02362                     ASSERT((HeapEntry + BlockSize)->PreviousSize == BlockSize);
02363                 }
02364 
02365                 /* Increase the free size */
02366                 Heap->TotalFreeSize += BlockSize;
02367             }
02368 
02369 
02370             if (RtlpGetMode() == UserMode &&
02371                 TagIndex != 0)
02372             {
02373                 // FIXME: Tagging
02374                 UNIMPLEMENTED;
02375             }
02376         }
02377         else
02378         {
02379             /* Decommit this block */
02380             RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
02381         }
02382     }
02383 
02384     /* Release the heap lock */
02385     if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
02386 
02387     return TRUE;
02388 }
02389 
02390 BOOLEAN NTAPI
02391 RtlpGrowBlockInPlace (IN PHEAP Heap,
02392                       IN ULONG Flags,
02393                       IN PHEAP_ENTRY InUseEntry,
02394                       IN SIZE_T Size,
02395                       IN SIZE_T Index)
02396 {
02397     UCHAR EntryFlags, RememberFlags;
02398     PHEAP_FREE_ENTRY FreeEntry, UnusedEntry, FollowingEntry;
02399     SIZE_T FreeSize, PrevSize, TailPart, AddedSize = 0;
02400     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
02401 
02402     /* We can't grow beyond specified threshold */
02403     if (Index > Heap->VirtualMemoryThreshold)
02404         return FALSE;
02405 
02406     /* Get entry flags */
02407     EntryFlags = InUseEntry->Flags;
02408 
02409     /* Get the next free entry */
02410     FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size);
02411 
02412     if (EntryFlags & HEAP_ENTRY_LAST_ENTRY)
02413     {
02414         /* There is no next block, just uncommitted space. Calculate how much is needed */
02415         FreeSize = (Index - InUseEntry->Size) << HEAP_ENTRY_SHIFT;
02416         FreeSize = ROUND_UP(FreeSize, PAGE_SIZE);
02417 
02418         /* Find and commit those pages */
02419         FreeEntry = RtlpFindAndCommitPages(Heap,
02420                                            Heap->Segments[InUseEntry->SegmentOffset],
02421                                            &FreeSize,
02422                                            FreeEntry);
02423 
02424         /* Fail if it failed... */
02425         if (!FreeEntry) return FALSE;
02426 
02427         /* It was successful, perform coalescing */
02428         FreeSize = FreeSize >> HEAP_ENTRY_SHIFT;
02429         FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE);
02430 
02431         /* Check if it's enough */
02432         if (FreeSize + InUseEntry->Size < Index)
02433         {
02434             /* Still not enough */
02435             RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize);
02436             Heap->TotalFreeSize += FreeSize;
02437             return FALSE;
02438         }
02439 
02440         /* Remember flags of this free entry */
02441         RememberFlags = FreeEntry->Flags;
02442 
02443         /* Sum up sizes */
02444         FreeSize += InUseEntry->Size;
02445     }
02446     else
02447     {
02448         /* The next block indeed exists. Check if it's free or in use */
02449         if (FreeEntry->Flags & HEAP_ENTRY_BUSY) return FALSE;
02450 
02451         /* Next entry is free, check if it can fit the block we need */
02452         FreeSize = InUseEntry->Size + FreeEntry->Size;
02453         if (FreeSize < Index) return FALSE;
02454 
02455         /* Remember flags of this free entry */
02456         RememberFlags = FreeEntry->Flags;
02457 
02458         /* Remove this block from the free list */
02459         RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
02460         Heap->TotalFreeSize -= FreeEntry->Size;
02461     }
02462 
02463     PrevSize = (InUseEntry->Size << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
02464     FreeSize -= Index;
02465 
02466     /* Don't produce too small blocks */
02467     if (FreeSize <= 2)
02468     {
02469         Index += FreeSize;
02470         FreeSize = 0;
02471     }
02472 
02473     /* Process extra stuff */
02474     if (RememberFlags & HEAP_ENTRY_EXTRA_PRESENT)
02475     {
02476         /* Calculate pointers */
02477         OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
02478         NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
02479 
02480         /* Copy contents */
02481         *NewExtra = *OldExtra;
02482 
02483         // FIXME Tagging
02484     }
02485 
02486     /* Update sizes */
02487     InUseEntry->Size = (USHORT)Index;
02488     InUseEntry->UnusedBytes = (UCHAR)((Index << HEAP_ENTRY_SHIFT) - Size);
02489 
02490     /* Check if there is a free space remaining after merging those blocks */
02491     if (!FreeSize)
02492     {
02493         /* Update flags and sizes */
02494         InUseEntry->Flags |= RememberFlags & HEAP_ENTRY_LAST_ENTRY;
02495 
02496         /* Either update previous size of the next entry or mark it as a last
02497            entry in the segment*/
02498         if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
02499             (InUseEntry + InUseEntry->Size)->PreviousSize = InUseEntry->Size;
02500     }
02501     else
02502     {
02503         /* Complex case, we need to split the block to give unused free space
02504            back to the heap */
02505         UnusedEntry = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
02506         UnusedEntry->PreviousSize = (USHORT)Index;
02507         UnusedEntry->SegmentOffset = InUseEntry->SegmentOffset;
02508 
02509         /* Update the following block or set the last entry in the segment */
02510         if (RememberFlags & HEAP_ENTRY_LAST_ENTRY)
02511         {
02512             /* Set flags and size */
02513             UnusedEntry->Flags = RememberFlags;
02514             UnusedEntry->Size = (USHORT)FreeSize;
02515 
02516             /* Insert it to the heap and update total size  */
02517             RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02518             Heap->TotalFreeSize += FreeSize;
02519         }
02520         else
02521         {
02522             /* There is a block after this one  */
02523             FollowingEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)UnusedEntry + FreeSize);
02524 
02525             if (FollowingEntry->Flags & HEAP_ENTRY_BUSY)
02526             {
02527                 /* Update flags and set size of the unused space entry */
02528                 UnusedEntry->Flags = RememberFlags & (~HEAP_ENTRY_LAST_ENTRY);
02529                 UnusedEntry->Size = (USHORT)FreeSize;
02530 
02531                 /* Update previous size of the following entry */
02532                 FollowingEntry->PreviousSize = (USHORT)FreeSize;
02533 
02534                 /* Insert it to the heap and update total free size */
02535                 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02536                 Heap->TotalFreeSize += FreeSize;
02537             }
02538             else
02539             {
02540                 /* That following entry is also free, what a fortune! */
02541                 RememberFlags = FollowingEntry->Flags;
02542 
02543                 /* Remove it */
02544                 RtlpRemoveFreeBlock(Heap, FollowingEntry, FALSE, FALSE);
02545                 Heap->TotalFreeSize -= FollowingEntry->Size;
02546 
02547                 /* And make up a new combined block */
02548                 FreeSize += FollowingEntry->Size;
02549                 UnusedEntry->Flags = RememberFlags;
02550 
02551                 /* Check where to put it */
02552                 if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
02553                 {
02554                     /* Fine for a dedicated list */
02555                     UnusedEntry->Size = (USHORT)FreeSize;
02556 
02557                     if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
02558                         ((PHEAP_ENTRY)UnusedEntry + FreeSize)->PreviousSize = (USHORT)FreeSize;
02559 
02560                     /* Insert it back and update total size */
02561                     RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02562                     Heap->TotalFreeSize += FreeSize;
02563                 }
02564                 else
02565                 {
02566                     /* The block is very large, leave all the hassle to the insertion routine */
02567                     RtlpInsertFreeBlock(Heap, UnusedEntry, FreeSize);
02568                 }
02569             }
02570         }
02571     }
02572 
02573     /* Properly "zero out" (and fill!) the space */
02574     if (Flags & HEAP_ZERO_MEMORY)
02575     {
02576         RtlZeroMemory((PCHAR)(InUseEntry + 1) + PrevSize, Size - PrevSize);
02577     }
02578     else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02579     {
02580         /* Calculate tail part which we need to fill */
02581         TailPart = PrevSize & (sizeof(ULONG) - 1);
02582 
02583         /* "Invert" it as usual */
02584         if (TailPart) TailPart = 4 - TailPart;
02585 
02586         if (Size > (PrevSize + TailPart))
02587             AddedSize = (Size - (PrevSize + TailPart)) & ~(sizeof(ULONG) - 1);
02588 
02589         if (AddedSize)
02590         {
02591             RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + PrevSize + TailPart,
02592                                AddedSize,
02593                                ARENA_INUSE_FILLER);
02594         }
02595     }
02596 
02597     /* Fill the new tail */
02598     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02599     {
02600         RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
02601                       HEAP_ENTRY_SIZE,
02602                       HEAP_TAIL_FILL);
02603     }
02604 
02605     /* Copy user settable flags */
02606     InUseEntry->Flags &= ~HEAP_ENTRY_SETTABLE_FLAGS;
02607     InUseEntry->Flags |= ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4);
02608 
02609     /* Return success */
02610     return TRUE;
02611 }
02612 
02613 PHEAP_ENTRY_EXTRA NTAPI
02614 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry)
02615 {
02616     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
02617 
02618     /* Check if it's a big block */
02619     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02620     {
02621         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02622 
02623         /* Return a pointer to the extra stuff*/
02624         return &VirtualEntry->ExtraStuff;
02625     }
02626     else
02627     {
02628         /* This is a usual entry, which means extra stuff follows this block */
02629         return (PHEAP_ENTRY_EXTRA)(HeapEntry + HeapEntry->Size - 1);
02630     }
02631 }
02632 
02633 
02634 /***********************************************************************
02635  *           RtlReAllocateHeap
02636  * PARAMS
02637  *   Heap   [in] Handle of heap block
02638  *   Flags    [in] Heap reallocation flags
02639  *   Ptr,    [in] Address of memory to reallocate
02640  *   Size     [in] Number of bytes to reallocate
02641  *
02642  * RETURNS
02643  * Pointer to reallocated memory block
02644  * NULL: Failure
02645  * 0x7d030f60--invalid flags in RtlHeapAllocate
02646  * @implemented
02647  */
02648 PVOID NTAPI
02649 RtlReAllocateHeap(HANDLE HeapPtr,
02650                   ULONG Flags,
02651                   PVOID Ptr,
02652                   SIZE_T Size)
02653 {
02654     PHEAP Heap = (PHEAP)HeapPtr;
02655     PHEAP_ENTRY InUseEntry, NewInUseEntry;
02656     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
02657     SIZE_T AllocationSize, FreeSize, DecommitSize;
02658     BOOLEAN HeapLocked = FALSE;
02659     PVOID NewBaseAddress;
02660     PHEAP_FREE_ENTRY SplitBlock, SplitBlock2;
02661     SIZE_T OldSize, Index, OldIndex;
02662     UCHAR FreeFlags;
02663     NTSTATUS Status;
02664     PVOID DecommitBase;
02665     SIZE_T RemainderBytes, ExtraSize;
02666     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
02667     EXCEPTION_RECORD ExceptionRecord;
02668 
02669     /* Return success in case of a null pointer */
02670     if (!Ptr)
02671     {
02672         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS);
02673         return NULL;
02674     }
02675 
02676     /* Force heap flags */
02677     Flags |= Heap->ForceFlags;
02678 
02679     /* Call special heap */
02680     if (RtlpHeapIsSpecial(Flags))
02681         return RtlDebugReAllocateHeap(Heap, Flags, Ptr, Size);
02682 
02683     /* Make sure size is valid */
02684     if (Size >= 0x80000000)
02685     {
02686         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
02687         return NULL;
02688     }
02689 
02690     /* Calculate allocation size and index */
02691     if (Size)
02692         AllocationSize = Size;
02693     else
02694         AllocationSize = 1;
02695     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
02696 
02697     /* Add up extra stuff, if it is present anywhere */
02698     if (((((PHEAP_ENTRY)Ptr)-1)->Flags & HEAP_ENTRY_EXTRA_PRESENT) ||
02699         (Flags & HEAP_EXTRA_FLAGS_MASK) ||
02700         Heap->PseudoTagEntries)
02701     {
02702         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
02703     }
02704 
02705     /* Acquire the lock if necessary */
02706     if (!(Flags & HEAP_NO_SERIALIZE))
02707     {
02708         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02709         HeapLocked = TRUE;
02710         Flags &= ~HEAP_NO_SERIALIZE;
02711     }
02712 
02713     /* Get the pointer to the in-use entry */
02714     InUseEntry = (PHEAP_ENTRY)Ptr - 1;
02715 
02716     /* If that entry is not really in-use, we have a problem */
02717     if (!(InUseEntry->Flags & HEAP_ENTRY_BUSY))
02718     {
02719         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
02720 
02721         /* Release the lock and return */
02722         if (HeapLocked)
02723             RtlLeaveHeapLock(Heap->LockVariable);
02724         return Ptr;
02725     }
02726 
02727     if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02728     {
02729         /* This is a virtually allocated block. Get its size */
02730         OldSize = RtlpGetSizeOfBigBlock(InUseEntry);
02731 
02732         /* Convert it to an index */
02733         OldIndex = (OldSize + InUseEntry->Size) >> HEAP_ENTRY_SHIFT;
02734 
02735         /* Calculate new allocation size and round it to the page size */
02736         AllocationSize += FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02737         AllocationSize = ROUND_UP(AllocationSize, PAGE_SIZE);
02738     }
02739     else
02740     {
02741         /* Usual entry */
02742         OldIndex = InUseEntry->Size;
02743 
02744         OldSize = (OldIndex << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
02745     }
02746 
02747     /* Calculate new index */
02748     Index = AllocationSize >> HEAP_ENTRY_SHIFT;
02749 
02750     /* Check for 4 different scenarios (old size, new size, old index, new index) */
02751     if (Index <= OldIndex)
02752     {
02753         /* Difference must be greater than 1, adjust if it's not so */
02754         if (Index + 1 == OldIndex)
02755         {
02756             Index++;
02757             AllocationSize += sizeof(HEAP_ENTRY);
02758         }
02759 
02760         /* Calculate new size */
02761         if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02762         {
02763             /* Simple in case of a virtual alloc - just an unused size */
02764             InUseEntry->Size = (USHORT)(AllocationSize - Size);
02765         }
02766         else if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02767         {
02768             /* There is extra stuff, take it into account */
02769             OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
02770             NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
02771             *NewExtra = *OldExtra;
02772 
02773             // FIXME Tagging, TagIndex
02774 
02775             /* Update unused bytes count */
02776             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
02777         }
02778         else
02779         {
02780             // FIXME Tagging, SmallTagIndex
02781             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
02782         }
02783 
02784         /* If new size is bigger than the old size */
02785         if (Size > OldSize)
02786         {
02787             /* Zero out that additional space if required */
02788             if (Flags & HEAP_ZERO_MEMORY)
02789             {
02790                 RtlZeroMemory((PCHAR)Ptr + OldSize, Size - OldSize);
02791             }
02792             else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02793             {
02794                 /* Fill it on free if required */
02795                 RemainderBytes = OldSize & (sizeof(ULONG) - 1);
02796 
02797                 if (RemainderBytes)
02798                     RemainderBytes = 4 - RemainderBytes;
02799 
02800                 if (Size > (OldSize + RemainderBytes))
02801                 {
02802                     /* Calculate actual amount of extra bytes to fill */
02803                     ExtraSize = (Size - (OldSize + RemainderBytes)) & ~(sizeof(ULONG) - 1);
02804 
02805                     /* Fill them if there are any */
02806                     if (ExtraSize != 0)
02807                     {
02808                         RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + OldSize + RemainderBytes,
02809                                            ExtraSize,
02810                                            ARENA_INUSE_FILLER);
02811                     }
02812                 }
02813             }
02814         }
02815 
02816         /* Fill tail of the heap entry if required */
02817         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02818         {
02819             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
02820                           HEAP_ENTRY_SIZE,
02821                           HEAP_TAIL_FILL);
02822         }
02823 
02824         /* Check if the difference is significant or not */
02825         if (Index != OldIndex)
02826         {
02827             /* Save flags */
02828             FreeFlags = InUseEntry->Flags & ~HEAP_ENTRY_BUSY;
02829 
02830             if (FreeFlags & HEAP_ENTRY_VIRTUAL_ALLOC)
02831             {
02832                 /* This is a virtual block allocation */
02833                 VirtualAllocBlock = CONTAINING_RECORD(InUseEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02834 
02835                 // FIXME Tagging!
02836 
02837                 DecommitBase = (PCHAR)VirtualAllocBlock + AllocationSize;
02838                 DecommitSize = (OldIndex << HEAP_ENTRY_SHIFT) - AllocationSize;
02839 
02840                 /* Release the memory */
02841                 Status = ZwFreeVirtualMemory(NtCurrentProcess(),
02842                                              (PVOID *)&DecommitBase,
02843                                              &DecommitSize,
02844                                              MEM_RELEASE);
02845 
02846                 if (!NT_SUCCESS(Status))
02847                 {
02848                     DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase, DecommitSize, Status);
02849                 }
02850                 else
02851                 {
02852                     /* Otherwise reduce the commit size */
02853                     VirtualAllocBlock->CommitSize -= DecommitSize;
02854                 }
02855             }
02856             else
02857             {
02858                 /* Reduce size of the block and possibly split it */
02859                 SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
02860 
02861                 /* Initialize this entry */
02862                 SplitBlock->Flags = FreeFlags;
02863                 SplitBlock->PreviousSize = (USHORT)Index;
02864                 SplitBlock->SegmentOffset = InUseEntry->SegmentOffset;
02865 
02866                 /* Remember free size */
02867                 FreeSize = InUseEntry->Size - Index;
02868 
02869                 /* Set new size */
02870                 InUseEntry->Size = (USHORT)Index;
02871                 InUseEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
02872 
02873                 /* Is that the last entry */
02874                 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
02875                 {
02876                     /* Set its size and insert it to the list */
02877                     SplitBlock->Size = (USHORT)FreeSize;
02878                     RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02879 
02880                     /* Update total free size */
02881                     Heap->TotalFreeSize += FreeSize;
02882                 }
02883                 else
02884                 {
02885                     /* Get the block after that one */
02886                     SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
02887 
02888                     if (SplitBlock2->Flags & HEAP_ENTRY_BUSY)
02889                     {
02890                         /* It's in use, add it here*/
02891                         SplitBlock->Size = (USHORT)FreeSize;
02892 
02893                         /* Update previous size of the next entry */
02894                         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
02895 
02896                         /* Insert it to the list */
02897                         RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02898 
02899                         /* Update total size */
02900                         Heap->TotalFreeSize += FreeSize;
02901                     }
02902                     else
02903                     {
02904                         /* Next entry is free, so merge with it */
02905                         SplitBlock->Flags = SplitBlock2->Flags;
02906 
02907                         /* Remove it, update total size */
02908                         RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE, FALSE);
02909                         Heap->TotalFreeSize -= SplitBlock2->Size;
02910 
02911                         /* Calculate total free size */
02912                         FreeSize += SplitBlock2->Size;
02913 
02914                         if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
02915                         {
02916                             SplitBlock->Size = (USHORT)FreeSize;
02917 
02918                             if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY))
02919                             {
02920                                 /* Update previous size of the next entry */
02921                                 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
02922                             }
02923 
02924                             /* Insert the new one back and update total size */
02925                             RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02926                             Heap->TotalFreeSize += FreeSize;
02927                         }
02928                         else
02929                         {
02930                             /* Just add it */
02931                             RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize);
02932                         }
02933                     }
02934                 }
02935             }
02936         }
02937     }
02938     else
02939     {
02940         /* We're growing the block */
02941         if ((InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) ||
02942             !RtlpGrowBlockInPlace(Heap, Flags, InUseEntry, Size, Index))
02943         {
02944             /* Growing in place failed, so growing out of place */
02945             if (Flags & HEAP_REALLOC_IN_PLACE_ONLY)
02946             {
02947                 DPRINT1("Realloc in place failed, but it was the only option\n");
02948                 Ptr = NULL;
02949             }
02950             else
02951             {
02952                 /* Clear tag bits */
02953                 Flags &= ~HEAP_TAG_MASK;
02954 
02955                 /* Process extra stuff */
02956                 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02957                 {
02958                     /* Preserve user settable flags */
02959                     Flags &= ~HEAP_SETTABLE_USER_FLAGS;
02960 
02961                     Flags |= HEAP_SETTABLE_USER_VALUE | ((InUseEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4);
02962 
02963                     /* Get pointer to the old extra data */
02964                     OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
02965 
02966                     /* Save tag index if it was set */
02967                     if (OldExtra->TagIndex &&
02968                         !(OldExtra->TagIndex & HEAP_PSEUDO_TAG_FLAG))
02969                     {
02970                         Flags |= OldExtra->TagIndex << HEAP_TAG_SHIFT;
02971                     }
02972                 }
02973                 else if (InUseEntry->SmallTagIndex)
02974                 {
02975                     /* Take small tag index into account */
02976                     Flags |= InUseEntry->SmallTagIndex << HEAP_TAG_SHIFT;
02977                 }
02978 
02979                 /* Allocate new block from the heap */
02980                 NewBaseAddress = RtlAllocateHeap(HeapPtr,
02981                                                  Flags & ~HEAP_ZERO_MEMORY,
02982                                                  Size);
02983 
02984                 /* Proceed if it didn't fail */
02985                 if (NewBaseAddress)
02986                 {
02987                     /* Get new entry pointer */
02988                     NewInUseEntry = (PHEAP_ENTRY)NewBaseAddress - 1;
02989 
02990                     /* Process extra stuff if it exists */
02991                     if (NewInUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02992                     {
02993                         NewExtra = RtlpGetExtraStuffPointer(NewInUseEntry);
02994 
02995                         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02996                         {
02997                             OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
02998                             NewExtra->Settable = OldExtra->Settable;
02999                         }
03000                         else
03001                         {
03002                             RtlZeroMemory(NewExtra, sizeof(*NewExtra));
03003                         }
03004                     }
03005 
03006                     /* Copy actual user bits */
03007                     if (Size < OldSize)
03008                         RtlMoveMemory(NewBaseAddress, Ptr, Size);
03009                     else
03010                         RtlMoveMemory(NewBaseAddress, Ptr, OldSize);
03011 
03012                     /* Zero remaining part if required */
03013                     if (Size > OldSize &&
03014                         (Flags & HEAP_ZERO_MEMORY))
03015                     {
03016                         RtlZeroMemory((PCHAR)NewBaseAddress + OldSize, Size - OldSize);
03017                     }
03018 
03019                     /* Free the old block */
03020                     RtlFreeHeap(HeapPtr, Flags, Ptr);
03021                 }
03022 
03023                 Ptr = NewBaseAddress;
03024             }
03025         }
03026     }
03027 
03028     /* Did resizing fail? */
03029     if (!Ptr && (Flags & HEAP_GENERATE_EXCEPTIONS))
03030     {
03031         /* Generate an exception if required */
03032         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
03033         ExceptionRecord.ExceptionRecord = NULL;
03034         ExceptionRecord.NumberParameters = 1;
03035         ExceptionRecord.ExceptionFlags = 0;
03036         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
03037 
03038         RtlRaiseException(&ExceptionRecord);
03039     }
03040 
03041     /* Release the heap lock if it was acquired */
03042     if (HeapLocked)
03043         RtlLeaveHeapLock(Heap->LockVariable);
03044 
03045     return Ptr;
03046 }
03047 
03048 
03049 /***********************************************************************
03050  *           RtlCompactHeap
03051  *
03052  * @unimplemented
03053  */
03054 ULONG NTAPI
03055 RtlCompactHeap(HANDLE Heap,
03056         ULONG Flags)
03057 {
03058    UNIMPLEMENTED;
03059    return 0;
03060 }
03061 
03062 
03063 /***********************************************************************
03064  *           RtlLockHeap
03065  * Attempts to acquire the critical section object for a specified heap.
03066  *
03067  * PARAMS
03068  *   Heap  [in] Handle of heap to lock for exclusive access
03069  *
03070  * RETURNS
03071  * TRUE: Success
03072  * FALSE: Failure
03073  *
03074  * @implemented
03075  */
03076 BOOLEAN NTAPI
03077 RtlLockHeap(IN HANDLE HeapPtr)
03078 {
03079     PHEAP Heap = (PHEAP)HeapPtr;
03080 
03081     // FIXME Check for special heap
03082 
03083     /* Check if it's really a heap */
03084     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
03085 
03086     /* Lock if it's lockable */
03087     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03088     {
03089         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03090     }
03091 
03092     return TRUE;
03093 }
03094 
03095 
03096 /***********************************************************************
03097  *           RtlUnlockHeap
03098  * Releases ownership of the critical section object.
03099  *
03100  * PARAMS
03101  *   Heap  [in] Handle to the heap to unlock
03102  *
03103  * RETURNS
03104  * TRUE: Success
03105  * FALSE: Failure
03106  *
03107  * @implemented
03108  */
03109 BOOLEAN NTAPI
03110 RtlUnlockHeap(HANDLE HeapPtr)
03111 {
03112     PHEAP Heap = (PHEAP)HeapPtr;
03113 
03114     // FIXME Check for special heap
03115 
03116     /* Check if it's really a heap */
03117     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
03118 
03119     /* Unlock if it's lockable */
03120     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03121     {
03122         RtlLeaveHeapLock(Heap->LockVariable);
03123     }
03124 
03125     return TRUE;
03126 }
03127 
03128 
03129 /***********************************************************************
03130  *           RtlSizeHeap
03131  * PARAMS
03132  *   Heap  [in] Handle of heap
03133  *   Flags   [in] Heap size control flags
03134  *   Ptr     [in] Address of memory to return size for
03135  *
03136  * RETURNS
03137  * Size in bytes of allocated memory
03138  * 0xffffffff: Failure
03139  *
03140  * @implemented
03141  */
03142 SIZE_T NTAPI
03143 RtlSizeHeap(
03144    HANDLE HeapPtr,
03145    ULONG Flags,
03146    PVOID Ptr
03147 )
03148 {
03149     PHEAP Heap = (PHEAP)HeapPtr;
03150     PHEAP_ENTRY HeapEntry;
03151     SIZE_T EntrySize;
03152 
03153     // FIXME This is a hack around missing SEH support!
03154     if (!Heap)
03155     {
03156         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE);
03157         return (SIZE_T)-1;
03158     }
03159 
03160     /* Force flags */
03161     Flags |= Heap->ForceFlags;
03162 
03163     /* Call special heap */
03164     if (RtlpHeapIsSpecial(Flags))
03165         return RtlDebugSizeHeap(Heap, Flags, Ptr);
03166 
03167     /* Get the heap entry pointer */
03168     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
03169 
03170     /* Return -1 if that entry is free */
03171     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03172     {
03173         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03174         return (SIZE_T)-1;
03175     }
03176 
03177     /* Get size of this block depending if it's a usual or a big one */
03178     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
03179     {
03180         EntrySize = RtlpGetSizeOfBigBlock(HeapEntry);
03181     }
03182     else
03183     {
03184         /* Calculate it */
03185         EntrySize = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
03186     }
03187 
03188     /* Return calculated size */
03189     return EntrySize;
03190 }
03191 
03192 BOOLEAN NTAPI
03193 RtlpCheckInUsePattern(PHEAP_ENTRY HeapEntry)
03194 {
03195     SIZE_T Size, Result;
03196     PCHAR TailPart;
03197 
03198     /* Calculate size */
03199     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
03200         Size = RtlpGetSizeOfBigBlock(HeapEntry);
03201     else
03202         Size = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
03203 
03204     /* Calculate pointer to the tail part of the block */
03205     TailPart = (PCHAR)(HeapEntry + 1) + Size;
03206 
03207     /* Compare tail pattern */
03208     Result = RtlCompareMemory(TailPart,
03209                               FillPattern,
03210                               HEAP_ENTRY_SIZE);
03211 
03212     if (Result != HEAP_ENTRY_SIZE)
03213     {
03214         DPRINT1("HEAP: Heap entry (size %x) %p tail is modified at %p\n", Size, HeapEntry, TailPart + Result);
03215         return FALSE;
03216     }
03217 
03218     /* All is fine */
03219     return TRUE;
03220 }
03221 
03222 BOOLEAN NTAPI
03223 RtlpValidateHeapHeaders(
03224     PHEAP Heap,
03225     BOOLEAN Recalculate)
03226 {
03227     // We skip header validation for now
03228     return TRUE;
03229 }
03230 
03231 BOOLEAN NTAPI
03232 RtlpValidateHeapEntry(
03233     PHEAP Heap,
03234     PHEAP_ENTRY HeapEntry)
03235 {
03236     BOOLEAN BigAllocation, EntryFound = FALSE;
03237     PHEAP_SEGMENT Segment;
03238     ULONG SegmentOffset;
03239 
03240     /* Perform various consistency checks of this entry */
03241     if (!HeapEntry) goto invalid_entry;
03242     if ((ULONG_PTR)HeapEntry & (HEAP_ENTRY_SIZE - 1)) goto invalid_entry;
03243     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) goto invalid_entry;
03244 
03245     BigAllocation = HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC;
03246     Segment = Heap->Segments[HeapEntry->SegmentOffset];
03247 
03248     if (BigAllocation &&
03249         (((ULONG_PTR)HeapEntry & (PAGE_SIZE - 1)) != FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock)))
03250          goto invalid_entry;
03251 
03252     if (!BigAllocation && (HeapEntry->SegmentOffset >= HEAP_SEGMENTS ||
03253         !Segment ||
03254         HeapEntry < Segment->FirstEntry ||
03255         HeapEntry >= Segment->LastValidEntry))
03256         goto invalid_entry;
03257 
03258     if ((HeapEntry->Flags & HEAP_ENTRY_FILL_PATTERN) &&
03259         !RtlpCheckInUsePattern(HeapEntry))
03260         goto invalid_entry;
03261 
03262     /* Checks are done, if this is a virtual entry, that's all */
03263     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) return TRUE;
03264 
03265     /* Go through segments and check if this entry fits into any of them */
03266     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
03267     {
03268         Segment = Heap->Segments[SegmentOffset];
03269         if (!Segment) continue;
03270 
03271         if ((HeapEntry >= Segment->FirstEntry) &&
03272             (HeapEntry < Segment->LastValidEntry))
03273         {
03274             /* Got it */
03275             EntryFound = TRUE;
03276             break;
03277         }
03278     }
03279 
03280     /* Return our result of finding entry in the segments */
03281     return EntryFound;
03282 
03283 invalid_entry:
03284     DPRINT1("HEAP: Invalid heap entry %p in heap %p\n", HeapEntry, Heap);
03285     return FALSE;
03286 }
03287 
03288 BOOLEAN NTAPI
03289 RtlpValidateHeapSegment(
03290     PHEAP Heap,
03291     PHEAP_SEGMENT Segment,
03292     UCHAR SegmentOffset,
03293     PULONG FreeEntriesCount,
03294     PSIZE_T TotalFreeSize,
03295     PSIZE_T TagEntries,
03296     PSIZE_T PseudoTagEntries)
03297 {
03298     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
03299     PLIST_ENTRY UcrEntry;
03300     SIZE_T ByteSize, Size, Result;
03301     PHEAP_ENTRY CurrentEntry;
03302     ULONG UnCommittedPages;
03303     ULONG UnCommittedRanges;
03304     ULONG PreviousSize;
03305 
03306     UnCommittedPages = 0;
03307     UnCommittedRanges = 0;
03308 
03309     if (IsListEmpty(&Segment->UCRSegmentList))
03310     {
03311         UcrEntry = NULL;
03312         UcrDescriptor = NULL;
03313     }
03314     else
03315     {
03316         UcrEntry = Segment->UCRSegmentList.Flink;
03317         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
03318     }
03319 
03320     if (Segment->BaseAddress == Heap)
03321         CurrentEntry = &Heap->Entry;
03322     else
03323         CurrentEntry = &Segment->Entry;
03324 
03325     while (CurrentEntry < Segment->LastValidEntry)
03326     {
03327         if (UcrDescriptor &&
03328             ((PVOID)CurrentEntry >= UcrDescriptor->Address))
03329         {
03330             DPRINT1("HEAP: Entry %p is not inside uncommited range [%p .. %p)\n",
03331                     CurrentEntry, UcrDescriptor->Address,
03332                     (PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
03333 
03334             return FALSE;
03335         }
03336 
03337         PreviousSize = 0;
03338 
03339         while (CurrentEntry < Segment->LastValidEntry)
03340         {
03341             if (PreviousSize != CurrentEntry->PreviousSize)
03342             {
03343                 DPRINT1("HEAP: Entry %p has incorrect PreviousSize %x instead of %x\n",
03344                     CurrentEntry, CurrentEntry->PreviousSize, PreviousSize);
03345 
03346                 return FALSE;
03347             }
03348 
03349             PreviousSize = CurrentEntry->Size;
03350             Size = CurrentEntry->Size << HEAP_ENTRY_SHIFT;
03351 
03352             if (CurrentEntry->Flags & HEAP_ENTRY_BUSY)
03353             {
03354                 if (TagEntries)
03355                 {
03356                     UNIMPLEMENTED;
03357                 }
03358 
03359                 /* Check fill pattern */
03360                 if (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN)
03361                 {
03362                     if (!RtlpCheckInUsePattern(CurrentEntry))
03363                         return FALSE;
03364                 }
03365             }
03366             else
03367             {
03368                 /* The entry is free, increase free entries count and total free size */
03369                 *FreeEntriesCount = *FreeEntriesCount + 1;
03370                 *TotalFreeSize += CurrentEntry->Size;
03371 
03372                 if ((Heap->Flags & HEAP_FREE_CHECKING_ENABLED) &&
03373                     (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN))
03374                 {
03375                     ByteSize = Size - sizeof(HEAP_FREE_ENTRY);
03376 
03377                     if ((CurrentEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) &&
03378                         (ByteSize > sizeof(HEAP_FREE_ENTRY_EXTRA)))
03379                     {
03380                         ByteSize -= sizeof(HEAP_FREE_ENTRY_EXTRA);
03381                     }
03382 
03383                     Result = RtlCompareMemoryUlong((PCHAR)((PHEAP_FREE_ENTRY)CurrentEntry + 1),
03384                                                     ByteSize,
03385                                                     ARENA_FREE_FILLER);
03386 
03387                     if (Result != ByteSize)
03388                     {
03389                         DPRINT1("HEAP: Free heap block %p modified at %p after it was freed\n",
03390                             CurrentEntry,
03391                             (PCHAR)(CurrentEntry + 1) + Result);
03392 
03393                         return FALSE;
03394                     }
03395                 }
03396             }
03397 
03398             if (CurrentEntry->SegmentOffset != SegmentOffset)
03399             {
03400                 DPRINT1("HEAP: Heap entry %p SegmentOffset is incorrect %x (should be %x)\n", CurrentEntry, SegmentOffset, CurrentEntry->SegmentOffset);
03401                 return FALSE;
03402             }
03403 
03404             /* Check if it's the last entry */
03405             if (CurrentEntry->Flags & HEAP_ENTRY_LAST_ENTRY)
03406             {
03407                 CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
03408 
03409                 if (!UcrDescriptor)
03410                 {
03411                     /* Check if it's not really the last one */
03412                     if (CurrentEntry != Segment->LastValidEntry)
03413                     {
03414                         DPRINT1("HEAP: Heap entry %p is not last block in segment (%x)\n", CurrentEntry, Segment->LastValidEntry);
03415                         return FALSE;
03416                     }
03417                 }
03418                 else if (CurrentEntry != UcrDescriptor->Address)
03419                 {
03420                     DPRINT1("HEAP: Heap entry %p does not match next uncommitted address (%p)\n",
03421                         CurrentEntry, UcrDescriptor->Address);
03422 
03423                     return FALSE;
03424                 }
03425                 else
03426                 {
03427                     UnCommittedPages += (ULONG)(UcrDescriptor->Size / PAGE_SIZE);
03428                     UnCommittedRanges++;
03429 
03430                     CurrentEntry = (PHEAP_ENTRY)((PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
03431 
03432                     /* Go to the next UCR descriptor */
03433                     UcrEntry = UcrEntry->Flink;
03434                     if (UcrEntry == &Segment->UCRSegmentList)
03435                     {
03436                         UcrEntry = NULL;
03437                         UcrDescriptor = NULL;
03438                     }
03439                     else
03440                     {
03441                         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
03442                     }
03443                 }
03444 
03445                 break;
03446             }
03447 
03448             /* Advance to the next entry */
03449             CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
03450         }
03451     }
03452 
03453     /* Check total numbers of UCP and UCR */
03454     if (Segment->NumberOfUnCommittedPages != UnCommittedPages)
03455     {
03456         DPRINT1("HEAP: Segment %p NumberOfUnCommittedPages is invalid (%x != %x)\n",
03457             Segment, Segment->NumberOfUnCommittedPages, UnCommittedPages);
03458 
03459         return FALSE;
03460     }
03461 
03462     if (Segment->NumberOfUnCommittedRanges != UnCommittedRanges)
03463     {
03464         DPRINT1("HEAP: Segment %p NumberOfUnCommittedRanges is invalid (%x != %x)\n",
03465             Segment, Segment->NumberOfUnCommittedRanges, UnCommittedRanges);
03466 
03467         return FALSE;
03468     }
03469 
03470     return TRUE;
03471 }
03472 
03473 BOOLEAN NTAPI
03474 RtlpValidateHeap(PHEAP Heap,
03475                  BOOLEAN ForceValidation)
03476 {
03477     PHEAP_SEGMENT Segment;
03478     BOOLEAN EmptyList;
03479     UCHAR SegmentOffset;
03480     SIZE_T Size, TotalFreeSize;
03481     ULONG PreviousSize;
03482     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
03483     PLIST_ENTRY ListHead, NextEntry;
03484     PHEAP_FREE_ENTRY FreeEntry;
03485     ULONG FreeBlocksCount, FreeListEntriesCount;
03486 
03487     /* Check headers */
03488     if (!RtlpValidateHeapHeaders(Heap, FALSE))
03489         return FALSE;
03490 
03491     /* Skip validation if it's not needed */
03492     if (!ForceValidation && !(Heap->Flags & HEAP_VALIDATE_ALL_ENABLED))
03493         return TRUE;
03494 
03495     /* Check free lists bitmaps */
03496     FreeListEntriesCount = 0;
03497     ListHead = &Heap->FreeLists[0];
03498 
03499     for (Size = 0; Size < HEAP_FREELISTS; Size++)
03500     {
03501         if (Size)
03502         {
03503             /* This is a dedicated list. Check if it's empty */
03504             EmptyList = IsListEmpty(ListHead);
03505 
03506             if (Heap->u.FreeListsInUseBytes[Size >> 3] & (1 << (Size & 7)))
03507             {
03508                 if (EmptyList)
03509                 {
03510                     DPRINT1("HEAP: Empty %x-free list marked as non-empty\n", Size);
03511                     return FALSE;
03512                 }
03513             }
03514             else
03515             {
03516                 if (!EmptyList)
03517                 {
03518                     DPRINT1("HEAP: Non-empty %x-free list marked as empty\n", Size);
03519                     return FALSE;
03520                 }
03521             }
03522         }
03523 
03524         /* Now check this list entries */
03525         NextEntry = ListHead->Flink;
03526         PreviousSize = 0;
03527 
03528         while (ListHead != NextEntry)
03529         {
03530             FreeEntry = CONTAINING_RECORD(NextEntry, HEAP_FREE_ENTRY, FreeList);
03531             NextEntry = NextEntry->Flink;
03532 
03533             /* If there is an in-use entry in a free list - that's quite a big problem */
03534             if (FreeEntry->Flags & HEAP_ENTRY_BUSY)
03535             {
03536                 DPRINT1("HEAP: %x-dedicated list free element %x is marked in-use\n", Size, FreeEntry);
03537                 return FALSE;
03538             }
03539 
03540             /* Check sizes according to that specific list's size */
03541             if ((Size == 0) && (FreeEntry->Size < HEAP_FREELISTS))
03542             {
03543                 DPRINT1("HEAP: Non dedicated list free element %x has size %x which would fit a dedicated list\n", FreeEntry, FreeEntry->Size);
03544                 return FALSE;
03545             }
03546             else if (Size && (FreeEntry->Size != Size))
03547             {
03548                 DPRINT1("HEAP: %x-dedicated list free element %x has incorrect size %x\n", Size, FreeEntry, FreeEntry->Size);
03549                 return FALSE;
03550             }
03551             else if ((Size == 0) && (FreeEntry->Size < PreviousSize))
03552             {
03553                 DPRINT1("HEAP: Non dedicated list free element %x is not put in order\n", FreeEntry);
03554                 return FALSE;
03555             }
03556 
03557             /* Remember previous size*/
03558             PreviousSize = FreeEntry->Size;
03559 
03560             /* Add up to the total amount of free entries */
03561             FreeListEntriesCount++;
03562         }
03563 
03564         /* Go to the head of the next free list */
03565         ListHead++;
03566     }
03567 
03568     /* Check big allocations */
03569     ListHead = &Heap->VirtualAllocdBlocks;
03570     NextEntry = ListHead->Flink;
03571 
03572     while (ListHead != NextEntry)
03573     {
03574         VirtualAllocBlock = CONTAINING_RECORD(NextEntry, HEAP_VIRTUAL_ALLOC_ENTRY, Entry);
03575 
03576         /* We can only check the fill pattern */
03577         if (VirtualAllocBlock->BusyBlock.Flags & HEAP_ENTRY_FILL_PATTERN)
03578         {
03579             if (!RtlpCheckInUsePattern(&VirtualAllocBlock->BusyBlock))
03580                 return FALSE;
03581         }
03582 
03583         NextEntry = NextEntry->Flink;
03584     }
03585 
03586     /* Check all segments */
03587     FreeBlocksCount = 0;
03588     TotalFreeSize = 0;
03589 
03590     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
03591     {
03592         Segment = Heap->Segments[SegmentOffset];
03593 
03594         /* Go to the next one if there is no segment */
03595         if (!Segment) continue;
03596 
03597         if (!RtlpValidateHeapSegment(Heap,
03598                                      Segment,
03599                                      SegmentOffset,
03600                                      &FreeBlocksCount,
03601                                      &TotalFreeSize,
03602                                      NULL,
03603                                      NULL))
03604         {
03605             return FALSE;
03606         }
03607     }
03608 
03609     if (FreeListEntriesCount != FreeBlocksCount)
03610     {
03611         DPRINT1("HEAP: Free blocks count in arena (%d) does not match free blocks number in the free lists (%d)\n", FreeBlocksCount, FreeListEntriesCount);
03612         return FALSE;
03613     }
03614 
03615     if (Heap->TotalFreeSize != TotalFreeSize)
03616     {
03617         DPRINT1("HEAP: Total size of free blocks in arena (%d) does not equal to the one in heap header (%d)\n", TotalFreeSize, Heap->TotalFreeSize);
03618         return FALSE;
03619     }
03620 
03621     return TRUE;
03622 }
03623 
03624 /***********************************************************************
03625  *           RtlValidateHeap
03626  * Validates a specified heap.
03627  *
03628  * PARAMS
03629  *   Heap  [in] Handle to the heap
03630  *   Flags   [in] Bit flags that control access during operation
03631  *   Block  [in] Optional pointer to memory block to validate
03632  *
03633  * NOTES
03634  * Flags is ignored.
03635  *
03636  * RETURNS
03637  * TRUE: Success
03638  * FALSE: Failure
03639  *
03640  * @implemented
03641  */
03642 BOOLEAN NTAPI RtlValidateHeap(
03643    HANDLE HeapPtr,
03644    ULONG Flags,
03645    PVOID Block
03646 )
03647 {
03648     PHEAP Heap = (PHEAP)HeapPtr;
03649     BOOLEAN HeapLocked = FALSE;
03650     BOOLEAN HeapValid;
03651 
03652     /* Check for page heap */
03653     if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS)
03654         return RtlpDebugPageHeapValidate(HeapPtr, Flags, Block);
03655 
03656     /* Check signature */
03657     if (Heap->Signature != HEAP_SIGNATURE)
03658     {
03659         DPRINT1("HEAP: Signature %x is invalid for heap %p\n", Heap->Signature, Heap);
03660         return FALSE;
03661     }
03662 
03663     /* Force flags */
03664     Flags = Heap->ForceFlags;
03665 
03666     /* Acquire the lock if necessary */
03667     if (!(Flags & HEAP_NO_SERIALIZE))
03668     {
03669         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03670         HeapLocked = TRUE;
03671     }
03672 
03673     /* Either validate whole heap or just one entry */
03674     if (!Block)
03675         HeapValid = RtlpValidateHeap(Heap, TRUE);
03676     else
03677         HeapValid = RtlpValidateHeapEntry(Heap, (PHEAP_ENTRY)Block - 1);
03678 
03679     /* Unlock if it's lockable */
03680     if (HeapLocked)
03681     {
03682         RtlLeaveHeapLock(Heap->LockVariable);
03683     }
03684 
03685     return HeapValid;
03686 }
03687 
03688 VOID
03689 RtlInitializeHeapManager(VOID)
03690 {
03691     PPEB Peb;
03692 
03693     /* Get PEB */
03694     Peb = RtlGetCurrentPeb();
03695 
03696     /* Initialize heap-related fields of PEB */
03697     Peb->NumberOfHeaps = 0;
03698 
03699     /* Initialize the process heaps list protecting lock */
03700     RtlInitializeCriticalSection(&RtlpProcessHeapsListLock);
03701 }
03702 
03703 
03704 /*
03705  * @implemented
03706  */
03707 NTSTATUS NTAPI
03708 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine,
03709                     PVOID lParam)
03710 {
03711     UNIMPLEMENTED;
03712     return STATUS_NOT_IMPLEMENTED;
03713 }
03714 
03715 
03716 /*
03717  * @implemented
03718  */
03719 ULONG NTAPI
03720 RtlGetProcessHeaps(ULONG count,
03721                    HANDLE *heaps)
03722 {
03723     UNIMPLEMENTED;
03724     return 0;
03725 }
03726 
03727 
03728 /*
03729  * @implemented
03730  */
03731 BOOLEAN NTAPI
03732 RtlValidateProcessHeaps(VOID)
03733 {
03734     UNIMPLEMENTED;
03735     return TRUE;
03736 }
03737 
03738 
03739 /*
03740  * @unimplemented
03741  */
03742 BOOLEAN NTAPI
03743 RtlZeroHeap(
03744     IN PVOID HeapHandle,
03745     IN ULONG Flags
03746     )
03747 {
03748     UNIMPLEMENTED;
03749     return FALSE;
03750 }
03751 
03752 /*
03753  * @implemented
03754  */
03755 BOOLEAN
03756 NTAPI
03757 RtlSetUserValueHeap(IN PVOID HeapHandle,
03758                     IN ULONG Flags,
03759                     IN PVOID BaseAddress,
03760                     IN PVOID UserValue)
03761 {
03762     PHEAP Heap = (PHEAP)HeapHandle;
03763     PHEAP_ENTRY HeapEntry;
03764     PHEAP_ENTRY_EXTRA Extra;
03765     BOOLEAN HeapLocked = FALSE, ValueSet = FALSE;
03766 
03767     /* Force flags */
03768     Flags |= Heap->Flags;
03769 
03770     /* Call special heap */
03771     if (RtlpHeapIsSpecial(Flags))
03772         return RtlDebugSetUserValueHeap(Heap, Flags, BaseAddress, UserValue);
03773 
03774     /* Lock if it's lockable */
03775     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03776     {
03777         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03778         HeapLocked = TRUE;
03779     }
03780 
03781     /* Get a pointer to the entry */
03782     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03783 
03784     /* If it's a free entry - return error */
03785     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03786     {
03787         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03788 
03789         /* Release the heap lock if it was acquired */
03790         if (HeapLocked)
03791             RtlLeaveHeapLock(Heap->LockVariable);
03792 
03793         return FALSE;
03794     }
03795 
03796     /* Check if this entry has an extra stuff associated with it */
03797     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
03798     {
03799         /* Use extra to store the value */
03800         Extra = RtlpGetExtraStuffPointer(HeapEntry);
03801         Extra->Settable = (ULONG_PTR)UserValue;
03802 
03803         /* Indicate that value was set */
03804         ValueSet = TRUE;
03805     }
03806 
03807     /* Release the heap lock if it was acquired */
03808     if (HeapLocked)
03809         RtlLeaveHeapLock(Heap->LockVariable);
03810 
03811     return ValueSet;
03812 }
03813 
03814 /*
03815  * @implemented
03816  */
03817 BOOLEAN
03818 NTAPI
03819 RtlSetUserFlagsHeap(IN PVOID HeapHandle,
03820                     IN ULONG Flags,
03821                     IN PVOID BaseAddress,
03822                     IN ULONG UserFlagsReset,
03823                     IN ULONG UserFlagsSet)
03824 {
03825     PHEAP Heap = (PHEAP)HeapHandle;
03826     PHEAP_ENTRY HeapEntry;
03827     BOOLEAN HeapLocked = FALSE;
03828 
03829     /* Force flags */
03830     Flags |= Heap->Flags;
03831 
03832     /* Call special heap */
03833     if (RtlpHeapIsSpecial(Flags))
03834         return RtlDebugSetUserFlagsHeap(Heap, Flags, BaseAddress, UserFlagsReset, UserFlagsSet);
03835 
03836     /* Lock if it's lockable */
03837     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03838     {
03839         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03840         HeapLocked = TRUE;
03841     }
03842 
03843     /* Get a pointer to the entry */
03844     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03845 
03846     /* If it's a free entry - return error */
03847     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03848     {
03849         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03850 
03851         /* Release the heap lock if it was acquired */
03852         if (HeapLocked)
03853             RtlLeaveHeapLock(Heap->LockVariable);
03854 
03855         return FALSE;
03856     }
03857 
03858     /* Set / reset flags */
03859     HeapEntry->Flags &= ~(UserFlagsReset >> 4);
03860     HeapEntry->Flags |= (UserFlagsSet >> 4);
03861 
03862     /* Release the heap lock if it was acquired */
03863     if (HeapLocked)
03864         RtlLeaveHeapLock(Heap->LockVariable);
03865 
03866     return TRUE;
03867 }
03868 
03869 /*
03870  * @implemented
03871  */
03872 BOOLEAN
03873 NTAPI
03874 RtlGetUserInfoHeap(IN PVOID HeapHandle,
03875                    IN ULONG Flags,
03876                    IN PVOID BaseAddress,
03877                    OUT PVOID *UserValue,
03878                    OUT PULONG UserFlags)
03879 {
03880     PHEAP Heap = (PHEAP)HeapHandle;
03881     PHEAP_ENTRY HeapEntry;
03882     PHEAP_ENTRY_EXTRA Extra;
03883     BOOLEAN HeapLocked = FALSE;
03884 
03885     /* Force flags */
03886     Flags |= Heap->Flags;
03887 
03888     /* Call special heap */
03889     if (RtlpHeapIsSpecial(Flags))
03890         return RtlDebugGetUserInfoHeap(Heap, Flags, BaseAddress, UserValue, UserFlags);
03891 
03892     /* Lock if it's lockable */
03893     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03894     {
03895         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03896         HeapLocked = TRUE;
03897     }
03898 
03899     /* Get a pointer to the entry */
03900     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03901 
03902     /* If it's a free entry - return error */
03903     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03904     {
03905         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03906 
03907         /* Release the heap lock if it was acquired */
03908         if (HeapLocked)
03909             RtlLeaveHeapLock(Heap->LockVariable);
03910 
03911         return FALSE;
03912     }
03913 
03914     /* Check if this entry has an extra stuff associated with it */
03915     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
03916     {
03917         /* Get pointer to extra data */
03918         Extra = RtlpGetExtraStuffPointer(HeapEntry);
03919 
03920         /* Pass user value */
03921         if (UserValue)
03922             *UserValue = (PVOID)Extra->Settable;
03923 
03924         /* Decode and return user flags */
03925         if (UserFlags)
03926             *UserFlags = (HeapEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4;
03927     }
03928 
03929     /* Release the heap lock if it was acquired */
03930     if (HeapLocked)
03931         RtlLeaveHeapLock(Heap->LockVariable);
03932 
03933     return TRUE;
03934 }
03935 
03936 /*
03937  * @unimplemented
03938  */
03939 NTSTATUS
03940 NTAPI
03941 RtlUsageHeap(IN HANDLE Heap,
03942              IN ULONG Flags,
03943              OUT PRTL_HEAP_USAGE Usage)
03944 {
03945     /* TODO */
03946     UNIMPLEMENTED;
03947     return STATUS_NOT_IMPLEMENTED;
03948 }
03949 
03950 PWSTR
03951 NTAPI
03952 RtlQueryTagHeap(IN PVOID HeapHandle,
03953                 IN ULONG Flags,
03954                 IN USHORT TagIndex,
03955                 IN BOOLEAN ResetCounters,
03956                 OUT PRTL_HEAP_TAG_INFO HeapTagInfo)
03957 {
03958     /* TODO */
03959     UNIMPLEMENTED;
03960     return NULL;
03961 }
03962 
03963 ULONG
03964 NTAPI
03965 RtlExtendHeap(IN HANDLE Heap,
03966               IN ULONG Flags,
03967               IN PVOID P,
03968               IN SIZE_T Size)
03969 {
03970     /* TODO */
03971     UNIMPLEMENTED;
03972     return 0;
03973 }
03974 
03975 ULONG
03976 NTAPI
03977 RtlCreateTagHeap(IN HANDLE HeapHandle,
03978                  IN ULONG Flags,
03979                  IN PWSTR TagName,
03980                  IN PWSTR TagSubName)
03981 {
03982     /* TODO */
03983     UNIMPLEMENTED;
03984     return 0;
03985 }
03986 
03987 NTSTATUS
03988 NTAPI
03989 RtlWalkHeap(IN HANDLE HeapHandle,
03990             IN PVOID HeapEntry)
03991 {
03992     UNIMPLEMENTED;
03993     return STATUS_NOT_IMPLEMENTED;
03994 }
03995 
03996 PVOID
03997 NTAPI
03998 RtlProtectHeap(IN PVOID HeapHandle,
03999                IN BOOLEAN ReadOnly)
04000 {
04001     UNIMPLEMENTED;
04002     return NULL;
04003 }
04004 
04005 NTSTATUS
04006 NTAPI
04007 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL,
04008                       IN HEAP_INFORMATION_CLASS HeapInformationClass,
04009                       IN PVOID HeapInformation,
04010                       IN SIZE_T HeapInformationLength)
04011 {
04012     /* Setting heap information is not really supported except for enabling LFH */
04013     if (HeapInformationClass == 0) return STATUS_SUCCESS;
04014 
04015     /* Check buffer length */
04016     if (HeapInformationLength < sizeof(ULONG))
04017     {
04018         /* The provided buffer is too small */
04019         return STATUS_BUFFER_TOO_SMALL;
04020     }
04021 
04022     /* Check for a special magic value for enabling LFH */
04023     if (*(PULONG)HeapInformation == 2)
04024     {
04025         DPRINT1("RtlSetHeapInformation() needs to enable LFH\n");
04026         return STATUS_SUCCESS;
04027     }
04028 
04029     return STATUS_UNSUCCESSFUL;
04030 }
04031 
04032 NTSTATUS
04033 NTAPI
04034 RtlQueryHeapInformation(HANDLE HeapHandle,
04035                         HEAP_INFORMATION_CLASS HeapInformationClass,
04036                         PVOID HeapInformation OPTIONAL,
04037                         SIZE_T HeapInformationLength OPTIONAL,
04038                         PSIZE_T ReturnLength OPTIONAL)
04039 {
04040     PHEAP Heap = (PHEAP)HeapHandle;
04041 
04042     /* Only HeapCompatibilityInformation is supported */
04043     if (HeapInformationClass != HeapCompatibilityInformation)
04044         return STATUS_UNSUCCESSFUL;
04045 
04046     /* Set result length */
04047     if (ReturnLength) *ReturnLength = sizeof(ULONG);
04048 
04049     /* Check buffer length */
04050     if (HeapInformationLength < sizeof(ULONG))
04051     {
04052         /* It's too small, return needed length */
04053         return STATUS_BUFFER_TOO_SMALL;
04054     }
04055 
04056     /* Return front end heap type */
04057     *(PULONG)HeapInformation = Heap->FrontEndHeapType;
04058 
04059     return STATUS_SUCCESS;
04060 }
04061 
04062 NTSTATUS
04063 NTAPI
04064 RtlMultipleAllocateHeap(IN PVOID HeapHandle,
04065                         IN ULONG Flags,
04066                         IN SIZE_T Size,
04067                         IN ULONG Count,
04068                         OUT PVOID *Array)
04069 {
04070     UNIMPLEMENTED;
04071     return 0;
04072 }
04073 
04074 NTSTATUS
04075 NTAPI
04076 RtlMultipleFreeHeap(IN PVOID HeapHandle,
04077                     IN ULONG Flags,
04078                     IN ULONG Count,
04079                     OUT PVOID *Array)
04080 {
04081     UNIMPLEMENTED;
04082     return 0;
04083 }
04084 
04085 /* EOF */

Generated on Thu Oct 25 2012 04:22:19 for ReactOS by doxygen 1.7.6.1

ReactOS is a registered trademark or a trademark of ReactOS Foundation in the United States and other countries.