package core:mem/tlsf

⌘K
Ctrl+K
or
/

    Overview

    package mem_tlsf implements a Two Level Segregated Fit memory allocator.

    Copyright 2024 Jeroen van Rijn <nom@duclavier.com>.
    Made available under Odin's BSD-3 license.
    
    List of contributors:
    	Matt Conte:      Original C implementation, see LICENSE file in this package
    	Jeroen van Rijn: Source port
    

    Types

    Allocator ¶

    Allocator :: struct {
    	// Empty lists point at this block to indicate they are free.
    	block_null: Block_Header,
    	// Bitmaps for free lists.
    	fl_bitmap:  u32 `fmt:"-"`,
    	sl_bitmap:  [25]u32 `fmt:"-"`,
    	// Head of free lists.
    	blocks:     [25][32]^Block_Header `fmt:"-"`,
    	// 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,
    }
    Related Procedures With Parameters

    Block_Header ¶

    Block_Header :: struct {
    	prev_phys_block: ^Block_Header,
    	size:            uint,
    	// Next and previous free blocks.
    	next_free:       ^Block_Header,
    	prev_free:       ^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.

    Related Procedures With Parameters
    Related Procedures With Returns

    Error ¶

    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, 
    }
    Related Procedures With Returns

    Pool ¶

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

    Constants

    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: uintptr : 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

    POOL_OVERHEAD ¶

    POOL_OVERHEAD: uint : 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.

    Variables

    This section is empty.

    Procedures

    adjust_request_size ¶

    adjust_request_size :: proc(size, align: uint) -> (adjusted: uint) {…}
     

    Adjust an allocation size to be aligned to word size, and no smaller than internal minimum.

    adjust_request_size_with_err ¶

    adjust_request_size_with_err :: proc(size, align: uint) -> (adjusted: uint, err: runtime.Allocator_Error) {…}
     

    Adjust an allocation size to be aligned to word size, and no smaller than internal minimum.

    align_down ¶

    align_down :: proc(x, align: uint) -> (aligned: uint) {…}

    align_ptr ¶

    align_ptr :: proc(ptr: rawptr, align: uint) -> (aligned: rawptr) {…}

    align_up ¶

    align_up :: proc(x, align: uint) -> (aligned: uint) {…}

    alloc_bytes ¶

    alloc_bytes :: proc(control: ^Allocator, size: uint, align: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

    alloc_bytes_non_zeroed ¶

    alloc_bytes_non_zeroed :: proc(control: ^Allocator, size: uint, align: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

    allocator ¶

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

    allocator_proc ¶

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

    block_absorb ¶

    block_absorb :: proc(prev: ^Block_Header, block: ^Block_Header) -> (absorbed: ^Block_Header) {…}
     

    Absorb a free block's storage into an adjacent previous free block.

    block_can_split ¶

    block_can_split :: proc(block: ^Block_Header, size: uint) -> (can_split: bool) {…}

    block_from_ptr ¶

    block_from_ptr :: proc(ptr: rawptr) -> (block_ptr: ^Block_Header) {…}

    block_insert ¶

    block_insert :: proc(control: ^Allocator, block: ^Block_Header) {…}
     

    Insert a given block into the free list.

    block_is_free ¶

    block_is_free :: proc "contextless" (block: ^Block_Header) -> (is_free: bool) {…}

    block_is_last ¶

    block_is_last :: proc "contextless" (block: ^Block_Header) -> (is_last: bool) {…}

    block_is_prev_free ¶

    block_is_prev_free :: proc "contextless" (block: ^Block_Header) -> (is_prev_free: bool) {…}
    block_link_next :: proc(block: ^Block_Header) -> (next: ^Block_Header) {…}
     

    Link a new block with its physical neighbor, return the neighbor.

    block_locate_free ¶

    block_locate_free :: proc(control: ^Allocator, size: uint) -> (block: ^Block_Header) {…}

    block_mark_as_free ¶

    block_mark_as_free :: proc(block: ^Block_Header) {…}

    block_mark_as_used ¶

    block_mark_as_used :: proc(block: ^Block_Header) {…}

    block_merge_next ¶

    block_merge_next :: proc(control: ^Allocator, block: ^Block_Header) -> (merged: ^Block_Header) {…}
     

    Merge a just-freed block with an adjacent free block.

    block_merge_prev ¶

    block_merge_prev :: proc(control: ^Allocator, block: ^Block_Header) -> (merged: ^Block_Header) {…}
     

    Merge a just-freed block with an adjacent previous free block.

    block_next ¶

    block_next :: proc(block: ^Block_Header) -> (next: ^Block_Header) {…}
     

    Return location of next existing block.

    block_prepare_used ¶

    block_prepare_used :: proc(control: ^Allocator, block: ^Block_Header, size: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

    block_prev ¶

    block_prev :: proc(block: ^Block_Header) -> (prev: ^Block_Header) {…}
     

    Return location of previous block.

    block_remove ¶

    block_remove :: proc(control: ^Allocator, block: ^Block_Header) {…}
     

    Remove a given block from the free list.

    block_set_free ¶

    block_set_free :: proc "contextless" (block: ^Block_Header) {…}

    block_set_prev_free ¶

    block_set_prev_free :: proc "contextless" (block: ^Block_Header) {…}

    block_set_prev_used ¶

    block_set_prev_used :: proc "contextless" (block: ^Block_Header) {…}

    block_set_size ¶

    block_set_size :: proc "contextless" (block: ^Block_Header, size: uint) {…}

    block_set_used ¶

    block_set_used :: proc "contextless" (block: ^Block_Header) {…}

    block_size ¶

    block_size :: proc "contextless" (block: ^Block_Header) -> (size: uint) {…}

    block_split ¶

    block_split :: proc(block: ^Block_Header, size: uint) -> (remaining: ^Block_Header) {…}
     

    Split a block into two, the second of which is free.

    block_to_ptr ¶

    block_to_ptr :: proc(block: ^Block_Header) -> (ptr: rawptr) {…}

    block_trim_free ¶

    block_trim_free :: proc(control: ^Allocator, block: ^Block_Header, size: uint) {…}
     

    Trim any trailing block space off the end of a free block, return to pool.

    block_trim_free_leading ¶

    block_trim_free_leading :: proc(control: ^Allocator, block: ^Block_Header, size: uint) -> (remaining: ^Block_Header) {…}
     

    Trim leading block space, return to pool.

    block_trim_used ¶

    block_trim_used :: proc(control: ^Allocator, block: ^Block_Header, size: uint) {…}
     

    Trim any trailing block space off the end of a used block, return to pool.

    clear ¶

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

    Clear control structure and point all empty lists at the null block

    destroy ¶

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

    ffs ¶

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

    fls ¶

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

    fls_uint ¶

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

    free_with_size ¶

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

    init_from_allocator ¶

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

    init_from_buffer ¶

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

    insert_free_block ¶

    insert_free_block :: proc(control: ^Allocator, block: ^Block_Header, fl: i32, sl: i32) {…}
     

    Insert a free block into the free block list.

    mapping_insert ¶

    mapping_insert :: proc(size: uint) -> (fl, sl: i32) {…}

    mapping_round ¶

    mapping_round :: proc(size: uint) -> (rounded: uint) {…}
    mapping_search :: proc(size: uint) -> (fl, sl: i32) {…}
     

    This version rounds up to the next block size (for allocations)

    offset_to_block ¶

    offset_to_block :: proc(ptr: rawptr, size: uint) -> (block: ^Block_Header) {…}
     

    Return location of next block after block of given size.

    offset_to_block_backwards ¶

    offset_to_block_backwards :: proc(ptr: rawptr, size: uint) -> (block: ^Block_Header) {…}

    pool_add ¶

    pool_add :: proc(control: ^Allocator, pool: []u8) -> (err: Error) {…}

    pool_remove ¶

    pool_remove :: proc(control: ^Allocator, pool: []u8) {…}

    remove_free_block ¶

    remove_free_block :: proc(control: ^Allocator, block: ^Block_Header, fl: i32, sl: i32) {…}
     

    Remove a free block from the free list.

    resize ¶

    resize :: proc(control: ^Allocator, ptr: rawptr, old_size, new_size: uint, alignment: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

    resize_non_zeroed ¶

    resize_non_zeroed :: proc(control: ^Allocator, ptr: rawptr, old_size, new_size: uint, alignment: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

    search_suitable_block ¶

    search_suitable_block :: proc(control: ^Allocator, fli, sli: ^i32) -> (block: ^Block_Header) {…}

    Procedure Groups

    Source Files

    Generation Information

    Generated with odin version dev-2024-10 (vendor "odin") Windows_amd64 @ 2024-10-17 21:11:09.451020100 +0000 UTC