sascompoundheap.h File Reference

Shared Address Space Compound Heap. More...

`#include "sassimpleheap.h"`

Go to the source code of this file.

## 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

## SASCompoundFixedHeapCreate()

__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.

## SASCompoundHeapAlloc()

__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.

## SASCompoundHeapAllocNoLock()

__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.

## SASCompoundHeapAllocSize()

__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.

## SASCompoundHeapAllocSpace()

__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.

## SASCompoundHeapBringAll()

__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.

## SASCompoundHeapCreate()

__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.

## SASCompoundHeapCreatePageSize()

__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.

## SASCompoundHeapDestroy()

__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.

## SASCompoundHeapDestroyNoLock()

__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.

## SASCompoundHeapExpandCreate()

__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.

## SASCompoundHeapFree()

__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.

## SASCompoundHeapFreeNoLock()

__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.

## SASCompoundHeapFreeSpace()

__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.

## SASCompoundHeapFreeSpaceNoLock()

__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.

## SASCompoundHeapGetLoadFactor()

__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.

## SASCompoundHeapInit()

__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.

## SASCompoundHeapNearAlloc()

__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.

## SASCompoundHeapNearAllocNoLock()

__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.

## SASCompoundHeapNearDealloc()

__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.

## SASCompoundHeapNearDeallocNoLock()

__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.

## SASCompoundHeapPurgeAll()

__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.

## SASCompoundHeapRandomAccessAll()

__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.

## SASCompoundHeapReleaseAll()

__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.

## SASCompoundHeapSeqAccessAll()

__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.

## SASCompoundHeapSetLoadFactor()

__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.

## SASCompoundHeapWriteAll()

__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.