Buddy Allocator Template. More...

#include <alloc_buddy.h>

Collaboration diagram for Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >:

Classes
struct	List
	Free List structure Free lists are stored as circular doubly-linked lists. Every possible allocation size has an associated free list that is threaded through all currently free blocks of that size. That means MIN_ALLOC must be at least "sizeof(List)". More...

Public Member Functions
uintptr_t	malloc (size_t request)
	Allocate uninitialized memory.

void	free (uintptr_t ptr)
	Free allocated memory.

size_t	size (uintptr_t ptr)
	Retrieve the allocated size.

Private Member Functions
uintptr_t	ptr_ceil (uintptr_t ptr) const
	Round pointer to next BLOCK_SIZE aligned address.

bool	update_max_ptr (uintptr_t new_value)
	Prepare request for more reserved memory.

List *	ptr_for_node (size_t index, size_t bucket) const
	Map from the index of a node to the address of memory that node represents. The bucket can be derived from the index using a loop but is required to be provided here since having them means we can avoid the loop and have this function return in constant time.

size_t	node_for_ptr (uintptr_t ptr, size_t bucket) const
	Map from an address of memory to the node that represents that address. There are often many nodes that all map to the same address, so the bucket is needed to uniquely identify a node.

int	parent_is_split (size_t index) const
	Get the "is split" flag.

void	flip_parent_is_split (size_t index)
	Flip the "is split" flag of the parent.

size_t	bucket_for_request (size_t request) const
	Get the smallest bucket for the requested size.

Private Attributes
List	buckets [BUCKET_COUNT]
	Allocation buckets Each bucket corresponds to a certain allocation size and stores a free list for that size. The bucket at index 0 corresponds to an allocation size of MAX_ALLOC (i.e. the whole address space).

size_t	bucket_limit
	Allocation size We could initialize the allocator by giving it one free block the size of the entire address space. However, this would cause us to instantly reserve half of the entire address space on the first allocation, since the first split would store a free list entry at the start of the right child of the root. Instead, we have the tree start out small and grow the size of the tree as we use more memory. The size of the tree is tracked by this value.

uint8_t	node_is_split [(1<<(BUCKET_COUNT - 1))/8]
	binary tree This array represents a linearized binary tree of bits. Every possible allocation larger than MIN_ALLOC has a node in this tree (and therefore a bit in this array).

uintptr_t	base_ptr
	Start of reserved memory This is the starting address of the address range for this allocator. Every returned allocation will be an offset of this pointer from 0 to MAX_ALLOC.

uintptr_t	max_ptr
	Current end of reserved memory This is the maximum address that has ever been used by the allocator. It's used to know when to call RESERVED function to request more memory.

Static Private Attributes
static const size_t	HEADER_SIZE = sizeof(size_t)
	Header Every allocation needs an header to store the allocation size while staying aligned. The address returned by "malloc" is the address right after this header (i.e. the size occupies the `size_t` before the returned address).

static const size_t	MIN_ALLOC = static_cast<size_t>(1) << MIN_ALLOC_LOG2
	Minimum allocation size The minimum allocation size is at least twice the header size.

static const size_t	MAX_ALLOC = static_cast<size_t>(1) << MAX_ALLOC_LOG2
	Maximum total allocation size This is the total size of the heap.

static const size_t	BUCKET_COUNT = MAX_ALLOC_LOG2 - MIN_ALLOC_LOG2 + 1
	Number of allocation buckets Allocations are done in powers of two starting from MIN_ALLOC and ending at MAX_ALLOC inclusive. Each allocation size has a bucket that stores the free list for that allocation size.

Detailed Description

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
class Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >

Buddy Allocator Template.

This class implements a buddy memory allocator, which is an allocator that allocates memory within a fixed linear address range. It spans the address range with a binary tree that tracks free space. Both malloc and free are O(log N) time where N is the maximum possible number of allocations.

The "buddy" term comes from how the tree is used. When memory is allocated, nodes in the tree are split recursively until a node of the appropriate size is reached. Every split results in two child nodes, each of which is the buddy of the other. When a node is freed, the node and its buddy can be merged again if the buddy is also free. This makes the memory available for larger allocations again.

Template Parameters

MIN_ALLOC_LOG2	binary logarithm value of the minimal allocation size, has to be at least 4 (= 16 bytes)
MAX_ALLOC_LOG2	binary logarithm value of the maximum total memory which is allocatable
BLOCK_SIZE	allocation size will be a multiple of block size.
RESERVE	Callback function to reserve memory for allocator. First parameter is the start address (on the first call it will be nullptr and the function has to find an adequate position, for all subsequent calls the given address inevitably has to be the start address for the requested memory.) The second parameter is the requested size, always a multiple of `BLOCK_SIZE`. Returns a pointer to the start address if the requested memory was successfully reserved, otherwise nullptr.

