Implements a list allocator. More...

#include <list_allocator.hpp>

Inheritance diagram for m::list_allocator:

Collaboration diagram for m::list_allocator:

Public Types
using	base_type = allocator< list_allocator >

using	size_type = std::size_t

Public Member Functions
	list_allocator (size_type initial_size=0, AllocationStrategy strategy=AllocationStrategy::Linear)

	~list_allocator ()

	list_allocator (const list_allocator &other)
	Copy c'tor.

	list_allocator (list_allocator &&other)

list_allocator &	operator= (list_allocator other)

void *	allocate (const size_type size, const size_type alignment=0)

void	deallocate (void *ptr, const size_type size)

size_type	num_chunks_available () const

void	dump (std::ostream &out) const

void	dump () const

std::enable_if_t< not std::is_void_v< T >, T * >	allocate ()
	Allocate space for a single entity of type `T` that is aligned according to `T`s alignment requirement.

std::enable_if_t< not std::is_void_v< T >, T * >	allocate (size_type n)
	Allocate space for an array of `n` entities of type `T`.

std::enable_if_t< not std::is_void_v< T >, void >	deallocate (T *ptr)
	Deallocate the space for an entity of type `T` at `ptr`.

std::enable_if_t< not std::is_void_v< T >, void >	deallocate (T *arr, size_type n)
	Deallocate the space for an array of `n` entities of type `T`.

std::enable_if_t< not std::is_array_v< T >, std::unique_ptr< T > >	make_unique ()

std::enable_if_t< std::is_array_v< T >, std::unique_ptr< T > >	make_unique (size_type n)

void	dispose (std::unique_ptr< T > ptr)

void	dispose (std::unique_ptr< T > ptr, size_type n)

Private Types
using	chunk_list_type = doubly_linked_list< size_type, list_allocator_proxy >
	‍the type of the internal list of unused chunks

using	header_type = chunk_list_type::node_type
	‍the type of a list node, which is the "header" of an unused chunk

Private Member Functions
chunk_list_type::iterator	unlink_chunk (chunk_list_type::iterator it)
	Removes the referenced chunk from the list of available chunks without deallocating its memory.

chunk_list_type::iterator	link_chunk (chunk_list_type::iterator pos, void *chunk, size_type masked_size)
	Adds the given `chunk` to the list of unused chunks by emplacing the list node within the chunk's memory.

chunk_list_type::iterator	insert_chunk_sorted (void *chunk, size_type masked_size)

void	reclaim_chunk (void *chunk, size_type masked_size)

chunk_list_type::iterator	add_fresh_chunk (const size_type size, const size_type alignment)
	Allocates fresh memory that contains enough space to fit a chunk of size `size`, that is aligned according to `alignment`, and that also fits a header.

chunk_list_type::iterator	split_unused_chunk (chunk_list_type::iterator it, size_type required_size)
	Splits the given `chunk` into two chunks.

chunk_list_type::iterator	coalesce (chunk_list_type::iterator it)
	Attempt to coalesce the chunk pointed to by `it` and its successor.

void *	proxy_allocate (size_type, size_type)

void	proxy_deallocate (void *ptr, size_type)

void *	aligned_mmap (size_type size, size_type alignment)

Static Private Member Functions
static bool	is_unaligned (void *ptr, size_type alignment)

static bool	is_aligned (void *ptr, size_type alignment)

static size_type &	size_of_used_chunk (void *chunk, const size_type size)
	Returns a reference to the effective size field of a chunk in use.

static size_type	size_of_used_chunk (const void *chunk, const size_type size)

static header_type *	header_of_unused_chunk (size_type *value_addr)
	Returns a pointer to the header of an unused chunk.

static const header_type *	header_of_unused_chunk (const size_type *value_addr)

static bool	is_marked_for_deallocation (const header_type *header)

static size_type	extract_size (const header_type *header)

static size_type	mark_for_deallocation (size_type n)

static size_type	preserve_deallocation (size_type n, const header_type *header)

