heap.h

开放源码的嵌入式开发环境

/**
 *  @file  rtems/score/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 control
 *  structure contains control information for the heap.
 *
 *  FIXME: the alignment routines could be made faster should we require only
 *         powers of two to be supported both for 'page_size' and for
 *         'alignment' arguments. However, both workspace and malloc heaps are
 *         initialized with CPU_HEAP_ALIGNMENT as 'page_size', and while all
 *         the BSPs seem to use CPU_ALIGNMENT (that is power of two) as
 *         CPU_HEAP_ALIGNMENT, for whatever reason CPU_HEAP_ALIGNMENT is only
 *         required to be multiple of CPU_ALIGNMENT and explicitly not
 *         required to be a power of two.
 *
 *  COPYRIGHT (c) 1989-2006.
 *  On-Line Applications Research Corporation (OAR).
 *
 *  The license and distribution terms for this file may be
 *  found in the file LICENSE in this distribution or at
 *  http://www.rtems.com/license/LICENSE.
 *
 *  $Id: heap.h,v 1.25 2006/01/16 15:13:58 joel Exp $
 */

#ifndef _RTEMS_SCORE_HEAP_H
#define _RTEMS_SCORE_HEAP_H

/**
 *  @defgroup ScoreHeap Heap Handler
 *
 *  This handler encapsulates functionality which provides the foundation
 *  Heap services used in all of the APIs supported by RTEMS.
 */
/**@{*/

