Shared Address Space Compound Heap. More...

#include "sassimpleheap.h"

Typedefs
typedef void *	SASCompoundHeap_t
	Handle to SAS Compound Heap. The type is SAS_RUNTIME_COMPOUNDHEAP.

Functions
__C__ SASCompoundHeap_t	SASCompoundHeapInit (void *heap_block, block_size_t heap_size, block_size_t page_size, int expanding)
	Initialize a shared storage as a compound heap. More...

__C__ SASCompoundHeap_t	SASCompoundHeapExpandCreate (SASCompoundHeap_t heap)
	Create an expanding SAS Compound Heap based on existing heap. More...

__C__ SASCompoundHeap_t	SASCompoundHeapCreate (block_size_t heap_size)
	Create a new SAS Compound Heap with heap_size size. More...

__C__ SASCompoundHeap_t	SASCompoundHeapCreatePageSize (block_size_t heap_size, block_size_t page_size)
	Create a new SAS Compound Heap with heap_size size and page_size page size. More...

__C__ SASCompoundHeap_t	SASCompoundFixedHeapCreate (block_size_t heap_size)
	Create a new non expanding SAS Compound heap with heap_size. More...

__C__ void	SASCompoundHeapDestroy (SASCompoundHeap_t heap)
	Destroy the SAS Compound Heap heap. More...

__C__ void	SASCompoundHeapSetLoadFactor (SASCompoundHeap_t *heap, int load)
	Set the SAS Compound Heap heap load factor to load. More...

__C__ int	SASCompoundHeapGetLoadFactor (SASCompoundHeap_t *heap)
	Return the load factor from SAS Compound Heap heap. More...

__C__ block_size_t	SASCompoundHeapAllocSize (SASCompoundHeap_t heap)
	Return the page size from SAS Compound Heap heap. More...

__C__ block_size_t	SASCompoundHeapFreeSpace (SASCompoundHeap_t heap)
	Return the total available free space on SAS Compound heap heap. More...

__C__ block_size_t	SASCompoundHeapAllocSpace (SASCompoundHeap_t heap)
	Return the total block space allocated to this SAS Compound heap heap. More...

__C__ block_size_t	SASCompoundHeapWriteAll (SASCompoundHeap_t heap, int asyncBool)
	Write down the SAS Compound Heap to persistent storage. More...

__C__ block_size_t	SASCompoundHeapPurgeAll (SASCompoundHeap_t heap, int asyncBool)
	Write down the SAS Compound Heap to persistent storage and inform the kernel that those pages can be removed from real memory. More...

__C__ block_size_t	SASCompoundHeapReleaseAll (SASCompoundHeap_t heap)
	Inform the kernel that the SAS Compound Heap memory segments can be removed from real memory. More...

__C__ block_size_t	SASCompoundHeapBringAll (SASCompoundHeap_t heap)
	Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon. More...

__C__ block_size_t	SASCompoundHeapSeqAccessAll (SASCompoundHeap_t heap)
	Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon and will be accessed in sequential order. More...

__C__ block_size_t	SASCompoundHeapRandomAccessAll (SASCompoundHeap_t heap)
	Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon and will be accessed in random order. More...

__C__ SASSimpleHeap_t	SASCompoundHeapAlloc (SASCompoundHeap_t heap)
	Sub-Allocate a new SAS Simple Heap from a SAS Compound Heaps internal space. More...

__C__ void	SASCompoundHeapFree (SASCompoundHeap_t heap, SASSimpleHeap_t free_block)
	Free the allocated SAS Simple Heap block in the SAS Compound Heap heap. More...

__C__ SASSimpleHeap_t	SASCompoundHeapNearAlloc (void *nearObj)
	Allocate a new SAS Simple Heap from SAS Compound Heap nearObj. More...

__C__ void	SASCompoundHeapNearDealloc (void *memAddr)
	Free the allocated SAS Simple Heap based on a contained memAddr. More...

__C__ void	SASCompoundHeapDestroyNoLock (SASCompoundHeap_t heap)
	Destroy the SAS Compound Heap heap. More...

__C__ block_size_t	SASCompoundHeapFreeSpaceNoLock (SASCompoundHeap_t heap)
	Return the total available free space on SAS Compound heap heap. More...

__C__ SASSimpleHeap_t	SASCompoundHeapAllocNoLock (SASCompoundHeap_t heap)
	Sub-Allocate a new SAS Simple Heap from a SAS Compound Heaps internal space. More...

__C__ SASSimpleHeap_t	SASCompoundHeapNearAllocNoLock (void *nearObj)
	Allocate a new SAS Simple Heap from SAS Compound Heap nearObj. More...

__C__ void	SASCompoundHeapNearDeallocNoLock (void *memAddr)
	Free the allocated SAS Simple Heap memAddr from associated SAS Compound Heap. More...

