API reference#

pw_allocator: Flexible, safe, and measurable memory allocation

This module provides the following:

Generic allocator interfaces that can be injected into routines that need dynamic memory. These include Allocator, as well as the Layout type that is passed to it and the UniquePtr returned from it.
Concrete allocator implementations used to provide memory dynamically.
“Forwarding” allocators, as described by Forwarding allocator concept.
Additional allocator utility classes. These are typically used by allocator implementers.
Test utilities for testing allocator implementations. These are typically used by allocator implementers.

Core interfaces#

This module defines several types as part of a generic interface for memory users.

Layout#

A request for memory includes a requested size and alignment as a Layout:

class Layout#

Describes the layout of a block of memory.

Layouts are passed to allocators, and consist of a (possibly padded) size and a power-of-two alignment no larger than the size. Layouts can be constructed for a type T using Layout::Of.

Example:

struct MyStruct {
  uint8_t field1[3];
  uint32_t field2[3];
};
constexpr Layout layout_for_struct = Layout::Of<MyStruct>();

Public Static Functions

template<typename T> static inline constexpr Layout Of()#: Creates a Layout for the given type.

static inline constexpr Layout Unwrap(const Result<Layout> &result)#: If the result is okay, returns its contained layout; otherwise, returns a default layout.

Allocator#

Allocator is the most commonly used interface. It can be used to request memory of different layouts:

class Allocator : public pw::Deallocator #

Abstract interface for variable-layout memory allocation.

The interface makes no guarantees about its implementation. Consumers of the generic interface must not make any assumptions around allocator behavior, thread safety, or performance.

Subclassed by pw::allocator::SynchronizedAllocator< pw::sync::Mutex >, pw::allocator::TrackingAllocator< internal::AllMetrics >, pw::allocator::test::AllocatorForTest< kBufferSize, BlockType, internal::AllMetrics >, pw::allocator::test::SynchronizedAllocatorForTest< 1024 >, pw::allocator::BuddyAllocator< kMinOuterSize_, kNumBuckets >, pw::allocator::BumpAllocator, pw::allocator::FallbackAllocator, pw::allocator::LibCAllocator, pw::allocator::NullAllocator, pw::allocator::SynchronizedAllocator< LockType >, pw::allocator::TrackingAllocator< MetricsType >, pw::allocator::internal::GenericBlockAllocator, pw::allocator::test::AllocatorForTest< kBufferSize, BlockType_, MetricsType >, pw::allocator::test::SynchronizedAllocatorForTest< kBufferSize, BlockType_, MetricsType >

Public Functions

inline void *Allocate(Layout layout)#

Allocates a block of memory with the specified size and alignment.

Returns nullptr if the allocation cannot be made, or the layout has a size of 0.

Parameters:: layout – [in] Describes the memory to be allocated.

template<typename T, int&... ExplicitGuard, typename ...Args> inline T *New(Args&&... args)#

Constructs and object of type T from the given args

The return value is nullable, as allocating memory for the object may fail. Callers must check for this error before using the resulting pointer.

Parameters:: args... – [in] Arguments passed to the object constructor.

template<typename T, int&... ExplicitGuard> inline T *NewArray(size_t size)#

Constructs an array of type T from the given args and size

The return value is nullable, as allocating memory for the object may fail. Callers must check for this error before using the resulting pointer.

Parameters:: size – [in] The size of the array to allocate.

template<typename T, int&... ExplicitGuard, typename ...Args> inline UniquePtr<T> MakeUnique(Args&&... args)#

Constructs and object of type T from the given args, and wraps it in a UniquePtr

The returned value may contain null if allocating memory for the object fails. Callers must check for null before using the UniquePtr.

Parameters:: args... – [in] Arguments passed to the object constructor.

template<typename T, int&... ExplicitGuard> inline UniquePtr<T[]> MakeUniqueArray(size_t size)#

Constructs an array of type T from the given args and size, and wraps it in a UniquePtr

The returned value may contain null if allocating memory for the object fails. Callers must check for null before using the UniquePtr.

Parameters:: size – [in] The size of the array to allocate.

inline bool Resize(void *ptr, size_t new_size)#

Modifies the size of an previously-allocated block of memory without copying any data.

Returns true if its size was changed without copying data to a new allocation; otherwise returns false.

In particular, it always returns true if the old_layout.size() equals new_size, and always returns false if the given pointer is null, the old_layout.size() is 0, or the new_size is 0.

Parameters:

ptr – [in] Pointer to previously-allocated memory.
new_size – [in] Requested new size for the memory allocation.

inline bool Resize(void *ptr, Layout layout, size_t new_size)#: Deprecated version of Resize that takes a Layout. Do not use this method. It will be removed. TODO(b/326509341): Remove when downstream consumers migrate.

inline void *Reallocate(void *ptr, Layout new_layout)#

Modifies the size of a previously-allocated block of memory.

Returns pointer to the modified block of memory, or nullptr if the memory could not be modified.

The data stored by the memory being modified must be trivially copyable. If it is not, callers should themselves attempt to Resize, then Allocate, move the data, and Deallocate as needed.

If nullptr is returned, the block of memory is unchanged. In particular, if the new_layout has a size of 0, the given pointer will NOT be deallocated.

TODO(b/331290408): This error condition needs to be better communicated to module users, who may assume the pointer is freed.

Unlike Resize, providing a null pointer will return a new allocation.

If the request can be satisfied using Resize, the alignment parameter may be ignored.

Parameters:

ptr – [in] Pointer to previously-allocated memory.
new_layout – [in] Describes the memory to be allocated.

inline void *Reallocate(void *ptr, Layout old_layout, size_t new_size)#: Deprecated version of Reallocate that takes a Layout. Do not use this method. It will be removed. TODO(b/326509341): Remove when downstream consumers migrate.

inline size_t GetAllocated() const#: Returns the total bytes that have been allocated by this allocator, or size_t(-1) if this allocator does not track its total allocated bytes.

Pool#

Pool differs from Allocator in that it can be used to request memory of a single, fixed layout:

class Pool : public pw::Deallocator #

Abstract interface for fixed-layout memory allocation.

The interface makes no guarantees about its implementation. Consumers of the generic interface must not make any assumptions around allocator behavior, thread safety, or performance.

Subclassed by pw::allocator::AllocatorAsPool, pw::allocator::ChunkPool

Public Functions

inline void *Allocate()#

Returns a chunk of memory with this object’s fixed layout.

Like pw::allocator::Allocate, returns null if memory is exhausted.

Return values:: The – allocated memory.

Deallocator#

Both Allocator and Pool derive from and extend Deallocator. This type is intended for allocator implementers and not for module consumers.

class Deallocator#

Abstract interface for releasing memory.

Subclassed by pw::Allocator, pw::allocator::Pool

Public Functions

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

inline void Deallocate(void *ptr)#

Releases a previously-allocated block of memory.

The given pointer must have been previously provided by this memory resource; otherwise the behavior is undefined.

Parameters:: ptr – [in] Pointer to previously-allocated memory.

