IABSD.fr/src/usr.bin/ctfconv/parse.c

Branch : - branch - master - tag -

• Show log

  Commit

• Author : claudio
  Date : 2024-02-22 13:17:18
  Hash : 76af8930
  Message : Rewrite the it_cmp() function to use the common check bigger than, check smaller than logic. There was a bug in this code because of a badly placed ) which I only noticed after rewriting the function since I assumed that C integer promotion is playing tricks with us. OK mpi@

• usr.bin/ctfconv/parse.c

• /*	$OpenBSD: parse.c,v 1.20 2024/02/22 13:17:18 claudio Exp $ */
  
  /*
   * Copyright (c) 2016-2017 Martin Pieuchot
   * Copyright (c) 2016 Jasper Lievisse Adriaanse <jasper@openbsd.org>
   *
   * Permission to use, copy, modify, and distribute this software for any
   * purpose with or without fee is hereby granted, provided that the above
   * copyright notice and this permission notice appear in all copies.
   *
   * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
   * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
   * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
   * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
   * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
   * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
   */
  
  /*
   * DWARF to IT (internal type) representation parser.
   */
  
  #include <sys/queue.h>
  #include <sys/tree.h>
  #include <sys/types.h>
  #include <sys/ctf.h>
  
  #include <assert.h>
  #include <limits.h>
  #include <err.h>
  #include <stdlib.h>
  #include <string.h>
  
  #include "itype.h"
  #include "xmalloc.h"
  #include "dwarf.h"
  #include "dw.h"
  #include "pool.h"
  
  #ifdef DEBUG
  #include <stdio.h>
  #endif
  
  #ifndef NOPOOL
  struct pool it_pool, im_pool, ir_pool;
  #endif /* NOPOOL */
  
  #ifndef nitems
  #define nitems(_a)	(sizeof((_a)) / sizeof((_a)[0]))
  #endif
  
  #ifdef DEBUG
  #define DPRINTF(x...)	do { printf(x); } while (0)
  #else
  #define DPRINTF(x...)	do { ; } while (0)
  #endif
  
  #define VOID_OFFSET	1	/* Fake offset for generating "void" type. */
  
  /*
   * Tree used to resolve per-CU types based on their offset in
   * the abbrev section.
   */
  RB_HEAD(ioff_tree, itype);
  
  /*
   * Per-type trees used to merge existing types with the ones of
   * a newly parsed CU.
   */
  RB_HEAD(itype_tree, itype)	 itypet[CTF_K_MAX];
  
  /*
   * Tree of symbols used to build a list matching the order of
   * the ELF symbol table.
   */
  struct isymb_tree	 isymbt;
  
  struct itype		*void_it;		/* no type is emited for void */
  uint16_t		 tidx, fidx, oidx;	/* type, func & object IDs */
  uint16_t		 long_tidx;		/* index of "long", for array */
  
  
  void		 cu_stat(void);
  void		 cu_parse(struct dwcu *, struct itype_queue *,
  		     struct ioff_tree *);
  void		 cu_resolve(struct dwcu *, struct itype_queue *,
  		     struct ioff_tree *);
  void		 cu_reference(struct dwcu *, struct itype_queue *);
  void		 cu_merge(struct dwcu *, struct itype_queue *);
  
  struct itype	*parse_base(struct dwdie *, size_t);
  struct itype	*parse_refers(struct dwdie *, size_t, int);
  struct itype	*parse_array(struct dwdie *, size_t);
  struct itype	*parse_enum(struct dwdie *, size_t);
  struct itype	*parse_struct(struct dwdie *, size_t, int, size_t);
  struct itype	*parse_function(struct dwdie *, size_t);
  struct itype	*parse_funcptr(struct dwdie *, size_t);
  struct itype	*parse_variable(struct dwdie *, size_t);
  
  void		 subparse_subrange(struct dwdie *, size_t, struct itype *);
  void		 subparse_enumerator(struct dwdie *, size_t, struct itype *);
  void		 subparse_member(struct dwdie *, size_t, struct itype *, size_t);
  void		 subparse_arguments(struct dwdie *, size_t, struct itype *);
  
  size_t		 dav2val(struct dwaval *, size_t);
  const char	*dav2str(struct dwaval *);
  const char	*enc2name(unsigned short);
  
  struct itype	*it_new(uint64_t, size_t, const char *, uint32_t, uint16_t,
  		     uint64_t, uint16_t, unsigned int);
  void		 it_merge(struct itype *, struct itype *);
  void		 it_reference(struct itype *);
  void		 it_free(struct itype *);
  int		 it_cmp(struct itype *, struct itype *);
  int		 it_name_cmp(struct itype *, struct itype *);
  int		 it_off_cmp(struct itype *, struct itype *);
  void		 ir_add(struct itype *, struct itype *);
  void		 ir_purge(struct itype *);
  struct imember	*im_new(const char *, size_t, size_t);
  
  RB_GENERATE(itype_tree, itype, it_node, it_cmp);
  RB_GENERATE(isymb_tree, itype, it_node, it_name_cmp);
  RB_GENERATE(ioff_tree, itype, it_node, it_off_cmp);
  
  /*
   * Construct a list of internal type and functions based on DWARF
   * INFO and ABBREV sections.
   *
   * Multiple CUs are supported.
   */
  void
  dwarf_parse(const char *infobuf, size_t infolen, const char *abbuf,
      size_t ablen)
  {
  	struct dwbuf		 info = { .buf = infobuf, .len = infolen };
  	struct dwbuf		 abbrev = { .buf = abbuf, .len = ablen };
  	struct dwcu		*dcu = NULL;
  	struct ioff_tree	 cu_iofft;
  	struct itype_queue	 cu_itypeq;
  	struct itype		*it;
  	int			 i;
  
  	for (i = 0; i < CTF_K_MAX; i++)
  		RB_INIT(&itypet[i]);
  	RB_INIT(&isymbt);
  
  	void_it = it_new(++tidx, VOID_OFFSET, "void", 0,
  	    CTF_INT_SIGNED, 0, CTF_K_INTEGER, 0);
  	TAILQ_INSERT_TAIL(&itypeq, void_it, it_next);
  
  	while (dw_cu_parse(&info, &abbrev, infolen, &dcu) == 0) {
  		TAILQ_INIT(&cu_itypeq);
  
  		/* We use a tree to speed-up type resolution. */
  		RB_INIT(&cu_iofft);
  
  		/* Parse this CU */
  		cu_parse(dcu, &cu_itypeq, &cu_iofft);
  
  		/* Resolve its types. */
  		cu_resolve(dcu, &cu_itypeq, &cu_iofft);
  		assert(RB_EMPTY(&cu_iofft));
  
  		/* Mark used type as such. */
  		cu_reference(dcu, &cu_itypeq);
  
  #ifdef DEBUG
  		/* Dump statistics for current CU. */
  		cu_stat();
  #endif
  
  		/* Merge them with the common type list. */
  		cu_merge(dcu, &cu_itypeq);
  
  		dw_dcu_free(dcu);
  	}
  
  	/* We force array's index type to be 'long', for that we need its ID. */
  	RB_FOREACH(it, itype_tree, &itypet[CTF_K_INTEGER]) {
  		if (it_name(it) == NULL || it->it_size != (8 * sizeof(long)))
  			continue;
  
  		if (strcmp(it_name(it), "unsigned") == 0) {
  			long_tidx = it->it_idx;
  			break;
  		}
  	}
  }
  
  struct itype *
  it_new(uint64_t index, size_t off, const char *name, uint32_t size,
      uint16_t enc, uint64_t ref, uint16_t type, unsigned int flags)
  {
  	struct itype *it;
  #ifndef NOPOOL
  	static int it_pool_inited = 0;
  
  	if (!it_pool_inited) {
  		pool_init(&it_pool, "it", 512, sizeof(struct itype));
  		pool_init(&im_pool, "im", 1024, sizeof(struct imember));
  		pool_init(&ir_pool, "ir", 1024, sizeof(struct itref));
  		it_pool_inited = 1;
  	}
  #endif
  
  	assert((name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ)));
  
  	it = pmalloc(&it_pool, sizeof(*it));
  	SIMPLEQ_INIT(&it->it_refs);
  	TAILQ_INIT(&it->it_members);
  	it->it_off = off;
  	it->it_ref = ref;
  	it->it_refp = NULL;
  	it->it_size = size;
  	it->it_nelems = 0;
  	it->it_enc = enc;
  	it->it_idx = index;
  	it->it_type = type;
  	it->it_flags = flags;
  
  	if (name == NULL) {
  		it->it_flags |= ITF_ANON;
  	} else {
  		size_t n;
  
  		if ((n = strlcpy(it->it_name, name, ITNAME_MAX)) > ITNAME_MAX)
  			warnx("name %s too long %zd > %d", name, n, ITNAME_MAX);
  	}
  
  	return it;
  }
  
  struct itype *
  it_dup(struct itype *it)
  {
  	struct imember *copim, *im;
  	struct itype *copit;
  
  	copit = it_new(it->it_idx, it->it_off, it_name(it), it->it_size,
  	    it->it_enc, it->it_ref, it->it_type, it->it_flags);
  
  	copit->it_refp = it->it_refp;
  	copit->it_nelems = it->it_nelems;
  
  	TAILQ_FOREACH(im, &it->it_members, im_next) {
  		copim = im_new(im_name(im), im->im_ref, im->im_off);
  		copim->im_refp = im->im_refp;
  		TAILQ_INSERT_TAIL(&copit->it_members, copim, im_next);
  	}
  
  	return copit;
  }
  
  /*
   * Merge the content of ``it'', the full type declaration into the
   * forwarding representation ``fwd''.
   */
  void
  it_merge(struct itype *fwd, struct itype *it)
  {
  	assert(fwd->it_flags & ITF_FORWARD);
  	assert(fwd->it_type == it->it_type);
  	assert(TAILQ_EMPTY(&fwd->it_members));
  	assert(SIMPLEQ_EMPTY(&it->it_refs));
  
  	fwd->it_off = it->it_off;
  	fwd->it_ref = it->it_ref;
  	fwd->it_refp = it->it_refp;
  	fwd->it_size = it->it_size;
  	fwd->it_nelems = it->it_nelems;
  	fwd->it_enc = it->it_enc;
  	fwd->it_flags = it->it_flags;
  
  	TAILQ_CONCAT(&fwd->it_members, &it->it_members, im_next);
  	assert(TAILQ_EMPTY(&it->it_members));
  }
  
  const char *
  it_name(struct itype *it)
  {
  	if (!(it->it_flags & ITF_ANON))
  		return it->it_name;
  
  	return NULL;
  }
  
  void
  it_reference(struct itype *it)
  {
  	struct imember *im;
  
  	if (it == NULL || it->it_flags & ITF_USED)
  		return;
  
  	it->it_flags |= ITF_USED;
  
  	it_reference(it->it_refp);
  	TAILQ_FOREACH(im, &it->it_members, im_next)
  		it_reference(im->im_refp);
  }
  
  void
  it_free(struct itype *it)
  {
  	struct imember *im;
  
  	if (it == NULL)
  		return;
  
  	while ((im = TAILQ_FIRST(&it->it_members)) != NULL) {
  		TAILQ_REMOVE(&it->it_members, im, im_next);
  		pfree(&im_pool, im);
  	}
  
  	ir_purge(it);
  	pfree(&it_pool, it);
  }
  
  /*
   * Return 0 if ``a'' matches ``b''.
   */
  int
  it_cmp(struct itype *a, struct itype *b)
  {
  	if (a->it_type > b->it_type)
  		return 1;
  	if (a->it_type < b->it_type)
  		return -1;
  
  	/* Basic types need to have the same encoding and size. */
  	if ((a->it_type == CTF_K_INTEGER || a->it_type == CTF_K_FLOAT)) {
  		if (a->it_enc > b->it_enc)
  			return 1;
  		if (a->it_enc < b->it_enc)
  			return -1;
  		if (a->it_size > b->it_size)
  			return 1;
  		if (a->it_size < b->it_size)
  			return -1;
  	}
  
  	/* Arrays need to have same number of elements */
  	if (a->it_type == CTF_K_ARRAY) {
  		if (a->it_nelems > b->it_nelems)
  			return 1;
  		if (a->it_nelems < b->it_nelems)
  			return -1;
  	}
  
  	/* Match by name */
  	if (!(a->it_flags & ITF_ANON) && !(b->it_flags & ITF_ANON))
  		return strcmp(it_name(a), it_name(b));
  
  	/* Only one of them is anonym */
  	if ((a->it_flags & ITF_ANON) != (b->it_flags & ITF_ANON))
  		return (a->it_flags & ITF_ANON) ? -1 : 1;
  
  	/* Match by reference */
  	if ((a->it_refp != NULL) && (b->it_refp != NULL))
  		return it_cmp(a->it_refp, b->it_refp);
  	if (a->it_refp == NULL)
  		return -1;
  	if (b->it_refp == NULL)
  		return 1;
  
  	return 0;
  }
  
  int
  it_name_cmp(struct itype *a, struct itype *b)
  {
  	int diff;
  
  	if ((diff = strcmp(it_name(a), it_name(b))) != 0)
  		return diff;
  
  	return ((a->it_flags|ITF_MASK) - (b->it_flags|ITF_MASK));
  }
  
  int
  it_off_cmp(struct itype *a, struct itype *b)
  {
  	return a->it_off - b->it_off;
  }
  
  void
  ir_add(struct itype *it, struct itype *tmp)
  {
  	struct itref *ir;
  
  	SIMPLEQ_FOREACH(ir, &tmp->it_refs, ir_next) {
  		if (ir->ir_itp == it)
  			return;
  	}
  
  	ir = pmalloc(&ir_pool, sizeof(*ir));
  	ir->ir_itp = it;
  	SIMPLEQ_INSERT_TAIL(&tmp->it_refs, ir, ir_next);
  }
  
  void
  ir_purge(struct itype *it)
  {
  	struct itref *ir;
  
  	while ((ir = SIMPLEQ_FIRST(&it->it_refs)) != NULL) {
  		SIMPLEQ_REMOVE_HEAD(&it->it_refs, ir_next);
  		pfree(&ir_pool, ir);
  	}
  }
  
  struct imember *
  im_new(const char *name, size_t ref, size_t off)
  {
  	struct imember *im;
  
  	im = pmalloc(&im_pool, sizeof(*im));
  	im->im_ref = ref;
  	im->im_off = off;
  	im->im_refp = NULL;
  	if (name == NULL) {
  		im->im_flags = IMF_ANON;
  	} else {
  		size_t n;
  
  		n = strlcpy(im->im_name, name, ITNAME_MAX);
  		if (n > ITNAME_MAX)
  			warnx("name %s too long %zd > %d", name, n,
  			    ITNAME_MAX);
  		im->im_flags = 0;
  	}
  
  	return im;
  }
  
  const char *
  im_name(struct imember *im)
  {
  	if (!(im->im_flags & IMF_ANON))
  		return im->im_name;
  
  	return NULL;
  }
  
  void
  cu_stat(void)
  {
  #ifndef NOPOOL
  	pool_dump();
  #endif
  }
  
  /*
   * Iterate over all types found in a given CU.  For all non-resolved types
   * use their DWARF relative offset to find the relative type they are pointing
   * to.  The CU offset tree, `cuot', is used to speedup relative type lookup.
   */
  void
  cu_resolve(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
  {
  	struct itype	*it, *ref, tmp;
  	struct imember	*im;
  	unsigned int	 toresolve;
  	size_t		 off = dcu->dcu_offset;
  
  	TAILQ_FOREACH(it, cutq, it_next) {
  		if (!(it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)))
  			continue;
  
  		/* If this type references another one, try to find it. */
  		if (it->it_flags & ITF_UNRES) {
  			tmp.it_off = it->it_ref + off;
  			ref = RB_FIND(ioff_tree, cuot, &tmp);
  			if (ref != NULL) {
  				it->it_refp = ref;
  				ir_add(it, ref);
  				it->it_flags &= ~ITF_UNRES;
  			}
  		}
  
  		/* If this type has members, resolve all of them. */
  		toresolve = it->it_nelems;
  		if ((it->it_flags & ITF_UNRES_MEMB) && toresolve > 0) {
  			TAILQ_FOREACH(im, &it->it_members, im_next) {
  				tmp.it_off = im->im_ref + off;
  				ref = RB_FIND(ioff_tree, cuot, &tmp);
  				if (ref != NULL) {
  					im->im_refp = ref;
  					ir_add(it, ref);
  					toresolve--;
  				}
  			}
  			if (toresolve == 0)
  				it->it_flags &= ~ITF_UNRES_MEMB;
  		}
  #if defined(DEBUG)
  		if (it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)) {
  			printf("0x%zx: %s type=%d unresolved 0x%llx",
  			    it->it_off, it_name(it), it->it_type, it->it_ref);
  			if (toresolve)
  				printf(": %d members", toresolve);
  			TAILQ_FOREACH(im, &it->it_members, im_next) {
  				if (im->im_refp != NULL)
  					continue;
  				printf("\n%zu: %s", im->im_ref, im_name(im));
  			}
  			printf("\n");
  		}
  #endif /* defined(DEBUG) */
  	}
  
  	/* We'll reuse the tree for the next CU, so empty it. */
  	RB_FOREACH_SAFE(it, ioff_tree, cuot, ref)
  		RB_REMOVE(ioff_tree, cuot, it);
  }
  
  void
  cu_reference(struct dwcu *dcu, struct itype_queue *cutq)
  {
  	struct itype *it;
  
  	TAILQ_FOREACH(it, cutq, it_next) {
  		if (it->it_flags & (ITF_OBJ|ITF_FUNC))
  			it_reference(it);
  	}
  }
  
  /*
   * Merge type representation from a CU with already known types.
   */
  void
  cu_merge(struct dwcu *dcu, struct itype_queue *cutq)
  {
  	struct itype *it, *nit, *prev, *first;
  	int diff;
  
  	/* First ``it'' that needs a duplicate check. */
  	first = TAILQ_FIRST(cutq);
  	if (first == NULL)
  		return;
  
  	TAILQ_CONCAT(&itypeq, cutq, it_next);
  
  	/*
  	 * First pass: merge types
  	 */
  	for (it = first; it != NULL; it = nit) {
  		nit = TAILQ_NEXT(it, it_next);
  
  		/* Move functions & variable to their own list. */
  		if (it->it_flags & (ITF_FUNC|ITF_OBJ)) {
  			/*
  			 * FIXME: allow static variables with the same name
  			 * to be of different type.
  			 */
  			if (RB_FIND(isymb_tree, &isymbt, it) == NULL)
  				RB_INSERT(isymb_tree, &isymbt, it);
  			continue;
  		}
  
  		/* Look if we already have this type. */
  		if (it->it_flags & ITF_USED)
  			prev = RB_FIND(itype_tree, &itypet[it->it_type], it);
  		else
  			prev = NULL;
  
  		if (prev != NULL) {
  			struct itype *old = it;
  			struct itref *ir;
  			struct imember *im;
  
  			/* Substitute references */
  			while ((ir = SIMPLEQ_FIRST(&old->it_refs)) != NULL) {
  				it = ir->ir_itp;
  
  				SIMPLEQ_REMOVE_HEAD(&old->it_refs, ir_next);
  				pfree(&ir_pool, ir);
  
  				if (it->it_refp == old)
  					it->it_refp = prev;
  
  				TAILQ_FOREACH(im, &it->it_members, im_next) {
  					if (im->im_refp == old)
  						im->im_refp = prev;
  				}
  			}
  
  			/* If we first got a forward reference, complete it. */
  			if ((prev->it_flags & ITF_FORWARD) &&
  			    (old->it_flags & ITF_FORWARD) == 0)
  			    	it_merge(prev, old);
  
  			old->it_flags &= ~ITF_USED;
  		} else if (it->it_flags & ITF_USED) {
  			RB_INSERT(itype_tree, &itypet[it->it_type], it);
  		}
  	}
  
  	/*
  	 * Second pass: update indexes
  	 */
  	diff = 0;
  	for (it = first; it != NULL; it = nit) {
  		nit = TAILQ_NEXT(it, it_next);
  
  		if (it->it_flags & (ITF_FUNC|ITF_OBJ))
  			continue;
  
  		/* Adjust indexes */
  		if (it->it_flags & ITF_USED) {
  			it->it_idx -= diff;
  			continue;
  		}
  
  		/* Remove unused */
  		TAILQ_REMOVE(&itypeq, it, it_next);
  		it_free(it);
  		diff++;
  	}
  
  	/* Update global index to match removed entries. */
  	it = TAILQ_LAST(&itypeq, itype_queue);
  	while (it->it_flags & (ITF_FUNC|ITF_OBJ))
  		it = TAILQ_PREV(it, itype_queue, it_next);
  
  	tidx = it->it_idx;
  }
  
  /*
   * Parse a CU.
   */
  void
  cu_parse(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
  {
  	struct itype *it = NULL;
  	struct dwdie *die;
  	size_t psz = dcu->dcu_psize;
  	size_t off = dcu->dcu_offset;
  
  	assert(RB_EMPTY(cuot));
  
  	SIMPLEQ_FOREACH(die, &dcu->dcu_dies, die_next) {
  		uint64_t tag = die->die_dab->dab_tag;
  
  		switch (tag) {
  		case DW_TAG_array_type:
  			it = parse_array(die, dcu->dcu_psize);
  			break;
  		case DW_TAG_enumeration_type:
  			it = parse_enum(die, dcu->dcu_psize);
  			break;
  		case DW_TAG_pointer_type:
  			it = parse_refers(die, psz, CTF_K_POINTER);
  			break;
  		case DW_TAG_structure_type:
  			it = parse_struct(die, psz, CTF_K_STRUCT, off);
  			if (it == NULL)
  				continue;
  			break;
  		case DW_TAG_typedef:
  			it = parse_refers(die, psz, CTF_K_TYPEDEF);
  			break;
  		case DW_TAG_union_type:
  			it = parse_struct(die, psz, CTF_K_UNION, off);
  			if (it == NULL)
  				continue;
  			break;
  		case DW_TAG_base_type:
  			it = parse_base(die, psz);
  			if (it == NULL)
  				continue;
  			break;
  		case DW_TAG_const_type:
  			it = parse_refers(die, psz, CTF_K_CONST);
  			break;
  		case DW_TAG_volatile_type:
  			it = parse_refers(die, psz, CTF_K_VOLATILE);
  			break;
  		case DW_TAG_restrict_type:
  			it = parse_refers(die, psz, CTF_K_RESTRICT);
  			break;
  		case DW_TAG_subprogram:
  			it = parse_function(die, psz);
  			if (it == NULL)
  				continue;
  			break;
  		case DW_TAG_subroutine_type:
  			it = parse_funcptr(die, psz);
  			break;
  		/*
  		 * Children are assumed to be right after their parent in
  		 * the list.  The parent parsing function takes care of
  		 * parsing them.
  		 */
  		 case DW_TAG_member:
  			 assert(it->it_type == CTF_K_STRUCT ||
  			    it->it_type == CTF_K_UNION ||
  			    it->it_type == CTF_K_ENUM);
  			continue;
  		 case DW_TAG_subrange_type:
  			assert(it->it_type == CTF_K_ARRAY);
  			continue;
  		case DW_TAG_formal_parameter:
  			/*
  			 * If we skipped the second inline definition,
  			 * skip its arguments.
  			 */
  			if (it == NULL)
  				continue;
  
  			/* See comment in subparse_arguments(). */
  			if (it->it_type == CTF_K_STRUCT ||
  			    it->it_type == CTF_K_UNION ||
  			    it->it_type == CTF_K_ENUM ||
  			    it->it_type == CTF_K_TYPEDEF)
  				continue;
  
  			if (it->it_flags & ITF_OBJ)
  				continue;
  
  			assert(it->it_type == CTF_K_FUNCTION);
  			continue;
  		case DW_TAG_variable:
  			it = parse_variable(die, psz);
  			/* Unnamed variables are discarded. */
  			if (it == NULL)
  				continue;
  			break;
  #if 1
  		case DW_TAG_lexical_block:
  		case DW_TAG_inlined_subroutine:
  			continue;
  #endif
  		case DW_TAG_compile_unit:
  		default:
  			DPRINTF("%s\n", dw_tag2name(tag));
  			continue;
  		}
  
  		TAILQ_INSERT_TAIL(cutq, it, it_next);
  		RB_INSERT(ioff_tree, cuot, it);
  	}
  }
  
  struct itype *
  parse_base(struct dwdie *die, size_t psz)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	uint16_t encoding, enc = 0, bits = 0;
  	int type;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_encoding:
  			enc = dav2val(dav, psz);
  			break;
  		case DW_AT_byte_size:
  			bits = 8 * dav2val(dav, psz);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	switch (enc) {
  	case DW_ATE_unsigned:
  	case DW_ATE_address:
  		encoding = 0;
  		type = CTF_K_INTEGER;
  		break;
  	case DW_ATE_unsigned_char:
  		encoding = CTF_INT_CHAR;
  		type = CTF_K_INTEGER;
  		break;
  	case DW_ATE_signed:
  		encoding = CTF_INT_SIGNED;
  		type = CTF_K_INTEGER;
  		break;
  	case DW_ATE_signed_char:
  		encoding = CTF_INT_SIGNED | CTF_INT_CHAR;
  		type = CTF_K_INTEGER;
  		break;
  	case DW_ATE_boolean:
  		encoding = CTF_INT_SIGNED | CTF_INT_BOOL;
  		type = CTF_K_INTEGER;
  		break;
  	case DW_ATE_float:
  		if (bits < psz)
  			encoding = CTF_FP_SINGLE;
  		else if (bits == psz)
  			encoding = CTF_FP_DOUBLE;
  		else
  			encoding = CTF_FP_LDOUBLE;
  		type = CTF_K_FLOAT;
  		break;
  	case DW_ATE_complex_float:
  		if (bits < psz)
  			encoding = CTF_FP_CPLX;
  		else if (bits == psz)
  			encoding = CTF_FP_DCPLX;
  		else
  			encoding = CTF_FP_LDCPLX;
  		type = CTF_K_FLOAT;
  		break;
  	case DW_ATE_imaginary_float:
  		if (bits < psz)
  			encoding = CTF_FP_IMAGRY;
  		else if (bits == psz)
  			encoding = CTF_FP_DIMAGRY;
  		else
  			encoding = CTF_FP_LDIMAGRY;
  		type = CTF_K_FLOAT;
  		break;
  	default:
  		DPRINTF("unknown encoding: %d\n", enc);
  		return (NULL);
  	}
  
  	it = it_new(++tidx, die->die_offset, enc2name(enc), bits,
  	    encoding, 0, type, 0);
  
  	return it;
  }
  
  struct itype *
  parse_refers(struct dwdie *die, size_t psz, int type)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t ref = 0, size = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		case DW_AT_type:
  			ref = dav2val(dav, psz);
  			break;
  		case DW_AT_byte_size:
  			size = dav2val(dav, psz);
  			assert(size < UINT_MAX);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	it = it_new(++tidx, die->die_offset, name, size, 0, ref, type,
  	    ITF_UNRES);
  
  	if (it->it_ref == 0 && (it->it_size == sizeof(void *) ||
  	    type == CTF_K_CONST || type == CTF_K_VOLATILE ||
  	    type == CTF_K_POINTER || type == CTF_K_TYPEDEF)) {
  		/* Work around GCC/clang not emiting a type for void */
  		it->it_flags &= ~ITF_UNRES;
  		it->it_ref = VOID_OFFSET;
  		it->it_refp = void_it;
  	}
  
  	return it;
  }
  
  struct itype *
  parse_array(struct dwdie *die, size_t psz)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t ref = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		case DW_AT_type:
  			ref = dav2val(dav, psz);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_ARRAY,
  	    ITF_UNRES);
  
  	subparse_subrange(die, psz, it);
  
  	return it;
  }
  
  struct itype *
  parse_enum(struct dwdie *die, size_t psz)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t size = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_byte_size:
  			size = dav2val(dav, psz);
  			assert(size < UINT_MAX);
  			break;
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	it = it_new(++tidx, die->die_offset, name, size, 0, 0, CTF_K_ENUM, 0);
  
  	subparse_enumerator(die, psz, it);
  
  	return it;
  }
  
  void
  subparse_subrange(struct dwdie *die, size_t psz, struct itype *it)
  {
  	struct dwaval *dav;
  
  	assert(it->it_type == CTF_K_ARRAY);
  
  	if (die->die_dab->dab_children == DW_CHILDREN_no)
  		return;
  
  	/*
  	 * This loop assumes that the children of a DIE are just
  	 * after it on the list.
  	 */
  	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
  		uint64_t tag = die->die_dab->dab_tag;
  		size_t nelems = 0;
  
  		if (tag != DW_TAG_subrange_type)
  			break;
  
  		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  			switch (dav->dav_dat->dat_attr) {
  			case DW_AT_count:
  				nelems = dav2val(dav, psz);
  				break;
  			case DW_AT_upper_bound:
  				nelems = dav2val(dav, psz) + 1;
  				break;
  			default:
  				DPRINTF("%s\n",
  				    dw_at2name(dav->dav_dat->dat_attr));
  				break;
  			}
  		}
  
  		assert(nelems < UINT_MAX);
  		it->it_nelems = nelems;
  	}
  }
  
  void
  subparse_enumerator(struct dwdie *die, size_t psz, struct itype *it)
  {
  	struct imember *im;
  	struct dwaval *dav;
  
  	assert(it->it_type == CTF_K_ENUM);
  
  	if (die->die_dab->dab_children == DW_CHILDREN_no)
  		return;
  
  	/*
  	 * This loop assumes that the children of a DIE are just
  	 * after it on the list.
  	 */
  	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
  		uint64_t tag = die->die_dab->dab_tag;
  		size_t val = 0;
  		const char *name = NULL;
  
  		if (tag != DW_TAG_enumerator)
  			break;
  
  		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  			switch (dav->dav_dat->dat_attr) {
  			case DW_AT_name:
  				name = dav2str(dav);
  				break;
  			case DW_AT_const_value:
  				val = dav2val(dav, psz);
  				break;
  			default:
  				DPRINTF("%s\n",
  				    dw_at2name(dav->dav_dat->dat_attr));
  				break;
  			}
  		}
  
  		if (name == NULL) {
  			warnx("%s with anon member", it_name(it));
  			continue;
  		}
  
  		im = im_new(name, val, 0);
  		assert(it->it_nelems < UINT_MAX);
  		it->it_nelems++;
  		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
  	}
  }
  
  struct itype *
  parse_struct(struct dwdie *die, size_t psz, int type, size_t off)
  {
  	struct itype *it = NULL;
  	struct dwaval *dav;
  	const char *name = NULL;
  	unsigned int flags = 0;
  	size_t size = 0;
  	int forward = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_declaration:
  			forward = dav2val(dav, psz);
  			break;
  		case DW_AT_byte_size:
  			size = dav2val(dav, psz);
  			assert(size < UINT_MAX);
  			break;
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  
  	if (forward)
  		flags = ITF_FORWARD;
  	it = it_new(++tidx, die->die_offset, name, size, 0, 0, type, flags);
  	subparse_member(die, psz, it, off);
  
  	return it;
  }
  
  void
  subparse_member(struct dwdie *die, size_t psz, struct itype *it, size_t offset)
  {
  	struct imember *im;
  	struct dwaval *dav;
  	const char *name;
  	size_t off = 0, ref = 0, bits = 0;
  	uint8_t lvl = die->die_lvl;
  
  	assert(it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION);
  
  	if (die->die_dab->dab_children == DW_CHILDREN_no)
  		return;
  
  	/*
  	 * This loop assumes that the children of a DIE are just
  	 * after it on the list.
  	 */
  	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
  		int64_t tag = die->die_dab->dab_tag;
  
  		name = NULL;
  		if (die->die_lvl <= lvl)
  			break;
  
  		/* Skip members of members */
  		if (die->die_lvl > lvl + 1)
  			continue;
  		/*
  		 * Nested declaration.
  		 *
  		 * This matches the case where a ``struct'', ``union'',
  		 * ``enum'' or ``typedef'' is first declared "inside" a
  		 * union or struct declaration.
  		 */
  		if (tag == DW_TAG_structure_type || tag == DW_TAG_union_type ||
  		    tag == DW_TAG_enumeration_type || tag == DW_TAG_typedef)
  			continue;
  
  		it->it_flags |= ITF_UNRES_MEMB;
  
  		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  			switch (dav->dav_dat->dat_attr) {
  			case DW_AT_name:
  				name = dav2str(dav);
  				break;
  			case DW_AT_type:
  				ref = dav2val(dav, psz);
  				break;
  			case DW_AT_data_member_location:
  				off = 8 * dav2val(dav, psz);
  				break;
  			case DW_AT_bit_size:
  				bits = dav2val(dav, psz);
  				assert(bits < USHRT_MAX);
  				break;
  			default:
  				DPRINTF("%s\n",
  				    dw_at2name(dav->dav_dat->dat_attr));
  				break;
  			}
  		}
  
  		/*
  		 * When a structure is declared inside an union, we
  		 * have to generate a reference to make the resolver
  		 * happy.
  		 */
  		if ((ref == 0) && (tag == DW_TAG_structure_type))
  			ref = die->die_offset - offset;
  
  		im = im_new(name, ref, off);
  		assert(it->it_nelems < UINT_MAX);
  		it->it_nelems++;
  		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
  	}
  }
  
  
  void
  subparse_arguments(struct dwdie *die, size_t psz, struct itype *it)
  {
  	struct imember *im;
  	struct dwaval *dav;
  	size_t ref = 0;
  
  	assert(it->it_type == CTF_K_FUNCTION);
  
  	if (die->die_dab->dab_children == DW_CHILDREN_no)
  		return;
  
  	/*
  	 * This loop assumes that the children of a DIE are after it
  	 * on the list.
  	 */
  	while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
  		uint64_t tag = die->die_dab->dab_tag;
  
  		if (tag == DW_TAG_unspecified_parameters) {
  			/* TODO */
  			continue;
  		}
  
  		/*
  		 * Nested declaration.
  		 *
  		 * This matches the case where a ``struct'', ``union'',
  		 * ``enum'', ``typedef'' or ``static'' variable is first
  		 * declared inside a function declaration.
  		 */
  		switch (tag) {
  		case DW_TAG_structure_type:
  		case DW_TAG_union_type:
  		case DW_TAG_enumeration_type:
  		case DW_TAG_typedef:
  		case DW_TAG_variable:
  			continue;
  		default:
  			break;
  		}
  
  		if (tag != DW_TAG_formal_parameter)
  			break;
  
  		it->it_flags |= ITF_UNRES_MEMB;
  
  		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  			switch (dav->dav_dat->dat_attr) {
  			case DW_AT_type:
  				ref = dav2val(dav, psz);
  				break;
  			default:
  				DPRINTF("%s\n",
  				    dw_at2name(dav->dav_dat->dat_attr));
  				break;
  			}
  		}
  
  		im = im_new(NULL, ref, 0);
  		assert(it->it_nelems < UINT_MAX);
  		it->it_nelems++;
  		TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
  	}
  }
  
  struct itype *
  parse_function(struct dwdie *die, size_t psz)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t ref = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		case DW_AT_type:
  			ref = dav2val(dav, psz);
  			break;
  		case DW_AT_abstract_origin:
  			/*
  			 * Skip second empty definition for inline
  			 * functions.
  			 */
  			return NULL;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	/*
  	 * Work around for clang 4.0 generating DW_TAG_subprogram without
  	 * any attribute.
  	 */
  	if (name == NULL)
  		return NULL;
  
  	it = it_new(++fidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
  	    ITF_UNRES|ITF_FUNC);
  
  	subparse_arguments(die, psz, it);
  
  	if (it->it_ref == 0) {
  		/* Work around GCC not emiting a type for void */
  		it->it_flags &= ~ITF_UNRES;
  		it->it_ref = VOID_OFFSET;
  		it->it_refp = void_it;
  	}
  
  	return it;
  }
  
  struct itype *
  parse_funcptr(struct dwdie *die, size_t psz)
  {
  	struct itype *it;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t ref = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		case DW_AT_type:
  			ref = dav2val(dav, psz);
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
  	    ITF_UNRES);
  
  	subparse_arguments(die, psz, it);
  
  	if (it->it_ref == 0) {
  		/* Work around GCC not emiting a type for void */
  		it->it_flags &= ~ITF_UNRES;
  		it->it_ref = VOID_OFFSET;
  		it->it_refp = void_it;
  	}
  
  	return it;
  }
  
  struct itype *
  parse_variable(struct dwdie *die, size_t psz)
  {
  	struct itype *it = NULL;
  	struct dwaval *dav;
  	const char *name = NULL;
  	size_t ref = 0;
  	int forward = 0, global = 0;
  
  	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
  		switch (dav->dav_dat->dat_attr) {
  		case DW_AT_declaration:
  			forward = dav2val(dav, psz);
  			break;
  		case DW_AT_name:
  			name = dav2str(dav);
  			break;
  		case DW_AT_type:
  			ref = dav2val(dav, psz);
  			break;
  		case DW_AT_location:
  			switch (dav->dav_dat->dat_form) {
  			case DW_FORM_block:
  			case DW_FORM_block1:
  			case DW_FORM_block2:
  			case DW_FORM_block4:
  				global = 1;
  				break;
  			default:
  				break;
  			}
  			break;
  		default:
  			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
  			break;
  		}
  	}
  
  
  	if (global && !forward && name != NULL) {
  		it = it_new(++oidx, die->die_offset, name, 0, 0, ref, 0,
  		    ITF_UNRES|ITF_OBJ);
  	}
  
  	return it;
  }
  
  size_t
  dav2val(struct dwaval *dav, size_t psz)
  {
  	uint64_t val = (uint64_t)-1;
  
  	switch (dav->dav_dat->dat_form) {
  	case DW_FORM_addr:
  	case DW_FORM_ref_addr:
  		if (psz == sizeof(uint32_t))
  			val = dav->dav_u32;
  		else
  			val = dav->dav_u64;
  		break;
  	case DW_FORM_block1:
  	case DW_FORM_block2:
  	case DW_FORM_block4:
  	case DW_FORM_block:
  		dw_loc_parse(&dav->dav_buf, NULL, &val, NULL);
  		break;
  	case DW_FORM_flag:
  	case DW_FORM_data1:
  	case DW_FORM_ref1:
  		val = dav->dav_u8;
  		break;
  	case DW_FORM_data2:
  	case DW_FORM_ref2:
  		val = dav->dav_u16;
  		break;
  	case DW_FORM_data4:
  	case DW_FORM_ref4:
  		val = dav->dav_u32;
  		break;
  	case DW_FORM_sdata:
  	case DW_FORM_data8:
  	case DW_FORM_ref8:
  	case DW_FORM_udata:
  	case DW_FORM_ref_udata:
  		val = dav->dav_u64;
  		break;
  	case DW_FORM_strp:
  		val = dav->dav_u32;
  		break;
  	case DW_FORM_flag_present:
  		val = 1;
  		break;
  	default:
  		break;
  	}
  
  	return val;
  }
  
  const char *
  dav2str(struct dwaval *dav)
  {
  	const char *str = NULL;
  	extern const char *dstrbuf;
  	extern size_t dstrlen;
  
  	switch (dav->dav_dat->dat_form) {
  	case DW_FORM_string:
  		str = dav->dav_str;
  		break;
  	case DW_FORM_strp:
  		if (dav->dav_u32 >= dstrlen)
  			str = NULL;
  		else
  			str = dstrbuf + dav->dav_u32;
  		break;
  	default:
  		break;
  	}
  
  	return str;
  }
  
  const char *
  enc2name(unsigned short enc)
  {
  	static const char *enc_name[] = { "address", "boolean", "complex float",
  	    "float", "signed", "char", "unsigned", "unsigned char",
  	    "imaginary float", "packed decimal", "numeric string", "edited",
  	    "signed fixed", "unsigned fixed", "decimal float" };
  
  	if (enc > 0 && enc <= nitems(enc_name))
  		return enc_name[enc - 1];
  
  	return "invalid";
  }