src/third_party/pyelftools/elftools/dwarf/lineprogram.py

   1 #-------------------------------------------------------------------------------
   2 # elftools: dwarf/lineprogram.py
   3 #
   4 # DWARF line number program
   5 #
   6 # Eli Bendersky (eliben@gmail.com)
   7 # This code is in the public domain
   8 #-------------------------------------------------------------------------------
   9 import os
  10 import copy
  11 from collections import namedtuple
  12
  13 from ..common.utils import struct_parse
  14 from .constants import *
  15
  16
  17 # LineProgramEntry - an entry in the line program.
  18 # A line program is a sequence of encoded entries. Some of these entries add a
  19 # new LineState (mapping between line and address), and some don't.
  20 #
  21 # command:
  22 #   The command/opcode - always numeric. For standard commands - it's the opcode
  23 #   that can be matched with one of the DW_LNS_* constants. For extended commands
  24 #   it's the extended opcode that can be matched with one of the DW_LNE_*
  25 #   constants. For special commands, it's the opcode itself.
  26 #
  27 # args:
  28 #   A list of decoded arguments of the command.
  29 #
  30 # is_extended:
  31 #   Since extended commands are encoded by a zero followed by an extended
  32 #   opcode, and these extended opcodes overlap with other opcodes, this
  33 #   flag is needed to mark that the command has an extended opcode.
  34 #
  35 # state:
  36 #   For commands that add a new state, it's the relevant LineState object.
  37 #   For commands that don't add a new state, it's None.
  38 #
  39 LineProgramEntry = namedtuple(
  40     'LineProgramEntry', 'command is_extended args state')
  41
  42
  43 class LineState(object):
  44     """ Represents a line program state (or a "row" in the matrix
  45         describing debug location information for addresses).
  46         The instance variables of this class are the "state machine registers"
  47         described in section 6.2.2 of DWARFv3
  48     """
  49     def __init__(self, default_is_stmt):
  50         self.address = 0
  51         self.file = 1
  52         self.line = 1
  53         self.column = 0
  54         self.is_stmt = default_is_stmt
  55         self.basic_block = False
  56         self.end_sequence = False
  57         self.prologue_end = False
  58         self.epilogue_begin = False
  59         self.isa = 0
  60
  61     def __repr__(self):
  62         a = ['<LineState %x:' % id(self)]
  63         a.append('  address = 0x%x' % self.address)
  64         for attr in ('file', 'line', 'column', 'is_stmt', 'basic_block',
  65                      'end_sequence', 'prologue_end', 'epilogue_begin', 'isa'):
  66             a.append('  %s = %s' % (attr, getattr(self, attr)))
  67         return '\n'.join(a) + '>\n'
  68
  69
  70 class LineProgram(object):
  71     """ Builds a "line table", which is essentially the matrix described
  72         in section 6.2 of DWARFv3. It's a list of LineState objects,
  73         sorted by increasing address, so it can be used to obtain the
  74         state information for each address.
  75     """
  76     def __init__(self, header, stream, structs,
  77                  program_start_offset, program_end_offset):
  78         """
  79             header:
  80                 The header of this line program. Note: LineProgram may modify
  81                 its header by appending file entries if DW_LNE_define_file
  82                 instructions are encountered.
  83
  84             stream:
  85                 The stream this program can be read from.
  86
  87             structs:
  88                 A DWARFStructs instance suitable for this line program
  89
  90             program_{start|end}_offset:
  91                 Offset in the debug_line section stream where this program
  92                 starts (the actual program, after the header), and where it
  93                 ends.
  94                 The actual range includes start but not end: [start, end - 1]
  95         """
  96         self.stream = stream
  97         self.header = header
  98         self.structs = structs
  99         self.program_start_offset = program_start_offset
 100         self.program_end_offset = program_end_offset
 101         self._decoded_entries = None
 102
 103     def get_entries(self):
 104         """ Get the decoded entries for this line program. Return a list of
 105             LineProgramEntry objects.
 106             Note that this contains more information than absolutely required
 107             for the line table. The line table can be easily extracted from
 108             the list of entries by looking only at entries with non-None
 109             state. The extra information is mainly for the purposes of display
 110             with readelf and debugging.
 111         """
 112         if self._decoded_entries is None:
 113             self._decoded_entries = self._decode_line_program()
 114         return self._decoded_entries
 115
 116     #------ PRIVATE ------#
 117
 118     def __getitem__(self, name):
 119         """ Implement dict-like access to header entries
 120         """
 121         return self.header[name]
 122
 123     def _decode_line_program(self):
 124         entries = []
 125         state = LineState(self.header['default_is_stmt'])
 126
 127         def add_entry_new_state(cmd, args, is_extended=False):
 128             # Add an entry that sets a new state.
 129             # After adding, clear some state registers.
 130             entries.append(LineProgramEntry(
 131                 cmd, is_extended, args, copy.copy(state)))
 132             state.basic_block = False
 133             state.prologue_end = False
 134             state.epilogue_begin = False
 135
 136         def add_entry_old_state(cmd, args, is_extended=False):
 137             # Add an entry that doesn't visibly set a new state
 138             entries.append(LineProgramEntry(cmd, is_extended, args, None))
 139
 140         offset = self.program_start_offset
 141         while offset < self.program_end_offset:
 142             opcode = struct_parse(
 143                 self.structs.Dwarf_uint8(''),
 144                 self.stream,
 145                 offset)
 146
 147             # As an exercise in avoiding premature optimization, if...elif
 148             # chains are used here for standard and extended opcodes instead
 149             # of dispatch tables. This keeps the code much cleaner. Besides,
 150             # the majority of instructions in a typical program are special
 151             # opcodes anyway.
 152             if opcode >= self.header['opcode_base']:
 153                 # Special opcode (follow the recipe in 6.2.5.1)
 154                 adjusted_opcode = opcode - self['opcode_base']
 155                 address_addend = ((adjusted_opcode // self['line_range']) *
 156                                   self['minimum_instruction_length'])
 157                 state.address += address_addend
 158                 line_addend = (self['line_base'] +
 159                                adjusted_opcode % self['line_range'])
 160                 state.line += line_addend
 161                 add_entry_new_state(opcode, [line_addend, address_addend])
 162             elif opcode == 0:
 163                 # Extended opcode: start with a zero byte, followed by
 164                 # instruction size and the instruction itself.
 165                 inst_len = struct_parse(self.structs.Dwarf_uleb128(''),
 166                                         self.stream)
 167                 ex_opcode = struct_parse(self.structs.Dwarf_uint8(''),
 168                                          self.stream)
 169
 170                 if ex_opcode == DW_LNE_end_sequence:
 171                     state.end_sequence = True
 172                     add_entry_new_state(ex_opcode, [], is_extended=True)
 173                     # reset state
 174                     state = LineState(self.header['default_is_stmt'])
 175                 elif ex_opcode == DW_LNE_set_address:
 176                     operand = struct_parse(self.structs.Dwarf_target_addr(''),
 177                                            self.stream)
 178                     state.address = operand
 179                     add_entry_old_state(ex_opcode, [operand], is_extended=True)
 180                 elif ex_opcode == DW_LNE_define_file:
 181                     operand = struct_parse(
 182                         self.structs.Dwarf_lineprog_file_entry, self.stream)
 183                     self['file_entry'].append(operand)
 184                     add_entry_old_state(ex_opcode, [operand], is_extended=True)
 185                 else:
 186                     # Unknown, but need to roll forward the stream because the
 187                     # length is specified. Seek forward inst_len - 1 because
 188                     # we've already read the extended opcode, which takes part
 189                     # in the length.
 190                     self.stream.seek(inst_len - 1, os.SEEK_CUR)
 191             else: # 0 < opcode < opcode_base
 192                 # Standard opcode
 193                 if opcode == DW_LNS_copy:
 194                     add_entry_new_state(opcode, [])
 195                 elif opcode == DW_LNS_advance_pc:
 196                     operand = struct_parse(self.structs.Dwarf_uleb128(''),
 197                                            self.stream)
 198                     address_addend = (
 199                         operand * self.header['minimum_instruction_length'])
 200                     state.address += address_addend
 201                     add_entry_old_state(opcode, [address_addend])
 202                 elif opcode == DW_LNS_advance_line:
 203                     operand = struct_parse(self.structs.Dwarf_sleb128(''),
 204                                            self.stream)
 205                     state.line += operand
 206                 elif opcode == DW_LNS_set_file:
 207                     operand = struct_parse(self.structs.Dwarf_uleb128(''),
 208                                            self.stream)
 209                     state.file = operand
 210                     add_entry_old_state(opcode, [operand])
 211                 elif opcode == DW_LNS_set_column:
 212                     operand = struct_parse(self.structs.Dwarf_uleb128(''),
 213                                            self.stream)
 214                     state.column = operand
 215                     add_entry_old_state(opcode, [operand])
 216                 elif opcode == DW_LNS_negate_stmt:
 217                     state.is_stmt = not state.is_stmt
 218                     add_entry_old_state(opcode, [operand])
 219                 elif opcode == DW_LNS_set_basic_block:
 220                     state.basic_block = True
 221                     add_entry_old_state(opcode, [operand])
 222                 elif opcode == DW_LNS_const_add_pc:
 223                     adjusted_opcode = 255 - self['opcode_base']
 224                     address_addend = ((adjusted_opcode // self['line_range']) *
 225                                       self['minimum_instruction_length'])
 226                     state.address += address_addend
 227                     add_entry_old_state(opcode, [address_addend])
 228                 elif opcode == DW_LNS_fixed_advance_pc:
 229                     operand = struct_parse(self.structs.Dwarf_uint16(''),
 230                                            self.stream)
 231                     state.address += operand
 232                     add_entry_old_state(opcode, [operand])
 233                 elif opcode == DW_LNS_set_prologue_end:
 234                     state.prologue_end = True
 235                     add_entry_old_state(opcode, [])
 236                 elif opcode == DW_LNS_set_epilogue_begin:
 237                     state.epilogue_begin = True
 238                     add_entry_old_state(opcode, [])
 239                 elif opcode == DW_LNS_set_isa:
 240                     operand = struct_parse(self.structs.Dwarf_uleb128(''),
 241                                            self.stream)
 242                     state.isa = operand
 243                     add_entry_old_state(opcode, [operand])
 244                 else:
 245                     dwarf_assert(False, 'Invalid standard line program opcode: %s' % (
 246                         opcode,))
 247             offset = self.stream.tell()
 248         return entries
 249