__C__ void	SASCompoundHeapFreeNoLock (SASCompoundHeap_t heap, SASSimpleHeap_t free_block)
	Free the allocated SAS Simple Heap free_block from SAS Compound Heap heap. More...

Detailed Description

Shared Address Space Compound Heap.

Allocate a SAS block to be used as a Heap of SASSimpleHeap_t heaps. This is a useful constuct for managing complex data structures while maintaining some storage (cache, page, block segment) affinity. The implementation is based on allocation of sub-heaps and allocating structures "near" an already allocated structure (New Near).

With a Compound Heap it is easy to start a new sub group by allocating a new SASSimpleHeap_t from the containing SASCompoundHeap_t. The application allocates the "top" or "root" structure directly from this Simple Heap. Subsequent allocations that need good locality to the "root" can use the SASSimpleHeapNearAlloc() API. This API allocates storage from the Simple Heap nearest that provided (near object) address.

The allocated Simple Heaps are always a power of two size allocated on a matching power of two boundary. The runtime can always find the containing Simple Heap based on the address of any contained structure. The runtime will allocate from the immediate containing Simple heap if free space is available there.

The runtime can also find the containing Compound Heap for any Simple Heap allocated from it. This allows a number of extended near allocation schemes. For example allocations can be from adjacent Simple Heaps within the same Compound Heap. Or allocations can be from a spill area associated with the containing Compound Heap header.

Todo:: A future improvement would specify a Near Window that would restrict near allocations to be from a power of two sub-block of the containing Compound Heap. This could be used with large pages to restrict spill allocations to be from the same large page. For example if the Simple Heaps where allocated as 4K blocks but the physical Page size was 64K or 16M.

SAS Compound Heaps can be "expanding" or "fixed". Fixed Compound Heaps will fail that allocation once internal space is exhausted. Expanding Compound Heaps will respond to an allocation failure by allocating a block the size of the original compound heap, initialize it as a compound heap, and chain it the original. If expansion is successful the requested simple heap is allocated from the new space. Finally the storage associated with entire collection of related data structures allocated from a Compound Heap can be freed for reuse (destroyed) with one call.

A Compound Heap and the contained complex data structures can be arbitrarily large (up the the limits of the Region size or available disk space). Since SAS blocks are backed by memory mapped files, contained data structures, can be persistent and larger then available system memory.

Naturally pages of SAS storage (including Compound Heaps) will be paged into and out of system memory by the OS as need. The natural storage locality of a properly used Compound Heap will help to minimize paging. However is sometimes useful to advise the OS of the programs usage pattern. For example which storage (blocks/pages):

will be needed in the near future,
should be written to disk for checking-pointing
should be written to disk and removed from real storage
Whether we expect sequential or random access to virtual storage and backing file.

The SAS Compound Heap supports these operations (above) as described in sasmsync.h.

To create fixed compound heap use the function SASCompoundFixedHeapCreate or create the initial allocation of an expanding heap with SASCompoundHeapCreate or SASCompoundHeapCreatePageSize. The Default allocation is 4K which can be overridden with SASCompoundHeapCreatePageSize. The function SASCompoundHeapExpandCreate is used to expand the an expanding Compound Heap. The function SASCompoundHeapDestroy destroys the entire Compound Heap including any expansion blocks .

A new Simple Heap can be sub-allocated from a Compound Heap using SASCompoundHeapAlloc or SASCompoundHeapNearAlloc and freed by using the functions SASCompoundHeapFree and SASCompoundHeapNearDealloc respectively.

Note: the implementations of sasstringbtree.h and sasindex.h are derived from the Compound Heap. The internal BTree nodes are derived from the sassimpleheap.h implementation. This improves locality of reference as each node (key list and key data) is contained within a single page (unless the node fills with long keys and some data spills).

Todo:: A lock Free Compound Heap to compliment the SPH Lock Free Heap implementation of sphlockfreeheap.h would be a useful addition to the SAS/SPH runtime.

Function Documentation

__C__ SASCompoundHeap_t SASCompoundFixedHeapCreate ( block_size_t heap_size )

Create a new non expanding SAS Compound heap with heap_size.

Similar to SASCompoundHeapCreate but without the option to expand when load factor allows it.

Parameters

heap_size Size of the Compound Heap to create.

Returns: A handle to created SASCompoundHeap_t or 0 if the creating fails.

__C__ SASSimpleHeap_t SASCompoundHeapAlloc ( SASCompoundHeap_t heap )

Sub-Allocate a new SAS Simple Heap from a SAS Compound Heaps internal space.

The sas_type_t of heap must be SAS_RUNTIME_COMPOUNDHEAP. The allocated block is initialized as a SAS Simple Heap. The function holds a write lock on the Compound Heap during this operation.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: A newly created SASSimpleHeap_t or 0 if an error occurs.

