elftools/dwarf/locationlists.py

   1 #-------------------------------------------------------------------------------
   2 # elftools: dwarf/locationlists.py
   3 #
   4 # DWARF location lists section decoding (.debug_loc)
   5 #
   6 # Eli Bendersky (eliben@gmail.com)
   7 # This code is in the public domain
   8 #-------------------------------------------------------------------------------
   9 import os
  10 from collections import namedtuple
  11 from ..common.exceptions import DWARFError
  12 from ..common.utils import struct_parse
  13 from .dwarf_util import _iter_CUs_in_section
  14
  15 LocationExpr = namedtuple('LocationExpr', 'loc_expr')
  16 LocationEntry = namedtuple('LocationEntry', 'entry_offset entry_length begin_offset end_offset loc_expr is_absolute')
  17 BaseAddressEntry = namedtuple('BaseAddressEntry', 'entry_offset entry_length base_address')
  18 LocationViewPair = namedtuple('LocationViewPair', 'entry_offset begin end')
  19
  20 class LocationListsPair(object):
  21     """For those binaries that contain both a debug_loc and a debug_loclists section,
  22     it holds a LocationLists object for both and forwards API calls to the right one.
  23     """
  24     def __init__(self, streamv4, streamv5, structs, dwarfinfo=None):
  25         self._loc = LocationLists(streamv4, structs, 4, dwarfinfo)
  26         self._loclists = LocationLists(streamv5, structs, 5, dwarfinfo)
  27
  28     def get_location_list_at_offset(self, offset, die=None):
  29         """See LocationLists.get_location_list_at_offset().
  30         """
  31         if die is None:
  32             raise DWARFError("For this binary, \"die\" needs to be provided")
  33         section = self._loclists if die.cu.version >= 5 else self._loc
  34         return section.get_location_list_at_offset(offset, die)
  35
  36     def iter_location_lists(self):
  37         """Tricky proposition, since the structure of loc and loclists
  38         is not identical. A realistic readelf implementation needs to be aware of both
  39         """
  40         raise DWARFError("Iterating through two sections is not supported")
  41
  42     def iter_CUs(self):
  43         """See LocationLists.iter_CUs()
  44
  45         There are no CUs in DWARFv4 sections.
  46         """
  47         raise DWARFError("Iterating through two sections is not supported")
  48
  49 class LocationLists(object):
  50     """ A single location list is a Python list consisting of LocationEntry or
  51         BaseAddressEntry objects.
  52
  53         Starting with DWARF5, it may also contain LocationViewPair, but only
  54         if scanning the section, never when requested for a DIE attribute.
  55
  56         The default location entries are returned as LocationEntry with
  57         begin_offset == end_offset == -1
  58
  59         Version determines whether the executable contains a debug_loc
  60         section, or a DWARFv5 style debug_loclists one. Only the 4/5
  61         distinction matters.
  62
  63         Dwarfinfo is only needed for DWARFv5 location entry encodings
  64         that contain references to other sections (e. g. DW_LLE_startx_endx),
  65         and only for location list enumeration.
  66     """
  67     def __init__(self, stream, structs, version=4, dwarfinfo=None):
  68         self.stream = stream
  69         self.structs = structs
  70         self.dwarfinfo = dwarfinfo
  71         self.version = version
  72         self._max_addr = 2 ** (self.structs.address_size * 8) - 1
  73
  74     def get_location_list_at_offset(self, offset, die=None):
  75         """ Get a location list at the given offset in the section.
  76         Passing the die is only neccessary in DWARF5+, for decoding
  77         location entry encodings that contain references to other sections.
  78         """
  79         self.stream.seek(offset, os.SEEK_SET)
  80         return self._parse_location_list_from_stream_v5(die) if self.version >= 5 else self._parse_location_list_from_stream()
  81
  82     def iter_location_lists(self):
  83         """ Iterates through location lists and view pairs. Returns lists of
  84         LocationEntry, BaseAddressEntry, and LocationViewPair objects.
  85         """
  86         # The location lists section was never meant for sequential access.
  87         # Location lists are referenced by DIE attributes by offset or by index.
  88
  89         # As of DWARFv5, it may contain, in addition to proper location lists,
  90         # location list view pairs, which are referenced by the nonstandard DW_AT_GNU_locviews
  91         # attribute. A set of locview pairs (which is a couple of ULEB128 values) may preceed
  92         # a location list; the former is referenced by the DW_AT_GNU_locviews attribute, the
  93         # latter - by DW_AT_location (in the same DIE). Binutils' readelf dumps those.
  94         # There is a view pair for each location-type entry in the list.
  95         #
  96         # Also, the section may contain gaps.
  97         #
  98         # Taking a cue from binutils, we would have to scan this section while looking at
  99         # what's in DIEs.
 100         ver5 = self.version >= 5
 101         stream = self.stream
 102         stream.seek(0, os.SEEK_END)
 103         endpos = stream.tell()
 104
 105         stream.seek(0, os.SEEK_SET)
 106
 107         # Need to provide support for DW_AT_GNU_locviews. They are interspersed in
 108         # the locations section, no way to tell where short of checking all DIEs
 109         all_offsets = set() # Set of offsets where either a locview pair set can be found, or a view-less loclist
 110         locviews = dict() # Map of locview offset to the respective loclist offset
 111         cu_map = dict() # Map of loclist offsets to CUs
 112         for cu in self.dwarfinfo.iter_CUs():
 113             cu_ver = cu['version']
 114             if (cu_ver >= 5) == ver5:
 115                 for die in cu.iter_DIEs():
 116                     # A combination of location and locviews means there is a location list
 117                     # preceed by several locview pairs
 118                     if 'DW_AT_GNU_locviews' in die.attributes:
 119                         assert('DW_AT_location' in die.attributes and
 120                             LocationParser._attribute_has_loc_list(die.attributes['DW_AT_location'], cu_ver))
 121                         views_offset = die.attributes['DW_AT_GNU_locviews'].value
 122                         list_offset = die.attributes['DW_AT_location'].value
 123                         locviews[views_offset] = list_offset
 124                         cu_map[list_offset] = cu
 125                         all_offsets.add(views_offset)
 126
 127                     # Scan other attributes for location lists
 128                     for key in die.attributes:
 129                         attr = die.attributes[key]
 130                         if ((key != 'DW_AT_location' or 'DW_AT_GNU_locviews' not in die.attributes) and
 131                             LocationParser.attribute_has_location(attr, cu_ver) and
 132                             LocationParser._attribute_has_loc_list(attr, cu_ver)):
 133                             list_offset = attr.value
 134                             all_offsets.add(list_offset)
 135                             cu_map[list_offset] = cu
 136         all_offsets = list(all_offsets)
 137         all_offsets.sort()
 138
 139         if ver5:
 140             # Loclists section is organized as an array of CUs, each length prefixed.
 141             # We don't assume that the CUs go in the same order as the ones in info.
 142             offset_index = 0
 143             while stream.tell() < endpos:
 144                 # We are at the start of the CU block in the loclists now
 145                 cu_header = struct_parse(self.structs.Dwarf_loclists_CU_header, stream)
 146                 assert(cu_header.version == 5)
 147
 148                 # GNU binutils supports two traversal modes: by offsets in CU header, and sequential.
 149                 # We don't have a binary for the former yet. On an off chance that we one day might,
 150                 # let's parse the header anyway.
 151
 152                 cu_end_offset = cu_header.offset_after_length + cu_header.unit_length
 153                 # Unit_length includes the header but doesn't include the length
 154
 155                 while stream.tell() < cu_end_offset:
 156                     # Skip the gap to the next object
 157                     next_offset = all_offsets[offset_index]
 158                     if next_offset == stream.tell(): # At an object, either a loc list or a loc view pair
 159                         locview_pairs = self._parse_locview_pairs(locviews)
 160                         entries = self._parse_location_list_from_stream_v5()
 161                         yield locview_pairs + entries
 162                         offset_index += 1
 163                     else: # We are at a gap - skip the gap to the next object or to the next CU
 164                         if next_offset > cu_end_offset: # Gap at the CU end - the next object is in the next CU
 165                             next_offset = cu_end_offset # And implicitly quit the loop within the CU
 166                         stream.seek(next_offset, os.SEEK_SET)
 167         else:
 168             for offset in all_offsets:
 169                 list_offset = locviews.get(offset, offset)
 170                 if cu_map[list_offset].header.version < 5:
 171                     stream.seek(offset, os.SEEK_SET)
 172                     locview_pairs = self._parse_locview_pairs(locviews)
 173                     entries = self._parse_location_list_from_stream()
 174                     yield locview_pairs + entries
 175
 176     def iter_CUs(self):
 177         """For DWARF5 returns an array of objects, where each one has an array of offsets
 178         """
 179         if self.version < 5:
 180             raise DWARFError("CU iteration in loclists is not supported with DWARF<5")
 181
 182         structs = next(self.dwarfinfo.iter_CUs()).structs # Just pick one
 183         return _iter_CUs_in_section(self.stream, structs, structs.Dwarf_loclists_CU_header)
 184
 185     #------ PRIVATE ------#
 186
 187     def _parse_location_list_from_stream(self):
 188         lst = []
 189         while True:
 190             entry_offset = self.stream.tell()
 191             begin_offset = struct_parse(
 192                 self.structs.Dwarf_target_addr(''), self.stream)
 193             end_offset = struct_parse(
 194                 self.structs.Dwarf_target_addr(''), self.stream)
 195             if begin_offset == 0 and end_offset == 0:
 196                 # End of list - we're done.
 197                 break
 198             elif begin_offset == self._max_addr:
 199                 # Base address selection entry
 200                 entry_length = self.stream.tell() - entry_offset
 201                 lst.append(BaseAddressEntry(entry_offset=entry_offset, entry_length=entry_length, base_address=end_offset))
 202             else:
 203                 # Location list entry
 204                 expr_len = struct_parse(
 205                     self.structs.Dwarf_uint16(''), self.stream)
 206                 loc_expr = [struct_parse(self.structs.Dwarf_uint8(''),
 207                                          self.stream)
 208                                 for i in range(expr_len)]
 209                 entry_length = self.stream.tell() - entry_offset
 210                 lst.append(LocationEntry(
 211                     entry_offset=entry_offset,
 212                     entry_length=entry_length,
 213                     begin_offset=begin_offset,
 214                     end_offset=end_offset,
 215                     loc_expr=loc_expr,
 216                     is_absolute = False))
 217         return lst
 218
 219     # Also returns an array with BaseAddressEntry and LocationEntry
 220     # Can't possibly support indexed values, since parsing those requires
 221     # knowing the DIE context it came from
 222     def _parse_location_list_from_stream_v5(self, die = None):
 223         # This won't contain the terminator entry
 224         lst = [self._translate_entry_v5(entry, die)
 225             for entry
 226             in struct_parse(self.structs.Dwarf_loclists_entries, self.stream)]
 227         return lst
 228
 229     # From V5 style entries to a LocationEntry/BaseAddressEntry
 230     def _translate_entry_v5(self, entry, die):
 231         off = entry.entry_offset
 232         len = entry.entry_end_offset - off
 233         type = entry.entry_type
 234         if type == 'DW_LLE_base_address':
 235             return BaseAddressEntry(off, len, entry.address)
 236         elif type == 'DW_LLE_offset_pair':
 237             return LocationEntry(off, len, entry.start_offset, entry.end_offset, entry.loc_expr, False)
 238         elif type == 'DW_LLE_start_length':
 239             return LocationEntry(off, len, entry.start_address, entry.start_address + entry.length, entry.loc_expr, True)
 240         elif type == 'DW_LLE_start_end': # No test for this yet, but the format seems straightforward
 241             return LocationEntry(off, len, entry.start_address, entry.end_address, entry.loc_expr, True)
 242         elif type == 'DW_LLE_default_location': # No test for this either, and this is new in the API
 243             return LocationEntry(off, len, -1, -1, entry.loc_expr, True)
 244         elif type in ('DW_LLE_base_addressx', 'DW_LLE_startx_endx', 'DW_LLE_startx_length'):
 245             # We don't have sample binaries for those LLEs. Their proper parsing would
 246             # require knowing the CU context (so that indices can be resolved to code offsets)
 247             raise NotImplementedError("Location list entry type %s is not supported yet" % (type,))
 248         else:
 249             raise DWARFError(False, "Unknown DW_LLE code: %s" % (type,))
 250
 251     # Locviews is the dict, mapping locview offsets to corresponding loclist offsets
 252     def _parse_locview_pairs(self, locviews):
 253         stream = self.stream
 254         list_offset = locviews.get(stream.tell(), None)
 255         pairs = []
 256         if list_offset is not None:
 257             while stream.tell() < list_offset:
 258                 pair = struct_parse(self.structs.Dwarf_locview_pair, stream)
 259                 pairs.append(LocationViewPair(pair.entry_offset, pair.begin, pair.end))
 260             assert(stream.tell() == list_offset)
 261         return pairs
 262
 263 class LocationParser(object):
 264     """ A parser for location information in DIEs.
 265         Handles both location information contained within the attribute
 266         itself (represented as a LocationExpr object) and references to
 267         location lists in the .debug_loc section (represented as a
 268         list).
 269     """
 270     def __init__(self, location_lists):
 271         self.location_lists = location_lists
 272
 273     @staticmethod
 274     def attribute_has_location(attr, dwarf_version):
 275         """ Checks if a DIE attribute contains location information.
 276         """
 277         return (LocationParser._attribute_is_loclistptr_class(attr) and
 278                 (LocationParser._attribute_has_loc_expr(attr, dwarf_version) or
 279                  LocationParser._attribute_has_loc_list(attr, dwarf_version)))
 280
 281     def parse_from_attribute(self, attr, dwarf_version, die = None):
 282         """ Parses a DIE attribute and returns either a LocationExpr or
 283             a list.
 284         """
 285         if self.attribute_has_location(attr, dwarf_version):
 286             if self._attribute_has_loc_expr(attr, dwarf_version):
 287                 return LocationExpr(attr.value)
 288             elif self._attribute_has_loc_list(attr, dwarf_version):
 289                 return self.location_lists.get_location_list_at_offset(
 290                     attr.value, die)
 291                 # We don't yet know if the DIE context will be needed.
 292                 # We might get it without a full tree traversal using
 293                 # attr.offset as a key, but we assume a good DWARF5
 294                 # aware consumer would pass a DIE along.
 295         else:
 296             raise ValueError("Attribute does not have location information")
 297
 298     #------ PRIVATE ------#
 299
 300     @staticmethod
 301     def _attribute_has_loc_expr(attr, dwarf_version):
 302         return ((dwarf_version < 4 and attr.form.startswith('DW_FORM_block') and
 303             not attr.name == 'DW_AT_const_value') or
 304             attr.form == 'DW_FORM_exprloc')
 305
 306     @staticmethod
 307     def _attribute_has_loc_list(attr, dwarf_version):
 308         return ((dwarf_version < 4 and
 309                  attr.form in ('DW_FORM_data1', 'DW_FORM_data2', 'DW_FORM_data4', 'DW_FORM_data8') and
 310                  not attr.name == 'DW_AT_const_value') or
 311                 attr.form == 'DW_FORM_sec_offset')
 312
 313     @staticmethod
 314     def _attribute_is_loclistptr_class(attr):
 315         return (attr.name in ( 'DW_AT_location', 'DW_AT_string_length',
 316                                'DW_AT_const_value', 'DW_AT_return_addr',
 317                                'DW_AT_data_member_location',
 318                                'DW_AT_frame_base', 'DW_AT_segment',
 319                                'DW_AT_static_link', 'DW_AT_use_location',
 320                                'DW_AT_vtable_elem_location',
 321                                'DW_AT_call_value',
 322                                'DW_AT_GNU_call_site_value',
 323                                'DW_AT_GNU_call_site_target',
 324                                'DW_AT_GNU_call_site_data_value'))