Loading...
Searching...
No Matches
sphlockfreeheap.h File Reference

Shared Persistent Heap, lock free heap allocator for shared memory multi-thread/multi-core applications. More...

`#include "sastype.h"`

Go to the source code of this file.

## Typedefs

typedef void * | SPHLockFreeHeap_t
| Handle to an instance of SPH Lock Free Heap.

## Functions

__C__ SPHLockFreeHeap_t | SPHLockFreeHeapInit (void *heap_block, sas_type_t sasType, block_size_t heap_size, size_t unit_size)
| Initialize a shared storage block as a lock free heap.
__C__ SPHLockFreeHeap_t | SPHLockFreeHeapCreate (block_size_t heap_size, size_t unit_size)
| Create a lock free heap in a shared storage block.
__C__ int | SPHLockFreeHeapDestroy (SPHLockFreeHeap_t heap)
| Destroy a lock free heap and free the shared storage block.
__C__ block_size_t | SPHLockFreeHeapFreeSpace (SPHLockFreeHeap_t heap)
| Return the remaining allocatable free space within the specified lock free heap..
__C__ int | SPHLockFreeHeapEmpty (SPHLockFreeHeap_t heap)
| Return a boolean result indicating if the lock free heap is empty.
__C__ int | SPHLockFreeHeapFull (SPHLockFreeHeap_t heap)
| Return a boolean result indicating if the lock free heap is completely full.
__C__ void * | SPHLockFreeHeapAlloc (SPHLockFreeHeap_t heap, block_size_t alloc_size)
| Suballocate memory from a lock-free heap.
__C__ void * | SPHLockFreeHeapAlignAlloc (SPHLockFreeHeap_t heap, block_size_t alloc_size, block_size_t alignment)
| Suballocate memory from a lock free heap at a specified alignment.
__C__ void * | SPHLockFreeHeapNearAlloc (void *nearObj, long alloc_size)
| Suballocate memory from a lock free heap, close to a previous allocation.
__C__ int | SPHLockFreeHeapFree (SPHLockFreeHeap_t heap, void *free_block)
| Free memory allocated from a lock free heap for reuse.
__C__ int | SPHLockFreeHeapFreeNear (void *free_block)
| Free memory allocated from a lock free heap for reuse.
__C__ int | SPHLockFreeHeapFreeIn (SPHLockFreeHeap_t heap, void *free_block)
| Free memory allocated from a lock free heap for reuse.
__C__ int | SPHLockFreeHeapFreeChk (SPHLockFreeHeap_t heap, void *free_block, block_size_t alloc_size)
| Verify size of the allocation before freeing memory.
__C__ int | SPHLockFreeHeapFreeNearChk (void *free_block, block_size_t alloc_size)
| Verify size of the allocation before freeing memory.
__C__ SPHLockFreeHeap_t | SPHLockFreeHeapNearFind (void *nearObj)
| Find the containing SPHLockFreeHeap for a block of memory.

## Detailed Description

Shared Persistent Heap, lock free heap allocator for shared memory multi-thread/multi-core applications.

!

This implementation uses atomic bit vectors to control the allocation of memory in a fast and thread-safe manner. Each bit within the bit vector represents a fixed granule for allocation of memory. A string of contiguous bits represent larger allocations in multiples of the granule size.

Following the SPH design blocks used for LF heaps must be power of 2 in size and matching power of 2 alignment or better. This is required to support the near forms of alloc/free where the head header is implied from the contained address. The granules also must be power of 2 size which supports the aligned forms of allocation.

Allocations are tracked using bit vectors where each bit represents an power of 2 unit with matching alignment. Each heap is configured for a specific allocation unit size and different heaps can can be configured with varying unit sizes as required. For each unit size the maximum individual allocation size is limited the maximum atomic update granual of the underlying processor. For most processors this is defined by the largest compare-and-swap or equivalent atomic operation. However for biarch systems we may choose that smaller granual of the supported modes for consistency, normally 32-bits.

So any specific heap instance will support a maximum allocation request of 32 * unit-size. The Minimun unit size is 16-bytes so a heap configured with this size can support allocations of 16-byte multiples up to 512 bytes. If an application needs a larger allocation size a different heap needs to be configured with an appropriate unit size. For example if allocation up to 4K are need then a unit size of at least 128 bytes is needed. Of course this unit-size will also be the minimum allocation size and alignment for that heap.

We assume that this simple lock free heap will be used in the implementation of a compound lock free heap. Such a compound heap would automatically allocate multiple simple heaps with unit-sizes selected to support the the dynamic requests of the application.

