Doxygen

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