Memory-block abstraction whose purpose is to serve as a building block for custom memory-allocator implementations. More...

#include <block.h>

Inheritance diagram for temptable::Block:

[legend]

Public Member Functions
	Block () noexcept=default
	Default constructor which creates an empty Block. More...

	Block (size_t size, Source memory_source)
	Constructor which creates a Block of given size from the given memory source. More...

	Block (Chunk chunk) noexcept
	Constructor which creates a Block from given Chunk. More...

bool	operator== (const Block &other) const
	Equality operator. More...

bool	operator!= (const Block &other) const
	Inequality operator. More...

Chunk	allocate (size_t chunk_size) noexcept
	Allocate a Chunk from a Block. More...

size_t	deallocate (Chunk chunk, size_t chunk_size) noexcept
	Deallocate a Chunk from a Block. More...

void	destroy () noexcept
	Destroy the whole Block. More...

bool	is_empty () const
	Check if Block is empty (not holding any data). More...

bool	can_accommodate (size_t chunk_size) const
	Check if Block can fit (allocate) a Chunk of given size. More...

Source	type () const
	Get the Block Source type (memory where it resides). More...

size_t	size () const
	Get the Block size. More...

size_t	number_of_used_chunks () const
	Get current number of Chunks allocated by the Block. More...

std::string	to_string () const
	A human-readable string that describes a Block. More...

Static Public Member Functions
static size_t	size_hint (size_t n_bytes)
	For given size, how much memory will Block with single Chunk actually occupy. More...

Static Public Attributes
static constexpr size_t	ALIGN_TO = alignof(void *)
	Block will self-adjust all requested allocation-sizes to the multiple of this value. More...

Private Member Functions
	Block (uint8_t *block_memory, Source block_type, size_t block_size) noexcept
	Delegating constructor which populates Header with provided information. More...

bool	is_rightmost_chunk (const Chunk &chunk, size_t chunk_size) const
	Are we looking at the last (rightmost) chunk in a Block. More...

Private Member Functions inherited from temptable::Header
Source	memory_source_type () const
	Get the Block Source type (memory where it resides). More...

size_t	block_size () const
	Get the Block size. More...

size_t	number_of_used_chunks () const
	Get current number of Chunks allocated by the Block. More...

