lib/rtl/heappage.c

   1 /* COPYRIGHT:       See COPYING in the top level directory
   2  * PROJECT:         ReactOS system libraries
   3  * FILE:            lib/rtl/heappage.c
   4  * PURPOSE:         RTL Page Heap implementation
   5  * PROGRAMMERS:     Copyright 2011 Aleksey Bragin
   6  */
   7
   8 /* Useful references:
   9     http://msdn.microsoft.com/en-us/library/ms220938(VS.80).aspx
  10     http://blogs.msdn.com/b/jiangyue/archive/2010/03/16/windows-heap-overrun-monitoring.aspx
  11 */
  12
  13 /* INCLUDES *****************************************************************/
  14
  15 #include <rtl.h>
  16 #include <heap.h>
  17
  18 #define NDEBUG
  19 #include <debug.h>
  20
  21 /* TYPES **********************************************************************/
  22
  23 typedef struct _DPH_BLOCK_INFORMATION
  24 {
  25      ULONG StartStamp;
  26      PVOID Heap;
  27      SIZE_T RequestedSize;
  28      SIZE_T ActualSize;
  29      union
  30      {
  31           LIST_ENTRY FreeQueue;
  32           SINGLE_LIST_ENTRY FreePushList;
  33           WORD TraceIndex;
  34      };
  35      PVOID StackTrace;
  36      ULONG EndStamp;
  37 } DPH_BLOCK_INFORMATION, *PDPH_BLOCK_INFORMATION;
  38
  39 typedef struct _DPH_HEAP_BLOCK
  40 {
  41      union
  42      {
  43           struct _DPH_HEAP_BLOCK *pNextAlloc;
  44           LIST_ENTRY AvailableEntry;
  45           RTL_BALANCED_LINKS TableLinks;
  46      };
  47      PUCHAR pUserAllocation;
  48      PUCHAR pVirtualBlock;
  49      SIZE_T nVirtualBlockSize;
  50      SIZE_T nVirtualAccessSize;
  51      SIZE_T nUserRequestedSize;
  52      SIZE_T nUserActualSize;
  53      PVOID UserValue;
  54      ULONG UserFlags;
  55      PRTL_TRACE_BLOCK StackTrace;
  56      LIST_ENTRY AdjacencyEntry;
  57      PUCHAR pVirtualRegion;
  58 } DPH_HEAP_BLOCK, *PDPH_HEAP_BLOCK;
  59
  60 typedef struct _DPH_HEAP_ROOT
  61 {
  62      ULONG Signature;
  63      ULONG HeapFlags;
  64      PHEAP_LOCK HeapCritSect;
  65      ULONG nRemoteLockAcquired;
  66
  67      PDPH_HEAP_BLOCK pVirtualStorageListHead;
  68      PDPH_HEAP_BLOCK pVirtualStorageListTail;
  69      ULONG nVirtualStorageRanges;
  70      SIZE_T nVirtualStorageBytes;
  71
  72      RTL_AVL_TABLE BusyNodesTable;
  73      PDPH_HEAP_BLOCK NodeToAllocate;
  74      ULONG nBusyAllocations;
  75      SIZE_T nBusyAllocationBytesCommitted;
  76
  77      PDPH_HEAP_BLOCK pFreeAllocationListHead;
  78      PDPH_HEAP_BLOCK pFreeAllocationListTail;
  79      ULONG nFreeAllocations;
  80      SIZE_T nFreeAllocationBytesCommitted;
  81
  82      LIST_ENTRY AvailableAllocationHead;
  83      ULONG nAvailableAllocations;
  84      SIZE_T nAvailableAllocationBytesCommitted;
  85
  86      PDPH_HEAP_BLOCK pUnusedNodeListHead;
  87      PDPH_HEAP_BLOCK pUnusedNodeListTail;
  88      ULONG nUnusedNodes;
  89      SIZE_T nBusyAllocationBytesAccessible;
  90      PDPH_HEAP_BLOCK pNodePoolListHead;
  91      PDPH_HEAP_BLOCK pNodePoolListTail;
  92      ULONG nNodePools;
  93      SIZE_T nNodePoolBytes;
  94
  95      LIST_ENTRY NextHeap;
  96      ULONG ExtraFlags;
  97      ULONG Seed;
  98      PVOID NormalHeap;
  99      PRTL_TRACE_BLOCK CreateStackTrace;
 100      PVOID FirstThread;
 101 } DPH_HEAP_ROOT, *PDPH_HEAP_ROOT;
 102
 103 /* GLOBALS ********************************************************************/
 104
 105 BOOLEAN RtlpPageHeapEnabled = FALSE;
 106 ULONG RtlpDphGlobalFlags;
 107 ULONG RtlpPageHeapSizeRangeStart, RtlpPageHeapSizeRangeEnd;
 108 ULONG RtlpPageHeapDllRangeStart, RtlpPageHeapDllRangeEnd;
 109 WCHAR RtlpDphTargetDlls[512];
 110
 111 LIST_ENTRY RtlpDphPageHeapList;
 112 BOOLEAN RtlpDphPageHeapListInitialized;
 113 HEAP_LOCK _RtlpDphPageHeapListLock;
 114 PHEAP_LOCK RtlpDphPageHeapListLock = &_RtlpDphPageHeapListLock;
 115 ULONG RtlpDphPageHeapListLength;
 116 UNICODE_STRING RtlpDphTargetDllsUnicode;
 117
 118 HEAP_LOCK _RtlpDphDelayedFreeQueueLock;
 119 PHEAP_LOCK RtlpDphDelayedFreeQueueLock = &_RtlpDphDelayedFreeQueueLock;
 120 LIST_ENTRY RtlpDphDelayedFreeQueue;
 121 SLIST_HEADER RtlpDphDelayedTemporaryPushList;
 122 SIZE_T RtlpDphMemoryUsedByDelayedFreeBlocks;
 123 ULONG RtlpDphNumberOfDelayedFreeBlocks;
 124
 125 /* Counters */
 126 LONG RtlpDphCounter;
 127 LONG RtlpDphAllocFails;
 128 LONG RtlpDphReleaseFails;
 129 LONG RtlpDphFreeFails;
 130 LONG RtlpDphProtectFails;
 131
 132 #define DPH_RESERVE_SIZE 0x100000
 133 #define DPH_POOL_SIZE 0x4000
 134 #define DPH_FREE_LIST_MINIMUM 8
 135
 136 /* RtlpDphBreakOptions */
 137 #define DPH_BREAK_ON_RESERVE_FAIL 0x01
 138 #define DPH_BREAK_ON_COMMIT_FAIL  0x02
 139 #define DPH_BREAK_ON_RELEASE_FAIL 0x04
 140 #define DPH_BREAK_ON_FREE_FAIL    0x08
 141 #define DPH_BREAK_ON_PROTECT_FAIL 0x10
 142 #define DPH_BREAK_ON_NULL_FREE    0x80
 143
 144 /* RtlpDphDebugOptions */
 145 #define DPH_DEBUG_INTERNAL_VALIDATE 0x01
 146 #define DPH_DEBUG_VERBOSE           0x04
 147
 148 /* DPH ExtraFlags */
 149 #define DPH_EXTRA_LOG_STACK_TRACES 0x02
 150 #define DPH_EXTRA_CHECK_UNDERRUN   0x10
 151
 152 /* Fillers */
 153 #define DPH_FILL 0xEEEEEEEE
 154 #define DPH_FILL_START_STAMP_1 0xABCDBBBB
 155 #define DPH_FILL_START_STAMP_2 0xABCDBBBA
 156 #define DPH_FILL_END_STAMP_1   0xDCBABBBB
 157 #define DPH_FILL_END_STAMP_2   0xDCBABBBA
 158 #define DPH_FILL_SUFFIX        0xD0
 159 #define DPH_FILL_INFIX         0xC0
 160
 161 /* Validation info flags */
 162 #define DPH_VALINFO_BAD_START_STAMP      0x01
 163 #define DPH_VALINFO_BAD_END_STAMP        0x02
 164 #define DPH_VALINFO_BAD_POINTER          0x04
 165 #define DPH_VALINFO_BAD_PREFIX_PATTERN   0x08
 166 #define DPH_VALINFO_BAD_SUFFIX_PATTERN   0x10
 167 #define DPH_VALINFO_EXCEPTION            0x20
 168 #define DPH_VALINFO_1                    0x40
 169 #define DPH_VALINFO_BAD_INFIX_PATTERN    0x80
 170 #define DPH_VALINFO_ALREADY_FREED        0x100
 171 #define DPH_VALINFO_CORRUPTED_AFTER_FREE 0x200
 172
 173 /* Signatures */
 174 #define DPH_SIGNATURE 0xFFEEDDCC
 175
 176 /* Biased pointer macros */
 177 #define IS_BIASED_POINTER(ptr) ((ULONG_PTR)(ptr) & 1)
 178 #define POINTER_REMOVE_BIAS(ptr) ((ULONG_PTR)(ptr) & ~(ULONG_PTR)1)
 179 #define POINTER_ADD_BIAS(ptr) ((ULONG_PTR)(ptr) | 1)
 180
 181
 182 ULONG RtlpDphBreakOptions = 0;//0xFFFFFFFF;
 183 ULONG RtlpDphDebugOptions;
 184
 185 /* FUNCTIONS ******************************************************************/
 186
 187 BOOLEAN NTAPI
 188 RtlpDphGrowVirtual(PDPH_HEAP_ROOT DphRoot, SIZE_T Size);
 189
 190 BOOLEAN NTAPI
 191 RtlpDphIsNormalFreeHeapBlock(PVOID Block, PULONG ValidationInformation, BOOLEAN CheckFillers);
 192
 193 VOID NTAPI
 194 RtlpDphReportCorruptedBlock(PDPH_HEAP_ROOT DphRoot, ULONG Reserved, PVOID Block, ULONG ValidationInfo);
 195
 196 BOOLEAN NTAPI
 197 RtlpDphNormalHeapValidate(PDPH_HEAP_ROOT DphRoot, ULONG Flags, PVOID BaseAddress);
 198
 199
 200 VOID NTAPI
 201 RtlpDphRaiseException(NTSTATUS Status)
 202 {
 203     EXCEPTION_RECORD Exception;
 204
 205     /* Initialize exception record */
 206     Exception.ExceptionCode = Status;
 207     Exception.ExceptionAddress = RtlpDphRaiseException;
 208     Exception.ExceptionFlags = 0;
 209     Exception.ExceptionRecord = NULL;
 210     Exception.NumberParameters = 0;
 211
 212     /* Raise the exception */
 213     RtlRaiseException(&Exception);
 214 }
 215
 216 PVOID NTAPI
 217 RtlpDphPointerFromHandle(PVOID Handle)
 218 {
 219     PHEAP NormalHeap = (PHEAP)Handle;
 220     PDPH_HEAP_ROOT DphHeap = (PDPH_HEAP_ROOT)((PUCHAR)Handle + PAGE_SIZE);
 221
 222     if (NormalHeap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS)
 223     {
 224         if (DphHeap->Signature == DPH_SIGNATURE)
 225             return DphHeap;
 226     }
 227
 228     DPRINT1("heap handle with incorrect signature\n");
 229     DbgBreakPoint();
 230     return NULL;
 231 }
 232
 233 VOID NTAPI
 234 RtlpDphEnterCriticalSection(PDPH_HEAP_ROOT DphRoot, ULONG Flags)
 235 {
 236     if (Flags & HEAP_NO_SERIALIZE)
 237     {
 238         /* More complex scenario */
 239         if (!RtlEnterHeapLock(DphRoot->HeapCritSect, TRUE))
 240         {
 241             if (!DphRoot->nRemoteLockAcquired)
 242             {
 243                 DPRINT1("multithreaded access in HEAP_NO_SERIALIZE heap\n");
 244                 DbgBreakPoint();
 245
 246                 /* Clear out the no serialize flag */
 247                 DphRoot->HeapFlags &= ~HEAP_NO_SERIALIZE;
 248             }
 249
 250             /* Enter the heap's critical section */
 251             RtlEnterHeapLock(DphRoot->HeapCritSect, TRUE);
 252         }
 253     }
 254     else
 255     {
 256         /* Just enter the heap's critical section */
 257         RtlEnterHeapLock(DphRoot->HeapCritSect, TRUE);
 258     }
 259 }
 260
 261 VOID NTAPI
 262 RtlpDphLeaveCriticalSection(PDPH_HEAP_ROOT DphRoot)
 263 {
 264     /* Just leave the heap's critical section */
 265     RtlLeaveHeapLock(DphRoot->HeapCritSect);
 266 }
 267
 268
 269 VOID NTAPI
 270 RtlpDphPreProcessing(PDPH_HEAP_ROOT DphRoot, ULONG Flags)
 271 {
 272     RtlpDphEnterCriticalSection(DphRoot, Flags);
 273
 274     /* FIXME: Validate integrity, internal lists if necessary */
 275 }
 276
 277 VOID NTAPI
 278 RtlpDphPostProcessing(PDPH_HEAP_ROOT DphRoot)
 279 {
 280     if (!DphRoot) return;
 281
 282     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
 283     {
 284         /* FIXME: Validate integrity, internal lists if necessary */
 285     }
 286
 287     /* Release the lock */
 288     RtlpDphLeaveCriticalSection(DphRoot);
 289 }
 290
 291 NTSTATUS NTAPI
 292 RtlpSecMemFreeVirtualMemory(HANDLE Process, PVOID *Base, PSIZE_T Size, ULONG Type)
 293 {
 294     NTSTATUS Status;
 295     //PVOID *SavedBase = Base;
 296     //PSIZE_T SavedSize = Size;
 297
 298     /* Free the memory */
 299     Status = ZwFreeVirtualMemory(Process, Base, Size, Type);
 300
 301     /* Flush secure memory cache if needed and retry freeing */
 302 #if 0
 303     if (Status == STATUS_INVALID_PAGE_PROTECTION &&
 304         Process == NtCurrentProcess() &&
 305         RtlFlushSecureMemoryCache(*SavedBase, *SavedSize))
 306     {
 307         Status = ZwFreeVirtualMemory(NtCurrentProcess(), SavedBase, SavedSize, Type);
 308     }
 309 #endif
 310
 311     return Status;
 312 }
 313
 314 NTSTATUS NTAPI
 315 RtlpDphAllocateVm(PVOID *Base, SIZE_T Size, ULONG Type, ULONG Protection)
 316 {
 317     NTSTATUS Status;
 318     Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 319                                      Base,
 320                                      0,
 321                                      &Size,
 322                                      Type,
 323                                      Protection);
 324     DPRINT("Page heap: AllocVm (%p, %Ix, %lx) status %lx \n", Base, Size, Type, Status);
 325     /* Check for failures */
 326     if (!NT_SUCCESS(Status))
 327     {
 328         if (Type == MEM_RESERVE)
 329         {
 330             _InterlockedIncrement(&RtlpDphCounter);
 331             if (RtlpDphBreakOptions & DPH_BREAK_ON_RESERVE_FAIL)
 332             {
 333                 DPRINT1("Page heap: AllocVm (%p, %Ix, %x) failed with %x \n", Base, Size, Type, Status);
 334                 DbgBreakPoint();
 335                 return Status;
 336             }
 337         }
 338         else
 339         {
 340             _InterlockedIncrement(&RtlpDphAllocFails);
 341             if (RtlpDphBreakOptions & DPH_BREAK_ON_COMMIT_FAIL)
 342             {
 343                 DPRINT1("Page heap: AllocVm (%p, %Ix, %x) failed with %x \n", Base, Size, Type, Status);
 344                 DbgBreakPoint();
 345                 return Status;
 346             }
 347         }
 348     }
 349
 350     return Status;
 351 }
 352
 353 NTSTATUS NTAPI
 354 RtlpDphFreeVm(PVOID Base, SIZE_T Size, ULONG Type)
 355 {
 356     NTSTATUS Status;
 357
 358     /* Free the memory */
 359     Status = RtlpSecMemFreeVirtualMemory(NtCurrentProcess(), &Base, &Size, Type);
 360     DPRINT1("Page heap: FreeVm (%p, %Ix, %x) status %x \n", Base, Size, Type, Status);
 361     /* Log/report failures */
 362     if (!NT_SUCCESS(Status))
 363     {
 364         if (Type == MEM_RELEASE)
 365         {
 366             _InterlockedIncrement(&RtlpDphReleaseFails);
 367             if (RtlpDphBreakOptions & DPH_BREAK_ON_RELEASE_FAIL)
 368             {
 369                 DPRINT1("Page heap: FreeVm (%p, %Ix, %x) failed with %x \n", Base, Size, Type, Status);
 370                 DbgBreakPoint();
 371                 return Status;
 372             }
 373         }
 374         else
 375         {
 376             _InterlockedIncrement(&RtlpDphFreeFails);
 377             if (RtlpDphBreakOptions & DPH_BREAK_ON_FREE_FAIL)
 378             {
 379                 DPRINT1("Page heap: FreeVm (%p, %Ix, %x) failed with %x \n", Base, Size, Type, Status);
 380                 DbgBreakPoint();
 381                 return Status;
 382             }
 383         }
 384     }
 385
 386     return Status;
 387 }
 388
 389 NTSTATUS NTAPI
 390 RtlpDphProtectVm(PVOID Base, SIZE_T Size, ULONG Protection)
 391 {
 392     NTSTATUS Status;
 393     ULONG OldProtection;
 394
 395     /* Change protection */
 396     Status = ZwProtectVirtualMemory(NtCurrentProcess(), &Base, &Size, Protection, &OldProtection);
 397
 398     /* Log/report failures */
 399     if (!NT_SUCCESS(Status))
 400     {
 401         _InterlockedIncrement(&RtlpDphProtectFails);
 402         if (RtlpDphBreakOptions & DPH_BREAK_ON_PROTECT_FAIL)
 403         {
 404             DPRINT1("Page heap: ProtectVm (%p, %Ix, %x) failed with %x \n", Base, Size, Protection, Status);
 405             DbgBreakPoint();
 406             return Status;
 407         }
 408     }
 409
 410     return Status;
 411 }
 412
 413 BOOLEAN NTAPI
 414 RtlpDphWritePageHeapBlockInformation(PDPH_HEAP_ROOT DphRoot, PVOID UserAllocation, SIZE_T Size, SIZE_T UserSize)
 415 {
 416     PDPH_BLOCK_INFORMATION BlockInfo;
 417     PUCHAR FillPtr;
 418
 419     /* Get pointer to the block info structure */
 420     BlockInfo = (PDPH_BLOCK_INFORMATION)UserAllocation - 1;
 421
 422     /* Set up basic fields */
 423     BlockInfo->Heap = DphRoot;
 424     BlockInfo->ActualSize = UserSize;
 425     BlockInfo->RequestedSize = Size;
 426     BlockInfo->StartStamp = DPH_FILL_START_STAMP_1;
 427     BlockInfo->EndStamp = DPH_FILL_END_STAMP_1;
 428
 429     /* Fill with a pattern */
 430     FillPtr = (PUCHAR)UserAllocation + Size;
 431     RtlFillMemory(FillPtr, ROUND_UP(FillPtr, PAGE_SIZE) - (ULONG_PTR)FillPtr, DPH_FILL_SUFFIX);
 432
 433     /* FIXME: Check if logging stack traces is turned on */
 434     //if (DphRoot->ExtraFlags &
 435
 436     return TRUE;
 437 }
 438
 439 VOID NTAPI
 440 RtlpDphPlaceOnBusyList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK DphNode)
 441 {
 442     BOOLEAN NewElement;
 443     PVOID AddressUserData;
 444
 445     DPRINT("RtlpDphPlaceOnBusyList(%p %p)\n", DphRoot, DphNode);
 446
 447     /* Add it to the AVL busy nodes table */
 448     DphRoot->NodeToAllocate = DphNode;
 449     AddressUserData = RtlInsertElementGenericTableAvl(&DphRoot->BusyNodesTable,
 450                                                       &DphNode->pUserAllocation,
 451                                                       sizeof(ULONG_PTR),
 452                                                       &NewElement);
 453
 454     ASSERT(AddressUserData == &DphNode->pUserAllocation);
 455     ASSERT(NewElement == TRUE);
 456
 457     /* Update heap counters */
 458     DphRoot->nBusyAllocations++;
 459     DphRoot->nBusyAllocationBytesAccessible += DphNode->nVirtualAccessSize;
 460     DphRoot->nBusyAllocationBytesCommitted += DphNode->nVirtualBlockSize;
 461 }
 462
 463 VOID NTAPI
 464 RtlpDphPlaceOnFreeList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
 465 {
 466     DPRINT("RtlpDphPlaceOnFreeList(%p %p)\n", DphRoot, Node);
 467
 468     /* Node is being added to the tail of the list */
 469     Node->pNextAlloc = NULL;
 470
 471     /* Add it to the tail of the linked list */
 472     if (DphRoot->pFreeAllocationListTail)
 473         DphRoot->pFreeAllocationListTail->pNextAlloc = Node;
 474     else
 475         DphRoot->pFreeAllocationListHead = Node;
 476     DphRoot->pFreeAllocationListTail = Node;
 477
 478     /* Update byte counts taking in account this new node */
 479     DphRoot->nFreeAllocations++;
 480     DphRoot->nFreeAllocationBytesCommitted += Node->nVirtualBlockSize;
 481 }
 482
 483 VOID NTAPI
 484 RtlpDphPlaceOnPoolList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
 485 {
 486     DPRINT("RtlpDphPlaceOnPoolList(%p %p)\n", DphRoot, Node);
 487
 488     /* Node is being added to the tail of the list */
 489     Node->pNextAlloc = NULL;
 490
 491     /* Add it to the tail of the linked list */
 492     if (DphRoot->pNodePoolListTail)
 493         DphRoot->pNodePoolListTail->pNextAlloc = Node;
 494     else
 495         DphRoot->pNodePoolListHead = Node;
 496     DphRoot->pNodePoolListTail = Node;
 497
 498     /* Update byte counts taking in account this new node */
 499     DphRoot->nNodePools++;
 500     DphRoot->nNodePoolBytes += Node->nVirtualBlockSize;
 501 }
 502
 503 VOID NTAPI
 504 RtlpDphPlaceOnVirtualList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
 505 {
 506     DPRINT("RtlpDphPlaceOnVirtualList(%p %p)\n", DphRoot, Node);
 507
 508     /* Add it to the head of the virtual list */
 509     Node->pNextAlloc = DphRoot->pVirtualStorageListHead;
 510     if (!DphRoot->pVirtualStorageListHead)
 511         DphRoot->pVirtualStorageListTail = Node;
 512     DphRoot->pVirtualStorageListHead = Node;
 513
 514     /* Update byte counts taking in account this new node */
 515     DphRoot->nVirtualStorageRanges++;
 516     DphRoot->nVirtualStorageBytes += Node->nVirtualBlockSize;
 517 }
 518
 519 PDPH_HEAP_BLOCK NTAPI
 520 RtlpDphTakeNodeFromUnusedList(PDPH_HEAP_ROOT DphRoot)
 521 {
 522     PDPH_HEAP_BLOCK Node = DphRoot->pUnusedNodeListHead;
 523     PDPH_HEAP_BLOCK Next;
 524
 525     DPRINT("RtlpDphTakeNodeFromUnusedList(%p), ret %p\n", DphRoot, Node);
 526
 527     /* Take the first entry */
 528     if (!Node) return NULL;
 529
 530     /* Remove that entry (Node) from the list */
 531     Next = Node->pNextAlloc;
 532     if (DphRoot->pUnusedNodeListHead == Node) DphRoot->pUnusedNodeListHead = Next;
 533     if (DphRoot->pUnusedNodeListTail == Node) DphRoot->pUnusedNodeListTail = NULL;
 534
 535     /* Decrease amount of unused nodes */
 536     DphRoot->nUnusedNodes--;
 537
 538     return Node;
 539 }
 540
 541 VOID NTAPI
 542 RtlpDphReturnNodeToUnusedList(PDPH_HEAP_ROOT DphRoot,
 543                               PDPH_HEAP_BLOCK Node)
 544 {
 545     DPRINT("RtlpDphReturnNodeToUnusedList(%p, %p)\n", DphRoot, Node);
 546
 547     /* Add it back to the head of the unused list */
 548     Node->pNextAlloc = DphRoot->pUnusedNodeListHead;
 549     if (!DphRoot->pUnusedNodeListHead)
 550         DphRoot->pUnusedNodeListTail = Node;
 551     DphRoot->pUnusedNodeListHead = Node;
 552
 553     /* Increase amount of unused nodes */
 554     DphRoot->nUnusedNodes++;
 555 }
 556
 557 VOID NTAPI
 558 RtlpDphRemoveFromAvailableList(PDPH_HEAP_ROOT DphRoot,
 559                                PDPH_HEAP_BLOCK Node)
 560 {
 561     /* Make sure Adjacency list pointers are biased */
 562     //ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Flink));
 563     //ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Blink));
 564
 565     DPRINT("RtlpDphRemoveFromAvailableList(%p %p)\n", DphRoot, Node);
 566
 567     /* Check if it is in the list */
 568 #if 0
 569     {
 570         PLIST_ENTRY CurEntry;
 571         PDPH_HEAP_BLOCK NodeEntry;
 572         BOOLEAN Found = FALSE;
 573
 574         /* Find where to put this node according to its virtual address */
 575         CurEntry = DphRoot->AvailableAllocationHead.Flink;
 576
 577         while (CurEntry != &DphRoot->AvailableAllocationHead)
 578         {
 579             NodeEntry = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
 580
 581             if (NodeEntry == Node)
 582             {
 583                 Found = TRUE;
 584                 break;
 585             }
 586
 587             CurEntry = CurEntry->Flink;
 588         }
 589
 590         if (!Found)
 591         {
 592             DPRINT1("Trying to remove non-existing in availlist node!\n");
 593             DbgBreakPoint();
 594         }
 595     }
 596 #endif
 597
 598     /* Remove it from the list */
 599     RemoveEntryList(&Node->AvailableEntry);
 600
 601     /* Decrease heap counters */
 602     DphRoot->nAvailableAllocations--;
 603     DphRoot->nAvailableAllocationBytesCommitted -= Node->nVirtualBlockSize;
 604
 605     /* Remove bias from the AdjacencyEntry pointer */
 606     Node->AdjacencyEntry.Flink = (PLIST_ENTRY)POINTER_REMOVE_BIAS(Node->AdjacencyEntry.Flink);
 607     Node->AdjacencyEntry.Blink = (PLIST_ENTRY)POINTER_REMOVE_BIAS(Node->AdjacencyEntry.Blink);
 608 }
 609
 610 VOID NTAPI
 611 RtlpDphRemoveFromBusyList(PDPH_HEAP_ROOT DphRoot,
 612                           PDPH_HEAP_BLOCK Node)
 613 {
 614     BOOLEAN ElementPresent;
 615
 616     DPRINT("RtlpDphRemoveFromBusyList(%p %p)\n", DphRoot, Node);
 617
 618     /* Delete it from busy nodes table */
 619     ElementPresent = RtlDeleteElementGenericTableAvl(&DphRoot->BusyNodesTable, &Node->pUserAllocation);
 620     ASSERT(ElementPresent == TRUE);
 621
 622     /* Update counters */
 623     DphRoot->nBusyAllocations--;
 624     DphRoot->nBusyAllocationBytesCommitted -= Node->nVirtualBlockSize;
 625     DphRoot->nBusyAllocationBytesAccessible -= Node->nVirtualAccessSize;
 626 }
 627
 628 VOID NTAPI
 629 RtlpDphRemoveFromFreeList(PDPH_HEAP_ROOT DphRoot,
 630                           PDPH_HEAP_BLOCK Node,
 631                           PDPH_HEAP_BLOCK Prev)
 632 {
 633     PDPH_HEAP_BLOCK Next;
 634
 635     DPRINT("RtlpDphRemoveFromFreeList(%p %p %p)\n", DphRoot, Node, Prev);
 636
 637     /* Detach it from the list */
 638     Next = Node->pNextAlloc;
 639     if (DphRoot->pFreeAllocationListHead == Node)
 640         DphRoot->pFreeAllocationListHead = Next;
 641     if (DphRoot->pFreeAllocationListTail == Node)
 642         DphRoot->pFreeAllocationListTail = Prev;
 643     if (Prev) Prev->pNextAlloc = Next;
 644
 645     /* Decrease heap counters */
 646     DphRoot->nFreeAllocations--;
 647     DphRoot->nFreeAllocationBytesCommitted -= Node->nVirtualBlockSize;
 648
 649     Node->StackTrace = NULL;
 650 }
 651
 652 VOID NTAPI
 653 RtlpDphCoalesceNodeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
 654                                  PDPH_HEAP_BLOCK Node)
 655 {
 656     PDPH_HEAP_BLOCK NodeEntry, PrevNode = NULL, NextNode;
 657     PLIST_ENTRY AvailListHead;
 658     PLIST_ENTRY CurEntry;
 659
 660     DPRINT("RtlpDphCoalesceNodeIntoAvailable(%p %p)\n", DphRoot, Node);
 661
 662     /* Update heap counters */
 663     DphRoot->nAvailableAllocationBytesCommitted += Node->nVirtualBlockSize;
 664     DphRoot->nAvailableAllocations++;
 665
 666     /* Find where to put this node according to its virtual address */
 667     AvailListHead = &DphRoot->AvailableAllocationHead;
 668
 669     /* Find a point where to insert an available node */
 670     CurEntry = AvailListHead->Flink;
 671
 672     while (CurEntry != AvailListHead)
 673     {
 674         NodeEntry = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
 675         if (NodeEntry->pVirtualBlock >= Node->pVirtualBlock)
 676         {
 677             PrevNode = NodeEntry;
 678             break;
 679         }
 680         CurEntry = CurEntry->Flink;
 681     }
 682
 683     if (!PrevNode)
 684     {
 685         /* That means either this list is empty, or we should add to the head of it */
 686         InsertHeadList(AvailListHead, &Node->AvailableEntry);
 687     }
 688     else
 689     {
 690         /* Check the previous node and merge if possible */
 691         if (PrevNode->pVirtualBlock + PrevNode->nVirtualBlockSize == Node->pVirtualBlock)
 692         {
 693             /* They are adjacent - merge! */
 694             PrevNode->nVirtualBlockSize += Node->nVirtualBlockSize;
 695             RtlpDphReturnNodeToUnusedList(DphRoot, Node);
 696             DphRoot->nAvailableAllocations--;
 697
 698             Node = PrevNode;
 699         }
 700         else
 701         {
 702             /* Insert after PrevNode */
 703             InsertTailList(&PrevNode->AvailableEntry, &Node->AvailableEntry);
 704         }
 705
 706         /* Now check the next entry after our one */
 707         if (Node->AvailableEntry.Flink != AvailListHead)
 708         {
 709             NextNode = CONTAINING_RECORD(Node->AvailableEntry.Flink, DPH_HEAP_BLOCK, AvailableEntry);
 710             /* Node is not at the tail of the list, check if it's adjacent */
 711             if (Node->pVirtualBlock + Node->nVirtualBlockSize == NextNode->pVirtualBlock)
 712             {
 713                 /* They are adjacent - merge! */
 714                 Node->nVirtualBlockSize += NextNode->nVirtualBlockSize;
 715
 716                 /* Remove next entry from the list and put it into unused entries list */
 717                 RemoveEntryList(&NextNode->AvailableEntry);
 718                 RtlpDphReturnNodeToUnusedList(DphRoot, NextNode);
 719                 DphRoot->nAvailableAllocations--;
 720             }
 721         }
 722     }
 723 }
 724
 725 VOID NTAPI
 726 RtlpDphCoalesceFreeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
 727                                  ULONG LeaveOnFreeList)
 728 {
 729     PDPH_HEAP_BLOCK Node = DphRoot->pFreeAllocationListHead, Next;
 730     SIZE_T FreeAllocations = DphRoot->nFreeAllocations;
 731
 732     /* Make sure requested size is not too big */
 733     ASSERT(FreeAllocations >= LeaveOnFreeList);
 734
 735     DPRINT("RtlpDphCoalesceFreeIntoAvailable(%p %lu)\n", DphRoot, LeaveOnFreeList);
 736
 737     while (Node)
 738     {
 739         FreeAllocations--;
 740         if (FreeAllocations < LeaveOnFreeList) break;
 741
 742         /* Get the next pointer, because it may be changed after following two calls */
 743         Next = Node->pNextAlloc;
 744
 745         /* Remove it from the free list */
 746         RtlpDphRemoveFromFreeList(DphRoot, Node, NULL);
 747
 748         /* And put into the available */
 749         RtlpDphCoalesceNodeIntoAvailable(DphRoot, Node);
 750
 751         /* Go to the next node */
 752         Node = Next;
 753     }
 754 }
 755
 756 VOID NTAPI
 757 RtlpDphAddNewPool(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK NodeBlock, PVOID Virtual, SIZE_T Size, BOOLEAN PlaceOnPool)
 758 {
 759     PDPH_HEAP_BLOCK DphNode, DphStartNode;
 760     ULONG NodeCount, i;
 761
 762     //NodeCount = (Size >> 6) - 1;
 763     NodeCount = (ULONG)(Size / sizeof(DPH_HEAP_BLOCK));
 764     DphStartNode = Virtual;
 765
 766     /* Set pNextAlloc for all blocks */
 767     for (DphNode = Virtual, i=NodeCount-1; i > 0; i--)
 768     {
 769         DphNode->pNextAlloc = DphNode + 1;
 770         DphNode = DphNode->pNextAlloc;
 771     }
 772
 773     /* and the last one */
 774     DphNode->pNextAlloc = NULL;
 775
 776     /* Add it to the tail of unused node list */
 777     if (DphRoot->pUnusedNodeListTail)
 778         DphRoot->pUnusedNodeListTail->pNextAlloc = DphStartNode;
 779     else
 780         DphRoot->pUnusedNodeListHead = DphStartNode;
 781
 782     DphRoot->pUnusedNodeListTail = DphNode;
 783
 784     /* Increase counters */
 785     DphRoot->nUnusedNodes += NodeCount;
 786
 787     /* Check if we need to place it on the pool list */
 788     if (PlaceOnPool)
 789     {
 790         /* Get a node from the unused list */
 791         DphNode = RtlpDphTakeNodeFromUnusedList(DphRoot);
 792         ASSERT(DphNode);
 793
 794         /* Set its virtual block values */
 795         DphNode->pVirtualBlock = Virtual;
 796         DphNode->nVirtualBlockSize = Size;
 797
 798         /* Place it on the pool list */
 799         RtlpDphPlaceOnPoolList(DphRoot, DphNode);
 800     }
 801 }
 802
 803 PDPH_HEAP_BLOCK NTAPI
 804 RtlpDphSearchAvailableMemoryListForBestFit(PDPH_HEAP_ROOT DphRoot,
 805                                            SIZE_T Size)
 806 {
 807     PLIST_ENTRY CurEntry;
 808     PDPH_HEAP_BLOCK Node, NodeFound = NULL;
 809
 810     CurEntry = DphRoot->AvailableAllocationHead.Flink;
 811
 812     while (CurEntry != &DphRoot->AvailableAllocationHead)
 813     {
 814         /* Get the current available node */
 815         Node = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
 816
 817         /* Check its size */
 818         if (Node->nVirtualBlockSize >= Size)
 819         {
 820             NodeFound = Node;
 821             break;
 822         }
 823
 824         /* Move to the next available entry */
 825         CurEntry = CurEntry->Flink;
 826     }
 827
 828     /* Make sure Adjacency list pointers are biased */
 829     //ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Flink));
 830     //ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Blink));
 831
 832     return NodeFound;
 833 }
 834
 835 PDPH_HEAP_BLOCK NTAPI
 836 RtlpDphFindAvailableMemory(PDPH_HEAP_ROOT DphRoot,
 837                            SIZE_T Size,
 838                            BOOLEAN Grow)
 839 {
 840     PDPH_HEAP_BLOCK Node;
 841     ULONG NewSize;
 842
 843     /* Find an available best fitting node */
 844     Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
 845
 846     /* If that didn't work, try to search a smaller one in the loop */
 847     while (!Node)
 848     {
 849         /* Break if the free list becomes too small */
 850         if (DphRoot->nFreeAllocations <= DPH_FREE_LIST_MINIMUM) break;
 851
 852         /* Calculate a new free list size */
 853         NewSize = DphRoot->nFreeAllocations >> 2;
 854         if (NewSize < DPH_FREE_LIST_MINIMUM) NewSize = DPH_FREE_LIST_MINIMUM;
 855
 856         /* Coalesce free into available */
 857         RtlpDphCoalesceFreeIntoAvailable(DphRoot, NewSize);
 858
 859         /* Try to find an available best fitting node again */
 860         Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
 861     }
 862
 863     /* If Node is NULL, then we could fix the situation only by
 864        growing the available VM size */
 865     if (!Node && Grow)
 866     {
 867         /* Grow VM size, if it fails - return failure directly */
 868         if (!RtlpDphGrowVirtual(DphRoot, Size)) return NULL;
 869
 870         /* Try to find an available best fitting node again */
 871         Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
 872
 873         if (!Node)
 874         {
 875             /* Do the last attempt: coalesce all free into available (if Size fits there) */
 876             if (DphRoot->nFreeAllocationBytesCommitted + DphRoot->nAvailableAllocationBytesCommitted >= Size)
 877             {
 878                 /* Coalesce free into available */
 879                 RtlpDphCoalesceFreeIntoAvailable(DphRoot, 0);
 880
 881                 /* Try to find an available best fitting node again */
 882                 Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
 883             }
 884         }
 885     }
 886
 887     /* Return node we found */
 888     return Node;
 889 }
 890
 891 PDPH_HEAP_BLOCK NTAPI
 892 RtlpDphFindBusyMemory(PDPH_HEAP_ROOT DphRoot,
 893                       PVOID pUserMem)
 894 {
 895     PDPH_HEAP_BLOCK Node;
 896     PVOID Ptr;
 897
 898     /* Lookup busy block in AVL */
 899     Ptr = RtlLookupElementGenericTableAvl(&DphRoot->BusyNodesTable, &pUserMem);
 900     if (!Ptr) return NULL;
 901
 902     /* Restore pointer to the heap block */
 903     Node = CONTAINING_RECORD(Ptr, DPH_HEAP_BLOCK, pUserAllocation);
 904     ASSERT(Node->pUserAllocation == pUserMem);
 905     return Node;
 906 }
 907
 908 NTSTATUS NTAPI
 909 RtlpDphSetProtectionBeforeUse(PDPH_HEAP_ROOT DphRoot, PUCHAR VirtualBlock, ULONG UserSize)
 910 {
 911     ULONG Protection;
 912     PVOID Base;
 913
 914     if (DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)
 915     {
 916         Base = VirtualBlock + PAGE_SIZE;
 917     }
 918     else
 919     {
 920         Base = VirtualBlock;
 921     }
 922
 923     // FIXME: It should be different, but for now it's fine
 924     Protection = PAGE_READWRITE;
 925
 926     return RtlpDphProtectVm(Base, UserSize, Protection);
 927 }
 928
 929 NTSTATUS NTAPI
 930 RtlpDphSetProtectionAfterUse(PDPH_HEAP_ROOT DphRoot, /*PUCHAR VirtualBlock*/PDPH_HEAP_BLOCK Node)
 931 {
 932     ASSERT((Node->nVirtualAccessSize + PAGE_SIZE) <= Node->nVirtualBlockSize);
 933
 934     // FIXME: Bring stuff here
 935     if (DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)
 936     {
 937     }
 938     else
 939     {
 940     }
 941
 942     return STATUS_SUCCESS;
 943 }
 944
 945 PDPH_HEAP_BLOCK NTAPI
 946 RtlpDphAllocateNode(PDPH_HEAP_ROOT DphRoot)
 947 {
 948     PDPH_HEAP_BLOCK Node;
 949     NTSTATUS Status;
 950     SIZE_T Size = DPH_POOL_SIZE, SizeVirtual;
 951     PVOID Ptr = NULL;
 952
 953     /* Check for the easy case */
 954     if (DphRoot->pUnusedNodeListHead)
 955     {
 956         /* Just take a node from this list */
 957         Node = RtlpDphTakeNodeFromUnusedList(DphRoot);
 958         ASSERT(Node);
 959         return Node;
 960     }
 961
 962     /* There is a need to make free space */
 963     Node = RtlpDphFindAvailableMemory(DphRoot, DPH_POOL_SIZE, FALSE);
 964
 965     if (!DphRoot->pUnusedNodeListHead && !Node)
 966     {
 967         /* Retry with a smaller request */
 968         Size = PAGE_SIZE;
 969         Node = RtlpDphFindAvailableMemory(DphRoot, PAGE_SIZE, FALSE);
 970     }
 971
 972     if (!DphRoot->pUnusedNodeListHead)
 973     {
 974         if (Node)
 975         {
 976             RtlpDphRemoveFromAvailableList(DphRoot, Node);
 977             Ptr = Node->pVirtualBlock;
 978             SizeVirtual = Node->nVirtualBlockSize;
 979         }
 980         else
 981         {
 982             /* No free space, need to alloc a new VM block */
 983             Size = DPH_POOL_SIZE;
 984             SizeVirtual = DPH_RESERVE_SIZE;
 985             Status = RtlpDphAllocateVm(&Ptr, SizeVirtual, MEM_COMMIT, PAGE_NOACCESS);
 986
 987             if (!NT_SUCCESS(Status))
 988             {
 989                 /* Retry with a smaller size */
 990                 SizeVirtual = 0x10000;
 991                 Status = RtlpDphAllocateVm(&Ptr, SizeVirtual, MEM_COMMIT, PAGE_NOACCESS);
 992                 if (!NT_SUCCESS(Status)) return NULL;
 993             }
 994         }
 995
 996         /* VM is allocated at this point, set protection */
 997         Status = RtlpDphProtectVm(Ptr, Size, PAGE_READWRITE);
 998         if (!NT_SUCCESS(Status))
 999         {
1000             if (Node)
1001             {
1002                 RtlpDphCoalesceNodeIntoAvailable(DphRoot, Node);
1003             }
1004             else
1005             {
1006                 //RtlpDphFreeVm();
1007                 ASSERT(FALSE);
1008             }
1009
1010             return NULL;
1011         }
1012
1013         /* Zero the memory */
1014         if (Node) RtlZeroMemory(Ptr, Size);
1015
1016         /* Add a new pool based on this VM */
1017         RtlpDphAddNewPool(DphRoot, Node, Ptr, Size, TRUE);
1018
1019         if (Node)
1020         {
1021             if (Node->nVirtualBlockSize > Size)
1022             {
1023                 Node->pVirtualBlock += Size;
1024                 Node->nVirtualBlockSize -= Size;
1025
1026                 RtlpDphCoalesceNodeIntoAvailable(DphRoot, Node);
1027             }
1028             else
1029             {
1030                 RtlpDphReturnNodeToUnusedList(DphRoot, Node);
1031             }
1032         }
1033         else
1034         {
1035             /* The new VM block was just allocated a few code lines ago,
1036                so initialize it */
1037             Node = RtlpDphTakeNodeFromUnusedList(DphRoot);
1038             Node->pVirtualBlock = Ptr;
1039             Node->nVirtualBlockSize = SizeVirtual;
1040             RtlpDphPlaceOnVirtualList(DphRoot, Node);
1041
1042             Node = RtlpDphTakeNodeFromUnusedList(DphRoot);
1043             Node->pVirtualBlock = (PUCHAR)Ptr + Size;
1044             Node->nVirtualBlockSize = SizeVirtual - Size;
1045             RtlpDphPlaceOnVirtualList(DphRoot, Node);
1046
1047             /* Coalesce them into available list */
1048             RtlpDphCoalesceNodeIntoAvailable(DphRoot, Node);
1049         }
1050     }
1051
1052     return RtlpDphTakeNodeFromUnusedList(DphRoot);
1053 }
1054
1055 BOOLEAN NTAPI
1056 RtlpDphGrowVirtual(PDPH_HEAP_ROOT DphRoot,
1057                    SIZE_T Size)
1058 {
1059     PDPH_HEAP_BLOCK Node, AvailableNode;
1060     PVOID Base = NULL;
1061     SIZE_T VirtualSize;
1062     NTSTATUS Status;
1063
1064     /* Start with allocating a couple of nodes */
1065     Node = RtlpDphAllocateNode(DphRoot);
1066     if (!Node) return FALSE;
1067
1068     AvailableNode = RtlpDphAllocateNode(DphRoot);
1069     if (!AvailableNode)
1070     {
1071         /* Free the allocated node and return failure */
1072         RtlpDphReturnNodeToUnusedList(DphRoot, Node);
1073         return FALSE;
1074     }
1075
1076     /* Calculate size of VM to allocate by rounding it up */
1077     Size = ROUND_UP(Size, 0xFFFF);
1078     VirtualSize = Size;
1079     if (Size < DPH_RESERVE_SIZE)
1080         VirtualSize = DPH_RESERVE_SIZE;
1081
1082     /* Allocate the virtual memory */
1083     // FIXME: Shouldn't it be MEM_RESERVE with later committing?
1084     Status = RtlpDphAllocateVm(&Base, VirtualSize, MEM_COMMIT, PAGE_NOACCESS);
1085     if (!NT_SUCCESS(Status))
1086     {
1087         /* Retry again with a smaller size */
1088         VirtualSize = Size;
1089         Status = RtlpDphAllocateVm(&Base, VirtualSize, MEM_COMMIT, PAGE_NOACCESS);
1090         if (!NT_SUCCESS(Status))
1091         {
1092             /* Free the allocated node and return failure */
1093             RtlpDphReturnNodeToUnusedList(DphRoot, Node);
1094             RtlpDphReturnNodeToUnusedList(DphRoot, AvailableNode);
1095             return FALSE;
1096         }
1097     }
1098
1099     /* Set up our two nodes describing this VM */
1100     Node->pVirtualBlock = Base;
1101     Node->nVirtualBlockSize = VirtualSize;
1102     AvailableNode->pVirtualBlock = Base;
1103     AvailableNode->nVirtualBlockSize = VirtualSize;
1104
1105     /* Add them to virtual and available lists respectively */
1106     RtlpDphPlaceOnVirtualList(DphRoot, Node);
1107     RtlpDphCoalesceNodeIntoAvailable(DphRoot, AvailableNode);
1108
1109     /* Return success */
1110     return TRUE;
1111 }
1112
1113 RTL_GENERIC_COMPARE_RESULTS
1114 NTAPI
1115 RtlpDphCompareNodeForTable(IN PRTL_AVL_TABLE Table,
1116                            IN PVOID FirstStruct,
1117                            IN PVOID SecondStruct)
1118 {
1119     ULONG_PTR FirstBlock, SecondBlock;
1120
1121     FirstBlock = *((ULONG_PTR *)FirstStruct);
1122     SecondBlock = *((ULONG_PTR *)SecondStruct);
1123
1124     if (FirstBlock < SecondBlock)
1125         return GenericLessThan;
1126     else if (FirstBlock > SecondBlock)
1127         return GenericGreaterThan;
1128
1129     return GenericEqual;
1130 }
1131
1132 PVOID
1133 NTAPI
1134 RtlpDphAllocateNodeForTable(IN PRTL_AVL_TABLE Table,
1135                             IN CLONG ByteSize)
1136 {
1137     PDPH_HEAP_BLOCK pBlock;
1138     PDPH_HEAP_ROOT DphRoot;
1139
1140     /* This mega-assert comes from a text search over Windows 2003 checked binary of ntdll.dll */
1141     ASSERT((ULONG_PTR)(((PRTL_BALANCED_LINKS)0)+1) + sizeof(PUCHAR) == ByteSize);
1142
1143     /* Get pointer to the containing heap root record */
1144     DphRoot = CONTAINING_RECORD(Table, DPH_HEAP_ROOT, BusyNodesTable);
1145     pBlock = DphRoot->NodeToAllocate;
1146
1147     DphRoot->NodeToAllocate = NULL;
1148     ASSERT(pBlock);
1149
1150     return &(pBlock->TableLinks);
1151 }
1152
1153 VOID
1154 NTAPI
1155 RtlpDphFreeNodeForTable(IN PRTL_AVL_TABLE Table,
1156                         IN PVOID Buffer)
1157 {
1158     /* Nothing */
1159 }
1160
1161 NTSTATUS NTAPI
1162 RtlpDphInitializeDelayedFreeQueue()
1163 {
1164     NTSTATUS Status;
1165
1166     Status = RtlInitializeHeapLock(&RtlpDphDelayedFreeQueueLock);
1167     if (!NT_SUCCESS(Status))
1168     {
1169         // TODO: Log this error!
1170         DPRINT1("Failure initializing delayed free queue critical section\n");
1171         return Status;
1172     }
1173
1174     /* Initialize lists */
1175     InitializeListHead(&RtlpDphDelayedFreeQueue);
1176     RtlInitializeSListHead(&RtlpDphDelayedTemporaryPushList);
1177
1178     /* Reset counters */
1179     RtlpDphMemoryUsedByDelayedFreeBlocks = 0;
1180     RtlpDphNumberOfDelayedFreeBlocks = 0;
1181
1182     return Status;
1183 }
1184
1185 VOID NTAPI
1186 RtlpDphFreeDelayedBlocksFromHeap(PDPH_HEAP_ROOT DphRoot,
1187                                  PHEAP NormalHeap)
1188 {
1189     PLIST_ENTRY Current, Next;
1190     PDPH_BLOCK_INFORMATION BlockInfo;
1191     ULONG ValidationInfo;
1192
1193     /* The original routine seems to use a temporary SList to put blocks to be freed,
1194        then it releases the lock and frees the blocks. But let's make it simple for now */
1195
1196     /* Acquire the delayed free queue lock */
1197     RtlEnterHeapLock(RtlpDphDelayedFreeQueueLock, TRUE);
1198
1199     /* Traverse the list */
1200     Current = RtlpDphDelayedFreeQueue.Flink;
1201     while (Current != &RtlpDphDelayedFreeQueue)
1202     {
1203         /* Get the next entry pointer */
1204         Next = Current->Flink;
1205
1206         BlockInfo = CONTAINING_RECORD(Current, DPH_BLOCK_INFORMATION, FreeQueue);
1207
1208         /* Check if it belongs to the same heap */
1209         if (BlockInfo->Heap == DphRoot)
1210         {
1211             /* Remove it from the list */
1212             RemoveEntryList(Current);
1213
1214             /* Reset its heap to NULL */
1215             BlockInfo->Heap = NULL;
1216
1217             if (!RtlpDphIsNormalFreeHeapBlock(BlockInfo + 1, &ValidationInfo, TRUE))
1218             {
1219                 RtlpDphReportCorruptedBlock(DphRoot, 10, BlockInfo + 1, ValidationInfo);
1220             }
1221
1222             /* Decrement counters */
1223             RtlpDphMemoryUsedByDelayedFreeBlocks -= BlockInfo->ActualSize;
1224             RtlpDphNumberOfDelayedFreeBlocks--;
1225
1226             /* Free the normal heap */
1227             RtlFreeHeap (NormalHeap, 0, BlockInfo);
1228         }
1229
1230         /* Move to the next one */
1231         Current = Next;
1232     }
1233
1234     /* Release the delayed free queue lock */
1235     RtlLeaveHeapLock(RtlpDphDelayedFreeQueueLock);
1236 }
1237
1238 NTSTATUS NTAPI
1239 RtlpDphTargetDllsLogicInitialize()
1240 {
1241     UNIMPLEMENTED;
1242     return STATUS_SUCCESS;
1243 }
1244
1245 VOID NTAPI
1246 RtlpDphInternalValidatePageHeap(PDPH_HEAP_ROOT DphRoot, PVOID Address, ULONG Value)
1247 {
1248     UNIMPLEMENTED;
1249 }
1250
1251 VOID NTAPI
1252 RtlpDphVerifyIntegrity(PDPH_HEAP_ROOT DphRoot)
1253 {
1254     UNIMPLEMENTED;
1255 }
1256
1257 VOID NTAPI
1258 RtlpDphReportCorruptedBlock(PDPH_HEAP_ROOT DphRoot,
1259                             ULONG Reserved,
1260                             PVOID Block,
1261                             ULONG ValidationInfo)
1262 {
1263     //RtlpDphGetBlockSizeFromCorruptedBlock();
1264
1265     if (ValidationInfo & DPH_VALINFO_CORRUPTED_AFTER_FREE)
1266     {
1267         DPRINT1("block corrupted after having been freed\n");
1268     }
1269
1270     if (ValidationInfo & DPH_VALINFO_ALREADY_FREED)
1271     {
1272         DPRINT1("block already freed\n");
1273     }
1274
1275     if (ValidationInfo & DPH_VALINFO_BAD_INFIX_PATTERN)
1276     {
1277         DPRINT1("corrupted infix pattern for freed block\n");
1278     }
1279
1280     if (ValidationInfo & DPH_VALINFO_BAD_POINTER)
1281     {
1282         DPRINT1("corrupted heap pointer or using wrong heap\n");
1283     }
1284
1285     if (ValidationInfo & DPH_VALINFO_BAD_SUFFIX_PATTERN)
1286     {
1287         DPRINT1("corrupted suffix pattern\n");
1288     }
1289
1290     if (ValidationInfo & DPH_VALINFO_BAD_PREFIX_PATTERN)
1291     {
1292         DPRINT1("corrupted prefix pattern\n");
1293     }
1294
1295     if (ValidationInfo & DPH_VALINFO_BAD_START_STAMP)
1296     {
1297         DPRINT1("corrupted start stamp\n");
1298     }
1299
1300     if (ValidationInfo & DPH_VALINFO_BAD_END_STAMP)
1301     {
1302         DPRINT1("corrupted end stamp\n");
1303     }
1304
1305     if (ValidationInfo & DPH_VALINFO_EXCEPTION)
1306     {
1307         DPRINT1("exception raised while verifying block\n");
1308     }
1309
1310     DPRINT1("Corrupted heap block %p\n", Block);
1311 }
1312
1313 BOOLEAN NTAPI
1314 RtlpDphIsPageHeapBlock(PDPH_HEAP_ROOT DphRoot,
1315                        PVOID Block,
1316                        PULONG ValidationInformation,
1317                        BOOLEAN CheckFillers)
1318 {
1319     PDPH_BLOCK_INFORMATION BlockInfo;
1320     BOOLEAN SomethingWrong = FALSE;
1321     PUCHAR Byte, Start, End;
1322
1323     ASSERT(ValidationInformation != NULL);
1324     *ValidationInformation = 0;
1325
1326     // _SEH2_TRY {
1327     BlockInfo = (PDPH_BLOCK_INFORMATION)Block - 1;
1328
1329     /* Check stamps */
1330     if (BlockInfo->StartStamp != DPH_FILL_START_STAMP_1)
1331     {
1332         *ValidationInformation |= DPH_VALINFO_BAD_START_STAMP;
1333         SomethingWrong = TRUE;
1334
1335         /* Check if it has an alloc/free mismatch */
1336         if (BlockInfo->StartStamp == DPH_FILL_START_STAMP_2)
1337         {
1338             /* Notify respectively */
1339             *ValidationInformation = 0x101;
1340         }
1341     }
1342
1343     if (BlockInfo->EndStamp != DPH_FILL_END_STAMP_1)
1344     {
1345         *ValidationInformation |= DPH_VALINFO_BAD_END_STAMP;
1346         SomethingWrong = TRUE;
1347     }
1348
1349     /* Check root heap pointer */
1350     if (BlockInfo->Heap != DphRoot)
1351     {
1352         *ValidationInformation |= DPH_VALINFO_BAD_POINTER;
1353         SomethingWrong = TRUE;
1354     }
1355
1356     /* Check other fillers if requested */
1357     if (CheckFillers)
1358     {
1359         /* Check space after the block */
1360         Start = (PUCHAR)Block + BlockInfo->RequestedSize;
1361         End = (PUCHAR)ROUND_UP(Start, PAGE_SIZE);
1362         for (Byte = Start; Byte < End; Byte++)
1363         {
1364             if (*Byte != DPH_FILL_SUFFIX)
1365             {
1366                 *ValidationInformation |= DPH_VALINFO_BAD_SUFFIX_PATTERN;
1367                 SomethingWrong = TRUE;
1368                 break;
1369             }
1370         }
1371     }
1372
1373     return (SomethingWrong == FALSE);
1374 }
1375
1376 BOOLEAN NTAPI
1377 RtlpDphIsNormalFreeHeapBlock(PVOID Block,
1378                              PULONG ValidationInformation,
1379                              BOOLEAN CheckFillers)
1380 {
1381     ASSERT(ValidationInformation != NULL);
1382
1383     UNIMPLEMENTED;
1384     *ValidationInformation = 0;
1385     return TRUE;
1386 }
1387
1388 NTSTATUS NTAPI
1389 RtlpDphProcessStartupInitialization()
1390 {
1391     NTSTATUS Status;
1392     PTEB Teb = NtCurrentTeb();
1393
1394     /* Initialize the DPH heap list and its critical section */
1395     InitializeListHead(&RtlpDphPageHeapList);
1396     Status = RtlInitializeHeapLock(&RtlpDphPageHeapListLock);
1397     if (!NT_SUCCESS(Status))
1398     {
1399         ASSERT(FALSE);
1400         return Status;
1401     }
1402
1403     /* Initialize delayed-free queue */
1404     Status = RtlpDphInitializeDelayedFreeQueue();
1405     if (!NT_SUCCESS(Status)) return Status;
1406
1407     /* Initialize the target dlls string */
1408     RtlInitUnicodeString(&RtlpDphTargetDllsUnicode, RtlpDphTargetDlls);
1409     Status = RtlpDphTargetDllsLogicInitialize();
1410
1411     /* Per-process DPH init is done */
1412     RtlpDphPageHeapListInitialized = TRUE;
1413
1414     DPRINT1("Page heap: pid 0x%p: page heap enabled with flags 0x%X.\n",
1415             Teb->ClientId.UniqueProcess, RtlpDphGlobalFlags);
1416
1417     return Status;
1418 }
1419
1420 BOOLEAN NTAPI
1421 RtlpDphShouldAllocateInPageHeap(PDPH_HEAP_ROOT DphRoot,
1422                                 SIZE_T Size)
1423 {
1424     //UNIMPLEMENTED;
1425     /* Always use page heap for now */
1426     return TRUE;
1427 }
1428
1429 HANDLE NTAPI
1430 RtlpPageHeapCreate(ULONG Flags,
1431                    PVOID Addr,
1432                    SIZE_T TotalSize,
1433                    SIZE_T CommitSize,
1434                    PVOID Lock,
1435                    PRTL_HEAP_PARAMETERS Parameters)
1436 {
1437     PVOID Base = NULL;
1438     PHEAP HeapPtr;
1439     PDPH_HEAP_ROOT DphRoot;
1440     PDPH_HEAP_BLOCK DphNode;
1441     ULONG MemSize;
1442     NTSTATUS Status;
1443     LARGE_INTEGER PerfCounter;
1444
1445     /* Check for a DPH bypass flag */
1446     if ((ULONG_PTR)Parameters == -1) return NULL;
1447
1448     /* Make sure no user-allocated stuff was provided */
1449     if (Addr || Lock) return NULL;
1450
1451     /* Allocate minimum amount of virtual memory */
1452     MemSize = DPH_RESERVE_SIZE;
1453     Status = RtlpDphAllocateVm(&Base, MemSize, MEM_COMMIT, PAGE_NOACCESS);
1454     if (!NT_SUCCESS(Status))
1455     {
1456         ASSERT(FALSE);
1457         return NULL;
1458     }
1459
1460     /* Set protection */
1461     Status = RtlpDphProtectVm(Base, 2*PAGE_SIZE + DPH_POOL_SIZE, PAGE_READWRITE);
1462     if (!NT_SUCCESS(Status))
1463     {
1464         //RtlpDphFreeVm(Base, 0, 0, 0);
1465         ASSERT(FALSE);
1466         return NULL;
1467     }
1468
1469     /* Start preparing the 1st page. Fill it with the default filler */
1470     RtlFillMemoryUlong(Base, PAGE_SIZE, DPH_FILL);
1471
1472     /* Set flags in the "HEAP" structure */
1473     HeapPtr = (PHEAP)Base;
1474     HeapPtr->Flags = Flags | HEAP_FLAG_PAGE_ALLOCS;
1475     HeapPtr->ForceFlags = Flags | HEAP_FLAG_PAGE_ALLOCS;
1476
1477     /* Set 1st page to read only now */
1478     Status = RtlpDphProtectVm(Base, PAGE_SIZE, PAGE_READONLY);
1479     if (!NT_SUCCESS(Status))
1480     {
1481         ASSERT(FALSE);
1482         return NULL;
1483     }
1484
1485     /* 2nd page is the real DPH root block */
1486     DphRoot = (PDPH_HEAP_ROOT)((PCHAR)Base + PAGE_SIZE);
1487
1488     /* Initialize the DPH root */
1489     DphRoot->Signature = DPH_SIGNATURE;
1490     DphRoot->HeapFlags = Flags;
1491     DphRoot->HeapCritSect = (PHEAP_LOCK)((PCHAR)DphRoot + DPH_POOL_SIZE);
1492     DphRoot->ExtraFlags = RtlpDphGlobalFlags;
1493
1494     ZwQueryPerformanceCounter(&PerfCounter, NULL);
1495     DphRoot->Seed = PerfCounter.LowPart;
1496
1497     RtlInitializeHeapLock(&DphRoot->HeapCritSect);
1498     InitializeListHead(&DphRoot->AvailableAllocationHead);
1499
1500     /* Create a normal heap for this paged heap */
1501     DphRoot->NormalHeap = RtlCreateHeap(Flags, NULL, TotalSize, CommitSize, NULL, (PRTL_HEAP_PARAMETERS)-1);
1502     if (!DphRoot->NormalHeap)
1503     {
1504         ASSERT(FALSE);
1505         return NULL;
1506     }
1507
1508     /* 3rd page: a pool for DPH allocations */
1509     RtlpDphAddNewPool(DphRoot, NULL, DphRoot + 1, DPH_POOL_SIZE - sizeof(DPH_HEAP_ROOT), FALSE);
1510
1511     /* Allocate internal heap blocks. For the root */
1512     DphNode = RtlpDphAllocateNode(DphRoot);
1513     ASSERT(DphNode != NULL);
1514     DphNode->pVirtualBlock = (PUCHAR)DphRoot;
1515     DphNode->nVirtualBlockSize = DPH_POOL_SIZE;
1516     RtlpDphPlaceOnPoolList(DphRoot, DphNode);
1517
1518     /* For the memory we allocated as a whole */
1519     DphNode = RtlpDphAllocateNode(DphRoot);
1520     ASSERT(DphNode != NULL);
1521     DphNode->pVirtualBlock = Base;
1522     DphNode->nVirtualBlockSize = MemSize;
1523     RtlpDphPlaceOnVirtualList(DphRoot, DphNode);
1524
1525     /* For the remaining part */
1526     DphNode = RtlpDphAllocateNode(DphRoot);
1527     ASSERT(DphNode != NULL);
1528     DphNode->pVirtualBlock = (PUCHAR)Base + 2*PAGE_SIZE + DPH_POOL_SIZE;
1529     DphNode->nVirtualBlockSize = MemSize - (2*PAGE_SIZE + DPH_POOL_SIZE);
1530     RtlpDphCoalesceNodeIntoAvailable(DphRoot, DphNode);
1531
1532     //DphRoot->CreateStackTrace = RtlpDphLogStackTrace(1);
1533
1534     /* Initialize AVL-based busy nodes table */
1535     RtlInitializeGenericTableAvl(&DphRoot->BusyNodesTable,
1536                                  RtlpDphCompareNodeForTable,
1537                                  RtlpDphAllocateNodeForTable,
1538                                  RtlpDphFreeNodeForTable,
1539                                  NULL);
1540
1541     /* Initialize per-process startup info */
1542     if (!RtlpDphPageHeapListInitialized) RtlpDphProcessStartupInitialization();
1543
1544     /* Acquire the heap list lock */
1545     RtlEnterHeapLock(RtlpDphPageHeapListLock, TRUE);
1546
1547     /* Insert this heap to the tail of the global list */
1548     InsertTailList(&RtlpDphPageHeapList, &DphRoot->NextHeap);
1549
1550     /* Note we increased the size of the list */
1551     RtlpDphPageHeapListLength++;
1552
1553     /* Release the heap list lock */
1554     RtlLeaveHeapLock(RtlpDphPageHeapListLock);
1555
1556     if (RtlpDphDebugOptions & DPH_DEBUG_VERBOSE)
1557     {
1558         DPRINT1("Page heap: process 0x%p created heap @ %p (%p, flags 0x%X)\n",
1559                 NtCurrentTeb()->ClientId.UniqueProcess, (PUCHAR)DphRoot - PAGE_SIZE,
1560                 DphRoot->NormalHeap, DphRoot->ExtraFlags);
1561     }
1562
1563     /* Perform internal validation if required */
1564     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
1565         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
1566
1567     return (PUCHAR)DphRoot - PAGE_SIZE;
1568 }
1569
1570 PVOID NTAPI
1571 RtlpPageHeapDestroy(HANDLE HeapPtr)
1572 {
1573     PDPH_HEAP_ROOT DphRoot;
1574     PDPH_HEAP_BLOCK Node, Next;
1575     PHEAP NormalHeap;
1576     ULONG Value;
1577
1578     /* Check if it's not a process heap */
1579     if (HeapPtr == RtlGetProcessHeap())
1580     {
1581         DbgBreakPoint();
1582         return NULL;
1583     }
1584
1585     /* Get pointer to the heap root */
1586     DphRoot = RtlpDphPointerFromHandle(HeapPtr);
1587     if (!DphRoot) return NULL;
1588
1589     RtlpDphPreProcessing(DphRoot, DphRoot->HeapFlags);
1590
1591     /* Get the pointer to the normal heap */
1592     NormalHeap = DphRoot->NormalHeap;
1593
1594     /* Free the delayed-free blocks */
1595     RtlpDphFreeDelayedBlocksFromHeap(DphRoot, NormalHeap);
1596
1597     /* Go through the busy blocks */
1598     Node = RtlEnumerateGenericTableAvl(&DphRoot->BusyNodesTable, TRUE);
1599
1600     while (Node)
1601     {
1602         if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN))
1603         {
1604             if (!RtlpDphIsPageHeapBlock(DphRoot, Node->pUserAllocation, &Value, TRUE))
1605             {
1606                 RtlpDphReportCorruptedBlock(DphRoot, 3, Node->pUserAllocation, Value);
1607             }
1608         }
1609
1610         /* FIXME: Call AV notification */
1611         //AVrfInternalHeapFreeNotification();
1612
1613         /* Go to the next node */
1614         Node = RtlEnumerateGenericTableAvl(&DphRoot->BusyNodesTable, FALSE);
1615     }
1616
1617     /* Acquire the global heap list lock */
1618     RtlEnterHeapLock(RtlpDphPageHeapListLock, TRUE);
1619
1620     /* Remove the entry and decrement the global counter */
1621     RemoveEntryList(&DphRoot->NextHeap);
1622     RtlpDphPageHeapListLength--;
1623
1624     /* Release the global heap list lock */
1625     RtlLeaveHeapLock(RtlpDphPageHeapListLock);
1626
1627     /* Leave and delete this heap's critical section */
1628     RtlLeaveHeapLock(DphRoot->HeapCritSect);
1629     RtlDeleteHeapLock(DphRoot->HeapCritSect);
1630
1631     /* Now go through all virtual list nodes and release the VM */
1632     Node = DphRoot->pVirtualStorageListHead;
1633     while (Node)
1634     {
1635         Next = Node->pNextAlloc;
1636         /* Release the memory without checking result */
1637         RtlpDphFreeVm(Node->pVirtualBlock, 0, MEM_RELEASE);
1638         Node = Next;
1639     }
1640
1641     /* Destroy the normal heap */
1642     RtlDestroyHeap(NormalHeap);
1643
1644     /* Report success */
1645     if (RtlpDphDebugOptions & DPH_DEBUG_VERBOSE)
1646         DPRINT1("Page heap: process 0x%p destroyed heap @ %p (%p)\n",
1647                 NtCurrentTeb()->ClientId.UniqueProcess, HeapPtr, NormalHeap);
1648
1649     return NULL;
1650 }
1651
1652 PVOID NTAPI
1653 RtlpPageHeapAllocate(IN PVOID HeapPtr,
1654                      IN ULONG Flags,
1655                      IN SIZE_T Size)
1656 {
1657     PDPH_HEAP_ROOT DphRoot;
1658     PDPH_HEAP_BLOCK AvailableNode, BusyNode;
1659     BOOLEAN Biased = FALSE;
1660     ULONG AllocateSize, AccessSize;
1661     NTSTATUS Status;
1662     SIZE_T UserActualSize;
1663     PVOID Ptr;
1664
1665     /* Check requested size */
1666     if (Size > 0x7FF00000)
1667     {
1668         DPRINT1("extreme size request\n");
1669
1670         /* Generate an exception if needed */
1671         if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY);
1672
1673         return NULL;
1674     }
1675
1676     /* Unbias the pointer if necessary */
1677     if (IS_BIASED_POINTER(HeapPtr))
1678     {
1679         HeapPtr = (PVOID)POINTER_REMOVE_BIAS(HeapPtr);
1680         Biased = TRUE;
1681     }
1682
1683     /* Get a pointer to the heap root */
1684     DphRoot = RtlpDphPointerFromHandle(HeapPtr);
1685     if (!DphRoot) return NULL;
1686
1687     /* Acquire the heap lock */
1688     RtlpDphPreProcessing(DphRoot, Flags);
1689
1690     /* Perform internal validation if specified by flags */
1691     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased)
1692     {
1693         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
1694     }
1695
1696     /* Add heap flags */
1697     Flags |= DphRoot->HeapFlags;
1698
1699     if (!Biased && !RtlpDphShouldAllocateInPageHeap(DphRoot, Size))
1700     {
1701         /* Perform allocation from a normal heap */
1702         ASSERT(FALSE);
1703     }
1704
1705     /* Perform heap integrity check if specified by flags */
1706     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
1707     {
1708         RtlpDphVerifyIntegrity(DphRoot);
1709     }
1710
1711     /* Calculate sizes */
1712     AccessSize = ROUND_UP(Size + sizeof(DPH_BLOCK_INFORMATION), PAGE_SIZE);
1713     AllocateSize = AccessSize + PAGE_SIZE;
1714
1715     // FIXME: Move RtlpDphAllocateNode(DphRoot) to this place
1716     AvailableNode = RtlpDphFindAvailableMemory(DphRoot, AllocateSize, TRUE);
1717     if (!AvailableNode)
1718     {
1719         DPRINT1("Page heap: Unable to allocate virtual memory\n");
1720         DbgBreakPoint();
1721
1722         /* Release the lock */
1723         RtlpDphPostProcessing(DphRoot);
1724
1725         return NULL;
1726     }
1727     ASSERT(AvailableNode->nVirtualBlockSize >= AllocateSize);
1728
1729     /* Set protection */
1730     Status = RtlpDphSetProtectionBeforeUse(DphRoot,
1731                                            AvailableNode->pVirtualBlock,
1732                                            AccessSize);
1733     if (!NT_SUCCESS(Status))
1734     {
1735         ASSERT(FALSE);
1736     }
1737
1738     /* Save available node pointer */
1739     Ptr = AvailableNode->pVirtualBlock;
1740
1741     /* Check node's size */
1742     if (AvailableNode->nVirtualBlockSize > AllocateSize)
1743     {
1744         /* The block contains too much free space, reduce it */
1745         AvailableNode->pVirtualBlock += AllocateSize;
1746         AvailableNode->nVirtualBlockSize -= AllocateSize;
1747         DphRoot->nAvailableAllocationBytesCommitted -= AllocateSize;
1748
1749         /* Allocate a new node which will be our busy node */
1750         BusyNode = RtlpDphAllocateNode(DphRoot);
1751         ASSERT(BusyNode != NULL);
1752         BusyNode->pVirtualBlock = Ptr;
1753         BusyNode->nVirtualBlockSize = AllocateSize;
1754     }
1755     else
1756     {
1757         /* The block's size fits exactly */
1758         RtlpDphRemoveFromAvailableList(DphRoot, AvailableNode);
1759         BusyNode = AvailableNode;
1760     }
1761
1762     /* Calculate actual user size  */
1763     if (DphRoot->HeapFlags & HEAP_NO_ALIGNMENT)
1764         UserActualSize = Size;
1765     else
1766         UserActualSize = ROUND_UP(Size, 8);
1767
1768     /* Set up the block */
1769     BusyNode->nVirtualAccessSize = AccessSize;
1770     BusyNode->nUserActualSize = UserActualSize;
1771     BusyNode->nUserRequestedSize = Size;
1772
1773     if (DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)
1774         BusyNode->pUserAllocation = BusyNode->pVirtualBlock + PAGE_SIZE;
1775     else
1776         BusyNode->pUserAllocation = BusyNode->pVirtualBlock + BusyNode->nVirtualAccessSize - UserActualSize;
1777
1778     BusyNode->UserValue = NULL;
1779     BusyNode->UserFlags = Flags & HEAP_SETTABLE_USER_FLAGS;
1780
1781     // FIXME: Don't forget about stack traces if such flag was set
1782     BusyNode->StackTrace = NULL;
1783
1784     /* Place it on busy list */
1785     RtlpDphPlaceOnBusyList(DphRoot, BusyNode);
1786
1787     /* Zero or patter-fill memory depending on flags */
1788     if (Flags & HEAP_ZERO_MEMORY)
1789         RtlZeroMemory(BusyNode->pUserAllocation, Size);
1790     else
1791         RtlFillMemory(BusyNode->pUserAllocation, Size, DPH_FILL_INFIX);
1792
1793     /* Write DPH info */
1794     if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN))
1795     {
1796         RtlpDphWritePageHeapBlockInformation(DphRoot,
1797                                              BusyNode->pUserAllocation,
1798                                              Size,
1799                                              AccessSize);
1800     }
1801
1802     /* Finally allocation is done, perform validation again if required */
1803     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased)
1804     {
1805         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
1806     }
1807
1808     /* Release the lock */
1809     RtlpDphPostProcessing(DphRoot);
1810
1811     DPRINT("Allocated user block pointer: %p\n", BusyNode->pUserAllocation);
1812
1813     /* Return pointer to user allocation */
1814     return BusyNode->pUserAllocation;
1815 }
1816
1817 BOOLEAN NTAPI
1818 RtlpPageHeapFree(HANDLE HeapPtr,
1819                  ULONG Flags,
1820                  PVOID Ptr)
1821 {
1822     PDPH_HEAP_ROOT DphRoot;
1823     PDPH_HEAP_BLOCK Node;
1824     ULONG ValidationInfo;
1825     PDPH_BLOCK_INFORMATION Info;
1826
1827     /* Check for a NULL pointer freeing */
1828     if (!Ptr)
1829     {
1830         if (RtlpDphBreakOptions & DPH_BREAK_ON_NULL_FREE)
1831         {
1832             DPRINT1("Page heap: freeing a null pointer \n");
1833             DbgBreakPoint();
1834         }
1835         return TRUE;
1836     }
1837
1838     /* Get a pointer to the heap root */
1839     DphRoot = RtlpDphPointerFromHandle(HeapPtr);
1840     if (!DphRoot) return FALSE;
1841
1842     /* Acquire the heap lock */
1843     RtlpDphPreProcessing(DphRoot, Flags);
1844
1845     /* Perform internal validation if specified by flags */
1846     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
1847         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
1848
1849     /* Add heap flags */
1850     Flags |= DphRoot->HeapFlags;
1851
1852     /* Find busy memory */
1853     Node = RtlpDphFindBusyMemory(DphRoot, Ptr);
1854
1855     if (!Node)
1856     {
1857         /* This block was not found in page heap, try a normal heap instead */
1858         //RtlpDphNormalHeapFree();
1859         ASSERT(FALSE);
1860     }
1861
1862     if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN))
1863     {
1864         /* Check and report corrupted block */
1865         if (!RtlpDphIsPageHeapBlock(DphRoot, Ptr, &ValidationInfo, TRUE))
1866         {
1867             RtlpDphReportCorruptedBlock(DphRoot, 1, Ptr, ValidationInfo);
1868         }
1869
1870         // FIXME: Should go inside RtlpDphSetProtectionAfterUse
1871         if (Node->nVirtualAccessSize != 0)
1872         {
1873             /* Set stamps */
1874             Info = (PDPH_BLOCK_INFORMATION)Node->pUserAllocation - 1;
1875             Info->StartStamp = DPH_FILL_START_STAMP_2;
1876             Info->EndStamp = DPH_FILL_END_STAMP_2;
1877
1878             RtlpDphProtectVm(Node->pVirtualBlock, Node->nVirtualAccessSize, PAGE_NOACCESS);
1879         }
1880     }
1881     else
1882     {
1883         // FIXME: Should go inside RtlpDphSetProtectionAfterUse
1884         if (Node->nVirtualAccessSize != 0)
1885             RtlpDphProtectVm(Node->pVirtualBlock + PAGE_SIZE, Node->nVirtualAccessSize, PAGE_NOACCESS);
1886     }
1887
1888     /* Set new protection */
1889     //RtlpDphSetProtectionAfterUse(DphRoot, Node);
1890
1891     /* Remove it from the list of busy nodes */
1892     RtlpDphRemoveFromBusyList(DphRoot, Node);
1893
1894     /* And put it into the list of free nodes */
1895     RtlpDphPlaceOnFreeList(DphRoot, Node);
1896
1897     //if (DphRoot->ExtraFlags & DPH_EXTRA_LOG_STACK_TRACES)
1898     //    Node->StackTrace = RtlpDphLogStackTrace(3);
1899     //else
1900         Node->StackTrace = NULL;
1901
1902     /* Leave the heap lock */
1903     RtlpDphPostProcessing(DphRoot);
1904
1905     /* Return success */
1906     return TRUE;
1907 }
1908
1909 PVOID NTAPI
1910 RtlpPageHeapReAllocate(HANDLE HeapPtr,
1911                        ULONG Flags,
1912                        PVOID Ptr,
1913                        SIZE_T Size)
1914 {
1915     PDPH_HEAP_ROOT DphRoot;
1916     PDPH_HEAP_BLOCK Node = NULL, AllocatedNode;
1917     BOOLEAN Biased = FALSE, UseNormalHeap = FALSE, OldBlockPageHeap = TRUE;
1918     ULONG ValidationInfo;
1919     SIZE_T DataSize;
1920     PVOID NewAlloc = NULL;
1921
1922     /* Check requested size */
1923     if (Size > 0x7FF00000)
1924     {
1925         DPRINT1("extreme size request\n");
1926
1927         /* Generate an exception if needed */
1928         if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY);
1929
1930         return NULL;
1931     }
1932
1933     /* Unbias the pointer if necessary */
1934     if (IS_BIASED_POINTER(HeapPtr))
1935     {
1936         HeapPtr = (PVOID)POINTER_REMOVE_BIAS(HeapPtr);
1937         Biased = TRUE;
1938     }
1939
1940     /* Get a pointer to the heap root */
1941     DphRoot = RtlpDphPointerFromHandle(HeapPtr);
1942     if (!DphRoot) return NULL;
1943
1944     /* Acquire the heap lock */
1945     RtlpDphPreProcessing(DphRoot, Flags);
1946
1947     /* Perform internal validation if specified by flags */
1948     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
1949     {
1950         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
1951     }
1952
1953     /* Add heap flags */
1954     Flags |= DphRoot->HeapFlags;
1955
1956     /* Exit with NULL right away if inplace is specified */
1957     if (Flags & HEAP_REALLOC_IN_PLACE_ONLY)
1958     {
1959         /* Release the lock */
1960         RtlpDphPostProcessing(DphRoot);
1961
1962         /* Generate an exception if needed */
1963         if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY);
1964
1965         return NULL;
1966     }
1967
1968     /* Try to get node of the allocated block */
1969     AllocatedNode = RtlpDphFindBusyMemory(DphRoot, Ptr);
1970
1971     if (!AllocatedNode)
1972     {
1973         /* This block was not found in page heap, try a normal heap instead */
1974         //RtlpDphNormalHeapFree();
1975         ASSERT(FALSE);
1976         OldBlockPageHeap = FALSE;
1977     }
1978
1979     /* Check the block */
1980     if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN))
1981     {
1982         if (!RtlpDphIsPageHeapBlock(DphRoot, AllocatedNode->pUserAllocation, &ValidationInfo, TRUE))
1983         {
1984             RtlpDphReportCorruptedBlock(DphRoot, 3, AllocatedNode->pUserAllocation, ValidationInfo);
1985         }
1986     }
1987
1988     /* Remove old one from the busy list */
1989     RtlpDphRemoveFromBusyList(DphRoot, AllocatedNode);
1990
1991     if (!Biased && !RtlpDphShouldAllocateInPageHeap(DphRoot, Size))
1992     {
1993         // FIXME: Use normal heap
1994         ASSERT(FALSE);
1995         UseNormalHeap = TRUE;
1996     }
1997     else
1998     {
1999         /* Now do a trick: bias the pointer and call our allocate routine */
2000         NewAlloc = RtlpPageHeapAllocate((PVOID)POINTER_ADD_BIAS(HeapPtr), Flags, Size);
2001     }
2002
2003     if (!NewAlloc)
2004     {
2005         /* New allocation failed, put the block back (if it was found in page heap) */
2006         RtlpDphPlaceOnBusyList(DphRoot, AllocatedNode);
2007
2008         /* Release the lock */
2009         RtlpDphPostProcessing(DphRoot);
2010
2011         /* Perform validation again if required */
2012         if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
2013         {
2014             RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
2015         }
2016
2017         /* Generate an exception if needed */
2018         if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY);
2019
2020         return NULL;
2021     }
2022
2023     /* Copy contents of the old block */
2024     if (AllocatedNode->nUserRequestedSize > Size)
2025         DataSize = Size;
2026     else
2027         DataSize = AllocatedNode->nUserRequestedSize;
2028
2029     if (DataSize != 0) RtlCopyMemory(NewAlloc, Ptr, DataSize);
2030
2031     /* Copy user flags and values */
2032     if (!UseNormalHeap)
2033     {
2034         /* Get the node of the new block */
2035         Node = RtlpDphFindBusyMemory(DphRoot, NewAlloc);
2036         ASSERT(Node != NULL);
2037
2038         /* Set its values/flags */
2039         Node->UserValue = AllocatedNode->UserValue;
2040         if (Flags & HEAP_SETTABLE_USER_FLAGS)
2041             Node->UserFlags = Flags & HEAP_SETTABLE_USER_FLAGS;
2042         else
2043             Node->UserFlags = AllocatedNode->UserFlags;
2044     }
2045
2046     if (!OldBlockPageHeap)
2047     {
2048         /* Weird scenario, investigate */
2049         ASSERT(FALSE);
2050     }
2051
2052     /* Mark the old block as no access */
2053     if (AllocatedNode->nVirtualAccessSize != 0)
2054     {
2055         RtlpDphProtectVm(AllocatedNode->pVirtualBlock, AllocatedNode->nVirtualAccessSize, PAGE_NOACCESS);
2056     }
2057
2058     /* And place it on the free list */
2059     RtlpDphPlaceOnFreeList(DphRoot, AllocatedNode);
2060
2061     // FIXME: Capture stack traces if needed
2062     AllocatedNode->StackTrace = NULL;
2063
2064     /* Finally allocation is done, perform validation again if required */
2065     if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased)
2066     {
2067         RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
2068     }
2069
2070     /* Release the lock */
2071     RtlpDphPostProcessing(DphRoot);
2072
2073     DPRINT("Allocated new user block pointer: %p\n", NewAlloc);
2074
2075     /* Return pointer to user allocation */
2076     return NewAlloc;
2077 }
2078
2079 BOOLEAN NTAPI
2080 RtlpPageHeapGetUserInfo(PVOID HeapHandle,
2081                         ULONG Flags,
2082                         PVOID BaseAddress,
2083                         PVOID *UserValue,
2084                         PULONG UserFlags)
2085 {
2086     PDPH_HEAP_ROOT DphRoot;
2087     PDPH_HEAP_BLOCK Node;
2088
2089     /* Get a pointer to the heap root */
2090     DphRoot = RtlpDphPointerFromHandle(HeapHandle);
2091     if (!DphRoot) return FALSE;
2092
2093     /* Add heap flags */
2094     Flags |= DphRoot->HeapFlags;
2095
2096     /* Acquire the heap lock */
2097     RtlpDphPreProcessing(DphRoot, Flags);
2098
2099     /* Find busy memory */
2100     Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress);
2101
2102     if (!Node)
2103     {
2104         /* This block was not found in page heap, try a normal heap instead */
2105         //RtlpDphNormalHeapGetUserInfo();
2106         ASSERT(FALSE);
2107         return FALSE;
2108     }
2109
2110     /* Get user values and flags and store them in user provided pointers */
2111     if (UserValue) *UserValue = Node->UserValue;
2112     if (UserFlags) *UserFlags = Node->UserFlags;
2113
2114     /* Leave the heap lock */
2115     RtlpDphPostProcessing(DphRoot);
2116
2117     /* Return success */
2118     return TRUE;
2119 }
2120
2121 BOOLEAN NTAPI
2122 RtlpPageHeapSetUserValue(PVOID HeapHandle,
2123                          ULONG Flags,
2124                          PVOID BaseAddress,
2125                          PVOID UserValue)
2126 {
2127     PDPH_HEAP_ROOT DphRoot;
2128     PDPH_HEAP_BLOCK Node;
2129
2130     /* Get a pointer to the heap root */
2131     DphRoot = RtlpDphPointerFromHandle(HeapHandle);
2132     if (!DphRoot) return FALSE;
2133
2134     /* Add heap flags */
2135     Flags |= DphRoot->HeapFlags;
2136
2137     /* Acquire the heap lock */
2138     RtlpDphPreProcessing(DphRoot, Flags);
2139
2140     /* Find busy memory */
2141     Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress);
2142
2143     if (!Node)
2144     {
2145         /* This block was not found in page heap, try a normal heap instead */
2146         //RtlpDphNormalHeapSetUserValue();
2147         ASSERT(FALSE);
2148         return FALSE;
2149     }
2150
2151     /* Get user values and flags and store them in user provided pointers */
2152     Node->UserValue = UserValue;
2153
2154     /* Leave the heap lock */
2155     RtlpDphPostProcessing(DphRoot);
2156
2157     /* Return success */
2158     return TRUE;
2159 }
2160
2161 BOOLEAN
2162 NTAPI
2163 RtlpPageHeapSetUserFlags(PVOID HeapHandle,
2164                          ULONG Flags,
2165                          PVOID BaseAddress,
2166                          ULONG UserFlagsReset,
2167                          ULONG UserFlagsSet)
2168 {
2169     PDPH_HEAP_ROOT DphRoot;
2170     PDPH_HEAP_BLOCK Node;
2171
2172     /* Get a pointer to the heap root */
2173     DphRoot = RtlpDphPointerFromHandle(HeapHandle);
2174     if (!DphRoot) return FALSE;
2175
2176     /* Add heap flags */
2177     Flags |= DphRoot->HeapFlags;
2178
2179     /* Acquire the heap lock */
2180     RtlpDphPreProcessing(DphRoot, Flags);
2181
2182     /* Find busy memory */
2183     Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress);
2184
2185     if (!Node)
2186     {
2187         /* This block was not found in page heap, try a normal heap instead */
2188         //RtlpDphNormalHeapSetUserFlags();
2189         ASSERT(FALSE);
2190         return FALSE;
2191     }
2192
2193     /* Get user values and flags and store them in user provided pointers */
2194     Node->UserFlags &= ~(UserFlagsReset);
2195     Node->UserFlags |= UserFlagsSet;
2196
2197     /* Leave the heap lock */
2198     RtlpDphPostProcessing(DphRoot);
2199
2200     /* Return success */
2201     return TRUE;
2202 }
2203
2204 SIZE_T NTAPI
2205 RtlpPageHeapSize(HANDLE HeapHandle,
2206                  ULONG Flags,
2207                  PVOID BaseAddress)
2208 {
2209     PDPH_HEAP_ROOT DphRoot;
2210     PDPH_HEAP_BLOCK Node;
2211     SIZE_T Size;
2212
2213     /* Get a pointer to the heap root */
2214     DphRoot = RtlpDphPointerFromHandle(HeapHandle);
2215     if (!DphRoot) return -1;
2216
2217     /* Add heap flags */
2218     Flags |= DphRoot->HeapFlags;
2219
2220     /* Acquire the heap lock */
2221     RtlpDphPreProcessing(DphRoot, Flags);
2222
2223     /* Find busy memory */
2224     Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress);
2225
2226     if (!Node)
2227     {
2228         /* This block was not found in page heap, try a normal heap instead */
2229         //RtlpDphNormalHeapSize();
2230         ASSERT(FALSE);
2231         return -1;
2232     }
2233
2234     /* Get heap block size */
2235     Size = Node->nUserRequestedSize;
2236
2237     /* Leave the heap lock */
2238     RtlpDphPostProcessing(DphRoot);
2239
2240     /* Return user requested size */
2241     return Size;
2242 }
2243
2244 BOOLEAN
2245 NTAPI
2246 RtlpDebugPageHeapValidate(PVOID HeapHandle,
2247                           ULONG Flags,
2248                           PVOID BaseAddress)
2249 {
2250     PDPH_HEAP_ROOT DphRoot;
2251     PDPH_HEAP_BLOCK Node = NULL;
2252     BOOLEAN Valid = FALSE;
2253
2254     /* Get a pointer to the heap root */
2255     DphRoot = RtlpDphPointerFromHandle(HeapHandle);
2256     if (!DphRoot) return -1;
2257
2258     /* Add heap flags */
2259     Flags |= DphRoot->HeapFlags;
2260
2261     /* Acquire the heap lock */
2262     RtlpDphPreProcessing(DphRoot, Flags);
2263
2264     /* Find busy memory */
2265     if (BaseAddress)
2266         Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress);
2267
2268     if (!Node)
2269     {
2270         /* This block was not found in page heap, or the request is to validate all normal heap */
2271         Valid = RtlpDphNormalHeapValidate(DphRoot, Flags, BaseAddress);
2272     }
2273
2274     /* Leave the heap lock */
2275     RtlpDphPostProcessing(DphRoot);
2276
2277     /* Return result of a normal heap validation */
2278     if (BaseAddress && !Node)
2279         return Valid;
2280
2281     /* Otherwise return our own result */
2282     if (!BaseAddress || Node) Valid = TRUE;
2283
2284     return Valid;
2285 }
2286
2287 BOOLEAN
2288 NTAPI
2289 RtlpDphNormalHeapValidate(PDPH_HEAP_ROOT DphRoot,
2290                           ULONG Flags,
2291                           PVOID BaseAddress)
2292 {
2293     PDPH_BLOCK_INFORMATION BlockInfo = (PDPH_BLOCK_INFORMATION)BaseAddress - 1;
2294     if (!BaseAddress)
2295     {
2296         /* Validate all normal heap */
2297         return RtlValidateHeap(DphRoot->NormalHeap, Flags, NULL);
2298     }
2299
2300     // FIXME: Check is this a normal heap block
2301     /*if (!RtlpDphIsNormalHeapBlock(DphRoot, BaseAddress, &ValidationInfo))
2302     {
2303     }*/
2304
2305     return RtlValidateHeap(DphRoot->NormalHeap, Flags, BlockInfo);
2306 }
2307
2308 /* EOF */