## Typedef Documentation

## SPHLockFreeHeap_t

typedef void* SPHLockFreeHeap_t

Handle to an instance of SPH Lock Free Heap.

The type is SAS_RUNTIME_LOCKFREEHEAP

## Function Documentation

## SPHLockFreeHeapAlignAlloc()

__C__ void * SPHLockFreeHeapAlignAlloc | ( | SPHLockFreeHeap_t | heap,
|  | block_size_t | alloc_size,
|  | block_size_t | alignment )

extern

Suballocate memory from a lock free heap at a specified alignment.

Request alloc_size bytes of memory from the heap. The allocation size will be rounded up to the next intergral unit_size. The minimal alignment of the allocation will be specified by alignment. Returns a pointer to the allocated memory or NULL if no contiguous space of the requested size or alignment is available.

Parameters

  heap | to allocated from.
  alloc_size | size in bytes of the allocation request.
  alignment | required power of 2 alignment.

Returns
  pointer to the successfully allocate storage. NULL otherwise.

## SPHLockFreeHeapAlloc()

__C__ void * SPHLockFreeHeapAlloc | ( | SPHLockFreeHeap_t | heap,
|  | block_size_t | alloc_size )

extern

Suballocate memory from a lock-free heap.

Request alloc_size bytes of memory from the heap. The allocation size will be rounded up to the next intergral unit_size. The minimal alignment of the allocation will be the unit_size. Returns a pointer to the allocated memory or NULL if no contiguous space of the requested size is available.

Parameters

  heap | to allocated from.
  alloc_size | size in bytes of the allocation request.

Returns
  pointer to the successfully allocate storage. NULL otherwise.

## SPHLockFreeHeapCreate()

__C__ SPHLockFreeHeap_t SPHLockFreeHeapCreate | ( | block_size_t | heap_size,
|  | size_t | unit_size )

extern

Create a lock free heap in a shared storage block.

Allocate a SAS block and initialize the control blocks as a lock free heap. The block size must be power of two in size. The unit_size is the allocation granule in bytes and must be a power of two size greater then 1.

Parameters

  heap_size | power of 2 size of the heap to allocated and initialized.
  unit_size | power of 2 of the allocation granule.

Returns
  a handle of the newly allocated SPHLockFreeHeap_t. Or NULL for the failure case.

## SPHLockFreeHeapDestroy()

__C__ int SPHLockFreeHeapDestroy | ( | SPHLockFreeHeap_t | heap | ) |

extern

Destroy a lock free heap and free the shared storage block.

The sas_type_t must be of type SAS_LOCKFREEHEAP_TYPE.

Parameters

  heap | to destroyed and the storage freed.

Returns
  a 0 value indicated success, otherwise failure.

## SPHLockFreeHeapEmpty()

__C__ int SPHLockFreeHeapEmpty | ( | SPHLockFreeHeap_t | heap | ) |

extern

Return a boolean result indicating if the lock free heap is empty.

Parameters

  heap | to checked for full/empty.

Returns
  true if all available space is free.

## SPHLockFreeHeapFree()

__C__ int SPHLockFreeHeapFree | ( | SPHLockFreeHeap_t | heap,
|  | void * | free_block )

extern

Free memory allocated from a lock free heap for reuse.

The memory at *free_block is freed for reuse up to the length of the original allocation. Returns zero if the free operation is successful. Otherwise a non-zero value for an error condition.

Parameters

  heap | containing the allocation to be freed.
  free_block | pointer to the previously allocated storage to be freed.

Returns
  0 indicates success, otherwise the free operation failed.

## SPHLockFreeHeapFreeChk()

__C__ int SPHLockFreeHeapFreeChk | ( | SPHLockFreeHeap_t | heap,
|  | void * | free_block,
|  | block_size_t | alloc_size )

extern

Verify size of the allocation before freeing memory.

The memory at *free_block is freed for reuse up to the length of the original allocation. The allocation size is checked against the original allocation. Returns zero if the free operation is successful. Otherwise a non-zero value for an error condition.

Parameters

  heap | containing the allocation to be freed.
  free_block | pointer to the previously allocated storage to be freed.
  alloc_size | size in bytes of the original allocation.

Returns
  0 indicates success, otherwise the free operation failed.

## SPHLockFreeHeapFreeIn()

__C__ int SPHLockFreeHeapFreeIn | ( | SPHLockFreeHeap_t | heap,
|  | void * | free_block )

