[FREELDR]
[reactos.git] / reactos / boot / freeldr / freeldr / mm / heap.c
1 /*
2 * FreeLoader
3 * Copyright (C) 2011 Timo Kreuzer (timo.kreuzer@reactos.org)
4 *
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.
9 *
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.
14 *
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.
18 */
19
20 #include <freeldr.h>
21 #include <debug.h>
22
23 #define FREELDR_HEAP_VERIFIER
24
25 DBG_DEFAULT_CHANNEL(HEAP);
26
27 #define DEFAULT_HEAP_SIZE (1024 * 1024)
28 #define TEMP_HEAP_SIZE (1024 * 1024)
29
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)))
36
37 PVOID FrLdrDefaultHeap;
38 PVOID FrLdrTempHeap;
39
40 typedef struct _BLOCK_DATA
41 {
42 ULONG_PTR Flink:32;
43 ULONG_PTR Blink:32;
44 } BLOCK_DATA, *PBLOCK_DATA;
45
46 typedef struct _HEAP_BLOCK
47 {
48 USHORT Size;
49 USHORT PreviousSize;
50 ULONG Tag;
51 BLOCK_DATA Data[];
52 } HEAP_BLOCK, *PHEAP_BLOCK;
53
54 typedef struct _HEAP
55 {
56 SIZE_T MaximumSize;
57 SIZE_T CurrentAllocBytes;
58 SIZE_T MaxAllocBytes;
59 ULONG NumAllocs;
60 ULONG NumFrees;
61 SIZE_T LargestAllocation;
62 ULONGLONG AllocationTime;
63 ULONGLONG FreeTime;
64 ULONG_PTR TerminatingBlock;
65 HEAP_BLOCK Blocks;
66 } HEAP, *PHEAP;
67
68 PVOID
69 FrLdrHeapCreate(
70 SIZE_T MaximumSize,
71 TYPE_OF_MEMORY MemoryType)
72 {
73 PHEAP Heap;
74 PHEAP_BLOCK Block;
75 SIZE_T Remaining;
76 USHORT PreviousSize;
77 TRACE("HeapCreate(MemoryType=%ld)\n", MemoryType);
78
79 /* Allocate some memory for the heap */
80 MaximumSize = ALIGN_UP_BY(MaximumSize, MM_PAGE_SIZE);
81 Heap = MmAllocateMemoryWithType(MaximumSize, MemoryType);
82 if (!Heap)
83 {
84 ERR("HEAP: Failed to allocate heap of size 0x%lx, Type\n",
85 MaximumSize, MemoryType);
86 return NULL;
87 }
88
89 /* Initialize the heap header */
90 Heap->MaximumSize = MaximumSize;
91 Heap->CurrentAllocBytes = 0;
92 Heap->MaxAllocBytes = 0;
93 Heap->NumAllocs = 0;
94 Heap->NumFrees = 0;
95 Heap->LargestAllocation = 0;
96
97 /* Calculate what's left to process */
98 Remaining = (MaximumSize - sizeof(HEAP)) / sizeof(HEAP_BLOCK);
99 TRACE("Remaining = %ld\n", Remaining);
100
101 /* Substract 2 for the terminating entry (header + free entry) */
102 Remaining -= 2;
103
104 Block = &Heap->Blocks;
105 PreviousSize = 0;
106
107 /* Create free blocks */
108 while (Remaining > 1)
109 {
110 /* Initialize this free block */
111 Block->Size = (USHORT)min(MAXUSHORT, Remaining - 1);
112 Block->PreviousSize = PreviousSize;
113 Block->Tag = 0;
114 Block->Data[0].Flink = (Block - &Heap->Blocks) + Block->Size + 1;
115 Block->Data[0].Blink = (Block - &Heap->Blocks) - 1 - PreviousSize;
116
117 /* Substract current block size from remainder */
118 Remaining -= (Block->Size + 1);
119
120 /* Go to next block */
121 PreviousSize = Block->Size;
122 Block = Block + Block->Size + 1;
123
124 TRACE("Remaining = %ld\n", Remaining);
125 }
126
127 /* Now finish with a terminating block */
128 Heap->TerminatingBlock = Block - &Heap->Blocks;
129 Block->Size = 0;
130 Block->PreviousSize = PreviousSize;
131 Block->Tag = 'dnE#';
132 Block->Data[0].Flink = 0;
133 Block->Data[0].Blink = (Block - &Heap->Blocks) - 1 - PreviousSize;
134 Heap->Blocks.Data[0].Blink = Heap->TerminatingBlock;
135
136 return Heap;
137 }
138
139 VOID
140 FrLdrHeapDestroy(
141 PVOID HeapHandle)
142 {
143 PHEAP Heap = HeapHandle;
144
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);
150 }
151
152 #ifdef FREELDR_HEAP_VERIFIER
153 VOID
154 FrLdrHeapVerify(
155 PVOID HeapHandle)
156 {
157 PHEAP Heap = HeapHandle;
158 PHEAP_BLOCK Block;
159
160 /* Loop all heap chunks */
161 for (Block = &Heap->Blocks;
162 Block->Size != 0;
163 Block = Block + 1 + Block->Size)
164 {
165 /* Continue, if its not free */
166 if (Block->Tag != 0)
167 {
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);
172 continue;
173 }
174 }
175 }
176 #endif /* FREELDR_HEAP_VERIFIER */
177
178 VOID
179 FrLdrHeapRelease(
180 PVOID HeapHandle)
181 {
182 PHEAP Heap = HeapHandle;
183 PHEAP_BLOCK Block;
184 PUCHAR StartAddress, EndAddress;
185 PFN_COUNT FreePages, AllFreePages = 0;
186 TRACE("HeapRelease(%p)\n", HeapHandle);
187
188 /* Loop all heap chunks */
189 for (Block = &Heap->Blocks;
190 Block->Size != 0;
191 Block = Block + 1 + Block->Size)
192 {
193 /* Continue, if its not free */
194 if (Block->Tag != 0)
195 {
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);
201 #endif
202 continue;
203 }
204
205 /* Calculate page aligned start address of the free region */
206 StartAddress = ALIGN_UP_POINTER_BY(Block->Data, PAGE_SIZE);
207
208 /* Walk over adjacent free blocks */
209 while (Block->Tag == 0) Block = Block + Block->Size + 1;
210
211 /* Check if this was the last block */
212 if (Block->Size == 0)
213 {
214 /* Align the end address up to cover the end of the heap */
215 EndAddress = ALIGN_UP_POINTER_BY(Block->Data, PAGE_SIZE);
216 }
217 else
218 {
219 /* Align the end address down to not cover any allocations */
220 EndAddress = ALIGN_DOWN_POINTER_BY(Block->Data, PAGE_SIZE);
221 }
222
223 /* Check if we have free pages */
224 if (EndAddress > StartAddress)
225 {
226 /* Calculate the size of the free region in pages */
227 FreePages = (PFN_COUNT)((EndAddress - StartAddress) / MM_PAGE_SIZE);
228 AllFreePages += FreePages;
229
230 /* Now mark the pages free */
231 MmMarkPagesInLookupTable(PageLookupTableAddress,
232 (ULONG_PTR)StartAddress / MM_PAGE_SIZE,
233 FreePages,
234 LoaderFree);
235 }
236
237 /* bail out, if it was the last block */
238 if (Block->Size == 0) break;
239 }
240
241 TRACE("HeapRelease() done, freed %ld pages\n", AllFreePages);
242 }
243
244 VOID
245 FrLdrHeapCleanupAll(VOID)
246 {
247 PHEAP Heap;
248
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);
257
258
259 /* Release fre pages */
260 FrLdrHeapRelease(FrLdrDefaultHeap);
261
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);
268
269 /* Destroy the heap */
270 FrLdrHeapDestroy(FrLdrTempHeap);
271 }
272
273 static VOID
274 FrLdrHeapRemoveFreeList(
275 PHEAP Heap,
276 PHEAP_BLOCK Block)
277 {
278 PHEAP_BLOCK Previous, Next;
279
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);
286
287 Next->Data[0].Blink = Previous - &Heap->Blocks;
288 Previous->Data[0].Flink = Next - &Heap->Blocks;
289 }
290
291 static VOID
292 FrLdrHeapInsertFreeList(
293 PHEAP Heap,
294 PHEAP_BLOCK FreeBlock)
295 {
296 PHEAP_BLOCK ListHead, NextBlock;
297 ASSERT(FreeBlock->Tag == 0);
298
299 /* Terminating block serves as free list head */
300 ListHead = &Heap->Blocks + Heap->TerminatingBlock;
301
302 for (NextBlock = &Heap->Blocks + ListHead->Data[0].Flink;
303 NextBlock < FreeBlock;
304 NextBlock = &Heap->Blocks + NextBlock->Data[0].Flink);
305
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;
311 }
312
313 PVOID
314 FrLdrHeapAllocate(
315 PVOID HeapHandle,
316 SIZE_T ByteSize,
317 ULONG Tag)
318 {
319 PHEAP Heap = HeapHandle;
320 PHEAP_BLOCK Block, NextBlock;
321 USHORT BlockSize, Remaining;
322 ULONGLONG Time = __rdtsc();
323
324 #ifdef FREELDR_HEAP_VERIFIER
325 /* Verify the heap */
326 FrLdrHeapVerify(HeapHandle);
327
328 /* Add space for a size field and 2 redzones */
329 ByteSize += REDZONE_ALLOCATION;
330 #endif
331
332 /* Check if the allocation is too large */
333 if ((ByteSize + sizeof(HEAP_BLOCK)) > MAXUSHORT * sizeof(HEAP_BLOCK))
334 {
335 ERR("HEAP: Allocation of 0x%lx bytes too large\n", ByteSize);
336 return NULL;
337 }
338
339 /* We need a proper tag */
340 if (Tag == 0) Tag = 'enoN';
341
342 /* Calculate alloc size */
343 BlockSize = (USHORT)((ByteSize + sizeof(HEAP_BLOCK) - 1) / sizeof(HEAP_BLOCK));
344
345 /* Walk the free block list */
346 Block = &Heap->Blocks + Heap->TerminatingBlock;
347 for (Block = &Heap->Blocks + Block->Data[0].Flink;
348 Block->Size != 0;
349 Block = &Heap->Blocks + Block->Data[0].Flink)
350 {
351 ASSERT(Block->Tag == 0);
352
353 /* Continue, if its too small */
354 if (Block->Size < BlockSize) continue;
355
356 /* This block is just fine, use it */
357 Block->Tag = Tag;
358
359 /* Remove this entry from the free list */
360 FrLdrHeapRemoveFreeList(Heap, Block);
361
362 /* Calculate the remaining size */
363 Remaining = Block->Size - BlockSize;
364
365 /* Check if the remaining space is large enough for a new block */
366 if (Remaining > 1)
367 {
368 /* Make the allocated block as large as neccessary */
369 Block->Size = BlockSize;
370
371 /* Get pointer to the new block */
372 NextBlock = Block + 1 + BlockSize;
373
374 /* Make it a free block */
375 NextBlock->Tag = 0;
376 NextBlock->Size = Remaining - 1;
377 NextBlock->PreviousSize = BlockSize;
378 BlockSize = NextBlock->Size;
379 FrLdrHeapInsertFreeList(Heap, NextBlock);
380
381 /* Advance to the next block */
382 NextBlock = NextBlock + 1 + BlockSize;
383 }
384 else
385 {
386 /* Not enough left, use the full block */
387 BlockSize = Block->Size;
388
389 /* Get the next block */
390 NextBlock = Block + 1 + BlockSize;
391 }
392
393 /* Update the next blocks back link */
394 NextBlock->PreviousSize = BlockSize;
395
396 /* Update heap usage */
397 Heap->NumAllocs++;
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);
403
404 TRACE("HeapAllocate(%p, %ld, %.4s) -> return %p\n",
405 HeapHandle, ByteSize, &Tag, Block->Data);
406
407 /* HACK: zero out the allocation */
408 RtlZeroMemory(Block->Data, Block->Size * sizeof(HEAP_BLOCK));
409
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;
415
416 /* Allcoation starts after size field and redzone */
417 return (PUCHAR)Block->Data + REDZONE_LOW_OFFSET;
418 #endif
419 /* Return pointer to the data */
420 return Block->Data;
421 }
422
423 /* We found nothing */
424 WARN("HEAP: nothing suitable found for 0x%lx bytes\n", ByteSize);
425 return NULL;
426 }
427
428 VOID
429 FrLdrHeapFree(
430 PVOID HeapHandle,
431 PVOID Pointer,
432 ULONG Tag)
433 {
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#');
439
440 #ifdef FREELDR_HEAP_VERIFIER
441 /* Verify the heap */
442 FrLdrHeapVerify(HeapHandle);
443 #endif
444
445 /* Check if the block is really inside this heap */
446 if ((Pointer < (PVOID)(Heap + 1)) ||
447 (Pointer > (PVOID)((PUCHAR)Heap + Heap->MaximumSize)))
448 {
449 ERR("HEAP: trying to free %p outside of heap %p\n", Pointer, Heap);
450 ASSERT(FALSE);
451 }
452
453 Block = ((PHEAP_BLOCK)Pointer) - 1;
454 #ifdef FREELDR_HEAP_VERIFIER
455 Block = (PHEAP_BLOCK)((PUCHAR)Block - REDZONE_LOW_OFFSET);
456
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);
461 #endif
462
463 /* Check if the tag matches */
464 if ((Tag && (Block->Tag != Tag)) || (Block->Tag == 0))
465 {
466 ERR("HEAP: Bad tag! Pointer=%p: block tag '%.4s', requested '%.4s', size=0x%lx\n",
467 Pointer, &Block->Tag, &Tag, Block->Size);
468 ASSERT(FALSE);
469 }
470
471 /* Mark as free */
472 Block->Tag = 0;
473
474 /* Update heap usage */
475 Heap->NumFrees++;
476 Heap->CurrentAllocBytes -= Block->Size * sizeof(HEAP_BLOCK);
477
478 /* Get pointers to the next and previous block */
479 PrevBlock = Block - Block->PreviousSize - 1;
480 NextBlock = Block + Block->Size + 1;
481
482 /* Check if next block is free */
483 if ((NextBlock->Tag == 0) &&
484 ((Block->Size + NextBlock->Size + 1) <= MAXUSHORT))
485 {
486 /* Merge next block into current */
487 Block->Size += NextBlock->Size + 1;
488 FrLdrHeapRemoveFreeList(Heap, NextBlock);
489
490 NextBlock = Block + Block->Size + 1;
491 }
492
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))
496 {
497 /* Merge current block into previous */
498 PrevBlock->Size += Block->Size + 1;
499 Block = PrevBlock;
500 }
501 else
502 {
503 /* Insert the entry into the free list */
504 FrLdrHeapInsertFreeList(Heap, Block);
505 }
506
507 /* Update the next block's back link */
508 NextBlock->PreviousSize = Block->Size;
509
510 Heap->FreeTime += (__rdtsc() - Time);
511 }
512
513
514 /* Wrapper functions *********************************************************/
515
516 VOID
517 MmInitializeHeap(PVOID PageLookupTable)
518 {
519 TRACE("MmInitializeHeap()\n");
520
521 /* Create the default heap */
522 FrLdrDefaultHeap = FrLdrHeapCreate(DEFAULT_HEAP_SIZE, LoaderOsloaderHeap);
523 ASSERT(FrLdrDefaultHeap);
524
525 /* Create a temporary heap */
526 FrLdrTempHeap = FrLdrHeapCreate(TEMP_HEAP_SIZE, LoaderFirmwareTemporary);
527 ASSERT(FrLdrTempHeap);
528
529 TRACE("MmInitializeHeap() done, default heap %p, temp heap %p\n",
530 FrLdrDefaultHeap, FrLdrTempHeap);
531 }
532
533 PVOID
534 MmHeapAlloc(SIZE_T MemorySize)
535 {
536 return FrLdrHeapAllocate(FrLdrDefaultHeap, MemorySize, 'pHmM');
537 }
538
539 VOID
540 MmHeapFree(PVOID MemoryPointer)
541 {
542 FrLdrHeapFree(FrLdrDefaultHeap, MemoryPointer, 'pHmM');
543 }
544
545 PVOID
546 NTAPI
547 ExAllocatePoolWithTag(
548 IN POOL_TYPE PoolType,
549 IN SIZE_T NumberOfBytes,
550 IN ULONG Tag)
551 {
552 return FrLdrHeapAllocate(FrLdrDefaultHeap, NumberOfBytes, Tag);
553 }
554
555 PVOID
556 NTAPI
557 ExAllocatePool(
558 IN POOL_TYPE PoolType,
559 IN SIZE_T NumberOfBytes)
560 {
561 return FrLdrHeapAllocate(FrLdrDefaultHeap, NumberOfBytes, 0);
562 }
563
564 VOID
565 NTAPI
566 ExFreePool(
567 IN PVOID P)
568 {
569 FrLdrHeapFree(FrLdrDefaultHeap, P, 0);
570 }
571
572 VOID
573 NTAPI
574 ExFreePoolWithTag(
575 IN PVOID P,
576 IN ULONG Tag)
577 {
578 FrLdrHeapFree(FrLdrDefaultHeap, P, Tag);
579 }
580
581 PVOID
582 NTAPI
583 RtlAllocateHeap(
584 IN PVOID HeapHandle,
585 IN ULONG Flags,
586 IN SIZE_T Size)
587 {
588 PVOID ptr;
589
590 ptr = FrLdrHeapAllocate(FrLdrDefaultHeap, Size, ' ltR');
591 if (ptr && (Flags & HEAP_ZERO_MEMORY))
592 {
593 RtlZeroMemory(ptr, Size);
594 }
595
596 return ptr;
597 }
598
599 BOOLEAN
600 NTAPI
601 RtlFreeHeap(
602 IN PVOID HeapHandle,
603 IN ULONG Flags,
604 IN PVOID HeapBase)
605 {
606 FrLdrHeapFree(FrLdrDefaultHeap, HeapBase, ' ltR');
607 return TRUE;
608 }