2009-09-09 Sebastian Huber <Sebastian.Huber@embedded-brains.de>

	* score/include/rtems/score/heap.h, score/inline/rtems/score/heap.inl,
	score/src/heapallocate.c, score/src/heap.c, score/src/heapextend.c,
	score/src/heapresizeblock.c, score/src/heapwalk.c: Documenation.
	Simplified block resize. Improved heap walk. Changed heap layout to
	avoid a special case for _Heap_Is_used() and _Heap_Is_free().
	* libmisc/stackchk/check.c: Update for heap API changes.

1 files changed, 60 insertions, 130 deletions

diff --git a/cpukit/score/src/heapresizeblock.c b/cpukit/score/src/heapresizeblock.c
index 2f26589667..d684c84c26 100644
--- a/cpukit/score/src/heapresizeblock.c
+++ b/cpukit/score/src/heapresizeblock.c
@@ -10,6 +10,8 @@
  *  COPYRIGHT (c) 1989-1999.
  *  On-Line Applications Research Corporation (OAR).
  *
+ *  Copyright (c) 2009 embedded brains GmbH.
+ *
  *  The license and distribution terms for this file may be
  *  found in the file LICENSE in this distribution or at
  *  http://www.rtems.com/license/LICENSE.
@@ -25,165 +27,93 @@
 #include <rtems/score/sysstate.h>
 #include <rtems/score/heap.h>
 
