diff options
author | Joel Sherrill <joel.sherrill@OARcorp.com> | 1995-05-11 17:39:37 +0000 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@OARcorp.com> | 1995-05-11 17:39:37 +0000 |
commit | ac7d5ef06a6d6e8d84abbd1f0b82162725f98326 (patch) | |
tree | 9304cf759a73f2a1c6fd3191948f00e870af3787 /cpukit/score/include/rtems/score/heap.h | |
download | rtems-ac7d5ef06a6d6e8d84abbd1f0b82162725f98326.tar.bz2 |
Initial revision
Diffstat (limited to 'cpukit/score/include/rtems/score/heap.h')
-rw-r--r-- | cpukit/score/include/rtems/score/heap.h | 396 |
1 files changed, 396 insertions, 0 deletions
diff --git a/cpukit/score/include/rtems/score/heap.h b/cpukit/score/include/rtems/score/heap.h new file mode 100644 index 0000000000..9eb348a760 --- /dev/null +++ b/cpukit/score/include/rtems/score/heap.h @@ -0,0 +1,396 @@ +/* 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 <rtems/heap.inl> + +#ifdef __cplusplus +} +#endif + +#endif +/* end of include file */ |