libdw/fde.c

   1 /* FDE reading.
   2    Copyright (C) 2009-2010 Red Hat, Inc.
   3    This file is part of elfutils.
   4
   5    This file is free software; you can redistribute it and/or modify
   6    it under the terms of either
   7
   8      * the GNU Lesser General Public License as published by the Free
   9        Software Foundation; either version 3 of the License, or (at
  10        your option) any later version
  11
  12    or
  13
  14      * the GNU General Public License as published by the Free
  15        Software Foundation; either version 2 of the License, or (at
  16        your option) any later version
  17
  18    or both in parallel, as here.
  19
  20    elfutils is distributed in the hope that it will be useful, but
  21    WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23    General Public License for more details.
  24
  25    You should have received copies of the GNU General Public License and
  26    the GNU Lesser General Public License along with this program.  If
  27    not, see <http://www.gnu.org/licenses/>.  */
  28
  29 #ifdef HAVE_CONFIG_H
  30 # include <config.h>
  31 #endif
  32
  33 #include "cfi.h"
  34 #include <search.h>
  35 #include <stdlib.h>
  36
  37 #include "encoded-value.h"
  38
  39 static int
  40 compare_fde (const void *a, const void *b)
  41 {
  42   const struct dwarf_fde *fde1 = a;
  43   const struct dwarf_fde *fde2 = b;
  44
  45   /* Find out which of the two arguments is the search value.
  46      It has end offset 0.  */
  47   if (fde1->end == 0)
  48     {
  49       if (fde1->start < fde2->start)
  50         return -1;
  51       if (fde1->start >= fde2->end)
  52         return 1;
  53     }
  54   else
  55     {
  56       if (fde2->start < fde1->start)
  57         return 1;
  58       if (fde2->start >= fde1->end)
  59         return -1;
  60     }
  61
  62   return 0;
  63 }
  64
  65 static struct dwarf_fde *
  66 intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
  67 {
  68   /* Look up the new entry's CIE.  */
  69   struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
  70   if (cie == NULL)
  71     return (void *) -1l;
  72
  73   struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
  74   if (fde == NULL)
  75     {
  76       __libdw_seterrno (DWARF_E_NOMEM);
  77       return NULL;
  78     }
  79
  80   fde->instructions = entry->start;
  81   fde->instructions_end = entry->end;
  82   if (unlikely (read_encoded_value (cache, cie->fde_encoding,
  83                                     &fde->instructions, &fde->start))
  84       || unlikely (read_encoded_value (cache, cie->fde_encoding & 0x0f,
  85                                        &fde->instructions, &fde->end)))
  86     return NULL;
  87   fde->end += fde->start;
  88
  89   fde->cie = cie;
  90
  91   if (cie->sized_augmentation_data)
  92     {
  93       /* The CIE augmentation says the FDE has a DW_FORM_block
  94          before its actual instruction stream.  */
  95       Dwarf_Word len;
  96       get_uleb128 (len, fde->instructions);
  97       if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
  98         {
  99           free (fde);
 100           __libdw_seterrno (DWARF_E_INVALID_DWARF);
 101           return NULL;
 102         }
 103       fde->instructions += len;
 104     }
 105   else
 106     /* We had to understand all of the CIE augmentation string.
 107        We've recorded the number of data bytes in FDEs.  */
 108     fde->instructions += cie->fde_augmentation_data_size;
 109
 110   /* Add the new entry to the search tree.  */
 111   if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL)
 112     {
 113       free (fde);
 114       __libdw_seterrno (DWARF_E_NOMEM);
 115       return NULL;
 116     }
 117
 118   return fde;
 119 }
 120
 121 struct dwarf_fde *
 122 internal_function
 123 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
 124 {
 125   Dwarf_CFI_Entry entry;
 126   Dwarf_Off next_offset;
 127   int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
 128                                        &cache->data->d, CFI_IS_EH (cache),
 129                                        offset, &next_offset, &entry);
 130   if (result != 0)
 131     {
 132       if (result > 0)
 133       invalid:
 134         __libdw_seterrno (DWARF_E_INVALID_DWARF);
 135       return NULL;
 136     }
 137
 138   if (unlikely (dwarf_cfi_cie_p (&entry)))
 139     goto invalid;
 140
 141   /* We have a new FDE to consider.  */
 142   struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
 143   if (fde == (void *) -1l || fde == NULL)
 144     return NULL;
 145
 146   /* If this happened to be what we would have read next, notice it.  */
 147   if (cache->next_offset == offset)
 148     cache->next_offset = next_offset;
 149
 150   return fde;
 151 }
 152
 153 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset.  */
 154 static Dwarf_Off
 155 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
 156 {
 157   const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
 158                                               cache->search_table_encoding,
 159                                               NULL);
 160
 161   /* Dummy used by read_encoded_value.  */
 162   Dwarf_CFI dummy_cfi =
 163     {
 164       .e_ident = cache->e_ident,
 165       .datarel = cache->search_table_vaddr,
 166       .frame_vaddr = cache->search_table_vaddr,
 167     };
 168
 169   size_t l = 0, u = cache->search_table_entries;
 170   while (l < u)
 171     {
 172       size_t idx = (l + u) / 2;
 173
 174       const uint8_t *p = &cache->search_table[idx * size];
 175       Dwarf_Addr start;
 176       if (unlikely (read_encoded_value (&dummy_cfi,
 177                                         cache->search_table_encoding, &p,
 178                                         &start)))
 179         break;
 180       if (address < start)
 181         u = idx;
 182       else
 183         {
 184           Dwarf_Addr fde;
 185           if (unlikely (read_encoded_value (&dummy_cfi,
 186                                             cache->search_table_encoding, &p,
 187                                             &fde)))
 188             break;
 189           if (address >= start)
 190             {
 191               l = idx + 1;
 192
 193               /* If this is the last entry, its upper bound is assumed to be
 194                  the end of the module.
 195                  XXX really should be end of containing PT_LOAD segment */
 196               if (l < cache->search_table_entries)
 197                 {
 198                   /* Look at the start address in the following entry.  */
 199                   Dwarf_Addr end;
 200                   if (unlikely (read_encoded_value
 201                                 (&dummy_cfi, cache->search_table_encoding, &p,
 202                                  &end)))
 203                     break;
 204                   if (address >= end)
 205                     continue;
 206                 }
 207
 208               return fde - cache->frame_vaddr;
 209             }
 210         }
 211     }
 212
 213   return (Dwarf_Off) -1l;
 214 }
 215
 216 struct dwarf_fde *
 217 internal_function
 218 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
 219 {
 220   /* Look for a cached FDE covering this address.  */
 221
 222   const struct dwarf_fde fde_key = { .start = address, .end = 0 };
 223   struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
 224   if (found != NULL)
 225     return *found;
 226
 227   /* Use .eh_frame_hdr binary search table if possible.  */
 228   if (cache->search_table != NULL)
 229     {
 230       Dwarf_Off offset = binary_search_fde (cache, address);
 231       if (offset == (Dwarf_Off) -1l)
 232         goto no_match;
 233       struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
 234       if (unlikely (fde != NULL)
 235           /* Sanity check the address range.  */
 236           && unlikely (address < fde->start || address >= fde->end))
 237         {
 238           __libdw_seterrno (DWARF_E_INVALID_DWARF);
 239           return NULL;
 240         }
 241       return fde;
 242     }
 243
 244   /* It's not there.  Read more CFI entries until we find it.  */
 245   while (1)
 246     {
 247       Dwarf_Off last_offset = cache->next_offset;
 248       Dwarf_CFI_Entry entry;
 249       int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
 250                                            &cache->data->d, CFI_IS_EH (cache),
 251                                            last_offset, &cache->next_offset,
 252                                            &entry);
 253       if (result > 0)
 254         break;
 255       if (result < 0)
 256         {
 257           if (cache->next_offset == last_offset)
 258             /* We couldn't progress past the bogus FDE.  */
 259             break;
 260           /* Skip the loser and look at the next entry.  */
 261           continue;
 262         }
 263
 264       if (dwarf_cfi_cie_p (&entry))
 265         {
 266           /* This is a CIE, not an FDE.  We eagerly intern these
 267              because the next FDE will usually refer to this CIE.  */
 268           __libdw_intern_cie (cache, last_offset, &entry.cie);
 269           continue;
 270         }
 271
 272       /* We have a new FDE to consider.  */
 273       struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
 274
 275       if (fde == (void *) -1l)  /* Bad FDE, but we can keep looking.  */
 276         continue;
 277
 278       if (fde == NULL)          /* Bad data.  */
 279         return NULL;
 280
 281       /* Is this the one we're looking for?  */
 282       if (fde->start <= address && fde->end > address)
 283         return fde;
 284     }
 285
 286  no_match:
 287   /* We found no FDE covering this address.  */
 288   __libdw_seterrno (DWARF_E_NO_MATCH);
 289   return NULL;
 290 }