inline void Deallocate(void *ptr, Layout layout)#: Deprecated version of Deallocate that takes a Layout. Do not use this method. It will be removed. TODO(b/326509341): Remove when downstream consumers migrate.

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

Destroys the object at ptr and deallocates the associated memory.

The given pointer must have been previously obtained from a call to New using the same object; otherwise the behavior is undefined.

Parameters:: ptr – [in] Pointer to previously-allocated object.

inline StatusWithSize GetCapacity() const#

Returns the total amount of memory provided by this object.

This is an optional method. Some memory providers may not have an easily defined capacity, e.g. the system allocator. If implemented, the returned capacity may be less than the memory originally given to an allocator, e.g. if the allocator must align the region of memory, its capacity may be reduced.

inline bool IsEqual(const Deallocator &other) const#

Returns whether the given object is the same as this one.

This method is used instead of operator== in keeping with std::pmr::memory_resource::is_equal. There currently is no corresponding virtual DoIsEqual, as objects that would require dynamic_cast to properly determine equality are not supported. This method will allow the interface to remain unchanged should a future need for such objects arise.

Parameters:: other – [in] Object to compare with this object.

Capabilities#

Types deriving from MemoryResource can communicate about their optional methods and behaviors using Capabilities. This type is intended for allocator implementers and not for module consumers.

class Capabilities#

A collection of Capabilitys.

Concrete allocators should declare a constant set of capabilities, and pass it to the Allocator constructor.

class MyConcreteAllocator : public Allocator {
 public:
  static constexpr Capabilities kCapabilities = kCapability1 | kCapability2;

  MyConcreteAllocator() : Allocator(kCapabilities) {}
};

Forwarding allocators should pass the underlying allocator’s capabilities, potentially with modifications:

class MyForwardingAllocator : public Allocator {
 public:
  MyForwardingAllocator(Allocator& allocator)
    : Allocator(allocator.capabilities() | kCapability3),
      allocator_(allocator) {}
};

UniquePtr#

The UniquePtr smart pointer type can be created by any type deriving from MemoryResource.

template<typename T> class UniquePtr : public pw::allocator::internal::BaseUniquePtr#

An RAII pointer to a value of type T stored in memory provided by a Deallocator.

This is analogous to std::unique_ptr, but includes a few differences in order to support Deallocator and encourage safe usage. Most notably, UniquePtr<T> cannot be constructed from a T*.

Public Functions

inline constexpr UniquePtr()#

Creates an empty (nullptr) instance.

NOTE: Instances of this type are most commonly constructed using Deallocator::MakeUnique.

inline constexpr UniquePtr(std::nullptr_t)#

Creates an empty (nullptr) instance.

NOTE: Instances of this type are most commonly constructed using Deallocator::MakeUnique.

template<typename U> inline UniquePtr(UniquePtr &&other) noexcept#

Move-constructs a UniquePtr<T> from a UniquePtr.

This allows not only pure move construction where T == U, but also converting construction where T is a base class of U, like UniquePtr<Base> base(deallocator.MakeUnique<Child>());.

template<typename U> inline UniquePtr &operator=(UniquePtr &&other) noexcept#

Move-assigns a UniquePtr<T> from a UniquePtr.

This operation destructs and deallocates any value currently stored in this.

This allows not only pure move assignment where T == U, but also converting assignment where T is a base class of U, like UniquePtr<Base> base = deallocator.MakeUnique<Child>();.

inline UniquePtr &operator=(std::nullptr_t)#

Sets this UniquePtr to null, destructing and deallocating any currently-held value.

After this function returns, this UniquePtr will be in an “empty” (nullptr) state until a new value is assigned.

inline ~UniquePtr()#: Destructs and deallocates any currently-held value.

inline Deallocator *deallocator() const#: Returns a pointer to the object that can destroy the value.

inline UnderlyingType *Release()#

Releases a value from the UniquePtr without destructing or deallocating it.

After this call, the object will have an “empty” (nullptr) value.

inline void Reset()#

Destructs and deallocates any currently-held value.

After this function returns, this UniquePtr will be in an “empty” (nullptr) state until a new value is assigned.

explicit operator bool() const = delete#

operator bool is not provided in order to ensure that there is no confusion surrounding if (foo) vs. if (*foo).

nullptr checking should instead use if (foo == nullptr).

inline bool operator==(std::nullptr_t) const#: Returns whether this UniquePtr is in an “empty” (nullptr) state.

inline bool operator!=(std::nullptr_t) const#: Returns whether this UniquePtr is not in an “empty” (nullptr) state.

inline UnderlyingType *get()#: Returns the underlying (possibly null) pointer.

inline const UnderlyingType *get() const#: Returns the underlying (possibly null) pointer.

inline UnderlyingType *operator->()#

Permits accesses to members of T via my_unique_ptr->Member.

The behavior of this operation is undefined if this UniquePtr is in an “empty” (nullptr) state.

inline UnderlyingType &operator*()#

Returns a reference to any underlying value.

The behavior of this operation is undefined if this UniquePtr is in an “empty” (nullptr) state.

template<typename U = T, typename = std::enable_if_t<std::is_array_v, bool>> inline UnderlyingType &operator[](size_t index)#

Returns a reference to the element at the given index.

The behavior of this operation is undefined if this UniquePtr is in an “empty” (nullptr) state.

template<typename U = T, typename = std::enable_if_t<std::is_array_v, bool>> inline size_t size() const#

Returns the number of elements allocated.

This will assert if it is called on a non-array type UniquePtr.

inline UniquePtr(PrivateConstructorType, UnderlyingType *value, Deallocator *deallocator)#

Private constructor that is public only for use with emplace and other in-place construction functions.

Constructs a UniquePtr from an already-allocated value.

NOTE: Instances of this type are most commonly constructed using Deallocator::MakeUnique.

inline UniquePtr(PrivateConstructorType, UnderlyingType *value, Deallocator *deallocator, size_t size)#

Private constructor that is public only for use with emplace and other in-place construction functions.

Constructs a UniquePtr from an already-allocated value and size.

NOTE: Instances of this type are most commonly constructed using Deallocator::MakeUnique.

Friends

friend class Deallocator

Allocator implementations#

This module provides several concrete allocator implementations of the Allocator interface:

BlockAllocator#

template<typename BlockType_> class BlockAllocator : public pw::allocator::internal::GenericBlockAllocator#

A memory allocator that uses a list of blocks.

This class does not implement ChooseBlock and cannot be used directly. Instead, use one of its specializations.

NOTE!! Do NOT use memory returned from this allocator as the backing for another allocator. If this is done, the Query method may incorrectly think pointers returned by that allocator were created by this one, and report that this allocator can de/reallocate them.

Subclassed by pw::allocator::BestFitAllocator< BlockType >, pw::allocator::BucketAllocator< BlockType, kMinInnerSize, kNumBuckets >, pw::allocator::FirstFitAllocator< BlockType >, pw::allocator::WorstFitAllocator< BlockType >

Public Functions

Range blocks() const#: Returns a Range of blocks tracking the memory of this allocator.

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

void Init(ByteSpan region)#

Sets the memory region to be used by this allocator.

