buddy_allocator.c File Reference

#include "shared/shared.h"
#include "buddy_allocator.h"
#include <assert.h>

Go to the source code of this file.

Classes
struct	AllocatorFreeListItem
struct	BuddyAllocator

Typedefs
typedef enum AllocatorBlockState	AllocatorBlockState
typedef struct AllocatorFreeListItem	AllocatorFreeListItem
typedef struct BuddyAllocator	BuddyAllocator

Enumerations
enum	AllocatorBlockState { BLOCK_NONE = 0, BLOCK_FREE, BLOCK_SPLIT, BLOCK_ALLOCATED }

Functions
static size_t	_align (size_t value, size_t alignment)
static int32_t	uint_log2 (uint64_t x)
static AllocatorFreeListItem *	allocate_list_item (BuddyAllocator *allocator)
static void	free_list_item (BuddyAllocator *allocator, AllocatorFreeListItem *item)
static void	write_free_block_to_list (BuddyAllocator *allocator, uint32_t level, uint32_t block_index)
static uint32_t	get_level_offset (BuddyAllocator *allocator, uint32_t level)
static uint32_t	get_next_level_offset (BuddyAllocator *allocator, uint32_t level, uint32_t offset)
void	subdivide_block (BuddyAllocator *allocator, uint32_t src_level, uint32_t dst_level)
qboolean	merge_blocks (BuddyAllocator *allocator, uint32_t level, uint32_t block_index)
void	remove_block_from_free_list (BuddyAllocator *allocator, uint32_t level, uint32_t block_index)
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

AllocatorBlockState

typedef enum AllocatorBlockState AllocatorBlockState

AllocatorFreeListItem

typedef struct AllocatorFreeListItem AllocatorFreeListItem

BuddyAllocator

typedef struct BuddyAllocator BuddyAllocator

Enumeration Type Documentation

AllocatorBlockState

enum AllocatorBlockState

Enumerator
BLOCK_NONE
BLOCK_FREE
BLOCK_SPLIT
BLOCK_ALLOCATED

Definition at line 23 of file buddy_allocator.c.

{
    BLOCK_NONE = 0,
    BLOCK_FREE,
    BLOCK_SPLIT,
    BLOCK_ALLOCATED
} AllocatorBlockState;

Function Documentation

_align()

static size_t _align ( size_t  value, size_t  alignment  )

inlinestatic

Definition at line 234 of file buddy_allocator.c.

{
    return (value + alignment - 1) / alignment * alignment;
}

Referenced by create_buddy_allocator().

allocate_list_item()

static AllocatorFreeListItem * allocate_list_item ( BuddyAllocator *  allocator )

inlinestatic

Definition at line 247 of file buddy_allocator.c.

{
    AllocatorFreeListItem* item = allocator->free_items;
    allocator->free_items = item->next;
    return item;
}

Referenced by subdivide_block(), and write_free_block_to_list().

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);
}

free_list_item()

static void free_list_item ( BuddyAllocator *  allocator, AllocatorFreeListItem *  item  )

inlinestatic

Definition at line 254 of file buddy_allocator.c.

{
    item->next = allocator->free_items;
    allocator->free_items = item;
}

Referenced by buddy_allocator_allocate(), and remove_block_from_free_list().

get_level_offset()

static uint32_t get_level_offset ( BuddyAllocator *  allocator, uint32_t  level  )

inlinestatic

Definition at line 268 of file buddy_allocator.c.

{
    uint32_t offset = 0;
    for (int32_t i = 0; i < level; i++)
        offset += 1 << ((allocator->level_num - 1) - i);
 
    return offset;
}

Referenced by buddy_allocator_allocate(), buddy_allocator_free(), merge_blocks(), and subdivide_block().

get_next_level_offset()

static uint32_t get_next_level_offset ( BuddyAllocator *  allocator, uint32_t  level, uint32_t  offset  )

inlinestatic

Definition at line 277 of file buddy_allocator.c.

{
    return offset + (1 << ((allocator->level_num - 1) - prev_level));
}

Referenced by subdivide_block().

merge_blocks()

qboolean merge_blocks	(	BuddyAllocator *	allocator,
		uint32_t	level,
		uint32_t	block_index
	)

Definition at line 190 of file buddy_allocator.c.

