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