This method will instantiate an initial block using the memory region.

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

inline void Init(BlockType *begin)#

Sets the blocks to be used by this allocator.

This method will use the sequence of blocks including and following begin. These blocks which must be valid.

Parameters:: begin – [in] The first block for this allocator. The block must not have a previous block.

void Init(BlockType *begin, BlockType *end)#

Sets the blocks to be used by this allocator.

This method will use the sequence blocks as-is, which must be valid.

Parameters:

begin – [in] The first block for this allocator.
end – [in] The last block for this allocator. May be null, in which the sequence including and following begin is used. If not null, the block must not have a next block.

void Reset()#

Resets the allocator to an uninitialized state.

At the time of the call, there MUST NOT be any outstanding allocated blocks from this allocator.

FirstFitAllocator#

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

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.

Public Functions

constexpr FirstFitAllocator() = default#: Constexpr constructor. Callers must explicitly call Init.

inline FirstFitAllocator(ByteSpan region)#

Non-constexpr constructor that automatically calls Init.

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

inline FirstFitAllocator(ByteSpan region, size_t threshold)#

Non-constexpr constructor that automatically calls Init.

Parameters:

region – [in] Region of memory to use when satisfying allocation requests. The region MUST be valid as an argument to BlockType::Init.
threshold – [in] Value for which requests are considered “large”.

inline void set_threshold(size_t threshold)#: Sets the threshold value for which requests are considered “large”.

BestFitAllocator#

template<typename BlockType = BestFitBlock<uintptr_t>> class BestFitAllocator : public pw::allocator::BlockAllocator<BestFitBlock<uintptr_t>>#

Block allocator that uses a “best-fit” allocation strategy.

In this strategy, the allocator handles an allocation request by looking at all unused blocks and finding the smallest one which can satisfy the request.

This algorithm may make better use of available memory by wasting less on unused fragments, but may also lead to worse fragmentation as those fragments are more likely to be too small to be useful to other requests.

Public Functions

constexpr BestFitAllocator() = default#: Constexpr constructor. Callers must explicitly call Init.

inline BestFitAllocator(ByteSpan region)#

Non-constexpr constructor that automatically calls Init.

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

WorstFitAllocator#

template<typename BlockType = WorstFitBlock<uintptr_t>> class WorstFitAllocator : public pw::allocator::BlockAllocator<WorstFitBlock<uintptr_t>>#

Block allocator that uses a “worst-fit” allocation strategy.

In this strategy, the allocator handles an allocation request by looking at all unused blocks and finding the smallest one which can satisfy the request.

Public Functions

constexpr WorstFitAllocator() = default#: Constexpr constructor. Callers must explicitly call Init.

inline WorstFitAllocator(ByteSpan region)#

Non-constexpr constructor that automatically calls Init.

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

BucketAllocator#

template<typename BlockType = BucketBlock<>, size_t kMinInnerSize = 32, size_t kNumBuckets = 5> class BucketAllocator : public pw::allocator::BlockAllocator<BucketBlock<>>#

Block allocator that uses sized buckets of free blocks.

In this strategy, the allocator handles an allocation request by starting with the bucket with the smallest size that is larger than the requested size. It tries to allocate using the blocks in that block, if any, before trying the bucket with the next largest size.

On deallocation, blocks are placed in the bucket of the smallest size that is larger than usable space of the block being freed.

The last bucket always has an unbounded size.

As an example, assume that the allocator is configured with a minimum block inner size of 64 and 5 buckets. The internal state may look like the following:

bucket[0] (64B) --> block[12B] --> block[42B] --> block[64B] --> NULL
bucket[1] (128B) --> block[65B] --> block[72B] --> NULL
bucket[2] (256B) --> NULL
bucket[3] (512B) --> block[312B] --> block[512B] --> block[416B] --> NULL
bucket[4] (implicit) --> block[1024B] --> block[513B] --> NULL

Public Functions

inline constexpr BucketAllocator()#: Constexpr constructor. Callers must explicitly call Init.

inline explicit BucketAllocator(ByteSpan region)#

Non-constexpr constructor that automatically calls Init.

Parameters:: region – [in] Region of memory to use when satisfying allocation requests. The region MUST be large enough to fit an aligned block with overhead. It MUST NOT be larger than what is addressable by OffsetType.

BuddyAllocator#

template<size_t kMinOuterSize_ = internal::GenericBuddyAllocator::kDefaultMinOuterSize, size_t kNumBuckets = internal::GenericBuddyAllocator::kDefaultNumBuckets> class BuddyAllocator : public pw::Allocator #

Allocator that uses the buddy memory allocation algorithm.

This allocator allocates blocks of memory whose sizes are powers of two. This allows the allocator to satisfy requests to acquire and release memory very quickly, at the possible cost of higher internal fragmentation. In particular:

The maximum alignment for this allocator is kMinInnerSize.
The minimum size of an allocation is kMinInnerSize. Less may be requested, but it will be satisfied by a block of that inner size.
The maximum size of an allocation is kMinInnerSize << (kNumBuckets - 1).

Use this allocator if you know the needed sizes are close to but less than the block inner sizes and you need high allocator performance.

Template Parameters:

kMinOuterSize – Outer size of the smallest allocatable block. Must be a power of two. All allocations will use at least this much memory.
kNumBuckets – Number of buckets. Must be at least 1. Each additional bucket allows combining blocks into larger blocks.

Public Functions

inline BuddyAllocator()#: Constructs an allocator. Callers must call Init.

inline BuddyAllocator(ByteSpan region)#

Constructs an allocator, and initializes it with the given memory region.

Parameters:: region – [in] Region of memory to use when satisfying allocation requests. The region MUST be large enough to fit a least one minimally-size BuddyBlock.

inline void Init(ByteSpan region)#

Sets the memory region used by the allocator.

Parameters:: region – [in] Region of memory to use when satisfying allocation requests. The region MUST be large enough to fit a least one minimally-size BuddyBlock.

BumpAllocator#

class BumpAllocator : public pw::Allocator #

Allocator that does not automatically delete.

A “bump” or “arena” allocator provides memory by simply incrementing a pointer to a memory region in order to “allocate” memory for requests, and doing nothing on deallocation. All memory is freed only when the allocator itself is destroyed. As a result, this allocator is extremely fast.

Bump allocators are useful when short-lived to allocate objects from small buffers with almost zero overhead. Since memory is not deallocated, a bump allocator with a longer lifespan than any of its allocations will end up holding unusable memory. An example of a good use case might be decoding RPC messages that may require a variable amount of space only for as long as it takes to decode a single message.

On destruction, the destructors for any objects allocated using New or MakeUnique are NOT called. To have these destructors invoked, you can allocate “owned” objects using NewOwned and MakeUniqueOwned. This adds a small amount of overhead to the allocation.

Public Functions

inline constexpr BumpAllocator()#: Constructs a BumpAllocator without initializing it.

inline explicit BumpAllocator(ByteSpan region)#: Constructs a BumpAllocator and initializes it.

void Init(ByteSpan region)#: Sets the memory region to be used by the allocator.

