3 * Copyright (C) 2011 Timo Kreuzer (timo.kreuzer@reactos.org)
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 #define FREELDR_HEAP_VERIFIER
25 DBG_DEFAULT_CHANNEL(HEAP
);
27 #define REDZONE_MARK 0xCCCCCCCCCCCCCCCCULL
28 #define REDZONE_ALLOCATION 24
29 #define REDZONE_LOW_OFFSET 16
30 #define REDZONE_SIZE(Block) ((ULONG64*)Block->Data)
31 #define REDZONE_LOW(Block) ((ULONG64*)Block->Data + 1)
32 #define REDZONE_HI(Block) ((ULONG64*)((PUCHAR)Block->Data + 16 + *REDZONE_SIZE(Block)))
34 PVOID FrLdrDefaultHeap
;
37 typedef struct _BLOCK_DATA
41 } BLOCK_DATA
, *PBLOCK_DATA
;
43 typedef struct _HEAP_BLOCK
49 } HEAP_BLOCK
, *PHEAP_BLOCK
;
54 SIZE_T CurrentAllocBytes
;
58 SIZE_T LargestAllocation
;
59 ULONGLONG AllocationTime
;
61 ULONG_PTR TerminatingBlock
;
68 TYPE_OF_MEMORY MemoryType
)
74 TRACE("HeapCreate(MemoryType=%ld)\n", MemoryType
);
76 /* Allocate some memory for the heap */
77 MaximumSize
= ALIGN_UP_BY(MaximumSize
, MM_PAGE_SIZE
);
78 Heap
= MmAllocateMemoryWithType(MaximumSize
, MemoryType
);
81 ERR("HEAP: Failed to allocate heap of size 0x%lx, Type\n",
82 MaximumSize
, MemoryType
);
86 /* Initialize the heap header */
87 Heap
->MaximumSize
= MaximumSize
;
88 Heap
->CurrentAllocBytes
= 0;
89 Heap
->MaxAllocBytes
= 0;
92 Heap
->LargestAllocation
= 0;
94 /* Calculate what's left to process */
95 Remaining
= (MaximumSize
- sizeof(HEAP
)) / sizeof(HEAP_BLOCK
);
96 TRACE("Remaining = %ld\n", Remaining
);
98 /* Substract 2 for the terminating entry (header + free entry) */
101 Block
= &Heap
->Blocks
;
104 /* Create free blocks */
105 while (Remaining
> 1)
107 /* Initialize this free block */
108 Block
->Size
= (USHORT
)min(MAXUSHORT
, Remaining
- 1);
109 Block
->PreviousSize
= PreviousSize
;
111 Block
->Data
[0].Flink
= (Block
- &Heap
->Blocks
) + Block
->Size
+ 1;
112 Block
->Data
[0].Blink
= (Block
- &Heap
->Blocks
) - 1 - PreviousSize
;
114 /* Substract current block size from remainder */
115 Remaining
-= (Block
->Size
+ 1);
117 /* Go to next block */
118 PreviousSize
= Block
->Size
;
119 Block
= Block
+ Block
->Size
+ 1;
121 TRACE("Remaining = %ld\n", Remaining
);
124 /* Now finish with a terminating block */
125 Heap
->TerminatingBlock
= Block
- &Heap
->Blocks
;
127 Block
->PreviousSize
= PreviousSize
;
129 Block
->Data
[0].Flink
= 0;
130 Block
->Data
[0].Blink
= (Block
- &Heap
->Blocks
) - 1 - PreviousSize
;
131 Heap
->Blocks
.Data
[0].Blink
= Heap
->TerminatingBlock
;
140 PHEAP Heap
= HeapHandle
;
142 /* Mark all pages as firmware temporary, so they are free for the kernel */
143 MmMarkPagesInLookupTable(PageLookupTableAddress
,
144 (ULONG_PTR
)Heap
/ MM_PAGE_SIZE
,
145 (PFN_COUNT
)(Heap
->MaximumSize
/ MM_PAGE_SIZE
),
146 LoaderFirmwareTemporary
);
149 /* Make sure everything is dead */
150 RtlFillMemory(Heap
, Heap
->MaximumSize
, 0xCCCCCCCC);
154 #ifdef FREELDR_HEAP_VERIFIER
159 PHEAP Heap
= HeapHandle
;
162 /* Loop all heap chunks */
163 for (Block
= &Heap
->Blocks
;
165 Block
= Block
+ 1 + Block
->Size
)
167 /* Continue, if its not free */
170 /* Verify size and redzones */
171 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
172 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
173 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
178 #endif /* FREELDR_HEAP_VERIFIER */
184 PHEAP Heap
= HeapHandle
;
186 PUCHAR StartAddress
, EndAddress
;
187 PFN_COUNT FreePages
, AllPages
, AllFreePages
= 0;
188 TRACE("HeapRelease(%p)\n", HeapHandle
);
190 /* Loop all heap chunks */
191 for (Block
= &Heap
->Blocks
;
193 Block
= Block
+ 1 + Block
->Size
)
195 /* Continue, if its not free */
198 #ifdef FREELDR_HEAP_VERIFIER
199 /* Verify size and redzones */
200 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
201 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
202 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
207 /* Calculate page aligned start address of the free region */
208 StartAddress
= ALIGN_UP_POINTER_BY(Block
->Data
, PAGE_SIZE
);
210 /* Walk over adjacent free blocks */
211 while (Block
->Tag
== 0) Block
= Block
+ Block
->Size
+ 1;
213 /* Check if this was the last block */
214 if (Block
->Size
== 0)
216 /* Align the end address up to cover the end of the heap */
217 EndAddress
= ALIGN_UP_POINTER_BY(Block
->Data
, PAGE_SIZE
);
221 /* Align the end address down to not cover any allocations */
222 EndAddress
= ALIGN_DOWN_POINTER_BY(Block
->Data
, PAGE_SIZE
);
225 /* Check if we have free pages */
226 if (EndAddress
> StartAddress
)
228 /* Calculate the size of the free region in pages */
229 FreePages
= (PFN_COUNT
)((EndAddress
- StartAddress
) / MM_PAGE_SIZE
);
230 AllFreePages
+= FreePages
;
232 /* Now mark the pages free */
233 MmMarkPagesInLookupTable(PageLookupTableAddress
,
234 (ULONG_PTR
)StartAddress
/ MM_PAGE_SIZE
,
239 /* bail out, if it was the last block */
240 if (Block
->Size
== 0) break;
243 AllPages
= Heap
->MaximumSize
/ MM_PAGE_SIZE
;
244 TRACE("HeapRelease() done, freed %lu of %lu pages\n", AllFreePages
, AllPages
);
248 FrLdrHeapCleanupAll(VOID
)
252 Heap
= FrLdrDefaultHeap
;
253 TRACE("Heap statistics for default heap:\n"
254 "CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
255 "NumAllocs=%ld, NumFrees=%ld\n",
256 Heap
->CurrentAllocBytes
, Heap
->MaxAllocBytes
, Heap
->LargestAllocation
,
257 Heap
->NumAllocs
, Heap
->NumFrees
);
258 TRACE("AllocTime = %I64d, FreeTime = %I64d, sum = %I64d\n",
259 Heap
->AllocationTime
, Heap
->FreeTime
, Heap
->AllocationTime
+ Heap
->FreeTime
);
262 /* Release free pages from the default heap */
263 FrLdrHeapRelease(FrLdrDefaultHeap
);
265 Heap
= FrLdrTempHeap
;
266 TRACE("Heap statistics for temp heap:\n"
267 "CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
268 "NumAllocs=%ld, NumFrees=%ld\n",
269 Heap
->CurrentAllocBytes
, Heap
->MaxAllocBytes
, Heap
->LargestAllocation
,
270 Heap
->NumAllocs
, Heap
->NumFrees
);
272 /* Destroy the temp heap */
273 FrLdrHeapDestroy(FrLdrTempHeap
);
277 FrLdrHeapRemoveFreeList(
281 PHEAP_BLOCK Previous
, Next
;
283 Next
= &Heap
->Blocks
+ Block
->Data
[0].Flink
;
284 Previous
= &Heap
->Blocks
+ Block
->Data
[0].Blink
;
285 ASSERT((Next
->Tag
== 0) || (Next
->Tag
== 'dnE#'));
286 ASSERT(Next
->Data
[0].Blink
== Block
- &Heap
->Blocks
);
287 ASSERT((Previous
->Tag
== 0) || (Previous
->Tag
== 'dnE#'));
288 ASSERT(Previous
->Data
[0].Flink
== Block
- &Heap
->Blocks
);
290 Next
->Data
[0].Blink
= Previous
- &Heap
->Blocks
;
291 Previous
->Data
[0].Flink
= Next
- &Heap
->Blocks
;
295 FrLdrHeapInsertFreeList(
297 PHEAP_BLOCK FreeBlock
)
299 PHEAP_BLOCK ListHead
, NextBlock
;
300 ASSERT(FreeBlock
->Tag
== 0);
302 /* Terminating block serves as free list head */
303 ListHead
= &Heap
->Blocks
+ Heap
->TerminatingBlock
;
305 for (NextBlock
= &Heap
->Blocks
+ ListHead
->Data
[0].Flink
;
306 NextBlock
< FreeBlock
;
307 NextBlock
= &Heap
->Blocks
+ NextBlock
->Data
[0].Flink
);
309 FreeBlock
->Data
[0].Flink
= NextBlock
- &Heap
->Blocks
;
310 FreeBlock
->Data
[0].Blink
= NextBlock
->Data
[0].Blink
;
311 NextBlock
->Data
[0].Blink
= FreeBlock
- &Heap
->Blocks
;
312 NextBlock
= &Heap
->Blocks
+ FreeBlock
->Data
[0].Blink
;
313 NextBlock
->Data
[0].Flink
= FreeBlock
- &Heap
->Blocks
;
322 PHEAP Heap
= HeapHandle
;
323 PHEAP_BLOCK Block
, NextBlock
;
324 USHORT BlockSize
, Remaining
;
325 #if DBG && !defined(_M_ARM)
326 ULONGLONG Time
= __rdtsc();
329 #ifdef FREELDR_HEAP_VERIFIER
330 /* Verify the heap */
331 FrLdrHeapVerify(HeapHandle
);
333 /* Add space for a size field and 2 redzones */
334 ByteSize
+= REDZONE_ALLOCATION
;
337 /* Check if the allocation is too large */
338 if ((ByteSize
+ sizeof(HEAP_BLOCK
)) > MAXUSHORT
* sizeof(HEAP_BLOCK
))
340 ERR("HEAP: Allocation of 0x%lx bytes too large\n", ByteSize
);
344 /* We need a proper tag */
345 if (Tag
== 0) Tag
= 'enoN';
347 /* Calculate alloc size */
348 BlockSize
= (USHORT
)((ByteSize
+ sizeof(HEAP_BLOCK
) - 1) / sizeof(HEAP_BLOCK
));
350 /* Walk the free block list */
351 Block
= &Heap
->Blocks
+ Heap
->TerminatingBlock
;
352 for (Block
= &Heap
->Blocks
+ Block
->Data
[0].Flink
;
354 Block
= &Heap
->Blocks
+ Block
->Data
[0].Flink
)
356 ASSERT(Block
->Tag
== 0);
358 /* Continue, if its too small */
359 if (Block
->Size
< BlockSize
) continue;
361 /* This block is just fine, use it */
364 /* Remove this entry from the free list */
365 FrLdrHeapRemoveFreeList(Heap
, Block
);
367 /* Calculate the remaining size */
368 Remaining
= Block
->Size
- BlockSize
;
370 /* Check if the remaining space is large enough for a new block */
373 /* Make the allocated block as large as necessary */
374 Block
->Size
= BlockSize
;
376 /* Get pointer to the new block */
377 NextBlock
= Block
+ 1 + BlockSize
;
379 /* Make it a free block */
381 NextBlock
->Size
= Remaining
- 1;
382 NextBlock
->PreviousSize
= BlockSize
;
383 BlockSize
= NextBlock
->Size
;
384 FrLdrHeapInsertFreeList(Heap
, NextBlock
);
386 /* Advance to the next block */
387 NextBlock
= NextBlock
+ 1 + BlockSize
;
391 /* Not enough left, use the full block */
392 BlockSize
= Block
->Size
;
394 /* Get the next block */
395 NextBlock
= Block
+ 1 + BlockSize
;
398 /* Update the next blocks back link */
399 NextBlock
->PreviousSize
= BlockSize
;
401 /* Update heap usage */
403 Heap
->CurrentAllocBytes
+= Block
->Size
* sizeof(HEAP_BLOCK
);
404 Heap
->MaxAllocBytes
= max(Heap
->MaxAllocBytes
, Heap
->CurrentAllocBytes
);
405 Heap
->LargestAllocation
= max(Heap
->LargestAllocation
,
406 Block
->Size
* sizeof(HEAP_BLOCK
));
407 #if DBG && !defined(_M_ARM)
408 Heap
->AllocationTime
+= (__rdtsc() - Time
);
410 TRACE("HeapAllocate(%p, %ld, %.4s) -> return %p\n",
411 HeapHandle
, ByteSize
, &Tag
, Block
->Data
);
413 /* HACK: zero out the allocation */
414 RtlZeroMemory(Block
->Data
, Block
->Size
* sizeof(HEAP_BLOCK
));
416 #ifdef FREELDR_HEAP_VERIFIER
417 /* Write size and redzones */
418 *REDZONE_SIZE(Block
) = ByteSize
- REDZONE_ALLOCATION
;
419 *REDZONE_LOW(Block
) = REDZONE_MARK
;
420 *REDZONE_HI(Block
) = REDZONE_MARK
;
422 /* Allocation starts after size field and redzone */
423 return (PUCHAR
)Block
->Data
+ REDZONE_LOW_OFFSET
;
425 /* Return pointer to the data */
429 /* We found nothing */
430 WARN("HEAP: nothing suitable found for 0x%lx bytes\n", ByteSize
);
440 PHEAP Heap
= HeapHandle
;
441 PHEAP_BLOCK Block
, PrevBlock
, NextBlock
;
442 #if DBG && !defined(_M_ARM)
443 ULONGLONG Time
= __rdtsc();
445 TRACE("HeapFree(%p, %p)\n", HeapHandle
, Pointer
);
446 ASSERT(Tag
!= 'dnE#');
448 #ifdef FREELDR_HEAP_VERIFIER
449 /* Verify the heap */
450 FrLdrHeapVerify(HeapHandle
);
453 /* Check if the block is really inside this heap */
454 if ((Pointer
< (PVOID
)(Heap
+ 1)) ||
455 (Pointer
> (PVOID
)((PUCHAR
)Heap
+ Heap
->MaximumSize
)))
457 ERR("HEAP: trying to free %p outside of heap %p\n", Pointer
, Heap
);
461 Block
= ((PHEAP_BLOCK
)Pointer
) - 1;
462 #ifdef FREELDR_HEAP_VERIFIER
463 Block
= (PHEAP_BLOCK
)((PUCHAR
)Block
- REDZONE_LOW_OFFSET
);
465 /* Verify size and redzones */
466 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
467 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
468 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
471 /* Check if the tag matches */
472 if ((Tag
&& (Block
->Tag
!= Tag
)) || (Block
->Tag
== 0))
474 ERR("HEAP: Bad tag! Pointer=%p: block tag '%.4s', requested '%.4s', size=0x%lx\n",
475 Pointer
, &Block
->Tag
, &Tag
, Block
->Size
);
484 RtlFillMemory(Block
->Data
, Block
->Size
* sizeof(HEAP_BLOCK
), 0xCCCCCCCC);
487 /* Update heap usage */
489 Heap
->CurrentAllocBytes
-= Block
->Size
* sizeof(HEAP_BLOCK
);
491 /* Get pointers to the next and previous block */
492 PrevBlock
= Block
- Block
->PreviousSize
- 1;
493 NextBlock
= Block
+ Block
->Size
+ 1;
495 /* Check if next block is free */
496 if ((NextBlock
->Tag
== 0) &&
497 ((Block
->Size
+ NextBlock
->Size
+ 1) <= MAXUSHORT
))
499 /* Merge next block into current */
500 Block
->Size
+= NextBlock
->Size
+ 1;
501 FrLdrHeapRemoveFreeList(Heap
, NextBlock
);
503 NextBlock
= Block
+ Block
->Size
+ 1;
506 /* Check if there is a block before and it's free */
507 if ((Block
->PreviousSize
!= 0) && (PrevBlock
->Tag
== 0) &&
508 ((PrevBlock
->Size
+ Block
->Size
+ 1) <= MAXUSHORT
))
510 /* Merge current block into previous */
511 PrevBlock
->Size
+= Block
->Size
+ 1;
516 /* Insert the entry into the free list */
517 FrLdrHeapInsertFreeList(Heap
, Block
);
520 /* Update the next block's back link */
521 NextBlock
->PreviousSize
= Block
->Size
;
522 #if DBG && !defined(_M_ARM)
523 Heap
->FreeTime
+= (__rdtsc() - Time
);
528 /* Wrapper functions *********************************************************/
531 MmInitializeHeap(PVOID PageLookupTable
)
533 TRACE("MmInitializeHeap()\n");
535 /* Create the default heap */
536 FrLdrDefaultHeap
= FrLdrHeapCreate(DEFAULT_HEAP_SIZE
, LoaderOsloaderHeap
);
537 ASSERT(FrLdrDefaultHeap
);
539 /* Create a temporary heap */
540 FrLdrTempHeap
= FrLdrHeapCreate(TEMP_HEAP_SIZE
, LoaderFirmwareTemporary
);
541 ASSERT(FrLdrTempHeap
);
543 TRACE("MmInitializeHeap() done, default heap %p, temp heap %p\n",
544 FrLdrDefaultHeap
, FrLdrTempHeap
);
549 ExAllocatePoolWithTag(
550 IN POOL_TYPE PoolType
,
551 IN SIZE_T NumberOfBytes
,
554 return FrLdrHeapAllocateEx(FrLdrDefaultHeap
, NumberOfBytes
, Tag
);
560 IN POOL_TYPE PoolType
,
561 IN SIZE_T NumberOfBytes
)
563 return FrLdrHeapAllocateEx(FrLdrDefaultHeap
, NumberOfBytes
, 0);
571 FrLdrHeapFreeEx(FrLdrDefaultHeap
, P
, 0);
580 FrLdrHeapFreeEx(FrLdrDefaultHeap
, P
, Tag
);
592 ptr
= FrLdrHeapAllocateEx(FrLdrDefaultHeap
, Size
, ' ltR');
593 if (ptr
&& (Flags
& HEAP_ZERO_MEMORY
))
595 RtlZeroMemory(ptr
, Size
);
608 FrLdrHeapFreeEx(FrLdrDefaultHeap
, HeapBase
, ' ltR');