cxx::Buddy_alloc Class Reference

Buddy allocator backed by a perfect binary tree. More...

#include <buddy_alloc>

Collaboration diagram for cxx::Buddy_alloc:

Public Member Functions
void	init (l4_addr_t min_addr, l4_addr_t max_addr, unsigned char *metadata_addr, size_t metadata_size)
	Initialize the allocator.
void	add_mem (void *mem, size_t size)
	Add memory to the allocator.
void *	alloc (size_t size, size_t align, l4_addr_t lower=0, l4_addr_t upper=~0UL)
	Allocate a memory block.
void *	alloc_max (size_t min, size_t *max, size_t align, size_t granularity, l4_addr_t lower=0, l4_addr_t upper=~0UL)
	Allocate a memory block of min <= size <= max.
void	free (void *block, size_t size)
	Return a free memory block to the allocator.
size_t	avail () const
	Get the amount of available memory.

Static Public Member Functions
static constexpr size_t	metadata_bytes (l4_addr_t min_addr, l4_addr_t max_addr)
	Return metadata size in bytes required by the buddy allocator.

Detailed Description

Buddy allocator backed by a perfect binary tree.

The root node of the tree spans the entire memory area managed by the allocator and represents the largest block size supported by the allocator. Each subsequent level of the tree halves the block size until reaching the minimum block size.

Each node in the tree stores the largest order of block that can be allocated at or underneath it:

• A node with a value of 0 is allocated (used).
• A node with a value between 1 and level is split, i.e. has blocks allocated underneath it.
• A node with a value of level+1 is free.

An completely unallocated tree with four levels would look like:

       4
   3       3
 2   2   2   2
1 1 1 1 1 1 1 1

After allocating a block of 2 * Min_size:

       3
   2       3
 0   2   2   2
1 1 1 1 1 1 1 1

Definition at line 56 of file buddy_alloc.

Member Function Documentation

add_mem()

void cxx::Buddy_alloc::add_mem ( void * mem, size_t size )

inline

Add memory to the allocator.

Parameters

mem	Pointer to the memory.
size	Size of the memory.

Precondition

The memory must be within the memory range passed to init().

Definition at line 1307 of file buddy_alloc.

References L4_UNLIKELY.

alloc()

void * cxx::Buddy_alloc::alloc ( size_t size, size_t align, l4_addr_t lower = 0, l4_addr_t upper = ~0UL )

inline

Allocate a memory block.

Parameters

size	Size of the memory block.
align	Alignment constraint (must be a power of two).
lower	Lower bound of the physical region the memory block should be allocated from.
upper	Upper bound of the physical region the memory block should be allocated from, value is inclusive.

Return values

nullptr

Allocation failed.

Returns

Pointer to memory block.

Precondition

0 < size

align <= size

Definition at line 1351 of file buddy_alloc.

References L4_LIKELY, and L4_UNLIKELY.

alloc_max()

void * cxx::Buddy_alloc::alloc_max ( size_t min, size_t * max, size_t align, size_t granularity, l4_addr_t lower = 0, l4_addr_t upper = ~0UL )

inline

Allocate a memory block of min <= size <= max.

Parameters

	min	Minimal size to allocate (in bytes).
[in,out]	max	Maximum size to allocate (in bytes). The actual allocated size is returned here.
	align	Alignment constraint (must be a power of two).
	granularity	Granularity to use for the allocation (power of 2).
	lower	Lower bound of the physical region the memory block should be allocated from.
	upper	Upper bound of the physical region the memory block should be allocated from, value is inclusive.

Note

The allocated size is always a multiple of granularity, thus min is rounded up to a multiple of granularity internally.

Return values

nullptr

Allocation failed.

Returns

Pointer to memory block

Precondition

0 < min <= max

0 < max

align <= min

granularity <= align

Definition at line 1404 of file buddy_alloc.

References L4_LIKELY, and L4_UNLIKELY.

avail()

size_t cxx::Buddy_alloc::avail ( ) const

inline

Get the amount of available memory.

Returns

Available memory in bytes

Available memory in bytes.

Definition at line 1611 of file buddy_alloc.

References avail(), and L4_UNLIKELY.

Referenced by avail().

Here is the call graph for this function:

Here is the caller graph for this function:

free()

void cxx::Buddy_alloc::free ( void * block, size_t size )

inline

Return a free memory block to the allocator.

Parameters

block	Pointer to memory block.
size	Size of memory block.

Precondition

block must not be NULL.

block must have been obtained through alloc() or alloc_max().

Definition at line 1500 of file buddy_alloc.

References L4_UNLIKELY.

init()

void cxx::Buddy_alloc::init ( l4_addr_t min_addr, l4_addr_t max_addr, unsigned char * metadata_addr, size_t metadata_size )

inline

Initialize the allocator.

Parameters

min_addr	Minimum address covered by the allocator.
max_addr	Maximum address covered by the allocator (inclusive).
metadata_addr	Pointer to metadata memory chunk for the allocator.
metadata_size	Size of the metadata memory chunk.

Definition at line 139 of file buddy_alloc.

References metadata_bytes().

Here is the call graph for this function:

metadata_bytes()

constexpr size_t cxx::Buddy_alloc::metadata_bytes ( l4_addr_t min_addr, l4_addr_t max_addr )

inlinestaticconstexpr

Return metadata size in bytes required by the buddy allocator.

Parameters

min_addr	Minimum address covered by the allocator.
max_addr	Maximum address covered by the allocator (inclusive).

Definition at line 124 of file buddy_alloc.

Referenced by init().

Here is the caller graph for this function:

---

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

• l4/cxx/buddy_alloc