2010-08-25 Sebastian Huber <sebastian.huber@embedded-brains.de>

	PR 1672/cpukit
	* score/include/rtems/score/heap.h, score/src/heap.c,
	score/src/heapallocate.c, score/src/heapextend.c,
	score/src/heapfree.c, score/src/heapresizeblock.c,
	score/src/heapsizeofuserarea.c: Added heap protection in case
	RTEMS_DEBUG is defined.

6 files changed, 242 insertions, 47 deletions

diff --git a/cpukit/score/src/heap.c b/cpukit/score/src/heap.c
index a0efe71cdd..afde241931 100644
--- a/cpukit/score/src/heap.c
+++ b/cpukit/score/src/heap.c
@@ -23,8 +23,11 @@
 #include "config.h"
 #endif
 
+#include <string.h>
+
 #include <rtems/system.h>
 #include <rtems/score/heap.h>
+#include <rtems/score/interr.h>
 
 #if CPU_ALIGNMENT == 0 || CPU_ALIGNMENT % 2 != 0
   #error "invalid CPU_ALIGNMENT value"
@@ -123,6 +126,46 @@ static uint32_t instance = 0;
  *
  */
 
+#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_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 );
+    }
+  }
+
+  static void _Heap_Protection_block_error_default(
+    Heap_Control *heap,
+    Heap_Block *block
+  )
+  {
+    /* FIXME */
+    _Internal_error_Occurred( 0xdeadbeef, false, 0xdeadbeef );
+  }
+#endif
+
 bool _Heap_Get_first_and_last_block(
   uintptr_t heap_area_begin,
   uintptr_t heap_area_size,
@@ -202,6 +245,14 @@ uintptr_t _Heap_Initialize(
     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;
@@ -211,6 +262,7 @@ uintptr_t _Heap_Initialize(
   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;
@@ -226,6 +278,7 @@ uintptr_t _Heap_Initialize(
   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;
@@ -233,12 +286,6 @@ uintptr_t _Heap_Initialize(
   stats->min_free_size = first_block_size;
   stats->free_blocks = 1;
   stats->max_free_blocks = 1;
-  stats->used_blocks = 0;
-  stats->max_search = 0;
-  stats->allocs = 0;
-  stats->searches = 0;
-  stats->frees = 0;
-  stats->resizes = 0;
   stats->instance = instance++;
 
   _HAssert( _Heap_Is_aligned( heap->page_size, CPU_ALIGNMENT ) );
@@ -253,7 +300,7 @@ uintptr_t _Heap_Initialize(
   return first_block_size;
 }
 
-void _Heap_Block_split(
+static void _Heap_Block_split(
   Heap_Control *heap,
   Heap_Block *block,
   Heap_Block *free_list_anchor,
@@ -272,13 +319,13 @@ void _Heap_Block_split(
     _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_BLOCK_SIZE_OFFSET - used_size;
-  uintptr_t const free_size_limit = min_block_size + HEAP_BLOCK_SIZE_OFFSET;
+  uintptr_t const free_size = block_size + HEAP_ALLOC_BONUS - used_size;
+  uintptr_t const free_size_limit = min_block_size + HEAP_ALLOC_BONUS;
 
   Heap_Block *next_block = _Heap_Block_at( block, block_size );
 
-  _HAssert( used_size <= block_size + HEAP_BLOCK_SIZE_OFFSET );
-  _HAssert( used_size + free_size == block_size + HEAP_BLOCK_SIZE_OFFSET );
+  _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 );
@@ -310,6 +357,8 @@ void _Heap_Block_split(
 
     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;
   }
@@ -434,5 +483,7 @@ Heap_Block *_Heap_Block_allocate(
     stats->min_free_size = stats->free_size;
   }
 
+  _Heap_Protection_block_initialize( heap, block );
+
   return block;
 }
diff --git a/cpukit/score/src/heapallocate.c b/cpukit/score/src/heapallocate.c
index a1c6810eb8..61cebc2054 100644
--- a/cpukit/score/src/heapallocate.c
+++ b/cpukit/score/src/heapallocate.c
@@ -27,6 +27,47 @@
 #include <rtems/score/sysstate.h>
 #include <rtems/score/heap.h>
 
+#ifndef HEAP_PROTECTION
+  #define _Heap_Protection_free_delayed_blocks( heap, alloc_begin ) false
+#else
+  static bool _Heap_Protection_free_delayed_blocks(
+    Heap_Control *heap,
+    uintptr_t alloc_begin
+  )
+  {
+    bool search_again = false;
+    uintptr_t const blocks_to_free_count =
+      (heap->Protection.delayed_free_block_count + 1) / 2;
+
+    if ( alloc_begin == 0 && blocks_to_free_count > 0 ) {
+      Heap_Block *block_to_free = heap->Protection.first_delayed_free_block;
+      uintptr_t count = 0;
+
+      for ( count = 0; count < blocks_to_free_count; ++count ) {
+        Heap_Block *next_block_to_free =
+          block_to_free->Protection_begin.next_delayed_free_block;
+
+        block_to_free->Protection_begin.next_delayed_free_block =
+          HEAP_PROTECTION_OBOLUS;
+
+        _Heap_Free(
+          heap,
+          (void *) _Heap_Alloc_area_of_block( block_to_free )
+        );
+
+        block_to_free = next_block_to_free;
+      }
+
+      heap->Protection.delayed_free_block_count -= blocks_to_free_count;
+      heap->Protection.first_delayed_free_block = block_to_free;
+
+      search_again = true;
+    }
+
+    return search_again;
+  }
+#endif
+
 #ifdef RTEMS_HEAP_DEBUG
   static void _Heap_Check_allocation(
     const Heap_Control *heap,
@@ -58,7 +99,7 @@
       _Heap_Is_aligned( block_size, page_size )
     );
 
-    _HAssert( alloc_end <= block_end + HEAP_BLOCK_SIZE_OFFSET );
+    _HAssert( alloc_end <= block_end + HEAP_ALLOC_BONUS );
     _HAssert( alloc_area_begin == block_begin + HEAP_BLOCK_HEADER_SIZE);
     _HAssert( alloc_area_offset < page_size );
 
@@ -99,7 +140,7 @@ static uintptr_t _Heap_Check_block(
   uintptr_t const alloc_begin_ceiling = block_end - min_block_size
     + HEAP_BLOCK_HEADER_SIZE + page_size - 1;
 
-  uintptr_t alloc_end = block_end + HEAP_BLOCK_SIZE_OFFSET;
+  uintptr_t alloc_end = block_end + HEAP_ALLOC_BONUS;
   uintptr_t alloc_begin = alloc_end - alloc_size;
 
   alloc_begin = _Heap_Align_down( alloc_begin, alignment );
@@ -149,13 +190,13 @@ void *_Heap_Allocate_aligned_with_boundary(
 )
 {
   Heap_Statistics *const stats = &heap->stats;
-  Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
-  Heap_Block *block = _Heap_Free_list_first( heap );
   uintptr_t const block_size_floor = alloc_size + HEAP_BLOCK_HEADER_SIZE
-    - HEAP_BLOCK_SIZE_OFFSET;
+    - HEAP_ALLOC_BONUS;
   uintptr_t const page_size = heap->page_size;
+  Heap_Block *block = NULL;
   uintptr_t alloc_begin = 0;
   uint32_t search_count = 0;
+  bool search_again = false;
 
   if ( block_size_floor < alloc_size ) {
     /* Integer overflow occured */
@@ -172,40 +213,50 @@ void *_Heap_Allocate_aligned_with_boundary(
     }
   }
 
-  while ( block != free_list_tail ) {
-    _HAssert( _Heap_Is_prev_used( block ) );
+  do {
+    Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
+
+    block = _Heap_Free_list_first( heap );
+    while ( block != free_list_tail ) {
+      _HAssert( _Heap_Is_prev_used( block ) );
+
+      _Heap_Protection_block_check( heap, block );
+
+      /*
+       * The HEAP_PREV_BLOCK_USED flag is always set in the block size_and_flag
+       * field.  Thus the value is about one unit larger than the real block
+       * size.  The greater than operator takes this into account.
+       */
+      if ( block->size_and_flag > block_size_floor ) {
+        if ( alignment == 0 ) {
+          alloc_begin = _Heap_Alloc_area_of_block( block );
+        } else {
+          alloc_begin = _Heap_Check_block(
+            heap,
+            block,
+            alloc_size,
+            alignment,
+            boundary
+          );
+        }
+      }
+
+      /* Statistics */
+      ++search_count;
 
-    /* Statistics */
-    ++search_count;
-
-    /*
-     * The HEAP_PREV_BLOCK_USED flag is always set in the block size_and_flag
-     * field.  Thus the value is about one unit larger than the real block
-     * size.  The greater than operator takes this into account.
-     */
-    if ( block->size_and_flag > block_size_floor ) {
-      if ( alignment == 0 ) {
-        alloc_begin = _Heap_Alloc_area_of_block( block );
-      } else {
-        alloc_begin = _Heap_Check_block(
-          heap,
-          block,
-          alloc_size,
-          alignment,
-          boundary
-        );
+      if ( alloc_begin != 0 ) {
+        break;
       }
-    }
 
-    if ( alloc_begin != 0 ) {
-      break;
+      block = block->next;
     }
 
-    block = block->next;
-  }
+    search_again = _Heap_Protection_free_delayed_blocks( heap, alloc_begin );
+  } while ( search_again );
 
   if ( alloc_begin != 0 ) {
     /* Statistics */
+    ++stats->allocs;
     stats->searches += search_count;
 
     block = _Heap_Block_allocate( heap, block, alloc_begin, alloc_size );
diff --git a/cpukit/score/src/heapextend.c b/cpukit/score/src/heapextend.c
index c928e53f73..eab2a9482d 100644
--- a/cpukit/score/src/heapextend.c
+++ b/cpukit/score/src/heapextend.c
@@ -194,9 +194,11 @@ bool _Heap_Extend(
   extend_first_block->prev_size = extend_area_end;
   extend_first_block->size_and_flag =
     extend_first_block_size | HEAP_PREV_BLOCK_USED;
+  _Heap_Protection_block_initialize( heap, extend_first_block );
 
   extend_last_block->prev_size = extend_first_block_size;
   extend_last_block->size_and_flag = 0;
+  _Heap_Protection_block_initialize( heap, extend_last_block );
 
   if ( (uintptr_t) extend_first_block < (uintptr_t) heap->first_block ) {
     heap->first_block = extend_first_block;
diff --git a/cpukit/score/src/heapfree.c b/cpukit/score/src/heapfree.c
index 48b54293ea..27e853d5bb 100644
--- a/cpukit/score/src/heapfree.c
+++ b/cpukit/score/src/heapfree.c
@@ -22,9 +22,89 @@
 #endif
 
 #include <rtems/system.h>
-#include <rtems/score/sysstate.h>
 #include <rtems/score/heap.h>
 
+#ifndef HEAP_PROTECTION
+  #define _Heap_Protection_determine_block_free( heap, block ) true
+#else
+  static void _Heap_Protection_delay_block_free(
+    Heap_Control *heap,
+    Heap_Block *block
+  )
+  {
+    uintptr_t *const pattern_begin = (uintptr_t *)
+      _Heap_Alloc_area_of_block( block );
+    uintptr_t *const pattern_end = (uintptr_t *)
+      ((uintptr_t) block + _Heap_Block_size( block ) + HEAP_ALLOC_BONUS);
+    uintptr_t const delayed_free_block_count = 
+      heap->Protection.delayed_free_block_count;
+    uintptr_t *current = NULL;
+
+    block->Protection_begin.next_delayed_free_block = block;
+    block->Protection_begin.task = _Thread_Executing;
+
+    if ( delayed_free_block_count > 0 ) {
+      Heap_Block *const last = heap->Protection.last_delayed_free_block;
+      
+      last->Protection_begin.next_delayed_free_block = block;
+    } else {
+      heap->Protection.first_delayed_free_block = block;
+    }
+    heap->Protection.last_delayed_free_block = block;
+    heap->Protection.delayed_free_block_count = delayed_free_block_count + 1;
+
+    for ( current = pattern_begin; current != pattern_end; ++current ) {
+      *current = HEAP_FREE_PATTERN;
+    }
+  }
+
+  static void _Heap_Protection_check_free_block(
+    Heap_Control *heap,
+    Heap_Block *block
+  )
+  {
+    uintptr_t *const pattern_begin = (uintptr_t *)
+      _Heap_Alloc_area_of_block( block );
+    uintptr_t *const pattern_end = (uintptr_t *)
+      ((uintptr_t) block + _Heap_Block_size( block ) + HEAP_ALLOC_BONUS);
+    uintptr_t *current = NULL;
+
+    for ( current = pattern_begin; current != pattern_end; ++current ) {
+      if ( *current != HEAP_FREE_PATTERN ) {
+        _Heap_Protection_block_error( heap, block );
+        break;
+      }
+    }
+  }
+
+  static bool _Heap_Protection_determine_block_free(
+    Heap_Control *heap,
+    Heap_Block *block
+  )
+  {
+    bool do_free = true;
+
+    /*
+     * Sometimes after a free the allocated area is still in use.  An example
+     * is the task stack of a thread that deletes itself.  The thread dispatch
+     * disable level is a way to detect this use case.
+     */
+    if ( _Thread_Dispatch_disable_level == 0 ) {
+      Heap_Block *const next = block->Protection_begin.next_delayed_free_block;
+      if ( next == NULL ) {
+        _Heap_Protection_delay_block_free( heap, block );
+        do_free = false;
+      } else if ( next == HEAP_PROTECTION_OBOLUS ) {
+        _Heap_Protection_check_free_block( heap, block );
+      } else {
+        _Heap_Protection_block_error( heap, block );
+      }
+    }
+
+    return do_free;
+  }
+#endif
+
 bool _Heap_Free( Heap_Control *heap, void *alloc_begin_ptr )
 {
   Heap_Statistics *const stats = &heap->stats;
@@ -36,6 +116,8 @@ bool _Heap_Free( Heap_Control *heap, void *alloc_begin_ptr )
   uintptr_t next_block_size = 0;
   bool next_is_free = false;
 
+  _Heap_Protection_block_check( heap, block );
+
   if ( !_Heap_Is_block_in_heap( heap, block ) ) {
     return false;
   }
@@ -43,16 +125,23 @@ bool _Heap_Free( Heap_Control *heap, void *alloc_begin_ptr )
   block_size = _Heap_Block_size( block );
   next_block = _Heap_Block_at( block, block_size );
 
+  _Heap_Protection_block_check( heap, next_block );
+
   if ( !_Heap_Is_block_in_heap( heap, next_block ) ) {
     _HAssert( false );
     return false;
   }
 
   if ( !_Heap_Is_prev_used( next_block ) ) {
-    _HAssert( false );
+    _Heap_Protection_block_error( heap, block );
+
     return false;
   }
 
+  if ( !_Heap_Protection_determine_block_free( heap, block ) ) {
+    return true;
+  }
+
   next_block_size = _Heap_Block_size( next_block );
   next_is_free = next_block != heap->last_block
     && !_Heap_Is_prev_used( _Heap_Block_at( next_block, next_block_size ));
diff --git a/cpukit/score/src/heapresizeblock.c b/cpukit/score/src/heapresizeblock.c
index d684c84c26..152418fc71 100644
--- a/cpukit/score/src/heapresizeblock.c
+++ b/cpukit/score/src/heapresizeblock.c
@@ -42,7 +42,7 @@ static Heap_Resize_status _Heap_Resize_block_checked(
   uintptr_t block_size = _Heap_Block_size( block );
   uintptr_t block_end = block_begin + block_size;
 
-  uintptr_t alloc_size = block_end - alloc_begin + HEAP_BLOCK_SIZE_OFFSET;
+  uintptr_t alloc_size = block_end - alloc_begin + HEAP_ALLOC_BONUS;
 
   Heap_Block *next_block = _Heap_Block_at( block, block_size );
   uintptr_t next_block_size = _Heap_Block_size( next_block );
@@ -79,7 +79,7 @@ static Heap_Resize_status _Heap_Resize_block_checked(
 
   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;
+  *new_size = (uintptr_t) next_block - alloc_begin + HEAP_ALLOC_BONUS;
 
   /* Statistics */
   ++stats->resizes;
@@ -104,6 +104,8 @@ Heap_Resize_status _Heap_Resize_block(
   *old_size = 0;
   *new_size = 0;
 
+  _Heap_Protection_block_check( heap, block );
+
   if ( _Heap_Is_block_in_heap( heap, block ) ) {
     return _Heap_Resize_block_checked(
       heap,
diff --git a/cpukit/score/src/heapsizeofuserarea.c b/cpukit/score/src/heapsizeofuserarea.c
index 7c297a77e6..0a8b150811 100644
--- a/cpukit/score/src/heapsizeofuserarea.c
+++ b/cpukit/score/src/heapsizeofuserarea.c
@@ -51,7 +51,7 @@ bool _Heap_Size_of_alloc_area(
     return false;
   }
 
-  *alloc_size = (uintptr_t) next_block + HEAP_BLOCK_SIZE_OFFSET - alloc_begin;
+  *alloc_size = (uintptr_t) next_block + HEAP_ALLOC_BONUS - alloc_begin;
 
   return true;
 }