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