template<typename T, int&... ExplicitGuard, typename ...Args> inline T *NewOwned(Args&&... args)#

Constructs an “owned” object of type T from the given args

Owned objects will have their destructors invoked when the allocator goes out of scope.

The return value is nullable, as allocating memory for the object may fail. Callers must check for this error before using the resulting pointer.

Parameters:: args... – [in] Arguments passed to the object constructor.

template<typename T, int&... ExplicitGuard, typename ...Args> inline UniquePtr<T> MakeUniqueOwned(Args&&... args)#

Constructs and object of type T from the given args, and wraps it in a UniquePtr

Owned objects will have their destructors invoked when the allocator goes out of scope.

The returned value may contain null if allocating memory for the object fails. Callers must check for null before using the UniquePtr.

Parameters:: args... – [in] Arguments passed to the object constructor.

ChunkPool#

class ChunkPool : public pw::allocator::Pool #

Implementation of Pool that uses a list of free chunks.

The first sizeof(void*) bytes of each free chunk is used to store a pointer to the next free chunk, or null for the last free chunk.

Subclassed by pw::allocator::TypedPool< T >

Public Functions

ChunkPool(ByteSpan region, const Layout &layout)#

Construct a Pool that allocates from a region of memory.

Parameters:

region – The memory to allocate from. Must be large enough to allocate at least one chunk with the given layout.
layout – The size and alignment of the memory to be returned from this pool.

LibCAllocator#

class LibCAllocator : public pw::Allocator #

Memory allocator that uses malloc and free.

TODO: b/301930507 - aligned_alloc is not portable. As a result, this allocator has a maximum alignment of std::align_max_t.

Friends

friend LibCAllocator &GetLibCAllocator()#: Returns a reference to the LibCAllocator singleton.

NullAllocator#

class NullAllocator : public pw::Allocator #

A memory allocator that always fails to allocate memory.

A null allocator may be useful as part of a larger framework if allocation should be disallowed under certain circumstances. For example, a function that returns different allocators based on an input parameter may return a null allocator when given an invalid or unsupported parameter value.

Friends

friend NullAllocator &GetNullAllocator()#: Returns a reference to the NullAllocator singleton.

TypedPool#

template<typename T> class TypedPool : public pw::allocator::ChunkPool #

Typed pool that can be used for slab allocation.

This class is a special purpose pool designed to allocate objects of one specific type, T. It is useful when you need a dynamic pool of objects with very low performance and memory overhead costs. For example, a dispatcher might use such an allocator to manage memory for a set of task objects.

Template Parameters:: T – The type of object to allocate memory for.

Public Functions

template<size_t kNumObjects> inline TypedPool(Buffer<kNumObjects> &buffer)#

Construct a TypedPool.

This constructor uses the Buffer type to minimize wasted memory. For example:

TypedPool<MyObject>::Buffer<100> buffer;
TypedPool<MyObject> my_pool(buffer);

Parameters:: buffer – The memory to allocate from.

inline TypedPool(ByteSpan region)#

Construct a TypedPool.

To minimize wasted memory, align the buffer provided to the allocator to the object type’s alignment. For example:

alignas(MyObject) std::array<std::byte, 0x1000> buffer;
TypedPool<MyObject> my_pool(buffer);

Parameters:: region – The memory to allocate from. Must be large enough to allocate memory for at least one object.

template<int&... ExplicitGuard, typename ...Args> inline T *New(Args&&... args)#

Constructs and object from the given args

This method is similar to Allocator::New, except that it is specific to the pool’s object type.

Parameters:: args... – [in] Arguments passed to the object constructor.

template<int&... ExplicitGuard, typename ...Args> inline UniquePtr<T> MakeUnique(Args&&... args)#

Constructs and object from the given args, and wraps it in a UniquePtr

This method is similar to Allocator::MakeUnique, except that it is specific to the pool’s object type.

Parameters:: args... – [in] Arguments passed to the object constructor.

Public Static Functions

static inline constexpr size_t SizeNeeded(size_t num_objects)#: Returns the amount of memory needed to allocate num_objects.

static inline constexpr size_t AlignmentNeeded()#: Returns the optimal alignment for the backing memory region.

template<size_t kNumObjects> struct Buffer#: Provides aligned storage for kNumObjects of type T.

Forwarding Allocators#

This module provides several “forwarding” allocators, as described in Forwarding allocator concept.

AllocatorAsPool#

class AllocatorAsPool : public pw::allocator::Pool #

Implementation of Pool that satisfies requests using an Allocator.

Public Functions

AllocatorAsPool(Allocator &allocator, const Layout &layout)#

Construct a Pool from an Allocator.

Parameters:

allocator – The allocator used to create fixed-size allocations.
layout – The size and alignment of the memory to be returned from this pool.

PmrAllocator#

class PmrAllocator : public pw::pmr::polymorphic_allocator<std::byte>#

Implementation of C++’s abstract polymorphic allocator interface that uses a pw::Allocator.

Note that despite is name, this is NOT a pw::Allocator itself. Instead, it can be used in pw::pmr containers, such as pw::pmr::vector.

FallbackAllocator#

class FallbackAllocator : public pw::Allocator #

This class simply dispatches between a primary and secondary allocator. Any attempt to allocate memory will first be handled by the primary allocator. If it cannot allocate memory, e.g. because it is out of memory, the secondary alloator will try to allocate memory instead.

Public Functions

FallbackAllocator(Allocator &primary, Allocator &secondary)#

Constructor.

Parameters:

primary – [in] Allocator tried first. Must implement Query.
secondary – [in] Allocator tried if primary fails a request.

SynchronizedAllocator#

template<typename LockType> class SynchronizedAllocator : public pw::Allocator #

Wraps an Allocator with a lock to synchronize access.

Depending on the LockType, this object may be thread- and/or interrupt- safe. For example, SynchronizedAllocator<pw::sync::Mutex> is thread-safe, while SynchronizedAllocator<pw::sync::InterruptSpinLock> is thread- and interrupt-safe.

Template Parameters:: LockType – The type of the lock used to synchronize allocator access. Must be default-constructible.

TrackingAllocator#

template<typename MetricsType> class TrackingAllocator : public pw::Allocator #

Wraps an Allocator and records details of its usage.

Metric collection is performed using the provided template parameter type. Callers can not instantiate this class directly, as it lacks a public constructor. Instead, callers should use derived classes which provide the template parameter type, such as TrackingAllocator which uses the default metrics implementation, or TrackingAllocatorForTest which always uses the real metrics implementation.

Utility Classes#

In addition to providing allocator implementations themselves, this module includes some utility classes.

Block interfaces#

A block is an allocatable region of memory, and is the fundamental type managed by several of the concrete allocator implementations. Blocks are defined using several stateless “mix-in” interface types. These provide specific functionality, while deferring the detailed representation of a block to a derived type.

Tip

Avoid converting pointers to allocations into Block instances, even if you know your memory is coming from a BlockAllocator. Breaking the abstraction in this manner will limit your flexibility to change to a different allocator in the future.

BasicBlock#

template<typename Derived> class BasicBlock : public pw::allocator::internal::BasicBase#

