Overview

template<typename BlockType = FirstFitBlock<uintptr_t>>
class pw::allocator::FirstFitAllocator< BlockType >

Block allocator that uses a "first-fit" allocation strategy split between large and small allocations.

In this strategy, the allocator handles an allocation request by starting at the beginning of the range of blocks and looking for the first one which can satisfy the request.

Optionally, callers may set a "threshold" value. If set, requests smaller than the threshold are satisfied using the last compatible block. This separates large and small requests and can reduce overall fragmentation.

Inheritance diagram for pw::allocator::FirstFitAllocator< BlockType >:

Public Types
using	Base = BlockAllocator< BlockType >

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

using	Range = typename BlockType::Range

Public Types inherited from pw::Allocator
using	Fragmentation = allocator::Fragmentation

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

using	Capability = allocator::Capability

using	Layout = allocator::Layout

Public Member Functions
constexpr	FirstFitAllocator ()=default
	Constexpr constructor. Callers must explicitly call `Init`.

	FirstFitAllocator (ByteSpan region)

	FirstFitAllocator (ByteSpan region, size_t threshold)

void	set_threshold (size_t threshold)
	Sets the threshold value for which requests are considered "large".

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)

size_t	GetMaxAllocatable ()

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, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
T *	New (Args &&... args)

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

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)
	Constructs an `alignment`-byte aligned array of `count` objects.

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 , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T >	MakeUnique (size_t size)

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

template<typename T , std::enable_if_t< is_bounded_array_v< T >, int > = 0>
UniquePtr< T >	MakeUnique ()

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 , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
SharedPtr< T >	MakeShared (size_t size)

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

template<typename T , std::enable_if_t< is_bounded_array_v< T >, int > = 0>
SharedPtr< T >	MakeShared ()

bool	Resize (void *ptr, size_t new_size)

void *	Reallocate (void *ptr, Layout new_layout)

size_t	GetAllocated () const

std::optional< Fragmentation >	MeasureFragmentation () const
	Returns fragmentation information for the allocator's memory region.

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

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

void	Deallocate (void *ptr)

template<typename ElementType >
void	DeleteArray (ElementType *ptr, size_t count)

StatusWithSize	GetCapacity () const

bool	IsEqual (const Deallocator &other) const

template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0>
void	Delete (T *ptr)

template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_bounded_array_v< T >, int > = 0>
void	Delete (ElementType *ptr)

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

Private Member Functions
size_t	DoGetMaxAllocatable () override

BlockResult< BlockType >	ChooseBlock (Layout layout) override

void	ReserveBlock (BlockType &block) override

void	RecycleBlock (BlockType &block) override

Additional Inherited Members
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 *	DoAllocate (Layout layout) override

void	DoDeallocate (void *ptr) override

bool	DoResize (void *ptr, size_t new_size) override

size_t	DoGetAllocated () const override

std::optional< Fragmentation >	DoMeasureFragmentation () const override
	Returns fragmentation information for the allocator's memory region.

Result< Layout >	DoGetInfo (InfoType info_type, const void *ptr) const override

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)

virtual void *	DoAllocate (Layout layout)=0

virtual bool	DoResize (void *ptr, size_t new_size)

virtual void *	DoReallocate (void *ptr, Layout new_layout)

virtual size_t	DoGetAllocated () const

virtual std::optional< Fragmentation >	DoMeasureFragmentation () const
	Returns fragmentation information for the allocator's memory region.

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

constexpr	Deallocator (const Capabilities &capabilities)

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 = ::pw::is_bounded_array_v<T>

template<typename T >
static constexpr bool	is_unbounded_array_v = ::pw::is_unbounded_array_v<T>

Constructor & Destructor Documentation

◆ FirstFitAllocator() [1/2]

template<typename BlockType = FirstFitBlock<uintptr_t>>

pw::allocator::FirstFitAllocator< BlockType >::FirstFitAllocator ( ByteSpan region )

inline

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.

◆ FirstFitAllocator() [2/2]

template<typename BlockType >

pw::allocator::FirstFitAllocator< BlockType >::FirstFitAllocator	(	ByteSpan	region,
		size_t	threshold
	)

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`.
[in]	threshold	Value for which requests are considered "large".

Member Function Documentation

◆ ChooseBlock()

template<typename BlockType >

BlockResult< BlockType > pw::allocator::FirstFitAllocator< BlockType >::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_ >.

◆ DoGetMaxAllocatable()

template<typename BlockType >

size_t pw::allocator::FirstFitAllocator< BlockType >::DoGetMaxAllocatable

overrideprivatevirtual

Returns the largest single allocation that can succeed, given the current state of the allocator.

The largest allocation possible at any given time is the inner size of the largest free block. This method may be expensive to call if the block allocator implementation does not track its largest block. As a result, it should primarily be used for diagnostic purposes after an allocation failure, e.g.

auto my_object = block_allocator.MakeUnique<MyObject>(my_args);
if (my_object == nullptr) {
  PW_LOG("failed to allocate: needed %zu bytes, but only have %zu",
    sizeof(MyObject), block_allocator.GetMaxAllocatable());
}

Note that this method does not consider alignment. An allocation with a large alignment requirement may fail even when a large enough block is available if that block cannot satisfy the alignment requirement.

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

◆ RecycleBlock()

template<typename BlockType = FirstFitBlock<uintptr_t>>

void pw::allocator::FirstFitAllocator< BlockType >::RecycleBlock ( BlockType & block )

inlineoverrideprivatevirtual

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 = FirstFitBlock<uintptr_t>>

void pw::allocator::FirstFitAllocator< BlockType >::ReserveBlock ( BlockType & block )

inlineoverrideprivatevirtual

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/first_fit.h

Overview

Public Types

Public Member Functions

Private Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ FirstFitAllocator() [1/2]

◆ FirstFitAllocator() [2/2]

Member Function Documentation

◆ ChooseBlock()

◆ DoGetMaxAllocatable()

◆ RecycleBlock()

◆ ReserveBlock()