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

	* libcsupport/src/free.c, libmisc/stackchk/check.c,
	rtems/include/rtems/rtems/region.h, rtems/src/regioncreate.c,
	rtems/src/regionextend.c, rtems/src/regiongetinfo.c,
	rtems/src/regiongetsegment.c, rtems/src/regiongetsegmentsize.c,
	rtems/src/regionresizesegment.c, score/src/pheapallocate.c,
	score/src/pheapallocatealigned.c, score/src/pheapextend.c,
	score/src/pheapfree.c, score/src/pheapgetblocksize.c,
	score/src/pheapgetfreeinfo.c, score/src/pheapgetinfo.c,
	score/src/pheapgetsize.c, score/src/pheapinit.c,
	score/src/pheapresizeblock.c, score/src/pheapwalk.c:
	Update for heap API changes.
	* score/include/rtems/score/apimutex.h,
	score/include/rtems/score/object.h: Documentation.
	* score/include/rtems/score/heap.h,
	score/include/rtems/score/protectedheap.h,
	score/inline/rtems/score/heap.inl, score/src/heap.c,
	score/src/heapallocate.c, score/src/heapallocatealigned.c,
	score/src/heapextend.c, score/src/heapfree.c,
	score/src/heapgetfreeinfo.c, score/src/heapgetinfo.c,
	score/src/heapresizeblock.c, score/src/heapsizeofuserarea.c,
	score/src/heapwalk.c: Overall cleanup. Added boundary constraint to
	allocation function. More changes follow.

1 files changed, 418 insertions, 163 deletions