Base mix-in for block implementations.

This CRTP-style type can be combined with block mix-in types. Block mix-ins are stateless and trivially constructible. Mix-ins require the derived class to implement methods to access and modify state, such has how to return a block’s size or a pointer to its usable memory.

The mix-ins also follow the NVI pattern. This allows mix-ins to layer behavior for a particular method. For example, the implementation of AllocFirst in AlignableBlock handles allocation with larger than default alignment requirements, and delegates to AllocatableBlock for other requests. The derived type provided by the concrete block implementation can implement the public method that delegates to the correct mix-in. Overridable methods are named Do....

These mix-ins guarantee a number of invariants hold at the beginning and end of each regular public API call. Each mix-in can enforce invariants by overriding DoCheckInvariants. The concrete block implementation should override the same method by calling each of the relevant mix-in methods. Calling a public API method within an implementation of DoCheckInvariants will lead to infinite recursion. To avoid this, mix-ins provide and/or require versions of methods named ...Unchecked that skip checking invariants. These should only be used within the context of DoCheckInvariants or other ...Unchecked methods.

This mix-in requires its derived type provide the following symbols:

static constexpr size_t DefaultAlignment()
- Returns the alignment of the block type. Must be a power of two.
static constexpr size_t BlockOverhead()
- Returns the size of the metadata at the start of a block, before its usable space.
static constexpr size_t MinInnerSize()
- Returns the minimum inner size of a block. Should be 1 unless the usable space is used to track blocks when they are free.
size_t OuterSizeUnchecked() const
- Returns the size of the block. Must be multiple of kAlignment.

Public Functions

inline std::byte *UsableSpace()#

Returns:: A pointer to the usable space inside this block.

inline size_t OuterSize() const#

Returns:: The total size of the block in bytes, including the header.

inline size_t InnerSize() const#

Returns:: The number of usable bytes inside the block.

inline bool IsValid() const#

Returns:: whether a block is valid.

inline void CheckInvariantsIfStrict() const#: Does nothing unless PW_ALLOCATOR_STRICT_VALIDATION is set in the module configuration. If it is, calls CheckInvariants with crash_on_failure set. The method is static to avoid any checks of the pointer when strict validation is disabled.

Public Static Functions

static inline Derived *FromUsableSpace(void *usable_space)#

This is the inverse of UsableSpace().

Warning

This method does not do any checking; passing a random pointer will return a non-null pointer.

Returns:: A pointer to a Block, given a pointer to the start of the usable space inside the block.

static size_t OuterSizeFromInnerSize(size_t inner_size)#

Returns:: The outer size of a block from the corresponding inner size.

static size_t InnerSizeFromOuterSize(size_t outer_size)#

Returns:: The inner size of a block from the corresponding outer size.

ContiguousBlock#

template<typename Derived> class ContiguousBlock : public pw::allocator::internal::ContiguousBase#

Mix-in for blocks that collectively represent a contiguous region of memory.

Contiguous blocks can be split into smaller blocks and merged when adjacent.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from BasicBlock, and provide the following symbols:

static constexpr size_t MaxAddressableSize()
- Size of the largest region that can be addressed by a block.
static Derived* AsBlock(BytesSpan)
- Instantiates and returns a block for the given region of memory.
size_t PrevOuterSizeUnchecked() const
- Returns the outer size of the previous block, if any, or zero. Must be multiple of kAlignment.
bool IsLastUnchecked() const
- Returns whether this block is the last block.

Public Functions

inline Derived *Prev() const#

Returns:: the block immediately before this one, or null if this is the first block.

inline Derived *Next() const#

Returns:: the block immediately after this one, or null if this is the last block.

Public Static Functions

static Result<Derived*> Init(ByteSpan region)#

Creates the first block for a given memory region.

Returns:

Code	Description
`OK`	Returns a block representing the region.
`INVALID_ARGUMENT`	The region is null.
`RESOURCE_EXHAUSTED`	The region is too small for a block.
`OUT_OF_RANGE`	The region is larger than kMaxAddressableSize.

AllocatableBlock#

template<typename Derived> class AllocatableBlock : public pw::allocator::internal::AllocatableBase#

Mix-in for blocks that can be allocated and freed.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from ContiguousBlock and provide the following symbols:

size_t kMinOuterSize
- Size of the smallest block that can be allocated.
bool IsFreeUnchecked() const
- Returns whether the block is free or in use.
void SetFree(bool)
- Sets whether the block is free or in use.

Public Functions

inline bool IsFree() const#

Returns:: whether this block is free or is in use.

inline bool Used() const#

Indicates whether the block is in use is free.

This method will eventually be deprecated. Prefer IsFree.

StatusWithSize CanAlloc(Layout layout) const#

Checks if a block could be split from the block.

On error, this method will return the same status as AllocFirst or AllocLast without performing any modifications.

Pre:

The block must not be in use.

Returns:

Code	Description
`OK`	Returns the number of bytes to shift this block in order to align its usable space.
`FAILED_PRECONDITION`	This block is in use and cannot be split.
`RESOURCE_EXHAUSTED`	The available space is insufficient to fulfill the request. This may be due to a large requested size, or insufficient remaining space to fulfill the requested alignment create a valid leading block, and/or create a valid trailing block.

BlockResult<Derived> Resize(size_t new_inner_size)#

Grows or shrinks the block.

If successful, block may be merged with the block after it in order to provide additional memory (when growing) or to merge released memory (when shrinking). If unsuccessful, block will be unmodified.

Note: Resizing may modify the block following this one if it is free. Allocators that track free blocks based on their size must be prepared to handle this size change.

Pre:

The block must be in use.

Returns:

Code	Description
`OK`	The resize completed successfully.
`FAILED_PRECONDITION`	This block is not in use.
`RESOURCE_EXHAUSTED`	The available space is insufficient to fulfill the request. This may be due to a large requested size, or insufficient remaining space to fulfill the requested alignment create a valid leading block, and/or create a valid trailing block.

Public Static Functions

static BlockResult<Derived> AllocFirst(Derived *&&block, Layout layout)#

Splits an aligned block from the start of the block, and marks it as used.

If successful, block will be replaced by a block that has an inner size of at least inner_size, and whose starting address is aligned to an alignment boundary. If unsuccessful, block will be unmodified.

This method is static in order to consume the given block pointer. On success, a pointer to the new, smaller block is returned. In total, up to two additional blocks may be created: one to pad the returned block to an alignment boundary and one for the trailing space. On error, the original pointer is returned.

For larger alignments, the AllocLast method is generally preferable to this method, as this method may create an additional fragments both before and after the returned block in order to align the usable space.

Pre:

The block must not be in use.

Returns:

Code	Description
`OK`	The split completed successfully. The BlockAllocType indicates how extra memory was distributed to other blocks.
`FAILED_PRECONDITION`	This block is in use and cannot be split.
`RESOURCE_EXHAUSTED`	The available space is insufficient to fulfill the request. This may be due to a large requested size, or insufficient remaining space to fulfill the requested alignment create a valid leading block, and/or create a valid trailing block.

