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
_dwarf_die_alloc(Dwarf_Debug dbg,Dwarf_Die * ret_die,Dwarf_Error * error)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
_dwarf_die_add(Dwarf_CU cu,uint64_t offset,uint64_t abnum,Dwarf_Abbrev ab,Dwarf_Die * diep,Dwarf_Error * error)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
_dwarf_die_find(Dwarf_Die die,Dwarf_Unsigned off)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
_dwarf_die_parse(Dwarf_Debug dbg,Dwarf_Section * ds,Dwarf_CU cu,int dwarf_size,uint64_t offset,uint64_t next_offset,Dwarf_Die * ret_die,int search_sibling,Dwarf_Error * error)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
_dwarf_die_link(Dwarf_P_Die die,Dwarf_P_Die parent,Dwarf_P_Die child,Dwarf_P_Die left_sibling,Dwarf_P_Die right_sibling)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
_dwarf_die_count_links(Dwarf_P_Die parent,Dwarf_P_Die child,Dwarf_P_Die left_sibling,Dwarf_P_Die right_sibling)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
_dwarf_die_gen_recursive(Dwarf_P_Debug dbg,Dwarf_CU cu,Dwarf_Rel_Section drs,Dwarf_P_Die die,int pass2,Dwarf_Error * error)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
_dwarf_die_gen(Dwarf_P_Debug dbg,Dwarf_CU cu,Dwarf_Rel_Section drs,Dwarf_Error * error)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
_dwarf_die_pro_cleanup(Dwarf_P_Debug dbg)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