/* SPDX-License-Identifier: BSD-2-Clause */
/**
* @file
*
* @ingroup RTEMSScoreHeap
*
* @brief This source file contains the implementation of
* _Heap_Initialize() and _Heap_Block_allocate().
*/
/*
* COPYRIGHT (c) 1989-2009.
* On-Line Applications Research Corporation (OAR).
*
* Copyright (C) 2009, 2010 embedded brains GmbH & Co. KG
*
* 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.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include <rtems/score/heapimpl.h>
#include <rtems/score/threadimpl.h>
#include <rtems/score/interr.h>
#include <string.h>
#if CPU_ALIGNMENT == 0 || CPU_ALIGNMENT % 2 != 0
#error "invalid CPU_ALIGNMENT value"
#endif
/*
* _Heap_Initialize
*
* This kernel routine initializes a heap.
*
* Input parameters:
* heap - pointer to heap header
* area_begin - starting address of heap
* size - size of heap
* page_size - allocatable unit of memory
*
* Output parameters:
* returns - maximum memory available if RTEMS_SUCCESSFUL
* 0 - otherwise
*
* This is what a heap looks like in memory immediately after initialization:
*
*
* +--------------------------------+ <- begin = area_begin
* | unused space due to alignment |
* | size < page_size |
* 0 +--------------------------------+ <- first block
* | prev_size = page_size |
* 4 +--------------------------------+
* | size = size0 | 1 |
* 8 +---------------------+----------+ <- aligned on page_size
* | next = HEAP_TAIL | |
* 12 +---------------------+ |
* | prev = HEAP_HEAD | memory |
* +---------------------+ |
* | available |
* | |
* | for allocation |
* | |
* size0 +--------------------------------+ <- last dummy block
* | prev_size = size0 |
* +4 +--------------------------------+
* | size = page_size | 0 | <- prev block is free
* +8 +--------------------------------+ <- aligned on page_size
* | unused space due to alignment |
* | size < page_size |
* +--------------------------------+ <- end = begin + size
*
* Below is what a heap looks like after first allocation of SIZE bytes using
* _Heap_allocate(). BSIZE stands for SIZE + 4 aligned up on 'page_size'
* boundary.
* [NOTE: If allocation were performed by _Heap_Allocate_aligned(), the
* block size BSIZE is defined differently, and previously free block will
* be split so that upper part of it will become used block (see
* 'heapallocatealigned.c' for details).]
*
* +--------------------------------+ <- begin = area_begin
* | unused space due to alignment |
* | size < page_size |
* 0 +--------------------------------+ <- used block
* | prev_size = page_size |
* 4 +--------------------------------+
* | size = BSIZE | 1 | <- prev block is used
* 8 +--------------------------------+ <- aligned on page_size
* | . | Pointer returned to the user
* | . | is 8 for _Heap_Allocate()
* | . | and is in range
* 8 + | user-accessible | [8,8+page_size) for
* page_size +- - - - - -+ _Heap_Allocate_aligned()
* | area |
* | . |
* BSIZE +- - - - - . - - - - -+ <- free block
* | . |
* BSIZE +4 +--------------------------------+
* | size = S = size0 - BSIZE | 1 | <- prev block is used
* BSIZE +8 +-------------------+------------+ <- aligned on page_size
* | next = HEAP_TAIL | |
* BSIZE +12 +-------------------+ |
* | prev = HEAP_HEAD | memory |
* +-------------------+ |
* | . available |
* | . |
* | . for |
* | . |
* BSIZE +S+0 +-------------------+ allocation + <- last dummy block
* | prev_size = S | |
* +S+4 +-------------------+------------+
* | size = page_size | 0 | <- prev block is free
* +S+8 +--------------------------------+ <- aligned on page_size
* | unused space due to alignment |
* | size < page_size |
* +--------------------------------+ <- end = begin + size
*
*/
#ifdef HEAP_PROTECTION
static void _Heap_Protection_block_initialize_default(
Heap_Control *heap,
Heap_Block *block
)
{
block->Protection_begin.protector [0] = HEAP_BEGIN_PROTECTOR_0;
block->Protection_begin.protector [1] = HEAP_BEGIN_PROTECTOR_1;
block->Protection_begin.next_delayed_free_block = NULL;
block->Protection_begin.task = _Thread_Get_executing();
block->Protection_begin.tag = NULL;
block->Protection_end.protector [0] = HEAP_END_PROTECTOR_0;
block->Protection_end.protector [1] = HEAP_END_PROTECTOR_1;
}
static void _Heap_Protection_block_check_default(
Heap_Control *heap,
Heap_Block *block
)
{
if (
block->Protection_begin.protector [0] != HEAP_BEGIN_PROTECTOR_0
|| block->Protection_begin.protector [1] != HEAP_BEGIN_PROTECTOR_1
|| block->Protection_end.protector [0] != HEAP_END_PROTECTOR_0
|| block->Protection_end.protector [1] != HEAP_END_PROTECTOR_1
) {
_Heap_Protection_block_error( heap, block, HEAP_ERROR_BROKEN_PROTECTOR );
}
}
static void _Heap_Protection_block_error_default(
Heap_Control *heap,
Heap_Block *block,
Heap_Error_reason reason
)
{
Heap_Error_context error_context = {
.heap = heap,
.block = block,
.reason = reason
};
_Terminate( RTEMS_FATAL_SOURCE_HEAP, (uintptr_t) &error_context );
}
#endif
bool _Heap_Get_first_and_last_block(
uintptr_t heap_area_begin,
uintptr_t heap_area_size,
uintptr_t page_size,
uintptr_t min_block_size,
Heap_Block **first_block_ptr,
Heap_Block **last_block_ptr
)
{
uintptr_t const heap_area_end = heap_area_begin + heap_area_size;
uintptr_t const alloc_area_begin =
_Heap_Align_up( heap_area_begin + HEAP_BLOCK_HEADER_SIZE, page_size );
uintptr_t const first_block_begin =
alloc_area_begin - HEAP_BLOCK_HEADER_SIZE;
uintptr_t const overhead =
HEAP_BLOCK_HEADER_SIZE + (first_block_begin - heap_area_begin);
uintptr_t const first_block_size =
_Heap_Align_down( heap_area_size - overhead, page_size );
Heap_Block *const first_block = (Heap_Block *) first_block_begin;
Heap_Block *const last_block =
_Heap_Block_at( first_block, first_block_size );
if (
heap_area_end < heap_area_begin
|| heap_area_size <= overhead
|| first_block_size < min_block_size
) {
/* Invalid area or area too small */
return false;
}
*first_block_ptr = first_block;
*last_block_ptr = last_block;
return true;
}
uintptr_t _Heap_Initialize(
Heap_Control *heap,
void *heap_area_begin_ptr,
uintptr_t heap_area_size,
uintptr_t page_size
)
{
Heap_Statistics *const stats = &heap->stats;
uintptr_t const heap_area_begin = (uintptr_t) heap_area_begin_ptr;
uintptr_t const heap_area_end = heap_area_begin + heap_area_size;
uintptr_t first_block_begin = 0;
uintptr_t first_block_size = 0;
uintptr_t last_block_begin = 0;
uintptr_t min_block_size = 0;
bool area_ok = false;
Heap_Block *first_block = NULL;
Heap_Block *last_block = NULL;
if ( page_size == 0 ) {
page_size = CPU_ALIGNMENT;
} else {
page_size = _Heap_Align_up( page_size, CPU_ALIGNMENT );
if ( page_size < CPU_ALIGNMENT ) {
/* Integer overflow */
return 0;
}
}
min_block_size = _Heap_Min_block_size( page_size );
area_ok = _Heap_Get_first_and_last_block(
heap_area_begin,
heap_area_size,
page_size,
min_block_size,
&first_block,
&last_block
);
if ( !area_ok ) {
return 0;
}
memset(heap, 0, sizeof(*heap));
#ifdef HEAP_PROTECTION
heap->Protection.block_initialize = _Heap_Protection_block_initialize_default;
heap->Protection.block_check = _Heap_Protection_block_check_default;
heap->Protection.block_error = _Heap_Protection_block_error_default;
#endif
first_block_begin = (uintptr_t) first_block;
last_block_begin = (uintptr_t) last_block;
first_block_size = last_block_begin - first_block_begin;
/* First block */
first_block->prev_size = heap_area_end;
first_block->size_and_flag = first_block_size | HEAP_PREV_BLOCK_USED;
first_block->next = _Heap_Free_list_tail( heap );
first_block->prev = _Heap_Free_list_head( heap );
_Heap_Protection_block_initialize( heap, first_block );
/* Heap control */
heap->page_size = page_size;
heap->min_block_size = min_block_size;
heap->area_begin = heap_area_begin;
heap->area_end = heap_area_end;
heap->first_block = first_block;
heap->last_block = last_block;
_Heap_Free_list_head( heap )->next = first_block;
_Heap_Free_list_tail( heap )->prev = first_block;
/* Last block */
last_block->prev_size = first_block_size;
last_block->size_and_flag = 0;
_Heap_Set_last_block_size( heap );
_Heap_Protection_block_initialize( heap, last_block );
/* Statistics */
stats->size = first_block_size;
stats->free_size = first_block_size;
stats->min_free_size = first_block_size;
stats->free_blocks = 1;
stats->max_free_blocks = 1;
_Heap_Protection_set_delayed_free_fraction( heap, 2 );
_HAssert( _Heap_Is_aligned( heap->page_size, CPU_ALIGNMENT ) );
_HAssert( _Heap_Is_aligned( heap->min_block_size, page_size ) );
_HAssert(
_Heap_Is_aligned( _Heap_Alloc_area_of_block( first_block ), page_size )
);
_HAssert(
_Heap_Is_aligned( _Heap_Alloc_area_of_block( last_block ), page_size )
);
return first_block_size;
}
static void _Heap_Block_split(
Heap_Control *heap,
Heap_Block *block,
Heap_Block *next_block,
Heap_Block *free_list_anchor,
uintptr_t alloc_size
)
{
Heap_Statistics *const stats = &heap->stats;
uintptr_t const page_size = heap->page_size;
uintptr_t const min_block_size = heap->min_block_size;
uintptr_t const min_alloc_size = min_block_size - HEAP_BLOCK_HEADER_SIZE;
uintptr_t const block_size = _Heap_Block_size( block );
uintptr_t const used_size =
_Heap_Max( alloc_size, min_alloc_size ) + HEAP_BLOCK_HEADER_SIZE;
uintptr_t const used_block_size = _Heap_Align_up( used_size, page_size );
uintptr_t const free_size = block_size + HEAP_ALLOC_BONUS - used_size;
uintptr_t const free_size_limit = min_block_size + HEAP_ALLOC_BONUS;
_HAssert( used_size <= block_size + HEAP_ALLOC_BONUS );
_HAssert( used_size + free_size == block_size + HEAP_ALLOC_BONUS );
if ( free_size >= free_size_limit ) {
Heap_Block *const free_block = _Heap_Block_at( block, used_block_size );
uintptr_t free_block_size = block_size - used_block_size;
uintptr_t const next_block_size = _Heap_Block_size( next_block );
Heap_Block *const next_next_block =
_Heap_Block_at( next_block, next_block_size );
_HAssert( used_block_size + free_block_size == block_size );
_Heap_Block_set_size( block, used_block_size );
/* Statistics */
stats->free_size += free_block_size;
if ( _Heap_Is_prev_used( next_next_block ) ) {
_Heap_Free_list_insert_after( free_list_anchor, free_block );
/* Statistics */
++stats->free_blocks;
} else {
_Heap_Free_list_replace( next_block, free_block );
free_block_size += next_block_size;
next_block = _Heap_Block_at( free_block, free_block_size );
}
free_block->size_and_flag = free_block_size | HEAP_PREV_BLOCK_USED;
next_block->prev_size = free_block_size;
next_block->size_and_flag &= ~HEAP_PREV_BLOCK_USED;
_Heap_Protection_block_initialize( heap, free_block );
} else {
next_block->size_and_flag |= HEAP_PREV_BLOCK_USED;
}
}
static Heap_Block *_Heap_Block_allocate_from_begin(
Heap_Control *heap,
Heap_Block *block,
Heap_Block *next_block,
Heap_Block *free_list_anchor,
uintptr_t alloc_size
)
{
_Heap_Block_split( heap, block, next_block, free_list_anchor, alloc_size );
return block;
}
static Heap_Block *_Heap_Block_allocate_from_end(
Heap_Control *heap,
Heap_Block *block,
Heap_Block *next_block,
Heap_Block *free_list_anchor,
uintptr_t alloc_begin,
uintptr_t alloc_size
)
{
Heap_Statistics *const stats = &heap->stats;
Heap_Block *const new_block =
_Heap_Block_of_alloc_area( alloc_begin, heap->page_size );
uintptr_t const new_block_begin = (uintptr_t) new_block;
uintptr_t const new_block_size = (uintptr_t) next_block - new_block_begin;
uintptr_t block_size_adjusted = (uintptr_t) new_block - (uintptr_t) block;
_HAssert( block_size_adjusted >= heap->min_block_size );
_HAssert( new_block_size >= heap->min_block_size );
/* Statistics */
stats->free_size += block_size_adjusted;
if ( _Heap_Is_prev_used( block ) ) {
_Heap_Free_list_insert_after( free_list_anchor, block );
free_list_anchor = block;
/* Statistics */
++stats->free_blocks;
} else {
Heap_Block *const prev_block = _Heap_Prev_block( block );
uintptr_t const prev_block_size = _Heap_Block_size( prev_block );
block = prev_block;
block_size_adjusted += prev_block_size;
}
block->size_and_flag = block_size_adjusted | HEAP_PREV_BLOCK_USED;
new_block->prev_size = block_size_adjusted;
new_block->size_and_flag = new_block_size;
_Heap_Block_split( heap, new_block, next_block, free_list_anchor, alloc_size );
return new_block;
}
Heap_Block *_Heap_Block_allocate(
Heap_Control *heap,
Heap_Block *block,
uintptr_t alloc_begin,
uintptr_t alloc_size
)
{
Heap_Statistics *const stats = &heap->stats;
uintptr_t const alloc_area_begin = _Heap_Alloc_area_of_block( block );
uintptr_t const alloc_area_offset = alloc_begin - alloc_area_begin;
uintptr_t const block_size = _Heap_Block_size( block );
Heap_Block *const next_block = _Heap_Block_at( block, block_size );
Heap_Block *free_list_anchor = NULL;
_HAssert( alloc_area_begin <= alloc_begin );
if ( _Heap_Is_prev_used( next_block ) ) {
free_list_anchor = _Heap_Free_list_head( heap );
} else {
free_list_anchor = block->prev;
_Heap_Free_list_remove( block );
/* Statistics */
--stats->free_blocks;
++stats->used_blocks;
stats->free_size -= block_size;
}
if ( alloc_area_offset < heap->page_size ) {
alloc_size += alloc_area_offset;
block = _Heap_Block_allocate_from_begin(
heap,
block,
next_block,
free_list_anchor,
alloc_size
);
} else {
block = _Heap_Block_allocate_from_end(
heap,
block,
next_block,
free_list_anchor,
alloc_begin,
alloc_size
);
}
/* Statistics */
if ( stats->min_free_size > stats->free_size ) {
stats->min_free_size = stats->free_size;
}
_Heap_Protection_block_initialize( heap, block );
return block;
}
