Michael's allocator. More...

#include <cds/memory/michael/allocator.h>

Inheritance diagram for cds::memory::michael::Heap< Options >:

Data Structures
class	active_tag
	Processor heap's `active` field. More...

struct	anchor_tag
	Anchor of the superblock descriptor. Updated by CAS. More...

class	block_header
	Allocated block header. More...

struct	processor_desc
	Processor descriptor. More...

struct	processor_heap_base
	Processor heap. More...

struct	superblock_desc
	Superblock descriptor. More...

Public Types
enum	superblock_state { SBSTATE_ACTIVE = 0, SBSTATE_FULL = 1, SBSTATE_PARTIAL = 2, SBSTATE_EMPTY = 3 }
	Superblock states. More...

typedef options::sys_topology	sys_topology
	effective system topology

typedef options::system_heap	system_heap
	effective system heap

typedef options::aligned_heap	aligned_heap
	effective aligned heap

typedef options::sizeclass_selector	sizeclass_selector
	effective sizeclass selector

typedef options::page_heap	page_heap
	effective page heap

typedef options::procheap_stat	procheap_stat
	effective processor heap statistics

typedef options::os_allocated_stat	os_allocated_stat
	effective OS-allocated memory statistics

typedef details::bound_checker_selector < typename options::check_bounds >	bound_checker
	effective bound checker

typedef cds::details::type_padding < processor_heap_base, c_nAlignment >::type	processor_heap
	Aligned superblock descriptor.

Public Member Functions
	Heap ()
	Heap constructor.

	~Heap ()
	Heap destructor. More...

void *	alloc (size_t nSize)
	Allocate memory block. More...

void	free (void *pMemory)
	Free previously allocated memory block. More...

void *	realloc (void *pMemory, size_t nNewSize)
	Reallocate memory block. More...

void *	alloc_aligned (size_t nSize, size_t nAlignment)
	Allocate aligned memory block. More...

void	free_aligned (void *pMemory)
	Free aligned memory block previously allocated by alloc_aligned. More...

void	summaryStat (summary_stat &st)
	Get instant summary statistics.

Static Public Attributes
static const size_t	c_nMaxBlockInSuperBlock = 1024 * 2
	Max count of blocks in superblock (2 ** 11)

Protected Attributes
sys_topology	m_Topology
	System topology.

system_heap	m_LargeHeap
	Heap for large block.

aligned_heap	m_AlignedHeap
	Internal aligned heap.

sizeclass_selector	m_SizeClassSelector
	Size-class selector.

std::atomic< processor_desc * > *	m_arrProcDesc
	array of pointers to the processor descriptors

unsigned int	m_nProcessorCount
	Processor count.

bound_checker	m_BoundChecker
	Bound checker.

os_allocated_stat	m_OSAllocStat
	OS-allocated memory statistics.

Detailed Description

template<typename... Options>
class cds::memory::michael::Heap< Options >

Michael's allocator.

This class provides base functionality for Michael's allocator. It does not provide the interface described by std::allocator, therefore, we name it as a heap, not as an allocator. The heap interface is closer to semantics of malloc / free system functions. The heap supports allocation of aligned and unaligned data.

The algorithm is based on simplified version of

[2004] M.Michael "Scalable Lock-free Dynamic Memory Allocation"

that, in turn, is concurrent version of well-known Hoard allocator developed by Emery Berger, see

[2002] Emery Berger "Memory Management for High-Performance Application", PhD thesis

This is powerful, scalable, fully customizable heap with fast-path without any locks that has been developed specifically for multi-threading. With opt:sys_topology you can set as many allocation arena ("processor heap") as you need. You can manually bound any your thread to any arena ("processor"). With opt::sizeclass_selector option you can manage allocation granularity. With opt::page_heap you can utilize any OS-provided features for page allocation like mmap, VirtualAlloc etc. The heap can gather internal statistics that helps you to tune your application. The opt::check_bounds feature can help you to find a memory buffer overflow.

Brief algorithm description from Michael's work:

Large blocks (greater than 64K) are allocated directly from the OS and freed directly to the OS. For smaller block sizes, the heap is composed of large superblocks (64 KB or 1MB size). Each superblock is divided into multiple equal-sized blocks. Superblocks are distributed among size classes based on their block sizes. Each size class contains multiple processor heaps proportional to the number of processors in the system. A processor heap contains at most one active superblock. An active superblock contains one or more blocks available for reservation that are guaranteed to be available to threads that reach them through the header of the processor heap. Each superblock is associated with a descriptor. Each allocated block contains a prefix (8 bytes) that points to the descriptor of its superblock. On the first call to malloc, the static structures for the size classes and processor heaps (about 16 KB for a 16 processor machine) are allocated and initialized in a lock-free manner.

Malloc starts by identifying the appropriate processor heap, based on the requested block size and the identity of the calling thread. Typically, the heap already has an active superblock with blocks available for reservation. The thread atomically reads a pointer to the descriptor of the active superblock and reserves a block. Next, the thread atomically pops a block from that superblock and updates its descriptor. A typical free pushes the freed block into the list of available blocks of its original superblock by atomically updating its descriptor.

Constraint: one superblock may contain up to 2048 block. This restriction imposes a restriction on the maximum superblock size.

Available Options:

