2005-01-20 Sergei Organov <osv@topconrd.ru>

	PR 536/rtems
	Heap manager re-implementation to consume less memory and still satisfy
	alignment requirements.
	
	* score/src/heap.c, score/src/heapallocate.c, score/src/heapextend.c,
	score/src/heapfree.c, score/src/heapgetinfo.c,
	score/src/heapgetfreeinfo.c, core/src/heapsizeofuserarea.c,
	score/src/heapwalk.c, core/macros/rtems/score/heap.inl,
	score/inline/rtems/score/heap.inl,
	score/include/rtems/score/heap.h: Reimplemented.
	* score/src/heapallocatealigned.c: new file
	* score/Makefile.am: HEAP_C_FILES: add score/src/heapallocatealigned.c

1 files changed, 96 insertions, 72 deletions

diff --git a/cpukit/score/src/heapwalk.c b/cpukit/score/src/heapwalk.c
index 4f93ae7be0..a589b3cdf4 100644
--- a/cpukit/score/src/heapwalk.c
+++ b/cpukit/score/src/heapwalk.c
@@ -30,32 +30,32 @@
  *  Output parameters: NONE
  */
 
-#ifndef RTEMS_DEBUG
+#if !defined(RTEMS_HEAP_DEBUG)
 
-void _Heap_Walk(
+boolean _Heap_Walk(
   Heap_Control  *the_heap,
   int            source,
   boolean        do_dump
 )
 {
+  return TRUE;
 }
 
-#else
+#else /* defined(RTEMS_HEAP_DEBUG) */
 
 #include <stdio.h>
-#include <unistd.h>
 
-void _Heap_Walk(
+boolean _Heap_Walk(
   Heap_Control  *the_heap,
   int            source,
   boolean        do_dump
 )
 {
-  Heap_Block *the_block  = 0;  /* avoid warnings */
-  Heap_Block *next_block = 0;  /* avoid warnings */
-  int         notdone = 1;
-  int         error = 0;
-  int         passes = 0;
+  Heap_Block *the_block = the_heap->start;
+  Heap_Block *const end = the_heap->final;
+  Heap_Block *const tail = _Heap_Tail(the_heap);
+  int error = 0;
+  int passes = 0;
 
   /*
    * We don't want to allow walking the heap until we have
@@ -64,86 +64,110 @@ void _Heap_Walk(
    */
 
   if ( !_System_state_Is_up( _System_state_Get() ) )
-    return;
+    return FALSE;
 
-  the_block = the_heap->start;
+  if (source < 0)
+    source = the_heap->stats.instance;
 
-  if (do_dump == TRUE) {
-    printf("\nPASS: %d  start @ 0x%p   final 0x%p,   first 0x%p  last 0x%p\n",
-            source, the_heap->start, the_heap->final,
-                  the_heap->first, the_heap->last
-          );
-  }
+  if (do_dump == TRUE)
+    printf("\nPASS: %d start %p final %p first %p last %p begin %p end %p\n",
+      source, the_block, end,
+      _Heap_First(the_heap), _Heap_Last(the_heap),
+      the_heap->begin, the_heap->end);
 
   /*
    * Handle the 1st block
    */
 
-  if (the_block->back_flag != HEAP_DUMMY_FLAG) {
-    printf("PASS: %d  Back flag of 1st block isn't HEAP_DUMMY_FLAG\n", source);
+  if (!_Heap_Is_prev_used(the_block)) {
+    printf("PASS: %d !HEAP_PREV_USED flag of 1st block isn't set\n", source);
     error = 1;
   }
 
-  while (notdone) {
-    passes++;
-    if (error && (passes > 10))
-        abort();
-
-    if (do_dump == TRUE) {
-      printf("PASS: %d  Block @ 0x%p   Back %d,   Front %d",
-              source, the_block,
-              the_block->back_flag, the_block->front_flag);
-      if ( _Heap_Is_block_free(the_block) ) {
-        printf( "      Prev 0x%p,   Next 0x%p\n",
-                          the_block->previous, the_block->next);
-      } else {
-        printf("\n");
-      }
+  if (the_block->prev_size != HEAP_PREV_USED) {
+    printf("PASS: %d !prev_size of 1st block isn't HEAP_PREV_USED\n", source);
+    error = 1;
+  }
+
+  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);
+    boolean prev_used = _Heap_Is_prev_used(the_block);
+
+    if (do_dump) {
+      printf("PASS: %d block %p size %d(%c)",
+        source, the_block, the_size, (prev_used ? 'U' : 'F'));
+      if (prev_used)
+        printf(" prev_size %d", the_block->prev_size);
+      else
+        printf(" (prev_size) %d", the_block->prev_size);
     }
 
-    /*
-     * Handle the last block
-     */
+    if (!_Heap_Is_block_in(the_heap, next_block)) {
+      if (do_dump) printf("\n");
+      printf("PASS: %d !block %p is out of heap\n", source, next_block);
+      error = 1;
+      break;
+    }
 
-    if ( the_block->front_flag != HEAP_DUMMY_FLAG ) {
-      next_block = _Heap_Next_block(the_block);
-      if ( the_block->front_flag != next_block->back_flag ) {
+    if (!_Heap_Is_prev_used(next_block)) {
+      if (do_dump)
+        printf( " prev %p next %p", the_block->prev, the_block->next);
+      if (_Heap_Block_size(the_block) != next_block->prev_size) {
+        if (do_dump) printf("\n");
+        printf("PASS: %d !front and back sizes don't match", source);
         error = 1;
-        printf("PASS: %d  Front and back flags don't match\n", source);
-        printf("         Current Block (%p):  Back - %d,  Front - %d",
-               the_block, the_block->back_flag, the_block->front_flag);
-        if (do_dump == TRUE) {
-          if (_Heap_Is_block_free(the_block)) {
-            printf("      Prev 0x%p,   Next 0x%p\n",
-                   the_block->previous, the_block->next);
-          } else {
-            printf("\n");
-          }
-        } else {
-          printf("\n");
-        }
-        printf("         Next Block (%p):     Back - %d,  Front - %d",
-               next_block, next_block->back_flag, next_block->front_flag);
-        if (do_dump == TRUE) {
-          if (_Heap_Is_block_free(next_block)) {
-            printf("      Prev 0x%p,   Next 0x%p\n",
-                   the_block->previous, the_block->next);
-          } else {
-            printf("\n");
-          }
-        } else {
-          printf("\n");
+      }
+      if (!prev_used) {
+        if (do_dump || error) printf("\n");
+        printf("PASS: %d !two consecutive blocks are free", source);
+        error = 1;
+      }
+
+      { /* Check if 'the_block' is in the free block list */
+        Heap_Block* block = _Heap_First(the_heap);
+        while(block != the_block && block != tail)
+          block = block->next;
+        if(block != the_block) {
+          if (do_dump || error) printf("\n");
+          printf("PASS: %d !the_block not in the free list", source);
+          error = 1;
         }
       }
+
     }
+    if (do_dump || error) printf("\n");
 
-    if (the_block->front_flag == HEAP_DUMMY_FLAG)
-      notdone = 0;
-    else
-      the_block = next_block;
+    if (the_size < the_heap->min_block_size) {
+      printf("PASS: %d !block size is too small\n", source);
+      error = 1;
+      break;
+    }
+    if (!_Heap_Is_aligned( the_size, the_heap->page_size)) {
+      printf("PASS: %d !block size is misaligned\n", source);
+      error = 1;
+    }
+
+    if (++passes > (do_dump ? 10 : 0) && error)
+      break;
+
+    the_block = next_block;
+  }
+
+  if (the_block != end) {
+    printf("PASS: %d !last block address isn't equal to 'final'\n", source);
+    error = 1;
+  }
+
+  if (_Heap_Block_size(the_block) != 0) {
+    printf("PASS: %d !last block's size isn't 0\n", source);
+    error = 1;
   }
 
-  if (error)
-      abort();
+  if(do_dump && error)
+    abort();
+
+  return error == 0;
+
 }
-#endif
+#endif  /* defined(RTEMS_HEAP_DEBUG) */