sdk/lib/rtl/heap.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PROJECT:         ReactOS system libraries
   4  * FILE:            lib/rtl/heap.c
   5  * PURPOSE:         RTL Heap backend allocator
   6  * PROGRAMMERS:     Copyright 2010 Aleksey Bragin
   7  */
   8
   9 /* Useful references:
  10    http://msdn.microsoft.com/en-us/library/ms810466.aspx
  11    http://msdn.microsoft.com/en-us/library/ms810603.aspx
  12    http://www.securitylab.ru/analytics/216376.php
  13    http://binglongx.spaces.live.com/blog/cns!142CBF6D49079DE8!596.entry
  14    http://www.phreedom.org/research/exploits/asn1-bitstring/
  15    http://illmatics.com/Understanding_the_LFH.pdf
  16    http://www.alex-ionescu.com/?p=18
  17 */
  18
  19 /* INCLUDES *****************************************************************/
  20
  21 #include <rtl.h>
  22 #include <heap.h>
  23
  24 #define NDEBUG
  25 #include <debug.h>
  26
  27 /* Bitmaps stuff */
  28
  29 /* How many least significant bits are clear */
  30 UCHAR RtlpBitsClearLow[] =
  31 {
  32     8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  33     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  34     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  35     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  36     6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  37     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  38     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  39     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  40     7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  41     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  42     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  43     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  44     6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  45     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  46     5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  47     4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
  48 };
  49
  50 FORCEINLINE
  51 UCHAR
  52 RtlpFindLeastSetBit(ULONG Bits)
  53 {
  54     if (Bits & 0xFFFF)
  55     {
  56         if (Bits & 0xFF)
  57             return RtlpBitsClearLow[Bits & 0xFF]; /* Lowest byte */
  58         else
  59             return RtlpBitsClearLow[(Bits >> 8) & 0xFF] + 8; /* 2nd byte */
  60     }
  61     else
  62     {
  63         if ((Bits >> 16) & 0xFF)
  64             return RtlpBitsClearLow[(Bits >> 16) & 0xFF] + 16; /* 3rd byte */
  65         else
  66             return RtlpBitsClearLow[(Bits >> 24) & 0xFF] + 24; /* Highest byte */
  67     }
  68 }
  69
  70 /* Maximum size of a tail-filling pattern used for compare operation */
  71 UCHAR FillPattern[HEAP_ENTRY_SIZE] =
  72 {
  73     HEAP_TAIL_FILL,
  74     HEAP_TAIL_FILL,
  75     HEAP_TAIL_FILL,
  76     HEAP_TAIL_FILL,
  77     HEAP_TAIL_FILL,
  78     HEAP_TAIL_FILL,
  79     HEAP_TAIL_FILL,
  80     HEAP_TAIL_FILL
  81 };
  82
  83 /* FUNCTIONS *****************************************************************/
  84
  85 NTSTATUS NTAPI
  86 RtlpInitializeHeap(OUT PHEAP Heap,
  87                    IN ULONG Flags,
  88                    IN PHEAP_LOCK Lock OPTIONAL,
  89                    IN PRTL_HEAP_PARAMETERS Parameters)
  90 {
  91     ULONG NumUCRs = 8;
  92     ULONG Index;
  93     SIZE_T HeaderSize;
  94     NTSTATUS Status;
  95     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
  96
  97     /* Preconditions */
  98     ASSERT(Heap != NULL);
  99     ASSERT(Parameters != NULL);
 100     ASSERT(!(Flags & HEAP_LOCK_USER_ALLOCATED));
 101     ASSERT(!(Flags & HEAP_NO_SERIALIZE) || (Lock == NULL));  /* HEAP_NO_SERIALIZE => no lock */
 102
 103     /* Start out with the size of a plain Heap header */
 104     HeaderSize = ROUND_UP(sizeof(HEAP), sizeof(HEAP_ENTRY));
 105
 106     /* Check if space needs to be added for the Heap Lock */
 107     if (!(Flags & HEAP_NO_SERIALIZE))
 108     {
 109         if (Lock != NULL)
 110             /* The user manages the Heap Lock */
 111             Flags |= HEAP_LOCK_USER_ALLOCATED;
 112         else
 113         if (RtlpGetMode() == UserMode)
 114         {
 115             /* In user mode, the Heap Lock trails the Heap header */
 116             Lock = (PHEAP_LOCK) ((ULONG_PTR) (Heap) + HeaderSize);
 117             HeaderSize += ROUND_UP(sizeof(HEAP_LOCK), sizeof(HEAP_ENTRY));
 118         }
 119     }
 120
 121     /* Add space for the initial Heap UnCommitted Range Descriptor list */
 122     UcrDescriptor = (PHEAP_UCR_DESCRIPTOR) ((ULONG_PTR) (Heap) + HeaderSize);
 123     HeaderSize += ROUND_UP(NumUCRs * sizeof(HEAP_UCR_DESCRIPTOR), sizeof(HEAP_ENTRY));
 124
 125     /* Sanity check */
 126     ASSERT(HeaderSize <= PAGE_SIZE);
 127
 128     /* Initialise the Heap Entry header containing the Heap header */
 129     Heap->Entry.Size = (USHORT)(HeaderSize >> HEAP_ENTRY_SHIFT);
 130     Heap->Entry.Flags = HEAP_ENTRY_BUSY;
 131     Heap->Entry.SmallTagIndex = LOBYTE(Heap->Entry.Size) ^ HIBYTE(Heap->Entry.Size) ^ Heap->Entry.Flags;
 132     Heap->Entry.PreviousSize = 0;
 133     Heap->Entry.SegmentOffset = 0;
 134     Heap->Entry.UnusedBytes = 0;
 135
 136     /* Initialise the Heap header */
 137     Heap->Signature = HEAP_SIGNATURE;
 138     Heap->Flags = Flags;
 139     Heap->ForceFlags = (Flags & (HEAP_NO_SERIALIZE |
 140                                  HEAP_GENERATE_EXCEPTIONS |
 141                                  HEAP_ZERO_MEMORY |
 142                                  HEAP_REALLOC_IN_PLACE_ONLY |
 143                                  HEAP_VALIDATE_PARAMETERS_ENABLED |
 144                                  HEAP_VALIDATE_ALL_ENABLED |
 145                                  HEAP_TAIL_CHECKING_ENABLED |
 146                                  HEAP_CREATE_ALIGN_16 |
 147                                  HEAP_FREE_CHECKING_ENABLED));
 148
 149     /* Initialise the Heap parameters */
 150     Heap->VirtualMemoryThreshold = ROUND_UP(Parameters->VirtualMemoryThreshold, sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT;
 151     Heap->SegmentReserve = Parameters->SegmentReserve;
 152     Heap->SegmentCommit = Parameters->SegmentCommit;
 153     Heap->DeCommitFreeBlockThreshold = Parameters->DeCommitFreeBlockThreshold >> HEAP_ENTRY_SHIFT;
 154     Heap->DeCommitTotalFreeThreshold = Parameters->DeCommitTotalFreeThreshold >> HEAP_ENTRY_SHIFT;
 155     Heap->MaximumAllocationSize = Parameters->MaximumAllocationSize;
 156     Heap->CommitRoutine = Parameters->CommitRoutine;
 157
 158     /* Initialise the Heap validation info */
 159     Heap->HeaderValidateCopy = NULL;
 160     Heap->HeaderValidateLength = (USHORT)HeaderSize;
 161
 162     /* Initialise the Heap Lock */
 163     if (!(Flags & HEAP_NO_SERIALIZE) && !(Flags & HEAP_LOCK_USER_ALLOCATED))
 164     {
 165         Status = RtlInitializeHeapLock(&Lock);
 166         if (!NT_SUCCESS(Status))
 167             return Status;
 168     }
 169     Heap->LockVariable = Lock;
 170
 171     /* Initialise the Heap alignment info */
 172     if (Flags & HEAP_CREATE_ALIGN_16)
 173     {
 174         Heap->AlignMask = (ULONG) ~15;
 175         Heap->AlignRound = 15 + sizeof(HEAP_ENTRY);
 176     }
 177     else
 178     {
 179         Heap->AlignMask = (ULONG) ~(sizeof(HEAP_ENTRY) - 1);
 180         Heap->AlignRound = 2 * sizeof(HEAP_ENTRY) - 1;
 181     }
 182
 183     if (Flags & HEAP_TAIL_CHECKING_ENABLED)
 184         Heap->AlignRound += sizeof(HEAP_ENTRY);
 185
 186     /* Initialise the Heap Segment list */
 187     for (Index = 0; Index < HEAP_SEGMENTS; ++Index)
 188         Heap->Segments[Index] = NULL;
 189
 190     /* Initialise the Heap Free Heap Entry lists */
 191     for (Index = 0; Index < HEAP_FREELISTS; ++Index)
 192         InitializeListHead(&Heap->FreeLists[Index]);
 193
 194     /* Initialise the Heap Virtual Allocated Blocks list */
 195     InitializeListHead(&Heap->VirtualAllocdBlocks);
 196
 197     /* Initialise the Heap UnCommitted Region lists */
 198     InitializeListHead(&Heap->UCRSegments);
 199     InitializeListHead(&Heap->UCRList);
 200
 201     /* Register the initial Heap UnCommitted Region Descriptors */
 202     for (Index = 0; Index < NumUCRs; ++Index)
 203         InsertTailList(&Heap->UCRList, &UcrDescriptor[Index].ListEntry);
 204
 205     return STATUS_SUCCESS;
 206 }
 207
 208 FORCEINLINE
 209 VOID
 210 RtlpSetFreeListsBit(PHEAP Heap,
 211                     PHEAP_FREE_ENTRY FreeEntry)
 212 {
 213     ULONG Index, Bit;
 214
 215     ASSERT(FreeEntry->Size < HEAP_FREELISTS);
 216
 217     /* Calculate offset in the free list bitmap */
 218     Index = FreeEntry->Size >> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
 219     Bit = 1 << (FreeEntry->Size & 7);
 220
 221     /* Assure it's not already set */
 222     ASSERT((Heap->u.FreeListsInUseBytes[Index] & Bit) == 0);
 223
 224     /* Set it */
 225     Heap->u.FreeListsInUseBytes[Index] |= Bit;
 226 }
 227
 228 FORCEINLINE
 229 VOID
 230 RtlpClearFreeListsBit(PHEAP Heap,
 231                       PHEAP_FREE_ENTRY FreeEntry)
 232 {
 233     ULONG Index, Bit;
 234
 235     ASSERT(FreeEntry->Size < HEAP_FREELISTS);
 236
 237     /* Calculate offset in the free list bitmap */
 238     Index = FreeEntry->Size >> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
 239     Bit = 1 << (FreeEntry->Size & 7);
 240
 241     /* Assure it was set and the corresponding free list is empty */
 242     ASSERT(Heap->u.FreeListsInUseBytes[Index] & Bit);
 243     ASSERT(IsListEmpty(&Heap->FreeLists[FreeEntry->Size]));
 244
 245     /* Clear it */
 246     Heap->u.FreeListsInUseBytes[Index] ^= Bit;
 247 }
 248
 249 VOID NTAPI
 250 RtlpInsertFreeBlockHelper(PHEAP Heap,
 251                           PHEAP_FREE_ENTRY FreeEntry,
 252                           SIZE_T BlockSize,
 253                           BOOLEAN NoFill)
 254 {
 255     PLIST_ENTRY FreeListHead, Current;
 256     PHEAP_FREE_ENTRY CurrentEntry;
 257
 258     ASSERT(FreeEntry->Size == BlockSize);
 259
 260     /* Fill if it's not denied */
 261     if (!NoFill)
 262     {
 263         FreeEntry->Flags &= ~(HEAP_ENTRY_FILL_PATTERN |
 264                               HEAP_ENTRY_EXTRA_PRESENT |
 265                               HEAP_ENTRY_BUSY);
 266
 267         if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
 268         {
 269             RtlFillMemoryUlong((PCHAR)(FreeEntry + 1),
 270                                (BlockSize << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry),
 271                                ARENA_FREE_FILLER);
 272
 273             FreeEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
 274         }
 275     }
 276     else
 277     {
 278         /* Clear out all flags except the last entry one */
 279         FreeEntry->Flags &= HEAP_ENTRY_LAST_ENTRY;
 280     }
 281
 282     /* Insert it either into dedicated or non-dedicated list */
 283     if (BlockSize < HEAP_FREELISTS)
 284     {
 285         /* Dedicated list */
 286         FreeListHead = &Heap->FreeLists[BlockSize];
 287
 288         if (IsListEmpty(FreeListHead))
 289         {
 290             RtlpSetFreeListsBit(Heap, FreeEntry);
 291         }
 292     }
 293     else
 294     {
 295         /* Non-dedicated one */
 296         FreeListHead = &Heap->FreeLists[0];
 297         Current = FreeListHead->Flink;
 298
 299         /* Find a position where to insert it to (the list must be sorted) */
 300         while (FreeListHead != Current)
 301         {
 302             CurrentEntry = CONTAINING_RECORD(Current, HEAP_FREE_ENTRY, FreeList);
 303
 304             if (BlockSize <= CurrentEntry->Size)
 305                 break;
 306
 307             Current = Current->Flink;
 308         }
 309
 310         FreeListHead = Current;
 311     }
 312
 313     /* Actually insert it into the list */
 314     InsertTailList(FreeListHead, &FreeEntry->FreeList);
 315 }
 316
 317 VOID NTAPI
 318 RtlpInsertFreeBlock(PHEAP Heap,
 319                     PHEAP_FREE_ENTRY FreeEntry,
 320                     SIZE_T BlockSize)
 321 {
 322     USHORT Size, PreviousSize;
 323     UCHAR SegmentOffset, Flags;
 324     PHEAP_SEGMENT Segment;
 325
 326     DPRINT("RtlpInsertFreeBlock(%p %p %x)\n", Heap, FreeEntry, BlockSize);
 327
 328     /* Increase the free size counter */
 329     Heap->TotalFreeSize += BlockSize;
 330
 331     /* Remember certain values */
 332     Flags = FreeEntry->Flags;
 333     PreviousSize = FreeEntry->PreviousSize;
 334     SegmentOffset = FreeEntry->SegmentOffset;
 335     Segment = Heap->Segments[SegmentOffset];
 336
 337     /* Process it */
 338     while (BlockSize)
 339     {
 340         /* Check for the max size */
 341         if (BlockSize > HEAP_MAX_BLOCK_SIZE)
 342         {
 343             Size = HEAP_MAX_BLOCK_SIZE;
 344
 345             /* Special compensation if it goes above limit just by 1 */
 346             if (BlockSize == (HEAP_MAX_BLOCK_SIZE + 1))
 347                 Size -= 16;
 348
 349             FreeEntry->Flags = 0;
 350         }
 351         else
 352         {
 353             Size = (USHORT)BlockSize;
 354             FreeEntry->Flags = Flags;
 355         }
 356
 357         /* Change its size and insert it into a free list */
 358         FreeEntry->Size = Size;
 359         FreeEntry->PreviousSize = PreviousSize;
 360         FreeEntry->SegmentOffset = SegmentOffset;
 361
 362         /* Call a helper to actually insert the block */
 363         RtlpInsertFreeBlockHelper(Heap, FreeEntry, Size, FALSE);
 364
 365         /* Update sizes */
 366         PreviousSize = Size;
 367         BlockSize -= Size;
 368
 369         /* Go to the next entry */
 370         FreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size);
 371
 372         /* Check if that's all */
 373         if ((PHEAP_ENTRY)FreeEntry >= Segment->LastValidEntry) return;
 374     }
 375
 376     /* Update previous size if needed */
 377     if (!(Flags & HEAP_ENTRY_LAST_ENTRY))
 378         FreeEntry->PreviousSize = PreviousSize;
 379 }
 380
 381 VOID NTAPI
 382 RtlpRemoveFreeBlock(PHEAP Heap,
 383                     PHEAP_FREE_ENTRY FreeEntry,
 384                     BOOLEAN Dedicated,
 385                     BOOLEAN NoFill)
 386 {
 387     SIZE_T Result, RealSize;
 388
 389     /* Remove the free block and update the freelists bitmap */
 390     if (RemoveEntryList(&FreeEntry->FreeList) &&
 391         (Dedicated || (!Dedicated && FreeEntry->Size < HEAP_FREELISTS)))
 392     {
 393         RtlpClearFreeListsBit(Heap, FreeEntry);
 394     }
 395
 396     /* Fill with pattern if necessary */
 397     if (!NoFill &&
 398         (FreeEntry->Flags & HEAP_ENTRY_FILL_PATTERN))
 399     {
 400         RealSize = (FreeEntry->Size << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry);
 401
 402         /* Deduct extra stuff from block's real size */
 403         if (FreeEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT &&
 404             RealSize > sizeof(HEAP_FREE_ENTRY_EXTRA))
 405         {
 406             RealSize -= sizeof(HEAP_FREE_ENTRY_EXTRA);
 407         }
 408
 409         /* Check if the free filler is intact */
 410         Result = RtlCompareMemoryUlong((PCHAR)(FreeEntry + 1),
 411                                         RealSize,
 412                                         ARENA_FREE_FILLER);
 413
 414         if (Result != RealSize)
 415         {
 416             DPRINT1("Free heap block %p modified at %p after it was freed\n",
 417                 FreeEntry,
 418                 (PCHAR)(FreeEntry + 1) + Result);
 419         }
 420     }
 421 }
 422
 423 SIZE_T NTAPI
 424 RtlpGetSizeOfBigBlock(PHEAP_ENTRY HeapEntry)
 425 {
 426     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
 427
 428     /* Get pointer to the containing record */
 429     VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
 430     ASSERT(VirtualEntry->BusyBlock.Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY));
 431
 432     /* Restore the real size */
 433     return VirtualEntry->CommitSize - HeapEntry->Size;
 434 }
 435
 436 PHEAP_UCR_DESCRIPTOR NTAPI
 437 RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment)
 438 {
 439     PLIST_ENTRY Entry;
 440     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
 441     PHEAP_UCR_SEGMENT UcrSegment;
 442     PHEAP Heap = Segment->Heap;
 443     SIZE_T ReserveSize = 16 * PAGE_SIZE;
 444     SIZE_T CommitSize = 1 * PAGE_SIZE;
 445     NTSTATUS Status;
 446
 447     DPRINT("RtlpCreateUnCommittedRange(%p)\n", Segment);
 448
 449     /* Check if we have unused UCRs */
 450     if (IsListEmpty(&Heap->UCRList))
 451     {
 452         /* Get a pointer to the first UCR segment */
 453         UcrSegment = CONTAINING_RECORD(Heap->UCRSegments.Flink, HEAP_UCR_SEGMENT, ListEntry);
 454
 455         /* Check the list of UCR segments */
 456         if (IsListEmpty(&Heap->UCRSegments) ||
 457             UcrSegment->ReservedSize == UcrSegment->CommittedSize)
 458         {
 459             /* We need to create a new one. Reserve 16 pages for it */
 460             UcrSegment = NULL;
 461             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 462                                              (PVOID *)&UcrSegment,
 463                                              0,
 464                                              &ReserveSize,
 465                                              MEM_RESERVE,
 466                                              PAGE_READWRITE);
 467
 468             if (!NT_SUCCESS(Status)) return NULL;
 469
 470             /* Commit one page */
 471             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 472                                              (PVOID *)&UcrSegment,
 473                                              0,
 474                                              &CommitSize,
 475                                              MEM_COMMIT,
 476                                              PAGE_READWRITE);
 477
 478             if (!NT_SUCCESS(Status))
 479             {
 480                 /* Release reserved memory */
 481                 ZwFreeVirtualMemory(NtCurrentProcess(),
 482                                     (PVOID *)&UcrSegment,
 483                                     &ReserveSize,
 484                                     MEM_RELEASE);
 485                 return NULL;
 486             }
 487
 488             /* Set it's data */
 489             UcrSegment->ReservedSize = ReserveSize;
 490             UcrSegment->CommittedSize = CommitSize;
 491
 492             /* Add it to the head of the list */
 493             InsertHeadList(&Heap->UCRSegments, &UcrSegment->ListEntry);
 494
 495             /* Get a pointer to the first available UCR descriptor */
 496             UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)(UcrSegment + 1);
 497         }
 498         else
 499         {
 500             /* It's possible to use existing UCR segment. Commit one more page */
 501             UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)((PCHAR)UcrSegment + UcrSegment->CommittedSize);
 502             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 503                                              (PVOID *)&UcrDescriptor,
 504                                              0,
 505                                              &CommitSize,
 506                                              MEM_COMMIT,
 507                                              PAGE_READWRITE);
 508
 509             if (!NT_SUCCESS(Status)) return NULL;
 510
 511             /* Update sizes */
 512             UcrSegment->CommittedSize += CommitSize;
 513         }
 514
 515         /* There is a whole bunch of new UCR descriptors. Put them into the unused list */
 516         while ((PCHAR)(UcrDescriptor + 1) <= (PCHAR)UcrSegment + UcrSegment->CommittedSize)
 517         {
 518             InsertTailList(&Heap->UCRList, &UcrDescriptor->ListEntry);
 519             UcrDescriptor++;
 520         }
 521     }
 522
 523     /* There are unused UCRs, just get the first one */
 524     Entry = RemoveHeadList(&Heap->UCRList);
 525     UcrDescriptor = CONTAINING_RECORD(Entry, HEAP_UCR_DESCRIPTOR, ListEntry);
 526     return UcrDescriptor;
 527 }
 528
 529 VOID NTAPI
 530 RtlpDestroyUnCommittedRange(PHEAP_SEGMENT Segment,
 531                             PHEAP_UCR_DESCRIPTOR UcrDescriptor)
 532 {
 533     /* Zero it out */
 534     UcrDescriptor->Address = NULL;
 535     UcrDescriptor->Size = 0;
 536
 537     /* Put it into the heap's list of unused UCRs */
 538     InsertHeadList(&Segment->Heap->UCRList, &UcrDescriptor->ListEntry);
 539 }
 540
 541 VOID NTAPI
 542 RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment,
 543                            ULONG_PTR Address,
 544                            SIZE_T Size)
 545 {
 546     PLIST_ENTRY Current;
 547     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
 548
 549     DPRINT("RtlpInsertUnCommittedPages(%p %08Ix %Ix)\n", Segment, Address, Size);
 550
 551     /* Go through the list of UCR descriptors, they are sorted from lowest address
 552        to the highest */
 553     Current = Segment->UCRSegmentList.Flink;
 554     while (Current != &Segment->UCRSegmentList)
 555     {
 556         UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry);
 557
 558         if ((ULONG_PTR)UcrDescriptor->Address > Address)
 559         {
 560             /* Check for a really lucky case */
 561             if ((Address + Size) == (ULONG_PTR)UcrDescriptor->Address)
 562             {
 563                 /* Exact match */
 564                 UcrDescriptor->Address = (PVOID)Address;
 565                 UcrDescriptor->Size += Size;
 566                 return;
 567             }
 568
 569             /* We found the block before which the new one should go */
 570             break;
 571         }
 572         else if (((ULONG_PTR)UcrDescriptor->Address + UcrDescriptor->Size) == Address)
 573         {
 574             /* Modify this entry */
 575             Address = (ULONG_PTR)UcrDescriptor->Address;
 576             Size += UcrDescriptor->Size;
 577
 578             /* Advance to the next descriptor */
 579             Current = Current->Flink;
 580
 581             /* Remove the current descriptor from the list and destroy it */
 582             RemoveEntryList(&UcrDescriptor->SegmentEntry);
 583             RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
 584
 585             Segment->NumberOfUnCommittedRanges--;
 586         }
 587         else
 588         {
 589             /* Advance to the next descriptor */
 590             Current = Current->Flink;
 591         }
 592     }
 593
 594     /* Create a new UCR descriptor */
 595     UcrDescriptor = RtlpCreateUnCommittedRange(Segment);
 596     if (!UcrDescriptor) return;
 597
 598     UcrDescriptor->Address = (PVOID)Address;
 599     UcrDescriptor->Size = Size;
 600
 601     /* "Current" is the descriptor before which our one should go */
 602     InsertTailList(Current, &UcrDescriptor->SegmentEntry);
 603
 604     DPRINT("Added segment UCR with base %08Ix, size 0x%x\n", Address, Size);
 605
 606     /* Increase counters */
 607     Segment->NumberOfUnCommittedRanges++;
 608 }
 609
 610 PHEAP_FREE_ENTRY NTAPI
 611 RtlpFindAndCommitPages(PHEAP Heap,
 612                        PHEAP_SEGMENT Segment,
 613                        PSIZE_T Size,
 614                        PVOID AddressRequested)
 615 {
 616     PLIST_ENTRY Current;
 617     ULONG_PTR Address = 0;
 618     PHEAP_UCR_DESCRIPTOR UcrDescriptor, PreviousUcr = NULL;
 619     PHEAP_ENTRY FirstEntry, LastEntry;
 620     NTSTATUS Status;
 621
 622     DPRINT("RtlpFindAndCommitPages(%p %p %Ix %08Ix)\n", Heap, Segment, *Size, Address);
 623
 624     /* Go through UCRs in a segment */
 625     Current = Segment->UCRSegmentList.Flink;
 626     while (Current != &Segment->UCRSegmentList)
 627     {
 628         UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry);
 629
 630         /* Check if we can use that one right away */
 631         if (UcrDescriptor->Size >= *Size &&
 632             (UcrDescriptor->Address == AddressRequested || !AddressRequested))
 633         {
 634             /* Get the address */
 635             Address = (ULONG_PTR)UcrDescriptor->Address;
 636
 637             /* Commit it */
 638             if (Heap->CommitRoutine)
 639             {
 640                 Status = Heap->CommitRoutine(Heap, (PVOID *)&Address, Size);
 641             }
 642             else
 643             {
 644                 Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 645                                                  (PVOID *)&Address,
 646                                                  0,
 647                                                  Size,
 648                                                  MEM_COMMIT,
 649                                                  PAGE_READWRITE);
 650             }
 651
 652             DPRINT("Committed %Iu bytes at base %08Ix, UCR size is %lu\n", *Size, Address, UcrDescriptor->Size);
 653
 654             /* Fail in unsuccessful case */
 655             if (!NT_SUCCESS(Status))
 656             {
 657                 DPRINT1("Committing page failed with status 0x%08X\n", Status);
 658                 return NULL;
 659             }
 660
 661             /* Update tracking numbers */
 662             Segment->NumberOfUnCommittedPages -= (ULONG)(*Size / PAGE_SIZE);
 663
 664             /* Calculate first and last entries */
 665             FirstEntry = (PHEAP_ENTRY)Address;
 666
 667             /* Go through the entries to find the last one */
 668             if (PreviousUcr)
 669                 LastEntry = (PHEAP_ENTRY)((ULONG_PTR)PreviousUcr->Address + PreviousUcr->Size);
 670             else
 671                 LastEntry = &Segment->Entry;
 672
 673             while (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
 674             {
 675                 ASSERT(LastEntry->Size != 0);
 676                 LastEntry += LastEntry->Size;
 677             }
 678             ASSERT((LastEntry + LastEntry->Size) == FirstEntry);
 679
 680             /* Unmark it as a last entry */
 681             LastEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
 682
 683             /* Update UCR descriptor */
 684             UcrDescriptor->Address = (PVOID)((ULONG_PTR)UcrDescriptor->Address + *Size);
 685             UcrDescriptor->Size -= *Size;
 686
 687             DPRINT("Updating UcrDescriptor %p, new Address %p, size %lu\n",
 688                 UcrDescriptor, UcrDescriptor->Address, UcrDescriptor->Size);
 689
 690             /* Set various first entry fields */
 691             FirstEntry->SegmentOffset = LastEntry->SegmentOffset;
 692             FirstEntry->Size = (USHORT)(*Size >> HEAP_ENTRY_SHIFT);
 693             FirstEntry->PreviousSize = LastEntry->Size;
 694
 695             /* Check if anything left in this UCR */
 696             if (UcrDescriptor->Size == 0)
 697             {
 698                 /* It's fully exhausted */
 699
 700                 /* Check if this is the end of the segment */
 701                 if(UcrDescriptor->Address == Segment->LastValidEntry)
 702                 {
 703                     FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
 704                 }
 705                 else
 706                 {
 707                     FirstEntry->Flags = 0;
 708                     /* Update field of next entry */
 709                     ASSERT((FirstEntry + FirstEntry->Size)->PreviousSize == 0);
 710                     (FirstEntry + FirstEntry->Size)->PreviousSize = FirstEntry->Size;
 711                 }
 712
 713                 /* This UCR needs to be removed because it became useless */
 714                 RemoveEntryList(&UcrDescriptor->SegmentEntry);
 715
 716                 RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
 717                 Segment->NumberOfUnCommittedRanges--;
 718             }
 719             else
 720             {
 721                 FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
 722             }
 723
 724             /* We're done */
 725             return (PHEAP_FREE_ENTRY)FirstEntry;
 726         }
 727
 728         /* Advance to the next descriptor */
 729         PreviousUcr = UcrDescriptor;
 730         Current = Current->Flink;
 731     }
 732
 733     return NULL;
 734 }
 735
 736 VOID NTAPI
 737 RtlpDeCommitFreeBlock(PHEAP Heap,
 738                       PHEAP_FREE_ENTRY FreeEntry,
 739                       SIZE_T Size)
 740 {
 741     PHEAP_SEGMENT Segment;
 742     PHEAP_ENTRY PrecedingInUseEntry = NULL, NextInUseEntry = NULL;
 743     PHEAP_FREE_ENTRY NextFreeEntry;
 744     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
 745     SIZE_T PrecedingSize, NextSize, DecommitSize;
 746     ULONG_PTR DecommitBase;
 747     NTSTATUS Status;
 748
 749     DPRINT("Decommitting %p %p %x\n", Heap, FreeEntry, Size);
 750
 751     /* We can't decommit if there is a commit routine! */
 752     if (Heap->CommitRoutine)
 753     {
 754         /* Just add it back the usual way */
 755         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
 756         return;
 757     }
 758
 759     /* Get the segment */
 760     Segment = Heap->Segments[FreeEntry->SegmentOffset];
 761
 762     /* Get the preceding entry */
 763     DecommitBase = ROUND_UP(FreeEntry, PAGE_SIZE);
 764     PrecedingSize = (PHEAP_ENTRY)DecommitBase - (PHEAP_ENTRY)FreeEntry;
 765
 766     if (PrecedingSize == 1)
 767     {
 768         /* Just 1 heap entry, increase the base/size */
 769         DecommitBase += PAGE_SIZE;
 770         PrecedingSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT;
 771     }
 772     else if (FreeEntry->PreviousSize &&
 773              (DecommitBase == (ULONG_PTR)FreeEntry))
 774     {
 775         PrecedingInUseEntry = (PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize;
 776     }
 777
 778     /* Get the next entry */
 779     NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size);
 780     DecommitSize = ROUND_DOWN(NextFreeEntry, PAGE_SIZE);
 781     NextSize = (PHEAP_ENTRY)NextFreeEntry - (PHEAP_ENTRY)DecommitSize;
 782
 783     if (NextSize == 1)
 784     {
 785         /* Just 1 heap entry, increase the size */
 786         DecommitSize -= PAGE_SIZE;
 787         NextSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT;
 788     }
 789     else if (NextSize == 0 &&
 790              !(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
 791     {
 792         NextInUseEntry = (PHEAP_ENTRY)NextFreeEntry;
 793     }
 794
 795     NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry - NextSize);
 796
 797     /* Calculate real decommit size */
 798     if (DecommitSize > DecommitBase)
 799     {
 800         DecommitSize -= DecommitBase;
 801     }
 802     else
 803     {
 804         /* Nothing to decommit */
 805         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
 806         return;
 807     }
 808
 809     /* A decommit is necessary. Create a UCR descriptor */
 810     UcrDescriptor = RtlpCreateUnCommittedRange(Segment);
 811     if (!UcrDescriptor)
 812     {
 813         DPRINT1("HEAP: Failed to create UCR descriptor\n");
 814         RtlpInsertFreeBlock(Heap, FreeEntry, PrecedingSize);
 815         return;
 816     }
 817
 818     /* Decommit the memory */
 819     Status = ZwFreeVirtualMemory(NtCurrentProcess(),
 820                                  (PVOID *)&DecommitBase,
 821                                  &DecommitSize,
 822                                  MEM_DECOMMIT);
 823
 824     /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */
 825     RtlpDestroyUnCommittedRange(Segment, UcrDescriptor);
 826
 827     if (!NT_SUCCESS(Status))
 828     {
 829         RtlpInsertFreeBlock(Heap, FreeEntry, Size);
 830         return;
 831     }
 832
 833     /* Insert uncommitted pages */
 834     RtlpInsertUnCommittedPages(Segment, DecommitBase, DecommitSize);
 835     Segment->NumberOfUnCommittedPages += (ULONG)(DecommitSize / PAGE_SIZE);
 836
 837     if (PrecedingSize)
 838     {
 839         /* Adjust size of this free entry and insert it */
 840         FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
 841         FreeEntry->Size = (USHORT)PrecedingSize;
 842         Heap->TotalFreeSize += PrecedingSize;
 843
 844         /* Insert it into the free list */
 845         RtlpInsertFreeBlockHelper(Heap, FreeEntry, PrecedingSize, FALSE);
 846     }
 847     else if (PrecedingInUseEntry)
 848     {
 849         /* Adjust preceding in use entry */
 850         PrecedingInUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY;
 851     }
 852
 853     /* Now the next one */
 854     if (NextSize)
 855     {
 856         /* Adjust size of this free entry and insert it */
 857         NextFreeEntry->Flags = 0;
 858         NextFreeEntry->PreviousSize = 0;
 859         NextFreeEntry->SegmentOffset = Segment->Entry.SegmentOffset;
 860         NextFreeEntry->Size = (USHORT)NextSize;
 861
 862         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry + NextSize))->PreviousSize = (USHORT)NextSize;
 863
 864         Heap->TotalFreeSize += NextSize;
 865         RtlpInsertFreeBlockHelper(Heap, NextFreeEntry, NextSize, FALSE);
 866     }
 867     else if (NextInUseEntry)
 868     {
 869         NextInUseEntry->PreviousSize = 0;
 870     }
 871 }
 872
 873 NTSTATUS
 874 NTAPI
 875 RtlpInitializeHeapSegment(IN OUT PHEAP Heap,
 876                           OUT PHEAP_SEGMENT Segment,
 877                           IN UCHAR SegmentIndex,
 878                           IN ULONG SegmentFlags,
 879                           IN SIZE_T SegmentReserve,
 880                           IN SIZE_T SegmentCommit)
 881 {
 882     PHEAP_ENTRY HeapEntry;
 883
 884     /* Preconditions */
 885     ASSERT(Heap != NULL);
 886     ASSERT(Segment != NULL);
 887     ASSERT(SegmentCommit >= PAGE_SIZE);
 888     ASSERT(ROUND_DOWN(SegmentCommit, PAGE_SIZE) == SegmentCommit);
 889     ASSERT(SegmentReserve >= SegmentCommit);
 890     ASSERT(ROUND_DOWN(SegmentReserve, PAGE_SIZE) == SegmentReserve);
 891
 892     DPRINT("RtlpInitializeHeapSegment(%p %p %x %x %lx %lx)\n", Heap, Segment, SegmentIndex, SegmentFlags, SegmentReserve, SegmentCommit);
 893
 894     /* Initialise the Heap Entry header if this is not the first Heap Segment */
 895     if ((PHEAP_SEGMENT) (Heap) != Segment)
 896     {
 897         Segment->Entry.Size = ROUND_UP(sizeof(HEAP_SEGMENT), sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT;
 898         Segment->Entry.Flags = HEAP_ENTRY_BUSY;
 899         Segment->Entry.SmallTagIndex = LOBYTE(Segment->Entry.Size) ^ HIBYTE(Segment->Entry.Size) ^ Segment->Entry.Flags;
 900         Segment->Entry.PreviousSize = 0;
 901         Segment->Entry.SegmentOffset = SegmentIndex;
 902         Segment->Entry.UnusedBytes = 0;
 903     }
 904
 905     /* Sanity check */
 906     ASSERT((Segment->Entry.Size << HEAP_ENTRY_SHIFT) <= PAGE_SIZE);
 907
 908     /* Initialise the Heap Segment header */
 909     Segment->SegmentSignature = HEAP_SEGMENT_SIGNATURE;
 910     Segment->SegmentFlags = SegmentFlags;
 911     Segment->Heap = Heap;
 912     Heap->Segments[SegmentIndex] = Segment;
 913
 914     /* Initialise the Heap Segment location information */
 915     Segment->BaseAddress = Segment;
 916     Segment->NumberOfPages = (ULONG)(SegmentReserve >> PAGE_SHIFT);
 917
 918     /* Initialise the Heap Entries contained within the Heap Segment */
 919     Segment->FirstEntry = &Segment->Entry + Segment->Entry.Size;
 920     Segment->LastValidEntry = (PHEAP_ENTRY)((ULONG_PTR)Segment + SegmentReserve);
 921
 922     if (((SIZE_T)Segment->Entry.Size << HEAP_ENTRY_SHIFT) < SegmentCommit)
 923     {
 924         HeapEntry = Segment->FirstEntry;
 925
 926         /* Prepare a Free Heap Entry header */
 927         HeapEntry->Flags = HEAP_ENTRY_LAST_ENTRY;
 928         HeapEntry->PreviousSize = Segment->Entry.Size;
 929         HeapEntry->SegmentOffset = SegmentIndex;
 930
 931         /* Register the Free Heap Entry */
 932         RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY) HeapEntry, (SegmentCommit >> HEAP_ENTRY_SHIFT) - Segment->Entry.Size);
 933     }
 934
 935     /* Initialise the Heap Segment UnCommitted Range information */
 936     Segment->NumberOfUnCommittedPages = (ULONG)((SegmentReserve - SegmentCommit) >> PAGE_SHIFT);
 937     Segment->NumberOfUnCommittedRanges = 0;
 938     InitializeListHead(&Segment->UCRSegmentList);
 939
 940     /* Register the UnCommitted Range of the Heap Segment */
 941     if (Segment->NumberOfUnCommittedPages != 0)
 942         RtlpInsertUnCommittedPages(Segment, (ULONG_PTR) (Segment) + SegmentCommit, SegmentReserve - SegmentCommit);
 943
 944     return STATUS_SUCCESS;
 945 }
 946
 947 VOID NTAPI
 948 RtlpDestroyHeapSegment(PHEAP_SEGMENT Segment)
 949 {
 950     NTSTATUS Status;
 951     PVOID BaseAddress;
 952     SIZE_T Size = 0;
 953
 954     /* Make sure it's not user allocated */
 955     if (Segment->SegmentFlags & HEAP_USER_ALLOCATED) return;
 956
 957     BaseAddress = Segment->BaseAddress;
 958     DPRINT("Destroying segment %p, BA %p\n", Segment, BaseAddress);
 959
 960     /* Release virtual memory */
 961     Status = ZwFreeVirtualMemory(NtCurrentProcess(),
 962                                  &BaseAddress,
 963                                  &Size,
 964                                  MEM_RELEASE);
 965
 966     if (!NT_SUCCESS(Status))
 967     {
 968         DPRINT1("HEAP: Failed to release segment's memory with status 0x%08X\n", Status);
 969     }
 970 }
 971
 972 PHEAP_FREE_ENTRY NTAPI
 973 RtlpCoalesceHeap(PHEAP Heap)
 974 {
 975     UNIMPLEMENTED;
 976     return NULL;
 977 }
 978
 979 PHEAP_FREE_ENTRY NTAPI
 980 RtlpCoalesceFreeBlocks (PHEAP Heap,
 981                         PHEAP_FREE_ENTRY FreeEntry,
 982                         PSIZE_T FreeSize,
 983                         BOOLEAN Remove)
 984 {
 985     PHEAP_FREE_ENTRY CurrentEntry, NextEntry;
 986
 987     /* Get the previous entry */
 988     CurrentEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize);
 989
 990     /* Check it */
 991     if (CurrentEntry != FreeEntry &&
 992         !(CurrentEntry->Flags & HEAP_ENTRY_BUSY) &&
 993         (*FreeSize + CurrentEntry->Size) <= HEAP_MAX_BLOCK_SIZE)
 994     {
 995         ASSERT(FreeEntry->PreviousSize == CurrentEntry->Size);
 996
 997         /* Remove it if asked for */
 998         if (Remove)
 999         {
1000             RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
1001             Heap->TotalFreeSize -= FreeEntry->Size;
1002
1003             /* Remove it only once! */
1004             Remove = FALSE;
1005         }
1006
1007         /* Remove previous entry too */
1008         RtlpRemoveFreeBlock(Heap, CurrentEntry, FALSE, FALSE);
1009
1010         /* Copy flags */
1011         CurrentEntry->Flags = FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY;
1012
1013         /* Advance FreeEntry and update sizes */
1014         FreeEntry = CurrentEntry;
1015         *FreeSize = *FreeSize + CurrentEntry->Size;
1016         Heap->TotalFreeSize -= CurrentEntry->Size;
1017         FreeEntry->Size = (USHORT)(*FreeSize);
1018
1019         /* Also update previous size if needed */
1020         if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
1021         {
1022             ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize);
1023         }
1024     }
1025
1026     /* Check the next block if it exists */
1027     if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
1028     {
1029         NextEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + *FreeSize);
1030
1031         if (!(NextEntry->Flags & HEAP_ENTRY_BUSY) &&
1032             NextEntry->Size + *FreeSize <= HEAP_MAX_BLOCK_SIZE)
1033         {
1034             ASSERT(*FreeSize == NextEntry->PreviousSize);
1035
1036             /* Remove it if asked for */
1037             if (Remove)
1038             {
1039                 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
1040                 Heap->TotalFreeSize -= FreeEntry->Size;
1041             }
1042
1043             /* Copy flags */
1044             FreeEntry->Flags = NextEntry->Flags & HEAP_ENTRY_LAST_ENTRY;
1045
1046             /* Remove next entry now */
1047             RtlpRemoveFreeBlock(Heap, NextEntry, FALSE, FALSE);
1048
1049             /* Update sizes */
1050             *FreeSize = *FreeSize + NextEntry->Size;
1051             Heap->TotalFreeSize -= NextEntry->Size;
1052             FreeEntry->Size = (USHORT)(*FreeSize);
1053
1054             /* Also update previous size if needed */
1055             if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
1056             {
1057                 ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize);
1058             }
1059         }
1060     }
1061     return FreeEntry;
1062 }
1063
1064 PHEAP_FREE_ENTRY NTAPI
1065 RtlpExtendHeap(PHEAP Heap,
1066                SIZE_T Size)
1067 {
1068     ULONG Pages;
1069     UCHAR Index, EmptyIndex;
1070     SIZE_T FreeSize, CommitSize, ReserveSize;
1071     PHEAP_SEGMENT Segment;
1072     PHEAP_FREE_ENTRY FreeEntry;
1073     NTSTATUS Status;
1074
1075     DPRINT("RtlpExtendHeap(%p %x)\n", Heap, Size);
1076
1077     /* Calculate amount in pages */
1078     Pages = (ULONG)((Size + PAGE_SIZE - 1) / PAGE_SIZE);
1079     FreeSize = Pages * PAGE_SIZE;
1080     DPRINT("Pages %x, FreeSize %x. Going through segments...\n", Pages, FreeSize);
1081
1082     /* Find an empty segment */
1083     EmptyIndex = HEAP_SEGMENTS;
1084     for (Index = 0; Index < HEAP_SEGMENTS; Index++)
1085     {
1086         Segment = Heap->Segments[Index];
1087
1088         if (Segment) DPRINT("Segment[%u] %p with NOUCP %x\n", Index, Segment, Segment->NumberOfUnCommittedPages);
1089
1090         /* Check if its size suits us */
1091         if (Segment &&
1092             Pages <= Segment->NumberOfUnCommittedPages)
1093         {
1094             DPRINT("This segment is suitable\n");
1095
1096             /* Commit needed amount */
1097             FreeEntry = RtlpFindAndCommitPages(Heap, Segment, &FreeSize, NULL);
1098
1099             /* Coalesce it with adjacent entries */
1100             if (FreeEntry)
1101             {
1102                 FreeSize = FreeSize >> HEAP_ENTRY_SHIFT;
1103                 FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE);
1104                 RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize);
1105                 return FreeEntry;
1106             }
1107         }
1108         else if (!Segment &&
1109                  EmptyIndex == HEAP_SEGMENTS)
1110         {
1111             /* Remember the first unused segment index */
1112             EmptyIndex = Index;
1113         }
1114     }
1115
1116     /* No luck, need to grow the heap */
1117     if ((Heap->Flags & HEAP_GROWABLE) &&
1118         (EmptyIndex != HEAP_SEGMENTS))
1119     {
1120         Segment = NULL;
1121
1122         /* Reserve the memory */
1123         if ((Size + PAGE_SIZE) <= Heap->SegmentReserve)
1124             ReserveSize = Heap->SegmentReserve;
1125         else
1126             ReserveSize = Size + PAGE_SIZE;
1127
1128         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
1129                                          (PVOID)&Segment,
1130                                          0,
1131                                          &ReserveSize,
1132                                          MEM_RESERVE,
1133                                          PAGE_READWRITE);
1134
1135         /* If it failed, retry again with a half division algorithm */
1136         while (!NT_SUCCESS(Status) &&
1137             ReserveSize != Size + PAGE_SIZE)
1138         {
1139             ReserveSize /= 2;
1140
1141             if (ReserveSize < (Size + PAGE_SIZE))
1142                 ReserveSize = Size + PAGE_SIZE;
1143
1144             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
1145                                              (PVOID)&Segment,
1146                                              0,
1147                                              &ReserveSize,
1148                                              MEM_RESERVE,
1149                                              PAGE_READWRITE);
1150         }
1151
1152         /* Proceed only if it's success */
1153         if (NT_SUCCESS(Status))
1154         {
1155             Heap->SegmentReserve += ReserveSize;
1156
1157             /* Now commit the memory */
1158             if ((Size + PAGE_SIZE) <= Heap->SegmentCommit)
1159                 CommitSize = Heap->SegmentCommit;
1160             else
1161                 CommitSize = Size + PAGE_SIZE;
1162
1163             Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
1164                                              (PVOID)&Segment,
1165                                              0,
1166                                              &CommitSize,
1167                                              MEM_COMMIT,
1168                                              PAGE_READWRITE);
1169
1170             DPRINT("Committed %lu bytes at base %p\n", CommitSize, Segment);
1171
1172             /* Initialize heap segment if commit was successful */
1173             if (NT_SUCCESS(Status))
1174                 Status = RtlpInitializeHeapSegment(Heap, Segment, EmptyIndex, 0, ReserveSize, CommitSize);
1175
1176             /* If everything worked - cool */
1177             if (NT_SUCCESS(Status)) return (PHEAP_FREE_ENTRY)Segment->FirstEntry;
1178
1179             DPRINT1("Committing failed with status 0x%08X\n", Status);
1180
1181             /* Nope, we failed. Free memory */
1182             ZwFreeVirtualMemory(NtCurrentProcess(),
1183                                 (PVOID)&Segment,
1184                                 &ReserveSize,
1185                                 MEM_RELEASE);
1186         }
1187         else
1188         {
1189             DPRINT1("Reserving failed with status 0x%08X\n", Status);
1190         }
1191     }
1192
1193     if (RtlpGetMode() == UserMode)
1194     {
1195         /* If coalescing on free is disabled in usermode, then do it here */
1196         if (Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)
1197         {
1198             FreeEntry = RtlpCoalesceHeap(Heap);
1199
1200             /* If it's a suitable one - return it */
1201             if (FreeEntry &&
1202                 FreeEntry->Size >= Size)
1203             {
1204                 return FreeEntry;
1205             }
1206         }
1207     }
1208
1209     return NULL;
1210 }
1211
1212 /***********************************************************************
1213  *           RtlCreateHeap
1214  * RETURNS
1215  * Handle of heap: Success
1216  * NULL: Failure
1217  *
1218  * @implemented
1219  */
1220 HANDLE NTAPI
1221 RtlCreateHeap(ULONG Flags,
1222               PVOID Addr,
1223               SIZE_T TotalSize,
1224               SIZE_T CommitSize,
1225               PVOID Lock,
1226               PRTL_HEAP_PARAMETERS Parameters)
1227 {
1228     PVOID CommittedAddress = NULL, UncommittedAddress = NULL;
1229     PHEAP Heap = NULL;
1230     RTL_HEAP_PARAMETERS SafeParams = {0};
1231     ULONG_PTR MaximumUserModeAddress;
1232     SYSTEM_BASIC_INFORMATION SystemInformation;
1233     MEMORY_BASIC_INFORMATION MemoryInfo;
1234     ULONG NtGlobalFlags = RtlGetNtGlobalFlags();
1235     ULONG HeapSegmentFlags = 0;
1236     NTSTATUS Status;
1237     ULONG MaxBlockSize;
1238
1239     /* Check for a special heap */
1240     if (RtlpPageHeapEnabled && !Addr && !Lock)
1241     {
1242         Heap = RtlpPageHeapCreate(Flags, Addr, TotalSize, CommitSize, Lock, Parameters);
1243         if (Heap) return Heap;
1244
1245         /* Reset a special Parameters == -1 hack */
1246         if ((ULONG_PTR)Parameters == (ULONG_PTR)-1)
1247             Parameters = NULL;
1248         else
1249             DPRINT1("Enabling page heap failed\n");
1250     }
1251
1252     /* Check validation flags */
1253     if (!(Flags & HEAP_SKIP_VALIDATION_CHECKS) && (Flags & ~HEAP_CREATE_VALID_MASK))
1254     {
1255         DPRINT1("Invalid flags 0x%08x, fixing...\n", Flags);
1256         Flags &= HEAP_CREATE_VALID_MASK;
1257     }
1258
1259     /* TODO: Capture parameters, once we decide to use SEH */
1260     if (!Parameters) Parameters = &SafeParams;
1261
1262     /* Check global flags */
1263     if (NtGlobalFlags & FLG_HEAP_DISABLE_COALESCING)
1264         Flags |= HEAP_DISABLE_COALESCE_ON_FREE;
1265
1266     if (NtGlobalFlags & FLG_HEAP_ENABLE_FREE_CHECK)
1267         Flags |= HEAP_FREE_CHECKING_ENABLED;
1268
1269     if (NtGlobalFlags & FLG_HEAP_ENABLE_TAIL_CHECK)
1270         Flags |= HEAP_TAIL_CHECKING_ENABLED;
1271
1272     if (RtlpGetMode() == UserMode)
1273     {
1274         /* Also check these flags if in usermode */
1275         if (NtGlobalFlags & FLG_HEAP_VALIDATE_ALL)
1276             Flags |= HEAP_VALIDATE_ALL_ENABLED;
1277
1278         if (NtGlobalFlags & FLG_HEAP_VALIDATE_PARAMETERS)
1279             Flags |= HEAP_VALIDATE_PARAMETERS_ENABLED;
1280
1281         if (NtGlobalFlags & FLG_USER_STACK_TRACE_DB)
1282             Flags |= HEAP_CAPTURE_STACK_BACKTRACES;
1283     }
1284
1285     /* Set tunable parameters */
1286     RtlpSetHeapParameters(Parameters);
1287
1288     /* Get the max um address */
1289     Status = ZwQuerySystemInformation(SystemBasicInformation,
1290                                       &SystemInformation,
1291                                       sizeof(SystemInformation),
1292                                       NULL);
1293
1294     if (!NT_SUCCESS(Status))
1295     {
1296         DPRINT1("Getting max usermode address failed with status 0x%08x\n", Status);
1297         return NULL;
1298     }
1299
1300     MaximumUserModeAddress = SystemInformation.MaximumUserModeAddress;
1301
1302     /* Calculate max alloc size */
1303     if (!Parameters->MaximumAllocationSize)
1304         Parameters->MaximumAllocationSize = MaximumUserModeAddress - (ULONG_PTR)0x10000 - PAGE_SIZE;
1305
1306     MaxBlockSize = 0x80000 - PAGE_SIZE;
1307
1308     if (!Parameters->VirtualMemoryThreshold ||
1309         Parameters->VirtualMemoryThreshold > MaxBlockSize)
1310     {
1311         Parameters->VirtualMemoryThreshold = MaxBlockSize;
1312     }
1313
1314     /* Check reserve/commit sizes and set default values */
1315     if (!CommitSize)
1316     {
1317         CommitSize = PAGE_SIZE;
1318         if (TotalSize)
1319             TotalSize = ROUND_UP(TotalSize, PAGE_SIZE);
1320         else
1321             TotalSize = 64 * PAGE_SIZE;
1322     }
1323     else
1324     {
1325         /* Round up the commit size to be at least the page size */
1326         CommitSize = ROUND_UP(CommitSize, PAGE_SIZE);
1327
1328         if (TotalSize)
1329             TotalSize = ROUND_UP(TotalSize, PAGE_SIZE);
1330         else
1331             TotalSize = ROUND_UP(CommitSize, 16 * PAGE_SIZE);
1332     }
1333
1334     /* Call special heap */
1335     if (RtlpHeapIsSpecial(Flags))
1336         return RtlDebugCreateHeap(Flags, Addr, TotalSize, CommitSize, Lock, Parameters);
1337
1338     /* Without serialization, a lock makes no sense */
1339     if ((Flags & HEAP_NO_SERIALIZE) && (Lock != NULL))
1340         return NULL;
1341
1342     /* See if we are already provided with an address for the heap */
1343     if (Addr)
1344     {
1345         if (Parameters->CommitRoutine)
1346         {
1347             /* There is a commit routine, so no problem here, check params */
1348             if ((Flags & HEAP_GROWABLE) ||
1349                 !Parameters->InitialCommit ||
1350                 !Parameters->InitialReserve ||
1351                 (Parameters->InitialCommit > Parameters->InitialReserve))
1352             {
1353                 /* Fail */
1354                 return NULL;
1355             }
1356
1357             /* Calculate committed and uncommitted addresses */
1358             CommittedAddress = Addr;
1359             UncommittedAddress = (PCHAR)Addr + Parameters->InitialCommit;
1360             TotalSize = Parameters->InitialReserve;
1361
1362             /* Zero the initial page ourselves */
1363             RtlZeroMemory(CommittedAddress, PAGE_SIZE);
1364         }
1365         else
1366         {
1367             /* Commit routine is absent, so query how much memory caller reserved */
1368             Status = ZwQueryVirtualMemory(NtCurrentProcess(),
1369                                           Addr,
1370                                           MemoryBasicInformation,
1371                                           &MemoryInfo,
1372                                           sizeof(MemoryInfo),
1373                                           NULL);
1374
1375             if (!NT_SUCCESS(Status))
1376             {
1377                 DPRINT1("Querying amount of user supplied memory failed with status 0x%08X\n", Status);
1378                 return NULL;
1379             }
1380
1381             /* Validate it */
1382             if (MemoryInfo.BaseAddress != Addr ||
1383                 MemoryInfo.State == MEM_FREE)
1384             {
1385                 return NULL;
1386             }
1387
1388             /* Validation checks passed, set committed/uncommitted addresses */
1389             CommittedAddress = Addr;
1390
1391             /* Check if it's committed or not */
1392             if (MemoryInfo.State == MEM_COMMIT)
1393             {
1394                 /* Zero it out because it's already committed */
1395                 RtlZeroMemory(CommittedAddress, PAGE_SIZE);
1396
1397                 /* Calculate uncommitted address value */
1398                 CommitSize = MemoryInfo.RegionSize;
1399                 TotalSize = CommitSize;
1400                 UncommittedAddress = (PCHAR)Addr + CommitSize;
1401
1402                 /* Check if uncommitted address is reserved */
1403                 Status = ZwQueryVirtualMemory(NtCurrentProcess(),
1404                                               UncommittedAddress,
1405                                               MemoryBasicInformation,
1406                                               &MemoryInfo,
1407                                               sizeof(MemoryInfo),
1408                                               NULL);
1409
1410                 if (NT_SUCCESS(Status) &&
1411                     MemoryInfo.State == MEM_RESERVE)
1412                 {
1413                     /* It is, so add it up to the reserve size */
1414                     TotalSize += MemoryInfo.RegionSize;
1415                 }
1416             }
1417             else
1418             {
1419                 /* It's not committed, inform following code that a commit is necessary */
1420                 CommitSize = PAGE_SIZE;
1421                 UncommittedAddress = Addr;
1422             }
1423         }
1424
1425         /* Mark this as a user-committed mem */
1426         HeapSegmentFlags = HEAP_USER_ALLOCATED;
1427         Heap = (PHEAP)Addr;
1428     }
1429     else
1430     {
1431         /* Check commit routine */
1432         if (Parameters->CommitRoutine) return NULL;
1433
1434         /* Reserve memory */
1435         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
1436                                          (PVOID *)&Heap,
1437                                          0,
1438                                          &TotalSize,
1439                                          MEM_RESERVE,
1440                                          PAGE_READWRITE);
1441
1442         if (!NT_SUCCESS(Status))
1443         {
1444             DPRINT1("Failed to reserve memory with status 0x%08x\n", Status);
1445             return NULL;
1446         }
1447
1448         /* Set base addresses */
1449         CommittedAddress = Heap;
1450         UncommittedAddress = Heap;
1451     }
1452
1453     /* Check if we need to commit something */
1454     if (CommittedAddress == UncommittedAddress)
1455     {
1456         /* Commit the required size */
1457         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
1458                                          &CommittedAddress,
1459                                          0,
1460                                          &CommitSize,
1461                                          MEM_COMMIT,
1462                                          PAGE_READWRITE);
1463
1464         DPRINT("Committed %Iu bytes at base %p\n", CommitSize, CommittedAddress);
1465
1466         if (!NT_SUCCESS(Status))
1467         {
1468             DPRINT1("Failure, Status 0x%08X\n", Status);
1469
1470             /* Release memory if it was reserved */
1471             if (!Addr) ZwFreeVirtualMemory(NtCurrentProcess(),
1472                                            (PVOID *)&Heap,
1473                                            &TotalSize,
1474                                            MEM_RELEASE);
1475
1476             return NULL;
1477         }
1478
1479         /* Calculate new uncommitted address */
1480         UncommittedAddress = (PCHAR)UncommittedAddress + CommitSize;
1481     }
1482
1483     /* Initialize the heap */
1484     Status = RtlpInitializeHeap(Heap, Flags, Lock, Parameters);
1485     if (!NT_SUCCESS(Status))
1486     {
1487         DPRINT1("Failed to initialize heap (%x)\n", Status);
1488         return NULL;
1489     }
1490
1491     /* Initialize heap's first segment */
1492     Status = RtlpInitializeHeapSegment(Heap, (PHEAP_SEGMENT) (Heap), 0, HeapSegmentFlags, TotalSize, CommitSize);
1493     if (!NT_SUCCESS(Status))
1494     {
1495         DPRINT1("Failed to initialize heap segment (%x)\n", Status);
1496         return NULL;
1497     }
1498
1499     DPRINT("Created heap %p, CommitSize %x, ReserveSize %x\n", Heap, CommitSize, TotalSize);
1500
1501     /* Add heap to process list in case of usermode heap */
1502     if (RtlpGetMode() == UserMode)
1503     {
1504         RtlpAddHeapToProcessList(Heap);
1505
1506         // FIXME: What about lookasides?
1507     }
1508
1509     return Heap;
1510 }
1511
1512 /***********************************************************************
1513  *           RtlDestroyHeap
1514  * RETURNS
1515  * TRUE: Success
1516  * FALSE: Failure
1517  *
1518  * @implemented
1519  *
1520  * RETURNS
1521  *  Success: A NULL HANDLE, if heap is NULL or it was destroyed
1522  *  Failure: The Heap handle, if heap is the process heap.
1523  */
1524 HANDLE NTAPI
1525 RtlDestroyHeap(HANDLE HeapPtr) /* [in] Handle of heap */
1526 {
1527     PHEAP Heap = (PHEAP)HeapPtr;
1528     PLIST_ENTRY Current;
1529     PHEAP_UCR_SEGMENT UcrSegment;
1530     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
1531     PVOID BaseAddress;
1532     SIZE_T Size;
1533     LONG i;
1534     PHEAP_SEGMENT Segment;
1535
1536     if (!HeapPtr) return NULL;
1537
1538     /* Call page heap routine if required */
1539     if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) return RtlpPageHeapDestroy(HeapPtr);
1540
1541     /* Call special heap */
1542     if (RtlpHeapIsSpecial(Heap->Flags))
1543     {
1544         if (!RtlDebugDestroyHeap(Heap)) return HeapPtr;
1545     }
1546
1547     /* Check for a process heap */
1548     if (RtlpGetMode() == UserMode &&
1549         HeapPtr == NtCurrentPeb()->ProcessHeap) return HeapPtr;
1550
1551     /* Free up all big allocations */
1552     Current = Heap->VirtualAllocdBlocks.Flink;
1553     while (Current != &Heap->VirtualAllocdBlocks)
1554     {
1555         VirtualEntry = CONTAINING_RECORD(Current, HEAP_VIRTUAL_ALLOC_ENTRY, Entry);
1556         BaseAddress = (PVOID)VirtualEntry;
1557         Current = Current->Flink;
1558         Size = 0;
1559         ZwFreeVirtualMemory(NtCurrentProcess(),
1560                             &BaseAddress,
1561                             &Size,
1562                             MEM_RELEASE);
1563     }
1564
1565     /* Delete tags and remove heap from the process heaps list in user mode */
1566     if (RtlpGetMode() == UserMode)
1567     {
1568         // FIXME DestroyTags
1569         RtlpRemoveHeapFromProcessList(Heap);
1570     }
1571
1572     /* Delete the heap lock */
1573     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
1574     {
1575         /* Delete it if it wasn't user allocated */
1576         if (!(Heap->Flags & HEAP_LOCK_USER_ALLOCATED))
1577             RtlDeleteHeapLock(Heap->LockVariable);
1578
1579         /* Clear out the lock variable */
1580         Heap->LockVariable = NULL;
1581     }
1582
1583     /* Free UCR segments if any were created */
1584     Current = Heap->UCRSegments.Flink;
1585     while (Current != &Heap->UCRSegments)
1586     {
1587         UcrSegment = CONTAINING_RECORD(Current, HEAP_UCR_SEGMENT, ListEntry);
1588
1589         /* Advance to the next descriptor */
1590         Current = Current->Flink;
1591
1592         BaseAddress = (PVOID)UcrSegment;
1593         Size = 0;
1594
1595         /* Release that memory */
1596         ZwFreeVirtualMemory(NtCurrentProcess(),
1597                             &BaseAddress,
1598                             &Size,
1599                             MEM_RELEASE);
1600     }
1601
1602     /* Go through segments and destroy them */
1603     for (i = HEAP_SEGMENTS - 1; i >= 0; i--)
1604     {
1605         Segment = Heap->Segments[i];
1606         if (Segment) RtlpDestroyHeapSegment(Segment);
1607     }
1608
1609     return NULL;
1610 }
1611
1612 PHEAP_ENTRY NTAPI
1613 RtlpSplitEntry(PHEAP Heap,
1614                ULONG Flags,
1615                PHEAP_FREE_ENTRY FreeBlock,
1616                SIZE_T AllocationSize,
1617                SIZE_T Index,
1618                SIZE_T Size)
1619 {
1620     PHEAP_FREE_ENTRY SplitBlock, SplitBlock2;
1621     UCHAR FreeFlags, EntryFlags = HEAP_ENTRY_BUSY;
1622     PHEAP_ENTRY InUseEntry;
1623     SIZE_T FreeSize;
1624
1625     /* Add extra flags in case of settable user value feature is requested,
1626        or there is a tag (small or normal) or there is a request to
1627        capture stack backtraces */
1628     if ((Flags & HEAP_EXTRA_FLAGS_MASK) ||
1629         Heap->PseudoTagEntries)
1630     {
1631         /* Add flag which means that the entry will have extra stuff attached */
1632         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
1633
1634         /* NB! AllocationSize is already adjusted by RtlAllocateHeap */
1635     }
1636
1637     /* Add settable user flags, if any */
1638     EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4;
1639
1640     /* Save flags, update total free size */
1641     FreeFlags = FreeBlock->Flags;
1642     Heap->TotalFreeSize -= FreeBlock->Size;
1643
1644     /* Make this block an in-use one */
1645     InUseEntry = (PHEAP_ENTRY)FreeBlock;
1646     InUseEntry->Flags = EntryFlags;
1647     InUseEntry->SmallTagIndex = 0;
1648
1649     /* Calculate the extra amount */
1650     FreeSize = InUseEntry->Size - Index;
1651
1652     /* Update it's size fields (we don't need their data anymore) */
1653     InUseEntry->Size = (USHORT)Index;
1654     InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
1655
1656     /* If there is something to split - do the split */
1657     if (FreeSize != 0)
1658     {
1659         /* Don't split if resulting entry can't contain any payload data
1660         (i.e. being just HEAP_ENTRY_SIZE) */
1661         if (FreeSize == 1)
1662         {
1663             /* Increase sizes of the in-use entry */
1664             InUseEntry->Size++;
1665             InUseEntry->UnusedBytes += sizeof(HEAP_ENTRY);
1666         }
1667         else
1668         {
1669             /* Calculate a pointer to the new entry */
1670             SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
1671
1672             /* Initialize it */
1673             SplitBlock->Flags = FreeFlags;
1674             SplitBlock->SegmentOffset = InUseEntry->SegmentOffset;
1675             SplitBlock->Size = (USHORT)FreeSize;
1676             SplitBlock->PreviousSize = (USHORT)Index;
1677
1678             /* Check if it's the last entry */
1679             if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
1680             {
1681                 /* Insert it to the free list if it's the last entry */
1682                 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
1683                 Heap->TotalFreeSize += FreeSize;
1684             }
1685             else
1686             {
1687                 /* Not so easy - need to update next's previous size too */
1688                 SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
1689
1690                 if (SplitBlock2->Flags & HEAP_ENTRY_BUSY)
1691                 {
1692                     SplitBlock2->PreviousSize = (USHORT)FreeSize;
1693                     RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
1694                     Heap->TotalFreeSize += FreeSize;
1695                 }
1696                 else
1697                 {
1698                     /* Even more complex - the next entry is free, so we can merge them into one! */
1699                     SplitBlock->Flags = SplitBlock2->Flags;
1700
1701                     /* Remove that next entry */
1702                     RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE, FALSE);
1703
1704                     /* Update sizes */
1705                     FreeSize += SplitBlock2->Size;
1706                     Heap->TotalFreeSize -= SplitBlock2->Size;
1707
1708                     if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
1709                     {
1710                         /* Insert it back */
1711                         SplitBlock->Size = (USHORT)FreeSize;
1712
1713                         /* Don't forget to update previous size of the next entry! */
1714                         if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY))
1715                         {
1716                             ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
1717                         }
1718
1719                         /* Actually insert it */
1720                         RtlpInsertFreeBlockHelper(Heap, SplitBlock, (USHORT)FreeSize, FALSE);
1721
1722                         /* Update total size */
1723                         Heap->TotalFreeSize += FreeSize;
1724                     }
1725                     else
1726                     {
1727                         /* Resulting block is quite big */
1728                         RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize);
1729                     }
1730                 }
1731             }
1732
1733             /* Reset flags of the free entry */
1734             FreeFlags = 0;
1735         }
1736     }
1737
1738     /* Set last entry flag */
1739     if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
1740         InUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY;
1741
1742     return InUseEntry;
1743 }
1744
1745 PVOID NTAPI
1746 RtlpAllocateNonDedicated(PHEAP Heap,
1747                          ULONG Flags,
1748                          SIZE_T Size,
1749                          SIZE_T AllocationSize,
1750                          SIZE_T Index,
1751                          BOOLEAN HeapLocked)
1752 {
1753     PLIST_ENTRY FreeListHead, Next;
1754     PHEAP_FREE_ENTRY FreeBlock;
1755     PHEAP_ENTRY InUseEntry;
1756     PHEAP_ENTRY_EXTRA Extra;
1757     EXCEPTION_RECORD ExceptionRecord;
1758
1759     /* Go through the zero list to find a place where to insert the new entry */
1760     FreeListHead = &Heap->FreeLists[0];
1761
1762     /* Start from the largest block to reduce time */
1763     Next = FreeListHead->Blink;
1764     if (FreeListHead != Next)
1765     {
1766         FreeBlock = CONTAINING_RECORD(Next, HEAP_FREE_ENTRY, FreeList);
1767
1768         if (FreeBlock->Size >= Index)
1769         {
1770             /* Our request is smaller than the largest entry in the zero list */
1771
1772             /* Go through the list to find insertion place */
1773             Next = FreeListHead->Flink;
1774             while (FreeListHead != Next)
1775             {
1776                 FreeBlock = CONTAINING_RECORD(Next, HEAP_FREE_ENTRY, FreeList);
1777
1778                 if (FreeBlock->Size >= Index)
1779                 {
1780                     /* Found minimally fitting entry. Proceed to either using it as it is
1781                     or splitting it to two entries */
1782                     RemoveEntryList(&FreeBlock->FreeList);
1783
1784                     /* Split it */
1785                     InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
1786
1787                     /* Release the lock */
1788                     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
1789
1790                     /* Zero memory if that was requested */
1791                     if (Flags & HEAP_ZERO_MEMORY)
1792                         RtlZeroMemory(InUseEntry + 1, Size);
1793                     else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
1794                     {
1795                         /* Fill this block with a special pattern */
1796                         RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
1797                     }
1798
1799                     /* Fill tail of the block with a special pattern too if requested */
1800                     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
1801                     {
1802                         RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
1803                         InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
1804                     }
1805
1806                     /* Prepare extra if it's present */
1807                     if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
1808                     {
1809                         Extra = RtlpGetExtraStuffPointer(InUseEntry);
1810                         RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
1811
1812                         // TODO: Tagging
1813                     }
1814
1815                     /* Return pointer to the */
1816                     return InUseEntry + 1;
1817                 }
1818
1819                 /* Advance to the next entry */
1820                 Next = Next->Flink;
1821             }
1822         }
1823     }
1824
1825     /* Extend the heap, 0 list didn't have anything suitable */
1826     FreeBlock = RtlpExtendHeap(Heap, AllocationSize);
1827
1828     /* Use the new biggest entry we've got */
1829     if (FreeBlock)
1830     {
1831         RemoveEntryList(&FreeBlock->FreeList);
1832
1833         /* Split it */
1834         InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
1835
1836         /* Release the lock */
1837         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
1838
1839         /* Zero memory if that was requested */
1840         if (Flags & HEAP_ZERO_MEMORY)
1841             RtlZeroMemory(InUseEntry + 1, Size);
1842         else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
1843         {
1844             /* Fill this block with a special pattern */
1845             RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
1846         }
1847
1848         /* Fill tail of the block with a special pattern too if requested */
1849         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
1850         {
1851             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
1852             InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
1853         }
1854
1855         /* Prepare extra if it's present */
1856         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
1857         {
1858             Extra = RtlpGetExtraStuffPointer(InUseEntry);
1859             RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
1860
1861             // TODO: Tagging
1862         }
1863
1864         /* Return pointer to the */
1865         return InUseEntry + 1;
1866     }
1867
1868     /* Really unfortunate, out of memory condition */
1869     RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
1870
1871     /* Generate an exception */
1872     if (Flags & HEAP_GENERATE_EXCEPTIONS)
1873     {
1874         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
1875         ExceptionRecord.ExceptionRecord = NULL;
1876         ExceptionRecord.NumberParameters = 1;
1877         ExceptionRecord.ExceptionFlags = 0;
1878         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
1879
1880         RtlRaiseException(&ExceptionRecord);
1881     }
1882
1883     /* Release the lock */
1884     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
1885     DPRINT1("HEAP: Allocation failed!\n");
1886     DPRINT1("Flags %x\n", Heap->Flags);
1887     return NULL;
1888 }
1889
1890 /***********************************************************************
1891  *           HeapAlloc   (KERNEL32.334)
1892  * RETURNS
1893  * Pointer to allocated memory block
1894  * NULL: Failure
1895  * 0x7d030f60--invalid flags in RtlHeapAllocate
1896  * @implemented
1897  */
1898 PVOID NTAPI
1899 RtlAllocateHeap(IN PVOID HeapPtr,
1900                 IN ULONG Flags,
1901                 IN SIZE_T Size)
1902 {
1903     PHEAP Heap = (PHEAP)HeapPtr;
1904     PULONG FreeListsInUse;
1905     ULONG FreeListsInUseUlong;
1906     SIZE_T AllocationSize;
1907     SIZE_T Index, InUseIndex, i;
1908     PLIST_ENTRY FreeListHead;
1909     PHEAP_ENTRY InUseEntry;
1910     PHEAP_FREE_ENTRY FreeBlock;
1911     UCHAR FreeFlags, EntryFlags = HEAP_ENTRY_BUSY;
1912     EXCEPTION_RECORD ExceptionRecord;
1913     BOOLEAN HeapLocked = FALSE;
1914     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualBlock = NULL;
1915     PHEAP_ENTRY_EXTRA Extra;
1916     NTSTATUS Status;
1917
1918     /* Force flags */
1919     Flags |= Heap->ForceFlags;
1920
1921     /* Call special heap */
1922     if (RtlpHeapIsSpecial(Flags))
1923         return RtlDebugAllocateHeap(Heap, Flags, Size);
1924
1925     /* Check for the maximum size */
1926     if (Size >= 0x80000000)
1927     {
1928         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
1929         DPRINT1("HEAP: Allocation failed!\n");
1930         return NULL;
1931     }
1932
1933     if (Flags & (HEAP_CREATE_ENABLE_TRACING))
1934     {
1935         DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags);
1936     }
1937
1938     //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size);
1939
1940     /* Calculate allocation size and index */
1941     if (Size)
1942         AllocationSize = Size;
1943     else
1944         AllocationSize = 1;
1945     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
1946
1947     /* Add extra flags in case of settable user value feature is requested,
1948        or there is a tag (small or normal) or there is a request to
1949        capture stack backtraces */
1950     if ((Flags & HEAP_EXTRA_FLAGS_MASK) ||
1951         Heap->PseudoTagEntries)
1952     {
1953         /* Add flag which means that the entry will have extra stuff attached */
1954         EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT;
1955
1956         /* Account for extra stuff size */
1957         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
1958     }
1959
1960     /* Add settable user flags, if any */
1961     EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4;
1962
1963     Index = AllocationSize >>  HEAP_ENTRY_SHIFT;
1964
1965     /* Acquire the lock if necessary */
1966     if (!(Flags & HEAP_NO_SERIALIZE))
1967     {
1968         RtlEnterHeapLock(Heap->LockVariable, TRUE);
1969         HeapLocked = TRUE;
1970     }
1971
1972     /* Depending on the size, the allocation is going to be done from dedicated,
1973        non-dedicated lists or a virtual block of memory */
1974     if (Index < HEAP_FREELISTS)
1975     {
1976         FreeListHead = &Heap->FreeLists[Index];
1977
1978         if (!IsListEmpty(FreeListHead))
1979         {
1980             /* There is a free entry in this list */
1981             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
1982                                           HEAP_FREE_ENTRY,
1983                                           FreeList);
1984
1985             /* Save flags and remove the free entry */
1986             FreeFlags = FreeBlock->Flags;
1987             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
1988
1989             /* Update the total free size of the heap */
1990             Heap->TotalFreeSize -= Index;
1991
1992             /* Initialize this block */
1993             InUseEntry = (PHEAP_ENTRY)FreeBlock;
1994             InUseEntry->Flags = EntryFlags | (FreeFlags & HEAP_ENTRY_LAST_ENTRY);
1995             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
1996             InUseEntry->SmallTagIndex = 0;
1997         }
1998         else
1999         {
2000             /* Find smallest free block which this request could fit in */
2001             InUseIndex = Index >> 5;
2002             FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex];
2003
2004             /* This bit magic disables all sizes which are less than the requested allocation size */
2005             FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << ((ULONG)Index & 0x1f)) - 1);
2006
2007             /* If size is definitily more than our lists - go directly to the non-dedicated one */
2008             if (InUseIndex > 3)
2009                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
2010
2011             /* Go through the list */
2012             for (i = InUseIndex; i < 4; i++)
2013             {
2014                 if (FreeListsInUseUlong)
2015                 {
2016                     FreeListHead = &Heap->FreeLists[i * 32];
2017                     break;
2018                 }
2019
2020                 if (i < 3) FreeListsInUseUlong = *FreeListsInUse++;
2021             }
2022
2023             /* Nothing found, search in the non-dedicated list */
2024             if (i == 4)
2025                 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
2026
2027             /* That list is found, now calculate exact block  */
2028             FreeListHead += RtlpFindLeastSetBit(FreeListsInUseUlong);
2029
2030             /* Take this entry and remove it from the list of free blocks */
2031             FreeBlock = CONTAINING_RECORD(FreeListHead->Blink,
2032                                           HEAP_FREE_ENTRY,
2033                                           FreeList);
2034             RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE, FALSE);
2035
2036             /* Split it */
2037             InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size);
2038         }
2039
2040         /* Release the lock */
2041         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
2042
2043         /* Zero memory if that was requested */
2044         if (Flags & HEAP_ZERO_MEMORY)
2045             RtlZeroMemory(InUseEntry + 1, Size);
2046         else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
2047         {
2048             /* Fill this block with a special pattern */
2049             RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER);
2050         }
2051
2052         /* Fill tail of the block with a special pattern too if requested */
2053         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
2054         {
2055             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL);
2056             InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN;
2057         }
2058
2059         /* Prepare extra if it's present */
2060         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
2061         {
2062             Extra = RtlpGetExtraStuffPointer(InUseEntry);
2063             RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA));
2064
2065             // TODO: Tagging
2066         }
2067
2068         /* User data starts right after the entry's header */
2069         return InUseEntry + 1;
2070     }
2071     else if (Index <= Heap->VirtualMemoryThreshold)
2072     {
2073         /* The block is too large for dedicated lists, but fine for a non-dedicated one */
2074         return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked);
2075     }
2076     else if (Heap->Flags & HEAP_GROWABLE)
2077     {
2078         /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */
2079         AllocationSize += sizeof(HEAP_VIRTUAL_ALLOC_ENTRY) - sizeof(HEAP_ENTRY);
2080
2081         Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
2082                                          (PVOID *)&VirtualBlock,
2083                                          0,
2084                                          &AllocationSize,
2085                                          MEM_COMMIT,
2086                                          PAGE_READWRITE);
2087
2088         if (!NT_SUCCESS(Status))
2089         {
2090             // Set STATUS!
2091             /* Release the lock */
2092             if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
2093             DPRINT1("HEAP: Allocation failed!\n");
2094             return NULL;
2095         }
2096
2097         /* Initialize the newly allocated block */
2098         VirtualBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size);
2099         ASSERT(VirtualBlock->BusyBlock.Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY));
2100         VirtualBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT;
2101         VirtualBlock->CommitSize = AllocationSize;
2102         VirtualBlock->ReserveSize = AllocationSize;
2103
2104         /* Insert it into the list of virtual allocations */
2105         InsertTailList(&Heap->VirtualAllocdBlocks, &VirtualBlock->Entry);
2106
2107         /* Release the lock */
2108         if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
2109
2110         /* Return pointer to user data */
2111         return VirtualBlock + 1;
2112     }
2113
2114     /* Generate an exception */
2115     if (Flags & HEAP_GENERATE_EXCEPTIONS)
2116     {
2117         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
2118         ExceptionRecord.ExceptionRecord = NULL;
2119         ExceptionRecord.NumberParameters = 1;
2120         ExceptionRecord.ExceptionFlags = 0;
2121         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
2122
2123         RtlRaiseException(&ExceptionRecord);
2124     }
2125
2126     RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL);
2127
2128     /* Release the lock */
2129     if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable);
2130     DPRINT1("HEAP: Allocation failed!\n");
2131     return NULL;
2132 }
2133
2134
2135 /***********************************************************************
2136  *           HeapFree   (KERNEL32.338)
2137  * RETURNS
2138  * TRUE: Success
2139  * FALSE: Failure
2140  *
2141  * @implemented
2142  */
2143 BOOLEAN NTAPI RtlFreeHeap(
2144    HANDLE HeapPtr, /* [in] Handle of heap */
2145    ULONG Flags,   /* [in] Heap freeing flags */
2146    PVOID Ptr     /* [in] Address of memory to free */
2147 )
2148 {
2149     PHEAP Heap;
2150     PHEAP_ENTRY HeapEntry;
2151     USHORT TagIndex = 0;
2152     SIZE_T BlockSize;
2153     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
2154     BOOLEAN Locked = FALSE;
2155     NTSTATUS Status;
2156
2157     /* Freeing NULL pointer is a legal operation */
2158     if (!Ptr) return TRUE;
2159
2160     /* Get pointer to the heap and force flags */
2161     Heap = (PHEAP)HeapPtr;
2162     Flags |= Heap->ForceFlags;
2163
2164     /* Call special heap */
2165     if (RtlpHeapIsSpecial(Flags))
2166         return RtlDebugFreeHeap(Heap, Flags, Ptr);
2167
2168     /* Lock if necessary */
2169     if (!(Flags & HEAP_NO_SERIALIZE))
2170     {
2171         RtlEnterHeapLock(Heap->LockVariable, TRUE);
2172         Locked = TRUE;
2173     }
2174
2175     /* Get pointer to the heap entry */
2176     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
2177
2178     /* Check this entry, fail if it's invalid */
2179     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY) ||
2180         (((ULONG_PTR)Ptr & 0x7) != 0) ||
2181         (HeapEntry->SegmentOffset >= HEAP_SEGMENTS))
2182     {
2183         /* This is an invalid block */
2184         DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr);
2185         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
2186
2187         /* Release the heap lock */
2188         if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
2189         return FALSE;
2190     }
2191
2192     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
2193     {
2194         /* Big allocation */
2195         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
2196
2197         /* Remove it from the list */
2198         RemoveEntryList(&VirtualEntry->Entry);
2199
2200         // TODO: Tagging
2201
2202         BlockSize = 0;
2203         Status = ZwFreeVirtualMemory(NtCurrentProcess(),
2204                                      (PVOID *)&VirtualEntry,
2205                                      &BlockSize,
2206                                      MEM_RELEASE);
2207
2208         if (!NT_SUCCESS(Status))
2209         {
2210             DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n",
2211                 Status, Heap, Ptr, VirtualEntry);
2212             RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status);
2213         }
2214     }
2215     else
2216     {
2217         /* Normal allocation */
2218         BlockSize = HeapEntry->Size;
2219
2220         // TODO: Tagging
2221
2222         /* Coalesce in kernel mode, and in usermode if it's not disabled */
2223         if (RtlpGetMode() == KernelMode ||
2224             (RtlpGetMode() == UserMode && !(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE)))
2225         {
2226             HeapEntry = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks(Heap,
2227                                                            (PHEAP_FREE_ENTRY)HeapEntry,
2228                                                            &BlockSize,
2229                                                            FALSE);
2230         }
2231
2232         /* If there is no need to decommit the block - put it into a free list */
2233         if (BlockSize < Heap->DeCommitFreeBlockThreshold ||
2234             (Heap->TotalFreeSize + BlockSize < Heap->DeCommitTotalFreeThreshold))
2235         {
2236             /* Check if it needs to go to a 0 list */
2237             if (BlockSize > HEAP_MAX_BLOCK_SIZE)
2238             {
2239                 /* General-purpose 0 list */
2240                 RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
2241             }
2242             else
2243             {
2244                 /* Usual free list */
2245                 RtlpInsertFreeBlockHelper(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize, FALSE);
2246
2247                 /* Assert sizes are consistent */
2248                 if (!(HeapEntry->Flags & HEAP_ENTRY_LAST_ENTRY))
2249                 {
2250                     ASSERT((HeapEntry + BlockSize)->PreviousSize == BlockSize);
2251                 }
2252
2253                 /* Increase the free size */
2254                 Heap->TotalFreeSize += BlockSize;
2255             }
2256
2257
2258             if (RtlpGetMode() == UserMode &&
2259                 TagIndex != 0)
2260             {
2261                 // FIXME: Tagging
2262                 UNIMPLEMENTED;
2263             }
2264         }
2265         else
2266         {
2267             /* Decommit this block */
2268             RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize);
2269         }
2270     }
2271
2272     /* Release the heap lock */
2273     if (Locked) RtlLeaveHeapLock(Heap->LockVariable);
2274
2275     return TRUE;
2276 }
2277
2278 BOOLEAN NTAPI
2279 RtlpGrowBlockInPlace (IN PHEAP Heap,
2280                       IN ULONG Flags,
2281                       IN PHEAP_ENTRY InUseEntry,
2282                       IN SIZE_T Size,
2283                       IN SIZE_T Index)
2284 {
2285     UCHAR EntryFlags, RememberFlags;
2286     PHEAP_FREE_ENTRY FreeEntry, UnusedEntry, FollowingEntry;
2287     SIZE_T FreeSize, PrevSize, TailPart, AddedSize = 0;
2288     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
2289
2290     /* We can't grow beyond specified threshold */
2291     if (Index > Heap->VirtualMemoryThreshold)
2292         return FALSE;
2293
2294     /* Get entry flags */
2295     EntryFlags = InUseEntry->Flags;
2296
2297     /* Get the next free entry */
2298     FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size);
2299
2300     if (EntryFlags & HEAP_ENTRY_LAST_ENTRY)
2301     {
2302         /* There is no next block, just uncommitted space. Calculate how much is needed */
2303         FreeSize = (Index - InUseEntry->Size) << HEAP_ENTRY_SHIFT;
2304         FreeSize = ROUND_UP(FreeSize, PAGE_SIZE);
2305
2306         /* Find and commit those pages */
2307         FreeEntry = RtlpFindAndCommitPages(Heap,
2308                                            Heap->Segments[InUseEntry->SegmentOffset],
2309                                            &FreeSize,
2310                                            FreeEntry);
2311
2312         /* Fail if it failed... */
2313         if (!FreeEntry) return FALSE;
2314
2315         /* It was successful, perform coalescing */
2316         FreeSize = FreeSize >> HEAP_ENTRY_SHIFT;
2317         FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE);
2318
2319         /* Check if it's enough */
2320         if (FreeSize + InUseEntry->Size < Index)
2321         {
2322             /* Still not enough */
2323             RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize);
2324             Heap->TotalFreeSize += FreeSize;
2325             return FALSE;
2326         }
2327
2328         /* Remember flags of this free entry */
2329         RememberFlags = FreeEntry->Flags;
2330
2331         /* Sum up sizes */
2332         FreeSize += InUseEntry->Size;
2333     }
2334     else
2335     {
2336         /* The next block indeed exists. Check if it's free or in use */
2337         if (FreeEntry->Flags & HEAP_ENTRY_BUSY) return FALSE;
2338
2339         /* Next entry is free, check if it can fit the block we need */
2340         FreeSize = InUseEntry->Size + FreeEntry->Size;
2341         if (FreeSize < Index) return FALSE;
2342
2343         /* Remember flags of this free entry */
2344         RememberFlags = FreeEntry->Flags;
2345
2346         /* Remove this block from the free list */
2347         RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE, FALSE);
2348         Heap->TotalFreeSize -= FreeEntry->Size;
2349     }
2350
2351     PrevSize = (InUseEntry->Size << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
2352     FreeSize -= Index;
2353
2354     /* Don't produce too small blocks */
2355     if (FreeSize <= 2)
2356     {
2357         Index += FreeSize;
2358         FreeSize = 0;
2359     }
2360
2361     /* Process extra stuff */
2362     if (RememberFlags & HEAP_ENTRY_EXTRA_PRESENT)
2363     {
2364         /* Calculate pointers */
2365         OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
2366         NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
2367
2368         /* Copy contents */
2369         *NewExtra = *OldExtra;
2370
2371         // FIXME Tagging
2372     }
2373
2374     /* Update sizes */
2375     InUseEntry->Size = (USHORT)Index;
2376     InUseEntry->UnusedBytes = (UCHAR)((Index << HEAP_ENTRY_SHIFT) - Size);
2377
2378     /* Check if there is a free space remaining after merging those blocks */
2379     if (!FreeSize)
2380     {
2381         /* Update flags and sizes */
2382         InUseEntry->Flags |= RememberFlags & HEAP_ENTRY_LAST_ENTRY;
2383
2384         /* Either update previous size of the next entry or mark it as a last
2385            entry in the segment*/
2386         if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
2387             (InUseEntry + InUseEntry->Size)->PreviousSize = InUseEntry->Size;
2388     }
2389     else
2390     {
2391         /* Complex case, we need to split the block to give unused free space
2392            back to the heap */
2393         UnusedEntry = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
2394         UnusedEntry->PreviousSize = (USHORT)Index;
2395         UnusedEntry->SegmentOffset = InUseEntry->SegmentOffset;
2396
2397         /* Update the following block or set the last entry in the segment */
2398         if (RememberFlags & HEAP_ENTRY_LAST_ENTRY)
2399         {
2400             /* Set flags and size */
2401             UnusedEntry->Flags = RememberFlags;
2402             UnusedEntry->Size = (USHORT)FreeSize;
2403
2404             /* Insert it to the heap and update total size  */
2405             RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
2406             Heap->TotalFreeSize += FreeSize;
2407         }
2408         else
2409         {
2410             /* There is a block after this one  */
2411             FollowingEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)UnusedEntry + FreeSize);
2412
2413             if (FollowingEntry->Flags & HEAP_ENTRY_BUSY)
2414             {
2415                 /* Update flags and set size of the unused space entry */
2416                 UnusedEntry->Flags = RememberFlags & (~HEAP_ENTRY_LAST_ENTRY);
2417                 UnusedEntry->Size = (USHORT)FreeSize;
2418
2419                 /* Update previous size of the following entry */
2420                 FollowingEntry->PreviousSize = (USHORT)FreeSize;
2421
2422                 /* Insert it to the heap and update total free size */
2423                 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
2424                 Heap->TotalFreeSize += FreeSize;
2425             }
2426             else
2427             {
2428                 /* That following entry is also free, what a fortune! */
2429                 RememberFlags = FollowingEntry->Flags;
2430
2431                 /* Remove it */
2432                 RtlpRemoveFreeBlock(Heap, FollowingEntry, FALSE, FALSE);
2433                 Heap->TotalFreeSize -= FollowingEntry->Size;
2434
2435                 /* And make up a new combined block */
2436                 FreeSize += FollowingEntry->Size;
2437                 UnusedEntry->Flags = RememberFlags;
2438
2439                 /* Check where to put it */
2440                 if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
2441                 {
2442                     /* Fine for a dedicated list */
2443                     UnusedEntry->Size = (USHORT)FreeSize;
2444
2445                     if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY))
2446                         ((PHEAP_ENTRY)UnusedEntry + FreeSize)->PreviousSize = (USHORT)FreeSize;
2447
2448                     /* Insert it back and update total size */
2449                     RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE);
2450                     Heap->TotalFreeSize += FreeSize;
2451                 }
2452                 else
2453                 {
2454                     /* The block is very large, leave all the hassle to the insertion routine */
2455                     RtlpInsertFreeBlock(Heap, UnusedEntry, FreeSize);
2456                 }
2457             }
2458         }
2459     }
2460
2461     /* Properly "zero out" (and fill!) the space */
2462     if (Flags & HEAP_ZERO_MEMORY)
2463     {
2464         RtlZeroMemory((PCHAR)(InUseEntry + 1) + PrevSize, Size - PrevSize);
2465     }
2466     else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
2467     {
2468         /* Calculate tail part which we need to fill */
2469         TailPart = PrevSize & (sizeof(ULONG) - 1);
2470
2471         /* "Invert" it as usual */
2472         if (TailPart) TailPart = 4 - TailPart;
2473
2474         if (Size > (PrevSize + TailPart))
2475             AddedSize = (Size - (PrevSize + TailPart)) & ~(sizeof(ULONG) - 1);
2476
2477         if (AddedSize)
2478         {
2479             RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + PrevSize + TailPart,
2480                                AddedSize,
2481                                ARENA_INUSE_FILLER);
2482         }
2483     }
2484
2485     /* Fill the new tail */
2486     if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
2487     {
2488         RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
2489                       HEAP_ENTRY_SIZE,
2490                       HEAP_TAIL_FILL);
2491     }
2492
2493     /* Copy user settable flags */
2494     InUseEntry->Flags &= ~HEAP_ENTRY_SETTABLE_FLAGS;
2495     InUseEntry->Flags |= ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4);
2496
2497     /* Return success */
2498     return TRUE;
2499 }
2500
2501 PHEAP_ENTRY_EXTRA NTAPI
2502 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry)
2503 {
2504     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry;
2505
2506     /* Check if it's a big block */
2507     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
2508     {
2509         VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
2510
2511         /* Return a pointer to the extra stuff*/
2512         return &VirtualEntry->ExtraStuff;
2513     }
2514     else
2515     {
2516         /* This is a usual entry, which means extra stuff follows this block */
2517         return (PHEAP_ENTRY_EXTRA)(HeapEntry + HeapEntry->Size - 1);
2518     }
2519 }
2520
2521
2522 /***********************************************************************
2523  *           RtlReAllocateHeap
2524  * PARAMS
2525  *   Heap   [in] Handle of heap block
2526  *   Flags    [in] Heap reallocation flags
2527  *   Ptr,    [in] Address of memory to reallocate
2528  *   Size     [in] Number of bytes to reallocate
2529  *
2530  * RETURNS
2531  * Pointer to reallocated memory block
2532  * NULL: Failure
2533  * 0x7d030f60--invalid flags in RtlHeapAllocate
2534  * @implemented
2535  */
2536 PVOID NTAPI
2537 RtlReAllocateHeap(HANDLE HeapPtr,
2538                   ULONG Flags,
2539                   PVOID Ptr,
2540                   SIZE_T Size)
2541 {
2542     PHEAP Heap = (PHEAP)HeapPtr;
2543     PHEAP_ENTRY InUseEntry, NewInUseEntry;
2544     PHEAP_ENTRY_EXTRA OldExtra, NewExtra;
2545     SIZE_T AllocationSize, FreeSize, DecommitSize;
2546     BOOLEAN HeapLocked = FALSE;
2547     PVOID NewBaseAddress;
2548     PHEAP_FREE_ENTRY SplitBlock, SplitBlock2;
2549     SIZE_T OldSize, Index, OldIndex;
2550     UCHAR FreeFlags;
2551     NTSTATUS Status;
2552     PVOID DecommitBase;
2553     SIZE_T RemainderBytes, ExtraSize;
2554     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
2555     EXCEPTION_RECORD ExceptionRecord;
2556
2557     /* Return success in case of a null pointer */
2558     if (!Ptr)
2559     {
2560         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS);
2561         return NULL;
2562     }
2563
2564     /* Force heap flags */
2565     Flags |= Heap->ForceFlags;
2566
2567     /* Call special heap */
2568     if (RtlpHeapIsSpecial(Flags))
2569         return RtlDebugReAllocateHeap(Heap, Flags, Ptr, Size);
2570
2571     /* Make sure size is valid */
2572     if (Size >= 0x80000000)
2573     {
2574         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY);
2575         return NULL;
2576     }
2577
2578     /* Calculate allocation size and index */
2579     if (Size)
2580         AllocationSize = Size;
2581     else
2582         AllocationSize = 1;
2583     AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask;
2584
2585     /* Add up extra stuff, if it is present anywhere */
2586     if (((((PHEAP_ENTRY)Ptr)-1)->Flags & HEAP_ENTRY_EXTRA_PRESENT) ||
2587         (Flags & HEAP_EXTRA_FLAGS_MASK) ||
2588         Heap->PseudoTagEntries)
2589     {
2590         AllocationSize += sizeof(HEAP_ENTRY_EXTRA);
2591     }
2592
2593     /* Acquire the lock if necessary */
2594     if (!(Flags & HEAP_NO_SERIALIZE))
2595     {
2596         RtlEnterHeapLock(Heap->LockVariable, TRUE);
2597         HeapLocked = TRUE;
2598         Flags &= ~HEAP_NO_SERIALIZE;
2599     }
2600
2601     /* Get the pointer to the in-use entry */
2602     InUseEntry = (PHEAP_ENTRY)Ptr - 1;
2603
2604     /* If that entry is not really in-use, we have a problem */
2605     if (!(InUseEntry->Flags & HEAP_ENTRY_BUSY))
2606     {
2607         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
2608
2609         /* Release the lock and return */
2610         if (HeapLocked)
2611             RtlLeaveHeapLock(Heap->LockVariable);
2612         return Ptr;
2613     }
2614
2615     if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
2616     {
2617         /* This is a virtually allocated block. Get its size */
2618         OldSize = RtlpGetSizeOfBigBlock(InUseEntry);
2619
2620         /* Convert it to an index */
2621         OldIndex = (OldSize + InUseEntry->Size) >> HEAP_ENTRY_SHIFT;
2622
2623         /* Calculate new allocation size and round it to the page size */
2624         AllocationSize += FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
2625         AllocationSize = ROUND_UP(AllocationSize, PAGE_SIZE);
2626     }
2627     else
2628     {
2629         /* Usual entry */
2630         OldIndex = InUseEntry->Size;
2631
2632         OldSize = (OldIndex << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes;
2633     }
2634
2635     /* Calculate new index */
2636     Index = AllocationSize >> HEAP_ENTRY_SHIFT;
2637
2638     /* Check for 4 different scenarios (old size, new size, old index, new index) */
2639     if (Index <= OldIndex)
2640     {
2641         /* Difference must be greater than 1, adjust if it's not so */
2642         if (Index + 1 == OldIndex)
2643         {
2644             Index++;
2645             AllocationSize += sizeof(HEAP_ENTRY);
2646         }
2647
2648         /* Calculate new size */
2649         if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
2650         {
2651             /* Simple in case of a virtual alloc - just an unused size */
2652             InUseEntry->Size = (USHORT)(AllocationSize - Size);
2653             ASSERT(InUseEntry->Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY));
2654         }
2655         else if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
2656         {
2657             /* There is extra stuff, take it into account */
2658             OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1);
2659             NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1);
2660             *NewExtra = *OldExtra;
2661
2662             // FIXME Tagging, TagIndex
2663
2664             /* Update unused bytes count */
2665             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
2666         }
2667         else
2668         {
2669             // FIXME Tagging, SmallTagIndex
2670             InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size);
2671         }
2672
2673         /* If new size is bigger than the old size */
2674         if (Size > OldSize)
2675         {
2676             /* Zero out that additional space if required */
2677             if (Flags & HEAP_ZERO_MEMORY)
2678             {
2679                 RtlZeroMemory((PCHAR)Ptr + OldSize, Size - OldSize);
2680             }
2681             else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED)
2682             {
2683                 /* Fill it on free if required */
2684                 RemainderBytes = OldSize & (sizeof(ULONG) - 1);
2685
2686                 if (RemainderBytes)
2687                     RemainderBytes = 4 - RemainderBytes;
2688
2689                 if (Size > (OldSize + RemainderBytes))
2690                 {
2691                     /* Calculate actual amount of extra bytes to fill */
2692                     ExtraSize = (Size - (OldSize + RemainderBytes)) & ~(sizeof(ULONG) - 1);
2693
2694                     /* Fill them if there are any */
2695                     if (ExtraSize != 0)
2696                     {
2697                         RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + OldSize + RemainderBytes,
2698                                            ExtraSize,
2699                                            ARENA_INUSE_FILLER);
2700                     }
2701                 }
2702             }
2703         }
2704
2705         /* Fill tail of the heap entry if required */
2706         if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED)
2707         {
2708             RtlFillMemory((PCHAR)(InUseEntry + 1) + Size,
2709                           HEAP_ENTRY_SIZE,
2710                           HEAP_TAIL_FILL);
2711         }
2712
2713         /* Check if the difference is significant or not */
2714         if (Index != OldIndex)
2715         {
2716             /* Save flags */
2717             FreeFlags = InUseEntry->Flags & ~HEAP_ENTRY_BUSY;
2718
2719             if (FreeFlags & HEAP_ENTRY_VIRTUAL_ALLOC)
2720             {
2721                 /* This is a virtual block allocation */
2722                 VirtualAllocBlock = CONTAINING_RECORD(InUseEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock);
2723
2724                 // FIXME Tagging!
2725
2726                 DecommitBase = (PCHAR)VirtualAllocBlock + AllocationSize;
2727                 DecommitSize = (OldIndex << HEAP_ENTRY_SHIFT) - AllocationSize;
2728
2729                 /* Release the memory */
2730                 Status = ZwFreeVirtualMemory(NtCurrentProcess(),
2731                                              (PVOID *)&DecommitBase,
2732                                              &DecommitSize,
2733                                              MEM_RELEASE);
2734
2735                 if (!NT_SUCCESS(Status))
2736                 {
2737                     DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase, DecommitSize, Status);
2738                 }
2739                 else
2740                 {
2741                     /* Otherwise reduce the commit size */
2742                     VirtualAllocBlock->CommitSize -= DecommitSize;
2743                 }
2744             }
2745             else
2746             {
2747                 /* Reduce size of the block and possibly split it */
2748                 SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index);
2749
2750                 /* Initialize this entry */
2751                 SplitBlock->Flags = FreeFlags;
2752                 SplitBlock->PreviousSize = (USHORT)Index;
2753                 SplitBlock->SegmentOffset = InUseEntry->SegmentOffset;
2754
2755                 /* Remember free size */
2756                 FreeSize = InUseEntry->Size - Index;
2757
2758                 /* Set new size */
2759                 InUseEntry->Size = (USHORT)Index;
2760                 InUseEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY;
2761
2762                 /* Is that the last entry */
2763                 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY)
2764                 {
2765                     /* Set its size and insert it to the list */
2766                     SplitBlock->Size = (USHORT)FreeSize;
2767                     RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
2768
2769                     /* Update total free size */
2770                     Heap->TotalFreeSize += FreeSize;
2771                 }
2772                 else
2773                 {
2774                     /* Get the block after that one */
2775                     SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize);
2776
2777                     if (SplitBlock2->Flags & HEAP_ENTRY_BUSY)
2778                     {
2779                         /* It's in use, add it here*/
2780                         SplitBlock->Size = (USHORT)FreeSize;
2781
2782                         /* Update previous size of the next entry */
2783                         ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
2784
2785                         /* Insert it to the list */
2786                         RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
2787
2788                         /* Update total size */
2789                         Heap->TotalFreeSize += FreeSize;
2790                     }
2791                     else
2792                     {
2793                         /* Next entry is free, so merge with it */
2794                         SplitBlock->Flags = SplitBlock2->Flags;
2795
2796                         /* Remove it, update total size */
2797                         RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE, FALSE);
2798                         Heap->TotalFreeSize -= SplitBlock2->Size;
2799
2800                         /* Calculate total free size */
2801                         FreeSize += SplitBlock2->Size;
2802
2803                         if (FreeSize <= HEAP_MAX_BLOCK_SIZE)
2804                         {
2805                             SplitBlock->Size = (USHORT)FreeSize;
2806
2807                             if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY))
2808                             {
2809                                 /* Update previous size of the next entry */
2810                                 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize;
2811                             }
2812
2813                             /* Insert the new one back and update total size */
2814                             RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE);
2815                             Heap->TotalFreeSize += FreeSize;
2816                         }
2817                         else
2818                         {
2819                             /* Just add it */
2820                             RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize);
2821                         }
2822                     }
2823                 }
2824             }
2825         }
2826     }
2827     else
2828     {
2829         /* We're growing the block */
2830         if ((InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) ||
2831             !RtlpGrowBlockInPlace(Heap, Flags, InUseEntry, Size, Index))
2832         {
2833             /* Growing in place failed, so growing out of place */
2834             if (Flags & HEAP_REALLOC_IN_PLACE_ONLY)
2835             {
2836                 DPRINT1("Realloc in place failed, but it was the only option\n");
2837                 Ptr = NULL;
2838             }
2839             else
2840             {
2841                 /* Clear tag bits */
2842                 Flags &= ~HEAP_TAG_MASK;
2843
2844                 /* Process extra stuff */
2845                 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
2846                 {
2847                     /* Preserve user settable flags */
2848                     Flags &= ~HEAP_SETTABLE_USER_FLAGS;
2849
2850                     Flags |= HEAP_SETTABLE_USER_VALUE | ((InUseEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4);
2851
2852                     /* Get pointer to the old extra data */
2853                     OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
2854
2855                     /* Save tag index if it was set */
2856                     if (OldExtra->TagIndex &&
2857                         !(OldExtra->TagIndex & HEAP_PSEUDO_TAG_FLAG))
2858                     {
2859                         Flags |= OldExtra->TagIndex << HEAP_TAG_SHIFT;
2860                     }
2861                 }
2862                 else if (InUseEntry->SmallTagIndex)
2863                 {
2864                     /* Take small tag index into account */
2865                     Flags |= InUseEntry->SmallTagIndex << HEAP_TAG_SHIFT;
2866                 }
2867
2868                 /* Allocate new block from the heap */
2869                 NewBaseAddress = RtlAllocateHeap(HeapPtr,
2870                                                  Flags & ~HEAP_ZERO_MEMORY,
2871                                                  Size);
2872
2873                 /* Proceed if it didn't fail */
2874                 if (NewBaseAddress)
2875                 {
2876                     /* Get new entry pointer */
2877                     NewInUseEntry = (PHEAP_ENTRY)NewBaseAddress - 1;
2878
2879                     /* Process extra stuff if it exists */
2880                     if (NewInUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
2881                     {
2882                         NewExtra = RtlpGetExtraStuffPointer(NewInUseEntry);
2883
2884                         if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
2885                         {
2886                             OldExtra = RtlpGetExtraStuffPointer(InUseEntry);
2887                             NewExtra->Settable = OldExtra->Settable;
2888                         }
2889                         else
2890                         {
2891                             RtlZeroMemory(NewExtra, sizeof(*NewExtra));
2892                         }
2893                     }
2894
2895                     /* Copy actual user bits */
2896                     if (Size < OldSize)
2897                         RtlMoveMemory(NewBaseAddress, Ptr, Size);
2898                     else
2899                         RtlMoveMemory(NewBaseAddress, Ptr, OldSize);
2900
2901                     /* Zero remaining part if required */
2902                     if (Size > OldSize &&
2903                         (Flags & HEAP_ZERO_MEMORY))
2904                     {
2905                         RtlZeroMemory((PCHAR)NewBaseAddress + OldSize, Size - OldSize);
2906                     }
2907
2908                     /* Free the old block */
2909                     RtlFreeHeap(HeapPtr, Flags, Ptr);
2910                 }
2911
2912                 Ptr = NewBaseAddress;
2913             }
2914         }
2915     }
2916
2917     /* Did resizing fail? */
2918     if (!Ptr && (Flags & HEAP_GENERATE_EXCEPTIONS))
2919     {
2920         /* Generate an exception if required */
2921         ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY;
2922         ExceptionRecord.ExceptionRecord = NULL;
2923         ExceptionRecord.NumberParameters = 1;
2924         ExceptionRecord.ExceptionFlags = 0;
2925         ExceptionRecord.ExceptionInformation[0] = AllocationSize;
2926
2927         RtlRaiseException(&ExceptionRecord);
2928     }
2929
2930     /* Release the heap lock if it was acquired */
2931     if (HeapLocked)
2932         RtlLeaveHeapLock(Heap->LockVariable);
2933
2934     return Ptr;
2935 }
2936
2937
2938 /***********************************************************************
2939  *           RtlCompactHeap
2940  *
2941  * @unimplemented
2942  */
2943 ULONG NTAPI
2944 RtlCompactHeap(HANDLE Heap,
2945                 ULONG Flags)
2946 {
2947    UNIMPLEMENTED;
2948    return 0;
2949 }
2950
2951
2952 /***********************************************************************
2953  *           RtlLockHeap
2954  * Attempts to acquire the critical section object for a specified heap.
2955  *
2956  * PARAMS
2957  *   Heap  [in] Handle of heap to lock for exclusive access
2958  *
2959  * RETURNS
2960  * TRUE: Success
2961  * FALSE: Failure
2962  *
2963  * @implemented
2964  */
2965 BOOLEAN NTAPI
2966 RtlLockHeap(IN HANDLE HeapPtr)
2967 {
2968     PHEAP Heap = (PHEAP)HeapPtr;
2969
2970     // FIXME Check for special heap
2971
2972     /* Check if it's really a heap */
2973     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
2974
2975     /* Lock if it's lockable */
2976     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
2977     {
2978         RtlEnterHeapLock(Heap->LockVariable, TRUE);
2979     }
2980
2981     return TRUE;
2982 }
2983
2984
2985 /***********************************************************************
2986  *           RtlUnlockHeap
2987  * Releases ownership of the critical section object.
2988  *
2989  * PARAMS
2990  *   Heap  [in] Handle to the heap to unlock
2991  *
2992  * RETURNS
2993  * TRUE: Success
2994  * FALSE: Failure
2995  *
2996  * @implemented
2997  */
2998 BOOLEAN NTAPI
2999 RtlUnlockHeap(HANDLE HeapPtr)
3000 {
3001     PHEAP Heap = (PHEAP)HeapPtr;
3002
3003     // FIXME Check for special heap
3004
3005     /* Check if it's really a heap */
3006     if (Heap->Signature != HEAP_SIGNATURE) return FALSE;
3007
3008     /* Unlock if it's lockable */
3009     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
3010     {
3011         RtlLeaveHeapLock(Heap->LockVariable);
3012     }
3013
3014     return TRUE;
3015 }
3016
3017
3018 /***********************************************************************
3019  *           RtlSizeHeap
3020  * PARAMS
3021  *   Heap  [in] Handle of heap
3022  *   Flags   [in] Heap size control flags
3023  *   Ptr     [in] Address of memory to return size for
3024  *
3025  * RETURNS
3026  * Size in bytes of allocated memory
3027  * 0xffffffff: Failure
3028  *
3029  * @implemented
3030  */
3031 SIZE_T NTAPI
3032 RtlSizeHeap(
3033    HANDLE HeapPtr,
3034    ULONG Flags,
3035    PVOID Ptr
3036 )
3037 {
3038     PHEAP Heap = (PHEAP)HeapPtr;
3039     PHEAP_ENTRY HeapEntry;
3040     SIZE_T EntrySize;
3041
3042     // FIXME This is a hack around missing SEH support!
3043     if (!Heap)
3044     {
3045         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE);
3046         return (SIZE_T)-1;
3047     }
3048
3049     /* Force flags */
3050     Flags |= Heap->ForceFlags;
3051
3052     /* Call special heap */
3053     if (RtlpHeapIsSpecial(Flags))
3054         return RtlDebugSizeHeap(Heap, Flags, Ptr);
3055
3056     /* Get the heap entry pointer */
3057     HeapEntry = (PHEAP_ENTRY)Ptr - 1;
3058
3059     /* Return -1 if that entry is free */
3060     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
3061     {
3062         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
3063         return (SIZE_T)-1;
3064     }
3065
3066     /* Get size of this block depending if it's a usual or a big one */
3067     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
3068     {
3069         EntrySize = RtlpGetSizeOfBigBlock(HeapEntry);
3070     }
3071     else
3072     {
3073         /* Calculate it */
3074         EntrySize = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
3075     }
3076
3077     /* Return calculated size */
3078     return EntrySize;
3079 }
3080
3081 BOOLEAN NTAPI
3082 RtlpCheckInUsePattern(PHEAP_ENTRY HeapEntry)
3083 {
3084     SIZE_T Size, Result;
3085     PCHAR TailPart;
3086
3087     /* Calculate size */
3088     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC)
3089         Size = RtlpGetSizeOfBigBlock(HeapEntry);
3090     else
3091         Size = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes;
3092
3093     /* Calculate pointer to the tail part of the block */
3094     TailPart = (PCHAR)(HeapEntry + 1) + Size;
3095
3096     /* Compare tail pattern */
3097     Result = RtlCompareMemory(TailPart,
3098                               FillPattern,
3099                               HEAP_ENTRY_SIZE);
3100
3101     if (Result != HEAP_ENTRY_SIZE)
3102     {
3103         DPRINT1("HEAP: Heap entry (size %x) %p tail is modified at %p\n", Size, HeapEntry, TailPart + Result);
3104         return FALSE;
3105     }
3106
3107     /* All is fine */
3108     return TRUE;
3109 }
3110
3111 BOOLEAN NTAPI
3112 RtlpValidateHeapHeaders(
3113     PHEAP Heap,
3114     BOOLEAN Recalculate)
3115 {
3116     // We skip header validation for now
3117     return TRUE;
3118 }
3119
3120 BOOLEAN NTAPI
3121 RtlpValidateHeapEntry(
3122     PHEAP Heap,
3123     PHEAP_ENTRY HeapEntry)
3124 {
3125     BOOLEAN BigAllocation, EntryFound = FALSE;
3126     PHEAP_SEGMENT Segment;
3127     ULONG SegmentOffset;
3128
3129     /* Perform various consistency checks of this entry */
3130     if (!HeapEntry) goto invalid_entry;
3131     if ((ULONG_PTR)HeapEntry & (HEAP_ENTRY_SIZE - 1)) goto invalid_entry;
3132     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) goto invalid_entry;
3133
3134     BigAllocation = HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC;
3135     Segment = Heap->Segments[HeapEntry->SegmentOffset];
3136
3137     if (BigAllocation &&
3138         (((ULONG_PTR)HeapEntry & (PAGE_SIZE - 1)) != FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock)))
3139          goto invalid_entry;
3140
3141     if (!BigAllocation && (HeapEntry->SegmentOffset >= HEAP_SEGMENTS ||
3142         !Segment ||
3143         HeapEntry < Segment->FirstEntry ||
3144         HeapEntry >= Segment->LastValidEntry))
3145         goto invalid_entry;
3146
3147     if ((HeapEntry->Flags & HEAP_ENTRY_FILL_PATTERN) &&
3148         !RtlpCheckInUsePattern(HeapEntry))
3149         goto invalid_entry;
3150
3151     /* Checks are done, if this is a virtual entry, that's all */
3152     if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) return TRUE;
3153
3154     /* Go through segments and check if this entry fits into any of them */
3155     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
3156     {
3157         Segment = Heap->Segments[SegmentOffset];
3158         if (!Segment) continue;
3159
3160         if ((HeapEntry >= Segment->FirstEntry) &&
3161             (HeapEntry < Segment->LastValidEntry))
3162         {
3163             /* Got it */
3164             EntryFound = TRUE;
3165             break;
3166         }
3167     }
3168
3169     /* Return our result of finding entry in the segments */
3170     return EntryFound;
3171
3172 invalid_entry:
3173     DPRINT1("HEAP: Invalid heap entry %p in heap %p\n", HeapEntry, Heap);
3174     return FALSE;
3175 }
3176
3177 BOOLEAN NTAPI
3178 RtlpValidateHeapSegment(
3179     PHEAP Heap,
3180     PHEAP_SEGMENT Segment,
3181     UCHAR SegmentOffset,
3182     PULONG FreeEntriesCount,
3183     PSIZE_T TotalFreeSize,
3184     PSIZE_T TagEntries,
3185     PSIZE_T PseudoTagEntries)
3186 {
3187     PHEAP_UCR_DESCRIPTOR UcrDescriptor;
3188     PLIST_ENTRY UcrEntry;
3189     SIZE_T ByteSize, Size, Result;
3190     PHEAP_ENTRY CurrentEntry;
3191     ULONG UnCommittedPages;
3192     ULONG UnCommittedRanges;
3193     ULONG PreviousSize;
3194
3195     UnCommittedPages = 0;
3196     UnCommittedRanges = 0;
3197
3198     if (IsListEmpty(&Segment->UCRSegmentList))
3199     {
3200         UcrEntry = NULL;
3201         UcrDescriptor = NULL;
3202     }
3203     else
3204     {
3205         UcrEntry = Segment->UCRSegmentList.Flink;
3206         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
3207     }
3208
3209     if (Segment->BaseAddress == Heap)
3210         CurrentEntry = &Heap->Entry;
3211     else
3212         CurrentEntry = &Segment->Entry;
3213
3214     while (CurrentEntry < Segment->LastValidEntry)
3215     {
3216         if (UcrDescriptor &&
3217             ((PVOID)CurrentEntry >= UcrDescriptor->Address))
3218         {
3219             DPRINT1("HEAP: Entry %p is not inside uncommited range [%p .. %p)\n",
3220                     CurrentEntry, UcrDescriptor->Address,
3221                     (PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
3222
3223             return FALSE;
3224         }
3225
3226         PreviousSize = 0;
3227
3228         while (CurrentEntry < Segment->LastValidEntry)
3229         {
3230             if (PreviousSize != CurrentEntry->PreviousSize)
3231             {
3232                 DPRINT1("HEAP: Entry %p has incorrect PreviousSize %x instead of %x\n",
3233                     CurrentEntry, CurrentEntry->PreviousSize, PreviousSize);
3234
3235                 return FALSE;
3236             }
3237
3238             PreviousSize = CurrentEntry->Size;
3239             Size = CurrentEntry->Size << HEAP_ENTRY_SHIFT;
3240
3241             if (CurrentEntry->Flags & HEAP_ENTRY_BUSY)
3242             {
3243                 if (TagEntries)
3244                 {
3245                     UNIMPLEMENTED;
3246                 }
3247
3248                 /* Check fill pattern */
3249                 if (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN)
3250                 {
3251                     if (!RtlpCheckInUsePattern(CurrentEntry))
3252                         return FALSE;
3253                 }
3254             }
3255             else
3256             {
3257                 /* The entry is free, increase free entries count and total free size */
3258                 *FreeEntriesCount = *FreeEntriesCount + 1;
3259                 *TotalFreeSize += CurrentEntry->Size;
3260
3261                 if ((Heap->Flags & HEAP_FREE_CHECKING_ENABLED) &&
3262                     (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN))
3263                 {
3264                     ByteSize = Size - sizeof(HEAP_FREE_ENTRY);
3265
3266                     if ((CurrentEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) &&
3267                         (ByteSize > sizeof(HEAP_FREE_ENTRY_EXTRA)))
3268                     {
3269                         ByteSize -= sizeof(HEAP_FREE_ENTRY_EXTRA);
3270                     }
3271
3272                     Result = RtlCompareMemoryUlong((PCHAR)((PHEAP_FREE_ENTRY)CurrentEntry + 1),
3273                                                     ByteSize,
3274                                                     ARENA_FREE_FILLER);
3275
3276                     if (Result != ByteSize)
3277                     {
3278                         DPRINT1("HEAP: Free heap block %p modified at %p after it was freed\n",
3279                             CurrentEntry,
3280                             (PCHAR)(CurrentEntry + 1) + Result);
3281
3282                         return FALSE;
3283                     }
3284                 }
3285             }
3286
3287             if (CurrentEntry->SegmentOffset != SegmentOffset)
3288             {
3289                 DPRINT1("HEAP: Heap entry %p SegmentOffset is incorrect %x (should be %x)\n",
3290                         CurrentEntry, SegmentOffset, CurrentEntry->SegmentOffset);
3291                 return FALSE;
3292             }
3293
3294             /* Check if it's the last entry */
3295             if (CurrentEntry->Flags & HEAP_ENTRY_LAST_ENTRY)
3296             {
3297                 CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
3298
3299                 if (!UcrDescriptor)
3300                 {
3301                     /* Check if it's not really the last one */
3302                     if (CurrentEntry != Segment->LastValidEntry)
3303                     {
3304                         DPRINT1("HEAP: Heap entry %p is not last block in segment (%p)\n",
3305                                 CurrentEntry, Segment->LastValidEntry);
3306                         return FALSE;
3307                     }
3308                 }
3309                 else if (CurrentEntry != UcrDescriptor->Address)
3310                 {
3311                     DPRINT1("HEAP: Heap entry %p does not match next uncommitted address (%p)\n",
3312                         CurrentEntry, UcrDescriptor->Address);
3313
3314                     return FALSE;
3315                 }
3316                 else
3317                 {
3318                     UnCommittedPages += (ULONG)(UcrDescriptor->Size / PAGE_SIZE);
3319                     UnCommittedRanges++;
3320
3321                     CurrentEntry = (PHEAP_ENTRY)((PCHAR)UcrDescriptor->Address + UcrDescriptor->Size);
3322
3323                     /* Go to the next UCR descriptor */
3324                     UcrEntry = UcrEntry->Flink;
3325                     if (UcrEntry == &Segment->UCRSegmentList)
3326                     {
3327                         UcrEntry = NULL;
3328                         UcrDescriptor = NULL;
3329                     }
3330                     else
3331                     {
3332                         UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry);
3333                     }
3334                 }
3335
3336                 break;
3337             }
3338
3339             /* Advance to the next entry */
3340             CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size);
3341         }
3342     }
3343
3344     /* Check total numbers of UCP and UCR */
3345     if (Segment->NumberOfUnCommittedPages != UnCommittedPages)
3346     {
3347         DPRINT1("HEAP: Segment %p NumberOfUnCommittedPages is invalid (%x != %x)\n",
3348             Segment, Segment->NumberOfUnCommittedPages, UnCommittedPages);
3349
3350         return FALSE;
3351     }
3352
3353     if (Segment->NumberOfUnCommittedRanges != UnCommittedRanges)
3354     {
3355         DPRINT1("HEAP: Segment %p NumberOfUnCommittedRanges is invalid (%x != %x)\n",
3356             Segment, Segment->NumberOfUnCommittedRanges, UnCommittedRanges);
3357
3358         return FALSE;
3359     }
3360
3361     return TRUE;
3362 }
3363
3364 BOOLEAN NTAPI
3365 RtlpValidateHeap(PHEAP Heap,
3366                  BOOLEAN ForceValidation)
3367 {
3368     PHEAP_SEGMENT Segment;
3369     BOOLEAN EmptyList;
3370     UCHAR SegmentOffset;
3371     SIZE_T Size, TotalFreeSize;
3372     ULONG PreviousSize;
3373     PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock;
3374     PLIST_ENTRY ListHead, NextEntry;
3375     PHEAP_FREE_ENTRY FreeEntry;
3376     ULONG FreeBlocksCount, FreeListEntriesCount;
3377
3378     /* Check headers */
3379     if (!RtlpValidateHeapHeaders(Heap, FALSE))
3380         return FALSE;
3381
3382     /* Skip validation if it's not needed */
3383     if (!ForceValidation && !(Heap->Flags & HEAP_VALIDATE_ALL_ENABLED))
3384         return TRUE;
3385
3386     /* Check free lists bitmaps */
3387     FreeListEntriesCount = 0;
3388     ListHead = &Heap->FreeLists[0];
3389
3390     for (Size = 0; Size < HEAP_FREELISTS; Size++)
3391     {
3392         if (Size)
3393         {
3394             /* This is a dedicated list. Check if it's empty */
3395             EmptyList = IsListEmpty(ListHead);
3396
3397             if (Heap->u.FreeListsInUseBytes[Size >> 3] & (1 << (Size & 7)))
3398             {
3399                 if (EmptyList)
3400                 {
3401                     DPRINT1("HEAP: Empty %x-free list marked as non-empty\n", Size);
3402                     return FALSE;
3403                 }
3404             }
3405             else
3406             {
3407                 if (!EmptyList)
3408                 {
3409                     DPRINT1("HEAP: Non-empty %x-free list marked as empty\n", Size);
3410                     return FALSE;
3411                 }
3412             }
3413         }
3414
3415         /* Now check this list entries */
3416         NextEntry = ListHead->Flink;
3417         PreviousSize = 0;
3418
3419         while (ListHead != NextEntry)
3420         {
3421             FreeEntry = CONTAINING_RECORD(NextEntry, HEAP_FREE_ENTRY, FreeList);
3422             NextEntry = NextEntry->Flink;
3423
3424             /* If there is an in-use entry in a free list - that's quite a big problem */
3425             if (FreeEntry->Flags & HEAP_ENTRY_BUSY)
3426             {
3427                 DPRINT1("HEAP: %Ix-dedicated list free element %p is marked in-use\n", Size, FreeEntry);
3428                 return FALSE;
3429             }
3430
3431             /* Check sizes according to that specific list's size */
3432             if ((Size == 0) && (FreeEntry->Size < HEAP_FREELISTS))
3433             {
3434                 DPRINT1("HEAP: Non dedicated list free element %p has size %x which would fit a dedicated list\n", FreeEntry, FreeEntry->Size);
3435                 return FALSE;
3436             }
3437             else if (Size && (FreeEntry->Size != Size))
3438             {
3439                 DPRINT1("HEAP: %Ix-dedicated list free element %p has incorrect size %x\n", Size, FreeEntry, FreeEntry->Size);
3440                 return FALSE;
3441             }
3442             else if ((Size == 0) && (FreeEntry->Size < PreviousSize))
3443             {
3444                 DPRINT1("HEAP: Non dedicated list free element %p is not put in order\n", FreeEntry);
3445                 return FALSE;
3446             }
3447
3448             /* Remember previous size*/
3449             PreviousSize = FreeEntry->Size;
3450
3451             /* Add up to the total amount of free entries */
3452             FreeListEntriesCount++;
3453         }
3454
3455         /* Go to the head of the next free list */
3456         ListHead++;
3457     }
3458
3459     /* Check big allocations */
3460     ListHead = &Heap->VirtualAllocdBlocks;
3461     NextEntry = ListHead->Flink;
3462
3463     while (ListHead != NextEntry)
3464     {
3465         VirtualAllocBlock = CONTAINING_RECORD(NextEntry, HEAP_VIRTUAL_ALLOC_ENTRY, Entry);
3466
3467         /* We can only check the fill pattern */
3468         if (VirtualAllocBlock->BusyBlock.Flags & HEAP_ENTRY_FILL_PATTERN)
3469         {
3470             if (!RtlpCheckInUsePattern(&VirtualAllocBlock->BusyBlock))
3471                 return FALSE;
3472         }
3473
3474         NextEntry = NextEntry->Flink;
3475     }
3476
3477     /* Check all segments */
3478     FreeBlocksCount = 0;
3479     TotalFreeSize = 0;
3480
3481     for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++)
3482     {
3483         Segment = Heap->Segments[SegmentOffset];
3484
3485         /* Go to the next one if there is no segment */
3486         if (!Segment) continue;
3487
3488         if (!RtlpValidateHeapSegment(Heap,
3489                                      Segment,
3490                                      SegmentOffset,
3491                                      &FreeBlocksCount,
3492                                      &TotalFreeSize,
3493                                      NULL,
3494                                      NULL))
3495         {
3496             return FALSE;
3497         }
3498     }
3499
3500     if (FreeListEntriesCount != FreeBlocksCount)
3501     {
3502         DPRINT1("HEAP: Free blocks count in arena (%lu) does not match free blocks number in the free lists (%lu)\n", FreeBlocksCount, FreeListEntriesCount);
3503         return FALSE;
3504     }
3505
3506     if (Heap->TotalFreeSize != TotalFreeSize)
3507     {
3508         DPRINT1("HEAP: Total size of free blocks in arena (%Iu) does not equal to the one in heap header (%Iu)\n", TotalFreeSize, Heap->TotalFreeSize);
3509         return FALSE;
3510     }
3511
3512     return TRUE;
3513 }
3514
3515 /***********************************************************************
3516  *           RtlValidateHeap
3517  * Validates a specified heap.
3518  *
3519  * PARAMS
3520  *   Heap  [in] Handle to the heap
3521  *   Flags   [in] Bit flags that control access during operation
3522  *   Block  [in] Optional pointer to memory block to validate
3523  *
3524  * NOTES
3525  * Flags is ignored.
3526  *
3527  * RETURNS
3528  * TRUE: Success
3529  * FALSE: Failure
3530  *
3531  * @implemented
3532  */
3533 BOOLEAN NTAPI RtlValidateHeap(
3534    HANDLE HeapPtr,
3535    ULONG Flags,
3536    PVOID Block
3537 )
3538 {
3539     PHEAP Heap = (PHEAP)HeapPtr;
3540     BOOLEAN HeapLocked = FALSE;
3541     BOOLEAN HeapValid;
3542
3543     /* Check for page heap */
3544     if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS)
3545         return RtlpDebugPageHeapValidate(HeapPtr, Flags, Block);
3546
3547     /* Check signature */
3548     if (Heap->Signature != HEAP_SIGNATURE)
3549     {
3550         DPRINT1("HEAP: Signature %lx is invalid for heap %p\n", Heap->Signature, Heap);
3551         return FALSE;
3552     }
3553
3554     /* Force flags */
3555     Flags = Heap->ForceFlags;
3556
3557     /* Acquire the lock if necessary */
3558     if (!(Flags & HEAP_NO_SERIALIZE))
3559     {
3560         RtlEnterHeapLock(Heap->LockVariable, TRUE);
3561         HeapLocked = TRUE;
3562     }
3563
3564     /* Either validate whole heap or just one entry */
3565     if (!Block)
3566         HeapValid = RtlpValidateHeap(Heap, TRUE);
3567     else
3568         HeapValid = RtlpValidateHeapEntry(Heap, (PHEAP_ENTRY)Block - 1);
3569
3570     /* Unlock if it's lockable */
3571     if (HeapLocked)
3572     {
3573         RtlLeaveHeapLock(Heap->LockVariable);
3574     }
3575
3576     return HeapValid;
3577 }
3578
3579 /*
3580  * @implemented
3581  */
3582 NTSTATUS NTAPI
3583 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine,
3584                     PVOID lParam)
3585 {
3586     UNIMPLEMENTED;
3587     return STATUS_NOT_IMPLEMENTED;
3588 }
3589
3590
3591 /*
3592  * @implemented
3593  */
3594 ULONG NTAPI
3595 RtlGetProcessHeaps(ULONG count,
3596                    HANDLE *heaps)
3597 {
3598     UNIMPLEMENTED;
3599     return 0;
3600 }
3601
3602
3603 /*
3604  * @implemented
3605  */
3606 BOOLEAN NTAPI
3607 RtlValidateProcessHeaps(VOID)
3608 {
3609     UNIMPLEMENTED;
3610     return TRUE;
3611 }
3612
3613
3614 /*
3615  * @unimplemented
3616  */
3617 BOOLEAN NTAPI
3618 RtlZeroHeap(
3619     IN PVOID HeapHandle,
3620     IN ULONG Flags
3621     )
3622 {
3623     UNIMPLEMENTED;
3624     return FALSE;
3625 }
3626
3627 /*
3628  * @implemented
3629  */
3630 BOOLEAN
3631 NTAPI
3632 RtlSetUserValueHeap(IN PVOID HeapHandle,
3633                     IN ULONG Flags,
3634                     IN PVOID BaseAddress,
3635                     IN PVOID UserValue)
3636 {
3637     PHEAP Heap = (PHEAP)HeapHandle;
3638     PHEAP_ENTRY HeapEntry;
3639     PHEAP_ENTRY_EXTRA Extra;
3640     BOOLEAN HeapLocked = FALSE, ValueSet = FALSE;
3641
3642     /* Force flags */
3643     Flags |= Heap->Flags;
3644
3645     /* Call special heap */
3646     if (RtlpHeapIsSpecial(Flags))
3647         return RtlDebugSetUserValueHeap(Heap, Flags, BaseAddress, UserValue);
3648
3649     /* Lock if it's lockable */
3650     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
3651     {
3652         RtlEnterHeapLock(Heap->LockVariable, TRUE);
3653         HeapLocked = TRUE;
3654     }
3655
3656     /* Get a pointer to the entry */
3657     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
3658
3659     /* If it's a free entry - return error */
3660     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
3661     {
3662         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
3663
3664         /* Release the heap lock if it was acquired */
3665         if (HeapLocked)
3666             RtlLeaveHeapLock(Heap->LockVariable);
3667
3668         return FALSE;
3669     }
3670
3671     /* Check if this entry has an extra stuff associated with it */
3672     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
3673     {
3674         /* Use extra to store the value */
3675         Extra = RtlpGetExtraStuffPointer(HeapEntry);
3676         Extra->Settable = (ULONG_PTR)UserValue;
3677
3678         /* Indicate that value was set */
3679         ValueSet = TRUE;
3680     }
3681
3682     /* Release the heap lock if it was acquired */
3683     if (HeapLocked)
3684         RtlLeaveHeapLock(Heap->LockVariable);
3685
3686     return ValueSet;
3687 }
3688
3689 /*
3690  * @implemented
3691  */
3692 BOOLEAN
3693 NTAPI
3694 RtlSetUserFlagsHeap(IN PVOID HeapHandle,
3695                     IN ULONG Flags,
3696                     IN PVOID BaseAddress,
3697                     IN ULONG UserFlagsReset,
3698                     IN ULONG UserFlagsSet)
3699 {
3700     PHEAP Heap = (PHEAP)HeapHandle;
3701     PHEAP_ENTRY HeapEntry;
3702     BOOLEAN HeapLocked = FALSE;
3703
3704     /* Force flags */
3705     Flags |= Heap->Flags;
3706
3707     /* Call special heap */
3708     if (RtlpHeapIsSpecial(Flags))
3709         return RtlDebugSetUserFlagsHeap(Heap, Flags, BaseAddress, UserFlagsReset, UserFlagsSet);
3710
3711     /* Lock if it's lockable */
3712     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
3713     {
3714         RtlEnterHeapLock(Heap->LockVariable, TRUE);
3715         HeapLocked = TRUE;
3716     }
3717
3718     /* Get a pointer to the entry */
3719     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
3720
3721     /* If it's a free entry - return error */
3722     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
3723     {
3724         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
3725
3726         /* Release the heap lock if it was acquired */
3727         if (HeapLocked)
3728             RtlLeaveHeapLock(Heap->LockVariable);
3729
3730         return FALSE;
3731     }
3732
3733     /* Set / reset flags */
3734     HeapEntry->Flags &= ~(UserFlagsReset >> 4);
3735     HeapEntry->Flags |= (UserFlagsSet >> 4);
3736
3737     /* Release the heap lock if it was acquired */
3738     if (HeapLocked)
3739         RtlLeaveHeapLock(Heap->LockVariable);
3740
3741     return TRUE;
3742 }
3743
3744 /*
3745  * @implemented
3746  */
3747 BOOLEAN
3748 NTAPI
3749 RtlGetUserInfoHeap(IN PVOID HeapHandle,
3750                    IN ULONG Flags,
3751                    IN PVOID BaseAddress,
3752                    OUT PVOID *UserValue,
3753                    OUT PULONG UserFlags)
3754 {
3755     PHEAP Heap = (PHEAP)HeapHandle;
3756     PHEAP_ENTRY HeapEntry;
3757     PHEAP_ENTRY_EXTRA Extra;
3758     BOOLEAN HeapLocked = FALSE;
3759
3760     /* Force flags */
3761     Flags |= Heap->Flags;
3762
3763     /* Call special heap */
3764     if (RtlpHeapIsSpecial(Flags))
3765         return RtlDebugGetUserInfoHeap(Heap, Flags, BaseAddress, UserValue, UserFlags);
3766
3767     /* Lock if it's lockable */
3768     if (!(Heap->Flags & HEAP_NO_SERIALIZE))
3769     {
3770         RtlEnterHeapLock(Heap->LockVariable, TRUE);
3771         HeapLocked = TRUE;
3772     }
3773
3774     /* Get a pointer to the entry */
3775     HeapEntry = (PHEAP_ENTRY)BaseAddress - 1;
3776
3777     /* If it's a free entry - return error */
3778     if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY))
3779     {
3780         RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER);
3781
3782         /* Release the heap lock if it was acquired */
3783         if (HeapLocked)
3784             RtlLeaveHeapLock(Heap->LockVariable);
3785
3786         return FALSE;
3787     }
3788
3789     /* Check if this entry has an extra stuff associated with it */
3790     if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT)
3791     {
3792         /* Get pointer to extra data */
3793         Extra = RtlpGetExtraStuffPointer(HeapEntry);
3794
3795         /* Pass user value */
3796         if (UserValue)
3797             *UserValue = (PVOID)Extra->Settable;
3798     }
3799
3800     /* Decode and return user flags */
3801     if (UserFlags)
3802         *UserFlags = (HeapEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4;
3803
3804     /* Release the heap lock if it was acquired */
3805     if (HeapLocked)
3806         RtlLeaveHeapLock(Heap->LockVariable);
3807
3808     return TRUE;
3809 }
3810
3811 /*
3812  * @unimplemented
3813  */
3814 NTSTATUS
3815 NTAPI
3816 RtlUsageHeap(IN HANDLE Heap,
3817              IN ULONG Flags,
3818              OUT PRTL_HEAP_USAGE Usage)
3819 {
3820     /* TODO */
3821     UNIMPLEMENTED;
3822     return STATUS_NOT_IMPLEMENTED;
3823 }
3824
3825 PWSTR
3826 NTAPI
3827 RtlQueryTagHeap(IN PVOID HeapHandle,
3828                 IN ULONG Flags,
3829                 IN USHORT TagIndex,
3830                 IN BOOLEAN ResetCounters,
3831                 OUT PRTL_HEAP_TAG_INFO HeapTagInfo)
3832 {
3833     /* TODO */
3834     UNIMPLEMENTED;
3835     return NULL;
3836 }
3837
3838 ULONG
3839 NTAPI
3840 RtlExtendHeap(IN HANDLE Heap,
3841               IN ULONG Flags,
3842               IN PVOID P,
3843               IN SIZE_T Size)
3844 {
3845     /* TODO */
3846     UNIMPLEMENTED;
3847     return 0;
3848 }
3849
3850 ULONG
3851 NTAPI
3852 RtlCreateTagHeap(IN HANDLE HeapHandle,
3853                  IN ULONG Flags,
3854                  IN PWSTR TagName,
3855                  IN PWSTR TagSubName)
3856 {
3857     /* TODO */
3858     UNIMPLEMENTED;
3859     return 0;
3860 }
3861
3862 NTSTATUS
3863 NTAPI
3864 RtlWalkHeap(IN HANDLE HeapHandle,
3865             IN PVOID HeapEntry)
3866 {
3867     UNIMPLEMENTED;
3868     return STATUS_NOT_IMPLEMENTED;
3869 }
3870
3871 PVOID
3872 NTAPI
3873 RtlProtectHeap(IN PVOID HeapHandle,
3874                IN BOOLEAN ReadOnly)
3875 {
3876     UNIMPLEMENTED;
3877     return NULL;
3878 }
3879
3880 NTSTATUS
3881 NTAPI
3882 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL,
3883                       IN HEAP_INFORMATION_CLASS HeapInformationClass,
3884                       IN PVOID HeapInformation,
3885                       IN SIZE_T HeapInformationLength)
3886 {
3887     /* Setting heap information is not really supported except for enabling LFH */
3888     if (HeapInformationClass == HeapCompatibilityInformation)
3889     {
3890         /* Check buffer length */
3891         if (HeapInformationLength < sizeof(ULONG))
3892         {
3893             /* The provided buffer is too small */
3894             return STATUS_BUFFER_TOO_SMALL;
3895         }
3896
3897         /* Check for a special magic value for enabling LFH */
3898         if (*(PULONG)HeapInformation != 2)
3899         {
3900             return STATUS_UNSUCCESSFUL;
3901         }
3902
3903         DPRINT1("RtlSetHeapInformation() needs to enable LFH\n");
3904         return STATUS_SUCCESS;
3905     }
3906
3907     return STATUS_SUCCESS;
3908 }
3909
3910 NTSTATUS
3911 NTAPI
3912 RtlQueryHeapInformation(HANDLE HeapHandle,
3913                         HEAP_INFORMATION_CLASS HeapInformationClass,
3914                         PVOID HeapInformation,
3915                         SIZE_T HeapInformationLength,
3916                         PSIZE_T ReturnLength OPTIONAL)
3917 {
3918     PHEAP Heap = (PHEAP)HeapHandle;
3919
3920     /* Only HeapCompatibilityInformation is supported */
3921     if (HeapInformationClass == HeapCompatibilityInformation)
3922     {
3923         /* Set result length */
3924         if (ReturnLength)
3925             *ReturnLength = sizeof(ULONG);
3926
3927         /* Check buffer length */
3928         if (HeapInformationLength < sizeof(ULONG))
3929         {
3930             /* It's too small, return needed length */
3931             return STATUS_BUFFER_TOO_SMALL;
3932         }
3933
3934         /* Return front end heap type */
3935         *(PULONG)HeapInformation = Heap->FrontEndHeapType;
3936
3937         return STATUS_SUCCESS;
3938     }
3939
3940     return STATUS_UNSUCCESSFUL;
3941 }
3942
3943 NTSTATUS
3944 NTAPI
3945 RtlMultipleAllocateHeap(IN PVOID HeapHandle,
3946                         IN ULONG Flags,
3947                         IN SIZE_T Size,
3948                         IN ULONG Count,
3949                         OUT PVOID *Array)
3950 {
3951     UNIMPLEMENTED;
3952     return 0;
3953 }
3954
3955 NTSTATUS
3956 NTAPI
3957 RtlMultipleFreeHeap(IN PVOID HeapHandle,
3958                     IN ULONG Flags,
3959                     IN ULONG Count,
3960                     OUT PVOID *Array)
3961 {
3962     UNIMPLEMENTED;
3963     return 0;
3964 }
3965
3966 /* EOF */