score/src/heapfree.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_Free().
0010  */
0011
0012 /*
0013  *  COPYRIGHT (c) 1989-2007.
0014  *  On-Line Applications Research Corporation (OAR).
0015  *
0016  * Redistribution and use in source and binary forms, with or without
0017  * modification, are permitted provided that the following conditions
0018  * are met:
0019  * 1. Redistributions of source code must retain the above copyright
0020  *    notice, this list of conditions and the following disclaimer.
0021  * 2. Redistributions in binary form must reproduce the above copyright
0022  *    notice, this list of conditions and the following disclaimer in the
0023  *    documentation and/or other materials provided with the distribution.
0024  *
0025  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0026  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0027  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0028  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0029  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0030  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0031  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0032  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0033  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0034  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0035  * POSSIBILITY OF SUCH DAMAGE.
0036  */
0037
0038 #ifdef HAVE_CONFIG_H
0039 #include "config.h"
0040 #endif
0041
0042 #include <rtems/score/heapimpl.h>
0043 #include <rtems/score/threaddispatch.h>
0044
0045 #ifndef HEAP_PROTECTION
0046   #define _Heap_Protection_determine_block_free( heap, block ) true
0047 #else
0048   static void _Heap_Protection_delay_block_free(
0049     Heap_Control *heap,
0050     Heap_Block *block
0051   )
0052   {
0053     uintptr_t *const pattern_begin = (uintptr_t *)
0054       _Heap_Alloc_area_of_block( block );
0055     uintptr_t *const pattern_end = (uintptr_t *)
0056       ((uintptr_t) block + _Heap_Block_size( block ) + HEAP_ALLOC_BONUS);
0057     uintptr_t const delayed_free_block_count =
0058       heap->Protection.delayed_free_block_count;
0059     uintptr_t *current = NULL;
0060
0061     block->Protection_begin.next_delayed_free_block = block;
0062     block->Protection_begin.task = _Thread_Get_executing();
0063
0064     if ( delayed_free_block_count > 0 ) {
0065       Heap_Block *const last = heap->Protection.last_delayed_free_block;
0066
0067       last->Protection_begin.next_delayed_free_block = block;
0068     } else {
0069       heap->Protection.first_delayed_free_block = block;
0070     }
0071     heap->Protection.last_delayed_free_block = block;
0072     heap->Protection.delayed_free_block_count = delayed_free_block_count + 1;
0073
0074     for ( current = pattern_begin; current != pattern_end; ++current ) {
0075       *current = HEAP_FREE_PATTERN;
0076     }
0077   }
0078
0079   static void _Heap_Protection_check_free_block(
0080     Heap_Control *heap,
0081     Heap_Block *block
0082   )
0083   {
0084     uintptr_t *const pattern_begin = (uintptr_t *)
0085       _Heap_Alloc_area_of_block( block );
0086     uintptr_t *const pattern_end = (uintptr_t *)
0087       ((uintptr_t) block + _Heap_Block_size( block ) + HEAP_ALLOC_BONUS);
0088     uintptr_t *current = NULL;
0089
0090     for ( current = pattern_begin; current != pattern_end; ++current ) {
0091       if ( *current != HEAP_FREE_PATTERN ) {
0092         _Heap_Protection_block_error( heap, block, HEAP_ERROR_FREE_PATTERN );
0093         break;
0094       }
0095     }
0096   }
0097
0098   static bool _Heap_Protection_determine_block_free(
0099     Heap_Control *heap,
0100     Heap_Block *block
0101   )
0102   {
0103     bool do_free = true;
0104     Heap_Block *const next = block->Protection_begin.next_delayed_free_block;
0105
0106     if ( next == NULL ) {
0107       _Heap_Protection_delay_block_free( heap, block );
0108       do_free = false;
0109     } else if ( next == HEAP_PROTECTION_OBOLUS ) {
0110       _Heap_Protection_check_free_block( heap, block );
0111     } else {
0112       _Heap_Protection_block_error( heap, block, HEAP_ERROR_DOUBLE_FREE );
0113     }
0114
0115     return do_free;
0116   }
0117 #endif
0118
0119 bool _Heap_Free( Heap_Control *heap, void *alloc_begin_ptr )
0120 {
0121   Heap_Statistics *const stats = &heap->stats;
0122   uintptr_t alloc_begin;
0123   Heap_Block *block;
0124   Heap_Block *next_block = NULL;
0125   uintptr_t block_size = 0;
0126   uintptr_t next_block_size = 0;
0127   bool next_is_free = false;
0128
0129   /*
0130    * If NULL return true so a free on NULL is considered a valid release. This
0131    * is a special case that could be handled by the in heap check how-ever that
0132    * would result in false being returned which is wrong.
0133    */
0134   if ( alloc_begin_ptr == NULL ) {
0135     return true;
0136   }
0137
0138   alloc_begin = (uintptr_t) alloc_begin_ptr;
0139   block = _Heap_Block_of_alloc_area( alloc_begin, heap->page_size );
0140
0141   if ( !_Heap_Is_block_in_heap( heap, block ) ) {
0142     return false;
0143   }
0144
0145   _Heap_Protection_block_check( heap, block );
0146
0147   block_size = _Heap_Block_size( block );
0148   next_block = _Heap_Block_at( block, block_size );
0149
0150   if ( !_Heap_Is_block_in_heap( heap, next_block ) ) {
0151     return false;
0152   }
0153
0154   _Heap_Protection_block_check( heap, next_block );
0155
0156   if ( !_Heap_Is_prev_used( next_block ) ) {
0157     _Heap_Protection_block_error( heap, block, HEAP_ERROR_BAD_USED_BLOCK );
0158     return false;
0159   }
0160
0161   if ( !_Heap_Protection_determine_block_free( heap, block ) ) {
0162     return true;
0163   }
0164
0165   next_block_size = _Heap_Block_size( next_block );
0166   next_is_free = next_block != heap->last_block
0167     && !_Heap_Is_prev_used( _Heap_Block_at( next_block, next_block_size ));
0168
0169   if ( !_Heap_Is_prev_used( block ) ) {
0170     uintptr_t const prev_size = block->prev_size;
0171     Heap_Block * const prev_block = _Heap_Block_at( block, -prev_size );
0172
0173     if ( !_Heap_Is_block_in_heap( heap, prev_block ) ) {
0174       _HAssert( false );
0175       return( false );
0176     }
0177
0178     /* As we always coalesce free blocks, the block that preceedes prev_block
0179        must have been used. */
0180     if ( !_Heap_Is_prev_used ( prev_block) ) {
0181       _HAssert( false );
0182       return( false );
0183     }
0184
0185     if ( next_is_free ) {       /* coalesce both */
0186       uintptr_t const size = block_size + prev_size + next_block_size;
0187       _Heap_Free_list_remove( next_block );
0188       stats->free_blocks -= 1;
0189       prev_block->size_and_flag = size | HEAP_PREV_BLOCK_USED;
0190       next_block = _Heap_Block_at( prev_block, size );
0191       _HAssert(!_Heap_Is_prev_used( next_block));
0192       next_block->prev_size = size;
0193     } else {                      /* coalesce prev */
0194       uintptr_t const size = block_size + prev_size;
0195       prev_block->size_and_flag = size | HEAP_PREV_BLOCK_USED;
0196       next_block->size_and_flag &= ~HEAP_PREV_BLOCK_USED;
0197       next_block->prev_size = size;
0198     }
0199   } else if ( next_is_free ) {    /* coalesce next */
0200     uintptr_t const size = block_size + next_block_size;
0201     _Heap_Free_list_replace( next_block, block );
0202     block->size_and_flag = size | HEAP_PREV_BLOCK_USED;
0203     next_block  = _Heap_Block_at( block, size );
0204     next_block->prev_size = size;
0205   } else {                        /* no coalesce */
0206     /* Add 'block' to the head of the free blocks list as it tends to
0207        produce less fragmentation than adding to the tail. */
0208     _Heap_Free_list_insert_after( _Heap_Free_list_head( heap), block );
0209     block->size_and_flag = block_size | HEAP_PREV_BLOCK_USED;
0210     next_block->size_and_flag &= ~HEAP_PREV_BLOCK_USED;
0211     next_block->prev_size = block_size;
0212
0213     /* Statistics */
0214     ++stats->free_blocks;
0215     if ( stats->max_free_blocks < stats->free_blocks ) {
0216       stats->max_free_blocks = stats->free_blocks;
0217     }
0218   }
0219
0220   /* Statistics */
0221   --stats->used_blocks;
0222   ++stats->frees;
0223   stats->free_size += block_size;
0224   stats->lifetime_freed += block_size;
0225
0226   return( true );
0227 }