gcc/unwind-dw2-fde.c

   1 /* Subroutines needed for unwinding stack frames for exception handling.  */
   2 /* Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3    Contributed by Jason Merrill <jason@cygnus.com>.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 In addition to the permissions in the GNU General Public License, the
  13 Free Software Foundation gives you unlimited permission to link the
  14 compiled version of this file into combinations with other programs,
  15 and to distribute those combinations without any restriction coming
  16 from the use of this file.  (The General Public License restrictions
  17 do apply in other respects; for example, they cover modification of
  18 the file, and distribution when not linked into a combine
  19 executable.)
  20
  21 GNU CC is distributed in the hope that it will be useful,
  22 but WITHOUT ANY WARRANTY; without even the implied warranty of
  23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24 GNU General Public License for more details.
  25
  26 You should have received a copy of the GNU General Public License
  27 along with GNU CC; see the file COPYING.  If not, write to
  28 the Free Software Foundation, 59 Temple Place - Suite 330,
  29 Boston, MA 02111-1307, USA.  */
  30
  31 #include "tconfig.h"
  32 #include "tsystem.h"
  33 #include "unwind-dw2-fde.h"
  34 #include "gthr.h"
  35
  36 static struct object *objects;
  37
  38 #ifdef __GTHREAD_MUTEX_INIT
  39 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
  40 #else
  41 static __gthread_mutex_t object_mutex;
  42 #endif
  43
  44 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
  45 static void
  46 init_object_mutex (void)
  47 {
  48   __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
  49 }
  50
  51 static void
  52 init_object_mutex_once (void)
  53 {
  54   static __gthread_once_t once = __GTHREAD_ONCE_INIT;
  55   __gthread_once (&once, init_object_mutex);
  56 }
  57 #else
  58 #define init_object_mutex_once()
  59 #endif
  60
  61 /* Called from crtbegin.o to register the unwind info for an object.  */
  62
  63 void
  64 __register_frame_info (void *begin, struct object *ob)
  65 {
  66   ob->pc_begin = ob->pc_end = 0;
  67   ob->fde_begin = begin;
  68   ob->fde_array = 0;
  69   ob->count = 0;
  70
  71   init_object_mutex_once ();
  72   __gthread_mutex_lock (&object_mutex);
  73
  74   ob->next = objects;
  75   objects = ob;
  76
  77   __gthread_mutex_unlock (&object_mutex);
  78 }
  79
  80 void
  81 __register_frame (void *begin)
  82 {
  83   struct object *ob = (struct object *) malloc (sizeof (struct object));
  84   __register_frame_info (begin, ob);
  85 }
  86
  87 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
  88    for different translation units.  Called from the file generated by
  89    collect2.  */
  90
  91 void
  92 __register_frame_info_table (void *begin, struct object *ob)
  93 {
  94   ob->pc_begin = ob->pc_end = 0;
  95   ob->fde_begin = begin;
  96   ob->fde_array = begin;
  97   ob->count = 0;
  98
  99   init_object_mutex_once ();
 100   __gthread_mutex_lock (&object_mutex);
 101
 102   ob->next = objects;
 103   objects = ob;
 104
 105   __gthread_mutex_unlock (&object_mutex);
 106 }
 107
 108 void
 109 __register_frame_table (void *begin)
 110 {
 111   struct object *ob = (struct object *) malloc (sizeof (struct object));
 112   __register_frame_info_table (begin, ob);
 113 }
 114
 115 /* Called from crtbegin.o to deregister the unwind info for an object.  */
 116
 117 void *
 118 __deregister_frame_info (void *begin)
 119 {
 120   struct object **p;
 121
 122   init_object_mutex_once ();
 123   __gthread_mutex_lock (&object_mutex);
 124
 125   p = &objects;
 126   while (*p)
 127     {
 128       if ((*p)->fde_begin == begin)
 129         {
 130           struct object *ob = *p;
 131           *p = (*p)->next;
 132
 133           /* If we've run init_frame for this object, free the FDE array.  */
 134           if (ob->fde_array && ob->fde_array != begin)
 135             free (ob->fde_array);
 136
 137           __gthread_mutex_unlock (&object_mutex);
 138           return (void *) ob;
 139         }
 140       p = &((*p)->next);
 141     }
 142
 143   __gthread_mutex_unlock (&object_mutex);
 144   abort ();
 145 }
 146
 147 void
 148 __deregister_frame (void *begin)
 149 {
 150   free (__deregister_frame_info (begin));
 151 }
 152
 153 \f
 154 /* Sorting an array of FDEs by address.
 155    (Ideally we would have the linker sort the FDEs so we don't have to do
 156    it at run time. But the linkers are not yet prepared for this.)  */
 157
 158 /* This is a special mix of insertion sort and heap sort, optimized for
 159    the data sets that actually occur. They look like
 160    101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
 161    I.e. a linearly increasing sequence (coming from functions in the text
 162    section), with additionally a few unordered elements (coming from functions
 163    in gnu_linkonce sections) whose values are higher than the values in the
 164    surrounding linear sequence (but not necessarily higher than the values
 165    at the end of the linear sequence!).
 166    The worst-case total run time is O(N) + O(n log (n)), where N is the
 167    total number of FDEs and n is the number of erratic ones.  */
 168
 169 typedef struct fde_vector
 170 {
 171   fde **array;
 172   size_t count;
 173 } fde_vector;
 174
 175 typedef struct fde_accumulator
 176 {
 177   fde_vector linear;
 178   fde_vector erratic;
 179 } fde_accumulator;
 180
 181 static inline saddr
 182 fde_compare (fde *x, fde *y)
 183 {
 184   return (saddr)x->pc_begin - (saddr)y->pc_begin;
 185 }
 186
 187 static inline int
 188 start_fde_sort (fde_accumulator *accu, size_t count)
 189 {
 190   accu->linear.array = count ? (fde **) malloc (sizeof (fde *) * count) : NULL;
 191   accu->erratic.array = accu->linear.array ?
 192       (fde **) malloc (sizeof (fde *) * count) : NULL;
 193   accu->linear.count = 0;
 194   accu->erratic.count = 0;
 195
 196   return accu->linear.array != NULL;
 197 }
 198
 199 static inline void
 200 fde_insert (fde_accumulator *accu, fde *this_fde)
 201 {
 202   if (accu->linear.array)
 203     accu->linear.array[accu->linear.count++] = this_fde;
 204 }
 205
 206 /* Split LINEAR into a linear sequence with low values and an erratic
 207    sequence with high values, put the linear one (of longest possible
 208    length) into LINEAR and the erratic one into ERRATIC. This is O(N).
 209
 210    Because the longest linear sequence we are trying to locate within the
 211    incoming LINEAR array can be interspersed with (high valued) erratic
 212    entries.  We construct a chain indicating the sequenced entries.
 213    To avoid having to allocate this chain, we overlay it onto the space of
 214    the ERRATIC array during construction.  A final pass iterates over the
 215    chain to determine what should be placed in the ERRATIC array, and
 216    what is the linear sequence.  This overlay is safe from aliasing.  */
 217 static inline void
 218 fde_split (fde_vector *linear, fde_vector *erratic)
 219 {
 220   static fde *marker;
 221   size_t count = linear->count;
 222   fde **chain_end = &marker;
 223   size_t i, j, k;
 224
 225   /* This should optimize out, but it is wise to make sure this assumption
 226      is correct. Should these have different sizes, we cannot cast between
 227      them and the overlaying onto ERRATIC will not work.  */
 228   if (sizeof (fde *) != sizeof (fde **))
 229     abort ();
 230
 231   for (i = 0; i < count; i++)
 232     {
 233       fde **probe;
 234
 235       for (probe = chain_end;
 236            probe != &marker && fde_compare (linear->array[i], *probe) < 0;
 237            probe = chain_end)
 238         {
 239           chain_end = (fde **)erratic->array[probe - linear->array];
 240           erratic->array[probe - linear->array] = NULL;
 241         }
 242       erratic->array[i] = (fde *)chain_end;
 243       chain_end = &linear->array[i];
 244     }
 245
 246   /* Each entry in LINEAR which is part of the linear sequence we have
 247      discovered will correspond to a non-NULL entry in the chain we built in
 248      the ERRATIC array.  */
 249   for (i = j = k = 0; i < count; i++)
 250     if (erratic->array[i])
 251       linear->array[j++] = linear->array[i];
 252     else
 253       erratic->array[k++] = linear->array[i];
 254   linear->count = j;
 255   erratic->count = k;
 256 }
 257
 258 /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
 259    use a name that does not conflict.  */
 260 static inline void
 261 frame_heapsort (fde_vector *erratic)
 262 {
 263   /* For a description of this algorithm, see:
 264      Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
 265      p. 60-61. */
 266   fde ** a = erratic->array;
 267   /* A portion of the array is called a "heap" if for all i>=0:
 268      If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
 269      If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
 270 #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
 271   size_t n = erratic->count;
 272   size_t m = n;
 273   size_t i;
 274
 275   while (m > 0)
 276     {
 277       /* Invariant: a[m..n-1] is a heap. */
 278       m--;
 279       for (i = m; 2*i+1 < n; )
 280         {
 281           if (2*i+2 < n
 282               && fde_compare (a[2*i+2], a[2*i+1]) > 0
 283               && fde_compare (a[2*i+2], a[i]) > 0)
 284             {
 285               SWAP (a[i], a[2*i+2]);
 286               i = 2*i+2;
 287             }
 288           else if (fde_compare (a[2*i+1], a[i]) > 0)
 289             {
 290               SWAP (a[i], a[2*i+1]);
 291               i = 2*i+1;
 292             }
 293           else
 294             break;
 295         }
 296     }
 297   while (n > 1)
 298     {
 299       /* Invariant: a[0..n-1] is a heap. */
 300       n--;
 301       SWAP (a[0], a[n]);
 302       for (i = 0; 2*i+1 < n; )
 303         {
 304           if (2*i+2 < n
 305               && fde_compare (a[2*i+2], a[2*i+1]) > 0
 306               && fde_compare (a[2*i+2], a[i]) > 0)
 307             {
 308               SWAP (a[i], a[2*i+2]);
 309               i = 2*i+2;
 310             }
 311           else if (fde_compare (a[2*i+1], a[i]) > 0)
 312             {
 313               SWAP (a[i], a[2*i+1]);
 314               i = 2*i+1;
 315             }
 316           else
 317             break;
 318         }
 319     }
 320 #undef SWAP
 321 }
 322
 323 /* Merge V1 and V2, both sorted, and put the result into V1. */
 324 static void
 325 fde_merge (fde_vector *v1, const fde_vector *v2)
 326 {
 327   size_t i1, i2;
 328   fde * fde2;
 329
 330   i2 = v2->count;
 331   if (i2 > 0)
 332     {
 333       i1 = v1->count;
 334       do {
 335         i2--;
 336         fde2 = v2->array[i2];
 337         while (i1 > 0 && fde_compare (v1->array[i1-1], fde2) > 0)
 338           {
 339             v1->array[i1+i2] = v1->array[i1-1];
 340             i1--;
 341           }
 342         v1->array[i1+i2] = fde2;
 343       } while (i2 > 0);
 344       v1->count += v2->count;
 345     }
 346 }
 347
 348 static fde **
 349 end_fde_sort (fde_accumulator *accu, size_t count)
 350 {
 351   if (accu->linear.array && accu->linear.count != count)
 352     abort ();
 353
 354   if (accu->erratic.array)
 355     {
 356       fde_split (&accu->linear, &accu->erratic);
 357       if (accu->linear.count + accu->erratic.count != count)
 358         abort ();
 359       frame_heapsort (&accu->erratic);
 360       fde_merge (&accu->linear, &accu->erratic);
 361       free (accu->erratic.array);
 362     }
 363   else
 364     {
 365       /* We've not managed to malloc an erratic array, so heap sort in the
 366          linear one.  */
 367       frame_heapsort (&accu->linear);
 368     }
 369   return accu->linear.array;
 370 }
 371
 372 \f
 373 static size_t
 374 count_fdes (fde *this_fde)
 375 {
 376   size_t count;
 377
 378   for (count = 0; this_fde->length != 0; this_fde = next_fde (this_fde))
 379     /* Skip CIEs and omitted link-once FDE entries.  */
 380     if (this_fde->CIE_delta != 0 && this_fde->pc_begin != 0)
 381       ++count;
 382
 383   return count;
 384 }
 385
 386 static void
 387 add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr)
 388 {
 389   void *pc_begin = *beg_ptr;
 390   void *pc_end = *end_ptr;
 391
 392   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 393     {
 394       /* Skip CIEs and linked once FDE entries.  */
 395       if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
 396         continue;
 397
 398       fde_insert (accu, this_fde);
 399
 400       if (this_fde->pc_begin < pc_begin)
 401         pc_begin = this_fde->pc_begin;
 402       if (this_fde->pc_begin + this_fde->pc_range > pc_end)
 403         pc_end = this_fde->pc_begin + this_fde->pc_range;
 404     }
 405
 406   *beg_ptr = pc_begin;
 407   *end_ptr = pc_end;
 408 }
 409
 410 static fde *
 411 search_fdes (fde *this_fde, void *pc)
 412 {
 413   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 414     {
 415       /* Skip CIEs and linked once FDE entries.  */
 416       if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
 417         continue;
 418
 419       if ((uaddr)((char *)pc - (char *)this_fde->pc_begin) < this_fde->pc_range)
 420         return this_fde;
 421     }
 422   return NULL;
 423 }
 424
 425 /* Set up a sorted array of pointers to FDEs for a loaded object.  We
 426    count up the entries before allocating the array because it's likely to
 427    be faster.  We can be called multiple times, should we have failed to
 428    allocate a sorted fde array on a previous occasion.  */
 429
 430 static void
 431 frame_init (struct object* ob)
 432 {
 433   size_t count;
 434   fde_accumulator accu;
 435   void *pc_begin, *pc_end;
 436   fde **array;
 437
 438   if (ob->pc_begin)
 439     count = ob->count;
 440   else if (ob->fde_array)
 441     {
 442       fde **p = ob->fde_array;
 443       for (count = 0; *p; ++p)
 444         count += count_fdes (*p);
 445     }
 446   else
 447     count = count_fdes (ob->fde_begin);
 448   ob->count = count;
 449
 450   if (!start_fde_sort (&accu, count) && ob->pc_begin)
 451     return;
 452
 453   pc_begin = (void*)(uaddr)-1;
 454   pc_end = 0;
 455
 456   if (ob->fde_array)
 457     {
 458       fde **p = ob->fde_array;
 459       for (; *p; ++p)
 460         add_fdes (*p, &accu, &pc_begin, &pc_end);
 461     }
 462   else
 463     add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
 464   array = end_fde_sort (&accu, count);
 465   if (array)
 466     ob->fde_array = array;
 467   ob->pc_begin = pc_begin;
 468   ob->pc_end = pc_end;
 469 }
 470
 471 fde *
 472 _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases ATTRIBUTE_UNUSED)
 473 {
 474   struct object *ob;
 475   size_t lo, hi;
 476
 477   init_object_mutex_once ();
 478   __gthread_mutex_lock (&object_mutex);
 479
 480   /* Linear search through the objects, to find the one containing the pc. */
 481   for (ob = objects; ob; ob = ob->next)
 482     {
 483       if (ob->pc_begin == 0)
 484         frame_init (ob);
 485       if (pc >= ob->pc_begin && pc < ob->pc_end)
 486         break;
 487     }
 488
 489   if (ob == 0)
 490     {
 491       __gthread_mutex_unlock (&object_mutex);
 492       return 0;
 493     }
 494
 495   if (!ob->fde_array || (void *)ob->fde_array == (void *)ob->fde_begin)
 496     frame_init (ob);
 497
 498   if (ob->fde_array && (void *)ob->fde_array != (void *)ob->fde_begin)
 499     {
 500       __gthread_mutex_unlock (&object_mutex);
 501
 502       /* Standard binary search algorithm.  */
 503       for (lo = 0, hi = ob->count; lo < hi; )
 504         {
 505           size_t i = (lo + hi) / 2;
 506           fde *f = ob->fde_array[i];
 507
 508           if (pc < f->pc_begin)
 509             hi = i;
 510           else if (pc >= f->pc_begin + f->pc_range)
 511             lo = i + 1;
 512           else
 513             return f;
 514         }
 515     }
 516   else
 517     {
 518       /* Long slow labourious linear search, cos we've no memory. */
 519       fde *f;
 520
 521       if (ob->fde_array)
 522         {
 523           fde **p = ob->fde_array;
 524
 525           do
 526             {
 527               f = search_fdes (*p, pc);
 528               if (f)
 529                 break;
 530               p++;
 531             }
 532           while (*p);
 533         }
 534       else
 535         f = search_fdes (ob->fde_begin, pc);
 536
 537       __gthread_mutex_unlock (&object_mutex);
 538       return f;
 539     }
 540
 541   return 0;
 542 }