extern

Free memory allocated from a lock free heap for reuse.

The memory at *free_block is freed for reuse up to the length of the original allocation. Returns zero if the free operation is successful. Otherwise a non-zero value for an error condition.

Parameters

  heap | containing the allocation to be freed.
  free_block | pointer to the previously allocated storage to be freed.

Returns
  0 indicates success, otherwise the free operation failed.

## SPHLockFreeHeapFreeNear()

__C__ int SPHLockFreeHeapFreeNear | ( | void * | free_block | ) |

extern

Free memory allocated from a lock free heap for reuse.

The containing lock free heap is found, if possible, then the memory at *free_block is freed for reuse up to the length of the original allocation. Returns zero if the free operation is successful. Otherwise a non-zero value for an error condition.

Parameters

  free_block | pointer to the previously allocated storage to be freed.

Returns
  0 indicates success, otherwise the free operation failed.

## SPHLockFreeHeapFreeNearChk()

__C__ int SPHLockFreeHeapFreeNearChk | ( | void * | free_block,
|  | block_size_t | alloc_size )

extern

Verify size of the allocation before freeing memory.

The containing lock free heap is found, if posible, then the memory at *free_block is freed for reuse up to the length of the original allocation. The allocation size is checked against the original allocation. Returns zero if the free operation is successful. Otherwise a non-zero value for an error condition.

Parameters

  free_block | pointer to the previously allocated storage to be freed.
  alloc_size | size in bytes of the original allocation.

Returns
  0 indicates success, otherwise the free operation failed.

## SPHLockFreeHeapFreeSpace()

__C__ block_size_t SPHLockFreeHeapFreeSpace | ( | SPHLockFreeHeap_t | heap | ) |

extern

Return the remaining allocatable free space within the specified lock free heap..

Parameters

  heap | to checked for size.

Returns
  the remaining free space for this heap in bytes.

## SPHLockFreeHeapFull()

__C__ int SPHLockFreeHeapFull | ( | SPHLockFreeHeap_t | heap | ) |

extern

Return a boolean result indicating if the lock free heap is completely full.

Parameters

  heap | to checked for full/empty.

Returns
  true if all available space is already allocated.

## SPHLockFreeHeapInit()

__C__ SPHLockFreeHeap_t SPHLockFreeHeapInit | ( | void * | heap_block,
|  | sas_type_t | sasType,
|  | block_size_t | heap_size,
|  | size_t | unit_size )

extern

Initialize a shared storage block as a lock free heap.

Initialize the control blocks within the specified storage block as a lock free heap. The storage block must be power of two in size and have the same power of two (or better) alignment. The type should be SAS_LOCKFREEHEAP_TYPE. The unit_size is the allocation granule in bytes and must be a power of two size greater then 1.

Parameters

  heap_block | a block of allocated SAS storage matching the heap_size.
  sasType | a SAS type code for internal consistency checking.
  heap_size | power of two size of the heap to be initialized.
  unit_size | power of 2 size of the allocation granule.

Returns
  at handle to the initialized SPHLockFreeHeap_t

## SPHLockFreeHeapNearAlloc()

__C__ void * SPHLockFreeHeapNearAlloc | ( | void * | nearObj,
|  | long | alloc_size )

extern

Suballocate memory from a lock free heap, close to a previous allocation.

Request alloc_size bytes of memory from the heap. The allocation size will be rounded up to the next integral unit_size. The minimal alignment of the allocation will be the unit_size. Attempt to allocate from the SPHLockFreeHeap which contains the near object. Returns a pointer to the allocated memory or NULL if no contiguous space of the requested size is available in the "near" SPHLockFreeHeap.

Parameters

  nearObj | address of another lock free heap allocation.
  alloc_size | size in bytes of the allocation request.

Returns
  pointer to the successfully allocate storage. NULL otherwise.

## SPHLockFreeHeapNearFind()

__C__ SPHLockFreeHeap_t SPHLockFreeHeapNearFind | ( | void * | nearObj | ) |

extern

Find the containing SPHLockFreeHeap for a block of memory.

The containing lock free heap is found, if posible, then return LF heap address or NULL. From the near object pointer round down using increasing powers of 2 until a valid block header is found. If the block header is marked as a LockFreeHeap, return the block address. Otherwise return NULL.

Parameters

  nearObj | pointer to any current or previous allocation within the target heap.

Returns
  pointer to the containing SPHLockFreeHeap_t, or NULL if not found.