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
usingLayout::Of
.Example:
struct MyStruct { uint8_t field1[3]; uint32_t field2[3]; }; constexpr Layout layout_for_struct = Layout::Of<MyStruct>();
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::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 thelayout
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 givenargs
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 givenargs
and sizeThe 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 givenargs
, and wraps it in aUniquePtr
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 givenargs
and size, and wraps it in aUniquePtr
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()
equalsnew_size
, and always returns false if the given pointer is null, theold_layout.size()
is 0, or thenew_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 aLayout
. 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
, thenAllocate
, move the data, andDeallocate
as needed.If
nullptr
is returned, the block of memory is unchanged. In particular, if thenew_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
, thealignment
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 aLayout
. 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.
-
inline void *Allocate(Layout layout)#
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.
-
inline void *Allocate()#
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 aLayout
. 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 withstd::pmr::memory_resource::is_equal
. There currently is no corresponding virtualDoIsEqual
, as objects that would requiredynamic_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.
-
inline bool HasCapability(Capability capability) const#
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
Capability
s.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 aDeallocator
.This is analogous to
std::unique_ptr
, but includes a few differences in order to supportDeallocator
and encourage safe usage. Most notably,UniquePtr<T>
cannot be constructed from aT*
.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<U> &&other) noexcept# Move-constructs a
UniquePtr<T>
from aUniquePtr<U>
.This allows not only pure move construction where
T == U
, but also converting construction whereT
is a base class ofU
, likeUniquePtr<Base> base(deallocator.MakeUnique<Child>());
.
-
template<typename U>
inline UniquePtr &operator=(UniquePtr<U> &&other) noexcept# Move-assigns a
UniquePtr<T>
from aUniquePtr<U>
.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 whereT
is a base class ofU
, likeUniquePtr<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 surroundingif (foo)
vs.if (*foo)
.nullptr
checking should instead useif (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
viamy_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<U>, 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<U>, 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
-
inline constexpr UniquePtr()#
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.
-
Range blocks() const#
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”.
-
constexpr FirstFitAllocator() = default#
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
.
-
constexpr BestFitAllocator() = default#
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.
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 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
.
-
constexpr WorstFitAllocator() = default#
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
.
-
inline constexpr BucketAllocator()#
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
orMakeUnique
are NOT called. To have these destructors invoked, you can allocate “owned” objects usingNewOwned
andMakeUniqueOwned
. 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 givenargs
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 givenargs
, and wraps it in aUniquePtr
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.
-
inline constexpr BumpAllocator()#
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.
-
ChunkPool(ByteSpan region, const Layout &layout)#
LibCAllocator#
-
class LibCAllocator : public pw::Allocator#
Memory allocator that uses
malloc
andfree
.TODO: b/301930507 -
aligned_alloc
is not portable. As a result, this allocator has a maximum alignment ofstd::align_max_t
.Friends
-
friend LibCAllocator &GetLibCAllocator()#
Returns a reference to the LibCAllocator singleton.
-
friend LibCAllocator &GetLibCAllocator()#
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.
-
friend NullAllocator &GetNullAllocator()#
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 aUniquePtr
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 typeT
.
Forwarding Allocators#
This module provides several “forwarding” allocators, as described in Forwarding allocator concept.
AllocatorAsPool#
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 aspw::pmr::vector
.See also https://en.cppreference.com/w/cpp/memory/polymorphic_allocator.
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.
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, whileSynchronizedAllocator<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, orTrackingAllocatorForTest
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
inAlignableBlock
handles allocation with larger than default alignment requirements, and delegates toAllocatableBlock
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 namedDo...
.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 ofDoCheckInvariants
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 ofDoCheckInvariants
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, callsCheckInvariants
withcrash_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
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
orAllocLast
without performing any modifications.- Pre:
The block must not be in use.
- Returns:
Code
Description
Returns the number of bytes to shift this block in order to align its usable space.
This block is in use and cannot be split.
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
The resize completed successfully.
This block is not in use.
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 leastinner_size
, and whose starting address is aligned to analignment
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
The split completed successfully. The BlockAllocType indicates how extra memory was distributed to other blocks.
This block is in use and cannot be split.
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.
If successful,
block
will be replaced by a block that has an inner size of at leastinner_size
, and whose starting address is aligned to analignment
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.
- Pre:
The block must not be in use.
- Returns:
Code
Description
The split completed successfully. The BlockAllocType indicates how extra memory was distributed to other blocks.
This block is in use and cannot be split.
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
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.
-
class Iterator#
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.
-
class ReverseIterator#
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.
-
template<typename Parameters>
class DetailedBlockImpl : public pw::allocator::BasicBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::ForwardIterableBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::ReverseIterableBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::ContiguousBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::AllocatableBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::AlignableBlock<DetailedBlockImpl<Parameters>>, public pw::allocator::BlockWithLayout<DetailedBlockImpl<Parameters>>, public pw::allocator::PoisonableBlock<DetailedBlockImpl<Parameters>># 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 bystd::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 theParameters
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
andFindPrevIf
.
-
static inline constexpr auto MakeAddPredicate(size_t inner_size)#
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.
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 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
andFindPrevIf
.
-
static inline constexpr auto MakeAddPredicate(size_t inner_size)#
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”.
-
inline void set_threshold(size_t threshold)#
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 thepw::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
, orReallocate
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
orcumulative_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 byPW_ALLOCATOR_METRICS_DECLARE
`.This struct may be one of
AllMetrics
orNoMetrics
, 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.
-
struct pw::allocator::Fragmentation::[anonymous] sum_of_squares#
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
-
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. SeeAllocatorForTest
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.
-
inline void ResetParameters()#
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
Request
s, 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 toHandleRequest
. It will callReset
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 callReset
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.
-
void GenerateRequests(size_t max_size, size_t num_requests)#
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); // }