ReactOS  0.4.13-dev-79-gcd489d8
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 {
574  PBL_HEAP_BOUNDARIES Heap;
575  PBL_BUSY_HEAP_ENTRY BusyEntry, FreeEntry, NextEntry;
576 
577  /* Ignore heap allocation if the heap allocator isn't ready yet */
578  if (HapInitializationStatus != 1)
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  {
596  BufferSize = sizeof(BL_FREE_HEAP_ENTRY);
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 */
635  Heap->HeapStart->BufferNext.BufferFree = 1;
636  Heap->HeapStart->BufferNext.BufferOnHeap = 1;
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 }
Definition: heapalloc.c:32
struct _BL_FREE_HEAP_ENTRY BL_FREE_HEAP_ENTRY
ULONG_PTR HeapLimit
Definition: heapalloc.c:51
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
PBL_BUSY_HEAP_ENTRY HeapStart
Definition: heapalloc.c:53
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:43
uint32_t ULONG_PTR
Definition: typedefs.h:63
PBL_BUSY_HEAP_ENTRY MmHapFindBufferInFreeList(_In_ ULONG Size)
Definition: heapalloc.c:450
Definition: heapalloc.c:40
ULONG HapInitializationStatus
Definition: heapalloc.c:56
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
Definition: bufpool.h:45
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
ULONG_PTR BufferOnHeap
Definition: heapalloc.c:24
#define BufferSize
Definition: classpnp.h:419
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:42
ULONG_PTR BufferFree
Definition: heapalloc.c:23
NTSTATUS MmHapHeapAllocatorExtend(_In_ ULONG ExtendSize)
Definition: heapalloc.c:102
struct _BL_BUSY_HEAP_ENTRY * PBL_BUSY_HEAP_ENTRY
static const WCHAR L[]
Definition: oid.c:1250
IN PVOID IN PVOID IN USHORT IN USHORT Size
Definition: pci.h:359
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
VOID EfiPrintf(_In_ PWCHAR Format,...)
Definition: firmware.c:126
UCHAR Buffer[ANYSIZE_ARRAY]
Definition: heapalloc.c:44
unsigned int ULONG
Definition: retypes.h:1
#define ULONG_PTR
Definition: config.h:101
#define ALIGN_UP_BY(size, align)
LIST_ENTRY MmHeapBoundaries
Definition: heapalloc.c:57

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;
668  PBL_HEAP_BOUNDARIES Heap;
669  PLIST_ENTRY NextEntry;
670 
671  /* If the heap is not initialized, fail */
672  if (HapInitializationStatus != 1)
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 }
ULONG_PTR HeapBase
Definition: heapalloc.c:52
#define STATUS_INVALID_PARAMETER
Definition: udferr_usr.h:135
PBL_BUSY_HEAP_ENTRY HeapStart
Definition: heapalloc.c:53
uint32_t ULONG_PTR
Definition: typedefs.h:63
Definition: heapalloc.c:40
ULONG HapInitializationStatus
Definition: heapalloc.c:56
Definition: bufpool.h:45
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define STATUS_UNSUCCESSFUL
Definition: udferr_usr.h:132
PBL_FREE_HEAP_ENTRY MmHapAddToFreeList(_In_ PBL_BUSY_HEAP_ENTRY Entry, _In_ ULONG Flags)
Definition: heapalloc.c:393
Definition: typedefs.h:117
LIST_ENTRY MmHeapBoundaries
Definition: heapalloc.c:57
return STATUS_SUCCESS
Definition: btrfs.c:2725

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 */
546  MmFreeList = NULL;
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
SIZE_T WINAPI HeapSize(HANDLE, DWORD, LPCVOID)
ULONG HapInitializationStatus
Definition: heapalloc.c:56
smooth NULL
Definition: ftsmooth.c:416
ULONG HapAllocationAttributes
Definition: heapalloc.c:59
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
ULONG HapMinimumHeapSize
Definition: heapalloc.c:58
NTSTATUS MmHapHeapAllocatorExtend(_In_ ULONG ExtendSize)
Definition: heapalloc.c:102
#define PAGE_SIZE
Definition: env_spec_w32.h:49
Status
Definition: gdiplustypes.h:24
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
#define ALIGN_UP_BY(size, align)
LIST_ENTRY MmHeapBoundaries
Definition: heapalloc.c:57
return STATUS_SUCCESS
Definition: btrfs.c:2725

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
Definition: heapalloc.c:32
FORCEINLINE ULONG MmHapBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:76
PBL_FREE_HEAP_ENTRY MmHapCoalesceFreeBuffer(_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
Definition: heapalloc.c:333
BL_HEAP_POINTER FreeNext
Definition: heapalloc.c:36
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170
ULONG LibraryFlags
Definition: bl.h:758
FORCEINLINE ULONG MmHapUserBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:88
smooth NULL
Definition: ftsmooth.c:416
BL_HEAP_POINTER FreePrevious
Definition: heapalloc.c:37
#define BL_LIBRARY_FLAG_ZERO_HEAP_ALLOCATIONS_ON_FREE
Definition: bl.h:131
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
ULONG MmHapGetBucketId(_In_ ULONG Size)
Definition: heapalloc.c:199
PVOID MmHapCheckBufferLinks(_In_ PVOID BufferEntry)
Definition: heapalloc.c:268
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
base of all file and directory entries
Definition: entries.h:82

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 }
Definition: heapalloc.c:32
uint32_t ULONG_PTR
Definition: typedefs.h:63
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
#define ULONG_PTR
Definition: config.h:101
base of all file and directory entries
Definition: entries.h:82

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 }
struct _Entry Entry
Definition: kefuncs.h:640
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:34
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:35
Definition: heapalloc.c:32
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
VOID MmHapReportHeapCorruption(_In_ PBL_FREE_HEAP_ENTRY BufferEntry)
Definition: heapalloc.c:222
base of all file and directory entries
Definition: entries.h:82

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 }
struct _Entry Entry
Definition: kefuncs.h:640
Definition: heapalloc.c:32
BL_HEAP_POINTER FreeNext
Definition: heapalloc.c:36
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
BL_HEAP_POINTER FreePrevious
Definition: heapalloc.c:37
VOID MmHapReportHeapCorruption(_In_ PBL_FREE_HEAP_ENTRY BufferEntry)
Definition: heapalloc.c:222
base of all file and directory entries
Definition: entries.h:82

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 */
350  Next = MmHapRemoveBufferFromFreeList(Next);
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 */
374  Prev = MmHapRemoveBufferFromFreeList(Prev);
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 }
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:34
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:35
Definition: heapalloc.c:32
PBL_FREE_HEAP_ENTRY MmHapRemoveBufferFromFreeList(_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
Definition: heapalloc.c:293
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
ULONG_PTR BufferOnHeap
Definition: heapalloc.c:24
ULONG_PTR BufferFree
Definition: heapalloc.c:23
PVOID MmHapCheckBufferLinks(_In_ PVOID BufferEntry)
Definition: heapalloc.c:268

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 }
Definition: heapalloc.c:32
static int Link(const char **args)
Definition: vfdcmd.c:2414
#define BL_HEAP_POINTER_FLAG_BITS
Definition: heapalloc.c:15

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 }
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:34
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:35
Definition: heapalloc.c:32
FORCEINLINE ULONG MmHapBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:76
BL_HEAP_POINTER FreeNext
Definition: heapalloc.c:36
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:43
uint32_t ULONG_PTR
Definition: typedefs.h:63
PBL_FREE_HEAP_ENTRY MmHapRemoveBufferFromFreeList(_In_ PBL_FREE_HEAP_ENTRY FreeEntry)
Definition: heapalloc.c:293
Definition: heapalloc.c:40
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:42
struct _BL_BUSY_HEAP_ENTRY * PBL_BUSY_HEAP_ENTRY
PBL_FREE_HEAP_ENTRY MmHapAddToFreeList(_In_ PBL_BUSY_HEAP_ENTRY Entry, _In_ ULONG Flags)
Definition: heapalloc.c:393
IN PVOID IN PVOID IN USHORT IN USHORT Size
Definition: pci.h:359
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
ULONG MmHapGetBucketId(_In_ ULONG Size)
Definition: heapalloc.c:199
PVOID MmHapCheckBufferLinks(_In_ PVOID BufferEntry)
Definition: heapalloc.c:268
unsigned int ULONG
Definition: retypes.h:1
#define NT_ASSERT
Definition: rtlfuncs.h:3312

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 }
#define PAGE_SIZE
Definition: env_spec_w32.h:49
IN PVOID IN PVOID IN USHORT IN USHORT Size
Definition: pci.h:359
unsigned int ULONG
Definition: retypes.h:1

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 */
150  BlLoaderHeap,
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 */
174  NewHeap->HeapStart->BufferPrevious.P = HeapBase;
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 }
struct _BL_FREE_HEAP_ENTRY * PBL_FREE_HEAP_ENTRY
#define PAGE_SHIFT
Definition: env_spec_w32.h:45
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
NTSTATUS EfiStall(_In_ ULONG StallTime)
Definition: firmware.c:1003
LIST_ENTRY ListEntry
Definition: heapalloc.c:49
ULONG_PTR HeapBase
Definition: heapalloc.c:52
LONG NTSTATUS
Definition: precomp.h:26
Definition: heapalloc.c:32
ULONG_PTR HeapLimit
Definition: heapalloc.c:51
#define InsertTailList(ListHead, Entry)
SIZE_T WINAPI HeapSize(HANDLE, DWORD, LPCVOID)
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
PBL_BUSY_HEAP_ENTRY HeapStart
Definition: heapalloc.c:53
BL_HEAP_POINTER BufferPrevious
Definition: heapalloc.c:43
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG_PTR HeapEnd
Definition: heapalloc.c:50
#define STATUS_INTEGER_OVERFLOW
Definition: ntstatus.h:371
Definition: heapalloc.c:40
smooth NULL
Definition: ftsmooth.c:416
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
ULONG HapAllocationAttributes
Definition: heapalloc.c:59
struct _BL_HEAP_BOUNDARIES * PBL_HEAP_BOUNDARIES
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
ULONG HapMinimumHeapSize
Definition: heapalloc.c:58
ULONG_PTR BufferOnHeap
Definition: heapalloc.c:24
BL_HEAP_POINTER BufferNext
Definition: heapalloc.c:42
ULONG_PTR BufferFree
Definition: heapalloc.c:23
struct _BL_BUSY_HEAP_ENTRY * PBL_BUSY_HEAP_ENTRY
static const WCHAR L[]
Definition: oid.c:1250
#define PAGE_SIZE
Definition: env_spec_w32.h:49
_In_opt_ PVOID HeapBase
Definition: rtlfuncs.h:2169
Status
Definition: gdiplustypes.h:24
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
VOID EfiPrintf(_In_ PWCHAR Format,...)
Definition: firmware.c:126
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
#define ULONG_PTR
Definition: config.h:101
#define ALIGN_UP_BY(size, align)
LIST_ENTRY MmHeapBoundaries
Definition: heapalloc.c:57
return STATUS_SUCCESS
Definition: btrfs.c:2725
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

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 }
Definition: heapalloc.c:32
FORCEINLINE ULONG MmHapBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:76
BL_HEAP_POINTER FreeNext
Definition: heapalloc.c:36
FORCEINLINE PBL_FREE_HEAP_ENTRY MmHapDecodeLink(_In_ BL_HEAP_POINTER Link)
Definition: heapalloc.c:66
BL_HEAP_POINTER FreePrevious
Definition: heapalloc.c:37
PBL_FREE_HEAP_ENTRY * MmFreeList
Definition: heapalloc.c:60
ULONG MmHapGetBucketId(_In_ ULONG Size)
Definition: heapalloc.c:199
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 }
void __cdecl __debugbreak(void)
Definition: intrin_ppc.h:698
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
BOOLEAN BlBdDebuggerEnabled(VOID)
Definition: debug.c:53
static const WCHAR L[]
Definition: oid.c:1250
VOID EfiPrintf(_In_ PWCHAR Format,...)
Definition: firmware.c:126
VOID BlStatusPrint(_In_ PCWCH Format,...)
Definition: debug.c:75

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 }
Definition: heapalloc.c:32
FORCEINLINE ULONG MmHapBufferSize(_In_ PVOID FreeEntry)
Definition: heapalloc.c:76
Definition: heapalloc.c:40
Definition: bufpool.h:45
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
base of all file and directory entries
Definition: entries.h:82

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