LXR 6.1/​cpukit/​include/​rtems/​score/​heap.h	Source navigation Diff markup Identifier search General search
	Version: 6.1 Revert   Change

File indexing completed on 2025-05-11 08:24:12

 /* SPDX-License-Identifier: BSD-2-Clause */
 
 /**
  * @file
  *
  * @ingroup RTEMSScoreHeap
  *
  * @brief This header file provides interfaces of the
  *   @ref RTEMSScoreHeap which are used by the implementation and the
  *   @ref RTEMSImplApplConfig.
  */
 
 /*
  *  COPYRIGHT (c) 1989-2006.
  *  On-Line Applications Research Corporation (OAR).
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
 #ifndef _RTEMS_SCORE_HEAP_H
 #define _RTEMS_SCORE_HEAP_H
 
 #include <rtems/score/cpu.h>
 #include <rtems/score/heapinfo.h>
 
 #ifdef __cplusplus
 extern "C" {
 #endif
 
 #ifdef RTEMS_DEBUG
   #define HEAP_PROTECTION
 #endif
 
 /**
  * @defgroup RTEMSScoreHeap Heap Handler
  *
  * @ingroup RTEMSScore
  *
  * @brief This group contains the Heap Handler implementation.
  *
  * 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 free blocks is contained in the heap
  * area.  A heap control structure contains control information for the heap.
  *
  * The alignment routines could be made faster should we require only powers of
  * two to be supported for page size, alignment and boundary arguments.  The
  * minimum alignment requirement for pages is currently CPU_ALIGNMENT and this
  * value is only required to be multiple of two and explicitly not required to
  * be a power of two.
  *
  * There are two kinds of blocks.  One sort describes a free block from which
  * we can allocate memory.  The other blocks are used and provide an allocated
  * memory area.  The free blocks are accessible via a list of free blocks.
  *
  * Blocks or areas cover a continuous set of memory addresses. They have a
  * begin and end address.  The end address is not part of the set.  The size of
  * a block or area equals the distance between the begin and end address in
  * units of bytes.
  *
  * Free blocks look like:
  * <table>
  *   <tr>
  *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
  *       previous block is free, <br> otherwise it may contain data used by
  *       the previous block</td>
  *   </tr>
  *   <tr>
  *     <td>block size and a flag which indicates if the previous block is free
  *       or used, <br> this field contains always valid data regardless of the
  *       block usage</td>
  *   </tr>
  *   <tr><td>pointer to next block (this field is page size aligned)</td></tr>
  *   <tr><td>pointer to previous block</td></tr>
  *   <tr><td colspan=2>free space</td></tr>
  * </table>
  *
  * Used blocks look like:
  * <table>
  *   <tr>
  *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
  *       previous block is free,<br>otherwise it may contain data used by
  *       the previous block</td>
  *   </tr>
  *   <tr>
  *     <td>block size and a flag which indicates if the previous block is free
  *       or used, <br> this field contains always valid data regardless of the
  *       block usage</td>
  *   </tr>
  *   <tr><td>begin of allocated area (this field is page size aligned)</td></tr>
  *   <tr><td>allocated space</td></tr>
  *   <tr><td colspan=2>allocated space</td></tr>
  * </table>
  *
  * The heap area after initialization contains two blocks and looks like:
  * <table>
  *   <tr><th>Label</th><th colspan=2>Content</th></tr>
  *   <tr><td>heap->area_begin</td><td colspan=2>heap area begin address</td></tr>
  *   <tr>
  *     <td>first_block->prev_size</td>
  *     <td colspan=2>
  *       subordinate heap area end address (this will be used to maintain a
  *       linked list of scattered heap areas)
  *     </td>
  *   </tr>
  *   <tr>
  *     <td>first_block->size</td>
  *     <td colspan=2>size available for allocation
  *       | @c HEAP_PREV_BLOCK_USED</td>
  *   </tr>
  *   <tr>
  *     <td>first_block->next</td><td>_Heap_Free_list_tail(heap)</td>
  *     <td rowspan=3>memory area available for allocation</td>
  *   </tr>
  *   <tr><td>first_block->prev</td><td>_Heap_Free_list_head(heap)</td></tr>
  *   <tr><td>...</td></tr>
  *   <tr>
  *     <td>last_block->prev_size</td><td colspan=2>size of first block</td>
  *   </tr>
  *   <tr>
  *     <td>last_block->size</td>
  *     <td colspan=2>first block begin address - last block begin address</td>
  *   </tr>
  *   <tr><td>heap->area_end</td><td colspan=2>heap area end address</td></tr>
  * </table>
  * The next block of the last block is the first block.  Since the first
  * block indicates that the previous block is used, this ensures that the
  * last block appears as used for the _Heap_Is_used() and _Heap_Is_free()
  * functions.
  *
  * @{
  */
 
 typedef struct Heap_Control Heap_Control;
 
 typedef struct Heap_Block Heap_Block;
 
 /**
  * @brief The heap error reason.
  *
  * @see _Heap_Protection_block_error().
  */
 typedef enum {
   /**
    * @brief There is an unexpected value in the heap block protector area.
    */
   HEAP_ERROR_BROKEN_PROTECTOR,
 
   /**
    * @brief There is an unexpected value in the free pattern of a free heap
    * block.
    */
   HEAP_ERROR_FREE_PATTERN,
 
   /**
    * @brief There is was an attempt to free the same block twice.
    */
   HEAP_ERROR_DOUBLE_FREE,
 
   /**
    * @brief The next block of a supposed to be used block does not indicate that
    * the block is used.
    */
   HEAP_ERROR_BAD_USED_BLOCK,
 
   /**
    * @brief A supposed to be free block is not inside the heap memory area.
    */
   HEAP_ERROR_BAD_FREE_BLOCK
 } Heap_Error_reason;
 
 /**
  * @brief Context of a heap error.
  *
  * @see _Heap_Protection_block_error().
  */
 typedef struct {
   /**
    * @brief The heap of the block.
    */
   Heap_Control *heap;
 
   /**
    * @brief The heap block causing the error.
    */
   Heap_Block *block;
 
   /**
    * @brief The heap error reason.
    */
   Heap_Error_reason reason;
 } Heap_Error_context;
 
 #ifndef HEAP_PROTECTION
   #define HEAP_PROTECTION_HEADER_SIZE 0
 #else
   #define HEAP_PROTECTOR_COUNT 2
 
   #define HEAP_BEGIN_PROTECTOR_0 ((uintptr_t) 0xfd75a98f)
   #define HEAP_BEGIN_PROTECTOR_1 ((uintptr_t) 0xbfa1f177)
   #define HEAP_END_PROTECTOR_0 ((uintptr_t) 0xd6b8855e)
   #define HEAP_END_PROTECTOR_1 ((uintptr_t) 0x13a44a5b)
 
   #define HEAP_FREE_PATTERN ((uintptr_t) 0xe7093cdf)
 
   #define HEAP_PROTECTION_OBOLUS ((Heap_Block *) 1)
 
   typedef void (*_Heap_Protection_handler)(
      Heap_Control *heap,
      Heap_Block *block
   );
 
   typedef void (*_Heap_Protection_error_handler)(
      Heap_Control *heap,
      Heap_Block *block,
      Heap_Error_reason reason
   );
 
   typedef struct {
     _Heap_Protection_handler block_initialize;
     _Heap_Protection_handler block_check;
     _Heap_Protection_error_handler block_error;
     void *handler_data;
     Heap_Block *first_delayed_free_block;
     Heap_Block *last_delayed_free_block;
     uintptr_t delayed_free_block_count;
     uintptr_t delayed_free_fraction;
   } Heap_Protection;
 
   struct _Thread_Control;
 
   typedef struct {
     uintptr_t protector [HEAP_PROTECTOR_COUNT];
     Heap_Block *next_delayed_free_block;
     struct _Thread_Control *task;
     void *tag;
   } Heap_Protection_block_begin;
 
   typedef struct {
     uintptr_t protector [HEAP_PROTECTOR_COUNT];
   } Heap_Protection_block_end;
 
   #define HEAP_PROTECTION_HEADER_SIZE \
     (sizeof(Heap_Protection_block_begin) + sizeof(Heap_Protection_block_end))
 #endif
 
 /**
  * @brief The block header consists of the two size fields
  * (@ref Heap_Block.prev_size and @ref Heap_Block.size_and_flag).
  */
 #define HEAP_BLOCK_HEADER_SIZE \
   (2 * sizeof(uintptr_t) + HEAP_PROTECTION_HEADER_SIZE)
 
 /**
  * @brief Description for free or used blocks.
  */
 struct Heap_Block {
   /**
    * @brief Size of the previous block or part of the allocated area of the
    * previous block.
    *
    * This field is only valid if the previous block is free.  This case is
    * indicated by a cleared @c HEAP_PREV_BLOCK_USED flag in the
    * @a size_and_flag field of the current block.
    *
    * In a used block only the @a size_and_flag field needs to be valid.  The
    * @a prev_size field of the current block is maintained by the previous
    * block.  The current block can use the @a prev_size field in the next block
    * for allocation.
    */
   uintptr_t prev_size;
 
   #ifdef HEAP_PROTECTION
     Heap_Protection_block_begin Protection_begin;
   #endif
 
   /**
    * @brief Contains the size of the current block and a flag which indicates
    * if the previous block is free or used.
    *
    * If the flag @c HEAP_PREV_BLOCK_USED is set, then the previous block is
    * used, otherwise the previous block is free.  A used previous block may
    * claim the @a prev_size field for allocation.  This trick allows to
    * decrease the overhead in the used blocks by the size of the @a prev_size
    * field.  As sizes are required to be multiples of two, the least
    * significant bits would be always zero. We use this bit to store the flag.
    *
    * This field is always valid.
    */
   uintptr_t size_and_flag;
 
   #ifdef HEAP_PROTECTION
     Heap_Protection_block_end Protection_end;
   #endif
 
   /**
    * @brief Pointer to the next free block or part of the allocated area.
    *
    * This field is page size aligned and begins of the allocated area in case
    * the block is used.
    *
    * This field is only valid if the block is free and thus part of the free
    * block list.
    */
   Heap_Block *next;
 
   /**
    * @brief Pointer to the previous free block or part of the allocated area.
    *
    * This field is only valid if the block is free and thus part of the free
    * block list.
    */
   Heap_Block *prev;
 };
 
 /**
  * @brief Control block used to manage a heap.
  */
 struct Heap_Control {
   Heap_Block free_list;
   uintptr_t page_size;
   uintptr_t min_block_size;
   uintptr_t area_begin;
   uintptr_t area_end;
   Heap_Block *first_block;
   Heap_Block *last_block;
   Heap_Statistics stats;
   #ifdef HEAP_PROTECTION
     Heap_Protection Protection;
   #endif
 };
 
 /**
  * @brief Heap area structure for table based heap initialization and
  * extension.
  *
  * @see Heap_Initialization_or_extend_handler.
  */
 typedef struct {
   void *begin;
   uintptr_t size;
 } Heap_Area;
 
 /**
  * @brief Heap initialization and extend handler type.
  *
  * This helps to do a table based heap initialization and extension.  Create a
  * table of Heap_Area elements and iterate through it.  Set the handler to
  * _Heap_Initialize() in the first iteration and then to _Heap_Extend().
  *
  * @see Heap_Area, _Heap_Initialize(), _Heap_Extend(), or _Heap_No_extend().
  */
 typedef uintptr_t (*Heap_Initialization_or_extend_handler)(
   Heap_Control *heap,
   void *area_begin,
   uintptr_t area_size,
   uintptr_t page_size_or_unused
 );
 
 /**
  * @brief Extends the memory available for the heap.
  *
  * There are no alignment requirements for the memory area.  The memory area
  * must be big enough to contain some maintenance blocks.  It must not overlap
  * parts of the current heap memory areas.  Disconnected memory areas added to
  * the heap will lead to used blocks which cover the gaps.  Extending with an
  * inappropriate memory area will corrupt the heap resulting in undefined
  * behaviour.
  *
  * @param[in, out] heap The heap to extend.
  * @param[out] area_begin The start address of the area to extend the @a heap with.
  * @param area_size The size of the area in bytes.
  * @param unused Is not used, only provided to have the same signature as _Heap_Initialize().
  *
  * @retval some_value The extended space available for allocation after successful extension.
  * @retval 0 The heap extension failed.
  *
  * @see Heap_Initialization_or_extend_handler.
  */
 uintptr_t _Heap_Extend(
   Heap_Control *heap,
   void *area_begin,
   uintptr_t area_size,
   uintptr_t unused
 );
 
 /**
  * @brief This function returns always zero.
  *
  * This function only returns zero and does nothing else.
  *
  * @param unused_0 This parameter does nothing.
  * @param unused_1 This parameter does nothing.
  * @param unused_2 This parameter does nothing.
  * @param unused_3 This parameter does nothing.
  *
  * @see Heap_Initialization_or_extend_handler.
  */
 uintptr_t _Heap_No_extend(
   Heap_Control *unused_0,
   void *unused_1,
   uintptr_t unused_2,
   uintptr_t unused_3
 );
 
 /**
  * @brief Aligns the value to a given alignment, rounding up.
  *
  * @param value The value to be aligned.
  * @param alignment The alignment for the value.
  *
  * @return The @a value aligned to the given @a alignment, rounded up.
  */
 static inline uintptr_t _Heap_Align_up(
   uintptr_t value,
   uintptr_t alignment
 )
 {
   uintptr_t remainder = value % alignment;
 
   if ( remainder != 0 ) {
     return value - remainder + alignment;
   } else {
     return value;
   }
 }
 
 /**
  * @brief Returns the minimal Heap Block size for the given page_size.
  *
  * @param page_size The page size for the heap.
  *
  * @return The minimal Heap Block size for the given @a page_size.
  */
 static inline uintptr_t _Heap_Min_block_size( uintptr_t page_size )
 {
   return _Heap_Align_up( sizeof( Heap_Block ), page_size );
 }
 
 /**
  * @brief Returns the worst case overhead to manage a memory area.
  *
  * @param page_size The page size to calculate the worst case memory manage overhead.
  *
  * @return The worst case overhead to manage a memory area.
  */
 static inline uintptr_t _Heap_Area_overhead(
   uintptr_t page_size
 )
 {
   if ( page_size != 0 ) {
     page_size = _Heap_Align_up( page_size, CPU_ALIGNMENT );
   } else {
     page_size = CPU_ALIGNMENT;
   }
 
   /*
    * Account for a potential alignment of the area begin address to a page
    * boundary, the first block, and the last block.  The last block consists
    * only of a block header.
    */
   return page_size - 1 + _Heap_Min_block_size( page_size ) +
     HEAP_BLOCK_HEADER_SIZE;
 }
 
 /**
  * @brief Returns the size with administration and alignment overhead for one
  * allocation.
  *
  * @param page_size The page size for the allocation.
  * @param size The size to allocate.
  * @param alignment The alignment that needs to be considered.
  *
  * @return The size with administration and alignment overhead for one allocation.
  */
 static inline uintptr_t _Heap_Size_with_overhead(
   uintptr_t page_size,
   uintptr_t size,
   uintptr_t alignment
 )
 {
   if ( page_size != 0 ) {
     page_size = _Heap_Align_up( page_size, CPU_ALIGNMENT );
   } else {
     page_size = CPU_ALIGNMENT;
   }
 
   if ( page_size < alignment ) {
     page_size = alignment;
   }
 
   return HEAP_BLOCK_HEADER_SIZE + page_size - 1 + size;
 }
 
 /** @} */
 
 #ifdef __cplusplus
 }
 #endif
 
 #endif
 /* end of include file */

This page was automatically generated by the 2.3.7 LXR engine. The LXR team