-Heap_Resize_status _Heap_Resize_block(
+static Heap_Resize_status _Heap_Resize_block_checked(
   Heap_Control *heap,
-  void *alloc_begin_ptr,
+  Heap_Block *block,
+  uintptr_t alloc_begin,
   uintptr_t new_alloc_size,
   uintptr_t *old_size,
   uintptr_t *new_size
 )
 {
   Heap_Statistics *const stats = &heap->stats;
-  uintptr_t const min_block_size = heap->min_block_size;
-  uintptr_t const page_size = heap->page_size;
-  uintptr_t const alloc_begin = (uintptr_t) alloc_begin_ptr;
-  Heap_Block *const block = _Heap_Block_of_alloc_area( alloc_begin, page_size );
-  Heap_Block *next_block = NULL;
-  Heap_Block *next_next_block = NULL;
-  uintptr_t block_size = 0;
-  uintptr_t block_end = 0;
-  uintptr_t next_block_size = 0;
-  bool next_block_is_used = false;;
-  uintptr_t alloc_size = 0;
-  uintptr_t prev_block_used_flag = 0;
 
-  *old_size = 0;
-  *new_size = 0;
+  uintptr_t const block_begin = (uintptr_t) block;
+  uintptr_t block_size = _Heap_Block_size( block );
+  uintptr_t block_end = block_begin + block_size;
 
-  if ( !_Heap_Is_block_in_heap( heap, block ) ) {
-    return HEAP_RESIZE_FATAL_ERROR;
-  }
+  uintptr_t alloc_size = block_end - alloc_begin + HEAP_BLOCK_SIZE_OFFSET;
 
-  block_size = _Heap_Block_size( block );
-  block_end = (uintptr_t) block + block_size;
-  prev_block_used_flag = block->size_and_flag & HEAP_PREV_BLOCK_USED;
-  next_block = _Heap_Block_at( block, block_size );
+  Heap_Block *next_block = _Heap_Block_at( block, block_size );
+  uintptr_t next_block_size = _Heap_Block_size( next_block );
+  bool next_block_is_free = _Heap_Is_free( next_block );;
 
   _HAssert( _Heap_Is_block_in_heap( heap, next_block ) );
   _HAssert( _Heap_Is_prev_used( next_block ) );
 
-  next_block_size = _Heap_Block_size( next_block );
-  next_next_block = _Heap_Block_at( next_block, next_block_size );
-
-  _HAssert(
-    next_block == heap->last_block
-      || _Heap_Is_block_in_heap( heap, next_next_block )
-  );
-
-  next_block_is_used = next_block == heap->last_block
-    || _Heap_Is_prev_used( next_next_block );
-
-  alloc_size = block_end - alloc_begin + HEAP_BLOCK_SIZE_OFFSET;
-
   *old_size = alloc_size;
 
-  if ( new_alloc_size > alloc_size ) {
-    /*
-     * Need to extend the block: allocate part of the next block and then
-     * merge the blocks.
-     */
-    if ( next_block_is_used ) {
-      return HEAP_RESIZE_UNSATISFIED;
-    } else {
-      uintptr_t add_block_size =
-        _Heap_Align_up( new_alloc_size - alloc_size, page_size );
-
-      if ( add_block_size < min_block_size ) {
-        add_block_size = min_block_size;
-      }
-
-      if ( add_block_size > next_block_size ) {
-        return HEAP_RESIZE_UNSATISFIED;
-      }
-
-      next_block = _Heap_Block_allocate(
-        heap,
-        next_block,
-        _Heap_Alloc_area_of_block( next_block ),
-        add_block_size - HEAP_BLOCK_HEADER_SIZE
-      );
-
-      /* Merge the blocks */
-      block->size_and_flag = ( block_size + _Heap_Block_size( next_block ) )
-        | prev_block_used_flag;
-
-      /* Statistics */
-      --stats->used_blocks;
-    }
-  } else {
-    /* Calculate how much memory we could free */
-    uintptr_t free_block_size =
-      _Heap_Align_down( alloc_size - new_alloc_size, page_size );
-
-    if ( free_block_size > 0 ) {
-      /*
-       * To free some memory the block should be shortened so that it can can
-       * hold 'new_alloc_size' user bytes and still remain not shorter than
-       * 'min_block_size'. 
-       */
-      uintptr_t new_block_size = block_size - free_block_size;
-
-      if ( new_block_size < min_block_size ) {
-        uintptr_t const delta = min_block_size - new_block_size;
-
-        _HAssert( free_block_size >= delta );
+  if ( next_block_is_free ) {
+    block_size += next_block_size;
+    alloc_size += next_block_size;
+  }
 
-        free_block_size -= delta;
+  if ( new_alloc_size > alloc_size ) {
+    return HEAP_RESIZE_UNSATISFIED;
+  }
 
-        if ( free_block_size == 0 ) {
-          /* Statistics */
-          ++stats->resizes;
+  if ( next_block_is_free ) {
+    _Heap_Block_set_size( block, block_size );
 
-          return HEAP_RESIZE_SUCCESSFUL;
-        }
+    _Heap_Free_list_remove( next_block );
 
-        new_block_size += delta;
-      }
+    next_block = _Heap_Block_at( block, block_size );
+    next_block->size_and_flag |= HEAP_PREV_BLOCK_USED;
 
-      _HAssert( new_block_size >= min_block_size );
-      _HAssert( new_block_size + free_block_size == block_size );
-      _HAssert( _Heap_Is_aligned( new_block_size, page_size ) );
-      _HAssert( _Heap_Is_aligned( free_block_size, page_size ) );
+    /* Statistics */
+    --stats->free_blocks;
+    stats->free_size -= next_block_size;
+  }
 
-      if ( !next_block_is_used ) {
-        /* Extend the next block */
-        Heap_Block *const new_next_block =
-          _Heap_Block_at( block, new_block_size );
-        uintptr_t const new_next_block_size =
-          next_block_size + free_block_size;
+  block = _Heap_Block_allocate( heap, block, alloc_begin, new_alloc_size );
 
-        _HAssert( _Heap_Is_block_in_heap( heap, next_next_block ) );
+  block_size = _Heap_Block_size( block );
+  next_block = _Heap_Block_at( block, block_size );
+  *new_size = (uintptr_t) next_block - alloc_begin + HEAP_BLOCK_SIZE_OFFSET;
 
-        block->size_and_flag = new_block_size | prev_block_used_flag;
-        new_next_block->size_and_flag =
-          new_next_block_size | HEAP_PREV_BLOCK_USED;
-        next_next_block->prev_size = new_next_block_size;
+  /* Statistics */
+  ++stats->resizes;
 
-        _Heap_Free_list_replace( next_block, new_next_block );
+  return HEAP_RESIZE_SUCCESSFUL;
+}
 
-        *new_size = new_next_block_size - HEAP_BLOCK_SIZE_OFFSET;
+Heap_Resize_status _Heap_Resize_block(
+  Heap_Control *heap,
+  void *alloc_begin_ptr,
+  uintptr_t new_alloc_size,
+  uintptr_t *old_size,
+  uintptr_t *new_size
+)
+{
+  uintptr_t const page_size = heap->page_size;
 
-        /* Statistics */
-        stats->free_size += free_block_size;
-      } else if ( free_block_size >= min_block_size ) {
-        /* Split the block into two used parts, then free the second one */
-        block->size_and_flag = new_block_size | prev_block_used_flag;
-        next_block = _Heap_Block_at( block, new_block_size );
-        next_block->size_and_flag = free_block_size | HEAP_PREV_BLOCK_USED;
+  uintptr_t const alloc_begin = (uintptr_t) alloc_begin_ptr;
 
-        _Heap_Free( heap, (void *) _Heap_Alloc_area_of_block( next_block ) );
+  Heap_Block *const block = _Heap_Block_of_alloc_area( alloc_begin, page_size );
 
-        *new_size = free_block_size - HEAP_BLOCK_SIZE_OFFSET;
+  *old_size = 0;
+  *new_size = 0;
 
-        /* Statistics */
-        ++stats->used_blocks; /* We have created used block */
-        --stats->frees; /* Do not count next call in stats */
-      }
-    }
+  if ( _Heap_Is_block_in_heap( heap, block ) ) {
+    return _Heap_Resize_block_checked(
+      heap,
+      block,
+      alloc_begin,
+      new_alloc_size,
+      old_size,
+      new_size
+    );
+  } else {
+    return HEAP_RESIZE_FATAL_ERROR;
   }
-
-  /* Statistics */
-  ++stats->resizes;
-
-  return HEAP_RESIZE_SUCCESSFUL;
 }