This document serves as a crash course for all the memory related functionality NabiAllocator offers. Basically, everything inside the Memory folder.

Notes:

• Aside from this document, there is also inline documentation in the code as well as a description of the contents of each file at the top of its .h.
• In the following code snippets the nabi_allocator or na namespace has been omitted for brevity.

The memory command is the centre point for NabiAllocator's functionality and allows its different functionality to work together. It is a singleton and can be accessed through MemoryCommand::Instance.

However, for the most part you can just leave it be and don't have to worry about it. If NA_OVERRIDE_NEW_DELETE is defined allocations and frees will be automatically routed through it, and HeapZoneScopes will automatically push and pop themselves using RAII.

Custom memory allocation is great, but sometimes you just want to allocate some memory with good old malloc. If you do, you can use the UnmanagedHeap and call Allocate or Free. You can access the UnmanagedHeap through MemoryCommand::GetUnmanagedHeap or use the global c_UnmanagedHeap constant.

// This is recommended
NA_SET_HEAP_ZONE_SCOPE(&c_UnmanagedHeap, c_NullMemoryTag); 
int* i = new int();

// Though you could also do this
int* j = reinterpret_cast<int*>(MemoryCommand::Instance().GetUnmanagedHeap().Allocate(sizeof(int))); // (or just c_UnmanagedHeap.Allocate...)

Another name for the HeapZone would be a memory arena. HeapZones own blocks of memory allocated on the heap, and are templated with an allocator which manages how that memory is used. You can have multiple heap zones in a project, and even have heap zones within heap zones! HeapZones can be made thread safe via the NA_THREAD_SAFE_HEAP_ZONE define.

If you try to call HeapZone::Allocate directly, you'll notice it takes in an AllocationInfo struct. This struct contains the size of the requested allocation and, if NA_MEMORY_TAGGING is defined, its memory tag. In order to avoid errors when NA_MEMORY_TAGGING is defined on and off, you can use the handy NA_MAKE_ALLOCATION_INFO macro.

HeapZone<DefaultStackAllocator> parentZone = { HeapZoneBase::c_NoParent, 128, "ParentZone" };
HeapZone<DefaultFreeListAllocator> childZone = { &parentZone, 64, "ChildZone" };

// If you wanted to allocate to a heap zone directly, you could do something like this:
void* const allocation = childZone.Allocate(NA_MAKE_ALLOCATION_INFO(4u, c_NullMemoryTag));

Note: Be careful that you don't create a HeapZone which is too large. Your operating system or architecture may not be able to handle it. Under the hood a HeapZone uses malloc and free to manage its memory.

HeapZoneScopes are used to swap between HeapZones or change the memory tag. They use RAII, so when a HeapZoneScope goes out of scope then it falls back to the previous scope. You can think of it like a stack (because, well, it is!). The MemoryCommand manages this stack and uses it to determine which zone to allocate to.

The NA_SET_HEAP_ZONE_SCOPE can be used to simplify the creation of a HeapZoneScope.

HeapZone<DefaultFreeListAllocator> heapZoneOne = { HeapZoneBase::c_NoParent, 64u , "HeapZoneOne" };
HeapZone<DefaultFreeListAllocator> heapZoneTwo = { HeapZoneBase::c_NoParent, 64u , "HeapZoneTwo" };

{
	NA_SET_HEAP_ZONE_SCOPE(&heapZoneOne, c_NullMemoryTag);
	{
		NA_SET_HEAP_ZONE_SCOPE(&heapZoneTwo, c_NullMemoryTag);
		// Any allocations here would be handled by heapZoneTwo
	}
	// Any allocations here would be handled by heapZoneOne
}
// No heap zone is active in this scope

In NabiAllocator, you template a HeapZone with an allocator. The HeapZone owns a block of memory and the allocator manages the block. All allocators are templated with a settings struct, but if you just want the default behaviour you can use the Default[AllocatorName] typedef.

All allocators inherit from AllocatorBase. If you want to write your own allocator, that means all you need to do to write your own allocator is inherit from AllocatorBase and override the pure virtual Allocate, Free, Reset, IterateThroughHeapZone and GetAllocationInfo functions. Then you can just template a HeapZone with your allocator, and it will work like any of the prebuilt ones. Remember to override the virtual destructor and call the constructor as well.

