score/src/heapextend.c

0001 /* SPDX-License-Identifier: BSD-2-Clause */
0002
0003 /**
0004  * @file
0005  *
0006  * @ingroup RTEMSScoreHeap
0007  *
0008  * @brief This source file contains the implementation of
0009  *   _Heap_Extend().
0010  */
0011
0012 /*
0013  *  COPYRIGHT (c) 1989-1999.
0014  *  On-Line Applications Research Corporation (OAR).
0015  *
0016  *  Copyright (c) 2010 embedded brains GmbH & Co. KG
0017  *
0018  * Redistribution and use in source and binary forms, with or without
0019  * modification, are permitted provided that the following conditions
0020  * are met:
0021  * 1. Redistributions of source code must retain the above copyright
0022  *    notice, this list of conditions and the following disclaimer.
0023  * 2. Redistributions in binary form must reproduce the above copyright
0024  *    notice, this list of conditions and the following disclaimer in the
0025  *    documentation and/or other materials provided with the distribution.
0026  *
0027  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0028  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0029  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0030  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0031  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0032  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0033  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0034  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0035  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0036  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0037  * POSSIBILITY OF SUCH DAMAGE.
0038  */
0039
0040 #ifdef HAVE_CONFIG_H
0041 #include "config.h"
0042 #endif
0043
0044 #include <rtems/score/heapimpl.h>
0045
0046 static void _Heap_Free_block( Heap_Control *heap, Heap_Block *block )
0047 {
0048   Heap_Statistics *const stats = &heap->stats;
0049   Heap_Block *first_free;
0050
0051   /* Statistics */
0052   ++stats->used_blocks;
0053   --stats->frees;
0054
0055   /*
0056    * The _Heap_Free() will place the block to the head of free list.  We want
0057    * the new block at the end of the free list.  So that initial and earlier
0058    * areas are consumed first.
0059    */
0060   _Heap_Free( heap, (void *) _Heap_Alloc_area_of_block( block ) );
0061   _Heap_Protection_free_all_delayed_blocks( heap );
0062   first_free = _Heap_Free_list_first( heap );
0063   _Heap_Free_list_remove( first_free );
0064   _Heap_Free_list_insert_before( _Heap_Free_list_tail( heap ), first_free );
0065 }
0066
0067 static void _Heap_Merge_below(
0068   Heap_Control *heap,
0069   uintptr_t extend_area_begin,
0070   Heap_Block *first_block
0071 )
0072 {
0073   uintptr_t const page_size = heap->page_size;
0074   uintptr_t const new_first_block_alloc_begin =
0075     _Heap_Align_up( extend_area_begin + HEAP_BLOCK_HEADER_SIZE, page_size );
0076   uintptr_t const new_first_block_begin =
0077     new_first_block_alloc_begin - HEAP_BLOCK_HEADER_SIZE;
0078   uintptr_t const first_block_begin = (uintptr_t) first_block;
0079   uintptr_t const new_first_block_size =
0080     first_block_begin - new_first_block_begin;
0081   Heap_Block *const new_first_block = (Heap_Block *) new_first_block_begin;
0082
0083   new_first_block->prev_size = first_block->prev_size;
0084   new_first_block->size_and_flag = new_first_block_size | HEAP_PREV_BLOCK_USED;
0085
0086   _Heap_Free_block( heap, new_first_block );
0087 }
0088
0089 static void _Heap_Merge_above(
0090   Heap_Control *heap,
0091   Heap_Block *last_block,
0092   uintptr_t extend_area_end
0093 )
0094 {
0095   uintptr_t const page_size = heap->page_size;
0096   uintptr_t const last_block_begin = (uintptr_t) last_block;
0097   uintptr_t const last_block_new_size = _Heap_Align_down(
0098     extend_area_end - last_block_begin - HEAP_BLOCK_HEADER_SIZE,
0099     page_size
0100   );
0101   Heap_Block *const new_last_block =
0102     _Heap_Block_at( last_block, last_block_new_size );
0103
0104   new_last_block->size_and_flag =
0105     (last_block->size_and_flag - last_block_new_size)
0106       | HEAP_PREV_BLOCK_USED;
0107
0108   _Heap_Block_set_size( last_block, last_block_new_size );
0109
0110   _Heap_Free_block( heap, last_block );
0111 }
0112
0113 static void _Heap_Link_below(
0114   Heap_Block *link,
0115   Heap_Block *last_block
0116 )
0117 {
0118   uintptr_t const last_block_begin = (uintptr_t) last_block;
0119   uintptr_t const link_begin = (uintptr_t) link;
0120
0121   last_block->size_and_flag =
0122     (link_begin - last_block_begin) | HEAP_PREV_BLOCK_USED;
0123 }
0124
0125 static void _Heap_Link_above(
0126   Heap_Block *link,
0127   Heap_Block *first_block,
0128   Heap_Block *last_block
0129 )
0130 {
0131   uintptr_t const link_begin = (uintptr_t) link;
0132   uintptr_t const first_block_begin = (uintptr_t) first_block;
0133
0134   _Heap_Block_set_size( link, first_block_begin - link_begin );
0135
0136   last_block->size_and_flag |= HEAP_PREV_BLOCK_USED;
0137 }
0138
0139 uintptr_t _Heap_Extend(
0140   Heap_Control *heap,
0141   void *extend_area_begin_ptr,
0142   uintptr_t extend_area_size,
0143   uintptr_t unused RTEMS_UNUSED
0144 )
0145 {
0146   Heap_Statistics *const stats = &heap->stats;
0147   Heap_Block *const first_block = heap->first_block;
0148   Heap_Block *start_block = first_block;
0149   Heap_Block *merge_below_block = NULL;
0150   Heap_Block *merge_above_block = NULL;
0151   Heap_Block *link_below_block = NULL;
0152   Heap_Block *link_above_block = NULL;
0153   Heap_Block *extend_first_block = NULL;
0154   Heap_Block *extend_last_block = NULL;
0155   uintptr_t const page_size = heap->page_size;
0156   uintptr_t const min_block_size = heap->min_block_size;
0157   uintptr_t const extend_area_begin = (uintptr_t) extend_area_begin_ptr;
0158   uintptr_t const extend_area_end = extend_area_begin + extend_area_size;
0159   uintptr_t const free_size = stats->free_size;
0160   uintptr_t extend_first_block_size = 0;
0161   uintptr_t extended_size = 0;
0162   bool extend_area_ok = false;
0163
0164   if ( extend_area_end < extend_area_begin ) {
0165     return 0;
0166   }
0167
0168   extend_area_ok = _Heap_Get_first_and_last_block(
0169     extend_area_begin,
0170     extend_area_size,
0171     page_size,
0172     min_block_size,
0173     &extend_first_block,
0174     &extend_last_block
0175   );
0176   if (!extend_area_ok ) {
0177     /* For simplicity we reject extend areas that are too small */
0178     return 0;
0179   }
0180
0181   do {
0182     uintptr_t const sub_area_begin = (start_block != first_block) ?
0183       (uintptr_t) start_block : heap->area_begin;
0184     uintptr_t const sub_area_end = start_block->prev_size;
0185     Heap_Block *const end_block =
0186       _Heap_Block_of_alloc_area( sub_area_end, page_size );
0187
0188     if (
0189       sub_area_end > extend_area_begin && extend_area_end > sub_area_begin
0190     ) {
0191       return 0;
0192     }
0193
0194     if ( extend_area_end == sub_area_begin ) {
0195       merge_below_block = start_block;
0196     } else if ( extend_area_end < sub_area_end ) {
0197       link_below_block = start_block;
0198     }
0199
0200     if ( sub_area_end == extend_area_begin ) {
0201       start_block->prev_size = extend_area_end;
0202
0203       merge_above_block = end_block;
0204     } else if ( sub_area_end < extend_area_begin ) {
0205       link_above_block = end_block;
0206     }
0207
0208     start_block = _Heap_Block_at( end_block, _Heap_Block_size( end_block ) );
0209   } while ( start_block != first_block );
0210
0211   if ( extend_area_begin < heap->area_begin ) {
0212     heap->area_begin = extend_area_begin;
0213   } else if ( heap->area_end < extend_area_end ) {
0214     heap->area_end = extend_area_end;
0215   }
0216
0217   extend_first_block_size =
0218     (uintptr_t) extend_last_block - (uintptr_t) extend_first_block;
0219
0220   extend_first_block->prev_size = extend_area_end;
0221   extend_first_block->size_and_flag =
0222     extend_first_block_size | HEAP_PREV_BLOCK_USED;
0223   _Heap_Protection_block_initialize( heap, extend_first_block );
0224
0225   extend_last_block->prev_size = extend_first_block_size;
0226   extend_last_block->size_and_flag = 0;
0227   _Heap_Protection_block_initialize( heap, extend_last_block );
0228
0229   if ( (uintptr_t) extend_first_block < (uintptr_t) heap->first_block ) {
0230     heap->first_block = extend_first_block;
0231   } else if ( (uintptr_t) extend_last_block > (uintptr_t) heap->last_block ) {
0232     heap->last_block = extend_last_block;
0233   }
0234
0235   if ( merge_below_block != NULL ) {
0236     _Heap_Merge_below( heap, extend_area_begin, merge_below_block );
0237   } else if ( link_below_block != NULL ) {
0238     _Heap_Link_below(
0239       link_below_block,
0240       extend_last_block
0241     );
0242   }
0243
0244   if ( merge_above_block != NULL ) {
0245     _Heap_Merge_above( heap, merge_above_block, extend_area_end );
0246   } else if ( link_above_block != NULL ) {
0247     _Heap_Link_above(
0248       link_above_block,
0249       extend_first_block,
0250       extend_last_block
0251     );
0252   }
0253
0254   if ( merge_below_block == NULL && merge_above_block == NULL ) {
0255     _Heap_Free_block( heap, extend_first_block );
0256   }
0257
0258   _Heap_Set_last_block_size( heap );
0259
0260   extended_size = stats->free_size - free_size;
0261
0262   /* Statistics */
0263   stats->size += extended_size;
0264
0265   return extended_size;
0266 }