Private Attributes
size_type	min_allocation_size_
	‍the size of the next actual memory allocation

size_type	min_allocation_alignment_
	‍the minimum alignment of an actual memory allocation

AllocationStrategy	strategy_
	‍the allocation strategy; influences how `min_allocation_size_` is updated with each actual allocation

chunk_list_type	chunks_
	‍the list of unused (free) chunks

void *	override_addr_ = nullptr
	‍used to override the behavior of allocation requests by `chunks_` by routing through a proxy allocator

Static Private Attributes
static constexpr size_type	CHUNK_SPLIT_FACTOR = 2
	‍the factor by which a chunk must be larger than the requested allocation to be considered for splitting

static constexpr size_type	DEALLOCATION_BIT_MASK = size_type(1U) << (sizeof(size_type) * CHAR_BIT - 1U)
	‍mask of the high bit of a size_type (the type of the header of a used chunk)

Friends
struct	list_allocator_proxy

void	swap (list_allocator &first, list_allocator &second)

M_LCOV_EXCL_START friend std::ostream &	operator<< (std::ostream &out, const list_allocator &A)

Detailed Description

Implements a list allocator.

Allocated (in use) chunk: +--------—+---—+----------—+ | used part | size | unused part | +--------—+---—+----------—+ ^^^^ header

The unused part may be empty.

Unused (in list) chunk: +--------—+-----------------—+ | ptr, size | unused space | +--------—+-----------------—+ ^^^^^^^^^ header

