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