#include <block.h>

Classes
class	Iterator

class	Range

class	ReverseIterator

class	ReverseRange

Public Types
using	offset_type = OffsetType

Public Member Functions
	Block (const Block &other)=delete

Block &	operator= (const Block &other)=delete

size_t	OuterSize () const

size_t	InnerSize () const

size_t	RequestedSize () const

std::byte *	UsableSpace ()

const std::byte *	UsableSpace () const

StatusWithSize	CanAllocLast (Layout layout) const

Block *	Next () const

Block *	Prev () const

size_t	Alignment () const
	Returns the current alignment of a block.

bool	Used () const

bool	Last () const

void	MarkUsed ()
	Marks this block as in use.

void	MarkFree ()
	Marks this block as free.

void	MarkLast ()
	Marks this block as the last one in the chain.

void	ClearLast ()
	Clears the last bit from this block.

void	Poison (bool should_poison=true)

bool	IsValid () const
	Checks if a block is valid.

void	CrashIfInvalid () const
	Crashes with an informtaional message if a block is invalid.

Static Public Member Functions
static Result< Block * >	Init (ByteSpan region)
	Creates the first block for a given memory region.

template<int &... DeducedTypesOnly, typename PtrType , bool is_const_ptr = std::is_const_v<std::remove_pointer_t<PtrType>>, typename BytesPtr = std::conditional_t<is_const_ptr, const std::byte, std::byte>, typename BlockPtr = std::conditional_t<is_const_ptr, const Block, Block>>
static BlockPtr	FromUsableSpace (PtrType usable_space)

static Status	AllocFirst (Block *&block, Layout layout)

static Status	AllocLast (Block *&block, Layout layout)

static void	Free (Block *&block)

static Status	Resize (Block *&block, size_t new_inner_size)

static Block *	NextBlock (const Block *block)

static Block *	PrevBlock (const Block *block)

Static Public Attributes
static constexpr size_t	kAlignment = std::max(kAlign, alignof(offset_type))

static constexpr size_t	kBlockOverhead = AlignUp(sizeof(Block), kAlignment)

Detailed Description

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>
class pw::allocator::Block< OffsetType, kAlign, kCanPoison >

Memory region with links to adjacent blocks.

The blocks do not encode their size directly. Instead, they encode offsets to the next and previous blocks using the type given by the OffsetType template parameter. The encoded offsets are simply the offsets divded by the minimum block alignment, kAlignment.

The kAlignment constant provided by the derived block is typically the minimum value of alignof(OffsetType). Since the addressable range of a block is given by std::numeric_limits<OffsetType>::max() * kAlignment, it may be advantageous to set a higher alignment if it allows using a smaller offset type, even if this wastes some bytes in order to align block headers.

Blocks will always be aligned to a kAlignment boundary. Block sizes will always be rounded up to a multiple of kAlignment.

If kCanPoison is set, allocators may call Poison to overwrite the contents of a block with a poison pattern. This pattern will subsequently be checked when allocating blocks, and can detect memory corruptions such as use-after-frees.

As an example, the diagram below represents two contiguous Block<uint32_t, true, 8>s. The indices indicate byte offsets:

Block 1:
+---------------------+------+--------------+
| Header              | Info | Usable space |
+----------+----------+------+--------------+
| Prev     | Next     |      |              |
| 0......3 | 4......7 | 8..9 | 10.......280 |
| 00000000 | 00000046 | 8008 |  <app data>  |
+----------+----------+------+--------------+
Block 2:
+---------------------+------+--------------+
| Header              | Info | Usable space |
+----------+----------+------+--------------+
| Prev     | Next     |      |              |
| 0......3 | 4......7 | 8..9 | 10......1056 |
| 00000046 | 00000106 | 6008 | f7f7....f7f7 |
+----------+----------+------+--------------+

The overall size of the block (e.g. 280 bytes) is given by its next offset multiplied by the alignment (e.g. 0x106 * 4). Also, the next offset of a block matches the previous offset of its next block. The first block in a list is denoted by having a previous offset of 0.

