1 /* COPYRIGHT: See COPYING in the top level directory
2 * PROJECT: ReactOS system libraries
4 * PURPOSE: RTL Heap backend allocator
5 * PROGRAMMERS: Copyright 2010 Aleksey Bragin
9 http://msdn.microsoft.com/en-us/library/ms810466.aspx
10 http://msdn.microsoft.com/en-us/library/ms810603.aspx
11 http://www.securitylab.ru/analytics/216376.php
12 http://binglongx.spaces.live.com/blog/cns!142CBF6D49079DE8!596.entry
13 http://www.phreedom.org/research/exploits/asn1-bitstring/
14 http://illmatics.com/Understanding_the_LFH.pdf
15 http://www.alex-ionescu.com/?p=18
18 /* INCLUDES *****************************************************************/
26 RTL_CRITICAL_SECTION RtlpProcessHeapsListLock
;
30 /* How many least significant bits are clear */
31 UCHAR RtlpBitsClearLow
[] =
33 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
34 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
35 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
36 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
37 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
38 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
39 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
40 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
41 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
42 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
43 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
44 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
45 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
46 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
47 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
48 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
52 RtlpFindLeastSetBit(ULONG Bits
)
57 return RtlpBitsClearLow
[Bits
& 0xFF]; /* Lowest byte */
59 return RtlpBitsClearLow
[(Bits
>> 8) & 0xFF] + 8; /* 2nd byte */
63 if ((Bits
>> 16) & 0xFF)
64 return RtlpBitsClearLow
[(Bits
>> 16) & 0xFF] + 16; /* 3rd byte */
66 return RtlpBitsClearLow
[(Bits
>> 24) & 0xFF] + 24; /* Highest byte */
70 /* Maximum size of a tail-filling pattern used for compare operation */
71 UCHAR FillPattern
[HEAP_ENTRY_SIZE
] =
83 /* FUNCTIONS *****************************************************************/
86 RtlpInitializeHeap(OUT PHEAP Heap
,
88 IN PHEAP_LOCK Lock OPTIONAL
,
89 IN PRTL_HEAP_PARAMETERS Parameters
)
95 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
99 ASSERT(Parameters
!= NULL
);
100 ASSERT(!(Flags
& HEAP_LOCK_USER_ALLOCATED
));
101 ASSERT(!(Flags
& HEAP_NO_SERIALIZE
) || (Lock
== NULL
)); /* HEAP_NO_SERIALIZE => no lock */
103 /* Start out with the size of a plain Heap header */
104 HeaderSize
= ROUND_UP(sizeof(HEAP
), sizeof(HEAP_ENTRY
));
106 /* Check if space needs to be added for the Heap Lock */
107 if (!(Flags
& HEAP_NO_SERIALIZE
))
110 /* The user manages the Heap Lock */
111 Flags
|= HEAP_LOCK_USER_ALLOCATED
;
113 if (RtlpGetMode() == UserMode
)
115 /* In user mode, the Heap Lock trails the Heap header */
116 Lock
= (PHEAP_LOCK
) ((ULONG_PTR
) (Heap
) + HeaderSize
);
117 HeaderSize
+= ROUND_UP(sizeof(HEAP_LOCK
), sizeof(HEAP_ENTRY
));
121 /* Add space for the initial Heap UnCommitted Range Descriptor list */
122 UcrDescriptor
= (PHEAP_UCR_DESCRIPTOR
) ((ULONG_PTR
) (Heap
) + HeaderSize
);
123 HeaderSize
+= ROUND_UP(NumUCRs
* sizeof(HEAP_UCR_DESCRIPTOR
), sizeof(HEAP_ENTRY
));
126 ASSERT(HeaderSize
<= PAGE_SIZE
);
128 /* Initialise the Heap Entry header containing the Heap header */
129 Heap
->Entry
.Size
= (USHORT
)(HeaderSize
>> HEAP_ENTRY_SHIFT
);
130 Heap
->Entry
.Flags
= HEAP_ENTRY_BUSY
;
131 Heap
->Entry
.SmallTagIndex
= LOBYTE(Heap
->Entry
.Size
) ^ HIBYTE(Heap
->Entry
.Size
) ^ Heap
->Entry
.Flags
;
132 Heap
->Entry
.PreviousSize
= 0;
133 Heap
->Entry
.SegmentOffset
= 0;
134 Heap
->Entry
.UnusedBytes
= 0;
136 /* Initialise the Heap header */
137 Heap
->Signature
= HEAP_SIGNATURE
;
139 Heap
->ForceFlags
= (Flags
& (HEAP_NO_SERIALIZE
|
140 HEAP_GENERATE_EXCEPTIONS
|
142 HEAP_REALLOC_IN_PLACE_ONLY
|
143 HEAP_VALIDATE_PARAMETERS_ENABLED
|
144 HEAP_VALIDATE_ALL_ENABLED
|
145 HEAP_TAIL_CHECKING_ENABLED
|
146 HEAP_CREATE_ALIGN_16
|
147 HEAP_FREE_CHECKING_ENABLED
));
149 /* Initialise the Heap parameters */
150 Heap
->VirtualMemoryThreshold
= ROUND_UP(Parameters
->VirtualMemoryThreshold
, sizeof(HEAP_ENTRY
)) >> HEAP_ENTRY_SHIFT
;
151 Heap
->SegmentReserve
= Parameters
->SegmentReserve
;
152 Heap
->SegmentCommit
= Parameters
->SegmentCommit
;
153 Heap
->DeCommitFreeBlockThreshold
= Parameters
->DeCommitFreeBlockThreshold
>> HEAP_ENTRY_SHIFT
;
154 Heap
->DeCommitTotalFreeThreshold
= Parameters
->DeCommitTotalFreeThreshold
>> HEAP_ENTRY_SHIFT
;
155 Heap
->MaximumAllocationSize
= Parameters
->MaximumAllocationSize
;
156 Heap
->CommitRoutine
= Parameters
->CommitRoutine
;
158 /* Initialise the Heap validation info */
159 Heap
->HeaderValidateCopy
= NULL
;
160 Heap
->HeaderValidateLength
= (USHORT
)HeaderSize
;
162 /* Initialise the Heap Lock */
163 if (!(Flags
& HEAP_NO_SERIALIZE
) && !(Flags
& HEAP_LOCK_USER_ALLOCATED
))
165 Status
= RtlInitializeHeapLock(&Lock
);
166 if (!NT_SUCCESS(Status
))
169 Heap
->LockVariable
= Lock
;
171 /* Initialise the Heap alignment info */
172 if (Flags
& HEAP_CREATE_ALIGN_16
)
174 Heap
->AlignMask
= (ULONG
) ~15;
175 Heap
->AlignRound
= 15 + sizeof(HEAP_ENTRY
);
179 Heap
->AlignMask
= (ULONG
) ~(sizeof(HEAP_ENTRY
) - 1);
180 Heap
->AlignRound
= 2 * sizeof(HEAP_ENTRY
) - 1;
183 if (Flags
& HEAP_TAIL_CHECKING_ENABLED
)
184 Heap
->AlignRound
+= sizeof(HEAP_ENTRY
);
186 /* Initialise the Heap Segment list */
187 for (Index
= 0; Index
< HEAP_SEGMENTS
; ++Index
)
188 Heap
->Segments
[Index
] = NULL
;
190 /* Initialise the Heap Free Heap Entry lists */
191 for (Index
= 0; Index
< HEAP_FREELISTS
; ++Index
)
192 InitializeListHead(&Heap
->FreeLists
[Index
]);
194 /* Initialise the Heap Virtual Allocated Blocks list */
195 InitializeListHead(&Heap
->VirtualAllocdBlocks
);
197 /* Initialise the Heap UnCommitted Region lists */
198 InitializeListHead(&Heap
->UCRSegments
);
199 InitializeListHead(&Heap
->UCRList
);
201 /* Register the initial Heap UnCommitted Region Descriptors */
202 for (Index
= 0; Index
< NumUCRs
; ++Index
)
203 InsertTailList(&Heap
->UCRList
, &UcrDescriptor
[Index
].ListEntry
);
205 return STATUS_SUCCESS
;
209 RtlpSetFreeListsBit(PHEAP Heap
,
210 PHEAP_FREE_ENTRY FreeEntry
)
214 ASSERT(FreeEntry
->Size
< HEAP_FREELISTS
);
216 /* Calculate offset in the free list bitmap */
217 Index
= FreeEntry
->Size
>> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
218 Bit
= 1 << (FreeEntry
->Size
& 7);
220 /* Assure it's not already set */
221 ASSERT((Heap
->u
.FreeListsInUseBytes
[Index
] & Bit
) == 0);
224 Heap
->u
.FreeListsInUseBytes
[Index
] |= Bit
;
228 RtlpClearFreeListsBit(PHEAP Heap
,
229 PHEAP_FREE_ENTRY FreeEntry
)
233 ASSERT(FreeEntry
->Size
< HEAP_FREELISTS
);
235 /* Calculate offset in the free list bitmap */
236 Index
= FreeEntry
->Size
>> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
237 Bit
= 1 << (FreeEntry
->Size
& 7);
239 /* Assure it was set and the corresponding free list is empty */
240 ASSERT(Heap
->u
.FreeListsInUseBytes
[Index
] & Bit
);
241 ASSERT(IsListEmpty(&Heap
->FreeLists
[FreeEntry
->Size
]));
244 Heap
->u
.FreeListsInUseBytes
[Index
] ^= Bit
;
248 RtlpInsertFreeBlockHelper(PHEAP Heap
,
249 PHEAP_FREE_ENTRY FreeEntry
,
253 PLIST_ENTRY FreeListHead
, Current
;
254 PHEAP_FREE_ENTRY CurrentEntry
;
256 ASSERT(FreeEntry
->Size
== BlockSize
);
258 /* Fill if it's not denied */
261 FreeEntry
->Flags
&= ~(HEAP_ENTRY_FILL_PATTERN
|
262 HEAP_ENTRY_EXTRA_PRESENT
|
265 if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
267 RtlFillMemoryUlong((PCHAR
)(FreeEntry
+ 1),
268 (BlockSize
<< HEAP_ENTRY_SHIFT
) - sizeof(*FreeEntry
),
271 FreeEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
276 /* Clear out all flags except the last entry one */
277 FreeEntry
->Flags
&= HEAP_ENTRY_LAST_ENTRY
;
280 /* Insert it either into dedicated or non-dedicated list */
281 if (BlockSize
< HEAP_FREELISTS
)
284 FreeListHead
= &Heap
->FreeLists
[BlockSize
];
286 if (IsListEmpty(FreeListHead
))
288 RtlpSetFreeListsBit(Heap
, FreeEntry
);
293 /* Non-dedicated one */
294 FreeListHead
= &Heap
->FreeLists
[0];
295 Current
= FreeListHead
->Flink
;
297 /* Find a position where to insert it to (the list must be sorted) */
298 while (FreeListHead
!= Current
)
300 CurrentEntry
= CONTAINING_RECORD(Current
, HEAP_FREE_ENTRY
, FreeList
);
302 if (BlockSize
<= CurrentEntry
->Size
)
305 Current
= Current
->Flink
;
308 FreeListHead
= Current
;
311 /* Actually insert it into the list */
312 InsertTailList(FreeListHead
, &FreeEntry
->FreeList
);
316 RtlpInsertFreeBlock(PHEAP Heap
,
317 PHEAP_FREE_ENTRY FreeEntry
,
320 USHORT Size
, PreviousSize
;
321 UCHAR SegmentOffset
, Flags
;
322 PHEAP_SEGMENT Segment
;
324 DPRINT("RtlpInsertFreeBlock(%p %p %x)\n", Heap
, FreeEntry
, BlockSize
);
326 /* Increase the free size counter */
327 Heap
->TotalFreeSize
+= BlockSize
;
329 /* Remember certain values */
330 Flags
= FreeEntry
->Flags
;
331 PreviousSize
= FreeEntry
->PreviousSize
;
332 SegmentOffset
= FreeEntry
->SegmentOffset
;
333 Segment
= Heap
->Segments
[SegmentOffset
];
338 /* Check for the max size */
339 if (BlockSize
> HEAP_MAX_BLOCK_SIZE
)
341 Size
= HEAP_MAX_BLOCK_SIZE
;
343 /* Special compensation if it goes above limit just by 1 */
344 if (BlockSize
== (HEAP_MAX_BLOCK_SIZE
+ 1))
347 FreeEntry
->Flags
= 0;
351 Size
= (USHORT
)BlockSize
;
352 FreeEntry
->Flags
= Flags
;
355 /* Change its size and insert it into a free list */
356 FreeEntry
->Size
= Size
;
357 FreeEntry
->PreviousSize
= PreviousSize
;
358 FreeEntry
->SegmentOffset
= SegmentOffset
;
360 /* Call a helper to actually insert the block */
361 RtlpInsertFreeBlockHelper(Heap
, FreeEntry
, Size
, FALSE
);
367 /* Go to the next entry */
368 FreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ Size
);
370 /* Check if that's all */
371 if ((PHEAP_ENTRY
)FreeEntry
>= Segment
->LastValidEntry
) return;
374 /* Update previous size if needed */
375 if (!(Flags
& HEAP_ENTRY_LAST_ENTRY
))
376 FreeEntry
->PreviousSize
= PreviousSize
;
380 RtlpRemoveFreeBlock(PHEAP Heap
,
381 PHEAP_FREE_ENTRY FreeEntry
,
385 SIZE_T Result
, RealSize
;
387 /* Remove the free block and update the freelists bitmap */
388 if (RemoveEntryList(&FreeEntry
->FreeList
) &&
389 (Dedicated
|| (!Dedicated
&& FreeEntry
->Size
< HEAP_FREELISTS
)))
391 RtlpClearFreeListsBit(Heap
, FreeEntry
);
394 /* Fill with pattern if necessary */
396 (FreeEntry
->Flags
& HEAP_ENTRY_FILL_PATTERN
))
398 RealSize
= (FreeEntry
->Size
<< HEAP_ENTRY_SHIFT
) - sizeof(*FreeEntry
);
400 /* Deduct extra stuff from block's real size */
401 if (FreeEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
&&
402 RealSize
> sizeof(HEAP_FREE_ENTRY_EXTRA
))
404 RealSize
-= sizeof(HEAP_FREE_ENTRY_EXTRA
);
407 /* Check if the free filler is intact */
408 Result
= RtlCompareMemoryUlong((PCHAR
)(FreeEntry
+ 1),
412 if (Result
!= RealSize
)
414 DPRINT1("Free heap block %p modified at %p after it was freed\n",
416 (PCHAR
)(FreeEntry
+ 1) + Result
);
422 RtlpGetSizeOfBigBlock(PHEAP_ENTRY HeapEntry
)
424 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
426 /* Get pointer to the containing record */
427 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
429 /* Restore the real size */
430 return VirtualEntry
->CommitSize
- HeapEntry
->Size
;
433 PHEAP_UCR_DESCRIPTOR NTAPI
434 RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment
)
437 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
438 PHEAP_UCR_SEGMENT UcrSegment
;
439 PHEAP Heap
= Segment
->Heap
;
440 SIZE_T ReserveSize
= 16 * PAGE_SIZE
;
441 SIZE_T CommitSize
= 1 * PAGE_SIZE
;
444 DPRINT("RtlpCreateUnCommittedRange(%p)\n", Segment
);
446 /* Check if we have unused UCRs */
447 if (IsListEmpty(&Heap
->UCRList
))
449 /* Get a pointer to the first UCR segment */
450 UcrSegment
= CONTAINING_RECORD(Heap
->UCRSegments
.Flink
, HEAP_UCR_SEGMENT
, ListEntry
);
452 /* Check the list of UCR segments */
453 if (IsListEmpty(&Heap
->UCRSegments
) ||
454 UcrSegment
->ReservedSize
== UcrSegment
->CommittedSize
)
456 /* We need to create a new one. Reserve 16 pages for it */
458 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
459 (PVOID
*)&UcrSegment
,
465 if (!NT_SUCCESS(Status
)) return NULL
;
467 /* Commit one page */
468 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
469 (PVOID
*)&UcrSegment
,
475 if (!NT_SUCCESS(Status
))
477 /* Release reserved memory */
478 ZwFreeVirtualMemory(NtCurrentProcess(),
479 (PVOID
*)&UcrDescriptor
,
486 UcrSegment
->ReservedSize
= ReserveSize
;
487 UcrSegment
->CommittedSize
= CommitSize
;
489 /* Add it to the head of the list */
490 InsertHeadList(&Heap
->UCRSegments
, &UcrSegment
->ListEntry
);
492 /* Get a pointer to the first available UCR descriptor */
493 UcrDescriptor
= (PHEAP_UCR_DESCRIPTOR
)(UcrSegment
+ 1);
497 /* It's possible to use existing UCR segment. Commit one more page */
498 UcrDescriptor
= (PHEAP_UCR_DESCRIPTOR
)((PCHAR
)UcrSegment
+ UcrSegment
->CommittedSize
);
499 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
500 (PVOID
*)&UcrDescriptor
,
506 if (!NT_SUCCESS(Status
)) return NULL
;
509 UcrSegment
->CommittedSize
+= CommitSize
;
512 /* There is a whole bunch of new UCR descriptors. Put them into the unused list */
513 while ((PCHAR
)UcrDescriptor
< ((PCHAR
)UcrSegment
+ UcrSegment
->CommittedSize
))
515 InsertTailList(&Heap
->UCRList
, &UcrDescriptor
->ListEntry
);
520 /* There are unused UCRs, just get the first one */
521 Entry
= RemoveHeadList(&Heap
->UCRList
);
522 UcrDescriptor
= CONTAINING_RECORD(Entry
, HEAP_UCR_DESCRIPTOR
, ListEntry
);
523 return UcrDescriptor
;
527 RtlpDestroyUnCommittedRange(PHEAP_SEGMENT Segment
,
528 PHEAP_UCR_DESCRIPTOR UcrDescriptor
)
531 UcrDescriptor
->Address
= NULL
;
532 UcrDescriptor
->Size
= 0;
534 /* Put it into the heap's list of unused UCRs */
535 InsertHeadList(&Segment
->Heap
->UCRList
, &UcrDescriptor
->ListEntry
);
539 RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment
,
544 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
546 DPRINT("RtlpInsertUnCommittedPages(%p %p %x)\n", Segment
, Address
, Size
);
548 /* Go through the list of UCR descriptors, they are sorted from lowest address
550 Current
= Segment
->UCRSegmentList
.Flink
;
551 while(Current
!= &Segment
->UCRSegmentList
)
553 UcrDescriptor
= CONTAINING_RECORD(Current
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
555 if ((ULONG_PTR
)UcrDescriptor
->Address
> Address
)
557 /* Check for a really lucky case */
558 if ((Address
+ Size
) == (ULONG_PTR
)UcrDescriptor
->Address
)
561 UcrDescriptor
->Address
= (PVOID
)Address
;
562 UcrDescriptor
->Size
+= Size
;
566 /* We found the block after which the new one should go */
569 else if (((ULONG_PTR
)UcrDescriptor
->Address
+ UcrDescriptor
->Size
) == Address
)
571 /* Modify this entry */
572 Address
= (ULONG_PTR
)UcrDescriptor
->Address
;
573 Size
+= UcrDescriptor
->Size
;
575 /* Advance to the next descriptor */
576 Current
= Current
->Flink
;
578 /* Remove the current descriptor from the list and destroy it */
579 RemoveEntryList(&UcrDescriptor
->SegmentEntry
);
580 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
582 Segment
->NumberOfUnCommittedRanges
--;
586 /* Advance to the next descriptor */
587 Current
= Current
->Flink
;
591 /* Create a new UCR descriptor */
592 UcrDescriptor
= RtlpCreateUnCommittedRange(Segment
);
593 if (!UcrDescriptor
) return;
595 UcrDescriptor
->Address
= (PVOID
)Address
;
596 UcrDescriptor
->Size
= Size
;
598 /* "Current" is the descriptor after which our one should go */
599 InsertTailList(Current
, &UcrDescriptor
->SegmentEntry
);
601 DPRINT("Added segment UCR with base %p, size 0x%x\n", Address
, Size
);
603 /* Increase counters */
604 Segment
->NumberOfUnCommittedRanges
++;
607 PHEAP_FREE_ENTRY NTAPI
608 RtlpFindAndCommitPages(PHEAP Heap
,
609 PHEAP_SEGMENT Segment
,
611 PVOID AddressRequested
)
614 ULONG_PTR Address
= 0;
615 PHEAP_UCR_DESCRIPTOR UcrDescriptor
, PreviousUcr
= NULL
;
616 PHEAP_ENTRY FirstEntry
, LastEntry
;
619 DPRINT("RtlpFindAndCommitPages(%p %p %x %p)\n", Heap
, Segment
, *Size
, Address
);
621 /* Go through UCRs in a segment */
622 Current
= Segment
->UCRSegmentList
.Flink
;
623 while(Current
!= &Segment
->UCRSegmentList
)
625 UcrDescriptor
= CONTAINING_RECORD(Current
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
627 /* Check if we can use that one right away */
628 if (UcrDescriptor
->Size
>= *Size
&&
629 (UcrDescriptor
->Address
== AddressRequested
|| !AddressRequested
))
631 /* Get the address */
632 Address
= (ULONG_PTR
)UcrDescriptor
->Address
;
635 if (Heap
->CommitRoutine
)
637 Status
= Heap
->CommitRoutine(Heap
, (PVOID
*)&Address
, Size
);
641 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
649 DPRINT("Committed %d bytes at base %p, UCR size is %d\n", *Size
, Address
, UcrDescriptor
->Size
);
651 /* Fail in unsuccessful case */
652 if (!NT_SUCCESS(Status
))
654 DPRINT1("Committing page failed with status 0x%08X\n", Status
);
658 /* Update tracking numbers */
659 Segment
->NumberOfUnCommittedPages
-= (ULONG
)(*Size
/ PAGE_SIZE
);
661 /* Calculate first and last entries */
662 FirstEntry
= (PHEAP_ENTRY
)Address
;
664 /* Go through the entries to find the last one */
666 LastEntry
= (PHEAP_ENTRY
)((ULONG_PTR
)PreviousUcr
->Address
+ PreviousUcr
->Size
);
668 LastEntry
= &Segment
->Entry
;
670 while (!(LastEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
672 ASSERT(LastEntry
->Size
!= 0);
673 LastEntry
+= LastEntry
->Size
;
675 ASSERT((LastEntry
+ LastEntry
->Size
) == FirstEntry
);
677 /* Unmark it as a last entry */
678 LastEntry
->Flags
&= ~HEAP_ENTRY_LAST_ENTRY
;
680 /* Update UCR descriptor */
681 UcrDescriptor
->Address
= (PVOID
)((ULONG_PTR
)UcrDescriptor
->Address
+ *Size
);
682 UcrDescriptor
->Size
-= *Size
;
684 DPRINT("Updating UcrDescriptor %p, new Address %p, size %d\n",
685 UcrDescriptor
, UcrDescriptor
->Address
, UcrDescriptor
->Size
);
687 /* Set various first entry fields */
688 FirstEntry
->SegmentOffset
= LastEntry
->SegmentOffset
;
689 FirstEntry
->Size
= (USHORT
)(*Size
>> HEAP_ENTRY_SHIFT
);
690 FirstEntry
->PreviousSize
= LastEntry
->Size
;
692 /* Check if anything left in this UCR */
693 if (UcrDescriptor
->Size
== 0)
695 /* It's fully exhausted */
697 /* Check if this is the end of the segment */
698 if(UcrDescriptor
->Address
== Segment
->LastValidEntry
)
700 FirstEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
704 FirstEntry
->Flags
= 0;
705 /* Update field of next entry */
706 ASSERT((FirstEntry
+ FirstEntry
->Size
)->PreviousSize
== 0);
707 (FirstEntry
+ FirstEntry
->Size
)->PreviousSize
= FirstEntry
->Size
;
710 /* This UCR needs to be removed because it became useless */
711 RemoveEntryList(&UcrDescriptor
->SegmentEntry
);
713 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
714 Segment
->NumberOfUnCommittedRanges
--;
718 FirstEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
722 return (PHEAP_FREE_ENTRY
)FirstEntry
;
725 /* Advance to the next descriptor */
726 PreviousUcr
= UcrDescriptor
;
727 Current
= Current
->Flink
;
734 RtlpDeCommitFreeBlock(PHEAP Heap
,
735 PHEAP_FREE_ENTRY FreeEntry
,
738 PHEAP_SEGMENT Segment
;
739 PHEAP_ENTRY PrecedingInUseEntry
= NULL
, NextInUseEntry
= NULL
;
740 PHEAP_FREE_ENTRY NextFreeEntry
;
741 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
742 SIZE_T PrecedingSize
, NextSize
, DecommitSize
;
743 ULONG_PTR DecommitBase
;
746 DPRINT("Decommitting %p %p %x\n", Heap
, FreeEntry
, Size
);
748 /* We can't decommit if there is a commit routine! */
749 if (Heap
->CommitRoutine
)
751 /* Just add it back the usual way */
752 RtlpInsertFreeBlock(Heap
, FreeEntry
, Size
);
756 /* Get the segment */
757 Segment
= Heap
->Segments
[FreeEntry
->SegmentOffset
];
759 /* Get the preceding entry */
760 DecommitBase
= ROUND_UP(FreeEntry
, PAGE_SIZE
);
761 PrecedingSize
= (PHEAP_ENTRY
)DecommitBase
- (PHEAP_ENTRY
)FreeEntry
;
763 if (PrecedingSize
== 1)
765 /* Just 1 heap entry, increase the base/size */
766 DecommitBase
+= PAGE_SIZE
;
767 PrecedingSize
+= PAGE_SIZE
>> HEAP_ENTRY_SHIFT
;
769 else if (FreeEntry
->PreviousSize
&&
770 (DecommitBase
== (ULONG_PTR
)FreeEntry
))
772 PrecedingInUseEntry
= (PHEAP_ENTRY
)FreeEntry
- FreeEntry
->PreviousSize
;
775 /* Get the next entry */
776 NextFreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ Size
);
777 DecommitSize
= ROUND_DOWN(NextFreeEntry
, PAGE_SIZE
);
778 NextSize
= (PHEAP_ENTRY
)NextFreeEntry
- (PHEAP_ENTRY
)DecommitSize
;
782 /* Just 1 heap entry, increase the size */
783 DecommitSize
-= PAGE_SIZE
;
784 NextSize
+= PAGE_SIZE
>> HEAP_ENTRY_SHIFT
;
786 else if (NextSize
== 0 &&
787 !(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
789 NextInUseEntry
= (PHEAP_ENTRY
)NextFreeEntry
;
792 NextFreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)NextFreeEntry
- NextSize
);
794 /* Calculate real decommit size */
795 if (DecommitSize
> DecommitBase
)
797 DecommitSize
-= DecommitBase
;
801 /* Nothing to decommit */
802 RtlpInsertFreeBlock(Heap
, FreeEntry
, Size
);
806 /* A decommit is necessary. Create a UCR descriptor */
807 UcrDescriptor
= RtlpCreateUnCommittedRange(Segment
);
810 DPRINT1("HEAP: Failed to create UCR descriptor\n");
811 RtlpInsertFreeBlock(Heap
, FreeEntry
, PrecedingSize
);
815 /* Decommit the memory */
816 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
817 (PVOID
*)&DecommitBase
,
821 /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */
822 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
824 if (!NT_SUCCESS(Status
))
826 RtlpInsertFreeBlock(Heap
, FreeEntry
, Size
);
830 /* Insert uncommitted pages */
831 RtlpInsertUnCommittedPages(Segment
, DecommitBase
, DecommitSize
);
832 Segment
->NumberOfUnCommittedPages
+= (ULONG
)(DecommitSize
/ PAGE_SIZE
);
836 /* Adjust size of this free entry and insert it */
837 FreeEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
838 FreeEntry
->Size
= (USHORT
)PrecedingSize
;
839 Heap
->TotalFreeSize
+= PrecedingSize
;
841 /* Insert it into the free list */
842 RtlpInsertFreeBlockHelper(Heap
, FreeEntry
, PrecedingSize
, FALSE
);
844 else if (PrecedingInUseEntry
)
846 /* Adjust preceding in use entry */
847 PrecedingInUseEntry
->Flags
|= HEAP_ENTRY_LAST_ENTRY
;
850 /* Now the next one */
853 /* Adjust size of this free entry and insert it */
854 NextFreeEntry
->Flags
= 0;
855 NextFreeEntry
->PreviousSize
= 0;
856 NextFreeEntry
->SegmentOffset
= Segment
->Entry
.SegmentOffset
;
857 NextFreeEntry
->Size
= (USHORT
)NextSize
;
859 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)NextFreeEntry
+ NextSize
))->PreviousSize
= (USHORT
)NextSize
;
861 Heap
->TotalFreeSize
+= NextSize
;
862 RtlpInsertFreeBlockHelper(Heap
, NextFreeEntry
, NextSize
, FALSE
);
864 else if (NextInUseEntry
)
866 NextInUseEntry
->PreviousSize
= 0;
872 RtlpInitializeHeapSegment(IN OUT PHEAP Heap
,
873 OUT PHEAP_SEGMENT Segment
,
874 IN UCHAR SegmentIndex
,
875 IN ULONG SegmentFlags
,
876 IN SIZE_T SegmentReserve
,
877 IN SIZE_T SegmentCommit
)
879 PHEAP_ENTRY HeapEntry
;
882 ASSERT(Heap
!= NULL
);
883 ASSERT(Segment
!= NULL
);
884 ASSERT(SegmentCommit
>= PAGE_SIZE
);
885 ASSERT(ROUND_DOWN(SegmentCommit
, PAGE_SIZE
) == SegmentCommit
);
886 ASSERT(SegmentReserve
>= SegmentCommit
);
887 ASSERT(ROUND_DOWN(SegmentReserve
, PAGE_SIZE
) == SegmentReserve
);
889 DPRINT("RtlpInitializeHeapSegment(%p %p %x %x %lx %lx)\n", Heap
, Segment
, SegmentIndex
, SegmentFlags
, SegmentReserve
, SegmentCommit
);
891 /* Initialise the Heap Entry header if this is not the first Heap Segment */
892 if ((PHEAP_SEGMENT
) (Heap
) != Segment
)
894 Segment
->Entry
.Size
= ROUND_UP(sizeof(HEAP_SEGMENT
), sizeof(HEAP_ENTRY
)) >> HEAP_ENTRY_SHIFT
;
895 Segment
->Entry
.Flags
= HEAP_ENTRY_BUSY
;
896 Segment
->Entry
.SmallTagIndex
= LOBYTE(Segment
->Entry
.Size
) ^ HIBYTE(Segment
->Entry
.Size
) ^ Segment
->Entry
.Flags
;
897 Segment
->Entry
.PreviousSize
= 0;
898 Segment
->Entry
.SegmentOffset
= SegmentIndex
;
899 Segment
->Entry
.UnusedBytes
= 0;
903 ASSERT((Segment
->Entry
.Size
<< HEAP_ENTRY_SHIFT
) <= PAGE_SIZE
);
905 /* Initialise the Heap Segment header */
906 Segment
->SegmentSignature
= HEAP_SEGMENT_SIGNATURE
;
907 Segment
->SegmentFlags
= SegmentFlags
;
908 Segment
->Heap
= Heap
;
909 Heap
->Segments
[SegmentIndex
] = Segment
;
911 /* Initialise the Heap Segment location information */
912 Segment
->BaseAddress
= Segment
;
913 Segment
->NumberOfPages
= (ULONG
)(SegmentReserve
>> PAGE_SHIFT
);
915 /* Initialise the Heap Entries contained within the Heap Segment */
916 Segment
->FirstEntry
= &Segment
->Entry
+ Segment
->Entry
.Size
;
917 Segment
->LastValidEntry
= (PHEAP_ENTRY
)((ULONG_PTR
)Segment
+ SegmentReserve
);
919 if (((SIZE_T
)Segment
->Entry
.Size
<< HEAP_ENTRY_SHIFT
) < SegmentCommit
)
921 HeapEntry
= Segment
->FirstEntry
;
923 /* Prepare a Free Heap Entry header */
924 HeapEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
925 HeapEntry
->PreviousSize
= Segment
->Entry
.Size
;
926 HeapEntry
->SegmentOffset
= SegmentIndex
;
928 /* Register the Free Heap Entry */
929 RtlpInsertFreeBlock(Heap
, (PHEAP_FREE_ENTRY
) HeapEntry
, (SegmentCommit
>> HEAP_ENTRY_SHIFT
) - Segment
->Entry
.Size
);
932 /* Initialise the Heap Segment UnCommitted Range information */
933 Segment
->NumberOfUnCommittedPages
= (ULONG
)((SegmentReserve
- SegmentCommit
) >> PAGE_SHIFT
);
934 Segment
->NumberOfUnCommittedRanges
= 0;
935 InitializeListHead(&Segment
->UCRSegmentList
);
937 /* Register the UnCommitted Range of the Heap Segment */
938 if (Segment
->NumberOfUnCommittedPages
!= 0)
939 RtlpInsertUnCommittedPages(Segment
, (ULONG_PTR
) (Segment
) + SegmentCommit
, SegmentReserve
- SegmentCommit
);
941 return STATUS_SUCCESS
;
945 RtlpDestroyHeapSegment(PHEAP_SEGMENT Segment
)
951 /* Make sure it's not user allocated */
952 if (Segment
->SegmentFlags
& HEAP_USER_ALLOCATED
) return;
954 BaseAddress
= Segment
->BaseAddress
;
955 DPRINT("Destroying segment %p, BA %p\n", Segment
, BaseAddress
);
957 /* Release virtual memory */
958 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
963 if (!NT_SUCCESS(Status
))
965 DPRINT1("HEAP: Failed to release segment's memory with status 0x%08X\n", Status
);
971 RtlpAddHeapToProcessList(PHEAP Heap
)
976 Peb
= RtlGetCurrentPeb();
978 /* Acquire the lock */
979 RtlEnterCriticalSection(&RtlpProcessHeapsListLock
);
982 /* Check if max number of heaps reached */
983 if (Peb
->NumberOfHeaps
== Peb
->MaximumNumberOfHeaps
)
985 // TODO: Handle this case
989 /* Add the heap to the process heaps */
990 Peb
->ProcessHeaps
[Peb
->NumberOfHeaps
] = Heap
;
991 Peb
->NumberOfHeaps
++;
992 Heap
->ProcessHeapsListIndex
= (USHORT
)Peb
->NumberOfHeaps
;
995 /* Release the lock */
996 RtlLeaveCriticalSection(&RtlpProcessHeapsListLock
);
1001 /* Usermode only! */
1003 RtlpRemoveHeapFromProcessList(PHEAP Heap
)
1006 PHEAP
*Current
, *Next
;
1010 Peb
= RtlGetCurrentPeb();
1012 /* Acquire the lock */
1013 RtlEnterCriticalSection(&RtlpProcessHeapsListLock
);
1015 /* Check if we don't need anything to do */
1016 if ((Heap
->ProcessHeapsListIndex
== 0) ||
1017 (Heap
->ProcessHeapsListIndex
> Peb
->NumberOfHeaps
) ||
1018 (Peb
->NumberOfHeaps
== 0))
1020 /* Release the lock */
1021 RtlLeaveCriticalSection(&RtlpProcessHeapsListLock
);
1026 /* The process actually has more than one heap.
1027 Use classic, lernt from university times algorithm for removing an entry
1028 from a static array */
1030 Current
= (PHEAP
*)&Peb
->ProcessHeaps
[Heap
->ProcessHeapsListIndex
- 1];
1033 /* How many items we need to shift to the left */
1034 Count
= Peb
->NumberOfHeaps
- (Heap
->ProcessHeapsListIndex
- 1);
1036 /* Move them all in a loop */
1039 /* Copy it and advance next pointer */
1042 /* Update its index */
1043 (*Current
)->ProcessHeapsListIndex
-= 1;
1045 /* Advance pointers */
1050 /* Decrease total number of heaps */
1051 Peb
->NumberOfHeaps
--;
1053 /* Zero last unused item */
1054 Peb
->ProcessHeaps
[Peb
->NumberOfHeaps
] = NULL
;
1055 Heap
->ProcessHeapsListIndex
= 0;
1057 /* Release the lock */
1058 RtlLeaveCriticalSection(&RtlpProcessHeapsListLock
);
1061 PHEAP_FREE_ENTRY NTAPI
1062 RtlpCoalesceHeap(PHEAP Heap
)
1068 PHEAP_FREE_ENTRY NTAPI
1069 RtlpCoalesceFreeBlocks (PHEAP Heap
,
1070 PHEAP_FREE_ENTRY FreeEntry
,
1074 PHEAP_FREE_ENTRY CurrentEntry
, NextEntry
;
1076 /* Get the previous entry */
1077 CurrentEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
- FreeEntry
->PreviousSize
);
1080 if (CurrentEntry
!= FreeEntry
&&
1081 !(CurrentEntry
->Flags
& HEAP_ENTRY_BUSY
) &&
1082 (*FreeSize
+ CurrentEntry
->Size
) <= HEAP_MAX_BLOCK_SIZE
)
1084 ASSERT(FreeEntry
->PreviousSize
== CurrentEntry
->Size
);
1086 /* Remove it if asked for */
1089 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
1090 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
1092 /* Remove it only once! */
1096 /* Remove previous entry too */
1097 RtlpRemoveFreeBlock(Heap
, CurrentEntry
, FALSE
, FALSE
);
1100 CurrentEntry
->Flags
= FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
;
1102 /* Advance FreeEntry and update sizes */
1103 FreeEntry
= CurrentEntry
;
1104 *FreeSize
= *FreeSize
+ CurrentEntry
->Size
;
1105 Heap
->TotalFreeSize
-= CurrentEntry
->Size
;
1106 FreeEntry
->Size
= (USHORT
)(*FreeSize
);
1108 /* Also update previous size if needed */
1109 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1111 ((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
)->PreviousSize
= (USHORT
)(*FreeSize
);
1115 /* Check the next block if it exists */
1116 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1118 NextEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
);
1120 if (!(NextEntry
->Flags
& HEAP_ENTRY_BUSY
) &&
1121 NextEntry
->Size
+ *FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
1123 ASSERT(*FreeSize
== NextEntry
->PreviousSize
);
1125 /* Remove it if asked for */
1128 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
1129 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
1133 FreeEntry
->Flags
= NextEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
;
1135 /* Remove next entry now */
1136 RtlpRemoveFreeBlock(Heap
, NextEntry
, FALSE
, FALSE
);
1139 *FreeSize
= *FreeSize
+ NextEntry
->Size
;
1140 Heap
->TotalFreeSize
-= NextEntry
->Size
;
1141 FreeEntry
->Size
= (USHORT
)(*FreeSize
);
1143 /* Also update previous size if needed */
1144 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1146 ((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
)->PreviousSize
= (USHORT
)(*FreeSize
);
1153 PHEAP_FREE_ENTRY NTAPI
1154 RtlpExtendHeap(PHEAP Heap
,
1158 UCHAR Index
, EmptyIndex
;
1159 SIZE_T FreeSize
, CommitSize
, ReserveSize
;
1160 PHEAP_SEGMENT Segment
;
1161 PHEAP_FREE_ENTRY FreeEntry
;
1164 DPRINT("RtlpExtendHeap(%p %x)\n", Heap
, Size
);
1166 /* Calculate amount in pages */
1167 Pages
= (ULONG
)((Size
+ PAGE_SIZE
- 1) / PAGE_SIZE
);
1168 FreeSize
= Pages
* PAGE_SIZE
;
1169 DPRINT("Pages %x, FreeSize %x. Going through segments...\n", Pages
, FreeSize
);
1171 /* Find an empty segment */
1172 EmptyIndex
= HEAP_SEGMENTS
;
1173 for (Index
= 0; Index
< HEAP_SEGMENTS
; Index
++)
1175 Segment
= Heap
->Segments
[Index
];
1177 if (Segment
) DPRINT("Segment[%d] %p with NOUCP %x\n", Index
, Segment
, Segment
->NumberOfUnCommittedPages
);
1179 /* Check if its size suits us */
1181 Pages
<= Segment
->NumberOfUnCommittedPages
)
1183 DPRINT("This segment is suitable\n");
1185 /* Commit needed amount */
1186 FreeEntry
= RtlpFindAndCommitPages(Heap
, Segment
, &FreeSize
, NULL
);
1188 /* Coalesce it with adjacent entries */
1191 FreeSize
= FreeSize
>> HEAP_ENTRY_SHIFT
;
1192 FreeEntry
= RtlpCoalesceFreeBlocks(Heap
, FreeEntry
, &FreeSize
, FALSE
);
1193 RtlpInsertFreeBlock(Heap
, FreeEntry
, FreeSize
);
1197 else if (!Segment
&&
1198 EmptyIndex
== HEAP_SEGMENTS
)
1200 /* Remember the first unused segment index */
1205 /* No luck, need to grow the heap */
1206 if ((Heap
->Flags
& HEAP_GROWABLE
) &&
1207 (EmptyIndex
!= HEAP_SEGMENTS
))
1211 /* Reserve the memory */
1212 if ((Size
+ PAGE_SIZE
) <= Heap
->SegmentReserve
)
1213 ReserveSize
= Heap
->SegmentReserve
;
1215 ReserveSize
= Size
+ PAGE_SIZE
;
1217 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1224 /* If it failed, retry again with a half division algorithm */
1225 while (!NT_SUCCESS(Status
) &&
1226 ReserveSize
!= Size
+ PAGE_SIZE
)
1230 if (ReserveSize
< (Size
+ PAGE_SIZE
))
1231 ReserveSize
= Size
+ PAGE_SIZE
;
1233 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1241 /* Proceed only if it's success */
1242 if (NT_SUCCESS(Status
))
1244 Heap
->SegmentReserve
+= ReserveSize
;
1246 /* Now commit the memory */
1247 if ((Size
+ PAGE_SIZE
) <= Heap
->SegmentCommit
)
1248 CommitSize
= Heap
->SegmentCommit
;
1250 CommitSize
= Size
+ PAGE_SIZE
;
1252 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1259 DPRINT("Committed %d bytes at base %p\n", CommitSize
, Segment
);
1261 /* Initialize heap segment if commit was successful */
1262 if (NT_SUCCESS(Status
))
1263 Status
= RtlpInitializeHeapSegment(Heap
, Segment
, EmptyIndex
, 0, ReserveSize
, CommitSize
);
1265 /* If everything worked - cool */
1266 if (NT_SUCCESS(Status
)) return (PHEAP_FREE_ENTRY
)Segment
->FirstEntry
;
1268 DPRINT1("Committing failed with status 0x%08X\n", Status
);
1270 /* Nope, we failed. Free memory */
1271 ZwFreeVirtualMemory(NtCurrentProcess(),
1278 DPRINT1("Reserving failed with status 0x%08X\n", Status
);
1282 if (RtlpGetMode() == UserMode
)
1284 /* If coalescing on free is disabled in usermode, then do it here */
1285 if (Heap
->Flags
& HEAP_DISABLE_COALESCE_ON_FREE
)
1287 FreeEntry
= RtlpCoalesceHeap(Heap
);
1289 /* If it's a suitable one - return it */
1291 FreeEntry
->Size
>= Size
)
1301 /***********************************************************************
1304 * Handle of heap: Success
1310 RtlCreateHeap(ULONG Flags
,
1315 PRTL_HEAP_PARAMETERS Parameters
)
1317 PVOID CommittedAddress
= NULL
, UncommittedAddress
= NULL
;
1319 RTL_HEAP_PARAMETERS SafeParams
= {0};
1321 ULONG_PTR MaximumUserModeAddress
;
1322 SYSTEM_BASIC_INFORMATION SystemInformation
;
1323 MEMORY_BASIC_INFORMATION MemoryInfo
;
1324 ULONG NtGlobalFlags
= RtlGetNtGlobalFlags();
1325 ULONG HeapSegmentFlags
= 0;
1329 /* Check for a special heap */
1330 if (RtlpPageHeapEnabled
&& !Addr
&& !Lock
)
1332 Heap
= RtlpPageHeapCreate(Flags
, Addr
, TotalSize
, CommitSize
, Lock
, Parameters
);
1333 if (Heap
) return Heap
;
1335 /* Reset a special Parameters == -1 hack */
1336 if ((ULONG_PTR
)Parameters
== (ULONG_PTR
)-1)
1339 DPRINT1("Enabling page heap failed\n");
1342 /* Check validation flags */
1343 if (!(Flags
& HEAP_SKIP_VALIDATION_CHECKS
) && (Flags
& ~HEAP_CREATE_VALID_MASK
))
1345 DPRINT1("Invalid flags 0x%08x, fixing...\n", Flags
);
1346 Flags
&= HEAP_CREATE_VALID_MASK
;
1349 /* TODO: Capture parameters, once we decide to use SEH */
1350 if (!Parameters
) Parameters
= &SafeParams
;
1352 /* Check global flags */
1353 if (NtGlobalFlags
& FLG_HEAP_DISABLE_COALESCING
)
1354 Flags
|= HEAP_DISABLE_COALESCE_ON_FREE
;
1356 if (NtGlobalFlags
& FLG_HEAP_ENABLE_FREE_CHECK
)
1357 Flags
|= HEAP_FREE_CHECKING_ENABLED
;
1359 if (NtGlobalFlags
& FLG_HEAP_ENABLE_TAIL_CHECK
)
1360 Flags
|= HEAP_TAIL_CHECKING_ENABLED
;
1362 if (RtlpGetMode() == UserMode
)
1364 /* Also check these flags if in usermode */
1365 if (NtGlobalFlags
& FLG_HEAP_VALIDATE_ALL
)
1366 Flags
|= HEAP_VALIDATE_ALL_ENABLED
;
1368 if (NtGlobalFlags
& FLG_HEAP_VALIDATE_PARAMETERS
)
1369 Flags
|= HEAP_VALIDATE_PARAMETERS_ENABLED
;
1371 if (NtGlobalFlags
& FLG_USER_STACK_TRACE_DB
)
1372 Flags
|= HEAP_CAPTURE_STACK_BACKTRACES
;
1375 Peb
= RtlGetCurrentPeb();
1377 /* Apply defaults for non-set parameters */
1378 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= Peb
->HeapSegmentCommit
;
1379 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= Peb
->HeapSegmentReserve
;
1380 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= Peb
->HeapDeCommitFreeBlockThreshold
;
1381 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= Peb
->HeapDeCommitTotalFreeThreshold
;
1385 /* Apply defaults for non-set parameters */
1387 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= MmHeapSegmentCommit
;
1388 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= MmHeapSegmentReserve
;
1389 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= MmHeapDeCommitFreeBlockThreshold
;
1390 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= MmHeapDeCommitTotalFreeThreshold
;
1394 // FIXME: Move to memory manager
1395 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= PAGE_SIZE
* 2;
1396 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= 1048576;
1397 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= PAGE_SIZE
;
1398 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= 65536;
1400 /* Get the max um address */
1401 Status
= ZwQuerySystemInformation(SystemBasicInformation
,
1403 sizeof(SystemInformation
),
1406 if (!NT_SUCCESS(Status
))
1408 DPRINT1("Getting max usermode address failed with status 0x%08x\n", Status
);
1412 MaximumUserModeAddress
= SystemInformation
.MaximumUserModeAddress
;
1414 /* Calculate max alloc size */
1415 if (!Parameters
->MaximumAllocationSize
)
1416 Parameters
->MaximumAllocationSize
= MaximumUserModeAddress
- (ULONG_PTR
)0x10000 - PAGE_SIZE
;
1418 MaxBlockSize
= 0x80000 - PAGE_SIZE
;
1420 if (!Parameters
->VirtualMemoryThreshold
||
1421 Parameters
->VirtualMemoryThreshold
> MaxBlockSize
)
1423 Parameters
->VirtualMemoryThreshold
= MaxBlockSize
;
1426 /* Check reserve/commit sizes and set default values */
1429 CommitSize
= PAGE_SIZE
;
1431 TotalSize
= ROUND_UP(TotalSize
, PAGE_SIZE
);
1433 TotalSize
= 64 * PAGE_SIZE
;
1437 /* Round up the commit size to be at least the page size */
1438 CommitSize
= ROUND_UP(CommitSize
, PAGE_SIZE
);
1441 TotalSize
= ROUND_UP(TotalSize
, PAGE_SIZE
);
1443 TotalSize
= ROUND_UP(CommitSize
, 16 * PAGE_SIZE
);
1446 /* Call special heap */
1447 if (RtlpHeapIsSpecial(Flags
))
1448 return RtlDebugCreateHeap(Flags
, Addr
, TotalSize
, CommitSize
, Lock
, Parameters
);
1450 /* Without serialization, a lock makes no sense */
1451 if ((Flags
& HEAP_NO_SERIALIZE
) && (Lock
!= NULL
))
1454 /* See if we are already provided with an address for the heap */
1457 if (Parameters
->CommitRoutine
)
1459 /* There is a commit routine, so no problem here, check params */
1460 if ((Flags
& HEAP_GROWABLE
) ||
1461 !Parameters
->InitialCommit
||
1462 !Parameters
->InitialReserve
||
1463 (Parameters
->InitialCommit
> Parameters
->InitialReserve
))
1469 /* Calculate committed and uncommitted addresses */
1470 CommittedAddress
= Addr
;
1471 UncommittedAddress
= (PCHAR
)Addr
+ Parameters
->InitialCommit
;
1472 TotalSize
= Parameters
->InitialReserve
;
1474 /* Zero the initial page ourselves */
1475 RtlZeroMemory(CommittedAddress
, PAGE_SIZE
);
1479 /* Commit routine is absent, so query how much memory caller reserved */
1480 Status
= ZwQueryVirtualMemory(NtCurrentProcess(),
1482 MemoryBasicInformation
,
1487 if (!NT_SUCCESS(Status
))
1489 DPRINT1("Querying amount of user supplied memory failed with status 0x%08X\n", Status
);
1494 if (MemoryInfo
.BaseAddress
!= Addr
||
1495 MemoryInfo
.State
== MEM_FREE
)
1500 /* Validation checks passed, set committed/uncommitted addresses */
1501 CommittedAddress
= Addr
;
1503 /* Check if it's committed or not */
1504 if (MemoryInfo
.State
== MEM_COMMIT
)
1506 /* Zero it out because it's already committed */
1507 RtlZeroMemory(CommittedAddress
, PAGE_SIZE
);
1509 /* Calculate uncommitted address value */
1510 CommitSize
= MemoryInfo
.RegionSize
;
1511 TotalSize
= CommitSize
;
1512 UncommittedAddress
= (PCHAR
)Addr
+ CommitSize
;
1514 /* Check if uncommitted address is reserved */
1515 Status
= ZwQueryVirtualMemory(NtCurrentProcess(),
1517 MemoryBasicInformation
,
1522 if (NT_SUCCESS(Status
) &&
1523 MemoryInfo
.State
== MEM_RESERVE
)
1525 /* It is, so add it up to the reserve size */
1526 TotalSize
+= MemoryInfo
.RegionSize
;
1531 /* It's not committed, inform following code that a commit is necessary */
1532 CommitSize
= PAGE_SIZE
;
1533 UncommittedAddress
= Addr
;
1537 /* Mark this as a user-committed mem */
1538 HeapSegmentFlags
= HEAP_USER_ALLOCATED
;
1543 /* Check commit routine */
1544 if (Parameters
->CommitRoutine
) return NULL
;
1546 /* Reserve memory */
1547 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1554 if (!NT_SUCCESS(Status
))
1556 DPRINT1("Failed to reserve memory with status 0x%08x\n", Status
);
1560 /* Set base addresses */
1561 CommittedAddress
= Heap
;
1562 UncommittedAddress
= Heap
;
1565 /* Check if we need to commit something */
1566 if (CommittedAddress
== UncommittedAddress
)
1568 /* Commit the required size */
1569 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1576 DPRINT("Committed %d bytes at base %p\n", CommitSize
, CommittedAddress
);
1578 if (!NT_SUCCESS(Status
))
1580 DPRINT1("Failure, Status 0x%08X\n", Status
);
1582 /* Release memory if it was reserved */
1583 if (!Addr
) ZwFreeVirtualMemory(NtCurrentProcess(),
1591 /* Calculate new uncommitted address */
1592 UncommittedAddress
= (PCHAR
)UncommittedAddress
+ CommitSize
;
1595 /* Initialize the heap */
1596 Status
= RtlpInitializeHeap(Heap
, Flags
, Lock
, Parameters
);
1597 if (!NT_SUCCESS(Status
))
1599 DPRINT1("Failed to initialize heap (%x)\n", Status
);
1603 /* Initialize heap's first segment */
1604 Status
= RtlpInitializeHeapSegment(Heap
, (PHEAP_SEGMENT
) (Heap
), 0, HeapSegmentFlags
, TotalSize
, CommitSize
);
1605 if (!NT_SUCCESS(Status
))
1607 DPRINT1("Failed to initialize heap segment (%x)\n", Status
);
1611 DPRINT("Created heap %p, CommitSize %x, ReserveSize %x\n", Heap
, CommitSize
, TotalSize
);
1613 /* Add heap to process list in case of usermode heap */
1614 if (RtlpGetMode() == UserMode
)
1616 RtlpAddHeapToProcessList(Heap
);
1618 // FIXME: What about lookasides?
1624 /***********************************************************************
1633 * Success: A NULL HANDLE, if heap is NULL or it was destroyed
1634 * Failure: The Heap handle, if heap is the process heap.
1637 RtlDestroyHeap(HANDLE HeapPtr
) /* [in] Handle of heap */
1639 PHEAP Heap
= (PHEAP
)HeapPtr
;
1640 PLIST_ENTRY Current
;
1641 PHEAP_UCR_SEGMENT UcrSegment
;
1642 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
1646 PHEAP_SEGMENT Segment
;
1648 if (!HeapPtr
) return NULL
;
1650 /* Call page heap routine if required */
1651 if (Heap
->ForceFlags
& HEAP_FLAG_PAGE_ALLOCS
) return RtlpPageHeapDestroy(HeapPtr
);
1653 /* Call special heap */
1654 if (RtlpHeapIsSpecial(Heap
->Flags
))
1656 if (!RtlDebugDestroyHeap(Heap
)) return HeapPtr
;
1659 /* Check for a process heap */
1660 if (RtlpGetMode() == UserMode
&&
1661 HeapPtr
== NtCurrentPeb()->ProcessHeap
) return HeapPtr
;
1663 /* Free up all big allocations */
1664 Current
= Heap
->VirtualAllocdBlocks
.Flink
;
1665 while (Current
!= &Heap
->VirtualAllocdBlocks
)
1667 VirtualEntry
= CONTAINING_RECORD(Current
, HEAP_VIRTUAL_ALLOC_ENTRY
, Entry
);
1668 BaseAddress
= (PVOID
)VirtualEntry
;
1669 Current
= Current
->Flink
;
1671 ZwFreeVirtualMemory(NtCurrentProcess(),
1677 /* Delete tags and remove heap from the process heaps list in user mode */
1678 if (RtlpGetMode() == UserMode
)
1680 // FIXME DestroyTags
1681 RtlpRemoveHeapFromProcessList(Heap
);
1684 /* Delete the heap lock */
1685 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
1687 /* Delete it if it wasn't user allocated */
1688 if (!(Heap
->Flags
& HEAP_LOCK_USER_ALLOCATED
))
1689 RtlDeleteHeapLock(Heap
->LockVariable
);
1691 /* Clear out the lock variable */
1692 Heap
->LockVariable
= NULL
;
1695 /* Free UCR segments if any were created */
1696 Current
= Heap
->UCRSegments
.Flink
;
1697 while(Current
!= &Heap
->UCRSegments
)
1699 UcrSegment
= CONTAINING_RECORD(Current
, HEAP_UCR_SEGMENT
, ListEntry
);
1701 /* Advance to the next descriptor */
1702 Current
= Current
->Flink
;
1704 BaseAddress
= (PVOID
)UcrSegment
;
1707 /* Release that memory */
1708 ZwFreeVirtualMemory(NtCurrentProcess(),
1714 /* Go through segments and destroy them */
1715 for (i
= HEAP_SEGMENTS
- 1; i
>= 0; i
--)
1717 Segment
= Heap
->Segments
[i
];
1718 if (Segment
) RtlpDestroyHeapSegment(Segment
);
1725 RtlpSplitEntry(PHEAP Heap
,
1727 PHEAP_FREE_ENTRY FreeBlock
,
1728 SIZE_T AllocationSize
,
1732 PHEAP_FREE_ENTRY SplitBlock
, SplitBlock2
;
1733 UCHAR FreeFlags
, EntryFlags
= HEAP_ENTRY_BUSY
;
1734 PHEAP_ENTRY InUseEntry
;
1737 /* Add extra flags in case of settable user value feature is requested,
1738 or there is a tag (small or normal) or there is a request to
1739 capture stack backtraces */
1740 if ((Flags
& HEAP_EXTRA_FLAGS_MASK
) ||
1741 Heap
->PseudoTagEntries
)
1743 /* Add flag which means that the entry will have extra stuff attached */
1744 EntryFlags
|= HEAP_ENTRY_EXTRA_PRESENT
;
1746 /* NB! AllocationSize is already adjusted by RtlAllocateHeap */
1749 /* Add settable user flags, if any */
1750 EntryFlags
|= (Flags
& HEAP_SETTABLE_USER_FLAGS
) >> 4;
1752 /* Save flags, update total free size */
1753 FreeFlags
= FreeBlock
->Flags
;
1754 Heap
->TotalFreeSize
-= FreeBlock
->Size
;
1756 /* Make this block an in-use one */
1757 InUseEntry
= (PHEAP_ENTRY
)FreeBlock
;
1758 InUseEntry
->Flags
= EntryFlags
;
1759 InUseEntry
->SmallTagIndex
= 0;
1761 /* Calculate the extra amount */
1762 FreeSize
= InUseEntry
->Size
- Index
;
1764 /* Update it's size fields (we don't need their data anymore) */
1765 InUseEntry
->Size
= (USHORT
)Index
;
1766 InUseEntry
->UnusedBytes
= (UCHAR
)(AllocationSize
- Size
);
1768 /* If there is something to split - do the split */
1771 /* Don't split if resulting entry can't contain any payload data
1772 (i.e. being just HEAP_ENTRY_SIZE) */
1775 /* Increase sizes of the in-use entry */
1777 InUseEntry
->UnusedBytes
+= sizeof(HEAP_ENTRY
);
1781 /* Calculate a pointer to the new entry */
1782 SplitBlock
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
1785 SplitBlock
->Flags
= FreeFlags
;
1786 SplitBlock
->SegmentOffset
= InUseEntry
->SegmentOffset
;
1787 SplitBlock
->Size
= (USHORT
)FreeSize
;
1788 SplitBlock
->PreviousSize
= (USHORT
)Index
;
1790 /* Check if it's the last entry */
1791 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
1793 /* Insert it to the free list if it's the last entry */
1794 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
1795 Heap
->TotalFreeSize
+= FreeSize
;
1799 /* Not so easy - need to update next's previous size too */
1800 SplitBlock2
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
);
1802 if (SplitBlock2
->Flags
& HEAP_ENTRY_BUSY
)
1804 SplitBlock2
->PreviousSize
= (USHORT
)FreeSize
;
1805 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
1806 Heap
->TotalFreeSize
+= FreeSize
;
1810 /* Even more complex - the next entry is free, so we can merge them into one! */
1811 SplitBlock
->Flags
= SplitBlock2
->Flags
;
1813 /* Remove that next entry */
1814 RtlpRemoveFreeBlock(Heap
, SplitBlock2
, FALSE
, FALSE
);
1817 FreeSize
+= SplitBlock2
->Size
;
1818 Heap
->TotalFreeSize
-= SplitBlock2
->Size
;
1820 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
1822 /* Insert it back */
1823 SplitBlock
->Size
= (USHORT
)FreeSize
;
1825 /* Don't forget to update previous size of the next entry! */
1826 if (!(SplitBlock
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1828 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= (USHORT
)FreeSize
;
1831 /* Actually insert it */
1832 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, (USHORT
)FreeSize
, FALSE
);
1834 /* Update total size */
1835 Heap
->TotalFreeSize
+= FreeSize
;
1839 /* Resulting block is quite big */
1840 RtlpInsertFreeBlock(Heap
, SplitBlock
, FreeSize
);
1845 /* Reset flags of the free entry */
1850 /* Set last entry flag */
1851 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
1852 InUseEntry
->Flags
|= HEAP_ENTRY_LAST_ENTRY
;
1858 RtlpAllocateNonDedicated(PHEAP Heap
,
1861 SIZE_T AllocationSize
,
1865 PLIST_ENTRY FreeListHead
, Next
;
1866 PHEAP_FREE_ENTRY FreeBlock
;
1867 PHEAP_ENTRY InUseEntry
;
1868 PHEAP_ENTRY_EXTRA Extra
;
1869 EXCEPTION_RECORD ExceptionRecord
;
1871 /* Go through the zero list to find a place where to insert the new entry */
1872 FreeListHead
= &Heap
->FreeLists
[0];
1874 /* Start from the largest block to reduce time */
1875 Next
= FreeListHead
->Blink
;
1876 if (FreeListHead
!= Next
)
1878 FreeBlock
= CONTAINING_RECORD(Next
, HEAP_FREE_ENTRY
, FreeList
);
1880 if (FreeBlock
->Size
>= Index
)
1882 /* Our request is smaller than the largest entry in the zero list */
1884 /* Go through the list to find insertion place */
1885 Next
= FreeListHead
->Flink
;
1886 while (FreeListHead
!= Next
)
1888 FreeBlock
= CONTAINING_RECORD(Next
, HEAP_FREE_ENTRY
, FreeList
);
1890 if (FreeBlock
->Size
>= Index
)
1892 /* Found minimally fitting entry. Proceed to either using it as it is
1893 or splitting it to two entries */
1894 RemoveEntryList(&FreeBlock
->FreeList
);
1897 InUseEntry
= RtlpSplitEntry(Heap
, Flags
, FreeBlock
, AllocationSize
, Index
, Size
);
1899 /* Release the lock */
1900 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1902 /* Zero memory if that was requested */
1903 if (Flags
& HEAP_ZERO_MEMORY
)
1904 RtlZeroMemory(InUseEntry
+ 1, Size
);
1905 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
1907 /* Fill this block with a special pattern */
1908 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
1911 /* Fill tail of the block with a special pattern too if requested */
1912 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
1914 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
1915 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
1918 /* Prepare extra if it's present */
1919 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
1921 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
1922 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
1927 /* Return pointer to the */
1928 return InUseEntry
+ 1;
1931 /* Advance to the next entry */
1937 /* Extend the heap, 0 list didn't have anything suitable */
1938 FreeBlock
= RtlpExtendHeap(Heap
, AllocationSize
);
1940 /* Use the new biggest entry we've got */
1943 RemoveEntryList(&FreeBlock
->FreeList
);
1946 InUseEntry
= RtlpSplitEntry(Heap
, Flags
, FreeBlock
, AllocationSize
, Index
, Size
);
1948 /* Release the lock */
1949 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1951 /* Zero memory if that was requested */
1952 if (Flags
& HEAP_ZERO_MEMORY
)
1953 RtlZeroMemory(InUseEntry
+ 1, Size
);
1954 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
1956 /* Fill this block with a special pattern */
1957 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
1960 /* Fill tail of the block with a special pattern too if requested */
1961 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
1963 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
1964 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
1967 /* Prepare extra if it's present */
1968 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
1970 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
1971 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
1976 /* Return pointer to the */
1977 return InUseEntry
+ 1;
1980 /* Really unfortunate, out of memory condition */
1981 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
1983 /* Generate an exception */
1984 if (Flags
& HEAP_GENERATE_EXCEPTIONS
)
1986 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
1987 ExceptionRecord
.ExceptionRecord
= NULL
;
1988 ExceptionRecord
.NumberParameters
= 1;
1989 ExceptionRecord
.ExceptionFlags
= 0;
1990 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
1992 RtlRaiseException(&ExceptionRecord
);
1995 /* Release the lock */
1996 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1997 DPRINT1("HEAP: Allocation failed!\n");
1998 DPRINT1("Flags %x\n", Heap
->Flags
);
2002 /***********************************************************************
2003 * HeapAlloc (KERNEL32.334)
2005 * Pointer to allocated memory block
2007 * 0x7d030f60--invalid flags in RtlHeapAllocate
2011 RtlAllocateHeap(IN PVOID HeapPtr
,
2015 PHEAP Heap
= (PHEAP
)HeapPtr
;
2016 PULONG FreeListsInUse
;
2017 ULONG FreeListsInUseUlong
;
2018 SIZE_T AllocationSize
;
2019 SIZE_T Index
, InUseIndex
, i
;
2020 PLIST_ENTRY FreeListHead
;
2021 PHEAP_ENTRY InUseEntry
;
2022 PHEAP_FREE_ENTRY FreeBlock
;
2023 UCHAR FreeFlags
, EntryFlags
= HEAP_ENTRY_BUSY
;
2024 EXCEPTION_RECORD ExceptionRecord
;
2025 BOOLEAN HeapLocked
= FALSE
;
2026 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualBlock
= NULL
;
2027 PHEAP_ENTRY_EXTRA Extra
;
2031 Flags
|= Heap
->ForceFlags
;
2033 /* Call special heap */
2034 if (RtlpHeapIsSpecial(Flags
))
2035 return RtlDebugAllocateHeap(Heap
, Flags
, Size
);
2037 /* Check for the maximum size */
2038 if (Size
>= 0x80000000)
2040 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
2041 DPRINT1("HEAP: Allocation failed!\n");
2045 if (Flags
& (HEAP_CREATE_ENABLE_TRACING
|
2046 HEAP_CREATE_ALIGN_16
))
2048 DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags
);
2051 //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size);
2053 /* Calculate allocation size and index */
2055 AllocationSize
= Size
;
2058 AllocationSize
= (AllocationSize
+ Heap
->AlignRound
) & Heap
->AlignMask
;
2060 /* Add extra flags in case of settable user value feature is requested,
2061 or there is a tag (small or normal) or there is a request to
2062 capture stack backtraces */
2063 if ((Flags
& HEAP_EXTRA_FLAGS_MASK
) ||
2064 Heap
->PseudoTagEntries
)
2066 /* Add flag which means that the entry will have extra stuff attached */
2067 EntryFlags
|= HEAP_ENTRY_EXTRA_PRESENT
;
2069 /* Account for extra stuff size */
2070 AllocationSize
+= sizeof(HEAP_ENTRY_EXTRA
);
2073 /* Add settable user flags, if any */
2074 EntryFlags
|= (Flags
& HEAP_SETTABLE_USER_FLAGS
) >> 4;
2076 Index
= AllocationSize
>> HEAP_ENTRY_SHIFT
;
2078 /* Acquire the lock if necessary */
2079 if (!(Flags
& HEAP_NO_SERIALIZE
))
2081 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
2085 /* Depending on the size, the allocation is going to be done from dedicated,
2086 non-dedicated lists or a virtual block of memory */
2087 if (Index
< HEAP_FREELISTS
)
2089 FreeListHead
= &Heap
->FreeLists
[Index
];
2091 if (!IsListEmpty(FreeListHead
))
2093 /* There is a free entry in this list */
2094 FreeBlock
= CONTAINING_RECORD(FreeListHead
->Blink
,
2098 /* Save flags and remove the free entry */
2099 FreeFlags
= FreeBlock
->Flags
;
2100 RtlpRemoveFreeBlock(Heap
, FreeBlock
, TRUE
, FALSE
);
2102 /* Update the total free size of the heap */
2103 Heap
->TotalFreeSize
-= Index
;
2105 /* Initialize this block */
2106 InUseEntry
= (PHEAP_ENTRY
)FreeBlock
;
2107 InUseEntry
->Flags
= EntryFlags
| (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
);
2108 InUseEntry
->UnusedBytes
= (UCHAR
)(AllocationSize
- Size
);
2109 InUseEntry
->SmallTagIndex
= 0;
2113 /* Find smallest free block which this request could fit in */
2114 InUseIndex
= Index
>> 5;
2115 FreeListsInUse
= &Heap
->u
.FreeListsInUseUlong
[InUseIndex
];
2117 /* This bit magic disables all sizes which are less than the requested allocation size */
2118 FreeListsInUseUlong
= *FreeListsInUse
++ & ~((1 << ((ULONG
)Index
& 0x1f)) - 1);
2120 /* If size is definitily more than our lists - go directly to the non-dedicated one */
2122 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2124 /* Go through the list */
2125 for (i
= InUseIndex
; i
< 4; i
++)
2127 if (FreeListsInUseUlong
)
2129 FreeListHead
= &Heap
->FreeLists
[i
* 32];
2133 if (i
< 3) FreeListsInUseUlong
= *FreeListsInUse
++;
2136 /* Nothing found, search in the non-dedicated list */
2138 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2140 /* That list is found, now calculate exact block */
2141 FreeListHead
+= RtlpFindLeastSetBit(FreeListsInUseUlong
);
2143 /* Take this entry and remove it from the list of free blocks */
2144 FreeBlock
= CONTAINING_RECORD(FreeListHead
->Blink
,
2147 RtlpRemoveFreeBlock(Heap
, FreeBlock
, TRUE
, FALSE
);
2150 InUseEntry
= RtlpSplitEntry(Heap
, Flags
, FreeBlock
, AllocationSize
, Index
, Size
);
2153 /* Release the lock */
2154 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2156 /* Zero memory if that was requested */
2157 if (Flags
& HEAP_ZERO_MEMORY
)
2158 RtlZeroMemory(InUseEntry
+ 1, Size
);
2159 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2161 /* Fill this block with a special pattern */
2162 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
2165 /* Fill tail of the block with a special pattern too if requested */
2166 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2168 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
2169 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
2172 /* Prepare extra if it's present */
2173 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2175 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
2176 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
2181 /* User data starts right after the entry's header */
2182 return InUseEntry
+ 1;
2184 else if (Index
<= Heap
->VirtualMemoryThreshold
)
2186 /* The block is too large for dedicated lists, but fine for a non-dedicated one */
2187 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2189 else if (Heap
->Flags
& HEAP_GROWABLE
)
2191 /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */
2192 AllocationSize
+= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY
) - sizeof(HEAP_ENTRY
);
2194 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
2195 (PVOID
*)&VirtualBlock
,
2201 if (!NT_SUCCESS(Status
))
2204 /* Release the lock */
2205 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2206 DPRINT1("HEAP: Allocation failed!\n");
2210 /* Initialize the newly allocated block */
2211 VirtualBlock
->BusyBlock
.Size
= (USHORT
)(AllocationSize
- Size
);
2212 VirtualBlock
->BusyBlock
.Flags
= EntryFlags
| HEAP_ENTRY_VIRTUAL_ALLOC
| HEAP_ENTRY_EXTRA_PRESENT
;
2213 VirtualBlock
->CommitSize
= AllocationSize
;
2214 VirtualBlock
->ReserveSize
= AllocationSize
;
2216 /* Insert it into the list of virtual allocations */
2217 InsertTailList(&Heap
->VirtualAllocdBlocks
, &VirtualBlock
->Entry
);
2219 /* Release the lock */
2220 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2222 /* Return pointer to user data */
2223 return VirtualBlock
+ 1;
2226 /* Generate an exception */
2227 if (Flags
& HEAP_GENERATE_EXCEPTIONS
)
2229 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
2230 ExceptionRecord
.ExceptionRecord
= NULL
;
2231 ExceptionRecord
.NumberParameters
= 1;
2232 ExceptionRecord
.ExceptionFlags
= 0;
2233 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
2235 RtlRaiseException(&ExceptionRecord
);
2238 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL
);
2240 /* Release the lock */
2241 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2242 DPRINT1("HEAP: Allocation failed!\n");
2247 /***********************************************************************
2248 * HeapFree (KERNEL32.338)
2255 BOOLEAN NTAPI
RtlFreeHeap(
2256 HANDLE HeapPtr
, /* [in] Handle of heap */
2257 ULONG Flags
, /* [in] Heap freeing flags */
2258 PVOID Ptr
/* [in] Address of memory to free */
2262 PHEAP_ENTRY HeapEntry
;
2263 USHORT TagIndex
= 0;
2265 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
2266 BOOLEAN Locked
= FALSE
;
2269 /* Freeing NULL pointer is a legal operation */
2270 if (!Ptr
) return TRUE
;
2272 /* Get pointer to the heap and force flags */
2273 Heap
= (PHEAP
)HeapPtr
;
2274 Flags
|= Heap
->ForceFlags
;
2276 /* Call special heap */
2277 if (RtlpHeapIsSpecial(Flags
))
2278 return RtlDebugFreeHeap(Heap
, Flags
, Ptr
);
2280 /* Lock if necessary */
2281 if (!(Flags
& HEAP_NO_SERIALIZE
))
2283 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
2287 /* Get pointer to the heap entry */
2288 HeapEntry
= (PHEAP_ENTRY
)Ptr
- 1;
2290 /* Check this entry, fail if it's invalid */
2291 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
) ||
2292 (((ULONG_PTR
)Ptr
& 0x7) != 0) ||
2293 (HeapEntry
->SegmentOffset
>= HEAP_SEGMENTS
))
2295 /* This is an invalid block */
2296 DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr
);
2297 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
2299 /* Release the heap lock */
2300 if (Locked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2304 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2306 /* Big allocation */
2307 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2309 /* Remove it from the list */
2310 RemoveEntryList(&VirtualEntry
->Entry
);
2315 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
2316 (PVOID
*)&VirtualEntry
,
2320 if (!NT_SUCCESS(Status
))
2322 DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n",
2323 Status
, Heap
, Ptr
, VirtualEntry
);
2324 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status
);
2329 /* Normal allocation */
2330 BlockSize
= HeapEntry
->Size
;
2334 /* Coalesce in kernel mode, and in usermode if it's not disabled */
2335 if (RtlpGetMode() == KernelMode
||
2336 (RtlpGetMode() == UserMode
&& !(Heap
->Flags
& HEAP_DISABLE_COALESCE_ON_FREE
)))
2338 HeapEntry
= (PHEAP_ENTRY
)RtlpCoalesceFreeBlocks(Heap
,
2339 (PHEAP_FREE_ENTRY
)HeapEntry
,
2344 /* If there is no need to decommit the block - put it into a free list */
2345 if (BlockSize
< Heap
->DeCommitFreeBlockThreshold
||
2346 (Heap
->TotalFreeSize
+ BlockSize
< Heap
->DeCommitTotalFreeThreshold
))
2348 /* Check if it needs to go to a 0 list */
2349 if (BlockSize
> HEAP_MAX_BLOCK_SIZE
)
2351 /* General-purpose 0 list */
2352 RtlpInsertFreeBlock(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
);
2356 /* Usual free list */
2357 RtlpInsertFreeBlockHelper(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
, FALSE
);
2359 /* Assert sizes are consistent */
2360 if (!(HeapEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
2362 ASSERT((HeapEntry
+ BlockSize
)->PreviousSize
== BlockSize
);
2365 /* Increase the free size */
2366 Heap
->TotalFreeSize
+= BlockSize
;
2370 if (RtlpGetMode() == UserMode
&&
2379 /* Decommit this block */
2380 RtlpDeCommitFreeBlock(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
);
2384 /* Release the heap lock */
2385 if (Locked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2391 RtlpGrowBlockInPlace (IN PHEAP Heap
,
2393 IN PHEAP_ENTRY InUseEntry
,
2397 UCHAR EntryFlags
, RememberFlags
;
2398 PHEAP_FREE_ENTRY FreeEntry
, UnusedEntry
, FollowingEntry
;
2399 SIZE_T FreeSize
, PrevSize
, TailPart
, AddedSize
= 0;
2400 PHEAP_ENTRY_EXTRA OldExtra
, NewExtra
;
2402 /* We can't grow beyond specified threshold */
2403 if (Index
> Heap
->VirtualMemoryThreshold
)
2406 /* Get entry flags */
2407 EntryFlags
= InUseEntry
->Flags
;
2409 /* Get the next free entry */
2410 FreeEntry
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ InUseEntry
->Size
);
2412 if (EntryFlags
& HEAP_ENTRY_LAST_ENTRY
)
2414 /* There is no next block, just uncommitted space. Calculate how much is needed */
2415 FreeSize
= (Index
- InUseEntry
->Size
) << HEAP_ENTRY_SHIFT
;
2416 FreeSize
= ROUND_UP(FreeSize
, PAGE_SIZE
);
2418 /* Find and commit those pages */
2419 FreeEntry
= RtlpFindAndCommitPages(Heap
,
2420 Heap
->Segments
[InUseEntry
->SegmentOffset
],
2424 /* Fail if it failed... */
2425 if (!FreeEntry
) return FALSE
;
2427 /* It was successful, perform coalescing */
2428 FreeSize
= FreeSize
>> HEAP_ENTRY_SHIFT
;
2429 FreeEntry
= RtlpCoalesceFreeBlocks(Heap
, FreeEntry
, &FreeSize
, FALSE
);
2431 /* Check if it's enough */
2432 if (FreeSize
+ InUseEntry
->Size
< Index
)
2434 /* Still not enough */
2435 RtlpInsertFreeBlock(Heap
, FreeEntry
, FreeSize
);
2436 Heap
->TotalFreeSize
+= FreeSize
;
2440 /* Remember flags of this free entry */
2441 RememberFlags
= FreeEntry
->Flags
;
2444 FreeSize
+= InUseEntry
->Size
;
2448 /* The next block indeed exists. Check if it's free or in use */
2449 if (FreeEntry
->Flags
& HEAP_ENTRY_BUSY
) return FALSE
;
2451 /* Next entry is free, check if it can fit the block we need */
2452 FreeSize
= InUseEntry
->Size
+ FreeEntry
->Size
;
2453 if (FreeSize
< Index
) return FALSE
;
2455 /* Remember flags of this free entry */
2456 RememberFlags
= FreeEntry
->Flags
;
2458 /* Remove this block from the free list */
2459 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
2460 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
2463 PrevSize
= (InUseEntry
->Size
<< HEAP_ENTRY_SHIFT
) - InUseEntry
->UnusedBytes
;
2466 /* Don't produce too small blocks */
2473 /* Process extra stuff */
2474 if (RememberFlags
& HEAP_ENTRY_EXTRA_PRESENT
)
2476 /* Calculate pointers */
2477 OldExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ InUseEntry
->Size
- 1);
2478 NewExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ Index
- 1);
2481 *NewExtra
= *OldExtra
;
2487 InUseEntry
->Size
= (USHORT
)Index
;
2488 InUseEntry
->UnusedBytes
= (UCHAR
)((Index
<< HEAP_ENTRY_SHIFT
) - Size
);
2490 /* Check if there is a free space remaining after merging those blocks */
2493 /* Update flags and sizes */
2494 InUseEntry
->Flags
|= RememberFlags
& HEAP_ENTRY_LAST_ENTRY
;
2496 /* Either update previous size of the next entry or mark it as a last
2497 entry in the segment*/
2498 if (!(RememberFlags
& HEAP_ENTRY_LAST_ENTRY
))
2499 (InUseEntry
+ InUseEntry
->Size
)->PreviousSize
= InUseEntry
->Size
;
2503 /* Complex case, we need to split the block to give unused free space
2505 UnusedEntry
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
2506 UnusedEntry
->PreviousSize
= (USHORT
)Index
;
2507 UnusedEntry
->SegmentOffset
= InUseEntry
->SegmentOffset
;
2509 /* Update the following block or set the last entry in the segment */
2510 if (RememberFlags
& HEAP_ENTRY_LAST_ENTRY
)
2512 /* Set flags and size */
2513 UnusedEntry
->Flags
= RememberFlags
;
2514 UnusedEntry
->Size
= (USHORT
)FreeSize
;
2516 /* Insert it to the heap and update total size */
2517 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2518 Heap
->TotalFreeSize
+= FreeSize
;
2522 /* There is a block after this one */
2523 FollowingEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)UnusedEntry
+ FreeSize
);
2525 if (FollowingEntry
->Flags
& HEAP_ENTRY_BUSY
)
2527 /* Update flags and set size of the unused space entry */
2528 UnusedEntry
->Flags
= RememberFlags
& (~HEAP_ENTRY_LAST_ENTRY
);
2529 UnusedEntry
->Size
= (USHORT
)FreeSize
;
2531 /* Update previous size of the following entry */
2532 FollowingEntry
->PreviousSize
= (USHORT
)FreeSize
;
2534 /* Insert it to the heap and update total free size */
2535 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2536 Heap
->TotalFreeSize
+= FreeSize
;
2540 /* That following entry is also free, what a fortune! */
2541 RememberFlags
= FollowingEntry
->Flags
;
2544 RtlpRemoveFreeBlock(Heap
, FollowingEntry
, FALSE
, FALSE
);
2545 Heap
->TotalFreeSize
-= FollowingEntry
->Size
;
2547 /* And make up a new combined block */
2548 FreeSize
+= FollowingEntry
->Size
;
2549 UnusedEntry
->Flags
= RememberFlags
;
2551 /* Check where to put it */
2552 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
2554 /* Fine for a dedicated list */
2555 UnusedEntry
->Size
= (USHORT
)FreeSize
;
2557 if (!(RememberFlags
& HEAP_ENTRY_LAST_ENTRY
))
2558 ((PHEAP_ENTRY
)UnusedEntry
+ FreeSize
)->PreviousSize
= (USHORT
)FreeSize
;
2560 /* Insert it back and update total size */
2561 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2562 Heap
->TotalFreeSize
+= FreeSize
;
2566 /* The block is very large, leave all the hassle to the insertion routine */
2567 RtlpInsertFreeBlock(Heap
, UnusedEntry
, FreeSize
);
2573 /* Properly "zero out" (and fill!) the space */
2574 if (Flags
& HEAP_ZERO_MEMORY
)
2576 RtlZeroMemory((PCHAR
)(InUseEntry
+ 1) + PrevSize
, Size
- PrevSize
);
2578 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2580 /* Calculate tail part which we need to fill */
2581 TailPart
= PrevSize
& (sizeof(ULONG
) - 1);
2583 /* "Invert" it as usual */
2584 if (TailPart
) TailPart
= 4 - TailPart
;
2586 if (Size
> (PrevSize
+ TailPart
))
2587 AddedSize
= (Size
- (PrevSize
+ TailPart
)) & ~(sizeof(ULONG
) - 1);
2591 RtlFillMemoryUlong((PCHAR
)(InUseEntry
+ 1) + PrevSize
+ TailPart
,
2593 ARENA_INUSE_FILLER
);
2597 /* Fill the new tail */
2598 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2600 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
,
2605 /* Copy user settable flags */
2606 InUseEntry
->Flags
&= ~HEAP_ENTRY_SETTABLE_FLAGS
;
2607 InUseEntry
->Flags
|= ((Flags
& HEAP_SETTABLE_USER_FLAGS
) >> 4);
2609 /* Return success */
2613 PHEAP_ENTRY_EXTRA NTAPI
2614 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry
)
2616 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
2618 /* Check if it's a big block */
2619 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2621 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2623 /* Return a pointer to the extra stuff*/
2624 return &VirtualEntry
->ExtraStuff
;
2628 /* This is a usual entry, which means extra stuff follows this block */
2629 return (PHEAP_ENTRY_EXTRA
)(HeapEntry
+ HeapEntry
->Size
- 1);
2634 /***********************************************************************
2637 * Heap [in] Handle of heap block
2638 * Flags [in] Heap reallocation flags
2639 * Ptr, [in] Address of memory to reallocate
2640 * Size [in] Number of bytes to reallocate
2643 * Pointer to reallocated memory block
2645 * 0x7d030f60--invalid flags in RtlHeapAllocate
2649 RtlReAllocateHeap(HANDLE HeapPtr
,
2654 PHEAP Heap
= (PHEAP
)HeapPtr
;
2655 PHEAP_ENTRY InUseEntry
, NewInUseEntry
;
2656 PHEAP_ENTRY_EXTRA OldExtra
, NewExtra
;
2657 SIZE_T AllocationSize
, FreeSize
, DecommitSize
;
2658 BOOLEAN HeapLocked
= FALSE
;
2659 PVOID NewBaseAddress
;
2660 PHEAP_FREE_ENTRY SplitBlock
, SplitBlock2
;
2661 SIZE_T OldSize
, Index
, OldIndex
;
2665 SIZE_T RemainderBytes
, ExtraSize
;
2666 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock
;
2667 EXCEPTION_RECORD ExceptionRecord
;
2669 /* Return success in case of a null pointer */
2672 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS
);
2676 /* Force heap flags */
2677 Flags
|= Heap
->ForceFlags
;
2679 /* Call special heap */
2680 if (RtlpHeapIsSpecial(Flags
))
2681 return RtlDebugReAllocateHeap(Heap
, Flags
, Ptr
, Size
);
2683 /* Make sure size is valid */
2684 if (Size
>= 0x80000000)
2686 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
2690 /* Calculate allocation size and index */
2692 AllocationSize
= Size
;
2695 AllocationSize
= (AllocationSize
+ Heap
->AlignRound
) & Heap
->AlignMask
;
2697 /* Add up extra stuff, if it is present anywhere */
2698 if (((((PHEAP_ENTRY
)Ptr
)-1)->Flags
& HEAP_ENTRY_EXTRA_PRESENT
) ||
2699 (Flags
& HEAP_EXTRA_FLAGS_MASK
) ||
2700 Heap
->PseudoTagEntries
)
2702 AllocationSize
+= sizeof(HEAP_ENTRY_EXTRA
);
2705 /* Acquire the lock if necessary */
2706 if (!(Flags
& HEAP_NO_SERIALIZE
))
2708 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
2710 Flags
&= ~HEAP_NO_SERIALIZE
;
2713 /* Get the pointer to the in-use entry */
2714 InUseEntry
= (PHEAP_ENTRY
)Ptr
- 1;
2716 /* If that entry is not really in-use, we have a problem */
2717 if (!(InUseEntry
->Flags
& HEAP_ENTRY_BUSY
))
2719 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
2721 /* Release the lock and return */
2723 RtlLeaveHeapLock(Heap
->LockVariable
);
2727 if (InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2729 /* This is a virtually allocated block. Get its size */
2730 OldSize
= RtlpGetSizeOfBigBlock(InUseEntry
);
2732 /* Convert it to an index */
2733 OldIndex
= (OldSize
+ InUseEntry
->Size
) >> HEAP_ENTRY_SHIFT
;
2735 /* Calculate new allocation size and round it to the page size */
2736 AllocationSize
+= FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2737 AllocationSize
= ROUND_UP(AllocationSize
, PAGE_SIZE
);
2742 OldIndex
= InUseEntry
->Size
;
2744 OldSize
= (OldIndex
<< HEAP_ENTRY_SHIFT
) - InUseEntry
->UnusedBytes
;
2747 /* Calculate new index */
2748 Index
= AllocationSize
>> HEAP_ENTRY_SHIFT
;
2750 /* Check for 4 different scenarios (old size, new size, old index, new index) */
2751 if (Index
<= OldIndex
)
2753 /* Difference must be greater than 1, adjust if it's not so */
2754 if (Index
+ 1 == OldIndex
)
2757 AllocationSize
+= sizeof(HEAP_ENTRY
);
2760 /* Calculate new size */
2761 if (InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2763 /* Simple in case of a virtual alloc - just an unused size */
2764 InUseEntry
->Size
= (USHORT
)(AllocationSize
- Size
);
2766 else if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2768 /* There is extra stuff, take it into account */
2769 OldExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ InUseEntry
->Size
- 1);
2770 NewExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ Index
- 1);
2771 *NewExtra
= *OldExtra
;
2773 // FIXME Tagging, TagIndex
2775 /* Update unused bytes count */
2776 InUseEntry
->UnusedBytes
= (UCHAR
)(AllocationSize
- Size
);
2780 // FIXME Tagging, SmallTagIndex
2781 InUseEntry
->UnusedBytes
= (UCHAR
)(AllocationSize
- Size
);
2784 /* If new size is bigger than the old size */
2787 /* Zero out that additional space if required */
2788 if (Flags
& HEAP_ZERO_MEMORY
)
2790 RtlZeroMemory((PCHAR
)Ptr
+ OldSize
, Size
- OldSize
);
2792 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2794 /* Fill it on free if required */
2795 RemainderBytes
= OldSize
& (sizeof(ULONG
) - 1);
2798 RemainderBytes
= 4 - RemainderBytes
;
2800 if (Size
> (OldSize
+ RemainderBytes
))
2802 /* Calculate actual amount of extra bytes to fill */
2803 ExtraSize
= (Size
- (OldSize
+ RemainderBytes
)) & ~(sizeof(ULONG
) - 1);
2805 /* Fill them if there are any */
2808 RtlFillMemoryUlong((PCHAR
)(InUseEntry
+ 1) + OldSize
+ RemainderBytes
,
2810 ARENA_INUSE_FILLER
);
2816 /* Fill tail of the heap entry if required */
2817 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2819 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
,
2824 /* Check if the difference is significant or not */
2825 if (Index
!= OldIndex
)
2828 FreeFlags
= InUseEntry
->Flags
& ~HEAP_ENTRY_BUSY
;
2830 if (FreeFlags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2832 /* This is a virtual block allocation */
2833 VirtualAllocBlock
= CONTAINING_RECORD(InUseEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2837 DecommitBase
= (PCHAR
)VirtualAllocBlock
+ AllocationSize
;
2838 DecommitSize
= (OldIndex
<< HEAP_ENTRY_SHIFT
) - AllocationSize
;
2840 /* Release the memory */
2841 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
2842 (PVOID
*)&DecommitBase
,
2846 if (!NT_SUCCESS(Status
))
2848 DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase
, DecommitSize
, Status
);
2852 /* Otherwise reduce the commit size */
2853 VirtualAllocBlock
->CommitSize
-= DecommitSize
;
2858 /* Reduce size of the block and possibly split it */
2859 SplitBlock
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
2861 /* Initialize this entry */
2862 SplitBlock
->Flags
= FreeFlags
;
2863 SplitBlock
->PreviousSize
= (USHORT
)Index
;
2864 SplitBlock
->SegmentOffset
= InUseEntry
->SegmentOffset
;
2866 /* Remember free size */
2867 FreeSize
= InUseEntry
->Size
- Index
;
2870 InUseEntry
->Size
= (USHORT
)Index
;
2871 InUseEntry
->Flags
&= ~HEAP_ENTRY_LAST_ENTRY
;
2873 /* Is that the last entry */
2874 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
2876 /* Set its size and insert it to the list */
2877 SplitBlock
->Size
= (USHORT
)FreeSize
;
2878 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2880 /* Update total free size */
2881 Heap
->TotalFreeSize
+= FreeSize
;
2885 /* Get the block after that one */
2886 SplitBlock2
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
);
2888 if (SplitBlock2
->Flags
& HEAP_ENTRY_BUSY
)
2890 /* It's in use, add it here*/
2891 SplitBlock
->Size
= (USHORT
)FreeSize
;
2893 /* Update previous size of the next entry */
2894 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= (USHORT
)FreeSize
;
2896 /* Insert it to the list */
2897 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2899 /* Update total size */
2900 Heap
->TotalFreeSize
+= FreeSize
;
2904 /* Next entry is free, so merge with it */
2905 SplitBlock
->Flags
= SplitBlock2
->Flags
;
2907 /* Remove it, update total size */
2908 RtlpRemoveFreeBlock(Heap
, SplitBlock2
, FALSE
, FALSE
);
2909 Heap
->TotalFreeSize
-= SplitBlock2
->Size
;
2911 /* Calculate total free size */
2912 FreeSize
+= SplitBlock2
->Size
;
2914 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
2916 SplitBlock
->Size
= (USHORT
)FreeSize
;
2918 if (!(SplitBlock
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
2920 /* Update previous size of the next entry */
2921 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= (USHORT
)FreeSize
;
2924 /* Insert the new one back and update total size */
2925 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2926 Heap
->TotalFreeSize
+= FreeSize
;
2931 RtlpInsertFreeBlock(Heap
, SplitBlock
, FreeSize
);
2940 /* We're growing the block */
2941 if ((InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
) ||
2942 !RtlpGrowBlockInPlace(Heap
, Flags
, InUseEntry
, Size
, Index
))
2944 /* Growing in place failed, so growing out of place */
2945 if (Flags
& HEAP_REALLOC_IN_PLACE_ONLY
)
2947 DPRINT1("Realloc in place failed, but it was the only option\n");
2952 /* Clear tag bits */
2953 Flags
&= ~HEAP_TAG_MASK
;
2955 /* Process extra stuff */
2956 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2958 /* Preserve user settable flags */
2959 Flags
&= ~HEAP_SETTABLE_USER_FLAGS
;
2961 Flags
|= HEAP_SETTABLE_USER_VALUE
| ((InUseEntry
->Flags
& HEAP_ENTRY_SETTABLE_FLAGS
) << 4);
2963 /* Get pointer to the old extra data */
2964 OldExtra
= RtlpGetExtraStuffPointer(InUseEntry
);
2966 /* Save tag index if it was set */
2967 if (OldExtra
->TagIndex
&&
2968 !(OldExtra
->TagIndex
& HEAP_PSEUDO_TAG_FLAG
))
2970 Flags
|= OldExtra
->TagIndex
<< HEAP_TAG_SHIFT
;
2973 else if (InUseEntry
->SmallTagIndex
)
2975 /* Take small tag index into account */
2976 Flags
|= InUseEntry
->SmallTagIndex
<< HEAP_TAG_SHIFT
;
2979 /* Allocate new block from the heap */
2980 NewBaseAddress
= RtlAllocateHeap(HeapPtr
,
2981 Flags
& ~HEAP_ZERO_MEMORY
,
2984 /* Proceed if it didn't fail */
2987 /* Get new entry pointer */
2988 NewInUseEntry
= (PHEAP_ENTRY
)NewBaseAddress
- 1;
2990 /* Process extra stuff if it exists */
2991 if (NewInUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2993 NewExtra
= RtlpGetExtraStuffPointer(NewInUseEntry
);
2995 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2997 OldExtra
= RtlpGetExtraStuffPointer(InUseEntry
);
2998 NewExtra
->Settable
= OldExtra
->Settable
;
3002 RtlZeroMemory(NewExtra
, sizeof(*NewExtra
));
3006 /* Copy actual user bits */
3008 RtlMoveMemory(NewBaseAddress
, Ptr
, Size
);
3010 RtlMoveMemory(NewBaseAddress
, Ptr
, OldSize
);
3012 /* Zero remaining part if required */
3013 if (Size
> OldSize
&&
3014 (Flags
& HEAP_ZERO_MEMORY
))
3016 RtlZeroMemory((PCHAR
)NewBaseAddress
+ OldSize
, Size
- OldSize
);
3019 /* Free the old block */
3020 RtlFreeHeap(HeapPtr
, Flags
, Ptr
);
3023 Ptr
= NewBaseAddress
;
3028 /* Did resizing fail? */
3029 if (!Ptr
&& (Flags
& HEAP_GENERATE_EXCEPTIONS
))
3031 /* Generate an exception if required */
3032 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
3033 ExceptionRecord
.ExceptionRecord
= NULL
;
3034 ExceptionRecord
.NumberParameters
= 1;
3035 ExceptionRecord
.ExceptionFlags
= 0;
3036 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
3038 RtlRaiseException(&ExceptionRecord
);
3041 /* Release the heap lock if it was acquired */
3043 RtlLeaveHeapLock(Heap
->LockVariable
);
3049 /***********************************************************************
3055 RtlCompactHeap(HANDLE Heap
,
3063 /***********************************************************************
3065 * Attempts to acquire the critical section object for a specified heap.
3068 * Heap [in] Handle of heap to lock for exclusive access
3077 RtlLockHeap(IN HANDLE HeapPtr
)
3079 PHEAP Heap
= (PHEAP
)HeapPtr
;
3081 // FIXME Check for special heap
3083 /* Check if it's really a heap */
3084 if (Heap
->Signature
!= HEAP_SIGNATURE
) return FALSE
;
3086 /* Lock if it's lockable */
3087 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3089 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
3096 /***********************************************************************
3098 * Releases ownership of the critical section object.
3101 * Heap [in] Handle to the heap to unlock
3110 RtlUnlockHeap(HANDLE HeapPtr
)
3112 PHEAP Heap
= (PHEAP
)HeapPtr
;
3114 // FIXME Check for special heap
3116 /* Check if it's really a heap */
3117 if (Heap
->Signature
!= HEAP_SIGNATURE
) return FALSE
;
3119 /* Unlock if it's lockable */
3120 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3122 RtlLeaveHeapLock(Heap
->LockVariable
);
3129 /***********************************************************************
3132 * Heap [in] Handle of heap
3133 * Flags [in] Heap size control flags
3134 * Ptr [in] Address of memory to return size for
3137 * Size in bytes of allocated memory
3138 * 0xffffffff: Failure
3149 PHEAP Heap
= (PHEAP
)HeapPtr
;
3150 PHEAP_ENTRY HeapEntry
;
3153 // FIXME This is a hack around missing SEH support!
3156 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE
);
3161 Flags
|= Heap
->ForceFlags
;
3163 /* Call special heap */
3164 if (RtlpHeapIsSpecial(Flags
))
3165 return RtlDebugSizeHeap(Heap
, Flags
, Ptr
);
3167 /* Get the heap entry pointer */
3168 HeapEntry
= (PHEAP_ENTRY
)Ptr
- 1;
3170 /* Return -1 if that entry is free */
3171 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3173 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3177 /* Get size of this block depending if it's a usual or a big one */
3178 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
3180 EntrySize
= RtlpGetSizeOfBigBlock(HeapEntry
);
3185 EntrySize
= (HeapEntry
->Size
<< HEAP_ENTRY_SHIFT
) - HeapEntry
->UnusedBytes
;
3188 /* Return calculated size */
3193 RtlpCheckInUsePattern(PHEAP_ENTRY HeapEntry
)
3195 SIZE_T Size
, Result
;
3198 /* Calculate size */
3199 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
3200 Size
= RtlpGetSizeOfBigBlock(HeapEntry
);
3202 Size
= (HeapEntry
->Size
<< HEAP_ENTRY_SHIFT
) - HeapEntry
->UnusedBytes
;
3204 /* Calculate pointer to the tail part of the block */
3205 TailPart
= (PCHAR
)(HeapEntry
+ 1) + Size
;
3207 /* Compare tail pattern */
3208 Result
= RtlCompareMemory(TailPart
,
3212 if (Result
!= HEAP_ENTRY_SIZE
)
3214 DPRINT1("HEAP: Heap entry (size %x) %p tail is modified at %p\n", Size
, HeapEntry
, TailPart
+ Result
);
3223 RtlpValidateHeapHeaders(
3225 BOOLEAN Recalculate
)
3227 // We skip header validation for now
3232 RtlpValidateHeapEntry(
3234 PHEAP_ENTRY HeapEntry
)
3236 BOOLEAN BigAllocation
, EntryFound
= FALSE
;
3237 PHEAP_SEGMENT Segment
;
3238 ULONG SegmentOffset
;
3240 /* Perform various consistency checks of this entry */
3241 if (!HeapEntry
) goto invalid_entry
;
3242 if ((ULONG_PTR
)HeapEntry
& (HEAP_ENTRY_SIZE
- 1)) goto invalid_entry
;
3243 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
)) goto invalid_entry
;
3245 BigAllocation
= HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
;
3246 Segment
= Heap
->Segments
[HeapEntry
->SegmentOffset
];
3248 if (BigAllocation
&&
3249 (((ULONG_PTR
)HeapEntry
& (PAGE_SIZE
- 1)) != FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
)))
3252 if (!BigAllocation
&& (HeapEntry
->SegmentOffset
>= HEAP_SEGMENTS
||
3254 HeapEntry
< Segment
->FirstEntry
||
3255 HeapEntry
>= Segment
->LastValidEntry
))
3258 if ((HeapEntry
->Flags
& HEAP_ENTRY_FILL_PATTERN
) &&
3259 !RtlpCheckInUsePattern(HeapEntry
))
3262 /* Checks are done, if this is a virtual entry, that's all */
3263 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
) return TRUE
;
3265 /* Go through segments and check if this entry fits into any of them */
3266 for (SegmentOffset
= 0; SegmentOffset
< HEAP_SEGMENTS
; SegmentOffset
++)
3268 Segment
= Heap
->Segments
[SegmentOffset
];
3269 if (!Segment
) continue;
3271 if ((HeapEntry
>= Segment
->FirstEntry
) &&
3272 (HeapEntry
< Segment
->LastValidEntry
))
3280 /* Return our result of finding entry in the segments */
3284 DPRINT1("HEAP: Invalid heap entry %p in heap %p\n", HeapEntry
, Heap
);
3289 RtlpValidateHeapSegment(
3291 PHEAP_SEGMENT Segment
,
3292 UCHAR SegmentOffset
,
3293 PULONG FreeEntriesCount
,
3294 PSIZE_T TotalFreeSize
,
3296 PSIZE_T PseudoTagEntries
)
3298 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
3299 PLIST_ENTRY UcrEntry
;
3300 SIZE_T ByteSize
, Size
, Result
;
3301 PHEAP_ENTRY CurrentEntry
;
3302 ULONG UnCommittedPages
;
3303 ULONG UnCommittedRanges
;
3306 UnCommittedPages
= 0;
3307 UnCommittedRanges
= 0;
3309 if (IsListEmpty(&Segment
->UCRSegmentList
))
3312 UcrDescriptor
= NULL
;
3316 UcrEntry
= Segment
->UCRSegmentList
.Flink
;
3317 UcrDescriptor
= CONTAINING_RECORD(UcrEntry
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
3320 if (Segment
->BaseAddress
== Heap
)
3321 CurrentEntry
= &Heap
->Entry
;
3323 CurrentEntry
= &Segment
->Entry
;
3325 while (CurrentEntry
< Segment
->LastValidEntry
)
3327 if (UcrDescriptor
&&
3328 ((PVOID
)CurrentEntry
>= UcrDescriptor
->Address
))
3330 DPRINT1("HEAP: Entry %p is not inside uncommited range [%p .. %p)\n",
3331 CurrentEntry
, UcrDescriptor
->Address
,
3332 (PCHAR
)UcrDescriptor
->Address
+ UcrDescriptor
->Size
);
3339 while (CurrentEntry
< Segment
->LastValidEntry
)
3341 if (PreviousSize
!= CurrentEntry
->PreviousSize
)
3343 DPRINT1("HEAP: Entry %p has incorrect PreviousSize %x instead of %x\n",
3344 CurrentEntry
, CurrentEntry
->PreviousSize
, PreviousSize
);
3349 PreviousSize
= CurrentEntry
->Size
;
3350 Size
= CurrentEntry
->Size
<< HEAP_ENTRY_SHIFT
;
3352 if (CurrentEntry
->Flags
& HEAP_ENTRY_BUSY
)
3359 /* Check fill pattern */
3360 if (CurrentEntry
->Flags
& HEAP_ENTRY_FILL_PATTERN
)
3362 if (!RtlpCheckInUsePattern(CurrentEntry
))
3368 /* The entry is free, increase free entries count and total free size */
3369 *FreeEntriesCount
= *FreeEntriesCount
+ 1;
3370 *TotalFreeSize
+= CurrentEntry
->Size
;
3372 if ((Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
) &&
3373 (CurrentEntry
->Flags
& HEAP_ENTRY_FILL_PATTERN
))
3375 ByteSize
= Size
- sizeof(HEAP_FREE_ENTRY
);
3377 if ((CurrentEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
) &&
3378 (ByteSize
> sizeof(HEAP_FREE_ENTRY_EXTRA
)))
3380 ByteSize
-= sizeof(HEAP_FREE_ENTRY_EXTRA
);
3383 Result
= RtlCompareMemoryUlong((PCHAR
)((PHEAP_FREE_ENTRY
)CurrentEntry
+ 1),
3387 if (Result
!= ByteSize
)
3389 DPRINT1("HEAP: Free heap block %p modified at %p after it was freed\n",
3391 (PCHAR
)(CurrentEntry
+ 1) + Result
);
3398 if (CurrentEntry
->SegmentOffset
!= SegmentOffset
)
3400 DPRINT1("HEAP: Heap entry %p SegmentOffset is incorrect %x (should be %x)\n", CurrentEntry
, SegmentOffset
, CurrentEntry
->SegmentOffset
);
3404 /* Check if it's the last entry */
3405 if (CurrentEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
)
3407 CurrentEntry
= (PHEAP_ENTRY
)((PCHAR
)CurrentEntry
+ Size
);
3411 /* Check if it's not really the last one */
3412 if (CurrentEntry
!= Segment
->LastValidEntry
)
3414 DPRINT1("HEAP: Heap entry %p is not last block in segment (%x)\n", CurrentEntry
, Segment
->LastValidEntry
);
3418 else if (CurrentEntry
!= UcrDescriptor
->Address
)
3420 DPRINT1("HEAP: Heap entry %p does not match next uncommitted address (%p)\n",
3421 CurrentEntry
, UcrDescriptor
->Address
);
3427 UnCommittedPages
+= (ULONG
)(UcrDescriptor
->Size
/ PAGE_SIZE
);
3428 UnCommittedRanges
++;
3430 CurrentEntry
= (PHEAP_ENTRY
)((PCHAR
)UcrDescriptor
->Address
+ UcrDescriptor
->Size
);
3432 /* Go to the next UCR descriptor */
3433 UcrEntry
= UcrEntry
->Flink
;
3434 if (UcrEntry
== &Segment
->UCRSegmentList
)
3437 UcrDescriptor
= NULL
;
3441 UcrDescriptor
= CONTAINING_RECORD(UcrEntry
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
3448 /* Advance to the next entry */
3449 CurrentEntry
= (PHEAP_ENTRY
)((PCHAR
)CurrentEntry
+ Size
);
3453 /* Check total numbers of UCP and UCR */
3454 if (Segment
->NumberOfUnCommittedPages
!= UnCommittedPages
)
3456 DPRINT1("HEAP: Segment %p NumberOfUnCommittedPages is invalid (%x != %x)\n",
3457 Segment
, Segment
->NumberOfUnCommittedPages
, UnCommittedPages
);
3462 if (Segment
->NumberOfUnCommittedRanges
!= UnCommittedRanges
)
3464 DPRINT1("HEAP: Segment %p NumberOfUnCommittedRanges is invalid (%x != %x)\n",
3465 Segment
, Segment
->NumberOfUnCommittedRanges
, UnCommittedRanges
);
3474 RtlpValidateHeap(PHEAP Heap
,
3475 BOOLEAN ForceValidation
)
3477 PHEAP_SEGMENT Segment
;
3479 UCHAR SegmentOffset
;
3480 SIZE_T Size
, TotalFreeSize
;
3482 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock
;
3483 PLIST_ENTRY ListHead
, NextEntry
;
3484 PHEAP_FREE_ENTRY FreeEntry
;
3485 ULONG FreeBlocksCount
, FreeListEntriesCount
;
3488 if (!RtlpValidateHeapHeaders(Heap
, FALSE
))
3491 /* Skip validation if it's not needed */
3492 if (!ForceValidation
&& !(Heap
->Flags
& HEAP_VALIDATE_ALL_ENABLED
))
3495 /* Check free lists bitmaps */
3496 FreeListEntriesCount
= 0;
3497 ListHead
= &Heap
->FreeLists
[0];
3499 for (Size
= 0; Size
< HEAP_FREELISTS
; Size
++)
3503 /* This is a dedicated list. Check if it's empty */
3504 EmptyList
= IsListEmpty(ListHead
);
3506 if (Heap
->u
.FreeListsInUseBytes
[Size
>> 3] & (1 << (Size
& 7)))
3510 DPRINT1("HEAP: Empty %x-free list marked as non-empty\n", Size
);
3518 DPRINT1("HEAP: Non-empty %x-free list marked as empty\n", Size
);
3524 /* Now check this list entries */
3525 NextEntry
= ListHead
->Flink
;
3528 while (ListHead
!= NextEntry
)
3530 FreeEntry
= CONTAINING_RECORD(NextEntry
, HEAP_FREE_ENTRY
, FreeList
);
3531 NextEntry
= NextEntry
->Flink
;
3533 /* If there is an in-use entry in a free list - that's quite a big problem */
3534 if (FreeEntry
->Flags
& HEAP_ENTRY_BUSY
)
3536 DPRINT1("HEAP: %x-dedicated list free element %x is marked in-use\n", Size
, FreeEntry
);
3540 /* Check sizes according to that specific list's size */
3541 if ((Size
== 0) && (FreeEntry
->Size
< HEAP_FREELISTS
))
3543 DPRINT1("HEAP: Non dedicated list free element %x has size %x which would fit a dedicated list\n", FreeEntry
, FreeEntry
->Size
);
3546 else if (Size
&& (FreeEntry
->Size
!= Size
))
3548 DPRINT1("HEAP: %x-dedicated list free element %x has incorrect size %x\n", Size
, FreeEntry
, FreeEntry
->Size
);
3551 else if ((Size
== 0) && (FreeEntry
->Size
< PreviousSize
))
3553 DPRINT1("HEAP: Non dedicated list free element %x is not put in order\n", FreeEntry
);
3557 /* Remember previous size*/
3558 PreviousSize
= FreeEntry
->Size
;
3560 /* Add up to the total amount of free entries */
3561 FreeListEntriesCount
++;
3564 /* Go to the head of the next free list */
3568 /* Check big allocations */
3569 ListHead
= &Heap
->VirtualAllocdBlocks
;
3570 NextEntry
= ListHead
->Flink
;
3572 while (ListHead
!= NextEntry
)
3574 VirtualAllocBlock
= CONTAINING_RECORD(NextEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, Entry
);
3576 /* We can only check the fill pattern */
3577 if (VirtualAllocBlock
->BusyBlock
.Flags
& HEAP_ENTRY_FILL_PATTERN
)
3579 if (!RtlpCheckInUsePattern(&VirtualAllocBlock
->BusyBlock
))
3583 NextEntry
= NextEntry
->Flink
;
3586 /* Check all segments */
3587 FreeBlocksCount
= 0;
3590 for (SegmentOffset
= 0; SegmentOffset
< HEAP_SEGMENTS
; SegmentOffset
++)
3592 Segment
= Heap
->Segments
[SegmentOffset
];
3594 /* Go to the next one if there is no segment */
3595 if (!Segment
) continue;
3597 if (!RtlpValidateHeapSegment(Heap
,
3609 if (FreeListEntriesCount
!= FreeBlocksCount
)
3611 DPRINT1("HEAP: Free blocks count in arena (%d) does not match free blocks number in the free lists (%d)\n", FreeBlocksCount
, FreeListEntriesCount
);
3615 if (Heap
->TotalFreeSize
!= TotalFreeSize
)
3617 DPRINT1("HEAP: Total size of free blocks in arena (%d) does not equal to the one in heap header (%d)\n", TotalFreeSize
, Heap
->TotalFreeSize
);
3624 /***********************************************************************
3626 * Validates a specified heap.
3629 * Heap [in] Handle to the heap
3630 * Flags [in] Bit flags that control access during operation
3631 * Block [in] Optional pointer to memory block to validate
3642 BOOLEAN NTAPI
RtlValidateHeap(
3648 PHEAP Heap
= (PHEAP
)HeapPtr
;
3649 BOOLEAN HeapLocked
= FALSE
;
3652 /* Check for page heap */
3653 if (Heap
->ForceFlags
& HEAP_FLAG_PAGE_ALLOCS
)
3654 return RtlpDebugPageHeapValidate(HeapPtr
, Flags
, Block
);
3656 /* Check signature */
3657 if (Heap
->Signature
!= HEAP_SIGNATURE
)
3659 DPRINT1("HEAP: Signature %x is invalid for heap %p\n", Heap
->Signature
, Heap
);
3664 Flags
= Heap
->ForceFlags
;
3666 /* Acquire the lock if necessary */
3667 if (!(Flags
& HEAP_NO_SERIALIZE
))
3669 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
3673 /* Either validate whole heap or just one entry */
3675 HeapValid
= RtlpValidateHeap(Heap
, TRUE
);
3677 HeapValid
= RtlpValidateHeapEntry(Heap
, (PHEAP_ENTRY
)Block
- 1);
3679 /* Unlock if it's lockable */
3682 RtlLeaveHeapLock(Heap
->LockVariable
);
3689 RtlInitializeHeapManager(VOID
)
3694 Peb
= RtlGetCurrentPeb();
3696 /* Initialize heap-related fields of PEB */
3697 Peb
->NumberOfHeaps
= 0;
3699 /* Initialize the process heaps list protecting lock */
3700 RtlInitializeCriticalSection(&RtlpProcessHeapsListLock
);
3708 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine
,
3712 return STATUS_NOT_IMPLEMENTED
;
3720 RtlGetProcessHeaps(ULONG count
,
3732 RtlValidateProcessHeaps(VOID
)
3744 IN PVOID HeapHandle
,
3757 RtlSetUserValueHeap(IN PVOID HeapHandle
,
3759 IN PVOID BaseAddress
,
3762 PHEAP Heap
= (PHEAP
)HeapHandle
;
3763 PHEAP_ENTRY HeapEntry
;
3764 PHEAP_ENTRY_EXTRA Extra
;
3765 BOOLEAN HeapLocked
= FALSE
, ValueSet
= FALSE
;
3768 Flags
|= Heap
->Flags
;
3770 /* Call special heap */
3771 if (RtlpHeapIsSpecial(Flags
))
3772 return RtlDebugSetUserValueHeap(Heap
, Flags
, BaseAddress
, UserValue
);
3774 /* Lock if it's lockable */
3775 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3777 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
3781 /* Get a pointer to the entry */
3782 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3784 /* If it's a free entry - return error */
3785 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3787 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3789 /* Release the heap lock if it was acquired */
3791 RtlLeaveHeapLock(Heap
->LockVariable
);
3796 /* Check if this entry has an extra stuff associated with it */
3797 if (HeapEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
3799 /* Use extra to store the value */
3800 Extra
= RtlpGetExtraStuffPointer(HeapEntry
);
3801 Extra
->Settable
= (ULONG_PTR
)UserValue
;
3803 /* Indicate that value was set */
3807 /* Release the heap lock if it was acquired */
3809 RtlLeaveHeapLock(Heap
->LockVariable
);
3819 RtlSetUserFlagsHeap(IN PVOID HeapHandle
,
3821 IN PVOID BaseAddress
,
3822 IN ULONG UserFlagsReset
,
3823 IN ULONG UserFlagsSet
)
3825 PHEAP Heap
= (PHEAP
)HeapHandle
;
3826 PHEAP_ENTRY HeapEntry
;
3827 BOOLEAN HeapLocked
= FALSE
;
3830 Flags
|= Heap
->Flags
;
3832 /* Call special heap */
3833 if (RtlpHeapIsSpecial(Flags
))
3834 return RtlDebugSetUserFlagsHeap(Heap
, Flags
, BaseAddress
, UserFlagsReset
, UserFlagsSet
);
3836 /* Lock if it's lockable */
3837 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3839 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
3843 /* Get a pointer to the entry */
3844 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3846 /* If it's a free entry - return error */
3847 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3849 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3851 /* Release the heap lock if it was acquired */
3853 RtlLeaveHeapLock(Heap
->LockVariable
);
3858 /* Set / reset flags */
3859 HeapEntry
->Flags
&= ~(UserFlagsReset
>> 4);
3860 HeapEntry
->Flags
|= (UserFlagsSet
>> 4);
3862 /* Release the heap lock if it was acquired */
3864 RtlLeaveHeapLock(Heap
->LockVariable
);
3874 RtlGetUserInfoHeap(IN PVOID HeapHandle
,
3876 IN PVOID BaseAddress
,
3877 OUT PVOID
*UserValue
,
3878 OUT PULONG UserFlags
)
3880 PHEAP Heap
= (PHEAP
)HeapHandle
;
3881 PHEAP_ENTRY HeapEntry
;
3882 PHEAP_ENTRY_EXTRA Extra
;
3883 BOOLEAN HeapLocked
= FALSE
;
3886 Flags
|= Heap
->Flags
;
3888 /* Call special heap */
3889 if (RtlpHeapIsSpecial(Flags
))
3890 return RtlDebugGetUserInfoHeap(Heap
, Flags
, BaseAddress
, UserValue
, UserFlags
);
3892 /* Lock if it's lockable */
3893 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3895 RtlEnterHeapLock(Heap
->LockVariable
, TRUE
);
3899 /* Get a pointer to the entry */
3900 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3902 /* If it's a free entry - return error */
3903 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3905 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3907 /* Release the heap lock if it was acquired */
3909 RtlLeaveHeapLock(Heap
->LockVariable
);
3914 /* Check if this entry has an extra stuff associated with it */
3915 if (HeapEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
3917 /* Get pointer to extra data */
3918 Extra
= RtlpGetExtraStuffPointer(HeapEntry
);
3920 /* Pass user value */
3922 *UserValue
= (PVOID
)Extra
->Settable
;
3924 /* Decode and return user flags */
3926 *UserFlags
= (HeapEntry
->Flags
& HEAP_ENTRY_SETTABLE_FLAGS
) << 4;
3929 /* Release the heap lock if it was acquired */
3931 RtlLeaveHeapLock(Heap
->LockVariable
);
3941 RtlUsageHeap(IN HANDLE Heap
,
3943 OUT PRTL_HEAP_USAGE Usage
)
3947 return STATUS_NOT_IMPLEMENTED
;
3952 RtlQueryTagHeap(IN PVOID HeapHandle
,
3955 IN BOOLEAN ResetCounters
,
3956 OUT PRTL_HEAP_TAG_INFO HeapTagInfo
)
3965 RtlExtendHeap(IN HANDLE Heap
,
3977 RtlCreateTagHeap(IN HANDLE HeapHandle
,
3980 IN PWSTR TagSubName
)
3989 RtlWalkHeap(IN HANDLE HeapHandle
,
3993 return STATUS_NOT_IMPLEMENTED
;
3998 RtlProtectHeap(IN PVOID HeapHandle
,
3999 IN BOOLEAN ReadOnly
)
4007 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL
,
4008 IN HEAP_INFORMATION_CLASS HeapInformationClass
,
4009 IN PVOID HeapInformation
,
4010 IN SIZE_T HeapInformationLength
)
4012 /* Setting heap information is not really supported except for enabling LFH */
4013 if (HeapInformationClass
== 0) return STATUS_SUCCESS
;
4015 /* Check buffer length */
4016 if (HeapInformationLength
< sizeof(ULONG
))
4018 /* The provided buffer is too small */
4019 return STATUS_BUFFER_TOO_SMALL
;
4022 /* Check for a special magic value for enabling LFH */
4023 if (*(PULONG
)HeapInformation
== 2)
4025 DPRINT1("RtlSetHeapInformation() needs to enable LFH\n");
4026 return STATUS_SUCCESS
;
4029 return STATUS_UNSUCCESSFUL
;
4034 RtlQueryHeapInformation(HANDLE HeapHandle
,
4035 HEAP_INFORMATION_CLASS HeapInformationClass
,
4036 PVOID HeapInformation OPTIONAL
,
4037 SIZE_T HeapInformationLength OPTIONAL
,
4038 PSIZE_T ReturnLength OPTIONAL
)
4040 PHEAP Heap
= (PHEAP
)HeapHandle
;
4042 /* Only HeapCompatibilityInformation is supported */
4043 if (HeapInformationClass
!= HeapCompatibilityInformation
)
4044 return STATUS_UNSUCCESSFUL
;
4046 /* Set result length */
4047 if (ReturnLength
) *ReturnLength
= sizeof(ULONG
);
4049 /* Check buffer length */
4050 if (HeapInformationLength
< sizeof(ULONG
))
4052 /* It's too small, return needed length */
4053 return STATUS_BUFFER_TOO_SMALL
;
4056 /* Return front end heap type */
4057 *(PULONG
)HeapInformation
= Heap
->FrontEndHeapType
;
4059 return STATUS_SUCCESS
;
4064 RtlMultipleAllocateHeap(IN PVOID HeapHandle
,
4076 RtlMultipleFreeHeap(IN PVOID HeapHandle
,