PATCH:libgcc/frame.c malloc failures

[Nathan Sidwell <nathan at acm dot org>]

Hi,

Yonks ago I provided a large patch to fix some problems with exception
handling in low memory situations. That has atrophied in the meantime,
so I'm resubmitting it in smaller, more easily digestible, pieces, for
the appropriate maintainer to look at.

So, here's a patch for frame.c which currently attempts to malloc two
large arrays to order the FDE lists. The list of objects to search
during unwinding is chained off OBJECTS, in `struct object' records.
frame_init is responsible for
locating the range of pc values an object occupies, and generating the
ordered FDE table. The patch modifies its behaviour so that it can be
called multiple times, and can cope with not generating an ordered FDE
table. If an FDE table has been allocated then ob->fde_array will be
non-NULL and different to ob->fde_begin. find_fde is modified to check
for this condition. If the target pc is found to be within such an
object, a linear search of the unordered FDE's is done, via new
function search_fdes. (An attempt is made to sort the FDE's in case
more memory is available now.)

start_fde_sort is modified to return a flag indicating that space is
available to create the sorted FDE table. This allows frame_init to
avoid wasting time on subsequent failed inits of an object.

ok?

nathan
-- 
Dr Nathan Sidwell :: Computer Science Department :: Bristol University
Never hand someone a gun unless you are sure where they will point it
nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk
1999-11-29  Nathan Sidwell  <nathan@acm.org>

	* frame.c (start_fde_sort): Only allocate erratic array, if
	linear one was. Return allocated flag.
	(fde_insert): Only insert, if there's a valid array.
	(fde_end_sort): Split, sort and merge if linear and erratic
	arrays exist, else just sort linear one.
	(search_fdes): New function. Linear search through original fde
	structure.
	(frame_init): Permit multiple initializations. Cope with
	memory shortages.
	(find_fde): Fallback on linear search, if failed to sort array.
	(__deregister_frame_info): Only free sorted array, if we
	allocated it.

Index: frame.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/frame.c,v
retrieving revision 1.26
diff -c -3 -p -r1.26 frame.c
*** frame.c	1999/10/05 19:41:35	1.26
--- frame.c	1999/11/29 10:28:06
*************** typedef struct fde_accumulator
*** 283,301 ****
    fde_vector erratic;
  } fde_accumulator;
  
! static inline void
  start_fde_sort (fde_accumulator *accu, size_t count)
  {
    accu->linear.array = (fde **) malloc (sizeof (fde *) * count);
!   accu->erratic.array = (fde **) malloc (sizeof (fde *) * count);
    accu->linear.count = 0;
    accu->erratic.count = 0;
  }
  
  static inline void
  fde_insert (fde_accumulator *accu, fde *this_fde)
  {
!   accu->linear.array[accu->linear.count++] = this_fde;
  }
  
  /* Split LINEAR into a linear sequence with low values and an erratic
--- 283,305 ----
    fde_vector erratic;
  } fde_accumulator;
  
! static inline int
  start_fde_sort (fde_accumulator *accu, size_t count)
  {
    accu->linear.array = (fde **) malloc (sizeof (fde *) * count);
!   accu->erratic.array = accu->linear.array ?
!       (fde **) malloc (sizeof (fde *) * count) : NULL;
    accu->linear.count = 0;
    accu->erratic.count = 0;
+   
+   return accu->linear.array != NULL;
  }
  
  static inline void
  fde_insert (fde_accumulator *accu, fde *this_fde)
  {
!   if (accu->linear.array)
!     accu->linear.array[accu->linear.count++] = this_fde;
  }
  
  /* Split LINEAR into a linear sequence with low values and an erratic
*************** fde_merge (fde_vector *v1, const fde_vec
*** 422,435 ****
  static fde **
  end_fde_sort (fde_accumulator *accu, size_t count)
  {
!   if (accu->linear.count != count)
!     abort ();
!   fde_split (&accu->linear, &accu->erratic);
!   if (accu->linear.count + accu->erratic.count != count)
      abort ();
!   frame_heapsort (&accu->erratic);
!   fde_merge (&accu->linear, &accu->erratic);
!   free (accu->erratic.array);
    return accu->linear.array;
  }
  
--- 426,450 ----
  static fde **
  end_fde_sort (fde_accumulator *accu, size_t count)
  {
!   if (accu->linear.array && accu->linear.count != count)
      abort ();
!   
!   if (accu->erratic.array)
!     {
!       fde_split (&accu->linear, &accu->erratic);
!       if (accu->linear.count + accu->erratic.count != count)
! 	abort ();
!       frame_heapsort (&accu->erratic);
!       fde_merge (&accu->linear, &accu->erratic);
!       if (accu->erratic.array)
!         free (accu->erratic.array);
!     }
!   else
!     {
!       /* We've not managed to malloc an erratic array, so heap sort in the
!          linear one.  */
!       frame_heapsort (&accu->linear);
!     }
    return accu->linear.array;
  }
  
*************** add_fdes (fde *this_fde, fde_accumulator
*** 474,482 ****
    *end_ptr = pc_end;
  }
  
  /* Set up a sorted array of pointers to FDEs for a loaded object.  We
     count up the entries before allocating the array because it's likely to
!    be faster.  */
  
  static void
  frame_init (struct object* ob)
--- 489,514 ----
    *end_ptr = pc_end;
  }
  
+ /* search this fde table for the one containing the pc */
+ static fde *
+ search_fdes (fde *this_fde, void *pc)
+ {
+   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
+     {
+       /* Skip CIEs and linked once FDE entries.  */
+       if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
+ 	continue;
+ 
+       if ((uaddr)((char *)pc - (char *)this_fde->pc_begin) < this_fde->pc_range)
+ 	return this_fde;
+     }
+   return NULL;
+ }
+ 
  /* Set up a sorted array of pointers to FDEs for a loaded object.  We
     count up the entries before allocating the array because it's likely to
!    be faster.  We can be called multiple times, should we have failed to
!    allocate a sorted fde array on a previous occasion.  */
  
  static void
  frame_init (struct object* ob)
*************** frame_init (struct object* ob)
*** 484,491 ****
    size_t count;
    fde_accumulator accu;
    void *pc_begin, *pc_end;
  
!   if (ob->fde_array)
      {
        fde **p = ob->fde_array;
        for (count = 0; *p; ++p)
--- 516,526 ----
    size_t count;
    fde_accumulator accu;
    void *pc_begin, *pc_end;
+   fde **array;
  
!   if (ob->pc_begin)
!     count = ob->count;
!   else if (ob->fde_array)
      {
        fde **p = ob->fde_array;
        for (count = 0; *p; ++p)
*************** frame_init (struct object* ob)
*** 493,502 ****
      }
    else
      count = count_fdes (ob->fde_begin);
- 
    ob->count = count;
  
!   start_fde_sort (&accu, count);
    pc_begin = (void*)(uaddr)-1;
    pc_end = 0;
  
--- 528,538 ----
      }
    else
      count = count_fdes (ob->fde_begin);
    ob->count = count;
  
!   if (!start_fde_sort (&accu, count) && ob->pc_begin)
!     return;
! 
    pc_begin = (void*)(uaddr)-1;
    pc_end = 0;
  
*************** frame_init (struct object* ob)
*** 509,515 ****
    else
      add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
  
!   ob->fde_array = end_fde_sort (&accu, count);
    ob->pc_begin = pc_begin;
    ob->pc_end = pc_end;
  }
--- 545,553 ----
    else
      add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
  
!   array = end_fde_sort (&accu, count);
!   if (array)
!     ob->fde_array = array;
    ob->pc_begin = pc_begin;
    ob->pc_end = pc_end;
  }
*************** find_fde (void *pc)
*** 525,530 ****
--- 563,569 ----
    init_object_mutex_once ();
    __gthread_mutex_lock (&object_mutex);
  
+   /* Linear search through the objects, to find the one containing the pc. */
    for (ob = objects; ob; ob = ob->next)
      {
        if (ob->pc_begin == 0)
*************** find_fde (void *pc)
*** 533,557 ****
  	break;
      }
  
-   __gthread_mutex_unlock (&object_mutex);
- 
    if (ob == 0)
!     return 0;
  
!   /* Standard binary search algorithm.  */
!   for (lo = 0, hi = ob->count; lo < hi; )
      {
!       size_t i = (lo + hi) / 2;
!       fde *f = ob->fde_array[i];
  
!       if (pc < f->pc_begin)
! 	hi = i;
!       else if (pc >= f->pc_begin + f->pc_range)
! 	lo = i + 1;
        else
! 	return f;
      }
- 
    return 0;
  }
  
--- 572,625 ----
  	break;
      }
  
    if (ob == 0)
!     {
!       __gthread_mutex_unlock (&object_mutex);
!       return 0;
!     }
! 
!   if (!ob->fde_array || (void *)ob->fde_array == (void *)ob->fde_begin)
!     frame_init (ob);
  
!   if (ob->fde_array && (void *)ob->fde_array != (void *)ob->fde_begin)
      {
!       __gthread_mutex_unlock (&object_mutex);
!       
!       /* Standard binary search algorithm.  */
!       for (lo = 0, hi = ob->count; lo < hi; )
! 	{
! 	  size_t i = (lo + hi) / 2;
! 	  fde *f = ob->fde_array[i];
  
! 	  if (pc < f->pc_begin)
! 	    hi = i;
! 	  else if (pc >= f->pc_begin + f->pc_range)
! 	    lo = i + 1;
! 	  else
! 	    return f;
! 	}
!     }
!   else
!     {
!       /* Long slow labourious linear search, cos we've no memory. */
!       fde *f;
!       
!       if (ob->fde_array)
! 	{
! 	  fde **p = ob->fde_array;
! 	  
! 	  for (; *p; ++p)
! 	    {
! 	      f = search_fdes (*p, pc);
! 	      if (f)
! 		break;
! 	    }
! 	}
        else
! 	f = search_fdes (ob->fde_begin, pc);
!       __gthread_mutex_unlock (&object_mutex);
!       return f;
      }
    return 0;
  }
  
*************** __deregister_frame_info (void *begin)
*** 804,810 ****
  	  *p = (*p)->next;
  
  	  /* If we've run init_frame for this object, free the FDE array.  */
! 	  if (ob->pc_begin)
  	    free (ob->fde_array);
  
  	  __gthread_mutex_unlock (&object_mutex);
--- 877,883 ----
  	  *p = (*p)->next;
  
  	  /* If we've run init_frame for this object, free the FDE array.  */
! 	  if (ob->fde_array && ob->fde_array != begin)
  	    free (ob->fde_array);
  
  	  __gthread_mutex_unlock (&object_mutex);