reactos/lib/rtl/heappage.c

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