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, 189 insertions, 25 deletions

diff --git a/cpukit/score/src/heapallocate.c b/cpukit/score/src/heapallocate.c
index 7c9e78f31e..7b0f51e232 100644
--- a/cpukit/score/src/heapallocate.c
+++ b/cpukit/score/src/heapallocate.c
@@ -1,9 +1,17 @@
-/*
- *  Heap Handler
+/**
+ * @file
+ *
+ * @ingroup ScoreHeap
  *
+ * @brief Heap Handler implementation.
+ */
+
+/*
  *  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.
@@ -19,48 +27,204 @@
 #include <rtems/score/sysstate.h>
 #include <rtems/score/heap.h>
 
-void *_Heap_Allocate( Heap_Control *heap, uintptr_t size )
+#ifdef RTEMS_HEAP_DEBUG
+  static void _Heap_Check_allocation(
+    const Heap_Control *heap,
+    const Heap_Block *block,
+    uintptr_t alloc_begin,
+    uintptr_t alloc_size,
+    uintptr_t alignment,
+    uintptr_t boundary
+  )
+  {
+    uintptr_t const min_block_size = heap->min_block_size;
+    uintptr_t const page_size = heap->page_size;
+
+    uintptr_t const block_begin = (uintptr_t) block;
+    uintptr_t const block_size = _Heap_Block_size( block );
+    uintptr_t const block_end = block_begin + block_size;
+
+    uintptr_t const alloc_end = alloc_begin + alloc_size;
+
+    uintptr_t const alloc_area_begin = _Heap_Alloc_area_of_block( block );
+    uintptr_t const alloc_area_offset = alloc_begin - alloc_area_begin;
+    uintptr_t const alloc_area_size = alloc_area_offset + alloc_size;
+
+    _HAssert( block_size >= min_block_size );
+    _HAssert( block_begin < block_end );
+    _HAssert(
+      _Heap_Is_aligned( block_begin + HEAP_BLOCK_HEADER_SIZE, page_size )
+    );
+    _HAssert(
+      _Heap_Is_aligned( block_size, page_size )
+    );
+
+    _HAssert( alloc_end <= block_end + HEAP_BLOCK_SIZE_OFFSET );
+    _HAssert( alloc_area_begin == block_begin + HEAP_BLOCK_HEADER_SIZE);
+    _HAssert( alloc_area_offset < page_size );
+
+    _HAssert( _Heap_Is_aligned( alloc_area_begin, page_size ) );
+    if ( alignment == 0 ) {
+      _HAssert( alloc_begin == alloc_area_begin );
+    } else {
+      _HAssert( _Heap_Is_aligned( alloc_begin, alignment ) );
+    }
+
+    if ( boundary != 0 ) {
+      uintptr_t boundary_line = _Heap_Align_down( alloc_end, boundary );
+
+      _HAssert( alloc_size <= boundary );
+      _HAssert( boundary_line <= alloc_begin || alloc_end <= boundary_line );
+    }
+  }
+#else
+  #define _Heap_Check_allocation( h, b, ab, as, ag, bd ) ((void) 0)
+#endif
+
+static uintptr_t _Heap_Check_block(
+  const Heap_Control *heap,
+  const Heap_Block *block,
+  uintptr_t alloc_size,
+  uintptr_t alignment,
+  uintptr_t boundary
+)
+{
+  uintptr_t const page_size = heap->page_size;
+  uintptr_t const min_block_size = heap->min_block_size;
+
+  uintptr_t const block_begin = (uintptr_t) block;
+  uintptr_t const block_size = _Heap_Block_size( block );
+  uintptr_t const block_end = block_begin + block_size;
+
+  uintptr_t const alloc_begin_floor = _Heap_Alloc_area_of_block( 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_begin = alloc_end - alloc_size;
+
+  alloc_begin = _Heap_Align_down( alloc_begin, alignment );
+
+  /* Ensure that the we have a valid new block at the end */
+  if ( alloc_begin > alloc_begin_ceiling ) {
+    alloc_begin = _Heap_Align_down( alloc_begin_ceiling, alignment );
+  }
+
+  alloc_end = alloc_begin + alloc_size;
+
+  /* Ensure boundary constaint */
+  if ( boundary != 0 ) {
+    uintptr_t const boundary_floor = alloc_begin_floor + alloc_size;
+    uintptr_t boundary_line = _Heap_Align_down( alloc_end, boundary );
+
+    while ( alloc_begin < boundary_line && boundary_line < alloc_end ) {
+      if ( boundary_line < boundary_floor ) {
+        return 0;
+      }
+      alloc_begin = boundary_line - alloc_size;
+      alloc_begin = _Heap_Align_down( alloc_begin, alignment );
+      alloc_end = alloc_begin + alloc_size;
+      boundary_line = _Heap_Align_down( alloc_end, boundary );
+    }
+  }
+
+  /* Ensure that the we have a valid new block at the beginning */
+  if ( alloc_begin >= alloc_begin_floor ) {
+    uintptr_t const alloc_block_begin =
+      (uintptr_t) _Heap_Block_of_alloc_area( alloc_begin, page_size );
+    uintptr_t const free_size = alloc_block_begin - block_begin;
+
+    if ( free_size >= min_block_size || free_size == 0 ) {
+      return alloc_begin;
+    }
+  }
+
+  return 0;
+}
+
+void *_Heap_Allocate_aligned_with_boundary(
+  Heap_Control *heap,
+  uintptr_t alloc_size,
+  uintptr_t alignment,
+  uintptr_t boundary
+)
 {
   Heap_Statistics *const stats = &heap->stats;
-  Heap_Block * const tail = _Heap_Free_list_tail( heap );
-  Heap_Block *block = _Heap_First_free_block( heap );
+  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;
+  uintptr_t const page_size = heap->page_size;
+  uintptr_t alloc_begin = 0;
   uint32_t search_count = 0;
-  void *alloc_area_begin_ptr = NULL;
 
-  size = _Heap_Calc_block_size( size, heap->page_size, heap->min_block_size );
-  if( size == 0 ) {
+  if ( block_size_floor < alloc_size ) {
+    /* Integer overflow occured */
     return NULL;
   }
 
-  /*
-   * Find large enough free block.
-   *
-   * Do not bother to mask out the HEAP_PREV_BLOCK_USED bit as it will not
-   * change the result of the size comparison.
-   */
-  while (block != tail && block->size_and_flag < size) {
-    _HAssert( _Heap_Is_prev_used( block ));
+  if ( boundary != 0 ) {
+    if ( boundary < alloc_size ) {
+      return NULL;
+    }
 
-    block = block->next;
-    ++search_count;
+    if ( alignment == 0 ) {
+      alignment = page_size;
+    }
   }
 
-  if (block != tail) {
-    _Heap_Block_allocate( heap, block, size );
+  while ( block != free_list_tail ) {
+    _HAssert( _Heap_Is_prev_used( block ) );
+
+    /* 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;
+    }
+
+    block = block->next;
+  }
 
-    alloc_area_begin_ptr = (void *) _Heap_Alloc_area_of_block( block );
+  if ( alloc_begin != 0 ) {
+    block = _Heap_Block_allocate( heap, block, alloc_begin, alloc_size );
 
-    _HAssert( _Heap_Is_aligned( (uintptr_t) alloc_area_begin_ptr, heap->page_size ));
+    _Heap_Check_allocation(
+      heap,
+      block,
+      alloc_begin,
+      alloc_size,
+      alignment,
+      boundary
+    );
 
     /* Statistics */
-    ++stats->allocs;
     stats->searches += search_count;
   }
 
   /* Statistics */
-  if (stats->max_search < search_count) {
+  if ( stats->max_search < search_count ) {
     stats->max_search = search_count;
   }
 
-  return alloc_area_begin_ptr;
+  return (void *) alloc_begin;
 }