libdw/dwarf_getlocation.c

   1 /* Return location expression list.
   2    Copyright (C) 2000-2010 Red Hat, Inc.
   3    This file is part of Red Hat elfutils.
   4    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
   5
   6    Red Hat elfutils is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by the
   8    Free Software Foundation; version 2 of the License.
   9
  10    Red Hat elfutils is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License along
  16    with Red Hat elfutils; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
  18
  19    In addition, as a special exception, Red Hat, Inc. gives You the
  20    additional right to link the code of Red Hat elfutils with code licensed
  21    under any Open Source Initiative certified open source license
  22    (http://www.opensource.org/licenses/index.php) which requires the
  23    distribution of source code with any binary distribution and to
  24    distribute linked combinations of the two.  Non-GPL Code permitted under
  25    this exception must only link to the code of Red Hat elfutils through
  26    those well defined interfaces identified in the file named EXCEPTION
  27    found in the source code files (the "Approved Interfaces").  The files
  28    of Non-GPL Code may instantiate templates or use macros or inline
  29    functions from the Approved Interfaces without causing the resulting
  30    work to be covered by the GNU General Public License.  Only Red Hat,
  31    Inc. may make changes or additions to the list of Approved Interfaces.
  32    Red Hat's grant of this exception is conditioned upon your not adding
  33    any new exceptions.  If you wish to add a new Approved Interface or
  34    exception, please contact Red Hat.  You must obey the GNU General Public
  35    License in all respects for all of the Red Hat elfutils code and other
  36    code used in conjunction with Red Hat elfutils except the Non-GPL Code
  37    covered by this exception.  If you modify this file, you may extend this
  38    exception to your version of the file, but you are not obligated to do
  39    so.  If you do not wish to provide this exception without modification,
  40    you must delete this exception statement from your version and license
  41    this file solely under the GPL without exception.
  42
  43    Red Hat elfutils is an included package of the Open Invention Network.
  44    An included package of the Open Invention Network is a package for which
  45    Open Invention Network licensees cross-license their patents.  No patent
  46    license is granted, either expressly or impliedly, by designation as an
  47    included package.  Should you wish to participate in the Open Invention
  48    Network licensing program, please visit www.openinventionnetwork.com
  49    <http://www.openinventionnetwork.com>.  */
  50
  51 #ifdef HAVE_CONFIG_H
  52 # include <config.h>
  53 #endif
  54
  55 #include <dwarf.h>
  56 #include <search.h>
  57 #include <stdlib.h>
  58 #include <assert.h>
  59
  60 #include <libdwP.h>
  61
  62
  63 static bool
  64 attr_ok (Dwarf_Attribute *attr)
  65 {
  66   if (attr == NULL)
  67     return false;
  68
  69   /* Must be one of the attributes listed below.  */
  70   switch (attr->code)
  71     {
  72     case DW_AT_location:
  73     case DW_AT_data_member_location:
  74     case DW_AT_vtable_elem_location:
  75     case DW_AT_string_length:
  76     case DW_AT_use_location:
  77     case DW_AT_frame_base:
  78     case DW_AT_return_addr:
  79     case DW_AT_static_link:
  80       break;
  81
  82     default:
  83       __libdw_seterrno (DWARF_E_NO_LOCLIST);
  84       return false;
  85     }
  86
  87   return true;
  88 }
  89
  90
  91 struct loclist
  92 {
  93   uint8_t atom;
  94   Dwarf_Word number;
  95   Dwarf_Word number2;
  96   Dwarf_Word offset;
  97   struct loclist *next;
  98 };
  99
 100
 101 static int
 102 loc_compare (const void *p1, const void *p2)
 103 {
 104   const struct loc_s *l1 = (const struct loc_s *) p1;
 105   const struct loc_s *l2 = (const struct loc_s *) p2;
 106
 107   if ((uintptr_t) l1->addr < (uintptr_t) l2->addr)
 108     return -1;
 109   if ((uintptr_t) l1->addr > (uintptr_t) l2->addr)
 110     return 1;
 111
 112   return 0;
 113 }
 114
 115 /* For each DW_OP_implicit_value, we store a special entry in the cache.
 116    This points us directly to the block data for later fetching.  */
 117 static void
 118 store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op,
 119                       unsigned char *data)
 120 {
 121   struct loc_block_s *block = libdw_alloc (dbg, struct loc_block_s,
 122                                            sizeof (struct loc_block_s), 1);
 123   block->addr = op;
 124   block->data = data + op->number2;
 125   block->length = op->number;
 126   (void) tsearch (block, cache, loc_compare);
 127 }
 128
 129 int
 130 dwarf_getlocation_implicit_value (attr, op, return_block)
 131      Dwarf_Attribute *attr;
 132      const Dwarf_Op *op;
 133      Dwarf_Block *return_block;
 134 {
 135   if (attr == NULL)
 136     return -1;
 137
 138   struct loc_block_s fake = { .addr = (void *) op };
 139   struct loc_block_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
 140   if (unlikely (found == NULL))
 141     {
 142       __libdw_seterrno (DWARF_E_NO_BLOCK);
 143       return -1;
 144     }
 145
 146   return_block->length = (*found)->length;
 147   return_block->data = (*found)->data;
 148   return 0;
 149 }
 150
 151 /* DW_AT_data_member_location can be a constant as well as a loclistptr.
 152    Only data[48] indicate a loclistptr.  */
 153 static int
 154 check_constant_offset (Dwarf_Attribute *attr,
 155                        Dwarf_Op **llbuf, size_t *listlen)
 156 {
 157   if (attr->code != DW_AT_data_member_location)
 158     return 1;
 159
 160   switch (attr->form)
 161     {
 162       /* Punt for any non-constant form.  */
 163     default:
 164       return 1;
 165
 166     case DW_FORM_data1:
 167     case DW_FORM_data2:
 168     case DW_FORM_data4:
 169     case DW_FORM_data8:
 170     case DW_FORM_sdata:
 171     case DW_FORM_udata:
 172       break;
 173     }
 174
 175   /* Check whether we already cached this location.  */
 176   struct loc_s fake = { .addr = attr->valp };
 177   struct loc_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
 178
 179   if (found == NULL)
 180     {
 181       Dwarf_Word offset;
 182       if (INTUSE(dwarf_formudata) (attr, &offset) != 0)
 183         return -1;
 184
 185       Dwarf_Op *result = libdw_alloc (attr->cu->dbg,
 186                                       Dwarf_Op, sizeof (Dwarf_Op), 1);
 187
 188       result->atom = DW_OP_plus_uconst;
 189       result->number = offset;
 190       result->number2 = 0;
 191       result->offset = 0;
 192
 193       /* Insert a record in the search tree so we can find it again later.  */
 194       struct loc_s *newp = libdw_alloc (attr->cu->dbg,
 195                                         struct loc_s, sizeof (struct loc_s),
 196                                         1);
 197       newp->addr = attr->valp;
 198       newp->loc = result;
 199       newp->nloc = 1;
 200
 201       found = tsearch (newp, &attr->cu->locs, loc_compare);
 202     }
 203
 204   assert ((*found)->nloc == 1);
 205
 206   if (llbuf != NULL)
 207     {
 208       *llbuf = (*found)->loc;
 209       *listlen = 1;
 210     }
 211
 212   return 0;
 213 }
 214
 215 int
 216 internal_function
 217 __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
 218                            unsigned int address_size, unsigned int ref_size,
 219                            void **cache, const Dwarf_Block *block,
 220                            bool cfap, bool valuep,
 221                            Dwarf_Op **llbuf, size_t *listlen, int sec_index)
 222 {
 223   /* Check whether we already looked at this list.  */
 224   struct loc_s fake = { .addr = block->data };
 225   struct loc_s **found = tfind (&fake, cache, loc_compare);
 226   if (found != NULL)
 227     {
 228       /* We already saw it.  */
 229       *llbuf = (*found)->loc;
 230       *listlen = (*found)->nloc;
 231
 232       if (valuep)
 233         {
 234           assert (*listlen > 1);
 235           assert ((*llbuf)[*listlen - 1].atom == DW_OP_stack_value);
 236         }
 237
 238       return 0;
 239     }
 240
 241   const unsigned char *data = block->data;
 242   const unsigned char *const end_data = data + block->length;
 243
 244   const struct { bool other_byte_order; } bo = { other_byte_order };
 245
 246   struct loclist *loclist = NULL;
 247   unsigned int n = 0;
 248   /* Decode the opcodes.  It is possible in some situations to have a
 249      block of size zero.  */
 250   while (data < end_data)
 251     {
 252       struct loclist *newloc;
 253       newloc = (struct loclist *) alloca (sizeof (struct loclist));
 254       newloc->number = 0;
 255       newloc->number2 = 0;
 256       newloc->offset = data - block->data;
 257       newloc->next = loclist;
 258       loclist = newloc;
 259       ++n;
 260
 261       switch ((newloc->atom = *data++))
 262         {
 263         case DW_OP_addr:
 264           /* Address, depends on address size of CU.  */
 265           if (__libdw_read_address_inc (dbg, sec_index, &data,
 266                                         address_size, &newloc->number))
 267             return -1;
 268           break;
 269
 270         case DW_OP_call_ref:
 271           /* DW_FORM_ref_addr, depends on offset size of CU.  */
 272           if (__libdw_read_offset_inc (dbg, sec_index, &data, ref_size,
 273                                        &newloc->number, IDX_debug_info, 0))
 274             return -1;
 275           break;
 276
 277         case DW_OP_deref:
 278         case DW_OP_dup:
 279         case DW_OP_drop:
 280         case DW_OP_over:
 281         case DW_OP_swap:
 282         case DW_OP_rot:
 283         case DW_OP_xderef:
 284         case DW_OP_abs:
 285         case DW_OP_and:
 286         case DW_OP_div:
 287         case DW_OP_minus:
 288         case DW_OP_mod:
 289         case DW_OP_mul:
 290         case DW_OP_neg:
 291         case DW_OP_not:
 292         case DW_OP_or:
 293         case DW_OP_plus:
 294         case DW_OP_shl:
 295         case DW_OP_shr:
 296         case DW_OP_shra:
 297         case DW_OP_xor:
 298         case DW_OP_eq:
 299         case DW_OP_ge:
 300         case DW_OP_gt:
 301         case DW_OP_le:
 302         case DW_OP_lt:
 303         case DW_OP_ne:
 304         case DW_OP_lit0 ... DW_OP_lit31:
 305         case DW_OP_reg0 ... DW_OP_reg31:
 306         case DW_OP_nop:
 307         case DW_OP_push_object_address:
 308         case DW_OP_call_frame_cfa:
 309         case DW_OP_form_tls_address:
 310         case DW_OP_GNU_push_tls_address:
 311         case DW_OP_stack_value:
 312           /* No operand.  */
 313           break;
 314
 315         case DW_OP_const1u:
 316         case DW_OP_pick:
 317         case DW_OP_deref_size:
 318         case DW_OP_xderef_size:
 319           if (unlikely (data >= end_data))
 320             {
 321             invalid:
 322               __libdw_seterrno (DWARF_E_INVALID_DWARF);
 323               return -1;
 324             }
 325
 326           newloc->number = *data++;
 327           break;
 328
 329         case DW_OP_const1s:
 330           if (unlikely (data >= end_data))
 331             goto invalid;
 332
 333           newloc->number = *((int8_t *) data);
 334           ++data;
 335           break;
 336
 337         case DW_OP_const2u:
 338           if (unlikely (data + 2 > end_data))
 339             goto invalid;
 340
 341           newloc->number = read_2ubyte_unaligned_inc (&bo, data);
 342           break;
 343
 344         case DW_OP_const2s:
 345         case DW_OP_skip:
 346         case DW_OP_bra:
 347         case DW_OP_call2:
 348           if (unlikely (data + 2 > end_data))
 349             goto invalid;
 350
 351           newloc->number = read_2sbyte_unaligned_inc (&bo, data);
 352           break;
 353
 354         case DW_OP_const4u:
 355           if (unlikely (data + 4 > end_data))
 356             goto invalid;
 357
 358           newloc->number = read_4ubyte_unaligned_inc (&bo, data);
 359           break;
 360
 361         case DW_OP_const4s:
 362         case DW_OP_call4:
 363           if (unlikely (data + 4 > end_data))
 364             goto invalid;
 365
 366           newloc->number = read_4sbyte_unaligned_inc (&bo, data);
 367           break;
 368
 369         case DW_OP_const8u:
 370           if (unlikely (data + 8 > end_data))
 371             goto invalid;
 372
 373           newloc->number = read_8ubyte_unaligned_inc (&bo, data);
 374           break;
 375
 376         case DW_OP_const8s:
 377           if (unlikely (data + 8 > end_data))
 378             goto invalid;
 379
 380           newloc->number = read_8sbyte_unaligned_inc (&bo, data);
 381           break;
 382
 383         case DW_OP_constu:
 384         case DW_OP_plus_uconst:
 385         case DW_OP_regx:
 386         case DW_OP_piece:
 387           /* XXX Check size.  */
 388           get_uleb128 (newloc->number, data);
 389           break;
 390
 391         case DW_OP_consts:
 392         case DW_OP_breg0 ... DW_OP_breg31:
 393         case DW_OP_fbreg:
 394           /* XXX Check size.  */
 395           get_sleb128 (newloc->number, data);
 396           break;
 397
 398         case DW_OP_bregx:
 399           /* XXX Check size.  */
 400           get_uleb128 (newloc->number, data);
 401           get_sleb128 (newloc->number2, data);
 402           break;
 403
 404         case DW_OP_bit_piece:
 405           /* XXX Check size.  */
 406           get_uleb128 (newloc->number, data);
 407           get_uleb128 (newloc->number2, data);
 408           break;
 409
 410         case DW_OP_implicit_value:
 411           /* This cannot be used in a CFI expression.  */
 412           if (unlikely (dbg == NULL))
 413             goto invalid;
 414
 415           /* XXX Check size.  */
 416           get_uleb128 (newloc->number, data); /* Block length.  */
 417           if (unlikely ((Dwarf_Word) (end_data - data) < newloc->number))
 418             goto invalid;
 419           newloc->number2 = data - block->data; /* Relative block offset.  */
 420           data += newloc->number;               /* Skip the block.  */
 421           break;
 422
 423         case DW_OP_GNU_implicit_pointer:
 424           /* DW_FORM_ref_addr, depends on offset size of CU.  */
 425           if (__libdw_read_offset_inc (dbg, sec_index, &data, ref_size,
 426                                        &newloc->number, IDX_debug_info, 0))
 427             return -1;
 428           /* XXX Check size.  */
 429           get_uleb128 (newloc->number2, data); /* Byte offset.  */
 430           break;
 431
 432         default:
 433           goto invalid;
 434         }
 435     }
 436
 437   if (unlikely (n == 0))
 438     {
 439       /* This is not allowed.
 440
 441          XXX Is it?  */
 442       goto invalid;
 443     }
 444
 445   if (valuep)
 446     {
 447       struct loclist *newloc;
 448       newloc = (struct loclist *) alloca (sizeof (struct loclist));
 449       newloc->atom = DW_OP_stack_value;
 450       newloc->number = 0;
 451       newloc->number2 = 0;
 452       newloc->offset = data - block->data;
 453       newloc->next = loclist;
 454       loclist = newloc;
 455       ++n;
 456     }
 457
 458   if (cfap)
 459     ++n;
 460
 461   /* Allocate the array.  */
 462   Dwarf_Op *result;
 463   if (dbg != NULL)
 464     result = libdw_alloc (dbg, Dwarf_Op, sizeof (Dwarf_Op), n);
 465   else
 466     {
 467       result = malloc (sizeof *result * n);
 468       if (result == NULL)
 469         {
 470         nomem:
 471           __libdw_seterrno (DWARF_E_NOMEM);
 472           return -1;
 473         }
 474     }
 475
 476   /* Store the result.  */
 477   *llbuf = result;
 478   *listlen = n;
 479
 480   if (cfap)
 481     {
 482       /* Synthesize the operation to push the CFA before the expression.  */
 483       --n;
 484       result[0].atom = DW_OP_call_frame_cfa;
 485       result[0].number = 0;
 486       result[0].number2 = 0;
 487       result[0].offset = -1;
 488     }
 489
 490   do
 491     {
 492       /* We populate the array from the back since the list is backwards.  */
 493       --n;
 494       result[n].atom = loclist->atom;
 495       result[n].number = loclist->number;
 496       result[n].number2 = loclist->number2;
 497       result[n].offset = loclist->offset;
 498
 499       if (result[n].atom == DW_OP_implicit_value)
 500         store_implicit_value (dbg, cache, &result[n], block->data);
 501
 502       loclist = loclist->next;
 503     }
 504   while (n > 0);
 505
 506   /* Insert a record in the search tree so that we can find it again later.  */
 507   struct loc_s *newp;
 508   if (dbg != NULL)
 509     newp = libdw_alloc (dbg, struct loc_s, sizeof (struct loc_s), 1);
 510   else
 511     {
 512       newp = malloc (sizeof *newp);
 513       if (newp == NULL)
 514         {
 515           free (result);
 516           goto nomem;
 517         }
 518     }
 519
 520   newp->addr = block->data;
 521   newp->loc = result;
 522   newp->nloc = *listlen;
 523   (void) tsearch (newp, cache, loc_compare);
 524
 525   /* We did it.  */
 526   return 0;
 527 }
 528
 529 static int
 530 getlocation (struct Dwarf_CU *cu, const Dwarf_Block *block,
 531              Dwarf_Op **llbuf, size_t *listlen, int sec_index)
 532 {
 533   return __libdw_intern_expression (cu->dbg, cu->dbg->other_byte_order,
 534                                     cu->address_size, (cu->version == 2
 535                                                        ? cu->address_size
 536                                                        : cu->offset_size),
 537                                     &cu->locs, block,
 538                                     false, false,
 539                                     llbuf, listlen, sec_index);
 540 }
 541
 542 int
 543 dwarf_getlocation (attr, llbuf, listlen)
 544      Dwarf_Attribute *attr;
 545      Dwarf_Op **llbuf;
 546      size_t *listlen;
 547 {
 548   if (! attr_ok (attr))
 549     return -1;
 550
 551   int result = check_constant_offset (attr, llbuf, listlen);
 552   if (result != 1)
 553     return result;
 554
 555   /* If it has a block form, it's a single location expression.  */
 556   Dwarf_Block block;
 557   if (INTUSE(dwarf_formblock) (attr, &block) != 0)
 558     return -1;
 559
 560   return getlocation (attr->cu, &block, llbuf, listlen, cu_sec_idx (attr->cu));
 561 }
 562
 563 int
 564 dwarf_getlocation_addr (attr, address, llbufs, listlens, maxlocs)
 565      Dwarf_Attribute *attr;
 566      Dwarf_Addr address;
 567      Dwarf_Op **llbufs;
 568      size_t *listlens;
 569      size_t maxlocs;
 570 {
 571   if (! attr_ok (attr))
 572     return -1;
 573
 574   if (llbufs == NULL)
 575     maxlocs = SIZE_MAX;
 576
 577   /* If it has a block form, it's a single location expression.  */
 578   Dwarf_Block block;
 579   if (INTUSE(dwarf_formblock) (attr, &block) == 0)
 580     {
 581       if (maxlocs == 0)
 582         return 0;
 583       if (llbufs != NULL &&
 584           getlocation (attr->cu, &block, &llbufs[0], &listlens[0],
 585                        cu_sec_idx (attr->cu)) != 0)
 586         return -1;
 587       return listlens[0] == 0 ? 0 : 1;
 588     }
 589
 590   int error = INTUSE(dwarf_errno) ();
 591   if (unlikely (error != DWARF_E_NO_BLOCK))
 592     {
 593       __libdw_seterrno (error);
 594       return -1;
 595     }
 596
 597   int result = check_constant_offset (attr, &llbufs[0], &listlens[0]);
 598   if (result != 1)
 599     return result ?: 1;
 600
 601   unsigned char *endp;
 602   unsigned char *readp = __libdw_formptr (attr, IDX_debug_loc,
 603                                           DWARF_E_NO_LOCLIST, &endp, NULL);
 604   if (readp == NULL)
 605     return -1;
 606
 607   Dwarf_Addr base = (Dwarf_Addr) -1;
 608   size_t got = 0;
 609   while (got < maxlocs)
 610     {
 611       if (endp - readp < attr->cu->address_size * 2)
 612         {
 613         invalid:
 614           __libdw_seterrno (DWARF_E_INVALID_DWARF);
 615           return -1;
 616         }
 617
 618       Dwarf_Addr begin;
 619       Dwarf_Addr end;
 620
 621       int status
 622         = __libdw_read_begin_end_pair_inc (attr->cu->dbg, IDX_debug_loc,
 623                                            &readp, attr->cu->address_size,
 624                                            &begin, &end, &base);
 625       if (status == 2) /* End of list entry.  */
 626         break;
 627       else if (status == 1) /* Base address selected.  */
 628         continue;
 629       else if (status < 0)
 630         return status;
 631
 632       if (endp - readp < 2)
 633         goto invalid;
 634
 635       /* We have a location expression.  */
 636       block.length = read_2ubyte_unaligned_inc (attr->cu->dbg, readp);
 637       block.data = readp;
 638       if (endp - readp < (ptrdiff_t) block.length)
 639         goto invalid;
 640       readp += block.length;
 641
 642       if (base == (Dwarf_Addr) -1)
 643         {
 644           /* Fetch the CU's base address.  */
 645           Dwarf_Die cudie = CUDIE (attr->cu);
 646
 647           /* Find the base address of the compilation unit.  It will
 648              normally be specified by DW_AT_low_pc.  In DWARF-3 draft 4,
 649              the base address could be overridden by DW_AT_entry_pc.  It's
 650              been removed, but GCC emits DW_AT_entry_pc and not DW_AT_lowpc
 651              for compilation units with discontinuous ranges.  */
 652           Dwarf_Attribute attr_mem;
 653           if (unlikely (INTUSE(dwarf_lowpc) (&cudie, &base) != 0)
 654               && INTUSE(dwarf_formaddr) (INTUSE(dwarf_attr) (&cudie,
 655                                                              DW_AT_entry_pc,
 656                                                              &attr_mem),
 657                                          &base) != 0)
 658             {
 659               if (INTUSE(dwarf_errno) () != 0)
 660                 return -1;
 661
 662               /* The compiler provided no base address when it should
 663                  have.  Buggy GCC does this when it used absolute
 664                  addresses in the location list and no DW_AT_ranges.  */
 665               base = 0;
 666             }
 667         }
 668
 669       if (address >= base + begin && address < base + end)
 670         {
 671           /* This one matches the address.  */
 672           if (llbufs != NULL
 673               && unlikely (getlocation (attr->cu, &block,
 674                                         &llbufs[got], &listlens[got],
 675                                         IDX_debug_loc) != 0))
 676             return -1;
 677           ++got;
 678         }
 679     }
 680
 681   return got;
 682 }