contrib/elftoolchain/libdwarf/libdwarf_die.c

   1 /*-
   2  * Copyright (c) 2007 John Birrell (jb@freebsd.org)
   3  * Copyright (c) 2009-2011 Kai Wang
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include "_libdwarf.h"
  29
  30 ELFTC_VCSID("$Id: libdwarf_die.c 3039 2014-05-18 15:10:56Z kaiwang27 $");
  31
  32 int
  33 _dwarf_die_alloc(Dwarf_Debug dbg, Dwarf_Die *ret_die, Dwarf_Error *error)
  34 {
  35         Dwarf_Die die;
  36
  37         assert(ret_die != NULL);
  38
  39         if ((die = calloc(1, sizeof(struct _Dwarf_Die))) == NULL) {
  40                 DWARF_SET_ERROR(dbg, error, DW_DLE_MEMORY);
  41                 return (DW_DLE_MEMORY);
  42         }
  43
  44         STAILQ_INIT(&die->die_attr);
  45
  46         *ret_die = die;
  47
  48         return (DW_DLE_NONE);
  49 }
  50
  51 static int
  52 _dwarf_die_add(Dwarf_CU cu, uint64_t offset, uint64_t abnum, Dwarf_Abbrev ab,
  53     Dwarf_Die *diep, Dwarf_Error *error)
  54 {
  55         Dwarf_Debug dbg;
  56         Dwarf_Die die;
  57         int ret;
  58
  59         assert(cu != NULL);
  60         assert(ab != NULL);
  61
  62         dbg = cu->cu_dbg;
  63
  64         if ((ret = _dwarf_die_alloc(dbg, &die, error)) != DW_DLE_NONE)
  65                 return (ret);
  66
  67         die->die_offset = offset;
  68         die->die_abnum  = abnum;
  69         die->die_ab     = ab;
  70         die->die_cu     = cu;
  71         die->die_dbg    = cu->cu_dbg;
  72
  73         if (diep != NULL)
  74                 *diep = die;
  75
  76         return (DW_DLE_NONE);
  77 }
  78
  79 /* Find die at offset 'off' within the same CU. */
  80 Dwarf_Die
  81 _dwarf_die_find(Dwarf_Die die, Dwarf_Unsigned off)
  82 {
  83         Dwarf_Debug dbg;
  84         Dwarf_Section *ds;
  85         Dwarf_CU cu;
  86         Dwarf_Die die1;
  87         Dwarf_Error de;
  88         int ret;
  89
  90         cu = die->die_cu;
  91         dbg = die->die_dbg;
  92         ds = cu->cu_is_info ? dbg->dbg_info_sec : dbg->dbg_types_sec;
  93
  94         ret = _dwarf_die_parse(dbg, ds, cu, cu->cu_dwarf_size, off,
  95             cu->cu_next_offset, &die1, 0, &de);
  96
  97         if (ret == DW_DLE_NONE)
  98                 return (die1);
  99         else
 100                 return (NULL);
 101 }
 102
 103 int
 104 _dwarf_die_parse(Dwarf_Debug dbg, Dwarf_Section *ds, Dwarf_CU cu,
 105     int dwarf_size, uint64_t offset, uint64_t next_offset, Dwarf_Die *ret_die,
 106     int search_sibling, Dwarf_Error *error)
 107 {
 108         Dwarf_Abbrev ab;
 109         Dwarf_AttrDef ad;
 110         Dwarf_Die die;
 111         uint64_t abnum;
 112         uint64_t die_offset;
 113         int ret, level;
 114
 115         assert(cu != NULL);
 116
 117         level = 1;
 118         die = NULL;
 119
 120         while (offset < next_offset && offset < ds->ds_size) {
 121
 122                 die_offset = offset;
 123
 124                 abnum = _dwarf_read_uleb128(ds->ds_data, &offset);
 125
 126                 if (abnum == 0) {
 127                         if (level == 0 || !search_sibling)
 128                                 return (DW_DLE_NO_ENTRY);
 129
 130                         /*
 131                          * Return to previous DIE level.
 132                          */
 133                         level--;
 134                         continue;
 135                 }
 136
 137                 if ((ret = _dwarf_abbrev_find(cu, abnum, &ab, error)) !=
 138                     DW_DLE_NONE)
 139                         return (ret);
 140
 141                 if ((ret = _dwarf_die_add(cu, die_offset, abnum, ab, &die,
 142                     error)) != DW_DLE_NONE)
 143                         return (ret);
 144
 145                 STAILQ_FOREACH(ad, &ab->ab_attrdef, ad_next) {
 146                         if ((ret = _dwarf_attr_init(dbg, ds, &offset,
 147                             dwarf_size, cu, die, ad, ad->ad_form, 0,
 148                             error)) != DW_DLE_NONE)
 149                                 return (ret);
 150                 }
 151
 152                 die->die_next_off = offset;
 153                 if (search_sibling && level > 0) {
 154                         dwarf_dealloc(dbg, die, DW_DLA_DIE);
 155                         if (ab->ab_children == DW_CHILDREN_yes) {
 156                                 /* Advance to next DIE level. */
 157                                 level++;
 158                         }
 159                 } else {
 160                         *ret_die = die;
 161                         return (DW_DLE_NONE);
 162                 }
 163         }
 164
 165         return (DW_DLE_NO_ENTRY);
 166 }
 167
 168 void
 169 _dwarf_die_link(Dwarf_P_Die die, Dwarf_P_Die parent, Dwarf_P_Die child,
 170     Dwarf_P_Die left_sibling, Dwarf_P_Die right_sibling)
 171 {
 172         Dwarf_P_Die last_child;
 173
 174         assert(die != NULL);
 175
 176         if (parent) {
 177
 178                 /* Disconnect from old parent. */
 179                 if (die->die_parent) {
 180                         if (die->die_parent != parent) {
 181                                 if (die->die_parent->die_child == die)
 182                                         die->die_parent->die_child = NULL;
 183                                 die->die_parent = NULL;
 184                      }
 185                 }
 186
 187                 /* Find the last child of this parent. */
 188                 last_child = parent->die_child;
 189                 if (last_child) {
 190                         while (last_child->die_right != NULL)
 191                                 last_child = last_child->die_right;
 192                 }
 193
 194                 /* Connect to new parent. */
 195                 die->die_parent = parent;
 196
 197                 /*
 198                  * Attach this DIE to the end of sibling list. If new
 199                  * parent doesn't have any child, set this DIE as the
 200                  * first child.
 201                  */
 202                 if (last_child) {
 203                         assert(last_child->die_right == NULL);
 204                         last_child->die_right = die;
 205                         die->die_left = last_child;
 206                 } else
 207                         parent->die_child = die;
 208         }
 209
 210         if (child) {
 211
 212                 /* Disconnect from old child. */
 213                 if (die->die_child) {
 214                         if (die->die_child != child) {
 215                                 die->die_child->die_parent = NULL;
 216                                 die->die_child = NULL;
 217                         }
 218                 }
 219
 220                 /* Connect to new child. */
 221                 die->die_child = child;
 222                 child->die_parent = die;
 223         }
 224
 225         if (left_sibling) {
 226
 227                 /* Disconnect from old left sibling. */
 228                 if (die->die_left) {
 229                         if (die->die_left != left_sibling) {
 230                                 die->die_left->die_right = NULL;
 231                                 die->die_left = NULL;
 232                         }
 233                 }
 234
 235                 /* Connect to new right sibling. */
 236                 die->die_left = left_sibling;
 237                 left_sibling->die_right = die;
 238         }
 239
 240         if (right_sibling) {
 241
 242                 /* Disconnect from old right sibling. */
 243                 if (die->die_right) {
 244                         if (die->die_right != right_sibling) {
 245                                 die->die_right->die_left = NULL;
 246                                 die->die_right = NULL;
 247                         }
 248                 }
 249
 250                 /* Connect to new right sibling. */
 251                 die->die_right = right_sibling;
 252                 right_sibling->die_left = die;
 253         }
 254 }
 255
 256 int
 257 _dwarf_die_count_links(Dwarf_P_Die parent, Dwarf_P_Die child,
 258     Dwarf_P_Die left_sibling, Dwarf_P_Die right_sibling)
 259 {
 260         int count;
 261
 262         count = 0;
 263
 264         if (parent)
 265                 count++;
 266         if (child)
 267                 count++;
 268         if (left_sibling)
 269                 count++;
 270         if (right_sibling)
 271                 count++;
 272
 273         return (count);
 274 }
 275
 276 static int
 277 _dwarf_die_gen_recursive(Dwarf_P_Debug dbg, Dwarf_CU cu, Dwarf_Rel_Section drs,
 278     Dwarf_P_Die die, int pass2, Dwarf_Error *error)
 279 {
 280         Dwarf_P_Section ds;
 281         Dwarf_Abbrev ab;
 282         Dwarf_Attribute at;
 283         Dwarf_AttrDef ad;
 284         int match, ret;
 285
 286         ds = dbg->dbgp_info;
 287         assert(ds != NULL);
 288
 289         if (pass2)
 290                 goto attr_gen;
 291
 292         /*
 293          * Add DW_AT_sibling attribute for DIEs with children, so consumers
 294          * can quickly scan chains of siblings, while ignoring the children
 295          * of individual siblings.
 296          */
 297         if (die->die_child && die->die_right) {
 298                 if (_dwarf_attr_find(die, DW_AT_sibling) == NULL)
 299                         (void) dwarf_add_AT_reference(dbg, die, DW_AT_sibling,
 300                             die->die_right, error);
 301         }
 302
 303         /*
 304          * Search abbrev list to find a matching entry.
 305          */
 306         die->die_ab = NULL;
 307         for (ab = cu->cu_abbrev_hash; ab != NULL; ab = ab->ab_hh.next) {
 308                 if (die->die_tag != ab->ab_tag)
 309                         continue;
 310                 if (ab->ab_children == DW_CHILDREN_no && die->die_child != NULL)
 311                         continue;
 312                 if (ab->ab_children == DW_CHILDREN_yes &&
 313                     die->die_child == NULL)
 314                         continue;
 315                 at = STAILQ_FIRST(&die->die_attr);
 316                 ad = STAILQ_FIRST(&ab->ab_attrdef);
 317                 match = 1;
 318                 while (at != NULL && ad != NULL) {
 319                         if (at->at_attrib != ad->ad_attrib ||
 320                             at->at_form != ad->ad_form) {
 321                                 match = 0;
 322                                 break;
 323                         }
 324                         at = STAILQ_NEXT(at, at_next);
 325                         ad = STAILQ_NEXT(ad, ad_next);
 326                 }
 327                 if ((at == NULL && ad != NULL) || (at != NULL && ad == NULL))
 328                         match = 0;
 329                 if (match) {
 330                         die->die_ab = ab;
 331                         break;
 332                 }
 333         }
 334
 335         /*
 336          * Create a new abbrev entry if we can not reuse any existing one.
 337          */
 338         if (die->die_ab == NULL) {
 339                 ret = _dwarf_abbrev_add(cu, ++cu->cu_abbrev_cnt, die->die_tag,
 340                     die->die_child != NULL ? DW_CHILDREN_yes : DW_CHILDREN_no,
 341                     0, &ab, error);
 342                 if (ret != DW_DLE_NONE)
 343                         return (ret);
 344                 STAILQ_FOREACH(at, &die->die_attr, at_next) {
 345                         ret = _dwarf_attrdef_add(dbg, ab, at->at_attrib,
 346                             at->at_form, 0, NULL, error);
 347                         if (ret != DW_DLE_NONE)
 348                                 return (ret);
 349                 }
 350                 die->die_ab = ab;
 351         }
 352
 353         die->die_offset = ds->ds_size;
 354
 355         /*
 356          * Transform the DIE to bytes stream.
 357          */
 358         ret = _dwarf_write_uleb128_alloc(&ds->ds_data, &ds->ds_cap,
 359             &ds->ds_size, die->die_ab->ab_entry, error);
 360         if (ret != DW_DLE_NONE)
 361                 return (ret);
 362
 363 attr_gen:
 364
 365         /* Transform the attributes of this DIE. */
 366         ret = _dwarf_attr_gen(dbg, ds, drs, cu, die, pass2, error);
 367         if (ret != DW_DLE_NONE)
 368                 return (ret);
 369
 370         /* Proceed to child DIE. */
 371         if (die->die_child != NULL) {
 372                 ret = _dwarf_die_gen_recursive(dbg, cu, drs, die->die_child,
 373                     pass2, error);
 374                 if (ret != DW_DLE_NONE)
 375                         return (ret);
 376         }
 377
 378         /* Proceed to sibling DIE. */
 379         if (die->die_right != NULL) {
 380                 ret = _dwarf_die_gen_recursive(dbg, cu, drs, die->die_right,
 381                     pass2, error);
 382                 if (ret != DW_DLE_NONE)
 383                         return (ret);
 384         }
 385
 386         /* Write a null DIE indicating the end of current level. */
 387         if (die->die_right == NULL) {
 388                 ret = _dwarf_write_uleb128_alloc(&ds->ds_data, &ds->ds_cap,
 389                     &ds->ds_size, 0, error);
 390                 if (ret != DW_DLE_NONE)
 391                         return (ret);
 392         }
 393
 394         return (DW_DLE_NONE);
 395 }
 396
 397 int
 398 _dwarf_die_gen(Dwarf_P_Debug dbg, Dwarf_CU cu, Dwarf_Rel_Section drs,
 399     Dwarf_Error *error)
 400 {
 401         Dwarf_Abbrev ab, tab;
 402         Dwarf_AttrDef ad, tad;
 403         Dwarf_Die die;
 404         int ret;
 405
 406         assert(dbg != NULL && cu != NULL);
 407         assert(dbg->dbgp_root_die != NULL);
 408
 409         die = dbg->dbgp_root_die;
 410
 411         /*
 412          * Insert a DW_AT_stmt_list attribute into root DIE, if there are
 413          * line number information.
 414          */
 415         if (!STAILQ_EMPTY(&dbg->dbgp_lineinfo->li_lnlist))
 416                 RCHECK(_dwarf_add_AT_dataref(dbg, die, DW_AT_stmt_list, 0, 0,
 417                     ".debug_line", NULL, error));
 418
 419         RCHECK(_dwarf_die_gen_recursive(dbg, cu, drs, die, 0, error));
 420
 421         if (cu->cu_pass2)
 422                 RCHECK(_dwarf_die_gen_recursive(dbg, cu, drs, die, 1, error));
 423
 424         return (DW_DLE_NONE);
 425
 426 gen_fail:
 427
 428         HASH_ITER(ab_hh, cu->cu_abbrev_hash, ab, tab) {
 429                 HASH_DELETE(ab_hh, cu->cu_abbrev_hash, ab);
 430                 STAILQ_FOREACH_SAFE(ad, &ab->ab_attrdef, ad_next, tad) {
 431                         STAILQ_REMOVE(&ab->ab_attrdef, ad, _Dwarf_AttrDef,
 432                             ad_next);
 433                         free(ad);
 434                 }
 435                 free(ab);
 436         }
 437
 438         return (ret);
 439 }
 440
 441 void
 442 _dwarf_die_pro_cleanup(Dwarf_P_Debug dbg)
 443 {
 444         Dwarf_P_Die die, tdie;
 445         Dwarf_P_Attribute at, tat;
 446
 447         assert(dbg != NULL && dbg->dbg_mode == DW_DLC_WRITE);
 448
 449         STAILQ_FOREACH_SAFE(die, &dbg->dbgp_dielist, die_pro_next, tdie) {
 450                 STAILQ_FOREACH_SAFE(at, &die->die_attr, at_next, tat) {
 451                         STAILQ_REMOVE(&die->die_attr, at, _Dwarf_Attribute,
 452                             at_next);
 453                         free(at);
 454                 }
 455                 free(die);
 456         }
 457 }