#include <tlsf_allocator.h>

Inheritance diagram for pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >:

Public Member Functions
constexpr	TlsfAllocator ()
	Constexpr constructor. Callers must explicitly call `Init`.

	TlsfAllocator (ByteSpan region)

Public Member Functions inherited from pw::allocator::BlockAllocator< BlockType_ >
Range	blocks () const
	Returns a `Range` of blocks tracking the memory of this allocator.

void	Init (ByteSpan region)

Fragmentation	MeasureFragmentation () const
	Returns fragmentation information for the block allocator's memory region.

Public Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
	GenericBlockAllocator (const GenericBlockAllocator &)=delete

GenericBlockAllocator &	operator= (const GenericBlockAllocator &)=delete

	GenericBlockAllocator (GenericBlockAllocator &&)=delete

GenericBlockAllocator &	operator= (GenericBlockAllocator &&)=delete

Public Member Functions inherited from pw::Allocator
void *	Allocate (Layout layout)

template<typename T , int &... kExplicitGuard, typename... Args>
std::enable_if_t<!std::is_array_v< T >, T * >	New (Args &&... args)

template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
ElementType *	New (size_t count)

template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
ElementType *	New (size_t count, size_t alignment)

template<typename T >
T *	NewArray (size_t count)

template<typename T >
T *	NewArray (size_t count, size_t alignment)

template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
UniquePtr< T >	MakeUnique (Args &&... args)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T >	MakeUnique (size_t size)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T >	MakeUnique (size_t size, size_t alignment)

template<typename T >
UniquePtr< T[]>	MakeUniqueArray (size_t size)

template<typename T >
UniquePtr< T[]>	MakeUniqueArray (size_t size, size_t alignment)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_bounded_array_v< T >, int > = 0, typename... Args>
void	MakeUnique (Args &&...)=delete

template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
SharedPtr< T >	MakeShared (Args &&... args)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
SharedPtr< T >	MakeShared (size_t size)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
SharedPtr< T >	MakeShared (size_t size, size_t alignment)

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_bounded_array_v< T >, int > = 0, typename... Args>
std::enable_if_t< is_bounded_array_v< T > >	MakeShared (Args &&...)=delete

bool	Resize (void *ptr, size_t new_size)

bool	Resize (void *ptr, Layout layout, size_t new_size)

void *	Reallocate (void *ptr, Layout new_layout)

void *	Reallocate (void *ptr, Layout old_layout, size_t new_size)

size_t	GetAllocated () const

Public Member Functions inherited from pw::Deallocator
constexpr const Capabilities &	capabilities () const

bool	HasCapability (Capability capability) const
	Returns whether a given capabilityis enabled for this object.

void	Deallocate (void *ptr)

void	Deallocate (void *ptr, Layout layout)

template<typename T >
void	Delete (T *ptr)

StatusWithSize	GetCapacity () const

bool	IsEqual (const Deallocator &other) const

template<typename T , int &... kExplicitGuard, std::enable_if_t< is_bounded_array_v< T >, int > = 0, typename... Args>
void	WrapUnique (Args &&...)=delete

Private Member Functions
BlockResult< BlockType >	ChooseBlock (Layout layout) override

void	ReserveBlock (BlockType &block) override

void	RecycleBlock (BlockType &block) override

Additional Inherited Members
Public Types inherited from pw::allocator::BlockAllocator< BlockType_ >
using	BlockType = BlockType_

using	Range = typename BlockType::Range

Public Types inherited from pw::Deallocator
using	Capabilities = allocator::Capabilities

using	Capability = allocator::Capability

using	Layout = allocator::Layout

Static Public Attributes inherited from pw::allocator::BlockAllocator< BlockType_ >
static constexpr Capabilities	kCapabilities

static constexpr size_t	kPoisonInterval = PW_ALLOCATOR_BLOCK_POISON_INTERVAL

Protected Member Functions inherited from pw::allocator::BlockAllocator< BlockType_ >
void	Init (BlockType *begin)

template<typename Ptr >
internal::copy_const_ptr_t< Ptr, BlockType * >	FromUsableSpace (Ptr ptr) const

virtual void	DeallocateBlock (BlockType *&&block)

Protected Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
constexpr	GenericBlockAllocator (Capabilities capabilities)

Protected Member Functions inherited from pw::Allocator
constexpr	Allocator ()=default
	TODO(b/326509341): Remove when downstream consumers migrate.

constexpr	Allocator (const Capabilities &capabilities)

Protected Member Functions inherited from pw::Deallocator
constexpr	Deallocator ()=default
	TODO(b/326509341): Remove when downstream consumers migrate.