size_t	first_pristine_offset () const
	Get current first-pristine-offset. More...

	Header () noexcept
	Default constructor which creates an empty Header. More...

	Header (uint8_t *block_memory, Source block_memory_type, size_t block_size) noexcept
	Constructor which initializes the Header metadata when constructing fresh Blocks. More...

	Header (uint8_t *block_memory) noexcept
	Constructor which initializes the Header metadata from already existing Blocks in memory (e.g. More...

uint8_t *	next_available_slot () const
	Enable Block to get the next available slot that it can use for next Chunk allocation. More...

uint8_t *	block_address () const
	Enable Block to get its memory address. More...

size_t	increment_number_of_used_chunks (size_t chunk_size)
	Enable Block to increment the reference-count when (logically) allocating new Chunks. More...

size_t	decrement_number_of_used_chunks (size_t chunk_size, bool rightmost_chunk)
	Enable Block to decrement the reference-count when (logically) deallocating existing Chunks. More...

void	reset ()
	Enable Block to reset the Header metadata upon Block destruction. More...

Static Private Member Functions
static size_t	aligned_size (size_t size)
	What is the word-size (ALIGN_TO) aligned size of an input size? More...

Additional Inherited Members
Private Types inherited from temptable::Header
using	metadata_type = uintptr_t
	Type that we will be using for storing metadata information. More...

Static Private Attributes inherited from temptable::Header
static constexpr size_t	SIZE = 4 * sizeof(Header::metadata_type)
	Block header (metadata) size. More...

Detailed Description

Memory-block abstraction whose purpose is to serve as a building block for custom memory-allocator implementations.

TL;DR How it works: Instantiation:

With given size and given memory source, Block will allocate memory and adjust its Header metadata with the relevant information. Allocation:
From allocated memory space, Block finds out what is the next available slot to fit the new Chunk into.
Creates a new Chunk with the address pointing to that slot.
Increments the number of allocated chunks.
Returns a Chunk. Deallocation:
Decrements the number of allocated chunks.
Returns current number of allocated chunks. Destruction:
Simply deallocates the memory.

Now, more detailed description ...

Normally, custom memory-allocators will feed clients' memory allocation and deallocation requests solely through the provided Block interface which enables allocators not to worry about the whole lot of low-level memory byte-juggling but to focus on application-level details.

Block, once created, will occupy at-least (see below why) the specified amount of memory after which it will be able to serve client-requested allocations and deallocations in logical units called Chunks. Chunk is an arbitrarily-sized view over a region of memory allocated during the Block creation. Block can fit as many Chunks as there is free memory space left in it. Once there is no free space left, another Block of memory has to be created. Block is not resizeable. E.g. 4KB-sized Block can feed 1x4KB, 2x2KB, 1KB+3KB or any other combination of Chunks whose total size does not exceed the Block size (4KB).

Organizing Block memory into Chunks is implementation house-keeping detail stored in its Header metadata region. Block does not maintain the list of Chunks, it only ever keeps the number of currently allocated Chunks and the offset to the first memory location available to feed the next allocation request.

While still using the same interface, custom memory-allocators are able to choose where should the Block allocate actual memory from. It could be anything defined by Source but currently only RAM and MMAP-ed files are available and implemented as options.

For the benefit of (amortized) constant-time allocations, Block does not re-use or do any other special operations over deallocated Chunks so memory-allocators which will be using it may suffer from block-level memory-fragmentation and consequently higher memory-consumption. Exceptions are deallocations of first and last Chunks in a Block when it is possible to easily re-adjust the offset and therefore be able to re-use that part of memory.

Another big advantage, which is very closely related to constant-time allocations, is that it minimizes the number of system-calls required to allocate and deallocate the memory which consequently may lower the process-level memory-fragmentation.

Block size does not necessarily end-up being the size originally requested by the client but it will be actually implicitly rounded to the next multiple of CPU word-size which may result in better memory utilization. Actual block size can be queried through the Block interface.

To optimize for the CPU memory-access, but also to enable code not to segfault on architectures which do not support unaligned-memory-access (e.g. SPARC), Block will always adjust requested Chunk allocation size to match the size which is rounded to the next multiple of CPU word-size (Block::ALIGN_TO constant). End result is that Block might end up allocating just a few more bytes bigger Chunk than actually requested but that information, however, does not need to be maintained or cared about by the client code.

Along with the small space overhead due to the automatic word-size-adjustment of Chunk size, each Block allocation will also have a few bytes overhead for maintaining the Header metadata (Header::SIZE) as well as for maintaining the Chunk metadata (Chunk::METADATA_SIZE). Implementation and data layout details can be found at respective header file declarations.

All dirty-implementation details are hidden in Header implementation which makes sure that proper care is taken to handle chunk offsets, available slots, number of present chunks etc.

Constructor & Destructor Documentation

◆ Block() [1/4]

temptable::Block::Block ( )

defaultnoexcept

Default constructor which creates an empty Block.

◆ Block() [2/4]

temptable::Block::Block	(	size_t	size,
		Source	memory_source
	)

inline

Constructor which creates a Block of given size from the given memory source.

[in] Block size in bytes. [in] Source where Block will allocate actual memory from.

◆ Block() [3/4]

temptable::Block::Block ( Chunk chunk )

inlineexplicitnoexcept

Constructor which creates a Block from given Chunk.

Chunk holds just enough information so we can deduce which Block does it belong to.

[in] Existing Chunk in memory.

◆ Block() [4/4]

temptable::Block::Block	(	uint8_t *	block_memory,
		Source	block_type,
		size_t	block_size
	)

inlineprivatenoexcept

Delegating constructor which populates Header with provided information.

[in] Address of a memory region allocated by the Block [in] Source of memory region [in] Block size in bytes.

Member Function Documentation

◆ aligned_size()

size_t temptable::Block::aligned_size ( size_t size )

inlinestaticprivate

What is the word-size (ALIGN_TO) aligned size of an input size?

[in] Input size

Returns: Block-size rounded up to the next ALIGN_TO size

◆ allocate()

Chunk temptable::Block::allocate ( size_t chunk_size )

inlinenoexcept

Allocate a Chunk from a Block.

[in] Size of the Chunk to be allocated.

Returns: Chunk of memory.

◆ can_accommodate()

bool temptable::Block::can_accommodate ( size_t chunk_size ) const

inline

Check if Block can fit (allocate) a Chunk of given size.

[in] Desired chunk size in bytes.

Returns: true if can

◆ deallocate()

size_t temptable::Block::deallocate	(	Chunk	chunk,
		size_t	chunk_size
	)

inlinenoexcept

Deallocate a Chunk from a Block.

[in] Chunk to be deallocated. [in] Size of the Chunk to be deallocated.

Returns: Remaining number of Chunks in a Block.

◆ destroy()

void temptable::Block::destroy ( )

inlinenoexcept

Destroy the whole Block.

This operation will release all occupied memory by the Block so client code must make sure that it doesn't keep dangling Chunks in the memory.

◆ is_empty()

bool temptable::Block::is_empty ( void ) const

inline

Check if Block is empty (not holding any data).

Returns: true if it is

◆ is_rightmost_chunk()

bool temptable::Block::is_rightmost_chunk	(	const Chunk &	chunk,
		size_t	chunk_size
	)		const

inlineprivate

Are we looking at the last (rightmost) chunk in a Block.

[in] Reference to a Chunk [in] Chunk size

Returns: true if we are

◆ number_of_used_chunks()

size_t temptable::Block::number_of_used_chunks ( ) const

inline

Get current number of Chunks allocated by the Block.

Returns: Number of Chunks allocated by this Block

◆ operator!=()

bool temptable::Block::operator!= ( const Block & other ) const

inline

Inequality operator.

[in] Block to compare it against.

Returns: true if two Blocks are not equal (not pointing to the same memory location).

◆ operator==()

bool temptable::Block::operator== ( const Block & other ) const

inline

Equality operator.

[in] Block to compare it against.

Returns: true if two Blocks are equal (pointing to the same memory location).

◆ size()

size_t temptable::Block::size ( ) const

inline

Get the Block size.

Returns: Block size

◆ size_hint()

size_t temptable::Block::size_hint ( size_t n_bytes )

inlinestatic

For given size, how much memory will Block with single Chunk actually occupy.

This calculation takes into account both the Header/Chunk metadata and the data payload.

[in] Data payload size in bytes.

Returns: Size Block would allocate for given n_bytes.

◆ to_string()

std::string temptable::Block::to_string ( ) const

inline

A human-readable string that describes a Block.

Returns: human-readable string

◆ type()

Source temptable::Block::type ( ) const

inline

Get the Block Source type (memory where it resides).

Returns: one of Source values

Member Data Documentation

◆ ALIGN_TO

constexpr size_t temptable::Block::ALIGN_TO = alignof(void *)

staticconstexpr

Block will self-adjust all requested allocation-sizes to the multiple of this value.

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

storage/temptable/include/temptable/block.h

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Block() [1/4]

◆ Block() [2/4]

◆ Block() [3/4]

◆ Block() [4/4]

Member Function Documentation

◆ aligned_size()

◆ allocate()

◆ can_accommodate()

◆ deallocate()

◆ destroy()

◆ is_empty()

◆ is_rightmost_chunk()

◆ number_of_used_chunks()

◆ operator!=()

◆ operator==()

◆ size()

◆ size_hint()

◆ to_string()

◆ type()

Member Data Documentation

◆ ALIGN_TO