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