Template Parameters

OffsetType	Unsigned integral type used to encode offsets. Larger types can address more memory, but consume greater overhead.
kCanPoison	Indicates whether to enable poisoning free blocks.
kAlign	Sets the overall alignment for blocks. Minimum is `alignof(OffsetType)` (the default). Larger values can address more memory, but consume greater overhead.

Member Function Documentation

◆ AllocFirst()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Status pw::allocator::Block< OffsetType, kAlign, kCanPoison >::AllocFirst	(	Block< OffsetType, kAlign, kCanPoison > *&	block,
		Layout	layout
	)

static

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 and replace the given block pointer with a pointer to the new, smaller block. 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.

Precondition: The block must not be in use.

Returns

embed:rst:leading-asterisk
 
* 
*  .. pw-status-codes::
* 
*     OK: The split completed successfully.
* 
*     FAILED_PRECONDITION: This block is in use and cannot be split.
* 
*     OUT_OF_RANGE: The requested size plus padding needed for alignment
*     is greater than the current size.
* 
*

◆ AllocLast()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Status pw::allocator::Block< OffsetType, kAlign, kCanPoison >::AllocLast	(	Block< OffsetType, kAlign, kCanPoison > *&	block,
		Layout	layout
	)

static

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 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 and replace the given block pointer with a pointer to the new, smaller block. An additional block may be created for the leading space.

Precondition: The block must not be in use.

Returns

embed:rst:leading-asterisk
 
* 
*  .. pw-status-codes::
* 
*     OK: The split completed successfully.
* 
*     FAILED_PRECONDITION: This block is in use and cannot be split.
* 
*     OUT_OF_RANGE: The requested size is greater than the current size.
* 
*     RESOURCE_EXHAUSTED: The remaining space is too small to hold a new
*     block.
* 
*

◆ CanAllocLast()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

StatusWithSize pw::allocator::Block< OffsetType, kAlign, kCanPoison >::CanAllocLast ( Layout layout ) const

Checks if an aligned block could be split from the end of the block.

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

Precondition: The block must not be in use.

Returns

embed:rst:leading-asterisk
 
* 
*  .. pw-status-codes::
* 
*     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.
* 
*     OUT_OF_RANGE: The requested size is greater than the current size.
* 
*     RESOURCE_EXHAUSTED: The remaining space is too small to hold a
*     new block.
* 
*

◆ CrashIfInvalid()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

void pw::allocator::Block< OffsetType, kAlign, kCanPoison >::CrashIfInvalid

Crashes with an informtaional message if a block is invalid.

Does nothing if the block is valid.

◆ Free()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

void pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Free ( Block< OffsetType, kAlign, kCanPoison > *& block )

static

Marks the block as free and merges it with any free neighbors.

This method is static in order to consume and replace the given block pointer. If neither member is free, the returned pointer will point to the original block. Otherwise, it will point to the new, larger block created by merging adjacent free blocks together.

◆ FromUsableSpace()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

template<int &... DeducedTypesOnly, typename PtrType , bool is_const_ptr = std::is_const_v<std::remove_pointer_t<PtrType>>, typename BytesPtr = std::conditional_t<is_const_ptr, const std::byte*, std::byte*>, typename BlockPtr = std::conditional_t<is_const_ptr, const Block*, Block*>>

static BlockPtr pw::allocator::Block< OffsetType, kAlign, kCanPoison >::FromUsableSpace ( PtrType usable_space )

inlinestatic

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

This is the inverse of UsableSpace().

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

◆ Init()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Result< Block< OffsetType, kAlign, kCanPoison > * > pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Init ( ByteSpan region )

static

Creates the first block for a given memory region.

Returns

embed:rst:leading-asterisk
 
* 
*  .. pw-status-codes::
* 
*     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 too big to be addressed using
*     ``OffsetType``.
* 
*

◆ InnerSize()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

size_t pw::allocator::Block< OffsetType, kAlign, kCanPoison >::InnerSize ( ) const

inline

Returns: The number of usable bytes inside the block.

◆ IsValid()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