diff --git a/cpukit/score/src/heapwalk.c b/cpukit/score/src/heapwalk.c
index a6628df0b3..dd255e1a17 100644
--- a/cpukit/score/src/heapwalk.c
+++ b/cpukit/score/src/heapwalk.c
@@ -1,8 +1,14 @@
-/*
- *  Heap Handler
+/**
+ * @file
  *
- *  COPYRIGHT (c) 1989-2007.
- *  On-Line Applications Research Corporation (OAR).
+ * @ingroup ScoreHeap
+ *
+ * @brief Heap Handler implementation.
+ */
+
+/*
+ *  COPYRIGHT ( c ) 1989-2007.
+ *  On-Line Applications Research Corporation ( OAR ).
  *
  *  The license and distribution terms for this file may be
  *  found in the file LICENSE in this distribution or at
@@ -22,197 +28,446 @@
 #include <rtems/score/interr.h>
 #include <rtems/bspIo.h>
 
-#if defined(__GNUC__)
-  #define DO_NOT_INLINE __attribute__((__noinline__))
-#else
-  #define DO_NOT_INLINE
-#endif
-/*
- *  Helper to avoid introducing even more branches and paths in this
- *  code to do coverage analysis on.
- *
- *  We do not want this inlined.
- */
-static void hw_nl( 
-  int    error,
-  bool   do_dump
-) DO_NOT_INLINE;
+static void _Heap_Walk_printk( int source, bool dump, bool error, const char *fmt, ... )
+{
+  if ( dump ) {
+    va_list ap;
 
-/*PAGE
- *
- *  _Heap_Walk
- *
- *  This kernel routine walks the heap and verifies its correctness.
- *
- *  Input parameters:
- *    the_heap  - pointer to heap header
- *    source    - a numeric indicator of the invoker of this routine
- *    do_dump   - when true print the information
- *
- *  Output parameters: NONE
- */
+    if ( error ) {
+      printk( "FAIL[%d]: ", source );
+    } else {
+      printk( "PASS[%d]: ", source );
+    }
 
-bool _Heap_Walk(
-  Heap_Control  *the_heap,
-  int            source,
-  bool           do_dump
+    va_start( ap, fmt );
+    vprintk( fmt, ap );
+    va_end( ap );
+  }
+}
+
+static bool _Heap_Walk_check_free_list(
+  int source,
+  bool dump,
+  Heap_Control *heap
 )
 {
-  Heap_Block *the_block = the_heap->start;
-  Heap_Block *const end = the_heap->final;
-  Heap_Block *const tail = _Heap_Free_list_tail(the_heap);
-  int error = 0;
-  int passes = 0;
-
-  /* FIXME: Why is this disabled? */
-  do_dump = false;
-
-  /* FIXME: Why is this disabled? */
-  /*
-   * We don't want to allow walking the heap until we have
-   * transferred control to the user task so we watch the
-   * system state.
-   */
+  const Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
+  const Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
+  const Heap_Block *free_block = first_free_block;
+  uintptr_t const page_size = heap->page_size;
+  uintptr_t const loop_limit =
+    ((uintptr_t) heap->last_block - (uintptr_t) heap->first_block)
+      / heap->min_block_size;
+  uintptr_t loop_counter = 0;
 
-/*
-  if ( !_System_state_Is_up( _System_state_Get() ) )
-    return true;
-*/
+  while ( free_block != free_list_tail && loop_counter < loop_limit ) {
+    if ( !_Heap_Is_block_in_heap( heap, free_block ) ) {
+      _Heap_Walk_printk(
+        source,
+        dump,
+        true,
+        "free block 0x%08x: not in heap\n",
+        free_block
+      );
 
-  /* FIXME: Reason for this? */
-  if (source < 0)
-    source = (int) the_heap->stats.instance;
+      return false;
+    }
+
+    if (
+      !_Heap_Is_aligned( _Heap_Alloc_area_of_block( free_block ), page_size )
+    ) {
+      _Heap_Walk_printk(
+        source,
+        dump,
+        true,
+        "free block 0x%08x: alloc area not page aligned\n",
+        free_block
+      );
 
-  if (do_dump)
-    printk("\nPASS: %d start %p final %p first %p last %p begin %p end %p\n",
-      source, the_block, end,
-      _Heap_First_free_block(the_heap), _Heap_Last_free_block(the_heap),
-      the_heap->begin, the_heap->end);
+      return false;
+    }
 
-  /*
-   * Handle the 1st block
-   */
+    ++loop_counter;
 
-  if (!_Heap_Is_prev_used(the_block)) {
-    printk("PASS: %d !HEAP_PREV_BLOCK_USED flag of 1st block isn't set\n", source);
-    error = 1;
+    free_block = free_block->next;
   }
 
-  if (the_block->prev_size != the_heap->page_size) {
-    printk("PASS: %d !prev_size of 1st block isn't page_size\n", source);
-    error = 1;
+  if ( loop_counter >= loop_limit ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "free list contains a loop\n"
+    );
+
+    return false;
   }
 
-  while ( the_block != end ) {
-    uint32_t const the_size = _Heap_Block_size(the_block);
-    Heap_Block *const next_block = _Heap_Block_at(the_block, the_size);
-    bool    prev_used = _Heap_Is_prev_used(the_block);
+  return true;
+}
 
-    if (do_dump) {
-      printk("PASS: %d block %p size %d(%c)",
-        source, the_block, the_size, (prev_used ? 'U' : 'F'));
-      if (prev_used)
-        printk(" prev_size %d", the_block->prev_size);
-      else
-        printk(" (prev_size) %d", the_block->prev_size);
+static bool _Heap_Walk_is_in_free_list(
+  Heap_Control *heap,
+  Heap_Block *block
+)
+{
+  const Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
+  const Heap_Block *free_block = _Heap_Free_list_first( heap );
+
+  while ( free_block != free_list_tail ) {
+    if ( free_block == block ) {
+      return true;
     }
+    free_block = free_block->next;
+  }
 
+  return false;
+}
 
-    if (!_Addresses_Is_aligned(next_block) ) {
-      printk("PASS: %d next_block %p is not aligned\n", source, next_block);
-      error = 1;
-      break;
-    }
-   
-    if (!_Heap_Is_prev_used(next_block)) {
-      if (do_dump)
-        printk( " prev %p next %p", the_block->prev, the_block->next);
-      if (_Heap_Block_size(the_block) != next_block->prev_size) {
-        if (do_dump) printk("\n");
-        printk("PASS: %d !front and back sizes don't match", source);
-        error = 1;
-      }
-      if (!prev_used) {
-        
-        hw_nl(do_dump, error);
-        printk("PASS: %d !two consecutive blocks are free", source);
-        error = 1;
-      }
+static bool _Heap_Walk_check_control(
+  int source,
+  bool dump,
+  Heap_Control *heap
+)
+{
+  uintptr_t const page_size = heap->page_size;
+  uintptr_t const min_block_size = heap->min_block_size;
+  Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
+  Heap_Block *const free_list_head = _Heap_Free_list_head( heap );
+  Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
+  Heap_Block *const last_free_block = _Heap_Free_list_last( heap );
+  Heap_Block *const first_block = heap->first_block;
+  Heap_Block *const last_block = heap->last_block;
 
-      { /* Check if 'the_block' is in the free block list */
-        Heap_Block* block = _Heap_First_free_block(the_heap);
-        if (!_Addresses_Is_aligned(block) ) {
-          printk(
-            "PASS: %d first free block %p is not aligned\n", source, block);
-          error = 1;
-          break;
-        }
-        while(block != the_block && block != tail) {
-          if (!_Addresses_Is_aligned(block) ) {
-            printk(
-              "PASS: %d a free block %p is not aligned\n", source, block);
-            error = 1;
-            break;
-          }
-          if (!_Heap_Is_block_in_heap(the_heap, block)) {
-            printk("PASS: %d a free block %p is not in heap\n", source, block);
-            error = 1;
-            break;
-          }
-          block = block->next;
-        }
-        if (block != the_block) {
-          hw_nl(do_dump, error);
-          printk("PASS: %d !the_block not in the free list", source);
-          error = 1;
-        }
-      }
+  _Heap_Walk_printk(
+    source,
+    dump,
+    false,
+    "page size %u, min block size %u\n"
+      "\tarea begin 0x%08x, area end 0x%08x\n"
+      "\tfirst block 0x%08x, last block 0x%08x\n"
+      "\tfirst free 0x%08x, last free 0x%08x\n",
+    page_size, min_block_size,
+    heap->area_begin, heap->area_end,
+    first_block, last_block,
+    first_free_block, last_free_block
+  );
 
-    }
-    hw_nl(do_dump, error);
+  if ( page_size == 0 ) {
+    _Heap_Walk_printk( source, dump, true, "page size is zero\n" );
 
-    if (the_size < the_heap->min_block_size) {
-      printk("PASS: %d !block size is too small\n", source);
-      error = 1;
-      break;
-    }
-    if (!_Heap_Is_aligned( the_size, the_heap->page_size)) {
-      printk("PASS: %d !block size is misaligned\n", source);
-      error = 1;
-    }
+    return false;
+  }
 
-    if (++passes > (do_dump ? 10 : 0) && error)
-      break;
+  if ( !_Addresses_Is_aligned( (void *) page_size ) ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "page size %u not CPU aligned\n",
+      page_size
+    );
 
-    the_block = next_block;
+    return false;
   }
 
-  if (the_block != end) {
-    printk("PASS: %d !last block address isn't equal to 'final' %p %p\n",
-      source, the_block, end);
-    error = 1;
+  if ( !_Heap_Is_aligned( min_block_size, page_size ) ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "min block size %u not page aligned\n",
+      min_block_size
+    );
+
+    return false;
   }
 
-  if (_Heap_Block_size(the_block) != the_heap->page_size) {
-    printk("PASS: %d !last block's size isn't page_size (%d != %d)\n", source,
-           _Heap_Block_size(the_block), the_heap->page_size);
-    error = 1;
+  if (
+    first_free_block != free_list_head
+      && !_Addresses_Is_aligned( first_free_block )
+  ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "first free block: 0x%08x not CPU aligned\n",
+      first_free_block
+    );
+
+    return false;
   }
 
-  if (do_dump && error)
-    _Internal_error_Occurred( INTERNAL_ERROR_CORE, true, 0xffff0000 );
+  if (
+    last_free_block != free_list_tail
+      && !_Addresses_Is_aligned( last_free_block )
+  ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "last free block: 0x%08x not CPU aligned\n",
+      last_free_block
+    );
+    
+    return false;
+  }
 
-  return error;
+  if (
+    !_Heap_Is_aligned( _Heap_Alloc_area_of_block( first_block ), page_size )
+  ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "first block: 0x%08x not page aligned\n",
+      first_block
+    );
 
+    return false;
+  }
+
+  if (
+    !_Heap_Is_aligned( _Heap_Alloc_area_of_block( last_block ), page_size )
+  ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "last block: 0x%08x not page aligned\n",
+      last_block
+    );
+
+    return false;
+  }
+
+  if ( !_Heap_Is_prev_used( first_block ) ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "first block: HEAP_PREV_BLOCK_USED is cleared\n"
+    );
+  }
+
+  if ( first_block->prev_size != page_size ) {
+    _Heap_Walk_printk(
+      source,
+      dump,
+      true,
+      "first block: prev size %u != page size %u\n",
+      first_block->prev_size,
+      page_size
+    );
+  }
+
+  return _Heap_Walk_check_free_list( source, dump, heap );
 }
 
