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     {
01935         DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags);
01936     }
01937 
01938     //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size);
01939 
01940     /* Calculate allocation size and index */
01941     if (Size)
01942         AllocationSize = Size;
01943     else
01944         AllocationSize = 1;
01945     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
01946 
01947     /* Add extra flags in case of settable user value feature is requested,
01948        or there is a tag (small or normal) or there is a request to
01949        capture stack backtraces */
01950     if ((Flags & HEAP_EXTRA_FLAGS_MASK) ||
01951         Heap->PseudoTagEntries)
01952     {
01953         /* Add flag which means that the entry will have extra stuff attached */
01954         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
01955 
01956         /* Account for extra stuff size */
01957         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
01958     }
01959 
01960     /* Add settable user flags, if any */
01961     EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4;
01962 
01963     Index = AllocationSize >>  HEAP_ENTRY_SHIFT;
01964 
01965     /* Acquire the lock if necessary */
01966     if (!(Flags & HEAP_NO_SERIALIZE))
01967     {
01968         RtlEnterHeapLock(Heap->LockVariable, TRUE);
01969         HeapLocked = TRUE;
01970     }
01971 
01972     /* Depending on the size, the allocation is going to be done from dedicated,
01973        non-dedicated lists or a virtual block of memory */
01974     if (Index < HEAP_FREELISTS)
01975     {
01976         FreeListHead = &Heap->FreeLists[Index];
01977 
01978         if (!IsListEmpty(FreeListHead))
01979         {
01980             /* There is a free entry in this list */
01981             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
01982                                           HEAP_FREE_ENTRY,
01983                                           FreeList);
01984 
01985             /* Save flags and remove the free entry */
01986             FreeFlags = FreeBlock->Flags;
01987             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
01988 
01989             /* Update the total free size of the heap */
01990             Heap->TotalFreeSize -= Index;
01991 
01992             /* Initialize this block */
01993             InUseEntry = (PHEAP_ENTRY)FreeBlock;
01994             InUseEntry->Flags = EntryFlags | (FreeFlags & HEAP_ENTRY_LAST_ENTRY);
01995             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
01996             InUseEntry->SmallTagIndex = 0;
01997         }
01998         else
01999         {
02000             /* Find smallest free block which this request could fit in */
02001             InUseIndex = Index >> 5;
02002             FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex];
02003 
02004             /* This bit magic disables all sizes which are less than the requested allocation size */
02005             FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << ((ULONG)Index & 0x1f)) - 1);
02006 
02007             /* If size is definitily more than our lists - go directly to the non-dedicated one */
02008             if (InUseIndex > 3)
02009                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02010 
02011             /* Go through the list */
02012             for (i = InUseIndex; i < 4; i++)
02013             {
02014                 if (FreeListsInUseUlong)
02015                 {
02016                     FreeListHead = &Heap->FreeLists[i * 32];
02017                     break;
02018                 }
02019 
02020                 if (i < 3) FreeListsInUseUlong = *FreeListsInUse++;
02021             }
02022 
02023             /* Nothing found, search in the non-dedicated list */
02024             if (i == 4)
02025                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02026 
02027             /* That list is found, now calculate exact block  */
02028             FreeListHead += RtlpFindLeastSetBit(FreeListsInUseUlong);
02029 
02030             /* Take this entry and remove it from the list of free blocks */
02031             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
02032                                           HEAP_FREE_ENTRY,
02033                                           FreeList);
02034             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
02035 
02036             /* Split it */
02037             InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
02038         }
02039 
02040         /* Release the lock */
02041         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02042 
02043         /* Zero memory if that was requested */
02044         if (Flags & HEAP_ZERO_MEMORY)
02045             RtlZeroMemory(InUseEntry + 1, Size);
02046         else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02047         {
02048             /* Fill this block with a special pattern */
02049             RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
02050         }
02051 
02052         /* Fill tail of the block with a special pattern too if requested */
02053         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02054         {
02055             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
02056             InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
02057         }
02058 
02059         /* Prepare extra if it's present */
02060         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02061         {
02062             Extra = RtlpGetExtraStuffPointer(InUseEntry);
02063             RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
02064 
02065             // TODO: Tagging
02066         }
02067 
02068         /* User data starts right after the entry's header */
02069         return InUseEntry + 1;
02070     }
02071     else if (Index <= Heap->VirtualMemoryThreshold)
02072     {
02073         /* The block is too large for dedicated lists, but fine for a non-dedicated one */
02074         return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
02075     }
02076     else if (Heap->Flags & HEAP_GROWABLE)
02077     {
02078         /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */
02079         AllocationSize += sizeof(HEAP_VIRTUAL_ALLOC_ENTRY) - sizeof(HEAP_ENTRY);
02080 
02081         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
02082                                          (PVOID *)&VirtualBlock,
02083                                          0,
02084                                          &AllocationSize,
02085                                          MEM_COMMIT,
02086                                          PAGE_READWRITE);
02087 
02088         if (!NT_SUCCESS(Status))
02089         {
02090             // Set STATUS!
02091             /* Release the lock */
02092             if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02093             DPRINT1("HEAP: Allocation failed!\n");
02094             return NULL;
02095         }
02096 
02097         /* Initialize the newly allocated block */
02098         VirtualBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size);
02099         ASSERT(VirtualBlock->BusyBlock.Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY));
02100         VirtualBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT;
02101         VirtualBlock->CommitSize = AllocationSize;
02102         VirtualBlock->ReserveSize = AllocationSize;
02103 
02104         /* Insert it into the list of virtual allocations */
02105         InsertTailList(&Heap->VirtualAllocdBlocks, &VirtualBlock->Entry);
02106 
02107         /* Release the lock */
02108         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02109 
02110         /* Return pointer to user data */
02111         return VirtualBlock + 1;
02112     }
02113 
02114     /* Generate an exception */
02115     if (Flags & HEAP_GENERATE_EXCEPTIONS)
02116     {
02117         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
02118         ExceptionRecord.ExceptionRecord = NULL;
02119         ExceptionRecord.NumberParameters = 1;
02120         ExceptionRecord.ExceptionFlags = 0;
02121         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
02122 
02123         RtlRaiseException(&ExceptionRecord);
02124     }
02125 
02126     RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL);
02127 
02128     /* Release the lock */
02129     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
02130     DPRINT1("HEAP: Allocation failed!\n");
02131     return NULL;
02132 }
02133 
02134 
02135 /***********************************************************************
02136  *           HeapFree   (KERNEL32.338)
02137  * RETURNS
02138  * TRUE: Success
02139  * FALSE: Failure
02140  *
02141  * @implemented
02142  */
02143 BOOLEAN NTAPI RtlFreeHeap(
02144    HANDLE HeapPtr, /* [in] Handle of heap */
02145    ULONG Flags,   /* [in] Heap freeing flags */
02146    PVOID Ptr     /* [in] Address of memory to free */
02147 )
02148 {
02149     PHEAP Heap;
02150     PHEAP_ENTRY HeapEntry;
02151     USHORT TagIndex = 0;
02152     SIZE_T BlockSize;
02153     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
02154     BOOLEAN Locked = FALSE;
02155     NTSTATUS Status;
02156 
02157     /* Freeing NULL pointer is a legal operation */
02158     if (!Ptr) return TRUE;
02159 
02160     /* Get pointer to the heap and force flags */
02161     Heap = (PHEAP)HeapPtr;
02162     Flags |= Heap->ForceFlags;
02163 
02164     /* Call special heap */
02165     if (RtlpHeapIsSpecial(Flags))
02166         return RtlDebugFreeHeap(Heap, Flags, Ptr);
02167 
02168     /* Lock if necessary */
02169     if (!(Flags & HEAP_NO_SERIALIZE))
02170     {
02171         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02172         Locked = TRUE;
02173     }
02174 
02175     /* Get pointer to the heap entry */
02176     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
02177 
02178     /* Check this entry, fail if it's invalid */
02179     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY) ||
02180         (((ULONG_PTR)Ptr & 0x7) != 0) ||
02181         (HeapEntry->SegmentOffset >= HEAP_SEGMENTS))
02182     {
02183         /* This is an invalid block */
02184         DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr);
02185         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
02186 
02187         /* Release the heap lock */
02188         if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
02189         return FALSE;
02190     }
02191 
02192     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02193     {
02194         /* Big allocation */
02195         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02196 
02197         /* Remove it from the list */
02198         RemoveEntryList(&VirtualEntry->Entry);
02199 
02200         // TODO: Tagging
02201 
02202         BlockSize = 0;
02203         Status = ZwFreeVirtualMemory(NtCurrentProcess(),
02204                                      (PVOID *)&VirtualEntry,
02205                                      &BlockSize,
02206                                      MEM_RELEASE);
02207 
02208         if (!NT_SUCCESS(Status))
02209         {
02210             DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n",
02211                 Status, Heap, Ptr, VirtualEntry);
02212             RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status);
02213         }
02214     }
02215     else
02216     {
02217         /* Normal allocation */
02218         BlockSize = HeapEntry->Size;
02219 
02220         // TODO: Tagging
02221 
02222         /* Coalesce in kernel mode, and in usermode if it's not disabled */
02223         if (RtlpGetMode() == KernelMode ||
02224             (RtlpGetMode() == UserMode && !(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)))
02225         {
02226             HeapEntry = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks(Heap,
02227                                                            (PHEAP_FREE_ENTRY)HeapEntry,
02228                                                            &BlockSize,
02229                                                            FALSE);
02230         }
02231 
02232         /* If there is no need to decommit the block - put it into a free list */
02233         if (BlockSize < Heap->DeCommitFreeBlockThreshold ||
02234             (Heap->TotalFreeSize + BlockSize < Heap->DeCommitTotalFreeThreshold))
02235         {
02236             /* Check if it needs to go to a 0 list */
02237             if (BlockSize > HEAP_MAX_BLOCK_SIZE)
02238             {
02239                 /* General-purpose 0 list */
02240                 RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
02241             }
02242             else
02243             {
02244                 /* Usual free list */
02245                 RtlpInsertFreeBlockHelper(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize, FALSE);
02246 
02247                 /* Assert sizes are consistent */
02248                 if (!(HeapEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
02249                 {
02250                     ASSERT((HeapEntry + BlockSize)->PreviousSize == BlockSize);
02251                 }
02252 
02253                 /* Increase the free size */
02254                 Heap->TotalFreeSize += BlockSize;
02255             }
02256 
02257 
02258             if (RtlpGetMode() == UserMode &&
02259                 TagIndex != 0)
02260             {
02261                 // FIXME: Tagging
02262                 UNIMPLEMENTED;
02263             }
02264         }
02265         else
02266         {
02267             /* Decommit this block */
02268             RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
02269         }
02270     }
02271 
02272     /* Release the heap lock */
02273     if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
02274 
02275     return TRUE;
02276 }
02277 
02278 BOOLEAN NTAPI
02279 RtlpGrowBlockInPlace (IN PHEAP Heap,
02280                       IN ULONG Flags,
02281                       IN PHEAP_ENTRY InUseEntry,
02282                       IN SIZE_T Size,
02283                       IN SIZE_T Index)
02284 {
02285     UCHAR EntryFlags, RememberFlags;
02286     PHEAP_FREE_ENTRY FreeEntry, UnusedEntry, FollowingEntry;
02287     SIZE_T FreeSize, PrevSize, TailPart, AddedSize = 0;
02288     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
02289 
02290     /* We can't grow beyond specified threshold */
02291     if (Index > Heap->VirtualMemoryThreshold)
02292         return FALSE;
02293 
02294     /* Get entry flags */
02295     EntryFlags = InUseEntry->Flags;
02296 
02297     /* Get the next free entry */
02298     FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size);
02299 
02300     if (EntryFlags & HEAP_ENTRY_LAST_ENTRY)
02301     {
02302         /* There is no next block, just uncommitted space. Calculate how much is needed */
02303         FreeSize = (Index - InUseEntry->Size) << HEAP_ENTRY_SHIFT;
02304         FreeSize = ROUND_UP(FreeSize, PAGE_SIZE);
02305 
02306         /* Find and commit those pages */
02307         FreeEntry = RtlpFindAndCommitPages(Heap,
02308                                            Heap->Segments[InUseEntry->SegmentOffset],
02309                                            &FreeSize,
02310                                            FreeEntry);
02311 
02312         /* Fail if it failed... */
02313         if (!FreeEntry) return FALSE;
02314 
02315         /* It was successful, perform coalescing */
02316         FreeSize = FreeSize >> HEAP_ENTRY_SHIFT;
02317         FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE);
02318 
02319         /* Check if it's enough */
02320         if (FreeSize + InUseEntry->Size < Index)
02321         {
02322             /* Still not enough */
02323             RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize);
02324             Heap->TotalFreeSize += FreeSize;
02325             return FALSE;
02326         }
02327 
02328         /* Remember flags of this free entry */
02329         RememberFlags = FreeEntry->Flags;
02330 
02331         /* Sum up sizes */
02332         FreeSize += InUseEntry->Size;
02333     }
02334     else
02335     {
02336         /* The next block indeed exists. Check if it's free or in use */
02337         if (FreeEntry->Flags & HEAP_ENTRY_BUSY) return FALSE;
02338 
02339         /* Next entry is free, check if it can fit the block we need */
02340         FreeSize = InUseEntry->Size + FreeEntry->Size;
02341         if (FreeSize < Index) return FALSE;
02342 
02343         /* Remember flags of this free entry */
02344         RememberFlags = FreeEntry->Flags;
02345 
02346         /* Remove this block from the free list */
02347         RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
02348         Heap->TotalFreeSize -= FreeEntry->Size;
02349     }
02350 
02351     PrevSize = (InUseEntry->Size << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
02352     FreeSize -= Index;
02353 
02354     /* Don't produce too small blocks */
02355     if (FreeSize <= 2)
02356     {
02357         Index += FreeSize;
02358         FreeSize = 0;
02359     }
02360 
02361     /* Process extra stuff */
02362     if (RememberFlags & HEAP_ENTRY_EXTRA_PRESENT)
02363     {
02364         /* Calculate pointers */
02365         OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
02366         NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
02367 
02368         /* Copy contents */
02369         *NewExtra = *OldExtra;
02370 
02371         // FIXME Tagging
02372     }
02373 
02374     /* Update sizes */
02375     InUseEntry->Size = (USHORT)Index;
02376     InUseEntry->UnusedBytes = (UCHAR)((Index << HEAP_ENTRY_SHIFT) - Size);
02377 
02378     /* Check if there is a free space remaining after merging those blocks */
02379     if (!FreeSize)
02380     {
02381         /* Update flags and sizes */
02382         InUseEntry->Flags |= RememberFlags & HEAP_ENTRY_LAST_ENTRY;
02383 
02384         /* Either update previous size of the next entry or mark it as a last
02385            entry in the segment*/
02386         if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
02387             (InUseEntry + InUseEntry->Size)->PreviousSize = InUseEntry->Size;
02388     }
02389     else
02390     {
02391         /* Complex case, we need to split the block to give unused free space
02392            back to the heap */
02393         UnusedEntry = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
02394         UnusedEntry->PreviousSize = (USHORT)Index;
02395         UnusedEntry->SegmentOffset = InUseEntry->SegmentOffset;
02396 
02397         /* Update the following block or set the last entry in the segment */
02398         if (RememberFlags & HEAP_ENTRY_LAST_ENTRY)
02399         {
02400             /* Set flags and size */
02401             UnusedEntry->Flags = RememberFlags;
02402             UnusedEntry->Size = (USHORT)FreeSize;
02403 
02404             /* Insert it to the heap and update total size  */
02405             RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02406             Heap->TotalFreeSize += FreeSize;
02407         }
02408         else
02409         {
02410             /* There is a block after this one  */
02411             FollowingEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)UnusedEntry + FreeSize);
02412 
02413             if (FollowingEntry->Flags & HEAP_ENTRY_BUSY)
02414             {
02415                 /* Update flags and set size of the unused space entry */
02416                 UnusedEntry->Flags = RememberFlags & (~HEAP_ENTRY_LAST_ENTRY);
02417                 UnusedEntry->Size = (USHORT)FreeSize;
02418 
02419                 /* Update previous size of the following entry */
02420                 FollowingEntry->PreviousSize = (USHORT)FreeSize;
02421 
02422                 /* Insert it to the heap and update total free size */
02423                 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02424                 Heap->TotalFreeSize += FreeSize;
02425             }
02426             else
02427             {
02428                 /* That following entry is also free, what a fortune! */
02429                 RememberFlags = FollowingEntry->Flags;
02430 
02431                 /* Remove it */
02432                 RtlpRemoveFreeBlock(Heap, FollowingEntry, FALSE, FALSE);
02433                 Heap->TotalFreeSize -= FollowingEntry->Size;
02434 
02435                 /* And make up a new combined block */
02436                 FreeSize += FollowingEntry->Size;
02437                 UnusedEntry->Flags = RememberFlags;
02438 
02439                 /* Check where to put it */
02440                 if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
02441                 {
02442                     /* Fine for a dedicated list */
02443                     UnusedEntry->Size = (USHORT)FreeSize;
02444 
02445                     if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
02446                         ((PHEAP_ENTRY)UnusedEntry + FreeSize)->PreviousSize = (USHORT)FreeSize;
02447 
02448                     /* Insert it back and update total size */
02449                     RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
02450                     Heap->TotalFreeSize += FreeSize;
02451                 }
02452                 else
02453                 {
02454                     /* The block is very large, leave all the hassle to the insertion routine */
02455                     RtlpInsertFreeBlock(Heap, UnusedEntry, FreeSize);
02456                 }
02457             }
02458         }
02459     }
02460 
02461     /* Properly "zero out" (and fill!) the space */
02462     if (Flags & HEAP_ZERO_MEMORY)
02463     {
02464         RtlZeroMemory((PCHAR)(InUseEntry + 1) + PrevSize, Size - PrevSize);
02465     }
02466     else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02467     {
02468         /* Calculate tail part which we need to fill */
02469         TailPart = PrevSize & (sizeof(ULONG) - 1);
02470 
02471         /* "Invert" it as usual */
02472         if (TailPart) TailPart = 4 - TailPart;
02473 
02474         if (Size > (PrevSize + TailPart))
02475             AddedSize = (Size - (PrevSize + TailPart)) & ~(sizeof(ULONG) - 1);
02476 
02477         if (AddedSize)
02478         {
02479             RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + PrevSize + TailPart,
02480                                AddedSize,
02481                                ARENA_INUSE_FILLER);
02482         }
02483     }
02484 
02485     /* Fill the new tail */
02486     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02487     {
02488         RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
02489                       HEAP_ENTRY_SIZE,
02490                       HEAP_TAIL_FILL);
02491     }
02492 
02493     /* Copy user settable flags */
02494     InUseEntry->Flags &= ~HEAP_ENTRY_SETTABLE_FLAGS;
02495     InUseEntry->Flags |= ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4);
02496 
02497     /* Return success */
02498     return TRUE;
02499 }
02500 
02501 PHEAP_ENTRY_EXTRA NTAPI
02502 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry)
02503 {
02504     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
02505 
02506     /* Check if it's a big block */
02507     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02508     {
02509         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02510 
02511         /* Return a pointer to the extra stuff*/
02512         return &VirtualEntry->ExtraStuff;
02513     }
02514     else
02515     {
02516         /* This is a usual entry, which means extra stuff follows this block */
02517         return (PHEAP_ENTRY_EXTRA)(HeapEntry + HeapEntry->Size - 1);
02518     }
02519 }
02520 
02521 
02522 /***********************************************************************
02523  *           RtlReAllocateHeap
02524  * PARAMS
02525  *   Heap   [in] Handle of heap block
02526  *   Flags    [in] Heap reallocation flags
02527  *   Ptr,    [in] Address of memory to reallocate
02528  *   Size     [in] Number of bytes to reallocate
02529  *
02530  * RETURNS
02531  * Pointer to reallocated memory block
02532  * NULL: Failure
02533  * 0x7d030f60--invalid flags in RtlHeapAllocate
02534  * @implemented
02535  */
02536 PVOID NTAPI
02537 RtlReAllocateHeap(HANDLE HeapPtr,
02538                   ULONG Flags,
02539                   PVOID Ptr,
02540                   SIZE_T Size)
02541 {
02542     PHEAP Heap = (PHEAP)HeapPtr;
02543     PHEAP_ENTRY InUseEntry, NewInUseEntry;
02544     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
02545     SIZE_T AllocationSize, FreeSize, DecommitSize;
02546     BOOLEAN HeapLocked = FALSE;
02547     PVOID NewBaseAddress;
02548     PHEAP_FREE_ENTRY SplitBlock, SplitBlock2;
02549     SIZE_T OldSize, Index, OldIndex;
02550     UCHAR FreeFlags;
02551     NTSTATUS Status;
02552     PVOID DecommitBase;
02553     SIZE_T RemainderBytes, ExtraSize;
02554     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
02555     EXCEPTION_RECORD ExceptionRecord;
02556 
02557     /* Return success in case of a null pointer */
02558     if (!Ptr)
02559     {
02560         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS);
02561         return NULL;
02562     }
02563 
02564     /* Force heap flags */
02565     Flags |= Heap->ForceFlags;
02566 
02567     /* Call special heap */
02568     if (RtlpHeapIsSpecial(Flags))
02569         return RtlDebugReAllocateHeap(Heap, Flags, Ptr, Size);
02570 
02571     /* Make sure size is valid */
02572     if (Size >= 0x80000000)
02573     {
02574         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
02575         return NULL;
02576     }
02577 
02578     /* Calculate allocation size and index */
02579     if (Size)
02580         AllocationSize = Size;
02581     else
02582         AllocationSize = 1;
02583     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
02584 
02585     /* Add up extra stuff, if it is present anywhere */
02586     if (((((PHEAP_ENTRY)Ptr)-1)->Flags & HEAP_ENTRY_EXTRA_PRESENT) ||
02587         (Flags & HEAP_EXTRA_FLAGS_MASK) ||
02588         Heap->PseudoTagEntries)
02589     {
02590         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
02591     }
02592 
02593     /* Acquire the lock if necessary */
02594     if (!(Flags & HEAP_NO_SERIALIZE))
02595     {
02596         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02597         HeapLocked = TRUE;
02598         Flags &= ~HEAP_NO_SERIALIZE;
02599     }
02600 
02601     /* Get the pointer to the in-use entry */
02602     InUseEntry = (PHEAP_ENTRY)Ptr - 1;
02603 
02604     /* If that entry is not really in-use, we have a problem */
02605     if (!(InUseEntry->Flags & HEAP_ENTRY_BUSY))
02606     {
02607         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
02608 
02609         /* Release the lock and return */
02610         if (HeapLocked)
02611             RtlLeaveHeapLock(Heap->LockVariable);
02612         return Ptr;
02613     }
02614 
02615     if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02616     {
02617         /* This is a virtually allocated block. Get its size */
02618         OldSize = RtlpGetSizeOfBigBlock(InUseEntry);
02619 
02620         /* Convert it to an index */
02621         OldIndex = (OldSize + InUseEntry->Size) >> HEAP_ENTRY_SHIFT;
02622 
02623         /* Calculate new allocation size and round it to the page size */
02624         AllocationSize += FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02625         AllocationSize = ROUND_UP(AllocationSize, PAGE_SIZE);
02626     }
02627     else
02628     {
02629         /* Usual entry */
02630         OldIndex = InUseEntry->Size;
02631 
02632         OldSize = (OldIndex << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
02633     }
02634 
02635     /* Calculate new index */
02636     Index = AllocationSize >> HEAP_ENTRY_SHIFT;
02637 
02638     /* Check for 4 different scenarios (old size, new size, old index, new index) */
02639     if (Index <= OldIndex)
02640     {
02641         /* Difference must be greater than 1, adjust if it's not so */
02642         if (Index + 1 == OldIndex)
02643         {
02644             Index++;
02645             AllocationSize += sizeof(HEAP_ENTRY);
02646         }
02647 
02648         /* Calculate new size */
02649         if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
02650         {
02651             /* Simple in case of a virtual alloc - just an unused size */
02652             InUseEntry->Size = (USHORT)(AllocationSize - Size);
02653             ASSERT(InUseEntry->Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY));
02654         }
02655         else if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02656         {
02657             /* There is extra stuff, take it into account */
02658             OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
02659             NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
02660             *NewExtra = *OldExtra;
02661 
02662             // FIXME Tagging, TagIndex
02663 
02664             /* Update unused bytes count */
02665             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
02666         }
02667         else
02668         {
02669             // FIXME Tagging, SmallTagIndex
02670             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
02671         }
02672 
02673         /* If new size is bigger than the old size */
02674         if (Size > OldSize)
02675         {
02676             /* Zero out that additional space if required */
02677             if (Flags & HEAP_ZERO_MEMORY)
02678             {
02679                 RtlZeroMemory((PCHAR)Ptr + OldSize, Size - OldSize);
02680             }
02681             else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
02682             {
02683                 /* Fill it on free if required */
02684                 RemainderBytes = OldSize & (sizeof(ULONG) - 1);
02685 
02686                 if (RemainderBytes)
02687                     RemainderBytes = 4 - RemainderBytes;
02688 
02689                 if (Size > (OldSize + RemainderBytes))
02690                 {
02691                     /* Calculate actual amount of extra bytes to fill */
02692                     ExtraSize = (Size - (OldSize + RemainderBytes)) & ~(sizeof(ULONG) - 1);
02693 
02694                     /* Fill them if there are any */
02695                     if (ExtraSize != 0)
02696                     {
02697                         RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + OldSize + RemainderBytes,
02698                                            ExtraSize,
02699                                            ARENA_INUSE_FILLER);
02700                     }
02701                 }
02702             }
02703         }
02704 
02705         /* Fill tail of the heap entry if required */
02706         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
02707         {
02708             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
02709                           HEAP_ENTRY_SIZE,
02710                           HEAP_TAIL_FILL);
02711         }
02712 
02713         /* Check if the difference is significant or not */
02714         if (Index != OldIndex)
02715         {
02716             /* Save flags */
02717             FreeFlags = InUseEntry->Flags & ~HEAP_ENTRY_BUSY;
02718 
02719             if (FreeFlags & HEAP_ENTRY_VIRTUAL_ALLOC)
02720             {
02721                 /* This is a virtual block allocation */
02722                 VirtualAllocBlock = CONTAINING_RECORD(InUseEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
02723 
02724                 // FIXME Tagging!
02725 
02726                 DecommitBase = (PCHAR)VirtualAllocBlock + AllocationSize;
02727                 DecommitSize = (OldIndex << HEAP_ENTRY_SHIFT) - AllocationSize;
02728 
02729                 /* Release the memory */
02730                 Status = ZwFreeVirtualMemory(NtCurrentProcess(),
02731                                              (PVOID *)&DecommitBase,
02732                                              &DecommitSize,
02733                                              MEM_RELEASE);
02734 
02735                 if (!NT_SUCCESS(Status))
02736                 {
02737                     DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase, DecommitSize, Status);
02738                 }
02739                 else
02740                 {
02741                     /* Otherwise reduce the commit size */
02742                     VirtualAllocBlock->CommitSize -= DecommitSize;
02743                 }
02744             }
02745             else
02746             {
02747                 /* Reduce size of the block and possibly split it */
02748                 SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
02749 
02750                 /* Initialize this entry */
02751                 SplitBlock->Flags = FreeFlags;
02752                 SplitBlock->PreviousSize = (USHORT)Index;
02753                 SplitBlock->SegmentOffset = InUseEntry->SegmentOffset;
02754 
02755                 /* Remember free size */
02756                 FreeSize = InUseEntry->Size - Index;
02757 
02758                 /* Set new size */
02759                 InUseEntry->Size = (USHORT)Index;
02760                 InUseEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
02761 
02762                 /* Is that the last entry */
02763                 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
02764                 {
02765                     /* Set its size and insert it to the list */
02766                     SplitBlock->Size = (USHORT)FreeSize;
02767                     RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02768 
02769                     /* Update total free size */
02770                     Heap->TotalFreeSize += FreeSize;
02771                 }
02772                 else
02773                 {
02774                     /* Get the block after that one */
02775                     SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
02776 
02777                     if (SplitBlock2->Flags & HEAP_ENTRY_BUSY)
02778                     {
02779                         /* It's in use, add it here*/
02780                         SplitBlock->Size = (USHORT)FreeSize;
02781 
02782                         /* Update previous size of the next entry */
02783                         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
02784 
02785                         /* Insert it to the list */
02786                         RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02787 
02788                         /* Update total size */
02789                         Heap->TotalFreeSize += FreeSize;
02790                     }
02791                     else
02792                     {
02793                         /* Next entry is free, so merge with it */
02794                         SplitBlock->Flags = SplitBlock2->Flags;
02795 
02796                         /* Remove it, update total size */
02797                         RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE, FALSE);
02798                         Heap->TotalFreeSize -= SplitBlock2->Size;
02799 
02800                         /* Calculate total free size */
02801                         FreeSize += SplitBlock2->Size;
02802 
02803                         if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
02804                         {
02805                             SplitBlock->Size = (USHORT)FreeSize;
02806 
02807                             if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY))
02808                             {
02809                                 /* Update previous size of the next entry */
02810                                 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
02811                             }
02812 
02813                             /* Insert the new one back and update total size */
02814                             RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
02815                             Heap->TotalFreeSize += FreeSize;
02816                         }
02817                         else
02818                         {
02819                             /* Just add it */
02820                             RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize);
02821                         }
02822                     }
02823                 }
02824             }
02825         }
02826     }
02827     else
02828     {
02829         /* We're growing the block */
02830         if ((InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) ||
02831             !RtlpGrowBlockInPlace(Heap, Flags, InUseEntry, Size, Index))
02832         {
02833             /* Growing in place failed, so growing out of place */
02834             if (Flags & HEAP_REALLOC_IN_PLACE_ONLY)
02835             {
02836                 DPRINT1("Realloc in place failed, but it was the only option\n");
02837                 Ptr = NULL;
02838             }
02839             else
02840             {
02841                 /* Clear tag bits */
02842                 Flags &= ~HEAP_TAG_MASK;
02843 
02844                 /* Process extra stuff */
02845                 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02846                 {
02847                     /* Preserve user settable flags */
02848                     Flags &= ~HEAP_SETTABLE_USER_FLAGS;
02849 
02850                     Flags |= HEAP_SETTABLE_USER_VALUE | ((InUseEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4);
02851 
02852                     /* Get pointer to the old extra data */
02853                     OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
02854 
02855                     /* Save tag index if it was set */
02856                     if (OldExtra->TagIndex &&
02857                         !(OldExtra->TagIndex & HEAP_PSEUDO_TAG_FLAG))
02858                     {
02859                         Flags |= OldExtra->TagIndex << HEAP_TAG_SHIFT;
02860                     }
02861                 }
02862                 else if (InUseEntry->SmallTagIndex)
02863                 {
02864                     /* Take small tag index into account */
02865                     Flags |= InUseEntry->SmallTagIndex << HEAP_TAG_SHIFT;
02866                 }
02867 
02868                 /* Allocate new block from the heap */
02869                 NewBaseAddress = RtlAllocateHeap(HeapPtr,
02870                                                  Flags & ~HEAP_ZERO_MEMORY,
02871                                                  Size);
02872 
02873                 /* Proceed if it didn't fail */
02874                 if (NewBaseAddress)
02875                 {
02876                     /* Get new entry pointer */
02877                     NewInUseEntry = (PHEAP_ENTRY)NewBaseAddress - 1;
02878 
02879                     /* Process extra stuff if it exists */
02880                     if (NewInUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02881                     {
02882                         NewExtra = RtlpGetExtraStuffPointer(NewInUseEntry);
02883 
02884                         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
02885                         {
02886                             OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
02887                             NewExtra->Settable = OldExtra->Settable;
02888                         }
02889                         else
02890                         {
02891                             RtlZeroMemory(NewExtra, sizeof(*NewExtra));
02892                         }
02893                     }
02894 
02895                     /* Copy actual user bits */
02896                     if (Size < OldSize)
02897                         RtlMoveMemory(NewBaseAddress, Ptr, Size);
02898                     else
02899                         RtlMoveMemory(NewBaseAddress, Ptr, OldSize);
02900 
02901                     /* Zero remaining part if required */
02902                     if (Size > OldSize &&
02903                         (Flags & HEAP_ZERO_MEMORY))
02904                     {
02905                         RtlZeroMemory((PCHAR)NewBaseAddress + OldSize, Size - OldSize);
02906                     }
02907 
02908                     /* Free the old block */
02909                     RtlFreeHeap(HeapPtr, Flags, Ptr);
02910                 }
02911 
02912                 Ptr = NewBaseAddress;
02913             }
02914         }
02915     }
02916 
02917     /* Did resizing fail? */
02918     if (!Ptr && (Flags & HEAP_GENERATE_EXCEPTIONS))
02919     {
02920         /* Generate an exception if required */
02921         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
02922         ExceptionRecord.ExceptionRecord = NULL;
02923         ExceptionRecord.NumberParameters = 1;
02924         ExceptionRecord.ExceptionFlags = 0;
02925         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
02926 
02927         RtlRaiseException(&ExceptionRecord);
02928     }
02929 
02930     /* Release the heap lock if it was acquired */
02931     if (HeapLocked)
02932         RtlLeaveHeapLock(Heap->LockVariable);
02933 
02934     return Ptr;
02935 }
02936 
02937 
02938 /***********************************************************************
02939  *           RtlCompactHeap
02940  *
02941  * @unimplemented
02942  */
02943 ULONG NTAPI
02944 RtlCompactHeap(HANDLE Heap,
02945         ULONG Flags)
02946 {
02947    UNIMPLEMENTED;
02948    return 0;
02949 }
02950 
02951 
02952 /***********************************************************************
02953  *           RtlLockHeap
02954  * Attempts to acquire the critical section object for a specified heap.
02955  *
02956  * PARAMS
02957  *   Heap  [in] Handle of heap to lock for exclusive access
02958  *
02959  * RETURNS
02960  * TRUE: Success
02961  * FALSE: Failure
02962  *
02963  * @implemented
02964  */
02965 BOOLEAN NTAPI
02966 RtlLockHeap(IN HANDLE HeapPtr)
02967 {
02968     PHEAP Heap = (PHEAP)HeapPtr;
02969 
02970     // FIXME Check for special heap
02971 
02972     /* Check if it's really a heap */
02973     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
02974 
02975     /* Lock if it's lockable */
02976     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
02977     {
02978         RtlEnterHeapLock(Heap->LockVariable, TRUE);
02979     }
02980 
02981     return TRUE;
02982 }
02983 
02984 
02985 /***********************************************************************
02986  *           RtlUnlockHeap
02987  * Releases ownership of the critical section object.
02988  *
02989  * PARAMS
02990  *   Heap  [in] Handle to the heap to unlock
02991  *
02992  * RETURNS
02993  * TRUE: Success
02994  * FALSE: Failure
02995  *
02996  * @implemented
02997  */
02998 BOOLEAN NTAPI
02999 RtlUnlockHeap(HANDLE HeapPtr)
03000 {
03001     PHEAP Heap = (PHEAP)HeapPtr;
03002 
03003     // FIXME Check for special heap
03004 
03005     /* Check if it's really a heap */
03006     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
03007 
03008     /* Unlock if it's lockable */
03009     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03010     {
03011         RtlLeaveHeapLock(Heap->LockVariable);
03012     }
03013 
03014     return TRUE;
03015 }
03016 
03017 
03018 /***********************************************************************
03019  *           RtlSizeHeap
03020  * PARAMS
03021  *   Heap  [in] Handle of heap
03022  *   Flags   [in] Heap size control flags
03023  *   Ptr     [in] Address of memory to return size for
03024  *
03025  * RETURNS
03026  * Size in bytes of allocated memory
03027  * 0xffffffff: Failure
03028  *
03029  * @implemented
03030  */
03031 SIZE_T NTAPI
03032 RtlSizeHeap(
03033    HANDLE HeapPtr,
03034    ULONG Flags,
03035    PVOID Ptr
03036 )
03037 {
03038     PHEAP Heap = (PHEAP)HeapPtr;
03039     PHEAP_ENTRY HeapEntry;
03040     SIZE_T EntrySize;
03041 
03042     // FIXME This is a hack around missing SEH support!
03043     if (!Heap)
03044     {
03045         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE);
03046         return (SIZE_T)-1;
03047     }
03048 
03049     /* Force flags */
03050     Flags |= Heap->ForceFlags;
03051 
03052     /* Call special heap */
03053     if (RtlpHeapIsSpecial(Flags))
03054         return RtlDebugSizeHeap(Heap, Flags, Ptr);
03055 
03056     /* Get the heap entry pointer */
03057     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
03058 
03059     /* Return -1 if that entry is free */
03060     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03061     {
03062         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03063         return (SIZE_T)-1;
03064     }
03065 
03066     /* Get size of this block depending if it's a usual or a big one */
03067     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
03068     {
03069         EntrySize = RtlpGetSizeOfBigBlock(HeapEntry);
03070     }
03071     else
03072     {
03073         /* Calculate it */
03074         EntrySize = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
03075     }
03076 
03077     /* Return calculated size */
03078     return EntrySize;
03079 }
03080 
03081 BOOLEAN NTAPI
03082 RtlpCheckInUsePattern(PHEAP_ENTRY HeapEntry)
03083 {
03084     SIZE_T Size, Result;
03085     PCHAR TailPart;
03086 
03087     /* Calculate size */
03088     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
03089         Size = RtlpGetSizeOfBigBlock(HeapEntry);
03090     else
03091         Size = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
03092 
03093     /* Calculate pointer to the tail part of the block */
03094     TailPart = (PCHAR)(HeapEntry + 1) + Size;
03095 
03096     /* Compare tail pattern */
03097     Result = RtlCompareMemory(TailPart,
03098                               FillPattern,
03099                               HEAP_ENTRY_SIZE);
03100 
03101     if (Result != HEAP_ENTRY_SIZE)
03102     {
03103         DPRINT1("HEAP: Heap entry (size %x) %p tail is modified at %p\n", Size, HeapEntry, TailPart + Result);
03104         return FALSE;
03105     }
03106 
03107     /* All is fine */
03108     return TRUE;
03109 }
03110 
03111 BOOLEAN NTAPI
03112 RtlpValidateHeapHeaders(
03113     PHEAP Heap,
03114     BOOLEAN Recalculate)
03115 {
03116     // We skip header validation for now
03117     return TRUE;
03118 }
03119 
03120 BOOLEAN NTAPI
03121 RtlpValidateHeapEntry(
03122     PHEAP Heap,
03123     PHEAP_ENTRY HeapEntry)
03124 {
03125     BOOLEAN BigAllocation, EntryFound = FALSE;
03126     PHEAP_SEGMENT Segment;
03127     ULONG SegmentOffset;
03128 
03129     /* Perform various consistency checks of this entry */
03130     if (!HeapEntry) goto invalid_entry;
03131     if ((ULONG_PTR)HeapEntry & (HEAP_ENTRY_SIZE - 1)) goto invalid_entry;
03132     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) goto invalid_entry;
03133 
03134     BigAllocation = HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC;
03135     Segment = Heap->Segments[HeapEntry->SegmentOffset];
03136 
03137     if (BigAllocation &&
03138         (((ULONG_PTR)HeapEntry & (PAGE_SIZE - 1)) != FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock)))
03139          goto invalid_entry;
03140 
03141     if (!BigAllocation && (HeapEntry->SegmentOffset >= HEAP_SEGMENTS ||
03142         !Segment ||
03143         HeapEntry < Segment->FirstEntry ||
03144         HeapEntry >= Segment->LastValidEntry))
03145         goto invalid_entry;
03146 
03147     if ((HeapEntry->Flags & HEAP_ENTRY_FILL_PATTERN) &&
03148         !RtlpCheckInUsePattern(HeapEntry))
03149         goto invalid_entry;
03150 
03151     /* Checks are done, if this is a virtual entry, that's all */
03152     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) return TRUE;
03153 
03154     /* Go through segments and check if this entry fits into any of them */
03155     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
03156     {
03157         Segment = Heap->Segments[SegmentOffset];
03158         if (!Segment) continue;
03159 
03160         if ((HeapEntry >= Segment->FirstEntry) &&
03161             (HeapEntry < Segment->LastValidEntry))
03162         {
03163             /* Got it */
03164             EntryFound = TRUE;
03165             break;
03166         }
03167     }
03168 
03169     /* Return our result of finding entry in the segments */
03170     return EntryFound;
03171 
03172 invalid_entry:
03173     DPRINT1("HEAP: Invalid heap entry %p in heap %p\n", HeapEntry, Heap);
03174     return FALSE;
03175 }
03176 
03177 BOOLEAN NTAPI
03178 RtlpValidateHeapSegment(
03179     PHEAP Heap,
03180     PHEAP_SEGMENT Segment,
03181     UCHAR SegmentOffset,
03182     PULONG FreeEntriesCount,
03183     PSIZE_T TotalFreeSize,
03184     PSIZE_T TagEntries,
03185     PSIZE_T PseudoTagEntries)
03186 {
03187     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
03188     PLIST_ENTRY UcrEntry;
03189     SIZE_T ByteSize, Size, Result;
03190     PHEAP_ENTRY CurrentEntry;
03191     ULONG UnCommittedPages;
03192     ULONG UnCommittedRanges;
03193     ULONG PreviousSize;
03194 
03195     UnCommittedPages = 0;
03196     UnCommittedRanges = 0;
03197 
03198     if (IsListEmpty(&Segment->UCRSegmentList))
03199     {
03200         UcrEntry = NULL;
03201         UcrDescriptor = NULL;
03202     }
03203     else
03204     {
03205         UcrEntry = Segment->UCRSegmentList.Flink;
03206         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
03207     }
03208 
03209     if (Segment->BaseAddress == Heap)
03210         CurrentEntry = &Heap->Entry;
03211     else
03212         CurrentEntry = &Segment->Entry;
03213 
03214     while (CurrentEntry < Segment->LastValidEntry)
03215     {
03216         if (UcrDescriptor &&
03217             ((PVOID)CurrentEntry >= UcrDescriptor->Address))
03218         {
03219             DPRINT1("HEAP: Entry %p is not inside uncommited range [%p .. %p)\n",
03220                     CurrentEntry, UcrDescriptor->Address,
03221                     (PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
03222 
03223             return FALSE;
03224         }
03225 
03226         PreviousSize = 0;
03227 
03228         while (CurrentEntry < Segment->LastValidEntry)
03229         {
03230             if (PreviousSize != CurrentEntry->PreviousSize)
03231             {
03232                 DPRINT1("HEAP: Entry %p has incorrect PreviousSize %x instead of %x\n",
03233                     CurrentEntry, CurrentEntry->PreviousSize, PreviousSize);
03234 
03235                 return FALSE;
03236             }
03237 
03238             PreviousSize = CurrentEntry->Size;
03239             Size = CurrentEntry->Size << HEAP_ENTRY_SHIFT;
03240 
03241             if (CurrentEntry->Flags & HEAP_ENTRY_BUSY)
03242             {
03243                 if (TagEntries)
03244                 {
03245                     UNIMPLEMENTED;
03246                 }
03247 
03248                 /* Check fill pattern */
03249                 if (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN)
03250                 {
03251                     if (!RtlpCheckInUsePattern(CurrentEntry))
03252                         return FALSE;
03253                 }
03254             }
03255             else
03256             {
03257                 /* The entry is free, increase free entries count and total free size */
03258                 *FreeEntriesCount = *FreeEntriesCount + 1;
03259                 *TotalFreeSize += CurrentEntry->Size;
03260 
03261                 if ((Heap->Flags & HEAP_FREE_CHECKING_ENABLED) &&
03262                     (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN))
03263                 {
03264                     ByteSize = Size - sizeof(HEAP_FREE_ENTRY);
03265 
03266                     if ((CurrentEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) &&
03267                         (ByteSize > sizeof(HEAP_FREE_ENTRY_EXTRA)))
03268                     {
03269                         ByteSize -= sizeof(HEAP_FREE_ENTRY_EXTRA);
03270                     }
03271 
03272                     Result = RtlCompareMemoryUlong((PCHAR)((PHEAP_FREE_ENTRY)CurrentEntry + 1),
03273                                                     ByteSize,
03274                                                     ARENA_FREE_FILLER);
03275 
03276                     if (Result != ByteSize)
03277                     {
03278                         DPRINT1("HEAP: Free heap block %p modified at %p after it was freed\n",
03279                             CurrentEntry,
03280                             (PCHAR)(CurrentEntry + 1) + Result);
03281 
03282                         return FALSE;
03283                     }
03284                 }
03285             }
03286 
03287             if (CurrentEntry->SegmentOffset != SegmentOffset)
03288             {
03289                 DPRINT1("HEAP: Heap entry %p SegmentOffset is incorrect %x (should be %x)\n",
03290                         CurrentEntry, SegmentOffset, CurrentEntry->SegmentOffset);
03291                 return FALSE;
03292             }
03293 
03294             /* Check if it's the last entry */
03295             if (CurrentEntry->Flags & HEAP_ENTRY_LAST_ENTRY)
03296             {
03297                 CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
03298 
03299                 if (!UcrDescriptor)
03300                 {
03301                     /* Check if it's not really the last one */
03302                     if (CurrentEntry != Segment->LastValidEntry)
03303                     {
03304                         DPRINT1("HEAP: Heap entry %p is not last block in segment (%p)\n",
03305                                 CurrentEntry, Segment->LastValidEntry);
03306                         return FALSE;
03307                     }
03308                 }
03309                 else if (CurrentEntry != UcrDescriptor->Address)
03310                 {
03311                     DPRINT1("HEAP: Heap entry %p does not match next uncommitted address (%p)\n",
03312                         CurrentEntry, UcrDescriptor->Address);
03313 
03314                     return FALSE;
03315                 }
03316                 else
03317                 {
03318                     UnCommittedPages += (ULONG)(UcrDescriptor->Size / PAGE_SIZE);
03319                     UnCommittedRanges++;
03320 
03321                     CurrentEntry = (PHEAP_ENTRY)((PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
03322 
03323                     /* Go to the next UCR descriptor */
03324                     UcrEntry = UcrEntry->Flink;
03325                     if (UcrEntry == &Segment->UCRSegmentList)
03326                     {
03327                         UcrEntry = NULL;
03328                         UcrDescriptor = NULL;
03329                     }
03330                     else
03331                     {
03332                         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
03333                     }
03334                 }
03335 
03336                 break;
03337             }
03338 
03339             /* Advance to the next entry */
03340             CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
03341         }
03342     }
03343 
03344     /* Check total numbers of UCP and UCR */
03345     if (Segment->NumberOfUnCommittedPages != UnCommittedPages)
03346     {
03347         DPRINT1("HEAP: Segment %p NumberOfUnCommittedPages is invalid (%x != %x)\n",
03348             Segment, Segment->NumberOfUnCommittedPages, UnCommittedPages);
03349 
03350         return FALSE;
03351     }
03352 
03353     if (Segment->NumberOfUnCommittedRanges != UnCommittedRanges)
03354     {
03355         DPRINT1("HEAP: Segment %p NumberOfUnCommittedRanges is invalid (%x != %x)\n",
03356             Segment, Segment->NumberOfUnCommittedRanges, UnCommittedRanges);
03357 
03358         return FALSE;
03359     }
03360 
03361     return TRUE;
03362 }
03363 
03364 BOOLEAN NTAPI
03365 RtlpValidateHeap(PHEAP Heap,
03366                  BOOLEAN ForceValidation)
03367 {
03368     PHEAP_SEGMENT Segment;
03369     BOOLEAN EmptyList;
03370     UCHAR SegmentOffset;
03371     SIZE_T Size, TotalFreeSize;
03372     ULONG PreviousSize;
03373     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
03374     PLIST_ENTRY ListHead, NextEntry;
03375     PHEAP_FREE_ENTRY FreeEntry;
03376     ULONG FreeBlocksCount, FreeListEntriesCount;
03377 
03378     /* Check headers */
03379     if (!RtlpValidateHeapHeaders(Heap, FALSE))
03380         return FALSE;
03381 
03382     /* Skip validation if it's not needed */
03383     if (!ForceValidation && !(Heap->Flags & HEAP_VALIDATE_ALL_ENABLED))
03384         return TRUE;
03385 
03386     /* Check free lists bitmaps */
03387     FreeListEntriesCount = 0;
03388     ListHead = &Heap->FreeLists[0];
03389 
03390     for (Size = 0; Size < HEAP_FREELISTS; Size++)
03391     {
03392         if (Size)
03393         {
03394             /* This is a dedicated list. Check if it's empty */
03395             EmptyList = IsListEmpty(ListHead);
03396 
03397             if (Heap->u.FreeListsInUseBytes[Size >> 3] & (1 << (Size & 7)))
03398             {
03399                 if (EmptyList)
03400                 {
03401                     DPRINT1("HEAP: Empty %x-free list marked as non-empty\n", Size);
03402                     return FALSE;
03403                 }
03404             }
03405             else
03406             {
03407                 if (!EmptyList)
03408                 {
03409                     DPRINT1("HEAP: Non-empty %x-free list marked as empty\n", Size);
03410                     return FALSE;
03411                 }
03412             }
03413         }
03414 
03415         /* Now check this list entries */
03416         NextEntry = ListHead->Flink;
03417         PreviousSize = 0;
03418 
03419         while (ListHead != NextEntry)
03420         {
03421             FreeEntry = CONTAINING_RECORD(NextEntry, HEAP_FREE_ENTRY, FreeList);
03422             NextEntry = NextEntry->Flink;
03423 
03424             /* If there is an in-use entry in a free list - that's quite a big problem */
03425             if (FreeEntry->Flags & HEAP_ENTRY_BUSY)
03426             {
03427                 DPRINT1("HEAP: %Ix-dedicated list free element %p is marked in-use\n", Size, FreeEntry);
03428                 return FALSE;
03429             }
03430 
03431             /* Check sizes according to that specific list's size */
03432             if ((Size == 0) && (FreeEntry->Size < HEAP_FREELISTS))
03433             {
03434                 DPRINT1("HEAP: Non dedicated list free element %p has size %x which would fit a dedicated list\n", FreeEntry, FreeEntry->Size);
03435                 return FALSE;
03436             }
03437             else if (Size && (FreeEntry->Size != Size))
03438             {
03439                 DPRINT1("HEAP: %Ix-dedicated list free element %p has incorrect size %x\n", Size, FreeEntry, FreeEntry->Size);
03440                 return FALSE;
03441             }
03442             else if ((Size == 0) && (FreeEntry->Size < PreviousSize))
03443             {
03444                 DPRINT1("HEAP: Non dedicated list free element %p is not put in order\n", FreeEntry);
03445                 return FALSE;
03446             }
03447 
03448             /* Remember previous size*/
03449             PreviousSize = FreeEntry->Size;
03450 
03451             /* Add up to the total amount of free entries */
03452             FreeListEntriesCount++;
03453         }
03454 
03455         /* Go to the head of the next free list */
03456         ListHead++;
03457     }
03458 
03459     /* Check big allocations */
03460     ListHead = &Heap->VirtualAllocdBlocks;
03461     NextEntry = ListHead->Flink;
03462 
03463     while (ListHead != NextEntry)
03464     {
03465         VirtualAllocBlock = CONTAINING_RECORD(NextEntry, HEAP_VIRTUAL_ALLOC_ENTRY, Entry);
03466 
03467         /* We can only check the fill pattern */
03468         if (VirtualAllocBlock->BusyBlock.Flags & HEAP_ENTRY_FILL_PATTERN)
03469         {
03470             if (!RtlpCheckInUsePattern(&VirtualAllocBlock->BusyBlock))
03471                 return FALSE;
03472         }
03473 
03474         NextEntry = NextEntry->Flink;
03475     }
03476 
03477     /* Check all segments */
03478     FreeBlocksCount = 0;
03479     TotalFreeSize = 0;
03480 
03481     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
03482     {
03483         Segment = Heap->Segments[SegmentOffset];
03484 
03485         /* Go to the next one if there is no segment */
03486         if (!Segment) continue;
03487 
03488         if (!RtlpValidateHeapSegment(Heap,
03489                                      Segment,
03490                                      SegmentOffset,
03491                                      &FreeBlocksCount,
03492                                      &TotalFreeSize,
03493                                      NULL,
03494                                      NULL))
03495         {
03496             return FALSE;
03497         }
03498     }
03499 
03500     if (FreeListEntriesCount != FreeBlocksCount)
03501     {
03502         DPRINT1("HEAP: Free blocks count in arena (%lu) does not match free blocks number in the free lists (%lu)\n", FreeBlocksCount, FreeListEntriesCount);
03503         return FALSE;
03504     }
03505 
03506     if (Heap->TotalFreeSize != TotalFreeSize)
03507     {
03508         DPRINT1("HEAP: Total size of free blocks in arena (%Iu) does not equal to the one in heap header (%Iu)\n", TotalFreeSize, Heap->TotalFreeSize);
03509         return FALSE;
03510     }
03511 
03512     return TRUE;
03513 }
03514 
03515 /***********************************************************************
03516  *           RtlValidateHeap
03517  * Validates a specified heap.
03518  *
03519  * PARAMS
03520  *   Heap  [in] Handle to the heap
03521  *   Flags   [in] Bit flags that control access during operation
03522  *   Block  [in] Optional pointer to memory block to validate
03523  *
03524  * NOTES
03525  * Flags is ignored.
03526  *
03527  * RETURNS
03528  * TRUE: Success
03529  * FALSE: Failure
03530  *
03531  * @implemented
03532  */
03533 BOOLEAN NTAPI RtlValidateHeap(
03534    HANDLE HeapPtr,
03535    ULONG Flags,
03536    PVOID Block
03537 )
03538 {
03539     PHEAP Heap = (PHEAP)HeapPtr;
03540     BOOLEAN HeapLocked = FALSE;
03541     BOOLEAN HeapValid;
03542 
03543     /* Check for page heap */
03544     if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS)
03545         return RtlpDebugPageHeapValidate(HeapPtr, Flags, Block);
03546 
03547     /* Check signature */
03548     if (Heap->Signature != HEAP_SIGNATURE)
03549     {
03550         DPRINT1("HEAP: Signature %lx is invalid for heap %p\n", Heap->Signature, Heap);
03551         return FALSE;
03552     }
03553 
03554     /* Force flags */
03555     Flags = Heap->ForceFlags;
03556 
03557     /* Acquire the lock if necessary */
03558     if (!(Flags & HEAP_NO_SERIALIZE))
03559     {
03560         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03561         HeapLocked = TRUE;
03562     }
03563 
03564     /* Either validate whole heap or just one entry */
03565     if (!Block)
03566         HeapValid = RtlpValidateHeap(Heap, TRUE);
03567     else
03568         HeapValid = RtlpValidateHeapEntry(Heap, (PHEAP_ENTRY)Block - 1);
03569 
03570     /* Unlock if it's lockable */
03571     if (HeapLocked)
03572     {
03573         RtlLeaveHeapLock(Heap->LockVariable);
03574     }
03575 
03576     return HeapValid;
03577 }
03578 
03579 /*
03580  * @implemented
03581  */
03582 NTSTATUS NTAPI
03583 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine,
03584                     PVOID lParam)
03585 {
03586     UNIMPLEMENTED;
03587     return STATUS_NOT_IMPLEMENTED;
03588 }
03589 
03590 
03591 /*
03592  * @implemented
03593  */
03594 ULONG NTAPI
03595 RtlGetProcessHeaps(ULONG count,
03596                    HANDLE *heaps)
03597 {
03598     UNIMPLEMENTED;
03599     return 0;
03600 }
03601 
03602 
03603 /*
03604  * @implemented
03605  */
03606 BOOLEAN NTAPI
03607 RtlValidateProcessHeaps(VOID)
03608 {
03609     UNIMPLEMENTED;
03610     return TRUE;
03611 }
03612 
03613 
03614 /*
03615  * @unimplemented
03616  */
03617 BOOLEAN NTAPI
03618 RtlZeroHeap(
03619     IN PVOID HeapHandle,
03620     IN ULONG Flags
03621     )
03622 {
03623     UNIMPLEMENTED;
03624     return FALSE;
03625 }
03626 
03627 /*
03628  * @implemented
03629  */
03630 BOOLEAN
03631 NTAPI
03632 RtlSetUserValueHeap(IN PVOID HeapHandle,
03633                     IN ULONG Flags,
03634                     IN PVOID BaseAddress,
03635                     IN PVOID UserValue)
03636 {
03637     PHEAP Heap = (PHEAP)HeapHandle;
03638     PHEAP_ENTRY HeapEntry;
03639     PHEAP_ENTRY_EXTRA Extra;
03640     BOOLEAN HeapLocked = FALSE, ValueSet = FALSE;
03641 
03642     /* Force flags */
03643     Flags |= Heap->Flags;
03644 
03645     /* Call special heap */
03646     if (RtlpHeapIsSpecial(Flags))
03647         return RtlDebugSetUserValueHeap(Heap, Flags, BaseAddress, UserValue);
03648 
03649     /* Lock if it's lockable */
03650     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03651     {
03652         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03653         HeapLocked = TRUE;
03654     }
03655 
03656     /* Get a pointer to the entry */
03657     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03658 
03659     /* If it's a free entry - return error */
03660     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03661     {
03662         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03663 
03664         /* Release the heap lock if it was acquired */
03665         if (HeapLocked)
03666             RtlLeaveHeapLock(Heap->LockVariable);
03667 
03668         return FALSE;
03669     }
03670 
03671     /* Check if this entry has an extra stuff associated with it */
03672     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
03673     {
03674         /* Use extra to store the value */
03675         Extra = RtlpGetExtraStuffPointer(HeapEntry);
03676         Extra->Settable = (ULONG_PTR)UserValue;
03677 
03678         /* Indicate that value was set */
03679         ValueSet = TRUE;
03680     }
03681 
03682     /* Release the heap lock if it was acquired */
03683     if (HeapLocked)
03684         RtlLeaveHeapLock(Heap->LockVariable);
03685 
03686     return ValueSet;
03687 }
03688 
03689 /*
03690  * @implemented
03691  */
03692 BOOLEAN
03693 NTAPI
03694 RtlSetUserFlagsHeap(IN PVOID HeapHandle,
03695                     IN ULONG Flags,
03696                     IN PVOID BaseAddress,
03697                     IN ULONG UserFlagsReset,
03698                     IN ULONG UserFlagsSet)
03699 {
03700     PHEAP Heap = (PHEAP)HeapHandle;
03701     PHEAP_ENTRY HeapEntry;
03702     BOOLEAN HeapLocked = FALSE;
03703 
03704     /* Force flags */
03705     Flags |= Heap->Flags;
03706 
03707     /* Call special heap */
03708     if (RtlpHeapIsSpecial(Flags))
03709         return RtlDebugSetUserFlagsHeap(Heap, Flags, BaseAddress, UserFlagsReset, UserFlagsSet);
03710 
03711     /* Lock if it's lockable */
03712     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03713     {
03714         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03715         HeapLocked = TRUE;
03716     }
03717 
03718     /* Get a pointer to the entry */
03719     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03720 
03721     /* If it's a free entry - return error */
03722     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03723     {
03724         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03725 
03726         /* Release the heap lock if it was acquired */
03727         if (HeapLocked)
03728             RtlLeaveHeapLock(Heap->LockVariable);
03729 
03730         return FALSE;
03731     }
03732 
03733     /* Set / reset flags */
03734     HeapEntry->Flags &= ~(UserFlagsReset >> 4);
03735     HeapEntry->Flags |= (UserFlagsSet >> 4);
03736 
03737     /* Release the heap lock if it was acquired */
03738     if (HeapLocked)
03739         RtlLeaveHeapLock(Heap->LockVariable);
03740 
03741     return TRUE;
03742 }
03743 
03744 /*
03745  * @implemented
03746  */
03747 BOOLEAN
03748 NTAPI
03749 RtlGetUserInfoHeap(IN PVOID HeapHandle,
03750                    IN ULONG Flags,
03751                    IN PVOID BaseAddress,
03752                    OUT PVOID *UserValue,
03753                    OUT PULONG UserFlags)
03754 {
03755     PHEAP Heap = (PHEAP)HeapHandle;
03756     PHEAP_ENTRY HeapEntry;
03757     PHEAP_ENTRY_EXTRA Extra;
03758     BOOLEAN HeapLocked = FALSE;
03759 
03760     /* Force flags */
03761     Flags |= Heap->Flags;
03762 
03763     /* Call special heap */
03764     if (RtlpHeapIsSpecial(Flags))
03765         return RtlDebugGetUserInfoHeap(Heap, Flags, BaseAddress, UserValue, UserFlags);
03766 
03767     /* Lock if it's lockable */
03768     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
03769     {
03770         RtlEnterHeapLock(Heap->LockVariable, TRUE);
03771         HeapLocked = TRUE;
03772     }
03773 
03774     /* Get a pointer to the entry */
03775     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
03776 
03777     /* If it's a free entry - return error */
03778     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
03779     {
03780         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
03781 
03782         /* Release the heap lock if it was acquired */
03783         if (HeapLocked)
03784             RtlLeaveHeapLock(Heap->LockVariable);
03785 
03786         return FALSE;
03787     }
03788 
03789     /* Check if this entry has an extra stuff associated with it */
03790     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
03791     {
03792         /* Get pointer to extra data */
03793         Extra = RtlpGetExtraStuffPointer(HeapEntry);
03794 
03795         /* Pass user value */
03796         if (UserValue)
03797             *UserValue = (PVOID)Extra->Settable;
03798     }
03799 
03800     /* Decode and return user flags */
03801     if (UserFlags)
03802         *UserFlags = (HeapEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4;
03803 
03804     /* Release the heap lock if it was acquired */
03805     if (HeapLocked)
03806         RtlLeaveHeapLock(Heap->LockVariable);
03807 
03808     return TRUE;
03809 }
03810 
03811 /*
03812  * @unimplemented
03813  */
03814 NTSTATUS
03815 NTAPI
03816 RtlUsageHeap(IN HANDLE Heap,
03817              IN ULONG Flags,
03818              OUT PRTL_HEAP_USAGE Usage)
03819 {
03820     /* TODO */
03821     UNIMPLEMENTED;
03822     return STATUS_NOT_IMPLEMENTED;
03823 }
03824 
03825 PWSTR
03826 NTAPI
03827 RtlQueryTagHeap(IN PVOID HeapHandle,
03828                 IN ULONG Flags,
03829                 IN USHORT TagIndex,
03830                 IN BOOLEAN ResetCounters,
03831                 OUT PRTL_HEAP_TAG_INFO HeapTagInfo)
03832 {
03833     /* TODO */
03834     UNIMPLEMENTED;
03835     return NULL;
03836 }
03837 
03838 ULONG
03839 NTAPI
03840 RtlExtendHeap(IN HANDLE Heap,
03841               IN ULONG Flags,
03842               IN PVOID P,
03843               IN SIZE_T Size)
03844 {
03845     /* TODO */
03846     UNIMPLEMENTED;
03847     return 0;
03848 }
03849 
03850 ULONG
03851 NTAPI
03852 RtlCreateTagHeap(IN HANDLE HeapHandle,
03853                  IN ULONG Flags,
03854                  IN PWSTR TagName,
03855                  IN PWSTR TagSubName)
03856 {
03857     /* TODO */
03858     UNIMPLEMENTED;
03859     return 0;
03860 }
03861 
03862 NTSTATUS
03863 NTAPI
03864 RtlWalkHeap(IN HANDLE HeapHandle,
03865             IN PVOID HeapEntry)
03866 {
03867     UNIMPLEMENTED;
03868     return STATUS_NOT_IMPLEMENTED;
03869 }
03870 
03871 PVOID
03872 NTAPI
03873 RtlProtectHeap(IN PVOID HeapHandle,
03874                IN BOOLEAN ReadOnly)
03875 {
03876     UNIMPLEMENTED;
03877     return NULL;
03878 }
03879 
03880 NTSTATUS
03881 NTAPI
03882 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL,
03883                       IN HEAP_INFORMATION_CLASS HeapInformationClass,
03884                       IN PVOID HeapInformation,
03885                       IN SIZE_T HeapInformationLength)
03886 {
03887     /* Setting heap information is not really supported except for enabling LFH */
03888     if (HeapInformationClass == HeapCompatibilityInformation)
03889     {
03890         /* Check buffer length */
03891         if (HeapInformationLength < sizeof(ULONG))
03892         {
03893             /* The provided buffer is too small */
03894             return STATUS_BUFFER_TOO_SMALL;
03895         }
03896 
03897         /* Check for a special magic value for enabling LFH */
03898         if (*(PULONG)HeapInformation != 2)
03899         {
03900             return STATUS_UNSUCCESSFUL;
03901         }
03902 
03903         DPRINT1("RtlSetHeapInformation() needs to enable LFH\n");
03904         return STATUS_SUCCESS;
03905     }
03906 
03907     return STATUS_SUCCESS;
03908 }
03909 
03910 NTSTATUS
03911 NTAPI
03912 RtlQueryHeapInformation(HANDLE HeapHandle,
03913                         HEAP_INFORMATION_CLASS HeapInformationClass,
03914                         PVOID HeapInformation,
03915                         SIZE_T HeapInformationLength,
03916                         PSIZE_T ReturnLength OPTIONAL)
03917 {
03918     PHEAP Heap = (PHEAP)HeapHandle;
03919 
03920     /* Only HeapCompatibilityInformation is supported */
03921     if (HeapInformationClass == HeapCompatibilityInformation)
03922     {
03923         /* Set result length */
03924         if (ReturnLength)
03925             *ReturnLength = sizeof(ULONG);
03926 
03927         /* Check buffer length */
03928         if (HeapInformationLength < sizeof(ULONG))
03929         {
03930             /* It's too small, return needed length */
03931             return STATUS_BUFFER_TOO_SMALL;
03932         }
03933 
03934         /* Return front end heap type */
03935         *(PULONG)HeapInformation = Heap->FrontEndHeapType;
03936 
03937         return STATUS_SUCCESS;
03938     }
03939 
03940     return STATUS_UNSUCCESSFUL;
03941 }
03942 
03943 NTSTATUS
03944 NTAPI
03945 RtlMultipleAllocateHeap(IN PVOID HeapHandle,
03946                         IN ULONG Flags,
03947                         IN SIZE_T Size,
03948                         IN ULONG Count,
03949                         OUT PVOID *Array)
03950 {
03951     UNIMPLEMENTED;
03952     return 0;
03953 }
03954 
03955 NTSTATUS
03956 NTAPI
03957 RtlMultipleFreeHeap(IN PVOID HeapHandle,
03958                     IN ULONG Flags,
03959                     IN ULONG Count,
03960                     OUT PVOID *Array)
03961 {
03962     UNIMPLEMENTED;
03963     return 0;
03964 }
03965 
03966 /* EOF */