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 DEFAULT_HEAP_SIZE (1024 * 1024)
28 #define TEMP_HEAP_SIZE (1024 * 1024)
30 #define REDZONE_MARK 0xCCCCCCCCCCCCCCCCULL
31 #define REDZONE_ALLOCATION 24
32 #define REDZONE_LOW_OFFSET 16
33 #define REDZONE_SIZE(Block) ((ULONG64*)Block->Data)
34 #define REDZONE_LOW(Block) ((ULONG64*)Block->Data + 1)
35 #define REDZONE_HI(Block) ((ULONG64*)((PUCHAR)Block->Data + 16 + *REDZONE_SIZE(Block)))
37 PVOID FrLdrDefaultHeap
;
40 typedef struct _BLOCK_DATA
44 } BLOCK_DATA
, *PBLOCK_DATA
;
46 typedef struct _HEAP_BLOCK
52 } HEAP_BLOCK
, *PHEAP_BLOCK
;
57 SIZE_T CurrentAllocBytes
;
61 SIZE_T LargestAllocation
;
62 ULONGLONG AllocationTime
;
64 ULONG_PTR TerminatingBlock
;
71 TYPE_OF_MEMORY MemoryType
)
77 TRACE("HeapCreate(MemoryType=%ld)\n", MemoryType
);
79 /* Allocate some memory for the heap */
80 MaximumSize
= ALIGN_UP_BY(MaximumSize
, MM_PAGE_SIZE
);
81 Heap
= MmAllocateMemoryWithType(MaximumSize
, MemoryType
);
84 ERR("HEAP: Failed to allocate heap of size 0x%lx, Type\n",
85 MaximumSize
, MemoryType
);
89 /* Initialize the heap header */
90 Heap
->MaximumSize
= MaximumSize
;
91 Heap
->CurrentAllocBytes
= 0;
92 Heap
->MaxAllocBytes
= 0;
95 Heap
->LargestAllocation
= 0;
97 /* Calculate what's left to process */
98 Remaining
= (MaximumSize
- sizeof(HEAP
)) / sizeof(HEAP_BLOCK
);
99 TRACE("Remaining = %ld\n", Remaining
);
101 /* Substract 2 for the terminating entry (header + free entry) */
104 Block
= &Heap
->Blocks
;
107 /* Create free blocks */
108 while (Remaining
> 1)
110 /* Initialize this free block */
111 Block
->Size
= (USHORT
)min(MAXUSHORT
, Remaining
- 1);
112 Block
->PreviousSize
= PreviousSize
;
114 Block
->Data
[0].Flink
= (Block
- &Heap
->Blocks
) + Block
->Size
+ 1;
115 Block
->Data
[0].Blink
= (Block
- &Heap
->Blocks
) - 1 - PreviousSize
;
117 /* Substract current block size from remainder */
118 Remaining
-= (Block
->Size
+ 1);
120 /* Go to next block */
121 PreviousSize
= Block
->Size
;
122 Block
= Block
+ Block
->Size
+ 1;
124 TRACE("Remaining = %ld\n", Remaining
);
127 /* Now finish with a terminating block */
128 Heap
->TerminatingBlock
= Block
- &Heap
->Blocks
;
130 Block
->PreviousSize
= PreviousSize
;
132 Block
->Data
[0].Flink
= 0;
133 Block
->Data
[0].Blink
= (Block
- &Heap
->Blocks
) - 1 - PreviousSize
;
134 Heap
->Blocks
.Data
[0].Blink
= Heap
->TerminatingBlock
;
143 PHEAP Heap
= HeapHandle
;
145 /* Mark all pages as firmware temporary, so they are free for the kernel */
146 MmMarkPagesInLookupTable(PageLookupTableAddress
,
147 (ULONG_PTR
)Heap
/ MM_PAGE_SIZE
,
148 (PFN_COUNT
)(Heap
->MaximumSize
/ MM_PAGE_SIZE
),
149 LoaderFirmwareTemporary
);
152 #ifdef FREELDR_HEAP_VERIFIER
157 PHEAP Heap
= HeapHandle
;
160 /* Loop all heap chunks */
161 for (Block
= &Heap
->Blocks
;
163 Block
= Block
+ 1 + Block
->Size
)
165 /* Continue, if its not free */
168 /* Verify size and redzones */
169 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
170 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
171 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
176 #endif /* FREELDR_HEAP_VERIFIER */
182 PHEAP Heap
= HeapHandle
;
184 PUCHAR StartAddress
, EndAddress
;
185 PFN_COUNT FreePages
, AllFreePages
= 0;
186 TRACE("HeapRelease(%p)\n", HeapHandle
);
188 /* Loop all heap chunks */
189 for (Block
= &Heap
->Blocks
;
191 Block
= Block
+ 1 + Block
->Size
)
193 /* Continue, if its not free */
196 #ifdef FREELDR_HEAP_VERIFIER
197 /* Verify size and redzones */
198 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
199 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
200 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
205 /* Calculate page aligned start address of the free region */
206 StartAddress
= ALIGN_UP_POINTER_BY(Block
->Data
, PAGE_SIZE
);
208 /* Walk over adjacent free blocks */
209 while (Block
->Tag
== 0) Block
= Block
+ Block
->Size
+ 1;
211 /* Check if this was the last block */
212 if (Block
->Size
== 0)
214 /* Align the end address up to cover the end of the heap */
215 EndAddress
= ALIGN_UP_POINTER_BY(Block
->Data
, PAGE_SIZE
);
219 /* Align the end address down to not cover any allocations */
220 EndAddress
= ALIGN_DOWN_POINTER_BY(Block
->Data
, PAGE_SIZE
);
223 /* Check if we have free pages */
224 if (EndAddress
> StartAddress
)
226 /* Calculate the size of the free region in pages */
227 FreePages
= (PFN_COUNT
)((EndAddress
- StartAddress
) / MM_PAGE_SIZE
);
228 AllFreePages
+= FreePages
;
230 /* Now mark the pages free */
231 MmMarkPagesInLookupTable(PageLookupTableAddress
,
232 (ULONG_PTR
)StartAddress
/ MM_PAGE_SIZE
,
237 /* bail out, if it was the last block */
238 if (Block
->Size
== 0) break;
241 TRACE("HeapRelease() done, freed %ld pages\n", AllFreePages
);
245 FrLdrHeapCleanupAll(VOID
)
249 Heap
= FrLdrDefaultHeap
;
250 TRACE("Heap statistics for default heap:\n"
251 "CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
252 "NumAllocs=%ld, NumFrees=%ld\n",
253 Heap
->CurrentAllocBytes
, Heap
->MaxAllocBytes
, Heap
->LargestAllocation
,
254 Heap
->NumAllocs
, Heap
->NumFrees
);
255 TRACE("AllocTime = %I64d, FreeTime = %I64d, sum = %I64d\n",
256 Heap
->AllocationTime
, Heap
->FreeTime
, Heap
->AllocationTime
+ Heap
->FreeTime
);
259 /* Release fre pages */
260 FrLdrHeapRelease(FrLdrDefaultHeap
);
262 Heap
= FrLdrTempHeap
;
263 TRACE("Heap statistics for temp heap:\n"
264 "CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
265 "NumAllocs=%ld, NumFrees=%ld\n",
266 Heap
->CurrentAllocBytes
, Heap
->MaxAllocBytes
, Heap
->LargestAllocation
,
267 Heap
->NumAllocs
, Heap
->NumFrees
);
269 /* Destroy the heap */
270 FrLdrHeapDestroy(FrLdrTempHeap
);
274 FrLdrHeapRemoveFreeList(
278 PHEAP_BLOCK Previous
, Next
;
280 Next
= &Heap
->Blocks
+ Block
->Data
[0].Flink
;
281 Previous
= &Heap
->Blocks
+ Block
->Data
[0].Blink
;
282 ASSERT((Next
->Tag
== 0) || (Next
->Tag
== 'dnE#'));
283 ASSERT(Next
->Data
[0].Blink
== Block
- &Heap
->Blocks
);
284 ASSERT((Previous
->Tag
== 0) || (Previous
->Tag
== 'dnE#'));
285 ASSERT(Previous
->Data
[0].Flink
== Block
- &Heap
->Blocks
);
287 Next
->Data
[0].Blink
= Previous
- &Heap
->Blocks
;
288 Previous
->Data
[0].Flink
= Next
- &Heap
->Blocks
;
292 FrLdrHeapInsertFreeList(
294 PHEAP_BLOCK FreeBlock
)
296 PHEAP_BLOCK ListHead
, NextBlock
;
297 ASSERT(FreeBlock
->Tag
== 0);
299 /* Terminating block serves as free list head */
300 ListHead
= &Heap
->Blocks
+ Heap
->TerminatingBlock
;
302 for (NextBlock
= &Heap
->Blocks
+ ListHead
->Data
[0].Flink
;
303 NextBlock
< FreeBlock
;
304 NextBlock
= &Heap
->Blocks
+ NextBlock
->Data
[0].Flink
);
306 FreeBlock
->Data
[0].Flink
= NextBlock
- &Heap
->Blocks
;
307 FreeBlock
->Data
[0].Blink
= NextBlock
->Data
[0].Blink
;
308 NextBlock
->Data
[0].Blink
= FreeBlock
- &Heap
->Blocks
;
309 NextBlock
= &Heap
->Blocks
+ FreeBlock
->Data
[0].Blink
;
310 NextBlock
->Data
[0].Flink
= FreeBlock
- &Heap
->Blocks
;
319 PHEAP Heap
= HeapHandle
;
320 PHEAP_BLOCK Block
, NextBlock
;
321 USHORT BlockSize
, Remaining
;
322 ULONGLONG Time
= __rdtsc();
324 #ifdef FREELDR_HEAP_VERIFIER
325 /* Verify the heap */
326 FrLdrHeapVerify(HeapHandle
);
328 /* Add space for a size field and 2 redzones */
329 ByteSize
+= REDZONE_ALLOCATION
;
332 /* Check if the allocation is too large */
333 if ((ByteSize
+ sizeof(HEAP_BLOCK
)) > MAXUSHORT
* sizeof(HEAP_BLOCK
))
335 ERR("HEAP: Allocation of 0x%lx bytes too large\n", ByteSize
);
339 /* We need a proper tag */
340 if (Tag
== 0) Tag
= 'enoN';
342 /* Calculate alloc size */
343 BlockSize
= (USHORT
)((ByteSize
+ sizeof(HEAP_BLOCK
) - 1) / sizeof(HEAP_BLOCK
));
345 /* Walk the free block list */
346 Block
= &Heap
->Blocks
+ Heap
->TerminatingBlock
;
347 for (Block
= &Heap
->Blocks
+ Block
->Data
[0].Flink
;
349 Block
= &Heap
->Blocks
+ Block
->Data
[0].Flink
)
351 ASSERT(Block
->Tag
== 0);
353 /* Continue, if its too small */
354 if (Block
->Size
< BlockSize
) continue;
356 /* This block is just fine, use it */
359 /* Remove this entry from the free list */
360 FrLdrHeapRemoveFreeList(Heap
, Block
);
362 /* Calculate the remaining size */
363 Remaining
= Block
->Size
- BlockSize
;
365 /* Check if the remaining space is large enough for a new block */
368 /* Make the allocated block as large as neccessary */
369 Block
->Size
= BlockSize
;
371 /* Get pointer to the new block */
372 NextBlock
= Block
+ 1 + BlockSize
;
374 /* Make it a free block */
376 NextBlock
->Size
= Remaining
- 1;
377 NextBlock
->PreviousSize
= BlockSize
;
378 BlockSize
= NextBlock
->Size
;
379 FrLdrHeapInsertFreeList(Heap
, NextBlock
);
381 /* Advance to the next block */
382 NextBlock
= NextBlock
+ 1 + BlockSize
;
386 /* Not enough left, use the full block */
387 BlockSize
= Block
->Size
;
389 /* Get the next block */
390 NextBlock
= Block
+ 1 + BlockSize
;
393 /* Update the next blocks back link */
394 NextBlock
->PreviousSize
= BlockSize
;
396 /* Update heap usage */
398 Heap
->CurrentAllocBytes
+= Block
->Size
* sizeof(HEAP_BLOCK
);
399 Heap
->MaxAllocBytes
= max(Heap
->MaxAllocBytes
, Heap
->CurrentAllocBytes
);
400 Heap
->LargestAllocation
= max(Heap
->LargestAllocation
,
401 Block
->Size
* sizeof(HEAP_BLOCK
));
402 Heap
->AllocationTime
+= (__rdtsc() - Time
);
404 TRACE("HeapAllocate(%p, %ld, %.4s) -> return %p\n",
405 HeapHandle
, ByteSize
, &Tag
, Block
->Data
);
407 /* HACK: zero out the allocation */
408 RtlZeroMemory(Block
->Data
, Block
->Size
* sizeof(HEAP_BLOCK
));
410 #ifdef FREELDR_HEAP_VERIFIER
411 /* Write size and redzones */
412 *REDZONE_SIZE(Block
) = ByteSize
- REDZONE_ALLOCATION
;
413 *REDZONE_LOW(Block
) = REDZONE_MARK
;
414 *REDZONE_HI(Block
) = REDZONE_MARK
;
416 /* Allcoation starts after size field and redzone */
417 return (PUCHAR
)Block
->Data
+ REDZONE_LOW_OFFSET
;
419 /* Return pointer to the data */
423 /* We found nothing */
424 WARN("HEAP: nothing suitable found for 0x%lx bytes\n", ByteSize
);
434 PHEAP Heap
= HeapHandle
;
435 PHEAP_BLOCK Block
, PrevBlock
, NextBlock
;
436 ULONGLONG Time
= __rdtsc();
437 TRACE("HeapFree(%p, %p)\n", HeapHandle
, Pointer
);
438 ASSERT(Tag
!= 'dnE#');
440 #ifdef FREELDR_HEAP_VERIFIER
441 /* Verify the heap */
442 FrLdrHeapVerify(HeapHandle
);
445 /* Check if the block is really inside this heap */
446 if ((Pointer
< (PVOID
)(Heap
+ 1)) ||
447 (Pointer
> (PVOID
)((PUCHAR
)Heap
+ Heap
->MaximumSize
)))
449 ERR("HEAP: trying to free %p outside of heap %p\n", Pointer
, Heap
);
453 Block
= ((PHEAP_BLOCK
)Pointer
) - 1;
454 #ifdef FREELDR_HEAP_VERIFIER
455 Block
= (PHEAP_BLOCK
)((PUCHAR
)Block
- REDZONE_LOW_OFFSET
);
457 /* Verify size and redzones */
458 ASSERT(*REDZONE_SIZE(Block
) <= Block
->Size
* sizeof(HEAP_BLOCK
));
459 ASSERT(*REDZONE_LOW(Block
) == REDZONE_MARK
);
460 ASSERT(*REDZONE_HI(Block
) == REDZONE_MARK
);
463 /* Check if the tag matches */
464 if ((Tag
&& (Block
->Tag
!= Tag
)) || (Block
->Tag
== 0))
466 ERR("HEAP: Bad tag! Pointer=%p: block tag '%.4s', requested '%.4s', size=0x%lx\n",
467 Pointer
, &Block
->Tag
, &Tag
, Block
->Size
);
474 /* Update heap usage */
476 Heap
->CurrentAllocBytes
-= Block
->Size
* sizeof(HEAP_BLOCK
);
478 /* Get pointers to the next and previous block */
479 PrevBlock
= Block
- Block
->PreviousSize
- 1;
480 NextBlock
= Block
+ Block
->Size
+ 1;
482 /* Check if next block is free */
483 if ((NextBlock
->Tag
== 0) &&
484 ((Block
->Size
+ NextBlock
->Size
+ 1) <= MAXUSHORT
))
486 /* Merge next block into current */
487 Block
->Size
+= NextBlock
->Size
+ 1;
488 FrLdrHeapRemoveFreeList(Heap
, NextBlock
);
490 NextBlock
= Block
+ Block
->Size
+ 1;
493 /* Check if there is a block before and it's free */
494 if ((Block
->PreviousSize
!= 0) && (PrevBlock
->Tag
== 0) &&
495 ((PrevBlock
->Size
+ Block
->Size
+ 1) <= MAXUSHORT
))
497 /* Merge current block into previous */
498 PrevBlock
->Size
+= Block
->Size
+ 1;
503 /* Insert the entry into the free list */
504 FrLdrHeapInsertFreeList(Heap
, Block
);
507 /* Update the next block's back link */
508 NextBlock
->PreviousSize
= Block
->Size
;
510 Heap
->FreeTime
+= (__rdtsc() - Time
);
514 /* Wrapper functions *********************************************************/
517 MmInitializeHeap(PVOID PageLookupTable
)
519 TRACE("MmInitializeHeap()\n");
521 /* Create the default heap */
522 FrLdrDefaultHeap
= FrLdrHeapCreate(DEFAULT_HEAP_SIZE
, LoaderOsloaderHeap
);
523 ASSERT(FrLdrDefaultHeap
);
525 /* Create a temporary heap */
526 FrLdrTempHeap
= FrLdrHeapCreate(TEMP_HEAP_SIZE
, LoaderFirmwareTemporary
);
527 ASSERT(FrLdrTempHeap
);
529 TRACE("MmInitializeHeap() done, default heap %p, temp heap %p\n",
530 FrLdrDefaultHeap
, FrLdrTempHeap
);
534 MmHeapAlloc(SIZE_T MemorySize
)
536 return FrLdrHeapAllocate(FrLdrDefaultHeap
, MemorySize
, 'pHmM');
540 MmHeapFree(PVOID MemoryPointer
)
542 FrLdrHeapFree(FrLdrDefaultHeap
, MemoryPointer
, 'pHmM');
547 ExAllocatePoolWithTag(
548 IN POOL_TYPE PoolType
,
549 IN SIZE_T NumberOfBytes
,
552 return FrLdrHeapAllocate(FrLdrDefaultHeap
, NumberOfBytes
, Tag
);
558 IN POOL_TYPE PoolType
,
559 IN SIZE_T NumberOfBytes
)
561 return FrLdrHeapAllocate(FrLdrDefaultHeap
, NumberOfBytes
, 0);
569 FrLdrHeapFree(FrLdrDefaultHeap
, P
, 0);
578 FrLdrHeapFree(FrLdrDefaultHeap
, P
, Tag
);
590 ptr
= FrLdrHeapAllocate(FrLdrDefaultHeap
, Size
, ' ltR');
591 if (ptr
&& (Flags
& HEAP_ZERO_MEMORY
))
593 RtlZeroMemory(ptr
, Size
);
606 FrLdrHeapFree(FrLdrDefaultHeap
, HeapBase
, ' ltR');