2005-05-14 Sergei Organov <osv@topconrd.ru>

	PR 746/rtems
	Optimize realloc(). The problem is that realloc() can neither grow
	nor shrink efficiently the current memory region without support
	from underlying heap/region modules. The patch introduces one new
	routine for each of heap and region modules, _Heap_Resize_block(),
	and rtems_region_resize_segment(), respectively, and uses the
	latter to optimize realloc().

	The implementation of _Heap_Resize_block() lead to changing of the
	heap allocation strategy: now the heap manager, when splits larger
	free block into used and new free parts, makes the first part of
	the block used, not the last one as it was before. Due to this new
	strategy, _Heap_Resize_block() never needs to change the user
	pointer.

	Caveat: unlike previous heap implementation, first few bytes of
	the contents of the memory allocated from the heap are now almost
	never all zero. This can trigger bugs in client code that have not
	been visible before this patch.

	* libcsupport/src/malloc.c (realloc): try to resize segment in
	place using new rtems_region_resize_segment() routine before
	falling back to the malloc()/free() method.
	* score/src/heap.c:
	(_Heap_Initialize): change initial heap layout to reflect new
	allocation strategy of using of the lower part of a previously
	free block when splitting it for the purpose of allocation.
	(_Heap_Block_allocate): when split, make the lower part used, and
	leave the upper part free. Return type changed from Heap_Block* to
	uint32_t.
	* score/include/rtems/score/heap.h:
	(Heap_Statistics): added 'resizes' field.
	(Heap_Resize_status): new enum.
	(_Heap_Resize_block): new routine.
	(_Heap_Block_allocate): return type changed from Heap_Block* to
	uint32_t.
	* score/src/heapwalk.c: reflect new heap layout in checks.
	* score/src/heapsizeofuserarea.c: more assertions added.
	* score/src/heapresizeblock.c: new file.
	(_Heap_Resize_block): new routine.
	* score/src/heapfree.c: reverse the checks _Heap_Is_block_in() and
	_Heap_Is_prev_used() on entry to be in this order.
	* score/src/heapallocate.c, score/src/heapallocatealigned.c:
	ignore return value of _Heap_Block_allocate().
	* score/Makefile.am (HEAP_C_FILES): added src/heapresizeblock.c.
	* rtems/include/rtems/rtems/region.h:
	(rtems_region_resize_segment): new interface routine.
	(_Region_Process_queue): new internal routine called from
	rtems_region_resize_segment() and rtems_region_return_segment().
	* rtems/src/regionreturnsegment.c: move queue management code into
	the new internal routine _Region_Process_queue() and call it.

	* rtems/src/regionresizesegment.c: new file.
	(rtems_region_resize_segment): new interface routine.
	* rtems/src/regionprocessqueue.c: new file.
	(_Region_Process_queue): new internal routine containing queue
	management code factored out from 'regionreturnsegment.c'.
	* rtems/Makefile.am (REGION_C_FILES): Added
	src/regionresizesegment.c, and src/regionprocessqueue.c.
	* ada/rtems.adb, ada/rtems.ads: Added Region_Resize_Segment.

5 files changed, 219 insertions, 36 deletions

diff --git a/cpukit/rtems/Makefile.am b/cpukit/rtems/Makefile.am
index 947cb1a338..9486bedefb 100644
--- a/cpukit/rtems/Makefile.am
+++ b/cpukit/rtems/Makefile.am
@@ -105,7 +105,8 @@ SIGNAL_C_FILES = src/signal.c src/signalcatch.c src/signalsend.c
 REGION_C_FILES = src/region.c src/regioncreate.c src/regiondelete.c \
     src/regionextend.c src/regiongetsegment.c src/regiongetsegmentsize.c \
     src/regionident.c src/regionreturnsegment.c src/regiongetinfo.c \
-    src/regiongetfreeinfo.c
+    src/regiongetfreeinfo.c src/regionresizesegment.c \
+    src/regionprocessqueue.c
 
 PARTITION_C_FILES = src/part.c src/partcreate.c src/partdelete.c \
     src/partgetbuffer.c src/partident.c src/partreturnbuffer.c
diff --git a/cpukit/rtems/include/rtems/rtems/region.h b/cpukit/rtems/include/rtems/rtems/region.h
index a27dd7879b..9c8a0cffa9 100644
--- a/cpukit/rtems/include/rtems/rtems/region.h
+++ b/cpukit/rtems/include/rtems/rtems/region.h
@@ -232,8 +232,39 @@ rtems_status_code rtems_region_return_segment(
   void       *segment
 );
 
