unwind-dw2-fde.c revision 117395
1193323Sed/* Subroutines needed for unwinding stack frames for exception handling. */ 2193323Sed/* Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3193323Sed Contributed by Jason Merrill <jason@cygnus.com>. 4193323Sed 5193323SedThis file is part of GCC. 6193323Sed 7193323SedGCC is free software; you can redistribute it and/or modify it under 8193323Sedthe terms of the GNU General Public License as published by the Free 9193323SedSoftware Foundation; either version 2, or (at your option) any later 10193323Sedversion. 11193323Sed 12193323SedIn addition to the permissions in the GNU General Public License, the 13193323SedFree Software Foundation gives you unlimited permission to link the 14193323Sedcompiled version of this file into combinations with other programs, 15193323Sedand to distribute those combinations without any restriction coming 16193323Sedfrom the use of this file. (The General Public License restrictions 17193323Seddo apply in other respects; for example, they cover modification of 18193323Sedthe file, and distribution when not linked into a combine 19193323Sedexecutable.) 20193323Sed 21193323SedGCC is distributed in the hope that it will be useful, but WITHOUT ANY 22193323SedWARRANTY; without even the implied warranty of MERCHANTABILITY or 23193323SedFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 24193323Sedfor more details. 25193323Sed 26193323SedYou should have received a copy of the GNU General Public License 27193323Sedalong with GCC; see the file COPYING. If not, write to the Free 28193323SedSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 29193323Sed02111-1307, USA. */ 30193323Sed 31193323Sed#ifndef _Unwind_Find_FDE 32193323Sed#include "tconfig.h" 33193323Sed#include "tsystem.h" 34198090Srdivacky#include "dwarf2.h" 35198090Srdivacky#include "unwind.h" 36198090Srdivacky#define NO_BASE_OF_ENCODED_VALUE 37198090Srdivacky#include "unwind-pe.h" 38198090Srdivacky#include "unwind-dw2-fde.h" 39193323Sed#include "gthr.h" 40193323Sed#endif 41193323Sed 42193323Sed/* The unseen_objects list contains objects that have been registered 43198090Srdivacky but not yet categorized in any way. The seen_objects list has had 44198090Srdivacky it's pc_begin and count fields initialized at minimum, and is sorted 45198090Srdivacky by decreasing value of pc_begin. */ 46193323Sedstatic struct object *unseen_objects; 47193323Sedstatic struct object *seen_objects; 48193323Sed 49193323Sed#ifdef __GTHREAD_MUTEX_INIT 50193323Sedstatic __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT; 51193323Sed#else 52193323Sedstatic __gthread_mutex_t object_mutex; 53193323Sed#endif 54193323Sed 55198892Srdivacky#ifdef __GTHREAD_MUTEX_INIT_FUNCTION 56193323Sedstatic void 57193323Sedinit_object_mutex (void) 58193323Sed{ 59193323Sed __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex); 60198090Srdivacky} 61193323Sed 62193323Sedstatic void 63193323Sedinit_object_mutex_once (void) 64193323Sed{ 65193323Sed static __gthread_once_t once = __GTHREAD_ONCE_INIT; 66193323Sed __gthread_once (&once, init_object_mutex); 67193323Sed} 68193323Sed#else 69193323Sed#define init_object_mutex_once() 70193323Sed#endif 71193323Sed 72193323Sed/* Called from crtbegin.o to register the unwind info for an object. */ 73193323Sed 74193323Sedvoid 75193323Sed__register_frame_info_bases (void *begin, struct object *ob, 76193323Sed void *tbase, void *dbase) 77193323Sed{ 78202375Srdivacky /* If .eh_frame is empty, don't register at all. */ 79193323Sed if (*(uword *) begin == 0) 80202375Srdivacky return; 81193323Sed 82193323Sed ob->pc_begin = (void *)-1; 83202375Srdivacky ob->tbase = tbase; 84193323Sed ob->dbase = dbase; 85193323Sed ob->u.single = begin; 86193323Sed ob->s.i = 0; 87193323Sed ob->s.b.encoding = DW_EH_PE_omit; 88193323Sed#ifdef DWARF2_OBJECT_END_PTR_EXTENSION 89193323Sed ob->fde_end = NULL; 90193323Sed#endif 91193323Sed 92193323Sed init_object_mutex_once (); 93193323Sed __gthread_mutex_lock (&object_mutex); 94193323Sed 95193323Sed ob->next = unseen_objects; 96193323Sed unseen_objects = ob; 97193323Sed 98193323Sed __gthread_mutex_unlock (&object_mutex); 99193323Sed} 100193323Sed 101193323Sedvoid 102193323Sed__register_frame_info (void *begin, struct object *ob) 103193323Sed{ 104193323Sed __register_frame_info_bases (begin, ob, 0, 0); 105193323Sed} 106193323Sed 107193323Sedvoid 108193323Sed__register_frame (void *begin) 109193323Sed{ 110193323Sed struct object *ob; 111193323Sed 112193323Sed /* If .eh_frame is empty, don't register at all. */ 113193323Sed if (*(uword *) begin == 0) 114193323Sed return; 115193323Sed 116193323Sed ob = (struct object *) malloc (sizeof (struct object)); 117193323Sed __register_frame_info (begin, ob); 118193323Sed} 119193323Sed 120193323Sed/* Similar, but BEGIN is actually a pointer to a table of unwind entries 121193323Sed for different translation units. Called from the file generated by 122193323Sed collect2. */ 123193323Sed 124193323Sedvoid 125193323Sed__register_frame_info_table_bases (void *begin, struct object *ob, 126193323Sed void *tbase, void *dbase) 127193323Sed{ 128193323Sed ob->pc_begin = (void *)-1; 129193323Sed ob->tbase = tbase; 130193323Sed ob->dbase = dbase; 131193323Sed ob->u.array = begin; 132193323Sed ob->s.i = 0; 133193323Sed ob->s.b.from_array = 1; 134193323Sed ob->s.b.encoding = DW_EH_PE_omit; 135193323Sed 136193323Sed init_object_mutex_once (); 137193323Sed __gthread_mutex_lock (&object_mutex); 138193323Sed 139193323Sed ob->next = unseen_objects; 140193323Sed unseen_objects = ob; 141193323Sed 142193323Sed __gthread_mutex_unlock (&object_mutex); 143193323Sed} 144193323Sed 145193323Sedvoid 146193323Sed__register_frame_info_table (void *begin, struct object *ob) 147193323Sed{ 148193323Sed __register_frame_info_table_bases (begin, ob, 0, 0); 149193323Sed} 150193323Sed 151193323Sedvoid 152193323Sed__register_frame_table (void *begin) 153193323Sed{ 154193323Sed struct object *ob = (struct object *) malloc (sizeof (struct object)); 155193323Sed __register_frame_info_table (begin, ob); 156193323Sed} 157193323Sed 158193323Sed/* Called from crtbegin.o to deregister the unwind info for an object. */ 159193323Sed/* ??? Glibc has for a while now exported __register_frame_info and 160193323Sed __deregister_frame_info. If we call __register_frame_info_bases 161193323Sed from crtbegin (wherein it is declared weak), and this object does 162193323Sed not get pulled from libgcc.a for other reasons, then the 163193323Sed invocation of __deregister_frame_info will be resolved from glibc. 164193323Sed Since the registration did not happen there, we'll abort. 165193323Sed 166193323Sed Therefore, declare a new deregistration entry point that does the 167193323Sed exact same thing, but will resolve to the same library as 168193323Sed implements __register_frame_info_bases. */ 169193323Sed 170193323Sedvoid * 171193323Sed__deregister_frame_info_bases (void *begin) 172193323Sed{ 173193323Sed struct object **p; 174193323Sed struct object *ob = 0; 175193323Sed 176193323Sed /* If .eh_frame is empty, we haven't registered. */ 177193323Sed if (*(uword *) begin == 0) 178193323Sed return ob; 179193323Sed 180193323Sed init_object_mutex_once (); 181193323Sed __gthread_mutex_lock (&object_mutex); 182193323Sed 183193323Sed for (p = &unseen_objects; *p ; p = &(*p)->next) 184193323Sed if ((*p)->u.single == begin) 185193323Sed { 186193323Sed ob = *p; 187193323Sed *p = ob->next; 188193323Sed goto out; 189193323Sed } 190193323Sed 191193323Sed for (p = &seen_objects; *p ; p = &(*p)->next) 192193323Sed if ((*p)->s.b.sorted) 193193323Sed { 194193323Sed if ((*p)->u.sort->orig_data == begin) 195193323Sed { 196193323Sed ob = *p; 197193323Sed *p = ob->next; 198193323Sed free (ob->u.sort); 199193323Sed goto out; 200193323Sed } 201193323Sed } 202193323Sed else 203193323Sed { 204193323Sed if ((*p)->u.single == begin) 205193323Sed { 206193323Sed ob = *p; 207193323Sed *p = ob->next; 208193323Sed goto out; 209193323Sed } 210193323Sed } 211193323Sed 212193323Sed __gthread_mutex_unlock (&object_mutex); 213193323Sed abort (); 214193323Sed 215198090Srdivacky out: 216198090Srdivacky __gthread_mutex_unlock (&object_mutex); 217198090Srdivacky return (void *) ob; 218198090Srdivacky} 219198090Srdivacky 220198090Srdivackyvoid * 221198090Srdivacky__deregister_frame_info (void *begin) 222198090Srdivacky{ 223193323Sed return __deregister_frame_info_bases (begin); 224193323Sed} 225193323Sed 226193323Sedvoid 227193323Sed__deregister_frame (void *begin) 228193323Sed{ 229193323Sed /* If .eh_frame is empty, we haven't registered. */ 230193323Sed if (*(uword *) begin != 0) 231193323Sed free (__deregister_frame_info (begin)); 232193323Sed} 233193323Sed 234193323Sed 235193323Sed/* Like base_of_encoded_value, but take the base from a struct object 236193323Sed instead of an _Unwind_Context. */ 237193323Sed 238193323Sedstatic _Unwind_Ptr 239193323Sedbase_from_object (unsigned char encoding, struct object *ob) 240193323Sed{ 241193323Sed if (encoding == DW_EH_PE_omit) 242193323Sed return 0; 243193323Sed 244193323Sed switch (encoding & 0x70) 245193323Sed { 246193323Sed case DW_EH_PE_absptr: 247193323Sed case DW_EH_PE_pcrel: 248193323Sed case DW_EH_PE_aligned: 249202375Srdivacky return 0; 250193323Sed 251193323Sed case DW_EH_PE_textrel: 252193323Sed return (_Unwind_Ptr) ob->tbase; 253193323Sed case DW_EH_PE_datarel: 254193323Sed return (_Unwind_Ptr) ob->dbase; 255193323Sed } 256193323Sed abort (); 257193323Sed} 258193323Sed 259193323Sed/* Return the FDE pointer encoding from the CIE. */ 260193323Sed/* ??? This is a subset of extract_cie_info from unwind-dw2.c. */ 261193323Sed 262193323Sedstatic int 263193323Sedget_cie_encoding (struct dwarf_cie *cie) 264193323Sed{ 265193323Sed const unsigned char *aug, *p; 266193323Sed _Unwind_Ptr dummy; 267193323Sed _Unwind_Word utmp; 268198090Srdivacky _Unwind_Sword stmp; 269193323Sed 270193323Sed aug = cie->augmentation; 271193323Sed if (aug[0] != 'z') 272193323Sed return DW_EH_PE_absptr; 273193323Sed 274193323Sed p = aug + strlen (aug) + 1; /* Skip the augmentation string. */ 275193323Sed p = read_uleb128 (p, &utmp); /* Skip code alignment. */ 276202375Srdivacky p = read_sleb128 (p, &stmp); /* Skip data alignment. */ 277193323Sed p++; /* Skip return address column. */ 278193323Sed 279193323Sed aug++; /* Skip 'z' */ 280193323Sed p = read_uleb128 (p, &utmp); /* Skip augmentation length. */ 281193323Sed while (1) 282193323Sed { 283193323Sed /* This is what we're looking for. */ 284193323Sed if (*aug == 'R') 285202375Srdivacky return *p; 286193323Sed /* Personality encoding and pointer. */ 287193323Sed else if (*aug == 'P') 288193323Sed { 289193323Sed /* ??? Avoid dereferencing indirect pointers, since we're 290202375Srdivacky faking the base address. Gotta keep DW_EH_PE_aligned 291202375Srdivacky intact, however. */ 292200581Srdivacky p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy); 293193323Sed } 294193323Sed /* LSDA encoding. */ 295193323Sed else if (*aug == 'L') 296193323Sed p++; 297193323Sed /* Otherwise end of string, or unknown augmentation. */ 298193323Sed else 299193323Sed return DW_EH_PE_absptr; 300193323Sed aug++; 301193323Sed } 302193323Sed} 303193323Sed 304193323Sedstatic inline int 305193323Sedget_fde_encoding (struct dwarf_fde *f) 306193323Sed{ 307193323Sed return get_cie_encoding (get_cie (f)); 308193323Sed} 309193323Sed 310193323Sed 311193323Sed/* Sorting an array of FDEs by address. 312193323Sed (Ideally we would have the linker sort the FDEs so we don't have to do 313193323Sed it at run time. But the linkers are not yet prepared for this.) */ 314193323Sed 315193323Sed/* Comparison routines. Three variants of increasing complexity. */ 316193323Sed 317193323Sedstatic int 318193323Sedfde_unencoded_compare (struct object *ob __attribute__((unused)), 319193323Sed fde *x, fde *y) 320193323Sed{ 321193323Sed _Unwind_Ptr x_ptr = *(_Unwind_Ptr *) x->pc_begin; 322193323Sed _Unwind_Ptr y_ptr = *(_Unwind_Ptr *) y->pc_begin; 323193323Sed 324193323Sed if (x_ptr > y_ptr) 325193323Sed return 1; 326193323Sed if (x_ptr < y_ptr) 327193323Sed return -1; 328193323Sed return 0; 329193323Sed} 330193323Sed 331193323Sedstatic int 332193323Sedfde_single_encoding_compare (struct object *ob, fde *x, fde *y) 333193323Sed{ 334193323Sed _Unwind_Ptr base, x_ptr, y_ptr; 335193323Sed 336193323Sed base = base_from_object (ob->s.b.encoding, ob); 337193323Sed read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr); 338193323Sed read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr); 339193323Sed 340193323Sed if (x_ptr > y_ptr) 341193323Sed return 1; 342193323Sed if (x_ptr < y_ptr) 343193323Sed return -1; 344193323Sed return 0; 345193323Sed} 346193323Sed 347193323Sedstatic int 348193323Sedfde_mixed_encoding_compare (struct object *ob, fde *x, fde *y) 349193323Sed{ 350193323Sed int x_encoding, y_encoding; 351193323Sed _Unwind_Ptr x_ptr, y_ptr; 352193323Sed 353193323Sed x_encoding = get_fde_encoding (x); 354193323Sed read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob), 355193323Sed x->pc_begin, &x_ptr); 356193323Sed 357193323Sed y_encoding = get_fde_encoding (y); 358193323Sed read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob), 359193323Sed y->pc_begin, &y_ptr); 360193323Sed 361193323Sed if (x_ptr > y_ptr) 362193323Sed return 1; 363193323Sed if (x_ptr < y_ptr) 364193323Sed return -1; 365193323Sed return 0; 366193323Sed} 367193323Sed 368193323Sedtypedef int (*fde_compare_t) (struct object *, fde *, fde *); 369193323Sed 370193323Sed 371193323Sed/* This is a special mix of insertion sort and heap sort, optimized for 372193323Sed the data sets that actually occur. They look like 373193323Sed 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130. 374193323Sed I.e. a linearly increasing sequence (coming from functions in the text 375193323Sed section), with additionally a few unordered elements (coming from functions 376193323Sed in gnu_linkonce sections) whose values are higher than the values in the 377193323Sed surrounding linear sequence (but not necessarily higher than the values 378193323Sed at the end of the linear sequence!). 379193323Sed The worst-case total run time is O(N) + O(n log (n)), where N is the 380193323Sed total number of FDEs and n is the number of erratic ones. */ 381193323Sed 382193323Sedstruct fde_accumulator 383193323Sed{ 384193323Sed struct fde_vector *linear; 385193323Sed struct fde_vector *erratic; 386193323Sed}; 387193323Sed 388193323Sedstatic inline int 389193323Sedstart_fde_sort (struct fde_accumulator *accu, size_t count) 390193323Sed{ 391193323Sed size_t size; 392193323Sed if (! count) 393193323Sed return 0; 394193323Sed 395193323Sed size = sizeof (struct fde_vector) + sizeof (fde *) * count; 396193323Sed if ((accu->linear = (struct fde_vector *) malloc (size))) 397193323Sed { 398193323Sed accu->linear->count = 0; 399193323Sed if ((accu->erratic = (struct fde_vector *) malloc (size))) 400193323Sed accu->erratic->count = 0; 401193323Sed return 1; 402193323Sed } 403193323Sed else 404193323Sed return 0; 405193323Sed} 406193323Sed 407193323Sedstatic inline void 408193323Sedfde_insert (struct fde_accumulator *accu, fde *this_fde) 409193323Sed{ 410193323Sed if (accu->linear) 411193323Sed accu->linear->array[accu->linear->count++] = this_fde; 412193323Sed} 413193323Sed 414193323Sed/* Split LINEAR into a linear sequence with low values and an erratic 415193323Sed sequence with high values, put the linear one (of longest possible 416193323Sed length) into LINEAR and the erratic one into ERRATIC. This is O(N). 417193323Sed 418193323Sed Because the longest linear sequence we are trying to locate within the 419193323Sed incoming LINEAR array can be interspersed with (high valued) erratic 420193323Sed entries. We construct a chain indicating the sequenced entries. 421193323Sed To avoid having to allocate this chain, we overlay it onto the space of 422193323Sed the ERRATIC array during construction. A final pass iterates over the 423193323Sed chain to determine what should be placed in the ERRATIC array, and 424193323Sed what is the linear sequence. This overlay is safe from aliasing. */ 425193323Sed 426193323Sedstatic inline void 427193323Sedfde_split (struct object *ob, fde_compare_t fde_compare, 428193323Sed struct fde_vector *linear, struct fde_vector *erratic) 429193323Sed{ 430193323Sed static fde *marker; 431193323Sed size_t count = linear->count; 432193323Sed fde **chain_end = ▮ 433193323Sed size_t i, j, k; 434193323Sed 435193323Sed /* This should optimize out, but it is wise to make sure this assumption 436193323Sed is correct. Should these have different sizes, we cannot cast between 437193323Sed them and the overlaying onto ERRATIC will not work. */ 438193323Sed if (sizeof (fde *) != sizeof (fde **)) 439193323Sed abort (); 440193323Sed 441193323Sed for (i = 0; i < count; i++) 442193323Sed { 443193323Sed fde **probe; 444193323Sed 445193323Sed for (probe = chain_end; 446193323Sed probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0; 447193323Sed probe = chain_end) 448193323Sed { 449193323Sed chain_end = (fde **) erratic->array[probe - linear->array]; 450193323Sed erratic->array[probe - linear->array] = NULL; 451193323Sed } 452193323Sed erratic->array[i] = (fde *) chain_end; 453193323Sed chain_end = &linear->array[i]; 454193323Sed } 455193323Sed 456193323Sed /* Each entry in LINEAR which is part of the linear sequence we have 457193323Sed discovered will correspond to a non-NULL entry in the chain we built in 458193323Sed the ERRATIC array. */ 459193323Sed for (i = j = k = 0; i < count; i++) 460193323Sed if (erratic->array[i]) 461193323Sed linear->array[j++] = linear->array[i]; 462193323Sed else 463193323Sed erratic->array[k++] = linear->array[i]; 464193323Sed linear->count = j; 465193323Sed erratic->count = k; 466193323Sed} 467193323Sed 468193323Sed/* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must 469193323Sed use a name that does not conflict. */ 470193323Sed 471193323Sedstatic void 472193323Sedframe_heapsort (struct object *ob, fde_compare_t fde_compare, 473193323Sed struct fde_vector *erratic) 474193323Sed{ 475193323Sed /* For a description of this algorithm, see: 476193323Sed Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed., 477193323Sed p. 60-61. */ 478193323Sed fde ** a = erratic->array; 479193323Sed /* A portion of the array is called a "heap" if for all i>=0: 480193323Sed If i and 2i+1 are valid indices, then a[i] >= a[2i+1]. 481193323Sed If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */ 482193323Sed#define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0) 483193323Sed size_t n = erratic->count; 484193323Sed size_t m = n; 485193323Sed size_t i; 486193323Sed 487193323Sed while (m > 0) 488193323Sed { 489193323Sed /* Invariant: a[m..n-1] is a heap. */ 490193323Sed m--; 491193323Sed for (i = m; 2*i+1 < n; ) 492193323Sed { 493193323Sed if (2*i+2 < n 494193323Sed && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0 495193323Sed && fde_compare (ob, a[2*i+2], a[i]) > 0) 496193323Sed { 497193323Sed SWAP (a[i], a[2*i+2]); 498193323Sed i = 2*i+2; 499193323Sed } 500193323Sed else if (fde_compare (ob, a[2*i+1], a[i]) > 0) 501193323Sed { 502193323Sed SWAP (a[i], a[2*i+1]); 503193323Sed i = 2*i+1; 504193323Sed } 505193323Sed else 506193323Sed break; 507193323Sed } 508193323Sed } 509193323Sed while (n > 1) 510193323Sed { 511193323Sed /* Invariant: a[0..n-1] is a heap. */ 512193323Sed n--; 513193323Sed SWAP (a[0], a[n]); 514193323Sed for (i = 0; 2*i+1 < n; ) 515193323Sed { 516193323Sed if (2*i+2 < n 517193323Sed && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0 518193323Sed && fde_compare (ob, a[2*i+2], a[i]) > 0) 519193323Sed { 520193323Sed SWAP (a[i], a[2*i+2]); 521193323Sed i = 2*i+2; 522193323Sed } 523193323Sed else if (fde_compare (ob, a[2*i+1], a[i]) > 0) 524193323Sed { 525193323Sed SWAP (a[i], a[2*i+1]); 526193323Sed i = 2*i+1; 527193323Sed } 528193323Sed else 529193323Sed break; 530193323Sed } 531193323Sed } 532193323Sed#undef SWAP 533193323Sed} 534193323Sed 535193323Sed/* Merge V1 and V2, both sorted, and put the result into V1. */ 536193323Sedstatic inline void 537193323Sedfde_merge (struct object *ob, fde_compare_t fde_compare, 538193323Sed struct fde_vector *v1, struct fde_vector *v2) 539193323Sed{ 540193323Sed size_t i1, i2; 541193323Sed fde * fde2; 542193323Sed 543193323Sed i2 = v2->count; 544193323Sed if (i2 > 0) 545193323Sed { 546193323Sed i1 = v1->count; 547193323Sed do 548193323Sed { 549193323Sed i2--; 550193323Sed fde2 = v2->array[i2]; 551193323Sed while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0) 552193323Sed { 553193323Sed v1->array[i1+i2] = v1->array[i1-1]; 554193323Sed i1--; 555193323Sed } 556193323Sed v1->array[i1+i2] = fde2; 557193323Sed } 558193323Sed while (i2 > 0); 559193323Sed v1->count += v2->count; 560193323Sed } 561193323Sed} 562193323Sed 563193323Sedstatic inline void 564193323Sedend_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count) 565193323Sed{ 566193323Sed fde_compare_t fde_compare; 567193323Sed 568193323Sed if (accu->linear && accu->linear->count != count) 569193323Sed abort (); 570193323Sed 571193323Sed if (ob->s.b.mixed_encoding) 572193323Sed fde_compare = fde_mixed_encoding_compare; 573193323Sed else if (ob->s.b.encoding == DW_EH_PE_absptr) 574193323Sed fde_compare = fde_unencoded_compare; 575193323Sed else 576193323Sed fde_compare = fde_single_encoding_compare; 577193323Sed 578193323Sed if (accu->erratic) 579193323Sed { 580193323Sed fde_split (ob, fde_compare, accu->linear, accu->erratic); 581193323Sed if (accu->linear->count + accu->erratic->count != count) 582193323Sed abort (); 583193323Sed frame_heapsort (ob, fde_compare, accu->erratic); 584193323Sed fde_merge (ob, fde_compare, accu->linear, accu->erratic); 585193323Sed free (accu->erratic); 586193323Sed } 587193323Sed else 588193323Sed { 589193323Sed /* We've not managed to malloc an erratic array, 590193323Sed so heap sort in the linear one. */ 591193323Sed frame_heapsort (ob, fde_compare, accu->linear); 592193323Sed } 593193323Sed} 594193323Sed 595193323Sed 596193323Sed/* Update encoding, mixed_encoding, and pc_begin for OB for the 597193323Sed fde array beginning at THIS_FDE. Return the number of fdes 598193323Sed encountered along the way. */ 599193323Sed 600193323Sedstatic size_t 601193323Sedclassify_object_over_fdes (struct object *ob, fde *this_fde) 602193323Sed{ 603193323Sed struct dwarf_cie *last_cie = 0; 604193323Sed size_t count = 0; 605193323Sed int encoding = DW_EH_PE_absptr; 606193323Sed _Unwind_Ptr base = 0; 607193323Sed 608193323Sed for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 609193323Sed { 610193323Sed struct dwarf_cie *this_cie; 611193323Sed _Unwind_Ptr mask, pc_begin; 612193323Sed 613193323Sed /* Skip CIEs. */ 614193323Sed if (this_fde->CIE_delta == 0) 615193323Sed continue; 616193323Sed 617193323Sed /* Determine the encoding for this FDE. Note mixed encoded 618193323Sed objects for later. */ 619193323Sed this_cie = get_cie (this_fde); 620193323Sed if (this_cie != last_cie) 621193323Sed { 622193323Sed last_cie = this_cie; 623193323Sed encoding = get_cie_encoding (this_cie); 624193323Sed base = base_from_object (encoding, ob); 625193323Sed if (ob->s.b.encoding == DW_EH_PE_omit) 626193323Sed ob->s.b.encoding = encoding; 627193323Sed else if (ob->s.b.encoding != encoding) 628193323Sed ob->s.b.mixed_encoding = 1; 629193323Sed } 630193323Sed 631193323Sed read_encoded_value_with_base (encoding, base, this_fde->pc_begin, 632193323Sed &pc_begin); 633193323Sed 634193323Sed /* Take care to ignore link-once functions that were removed. 635193323Sed In these cases, the function address will be NULL, but if 636193323Sed the encoding is smaller than a pointer a true NULL may not 637193323Sed be representable. Assume 0 in the representable bits is NULL. */ 638193323Sed mask = size_of_encoded_value (encoding); 639193323Sed if (mask < sizeof (void *)) 640193323Sed mask = (1L << (mask << 3)) - 1; 641193323Sed else 642193323Sed mask = -1; 643193323Sed 644193323Sed if ((pc_begin & mask) == 0) 645193323Sed continue; 646193323Sed 647193323Sed count += 1; 648193323Sed if ((void *) pc_begin < ob->pc_begin) 649193323Sed ob->pc_begin = (void *) pc_begin; 650193323Sed } 651193323Sed 652193323Sed return count; 653193323Sed} 654193323Sed 655193323Sedstatic void 656193323Sedadd_fdes (struct object *ob, struct fde_accumulator *accu, fde *this_fde) 657193323Sed{ 658193323Sed struct dwarf_cie *last_cie = 0; 659193323Sed int encoding = ob->s.b.encoding; 660193323Sed _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob); 661193323Sed 662193323Sed for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 663193323Sed { 664193323Sed struct dwarf_cie *this_cie; 665193323Sed 666193323Sed /* Skip CIEs. */ 667193323Sed if (this_fde->CIE_delta == 0) 668193323Sed continue; 669193323Sed 670193323Sed if (ob->s.b.mixed_encoding) 671193323Sed { 672193323Sed /* Determine the encoding for this FDE. Note mixed encoded 673193323Sed objects for later. */ 674193323Sed this_cie = get_cie (this_fde); 675193323Sed if (this_cie != last_cie) 676193323Sed { 677193323Sed last_cie = this_cie; 678193323Sed encoding = get_cie_encoding (this_cie); 679193323Sed base = base_from_object (encoding, ob); 680193323Sed } 681193323Sed } 682193323Sed 683193323Sed if (encoding == DW_EH_PE_absptr) 684193323Sed { 685193323Sed if (*(_Unwind_Ptr *) this_fde->pc_begin == 0) 686193323Sed continue; 687193323Sed } 688193323Sed else 689193323Sed { 690193323Sed _Unwind_Ptr pc_begin, mask; 691193323Sed 692193323Sed read_encoded_value_with_base (encoding, base, this_fde->pc_begin, 693193323Sed &pc_begin); 694193323Sed 695193323Sed /* Take care to ignore link-once functions that were removed. 696193323Sed In these cases, the function address will be NULL, but if 697193323Sed the encoding is smaller than a pointer a true NULL may not 698193323Sed be representable. Assume 0 in the representable bits is NULL. */ 699193323Sed mask = size_of_encoded_value (encoding); 700193323Sed if (mask < sizeof (void *)) 701193323Sed mask = (1L << (mask << 3)) - 1; 702193323Sed else 703193323Sed mask = -1; 704193323Sed 705193323Sed if ((pc_begin & mask) == 0) 706193323Sed continue; 707193323Sed } 708193323Sed 709193323Sed fde_insert (accu, this_fde); 710193323Sed } 711193323Sed} 712193323Sed 713193323Sed/* Set up a sorted array of pointers to FDEs for a loaded object. We 714193323Sed count up the entries before allocating the array because it's likely to 715193323Sed be faster. We can be called multiple times, should we have failed to 716193323Sed allocate a sorted fde array on a previous occasion. */ 717193323Sed 718193323Sedstatic inline void 719193323Sedinit_object (struct object* ob) 720193323Sed{ 721193323Sed struct fde_accumulator accu; 722193323Sed size_t count; 723193323Sed 724193323Sed count = ob->s.b.count; 725193323Sed if (count == 0) 726193323Sed { 727193323Sed if (ob->s.b.from_array) 728193323Sed { 729193323Sed fde **p = ob->u.array; 730193323Sed for (count = 0; *p; ++p) 731193323Sed count += classify_object_over_fdes (ob, *p); 732193323Sed } 733193323Sed else 734193323Sed count = classify_object_over_fdes (ob, ob->u.single); 735193323Sed 736193323Sed /* The count field we have in the main struct object is somewhat 737193323Sed limited, but should suffice for virtually all cases. If the 738193323Sed counted value doesn't fit, re-write a zero. The worst that 739193323Sed happens is that we re-count next time -- admittedly non-trivial 740193323Sed in that this implies some 2M fdes, but at least we function. */ 741193323Sed ob->s.b.count = count; 742193323Sed if (ob->s.b.count != count) 743193323Sed ob->s.b.count = 0; 744193323Sed } 745193323Sed 746193323Sed if (!start_fde_sort (&accu, count)) 747193323Sed return; 748193323Sed 749193323Sed if (ob->s.b.from_array) 750193323Sed { 751193323Sed fde **p; 752193323Sed for (p = ob->u.array; *p; ++p) 753193323Sed add_fdes (ob, &accu, *p); 754193323Sed } 755193323Sed else 756193323Sed add_fdes (ob, &accu, ob->u.single); 757193323Sed 758193323Sed end_fde_sort (ob, &accu, count); 759193323Sed 760193323Sed /* Save the original fde pointer, since this is the key by which the 761193323Sed DSO will deregister the object. */ 762193323Sed accu.linear->orig_data = ob->u.single; 763193323Sed ob->u.sort = accu.linear; 764193323Sed 765193323Sed ob->s.b.sorted = 1; 766193323Sed} 767193323Sed 768193323Sed/* A linear search through a set of FDEs for the given PC. This is 769193323Sed used when there was insufficient memory to allocate and sort an 770193323Sed array. */ 771193323Sed 772193323Sedstatic fde * 773193323Sedlinear_search_fdes (struct object *ob, fde *this_fde, void *pc) 774193323Sed{ 775193323Sed struct dwarf_cie *last_cie = 0; 776193323Sed int encoding = ob->s.b.encoding; 777193323Sed _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob); 778193323Sed 779193323Sed for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 780193323Sed { 781193323Sed struct dwarf_cie *this_cie; 782193323Sed _Unwind_Ptr pc_begin, pc_range; 783193323Sed 784193323Sed /* Skip CIEs. */ 785193323Sed if (this_fde->CIE_delta == 0) 786193323Sed continue; 787193323Sed 788193323Sed if (ob->s.b.mixed_encoding) 789193323Sed { 790193323Sed /* Determine the encoding for this FDE. Note mixed encoded 791193323Sed objects for later. */ 792193323Sed this_cie = get_cie (this_fde); 793193323Sed if (this_cie != last_cie) 794193323Sed { 795193323Sed last_cie = this_cie; 796193323Sed encoding = get_cie_encoding (this_cie); 797193323Sed base = base_from_object (encoding, ob); 798193323Sed } 799193323Sed } 800193323Sed 801193323Sed if (encoding == DW_EH_PE_absptr) 802193323Sed { 803193323Sed pc_begin = ((_Unwind_Ptr *) this_fde->pc_begin)[0]; 804193323Sed pc_range = ((_Unwind_Ptr *) this_fde->pc_begin)[1]; 805193323Sed if (pc_begin == 0) 806193323Sed continue; 807193323Sed } 808193323Sed else 809193323Sed { 810193323Sed _Unwind_Ptr mask; 811193323Sed const char *p; 812193323Sed 813193323Sed p = read_encoded_value_with_base (encoding, base, 814193323Sed this_fde->pc_begin, &pc_begin); 815193323Sed read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 816193323Sed 817193323Sed /* Take care to ignore link-once functions that were removed. 818193323Sed In these cases, the function address will be NULL, but if 819193323Sed the encoding is smaller than a pointer a true NULL may not 820193323Sed be representable. Assume 0 in the representable bits is NULL. */ 821193323Sed mask = size_of_encoded_value (encoding); 822193323Sed if (mask < sizeof (void *)) 823193323Sed mask = (1L << (mask << 3)) - 1; 824193323Sed else 825193323Sed mask = -1; 826193323Sed 827193323Sed if ((pc_begin & mask) == 0) 828193323Sed continue; 829193323Sed } 830193323Sed 831193323Sed if ((_Unwind_Ptr) pc - pc_begin < pc_range) 832193323Sed return this_fde; 833193323Sed } 834193323Sed 835193323Sed return NULL; 836193323Sed} 837193323Sed 838193323Sed/* Binary search for an FDE containing the given PC. Here are three 839193323Sed implementations of increasing complexity. */ 840193323Sed 841193323Sedstatic inline fde * 842193323Sedbinary_search_unencoded_fdes (struct object *ob, void *pc) 843193323Sed{ 844193323Sed struct fde_vector *vec = ob->u.sort; 845193323Sed size_t lo, hi; 846193323Sed 847193323Sed for (lo = 0, hi = vec->count; lo < hi; ) 848193323Sed { 849193323Sed size_t i = (lo + hi) / 2; 850193323Sed fde *f = vec->array[i]; 851193323Sed void *pc_begin; 852193323Sed uaddr pc_range; 853193323Sed 854193323Sed pc_begin = ((void **) f->pc_begin)[0]; 855193323Sed pc_range = ((uaddr *) f->pc_begin)[1]; 856193323Sed 857193323Sed if (pc < pc_begin) 858193323Sed hi = i; 859193323Sed else if (pc >= pc_begin + pc_range) 860193323Sed lo = i + 1; 861193323Sed else 862193323Sed return f; 863193323Sed } 864193323Sed 865193323Sed return NULL; 866193323Sed} 867193323Sed 868193323Sedstatic inline fde * 869193323Sedbinary_search_single_encoding_fdes (struct object *ob, void *pc) 870193323Sed{ 871193323Sed struct fde_vector *vec = ob->u.sort; 872193323Sed int encoding = ob->s.b.encoding; 873193323Sed _Unwind_Ptr base = base_from_object (encoding, ob); 874193323Sed size_t lo, hi; 875193323Sed 876193323Sed for (lo = 0, hi = vec->count; lo < hi; ) 877193323Sed { 878193323Sed size_t i = (lo + hi) / 2; 879193323Sed fde *f = vec->array[i]; 880193323Sed _Unwind_Ptr pc_begin, pc_range; 881193323Sed const char *p; 882193323Sed 883193323Sed p = read_encoded_value_with_base (encoding, base, f->pc_begin, 884193323Sed &pc_begin); 885193323Sed read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 886193323Sed 887193323Sed if ((_Unwind_Ptr) pc < pc_begin) 888193323Sed hi = i; 889193323Sed else if ((_Unwind_Ptr) pc >= pc_begin + pc_range) 890193323Sed lo = i + 1; 891193323Sed else 892193323Sed return f; 893193323Sed } 894193323Sed 895193323Sed return NULL; 896193323Sed} 897193323Sed 898193323Sedstatic inline fde * 899193323Sedbinary_search_mixed_encoding_fdes (struct object *ob, void *pc) 900193323Sed{ 901193323Sed struct fde_vector *vec = ob->u.sort; 902193323Sed size_t lo, hi; 903193323Sed 904193323Sed for (lo = 0, hi = vec->count; lo < hi; ) 905193323Sed { 906193323Sed size_t i = (lo + hi) / 2; 907193323Sed fde *f = vec->array[i]; 908193323Sed _Unwind_Ptr pc_begin, pc_range; 909193323Sed const char *p; 910193323Sed int encoding; 911193323Sed 912193323Sed encoding = get_fde_encoding (f); 913193323Sed p = read_encoded_value_with_base (encoding, 914193323Sed base_from_object (encoding, ob), 915193323Sed f->pc_begin, &pc_begin); 916193323Sed read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 917193323Sed 918193323Sed if ((_Unwind_Ptr) pc < pc_begin) 919193323Sed hi = i; 920193323Sed else if ((_Unwind_Ptr) pc >= pc_begin + pc_range) 921193323Sed lo = i + 1; 922193323Sed else 923193323Sed return f; 924193323Sed } 925193323Sed 926193323Sed return NULL; 927193323Sed} 928193323Sed 929193323Sedstatic fde * 930193323Sedsearch_object (struct object* ob, void *pc) 931193323Sed{ 932193323Sed /* If the data hasn't been sorted, try to do this now. We may have 933193323Sed more memory available than last time we tried. */ 934193323Sed if (! ob->s.b.sorted) 935193323Sed { 936193323Sed init_object (ob); 937193323Sed 938193323Sed /* Despite the above comment, the normal reason to get here is 939193323Sed that we've not processed this object before. A quick range 940193323Sed check is in order. */ 941193323Sed if (pc < ob->pc_begin) 942193323Sed return NULL; 943193323Sed } 944193323Sed 945193323Sed if (ob->s.b.sorted) 946193323Sed { 947193323Sed if (ob->s.b.mixed_encoding) 948193323Sed return binary_search_mixed_encoding_fdes (ob, pc); 949193323Sed else if (ob->s.b.encoding == DW_EH_PE_absptr) 950193323Sed return binary_search_unencoded_fdes (ob, pc); 951193323Sed else 952193323Sed return binary_search_single_encoding_fdes (ob, pc); 953193323Sed } 954193323Sed else 955193323Sed { 956193323Sed /* Long slow labourious linear search, cos we've no memory. */ 957193323Sed if (ob->s.b.from_array) 958198090Srdivacky { 959193323Sed fde **p; 960193323Sed for (p = ob->u.array; *p ; p++) 961193323Sed { 962193323Sed fde *f = linear_search_fdes (ob, *p, pc); 963193323Sed if (f) 964193323Sed return f; 965193323Sed } 966193323Sed return NULL; 967193323Sed } 968193323Sed else 969193323Sed return linear_search_fdes (ob, ob->u.single, pc); 970193323Sed } 971193323Sed} 972193323Sed 973193323Sedfde * 974193323Sed_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases) 975193323Sed{ 976193323Sed struct object *ob; 977193323Sed fde *f = NULL; 978193323Sed 979193323Sed init_object_mutex_once (); 980193323Sed __gthread_mutex_lock (&object_mutex); 981193323Sed 982193323Sed /* Linear search through the classified objects, to find the one 983193323Sed containing the pc. Note that pc_begin is sorted descending, and 984193323Sed we expect objects to be non-overlapping. */ 985193323Sed for (ob = seen_objects; ob; ob = ob->next) 986193323Sed if (pc >= ob->pc_begin) 987193323Sed { 988193323Sed f = search_object (ob, pc); 989193323Sed if (f) 990193323Sed goto fini; 991193323Sed break; 992193323Sed } 993193323Sed 994193323Sed /* Classify and search the objects we've not yet processed. */ 995193323Sed while ((ob = unseen_objects)) 996193323Sed { 997193323Sed struct object **p; 998193323Sed 999193323Sed unseen_objects = ob->next; 1000193323Sed f = search_object (ob, pc); 1001193323Sed 1002193323Sed /* Insert the object into the classified list. */ 1003195340Sed for (p = &seen_objects; *p ; p = &(*p)->next) 1004195340Sed if ((*p)->pc_begin < ob->pc_begin) 1005195340Sed break; 1006194612Sed ob->next = *p; 1007194612Sed *p = ob; 1008195340Sed 1009195340Sed if (f) 1010195340Sed goto fini; 1011195340Sed } 1012195340Sed 1013195340Sed fini: 1014194612Sed __gthread_mutex_unlock (&object_mutex); 1015193323Sed 1016193323Sed if (f) 1017195340Sed { 1018193323Sed int encoding; 1019193323Sed 1020193323Sed bases->tbase = ob->tbase; 1021193323Sed bases->dbase = ob->dbase; 1022193323Sed 1023193323Sed encoding = ob->s.b.encoding; 1024193323Sed if (ob->s.b.mixed_encoding) 1025193323Sed encoding = get_fde_encoding (f); 1026193323Sed read_encoded_value_with_base (encoding, base_from_object (encoding, ob), 1027193323Sed f->pc_begin, (_Unwind_Ptr *)&bases->func); 1028193323Sed } 1029193323Sed 1030193323Sed return f; 1031193323Sed} 1032193323Sed