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 DPRINT("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(VOID) 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(VOID) 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(VOID) 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 PVOID Ptr; 1617 PDPH_HEAP_BLOCK Node, Next; 1618 PHEAP NormalHeap; 1619 ULONG Value; 1620 1621 /* Check if it's not a process heap */ 1622 if (HeapPtr == RtlGetProcessHeap()) 1623 { 1624 DbgBreakPoint(); 1625 return NULL; 1626 } 1627 1628 /* Get pointer to the heap root */ 1629 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 1630 if (!DphRoot) return NULL; 1631 1632 RtlpDphPreProcessing(DphRoot, DphRoot->HeapFlags); 1633 1634 /* Get the pointer to the normal heap */ 1635 NormalHeap = DphRoot->NormalHeap; 1636 1637 /* Free the delayed-free blocks */ 1638 RtlpDphFreeDelayedBlocksFromHeap(DphRoot, NormalHeap); 1639 1640 /* Go through the busy blocks */ 1641 Ptr = RtlEnumerateGenericTableAvl(&DphRoot->BusyNodesTable, TRUE); 1642 1643 while (Ptr) 1644 { 1645 Node = CONTAINING_RECORD(Ptr, DPH_HEAP_BLOCK, pUserAllocation); 1646 if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)) 1647 { 1648 if (!RtlpDphIsPageHeapBlock(DphRoot, Node->pUserAllocation, &Value, TRUE)) 1649 { 1650 RtlpDphReportCorruptedBlock(DphRoot, 3, Node->pUserAllocation, Value); 1651 } 1652 } 1653 1654 /* FIXME: Call AV notification */ 1655 //AVrfInternalHeapFreeNotification(); 1656 1657 /* Go to the next node */ 1658 Ptr = RtlEnumerateGenericTableAvl(&DphRoot->BusyNodesTable, FALSE); 1659 } 1660 1661 /* Acquire the global heap list lock */ 1662 RtlEnterHeapLock(RtlpDphPageHeapListLock, TRUE); 1663 1664 /* Remove the entry and decrement the global counter */ 1665 RemoveEntryList(&DphRoot->NextHeap); 1666 RtlpDphPageHeapListLength--; 1667 1668 /* Release the global heap list lock */ 1669 RtlLeaveHeapLock(RtlpDphPageHeapListLock); 1670 1671 /* Leave and delete this heap's critical section */ 1672 RtlLeaveHeapLock(DphRoot->HeapCritSect); 1673 RtlDeleteHeapLock(DphRoot->HeapCritSect); 1674 1675 /* Now go through all virtual list nodes and release the VM */ 1676 Node = DphRoot->pVirtualStorageListHead; 1677 while (Node) 1678 { 1679 Next = Node->pNextAlloc; 1680 /* Release the memory without checking result */ 1681 RtlpDphFreeVm(Node->pVirtualBlock, 0, MEM_RELEASE); 1682 Node = Next; 1683 } 1684 1685 /* Destroy the normal heap */ 1686 RtlDestroyHeap(NormalHeap); 1687 1688 /* Report success */ 1689 if (RtlpDphDebugOptions & DPH_DEBUG_VERBOSE) 1690 DPRINT1("Page heap: process 0x%p destroyed heap @ %p (%p)\n", 1691 NtCurrentTeb()->ClientId.UniqueProcess, HeapPtr, NormalHeap); 1692 1693 return NULL; 1694 } 1695 1696 PVOID NTAPI 1697 RtlpPageHeapAllocate(IN PVOID HeapPtr, 1698 IN ULONG Flags, 1699 IN SIZE_T Size) 1700 { 1701 PDPH_HEAP_ROOT DphRoot; 1702 PDPH_HEAP_BLOCK AvailableNode, BusyNode; 1703 BOOLEAN Biased = FALSE; 1704 ULONG AllocateSize, AccessSize; 1705 NTSTATUS Status; 1706 SIZE_T UserActualSize; 1707 PVOID Ptr; 1708 1709 /* Check requested size */ 1710 if (Size > 0x7FF00000) 1711 { 1712 DPRINT1("extreme size request\n"); 1713 1714 /* Generate an exception if needed */ 1715 if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY); 1716 1717 return NULL; 1718 } 1719 1720 /* Unbias the pointer if necessary */ 1721 if (IS_BIASED_POINTER(HeapPtr)) 1722 { 1723 HeapPtr = (PVOID)POINTER_REMOVE_BIAS(HeapPtr); 1724 Biased = TRUE; 1725 } 1726 1727 /* Get a pointer to the heap root */ 1728 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 1729 if (!DphRoot) return NULL; 1730 1731 /* Acquire the heap lock */ 1732 RtlpDphPreProcessing(DphRoot, Flags); 1733 1734 /* Perform internal validation if specified by flags */ 1735 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased) 1736 { 1737 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 1738 } 1739 1740 /* Add heap flags */ 1741 Flags |= DphRoot->HeapFlags; 1742 1743 if (!Biased && !RtlpDphShouldAllocateInPageHeap(DphRoot, Size)) 1744 { 1745 /* Perform allocation from a normal heap */ 1746 ASSERT(FALSE); 1747 } 1748 1749 /* Perform heap integrity check if specified by flags */ 1750 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE) 1751 { 1752 RtlpDphVerifyIntegrity(DphRoot); 1753 } 1754 1755 /* Calculate sizes */ 1756 AccessSize = ROUND_UP(Size + sizeof(DPH_BLOCK_INFORMATION), PAGE_SIZE); 1757 AllocateSize = AccessSize + PAGE_SIZE; 1758 1759 // FIXME: Move RtlpDphAllocateNode(DphRoot) to this place 1760 AvailableNode = RtlpDphFindAvailableMemory(DphRoot, AllocateSize, TRUE); 1761 if (!AvailableNode) 1762 { 1763 DPRINT1("Page heap: Unable to allocate virtual memory\n"); 1764 DbgBreakPoint(); 1765 1766 /* Release the lock */ 1767 RtlpDphPostProcessing(DphRoot); 1768 1769 return NULL; 1770 } 1771 ASSERT(AvailableNode->nVirtualBlockSize >= AllocateSize); 1772 1773 /* Set protection */ 1774 Status = RtlpDphSetProtectionBeforeUse(DphRoot, 1775 AvailableNode->pVirtualBlock, 1776 AccessSize); 1777 if (!NT_SUCCESS(Status)) 1778 { 1779 ASSERT(FALSE); 1780 } 1781 1782 /* Save available node pointer */ 1783 Ptr = AvailableNode->pVirtualBlock; 1784 1785 /* Check node's size */ 1786 if (AvailableNode->nVirtualBlockSize > AllocateSize) 1787 { 1788 /* The block contains too much free space, reduce it */ 1789 AvailableNode->pVirtualBlock += AllocateSize; 1790 AvailableNode->nVirtualBlockSize -= AllocateSize; 1791 DphRoot->nAvailableAllocationBytesCommitted -= AllocateSize; 1792 1793 /* Allocate a new node which will be our busy node */ 1794 BusyNode = RtlpDphAllocateNode(DphRoot); 1795 ASSERT(BusyNode != NULL); 1796 BusyNode->pVirtualBlock = Ptr; 1797 BusyNode->nVirtualBlockSize = AllocateSize; 1798 } 1799 else 1800 { 1801 /* The block's size fits exactly */ 1802 RtlpDphRemoveFromAvailableList(DphRoot, AvailableNode); 1803 BusyNode = AvailableNode; 1804 } 1805 1806 /* Calculate actual user size */ 1807 if (DphRoot->HeapFlags & HEAP_NO_ALIGNMENT) 1808 UserActualSize = Size; 1809 else 1810 UserActualSize = ROUND_UP(Size, 8); 1811 1812 /* Set up the block */ 1813 BusyNode->nVirtualAccessSize = AccessSize; 1814 BusyNode->nUserActualSize = UserActualSize; 1815 BusyNode->nUserRequestedSize = Size; 1816 1817 if (DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN) 1818 BusyNode->pUserAllocation = BusyNode->pVirtualBlock + PAGE_SIZE; 1819 else 1820 BusyNode->pUserAllocation = BusyNode->pVirtualBlock + BusyNode->nVirtualAccessSize - UserActualSize; 1821 1822 BusyNode->UserValue = NULL; 1823 BusyNode->UserFlags = Flags & HEAP_SETTABLE_USER_FLAGS; 1824 1825 // FIXME: Don't forget about stack traces if such flag was set 1826 BusyNode->StackTrace = NULL; 1827 1828 /* Place it on busy list */ 1829 RtlpDphPlaceOnBusyList(DphRoot, BusyNode); 1830 1831 /* Zero or patter-fill memory depending on flags */ 1832 if (Flags & HEAP_ZERO_MEMORY) 1833 RtlZeroMemory(BusyNode->pUserAllocation, Size); 1834 else 1835 RtlFillMemory(BusyNode->pUserAllocation, Size, DPH_FILL_INFIX); 1836 1837 /* Write DPH info */ 1838 if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)) 1839 { 1840 RtlpDphWritePageHeapBlockInformation(DphRoot, 1841 BusyNode->pUserAllocation, 1842 Size, 1843 AccessSize); 1844 } 1845 1846 /* Finally allocation is done, perform validation again if required */ 1847 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased) 1848 { 1849 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 1850 } 1851 1852 /* Release the lock */ 1853 RtlpDphPostProcessing(DphRoot); 1854 1855 DPRINT("Allocated user block pointer: %p\n", BusyNode->pUserAllocation); 1856 1857 /* Return pointer to user allocation */ 1858 return BusyNode->pUserAllocation; 1859 } 1860 1861 BOOLEAN NTAPI 1862 RtlpPageHeapFree(HANDLE HeapPtr, 1863 ULONG Flags, 1864 PVOID Ptr) 1865 { 1866 PDPH_HEAP_ROOT DphRoot; 1867 PDPH_HEAP_BLOCK Node; 1868 ULONG ValidationInfo; 1869 PDPH_BLOCK_INFORMATION Info; 1870 1871 /* Check for a NULL pointer freeing */ 1872 if (!Ptr) 1873 { 1874 if (RtlpDphBreakOptions & DPH_BREAK_ON_NULL_FREE) 1875 { 1876 DPRINT1("Page heap: freeing a null pointer \n"); 1877 DbgBreakPoint(); 1878 } 1879 return TRUE; 1880 } 1881 1882 /* Get a pointer to the heap root */ 1883 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 1884 if (!DphRoot) return FALSE; 1885 1886 /* Acquire the heap lock */ 1887 RtlpDphPreProcessing(DphRoot, Flags); 1888 1889 /* Perform internal validation if specified by flags */ 1890 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE) 1891 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 1892 1893 /* Add heap flags */ 1894 Flags |= DphRoot->HeapFlags; 1895 1896 /* Find busy memory */ 1897 Node = RtlpDphFindBusyMemory(DphRoot, Ptr); 1898 1899 if (!Node) 1900 { 1901 /* This block was not found in page heap, try a normal heap instead */ 1902 //RtlpDphNormalHeapFree(); 1903 ASSERT(FALSE); 1904 } 1905 1906 if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)) 1907 { 1908 /* Check and report corrupted block */ 1909 if (!RtlpDphIsPageHeapBlock(DphRoot, Ptr, &ValidationInfo, TRUE)) 1910 { 1911 RtlpDphReportCorruptedBlock(DphRoot, 1, Ptr, ValidationInfo); 1912 } 1913 1914 // FIXME: Should go inside RtlpDphSetProtectionAfterUse 1915 if (Node->nVirtualAccessSize != 0) 1916 { 1917 /* Set stamps */ 1918 Info = (PDPH_BLOCK_INFORMATION)Node->pUserAllocation - 1; 1919 Info->StartStamp = DPH_FILL_START_STAMP_2; 1920 Info->EndStamp = DPH_FILL_END_STAMP_2; 1921 1922 RtlpDphProtectVm(Node->pVirtualBlock, Node->nVirtualAccessSize, PAGE_NOACCESS); 1923 } 1924 } 1925 else 1926 { 1927 // FIXME: Should go inside RtlpDphSetProtectionAfterUse 1928 if (Node->nVirtualAccessSize != 0) 1929 RtlpDphProtectVm(Node->pVirtualBlock + PAGE_SIZE, Node->nVirtualAccessSize, PAGE_NOACCESS); 1930 } 1931 1932 /* Set new protection */ 1933 //RtlpDphSetProtectionAfterUse(DphRoot, Node); 1934 1935 /* Remove it from the list of busy nodes */ 1936 RtlpDphRemoveFromBusyList(DphRoot, Node); 1937 1938 /* And put it into the list of free nodes */ 1939 RtlpDphPlaceOnFreeList(DphRoot, Node); 1940 1941 //if (DphRoot->ExtraFlags & DPH_EXTRA_LOG_STACK_TRACES) 1942 // Node->StackTrace = RtlpDphLogStackTrace(3); 1943 //else 1944 Node->StackTrace = NULL; 1945 1946 /* Leave the heap lock */ 1947 RtlpDphPostProcessing(DphRoot); 1948 1949 /* Return success */ 1950 return TRUE; 1951 } 1952 1953 PVOID NTAPI 1954 RtlpPageHeapReAllocate(HANDLE HeapPtr, 1955 ULONG Flags, 1956 PVOID Ptr, 1957 SIZE_T Size) 1958 { 1959 PDPH_HEAP_ROOT DphRoot; 1960 PDPH_HEAP_BLOCK Node = NULL, AllocatedNode; 1961 BOOLEAN Biased = FALSE, UseNormalHeap = FALSE, OldBlockPageHeap = TRUE; 1962 ULONG ValidationInfo; 1963 SIZE_T DataSize; 1964 PVOID NewAlloc = NULL; 1965 1966 /* Check requested size */ 1967 if (Size > 0x7FF00000) 1968 { 1969 DPRINT1("extreme size request\n"); 1970 1971 /* Generate an exception if needed */ 1972 if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY); 1973 1974 return NULL; 1975 } 1976 1977 /* Unbias the pointer if necessary */ 1978 if (IS_BIASED_POINTER(HeapPtr)) 1979 { 1980 HeapPtr = (PVOID)POINTER_REMOVE_BIAS(HeapPtr); 1981 Biased = TRUE; 1982 } 1983 1984 /* Get a pointer to the heap root */ 1985 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 1986 if (!DphRoot) return NULL; 1987 1988 /* Acquire the heap lock */ 1989 RtlpDphPreProcessing(DphRoot, Flags); 1990 1991 /* Perform internal validation if specified by flags */ 1992 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE) 1993 { 1994 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 1995 } 1996 1997 /* Add heap flags */ 1998 Flags |= DphRoot->HeapFlags; 1999 2000 /* Exit with NULL right away if inplace is specified */ 2001 if (Flags & HEAP_REALLOC_IN_PLACE_ONLY) 2002 { 2003 /* Release the lock */ 2004 RtlpDphPostProcessing(DphRoot); 2005 2006 /* Generate an exception if needed */ 2007 if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY); 2008 2009 return NULL; 2010 } 2011 2012 /* Try to get node of the allocated block */ 2013 AllocatedNode = RtlpDphFindBusyMemory(DphRoot, Ptr); 2014 2015 if (!AllocatedNode) 2016 { 2017 /* This block was not found in page heap, try a normal heap instead */ 2018 //RtlpDphNormalHeapFree(); 2019 ASSERT(FALSE); 2020 OldBlockPageHeap = FALSE; 2021 } 2022 2023 /* Check the block */ 2024 if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)) 2025 { 2026 if (!RtlpDphIsPageHeapBlock(DphRoot, AllocatedNode->pUserAllocation, &ValidationInfo, TRUE)) 2027 { 2028 RtlpDphReportCorruptedBlock(DphRoot, 3, AllocatedNode->pUserAllocation, ValidationInfo); 2029 } 2030 } 2031 2032 /* Remove old one from the busy list */ 2033 RtlpDphRemoveFromBusyList(DphRoot, AllocatedNode); 2034 2035 if (!Biased && !RtlpDphShouldAllocateInPageHeap(DphRoot, Size)) 2036 { 2037 // FIXME: Use normal heap 2038 ASSERT(FALSE); 2039 UseNormalHeap = TRUE; 2040 } 2041 else 2042 { 2043 /* Now do a trick: bias the pointer and call our allocate routine */ 2044 NewAlloc = RtlpPageHeapAllocate((PVOID)POINTER_ADD_BIAS(HeapPtr), Flags, Size); 2045 } 2046 2047 if (!NewAlloc) 2048 { 2049 /* New allocation failed, put the block back (if it was found in page heap) */ 2050 RtlpDphPlaceOnBusyList(DphRoot, AllocatedNode); 2051 2052 /* Release the lock */ 2053 RtlpDphPostProcessing(DphRoot); 2054 2055 /* Perform validation again if required */ 2056 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE) 2057 { 2058 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 2059 } 2060 2061 /* Generate an exception if needed */ 2062 if (Flags & HEAP_GENERATE_EXCEPTIONS) RtlpDphRaiseException(STATUS_NO_MEMORY); 2063 2064 return NULL; 2065 } 2066 2067 /* Copy contents of the old block */ 2068 if (AllocatedNode->nUserRequestedSize > Size) 2069 DataSize = Size; 2070 else 2071 DataSize = AllocatedNode->nUserRequestedSize; 2072 2073 if (DataSize != 0) RtlCopyMemory(NewAlloc, Ptr, DataSize); 2074 2075 /* Copy user flags and values */ 2076 if (!UseNormalHeap) 2077 { 2078 /* Get the node of the new block */ 2079 Node = RtlpDphFindBusyMemory(DphRoot, NewAlloc); 2080 ASSERT(Node != NULL); 2081 2082 /* Set its values/flags */ 2083 Node->UserValue = AllocatedNode->UserValue; 2084 if (Flags & HEAP_SETTABLE_USER_FLAGS) 2085 Node->UserFlags = Flags & HEAP_SETTABLE_USER_FLAGS; 2086 else 2087 Node->UserFlags = AllocatedNode->UserFlags; 2088 } 2089 2090 if (!OldBlockPageHeap) 2091 { 2092 /* Weird scenario, investigate */ 2093 ASSERT(FALSE); 2094 } 2095 2096 /* Mark the old block as no access */ 2097 if (AllocatedNode->nVirtualAccessSize != 0) 2098 { 2099 RtlpDphProtectVm(AllocatedNode->pVirtualBlock, AllocatedNode->nVirtualAccessSize, PAGE_NOACCESS); 2100 } 2101 2102 /* And place it on the free list */ 2103 RtlpDphPlaceOnFreeList(DphRoot, AllocatedNode); 2104 2105 // FIXME: Capture stack traces if needed 2106 AllocatedNode->StackTrace = NULL; 2107 2108 /* Finally allocation is done, perform validation again if required */ 2109 if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE && !Biased) 2110 { 2111 RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0); 2112 } 2113 2114 /* Release the lock */ 2115 RtlpDphPostProcessing(DphRoot); 2116 2117 DPRINT("Allocated new user block pointer: %p\n", NewAlloc); 2118 2119 /* Return pointer to user allocation */ 2120 return NewAlloc; 2121 } 2122 2123 BOOLEAN NTAPI 2124 RtlpPageHeapGetUserInfo(PVOID HeapHandle, 2125 ULONG Flags, 2126 PVOID BaseAddress, 2127 PVOID *UserValue, 2128 PULONG UserFlags) 2129 { 2130 PDPH_HEAP_ROOT DphRoot; 2131 PDPH_HEAP_BLOCK Node; 2132 2133 /* Get a pointer to the heap root */ 2134 DphRoot = RtlpDphPointerFromHandle(HeapHandle); 2135 if (!DphRoot) return FALSE; 2136 2137 /* Add heap flags */ 2138 Flags |= DphRoot->HeapFlags; 2139 2140 /* Acquire the heap lock */ 2141 RtlpDphPreProcessing(DphRoot, Flags); 2142 2143 /* Find busy memory */ 2144 Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress); 2145 2146 if (!Node) 2147 { 2148 /* This block was not found in page heap, try a normal heap instead */ 2149 //RtlpDphNormalHeapGetUserInfo(); 2150 ASSERT(FALSE); 2151 return FALSE; 2152 } 2153 2154 /* Get user values and flags and store them in user provided pointers */ 2155 if (UserValue) *UserValue = Node->UserValue; 2156 if (UserFlags) *UserFlags = Node->UserFlags; 2157 2158 /* Leave the heap lock */ 2159 RtlpDphPostProcessing(DphRoot); 2160 2161 /* Return success */ 2162 return TRUE; 2163 } 2164 2165 BOOLEAN NTAPI 2166 RtlpPageHeapSetUserValue(PVOID HeapHandle, 2167 ULONG Flags, 2168 PVOID BaseAddress, 2169 PVOID UserValue) 2170 { 2171 PDPH_HEAP_ROOT DphRoot; 2172 PDPH_HEAP_BLOCK Node; 2173 2174 /* Get a pointer to the heap root */ 2175 DphRoot = RtlpDphPointerFromHandle(HeapHandle); 2176 if (!DphRoot) return FALSE; 2177 2178 /* Add heap flags */ 2179 Flags |= DphRoot->HeapFlags; 2180 2181 /* Acquire the heap lock */ 2182 RtlpDphPreProcessing(DphRoot, Flags); 2183 2184 /* Find busy memory */ 2185 Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress); 2186 2187 if (!Node) 2188 { 2189 /* This block was not found in page heap, try a normal heap instead */ 2190 //RtlpDphNormalHeapSetUserValue(); 2191 ASSERT(FALSE); 2192 return FALSE; 2193 } 2194 2195 /* Get user values and flags and store them in user provided pointers */ 2196 Node->UserValue = UserValue; 2197 2198 /* Leave the heap lock */ 2199 RtlpDphPostProcessing(DphRoot); 2200 2201 /* Return success */ 2202 return TRUE; 2203 } 2204 2205 BOOLEAN 2206 NTAPI 2207 RtlpPageHeapSetUserFlags(PVOID HeapHandle, 2208 ULONG Flags, 2209 PVOID BaseAddress, 2210 ULONG UserFlagsReset, 2211 ULONG UserFlagsSet) 2212 { 2213 PDPH_HEAP_ROOT DphRoot; 2214 PDPH_HEAP_BLOCK Node; 2215 2216 /* Get a pointer to the heap root */ 2217 DphRoot = RtlpDphPointerFromHandle(HeapHandle); 2218 if (!DphRoot) return FALSE; 2219 2220 /* Add heap flags */ 2221 Flags |= DphRoot->HeapFlags; 2222 2223 /* Acquire the heap lock */ 2224 RtlpDphPreProcessing(DphRoot, Flags); 2225 2226 /* Find busy memory */ 2227 Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress); 2228 2229 if (!Node) 2230 { 2231 /* This block was not found in page heap, try a normal heap instead */ 2232 //RtlpDphNormalHeapSetUserFlags(); 2233 ASSERT(FALSE); 2234 return FALSE; 2235 } 2236 2237 /* Get user values and flags and store them in user provided pointers */ 2238 Node->UserFlags &= ~(UserFlagsReset); 2239 Node->UserFlags |= UserFlagsSet; 2240 2241 /* Leave the heap lock */ 2242 RtlpDphPostProcessing(DphRoot); 2243 2244 /* Return success */ 2245 return TRUE; 2246 } 2247 2248 SIZE_T NTAPI 2249 RtlpPageHeapSize(HANDLE HeapHandle, 2250 ULONG Flags, 2251 PVOID BaseAddress) 2252 { 2253 PDPH_HEAP_ROOT DphRoot; 2254 PDPH_HEAP_BLOCK Node; 2255 SIZE_T Size; 2256 2257 /* Get a pointer to the heap root */ 2258 DphRoot = RtlpDphPointerFromHandle(HeapHandle); 2259 if (!DphRoot) return -1; 2260 2261 /* Add heap flags */ 2262 Flags |= DphRoot->HeapFlags; 2263 2264 /* Acquire the heap lock */ 2265 RtlpDphPreProcessing(DphRoot, Flags); 2266 2267 /* Find busy memory */ 2268 Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress); 2269 2270 if (!Node) 2271 { 2272 /* This block was not found in page heap, try a normal heap instead */ 2273 //RtlpDphNormalHeapSize(); 2274 ASSERT(FALSE); 2275 return -1; 2276 } 2277 2278 /* Get heap block size */ 2279 Size = Node->nUserRequestedSize; 2280 2281 /* Leave the heap lock */ 2282 RtlpDphPostProcessing(DphRoot); 2283 2284 /* Return user requested size */ 2285 return Size; 2286 } 2287 2288 BOOLEAN 2289 NTAPI 2290 RtlpDebugPageHeapValidate(PVOID HeapHandle, 2291 ULONG Flags, 2292 PVOID BaseAddress) 2293 { 2294 PDPH_HEAP_ROOT DphRoot; 2295 PDPH_HEAP_BLOCK Node = NULL; 2296 BOOLEAN Valid = FALSE; 2297 2298 /* Get a pointer to the heap root */ 2299 DphRoot = RtlpDphPointerFromHandle(HeapHandle); 2300 if (!DphRoot) return -1; 2301 2302 /* Add heap flags */ 2303 Flags |= DphRoot->HeapFlags; 2304 2305 /* Acquire the heap lock */ 2306 RtlpDphPreProcessing(DphRoot, Flags); 2307 2308 /* Find busy memory */ 2309 if (BaseAddress) 2310 Node = RtlpDphFindBusyMemory(DphRoot, BaseAddress); 2311 2312 if (!Node) 2313 { 2314 /* This block was not found in page heap, or the request is to validate all normal heap */ 2315 Valid = RtlpDphNormalHeapValidate(DphRoot, Flags, BaseAddress); 2316 } 2317 2318 /* Leave the heap lock */ 2319 RtlpDphPostProcessing(DphRoot); 2320 2321 /* Return result of a normal heap validation */ 2322 if (BaseAddress && !Node) 2323 return Valid; 2324 2325 /* Otherwise return our own result */ 2326 if (!BaseAddress || Node) Valid = TRUE; 2327 2328 return Valid; 2329 } 2330 2331 BOOLEAN 2332 NTAPI 2333 RtlpDphNormalHeapValidate(PDPH_HEAP_ROOT DphRoot, 2334 ULONG Flags, 2335 PVOID BaseAddress) 2336 { 2337 PDPH_BLOCK_INFORMATION BlockInfo = (PDPH_BLOCK_INFORMATION)BaseAddress - 1; 2338 if (!BaseAddress) 2339 { 2340 /* Validate all normal heap */ 2341 return RtlValidateHeap(DphRoot->NormalHeap, Flags, NULL); 2342 } 2343 2344 // FIXME: Check is this a normal heap block 2345 /*if (!RtlpDphIsNormalHeapBlock(DphRoot, BaseAddress, &ValidationInfo)) 2346 { 2347 }*/ 2348 2349 return RtlValidateHeap(DphRoot->NormalHeap, Flags, BlockInfo); 2350 } 2351 2352 BOOLEAN 2353 NTAPI 2354 RtlpPageHeapLock(HANDLE HeapPtr) 2355 { 2356 PDPH_HEAP_ROOT DphRoot; 2357 2358 /* Get pointer to the heap root */ 2359 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 2360 if (!DphRoot) return FALSE; 2361 2362 RtlpDphEnterCriticalSection(DphRoot, DphRoot->HeapFlags); 2363 return TRUE; 2364 } 2365 2366 BOOLEAN 2367 NTAPI 2368 RtlpPageHeapUnlock(HANDLE HeapPtr) 2369 { 2370 PDPH_HEAP_ROOT DphRoot; 2371 2372 /* Get pointer to the heap root */ 2373 DphRoot = RtlpDphPointerFromHandle(HeapPtr); 2374 if (!DphRoot) return FALSE; 2375 2376 RtlpDphLeaveCriticalSection(DphRoot); 2377 return TRUE; 2378 } 2379 2380 /* EOF */ 2381