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     {
  87       free (fde);
  88       __libdw_seterrno (DWARF_E_INVALID_DWARF);
  89       return NULL;
  90     }
  91   fde->end += fde->start;
  92
  93   fde->cie = cie;
  94
  95   if (cie->sized_augmentation_data)
  96     {
  97       /* The CIE augmentation says the FDE has a DW_FORM_block
  98          before its actual instruction stream.  */
  99       Dwarf_Word len;
 100       get_uleb128 (len, fde->instructions);
 101       if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
 102         {
 103           free (fde);
 104           __libdw_seterrno (DWARF_E_INVALID_DWARF);
 105           return NULL;
 106         }
 107       fde->instructions += len;
 108     }
 109   else
 110     /* We had to understand all of the CIE augmentation string.
 111        We've recorded the number of data bytes in FDEs.  */
 112     fde->instructions += cie->fde_augmentation_data_size;
 113
 114   /* Add the new entry to the search tree.  */
 115   if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL)
 116     {
 117       free (fde);
 118       __libdw_seterrno (DWARF_E_NOMEM);
 119       return NULL;
 120     }
 121
 122   return fde;
 123 }
 124
 125 struct dwarf_fde *
 126 internal_function
 127 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
 128 {
 129   Dwarf_CFI_Entry entry;
 130   Dwarf_Off next_offset;
 131   int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
 132                                        &cache->data->d, CFI_IS_EH (cache),
 133                                        offset, &next_offset, &entry);
 134   if (result != 0)
 135     {
 136       if (result > 0)
 137       invalid:
 138         __libdw_seterrno (DWARF_E_INVALID_DWARF);
 139       return NULL;
 140     }
 141
 142   if (unlikely (dwarf_cfi_cie_p (&entry)))
 143     goto invalid;
 144
 145   /* We have a new FDE to consider.  */
 146   struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
 147   if (fde == (void *) -1l || fde == NULL)
 148     return NULL;
 149
 150   /* If this happened to be what we would have read next, notice it.  */
 151   if (cache->next_offset == offset)
 152     cache->next_offset = next_offset;
 153
 154   return fde;
 155 }
 156
 157 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset.  */
 158 static Dwarf_Off
 159 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
 160 {
 161   const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
 162                                               cache->search_table_encoding,
 163                                               NULL);
 164
 165   /* Dummy used by read_encoded_value.  */
 166   Dwarf_CFI dummy_cfi =
 167     {
 168       .e_ident = cache->e_ident,
 169       .datarel = cache->search_table_vaddr,
 170       .frame_vaddr = cache->search_table_vaddr,
 171     };
 172
 173   size_t l = 0, u = cache->search_table_entries;
 174   while (l < u)
 175     {
 176       size_t idx = (l + u) / 2;
 177
 178       const uint8_t *p = &cache->search_table[idx * size];
 179       Dwarf_Addr start;
 180       if (unlikely (read_encoded_value (&dummy_cfi,
 181                                         cache->search_table_encoding, &p,
 182                                         &start)))
 183         break;
 184       if (address < start)
 185         u = idx;
 186       else
 187         {
 188           l = idx + 1;
 189
 190           Dwarf_Addr fde;
 191           if (unlikely (read_encoded_value (&dummy_cfi,
 192                                             cache->search_table_encoding, &p,
 193                                             &fde)))
 194             break;
 195
 196           /* If this is the last entry, its upper bound is assumed to be
 197              the end of the module.
 198              XXX really should be end of containing PT_LOAD segment */
 199           if (l < cache->search_table_entries)
 200             {
 201               /* Look at the start address in the following entry.  */
 202               Dwarf_Addr end;
 203               if (unlikely (read_encoded_value
 204                             (&dummy_cfi, cache->search_table_encoding, &p,
 205                              &end)))
 206                 break;
 207               if (address >= end)
 208                 continue;
 209             }
 210
 211           return fde - cache->frame_vaddr;
 212         }
 213     }
 214
 215   return (Dwarf_Off) -1l;
 216 }
 217
 218 struct dwarf_fde *
 219 internal_function
 220 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
 221 {
 222   /* Look for a cached FDE covering this address.  */
 223
 224   const struct dwarf_fde fde_key = { .start = address, .end = 0 };
 225   struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
 226   if (found != NULL)
 227     return *found;
 228
 229   /* Use .eh_frame_hdr binary search table if possible.  */
 230   if (cache->search_table != NULL)
 231     {
 232       Dwarf_Off offset = binary_search_fde (cache, address);
 233       if (offset == (Dwarf_Off) -1l)
 234         goto no_match;
 235       struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
 236       if (likely (fde != NULL))
 237         {
 238           /* Sanity check the address range.  */
 239           if (unlikely (address < fde->start))
 240             {
 241               __libdw_seterrno (DWARF_E_INVALID_DWARF);
 242               return NULL;
 243             }
 244           /* .eh_frame_hdr does not indicate length covered by FDE.  */
 245           if (unlikely (address >= fde->end))
 246             goto no_match;
 247         }
 248       return fde;
 249     }
 250
 251   /* It's not there.  Read more CFI entries until we find it.  */
 252   while (1)
 253     {
 254       Dwarf_Off last_offset = cache->next_offset;
 255       Dwarf_CFI_Entry entry;
 256       int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
 257                                            &cache->data->d, CFI_IS_EH (cache),
 258                                            last_offset, &cache->next_offset,
 259                                            &entry);
 260       if (result > 0)
 261         break;
 262       if (result < 0)
 263         {
 264           if (cache->next_offset == last_offset)
 265             /* We couldn't progress past the bogus FDE.  */
 266             break;
 267           /* Skip the loser and look at the next entry.  */
 268           continue;
 269         }
 270
 271       if (dwarf_cfi_cie_p (&entry))
 272         {
 273           /* This is a CIE, not an FDE.  We eagerly intern these
 274              because the next FDE will usually refer to this CIE.  */
 275           __libdw_intern_cie (cache, last_offset, &entry.cie);
 276           continue;
 277         }
 278
 279       /* We have a new FDE to consider.  */
 280       struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
 281
 282       if (fde == (void *) -1l)  /* Bad FDE, but we can keep looking.  */
 283         continue;
 284
 285       if (fde == NULL)          /* Bad data.  */
 286         return NULL;
 287
 288       /* Is this the one we're looking for?  */
 289       if (fde->start <= address && fde->end > address)
 290         return fde;
 291     }
 292
 293  no_match:
 294   /* We found no FDE covering this address.  */
 295   __libdw_seterrno (DWARF_E_NO_MATCH);
 296   return NULL;
 297 }