gcc/frame.c

   1 /* Subroutines needed for unwinding stack frames for exception handling.  */
   2 /* Compile this one with gcc.  */
   3 /* Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
   4    Contributed by Jason Merrill <jason@cygnus.com>.
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 In addition to the permissions in the GNU General Public License, the
  14 Free Software Foundation gives you unlimited permission to link the
  15 compiled version of this file into combinations with other programs,
  16 and to distribute those combinations without any restriction coming
  17 from the use of this file.  (The General Public License restrictions
  18 do apply in other respects; for example, they cover modification of
  19 the file, and distribution when not linked into a combine
  20 executable.)
  21
  22 GNU CC is distributed in the hope that it will be useful,
  23 but WITHOUT ANY WARRANTY; without even the implied warranty of
  24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  25 GNU General Public License for more details.
  26
  27 You should have received a copy of the GNU General Public License
  28 along with GNU CC; see the file COPYING.  If not, write to
  29 the Free Software Foundation, 59 Temple Place - Suite 330,
  30 Boston, MA 02111-1307, USA.  */
  31
  32 /* Sorting an array of FDEs by address.
  33    (Ideally we would have the linker sort the FDEs so we don't have to do
  34    it at run time. But the linkers are not yet prepared for this.)  */
  35
  36 /* This is a special mix of insertion sort and heap sort, optimized for
  37    the data sets that actually occur. They look like
  38    101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
  39    I.e. a linearly increasing sequence (coming from functions in the text
  40    section), with additionally a few unordered elements (coming from functions
  41    in gnu_linkonce sections) whose values are higher than the values in the
  42    surrounding linear sequence (but not necessarily higher than the values
  43    at the end of the linear sequence!).
  44    The worst-case total run time is O(N) + O(n log (n)), where N is the
  45    total number of FDEs and n is the number of erratic ones.  */
  46
  47 typedef struct fde_vector
  48 {
  49   fde **array;
  50   size_t count;
  51 } fde_vector;
  52
  53 typedef struct fde_accumulator
  54 {
  55   fde_vector linear;
  56   fde_vector erratic;
  57 } fde_accumulator;
  58
  59 static inline int
  60 start_fde_sort (fde_accumulator *accu, size_t count)
  61 {
  62   accu->linear.array = (fde **) malloc (sizeof (fde *) * count);
  63   accu->erratic.array = accu->linear.array ?
  64       (fde **) malloc (sizeof (fde *) * count) : NULL;
  65   accu->linear.count = 0;
  66   accu->erratic.count = 0;
  67
  68   return accu->linear.array != NULL;
  69 }
  70
  71 static inline void
  72 fde_insert (fde_accumulator *accu, fde *this_fde)
  73 {
  74   if (accu->linear.array)
  75     accu->linear.array[accu->linear.count++] = this_fde;
  76 }
  77
  78 /* Split LINEAR into a linear sequence with low values and an erratic
  79    sequence with high values, put the linear one (of longest possible
  80    length) into LINEAR and the erratic one into ERRATIC. This is O(N).
  81
  82    Because the longest linear sequence we are trying to locate within the
  83    incoming LINEAR array can be interspersed with (high valued) erratic
  84    entries.  We construct a chain indicating the sequenced entries.
  85    To avoid having to allocate this chain, we overlay it onto the space of
  86    the ERRATIC array during construction.  A final pass iterates over the
  87    chain to determine what should be placed in the ERRATIC array, and
  88    what is the linear sequence.  This overlay is safe from aliasing.  */
  89 static inline void
  90 fde_split (fde_vector *linear, fde_vector *erratic)
  91 {
  92   static fde *marker;
  93   size_t count = linear->count;
  94   fde **chain_end = &marker;
  95   size_t i, j, k;
  96
  97   /* This should optimize out, but it is wise to make sure this assumption
  98      is correct. Should these have different sizes, we cannot cast between
  99      them and the overlaying onto ERRATIC will not work.  */
 100   if (sizeof (fde *) != sizeof (fde **))
 101     abort ();
 102
 103   for (i = 0; i < count; i++)
 104     {
 105       fde **probe;
 106
 107       for (probe = chain_end;
 108            probe != &marker && fde_compare (linear->array[i], *probe) < 0;
 109            probe = chain_end)
 110         {
 111           chain_end = (fde **)erratic->array[probe - linear->array];
 112           erratic->array[probe - linear->array] = NULL;
 113         }
 114       erratic->array[i] = (fde *)chain_end;
 115       chain_end = &linear->array[i];
 116     }
 117
 118   /* Each entry in LINEAR which is part of the linear sequence we have
 119      discovered will correspond to a non-NULL entry in the chain we built in
 120      the ERRATIC array.  */
 121   for (i = j = k = 0; i < count; i++)
 122     if (erratic->array[i])
 123       linear->array[j++] = linear->array[i];
 124     else
 125       erratic->array[k++] = linear->array[i];
 126   linear->count = j;
 127   erratic->count = k;
 128 }
 129
 130 /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
 131    use a name that does not conflict.  */
 132 static inline void
 133 frame_heapsort (fde_vector *erratic)
 134 {
 135   /* For a description of this algorithm, see:
 136      Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
 137      p. 60-61. */
 138   fde ** a = erratic->array;
 139   /* A portion of the array is called a "heap" if for all i>=0:
 140      If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
 141      If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
 142 #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
 143   size_t n = erratic->count;
 144   size_t m = n;
 145   size_t i;
 146
 147   while (m > 0)
 148     {
 149       /* Invariant: a[m..n-1] is a heap. */
 150       m--;
 151       for (i = m; 2*i+1 < n; )
 152         {
 153           if (2*i+2 < n
 154               && fde_compare (a[2*i+2], a[2*i+1]) > 0
 155               && fde_compare (a[2*i+2], a[i]) > 0)
 156             {
 157               SWAP (a[i], a[2*i+2]);
 158               i = 2*i+2;
 159             }
 160           else if (fde_compare (a[2*i+1], a[i]) > 0)
 161             {
 162               SWAP (a[i], a[2*i+1]);
 163               i = 2*i+1;
 164             }
 165           else
 166             break;
 167         }
 168     }
 169   while (n > 1)
 170     {
 171       /* Invariant: a[0..n-1] is a heap. */
 172       n--;
 173       SWAP (a[0], a[n]);
 174       for (i = 0; 2*i+1 < n; )
 175         {
 176           if (2*i+2 < n
 177               && fde_compare (a[2*i+2], a[2*i+1]) > 0
 178               && fde_compare (a[2*i+2], a[i]) > 0)
 179             {
 180               SWAP (a[i], a[2*i+2]);
 181               i = 2*i+2;
 182             }
 183           else if (fde_compare (a[2*i+1], a[i]) > 0)
 184             {
 185               SWAP (a[i], a[2*i+1]);
 186               i = 2*i+1;
 187             }
 188           else
 189             break;
 190         }
 191     }
 192 #undef SWAP
 193 }
 194
 195 /* Merge V1 and V2, both sorted, and put the result into V1. */
 196 static void
 197 fde_merge (fde_vector *v1, const fde_vector *v2)
 198 {
 199   size_t i1, i2;
 200   fde * fde2;
 201
 202   i2 = v2->count;
 203   if (i2 > 0)
 204     {
 205       i1 = v1->count;
 206       do {
 207         i2--;
 208         fde2 = v2->array[i2];
 209         while (i1 > 0 && fde_compare (v1->array[i1-1], fde2) > 0)
 210           {
 211             v1->array[i1+i2] = v1->array[i1-1];
 212             i1--;
 213           }
 214         v1->array[i1+i2] = fde2;
 215       } while (i2 > 0);
 216       v1->count += v2->count;
 217     }
 218 }
 219
 220 static fde **
 221 end_fde_sort (fde_accumulator *accu, size_t count)
 222 {
 223   if (accu->linear.array && accu->linear.count != count)
 224     abort ();
 225
 226   if (accu->erratic.array)
 227     {
 228       fde_split (&accu->linear, &accu->erratic);
 229       if (accu->linear.count + accu->erratic.count != count)
 230         abort ();
 231       frame_heapsort (&accu->erratic);
 232       fde_merge (&accu->linear, &accu->erratic);
 233       if (accu->erratic.array)
 234         free (accu->erratic.array);
 235     }
 236   else
 237     {
 238       /* We've not managed to malloc an erratic array, so heap sort in the
 239          linear one.  */
 240       frame_heapsort (&accu->linear);
 241     }
 242   return accu->linear.array;
 243 }
 244
 245 /* Called from crtbegin.o to register the unwind info for an object.  */
 246
 247 void
 248 __register_frame_info (void *begin, struct object *ob)
 249 {
 250   ob->fde_begin = begin;
 251
 252   ob->pc_begin = ob->pc_end = 0;
 253   ob->fde_array = 0;
 254   ob->count = 0;
 255
 256   init_object_mutex_once ();
 257   __gthread_mutex_lock (&object_mutex);
 258
 259   ob->next = objects;
 260   objects = ob;
 261
 262   __gthread_mutex_unlock (&object_mutex);
 263 }
 264
 265 void
 266 __register_frame (void *begin)
 267 {
 268   struct object *ob = (struct object *) malloc (sizeof (struct object));
 269   __register_frame_info (begin, ob);
 270 }
 271
 272 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
 273    for different translation units.  Called from the file generated by
 274    collect2.  */
 275
 276 void
 277 __register_frame_info_table (void *begin, struct object *ob)
 278 {
 279   ob->fde_begin = begin;
 280   ob->fde_array = begin;
 281
 282   ob->pc_begin = ob->pc_end = 0;
 283   ob->count = 0;
 284
 285   init_object_mutex_once ();
 286   __gthread_mutex_lock (&object_mutex);
 287
 288   ob->next = objects;
 289   objects = ob;
 290
 291   __gthread_mutex_unlock (&object_mutex);
 292 }
 293
 294 void
 295 __register_frame_table (void *begin)
 296 {
 297   struct object *ob = (struct object *) malloc (sizeof (struct object));
 298   __register_frame_info_table (begin, ob);
 299 }
 300
 301 /* Called from crtbegin.o to deregister the unwind info for an object.  */
 302
 303 void *
 304 __deregister_frame_info (void *begin)
 305 {
 306   struct object **p;
 307
 308   init_object_mutex_once ();
 309   __gthread_mutex_lock (&object_mutex);
 310
 311   p = &objects;
 312   while (*p)
 313     {
 314       if ((*p)->fde_begin == begin)
 315         {
 316           struct object *ob = *p;
 317           *p = (*p)->next;
 318
 319           /* If we've run init_frame for this object, free the FDE array.  */
 320           if (ob->fde_array && ob->fde_array != begin)
 321             free (ob->fde_array);
 322
 323           __gthread_mutex_unlock (&object_mutex);
 324           return (void *) ob;
 325         }
 326       p = &((*p)->next);
 327     }
 328
 329   __gthread_mutex_unlock (&object_mutex);
 330   abort ();
 331 }
 332
 333 void
 334 __deregister_frame (void *begin)
 335 {
 336   free (__deregister_frame_info (begin));
 337 }
 338