static BlockResult<Derived> AllocLast(Derived *&&block, Layout layout)#

Splits an aligned block from the end of the block, and marks it as used.

Pre:

The block must not be in use.

Returns:

Code	Description
`OK`	The split completed successfully. The BlockAllocType indicates how extra memory was distributed to other blocks.
`FAILED_PRECONDITION`	This block is in use and cannot be split.
`RESOURCE_EXHAUSTED`	The available space is insufficient to fulfill the request. This may be due to a large requested size, or insufficient remaining space to fulfill the requested alignment create a valid leading block, and/or create a valid trailing block.

static BlockResult<Derived> Free(Derived *&&block)#

Marks the block as free.

This method is static in order to consume the given block pointer. It returns a pointer to a freed block that is the result of merging the given block with either or both of its neighbors, if they were free.

Note: Freeing may modify the adjacent blocks if they are free. Allocators that track free blocks must be prepared to handle this merge.

AlignableBlock#

template<typename Derived> class AlignableBlock : public pw::allocator::internal::AlignableBase#

Mix-in for blocks that can be split on alignment boundaries.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from AllocatableBlock.

BlockWithLayout#

template<typename Derived> class BlockWithLayout : public pw::allocator::internal::BaseWithLayout#

Mix-in for blocks that can retrieve the layout used to allocate them.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from AlignableBlock and provide the following symbols:

size_t RequestedSize() const
- Returns the size of the original layout
size_t RequestedAlignment() const
- Returns the alignment of the original layout
void SetRequestedSize(size_t)
- Records the size of the original layout
void SetRequestedAlignment(size_t)
- Records the alignment from the original layout

Public Functions

Result<Layout> RequestedLayout() const#

Returns:: The memory layout that was requested using AllocFirst, AllocLast, or Resize, or FAILED_PRECONDITION if the block is free.

ForwardIterableBlock#

template<typename Derived> class ForwardIterableBlock : public pw::allocator::internal::ForwardIterableBase#

Mix-in for blocks that allows creating forward iterators over block ranges.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from ContiguousBlock.

class Iterator#

Represents an iterator that moves forward through a list of blocks.

This class is not typically instantiated directly, but rather using a range-based for-loop using Block::Range.

Allocating or freeing blocks invalidates the iterator.

class Range#

Represents a range of blocks that can be iterated over.

The typical usage of this class is in a range-based for-loop, e.g.

for (auto* block : Range(first, last)) { ... }

Allocating or freeing blocks invalidates the range.

Public Functions

inline explicit constexpr Range(Derived *begin)#: Constructs a range including begin and all valid following blocks.

inline constexpr Range(Derived *begin_inclusive, Derived *end_inclusive)#: Constructs a range of blocks from begin to end, inclusively.

ReverseIterableBlock#

template<typename Derived> class ReverseIterableBlock : public pw::allocator::internal::ReverseIterableBase#

Mix-in for blocks that allows creating reverse iterators over block ranges.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from ContiguousBlock.

class ReverseIterator#

Represents an iterator that moves backward through a list of blocks.

This class is not typically instantiated directly, but rather using a range-based for-loop using Block::ReverseRange.

Allocating or freeing blocks invalidates the iterator.

class ReverseRange#

Represents a range of blocks that can be iterated over in the reverse direction.

The typical usage of this class is in a range-based for-loop, e.g.

for (auto* block : ReverseRange(last, first)) { ... }

Allocating or freeing blocks invalidates the range.

Public Functions

inline explicit constexpr ReverseRange(Derived *rbegin)#: Constructs a range including rbegin and all valid preceding blocks.

inline constexpr ReverseRange(Derived *rbegin_inclusive, Derived *rend_inclusive)#: Constructs a range of blocks from rbegin to rend, inclusively.

PoisonableBlock#

template<typename Derived> class PoisonableBlock : public pw::allocator::internal::PoisonableBase#

Mix-in for blocks that can be poisoned.

A poisoned block’s usable space contains pattern of data whose integrity can be checked later for modification.

Block mix-ins are stateless and trivially constructible. See BasicBlock for details on how mix-ins can be combined to implement blocks.

This mix-in requires its derived type also derive from ContiguousBlock and provide the following method:

static consextpr size_t ReservedWhenFree()
- Indicates how many bytes should not be poisoned.
bool IsPoisoned() const
- Returns whether the block is poisoned.
void SetPoisoned(bool)
- Sets whether the block is poisoned.

Public Functions

inline constexpr uintptr_t GetPoisonWord() const#: Returns the value written to a block’s usable space when poisoning.

inline bool IsPoisoned() const#: Returns whether this block has been poisoned.

void Poison()#

Poisons the block’s usable space.

This method does nothing if the block is not free. The decision to poison a block is delegated to the allocator to allow for more nuanced strategies than simply all or nothing. For example, an allocator may want to balance security and performance by only poisoning every n-th free block.

BlockResult#

This type is not a block mix-in. It is used to communicate whether a method succeeded, what block was produced or modified, and what side-effects the call produced.

template<typename BlockType> class BlockResult : public pw::allocator::internal::GenericBlockResult#

Extends GenericBlockResult to include a pointer to a block.

The included pointer is to the block affected by the operation that produced a result. On error, this should be the original block. On success, it may be a newly produced block.

Template Parameters:: BlockType – The type of the block included in the result.

DetailedBlock#

This type is not a block mix-in. It is an example of a block implementation that uses the mix-ins above.

template<typename OffsetType_, typename WhenFree> struct DetailedBlockParameters#

Parameters type that encapsulates the block parameters.

Template Parameters:

OffsetType – Unsigned integral type used to encode offsets. Larger types can address more memory, but consume greater overhead.
WhenFree – Optional intrusive type that uses the block’s usable space to track the block when free. This will affect the minimum alignment, and what portion of the usable space is skipped when poisoning.

A block implementation that implements most optional block mix-ins.

This block dervies from various block mix-ins, allowing it to perform aligned allocations, iterate over blocks, poison and check free blocks, retrieve requested memory layouts, and more.

The amount of memory that can be addressed by a block of this type depends on it given OffsetType. This type is used to describe the size of both the current and previous block, so the maximum addressable range is given by std::numeric_limits<OffsetType> * alignof(OffsetType).

An additional 4 bytes are used to store details about an allocation, including whether it is in use or free, whether it is poisoned, and what the originally requested layout for a block was.

See also the DetailedBlock alias which provides the Parameters type automatically.

Template Parameters:: Parameters – Block traits, such as DetailedBlockParameters, which encapsulate a set of template parameters.

Bucket#

Several block allocator implementations improve performance by managing buckets, which are data structures that track free blocks. Several bucket implementations are provided that trade off between performance and per-block space needed when free.

FastSortedBucket#

template<typename BlockType> class FastSortedBucket : public internal::BucketBase<FastSortedBucket<BlockType>, BlockType, FastSortedItem<BlockType>>#

Container of size-sorted free blocks.

The container used to hold the blocks is a multimap. Insertion and removal are O(log(n)) operations. However, the multimap nodes require more space than the “compact” items. As such, this bucket type is a good general purpose container for items above a minimum size.