The crux is to move the header when a chunk is allocated. This enables us to locate the header once the chunk is deallocated. The header stores the effective/actual size of the chunk. (It does not necessarily store the size requested by the client's allocation. As long as a chunk is in use, we have no way of locating the header. The client must properly deallocate the chunk by specifying the size that was specified when the chunk was allocated.

Definition at line 93 of file list_allocator.hpp.

Member Typedef Documentation

◆ base_type

using m::list_allocator::base_type = allocator<list_allocator>

Definition at line 97 of file list_allocator.hpp.

◆ chunk_list_type

using m::list_allocator::chunk_list_type = doubly_linked_list<size_type, list_allocator_proxy>

private

‍the type of the internal list of unused chunks

Definition at line 115 of file list_allocator.hpp.

◆ header_type

using m::list_allocator::header_type = chunk_list_type::node_type

private

‍the type of a list node, which is the "header" of an unused chunk

Definition at line 119 of file list_allocator.hpp.

◆ size_type

using m::allocator< list_allocator >::size_type = std::size_t

inherited

Definition at line 19 of file allocator_base.hpp.

Constructor & Destructor Documentation

◆ list_allocator() [1/3]

m::list_allocator::list_allocator	(	size_type	initial_size = `0`,
		AllocationStrategy	strategy = `AllocationStrategy::Linear`
	)

inline

Definition at line 144 of file list_allocator.hpp.

References add_fresh_chunk(), chunks_, m::doubly_linked_list< T, Allocator >::empty(), m::get_pagesize(), M_insist, min_allocation_alignment_, min_allocation_size_, and m::doubly_linked_list< T, Allocator >::size().

◆ ~list_allocator()

m::list_allocator::~list_allocator ( )

inline

Definition at line 162 of file list_allocator.hpp.

References m::doubly_linked_list< T, Allocator >::begin(), chunks_, m::doubly_linked_list< T, Allocator >::empty(), m::doubly_linked_list< T, Allocator >::erase(), extract_size(), header_of_unused_chunk(), is_marked_for_deallocation(), and override_addr_.

◆ list_allocator() [2/3]

m::list_allocator::list_allocator ( const list_allocator & other )

inlineexplicit

Copy c'tor.

Copies the current behavior (allocation size and strategy). Does not copy the current allocations.

Definition at line 177 of file list_allocator.hpp.

◆ list_allocator() [3/3]

m::list_allocator::list_allocator ( list_allocator && other )

inline

Definition at line 181 of file list_allocator.hpp.

References swap.

Member Function Documentation

◆ add_fresh_chunk()

chunk_list_type::iterator m::list_allocator::add_fresh_chunk	(	const size_type	size,
		const size_type	alignment
	)

inlineprivate

Allocates fresh memory that contains enough space to fit a chunk of size size, that is aligned according to alignment, and that also fits a header.

The chunk is added to the list of chunks.

Returns: an iterator to the chunk

Definition at line 351 of file list_allocator.hpp.

References aligned_mmap(), m::Exponential, insert_chunk_sorted(), is_aligned(), m::is_pow_2(), m::Linear, M_insist, mark_for_deallocation(), min_allocation_alignment_, min_allocation_size_, override_addr_, and strategy_.

Referenced by allocate(), and list_allocator().

◆ aligned_mmap()

void * m::list_allocator::aligned_mmap	(	size_type	size,
		size_type	alignment
	)

inlineprivate

Definition at line 479 of file list_allocator.hpp.

References m::get_pagesize(), is_aligned(), and M_insist.

Referenced by add_fresh_chunk().

◆ allocate() [1/3]

std::enable_if_t< not std::is_void_v< T >, T * > m::allocator< list_allocator >::allocate ( )

inlineinherited

Allocate space for a single entity of type T that is aligned according to Ts alignment requirement.

Definition at line 40 of file allocator_base.hpp.

◆ allocate() [2/3]

void * m::list_allocator::allocate	(	const size_type	size,
		const size_type	alignment = `0`
	)

inline

Definition at line 185 of file list_allocator.hpp.

References add_fresh_chunk(), m::and, m::doubly_linked_list< T, Allocator >::begin(), CHUNK_SPLIT_FACTOR, chunks_, m::doubly_linked_list< T, Allocator >::end(), extract_size(), header_of_unused_chunk(), m::is_pow_2(), is_unaligned(), M_insist, size_of_used_chunk(), split_unused_chunk(), and unlink_chunk().

◆ allocate() [3/3]

std::enable_if_t< not std::is_void_v< T >, T * > m::allocator< list_allocator >::allocate ( size_type n )

inlineinherited

Allocate space for an array of n entities of type T.

The space is aligned according to Ts alignment requirement.

Definition at line 46 of file allocator_base.hpp.

◆ coalesce()

chunk_list_type::iterator m::list_allocator::coalesce ( chunk_list_type::iterator it )

inlineprivate

Attempt to coalesce the chunk pointed to by it and its successor.

Returns: an iterator to the coalesced chunk, if coalescing succeeded, it otherwise

Definition at line 428 of file list_allocator.hpp.

References chunks_, m::doubly_linked_list< T, Allocator >::end(), extract_size(), header_of_unused_chunk(), is_marked_for_deallocation(), M_insist, and unlink_chunk().

Referenced by reclaim_chunk().

◆ deallocate() [1/3]

std::enable_if_t< not std::is_void_v< T >, void > m::allocator< list_allocator >::deallocate	(	T *	arr,
		size_type	n
	)

inlineinherited

Deallocate the space for an array of n entities of type T.

Definition at line 56 of file allocator_base.hpp.

◆ deallocate() [2/3]

std::enable_if_t< not std::is_void_v< T >, void > m::allocator< list_allocator >::deallocate ( T * ptr )

inlineinherited

Deallocate the space for an entity of type T at ptr.

Definition at line 51 of file allocator_base.hpp.

◆ deallocate() [3/3]

void m::list_allocator::deallocate	(	void *	ptr,
		const size_type	size
	)

inline

Definition at line 230 of file list_allocator.hpp.

References reclaim_chunk(), and size_of_used_chunk().

◆ dispose() [1/2]

void m::allocator< list_allocator >::dispose ( std::unique_ptr< T > ptr )

inlineinherited

Definition at line 71 of file allocator_base.hpp.

◆ dispose() [2/2]

void m::allocator< list_allocator >::dispose	(	std::unique_ptr< T >	ptr,
		size_type	n
	)

inlineinherited

Definition at line 74 of file allocator_base.hpp.

◆ dump() [1/2]

void m::list_allocator::dump ( ) const

inline

Definition at line 256 of file list_allocator.hpp.

References dump().

Referenced by dump().

◆ dump() [2/2]

void m::list_allocator::dump ( std::ostream & out ) const

inline

Definition at line 255 of file list_allocator.hpp.

◆ extract_size()

static size_type m::list_allocator::extract_size ( const header_type * header )

inlinestaticprivate

Definition at line 301 of file list_allocator.hpp.

Referenced by allocate(), coalesce(), split_unused_chunk(), and ~list_allocator().

◆ header_of_unused_chunk() [1/2]

static const header_type * m::list_allocator::header_of_unused_chunk ( const size_type * value_addr )

inlinestaticprivate

Definition at line 294 of file list_allocator.hpp.

◆ header_of_unused_chunk() [2/2]

static header_type * m::list_allocator::header_of_unused_chunk ( size_type * value_addr )

inlinestaticprivate

Returns a pointer to the header of an unused chunk.

Definition at line 289 of file list_allocator.hpp.

Referenced by allocate(), coalesce(), reclaim_chunk(), split_unused_chunk(), unlink_chunk(), and ~list_allocator().

◆ insert_chunk_sorted()

chunk_list_type::iterator m::list_allocator::insert_chunk_sorted	(	void *	chunk,
		size_type	masked_size
	)

inlineprivate

Definition at line 329 of file list_allocator.hpp.

References m::and, m::doubly_linked_list< T, Allocator >::begin(), chunks_, m::doubly_linked_list< T, Allocator >::end(), and link_chunk().

Referenced by add_fresh_chunk(), and reclaim_chunk().

◆ is_aligned()

static bool m::list_allocator::is_aligned	(	void *	ptr,
		size_type	alignment
	)

inlinestaticprivate

Definition at line 269 of file list_allocator.hpp.

References is_unaligned().

Referenced by add_fresh_chunk(), and aligned_mmap().

◆ is_marked_for_deallocation()

static bool m::list_allocator::is_marked_for_deallocation ( const header_type * header )

inlinestaticprivate

Definition at line 300 of file list_allocator.hpp.

References DEALLOCATION_BIT_MASK.

Referenced by coalesce(), split_unused_chunk(), and ~list_allocator().

◆ is_unaligned()

static bool m::list_allocator::is_unaligned	(	void *	ptr,
		size_type	alignment
	)

inlinestaticprivate

Definition at line 264 of file list_allocator.hpp.

References m::is_pow_2(), and M_insist.

Referenced by allocate(), and is_aligned().

◆ link_chunk()

chunk_list_type::iterator m::list_allocator::link_chunk	(	chunk_list_type::iterator	pos,
		void *	chunk,
		size_type	masked_size
	)

inlineprivate

Adds the given chunk to the list of unused chunks by emplacing the list node within the chunk's memory.

The list node is inserted at position pos within the linked list.

Definition at line 321 of file list_allocator.hpp.

References chunks_, m::doubly_linked_list< T, Allocator >::end(), m::doubly_linked_list< T, Allocator >::insert(), M_insist, and override_addr_.

Referenced by insert_chunk_sorted(), and split_unused_chunk().

◆ make_unique() [1/2]

std::enable_if_t< not std::is_array_v< T >, std::unique_ptr< T > > m::allocator< list_allocator >::make_unique ( )

inlineinherited

Definition at line 64 of file allocator_base.hpp.

◆ make_unique() [2/2]

std::enable_if_t< std::is_array_v< T >, std::unique_ptr< T > > m::allocator< list_allocator >::make_unique ( size_type n )

inlineinherited

Definition at line 68 of file allocator_base.hpp.

◆ mark_for_deallocation()

static size_type m::list_allocator::mark_for_deallocation ( size_type n )

inlinestaticprivate

Definition at line 302 of file list_allocator.hpp.

References DEALLOCATION_BIT_MASK.

Referenced by add_fresh_chunk().

◆ num_chunks_available()

size_type m::list_allocator::num_chunks_available ( ) const

inline

Definition at line 236 of file list_allocator.hpp.

References chunks_, and m::doubly_linked_list< T, Allocator >::size().

◆ operator=()

list_allocator & m::list_allocator::operator= ( list_allocator other )

inline

Definition at line 183 of file list_allocator.hpp.

References swap.

◆ preserve_deallocation()

static size_type m::list_allocator::preserve_deallocation	(	size_type	n,
		const header_type *	header
	)

inlinestaticprivate

Definition at line 303 of file list_allocator.hpp.

References DEALLOCATION_BIT_MASK.

Referenced by split_unused_chunk().

◆ proxy_allocate()

void * m::list_allocator::proxy_allocate	(	size_type	,
		size_type
	)

inlineprivate

Definition at line 466 of file list_allocator.hpp.

References M_insist, and override_addr_.

◆ proxy_deallocate()

void m::list_allocator::proxy_deallocate	(	void *	ptr,
		size_type
	)

inlineprivate

Definition at line 473 of file list_allocator.hpp.

References M_insist, and override_addr_.

◆ reclaim_chunk()

void m::list_allocator::reclaim_chunk	(	void *	chunk,
		size_type	masked_size
	)

inlineprivate

Definition at line 338 of file list_allocator.hpp.

References m::doubly_linked_list< T, Allocator >::begin(), chunks_, coalesce(), m::doubly_linked_list< T, Allocator >::end(), header_of_unused_chunk(), insert_chunk_sorted(), and M_insist.

Referenced by deallocate().

◆ size_of_used_chunk() [1/2]

static size_type m::list_allocator::size_of_used_chunk	(	const void *	chunk,
		const size_type	size
	)

inlinestaticprivate

Definition at line 282 of file list_allocator.hpp.

◆ size_of_used_chunk() [2/2]

static size_type & m::list_allocator::size_of_used_chunk	(	void *	chunk,
		const size_type	size
	)

inlinestaticprivate

Returns a reference to the effective size field of a chunk in use.

Definition at line 277 of file list_allocator.hpp.

Referenced by allocate(), and deallocate().

◆ split_unused_chunk()

chunk_list_type::iterator m::list_allocator::split_unused_chunk	(	chunk_list_type::iterator	it,
		size_type	required_size
	)

inlineprivate

Splits the given chunk into two chunks.

The first chunk will be located at chunk and have a usable size not less than required_size. The second chunk, containing the remaining space of the original chunk, is added to the list of chunks. Alignment is assumed and not checked.

Returns: iterator to the first chunk

Definition at line 391 of file list_allocator.hpp.

References extract_size(), header_of_unused_chunk(), is_marked_for_deallocation(), link_chunk(), M_insist, and preserve_deallocation().

Referenced by allocate().

◆ unlink_chunk()

chunk_list_type::iterator m::list_allocator::unlink_chunk ( chunk_list_type::iterator it )

inlineprivate

Removes the referenced chunk from the list of available chunks without deallocating its memory.

Definition at line 313 of file list_allocator.hpp.

References chunks_, m::doubly_linked_list< T, Allocator >::erase(), header_of_unused_chunk(), and override_addr_.

Referenced by allocate(), and coalesce().

Friends And Related Function Documentation

◆ list_allocator_proxy

friend struct list_allocator_proxy

friend

Definition at line 95 of file list_allocator.hpp.

◆ operator<<

M_LCOV_EXCL_START friend std::ostream & operator<<	(	std::ostream &	out,
		const list_allocator &	A
	)

friend

Definition at line 239 of file list_allocator.hpp.

◆ swap

void swap	(	list_allocator &	first,
		list_allocator &	second
	)

friend

Definition at line 124 of file list_allocator.hpp.

Referenced by list_allocator(), and operator=().

Field Documentation

◆ CHUNK_SPLIT_FACTOR

constexpr size_type m::list_allocator::CHUNK_SPLIT_FACTOR = 2

staticconstexprprivate

‍the factor by which a chunk must be larger than the requested allocation to be considered for splitting

Definition at line 103 of file list_allocator.hpp.

Referenced by allocate().

◆ chunks_

chunk_list_type m::list_allocator::chunks_

private

‍the list of unused (free) chunks

Definition at line 117 of file list_allocator.hpp.

Referenced by allocate(), coalesce(), insert_chunk_sorted(), link_chunk(), list_allocator(), num_chunks_available(), reclaim_chunk(), unlink_chunk(), and ~list_allocator().

◆ DEALLOCATION_BIT_MASK

constexpr size_type m::list_allocator::DEALLOCATION_BIT_MASK = size_type(1U) << (sizeof(size_type) * CHAR_BIT - 1U)

staticconstexprprivate

‍mask of the high bit of a size_type (the type of the header of a used chunk)

Definition at line 105 of file list_allocator.hpp.

Referenced by is_marked_for_deallocation(), mark_for_deallocation(), and preserve_deallocation().

◆ min_allocation_alignment_

size_type m::list_allocator::min_allocation_alignment_

private

‍the minimum alignment of an actual memory allocation

Definition at line 110 of file list_allocator.hpp.

Referenced by add_fresh_chunk(), and list_allocator().

◆ min_allocation_size_

size_type m::list_allocator::min_allocation_size_

private

‍the size of the next actual memory allocation

Definition at line 108 of file list_allocator.hpp.

Referenced by add_fresh_chunk(), and list_allocator().

◆ override_addr_

void* m::list_allocator::override_addr_ = nullptr

private

‍used to override the behavior of allocation requests by chunks_ by routing through a proxy allocator

Definition at line 121 of file list_allocator.hpp.

Referenced by add_fresh_chunk(), link_chunk(), proxy_allocate(), proxy_deallocate(), unlink_chunk(), and ~list_allocator().

◆ strategy_

AllocationStrategy m::list_allocator::strategy_

private

‍the allocation strategy; influences how min_allocation_size_ is updated with each actual allocation

Definition at line 112 of file list_allocator.hpp.

Referenced by add_fresh_chunk().

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

include/mutable/util/list_allocator.hpp

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ base_type

◆ chunk_list_type

◆ header_type

◆ size_type

Constructor & Destructor Documentation

◆ list_allocator() [1/3]

◆ ~list_allocator()

◆ list_allocator() [2/3]

◆ list_allocator() [3/3]

Member Function Documentation

◆ add_fresh_chunk()

◆ aligned_mmap()

◆ allocate() [1/3]

◆ allocate() [2/3]

◆ allocate() [3/3]

◆ coalesce()

◆ deallocate() [1/3]

◆ deallocate() [2/3]

◆ deallocate() [3/3]

◆ dispose() [1/2]

◆ dispose() [2/2]

◆ dump() [1/2]

◆ dump() [2/2]

◆ extract_size()

◆ header_of_unused_chunk() [1/2]

◆ header_of_unused_chunk() [2/2]

◆ insert_chunk_sorted()

◆ is_aligned()

◆ is_marked_for_deallocation()

◆ is_unaligned()

◆ link_chunk()

◆ make_unique() [1/2]

◆ make_unique() [2/2]

◆ mark_for_deallocation()

◆ num_chunks_available()

◆ operator=()

◆ preserve_deallocation()

◆ proxy_allocate()

◆ proxy_deallocate()

◆ reclaim_chunk()

◆ size_of_used_chunk() [1/2]

◆ size_of_used_chunk() [2/2]

◆ split_unused_chunk()

◆ unlink_chunk()

Friends And Related Function Documentation

◆ list_allocator_proxy

◆ operator<<

◆ swap

Field Documentation

◆ CHUNK_SPLIT_FACTOR

◆ chunks_

◆ DEALLOCATION_BIT_MASK

◆ min_allocation_alignment_

◆ min_allocation_size_

◆ override_addr_

◆ strategy_