heap.h

Go to the documentation of this file.

/* SPDX-License-Identifier: BSD-2-Clause */
 
/*
 *  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
 
typedef struct Heap_Control Heap_Control;
 
typedef struct Heap_Block Heap_Block;
 
typedef enum {
  HEAP_ERROR_BROKEN_PROTECTOR,
 
  HEAP_ERROR_FREE_PATTERN,
 
  HEAP_ERROR_DOUBLE_FREE,
 
  HEAP_ERROR_BAD_USED_BLOCK,
 
  HEAP_ERROR_BAD_FREE_BLOCK
} Heap_Error_reason;
 
typedef struct {
  Heap_Control *heap;
 
  Heap_Block *block;
 
  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
 
#define HEAP_BLOCK_HEADER_SIZE \
  (2 * sizeof(uintptr_t) + HEAP_PROTECTION_HEADER_SIZE)
 
struct Heap_Block {
  uintptr_t prev_size;
 
  #ifdef HEAP_PROTECTION
    Heap_Protection_block_begin Protection_begin;
  #endif
 
  uintptr_t size_and_flag;
 
  #ifdef HEAP_PROTECTION
    Heap_Protection_block_end Protection_end;
  #endif
 
  Heap_Block *next;
 
  Heap_Block *prev;
};
 
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
};
 
typedef struct {
  void *begin;
  uintptr_t size;
} Heap_Area;
 
typedef uintptr_t (*Heap_Initialization_or_extend_handler)(
  Heap_Control *heap,
  void *area_begin,
  uintptr_t area_size,
  uintptr_t page_size_or_unused
);
 
uintptr_t _Heap_Extend(
  Heap_Control *heap,
  void *area_begin,
  uintptr_t area_size,
  uintptr_t unused
);
 
uintptr_t _Heap_No_extend(
  Heap_Control *unused_0,
  void *unused_1,
  uintptr_t unused_2,
  uintptr_t unused_3
);
 
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;
  }
}
 
static inline uintptr_t _Heap_Min_block_size( uintptr_t page_size )
{
  return _Heap_Align_up( sizeof( Heap_Block ), page_size );
}
 
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;
}
 
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 */