__C__ SASSimpleHeap_t SASCompoundHeapAllocNoLock ( SASCompoundHeap_t heap )

Sub-Allocate a new SAS Simple Heap from a SAS Compound Heaps internal space.

Similar to SASCompoundHeapAlloc but do not hold the write lock on the Compound Heap.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: A newly created SASSimpleHeap_t or 0 if an error occurs.

__C__ block_size_t SASCompoundHeapAllocSize ( SASCompoundHeap_t heap )

Return the page size from SAS Compound Heap heap.

The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: The page size value in bytes. Used to allocate Simple Heaps.

__C__ block_size_t SASCompoundHeapAllocSpace ( SASCompoundHeap_t heap )

Return the total block space allocated to this SAS Compound heap heap.

The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function holds a read lock while calculating the total block space, including expansion blocks.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: The total block space in bytes.

__C__ block_size_t SASCompoundHeapBringAll ( SASCompoundHeap_t heap )

Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon.

The function basically calls sasMsyncBring from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function hold a read lock over the heap's memory segments.

Parameters

heap	Handle the the SASCompoundHeap_t.

__C__ SASCompoundHeap_t SASCompoundHeapCreate ( block_size_t heap_size )

Create a new SAS Compound Heap with heap_size size.

Create and initialize a Compound Heap. The storate block must be power of two in size and SAS type returned is SAS_RUNTIME_COMPOUNDHEAP. The internal page size used is the default one defined in sasalloc.h (4096).

Parameters

heap_size Size of the Compound Heap to create.

Returns: A handle to created SASCompoundHeap_t or 0 if creation fails.

__C__ SASCompoundHeap_t SASCompoundHeapCreatePageSize	(	block_size_t	heap_size,
		block_size_t	page_size
	)

Create a new SAS Compound Heap with heap_size size and page_size page size.

Similar to SASCompoundHeapCreate but with additional option to set the internal page size.

Parameters

heap_size	Size of the Compound Heap to create.
page_size	Size of the internal page.

Returns: A handle to created SASCompoundHeap_t or 0 if creation fails.

__C__ void SASCompoundHeapDestroy ( SASCompoundHeap_t heap )

Destroy the SAS Compound Heap heap.

The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. Destroy holds an exclusive write lock while clearing the control blocks and freeing the SAS block.

Parameters

heap	Handle of the SASCompoundHeap_t to be destroyed.

__C__ void SASCompoundHeapDestroyNoLock ( SASCompoundHeap_t heap )

Destroy the SAS Compound Heap heap.

Similar to SASCompoundHeapDestroy but do not hold the write lock on the memory address.

Parameters

heap	Handle of the SASCompoundHeap_t.

__C__ SASCompoundHeap_t SASCompoundHeapExpandCreate ( SASCompoundHeap_t heap )

Create an expanding SAS Compound Heap based on existing heap.

Create an expanding SAS Compound Heap and add the heap on its internal list. Intended for internal runtime use but can be used to force expansion of the specified Compound Heap.

Parameters

heap	The SAS Compound Heap to add on expanding heap.

Returns: A new SASCompoundHeap handle or 0 if the new heap creation fails.

__C__ void SASCompoundHeapFree	(	SASCompoundHeap_t	heap,
		SASSimpleHeap_t	free_block
	)

Free the allocated SAS Simple Heap block in the SAS Compound Heap heap.

The sas_type_t of heap must be SAS_RUNTIME_COMPOUNDHEAP and the type of free_block must be SAS_RUNTIME_SIMPLEHEAP.

Parameters

heap	Handle to the SASCompoundHeap_t.
free_block	The created SASSimpleHeap_t created from heap.

__C__ void SASCompoundHeapFreeNoLock	(	SASCompoundHeap_t	heap,
		SASSimpleHeap_t	free_block
	)

Free the allocated SAS Simple Heap free_block from SAS Compound Heap heap.

Similar to SASCompoundHeapFree but do not hold the write lock.

Parameters

heap	Handle to the SASCompoundHeap_t.
free_block	The created SASSimpleHeap_t created from heap.

__C__ block_size_t SASCompoundHeapFreeSpace ( SASCompoundHeap_t heap )

Return the total available free space on SAS Compound heap heap.

The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function holds a write lock while calculating the total free space from heap.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: The total available free space in bytes.

__C__ block_size_t SASCompoundHeapFreeSpaceNoLock ( SASCompoundHeap_t heap )

Return the total available free space on SAS Compound heap heap.

Similar to SASCompoundHeapFreeSpace but do not hold the write lock on the Compound Heap.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: The total available free space in bytes.

__C__ int SASCompoundHeapGetLoadFactor ( SASCompoundHeap_t * heap )

Return the load factor from SAS Compound Heap heap.

The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP.

Parameters

heap	Handle to the SASCompoundHeap_t.