#ifdef __cplusplus
extern "C" {
#endif

/**
 * This type defines unsigned integer type to store 'void*'. Analog of C99
 * 'uintptr_t'. This should work on 16/32/64 bit architectures.
 *
 * FIXME: Something like this should better be defined by
 *        'rtems/score/types.h' and used here.
 */

typedef uintptr_t _H_uptr_t;

/**
 *  Forward reference
 *
 *  @ref Heap_Block
 */
typedef struct Heap_Block_struct Heap_Block;

/**
 *  The following defines the data structure used to manage individual blocks
 *  in a heap.  When the block is allocated, the 'next' and 'prev' fields, as
 *  well as 'prev_size' field of the next block, are not used by the heap
 *  manager and thus the address returned for the block starts at the address
 *  of the 'next' field and the size of the user accessible area includes the
 *  size of the 'prev_size' field.
 *
 *  @note The 'next' and 'prev' pointers are only valid when the block is free.
 *     Caution must be taken to ensure that every block is large enough to
 *     hold them and that they are not accessed while the block is actually
 *     allocated (i.e., not free).
 *
 *  @note The 'prev_size' field is only valid when HEAP_PREV_USED bit is clear
 *     in the 'size' field indicating that previous block is not allocated.
 *     If the bit is set, the 'prev_size' field is part of user-accessible
 *     space of the previous allocated block and thus shouldn't be accessed
 *     by the heap manager code. This trick allows to further decrease
 *     overhead in the used blocks to the size of 'size' field (4 bytes).
 *
 */

struct Heap_Block_struct {
  /** size of prev block (if prev block is free) */
  uint32_t  prev_size;
  /** size of block in bytes and status of prev block */
  uint32_t  size;
  /** pointer to the next free block */
  Heap_Block *next;
  /** pointer to the previous free block */
  Heap_Block *prev;
};

/**
 *  This flag used in the 'size' field of each heap block to indicate
 *  if previous block is free or in use. As sizes are always multiples of
 *  4, the 2 least significant bits would always be 0, and we use one of them
 *  to store the flag.
 */

#define HEAP_PREV_USED    1     /* indicates previous block is in use */

/**
 *  The following constants reflect various requirements of the
 *  heap data structures which impact the management of a heap.
 */

#define HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block))

/**
 *  Offset of the block header from the block pointer. Equal to the
 *  offsetof(Heap_Block.size).
 */
#define HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t))

/**
 *  Offset of user data pointer from the block pointer. Equal to the
 *  offsetof(Heap_Block.next).
 */
#define HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2)

/**
 *  Num bytes of overhead in used block. Equal to the sizeof(Heap_Block.size).
 */
#define HEAP_BLOCK_USED_OVERHEAD \
  (HEAP_BLOCK_USER_OFFSET - HEAP_BLOCK_HEADER_OFFSET)

/** Size of the permanent dummy last block. */
#define HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET

/**
 *  Run-time heap statistics.
 *
 *  @note (double)searches/allocs gives mean number of searches per alloc while
 *        max_search gives maximum number of searches ever performed on a
 *        single call to alloc.
 *
 *  @note the statistics is always gathered. I believe the imposed overhead is
 *        rather small. Feel free to make it compile-time option if you think
 *        the overhead is too high for your application.
 */

typedef struct Heap_Statistics_tag {
  /** instance number of this heap */
  uint32_t instance;
  /** the size of the memory for heap */
  uint32_t size;
  /** current free size */
  uint32_t free_size;
  /** minimum free size ever */
  uint32_t min_free_size;
  /** current number of free blocks */
  uint32_t free_blocks;
  /** maximum number of free blocks ever */
  uint32_t max_free_blocks;
  /** current number of used blocks */
  uint32_t used_blocks;
  /** maximum number of blocks searched ever */
  uint32_t max_search;
  /** total number of successful calls to alloc */
  uint32_t allocs;
  /** total number of searches ever */
  uint32_t searches;
  /** total number of suceessful calls to free */
  uint32_t frees;
  /** total number of successful resizes */
  uint32_t resizes;
} Heap_Statistics;

/**
 *  Control block used to manage each heap.
 */
typedef struct {
  /** head and tail of circular list of free blocks */
  Heap_Block  free_list;
  /** allocation unit and alignment */
  uint32_t  page_size;
  /** minimum block size aligned on page_size */
  uint32_t  min_block_size;
  /** first address of memory for the heap */
  void       *begin;
  /** first address past end of memory for the heap */
  void       *end;
  /** first valid block address in the heap */
  Heap_Block *start;
  /** last valid block address in the heap */
  Heap_Block *final;
  /** run-time statistics */
  Heap_Statistics stats;
} Heap_Control;

/**
 *  Status codes for _Heap_Extend
 */

typedef enum {
  HEAP_EXTEND_SUCCESSFUL,
  HEAP_EXTEND_ERROR,
  HEAP_EXTEND_NOT_IMPLEMENTED
} Heap_Extend_status;

/**
 *  Status codes for _Heap_Resize_block
 */

typedef enum {
  HEAP_RESIZE_SUCCESSFUL,
  HEAP_RESIZE_UNSATISFIED,
  HEAP_RESIZE_FATAL_ERROR
} Heap_Resize_status;

/**
 *  Status codes for _Heap_Get_information
 */

typedef enum {
  HEAP_GET_INFORMATION_SUCCESSFUL = 0,
  HEAP_GET_INFORMATION_BLOCK_ERROR
} Heap_Get_information_status;

/**
 *  Information block returned by the Heap routines used to
 *  obtain heap information.  This information is returned about
 *  either free or used blocks.
 */
typedef struct {
  /** Number of blocks of this type. */
  uint32_t number;
  /** Largest blocks of this type. */
  uint32_t largest;
  /** Total size of the blocks of this type. */
  uint32_t total;
} Heap_Information;

/**
 *  Information block returned by _Heap_Get_information
 */
typedef struct {
  /** This field is information on the used blocks in the heap. */
  Heap_Information Free;
  /** This field is information on the used blocks in the heap. */
  Heap_Information Used;
} Heap_Information_block;

/**
 *  This routine initializes @a the_heap record to manage the
 *  contiguous heap of @a size bytes which starts at @a starting_address.
 *  Blocks of memory are allocated from the heap in multiples of
 *  @a page_size byte units. If @a page_size is 0 or is not multiple of
 *  CPU_ALIGNMENT, it's aligned up to the nearest CPU_ALIGNMENT boundary.
 *
 *  @param[in] the_heap is the heap to operate upon
 *  @param[in] starting_address is the starting address of the memory for
 *         the heap
 *  @param[in] size is the size in bytes of the memory area for the heap
 *  @param[in] page_size is the size in bytes of the allocation unit
 *
 *  @return This method returns the maximum memory available.  If