Pigweed
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign > Class Template Reference

#include <bucket_block_allocator.h>

Public Types

using Base = BlockAllocator< OffsetType, 0, std::max(kAlign, alignof(std::byte *))>
 
using BlockType = typename Base::BlockType
 
- Public Types inherited from pw::allocator::BlockAllocator< OffsetType, kPoisonInterval, kAlign >
using BlockType = Block< OffsetType, kAlign, kPoisonInterval !=0 >
 
using Range = typename BlockType::Range
 
- Public Types inherited from pw::Deallocator
using Capabilities = allocator::Capabilities
 
using Capability = allocator::Capability
 
using Layout = allocator::Layout
 

Public Member Functions

constexpr BucketBlockAllocator ()
 Constexpr constructor. Callers must explicitly call Init.
 
 BucketBlockAllocator (ByteSpan region)
 
void Init (ByteSpan region)
 
void Init (BlockType *begin)
 
void Init (BlockType *begin, BlockType *end) override
 
- Public Member Functions inherited from pw::allocator::BlockAllocator< OffsetType, kPoisonInterval, kAlign >
constexpr BlockAllocator ()
 Constexpr constructor. Callers must explicitly call Init.
 
 BlockAllocator (ByteSpan region)
 
Range blocks () const
 Returns a Range of blocks tracking the memory of this allocator.
 
void Init (ByteSpan region)
 
void Init (BlockType *begin)
 
virtual void Init (BlockType *begin, BlockType *end)
 
Fragmentation MeasureFragmentation () const
 Returns fragmentation information for the block allocator's memory region.
 
void Reset ()
 
- Public Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
 GenericBlockAllocator (const GenericBlockAllocator &)=delete
 
GenericBlockAllocator & operator= (const GenericBlockAllocator &)=delete
 
 GenericBlockAllocator (GenericBlockAllocator &&)=delete
 
GenericBlockAllocator & operator= (GenericBlockAllocator &&)=delete
 
- Public Member Functions inherited from pw::Allocator
void * Allocate (Layout layout)
 
template<typename T , int &... ExplicitGuard, typename... Args>
T * New (Args &&... args)
 
template<typename T , int &... ExplicitGuard, typename... Args>
UniquePtr< T > MakeUnique (Args &&... args)
 
bool Resize (void *ptr, size_t new_size)
 
bool Resize (void *ptr, Layout layout, size_t new_size)
 
void * Reallocate (void *ptr, Layout new_layout)
 
void * Reallocate (void *ptr, Layout old_layout, size_t new_size)
 
allocator::AsPmrAllocator as_pmr ()
 
- Public Member Functions inherited from pw::Deallocator
const Capabilities & capabilities () const
 
bool HasCapability (Capability capability) const
 Returns whether a given capabilityis enabled for this object.
 
void Deallocate (void *ptr)
 
void Deallocate (void *ptr, Layout layout)
 
template<typename T >
void Delete (T *ptr)
 
StatusWithSize GetCapacity () const
 
bool IsEqual (const Deallocator &other) const
 

Additional Inherited Members

- Static Public Attributes inherited from pw::allocator::internal::GenericBlockAllocator
static constexpr Capabilities kCapabilities
 
- Protected Types inherited from pw::allocator::BlockAllocator< OffsetType, kPoisonInterval, kAlign >
using ReverseRange = typename BlockType::ReverseRange
 
- Protected Member Functions inherited from pw::allocator::BlockAllocator< OffsetType, kPoisonInterval, kAlign >
ReverseRange rblocks ()
 
template<typename PtrType , typename BlockPtrType = std::conditional_t< std::is_const_v<std::remove_pointer_t<PtrType>>, const BlockType*, BlockType*>>
Result< BlockPtrType > FromUsableSpace (PtrType ptr) const
 
virtual void ReserveBlock (BlockType *)
 
virtual void RecycleBlock (BlockType *)
 
- Protected Member Functions inherited from pw::Allocator
constexpr Allocator ()=default
 TODO(b/326509341): Remove when downstream consumers migrate.
 
constexpr Allocator (const Capabilities &capabilities)
 
- Protected Member Functions inherited from pw::Deallocator
constexpr Deallocator ()=default
 TODO(b/326509341): Remove when downstream consumers migrate.
 
constexpr Deallocator (const Capabilities &capabilities)
 
template<typename T >
UniquePtr< T > WrapUnique (T *ptr)
 
- Static Protected Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
static void CrashOnAllocated (void *allocated)
 
static void CrashOnInvalidFree (void *freed)
 
static void CrashOnDoubleFree (void *freed)
 Crashes with an informational message that a given block was freed twice.
 

Detailed Description

template<typename OffsetType = uintptr_t, size_t kMinBucketChunkSize = 32, size_t kNumBuckets = 5, size_t kAlign = std::max(alignof(OffsetType), alignof(std::byte*))>
class pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign >

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 chunk size of 64 and 5 buckets. The internal state may look like the following:

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

Note that since this allocator stores information in free chunks, it does not currently support poisoning.

Constructor & Destructor Documentation

◆ BucketBlockAllocator()

template<typename OffsetType = uintptr_t, size_t kMinBucketChunkSize = 32, size_t kNumBuckets = 5, size_t kAlign = std::max(alignof(OffsetType), alignof(std::byte*))>
pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign >::BucketBlockAllocator ( ByteSpan  region)
inlineexplicit

Non-constexpr constructor that automatically calls Init.

Parameters
[in]regionRegion 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.

Member Function Documentation

◆ Init() [1/3]

template<typename OffsetType = uintptr_t, size_t kMinBucketChunkSize = 32, size_t kNumBuckets = 5, size_t kAlign = std::max(alignof(OffsetType), alignof(std::byte*))>
void pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign >::Init ( BlockType *  begin)
inline

Sets the memory region to be used by this allocator.

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

Parameters
[in]regionRegion 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.

◆ Init() [2/3]

template<typename OffsetType = uintptr_t, size_t kMinBucketChunkSize = 32, size_t kNumBuckets = 5, size_t kAlign = std::max(alignof(OffsetType), alignof(std::byte*))>
void pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign >::Init ( BlockType *  begin,
BlockType *  end 
)
inlineoverridevirtual

Sets the memory region to be used by this allocator.

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

Parameters
[in]regionRegion 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.

Reimplemented from pw::allocator::BlockAllocator< OffsetType, kPoisonInterval, kAlign >.

◆ Init() [3/3]

template<typename OffsetType = uintptr_t, size_t kMinBucketChunkSize = 32, size_t kNumBuckets = 5, size_t kAlign = std::max(alignof(OffsetType), alignof(std::byte*))>
void pw::allocator::BucketBlockAllocator< OffsetType, kMinBucketChunkSize, kNumBuckets, kAlign >::Init ( ByteSpan  region)
inline

Sets the memory region to be used by this allocator.

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

Parameters
[in]regionRegion 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.
The documentation for this class was generated from the following file: