elftools/dwarf/dwarf_expr.py

   1 #-------------------------------------------------------------------------------
   2 # elftools: dwarf/dwarf_expr.py
   3 #
   4 # Decoding DWARF expressions
   5 #
   6 # Eli Bendersky (eliben@gmail.com)
   7 # This code is in the public domain
   8 #-------------------------------------------------------------------------------
   9 from collections import namedtuple
  10 from io import BytesIO
  11
  12 from ..common.utils import struct_parse, bytelist2string, read_blob
  13 from ..common.exceptions import DWARFError
  14
  15
  16 # DWARF expression opcodes. name -> opcode mapping
  17 DW_OP_name2opcode = dict(
  18     DW_OP_addr=0x03,
  19     DW_OP_deref=0x06,
  20     DW_OP_const1u=0x08,
  21     DW_OP_const1s=0x09,
  22     DW_OP_const2u=0x0a,
  23     DW_OP_const2s=0x0b,
  24     DW_OP_const4u=0x0c,
  25     DW_OP_const4s=0x0d,
  26     DW_OP_const8u=0x0e,
  27     DW_OP_const8s=0x0f,
  28     DW_OP_constu=0x10,
  29     DW_OP_consts=0x11,
  30     DW_OP_dup=0x12,
  31     DW_OP_drop=0x13,
  32     DW_OP_over=0x14,
  33     DW_OP_pick=0x15,
  34     DW_OP_swap=0x16,
  35     DW_OP_rot=0x17,
  36     DW_OP_xderef=0x18,
  37     DW_OP_abs=0x19,
  38     DW_OP_and=0x1a,
  39     DW_OP_div=0x1b,
  40     DW_OP_minus=0x1c,
  41     DW_OP_mod=0x1d,
  42     DW_OP_mul=0x1e,
  43     DW_OP_neg=0x1f,
  44     DW_OP_not=0x20,
  45     DW_OP_or=0x21,
  46     DW_OP_plus=0x22,
  47     DW_OP_plus_uconst=0x23,
  48     DW_OP_shl=0x24,
  49     DW_OP_shr=0x25,
  50     DW_OP_shra=0x26,
  51     DW_OP_xor=0x27,
  52     DW_OP_bra=0x28,
  53     DW_OP_eq=0x29,
  54     DW_OP_ge=0x2a,
  55     DW_OP_gt=0x2b,
  56     DW_OP_le=0x2c,
  57     DW_OP_lt=0x2d,
  58     DW_OP_ne=0x2e,
  59     DW_OP_skip=0x2f,
  60     DW_OP_regx=0x90,
  61     DW_OP_fbreg=0x91,
  62     DW_OP_bregx=0x92,
  63     DW_OP_piece=0x93,
  64     DW_OP_deref_size=0x94,
  65     DW_OP_xderef_size=0x95,
  66     DW_OP_nop=0x96,
  67     DW_OP_push_object_address=0x97,
  68     DW_OP_call2=0x98,
  69     DW_OP_call4=0x99,
  70     DW_OP_call_ref=0x9a,
  71     DW_OP_form_tls_address=0x9b,
  72     DW_OP_call_frame_cfa=0x9c,
  73     DW_OP_bit_piece=0x9d,
  74     DW_OP_implicit_value=0x9e,
  75     DW_OP_stack_value=0x9f,
  76     DW_OP_implicit_pointer=0xa0,
  77     DW_OP_addrx=0xa1,
  78     DW_OP_constx=0xa2,
  79     DW_OP_entry_value=0xa3,
  80     DW_OP_const_type=0xa4,
  81     DW_OP_regval_type=0xa5,
  82     DW_OP_deref_type=0xa6,
  83     DW_OP_xderef_type=0xa7,
  84     DW_OP_convert=0xa8,
  85     DW_OP_reinterpret=0xa9,
  86     DW_OP_lo_user=0xe0,
  87     DW_OP_GNU_push_tls_address=0xe0,
  88     DW_OP_WASM_location=0xed,
  89     DW_OP_GNU_uninit=0xf0,
  90     DW_OP_GNU_implicit_pointer=0xf2,
  91     DW_OP_GNU_entry_value=0xf3,
  92     DW_OP_GNU_const_type=0xf4,
  93     DW_OP_GNU_regval_type=0xf5,
  94     DW_OP_GNU_deref_type=0xf6,
  95     DW_OP_GNU_convert=0xf7,
  96     DW_OP_GNU_parameter_ref=0xfa,
  97     DW_OP_hi_user=0xff,
  98 )
  99
 100 def _generate_dynamic_values(map, prefix, index_start, index_end, value_start):
 101     """ Generate values in a map (dict) dynamically. Each key starts with
 102         a (string) prefix, followed by an index in the inclusive range
 103         [index_start, index_end]. The values start at value_start.
 104     """
 105     for index in range(index_start, index_end + 1):
 106         name = '%s%s' % (prefix, index)
 107         value = value_start + index - index_start
 108         map[name] = value
 109
 110 _generate_dynamic_values(DW_OP_name2opcode, 'DW_OP_lit', 0, 31, 0x30)
 111 _generate_dynamic_values(DW_OP_name2opcode, 'DW_OP_reg', 0, 31, 0x50)
 112 _generate_dynamic_values(DW_OP_name2opcode, 'DW_OP_breg', 0, 31, 0x70)
 113
 114 # opcode -> name mapping
 115 DW_OP_opcode2name = dict((v, k) for k, v in DW_OP_name2opcode.items())
 116
 117
 118 # Each parsed DWARF expression is returned as this type with its numeric opcode,
 119 # op name (as a string) and a list of arguments.
 120 DWARFExprOp = namedtuple('DWARFExprOp', 'op op_name args offset')
 121
 122
 123 class DWARFExprParser(object):
 124     """DWARF expression parser.
 125
 126     When initialized, requires structs to cache a dispatch table. After that,
 127     parse_expr can be called repeatedly - it's stateless.
 128     """
 129
 130     def __init__(self, structs):
 131         self._dispatch_table = _init_dispatch_table(structs)
 132
 133     def parse_expr(self, expr):
 134         """ Parses expr (a list of integers) into a list of DWARFExprOp.
 135
 136         The list can potentially be nested.
 137         """
 138         stream = BytesIO(bytelist2string(expr))
 139         parsed = []
 140
 141         while True:
 142             # Get the next opcode from the stream. If nothing is left in the
 143             # stream, we're done.
 144             offset = stream.tell()
 145             byte = stream.read(1)
 146             if len(byte) == 0:
 147                 break
 148
 149             # Decode the opcode and its name.
 150             op = ord(byte)
 151             op_name = DW_OP_opcode2name.get(op, 'OP:0x%x' % op)
 152
 153             # Use dispatch table to parse args.
 154             arg_parser = self._dispatch_table[op]
 155             args = arg_parser(stream)
 156
 157             parsed.append(DWARFExprOp(op=op, op_name=op_name, args=args, offset=offset))
 158
 159         return parsed
 160
 161
 162 def _init_dispatch_table(structs):
 163     """Creates a dispatch table for parsing args of an op.
 164
 165     Returns a dict mapping opcode to a function. The function accepts a stream
 166     and return a list of parsed arguments for the opcode from the stream;
 167     the stream is advanced by the function as needed.
 168     """
 169     table = {}
 170     def add(opcode_name, func):
 171         table[DW_OP_name2opcode[opcode_name]] = func
 172
 173     def parse_noargs():
 174         return lambda stream: []
 175
 176     def parse_op_addr():
 177         return lambda stream: [struct_parse(structs.Dwarf_target_addr(''),
 178                                             stream)]
 179
 180     def parse_arg_struct(arg_struct):
 181         return lambda stream: [struct_parse(arg_struct, stream)]
 182
 183     def parse_arg_struct2(arg1_struct, arg2_struct):
 184         return lambda stream: [struct_parse(arg1_struct, stream),
 185                                struct_parse(arg2_struct, stream)]
 186
 187     # ULEB128, then an expression of that length
 188     def parse_nestedexpr():
 189         def parse(stream):
 190             size = struct_parse(structs.Dwarf_uleb128(''), stream)
 191             nested_expr_blob = read_blob(stream, size)
 192             return [DWARFExprParser(structs).parse_expr(nested_expr_blob)]
 193         return parse
 194
 195     # ULEB128, then a blob of that size
 196     def parse_blob():
 197         return lambda stream: [read_blob(stream, struct_parse(structs.Dwarf_uleb128(''), stream))]
 198
 199     # ULEB128 with datatype DIE offset, then byte, then a blob of that size
 200     def parse_typedblob():
 201         return lambda stream: [struct_parse(structs.Dwarf_uleb128(''), stream), read_blob(stream, struct_parse(structs.Dwarf_uint8(''), stream))]
 202
 203     # https://yurydelendik.github.io/webassembly-dwarf/
 204     # Byte, then variant: 0, 1, 2 => uleb128, 3 => uint32
 205     def parse_wasmloc():
 206         def parse(stream):
 207             op = struct_parse(structs.Dwarf_uint8(''), stream)
 208             if 0 <= op <= 2:
 209                 return [op, struct_parse(structs.Dwarf_uleb128(''), stream)]
 210             elif op == 3:
 211                 return [op, struct_parse(structs.Dwarf_uint32(''), stream)]
 212             else:
 213                 raise DWARFError("Unknown operation code in DW_OP_WASM_location: %d" % (op,))
 214         return parse
 215
 216     add('DW_OP_addr', parse_op_addr())
 217     add('DW_OP_addrx', parse_arg_struct(structs.Dwarf_uleb128('')))
 218     add('DW_OP_const1u', parse_arg_struct(structs.Dwarf_uint8('')))
 219     add('DW_OP_const1s', parse_arg_struct(structs.Dwarf_int8('')))
 220     add('DW_OP_const2u', parse_arg_struct(structs.Dwarf_uint16('')))
 221     add('DW_OP_const2s', parse_arg_struct(structs.Dwarf_int16('')))
 222     add('DW_OP_const4u', parse_arg_struct(structs.Dwarf_uint32('')))
 223     add('DW_OP_const4s', parse_arg_struct(structs.Dwarf_int32('')))
 224     add('DW_OP_const8u', parse_arg_struct(structs.Dwarf_uint64('')))
 225     add('DW_OP_const8s', parse_arg_struct(structs.Dwarf_int64('')))
 226     add('DW_OP_constu', parse_arg_struct(structs.Dwarf_uleb128('')))
 227     add('DW_OP_consts', parse_arg_struct(structs.Dwarf_sleb128('')))
 228     add('DW_OP_pick', parse_arg_struct(structs.Dwarf_uint8('')))
 229     add('DW_OP_plus_uconst', parse_arg_struct(structs.Dwarf_uleb128('')))
 230     add('DW_OP_bra', parse_arg_struct(structs.Dwarf_int16('')))
 231     add('DW_OP_skip', parse_arg_struct(structs.Dwarf_int16('')))
 232
 233     for opname in [ 'DW_OP_deref', 'DW_OP_dup', 'DW_OP_drop', 'DW_OP_over',
 234                     'DW_OP_swap', 'DW_OP_swap', 'DW_OP_rot', 'DW_OP_xderef',
 235                     'DW_OP_abs', 'DW_OP_and', 'DW_OP_div', 'DW_OP_minus',
 236                     'DW_OP_mod', 'DW_OP_mul', 'DW_OP_neg', 'DW_OP_not',
 237                     'DW_OP_or', 'DW_OP_plus', 'DW_OP_shl', 'DW_OP_shr',
 238                     'DW_OP_shra', 'DW_OP_xor', 'DW_OP_eq', 'DW_OP_ge',
 239                     'DW_OP_gt', 'DW_OP_le', 'DW_OP_lt', 'DW_OP_ne', 'DW_OP_nop',
 240                     'DW_OP_push_object_address', 'DW_OP_form_tls_address',
 241                     'DW_OP_call_frame_cfa', 'DW_OP_stack_value',
 242                     'DW_OP_GNU_push_tls_address', 'DW_OP_GNU_uninit']:
 243         add(opname, parse_noargs())
 244
 245     for n in range(0, 32):
 246         add('DW_OP_lit%s' % n, parse_noargs())
 247         add('DW_OP_reg%s' % n, parse_noargs())
 248         add('DW_OP_breg%s' % n, parse_arg_struct(structs.Dwarf_sleb128('')))
 249
 250     add('DW_OP_fbreg', parse_arg_struct(structs.Dwarf_sleb128('')))
 251     add('DW_OP_regx', parse_arg_struct(structs.Dwarf_uleb128('')))
 252     add('DW_OP_bregx', parse_arg_struct2(structs.Dwarf_uleb128(''),
 253                                          structs.Dwarf_sleb128('')))
 254     add('DW_OP_piece', parse_arg_struct(structs.Dwarf_uleb128('')))
 255     add('DW_OP_bit_piece', parse_arg_struct2(structs.Dwarf_uleb128(''),
 256                                              structs.Dwarf_uleb128('')))
 257     add('DW_OP_deref_size', parse_arg_struct(structs.Dwarf_int8('')))
 258     add('DW_OP_xderef_size', parse_arg_struct(structs.Dwarf_int8('')))
 259     add('DW_OP_call2', parse_arg_struct(structs.Dwarf_uint16('')))
 260     add('DW_OP_call4', parse_arg_struct(structs.Dwarf_uint32('')))
 261     add('DW_OP_call_ref', parse_arg_struct(structs.Dwarf_offset('')))
 262     add('DW_OP_implicit_value', parse_blob())
 263     add('DW_OP_entry_value', parse_nestedexpr())
 264     add('DW_OP_const_type', parse_typedblob())
 265     add('DW_OP_regval_type', parse_arg_struct2(structs.Dwarf_uleb128(''),
 266                                                    structs.Dwarf_uleb128('')))
 267     add('DW_OP_deref_type', parse_arg_struct2(structs.Dwarf_uint8(''),
 268                                               structs.Dwarf_uleb128('')))
 269     add('DW_OP_implicit_pointer', parse_arg_struct2(structs.Dwarf_offset(''),
 270                                                         structs.Dwarf_sleb128('')))
 271     add('DW_OP_convert', parse_arg_struct(structs.Dwarf_uleb128('')))
 272     add('DW_OP_GNU_entry_value', parse_nestedexpr())
 273     add('DW_OP_GNU_const_type', parse_typedblob())
 274     add('DW_OP_GNU_regval_type', parse_arg_struct2(structs.Dwarf_uleb128(''),
 275                                                    structs.Dwarf_uleb128('')))
 276     add('DW_OP_GNU_deref_type', parse_arg_struct2(structs.Dwarf_uint8(''),
 277                                                    structs.Dwarf_uleb128('')))
 278     add('DW_OP_GNU_implicit_pointer', parse_arg_struct2(structs.Dwarf_offset(''),
 279                                                         structs.Dwarf_sleb128('')))
 280     add('DW_OP_GNU_parameter_ref', parse_arg_struct(structs.Dwarf_offset('')))
 281     add('DW_OP_GNU_convert', parse_arg_struct(structs.Dwarf_uleb128('')))
 282     add('DW_OP_WASM_location', parse_wasmloc())
 283
 284     return table