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