Returns: The load factor from heap or -1 if and error occurs.

__C__ SASCompoundHeap_t SASCompoundHeapInit	(	void *	heap_block,
		block_size_t	heap_size,
		block_size_t	page_size,
		int	expanding
	)

Initialize a shared storage as a compound heap.

Initialize the control blocks within the specified storage block as a Compound Heap. Both heap_size and page_size must be power of two in size and have the same power of two (or better) alignment. The SAS type created is SAS_RUNTIME_COMPOUNDHEAP.

Parameters

heap_block	Block of allocated SAS storage.
heap_size	Size of the simple heap within the block.
page_size	Size of each Simple Heap to be created.
expanding	Set the compound heap to expand and associate a load factor to used to determine when to expand.

Returns: A handle to the initialized SASSimpleHeap_t or 0 if an error occurs.

__C__ SASSimpleHeap_t SASCompoundHeapNearAlloc ( void * nearObj )

Allocate a new SAS Simple Heap from SAS Compound Heap nearObj.

The address nearObj is used to find the associated Compound Heap object. The sas_type_t of the heap must be SAS_RUNTIME_COMPOUNDHEAP. The allocated SAS Simple Heap is already initialized.

Parameters

nearObj Memory address of SASCompoundHeap_t.

Returns: A newly created SASSimpleHeap_t or 0 if an error occurs.

__C__ SASSimpleHeap_t SASCompoundHeapNearAllocNoLock ( void * nearObj )

Allocate a new SAS Simple Heap from SAS Compound Heap nearObj.

Similar to SASCompoundHeapNearAlloc but do not hold any locks.

Parameters

nearObj Memory address of SASCompoundHeap_t.

Returns: A newly created SASSimpleHeap_t or 0 if an error occurs.

__C__ void SASCompoundHeapNearDealloc ( void * memAddr )

Free the allocated SAS Simple Heap based on a contained memAddr.

The address memAddr is used to find the associated SAS Simple Heap and the containing SAS Compound Heap. If both objects can be found, the SAS Simple Heap is freed in the SAS Compound Heap.

Parameters

memAddr Memory Address of a SASSimpleHeap_t associated with a SASCompoundHeap_t.

__C__ void SASCompoundHeapNearDeallocNoLock ( void * memAddr )

Free the allocated SAS Simple Heap memAddr from associated SAS Compound Heap.

Similar to SASCompoundHeapNearDealloc but do not hold any locks.

Parameters

memAddr Memory Address of a SASSimpleHeap_t associated with a SASCompoundHeap_t.

__C__ block_size_t SASCompoundHeapPurgeAll	(	SASCompoundHeap_t	heap,
		int	asyncBool
	)

Write down the SAS Compound Heap to persistent storage and inform the kernel that those pages can be removed from real memory.

The function basically calls sasMsyncPurge from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function hold a read lock over the heap's memory segments.

Parameters

heap	Handle the the SASCompoundHeap_t.
asyncBool	Flag for asynchronous action if true.

__C__ block_size_t SASCompoundHeapRandomAccessAll ( SASCompoundHeap_t heap )

Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon and will be accessed in random order.

The function basically calls sasMsyncRandom from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function holds a read lock over the heap memory segments.

Parameters

heap	Handle to the SASCompoundHeap_t.

__C__ block_size_t SASCompoundHeapReleaseAll ( SASCompoundHeap_t heap )

Inform the kernel that the SAS Compound Heap memory segments can be removed from real memory.

The function basically calls sasMsyncRelease from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function hold a read lock over the heap's memory segments.

Parameters

heap	Handle the the SASCompoundHeap_t.

__C__ block_size_t SASCompoundHeapSeqAccessAll ( SASCompoundHeap_t heap )

Inform the kernel that the SAS Compound Heap memory segments pages will be needed soon and will be accessed in sequential order.

The function basically calls sasMsyncSequential from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function hold a read lock over the heap's memory segments.

Parameters

heap	Handle the the SASCompoundHeap_t.

__C__ void SASCompoundHeapSetLoadFactor	(	SASCompoundHeap_t *	heap,
		int	load
	)

Set the SAS Compound Heap heap load factor to load.

Parameters

heap	Handle to the SASCompoundHeap_t to be adjusted.
load	Load factor to set.

__C__ block_size_t SASCompoundHeapWriteAll	(	SASCompoundHeap_t	heap,
		int	asyncBool
	)

Write down the SAS Compound Heap to persistent storage.

The function basically call sasMsyncWrite from sasmsync.h on each internal SAS Simple Heap. The sas_type_t must be SAS_RUNTIME_COMPOUNDHEAP. The function hold a read lock over the heap's memory segments.

Parameters

heap	Handle the the SASCompoundHeap_t.
asyncBool	Flag for asynchronous action if true.

Typedefs

Functions

Detailed Description

Function Documentation