+/*
+ *  rtems_region_resize_segment
+ *
+ *  DESCRIPTION:
+ *
+ *  This routine implements the rtems_region_resize_segment directive.  It
+ *  tries to resize segment in the region associated with 'id' to the new size
+ *  'size' in place. The first 'size' or old size bytes of the segment
+ *  (whatever is less) are guaranteed to remain unmodified. The segment must
+ *  have been previously allocated from the same region.  If resizing the
+ *  segment results in enough memory being available to satisfy the
+ *  rtems_region_get_segment of the first blocked task, then that task and as
+ *  many subsequent tasks as possible will be unblocked with their requests
+ *  satisfied.
+ *  Returns:
+ *    RTEMS_SUCCESSFUL  - operation successful
+ *    RTEMS_UNSATISFIED - the segment can't be resized in place
+ *    any other code    - failure.
+ *  On RTEMS_SUCCESSFUL or RTEMS_UNSATISFIED exit it returns into the
+ *  'old_size' the old size in bytes of the user memory area of the specified
+ *  segment.
+ */
+
+rtems_status_code rtems_region_resize_segment(
+  Objects_Id  id,
+  void       *segment,
+  size_t      size,
+  size_t     *old_size
+);
+
 #ifndef __RTEMS_APPLICATION__
 #include <rtems/rtems/region.inl>
+extern void _Region_Process_queue(Region_Control *the_region);
 #endif
 #if defined(RTEMS_MULTIPROCESSING)
 #include <rtems/rtems/regionmp.h>
