core/mem/tlsf package | Odin Programming Language

Two Level Segregated Fit memory allocator. Copyright 2024 Jeroen van Rijn <[email protected]>. Made available under tlsf's LICENSE (BSD 3-clause). List of contributors: Matt Conte: Original C implementation, see LICENSE file in this package Jeroen van Rijn: Source port

Collection Info

Collection: core
Path: mem/tlsf
Entries: 34

Source Files

Constants

16

ALIGN_SIZE #

ALIGN_SIZE :: 1 << ALIGN_SIZE_LOG2

ALIGN_SIZE_LOG2 #

ALIGN_SIZE_LOG2 :: 3 when size_of(uintptr) == 8 else 2

All allocation sizes and addresses are aligned to 4/8 bytes

BLOCK_HEADER_FREE #

BLOCK_HEADER_FREE :: uint(1 << 0)

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 #

BLOCK_HEADER_OVERHEAD :: uint(size_of(uint))

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 #

BLOCK_HEADER_PREV_FREE :: uint(1 << 1)

BLOCK_SIZE_MAX #

BLOCK_SIZE_MAX :: uint(1) << FL_INDEX_MAX

BLOCK_SIZE_MIN #

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

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 #

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

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

FL_INDEX_COUNT #

FL_INDEX_COUNT :: FL_INDEX_MAX - FL_INDEX_SHIFT + 1

FL_INDEX_MAX #

FL_INDEX_MAX :: 32 when size_of(uintptr) == 8 else 30

We can increase this to support larger allocation sizes, at the expense of more overhead in the TLSF structure

FL_INDEX_SHIFT #

FL_INDEX_SHIFT :: TLSF_SL_INDEX_COUNT_LOG2 + ALIGN_SIZE_LOG2

INITIAL_POOL_OVERHEAD #

INITIAL_POOL_OVERHEAD :: 48

POOL_OVERHEAD #

POOL_OVERHEAD :: 2 * BLOCK_HEADER_OVERHEAD

SL_INDEX_COUNT #

SL_INDEX_COUNT :: 1 << TLSF_SL_INDEX_COUNT_LOG2

SMALL_BLOCK_SIZE #

SMALL_BLOCK_SIZE :: 1 << FL_INDEX_SHIFT

TLSF_SL_INDEX_COUNT_LOG2 #

TLSF_SL_INDEX_COUNT_LOG2 :: #config(TLSF_SL_INDEX_COUNT_LOG2, 5)

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.

Config Values

1

TLSF_SL_INDEX_COUNT_LOG2 #

TLSF_SL_INDEX_COUNT_LOG2 :: #config(TLSF_SL_INDEX_COUNT_LOG2, 5)

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.

Types

4

Allocator #

Allocator :: Allocator

Block_Header #

Block_Header :: Block_Header

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 #

Error :: Error

Pool #

Pool :: Pool

Procedures

11

allocator #

@(require_results)

allocator :: proc(t: ^Allocator) -> Allocator {…}

allocator_proc #

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

destroy #

destroy :: proc(control: ^Allocator) {…}

estimate_pool_from_size_alignment #

estimate_pool_from_size_alignment :: proc(count: int, size: int, alignment: int) -> (pool_size: int) {…}

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

estimate_pool_from_typeid #

estimate_pool_from_typeid :: proc(count: int, type: typeid) -> (pool_size: int) {…}

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

ffs #

@(require_results)

ffs :: proc "contextless" (word: u32) -> (bit: i32) {…}

Exported solely to facilitate testing

fls #

@(require_results)

fls :: proc "contextless" (word: u32) -> (bit: i32) {…}

Exported solely to facilitate testing

fls_uint #

@(require_results)

fls_uint :: proc "contextless" (size: uint) -> (bit: i32) {…}

Exported solely to facilitate testing

free_with_size #

@(no_sanitize_address)

free_with_size :: proc(control: ^Allocator, ptr: rawptr, size: uint) {…}

init_from_allocator #

@(require_results)

init_from_allocator :: proc(control: ^Allocator, backing: Allocator, initial_pool_size: int, new_pool_size: int = 0) -> Error {…}

init_from_buffer #

@(require_results)

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

Procedure Groups

2

estimate_pool_size #

estimate_pool_size :: proc{
	estimate_pool_from_size_alignment,
	estimate_pool_from_typeid,
}

init #

init :: proc{
	init_from_buffer,
	init_from_allocator,
}