source: rtems/cpukit/score/src/heapfree.c @ 80f2885b

4.104.114.84.95
Last change on this file since 80f2885b was 80f2885b, checked in by Joel Sherrill <joel.sherrill@…>, on 05/20/05 at 19:15:41

2005-05-14 Sergei Organov <osv@…>

PR 746/rtems
Optimize realloc(). The problem is that realloc() can neither grow
nor shrink efficiently the current memory region without support
from underlying heap/region modules. The patch introduces one new
routine for each of heap and region modules, _Heap_Resize_block(),
and rtems_region_resize_segment(), respectively, and uses the
latter to optimize realloc().

The implementation of _Heap_Resize_block() lead to changing of the
heap allocation strategy: now the heap manager, when splits larger
free block into used and new free parts, makes the first part of
the block used, not the last one as it was before. Due to this new
strategy, _Heap_Resize_block() never needs to change the user
pointer.

Caveat: unlike previous heap implementation, first few bytes of
the contents of the memory allocated from the heap are now almost
never all zero. This can trigger bugs in client code that have not
been visible before this patch.

  • libcsupport/src/malloc.c (realloc): try to resize segment in place using new rtems_region_resize_segment() routine before falling back to the malloc()/free() method.
  • score/src/heap.c: (_Heap_Initialize): change initial heap layout to reflect new allocation strategy of using of the lower part of a previously free block when splitting it for the purpose of allocation. (_Heap_Block_allocate): when split, make the lower part used, and leave the upper part free. Return type changed from Heap_Block* to uint32_t.
  • score/include/rtems/score/heap.h: (Heap_Statistics): added 'resizes' field. (Heap_Resize_status): new enum. (_Heap_Resize_block): new routine. (_Heap_Block_allocate): return type changed from Heap_Block* to uint32_t.
  • score/src/heapwalk.c: reflect new heap layout in checks.
  • score/src/heapsizeofuserarea.c: more assertions added.
  • score/src/heapresizeblock.c: new file. (_Heap_Resize_block): new routine.
  • score/src/heapfree.c: reverse the checks _Heap_Is_block_in() and _Heap_Is_prev_used() on entry to be in this order.
  • score/src/heapallocate.c, score/src/heapallocatealigned.c: ignore return value of _Heap_Block_allocate().
  • score/Makefile.am (HEAP_C_FILES): added src/heapresizeblock.c.
  • rtems/include/rtems/rtems/region.h: (rtems_region_resize_segment): new interface routine. (_Region_Process_queue): new internal routine called from rtems_region_resize_segment() and rtems_region_return_segment().
  • rtems/src/regionreturnsegment.c: move queue management code into the new internal routine _Region_Process_queue() and call it.
  • rtems/src/regionresizesegment.c: new file. (rtems_region_resize_segment): new interface routine.
  • rtems/src/regionprocessqueue.c: new file. (_Region_Process_queue): new internal routine containing queue management code factored out from 'regionreturnsegment.c'.
  • rtems/Makefile.am (REGION_C_FILES): Added src/regionresizesegment.c, and src/regionprocessqueue.c.
  • ada/rtems.adb, ada/rtems.ads: Added Region_Resize_Segment.
  • Property mode set to 100644
