xref: /openbsd-src/usr.bin/ctfconv/parse.c (revision ae3cb403620ab940fbaabb3055fac045a63d56b7)
1 /*	$OpenBSD: parse.c,v 1.10 2017/10/31 10:08:51 mpi Exp $ */
2 
3 /*
4  * Copyright (c) 2016-2017 Martin Pieuchot
5  * Copyright (c) 2016 Jasper Lievisse Adriaanse <jasper@openbsd.org>
6  *
7  * Permission to use, copy, modify, and distribute this software for any
8  * purpose with or without fee is hereby granted, provided that the above
9  * copyright notice and this permission notice appear in all copies.
10  *
11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18  */
19 
20 /*
21  * DWARF to IT (internal type) representation parser.
22  */
23 
24 #include <sys/queue.h>
25 #include <sys/tree.h>
26 #include <sys/types.h>
27 #include <sys/ctf.h>
28 
29 #include <assert.h>
30 #include <limits.h>
31 #include <err.h>
32 #include <stdlib.h>
33 #include <string.h>
34 
35 #include "itype.h"
36 #include "xmalloc.h"
37 #include "dwarf.h"
38 #include "dw.h"
39 #include "pool.h"
40 
41 #ifdef DEBUG
42 #include <stdio.h>
43 #endif
44 
45 #ifndef NOPOOL
46 struct pool it_pool, im_pool, ir_pool;
47 #endif /* NOPOOL */
48 
49 #ifndef nitems
50 #define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
51 #endif
52 
53 #define DPRINTF(x...)	do { /*printf(x)*/ } while (0)
54 
55 #define VOID_OFFSET	1	/* Fake offset for generating "void" type. */
56 
57 /*
58  * Tree used to resolve per-CU types based on their offset in
59  * the abbrev section.
60  */
61 RB_HEAD(ioff_tree, itype);
62 
63 /*
64  * Per-type trees used to merge existing types with the ones of
65  * a newly parsed CU.
66  */
67 RB_HEAD(itype_tree, itype)	 itypet[CTF_K_MAX];
68 
69 /*
70  * Tree of symbols used to build a list matching the order of
71  * the ELF symbol table.
72  */
73 struct isymb_tree	 isymbt;
74 
75 struct itype		*void_it;		/* no type is emited for void */
76 uint16_t		 tidx, fidx, oidx;	/* type, func & object IDs */
77 uint16_t		 long_tidx;		/* index of "long", for array */
78 
79 
80 void		 cu_stat(void);
81 void		 cu_parse(struct dwcu *, struct itype_queue *,
82 		     struct ioff_tree *);
83 void		 cu_resolve(struct dwcu *, struct itype_queue *,
84 		     struct ioff_tree *);
85 void		 cu_reference(struct dwcu *, struct itype_queue *);
86 void		 cu_merge(struct dwcu *, struct itype_queue *);
87 
88 struct itype	*parse_base(struct dwdie *, size_t);
89 struct itype	*parse_refers(struct dwdie *, size_t, int);
90 struct itype	*parse_array(struct dwdie *, size_t);
91 struct itype	*parse_enum(struct dwdie *, size_t);
92 struct itype	*parse_struct(struct dwdie *, size_t, int, size_t);
93 struct itype	*parse_function(struct dwdie *, size_t);
94 struct itype	*parse_funcptr(struct dwdie *, size_t);
95 struct itype	*parse_variable(struct dwdie *, size_t);
96 
97 void		 subparse_subrange(struct dwdie *, size_t, struct itype *);
98 void		 subparse_enumerator(struct dwdie *, size_t, struct itype *);
99 void		 subparse_member(struct dwdie *, size_t, struct itype *, size_t);
100 void		 subparse_arguments(struct dwdie *, size_t, struct itype *);
101 
102 size_t		 dav2val(struct dwaval *, size_t);
103 const char	*dav2str(struct dwaval *);
104 const char	*enc2name(unsigned short);
105 
106 struct itype	*it_new(uint64_t, size_t, const char *, uint32_t, uint16_t,
107 		     uint64_t, uint16_t, unsigned int);
108 void		 it_merge(struct itype *, struct itype *);
109 void		 it_reference(struct itype *);
110 void		 it_free(struct itype *);
111 int		 it_cmp(struct itype *, struct itype *);
112 int		 it_name_cmp(struct itype *, struct itype *);
113 int		 it_off_cmp(struct itype *, struct itype *);
114 void		 ir_add(struct itype *, struct itype *);
115 void		 ir_purge(struct itype *);
116 struct imember	*im_new(const char *, size_t, size_t);
117 
118 RB_GENERATE(itype_tree, itype, it_node, it_cmp);
119 RB_GENERATE(isymb_tree, itype, it_node, it_name_cmp);
120 RB_GENERATE(ioff_tree, itype, it_node, it_off_cmp);
121 
122 /*
123  * Construct a list of internal type and functions based on DWARF
124  * INFO and ABBREV sections.
125  *
126  * Multiple CUs are supported.
127  */
128 void
129 dwarf_parse(const char *infobuf, size_t infolen, const char *abbuf,
130     size_t ablen)
131 {
132 	struct dwbuf		 info = { .buf = infobuf, .len = infolen };
133 	struct dwbuf		 abbrev = { .buf = abbuf, .len = ablen };
134 	struct dwcu		*dcu = NULL;
135 	struct ioff_tree	 cu_iofft;
136 	struct itype_queue	 cu_itypeq;
137 	struct itype		*it;
138 	int			 i;
139 
140 	for (i = 0; i < CTF_K_MAX; i++)
141 		RB_INIT(&itypet[i]);
142 	RB_INIT(&isymbt);
143 
144 	void_it = it_new(++tidx, VOID_OFFSET, "void", 0,
145 	    CTF_INT_SIGNED, 0, CTF_K_INTEGER, 0);
146 	TAILQ_INSERT_TAIL(&itypeq, void_it, it_next);
147 
148 	while (dw_cu_parse(&info, &abbrev, infolen, &dcu) == 0) {
149 		TAILQ_INIT(&cu_itypeq);
150 
151 		/* We use a tree to speed-up type resolution. */
152 		RB_INIT(&cu_iofft);
153 
154 		/* Parse this CU */
155 		cu_parse(dcu, &cu_itypeq, &cu_iofft);
156 
157 		/* Resolve its types. */
158 		cu_resolve(dcu, &cu_itypeq, &cu_iofft);
159 		assert(RB_EMPTY(&cu_iofft));
160 
161 		/* Mark used type as such. */
162 		cu_reference(dcu, &cu_itypeq);
163 
164 #ifdef DEBUG
165 		/* Dump statistics for current CU. */
166 		cu_stat();
167 #endif
168 
169 		/* Merge them with the common type list. */
170 		cu_merge(dcu, &cu_itypeq);
171 
172 		dw_dcu_free(dcu);
173 	}
174 
175 	/* We force array's index type to be 'long', for that we need its ID. */
176 	RB_FOREACH(it, itype_tree, &itypet[CTF_K_INTEGER]) {
177 		if (it_name(it) == NULL || it->it_size != (8 * sizeof(long)))
178 			continue;
179 
180 		if (strcmp(it_name(it), "unsigned") == 0) {
181 			long_tidx = it->it_idx;
182 			break;
183 		}
184 	}
185 }
186 
187 struct itype *
188 it_new(uint64_t index, size_t off, const char *name, uint32_t size,
189     uint16_t enc, uint64_t ref, uint16_t type, unsigned int flags)
190 {
191 	struct itype *it;
192 #ifndef NOPOOL
193 	static int it_pool_inited = 0;
194 
195 	if (!it_pool_inited) {
196 		pool_init(&it_pool, "it", 512, sizeof(struct itype));
197 		pool_init(&im_pool, "im", 1024, sizeof(struct imember));
198 		pool_init(&ir_pool, "ir", 1024, sizeof(struct itref));
199 		it_pool_inited = 1;
200 	}
201 #endif
202 
203 	assert((name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ)));
204 
205 	it = pmalloc(&it_pool, sizeof(*it));
206 	SIMPLEQ_INIT(&it->it_refs);
207 	TAILQ_INIT(&it->it_members);
208 	it->it_off = off;
209 	it->it_ref = ref;
210 	it->it_refp = NULL;
211 	it->it_size = size;
212 	it->it_nelems = 0;
213 	it->it_enc = enc;
214 	it->it_idx = index;
215 	it->it_type = type;
216 	it->it_flags = flags;
217 
218 	if (name == NULL) {
219 		it->it_flags |= ITF_ANON;
220 	} else {
221 		size_t n;
222 
223 		if ((n = strlcpy(it->it_name, name, ITNAME_MAX)) > ITNAME_MAX)
224 			warnx("name %s too long %zd > %d", name, n, ITNAME_MAX);
225 	}
226 
227 	return it;
228 }
229 
230 struct itype *
231 it_dup(struct itype *it)
232 {
233 	struct imember *copim, *im;
234 	struct itype *copit;
235 
236 	copit = it_new(it->it_idx, it->it_off, it_name(it), it->it_size,
237 	    it->it_enc, it->it_ref, it->it_type, it->it_flags);
238 
239 	copit->it_refp = it->it_refp;
240 	copit->it_nelems = it->it_nelems;
241 
242 	TAILQ_FOREACH(im, &it->it_members, im_next) {
243 		copim = im_new(im_name(im), im->im_ref, im->im_off);
244 		copim->im_refp = im->im_refp;
245 		TAILQ_INSERT_TAIL(&copit->it_members, copim, im_next);
246 	}
247 
248 	return copit;
249 }
250 
251 /*
252  * Merge the content of ``it'', the full type declaration into the
253  * forwarding representation ``fwd''.
254  */
255 void
256 it_merge(struct itype *fwd, struct itype *it)
257 {
258 	assert(fwd->it_flags & ITF_FORWARD);
259 	assert(fwd->it_type == it->it_type);
260 	assert(TAILQ_EMPTY(&fwd->it_members));
261 	assert(SIMPLEQ_EMPTY(&it->it_refs));
262 
263 	fwd->it_off = it->it_off;
264 	fwd->it_ref = it->it_ref;
265 	fwd->it_refp = it->it_refp;
266 	fwd->it_size = it->it_size;
267 	fwd->it_nelems = it->it_nelems;
268 	fwd->it_enc = it->it_enc;
269 	fwd->it_flags = it->it_flags;
270 
271 	TAILQ_CONCAT(&fwd->it_members, &it->it_members, im_next);
272 	assert(TAILQ_EMPTY(&it->it_members));
273 }
274 
275 const char *
276 it_name(struct itype *it)
277 {
278 	if (!(it->it_flags & ITF_ANON))
279 		return it->it_name;
280 
281 	return NULL;
282 }
283 
284 void
285 it_reference(struct itype *it)
286 {
287 	struct imember *im;
288 
289 	if (it == NULL || it->it_flags & ITF_USED)
290 		return;
291 
292 	it->it_flags |= ITF_USED;
293 
294 	it_reference(it->it_refp);
295 	TAILQ_FOREACH(im, &it->it_members, im_next)
296 		it_reference(im->im_refp);
297 }
298 
299 void
300 it_free(struct itype *it)
301 {
302 	struct imember *im;
303 
304 	if (it == NULL)
305 		return;
306 
307 	while ((im = TAILQ_FIRST(&it->it_members)) != NULL) {
308 		TAILQ_REMOVE(&it->it_members, im, im_next);
309 		pfree(&im_pool, im);
310 	}
311 
312 	ir_purge(it);
313 	pfree(&it_pool, it);
314 }
315 
316 /*
317  * Return 0 if ``a'' matches ``b''.
318  */
319 int
320 it_cmp(struct itype *a, struct itype *b)
321 {
322 	int diff;
323 
324 	if ((diff = (a->it_type - b->it_type)) != 0)
325 		return diff;
326 
327 	/* Match by name */
328 	if (!(a->it_flags & ITF_ANON) && !(b->it_flags & ITF_ANON))
329 		return strcmp(it_name(a), it_name(b));
330 
331 	/* Only one of them is anonym */
332 	if ((a->it_flags & ITF_ANON) != (b->it_flags & ITF_ANON))
333 		return (a->it_flags & ITF_ANON) ? -1 : 1;
334 
335 	/* Match by reference */
336 	if ((a->it_refp != NULL) && (b->it_refp != NULL))
337 		return it_cmp(a->it_refp, b->it_refp);
338 
339 	return 1;
340 }
341 
342 int
343 it_name_cmp(struct itype *a, struct itype *b)
344 {
345 	int diff;
346 
347 	if ((diff = strcmp(it_name(a), it_name(b))) != 0)
348 		return diff;
349 
350 	return ((a->it_flags|ITF_MASK) - (b->it_flags|ITF_MASK));
351 }
352 
353 int
354 it_off_cmp(struct itype *a, struct itype *b)
355 {
356 	return a->it_off - b->it_off;
357 }
358 
359 void
360 ir_add(struct itype *it, struct itype *tmp)
361 {
362 	struct itref *ir;
363 
364 	SIMPLEQ_FOREACH(ir, &tmp->it_refs, ir_next) {
365 		if (ir->ir_itp == it)
366 			return;
367 	}
368 
369 	ir = pmalloc(&ir_pool, sizeof(*ir));
370 	ir->ir_itp = it;
371 	SIMPLEQ_INSERT_TAIL(&tmp->it_refs, ir, ir_next);
372 }
373 
374 void
375 ir_purge(struct itype *it)
376 {
377 	struct itref *ir;
378 
379 	while ((ir = SIMPLEQ_FIRST(&it->it_refs)) != NULL) {
380 		SIMPLEQ_REMOVE_HEAD(&it->it_refs, ir_next);
381 		pfree(&ir_pool, ir);
382 	}
383 }
384 
385 struct imember *
386 im_new(const char *name, size_t ref, size_t off)
387 {
388 	struct imember *im;
389 
390 	im = pmalloc(&im_pool, sizeof(*im));
391 	im->im_ref = ref;
392 	im->im_off = off;
393 	im->im_refp = NULL;
394 	if (name == NULL) {
395 		im->im_flags = IMF_ANON;
396 	} else {
397 		size_t n;
398 
399 		n = strlcpy(im->im_name, name, ITNAME_MAX);
400 		if (n > ITNAME_MAX)
401 			warnx("name %s too long %zd > %d", name, n,
402 			    ITNAME_MAX);
403 		im->im_flags = 0;
404 	}
405 
406 	return im;
407 }
408 
409 const char *
410 im_name(struct imember *im)
411 {
412 	if (!(im->im_flags & IMF_ANON))
413 		return im->im_name;
414 
415 	return NULL;
416 }
417 
418 void
419 cu_stat(void)
420 {
421 #ifndef NOPOOL
422 	pool_dump();
423 #endif
424 }
425 
426 /*
427  * Iterate over all types found in a given CU.  For all non-resolved types
428  * use their DWARF relative offset to find the relative type they are pointing
429  * to.  The CU offset tree, `cuot', is used to speedup relative type lookup.
430  */
431 void
432 cu_resolve(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
433 {
434 	struct itype	*it, *ref, tmp;
435 	struct imember	*im;
436 	unsigned int	 toresolve;
437 	size_t		 off = dcu->dcu_offset;
438 
439 	TAILQ_FOREACH(it, cutq, it_next) {
440 		if (!(it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)))
441 			continue;
442 
443 		/* If this type references another one, try to find it. */
444 		if (it->it_flags & ITF_UNRES) {
445 			tmp.it_off = it->it_ref + off;
446 			ref = RB_FIND(ioff_tree, cuot, &tmp);
447 			if (ref != NULL) {
448 				it->it_refp = ref;
449 				ir_add(it, ref);
450 				it->it_flags &= ~ITF_UNRES;
451 			}
452 		}
453 
454 		/* If this type has members, resolve all of them. */
455 		toresolve = it->it_nelems;
456 		if ((it->it_flags & ITF_UNRES_MEMB) && toresolve > 0) {
457 			TAILQ_FOREACH(im, &it->it_members, im_next) {
458 				tmp.it_off = im->im_ref + off;
459 				ref = RB_FIND(ioff_tree, cuot, &tmp);
460 				if (ref != NULL) {
461 					im->im_refp = ref;
462 					ir_add(it, ref);
463 					toresolve--;
464 				}
465 			}
466 			if (toresolve == 0)
467 				it->it_flags &= ~ITF_UNRES_MEMB;
468 		}
469 #if defined(DEBUG)
470 		if (it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)) {
471 			printf("0x%zx: %s type=%d unresolved 0x%llx",
472 			    it->it_off, it_name(it), it->it_type, it->it_ref);
473 			if (toresolve)
474 				printf(": %d members", toresolve);
475 			TAILQ_FOREACH(im, &it->it_members, im_next) {
476 				if (im->im_refp != NULL)
477 					continue;
478 				printf("\n%zu: %s", im->im_ref, im_name(im));
479 			}
480 			printf("\n");
481 		}
482 #endif /* defined(DEBUG) */
483 	}
484 
485 	/* We'll reuse the tree for the next CU, so empty it. */
486 	RB_FOREACH_SAFE(it, ioff_tree, cuot, ref)
487 		RB_REMOVE(ioff_tree, cuot, it);
488 }
489 
490 void
491 cu_reference(struct dwcu *dcu, struct itype_queue *cutq)
492 {
493 	struct itype *it;
494 
495 	TAILQ_FOREACH(it, cutq, it_next) {
496 		if (it->it_flags & (ITF_OBJ|ITF_FUNC))
497 			it_reference(it);
498 	}
499 }
500 
501 /*
502  * Merge type representation from a CU with already known types.
503  */
504 void
505 cu_merge(struct dwcu *dcu, struct itype_queue *cutq)
506 {
507 	struct itype *it, *nit, *prev, *first;
508 	int diff;
509 
510 	/* First ``it'' that needs a duplicate check. */
511 	first = TAILQ_FIRST(cutq);
512 	if (first == NULL)
513 		return;
514 
515 	TAILQ_CONCAT(&itypeq, cutq, it_next);
516 
517 	/*
518 	 * First pass: merge types
519 	 */
520 	for (it = first; it != NULL; it = nit) {
521 		nit = TAILQ_NEXT(it, it_next);
522 
523 		/* Move functions & variable to their own list. */
524 		if (it->it_flags & (ITF_FUNC|ITF_OBJ)) {
525 			/*
526 			 * FIXME: allow static variables with the same name
527 			 * to be of different type.
528 			 */
529 			if (RB_FIND(isymb_tree, &isymbt, it) == NULL)
530 				RB_INSERT(isymb_tree, &isymbt, it);
531 			continue;
532 		}
533 
534 		/* Look if we already have this type. */
535 		if (it->it_flags & ITF_USED)
536 			prev = RB_FIND(itype_tree, &itypet[it->it_type], it);
537 		else
538 			prev = NULL;
539 
540 		if (prev != NULL) {
541 			struct itype *old = it;
542 			struct itref *ir;
543 			struct imember *im;
544 
545 			/* Substitute references */
546 			while ((ir = SIMPLEQ_FIRST(&old->it_refs)) != NULL) {
547 				it = ir->ir_itp;
548 
549 				SIMPLEQ_REMOVE_HEAD(&old->it_refs, ir_next);
550 				pfree(&ir_pool, ir);
551 
552 				if (it->it_refp == old)
553 					it->it_refp = prev;
554 
555 				TAILQ_FOREACH(im, &it->it_members, im_next) {
556 					if (im->im_refp == old)
557 						im->im_refp = prev;
558 				}
559 			}
560 
561 			/* If we first got a forward reference, complete it. */
562 			if ((prev->it_flags & ITF_FORWARD) &&
563 			    (old->it_flags & ITF_FORWARD) == 0)
564 			    	it_merge(prev, old);
565 
566 			old->it_flags &= ~ITF_USED;
567 		} else if (it->it_flags & ITF_USED) {
568 			RB_INSERT(itype_tree, &itypet[it->it_type], it);
569 		}
570 	}
571 
572 	/*
573 	 * Second pass: update indexes
574 	 */
575 	diff = 0;
576 	for (it = first; it != NULL; it = nit) {
577 		nit = TAILQ_NEXT(it, it_next);
578 
579 		if (it->it_flags & (ITF_FUNC|ITF_OBJ))
580 			continue;
581 
582 		/* Adjust indexes */
583 		if (it->it_flags & ITF_USED) {
584 			it->it_idx -= diff;
585 			continue;
586 		}
587 
588 		/* Remove unused */
589 		TAILQ_REMOVE(&itypeq, it, it_next);
590 		it_free(it);
591 		diff++;
592 	}
593 
594 	/* Update global index to match removed entries. */
595 	it = TAILQ_LAST(&itypeq, itype_queue);
596 	while (it->it_flags & (ITF_FUNC|ITF_OBJ))
597 		it = TAILQ_PREV(it, itype_queue, it_next);
598 
599 	tidx = it->it_idx;
600 }
601 
602 /*
603  * Parse a CU.
604  */
605 void
606 cu_parse(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
607 {
608 	struct itype *it = NULL;
609 	struct dwdie *die;
610 	size_t psz = dcu->dcu_psize;
611 	size_t off = dcu->dcu_offset;
612 
613 	assert(RB_EMPTY(cuot));
614 
615 	SIMPLEQ_FOREACH(die, &dcu->dcu_dies, die_next) {
616 		uint64_t tag = die->die_dab->dab_tag;
617 
618 		switch (tag) {
619 		case DW_TAG_array_type:
620 			it = parse_array(die, dcu->dcu_psize);
621 			break;
622 		case DW_TAG_enumeration_type:
623 			it = parse_enum(die, dcu->dcu_psize);
624 			break;
625 		case DW_TAG_pointer_type:
626 			it = parse_refers(die, psz, CTF_K_POINTER);
627 			break;
628 		case DW_TAG_structure_type:
629 			it = parse_struct(die, psz, CTF_K_STRUCT, off);
630 			if (it == NULL)
631 				continue;
632 			break;
633 		case DW_TAG_typedef:
634 			it = parse_refers(die, psz, CTF_K_TYPEDEF);
635 			break;
636 		case DW_TAG_union_type:
637 			it = parse_struct(die, psz, CTF_K_UNION, off);
638 			if (it == NULL)
639 				continue;
640 			break;
641 		case DW_TAG_base_type:
642 			it = parse_base(die, psz);
643 			if (it == NULL)
644 				continue;
645 			break;
646 		case DW_TAG_const_type:
647 			it = parse_refers(die, psz, CTF_K_CONST);
648 			break;
649 		case DW_TAG_volatile_type:
650 			it = parse_refers(die, psz, CTF_K_VOLATILE);
651 			break;
652 		case DW_TAG_restrict_type:
653 			it = parse_refers(die, psz, CTF_K_RESTRICT);
654 			break;
655 		case DW_TAG_subprogram:
656 			it = parse_function(die, psz);
657 			if (it == NULL)
658 				continue;
659 			break;
660 		case DW_TAG_subroutine_type:
661 			it = parse_funcptr(die, psz);
662 			break;
663 		/*
664 		 * Children are assumed to be right after their parent in
665 		 * the list.  The parent parsing function takes care of
666 		 * parsing them.
667 		 */
668 		 case DW_TAG_member:
669 			 assert(it->it_type == CTF_K_STRUCT ||
670 			    it->it_type == CTF_K_UNION ||
671 			    it->it_type == CTF_K_ENUM);
672 			continue;
673 		 case DW_TAG_subrange_type:
674 			assert(it->it_type == CTF_K_ARRAY);
675 			continue;
676 		case DW_TAG_formal_parameter:
677 			/*
678 			 * If we skipped the second inline definition,
679 			 * skip its arguments.
680 			 */
681 			if (it == NULL)
682 				continue;
683 
684 			/* See comment in subparse_arguments(). */
685 			if (it->it_type == CTF_K_STRUCT ||
686 			    it->it_type == CTF_K_UNION ||
687 			    it->it_type == CTF_K_ENUM ||
688 			    it->it_type == CTF_K_TYPEDEF)
689 				continue;
690 
691 			if (it->it_flags & ITF_OBJ)
692 				continue;
693 
694 			assert(it->it_type == CTF_K_FUNCTION);
695 			continue;
696 		case DW_TAG_variable:
697 			it = parse_variable(die, psz);
698 			/* Unnamed variables are discarded. */
699 			if (it == NULL)
700 				continue;
701 			break;
702 #if 1
703 		case DW_TAG_lexical_block:
704 		case DW_TAG_inlined_subroutine:
705 			continue;
706 #endif
707 		case DW_TAG_compile_unit:
708 		default:
709 			DPRINTF("%s\n", dw_tag2name(tag));
710 			continue;
711 		}
712 
713 		TAILQ_INSERT_TAIL(cutq, it, it_next);
714 		RB_INSERT(ioff_tree, cuot, it);
715 	}
716 }
717 
718 struct itype *
719 parse_base(struct dwdie *die, size_t psz)
720 {
721 	struct itype *it;
722 	struct dwaval *dav;
723 	uint16_t encoding, enc = 0, bits = 0;
724 	int type;
725 
726 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
727 		switch (dav->dav_dat->dat_attr) {
728 		case DW_AT_encoding:
729 			enc = dav2val(dav, psz);
730 			break;
731 		case DW_AT_byte_size:
732 			bits = 8 * dav2val(dav, psz);
733 			break;
734 		default:
735 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
736 			break;
737 		}
738 	}
739 
740 	switch (enc) {
741 	case DW_ATE_unsigned:
742 	case DW_ATE_address:
743 		encoding = 0;
744 		type = CTF_K_INTEGER;
745 		break;
746 	case DW_ATE_unsigned_char:
747 		encoding = CTF_INT_CHAR;
748 		type = CTF_K_INTEGER;
749 		break;
750 	case DW_ATE_signed:
751 		encoding = CTF_INT_SIGNED;
752 		type = CTF_K_INTEGER;
753 		break;
754 	case DW_ATE_signed_char:
755 		encoding = CTF_INT_SIGNED | CTF_INT_CHAR;
756 		type = CTF_K_INTEGER;
757 		break;
758 	case DW_ATE_boolean:
759 		encoding = CTF_INT_SIGNED | CTF_INT_BOOL;
760 		type = CTF_K_INTEGER;
761 		break;
762 	case DW_ATE_float:
763 		if (bits < psz)
764 			encoding = CTF_FP_SINGLE;
765 		else if (bits == psz)
766 			encoding = CTF_FP_DOUBLE;
767 		else
768 			encoding = CTF_FP_LDOUBLE;
769 		type = CTF_K_FLOAT;
770 		break;
771 	case DW_ATE_complex_float:
772 		if (bits < psz)
773 			encoding = CTF_FP_CPLX;
774 		else if (bits == psz)
775 			encoding = CTF_FP_DCPLX;
776 		else
777 			encoding = CTF_FP_LDCPLX;
778 		type = CTF_K_FLOAT;
779 		break;
780 	case DW_ATE_imaginary_float:
781 		if (bits < psz)
782 			encoding = CTF_FP_IMAGRY;
783 		else if (bits == psz)
784 			encoding = CTF_FP_DIMAGRY;
785 		else
786 			encoding = CTF_FP_LDIMAGRY;
787 		type = CTF_K_FLOAT;
788 		break;
789 	default:
790 		DPRINTF("unknown encoding: %d\n", enc);
791 		return (NULL);
792 	}
793 
794 	it = it_new(++tidx, die->die_offset, enc2name(enc), bits,
795 	    encoding, 0, type, 0);
796 
797 	return it;
798 }
799 
800 struct itype *
801 parse_refers(struct dwdie *die, size_t psz, int type)
802 {
803 	struct itype *it;
804 	struct dwaval *dav;
805 	const char *name = NULL;
806 	size_t ref = 0, size = 0;
807 
808 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
809 		switch (dav->dav_dat->dat_attr) {
810 		case DW_AT_name:
811 			name = dav2str(dav);
812 			break;
813 		case DW_AT_type:
814 			ref = dav2val(dav, psz);
815 			break;
816 		case DW_AT_byte_size:
817 			size = dav2val(dav, psz);
818 			assert(size < UINT_MAX);
819 			break;
820 		default:
821 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
822 			break;
823 		}
824 	}
825 
826 	it = it_new(++tidx, die->die_offset, name, size, 0, ref, type,
827 	    ITF_UNRES);
828 
829 	if (it->it_ref == 0 && (it->it_size == sizeof(void *) ||
830 	    type == CTF_K_CONST || type == CTF_K_VOLATILE ||
831 	    type == CTF_K_POINTER)) {
832 		/* Work around GCC/clang not emiting a type for void */
833 		it->it_flags &= ~ITF_UNRES;
834 		it->it_ref = VOID_OFFSET;
835 		it->it_refp = void_it;
836 	}
837 
838 	return it;
839 }
840 
841 struct itype *
842 parse_array(struct dwdie *die, size_t psz)
843 {
844 	struct itype *it;
845 	struct dwaval *dav;
846 	const char *name = NULL;
847 	size_t ref = 0;
848 
849 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
850 		switch (dav->dav_dat->dat_attr) {
851 		case DW_AT_name:
852 			name = dav2str(dav);
853 			break;
854 		case DW_AT_type:
855 			ref = dav2val(dav, psz);
856 			break;
857 		default:
858 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
859 			break;
860 		}
861 	}
862 
863 	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_ARRAY,
864 	    ITF_UNRES);
865 
866 	subparse_subrange(die, psz, it);
867 
868 	return it;
869 }
870 
871 struct itype *
872 parse_enum(struct dwdie *die, size_t psz)
873 {
874 	struct itype *it;
875 	struct dwaval *dav;
876 	const char *name = NULL;
877 	size_t size = 0;
878 
879 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
880 		switch (dav->dav_dat->dat_attr) {
881 		case DW_AT_byte_size:
882 			size = dav2val(dav, psz);
883 			assert(size < UINT_MAX);
884 			break;
885 		case DW_AT_name:
886 			name = dav2str(dav);
887 			break;
888 		default:
889 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
890 			break;
891 		}
892 	}
893 
894 	it = it_new(++tidx, die->die_offset, name, size, 0, 0, CTF_K_ENUM, 0);
895 
896 	subparse_enumerator(die, psz, it);
897 
898 	return it;
899 }
900 
901 void
902 subparse_subrange(struct dwdie *die, size_t psz, struct itype *it)
903 {
904 	struct dwaval *dav;
905 
906 	assert(it->it_type == CTF_K_ARRAY);
907 
908 	if (die->die_dab->dab_children == DW_CHILDREN_no)
909 		return;
910 
911 	/*
912 	 * This loop assumes that the children of a DIE are just
913 	 * after it on the list.
914 	 */
915 	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
916 		uint64_t tag = die->die_dab->dab_tag;
917 		size_t nelems = 0;
918 
919 		if (tag != DW_TAG_subrange_type)
920 			break;
921 
922 		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
923 			switch (dav->dav_dat->dat_attr) {
924 			case DW_AT_count:
925 				nelems = dav2val(dav, psz);
926 				break;
927 			case DW_AT_upper_bound:
928 				nelems = dav2val(dav, psz) + 1;
929 				break;
930 			default:
931 				DPRINTF("%s\n",
932 				    dw_at2name(dav->dav_dat->dat_attr));
933 				break;
934 			}
935 		}
936 
937 		assert(nelems < UINT_MAX);
938 		it->it_nelems = nelems;
939 	}
940 }
941 
942 void
943 subparse_enumerator(struct dwdie *die, size_t psz, struct itype *it)
944 {
945 	struct imember *im;
946 	struct dwaval *dav;
947 
948 	assert(it->it_type == CTF_K_ENUM);
949 
950 	if (die->die_dab->dab_children == DW_CHILDREN_no)
951 		return;
952 
953 	/*
954 	 * This loop assumes that the children of a DIE are just
955 	 * after it on the list.
956 	 */
957 	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
958 		uint64_t tag = die->die_dab->dab_tag;
959 		size_t val = 0;
960 		const char *name = NULL;
961 
962 		if (tag != DW_TAG_enumerator)
963 			break;
964 
965 		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
966 			switch (dav->dav_dat->dat_attr) {
967 			case DW_AT_name:
968 				name = dav2str(dav);
969 				break;
970 			case DW_AT_const_value:
971 				val = dav2val(dav, psz);
972 				break;
973 			default:
974 				DPRINTF("%s\n",
975 				    dw_at2name(dav->dav_dat->dat_attr));
976 				break;
977 			}
978 		}
979 
980 		if (name == NULL) {
981 			warnx("%s with anon member", it_name(it));
982 			continue;
983 		}
984 
985 		im = im_new(name, val, 0);
986 		assert(it->it_nelems < UINT_MAX);
987 		it->it_nelems++;
988 		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
989 	}
990 }
991 
992 struct itype *
993 parse_struct(struct dwdie *die, size_t psz, int type, size_t off)
994 {
995 	struct itype *it = NULL;
996 	struct dwaval *dav;
997 	const char *name = NULL;
998 	unsigned int flags = 0;
999 	size_t size = 0;
1000 	int forward = 0;
1001 
1002 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1003 		switch (dav->dav_dat->dat_attr) {
1004 		case DW_AT_declaration:
1005 			forward = dav2val(dav, psz);
1006 			break;
1007 		case DW_AT_byte_size:
1008 			size = dav2val(dav, psz);
1009 			assert(size < UINT_MAX);
1010 			break;
1011 		case DW_AT_name:
1012 			name = dav2str(dav);
1013 			break;
1014 		default:
1015 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1016 			break;
1017 		}
1018 	}
1019 
1020 
1021 	if (forward)
1022 		flags = ITF_FORWARD;
1023 	it = it_new(++tidx, die->die_offset, name, size, 0, 0, type, flags);
1024 	subparse_member(die, psz, it, off);
1025 
1026 	return it;
1027 }
1028 
1029 void
1030 subparse_member(struct dwdie *die, size_t psz, struct itype *it, size_t offset)
1031 {
1032 	struct imember *im;
1033 	struct dwaval *dav;
1034 	const char *name;
1035 	size_t off = 0, ref = 0, bits = 0;
1036 	uint8_t lvl = die->die_lvl;
1037 
1038 	assert(it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION);
1039 
1040 	if (die->die_dab->dab_children == DW_CHILDREN_no)
1041 		return;
1042 
1043 	/*
1044 	 * This loop assumes that the children of a DIE are just
1045 	 * after it on the list.
1046 	 */
1047 	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
1048 		int64_t tag = die->die_dab->dab_tag;
1049 
1050 		name = NULL;
1051 		if (die->die_lvl <= lvl)
1052 			break;
1053 
1054 		/* Skip members of members */
1055 		if (die->die_lvl > lvl + 1)
1056 			continue;
1057 		/*
1058 		 * Nested declaration.
1059 		 *
1060 		 * This matches the case where a ``struct'', ``union'',
1061 		 * ``enum'' or ``typedef'' is first declared "inside" a
1062 		 * union or struct declaration.
1063 		 */
1064 		if (tag == DW_TAG_structure_type || tag == DW_TAG_union_type ||
1065 		    tag == DW_TAG_enumeration_type || tag == DW_TAG_typedef)
1066 			continue;
1067 
1068 		it->it_flags |= ITF_UNRES_MEMB;
1069 
1070 		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1071 			switch (dav->dav_dat->dat_attr) {
1072 			case DW_AT_name:
1073 				name = dav2str(dav);
1074 				break;
1075 			case DW_AT_type:
1076 				ref = dav2val(dav, psz);
1077 				break;
1078 			case DW_AT_data_member_location:
1079 				off = 8 * dav2val(dav, psz);
1080 				break;
1081 			case DW_AT_bit_size:
1082 				bits = dav2val(dav, psz);
1083 				assert(bits < USHRT_MAX);
1084 				break;
1085 			default:
1086 				DPRINTF("%s\n",
1087 				    dw_at2name(dav->dav_dat->dat_attr));
1088 				break;
1089 			}
1090 		}
1091 
1092 		/*
1093 		 * When a structure is declared inside an union, we
1094 		 * have to generate a reference to make the resolver
1095 		 * happy.
1096 		 */
1097 		if ((ref == 0) && (tag == DW_TAG_structure_type))
1098 			ref = die->die_offset - offset;
1099 
1100 		im = im_new(name, ref, off);
1101 		assert(it->it_nelems < UINT_MAX);
1102 		it->it_nelems++;
1103 		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
1104 	}
1105 }
1106 
1107 
1108 void
1109 subparse_arguments(struct dwdie *die, size_t psz, struct itype *it)
1110 {
1111 	struct imember *im;
1112 	struct dwaval *dav;
1113 	size_t ref = 0;
1114 
1115 	assert(it->it_type == CTF_K_FUNCTION);
1116 
1117 	if (die->die_dab->dab_children == DW_CHILDREN_no)
1118 		return;
1119 
1120 	/*
1121 	 * This loop assumes that the children of a DIE are after it
1122 	 * on the list.
1123 	 */
1124 	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
1125 		uint64_t tag = die->die_dab->dab_tag;
1126 
1127 		if (tag == DW_TAG_unspecified_parameters) {
1128 			/* TODO */
1129 			continue;
1130 		}
1131 
1132 		/*
1133 		 * Nested declaration.
1134 		 *
1135 		 * This matches the case where a ``struct'', ``union'',
1136 		 * ``enum'' or ``typedef'' is first declared "inside" a
1137 		 * function declaration.
1138 		 */
1139 		if (tag == DW_TAG_structure_type || tag == DW_TAG_union_type ||
1140 		    tag == DW_TAG_enumeration_type || tag == DW_TAG_typedef)
1141 			continue;
1142 
1143 		if (tag != DW_TAG_formal_parameter)
1144 			break;
1145 
1146 		it->it_flags |= ITF_UNRES_MEMB;
1147 
1148 		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1149 			switch (dav->dav_dat->dat_attr) {
1150 			case DW_AT_type:
1151 				ref = dav2val(dav, psz);
1152 				break;
1153 			default:
1154 				DPRINTF("%s\n",
1155 				    dw_at2name(dav->dav_dat->dat_attr));
1156 				break;
1157 			}
1158 		}
1159 
1160 		im = im_new(NULL, ref, 0);
1161 		assert(it->it_nelems < UINT_MAX);
1162 		it->it_nelems++;
1163 		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
1164 	}
1165 }
1166 
1167 struct itype *
1168 parse_function(struct dwdie *die, size_t psz)
1169 {
1170 	struct itype *it;
1171 	struct dwaval *dav;
1172 	const char *name = NULL;
1173 	size_t ref = 0;
1174 
1175 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1176 		switch (dav->dav_dat->dat_attr) {
1177 		case DW_AT_name:
1178 			name = dav2str(dav);
1179 			break;
1180 		case DW_AT_type:
1181 			ref = dav2val(dav, psz);
1182 			break;
1183 		case DW_AT_abstract_origin:
1184 			/*
1185 			 * Skip second empty definition for inline
1186 			 * functions.
1187 			 */
1188 			return NULL;
1189 		default:
1190 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1191 			break;
1192 		}
1193 	}
1194 
1195 	/*
1196 	 * Work around for clang 4.0 generating DW_TAG_subprogram without
1197 	 * any attribute.
1198 	 */
1199 	if (name == NULL)
1200 		return NULL;
1201 
1202 	it = it_new(++fidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
1203 	    ITF_UNRES|ITF_FUNC);
1204 
1205 	subparse_arguments(die, psz, it);
1206 
1207 	if (it->it_ref == 0) {
1208 		/* Work around GCC not emiting a type for void */
1209 		it->it_flags &= ~ITF_UNRES;
1210 		it->it_ref = VOID_OFFSET;
1211 		it->it_refp = void_it;
1212 	}
1213 
1214 	return it;
1215 }
1216 
1217 struct itype *
1218 parse_funcptr(struct dwdie *die, size_t psz)
1219 {
1220 	struct itype *it;
1221 	struct dwaval *dav;
1222 	const char *name = NULL;
1223 	size_t ref = 0;
1224 
1225 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1226 		switch (dav->dav_dat->dat_attr) {
1227 		case DW_AT_name:
1228 			name = dav2str(dav);
1229 			break;
1230 		case DW_AT_type:
1231 			ref = dav2val(dav, psz);
1232 			break;
1233 		default:
1234 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1235 			break;
1236 		}
1237 	}
1238 
1239 	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
1240 	    ITF_UNRES);
1241 
1242 	subparse_arguments(die, psz, it);
1243 
1244 	if (it->it_ref == 0) {
1245 		/* Work around GCC not emiting a type for void */
1246 		it->it_flags &= ~ITF_UNRES;
1247 		it->it_ref = VOID_OFFSET;
1248 		it->it_refp = void_it;
1249 	}
1250 
1251 	return it;
1252 }
1253 
1254 struct itype *
1255 parse_variable(struct dwdie *die, size_t psz)
1256 {
1257 	struct itype *it = NULL;
1258 	struct dwaval *dav;
1259 	const char *name = NULL;
1260 	size_t ref = 0;
1261 	int forward = 0;
1262 
1263 	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1264 		switch (dav->dav_dat->dat_attr) {
1265 		case DW_AT_declaration:
1266 			forward = dav2val(dav, psz);
1267 			break;
1268 		case DW_AT_name:
1269 			name = dav2str(dav);
1270 			break;
1271 		case DW_AT_type:
1272 			ref = dav2val(dav, psz);
1273 			break;
1274 		default:
1275 			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1276 			break;
1277 		}
1278 	}
1279 
1280 
1281 	if (!forward && name != NULL) {
1282 		it = it_new(++oidx, die->die_offset, name, 0, 0, ref, 0,
1283 		    ITF_UNRES|ITF_OBJ);
1284 	}
1285 
1286 	return it;
1287 }
1288 
1289 size_t
1290 dav2val(struct dwaval *dav, size_t psz)
1291 {
1292 	uint64_t val = (uint64_t)-1;
1293 
1294 	switch (dav->dav_dat->dat_form) {
1295 	case DW_FORM_addr:
1296 	case DW_FORM_ref_addr:
1297 		if (psz == sizeof(uint32_t))
1298 			val = dav->dav_u32;
1299 		else
1300 			val = dav->dav_u64;
1301 		break;
1302 	case DW_FORM_block1:
1303 	case DW_FORM_block2:
1304 	case DW_FORM_block4:
1305 	case DW_FORM_block:
1306 		dw_loc_parse(&dav->dav_buf, NULL, &val, NULL);
1307 		break;
1308 	case DW_FORM_flag:
1309 	case DW_FORM_data1:
1310 	case DW_FORM_ref1:
1311 		val = dav->dav_u8;
1312 		break;
1313 	case DW_FORM_data2:
1314 	case DW_FORM_ref2:
1315 		val = dav->dav_u16;
1316 		break;
1317 	case DW_FORM_data4:
1318 	case DW_FORM_ref4:
1319 		val = dav->dav_u32;
1320 		break;
1321 	case DW_FORM_sdata:
1322 	case DW_FORM_data8:
1323 	case DW_FORM_ref8:
1324 		val = dav->dav_u64;
1325 		break;
1326 	case DW_FORM_strp:
1327 		val = dav->dav_u32;
1328 		break;
1329 	case DW_FORM_flag_present:
1330 		val = 1;
1331 		break;
1332 	default:
1333 		break;
1334 	}
1335 
1336 	return val;
1337 }
1338 
1339 const char *
1340 dav2str(struct dwaval *dav)
1341 {
1342 	const char *str = NULL;
1343 	extern const char *dstrbuf;
1344 	extern size_t dstrlen;
1345 
1346 	switch (dav->dav_dat->dat_form) {
1347 	case DW_FORM_string:
1348 		str = dav->dav_str;
1349 		break;
1350 	case DW_FORM_strp:
1351 		if (dav->dav_u32 >= dstrlen)
1352 			str = NULL;
1353 		else
1354 			str = dstrbuf + dav->dav_u32;
1355 		break;
1356 	default:
1357 		break;
1358 	}
1359 
1360 	return str;
1361 }
1362 
1363 const char *
1364 enc2name(unsigned short enc)
1365 {
1366 	static const char *enc_name[] = { "address", "boolean", "complex float",
1367 	    "float", "signed", "char", "unsigned", "unsigned char",
1368 	    "imaginary float", "packed decimal", "numeric string", "edited",
1369 	    "signed fixed", "unsigned fixed", "decimal float" };
1370 
1371 	if (enc > 0 && enc <= nitems(enc_name))
1372 		return enc_name[enc - 1];
1373 
1374 	return "invalid";
1375 }
1376