/* 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 #include #include #include #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; }