core/mem/tlsf

mem_tlsf

Types

Allocator :: struct {
	// Empty lists point at this block to indicate they are free.
	block_null:    Block_Header,
	// Bitmaps for free lists.
	fl_bitmap:     u32,
	sl_bitmap:     [FL_INDEX_COUNT]u32,
	// Head of free lists.
	blocks:        [FL_INDEX_COUNT][SL_INDEX_COUNT]^Block_Header,
	// Keep track of pools so we can deallocate them.
	// If `pool.allocator` is blank, we don't do anything.
	// We also use this linked list of pools to report
	// statistics like how much memory is still available,
	// fragmentation, etc.
	pool:          Pool,
	// If we're expected to grow when we run out of memory,
	// how much should we ask the backing allocator for?
	new_pool_size: uint,
}

Source

Block_Header :: struct {
	prev_phys_block: ^Block_Header,
	size:            uint,
	// Next and previous free blocks.
	next_free:       ^Block_Header,
	prev_free:       ^Block_Header,
}

Source

Block header structure.

There are several implementation subtleties involved:

The prev_phys_block field is only valid if the previous block is free.
The prev_phys_block field is actually stored at the end of the

previous block. It appears at the beginning of this structure only to
	simplify the implementation.
- The `next_free` / `prev_free` fields are only valid if the block is free.

Error :: enum u8 {
	None                      = 0,
	Invalid_Backing_Allocator = 1,
	Invalid_Alignment         = 2,
	Backing_Buffer_Too_Small  = 3,
	Backing_Buffer_Too_Large  = 4,
	Backing_Allocator_Error   = 5,
}

Source

Pool :: struct {
	data:      []u8,
	allocator: runtime.Allocator,
	next:      ^Pool,
}

Source

Constants

ALIGN_SIZE :: _ = 1 << ALIGN_SIZE_LOG2Source

BLOCK_HEADER_FREE :: uint = uint(1 << 0)Source

Since block sizes are always at least a multiple of 4, the two least significant bits of the size field are used to store the block status:

bit 0: whether block is busy or free
bit 1: whether previous block is busy or free

BLOCK_HEADER_OVERHEAD :: uint = uint(size_of(uint))Source

The size of the block header exposed to used blocks is the size field. The prev_phys_block field is stored inside the previous free block.

BLOCK_HEADER_PREV_FREE :: uint = uint(1 << 1)Source

BLOCK_SIZE_MAX :: uint = uint(1) << FL_INDEX_MAXSource

BLOCK_SIZE_MIN :: uint = uint(size_of(Block_Header) - size_of(^Block_Header))Source

A free block must be large enough to store its header minus the size of the prev_phys_block field, and no larger than the number of addressable bits for FL_INDEX.

BLOCK_START_OFFSET :: offset_of = offset_of(Block_Header, size) + size_of(Block_Header{}.size)Source

User data starts directly after the size field in a used block.

FL_INDEX_COUNT :: _ = FL_INDEX_MAX - FL_INDEX_SHIFT + 1Source

FL_INDEX_SHIFT :: _ = TLSF_SL_INDEX_COUNT_LOG2 + ALIGN_SIZE_LOG2Source

INITIAL_POOL_OVERHEAD :: 48Source

POOL_OVERHEAD :: _ = 2 * BLOCK_HEADER_OVERHEADSource

SL_INDEX_COUNT :: 1 << TLSF_SL_INDEX_COUNT_LOG2Source

SMALL_BLOCK_SIZE :: _ = 1 << FL_INDEX_SHIFTSource

TLSF_SL_INDEX_COUNT_LOG2 :: #config(TLSF_SL_INDEX_COUNT_LOG2, 5)Source

log2 of number of linear subdivisions of block sizes. Larger values require more memory in the control structure. Values of 4 or 5 are typical.

Procedures

allocator :: proc(t: ^Allocator) -> (runtime.Allocator)Source

allocator_proc :: proc(
	allocator_data: rawptr,
	mode:           runtime.Allocator_Mode,
	size:           int,
	alignment:      int,
	old_memory:     rawptr,
	old_size:       int,
	location:       _ = #caller_location,
) -> ([]u8, runtime.Allocator_Error)

Source

destroy :: proc(control: ^Allocator)Source

estimate_pool_from_size_alignment :: proc(count: int, size: int, alignment: int) -> (pool_size: int)Source

Tries to estimate a pool size sufficient for count allocations, each of size and with alignment.

estimate_pool_from_typeid :: proc(count: int, type: typeid) -> (pool_size: int)Source

Tries to estimate a pool size sufficient for count allocations of type.

ffs :: proc(word: u32) -> (bit: i32)Source

Exported solely to facilitate testing

fls :: proc(word: u32) -> (bit: i32)Source

Exported solely to facilitate testing

fls_uint :: proc(size: uint) -> (bit: i32)Source

Exported solely to facilitate testing

free_with_size :: proc(control: ^Allocator, ptr: rawptr, size: uint)Source

init_from_allocator :: proc(control: ^Allocator, backing: runtime.Allocator, initial_pool_size: int, new_pool_size: untyped integer = 0) -> (Error)

Source

init_from_buffer :: proc(control: ^Allocator, buf: []u8) -> (Error)Source

Procedure Groups

estimate_pool_size :: proc{estimate_pool_from_size_alignment, estimate_pool_from_typeid}Source

init :: proc{init_from_buffer, init_from_allocator}Source

mem_tlsf

Types

Constants

Procedures

Procedure Groups

Find anything

Settings