ReactOS 0.4.15-dev-7660-g0086d05
heapalloc.c File Reference
#include "bl.h"
Include dependency graph for heapalloc.c:

Go to the source code of this file.

Classes

struct  _BL_HEAP_POINTER
 
struct  _BL_FREE_HEAP_ENTRY
 
struct  _BL_BUSY_HEAP_ENTRY
 
struct  _BL_HEAP_BOUNDARIES
 

Macros

#define BL_HEAP_POINTER_FLAG_BITS   3
 

Typedefs

typedef struct _BL_HEAP_POINTER BL_HEAP_POINTER
 
typedef struct _BL_HEAP_POINTERPBL_HEAP_POINTER
 
typedef struct _BL_FREE_HEAP_ENTRY BL_FREE_HEAP_ENTRY
 
typedef struct _BL_FREE_HEAP_ENTRYPBL_FREE_HEAP_ENTRY
 
typedef struct _BL_BUSY_HEAP_ENTRY BL_BUSY_HEAP_ENTRY
 
typedef struct _BL_BUSY_HEAP_ENTRYPBL_BUSY_HEAP_ENTRY
 
typedef struct _BL_HEAP_BOUNDARIES BL_HEAP_BOUNDARIES
 
typedef struct _BL_HEAP_BOUNDARIESPBL_HEAP_BOUNDARIES
 

Functions

FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink (_In_ BL_HEAP_POINTER Link)
 
FORCEINLINE ULONG MmHapBufferSize (_In_ PVOID FreeEntry)
 
FORCEINLINE ULONG MmHapUserBufferSize (_In_ PVOID FreeEntry)
 
NTSTATUS MmHapHeapAllocatorExtend (_In_ ULONG ExtendSize)
 
ULONG MmHapGetBucketId (_In_ ULONG Size)
 
VOID MmHapReportHeapCorruption (_In_ PBL_FREE_HEAP_ENTRY BufferEntry)
 
PVOID MmHapCheckFreeLinks (_In_ PVOID BufferEntry)
 
PVOID MmHapCheckBufferLinks (_In_ PVOID BufferEntry)
 
