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