reactos/lib/rtl/heap.c

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