PBL_FREE_HEAP_ENTRY MmHapRemoveBufferFromFreeList (_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
 
PBL_FREE_HEAP_ENTRY MmHapCoalesceFreeBuffer (_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
 
PBL_FREE_HEAP_ENTRY MmHapAddToFreeList (_In_ PBL_BUSY_HEAP_ENTRY Entry, _In_ ULONG Flags)
 
PBL_BUSY_HEAP_ENTRY MmHapFindBufferInFreeList (_In_ ULONG Size)
 
NTSTATUS MmHaInitialize (_In_ ULONG HeapSize, _In_ ULONG HeapAttributes)
 
PVOID BlMmAllocateHeap (_In_ SIZE_T Size)
 
NTSTATUS BlMmFreeHeap (_In_ PVOID Buffer)
 

Variables

ULONG HapInitializationStatus
 
LIST_ENTRY MmHeapBoundaries
 
ULONG HapMinimumHeapSize
 
ULONG HapAllocationAttributes
 
PBL_FREE_HEAP_ENTRYMmFreeList
 

Macro Definition Documentation

◆ BL_HEAP_POINTER_FLAG_BITS

#define BL_HEAP_POINTER_FLAG_BITS   3

Definition at line 15 of file heapalloc.c.

Typedef Documentation

◆ BL_BUSY_HEAP_ENTRY

◆ BL_FREE_HEAP_ENTRY

◆ BL_HEAP_BOUNDARIES

◆ BL_HEAP_POINTER

◆ PBL_BUSY_HEAP_ENTRY

◆ PBL_FREE_HEAP_ENTRY

◆ PBL_HEAP_BOUNDARIES

◆ PBL_HEAP_POINTER

Function Documentation

◆ BlMmAllocateHeap()

PVOID BlMmAllocateHeap ( _In_ SIZE_T  Size)

Definition at line 569 of file heapalloc.c.

572{
575 PBL_BUSY_HEAP_ENTRY BusyEntry, FreeEntry, NextEntry;
576
577 /* Ignore heap allocation if the heap allocator isn't ready yet */
579 {
580 return NULL;
581 }
582
583 /* Align the buffer size to the minimum size required */
586
587 /* Watch out for overflow */
588 if (BufferSize <= Size)
589 {
590 return NULL;
591 }
592
593 /* Make sure it's at least big enough to hold a free entry later on */
594 if (BufferSize < sizeof(BL_FREE_HEAP_ENTRY))
595 {
597 }
598
599 /* Loop while we try to allocate memory */
600 while (1)
601 {
602 /* Find a free buffer for this allocation */
604 if (BusyEntry)
605 {
606 break;
607 }
608
609 /* We couldn't find a free buffer. Do we have any heaps? */
611 {
612 /* Get the current heap */
615 ListEntry);
616
617 /* Check if we have space in the heap page for this allocation? */
618 FreeEntry = Heap->HeapStart;
619 NextEntry = (PBL_BUSY_HEAP_ENTRY)((ULONG_PTR)FreeEntry + BufferSize);
620
621 if ((NextEntry >= FreeEntry) &&
622 ((ULONG_PTR)NextEntry <=
624 {
625 /* Update the heap top pointer past this allocation */
626 Heap->HeapStart = NextEntry;
627
628 /* Make this allocation point to the slot */
629 FreeEntry->BufferNext.P = Heap->HeapStart;
630
631 /* And make the free heap entry point back to us */
632 Heap->HeapStart->BufferPrevious.P = FreeEntry;
633
634 /* Mark the heap entry as being free and on the heap */
637
638 /* The previously freed entry on the heap page is now ours */
639 BusyEntry = FreeEntry;
640 break;
641 }
642 }
643
644 /* We have no heaps or space on any heap -- extend the heap and retry */
646 {
647 EfiPrintf(L"Heap extension failed!\r\n");
648 return NULL;
649 }
650
651 EfiPrintf(L"Heap extended -- trying again\r\n");
652 }
653
654 /* Clear all the bits, marking this entry as allocated */
655 BusyEntry->BufferNext.P = MmHapDecodeLink(BusyEntry->BufferNext);
656
657 /* Return the entry's data buffer */
658 //EfiPrintf(L"Returning buffer at 0x%p\r\n", &BusyEntry->Buffer);
659 return &BusyEntry->Buffer;
660}
#define ALIGN_UP_BY(size, align)
VOID EfiPrintf(_In_ PWCHAR Format,...)
Definition: firmware.c:126
Definition: bufpool.h:45
#define BufferSize
Definition: mmc.h:75
#define NULL
Definition: types.h:112
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define ULONG_PTR
Definition: config.h:101
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
struct _BL_BUSY_HEAP_ENTRY * PBL_BUSY_HEAP_ENTRY
LIST_ENTRY MmHeapBoundaries
Definition: heapalloc.c:57
struct _BL_FREE_HEAP_ENTRY BL_FREE_HEAP_ENTRY
PBL_BUSY_HEAP_ENTRY MmHapFindBufferInFreeList(_In_ ULONG Size)
Definition: heapalloc.c:450
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
NTSTATUS MmHapHeapAllocatorExtend(_In_ ULONG ExtendSize)
Definition: heapalloc.c:102
ULONG HapInitializationStatus
Definition: heapalloc.c:56
#define L(x)
Definition: ntvdm.h:50
Definition: heapalloc.c:41
UCHAR Buffer[ANYSIZE_ARRAY]
Definition: heapalloc.c:44
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:42
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:43
Definition: heapalloc.c:33
PBL_BUSY_HEAP_ENTRY HeapStart
Definition: heapalloc.c:53
ULONG_PTR HeapLimit
Definition: heapalloc.c:51
ULONG_PTR BufferFree
Definition: heapalloc.c:23
ULONG_PTR BufferOnHeap
Definition: heapalloc.c:24
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
_Must_inspect_result_ _In_ WDFDEVICE _In_ PWDF_DEVICE_PROPERTY_DATA _In_ DEVPROPTYPE _In_ ULONG Size
Definition: wdfdevice.h:4533
_In_ WDFMEMORY _Out_opt_ size_t * BufferSize
Definition: wdfmemory.h:254

Referenced by BcdEnumerateAndUnpackElements(), BcdOpenStoreFromFile(), BfLoadFontFile(), BiEnumerateElements(), BiEnumerateSubKeys(), BiGetRegistryValue(), BiLoadHive(), BiOpenKey(), BlAppendBootOptionBoolean(), BlAppendBootOptionInteger(), BlAppendBootOptions(), BlAppendBootOptionString(), BlCopyBootOptions(), BlGetBootOptionDevice(), BlGetBootOptionGuidList(), BlGetBootOptionString(), BlHtCreate(), BlHtStore(), BlImgLoadBootApplication(), BlMmGetMemoryMap(), BlockIoEfiCreateDeviceEntry(), BlockIoOpen(), BlockIopInitialize(), BlpDeviceInitialize(), BlpDeviceOpen(), BlpFileInitialize(), BlpFileRegisterFileSystem(), BlpGetBootOptionIntegerList(), BlpIoInitialize(), BlpMmCreateBlockAllocator(), BlReplaceBootOptions(), BlTblSetEntry(), BmEnumerateBootEntries(), BmFwInitializeBootDirectoryPath(), BmGetBootSequence(), BmGetOptionList(), BmOpenDataStore(), BmpFwGetApplicationDirectoryPath(), BmpFwGetFullPath(), BmpGetSelectedBootEntry(), BmpPopulateBootEntryList(), CmpAllocate(), ConsoleCreateLocalInputConsole(), ConsoleCreateRemoteConsole(), ConsoleEfiTextFindModeFromAllowed(), ConsoleInputBaseConstruct(), ConsolepClearBuffer(), ConvertBmpToGopBlt(), DsppInitialize(), DsppLoadFontFile(), EfiLocateHandleBuffer(), EfiVmOpenProtocol(), EtfsInitialize(), EtfsMount(), EtfsOpen(), EtfspCreateContext(), FatInitialize(), FileIoCopyFileName(), FileIoCopyParentDirectoryPath(), ImgpInitializeBootApplicationParameters(), MmBaInitialize(), MmMdFreeGlobalDescriptors(), OslPrepareTarget(), and RtlpAllocateMemory().

◆ BlMmFreeHeap()

NTSTATUS BlMmFreeHeap ( _In_ PVOID  Buffer)

Definition at line 663 of file heapalloc.c.

666{
667 PBL_BUSY_HEAP_ENTRY BusyEntry;
669 PLIST_ENTRY NextEntry;
670
671 /* If the heap is not initialized, fail */
673 {
674 return STATUS_UNSUCCESSFUL;
675 }
676
677 /* Get the heap header */
678 //EfiPrintf(L"Freeing entry at: %p\r\n", Buffer);
679 if (Buffer)
680 {
681 /* Don't free heap until we discover the corruption */
682 return STATUS_SUCCESS;
683 }
684
686
687 /* Loop all the heaps */
688 NextEntry = MmHeapBoundaries.Flink;
689 while (NextEntry != &MmHeapBoundaries)
690 {
691 /* Get the current heap in the list */
692 Heap = CONTAINING_RECORD(NextEntry, BL_HEAP_BOUNDARIES, ListEntry);
693
694 /* Is this entry part of this heap? */
695 if (((ULONG_PTR)Heap->HeapBase <= (ULONG_PTR)BusyEntry) &&
696 ((ULONG_PTR)BusyEntry < (ULONG_PTR)Heap->HeapStart))
697 {
698 /* Ignore double-free */
699 if (BusyEntry->BufferNext.BufferFree)
700 {
702 }
703
704 /* It is -- add it to the free list */
705 MmHapAddToFreeList(BusyEntry, 0);
706 return STATUS_SUCCESS;
707 }
708
709 /* It isn't, move to the next heap */
710 NextEntry = NextEntry->Flink;
711 }
712
713 /* The entry is not on any valid heap */
715}
PBL_FREE_HEAP_ENTRY MmHapAddToFreeList(_In_ PBL_BUSY_HEAP_ENTRY Entry, _In_ ULONG Flags)
Definition: heapalloc.c:393
#define STATUS_SUCCESS
Definition: shellext.h:65
ULONG_PTR HeapBase
Definition: heapalloc.c:52
Definition: typedefs.h:120
#define STATUS_INVALID_PARAMETER
Definition: udferr_usr.h:135
#define STATUS_UNSUCCESSFUL
Definition: udferr_usr.h:132

Referenced by BcdEnumerateAndUnpackElements(), BcdOpenStoreFromFile(), BfiFreeDeferredFontFile(), BiCloseKey(), BiDeleteKey(), BiEnumerateElements(), BiEnumerateSubKeys(), BiGetObjectDescription(), BiLoadHive(), BiOpenKey(), BlAppendBootOptionBoolean(), BlAppendBootOptionInteger(), BlAppendBootOptions(), BlAppendBootOptionString(), BlDestroyBootEntry(), BlFwEnumerateDevice(), BlGetBootOptionDevice(), BlHtCreate(), BlHtDelete(), BlImgLoadBootApplication(), BlImgUnloadBootApplication(), BlMmGetMemoryMap(), BlockIoDeviceTableDestroy(), BlockIoDeviceTableDestroyEntry(), BlockIoEfiCompareDevice(), BlockIoEfiCreateDeviceEntry(), BlockIoEfiGetChildHandle(), BlockIoFirmwareOpen(), BlockIopDestroy(), BlockIopFreeAllocations(), BlpDeviceOpen(), BlpFileRegisterFileSystem(), BlpMmCreateBlockAllocator(), BlpResourceInitialize(), BlReplaceBootOptions(), BlTblSetEntry(), BmEnumerateBootEntries(), BmErrorPurge(), BmFwInitializeBootDirectoryPath(), BmGetBootSequence(), BmGetOptionList(), BmLaunchRecoverySequence(), BmMain(), BmOpenDataStore(), BmpFwGetApplicationDirectoryPath(), BmpGetSelectedBootEntry(), BmpInitializeBootStatusDataLog(), BmpPopulateBootEntryList(), BmpTransferExecution(), BmpUpdateApplicationOptions(), CmpFree(), ConsoleCreateLocalInputConsole(), ConsoleCreateRemoteConsole(), ConsoleEfiTextFindModeFromAllowed(), ConsoleInputLocalDestruct(), DeviceTableDestroyEntry(), DsppInitialize(), DsppLoadFontFile(), EfiLocateHandleBuffer(), EfiVmOpenProtocol(), EfiVmpFreeInterfaceEntry(), EtfsMount(), EtfsOpen(), EtfspDeviceContextDestroy(), FileIoCopyParentDirectoryPath(), FileIoOpen(), FileTableDestroyEntry(), ImgpInitializeBootApplicationParameters(), MmBapFreeBlockAllocatorTableEntry(), MmMdFreeDescriptor(), OslpRemoveInternalApplicationOptions(), OslPrepareTarget(), and RtlpFreeMemory().

◆ MmHaInitialize()

NTSTATUS MmHaInitialize ( _In_ ULONG  HeapSize,
_In_ ULONG  HeapAttributes 
)

Definition at line 538 of file heapalloc.c.

542{
544
545 /* No free list to begin with */
547
548 /* Configure the minimum heap size and allocation attributes */
550 HapAllocationAttributes = HeapAttributes & 0x20000;
551
552 /* Initialize the heap boundary list */
554
555 /* Initialize a heap big enough to handle a one pointer long allocation */
557 if (NT_SUCCESS(Status))
558 {
559 /* The heap is ready! */
562 }
563
564 /* Return initialization status */
565 return Status;
566}
LONG NTSTATUS
Definition: precomp.h:26
#define PAGE_SIZE
Definition: env_spec_w32.h:49
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
Status
Definition: gdiplustypes.h:25
ULONG HapMinimumHeapSize
Definition: heapalloc.c:58
ULONG HapAllocationAttributes
Definition: heapalloc.c:59
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
SIZE_T WINAPI HeapSize(HANDLE, DWORD, LPCVOID)

Referenced by BlpMmInitialize().

◆ MmHapAddToFreeList()

PBL_FREE_HEAP_ENTRY MmHapAddToFreeList ( _In_ PBL_BUSY_HEAP_ENTRY  Entry,
_In_ ULONG  Flags 
)

Definition at line 393 of file heapalloc.c.

397{
398 PBL_FREE_HEAP_ENTRY FreeEntry, Head;
399 ULONG BucketId;
400 BL_LIBRARY_PARAMETERS LocalParameters;
401
402 /* First, check if the entry is valid */
404 if (!Entry)
405 {
406 return NULL;
407 }
408
409 /* Check if we should zero the entry */
410 LocalParameters = BlpLibraryParameters;
412 !(Flags))
413 {
414 /* Yep, zero it out */
416 }
417
418 /* Now mark the entry as free */
419 Entry->BufferNext.BufferFree = 1;
420
421 /* Now that this buffer is free, try to coalesce it */
423 if (!FreeEntry)
424 {
425 return FreeEntry;
426 }
427
428 /* Compute the bucket ID for the free list */
430
431 /* Get the current head for this bucket, if one exists */
432 Head = MmFreeList ? MmFreeList[BucketId] : NULL;
433
434 /* Update the head's backlink to point to this newly freed entry */
435 if (Head)
436 {
437 Head->FreePrevious.P = FreeEntry;
438 }
439
440 /* Nobody behind us, the old head in front of us */
441 FreeEntry->FreePrevious.P = NULL;
442 FreeEntry->FreeNext.P = Head;
443
444 /* Put us at the head of list now, and return the entry */
445 MmFreeList[BucketId] = FreeEntry;
446 return FreeEntry;
447}
BL_LIBRARY_PARAMETERS BlpLibraryParameters
Definition: bootlib.c:15
#define BL_LIBRARY_FLAG_ZERO_HEAP_ALLOCATIONS_ON_FREE
Definition: bl.h:130
PVOID MmHapCheckBufferLinks(_In_ PVOID BufferEntry)
Definition: heapalloc.c:268
FORCEINLINE ULONG MmHapUserBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:88
PBL_FREE_HEAP_ENTRY MmHapCoalesceFreeBuffer(_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
Definition: heapalloc.c:333
ULONG MmHapGetBucketId(_In_ ULONG Size)
Definition: heapalloc.c:199
FORCEINLINE ULONG MmHapBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:76
base of all file and directory entries
Definition: entries.h:83
BL_HEAP_POINTER FreeNext
Definition: heapalloc.c:36
BL_HEAP_POINTER FreePrevious
Definition: heapalloc.c:37
ULONG LibraryFlags
Definition: bl.h:757
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170

Referenced by BlMmFreeHeap(), and MmHapFindBufferInFreeList().

◆ MmHapBufferSize()

FORCEINLINE ULONG MmHapBufferSize ( _In_ PVOID  FreeEntry)

Definition at line 76 of file heapalloc.c.

79{
80 PBL_FREE_HEAP_ENTRY Entry = FreeEntry;
81
82 /* The space between the next buffer header and this one is the size */
83 return (ULONG_PTR)MmHapDecodeLink(Entry->BufferNext) - (ULONG_PTR)Entry;
84}

Referenced by MmHapAddToFreeList(), MmHapFindBufferInFreeList(), MmHapRemoveBufferFromFreeList(), and MmHapUserBufferSize().

◆ MmHapCheckBufferLinks()

PVOID MmHapCheckBufferLinks ( _In_ PVOID  BufferEntry)

Definition at line 268 of file heapalloc.c.

271{
272 PBL_FREE_HEAP_ENTRY Prev, Next;
273 PBL_FREE_HEAP_ENTRY Entry = BufferEntry;
274
275 /* Get the previous and next buffer pointers */
276 Prev = MmHapDecodeLink(Entry->BufferPrevious);
277 Next = MmHapDecodeLink(Entry->BufferNext);
278
279 /* Make sure that both the previous and next entries point to this one */
280 if (((Next) && (MmHapDecodeLink(Next->BufferPrevious)) != Entry) ||
281 ((Prev) && (MmHapDecodeLink(Prev->BufferNext)) != Entry))
282 {
283 /* They don't, so the heap headers are corrupted */
285 return NULL;
286 }
287
288 /* They, do the entry is valid */
289 return Entry;
290}
VOID MmHapReportHeapCorruption(_In_ PBL_FREE_HEAP_ENTRY BufferEntry)
Definition: heapalloc.c:222
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:35
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:34

Referenced by MmHapAddToFreeList(), MmHapCoalesceFreeBuffer(), and MmHapFindBufferInFreeList().

◆ MmHapCheckFreeLinks()

PVOID MmHapCheckFreeLinks ( _In_ PVOID  BufferEntry)

Definition at line 243 of file heapalloc.c.

246{
247 PBL_FREE_HEAP_ENTRY Prev, Next;
248 PBL_FREE_HEAP_ENTRY Entry = BufferEntry;
249
250 /* Get the previous and next free pointers */
251 Prev = MmHapDecodeLink(Entry->FreePrevious);
252 Next = MmHapDecodeLink(Entry->FreeNext);
253
254 /* Make sure that both the previous and next entries point to this one */
255 if (((Next) && (MmHapDecodeLink(Next->FreePrevious)) != Entry) ||
256 ((Prev) && (MmHapDecodeLink(Prev->FreeNext)) != Entry))
257 {
258 /* They don't, so the free headers are corrupted */
260 return NULL;
261 }
262
263 /* They do, return the free entry as valid */
264 return Entry;
265}

Referenced by MmHapRemoveBufferFromFreeList().

◆ MmHapCoalesceFreeBuffer()

PBL_FREE_HEAP_ENTRY MmHapCoalesceFreeBuffer ( _In_ PBL_FREE_HEAP_ENTRY  FreeEntry)

Definition at line 333 of file heapalloc.c.

336{
337 PBL_FREE_HEAP_ENTRY Prev, Next;
338
339 /* First make sure that this is a valid buffer entry */
340 if (!MmHapCheckBufferLinks(FreeEntry))
341 {
342 return NULL;
343 }
344
345 /* Get the next entry and check if it's free */
346 Next = MmHapDecodeLink(FreeEntry->BufferNext);
347 if (!(Next->BufferNext.BufferOnHeap) && (Next->BufferNext.BufferFree))
348 {
349 /* Remove the next buffer from the free list since we're coalescing */
351 if (!Next)
352 {
353 return NULL;
354 }
355
356 /* The forward link of the *new* free buffer should now point to us */
357 MmHapDecodeLink(Next->BufferNext)->BufferPrevious.P = FreeEntry;
358
359 /* Our forward link should point to the *new* free buffer as well */
360 FreeEntry->BufferNext.P = MmHapDecodeLink(Next->BufferNext);
361
362 /* Mark our buffer as free */
363 FreeEntry->BufferNext.BufferFree = 1;
364 }
365
366 /* Get the previous entry and check if it's free */
367 Prev = MmHapDecodeLink(FreeEntry->BufferPrevious);
368 if (!(Prev) || !(Prev->BufferNext.BufferFree))
369 {
370 return FreeEntry;
371 }
372
373 /* It's free, so remove it */
375 if (!Prev)
376 {
377 return NULL;
378 }
379
380 /* The previous link of our next buffer should now point to our *previous* */
381 MmHapDecodeLink(FreeEntry->BufferNext)->BufferPrevious.P = Prev;
382
383 /* Our previous link should point the next free buffer now */
384 Prev->BufferNext.P = MmHapDecodeLink(FreeEntry->BufferNext);
385
386 /* Set the new freed buffer as the previous buffer, and mark it free */
387 FreeEntry = Prev;
388 FreeEntry->BufferNext.BufferFree = 1;
389 return FreeEntry;
390}
PBL_FREE_HEAP_ENTRY MmHapRemoveBufferFromFreeList(_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
Definition: heapalloc.c:293

Referenced by MmHapAddToFreeList().

◆ MmHapDecodeLink()

Definition at line 66 of file heapalloc.c.

69{
70 /* Decode the buffer pointer by ignoring the flags */
71 return (PBL_FREE_HEAP_ENTRY)(Link.BufferPointer << BL_HEAP_POINTER_FLAG_BITS);
72}
#define BL_HEAP_POINTER_FLAG_BITS
Definition: heapalloc.c:15
static int Link(const char **args)
Definition: vfdcmd.c:2414

Referenced by BlMmAllocateHeap(), MmHapBufferSize(), MmHapCheckBufferLinks(), MmHapCheckFreeLinks(), MmHapCoalesceFreeBuffer(), MmHapFindBufferInFreeList(), and MmHapRemoveBufferFromFreeList().

◆ MmHapFindBufferInFreeList()

PBL_BUSY_HEAP_ENTRY MmHapFindBufferInFreeList ( _In_ ULONG  Size)

Definition at line 450 of file heapalloc.c.

453{
454 PBL_FREE_HEAP_ENTRY FreeEntry = NULL;
455 PBL_BUSY_HEAP_ENTRY NextEntry;
456 ULONG BucketId;
457
458 /* Get the appropriate bucket for our size */
459 BucketId = MmHapGetBucketId(Size);
460 if (BucketId >= 8)
461 {
462 return NULL;
463 }
464
465 /* Keep going as long as we don't have a free entry */
466 while (!FreeEntry)
467 {
468 /* Fet the first free entry in this list */
469 FreeEntry = MmFreeList ? MmFreeList[BucketId] : NULL;
470
471 /* Loop as long as there's entries in the list */
472 while (FreeEntry)
473 {
474 /* Can this free entry satisfy our needs? */
475 if (MmHapBufferSize(FreeEntry) >= Size)
476 {
477 /* All good */
478 break;
479 }
480
481 /* It cannot, keep going to the next one */
482 FreeEntry = MmHapDecodeLink(FreeEntry->FreeNext);
483 }
484
485 /* Try the next list -- have we exhausted all the lists? */
486 if (++BucketId >= 8)
487 {
488 /* Have we not found an entry yet? Fail if so... */
489 if (!FreeEntry)
490 {
491 return NULL;
492 }
493 }
494 }
495
496 /* We should have an entry if we're here. Remove it from the free list */
497 NT_ASSERT(FreeEntry != NULL);
498 FreeEntry = MmHapRemoveBufferFromFreeList(FreeEntry);
499 if (!FreeEntry)
500 {
501 return NULL;
502 }
503
504 /* Make sure it's not corrupted */
505 FreeEntry = MmHapCheckBufferLinks(FreeEntry);
506 if (!FreeEntry)
507 {
508 return NULL;
509 }
510
511 /* Do we have space for at least another buffer? */
512 if ((MmHapBufferSize(FreeEntry) - Size) >= sizeof(BL_FREE_HEAP_ENTRY))
513 {
514 /* Go to where the new next buffer will start */
515 NextEntry = (PBL_BUSY_HEAP_ENTRY)((ULONG_PTR)FreeEntry + Size);
516
517 /* Make the new next buffer point to the next buffer */
518 NextEntry->BufferNext.P = MmHapDecodeLink(FreeEntry->BufferNext);
519
520 /* Make the old next buffer point back to the new one */
521 MmHapDecodeLink(FreeEntry->BufferNext)->BufferPrevious.P = NextEntry;
522
523 /* Point the new next buffer point back to us */
524 NextEntry->BufferPrevious.P = FreeEntry;
525
526 /* Point us to the new next buffer */
527 FreeEntry->BufferNext.P = NextEntry;
528
529 /* And insert the new next buffer into the free list */
530 MmHapAddToFreeList(NextEntry, 1);
531 }
532
533 /* Return the entry, which is now allocated */
534 return (PBL_BUSY_HEAP_ENTRY)FreeEntry;
535}
#define NT_ASSERT
Definition: rtlfuncs.h:3310

Referenced by BlMmAllocateHeap().

◆ MmHapGetBucketId()

ULONG MmHapGetBucketId ( _In_ ULONG  Size)

Definition at line 199 of file heapalloc.c.

202{
203 ULONG BucketIndex = 0;
204
205 /* Use the last bucket if this is a large allocation */
206 if (Size >= PAGE_SIZE)
207 {
208 return 7;
209 }
210
211 /* Otherwise, use a higher index for each new power of two */
212 while (Size >> BucketIndex)
213 {
214 BucketIndex++;
215 }
216
217 /* Allocations are at least 16 bytes (2^4 = 5th index) */
218 return BucketIndex - 5;
219}

Referenced by MmHapAddToFreeList(), MmHapFindBufferInFreeList(), and MmHapRemoveBufferFromFreeList().

◆ MmHapHeapAllocatorExtend()

NTSTATUS MmHapHeapAllocatorExtend ( _In_ ULONG  ExtendSize)

Definition at line 102 of file heapalloc.c.

105{
106 ULONG HeapSize, AlignedSize, HeapLimit;
107 PBL_HEAP_BOUNDARIES Heap, NewHeap;
110
111 /* Compute a new heap, and add 2 more pages for the free list */
112 HeapSize = ExtendSize + (2 * PAGE_SIZE);
113 if (HeapSize < ExtendSize)
114 {
116 }
117
118 /* Make sure the new heap is at least the minimum configured size */
120 {
122 }
123
124 /* Align it on a page boundary */
125 AlignedSize = ALIGN_UP_BY(HeapSize, PAGE_SIZE);
126 if (!AlignedSize)
127 {
129 }
130
131 /* Check if we already have a heap */
133 {
134 /* Find the first heap*/
137 ListEntry);
138
139 /* Check if we have a page free above the heap */
140 HeapLimit = Heap->HeapLimit + PAGE_SIZE;
141 if (HeapLimit <= Heap->HeapEnd)
142 {
143 EfiPrintf(L"Heap extension TODO\r\n");
145 }
146 }
147
148 /* We do not -- allocate one */
151 AlignedSize >> PAGE_SHIFT,
153 0,
154 NULL,
155 0);
156 if (!NT_SUCCESS(Status))
157 {
158 EfiPrintf(L"HEAP ALLOCATION FAILED\r\n");
159 EfiStall(1000000);
160 return Status;
161 }
162
163 /* Set the heap bottom, limit, and top */
164 NewHeap = (PBL_HEAP_BOUNDARIES)HeapBase->Buffer;
165 NewHeap->HeapBase = (ULONG_PTR)HeapBase;
166 NewHeap->HeapLimit = (ULONG_PTR)HeapBase + AlignedSize;
167 NewHeap->HeapStart = (PBL_BUSY_HEAP_ENTRY)(NewHeap + 1);
168
169 /* Set the buffer links */
170 HeapBase->BufferPrevious.P = NULL;
171 HeapBase->BufferNext.P = NewHeap->HeapStart;
172
173 /* Set the buffer at the top of the heap and mark it as being free */
175 NewHeap->HeapStart->BufferNext.P = NewHeap->HeapStart;
176 NewHeap->HeapStart->BufferNext.BufferFree = 1;
177 NewHeap->HeapStart->BufferNext.BufferOnHeap = 1;
178
179 /* Is this the first heap ever? */
181 {
182 /* We will host the free list at the top of the heap */
184 NewHeap->HeapLimit = (ULONG_PTR)MmFreeList;
186 }
187
188 /* Remove a page on top */
189 HeapLimit = NewHeap->HeapLimit;
190 NewHeap->HeapEnd = NewHeap->HeapLimit;
191 NewHeap->HeapLimit -= PAGE_SIZE;
192
193 /* Add us into the heap list */
195 return STATUS_SUCCESS;
196}
@ BlLoaderHeap
Definition: bl.h:308
NTSTATUS MmPapAllocatePagesInRange(_Inout_ PVOID *PhysicalAddress, _In_ BL_MEMORY_TYPE MemoryType, _In_ ULONGLONG Pages, _In_ ULONG Attributes, _In_ ULONG Alignment, _In_opt_ PBL_ADDRESS_RANGE Range, _In_ ULONG Type)
Definition: pagealloc.c:707
NTSTATUS EfiStall(_In_ ULONG StallTime)
Definition: firmware.c:1003
#define InsertTailList(ListHead, Entry)
#define PAGE_SHIFT
Definition: env_spec_w32.h:45
struct _BL_HEAP_BOUNDARIES * PBL_HEAP_BOUNDARIES
struct _BL_FREE_HEAP_ENTRY * PBL_FREE_HEAP_ENTRY
#define STATUS_INTEGER_OVERFLOW
Definition: ntstatus.h:385
ULONG_PTR HeapEnd
Definition: heapalloc.c:50
LIST_ENTRY ListEntry
Definition: heapalloc.c:49
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
_In_opt_ PVOID HeapBase
Definition: rtlfuncs.h:2167

Referenced by BlMmAllocateHeap(), and MmHaInitialize().

◆ MmHapRemoveBufferFromFreeList()

PBL_FREE_HEAP_ENTRY MmHapRemoveBufferFromFreeList ( _In_ PBL_FREE_HEAP_ENTRY  FreeEntry)

Definition at line 293 of file heapalloc.c.

296{
297 PBL_FREE_HEAP_ENTRY Prev, Next;
298
299 /* Firest, make sure the free entry is valid */
300 FreeEntry = MmHapCheckFreeLinks(FreeEntry);
301 if (!FreeEntry)
302 {
303 return FreeEntry;
304 }
305
306 /* Get the previous and next entry */
307 Prev = MmHapDecodeLink(FreeEntry->FreePrevious);
308 Next = MmHapDecodeLink(FreeEntry->FreeNext);
309
310 /* Update the next entry to point to our previous entry */
311 if (Next)
312 {
313 Next->FreePrevious.P = Prev;
314 }
315
316 /* Are we at the head? */
317 if (Prev)
318 {
319 /* Nope, so update our previous entry to point to our next entry */
320 Prev->FreeNext.P = Next;
321 }
322 else
323 {
324 /* Yep, so update the appropriate bucket listhead */
325 MmFreeList[MmHapGetBucketId(MmHapBufferSize(FreeEntry))] = Prev;
326 }
327
328 /* Return the (now removed) entry */
329 return FreeEntry;
330}
PVOID MmHapCheckFreeLinks(_In_ PVOID BufferEntry)
Definition: heapalloc.c:243

Referenced by MmHapCoalesceFreeBuffer(), and MmHapFindBufferInFreeList().

◆ MmHapReportHeapCorruption()

VOID MmHapReportHeapCorruption ( _In_ PBL_FREE_HEAP_ENTRY  BufferEntry)

Definition at line 222 of file heapalloc.c.

225{
226#if 0
227 BOOLEAN DebuggerEnabled;
228
229 BlStatusPrint(L"Heap corruption in the links surrounding %p!\r\n", BufferEntry);
230
231 DebuggerEnabled = BlBdDebuggerEnabled();
232 if (DebuggerEnabled)
233 {
234 BlStatusPrint(L"\n*** Fatal Error 0x%08x :\n (0x%p, 0x%p, 0x%p, 0x%p)\n\r\n", 2, BufferEntry, NULL, NULL, NULL);
235 __debugbreak();
236 }
237#else
238 EfiPrintf(L"Heap corruption in the links surrounding %p!\r\n", BufferEntry);
239#endif
240}
unsigned char BOOLEAN
BOOLEAN BlBdDebuggerEnabled(VOID)
Definition: debug.c:53
VOID BlStatusPrint(_In_ PCWCH Format,...)
Definition: debug.c:75
void __cdecl __debugbreak(void)
Definition: intrin_ppc.h:698

Referenced by MmHapCheckBufferLinks(), and MmHapCheckFreeLinks().

◆ MmHapUserBufferSize()

FORCEINLINE ULONG MmHapUserBufferSize ( _In_ PVOID  FreeEntry)

Definition at line 88 of file heapalloc.c.

91{
92 PBL_FREE_HEAP_ENTRY Entry = FreeEntry;
93
94 /* Get the size of the buffer as the user sees it */
96}

Referenced by MmHapAddToFreeList().

Variable Documentation

◆ HapAllocationAttributes

ULONG HapAllocationAttributes

Definition at line 59 of file heapalloc.c.

Referenced by MmHaInitialize(), and MmHapHeapAllocatorExtend().

◆ HapInitializationStatus

ULONG HapInitializationStatus

Definition at line 56 of file heapalloc.c.

Referenced by BlMmAllocateHeap(), BlMmFreeHeap(), and MmHaInitialize().

◆ HapMinimumHeapSize

ULONG HapMinimumHeapSize

Definition at line 58 of file heapalloc.c.

Referenced by MmHaInitialize(), and MmHapHeapAllocatorExtend().

◆ MmFreeList

◆ MmHeapBoundaries

LIST_ENTRY MmHeapBoundaries