/* heap.h * * This include file contains the information pertaining to the Heap * Handler. A heap is a doubly linked list of variable size * blocks which are allocated using the first fit method. Garbage * collection is performed each time a block is returned to the heap by * coalescing neighbor blocks. Control information for both allocated * and unallocated blocks is contained in the heap space. A heap header * contains control information for the heap. * * COPYRIGHT (c) 1989, 1990, 1991, 1992, 1993, 1994. * On-Line Applications Research Corporation (OAR). * All rights assigned to U.S. Government, 1994. * * This material may be reproduced by or for the U.S. Government pursuant * to the copyright license under the clause at DFARS 252.227-7013. This * notice must appear in all copies of this file and its derivatives. * * $Id$ */ #ifndef __RTEMS_HEAP_h #define __RTEMS_HEAP_h #ifdef __cplusplus extern "C" { #endif /* * Status codes for heap_extend */ typedef enum { HEAP_EXTEND_SUCCESSFUL, HEAP_EXTEND_ERROR, HEAP_EXTEND_NOT_IMPLEMENTED } Heap_Extend_status; /* * Constants used in the size/used field of each heap block to * indicate when a block is free or in use. */ #define HEAP_BLOCK_USED 1 /* indicates block is in use */ #define HEAP_BLOCK_FREE 0 /* indicates block is free */ /* * The size/used field value for the dummy front and back flags. */ #define HEAP_DUMMY_FLAG (0 + HEAP_BLOCK_USED) /* * The following constants reflect various requirements of the * heap data structures which impact the management of a heap. * * NOTE: Because free block overhead is greater than used block * overhead AND a portion of the allocated space is from * the extra free block overhead, the absolute lower bound * of the minimum fragment size is equal to the size of * the free block overhead. */ #define HEAP_OVERHEAD \ (sizeof( unsigned32 ) * 2) /* size dummy first and last blocks */ #define HEAP_BLOCK_USED_OVERHEAD \ (sizeof( void * ) * 2) /* num bytes overhead in used block */ #define HEAP_MINIMUM_SIZE \ (HEAP_OVERHEAD + sizeof (Heap_Block)) /* min number of bytes the user may */ /* specify for the heap size */ /* * The following defines the data structure used to manage * individual blocks in a heap. When the block is allocated, the * next and previous fields are not used by the Heap Handler * and thus the address returned for the block starts at * the address of the next field. * * NOTE: The next and previous pointers are only valid when the * block is free. Caution must be exercised to insure that * allocated blocks are large enough to contain them and * that they are not accidentally overwritten when the * block is actually allocated. */ typedef struct Heap_Block_struct Heap_Block; struct Heap_Block_struct { unsigned32 back_flag; /* size and status of prev block */ unsigned32 front_flag; /* size and status of block */ Heap_Block *next; /* pointer to next block */ Heap_Block *previous; /* pointer to previous block */ }; /* * The following defines the control block used to manage each heap. * * NOTE: * * This structure is layed out such that it can be used a a dummy * first and last block on the free block chain. The extra padding * insures the dummy last block is the correct size. * * The first Heap_Block starts at first while the second starts at * final. This is effectively the same trick as is used in the Chain * Handler. */ typedef struct { Heap_Block *start; /* first valid block address in heap */ Heap_Block *final; /* last valid block address in heap */ Heap_Block *first; /* pointer to first block in heap */ Heap_Block *permanent_null; /* always NULL pointer */ Heap_Block *last; /* pointer to last block in heap */ unsigned32 page_size; /* allocation unit */ unsigned32 reserved; } Heap_Control; /* * _Heap_Initialize * * DESCRIPTION: * * This routine initializes the_heap record to manage the * contiguous heap of size bytes which starts at starting_address. * Blocks of memory are allocated from the heap in multiples of * page_size byte units. */ unsigned32 _Heap_Initialize( Heap_Control *the_heap, void *starting_address, unsigned32 size, unsigned32 page_size ); /* * _Heap_Extend * * DESCRIPTION: * * This routine grows the_heap memory area using the size bytes which * begin at starting_address. */ Heap_Extend_status _Heap_Extend( Heap_Control *the_heap, void *starting_address, unsigned32 size, unsigned32 *amount_extended ); /* * _Heap_Allocate * * DESCRIPTION: * * DESCRIPTION: * * This function attempts to allocate a block of size bytes from * the_heap. If insufficient memory is free in the_heap to allocate * a block of the requested size, then NULL is returned. */ void *_Heap_Allocate( Heap_Control *the_heap, unsigned32 size ); /* * _Heap_Size_of_user_area * * DESCRIPTION: * * This kernel routine sets size to the size of the given heap block. * It returns TRUE if the starting_address is in the heap, and FALSE * otherwise. */ boolean _Heap_Size_of_user_area( Heap_Control *the_heap, void *starting_address, unsigned32 *size ); /* * _Heap_Free * * DESCRIPTION: * * This routine returns the block of memory which begins * at starting_address to the_heap. Any coalescing which is * possible with the freeing of this routine is performed. */ boolean _Heap_Free( Heap_Control *the_heap, void *start_address ); /* * _Heap_Walk * * DESCRIPTION: * * This routine walks the heap to verify its integrity. */ void _Heap_Walk( Heap_Control *the_heap, int source, boolean do_dump ); /* * _Heap_Head * * DESCRIPTION: * * This function returns the head of the specified heap. */ STATIC INLINE Heap_Block *_Heap_Head ( Heap_Control *the_heap ); /* * _Heap_Tail * * DESCRIPTION: * * This function returns the tail of the specified heap. */ STATIC INLINE Heap_Block *_Heap_Tail ( Heap_Control *the_heap ); /* * _Heap_Previous_block * * DESCRIPTION: * * This function returns the address of the block which physically * precedes the_block in memory. */ STATIC INLINE Heap_Block *_Heap_Previous_block ( Heap_Block *the_block ); /* * _Heap_Next_block * * DESCRIPTION: * * This function returns the address of the block which physically * follows the_block in memory. */ STATIC INLINE Heap_Block *_Heap_Next_block ( Heap_Block *the_block ); /* * _Heap_Block_at * * DESCRIPTION: * * This function calculates and returns a block's location (address) * in the heap based upad a base address and an offset. */ STATIC INLINE Heap_Block *_Heap_Block_at( void *base, unsigned32 offset ); /* * _Heap_Is_previous_block_free * * DESCRIPTION: * * This function returns TRUE if the previous block of the_block * is free, and FALSE otherwise. */ STATIC INLINE boolean _Heap_Is_previous_block_free ( Heap_Block *the_block ); /* * _Heap_Is_block_free * * DESCRIPTION: * * This function returns TRUE if the block is free, and FALSE otherwise. */ STATIC INLINE boolean _Heap_Is_block_free ( Heap_Block *the_block ); /* * _Heap_Is_block_used * * DESCRIPTION: * * This function returns TRUE if the block is currently allocated, * and FALSE otherwise. */ STATIC INLINE boolean _Heap_Is_block_used ( Heap_Block *the_block ); /* * _Heap_Block_size * * DESCRIPTION: * * This function returns the size of the_block in bytes. */ STATIC INLINE unsigned32 _Heap_Block_size ( Heap_Block *the_block ); /* * _Heap_Start_of_user_area * * DESCRIPTION: * * This function returns the starting address of the portion of the block * which the user may access. */ STATIC INLINE void *_Heap_Start_of_user_area ( Heap_Block *the_block ); /* * _Heap_Is_block_in * * DESCRIPTION: * * This function returns TRUE if the_block is within the memory area * managed by the_heap, and FALSE otherwise. */ STATIC INLINE boolean _Heap_Is_block_in ( Heap_Control *the_heap, Heap_Block *the_block ); /* * _Heap_Is_page_size_valid * * DESCRIPTION: * * This function validates a specified heap page size. If the page size * is 0 or if lies outside a page size alignment boundary it is invalid * and FALSE is returned. Otherwise, the page size is valid and TRUE is * returned. */ STATIC INLINE boolean _Heap_Is_page_size_valid( unsigned32 page_size ); /* * _Heap_Build_flag * * DESCRIPTION: * * This function returns the block flag composed of size and in_use_flag. * The flag returned is suitable for use as a back or front flag in a * heap block. */ STATIC INLINE unsigned32 _Heap_Build_flag ( unsigned32 size, unsigned32 in_use_flag ); #include #ifdef __cplusplus } #endif #endif /* end of include file */