File size: 3.8 KB
Line 
1/*
2 *  Heap Handler
3 *
4 *  COPYRIGHT (c) 1989-1999.
5 *  On-Line Applications Research Corporation (OAR).
6 *
7 *  The license and distribution terms for this file may be
8 *  found in the file LICENSE in this distribution or at
9 *  http://www.rtems.com/license/LICENSE.
10 *
11 *  $Id$
12 */
13
14#if HAVE_CONFIG_H
15#include "config.h"
16#endif
17
18#include <rtems/system.h>
19#include <rtems/score/sysstate.h>
20#include <rtems/score/heap.h>
21
22/*PAGE
23 *
24 *  _Heap_Free
25 *
26 *  This kernel routine returns the memory designated by the
27 *  given heap and given starting address to the memory pool.
28 *
29 *  Input parameters:
30 *    the_heap         - pointer to heap header
31 *    starting_address - starting address of the memory block to free.
32 *
33 *  Output parameters:
34 *    TRUE  - if starting_address is valid heap address
35 *    FALSE - if starting_address is invalid heap address
36 */
37
38boolean _Heap_Free(
39  Heap_Control        *the_heap,
40  void                *starting_address
41)
42{
43  Heap_Block        *the_block;
44  Heap_Block        *next_block;
45  uint32_t         the_size;
46  uint32_t         next_size;
47  Heap_Statistics *const stats = &the_heap->stats;
48  boolean            next_is_free;
49
50  _Heap_Start_of_block( the_heap, starting_address, &the_block );
51
52  if ( !_Heap_Is_block_in( the_heap, the_block ) ) {
53    _HAssert(starting_address == NULL);
54    _HAssert(FALSE);
55    return( FALSE );
56  }
57
58  the_size = _Heap_Block_size( the_block );
59  next_block = _Heap_Block_at( the_block, the_size );
60
61  if ( !_Heap_Is_block_in( the_heap, next_block ) ) {
62    _HAssert(FALSE);
63    return( FALSE );
64  }
65
66  if ( !_Heap_Is_prev_used( next_block ) ) {
67    _HAssert(FALSE);
68    return( FALSE );
69  }
70
71  next_size = _Heap_Block_size( next_block );
72  next_is_free = next_block < the_heap->final &&
73    !_Heap_Is_prev_used(_Heap_Block_at(next_block, next_size));
74
75  if ( !_Heap_Is_prev_used( the_block ) ) {
76    uint32_t const prev_size = the_block->prev_size;
77    Heap_Block *const prev_block = _Heap_Block_at( the_block, -prev_size );
78
79    if ( !_Heap_Is_block_in( the_heap, prev_block ) ) {
80      _HAssert(FALSE);
81      return( FALSE );
82    }
83
84    /* As we always coalesce free blocks, the block that preceedes prev_block
85       must have been used. */
86    if ( !_Heap_Is_prev_used ( prev_block) ) {
87      _HAssert(FALSE);
88      return( FALSE );
89    }
90
91    if ( next_is_free ) {       /* coalesce both */
92      uint32_t const size = the_size + prev_size + next_size;
93      _Heap_Block_remove( next_block );
94      stats->free_blocks -= 1;
95      prev_block->size = size | HEAP_PREV_USED;
96      next_block = _Heap_Block_at( prev_block, size );
97      _HAssert(!_Heap_Is_prev_used( next_block));
98      next_block->prev_size = size;
99    }
100    else {                      /* coalesce prev */
101      uint32_t const size = the_size + prev_size;
102      prev_block->size = size | HEAP_PREV_USED;
103      next_block->size &= ~HEAP_PREV_USED;
104      next_block->prev_size = size;
105    }
106  }
107  else if ( next_is_free ) {    /* coalesce next */
108    uint32_t const size = the_size + next_size;
109    _Heap_Block_replace( next_block, the_block );
110    the_block->size = size | HEAP_PREV_USED;
111    next_block  = _Heap_Block_at( the_block, size );
112    next_block->prev_size = size;
113  }
114  else {                        /* no coalesce */
115    /* Add 'the_block' to the head of the free blocks list as it tends to
116       produce less fragmentation than adding to the tail. */
117    _Heap_Block_insert_after( _Heap_Head( the_heap), the_block );
118    the_block->size = the_size | HEAP_PREV_USED;
119    next_block->size &= ~HEAP_PREV_USED;
120    next_block->prev_size = the_size;
121
122    stats->free_blocks += 1;
123    if ( stats->max_free_blocks < stats->free_blocks )
124      stats->max_free_blocks = stats->free_blocks;
125  }
126
127  stats->used_blocks -= 1;
128  stats->free_size += the_size;
129  stats->frees += 1;
130
131  return( TRUE );
132}
Note: See TracBrowser for help on using the repository browser.