190075Sobrien/* Subroutines needed for unwinding stack frames for exception handling. */ 2169689Skan/* Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 3169689Skan Free Software Foundation, Inc. 490075Sobrien Contributed by Jason Merrill <jason@cygnus.com>. 590075Sobrien 690075SobrienThis file is part of GCC. 790075Sobrien 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1290075Sobrien 1390075SobrienIn addition to the permissions in the GNU General Public License, the 1490075SobrienFree Software Foundation gives you unlimited permission to link the 1590075Sobriencompiled version of this file into combinations with other programs, 1690075Sobrienand to distribute those combinations without any restriction coming 1790075Sobrienfrom the use of this file. (The General Public License restrictions 1890075Sobriendo apply in other respects; for example, they cover modification of 1990075Sobrienthe file, and distribution when not linked into a combine 2090075Sobrienexecutable.) 2190075Sobrien 2290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 2390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 2490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 2590075Sobrienfor more details. 2690075Sobrien 2790075SobrienYou should have received a copy of the GNU General Public License 2890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 29169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 30169689Skan02110-1301, USA. */ 3190075Sobrien 3290075Sobrien#ifndef _Unwind_Find_FDE 3390075Sobrien#include "tconfig.h" 3490075Sobrien#include "tsystem.h" 35132718Skan#include "coretypes.h" 36132718Skan#include "tm.h" 3790075Sobrien#include "dwarf2.h" 3890075Sobrien#include "unwind.h" 3990075Sobrien#define NO_BASE_OF_ENCODED_VALUE 4090075Sobrien#include "unwind-pe.h" 4190075Sobrien#include "unwind-dw2-fde.h" 4290075Sobrien#include "gthr.h" 4390075Sobrien#endif 4490075Sobrien 4590075Sobrien/* The unseen_objects list contains objects that have been registered 4690075Sobrien but not yet categorized in any way. The seen_objects list has had 4790075Sobrien it's pc_begin and count fields initialized at minimum, and is sorted 4890075Sobrien by decreasing value of pc_begin. */ 4990075Sobrienstatic struct object *unseen_objects; 5090075Sobrienstatic struct object *seen_objects; 5190075Sobrien 5290075Sobrien#ifdef __GTHREAD_MUTEX_INIT 5390075Sobrienstatic __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT; 5490075Sobrien#else 5590075Sobrienstatic __gthread_mutex_t object_mutex; 5690075Sobrien#endif 5790075Sobrien 5890075Sobrien#ifdef __GTHREAD_MUTEX_INIT_FUNCTION 59117395Skanstatic void 6090075Sobrieninit_object_mutex (void) 6190075Sobrien{ 6290075Sobrien __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex); 6390075Sobrien} 6490075Sobrien 6590075Sobrienstatic void 6690075Sobrieninit_object_mutex_once (void) 6790075Sobrien{ 6890075Sobrien static __gthread_once_t once = __GTHREAD_ONCE_INIT; 6990075Sobrien __gthread_once (&once, init_object_mutex); 7090075Sobrien} 7190075Sobrien#else 7290075Sobrien#define init_object_mutex_once() 7390075Sobrien#endif 7490075Sobrien 7590075Sobrien/* Called from crtbegin.o to register the unwind info for an object. */ 7690075Sobrien 7790075Sobrienvoid 78132718Skan__register_frame_info_bases (const void *begin, struct object *ob, 7990075Sobrien void *tbase, void *dbase) 8090075Sobrien{ 8190075Sobrien /* If .eh_frame is empty, don't register at all. */ 82132718Skan if ((uword *) begin == 0 || *(uword *) begin == 0) 8390075Sobrien return; 8490075Sobrien 8590075Sobrien ob->pc_begin = (void *)-1; 8690075Sobrien ob->tbase = tbase; 8790075Sobrien ob->dbase = dbase; 8890075Sobrien ob->u.single = begin; 8990075Sobrien ob->s.i = 0; 9090075Sobrien ob->s.b.encoding = DW_EH_PE_omit; 91117395Skan#ifdef DWARF2_OBJECT_END_PTR_EXTENSION 92117395Skan ob->fde_end = NULL; 93117395Skan#endif 9490075Sobrien 9590075Sobrien init_object_mutex_once (); 9690075Sobrien __gthread_mutex_lock (&object_mutex); 9790075Sobrien 9890075Sobrien ob->next = unseen_objects; 9990075Sobrien unseen_objects = ob; 10090075Sobrien 10190075Sobrien __gthread_mutex_unlock (&object_mutex); 10290075Sobrien} 10390075Sobrien 10490075Sobrienvoid 105132718Skan__register_frame_info (const void *begin, struct object *ob) 10690075Sobrien{ 10790075Sobrien __register_frame_info_bases (begin, ob, 0, 0); 10890075Sobrien} 10990075Sobrien 11090075Sobrienvoid 11190075Sobrien__register_frame (void *begin) 11290075Sobrien{ 11390075Sobrien struct object *ob; 11490075Sobrien 11590075Sobrien /* If .eh_frame is empty, don't register at all. */ 11690075Sobrien if (*(uword *) begin == 0) 11790075Sobrien return; 11890075Sobrien 119132718Skan ob = malloc (sizeof (struct object)); 120117395Skan __register_frame_info (begin, ob); 12190075Sobrien} 12290075Sobrien 12390075Sobrien/* Similar, but BEGIN is actually a pointer to a table of unwind entries 12490075Sobrien for different translation units. Called from the file generated by 12590075Sobrien collect2. */ 12690075Sobrien 12790075Sobrienvoid 12890075Sobrien__register_frame_info_table_bases (void *begin, struct object *ob, 12990075Sobrien void *tbase, void *dbase) 13090075Sobrien{ 13190075Sobrien ob->pc_begin = (void *)-1; 13290075Sobrien ob->tbase = tbase; 13390075Sobrien ob->dbase = dbase; 13490075Sobrien ob->u.array = begin; 13590075Sobrien ob->s.i = 0; 13690075Sobrien ob->s.b.from_array = 1; 13790075Sobrien ob->s.b.encoding = DW_EH_PE_omit; 13890075Sobrien 13990075Sobrien init_object_mutex_once (); 14090075Sobrien __gthread_mutex_lock (&object_mutex); 14190075Sobrien 14290075Sobrien ob->next = unseen_objects; 14390075Sobrien unseen_objects = ob; 14490075Sobrien 14590075Sobrien __gthread_mutex_unlock (&object_mutex); 14690075Sobrien} 14790075Sobrien 14890075Sobrienvoid 14990075Sobrien__register_frame_info_table (void *begin, struct object *ob) 15090075Sobrien{ 15190075Sobrien __register_frame_info_table_bases (begin, ob, 0, 0); 15290075Sobrien} 15390075Sobrien 15490075Sobrienvoid 15590075Sobrien__register_frame_table (void *begin) 15690075Sobrien{ 157132718Skan struct object *ob = malloc (sizeof (struct object)); 15890075Sobrien __register_frame_info_table (begin, ob); 15990075Sobrien} 16090075Sobrien 16190075Sobrien/* Called from crtbegin.o to deregister the unwind info for an object. */ 16290075Sobrien/* ??? Glibc has for a while now exported __register_frame_info and 16390075Sobrien __deregister_frame_info. If we call __register_frame_info_bases 16490075Sobrien from crtbegin (wherein it is declared weak), and this object does 16590075Sobrien not get pulled from libgcc.a for other reasons, then the 16690075Sobrien invocation of __deregister_frame_info will be resolved from glibc. 167169689Skan Since the registration did not happen there, we'll die. 16890075Sobrien 16990075Sobrien Therefore, declare a new deregistration entry point that does the 170117395Skan exact same thing, but will resolve to the same library as 17190075Sobrien implements __register_frame_info_bases. */ 17290075Sobrien 17390075Sobrienvoid * 174132718Skan__deregister_frame_info_bases (const void *begin) 17590075Sobrien{ 17690075Sobrien struct object **p; 17790075Sobrien struct object *ob = 0; 17890075Sobrien 17990075Sobrien /* If .eh_frame is empty, we haven't registered. */ 180132718Skan if ((uword *) begin == 0 || *(uword *) begin == 0) 18190075Sobrien return ob; 18290075Sobrien 18390075Sobrien init_object_mutex_once (); 18490075Sobrien __gthread_mutex_lock (&object_mutex); 18590075Sobrien 18690075Sobrien for (p = &unseen_objects; *p ; p = &(*p)->next) 18790075Sobrien if ((*p)->u.single == begin) 18890075Sobrien { 18990075Sobrien ob = *p; 19090075Sobrien *p = ob->next; 19190075Sobrien goto out; 19290075Sobrien } 19390075Sobrien 19490075Sobrien for (p = &seen_objects; *p ; p = &(*p)->next) 19590075Sobrien if ((*p)->s.b.sorted) 19690075Sobrien { 19790075Sobrien if ((*p)->u.sort->orig_data == begin) 19890075Sobrien { 19990075Sobrien ob = *p; 20090075Sobrien *p = ob->next; 20190075Sobrien free (ob->u.sort); 20290075Sobrien goto out; 20390075Sobrien } 20490075Sobrien } 20590075Sobrien else 20690075Sobrien { 20790075Sobrien if ((*p)->u.single == begin) 20890075Sobrien { 20990075Sobrien ob = *p; 21090075Sobrien *p = ob->next; 21190075Sobrien goto out; 21290075Sobrien } 21390075Sobrien } 21490075Sobrien 21590075Sobrien out: 21690075Sobrien __gthread_mutex_unlock (&object_mutex); 217169689Skan gcc_assert (ob); 21890075Sobrien return (void *) ob; 21990075Sobrien} 22090075Sobrien 22190075Sobrienvoid * 222132718Skan__deregister_frame_info (const void *begin) 22390075Sobrien{ 22490075Sobrien return __deregister_frame_info_bases (begin); 22590075Sobrien} 22690075Sobrien 22790075Sobrienvoid 22890075Sobrien__deregister_frame (void *begin) 22990075Sobrien{ 23090075Sobrien /* If .eh_frame is empty, we haven't registered. */ 23190075Sobrien if (*(uword *) begin != 0) 23290075Sobrien free (__deregister_frame_info (begin)); 23390075Sobrien} 23490075Sobrien 23590075Sobrien 23690075Sobrien/* Like base_of_encoded_value, but take the base from a struct object 23790075Sobrien instead of an _Unwind_Context. */ 23890075Sobrien 23990075Sobrienstatic _Unwind_Ptr 24090075Sobrienbase_from_object (unsigned char encoding, struct object *ob) 24190075Sobrien{ 24290075Sobrien if (encoding == DW_EH_PE_omit) 24390075Sobrien return 0; 24490075Sobrien 24590075Sobrien switch (encoding & 0x70) 24690075Sobrien { 24790075Sobrien case DW_EH_PE_absptr: 24890075Sobrien case DW_EH_PE_pcrel: 24990075Sobrien case DW_EH_PE_aligned: 25090075Sobrien return 0; 25190075Sobrien 25290075Sobrien case DW_EH_PE_textrel: 25390075Sobrien return (_Unwind_Ptr) ob->tbase; 25490075Sobrien case DW_EH_PE_datarel: 25590075Sobrien return (_Unwind_Ptr) ob->dbase; 256169689Skan default: 257169689Skan gcc_unreachable (); 25890075Sobrien } 25990075Sobrien} 26090075Sobrien 26190075Sobrien/* Return the FDE pointer encoding from the CIE. */ 26290075Sobrien/* ??? This is a subset of extract_cie_info from unwind-dw2.c. */ 26390075Sobrien 26490075Sobrienstatic int 265132718Skanget_cie_encoding (const struct dwarf_cie *cie) 26690075Sobrien{ 26790075Sobrien const unsigned char *aug, *p; 26890075Sobrien _Unwind_Ptr dummy; 26990075Sobrien _Unwind_Word utmp; 27090075Sobrien _Unwind_Sword stmp; 27190075Sobrien 27290075Sobrien aug = cie->augmentation; 27390075Sobrien if (aug[0] != 'z') 27490075Sobrien return DW_EH_PE_absptr; 27590075Sobrien 276169689Skan p = aug + strlen ((const char *)aug) + 1; /* Skip the augmentation string. */ 27790075Sobrien p = read_uleb128 (p, &utmp); /* Skip code alignment. */ 27890075Sobrien p = read_sleb128 (p, &stmp); /* Skip data alignment. */ 279169689Skan if (cie->version == 1) /* Skip return address column. */ 280169689Skan p++; 281169689Skan else 282169689Skan p = read_uleb128 (p, &utmp); 28390075Sobrien 28490075Sobrien aug++; /* Skip 'z' */ 28590075Sobrien p = read_uleb128 (p, &utmp); /* Skip augmentation length. */ 28690075Sobrien while (1) 28790075Sobrien { 28890075Sobrien /* This is what we're looking for. */ 28990075Sobrien if (*aug == 'R') 29090075Sobrien return *p; 29190075Sobrien /* Personality encoding and pointer. */ 29290075Sobrien else if (*aug == 'P') 29390075Sobrien { 29490075Sobrien /* ??? Avoid dereferencing indirect pointers, since we're 29590075Sobrien faking the base address. Gotta keep DW_EH_PE_aligned 29690075Sobrien intact, however. */ 29790075Sobrien p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy); 29890075Sobrien } 29990075Sobrien /* LSDA encoding. */ 30090075Sobrien else if (*aug == 'L') 30190075Sobrien p++; 30290075Sobrien /* Otherwise end of string, or unknown augmentation. */ 30390075Sobrien else 30490075Sobrien return DW_EH_PE_absptr; 30590075Sobrien aug++; 30690075Sobrien } 30790075Sobrien} 30890075Sobrien 30990075Sobrienstatic inline int 310132718Skanget_fde_encoding (const struct dwarf_fde *f) 31190075Sobrien{ 31290075Sobrien return get_cie_encoding (get_cie (f)); 31390075Sobrien} 31490075Sobrien 31590075Sobrien 31690075Sobrien/* Sorting an array of FDEs by address. 31790075Sobrien (Ideally we would have the linker sort the FDEs so we don't have to do 31890075Sobrien it at run time. But the linkers are not yet prepared for this.) */ 31990075Sobrien 32090075Sobrien/* Comparison routines. Three variants of increasing complexity. */ 32190075Sobrien 32290075Sobrienstatic int 32390075Sobrienfde_unencoded_compare (struct object *ob __attribute__((unused)), 324132718Skan const fde *x, const fde *y) 32590075Sobrien{ 32690075Sobrien _Unwind_Ptr x_ptr = *(_Unwind_Ptr *) x->pc_begin; 32790075Sobrien _Unwind_Ptr y_ptr = *(_Unwind_Ptr *) y->pc_begin; 32890075Sobrien 32990075Sobrien if (x_ptr > y_ptr) 33090075Sobrien return 1; 33190075Sobrien if (x_ptr < y_ptr) 33290075Sobrien return -1; 33390075Sobrien return 0; 33490075Sobrien} 33590075Sobrien 33690075Sobrienstatic int 337132718Skanfde_single_encoding_compare (struct object *ob, const fde *x, const fde *y) 33890075Sobrien{ 33990075Sobrien _Unwind_Ptr base, x_ptr, y_ptr; 34090075Sobrien 34190075Sobrien base = base_from_object (ob->s.b.encoding, ob); 34290075Sobrien read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr); 34390075Sobrien read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr); 34490075Sobrien 34590075Sobrien if (x_ptr > y_ptr) 34690075Sobrien return 1; 34790075Sobrien if (x_ptr < y_ptr) 34890075Sobrien return -1; 34990075Sobrien return 0; 35090075Sobrien} 35190075Sobrien 35290075Sobrienstatic int 353132718Skanfde_mixed_encoding_compare (struct object *ob, const fde *x, const fde *y) 35490075Sobrien{ 35590075Sobrien int x_encoding, y_encoding; 35690075Sobrien _Unwind_Ptr x_ptr, y_ptr; 35790075Sobrien 35890075Sobrien x_encoding = get_fde_encoding (x); 35990075Sobrien read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob), 36090075Sobrien x->pc_begin, &x_ptr); 36190075Sobrien 36290075Sobrien y_encoding = get_fde_encoding (y); 36390075Sobrien read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob), 36490075Sobrien y->pc_begin, &y_ptr); 36590075Sobrien 36690075Sobrien if (x_ptr > y_ptr) 36790075Sobrien return 1; 36890075Sobrien if (x_ptr < y_ptr) 36990075Sobrien return -1; 37090075Sobrien return 0; 37190075Sobrien} 37290075Sobrien 373132718Skantypedef int (*fde_compare_t) (struct object *, const fde *, const fde *); 37490075Sobrien 37590075Sobrien 37690075Sobrien/* This is a special mix of insertion sort and heap sort, optimized for 37790075Sobrien the data sets that actually occur. They look like 37890075Sobrien 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130. 37990075Sobrien I.e. a linearly increasing sequence (coming from functions in the text 38090075Sobrien section), with additionally a few unordered elements (coming from functions 38190075Sobrien in gnu_linkonce sections) whose values are higher than the values in the 38290075Sobrien surrounding linear sequence (but not necessarily higher than the values 38390075Sobrien at the end of the linear sequence!). 38490075Sobrien The worst-case total run time is O(N) + O(n log (n)), where N is the 38590075Sobrien total number of FDEs and n is the number of erratic ones. */ 38690075Sobrien 38790075Sobrienstruct fde_accumulator 38890075Sobrien{ 38990075Sobrien struct fde_vector *linear; 39090075Sobrien struct fde_vector *erratic; 39190075Sobrien}; 39290075Sobrien 39390075Sobrienstatic inline int 39490075Sobrienstart_fde_sort (struct fde_accumulator *accu, size_t count) 39590075Sobrien{ 39690075Sobrien size_t size; 39790075Sobrien if (! count) 39890075Sobrien return 0; 39990075Sobrien 400132718Skan size = sizeof (struct fde_vector) + sizeof (const fde *) * count; 401132718Skan if ((accu->linear = malloc (size))) 40290075Sobrien { 40390075Sobrien accu->linear->count = 0; 404132718Skan if ((accu->erratic = malloc (size))) 40590075Sobrien accu->erratic->count = 0; 40690075Sobrien return 1; 40790075Sobrien } 40890075Sobrien else 409117395Skan return 0; 41090075Sobrien} 41190075Sobrien 41290075Sobrienstatic inline void 413132718Skanfde_insert (struct fde_accumulator *accu, const fde *this_fde) 41490075Sobrien{ 41590075Sobrien if (accu->linear) 41690075Sobrien accu->linear->array[accu->linear->count++] = this_fde; 41790075Sobrien} 41890075Sobrien 41990075Sobrien/* Split LINEAR into a linear sequence with low values and an erratic 42090075Sobrien sequence with high values, put the linear one (of longest possible 42190075Sobrien length) into LINEAR and the erratic one into ERRATIC. This is O(N). 422117395Skan 42390075Sobrien Because the longest linear sequence we are trying to locate within the 42490075Sobrien incoming LINEAR array can be interspersed with (high valued) erratic 42590075Sobrien entries. We construct a chain indicating the sequenced entries. 42690075Sobrien To avoid having to allocate this chain, we overlay it onto the space of 42790075Sobrien the ERRATIC array during construction. A final pass iterates over the 42890075Sobrien chain to determine what should be placed in the ERRATIC array, and 42990075Sobrien what is the linear sequence. This overlay is safe from aliasing. */ 43090075Sobrien 43190075Sobrienstatic inline void 43290075Sobrienfde_split (struct object *ob, fde_compare_t fde_compare, 43390075Sobrien struct fde_vector *linear, struct fde_vector *erratic) 43490075Sobrien{ 435132718Skan static const fde *marker; 43690075Sobrien size_t count = linear->count; 437132718Skan const fde **chain_end = ▮ 43890075Sobrien size_t i, j, k; 43990075Sobrien 44090075Sobrien /* This should optimize out, but it is wise to make sure this assumption 44190075Sobrien is correct. Should these have different sizes, we cannot cast between 44290075Sobrien them and the overlaying onto ERRATIC will not work. */ 443169689Skan gcc_assert (sizeof (const fde *) == sizeof (const fde **)); 444117395Skan 44590075Sobrien for (i = 0; i < count; i++) 44690075Sobrien { 447132718Skan const fde **probe; 448117395Skan 44990075Sobrien for (probe = chain_end; 450117395Skan probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0; 451117395Skan probe = chain_end) 452117395Skan { 453132718Skan chain_end = (const fde **) erratic->array[probe - linear->array]; 454117395Skan erratic->array[probe - linear->array] = NULL; 455117395Skan } 456132718Skan erratic->array[i] = (const fde *) chain_end; 45790075Sobrien chain_end = &linear->array[i]; 45890075Sobrien } 45990075Sobrien 46090075Sobrien /* Each entry in LINEAR which is part of the linear sequence we have 46190075Sobrien discovered will correspond to a non-NULL entry in the chain we built in 46290075Sobrien the ERRATIC array. */ 46390075Sobrien for (i = j = k = 0; i < count; i++) 46490075Sobrien if (erratic->array[i]) 46590075Sobrien linear->array[j++] = linear->array[i]; 46690075Sobrien else 46790075Sobrien erratic->array[k++] = linear->array[i]; 46890075Sobrien linear->count = j; 46990075Sobrien erratic->count = k; 47090075Sobrien} 47190075Sobrien 472132718Skan#define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0) 473132718Skan 474132718Skan/* Convert a semi-heap to a heap. A semi-heap is a heap except possibly 475132718Skan for the first (root) node; push it down to its rightful place. */ 476132718Skan 477132718Skanstatic void 478132718Skanframe_downheap (struct object *ob, fde_compare_t fde_compare, const fde **a, 479132718Skan int lo, int hi) 480132718Skan{ 481132718Skan int i, j; 482132718Skan 483132718Skan for (i = lo, j = 2*i+1; 484132718Skan j < hi; 485132718Skan j = 2*i+1) 486132718Skan { 487132718Skan if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0) 488132718Skan ++j; 489132718Skan 490132718Skan if (fde_compare (ob, a[i], a[j]) < 0) 491132718Skan { 492132718Skan SWAP (a[i], a[j]); 493132718Skan i = j; 494132718Skan } 495132718Skan else 496132718Skan break; 497132718Skan } 498132718Skan} 499132718Skan 50090075Sobrien/* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must 50190075Sobrien use a name that does not conflict. */ 50290075Sobrien 50390075Sobrienstatic void 50490075Sobrienframe_heapsort (struct object *ob, fde_compare_t fde_compare, 50590075Sobrien struct fde_vector *erratic) 50690075Sobrien{ 50790075Sobrien /* For a description of this algorithm, see: 50890075Sobrien Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed., 50990075Sobrien p. 60-61. */ 510132718Skan const fde ** a = erratic->array; 51190075Sobrien /* A portion of the array is called a "heap" if for all i>=0: 51290075Sobrien If i and 2i+1 are valid indices, then a[i] >= a[2i+1]. 51390075Sobrien If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */ 51490075Sobrien size_t n = erratic->count; 515132718Skan int m; 51690075Sobrien 517132718Skan /* Expand our heap incrementally from the end of the array, heapifying 518132718Skan each resulting semi-heap as we go. After each step, a[m] is the top 519132718Skan of a heap. */ 520132718Skan for (m = n/2-1; m >= 0; --m) 521132718Skan frame_downheap (ob, fde_compare, a, m, n); 522132718Skan 523132718Skan /* Shrink our heap incrementally from the end of the array, first 524132718Skan swapping out the largest element a[0] and then re-heapifying the 525132718Skan resulting semi-heap. After each step, a[0..m) is a heap. */ 526132718Skan for (m = n-1; m >= 1; --m) 52790075Sobrien { 528132718Skan SWAP (a[0], a[m]); 529132718Skan frame_downheap (ob, fde_compare, a, 0, m); 53090075Sobrien } 53190075Sobrien#undef SWAP 53290075Sobrien} 53390075Sobrien 53490075Sobrien/* Merge V1 and V2, both sorted, and put the result into V1. */ 53590075Sobrienstatic inline void 53690075Sobrienfde_merge (struct object *ob, fde_compare_t fde_compare, 53790075Sobrien struct fde_vector *v1, struct fde_vector *v2) 53890075Sobrien{ 53990075Sobrien size_t i1, i2; 540132718Skan const fde * fde2; 54190075Sobrien 54290075Sobrien i2 = v2->count; 54390075Sobrien if (i2 > 0) 54490075Sobrien { 54590075Sobrien i1 = v1->count; 54690075Sobrien do 54790075Sobrien { 54890075Sobrien i2--; 54990075Sobrien fde2 = v2->array[i2]; 55090075Sobrien while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0) 55190075Sobrien { 55290075Sobrien v1->array[i1+i2] = v1->array[i1-1]; 55390075Sobrien i1--; 55490075Sobrien } 555117395Skan v1->array[i1+i2] = fde2; 55690075Sobrien } 55790075Sobrien while (i2 > 0); 55890075Sobrien v1->count += v2->count; 55990075Sobrien } 56090075Sobrien} 56190075Sobrien 56290075Sobrienstatic inline void 56390075Sobrienend_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count) 56490075Sobrien{ 56590075Sobrien fde_compare_t fde_compare; 56690075Sobrien 567169689Skan gcc_assert (!accu->linear || accu->linear->count == count); 56890075Sobrien 56990075Sobrien if (ob->s.b.mixed_encoding) 57090075Sobrien fde_compare = fde_mixed_encoding_compare; 57190075Sobrien else if (ob->s.b.encoding == DW_EH_PE_absptr) 57290075Sobrien fde_compare = fde_unencoded_compare; 57390075Sobrien else 57490075Sobrien fde_compare = fde_single_encoding_compare; 57590075Sobrien 57690075Sobrien if (accu->erratic) 57790075Sobrien { 57890075Sobrien fde_split (ob, fde_compare, accu->linear, accu->erratic); 579169689Skan gcc_assert (accu->linear->count + accu->erratic->count == count); 58090075Sobrien frame_heapsort (ob, fde_compare, accu->erratic); 58190075Sobrien fde_merge (ob, fde_compare, accu->linear, accu->erratic); 58290075Sobrien free (accu->erratic); 58390075Sobrien } 58490075Sobrien else 58590075Sobrien { 58690075Sobrien /* We've not managed to malloc an erratic array, 58790075Sobrien so heap sort in the linear one. */ 58890075Sobrien frame_heapsort (ob, fde_compare, accu->linear); 58990075Sobrien } 59090075Sobrien} 59190075Sobrien 59290075Sobrien 593117395Skan/* Update encoding, mixed_encoding, and pc_begin for OB for the 59490075Sobrien fde array beginning at THIS_FDE. Return the number of fdes 59590075Sobrien encountered along the way. */ 59690075Sobrien 59790075Sobrienstatic size_t 598132718Skanclassify_object_over_fdes (struct object *ob, const fde *this_fde) 59990075Sobrien{ 600132718Skan const struct dwarf_cie *last_cie = 0; 60190075Sobrien size_t count = 0; 60290075Sobrien int encoding = DW_EH_PE_absptr; 60390075Sobrien _Unwind_Ptr base = 0; 60490075Sobrien 605117395Skan for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 60690075Sobrien { 607132718Skan const struct dwarf_cie *this_cie; 60890075Sobrien _Unwind_Ptr mask, pc_begin; 60990075Sobrien 61090075Sobrien /* Skip CIEs. */ 61190075Sobrien if (this_fde->CIE_delta == 0) 61290075Sobrien continue; 61390075Sobrien 61490075Sobrien /* Determine the encoding for this FDE. Note mixed encoded 61590075Sobrien objects for later. */ 61690075Sobrien this_cie = get_cie (this_fde); 61790075Sobrien if (this_cie != last_cie) 61890075Sobrien { 61990075Sobrien last_cie = this_cie; 62090075Sobrien encoding = get_cie_encoding (this_cie); 62190075Sobrien base = base_from_object (encoding, ob); 62290075Sobrien if (ob->s.b.encoding == DW_EH_PE_omit) 62390075Sobrien ob->s.b.encoding = encoding; 62490075Sobrien else if (ob->s.b.encoding != encoding) 62590075Sobrien ob->s.b.mixed_encoding = 1; 62690075Sobrien } 62790075Sobrien 62890075Sobrien read_encoded_value_with_base (encoding, base, this_fde->pc_begin, 62990075Sobrien &pc_begin); 63090075Sobrien 63190075Sobrien /* Take care to ignore link-once functions that were removed. 63290075Sobrien In these cases, the function address will be NULL, but if 63390075Sobrien the encoding is smaller than a pointer a true NULL may not 63490075Sobrien be representable. Assume 0 in the representable bits is NULL. */ 63590075Sobrien mask = size_of_encoded_value (encoding); 63690075Sobrien if (mask < sizeof (void *)) 63790075Sobrien mask = (1L << (mask << 3)) - 1; 63890075Sobrien else 63990075Sobrien mask = -1; 64090075Sobrien 64190075Sobrien if ((pc_begin & mask) == 0) 64290075Sobrien continue; 64390075Sobrien 64490075Sobrien count += 1; 64590075Sobrien if ((void *) pc_begin < ob->pc_begin) 64690075Sobrien ob->pc_begin = (void *) pc_begin; 64790075Sobrien } 64890075Sobrien 64990075Sobrien return count; 65090075Sobrien} 65190075Sobrien 65290075Sobrienstatic void 653132718Skanadd_fdes (struct object *ob, struct fde_accumulator *accu, const fde *this_fde) 65490075Sobrien{ 655132718Skan const struct dwarf_cie *last_cie = 0; 65690075Sobrien int encoding = ob->s.b.encoding; 65790075Sobrien _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob); 65890075Sobrien 659117395Skan for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 66090075Sobrien { 661132718Skan const struct dwarf_cie *this_cie; 66290075Sobrien 66390075Sobrien /* Skip CIEs. */ 66490075Sobrien if (this_fde->CIE_delta == 0) 66590075Sobrien continue; 66690075Sobrien 66790075Sobrien if (ob->s.b.mixed_encoding) 66890075Sobrien { 66990075Sobrien /* Determine the encoding for this FDE. Note mixed encoded 67090075Sobrien objects for later. */ 67190075Sobrien this_cie = get_cie (this_fde); 67290075Sobrien if (this_cie != last_cie) 67390075Sobrien { 67490075Sobrien last_cie = this_cie; 67590075Sobrien encoding = get_cie_encoding (this_cie); 67690075Sobrien base = base_from_object (encoding, ob); 67790075Sobrien } 67890075Sobrien } 67990075Sobrien 68090075Sobrien if (encoding == DW_EH_PE_absptr) 68190075Sobrien { 68290075Sobrien if (*(_Unwind_Ptr *) this_fde->pc_begin == 0) 68390075Sobrien continue; 68490075Sobrien } 68590075Sobrien else 68690075Sobrien { 68790075Sobrien _Unwind_Ptr pc_begin, mask; 68890075Sobrien 68990075Sobrien read_encoded_value_with_base (encoding, base, this_fde->pc_begin, 69090075Sobrien &pc_begin); 69190075Sobrien 69290075Sobrien /* Take care to ignore link-once functions that were removed. 69390075Sobrien In these cases, the function address will be NULL, but if 69490075Sobrien the encoding is smaller than a pointer a true NULL may not 69590075Sobrien be representable. Assume 0 in the representable bits is NULL. */ 69690075Sobrien mask = size_of_encoded_value (encoding); 69790075Sobrien if (mask < sizeof (void *)) 69890075Sobrien mask = (1L << (mask << 3)) - 1; 69990075Sobrien else 70090075Sobrien mask = -1; 70190075Sobrien 70290075Sobrien if ((pc_begin & mask) == 0) 70390075Sobrien continue; 70490075Sobrien } 70590075Sobrien 70690075Sobrien fde_insert (accu, this_fde); 70790075Sobrien } 70890075Sobrien} 70990075Sobrien 71090075Sobrien/* Set up a sorted array of pointers to FDEs for a loaded object. We 71190075Sobrien count up the entries before allocating the array because it's likely to 71290075Sobrien be faster. We can be called multiple times, should we have failed to 71390075Sobrien allocate a sorted fde array on a previous occasion. */ 71490075Sobrien 71590075Sobrienstatic inline void 71690075Sobrieninit_object (struct object* ob) 71790075Sobrien{ 71890075Sobrien struct fde_accumulator accu; 71990075Sobrien size_t count; 72090075Sobrien 72190075Sobrien count = ob->s.b.count; 72290075Sobrien if (count == 0) 72390075Sobrien { 72490075Sobrien if (ob->s.b.from_array) 72590075Sobrien { 72690075Sobrien fde **p = ob->u.array; 72790075Sobrien for (count = 0; *p; ++p) 72890075Sobrien count += classify_object_over_fdes (ob, *p); 72990075Sobrien } 73090075Sobrien else 73190075Sobrien count = classify_object_over_fdes (ob, ob->u.single); 73290075Sobrien 73390075Sobrien /* The count field we have in the main struct object is somewhat 73490075Sobrien limited, but should suffice for virtually all cases. If the 73590075Sobrien counted value doesn't fit, re-write a zero. The worst that 73690075Sobrien happens is that we re-count next time -- admittedly non-trivial 73790075Sobrien in that this implies some 2M fdes, but at least we function. */ 73890075Sobrien ob->s.b.count = count; 73990075Sobrien if (ob->s.b.count != count) 74090075Sobrien ob->s.b.count = 0; 74190075Sobrien } 74290075Sobrien 74390075Sobrien if (!start_fde_sort (&accu, count)) 74490075Sobrien return; 74590075Sobrien 74690075Sobrien if (ob->s.b.from_array) 74790075Sobrien { 74890075Sobrien fde **p; 74990075Sobrien for (p = ob->u.array; *p; ++p) 750117395Skan add_fdes (ob, &accu, *p); 75190075Sobrien } 75290075Sobrien else 75390075Sobrien add_fdes (ob, &accu, ob->u.single); 75490075Sobrien 75590075Sobrien end_fde_sort (ob, &accu, count); 75690075Sobrien 75790075Sobrien /* Save the original fde pointer, since this is the key by which the 75890075Sobrien DSO will deregister the object. */ 75990075Sobrien accu.linear->orig_data = ob->u.single; 76090075Sobrien ob->u.sort = accu.linear; 76190075Sobrien 76290075Sobrien ob->s.b.sorted = 1; 76390075Sobrien} 76490075Sobrien 76590075Sobrien/* A linear search through a set of FDEs for the given PC. This is 76690075Sobrien used when there was insufficient memory to allocate and sort an 76790075Sobrien array. */ 76890075Sobrien 769132718Skanstatic const fde * 770132718Skanlinear_search_fdes (struct object *ob, const fde *this_fde, void *pc) 77190075Sobrien{ 772132718Skan const struct dwarf_cie *last_cie = 0; 77390075Sobrien int encoding = ob->s.b.encoding; 77490075Sobrien _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob); 77590075Sobrien 776117395Skan for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde)) 77790075Sobrien { 778132718Skan const struct dwarf_cie *this_cie; 77990075Sobrien _Unwind_Ptr pc_begin, pc_range; 78090075Sobrien 78190075Sobrien /* Skip CIEs. */ 78290075Sobrien if (this_fde->CIE_delta == 0) 78390075Sobrien continue; 78490075Sobrien 78590075Sobrien if (ob->s.b.mixed_encoding) 78690075Sobrien { 78790075Sobrien /* Determine the encoding for this FDE. Note mixed encoded 78890075Sobrien objects for later. */ 78990075Sobrien this_cie = get_cie (this_fde); 79090075Sobrien if (this_cie != last_cie) 79190075Sobrien { 79290075Sobrien last_cie = this_cie; 79390075Sobrien encoding = get_cie_encoding (this_cie); 79490075Sobrien base = base_from_object (encoding, ob); 79590075Sobrien } 79690075Sobrien } 79790075Sobrien 79890075Sobrien if (encoding == DW_EH_PE_absptr) 79990075Sobrien { 80090075Sobrien pc_begin = ((_Unwind_Ptr *) this_fde->pc_begin)[0]; 80190075Sobrien pc_range = ((_Unwind_Ptr *) this_fde->pc_begin)[1]; 80290075Sobrien if (pc_begin == 0) 80390075Sobrien continue; 80490075Sobrien } 80590075Sobrien else 80690075Sobrien { 80790075Sobrien _Unwind_Ptr mask; 808169689Skan const unsigned char *p; 80990075Sobrien 81090075Sobrien p = read_encoded_value_with_base (encoding, base, 81190075Sobrien this_fde->pc_begin, &pc_begin); 81290075Sobrien read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 81390075Sobrien 81490075Sobrien /* Take care to ignore link-once functions that were removed. 81590075Sobrien In these cases, the function address will be NULL, but if 81690075Sobrien the encoding is smaller than a pointer a true NULL may not 81790075Sobrien be representable. Assume 0 in the representable bits is NULL. */ 81890075Sobrien mask = size_of_encoded_value (encoding); 81990075Sobrien if (mask < sizeof (void *)) 82090075Sobrien mask = (1L << (mask << 3)) - 1; 82190075Sobrien else 82290075Sobrien mask = -1; 82390075Sobrien 82490075Sobrien if ((pc_begin & mask) == 0) 82590075Sobrien continue; 82690075Sobrien } 82790075Sobrien 82890075Sobrien if ((_Unwind_Ptr) pc - pc_begin < pc_range) 829117395Skan return this_fde; 83090075Sobrien } 83190075Sobrien 83290075Sobrien return NULL; 83390075Sobrien} 83490075Sobrien 83590075Sobrien/* Binary search for an FDE containing the given PC. Here are three 83690075Sobrien implementations of increasing complexity. */ 83790075Sobrien 838132718Skanstatic inline const fde * 83990075Sobrienbinary_search_unencoded_fdes (struct object *ob, void *pc) 84090075Sobrien{ 84190075Sobrien struct fde_vector *vec = ob->u.sort; 84290075Sobrien size_t lo, hi; 843117395Skan 84490075Sobrien for (lo = 0, hi = vec->count; lo < hi; ) 84590075Sobrien { 84690075Sobrien size_t i = (lo + hi) / 2; 847132718Skan const fde *f = vec->array[i]; 84890075Sobrien void *pc_begin; 84990075Sobrien uaddr pc_range; 85090075Sobrien 85190075Sobrien pc_begin = ((void **) f->pc_begin)[0]; 85290075Sobrien pc_range = ((uaddr *) f->pc_begin)[1]; 85390075Sobrien 85490075Sobrien if (pc < pc_begin) 85590075Sobrien hi = i; 85690075Sobrien else if (pc >= pc_begin + pc_range) 85790075Sobrien lo = i + 1; 85890075Sobrien else 85990075Sobrien return f; 86090075Sobrien } 86190075Sobrien 86290075Sobrien return NULL; 86390075Sobrien} 86490075Sobrien 865132718Skanstatic inline const fde * 86690075Sobrienbinary_search_single_encoding_fdes (struct object *ob, void *pc) 86790075Sobrien{ 86890075Sobrien struct fde_vector *vec = ob->u.sort; 86990075Sobrien int encoding = ob->s.b.encoding; 87090075Sobrien _Unwind_Ptr base = base_from_object (encoding, ob); 87190075Sobrien size_t lo, hi; 872117395Skan 87390075Sobrien for (lo = 0, hi = vec->count; lo < hi; ) 87490075Sobrien { 87590075Sobrien size_t i = (lo + hi) / 2; 876132718Skan const fde *f = vec->array[i]; 87790075Sobrien _Unwind_Ptr pc_begin, pc_range; 878169689Skan const unsigned char *p; 87990075Sobrien 88090075Sobrien p = read_encoded_value_with_base (encoding, base, f->pc_begin, 88190075Sobrien &pc_begin); 88290075Sobrien read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 88390075Sobrien 88490075Sobrien if ((_Unwind_Ptr) pc < pc_begin) 88590075Sobrien hi = i; 88690075Sobrien else if ((_Unwind_Ptr) pc >= pc_begin + pc_range) 88790075Sobrien lo = i + 1; 88890075Sobrien else 88990075Sobrien return f; 89090075Sobrien } 89190075Sobrien 89290075Sobrien return NULL; 89390075Sobrien} 89490075Sobrien 895132718Skanstatic inline const fde * 89690075Sobrienbinary_search_mixed_encoding_fdes (struct object *ob, void *pc) 89790075Sobrien{ 89890075Sobrien struct fde_vector *vec = ob->u.sort; 89990075Sobrien size_t lo, hi; 900117395Skan 90190075Sobrien for (lo = 0, hi = vec->count; lo < hi; ) 90290075Sobrien { 90390075Sobrien size_t i = (lo + hi) / 2; 904132718Skan const fde *f = vec->array[i]; 90590075Sobrien _Unwind_Ptr pc_begin, pc_range; 906169689Skan const unsigned char *p; 90790075Sobrien int encoding; 90890075Sobrien 90990075Sobrien encoding = get_fde_encoding (f); 91090075Sobrien p = read_encoded_value_with_base (encoding, 91190075Sobrien base_from_object (encoding, ob), 91290075Sobrien f->pc_begin, &pc_begin); 91390075Sobrien read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); 91490075Sobrien 91590075Sobrien if ((_Unwind_Ptr) pc < pc_begin) 91690075Sobrien hi = i; 91790075Sobrien else if ((_Unwind_Ptr) pc >= pc_begin + pc_range) 91890075Sobrien lo = i + 1; 91990075Sobrien else 92090075Sobrien return f; 92190075Sobrien } 92290075Sobrien 92390075Sobrien return NULL; 92490075Sobrien} 92590075Sobrien 926132718Skanstatic const fde * 92790075Sobriensearch_object (struct object* ob, void *pc) 92890075Sobrien{ 92990075Sobrien /* If the data hasn't been sorted, try to do this now. We may have 93090075Sobrien more memory available than last time we tried. */ 93190075Sobrien if (! ob->s.b.sorted) 93290075Sobrien { 93390075Sobrien init_object (ob); 93490075Sobrien 93590075Sobrien /* Despite the above comment, the normal reason to get here is 93690075Sobrien that we've not processed this object before. A quick range 93790075Sobrien check is in order. */ 93890075Sobrien if (pc < ob->pc_begin) 93990075Sobrien return NULL; 94090075Sobrien } 94190075Sobrien 94290075Sobrien if (ob->s.b.sorted) 94390075Sobrien { 94490075Sobrien if (ob->s.b.mixed_encoding) 94590075Sobrien return binary_search_mixed_encoding_fdes (ob, pc); 94690075Sobrien else if (ob->s.b.encoding == DW_EH_PE_absptr) 94790075Sobrien return binary_search_unencoded_fdes (ob, pc); 94890075Sobrien else 94990075Sobrien return binary_search_single_encoding_fdes (ob, pc); 95090075Sobrien } 95190075Sobrien else 95290075Sobrien { 95390075Sobrien /* Long slow labourious linear search, cos we've no memory. */ 95490075Sobrien if (ob->s.b.from_array) 955117395Skan { 956117395Skan fde **p; 95790075Sobrien for (p = ob->u.array; *p ; p++) 95890075Sobrien { 959132718Skan const fde *f = linear_search_fdes (ob, *p, pc); 960117395Skan if (f) 96190075Sobrien return f; 962117395Skan } 96390075Sobrien return NULL; 96490075Sobrien } 96590075Sobrien else 96690075Sobrien return linear_search_fdes (ob, ob->u.single, pc); 96790075Sobrien } 96890075Sobrien} 96990075Sobrien 970132718Skanconst fde * 97190075Sobrien_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases) 97290075Sobrien{ 97390075Sobrien struct object *ob; 974132718Skan const fde *f = NULL; 97590075Sobrien 97690075Sobrien init_object_mutex_once (); 97790075Sobrien __gthread_mutex_lock (&object_mutex); 97890075Sobrien 97990075Sobrien /* Linear search through the classified objects, to find the one 98090075Sobrien containing the pc. Note that pc_begin is sorted descending, and 98190075Sobrien we expect objects to be non-overlapping. */ 98290075Sobrien for (ob = seen_objects; ob; ob = ob->next) 98390075Sobrien if (pc >= ob->pc_begin) 98490075Sobrien { 98590075Sobrien f = search_object (ob, pc); 98690075Sobrien if (f) 98790075Sobrien goto fini; 98890075Sobrien break; 98990075Sobrien } 99090075Sobrien 99190075Sobrien /* Classify and search the objects we've not yet processed. */ 99290075Sobrien while ((ob = unseen_objects)) 99390075Sobrien { 99490075Sobrien struct object **p; 99590075Sobrien 99690075Sobrien unseen_objects = ob->next; 99790075Sobrien f = search_object (ob, pc); 99890075Sobrien 99990075Sobrien /* Insert the object into the classified list. */ 100090075Sobrien for (p = &seen_objects; *p ; p = &(*p)->next) 100190075Sobrien if ((*p)->pc_begin < ob->pc_begin) 100290075Sobrien break; 100390075Sobrien ob->next = *p; 100490075Sobrien *p = ob; 100590075Sobrien 100690075Sobrien if (f) 100790075Sobrien goto fini; 100890075Sobrien } 100990075Sobrien 101090075Sobrien fini: 101190075Sobrien __gthread_mutex_unlock (&object_mutex); 101290075Sobrien 101390075Sobrien if (f) 101490075Sobrien { 101590075Sobrien int encoding; 1016169689Skan _Unwind_Ptr func; 101790075Sobrien 101890075Sobrien bases->tbase = ob->tbase; 101990075Sobrien bases->dbase = ob->dbase; 102090075Sobrien 102190075Sobrien encoding = ob->s.b.encoding; 102290075Sobrien if (ob->s.b.mixed_encoding) 102390075Sobrien encoding = get_fde_encoding (f); 102490075Sobrien read_encoded_value_with_base (encoding, base_from_object (encoding, ob), 1025169689Skan f->pc_begin, &func); 1026169689Skan bases->func = (void *) func; 102790075Sobrien } 102890075Sobrien 102990075Sobrien return f; 103090075Sobrien} 1031