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 HEAP_LOCK 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 */
71 RtlCompareMemoryUlong(PVOID Source
, ULONG Length
, ULONG Value
);
73 /* FUNCTIONS *****************************************************************/
76 RtlpInitializeHeap(PHEAP Heap
,
82 PVOID NextHeapBase
= Heap
+ 1;
83 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
89 *HeaderSize
+= NumUCRs
* sizeof(*UcrDescriptor
);
91 /* Prepare a list of UCRs */
92 InitializeListHead(&Heap
->UCRList
);
93 InitializeListHead(&Heap
->UCRSegmentList
);
94 UcrDescriptor
= NextHeapBase
;
96 for (i
=0; i
<NumUCRs
; i
++, UcrDescriptor
++)
98 InsertTailList(&Heap
->UCRList
, &UcrDescriptor
->ListEntry
);
101 NextHeapBase
= UcrDescriptor
;
104 /* Round up header size again */
105 *HeaderSize
= ROUND_UP(*HeaderSize
, HEAP_ENTRY_SIZE
);
107 ASSERT(*HeaderSize
<= PAGE_SIZE
);
109 /* Initialize heap's header */
110 Heap
->Entry
.Size
= (*HeaderSize
) >> HEAP_ENTRY_SHIFT
;
111 Heap
->Entry
.Flags
= HEAP_ENTRY_BUSY
;
113 Heap
->Signature
= HEAP_SIGNATURE
;
115 Heap
->ForceFlags
= (Flags
& (HEAP_NO_SERIALIZE
|
116 HEAP_GENERATE_EXCEPTIONS
|
118 HEAP_REALLOC_IN_PLACE_ONLY
|
119 HEAP_VALIDATE_PARAMETERS_ENABLED
|
120 HEAP_VALIDATE_ALL_ENABLED
|
121 HEAP_TAIL_CHECKING_ENABLED
|
122 HEAP_CREATE_ALIGN_16
|
123 HEAP_FREE_CHECKING_ENABLED
));
124 Heap
->HeaderValidateCopy
= NULL
;
125 Heap
->HeaderValidateLength
= ((PCHAR
)NextHeapBase
- (PCHAR
)Heap
);
127 /* Initialize free lists */
128 for (i
=0; i
<HEAP_FREELISTS
; i
++)
130 InitializeListHead(&Heap
->FreeLists
[i
]);
133 /* Initialize "big" allocations list */
134 InitializeListHead(&Heap
->VirtualAllocdBlocks
);
136 /* Initialize lock */
140 Status
= RtlInitializeHeapLock((PHEAP_LOCK
)Lock
);
141 if (!NT_SUCCESS(Status
))
143 DPRINT1("Initializing the lock failed!\n");
144 return /*NULL*/; // FIXME!
148 /* Set the lock variable */
149 Heap
->LockVariable
= Lock
;
153 RtlpSetFreeListsBit(PHEAP Heap
,
154 PHEAP_FREE_ENTRY FreeEntry
)
158 ASSERT(FreeEntry
->Size
< HEAP_FREELISTS
);
160 /* Calculate offset in the free list bitmap */
161 Index
= FreeEntry
->Size
>> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
162 Bit
= 1 << (FreeEntry
->Size
& 7);
164 /* Assure it's not already set */
165 ASSERT((Heap
->u
.FreeListsInUseBytes
[Index
] & Bit
) == 0);
168 Heap
->u
.FreeListsInUseBytes
[Index
] |= Bit
;
172 RtlpClearFreeListsBit(PHEAP Heap
,
173 PHEAP_FREE_ENTRY FreeEntry
)
177 ASSERT(FreeEntry
->Size
< HEAP_FREELISTS
);
179 /* Calculate offset in the free list bitmap */
180 Index
= FreeEntry
->Size
>> 3; /* = FreeEntry->Size / (sizeof(UCHAR) * 8)*/
181 Bit
= 1 << (FreeEntry
->Size
& 7);
183 /* Assure it was set and the corresponding free list is empty */
184 ASSERT(Heap
->u
.FreeListsInUseBytes
[Index
] & Bit
);
185 ASSERT(IsListEmpty(&Heap
->FreeLists
[FreeEntry
->Size
]));
188 Heap
->u
.FreeListsInUseBytes
[Index
] ^= Bit
;
192 RtlpInsertFreeBlockHelper(PHEAP Heap
,
193 PHEAP_FREE_ENTRY FreeEntry
,
197 PLIST_ENTRY FreeListHead
, Current
;
198 PHEAP_FREE_ENTRY CurrentEntry
;
200 ASSERT(FreeEntry
->Size
== BlockSize
);
202 /* Fill if it's not denied */
205 FreeEntry
->Flags
&= ~(HEAP_ENTRY_FILL_PATTERN
|
206 HEAP_ENTRY_EXTRA_PRESENT
|
209 if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
211 RtlFillMemoryUlong((PCHAR
)(FreeEntry
+ 1),
212 (BlockSize
<< HEAP_ENTRY_SHIFT
) - sizeof(*FreeEntry
),
215 FreeEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
220 /* Clear out all flags except the last entry one */
221 FreeEntry
->Flags
&= HEAP_ENTRY_LAST_ENTRY
;
224 /* Check if PreviousSize of the next entry matches ours */
225 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
227 ASSERT(((PHEAP_ENTRY
)FreeEntry
+ BlockSize
)->PreviousSize
= BlockSize
);
230 /* Insert it either into dedicated or non-dedicated list */
231 if (BlockSize
< HEAP_FREELISTS
)
234 FreeListHead
= &Heap
->FreeLists
[BlockSize
];
236 if (IsListEmpty(FreeListHead
))
238 RtlpSetFreeListsBit(Heap
, FreeEntry
);
243 /* Non-dedicated one */
244 FreeListHead
= &Heap
->FreeLists
[0];
245 Current
= FreeListHead
->Flink
;
247 /* Find a position where to insert it to (the list must be sorted) */
248 while (FreeListHead
!= Current
)
250 CurrentEntry
= CONTAINING_RECORD(Current
, HEAP_FREE_ENTRY
, FreeList
);
252 if (BlockSize
<= CurrentEntry
->Size
)
255 Current
= Current
->Flink
;
258 FreeListHead
= Current
;
261 /* Actually insert it into the list */
262 InsertTailList(FreeListHead
, &FreeEntry
->FreeList
);
266 RtlpInsertFreeBlock(PHEAP Heap
,
267 PHEAP_FREE_ENTRY FreeEntry
,
270 USHORT Size
, PreviousSize
;
271 UCHAR SegmentOffset
, Flags
;
272 PHEAP_SEGMENT Segment
;
274 DPRINT("RtlpInsertFreeBlock(%p %p %x)\n", Heap
, FreeEntry
, BlockSize
);
276 /* Increase the free size counter */
277 Heap
->TotalFreeSize
+= BlockSize
;
279 /* Remember certain values */
280 Flags
= FreeEntry
->Flags
;
281 PreviousSize
= FreeEntry
->PreviousSize
;
282 SegmentOffset
= FreeEntry
->SegmentOffset
;
283 Segment
= Heap
->Segments
[SegmentOffset
];
288 /* Check for the max size */
289 if (BlockSize
> HEAP_MAX_BLOCK_SIZE
)
291 Size
= HEAP_MAX_BLOCK_SIZE
;
293 /* Special compensation if it goes above limit just by 1 */
294 if (BlockSize
== (HEAP_MAX_BLOCK_SIZE
+ 1))
297 FreeEntry
->Flags
= 0;
302 FreeEntry
->Flags
= Flags
;
305 /* Change its size and insert it into a free list */
306 FreeEntry
->Size
= Size
;
307 FreeEntry
->PreviousSize
= PreviousSize
;
308 FreeEntry
->SegmentOffset
= SegmentOffset
;
310 /* Call a helper to actually insert the block */
311 RtlpInsertFreeBlockHelper(Heap
, FreeEntry
, Size
, FALSE
);
317 /* Go to the next entry */
318 FreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ Size
);
320 /* Check if that's all */
321 if ((PHEAP_ENTRY
)FreeEntry
>= Segment
->LastValidEntry
) return;
324 /* Update previous size if needed */
325 if (!(Flags
& HEAP_ENTRY_LAST_ENTRY
))
326 FreeEntry
->PreviousSize
= PreviousSize
;
330 RtlpRemoveFreeBlock(PHEAP Heap
,
331 PHEAP_FREE_ENTRY FreeEntry
,
335 SIZE_T Result
, RealSize
;
336 PLIST_ENTRY OldBlink
, OldFlink
;
338 // FIXME: Maybe use RemoveEntryList?
340 /* Remove the free block */
341 OldFlink
= FreeEntry
->FreeList
.Flink
;
342 OldBlink
= FreeEntry
->FreeList
.Blink
;
343 OldBlink
->Flink
= OldFlink
;
344 OldFlink
->Blink
= OldBlink
;
346 /* Update the freelists bitmap */
347 if ((OldFlink
== OldBlink
) &&
348 (Dedicated
|| (!Dedicated
&& FreeEntry
->Size
< HEAP_FREELISTS
)))
350 RtlpClearFreeListsBit(Heap
, FreeEntry
);
353 /* Fill with pattern if necessary */
355 (FreeEntry
->Flags
& HEAP_ENTRY_FILL_PATTERN
))
357 RealSize
= (FreeEntry
->Size
<< HEAP_ENTRY_SHIFT
) - sizeof(*FreeEntry
);
359 /* Deduct extra stuff from block's real size */
360 if (FreeEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
&&
361 RealSize
> sizeof(HEAP_FREE_ENTRY_EXTRA
))
363 RealSize
-= sizeof(HEAP_FREE_ENTRY_EXTRA
);
366 /* Check if the free filler is intact */
367 Result
= RtlCompareMemoryUlong((PCHAR
)(FreeEntry
+ 1),
371 if (Result
!= RealSize
)
373 DPRINT1("Free heap block %p modified at %p after it was freed\n",
375 (PCHAR
)(FreeEntry
+ 1) + Result
);
381 RtlpGetSizeOfBigBlock(PHEAP_ENTRY HeapEntry
)
383 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
385 /* Get pointer to the containing record */
386 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
388 /* Restore the real size */
389 return VirtualEntry
->CommitSize
- HeapEntry
->Size
;
392 PHEAP_UCR_DESCRIPTOR NTAPI
393 RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment
)
396 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
397 PHEAP Heap
= Segment
->Heap
;
399 DPRINT("RtlpCreateUnCommittedRange(%p)\n", Segment
);
401 /* Check if we have unused UCRs */
402 if (IsListEmpty(&Heap
->UCRList
))
407 /* There are unused UCRs, just get the first one */
408 Entry
= RemoveHeadList(&Heap
->UCRList
);
409 UcrDescriptor
= CONTAINING_RECORD(Entry
, HEAP_UCR_DESCRIPTOR
, ListEntry
);
410 return UcrDescriptor
;
414 RtlpDestroyUnCommittedRange(PHEAP_SEGMENT Segment
,
415 PHEAP_UCR_DESCRIPTOR UcrDescriptor
)
418 UcrDescriptor
->Address
= NULL
;
419 UcrDescriptor
->Size
= 0;
421 /* Put it into the heap's list of unused UCRs */
422 InsertHeadList(&Segment
->Heap
->UCRList
, &UcrDescriptor
->ListEntry
);
426 RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment
,
431 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
433 DPRINT("RtlpInsertUnCommittedPages(%p %p %x)\n", Segment
, Address
, Size
);
435 /* Go through the list of UCR descriptors, they are sorted from lowest address
437 Current
= Segment
->UCRSegmentList
.Flink
;
438 while(Current
!= &Segment
->UCRSegmentList
)
440 UcrDescriptor
= CONTAINING_RECORD(Current
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
442 if ((ULONG_PTR
)UcrDescriptor
->Address
> Address
)
444 /* Check for a really lucky case */
445 if ((Address
+ Size
) == (ULONG_PTR
)UcrDescriptor
->Address
)
448 UcrDescriptor
->Address
= (PVOID
)Address
;
449 UcrDescriptor
->Size
+= Size
;
453 /* We found the block after which the new one should go */
456 else if (((ULONG_PTR
)UcrDescriptor
->Address
+ UcrDescriptor
->Size
) == Address
)
458 /* Modify this entry */
459 Address
= (ULONG_PTR
)UcrDescriptor
->Address
;
460 Size
+= UcrDescriptor
->Size
;
462 /* Remove it from the list and destroy it */
463 RemoveEntryList(Current
);
464 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
466 Segment
->NumberOfUnCommittedRanges
--;
470 /* Advance to the next descriptor */
471 Current
= Current
->Flink
;
475 /* Create a new UCR descriptor */
476 UcrDescriptor
= RtlpCreateUnCommittedRange(Segment
);
477 if (!UcrDescriptor
) return;
479 UcrDescriptor
->Address
= (PVOID
)Address
;
480 UcrDescriptor
->Size
= Size
;
482 /* "Current" is the descriptor after which our one should go */
483 InsertTailList(Current
, &UcrDescriptor
->SegmentEntry
);
485 DPRINT("Added segment UCR with base %p, size 0x%x\n", Address
, Size
);
487 /* Increase counters */
488 Segment
->NumberOfUnCommittedRanges
++;
491 PHEAP_FREE_ENTRY NTAPI
492 RtlpFindAndCommitPages(PHEAP Heap
,
493 PHEAP_SEGMENT Segment
,
498 PHEAP_UCR_DESCRIPTOR UcrDescriptor
, PreviousUcr
= NULL
;
499 PHEAP_ENTRY FirstEntry
, LastEntry
, PreviousLastEntry
;
502 DPRINT("RtlpFindAndCommitPages(%p %p %x %p)\n", Heap
, Segment
, *Size
, Address
);
504 /* Go through UCRs in a segment */
505 Current
= Segment
->UCRSegmentList
.Flink
;
506 while(Current
!= &Segment
->UCRSegmentList
)
508 UcrDescriptor
= CONTAINING_RECORD(Current
, HEAP_UCR_DESCRIPTOR
, SegmentEntry
);
510 /* Check if we can use that one right away */
511 if (UcrDescriptor
->Size
>= *Size
&&
512 (UcrDescriptor
->Address
== Address
|| !Address
))
514 /* Get the address */
515 Address
= UcrDescriptor
->Address
;
518 if (Heap
->CommitRoutine
)
520 Status
= Heap
->CommitRoutine(Heap
, &Address
, Size
);
524 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
532 DPRINT("Committed %d bytes at base %p, UCR size is %d\n", *Size
, Address
, UcrDescriptor
->Size
);
534 /* Fail in unsuccessful case */
535 if (!NT_SUCCESS(Status
))
537 DPRINT1("Committing page failed with status 0x%08X\n", Status
);
541 /* Update tracking numbers */
542 Segment
->NumberOfUnCommittedPages
-= *Size
/ PAGE_SIZE
;
544 /* Calculate first and last entries */
545 FirstEntry
= (PHEAP_ENTRY
)Address
;
547 if ((Segment
->LastEntryInSegment
->Flags
& HEAP_ENTRY_LAST_ENTRY
) &&
548 (ULONG_PTR
)(Segment
->LastEntryInSegment
+ Segment
->LastEntryInSegment
->Size
) == (ULONG_PTR
)UcrDescriptor
->Address
)
550 LastEntry
= Segment
->LastEntryInSegment
;
554 /* Go through the entries to find the last one */
557 LastEntry
= (PHEAP_ENTRY
)((ULONG_PTR
)PreviousUcr
->Address
+ PreviousUcr
->Size
);
559 LastEntry
= Segment
->FirstEntry
;
561 while (!(LastEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
563 PreviousLastEntry
= LastEntry
;
564 LastEntry
+= LastEntry
->Size
;
566 if ((ULONG_PTR
)LastEntry
>= (ULONG_PTR
)Segment
->LastValidEntry
||
567 LastEntry
->Size
== 0)
569 if (LastEntry
== (PHEAP_ENTRY
)Address
)
572 LastEntry
= PreviousLastEntry
;
576 DPRINT1("Last entry not found in a committed range near to %p\n", PreviousLastEntry
);
582 /* Unmark it as a last entry */
583 LastEntry
->Flags
&= ~HEAP_ENTRY_LAST_ENTRY
;
585 /* Update UCR descriptor */
586 UcrDescriptor
->Address
= (PUCHAR
)UcrDescriptor
->Address
+ *Size
;
587 UcrDescriptor
->Size
-= *Size
;
589 DPRINT("Updating UcrDescriptor %p, new Address %p, size %d\n",
590 UcrDescriptor
, UcrDescriptor
->Address
, UcrDescriptor
->Size
);
592 /* Check if anything left in this UCR */
593 if (UcrDescriptor
->Size
== 0)
595 /* It's fully exhausted */
596 if (UcrDescriptor
->Address
== Segment
->LastValidEntry
)
598 FirstEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
599 Segment
->LastEntryInSegment
= FirstEntry
;
603 FirstEntry
->Flags
= 0;
604 Segment
->LastEntryInSegment
= Segment
->FirstEntry
;
607 /* This UCR needs to be removed because it became useless */
608 RemoveEntryList(&UcrDescriptor
->SegmentEntry
);
610 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
611 Segment
->NumberOfUnCommittedRanges
--;
615 FirstEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
616 Segment
->LastEntryInSegment
= FirstEntry
;
619 /* Set various first entry fields*/
620 FirstEntry
->SegmentOffset
= LastEntry
->SegmentOffset
;
621 FirstEntry
->Size
= *Size
>> HEAP_ENTRY_SHIFT
;
622 FirstEntry
->PreviousSize
= LastEntry
->Size
;
624 /* Update previous size */
625 if (!(FirstEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
626 (FirstEntry
+ FirstEntry
->Size
)->PreviousSize
= FirstEntry
->Size
;
629 return (PHEAP_FREE_ENTRY
)FirstEntry
;
632 /* Advance to the next descriptor */
633 Current
= Current
->Flink
;
640 RtlpDeCommitFreeBlock(PHEAP Heap
,
641 PHEAP_FREE_ENTRY FreeEntry
,
645 PHEAP_SEGMENT Segment
;
646 PHEAP_ENTRY PrecedingInUseEntry
= NULL
, NextInUseEntry
= NULL
;
647 PHEAP_FREE_ENTRY NextFreeEntry
;
648 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
649 ULONG PrecedingSize
, NextSize
, DecommitSize
;
653 /* We can't decommit if there is a commit routine! */
654 if (Heap
->CommitRoutine
)
656 /* Just add it back the usual way */
657 RtlpInsertFreeBlock(Heap
, FreeEntry
, Size
);
661 /* Get the segment */
662 Segment
= Heap
->Segments
[FreeEntry
->SegmentOffset
];
664 /* Get the preceding entry */
665 DecommitBase
= ROUND_UP(FreeEntry
, PAGE_SIZE
);
666 PrecedingSize
= (PHEAP_ENTRY
)DecommitBase
- (PHEAP_ENTRY
)FreeEntry
;
668 if (PrecedingSize
== 1)
670 /* Just 1 heap entry, increase the base/size */
671 DecommitBase
+= PAGE_SIZE
;
672 PrecedingSize
+= PAGE_SIZE
>> HEAP_ENTRY_SHIFT
;
674 else if (FreeEntry
->PreviousSize
&&
675 (DecommitBase
== (ULONG_PTR
)FreeEntry
))
677 PrecedingInUseEntry
= (PHEAP_ENTRY
)FreeEntry
- FreeEntry
->PreviousSize
;
680 /* Get the next entry */
681 NextFreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ (Size
>> HEAP_ENTRY_SHIFT
));
682 DecommitSize
= ROUND_DOWN(NextFreeEntry
, PAGE_SIZE
);
683 NextSize
= (PHEAP_ENTRY
)NextFreeEntry
- (PHEAP_ENTRY
)DecommitSize
;
687 /* Just 1 heap entry, increase the size */
688 DecommitSize
-= PAGE_SIZE
;
689 NextSize
+= PAGE_SIZE
>> HEAP_ENTRY_SHIFT
;
691 else if (NextSize
== 0 &&
692 !(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
694 NextInUseEntry
= (PHEAP_ENTRY
)NextFreeEntry
;
697 NextFreeEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)NextFreeEntry
- NextSize
);
699 if (DecommitSize
> DecommitBase
)
700 DecommitSize
-= DecommitBase
;
703 /* Nothing to decommit */
704 RtlpInsertFreeBlock(Heap
, FreeEntry
, PrecedingSize
);
708 /* A decommit is necessary. Create a UCR descriptor */
709 UcrDescriptor
= RtlpCreateUnCommittedRange(Segment
);
712 DPRINT1("HEAP: Failed to create UCR descriptor\n");
713 RtlpInsertFreeBlock(Heap
, FreeEntry
, PrecedingSize
);
717 /* Decommit the memory */
718 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
719 (PVOID
*)&DecommitBase
,
723 /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */
724 RtlpDestroyUnCommittedRange(Segment
, UcrDescriptor
);
726 if (!NT_SUCCESS(Status
))
728 RtlpInsertFreeBlock(Heap
, FreeEntry
, PrecedingSize
);
732 /* Insert uncommitted pages */
733 RtlpInsertUnCommittedPages(Segment
, DecommitBase
, DecommitSize
);
734 Segment
->NumberOfUnCommittedPages
+= (DecommitSize
/ PAGE_SIZE
);
738 /* Adjust size of this free entry and insert it */
739 FreeEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
740 FreeEntry
->Size
= PrecedingSize
;
741 Heap
->TotalFreeSize
+= PrecedingSize
;
742 Segment
->LastEntryInSegment
= (PHEAP_ENTRY
)FreeEntry
;
743 RtlpInsertFreeBlockHelper(Heap
, FreeEntry
, PrecedingSize
);
745 else if (NextInUseEntry
)
747 /* Adjust preceding in use entry */
748 PrecedingInUseEntry
->Flags
|= HEAP_ENTRY_LAST_ENTRY
;
749 Segment
->LastEntryInSegment
= PrecedingInUseEntry
;
751 else if ((Segment
->LastEntryInSegment
>= (PHEAP_ENTRY
)DecommitBase
))
753 /* Adjust last entry in the segment */
754 Segment
->LastEntryInSegment
= Segment
->FirstEntry
;
757 /* Now the next one */
760 /* Adjust size of this free entry and insert it */
761 NextFreeEntry
->Flags
= 0;
762 NextFreeEntry
->PreviousSize
= 0;
763 NextFreeEntry
->SegmentOffset
= Segment
->Entry
.SegmentOffset
;
764 NextFreeEntry
->Size
= NextSize
;
766 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)NextFreeEntry
+ NextSize
))->PreviousSize
= NextSize
;
768 Heap
->TotalFreeSize
+= PrecedingSize
;
769 RtlpInsertFreeBlockHelper(Heap
, NextFreeEntry
, NextSize
);
771 else if (NextInUseEntry
)
773 NextInUseEntry
->PreviousSize
= 0;
776 RtlpInsertFreeBlock(Heap
, FreeEntry
, Size
);
781 RtlpInitializeHeapSegment(PHEAP Heap
,
782 PHEAP_SEGMENT Segment
,
786 PVOID UncommittedBase
,
789 ULONG Pages
, CommitSize
;
790 PHEAP_ENTRY HeapEntry
;
791 USHORT PreviousSize
= 0, NewSize
;
794 Pages
= ((PCHAR
)LimitAddress
- (PCHAR
)BaseAddress
) / PAGE_SIZE
;
796 HeapEntry
= (PHEAP_ENTRY
)ROUND_UP(Segment
+ 1, HEAP_ENTRY_SIZE
);
798 DPRINT("RtlpInitializeHeapSegment(%p %p %x %x %p %p %p)\n", Heap
, Segment
, SegmentIndex
, Flags
, BaseAddress
, UncommittedBase
, LimitAddress
);
799 DPRINT("Pages %x, HeapEntry %p, sizeof(HEAP_SEGMENT) %x\n", Pages
, HeapEntry
, sizeof(HEAP_SEGMENT
));
801 /* Check if it's the first segment and remember its size */
802 if (Heap
== BaseAddress
)
803 PreviousSize
= Heap
->Entry
.Size
;
805 NewSize
= ((PCHAR
)HeapEntry
- (PCHAR
)Segment
) >> HEAP_ENTRY_SHIFT
;
807 if ((PVOID
)(HeapEntry
+ 1) >= UncommittedBase
)
809 /* Check if it goes beyond the limit */
810 if ((PVOID
)(HeapEntry
+ 1) >= LimitAddress
)
813 /* Need to commit memory */
814 CommitSize
= (PCHAR
)(HeapEntry
+ 1) - (PCHAR
)UncommittedBase
;
815 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
816 (PVOID
)&UncommittedBase
,
821 if (!NT_SUCCESS(Status
))
823 DPRINT1("Committing page failed with status 0x%08X\n", Status
);
827 DPRINT("Committed %d bytes at base %p\n", CommitSize
, UncommittedBase
);
829 /* Calcule the new uncommitted base */
830 UncommittedBase
= (PVOID
)((PCHAR
)UncommittedBase
+ CommitSize
);
833 /* Initialize the segment entry */
834 Segment
->Entry
.PreviousSize
= PreviousSize
;
835 Segment
->Entry
.Size
= NewSize
;
836 Segment
->Entry
.Flags
= HEAP_ENTRY_BUSY
;
837 Segment
->Entry
.SegmentOffset
= SegmentIndex
;
839 /* Initialize the segment itself */
840 Segment
->SegmentSignature
= HEAP_SEGMENT_SIGNATURE
;
841 Segment
->Heap
= Heap
;
842 Segment
->BaseAddress
= BaseAddress
;
843 Segment
->FirstEntry
= HeapEntry
;
844 Segment
->LastValidEntry
= (PHEAP_ENTRY
)((PCHAR
)BaseAddress
+ Pages
* PAGE_SIZE
);
845 Segment
->NumberOfPages
= Pages
;
846 Segment
->NumberOfUnCommittedPages
= ((PCHAR
)LimitAddress
- (PCHAR
)UncommittedBase
) / PAGE_SIZE
;
847 InitializeListHead(&Segment
->UCRSegmentList
);
849 /* Insert uncommitted pages into UCR (uncommitted ranges) list */
850 if (Segment
->NumberOfUnCommittedPages
)
852 RtlpInsertUnCommittedPages(Segment
, (ULONG_PTR
)UncommittedBase
, Segment
->NumberOfUnCommittedPages
* PAGE_SIZE
);
855 /* Set the segment index pointer */
856 Heap
->Segments
[SegmentIndex
] = Segment
;
858 /* Prepare a free heap entry */
859 HeapEntry
->Flags
= HEAP_ENTRY_LAST_ENTRY
;
860 HeapEntry
->PreviousSize
= Segment
->Entry
.Size
;
861 HeapEntry
->SegmentOffset
= SegmentIndex
;
863 /* Set last entry in segment */
864 Segment
->LastEntryInSegment
= HeapEntry
;
867 RtlpInsertFreeBlock(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, (PHEAP_ENTRY
)UncommittedBase
- HeapEntry
);
873 RtlpDestroyHeapSegment(PHEAP_SEGMENT Segment
)
879 /* Make sure it's not user allocated */
880 if (Segment
->SegmentFlags
& HEAP_USER_ALLOCATED
) return;
882 BaseAddress
= Segment
->BaseAddress
;
883 DPRINT("Destroying segment %p, BA %p\n", Segment
, BaseAddress
);
885 /* Release virtual memory */
886 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
891 if (!NT_SUCCESS(Status
))
893 DPRINT1("HEAP: Failed to release segment's memory with status 0x%08X\n", Status
);
899 RtlpAddHeapToProcessList(PHEAP Heap
)
904 Peb
= RtlGetCurrentPeb();
906 /* Acquire the lock */
907 RtlEnterHeapLock(&RtlpProcessHeapsListLock
);
910 /* Check if max number of heaps reached */
911 if (Peb
->NumberOfHeaps
== Peb
->MaximumNumberOfHeaps
)
913 // TODO: Handle this case
917 /* Add the heap to the process heaps */
918 Peb
->ProcessHeaps
[Peb
->NumberOfHeaps
] = Heap
;
919 Peb
->NumberOfHeaps
++;
920 Heap
->ProcessHeapsListIndex
= Peb
->NumberOfHeaps
;
923 /* Release the lock */
924 RtlLeaveHeapLock(&RtlpProcessHeapsListLock
);
931 RtlpRemoveHeapFromProcessList(PHEAP Heap
)
934 PHEAP
*Current
, *Next
;
938 Peb
= RtlGetCurrentPeb();
940 /* Acquire the lock */
941 RtlEnterHeapLock(&RtlpProcessHeapsListLock
);
943 /* Check if we don't need anything to do */
944 if ((Heap
->ProcessHeapsListIndex
== 0) ||
945 (Heap
->ProcessHeapsListIndex
> Peb
->NumberOfHeaps
) ||
946 (Peb
->NumberOfHeaps
== 0))
948 /* Release the lock */
949 RtlLeaveHeapLock(&RtlpProcessHeapsListLock
);
954 /* The process actually has more than one heap.
955 Use classic, lernt from university times algorithm for removing an entry
956 from a static array */
958 Current
= (PHEAP
*)&Peb
->ProcessHeaps
[Heap
->ProcessHeapsListIndex
- 1];
961 /* How many items we need to shift to the left */
962 Count
= Peb
->NumberOfHeaps
- (Heap
->ProcessHeapsListIndex
- 1);
964 /* Move them all in a loop */
967 /* Copy it and advance next pointer */
970 /* Update its index */
971 (*Current
)->ProcessHeapsListIndex
-= 1;
973 /* Advance pointers */
978 /* Decrease total number of heaps */
979 Peb
->NumberOfHeaps
--;
981 /* Zero last unused item */
982 Peb
->ProcessHeaps
[Peb
->NumberOfHeaps
] = NULL
;
983 Heap
->ProcessHeapsListIndex
= 0;
985 /* Release the lock */
986 RtlLeaveHeapLock(&RtlpProcessHeapsListLock
);
989 PHEAP_FREE_ENTRY NTAPI
990 RtlpCoalesceHeap(PHEAP Heap
)
996 PHEAP_FREE_ENTRY NTAPI
997 RtlpCoalesceFreeBlocks (PHEAP Heap
,
998 PHEAP_FREE_ENTRY FreeEntry
,
1002 PHEAP_FREE_ENTRY CurrentEntry
, NextEntry
;
1004 /* Get the previous entry */
1005 CurrentEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
- FreeEntry
->PreviousSize
);
1008 if (CurrentEntry
!= FreeEntry
&&
1009 !(CurrentEntry
->Flags
& HEAP_ENTRY_BUSY
) &&
1010 (*FreeSize
+ CurrentEntry
->Size
) <= HEAP_MAX_BLOCK_SIZE
)
1012 ASSERT(FreeEntry
->PreviousSize
== CurrentEntry
->Size
);
1014 /* Remove it if asked for */
1017 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
1018 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
1020 /* Remove it only once! */
1024 /* Remove previous entry too */
1025 RtlpRemoveFreeBlock(Heap
, CurrentEntry
, FALSE
, FALSE
);
1028 CurrentEntry
->Flags
= FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
;
1030 /* Update last entry in the segment */
1031 if (CurrentEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
)
1032 Heap
->Segments
[CurrentEntry
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)CurrentEntry
;
1034 /* Advance FreeEntry and update sizes */
1035 FreeEntry
= CurrentEntry
;
1036 *FreeSize
+= CurrentEntry
->Size
;
1037 Heap
->TotalFreeSize
-= CurrentEntry
->Size
;
1038 FreeEntry
->Size
= *FreeSize
;
1040 /* Also update previous size if needed */
1041 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1043 ((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
)->PreviousSize
= *FreeSize
;
1047 /* Check the next block if it exists */
1048 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1050 NextEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
);
1052 if (!(NextEntry
->Flags
& HEAP_ENTRY_BUSY
) &&
1053 NextEntry
->Size
+ *FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
1055 ASSERT(*FreeSize
== NextEntry
->PreviousSize
);
1057 /* Remove it if asked for */
1060 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
1061 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
1065 FreeEntry
->Flags
= NextEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
;
1067 /* Update last entry in the segment */
1068 if (FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
)
1069 Heap
->Segments
[FreeEntry
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)FreeEntry
;
1071 /* Remove next entry now */
1072 RtlpRemoveFreeBlock(Heap
, NextEntry
, FALSE
, FALSE
);
1075 *FreeSize
+= NextEntry
->Size
;
1076 Heap
->TotalFreeSize
-= NextEntry
->Size
;
1077 FreeEntry
->Size
= *FreeSize
;
1079 /* Also update previous size if needed */
1080 if (!(FreeEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1082 ((PHEAP_ENTRY
)FreeEntry
+ *FreeSize
)->PreviousSize
= *FreeSize
;
1089 PHEAP_FREE_ENTRY NTAPI
1090 RtlpExtendHeap(PHEAP Heap
,
1094 UCHAR Index
, EmptyIndex
;
1095 SIZE_T FreeSize
, CommitSize
, ReserveSize
;
1096 PHEAP_SEGMENT Segment
;
1097 PHEAP_FREE_ENTRY FreeEntry
;
1100 DPRINT("RtlpExtendHeap(%p %x)\n", Heap
, Size
);
1102 /* Calculate amount in pages */
1103 Pages
= (Size
+ PAGE_SIZE
- 1) / PAGE_SIZE
;
1104 FreeSize
= Pages
* PAGE_SIZE
;
1105 DPRINT("Pages %x, FreeSize %x. Going through segments...\n", Pages
, FreeSize
);
1107 /* Find an empty segment */
1108 EmptyIndex
= HEAP_SEGMENTS
;
1109 for (Index
= 0; Index
< HEAP_SEGMENTS
; Index
++)
1111 Segment
= Heap
->Segments
[Index
];
1113 if (Segment
) DPRINT("Segment[%d] %p with NOUCP %x\n", Index
, Segment
, Segment
->NumberOfUnCommittedPages
);
1115 /* Check if its size suits us */
1117 Pages
<= Segment
->NumberOfUnCommittedPages
)
1119 DPRINT("This segment is suitable\n");
1121 /* Commit needed amount */
1122 FreeEntry
= RtlpFindAndCommitPages(Heap
, Segment
, &FreeSize
, NULL
);
1124 /* Coalesce it with adjacent entries */
1127 FreeSize
= FreeSize
>> HEAP_ENTRY_SHIFT
;
1128 FreeEntry
= RtlpCoalesceFreeBlocks(Heap
, FreeEntry
, &FreeSize
, FALSE
);
1129 RtlpInsertFreeBlock(Heap
, FreeEntry
, FreeSize
);
1133 else if (!Segment
&&
1134 EmptyIndex
== HEAP_SEGMENTS
)
1136 /* Remember the first unused segment index */
1141 /* No luck, need to grow the heap */
1142 if ((Heap
->Flags
& HEAP_GROWABLE
) &&
1143 (EmptyIndex
!= HEAP_SEGMENTS
))
1147 /* Reserve the memory */
1148 if ((Size
+ PAGE_SIZE
) <= Heap
->SegmentReserve
)
1149 ReserveSize
= Heap
->SegmentReserve
;
1151 ReserveSize
= Size
+ PAGE_SIZE
;
1153 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1160 /* If it failed, retry again with a half division algorithm */
1161 while (!NT_SUCCESS(Status
) &&
1162 ReserveSize
!= Size
+ PAGE_SIZE
)
1166 if (ReserveSize
< (Size
+ PAGE_SIZE
))
1167 ReserveSize
= Size
+ PAGE_SIZE
;
1169 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1177 /* Proceed only if it's success */
1178 if (NT_SUCCESS(Status
))
1180 Heap
->SegmentReserve
+= ReserveSize
;
1182 /* Now commit the memory */
1183 if ((Size
+ PAGE_SIZE
) <= Heap
->SegmentCommit
)
1184 CommitSize
= Heap
->SegmentCommit
;
1186 CommitSize
= Size
+ PAGE_SIZE
;
1188 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1195 DPRINT("Committed %d bytes at base %p\n", CommitSize
, Segment
);
1197 /* Initialize heap segment if commit was successful */
1198 if (NT_SUCCESS(Status
))
1200 if (!RtlpInitializeHeapSegment(Heap
, Segment
, EmptyIndex
, 0, Segment
,
1201 (PCHAR
)Segment
+ CommitSize
, (PCHAR
)Segment
+ ReserveSize
))
1203 Status
= STATUS_NO_MEMORY
;
1207 /* If everything worked - cool */
1208 if (NT_SUCCESS(Status
)) return (PHEAP_FREE_ENTRY
)Segment
->FirstEntry
;
1210 DPRINT1("Committing failed with status 0x%08X\n", Status
);
1212 /* Nope, we failed. Free memory */
1213 ZwFreeVirtualMemory(NtCurrentProcess(),
1220 DPRINT1("Reserving failed with status 0x%08X\n", Status
);
1224 if (RtlpGetMode() == UserMode
)
1226 /* If coalescing on free is disabled in usermode, then do it here */
1227 if (Heap
->Flags
& HEAP_DISABLE_COALESCE_ON_FREE
)
1229 FreeEntry
= RtlpCoalesceHeap(Heap
);
1231 /* If it's a suitable one - return it */
1233 FreeEntry
->Size
>= Size
)
1243 /***********************************************************************
1246 * Handle of heap: Success
1252 RtlCreateHeap(ULONG Flags
,
1257 PRTL_HEAP_PARAMETERS Parameters
)
1259 PVOID CommittedAddress
= NULL
, UncommittedAddress
= NULL
;
1261 RTL_HEAP_PARAMETERS SafeParams
= {0};
1263 ULONG_PTR MaximumUserModeAddress
;
1264 SYSTEM_BASIC_INFORMATION SystemInformation
;
1265 MEMORY_BASIC_INFORMATION MemoryInfo
;
1266 ULONG NtGlobalFlags
= RtlGetNtGlobalFlags();
1267 ULONG HeapSegmentFlags
= 0;
1269 ULONG MaxBlockSize
, HeaderSize
;
1270 BOOLEAN AllocateLock
= FALSE
;
1272 /* Check for a special heap */
1273 if (RtlpPageHeapEnabled
&& !Addr
&& !Lock
)
1275 Heap
= RtlpPageHeapCreate(Flags
, Addr
, TotalSize
, CommitSize
, Lock
, Parameters
);
1276 if (Heap
) return Heap
;
1279 DPRINT1("Enabling page heap failed\n");
1282 /* Check validation flags */
1283 if (!(Flags
& HEAP_SKIP_VALIDATION_CHECKS
) && (Flags
& ~HEAP_CREATE_VALID_MASK
))
1285 DPRINT1("Invalid flags 0x%08x, fixing...\n", Flags
);
1286 Flags
&= HEAP_CREATE_VALID_MASK
;
1289 /* TODO: Capture parameters, once we decide to use SEH */
1290 if (!Parameters
) Parameters
= &SafeParams
;
1292 /* Check global flags */
1293 if (NtGlobalFlags
& FLG_HEAP_DISABLE_COALESCING
)
1294 Flags
|= HEAP_DISABLE_COALESCE_ON_FREE
;
1296 if (NtGlobalFlags
& FLG_HEAP_ENABLE_FREE_CHECK
)
1297 Flags
|= HEAP_FREE_CHECKING_ENABLED
;
1299 if (NtGlobalFlags
& FLG_HEAP_ENABLE_TAIL_CHECK
)
1300 Flags
|= HEAP_TAIL_CHECKING_ENABLED
;
1302 if (RtlpGetMode() == UserMode
)
1304 /* Also check these flags if in usermode */
1305 if (NtGlobalFlags
& FLG_HEAP_VALIDATE_ALL
)
1306 Flags
|= HEAP_VALIDATE_ALL_ENABLED
;
1308 if (NtGlobalFlags
& FLG_HEAP_VALIDATE_PARAMETERS
)
1309 Flags
|= HEAP_VALIDATE_PARAMETERS_ENABLED
;
1311 if (NtGlobalFlags
& FLG_USER_STACK_TRACE_DB
)
1312 Flags
|= HEAP_CAPTURE_STACK_BACKTRACES
;
1315 Peb
= RtlGetCurrentPeb();
1317 /* Apply defaults for non-set parameters */
1318 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= Peb
->HeapSegmentCommit
;
1319 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= Peb
->HeapSegmentReserve
;
1320 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= Peb
->HeapDeCommitFreeBlockThreshold
;
1321 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= Peb
->HeapDeCommitTotalFreeThreshold
;
1325 /* Apply defaults for non-set parameters */
1327 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= MmHeapSegmentCommit
;
1328 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= MmHeapSegmentReserve
;
1329 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= MmHeapDeCommitFreeBlockThreshold
;
1330 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= MmHeapDeCommitTotalFreeThreshold
;
1334 // FIXME: Move to memory manager
1335 if (!Parameters
->SegmentCommit
) Parameters
->SegmentCommit
= PAGE_SIZE
* 2;
1336 if (!Parameters
->SegmentReserve
) Parameters
->SegmentReserve
= 1048576;
1337 if (!Parameters
->DeCommitFreeBlockThreshold
) Parameters
->DeCommitFreeBlockThreshold
= PAGE_SIZE
;
1338 if (!Parameters
->DeCommitTotalFreeThreshold
) Parameters
->DeCommitTotalFreeThreshold
= 65536;
1340 /* Get the max um address */
1341 Status
= ZwQuerySystemInformation(SystemBasicInformation
,
1343 sizeof(SystemInformation
),
1346 if (!NT_SUCCESS(Status
))
1348 DPRINT1("Getting max usermode address failed with status 0x%08x\n", Status
);
1352 MaximumUserModeAddress
= SystemInformation
.MaximumUserModeAddress
;
1354 /* Calculate max alloc size */
1355 if (!Parameters
->MaximumAllocationSize
)
1356 Parameters
->MaximumAllocationSize
= MaximumUserModeAddress
- (ULONG_PTR
)0x10000 - PAGE_SIZE
;
1358 MaxBlockSize
= 0x80000 - PAGE_SIZE
;
1360 if (!Parameters
->VirtualMemoryThreshold
||
1361 Parameters
->VirtualMemoryThreshold
> MaxBlockSize
)
1363 Parameters
->VirtualMemoryThreshold
= MaxBlockSize
;
1366 /* Check reserve/commit sizes and set default values */
1369 CommitSize
= PAGE_SIZE
;
1371 TotalSize
= ROUND_UP(TotalSize
, PAGE_SIZE
);
1373 TotalSize
= 64 * PAGE_SIZE
;
1377 /* Round up the commit size to be at least the page size */
1378 CommitSize
= ROUND_UP(CommitSize
, PAGE_SIZE
);
1381 TotalSize
= ROUND_UP(TotalSize
, PAGE_SIZE
);
1383 TotalSize
= ROUND_UP(CommitSize
, 16 * PAGE_SIZE
);
1386 if (RtlpGetMode() == UserMode
)
1388 /* TODO: Here should be a call to special "Debug" heap, which does parameters validation,
1389 however we're just going to simulate setting correct flags here */
1390 if (Flags
& (HEAP_VALIDATE_ALL_ENABLED
|
1391 HEAP_VALIDATE_PARAMETERS_ENABLED
|
1392 HEAP_CAPTURE_STACK_BACKTRACES
|
1393 HEAP_FLAG_PAGE_ALLOCS
|
1394 HEAP_CREATE_ENABLE_TRACING
) &&
1395 !(Flags
& HEAP_SKIP_VALIDATION_CHECKS
))
1397 // RtlDebugCreateHeap(Flags, Addr, TotalSize, CommitSize, Lock, Parameters);
1398 Flags
|= HEAP_SKIP_VALIDATION_CHECKS
|
1399 HEAP_TAIL_CHECKING_ENABLED
|
1400 HEAP_FREE_CHECKING_ENABLED
;
1404 /* Calculate header size */
1405 HeaderSize
= sizeof(HEAP
);
1406 if (!(Flags
& HEAP_NO_SERIALIZE
))
1410 Flags
|= HEAP_LOCK_USER_ALLOCATED
;
1414 HeaderSize
+= sizeof(HEAP_LOCK
);
1415 AllocateLock
= TRUE
;
1420 /* Invalid parameters */
1424 /* See if we are already provided with an address for the heap */
1427 if (Parameters
->CommitRoutine
)
1429 /* There is a commit routine, so no problem here, check params */
1430 if ((Flags
& HEAP_GROWABLE
) ||
1431 !Parameters
->InitialCommit
||
1432 !Parameters
->InitialReserve
||
1433 (Parameters
->InitialCommit
> Parameters
->InitialReserve
))
1439 /* Calculate committed and uncommitted addresses */
1440 CommittedAddress
= Addr
;
1441 UncommittedAddress
= (PCHAR
)Addr
+ Parameters
->InitialCommit
;
1442 TotalSize
= Parameters
->InitialReserve
;
1444 /* Zero the initial page ourselves */
1445 RtlZeroMemory(CommittedAddress
, PAGE_SIZE
);
1449 /* Commit routine is absent, so query how much memory caller reserved */
1450 Status
= ZwQueryVirtualMemory(NtCurrentProcess(),
1452 MemoryBasicInformation
,
1457 if (!NT_SUCCESS(Status
))
1459 DPRINT1("Querying amount of user supplied memory failed with status 0x%08X\n", Status
);
1464 if (MemoryInfo
.BaseAddress
!= Addr
||
1465 MemoryInfo
.State
== MEM_FREE
)
1470 /* Validation checks passed, set committed/uncommitted addresses */
1471 CommittedAddress
= Addr
;
1473 /* Check if it's committed or not */
1474 if (MemoryInfo
.State
== MEM_COMMIT
)
1476 /* Zero it out because it's already committed */
1477 RtlZeroMemory(CommittedAddress
, PAGE_SIZE
);
1479 /* Calculate uncommitted address value */
1480 CommitSize
= MemoryInfo
.RegionSize
;
1481 TotalSize
= CommitSize
;
1482 UncommittedAddress
= (PCHAR
)Addr
+ CommitSize
;
1484 /* Check if uncommitted address is reserved */
1485 Status
= ZwQueryVirtualMemory(NtCurrentProcess(),
1487 MemoryBasicInformation
,
1492 if (NT_SUCCESS(Status
) &&
1493 MemoryInfo
.State
== MEM_RESERVE
)
1495 /* It is, so add it up to the reserve size */
1496 TotalSize
+= MemoryInfo
.RegionSize
;
1501 /* It's not committed, inform following code that a commit is necessary */
1502 CommitSize
= PAGE_SIZE
;
1503 UncommittedAddress
= Addr
;
1507 /* Mark this as a user-committed mem */
1508 HeapSegmentFlags
= HEAP_USER_ALLOCATED
;
1513 /* Check commit routine */
1514 if (Parameters
->CommitRoutine
) return NULL
;
1516 /* Reserve memory */
1517 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1524 if (!NT_SUCCESS(Status
))
1526 DPRINT1("Failed to reserve memory with status 0x%08x\n", Status
);
1530 /* Set base addresses */
1531 CommittedAddress
= Heap
;
1532 UncommittedAddress
= Heap
;
1535 /* Check if we need to commit something */
1536 if (CommittedAddress
== UncommittedAddress
)
1538 /* Commit the required size */
1539 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
1546 DPRINT("Committed %d bytes at base %p\n", CommitSize
, CommittedAddress
);
1548 if (!NT_SUCCESS(Status
))
1550 DPRINT1("Failure, Status 0x%08X\n", Status
);
1552 /* Release memory if it was reserved */
1553 if (!Addr
) ZwFreeVirtualMemory(NtCurrentProcess(),
1561 /* Calculate new uncommitted address */
1562 UncommittedAddress
= (PCHAR
)UncommittedAddress
+ CommitSize
;
1565 DPRINT("Created heap %p, CommitSize %x, ReserveSize %x\n", Heap
, CommitSize
, TotalSize
);
1567 /* Initialize the heap */
1568 RtlpInitializeHeap(Heap
, &HeaderSize
, Flags
, AllocateLock
, Lock
);
1570 /* Initialize heap's first segment */
1571 if (!RtlpInitializeHeapSegment(Heap
,
1572 (PHEAP_SEGMENT
)((PCHAR
)Heap
+ HeaderSize
),
1577 (PCHAR
)CommittedAddress
+ TotalSize
))
1579 DPRINT1("Failed to initialize heap segment\n");
1583 /* Set other data */
1584 Heap
->ProcessHeapsListIndex
= 0;
1585 Heap
->SegmentCommit
= Parameters
->SegmentCommit
;
1586 Heap
->SegmentReserve
= Parameters
->SegmentReserve
;
1587 Heap
->DeCommitFreeBlockThreshold
= Parameters
->DeCommitFreeBlockThreshold
>> HEAP_ENTRY_SHIFT
;
1588 Heap
->DeCommitTotalFreeThreshold
= Parameters
->DeCommitTotalFreeThreshold
>> HEAP_ENTRY_SHIFT
;
1589 Heap
->MaximumAllocationSize
= Parameters
->MaximumAllocationSize
;
1590 Heap
->VirtualMemoryThreshold
= ROUND_UP(Parameters
->VirtualMemoryThreshold
, HEAP_ENTRY_SIZE
) >> HEAP_ENTRY_SHIFT
;
1591 Heap
->CommitRoutine
= Parameters
->CommitRoutine
;
1594 if (Flags
& HEAP_CREATE_ALIGN_16
)
1596 Heap
->AlignMask
= (ULONG
)~15;
1597 Heap
->AlignRound
= 15 + sizeof(HEAP_ENTRY
);
1601 Heap
->AlignMask
= (ULONG
)~(HEAP_ENTRY_SIZE
- 1);
1602 Heap
->AlignRound
= HEAP_ENTRY_SIZE
- 1 + sizeof(HEAP_ENTRY
);
1605 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
1606 Heap
->AlignRound
+= HEAP_ENTRY_SIZE
;
1608 /* Add heap to process list in case of usermode heap */
1609 if (RtlpGetMode() == UserMode
)
1611 RtlpAddHeapToProcessList(Heap
);
1613 // FIXME: What about lookasides?
1616 DPRINT("Heap %p, flags 0x%08x\n", Heap
, Heap
->Flags
);
1620 /***********************************************************************
1629 * Success: A NULL HANDLE, if heap is NULL or it was destroyed
1630 * Failure: The Heap handle, if heap is the process heap.
1633 RtlDestroyHeap(HANDLE HeapPtr
) /* [in] Handle of heap */
1635 PHEAP Heap
= (PHEAP
)HeapPtr
;
1636 PLIST_ENTRY Current
;
1637 PHEAP_UCR_DESCRIPTOR UcrDescriptor
;
1638 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
1642 PHEAP_SEGMENT Segment
;
1644 if (!HeapPtr
) return NULL
;
1646 // TODO: Check for special heap
1648 /* Check for a process heap */
1649 if (RtlpGetMode() == UserMode
&&
1650 HeapPtr
== NtCurrentPeb()->ProcessHeap
) return HeapPtr
;
1652 /* Free up all big allocations */
1653 Current
= Heap
->VirtualAllocdBlocks
.Flink
;
1654 while (Current
!= &Heap
->VirtualAllocdBlocks
)
1656 VirtualEntry
= CONTAINING_RECORD(Current
, HEAP_VIRTUAL_ALLOC_ENTRY
, Entry
);
1657 BaseAddress
= (PVOID
)VirtualEntry
;
1658 Current
= Current
->Flink
;
1660 ZwFreeVirtualMemory(NtCurrentProcess(),
1666 /* Delete tags and remove heap from the process heaps list in user mode */
1667 if (RtlpGetMode() == UserMode
)
1669 // FIXME DestroyTags
1670 RtlpRemoveHeapFromProcessList(Heap
);
1673 /* Delete the heap lock */
1674 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
1676 /* Delete it if it wasn't user allocated */
1677 if (!(Heap
->Flags
& HEAP_LOCK_USER_ALLOCATED
))
1678 RtlDeleteHeapLock(Heap
->LockVariable
);
1680 /* Clear out the lock variable */
1681 Heap
->LockVariable
= NULL
;
1684 /* Go through heap's global uncommitted ranges list and free them */
1685 DPRINT1("HEAP: Freeing segment's UCRs is not yet implemented!\n");
1686 Current
= Heap
->UCRSegmentList
.Flink
;
1687 while(Current
!= &Heap
->UCRSegmentList
)
1689 UcrDescriptor
= CONTAINING_RECORD(Current
, HEAP_UCR_DESCRIPTOR
, ListEntry
);
1693 BaseAddress
= UcrDescriptor
->Address
;
1696 /* Release that memory */
1697 ZwFreeVirtualMemory(NtCurrentProcess(),
1703 /* Advance to the next descriptor */
1704 Current
= Current
->Flink
;
1707 /* Go through segments and destroy them */
1708 for (i
= HEAP_SEGMENTS
- 1; i
>= 0; i
--)
1710 Segment
= Heap
->Segments
[i
];
1711 if (Segment
) RtlpDestroyHeapSegment(Segment
);
1718 RtlpSplitEntry(PHEAP Heap
,
1719 PHEAP_FREE_ENTRY FreeBlock
,
1720 SIZE_T AllocationSize
,
1724 PHEAP_FREE_ENTRY SplitBlock
, SplitBlock2
;
1726 PHEAP_ENTRY InUseEntry
;
1729 /* Save flags, update total free size */
1730 FreeFlags
= FreeBlock
->Flags
;
1731 Heap
->TotalFreeSize
-= FreeBlock
->Size
;
1733 /* Make this block an in-use one */
1734 InUseEntry
= (PHEAP_ENTRY
)FreeBlock
;
1735 InUseEntry
->Flags
= HEAP_ENTRY_BUSY
;
1736 InUseEntry
->SmallTagIndex
= 0;
1738 /* Calculate the extra amount */
1739 FreeSize
= InUseEntry
->Size
- Index
;
1741 /* Update it's size fields (we don't need their data anymore) */
1742 InUseEntry
->Size
= Index
;
1743 InUseEntry
->UnusedBytes
= AllocationSize
- Size
;
1745 /* If there is something to split - do the split */
1748 /* Don't split if resulting entry can't contain any payload data
1749 (i.e. being just HEAP_ENTRY_SIZE) */
1752 /* Increase sizes of the in-use entry */
1754 InUseEntry
->UnusedBytes
+= sizeof(HEAP_ENTRY
);
1758 /* Calculate a pointer to the new entry */
1759 SplitBlock
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
1762 SplitBlock
->Flags
= FreeFlags
;
1763 SplitBlock
->SegmentOffset
= InUseEntry
->SegmentOffset
;
1764 SplitBlock
->Size
= FreeSize
;
1765 SplitBlock
->PreviousSize
= Index
;
1767 /* Check if it's the last entry */
1768 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
1770 /* Insert it to the free list if it's the last entry */
1771 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
1772 Heap
->TotalFreeSize
+= FreeSize
;
1776 /* Not so easy - need to update next's previous size too */
1777 SplitBlock2
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
);
1779 if (SplitBlock2
->Flags
& HEAP_ENTRY_BUSY
)
1781 SplitBlock2
->PreviousSize
= (USHORT
)FreeSize
;
1782 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
1783 Heap
->TotalFreeSize
+= FreeSize
;
1787 /* Even more complex - the next entry is free, so we can merge them into one! */
1788 SplitBlock
->Flags
= SplitBlock2
->Flags
;
1790 /* Remove that next entry */
1791 RtlpRemoveFreeBlock(Heap
, SplitBlock2
, FALSE
, FALSE
);
1794 FreeSize
+= SplitBlock2
->Size
;
1795 Heap
->TotalFreeSize
-= SplitBlock2
->Size
;
1797 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
1799 /* Insert it back */
1800 SplitBlock
->Size
= FreeSize
;
1802 /* Don't forget to update previous size of the next entry! */
1803 if (!(SplitBlock
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
1805 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= FreeSize
;
1808 /* Actually insert it */
1809 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, (USHORT
)FreeSize
, FALSE
);
1811 /* Update total size */
1812 Heap
->TotalFreeSize
+= FreeSize
;
1816 /* Resulting block is quite big */
1817 RtlpInsertFreeBlock(Heap
, SplitBlock
, FreeSize
);
1822 /* Reset flags of the free entry */
1825 /* Update last entry in segment */
1826 if (SplitBlock
->Flags
& HEAP_ENTRY_LAST_ENTRY
)
1828 Heap
->Segments
[SplitBlock
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)SplitBlock
;
1833 /* Set last entry flag */
1834 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
1835 InUseEntry
->Flags
|= HEAP_ENTRY_LAST_ENTRY
;
1841 RtlpAllocateNonDedicated(PHEAP Heap
,
1844 SIZE_T AllocationSize
,
1848 PLIST_ENTRY FreeListHead
, Next
;
1849 PHEAP_FREE_ENTRY FreeBlock
;
1850 PHEAP_ENTRY InUseEntry
;
1851 PHEAP_ENTRY_EXTRA Extra
;
1852 EXCEPTION_RECORD ExceptionRecord
;
1854 /* Go through the zero list to find a place where to insert the new entry */
1855 FreeListHead
= &Heap
->FreeLists
[0];
1857 /* Start from the largest block to reduce time */
1858 Next
= FreeListHead
->Blink
;
1859 if (FreeListHead
!= Next
)
1861 FreeBlock
= CONTAINING_RECORD(Next
, HEAP_FREE_ENTRY
, FreeList
);
1863 if (FreeBlock
->Size
>= Index
)
1865 /* Our request is smaller than the largest entry in the zero list */
1867 /* Go through the list to find insertion place */
1868 Next
= FreeListHead
->Flink
;
1869 while (FreeListHead
!= Next
)
1871 FreeBlock
= CONTAINING_RECORD(Next
, HEAP_FREE_ENTRY
, FreeList
);
1873 if (FreeBlock
->Size
>= Index
)
1875 /* Found minimally fitting entry. Proceed to either using it as it is
1876 or splitting it to two entries */
1877 RemoveEntryList(&FreeBlock
->FreeList
);
1880 InUseEntry
= RtlpSplitEntry(Heap
, FreeBlock
, AllocationSize
, Index
, Size
);
1882 /* Release the lock */
1883 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1885 /* Zero memory if that was requested */
1886 if (Flags
& HEAP_ZERO_MEMORY
)
1887 RtlZeroMemory(InUseEntry
+ 1, Size
);
1888 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
1890 /* Fill this block with a special pattern */
1891 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
1894 /* Fill tail of the block with a special pattern too if requested */
1895 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
1897 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
1898 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
1901 /* Prepare extra if it's present */
1902 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
1904 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
1905 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
1910 /* Return pointer to the */
1911 return InUseEntry
+ 1;
1914 /* Advance to the next entry */
1920 /* Extend the heap, 0 list didn't have anything suitable */
1921 FreeBlock
= RtlpExtendHeap(Heap
, AllocationSize
);
1923 /* Use the new biggest entry we've got */
1926 RemoveEntryList(&FreeBlock
->FreeList
);
1929 InUseEntry
= RtlpSplitEntry(Heap
, FreeBlock
, AllocationSize
, Index
, Size
);
1931 /* Release the lock */
1932 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1934 /* Zero memory if that was requested */
1935 if (Flags
& HEAP_ZERO_MEMORY
)
1936 RtlZeroMemory(InUseEntry
+ 1, Size
);
1937 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
1939 /* Fill this block with a special pattern */
1940 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
1943 /* Fill tail of the block with a special pattern too if requested */
1944 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
1946 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
1947 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
1950 /* Prepare extra if it's present */
1951 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
1953 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
1954 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
1959 /* Return pointer to the */
1960 return InUseEntry
+ 1;
1963 /* Really unfortunate, out of memory condition */
1964 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
1966 /* Generate an exception */
1967 if (Flags
& HEAP_GENERATE_EXCEPTIONS
)
1969 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
1970 ExceptionRecord
.ExceptionRecord
= NULL
;
1971 ExceptionRecord
.NumberParameters
= 1;
1972 ExceptionRecord
.ExceptionFlags
= 0;
1973 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
1975 RtlRaiseException(&ExceptionRecord
);
1978 /* Release the lock */
1979 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
1980 DPRINT1("HEAP: Allocation failed!\n");
1981 DPRINT1("Flags %x\n", Heap
->Flags
);
1985 /***********************************************************************
1986 * HeapAlloc (KERNEL32.334)
1988 * Pointer to allocated memory block
1990 * 0x7d030f60--invalid flags in RtlHeapAllocate
1994 RtlAllocateHeap(IN PVOID HeapPtr
,
1998 PHEAP Heap
= (PHEAP
)HeapPtr
;
1999 PULONG FreeListsInUse
;
2000 ULONG FreeListsInUseUlong
;
2001 SIZE_T AllocationSize
;
2003 PLIST_ENTRY FreeListHead
;
2004 PHEAP_ENTRY InUseEntry
;
2005 PHEAP_FREE_ENTRY FreeBlock
;
2006 ULONG InUseIndex
, i
;
2008 EXCEPTION_RECORD ExceptionRecord
;
2009 BOOLEAN HeapLocked
= FALSE
;
2010 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualBlock
= NULL
;
2011 PHEAP_ENTRY_EXTRA Extra
;
2015 Flags
|= Heap
->ForceFlags
;
2017 /* Check for the maximum size */
2018 if (Size
>= 0x80000000)
2020 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
2021 DPRINT1("HEAP: Allocation failed!\n");
2026 HEAP_VALIDATE_ALL_ENABLED
|
2027 HEAP_VALIDATE_PARAMETERS_ENABLED
|
2028 HEAP_FLAG_PAGE_ALLOCS
|
2029 HEAP_CREATE_ENABLE_TRACING
|
2030 HEAP_CREATE_ALIGN_16
))
2032 DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags
);
2035 //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size);
2037 /* Calculate allocation size and index */
2039 AllocationSize
= Size
;
2042 AllocationSize
= (AllocationSize
+ Heap
->AlignRound
) & Heap
->AlignMask
;
2043 Index
= AllocationSize
>> HEAP_ENTRY_SHIFT
;
2045 /* Acquire the lock if necessary */
2046 if (!(Flags
& HEAP_NO_SERIALIZE
))
2048 RtlEnterHeapLock(Heap
->LockVariable
);
2052 /* Depending on the size, the allocation is going to be done from dedicated,
2053 non-dedicated lists or a virtual block of memory */
2054 if (Index
< HEAP_FREELISTS
)
2056 FreeListHead
= &Heap
->FreeLists
[Index
];
2058 if (!IsListEmpty(FreeListHead
))
2060 /* There is a free entry in this list */
2061 FreeBlock
= CONTAINING_RECORD(FreeListHead
->Blink
,
2065 /* Save flags and remove the free entry */
2066 FreeFlags
= FreeBlock
->Flags
;
2067 RtlpRemoveFreeBlock(Heap
, FreeBlock
, TRUE
, FALSE
);
2069 /* Update the total free size of the heap */
2070 Heap
->TotalFreeSize
-= Index
;
2072 /* Initialize this block */
2073 InUseEntry
= (PHEAP_ENTRY
)FreeBlock
;
2074 InUseEntry
->Flags
= HEAP_ENTRY_BUSY
| (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
);
2075 InUseEntry
->UnusedBytes
= AllocationSize
- Size
;
2076 InUseEntry
->SmallTagIndex
= 0;
2080 /* Find smallest free block which this request could fit in */
2081 InUseIndex
= Index
>> 5;
2082 FreeListsInUse
= &Heap
->u
.FreeListsInUseUlong
[InUseIndex
];
2084 /* This bit magic disables all sizes which are less than the requested allocation size */
2085 FreeListsInUseUlong
= *FreeListsInUse
++ & ~((1 << ((ULONG
)Index
& 0x1f)) - 1);
2087 /* If size is definitily more than our lists - go directly to the non-dedicated one */
2089 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2091 /* Go through the list */
2092 for (i
= InUseIndex
; i
< 4; i
++)
2094 if (FreeListsInUseUlong
)
2096 FreeListHead
= &Heap
->FreeLists
[i
* 32];
2100 if (i
< 3) FreeListsInUseUlong
= *FreeListsInUse
++;
2103 /* Nothing found, search in the non-dedicated list */
2105 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2107 /* That list is found, now calculate exact block */
2108 FreeListHead
+= RtlpFindLeastSetBit(FreeListsInUseUlong
);
2110 /* Take this entry and remove it from the list of free blocks */
2111 FreeBlock
= CONTAINING_RECORD(FreeListHead
->Blink
,
2114 RtlpRemoveFreeBlock(Heap
, FreeBlock
, TRUE
, FALSE
);
2117 InUseEntry
= RtlpSplitEntry(Heap
, FreeBlock
, AllocationSize
, Index
, Size
);
2120 /* Release the lock */
2121 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2123 /* Zero memory if that was requested */
2124 if (Flags
& HEAP_ZERO_MEMORY
)
2125 RtlZeroMemory(InUseEntry
+ 1, Size
);
2126 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2128 /* Fill this block with a special pattern */
2129 RtlFillMemoryUlong(InUseEntry
+ 1, Size
& ~0x3, ARENA_INUSE_FILLER
);
2132 /* Fill tail of the block with a special pattern too if requested */
2133 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2135 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
, sizeof(HEAP_ENTRY
), HEAP_TAIL_FILL
);
2136 InUseEntry
->Flags
|= HEAP_ENTRY_FILL_PATTERN
;
2139 /* Prepare extra if it's present */
2140 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2142 Extra
= RtlpGetExtraStuffPointer(InUseEntry
);
2143 RtlZeroMemory(Extra
, sizeof(HEAP_ENTRY_EXTRA
));
2148 /* User data starts right after the entry's header */
2149 return InUseEntry
+ 1;
2151 else if (Index
<= Heap
->VirtualMemoryThreshold
)
2153 /* The block is too large for dedicated lists, but fine for a non-dedicated one */
2154 return RtlpAllocateNonDedicated(Heap
, Flags
, Size
, AllocationSize
, Index
, HeapLocked
);
2156 else if (Heap
->Flags
& HEAP_GROWABLE
)
2158 /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */
2159 AllocationSize
+= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY
) - sizeof(HEAP_ENTRY
);
2161 Status
= ZwAllocateVirtualMemory(NtCurrentProcess(),
2162 (PVOID
*)&VirtualBlock
,
2168 if (!NT_SUCCESS(Status
))
2171 /* Release the lock */
2172 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2173 DPRINT1("HEAP: Allocation failed!\n");
2177 /* Initialize the newly allocated block */
2178 VirtualBlock
->BusyBlock
.Size
= (AllocationSize
- Size
);
2179 VirtualBlock
->BusyBlock
.Flags
= HEAP_ENTRY_VIRTUAL_ALLOC
| HEAP_ENTRY_EXTRA_PRESENT
| HEAP_ENTRY_BUSY
;
2180 VirtualBlock
->CommitSize
= AllocationSize
;
2181 VirtualBlock
->ReserveSize
= AllocationSize
;
2183 /* Insert it into the list of virtual allocations */
2184 InsertTailList(&Heap
->VirtualAllocdBlocks
, &VirtualBlock
->Entry
);
2186 /* Release the lock */
2187 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2189 /* Return pointer to user data */
2190 return VirtualBlock
+ 1;
2193 /* Generate an exception */
2194 if (Flags
& HEAP_GENERATE_EXCEPTIONS
)
2196 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
2197 ExceptionRecord
.ExceptionRecord
= NULL
;
2198 ExceptionRecord
.NumberParameters
= 1;
2199 ExceptionRecord
.ExceptionFlags
= 0;
2200 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
2202 RtlRaiseException(&ExceptionRecord
);
2205 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL
);
2207 /* Release the lock */
2208 if (HeapLocked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2209 DPRINT1("HEAP: Allocation failed!\n");
2214 /***********************************************************************
2215 * HeapFree (KERNEL32.338)
2222 BOOLEAN NTAPI
RtlFreeHeap(
2223 HANDLE HeapPtr
, /* [in] Handle of heap */
2224 ULONG Flags
, /* [in] Heap freeing flags */
2225 PVOID Ptr
/* [in] Address of memory to free */
2229 PHEAP_ENTRY HeapEntry
;
2230 USHORT TagIndex
= 0;
2232 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
2233 BOOLEAN Locked
= FALSE
;
2236 /* Freeing NULL pointer is a legal operation */
2237 if (!Ptr
) return TRUE
;
2239 /* Get pointer to the heap and force flags */
2240 Heap
= (PHEAP
)HeapPtr
;
2241 Flags
|= Heap
->ForceFlags
;
2243 /* Lock if necessary */
2244 if (!(Flags
& HEAP_NO_SERIALIZE
))
2246 RtlEnterHeapLock(Heap
->LockVariable
);
2250 /* Get pointer to the heap entry */
2251 HeapEntry
= (PHEAP_ENTRY
)Ptr
- 1;
2253 /* Check this entry, fail if it's invalid */
2254 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
) ||
2255 (((ULONG_PTR
)Ptr
& 0x7) != 0) ||
2256 (HeapEntry
->SegmentOffset
>= HEAP_SEGMENTS
))
2258 /* This is an invalid block */
2259 DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr
);
2260 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
2262 /* Release the heap lock */
2263 if (Locked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2267 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2269 /* Big allocation */
2270 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2272 /* Remove it from the list */
2273 RemoveEntryList(&VirtualEntry
->Entry
);
2278 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
2279 (PVOID
*)&VirtualEntry
,
2283 if (!NT_SUCCESS(Status
))
2285 DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n",
2286 Status
, Heap
, Ptr
, VirtualEntry
);
2287 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status
);
2292 /* Normal allocation */
2293 BlockSize
= HeapEntry
->Size
;
2297 /* Coalesce in kernel mode, and in usermode if it's not disabled */
2298 if (RtlpGetMode() == KernelMode
||
2299 (RtlpGetMode() == UserMode
&& !(Heap
->Flags
& HEAP_DISABLE_COALESCE_ON_FREE
)))
2301 HeapEntry
= (PHEAP_ENTRY
)RtlpCoalesceFreeBlocks(Heap
,
2302 (PHEAP_FREE_ENTRY
)HeapEntry
,
2307 /* If there is no need to decommit the block - put it into a free list */
2308 if (BlockSize
< Heap
->DeCommitFreeBlockThreshold
||
2309 (Heap
->TotalFreeSize
+ BlockSize
< Heap
->DeCommitTotalFreeThreshold
))
2311 /* Check if it needs to go to a 0 list */
2312 if (BlockSize
> HEAP_MAX_BLOCK_SIZE
)
2314 /* General-purpose 0 list */
2315 RtlpInsertFreeBlock(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
);
2319 /* Usual free list */
2320 RtlpInsertFreeBlockHelper(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
, FALSE
);
2322 /* Assert sizes are consistent */
2323 if (!(HeapEntry
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
2325 ASSERT((HeapEntry
+ BlockSize
)->PreviousSize
== BlockSize
);
2328 /* Increase the free size */
2329 Heap
->TotalFreeSize
+= BlockSize
;
2333 if (RtlpGetMode() == UserMode
&&
2342 /* Decommit this block */
2343 RtlpDeCommitFreeBlock(Heap
, (PHEAP_FREE_ENTRY
)HeapEntry
, BlockSize
);
2347 /* Release the heap lock */
2348 if (Locked
) RtlLeaveHeapLock(Heap
->LockVariable
);
2354 RtlpGrowBlockInPlace (IN PHEAP Heap
,
2356 IN PHEAP_ENTRY InUseEntry
,
2360 UCHAR EntryFlags
, RememberFlags
;
2361 PHEAP_FREE_ENTRY FreeEntry
, UnusedEntry
, FollowingEntry
;
2362 SIZE_T FreeSize
, PrevSize
, TailPart
, AddedSize
= 0;
2363 PHEAP_ENTRY_EXTRA OldExtra
, NewExtra
;
2365 /* We can't grow beyond specified threshold */
2366 if (Index
> Heap
->VirtualMemoryThreshold
)
2369 /* Get entry flags */
2370 EntryFlags
= InUseEntry
->Flags
;
2372 /* Get the next free entry */
2373 FreeEntry
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ InUseEntry
->Size
);
2375 if (EntryFlags
& HEAP_ENTRY_LAST_ENTRY
)
2377 /* There is no next block, just uncommitted space. Calculate how much is needed */
2378 FreeSize
= (Index
- InUseEntry
->Size
) << HEAP_ENTRY_SHIFT
;
2379 FreeSize
= ROUND_UP(FreeSize
, PAGE_SIZE
);
2381 /* Find and commit those pages */
2382 FreeEntry
= RtlpFindAndCommitPages(Heap
,
2383 Heap
->Segments
[InUseEntry
->SegmentOffset
],
2387 /* Fail if it failed... */
2388 if (!FreeEntry
) return FALSE
;
2390 /* It was successful, perform coalescing */
2391 FreeSize
= FreeSize
>> HEAP_ENTRY_SHIFT
;
2392 FreeEntry
= RtlpCoalesceFreeBlocks(Heap
, FreeEntry
, &FreeSize
, FALSE
);
2394 /* Check if it's enough */
2395 if (FreeSize
+ InUseEntry
->Size
< Index
)
2397 /* Still not enough */
2398 RtlpInsertFreeBlock(Heap
, FreeEntry
, FreeSize
);
2399 Heap
->TotalFreeSize
+= FreeSize
;
2403 /* Remember flags of this free entry */
2404 RememberFlags
= FreeEntry
->Flags
;
2407 FreeSize
+= InUseEntry
->Size
;
2411 /* The next block indeed exists. Check if it's free or in use */
2412 if (FreeEntry
->Flags
& HEAP_ENTRY_BUSY
) return FALSE
;
2414 /* Next entry is free, check if it can fit the block we need */
2415 FreeSize
= InUseEntry
->Size
+ FreeEntry
->Size
;
2416 if (FreeSize
< Index
) return FALSE
;
2418 /* Remember flags of this free entry */
2419 RememberFlags
= FreeEntry
->Flags
;
2421 /* Remove this block from the free list */
2422 RtlpRemoveFreeBlock(Heap
, FreeEntry
, FALSE
, FALSE
);
2423 Heap
->TotalFreeSize
-= FreeEntry
->Size
;
2426 PrevSize
= (InUseEntry
->Size
<< HEAP_ENTRY_SHIFT
) - InUseEntry
->UnusedBytes
;
2429 /* Don't produce too small blocks */
2436 /* Process extra stuff */
2437 if (RememberFlags
& HEAP_ENTRY_EXTRA_PRESENT
)
2439 /* Calculate pointers */
2440 OldExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ InUseEntry
->Size
- 1);
2441 NewExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ Index
- 1);
2444 *NewExtra
= *OldExtra
;
2450 InUseEntry
->Size
= Index
;
2451 InUseEntry
->UnusedBytes
= ((Index
<< HEAP_ENTRY_SHIFT
) - Size
);
2453 /* Check if there is a free space remaining after merging those blocks */
2456 /* Update flags and sizes */
2457 InUseEntry
->Flags
|= RememberFlags
& HEAP_ENTRY_LAST_ENTRY
;
2459 /* Either update previous size of the next entry or mark it as a last
2460 entry in the segment*/
2461 if (RememberFlags
& HEAP_ENTRY_LAST_ENTRY
)
2462 Heap
->Segments
[InUseEntry
->SegmentOffset
]->LastEntryInSegment
= InUseEntry
;
2464 (InUseEntry
+ InUseEntry
->Size
)->PreviousSize
= InUseEntry
->Size
;
2468 /* Complex case, we need to split the block to give unused free space
2470 UnusedEntry
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
2471 UnusedEntry
->PreviousSize
= Index
;
2472 UnusedEntry
->SegmentOffset
= InUseEntry
->SegmentOffset
;
2474 /* Update the following block or set the last entry in the segment */
2475 if (RememberFlags
& HEAP_ENTRY_LAST_ENTRY
)
2477 /* Set last entry and set flags and size */
2478 Heap
->Segments
[InUseEntry
->SegmentOffset
]->LastEntryInSegment
= InUseEntry
;
2479 UnusedEntry
->Flags
= RememberFlags
;
2480 UnusedEntry
->Size
= FreeSize
;
2482 /* Insert it to the heap and update total size */
2483 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2484 Heap
->TotalFreeSize
+= FreeSize
;
2488 /* There is a block after this one */
2489 FollowingEntry
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)UnusedEntry
+ FreeSize
);
2491 if (FollowingEntry
->Flags
& HEAP_ENTRY_BUSY
)
2493 /* Update flags and set size of the unused space entry */
2494 UnusedEntry
->Flags
= RememberFlags
& (~HEAP_ENTRY_LAST_ENTRY
);
2495 UnusedEntry
->Size
= FreeSize
;
2497 /* Update previous size of the following entry */
2498 FollowingEntry
->PreviousSize
= FreeSize
;
2500 /* Insert it to the heap and update total free size */
2501 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2502 Heap
->TotalFreeSize
+= FreeSize
;
2506 /* That following entry is also free, what a fortune! */
2507 RememberFlags
= FollowingEntry
->Flags
;
2510 RtlpRemoveFreeBlock(Heap
, FollowingEntry
, FALSE
, FALSE
);
2511 Heap
->TotalFreeSize
-= FollowingEntry
->Size
;
2513 /* And make up a new combined block */
2514 FreeSize
+= FollowingEntry
->Size
;
2515 UnusedEntry
->Flags
= RememberFlags
;
2517 /* Check where to put it */
2518 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
2520 /* Fine for a dedicated list */
2521 UnusedEntry
->Size
= FreeSize
;
2523 if (RememberFlags
& HEAP_ENTRY_LAST_ENTRY
)
2524 Heap
->Segments
[UnusedEntry
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)UnusedEntry
;
2526 ((PHEAP_ENTRY
)UnusedEntry
+ FreeSize
)->PreviousSize
= FreeSize
;
2528 /* Insert it back and update total size */
2529 RtlpInsertFreeBlockHelper(Heap
, UnusedEntry
, FreeSize
, FALSE
);
2530 Heap
->TotalFreeSize
+= FreeSize
;
2534 /* The block is very large, leave all the hassle to the insertion routine */
2535 RtlpInsertFreeBlock(Heap
, UnusedEntry
, FreeSize
);
2541 /* Copy user settable flags */
2542 InUseEntry
->Flags
&= ~HEAP_ENTRY_SETTABLE_FLAGS
;
2543 InUseEntry
->Flags
|= ((Flags
& HEAP_SETTABLE_USER_FLAGS
) >> 4);
2545 /* Properly "zero out" (and fill!) the space */
2546 if (Flags
& HEAP_ZERO_MEMORY
)
2548 RtlZeroMemory((PCHAR
)(InUseEntry
+ 1) + PrevSize
, Size
- PrevSize
);
2550 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2552 /* Calculate tail part which we need to fill */
2553 TailPart
= PrevSize
& (sizeof(ULONG
) - 1);
2555 /* "Invert" it as usual */
2556 if (TailPart
) TailPart
= 4 - TailPart
;
2558 if (Size
> (PrevSize
+ TailPart
))
2559 AddedSize
= (Size
- (PrevSize
+ TailPart
)) & ~(sizeof(ULONG
) - 1);
2563 RtlFillMemoryUlong((PCHAR
)(InUseEntry
+ 1) + PrevSize
+ TailPart
,
2565 ARENA_INUSE_FILLER
);
2569 /* Fill the new tail */
2570 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2572 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
,
2577 /* Return success */
2581 PHEAP_ENTRY_EXTRA NTAPI
2582 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry
)
2584 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry
;
2586 /* Check if it's a big block */
2587 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2589 VirtualEntry
= CONTAINING_RECORD(HeapEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2591 /* Return a pointer to the extra stuff*/
2592 return &VirtualEntry
->ExtraStuff
;
2596 /* This is a usual entry, which means extra stuff follows this block */
2597 return (PHEAP_ENTRY_EXTRA
)(HeapEntry
+ HeapEntry
->Size
- 1);
2602 /***********************************************************************
2605 * Heap [in] Handle of heap block
2606 * Flags [in] Heap reallocation flags
2607 * Ptr, [in] Address of memory to reallocate
2608 * Size [in] Number of bytes to reallocate
2611 * Pointer to reallocated memory block
2613 * 0x7d030f60--invalid flags in RtlHeapAllocate
2617 RtlReAllocateHeap(HANDLE HeapPtr
,
2622 PHEAP Heap
= (PHEAP
)HeapPtr
;
2623 PHEAP_ENTRY InUseEntry
, NewInUseEntry
;
2624 PHEAP_ENTRY_EXTRA OldExtra
, NewExtra
;
2625 SIZE_T AllocationSize
, FreeSize
, DecommitSize
;
2626 BOOLEAN HeapLocked
= FALSE
;
2627 PVOID NewBaseAddress
;
2628 PHEAP_FREE_ENTRY SplitBlock
, SplitBlock2
;
2629 SIZE_T OldSize
, Index
, OldIndex
;
2633 SIZE_T RemainderBytes
, ExtraSize
;
2634 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock
;
2635 EXCEPTION_RECORD ExceptionRecord
;
2637 /* Return success in case of a null pointer */
2640 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS
);
2644 /* Force heap flags */
2645 Flags
|= Heap
->ForceFlags
;
2647 // Check for special heap
2649 /* Make sure size is valid */
2650 if (Size
>= 0x80000000)
2652 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY
);
2656 /* Calculate allocation size and index */
2658 AllocationSize
= Size
;
2661 AllocationSize
= (AllocationSize
+ Heap
->AlignRound
) & Heap
->AlignMask
;
2663 /* Add up extra stuff, if it is present anywhere */
2664 if (((((PHEAP_ENTRY
)Ptr
)-1)->Flags
& HEAP_ENTRY_EXTRA_PRESENT
) ||
2665 (Flags
& HEAP_EXTRA_FLAGS_MASK
) ||
2666 Heap
->PseudoTagEntries
)
2668 AllocationSize
+= sizeof(HEAP_ENTRY_EXTRA
);
2671 /* Acquire the lock if necessary */
2672 if (!(Flags
& HEAP_NO_SERIALIZE
))
2674 RtlEnterHeapLock(Heap
->LockVariable
);
2676 Flags
^= HEAP_NO_SERIALIZE
;
2679 /* Get the pointer to the in-use entry */
2680 InUseEntry
= (PHEAP_ENTRY
)Ptr
- 1;
2682 /* If that entry is not really in-use, we have a problem */
2683 if (!(InUseEntry
->Flags
& HEAP_ENTRY_BUSY
))
2685 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
2687 /* Release the lock and return */
2689 RtlLeaveHeapLock(Heap
->LockVariable
);
2693 if (InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2695 /* This is a virtually allocated block. Get its size */
2696 OldSize
= RtlpGetSizeOfBigBlock(InUseEntry
);
2698 /* Convert it to an index */
2699 OldIndex
= (OldSize
+ InUseEntry
->Size
) >> HEAP_ENTRY_SHIFT
;
2701 /* Calculate new allocation size and round it to the page size */
2702 AllocationSize
+= FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2703 AllocationSize
= ROUND_UP(AllocationSize
, PAGE_SIZE
);
2708 OldIndex
= InUseEntry
->Size
;
2710 OldSize
= (OldIndex
<< HEAP_ENTRY_SHIFT
) - InUseEntry
->UnusedBytes
;
2713 /* Calculate new index */
2714 Index
= AllocationSize
>> HEAP_ENTRY_SHIFT
;
2716 /* Check for 4 different scenarios (old size, new size, old index, new index) */
2717 if (Index
<= OldIndex
)
2719 /* Difference must be greater than 1, adjust if it's not so */
2720 if (Index
+ 1 == OldIndex
)
2723 AllocationSize
+= sizeof(HEAP_ENTRY
);
2726 /* Calculate new size */
2727 if (InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2729 /* Simple in case of a virtual alloc - just an unused size */
2730 InUseEntry
->Size
= AllocationSize
- Size
;
2732 else if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2734 /* There is extra stuff, take it into account */
2735 OldExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ InUseEntry
->Size
- 1);
2736 NewExtra
= (PHEAP_ENTRY_EXTRA
)(InUseEntry
+ Index
- 1);
2737 *NewExtra
= *OldExtra
;
2739 // FIXME Tagging, TagIndex
2741 /* Update unused bytes count */
2742 InUseEntry
->UnusedBytes
= AllocationSize
- Size
;
2746 // FIXME Tagging, SmallTagIndex
2747 InUseEntry
->UnusedBytes
= AllocationSize
- Size
;
2750 /* If new size is bigger than the old size */
2753 /* Zero out that additional space if required */
2754 if (Flags
& HEAP_ZERO_MEMORY
)
2756 RtlZeroMemory((PCHAR
)Ptr
+ OldSize
, Size
- OldSize
);
2758 else if (Heap
->Flags
& HEAP_FREE_CHECKING_ENABLED
)
2760 /* Fill it on free if required */
2761 RemainderBytes
= OldSize
& (sizeof(ULONG
) - 1);
2764 RemainderBytes
= 4 - RemainderBytes
;
2766 if (Size
> (OldSize
+ RemainderBytes
))
2768 /* Calculate actual amount of extra bytes to fill */
2769 ExtraSize
= (Size
- (OldSize
+ RemainderBytes
)) & ~(sizeof(ULONG
) - 1);
2771 /* Fill them if there are any */
2774 RtlFillMemoryUlong((PCHAR
)(InUseEntry
+ 1) + OldSize
+ RemainderBytes
,
2776 ARENA_INUSE_FILLER
);
2782 /* Fill tail of the heap entry if required */
2783 if (Heap
->Flags
& HEAP_TAIL_CHECKING_ENABLED
)
2785 RtlFillMemory((PCHAR
)(InUseEntry
+ 1) + Size
,
2790 /* Check if the difference is significant or not */
2791 if (Index
!= OldIndex
)
2794 FreeFlags
= InUseEntry
->Flags
& ~HEAP_ENTRY_BUSY
;
2796 if (FreeFlags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
2798 /* This is a virtual block allocation */
2799 VirtualAllocBlock
= CONTAINING_RECORD(InUseEntry
, HEAP_VIRTUAL_ALLOC_ENTRY
, BusyBlock
);
2803 DecommitBase
= (PCHAR
)VirtualAllocBlock
+ AllocationSize
;
2804 DecommitSize
= (OldIndex
<< HEAP_ENTRY_SHIFT
) - AllocationSize
;
2806 /* Release the memory */
2807 Status
= ZwFreeVirtualMemory(NtCurrentProcess(),
2808 (PVOID
*)&DecommitBase
,
2812 if (!NT_SUCCESS(Status
))
2814 DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase
, DecommitSize
, Status
);
2818 /* Otherwise reduce the commit size */
2819 VirtualAllocBlock
->CommitSize
-= DecommitSize
;
2824 /* Reduce size of the block and possibly split it */
2825 SplitBlock
= (PHEAP_FREE_ENTRY
)(InUseEntry
+ Index
);
2827 /* Initialize this entry */
2828 SplitBlock
->Flags
= FreeFlags
;
2829 SplitBlock
->PreviousSize
= Index
;
2830 SplitBlock
->SegmentOffset
= InUseEntry
->SegmentOffset
;
2832 /* Remember free size */
2833 FreeSize
= InUseEntry
->Size
- Index
;
2836 InUseEntry
->Size
= Index
;
2837 InUseEntry
->Flags
&= ~HEAP_ENTRY_LAST_ENTRY
;
2839 /* Is that the last entry */
2840 if (FreeFlags
& HEAP_ENTRY_LAST_ENTRY
)
2842 /* Update segment's last entry */
2843 Heap
->Segments
[SplitBlock
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)SplitBlock
;
2845 /* Set its size and insert it to the list */
2846 SplitBlock
->Size
= (USHORT
)FreeSize
;
2847 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2849 /* Update total free size */
2850 Heap
->TotalFreeSize
+= FreeSize
;
2854 /* Get the block after that one */
2855 SplitBlock2
= (PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
);
2857 if (SplitBlock2
->Flags
& HEAP_ENTRY_BUSY
)
2859 /* It's in use, add it here*/
2860 SplitBlock
->Size
= (USHORT
)FreeSize
;
2862 /* Update previous size of the next entry */
2863 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= (USHORT
)FreeSize
;
2865 /* Insert it to the list */
2866 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2868 /* Update total size */
2869 Heap
->TotalFreeSize
+= FreeSize
;
2873 /* Next entry is free, so merge with it */
2874 SplitBlock
->Flags
= SplitBlock2
->Flags
;
2876 /* Remove it, update total size */
2877 RtlpRemoveFreeBlock(Heap
, SplitBlock2
, FALSE
, FALSE
);
2878 Heap
->TotalFreeSize
-= SplitBlock2
->Size
;
2880 /* Calculate total free size */
2881 FreeSize
+= SplitBlock2
->Size
;
2883 if (FreeSize
<= HEAP_MAX_BLOCK_SIZE
)
2885 SplitBlock
->Size
= FreeSize
;
2887 if (!(SplitBlock
->Flags
& HEAP_ENTRY_LAST_ENTRY
))
2889 /* Update previous size of the next entry */
2890 ((PHEAP_FREE_ENTRY
)((PHEAP_ENTRY
)SplitBlock
+ FreeSize
))->PreviousSize
= FreeSize
;
2894 Heap
->Segments
[SplitBlock
->SegmentOffset
]->LastEntryInSegment
= (PHEAP_ENTRY
)SplitBlock
;
2897 /* Insert the new one back and update total size */
2898 RtlpInsertFreeBlockHelper(Heap
, SplitBlock
, FreeSize
, FALSE
);
2899 Heap
->TotalFreeSize
+= FreeSize
;
2904 RtlpInsertFreeBlock(Heap
, SplitBlock
, FreeSize
);
2913 /* We're growing the block */
2914 if ((InUseEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
) ||
2915 !RtlpGrowBlockInPlace(Heap
, Flags
, InUseEntry
, Size
, Index
))
2917 /* Growing in place failed, so growing out of place */
2918 if (Flags
& HEAP_REALLOC_IN_PLACE_ONLY
)
2920 DPRINT1("Realloc in place failed, but it was the only option\n");
2925 /* Clear tag bits */
2926 Flags
&= ~HEAP_TAG_MASK
;
2928 /* Process extra stuff */
2929 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2931 /* Preserve user settable flags */
2932 Flags
&= ~HEAP_SETTABLE_USER_FLAGS
;
2934 Flags
|= HEAP_SETTABLE_USER_VALUE
| ((InUseEntry
->Flags
& HEAP_ENTRY_SETTABLE_FLAGS
) << 4);
2936 /* Get pointer to the old extra data */
2937 OldExtra
= RtlpGetExtraStuffPointer(InUseEntry
);
2939 /* Save tag index if it was set */
2940 if (OldExtra
->TagIndex
&&
2941 !(OldExtra
->TagIndex
& HEAP_PSEUDO_TAG_FLAG
))
2943 Flags
|= OldExtra
->TagIndex
<< HEAP_TAG_SHIFT
;
2946 else if (InUseEntry
->SmallTagIndex
)
2948 /* Take small tag index into account */
2949 Flags
|= InUseEntry
->SmallTagIndex
<< HEAP_TAG_SHIFT
;
2952 /* Allocate new block from the heap */
2953 NewBaseAddress
= RtlAllocateHeap(HeapPtr
,
2954 Flags
& ~HEAP_ZERO_MEMORY
,
2957 /* Proceed if it didn't fail */
2960 /* Get new entry pointer */
2961 NewInUseEntry
= (PHEAP_ENTRY
)NewBaseAddress
- 1;
2963 /* Process extra stuff if it exists */
2964 if (NewInUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2966 NewExtra
= RtlpGetExtraStuffPointer(NewInUseEntry
);
2968 if (InUseEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
2970 OldExtra
= RtlpGetExtraStuffPointer(InUseEntry
);
2971 NewExtra
->Settable
= OldExtra
->Settable
;
2975 RtlZeroMemory(NewExtra
, sizeof(*NewExtra
));
2979 /* Copy actual user bits */
2981 RtlMoveMemory(NewBaseAddress
, Ptr
, Size
);
2983 RtlMoveMemory(NewBaseAddress
, Ptr
, OldSize
);
2985 /* Zero remaining part if required */
2986 if (Size
> OldSize
&&
2987 (Flags
& HEAP_ZERO_MEMORY
))
2989 RtlZeroMemory((PCHAR
)NewBaseAddress
+ OldSize
, Size
- OldSize
);
2992 /* Free the old block */
2993 RtlFreeHeap(HeapPtr
, Flags
, Ptr
);
2996 Ptr
= NewBaseAddress
;
3001 /* Did resizing fail? */
3002 if (!Ptr
&& (Flags
& HEAP_GENERATE_EXCEPTIONS
))
3004 /* Generate an exception if required */
3005 ExceptionRecord
.ExceptionCode
= STATUS_NO_MEMORY
;
3006 ExceptionRecord
.ExceptionRecord
= NULL
;
3007 ExceptionRecord
.NumberParameters
= 1;
3008 ExceptionRecord
.ExceptionFlags
= 0;
3009 ExceptionRecord
.ExceptionInformation
[0] = AllocationSize
;
3011 RtlRaiseException(&ExceptionRecord
);
3014 /* Release the heap lock if it was acquired */
3016 RtlLeaveHeapLock(Heap
->LockVariable
);
3022 /***********************************************************************
3028 RtlCompactHeap(HANDLE Heap
,
3036 /***********************************************************************
3038 * Attempts to acquire the critical section object for a specified heap.
3041 * Heap [in] Handle of heap to lock for exclusive access
3050 RtlLockHeap(IN HANDLE HeapPtr
)
3052 PHEAP Heap
= (PHEAP
)HeapPtr
;
3054 // FIXME Check for special heap
3056 /* Check if it's really a heap */
3057 if (Heap
->Signature
!= HEAP_SIGNATURE
) return FALSE
;
3059 /* Lock if it's lockable */
3060 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3062 RtlEnterHeapLock(Heap
->LockVariable
);
3069 /***********************************************************************
3071 * Releases ownership of the critical section object.
3074 * Heap [in] Handle to the heap to unlock
3083 RtlUnlockHeap(HANDLE HeapPtr
)
3085 PHEAP Heap
= (PHEAP
)HeapPtr
;
3087 // FIXME Check for special heap
3089 /* Check if it's really a heap */
3090 if (Heap
->Signature
!= HEAP_SIGNATURE
) return FALSE
;
3092 /* Unlock if it's lockable */
3093 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3095 RtlLeaveHeapLock(Heap
->LockVariable
);
3102 /***********************************************************************
3105 * Heap [in] Handle of heap
3106 * Flags [in] Heap size control flags
3107 * Ptr [in] Address of memory to return size for
3110 * Size in bytes of allocated memory
3111 * 0xffffffff: Failure
3122 PHEAP Heap
= (PHEAP
)HeapPtr
;
3123 PHEAP_ENTRY HeapEntry
;
3126 // FIXME This is a hack around missing SEH support!
3129 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE
);
3134 Flags
|= Heap
->Flags
;
3136 // FIXME Special heap
3138 /* Get the heap entry pointer */
3139 HeapEntry
= (PHEAP_ENTRY
)Ptr
- 1;
3141 /* Return -1 if that entry is free */
3142 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3144 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3148 /* Get size of this block depending if it's a usual or a big one */
3149 if (HeapEntry
->Flags
& HEAP_ENTRY_VIRTUAL_ALLOC
)
3151 EntrySize
= RtlpGetSizeOfBigBlock(HeapEntry
);
3156 EntrySize
= (HeapEntry
->Size
<< HEAP_ENTRY_SHIFT
) - HeapEntry
->UnusedBytes
;
3159 /* Return calculated size */
3164 /***********************************************************************
3166 * Validates a specified heap.
3169 * Heap [in] Handle to the heap
3170 * Flags [in] Bit flags that control access during operation
3171 * Block [in] Optional pointer to memory block to validate
3182 BOOLEAN NTAPI
RtlValidateHeap(
3190 /* Imitate success */
3195 RtlInitializeHeapManager(VOID
)
3200 Peb
= RtlGetCurrentPeb();
3202 /* Initialize heap-related fields of PEB */
3203 Peb
->NumberOfHeaps
= 0;
3205 /* Initialize the process heaps list protecting lock */
3206 RtlInitializeHeapLock(&RtlpProcessHeapsListLock
);
3214 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine
,
3218 return STATUS_NOT_IMPLEMENTED
;
3226 RtlGetProcessHeaps(ULONG count
,
3238 RtlValidateProcessHeaps(VOID
)
3250 IN PVOID HeapHandle
,
3263 RtlSetUserValueHeap(IN PVOID HeapHandle
,
3265 IN PVOID BaseAddress
,
3268 PHEAP Heap
= (PHEAP
)HeapHandle
;
3269 PHEAP_ENTRY HeapEntry
;
3270 PHEAP_ENTRY_EXTRA Extra
;
3271 BOOLEAN HeapLocked
= FALSE
;
3274 Flags
|= Heap
->Flags
;
3276 /* Lock if it's lockable */
3277 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3279 RtlEnterHeapLock(Heap
->LockVariable
);
3283 /* Get a pointer to the entry */
3284 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3286 /* If it's a free entry - return error */
3287 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3289 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3291 /* Release the heap lock if it was acquired */
3293 RtlLeaveHeapLock(Heap
->LockVariable
);
3298 /* Check if this entry has an extra stuff associated with it */
3299 if (HeapEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
3301 /* Use extra to store the value */
3302 Extra
= RtlpGetExtraStuffPointer(HeapEntry
);
3303 Extra
->Settable
= (ULONG_PTR
)UserValue
;
3306 /* Release the heap lock if it was acquired */
3308 RtlLeaveHeapLock(Heap
->LockVariable
);
3318 RtlSetUserFlagsHeap(IN PVOID HeapHandle
,
3320 IN PVOID BaseAddress
,
3321 IN ULONG UserFlagsReset
,
3322 IN ULONG UserFlagsSet
)
3324 PHEAP Heap
= (PHEAP
)HeapHandle
;
3325 PHEAP_ENTRY HeapEntry
;
3326 BOOLEAN HeapLocked
= FALSE
;
3329 Flags
|= Heap
->Flags
;
3331 /* Lock if it's lockable */
3332 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3334 RtlEnterHeapLock(Heap
->LockVariable
);
3338 /* Get a pointer to the entry */
3339 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3341 /* If it's a free entry - return error */
3342 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3344 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3346 /* Release the heap lock if it was acquired */
3348 RtlLeaveHeapLock(Heap
->LockVariable
);
3353 /* Set / reset flags */
3354 HeapEntry
->Flags
&= ~(UserFlagsReset
>> 4);
3355 HeapEntry
->Flags
|= (UserFlagsSet
>> 4);
3357 /* Release the heap lock if it was acquired */
3359 RtlLeaveHeapLock(Heap
->LockVariable
);
3369 RtlGetUserInfoHeap(IN PVOID HeapHandle
,
3371 IN PVOID BaseAddress
,
3372 OUT PVOID
*UserValue
,
3373 OUT PULONG UserFlags
)
3375 PHEAP Heap
= (PHEAP
)HeapHandle
;
3376 PHEAP_ENTRY HeapEntry
;
3377 PHEAP_ENTRY_EXTRA Extra
;
3378 BOOLEAN HeapLocked
= FALSE
;
3381 Flags
|= Heap
->Flags
;
3383 /* Lock if it's lockable */
3384 if (!(Heap
->Flags
& HEAP_NO_SERIALIZE
))
3386 RtlEnterHeapLock(Heap
->LockVariable
);
3390 /* Get a pointer to the entry */
3391 HeapEntry
= (PHEAP_ENTRY
)BaseAddress
- 1;
3393 /* If it's a free entry - return error */
3394 if (!(HeapEntry
->Flags
& HEAP_ENTRY_BUSY
))
3396 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER
);
3398 /* Release the heap lock if it was acquired */
3400 RtlLeaveHeapLock(Heap
->LockVariable
);
3405 /* Check if this entry has an extra stuff associated with it */
3406 if (HeapEntry
->Flags
& HEAP_ENTRY_EXTRA_PRESENT
)
3408 /* Get pointer to extra data */
3409 Extra
= RtlpGetExtraStuffPointer(HeapEntry
);
3411 /* Pass user value */
3413 *UserValue
= (PVOID
)Extra
->Settable
;
3415 /* Decode and return user flags */
3417 *UserFlags
= (HeapEntry
->Flags
& HEAP_ENTRY_SETTABLE_FLAGS
) << 4;
3420 /* Release the heap lock if it was acquired */
3422 RtlLeaveHeapLock(Heap
->LockVariable
);
3432 RtlUsageHeap(IN HANDLE Heap
,
3434 OUT PRTL_HEAP_USAGE Usage
)
3438 return STATUS_NOT_IMPLEMENTED
;
3443 RtlQueryTagHeap(IN PVOID HeapHandle
,
3446 IN BOOLEAN ResetCounters
,
3447 OUT PRTL_HEAP_TAG_INFO HeapTagInfo
)
3456 RtlExtendHeap(IN HANDLE Heap
,
3468 RtlCreateTagHeap(IN HANDLE HeapHandle
,
3471 IN PWSTR TagSubName
)
3480 RtlWalkHeap(IN HANDLE HeapHandle
,
3484 return STATUS_NOT_IMPLEMENTED
;
3489 RtlProtectHeap(IN PVOID HeapHandle
,
3490 IN BOOLEAN ReadOnly
)
3498 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL
,
3499 IN HEAP_INFORMATION_CLASS HeapInformationClass
,
3500 IN PVOID HeapInformation
,
3501 IN SIZE_T HeapInformationLength
)
3503 /* Setting heap information is not really supported except for enabling LFH */
3504 if (HeapInformationClass
== 0) return STATUS_SUCCESS
;
3506 /* Check buffer length */
3507 if (HeapInformationLength
< sizeof(ULONG
))
3509 /* The provided buffer is too small */
3510 return STATUS_BUFFER_TOO_SMALL
;
3513 /* Check for a special magic value for enabling LFH */
3514 if (*(PULONG
)HeapInformation
== 2)
3516 DPRINT1("RtlSetHeapInformation() needs to enable LFH\n");
3517 return STATUS_SUCCESS
;
3520 return STATUS_UNSUCCESSFUL
;
3525 RtlQueryHeapInformation(HANDLE HeapHandle
,
3526 HEAP_INFORMATION_CLASS HeapInformationClass
,
3527 PVOID HeapInformation OPTIONAL
,
3528 SIZE_T HeapInformationLength OPTIONAL
,
3529 PSIZE_T ReturnLength OPTIONAL
)
3531 PHEAP Heap
= (PHEAP
)HeapHandle
;
3533 /* Only HeapCompatibilityInformation is supported */
3534 if (HeapInformationClass
!= HeapCompatibilityInformation
)
3535 return STATUS_UNSUCCESSFUL
;
3537 /* Set result length */
3538 if (ReturnLength
) *ReturnLength
= sizeof(ULONG
);
3540 /* Check buffer length */
3541 if (HeapInformationLength
< sizeof(ULONG
))
3543 /* It's too small, return needed length */
3544 return STATUS_BUFFER_TOO_SMALL
;
3547 /* Return front end heap type */
3548 *(PULONG
)HeapInformation
= Heap
->FrontEndHeapType
;
3550 return STATUS_SUCCESS
;
3555 RtlMultipleAllocateHeap(IN PVOID HeapHandle
,
3567 RtlMultipleFreeHeap(IN PVOID HeapHandle
,