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. |
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
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
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
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)".
template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
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.
1.9.1