Member Function Documentation

◆ bucket_for_request()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

size_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::bucket_for_request ( size_t request ) const

inlineprivate

Get the smallest bucket for the requested size.

Parameters

the	requested size passed to malloc
index	of the smallest bucket that can fit that size

◆ flip_parent_is_split()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

void Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::flip_parent_is_split ( size_t index )

inlineprivate

Flip the "is split" flag of the parent.

Parameters

index the index of a node

◆ free()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

void Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::free ( uintptr_t ptr )

inline

Free allocated memory.

Parameters

ptr	pointer to the start of a memory allocated using malloc

◆ malloc()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

uintptr_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::malloc ( size_t request )

inline

Allocate uninitialized memory.

Parameters

request the size for the memory

Returns: address of the allocated memory or NULL

◆ node_for_ptr()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

size_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::node_for_ptr	(	uintptr_t	ptr,
		size_t	bucket
	)		const

inlineprivate

Map from an address of memory to the node that represents that address. There are often many nodes that all map to the same address, so the bucket is needed to uniquely identify a node.

Parameters

ptr	memory address
bucket	bucket index

Returns: index of the node

◆ parent_is_split()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

int Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::parent_is_split ( size_t index ) const

inlineprivate

Get the "is split" flag.

Parameters

index the index of a node

Returns: the "is split" flag of the parent

◆ ptr_ceil()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

uintptr_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::ptr_ceil ( uintptr_t ptr ) const

inlineprivate

Round pointer to next BLOCK_SIZE aligned address.

Parameters

ptr pointer

Returns: pointer rounded to next block aligned address

◆ ptr_for_node()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

List * Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::ptr_for_node	(	size_t	index,
		size_t	bucket
	)		const

inlineprivate

Map from the index of a node to the address of memory that node represents. The bucket can be derived from the index using a loop but is required to be provided here since having them means we can avoid the loop and have this function return in constant time.

Parameters

index	index of the node
bucket	bucket index

Returns: List element (memory address) of the node

◆ size()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

size_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::size ( uintptr_t ptr )

inline

Retrieve the allocated size.

ptr pointer to the start of the allocated memory

Returns: size of the allocated memory

◆ update_max_ptr()

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

bool Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::update_max_ptr ( uintptr_t new_value )

inlineprivate

Prepare request for more reserved memory.

Parameters

new_value the requested new end for the reserved memory – all addresses from base_ptr to new_value have to be valid reserved addresses for the allocator.

Returns: true if the memory could be reserved, false otherwise

Member Data Documentation

◆ BUCKET_COUNT

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

const size_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::BUCKET_COUNT = MAX_ALLOC_LOG2 - MIN_ALLOC_LOG2 + 1

staticprivate

Number of allocation buckets Allocations are done in powers of two starting from MIN_ALLOC and ending at MAX_ALLOC inclusive. Each allocation size has a bucket that stores the free list for that allocation size.

Given a bucket index, the size of the allocations in that bucket can be found with "(size_t)1 << (MAX_ALLOC_LOG2 - bucket)".

◆ node_is_split

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>

uint8_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::node_is_split[(1<<(BUCKET_COUNT - 1))/8]

private

binary tree This array represents a linearized binary tree of bits. Every possible allocation larger than MIN_ALLOC has a node in this tree (and therefore a bit in this array).

Given the index for a node, linearized binary trees allow you to traverse to the parent node or the child nodes just by doing simple arithmetic on the index:

Move to parent: index = (index - 1) / 2;
Move to left child: index = index * 2 + 1;
Move to right child: index = index * 2 + 2;
Move to sibling: index = ((index - 1) ^ 1) + 1;

Each node in this tree can be in one of several states:

UNUSED (both children are UNUSED)
SPLIT (one child is UNUSED and the other child isn't)
USED (neither children are UNUSED)

These states take two bits to store. However, it turns out we have enough information to distinguish between UNUSED and USED from context, so we only need to store SPLIT or not, which only takes a single bit.

Note that we don't need to store any nodes for allocations of size MIN_ALLOC since we only ever care about parent nodes.

The documentation for this class was generated from the following file:

utils/alloc_buddy.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Function Documentation

◆ bucket_for_request()

◆ flip_parent_is_split()

◆ free()

◆ malloc()

◆ node_for_ptr()

◆ parent_is_split()

◆ ptr_ceil()

◆ ptr_for_node()

◆ size()

◆ update_max_ptr()

Member Data Documentation

◆ BUCKET_COUNT

◆ node_is_split