{
    if (level == allocator->level_num - 1)
    {
        write_free_block_to_list(allocator, level, block_index);
        return qtrue;
    }
 
    const uint32_t level_block_offset = get_level_offset(allocator, level);
    const uint32_t buddy_block_index = (block_index % 2) == 0 ? block_index + 1 : block_index - 1;
 
    if (allocator->block_states[level_block_offset + buddy_block_index] != BLOCK_FREE)
        return qfalse;
 
    remove_block_from_free_list(allocator, level, buddy_block_index);
 
    const uint32_t next_level_block_offset = get_level_offset(allocator, level + 1);
    const uint32_t next_level_block_index = block_index / 2;
    assert(allocator->block_states[next_level_block_offset + next_level_block_index] == BLOCK_SPLIT);
    allocator->block_states[next_level_block_offset + next_level_block_index] = BLOCK_FREE;
 
    if (!merge_blocks(allocator, level + 1, next_level_block_index))
        write_free_block_to_list(allocator, level + 1, next_level_block_index);
 
    return qtrue;
}

Referenced by buddy_allocator_free().

remove_block_from_free_list()

void remove_block_from_free_list	(	BuddyAllocator *	allocator,
		uint32_t	level,
		uint32_t	block_index
	)

Definition at line 217 of file buddy_allocator.c.

{
    AllocatorFreeListItem** prev_next = &allocator->free_block_lists[level];
    AllocatorFreeListItem* item = allocator->free_block_lists[level];
 
    assert(item != NULL);
    while (item->block_index != block_index)
    {
        prev_next = &item->next;
        item = item->next;
        assert(item != NULL);
    }
 
    *prev_next = item->next;
    free_list_item(allocator, item);
}

Referenced by merge_blocks().

subdivide_block()

void subdivide_block	(	BuddyAllocator *	allocator,
		uint32_t	src_level,
		uint32_t	dst_level
	)

Definition at line 155 of file buddy_allocator.c.

{
    assert(dst_level < src_level);
 
    {
        // Task free block from the list
        AllocatorFreeListItem* item = allocator->free_block_lists[src_level];
        allocator->free_block_lists[src_level] = item->next;
 
        // Find offsets for states
        const uint32_t previous_level_block_offset = get_level_offset(allocator, src_level - 1);
        const uint32_t current_level_block_offset = get_next_level_offset(allocator, src_level - 1, previous_level_block_offset);
 
        const uint32_t block_index = item->block_index;
 
        // Change state of the blocks
        assert(allocator->block_states[current_level_block_offset + block_index] == BLOCK_FREE);
        allocator->block_states[current_level_block_offset + block_index] = BLOCK_SPLIT;
        allocator->block_states[previous_level_block_offset + block_index * 2] = BLOCK_FREE;
        allocator->block_states[previous_level_block_offset + block_index * 2 + 1] = BLOCK_FREE;
 
        // Add blocks to free list
        AllocatorFreeListItem* item0 = allocate_list_item(allocator);
        AllocatorFreeListItem* item1 = allocate_list_item(allocator);
        item0->block_index = block_index * 2;
        item0->next = item1;
        item1->block_index = block_index * 2 + 1;
        item1->next = allocator->free_block_lists[src_level - 1];
        allocator->free_block_lists[src_level - 1] = item0;
    }
 
    if (src_level - 1 != dst_level)
        subdivide_block(allocator, src_level - 1, dst_level);
}

Referenced by buddy_allocator_allocate().

uint_log2()

static int32_t uint_log2 ( uint64_t  x )

inlinestatic

Definition at line 239 of file buddy_allocator.c.

{
    uint32_t result = 0;
    while (x >>= 1)
        result++;
    return result;
}

Referenced by create_buddy_allocator().

write_free_block_to_list()

static void write_free_block_to_list ( BuddyAllocator *  allocator, uint32_t  level, uint32_t  block_index  )

inlinestatic

Definition at line 260 of file buddy_allocator.c.

{
    AllocatorFreeListItem* item = allocate_list_item(allocator);
    item->block_index = block_index;
    item->next = allocator->free_block_lists[level];
    allocator->free_block_lists[level] = item;
}

Referenced by buddy_allocator_free(), create_buddy_allocator(), and merge_blocks().