opt::sys_topology - class that describes system topology needed for allocator. Default is cds::OS::topology (see cds::OS::Win32::topology for interface description)
opt::system_heap - option setter for an allocator for large blocks that is used for direct allocation from OS. Default is malloc_heap.
opt::aligned_heap - option setter for a heap used for internal aligned memory management. Default is aligned_malloc_heap
opt::page_heap - option setter for a heap used for page (superblock) allocation of 64K/1M size. Default is page_cached_allocator
opt::sizeclass_selector - option setter for a class used to select appropriate size-class for incoming allocation request. Default is default_sizeclass_selector
opt::free_list - option setter for a class to manage a list of free superblock descriptors Default is free_list_locked
opt::partial_list - option setter for a class to manage a list of partial filled superblocks Default is partial_list_locked
opt::procheap_stat - option setter for a class to gather internal statistics for memory allocation that is maintained by the heap. Default is procheap_empty_stat
opt::os_allocated_stat - option setter for a class to gather internal statistics for large block allocation. Term "large block" is specified by the size-class selector (see opt::sizeclass_selector) and it is 64K for default_sizeclass_selector. Any block that is large that 64K is allocated from OS directly. os_allocated_stat option is set a class to gather statistics for large blocks. Default is os_allocated_empty
opt::check_bounds - a bound checker. Default is no bound checker (cds::opt::none)

Usage:: The heap is the basic building block for your allocator or operator new implementation.

#include <cds/memory/michael/allocator.h>
// Heap with explicitly defined options:
cds::memory::michael::Heap<
    opt::aligned_heap< aligned_malloc_heap >,
    opt::page_heap< page_cached_allocator<16, malloc_heap> >
>   myHeap  ;
// Heap with default options:
cds::memory::michael::Heap<>    myDefHeap   ;

How to make std-like allocator

There are serious differencies of heap and std::allocator interface:

Heap is stateful, and std::allocator is stateless.
Heap has much more template parameters than std::allocator
Heap has low-level interface for memory allocating only unlike the allocator interface that can construct/destroy objects of any type T.

To convert heap interface into std::allocator -like interface you should:

Declare object of class cds::memory::michael::Heap specifying the necessary template parameters; this is usually static object
Create a class with std::allocator interface that uses the function of heap.
#include <cds/memory/michael/allocator.h>

template <class T>

class MichaelAllocator

{

typedef std::allocator<T> std_allocator ;

typedef cds::memory::michael::Heap<> michael_heap ;

// Michael heap static object

static michael_heap s_Heap ;

public:

// Declare typedefs from std::allocator

typedef typename std_allocator::const_pointer const_pointer ;

typedef typename std_allocator::pointer pointer ;

typedef typename std_allocator::const_reference const_reference ;

typedef typename std_allocator::reference reference ;

typedef typename std_allocator::difference_type difference_type ;

typedef typename std_allocator::size_type size_type ;

typedef typename std_allocator::value_type value_type ;

// Allocation function

pointer allocate( size_type _Count, const void* _Hint )

{

return reinterpret_cast<pointer>( s_Heap.alloc( sizeof(T) * _Count )) ;

}

// Deallocation function

void deallocate( pointer _Ptr, size_type _Count )

{

s_Heap.free( _Ptr ) ;

}

// Other std::allocator specific functions: address, construct, destroy, etc.

...

// Rebinding allocator to other type

template <class _Other>

struct rebind {

typedef MichaelAllocator<_Other> other;

};

};

// In .cpp file:

MichaelAllocator::michael_heap MichaelAllocator::s_Heap ;

Member Enumeration Documentation

template<typename... Options>

enum cds::memory::michael::Heap::superblock_state

Superblock states.

A superblock can be in one of four states: ACTIVE, FULL, PARTIAL, or EMPTY. A superblock is ACTIVE if it is the active superblock in a heap, or if a thread intends to try to install it as such. A superblock is FULL if all its blocks are either allocated or reserved. A superblock is PARTIAL if it is not ACTIVE and contains unreserved available blocks. A superblock is EMPTY if all its blocks are free and it is not ACTIVE.

Enumerator
SBSTATE_ACTIVE	superblock is active
SBSTATE_FULL	superblock is full
SBSTATE_PARTIAL	superblock is partially allocated
SBSTATE_EMPTY	superblock is empty and may be freed

Constructor & Destructor Documentation

template<typename... Options>

cds::memory::michael::Heap< Options >::~Heap ( )

inline

Heap destructor.

The destructor frees all memory allocated by the heap.

Member Function Documentation

template<typename... Options>

void* cds::memory::michael::Heap< Options >::alloc ( size_t nSize )

inline

Allocate memory block.

Parameters

nSize Size of memory block to allocate in bytes

template<typename... Options>

void* cds::memory::michael::Heap< Options >::alloc_aligned	(	size_t	nSize,
		size_t	nAlignment
	)

inline

Allocate aligned memory block.

Parameters

nSize	Size of memory block to allocate in bytes
nAlignment	Alignment

template<typename... Options>

void cds::memory::michael::Heap< Options >::free ( void * pMemory )

inline

Free previously allocated memory block.

Parameters

pMemory Pointer to memory block to free

template<typename... Options>

void cds::memory::michael::Heap< Options >::free_aligned ( void * pMemory )

inline

Free aligned memory block previously allocated by alloc_aligned.

Parameters

pMemory Pointer to memory block to free

template<typename... Options>

void* cds::memory::michael::Heap< Options >::realloc	(	void *	pMemory,
		size_t	nNewSize
	)

inline

Reallocate memory block.

If nNewSize is zero, then the block pointed to by pMemory is freed; the return value is NULL, and pMemory is left pointing at a freed block.

If there is not enough available memory to expand the block to the given size, the original block is left unchanged, and NULL is returned.

Aligned memory block cannot be realloc'ed: if pMemory has been allocated by alloc_aligned, then the return value is NULL and the original block is left unchanged.

Parameters

pMemory	Pointer to previously allocated memory block
nNewSize	New size of memory block, in bytes

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

cds/memory/michael/allocator.h

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Protected Attributes

Detailed Description

template<typename... Options> class cds::memory::michael::Heap< Options >

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename... Options>
class cds::memory::michael::Heap< Options >