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 } 458