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 = count ? (fde **) malloc (sizeof (fde *) * count) : NULL;
  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       free (accu->erratic.array);
 234     }
 235   else
 236     {
 237       /* We've not managed to malloc an erratic array, so heap sort in the
 238          linear one.  */
 239       frame_heapsort (&accu->linear);
 240     }
 241   return accu->linear.array;
 242 }
 243
 244 /* Called from crtbegin.o to register the unwind info for an object.  */
 245
 246 void
 247 __register_frame_info (void *begin, struct object *ob)
 248 {
 249   ob->fde_begin = begin;
 250
 251   ob->pc_begin = ob->pc_end = 0;
 252   ob->fde_array = 0;
 253   ob->count = 0;
 254
 255   init_object_mutex_once ();
 256   __gthread_mutex_lock (&object_mutex);
 257
 258   ob->next = objects;
 259   objects = ob;
 260
 261   __gthread_mutex_unlock (&object_mutex);
 262 }
 263
 264 void
 265 __register_frame (void *begin)
 266 {
 267   struct object *ob = (struct object *) malloc (sizeof (struct object));
 268   __register_frame_info (begin, ob);
 269 }
 270
 271 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
 272    for different translation units.  Called from the file generated by
 273    collect2.  */
 274
 275 void
 276 __register_frame_info_table (void *begin, struct object *ob)
 277 {
 278   ob->fde_begin = begin;
 279   ob->fde_array = begin;
 280
 281   ob->pc_begin = ob->pc_end = 0;
 282   ob->count = 0;
 283
 284   init_object_mutex_once ();
 285   __gthread_mutex_lock (&object_mutex);
 286
 287   ob->next = objects;
 288   objects = ob;
 289
 290   __gthread_mutex_unlock (&object_mutex);
 291 }
 292
 293 void
 294 __register_frame_table (void *begin)
 295 {
 296   struct object *ob = (struct object *) malloc (sizeof (struct object));
 297   __register_frame_info_table (begin, ob);
 298 }
 299
 300 /* Called from crtbegin.o to deregister the unwind info for an object.  */
 301
 302 void *
 303 __deregister_frame_info (void *begin)
 304 {
 305   struct object **p;
 306
 307   init_object_mutex_once ();
 308   __gthread_mutex_lock (&object_mutex);
 309
 310   p = &objects;
 311   while (*p)
 312     {
 313       if ((*p)->fde_begin == begin)
 314         {
 315           struct object *ob = *p;
 316           *p = (*p)->next;
 317
 318           /* If we've run init_frame for this object, free the FDE array.  */
 319           if (ob->fde_array && ob->fde_array != begin)
 320             free (ob->fde_array);
 321
 322           __gthread_mutex_unlock (&object_mutex);
 323           return (void *) ob;
 324         }
 325       p = &((*p)->next);
 326     }
 327
 328   __gthread_mutex_unlock (&object_mutex);
 329   abort ();
 330 }
 331
 332 void
 333 __deregister_frame (void *begin)
 334 {
 335   free (__deregister_frame_info (begin));
 336 }
 337