diff --git a/cpukit/rtems/src/regionprocessqueue.c b/cpukit/rtems/src/regionprocessqueue.c
new file mode 100644
index 0000000000..6fdb216989
--- /dev/null
+++ b/cpukit/rtems/src/regionprocessqueue.c
@@ -0,0 +1,83 @@
+/*
+ *  Region Manager
+ *
+ *
+ *  COPYRIGHT (c) 1989-1999.
+ *  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
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#include <rtems/system.h>
+#include <rtems/rtems/status.h>
+#include <rtems/rtems/support.h>
+#include <rtems/score/object.h>
+#include <rtems/rtems/options.h>
+#include <rtems/rtems/region.h>
+#include <rtems/score/states.h>
+#include <rtems/score/thread.h>
+#include <rtems/score/apimutex.h>
+
+/*PAGE
+ *
+ *  _Region_Process_queue
+ *
+ *  If enough memory is available to satisfy the rtems_region_get_segment of
+ *  the first blocked task, then that task and as many subsequent tasks as
+ *  possible will be unblocked with their requests satisfied.
+ *
+ *  Input parameters:
+ *    the_region - the region
+ *
+ *  Output parameters:
+ *    none
+ */
+
+void _Region_Process_queue(
+  Region_Control *the_region
+)
+{
+  Thread_Control *the_thread;
+  void           *the_segment;
+  /*
+   *  Switch from using the memory allocation mutex to using a
+   *  dispatching disabled critical section.  We have to do this
+   *  because this thread may unblock one or more threads that were
+   *  waiting on memory.  
+   *
+   *  NOTE: Be sure to disable dispatching before unlocking the mutex
+   *        since we do not want to open a window where a context 
+   *        switch could occur.
+   */
+  _Thread_Disable_dispatch();
+  _RTEMS_Unlock_allocator();
+
+  /*
+   *  NOTE: The following loop is O(n) where n is the number of
+   *        threads whose memory request is satisfied.
+   */
+  for ( ; ; ) {
+    the_thread = _Thread_queue_First( &the_region->Wait_queue );
+
+    if ( the_thread == NULL )
+      break;
+
+    the_segment = (void **) _Region_Allocate_segment(
+      the_region,
+      the_thread->Wait.count
+    );
+
+    if ( the_segment == NULL )
+      break;
+
+    *(void **)the_thread->Wait.return_argument = the_segment;
+    the_region->number_of_used_blocks += 1;
+    _Thread_queue_Extract( &the_region->Wait_queue, the_thread );
+    the_thread->Wait.return_code = RTEMS_SUCCESSFUL;
+  }
+  _Thread_Enable_dispatch();
+}
diff --git a/cpukit/rtems/src/regionresizesegment.c b/cpukit/rtems/src/regionresizesegment.c
new file mode 100644
index 0000000000..b83ed2c6e6
--- /dev/null
+++ b/cpukit/rtems/src/regionresizesegment.c
@@ -0,0 +1,101 @@
+/*
+ *  Region Manager
+ *
+ *
+ *  COPYRIGHT (c) 1989-1999.
+ *  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
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/rtems/status.h>
+#include <rtems/rtems/support.h>
+#include <rtems/score/object.h>
+#include <rtems/rtems/options.h>
+#include <rtems/rtems/region.h>
+#include <rtems/score/states.h>
+#include <rtems/score/thread.h>
+#include <rtems/score/apimutex.h>
+
+/*PAGE
+ *
+ *  rtems_region_resize_segment
+ *
+ *  This directive will try to resize segment to the new size 'size'
+ *  "in place".
+ *
+ *  Input parameters:
+ *    id      - region id
+ *    segment - pointer to segment address
+ *    size    - new required size
+ *
+ *  Output parameters:
+ *    RTEMS_SUCCESSFUL - if successful
+ *    error code       - if unsuccessful
+ */
+
+rtems_status_code rtems_region_resize_segment(
+  Objects_Id  id,
+  void       *segment,
+  size_t      size,
+  size_t     *old_size
+)
+{
+  register Region_Control *the_region;
+  Objects_Locations        location;
+  Heap_Resize_status       status;
+  uint32_t                 avail_size;
+  uint32_t                 osize;
+
+  if ( !old_size )
+    return RTEMS_INVALID_ADDRESS;
+
+  _RTEMS_Lock_allocator();
+  the_region = _Region_Get( id, &location );
+  switch ( location ) {
+
+    case OBJECTS_REMOTE:        /* this error cannot be returned */
+      _RTEMS_Unlock_allocator();
+      return RTEMS_INTERNAL_ERROR;
+
+    case OBJECTS_ERROR:
+      _RTEMS_Unlock_allocator();
+      return RTEMS_INVALID_ID;
+
+    case OBJECTS_LOCAL:
+
+      _Region_Debug_Walk( the_region, 7 );
+
+      status = _Heap_Resize_block(
+        &the_region->Memory,
+        segment,
+        (uint32_t) size,
+        &osize,
+        &avail_size
+      );
+      *old_size = (uint32_t) osize;
+
+      _Region_Debug_Walk( the_region, 8 );
+
+      if( status == HEAP_RESIZE_SUCCESSFUL && avail_size > 0 )
+        _Region_Process_queue( the_region ); /* unlocks allocator internally */
+      else
+        _RTEMS_Unlock_allocator();
+
+      return
+        (status == HEAP_RESIZE_SUCCESSFUL) ?  RTEMS_SUCCESSFUL :
+        (status == HEAP_RESIZE_UNSATISFIED) ? RTEMS_UNSATISFIED :
+        RTEMS_INVALID_ADDRESS;
+  }
+
+  return RTEMS_INTERNAL_ERROR;   /* unreached - only to remove warnings */
+}
diff --git a/cpukit/rtems/src/regionreturnsegment.c b/cpukit/rtems/src/regionreturnsegment.c
index ad8037fe6b..dc080e5ed5 100644
--- a/cpukit/rtems/src/regionreturnsegment.c
+++ b/cpukit/rtems/src/regionreturnsegment.c
@@ -55,9 +55,7 @@ rtems_status_code rtems_region_return_segment(
 )
 {
   register Region_Control *the_region;
-  Thread_Control          *the_thread;
   Objects_Locations        location;
-  void                   **the_segment;
 #ifdef RTEMS_REGION_FREE_SHRED_PATTERN
   uint32_t                 size;
 #endif
@@ -81,7 +79,7 @@ rtems_status_code rtems_region_return_segment(
 
 #ifdef RTEMS_REGION_FREE_SHRED_PATTERN
       if ( _Heap_Size_of_user_area( &the_region->Memory, segment, &size ) ) {
-        memset(segment, (RTEMS_REGION_FREE_SHRED_PATTERN & 0xFF), size);
+        memset( segment, (RTEMS_REGION_FREE_SHRED_PATTERN & 0xFF), size );
       } else {
         _RTEMS_Unlock_allocator();
         return RTEMS_INVALID_ADDRESS;
@@ -99,38 +97,7 @@ rtems_status_code rtems_region_return_segment(
 
       the_region->number_of_used_blocks -= 1;
 
-      /*
-       *  Switch from using the memory allocation mutex to using a
-       *  dispatching disabled critical section.  We have to do this
-       *  because this thread may unblock one or more threads that were
-       *  waiting on memory.
-       *
-       *  NOTE: The following loop is O(n) where n is the number of
-       *        threads whose memory request is satisfied.
-       */
-      _RTEMS_Unlock_allocator();
-      _Thread_Disable_dispatch();
-
-      for ( ; ; ) {
-        the_thread = _Thread_queue_First( &the_region->Wait_queue );
-
-        if ( the_thread == NULL )
-           break;
-
-        the_segment = (void **) _Region_Allocate_segment(
-           the_region,
-           the_thread->Wait.count
-        );
-
-        if ( the_segment == NULL )
-           break;
-
-        *(void **)the_thread->Wait.return_argument = the_segment;
-        the_region->number_of_used_blocks += 1;
-        _Thread_queue_Extract( &the_region->Wait_queue, the_thread );
-        the_thread->Wait.return_code = RTEMS_SUCCESSFUL;
-      }
-      _Thread_Enable_dispatch();
+      _Region_Process_queue(the_region); /* unlocks allocator internally */
 
       return RTEMS_SUCCESSFUL;
   }