libdw/fde.c

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