[RTL]
[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 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 /* EOF */