All of these functions take the HeapZoneInfo struct, which contains the start and end pointer of the HeapZone the allocator is being used with. This can be used, for example, to check if an allocation will exceed the memory in the heap zone.

• Allocate takes in an AllocationInfo struct, which contains the size of the allocation and if NA_MEMORY_TAGGING is defined the memory tag to pack with the allocations.
• Free takes in the pointer to the memory to free. Note: If the free request comes through the MemoryCommand then the pointer will always be valid.
• Reset only takes in the HeapZoneInfo. It should reset the allocator and heapzone to its default state.
• IterateThroughHeapZone should return a std::deque<AllocatorBlockInfo> of all of the blocks of memory (allocated or free) in the heap zone.
• GetAllocationInfo should return a AllocatorBlockInfo for a single block.

To test and benchmark your allocator, you can hook into the tests defined in AllocatorDefaultTests.cpp and AllocatorDefaultBenchmarks.cpp. An example of there use can be seen in FreeListAllocatorTests.cpp.

A free list allocator works my maintaining a linked list of all of the free blocks of memory in an arena. When an allocation request comes in, the list is traversed to find a free block of suitable size.

The traversal algorithm can be customised to favour speed or space efficiency.

• BestFit, the default algorithm, will find the block of memory which is the closest to the requested blocks size.
• FirstFit will find the first block which is large enough to fit the allocation.

In NabiAllocator, the FreeListAllocator has a memory layout like so:

• Allocated block: BlockHeader struct -> Payload -> Padding -> BlockPadding struct -> BlockFooter struct
• Free block: BlockHeader struct -> FreeListNode struct -> BlockFooter struct

The FreeListAllocator is templated with FreeListAllocatorSettings. You can use this struct to set the search algorithm and leniency for the allocator.

FreeListAllocatorSettings constexpr settings =
{
	.m_SearchAlgorithm = SearchAlgorithm::FirstFit
};
HeapZone<FreeListAllocator<settings>> firstFitFreeListAllocatorHeapZone = ...;

A stack allocator works like a stack! Memory can only be allocated and freed from the top of the stack. It is much less flexible than the free list allocator, but potentially faster in certain situations.

In NabiAllocator, the StackAllocator has a memory layout like so:

• Payload -> Padding -> BlockPadding Struct -> BlockHeader Struct

Memory tagging is a technique where additional information is packed with each allocation. It can be used, for example, to label memory with where its been allocated from and thus create a memory usage graph. In NabiAllocator, memory tagging can be enabled with the NA_MEMORY_TAGGING define.

Memory tags in NabiAllocator are by default a u32 (unsigned 32 bit integer). This integer has been typedef'ed to memoryTag and is defined in MemoryConstants.h. The current memory tag can be set with NA_SET_HEAP_ZONE_SCOPE.

enum class MemoryTag : memoryTag
{
	TagOne     = 1u << 1u,
	TagTwo     = 1u << 2u,
	All        = ~0u,

	ENUM_COUNT = 3u
};

HeapZone<DefaultFreeListAllocator> heapZone = { HeapZoneBase::c_NoParent, 256u , "HeapZone" };
NA_SET_HEAP_ZONE_SCOPE(&heapZone, type_utils::ToUnderlying(MemoryTag::TagOne));

auto const& allocator = heapZone.GetAllocator();
auto const& zoneInfo = heapZone.GetZoneInfo();

int const* const i = new int(1);
int const* const j = new int(2);

std::deque<AllocatorBlockInfo> const allBlocks = allocator.IterateThroughHeapZone(std::nullopt, zoneInfo);
AllocatorBlockInfo const iBlock = allocator.GetAllocationInfo(i, zoneInfo);

// Your logic here
// eg: iBlock.m_MemoryTag...

delete i;
delete j;

Instead of passing in std::nullopt to IterateThroughHeapZone, you can pass in a std::function<bool(AllocatorBlockInfo const&)> which will be called on each block. This is how, for example, the GetFullMemoryUsage function works - you can see a good example of this in the AllocatorMemoryTagTest.