free_list.c File Reference

Free list based allocator implementation. More...

#include <kiba/allocators/free_list.h>
#include <kiba/core/log.h>
#include <kiba/core/memory.h>

Include dependency graph for free_list.c:

Go to the source code of this file.

Data Structures
struct	free_list_entry
	A single entry of a free list. More...
struct	free_list_allocator_block
	Internal state of the free_list_allocator. More...

Macros
#define	KB_FL_ALLOC_CONSISTENCY_CHECK   0
#define	PTR_COMPARE(ptr1, offset1, op, ptr2, offset2)   ((((u8 *) (ptr1)) + (offset1)) op(((u8 *) (ptr2)) + (offset2)))
	Compare two pointers with byte-wise offsets applied. More...

Typedefs
typedef struct free_list_entry	free_list_entry
	A single entry of a free list. More...
typedef struct free_list_allocator_block	free_list_allocator_block
	Internal state of the free_list_allocator. More...

Functions
void	free_list_entry_create (free_list_entry *entry, usize data_size)
	Initialize a free_list_list_entry for a block of a certain size. More...
b8	free_list_insert (free_list_entry **head, usize size, void *at)
	Add a free_list_entry to the free list. More...
b8	free_list_remove (free_list_entry **head, usize size, void **res)
	Find a suitable offset for a requested size in the free list. More...
free_list_allocator_block *	free_list_allocator_block_create (usize size, free_list_allocator_block *next)
	Create a new free_list_allocator_block. More...
void	free_list_allocator_block_destroy (free_list_allocator_block *block)
	Destroy a free_list_allocator_block. More...
b8	free_list_allocator_create (allocator *alloc, usize size)
void	free_list_allocator_destroy (allocator *alloc)
void *	free_list_allocator_allocate (allocator *alloc, usize size)
void	free_list_allocator_free (allocator *alloc, void *mem, usize size)
void	free_list_allocator_free_all (allocator *alloc)

Detailed Description

Free list based allocator implementation.

Definition in file free_list.c.

Macro Definition Documentation

PTR_COMPARE

#define PTR_COMPARE	(		ptr1,
			offset1,
			op,
			ptr2,
			offset2
	)		((((u8 *) (ptr1)) + (offset1)) op(((u8 *) (ptr2)) + (offset2)))

Compare two pointers with byte-wise offsets applied.

Can be used as a condition.

Parameters

ptr1	first pointer of the comparison
offset1	offset to apply to the first pointer
op	operator to use for the comparison
ptr2	second pointer of the comparison
offset2	offset to apply to the second pointer

Definition at line 87 of file free_list.c.

Typedef Documentation

free_list_allocator_block

typedef struct free_list_allocator_block free_list_allocator_block

Internal state of the free_list_allocator.

Memory is managed as a linked list. Each block also points to a free list modeled as a linked list which is stored in the same memory block.

free_list_entry

typedef struct free_list_entry free_list_entry

A single entry of a free list.

Each free list entry preceeds the block of free memory it stands for.

Function Documentation

free_list_allocator_allocate()

void* free_list_allocator_allocate	(	allocator *	alloc,
		usize	size
	)

See also

allocator_impl_allocate_fn

Definition at line 298 of file free_list.c.

free_list_allocator_block_create()

free_list_allocator_block * free_list_allocator_block_create	(	usize	size,
		free_list_allocator_block *	next
	)

Create a new free_list_allocator_block.

Parameters

size	minimum number of bytes that should be provided
next	pointer to the next element the block should reference

Returns

pointer to the new block or KB_NULL if unsuccessful

Definition at line 249 of file free_list.c.

free_list_allocator_block_destroy()

void free_list_allocator_block_destroy

(

free_list_allocator_block *

block

)

Destroy a free_list_allocator_block.

Will return the associated memory to the memory system.

Parameters

block

pointer to the block to destroy

Definition at line 266 of file free_list.c.

free_list_allocator_create()

b8 free_list_allocator_create	(	allocator *	alloc,
		usize	size
	)

See also

allocator_impl_create_fn

Definition at line 268 of file free_list.c.

Here is the call graph for this function:

free_list_allocator_destroy()

void free_list_allocator_destroy

(

allocator *

alloc

)

See also

allocator_impl_destroy_fn

Definition at line 284 of file free_list.c.

Here is the call graph for this function:

free_list_allocator_free()

void free_list_allocator_free	(	allocator *	alloc,
		void *	mem,
		usize	size
	)

See also

allocator_impl_free_fn

Definition at line 336 of file free_list.c.

free_list_allocator_free_all()

void free_list_allocator_free_all

(

allocator *

alloc

)

See also

allocator_impl_free_all_fn

Definition at line 352 of file free_list.c.

Here is the call graph for this function:

free_list_entry_create()

void free_list_entry_create	(	free_list_entry *	entry,
		usize	data_size
	)

Initialize a free_list_list_entry for a block of a certain size.

Parameters

entry	will be populated as the head of a new list
data_size	size of the associated memory block

Definition at line 89 of file free_list.c.

free_list_insert()

b8 free_list_insert	(	free_list_entry **	head,
		usize	size,
		void *	at
	)

Add a free_list_entry to the free list.

Invariant

The list remains sorted by their position in the block from lowest to largest.

The position for the new entry will be determined. The new entry will be merged with the previous and/or following entry when possible to avoid fragmentation. The entry will be placed inside the block before the area of free space.

Parameters

head	start of the free list to search through
size	the size of the new entry to add
at	pointer into the block where the new free space lives

Returns

true if the entry was successfully added/merged, false otherwise

Definition at line 95 of file free_list.c.

Here is the call graph for this function:

free_list_remove()

b8 free_list_remove	(	free_list_entry **	head,
		usize	size,
		void **	res
	)

Find a suitable offset for a requested size in the free list.

Invariant

The list remains sorted by their block positions from lowest to largest.

A viable entry can either be:

• an entry whose size is exacly the requested size
• an entry whose size can hold the requested size + sizeof(free_list_entry)

Each free list entry preceeds its free space. The reverse must also be true to ensure it can be returned later. Thus if we remove something from the list we need to ensure that it can be added back separately. So the first case will simply leverage the existing entry whereas the latter case creates a new entry at the end of the space of the viable entry.

Parameters

	head	start of the free list to search through
	size	the requested size to find in the free list
[out]	res	will be populated with a pointer to the free memory space that it found

Returns

true if a viable entry was found, false otherwise

Definition at line 155 of file free_list.c.