Doxygen

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