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