libdwarf_die.c revision 260697 
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
30ELFTC_VCSID("$Id: libdwarf_die.c 2948 2013-05-30 21:25:52Z kaiwang27 $");
31
32int
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
51static 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. */
80Dwarf_Die
81_dwarf_die_find(Dwarf_Die die, Dwarf_Unsigned off)
82{
83	Dwarf_Debug dbg;
84	Dwarf_CU cu;
85	Dwarf_Die die1;
86	Dwarf_Error de;
87	int ret;
88
89	cu = die->die_cu;
90	dbg = die->die_dbg;
91
92	ret = _dwarf_die_parse(dbg, dbg->dbg_info_sec, cu, cu->cu_dwarf_size,
93	    off, cu->cu_next_offset, &die1, 0, &de);
94
95	if (ret == DW_DLE_NONE)
96		return (die1);
97	else
98		return (NULL);
99}
100
101int
102_dwarf_die_parse(Dwarf_Debug dbg, Dwarf_Section *ds, Dwarf_CU cu,
103    int dwarf_size, uint64_t offset, uint64_t next_offset, Dwarf_Die *ret_die,
104    int search_sibling, Dwarf_Error *error)
105{
106	Dwarf_Abbrev ab;
107	Dwarf_AttrDef ad;
108	Dwarf_Die die;
109	uint64_t abnum;
110	uint64_t die_offset;
111	int ret, level;
112
113	assert(cu != NULL);
114
115	level = 1;
116	die = NULL;
117
118	while (offset < next_offset && offset < ds->ds_size) {
119
120		die_offset = offset;
121
122		abnum = _dwarf_read_uleb128(ds->ds_data, &offset);
123
124		if (abnum == 0) {
125			if (level == 0 || !search_sibling)
126				return (DW_DLE_NO_ENTRY);
127
128			/*
129			 * Return to previous DIE level.
130			 */
131			level--;
132			continue;
133		}
134
135		if ((ret = _dwarf_abbrev_find(cu, abnum, &ab, error)) !=
136		    DW_DLE_NONE)
137			return (ret);
138
139		if ((ret = _dwarf_die_add(cu, die_offset, abnum, ab, &die,
140		    error)) != DW_DLE_NONE)
141			return (ret);
142
143		STAILQ_FOREACH(ad, &ab->ab_attrdef, ad_next) {
144			if ((ret = _dwarf_attr_init(dbg, ds, &offset,
145			    dwarf_size, cu, die, ad, ad->ad_form, 0,
146			    error)) != DW_DLE_NONE)
147				return (ret);
148		}
149
150		die->die_next_off = offset;
151		if (search_sibling && level > 0) {
152			dwarf_dealloc(dbg, die, DW_DLA_DIE);
153			if (ab->ab_children == DW_CHILDREN_yes) {
154				/* Advance to next DIE level. */
155				level++;
156			}
157		} else {
158			*ret_die = die;
159			return (DW_DLE_NONE);
160		}
161	}
162
163	return (DW_DLE_NO_ENTRY);
164}
165
166void
167_dwarf_die_link(Dwarf_P_Die die, Dwarf_P_Die parent, Dwarf_P_Die child,
168    Dwarf_P_Die left_sibling, Dwarf_P_Die right_sibling)
169{
170	Dwarf_P_Die last_child;
171
172	assert(die != NULL);
173
174	if (parent) {
175
176		/* Disconnect from old parent. */
177		if (die->die_parent) {
178			if (die->die_parent != parent) {
179				if (die->die_parent->die_child == die)
180					die->die_parent->die_child = NULL;
181				die->die_parent = NULL;
182                     }
183		}
184
185		/* Find the last child of this parent. */
186		last_child = parent->die_child;
187		if (last_child) {
188			while (last_child->die_right != NULL)
189				last_child = last_child->die_right;
190		}
191
192		/* Connect to new parent. */
193		die->die_parent = parent;
194
195		/*
196		 * Attach this DIE to the end of sibling list. If new
197		 * parent doesn't have any child, set this DIE as the
198		 * first child.
199		 */
200		if (last_child) {
201			assert(last_child->die_right == NULL);
202			last_child->die_right = die;
203			die->die_left = last_child;
204		} else
205			parent->die_child = die;
206	}
207
208	if (child) {
209
210		/* Disconnect from old child. */
211		if (die->die_child) {
212			if (die->die_child != child) {
213				die->die_child->die_parent = NULL;
214				die->die_child = NULL;
215			}
216		}
217
218		/* Connect to new child. */
219		die->die_child = child;
220		child->die_parent = die;
221	}
222
223	if (left_sibling) {
224
225		/* Disconnect from old left sibling. */
226		if (die->die_left) {
227			if (die->die_left != left_sibling) {
228				die->die_left->die_right = NULL;
229				die->die_left = NULL;
230			}
231		}
232
233		/* Connect to new right sibling. */
234		die->die_left = left_sibling;
235		left_sibling->die_right = die;
236	}
237
238	if (right_sibling) {
239
240		/* Disconnect from old right sibling. */
241		if (die->die_right) {
242			if (die->die_right != right_sibling) {
243				die->die_right->die_left = NULL;
244				die->die_right = NULL;
245			}
246		}
247
248		/* Connect to new right sibling. */
249		die->die_right = right_sibling;
250		right_sibling->die_left = die;
251	}
252}
253
254int
255_dwarf_die_count_links(Dwarf_P_Die parent, Dwarf_P_Die child,
256    Dwarf_P_Die left_sibling, Dwarf_P_Die right_sibling)
257{
258	int count;
259
260	count = 0;
261
262	if (parent)
263		count++;
264	if (child)
265		count++;
266	if (left_sibling)
267		count++;
268	if (right_sibling)
269		count++;
270
271	return (count);
272}
273
274static int
275_dwarf_die_gen_recursive(Dwarf_P_Debug dbg, Dwarf_CU cu, Dwarf_Rel_Section drs,
276    Dwarf_P_Die die, int pass2, Dwarf_Error *error)
277{
278	Dwarf_P_Section ds;
279	Dwarf_Abbrev ab;
280	Dwarf_Attribute at;
281	Dwarf_AttrDef ad;
282	int match, ret;
283
284	ds = dbg->dbgp_info;
285	assert(ds != NULL);
286
287	if (pass2)
288		goto attr_gen;
289
290	/*
291	 * Add DW_AT_sibling attribute for DIEs with children, so consumers
292	 * can quickly scan chains of siblings, while ignoring the children
293	 * of individual siblings.
294	 */
295	if (die->die_child && die->die_right) {
296		if (_dwarf_attr_find(die, DW_AT_sibling) == NULL)
297			(void) dwarf_add_AT_reference(dbg, die, DW_AT_sibling,
298			    die->die_right, error);
299	}
300
301	/*
302	 * Search abbrev list to find a matching entry.
303	 */
304	die->die_ab = NULL;
305	for (ab = cu->cu_abbrev_hash; ab != NULL; ab = ab->ab_hh.next) {
306		if (die->die_tag != ab->ab_tag)
307			continue;
308		if (ab->ab_children == DW_CHILDREN_no && die->die_child != NULL)
309			continue;
310		if (ab->ab_children == DW_CHILDREN_yes &&
311		    die->die_child == NULL)
312			continue;
313		at = STAILQ_FIRST(&die->die_attr);
314		ad = STAILQ_FIRST(&ab->ab_attrdef);
315		match = 1;
316		while (at != NULL && ad != NULL) {
317			if (at->at_attrib != ad->ad_attrib ||
318			    at->at_form != ad->ad_form) {
319				match = 0;
320				break;
321			}
322			at = STAILQ_NEXT(at, at_next);
323			ad = STAILQ_NEXT(ad, ad_next);
324		}
325		if ((at == NULL && ad != NULL) || (at != NULL && ad == NULL))
326			match = 0;
327		if (match) {
328			die->die_ab = ab;
329			break;
330		}
331	}
332
333	/*
334	 * Create a new abbrev entry if we can not reuse any existing one.
335	 */
336	if (die->die_ab == NULL) {
337		ret = _dwarf_abbrev_add(cu, ++cu->cu_abbrev_cnt, die->die_tag,
338		    die->die_child != NULL ? DW_CHILDREN_yes : DW_CHILDREN_no,
339		    0, &ab, error);
340		if (ret != DW_DLE_NONE)
341			return (ret);
342		STAILQ_FOREACH(at, &die->die_attr, at_next) {
343			ret = _dwarf_attrdef_add(dbg, ab, at->at_attrib,
344			    at->at_form, 0, NULL, error);
345			if (ret != DW_DLE_NONE)
346				return (ret);
347		}
348		die->die_ab = ab;
349	}
350
351	die->die_offset = ds->ds_size;
352
353	/*
354	 * Transform the DIE to bytes stream.
355	 */
356	ret = _dwarf_write_uleb128_alloc(&ds->ds_data, &ds->ds_cap,
357	    &ds->ds_size, die->die_ab->ab_entry, error);
358	if (ret != DW_DLE_NONE)
359		return (ret);
360
361attr_gen:
362
363	/* Transform the attributes of this DIE. */
364	ret = _dwarf_attr_gen(dbg, ds, drs, cu, die, pass2, error);
365	if (ret != DW_DLE_NONE)
366		return (ret);
367
368	/* Proceed to child DIE. */
369	if (die->die_child != NULL) {
370		ret = _dwarf_die_gen_recursive(dbg, cu, drs, die->die_child,
371		    pass2, error);
372		if (ret != DW_DLE_NONE)
373			return (ret);
374	}
375
376	/* Proceed to sibling DIE. */
377	if (die->die_right != NULL) {
378		ret = _dwarf_die_gen_recursive(dbg, cu, drs, die->die_right,
379		    pass2, error);
380		if (ret != DW_DLE_NONE)
381			return (ret);
382	}
383
384	/* Write a null DIE indicating the end of current level. */
385	if (die->die_right == NULL) {
386		ret = _dwarf_write_uleb128_alloc(&ds->ds_data, &ds->ds_cap,
387		    &ds->ds_size, 0, error);
388		if (ret != DW_DLE_NONE)
389			return (ret);
390	}
391
392	return (DW_DLE_NONE);
393}
394
395int
396_dwarf_die_gen(Dwarf_P_Debug dbg, Dwarf_CU cu, Dwarf_Rel_Section drs,
397    Dwarf_Error *error)
398{
399	Dwarf_Abbrev ab, tab;
400	Dwarf_AttrDef ad, tad;
401	Dwarf_Die die;
402	int ret;
403
404	assert(dbg != NULL && cu != NULL);
405	assert(dbg->dbgp_root_die != NULL);
406
407	die = dbg->dbgp_root_die;
408
409	/*
410	 * Insert a DW_AT_stmt_list attribute into root DIE, if there are
411	 * line number information.
412	 */
413	if (!STAILQ_EMPTY(&dbg->dbgp_lineinfo->li_lnlist))
414		RCHECK(_dwarf_add_AT_dataref(dbg, die, DW_AT_stmt_list, 0, 0,
415		    ".debug_line", NULL, error));
416
417	RCHECK(_dwarf_die_gen_recursive(dbg, cu, drs, die, 0, error));
418
419	if (cu->cu_pass2)
420		RCHECK(_dwarf_die_gen_recursive(dbg, cu, drs, die, 1, error));
421
422	return (DW_DLE_NONE);
423
424gen_fail:
425
426	HASH_ITER(ab_hh, cu->cu_abbrev_hash, ab, tab) {
427		HASH_DELETE(ab_hh, cu->cu_abbrev_hash, ab);
428		STAILQ_FOREACH_SAFE(ad, &ab->ab_attrdef, ad_next, tad) {
429			STAILQ_REMOVE(&ab->ab_attrdef, ad, _Dwarf_AttrDef,
430			    ad_next);
431			free(ad);
432		}
433		free(ab);
434	}
435
436	return (ret);
437}
438
439void
440_dwarf_die_pro_cleanup(Dwarf_P_Debug dbg)
441{
442	Dwarf_P_Die die, tdie;
443	Dwarf_P_Attribute at, tat;
444
445	assert(dbg != NULL && dbg->dbg_mode == DW_DLC_WRITE);
446
447	STAILQ_FOREACH_SAFE(die, &dbg->dbgp_dielist, die_pro_next, tdie) {
448		STAILQ_FOREACH_SAFE(at, &die->die_attr, at_next, tat) {
449			STAILQ_REMOVE(&die->die_attr, at, _Dwarf_Attribute,
450			    at_next);
451			free(at);
452		}
453		free(die);
454	}
455}
456