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