-/*
- *  This method exists to simplify branch paths in the generated code above.
- */
-static void hw_nl( 
-  int            error,
-  bool           do_dump
+bool _Heap_Walk(
+  Heap_Control *heap,
+  int source,
+  bool dump
 )
 {
-  if (do_dump || error) printk("\n");
+  uintptr_t const page_size = heap->page_size;
+  uintptr_t const min_block_size = heap->min_block_size;
+  Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
+  Heap_Block *const free_list_head = _Heap_Free_list_head( heap );
+  Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
+  Heap_Block *const last_free_block = _Heap_Free_list_last( heap );
+  Heap_Block *const last_block = heap->last_block;
+  Heap_Block *block = heap->first_block;
+  bool error = false;
+
+  if ( !_System_state_Is_up( _System_state_Get() ) ) {
+    return true;
+  }
+
+  if ( !_Heap_Walk_check_control( source, dump, heap ) ) {
+    return false;
+  }
+
+  while ( block != last_block && _Addresses_Is_aligned( block ) ) {
+    uintptr_t const block_begin = (uintptr_t) block;
+    uintptr_t const block_size = _Heap_Block_size( block );
+    bool const prev_used = _Heap_Is_prev_used( block );
+    Heap_Block *const next_block = _Heap_Block_at( block, block_size );
+    uintptr_t const next_block_begin = (uintptr_t) next_block;
+
+    if ( prev_used ) {
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: size %u\n",
+        block,
+        block_size
+      );
+    } else {
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: size %u, prev_size %u\n",
+        block,
+        block_size,
+        block->prev_size
+      );
+    }
+
+    if (
+      !_Heap_Is_aligned( block_begin + HEAP_BLOCK_HEADER_SIZE, page_size )
+    ) {
+      error = true;
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: not page (%u) aligned\n",
+        block,
+        page_size
+      );
+      break;
+    }
+
+    if ( !_Heap_Is_aligned( block_size, page_size ) ) {
+      error = true;
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: block size %u not page (%u) aligned\n",
+        block,
+        block_size,
+        page_size
+      );
+      break;
+    }
+
+    if ( block_size < min_block_size ) {
+      error = true;
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: size %u < min block size %u\n",
+        block,
+        block_size,
+        min_block_size
+      );
+      break;
+    }
+
+    if ( next_block_begin <= block_begin ) {
+      error = true;
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: next block 0x%08x is not a successor\n",
+        block,
+        next_block
+      );
+      break;
+    }
+   
+    if ( !_Heap_Is_prev_used( next_block ) ) {
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "block 0x%08x: prev 0x%08x%s, next 0x%08x%s\n",
+        block,
+        block->prev,
+        block->prev == first_free_block ?
+          " (= first)"
+            : (block->prev == free_list_head ? " (= head)" : ""),
+        block->next,
+        block->next == last_free_block ?
+          " (= last)"
+            : (block->next == free_list_tail ? " (= tail)" : "")
+      );
+
+      if ( block_size != next_block->prev_size ) {
+        error = true;
+        _Heap_Walk_printk(
+          source,
+          dump,
+          error,
+          "block 0x%08x: size %u != size %u (in next block 0x%08x)\n",
+          block,
+          block_size,
+          next_block->prev_size,
+          next_block
+        );
+      }
+
+      if ( !prev_used ) {
+        error = true;
+        _Heap_Walk_printk(
+          source,
+          dump,
+          error,
+          "block 0x%08x: two consecutive blocks are free\n",
+          block
+        );
+      }
+
+      if ( !_Heap_Walk_is_in_free_list( heap, block ) ) {
+        error = true;
+        _Heap_Walk_printk(
+          source,
+          dump,
+          error,
+          "block 0x%08x: free block not in free list\n",
+          block
+        );
+      }
+    }
+
+    block = next_block;
+  }
+
+  if ( !_Addresses_Is_aligned( block ) ) {
+    error = true;
+    _Heap_Walk_printk(
+      source,
+      dump,
+      error,
+      "block 0x%08x: not CPU aligned\n",
+      block
+    );
+
+    return false;
+  }
+
+  if ( block == last_block ) {
+    uintptr_t const block_size = _Heap_Block_size( block );
+
+    if ( block_size != page_size ) {
+      error = true;
+      _Heap_Walk_printk(
+        source,
+        dump,
+        error,
+        "last block 0x%08x: size %u != page size %u\n",
+        block,
+        block_size,
+        page_size
+      );
+    }
+  } else {
+    error = true;
+    _Heap_Walk_printk(
+      source,
+      dump,
+      error,
+      "last block 0x%08x != last block 0x%08x\n",
+      block,
+      last_block
+    );
+  }
+
+  return !error;
 }