ForwardSortedBucket#

template<typename BlockType> class ForwardSortedBucket : public pw::allocator::internal::SortedBucketBase<ForwardSortedBucket<BlockType>, BlockType>#

Container of free blocks sorted in order of increasing size.

As noted in the base class, this class relies on a forward list. This allows the free blocks to be as small as a single pointer, but makes insertion and lookup O(n) on the number of blocks in the bucket.

Calling RemoveAny() on this bucket will return the smallest free block.

Public Static Functions

static inline constexpr auto MakeAddPredicate(size_t inner_size)#

Returns a lambda that tests if the block storing an item has an inner size larger than the given inner_size.

This lambda can be used with std::find_if and FindPrevIf.

ReverseFastSortedBucket#

template<typename BlockType> class ReverseFastSortedBucket : public internal::BucketBase<ReverseFastSortedBucket<BlockType>, BlockType, FastSortedItem<BlockType>>#

Like FastSortedBucket, but ordered largest to smallest.

In particular, Remove() will return the largest free block.

ReverseSortedBucket#

template<typename BlockType> class ReverseSortedBucket : public pw::allocator::internal::SortedBucketBase<ReverseSortedBucket<BlockType>, BlockType>#

Container of free blocks sorted in order of decreasing size.

Calling RemoveAny() on this bucket will return the largest free block.

Public Static Functions

static inline constexpr auto MakeAddPredicate(size_t inner_size)#

Returns a lambda that tests if the block storing an item has an inner size smaller than the given inner_size.

This lambda can be used with std::find_if and FindPrevIf.

SequencedBucket#

template<typename BlockType> class SequencedBucket : public internal::BucketBase<SequencedBucket<BlockType>, BlockType, SequencedItem>#

Container of a sequence of free blocks.

The container used to hold the blocks is a doubly-linked list. The list is sorted on the memory address of the blocks themselves. Insertion is O(n), while removal is O(1). This bucket type is useful when the order of blocks must be preserved.

Public Functions

inline void set_threshold(size_t threshold)#

Sets the threshold for which blocks are considered “large”.

This threshold can improve performance when blocks are partitioned based on size. Iterating over the free blocks to add or remove a block will start at the beginning for block with an inner size considered “large”, and the end for blocks with an inner size considered “small”.

UnorderedBucket#

template<typename BlockType> class UnorderedBucket : public internal::BucketBase<UnorderedBucket<BlockType>, BlockType, UnorderedItem>#

Container of free blocks that use minimal usable space.

The container used to hold the blocks is a singly-linked list. As a result, it is able to store free blocks as small as sizeof(void*). Insertion and removal of an unspecified block is O(1). Removal internal::of a specific block is O(n) since the whole list may need to be walked to find the block. As such, this bucket type is useful for pools of blocks of a single size.

Metrics#

template<typename MetricsType> class Metrics#

Encapsulates the metrics struct for pw::allocator::TrackingAllocator.

This class uses the type traits from PW_ALLOCATOR_METRICS_DECLARE to conditionally include or exclude code to update metrics based on calls to the pw::Allocator API. This minimizes code size without adding additional conditions to be evaluated at runtime.

Template Parameters:: MetricsType – The struct defining which metrics are enabled.

Public Functions

void ModifyRequested(size_t increase, size_t decrease)#

Updates how much memory was requested and successfully allocated.

This will update the current, peak, and cumulative amounts of memory requests that were satisfied by an allocator.

Parameters:

increase – How much memory was requested to be allocated.
decrease – How much memory was requested to be freed.

void ModifyAllocated(size_t increase, size_t decrease)#

Updates how much memory is allocated.

This will update the current, peak, and cumulative amounts of memory that has been actually allocated or freed. This method acts as if it frees memory before allocating. If a routine suchas Reallocate allocates before freeing, the update should be separated into two calls, e.g.

ModifyAllocated(increase, 0);
ModifyAllocated(0, decrease);

Parameters:

increase – How much memory was allocated.
decrease – How much memory was freed.

void IncrementAllocations()#: Records that a call to Allocate was made.

void IncrementDeallocations()#: Records that a call to Deallocate was made.

void IncrementResizes()#: Records that a call to Resize was made.

void IncrementReallocations()#: Records that a call to Reallocate was made.

void RecordFailure(size_t requested)#

Records that a call to Allocate, Resize, or Reallocate failed.

This may indicated that memory becoming exhausted and/or highly fragmented.

Parameters:: requested – How much memory was requested in the failed call.

This class is templated on a MetricsType struct. See Allocator metrics for additional details on how the struct, this class, and TrackingAllocator interact.

Module consumers can define their own metrics structs using the following macros:

PW_ALLOCATOR_METRICS_DECLARE(metric_name)#

Declares the names of metrics used by pw::allocator::Metrics.

Only the names of declared metrics may be passed to PW_ALLOCATOR_METRICS_ENABLE as part of a metrics struct definition.

This macro generates trait types that are used by Metrics to conditionally include metric-related code.

Note: if enabling `peak_allocated_bytes or cumulative_allocated_bytes, allocated_bytes should also be enabled.

PW_ALLOCATOR_METRICS_ENABLE(metric_name)#

Enables a metric for in a metrics struct.

The pw::allocator::TrackingAllocator template takes a struct that enables zero or more of the metrics enumerated by PW_ALLOCATOR_METRICS_DECLARE`.

This struct may be one of AllMetrics or NoMetrics, or may be a custom struct that selects a subset of metrics.

Note that this must be fully-qualified since the metric struct may be defined in any namespace.

Example:

struct MyMetrics {
  PW_ALLOCATOR_METRICS_ENABLE(allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(peak_allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(num_failures);
};

Fragmentation#

struct Fragmentation#

Information that can be used to represent the fragmentation of the block allocator’s memory region.

Fragmentation can be measured as 1 minus the normalized root-sum-square of the free block inner sizes, i.e.

1 - (sqrt(sum(U[i]^2)) / sum(U[i])

where U[i] is the inner size of the i-th free block.

This metric has been described by Adam Sawicki (https://asawicki.info/news_1757_a_metric_for_memory_fragmentation), and used in esp8266/Arduino (esp8266/Arduino), among others.

This struct provides the sum-of-squares and the sum of the inner sizes of free blocks. It is left to the caller to perform the square root and division steps, perhaps on a host, AP, or other device with better floating point support.

The sum-of-squares is stored as a pair of sizes, since it can overflow.

Public Members

struct pw::allocator::Fragmentation::[anonymous] sum_of_squares#: Sum-of-squares of the inner sizes of free blocks.

size_t sum = 0#: Sum of the inner sizes of free blocks.

SizeReporter#

This module includes a utility class for generating size reports. It is intended for allocator implementers and not for module consumers.

class SizeReporter#

Utility class for generating allocator size reports.

The pw_bloat module can be used to compare the size of binaries. This class facilitates creating binaries with and without a given allocator type.

To create a size report:

Make a copy of //pw_allocator/size_report/base.cc
Instantiate your allocator and pass it to MeasureAllocator.
Create build target(s) for your binary, and a pw_size_diff target that compares it to “$dir_pw_allocator/size_report:base”.

Public Functions

inline void Measure(Allocator &allocator)#

Exercises an allocator as part of a size report.

Parameters:: allocator – [in] The allocator to exercise. Will be ignored if not derived from Allocator.

struct Bar#: Nested type used for exercising an allocator.

struct Baz#: Nested type used for exercising an allocator.

struct Foo#: Nested type used for exercising an allocator.

Buffer management#

template<typename T, size_t kBufferSize, size_t kAlignment = 1> class WithBuffer#

Associates a default-constructed type with a memory buffer.

Although the type is arbitrary, the intended purpose of of this class is to provide allocators with memory to use, e.g. when testing.

This class uses composition instead of inheritance in order to allow the wrapped type’s destructor to reference the memory without risk of a use-after-free. As a result, the specific methods of the wrapped type are not directly accesible. Instead, they can be accessed using the * and -> operators, e.g.

WithBuffer<MyAllocator, 256> allocator;
allocator->MethodSpecificToMyAllocator();

Note that this class does NOT initialize the allocator, since initialization is not specified as part of the Allocator interface and may vary from allocator to allocator. As a result, typical usage includes deriving a class that initializes the wrapped allocator with the buffer in a constructor. See AllocatorForTest for an example.

Template Parameters:

T – The wrapped object.
kBufferSize – The size of the backing memory, in bytes.
kAlignment – Buffer memory will be aligned to this alignment boundary.

Test support#

This module includes test utilities for allocator implementers. These facilitate writing unit tests and fuzz tests for both concrete and forwarding allocator implementations. They are not intended to be used by module consumers.

AllocatorForTest#

template<size_t kBufferSize, typename BlockType_ = FirstFitBlock<uint32_t>, typename MetricsType = internal::AllMetrics> class AllocatorForTest : public pw::Allocator #

An AllocatorForTest that is automatically initialized on construction.

Public Functions

inline void ResetParameters()#: Resets the recorded parameters to an initial state.

inline void Exhaust()#: Allocates all the memory from this object.

inline Fragmentation MeasureFragmentation() const#: Returns fragmentation information for the block allocator’s memory region.

SynchronizedAllocatorForTest#

template<size_t kBufferSize, typename BlockType_ = FirstFitBlock<uint32_t>, typename MetricsType = internal::AllMetrics> class SynchronizedAllocatorForTest : public pw::Allocator #: An AllocatorForTest that is thread and interrupt-safe and automatically initialized on construction.

TestHarness#

class TestHarness#

Associates an Allocator with a list to store allocated pointers.

This class facilitates performing allocations from generated Requests, enabling the creation of performance, stress, and fuzz tests for various allocators.

This class does NOT implement TestHarness::Init. It must be extended further with a method that provides an initialized allocator.

For example, one can create a fuzzer for MyAllocator that verifies it never crashes by adding the following class, function, and macro:

constexpr size_t kMaxRequests = 256;
constexpr size_t kMaxAllocations = 128;
constexpr size_t kMaxSize = 2048;

class MyAllocatorFuzzer : public TestHarness {
 private:
  Allocator* Init() override { return &allocator_; }
  MyAllocator allocator_;
};

void MyAllocatorNeverCrashes(const Vector<Request>& requests) {
  static MyAllocatorFuzzer fuzzer;
  fuzzer.HandleRequests(requests);
}

FUZZ_TEST(MyAllocator, MyAllocatorNeverCrashes)
  .WithDomains(ArbitraryRequests<kMaxRequests, kMaxSize>());

Public Functions

void GenerateRequests(size_t max_size, size_t num_requests)#

Generates and handles a sequence of allocation requests.

This method will use the given PRNG to generate num_requests allocation requests and pass each in turn to HandleRequest. It will call Reset before returning.

void GenerateRequest(size_t max_size)#

Generate and handle an allocation requests.

This method will use the given PRNG to generate an allocation request and pass it to HandleRequest. Callers MUST call Reset when no more requests remain to be generated.

void HandleRequests(const Vector<Request> &requests)#

Handles a sequence of allocation requests.

This method is useful for processing externally generated requests, e.g. from FuzzTest. It will call Reset before returning.

bool HandleRequest(const Request &request)#

Handles an allocator request.

This method is stateful, and modifies the vector of allocated pointers. It will call Init if it has not yet been called.

If the request is an allocation request:

If the vector of previous allocations is full, ignores the request.
Otherwise, allocates memory and stores the pointer in the vector.

If the request is a deallocation request:

If the vector of previous allocations is empty, ignores the request.
Otherwise, removes a pointer from the vector and deallocates it.

If the request is a reallocation request:

If the vector of previous allocations is empty, reallocates a nullptr.
Otherwise, removes a pointer from the vector and reallocates it.

Returns whether the request was handled. This is different from whether the request succeeded, e.g. a DeallocationRequest cannot be handled when there are no current allocations and will return false. By contrast, an AllocationRequest may be handled, but fail due to insufficient memory, and will return true.

void Reset()#: Deallocates any pointers stored in the vector of allocated pointers.

struct Allocation : public pw::containers::future::IntrusiveList<T>::Item#: Associates a pointer to memory with the Layout used to allocate it.

FuzzTest support#

fuzzer::Domain<Request> pw::allocator::test::ArbitraryRequest(size_t max_size)#

Returns a FuzzTest domain for producing arbitrary allocator requests.

This method integrates with FuzzTest to use code coverage to produce guided mutations.

See google/fuzztest

Parameters:: max_size – Size of the largest allocation that can be requested.

template<size_t kMaxRequests, size_t kMaxSize> auto pw::allocator::test::ArbitraryRequests()#

Returns a FuzzTest domain for producing sequences of arbitrary allocator requests.

This method can be used to drive an AllocatorTestHarness as part of a fuzz test.

See google/fuzztest

Parameters:: max_size – Size of the largest allocation that can be requested.

template<size_t kIndex, typename ...Args> Request pw::allocator::test::MakeRequest(Args... args)#

Builds an Request from an index and values.

Unfortunately, the reproducer emitted by FuzzTest for vectors of Requests cannot simply be copied and pasted. To create a reproducer, create a pw::Vector of the appropriate size, and populate it using this method with the correct index.

For example, consider the following sample output:

The test fails with input:
argument 0: {(index=0, value={0, 1}), (index=0, value={1209, 8}),
(index=2, value={9223372036854775807, 2048})}

=================================================================
=== Reproducer test

TEST(MyAllocatorFuzzTest, NeverCrashesU16Regression) {
  NeverCrashes(
    {{0, 1}, {1209, 8}, {9223372036854775807, 2048},
  );
}

A valid reproducer might be:

    TEST(MyAllocatorFuzzTest, NeverCrashesU16Regression) {
      Vector<test::Request, 3> input({
        test::MakeRequest<0>(0u, 1u),
        test::MakeRequest<0>(1209u, 8u),
        test::MakeRequest<2>(9223372036854775807u, 2048u),
      });
      NeverCrashes(input);
// }