libdw/fde.c

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