constexpr	Deallocator (const Capabilities &capabilities)

template<typename T , std::enable_if_t<!std::is_array_v< T >, int > = 0>
UniquePtr< T >	WrapUnique (T *ptr)

template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T >	WrapUnique (ElementType *ptr, size_t size)

template<typename T >
UniquePtr< T[]>	WrapUniqueArray (T *ptr, size_t size)

Static Protected Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
template<typename BlockType >
static constexpr Capabilities	GetCapabilities ()

static void	CrashOnAllocated (const void *allocated)

static void	CrashOnOutOfRange (const void *freed)

static void	CrashOnDoubleFree (const void *freed)
	Crashes with an informational message that a given block was freed twice.

Static Protected Attributes inherited from pw::Deallocator
template<typename T >
static constexpr bool	is_bounded_array_v

template<typename T >
static constexpr bool	is_unbounded_array_v

Detailed Description

template<typename BlockType = TlsfBlock<uint32_t>, size_t kMinSize = TlsfDefaults::kMinSize, size_t kNumShelves = TlsfDefaults::kNumShelves>
class pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >

Two-layered, segregated fit allocator.

This allocator uses a two-dimensional array of buckets to quickly satisfy memory allocations with best-fit blocks as described by http://www.gii.upv.es/tlsf/files/papers/ecrts04_tlsf.pdf

This class refers to the "second-level arrays" in that paper as "shelves". Each shelf holds an array of Buckets, and an instance of this class holds an array of shelves. Conceptually, buckets can be thought of as being organized on a set of "shelves", with each shelf having 16 buckets arranged from smallest maximum inner size to largest. The smallest maximum inner size on a shelf is a power of 2, and the shelves are arranged from the kMinSize on the "bottom" to the largest maximum inner sizes on the "top". The last bucket on the topmost shelf is unbounded to handle any blocks of arbitrary size.

For example, if kMinSize is 64, and kNumShelves is 10, than the maximum inner sizes of buckets on each shelf could be represented as:

{
  shelves_[9]: { 32k, 34k, ..., 62k, inf },
          ...: { ..., ..., ..., ..., ... },
  shelves_[1]: { 128, 136, ..., 240, 248 },
  shelves_[0]: {  64,  68, ..., 120, 124 },
}

Template Parameters

BlockType	Block implementation
kMinSize	Maximum inner size of blocks in the first bucket on lowest shelf.
kNumShelves	Number of rows in the two-dimensional array.

Constructor & Destructor Documentation

◆ TlsfAllocator()

template<typename BlockType = TlsfBlock<uint32_t>, size_t kMinSize = TlsfDefaults::kMinSize, size_t kNumShelves = TlsfDefaults::kNumShelves>

pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >::TlsfAllocator ( ByteSpan region )

inlineexplicit

Non-constexpr constructor that automatically calls Init.

Parameters

[in] region Region of memory to use when satisfying allocation requests. The region MUST be valid as an argument to BlockType::Init.

Member Function Documentation

◆ ChooseBlock()

template<typename BlockType , size_t kMinSize, size_t kNumShelves>

BlockResult< BlockType > pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >::ChooseBlock ( Layout layout )

overrideprivatevirtual

Selects a free block to allocate from.

This method represents the allocator-specific strategy of choosing which block should be used to satisfy allocation requests. If the returned result indicates success, block will be replaced by the chosen block.

Parameters

block	Used to return the chosen block.
layout	Same as `Allocator::Allocate`.

Implements pw::allocator::BlockAllocator< BlockType_ >.

◆ RecycleBlock()

template<typename BlockType , size_t kMinSize, size_t kNumShelves>

void pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >::RecycleBlock ( BlockType & block )

overrideprivatevirtual

Indicates that a block is now free.

Does nothing by default. Derived class may overload to do additional bookkeeeping.

Parameters

block The block being freed.

Reimplemented from pw::allocator::BlockAllocator< BlockType_ >.

◆ ReserveBlock()

template<typename BlockType , size_t kMinSize, size_t kNumShelves>

void pw::allocator::TlsfAllocator< BlockType, kMinSize, kNumShelves >::ReserveBlock ( BlockType & block )

overrideprivatevirtual

Indicates that a block will no longer be free.

Does nothing by default. Derived class may overload to do additional bookkeeeping.

Parameters

block The block being freed.

Reimplemented from pw::allocator::BlockAllocator< BlockType_ >.

The documentation for this class was generated from the following file:

pw_allocator/public/pw_allocator/tlsf_allocator.h

Public Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ TlsfAllocator()

Member Function Documentation

◆ ChooseBlock()

◆ RecycleBlock()

◆ ReserveBlock()