bool pw::allocator::Block< OffsetType, kAlign, kCanPoison >::IsValid ( ) const

inline

Checks if a block is valid.

Returns

true if and only if the following conditions are met:

The block is aligned.
The prev/next fields match with the previous and next blocks.
The poisoned bytes are not damaged (if poisoning is enabled).

◆ Last()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

bool pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Last ( ) const

inline

Indicates whether this block is the last block or not (i.e. whether Next() points to a valid block or not). This is needed because Next() points to the end of this block, whether there is a valid block there or not.

Returns: true is this is the last block or false if not.

◆ Next()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Block< OffsetType, kAlign, kCanPoison > * pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Next

Fetches the block immediately after this one.

For performance, this always returns a block pointer, even if the returned pointer is invalid. The pointer is valid if and only if Last() is false.

Typically, after calling Init callers may save a pointer past the end of the list using Next(). This makes it easy to subsequently iterate over the list:

auto result = Block<>::Init(byte_span);
Block<>* begin = *result;
Block<>* end = begin->Next();
...
for (auto* block = begin; block != end; block = block->Next()) {
  // Do something which each block.
}

◆ NextBlock()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

static Block * pw::allocator::Block< OffsetType, kAlign, kCanPoison >::NextBlock ( const Block< OffsetType, kAlign, kCanPoison > * block )

inlinestatic

◆ OuterSize()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

size_t pw::allocator::Block< OffsetType, kAlign, kCanPoison >::OuterSize ( ) const

inline

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

◆ Poison()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

void pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Poison ( bool should_poison = true )

Poisons the block's usable space.

This method does nothing if kCanPoison is false, or if the block is in use, or if should_poison is false. The decision to poison a block is deferred 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.

Parameters

should_poison Indicates tha block should be poisoned, if poisoning is enabled.

◆ Prev()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Block< OffsetType, kAlign, kCanPoison > * pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Prev

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

◆ PrevBlock()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

static Block * pw::allocator::Block< OffsetType, kAlign, kCanPoison >::PrevBlock ( const Block< OffsetType, kAlign, kCanPoison > * block )

inlinestatic

◆ RequestedSize()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

size_t pw::allocator::Block< OffsetType, kAlign, kCanPoison >::RequestedSize ( ) const

inline

Returns: The number of bytes requested using AllocFirst, AllocLast, or Resize.

◆ Resize()

template<typename OffsetType , size_t kAlign, bool kCanPoison>

Status pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Resize	(	Block< OffsetType, kAlign, kCanPoison > *&	block,
		size_t	new_inner_size
	)

static

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.

This method is static in order to consume and replace the given block pointer with a pointer to the new, smaller block.

Precondition: The block must be in use.

Returns

embed:rst:leading-asterisk
 
* 
*  .. pw-status-codes::
* 
*     OK: The resize completed successfully.
* 
*     FAILED_PRECONDITION: This block is not in use.
* 
*     OUT_OF_RANGE: The requested size is greater than the available space.
* 
*

◆ UsableSpace()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

std::byte * pw::allocator::Block< OffsetType, kAlign, kCanPoison >::UsableSpace ( )

inline

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

◆ Used()

template<typename OffsetType = uintptr_t, size_t kAlign = alignof(OffsetType), bool kCanPoison = false>

bool pw::allocator::Block< OffsetType, kAlign, kCanPoison >::Used ( ) const

inline

Indicates whether the block is in use.

Returns: true if the block is in use or false if not.

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

/b/s/w/ir/x/w/co/pw_allocator/public/pw_allocator/block.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Function Documentation

◆ AllocFirst()

◆ AllocLast()

◆ CanAllocLast()

◆ CrashIfInvalid()

◆ Free()

◆ FromUsableSpace()

◆ Init()

◆ InnerSize()

◆ IsValid()

◆ Last()

◆ Next()

◆ NextBlock()

◆ OuterSize()

◆ Poison()

◆ Prev()

◆ PrevBlock()

◆ RequestedSize()

◆ Resize()

◆ UsableSpace()

◆ Used()