buddy_allocator.h File Reference

#include <stdint.h>

Go to the source code of this file.

Typedefs
typedef struct BuddyAllocator	BuddyAllocator

Enumerations
enum	BAResult { BA_SUCCESS = 0, BA_NOT_ENOUGH_MEMORY, BA_INVALID_ALIGNMENT }

Functions
BuddyAllocator *	create_buddy_allocator (uint64_t capacity, uint64_t block_size)
BAResult	buddy_allocator_allocate (BuddyAllocator *allocator, uint64_t size, uint64_t alignment, uint64_t *offset)
void	buddy_allocator_free (BuddyAllocator *allocator, uint64_t offset, uint64_t size)
void	destroy_buddy_allocator (BuddyAllocator *allocator)

Typedef Documentation

BuddyAllocator

typedef struct BuddyAllocator BuddyAllocator

Definition at line 29 of file buddy_allocator.h.

Enumeration Type Documentation

BAResult

enum BAResult

Enumerator
BA_SUCCESS
BA_NOT_ENOUGH_MEMORY
BA_INVALID_ALIGNMENT

Definition at line 22 of file buddy_allocator.h.

{
    BA_SUCCESS = 0,
    BA_NOT_ENOUGH_MEMORY,
    BA_INVALID_ALIGNMENT
} BAResult;

Function Documentation

buddy_allocator_allocate()

BAResult buddy_allocator_allocate	(	BuddyAllocator *	allocator,
		uint64_t	size,
		uint64_t	alignment,
		uint64_t *	offset
	)

Definition at line 97 of file buddy_allocator.c.

{
    uint32_t level = max((uint32_t)ceil(log2(size)), allocator->base_level) - allocator->base_level;
 
    // The requested size exceeds the allocator capacity
    if (level >= allocator->level_num)
        return BA_NOT_ENOUGH_MEMORY;
 
    // Every block is aligned to its size
    const uint64_t block_size = (uint64_t)(1 << (level + allocator->base_level));
    const uint64_t alignment_size = block_size % alignment;
 
    assert(alignment_size == 0);
    if (alignment_size != 0)
        return BA_INVALID_ALIGNMENT;
 
    uint32_t i = level;
    for (; i < allocator->level_num && allocator->free_block_lists[i] == NULL; i++)
    {
    }
 
    if (i == allocator->level_num)
        return BA_NOT_ENOUGH_MEMORY;
 
    if (i > level)
        subdivide_block(allocator, i, level);
 
    AllocatorFreeListItem* item = allocator->free_block_lists[level];
    allocator->free_block_lists[level] = item->next;
 
    const uint32_t level_block_offset = get_level_offset(allocator, level);
    allocator->block_states[level_block_offset + item->block_index] = BLOCK_ALLOCATED;
 
    *offset = item->block_index * block_size;
    free_list_item(allocator, item);
 
    return BA_SUCCESS;
}

Referenced by allocate_device_memory().

buddy_allocator_free()

void buddy_allocator_free	(	BuddyAllocator *	allocator,
		uint64_t	offset,
		uint64_t	size
	)

Definition at line 136 of file buddy_allocator.c.

{
    const uint32_t level = max((uint32_t)ceil(log2(size)), allocator->base_level) - allocator->base_level;
    const uint64_t block_size = (uint64_t)(1 << (level + allocator->base_level));
    const uint32_t block_index = offset / block_size;
 
    const uint32_t level_block_offset = get_level_offset(allocator, level);
    assert(allocator->block_states[level_block_offset + block_index] == BLOCK_ALLOCATED);
    allocator->block_states[level_block_offset + block_index] = BLOCK_FREE;
 
    if (!merge_blocks(allocator, level, block_index))
        write_free_block_to_list(allocator, level, block_index);
}

Referenced by free_device_memory().

create_buddy_allocator()

BuddyAllocator* create_buddy_allocator	(	uint64_t	capacity,
		uint64_t	block_size
	)

Definition at line 59 of file buddy_allocator.c.

{
    const uint32_t base_level = uint_log2(block_size);
    const uint32_t level_num = uint_log2(capacity) - base_level + 1;
 
    uint32_t block_num = 0;
    for (uint32_t i = 0; i < level_num; i++)
        block_num += 1 << ((level_num - 1) - i);
 
    const size_t alignment = 16;
    const size_t allocator_size = _align(sizeof(BuddyAllocator), alignment);
    const size_t free_list_array_size = _align(level_num * sizeof(AllocatorFreeListItem*), alignment);
    const size_t free_item_buffer_size = _align(block_num * sizeof(AllocatorFreeListItem), alignment);
    const size_t block_state_size = _align(block_num * sizeof(uint8_t), alignment);
    char* memory = malloc(allocator_size + free_list_array_size + free_item_buffer_size + block_state_size);
 
    BuddyAllocator* allocator = (BuddyAllocator*)memory;
    allocator->base_level = base_level;
    allocator->level_num = level_num;
    allocator->memory = memory;
    allocator->free_block_lists = (AllocatorFreeListItem**)(memory + allocator_size);
    allocator->free_items = (AllocatorFreeListItem*)(memory + allocator_size + free_list_array_size);
    allocator->block_states = (uint8_t*)(memory + allocator_size + free_list_array_size + free_item_buffer_size);
 
    memset(allocator->free_block_lists, 0, level_num * sizeof(AllocatorFreeListItem*));
    memset(allocator->free_items, 0, block_num * sizeof(AllocatorFreeListItem));
    memset(allocator->block_states, 0, block_num * sizeof(uint8_t));
 
    for (uint32_t i = 0; i < block_num; i++)
        allocator->free_items[i].next = allocator->free_items + i + 1;
    allocator->free_items[block_num - 1].next = NULL;
 
    allocator->block_states[block_num - 1] = BLOCK_FREE;
    write_free_block_to_list(allocator, level_num - 1, 0);
 
    return allocator;
}

Referenced by create_sub_allocator().

destroy_buddy_allocator()

void destroy_buddy_allocator

(

BuddyAllocator *

allocator

)

Definition at line 150 of file buddy_allocator.c.

{
    free(allocator->memory);
}